無線傳感網中瓶頸節點的局部探測及其關鍵性的量化

吳院，馬永強

（西南交通大學 信息科學與技術學院，成都610031）

吳院（碩士研究生），研究方向為計算機網絡與信息系統；馬永強（教授），研究方向為網絡與信息系統、基于視頻圖像的監測技術、嵌入式系統及其應用。

引 言

無線傳感網是由大量能量資源有限的自組織傳感器節點密集部署而成［1］。所有節點的能量消耗并不是統一的，那些處在關鍵位置的節點會消耗更多的能量，這些關鍵節點的移除會導致網絡的斷裂［2］。為了實現節點的低成本，通常節點上都不會帶有GPS定位裝置，這樣節點就不知道其在網絡中的準確位置，也不能用定位方法去識別網絡中的瓶頸節點。本文提出了一種通過關鍵性來探測其是否為瓶頸節點的局部方法。

瓶頸節點示例如圖1所示。由于隨機部署的原因，連接兩個或多個區域的瓶頸節點必須承擔兩個區域之間大量數據包的轉發工作，因為在它的周圍沒有其他節點可以分擔他的負載。因此，其能量消耗速度比其他普通節點更快，這些節點的移除或死亡，會造成整個網絡的割裂［3］。

本文的目的就是要研究一種局部算法，用來識別瓶頸節點以及它們的關鍵性等級。節點的關鍵性等級會影響它們在網絡中數據包轉發工作的分配。通常，在基于節點的剩余能量確定其關鍵性時，假設對所有的節點來說，移除任意一個節點造成整個網絡被割裂的概率是相等的。

1 節點能耗假設

圖2和圖3分別表示存在關鍵節點與不存在關鍵節點的傳感網中所有節點的能耗分布［4］。圖2是不理想的節點能耗直方圖，可明顯知道網絡中確實存在瓶頸節點，一些節點因鄰居節點少而承擔少量的數據轉發工作，而其他擁有較多鄰居節點的節點會經常用來轉發數據，以至能量幾乎消耗殆盡，本文的目的就是要找出此類節點。圖3是理想的節點能耗直方圖。盡管兩者的總能耗量是相同的，但圖3中節點的能耗顯然要比圖2的均衡，這樣它的網絡生存期也相應會長些。

圖1 瓶頸節點示例

圖2 不理想的節點能耗直方圖

圖3 理想的節點能耗直方圖

研究中，假設所有節點都是靜止的，網絡拓撲不發生變化，沒有基礎設施支持，且任何兩個位于對方通信半徑內的節點都能互發消息。

2 局部探測算法

這里將所有的節點分為兩部分：一部分為根節點，它們在網絡初始階段以泛洪方式傳送消息；其他所有節點負責轉發各根節點的獨特消息。所有選出來的根節點必須保證網絡的大部分區域能被監控到。這些根節點有一個重要的特征：相比于其他普通節點，它們擁有較少數量的鄰居節點。因為這樣它們就很可能位于網絡的邊界處。通過鄰居節點的數量，就能選出最合適的根節點，也就能知道網絡的邊界節點。所以在節點部署完成后，通過節點的通信半徑來計算它們的鄰居節點數。

網絡拓撲中關鍵節點［5］的探測分兩步進行。

（1）尋找根節點

每個節點中都有一個可復位的定時器。如果超時，節點的等級標識值就會成為無窮大，沒有任何泛洪數據包［6］，成為一個孤立的節點。同樣，每個節點也有一個發送定時器，每個發送周期過后，它都會被重置。在每個發送定時器周期里，泛洪消息傳送都會發生。發送定時器的重要性不及可復位定時器。

節點部署完后，每個節點都會發送一個PⅠNG消息，在其傳輸半徑內的鄰居節點都會收到它。接收到消息的節點都會回復一個ACK消息，并且每個節點都會把它的鄰居節點信息保存下來［7］。鄰居節點的數量將成為判斷節點是否能成為根節點的依據。在一個節點分布密集的傳感網中，這些根節點很顯然會位于網絡拓撲的邊界處。

有一點必須要注意的是，被選出的任何兩個根節點不能位于彼此的通信半徑之內。這樣是為了避免造成對瓶頸節點錯誤的探測。

每個節點將其鄰居節點的數量發送給它的每一個鄰居節點，這樣每個節點就能知道它自己和每個鄰居節點的鄰居節點數。只有一個鄰居節點的節點將被判別為根節點。被選出來的根節點會發送泛洪數據包給其鄰居節點，然后每個鄰居節點會依次向更遠處轉發收到的泛洪消息［8］。如果所有的節點都有多個鄰居，這樣將沒有根節點。一旦超時，并且沒有收到泛洪消息，每個節點會重置它的發送定時器，并且增大用來作為根節點判斷依據的鄰居節點數這一閾值。

值得注意的是，為了能更好地估算出鄰居節點數，節點的通信半徑須取其最大可能值。這樣選出來的根節點位于網絡邊界的幾率最大。

（2）探測關鍵節點

假設整個網絡拓撲中有n個根節點，這些等級為0的節點開始發送泛洪消息，收到從0等級節點發送來的泛洪請求的鄰居節點會將它們自身等級標記為1，并向遠處傳播泛洪消息。其后依次進行。n個根節點就會在網絡中傳播n種不同的泛洪消息。每個節點會繼續轉發收到的泛洪消息，只要這個消息能使當前節點等級更高，否則，就丟棄這個消息［9］。

如果節點能同時收到兩個不同根節點發送來的消息，這個節點就是關鍵節點。如果這個關鍵節點或其子節點又收到另一根節點發送來的消息，那么它將比先前的關鍵節點更關鍵，因為這個節點連接著3個根節點。依此類推，節點的關鍵度取決于其所收到的不同泛洪消息的數量。這樣，在進行實際的數據傳輸之前，每個節點就能知道它的關鍵度。對于這一步，需選取最適宜的通信半徑來節省節點能量，并且不能有孤立節點存在。

3 性能分析與仿真

本節通過Matlab仿真說明網絡中瓶頸節點所占的比例，并將其歸類，最高類的瓶頸節點最關鍵。

仿真平臺采用Matlab。仿真時，假設160個節點隨機分布在一塊1 000m×1 000m的區域內，每個節點的傳輸半徑為185m，初始等級為無窮大，并用ⅠD號標識。選擇出的根節點分別位于方形區域的各個角落。

在任一拓撲網絡［10］中，感知數據的傳輸大多數時間都會穿越整個網絡，這樣可利于各節點關鍵度的探測，并通過采取合適的路由策略來延長網絡的生存期。每個根節點的關鍵度等級設為0，它們在網絡中廣播帶ⅠD編號的泛洪消息，其收到消息的鄰居節點的等級將被指派為1。當節點能收到兩個不同消息時，它就屬于第1類瓶頸節點，并且其所有子節點也將是瓶頸節點，因為它們必須通過父節點才能與各根節點相連。如果任何一個第1類瓶頸節點又收到來自第3個根節點的消息，那么它和它所有的子節點將屬于第2類瓶頸節點。這里的子節點是指所有與其相連而未收到任何根節點消息的節點。如果有n個根節點，則最多有（n－1）類瓶頸節點，第（n－1）類最關鍵，因為它們與n個根節點都存在通路，可能承擔整個網絡的數據轉發工作。

表1列出了任一拓撲網絡中各類瓶頸節點的百分比。此仿真中，選取了4個根節點，所以總共有3類瓶頸節點，其中第3類最關鍵。

表1 瓶頸節點的百分比

圖4中黑色圓點表示隨機部署在網絡中的傳感器節點。圖5表示根節點的選取，其中用矩形圈住的圓點為根節點。在圖6中，被矩形圈住的星狀點為第1類瓶頸節點，被三角形圈住的星狀點為第2類瓶頸節點，被圓形圈住的星狀點為最關鍵的第3類瓶頸節點。

圖4 傳感器節點的部署

圖5 選取根節點

圖6 瓶頸節點的探測

4 結 論

本文提出了一種傳感網中瓶頸節點的局部探測算法，并對其關鍵性進行量化。理論分析與仿真實驗表明，此算法對網絡中關鍵節點檢測的準確度較高，在每個節點進行實際的數據傳輸之前，就能知道它的關鍵度，從而減少關鍵節點的能量消耗，延長網絡的生存期，提高整個網絡的連通性和覆蓋率［11］，節省網絡維護的成本。

［1］Ⅰ Akyildiz，W Su，Y Sankarasubramaniam，et al.A Survey on Sensor Networks［J］.ⅠEEE Communications Magazine，2002，40（8）：102－114.

［2］J S Hartmut Ritter，Rolf Winter.A Partition Detection System for Mobile Ad－hoc networks［C］／／Sensor and Ad Hoc Communications and Networks（ⅠEEE－SECON），2004：489 497.

［3］Tian Le，Xie Dongliang，Han Bing，et al.Study on bottleneck nodes in wireless sensor networks［J］.Journal of Software，2006，17（4）：830－837.

［4］C Schurgers，M B Srivastava.Energy Efficient Routing in Wireless Sensor Networks［C］／／Military Communications Conference（ⅠEEE－MⅠLCOM），2001：357－361.

［5］Milenko Jorgic，Ⅰvan Stojmenovic.Localized Algorithms for Detection of Critical Nodes and Links for Connectivity in Ad Hoc Networks［C］／／20th Ⅰnternational Conference on Advanced Ⅰnformation Networking and Applications Volume 2（AⅠNA＇06），2006：336－340.

［6］張少軍.無線傳感器網絡技術及應用［M］.北京：中國電力出版社，2010.

［7］李磊，李鳳榮，黃河清.無線傳感器網絡局部瓶頸節點的分布式檢測算法［J］.西南交通大學學報，2011（3）.

［8］馬震.關于無線傳感器網絡節能的若干關鍵問題研究［D］.北京：北京交通大學，2009.

［9］Li Jiandong，Tian Ye，Sheng Min，et al.Partition detection for large scale ad hoc networks［J］.Journal of Communications，2008，29（9）：54－61.

［10］Gou Haosong，Yoo Younghwan.Distributed Bottleneck Node Detection in Wireless Sensor Network［C］／／10thⅠEEE Ⅰnternational Conference on Computer and Ⅰnformation Technology，2010.

［11］孫利民，李建中，等.無線傳感器網絡［M］.北京：清華大學出版社，2005.