無線傳感器與執(zhí)行器網(wǎng)絡(luò)基于鄰居信息的割點(diǎn)檢測算法*

李修琪，楊 杰，馮 勇，王 翊

（昆明理工大學(xué)云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，昆明650500）

無線傳感器與執(zhí)行器網(wǎng)絡(luò)WSANs（Wireless Sensor and Actuator Networks）是在無線傳感器網(wǎng)絡(luò)WSNs的基礎(chǔ)上發(fā)展起來的一種新型的無線自組織網(wǎng)絡(luò)［1-2］。WSANs擁有一定數(shù)量的可自主移動的執(zhí)行器，具有可作用于環(huán)境、能夠?qū)崟r響應(yīng)環(huán)境變化等傳統(tǒng)無線傳感器網(wǎng)絡(luò)并不具備的優(yōu)點(diǎn)。

WSANs中普通傳感器節(jié)點(diǎn)能量、計(jì)算、存儲和通信能力都有限且節(jié)點(diǎn)不可移動，而執(zhí)行器節(jié)點(diǎn)則是可移動的，具有更多的能量，更強(qiáng)的計(jì)算、存儲和通信能力［3］。WSANs中可以通過執(zhí)行器節(jié)點(diǎn)的移動來實(shí)現(xiàn)網(wǎng)絡(luò)的最佳性能［4］，也可以在傳感器節(jié)點(diǎn)出現(xiàn)問題的時候?qū)?zhí)行器節(jié)點(diǎn)移動到問題節(jié)點(diǎn)處進(jìn)行拓?fù)湫迯?fù)，以提高網(wǎng)絡(luò)的魯棒性、保證網(wǎng)絡(luò)的性能。

割點(diǎn)（cut vertex），是無線傳感器與執(zhí)行器網(wǎng)絡(luò)中一旦失效就會引起網(wǎng)絡(luò)分割的關(guān)鍵節(jié)點(diǎn)，是因?yàn)榫W(wǎng)絡(luò)中節(jié)點(diǎn)隨機(jī)分布可能產(chǎn)生的瓶頸節(jié)點(diǎn)［5］。割點(diǎn)的失效可能會引起無線傳感器網(wǎng)絡(luò)區(qū)域性的通信中斷，影響網(wǎng)絡(luò)的信息收集和傳送功能。而且由于無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)能量有限，一旦割點(diǎn)失效還將影響到傳感器的能量優(yōu)化從而增加整個網(wǎng)絡(luò)的能量消耗，縮短WSANs的生命周期［6］。因此，在WSANs中，準(zhǔn)確的割點(diǎn)檢測機(jī)制是實(shí)現(xiàn)拓?fù)湫迯?fù)以增強(qiáng)網(wǎng)絡(luò)魯棒性的重要基礎(chǔ)。

本文提出了一種基于鄰居信息進(jìn)行割點(diǎn)檢測的分布式算法，該算法中每個節(jié)點(diǎn)通過與距離自身至多兩跳鄰居節(jié)點(diǎn)進(jìn)行信息交換建立局部的網(wǎng)絡(luò)拓?fù)湫畔⒉⒎治鯳SANs網(wǎng)絡(luò)拓?fù)渲械沫h(huán)和折線，然后根據(jù)判定規(guī)則判斷節(jié)點(diǎn)是否為割點(diǎn)。試驗(yàn)?zāi)M發(fā)現(xiàn)DCVN能很好的完成割點(diǎn)檢測的任務(wù)，相較之前的幾種割點(diǎn)檢測算法，準(zhǔn)確率有所提高。

1 相關(guān)工作

早在2004年，割點(diǎn)的定義首先被Milenko Jorgic'等人提出［7］，此后的十多年中人們嘗試?yán)脠D論，連通支配集，關(guān)鍵點(diǎn)等各種各樣的工具來尋找割點(diǎn)，但是割點(diǎn)檢測的準(zhǔn)確率和命中率仍有待提高。

Muhammad Imran等人提出的DCR算法［8］中，每個執(zhí)行器節(jié)點(diǎn)通過鄰居節(jié)點(diǎn)的位置信息來判斷自身是否為割點(diǎn)。根據(jù)節(jié)點(diǎn)位置計(jì)算節(jié)點(diǎn)間距離來判斷兩個節(jié)點(diǎn)是否相鄰。最后，如果節(jié)點(diǎn)的所有一跳鄰居節(jié)點(diǎn)都能相互連通，則該節(jié)點(diǎn)為普通節(jié)點(diǎn)，否則就是割點(diǎn)。該方法實(shí)現(xiàn)簡單，但是判斷是割點(diǎn)的條件比較苛刻，會有一部分割點(diǎn)無法檢測出來。割點(diǎn)判別的準(zhǔn)確率高但是漏檢率也較高。

文獻(xiàn)［9］提出了一個構(gòu)造連通支配集來尋找割點(diǎn)的算法。首先介紹了形成連通支配集的算法，然后提出了一個減小支配集的支配集修剪規(guī)則。文獻(xiàn)［10-11］把屬于連通支配集的節(jié)點(diǎn)稱為支配者，把與連通支配集相鄰的節(jié)點(diǎn)稱作被支配者。根據(jù)支配者與被支配者的關(guān)系來判定是不是割點(diǎn)，但是該割點(diǎn)檢測算法的準(zhǔn)確率還有待提高。

文獻(xiàn)［12］提出了一個基于有限拓?fù)湫畔⒌年P(guān)鍵節(jié)點(diǎn)和非關(guān)鍵節(jié)點(diǎn)的分離算法（LASCNN）。每個節(jié)點(diǎn)創(chuàng)建并維護(hù)一個k跳連接列表，列表包含了k跳內(nèi)的所有節(jié)點(diǎn)。每個節(jié)點(diǎn)順次反復(fù)遍歷自己的連接列表，最后創(chuàng)建一個k跳連接的鄰居列表。如果k跳連接鄰居列表包含所有的k跳鄰居節(jié)點(diǎn)，則該節(jié)點(diǎn)是普通節(jié)點(diǎn)，否則為割點(diǎn)。該算法已經(jīng)能夠做到對割點(diǎn)比較準(zhǔn)確的檢測。

DCVN算法采用了根據(jù)鄰居信息進(jìn)行拓?fù)淦ヅ涞母铧c(diǎn)判決思路。首先，我們將無線傳感器與執(zhí)行器網(wǎng)絡(luò)劃分成5種基本的拓?fù)浣Y(jié)構(gòu)并總結(jié)出割點(diǎn)的判定規(guī)則。然后，在權(quán)衡準(zhǔn)確性與算法復(fù)雜度的基礎(chǔ)之上取了至多兩跳的鄰居信息來進(jìn)行割點(diǎn)的檢測。

2 對網(wǎng)絡(luò)拓?fù)涞幕緞澐?/h2>

在WSANs中，相鄰節(jié)點(diǎn)之間通過定期發(fā)送“心跳”消息［13］來交換彼此的狀態(tài)信息（路由信息，能量狀態(tài)，地理位置等）。一旦不能收到某個鄰居節(jié)點(diǎn)的“心跳”消息，我們就認(rèn)為該節(jié)點(diǎn)因?yàn)槟承┰蚴А?jù)此我們可以判斷節(jié)點(diǎn)是否正常工作。

圖1是一個無線傳感器與執(zhí)行器網(wǎng)絡(luò)拓?fù)鋱D，圖中連線表示兩節(jié)點(diǎn)能夠正常交流“心跳”信息，互為鄰居關(guān)系。

圖1 一個WSANs的拓?fù)浣Y(jié)構(gòu)

對圖1的拓?fù)浣Y(jié)構(gòu)進(jìn)一步分析，我們可以得出以下結(jié)論：無論網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量有多少，網(wǎng)絡(luò)拓?fù)溆扇N最基本的元素構(gòu)成，就是環(huán)、折線和孤立節(jié)點(diǎn)。環(huán)是指由兩個以上節(jié)點(diǎn)所組成的起點(diǎn)和終點(diǎn)相同的結(jié)構(gòu)。折線是指兩個及以上節(jié)點(diǎn)組成的線型結(jié)構(gòu)。孤立節(jié)點(diǎn)是指沒有鄰居節(jié)點(diǎn)的單獨(dú)節(jié)點(diǎn)。

我們將環(huán)、折線、孤立節(jié)點(diǎn)這三種元素的所有組合方式概括為5種：環(huán)組合方式，折線組合方式，孤立節(jié)點(diǎn)組合方式，環(huán)與環(huán)相交的組合方式，環(huán)與折線的組合方式，如圖2所示。

圖2 網(wǎng)絡(luò)拓?fù)涞?種基本劃分

根據(jù)割點(diǎn)的定義可知：環(huán)上的節(jié)點(diǎn)都是普通節(jié)點(diǎn)；折線上的節(jié)點(diǎn)除了葉子節(jié)點(diǎn)之外都是割點(diǎn)；葉子節(jié)點(diǎn)和孤立節(jié)點(diǎn)是普通節(jié)點(diǎn)；環(huán)與環(huán)相交處的節(jié)點(diǎn)以及環(huán)與折線相交處的節(jié)點(diǎn)是割點(diǎn)。

3 割點(diǎn)的判定規(guī)則

結(jié)合上述5種組合方式以及文獻(xiàn)［14］和［15］中的割點(diǎn)判別方法，本文總結(jié)出如下割點(diǎn)判定規(guī)則：

①如果Ai是葉子節(jié)點(diǎn)或者孤立節(jié)點(diǎn)，則Ai是普通節(jié)點(diǎn)（如圖2（C）中節(jié)點(diǎn)6，圖1中節(jié)點(diǎn)9）。

②如果Ai與他所有的一跳鄰居節(jié)點(diǎn)能夠形成一個環(huán)，或者Ai的所有一跳鄰居能夠自己組成一個環(huán)，則Ai是普通節(jié)點(diǎn)（如圖2（A）中節(jié)點(diǎn)2，圖1中節(jié)點(diǎn)1）。

③如果Ai與他的部分一跳鄰居節(jié)點(diǎn)能夠形成一個環(huán)，與部分的鄰居節(jié)點(diǎn)連成折線，這些環(huán)和折線包含了所以的一跳鄰居，并且這些折線中至少有一條折線的一跳或二跳鄰居節(jié)點(diǎn)是葉子節(jié)點(diǎn)或割點(diǎn)，則Ai是割點(diǎn)（如圖2（E）中節(jié)點(diǎn)0）。

④如果Ai能夠組成兩個或兩個以上的環(huán)，這些環(huán)包含了所有的一跳鄰居節(jié)點(diǎn)并且環(huán)與環(huán)之間沒有公共節(jié)點(diǎn)，則Ai是割點(diǎn)（如圖2（D）中節(jié)點(diǎn)2）。

⑤如果Ai能夠組成兩個或兩個以上的環(huán)和若干條折線，所有的一跳鄰居節(jié)點(diǎn)不能組成環(huán)，折線中至少有一條折線的一跳或二跳鄰居節(jié)點(diǎn)是葉子節(jié)點(diǎn)或割點(diǎn)，則Ai是割點(diǎn)（如圖1中的節(jié)點(diǎn)22）。

⑥如果Ai與一跳鄰居不能組成環(huán)，但是Ai有若干條折線，并且存在至少一條折線的一跳或二跳鄰居節(jié)點(diǎn)是葉子節(jié)點(diǎn)或割點(diǎn)，則Ai是割點(diǎn)（如圖2（E）中節(jié)點(diǎn)3，圖1中節(jié)點(diǎn)12）。

4 算法的具體實(shí)現(xiàn)

DCVN中節(jié)點(diǎn)分別對收集到的距自身兩跳和四跳之內(nèi)的鄰居列表順次遍歷得出相應(yīng)的環(huán)、折線和孤立節(jié)點(diǎn)進(jìn)而判斷自己是割點(diǎn)還是普通節(jié)點(diǎn)。DCVN算法分為三步：第一步，收集兩跳鄰居列表；第二步，挖掘本地信息做判斷，第三步，詢問鄰居節(jié)點(diǎn)做判斷。

4.1 收集兩跳鄰居列表

用到的節(jié)點(diǎn)命名規(guī)則：

Ai：需要判斷自身是否為割點(diǎn)的節(jié)點(diǎn)。

AiNj_1hop：距Ai一跳的鄰居節(jié)點(diǎn)。

AiNj+1_1hop：距Ai的不同于AiNj_1hop的其他一跳鄰居節(jié)點(diǎn)。

AiNjNk_2hop：距AiNj_1hop一跳的鄰居節(jié)點(diǎn)（即距Ai兩跳的鄰居節(jié)點(diǎn)）。

AiNj+1Nk_2hop：距AiNj+1_1hop一跳的鄰居節(jié)點(diǎn)（即距Ai兩跳的鄰居節(jié)點(diǎn)）。

我們知道，相鄰的節(jié)點(diǎn)可以通過發(fā)送“Hello”消息來收集彼此包括ID在內(nèi)的狀態(tài)信息。DCVN的兩跳鄰居列表收集可以分為兩步：

①節(jié)點(diǎn)Ai發(fā)送“Hello”消息給一跳范圍內(nèi)所有鄰居節(jié)點(diǎn)，收到消息的一跳鄰居節(jié)點(diǎn)AiNj_1hop返回一條ACK消息給節(jié)點(diǎn)Ai。

這一步可以收集節(jié)點(diǎn)Ai的一跳鄰居列表，然后保存到一跳鄰居列表listAi_1hop中。

例如，圖1中節(jié)點(diǎn)A12有三個鄰居節(jié)點(diǎn)：A8、A10、A22，則A12可收集一跳鄰居列表如表1所示。

表1 節(jié)點(diǎn)A12的一跳鄰居列表listA12_1hop

②節(jié)點(diǎn)Ai的一跳鄰居節(jié)點(diǎn)AiNj_1hop也廣播“Hello”消息來收集自身的一跳鄰居列表。然后Ai與AiNj_1hop交換自己的一跳鄰居列表。這樣，Ai能收集到距自身兩跳的鄰居節(jié)點(diǎn)信息，AiNj_1hop能收集到距自身一跳的部分鄰居節(jié)點(diǎn)信息。

經(jīng)過這兩步，節(jié)點(diǎn)Ai就在本地存儲了距自身一跳和兩跳的節(jié)點(diǎn)列表，DCVN就是利用這些信息實(shí)現(xiàn)割點(diǎn)檢測。

表2 節(jié)點(diǎn)A10的兩跳鄰居列表listA10_2hop

下面以圖1中的節(jié)點(diǎn)A10為例來進(jìn)行說明。首先，A10發(fā)送“Hello”消息給一跳鄰居節(jié)點(diǎn)A6、A12、A18，這三個一跳鄰居節(jié)點(diǎn)收到“Hello”消息后返回ACK消息。與此同時，A6、A12、A18等節(jié)點(diǎn)也會發(fā)送它們自己的“Hello”消息來收集它們自己的一跳鄰居列表。接下來第（2）步中，A10與A6、A12、A18交換自身的一跳鄰居列表。經(jīng)過這兩步之后A10就收集到了距自身兩跳的鄰居節(jié)點(diǎn)列表（A10刪除與自身ID相同的兩跳節(jié)點(diǎn)），如表2所示。

節(jié)點(diǎn)Ai收集到自身的兩跳鄰居列表后，通過挖掘這些鄰居列表獲得拓?fù)渲械沫h(huán)與折線，然后依照割點(diǎn)判定規(guī)則判斷自己是割點(diǎn)還是普通節(jié)點(diǎn)。

4.2 挖掘本地信息做判斷

挖掘本地信息是指節(jié)點(diǎn)依次遍歷自身的一跳和兩跳鄰居列表，并尋找列表中具有相同ID的節(jié)點(diǎn)，從而找出拓?fù)浣Y(jié)構(gòu)中由3個或4個節(jié)點(diǎn)組成的環(huán)和由3個節(jié)點(diǎn)組成的折線。具體的步驟如下：

（1）節(jié)點(diǎn)Ai先讀取自己的一跳鄰居節(jié)點(diǎn)列表做判斷。

①如果Ai沒有一跳鄰居節(jié)點(diǎn)，則Ai是孤立節(jié)點(diǎn)，非割點(diǎn)。

②如果Ai有唯一的一跳鄰居節(jié)點(diǎn)，則Ai是葉子節(jié)點(diǎn)，非割點(diǎn)。

③如果Ai有兩個或兩個以上的一跳鄰居節(jié)點(diǎn)。則取一跳鄰居節(jié)點(diǎn)AiNj_1hop，將AiNj_1hop的一跳鄰居AiNjNk_2hop的ID依次與Ai的其他一跳鄰居AiNj+1_1hop進(jìn)行對比。如果ID相等，說明Ai、AiNj+1_1hop、AiNjNk_2hop3個節(jié)點(diǎn)組成一個環(huán)，將組成環(huán)的節(jié)點(diǎn)ID存儲到環(huán)列表中，跳轉(zhuǎn)到第（3）步。如果ID不相等，則將節(jié)點(diǎn)ID存儲到表示折線的列表中，跳轉(zhuǎn)到第（2）步。

（2）將AiNj_1hop的一跳鄰居AiNjNk_2hopID依次與AiNj+1_1hop的一跳鄰居AiNj+1Nk_2hopID進(jìn)行對比。如果ID相等，則Ai、AiNj_1hop、AiNjNk_2hop、AiNj+1_1hop4個節(jié)點(diǎn)組成一個環(huán)，將組成環(huán)的節(jié)點(diǎn)ID存儲到表示環(huán)的列表中，并跳轉(zhuǎn)到第（3）步。如果ID不相等，就將節(jié)點(diǎn)ID存儲到表示折線的列表中，也跳轉(zhuǎn)到第（3）步。

（3）繼續(xù)用AiNj_1hop的一跳鄰居AiNjNk_2hop執(zhí)行第（2）步，直到AiNj_1hop的一跳鄰居列表遍歷完畢。在Ai重復(fù)執(zhí)行上述步驟時，如果AiNjNk_2hop的ID與Ai或AiNj_1hop的ID相等則直接跳過（1）（2）步，繼續(xù)遍歷下一個節(jié)點(diǎn)，因?yàn)樵摥h(huán)已經(jīng)被遍歷記錄過。

（4）繼續(xù)用Ai剩余的一跳鄰居節(jié)點(diǎn)執(zhí)行上述三步，直到Ai的一跳鄰居節(jié)點(diǎn)遍歷完畢。

（5）將前面四步得到的環(huán)的節(jié)點(diǎn)ID相互進(jìn)行對比。如果環(huán)包含了折線的所有點(diǎn)，則刪掉該折線；如果環(huán)與環(huán)之間有兩個及兩個以上的公共節(jié)點(diǎn)，則兩個環(huán)合并為同一個環(huán)。

經(jīng)過以上五步，節(jié)點(diǎn)Ai依個點(diǎn)判定規(guī)則能夠判斷出由3個或4個節(jié)點(diǎn)組成的環(huán)和不超過3個節(jié)點(diǎn)的折線中的節(jié)點(diǎn)是割點(diǎn)還是普通節(jié)點(diǎn)。如果仍舊無法判斷出自己是否是割點(diǎn)則繼續(xù)執(zhí)行后續(xù)的詢問鄰居節(jié)點(diǎn)部分。

挖掘本地信息是DCVN最基本最重要的一步，此處以圖1中節(jié)點(diǎn)A25為例說明挖掘本地信息的過程。首先，A25讀取兩跳鄰居信息，得到自己及一跳鄰居的一跳鄰居列表（表3）。首先，A25讀取第一個一跳鄰居節(jié)點(diǎn)A1所對應(yīng)的一跳鄰居列表中的A0，再將A0的節(jié)點(diǎn)ID分別與A25的其余的一跳鄰居節(jié)點(diǎn)A8、A18、A15的ID進(jìn)行對比，ID不相等，此時第一步執(zhí)行完畢。第二步，A25將A0的節(jié)點(diǎn)ID分別和A8、A18、A15的一跳鄰居列表（即A25的二跳鄰居節(jié)點(diǎn)ID）進(jìn)行對比，發(fā)現(xiàn)A0的ID和A15的一跳鄰居列表中的某個節(jié)點(diǎn)的ID相等而其他A25的兩跳鄰居列表中沒有與A0相同的節(jié)點(diǎn)，所以判定只有A25、A1、A15、A0這4個節(jié)點(diǎn)組成環(huán)并記錄到環(huán)的列表中。接下來執(zhí)行第三步，A25讀取A1所對應(yīng)的一跳鄰居節(jié)點(diǎn)A11，并重復(fù)執(zhí)行第一步和第二步。由于沒有節(jié)點(diǎn)與A11的ID相等，所以A25保存A25、A1、A11這3個節(jié)點(diǎn)組成的折線到折線列表中。

按以上方法遍歷A15、A1、A8、A18，能夠得到表4。在遍歷完所有的一跳鄰居之后，A25對得到的環(huán)和折線進(jìn)行合并處理最后，A25得到的挖掘本地信息表如表5所示。

表3 A25、A1、A15、A8、A18的一跳鄰居列表

表4 節(jié)點(diǎn)A25合并之前構(gòu)成的環(huán)與折線

表5 節(jié)點(diǎn)A25合并之后構(gòu)成的環(huán)與折線

根據(jù)表4的信息，A25暫時不能判斷自己是割點(diǎn)還是普通節(jié)點(diǎn)，所以A25繼續(xù)執(zhí)行DCVN算法后面的詢問鄰居節(jié)點(diǎn)部分的算法。

在執(zhí)行完畢挖掘本地信息的過程后，雖然A25還不能推斷出自己是否是割點(diǎn)，但是有一部分節(jié)點(diǎn)已經(jīng)可以判斷出自己是割點(diǎn)還是普通節(jié)點(diǎn)。圖1所示的拓?fù)浣Y(jié)構(gòu)在執(zhí)行完挖掘本地信息過程后，得到的拓?fù)浣Y(jié)構(gòu)如圖3所示，黑色填充節(jié)點(diǎn)是割點(diǎn)，灰色填充節(jié)點(diǎn)是暫時不能做出判斷的節(jié)點(diǎn)。

4.3 詢問鄰居節(jié)點(diǎn)做判斷

假如Ai經(jīng)過上一步還不能判斷自己究竟是割點(diǎn)還是普通節(jié)點(diǎn)則Ai繼續(xù)向自己的部分第二跳鄰居節(jié)點(diǎn)AiNjNk_2hop發(fā)送請求消息，請求AiNjNk_2hop發(fā)送自身的兩跳鄰居列表給Ai。Ai根據(jù)收到的消息進(jìn)一步判斷自己是否為割點(diǎn)。詢問兩跳鄰居節(jié)點(diǎn)其實(shí)就是要分析得出大于4個節(jié)點(diǎn)組成的環(huán)。Ai的詢問兩跳鄰居節(jié)點(diǎn)部分分為以下4步：

①Ai發(fā)送請求消息，獲取Ai的兩跳節(jié)點(diǎn)AiNjNk_2hop的兩跳鄰居列表（也就是距Ai三跳或四跳的鄰居列表）。

我們把Ai的一跳鄰居節(jié)點(diǎn)AiNj_1hop分成兩類，一類AiNj_1hop是組成環(huán)的一部分。另一類AiNj_1hop不是環(huán)的一部分（即是折線的一部分）。Ai只向第二類AiNj_1hop的一跳鄰居AiNjNk_2hop發(fā)送請求，獲得AiNjNk_2hop的兩跳鄰居列表，但是這兩跳鄰居不能包括回溯的點(diǎn)，即AiNjNk_2hop的一跳鄰居需要把AiNj_1hop排除在外。

例如，圖3中的節(jié)點(diǎn)A25發(fā)送請求消息給A2、A17、A10，請求A2、A17、A10發(fā)送兩跳鄰居列表給A25。但是A25不發(fā)送請求消息給A11、A12、A4，因?yàn)锳11、A12、A4所對應(yīng)的A1、A8、A15已經(jīng)是上一步中挖掘本地信息部分得到的環(huán)的組成部分。

圖3 DCVN挖掘本地信息后的割點(diǎn)分布

②）Ai根據(jù)收到的AiNjNk_2hop兩跳內(nèi)的鄰居節(jié)點(diǎn)信息，分析已知信息中是否還有環(huán)存在。Ai首先將第一步得到的兩跳鄰居AiNjNk_2hop中的一跳和二跳節(jié)點(diǎn)ID與挖掘本地信息部分得到的折線的第三個節(jié)點(diǎn)（即Ai的二跳鄰居節(jié)點(diǎn)）ID進(jìn)行對比，如果相等，說明相關(guān)聯(lián)的這些節(jié)點(diǎn)能組成一個環(huán)將他們存入Ai的環(huán)列表，否則，轉(zhuǎn)到第（3）步。

③Ai將第一步得到的兩跳鄰居AiNjNk_2hop中的一跳和二跳節(jié)點(diǎn)ID相互對比，也與其他的兩跳鄰居AiNjNk+1_2hop的一跳和兩跳鄰居進(jìn)行對比。如果有相等的節(jié)點(diǎn)就說明Ai、AiNj_1hop、AiNjNk_2hop這條折線之后有環(huán)存在；如果不相等的節(jié)點(diǎn)就認(rèn)為此條折線之后是葉子節(jié)點(diǎn)。依次遍歷對比Ai的所有兩跳節(jié)點(diǎn)的后續(xù)兩跳節(jié)點(diǎn)。

④將的Ai環(huán)列表中的環(huán)與環(huán)進(jìn)行對比，折線與折線進(jìn)行對比。如果有重復(fù)的環(huán)則刪掉多余的；如果環(huán)與環(huán)之間有兩個或兩個以上的公共節(jié)點(diǎn)，則這兩個環(huán)合并為一個環(huán)。如果有能覆蓋短折線的更長折線則取最長的那條折線。

經(jīng)過以上三步節(jié)點(diǎn)Ai能夠得到節(jié)點(diǎn)數(shù)量超過4個少于9個的環(huán)，此時可以再次根據(jù)割點(diǎn)判定規(guī)則進(jìn)行判斷。此次判斷能夠判斷出由5到8個節(jié)點(diǎn)組成的環(huán)和4個節(jié)點(diǎn)組成的折線中的節(jié)點(diǎn)是割點(diǎn)還是普通節(jié)點(diǎn)。

經(jīng)過詢問鄰居節(jié)點(diǎn)的以上四步，對于超過8個節(jié)點(diǎn)組成的環(huán)和超過5個節(jié)點(diǎn)組成的折線我們還是不能得出來，對于依舊不能判斷自身是否是割點(diǎn)的DCVN默認(rèn)為割點(diǎn)。首先，超過8個節(jié)點(diǎn)的折線中的節(jié)點(diǎn)本來就是割點(diǎn)，所以我們直接判定其為割點(diǎn)。而對于超過8個節(jié)點(diǎn)組成的環(huán)，首先該節(jié)點(diǎn)無法判斷出自身是否處于一個環(huán)網(wǎng)中。即使該節(jié)點(diǎn)處于一個環(huán)網(wǎng)中（超過8個節(jié)點(diǎn)組成），假如這個節(jié)點(diǎn)失效，那么這個環(huán)中其他節(jié)點(diǎn)間的通信就可能需要迂回很長的距離來實(shí)現(xiàn)，在該迂回距離較長的時候會加快該通信路線上節(jié)點(diǎn)的能量消耗［16］，所以我們也將這樣的節(jié)點(diǎn)視為割點(diǎn)。割點(diǎn)判定的整個過程如圖4中流程圖所示。

例如，圖5（A）中，A0能夠通過詢問鄰居節(jié)點(diǎn)得到由A0、A1、A2、A3、A4、A5、A6、A7這8個節(jié)點(diǎn)組成的環(huán)，我們能夠判斷出A0不是割點(diǎn)。圖5（B）中，A0通過詢問鄰居節(jié)點(diǎn)執(zhí)行DCVN算法，無法判斷自身是否處于環(huán)中，即A0無法判斷自身是不是割點(diǎn)。此時即使A0處于環(huán)中，由于環(huán)路可能較長（環(huán)中節(jié)點(diǎn)數(shù)大于等于9個）一旦A0斷開，其他節(jié)點(diǎn)的通信代價較大，需要消耗較多的能量來進(jìn)行信息的交換，此時我們也將A0看作割點(diǎn)。

圖4 割點(diǎn)檢測流程圖

圖5 8個及8個以上節(jié)點(diǎn)組成的環(huán)

在執(zhí)行完DCVN算法后，網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)都能夠判斷出自己是割點(diǎn)還是普通節(jié)點(diǎn)。圖3中的拓?fù)浣Y(jié)構(gòu)執(zhí)行完DCVN算法后，到的結(jié)果如圖6所示。其中，白色節(jié)點(diǎn)是普通節(jié)點(diǎn)，陰影填充節(jié)點(diǎn)是割點(diǎn)在算法的成功率方面，除非拓?fù)浣Y(jié)構(gòu)中存在8個以上節(jié)點(diǎn)組成的環(huán)，否則DCVN都能夠準(zhǔn)確的判斷出節(jié)點(diǎn)到底是割點(diǎn)還是普通節(jié)點(diǎn)。

圖6 執(zhí)行完DCVN算法后的割點(diǎn)分布

5 實(shí)驗(yàn)?zāi)M及分析

我們在實(shí)驗(yàn)中引入了幾個指標(biāo)來衡量DCVN算法性能：

割點(diǎn)占比（Critical Node Ratio）：代表算法檢測出的割點(diǎn)的數(shù)量占總節(jié)點(diǎn)數(shù)量的百分比。用于近似衡量網(wǎng)絡(luò)的連接性和易損壞性，占比越大表明網(wǎng)絡(luò)的連接性越差，越容易損壞。其中Critical node表示算法成功檢測出的割點(diǎn)。由于檢測準(zhǔn)確率通常不能達(dá)到百分之百，因此Critical Node數(shù)目小于等于網(wǎng)絡(luò)中實(shí)際存在的割點(diǎn)（cut vertex）數(shù)目。

割點(diǎn)檢測準(zhǔn)確率（Detection Ratio）：代表網(wǎng)絡(luò)中被正確識別為割點(diǎn)的節(jié)點(diǎn)數(shù)量占割點(diǎn)實(shí)際總數(shù)量的百分比。表明了DCVN算法的識別準(zhǔn)確率。

部署節(jié)點(diǎn)數(shù)量（Number of Nodes）：整個網(wǎng)絡(luò)區(qū)域中組成網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量，反映網(wǎng)絡(luò)的規(guī)模，同時因?yàn)閷?shí)驗(yàn)區(qū)域一定，所以網(wǎng)絡(luò)中節(jié)點(diǎn)的密度也在增加。

通信半徑（Communication Range）：兩個相鄰節(jié)點(diǎn)能夠相互通信的最大距離。網(wǎng)絡(luò)中的所有節(jié)點(diǎn)設(shè)為相同的通信半徑。

實(shí)驗(yàn)?zāi)M在NS-2.35軟件上進(jìn)行，無線傳感器與執(zhí)行器的部署區(qū)域設(shè)定為1 000 m×1 000 m，節(jié)點(diǎn)數(shù)量取50、100、150、200、250共五種情況。節(jié)點(diǎn)的通信半徑設(shè)為100、125、150、175、200、225、250共七種情況。節(jié)點(diǎn)個數(shù)默認(rèn)150個，節(jié)點(diǎn)通信半徑默認(rèn)150 m。

5.1 割點(diǎn)占比

圖7中，最大通信半徑150 m保持不變。隨著網(wǎng)絡(luò)區(qū)域中節(jié)點(diǎn)數(shù)量的增加，割點(diǎn)占比呈下降趨勢。在節(jié)點(diǎn)數(shù)量從50個增加到150個的過程中，割點(diǎn)占比下降速度較快。對比其他幾種割點(diǎn)檢測算法，DCVN檢測的割點(diǎn)占比較低。隨著節(jié)點(diǎn)數(shù)量的增加，割點(diǎn)占比呈下降趨勢。這是因?yàn)椋S著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增加，網(wǎng)絡(luò)中的通信冗余鏈路必然會越來越多，網(wǎng)絡(luò)中的割點(diǎn)必然逐漸減少。另外，隨著節(jié)點(diǎn)數(shù)量的增加，在仿真實(shí)驗(yàn)的環(huán)境中，節(jié)點(diǎn)的密度也在增加，即節(jié)點(diǎn)之間的平均距離是減少的，節(jié)點(diǎn)和節(jié)點(diǎn)之間能夠相互通信的概率也隨之增加，所以割點(diǎn)占比在變小。

圖7 割點(diǎn)占比與節(jié)點(diǎn)數(shù)量的關(guān)系

在圖8中，網(wǎng)絡(luò)區(qū)域中節(jié)點(diǎn)的數(shù)量150保持不變，橫坐標(biāo)是相鄰節(jié)點(diǎn)之間能夠通信的最大半徑，縱坐標(biāo)是割點(diǎn)所占總節(jié)點(diǎn)數(shù)量的百分比。可以看到，隨著最大通信半徑的增加，網(wǎng)絡(luò)中割點(diǎn)所占的比重也越來越小。這是因?yàn)殡S著最大通信半徑的增加，原本不能夠通信的兩節(jié)點(diǎn)開始變成鄰居節(jié)點(diǎn)，就是說就節(jié)點(diǎn)的一跳以及兩跳的鄰居變多了，節(jié)點(diǎn)之間能夠通信的概率越來越大，通信瓶頸變小，所以網(wǎng)絡(luò)中的割點(diǎn)數(shù)量不斷減少，割點(diǎn)占比呈下降趨勢。

圖8 割點(diǎn)占比與最大通信半徑的關(guān)系

5.2 割點(diǎn)檢測準(zhǔn)確率

圖9中，最大通信半徑保持150 m不變，橫坐標(biāo)表示區(qū)域中節(jié)點(diǎn)數(shù)量，從50個以50為步長逐次增加到250個，縱坐標(biāo)是割點(diǎn)檢測的準(zhǔn)確率。割點(diǎn)檢測率的變化趨勢較復(fù)雜，先略微下降再呈緩慢上升趨勢。可以看到，DCVN的割點(diǎn)檢測率在這幾種割點(diǎn)檢測算法中是最高的，表明我們的算法可以很好的完成割點(diǎn)檢測任務(wù)。

圖10顯示的是在節(jié)點(diǎn)數(shù)量保持150不變的前提下，割點(diǎn)檢測的準(zhǔn)確率隨著最大通信半徑的變化趨勢。可以看出，隨著通信半徑的增加，這4種算法對割點(diǎn)的檢測率都是逐漸增大的，DCVN算法只有在通信半徑最短的情況下檢測率較低，隨著最大通信半徑的增大，DCVN算的檢測率一直是這幾種算法中最高的。

圖9 割點(diǎn)檢測準(zhǔn)確率與節(jié)點(diǎn)數(shù)量的關(guān)系

圖10 割點(diǎn)檢測準(zhǔn)確率與最大通信半徑的關(guān)系

DCVN是一種分布式算法，收斂速度較快。在通常情況下節(jié)點(diǎn)只與其一跳鄰居交換信息，此時DCVN算法的時間復(fù)雜度為T(n)=O(n2)。在最壞的情況下節(jié)點(diǎn)需要與其兩跳鄰居進(jìn)行交互，此時DCVN算法的時間復(fù)雜度為T(n)=O(n4)。因此DCVN檢測準(zhǔn)確率的提高是以部分增加算法的時間復(fù)雜度為代價的。

6 總結(jié)

WSANs不僅能夠監(jiān)測環(huán)境中的事件信息而且能夠主動改變環(huán)境狀態(tài)以滿足用戶需求，從而大大拓展了無線傳感器網(wǎng)絡(luò)的能力和應(yīng)用范圍。有效的割點(diǎn)檢測算法能夠?yàn)橥負(fù)湫迯?fù)提供準(zhǔn)確的數(shù)據(jù)，對于提高拓?fù)湫迯?fù)的效率增強(qiáng)WSANs的魯棒性有著重要意義。本文提出了一種基于鄰居信息進(jìn)行割點(diǎn)檢測的分布式算法DCVN，該算法建立了割點(diǎn)的判別準(zhǔn)則，每個節(jié)點(diǎn)通過與距離自身至多兩跳的鄰居節(jié)點(diǎn)進(jìn)行信息交換來建立局部的網(wǎng)絡(luò)拓?fù)湫畔ⅲ⒒谶@些準(zhǔn)則分析網(wǎng)絡(luò)拓?fù)渲械沫h(huán)和折線從而實(shí)現(xiàn)割點(diǎn)的檢測。仿真實(shí)驗(yàn)表明，該算法能夠準(zhǔn)確識別網(wǎng)絡(luò)中的割點(diǎn)，與現(xiàn)有幾種有代表性的割點(diǎn)檢測算法相比DCVN的檢測準(zhǔn)確率較高。

［1］Melodia T，Pompili D，Gungor V C，et al.Communication and Coordination in Wireless Sensor and Actor Networks［J］.Mobile Computing，IEEE Transactions on，2007，6（10）：1116-1129.

［2］魏春娟，楊俊杰，張志美.一種分布式能量有效的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.傳感技術(shù)學(xué)報，2013，26（7）：1014-1018.

［3］Amiya Nayak，Ivan Stojmenovic.Wireless Sensor and Actuator Networks Algorithms and Protocols for Scalable Coordination and Data Communication［M］.New Jersey：John Wiley&Sons，2010：15-20.

［4］Wu X，Liu M，Wu Y.In-situ Soil Moisture Sensing：Optimal Sen?sor Placement and Field Estimation［J］.ACM Transactions on Sensor Networks（TOSN），2012，8（4）：33.

［5］Xiong S，Li J.An Efficient Algorithm for Cut Vertex Detection in Wireless Sensor Networks［C］//Distributed Computing Systems（ICDCS），2010 IEEE 30th International Conference on.IEEE，2010：368-377.

［6］Liu X，Xiao L，Kreling A.A fully Distributed Method to Detect and Reduce Cut Vertices in Large-Scale Overlay Networks［J］.Computers，IEEE Transactions on，2012，61（7）：969-98

［7］Jorgic M，Hauspie M，Simplot-Ryl D，et al.Localized Algorithms for Detection of Critical Nodes and Links for Connectivity in Ad Hoc Networks［C］//Mediterranean Ad Hoc Networking Workshop，2004：12.

［8］Imran M，Younis M，Said A M，et al.Localized Motion-Based Con?nectivity Restoration Algorithms for Wireless Sensor and Actor Networks［J］.Journal of Network and Computer Applications，2012，35（2）：844-856.

［9］Dai F，Wu J.An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks［J］.Par?allel and Distributed Systems，IEEE Transactions on，2004，15（10）：908-920.

［10］Akkaya K，Thimmapuram A，Senel F，et al.Distributed Recovery of Actor Failures in Wireless Sensor and Actor Networks［C］//Wireless Communications and Networking Conference，2008.WCNC 2008.IEEE.IEEE，2008：2480-2485.

［11］Zamanifar A，Sharifi M，Kashefi O.A Hybrid Approach to Actor-Actor Connectivity Restoration in Wireless Sensor and Actor Net?works［C］//Networks，ICN’09，2009.

［12］Alnuem M，Zafar N A，Imran M，et al.Formal Specification and Validation of a Localized Algorithm for Segregation of Critical/Noncritical Nodes in MAHSNs［J］.International Journal of Dis?tributed Sensor Networks，2014，19：1167-1172.

［13］Zhang Y，Zhang X，Wang Z，et al.Virtual Edge Based Coverage Hole Detection Algorithm in Wireless Sensor Networks［C］//Wire?less Communications and Networking Conference（WCNC），2013 IEEE.IEEE，2013：1488-1492.

［14］Gary Chartrand，Ping Zhang著.圖論導(dǎo)引.范益政，汪毅，龔世才，朱明，譯.人民郵電出版社，2007：93-94.

［15］Xiong S，Li J.An Efficient Algorithm for Cut Vertex Detection in Wireless Sensor Networks［C］//Distributed Computing Systems（ICDCS），2010 IEEE 30th International Conference on.IEEE，2010：368-377.

［16］王越，萬洪.一種節(jié)能的無線傳感器網(wǎng)絡(luò)多跳自適應(yīng)時間同步算法［J］.傳感技術(shù)學(xué)報，2013，26（11）：1557-1563.