Distributed MCDS constructing algorithm in Ad hoc networks
Aimin Liu · Jisuanji yingyong yanjiu · 2009
For the NP-hard problem of constructing minimum connected dominating set(MCDS) in Ad hoc networks,this paper proposed a novel distributed MCDS constructing algorithm called DMCA.DMCA constructed a MCDS for Ad hoc networks based on a maximal independent set(MIS).In DMCA,each node only required the knowledge of its one-hop neighbors and there existed only one shortest path connecting two dominators these were at most three hops away.The theoretical analysis shows that DMCA was fully localized,had a constant approximation ratio,and O(n) time complexity and O(n) message complexity.Detailed simulation results and comparisons with existed algorithms show that the proposed DMCA algorithm has less size of MCDS with varying node number and transmission range.