5th International ICST Conference on Wireless Internet

Research Article

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

Download339 downloads
  • @INPROCEEDINGS{10.4108/ICST.WICON2010.8525,
        author={Vahid Ghasemi and Seyed Naser Hashemi and Mojtaba Mozaffari},
        title={Connected dominating set construction using an efficient pruning method in ad hoc networks},
        proceedings={5th International ICST Conference on Wireless Internet},
        publisher={IEEE},
        proceedings_a={WICON},
        year={2010},
        month={4},
        keywords={connected dominating set (CDS) wireless ad hoc networks flooding pruning},
        doi={10.4108/ICST.WICON2010.8525}
    }
    
  • Vahid Ghasemi
    Seyed Naser Hashemi
    Mojtaba Mozaffari
    Year: 2010
    Connected dominating set construction using an efficient pruning method in ad hoc networks
    WICON
    IEEE
    DOI: 10.4108/ICST.WICON2010.8525
Vahid Ghasemi1,*, Seyed Naser Hashemi1,*, Mojtaba Mozaffari1,*
  • 1: Department of Computer Science, Amirkabir University of Technology, Tehran, Iran
*Contact email: vahid.ghasemi@aut.ac.ir, nhashemi@aut.ac.ir, mozaffar@aut.ac.ir

Abstract

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.