尹榮榮 劉 彬 劉浩然 郝曉辰

(燕山大學電氣工程學院 秦皇島 066004)

1 引言

無線傳感器網(wǎng)絡(Wireless Sensor Networks,WSNs)可以隨時隨地自組成網(wǎng)，特別適合在敵對或惡劣條件下快速組網(wǎng)，形成對特定目標的有效監(jiān)視[1]。由于傳感器節(jié)點常部署在面積廣大且人跡罕至甚至危險的遠程環(huán)境中，供電電池不易替換[2]，環(huán)境損壞造成的節(jié)點失效情況頻繁出現(xiàn)[3]，所以綜合關注網(wǎng)絡節(jié)能效率和節(jié)點隨機故障容忍能力的容錯拓撲控制[4]是WSNs的一個重要研究課題。

目前容錯拓撲控制的研究，重點集中于探索分布式算法構造具有節(jié)能特點的k連通容錯網(wǎng)絡[5]與無標度容錯網(wǎng)絡[6]，以保證節(jié)點隨機失效下的網(wǎng)絡正常運行。對于k連通容錯算法，文獻[7]為冗余機制能自動產(chǎn)生一個具備相似功能的替代方案，使網(wǎng)絡在任意k.-1個節(jié)點同時失效狀態(tài)下依然能正常工作，提出了k連通k支配集構造算法；文獻[8]認為在連通支配集中節(jié)點存在功能差異，配備相同的冗余度并非必要，拓展了基于睡眠/工作調度的k連通m支配集生成算法；文獻[9]聯(lián)合睡眠調度和功率調整技術，給出了簇間k連通容錯拓撲控制算法；這些算法均為WSNs建立了k連通最小能耗容錯拓撲，但是，網(wǎng)絡維持k連通需要耗費大量的能量資源[10]，造成僅能容忍少量隨機失效節(jié)點的弊端。因此，近來少量學者從無標度網(wǎng)絡對節(jié)點隨機失效的強容錯性[11,12]出發(fā)，建立適用于WSNs的無標度拓撲結構。如，陳力軍等人[13]借助隨機行走機制，通過改善拓撲均勻性，生成了具有無標度特征的WSNs簇間拓撲結構；文獻[14]將節(jié)點剩余能量與無標度網(wǎng)絡擇優(yōu)增長機制相結合，建立了具有無標度特征的 WSNs能量均衡拓撲；文獻[15]借助適應度拓撲演化模型，將適應度計算與節(jié)點能量值直接關聯(lián)，提出了WSNs無標度拓撲構建算法；他們均使WSNs具有了無標度網(wǎng)絡的強容錯性。然而，無論是k連通構建算法還是無標度生成算法，皆是在保證網(wǎng)絡容錯結構基礎上進行的能量優(yōu)化，由于忽視了節(jié)點能量耗盡故障對拓撲容錯性的影響，導致建立的網(wǎng)絡拓撲容錯性差，而且存在嚴重的能效約束。因此，面向節(jié)點能量耗盡和隨機失效的綜合故障優(yōu)化是探索更加有效的WSNs容錯拓撲控制方法的新思路。

基于上述分析，本文提出一種基于節(jié)點能量耗盡和隨機失效綜合故障模型的WSNs容錯拓撲控制方法 FTCA(Fault-tolerant Topology Control Approach)，該方法首先根據(jù)節(jié)點能量耗盡和隨機失效信息進行綜合故障建模，然后利用不等式放縮法與一元函數(shù)極值分析法對故障模型進行節(jié)點度量化分析，最后通過調整網(wǎng)絡中各節(jié)點的節(jié)點度趨于其節(jié)點度最優(yōu)值對拓撲結構進行控制，保證了網(wǎng)絡生命期和節(jié)點能量耗盡及隨機失效綜合容忍能力的雙重需求。

2 節(jié)點綜合故障建模

由于能量耗盡造成節(jié)點故障和環(huán)境損壞導致節(jié)點隨機失效是WSNs故障的主要表現(xiàn)形式，則可將網(wǎng)絡中任意節(jié)點i的故障概率表示為能量耗盡概率fe(i)和隨機失效概率fr(i)的乘積形式。

其中fe(i)[16]取決于節(jié)點i的初始能量E0(i)，能量消耗Ec(i)和網(wǎng)絡運行時間t，即

采用圖 1無線通信能耗模型[17]，相距為d的節(jié)點發(fā)送lbit數(shù)據(jù)所消耗的能量Etx為信號發(fā)射電路與信號放大電路消耗的能量之和為

節(jié)點接收lbit數(shù)據(jù)消耗能量Erx由式(4)計算得到

那么，節(jié)點i的總能耗Ec(i)可用下述形式表示：

假設N個節(jié)點均勻散布在 2維有界監(jiān)測區(qū)域G(面積為A)內，則節(jié)點落入以通信距離d為半徑的圓域D內的概率為

圖1 無線通信能耗模型

即節(jié)點傳輸距離d與其節(jié)點度k之間存在如下關系：

將式(7)代入式(5)可得節(jié)點i的能耗值Ec(i)隨其節(jié)點度k的變化關系，進而代入式(2)得到由節(jié)點度k和運行時間t描述的節(jié)點能量耗盡概率fe(i)。

考慮到節(jié)點隨機失效是因環(huán)境損壞導致網(wǎng)絡稀疏，從而使節(jié)點在網(wǎng)絡運行環(huán)境中發(fā)生孤立喪失規(guī)定功能的一類故障，其概率與節(jié)點度k呈指數(shù)變化關系[18]，有

結合式(1)、式(8)和式(9)，可得網(wǎng)絡中任意節(jié)點i的故障模型如下：

從而，利用節(jié)點度k和網(wǎng)絡運行時間t，節(jié)點能量耗盡和環(huán)境損壞造成的綜合失效故障具有式(10)的統(tǒng)一模型形式，有必要對k值進行分析，以得到WSNs容錯拓撲構建的理論依據(jù)。

3 基于故障模型的節(jié)點度量化分析

在對k值進行量化分析之前，必須對網(wǎng)絡生命期和節(jié)點能量耗盡及隨機失效綜合故障容忍能力的雙重需求進行定義：

討論定義1是針對網(wǎng)絡拓撲的節(jié)能和容錯雙重需求而言的，此定義表明，對于一個網(wǎng)絡G，為提高其拓撲的能量有效性，網(wǎng)絡G須保證一定的生存時間tmin，即t≥tmin；同時為增強其拓撲對隨機失效節(jié)點的容忍能力，網(wǎng)絡G須維持一定的節(jié)點度下限kmin，即k≥kmin，而為增強其拓撲對能量耗盡節(jié)點的容錯性，網(wǎng)絡G又須限定其節(jié)點度的上限kmax，即k≤kmax。可見，若網(wǎng)絡G滿足定義 1的條件，則它不僅可以確保網(wǎng)絡的生存時間需求，又可以增強容忍能量耗盡和環(huán)境損壞導致的綜合節(jié)點失效現(xiàn)象，也就是說，能夠滿足網(wǎng)絡生命期和綜合故障容忍能力要求較高的應用場景。

3.1 滿足雙重需求的節(jié)點故障率分析

基于節(jié)點故障模型(式(10))和網(wǎng)絡生命期及綜合故障容忍能力雙重需求(定義1)，給出滿足網(wǎng)絡生命期和綜合故障容忍能力雙重需求的節(jié)點故障率取值。

證明為確保網(wǎng)絡滿足定義 1，網(wǎng)絡中任意節(jié)點i須滿足定義1，為此下面采用不等式放縮法對滿足定義1的節(jié)點故障率f(i)進行討論。

(1)由t≥tmin可得，節(jié)點i的故障率f(i)符合

又根據(jù)kmin≤k≤kmax易得

那么由不等式的基本性質可以推出

(2)由kmin≤k≤kmax得

基于不等式的基本性質，由式(10)得到

綜合式(14)和式(17)，有

3.2 節(jié)點度的定量分析

根據(jù)定理 1，網(wǎng)絡生命期和綜合故障容忍能力的雙重需求轉化成了節(jié)點故障率的要求(式(18))，在此基礎上，通過一元函數(shù)極值分析法可以對節(jié)點度進行定量分析，獲取在滿足故障率要求下具有最大生存時間的節(jié)點度取值，為網(wǎng)絡拓撲構建提供依據(jù)。

證明令c=a/b，當節(jié)點故障率滿足f(i) =f0，記網(wǎng)絡運行時間t為，根據(jù)式(10)有

采用一元函數(shù)極值分析法研究節(jié)點度取值k與網(wǎng)絡生存時間之間的變化關系，對關于k求一階導數(shù)得

進而，根據(jù)式(20)可得，在k∈[kmin,+ ∞) 內＞0，那么是增函數(shù)，從而，在滿足k≤kmax且e-k-f0＞ 0 的條件下，即k=min{kmax,- lnf0}點處，最大。也就是說，存在唯一極值點k0=min{kmax,- lnf0}，使得節(jié)點i在滿足故障率要求下可實現(xiàn)其生命期的最大化。 證畢

綜上，本節(jié)獲得了滿足網(wǎng)絡生命期和綜合故障容忍能力雙重需求的節(jié)點度k的最優(yōu)值k0，為構建可最大限度延長網(wǎng)絡生命期，且能夠有效提高對節(jié)點能量耗盡及隨機失效綜合故障容忍能力的目標拓撲提供依據(jù)。

4 基于節(jié)點度調整的FTCA算法

FTCA算法是基于確定的節(jié)點度最優(yōu)值k0提出的一種WSNs容錯拓撲控制方法，主要包括以下步驟：

(1)信息交換 各節(jié)點以最大發(fā)射功率廣播包含自身id和位置信息(x,y)的HELLO數(shù)據(jù)包。任意收到HELLO包的節(jié)點建立其鄰居列表，以節(jié)點i為例，鄰居列表nl(i)的表頭格式如表1所示。其中，id(j)表示節(jié)點i的鄰居節(jié)點j的id,(xj,yj)表示節(jié)點j的地理位置，d(i,j)為i和j之間的距離，由兩點間的距離公式計算得到，mark(j)為狀態(tài)標識，初始記為0。

表1 節(jié)點i鄰居列表nl( i)的表頭格式

(2)鄰居排序 節(jié)點i依據(jù)鄰居列表nl(i)中距離的升序排列其鄰節(jié)點，并廣播包含自身id和鄰居列表的NOTICE信息。對于收到NOTICE信息的節(jié)點，判斷自身通信區(qū)域內的鏈路狀態(tài)，建立區(qū)域鏈路列表，其表頭格式見表2。其中，d(j1,j2)為節(jié)點i的相互可達鄰居節(jié)點j1和j2間的距離，id(j1)和id(j2) 分別為j1,j2的id, s ign(j1,j2)為狀態(tài)標識，初始設定為0。

表2 節(jié)點i區(qū)域鏈路列表ll( i)的表頭格式

節(jié)點i按照通信距離d(j1,j2)對其區(qū)域鏈路列表ll(i)進行升序排列，如果j1和j2之間不存在通信路徑，將鏈路l(j1,j2)的狀態(tài)標識sign(ji,jj)更新為1，直至與所有鄰節(jié)點皆建立通信路徑為止，刪除sign標記為0的鏈路項信息。

(3)鏈路選擇 基于區(qū)域鏈路列表ll(i)，節(jié)點i尋找ll(i)中由自身出發(fā)的鏈路項，將其sign標記為2，刪除標記為1的鏈路項信息，并廣播包含自身id和ll(i)信息的CONNECT數(shù)據(jù)包。根據(jù)所接收到的CONNECT數(shù)據(jù)，以鏈路雙向性原則確定其鄰節(jié)點，并將其nl列表中的相應標識位mark更新為1，統(tǒng)計其數(shù)目記為kmin，計算出k0與kmin的差值。按距離升序依次將個nl列表中標識為0的節(jié)點標記為2，廣播其id，保留具有雙向鏈路的鄰節(jié)點，將nl中相應狀態(tài)標識更新為 1，刪除狀態(tài)不為 1的鄰節(jié)點信息項。

(4)功率調整 最后，節(jié)點i確定的發(fā)射功率應保證與其所有鄰節(jié)點(位于已更新的鄰居列表nl中)皆能正常通信，即節(jié)點i的發(fā)射半徑為di=max{d(i,j)|j∈nl(i) } 。

5 實驗分析

本文使用仿真工具 Matlab實現(xiàn)k連通算法k-Grid(k=2)[7]、無標度算法 EAEM(m0=2,m=1)[14]以及FTCA算法，并比較所得網(wǎng)絡拓撲的節(jié)能性和容錯能力。實驗中參數(shù)設置如表3所示，運行仿真實驗50次，以下分析數(shù)據(jù)均為50次實驗數(shù)據(jù)均值。

基于網(wǎng)絡生命期和節(jié)點能量耗盡故障及隨機失效故障綜合容忍能力的雙重需求，節(jié)點度k的量化分析結果如圖2所示，該圖直觀地描述并驗證了k的最優(yōu)值k0的存在性。圖3描述了FTCA算法所得目標拓撲中節(jié)點平均度＜k＞與其理論最優(yōu)值k0之間的偏差情況，偏差越小意味FTCA算法的準確率越高。從圖2中可以看出，當節(jié)點度取值為k=-ln(f0)時其生存時間t達到最大，即最優(yōu)值k0的存在性在圖中得到了很好的體現(xiàn)。從圖3中可以看出，當網(wǎng)絡節(jié)點數(shù)目增加時，F(xiàn)TCA算法所得拓撲的節(jié)點平均度與理論最優(yōu)值之間的偏差在減小，且最大偏差小于0.15，也就是說，F(xiàn)TCA算法可以有效保證生成拓撲的準確性。

圖 4描述了原始拓撲結構Gs以及k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA算法所得目標拓撲結構圖，該圖驗證了FTCA算法的相關拓撲性質，如連通性、對稱性與魯棒性。從圖4可以看出，k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和FTCA算法均對原始拓撲結構Gs進行了簡化，生成的目標拓撲結構都保留了雙向鏈路。另外，由于k-Grid(k=2)算法基于概率進行拓撲構建，依據(jù)鏈路冗余實現(xiàn)拓撲容錯，較 EAEM(m0=2,m=1)算法和FTCA算法所得拓撲更為密集，且拓撲的連通性不能很好地保證；而EAEM算法是根據(jù)結構的不均勻性實現(xiàn)容錯，F(xiàn)TCA算法是以維持各節(jié)點的節(jié)點度在某一特定值達到容錯，兩者所得拓撲結構更為稀疏，且有效確保了所得拓撲的全連通。

表3 實驗參數(shù)設置

圖2 節(jié)點度最優(yōu)值k0存在性分析圖

圖3 FTCA算法準確性分析圖

圖4 拓撲結構分析圖

圖 5描述了k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA算法所得目標拓撲的節(jié)點平均發(fā)射半徑。由于較小的發(fā)射半徑能夠降低節(jié)點能量消耗，減少通信干擾，增大網(wǎng)絡容量，因此節(jié)點的發(fā)射半徑大小一定程度上能體現(xiàn)網(wǎng)絡的節(jié)能性，是容錯拓撲控制算法追求的良好拓撲性質之一。圖 6描述了k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和FTCA算法所得目標拓撲的節(jié)點平均度。由于節(jié)點最小度為k的k連通網(wǎng)絡在任意k-1個節(jié)點失效后仍能保持連通，具有k-1的容錯能力，雖然節(jié)點平均度為k不能保證網(wǎng)絡是k連通，但是，節(jié)點的平均度在一定程度上也能反映網(wǎng)絡的容錯能力，是容錯拓撲控制算法追求的又一良好拓撲性質。從圖5可以看出，網(wǎng)絡節(jié)點數(shù)從100至500的變化中，由于FTCA算法所得拓撲無需維持k-Grid(k=2)拓撲的冗余鏈路，也不存在 EAEM(m0=2,m=1)拓撲的集散(度很大)節(jié)點，故其節(jié)點平均發(fā)射半徑始終遠小于k-Grid(k=2)和EAEM(m0=2,m=1)拓撲，并且隨著節(jié)點數(shù)的增大，節(jié)點平均發(fā)射半徑逐漸減小，即網(wǎng)絡具有更好的節(jié)能性。從圖6可以看出，由于FTCA算法以節(jié)點能量故障和隨機故障的協(xié)同優(yōu)化為設計目標，通過各節(jié)點維持某一特定節(jié)點度實現(xiàn)容錯，所得拓撲的節(jié)點平均度低于k-Grid(k=2)冗余拓撲，高于 EAEM(m0=2,m=1)非冗余拓撲，即網(wǎng)絡對節(jié)點隨機失效的容忍能力介于k-Grid(k=2)拓撲與EAEM(m0=2,m=1)拓撲之間。

WSNs生命期定義為有效數(shù)據(jù)采集輪數(shù)(采集1輪數(shù)據(jù)規(guī)定為全網(wǎng)中各節(jié)點傳輸數(shù)據(jù)1次)是評價容錯拓撲控制算法性能的重要指標，對于特定的節(jié)點數(shù)(100個)，分別運行k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA 算法，然后以 Poisson規(guī)則隨機地失效節(jié)點，直到可用節(jié)點(位于最大連通分支中)數(shù)占網(wǎng)絡原有節(jié)點數(shù)的50%時停止，此時網(wǎng)絡生命期也終止。圖7給出了上述算法所得目標拓撲在節(jié)點能量耗盡與隨機失效故障共存下的生命期變化情況。其中，圖 7(a)描述了從開始至網(wǎng)絡終止整個運行時間段內的節(jié)點隨機失效現(xiàn)象，圖7(b)為該時間段內網(wǎng)絡可用節(jié)點數(shù)的變化情況，圖 7(c)為網(wǎng)絡出現(xiàn)節(jié)點能量耗盡故障的運行時刻，圖7(d)為網(wǎng)絡出現(xiàn)節(jié)點隨機失效故障的運行時刻。可見，k-Grid(k=2)算法所得拓撲對隨機節(jié)點失效有較強的容錯能力，在網(wǎng)絡終止前僅出現(xiàn)一次因隨機失效節(jié)點引發(fā)的網(wǎng)絡分割現(xiàn)象(圖 7(d))，但因多節(jié)點的能量耗盡故障(圖7(c))導致網(wǎng)絡較早終止(圖7(b))；EAEM(m0=2,m=1)算法所得網(wǎng)絡拓撲的容錯能力恰與k-Grid(k=2)拓撲相反，在網(wǎng)絡終止前沒有出現(xiàn)過節(jié)點能量耗盡現(xiàn)象(圖 7(c))，卻因部分隨機失效節(jié)點發(fā)生網(wǎng)絡分割(圖 7(d))，最終因集散節(jié)點的能量耗盡故障而較早終止運行(圖 7(b))；FTCA算法由于考慮了節(jié)點能量耗盡故障對網(wǎng)絡容錯性的影響，并以優(yōu)化節(jié)點綜合故障為設計目標，所得拓撲結構在最大化網(wǎng)絡生命期(圖 7(b))和提升網(wǎng)絡綜合故障容忍能力方面(圖 7(c)和圖 7(d))均體現(xiàn)出極佳的效果，大大延長了網(wǎng)絡的生命期，增強了網(wǎng)絡對節(jié)點能量耗盡故障和隨機失效故障的綜合容錯性。

圖5 節(jié)點平均發(fā)射半徑分析圖

圖6 節(jié)點平均度分析圖

圖7 節(jié)點能量耗盡與隨機失效綜合故障下網(wǎng)絡生命期分析圖

6 結束語

本文提出了一種基于節(jié)點能量耗盡和隨機失效綜合故障模型的WSNs容錯拓撲控制方法FTCA，使得生成的網(wǎng)絡拓撲具有較大生命期和對節(jié)點能量耗盡及隨機失效強容錯的雙重性能。另外，通過對節(jié)點故障模型的分析得出，當節(jié)點度為 min{kmax,- ln (f0)}時可以獲得滿足節(jié)能和容錯雙重需求的目標拓撲；并對FTCA算法實驗數(shù)據(jù)的分析得出，相對k-Grid(k=2)算法和 EAEM(m0=2,m=1)算法，F(xiàn)TCA算法由于采用了節(jié)點能量故障和隨機故障綜合優(yōu)化的節(jié)點度取值，大大延緩了因節(jié)點能量耗盡及隨機失效綜合故障造成的網(wǎng)絡生命期終止時刻，有效地增強了網(wǎng)絡對節(jié)點能量耗盡及隨機失效的綜合容錯能力。

[1]Akyildiz I F, Su W, Sankarasubramaniam Y,et al.. Wireless sensor networks: a survey[J].Computer Networks, 2002, 38(4):393-422.

[2]Chen I R, Speer A P, and Eltoweissy M. Adaptive fault-tolerant QoS control algorithm for maximizing system lifetime of query-based wireless sensor networks[J].IEEE Transactions on Dependable and Secure Computing, 2011,8(2): 161-176.

[3]Lee S and Younis M. Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree[J].Journal of Parallel and Distributed Computing, 2010,70(5): 525-536.

[4]Bari A, Jaekel A, Jiang J,et al.. Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirement[J].Computer Communications, 2012, 35(3):320-333.

[5]Zhang W Y, Xue G L, and Misra S. Fault-tolerant relay node placement in wireless sensor networks: problems and algorithms[C]. Proceedings-IEEE INFOCOM, Anchorage,AK, 2007: 1649-1657.

[6]Zhang K, Han D H, and Feng H P. A model of linear expanding in the local-world based on the laws of internal evolution of the wireless sensor networks[C]. Proceedings of the 2010 International Conference on Computer Application and System Modeling, Taiyuan, China, 2010: 357-360.

[7]Dai F and Wu J. On constructing k-connected k-dominating set in wireless Ad hoc and sensor networks[J].Journal of Parallel and Distributed Computing, 2006, 66(7): 947-958.

[8]Zhao Y X, Wu J, Li F,et al.. VBS: maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones[C]. Proceedings-IEEE INFOCOM, San Diego, CA,2010: 1-5.

[9]Forghani A and Rahmani A M. Multi state fault tolerant topology control algorithm for wireless sensor networks[C].Proceedings of the 2008 2nd International Conference on Future Generation Communication and Networking, Hainan Island, China, 2008: 433-436.

[10]王良民, 馬建峰, 王超. 無線傳感器網(wǎng)絡拓撲的容錯度與容侵度[J]. 電子學報, 2006, 34(8): 1446-1451.

Wang L M, Ma J F, and Wang C. Degree of fault-tolerance and intrusion-tolerance for topologies of wireless sensor networks[J].Acta Electronic Sinica, 2006, 34(8): 1446-1451.

[11]Barabasi A L and Albert R. Emergence of scaling in random networks[J].Science, 1999, 286(5439): 509-512.

[12]Cohen R, Erez K, Ben A D,et al.. Resilience of the internet to random breakdowns[J].Physical Review Letters, 2000, 85(21):4626-4628.

[13]陳力軍, 劉明, 陳道蓄, 等. 基于隨機行走的無線傳感器網(wǎng)絡簇間拓撲演化[J]. 計算機學報, 2009, 32(1): 69-76.

Chen L J, Liu M, Chen D X,et al.. Topology evolution of wireless sensor networks among cluster heads by random walkers[J].Chinese Journal of Computers, 2009, 32(1): 69-76.

[14]Zhu H L, Luo H, Peng H P,et al.. Complex networks-based energy-efficient evolution model for wireless sensor networks[J].Chaos,Solitons and Fractals, 2009, 41(4):1828-1835.

[15]Qi X Q, Ma S Q, and Zheng G Z. Topology evolution of wireless sensor networks based on adaptive free-scale networks[J].Journal of Information and Computational Science, 2011, 8(3): 467-475.

[16]Mizanian K, Yousefi H, and Jahangir A H. Modeling and evaluating reliable real-time degree in multi-hop wireless sensor networks[C]. Proceedings of the 2009 IEEE Sarnoff Symposium, Princeton, NJ, 2009: 1-6.

[17]Heizelman W R, Chandrakasan A, and Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]. Proceedings of the Hawaii International Conference on System Sciences, Maui, USA,2000: 1-10.

[18]Kleinrock L and Silvester J. Optimum transmission radii for packet radio networks or why six is a magic number[C].Proceedings of the National Telecommunications Conference,Birmingham Ala, 1978: 1-5.