基于輪作的無線傳感網絡鏈式路由協議

于 秦，王偉東，張蘭心，毛玉明

?

基于輪作的無線傳感網絡鏈式路由協議

于 秦，王偉東，張蘭心，毛玉明

(電子科技大學通信與信息工程學院 成都 611731)

為了節省無線傳感器節點能耗，延長無線傳感網絡的生存周期，提出一種基于輪流作業策略的RPB無線傳感網絡鏈式節能路由協議。該協議基于PEGASIS鏈式協議并結合GAF協議進行改進。仿真結果顯示，在保證有較高網絡覆蓋度的前提下，相較于傳統的無線傳感網絡PEGASIS、LEACH和EEPB等路由協議，RPB協議在節能上更為突出，且在傳感節點死亡超過總數的一半時，能實現節點在網絡中較為均勻的分布。

節能; 輪作; 路由協議; 無線傳感網絡

針對無線傳感器節點能量有限的問題，為了延長無線傳感網絡的生存周期，研究人員提出了許多能量高效的算法[1]。其中PEGASIS(power-efficient gathering in sensor information system)鏈式協議[2]是建立在LEACH(low energy adaptive clustering hierarchy)分簇算法[3]基礎上的改進協議，通過貪婪算法生成一條由所有節點組成的單鏈，然后由鏈中的節點輪流擔任LEADER節點，并在融合全網數據后將數據發往基站。這種做法可以在最大程度上減少節點的耗能，EEPB(energy-efficient PEGASIS- base protocol)[4]則是基于PEGASIS協議的改進算法；GAF(geographical adaptive fidelity)[5]協議是以節點的地理位置為依據的算法，通過把檢測區域劃分成虛擬的單元格，每個單元格中的節點可以認為是等價的，因此在一個時間段內，一個單元格只需要一個節點實施數據采集，同一單元格內的其他節點可以進入睡眠以節省能量。上述算法的不足主要體現在：PEGASIS中已經加入鏈的鄰居不能被再次訪問，因此相鄰節點間長鏈不可避免，且節點輪流當選LEADER策略會導致遠離基站的節點過早死亡；而GAF則要求節點配備GPS等額外設備來獲取節點地理位置信息，增加了無線傳感器節點的制造成本。此外，還有在GAF和PEGASIS的基礎上改進的GSSC[6]協議，該協議同GAF一樣把檢測區域分成虛擬單元格，格間節點按距離組成多條鏈，也需要節點擁有全局位置信息。而CRBCC[7]則是在PEGASIS的基礎上并行建成多跳鏈，鏈首之間又建鏈，挑選其中一個鏈首向基站發送消息，該協議有效地減少了數據傳輸時延，但節能性略差于PEGASIS。類似的還有CCM[8]，要求節點均勻地分布在監測區域。在分析各種算法后，本文提出了一種基于輪作和鏈式的無線傳感網絡節能路由新算法RPB(rotation and PEGASIS-based protocol)。

1 無線傳感網絡隨機分布模型及覆蓋控制

在對協議進行描述之前，先介紹無線傳感網絡隨機分布及覆蓋控制模型。參考文獻[9]已經證明，在一個覆蓋的網絡模型中，如果傳感器節點在監測區域內呈密度分布為的均勻分布，區域內節點個數的概率服從泊松分布，其概率密度函數為：

證明：

(4)

2 協議描述

RPB協議由3個階段組成：鏈路建立階段、LEADER節點選取階段和數據傳輸階段。

2.1 鏈路建立階段

在鏈路建立階段，基站廣播hello消息，節點應答后基站即獲取全網信息，如節點ID、存活狀況、節點到基站的距離等，此時當一個節點收到其他節點發送給基站的信息時，可以通過鍵值對的方式記錄所有其他節點的ID及這些節點與自己的距離。然后，基站廣播最遠節點(END)的ID并從離基站最遠的節點開始建立鏈路，END節點在記錄中尋找距離自己最近的未加入鏈的節點，通過發送數據量很少的請求消息讓目標節點加入鏈中，其中，請求消息含有當前已經加入鏈路的節點個數，其他節點監聽到該消息時更新自己的鏈路信息，如果監聽到的請求消息信息與自身記錄信息不符，可通過詢問鄰居節點的方式獲得當前鏈路。

當節點能量即將耗盡時，為了確保節點留有一定的剩余能量并能在下一個數據發送周期開始前通知鄰居，設節點最小剩余能量為，其中為節點作為LEADER發送一次數據到基站所消耗的能量，當節點能量小于等于，節點不再進入睡眠，并通知被接替工作的節點(假設為節點)，如果節點周圍沒有剩余能量大于的節點在下一輪接替其工作，則節點也不再進入睡眠，每一輪都參加鏈路建立和數據傳輸。

圖1 鏈路建立過程

由該算法構成的鏈如圖2所示(圖中未加入鏈的帶“*”的節點為本輪進入睡眠的節點，帶“+”的節點為下一輪將進入睡眠的節點)。

圖2 由RPB算法構成的鏈

2.2 LEADER節點選取階段

選取LEADER節點時，參考常用的無線傳輸能量耗費模型(radio energy dissipation model, REDM)?；谠撃Ｐ?，傳輸一個比特的消息，節點消耗的能量為：

(6)

接收該消息需要消耗的能量為：

(8)

2.3 數據傳輸階段

在數據傳輸階段，每個傳感器節點調整自身發射功率以便只有最近鄰居才能聽到，然后進入數據傳輸階段。數據傳輸階段使用Token(令牌)機制，Token很小，因此在傳輸過程中耗能較小，其傳輸過程如圖3所示。END節點0首先獲得Token，沿著數據鏈將數據傳給1，1將0發來的數據和自身采集的數據進行融合后傳給2，然后2將Token傳給端節點4；2以同樣的方式收集到4和3的數據以后與自身采集的數據融合，沿著LEADER節點方向將數據傳到5[10]。

LEADER節點以同樣方式收集到所有數據并進行融合后發送到基站，至此一輪數據收集結束。在該輪進入休眠的節點此時醒來，被接替工作的節點設定定時器并進入睡眠，協議從鏈路建立階段的“基站廣播hello消息，節點應答后基站即獲取全網信息”這一步驟之后重新開始下一輪數據傳輸。

圖3 數據傳輸過程

3 仿真實驗

結合上述覆蓋模型，通過MATLAB以不同的密度將無線傳感器節點部署在不同的場景中，并改變的值，觀察其面積覆蓋率。其中傳感器節點的感知半徑由傳感器本身性能決定。本文假設，對每個場景下的不同節點總數分別進行500次節點隨機撒播模擬，并取在一輪里面工作節點的平均個數(結果統一向下取整)，得到的數據如表1和表2所示。

當所有節點在一輪里全部投入工作，即其最大面積覆蓋率對應25、50和100個節點分別為86.6%、98.2%和99.97%。

當所有節點在一輪里全部投入工作，即其最大面積覆蓋率對應50、100、150和200個節點分別為63.39%、86.6%、95.09%和98.2%。

表1 50 m×50 m場景下節點隨機撒播模擬

表2 100 m×100 m場景下節點隨機撒播模擬

3.1 仿真場景及參數

本文在100 m×100 m的場景中隨機放置了100個節點，其中基站的位置為(50,300)，其他具體仿真參數如表3所示。

表3 仿真參數

3.2 不同協議性能對比分析

通過MATLAB分別對LEACH、PEGASIS、EEPB(為定義距離門限時用戶自定義的系數，本文取值1.2)和RPB進行仿真對比，得到的結果如圖4所示，其中輪數越大表示網絡的生存時間越長。

從存活節點圖可以看出鏈式協議比簇類協議在減少能量消耗、延長網絡生命周期方面的優勢較為突出，而通過輪作的策略使得RPB比EEPB的生存時間延長了15.04%，比PEGASIS的生存時間延長了28.72%，比LEACH的生存時間延長了115%，其中RPB優于EEPB的部分主要為休眠節點所貢獻。

圖4 不同協議的對比仿真

表4為死亡節點占所有節點不同百分比下的協議輪數對比，可見RPB首個死亡節點出現比EEPB早，這是由于選取鏈首的策略不一樣造成的。死亡節點占10%時出現的輪數比EEPB延后了11.3%，而死亡節點占50%以及死亡節點占100%時，RPB相對EEPB延后了14.6%和15%。

表4 死亡節點占所有節點的百分比

圖5為網絡的剩余能量圖，從網絡能量消耗曲線可以看出，LEACH的斜率較大，曲線較陡，PEGASIS次之，EEPB和RPB的曲線斜率較小也較為平緩。由此可見，在一定時間內，鏈式協議的剩余能量明顯多于分簇式協議的剩余能量。以EEPB和RPB參照節點能量來選擇LEADER節點，因此消耗曲線看似一條直線，而LEACH和PEGASIS則以概率或者輪流的方式來選擇簇頭或者鏈首，因此消耗曲線在剩余能量較低的地方斜率會發生變化，這是因為遠離基站的節點此時都已經死亡，只剩下離基站近的存活節點在工作。

圖5 網絡的剩余能量圖

3.3 改變節點數量時不同協議性能對比分析

通過MATLAB分別對LEACH、PEGASIS、EEPB和RPB在不同節點數量時的性能進行仿真和對比分析，其結果如圖6所示。

分析圖6的數據可得，當改變時，基于分簇的LEACH協議由于節點并沒有分攤將數據發送到基站所消耗的能量，因此在存活時間上沒有改善，而鏈式協議由于節點分攤了將數據發送到基站所消耗的能量，因此存活時間得以延長。通過協議間比較可以發現，當=100時，RPB比EEPB的存活周期延長了15.04%，比PEGASIS延長了28.72%；當=150時，RPB比EEPB的存活周期延長了23.63%，比PEGASIS延長了39.35%；當=200時，RPB比EEPB的存活周期延長了39.1%，比PEGASIS延長了54.89%?？梢姡S著監測區域中節點密度的提高，可以進入休眠的節點也隨著增加，休眠輪作調度的優越性也漸漸顯示出來。

a.=150時，不同協議的節點存活圖

b.=150時，不同協議的節點剩余能量圖

c.=200時不同協議的節點存活圖

d.=200時，不同協議的節點剩余能量圖

圖6 當取不同的值時各個協議的性能比較

4 結 論

結合無線傳感網絡節點被密集撒播的特點，對某些感知范圍被其他節點完全或絕大部分覆蓋的節點實行休眠輪作調度策略，以及改變節點加入鏈的條件和LEADER節點的選取策略，可以進一步實現減少節點能耗，從而為保證一定覆蓋率的前提下實現最大限度減少節點耗能提供了一種解決方案。對實時性不高，節點撒播較為密集且需要持續長久地監測目標的場合，其優勢比較明顯。

[1] 孫利民, 李建中, 陳渝, 等. 無線傳感器網絡[M]. 北京:清華大學出版社, 2005.

SUN Li-min, LI Jian-zhong, CHEN Yu, et al. Wireless sensor network[M]. Beijing: Tsinghua University Press, 2005.

[2] LINDSEY S, RAGHAVENDRA C. PEGASIS: Power- efficient gathering in Sensor information system[C]//Proc of IEEE Aerospace Conference. Los Alamitos, CA: IEEE Computer Society Press, 2002: 1-6.

[3] HEINZELMAN W R, CHANDRAKASA A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//IEEE Proceedings of the Hawail International Conference on System Science. [S.l.]: IEEE, 2000: 1-10.

[4] 余勇昌, 韋崗. 無線傳感器網絡中基于PEGASIS協議的改進算法[J]. 電子學報, 2008, 36(7): 1309-1313.

YU Yong-chang, WEI Gang. An improved PEGASIS algorithm in wireless sensor network[J]. Chinese Journal of Electronics, 2008, 36(7): 1309-1313.

[5] XU Y, HEIDEMANN J, ESTRIN D. Geography-informed energy conservation for ad hoc routing[C]//Proceedings of 7th Annual International Conference on Mobile Computing and Networking (MOBICOM’01). [S.l.]: ACM, 2001: 70-84.

[6] LOHAN P, RAJNI C. Geography-informed sleep scheduled and chaining based energy efficient data routing in WSN[C]//IEEE Students’ Conference on Electrical, Electronics and Computer Science. [S.l.]: IEEE, 2012: 9-12.

[7] ZHENG Geng-sheng, HU Zheng-bing. Chain routing based on coordinates-oriented clustering strategy in WSNS[C]//Computer Network and Multimedia Technology. Wuhan: [s.n.], 2009: 1-4.

[8] TANG Fei-long, LLSUM Y, GUO Song, et al. A chain-cluster based routing algorithm for wireless sensor network[J]. Journal of Intelligent Manufacturing, 2012, 23(4): 1305-1313.

[9] 高德民, 錢煥延, 徐江, 等. 無線傳感器網絡隨機分布模型及覆蓋控制研究[J]. 傳感技術學報, 2011, 24(3): 412-417.

GAO De-min, QIAN Huan-yan, XU Jiang, et al. Wireless sensor network random distribution model and coverage control research[J]. Chinese Journal of Sensors and Actuators, 2011, 24(3): 412-417.

[10] LIM Se-jung, PARK Myong-soon. Energy-efficient chain formation algorithm for data gathering in wireless sensor networks[J]. International Journal of Distributed Sensor Networks, doi: 10.1155/2012/843413.

編 輯 稅 紅

Rotation-Based WSN Chain Routing Protocol

YU Qin, WANG Wei-dong, ZHANG Lan-xin, and MAO Yu-ming

(School of Communication and Information Engineering, University of Electronic Science and Technology of China Chengdu 611731)

In this paper a rotation and PEGASIS-based energy-efficient chain routing protocol is proposed to reduce energy consumption in wireless sensor nodes and prolong the life span of wireless sensor networks (WSNs). The proposed protocol is an improved protocol of geographical adaptive fidelity (GAF) protocol based on (power-efficient gathering in sensor information system, PEGASIS) chain protocol. Simulation results demonstrate that the proposed protocolhas better performance in energy conservation than traditional routing protocols, such as PEGASIS, LEACH and EEPB. Moreover, more uniform distribution of the wireless sensor nodes could be realized when more than a half of the sensor nodes died.

energy-efficient (EE); rotation; routing protocol (RP); wireless sensor networks (WSN)

TN919

A

10.3969/j.issn.1001-0548.2015.02.006

2013-07-15；

2014-12-31

國家自然科學基金(61104042)；中央高校基本科研業務費專項資金(ZYGX2012J082)

于秦(1974-)，女，博士，副教授，主要從事無線網絡、移動通信和信息安全方面的研究.