Distributed Spanners with Bounded Degree for Wireless Ad Hoc Networks

Yu Wang (joint work with Prof. Xiang-Yang Li)
Department of Computer Science, Illinois Institute of Technology

Abstract

In this paper, we propose some new distributed algorithms that construct the
sparse subgraphs of the unit disk graph efficiently for wireless ad hoc
networks. They maintain a linear number of links while still preserving some
power-efficient routes for any pair of nodes. We prove that all structures
have bounded node degrees, and the Yao and Sink structure has a bounded
power stretch factor in general unit disk graph, while the Yao plus reverse
Yao graph has a bounded power stretch factor in civilized unit disk graph.
In addition, we show that the symmetric Yao graph does not have a constant
bounded power stretch factor. Finally, we conduct simulations to study the
practical performances of these structures. All structures have small power
stretch factors for randomly generated unit disk graphs.