一種用于Ad Hoc網(wǎng)絡(luò)的自適應(yīng)故障檢測算法

李 香，門朝光，何忠政

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001)

故障檢測器是構(gòu)建可靠分布式應(yīng)用系統(tǒng)的基礎(chǔ)組件之一［1］。對于具有分布式特性的Ad Hoc網(wǎng)絡(luò)，其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)易變，帶寬、能源有限，網(wǎng)絡(luò)中結(jié)點(diǎn)發(fā)生故障的概率較高，故障檢測服務(wù)是提高系統(tǒng)可靠性和安全性的有效手段之一。Ad Hoc網(wǎng)絡(luò)中需要著重考慮故障檢測機(jī)制的自適應(yīng)性和可擴(kuò)展性，以適應(yīng)網(wǎng)絡(luò)拓?fù)渥兓４送猓收蠙z測器的服務(wù)質(zhì)量(QoS)需要依靠超時(shí)值的正確設(shè)定，一個(gè)過小的超時(shí)值能快速檢測到節(jié)點(diǎn)是否出現(xiàn)故障，但同時(shí)也會(huì)增加判斷錯(cuò)誤的次數(shù)，減少故障檢測器的準(zhǔn)確率，而過大的超時(shí)值雖然能減少判斷錯(cuò)誤的次數(shù)，提高準(zhǔn)確率，但又會(huì)增加檢測時(shí)間，使SAN的收斂時(shí)間延長，因此故障檢測器應(yīng)達(dá)到快速性和準(zhǔn)確性的平衡［2］。在分布式系統(tǒng)故障檢測算法的基礎(chǔ)上，專家和學(xué)者針對Ad Hoc網(wǎng)絡(luò)高度動(dòng)態(tài)變化的拓?fù)浣Y(jié)構(gòu)、分布式等特性提出了一些Ad Hoc網(wǎng)絡(luò)故障檢測算法［3-5］。此外，故障檢測器可用來解決分布式系統(tǒng)中的一些基本問題，如一致性和原子提交問題［6，7］。本文基于Xiong的故障檢測算法TAM FD［8］，提出了適應(yīng)于Ad Hoc網(wǎng)絡(luò)的故障檢測算法，通過對心跳消息到達(dá)時(shí)間進(jìn)行動(dòng)態(tài)預(yù)測并實(shí)時(shí)更新調(diào)整，以減少網(wǎng)絡(luò)狀態(tài)變化對預(yù)測時(shí)間的影響，從而盡量避免故障檢測器發(fā)生錯(cuò)誤的判斷。

1 系統(tǒng)模型

系統(tǒng)由n個(gè)結(jié)點(diǎn)組成，∏為結(jié)點(diǎn)集合。假設(shè)故障類型為Fail-Stop，結(jié)點(diǎn)之間通過可靠的通信信道連接，如果結(jié)點(diǎn)q向p發(fā)送一條心跳消息，除非p本身發(fā)生故障，否則它最終會(huì)收到該消息。每一個(gè)故障檢測器輸出一個(gè)當(dāng)前被懷疑為故障的結(jié)點(diǎn)集合Suspectsi。故障檢測器的歷史H被定義為:H:∏×T→2∏。H(p，t)是t時(shí)刻故障檢測器對結(jié)點(diǎn)p的判斷。如果q∈H(p，t)，則認(rèn)為在t時(shí)刻p懷疑q［9］。

系統(tǒng)存在一個(gè)全局時(shí)鐘，系統(tǒng)中消息的發(fā)送、傳輸及處理時(shí)間，即消息傳輸延遲有上限，設(shè)全局穩(wěn)定時(shí)間GST之后結(jié)點(diǎn)間一跳消息傳輸延遲的最大值為Δmessage。

根據(jù)以上系統(tǒng)模型和假設(shè)，定義故障檢測級(jí)別如下:

(1)強(qiáng)完整性:每一個(gè)故障的結(jié)點(diǎn)最終都會(huì)被所有正確的結(jié)點(diǎn)永遠(yuǎn)判定為故障。

(2)最終強(qiáng)準(zhǔn)確性:存在某個(gè)時(shí)間t，在此之后，每個(gè)正確的結(jié)點(diǎn)都不會(huì)被任意一個(gè)正確結(jié)點(diǎn)判定為故障。

2 自適應(yīng)故障檢測算法

2.1 基本思想

被檢測結(jié)點(diǎn)q周期性地向檢測結(jié)點(diǎn)p發(fā)送心跳消息，每個(gè)發(fā)送消息的序號(hào)順序遞增。p根據(jù)最近i次接收到的心跳消息到達(dá)時(shí)間和預(yù)測策略，預(yù)測第i+1次心跳消息到達(dá)時(shí)間。如果在預(yù)測的時(shí)間內(nèi)檢測結(jié)點(diǎn)p沒有收到被檢測結(jié)點(diǎn)q發(fā)來的心跳消息，則懷疑q故障;如果p之后收到q發(fā)來的心跳消息，則取消對該結(jié)點(diǎn)q的懷疑。

2.2 超時(shí)值預(yù)測模型

基于心跳策略的故障檢測算法的核心是對心跳到達(dá)超時(shí)值的預(yù)測，自適應(yīng)故障檢測算法大多是根據(jù)系統(tǒng)狀態(tài)對心跳消息到達(dá)時(shí)間的預(yù)測超時(shí)值進(jìn)行調(diào)整。

其中:為最近i個(gè)心跳消息到達(dá)時(shí)間延遲的平均值。

采用Chen［10］類似方法，引入固定修正值αi+1對EAi+1進(jìn)行調(diào)整，以反映系統(tǒng)的動(dòng)態(tài)變化，并減少網(wǎng)絡(luò)狀況對預(yù)測時(shí)間的影響。修正值αi+1計(jì)算公式如下:

對EAi+1進(jìn)行調(diào)整，得到心跳消息到達(dá)時(shí)間的預(yù)測超時(shí)值τi+1為:

其中γ為調(diào)節(jié)系數(shù)。

2 .3 故障檢測算法

采用基于PUSH類型的心跳策略，根據(jù)網(wǎng)絡(luò)狀態(tài)預(yù)測并自適應(yīng)調(diào)節(jié)超時(shí)值，以確保故障檢測的實(shí)時(shí)動(dòng)態(tài)性，從而滿足上層應(yīng)用的需求。提出的Ad Hoc網(wǎng)絡(luò)環(huán)境下的故障檢測算法如下:

故障檢測算法.

算法的主要工作機(jī)理如下:

Task 1.被檢測結(jié)點(diǎn)q以間隔Δ周期性地向檢測結(jié)點(diǎn)p發(fā)送心跳消息。

Task 3.如果在預(yù)測的時(shí)間內(nèi)，p未收到q發(fā)送的心跳消息，則p懷疑q故障。

2.4 算法證明

引理1

如果在tcrash時(shí)刻被檢測結(jié)點(diǎn)發(fā)生故障，則存在一個(gè)時(shí)刻tmute，在此之后檢測結(jié)點(diǎn)p不會(huì)接收到被檢測結(jié)點(diǎn)q發(fā)送的消息。

網(wǎng)絡(luò)中結(jié)點(diǎn)個(gè)數(shù)為N，有:

證明:最壞情況下，網(wǎng)絡(luò)為線性結(jié)構(gòu)，且p和q相距N-1跳，則q的心跳消息經(jīng)過(N-1)個(gè)心跳間隔和傳輸延遲到達(dá)p。全局穩(wěn)定時(shí)間GST后，一跳結(jié)點(diǎn)間消息傳輸延遲上界為Δmessage。因此，最壞情況下，若q在tcrash時(shí)刻故障，停止發(fā)送心跳消息，則存在時(shí)刻tcrash+(N-1)(Δ+Δmessage)，在此之后p不會(huì)接收到q發(fā)送的消息。故引理1成立。

引理2

假設(shè)檢測結(jié)點(diǎn)p從被檢測結(jié)點(diǎn)q接收了i個(gè)心跳消息序列，當(dāng)p不再從q接收任何的直接或間接心跳消息時(shí)，存在一個(gè)時(shí)刻后p開始懷疑q。

證明:當(dāng)p從q接收到i個(gè)心跳消息，它會(huì)預(yù)測下一個(gè)心跳消息到達(dá)時(shí)間之后p開始懷疑q。那么，當(dāng)收斂時(shí)，肯定存在p開始懷疑q的時(shí)刻。因此，只需證明有界。

根據(jù)文獻(xiàn)［8］中證明，以下式子(7)、(8)成立:

若只接收到一條最新心跳消息，無重復(fù)最新心跳消息存在，由算法1有由(7)、(8)得 τi+1有界，即有界。

若接收到重復(fù)最新心跳消息，則由算法1有。結(jié)合式(7)、(8)，只需證明更新有界。如引理1所述，在最壞情況下，除q之外p的所有鄰居結(jié)點(diǎn)都在轉(zhuǎn)發(fā)該重復(fù)最新心跳消息的路徑中，則p至多在(N-2)(Δ+Δmessage)時(shí)長之后接收到來自q的重復(fù)最新心跳消息。因此，有，可計(jì)算出有界，即預(yù)測時(shí)間的更新值有界。

故有界，即引理2成立。

定理1

(強(qiáng)完整性)本文設(shè)計(jì)的故障檢測算法滿足強(qiáng)完整性要求，即

證明:如果引理1，2被證明，則定理1成立。即存在一個(gè)時(shí)刻tmute，在此之后沒有一個(gè)正確的檢測結(jié)點(diǎn)收到發(fā)生故障的被檢測結(jié)點(diǎn)發(fā)送的心跳消息;存在一個(gè)時(shí)刻ttimeout，在此之后所有正確的檢測結(jié)點(diǎn)會(huì)永久性地判定被檢測結(jié)點(diǎn)發(fā)生故障。

由引理1和引理2可得定理1成立。證畢。

定理2

(最終強(qiáng)準(zhǔn)確性)本文設(shè)計(jì)的故障檢測算法滿足最終強(qiáng)準(zhǔn)確性要求，即

證明:由引理1可知，除非結(jié)點(diǎn)發(fā)生故障，否則心跳消息一定會(huì)在(N-1)(Δ+Δmessage)之前到達(dá)p。設(shè)tk+1為k+1次心跳消息實(shí)際到達(dá)時(shí)間，有tk+1＜(N-1)(Δ+Δmessage)。

因此，存在時(shí)間t為(N-1)(Δ+Δmessage)，在此之后，每個(gè)正確的結(jié)點(diǎn)都不會(huì)被任意一個(gè)正確結(jié)點(diǎn)判定為故障。證畢。

3 實(shí)驗(yàn)結(jié)果

仿真實(shí)驗(yàn)在Windows XP SP3環(huán)境下使用GloMoSim進(jìn)行模擬仿真。50個(gè)結(jié)點(diǎn)在1000×1000m2范圍內(nèi)采取隨機(jī)移動(dòng)模型以2m/s-20m/s速度勻速移動(dòng)，MAC層采用IEEE 802.11協(xié)議，網(wǎng)絡(luò)層采用IP協(xié)議，應(yīng)用層采用CBR協(xié)議，采用DSR路由協(xié)議源結(jié)點(diǎn)周期性地向目的結(jié)點(diǎn)發(fā)送固定尺寸的報(bào)文。

心跳消息發(fā)送間隔為5000ms，初始超時(shí)值為5500ms，對預(yù)測和實(shí)際超時(shí)值進(jìn)行比較。如圖1所示:實(shí)際超時(shí)值近似于固定值;隨著心跳消息的增多，預(yù)測超時(shí)值逐漸趨近于實(shí)際超時(shí)值。因此，本文故障檢測算法可以準(zhǔn)確地對超時(shí)值做出預(yù)測。

圖1 超時(shí)值比較

平均錯(cuò)誤率λM和查詢準(zhǔn)確率PA經(jīng)常被用來評價(jià)故障檢測算法的準(zhǔn)確性，且需要兩者結(jié)合來檢驗(yàn)［10］。心跳消息發(fā)送間隔為1000ms，接收窗口大小為500，實(shí)驗(yàn)統(tǒng)計(jì)接收消息達(dá)到500以后λM、PA隨檢測時(shí)間變化的曲線，對故障檢測算法的準(zhǔn)確性進(jìn)行檢驗(yàn)。

圖2對比了NFD-E［10］、TAM FD［8］、本文故障檢測算法的平均錯(cuò)誤率。從圖中可以看出:隨著檢測時(shí)間的增長，算法的平均錯(cuò)誤率逐漸降低;當(dāng)檢測時(shí)間達(dá)到500ms時(shí)，平均錯(cuò)誤率達(dá)到10-2級(jí)別，具有較低的平均錯(cuò)誤率，這表明故障檢測器在單位時(shí)間內(nèi)發(fā)生誤判的概率較小，有效地避免了狀態(tài)切換帶來的系統(tǒng)開銷，從而提高故障檢測的性能。其中，本文算法的平均錯(cuò)誤率最低，這是由于本文算法充分考慮Ad Hoc網(wǎng)絡(luò)特點(diǎn)，根據(jù)接收到的心跳消息實(shí)時(shí)動(dòng)態(tài)更新預(yù)測超時(shí)值，從而能更好地適應(yīng)Ad Hoc網(wǎng)絡(luò)環(huán)境。

NFD-E、TAM FD、本文故障檢測算法查詢準(zhǔn)確率隨檢測時(shí)間變化的情況如圖3所示。隨著檢測時(shí)間的增長，查詢準(zhǔn)確率不斷提高，在600ms后查詢準(zhǔn)確率超過97%，表明故障檢測器輸出正確的概率較高。其中，NFD-E查詢準(zhǔn)確率相對較差，隨著檢測時(shí)間的增長，查詢準(zhǔn)確率停留在90%左右，且波動(dòng)較大，可見固定的修正值不適合動(dòng)態(tài)的Ad Hoc網(wǎng)絡(luò)環(huán)境。TAM FD隨著檢測時(shí)間的增長，查詢準(zhǔn)確率平穩(wěn)上升，一定時(shí)間后趨于平衡。本文故障檢測算法在檢測時(shí)間較小時(shí)與TAM FD性能基本一致;隨著檢測時(shí)間的增長，達(dá)到500ms以后，本文算法的查詢準(zhǔn)確率高于TAM FD。

圖2 不同算法平均錯(cuò)誤率比較

圖3 不同算法查詢準(zhǔn)確率比較

4 結(jié)語

該文提出了一個(gè)Ad Hoc網(wǎng)絡(luò)環(huán)境下的故障檢測算法，算法根據(jù)網(wǎng)絡(luò)狀況動(dòng)態(tài)的調(diào)節(jié)預(yù)測超時(shí)時(shí)間;針對Ad Hoc網(wǎng)絡(luò)多跳通信和結(jié)點(diǎn)混雜工作模式等特點(diǎn)，對預(yù)測時(shí)間進(jìn)行更新。理論證明，算法滿足強(qiáng)完整性和最終強(qiáng)準(zhǔn)確性，是一個(gè)?P類故障檢測器。仿真實(shí)驗(yàn)表明:算法可以準(zhǔn)確地對超時(shí)值做出預(yù)測;算法的平均錯(cuò)誤率低、查詢準(zhǔn)確率高，具有較好的檢測準(zhǔn)確性指標(biāo)。

［1］Pasin M，F(xiàn)ontaine S，Bouchenak S.Failure Detection in Large Scale Systems:a Survey［C］//IEEE Network Operations and Management Symposium Workshops.Salvador，2008:165-168.

［2］楊光.存儲(chǔ)區(qū)域網(wǎng)中基于神經(jīng)網(wǎng)絡(luò)故障檢測器的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(33):10-12.

［3］Friedman R，Tcharny G.Evaluating failure detection in mobile ad-hoc networks［J］.International Journal of Wireless and Mobile Computing，2005，1(8):1-3.

［4］Elhadef M，Boukerche A.A Gossip-Style Crash Faults Detection Protocol for Wireless Ad-Hoc and Mesh Networks［C］//Proceedings of IPCCC.New Orleans，2007:600-605.

［5］Elhadef M，Abdun-Nur F.Adaptable Crash Faults Detector for Mobile Ad-Hoc Networks［C］//Proceedings of AINAW’07.Niagara Falls，2007:207-212.

［6］Chockler G，Demirbas M，Gilbert S.Consensus and collision detectors in wireless ad hoc networks［C］//24th Annual Symposium on the Principles of Distributed Computing(PODC).Las Vegas，2005:197-206.

［7］Wu W，Cao J，Yang J.A hierarchical consensus protocol for mobile ad hoc networks［C］//Proceedings of the 14th Euromicro International Conference on Parallel，Distributed，and Network-Based Processing(PDP’06).Washington，DC，2006:64-72.

［8］Xiong N，Vasilakos A.Comparative analysis of quality of service and memory usage for adaptive failure detectors in healthcare systems［J］.IEEE Journal on Selected Areas in Communications，2009，27(4):495-509.

［9］Chandra T D，Toueg S.Unreliable failure detectors for reliable distributed systems［J］.Journal of ACM，1996，43(2):225-267.

［10］Chen W，Toueg S，Aguilera M K.On the quality of service of failure detectors［J］.IEEE Transactions on Computers，2002，51(5):561-580.