On Practical Reconstruction of Quality Virtual Backbones in Heterogeneous Wireless Sensor Networks With Faulty Nodes

作     者：He, Feng Liang, Jiarong Li, Qingnian 

作者机构：Guangxi Univ Sch Comp Elect & Informat Nanning 530004 Peoples R China Nanning Univ Coll Informat Engn Nanning 530200 Guangxi Peoples R China Guangxi Univ Sch Comp Elect & Informat Nanning 530004 Peoples R China Guangxi Univ Guangxi Key Lab Multimedia Commun & Network Techno Nanning 530004 Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT》 (IEEE Trans. Netw. Serv. Manage.)

年 卷 期：2024年第21卷第2期

页      面：2064-2076页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China 

主　　题：Connected dominating set distributed algorithm wireless sensor network approximation algorithm disk graph with bidirectional links 

摘      要：Frequently, unit disk graphs (UDGs) are used to model homogeneous wireless sensor networks (WSNs), in which each node has the same transmission radius. In some applications, however, different nodes in a WSN have different transmission radii, meaning that a UDG cannot accurately model the WSN. In this case, a disk graph with bidirectional links (DGB) can be used in place of a UDG. Nevertheless, most results reported to date concern the problem of finding minimum fault-tolerant CDSs in UDGs. In this paper, we investigate the minimum fault-tolerant CDS problem for DGBs by reconstructing CDSs for DGBs with faulty nodes. We present a centralized approximation algorithm for CDS reconstruction to address the minimum fault-tolerant CDS problem in given DGBs. The performance ratio (PR) of the presented algorithm is the same as that of the algorithm used to generate the input CDS C . Furthermore, we present a distributed version, which not only can be easily implemented in real situations but also considers CDS size to reduce the network cost. Theoretical analysis shows that the PR of our proposed algorithm is lower than those of other state-of-the-art algorithms for the minimum fault-tolerant CDS problem in given DGBs. In addition, numerical experiments objectively demonstrate that the performance of our algorithm is superior on average to that of its competitors in terms of CDS size, run time and application rate.