吳院，馬永強(qiáng)

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

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

引 言

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

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

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

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

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

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

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

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

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

2 局部探測(cè)算法

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

網(wǎng)絡(luò)拓?fù)渲嘘P(guān)鍵節(jié)點(diǎn)［5］的探測(cè)分兩步進(jìn)行。

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

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

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

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

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

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

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

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

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

3 性能分析與仿真

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

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

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

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

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

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

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

圖5 選取根節(jié)點(diǎn)

圖6 瓶頸節(jié)點(diǎn)的探測(cè)

4 結(jié) 論

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

［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é)點(diǎn)的分布式檢測(cè)算法［J］.西南交通大學(xué)學(xué)報(bào)，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.