基于斯坦纳树和泰森多边形的连通恢复算法

A connectivity restoration algorithm based on Steiner tree and Tyson polygon

针对无线传感器网络容易遭受恶劣环境破坏,连通恢复后各关键节点的能量损耗远大于其他节点从而导致网络断连的问题,提出基于斯坦纳树和泰森多边形的连通恢复算法(CRAST)。首先,将被分割的节点分区抽象为离散点,枚举出离散点区域内的所有非退化四边形,再使用四边形斯坦纳树结构对这些非退化四边形部署中继节点以达到连通恢复。然后,用关键节点构建Delaunay三角网,通过Delaunay三角网构建出整个无线传感器网络的泰森多边形拓扑结构。最后,在泰森多边形所有顶点部署可移动的备用中继节点,在关键节点损坏时通过比较备用节点所占关键节点对应的所有备用节点比重选择要移动的备用节点,移动备用中继节点替换损坏的关键节点。整个算法能使传感器网络以最少的代价实现连通恢复,并且拥有较强的高效性和健壮性。

Aiming at the problem that wireless sensor networks are susceptible to severe environmental damage and the energy consumption of key nodes is fast after connectivity restoration,which leads to network disconnection,this paper proposes a network connectivity restoration(CRAST)algorithm based on Steiner tree and Tyson polygon.Firstly,the algorithm abstracts the divided node partitions into discrete points,enumerates all non-degenerate quads in the discrete point area,and then uses the quadrangular Steiner tree structure to deploy relay nodes to these non-degenerate quads so as to achieve connectivity restoration.Secondly,the algorithm constructs a Delaunay triangle network with key nodes,and uses the Delaunay triangle network to construct the Tyson polygon topology of the entire wireless sensor network.Finally,the algorithm deploys movable backup relay nodes at all vertices of the Tyson polygon,and moves the backup relay node to replace the damaged key node when the key node is damaged.The algorithm enables the sensor network to achieve connectivity recovery at the least cost,and has strong efficiency and robustness.