Minimum connected dominating set algorithm based on directed diffusion

Abstract

A new minimum connected dominating set algorithm based on directed diffusion MCDSDD was proposed, which attempted to improve the existed area coverage algorithms through introducing node’s gradient in wireless sensor networks. During built a directed tree rooted from sink node using directed diffusion routing algorithm, an ascending node’s gradient series could be constructed. Non-adjacent sensor nodes were picked out and made up a maximum domi- nator set during routing information diffusion gradient by gradient, and then some intermediate nodes are sought from those nodes, which were adjacent to both nodes unconnected in maximum dominator set and their gradients just between them yet, to "glue" the non-adjacent two nodes in maximum dominator set, and last, an approximate minimum connected dominator set was constructed. Simulation results show that MCDSDD can save time and multiple covers hot spot in the surveillance area, and prolong the life time of the WSN.

Keywords

• wireless sensor networks;area coverage;minimum connected dominator set;directed diffusion;round-robin scheduling