Connected dominating set construction using an efficient pruning method in ad hoc networks

In a broadcasting process in wireless ad hoc networks, the number of retransmissions of a packet i.e. the number of forwarder nodes, is generally considered as the cost of broadcasting. A connected dominating set (CDS) is an infrastructure used to manage broadcast of packets such that only nodes in the CDS forward the packets. In this paper an enhanced algorithm to construct a connected dominating set is presented. In the first step, we use a known local algorithm to determine the primary CDS. Then an efficient probabilistic pruning process is suggested to implement the secondary CDS. As a result, the number of nodes in the pruned CDS decreases efficiently. The performance of the suggested method, in terms of the size of the secondary CDS and the message length of broadcast, is discussed and compared to an efficient local algorithm based on complete 2-hop information having a message length O(m^2), where m is the maximum degree of nodes in the network. Simulations show that our method is good for sparse networks, while for dense networks, it works almost similarly like the algorithm using complete 2-hop information. Our algorithm has the message length O(m) and decreases the size of CDS significantly. Therefore, it has a better performance in contrast to the algorithm with complete 2-hop information.