分布式無線傳感器網絡的故障診斷摘要：無線傳感器網絡部署在惡劣環境中,傳感器節點容易出現故障。因此很好的故障檢測和定位可以較好的提高傳感器網絡的魯棒性和健壯性。本文介紹了一個高效的分布式算法對接點進行故障診斷。它是基于本地感知數據和鄰近的節點進行相似性比較，時間冗余對一些傳感器網絡的瞬態故障和通信有一定的容錯性。matlab仿真顯示該算法可以高效率診斷錯誤和很好的診斷精度。引言無線傳感器網絡是新興人工智能，廣泛應用于環境監控、安全監視和目標跟蹤［1］。低成本，低功耗的微型傳感器由信號發送、信息處理和通信單元組成。由于無線傳感器網絡通常部署在惡劣的環境中，難免傳感器網絡中會出現一些故障。傳感器網絡故障導致不正確的數據產生和錯誤的數據處理進而危及整個傳感器網絡。文獻［2-9］是一些關于無線傳感器網絡故障監測與診斷的調查研究。文獻［5］提出一種基于外部事件驅動對無線傳感器網絡進行故障診斷的方法。它可以全局上管理整個網絡，雖然外部處理可以執行更復雜的功能，但傳感器節點間的通信及管理是一個急需解決的問題。丁等人［8］提出了一種較低的計算開銷的局部診斷算法。每個傳感器節點通過比較自己的鄰居的感知數據和中位數數據來確定自己的狀態。局部診斷對于隨機部署的非均勻節點度的傳感器網絡處理能力非常有限。此外，在無線傳感器網絡環境中,對無故障的傳感器節點的拓撲也是一個很重要的方面。近幾年，提出了無線傳感器網絡的分布式故障診斷方法，如文章［9］，它通過節點自身感知數據和可信的鄰居節點數據進行比較，采用多數投票判決的方式進行故障診斷。這種算法針對出現兩次與臨節點達到預定閥值而進行判決的場景較為復雜，并且此算法不適用于節點間通信時產生的瞬態故障的情況下。在本文中，提出了一種高效的分布式算法對無線傳感器網絡中的故障節點進行隔離。通過利用自節點與臨節點間的數據比較和互傳測試結果來提高診斷精度。同時，時間冗余技術對一些問題節點和通信故障有一定的容錯性，通過無故障節點對故障節點進行剔除。在故障診斷中，無論節點是否被確定為無故障亦或是沒有參與診斷，傳感器網絡的連通性及故障診斷精度都極其重要。故障診斷模型在傳感器故障診斷模型中，假定傳感器節點隨機部署在目標區域及所有節點具有相同的傳輸范圍。每個節點擁有器鄰居節點的信息（該節點傳播范圍內的鄰居節點）。以下為故障診斷模型。故障不受位置的影響，可能發生在任何傳感器網絡節點上。兩個相鄰節點之間的通信可能會出現間歇性故障甚至永久性故障。最后傳感器節點傳送的數據可能會因為通信的間歇問題而導致發送出錯誤的數據，并被判別成正常節點。換句話說，就是只把永久故障的節點從網絡中移除。對傳感器網絡數據模型進行定義。每一個無故障傳感器節點和其及臨節點具有非常相近的數據值，假設Vi與Vj是兩個鄰居節點，Xi為節點Vi的發送數據。設定無故障閥值公式為|Xi-Xj|<=B，其中&依賴于傳感器網絡應用場景。例如，在溫度監測的傳感器網絡中，傳感器節點的監測數據和氣臨節點具有極其相似性，這就要求&是一個比較小的閥值。用G（V，E）代表傳感器網絡，其中V代表網絡中傳感器節點的集合和E代表的邊緣連接傳感器節點集。如果節點vi和vj之間的通信距離小于r，則相互進行鏈接并診斷。當（vi,vj）在E內時，vi與vj間的比較也是指G（V，E）的一個測試圖。如果鏈接正常則測試結果輸出為0.定義1對于圖G（V，E）和VieV，R（Vi）={VjeV:（Vi,Vj）eE}的所有Vi鄰居節點點集用R（Vi）定義。定義2：對于圖G（V，E），用Cij表示（Vi,Vj）eE；狀態正常則用Cij=0表示，否則Cij=1。定義3對于圖G（V，E）和VieV,用|Ci|標記VjeR（Vi）中Cij=0的數目，因此，0<|Ci|<|R（Vi）|。一個完整的診斷系統是指所有的故障節點可以根據確定的綜合系統生成，否則它是一個不完備的診斷。類似這種診斷，它不會把正常節點誤認為是故障節點。當無線傳感器網絡部署在惡劣環境中，其節點發生故障的可能性也大大增加。一個完備且正確的診斷系統是很難實現甚至在某些條件下是不可能的。在傳感器網絡可接受的不完備診斷方法，必須可以對故障節點被視為正常節點有一定的容錯性，并能較好的管理整個節點網絡。此外,它是仍然可以使用診斷算法把可能不正確的但被識別為無故障節點進行孤立并剔出網絡。原因是傳感器節點通常將廉價的和冗余節點來實現容錯反饋。使用上面的定義,我們提出一個分布式算法隔離傳感器網絡中故障節點。診斷包括三個步驟。它始于每個傳感器節點存儲的鄰居表NT。每個節點的鄰居表都包含了其所有鄰居節點的狀態Cij，以及每個節點的初始故障狀態值（故障用1表示）。用以下兩個決策標準來判定一個節點是否無故障：對每個節點Vi，如果|Ci|1,則把Fi=0（無故障）。對每個節點Vi，如果他的鄰居節點Vj有Fj=0且Cij=0,則Vi被診斷為無故障節點（Fi=0）。雖然我們的診斷算法是在某一時刻t基于比較感知數據的收集，我們收集q時刻發送的數據是為了對節點間通信的瞬態故障有一定的容錯能力。節點Vw根據鄰居節點在q個不同時間（t1,t2,t3???…發送的數據進行決策。這樣一個可變動范圍能更好的進行決策。用Xji去表示在時刻t.在Vi節點的狀態。然后，xj與每一個鄰節點數據的比較，其中1<j至q。iwCwj由Vw與Vj節點間的比較次數來決定，最后結果我們用e2來表示。舉個例子，有六個鄰居節點的節點Vw,并設定q=4,用每一個鄰節點與該節點數據進行比較，結果如下：/仃門1(1門＞JV1-(1門(}(J(J(j1111\丄(J11丿c4=0,c5=1。e2的值取決于q和ww如果°c4=0,c5=1。e2的值取決于q和wwwww節點間通信可靠程度。如果|Cw|ne1,則判為無故障節點，在這個實例中如果e1=3、|Cw|=4,Vw將被診斷為無故障節點。至少一個節點必須滿足開始啟動的第一個診斷條件。一旦發現故障的節點,其結果將被傳播給它的鄰居節點,并所有節點都刷新當前數據變成另一狀態。其大致診斷策略可用如下描述：AlgorithmfarInolatingFaultyNodexStep0:Eachnode心createsatiiblc1andinitializes”仞(o1cind1..lo1(Qiuliy>Seep1:Repeatthefollowingqtimessensornode化tests(卄c_丿￡(打玄)

togeneratew沁usingthefollowingcriterion

if—■:f：j<久then川卡止=0Step2:Set旬to0it川護<(7-弘)If>6,lthen1\—CJ(ftnilt-ftee)Step3>~ForllieremainingundelennijiedtiodesDorhefollowinginparallelForeachfwith「詢一①心“=6J=0and1^.—I,Setto0{fault-free)為了說明診斷算法,我們認為傳感器網絡有11個節點,如圖1所示,其中六他們都是無過錯的。為方便各邊標記1（不匹配）或0（匹配）,“匹配”的意思是該端點具有類似的檢測值。在本例中缺省值為Cij=Cji。所有成員節點運行的診斷算法的閾值缺省為&1=3。在步驟二中，在A、B和C、D的節點的協助下|Ch|和|Cc|大于或等于3則認為C、H是沒有故障的（即Fc=0）。第三步,C、H將把它們的診斷結果狀態告知鄰居節點,并讓網絡把A、B、D、G、I、J、K設置為無故障節點，C節點如果通信等級已被標記為1將不會對節點E造成影響。每一個A、B和D將檢查它是否有權限廣播其無故障狀態的鄰居節點。如果沒有權限將不采取任何操作。G發送它的狀態給鄰節點F,把Ff置為0（無故障），直至E和F都被標記為1才能執行下一步操作。確定故障的節點的數目是10，而不是6。這種不良狀態的原因是故障節點A、B、D、C產生相同的故障。故障節點c,錯誤地確定為無故障，并傳播錯誤的決定給它的鄰居把自己狀態設置成無故障。雖然我們選擇了這個特殊的案例說明，這種情況不太可能發生，可通過設置閾值&1來最小化這類故障。傳感器部署后的初步診斷節點進行，故障節點將被識別和從傳感器網絡中分離。他們中的一些人可能不工作從一開始就這樣被忽略。后有故障的節點數量的增加將是相當小而慢也就是說，這將是更自然的假設有故障的傳感器節點的概率是比較一旦初始部署后的故障節點被隔離。在隔離故障節點后的正常運行網絡，這是更現實的假設，平均節點度隨著時間的性能評估為了評估所提出的分布式的診斷算法的性能，利用蒙特卡洛進行模擬。它取決于各種參數平均節點度、節點故障率、和閥值01。以下是仿真設定的初始缺省值：1）故障間相互獨立；2）故障率p是指忽略定位錯誤的情況下的節點故障率°Ng、Nf分別代表節點的正常和故障。Ng、Nf由也讓被確定為故障的故障的節點數和被診斷出故障的節點的數目。診斷精度（DA）和虛警率（FAR）通過下列公式計算：DA=仙片har=刀二1皿m（1）nifn是節點總數。DA和FAR的范圍是0到1,而我們想要的是他們的值盡量接近于0.用計算機模擬一個傳感器網絡。1024個節點被隨機部署到512*512的區域范圍內。假定所有節點有一個默認的傳輸范圍。選擇的范圍決定著傳感器網絡具有所需的平均節點度。在模擬中,傳感器節點被認為是錯誤的概率為0.05,0.1,0.15,0.20,0.25。為獲得最壞的情況下的結果，我們還假定所有錯誤節點的情況下進行比較。我們已經得到不同p和0情況下DA和FAR的值。表1實在d=15是的結果。

TWBLE1t'AHP(HRVARIOUSf>AND叭WHEN〃卍1也(A)"川，<J“/A"3^7^9^V50.050.48<27)0.90(5)1.00fO.O)1.00(00*1.CKXO.O)0.100.23C79)0.62(39)0.99(G.&)1.00(0.0)1.CKXG.O)0.15OJ1(136)0.35(1O1)O.5H3(1L>O.*^9(13)L.CHXO.U)O.2U<1.06(193)0.1H(169)0.66(65)<1.97(14)1CHXU.O)0.250.03(249^0.09(234)0.33C171)0.65(91)l.OCKO.l)ffL=\37150.05OJO0.200.25n.oooo<m(M)o.ooonQrooni<oPo^jOrOOD1<0,07Jo.oooi<0.1nOOOOI(00,0001(0,08)n.DOOlto.13)0,0002(0,17^0.0003(0.25^O.OOOI<006^0,0001〔0,1)9、0,0002CO.16^0,0003CO.22^0.0004(0.34^0.0001(0.06)0.0001(0J仃)0.0002(0,Ifi)0.0003(0,24)0.0005(0.38)在忽略p和01的影響只考慮d=15是，虛警率得到了一個很好的結果。不過，閥值01也是一個很重要的影響因素，尤其在大面積故障的情況下。在d=15的情況下盡量保證Nfg低于4.例如，01比第3個p=0.05和第9個p=0.20都好，在d=15時，建議選擇01的范圍為11到19,這樣可以減少錯誤節點被誤認為是正確節點。在大部分p變動比較大的情況下取01=d。改變d的值研究仿真結果如表二所示：TABLEII.J1'.\FORVAItCOUSfjAND心lWHENtJ.Q7.<A)U./DtP&L=13570.050.10OJ11(16.)0.4820,336<102)0.234-(157>0.164(214>0.9840.910(9.2)0.782(34.)0627(77.)0.479(133)1.000(0.0)0.996<0.4)0.975<3.8)0.922(16.)0.824(45J1.000(0.0^1.000<0.0)0,9991J0.995(1.1)0.978<5.6^/■Bl=13^7^0.000.250002(1.7)0.002(1.7)?003(2,7)0004(3.5)0.006(4.4)0.004(4.2>0.006(5.4)0.008(7.0)0.0]L(S.9)0.015(12.>0.006(6.0)O.OOS(7.8)0.012(10.)0.017(14>0.025(19.)O.OOS(7.4)0.011(10.)0.016(14J0.023(19_)0.041(31.)在d=7的情況下得到不同的DA和FAR,為保證p小于等于0.25,取Nfg小于4,例如，01>7?然而會使Ngg為一個相對較小的值，實際上在這種情況下,Ngf會大于等于30,導致無故障節點數目不太理想。沒有很好的仿真結果是因為d值較小使無故障傳感器節點不太可能形成連通圖。一小群無故障節點或沒有使用，并與其他無故障的節點相隔離并不會對該故障診斷算法產生很大的影響。當p=0.25時，舉個例子，因為一小部分節點和其他正常節點相隔離導致FAR從0.006變化到0.041。所提出的診斷算法是構建一個功能的傳感器網絡的識別無故障傳感器節點盡可能，作為反對識別故障節點將形成一個連通圖，不會與故障節點診斷為無故障。一旦有故障的節點從網絡中隔離，他們可以被視為死亡節點。由于這些節點的刪除不需要的考慮，這是合理的假設，相對較小，經初步診斷。此外，所提出的診斷算法，如果周期性地施加，將刪除故障節點新生成的相鄰的兩個測試周期之間，保持相對小，除非事件導致大量的傳感器節點在同一時間失敗。我們已經觀察到的診斷算法的性能強烈依賴于底層的連接圖。隨機部署部分隔離的傳感器無故障節點，即使節點被正確診斷也不可能有效的降低這種依賴性。因此，一個高效的診斷算法應該適當的部署傳感器網絡和擁有一個相對高的d值，算法復雜度低點也能相對的降低通信開銷。由于文章內容量限制，在傳感和通信的瞬態故障的仿真結果在本文中沒有給出。我們發現，可以通過選擇合適的q和2來對瞬時故障進行容錯。總結在本文中，我們提出了一種分布式算法，用于隔離故障傳感器節點的無線傳感器網絡。在其初始狀態的基礎上的檢測數據和傳播的測試結果的局部比較，對每個傳感器節點的狀態進行了確定。該算法簡單，并高效的實現了對高故障率情況下的故障診斷。傳感器無故障節點的連通性在實現高性能的自診斷中非常重要，小部分無故障節點被隔離或沒有使用也能被正確識別。該算法還對通信中的一些瞬時故障具有容錯能力。致謝本工作經基礎研究項目韓國科學與工程基金會批準，批準號為R01-2006-000-10073-0。etMxsREHtr忑ENCES〔1〕LF?AkyiEi卜送"Sir<-w-dnkaTHMUhmKH二H」ULm-CyircL”"wirertsw誇二弓rNerwo『?rK>MurveyrCampucerNeT￡afk:r€2-3產no42002*Bp,|_2一o-Juikztiect,.C\sri5ilthfup03phllrG—c-ShethtDiagncIsis.o*EetlEorSSI■work.?1:【nrconf"communictdionssYcds"p-p?162711632*」L=1C2001-「31B"Kr7hIlannach.ar.Landw?I^en曲ar?：Ba*rCD3imlA-血CTifhnl"ForFaun—EleralnEvrt」二齊炸gcJtlDe-ecH匚ni=XVLlrcirtIZxsellwGrNelwurkrzrIEEETmnzlMsiclIlylrJricampL!-巾r*“WtL「3"NfxwrMarch2004,|_4一F:KIOUKhaJlf3u\.M,PCHr口nj1177*A?/-3ulcraiovarHlil<LIl-ce-」Lm=L:cn—linefaulttLscnLionofs-cnsclrrncDScTcnlcnlls'^IEEE⑷cljwors"VOL2."pp?974—Qoocl*Oc嚴2003-〔51LBRUFI-G