Construction of minimum connected dominating set in wireless sensor networks using pseudo dominating set

In a wireless network, messages need to be sent on in an optimized way to preserve the energy of the network. A minimum connected dominating set (MCDS) offers an optimized way of sending messages. However, MCDS construction is a NP-Hard   problem. In this paper, we propose a new degree-based greedy approximation algorithm named as Connected Pseudo Dominating Set Using 2 Hop Information (CPDS2HI), which reduces the CDS size as much as possible. Our method first constructs the CDS and then reduces its size further by excluding some of the CDS nodes cleverly without any loss in coverage or connectivity. The simulation results show that our method outperforms existing CDS construction algorithms in terms of both the CDS size and construction cost. CPDS2HI retains the current best performance ratio of (4.8+ln5)|opt|+1.2,(4.8+ln5)|opt|+1.2, |opt| being the size of an optimal CDS of the network, and has the best time complexity of O(D), where D is the network diameter. To the best of our knowledge this is the most time efficient and size-optimal CDS construction algorithm. It has a linear message complexity of O(nΔ), where n is the network size and Δ is the maximum degree of all the nodes.