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

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

（昆明理工大學(xué)云南省計算機技術(shù)應(yīng)用重點實驗室，昆明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)點。

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

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

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

1 相關(guān)工作

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

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

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

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

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

2 對網(wǎng)絡(luò)拓撲的基本劃分

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

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

圖1 一個WSANs的拓撲結(jié)構(gòu)

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

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

圖2 網(wǎng)絡(luò)拓撲的5種基本劃分

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

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

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

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

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

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

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

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

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

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

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

4.1 收集兩跳鄰居列表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 挖掘本地信息做判斷

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

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

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

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

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

（2）將AiNj_1hop的一跳鄰居AiNjNk_2hopID依次與AiNj+1_1hop的一跳鄰居AiNj+1Nk_2hopID進行對比。如果ID相等，則Ai、AiNj_1hop、AiNjNk_2hop、AiNj+1_1hop4個節(jié)點組成一個環(huán)，將組成環(huán)的節(jié)點ID存儲到表示環(huán)的列表中，并跳轉(zhuǎn)到第（3）步。如果ID不相等，就將節(jié)點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é)點，因為該環(huán)已經(jīng)被遍歷記錄過。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 DCVN挖掘本地信息后的割點分布

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

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

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

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

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

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

圖4 割點檢測流程圖

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

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

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

5 實驗?zāi)M及分析

我們在實驗中引入了幾個指標來衡量DCVN算法性能：

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

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

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

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

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

5.1 割點占比

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

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

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

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

5.2 割點檢測準確率

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

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

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

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

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

6 總結(jié)

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

［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.