Book chapter
Topology Control and Geographic Routing in Realistic Wireless Networks
Ad-Hoc, Mobile, and Wireless Networks, pp.15-31
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2008
DOI: 10.1007/978-3-540-74823-6_2
Abstract
We present a distributed topology control protocol that runs on a d-QUDG for d ≥ 1/\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\sqrt{2}$\end{document}, 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(l2) 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).
Details
- Title: Subtitle
- Topology Control and Geographic Routing in Realistic Wireless Networks
- Creators
- Kevin M. Lillis - Saint Ambrose UniversitySriram V. Pemmaraju - University of IowaImran A. Pirwani - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Ad-Hoc, Mobile, and Wireless Networks, pp.15-31
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-540-74823-6_2
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2008
- Academic Unit
- Computer Science
- Record Identifier
- 9984259498302771
Metrics
2 Record Views