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

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 communicati...

Full description

Saved in:
Bibliographic Details
Main Authors: Raei, H., Sarram, M., Adibniya, F., Tashtarian, F.
Format: Conference Proceeding
Language:English
Subjects:
Approximation methods
Color
Complexity theory
Connectors
Construction industry
Distributed algorithms
Wireless sensor networks
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2155-6806
2155-6814
DOI:10.1109/MAHSS.2008.4660106