Title :
Connected dominating sets in disk graphs with bidirectional links
Author :
Thai, My T. ; Du, Ding-Zhu
Author_Institution :
Dept. of Comput. Sci. & Eng., Minnesota Univ., Minneapolis, MN, USA
fDate :
3/1/2006 12:00:00 AM
Abstract :
In this paper, we study the connected dominating set (CDS) problem in disk graphs. The CDS problem has a significant impact on an efficient design of routing protocols in wireless networks. This problem has been studied extensively in unit disk graphs, in which each node has the same transmission range. However, in wireless ad hoc networks, the transmission ranges of all nodes are not necessary equal. In this paper, we introduce the CDS problem in disk graphs and present a constant approximation algorithm which can be implemented as a distributed algorithm.
Keywords :
ad hoc networks; distributed algorithms; graph theory; routing protocols; CDS problem; approximation algorithm; bidirectional link; connected dominating set; disk graph; distributed algorithm; routing protocol; wireless ad hoc network; Approximation algorithms; Distributed algorithms; Intelligent networks; Mobile ad hoc networks; Network topology; Routing protocols; Spine; Spread spectrum communication; Telecommunication traffic; Wireless networks;
Journal_Title :
Communications Letters, IEEE
DOI :
10.1109/LCOMM.2006.1603363
