基于WSN的分布式容錯算法研究

劉 洋，王 軍，2*，吳云鵬

(1. 蘇州科技大學，江蘇蘇州 215009； 2. 中國科學院長春光學精密機械與物理研究所，吉林 長春 130033)

1 引言

WSN是由大量具有感知和通信能力的低功耗節點組成的多跳自組織網絡，其通常部署在一些人跡罕至的惡劣環境中，這就要求WSN具備一定的容錯能力以應對極端環境所導致的各類故障。一般影響WSN性能的故障分為硬故障和軟故障，硬故障主要是節點自身組件損壞或電源能量不足等因素造成的，而軟故障主要是節點采集傳輸數據的誤差率太大，不能得到準確的觀測值。而如何設計可靠的容錯機制，實現WSN數據傳輸的高效準確，是目前研究的熱點。

當前，國內外大多數解決方案都是從實踐上研究容錯機制，在文獻[3]中，Somaye等人設計了一種基于WSN的容錯和節能聚類算法(fault tolerance and energy clustering，FTEC)，FTEC算法折中考慮了能耗和容錯這兩個矛盾因素，在具體容錯過程中，該算法依據一定規則劃分有效簇，并對CH節點導致的故障提出了相應的自愈恢復策略，一定程度上提高了WSN的容錯性能，不過該算法沒有考慮實際算法開銷以及數據傳輸時延，只能在特定環境下應用；文獻[4]中，Chalhoub等人提出了一種以機器學習技術為核心的容錯框架，對不同故障類型的傳感器進行檢測與跟蹤，以便能夠快速進行自愈操作，但是該系統沒有考慮機器學習模型需要遍歷所有節點，此方案會產生大量額外的通信開銷，不適用于大規模網絡；文獻[5]中，Menaria等人提出了一種基于Petri網的分布式模型進行WSN容錯，該方案通過鄰居節點感知信息的時空相關性來檢測節點故障，能在物理層上極大的容忍硬件故障，然而該算法沒有考慮負載平衡的解決方案，隨著網絡節點數的增加，算法效率會逐漸降低，不能滿足多節點網絡需求；文獻[6]里，蔣和徐等人基于不相交路徑設計了一種路由容錯系統，通過色彩空間分離技術搭建節點間的數據路由路徑，避免了節點路由路徑的纏繞問題，大大增強了數據傳輸穩定性，但是其不能完全克服隨機路徑選擇過程中的網絡故障，實用性稍差，難以大規模推廣。

針對上述問題，本文提出了一種基于分簇的分布式容錯算法(distributed fault-tolerant algorithm，DFTA)，通過故障檢測、故障分類和故障恢復進行容錯機制設計，首先監視系統是否存在任何不當行為(故障檢測)，之后分析收集的數據并對網絡進行故障分類，最后使用建議的恢復算法在CH級別上進行恢復操作，并且利用該算法克服能量損失和硬件故障，延長了WSN內節點的生命周期。

2 網絡與節點模型

2.1 網絡模型與假設

如圖1所示，假設有N個初始能量相同的靜態傳感器節點隨機分布在一個二維區域內，它們分組成簇并自己選定CH，簇內的傳感器節點根據自己的傳輸半徑以多跳的方式相互連接，各個簇內的節點通過各自CH能夠互相通信，最終將來自所有簇的聚合消息都傳輸至基站，用以進一步處理信息。設所有節點初始狀態正常，都有屬于自己的獨立ID號，結構、功能和傳輸半徑均一致，并以固定的速率感知來自環境的數據，健康的節點可以將自己感測到的數據交換到鄰居節點上，且周期性地將自己處理過的數據和廣播信息傳輸給CH節點，通過同步通信，CH在一個固定的時間間隔內接收所有節點的數據和廣播消息用以保持網絡狀態，并且CH具有數據檢查和匯聚節點的屬性功能。

圖1 WSN分簇網絡模型

2.2 節點能耗模型

DFTA算法設計的最終目標是為了延長整個WSN的工作壽命，所以需要以節點能量耗盡所經歷時間為最大時間建模，所以本算法在Heinzelman等人提出的能耗模型上做了一些改進，在WSN數據傳輸能量消耗上僅針對數據傳輸和數據接收，令電池能量損耗為0，其能耗方程式如式(1)所示。

(1)

式(1)中，為傳輸1比特數據后的剩余能量，單位為焦耳()，為每個節點的初始能量，代表一定時間內傳輸1比特數據所消耗的能量，為傳輸時間，單位為微秒()，為接收到1比特數據后的剩余能量，是接收1比特數據所消耗的能量，代表接收時間，為電池的能量所示，本模型中假設電池為理想狀態，不考慮其損耗，并設定所有傳輸路徑具有相同的負載。

2.3 路徑損耗模型

為了進一步降低網絡內能量損耗，本文算法基于自由空間路徑損耗模型做了一些改進，DFTA中，路徑損耗(path loss，P)與距離成正比，其路徑損耗模型如式(2)所示。

=

(2)

2.4 CH競選模型

在實現算法之前，需要對WSN內節點進行分簇和競選CH的處理，首先任意傳感器節點i在其通信范圍內廣播一條包含其能量、位置和編號的消息，為了減少網絡內節點的整體能量消耗，控制參加競選的節點數量，在該模型內設置一個競選能量閾值T，如果節點能量大于該閾值則可以參加CH競選，反之則不行。每一輪中，符合條件的節點計算其CH競爭半徑(radius of competition，R)的大小，并綜合考慮節點剩余能量和與基站(base station，BS)的距離等因素，其計算公式如式(3)所示

(3)

式(3)中，表示第個節點到的距離；是任意節點到的最大距離；代表自定義的最大競爭半徑，其單位都是米；為當前競選節點的剩余能量；為競爭系數，取值為0到1之間的常數。針對本文大規模網絡的應用背景，考慮節點能量與距離因素對的影響，將的取值定為80-100，取值為065，當?，?時，節點的競爭半徑最大，其競選成功率也達最高。

3 分布式容錯算法

提出的算法是通過故障檢測、故障分類和故障恢復來實現WSN節點的物理層故障，屬于自愈技術的范疇，在DFTA算法中，網絡內的每個節點通過周期性的廣播消息向CH節點表示其運行狀態，CH再根據簇內節點狀態進行下一步動作，該算法共分為部署、故障檢測和故障恢復這三個階段。

3.1 部署階段

在部署階段中，主要包含兩個狀態，分別為設置狀態和穩態狀態，DFTA算法路由協議是基于LEACH的概念，其路由協議的時間棧如圖2所示。

圖2 部署階段路由協議時間棧

在設置狀態時，應用CH競選模型選擇合適的節點成為CH，每一輪中，選定的CH節點向簇內所有節點廣播一條廣告消息，通知所有節點更新狀態消息，在接受到該消息之后，所有非CH節點確定自己所在簇，并開始進入工作狀態。

在穩態狀態時，各個簇中的節點開始感知消息，并將感知到的數據與自身鄰居節點進行聚合比較，然后在規定的時間間隔內將感測到的信息傳輸給各自CH，最后經由CH匯總數據信息傳輸至BS。由于CH過多通信需要消耗大量能量，所以每一輪都必須重新競選CH節點，延長網絡內節點的生存壽命。

3.2 故障檢測階段

本階段主要是在CH級別和節點級別上進行故障診斷與檢測。在節點級，傳感器節點定時發送和接收來自鄰居節點的所有數據，時間設置為300μs，之后節點使用處理器將自身的采集數據與鄰居數據進行對比，以此來診斷各個傳感器節點；當關閉收發機電路時，傳感器節點進入睡眠狀態，時間設定為299μs。在CH級，CH節點接收簇內各節點收集的聚合數據，并使用式(4)對簇內節點進行綜合評估。

()=()-()(0≤≤)

(4)

式(4)中，()為信息差分向量，()為鄰居節點在一個周期內感知到的數據信息值，為差分因子，()表示傳感器節點在周期內感知到的信息值，通過計算()與()之間的向量差來對節點進行評估。CH從接收到的數據篩選發送方標識符，以識別哪些傳感器節點能夠成功發送數據，在周期t內無法向CH發送廣播消息的節點則被標識為故障節點，成功的對節點狀態進行檢測。

3.3 故障恢復階段

本階段為DFTA算法最重要的一環，主要是在節點級別和CH級別上聯合處理傳感器節點的硬件故障。當傳感器節點沒有在周期t內感知到環境信息，則會被檢測為“感知錯誤”，CH將其聲明為業務節點；若傳感器節點在一個周期時間t內都沒有從其鄰居們接收到任何數據，其會被檢測為“接收故障”，CH會將其聲明為僅感測節點，它只感知環境信息發送給CH，而不從其鄰居接收任何數據。

當節點電池能量大于預設置的休眠閾值時，CH會將其標識為活動節點，隨著節點能量達到一個閾值極限時，該節點會保留接收到的信息并向CH發送一條休眠通知消息，宣告自己為休眠節點，CH反饋消息并移除該節點，使用其它節點來替代其工作，至此網絡重新進入活動模式，新的節點開始向CH廣播消息，CH節點反過來將該節點添加到網絡中用以更新拓撲；若故障節點未得到CH反饋，它將一直保持睡眠狀態，CH重新選擇路由路徑并將該節點移出拓撲。而針對業務節點與僅感測節點，CH也會將其標識為故障節點，并使用其它節點來更新拓撲。其具體的容錯算法流程圖如圖3所示。

圖3中，N表示網絡中的活動節點數量，N為故障節點數量，N代表故障存疑節點，需要進一步確認其狀態；該容錯步驟主要是從廣播消息與數據包(data packet，DP)這兩方面來進行CH判斷，以此來檢測節點組件故障和電源模塊狀態，若節點發生故障，CH則開始進入恢復階段，其具體恢復流程如圖4所示。

4 實驗結果及分析

4.1 實驗設置

在本節實驗中，使用MATLAB仿真軟件對提出的DFTA算法進行驗證，令所有傳感器節點以分布式方式隨機分布在一個300m×300m正方形區域內，每個節點的最大傳輸距離設定為75m，其初始能量都為10J，節點休眠閾值設置為初始能量的3%，CH競選閾值設為初始能量的70%，所有節點的數據傳輸時間都規定為300μs，網絡內節點故障概率隨機設置，對節點數量N={50，100，…，300}進行重復比較，并根據CH競選模型將網絡分成不同的簇，對實驗方案獨立執行50次取其平均值作為最終結果，其仿真偽代碼和參數表如下。

圖3 一輪容錯流程圖

圖4 CH級故障恢復

仿真偽代碼:1) For random(k) do {隨機使用不同的節點故障概率}2) For N=50 to 300 step 50 do {從50到300個節點,每次遞增50}3)H←randamnetwork(N);{構建隨機網絡} 4) For A in DFTA do {運行DFTA算法} 5)S←A.InitPhaseTopo(K,H);{初始化網絡拓撲}6)TN←CalculateNodeAverageLifeTime(S);{計算節點的平均生存時間}

表1 仿真參數表

4.2 仿真結果及性能分析

4.2.1 檢測精度分析

為了驗證DFTA算法在故障檢測上的性能優勢，使用故障檢出率和故障誤檢率作為故障檢測精度的分析指標，其中故障檢出率=已檢出的故障節點個數/網絡故障節點總數，故障誤檢率=檢測為故障的正常節點數/網絡正常節點總數。對WSN內節點分別在傳感器故障、接收器故障和電池故障情形下進行檢測精度比較，并針對這三種故障設置不同的節點故障率，按照實驗設置每種實驗方案獨立執行50次，取平均值為最終結果，其實驗結果如圖5(a)和(b)所示。

圖5 三種故障下的檢測精度

由圖5(a)和(b)可知，DFTA算法針對不同故障情形都具有較高的故障檢測精度。當節點發生傳感器故障，且網絡故障率低于30%時，算法的故障檢出率在80%以上，誤檢率在3%以下，這是由于節點發生感知或發射器故障(統稱傳感器故障)時，它不會傳輸任何感知信息給CH，且無法與正常鄰居節點進行信息交互，故CH節點對此類故障有較高的檢測精度；當節點發生接收器故障，且網絡故障率在40%以上時，故障檢出率在70%左右，誤檢率在6%以下，檢測精度良好；當節點出現電池故障時，由于網絡內節點初始能量是隨機設置的，僅通過節點本身發送休眠信息，CH很難分辨出節點是否已經達到休眠閾值進入休眠，所以在網絡故障率同為30%左右時，電池故障的檢測率相比于傳感器故障降低了8%，又因為CH通過接收電池故障節點的鄰居節點消息，可判斷出該節點的故障類型，故相同的網絡故障率條件下，其故障檢出率還高于節點接收故障。從整體的實驗結果來看，DFTA算法對各種故障類型都具有很好的適應性，這對于本文容錯算法的實際應用提供了重要支撐。

4.2.2 網絡容錯率分析

為驗證故障節點數量對DFTA算法容錯性能的影響程度，將其與網絡級聯故障自愈算法(network cascade fault self-healing，NCFSH)、故障冗余路由算法(failure redundant routing algorithm，FRRA)和分布式異構聚類算法(distributed heterogeneous clustering algorithm，DHCA)進行比較，并且在每次實驗中，增加網絡節點個數，其失效節點容錯率比較圖如圖6所示。

圖6 不同節點數量下的容錯率

圖6清楚的展示出了不論節點數量多少，DFTA算法都具有較其它三種算法更高的故障節點容忍率。對于擁有200個節點的WSN而言，當網絡中超過37%、24%和20%的部署節點出現故障時，FRRA、NCFSH和DHCA算法均不能維持WSN基本功能，而本文算法仍可進行正常感測工作，這是由于所提算法是在CH級進行故障恢復，并在完成一輪恢復工作后重新進行CH競選，極大程度上保證了CH能夠正常進行恢復工作，使網絡擁有高容錯率。而隨著節點數量的增加，DFTA算法的容錯率提升幅度最大，其性能方面遠超其它同類算法。

4.2.3 能量消耗分析

圖7展示了DFTA、FRRA、NCFSH和DHCA這四種算法在節點數量一定時WSN內能量消耗情況，其中橫軸代表傳輸數據包次數，縱軸為網絡內平均能量消耗。從圖中可以看出這四種算法的變化趨勢大致相同，DFTA算法的能量消耗率比NCFSH算法節省了16%，比DHCA算法節省了22%，也比FRRA算法節省了28%，這是因為本文的節點能耗僅針對數據傳輸和數據接收，通信路徑損耗也只是與距離的發射和接收功率成正比的，再加上CH節點會移除網絡中發生故障的節點，減少了故障節點的能量消耗，并且增加節點休眠喚醒機制，大大減小了WSN整體能量消耗，達到了預期結果。

圖7 能量消耗比較圖

4.2.4 節點生存率分析

節點生存率是衡量容錯算法適用性的一個重要指標，由已部署節點總數減去被移除網絡拓撲的節點個數比上節點總數來表示。本小節在節點數為300的網絡規模下對每一輪的存活節點數量進行仿真分析，并將其與DHCA、FRRA和NCFSH這三種算法進行比較，其實驗結果如圖8所示。

圖8 節點生存率比較圖

如圖8所示，本文算法在平均節點生存率方面有較高優勢，其相較于NCFSH算法節點生存率提高了13.6%，比DHCA算法提高了19.5%，比FRRA算法提高了20.7%，這主要是由于DFTA算法在每一輪都會重新競選CH，大大減小了CH節點的能量消耗，并且將這種高能耗平均到了多個節點上，再加上算法采用的節點能耗模型和路徑損耗模型，進一步降低了網絡內能量消耗，從而延長了部署節點的生存時間，表現出了良好的性能。

5 結論

WSN作為現代通信系統的重要組成部分，高容錯能力是提高其網絡性能的有效方法，本文以網絡故障管理中故障容錯能力為研究目標，提出了一種基于WSN的分布式容錯算法(DFTA)來檢測和恢復節點硬件故障，并分別在節點級和CH級執行檢測和恢復。DFTA算法與FRRA、NCFSH、DHCA算法相比，在節點故障檢測上平均能夠達到80%左右的精度，在網絡容錯率和能量消耗方面性能也均高于其它三種算法，最后在節點生存率方面相較于其它三種算法分別提高了13.6%、19.5%、20.7%，顯示出了理想的故障容錯能力。

在未來研究中，會側重構造更多的傳感器網絡用以模擬真實環境樣本，評估軟件故障對WSN的實際影響，在增加大量數據包的基礎上，構建一種合適的路由算法，降低通信開銷，并在CH節點上應用自配置機制來管理各個簇內網絡，最后能夠延長WSN網絡壽命和算法穩定性。