Article ID Journal Published Year Pages File Type
445468 Ad Hoc Networks 2016 13 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computer Networks and Communications
Authors
, , , ,