斯坦纳树和凸多边形的WSN分区双连通恢复
作者:
作者单位:

(1. 昆明理工大学信息工程与自动化学院,昆明650500;2. 云南枭润科技服务有限公司,昆明650500)

作者简介:

通讯作者:

E-mail: 1735335400@qq.com.

中图分类号:

TP391.9

基金项目:

国家自然科学基金项目(61562051);云南省技术创新人才基金项目(2019HB113).


Partition double connectivity recovery using Steiner tree and convex polygon in WSN
Author:
Affiliation:

(1.Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming650500,China;2. Yunnan Xiaorun Technology Service Co., Ltd.,Kunming650500,China)

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    针对无线传感器网络分区在恢复连通后仍然容错不足的问题,提出斯坦纳树和凸多边形的分区双连通恢复方法.首先,以距离为依据选取现有叶子节点来促使少数未连通的离散节点统一成区;然后,将分区抽象成点后枚举出所有的非退化型四边形,进而将计算得到的四边形中的两个斯坦纳点与4个顶点连接构造斯坦纳边部署中继节点,使分区实现单连通;最后,利用格雷厄姆凸壳算法选取抽象点中的凸壳顶点连接,形成凸多边形实现分区的双连通,并对第2轮连通路径上的中继节点实施休眠唤醒机制.在保证关键节点二次失效不会使网络再次瘫痪的基础上,简化网络结构并降低数据通信延迟.通过仿真,将所提出方案与利用最小斯坦纳树优化中继节点布局的分布式算法(DORMS)和1C-SpriderWeb算法进行对比,对比结果表明所提出方案可减少中继节点的部署数量,延长网络寿命.

    Abstract:

    For the problem that the wireless sensor network partition is still insufficient fault-tolerant after restoring their connectivity, we propose a partitioned dual connectivity recovery method based on Steiner tree and convex polygons. Firstly, the existing leaf nodes are selected based on distance to make a few disconnected discrete nodes unified into zones. The partition is abstracted into points and all non-degenerate quadrilaterals are enumerated. Two Steiner points in the quadrilateral are connected with four vertices to construct Steiner edge deployment relay nodes to make the partition simple connected. Finally, the Graham convex hull algorithm is used to select the convex hull vertices in the abstract points to connect to form convex polygons to realize the dual connectivity of the partition, and the sleeping mechanism is applied to the relay nodes on the second connected path. On the basis of ensuring that the secondary failure of key nodes will not paralyze the network again, the network structure is simplified and the data communication delay is reduced. By simulation, compared with the distributed algorithm for optimized relay node placement using minimum steiner tree(DORMS) and 1C-Sprider Web algorithms, the proposed scheme reduces the number of relay nodes deployed and prolongs the network lifetime.

    参考文献
    相似文献
    引证文献
引用本文

张晶,喻小惠,黄云明.斯坦纳树和凸多边形的WSN分区双连通恢复[J].控制与决策,2019,34(11):2350-2357

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2019-10-30
  • 出版日期: