Distributed algorithm for connected Dominating Sets in Wireless Sensor Networks with different transmission ranges

Since there is no fixed infrastructure or centralized management in wireless sensor networks (WSNs), 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. The CDS problem has been studied inten...

Full description

Saved in:
Bibliographic Details
Main Authors: Raei, H., Sarram, M., Adibniya, F.
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Approximation methods
Complexity theory
Connected Dominating Set
Construction industry
Disk graph
Distributed algorithms
Optimized production technology
Virtual Backbone
Wireless Sensor Network
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 networks (WSNs), 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. The CDS problem has been studied intensively in unit disk graph (UDG), in which each node has the same transmission range. In real world this kind of networks are not necessarily contain nodes with equal transmission range. Recently one research has investigated the CDS problem in disk graph with bidirectional links (DGB), in which nodes have different transmission ranges. This approach has constant Approximation ratio with time and message complexity of O(n 2 ). In this paper, a new distributed algorithm for CDS problem in DGB with constant approximation ratio is introduced which has outstanding time complexity of O(n) and message complexity of O(nlog n).
DOI:10.1109/ISTEL.2008.4651324