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

張 姿，黃廷磊* ，吳拱星

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

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

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

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

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

(2)識別算法的“cut”節(jié)點對

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

(3)確定環(huán)

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

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

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

2 AIBNDA算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真

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

(1)節(jié)點度對算法檢測準(zhǔn)確率的影響

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

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

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

(2)洞的個數(shù)對通信量的影響

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

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

4 結(jié)束語

BRSN-TM算法以任意的節(jié)點為根節(jié)點，構(gòu)造整個網(wǎng)絡(luò)的節(jié)點拓?fù)渥疃搪窂綐洌冒鼑W(wǎng)絡(luò)中所有洞的環(huán)識別網(wǎng)絡(luò)的邊界節(jié)點。該算法雖然嚴(yán)謹(jǐn)?shù)菆?zhí)行了多次的網(wǎng)絡(luò)洪泛以及整個網(wǎng)絡(luò)節(jié)點的同步，所以造成網(wǎng)絡(luò)節(jié)點通信量大。ABRSN-TM算法對BRSN-TM進(jìn)行改進(jìn)，但文中領(lǐng)導(dǎo)節(jié)點的選取方法描述不準(zhǔn)確，劃分網(wǎng)絡(luò)的緯度線的依據(jù)不合理，未描述如何將包圍空洞的環(huán)轉(zhuǎn)化為網(wǎng)絡(luò)的內(nèi)邊界以及外邊界。本文針對BRSN-TM算法構(gòu)造最短路徑樹的通信量大，ABRSN-TM算法的不足之處，從降低通信量及提高邊界節(jié)點檢測的準(zhǔn)確性兩個方面來考慮。在AIBNDA算法中，采用競爭方法選取領(lǐng)導(dǎo)節(jié)點，利用空洞的大小計算緯度線的條數(shù)，構(gòu)造多個環(huán)分別包圍網(wǎng)絡(luò)中的單洞，同時引入環(huán)上節(jié)點動態(tài)替換方法，把環(huán)轉(zhuǎn)換為網(wǎng)絡(luò)的邊界。實驗驗證，AIBNDA算法在網(wǎng)絡(luò)的低節(jié)點度的情況下，能獲得比較高的檢測準(zhǔn)確率;并且在網(wǎng)絡(luò)中洞的個數(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ǎng)絡(luò)中d-Hop 2-連通容錯支配集的分布式構(gòu)造算法”[J]．傳感技術(shù)學(xué)報，2012，25(5):696－701．

[4]王新民，肖亞輝，顧曉婕．“基于混合優(yōu)化的移動傳感器網(wǎng)絡(luò)反隱身研究”[J]．傳感技術(shù)學(xué)報，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ǎng)絡(luò)邊界節(jié)點檢測[J]．桂林電子科技大學(xué)學(xué)報，2012，32(5):373－377．

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