張生鳳，王坤達，吳曉蓓

(1.中國船舶重工集團公司第七二三研究所，江蘇 揚州 225001； 2.南京理工大學 自動化學院，江蘇 南京 210094)

0 引 言

無線傳感器網絡的壽命通常會受到傳感器節(jié)點的生命周期的影響，而有限的能量供給和惡劣的工作環(huán)境又會導致傳感器節(jié)點的過早失效。因失效節(jié)點在拓撲中的所處位置不同，該失效對網絡的影響也不盡相同。根據網絡中數據傳輸的特性，失效節(jié)點會導致其本身傳遞的數據負載重新分配，可能會導致網絡中其余節(jié)點的負載增加而發(fā)生級聯失效[1]。

目前，級聯失效相關問題的主要研究方向還是復雜網絡[2-7]，其中最為典型的應用就是電力網絡[5-7]。文獻[2]針對物聯網中日益需求的面向服務計算，研究了服務節(jié)點可能出現的級聯失效問題，提出了一種基于新增服務節(jié)點的復雜網路容錯控制算法。Liu等[4]則充分考慮了失效節(jié)點鄰居節(jié)點的剩余能量，提出了一種時變的負載重新分配方法來降低級聯失效的影響。針對無線傳感器網絡相關的級聯失效問題研究多是圍繞網絡模型而展開，并有一些學者也在此基礎上提出了相關容錯策略[8-11]。Hu等[8]就對隨機網絡、無標度網絡、WS小世界網絡、NW小世界網絡4種模型下的級聯失效問題進行分析，通過仿真得出了無標度網絡模型在節(jié)點失效容忍方面比其它模型更為穩(wěn)定的結論。文獻[9]則通過構建無標度網絡模型，得出了節(jié)點的級聯失效臨界負載值，并在節(jié)點負載大于臨界時切斷相應鏈路來避免級聯失效的發(fā)生。然而，此類容錯研究往往對網絡初始部署節(jié)點的能量有所要求，而且對于網絡中已經出現節(jié)點失效的情況并不一定適用。

為此，本文針對無線傳感器網絡中單一節(jié)點失效導致的負載再分配問題，提出了一種基于時間容忍條件的單一節(jié)點失效修復策略(TTM based topology reconfiguration algorithm，TTM-TRA)。其中，節(jié)點失效的時間容忍條件(time tolerated manner，TTM)是基于傳統的級聯失效模型提出的。TTM-TRA屬于典型的反應式修復策略，并可分為失效節(jié)點的影響評估和修復節(jié)點的選擇調度兩個部分。該算法在檢測到節(jié)點失效后，通過判定網絡中其余節(jié)點對該節(jié)點失效是否容忍，并利用局部拓撲重構來緩解該失效造成的負載重新分配問題對其它節(jié)點的影響，能夠在一定程度上延長網絡的生命周期。

1 前提假設與基本定義

1.1 前提假設

為簡化本文后續(xù)的分析及討論，對網絡及節(jié)點做出以下幾點假設：

(1)網絡初始狀態(tài)為整體連通，各傳感器節(jié)點為同構，即具有相同的通信半徑R、硬件特性等，并且網絡中的節(jié)點都具備移動特性。

(2)正常運行過程中，網絡拓撲及數據路由保持不變，且網絡中的節(jié)點能夠以既定路由將數據傳輸至匯聚節(jié)點。

(3)網絡中各傳感器節(jié)點能夠獲知自己的位置，并且能夠獲知其兩跳內鄰居節(jié)點的相關信息，如容量、負載、剩余的能量、位置信息等。

(4)節(jié)點能夠將需要傳輸的數據量均勻地分配給所有路由方向上的子節(jié)點。

1.2 基本定義

考慮到無線傳感器網絡的級聯失效問題是由節(jié)點失效導致的負載再分配而形成，為便于本文后續(xù)內容的理解和說明，對涉及的特定名詞給出以下定義。

定義1 節(jié)點容量：節(jié)點的容量定義為網絡中節(jié)點所能承載的最大實時傳輸數據量，表示為C；

定義2 節(jié)點負載：節(jié)點的負載定義為節(jié)點實時傳輸的數據量，表示為L；

定義3 節(jié)點生命周期：節(jié)點的生命周期定義為節(jié)點由初始工作至失效的運行時間，表示為T。為了方便統計，本文中節(jié)點的生命周期計為該節(jié)點進行數據傳輸的次數；

定義4 父節(jié)點：在路由確定的網絡中，若數據由節(jié)點i傳輸至節(jié)點j，則節(jié)點i稱作節(jié)點j的父節(jié)點；

定義5 次級節(jié)點：在路由確定的網絡中，若節(jié)點j為節(jié)點i的子節(jié)點，且節(jié)點k是節(jié)點j的子節(jié)點，則稱節(jié)點k是節(jié)點i的次級節(jié)點；

定義6 同層節(jié)點：在路由確定的網絡中，若節(jié)點Aii=1,2,…,n擁有共同的父節(jié)點B，則稱節(jié)點Aii=1,2,…,n互為同層節(jié)點。

2 網絡模型及問題描述

2.1 節(jié)點通信能耗模型

本文研究基于時間容忍條件的節(jié)點失效修復問題，節(jié)點的負載重新分配和節(jié)點生命周期的重新計算是其中的兩個關鍵點，而這兩方面都與節(jié)點的通信能耗模型密切相關。目前，相關研究采用的節(jié)點通信能耗模型有多種，且各模型均有不同的側重。因為要針對節(jié)點的通信負載進行研究，故選用文獻[12]給出的節(jié)點通信能耗的評估模型

ξ(e)=ms×nh+tr

(1)

其中，ms為傳輸的數據量，nh為數據傳輸所需的跳數，tr為數據傳輸過程中偵聽和接收數據所需的時間。計算節(jié)點向1跳鄰居傳輸數據的能耗時，nh=1。為了進一步簡化分析，假設各節(jié)點的tr相同，節(jié)點通信能耗的評估模型可簡化為ξ(e)=ms。因此，本文假設節(jié)點的通信能耗與節(jié)點的數據傳輸量成正比，它們間的關系滿足下式

e=k*ms=k*L

(2)

其中，k為網絡中的特征常數，表示節(jié)點傳輸單位數據時的通信能耗，ms為節(jié)點傳輸的數據量，即節(jié)點的通信負載。

2.2 節(jié)點失效的時間容忍條件

本文主要基于無線傳感器網絡中目前已有的級聯失效的概念，提出了網絡對于節(jié)點失效的時間容忍條件，并在此基礎上完成了TTM-TRA算法的設計。下面結合圖1，簡要介紹級聯失效的概念。

圖1 級聯失效

(1)初始網絡中，節(jié)點V4的負載均勻地分配給它的3個子節(jié)點V2、V5、V6；

(2)若節(jié)點V5在t時刻失效，V4與V5之間的連通鏈路斷裂；V4節(jié)點的負載L4(t)將會重新分配給它的剩余子節(jié)點V2和V6，則此時V2和V6增加的負載為

(3)

(3)若節(jié)點V2的負載超過容量C，節(jié)點V2也會失效，進而導致節(jié)點V3再次進行負載重新分配。類似的負載再分配過程會持續(xù)進行，直至網絡整體連通斷裂或所有節(jié)點的負載均滿足Li(t)≤C(i為節(jié)點編號)。

由上述內容可以看出，級聯失效是指由初始部分節(jié)點失效而導致的后續(xù)一系列失效過程，通常是指節(jié)點負載超過其最大容量而失效的情況，然而失效節(jié)點負載重新分配的影響卻不僅限于此。總體來講，負載的重新分配會導致某些節(jié)點由于負載超過其容量直接失效，或導致節(jié)點的負載處于一個較高的狀態(tài)，大大縮減其生存周期。為此，本文給出了網絡中節(jié)點失效的時間容忍條件TTM，其具體定義如下：

若網絡中節(jié)點Vi在t時刻失效，網絡中其余節(jié)點Vjj∈1,…,N,j≠i在t時刻的負載、能耗以及剩余能量分別為Lj(t)、ej(t)、Ej(t)。結合節(jié)點的能耗模型可得節(jié)點的剩余的生命周期為

(4)

如上式所示，若Lj(t)>C，則節(jié)點Vj會由于瞬時負載超過其容量而直接失效。為了能夠較為全面地分析隨機節(jié)點失效對網絡中負載重新分配的影響，對網絡中其余節(jié)點Vjj∈1,…,N,j≠i設定特定的失效時間容忍閥值Tj。若tj≥Tj，則稱節(jié)點Vj能夠容忍節(jié)點Vi的失效；否則不能容忍，即表示為節(jié)點Vj將會直接受到由Vi失效的影響，立即或在較短時間內由于過高能耗而失效。

(1)若某節(jié)點C的路由方向上有兩個子節(jié)點，如圖2(a)中節(jié)點D和節(jié)點E。假設D點在t時刻失效，節(jié)點E的實時負載為

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

(5)

(2)若某節(jié)點C的路由方向上有3個子節(jié)點，如圖2(b)所示。假設D點在t時刻失效，節(jié)點E的實時負載為

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

(6)

以上兩式中，Lp表示由其余父節(jié)點分配至節(jié)點E的負載，LC為節(jié)點C的負載?？紤]較為理想的情況，設Lp=0且兩種情況均滿足LE(t)≤C，則在節(jié)點D失效之后，節(jié)點E的生命周期分別為失效之前時的1/2和2/3。再因為第一類情況中，節(jié)點D的失效會導致節(jié)點E變?yōu)楦铧c，所以本文設定常數α=2/3。

3 基于時間容忍條件的拓撲重構修復算法

TTM-TRA作為典型的反應式算法，其主要執(zhí)行步驟可以分為兩個部分。首先是對失效節(jié)點的影響進行衡量和評估，判斷其失效是否會導致網絡中其余節(jié)點的生命周期不能滿足時間容忍條件，這個步驟可以在網絡拓撲形成之后通過具體計算得到；其次是修復節(jié)點的選擇，若該節(jié)點的失效會導致其余節(jié)點受到較為嚴重的影響，則需要對該節(jié)點的失效進行修復，如何選擇最合理的移動節(jié)點進行修復也需要進行討論。

3.1 失效節(jié)點的影響評估

由前提假設(3)可知，每個傳感器節(jié)點能夠獲知其兩跳鄰居的信息，則每個節(jié)點Vi就能得到其路由方向的父節(jié)點Vj以及Vj的其余子節(jié)點的狀態(tài)參數。若節(jié)點Vj的實時負載為Lj且路由方向上子節(jié)點的個數為γ，則僅由節(jié)點Vj分配至其路由子節(jié)點的負載可以表示為Lj/γ。因此，某一節(jié)點隨機失效會導致其父節(jié)點的路由子節(jié)點總數發(fā)生變化，進而會導致其同層節(jié)點的負載直接發(fā)生改變。

節(jié)點失效而導致的負載變化可能會波及到整個網絡，但是遭受最為直接影響的是失效節(jié)點的路由子節(jié)點及其同層節(jié)點。通常情況下，失效節(jié)點路由子節(jié)點的負載都不會隨著該節(jié)點的失效而增大。為了能夠更為直接分析TTM在節(jié)點失效后的作用機制，本文主要針對失效節(jié)點的同層節(jié)點展開分析。

如前文所述，負載再分配除可能直接導致網絡中部分節(jié)點的負載超過容量之外，還可能使部分節(jié)點工作在高額負載并且極大縮短其生命周期。下面結合TTM，將網絡中失效節(jié)點的情況分為以下3類：

(1)失效節(jié)點為割點。這是一類特殊情況，也為目前相關研究的重點，失效節(jié)點必須修復。

(2)節(jié)點失效會導致網絡中其余節(jié)點出現過容情況。網絡中存在其余節(jié)點的實時負載超過其本身容量，失效節(jié)點需要修復。

(3)節(jié)點失效會導致網絡中其余節(jié)點出現高額負載情況。這種情況會導致網絡中存在部分節(jié)點由于較高負載而過早失效。

除針對割點的第一類特殊情況需要對節(jié)點位置進行分析之外，第二、三類節(jié)點的失效都需要對網絡中其余節(jié)點的實時負載進行計算，并需要結合TTM判斷該失效是否能被容忍。

網絡正常運行過程中，各節(jié)點之間可以通過定期的“heartbeat”信息交互確認自身工作狀態(tài)，并將是否丟失這種信息用作判斷節(jié)點是否失效的依據。設定某個連續(xù)丟失兩周期“heartbeat”信息的節(jié)點為失效節(jié)點，一旦檢測到某一節(jié)點的失效，該失效節(jié)點影響的評估策略開始執(zhí)行。針對以上3種失效節(jié)點的分類，失效節(jié)點影響的評估主要分為兩個步驟：

(1)首先，進行失效節(jié)點是否為割點的判斷。有關割點的判斷目前有很多成熟的方法，其中最為經典的就是利用深度優(yōu)先搜索算法(deep first search，DFS)。然而，DFS算法需要進行全局搜索且開銷巨大，故依據文獻[13]所提出的分布式CAM算法進行割點的判斷。CAM算法是一種近似判定方法，它通過設置節(jié)點與其關聯的通信鏈路編號，能夠較為準確地進行割點的判斷，且通信復雜度僅為On(n為網絡中的節(jié)點數)。

(2)其次，若失效節(jié)點不屬于割點，則需通過TTM判斷該失效是否會被容忍。如該失效無法容忍才進行修復。具體的判斷分為兩個步驟：首先，直接判斷失效節(jié)點的同層節(jié)點中是否有節(jié)點的負載超過其容量；其次，在節(jié)點負載并未溢出的前提下，對失效節(jié)點的同層節(jié)點進行實時的剩余生命周期計算，并與同等能量條件、負載未變化的情況下的理論剩余生命周期作比較，判斷TTM是否成立

(7)

其中，et-1和e(t)分別表示在t時刻，節(jié)點失效前后該同層節(jié)點的單輪次數據傳輸能耗，E(t)表示t時刻節(jié)點的剩余能量。若失效發(fā)生前后該節(jié)點的理論生命周期間的關系滿足上式，則該失效可以容忍，不需要執(zhí)行修復策略。若無法容忍，則該失效節(jié)點需要進行修復。

3.2 修復節(jié)點的選擇

TTM-TRA算法主要基于網絡中節(jié)點的移動特性，選取最佳的修復節(jié)點移動至失效節(jié)點位置，并替代其在網絡中的作用。與已有的相關研究不同，TTM-TRA中的修復節(jié)點并不能直接從失效節(jié)點的鄰居節(jié)點中挑選。這是因為，TTM更加關注節(jié)點之間數據傳輸的相對關系，失效節(jié)點的通信鄰居中也可能存在關鍵節(jié)點，所以不能直接通過距離等因素進行修復節(jié)點的選擇。下面將從兩個方面來討論如何進行修復節(jié)點的選擇，首先是確定修復節(jié)點的選擇范圍；其次是設定合理修復節(jié)點選擇的優(yōu)先權值，完成多數備選節(jié)點中最佳的選擇。

3.2.1 修復節(jié)點的選擇范圍

因為修復節(jié)點的移動應當被視作在原位置的失效，所以修復節(jié)點的選擇應該滿足以下兩個基本條件：

(1)修復節(jié)點不能是割點，否則其移動會導致網絡連通性破壞；

(2)修復節(jié)點的移動應當能夠被其余節(jié)點所容忍，否則該修復過程會帶來新的失效問題。

下面結合定理1和定理2，對修復節(jié)點的可選范圍進行確定。

定理1 若某一節(jié)點的失效無法滿足TTM，那么該失效節(jié)點的同層節(jié)點不能被選作修復節(jié)點。

證明：由前提假設可知，失效節(jié)點及其同層節(jié)點的負載是由路由父節(jié)點均勻分配的，而移動失效節(jié)點的同層節(jié)點進行修復后，其路由父節(jié)點的剩余子節(jié)點數并不會改變。因此，若失效節(jié)點無法滿足TTM，它的同層節(jié)點不能被選作該失效的修復節(jié)點。

定理2 在不考慮節(jié)點負載超過容量的前提下，若網絡中某一節(jié)點擁有超過3個子節(jié)點時，則該節(jié)點任一子節(jié)點的失效能夠滿足TTM。

證明：因為假設時間容忍閥值中特征常數α=2/3，結合2.2小節(jié)的論述，定理2顯然得證。

因為選擇失效節(jié)點的1跳鄰居作為修復節(jié)點，可以大大節(jié)省修復節(jié)點移動時的能量消耗，所以失效節(jié)點的1跳鄰居仍是修復節(jié)點的最佳選擇范圍。由于節(jié)點的1跳鄰居中可能包含多個路由關系，還需對其中的一些特殊情況加以說明。首先，雖然失效節(jié)點的路由父節(jié)點是其1跳鄰居，但是路由父節(jié)點的移動將會導致更大范圍的負載再分配，所以不能被選作修復節(jié)點。其次，由定理1可以明顯看出，若失效節(jié)點無法滿足TTM，該失效節(jié)點的同層節(jié)點通常不能被選作修復節(jié)點。由此可以得到，失效節(jié)點的路由子節(jié)點可以作為修復節(jié)點的備選范圍。

定理2說明了在失效節(jié)點具有3個或3個以上路由子節(jié)點的情況下，選擇其中的任何一個節(jié)點作為修復節(jié)點都能夠滿足TTM。若失效節(jié)點的路由子節(jié)點數無法滿足上述條件，則就需要在失效節(jié)點的非1跳鄰居中選擇修復節(jié)點。因此，在這種情況下，修復節(jié)點的選擇范圍需要擴大至失效節(jié)點的次級節(jié)點。

下面結合圖例對修復節(jié)點的可選范圍進行簡要說明。如圖3(a)所示，若圖中節(jié)點C失效，其路由子節(jié)點D、E、F都可以作為修復節(jié)點的備選節(jié)點。如圖3(b)所示，若圖中節(jié)點C失效，其路由子節(jié)點D、E的移動無法滿足TTM，而節(jié)點D的子節(jié)點F、G、H可以作為修復節(jié)點的備選節(jié)點。

圖3 失效節(jié)點的修復節(jié)點選擇范圍

3.2.2 修復節(jié)點選擇的優(yōu)先權值

除上述的基本條件外，仍需要在選取修復節(jié)點時綜合考慮備選節(jié)點距離失效節(jié)點的距離d和節(jié)點的剩余能量E。因為節(jié)點在移動過程中需要耗費一定的能量，所以越短的移動距離越能夠減小節(jié)點在移動過程中的消耗，從而使其在修復結束之后能夠保留較多的能量；另一方面，節(jié)點的剩余能量也是影響節(jié)點生命周期的直接因素，較高的剩余能量也能夠保證其在執(zhí)行修復步驟之后能維持較長時間的穩(wěn)定工作。因此，下面給出了修復節(jié)點選擇的優(yōu)先權值定義

(8)

式中：E表示備選節(jié)點的剩余能量，d表示備選節(jié)點與失效節(jié)點之間的距離，β為0-1之間的一個固定常數(設定為0.5)，P則表示節(jié)點被選作修復節(jié)點的優(yōu)先權值。在確定修復節(jié)點的可選范圍之后，可以通過計算各個備選節(jié)點對應的優(yōu)先權值，完成最優(yōu)修復節(jié)點的選擇。

考慮到修復節(jié)點需要移動至失效節(jié)點處，所以移動節(jié)點剩余能量與其相距失效節(jié)點之間的距離還需要滿足一個基本條件，E≥γd(γ表示節(jié)點移動單位距離的能耗)。因此，可以通過對可選范圍內的每個傳感器節(jié)點，進行類似自檢程序的初步計算來進一步縮小修復節(jié)點的可選范圍。

3.3 TTM-TRA算法執(zhí)行流程

綜上所述，TTM-TRA算法的執(zhí)行流程可以歸納如圖4所示，主要包括失效節(jié)點的檢測發(fā)現、失效節(jié)點的影響判斷、修復節(jié)點的選擇這3個主要步驟。與目前單一節(jié)點失效修復的相關研究類似，TTM-TRA算法中的割點失效依舊具有最高優(yōu)先級，而對非割點失效的情況才會進行其它節(jié)點的TTM容忍性判斷。

圖4 TTM-TRA算法執(zhí)行流程

下面結合圖例，對TTM-TRA算法執(zhí)行前后的網絡拓撲進行分析對比。圖5(a)為網絡的初始拓撲，節(jié)點A有3個路由子節(jié)點B、C、D。若節(jié)點A失效，節(jié)點B、C、D都在修復節(jié)點的可選擇范圍內。首先，判定節(jié)點A不是割點，但是它的失效無法滿足時間容忍條件TTM，因此需要進行修復節(jié)點的選擇。其次，失效節(jié)點A的3個路由子節(jié)點中僅有節(jié)點B、D滿足修復節(jié)點的選擇條件，若通過計算這兩個節(jié)點的選擇優(yōu)先權值，最終得到PD>PB，則可以判定最優(yōu)修復節(jié)點為節(jié)點D。最后，節(jié)點D移動至失效節(jié)點A的位置，并且分別建立節(jié)點D與節(jié)點C、節(jié)點B之間的連通鏈路，修復之后的網絡拓撲如圖5(b)所示。

3.4 算法性能分析

TTM-TRA算法的通信開銷并不大，而且主要集中在失效節(jié)點影響評估以及修復節(jié)點選擇范圍確定的過程中。首先，失效節(jié)點的影響評估依賴于CAM算法及與失效節(jié)點能否滿足TTM的判定過程，其中由文獻[13]中的分析可以得到CAM算法的通信復雜度在通常網絡中可以表示為On；而相關節(jié)點的失效容忍判定僅需要進行兩跳內的一次交互通信傳輸，其通信過程的復雜度可以表示為On。其次，修復節(jié)點的選擇范圍設定為失效節(jié)點的兩跳內的路由子節(jié)點，而可選修復節(jié)點的判定則依賴于各節(jié)點本身狀態(tài)信息的傳輸，該過程的通信復雜度也為On。綜上所述，TTM-TRA算法的通信復雜度可以表示為O(n)，

圖5 TTM-TRA修復前后網絡拓撲圖

n表示網絡中節(jié)點的數量。

通過設定時間容忍閥值中特征常數α的不同取值，可以反映出修復算法對節(jié)點失效的不同容忍程度。比如，設定α=2/3，就表示在不考慮附加負載的情況下，失效節(jié)點至少有兩個同層節(jié)點時該失效才能被容忍；若設定α=1/2，失效節(jié)點至少有一個同層節(jié)點時該失效才能被容忍，這與 “二元點割集”的相關討論也有所關聯。因為修復節(jié)點的選擇范圍僅為失效節(jié)點的兩跳鄰居，TTM-TRA算法的執(zhí)行要求失效節(jié)點擁有一定數目的路由子節(jié)點或者次級節(jié)點，所以它比較適用于節(jié)點分布相對密集的網絡。

4 仿真分析

4.1 仿真參數設定

本部分對TTM-TRA算法進行了仿真設計，旨在對路由確定網絡中出現的單一節(jié)點失效的影響進行分析，并在此基礎上完成對該失效的合理修復，避免直接或間接式的級聯失效發(fā)生，在一定程度上延長網絡中其余部分節(jié)點的生命周期。仿真在同等條件下，將TTM-TRA與RIM算法進行了部分參數的對比，因為相較于DARA算法，RIM并不局限于割點的失效修復問題，而且TTM-TRA針對的失效節(jié)點范圍也相對寬泛?？紤]到節(jié)點失效的時間容忍條件是從節(jié)點的生命周期的角度進行分析，所以仿真將各修復算法所需的修復節(jié)點數、修復節(jié)點移動總距離以及相應節(jié)點的剩余生命周期進行對比：

(1)修復節(jié)點數：指完成修復所需移動的修復節(jié)點數量，直接反映了修復算法造成的拓撲重構規(guī)模。

(2)修復節(jié)點移動總距離：指所有修復節(jié)點的移動距離之和。TTM-TRA算法利用節(jié)點的移動特性完成失效節(jié)點的修復，而節(jié)點移動過程耗能都相對較大，所以修復節(jié)點的移動總距離能夠在一定程度上反映出算法在實際執(zhí)行過程中的開銷。

(3)相應節(jié)點的剩余生命周期：指修復完成后，之前受到失效影響節(jié)點的剩余生命周期。節(jié)點失效導致的負載重新分配會直接影響部分節(jié)點的生命周期，該參數能夠在一定程度上反映TTM-TRA算法的有效性。因此，相應節(jié)點的剩余生命周期是衡量TTM-TRA算法效果的一個重要指標。

TTM-TRA算法的仿真設計均基于Matlab 2010b平臺，主要的仿真參數見表1。此外，仿真設定網絡為樹形結構，且各個節(jié)點能夠按照既定的路由進行數據傳輸?？紤]到算法在設計過程中涉及了兩個特征參數的選?。簳r間容忍閥值α和修復節(jié)點優(yōu)先權值的選擇參數β，因此仿真設計對這兩個參數的選擇不同也進行了相應的對比。

表1 仿真參數設定

4.2 修復所需節(jié)點數

TTM-TRA算法與RIM算法有著本質的區(qū)別，RIM采用的是“向心收縮”的修復算法，而TTM-TRA則是與DARA類似，單一節(jié)點失效通常會在1跳鄰居內選擇最優(yōu)的修復節(jié)點進行直接修復。在涉及到某些特殊情況時(如1跳鄰居內沒有可選修復節(jié)點)，需要采用多節(jié)點級聯移動的方式，從而會導致部分仿真所需節(jié)點數上升。本部分共進行兩組仿真，分別從固定初始網絡節(jié)點規(guī)模和固定節(jié)點通信半徑的角度出發(fā)。第一組設定初始網絡節(jié)點數由200至400變化，節(jié)點的通信半徑設定為50 m；第二組設定初始傳感器節(jié)點數為300，節(jié)點的通信半徑由30 m至50 m變化。仿真數據均為50次迭代的平均值，并且仿真也討論了時間容忍閥值中特征參數α的取值對結果的影響。兩組仿真條件下，最終得到的修復所需移動節(jié)點數目對比分別如圖6(a)和圖6(b)所示，其中TTM-TRA(I)和TTM-TRA(II)分別表示了α=2/3和α=1/2時的修復算法。

圖6 所需修復節(jié)點數隨網絡參數變化關系

由圖6(a)可以看出，RIM算法在修復單一節(jié)點失效時需要移動較多的節(jié)點，而且所需修復節(jié)點的數目會隨著網絡規(guī)模的增大而增大，因為其修復所需移動節(jié)點數與失效節(jié)點的1跳鄰居節(jié)點數有直接的聯系。而TTM-TRA算法在完成修復時所需節(jié)點數相對較小，基本能夠維持在2以內。隨著網絡初始部署的節(jié)點數逐漸增多，節(jié)點部署逐漸密集，修復節(jié)點可能直接由失效節(jié)點的1跳路由子節(jié)點中選出，所以修復所需節(jié)點數會隨著網絡規(guī)模的逐漸增大有一定的減少。通過對比TTM-TRA(I)和TTM-TRA(II)的曲線還可以看出，隨著α取值的增大，修復節(jié)點所需滿足的要求愈加苛刻，可能需要在失效節(jié)點的次級節(jié)點中選擇修復節(jié)點，因此修復所需節(jié)點數會相對較大。

圖6(b)顯示了修復所需節(jié)點數與節(jié)點通信半徑間的對應關系。隨著節(jié)點通信半徑逐漸增大，初始網絡中的節(jié)點分布越來越密集，失效節(jié)點的路由子節(jié)點會逐漸增多，能夠基本保證僅需要移動一個路由子節(jié)點就完成修復。所以，節(jié)點的通信半徑逐漸增大時，所需移動的修復節(jié)點數會逐漸收斂到1。由圖中可以看出，TTM-TRA算法在節(jié)點通信半徑為50 m時，基本僅需移動一個節(jié)點就能完成修復。與網絡初始節(jié)點數變化時類似，在α=2/3的情況下，TTM-TRA算法所需的修復節(jié)點數與α=1/2時相比也較少。而RIM則與之相反，隨著網絡中節(jié)點分布的逐漸密集，失效節(jié)點的1跳鄰居節(jié)點數增加，直接會導致其需要移動較多的修復節(jié)點。

4.3 修復節(jié)點移動總距離

本小節(jié)設計了兩組不同的仿真環(huán)境，分別對修復節(jié)點移動總距離與初始網絡中節(jié)點數目、節(jié)點通信半徑之間的關系進行了討論。第一組設定節(jié)點通信半徑為50 m，初始節(jié)點數由200至400變化；第二組設定網絡初始節(jié)點數為300，節(jié)點通信半徑由30 m變化至50 m。仿真數據均為50次迭代的平均值，并且仿真也討論了時間容忍閥值中特征參數α的取值對結果的影響。兩組仿真條件下，最終得到的修復節(jié)點移動總距離對比結果分別如圖7(a)和圖7(b)所示，其中TTM-TRA(I)和TTM-TRA(II)分別表示了α=2/3和α=1/2時的修復算法。

由圖7(a)可以看出，RIM算法因為需要移動較多節(jié)點完成修復，所以節(jié)點的總體移動距離會比TTM-TRA算法大。此外，隨著初始部署節(jié)點數增多，失效節(jié)點的1跳鄰居數也可能增多，RIM算法修復節(jié)點的移動總距離也會呈現上升趨勢。在網絡初始部署節(jié)點數達到300時，RIM算法中修復節(jié)點移動總距離會出現略微的下降。這可能是因為，隨著網絡中的節(jié)點越來越密集，雖然移動的節(jié)點總數增加，但是單個節(jié)點需要移動的距離會有所下降，所有節(jié)點的移動總距離也可能出現略微下降。與之相比，TTM-TRA算法由于通常僅需要移動一個修復節(jié)點，而節(jié)點之間的距離會隨著網絡初始部署節(jié)點增多而減小，所以修復節(jié)點移動的距離總體會呈現一個下降趨勢。然而，在α取2/3時，修復節(jié)點的可選范圍會比α取1/2時小，所以TTM-TRA(I)算法所需的修復節(jié)點移動總距離會比TTM-TRA(II)算法小。

圖7 修復節(jié)點移動總距離隨網絡參數變化關系

圖7(b)顯示了修復節(jié)點移動總距離與節(jié)點通信半徑間的變化曲線。由圖中可以看出，RIM算法中修復節(jié)點移動總距離會隨著節(jié)點通信半徑的變大而明顯上升。由于TTM-TRA算法中的修復節(jié)點能夠在失效節(jié)點的路由子節(jié)點和次級節(jié)點中獲得，所以修復節(jié)點的移動總數不會很大，修復節(jié)點的移動總距離也僅會隨著節(jié)點通信半徑的變大而略微增大。就修復算法所需移動節(jié)點數目和節(jié)點移動的總距離來講，雖然TTM-TRA算法會比RIM算法有著一定的優(yōu)勢，然而在節(jié)點的平均移動距離方面，RIM會表現得更好。

4.4 相應節(jié)點剩余生命周期對比

若網絡中出現單一節(jié)點失效，則失效節(jié)點的同層節(jié)點將會直接受到負載重新分配的影響，節(jié)點的生命周期可能會有所下降。對失效節(jié)點的同層節(jié)點剩余生命周期進行分析，能夠反映出TTM-TRA算法能否有效地減小負載再分配的負面影響。假設節(jié)點每輪采集數據量為10 bit，節(jié)點的容量為400 bit，單位數據傳輸能耗為200 nJ/bit，并且設定α=2/3。為了簡要說明算法的可行性，此處將節(jié)點接收和發(fā)送的數據量視作近似相等。仿真選取了兩類情況分別分析了節(jié)點失效與修復時的剩余生命周期對比。其中，第一類情況為失效節(jié)點存在2個同層節(jié)點，第二類情況為失效節(jié)點存在1個同層節(jié)點。仿真結果分別如圖8(a)、圖8(b)所示。

圖8(a)中的“Node 1、Node 2”分別表示了失效節(jié)點的兩個同層節(jié)點，圖8(b)中的“Node 1”表示了失效節(jié)點的一個同層節(jié)點。兩種情況下，修復節(jié)點在完成修復后，生命周期是有較為明顯的下降，因為移動消耗掉了它相當部分的能量。理論上，當失效節(jié)點被修復時，失效節(jié)點同層節(jié)點的生命周期應該上升至修復前的3/2。圖8(a)中的“Node 1”在修復前后生命周期上升幅度并沒有達到理想值，因為其本身的負載可能來自多個父節(jié)點。由圖8(b)中可以看出，當失效節(jié)點僅有1個同層節(jié)點時，該節(jié)點的剩余生命周期在失效節(jié)點修復后會上升到修復前的3/2。

圖8 兩類情況修復前后同層節(jié)點的剩余周期變化

總體而言，節(jié)點失效時間容忍條件中α的取值相當關鍵，它直接決定了TTM-TRA算法需要針對的失效節(jié)點以及修復節(jié)點的可選情況。本章中設定α=2/3，實際是約束了失效節(jié)點具有2個或2個以下同層節(jié)點的情況，而對于它具有更多同層節(jié)點的情況并不會執(zhí)行修復。若需要基于時間容忍條件對不同類型的節(jié)點失效情況進行處理，則可以根據網絡需求對α的實際取值進行相應調整，α的取值越大，時間容忍條件對失效節(jié)點的約束越苛刻。

5 結束語

本文針對節(jié)點失效導致的負載再分配問題，提出了一種單一節(jié)點失效的拓撲重構式修復策略TTM-TRA。該修復策略在節(jié)點級聯失效模型的基礎上提出了節(jié)點失效的時間容忍條件，并通過失效節(jié)點同層節(jié)點的生命周期的計算判定失效節(jié)點的影響。時間容忍條件的使用取決于容忍閥值中特征常數α的取值，α的數值越大可以認為失效節(jié)點容忍條件越為苛刻。通過設定時間容忍閥值的特征參數為α=2/3，能夠保證TTM-TRA算法對同層節(jié)點數不超過2的失效節(jié)點進行有效修復。由仿真分析可以看出，TTM-TRA算法實際是將修復節(jié)點的部分生命周期與失效節(jié)點的同層節(jié)點進行高效置換，能夠在一定程度上延長網絡的整體壽命。