徐振朋,沈 浩,曾瑋妮

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

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

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

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

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

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

1 概述

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

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

2 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

擔(dān)負(fù)多重角色的簇管理節(jié)點(diǎn)需完成額外計(jì)算與傳輸工作,負(fù)載與開銷均高于系統(tǒng)其他節(jié)點(diǎn)。為了盡量避免簇管理節(jié)點(diǎn)限制系統(tǒng)故障檢測技術(shù)機(jī)制,本文對系統(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)檢測到主用節(jié)點(diǎn)發(fā)生異常,備用節(jié)點(diǎn)可快速接管主用節(jié)點(diǎn)的功能,可以盡量降低主用節(jié)點(diǎn)異常對整個(gè)系統(tǒng)故障檢測機(jī)制的影響。

4 故障檢測算法

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

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

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

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

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

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

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

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

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

5 性能分析

通過NS仿真軟件設(shè)定無線自組網(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)行對比[3]。如圖3所示, 3種機(jī)制的平均錯(cuò)誤率均隨著檢測時(shí)間的增加而降低,總體上本文算法最優(yōu)。相同檢測時(shí)間情況下本文算法比NFD_E和TAM_FD具備更低的平均錯(cuò)誤率,而NFD_E具備最高的平均錯(cuò)誤率,TAM_FD的平均錯(cuò)誤率介于NFD_E和本文算法之間。經(jīng)分析,這是由于本文故障檢測機(jī)制采用了冗余簇管理節(jié)點(diǎn)的模式,并提出了更加準(zhǔn)確的算法用于心跳信號預(yù)判。

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

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

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

6 結(jié)束語

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

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

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

2014-08-28

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