计算机工程

作者：何峰, 梁家荣, 黎昌珍

单位：1. 广西大学 计算机与电子信息学院, 南宁 5300042. 广西大学 公共管理学院, 南宁 5300043. 广西多媒体通信与网络技术重点实验室, 南宁 530004

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

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

无线传感器网络的虚拟骨干是承担网络路由任务的结点组成的子集。当一个异质无线传感器网络故障时，原有的虚拟骨干可能就会失去部分功能，然而现有的容错虚拟骨干只能容纳顶点故障，无法解决只有链路故障但没有顶点故障的问题，且虚拟骨干大小会随故障顶点数量的增加呈超线性增加。针对上述问题，研究在异质无线传感器网络链路发生故障时的虚拟骨干重构问题。对于一个只有链路故障的异质无线传感器网络，设计一个虚拟骨干重构近似算法(ZREA22)，寻找一个未被控制的点组成的集合，在该集合导出的子图中构造一个极大独立集，并向该极大独立集和原连通控制集中添加结点以形成一个重构的连通控制集。实验结果表明，ZREA22算法能够产生一个大小有界的连通控制集，且虚拟骨干大小相比于WFSK09和SHLO14算法至少减少了9%和31%，同时算法运行时间更短。

来源：2023年第9期

《计算机工程》期刊编辑部

查看计算机工程杂志2023年第9期