无线传感器网络增配节点实现双连通并优化中继路径

Supplement nodes in wireless sensor network to achieve biconnectivity and optimize relay paths

对所有节点有统一通信功率和传输半径的无线传感器网络,用平面无向图建模。提出一个基于广度优先的O(n^3)多项式时间搜索算法来发现无线传感器网络中的双连通分量,继而确定网络中所有关节点,然后提出一个最坏情况有O(n^2log(n/3))多项式计算时间的贪心算法来增加尽量少的节点以实现网络双连通,同时,增配节点形成的新路径有助于减少部分节点到汇聚节点的中继跳数。实验结果也验证了以上算法的效果。

Wireless sensor network with uniform communication power and transmission radius was modeled as planar undirected graph. A search algorithm running in O（n^3 ） polynomial time was proposed to find all the biconnected components in the wireless sensor network, and then all the articulation points in the network can be found out. A greedy algorithm with worst case 0（ n^2log（ n/3 ） ） polynomial time bound was proposed to supplement nodes as few as possible to achieve network biconnectivity. At the same time, the new paths formed by the supplemented nodes help to decrease the number of relay hops between some sensor nodes and the sink node. The experimental results verify the effect of the algorithms.