摘要：In this paper, a Connected Dominating Set (CDS) construction algorithm CSCDS (Connected Subset based CDS) is proposed, which is based on the connected subset concept. The CSCDS contains two main stages, which arc dominating set construction stage and connected dominating set construction stage respectively. In the first stage, the dominators are proposed based on the one hop white neighbor information, and the redundant dominators are reduce to obtain the minimum number of dominators. In the second stage, the CDS is constructed based on the connected subset, which is used as the basis to select the connectors. The message complexity is 0(Δ~2) (0(Δ~2) is a linear relationship function with Δ~2, and Δ is the maximum one hop neighbor degree), Simulation results show that CSCDS has smaller size compared with the classical algorithms.
关键词：Connected dominating set ; connected subset ; wireless networks ; dominating set construction stage ; connected dominating set construction stage
