摘 要：無線傳感器網(wǎng)絡(luò)（WSN）路由協(xié)議研究的一個重要的目標是如何在有限的能源下降低整個網(wǎng)絡(luò)的能耗，提高網(wǎng)絡(luò)的生存時間。以分簇路由協(xié)議LEACH為研究基礎(chǔ)，提出了一種改進算法。該算法改進了簇首選擇規(guī)則，引入?yún)f(xié)調(diào)件協(xié)議算法，通過在成簇階段降低剩余能量低的節(jié)點被選擇成為簇首的概率，在穩(wěn)定運行階段使簇首節(jié)點盡可能多的保持睡眠狀態(tài)，從而降低了網(wǎng)絡(luò)能耗。仿真結(jié)果表明，與原LEACH算法相比，改進的算法能夠明顯地延長網(wǎng)絡(luò)生存時間。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)； 分簇算法； 協(xié)調(diào)件協(xié)議； 生存周期

中圖分類號：TN91134 文獻標識碼：A 文章編號：1004373X（2012）22009704

0 引 言

無線傳感器網(wǎng)絡(luò)（WSN）是由具有感知、計算存儲和無線通信能力的微型傳感器組成的網(wǎng)絡(luò)，由于其具有自組織、自治、自適應(yīng)等屬性，已廣泛應(yīng)用于軍事偵察、醫(yī)療監(jiān)護、環(huán)境監(jiān)測、農(nóng)業(yè)養(yǎng)殖等領(lǐng)域［1］。由于無線傳感器網(wǎng)絡(luò)節(jié)點體積小，一般都依靠電池供電，但是電池容量有限，而網(wǎng)絡(luò)中節(jié)點數(shù)量巨大，節(jié)點的更換和能量補充很難實現(xiàn)，因此，如何最大限度地節(jié)省能源的使用以及延長整個網(wǎng)絡(luò)的生存時間是無線傳感器網(wǎng)絡(luò)研究的關(guān)鍵［24］。

針對上述問題，國內(nèi)外提出了多種路由算法，其中分簇路由算法是比較符合傳感器網(wǎng)絡(luò)特性的高效算法。LEACH就是一種經(jīng)典的分簇路由算法，它的基本思想是以循環(huán)方式隨機選取簇首，將網(wǎng)絡(luò)的能量負載平均到每一個節(jié)點上，從而降低能耗和延長網(wǎng)絡(luò)生存時間。但是LEACH算法存在一些不足，主要是由于簇首節(jié)點在整個網(wǎng)絡(luò)傳輸中擔負著重要角色，一旦簇首節(jié)點死亡則整個網(wǎng)絡(luò)就會出現(xiàn)數(shù)據(jù)丟失，產(chǎn)生監(jiān)控盲點［5］。本文提出了一種能夠有效提高簇首生存時間的算法，其與LEACH算法相比能夠更加有效的提高網(wǎng)絡(luò)的生存時間。

1 LEACH協(xié)議簡介

LEACH協(xié)議［6］是一種按層次分簇的自適應(yīng)路由算法，它將整個網(wǎng)絡(luò)節(jié)點分成不同的簇，并以簇首產(chǎn)生概率p在其中選出簇首節(jié)點，簇首節(jié)點負責收集簇內(nèi)節(jié)點的信息和簇間數(shù)據(jù)通信。并引入“輪”（round）的概念，通過周期性的簇重構(gòu)來避免簇首節(jié)點能量消耗過快，從而提高了整個網(wǎng)絡(luò)的生存時間。每一輪都包括2個階段：簇建立階段和數(shù)據(jù)傳輸階段。

簇建立階段：每個節(jié)點都產(chǎn)生一個0～1之間的隨機數(shù)，如果某個節(jié)點產(chǎn)生的隨機值小于設(shè)定的閾值T（n），則選擇該節(jié)點為簇首節(jié)點。式（1）是閾值T（n）的定義：T（n）=p1－p·（r mod1p），n∈G

0，其他

（1）式中：p為簇首節(jié)點在傳感器網(wǎng)絡(luò)節(jié)點中所占的百分比；r為當前所進行的輪次；G為上一輪選擇中未被選中為簇首的節(jié)點集合。當簇首選擇完成后，簇首節(jié)點使用CSMAMAC協(xié)議以相同能量對整個網(wǎng)絡(luò)進行廣播通知。網(wǎng)絡(luò)中的其他節(jié)點通過接收到廣播信號的強弱自主選則加入到哪個簇，并通知所屬簇首節(jié)點。之后，簇首節(jié)點產(chǎn)生一個TDMA進度表并在簇內(nèi)廣播，簇內(nèi)節(jié)點按照進度表分配的時隙與簇首節(jié)點進行通信。

數(shù)據(jù)傳輸階段：當整個網(wǎng)絡(luò)完成簇劃分并確定TDMA進度表后，即進入本輪的數(shù)據(jù)傳輸階段。簇首節(jié)點將接收到的簇內(nèi)節(jié)點采集的數(shù)據(jù)融合后，發(fā)送到基站。經(jīng)過一定時間的傳輸段后，進行新一輪的簇首選擇過程。

LEACH算法與一般的平面路由算法相比較，具有能量消耗明顯減少，整個網(wǎng)絡(luò)負載相對均衡的特點，從而延長了網(wǎng)絡(luò)的生存時間，據(jù)文獻［7］研究可提高30%左右的網(wǎng)絡(luò)生命周期。但LEACH算法的不足之處在于，一方面簇首的選擇沒有考慮到節(jié)點的剩余能量，這樣就會出現(xiàn)剩余能量少的節(jié)點被選成簇首的情況，從而導(dǎo)致這個簇首節(jié)點迅速死亡，造成網(wǎng)絡(luò)盲點。另一方面，當簇建立后簇首節(jié)點在無數(shù)據(jù)傳輸時仍然處于活躍狀態(tài)，能量白白消耗，降低了網(wǎng)絡(luò)的生存時間［8］。

2 改進的LEACH算法

針對LEACH算法的不足，考慮到簇首節(jié)點擔負著融合簇內(nèi)信息，并且發(fā)送至BS的任務(wù)，簇首節(jié)點的壽命在很大程度上影響了整個網(wǎng)絡(luò)的生存時間。在這里提出了兩點改進方法：

（1） 在簇首選擇時考慮節(jié)點剩余能量，避免能量低的節(jié)點被選為簇首節(jié)點；

（2） 在簇建立后，簇內(nèi)通信方式引入MD協(xié)議，從而起到減少簇首能量消耗，提高全網(wǎng)生存時間的作用。

2.1 無線傳感網(wǎng)絡(luò)模型說明

本文假定N個傳感器節(jié)點隨機均勻分布在一個二維平面區(qū)域內(nèi)，且具有如下性質(zhì)［9］：

（1） 傳感器節(jié)點布置后不再移動；

（2） 傳感器節(jié)點同構(gòu)，能量相同，且每一節(jié)點有惟一的標志ID，區(qū)域內(nèi)有惟一的基站（Base Station，BS）；

（3） 所有節(jié)點具有相似的處理能力（處理/通信），并且地位平等；

（4） 每一個節(jié)點都能與網(wǎng)絡(luò)中其他任何節(jié)點通信，也能與基站直接通信。

2.2 協(xié)調(diào)件協(xié)議

在MD協(xié)議（Mediation Device Protocol） 中［10］，使用MD節(jié)點接收網(wǎng)絡(luò)內(nèi)所有通信請求，其作用是預(yù)先使網(wǎng)絡(luò)內(nèi)節(jié)點進入睡眠狀態(tài)，當收到通信請求時喚醒網(wǎng)絡(luò)內(nèi)相應(yīng)節(jié)點進行數(shù)據(jù)傳輸，通過這種方法節(jié)約整個系統(tǒng)的能量消耗。MD協(xié)議不需要額外添加新的硬件，對節(jié)點電池壽命的影響也很小。

網(wǎng)絡(luò)中節(jié)點平均耗能表示為：E=μEa+（1-μ） *Es

（2）式中：E表示平均功耗，μ為節(jié)點工作占空比［11］（一個完整的喚醒周期包括休眠時段和監(jiān)聽時段，監(jiān)聽時段與喚醒時段的時間長度之比就是占空比。） Ea為活動狀態(tài)下的功耗， Es為待機狀態(tài)下的功耗。在實際應(yīng)用中，大多數(shù)時候Ea> >Es，所以可以通過降低占空比來延長網(wǎng)絡(luò)壽命，引入?yún)f(xié)調(diào)件協(xié)議就是在保持功耗最小化的同時實現(xiàn)穩(wěn)定的時間同步。

如果節(jié)點A需要傳輸數(shù)據(jù)到節(jié)點B，則A發(fā)送RTS（Request To Send）信標到MD節(jié)點，信標中包含目的節(jié)點B的地址和數(shù)據(jù)傳輸請求。MD節(jié)點向目的節(jié)點B發(fā)送喚醒信號。B節(jié)點收到喚醒信號后醒來并根據(jù)查詢信標等待一點時間接收數(shù)據(jù)，如果期間無數(shù)據(jù)傳輸則返回睡眠狀態(tài)，如果節(jié)點得到數(shù)據(jù)被收到的確認后，A和B均返回睡眠。使用MD節(jié)點使網(wǎng)絡(luò)中的節(jié)點只在有數(shù)據(jù)傳輸時網(wǎng)絡(luò)節(jié)點才會被喚醒，從而減少了節(jié)點能耗，延長了網(wǎng)絡(luò)的生存時間。

MD協(xié)議具有以下優(yōu)點：

（1） 進行數(shù)據(jù)傳輸?shù)墓?jié)點之間無需同步時間；

（2） MD協(xié)議是能量的消耗集中在MD節(jié)點上，其他節(jié)點大部分時間都處于睡眠狀態(tài)，而睡眠狀態(tài)期間主要的能量消耗只產(chǎn)生在收發(fā)周期性信標時。

2.3 簇首選擇階段

在網(wǎng)絡(luò)的初始階段，所有節(jié)點的能量都是相同的，但經(jīng)過幾個輪次后，節(jié)點的剩余能量會存在很大的不同，為避免能量低的節(jié)點被選擇成為簇首，導(dǎo)致整個網(wǎng)絡(luò)穩(wěn)定性下降，我們將節(jié)點剩余能量作為簇首選擇時的一個參數(shù)，來保證剩余能量多的節(jié)點被選擇成為簇首的概率加大。

Ecurrent表示當前節(jié)點剩余能量，Eoriginal表示節(jié)點的初始能量，r表示已經(jīng)過的輪次，v表示節(jié)點被選擇成為簇首的次數(shù)，令：λ=（r－v）EcurrentrEoriginal

（3）將式（3）引入LEACH算法簇首的閾值計算中，則改進的閾值計算公式變?yōu)椋篢（n）=p1－p（rmod1p）λ，n∈G

0，其他

（4） 通過加入節(jié)點的當前的剩余能量作為簇首的選擇條件，算法能夠有效地降低剩余能量較小的節(jié)點被選為簇首節(jié)點的幾率，避免了出現(xiàn)簇首節(jié)點迅速死亡造成網(wǎng)絡(luò)盲點的現(xiàn)象。

2.4 穩(wěn)定運行階段

在簇內(nèi)通信階段，簇首節(jié)點周期性地進入睡眠狀態(tài)，只有當接收到MD節(jié)點發(fā)來的喚醒信號才進入活躍狀態(tài)。此時簇首節(jié)點準備接收數(shù)據(jù)，簇內(nèi)節(jié)點在基于TDMA分配的時隙中與簇首節(jié)點進行數(shù)據(jù)傳輸。一旦簇首節(jié)點完成了數(shù)據(jù)收集，則將其融合后傳給BS。

當簇內(nèi)節(jié)點采集到數(shù)據(jù)后，該節(jié)點保存數(shù)據(jù)直至他所分配到的時隙來臨。此時其按照如下步驟進行數(shù)據(jù)傳輸：簇內(nèi)節(jié)點連續(xù)發(fā)送RTS（請求和發(fā)送）信標到MD節(jié)點，并等待RTS應(yīng)答；MD節(jié)點發(fā)送一個喚醒消息給簇首節(jié)點，消息中包含請求通信節(jié)點的地址；簇首節(jié)點收到MD節(jié)點的喚醒消息后，根據(jù)消息中的地址發(fā)送CTS（清除和發(fā)送）信標，傳輸開始；當?shù)玫较⒈皇盏降拇_認后，簇首節(jié)點返回睡眠狀態(tài)。在這里假定節(jié)點所分配的時隙足夠完成數(shù)據(jù)傳輸。通過這種方法盡可能多地使簇首節(jié)點保持睡眠狀態(tài)，從而減少了能量消耗。當簇首節(jié)點能量低于一定水平時，進行新一輪的簇首選舉過程。

如圖1所示，具體算法描述如下：

（1） 簇內(nèi)節(jié)點

當節(jié)點采集到數(shù)據(jù)并且當前是它所在的時隙時：

① 向MD節(jié)點發(fā)送RTS請求；

② 等待簇首節(jié)點發(fā)回的CTS；

③ 向簇首節(jié)點傳送數(shù)據(jù)；

④ 收到確認（ACK）信號。

（2） MD節(jié)點

當收到簇內(nèi)節(jié)點發(fā)來的RTS請求時，向簇首節(jié)點發(fā)送喚醒信標。

（3） 簇首節(jié)點

當收到喚醒信標：

① 向請求通信的節(jié)點發(fā)送CTS信號；

② 接收數(shù)據(jù)；

③ 傳輸完成后發(fā)回確認（ACK）信號；

④ 無通信請求返回睡眠狀態(tài)。

圖1 簇首節(jié)點在MD節(jié)點協(xié)調(diào)下的數(shù)據(jù)傳輸過程3 仿真與結(jié)果分析

3.1 仿真環(huán)境

為了驗證和評價改進后的算法性能，在這里使用Matlab軟件進行仿真。采用文獻［6］的無線通信系統(tǒng)模型，當發(fā)送方傳輸k比特的數(shù)據(jù)與距離為d的節(jié)點通信時，發(fā)送和接收方所消耗的能量分別為：

發(fā)送信息時的能耗：

ETx（k，d）=ETx-elec（k）+ETx-amp（k）

=Eelec×k+εfs×k×d2， d≤d0

Eelec×k+εmp×k×d4， d≥d0

（5）

接收時的能耗：ERx（k）=ERx－elec（k）

ERx（k）=Eeleck

（6）式中：Eelec表示發(fā)送和接收電路功耗；εfs表示當接收雙方的距離d小于閾值d0時的放大電路功耗；εmp表示當接收雙方的距離d大于或等于閾值d0時的放大電路功耗。整個網(wǎng)絡(luò)是在100 m×100 m的正方形監(jiān)測區(qū)域中隨機分布著100個無線傳感器節(jié)點，如圖2所示。具體仿真的試驗參數(shù)如表1所示。

3.2 實驗結(jié)果分析

延長網(wǎng)絡(luò)壽命的一個重要因素是如何能夠更有效地使用網(wǎng)絡(luò)中節(jié)點的能量。圖3分別對改進算法和LEACH的能耗情況進行了仿真對比。由圖3可以看出，改進的算法的能耗與LEACH算法的相比明顯降低，這是因為該進算法在成簇階段考慮到節(jié)點的剩余能量，避免了剩余能量較低的節(jié)點被選為簇首節(jié)點，在穩(wěn)定運行階段改進的算法簇首節(jié)點盡可能多的保持睡眠狀態(tài)從而降低了能量消耗。

網(wǎng)絡(luò)生命周期比較如圖4所示。在圖4中，將改進算法和LEACH的生命周期進行了對比。在相同的參數(shù)設(shè)置條件下，分別對2種算法對每輪過后網(wǎng)絡(luò)中存活節(jié)點數(shù)目進行統(tǒng)計，取200次仿真實驗中每輪存活節(jié)點數(shù)目的平均值?？梢钥闯觯倪M的算法比LEACH算法的網(wǎng)絡(luò)生命周期延長了約14%，有效的提高了網(wǎng)絡(luò)的工作效率。

本文針對無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點能量有限、能耗不均衡的問題，通過改進簇首選擇規(guī)則，引入?yún)f(xié)調(diào)件協(xié)議的有關(guān)算法，提出了一種在成簇階段有效降低剩余能量低的節(jié)點被選擇成為簇首，穩(wěn)定運行階段使簇首節(jié)點盡可能多的保持睡眠狀態(tài)，從而達到節(jié)約能量和提高整個網(wǎng)絡(luò)生存周期的改進算法。實驗結(jié)果表明，該算法相對于LEACH協(xié)議改進的算法在延長網(wǎng)絡(luò)生存時間方面取得了良好的效果。

參 考 文 獻

［1］ 孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京：清華大學出版社，2005.

［2］ FAN Xiangning， SONG Yulin. Improvement on LEACH protocol of wireless sensor network ＼[C＼]// Proceedings of the International Conference on Sensor Technologies and Applications. Valencia： ICSTA， 2007： 260264.

［3］ BUTT I， KHAN S. Analyzing enhancing energy efficient communication protocol for wireless microsensor networks ＼[C＼]// Proceedings of the International Conference. ＼[S.l.＼]： ICICT， 2005： 123129.

［4］ ABUHELALEH M， MISMAR T， ABUZNEID A. ArmorLEACHenergy efficient， secure wireless networks communication ＼[C＼]// Proc. of the ICCCN. ＼[S.l.＼]： ICCCN， 2008： 222227.

［5］ POTTIE G J， KAISER W J. Wireless intergated network sensors ＼[J＼].Communication. 2000， 43（5）： 5158.

［6］ HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN H. Energyefficient communication protocol for wireless microsensor networks ＼[C＼]// Proc.of the 33rd Annual Hawaii International Conf. on System Science. Maui， USA： IEEE Computer Society， 2000： 30053014.

［7］ IBBINI E. An efficient mechanism for saving energy of LEACH protocol in WSN ＼[D＼]. Jordan： Computer Science， Jordan University of Science Technology， 2010.

［8］ XUNBO L， NA L， LIANG C S， et al. An improved LEACH for clustering protocols in wireless sensor networks ＼[C＼]// Proceedings of the IEEE International Conference on Measuring Technology and Mechatronics Automation. ＼[S.l.＼]： IEEE， 2010： 111117.

［9］ 彭鐸，張秋余，賈科軍.能量高效的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.計算機工程，2009，35（17）：123126.

［10］ KARL H， WILLING A. Protocols and architecture for wireless sensor network ＼[M＼]. ＼[S.l.＼]： John Wiley and Sons， 2005.

［11］ AKYILDIZ I， SU W， SANKARASUBRAMANIAM Y， et al. A survey on sensor networks ＼[J＼]. IEEE Communications Magazine， 2002 （9）： 1118.

［12］ ELHOIYDI A. On the lifetime of wireless sensor networks ＼[J＼]. ACM Transactions on Sensor Networks， 2009， 5（1）： 3539.

作者簡介： 韓媛萍 女，1981年出生，貴州人，工程師，碩士。研究方向為無線通信技術(shù)。