Optimal distributed algorithm for minimum connected dominating sets in Wireless Sensor Networks

Abstract

Since there is no fixed infrastructure or centralized management in wireless sensor network (WSN), a connected dominating set (CDS) has been proposed as a virtual backbone. The CDS plays a major role in routing, broadcasting, coverage and activity scheduling. To reduce the traffic during communication and prolong network lifetime, it is desirable to construct a minimum CDS (MCDS). For the MCDS problem, this kind of the networks usually has been modeled in unit disk graph (UDG), in which each node has the same transmission range. In this paper, a new distributed algorithm for MCDS problem in UDG with constant approximation ratio is introduced which has outstanding time complexity of O(1) and message complexity of O(n) . Theoretical analysis and simulation results are also presented to verify efficiencypsilas our approach.