時(shí)間容忍條件下無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)失效修復(fù)

張生鳳，王坤達(dá)，吳曉蓓

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

0 引 言

無線傳感器網(wǎng)絡(luò)的壽命通常會(huì)受到傳感器節(jié)點(diǎn)的生命周期的影響，而有限的能量供給和惡劣的工作環(huán)境又會(huì)導(dǎo)致傳感器節(jié)點(diǎn)的過早失效。因失效節(jié)點(diǎn)在拓?fù)渲械乃幬恢貌煌?，該失效?duì)網(wǎng)絡(luò)的影響也不盡相同。根據(jù)網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)奶匦?，失效?jié)點(diǎn)會(huì)導(dǎo)致其本身傳遞的數(shù)據(jù)負(fù)載重新分配，可能會(huì)導(dǎo)致網(wǎng)絡(luò)中其余節(jié)點(diǎn)的負(fù)載增加而發(fā)生級(jí)聯(lián)失效[1]。

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

為此，本文針對(duì)無線傳感器網(wǎng)絡(luò)中單一節(jié)點(diǎn)失效導(dǎo)致的負(fù)載再分配問題，提出了一種基于時(shí)間容忍條件的單一節(jié)點(diǎn)失效修復(fù)策略(TTM based topology reconfiguration algorithm，TTM-TRA)。其中，節(jié)點(diǎn)失效的時(shí)間容忍條件(time tolerated manner，TTM)是基于傳統(tǒng)的級(jí)聯(lián)失效模型提出的。TTM-TRA屬于典型的反應(yīng)式修復(fù)策略，并可分為失效節(jié)點(diǎn)的影響評(píng)估和修復(fù)節(jié)點(diǎn)的選擇調(diào)度兩個(gè)部分。該算法在檢測(cè)到節(jié)點(diǎn)失效后，通過判定網(wǎng)絡(luò)中其余節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)失效是否容忍，并利用局部拓?fù)渲貥?gòu)來緩解該失效造成的負(fù)載重新分配問題對(duì)其它節(jié)點(diǎn)的影響，能夠在一定程度上延長網(wǎng)絡(luò)的生命周期。

1 前提假設(shè)與基本定義

1.1 前提假設(shè)

為簡(jiǎn)化本文后續(xù)的分析及討論，對(duì)網(wǎng)絡(luò)及節(jié)點(diǎn)做出以下幾點(diǎn)假設(shè)：

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

(2)正常運(yùn)行過程中，網(wǎng)絡(luò)拓?fù)浼皵?shù)據(jù)路由保持不變，且網(wǎng)絡(luò)中的節(jié)點(diǎn)能夠以既定路由將數(shù)據(jù)傳輸至匯聚節(jié)點(diǎn)。

(3)網(wǎng)絡(luò)中各傳感器節(jié)點(diǎn)能夠獲知自己的位置，并且能夠獲知其兩跳內(nèi)鄰居節(jié)點(diǎn)的相關(guān)信息，如容量、負(fù)載、剩余的能量、位置信息等。

(4)節(jié)點(diǎn)能夠?qū)⑿枰獋鬏數(shù)臄?shù)據(jù)量均勻地分配給所有路由方向上的子節(jié)點(diǎn)。

1.2 基本定義

考慮到無線傳感器網(wǎng)絡(luò)的級(jí)聯(lián)失效問題是由節(jié)點(diǎn)失效導(dǎo)致的負(fù)載再分配而形成，為便于本文后續(xù)內(nèi)容的理解和說明，對(duì)涉及的特定名詞給出以下定義。

定義1 節(jié)點(diǎn)容量：節(jié)點(diǎn)的容量定義為網(wǎng)絡(luò)中節(jié)點(diǎn)所能承載的最大實(shí)時(shí)傳輸數(shù)據(jù)量，表示為C；

定義2 節(jié)點(diǎn)負(fù)載：節(jié)點(diǎn)的負(fù)載定義為節(jié)點(diǎn)實(shí)時(shí)傳輸?shù)臄?shù)據(jù)量，表示為L；

定義3 節(jié)點(diǎn)生命周期：節(jié)點(diǎn)的生命周期定義為節(jié)點(diǎn)由初始工作至失效的運(yùn)行時(shí)間，表示為T。為了方便統(tǒng)計(jì)，本文中節(jié)點(diǎn)的生命周期計(jì)為該節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸?shù)拇螖?shù)；

定義4 父節(jié)點(diǎn)：在路由確定的網(wǎng)絡(luò)中，若數(shù)據(jù)由節(jié)點(diǎn)i傳輸至節(jié)點(diǎn)j，則節(jié)點(diǎn)i稱作節(jié)點(diǎn)j的父節(jié)點(diǎn)；

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

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

2 網(wǎng)絡(luò)模型及問題描述

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

本文研究基于時(shí)間容忍條件的節(jié)點(diǎn)失效修復(fù)問題，節(jié)點(diǎn)的負(fù)載重新分配和節(jié)點(diǎn)生命周期的重新計(jì)算是其中的兩個(gè)關(guān)鍵點(diǎn)，而這兩方面都與節(jié)點(diǎn)的通信能耗模型密切相關(guān)。目前，相關(guān)研究采用的節(jié)點(diǎn)通信能耗模型有多種，且各模型均有不同的側(cè)重。因?yàn)橐槍?duì)節(jié)點(diǎn)的通信負(fù)載進(jìn)行研究，故選用文獻(xiàn)[12]給出的節(jié)點(diǎn)通信能耗的評(píng)估模型

ξ(e)=ms×nh+tr

(1)

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

e=k*ms=k*L

(2)

其中，k為網(wǎng)絡(luò)中的特征常數(shù)，表示節(jié)點(diǎn)傳輸單位數(shù)據(jù)時(shí)的通信能耗，ms為節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量，即節(jié)點(diǎn)的通信負(fù)載。

2.2 節(jié)點(diǎn)失效的時(shí)間容忍條件

本文主要基于無線傳感器網(wǎng)絡(luò)中目前已有的級(jí)聯(lián)失效的概念，提出了網(wǎng)絡(luò)對(duì)于節(jié)點(diǎn)失效的時(shí)間容忍條件，并在此基礎(chǔ)上完成了TTM-TRA算法的設(shè)計(jì)。下面結(jié)合圖1，簡(jiǎn)要介紹級(jí)聯(lián)失效的概念。

圖1 級(jí)聯(lián)失效

(1)初始網(wǎng)絡(luò)中，節(jié)點(diǎn)V4的負(fù)載均勻地分配給它的3個(gè)子節(jié)點(diǎn)V2、V5、V6；

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

(3)

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

由上述內(nèi)容可以看出，級(jí)聯(lián)失效是指由初始部分節(jié)點(diǎn)失效而導(dǎo)致的后續(xù)一系列失效過程，通常是指節(jié)點(diǎn)負(fù)載超過其最大容量而失效的情況，然而失效節(jié)點(diǎn)負(fù)載重新分配的影響卻不僅限于此?？傮w來講，負(fù)載的重新分配會(huì)導(dǎo)致某些節(jié)點(diǎn)由于負(fù)載超過其容量直接失效，或?qū)е鹿?jié)點(diǎn)的負(fù)載處于一個(gè)較高的狀態(tài)，大大縮減其生存周期。為此，本文給出了網(wǎng)絡(luò)中節(jié)點(diǎn)失效的時(shí)間容忍條件TTM，其具體定義如下：

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

(4)

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

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

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

(5)

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

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

(6)

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

3 基于時(shí)間容忍條件的拓?fù)渲貥?gòu)修復(fù)算法

TTM-TRA作為典型的反應(yīng)式算法，其主要執(zhí)行步驟可以分為兩個(gè)部分。首先是對(duì)失效節(jié)點(diǎn)的影響進(jìn)行衡量和評(píng)估，判斷其失效是否會(huì)導(dǎo)致網(wǎng)絡(luò)中其余節(jié)點(diǎn)的生命周期不能滿足時(shí)間容忍條件，這個(gè)步驟可以在網(wǎng)絡(luò)拓?fù)湫纬芍笸ㄟ^具體計(jì)算得到；其次是修復(fù)節(jié)點(diǎn)的選擇，若該節(jié)點(diǎn)的失效會(huì)導(dǎo)致其余節(jié)點(diǎn)受到較為嚴(yán)重的影響，則需要對(duì)該節(jié)點(diǎn)的失效進(jìn)行修復(fù)，如何選擇最合理的移動(dòng)節(jié)點(diǎn)進(jìn)行修復(fù)也需要進(jìn)行討論。

3.1 失效節(jié)點(diǎn)的影響評(píng)估

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

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

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

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

(2)節(jié)點(diǎn)失效會(huì)導(dǎo)致網(wǎng)絡(luò)中其余節(jié)點(diǎn)出現(xiàn)過容情況。網(wǎng)絡(luò)中存在其余節(jié)點(diǎn)的實(shí)時(shí)負(fù)載超過其本身容量，失效節(jié)點(diǎn)需要修復(fù)。

(3)節(jié)點(diǎn)失效會(huì)導(dǎo)致網(wǎng)絡(luò)中其余節(jié)點(diǎn)出現(xiàn)高額負(fù)載情況。這種情況會(huì)導(dǎo)致網(wǎng)絡(luò)中存在部分節(jié)點(diǎn)由于較高負(fù)載而過早失效。

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

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

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

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

(7)

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

3.2 修復(fù)節(jié)點(diǎn)的選擇

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

3.2.1 修復(fù)節(jié)點(diǎn)的選擇范圍

因?yàn)樾迯?fù)節(jié)點(diǎn)的移動(dòng)應(yīng)當(dāng)被視作在原位置的失效，所以修復(fù)節(jié)點(diǎn)的選擇應(yīng)該滿足以下兩個(gè)基本條件：

(1)修復(fù)節(jié)點(diǎn)不能是割點(diǎn)，否則其移動(dòng)會(huì)導(dǎo)致網(wǎng)絡(luò)連通性破壞；

(2)修復(fù)節(jié)點(diǎn)的移動(dòng)應(yīng)當(dāng)能夠被其余節(jié)點(diǎn)所容忍，否則該修復(fù)過程會(huì)帶來新的失效問題。

下面結(jié)合定理1和定理2，對(duì)修復(fù)節(jié)點(diǎn)的可選范圍進(jìn)行確定。

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

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

定理2 在不考慮節(jié)點(diǎn)負(fù)載超過容量的前提下，若網(wǎng)絡(luò)中某一節(jié)點(diǎn)擁有超過3個(gè)子節(jié)點(diǎn)時(shí)，則該節(jié)點(diǎn)任一子節(jié)點(diǎn)的失效能夠滿足TTM。

證明：因?yàn)榧僭O(shè)時(shí)間容忍閥值中特征常數(shù)α=2/3，結(jié)合2.2小節(jié)的論述，定理2顯然得證。

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

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

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

圖3 失效節(jié)點(diǎn)的修復(fù)節(jié)點(diǎn)選擇范圍

3.2.2 修復(fù)節(jié)點(diǎn)選擇的優(yōu)先權(quán)值

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

(8)

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

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

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

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

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

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

3.4 算法性能分析

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

圖5 TTM-TRA修復(fù)前后網(wǎng)絡(luò)拓?fù)鋱D

n表示網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量。

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

4 仿真分析

4.1 仿真參數(shù)設(shè)定

本部分對(duì)TTM-TRA算法進(jìn)行了仿真設(shè)計(jì)，旨在對(duì)路由確定網(wǎng)絡(luò)中出現(xiàn)的單一節(jié)點(diǎn)失效的影響進(jìn)行分析，并在此基礎(chǔ)上完成對(duì)該失效的合理修復(fù)，避免直接或間接式的級(jí)聯(lián)失效發(fā)生，在一定程度上延長網(wǎng)絡(luò)中其余部分節(jié)點(diǎn)的生命周期。仿真在同等條件下，將TTM-TRA與RIM算法進(jìn)行了部分參數(shù)的對(duì)比，因?yàn)橄噍^于DARA算法，RIM并不局限于割點(diǎn)的失效修復(fù)問題，而且TTM-TRA針對(duì)的失效節(jié)點(diǎn)范圍也相對(duì)寬泛。考慮到節(jié)點(diǎn)失效的時(shí)間容忍條件是從節(jié)點(diǎn)的生命周期的角度進(jìn)行分析，所以仿真將各修復(fù)算法所需的修復(fù)節(jié)點(diǎn)數(shù)、修復(fù)節(jié)點(diǎn)移動(dòng)總距離以及相應(yīng)節(jié)點(diǎn)的剩余生命周期進(jìn)行對(duì)比：

(1)修復(fù)節(jié)點(diǎn)數(shù)：指完成修復(fù)所需移動(dòng)的修復(fù)節(jié)點(diǎn)數(shù)量，直接反映了修復(fù)算法造成的拓?fù)渲貥?gòu)規(guī)模。

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

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

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

表1 仿真參數(shù)設(shè)定

4.2 修復(fù)所需節(jié)點(diǎn)數(shù)

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

圖6 所需修復(fù)節(jié)點(diǎn)數(shù)隨網(wǎng)絡(luò)參數(shù)變化關(guān)系

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

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

4.3 修復(fù)節(jié)點(diǎn)移動(dòng)總距離

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

由圖7(a)可以看出，RIM算法因?yàn)樾枰苿?dòng)較多節(jié)點(diǎn)完成修復(fù)，所以節(jié)點(diǎn)的總體移動(dòng)距離會(huì)比TTM-TRA算法大。此外，隨著初始部署節(jié)點(diǎn)數(shù)增多，失效節(jié)點(diǎn)的1跳鄰居數(shù)也可能增多，RIM算法修復(fù)節(jié)點(diǎn)的移動(dòng)總距離也會(huì)呈現(xiàn)上升趨勢(shì)。在網(wǎng)絡(luò)初始部署節(jié)點(diǎn)數(shù)達(dá)到300時(shí)，RIM算法中修復(fù)節(jié)點(diǎn)移動(dòng)總距離會(huì)出現(xiàn)略微的下降。這可能是因?yàn)椋S著網(wǎng)絡(luò)中的節(jié)點(diǎn)越來越密集，雖然移動(dòng)的節(jié)點(diǎn)總數(shù)增加，但是單個(gè)節(jié)點(diǎn)需要移動(dòng)的距離會(huì)有所下降，所有節(jié)點(diǎn)的移動(dòng)總距離也可能出現(xiàn)略微下降。與之相比，TTM-TRA算法由于通常僅需要移動(dòng)一個(gè)修復(fù)節(jié)點(diǎn)，而節(jié)點(diǎn)之間的距離會(huì)隨著網(wǎng)絡(luò)初始部署節(jié)點(diǎn)增多而減小，所以修復(fù)節(jié)點(diǎn)移動(dòng)的距離總體會(huì)呈現(xiàn)一個(gè)下降趨勢(shì)。然而，在α取2/3時(shí)，修復(fù)節(jié)點(diǎn)的可選范圍會(huì)比α取1/2時(shí)小，所以TTM-TRA(I)算法所需的修復(fù)節(jié)點(diǎn)移動(dòng)總距離會(huì)比TTM-TRA(II)算法小。

圖7 修復(fù)節(jié)點(diǎn)移動(dòng)總距離隨網(wǎng)絡(luò)參數(shù)變化關(guān)系

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

4.4 相應(yīng)節(jié)點(diǎn)剩余生命周期對(duì)比

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

圖8(a)中的“Node 1、Node 2”分別表示了失效節(jié)點(diǎn)的兩個(gè)同層節(jié)點(diǎn)，圖8(b)中的“Node 1”表示了失效節(jié)點(diǎn)的一個(gè)同層節(jié)點(diǎn)。兩種情況下，修復(fù)節(jié)點(diǎn)在完成修復(fù)后，生命周期是有較為明顯的下降，因?yàn)橐苿?dòng)消耗掉了它相當(dāng)部分的能量。理論上，當(dāng)失效節(jié)點(diǎn)被修復(fù)時(shí)，失效節(jié)點(diǎn)同層節(jié)點(diǎn)的生命周期應(yīng)該上升至修復(fù)前的3/2。圖8(a)中的“Node 1”在修復(fù)前后生命周期上升幅度并沒有達(dá)到理想值，因?yàn)槠浔旧淼呢?fù)載可能來自多個(gè)父節(jié)點(diǎn)。由圖8(b)中可以看出，當(dāng)失效節(jié)點(diǎn)僅有1個(gè)同層節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)的剩余生命周期在失效節(jié)點(diǎn)修復(fù)后會(huì)上升到修復(fù)前的3/2。

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

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

5 結(jié)束語

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