Title | ||
---|---|---|
Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks |
Abstract | ||
---|---|---|
Connected dominating setis widely used in wireless ad-hoc and sensor networks as a routing and topology control backbone to improve the performance and increase the lifetime of the network. Most of the distributed algorithms for approximating connected dominating set are based on constructing maximal independent set. The performance of such algorithms highly depends on the relation between the size of the maximum independent set (mis(G)) and the size of the minimum connected dominating set (cds(G)) in the graph G. In this paper, after observing the properties of such subgraphs, we decrease the previous ratio of 3.453 to 3.0 by showing that mis(G) ≤ 3·mcds(G) + 3. Additionally, we prove that this bound is tight and cannot be improved. Finally, we present practical analysis of constructing connected dominating set based on maximal independent set in wireless networks. It is shown that the theoretical bound for unit disk graphis still practically applicable for general wireless networks. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/978-3-540-87779-0_33 | DISC |
Keywords | Field | DocType |
wireless network,general wireless network,previous ratio,sensor network,ad hoc,topology control backbone,unit disk,practical analysis,maximal independent set,maximum independent set,theoretical bound,sensor networks,connected dominating set,graph g.,unit disk graph,distributed algorithm | Discrete mathematics,Dominating set,Topology control,Computer science,Independent set,Connected dominating set,Wireless sensor network,Unit disk graph,Maximal independent set,Distributed computing,Domatic number | Conference |
Volume | ISSN | Citations |
5218 | 0302-9743 | 13 |
PageRank | References | Authors |
0.75 | 18 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alireza Vahdatpour | 1 | 237 | 15.94 |
Foad Dabiri | 2 | 288 | 27.01 |
Maryam Moazeni | 3 | 40 | 3.81 |
Majid Sarrafzadeh | 4 | 3103 | 317.63 |