路由约束下的高效可靠虚拟骨干网构建算法

A high-efficiency and reliable algorithm on constructing virtual backbone network under routing constraint

大规模无线传感器中通常采用虚拟主干网来实现信息的有效传输,如何构建具备高效传输和一定容错性的虚拟骨干网成为当前学术界的研究热点之一。构建虚拟骨干网问题可以转化为图论中的构造连通控制集问题来解决,求解最小连通控制集(minimum connected dominating set,MCDS)问题已经被证明是非确定性多项式(non-deterministic polynomial,NP)完全问题,通过严格的理论分析和验证可以将近似算法多项式时间内求得的连通控制集规模限定在特定的约束范围内。本文提出一种同时考虑高效路由和容错性的虚拟骨干网构建算法,该算法采用m重控制来提高路由的容错性,时间复杂度为O(n 3)。通过理论分析和仿真实验发现,在二维平面内,设Mopt(1,m)为二维空间下最小m重连通控制集问题的最优解,当m≤5时,该连通控制集近似比为(240/m+5)Mopt(1,m);当m>5时,该连通控制集近似比为54Mopt(1,m)。

The virtual backbone network is usually used in large-scale wireless sensors to realize effective information transmission.How to construct a virtual backbone network with high-efficiency transmission and fault tolerance has become one of the important research hotspots in the current academic circle.The problem of constructing virtual backbone network can be transformed into the problem of constructing connected dominating sets in graph theory.Solving the minimum connected dominating set(MCDS)problem has been proved to be a problem of non-deterministic polynomial(NP)completeness.Through strict theoretical analysis and verification,the size of the connected dominant set solved within the time of the approximation algorithm polynomial can be limited within the scope of a specific constraint.This paper proposed an algorithm on constructing virtual backbone network simultaneously considering both high-efficiency routing and fault tolerance.The algorithm uses m-plex of control to improve the fault tolerance of routing with time complexity of O(n 3).Through theoretical analysis and simulation experiment,it is found that within the 2D plane,suppose that Mopt(1,m)is the optimal solution to the problem of minimum m-plex of connected dominating set within 2D space.When m≤5,the approximate ratio of the connected dominating set is(240/m+5)Mopt(1,m).When m>5,the approximate ratio is 54Mopt(1,m).