Maximal Independent Set Based Distributed Algorithm for Minimum Connected Dominating Set
Zhou Ming-tian · Dianzi xuebao · 2007
Broadcasting is a basic operation in wireless sensor networks and mobile ad hoc networks.Reducing redundant retransmission nodes to save network resource is a critical problem for broadcasting.Minimizing retransmission nodes in broadcasting is equivalent to minimizing connected dominating set in graph theory,and finding a minimum connected dominating set is NP-complete for graphs.Based on maximal independent set,this paper proposes a distributed algorithm for minimum connected dominating set(MISB),and proves the accurateness of the algorithm.The simulation results show that,using this algorithm,the size of the resultant connected dominating set is smaller.So the algorithm can reduce the retransmission nodes and save network resources efficiently in broadcasting.