Back to Search
Start Over
Fault-Tolerant Virtual Backbone in Heterogeneous Wireless Sensor Network.
- Source :
- IEEE/ACM Transactions on Networking; Dec2017, Vol. 25 Issue 6, p3487-3499, 13p
- Publication Year :
- 2017
-
Abstract
- To save energy and alleviate interference, connected dominating set (CDS) was proposed to serve as a virtual backbone of wireless sensor networks (WSNs). Because sensor nodes may fail due to accidental damages or energy depletion, it is desirable to construct a fault tolerant virtual backbone with high redundancy in both coverage and connectivity. This can be modeled as a $k$ -connected $m$ -fold dominating set (abbreviated as $(k,m)$ -CDS) problem. A node set $C\subseteq V(G)$ is a $(k,m)$ -CDS of graph $G$ if every node in $V(G)\backslash C$ is adjacent with at least $m$ nodes in $C$ and the subgraph of $G$ induced by $C$ is $k$ -connected. Constant approximation algorithm is known for $(3,m)$ -CDS in unit disk graph, which models homogeneous WSNs. In this paper, we present the first performance guaranteed approximation algorithm for $(3,m)$ -CDS in a heterogeneous WSN. In fact, our performance ratio is valid for any topology. The performance ratio is at most $\gamma $ , where $\gamma =\alpha +8+2\ln (2\alpha -6)$ for $\alpha \geq 4$ and $\gamma =3\alpha +2\ln 2$ for $\alpha <4$ , and $\alpha $ is the performance ratio for the minimum $(2,m)$ -CDS problem. Using currently best known value of $\alpha $ , the performance ratio is $\ln \delta +o(\ln \delta )$ , where $\delta $ is the maximum degree of the graph, which is asymptotically best possible in view of the non-approximability of the problem. Applying our algorithm on a unit disk graph, the performance ratio is less than 27, improving previous ratio 62.3 by a large amount for the $(3,m)$ -CDS problem on a unit disk graph. [ABSTRACT FROM PUBLISHER]
- Subjects :
- WIRELESS sensor networks
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 10636692
- Volume :
- 25
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- IEEE/ACM Transactions on Networking
- Publication Type :
- Academic Journal
- Accession number :
- 126885762
- Full Text :
- https://doi.org/10.1109/TNET.2017.2740328