一種無線自組網故障檢測算法

徐振朋,沈 浩,曾瑋妮

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

一種無線自組網故障檢測算法

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

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

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

無線自組網;容錯;節點故障;故障檢測;心跳預判

1 概述

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

故障檢測機制作為可靠分布式系統的基礎組件已取得了階段性的成果[5]。基于分布式系統故障檢測的基礎理論,文獻[6]分析了不可靠故障檢測相關概念,并結合故障檢測相關屬性劃分了故障檢測機制的基本類型。作為障檢測機制的核心,故障檢測算法均以心跳機制為基礎[7]。文獻[8]提出了一個能夠根據網絡狀況動態自適應的故障檢測算法。基于自適應的故障檢測算法,文獻[9]提出了動態的預測修正值的計算方法,以盡量降低檢測延遲。文獻[10]提出的φ-檢測器增強了檢測靈活性。文獻[11]基于灰色預測理論提出了一種基于QoS的故障檢測算法。為了應對自組網系統故障檢測的擴展性難題,文獻[12]構建了層次式故障檢測機制。然而,上述故障檢測機制尚存在諸多缺點。為此,本文進一步分析無線自組網對應的故障檢測模型,并在此基礎上設計準確高效的故障檢測算法。

2 系統模型

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

圖1 無線自組網結構表示圖

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

3 故障檢測架構

故障檢測機制主要完成簇管理節點對內部成員異常狀態監控的設計,具體流程如圖2所示,主要過程如下:

(1)過程1:當系統節點收到其他節點的心跳信號時,需要向主用簇管理節點轉發該信號,主用簇管理節點的心跳信號需要被轉發至備用節點,主用和備用簇管理節點根據接收到的信號對節點狀態進行判定。

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

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

圖2 局部成員內部檢測流程

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

4 故障檢測算法

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

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

(2)計算調整量。調整心跳信號預判值用于體現系統不同網絡狀況對預判值的調整,以降低節點異常誤判的概率。心跳信號預判值調整量αi+1可通過下式得到,其中,參數β∈(0,1);ε為設定的定值[12]。

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

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

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

被監控節點INIT_HBS的主要處理過程如下所示,即按照設定周期值產生自身的心跳信號。

DEAL_HBS模塊主要完成調整心跳信號預判值的功能,通過收到的心跳信號數量得到后續的預判值,這里用tmr表示監控節點p可用的時間值。

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

5 性能分析

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

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

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

圖4 3種算法查詢準確率對比

6 結束語

通過分析無線自組網分布式系統故障檢測研究存在的問題,本文提出一種面向無線自組網的高效故障檢測算法,分簇時分別確定主用和備用簇管理節點,冗余的簇管理節點負責對內部成員實施異常檢測,心跳預判實時調整機制確保算法能夠動態適應自組網易變的拓撲結構,并通過備用簇管理節點和簇間共享異常信息機制提高系統故障檢測的可靠性。最后利用仿真實驗對故障檢測機制的性能進行評估,結果表明,設計的故障檢測算法具有較好的可擴展性、較低的平均錯誤率和較高的查詢準確率,能夠較好地適應大規模的無線自組網系統。

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

[2] 唐明珠,陽春華,桂衛華.基于改進的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網絡結點故障檢測技術研究[D].哈爾濱:哈爾濱工程大學,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] 田 東,陳蜀宇,陳 鋒.一種網格環境下的動態故障檢測算法[J].計算機研究與發展,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

徐振朋,沈 浩,曾瑋妮.一種無線自組網故障檢測算法[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

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

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

2014-08-28

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