一种通过加入中继节点以修复大面积网络损坏的能量均衡算法

黄健文，倪卫明

0 引言

近年来，无线传感网在学术与工程界均成为了研究热点之一[1]。在太空探索、边境防护、战场侦察、环境监控等等领域有广泛的应用。无线传感网包含大量SN（Sensor Node：传感节点），能够在目标区域中对事件及其数据进行传感与处理，并通过无线ad hoc网络进行传输。但是，传感节点具有有限的能量和传输范围。且会因为极端的环境而产生大面积损坏，网络被分割成若干不相连的分区，如图1所示：

图1 一种损坏了的WSN，分割成多个分区

多边形圈外的节点即损坏节点，其把网络分成了 3个分区。分区内实心圆点为分区的边界点，小方框内圆点是边界点中剩余能量最大的。在后文算法中有所应用。

这种情况下，大量文献致力于研究如何修复网络连通性。比如，可以通过重置其中某些节点的位置进行修复[2]；也可以通过加入RN(Relay Node：中继节点)，辅助数据的传输与能量的优化[3]。一些启发式算法致力于研究如何通过加入尽可能少的节点来进行修复。比如 CIST[4]（Connected Inter-Segment Topology：连通分区内拓扑）算法以 Steiner树作为工具，采用的方法是：在每个分区边界随机选取一个rep（Representitive Node：代表节点），形成最小生成树。以3个相邻分区为单位，加入最少数量的RN，通过迭代修复连通性。其主要缺点是：网络损坏后，由若干RN在单条链路上连通两个分区，这些RN大多是割点，再次损坏概率很大。因此，蜘蛛网算法[5]（Spider-web Algorithm）对其进行改进，主要方法是：在每个分区随机选择一个节点作为代表，找到这些代表形成的凸包的中心点，各rep通过加入RN向中心节点靠拢，同时加入RN与左右邻居rep连通。网络的鲁棒性有显著提升，代价是增加了RN数量。

1 问题描述与基本模型

1.1 问题描述

需解决的问题描述如下：“在目标区域中给定n个不相连的传感器分区，确定最少数量的RN以修复分区之间的连通性，并且考虑节点的剩余能量均衡性。”这个问题的最优解决方案为加入Steiner点，形成一棵最小Steiner树。这里的Steiner点可以理解为RN。通常情况下，RN的主要功能是数据聚合和转发。RN价格高，能量大，传输范围大。但在本文中，假设所有节点的传输范围相同，均为“R”。该问题可定义为SMT-MSP[6]（Steiner Minimum Tree with Minimum number of Steiner Points and bounded edge length：边长受限、Steiner点数最小化的最小Steiner树）问题，具体如下：

定义 1：SMT-MSP：给定节点组 V，传输范围 R，SMT-MSP就是在V中形成一棵树T，且加入的Steiner点数最少，T中的边长均不超过R。

SMT-MSP问题是NP-hard问题。大量文献致力于研究该问题，但大多较为关注如何减少RN数、提高覆盖率、优化网络拓扑等等，往往忽略了各节点能量均衡问题。

SMT-MSP的经典算法之一，以3-approximate为例，描述如下：找出所有可能性的边，按边长从小到大排列。若存在一个Steiner点可同时连接3个节点，则加上。再将剩余的边上添加Steiner点完成连通。

1.2 系统模型

初始时，网络由一组剩余能量不同、不可移动的SN组成，随机分布在目标区域中。负责传感周围信息，处理数据并在传感范围内传输。SN和RN 具有相同的传感范围R。对每个节点Ni，其剩余能量为E(Ni)。由于不可抗力造成大面积节点损坏，网络被分离成n个连通分区。在每个分区选出一个rep后，形成mst[8]（Minimum Spanning Tree：最小生成树）。若两个代表节点repi和repj之间在mst存在边，则称repi和repj为邻居节点。同理，3个代表节点之间在mst中存在且只存在两条边，该3点也看作邻居节点。本文不考虑其他邻居情况。为连通若干rep所需加入的RN数量定义分为两种，具体如下。这里，repi表示代表节点的编号，表示两代表节点之间的距离。

a.连通两个rep：

当需要连通3个rep时，会有两种选择。Wmst的情况如图2所示：

图2 通过mst连通分区

在两条较短的链路添加Steiner点。Wf如图3所示：

图3 通过费马点连通分区

先寻找3个节点的费马点（Fermat Point）[9]。然后在连向费马点的3条链路上添加Steiner点。

采取哪一种方式取决于所需Steiner点数的多少比较，即Gain值正负。Gain值定义为

本文也将节点的剩余能量纳入考虑参数，采用经典的能量定义[10]如下。传感能耗：Ps=α1per bit；发送能耗：Pt(r)=γ1+β*rαper bit；接收能耗：Pr=γ2per bit。式中，α1，γ1和γ2为常数，由底层技术决定。α是路径损耗系数，取决于环境。β描述单位距离上传输单位bit信息所需的能量。

2 本文算法

下面介绍本文的算法流程。其伪代码如图4所示：

图4 所提出算法的伪代码

首先，网络中的每个节点通过心跳信号维护一张表格，记录邻居节点的编号与位置。若节点失去邻居节点信号，则将自己标记为边界节点。各边界节点运行洪泛算法将其位置与剩余能量信息告知各节点。蜘蛛网算法采用随机抽取的方法选出每个分区的rep，CIST算法在分区边界上随机选择。考虑到降低RN数量、均衡节点能量，所有节点默认将剩余能量最多的边界节点看作该分区的rep。

步骤一：算法初始化

某个特殊的可移动节点巡逻得知各 rep位置与能量，由一能量不限的中心节点承担计算任务，将rep形成mst。步骤二：迭代连通各分区

如图5所示：

图5 算法运行步骤说明

找出所有由3个节点组成的邻居节点，并计算Gain。将 Gain按绝对值大小排列。选择绝对值最大的一组添加Steiner点，Gain值为正则选择费马点方法；为负则选择mst方法。如图5(a)所示，第一轮迭代中选择用费马点方法连通S3,S4,S5。

由于能量的消耗与发送能耗直接相关且P rt∝ 。为均衡能耗，应使剩余能耗少的节点更靠近RN。如图2，因为E (repi)＜ E(repj)，所以Steiner点从repj开始相隔R摆放。步骤三：更新节点状态

首先，删掉冗余邻居节点。比如 S3无需再考虑与 S4连通，所以在下一轮迭代中无需考虑S3，S4，S6形成的邻居节点。

为了进一步减少 RN数，充分利用新加入的 RN。若SN连接了RN，则其在之后的迭代中考虑由距离最近的RN代替的情况，计算新Gain。若可以减少需添加RN数，则采用替代方案。如图5(b)，S3由R1代替，在后续迭代中完成与S1、S2连通。

需要说明的是，若发现网络已不存在3个节点组成的邻居，再考虑两节点邻居，并连通。如图5(c)中的S7和S8。

3 相关证明

定理1：本文算法的时间复杂度为O(n3)。

证明：假设网络分成 n个分区，首先采用 DD[11](Directed Diffusion：定向扩散路由协议)将边界节点信息洪泛发送，时间复杂度为O(n)。由 mst性质可知，n个点形成的 mst有 e=n-1条边。形成 mst的时间复杂度为O(elgn)=O((n-1)lgn)。在计算每组由 3个节点组成的邻居所具有的Gain时，最坏情况是节点恰巧组成了星型网络，存在=组。计算费马点及RN位置可在固定时间内完成。节点摆放与状态更新均可在固定时间内完成。因此，该算法的总时间复杂度为 O()，即O(n3)。

定理2：本文算法可保证网络的连通性。

证明：采用反证法。假设算法的运行未完成网络的连通，则至少存在一个分区，与其他分区分隔。在网络尚未连通的情况下，就会运行伪代码Procedure: Algorithm第七行的while循环。根据mst的定义，至少存在一个邻居分区与该分区相连。根据while循环的步骤，可完成连通。

4 仿真结果

对提出的算法进行仿真，并将其性能与蜘蛛网算法、SMT-MSP算法进行比较。仿真环境为1000m*1200m平面。节点随机产生。通过改变网络规模，节点传输范围来仿真所需RN数量的变化规律。所得结果是通过将算法运行50次取平均值得到的，且样本值保持在均值15%区间范围内。

4.1 不同网络规模下需加入RN数量仿真

如图6所示：

图6 不同网络规模下所需RN数曲线

比较了 3种算法在不同网络规模下所需的 RN数量（假设传输距离R=100m）。

Spider-web算法所需RN数随着分区数增加而大幅增加，这是因为分区数增多，就意味着节点离凸包中心点的距离增加，形成蜘蛛网所需的互联节点增多。这需要大量的RN来完成。SMT-MSP算法与本文算法所需RN数也会随分区数增加，这是因为分区增加意味着mst边数增加，连通任务加大。

特定分区数下，Spider-web算法需要的RN数最大。这是因为该算法致力于优化网络拓扑，并提高覆盖率，减少割点。这是以增加 RN数为代价的。相对而言，经典的SMT-MSP算法仅以减少RN数为目标，在RN数上性能较优。本文提出的算法以减少RN数和均衡节点剩余能量为目标。通过mst方法、费马点等方法减少RN数量。为了均衡节点能量，剩余能量较多的节点会承担更多的连通过任务。RN替代的方法进一步减少RN数量。所以，本文的该项性能上有了进一步提升。

如图7所示：

图7 不同传输范围下所需RN数曲线

比较了不同传输范围情况下的所需RN数（假设分区数=9）。也得到了相似的结论。传输范围增加有利于分区互联，所以所需RN数随之减少。

4.2 能量仿真

本文仿真了网络中剩余 SN数随时间的变化情况。假设α1=60 *10-9J/bit，γ1=45 *10-9J/bit ，γ2=135 *10-9J/bit。设为α=2。当α=2时， β=10 *10-12J/ bit/m2。假设传感节点每隔1s进行一次传感，任何节点的传输数据量取决于拓扑结构，且单位数据量为2bit。仿真考虑两种路由：a.SPR(Shortest Path Routing：最短路径路由)，以距离为边的权值。b.EBR(Energy Balancing Routing：最优能耗路由)，综合考虑链路通信能耗与节点剩余能耗[12]。网络规模设置如下：存在10个SN，传输范围为50。新节点的初始能量为0.1J，但算法开始运行时，假设网络已工作一段时间，SN剩余能量各不相同，RN刚被加入网络。在每个时间点所得的数值是通过取 50次平均值所得，且样本值保持在均值15%区间范围内。

如图8所示：

图8 存活SN随时间变化曲线

当第一个RN能量耗尽时，网络停止运转。首先，采用不同的路由方式对网络生命有一定的影响。EBR方式路由将节点剩余能量以及收发能耗作为权值，能耗较大的节点、能耗较小的链路会承担更多的传输任务。而SPR方式路由以距离为权值。所以无论哪种算法，EBR方式路由均在网络生命上优于 SPR方式路由。其次，本文提出的算法在网络能耗上优于SMT-MSP 3-App算法。这是因为本文在rep选择上考虑了能耗，且在之后的拓扑上采用RN代替SN进行传输等均衡能耗的方法。

5 结束语

本文研究了无线传感网出现大面积损坏节点时的连通性修复问题，在 CIST, Spider-web算法的基础上，以减少RN数，均衡各节点剩余能量为目标提出了新的算法。在算法中，采用了最小生成树，Steiner点，费马点等经典方法减少RN数量。且剩余能量较多的边界节点、RN节点承担更多的传输任务，以均衡网络节点的剩余能量。仿真结果显示该算法可以以加入较少RN节点且维护网络能量均衡。

[1]Chong.C.Y, Kumar.S.P.Sensor networks: Evolution,opportunities, and challenges[C]//Proc.of IEEE.[s.n.].2003:1247-1256.

[2]Younis.M, Lee.S, Gupota.S,et al.A Localized Self-healing Algorithm for Networks of Moveable Sensor Nodes[C]// Proc.Conf.GLOBECOM.New Orleans:[s.n.].2008:1-5.

[3]Lee.S, Younis.M.Optimized Relay Placement to Federate Segments in Wireless Sensor Networks[J].IEEE On Selected Areas in Commun., 2011,28(5):742-752.

[4]Senel.F,Younis.M.Optimized Connectivity Restoration in a Partitioned Wireless Sensor Network[C]// Proc.Conf.GLOBECOM.Houston: [s.n.].2011:1-5.

[5]Senel.F, Younis.M, Akkaya.K.A Robust Relay Node Placement Heuristic for Structurally Damaged Wireless Sensor Networks[C]// Proc.Conf.Local Computer Networks.Switzerland: [s.n.].2009:20-23.

[6]Chen.D.H, Du.D.Z, Hu.X.D,et al.Approximations for Steiner Trees with Minimum Number of Steiner Points[J].Journal of Global Optimization., 2000,18:17-33.

[7]Cheng.X.Z, Du.D.Z, Wang.L.S.[C]Relay Sensor Placement in Wireless Sensor Networks

[8]Ruzika.S,Hamacher.H.W.A Survey on Multiple Objective Minimum Spanning Tree Problems[J].Algorithmics of Large and Complex Networks., 2009, 5515:104-116.

[9]Shay.G, Ran.T., The Fermat-Steiner Problem[J].The American Mathematical Monthly., 2002,109(5): 443-451.

[10]Sun.D, Shayman.M.Prolonging Network Lifetime via Partially Controlled Node Deployment and Adaptive Data Propagation in WSN[C]//Proc.Conf.Information Sciences and Systems.Baltimore: [s.n.].2007:226-231.

[11]张锦,林亚平,李超等.传感器网络中基于角度域的洪泛路由算法[J].计算机工程与科学, 2005,27(9):59-71.

[12]Bechkit.M, Koudil.M, Challal.Y, et al.A New Weighted Shortest Path Tree for Convergecast Traffic Routing in WSN[C]//Proc.Conf.Computers and Communications.Cappadocia: [s.n.].2012:187-192.