A greedy approximation algorithm for the minimum (2,2)-connected dominating set problem

Using a connected dominating set (CDS) to serve as the virtual backbone of a wireless sensor network (WSN) is an effective way to save energy and reduce the impact of broadcasting storms. Since nodes may fail due to accidental damage or energy depletion, it is desirable that the virtual backbone is...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-05
Main Authors: Aneja, Yash P, Mukhopadhyay, Asish, Rahman, Md Zamilur
Format: Article
Language:English
Subjects:
Approximation
Backbone
Depletion
Energy conservation
Fault tolerance
Graph theory
Greedy algorithms
Impact damage
Mathematical analysis
Remote sensors
Storm damage
Wireless sensor networks
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Using a connected dominating set (CDS) to serve as the virtual backbone of a wireless sensor network (WSN) is an effective way to save energy and reduce the impact of broadcasting storms. Since nodes may fail due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault tolerant. This could be modeled as a k-connected, m-fold dominating set ((k,m)-CDS). Given a virtual undirected network G=(V,E), a subset C\subset V is a (k,m)-CDS of G if (i) G[C], the subgraph of G induced by C is k-connected, and (ii) each node in V\C has at least m neighbors in C. We present a two-phase greedy algorithm for computing a (2,2)-CDS that achieves an asymptotic approximation factor of \((3+\ln(\Delta+2))\), where \(\Delta\) is the maximum degree of G. This result improves on the previous best known performance factor of \((4+\ln\Delta+2\ln(2+\ln\Delta))\) for this problem.
ISSN:2331-8422