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

作者：何峰; 梁家荣; 黎昌珍^*

来源：计算机工程, 2023, 49(09): 191-198.

DOI：10.19678/j.issn.1000-3428.0066831

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

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

• 单位
  广西大学