有損網(wǎng)絡(luò)中基于計(jì)時(shí)器的節(jié)點(diǎn)故障檢測模型研究

趙英姿

有損網(wǎng)絡(luò)中基于計(jì)時(shí)器的節(jié)點(diǎn)故障檢測模型研究

趙英姿

當(dāng)前大多數(shù)不可靠故障檢測器利用可靠的通信鏈路來通知完全連通網(wǎng)絡(luò)中的故障，且在部署時(shí)沒有考慮能量、存儲(chǔ)和帶寬方面的資源約束，不適用于有損網(wǎng)絡(luò)?；诖耍岢鲆环N低功耗有損網(wǎng)絡(luò)故障檢測模型ALLONE。該模型在考慮無線鏈路間歇性故障的條件下，利用自適應(yīng)計(jì)時(shí)器實(shí)現(xiàn)節(jié)點(diǎn)故障檢測。此外，提出兩種計(jì)時(shí)器調(diào)整技術(shù)，實(shí)現(xiàn)多應(yīng)用場景下ALLONE的運(yùn)行性能調(diào)整。在Omnet++/Mixim框架下對(duì)模型和方法進(jìn)行評(píng)估。仿真結(jié)果表明，與其他方法相比，其方法提高了故障檢測和恢復(fù)率，降低了報(bào)文丟失率和故障陽性檢測率，沒有增加能耗開銷。

故障檢測；有損網(wǎng)絡(luò)；資源約束；計(jì)時(shí)器

0 引言

不可靠故障檢測器是分布式系統(tǒng)的一個(gè)重要服務(wù)。Chandra和Toueg等人[1]闡述了故障檢測的重要意義，將故障檢測器定義為每個(gè)進(jìn)程的啟示程序（Oracle），可定期提供一個(gè)可能已經(jīng)發(fā)生故障的進(jìn)程列表。王明等[2]提出一種自適應(yīng)心跳檢測器（SA-HD，Self-Adaptive Heartbeat Detector）。SA-HD采用了基于拉式（pull）的自適應(yīng)心跳算法，在考慮故障檢測性能的同時(shí)也考慮了心跳檢測所占用的網(wǎng)絡(luò)資源對(duì)網(wǎng)絡(luò)性能的影響。饒翔等[3]提出一種基于故障注入測試的故障特征提取方法，該方法主要由3步組成：（1）過濾噪聲日志；（2）構(gòu)造1個(gè)故障識(shí)別器識(shí)別不同故障的早期特征；（3）為每類故障構(gòu)造限狀態(tài)追蹤器追蹤該故障的后期傳播狀態(tài)，從而在故障被識(shí)別出來后持續(xù)跟蹤故障傳播狀態(tài)。文獻(xiàn)[4]針對(duì)現(xiàn)有方法在滿足網(wǎng)格特定需求方面的缺陷，提出設(shè)計(jì)動(dòng)態(tài)自適應(yīng)故障檢測服務(wù)的手段，通過對(duì)分布式系統(tǒng)中已有動(dòng)態(tài)自適應(yīng)故障服務(wù)的分析，設(shè)計(jì)了解決的辦法。然而，上述檢測方案大多假設(shè)通過一種機(jī)制，利用可靠的通信鏈路來通知完全連通網(wǎng)絡(luò)中的故障。另外，檢測器在部署時(shí)也沒有考慮能量、存儲(chǔ)和帶寬方面的資源約束。因此，不適用于有損網(wǎng)絡(luò)。為此，本文重點(diǎn)研究MANET、MESH和WSN等低功耗有損網(wǎng)絡(luò)（LLN）的故障檢測問題。旨在改進(jìn)LLN的故障檢測模式，并提出一種新的故障檢測器ALLONE（低功耗有損網(wǎng)絡(luò)的自適應(yīng)故障檢測器）。在考慮無線鏈路間歇性故障的情況下，利用自適應(yīng)計(jì)時(shí)器實(shí)現(xiàn)節(jié)點(diǎn)故障檢測。進(jìn)程故障的檢測只基于節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的本地感知，與全局信息交換無關(guān)。被交換的疑似故障列表捎帶到LLN應(yīng)用的周期性數(shù)據(jù)報(bào)文中?；贠mnet++/Mixim展開仿真實(shí)驗(yàn)，評(píng)估本文方法的檢測和精度性能。結(jié)果表明，與其他方法相比，本文方法提高了故障檢測和恢復(fù)率，降低了報(bào)文丟失率和故障陽性檢測率，而且并沒有增加能耗開銷。

1 問題分析

設(shè)一個(gè)系統(tǒng)包括兩個(gè)進(jìn)程：進(jìn)程Pj必須周期性地向Pi發(fā)送數(shù)據(jù)報(bào)文。首先假設(shè)鏈路可靠性較高，這意味著在正常進(jìn)程間傳播的報(bào)文總是能被正確傳輸。故障檢測時(shí)間（Tj）定義為：如果Tj在接收到期望報(bào)文前到期，則Pi懷疑Pj故障。根據(jù)應(yīng)用參數(shù)（比如周期性發(fā)送間隔，傳輸延時(shí)等），可對(duì)Tj數(shù)值初始化。

然而，如果除了進(jìn)程故障外還有可能發(fā)生報(bào)文丟棄和鏈路故障，則上述情況將會(huì)不同。實(shí)際上，就上述Tj而言，當(dāng)Pj仍在正常運(yùn)行但由于間歇性故障（有損鏈路、擁塞等）導(dǎo)致報(bào)文丟失時(shí)，Pi便有可能出錯(cuò)。此外，在整個(gè)網(wǎng)絡(luò)壽命期間，報(bào)文丟失模式也不穩(wěn)定。隨著障礙物、地理特征、抑制、部署和機(jī)動(dòng)性不同，上述情況也會(huì)發(fā)生變化。為此，本文根據(jù)Pj的動(dòng)態(tài)有損模式來更新Tj。此外，如果網(wǎng)絡(luò)包括2個(gè)以上進(jìn)程，則每個(gè)節(jié)點(diǎn)的故障檢測器必須在本地檢測出故障，然后將故障情況通知給其他相鄰節(jié)點(diǎn)。所支持的機(jī)制必須考慮能耗、帶寬和存儲(chǔ)空間等資源約束。實(shí)際上，通知故障情況會(huì)導(dǎo)致額外能耗和網(wǎng)絡(luò)流量。

本文研究基于直接相鄰節(jié)點(diǎn)間本地交互的自適應(yīng)性計(jì)時(shí)器使用問題。利用一種隨機(jī)策略，在考慮丟失率、鏈路狀態(tài)和傳輸時(shí)延等因素的情況下確定計(jì)時(shí)器T 。該計(jì)時(shí)器是在兩個(gè)連續(xù)相鄰節(jié)點(diǎn)間而不是任意一對(duì)節(jié)點(diǎn)間定義，這樣可以提高T 數(shù)值計(jì)算的準(zhǔn)確性。此時(shí)T數(shù)值取決于本地可預(yù)測的傳輸延時(shí)，且不需要知道整個(gè)系統(tǒng)和網(wǎng)絡(luò)結(jié)構(gòu)的相關(guān)信息。本地故障懷疑信息將在網(wǎng)絡(luò)中傳輸。每個(gè)進(jìn)程可以查詢一個(gè)故障檢測模塊，且該模塊可以提供信息明確其相鄰節(jié)點(diǎn)中哪些進(jìn)程發(fā)生故障。這一信息的格式往往是疑似故障的列表形式。利用相鄰區(qū)域交互，將該列表捎帶進(jìn)周期性數(shù)據(jù)報(bào)文中，可避免使用專門信令報(bào)文導(dǎo)致的額外開銷。

2 系統(tǒng)模型

2.1 故障模型

假設(shè)進(jìn)程有可能發(fā)生故障。此外，相鄰節(jié)點(diǎn)間的鏈路為有損鏈路：在傳輸過程中報(bào)文可能會(huì)丟失。這往往是由傳輸鏈路故障導(dǎo)致，這些傳輸鏈路故障往往是間歇性故障。因此，如果進(jìn)程沒有成功發(fā)送部分報(bào)文，則這一報(bào)文丟失現(xiàn)象定義為間歇性故障。然而，如果進(jìn)程故障，則進(jìn)程永遠(yuǎn)不再屬于網(wǎng)絡(luò)，并且要把這一情況告知所有相鄰節(jié)點(diǎn)。于是，即使故障檢測器在鏈路故障時(shí)懷疑進(jìn)程故障，則當(dāng)鏈路恢復(fù)時(shí)也有能力檢測出錯(cuò)誤的故障判斷。為了容忍LLN中的間歇性故障，本文使用文獻(xiàn)[5，6]提出的突發(fā)報(bào)文丟失模型。連續(xù)報(bào)文丟失數(shù)量可表示為BL（突發(fā)長度）變量的幾何分布，該分布明確了處于Bad狀態(tài)（即連續(xù)報(bào)文丟失）的時(shí)間長度。定義故障檢測器必須能夠容忍的突發(fā)丟失上限（BLL）為：

2.2 數(shù)據(jù)采集模型

考慮基于周期性報(bào)文傳輸?shù)膬煞N通信模型：檢索驅(qū)動(dòng)和時(shí)間驅(qū)動(dòng)。其中，檢索驅(qū)動(dòng)模型又稱為檢索響應(yīng)路由模型，以網(wǎng)絡(luò)偵詢?yōu)榛A(chǔ)，進(jìn)程依次向所有網(wǎng)絡(luò)節(jié)點(diǎn)（相鄰節(jié)點(diǎn)）發(fā)起查詢。目的進(jìn)程在協(xié)議參數(shù)事先定義好的時(shí)間間隔內(nèi)做出響應(yīng)。例如，DSR[7]和AODV[8]均為基于查詢的協(xié)議。另一方面，時(shí)間驅(qū)動(dòng)模型使用周期性數(shù)據(jù)傳輸方法。路由協(xié)議為每輪數(shù)據(jù)傳輸定義了一個(gè)時(shí)間隙或一個(gè)時(shí)間間隔。許多主動(dòng)式協(xié)議（例如DSDV[9]、OSR[10])使用時(shí)間驅(qū)動(dòng)模型來構(gòu)建和維護(hù)路由。

3 ALLONE：故障檢測算法

算法根據(jù)通信模型的周期性模式按輪運(yùn)行。在每一輪中，節(jié)點(diǎn)向其相鄰節(jié)點(diǎn)發(fā)送報(bào)文，直到有可能故障為止。本文模型的基本原則是：將疑似故障捎帶進(jìn)當(dāng)前數(shù)據(jù)/路由報(bào)文，并?逐Su條s傳p播e信c息t。e因d此i， 將表S示u進(jìn)s程pPeic t包e含其d疑i似 故列障表相加鄰到節(jié)每點(diǎn)個(gè)的報(bào)列文表中。。進(jìn)程Pi的ALLONE模塊如圖1所示：

圖1 ALLONE模型

它由兩個(gè)主要組件（發(fā)送和接收）和一個(gè)任務(wù)構(gòu)成：對(duì)每個(gè)消息MSG，ALLONE檢查MSG是否屬于發(fā)送組件（即Pi 生成的將要發(fā)送到網(wǎng)絡(luò)中的數(shù)據(jù)報(bào)文）。如果屬于，則Pi中MSG包含Suspectedi 集合（第4行）。在將信息捎帶處理后，Pi向neighborsi 中的相應(yīng)節(jié)點(diǎn)發(fā)送新的報(bào)文?MSGs（第5行）。然后，Pi 為每個(gè)正常已知相鄰節(jié)點(diǎn)初始化一個(gè)新的計(jì)時(shí)器，即節(jié)點(diǎn)Pj等待下一報(bào)文，計(jì)時(shí)器為Tj。如果有Tj到期，則Pi懷疑Pj在任務(wù)T1中故障。然后，疑似信息插入Suspected（i第20行）。如果有另一個(gè)MSG需要發(fā)送，則該疑似信息包含在下一數(shù)據(jù)報(bào)文中。計(jì)時(shí)器調(diào)度具有動(dòng)態(tài)特性，取決于網(wǎng)絡(luò)的隨機(jī)變化。下一節(jié)將闡述如何調(diào)節(jié)計(jì)時(shí)器。另一方面，如果Pi接收到來自相鄰節(jié)點(diǎn)Pj 的MSG（第8行），則ALLONE運(yùn)行第2個(gè)組件（即接收組件），根據(jù)接收到的報(bào)文中捎帶的的疑似故障集合來更新疑似故障集合。它還努力尋找先前被錯(cuò)判的疑似故障，以便能從疑似列表中將相應(yīng)節(jié)點(diǎn)去除。首先，Pi將數(shù)據(jù)報(bào)文發(fā)送給其應(yīng)用層。然后，檢索相關(guān)信息，即源節(jié)點(diǎn)Pj的集合Suspected（j第11和12行）。因?yàn)镻i已經(jīng)成功地從Pj處接收到報(bào)文，所以中止計(jì)時(shí)器? Tj（第13行）。Pi 檢查Pj 在最近是否被懷疑，以便將其從Suspectedj集合中刪除（第14和15行）。此后，Pi 利用接收到的Pj 報(bào)文中關(guān)于疑似故障和錯(cuò)判故障的相關(guān)信息來更新自己的列表。因此，Pi包括Pj通知的每一個(gè)疑似故障進(jìn)程。此外，如果Pj通知Pm先前被錯(cuò)判為疑似故障進(jìn)程，則Pi將Pm 從其Suspectedi 中刪除（第16-18行）。如果Suspectedi 不包括Pm 但后者仍在Suspectedi 列表中，則檢測出錯(cuò)判。

4 計(jì)時(shí)器調(diào)整技術(shù)

本節(jié)闡述如何調(diào)度ALLONE中的故障檢測計(jì)時(shí)器（圖1第7行）。本文提出的計(jì)時(shí)器T 應(yīng)該在考慮傳輸故障、通信協(xié)議內(nèi)容和網(wǎng)絡(luò)動(dòng)態(tài)特征的條件下進(jìn)行動(dòng)態(tài)更新。為此，本文提出基于這一機(jī)制的兩種計(jì)時(shí)器調(diào)整方法。第1種方法通知所有故障且虛警率較低，因此，稱為精度感知隨機(jī)自適應(yīng)計(jì)時(shí)器A-SAT。第2種方法以最短時(shí)間通知各種進(jìn)程故障以進(jìn)行實(shí)時(shí)監(jiān)控。很顯然，這可能增加虛警率。然而，該機(jī)制的目的是實(shí)現(xiàn)實(shí)時(shí)檢測。于是，本文將其稱為完整性感知隨機(jī)自適應(yīng)計(jì)時(shí)器C-SAT。兩種方法的計(jì)時(shí)器設(shè)置和更新算法如圖2所示：

圖2 計(jì)時(shí)器自適應(yīng)算法

在開始時(shí)，由于沒有之前的通信過程供我們獲取統(tǒng)計(jì)數(shù)據(jù)，所以根據(jù)傳輸間隔和延時(shí)的假設(shè)值來設(shè)置首個(gè)T值（第1行）。然后，應(yīng)用運(yùn)行期間利用關(guān)于被接收數(shù)據(jù)報(bào)文的有效丟失率來更新T。也就是說，如果錯(cuò)誤檢測率WDR超過能夠容忍的錯(cuò)誤檢測率TWR（第2和3行），則T將會(huì)增加，其中TWR是用于控制故障檢測器精度的閾值。如果到達(dá)該閾值，則ALLONE必須在通知故障前增加等待時(shí)間。然而，如果T允許滿足預(yù)期TWR值，那么若它還沒有達(dá)到預(yù)先定義的可靠性閾值（第4到5行），我們通過降低其數(shù)值來增加故障通知性能。在應(yīng)用中引入是為了明確允許快速檢測時(shí)故障檢測器的預(yù)期可靠性。很顯然，算法希望提高檢測速度的同時(shí)降低差錯(cuò)率，如圖3所示。算法性能取決于預(yù)定義參數(shù)及Decrease(T)和 Increase(T)函數(shù)。下面將闡述如何根據(jù)應(yīng)用要求采用不同方式實(shí)現(xiàn)時(shí)間增加/下降功能。

4.1 精度感知方法(A-SAT)

本文希望通過A-SAT方法，提高故障通知的精確性。這種方法的目的是降低錯(cuò)判率。為此，使用文獻(xiàn)[11]中的乘性相加加性相減算法（MIAD）。MIAD將計(jì)時(shí)器數(shù)值的指數(shù)增加特點(diǎn)與線性下降特點(diǎn)融合起來，以滿足故障檢測最低可靠性要求：

假設(shè)故障檢測器已經(jīng)發(fā)生了多起錯(cuò)誤，于是虛警率超過能夠容忍的閾值（WDR>TWR）。根據(jù)算法如圖3所示：

圖3計(jì)時(shí)器更新進(jìn)程

我們增加計(jì)時(shí)器數(shù)值。因?yàn)锳-SAT希望降低錯(cuò)誤數(shù)量，所以將計(jì)時(shí)器乘以以放大其數(shù)值。此外，參數(shù)a取決于程序運(yùn)行期間觀察到的本地隨機(jī)信息，即WDR和TWR。因此，計(jì)時(shí)器的指數(shù)上升取決于導(dǎo)致其增加的有效虛警率。然而，在decrease(T)函數(shù)中，使用參數(shù)β降低計(jì)時(shí)器數(shù)值。根據(jù)故障檢測期間的本地通知延時(shí)來推導(dǎo)β數(shù)值（通知延時(shí)是指故障出現(xiàn)至故障被檢測出來之間的時(shí)間）。請(qǐng)注意，如果故障檢測器的可靠性低于可靠性閾值要求，則觸發(fā)decrease(T)函數(shù)。出于簡便考慮，將可靠性定義為正確故障判斷的比例，即1-WDR。通過在控制虛警率時(shí)猛烈增加計(jì)時(shí)器數(shù)值，A-SAT增加其等待時(shí)間，以容忍更多的間歇性故障，避免錯(cuò)誤判斷。每當(dāng)故障檢測率下降時(shí)，根據(jù)通知延時(shí)的均值來降低計(jì)時(shí)器數(shù)值，以迅速克服可靠性較低的問題。

4.2 完整性感知(C-SAT)

本文提出完整性感知隨機(jī)自適應(yīng)技術(shù)（C-SAT）以實(shí)現(xiàn)故障的迅速檢測。目的是迅速通知任何故障。為此，我們使用文獻(xiàn)[11]中的加性增加乘性相減方法（AIMD）。與MIAD方法不同，AIMD融合了計(jì)時(shí)器的線性上升和指數(shù)性下降特點(diǎn)，如下式所示：

對(duì)于AIMD和A-SAT，計(jì)時(shí)器的增加和下降函數(shù)分別取決于故障通知的可靠性和虛警率。C-SAT猛烈降低計(jì)時(shí)器數(shù)值來迅速檢測出任何故障。為此，將T與根據(jù)有效虛警率而確定的參數(shù)相乘。做出這種選擇，是因?yàn)镃-SAT通過降低計(jì)時(shí)器數(shù)值來迅速檢測出故障。同時(shí)，為了避免誤判，當(dāng)?shù)竭_(dá)可靠性要求時(shí)，C-SAT增加T值。為此，將T與參數(shù)相加，參數(shù)取決于應(yīng)用運(yùn)行期間的隨機(jī)信息（比如導(dǎo)致先前部分誤判的傳輸延時(shí)平均周期數(shù)值）。

5 性能評(píng)估

本節(jié)評(píng)估了動(dòng)態(tài)故障檢測器ALLONE和計(jì)時(shí)器調(diào)整方法的性能。首先，比較本文基于計(jì)時(shí)器的廣義模型與無計(jì)時(shí)器的故障檢測器。然后，衡量計(jì)時(shí)器更新的重要性，以及兩種動(dòng)態(tài)調(diào)整方法（即C-SAT和A-SAT）的影響。為此，選擇文獻(xiàn)[12]中的HeartBeat（HB）作為無計(jì)時(shí)器故障檢測器?；贠mnet++/Mixim展開仿真實(shí)驗(yàn)，仿真模型總結(jié)如表1所示：

表1 仿真模型

為了闡述使用自適應(yīng)故障檢測器的結(jié)果，本文主要利用兩種場景考察多次仿真的結(jié)果。在場景1改變隨機(jī)部署的節(jié)點(diǎn)數(shù)量（20-200個(gè)節(jié)點(diǎn)）；在場景2改變相同網(wǎng)絡(luò)條件下的故障數(shù)量（所有節(jié)點(diǎn)的10%-50%）。為了獲得周期性數(shù)據(jù)通信模型，采用文獻(xiàn)[8]中的有向擴(kuò)散路由協(xié)議DD。在本文仿真測試中，比較DD-HB（利用無計(jì)時(shí)器故障檢測器進(jìn)行增強(qiáng)的DD協(xié)議），F(xiàn)aT2D[2]（利用靜態(tài)計(jì)時(shí)器故障檢測器進(jìn)行增強(qiáng)的DD協(xié)議），以及ALLONE的兩個(gè)版本：ALLONE-ASAT和ALLONE-CSAT。這兩個(gè)版本的主要區(qū)別就是使用的計(jì)時(shí)器調(diào)整技術(shù)不同。

5.1 性能指標(biāo)：

本文實(shí)驗(yàn)主要考察3種類型6大指標(biāo)：

（1）故障檢測器的屬性：在該類型下，主要測試精度和完整性屬性。于是，可以根據(jù)虛警率（精度）和故障檢測率（完整性）方面的性能表現(xiàn)對(duì)本文方法進(jìn)行分類。

（2）檢測和恢復(fù)性能：每種檢測機(jī)制的目的均是發(fā)現(xiàn)網(wǎng)絡(luò)中的故障，恢復(fù)路由路徑，避免故障的影響。為此，使用檢測和恢復(fù)周期及報(bào)文丟失率兩個(gè)指標(biāo)。這些測量值可以衡量檢測技術(shù)的速度及其對(duì)數(shù)據(jù)報(bào)文丟失的影響。

（3）資源管理：因?yàn)長LN是資源受限型網(wǎng)絡(luò)，所以有必要評(píng)估并比較每種技術(shù)的能耗和開銷（網(wǎng)絡(luò)中的報(bào)文量）。

5.2 結(jié)果分析

完整性性能如圖4所示：

圖4 故障檢測計(jì)時(shí)器對(duì)完整性的影響

兩種ALLONE方法的結(jié)果要優(yōu)于基于計(jì)時(shí)器的靜態(tài)FaT2D算法。此外，C-SAT的完整率最高（70%-95%）。很顯然，這是因?yàn)镃-SAT中的計(jì)時(shí)器進(jìn)行了調(diào)整，以實(shí)現(xiàn)所有故障的迅速檢測。然而，無計(jì)時(shí)器HB算法只能檢測出網(wǎng)絡(luò)中所有故障的50%。因?yàn)?，采集的來自所有?jié)點(diǎn)的信息在送給應(yīng)用前HB無法做出決策，所以檢測方法的速度非常慢。檢測時(shí)間如圖5所示：

圖5 故障檢測計(jì)時(shí)器對(duì)檢測和恢復(fù)時(shí)間的影響

從圖5中可以顯著看出這點(diǎn)。如上文所述，HB需要等待較長時(shí)間才能決策是否出現(xiàn)節(jié)點(diǎn)故障。為此，它的檢測時(shí)間要長于基于計(jì)時(shí)器的FaT2D、C-SAT和A-SAT。然而，如果考察這3種算法的檢測和恢復(fù)時(shí)間，會(huì)發(fā)現(xiàn)C-SAT的性能最優(yōu)。請(qǐng)注意，檢測和恢復(fù)時(shí)間相加便確定了故障處理的整個(gè)時(shí)間（先是檢測和通知，然后是抑制和路徑恢復(fù)）。HB沒有定義任何恢復(fù)機(jī)制。

另一方面，3種算法中A-SAT的精度最高如圖6所示：

圖6 故障檢測計(jì)時(shí)器對(duì)精度的影響

很明顯，這是因?yàn)锳-SAT中利用公式進(jìn)行了計(jì)時(shí)器更新，以實(shí)現(xiàn)差錯(cuò)率最小化。尤其地，HB在這方面的性能也較優(yōu)，因?yàn)樗歼M(jìn)程為故障進(jìn)程所需時(shí)間較長。因此，它可避免出現(xiàn)差錯(cuò)。

對(duì)LLN來說，能耗、內(nèi)存空間和帶寬是重要約束，因此需要評(píng)估故障檢測機(jī)制對(duì)電池使用量和開銷的影響。

即使C-SAT和A-SAT部署了專門的計(jì)時(shí)器更新機(jī)制，但是與靜態(tài)計(jì)時(shí)器相比，電池能耗的差異很小，如圖7所示：

圖7 故障檢測計(jì)時(shí)器對(duì)能耗的影響

這一結(jié)果非常有前景，因?yàn)椴渴饘ｉT的故障檢測機(jī)制導(dǎo)致的額外開銷可以彌補(bǔ)節(jié)點(diǎn)故障后無用傳輸導(dǎo)致的開銷，如圖8所示。

圖8 故障檢測計(jì)時(shí)器對(duì)開銷的影響

此外，使用本地交互和在數(shù)據(jù)報(bào)文中捎帶確認(rèn)故障通知，顯著降低了網(wǎng)絡(luò)開銷。與無計(jì)時(shí)器HB相比，這些特征顯著提升了故障檢測性能。實(shí)際上，HB方法將額外的報(bào)文轉(zhuǎn)發(fā)給網(wǎng)絡(luò)中的所有節(jié)點(diǎn)，以便傳輸故障檢測信息（即每個(gè)節(jié)點(diǎn)的計(jì)數(shù)器），而部署的所有基于計(jì)時(shí)器的方法使用數(shù)據(jù)報(bào)文來傳輸這些信息。此外，報(bào)文只傳輸給直接相鄰節(jié)點(diǎn)。它在數(shù)據(jù)傳輸過程中將會(huì)到達(dá)其他節(jié)點(diǎn)。與靜態(tài)計(jì)時(shí)器FaT2D相比，C-SAT和A-SAT兩種計(jì)時(shí)器調(diào)整方法不會(huì)導(dǎo)致額外的能耗。

6 總結(jié)

本文提出一種新的故障檢測機(jī)制ALLONE。ALLONE的特征如下：（1）它考慮了能源約束（能量，內(nèi)存，帶寬），是一種低功耗有損網(wǎng)絡(luò)的廣義故障檢測模型；（2）報(bào)文交換模式基于相鄰節(jié)點(diǎn)間的本地信息交換，而不是基于系統(tǒng)中的全局節(jié)點(diǎn)信息交換；（3）可以容忍間歇性故障，通過一種交互式動(dòng)態(tài)計(jì)時(shí)器對(duì)故障檢測步驟進(jìn)行調(diào)整。

此外，引入A-SAT和C-SAT兩種計(jì)時(shí)器調(diào)整策略，使得本文可以根據(jù)應(yīng)用要求來調(diào)整ALLONE的運(yùn)行性能。如果降低虛警率更為重要，則應(yīng)使用A-SAT，對(duì)密集型網(wǎng)絡(luò)來說尤其如此。相反，如果檢測所有故障比避免差錯(cuò)更為重要，則最優(yōu)選擇是C-SAT。兩種方法均可提升檢測時(shí)間和數(shù)據(jù)傳輸方面的性能。此外，仿真結(jié)果還表明，將故障檢測信息捎帶進(jìn)數(shù)據(jù)報(bào)文及利用自適應(yīng)計(jì)時(shí)器，可以節(jié)約能耗和帶寬。

[1] Chandra T.D.and Toueg S. Unreliable failure detectors for reliable distributed systems [J]. Journal of the ACM, 2006,11(4):631-643.

[2] 王明,張春熹,伊小素.基于自適應(yīng)心跳算法的分布式系統(tǒng)故障檢測器[J].北京航空航天大學(xué)學(xué)報(bào),2013,39(7):1601-1609.

[3] 饒翔,王懷民,陳振邦.云計(jì)算系統(tǒng)中基于伴隨狀態(tài)追蹤的故障檢測機(jī)制[J].計(jì)算機(jī)學(xué)報(bào),2012,35(5):856-870.

[4] 李景林.網(wǎng)格環(huán)境下的故障檢測服務(wù)研究[J].計(jì)算機(jī)應(yīng)用與軟件,2010,27(6):120-123.

[5] Quevedo D E, Ne?i? D. Robust stability of packetized predictive control of nonlinear systems with disturbances and Markovian packet losses [J]. Automatica, 2012,48(8): 1803-1811.

[6] Mahmood K, Rizk A, Jiang Y. On the flow-level delay of a spatial multiplexing MIMO wireless channel[C]. Communications (ICC), 2011 IEEE International Conference on. IEEE, 2011:1-6.

[7] Taneja S, Kush A. A Survey of routing protocols in mobile ad hoc networks [J]. International Journal of Innovation, Management and Technology, 2010, 1(3): 2010-0248.

[8] Alotaibi E, Mukherjee B. A survey on routing algorithms for wireless Ad-Hoc and mesh networks [J]. Computer Networks, 2012, 56(2): 940-965.

[9] Narra H, Cheng Y, Cetinkaya E K, et al. Destination-sequenced distance vector (DSDV) routing protocol implementation in ns-3[C]. Proceedings of the 4th International ICST Conference on Simulation Tools and Techniques. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2011: 439-446.

[10] Yi J, Adnane A, David S, et al. Multipath optimized link state routing for mobile ad hoc networks [J]. Ad Hoc Networks, 2011, 9(1): 28-47.

[11] Yang P, Luo W, Xu L, et al. TCP congestion avoidance algorithm identification[C].Distributed Computing Systems (ICDCS), 2011 31st International Conference on. IEEE, 2011: 310-321.

[12] Zhangjie Wang, Xiao Li. A new real-time Heartbeat Failure Detection[C]. 4th International Conference on Wireless Communications, Networking and Mobile Computing, 2008:1-3.

TP393

A

2015.03.28）

1007-757X(2015)07-0034-04

趙英姿（1971-），女，陜西洛川人，東莞理工學(xué)校，高級(jí)講師，研究方向：移動(dòng)互聯(lián)網(wǎng)、大數(shù)據(jù)、軟件工程，東莞，523000