一种基于代理和环形路由的传感器网络覆盖空洞修复策略

任炬，刘安丰，陈志刚

(中南大学 信息科学与工程学院，湖南 长沙，410083)

摘要：提出一种基于代理和环形路由的传感器网络覆盖空洞修复策略。此策略的核心在于：每一个休眠节点选取距离自己最近的工作节点作为代理节点，以代理节点与网络几何中心的连线方向扩散其位置信息，形成纵穿网络的存储代理信息的扩散路径；当网络中工作节点濒临死亡时，从代理节点开始以网络几何中心为圆心进行绕环路由，定位替换节点；经过仔细规划对信息路由的剪枝规则，降低节点的存储信息量。通过理论与仿真实验对网络能耗、节点移动距离和节点存储容量等多个方面对修复算法进行分析、评价与实验。研究结果表明：本文提出的策略有利于降低网络能耗，提高节点存储容量。

关键词：传感器网络；移动节点；覆盖修复；代理；环形路由

中图分类号：TP393          文献标志码：A         文章编号：1672-7207(2014)08-2629-11

An efficient coverage maintenance scheme based on proxy information sharing and circular routing in WSNs

REN Ju, LIU Anfeng, CHEN Zhigang

(School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: A sensor relocation protocol based on proxy and circular routing (SRPCR) was proposed for mobile sensor networks. The main idea of SRPCR can be expressed as follows. Each redundant sensor spontaneously takes the nearest neighboring active node as proxy at first. Then, proxy nodes record the location of their delegated redundant node and diffuse it over the network. Once an active node is on the verge of failure, it will launch a circular routing to find a nearby proxy. With the diffusion of the well-designed blocking rules for the proxy information, SRPCR can guarantee the storage capacity of each node is constant. Finally, theoretical reasoning and simulations are conducted to analyze and evaluate the improvement of energy consumption, distance of the movements and nodal storage. Performances of this protocol show that energy consumption decreases and nodal storage are improved remarkably.

Key words: wireless sensor network; mobile sensor; coverage maintenance; proxy; circular routing

网络覆盖是无线传感器网络服务质量的一项重要指标^[1]，反映了传感器网络对整体区域的监控程度。导致网络覆盖空洞产生的原因很多，本文依据覆盖空洞发生在网络的阶段不同而将其分为以下2种：一是在部署阶段，由于网络节点部署的随机性或监测区域的地域特征导致网络在部署时所形成的覆盖空洞^[2]；二是在网络稳定运行阶段，由于网络中节点能耗不均或自然环境对节点产生致命影响等原因，常常会导致部分节点过早死亡，从而产生的局部覆盖空洞^[3]。对于部署空洞的覆盖修复问题，目前已经有较丰富的研究成果^[4-9]。这些研究的核心是在节点随机部署后，通过Voronoi划分等方法进行空洞定位，再使用一种有效的节点移动策略填补部署空洞，使得整个网络的覆盖面积最大化。但是，在网络运行期间，节点失效等问题造成的覆盖空洞现象由于其事先不可预测的动态性，对网络产生了长期影响，因而其研究变得尤其重要。本文将主要研究网络运行期的覆盖空洞修补问题。一种有效的解决方案是部署一定量的处于休眠状态的冗余移动节点，在活动节点失效后，将冗余节点唤醒用来填补死亡节点产生的覆盖空洞。但由于移动节点本身也受到能量约束，且移动过程将消耗大量能量，因此，如何找出距离死亡节点最近的冗余移动节点，并填补死亡节点造成的覆盖空洞，成为关键性的问题。针对网络运行期间的覆盖空洞修复问题，本文作者提出一种基于代理信息共享和环形路由的节点失效覆盖空洞修复协议。在传统的一旦部署节点就不能再移动的静态无线传感器网络(WSNs)中，由于网络节点部署的随机性，往往无法有效地避免覆盖空洞的产生。为保证网络的覆盖要求和运行寿命，通常使用大量的冗余节点部署以形成对网络的多重覆盖，以此来避免因节点死亡引起的覆盖空洞，保证网络覆盖率。但是，过多的冗余节点无疑增加了网络成本，还会引起通信干扰和冲突，反而降低了网络性能，造成网络资源和节点能量的浪费。凡高娟等^[2]提出一种非均匀分布下的WSN节点调度机制，利用节点间的距离信息对覆盖冗余进行判别，以调整节点的工作状态。何欣等^[3]采用分轮机制，提出一个基于延迟唤醒的活跃节点集选择算法。以上方法的核心思想均是通过设置一种合理的节点调度机制，获得一个能够实现全网覆盖的最小活跃节点集，以达到节省能量、延长网络寿命的目的。但静态网络中，冗余部署的成本依旧无法得到有效的控制。

随着传感器节点移动技术的发展，从而涌现了大量采用移动节点来保护网络覆盖的研究，成为近年来的研究热点。依据对覆盖空洞的分类，覆盖修复方案的研究成果可分为2类。

(1) 部署覆盖空洞修复研究。Wang等^[10]提出一种基于代理的部署空洞修复算法(简称WCP)，用于解决由静态节点和动态节点所组成的混合网络中的部署覆盖空洞问题。在WCP协议中，静态节点通过建立Voronoi划分来定位网络中的部署空洞；然后，通知最近的移动节点来修复他们所在的Voronoi多边形中的覆盖空洞。当移动节点修复1个部署空洞时，将产生新的空洞，算法将一直持续直至所有空洞均被修复。Li等^[4]提出一种基于虚拟力的节点部署方法。在随机播撒之后，通过虚拟力算法(VFA)作为节点部署方法来提高覆盖率。

王良民等^[5]提出一种三角形贴片式的逐步增加移动节点方法来进行网络部署空洞修复。该方法利用覆盖洞边缘节点提供的辅助信息，指导移动节点移动到“最佳”位置，并从几何理论上分析了最佳位置的存在条件，证明在相关位置部署移动节点可保证最低覆盖率大于90%。赵小敏等^[6]提出基于Delaunay三角化与网格的节点随机部署算法。该算法将传感器节点进行Delaunay三角化分组，通过TPM算法计算出各个Delaunay三角形的目标点TP，并提出边界补强机制及钝角三角形TP点优化策略，有效提高了覆盖范围。

(2) 节点失效引起的覆盖空洞修复研究。Wang等^[8]提出一种基于网格的空洞修复协议。它将网络划分成一个个二维网格；然后，在每一个网格选出1个cell head。Cell head在获取本格的冗余信息后，将其扩散至网络中同一列的其他网格中。当出现节点失效时，其失效节点所在网格的Cell head便启动最佳冗余节点查找，将沿着网络中的一行网格依次查询，定位最佳冗余节点。这种方案能有效地获取全局范围内的最佳替换信息，但其局限性在于对于不规则的网络无法合理划分网格，且冗余节点信息在网络中扩散能耗较大，单个节点存储容量要求高，不适用于大型网络。Li等^[9]在此基础上提出一种基于代理信息网格的空洞修复协议，每一个冗余节点选取离自身最近的活跃节点为代理节点。代理节点以其冗余节点的位置信息作为代理信息在网络中进行扩散，最终在网络中形成包含代理信息的Information mesh。当节点失效后，将发起查询路由沿包围自己的Information mesh找出局部的最佳代理信息。此协议虽不能保证每一次均能找出全局的最优替换信息，但它在节点上实现了路由裁剪，保证了节点的常量存储。然而，协议并未给出代理信息维护方案，在执行1次节点替换后，需重新进行Information mesh的建造工作，造成了不必要的能量消耗。包旭等^[11]提出一种基于分簇网络的无线传感器网络运行时空洞修复算法。该算法为每个节点设置1个能量阈值，当节点能量低于该阈值时立即向簇首发送失效信息，簇首收到信息后通过计算失效节点与所有邻居节点的交点角来判断是否有邻居节点为非边界节点, 最后，在失效节点的感知半径内选择邻居节点个数最多的冗余节点激活执行替换过程。Li等^[12]提出一组空洞修复协议，包括R3S2, G-R3S2, C-R3S2 and C-G-R3S2。在R3S2中，移动节点随机移动；G-R3S2协议中移动节点基于一个虚拟网格并往近期访问最少的网格点移动。C-R3S2和C-G-R3S2协议是将分簇和虚拟力技术引入后对前2种协议的一个变种。但这也并未对网络寿命，节点存储容量和协议维护成本进行综合的考虑。

与上述研究相比，本文作者提出一种较好的简单易行的节点失效覆盖修复方案，失效节点通过2次绕环路由后定位代理节点。网络节点的存储容量将保持常量级别，每一次节点替换后的代理信息都只需要局部的重建操作，从而可将信息维护代价降到最小，保证算法具有良好的整体性能。

1  系统模型和问题描述

1.1  网络结构模型

(1) 假设在网络的部署阶段，可通过一系列部署算法^[2-7]在目标区域放置一定量的工作节点，使其满足初始的覆盖条件，之后再随机投放一定量的冗余休眠节点。传感器节点均装备了可移动装置与GPS定位设备，节点通过低功耗的通信协议获得邻居节点的相关信息，能根据需要移动至网络中的指定位置。依据传感器节点的工作状态的不同，将其分为工作节点和休眠节点。工作节点自部署后保持工作状态直至能量耗尽，休眠节点在执行替换工作之前维持休眠状态，以节约能量来保证网络的持续连通性。

(2) 监测区域可为任意形状的二维平面区域。设网络几何中心坐标能通过数学方法测量^[5]，网络中所有传感器节点均已知网络的中心坐标。在网络开始运行前，节点采用路数扩散算法^[13]以确定其距离网络中心的跳数，确定其所在环数。

(3) 网络中节点的能耗不存在规律性，节点可能在任意时刻濒临失效。每一个工作节点预先设定1个较小的阈值能量E_d，当节点剩余能量小于E_d时，节点启动覆盖修复工作。设传感器网络为理想的无线通信信道，即不考虑数据包冲突和传输错误等^[5-7]，便于集中讨论覆盖修复问题的细节。

1.2  能量消耗模型

采用典型能量消耗模型^[13-14]，发送数据的能量消耗见式(1)，接收数据的能量消耗见式(2)。

         (1)

                  (2)

式中：E_elec表示发射电路损耗的能量，若传输距离小于阈值d₀，则功率放大损耗采用自由空间模型，若传输距离大于等于阈值d₀，则采用多路径衰减模型；ε_fs和ε_amp分别为这2种模型中功率放大所需的能量。节点接收l bit的数据消耗的能量如式(2)所示。在本文中，以上参数的具体设置取自文献[13]，如表1所示。

表2中所示为本文所使用的相关符号表示的意义。

表1  网络参数

Table 1  Network parameter

表2  符号含义表

Table 2  Symbolic meaning

1.3  问题描述

本文研究的问题可归结为使网络下面3个方面的优化：

(1) 协议所需的能量消耗最小化，也就是网络寿命最大化。能量消耗最小是所有覆盖空洞修复的研究的中心目标。覆盖空洞修复策略的能量消耗主要由4部分组成：信息扩散的能量消耗，查找的能量消耗，移动的能量消耗以及信息重建的能量消耗。设这4部分能量消耗分别表示为e¹，e²，e³的e⁴。那么使得能量消耗最小，网络寿命T最大化可以表达为

         (3)

(2) 失效节点找到最近代理节点的概率。设失效节点s_i找到最近代理节点的概率为P(s_i)。因此，协议优化的目标是使失效节点找到最近代理节点的概率最 大化：

           (4)

其中：m为冗余节点个数。

(3) 协议对节点的存储需求较小。传感器节点的存储容量一般来说较小，往往在千个字节的数据级范围内^[14]。因而，协议优化的第3个目标是使得节点在覆盖空洞修复过程中所需的存储容量最小化，即

    (5)

其中：n_i·γ为节点n_i需要存储覆盖空洞修复协议的存储容量；τ为允许的最大存储上限。

综上所述，可以得到本文的优化目标：

    (6)

2  SRPCR协议

本节将详细介绍本文所提出的基于代理信息共享和绕环路由的覆盖空洞修复协议SRPCR。根据上文对覆盖修复问题的描述，一种高效的修复协议设计应当遵循以下几个原则：(1) 尽可能找出最佳替换节点并制定最优的修复路径来修复失效节点形成的覆盖空洞；(2) 降低传感器节点存储容量，以此降低对传感器硬件的要求；(3) 降低代理信息的维护成本，保证最大化的生命周期。

2.1  协议描述

从协议的工作时段来看，SRPCR可分为以下4个步骤：(1)代理信息扩散，(2)替换节点查找，(3)节点移动和(4)代理信息维护。图1所示为SRPCR协议的工作示意图。图中虚线边框节点为冗余休眠节点，对应的4个阴影节点为代理节点，图中2个白色节点代表濒临失效需进行替换操作的节点。检测区域的几何中心位置以三角形标识，网络中各节点根据其距离几何中心的跳数划分成不同的层次，图中以黑色虚线圆标识。

图1中Proxy_a, Proxy_b, Proxy_c和Proxy_d这4个节点被选中作为代理节点后，将沿网络中心连线方向双向扩散代理信息。当网络中D1和D2节点失效后，将发起绕环路由，寻找最优的代理信息，定位冗余节点进行替换工作。图中点线和虚线箭头路径分别表示网络中唤醒消息的传送路径和节点的移动路径。在节点成功移动修复D1导致的覆盖空洞后，其路由交汇点P将启动代理信息重建，清除代理路径Proxy_a的代理信息。

图1  SRPCR协议的工作示意图

Fig. 1  Working scheme of SRPCR protocol

2.2  SRPCR协议算法详述

2.2.1  代理信息扩散

代理信息扩散只在网络的初始化阶段进行。为防止网络中代理信息扩散产生冲突，每一个冗余节点i将间隔一段随机时间α后启动代理信息扩散工作，且与其代理节点保持一对一关系。当冗余节点i开始信息扩散后，将选择其邻居节点中距离自己最近的非代理工作节点P_i为自身代理节点，并将自身的相关状态信息传递给P_i，之后节点便进入睡眠状态以节约能量。代理节点P_i将以自身编号，坐标等信息创建代理信息数据包，分别选择自身通信范围内面向网络中心方向和背离网络中心方向上最远的工作节点作为下一跳节点，进行双向扩散。在SRPCR协议中，代理信息数据包(PM)格式如图2所示。

图2  PM格式

Fig. 2  Format of PM

任意工作节点收到代理信息PM_i后，将计算其与休眠节点的距离(其中，代表自身与上一跳节点的距离)，然后执行剪枝算法存储和扩散最优的代理信息。剪枝规则如下：若当前节点未收到过代理信息，则令，，，然后更新PM_i使，并向前扩散M_i。若节点已存储代理信息，则比较和。若，则令，，，更新PM_i并向前扩散；若，则丢弃M_i，此时M_i在此方向上的代理信息扩散终止。

在面向网络中心方向，代理信息扩散至距离网络中心最近的节点停止，在背离网络中心方向，代理信息扩散至邻居节点中再无距离网络中心更远的节点时停止。通过代理扩散工作后，每一个代理扩散路径上的节点均保存了最佳代理节点(BP)的相关信息。

2.2.2  替换节点查找

在代理信息扩散完成后，网络将进入稳定运行状态，直至网络中出现节点剩余能量低于阈值能量E_s时，开始启动替换节点查找工作。失效节点启动绕环路由后，将贯穿网络寻找最优的替换节点。系统将绕环路由所经过的距离与节点中保存的最佳代理距离之和(称为曲线修复距离)作为选取最佳替换节点的标准。而由于在1个环中，2个节点的绕行距离会因绕行方向而产生差别，因此，在进行完一次绕环后，还需逆向再次绕环，统计反向绕行的最佳替换节点，比较正反2次绕环的统计的距离替换节点的距离，选择小的节点作为最佳代理节点。算法具体步骤如下。

首先，失效节点i将与其邻居节点进行广播通信，获取邻居节点中可用代理信息。对于自己和任意存储了可用代理信息的邻居节点j，先计算出2节点间的距离D_ij，然后选择D_ij+最小的节点作为自己的最佳邻居节点。然后，计算出其与网络中心所在的直线，从其一跳的邻居节点中，选择在此直线上方离自身最近的同层节点作为下一跳节点，若下一跳节点无法找到，则说明路由碰到网络边界，节点启用右手规则路由进行绕边界，选取下一跳节点。最后节点将创建查询消息(LM)，发送给下一跳节点。查询消息格式见图3。

图3  查询消息格式

Fig. 3  Format of query massege

图3中，bp_id代表最佳代理节点编号，offer_id代表环形路由上的最佳替换信息的提供者，dis_to_nen表示当前节点与失效节点的距离，best_dis_to_proxy代表与最佳替换节点的距离，nen_id代表失效节点编号，标识这次查询是由哪个失效节点发起的。

当任意节点k收到节点p发过来的查询消息后，同样与其邻居节点进行广播通信，找出自己和邻居节点中的最佳邻居节点j。然后，节点k比较D_kj++ D_kp+ dis_to_nen与best_dis_to_proxy，若前者较小，则更新整个查询消息包，转发至下一跳节点，否则只更新dis_to_nen字段，转发至下一跳节点。下一跳节点的选取过程与失效节点查询过程类似。直至节点k在可选的下一跳节点中找到失效节点i时，将查询消息包转发给i，逆时钟绕环路由结束。

在逆时钟绕环路由结束后，失效节点i统计到逆时钟方向的最佳替换节点及相关信息。此后，节点i将顺时钟进行第二轮绕环路由。由于在第一轮绕环过程中，每一个节点都记录了自己的最佳邻居节点信息，因此，在这一次绕环过程中，每一个节点都将反向绕行，将数据包传递给之前的上一跳节点，而且每一个节点都无需与邻居节点通信，只是比较最佳代理信息，更新查询消息传递回节点i。最终节点i通过比较2次绕环获取的best_dis_to_proxy，选择较小者为最佳的代理信息。

2.2.3  节点移动方案

在失效节点完成替换信息查找后，将定位网络中最佳替换节点，并沿循环路由路径与代理扩散路径发送唤醒信息给冗余休眠节点，通知其移动以修复覆盖空洞。由于节点移动将导致较大的能量消耗，SRPCR协议给出一种能耗均衡的节点移动方案。方案的具体步骤如下：在失效节点确定最佳代理节点BP后，将往BP发送唤醒消息，通知其唤醒所代理的冗余休眠节点。唤醒消息包(WM)的格式如图4所示。

图4  唤醒消息格式

Fig. 4  Format of of wakeup message

图4中，offer_id，bp_id和direction分别代表失效节点通过2次绕环路由所确定的最佳代理编号、最佳信息提供者编号以及最佳代理的绕行方向，replace_x和replace_y表示节点需要移动到的位置坐标。在发送此唤醒消息的过程中，将同时进行节点的移动工作。也就是说，唤醒路由路径上的所有节点在收到唤醒消息后，将更新此唤醒消息，然后连同自身状态信息一同移交给下一跳节点，之后自己移动至(replace_x，replace_y)点所代表的位置。如此持续，一直到代理节点将休眠节点唤醒并通知取代自身位置后终止。

通过这种移动方案，明显延长了节点的修复距离。但是，此方案能合理且准确的确定配合移动的节点，又能将覆盖修复过程的移动能耗分摊到整条路由上的节点，有效地均衡了网络能耗，提高了网络寿命。

2.2.4  代理信息维护

由于节点的移动，必将导致网络中的代理信息发生变化，SRPCR协议给出一种局部代理信息重建算法。算法的关键思想如下：在代理节点完成代理信息扩散后，形成了一棵棵以最靠近网络中心的节点为根节点的树。而当网络中节点移动后，代理信息维护工作即变为局部代理信息树的重建工作。在唤醒路由的过程中，选出需重建代理信息树上的代理信息维护节点(RN)。在休眠节点s移动完成后，RN将创建重建消息包(RM)发送给此代理信息树上与之相连的节点，消息包中包含了已移动的代理节点编号。对于任意收到此RM消息的节点，若存储了已移动的代理节点信息，将清除此信息；若节点为此代理树上的其他代理节点，则设定在一段时间后重新启动代理信息扩散工作，重建此代理信息树，之后节点将RM消息传送给此代理树上的其它相连节点。如此逐跳扩散，直至RM消息传送至根节点和所有叶子节点则扩散终止。之后，此代理信息树的其余代理节点将开始重建工作。

3  网络性能分析

本节将从能量消耗，节点移动距离，消息复杂度和节点存储容量等几个影响传感器网络性能和成本的关键指标入手，对SRPCR协议的网络性能进行分析。

定理1：在网络半径为R的规则圆形网络中，SRPCR协议的代理扩散能耗满足：；而对于网络边界周长为l的网络，设其网络边界距中心的最近距离为d_min，SRPCR协议的代理扩散能耗满足：

     (7)

证明：在代理扩散阶段，网络能耗主要集中在扩散路径上的节点对于代理消息的发送和接收。在规则的圆形网络中，任意代理节点将以发射半径r_t将代理信息贯穿网络中心到边界的区域。所以，对于单个代理节点，其代理扩散的能耗为 。而在代理扩散阶段，节点对于交汇路径的裁剪将使整个网络代理扩散的能耗减少。因此，当m个代理节点各不相交扩散代理信息为能耗最大时，此时。所以，SRPCR协议的代理扩散能耗满足，即。

在网络边界周长为l的不规则网络中，其扩散路径可能由于网络边界的不规则而产生绕边界效应。而对于网络中任意代理节点，其最长的扩散路径应为，即围绕整个网络边界进行绕圈。在此情况下，单个代理节点扩散能耗应为 。那么与规则网络同理可得，SRPCR协议的代理扩散能耗 。证毕。

定理2：在网络半径为R的规则圆形网络中，SRPCR协议在第i层环形路由查找能耗满足：；而对于网络边界周长为l的不规则网络，SRPCR协议在任意层的环形路由查找能耗满足：

    (8)

证明：基于第3节所介绍的网络模型及问题描述，SRPCR协议中，环形路由查找阶段的能耗主要集中在正反向绕行时的数据发送和接收能耗，以及正向绕行时的广播能耗。对于网络半径为R的圆形网络，失效节点在第i层的平均绕环距离可计算为，那么，第i层的失效节点其正方向绕行能耗应为。而在绕环路由进行过程中，其路径上的每个节点将以通信半径r_t与其邻居节点进行广播通信，因此，可将广播覆盖范围视为宽度为2r_t的圆环，即覆盖了网络的2个层面。

而在代理扩散阶段，每一层应有1个代理信息节点，所以，1次绕环路由共与2m个代理信息节点广播通信。这样，1次环形路由共经过个节点，每个节点广播的能耗可计算为，同时2m个代理信息节点将接收广播消息并回复代理信息数据包，能耗可计算为，此处r_t/2为邻居节点距离广播节点的平均距离。因此，第i层的环形路由查找能耗需满足：

即

对于网络边界周长为l的不规则网络，由于其形状不规则，无法精确计算其每一层的绕行距离，但任意层次的节点失效，其环形路由的最大绕行距离必定不超过网络边界长度l。因此，任意失效节点其正反方向绕环路由的最大能耗应为，环形路由上节点的广播的最大能耗为，邻居节点接收广播和回复代理信息的能耗为。所以，在边界周长为l的不规则网络中，环形路由查找能耗满足

即

证毕。

推论1：设网络中代理节点落入另一代理节点的邻近区域时必定发生扩散路由交汇，且任意节点落入其邻近区域的概率为λ。那么在网络半径为R的规则圆形网络中，SRPCR协议代理信息维护能耗满足

  (9)

对于网络边界周长为l的网络，设其网络边界距中心的最近距离为d_min，SRPCR协议代理信息维护能耗满足

 (10)

证明：对任意区域的代理信息维护过程，即为此局部区域的代理信息重建过程。在规则的圆形网络中，根据定理1可知，单个代理节点在不发生扩散交汇的情况下，其代理信息扩散能耗为。若此代理信息重建区域有n个代理节点，那么，其代理重建的能耗即为。根据已知条件，在移动冗余节点邻近区域，网络中另外(m-1)个冗余节点任意1个落入此区域的概率为 ，有i个冗余节点落入此移动节点的区域与其代理扩散路径相交的概率为。因此，在任意冗余节点移动后，此区域的代理信息重建能耗应满足

即

在网络边界周长为l的不规则网络中，根据上文的推理，同样可得在任意冗余节点移动后，此区域的代理信息重建能耗满足

即

证毕。

定理3：设冗余节点至失效节点的移动距离为s，SRPCR协议中单个节点一次修复过程中的最大移动能耗E_m和最大修复时延应当满足以下公式：

        (11)

证明：在SRPCR协议的移动方案中，其移动路径上的节点均会参与节点移动，通过逐跳的换位来修复失效节点产生的覆盖空洞。那么，当冗余节点至失效节点的移动距离s小于一跳范围时，其移动的能量应当为；而当s大于一跳范围时，任一节点只需移动至唤醒路由的上一跳节点位置，也就是说节点的最大移动距离为r_t，所以，。同理，单个节点在一次修复过程中的最大时延所满足条件也如定理3所示。

证毕。

根据上一节给出的节点修复方案描述，SRPCR协议无法为每一个失效节点定位全局最优的冗余替换节点，因为曲线修复距离大于直线修复距离。但SRPCR协议在曲线修复方式下，能保证曲线修复路径最短。

定理4：在曲线修复距离下，SRPCR协议中找出的替换节点一定全局最优解。

证明：首先，在SRPCR的代理扩散阶段，代理信息在交汇点进行了剪枝操作。通过剪枝算法，终止了部分非最优节点的向前扩散，保证了每个层面的上的代理信息都是局部筛选出的最优解。而在环形路由阶段，节点将获取所有的局部最优信息进行比较，由此得出的必定是全局的最优解。所以，对于此命题的证明将转化为，环形路由阶段节点广播是否能够覆盖所有的局部最优代理信息。

在代理信息的扩散中，节点以发射半径r_t向前方扩散代理信息，这就意味着一个代理信息的最大跨度为r_t。若要求环形路由中节点广播范围能够覆盖所有代理信息，则必须环形路由中任意2个节点广播所形成的覆盖最窄的区域宽度要超过r_t。即图2中所示的相邻2个节点m和n形成的重叠覆盖最窄的宽度d＞r_t，那么，环形路由阶段节点广播一定能够覆盖所有的局部最优代理信息。因此，问题转化为，对于环形路由的2个相邻节点所形成的覆盖重叠区域最窄的宽度d，必定有d＞r_t。

节点n必定位于节点m的覆盖区域内，也就是说节点n距离节点m的距离小于等于r_t。设节n距离m的距离为x，那么，节点n与节点m覆盖重叠区域最窄的宽度计算如下。

将节点节点n与节点m连线(见图5(a)和(b))，节点n与节点m覆盖重叠区域最窄处必定是分别以节点n与节点m为圆心、以广播半径为r_t的2个圆的交点p和q的连线。因此，只要证明线段|pq|＞r_t即可。而从图5中可得出：|pq|=。很显然，当时，|pq|最大，为2r_t；而时，|pq|最小，为。可见，无论节点n处于哪个位置，必有|pq|＞r_t。从而得证。

图5  环形路由节点的广播覆盖

Fig. 5  Broadcasting coverage of circular routing rode

定理5：SRPCR协议中节点的存储容量为O(1)，所有消息包的空间复杂度均为O(1)。

证明：从2.2节可知，SRPCR协议中，节点只存储了最优的代理信息，而未随代理节点数目的增加或减少而变化，保证了节点的存储容量为O(1)。

2.2节中给出了SRPCR协议运行中，主要产生的4种消息包。从消息报的结构易知，所有消息包的空间复杂度均为复杂度O(1)。

证毕。

4  仿真实验数据分析

本文采用OMNET++来进行实验验证。OMNET是一个为大型网络提供开源的、基于组件的、模块化的开放网络仿真平台，在非商业化的仿真软件中拥有大量的用户，得到学术界广泛认可^[13]。实验场景中的网络参数设定如下。在规则的圆形网络中网络半径R=400 m，1 000个活跃节点随机部署于网络之中。对于非规则的网络，保证其网络覆盖面积与规则网络一致，同样随机部署1 000个活跃节点。2种网络场景中，以T作为1个时间周期，在每个周期内任一传感器节点将消耗1个随机能量用于数据感知和收集等，其中10 000＜＜90 000。传感器能量消耗模型中的参数取值如表1所示，表2中部分变量的取值为：σ=100 bit，τ=50 bit，φ=10 bit，η=30 bit。

4.1  SRPCR协议性能对比

本节验证SRPCR协议的性能对比。为更好地体现协议在网络寿命，最优冗余节点选取率，节点存储容量等方面的优化，对比协议采用了Li等^[9]提出的MSRP协议。

图6(a)所示为代理信息扩散阶段的能耗对比。从图6(a)可见：随着代理数目的增加，2种协议的代理信息扩散能耗也在增加，但增加的趋势愈见平缓。对于同一个协议，在2种不同网络场景下其能耗相当接近，但MSRP协议的代理信息扩散能耗明显比SRPCR协议的高。图6(b)所示为代理信息维护阶段的能耗对比曲线。对于MSRP协议，代理信息在发生一次节点移动后将全局重新扩散，因此，其代理信息维护能耗与其代理扩散能耗曲线一致；而SRPCR协议在代理信息维护过程采用了局部重建算法，其维护能耗随代理节点数目的增加而增长，但从整体来看，整个维护能耗与MSRP协议的维护能耗相差甚远。

图6(c)所示为查找最佳代理阶段所消耗的能量对比图。从图6(c)可见：，随代理节点数目的增加，MSRP协议的查找能量逐渐减少，而SRPCR协议的查找能量则逐渐增加，2种不同的网络环境对协议的能量变化影响不大。但从图6(b)可见：节点的查找能耗与代理信息维护能耗相比相差了1个数量级，因此，SRPCR协议在此部分的额外能耗不会过多地影响网络寿命。

图6(d)对比了2种协议下的网络寿命。从图6(d)可见：随着代理节点数目的增加，2种协议的网络寿命也随之增长，但相比之下，SRPCR协议具有更好的寿命表现。图7(a)所示为SRPCR协议和MSRP协议下节点失效空洞修复时选中全局最佳替换节点的概率对比。从图7(a)可见：随着冗余替换节点数量的增加，2种协议选中最佳替换节点的概率都逐步增长。在替换节点数目相同的情况下，SRPCR协议选中最佳替换节点的概率要略微高于MSRP协议。图7(b)中所示为参与代理信息扩散的节点存储信息量对比图。为体现协议中剪枝算法对于节点存储量的改善，在对比图中加入了文献[8]中的空洞修复协议，简称为SPMSN协议。对于使用了剪枝算法的SRPCR和MSRP协议，其节点的代理信息存储量始终维持在1个单位，而SPMSN协议则随着替换节点数目的增加，节点的信息存储量持续上扬。

图6  SRPCR与MSRP协议对比图

Fig. 6  Comparison chart of SRPCR and MSRP protocols

图7  多个协议对比

Fig. 7  Comparison of different protocols

4.2  网络参数对协议性能的影响

从4.1节的实验结果可知，网络的形状对于协议的整体性能影响不大。因此，这里以规则的圆形网络为例，通过变换网络中的一些重要参数来验证网络性能的变化，了解不同的网络参数对于协议性能的影响。

图8(a)所示为不同代理节点数目下，网络寿命随网络半径的变化规律。在同样的代理节点占总节点的比例条件下，网络寿命随网络半径的增长而缓慢增加。但在同一网络半径下，网络寿命随着代理节点数目的增加而增长迅速。数据包的大小将直接影响网络的总体能耗和网络的生命周期，图8(b)和(c)所示分别为数据包和环形路由数据包的大小变化对SRPCR协议下网络生命周期的影响。从图8(b)可见：代理数据包的变化对于网络寿命的影响比较显著，在代理节占总节点的比例较高的网络中，代理数据包大小的变化对网络寿命的影响更为显著。从图8(c)可见：环形路由数据的长度变化对网络寿命的影响较为薄弱，在同一数据包长度下，网络寿命的差距较明显。

图8  网络寿命对比

Fig. 8  Network lifetime comparison

5  结论

(1) 提出了一种新的覆盖空洞失效修复协议(SRPCR)。其协议主要思想如下：该算法为每一个冗余休眠节点选取离自身最近的工作节点作为其代理节点。之后，代理节点将自己的位置信息（称为代理信息）沿自己与网络几何中心的连线方向向两端进行逐跳扩散，直到网络边界，以此使得代理信息能纵穿整个网络。当工作节点濒临失效时，将以几何中心为圆心，在网络中进行绕环路由，寻找距离自身最近的休眠节点，并将其唤醒。之后，SRPCR采用了一种能量均衡的节点移动方案，使节点移动路径上的每一个节点配合移动，修复节点失效所产生的覆盖空洞。

(2) SRPCR协议极大地降低了代理信息维护的能耗，优化了网络寿命。当一个休眠节点被唤醒执行修复工作后，网络节点所存储的代理信息将发生变化。在大多数已有的研究中，整个网络的代理存储信息都需要重新建立，从而带来巨大系统开销。因此， SRPCR协议给出了一种高效的代理信息维护算法，通过代理信息维护节点，以较小的代价重建局部代理信息树，保证了代理信息的维护能耗大大减小，延长了网络的生命周期。

(3) SRPCR协议使节点存储容量和消息包长度均为O(1)，并且其最佳替换节点的选中率接近90%。在多个代理节点进行信息扩散时，会产生扩散路径的交叉现象。SRPCR在每一个交叉节点中使用了剪枝算法，使其选取局部最优的代理信息存储并向前扩散，保证了代理扩散消息包的长度为O(1)。SRPCR协议能保证全局最佳替换节点的选中概率高达90%以上。

参考文献：

[1] 韩志杰, 吴志斌, 王汝传, 等. 新的无线传感器网络覆盖控制算法[J]. 通信学报, 2011, 32(10): 174-184.

HAN Zhijie, WU Zhibin, WANG Ruchuan, et al. Novel coverage control algorithm for wireless sensor network[J]. Journal on Communications, 2011, 32(10): 174-184.

[2] 凡高娟, 孙力娟, 王汝传, 等. 非均匀分布下无线传感器网络节点调度机制[J]. 通信学报, 2011, 32(3): 10-17.

FAN Gaojuan, SUN Lijuan, WANG Ruchuan, et al. Non-uniform distribution node scheduling scheme in wireless sensor networks[J]. Jounal of Communications, 2011, 32(3): 10-17.

[3] 何欣, 桂小林, 安健. 基于延迟唤醒的无线传感器网络的分布式区域覆盖算法[J]. 计算机研究与发展, 2011, 48(5): 786-792.

Xin He, Xiaoxin Gui, An Jian. A distributed area coverage algorithm based on delayed awakening in wireless sensor networks [J]. Journal of Computer Research and Development, 2011, 48(5): 786-792.

[4] Li J, Zhang B, Cui L, et al. An extended virtual force-based approach to distributed self-deployment in mobile sensor networks[J]. International Journal of Distributed Sensor Networks, 2012, 2012: 1-15.

[5] 王良民, 李菲, 秦颖. 基于移动节点的无线传感器网络覆盖洞修复方法[J]. 通信学报, 2011, 32(4): 1-8.

WANG Liangmin, LI Fei, QIN Ying. Resilient method for recovering coverage holes of wireless sensor networks by using mobile nodes[J]. Journal on Communications, 2011, 32(4): 1-8.

[6] 赵小敏, 毛科技, 何文秀, 等. 感测范围不规则情况下无线传感器网络节点部署算法[J]. 软件学报, 2012, 23(1): 59-68.

ZHAO Xiaomin, MAO Keji, HE Wenxiu, et al. Deployment algorithm for wireless sensor network with irregular sensing range[J]. Journal of Software, 2012, 23(1): 59-68.

[7] Chellappan S, Bai X, Ma B, et al. Sensor networks deployment using flip-based sensors[C]//Mobile Adhoc and Sensor Systems Conference, 2005. IEEE International Conference on. Washington: IEEE, 2005: 8-298.

[8] Wang G, Cao G, La Porta T, et al. Sensor relocation in mobile sensor networks[C]//INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE. Miami, USA: IEEE, 2005, 4: 2302-2312.

[9] Li X, Santoro N, Stojmenovic I. Mesh-based sensor relocation for coverage maintenance in mobile sensor networks[J]. Ubiquitous Intelligence and Computing, 2007: 696-708.

[10] Wang G, Cao G, La Porta T. Proxy-based sensor deployment for mobile sensor networks[C]//Mobile Ad-hoc and Sensor Systems, 2004 IEEE International Conference on. Florida: IEEE, 2004: 493-502.

[11] 包旭, 巨永锋. 面向节点失效的无线传感器网络覆盖空洞修复算法[J]. 计算机测量与控制, 2011, 19(6): 1516-1522.

BAO Xu, JU Yongfeng. Coverage-Hole repair algorithm towards nodes failure in wireless sensor networks[J]. Computer Measurement & Control, 2011, 19(6): 1516-1522.

[12] Li X, Fletcher G, Nayak A, et al. Randomized carrier-based sensor relocation in wireless sensor and robot networks[J]. Ad Hoc Networks, 2013, 11(7): 1951-1962.

[13] Liu A F, Zhang P H, Chen Z G. Theoretical analysis of the lifetime and energy hole in cluster based wireless sensor networks[J]. Journal of Parallel and Distributed Computing, 2011, 71(10): 1327-1355.

(编辑  邓履翔)

收稿日期：2013-08-01；修回日期：2013-10-06

基金项目：国际科技合作计划专项(2013DFB10071)；国家自然科学基金资助项目(61073104)；中南大学米塔尔创新项目(12MX15)

通信作者：刘安丰(1971-)，男，湖南常德人，副教授，博士，从事研究领域为无线传感器网络研究；电话：13723860232；E-mail：csuanfengliu@gmail.com