基于輪作的無線傳感網(wǎng)絡(luò)鏈式路由協(xié)議

于 秦，王偉東，張?zhí)m心，毛玉明

?

基于輪作的無線傳感網(wǎng)絡(luò)鏈式路由協(xié)議

于 秦，王偉東，張?zhí)m心，毛玉明

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

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

節(jié)能; 輪作; 路由協(xié)議; 無線傳感網(wǎng)絡(luò)

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

1 無線傳感網(wǎng)絡(luò)隨機分布模型及覆蓋控制

在對協(xié)議進行描述之前，先介紹無線傳感網(wǎng)絡(luò)隨機分布及覆蓋控制模型。參考文獻[9]已經(jīng)證明，在一個覆蓋的網(wǎng)絡(luò)模型中，如果傳感器節(jié)點在監(jiān)測區(qū)域內(nèi)呈密度分布為的均勻分布，區(qū)域內(nèi)節(jié)點個數(shù)的概率服從泊松分布，其概率密度函數(shù)為：

證明：

(4)

2 協(xié)議描述

RPB協(xié)議由3個階段組成：鏈路建立階段、LEADER節(jié)點選取階段和數(shù)據(jù)傳輸階段。

2.1 鏈路建立階段

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

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

圖1 鏈路建立過程

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

圖2 由RPB算法構(gòu)成的鏈

2.2 LEADER節(jié)點選取階段

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

(6)

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

(8)

2.3 數(shù)據(jù)傳輸階段

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

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

圖3 數(shù)據(jù)傳輸過程

3 仿真實驗

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

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

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

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

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

3.1 仿真場景及參數(shù)

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

表3 仿真參數(shù)

3.2 不同協(xié)議性能對比分析

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

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

圖4 不同協(xié)議的對比仿真

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

表4 死亡節(jié)點占所有節(jié)點的百分比

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

圖5 網(wǎng)絡(luò)的剩余能量圖

3.3 改變節(jié)點數(shù)量時不同協(xié)議性能對比分析

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

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

a.=150時，不同協(xié)議的節(jié)點存活圖

b.=150時，不同協(xié)議的節(jié)點剩余能量圖

c.=200時不同協(xié)議的節(jié)點存活圖

d.=200時，不同協(xié)議的節(jié)點剩余能量圖

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

4 結(jié) 論

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

[1] 孫利民, 李建中, 陳渝, 等. 無線傳感器網(wǎng)絡(luò)[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] 余勇昌, 韋崗. 無線傳感器網(wǎng)絡(luò)中基于PEGASIS協(xié)議的改進算法[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] 高德民, 錢煥延, 徐江, 等. 無線傳感器網(wǎng)絡(luò)隨機分布模型及覆蓋控制研究[J]. 傳感技術(shù)學報, 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)；中央高校基本科研業(yè)務(wù)費專項資金(ZYGX2012J082)

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