Distributed MCDS constructing algorithm in Ad hoc networks
自组织网络分布式最小连通支配集创建算法*

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 a...