基于骨干多边形的传感器网络分区双连通恢复算法

计算机工程与科学

基于骨干多边形的传感器网络分区双连通恢复算法

秦宁宁1,2，吴德恩1，余颖华1

（1.江南大学物联网工程学院，江苏无锡 214122；
2.江南大学轻工过程先进控制教育部重点实验室，江苏无锡 214122）

收稿日期:2015-12-28 修回日期:2016-03-04 出版日期:2017-04-25 发布日期:2017-04-25
基金资助:
江苏省“六大人才高峰”第十一批高层次人才项目(DZXX026)；2014年国家公派高级研究学者及访问学者(含博士后)项目；国家自然科学基金(61304264)；江苏高校优势学科建设工程资助项目（PAPD）；江苏省产学研联合创新资金前瞻性联合研究项目（BY201402331）；中央高校基本科研业务费专项资金（JUSRP51510）

A double connectivity recovery algorithm in partition

based on backbone polygon in sensor networks

QIN Ning-ning1,2，WU De-en1，YU Ying-hua1

（1.School of Internet of Things Engineering,Jiangnan University,Wuxi 214122；

2.Key Laboratory of Advanced Process Control for Light Industry of

Ministry of Education,Jiangnan University,Wuxi 214122,China）

Received:2015-12-28 Revised:2016-03-04 Online:2017-04-25 Published:2017-04-25

摘要/Abstract

摘要：

针对现有算法恢复分区连通性存在容错性差的问题，提出了分区双连通性恢复算法DCRA。该算法旨在网络中心区域构建骨干多边形，分区以两条互不相交的路径与多边形连接，从而实现分区间的双连通。仿真实验表明，与现有一些双连通算法相比，所提算法不仅减少了部署中继节点的数量，而且算法的运行时间能够减少60%左右，可以快速确定部署的中继节点位置，从而快速恢复分区连通性。

关键词: 双连通, 容错性, 骨干多边形, 中继节点

Abstract:

In order to solve the problem that the existing algorithms have poor fault tolerance when recovering the partition connectivity, we propose a double connectivity recovery algorithm in partition (DCRA). The algorithm aims at building a backbone polygon in the center area of the network and connecting partitions with the polygon by two disjoint paths to realize double connectivity between partitions. Simulation experiments show that compared with some existing double connectivity algorithms, the proposed algorithm cannot only reduce the number of deployed relay nodes and the running time of the algorithm by about 60%, but also quickly determine the location of the relay nodes so as to quickly recovery partition connectivity.

Key words: double connectivity, fault tolerance, backbone polygon, relay node

秦宁宁1,2，吴德恩1，余颖华1. 基于骨干多边形的传感器网络分区双连通恢复算法[J]. 计算机工程与科学.

QIN Ning-ning1,2，WU De-en1，YU Ying-hua1.

A double connectivity recovery algorithm in partition

based on backbone polygon in sensor networks

[J]. Computer Engineering & Science.

[1]	曹敦1,2，雷正保1. 一种山区环境下车际网的中继节点选择方法[J]. 计算机工程与科学, 2017, 39(02): 297-302.
[2]	刘天明，张大方，曾彬，谢希，李明伟. 一种基于改进HyperCast的多播协议[J]. J4, 2010, 32(4): 14-17.
[3]	陈龙，李鹏. 一种基于完整性指示码的电子证据分散存储改进方法[J]. J4, 2010, 32(11): 60-62.
[4]	王国军陈松乔等. 具有大量错误结点的超立方体网络中并行路由算法[J]. J4, 2001, 23(5): 5-12.