Basic Research On Minimum Connected Dominating Sets

A Connected Dominating Set(CDS) performs a vital role in wireless sensor networks, which can establish a virtual backbone and thus leads to less energy consumption, maintenance overhead, above all, it can significantly reduce the influence of broadcast storms and improve the efficiency of communication between distributed nodes. However, finding the Minimum Connected Dominating Set(MCDS) is a NP-complete problem. And the distributed nodes in wireless sensor networks limited in power, storage resource and computing capability with the nature of self-organizing and self-control, many researchers have proposed many distinguish algorithms about how to find an approximate MCDS in the literature.The author proposes four distributed algorithms to find an approximate MCDS in static wireless sensor networks. The Algorithm-Ⅰis totally an asynchronously and parallelly distributed algorithm. The distributed node decides whether to join the connected dominating set only based on its 1-hop neighbor information. According to the fact that a Maximum Independent Set(MIS) is also a dominating set, the Algorithm-Ⅰ constructs an approximate MCDS by establishing an MIS first and then adds new nodes to the MIS to let subgraph induced by these nodes be connected. The knowledge to make the nodes in MIS become connected is obtained by 3-hop message relay combining with some rules. In the Algorithm-Ⅱ, the author introduces “effective degree” instead of degree of a node to select a dominator node into MIS, which can reduce the size of CDS effectively. The convergence time is not controlled and also directly related with the scale of networks and a network topology. Thus, the author proposes the Algorithm-Ⅲ which can be divided into two phases. By computer simulation, it can obtain the related parameters of time to generate an approximate MCDS. In the Algorithm- Ⅳ, it uses the Minimum-Weight Spanning Tree(MST) to optimize a prior Connected Dominating Set(CDS). The graph induced by the prior CDS can be subtly converted to a weight graph. And then an MST can be found from this weight graph to further optimize the CDS. This idea is first proposed in the literature. The simulation shows that the Algorithm-Ⅳ has an excellent performance to generate an approximate MCDS.