時間容忍條件下無線傳感器網絡節點失效修復

張生鳳，王坤達，吳曉蓓

(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算法實際是將修復節點的部分生命周期與失效節點的同層節點進行高效置換，能夠在一定程度上延長網絡的整體壽命。