• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2020, Vol. 42 ›› Issue (08): 1352-1358.

• 计算机网络与信息安全 • 上一篇    下一篇

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

王茂秋1,张江2,张晶1,3,4    

  1. (1.昆明理工大学信息工程与自动化学院,云南 昆明 650500;
    2.中国船舶集团有限公司第七〇五研究所昆明分部,云南 昆明 650102;
    3.云南枭润科技服务有限公司,云南 昆明 650500;4.昆明理工大学云南省人工智能重点实验室,云南 昆明 650500)

  • 收稿日期:2020-01-09 修回日期:2020-03-11 接受日期:2020-08-25 出版日期:2020-08-25 发布日期:2020-08-29
  • 基金资助:
    云南省技术创新人才资助项目(2019HB113);云南省“万人计划”产业技术领军人才资助项目(云发改人事[2019]1096号)

A connectivity restoration algorithm based on Steiner tree and Tyson polygon

WANG Mao-qiu1,ZHANG Jiang2,ZHANG Jing1,3,4   

  1. (1.Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500;

    2.Kunming Branch of the 705th Research Institute of China State ShipBuilding Co.,Ltd.,Kunming 650102;

    3.Yunnan Xiaorun Technology Service Co.,Ltd.,Kunming 650500;

    4.Yunnan Key Laboratory of Artificial Intelligence,Kunming University of Science and Technology,Kunming 650500,China)

  • Received:2020-01-09 Revised:2020-03-11 Accepted:2020-08-25 Online:2020-08-25 Published:2020-08-29

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

关键词: 连通恢复, 斯坦纳树, 泰森多边形, 备用节点移动

Abstract: 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.


Key words: connectivity restoration, Steiner tree, Tyson polygon, standby node movement