RCDS: A Ranking-Based Algorithm to Compute the CDS of the Ad Hoc Networks

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.