基于最小連通支配集移動(dòng)的WSANs連接恢復(fù)算法

周 杰，姚 雷，杜景林

近年來(lái)，無(wú)線(xiàn)傳感器與執(zhí)行器網(wǎng)絡(luò)(wireless sensor-actor networks，簡(jiǎn)稱(chēng)WSANs)在應(yīng)用層面引起廣泛的興趣.WSANs［1］網(wǎng)絡(luò)由大量傳感器節(jié)點(diǎn)(sensor)和少量執(zhí)行器節(jié)點(diǎn)(actor)構(gòu)成，分布在特定檢測(cè)地理區(qū)域中，特別是一些偏遠(yuǎn)、環(huán)境惡劣、人類(lèi)無(wú)法干預(yù)的地區(qū)，傳感器用來(lái)環(huán)境感知、簡(jiǎn)單處理以及轉(zhuǎn)發(fā)數(shù)據(jù)到基站.執(zhí)行器節(jié)點(diǎn)根據(jù)傳感器節(jié)點(diǎn)匯報(bào)的事件和收集的數(shù)據(jù)執(zhí)行相應(yīng)的分配任務(wù)［2］.執(zhí)行器節(jié)點(diǎn)類(lèi)似于移動(dòng)的機(jī)器人、無(wú)人駕駛的車(chē)輛［3］等，都是自主和協(xié)作的實(shí)現(xiàn)應(yīng)用程序中的任務(wù).在連通的WSANs中，一個(gè)或多個(gè)執(zhí)行器節(jié)點(diǎn)出現(xiàn)故障可能會(huì)導(dǎo)致其他節(jié)點(diǎn)或通信鏈路失效，如果受影響的節(jié)點(diǎn)之間的替代路徑不可用，網(wǎng)絡(luò)就形成分區(qū)，節(jié)點(diǎn)喪失工作能力.這種情況不僅會(huì)阻礙節(jié)點(diǎn)間的合作、破壞實(shí)時(shí)連接的要求，也對(duì)實(shí)際應(yīng)用造成不良后果.在WSANs所提供的遠(yuǎn)程設(shè)置服務(wù)使用額外的資源部署來(lái)恢復(fù)連接是不切實(shí)際的，重新部署節(jié)點(diǎn)將成為最好的恢復(fù)選擇［4］.因此，WSANs應(yīng)該具備容錯(cuò)能力，能以一種分布式的、及時(shí)的、節(jié)能的方式自我恢復(fù).首先，恢復(fù)過(guò)程采用分布式方法，因?yàn)檫@些網(wǎng)絡(luò)通常是自治的;第二，為了對(duì)監(jiān)測(cè)到的事件迅速反應(yīng)，恢復(fù)過(guò)程需要足夠快;最后，恢復(fù)過(guò)程中的能源開(kāi)銷(xiāo)應(yīng)盡量減少，以延長(zhǎng)網(wǎng)絡(luò)壽命［5］.

在恢復(fù)WSANs網(wǎng)絡(luò)連通性方面，很多文獻(xiàn)已經(jīng)從各個(gè)方面進(jìn)行了深入的研究，主要采用通過(guò)移動(dòng)執(zhí)行器節(jié)點(diǎn)的位置來(lái)恢復(fù)連接.文獻(xiàn)中現(xiàn)有的方法可以歸類(lèi)成節(jié)點(diǎn)的級(jí)聯(lián)運(yùn)動(dòng)［6］和塊體運(yùn)動(dòng)［7］.為了避免過(guò)度的狀態(tài)更新的開(kāi)銷(xiāo)和更好地恢復(fù)連接過(guò)程，之前的工作都是依靠于保持一跳或兩跳路由表并決定參與恢復(fù)節(jié)點(diǎn)的標(biāo)準(zhǔn)［8－10］.文獻(xiàn)［8］要求每個(gè)執(zhí)行器節(jié)點(diǎn)保留兩跳鄰居信息.挑選失效節(jié)點(diǎn)的一個(gè)鄰居來(lái)啟動(dòng)恢復(fù)過(guò)程，盡可能降低移動(dòng)開(kāi)銷(xiāo)和交換消息數(shù)量.在割點(diǎn)失效時(shí)，分布式執(zhí)行器節(jié)點(diǎn)恢復(fù)算法(distributed actor recovery algorithm，簡(jiǎn)稱(chēng)DARA)指定度最小的鄰居啟動(dòng)恢復(fù)連通性過(guò)程，而分區(qū)檢測(cè)恢復(fù)算法(partition detection and recovery algorithm，簡(jiǎn)稱(chēng)PADRA)首先標(biāo)識(shí)出支配節(jié)點(diǎn)以監(jiān)聽(tīng)割點(diǎn)，這個(gè)支配節(jié)點(diǎn)不直接移動(dòng)到失效節(jié)點(diǎn)的位置.盡管如此，他們均使用分布式算法，需要保留兩跳鄰居的信息，增加了通信開(kāi)銷(xiāo).Younis等人提出了一種名為內(nèi)縮移動(dòng)恢復(fù)算法(recovery through inward motion，簡(jiǎn)稱(chēng)RIM)［9］.當(dāng)一個(gè)節(jié)點(diǎn)發(fā)生故障時(shí)，其鄰居向它的位置移動(dòng)，使他們能夠相互連接，這種遞歸重置過(guò)程適用于處理任何節(jié)點(diǎn)失效時(shí)其鄰居的移動(dòng).但是該算法沒(méi)有區(qū)分割點(diǎn)與葉節(jié)點(diǎn)的情況，帶來(lái)不必要的恢復(fù)過(guò)程.

論文設(shè)計(jì)了一種基于最小連通支配集移動(dòng)的連接性恢復(fù)算法(MCDSR)，由于網(wǎng)絡(luò)分區(qū)是割點(diǎn)(關(guān)鍵節(jié)點(diǎn))失效引起的，先用基于深度優(yōu)先的割點(diǎn)搜索算法判斷節(jié)點(diǎn)是否是割點(diǎn).一旦割點(diǎn)確定，再指定適當(dāng)?shù)泥従幼鳛楦铧c(diǎn)的備份節(jié)點(diǎn)來(lái)監(jiān)聽(tīng)失效.備份節(jié)點(diǎn)檢測(cè)到任何故障后，在其分區(qū)中選擇一個(gè)最小連通支配集級(jí)聯(lián)運(yùn)動(dòng)替換失效節(jié)點(diǎn).替代節(jié)點(diǎn)不是直接移動(dòng)到失效節(jié)點(diǎn)的確切位置，它只是移動(dòng)到某個(gè)最佳位置來(lái)管理多個(gè)傳感器，其子節(jié)點(diǎn)也相應(yīng)移動(dòng)與先驅(qū)節(jié)點(diǎn)保持連接，論文將給出最佳位置的計(jì)算方法.MCDSR的目標(biāo)是確保執(zhí)行器節(jié)點(diǎn)的覆蓋度減少最少，恢復(fù)過(guò)程中造成的節(jié)點(diǎn)移動(dòng)和通信開(kāi)銷(xiāo)最小.

圖1 WSANs系統(tǒng)模型Fig.1 The system model of the WSANs

1 WSANs系統(tǒng)模型

1.1 系統(tǒng)模型

執(zhí)行器節(jié)點(diǎn)是隨機(jī)部署在感知區(qū)域，一旦部署完成節(jié)點(diǎn)就試圖發(fā)現(xiàn)其他節(jié)點(diǎn)，并通過(guò)現(xiàn)有的技術(shù)形成一個(gè)連通的網(wǎng)絡(luò).執(zhí)行器節(jié)點(diǎn)為了在更大的區(qū)域執(zhí)行任務(wù)或者提高網(wǎng)絡(luò)的連通性，可以根據(jù)應(yīng)用的需求移動(dòng).圖1顯示一個(gè)WSANS系統(tǒng)模型.

圖1中，一個(gè)執(zhí)行器節(jié)點(diǎn)收集來(lái)自其鄰居傳感器節(jié)點(diǎn)的數(shù)據(jù)并與其他的執(zhí)行器節(jié)點(diǎn)協(xié)作，其中一些關(guān)鍵執(zhí)行器節(jié)點(diǎn)可以通過(guò)很長(zhǎng)的通信鏈路(衛(wèi)星)連接遠(yuǎn)區(qū)域的命令中心，來(lái)報(bào)告它的活動(dòng)狀態(tài)和探測(cè)到的事件.

1.2 問(wèn)題描述

執(zhí)行器節(jié)點(diǎn)的失效對(duì)網(wǎng)絡(luò)的連接可能是有限的也可能是劇烈的.如果失效的節(jié)點(diǎn)是一個(gè)葉節(jié)點(diǎn)，那么對(duì)網(wǎng)絡(luò)的連通性影響就不那么大.如果失效的節(jié)點(diǎn)是一個(gè)割點(diǎn)，起著連接多個(gè)網(wǎng)絡(luò)分隔區(qū)的作用，將會(huì)對(duì)網(wǎng)絡(luò)連接產(chǎn)生嚴(yán)重影響.圖2顯示一個(gè)內(nèi)執(zhí)行器網(wǎng)絡(luò).

圖2 內(nèi)執(zhí)行器網(wǎng)絡(luò)Fig.2 Inter-actor network

在圖2中可以看出，一個(gè)葉節(jié)點(diǎn)13的失效不會(huì)影響網(wǎng)絡(luò)的連通性，同樣的17、18由于是雙連通的也不會(huì)產(chǎn)生影響.但由于執(zhí)行器節(jié)點(diǎn)6是割點(diǎn)，會(huì)將網(wǎng)絡(luò)分隔成兩塊以上的不連接的區(qū)域.

為了容錯(cuò)割點(diǎn)的失效導(dǎo)致網(wǎng)絡(luò)的分隔，通常采取兩種策略:提前預(yù)防和實(shí)時(shí)恢復(fù).提前預(yù)防策略致力于在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)初始形成階段提供容錯(cuò).在網(wǎng)絡(luò)中建立k－連通的拓?fù)浣Y(jié)構(gòu)，使每個(gè)節(jié)點(diǎn)都有至少有K條到達(dá)其他節(jié)點(diǎn)的獨(dú)立路徑，這樣的設(shè)置可以使網(wǎng)絡(luò)能夠同時(shí)容忍K－1執(zhí)行器節(jié)點(diǎn)失效.但要注意的是，這種高度連通的網(wǎng)絡(luò)需要部署大量的執(zhí)行器節(jié)點(diǎn)和高能耗，在實(shí)際中是不可取的.另外，也可能限制執(zhí)行器節(jié)點(diǎn)的移動(dòng)從而影響應(yīng)用層面的功能，實(shí)時(shí)恢復(fù)實(shí)現(xiàn)從檢測(cè)到執(zhí)行器節(jié)點(diǎn)失效到恢復(fù)的過(guò)程.但由于它是異步性，本身又是被動(dòng)的，很難預(yù)測(cè)移動(dòng)的位置和范圍，所以需要設(shè)計(jì)一種算法來(lái)根據(jù)失效節(jié)點(diǎn)的影響自適應(yīng)計(jì)算最佳位置和范圍.

2 MCDSR恢復(fù)算法

基于最小連通支配集移動(dòng)的連接性恢復(fù)算法MCDSR，該算法不要求時(shí)鐘同步，這樣可減少大量通信產(chǎn)生的能量消耗，實(shí)現(xiàn)網(wǎng)絡(luò)的能量有效性.同時(shí)該算法為分布式，避免了集中式算法無(wú)法針對(duì)網(wǎng)絡(luò)改變及時(shí)調(diào)整調(diào)度的弊端.

2.1 割點(diǎn)識(shí)別階段

如果刪除圖中某點(diǎn)以及它所連接的邊后，該圖的連通分支的數(shù)目增加，則被刪除的點(diǎn)稱(chēng)為圖的割點(diǎn).割點(diǎn)是WSANs網(wǎng)絡(luò)拓?fù)渲蟹浅Ｖ匾墓?jié)點(diǎn)，它與網(wǎng)絡(luò)連通性關(guān)系密切.割點(diǎn)的存在使得WSANs網(wǎng)絡(luò)的連通存在薄弱環(huán)節(jié).一旦割點(diǎn)失效，將直接影響網(wǎng)絡(luò)的性能，因此如何在網(wǎng)絡(luò)拓?fù)渲袡z測(cè)到割點(diǎn)顯得尤為重要.接下來(lái)研究一種基于深度優(yōu)先的割點(diǎn)搜索算法，在連通圖上尋找割點(diǎn).對(duì)圖G(V，E)進(jìn)行深度優(yōu)先遍歷，選擇任意節(jié)點(diǎn)作為開(kāi)始節(jié)點(diǎn)，對(duì)某一鄰居節(jié)點(diǎn)遍歷，并沿著該鄰居節(jié)點(diǎn)繼續(xù)對(duì)更深層次的鄰居節(jié)點(diǎn)遍歷，如果節(jié)點(diǎn)v的所有鄰居節(jié)點(diǎn)都被遍歷過(guò)，則返回到v的祖先節(jié)點(diǎn)重新按照上述過(guò)程深度遍歷，直到所有節(jié)點(diǎn)都被遍歷，由此得到最小遍歷生成樹(shù).遍歷時(shí)需要記錄每個(gè)節(jié)點(diǎn)的兩個(gè)信息:visit_num［v］和 small［v］.visit_num［v］為生成樹(shù)中前序遍歷時(shí)的節(jié)點(diǎn)序號(hào).small［v］=min(visit_num［v］，visit_num［n］，small［m］)，m是v在深度優(yōu)先生成樹(shù)上的子節(jié)點(diǎn)，n是v在深度優(yōu)先生成樹(shù)上由回邊連接的祖先節(jié)點(diǎn)，(m，v)，(n，v)均是圖中的邊.對(duì)于點(diǎn) v，如果存在子節(jié)點(diǎn) m，有 small［m］≥visit_num［v］，表明 m及其子孫均沒(méi)有指向v祖先的回邊，則v是割點(diǎn).通過(guò)上述基于深度優(yōu)先的搜索算法，可以找到無(wú)向連通圖中的割點(diǎn).使用鄰接矩陣作為圖的存儲(chǔ)形式且圖中節(jié)點(diǎn)個(gè)數(shù)為n時(shí)，如果算法中對(duì)鄰接矩陣的查找時(shí)間復(fù)雜度為O(e)，那么該割點(diǎn)查找算法的總的時(shí)間復(fù)雜度為O(n+e)，因此該算法具有較好的時(shí)間復(fù)雜度和空間復(fù)雜度.

2.2 備份最小連通支配集選擇與失效監(jiān)測(cè)階段

2.2.1 備份最小連通支配集選擇

一旦割點(diǎn)確定，它的失效就會(huì)造成網(wǎng)絡(luò)分成幾個(gè)分區(qū)塊，下一步就要在這些分區(qū)塊中選擇最小的連通支配集塊作為他們的備份節(jié)點(diǎn).指定備份支配集的目的是為了對(duì)割點(diǎn)的故障做出迅速反應(yīng)，避免該故障對(duì)網(wǎng)絡(luò)造成分區(qū).

為避免額外的通信開(kāi)銷(xiāo)，執(zhí)行器節(jié)點(diǎn)只保留最少的鄰居狀態(tài)信息(一跳鄰居).由于一個(gè)關(guān)鍵節(jié)點(diǎn)失效時(shí)與其鄰居斷開(kāi)，備份執(zhí)行器節(jié)點(diǎn)確定后提前報(bào)告關(guān)鍵節(jié)點(diǎn)發(fā)生故障.一個(gè)節(jié)點(diǎn)可以作為多個(gè)執(zhí)行器節(jié)點(diǎn)的備份.一跳鄰居中備份節(jié)點(diǎn)的選擇基于以下標(biāo)準(zhǔn)［11］:

簡(jiǎn)析：觀(guān)察裝置左側(cè)加入溶液中含有,流出的溶液中含有 Ce4+、,說(shuō)明左側(cè)發(fā)生了氧化反應(yīng);同樣右側(cè)變化是,發(fā)生了還原反應(yīng)。這些信息可作為判斷電極反應(yīng)的證據(jù),左側(cè)是陽(yáng)極,右側(cè)是陰極,進(jìn)而寫(xiě)出電極反應(yīng)式。要特別注意該電解過(guò)程中陽(yáng)離子Ce3+在陽(yáng)極上被氧化,陰離子在陰極上被還原,與常見(jiàn)的電解反應(yīng)比較有一定的特殊性,分析時(shí)不要被所謂“常識(shí)”所迷惑,這就是突破認(rèn)識(shí)誤區(qū)。事實(shí)上,只要抓住電極反應(yīng)的本質(zhì)要素,就不會(huì)被“常識(shí)”或“特殊”所迷惑。

(1)一跳鄰居位置(NP):割點(diǎn)失效，就從它的一條鄰居列表中找到離它最近的節(jié)點(diǎn).

(2)一跳鄰居節(jié)點(diǎn)的節(jié)點(diǎn)度(AD):移動(dòng)一個(gè)有許多鄰居的節(jié)點(diǎn)的影響是巨大的.因此，搜索到一跳鄰居節(jié)點(diǎn)度最小的節(jié)點(diǎn)，這將限制級(jí)聯(lián)移動(dòng)的范圍，從而降低恢復(fù)過(guò)程的開(kāi)銷(xiāo).

(3)執(zhí)行器節(jié)點(diǎn)的ID:在失效節(jié)點(diǎn)一跳鄰居中，可能有兩個(gè)或兩個(gè)以上的執(zhí)行器節(jié)點(diǎn)離失效節(jié)點(diǎn)最近并且有相同的節(jié)點(diǎn)度.這時(shí)有著ID號(hào)大的節(jié)點(diǎn)將被選擇去恢復(fù)連接.

根據(jù)以上標(biāo)準(zhǔn)如果割點(diǎn)6失效，圖3中圓圈圈起來(lái)的將是備份的最小連通支配集.

圖3 選擇最小的CDSFig.3 Select the minimal CDS

2.2.2 失效監(jiān)測(cè)

執(zhí)行器節(jié)點(diǎn)會(huì)定期發(fā)送心跳消息給它們的鄰居節(jié)點(diǎn)來(lái)確保它的功能有效，同時(shí)報(bào)告自己的更新?tīng)顟B(tài).心跳消息包的丟失可作為節(jié)點(diǎn)失效監(jiān)測(cè)的一種手段.

節(jié)點(diǎn)與其鄰居交換心跳消息作為網(wǎng)絡(luò)操作的一部分，以更新自己的狀態(tài)，通過(guò)這些消息通知選定的備份節(jié)點(diǎn).一個(gè)執(zhí)行器節(jié)點(diǎn)一旦收到備份通知，它開(kāi)始通過(guò)心跳包監(jiān)測(cè)割點(diǎn).丟失一定數(shù)量的連續(xù)心跳包時(shí)，備份節(jié)點(diǎn)視割點(diǎn)失效.

2.3 恢復(fù)過(guò)程

盡管非割點(diǎn)的失效不會(huì)對(duì)網(wǎng)絡(luò)連通性造成任何問(wèn)題，但它卻會(huì)產(chǎn)生其他問(wèn)題，如形成覆蓋漏洞、擾亂某個(gè)特定區(qū)域的數(shù)據(jù)收集等.在這種情況下，根據(jù)應(yīng)用級(jí)別的要求，這些問(wèn)題仍需要處理.論文在恢復(fù)的過(guò)程中首先考慮到執(zhí)行器節(jié)點(diǎn)連接的恢復(fù)，同時(shí)也考慮到覆蓋漏洞的修復(fù).

2.3.1 最佳位置確定

定理1 若要保證移動(dòng)的執(zhí)行器節(jié)點(diǎn)距離最短且由于移動(dòng)覆蓋面積減少最小，則移動(dòng)執(zhí)行器節(jié)點(diǎn)應(yīng)放置在A(yíng)C邊A的中垂線(xiàn)上.

圖4 最佳位置計(jì)算模型Fig.4 The calculation model of best position

證明 如圖4所示，記節(jié)點(diǎn)移動(dòng)到最佳位置形成ABCD的面積為S1，為了使由于節(jié)點(diǎn)失效導(dǎo)致的覆蓋率減少到最小，保證修復(fù)連接移動(dòng)節(jié)點(diǎn)數(shù)目最少且移動(dòng)的距離最小，S1的面積應(yīng)達(dá)到最大.ΔABC的面積為 S2，ΔAEC的面積為 S3.由于ΔABC的面積S2是固定的，所以要使得S1最大，需要S3取最大值.過(guò)點(diǎn)E做邊AC的垂線(xiàn)EF，垂足為F，則其中，||、||分別表示線(xiàn)段AC、EF的模值.由于A(yíng)C為固定值，要使S3最大，需EF取最大值.假設(shè) AE≤ CE，相應(yīng)地，有AF≤CF.由于A(yíng)C=AF+CF，所以AC≤2CF，即

作為新的邊緣節(jié)點(diǎn)，移動(dòng)節(jié)點(diǎn)E要保證與C的通信，故有CE≤Rc.在ΔEFC中由勾股定理可知

從而在CE取最大值Rc，CF取最小值A(chǔ)C/2，EF可取最大值，此時(shí)S3最大.因?yàn)镃F=AC/2，故F為AC的中點(diǎn)，因此移動(dòng)節(jié)點(diǎn)的位置E點(diǎn)位于A(yíng)C的中垂線(xiàn)上移動(dòng)距離最短，這時(shí)才可能獲得最大的感知面積，覆蓋減少率最小.

2.3.2 恢復(fù)過(guò)程描述

圖5顯示了當(dāng)執(zhí)行器節(jié)點(diǎn)6失效時(shí)最小節(jié)點(diǎn)塊怎樣移動(dòng)來(lái)恢復(fù)連接.顯然，節(jié)點(diǎn)6是一個(gè)割點(diǎn)并為其備份最小連通支配集來(lái)檢測(cè)失效，節(jié)點(diǎn)5是在最小連通支配集中失效節(jié)點(diǎn)6的一跳鄰居節(jié)點(diǎn).圖5(a)～(b)確定最佳位置點(diǎn)，使失效節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)向最佳位置點(diǎn)移動(dòng).在圖5(c)中，節(jié)點(diǎn)5向最佳位置點(diǎn)移動(dòng)，并發(fā)送恢復(fù)消息給它的子節(jié)點(diǎn).在節(jié)點(diǎn)5移動(dòng)過(guò)程中，其子節(jié)點(diǎn)產(chǎn)生級(jí)聯(lián)運(yùn)動(dòng)始終與節(jié)點(diǎn)5保持連接，見(jiàn)圖5(d).子節(jié)點(diǎn)的級(jí)聯(lián)運(yùn)動(dòng)對(duì)當(dāng)前的拓?fù)溥B接不產(chǎn)生影響.在圖5(e)中子節(jié)點(diǎn)5，7移動(dòng)前通知它們的子節(jié)點(diǎn)移動(dòng)保持連接.重復(fù)以上步驟直至整個(gè)網(wǎng)絡(luò)連接恢復(fù).

圖5 恢復(fù)過(guò)程圖Fig.5 Restoration process diagram

3 算法仿真結(jié)果與分析

對(duì)提出的算法進(jìn)行仿真，并將其性能與先前文章提到的RIM算法、DARA算法進(jìn)行比較.仿真環(huán)境部署了一個(gè)由不同數(shù)量的節(jié)點(diǎn)組成的拓?fù)浣Y(jié)構(gòu).節(jié)點(diǎn)隨機(jī)分布在面積為1 000 m×600 m的沒(méi)有障礙的區(qū)域，即節(jié)點(diǎn)移動(dòng)到一個(gè)新位置是不存在阻礙的.節(jié)點(diǎn)的數(shù)量分別被設(shè)置為20，40，60，80和100.節(jié)點(diǎn)的通信范圍也分別設(shè)置成50，75，100和125 m.當(dāng)改變節(jié)點(diǎn)的數(shù)量時(shí)，“r”是固定值100 m;當(dāng)改變通信范圍時(shí)，“N”是固定值100.所得結(jié)果是將算法取50次平均值得到的.通過(guò)以下指標(biāo)評(píng)估MCDSR算法的性能:

(1)恢復(fù)過(guò)程節(jié)點(diǎn)移動(dòng)數(shù)目:這個(gè)指標(biāo)反映了由于節(jié)點(diǎn)失效導(dǎo)致的對(duì)網(wǎng)絡(luò)拓?fù)涞挠绊?，移?dòng)的節(jié)點(diǎn)數(shù)越少說(shuō)明網(wǎng)絡(luò)拓?fù)涓淖冊(cè)叫?，越利于網(wǎng)絡(luò)整體的穩(wěn)定.由圖6中移動(dòng)節(jié)點(diǎn)數(shù)量的圖線(xiàn)可見(jiàn)，DARA算法比RIM算法有相當(dāng)大的改進(jìn)，論文提出的算法得到的移動(dòng)節(jié)點(diǎn)數(shù)較DARA算法又有一定的減少，且隨著節(jié)點(diǎn)密度的增加緩慢增加.DARA算法優(yōu)于RIM算法的原因在于節(jié)點(diǎn)的移動(dòng)集中在損壞節(jié)點(diǎn)的附近.論文算法移動(dòng)節(jié)點(diǎn)數(shù)會(huì)進(jìn)一步減少的原因在于每次在網(wǎng)絡(luò)分隔區(qū)中總是尋找最小的連通支配集，而且如果子節(jié)點(diǎn)在先驅(qū)節(jié)點(diǎn)的連接范圍內(nèi)就不需要移動(dòng)，這就減少了節(jié)點(diǎn)移動(dòng)數(shù)量.移動(dòng)數(shù)量會(huì)隨著節(jié)點(diǎn)密度增加的原因是，密度越大，損壞節(jié)點(diǎn)周?chē)囊惶?jié)點(diǎn)就越多，牽涉到修復(fù)的節(jié)點(diǎn)就越多.

圖6 不同網(wǎng)絡(luò)規(guī)模下節(jié)點(diǎn)移動(dòng)數(shù)量與不同通信半徑下節(jié)點(diǎn)移動(dòng)數(shù)量Fig.6 Mobile nodes in different network scale and mobile nodes in different communication radius

(2)節(jié)點(diǎn)總的移動(dòng)距離:連通性恢復(fù)過(guò)程中涉及的所有節(jié)點(diǎn)移動(dòng)的總距離，這個(gè)指標(biāo)度量了整個(gè)網(wǎng)絡(luò)由于節(jié)點(diǎn)的移動(dòng)而消耗能源的多少.

圖7顯示了連接恢復(fù)完成后節(jié)點(diǎn)總移動(dòng)距離.

圖7 節(jié)點(diǎn)總的移動(dòng)距離Fig.7 The total moving distance of the node

MCDSR算法明顯優(yōu)于現(xiàn)有的算法DARA、RIM.如圖所示，即使節(jié)點(diǎn)數(shù)目、通信范圍擴(kuò)大，MCDSR算法總移動(dòng)距離也沒(méi)有突然的變化.這是因?yàn)镸CDSR每次移動(dòng)的都是分區(qū)中的最小連通支配集，產(chǎn)生的級(jí)聯(lián)運(yùn)動(dòng)也是在超出通信范圍內(nèi)才移動(dòng).而RIM算法是所有的一跳均向失效節(jié)點(diǎn)移動(dòng)，直到連接恢復(fù).因此不管節(jié)點(diǎn)數(shù)目還是通信半徑的增加，RIM的性能也遠(yuǎn)不及MCDSR.

(3)覆蓋度減少的百分比:雖然保證連通性是恢復(fù)算法的主要目標(biāo)，但節(jié)點(diǎn)的覆蓋度對(duì)許多應(yīng)用來(lái)說(shuō)也是非常重要的.一個(gè)節(jié)點(diǎn)的故障通常會(huì)對(duì)覆蓋造成負(fù)面影響.覆蓋度減少的百分比的性能捕獲了節(jié)點(diǎn)移動(dòng)導(dǎo)致的覆蓋損失.

圖8顯示了節(jié)點(diǎn)故障對(duì)覆蓋度產(chǎn)生的影響.改變N和r時(shí)，用覆蓋度減少的百分比來(lái)衡量.圖8(a)表明3種方法的曲線(xiàn)走勢(shì)大致相同.雖然增加節(jié)點(diǎn)密度有利于RIM和DARA的表現(xiàn)，但這兩者的性能仍然比不上MCDSR.

圖8 恢復(fù)后覆蓋面積的減少Fig.8 Reduction of the coverage area after recovery

MCDSR在覆蓋度方面的優(yōu)勢(shì)是由于其對(duì)節(jié)點(diǎn)移動(dòng)范圍的限制，當(dāng)然這會(huì)導(dǎo)致在網(wǎng)絡(luò)邊緣的覆蓋損失.在圖8(b)中，隨著r的增加，網(wǎng)絡(luò)連接變得更加緊密，雖然失效節(jié)點(diǎn)的鄰居數(shù)也在增長(zhǎng).DARA、MCDSR卻表現(xiàn)了良好的覆蓋性能.而RIM算法節(jié)點(diǎn)的定向移動(dòng)使得失效節(jié)點(diǎn)的周?chē)訐頂D，而網(wǎng)絡(luò)邊緣卻無(wú)法覆蓋，這樣就造成了巨大的邊緣覆蓋損失.

4 結(jié)束語(yǔ)

論文提出了一種基于最小連通支配集移動(dòng)的節(jié)點(diǎn)失效恢復(fù)算法，主要關(guān)注內(nèi)執(zhí)行器網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)失效時(shí)的連接恢復(fù).MCDSR算法利用基于深度優(yōu)先遍歷割點(diǎn)搜索算法確定關(guān)鍵節(jié)點(diǎn)，并根據(jù)節(jié)點(diǎn)位置和節(jié)點(diǎn)度為它們指定備份節(jié)點(diǎn).一旦備份節(jié)點(diǎn)檢測(cè)到關(guān)鍵節(jié)點(diǎn)失效就啟動(dòng)恢復(fù)過(guò)程.在恢復(fù)過(guò)程中，該算法為備份節(jié)點(diǎn)找到一個(gè)最佳位置來(lái)恢復(fù)連接.仿真結(jié)果證明，和現(xiàn)有的一些方法相比，MCDSR在滿(mǎn)足應(yīng)用需求、減少恢復(fù)開(kāi)銷(xiāo)和限制關(guān)鍵節(jié)點(diǎn)故障對(duì)覆蓋及連通的影響等方面具有優(yōu)勢(shì).

［1］ Akyildiz I F，Kasimoglu I H.Wireless sensor and actor networks:research challenges［J］.Ad Hoc Networks，2004，2(4):351－367.

［2］ Akkaya K，Janapala S.Maximizing connected coverage via controlled actor relocation in wireless sensor and actor networks［J］.Computer Networks，2008，52(14):2779 －2796.

［3］ Chang CY，Xiang Y，Shi M L.Development and status of vehicular ad hoc networks［J］.Journal on Communications，2007，28(11):116 －126.

［4］ Younis M，Akkaya K.Strategies and techniques for node placement in wireless sensor networks:a survey［J］.Ad Hoc Networks，2008，6(4):621 －655

［5］ Akkaya K，Senel F，Thimmapuram A.Distributed recovery from network partitioning in movable sensor/actor networks via controlled mobility［J］.IEEE Transactions on Computers，2010，59(2):258 －71.

［6］ Tamboli N，Younis M.Coverage － aware connectivity restoration in mobile sensor networks［J］.Journal of Network and Computer Applications，2010，33(4):363 －374.

［7］ Basu P，Redi J.Movement control algorithms for realization of fault-tolerant and hoc robot networks［J］.IEEE Networks，2004，18(4):36 －44.

［8］ Abbasi A，Younis M，Akkaya K.Movement－assisted connectivity restoration in wireless sensor and actor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20(9):1366 － 1379.

［9］ Younis M，Lee S，Gupta S，et al.A localized self－ healing algorithm for networks of moveable sensor nodes［C］∥Global Telecommunications Conference，IEEE Globecom，2008:1 －5.

［10］ Yang Y Y.Adaptive energy efficient sensor scheduling for wireless sensor networks［J］.Optimization Letters，2010，4(3):359－369

［11］ Du J，Xie L，Sun X，et al.Application－oriented fault detection and recovery algorithm for wireless sensor and actor networks［J/OL］.International Journal of DistributedSensorNetworks，2012:273792.［2012 － 09 － 17］.http://www.hindawi.com/journals/ijdsn/2012/273792/.