基于節點綜合故障模型的無線傳感器網絡容錯拓撲控制方法

尹榮榮 劉 彬 劉浩然 郝曉辰

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

1 引言

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

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

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

2 節點綜合故障建模

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

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

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

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

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

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

圖1 無線通信能耗模型

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

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

考慮到節點隨機失效是因環境損壞導致網絡稀疏，從而使節點在網絡運行環境中發生孤立喪失規定功能的一類故障，其概率與節點度k呈指數變化關系[18]，有

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

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

3 基于故障模型的節點度量化分析

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

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

3.1 滿足雙重需求的節點故障率分析

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

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

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

又根據kmin≤k≤kmax易得

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

(2)由kmin≤k≤kmax得

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

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

3.2 節點度的定量分析

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

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

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

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

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

4 基于節點度調整的FTCA算法

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

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

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

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

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

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

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

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

5 實驗分析

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

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

圖 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)算法基于概率進行拓撲構建，依據鏈路冗余實現拓撲容錯，較 EAEM(m0=2,m=1)算法和FTCA算法所得拓撲更為密集，且拓撲的連通性不能很好地保證；而EAEM算法是根據結構的不均勻性實現容錯，FTCA算法是以維持各節點的節點度在某一特定值達到容錯，兩者所得拓撲結構更為稀疏，且有效確保了所得拓撲的全連通。

表3 實驗參數設置

圖2 節點度最優值k0存在性分析圖

圖3 FTCA算法準確性分析圖

圖4 拓撲結構分析圖

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

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

圖5 節點平均發射半徑分析圖

圖6 節點平均度分析圖

圖7 節點能量耗盡與隨機失效綜合故障下網絡生命期分析圖

6 結束語

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

[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]王良民, 馬建峰, 王超. 無線傳感器網絡拓撲的容錯度與容侵度[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]陳力軍, 劉明, 陳道蓄, 等. 基于隨機行走的無線傳感器網絡簇間拓撲演化[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.