基于网络分层的连通支配集算法

In Wireless Sensor Networks, Virtual Backbone is an important method to optimize network performance. In mathematics，the construction of Virtual Backbone equivalent to seeking the Minimum Connected Dominating Set(MCDS) which has been to proved to be NP-complete problem. A heuristic approach is an approximate solution. This paper presents LCDS algorithm (A Layer Based CDS Construction Algorithm) proposes a layer model. First, this algorithm selects a source node (sink or cluster head), then it starts a broadcast from this node to divide networks into several layers according to hops. After layer is divided, each layer performing CDS construction algorithm computes dominating set separately, and the union of dominating set of all layers acts CDS of networks. The time complexity of LCDS is where represent average degree of nodes. Simulation results show that, LCDS algorithm gets a smaller CDS than other algorithms which include MTCDS[6] and MISB[10] algorithm and with the rapid increase of network density, the increase of CDS is very slow. When nodes of WSN have a very large density, LCDS algorithm is still able to get a smaller CDS.