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

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

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

1 引言

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

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

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

2 網(wǎng)絡與節(jié)點模型

2.1 網(wǎng)絡模型與假設

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

圖1 WSN分簇網(wǎng)絡模型

2.2 節(jié)點能耗模型

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

(1)

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

2.3 路徑損耗模型

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

=

(2)

2.4 CH競選模型

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

(3)

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

3 分布式容錯算法

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

3.1 部署階段

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

圖2 部署階段路由協(xié)議時間棧

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

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

3.2 故障檢測階段

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

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

(4)

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

3.3 故障恢復階段

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

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

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

4 實驗結果及分析

4.1 實驗設置

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

圖3 一輪容錯流程圖

圖4 CH級故障恢復

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

表1 仿真參數(shù)表

4.2 仿真結果及性能分析

4.2.1 檢測精度分析

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

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

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

4.2.2 網(wǎng)絡容錯率分析

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

圖6 不同節(jié)點數(shù)量下的容錯率

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

4.2.3 能量消耗分析

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

圖7 能量消耗比較圖

4.2.4 節(jié)點生存率分析

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

圖8 節(jié)點生存率比較圖

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

5 結論

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

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