引用本文:张晶,喻小惠,黄云明.斯坦纳树和凸多边形的WSN分区双连通恢复[J].控制与决策,2019,34(11):2350-2357
【打印本页】   【HTML】   【下载PDF全文】   查看/发表评论  【EndNote】   【RefMan】   【BibTex】 附件
←前一篇|后一篇→ 过刊浏览    高级检索
本文已被:浏览次   下载 本文二维码信息
码上扫一扫!
分享到: 微信 更多
斯坦纳树和凸多边形的WSN分区双连通恢复
张晶1,2, 喻小惠1, 黄云明1
(1. 昆明理工大学信息工程与自动化学院,昆明650500;2. 云南枭润科技服务有限公司,昆明650500)
摘要:
针对无线传感器网络分区在恢复连通后仍然容错不足的问题,提出斯坦纳树和凸多边形的分区双连通恢复方法.首先,以距离为依据选取现有叶子节点来促使少数未连通的离散节点统一成区;然后,将分区抽象成点后枚举出所有的非退化型四边形,进而将计算得到的四边形中的两个斯坦纳点与4个顶点连接构造斯坦纳边部署中继节点,使分区实现单连通;最后,利用格雷厄姆凸壳算法选取抽象点中的凸壳顶点连接,形成凸多边形实现分区的双连通,并对第2轮连通路径上的中继节点实施休眠唤醒机制.在保证关键节点二次失效不会使网络再次瘫痪的基础上,简化网络结构并降低数据通信延迟.通过仿真,将所提出方案与利用最小斯坦纳树优化中继节点布局的分布式算法(DORMS)和1C-SpriderWeb算法进行对比,对比结果表明所提出方案可减少中继节点的部署数量,延长网络寿命.
关键词:  分区双连通  无线传感器网络  节点移动  斯坦纳树  凸多边形  休眠机制
DOI:10.13195/j.kzyjc.2019.0021
分类号:TP391.9
基金项目:国家自然科学基金项目(61562051);云南省技术创新人才基金项目(2019HB113).
Partition double connectivity recovery using Steiner tree and convex polygon in WSN
ZHANG Jing1,2,YU Xiao-hui1,HUANG Yun-ming1
(1.Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming650500,China;2. Yunnan Xiaorun Technology Service Co., Ltd.,Kunming650500,China)
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.
Key words:  partition double connectivity  wireless sensor network  node movement  Steiner tree  convex ploygon  sleeping mechanism

用微信扫一扫

用微信扫一扫