Distributed Algorithms for Coloring and Domination in Wireless Ad Hoc Networks

Part of this work was done when the author was a student at the University of Maryland and was supported by NSF Award CCR-9820965. Research also supported by Rutgers University’s Research Council

grant. Abstract. We present fast distributed algorithms for coloring and (connected) dominating set construction in wireless ad hoc networks. We present our algorithms in the context of Unit Disk Graphs which are known to realistically model wireless networks. Our distributed algorithms take into account the loss of messages due to contention from simultaneous interfering transmissions in the wireless medium. We present randomized distributed algorithms for (conflict-free) Distance-2 coloring, dominating set construc- tion, and connected dominating set construction in Unit Disk Graphs. The coloring algorithm has a time com- plexity of O(∆log2n) and is guaranteed to use at most O(1) times the number of colors required by the optimal algorithm. We present two distributed algorithms for constructing the (connected) dominating set; the former runs in time O(∆log2n) and the latter runs in time O(log2n). The two algorithms differ in the amount of local topology information available to the network nodes. Our algorithms are geared at constructing Well Connected Dominating Sets (WCDS) which have certain powerful and useful structural properties such as low size, low stretch and low degree. In this work, we also explore the rich connections between WCDS and routing in ad hoc networks. Specifically, we combine the properties of...

Website: www.crab.rutgers.edu | Filesize: -
No of Page(s): 12
Download Distributed Algorithms for Coloring and Domination in Wireless Ad ....pdf