徐振朋,沈 浩,曾瑋妮

(1.杰瑞深軟科技有限公司,江蘇連云港222061;2.江蘇自動(dòng)化研究所,江蘇連云港222061)

一種無(wú)線自組網(wǎng)故障檢測(cè)算法

徐振朋1,沈 浩2,曾瑋妮2

(1.杰瑞深軟科技有限公司,江蘇連云港222061;2.江蘇自動(dòng)化研究所,江蘇連云港222061)

針對(duì)無(wú)線自組網(wǎng)的拓?fù)浣Y(jié)構(gòu),設(shè)計(jì)一種基于分簇的無(wú)線自組網(wǎng)節(jié)點(diǎn)故障檢測(cè)架構(gòu)和對(duì)應(yīng)的故障檢測(cè)算法。分簇時(shí)分別確定主用簇和備用簇管理節(jié)點(diǎn),冗余簇管理節(jié)點(diǎn)負(fù)責(zé)對(duì)內(nèi)部成員實(shí)施異常檢測(cè),給出故障檢測(cè)模塊的心跳發(fā)送、心跳監(jiān)控、心跳預(yù)判與實(shí)時(shí)調(diào)整機(jī)制,通過(guò)增加心跳預(yù)判實(shí)時(shí)調(diào)整機(jī)制,確保算法能夠動(dòng)態(tài)適應(yīng)自組網(wǎng)易變的拓?fù)浣Y(jié)構(gòu),并通過(guò)備用簇管理節(jié)點(diǎn)和簇間共享異常信息機(jī)制,提高系統(tǒng)故障檢測(cè)的可靠性。利用仿真實(shí)驗(yàn)對(duì)故障檢測(cè)機(jī)制的性能進(jìn)行評(píng)估,結(jié)果表明,提出的故障檢測(cè)算法具備較好的檢測(cè)準(zhǔn)確率,能夠有效滿足上層應(yīng)用在系統(tǒng)可靠性設(shè)計(jì)方面的需求。

無(wú)線自組網(wǎng);容錯(cuò);節(jié)點(diǎn)故障;故障檢測(cè);心跳預(yù)判

1 概述

無(wú)線自組網(wǎng)(Ad Hoc Network)作為一種無(wú)中心、動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涞姆植际接?jì)算系統(tǒng),依靠自身的便捷、自組以及易接入等優(yōu)勢(shì)已廣泛用于各行業(yè)領(lǐng)域[1]。隨著無(wú)線自組網(wǎng)的不斷發(fā)展,其系統(tǒng)規(guī)模及復(fù)雜性不斷提高,系統(tǒng)相關(guān)的信息丟失、鏈路故障、節(jié)點(diǎn)失效對(duì)頂層應(yīng)用的影響越來(lái)越大[2-3]。作為基礎(chǔ)組件,故障與失效檢測(cè)是構(gòu)建可靠的分布式應(yīng)用的關(guān)鍵之一,其拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)性對(duì)其故障檢測(cè)機(jī)制的設(shè)計(jì)提出了很大的挑戰(zhàn),具有非常重要的理論與現(xiàn)實(shí)意義[4]。

故障檢測(cè)機(jī)制作為可靠分布式系統(tǒng)的基礎(chǔ)組件已取得了階段性的成果[5]?；诜植际较到y(tǒng)故障檢測(cè)的基礎(chǔ)理論,文獻(xiàn)[6]分析了不可靠故障檢測(cè)相關(guān)概念,并結(jié)合故障檢測(cè)相關(guān)屬性劃分了故障檢測(cè)機(jī)制的基本類型。作為障檢測(cè)機(jī)制的核心,故障檢測(cè)算法均以心跳機(jī)制為基礎(chǔ)[7]。文獻(xiàn)[8]提出了一個(gè)能夠根據(jù)網(wǎng)絡(luò)狀況動(dòng)態(tài)自適應(yīng)的故障檢測(cè)算法?；谧赃m應(yīng)的故障檢測(cè)算法,文獻(xiàn)[9]提出了動(dòng)態(tài)的預(yù)測(cè)修正值的計(jì)算方法,以盡量降低檢測(cè)延遲。文獻(xiàn)[10]提出的φ-檢測(cè)器增強(qiáng)了檢測(cè)靈活性。文獻(xiàn)[11]基于灰色預(yù)測(cè)理論提出了一種基于QoS的故障檢測(cè)算法。為了應(yīng)對(duì)自組網(wǎng)系統(tǒng)故障檢測(cè)的擴(kuò)展性難題,文獻(xiàn)[12]構(gòu)建了層次式故障檢測(cè)機(jī)制。然而,上述故障檢測(cè)機(jī)制尚存在諸多缺點(diǎn)。為此,本文進(jìn)一步分析無(wú)線自組網(wǎng)對(duì)應(yīng)的故障檢測(cè)模型,并在此基礎(chǔ)上設(shè)計(jì)準(zhǔn)確高效的故障檢測(cè)算法。

2 系統(tǒng)模型

如圖1所示,所述無(wú)線自組網(wǎng)由無(wú)向圖G=(V,E)表示,其中V表示分布在設(shè)定地理區(qū)域的無(wú)線節(jié)點(diǎn),能夠在一定范圍內(nèi)活動(dòng)[1]。E為無(wú)線節(jié)點(diǎn)V之間通信鏈路的集合,若無(wú)線節(jié)點(diǎn)X和Y之間存在連接e,則意味著節(jié)點(diǎn)Y在節(jié)點(diǎn)X的傳輸范圍之內(nèi)且X也在Y的傳輸范圍之內(nèi)[2]。用NX(t)表示t時(shí)刻節(jié)點(diǎn)X相鄰節(jié)點(diǎn),即t時(shí)刻處于節(jié)點(diǎn)X傳輸范圍之內(nèi)的節(jié)點(diǎn)都是X的相鄰節(jié)點(diǎn)。假設(shè)系統(tǒng)各節(jié)點(diǎn)網(wǎng)絡(luò)鏈路為混雜模式,即無(wú)論X的相鄰節(jié)點(diǎn)是否為發(fā)送消息的目標(biāo)節(jié)點(diǎn),都可偵聽(tīng)到X發(fā)送的消息[3]。本文無(wú)線自組網(wǎng)節(jié)點(diǎn)采用隨機(jī)移動(dòng)模型,即在一段時(shí)間t內(nèi)系統(tǒng)各節(jié)點(diǎn)的移動(dòng)速度和方向是隨機(jī)的。無(wú)線節(jié)點(diǎn)移動(dòng)速度v(t)在[vmin,vmax]滿足均勻分布,無(wú)線節(jié)點(diǎn)移動(dòng)方向θ(t)在[0,2π]同樣滿足均勻分布[3-4]。

圖1 無(wú)線自組網(wǎng)結(jié)構(gòu)表示圖

假定系統(tǒng)中每個(gè)節(jié)點(diǎn)的時(shí)鐘基本一致,系統(tǒng)中節(jié)點(diǎn)通信以ω及處理延遲時(shí)間是有限但任意的[9]。本文算法主要針對(duì)失效即停止類故障事件,節(jié)點(diǎn)發(fā)生異常事件以后不能發(fā)出消息和接收消息,不會(huì)影響系統(tǒng)其他節(jié)點(diǎn)狀態(tài)[12]。

3 故障檢測(cè)架構(gòu)

故障檢測(cè)機(jī)制主要完成簇管理節(jié)點(diǎn)對(duì)內(nèi)部成員異常狀態(tài)監(jiān)控的設(shè)計(jì),具體流程如圖2所示,主要過(guò)程如下:

(1)過(guò)程1:當(dāng)系統(tǒng)節(jié)點(diǎn)收到其他節(jié)點(diǎn)的心跳信號(hào)時(shí),需要向主用簇管理節(jié)點(diǎn)轉(zhuǎn)發(fā)該信號(hào),主用簇管理節(jié)點(diǎn)的心跳信號(hào)需要被轉(zhuǎn)發(fā)至備用節(jié)點(diǎn),主用和備用簇管理節(jié)點(diǎn)根據(jù)接收到的信號(hào)對(duì)節(jié)點(diǎn)狀態(tài)進(jìn)行判定。

(2)過(guò)程2:內(nèi)部節(jié)點(diǎn)按照設(shè)定周期值向主用簇管理節(jié)點(diǎn)發(fā)送心跳信號(hào),收到心跳主用簇管理節(jié)點(diǎn)需確定成員節(jié)點(diǎn)的狀態(tài)并預(yù)測(cè)隨后心跳的到達(dá)時(shí)間。與此同時(shí),為了實(shí)現(xiàn)主用和備用簇管理節(jié)點(diǎn)之間的相互監(jiān)控,主用簇管理節(jié)點(diǎn)需要向備用節(jié)點(diǎn)發(fā)送心跳信號(hào)。

(3)過(guò)程3:依照上述過(guò)程判定,主用節(jié)點(diǎn)或備用簇管理節(jié)點(diǎn)可以確定內(nèi)部成員的是否出現(xiàn)異常。若判定出新的故障事件,則將該事件通過(guò)備用節(jié)點(diǎn)告知系統(tǒng)其他簇管理節(jié)點(diǎn),使得每個(gè)簇管理節(jié)點(diǎn)能夠了解整個(gè)系統(tǒng)的狀況。

圖2 局部成員內(nèi)部檢測(cè)流程

擔(dān)負(fù)多重角色的簇管理節(jié)點(diǎn)需完成額外計(jì)算與傳輸工作,負(fù)載與開(kāi)銷均高于系統(tǒng)其他節(jié)點(diǎn)。為了盡量避免簇管理節(jié)點(diǎn)限制系統(tǒng)故障檢測(cè)技術(shù)機(jī)制,本文對(duì)系統(tǒng)分組劃分算法進(jìn)行了相應(yīng)調(diào)整,在確定系統(tǒng)簇管理節(jié)點(diǎn)時(shí)需要分別確定主用和備用節(jié)點(diǎn),以支撐主用和備用節(jié)點(diǎn)間相互監(jiān)控和簇間異常狀態(tài)的高效傳遞,備用節(jié)點(diǎn)平時(shí)擔(dān)負(fù)簇間異常狀態(tài)消息傳送功能以降低主用節(jié)點(diǎn)的負(fù)載。與此同時(shí),一旦備用節(jié)點(diǎn)檢測(cè)到主用節(jié)點(diǎn)發(fā)生異常,備用節(jié)點(diǎn)可快速接管主用節(jié)點(diǎn)的功能,可以盡量降低主用節(jié)點(diǎn)異常對(duì)整個(gè)系統(tǒng)故障檢測(cè)機(jī)制的影響。

4 故障檢測(cè)算法

分布式系統(tǒng)中各節(jié)點(diǎn)均具備各自的異常監(jiān)控模塊Exception_M,異常監(jiān)控模塊Exception_M使用集合ALL_LIST保存所有節(jié)點(diǎn)的標(biāo)識(shí),并通過(guò)下述過(guò)程對(duì)心跳信號(hào)進(jìn)行計(jì)算和預(yù)判:

(1)計(jì)算預(yù)判值。由于無(wú)線自組網(wǎng)具備節(jié)點(diǎn)位置不定和限定續(xù)航時(shí)間的局限,因此需要盡量降低故障檢測(cè)對(duì)系統(tǒng)處理和傳輸負(fù)載。心跳信號(hào)的預(yù)判值可通過(guò)下式計(jì)算得到:其中,用Δ(t)表示心跳信號(hào)的參數(shù)值;d—i表示心跳信號(hào)延遲期望值。

(2)計(jì)算調(diào)整量。調(diào)整心跳信號(hào)預(yù)判值用于體現(xiàn)系統(tǒng)不同網(wǎng)絡(luò)狀況對(duì)預(yù)判值的調(diào)整,以降低節(jié)點(diǎn)異常誤判的概率。心跳信號(hào)預(yù)判值調(diào)整量αi+1可通過(guò)下式得到,其中,參數(shù)β∈(0,1);ε為設(shè)定的定值[12]。

(3)預(yù)判心跳信號(hào)。心跳信號(hào)的最終預(yù)判值可通過(guò)下式確定,參數(shù)γ是預(yù)判值變化值的調(diào)整變量。

具體的故障檢測(cè)機(jī)制共包括INIT_HBS,DEAL_ TOS和DEAL_HBS 3個(gè)部分,INIT_HBS主要依照配置定期觸發(fā)心跳信號(hào)的功能,DEAL_TOS主要依據(jù)預(yù)判值完成對(duì)心跳信號(hào)的檢測(cè)功能,若超過(guò)預(yù)判值仍未接收到心跳信號(hào)則可推測(cè)被監(jiān)控節(jié)點(diǎn)出現(xiàn)異常事件,需及時(shí)記錄被監(jiān)控節(jié)點(diǎn)的狀態(tài)信息。DEAL_HBS主要通過(guò)初始預(yù)判值,以及對(duì)其的調(diào)整,完成準(zhǔn)確預(yù)判心跳信號(hào)的功能。涉及預(yù)判的處理過(guò)程COMP_ DEST如下:

在COMP_DEST處理過(guò)程中,記Suspectp為監(jiān)控節(jié)點(diǎn)p推測(cè)的異常節(jié)點(diǎn)的集合;記Informersp[q]為參與傳輸q的心跳信號(hào)給p的節(jié)點(diǎn)。記ArrivalTimesp[q]為節(jié)點(diǎn)p保存的節(jié)點(diǎn)q的心跳信號(hào)預(yù)判值;記Heartbeatsp[q]為監(jiān)控節(jié)點(diǎn)p上保存的被監(jiān)控節(jié)點(diǎn)q的心跳信號(hào)計(jì)數(shù)值。根據(jù)上述檢測(cè)算法,心跳信號(hào)預(yù)判值的調(diào)整可通過(guò)DEST_UP實(shí)現(xiàn),監(jiān)控節(jié)點(diǎn)p根據(jù)當(dāng)前已得到的被監(jiān)控節(jié)點(diǎn)q的心跳信號(hào)對(duì)后續(xù)心跳信號(hào)預(yù)判值進(jìn)行調(diào)整,具體過(guò)程如下:

被監(jiān)控節(jié)點(diǎn)INIT_HBS的主要處理過(guò)程如下所示,即按照設(shè)定周期值產(chǎn)生自身的心跳信號(hào)。

DEAL_HBS模塊主要完成調(diào)整心跳信號(hào)預(yù)判值的功能,通過(guò)收到的心跳信號(hào)數(shù)量得到后續(xù)的預(yù)判值,這里用tmr表示監(jiān)控節(jié)點(diǎn)p可用的時(shí)間值。

DEAL_TOS模塊主要處理過(guò)程如下所示,依據(jù)預(yù)判值完成對(duì)實(shí)際心跳信號(hào)的監(jiān)控功能。

5 性能分析

通過(guò)NS仿真軟件設(shè)定無(wú)線自組網(wǎng)設(shè)定為1000 m×1000 m的區(qū)域,系統(tǒng)中包含50個(gè)節(jié)點(diǎn),設(shè)置節(jié)點(diǎn)移動(dòng)模型為隨機(jī)移動(dòng)模型且速度處于[2 m/s,20 m/s]區(qū)間[4]。網(wǎng)絡(luò)設(shè)置為DSR路由協(xié)議、IP協(xié)議、IEEE 802.11,應(yīng)用層設(shè)置為固定頻率的CBR會(huì)話,并且源節(jié)點(diǎn)按照周期值向目的節(jié)點(diǎn)發(fā)送固定大小的報(bào)文[5]。選取NFD_E和TAM_FD這2種具有代表性的算法進(jìn)行對(duì)比[3]。如圖3所示, 3種機(jī)制的平均錯(cuò)誤率均隨著檢測(cè)時(shí)間的增加而降低,總體上本文算法最優(yōu)。相同檢測(cè)時(shí)間情況下本文算法比NFD_E和TAM_FD具備更低的平均錯(cuò)誤率,而NFD_E具備最高的平均錯(cuò)誤率,TAM_FD的平均錯(cuò)誤率介于NFD_E和本文算法之間。經(jīng)分析,這是由于本文故障檢測(cè)機(jī)制采用了冗余簇管理節(jié)點(diǎn)的模式,并提出了更加準(zhǔn)確的算法用于心跳信號(hào)預(yù)判。

圖3 3種算法平均錯(cuò)誤率對(duì)比

查詢準(zhǔn)確率是檢測(cè)機(jī)制在一定時(shí)間段內(nèi)輸出正確結(jié)果的比率,是反映檢測(cè)準(zhǔn)確性的重要指標(biāo)[4]。如圖4所示,3種機(jī)制的查詢準(zhǔn)確率均隨著檢測(cè)時(shí)間的增加而增加,總體上本文算法的查詢準(zhǔn)確率高于TAM_FD和NFD_E。在相同檢測(cè)時(shí)間情況下, NFD_E的查詢準(zhǔn)確率最低,但是隨著系統(tǒng)檢測(cè)時(shí)間的不斷增加出現(xiàn)了局部震蕩,最終只能穩(wěn)定于90%左右,這是由于其固定調(diào)整值的方法無(wú)法完全適用于易變的無(wú)線自組網(wǎng)。不同于NFD_E算法,TAM_ FD算法的查詢準(zhǔn)確率隨著系統(tǒng)檢測(cè)時(shí)間的不斷增加總體變化較平穩(wěn),最終能夠穩(wěn)定于95%左右。本文算法的查詢準(zhǔn)確率初始時(shí)與TAM_FD大體相當(dāng),但隨著系統(tǒng)檢測(cè)時(shí)間的不斷增加最終高于后者,穩(wěn)定于97%左右。經(jīng)分析,這是由于本文算法設(shè)計(jì)了更準(zhǔn)確的心跳信號(hào)預(yù)判調(diào)整方法。

圖4 3種算法查詢準(zhǔn)確率對(duì)比

6 結(jié)束語(yǔ)

通過(guò)分析無(wú)線自組網(wǎng)分布式系統(tǒng)故障檢測(cè)研究存在的問(wèn)題,本文提出一種面向無(wú)線自組網(wǎng)的高效故障檢測(cè)算法,分簇時(shí)分別確定主用和備用簇管理節(jié)點(diǎn),冗余的簇管理節(jié)點(diǎn)負(fù)責(zé)對(duì)內(nèi)部成員實(shí)施異常檢測(cè),心跳預(yù)判實(shí)時(shí)調(diào)整機(jī)制確保算法能夠動(dòng)態(tài)適應(yīng)自組網(wǎng)易變的拓?fù)浣Y(jié)構(gòu),并通過(guò)備用簇管理節(jié)點(diǎn)和簇間共享異常信息機(jī)制提高系統(tǒng)故障檢測(cè)的可靠性。最后利用仿真實(shí)驗(yàn)對(duì)故障檢測(cè)機(jī)制的性能進(jìn)行評(píng)估,結(jié)果表明,設(shè)計(jì)的故障檢測(cè)算法具有較好的可擴(kuò)展性、較低的平均錯(cuò)誤率和較高的查詢準(zhǔn)確率,能夠較好地適應(yīng)大規(guī)模的無(wú)線自組網(wǎng)系統(tǒng)。

[1] Stewart W,Gabriel A,James W.Fault Detection for Vehicular AdhocWirelessNetworks[J].IEEE IntelligentTransportationSystemsMagazine,2014, 6(2):34-44.

[2] 唐明珠,陽(yáng)春華,桂衛(wèi)華.基于改進(jìn)的QBC和CS-SVM的故障檢測(cè)[J].控制與決策,2012,27(10): 1489-1493.

[3] Ekin K O,Ridha M A,Onur O,et al.Survivability in Hierarchical Telecommunications Networks Under Dual Homing[J].INFORMS Journal on Computing,2014, 26(1):1-15.

[4] 胡景龍.基于分簇的Ad Hoc網(wǎng)絡(luò)結(jié)點(diǎn)故障檢測(cè)技術(shù)研究[D].哈爾濱:哈爾濱工程大學(xué),2010.

[5] Chandra T D,Toueg S.Unreliable Failure Detectors for Reliable Distributed Systems[J].Journal of ACM, 1996,43(2):225-267.

[6] Larrea M,FernándezA,ArevaloS.Eventually Consistent Failure Detectors[J].Jounal of Parallel and Distributing Computing,2005,65(3):361-373.

[7] Zhang Jianhua,Song Bo,Zhang Zhaojun,et al.An Approach for Modeling Vulnerability of the Network of Networks[J].Physica A:Statistical Mechanics and Its Applications,2014,412:127-136.

[8] Bertier M,MarinO,SensP.Implementationand Performance Evaluation of an Adaptable Failure Detector[C]//Proceedingsofthe15thInternational Conference on Dependable SystemsandNetworks. Bethesda,USA:[s.n.],2002:354-363.

[9] Hayashibara N,DefagoX,KatayamaT.Two-ways Adaptive Failure Detectionwiththeφ-failureDetector[C]//ProceedingsofWorkshoponAdaptive Distributed Systems.Sorrento,Italy:[s.n.],2003: 22-27.

[10] 田 東,陳蜀宇,陳 鋒.一種網(wǎng)格環(huán)境下的動(dòng)態(tài)故障檢測(cè)算法[J].計(jì)算機(jī)研究與發(fā)展,2006,43(11): 1870-1875.

[11] Hayashibara N,Cherif A,Katayama T.Failure Detectors for Large-scale Distributed Systems[C]//Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems.Osaka,Japan:[s.n.],2002:404-409.

[12] Camp T,Boleng J,Davies V.A Survey of Mobility Models for Ad hoc Network Research[J].Wireless Communications and Mobile Computing,2002,2(5): 483-502.

編輯 顧逸斐

A Failure Detection Algorithm for Ad Hoc Network

XU Zhenpeng1,SHEN Hao2,ZENG Weini2
(1.JARI Deepsoft Technology Co.,Ltd.,Lianyungang 222061,China;
2.Jiangsu Automation Research Institute,Lianyungang 222061,China)

A failure detection architecture and algorithm based on clustering are proposed according to the topology of Ad Hoc networks.The active and the backup cluster manager are designated respectively.The exception detection function of the members is implemented by the selected redundancy cluster managers.The sending,monitoring,prediction and updating process of the heartbeat message are designed for fault detection.The updating method of the heartbeat prediction is added to fit the variable topology of Ad Hoc networks dynamically.Through the backup cluster manager and the exception data shared mechanisms among clusters,the system fault detection reliability is improved.The proposal is evaluated by the simulation.As a result,the proposed failure detection mechanism achieves a high accuracy,and is capable of the requirement of the top application design for the system reliability.

Ad Hoc network;fault tolerance;node failure;fault detection;heartbeat anticipation

徐振朋,沈 浩,曾瑋妮.一種無(wú)線自組網(wǎng)故障檢測(cè)算法[J].計(jì)算機(jī)工程,2015,41(2):313-316.

英文引用格式:Xu Zhenpeng,Shen Hao,Zeng Weini.A Failure Detection Algorithm for Ad Hoc Network[J].Computer Engineering,2015,41(2):313-316.

1000-3428(2015)02-0313-04

:A

:TP301.6

10.3969/j.issn.1000-3428.2015.02.060

國(guó)家自然科學(xué)基金資助項(xiàng)目(61303045);江蘇省自然科學(xué)基金資助項(xiàng)目(BK2012237)。

徐振朋(1983-),男,高級(jí)工程師、博士,主研方向:普適計(jì)算,分布式計(jì)算;沈 浩,工程師、碩士;曾瑋妮,高級(jí)工程師、博士。

2014-08-28

:2014-10-27E-mail:xuzhenpeng@jari.cn