In this paper, we propose an efficient, distributed and localized algorithm for finding an almost connected dominating set of small size on wireless ad hoc networks. Broadcasting and routing based on a connected dominating set (CDS) is a promising approach. A set is dominating if all the nodes of the network are either in the set or neighbors of nodes in the set. The efficiency of dominating-set-based broadcasting or routing mainly depends on the overhead in constructing the dominating set and the size of the dominating set. Our algorithm can find a CDS faster and the size of the found CDS is smaller than the previous algorithms proposed in the literature. Although our algorithm cannot guarantee the set found is actually a CDS but from our simulation results, the probabilities that the found set is a CDS are higher than 99.96% in all cases.
展开▼
