Topology Control and Geographic Routing in Realistic Wireless Networks
Kevin M. Lillis, Sriram V. Pemmaraju and Imran A. Pirwani
We present distributed topology control protocols that run on a d-QUDG for d ≥ 1/√2, and compute a sparse, constant-spanner, both in Euclidean distance and in hop distance. QUDGs (short for Quasi Unit Disk Graphs) generalize Unit Disk Graphs and permit more realistic modeling of wireless networks, allowing for imperfect and non-uniform transmission ranges as well as uncertain node location information. Our protocols are local and run in O(1) rounds and yield an output topology in which each node maintains information on a constant number of neighbors. The output topology permits memoryless, geographic routing with guaranteed delivery. In fact, when our topology control protocol is used as preprocessing step for the geographic routing protocol GOAFR+ (PODC 2003), we get the routing path length guarantee of O(ℓ2) for any source-destination pair that are units away from each other in the input d-QUDG. Our results build upon a simple and elegant proposal by Kuhn et al. (DIALM-POMC 2003): to obtain planarity, replace each edge intersection with a virtual node and have a real node serve as a proxy for the virtual node. This idea is supported by other parts of our protocol that (i) use clustering to keep the density of edge crossings bounded and (ii) guarantee that an edge between a virtual node and a neighbor is realized by a constant-hop path in the real network. The virtual node idea is simple enough to be useful in many contexts. For example, it can be combined with a scheme recently suggested by Funke and Milosavljević (INFOCOM 2007) to guarantee delivery under uncertain node locations. Similarly, the virtual nodes idea can also be used as a cheap alternative to edge-crossing removal schemes suggested by Kim et al. (DIALM-POMC 2005, SENSYS 2006).
Keywords: Wireless sensor networks, topology control, geographic routing, clustering, unit disk graphs, quasi unit disk graphs, spanners.