Abstract:Because finding a minimum connected domination set (MCDS) for a general connected network is NP-complete, a topology-aware heuristic algorithm is proposed in this paper whose correctness is proved. By taking advantage of the topology characteristic of nodes, the algorithm can reduce the blindness in the process of selecting dominating nodes, and form a smaller CDS (connected domination set) based on 2-hop local information, consequently obtain a virtue backbone network with the CDS. The simulation results show that the algorithm is superior to other distributed CDS algorithms, and closer to minimum CDS.