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

王茂秋，张 江，张晶,3,4

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

1 引言

在信息化时代，实时掌握指定区域内状态的技术常被应用到军事、气象等多个领域[1]，作为计算机网络中最重要的技术，无线传感器网络也得到了前所未有的发展。无线传感器网络中的传感器节点通过对覆盖区域进行数据的收集、信息的检测、信息的识别、位置的定位和节点的操控来保证对指定区域的信息控制[2]。然而在无线传感器网络领域，仍有很多问题需要进一步解决，传感器节点通常容易因为条件复杂的环境而损坏，再加上节点需要控制自身体积，其所能拥有的能量有限，一旦部分节点损坏或者能量耗尽，会导致正常节点与失效节点无法通信，使得整个传感器网络被隔离成若干个独立的分区，最终导致网络瘫痪。因此，如何恢复传感器网络的连通并且保障恢复后网络的高效性和健壮性成为了此领域的研究热点[3]。

近年来，很多学者为无线传感器网络连通恢复相关工作做出了努力，Abbasi等人[4]提出了DARA(Distributed Actor Recovery Algorithm)算法，该算法通过综合距离、节点度和节点标号等因素来选择现有节点，移动被选节点到指定区域以恢复连通。Senel等人[5,6]将基于蜘蛛网结构的仿生研究应用到无线传感器网络连通恢复上，提出了1C-SpiderWeb算法，利用近似网状的拓扑结构对瘫痪区域实现了连通恢复，但是所需要的中继节点RN(Relay Node)数量较多，增加了恢复连通的成本，并且这种拓扑结构较为复杂，导致其容错性较差。Lee等人[7]提出了用最小斯坦纳树恢复无线传感器网络多个同时故障的算法，算法以斯坦纳树为初始拓扑结构，研究了RN的放置位置，并以RN的放置位置计算出最少的中继节点数量，通过移动中继节点来达到故障区域的连通恢复，但是该算法不能保证移动RN冗余以及恢复连通后传感器网络的健壮性。Senel等人[8]在2011年提出FeSTA(Federate network Segments via triangular steiner Tree Approximation)算法,将三角形斯坦纳树结构用于网络的断连恢复，利用三角形斯坦纳树结构的特点有效地降低了中继节点部署数量。

为了使连通恢复后的无线传感器网络高效且健壮，本文提出了基于斯坦纳树和泰森多边形的连通恢复算法CRAST(Connectivity Restoration Algorithm based on Steiner tree and Tyson Polygon)。本文采用改进泰森多边形部署可移动的备用节点。文献[9]描述了泰森多边形的性质以及泰森多边形的常规生成法，提出了相邻离散点是以泰森多边形边对称的。文献[10]提出了使用三角剖分算法构建泰森多边形，该算法生成泰森多边形的速度较快，并且提出了新的算法迅速分类出邻近节点，提高了生成泰森多边形的效率。

2 网络模型

2.1 问题描述

四边形斯坦纳树结构部署RN相比于三角形斯坦纳树结构和最小生成树结构[11]部署RN，可以以较少的RN实现无线传感器网络的连通恢复，故本文使用四边形斯坦纳树结构来部署RN使瘫痪区域实现连通恢复。由于四边形斯坦纳树的连通恢复方法过度依赖其中的关键节点KN(Key Node)，导致一方面这些KN相较其他节点而言需要消耗更多的能量，最终因能量消耗殆尽而停止工作，另一方面恶劣的外界环境极可能会毁坏这些KN，导致网络的大片区域再次陷入瘫痪状态。本文针对这个问题，提出了用泰森多边形的算法在恢复区域内部署KN的备用节点SN(Standby Node)，在KN损坏时能够通过移动SN及时地使传感器网络再次恢复到连通状态。

2.2 系统模型

将M个离散点随机部署在区域Ω中，表示区域Ω中的M个节点。一般情况下，能量耗尽和恶劣的外界条件会导致传感器某些节点失效，从而使网络在区域Ω中被拆分为多个节点群。我们把节点群内所有节点能够相互进行通信的节点群称为分区，将这些分区看作为点，每个分区用Segi表示，i∈[1,n]，故n为划分的分区数量，如图1所示，分区与分区之间无法进行通信。

Figure 1 Partitioned area Ω图1 分区后的区域Ω

2.3 算法基本理论

定义1(四边形斯坦纳点) 根据文献[12]对于任意1个四边形，其内部存在2个点，使得四边形的4个顶点通过这2个点连接的长度最小。

定义2(凸非退化型四边形) 若1个四边形中的4个内角均小于或等于120°，则这个四边形为凸非退化四边形。

定义3(斯坦纳点) 对于任意凸非退化型四边形ABCD，对其2条对角线的锐角夹角所对的2条边分别向锐角开口方向作等边三角形得到△ABE和△BCF,对△ABE和△BCF分别做外接圆；连接E、F得到线段EF，EF与2个外接圆相交的2个点即为ABCD的斯坦纳点。

定义4(Delaunay三角网) 由若干个三角形组成的网络，并且互为相邻的三角形的相邻边为2个三角形公共的边[13]，如图2a和图2b所示。

Figure 2 区域Ω内散点和基于散点的Delaunay网图2 Discrete points in region Ω, and Delaunay triangulation formed by discrete points

定义5(凸包插值算法) 该算法是基于多维空间中生成Delaunay三角网的算法，先后使用凸包生成、环切边界凸包三角剖分和内插法构建Delaunay三角形，具体步骤可参照文献[14]。

3 四边形斯坦纳树连通恢复算法

由于连通恢复问题为NP难问题，本文使用作为启发式算法的四边形斯坦纳树算法。若要将区域Ω内的所有分区用中继节点RN连接，四边形斯坦纳树连接算法是最节省中继节点的，算法步骤如下所示：

(1)对区域Ω内的所有分区以4个分区为1组的方式进行组合，枚举出全部非退化四边形。

(2)计算枚举出的全部非退化四边形的周长，并按照周长从小到大将这些非退化四边形存入数组NQ[]中。按照数组的顺序对所有非退化四边形进行判别，若非退化四边形的顶点被其他非退化四边形占用的个数小于或等于1，则对此非退化四边形按照定义3的方法标出此非退化四边形的斯坦纳点，将斯坦纳点与顶点连接起来即为斯坦纳边，再沿着斯坦纳边部署中继节点。每条去掉端点的斯坦纳边的中继节点RN个数用Numse表示，则：

(1)

其中,lengthse表示每条斯坦纳边的长度；R表示中继节点的通信半径。连通的非退化四边形被看作一个分区，继续抽象为点与其他分区组合为非退化四边形。

(3)在无法再用非退化四边形方式连通后，枚举出剩余分区的三角形组合，按照三角形斯坦纳树连通，无法构建三角形斯坦纳树的分区则与距离最近并且已与主体连通的分区沿直线连通，如图3所示，SegA～SegL为分区，K1～K6为关键节点KN。

Figure 3 Quadrilateral Steiner connectivity restoration图3 四边形斯坦纳连通恢复

4 基于泰森多边形的优化算法

在保证中继节点数量尽可能少的情况下，本文使用四边形斯坦纳树的连通恢复算法恢复了瘫痪区域，使所有分区实现了相互连通。为了保证恢复网络的健壮性，本文针对四边形斯坦纳点所在的关键节点KN，使用泰森多边形的拓扑结构部署备用节点SN，保证在这些关键节点损坏时能够及时移动备用中继节点替换。

4.1 泰森多边形部署节点

根据泰森多边形的性质可知，泰森多边形每个顶点是与另外2个以上的泰森多边形的共同顶点，并且泰森多边形的每个顶点到其对应的2个离散点距离相等，所以对于整个传感器网络而言，使用泰森多边形部署SN可以极大减少SN的部署数量，同时还能保证SN冗余。算法步骤如下所示：

(1)用KN构建Delaunay三角形。

(2)将KN节点编号储存入数组KN[]中，将三角形编号并储存入数组TRI[]中，记录每个三角形所对应的3个KN节点，即TRI[]→KN[]。

(3)根据TRI[]→KN[]，对与每个KN节点相邻的三角形标号，如图4所示，对于任意KN，假设此KN为K7，则找出与K7同为一个三角形顶点的另外一个顶点，假设此顶点为K8且此三角形为A，则能够找出三角形A的第3个顶点并假设此顶点为K9，以K7和K9为顶点，则能找到三角形B的第3个顶点并假设为K10，以K7和K10为顶点，则能找到三角形C的第3个顶点并假设为K11，以此类推，直至回到以K7和K8为顶点时结束此KN相邻三角形的排序[15,16]。按照排序将相邻三角形储存入数组AD[]中。

Figure 4 Delaunay triangles are sorted counterclockwise图4 Delaunay三角形逆时针排序

(4)构建数组TRI[]内每个三角形的外接圆圆心，将相邻三角形的外接圆圆心连接起来,如图5所示。

Figure 5 Constructing Tyson Polygon图5 构造泰森多边形

(5)将区域Ω中形成的所有泰森多边形标记并储存入数组TP[]中，并且记录每个泰森多边形所对应的顶点，将顶点储存入二维数组VER[][]中，并且将关键节点KN对应相应的泰森多边形和泰森多边形顶点，即KN[]→TP[]→VER[][]。

(6)根据数组VER[][]在所有泰森多边形的顶点部署SN，将信息储存入二维数组SN[][]中，则对应关系为KN[]→TP[]→SN[][]，当关键节点能量耗尽或者损坏时，移动此KN所对应的SN予以替换。

4.2 基于节点数量权重比较的移动节点选择

由于多个泰森多边形共用同一个顶点，故在一个顶点上部署的SN将负责多个KN的替换，所以如何选择SN去替换KN是保障网络流畅工作的重要任务。假设失效的KN为Ka，与其相邻的KN节点分别为Kb、Kc、Kd、Ke，与Ka对应的SN编号分别为Sa和Sb，如图6所示。算法初始化KN[]→SN[][]信息，分别计算SN节点Sa占KN节点Kb、Kc、Kd对应的SN数量的加权比重，SN节点Sb占KN节点Kd、Ke对应的SN数量的加权比重。选择SN过程可用数学公式描述为：

Figure 6 Deploying a standby node图6 部署备用节点

(2)

其中,SN[i][j]表示KN[i]的备用节点，i=1,2,3,…;j=1,2,3,…；PROPORTIONSN[i][j]表示SN[i][j]占其对应KN的所有备用节点的加权比重；KN[m]SN[i][j]表示与备用节点SN[i][j]对应的所有关键节点，m=1,2,3,…;NUMSN表示求KN所对应的SN个数的运算。由式(2)计算出最小加权比重的SN后，移动此备用节点替换失效的关键节点。最后在SN节点移动去替换KN节点后，更新KN[]→SN[][]信息。

算法1基于泰森多边形的优化算法CRAST伪代码

输入：分区集合Seg，中继节点RN通信半径R。

输出：需要部署的RN和SN总个数及位置信息。

1. dealQuadrilateral;

2. dealTriangle;

3.IFthere are Segs that are not connectedTHEN

4. Find the shortestedge(u,v),uinSeg1andvinSeg2;

6.ENDIF

7. Define variableNUMBERSTand put the number of relay nodes intoNUMBERST;

8. Constructing Delaunay triangle with KN;

9. Store Delaunay triangle in the arrayTRI[];

10. StoreKNin the arrayKN[];

11.FORarrayKN[]DO

12.KN[] correspond toTRI[];

13. Sort adjacent triangles and store in arrayAD[]

14.FORarrayAD[]DO

15. Construct the center of the circumscribed circle;

16.ENDFOR

17.ENDFOR

18. Connect all centers of the circumscribed circles;

19. Store the vertices of Tyson polygon into arrayVER[][];

20.FORarrayVER[][]DO

21. Deploy SN on vertices and store SN in the arraySN[][];

22.KN[] correspond toSN[][];

23.ENDFOR

24. Define variableNUMBERTPand put the number of standby nodes intoNUMBERTP;

25. Define variableNUMBERRNandNUMBERRN=NUMBERST+NUMBERTP;

26.IFKN[i] is damagedTHEN

26. ReadKN[i]→SN[i][j];

28.FORminjDO

29. Calculate the proportion ofSN[i][m] to the sum of SN numbers of all KN corresponding toSN[i][m];

30.ENDFOR

31. Compare the minimum proportion;

32. MoveSN[i][j] with minimum proportion;

33.ENDIF

34.Output variableNUMBERRN

5 仿真分析

本节采用Matlab进行仿真实验，在中继节点部署数量和健壮性2个方面对CRAST算法与1C-SpiderWeb算法和FeSTA算法进行比较。由于1C-SpiderWeb算法和FeSTA算法没有备用节点替换损坏节点的功能，1C-SpiderWeb算法和FeSTA算法在仿真前期容易因为某个中继节点损坏而被再次断连，不能完整地模拟在恶劣环境中的工作表现，故实验中为1C-SpiderWeb算法和FeSTA算法配备可移动节点，以保证1C-SpiderWeb算法和FeSTA算法能够在考虑恶劣外部环境影响的仿真中完整运行。实验将1C-SpiderWeb算法和FeSTA算法的中继节点以每3个为1组，余下节点成1组进行分组，为每组配备1个可移动节点。本实验将传感器网络区域Ω定义为1500 m×1500 m的正方形区域，通信半径R∈[40,120]，每20 m取值一次，Segi个数取8，9，10，实验在多种随机组合的情况下取平均值，以保证实验结果的普遍性。

5.1 中继节点数量

在处理无线传感器网络连通恢复的算法中，往往中继节点数量是非常重要的一项指标，在保证瘫痪网络恢复连通的同时减少中继节点数量是无数相关学者的主要研究方向。实验在3个分区数下，改变中继节点通信半径来测试CRAST算法、1C-SpiderWeb算法和FeSTA算法的高效性。

通过如图7所示的对8个分区、9个分区和10个分区下中继节点数量与通信半径的关系对比，可以发现在同一分区下CRAST算法、1C-SpiderWeb算法和FeSTA算法的中继节点数量随着通信半径的增加而减少，由于1C-SpiderWeb算法的特殊拓扑结构，导致1C-SpiderWeb算法与CRAST算法和FeSTA算法相比在分区数越多的情况下，其所需要部署的中继节点越多。对比图7可知，在中继节点通信半径R较小时，由于CRAST算法中四边形斯坦纳树结构和泰森多边形结构都能有效降低中继节点数量，FeSTA算法所需要的中继节点数量多于CRAST算法的，当中继节点通信半径R较大时，由于CRAST算法的备用节点更多，CRAST算法所需要的中继节点数量略多于FeSTA算法的。通过对3个算法进行仿真实验，发现CRAST算法比1C-SpiderWeb算法具有更强的高效性，而在中继节点通信半径R较小时,CRAST算法比FeSTA算法更高效，在中继节点通信半径R较大时FeSTA算法比CRAST算法高效。

Figure 7 Relationship between the number of relay nodes and the communication radius in different partitions图7 不同分区数下中继节点个数与通信半径的关系

5.2 健壮性

在对瘫痪网络进行连通恢复后，保证恢复后网络的健壮性同样是衡量连通恢复算法优异性的重要指标。传统无线传感器网络连通恢复算法由于其关键节点能耗远大于其他中继节点，导致关键节点工作寿命远小于其他中继节点，继而导致恢复后的工作寿命短。本实验采用在8个分区、9个分区和10个分区的情况下观察失效中继节点与工作寿命之间的关系来验证CRAST算法、1C-SpiderWeb算法和FeSTA算法在较高故障率下的健壮性，中继节点通信半径为80 m。实验结果如图8所示。

Figure 8 Working life of three algorithms in different partitions图8 不同分区下3种算法的工作寿命

通过直方图对比可知，由于CRAST算法针对关键节点优化，CRAST算法的网络工作寿命比1C-SpiderWeb算法和FeSTA算法的网络工作寿命更长，而1C-SpiderWeb算法和FeSTA算法由于关键中继节点消耗过多能量，导致网络的工作寿命无法达到最大化。

6 结束语

本文提出的CRAST算法旨在解决无线传感器网络由于部分中继节点失效导致网络被分割成多个分区的问题，通过构建四边形斯坦纳树和泰森多边形实现高效且健壮的连通恢复。通过多个实验与1C-SpiderWeb算法和FeSTA算法进行对比，验证了CRAST算法相比1C-SpiderWeb算法和FeSTA算法具有更出色的高效性和健壮性。由于本文算法是基于二维空间的算法，无法解决自然环境中非平面地形的部署，所以接下来的工作将针对三维空间的网络连通恢复进行研究，以保证在三维空间中网络出现瘫痪后能够及时恢复。