Topology Construction Based on Minimum Connected Dominating Set for Wireless Sensor Networks

Topology construction based on virtual backbone communication is an effective way to shut down redundant nodes and save energy of whole network. In this paper, an issue of finding optimal virtual backbone through fully connected network is abstracted and converted into Minimum Connected Dominating Set (MCDS) issue while a new mathematical modeling approach which is called (NMIP)-MCDS based on Mixed Integer Programming is proposed. Furthermore, with the help of analyzing MCDS solution, the product of token distribution number and energy consumption from nodes are built as the goal of optimization function. Simultaneously, the optimal MCDS is constructed via manner of token distribution and network energy load balancing. Finally, simulation results show the effectiveness of NMIP-MCDS. It could be further applied to practical general WSNs.