一種改進(jìn)的邊界節(jié)點(diǎn)檢測(cè)算法*

張 姿，黃廷磊* ，吳拱星

(1．中國(guó)科學(xué)院電子學(xué)研究所，北京100190;2．桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西桂林541004)

傳感器網(wǎng)絡(luò)是由大量節(jié)點(diǎn)組成的一種特殊的自組織網(wǎng)絡(luò)，已經(jīng)在軍事監(jiān)視、工業(yè)檢測(cè)和醫(yī)療健康檢測(cè)等領(lǐng)域得到了廣泛的應(yīng)用。近幾年來(lái)，出現(xiàn)了作為自治設(shè)備的新型傳感器節(jié)點(diǎn)，它集感知、處理、通信能力于一體，形成多跳傳感器網(wǎng)絡(luò)。實(shí)際應(yīng)用中，大量傳感器部署后，經(jīng)常處于無(wú)人值守的狀態(tài)[1－4]。因此，電池的損耗、動(dòng)物的損壞、偶然事件的發(fā)生造成部分節(jié)點(diǎn)失效，便形成了空洞，影響網(wǎng)絡(luò)的連通性。為了盡量減少空洞對(duì)網(wǎng)絡(luò)連通的影響，準(zhǔn)確識(shí)別空洞的邊界，有助于保持?jǐn)?shù)據(jù)業(yè)務(wù)流、防止數(shù)據(jù)損失，避免額外的能量消耗，防止空洞的擴(kuò)展，并確定替代的通信路徑。因此邊界檢測(cè)算法的研究具有非常重要的意義。

到目前為止，在無(wú)線傳感器網(wǎng)絡(luò)邊界節(jié)點(diǎn)檢測(cè)算法研究方面，許多學(xué)者已經(jīng)進(jìn)行了大量的研究工作，并且提出了許多有效的算法。根據(jù)算法使用的核心技術(shù)，可將目前的邊界識(shí)別算法分為基于地理位置信息的算法、基于統(tǒng)計(jì)信息的算法和基于拓?fù)湫畔⒌乃惴╗5－7]。本文主要研究基于拓?fù)湫畔⒌倪吔绻?jié)點(diǎn)檢測(cè)算法。

基于拓?fù)湫畔⒌倪吔绻?jié)點(diǎn)檢測(cè)算法利用網(wǎng)絡(luò)的拓?fù)溥B接信息尋找隱藏的網(wǎng)絡(luò)幾何信息，從而確定網(wǎng)絡(luò)節(jié)點(diǎn)的的分布。Ghrist等在文獻(xiàn)[8]提出了一種基于拓?fù)湫畔⒌倪吔缱R(shí)別算法，算法利用節(jié)點(diǎn)同源且方向不可延續(xù)檢測(cè)網(wǎng)絡(luò)的洞。該種算法是比較有代表性的一種識(shí)別方法。但是該算法是集中式算法，不大符合傳感器網(wǎng)絡(luò)的應(yīng)用發(fā)展。Olga Saukh等在文獻(xiàn)[9]提出一種新的基于拓?fù)湫畔⒌乃惴āＷ髡咛峁┑乃惴](méi)有過(guò)多的條件限制，具有比較普遍的應(yīng)用價(jià)值。該算法通過(guò)尋找被取名為“flower”及“flower”的組合結(jié)構(gòu)來(lái)檢測(cè)網(wǎng)絡(luò)的邊界節(jié)點(diǎn)。算法的執(zhí)行嚴(yán)格的依賴于“flower”結(jié)構(gòu)。但是在某些特定應(yīng)用場(chǎng)合，“flower”不總是存在的。針對(duì)實(shí)際應(yīng)用，作者Funke等在文獻(xiàn)[10]提出了一個(gè)非常有代表性算法，后續(xù)很多基于拓?fù)湫畔⒌倪吔绻?jié)點(diǎn)檢測(cè)算法都受該算法啟發(fā)。該算法對(duì)節(jié)點(diǎn)度的要求比較高;為了獲得比較好的檢測(cè)效果，網(wǎng)絡(luò)的平均節(jié)點(diǎn)度要求至少是15。Wang Yue等人在文獻(xiàn)[11]提出了一種比較準(zhǔn)確的檢測(cè)算法，并且作者在論文中給出了算法可行性的理論證明。本文把文獻(xiàn)[11]提出的算法簡(jiǎn)寫(xiě)為BRSN-TM算法。該算法雖然嚴(yán)謹(jǐn)?shù)菆?zhí)行了多次的網(wǎng)絡(luò)洪泛以及整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的同步，所以造成網(wǎng)絡(luò)節(jié)點(diǎn)通信量大。文獻(xiàn)[12]對(duì)BRSN-TM算法進(jìn)行了改進(jìn)，設(shè)計(jì)了一種以網(wǎng)絡(luò)緯度線檢測(cè)網(wǎng)絡(luò)邊界的規(guī)?？蓴U(kuò)展算法ABRSN-TM，但文中領(lǐng)導(dǎo)節(jié)點(diǎn)的選取方法過(guò)于簡(jiǎn)單，劃分網(wǎng)絡(luò)的緯度線的依據(jù)不合理，未描述如何將包圍空洞的環(huán)轉(zhuǎn)化為網(wǎng)絡(luò)的內(nèi)邊界以及外邊界。本文在文獻(xiàn)[11－12]的基礎(chǔ)進(jìn)行改進(jìn)，得到改進(jìn)算法AIBNDA。

1 BRSN-TM算法

(1)構(gòu)建最短路徑樹(shù)

在網(wǎng)絡(luò)中選擇一個(gè)節(jié)點(diǎn)作為最短路徑樹(shù)的根節(jié)點(diǎn)，命名為R節(jié)點(diǎn)。然后利用貪婪算法在網(wǎng)絡(luò)中構(gòu)建以R為根節(jié)點(diǎn)的最短路徑樹(shù)[11]。

(2)識(shí)別算法的“cut”節(jié)點(diǎn)對(duì)

網(wǎng)絡(luò)中洞的分布信息隱藏在最短路徑樹(shù)的結(jié)構(gòu)上。這個(gè)結(jié)構(gòu)具體的說(shuō)就是最短路徑樹(shù)上的“cut”節(jié)點(diǎn)對(duì)?！癱ut”的節(jié)點(diǎn)對(duì)是一對(duì)鄰居節(jié)點(diǎn)，這對(duì)鄰居節(jié)點(diǎn)的在最短路徑樹(shù)上的共同祖先節(jié)點(diǎn)明顯比其他鄰居點(diǎn)的共同祖先節(jié)點(diǎn)遠(yuǎn)。

(3)確定環(huán)

確定一個(gè)環(huán)，這個(gè)環(huán)包圍網(wǎng)絡(luò)中的洞。網(wǎng)絡(luò)的一個(gè)包圍洞的環(huán)是由“cut”的兩個(gè)節(jié)點(diǎn)到達(dá)共同祖先的兩條最短路徑，加上“cut”兩節(jié)點(diǎn)的連線組成。算法確定的這個(gè)環(huán)可以當(dāng)成網(wǎng)絡(luò)的內(nèi)邊界，只是這個(gè)內(nèi)邊界比較粗糙。但是已經(jīng)基本具備內(nèi)邊界的特性。

(4)確定網(wǎng)絡(luò)外邊界和網(wǎng)絡(luò)內(nèi)邊界

確定的環(huán)不會(huì)緊貼網(wǎng)絡(luò)的內(nèi)邊界。作者通過(guò)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)泛洪，重新求精網(wǎng)絡(luò)的內(nèi)外邊界，從而達(dá)到準(zhǔn)確識(shí)別網(wǎng)絡(luò)的內(nèi)外邊界的目的。

2 AIBNDA算法

(1)選取領(lǐng)導(dǎo)節(jié)點(diǎn)

在AIBNDA中，領(lǐng)導(dǎo)節(jié)點(diǎn)是邊界節(jié)點(diǎn)檢測(cè)算法的發(fā)起節(jié)點(diǎn)并且領(lǐng)導(dǎo)網(wǎng)絡(luò)中所有節(jié)點(diǎn)同步。ABRSN-TM中，領(lǐng)導(dǎo)節(jié)點(diǎn)的選取方法是以ID號(hào)最大節(jié)點(diǎn)作為領(lǐng)導(dǎo)節(jié)點(diǎn)，該方法實(shí)現(xiàn)簡(jiǎn)單。但是該方法的弊端是如果網(wǎng)絡(luò)被某些不可預(yù)測(cè)的因素切斷為連續(xù)性不明確的兩個(gè)區(qū)域時(shí)，這樣，選取的領(lǐng)導(dǎo)節(jié)點(diǎn)將無(wú)法啟動(dòng)兩個(gè)區(qū)域的邊界節(jié)點(diǎn)檢測(cè)。為了避免這種選取方法的不足之處，因此AIBNDA采用競(jìng)爭(zhēng)方法選取領(lǐng)導(dǎo)節(jié)點(diǎn)[13]。

(2)確定網(wǎng)絡(luò)的信標(biāo)節(jié)點(diǎn)

AIBNDA在網(wǎng)絡(luò)中尋找兩個(gè)信標(biāo)節(jié)點(diǎn)，確定兩個(gè)信標(biāo)節(jié)點(diǎn)應(yīng)具有兩個(gè)特征:第一，兩節(jié)點(diǎn)要起到信標(biāo)節(jié)點(diǎn)的作用。第二，兩節(jié)點(diǎn)應(yīng)該位于網(wǎng)絡(luò)中的某一方向相反的兩端。所以充當(dāng)信標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)應(yīng)該盡量跨越網(wǎng)絡(luò)中的大部分特性區(qū)域。這里的特性主要指網(wǎng)絡(luò)中洞的分布。通過(guò)領(lǐng)導(dǎo)節(jié)點(diǎn)L來(lái)尋找具有以上特性的兩個(gè)信標(biāo)節(jié)點(diǎn)。首先以領(lǐng)導(dǎo)節(jié)點(diǎn)L為信標(biāo)節(jié)點(diǎn)，在網(wǎng)絡(luò)中利用貪婪算法確定網(wǎng)絡(luò)中每一節(jié)點(diǎn)到達(dá)L節(jié)點(diǎn)的最短跳數(shù)。然后選取到達(dá)L節(jié)點(diǎn)跳數(shù)最大的節(jié)點(diǎn)為信標(biāo)節(jié)點(diǎn)，標(biāo)號(hào)為N．同樣的以節(jié)點(diǎn)N為信標(biāo)節(jié)點(diǎn)，尋找到達(dá)節(jié)點(diǎn)N最遠(yuǎn)的節(jié)點(diǎn)，標(biāo)號(hào)為S。從上面的方法可知，節(jié)點(diǎn)N和節(jié)點(diǎn)S滿足信標(biāo)節(jié)點(diǎn)的兩個(gè)要求。

(3)劃分網(wǎng)絡(luò)的緯度線

在完成網(wǎng)絡(luò)的信標(biāo)節(jié)點(diǎn)選取后，網(wǎng)絡(luò)中所有的節(jié)點(diǎn)同時(shí)已獲取了自身節(jié)點(diǎn)到兩個(gè)信標(biāo)節(jié)點(diǎn)的跳數(shù)坐標(biāo)。在網(wǎng)絡(luò)中劃分一些等距線，類(lèi)似于地球上的緯度線，因此本文把這些等距線稱為緯度線。緯度線為到達(dá)兩信標(biāo)節(jié)點(diǎn)的距離比值恒定的節(jié)點(diǎn)的集合。連續(xù)的緯度線定義為緯度線段，每段緯度線段上選取一個(gè)頭節(jié)點(diǎn)，每個(gè)頭節(jié)點(diǎn)代表緯度線段向領(lǐng)導(dǎo)節(jié)點(diǎn)發(fā)送一條注冊(cè)消息。網(wǎng)絡(luò)緯度線條數(shù)設(shè)定與緯度線間的間隔有關(guān)。ABRSN-TM是通過(guò)經(jīng)驗(yàn)值，根據(jù)網(wǎng)絡(luò)的規(guī)模，設(shè)定緯度線間的寬度。這種算法不夠嚴(yán)謹(jǐn)，如果緯度線間的寬度比較大，有可能使網(wǎng)絡(luò)中比較小的洞未能被檢測(cè)出來(lái)(圖1(a))所示。但是如果網(wǎng)絡(luò)中緯度線間的寬度劃分太小，使網(wǎng)絡(luò)的緯度線比較密集，那么將增加網(wǎng)絡(luò)的通信壓力。如果希望比較準(zhǔn)確的設(shè)置網(wǎng)絡(luò)中緯度線的條數(shù)，可以先對(duì)洞的大小進(jìn)行定義。然后利用洞的大小計(jì)算緯度線的條數(shù)，從而確定節(jié)點(diǎn)到達(dá)兩信標(biāo)節(jié)點(diǎn)的預(yù)設(shè)距離比值((圖1(b))所示。網(wǎng)絡(luò)中的緯度線的數(shù)量可用式(1)計(jì)算:

TH為緯度線加密系數(shù)，可取0、1、2等值，用于適當(dāng)增加網(wǎng)絡(luò)中的緯度線條數(shù)。Dh表示洞的直徑定義為網(wǎng)絡(luò)中洞的邊界節(jié)點(diǎn)中相隔距離最大的兩個(gè)節(jié)點(diǎn)之間的跳數(shù)。Dn表示網(wǎng)絡(luò)中任意節(jié)點(diǎn)間距離最遠(yuǎn)的兩節(jié)點(diǎn)的跳數(shù)距離定義為網(wǎng)絡(luò)的規(guī)模。

圖1 網(wǎng)絡(luò)中緯度線的劃分

(4)確定網(wǎng)絡(luò)中洞的分布情況

AIBNDA的核心思想是通過(guò)網(wǎng)絡(luò)中洞的分布情況來(lái)尋找網(wǎng)絡(luò)中包圍洞的環(huán)。如果網(wǎng)絡(luò)中存在洞，那么緯度線將被洞分割成多段;如果緯度線所跨越的地理區(qū)域不存在洞，那么緯度線將是連續(xù)的。把連續(xù)的整段緯度線，稱為緯度線段。每段緯度線段上選取一個(gè)頭節(jié)點(diǎn)，每個(gè)頭節(jié)點(diǎn)代表緯度線段向領(lǐng)導(dǎo)節(jié)點(diǎn)發(fā)送一條注冊(cè)消息。

節(jié)點(diǎn)ID值最小的節(jié)點(diǎn)被選為頭節(jié)點(diǎn)，每個(gè)頭結(jié)點(diǎn)發(fā)出包含自身ID及緯度線號(hào)的注冊(cè)信息給領(lǐng)導(dǎo)節(jié)點(diǎn)。領(lǐng)導(dǎo)節(jié)點(diǎn)接收每個(gè)頭節(jié)點(diǎn)的注冊(cè)信息，并且對(duì)信息中的緯度線號(hào)進(jìn)行計(jì)數(shù)。如果出現(xiàn)重復(fù)的緯度線標(biāo)示符，那么說(shuō)明該緯度線被網(wǎng)絡(luò)中的洞切斷。

(5)構(gòu)造包圍洞的環(huán)

根據(jù)Jordan曲線理論，二維平面內(nèi)一條封閉的曲線把平面分成兩部分:曲線內(nèi)部和曲線外部。確定了網(wǎng)絡(luò)中空洞的大概位置，就構(gòu)造一個(gè)包圍網(wǎng)絡(luò)中空洞的環(huán)。這里所提及的環(huán)就是網(wǎng)絡(luò)中由節(jié)點(diǎn)的連接組成的一條封閉的二維曲線。AIBNDA將構(gòu)造的環(huán)把網(wǎng)絡(luò)分成兩部分:環(huán)內(nèi)部為包圍特定洞的部分;環(huán)外為不包含洞的部分。圖2所示，網(wǎng)絡(luò)中的空洞在緯度線3和緯度線7之間，同時(shí)也在緯度線4、5、6的兩個(gè)頭節(jié)點(diǎn)對(duì)之間。網(wǎng)絡(luò)中的八個(gè)頭節(jié)點(diǎn)，利用最短路徑算法找到各自臨近的頭節(jié)點(diǎn)，將它們連接就形成了一個(gè)包圍洞的環(huán)，命名為S。組成S的節(jié)點(diǎn)集合為{s1，s2，s3，……sn}。

圖2 網(wǎng)絡(luò)包含洞的環(huán)

(6)識(shí)別網(wǎng)絡(luò)內(nèi)外邊界

組成 S的節(jié)點(diǎn)集合{s1，s2，s3，……sn}。它們的一跳鄰居節(jié)點(diǎn)集合分別是，Hops1(1)，Hops2(1)，Hops3(1)，Hops4(1)，Hops5(1)，…，Hopsn(1)。

隨意選取S上的一個(gè)節(jié)點(diǎn)，假設(shè)s1，轉(zhuǎn)發(fā)，Hops1(1)給它的所有1跳鄰接節(jié)點(diǎn)。每個(gè)鄰接節(jié)點(diǎn)找到自己1跳的鄰接節(jié)點(diǎn)中，同時(shí)也是s1的1跳鄰接節(jié)點(diǎn)的集合?？偨Y(jié)如下:

在式(2)中的LinkedToHops1(1)(a)是指在節(jié)點(diǎn)s1的1跳鄰接表中同時(shí)也是節(jié)點(diǎn)a的1跳鄰接節(jié)點(diǎn)的集合。為了演示這個(gè)算法，設(shè)已識(shí)別包圍空洞的環(huán)為S3，圖3所示。本文以s31為例。

圖3 包含空洞的環(huán)轉(zhuǎn)換成網(wǎng)絡(luò)內(nèi)界的過(guò)程

表1顯示了算法的運(yùn)算過(guò)程。因?yàn)?s31、s32、s3j都屬于環(huán)S3的節(jié)點(diǎn)，根據(jù)其鄰居關(guān)系推出s41，s42，s4p是屬于新環(huán)S4，s21，s22是屬于新環(huán)S2。將S環(huán)上的其他節(jié)點(diǎn)依次按照上述步驟，就將形成完整的S4，S2。然后，將形成的 S4，S2，按照上述動(dòng)態(tài)方法，形成新的環(huán)。在新形成的環(huán)，按照迭代方法，直到找到網(wǎng)絡(luò)的內(nèi)外邊界，如圖4所示。

表1 S31的一跳鄰居節(jié)點(diǎn)之間的相互通信的鏈接

圖4 網(wǎng)絡(luò)的內(nèi)外邊界

3 仿真

為了驗(yàn)證AIBNDA的性能，用NS2進(jìn)行了仿真實(shí)驗(yàn)[13]。在軟件的環(huán)境中設(shè)置各種不同的參數(shù)驗(yàn)證算法的可行性。為了評(píng)估AIBNDA算法的優(yōu)化性能，在統(tǒng)一的平臺(tái)上對(duì)算法 AIBNDA、ABRSN-TM、BRSN-TM進(jìn)行一系列的仿真，然后對(duì)比實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)過(guò)程中，網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)區(qū)域、節(jié)點(diǎn)通信范圍、洞的類(lèi)型、洞的數(shù)量等參數(shù)在未加說(shuō)明的情況下采用如下初始值。節(jié)點(diǎn)數(shù):3 500;網(wǎng)絡(luò)區(qū)域形狀:正方形;傳感器區(qū)域規(guī)模:1 000 m×1 000 m;通信范圍:30 m;平均節(jié)點(diǎn)度:9;洞的形狀:類(lèi)圓。

(1)節(jié)點(diǎn)度對(duì)算法檢測(cè)準(zhǔn)確率的影響

在這組實(shí)驗(yàn)中，通過(guò)調(diào)整網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目，使節(jié)點(diǎn)的平均度在6、9、12、15變化。在不同節(jié)點(diǎn)度的環(huán)境下執(zhí)行AIBNDA、ABRSN-TM、BRSN-TM算法各50次，分別記錄邊界節(jié)點(diǎn)識(shí)別的準(zhǔn)確率，取平均值。

如圖5，節(jié)點(diǎn)度為6時(shí)，算法AIBNDA、ABRSNTM、BRSN-TM邊界節(jié)點(diǎn)的檢測(cè)準(zhǔn)確率都比較低。特別在BRSN-TM算法中，由于網(wǎng)絡(luò)稀疏，從而致使稀疏區(qū)域的一些非邊界的節(jié)點(diǎn)被誤選為邊界節(jié)點(diǎn)。算法ABRSN-TM中，由于缺少將包圍空洞的環(huán)轉(zhuǎn)化為網(wǎng)絡(luò)的內(nèi)邊界以及外邊界這一步驟，因此，邊界節(jié)點(diǎn)的識(shí)別準(zhǔn)確率不及ABRSN-TM。實(shí)驗(yàn)結(jié)果顯示了隨著節(jié)點(diǎn)度提高，邊界節(jié)點(diǎn)檢測(cè)算法的識(shí)別準(zhǔn)確率不斷的提高。從仿真結(jié)果可知，不管節(jié)點(diǎn)度高或者低，在識(shí)別準(zhǔn)確率方面，AIBNDA分別比 ABRSNTM、BRSN-TM提高程度平均有2%和7%以上。因此在網(wǎng)絡(luò)低節(jié)點(diǎn)度的情況下，AIBNDA擁有比ABRSN-TM、BRSN-TM更高的識(shí)別準(zhǔn)確率。

圖5 不同節(jié)點(diǎn)度識(shí)別準(zhǔn)確率

(2)洞的個(gè)數(shù)對(duì)通信量的影響

在這組實(shí)驗(yàn)中，網(wǎng)絡(luò)中空洞的個(gè)數(shù)由1個(gè)變化到8個(gè)，AIBNDA、ABRSN-TM、BRSN-TM 算法各執(zhí)行50次，分別記錄算法的識(shí)別邊界節(jié)點(diǎn)的通信量，計(jì)算平均值。圖6所示，空洞的個(gè)數(shù)比較少時(shí)，BRSN-TM算法的通信量是比較少的。但是當(dāng)網(wǎng)絡(luò)的洞的個(gè)數(shù)大于3時(shí)，BRSN-TM的通信量超過(guò)了ABRSN-TM算法的通信量。當(dāng)網(wǎng)絡(luò)的洞的個(gè)數(shù)大于4時(shí)，AIBNDA算法的通信量低于ABRSN-TM算法的通信量。AIBNDA的通信量平均比ABRSN-TM、BRSN-TM低。所以，當(dāng)網(wǎng)絡(luò)的空洞大于4時(shí)，AIBNDA降低檢測(cè)邊界節(jié)點(diǎn)的通信量。

圖6 算法交換的數(shù)據(jù)量

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

BRSN-TM算法以任意的節(jié)點(diǎn)為根節(jié)點(diǎn)，構(gòu)造整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)拓?fù)渥疃搪窂綐?shù)，利用包圍網(wǎng)絡(luò)中所有洞的環(huán)識(shí)別網(wǎng)絡(luò)的邊界節(jié)點(diǎn)。該算法雖然嚴(yán)謹(jǐn)?shù)菆?zhí)行了多次的網(wǎng)絡(luò)洪泛以及整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的同步，所以造成網(wǎng)絡(luò)節(jié)點(diǎn)通信量大。ABRSN-TM算法對(duì)BRSN-TM進(jìn)行改進(jìn)，但文中領(lǐng)導(dǎo)節(jié)點(diǎn)的選取方法描述不準(zhǔn)確，劃分網(wǎng)絡(luò)的緯度線的依據(jù)不合理，未描述如何將包圍空洞的環(huán)轉(zhuǎn)化為網(wǎng)絡(luò)的內(nèi)邊界以及外邊界。本文針對(duì)BRSN-TM算法構(gòu)造最短路徑樹(shù)的通信量大，ABRSN-TM算法的不足之處，從降低通信量及提高邊界節(jié)點(diǎn)檢測(cè)的準(zhǔn)確性兩個(gè)方面來(lái)考慮。在AIBNDA算法中，采用競(jìng)爭(zhēng)方法選取領(lǐng)導(dǎo)節(jié)點(diǎn)，利用空洞的大小計(jì)算緯度線的條數(shù)，構(gòu)造多個(gè)環(huán)分別包圍網(wǎng)絡(luò)中的單洞，同時(shí)引入環(huán)上節(jié)點(diǎn)動(dòng)態(tài)替換方法，把環(huán)轉(zhuǎn)換為網(wǎng)絡(luò)的邊界。實(shí)驗(yàn)驗(yàn)證，AIBNDA算法在網(wǎng)絡(luò)的低節(jié)點(diǎn)度的情況下，能獲得比較高的檢測(cè)準(zhǔn)確率;并且在網(wǎng)絡(luò)中洞的個(gè)數(shù)比較多的情況下，算法的通信量能得到降低。

[1]Khan I M，Jabeur N，Zeadally S．Hop-based Approach for Holes and Boundary Detection in Wireless Sensor Networks[J]．IET Wirel．Sens．Syst．，2012，2(4):328－337．

[2]Simek M．Bocek J Moravek．Optimization of Boundary Recognition Algorithms for Wireless Sensor Network Applications[C]//Telecommunications and Signal Processing(TSP)，2011 34th International Conference on Digital Object Identifier，2011:189－194．

[3]鄭嬋，尹令，孫世新．“無(wú)線傳感器網(wǎng)絡(luò)中d-Hop 2-連通容錯(cuò)支配集的分布式構(gòu)造算法”[J]．傳感技術(shù)學(xué)報(bào)，2012，25(5):696－701．

[4]王新民，肖亞輝，顧曉婕．“基于混合優(yōu)化的移動(dòng)傳感器網(wǎng)絡(luò)反隱身研究”[J]．傳感技術(shù)學(xué)報(bào)，2012，25(1):94－98．

[5]Simek M Bocek，Moravek J．Optimization of Boundary Recognition Algorithms for Wireless Sensor Network Applications[C]//Telecommunications and Signal Processing(TSP)，2011 34th International Conference on Digital Object Identifier，2011:189－194．

[6]Khan I M，Khan M Z，Mokhtar H Merabti．Enhancements of the Self-Detection Scheme for Boundary Recognition in Wireless Sensor Networks”[J]．Developments in E-systems Engineering(DeSE)，2011:448－453．

[7]Khan I Mokhtar，Merabti H．A New Self-detection Scheme for Sensor Network Boundary Recognition[C]//Local Computer Networks，2009．LCN 2009．IEEE 34th Conference on Year，2009:241－244．

[8]Ghrist R，Muhammad A．Coverage and Hole-detection in Sensor Networks Via Homology[C]//Proc．4th Internat．Sympos．Information Processing in Sensor Networks，2005:254－260．

[9]Olga Saukh，Robert Sauter，Matthias Gauger，et al．On Boundary Recognition without Location Information in Wireless Sensor Networks[C]//ACM Transactions on Sensor Networks，Article 20，Publication date:June，2010，6(3):20－35．

[10]Funke S，Klein C．Hole Detection or:How Much Geometry Hides in Connectivity?[C]//Proc．22nd ACM Sympos．Computational Geometry，2006:377－385．

[11]Wang Y，Gao J，Joseph Mitchell S B．Boundary Recognition in Sensor Networks by Topological Methods[C]//12th Annual Nternational Conference on Mobile Computing and Networking(MobiCom’06)，Los angeles，USA，September，2006:122－133．

[12]吳拱星，黃廷磊．基于拓?fù)涞臒o(wú)線傳感器網(wǎng)絡(luò)邊界節(jié)點(diǎn)檢測(cè)[J]．桂林電子科技大學(xué)學(xué)報(bào)，2012，32(5):373－377．

[13]黃化吉，馮穗力等．NS網(wǎng)絡(luò)模擬和協(xié)議仿真[M]．北京:人民郵電出版社，2010．