时间容忍条件下无线传感器网络节点失效修复

张生凤，王坤达，吴晓蓓

(1.中国船舶重工集团公司第七二三研究所，江苏 扬州 225001； 2.南京理工大学 自动化学院，江苏 南京 210094)

0 引 言

无线传感器网络的寿命通常会受到传感器节点的生命周期的影响，而有限的能量供给和恶劣的工作环境又会导致传感器节点的过早失效。因失效节点在拓扑中的所处位置不同，该失效对网络的影响也不尽相同。根据网络中数据传输的特性，失效节点会导致其本身传递的数据负载重新分配，可能会导致网络中其余节点的负载增加而发生级联失效[1]。

目前，级联失效相关问题的主要研究方向还是复杂网络[2-7]，其中最为典型的应用就是电力网络[5-7]。文献[2]针对物联网中日益需求的面向服务计算，研究了服务节点可能出现的级联失效问题，提出了一种基于新增服务节点的复杂网路容错控制算法。Liu等[4]则充分考虑了失效节点邻居节点的剩余能量，提出了一种时变的负载重新分配方法来降低级联失效的影响。针对无线传感器网络相关的级联失效问题研究多是围绕网络模型而展开，并有一些学者也在此基础上提出了相关容错策略[8-11]。Hu等[8]就对随机网络、无标度网络、WS小世界网络、NW小世界网络4种模型下的级联失效问题进行分析，通过仿真得出了无标度网络模型在节点失效容忍方面比其它模型更为稳定的结论。文献[9]则通过构建无标度网络模型，得出了节点的级联失效临界负载值，并在节点负载大于临界时切断相应链路来避免级联失效的发生。然而，此类容错研究往往对网络初始部署节点的能量有所要求，而且对于网络中已经出现节点失效的情况并不一定适用。

为此，本文针对无线传感器网络中单一节点失效导致的负载再分配问题，提出了一种基于时间容忍条件的单一节点失效修复策略(TTM based topology reconfiguration algorithm，TTM-TRA)。其中，节点失效的时间容忍条件(time tolerated manner，TTM)是基于传统的级联失效模型提出的。TTM-TRA属于典型的反应式修复策略，并可分为失效节点的影响评估和修复节点的选择调度两个部分。该算法在检测到节点失效后，通过判定网络中其余节点对该节点失效是否容忍，并利用局部拓扑重构来缓解该失效造成的负载重新分配问题对其它节点的影响，能够在一定程度上延长网络的生命周期。

1 前提假设与基本定义

1.1 前提假设

为简化本文后续的分析及讨论，对网络及节点做出以下几点假设：

(1)网络初始状态为整体连通，各传感器节点为同构，即具有相同的通信半径R、硬件特性等，并且网络中的节点都具备移动特性。

(2)正常运行过程中，网络拓扑及数据路由保持不变，且网络中的节点能够以既定路由将数据传输至汇聚节点。

(3)网络中各传感器节点能够获知自己的位置，并且能够获知其两跳内邻居节点的相关信息，如容量、负载、剩余的能量、位置信息等。

(4)节点能够将需要传输的数据量均匀地分配给所有路由方向上的子节点。

1.2 基本定义

考虑到无线传感器网络的级联失效问题是由节点失效导致的负载再分配而形成，为便于本文后续内容的理解和说明，对涉及的特定名词给出以下定义。

定义1 节点容量：节点的容量定义为网络中节点所能承载的最大实时传输数据量，表示为C；

定义2 节点负载：节点的负载定义为节点实时传输的数据量，表示为L；

定义3 节点生命周期：节点的生命周期定义为节点由初始工作至失效的运行时间，表示为T。为了方便统计，本文中节点的生命周期计为该节点进行数据传输的次数；

定义4 父节点：在路由确定的网络中，若数据由节点i传输至节点j，则节点i称作节点j的父节点；

定义5 次级节点：在路由确定的网络中，若节点j为节点i的子节点，且节点k是节点j的子节点，则称节点k是节点i的次级节点；

定义6 同层节点：在路由确定的网络中，若节点Aii=1,2,…,n拥有共同的父节点B，则称节点Aii=1,2,…,n互为同层节点。

2 网络模型及问题描述

2.1 节点通信能耗模型

本文研究基于时间容忍条件的节点失效修复问题，节点的负载重新分配和节点生命周期的重新计算是其中的两个关键点，而这两方面都与节点的通信能耗模型密切相关。目前，相关研究采用的节点通信能耗模型有多种，且各模型均有不同的侧重。因为要针对节点的通信负载进行研究，故选用文献[12]给出的节点通信能耗的评估模型

ξ(e)=ms×nh+tr

(1)

其中，ms为传输的数据量，nh为数据传输所需的跳数，tr为数据传输过程中侦听和接收数据所需的时间。计算节点向1跳邻居传输数据的能耗时，nh=1。为了进一步简化分析，假设各节点的tr相同，节点通信能耗的评估模型可简化为ξ(e)=ms。因此，本文假设节点的通信能耗与节点的数据传输量成正比，它们间的关系满足下式

e=k*ms=k*L

(2)

其中，k为网络中的特征常数，表示节点传输单位数据时的通信能耗，ms为节点传输的数据量，即节点的通信负载。

2.2 节点失效的时间容忍条件

本文主要基于无线传感器网络中目前已有的级联失效的概念，提出了网络对于节点失效的时间容忍条件，并在此基础上完成了TTM-TRA算法的设计。下面结合图1，简要介绍级联失效的概念。

图1 级联失效

(1)初始网络中，节点V4的负载均匀地分配给它的3个子节点V2、V5、V6；

(2)若节点V5在t时刻失效，V4与V5之间的连通链路断裂；V4节点的负载L4(t)将会重新分配给它的剩余子节点V2和V6，则此时V2和V6增加的负载为

(3)

(3)若节点V2的负载超过容量C，节点V2也会失效，进而导致节点V3再次进行负载重新分配。类似的负载再分配过程会持续进行，直至网络整体连通断裂或所有节点的负载均满足Li(t)≤C(i为节点编号)。

由上述内容可以看出，级联失效是指由初始部分节点失效而导致的后续一系列失效过程，通常是指节点负载超过其最大容量而失效的情况，然而失效节点负载重新分配的影响却不仅限于此。总体来讲，负载的重新分配会导致某些节点由于负载超过其容量直接失效，或导致节点的负载处于一个较高的状态，大大缩减其生存周期。为此，本文给出了网络中节点失效的时间容忍条件TTM，其具体定义如下：

若网络中节点Vi在t时刻失效，网络中其余节点Vjj∈1,…,N,j≠i在t时刻的负载、能耗以及剩余能量分别为Lj(t)、ej(t)、Ej(t)。结合节点的能耗模型可得节点的剩余的生命周期为

(4)

如上式所示，若Lj(t)>C，则节点Vj会由于瞬时负载超过其容量而直接失效。为了能够较为全面地分析随机节点失效对网络中负载重新分配的影响，对网络中其余节点Vjj∈1,…,N,j≠i设定特定的失效时间容忍阀值Tj。若tj≥Tj，则称节点Vj能够容忍节点Vi的失效；否则不能容忍，即表示为节点Vj将会直接受到由Vi失效的影响，立即或在较短时间内由于过高能耗而失效。

(1)若某节点C的路由方向上有两个子节点，如图2(a)中节点D和节点E。假设D点在t时刻失效，节点E的实时负载为

LE(t)=LC+Lp=LEt-1+LC/2

(5)

(2)若某节点C的路由方向上有3个子节点，如图2(b)所示。假设D点在t时刻失效，节点E的实时负载为

LE(t)=LC/2+Lp=LEt-1+LC/6

(6)

以上两式中，Lp表示由其余父节点分配至节点E的负载，LC为节点C的负载。考虑较为理想的情况，设Lp=0且两种情况均满足LE(t)≤C，则在节点D失效之后，节点E的生命周期分别为失效之前时的1/2和2/3。再因为第一类情况中，节点D的失效会导致节点E变为割点，所以本文设定常数α=2/3。

3 基于时间容忍条件的拓扑重构修复算法

TTM-TRA作为典型的反应式算法，其主要执行步骤可以分为两个部分。首先是对失效节点的影响进行衡量和评估，判断其失效是否会导致网络中其余节点的生命周期不能满足时间容忍条件，这个步骤可以在网络拓扑形成之后通过具体计算得到；其次是修复节点的选择，若该节点的失效会导致其余节点受到较为严重的影响，则需要对该节点的失效进行修复，如何选择最合理的移动节点进行修复也需要进行讨论。

3.1 失效节点的影响评估

由前提假设(3)可知，每个传感器节点能够获知其两跳邻居的信息，则每个节点Vi就能得到其路由方向的父节点Vj以及Vj的其余子节点的状态参数。若节点Vj的实时负载为Lj且路由方向上子节点的个数为γ，则仅由节点Vj分配至其路由子节点的负载可以表示为Lj/γ。因此，某一节点随机失效会导致其父节点的路由子节点总数发生变化，进而会导致其同层节点的负载直接发生改变。

节点失效而导致的负载变化可能会波及到整个网络，但是遭受最为直接影响的是失效节点的路由子节点及其同层节点。通常情况下，失效节点路由子节点的负载都不会随着该节点的失效而增大。为了能够更为直接分析TTM在节点失效后的作用机制，本文主要针对失效节点的同层节点展开分析。

如前文所述，负载再分配除可能直接导致网络中部分节点的负载超过容量之外，还可能使部分节点工作在高额负载并且极大缩短其生命周期。下面结合TTM，将网络中失效节点的情况分为以下3类：

(1)失效节点为割点。这是一类特殊情况，也为目前相关研究的重点，失效节点必须修复。

(2)节点失效会导致网络中其余节点出现过容情况。网络中存在其余节点的实时负载超过其本身容量，失效节点需要修复。

(3)节点失效会导致网络中其余节点出现高额负载情况。这种情况会导致网络中存在部分节点由于较高负载而过早失效。

除针对割点的第一类特殊情况需要对节点位置进行分析之外，第二、三类节点的失效都需要对网络中其余节点的实时负载进行计算，并需要结合TTM判断该失效是否能被容忍。

网络正常运行过程中，各节点之间可以通过定期的“heartbeat”信息交互确认自身工作状态，并将是否丢失这种信息用作判断节点是否失效的依据。设定某个连续丢失两周期“heartbeat”信息的节点为失效节点，一旦检测到某一节点的失效，该失效节点影响的评估策略开始执行。针对以上3种失效节点的分类，失效节点影响的评估主要分为两个步骤：

(1)首先，进行失效节点是否为割点的判断。有关割点的判断目前有很多成熟的方法，其中最为经典的就是利用深度优先搜索算法(deep first search，DFS)。然而，DFS算法需要进行全局搜索且开销巨大，故依据文献[13]所提出的分布式CAM算法进行割点的判断。CAM算法是一种近似判定方法，它通过设置节点与其关联的通信链路编号，能够较为准确地进行割点的判断，且通信复杂度仅为On(n为网络中的节点数)。

(2)其次，若失效节点不属于割点，则需通过TTM判断该失效是否会被容忍。如该失效无法容忍才进行修复。具体的判断分为两个步骤：首先，直接判断失效节点的同层节点中是否有节点的负载超过其容量；其次，在节点负载并未溢出的前提下，对失效节点的同层节点进行实时的剩余生命周期计算，并与同等能量条件、负载未变化的情况下的理论剩余生命周期作比较，判断TTM是否成立

(7)

其中，et-1和e(t)分别表示在t时刻，节点失效前后该同层节点的单轮次数据传输能耗，E(t)表示t时刻节点的剩余能量。若失效发生前后该节点的理论生命周期间的关系满足上式，则该失效可以容忍，不需要执行修复策略。若无法容忍，则该失效节点需要进行修复。

3.2 修复节点的选择

TTM-TRA算法主要基于网络中节点的移动特性，选取最佳的修复节点移动至失效节点位置，并替代其在网络中的作用。与已有的相关研究不同，TTM-TRA中的修复节点并不能直接从失效节点的邻居节点中挑选。这是因为，TTM更加关注节点之间数据传输的相对关系，失效节点的通信邻居中也可能存在关键节点，所以不能直接通过距离等因素进行修复节点的选择。下面将从两个方面来讨论如何进行修复节点的选择，首先是确定修复节点的选择范围；其次是设定合理修复节点选择的优先权值，完成多数备选节点中最佳的选择。

3.2.1 修复节点的选择范围

因为修复节点的移动应当被视作在原位置的失效，所以修复节点的选择应该满足以下两个基本条件：

(1)修复节点不能是割点，否则其移动会导致网络连通性破坏；

(2)修复节点的移动应当能够被其余节点所容忍，否则该修复过程会带来新的失效问题。

下面结合定理1和定理2，对修复节点的可选范围进行确定。

定理1 若某一节点的失效无法满足TTM，那么该失效节点的同层节点不能被选作修复节点。

证明：由前提假设可知，失效节点及其同层节点的负载是由路由父节点均匀分配的，而移动失效节点的同层节点进行修复后，其路由父节点的剩余子节点数并不会改变。因此，若失效节点无法满足TTM，它的同层节点不能被选作该失效的修复节点。

定理2 在不考虑节点负载超过容量的前提下，若网络中某一节点拥有超过3个子节点时，则该节点任一子节点的失效能够满足TTM。

证明：因为假设时间容忍阀值中特征常数α=2/3，结合2.2小节的论述，定理2显然得证。

因为选择失效节点的1跳邻居作为修复节点，可以大大节省修复节点移动时的能量消耗，所以失效节点的1跳邻居仍是修复节点的最佳选择范围。由于节点的1跳邻居中可能包含多个路由关系，还需对其中的一些特殊情况加以说明。首先，虽然失效节点的路由父节点是其1跳邻居，但是路由父节点的移动将会导致更大范围的负载再分配，所以不能被选作修复节点。其次，由定理1可以明显看出，若失效节点无法满足TTM，该失效节点的同层节点通常不能被选作修复节点。由此可以得到，失效节点的路由子节点可以作为修复节点的备选范围。

定理2说明了在失效节点具有3个或3个以上路由子节点的情况下，选择其中的任何一个节点作为修复节点都能够满足TTM。若失效节点的路由子节点数无法满足上述条件，则就需要在失效节点的非1跳邻居中选择修复节点。因此，在这种情况下，修复节点的选择范围需要扩大至失效节点的次级节点。

下面结合图例对修复节点的可选范围进行简要说明。如图3(a)所示，若图中节点C失效，其路由子节点D、E、F都可以作为修复节点的备选节点。如图3(b)所示，若图中节点C失效，其路由子节点D、E的移动无法满足TTM，而节点D的子节点F、G、H可以作为修复节点的备选节点。

图3 失效节点的修复节点选择范围

3.2.2 修复节点选择的优先权值

除上述的基本条件外，仍需要在选取修复节点时综合考虑备选节点距离失效节点的距离d和节点的剩余能量E。因为节点在移动过程中需要耗费一定的能量，所以越短的移动距离越能够减小节点在移动过程中的消耗，从而使其在修复结束之后能够保留较多的能量；另一方面，节点的剩余能量也是影响节点生命周期的直接因素，较高的剩余能量也能够保证其在执行修复步骤之后能维持较长时间的稳定工作。因此，下面给出了修复节点选择的优先权值定义

(8)

式中：E表示备选节点的剩余能量，d表示备选节点与失效节点之间的距离，β为0-1之间的一个固定常数(设定为0.5)，P则表示节点被选作修复节点的优先权值。在确定修复节点的可选范围之后，可以通过计算各个备选节点对应的优先权值，完成最优修复节点的选择。

考虑到修复节点需要移动至失效节点处，所以移动节点剩余能量与其相距失效节点之间的距离还需要满足一个基本条件，E≥γd(γ表示节点移动单位距离的能耗)。因此，可以通过对可选范围内的每个传感器节点，进行类似自检程序的初步计算来进一步缩小修复节点的可选范围。

3.3 TTM-TRA算法执行流程

综上所述，TTM-TRA算法的执行流程可以归纳如图4所示，主要包括失效节点的检测发现、失效节点的影响判断、修复节点的选择这3个主要步骤。与目前单一节点失效修复的相关研究类似，TTM-TRA算法中的割点失效依旧具有最高优先级，而对非割点失效的情况才会进行其它节点的TTM容忍性判断。

图4 TTM-TRA算法执行流程

下面结合图例，对TTM-TRA算法执行前后的网络拓扑进行分析对比。图5(a)为网络的初始拓扑，节点A有3个路由子节点B、C、D。若节点A失效，节点B、C、D都在修复节点的可选择范围内。首先，判定节点A不是割点，但是它的失效无法满足时间容忍条件TTM，因此需要进行修复节点的选择。其次，失效节点A的3个路由子节点中仅有节点B、D满足修复节点的选择条件，若通过计算这两个节点的选择优先权值，最终得到PD>PB，则可以判定最优修复节点为节点D。最后，节点D移动至失效节点A的位置，并且分别建立节点D与节点C、节点B之间的连通链路，修复之后的网络拓扑如图5(b)所示。

3.4 算法性能分析

TTM-TRA算法的通信开销并不大，而且主要集中在失效节点影响评估以及修复节点选择范围确定的过程中。首先，失效节点的影响评估依赖于CAM算法及与失效节点能否满足TTM的判定过程，其中由文献[13]中的分析可以得到CAM算法的通信复杂度在通常网络中可以表示为On；而相关节点的失效容忍判定仅需要进行两跳内的一次交互通信传输，其通信过程的复杂度可以表示为On。其次，修复节点的选择范围设定为失效节点的两跳内的路由子节点，而可选修复节点的判定则依赖于各节点本身状态信息的传输，该过程的通信复杂度也为On。综上所述，TTM-TRA算法的通信复杂度可以表示为O(n)，

图5 TTM-TRA修复前后网络拓扑图

n表示网络中节点的数量。

通过设定时间容忍阀值中特征常数α的不同取值，可以反映出修复算法对节点失效的不同容忍程度。比如，设定α=2/3，就表示在不考虑附加负载的情况下，失效节点至少有两个同层节点时该失效才能被容忍；若设定α=1/2，失效节点至少有一个同层节点时该失效才能被容忍，这与 “二元点割集”的相关讨论也有所关联。因为修复节点的选择范围仅为失效节点的两跳邻居，TTM-TRA算法的执行要求失效节点拥有一定数目的路由子节点或者次级节点，所以它比较适用于节点分布相对密集的网络。

4 仿真分析

4.1 仿真参数设定

本部分对TTM-TRA算法进行了仿真设计，旨在对路由确定网络中出现的单一节点失效的影响进行分析，并在此基础上完成对该失效的合理修复，避免直接或间接式的级联失效发生，在一定程度上延长网络中其余部分节点的生命周期。仿真在同等条件下，将TTM-TRA与RIM算法进行了部分参数的对比，因为相较于DARA算法，RIM并不局限于割点的失效修复问题，而且TTM-TRA针对的失效节点范围也相对宽泛。考虑到节点失效的时间容忍条件是从节点的生命周期的角度进行分析，所以仿真将各修复算法所需的修复节点数、修复节点移动总距离以及相应节点的剩余生命周期进行对比：

(1)修复节点数：指完成修复所需移动的修复节点数量，直接反映了修复算法造成的拓扑重构规模。

(2)修复节点移动总距离：指所有修复节点的移动距离之和。TTM-TRA算法利用节点的移动特性完成失效节点的修复，而节点移动过程耗能都相对较大，所以修复节点的移动总距离能够在一定程度上反映出算法在实际执行过程中的开销。

(3)相应节点的剩余生命周期：指修复完成后，之前受到失效影响节点的剩余生命周期。节点失效导致的负载重新分配会直接影响部分节点的生命周期，该参数能够在一定程度上反映TTM-TRA算法的有效性。因此，相应节点的剩余生命周期是衡量TTM-TRA算法效果的一个重要指标。

TTM-TRA算法的仿真设计均基于Matlab 2010b平台，主要的仿真参数见表1。此外，仿真设定网络为树形结构，且各个节点能够按照既定的路由进行数据传输。考虑到算法在设计过程中涉及了两个特征参数的选取：时间容忍阀值α和修复节点优先权值的选择参数β，因此仿真设计对这两个参数的选择不同也进行了相应的对比。

表1 仿真参数设定

4.2 修复所需节点数

TTM-TRA算法与RIM算法有着本质的区别，RIM采用的是“向心收缩”的修复算法，而TTM-TRA则是与DARA类似，单一节点失效通常会在1跳邻居内选择最优的修复节点进行直接修复。在涉及到某些特殊情况时(如1跳邻居内没有可选修复节点)，需要采用多节点级联移动的方式，从而会导致部分仿真所需节点数上升。本部分共进行两组仿真，分别从固定初始网络节点规模和固定节点通信半径的角度出发。第一组设定初始网络节点数由200至400变化，节点的通信半径设定为50 m；第二组设定初始传感器节点数为300，节点的通信半径由30 m至50 m变化。仿真数据均为50次迭代的平均值，并且仿真也讨论了时间容忍阀值中特征参数α的取值对结果的影响。两组仿真条件下，最终得到的修复所需移动节点数目对比分别如图6(a)和图6(b)所示，其中TTM-TRA(I)和TTM-TRA(II)分别表示了α=2/3和α=1/2时的修复算法。

图6 所需修复节点数随网络参数变化关系

由图6(a)可以看出，RIM算法在修复单一节点失效时需要移动较多的节点，而且所需修复节点的数目会随着网络规模的增大而增大，因为其修复所需移动节点数与失效节点的1跳邻居节点数有直接的联系。而TTM-TRA算法在完成修复时所需节点数相对较小，基本能够维持在2以内。随着网络初始部署的节点数逐渐增多，节点部署逐渐密集，修复节点可能直接由失效节点的1跳路由子节点中选出，所以修复所需节点数会随着网络规模的逐渐增大有一定的减少。通过对比TTM-TRA(I)和TTM-TRA(II)的曲线还可以看出，随着α取值的增大，修复节点所需满足的要求愈加苛刻，可能需要在失效节点的次级节点中选择修复节点，因此修复所需节点数会相对较大。

图6(b)显示了修复所需节点数与节点通信半径间的对应关系。随着节点通信半径逐渐增大，初始网络中的节点分布越来越密集，失效节点的路由子节点会逐渐增多，能够基本保证仅需要移动一个路由子节点就完成修复。所以，节点的通信半径逐渐增大时，所需移动的修复节点数会逐渐收敛到1。由图中可以看出，TTM-TRA算法在节点通信半径为50 m时，基本仅需移动一个节点就能完成修复。与网络初始节点数变化时类似，在α=2/3的情况下，TTM-TRA算法所需的修复节点数与α=1/2时相比也较少。而RIM则与之相反，随着网络中节点分布的逐渐密集，失效节点的1跳邻居节点数增加，直接会导致其需要移动较多的修复节点。

4.3 修复节点移动总距离

本小节设计了两组不同的仿真环境，分别对修复节点移动总距离与初始网络中节点数目、节点通信半径之间的关系进行了讨论。第一组设定节点通信半径为50 m，初始节点数由200至400变化；第二组设定网络初始节点数为300，节点通信半径由30 m变化至50 m。仿真数据均为50次迭代的平均值，并且仿真也讨论了时间容忍阀值中特征参数α的取值对结果的影响。两组仿真条件下，最终得到的修复节点移动总距离对比结果分别如图7(a)和图7(b)所示，其中TTM-TRA(I)和TTM-TRA(II)分别表示了α=2/3和α=1/2时的修复算法。

由图7(a)可以看出，RIM算法因为需要移动较多节点完成修复，所以节点的总体移动距离会比TTM-TRA算法大。此外，随着初始部署节点数增多，失效节点的1跳邻居数也可能增多，RIM算法修复节点的移动总距离也会呈现上升趋势。在网络初始部署节点数达到300时，RIM算法中修复节点移动总距离会出现略微的下降。这可能是因为，随着网络中的节点越来越密集，虽然移动的节点总数增加，但是单个节点需要移动的距离会有所下降，所有节点的移动总距离也可能出现略微下降。与之相比，TTM-TRA算法由于通常仅需要移动一个修复节点，而节点之间的距离会随着网络初始部署节点增多而减小，所以修复节点移动的距离总体会呈现一个下降趋势。然而，在α取2/3时，修复节点的可选范围会比α取1/2时小，所以TTM-TRA(I)算法所需的修复节点移动总距离会比TTM-TRA(II)算法小。

图7 修复节点移动总距离随网络参数变化关系

图7(b)显示了修复节点移动总距离与节点通信半径间的变化曲线。由图中可以看出，RIM算法中修复节点移动总距离会随着节点通信半径的变大而明显上升。由于TTM-TRA算法中的修复节点能够在失效节点的路由子节点和次级节点中获得，所以修复节点的移动总数不会很大，修复节点的移动总距离也仅会随着节点通信半径的变大而略微增大。就修复算法所需移动节点数目和节点移动的总距离来讲，虽然TTM-TRA算法会比RIM算法有着一定的优势，然而在节点的平均移动距离方面，RIM会表现得更好。

4.4 相应节点剩余生命周期对比

若网络中出现单一节点失效，则失效节点的同层节点将会直接受到负载重新分配的影响，节点的生命周期可能会有所下降。对失效节点的同层节点剩余生命周期进行分析，能够反映出TTM-TRA算法能否有效地减小负载再分配的负面影响。假设节点每轮采集数据量为10 bit，节点的容量为400 bit，单位数据传输能耗为200 nJ/bit，并且设定α=2/3。为了简要说明算法的可行性，此处将节点接收和发送的数据量视作近似相等。仿真选取了两类情况分别分析了节点失效与修复时的剩余生命周期对比。其中，第一类情况为失效节点存在2个同层节点，第二类情况为失效节点存在1个同层节点。仿真结果分别如图8(a)、图8(b)所示。

图8(a)中的“Node 1、Node 2”分别表示了失效节点的两个同层节点，图8(b)中的“Node 1”表示了失效节点的一个同层节点。两种情况下，修复节点在完成修复后，生命周期是有较为明显的下降，因为移动消耗掉了它相当部分的能量。理论上，当失效节点被修复时，失效节点同层节点的生命周期应该上升至修复前的3/2。图8(a)中的“Node 1”在修复前后生命周期上升幅度并没有达到理想值，因为其本身的负载可能来自多个父节点。由图8(b)中可以看出，当失效节点仅有1个同层节点时，该节点的剩余生命周期在失效节点修复后会上升到修复前的3/2。

图8 两类情况修复前后同层节点的剩余周期变化

总体而言，节点失效时间容忍条件中α的取值相当关键，它直接决定了TTM-TRA算法需要针对的失效节点以及修复节点的可选情况。本章中设定α=2/3，实际是约束了失效节点具有2个或2个以下同层节点的情况，而对于它具有更多同层节点的情况并不会执行修复。若需要基于时间容忍条件对不同类型的节点失效情况进行处理，则可以根据网络需求对α的实际取值进行相应调整，α的取值越大，时间容忍条件对失效节点的约束越苛刻。

5 结束语

本文针对节点失效导致的负载再分配问题，提出了一种单一节点失效的拓扑重构式修复策略TTM-TRA。该修复策略在节点级联失效模型的基础上提出了节点失效的时间容忍条件，并通过失效节点同层节点的生命周期的计算判定失效节点的影响。时间容忍条件的使用取决于容忍阀值中特征常数α的取值，α的数值越大可以认为失效节点容忍条件越为苛刻。通过设定时间容忍阀值的特征参数为α=2/3，能够保证TTM-TRA算法对同层节点数不超过2的失效节点进行有效修复。由仿真分析可以看出，TTM-TRA算法实际是将修复节点的部分生命周期与失效节点的同层节点进行高效置换，能够在一定程度上延长网络的整体寿命。