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

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

传感器网络中最小k-连通m-控制集问题的近似算法

在当前无线传感器网络的相关研究中,虚拟骨干网的构造引起广泛的关注.通过引进虚拟骨干网来设计路由协议,使得路由更加可靠和高效,从而减少广播风暴.无线传感器网络中具有容错功能的虚拟骨干网的构造可转化为圆盘图中的最小k-连通m-控制集问题.本文研究了具有不同传输半径的双向圆盘图中的最小k-连通m-控制集问题,给出了一个构造最小k-连通m-控制集的多项式时间近似算法,理论分析表明该算法具有较好的近似比.最后,在不同的网络拓扑上进行了仿真实验,仿真结果进一步验证了算法的有效性.