Constructing Minimum Connected Dominating Set: Algorithmic Approach

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 the authors 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.