Constructing Minimum Connected Dominating Set: Algorithmic approach

Connected Dominating Set is popularly used for constructing virtual backbonesfor broadcasting operation in WSNs. UD Graph is the most suitable model for a wirelesssensor network. In this paper we provide an algorithm to find MCDS in UD Graph. It isbased on the computation of convex hulls of sensor nodes or vertices. Constructing avirtual backbone in WSNs is an important issue because it reduces unnecessary messagetransmission or flooding in the network. It helps in reducing interference and energyconsumption because a limited number of sensors are engaged in message transmissionand thus it helps in improving the Quality of Service (QoS) in the network