控制与决策  2019, Vol. 34 Issue (11): 2350-2357  
0

引用本文 [复制中英文]

张晶, 喻小惠, 黄云明. 斯坦纳树和凸多边形的WSN分区双连通恢复[J]. 控制与决策, 2019, 34(11): 2350-2357.
[复制中文]
ZHANG Jing, YU Xiao-hui, HUANG Yun-ming. Partition double connectivity recovery using Steiner tree and convex polygon in WSN[J]. Control and Decision, 2019, 34(11): 2350-2357. DOI: 10.13195/j.kzyjc.2019.0021.
[复制英文]

基金项目

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

作者简介

张晶(1974—), 男, 教授, 博士生导师, 从事信息物理融合系统等研究, E-mail: 1735335400@qq.com;
喻小惠(1994—), 女, 硕士生, 从事信息物理融合系统的研究, E-mail: 1078233872@qq.com;
黄云明(1995—), 男, 硕士生, 从事信息物理融合系统的研究, E-mail: 409562143@qq.com

通讯作者

张晶, E-mail: 1735335400@qq.com

文章历史

收稿日期:2019-01-04
修回日期:2019-07-02
斯坦纳树和凸多边形的WSN分区双连通恢复
张晶 1,2, 喻小惠 1, 黄云明 1     
1. 昆明理工大学 信息工程与自动化学院,昆明 650500;
2. 云南枭润科技服务有限公司,昆明 650500
摘要:针对无线传感器网络分区在恢复连通后仍然容错不足的问题, 提出斯坦纳树和凸多边形的分区双连通恢复方法.首先, 以距离为依据选取现有叶子节点来促使少数未连通的离散节点统一成区; 然后, 将分区抽象成点后枚举出所有的非退化型四边形, 进而将计算得到的四边形中的两个斯坦纳点与4个顶点连接构造斯坦纳边部署中继节点, 使分区实现单连通; 最后, 利用格雷厄姆凸壳算法选取抽象点中的凸壳顶点连接, 形成凸多边形实现分区的双连通, 并对第2轮连通路径上的中继节点实施休眠唤醒机制.在保证关键节点二次失效不会使网络再次瘫痪的基础上, 简化网络结构并降低数据通信延迟.通过仿真, 将所提出方案与利用最小斯坦纳树优化中继节点布局的分布式算法(DORMS)和1C-SpriderWeb算法进行对比, 对比结果表明所提出方案可减少中继节点的部署数量, 延长网络寿命.
关键词分区双连通    无线传感器网络    节点移动    斯坦纳树    凸多边形    休眠机制    
Partition double connectivity recovery using Steiner tree and convex polygon in WSN
ZHANG Jing 1,2, YU Xiao-hui 1, HUANG Yun-ming 1     
1. Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China;
2. Yunnan Xiaorun Technology Service Co., Ltd., Kunming 650500, 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.
Keywords: partition double connectivity    wireless sensor network    node movement    Steiner tree    convex ploygon    sleeping mechanism    
0 引言

无线传感器网络(wireless sensor network, WSN)是信息物理系统(cyber-physical systems, CPS)感知阶段的重要应用. WSN主要布置在一些恶劣的野外环境, 例如海岸、边境保护、搜索和救援以及战场侦察[1], 并通过使小型传感器在这种恶劣设置中无人值守地运行, 可以降低应用成本并避免对人类生命造成风险.由于环境破坏且传感器自身由嵌入的小型电池供电, 在长时间工作或遭受意外情况时, 很有可能会造成节点的大面积失效, 进而将网络分割成为多个独立的分区, 导致通信失效.此时网络的生命周期基本结束, 丧失了数据感知、实时传输的功能[2-3].因此, 在WSN中如何恢复网络的连通性并且保障连通后的抗毁性显得至关重要.

现阶段对于网络的连通恢复主要通过移动现有节点和部署中继节点(relay node, RN)来完成.但是, 移动现有节点只适用于小规模的节点失效, 且大量移动现有节点会改变网络拓扑.通过改进算法找到连接分区的最短路径以部署最少的中继节点来恢复网络连通是最有效的办法. Lee等[4-5]先后提出基于服务质量的中继节点部署算法和DORMS算法, 通过启发式策略寻找中继节点的最佳数量以及位置. Senel等[6]首先选取各个分区的代表性节点与其他分区中的节点和中心位置节点进行连接形成1C-SpiderWeb算法, 虽然增大了分区之间的连通性, 但构成的网络拓扑过于复杂.几年后, Senel等[7]再次将中继节点的部署利用三角形斯坦纳树对初始部署进行优化, 通过分布式启发式方法以满足具有最少数量的RN的段间连接性要求.文献[8]通过能量采集率赋予节点权值进而计算各边权重, 构造最小生成树, 为低能量的非叶子节点部署RN来实现网络的可持续性.文献[9]通过采用凸壳算法构造骨干多边形, 连接区域内节点实现分区的双连通.文献[10]按照初始部署、启发部署、斯坦纳树部署3个步骤找到RN的最佳部署位置.文献[11]在此基础上利用四边形斯坦纳树来构造斯坦纳路径, 其仿真表明, 在节点平均度以及RN的数量上均有效益, 但恢复后的单连通降低了网络的稳定性和鲁棒性.

本文算法针对移动现有节点无法应对较大的分区规模和部署中继节点实现连通的低健壮性两个问题作出优化改进, 只把移动现有节点应用于统一成区中, 通过构造四边形斯坦纳边实现单连通, 再构造凸多边形实现分区的双连通, 并且通过加入休眠唤醒机制, 在保证后期数据正常通信的前提下, 最大限度地简化网络结构且达到节能, 延长网络工作时间的目的.

1 问题描述 1.1 网络模型

图 1的网络分区所示, 当给定区域内的WSN遭受大规模失效时, 各节点根据临近距离, 自适应形成多个网络分区Segi(i={1, 2, ..., n}), 并且在连通过程中每个分区抽象为点.基于此, 网络的连通恢复问题可以抽象为在区域A中, 存在离散的节点i个, 如何构造路径使得部署最少的中继节点来实现互不通信的各节点Segi之间的通信链路连通是本文的优化目标, 并且尽可能地保证连通后的网络具有高稳定性和高健壮性.

图 1 破坏后的分区场景图

用函数C(i, j)表示分区Segi与分区Segj之间连通之后的RN数量, 函数S(i, j)表示分区Segi和分区Segj连通后的通信情况, 若S(i, j)=1, 则分区之间可以进行通信.

优化目标用数学公式描述如下:

(1)

式(1)表示在两个分区连通的基础上, 分区之间用于连接的中继节点数量尽可能少.

对传感器节点和中继节点作出如下假设:

1) 本文中涉及的所有传感器节点和新的中继节点的通信半径是相同的.所有节点在半径以内可以感知接收和发送传输数据.应用如下的各种应用环境, 定理、引理等自动生成, 并按顺序生成编号.

2) 以distanceAB表示分区A与分区B之间的连接长度, 则连接线路e中需要部署RN的数量为

(2)

3) 求解该问题需要利用现有算法来获取各分区的位置信息以及特定的巡视设备来获取全局的分区信息, 进而根据各分区的方位和位置坐标来部署RN.

1.2 基础理论

根据文献[11]中凸集和凸壳算法的描述给出如下定理.

定理1  点集S中共有n(n>o)个点, 若其中的i个点依次连接形成多边形并且S中任意两个点的连线段npnq均位于该多边形中, 则称这i个点组成的集合为凸集.

定理2  点集S中凸壳顶点的选取方法如下:

1) 将离散的点集Sy坐标值最小的点定义为p1, 将p1同其他n - 1个节点连接起来形成n - 1条线段, 并依次计算这些线段与水平线的夹角, 按照夹角大小从小到大排序得到序列O(若pipjp1形成线段夹角相等且|p1pi|>|p1pj|, 则删除点pj).如图 2(a)所示在最终形成新的序列{p1, p2, ..., p7, p8}中, p1, p2, p8三个点必为凸壳顶点.

图 2 构造凸多边形

2) 将剩余的各顶点依次从前到后判断其凹凸性.

k=4, 若p1pk分别在线段pk-1pk-2的两侧, 则判断pk-1是凹点, 从点集中删除, 并且将pkpn的所有节点序列号减1;若p1pk分别在线段pk-1pk-2的同侧, 则判断pk-1是凸点, 执行k=k+1, 将所有节点全部进行判断, 最终得到所有的凸壳顶点.

按照如上方法, 图 2(a)中的所有凸壳顶点序列为{p1, p2, p5, p8}.将所有凸壳顶点连接起来形成凸多边形, 如图 2(b)所示.

根据文献[12]给出如下定理.

定理3  若一个四边形中有任意内角大于120°, 则将其称为退化型四边形.

定理4  找到非退化型四边形中两对角线形成的较小夹角中所对的两条边, 并以这两条边向外分别做两个等边三角形, 再对两个等边三角形做外接圆.连接两个等边三角形向外的顶点, 此连线与外接圆在非退化型四边形内部的交点即为四边形斯坦纳点.具体的做图过程在文献[12]中已经详细给出.

定理5  若一个三角形中有任意内角大于120°, 则将其称为退化型三角形.

定理6  对非退化型三角形的任意两边向外做等边三角形, 然后对两等边三角形的任意两边做外接圆, 两外接圆在三角形内部的交点即为三角形的斯坦纳点.

2 问题描述

本文提出的算法是先移动现有节点以融合少数未失效节点, 构成同一分区, 再对枚举的非退化型四边形依次找出四边形斯坦纳点对各分区实现单连通, 利用凸壳算法找出所有分区抽象节点的凸集, 依次连接构成各分区的双连通, 并通过唤醒机制调动双连通中各RN的工作.在保证网络不会因为少数关键节点的再次失效而陷入瘫痪的基础上最大程度地降低网络的复杂性.

为了方便理解本文算法中的详细步骤, 在此给出网络的原始失效分区的抽象图, 如图 3所示.

图 3 分区抽象图
2.1 现有节点成区

由于通信半径的限制, 导致了失效区域的不均匀性.少数节点与单独成区的距离相隔较近, 但又不具备自主通信能力, 此区域的节点相对比较密集, 若此时部署中继节点RN, 则只会增加成本和恢复连通的复杂度.此时可以根据成区范围内各节点的距离来选择哪一个节点移动, 使得少数节点可以与区内节点通信, 统一成区.以文献[12]中移动原有节点的方法为基础, 先进行失效节点探测, 然后指派最好的可用候选节点进行恢复操作.

定理7  用ξt(i)表示在t时刻节点i的位置.若|ξt(i)-ξt(j)| < R, 则表示节点i与节点j之间可以互相通信.

定理8  若节点i没有子节点, 则定义为叶子节点, 并且标记为Leaf(i)=1, 否则Leaf(i)=0.

将与单独失效节点与密集区域集合中心内的所有节点按照距离从小到大存放在数组Avb[]中, 以便优先选取距离较近的节点与叶子节点连接, 减少移动代价和通信代价.此过程的详细步骤如下.

Step 1: 若节点a与其他节点之间已经没有通信链路, 无法将自身感知的数据进行传输, 则判断其为单独失效节点, 需要与其他密集的节点统一成区.

Step 2: 对密集区域中的可通信节点依次编号1, 2, ..., n), 然后按照编号顺序依次判断它们是否为叶子节点.当有Leaf(i)=1时, 说明该节点移动不会造成该分区内拓扑结构发生变化, 可以用作移动节点, 并且依据Avb[]中元素的先后关系, 将这些叶子节点按照距离从小到大的顺序存储于数组move[]中.

Step 3: 将数组move[]中的元素依次移动, 移动后一端用于连接单独节点, 另外一端与数组Avb[]中的节点依次连接, 并且判断是否满足|ξt(i)-ξt(j)| < R且|ξt(j)-ξt(k)| < R.若符合, 则该叶子节点可用于移动.

图 4(a)可以看出, 节点k无法与分区A*直接通信, 若将节点k单独成区, 则不仅需要部署多余的RN, 并且有可能导致在后续的连通恢复过程中增加网络拓扑的复杂度.此时需要寻找在A*中符合条件的节点进行移动, 使得节点k与区域A*实现连通.

图 4 节点k统一成区

分区A*中的节点m为叶子节点, 说明可用作移动节点.且节点n为数组Avb[]中的第1个元素, 节点m在与k连通后有限选择与n相连, 且满足|ξt(k)-ξt(m)| < R, |ξt(m)-ξt(n)| < R, 则移动节点m使得节点k与分区A*重新统一分区为A, 如图 4(b)所示.

2.2 四边形斯坦纳树的单连通算法

文献[12]中已经证实, 按照四边形斯坦纳边部署方法可以有效减少RN的数量, 并且在分区连通后的节点平均度也提高.此过程的详细步骤如下:

Step 1: 在分区抽象的点集中, 采用蛮力法枚举出所有的非退化型四边形, 以此计算其周长, 并且按照从小到大的顺序排列, 存放于数组peri[]中.

Step 2: 按照数组中的先后顺序, 依次对4个顶点全部未被占用的四边形找出相应的2个斯坦纳点, 将四边形的4个顶点与2个斯坦纳点连接以构造斯坦纳边, 最后按照通信半径在斯坦纳边上部署中继节点.

Step 3: 将实现连通的4个分区继续抽象为一个新分区, 并与其他分区继续构造非退化型四边形, 对数组peri[]进行实时更新.

Step 4: 若对数组peri[]中的所有成员均遍历完成后, 仍有少数节点未被连通, 则判断是否能使用构造三角形斯坦纳点的方法进行第2轮连通, 若不能, 则选择距离最近的分区直接相连.

在9个分区可以构成的所有非退化型四边形中, SegA、SegB、SegC、SegD连通的四边形周长最小.首先, 构造斯坦纳边进行连通; 然后, 将这连通后4个分区看作一个更大的分区加入到非退化四边形的构造中.经过图 5处理后, 所有能够通过构造四边形斯坦纳边的分区全部连通, 剩余的分区不能再组成非退化型四边形.

图 5 四边形斯坦纳边连接分区

将剩余分区SegABCD, SegEFGH和SegI通过构造三角形斯坦那边的方法进行连通.经过图 6处理后, 所有的分区全部连通.整个网络再次实现数据正常传输, WSN投入正常工作.

图 6 基于三角形斯坦纳树恢复连通
2.3 基于休眠唤醒的凸多边形的双连通算法

通过2.2节的算法, 所有分区已经实现了单连通.但由于网络拓扑的异质性, 某些RN处于整个网络的关键位置, 承载着高频率的数据传输转发任务, 这将导致其能量相较于其他节点消耗较快.从分布的地理位置上看, 若这些关键RN由于能源耗尽失效, 则整个网络又将再次陷入瘫痪状态.

2.3.1 第2轮连通

通过格雷厄姆凸壳算法找到整个WSN中被判定为凸壳顶点的分区集合, 然后依次连接构造凸多边形.按照RN的通信半径部署中继节点, 由此各离散的分区之间构成连通的第2条路径.该路径为环形拓扑, 数据传输具有双向性, 因此可以有效降低当某个RN失效时, 数据无法传输的几率.

由于数据传输的随机性, 可能会选取路径较长的线路, 会增加数据通信的延迟和各节点的能量消耗.考虑到网络结构的复杂性, 在连通之后的前期阶段, 暂不开启凸多边形构成的第2条连通路径, 该路径上涉及的所有中继节点处于休眠状态, 最大程度上降低了这些RN的能耗.

图 7所示, 中继节点S处于关键位置, 若它失效, 则又将网络划分为如图 4中的3个分区.

图 7 基于凸多边形分区双连通

用文中所述算法, 首先找到网络中所有分区抽象出的所有节点中的凸壳顶点集合{segA, segB, segI, segH, segG}, 然后将集合中的点依次连接, 构造凸多边形.此时整个WSN中的所有分区均被涵括在其中.按照RN的通信半径, 在凸多边形中部署达成网络的双连通.此时该路径上的所有RN处于休眠状态, 不消耗能量.

2.3.2 传感器节点的休眠唤醒机制

传感器节点处于休眠、空闲、接收数据和发送数据4种状态的能耗之比为0.01: 4: 4: 20[13], 由此可见, 当节点处于空闲时的能耗是休眠时的400倍.因此在不影响网络的正常通信下, 尽可能多地使网络节点进入休眠状态可以大大降低网络功耗.所以, 规定只有当第1条连通路径中的关键节点再次失效或普通节点大量失效, 再次形成新分区导致数据无法正常通信时, 才能唤醒第2条路径上的RN进入工作状态.

首先, 将第2轮连通中的全部节点划分为活跃节点和休眠节点, 并且在首轮中以概率p(0 < p < 1)选取休眠节点的个数, 即

(3)
(4)

其中Nsecond表示第2轮连通路径上的节点总量.经过活跃节点和休眠节点相互替换得出每一轮中休眠节点和活跃节点的个数如下:

(5)
(6)

将每一轮中的活跃节点较为平均地分布在第2条路径上.当第1条路径无法满足当轮数据的传输时, 通过第2条路径中的活跃节点唤醒邻居节点的方式形成完整的通信链路, 从而进行数据的传输.

基于斯坦纳树和凸多边形的双连通算法(DWDC)的伪代码如下.

输入: 失效节点集合K, 分区集合Seg;

输出: 需要新布置中继节点的个数和位置坐标.

1)  Procedure DWDC(K, Seg)

2)  for k in K

3)      bubbleSort(Seg, k)

4)      for i=length(Seg) to 2 do

5)        if Seg[i]->Leaf==1 then

6)          move Seg[i]

7)        end if

8)        if length(k, Seg[1])/(length(Seg)-i+2) < R then

9)          break

10)      end if

11)    end for

12)  end for

13)  dealQuadrilateral(Seg)

14)  dealTriangle(Seg)

15)  if not all Seg connected then

16)    find shortest edge(u, v), u in the Seg 1, v in the Seg2

17)    deploy length(u, v)/Rnode between Seg1 and Seg 2

18)  end if

19)  C=create Convex Ploygon(Seg)

20)  for i=1 to length(C) do

21)      j=length(ci, ci.next)/R

22)      for l=0 to j do

23)        deploy node(l) between ci and ci.next

24)      end for

25)  end for

26)  equably sleep nodes on convex ploygon with p

27)  if the first connection lose efficacy then

28)      wake up all sleeped nodes

29)  end if

2.4 算法性能分析

本节将对本文算法的时间复杂度进行分析以及验证该算法在节能和在简化网络结构两方面的有效性.

1) DWDC算法的时间复杂度分析.

DWDC算法在孤立节点统一成区部分中, 第2、第3行采用冒泡排序对密集区域所有节点按照距离排序, 时间复杂度为O(n2).第4~第8行是移动节点实现连通, 时间复杂度是移动节点个数, 为常数.第13~第17行为分区单连通部分, 根据文献[12]所述该部分例举所有四边形并进行排序的时间复杂度为O(n4log n).第19行选取凸壳顶点构造凸多边形, 根据第1.2节描述的构建方法, 第1)部分中的角度排序时间复杂度为O(nlog n), 第2)部分判断顶点凹凸性, 时间复杂度为O(n).第26~第28行是对第2轮连通路径上的中继节点实现休眠机制, 实施的次数为网络运行轮数, 时间复杂度为O(n).故整个算法的时间复杂度为O(n4log n).

2) 本文提出的DWDC算法简化了网络结构并且具有节能作用.

在算法执行中前期, 由于四边形斯坦纳树连通路径完全可用, 此时不启用凸多边形的连通路径, 数据通信路径如图 6所示.在算法后期, 第1轮路径由于网络的异质性关键节点大量失效, 数据的传输路径转变为凸多边形.相比于文献[6]和文献[9], DWDC算法简化了网络结构.

图 6所示, 斯坦纳树算法构造的路径具有单一性, 所以一些节点承载较大的数据转发任务, 因此能量消耗较快, 一段时间后导致一些节点失效, 但这并不意味着第1轮路径完全不能工作.所以, 此时凸多边形上的节点以概率p保持休眠, 并且假设休眠节点是随机均匀分布的, 当活跃节点监听到有数据需要通过凸多边形路径传输时, 则唤醒休眠节点.由文献[13]可知, 若凸多边形上有n个中继节点, 则节点空闲状态消耗的能量是休眠状态的400 pn倍, 所以本文算法达到了节能效果.

3 实验仿真及分析

构造部署RN路径的方法多种多样, 由于DWDC算法主要研究分区的双连通性, 需要与同样是双连通恢复的1C-SpiderWeb算法进行比较.另外, 为了验证移动现有节点统一分区能够有效减少部署RN的数量以及构造四边形斯坦纳边的有效性, 进而与三角形斯坦纳树相关算法DORMS进行比较.

本文在Matlab的实验平台上, 与1C-SpiderWeb算法和DORMS算法在中继节点部署数量以及与网络的抗毁性两方面作出比较.将WSN的区域限定在1 500 × 1 500的正方形中, 通信半径R在40 m~240 m之间取值, 分区个数取值为6~9个, 为保证实验数据的普遍性, 让实验在多种随机组合的情况下取平均值.其他与实验相关的参数设置见表 1.

表 1 实验参数
3.1 中继节点数量

RN的数量是衡量传感器网络工作效率的重要指标.分区越多, 网络结构越复杂, 实现连通所需要的RN也越多; 通信半径越大, 相同距离所需要的RN越少.首先, 本文只在首轮连通断裂的情况下, 才唤醒第2轮连通的RN, 所以在进行中继节点的数量比较时只考虑单连通情况; 其次, RN的数量随着分区数量, 通信半径的改变而改变.因此, 需要采用控制变量的方法进行实验.

图 8给出了分区数量不同时, 通信半径和中继节点数量之间的关系.可以看出, 随着分区数量的减少以及通信半径的增大, 各算法所需的RN减少, 并且算法之间的RN数量差距也逐渐减小. 1C-SpiderWeb算法由于错综复杂的节点连接方式, 导致所需的RN最多, 并且随着分区数量减少所显现的RN数量减少跨度越大, 由此看出, 该算法不适合分区数量大的网络连通. DORMS算法使用三角形斯坦纳数的连通方法, 导致一次连通的分区数量少, 需要进行多次非退化型三角形的构造以及RN的部署, 因此相较于本文的DWDC算法所需的RN更多.

图 8 中继节点数量与通信半径及分区数量之间的关系

本文的DWDC算法在前期先利用现有节点移动使得少数节点可以统一成区, 不仅有效减少了用于连通的RN数量, 而且减少了数组peri[]中的元素数量, 进而减少了构造四边形斯坦纳树连通的次数.再者, 用四边形构造斯坦纳边的方式可以利用最短的连线路径连通更多分区, 说明DWDC算法的工作效率更高.

3.2 网络抗毁性

因为无线传感器网络的特殊布置环境, 当实现连通后极大可能会继续遭受大规模破坏, 进而关键节点失效导致分区的产生.于是, WSN的持续工作时间仍然是连通恢复后需要考虑的重要因素.根据文献[14]中的内容, 选取网络寿命作为网络抗毁性的度量标准.

为了证明实验的普遍有效性, 实验结果取(R, Nseg)分别为(40, 6)、(160, 7)、(80, 8)和(100, 9)四种实验场景结果的平均值.

当WSN工作一段时间后, 节点由于自身能量的限制或者是外界的破坏再次出现失效的情形, 如图 9所示, 3种算法连通后的网络寿命都随着节点失效数量的增多而减少. DORMS算法因其自身的单连通性和节点失效的随机性, 网络寿命相较于其他两种算法一直都呈现出较短的现象. 1C-SpriderWeb和DWDC两种算法在失效节点较少时, 网络运行的轮数趋近, 但当节点失效达到15个时, 由于1C-SpriderWeb算法中的节点的平均度降低以及少数关键节点的失效破坏了一部分数据通信的有效链路, 导致可工作轮数降低.本文提出的DWDC算法在失效节点达到30个时, 网络才完全停止工作, 且在失效节点个数相同时一直保持比其他两种算法拥有更长的网络工作时间.

图 9 连通后节点失效个数与网络寿命的关系
4 结论

本文提出的WSN中基于斯坦纳树和凸多边形的分区双连通恢复方法(DWDC)权衡中继节点数量和网络生命周期之间的关系, 有效提升了分区连通之后的容错效果.该算法通过移动现有节点有效减少中继节点数量并在二次连通路径上引入休眠唤醒机制, 以第1条路径无法完整进行数据通信作为触发事件.唤醒之后, 仍然保持以概率p轮换地选取一定数量的休眠节点.不仅利用第2轮中继节点延长了网络寿命能耗, 而且在初期简化了网络拓扑以及减少了数据包选择传输路径产生的时延.

下一步工作针对WSN受恶劣环境影响可能导致数据在感知、传输的过程中受到破坏的问题, 将延长网络寿命的相关算法同数据传输的安全性相结合, 使得整个网络具有更强的鲁棒性[15-16].

参考文献
[1]
Abbasi A A, Akkaya K, Younis M. A distributed connectivity restoration algorithm in wireless sensor and actor networks[C]. IEEE Conference on Local Computer Networks. Dubin, 2007: 496-503.
[2]
Bari A, Jaekel A, Jiang J, et al. Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirements[J]. Computer Communications, 2012, 35(3): 320-333. DOI:10.1016/j.comcom.2011.10.006
[3]
刘浩然, 尹文晓, 董明如. 一种强容侵能力的无线传感器网络无标度拓扑模型研究[J]. 物理学报, 2014, 63(9): 83-90.
(Liu H R, Yin W X, Dong M R. Study on the scale-free top ology mo del with strong intrusion-tolerance ability in wireless sensor networks[J]. Acta Physica Sinica, 2014, 63(9): 83-90.)
[4]
Lee S, Younis M. EQAR: Effective QoS-aware relay node placement algorithm for connecting disjoint wireless sensor subnetworks[J]. IEEE Transactions on Computer, 2011, 60(12): 1772-1787. DOI:10.1109/TC.2011.81
[5]
Lee S, Younis M. Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree[J]. Journal of Parallel & Distributed Computing, 2010, 70(5): 525-536.
[6]
Senel F, Younis M, Akkaya K. A robust relay node placement heuristic for structurally damaged wireless sensor networks[C]. The 34th IEEE Conference on Local Computer Networks. Zurich: IEEE, 2009: 633-640.
[7]
Senel F, Younis M. Relay node placement in structurally damaged wireless sensor networks via triangular steiner tree approximation[J]. Computer Communications, 2011, 34(16): 1932-1941.
[8]
吕志恒. 可持续WSN中基于能量采集感知的中继节点部署算法[J]. 传感技术学报, 2018, 31(5): 140-144.
(Lü Z H. Energy harvesting aware-based deploying relay nodes algorithm for survivable WSNs[J]. Chinese Journal of Sensors and Actuators, 2018, 31(5): 140-144.)
[9]
秦宁宁, 吴德恩, 余颖华. 基于骨干多边形的传感器网络分区双连通恢复算法[J]. 计算机工程与科学, 2017, 39(4): 673-677.
(Qin N N, Wu D E, Yu Y H. A double connectivity recovery algorithm in partition based on backbone polygon in sensor networks[J]. Computer Engineering and Science, 2017, 39(4): 673-677. DOI:10.3969/j.issn.1007-130X.2017.04.009)
[10]
秦宁宁, 吴德恩, 余颖华. 基于三角形斯坦纳树的分区连通性恢复算法[J]. 传感技术学报, 2016, 29(3): 423-428.
(Qin N N, Wu D E, Yu Y H. Con-nectivity recovery algorithm in partition based on triangle Steiner tree[J]. Chinese Journal of Sensors and Actuators, 2016, 29(3): 423-428. DOI:10.3969/j.issn.1004-1699.2016.03.020)
[11]
王丽青. GIS中的计算几何算法研究[D].长沙: 中南大学信息物理工程学院, 2008.
(Wang L Q. Rrsearch on algorithms of computation geometry in GIS[D]. Changsha: School of Information Physics Engineering, Central South University, 2008.) http://cdmd.cnki.com.cn/Article/CDMD-10533-2008167717.htm
[12]
陈洪生, 石柯. 基于四边形斯坦纳树的无线传感器网络连通恢复[J]. 计算机学报, 2014, 37(2): 457-469.
(Chen H S, Shi K. Quadrilateral Steiner tree based connectivity restoration for wireless sensor networks[J]. Chinese Journal of Computers, 2014, 37(2): 457-469.)
[13]
Hill J, Szewczyk R, Woo A, et al. System architecture directions for networked sensors[J]. Szqops Operating Systems Review, 2000, 34(5): 93-104. DOI:10.1145/384264.379006
[14]
Mellouk A, Mellouk A, Senouci H, et al. Performance evaluation of network lifetime spatial-temporal distribution for WSN routing protocols[J]. Journal of Network & Computer Applications, 2012, 35(4): 1317-1328.
[15]
Fang W, Zhang C, Shi Z, et al. BTRES: Beta-based trust and reputation evaluation system for wireless sensor networks[J]. Journal of Network & Computer Applications, 2016, 59: 88-94.
[16]
Sajjad S M, Bouk S H, Yousaf M. Neighbor node trust based intrusion detection system for WSN[J]. Procedia Computer Science, 2015, 63: 183-188. DOI:10.1016/j.procs.2015.08.331