徐振朋,沈 浩,曾瑋妮

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

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

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

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

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

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

1 概述

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

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

2 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

4 故障檢測算法

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

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

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

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

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

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

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

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

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

5 性能分析

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

圖3 3種算法平均錯誤率對比

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

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

6 結(jié)束語

通過分析無線自組網(wǎng)分布式系統(tǒng)故障檢測研究存在的問題,本文提出一種面向無線自組網(wǎng)的高效故障檢測算法,分簇時分別確定主用和備用簇管理節(jié)點,冗余的簇管理節(jié)點負責(zé)對內(nèi)部成員實施異常檢測,心跳預(yù)判實時調(diào)整機制確保算法能夠動態(tài)適應(yīng)自組網(wǎng)易變的拓撲結(jié)構(gòu),并通過備用簇管理節(jié)點和簇間共享異常信息機制提高系統(tǒng)故障檢測的可靠性。最后利用仿真實驗對故障檢測機制的性能進行評估,結(jié)果表明,設(shè)計的故障檢測算法具有較好的可擴展性、較低的平均錯誤率和較高的查詢準(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)華.基于改進的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é)點故障檢測技術(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)境下的動態(tài)故障檢測算法[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].計算機工程,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é)基金資助項目(61303045);江蘇省自然科學(xué)基金資助項目(BK2012237)。

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

2014-08-28

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