曉璇, ,,

(南京郵電大學(xué) a.寬帶無(wú)線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室; b.江蘇省無(wú)線通信重點(diǎn)實(shí)驗(yàn)室,南京 210003)

0 概述

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)[1]是由大量密集部署在目標(biāo)區(qū)域的節(jié)點(diǎn)構(gòu)成的一種自組織網(wǎng)絡(luò)應(yīng)用系統(tǒng)[2]。該系統(tǒng)由大量小規(guī)模、低成本的傳感器構(gòu)成,將在目標(biāo)區(qū)域采集到的數(shù)據(jù)匯集到基站[3]。WSN起源于軍事領(lǐng)域的應(yīng)用,近年來(lái),其在環(huán)境監(jiān)測(cè)、醫(yī)療護(hù)理、火災(zāi)監(jiān)測(cè)、交通監(jiān)控等領(lǐng)域也得到廣泛的應(yīng)用[4]。

由于傳感器自身資源及能量的限制,傳感器節(jié)點(diǎn)易受到損壞,關(guān)鍵節(jié)點(diǎn)的損壞將導(dǎo)致網(wǎng)絡(luò)被分割成不連通的分區(qū),給實(shí)際應(yīng)用帶來(lái)不便。無(wú)線傳感器網(wǎng)絡(luò)的故障一般分為小規(guī)模故障和大規(guī)模故障,小規(guī)模故障往往源于個(gè)別傳感器能量耗盡,導(dǎo)致鄰居節(jié)點(diǎn)之間無(wú)法連通;大規(guī)模故障往往源于惡劣環(huán)境下,如森林中,由于失火導(dǎo)致大量節(jié)點(diǎn)失效,造成網(wǎng)絡(luò)被分割成不連通的分區(qū)。重新將網(wǎng)絡(luò)連通對(duì)于延長(zhǎng)網(wǎng)絡(luò)生存周期尤為重要。對(duì)于網(wǎng)絡(luò)修復(fù)問(wèn)題的研究業(yè)界已經(jīng)取得了一定的進(jìn)展,拓?fù)鋱D論中有許多算法,如最短路徑算法、搜索算法、生成樹算法等在網(wǎng)絡(luò)修復(fù)中也得以應(yīng)用[5]。本文分析各類無(wú)線傳感器網(wǎng)絡(luò)修復(fù)算法,并針對(duì)不同的網(wǎng)絡(luò)故障規(guī)模,對(duì)以往的研究進(jìn)行分類和總結(jié)。

1 網(wǎng)絡(luò)修復(fù)算法分類分析

在研究無(wú)線傳感器網(wǎng)絡(luò)修復(fù)算法時(shí),需要根據(jù)不同的應(yīng)用需求采用不同的系統(tǒng)模型。圖1對(duì)現(xiàn)有的網(wǎng)絡(luò)修復(fù)算法進(jìn)行分類與總結(jié)。根據(jù)網(wǎng)絡(luò)破壞規(guī)模的不同,可將已有的算法分為小規(guī)模故障修復(fù)算法和大規(guī)模故障修復(fù)算法兩大類。

圖1 網(wǎng)絡(luò)修復(fù)算法的分類

在小規(guī)模故障中,根據(jù)修復(fù)算法的觸發(fā)條件,可以將網(wǎng)絡(luò)修復(fù)算法分為不區(qū)分節(jié)點(diǎn)重要度的算法和區(qū)分節(jié)點(diǎn)重要度的算法兩類。如RIM[6]、MCDS[7]算法,只要節(jié)點(diǎn)發(fā)生故障就立即觸發(fā)修復(fù)程序,這容易造成不必要的修復(fù),增大開銷。DCR[8]、DCRS[9]等算法先對(duì)節(jié)點(diǎn)進(jìn)行重要度判斷,只有當(dāng)失效節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)時(shí)才啟動(dòng)修復(fù)算法,即為區(qū)分節(jié)點(diǎn)重要度的算法。該類算法可以從4個(gè)方面進(jìn)行分類:1)根據(jù)關(guān)鍵節(jié)點(diǎn)的判斷時(shí)間分類;2)根據(jù)關(guān)鍵節(jié)點(diǎn)的判斷方法分類;3)根據(jù)重定位節(jié)點(diǎn)移動(dòng)方式分類;4)根據(jù)算法實(shí)現(xiàn)角度分類。在大規(guī)模故障中,可以根據(jù)算法的實(shí)現(xiàn)角度分為2類:1)集中式算法,網(wǎng)絡(luò)中的節(jié)點(diǎn)可以提前知道每個(gè)分區(qū)的信息,有利于修復(fù)算法的執(zhí)行;2)分布式算法,節(jié)點(diǎn)對(duì)分區(qū)的數(shù)目以及位置等信息未知,可以有效降低消息成本。下面對(duì)具體算法的適用環(huán)境及優(yōu)缺點(diǎn)進(jìn)行分析與比較。

2 小規(guī)模故障的拓?fù)湫迯?fù)算法

該類算法主要考慮單個(gè)節(jié)點(diǎn)故障的情況,網(wǎng)絡(luò)通過(guò)故障節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的自身移動(dòng)完成網(wǎng)絡(luò)修復(fù),而源宿節(jié)點(diǎn)的尋路過(guò)程需要消耗能量[10],因此,必須盡可能減少移動(dòng)距離來(lái)延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。

根據(jù)算法觸發(fā)條件的不同,小規(guī)模故障修復(fù)算法可分為2類:1)不區(qū)分故障節(jié)點(diǎn)重要度的算法;2)區(qū)分故障節(jié)點(diǎn)重要度的算法。前者適用于對(duì)網(wǎng)絡(luò)覆蓋率要求較高的網(wǎng)絡(luò),為了降低網(wǎng)絡(luò)覆蓋率的損失,只要有節(jié)點(diǎn)故障,就啟動(dòng)修復(fù)算法。后者適用于將網(wǎng)絡(luò)連通性作為修復(fù)目標(biāo)的網(wǎng)絡(luò),該類算法先對(duì)故障節(jié)點(diǎn)的重要度進(jìn)行判斷,僅當(dāng)故障節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)時(shí),才啟動(dòng)修復(fù)算法,如此可以有效減少節(jié)點(diǎn)重定位過(guò)程中的能量消耗,避免不必要的修復(fù)。下面針對(duì)這2類算法給出詳細(xì)的分類。

2.1 不區(qū)分故障節(jié)點(diǎn)的重要度

冗余節(jié)點(diǎn)移動(dòng)算法[11]、MCDS[6]算法、RIM[7]算法等修復(fù)算法不對(duì)節(jié)點(diǎn)的重要度進(jìn)行評(píng)估,這樣雖然可以在一定程度上降低消息傳輸?shù)某杀?但是會(huì)造成不必要的修復(fù),增大網(wǎng)絡(luò)中重定位節(jié)點(diǎn)的數(shù)目,導(dǎo)致節(jié)點(diǎn)總移動(dòng)距離以及網(wǎng)絡(luò)修復(fù)時(shí)間的增加。

當(dāng)有節(jié)點(diǎn)失效時(shí),冗余節(jié)點(diǎn)移動(dòng)算法調(diào)用網(wǎng)絡(luò)中的冗余節(jié)點(diǎn)移動(dòng)到失效節(jié)點(diǎn)位置。該修復(fù)方法復(fù)雜度低,但只適用于節(jié)點(diǎn)密度較高的情況。RIM算法中失效節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)向失效節(jié)點(diǎn)移動(dòng),直到這些鄰居節(jié)點(diǎn)可以互連。如圖2所示,當(dāng)B、A、G、H節(jié)點(diǎn)檢測(cè)到節(jié)點(diǎn)F故障后,開始向F移動(dòng),同時(shí)需考慮自身與鄰居節(jié)點(diǎn)的距離、度等因素。該算法在網(wǎng)絡(luò)規(guī)模增加的情況下,節(jié)點(diǎn)的總移動(dòng)距離會(huì)大幅增加。

圖2 RIM算法拓?fù)浣Y(jié)構(gòu)

2.2 區(qū)分故障節(jié)點(diǎn)的重要度

提前對(duì)節(jié)點(diǎn)進(jìn)行重要度判斷,針對(duì)關(guān)鍵節(jié)點(diǎn)和非關(guān)鍵節(jié)點(diǎn)的故障采取不同的修復(fù)措施可以減少不必要的修復(fù),縮短移動(dòng)距離,但是會(huì)增大消息傳輸?shù)某杀尽Ｏ旅娓鶕?jù)關(guān)鍵節(jié)點(diǎn)判斷時(shí)機(jī)、判斷方法、候選節(jié)點(diǎn)選取規(guī)則和移動(dòng)方式的不同對(duì)此類算法進(jìn)行分類。

2.2.1 根據(jù)關(guān)鍵節(jié)點(diǎn)判斷時(shí)機(jī)的分類

1)主動(dòng)修復(fù)

主動(dòng)修復(fù)方法[8-9,12-14]是指在節(jié)點(diǎn)未失效之前先進(jìn)行重要度判斷,并將該信息傳遞給鄰居節(jié)點(diǎn),當(dāng)節(jié)點(diǎn)失效時(shí)立即修復(fù),可以有效提高修復(fù)效率。

DARA[12]算法根據(jù)節(jié)點(diǎn)的度和與故障節(jié)點(diǎn)的距離給每個(gè)故障節(jié)點(diǎn)選擇候選節(jié)點(diǎn),并級(jí)聯(lián)地用候選節(jié)點(diǎn)來(lái)取代故障節(jié)點(diǎn)。該算法容易出現(xiàn)過(guò)度替代,且由于不提供關(guān)鍵節(jié)點(diǎn)的判斷機(jī)制,每個(gè)節(jié)點(diǎn)需要知道整個(gè)拓?fù)涞男畔ⅰADRA[13]算法中每個(gè)節(jié)點(diǎn)存儲(chǔ)自身兩跳范圍內(nèi)的節(jié)點(diǎn)信息,采用最小連通支配集(Connected Dominating Set,CDS)將節(jié)點(diǎn)區(qū)分為支配節(jié)點(diǎn)和被支配節(jié)點(diǎn)2類,并以此給出割點(diǎn)的確定方案。如果割點(diǎn)的鄰居節(jié)點(diǎn)中存在被支配節(jié)點(diǎn),則當(dāng)割點(diǎn)失效時(shí)該節(jié)點(diǎn)鄰居節(jié)點(diǎn)中的被支配節(jié)點(diǎn)取代割點(diǎn)的位置;否則,每個(gè)割點(diǎn)找到最近的鄰居節(jié)點(diǎn)來(lái)取代自己,直到這個(gè)鄰居節(jié)點(diǎn)是被支配節(jié)點(diǎn)為止。相對(duì)于DARA算法來(lái)說(shuō),PADRA算法總移動(dòng)距離較少,降低了能耗,延長(zhǎng)了網(wǎng)絡(luò)的生命周期,但是該算法引入的深度優(yōu)先搜索(Depth First Search,DFS)算法復(fù)雜度較高,增大了消息傳輸成本。

2)被動(dòng)修復(fù)

被動(dòng)修復(fù)方法[15-17]是指在節(jié)點(diǎn)失效后才采取相應(yīng)的措施進(jìn)行網(wǎng)絡(luò)修復(fù)。CCRA[15]、LeDiR[16]算法為被動(dòng)修復(fù)算法,只需要判斷失效節(jié)點(diǎn)的重要性,這可以有效降低消息傳輸成本,但會(huì)增大網(wǎng)絡(luò)修復(fù)時(shí)間。LeDiR[16]重定位盡可能少的節(jié)點(diǎn),通過(guò)塊移動(dòng)來(lái)完成網(wǎng)絡(luò)修復(fù),確保任何一對(duì)受影響的節(jié)點(diǎn)相對(duì)故障前的狀態(tài)路徑是沒(méi)有擴(kuò)展的。被動(dòng)修復(fù)方法分為4個(gè)步驟:(1)故障檢測(cè);(2)最小塊確認(rèn);(3)取代故障節(jié)點(diǎn);(4)子節(jié)點(diǎn)移動(dòng)。該算法降低了參與移動(dòng)節(jié)點(diǎn)各自的移動(dòng)距離,但是增大了總移動(dòng)距離。此外,該算法采用的塊移動(dòng)方法增大了平均移動(dòng)節(jié)點(diǎn)數(shù)目以及能量消耗。

2.2.2 根據(jù)關(guān)鍵節(jié)點(diǎn)判斷方法的分類

通過(guò)一跳鄰居節(jié)點(diǎn)來(lái)判斷網(wǎng)絡(luò)中的節(jié)點(diǎn)是否為關(guān)鍵節(jié)點(diǎn),可以降低算法的復(fù)雜度,有效減少消息傳輸?shù)某杀?在一定程度上降低能量消耗。DCR[8]算法根據(jù)一跳鄰居節(jié)點(diǎn)的位置信息提前確定關(guān)鍵節(jié)點(diǎn),并在鄰居節(jié)點(diǎn)中選擇候選節(jié)點(diǎn),當(dāng)節(jié)點(diǎn)失效時(shí),候選節(jié)點(diǎn)就會(huì)啟動(dòng)網(wǎng)絡(luò)修復(fù)程序。該算法采用提前預(yù)測(cè)與及時(shí)響應(yīng)相結(jié)合的方式,適用于對(duì)時(shí)延有限制的應(yīng)用。如圖3所示,A為非關(guān)鍵節(jié)點(diǎn),即使節(jié)點(diǎn)A故障,它的一跳鄰居節(jié)點(diǎn)相互之間仍然為連通;節(jié)點(diǎn)F的故障會(huì)導(dǎo)致它的鄰居節(jié)點(diǎn)被分割成2個(gè)不連通的分區(qū),因此,節(jié)點(diǎn)F為關(guān)鍵節(jié)點(diǎn)。由于該算法僅依賴于一跳的鄰居節(jié)點(diǎn)信息來(lái)確定關(guān)鍵節(jié)點(diǎn),可能出現(xiàn)所選擇的關(guān)鍵節(jié)點(diǎn)并非為割點(diǎn)的情況,造成不必要的修復(fù)。

圖3 關(guān)鍵節(jié)點(diǎn)確定

在確定關(guān)鍵節(jié)點(diǎn)時(shí),既需要依賴盡可能少的局部信息來(lái)減少能耗,又需要保證消息的價(jià)值。僅根據(jù)一跳鄰居節(jié)點(diǎn)判定關(guān)鍵節(jié)點(diǎn)易造成誤判,采用DFS算法復(fù)雜度較高,因此,C2AM[9]、CCRA[15]以及DCRS[9]提出根據(jù)兩跳鄰居節(jié)點(diǎn)的信息來(lái)判斷節(jié)點(diǎn)是否為關(guān)鍵節(jié)點(diǎn)。DCRS[9]算法根據(jù)一跳鄰居節(jié)點(diǎn)的位置信息和部分兩跳鄰居節(jié)點(diǎn)來(lái)判定關(guān)鍵節(jié)點(diǎn),在消息傳輸?shù)某杀竞拖⒌膬r(jià)值之間尋求平衡。此外,DCRS通過(guò)設(shè)定閾值改善了級(jí)聯(lián)算法,限制了節(jié)點(diǎn)重定位的范圍,降低了重定位中長(zhǎng)路由的風(fēng)險(xiǎn),有效減少了總移動(dòng)距離以及移動(dòng)節(jié)點(diǎn)數(shù)目。

PADRA算法通過(guò)確定網(wǎng)絡(luò)的CDS來(lái)判斷節(jié)點(diǎn)是否為關(guān)鍵節(jié)點(diǎn),也存在算法假設(shè)每個(gè)節(jié)點(diǎn)對(duì)該信息已知,如DARA算法和CVTR[14]算法。在此類算法中,每個(gè)節(jié)點(diǎn)需要提前知曉整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?具有一定的局限性。與其他算法不同的是,CVTR算法針對(duì)割點(diǎn)和非割點(diǎn)采取不同的修復(fù)措施,而并非忽略非割點(diǎn)的故障,這樣可以有效降低覆蓋損失率,使得修復(fù)后的網(wǎng)絡(luò)覆蓋率達(dá)到90%,且總移動(dòng)節(jié)點(diǎn)數(shù)目較少,但是修復(fù)過(guò)程中總移動(dòng)距離較大,能耗過(guò)大。

2.2.3 根據(jù)重定位節(jié)點(diǎn)移動(dòng)方式的分類

塊移動(dòng)[16]是指根據(jù)節(jié)點(diǎn)原先的位置,分區(qū)中的領(lǐng)導(dǎo)節(jié)點(diǎn)向著失效節(jié)點(diǎn)的位置移動(dòng),分區(qū)中的其他節(jié)點(diǎn)保持原先的鏈路拓?fù)涓S著領(lǐng)導(dǎo)節(jié)點(diǎn)的方向移動(dòng),該類算法移動(dòng)節(jié)點(diǎn)數(shù)目過(guò)多,總移動(dòng)距離較大。

級(jí)聯(lián)移動(dòng)[17]相對(duì)塊移動(dòng)來(lái)說(shuō),只需要移動(dòng)相對(duì)較少數(shù)量的節(jié)點(diǎn),此外塊移動(dòng)需要分區(qū)中的每個(gè)節(jié)點(diǎn)知道各自需要移動(dòng)的位置,增大了消息傳輸?shù)某杀?而級(jí)聯(lián)移動(dòng)中節(jié)點(diǎn)只需知道局部范圍內(nèi)鄰居節(jié)點(diǎn)的信息。根據(jù)研究目標(biāo)的不同,不同算法的級(jí)聯(lián)移動(dòng)策略也不同,如DARA需要根據(jù)鄰居節(jié)點(diǎn)的度和距離選擇候選節(jié)點(diǎn),PADRA根據(jù)動(dòng)態(tài)規(guī)劃選擇需要重定位的節(jié)點(diǎn),DCRS根據(jù)CDS確定關(guān)鍵節(jié)點(diǎn)和候選節(jié)點(diǎn),并給定閾值來(lái)確定如何實(shí)現(xiàn)級(jí)聯(lián)移動(dòng)。

2.2.4 根據(jù)算法實(shí)現(xiàn)方式的分類

集中式算法[6,11]是指在算法執(zhí)行時(shí),節(jié)點(diǎn)相互之間存在聯(lián)系,以快速地完成網(wǎng)絡(luò)修復(fù),算法實(shí)現(xiàn)比較簡(jiǎn)單。缺點(diǎn)是每個(gè)節(jié)點(diǎn)都需要知道整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?會(huì)造成消息傳輸成本過(guò)大,算法效率隨著問(wèn)題規(guī)模的增大而增大,僅適用于小規(guī)模的網(wǎng)絡(luò)。

局部分布式算法[17]是指局部地以一部分為單位分別執(zhí)行算法,每個(gè)節(jié)點(diǎn)僅需要保存局部節(jié)點(diǎn)的信息,減少了消息傳遞,可以有效延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間,而且算法的效率隨著網(wǎng)絡(luò)規(guī)模的增大變化不大,因此,該算法適用于大規(guī)模的網(wǎng)絡(luò),缺點(diǎn)是算法實(shí)現(xiàn)相對(duì)復(fù)雜。

2.3 算法分類與歸納比較

大多文獻(xiàn)都是在某些限制條件下提出了網(wǎng)絡(luò)修復(fù)算法,只能針對(duì)某些性能進(jìn)行改善。表1對(duì)已有的不同算法實(shí)現(xiàn)方法和性能進(jìn)行了比較。除了上文提到的參數(shù)之外,總移動(dòng)距離是指從網(wǎng)絡(luò)修復(fù)開始至整個(gè)網(wǎng)絡(luò)連通參與移動(dòng)的所有節(jié)點(diǎn)的總移動(dòng)距離?？傄苿?dòng)節(jié)點(diǎn)數(shù)目是指參與到網(wǎng)絡(luò)修復(fù)過(guò)程中的總節(jié)點(diǎn)數(shù)目,當(dāng)大量的節(jié)點(diǎn)移動(dòng)時(shí)所需要消耗的能量較多,但是當(dāng)較少的移動(dòng)節(jié)點(diǎn)完成網(wǎng)絡(luò)修復(fù)時(shí),又會(huì)造成大量的通信開銷,使得移動(dòng)節(jié)點(diǎn)的能量消耗過(guò)大,造成節(jié)點(diǎn)之間負(fù)載的不平衡,如CCRA[15]算法。因此,針對(duì)單個(gè)節(jié)點(diǎn)故障的網(wǎng)絡(luò)修復(fù)算法,研究的重點(diǎn)是找到總移動(dòng)節(jié)點(diǎn)數(shù)目和總移動(dòng)距離之間的平衡,在完成網(wǎng)絡(luò)修復(fù)的同時(shí)延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。

表1 單個(gè)節(jié)點(diǎn)失效算法的性能比較

3 大規(guī)模故障的拓?fù)湫迯?fù)算法

由于傳感器節(jié)點(diǎn)的資源和能量的限制使得傳感器節(jié)點(diǎn)不適合長(zhǎng)距離移動(dòng),因此通過(guò)鄰居節(jié)點(diǎn)重定位完成網(wǎng)絡(luò)修復(fù)只適合處理單個(gè)節(jié)點(diǎn)故障的情況,當(dāng)網(wǎng)絡(luò)出現(xiàn)大規(guī)模故障產(chǎn)生分區(qū)時(shí),需要往分區(qū)之間填充中繼節(jié)點(diǎn)(Relay Node,RN)來(lái)完成網(wǎng)絡(luò)修復(fù)。該類算法的主要目標(biāo)是減少所需RN的數(shù)目,一般假設(shè)RN相對(duì)普通的傳感器節(jié)點(diǎn)來(lái)說(shuō)具有更高的能量以及更大的通信范圍。根據(jù)對(duì)網(wǎng)絡(luò)整體拓?fù)湫畔⒌囊阎闆r,從算法實(shí)現(xiàn)角度,將此類算法分為集中式算法和分布式算法。

3.1 集中式算法

在網(wǎng)絡(luò)出現(xiàn)大規(guī)模故障的情況中,已有的多數(shù)算法均為集中式算法,此類算法的優(yōu)點(diǎn)在于網(wǎng)絡(luò)中的節(jié)點(diǎn)可以提前知道每個(gè)分區(qū)的信息,包括分區(qū)的數(shù)目和位置,有利于修復(fù)算法的執(zhí)行,但是集中式算法的消息成本較大。下面針對(duì)此類文獻(xiàn)中的代表性算法進(jìn)行介紹。

3.1.1 蜘蛛網(wǎng)算法和ORC算法

大部分算法只關(guān)注減少RN的數(shù)目,導(dǎo)致新放置的RN大多為割點(diǎn),網(wǎng)絡(luò)容易再次出現(xiàn)分區(qū)。為了減少割點(diǎn)所占的比例,蜘蛛網(wǎng)算法[18]與ORC算法[19]提出通過(guò)Graham Scan算法求得凸多邊形,然后以輪的方式迭代確定RN的放置位置。

蜘蛛網(wǎng)算法建立了一個(gè)蜘蛛網(wǎng)的拓?fù)鋱D,從每個(gè)分區(qū)到重心部署節(jié)點(diǎn),直到所有的分區(qū)連通。如圖4所示。其中,實(shí)線代表中繼節(jié)點(diǎn)之間的連線,虛線代表分區(qū)代表節(jié)點(diǎn)之間或者分區(qū)代表節(jié)點(diǎn)和中繼節(jié)點(diǎn)之間的連線。從分區(qū)Pi往重心依次放置中繼節(jié)點(diǎn)Ri。在朝著重心部署RN的過(guò)程中,為了增加連通的強(qiáng)度,一個(gè)分區(qū)至少應(yīng)該和它的左右2個(gè)鄰居分區(qū)相連接。該算法以增加RN的數(shù)目為代價(jià)獲得了多個(gè)可取的功能,不僅增加了網(wǎng)絡(luò)的總覆蓋率,而且減少了割點(diǎn)所占的百分比,增加了平均節(jié)點(diǎn)的度,可以更好地平衡RN的流量負(fù)載分布。ORC算法通過(guò)每一輪尋找網(wǎng)絡(luò)分區(qū)的凸多邊形和Steiner點(diǎn)(Steiner Point,SP)的方式確定RN的位置。第1輪求得的SP為第2輪求凸多邊形的初始節(jié)點(diǎn),以此類推,直到整個(gè)網(wǎng)絡(luò)連通。相對(duì)蜘蛛網(wǎng)算法,ORC算法降低了RN的數(shù)目,但是網(wǎng)絡(luò)對(duì)故障的容忍性較低。

圖4 蜘蛛網(wǎng)部署中繼節(jié)點(diǎn)的算法

3.1.2 CIST算法

由于分區(qū)的大小以及分區(qū)間的距離具有隨機(jī)性,因此每個(gè)分區(qū)選取一個(gè)代表節(jié)點(diǎn)會(huì)造成RN的不合理使用。CIST[20]算法提出需要針對(duì)連接的不同分區(qū)選擇不同的代表節(jié)點(diǎn)。CIST算法首先求得各個(gè)分區(qū)建立的最小生成樹,然后確定所有可能的三角形集合,選定權(quán)重最小的三角形,形成Steiner最小樹,最后將得到的樹和未連接的分區(qū)通過(guò)最小生成樹連接起來(lái)。CIST算法采用迭代尋找連接3個(gè)分區(qū)的最佳三角集合的方法,相對(duì)于沿著最小生成樹的邊放置RN的方式,該算法所需的RN的數(shù)目較少,但是復(fù)雜度較高。

3.1.3 特殊應(yīng)用場(chǎng)景下的修復(fù)算法

有些文獻(xiàn)針對(duì)特定的應(yīng)用場(chǎng)景提出了網(wǎng)絡(luò)修復(fù)算法,如虛擬骨干網(wǎng)修復(fù)算法[21]和移動(dòng)與固定RN混合部署算法[22]。虛擬骨干網(wǎng)修復(fù)算法針對(duì)支配節(jié)點(diǎn)出現(xiàn)大規(guī)模故障的情況,通過(guò)給每個(gè)分區(qū)重建支配集CDS來(lái)完成網(wǎng)絡(luò)修復(fù)。

當(dāng)缺少足夠多的RN來(lái)連接所有的分區(qū)時(shí),一些RN可以用作移動(dòng)數(shù)據(jù)采集器(Mobile Data Collector,MDC)來(lái)訪問(wèn)多個(gè)分區(qū)。文獻(xiàn)[22]提出了固定和移動(dòng)的RN數(shù)目動(dòng)態(tài)變化的策略,先假定所有的RN均為MDC,并通過(guò)迭代來(lái)降低MDC的數(shù)目。該算法首先找到成本消耗最小的分區(qū)安置固定的RN,然后根據(jù)閾值來(lái)檢測(cè)是否滿足覆蓋限制條件,若滿足,則對(duì)網(wǎng)絡(luò)分簇,使得每個(gè)MDC訪問(wèn)一個(gè)簇中的每個(gè)分區(qū)。該算法在滿足覆蓋限制條件的同時(shí)可以使最大移動(dòng)距離最小化。但是,MDC實(shí)現(xiàn)的是間斷性的網(wǎng)絡(luò)連接,不可避免地在數(shù)據(jù)采集和傳輸?shù)倪^(guò)程中會(huì)出現(xiàn)時(shí)延,在實(shí)時(shí)的應(yīng)用中這些數(shù)據(jù)是無(wú)效的。

3.2 分布式算法

集中式算法要求網(wǎng)絡(luò)中的節(jié)點(diǎn)需提前掌握整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?但在惡劣環(huán)境中有時(shí)難以獲得該信息,此時(shí)需要采用分布式算法進(jìn)行網(wǎng)絡(luò)修復(fù)。在分布式算法中,通過(guò)RN的安置來(lái)了解整個(gè)網(wǎng)絡(luò)拓?fù)?節(jié)點(diǎn)不需要知道全部拓?fù)湫畔?使得修復(fù)更加迅速,消息成本較低。但是由于分布式算法自身?xiàng)l件的限制,該類算法復(fù)雜度較高,且對(duì)RN配置有較高的要求,如需要攜帶攝像機(jī)來(lái)觀察周圍節(jié)點(diǎn)的分布情況。

3.2.1 CORP算法

文獻(xiàn)[23]提出的CORP算法將網(wǎng)絡(luò)劃分為等大小的網(wǎng)格,通過(guò)每一圈向中間靠攏來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)修復(fù)。具體實(shí)現(xiàn)步驟如下:

1)計(jì)算每個(gè)邊界節(jié)點(diǎn)的鄰居節(jié)點(diǎn)與其他分區(qū)上一圈的邊界節(jié)點(diǎn)的距離,取最小的小區(qū)作為最佳小區(qū),然后確定新一圈的邊界節(jié)點(diǎn),以此循環(huán)下去直到所有分區(qū)布置的最佳鄰居節(jié)點(diǎn)都連通。

2)通過(guò)優(yōu)化布局節(jié)點(diǎn),使用盡可能少的RN實(shí)現(xiàn)連通。

該算法經(jīng)過(guò)RN的安置和裁剪2個(gè)步驟有效地減少RN的數(shù)目,降低了通信能耗。但是該算法并未明確給出代表節(jié)點(diǎn)的選擇方案。

3.2.2 DORMS算法

DORMS[24]算法從每個(gè)分區(qū)向網(wǎng)絡(luò)中心放置RN,只要RN到達(dá)彼此的通信范圍內(nèi),則認(rèn)為分區(qū)連通。算法分為2步:

1)初始化RN安置過(guò)程:每個(gè)分區(qū)朝著網(wǎng)絡(luò)重心的位置放置RN,根據(jù)每個(gè)分區(qū)的標(biāo)號(hào)以及距離中心點(diǎn)的位置給每個(gè)RN標(biāo)號(hào),距離分區(qū)最近的節(jié)點(diǎn)可以確定分區(qū)的位置,并在任意2個(gè)分區(qū)和重心之間確定MST。

2)重定位RN的位置:該部分通過(guò)重定位RN的位置來(lái)減少RN。

該算法不僅連通了網(wǎng)絡(luò),而且生成了更多有效的拓?fù)?增加了連通的平均度,平衡了通信負(fù)載,但是需要的RN數(shù)目較多。

3.2.3 博弈論和RPFP算法

以往大規(guī)模故障修復(fù)的算法均先確定RN的位置然后直接放置RN,修復(fù)的主要目的是減少RN的數(shù)目。但是考慮到實(shí)際應(yīng)用,在確定的位置投放RN并不實(shí)際,因此,文獻(xiàn)[25-26]提出通過(guò)無(wú)人機(jī)在大致的故障區(qū)域投放RN,然后將RN移動(dòng)到需要放置RN的位置來(lái)完成網(wǎng)絡(luò)修復(fù)。該類算法除了需要確定RN的放置位置,也應(yīng)考慮RN的移動(dòng)問(wèn)題,這將增大算法的復(fù)雜度。

博弈論[25]算法提出每個(gè)RN需要包含攝像頭來(lái)確定自己的移動(dòng)方向,根據(jù)分區(qū)的概率密度函數(shù)(Probability Density Function,PDF)來(lái)決定需要連接的目標(biāo)分區(qū),具有高PDF的分區(qū)可以盡早修復(fù)使之成為已連通分區(qū)中的一員,如果和RN連通則具有和已連通分區(qū)相同的納什均衡值,直到整個(gè)網(wǎng)絡(luò)具有相同的均衡值時(shí)證明整個(gè)網(wǎng)絡(luò)已連通,修復(fù)過(guò)程停止。RPFP[26]算法提出每個(gè)分區(qū)采用凸多邊形算法來(lái)確定代表節(jié)點(diǎn),通過(guò)尋找三角形中的0斜率點(diǎn)確定RN的放置位置。算法使用貪心方式來(lái)放置RN,因此,修復(fù)時(shí)間短,但是可能出現(xiàn)多個(gè)RN同時(shí)向一個(gè)目標(biāo)位置移動(dòng)的情況,直到RN感知到彼此存在時(shí)才計(jì)算各自針對(duì)目標(biāo)位置的優(yōu)先級(jí),在一定程度上造成了RN資源的浪費(fèi)。

3.3 算法性能比較

大規(guī)模網(wǎng)絡(luò)破壞的修復(fù)算法一般以所需RN的數(shù)目、平均節(jié)點(diǎn)的度以及平均路徑長(zhǎng)度等性能參數(shù)作為修復(fù)目標(biāo)。所需RN的數(shù)目表示修復(fù)分區(qū)過(guò)程中的總成本,一般希望可以最小化RN的數(shù)目;平均節(jié)點(diǎn)的度指網(wǎng)絡(luò)的魯棒性,度越高可以更好地平衡負(fù)載,降低出現(xiàn)再次故障的概率;平均路徑長(zhǎng)度(Average Path Length,APL)指代修復(fù)后分區(qū)之間的路徑長(zhǎng)度,較小的APL值可以有效地降低數(shù)據(jù)延遲,適用于對(duì)實(shí)時(shí)性要求較高的網(wǎng)絡(luò)。

圖5以RN的通信半徑為橫坐標(biāo),對(duì)不同的算法針對(duì)以上3個(gè)性能進(jìn)行了比較,由于不同算法性能修復(fù)目標(biāo)的側(cè)重點(diǎn)不同,因此每種性能參數(shù)只對(duì)部分算法進(jìn)行對(duì)比。蜘蛛網(wǎng)算法雖然所需RN的數(shù)目較多,但是修復(fù)后網(wǎng)絡(luò)節(jié)點(diǎn)平均度較高,適用于對(duì)網(wǎng)絡(luò)穩(wěn)定性要求較高的場(chǎng)景;RFPF算法和ORC算法平均路徑長(zhǎng)度較短,適用于對(duì)實(shí)時(shí)性要求較高的網(wǎng)絡(luò);CORP算法和DORMS算法為分布式算法,較好地達(dá)到了RN數(shù)目和平均節(jié)點(diǎn)的度2個(gè)性能之間的平衡。此外,固定和移動(dòng)節(jié)點(diǎn)混合部署算法中假設(shè)RN數(shù)目固定,博弈論算法適用于傳感器節(jié)點(diǎn)數(shù)目較少的小規(guī)模網(wǎng)絡(luò)。

圖5 不同通信半徑下的算法性能對(duì)比

4 算法的不足及展望

網(wǎng)絡(luò)拓?fù)湫迯?fù)算法的不足及需要改進(jìn)的地方有如下6個(gè)方面:

1)多數(shù)算法只是在一定的條件限制下對(duì)某些性能進(jìn)行改善,未來(lái)的研究中應(yīng)該盡可能減少限制條件,提出更具有一般性、可擴(kuò)展性的算法。

2)幾乎沒(méi)有算法可以滿足所有的性能參數(shù)要求,多數(shù)算法只能針對(duì)單個(gè)或幾個(gè)性能表現(xiàn)較好。例如在小規(guī)模故障中大部分算法并未將網(wǎng)絡(luò)覆蓋率考慮在內(nèi),因此,如何達(dá)到能量消耗和網(wǎng)絡(luò)覆蓋率之間的平衡,是未來(lái)的研究方向之一。

3)對(duì)于實(shí)時(shí)性要求較高的網(wǎng)絡(luò),如軍事、自然災(zāi)害等,要求反應(yīng)時(shí)間快,需要降低網(wǎng)絡(luò)修復(fù)的時(shí)間,減少延遲,如何能夠高效快速地完成修復(fù)也是未來(lái)的研究重點(diǎn)之一。

4)在大規(guī)模算法中,修復(fù)之后得到的拓?fù)淙匀淮嬖谠S多割點(diǎn),使得網(wǎng)絡(luò)容易再次出現(xiàn)故障,因此,需要研究提高修復(fù)后網(wǎng)絡(luò)的魯棒性,達(dá)到節(jié)點(diǎn)數(shù)目和節(jié)點(diǎn)平均度之間的平衡,有效地延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。

5)在提高節(jié)點(diǎn)平均度的同時(shí),應(yīng)避免節(jié)點(diǎn)度的兩極分化,使各個(gè)節(jié)點(diǎn)之間的度達(dá)到平均,避免因?yàn)槟芰肯牟痪馐咕W(wǎng)絡(luò)出現(xiàn)故障。

6)無(wú)線傳感器網(wǎng)絡(luò)在三維環(huán)境下的應(yīng)用越來(lái)越廣泛,而目前對(duì)網(wǎng)絡(luò)修復(fù)的研究大多只適用于二維場(chǎng)景,需要對(duì)此進(jìn)行拓展。

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

無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)由于環(huán)境以及能量耗盡等問(wèn)題容易出現(xiàn)故障,因此,需要通過(guò)網(wǎng)絡(luò)修復(fù)技術(shù)排除故障。本文針對(duì)單個(gè)節(jié)點(diǎn)故障和多個(gè)節(jié)點(diǎn)故障的情況對(duì)已有算法進(jìn)行了歸納總結(jié)。分析結(jié)果表明,對(duì)于無(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)修復(fù)方法仍然存在許多有待改進(jìn)的地方。下一步需要根據(jù)三維網(wǎng)絡(luò)的特性研究有針對(duì)性的修復(fù)算法。