DocumentCode :
2971547
Title :
Efficient Algorithms for Connected Dominating Sets in Ad Hoc Networks
Author :
Kassaei, Hossein ; Mehrandish, Mona ; Narayanan, Lata ; Opatrny, Jaroslav
Author_Institution :
Dept. of Comput. Sci., Concordia Univ., Montreal, QC, Canada
fYear :
2010
fDate :
18-21 April 2010
Firstpage :
1
Lastpage :
6
Abstract :
A emph {Connected Dominating Set} (CDS) can be used as a routing backbone in ad hoc networks and a data gathering/dissemination infrastructure in sensor networks. This virtual backbone can efficiently narrow down the search space for a route to the nodes in the CDS and thus be used by any routing protocol. Ideally, the backbone should constitute the smallest percentage of nodes in the network. However, finding a emph{Minimum CDS} (MCDS) is an NP-hard problem. In this paper, we propose an efficient distributed algorithm to construct a CDS in general graphs. The time and message complexity of our algorithm is linear in the number of nodes and degree of the network. Extensive simulations on emph{Unit Disk Graphs} (UDGs) show that this algorithm outperforms the distributed algorithms proposed in cite{Butenko}, cite{Zone-Based}, cite{WAF}, and cite{ECDS} in terms of the size of the CDS. We also present a local implementation of our algorithm in location-aware UDGs. Our algorithm provides the flexibility to arbitrarily adjust the trade-off between the degree of locality and the size of the generated CDS.
Keywords :
Ad hoc networks; Approximation algorithms; Clustering algorithms; Distributed algorithms; Mobile ad hoc networks; Peer to peer computing; Robustness; Scalability; Spine; Testing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Wireless Communications and Networking Conference (WCNC), 2010 IEEE
Conference_Location :
Sydney, Australia
ISSN :
1525-3511
Print_ISBN :
978-1-4244-6396-1
Type :
conf
DOI :
10.1109/WCNC.2010.5506390
Filename :
5506390
Link To Document :
بازگشت