吳院，馬永強

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都610031）

吳院（碩士研究生），研究方向為計算機網(wǎng)絡(luò)與信息系統(tǒng)；馬永強（教授），研究方向為網(wǎng)絡(luò)與信息系統(tǒng)、基于視頻圖像的監(jiān)測技術(shù)、嵌入式系統(tǒng)及其應(yīng)用。

引 言

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

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

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

1 節(jié)點能耗假設(shè)

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

圖1 瓶頸節(jié)點示例

圖2 不理想的節(jié)點能耗直方圖

圖3 理想的節(jié)點能耗直方圖

研究中，假設(shè)所有節(jié)點都是靜止的，網(wǎng)絡(luò)拓撲不發(fā)生變化，沒有基礎(chǔ)設(shè)施支持，且任何兩個位于對方通信半徑內(nèi)的節(jié)點都能互發(fā)消息。

2 局部探測算法

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

網(wǎng)絡(luò)拓撲中關(guān)鍵節(jié)點［5］的探測分兩步進行。

（1）尋找根節(jié)點

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

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

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

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

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

（2）探測關(guān)鍵節(jié)點

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

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

3 性能分析與仿真

本節(jié)通過Matlab仿真說明網(wǎng)絡(luò)中瓶頸節(jié)點所占的比例，并將其歸類，最高類的瓶頸節(jié)點最關(guān)鍵。

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

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

表1列出了任一拓撲網(wǎng)絡(luò)中各類瓶頸節(jié)點的百分比。此仿真中，選取了4個根節(jié)點，所以總共有3類瓶頸節(jié)點，其中第3類最關(guān)鍵。

表1 瓶頸節(jié)點的百分比

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

圖4 傳感器節(jié)點的部署

圖5 選取根節(jié)點

圖6 瓶頸節(jié)點的探測

4 結(jié) 論

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

［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－h(huán)oc 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］張少軍.無線傳感器網(wǎng)絡(luò)技術(shù)及應(yīng)用［M］.北京：中國電力出版社，2010.

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

［8］馬震.關(guān)于無線傳感器網(wǎng)絡(luò)節(jié)能的若干關(guān)鍵問題研究［D］.北京：北京交通大學(xué)，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］孫利民，李建中，等.無線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，2005.