Constructing Minimum Connected Dominating Set: Algorithmic Approach
Govind Narayan Purohit, Usha Sharma · International Journal on Applications of Graph Theory In wireless Ad Hoc Networks And sensor Networks · 2010
Connected Dominating Set is popularly used for constructing virtual backbones for broadcasting operation in WSNs.UD Graph is the most suitable model for a wireless sensor network.In this paper we provide an algorithm to find MCDS in UD Graph.It is based on the computation of convex hulls of sensor nodes or vertices.Constructing a virtual backbone in WSNs is an important issue because it reduces unnecessary message transmission or flooding in the network.It helps in reducing interference and energy consumption because a limited number of sensors are engaged in message transmission and thus it helps in improving the Quality of Service (QoS) in the network.