Name
Abstract | ||
|---|---|---|
Construction of CDS (connected dominating set) is the foundation to build virtual backbone subnet or deploy layered routing in ad hoc or wireless sensor networks where packet flooding is extensively used. Current algorithm generally falls into two types: (1) cluster-based and (2) direct algorithm. This paper proposes a direct algorithm with linear time and message complexity. Our algorithm RCDS partitions the network nodes into dominators and dominatees. RCDS is a greedy algorithm which always chooses the farther and steadier node as future dominators. The experiment result shows that RCDS can construct smaller CDS than other algorithms. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/NCM.2008.26 | NCM (1) |
Keywords | Field | DocType |
smaller cds,ranking-based algorithm,backtrace,future dominator,algorithm rcds,linear time,experiment result,communication complexity,direct algorithm,virtual backbone subnet,greedy algorithm,current algorithm,connected dominating set,broadcast,greedy algorithms,packet flooding,wireless sensor networks,deploy layered routing,ad hoc networks,cluster-based algorithm,message complexity,approximation algorithms,clustering algorithms,wireless sensor network,data structures,ad hoc network | Approximation algorithm,Computer science,Algorithm,Computer network,Node (networking),Greedy algorithm,Subnet,Connected dominating set,Wireless ad hoc network,Time complexity,Wireless sensor network,Distributed computing | Conference |
Volume | ISBN | Citations |
1 | 978-0-7695-3322-3 | 0 |
PageRank | References | Authors |
0.34 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dong Shi | 1 | 5 | 1.17 |
| Xinming Zhang | 2 | 179 | 21.95 |
| Wenbo Zhu | 3 | 15 | 2.42 |
| Enbo Wang | 4 | 11 | 1.67 |