無線傳感器網(wǎng)絡(luò)拓?fù)湫迯?fù)算法綜述

曉璇, ,,

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

0 概述

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)[1]是由大量密集部署在目標(biāo)區(qū)域的節(jié)點構(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)用,近年來,其在環(huán)境監(jiān)測、醫(yī)療護(hù)理、火災(zāi)監(jiān)測、交通監(jiān)控等領(lǐng)域也得到廣泛的應(yīng)用[4]。

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

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

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

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

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

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

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

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

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

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

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

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

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

1)主動修復(fù)

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

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

2)被動修復(fù)

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

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

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

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

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

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

2.2.3 根據(jù)重定位節(jié)點移動方式的分類

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

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

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

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

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

2.3 算法分類與歸納比較

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

表1 單個節(jié)點失效算法的性能比較

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

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

3.1 集中式算法

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

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

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

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

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

3.1.2 CIST算法

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

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

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

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

3.2 分布式算法

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

3.2.1 CORP算法

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

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

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

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

3.2.2 DORMS算法

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

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

2)重定位RN的位置:該部分通過重定位RN的位置來減少RN。

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

3.2.3 博弈論和RPFP算法

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

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

3.3 算法性能比較

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

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

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

4 算法的不足及展望

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

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

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

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

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

5)在提高節(jié)點平均度的同時,應(yīng)避免節(jié)點度的兩極分化,使各個節(jié)點之間的度達(dá)到平均,避免因為能量消耗不均衡使網(wǎng)絡(luò)出現(xiàn)故障。

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

5 結(jié)束語

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