异质无线传感器网络虚拟骨干重构  

Reconstruction of Virtual Backbones in Heterogeneous Wireless Sensor Networks

作　　者：何峰 梁家荣[1,3] 黎昌珍 HE Feng;LIANG Jiarong;LI Changzhen(School of Computer and Electronics Information,Guangxi University,Nanning 530004,China;School of Public Policy and Management,Guangxi University,Nanning 530004,China;Guangxi Key Laboratory of Multimedia Communications and Network Technology,Nanning 530004,China)

机构地区：[1]广西大学计算机与电子信息学院,南宁530004 [2]广西大学公共管理学院,南宁530004 [3]广西多媒体通信与网络技术重点实验室,南宁530004

出　　处：《计算机工程》2023年第9期191-198,共8页Computer Engineering

基　　金：国家自然科学基金(61862003);广西自然科学基金(2018GXNSFDA281052)。

摘　　要：无线传感器网络的虚拟骨干是承担网络路由任务的结点组成的子集。当一个异质无线传感器网络故障时,原有的虚拟骨干可能就会失去部分功能,然而现有的容错虚拟骨干只能容纳顶点故障,无法解决只有链路故障但没有顶点故障的问题,且虚拟骨干大小会随故障顶点数量的增加呈超线性增加。针对上述问题,研究在异质无线传感器网络链路发生故障时的虚拟骨干重构问题。对于一个只有链路故障的异质无线传感器网络,设计一个虚拟骨干重构近似算法(ZREA22),寻找一个未被控制的点组成的集合,在该集合导出的子图中构造一个极大独立集,并向该极大独立集和原连通控制集中添加结点以形成一个重构的连通控制集。实验结果表明,ZREA22算法能够产生一个大小有界的连通控制集,且虚拟骨干大小相比于WFSK09和SHLO14算法至少减少了9%和31%,同时算法运行时间更短。A Wireless Sensor Network(WSN)relies on a Virtual Backbone(VB),which comprises a subset of nodes solely responsible for routing tasks.In the event of failure within a heterogeneous WSN,the original VB's functionality may be compromised.However,existing fault-tolerant VBs only address node failures and do not account for scenarios involving link failures without node failures.Moreover,their size increases disproportionately with the number of faulty nodes.Therefore,to address the drawbacks associated with existing fault-tolerant VBs,this study investigates the challenge of reconstructing a VB for heterogeneous WSNs with faulty links.For a given heterogeneous WSN with faulty links,an approximation algorithm(ZREA22)is designed for VB reconstruction.The algorithm first selects the set comprising nodes that remain unaffected by the original connected dominating set.Next,it constructs a maximal independent set derived from the induced subgraph of the obtained set.Finally,additional nodes are added into both the maximal independent set and the original connected dominating set,thereby shaping the reconstructed connected dominating set.Experimental results confirm that ZREA22 can effectively generate a new VB with a predetermined upper bound on its size.Comparative analysis against benchmarks WFSK09 and SHLO14 reveal that ZREA22 achieves a reduction in VB size of no less than 9%and 31%,respectively.Furthermore,ZREA22 demonstrates superior performance in terms of runtime efficiency.

关 键 词：虚拟骨干 连通控制集 近似算法 无线传感器网络 双向链路圆盘图 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]