On the Computation of Virtual Backbones With Fault Tolerance in Heterogeneous Wireless Sensor Networks
- 5 January 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 21 (8) , 2922-2938
Abstract
In the context of wireless sensor networks (WSNs), the problem of virtual backbones (VBs) for undertaking routing tasks to alleviate broadcast storms has been extensively studied. In practical applications, different nodes in a WSN may have different transmission ranges because of differences in power control or functionality, among other reasons. In such a situation, a disk graph (DG) can be used as a mathematical model of the WSN, and a strongly connected dominating and absorbent set (SCDAS) in the DG can be treated as a VB in the corresponding WSN. In a WSN with faulty nodes, a fault-tolerant VB is superior to a traditional one. Thus, it is desirable to construct a $ k$ -strongly connected $ m$ -dominating and absorbent set ( $ (k,m)$ -SCDAS) in the DG to serve as a fault-tolerant VB in the corresponding WSN. In this article, to enable the construction of a high-quality $ (k,m)$ -SCDAS in a DG, a constant approximation algorithm with a performance ratio of $(2k(5^{k-1}-1)+1)(R+m+4(\frac{R}{m}+1))$ is proposed, where $ k$ and $ m$ are constants ( $ 2 \;\leqslant\; k \;\leqslant\; m$ ) and $ R$ is the maximum number of independent nodes within the transmission range of a node in the DG. A theoretical analysis and simulation results show that our work is superior to previous approaches.
Keywords
Funding Information
- National Natural Science Foundation of China (61761006, 61862003)
- Natural Science Foundation of the Guangxi Zhuang Autonomous Region of China (2018GXNSFDA281052)
This publication has 33 references indexed in Scilit:
- Applications of wireless sensor networks for urban areas: A surveyJournal of Network and Computer Applications, 2016
- Maximal Independent Sets in Heterogeneous Wireless Ad Hoc NetworksIEEE Transactions on Mobile Computing, 2015
- The first constant factor approximation for minimum partial connected dominating set problem in growth-bounded graphsWireless Networks, 2015
- A greedy algorithm for the minimum $2$ 2 -connected $m$ m -fold dominating set problemJournal of Combinatorial Optimization, 2014
- A new bound on maximum independent set and minimum connected dominating set in unit disk graphsJournal of Combinatorial Optimization, 2013
- On Enhancing Fault Tolerance of Virtual Backbone in a Wireless Sensor Network with Unidirectional Links2011
- On the construction of k-connected m-dominating sets in wireless networksJournal of Combinatorial Optimization, 2010
- On approximation algorithms of -connected -dominating sets in disk graphsTheoretical Computer Science, 2007
- On constructing k-connected k-dominating set in wireless ad hoc and sensor networksJournal of Parallel and Distributed Computing, 2006
- Distributed Construction of Connected Dominating Set in Wireless Ad Hoc NetworksMobile Networks and Applications, 2004