A connected dominating set (CDS) can act as a virtual backbone (VB) in a wireless sensor network (WSN). The overhead in a WSN is usually determined by the size of the corresponding VB. However, the construction of minimum CDSs (MCDSs) has been proven to be an NP-hard problem. Thus, most researchers use approximation algorithms to find smaller CDSs. In certain applications, the transmission radii of some nodes in the network are unstable due to certain environmental factors such as obstacles, signal interference and node movement. Thus, the robustness of VBs in WSNs should be considered. In this paper, we propose the concept of a d-robust CDS and corresponding algorithms to construct d-robust CDSs in WSNs with unstable transmission ranges. We propose algorithms for a d-robust CDS that is bounded by [40.68/(1 - d) 2 + 10.17] · opt + [31.32/(1 - d) 2 + 7.83], where opt is the size of the MCDS and d ∈ [0, 1). Through simulations, we show the relationship between the size of the d-robust CDS and the value of d and compare our algorithms with existing algorithms in terms of the robustness degree of the CDS. The results show that the CDSs produced by our algorithms exhibit better robustness.
5 January 2021 in IEEE Transactions on Mobile Computing
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.
The work of routing and topological control for a wireless sensor network (WSN) is often undertaken by means of its virtual backbone (VB). Usually, a WSN and its VB can be modeled as a unit disk graph (UDG) and a corresponding connected dominating set (CDS), respectively. A smaller CDS in a UDG is preferred because it will lead to less overhead. In practical applications, sensor nodes or their links in a WSN may fail due to obstacles or accidental damage. Thus, it is desirable to either construct a robust VB or be able to reconstruct a new VB. In this paper, the problem of reconstructing CDSs for UDGs with faulty links is considered. First, we propose a centralized approximation algorithm for the problem. We theoretically show that for a given UDG, the size of the CDS constructed by our algorithm does not exceed $\xi \cdot opt+\gamma +2m$ , where $\xi \cdot opt+\gamma$ is the upper bound on the original CDS size, $opt$ is the minimum CDS size in the UDG, $\xi$ and $\gamma$ are two positive constants, and $m$ is the number of faulty links. Next, we design a distributed approximation algorithm on the basis of our centralized approximation algorithm and analyze its time and message complexity. Related simulation experiments are presented to compare our algorithm with other state-of-the-art algorithms for solving this problem, and the results show that our algorithm outperforms its competitors.
Wireless sensor networks (WSNs) are extensively utilized in various circumstances. For applications, the construction of the virtual backbones (VBs) of WSNs has attracted considerable attention in this field. Generally, a homogeneous WSN is formulated as a unit disk graph (UDG), and the VB of the corresponding WSN is modeled as a connected dominating set (CDS) in the UDG. In certain applications, communication between sensors in a network may fail for various reasons, such as sensor movement, signal interference, and the appearance of obstacles. Consequently, a CDS in a UDG should possess fault tolerance on the edges. In this paper, we introduce a new concept called the 2 edge‐connected 2 edge‐dominating set ((2, 2)‐ECDS); then, we design an approximation algorithm for computing (2, 2)‐ECDSs in UDGs, the performance ratio of which is 30.51. By means of simulations, we compare our algorithm and existing algorithms in terms of the CDS size, running time, success rate, and network lifetime. The simulation results indicate that our algorithm exhibits better performance and is more suitable for constructing a VB with edge fault tolerance in a WSN.