2007 | OriginalPaper | Buchkapitel
Topology Control and Geographic Routing in Realistic Wireless Networks
verfasst von : Kevin M. Lillis, Sriram V. Pemmaraju, Imran A. Pirwani
Erschienen in: Ad-Hoc, Mobile, and Wireless Networks
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a distributed topology control protocol that runs on a
d
-QUDG for
d
≥ 1/
$\sqrt{2}$
, and computes 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 protocol is local and runs in
O
(1) rounds. 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
+
, we get the routing time guarantee of
O
(
l
2
) for any source-destination pair that are
l
units away from each other in the input d-QUDG. The key idea is simple: to obtain planarity, we 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).