無線傳感器網(wǎng)絡(luò)中能量有效分簇路由算法＊

周則順 李臘元 許 毅 高 玉

（武漢理工大學(xué)計(jì)算機(jī)學(xué)院 武漢 430063）

無線傳感器網(wǎng)絡(luò)（wireless sensor networks）是信息感知和采集技術(shù)最重要的技術(shù)之一，它部署靈活、維護(hù)簡單，廣泛應(yīng)用于軍事偵察、環(huán)境監(jiān)測、醫(yī)療監(jiān)護(hù)、農(nóng)業(yè)養(yǎng)殖和其他商業(yè)領(lǐng)域，以及空間探索和抗災(zāi)搶險等特殊領(lǐng)域.由于傳感器節(jié)點(diǎn)一般由電池供電，能量有限且不可補(bǔ)充，因此，在影響無線傳感器網(wǎng)絡(luò)生命周期的眾多因素中，節(jié)點(diǎn)的能量最為重要.同時，分簇算法與平面路由算法相比具有更好的能量有效性及可擴(kuò)展性［1］.文獻(xiàn)［2］中HEED選舉簇頭時考慮了剩余能量，但以主從關(guān)系引入了多個約束條件作用于簇頭的選舉過程，提高了協(xié)議的復(fù)雜度.本文提出了一種基于能量有效的分簇的路由算法（EECRA），該算法有效地平衡各節(jié)點(diǎn)的能量消耗，最大化整個網(wǎng)絡(luò)的生命周期.

1 EECRA的網(wǎng)絡(luò)描述

無線傳感網(wǎng)絡(luò)由N個隨機(jī)部署的節(jié)點(diǎn)組成，因此可有如下描述定義.

定義1設(shè)圖G＝（V，E）為簡單連通無向圖，當(dāng)且僅當(dāng)圖G為無自圈的、連通的無向圖；且G中任意2個節(jié)點(diǎn)之間最多有一條邊，其中V為所有節(jié)點(diǎn)構(gòu)成的頂點(diǎn)集合，E為所有鏈路構(gòu)成的邊集合.

定義2假定傳感器網(wǎng)絡(luò)G中各節(jié)點(diǎn)均具有相同的初始能量E0，對G中的任意節(jié)點(diǎn)v，可用E（v）表示節(jié)點(diǎn)v的當(dāng)前剩余能量；同時，節(jié)點(diǎn)具備數(shù)據(jù)融合功能，每個節(jié)點(diǎn)都有一個惟一的標(biāo)識（ID）.

定義3網(wǎng)絡(luò)中節(jié)點(diǎn)通信采用Heinzelman等人在文獻(xiàn)［2－3］中提出的無線通信模型.當(dāng)發(fā)送節(jié)點(diǎn)與接節(jié)點(diǎn)的距離小于閾值d0時，采用自由空間模型，即發(fā)送方發(fā)數(shù)據(jù)的能耗與距離的平方成正比，否則采用多路衰減模型，發(fā)送方發(fā)送數(shù)據(jù)的能耗與距離的四次方成正比.發(fā)送方發(fā)送kbit的數(shù)據(jù)到距離為d的接收方所消耗的能量為

式中：Eelec為發(fā)射電路的能耗；εfs，εmp分別為這2種模型中功率放大所需的能量.

2 EECRA的實(shí)現(xiàn)

EECRA算法是按輪運(yùn)行，每輪分為成簇階段和數(shù)據(jù)傳輸階段.在成簇階段首先將所有節(jié)點(diǎn)組織成簇，然后構(gòu)造路由樹，在數(shù)據(jù)傳輸階段把網(wǎng)絡(luò)采集的數(shù)據(jù)融合后傳遞到基站.為了減小簇頭節(jié)點(diǎn)的能量開銷，簇頭之間采用了多跳中繼的方式將采集的數(shù)據(jù)發(fā)送到基站.

2.1 簇及簇頭的選擇算法

EECRA為分布式競爭算法，簇首的選擇以節(jié)點(diǎn)與基站的距離及其鄰居節(jié)點(diǎn)的剩余能量中的最小為主要依據(jù).算法開始時，基站先以給定的功率向全網(wǎng)發(fā)送廣播信號BS＿message，節(jié)點(diǎn)根據(jù)接收到的信號強(qiáng)度計(jì)算出它到基站的距離di－BS，由該距離值得到自己的競爭半徑Ri，計(jì)算如下.

式中：c為控制取值范圍的參數(shù)，依網(wǎng)絡(luò)規(guī)模在［0，1］內(nèi)取值，其值確定后固定不變；dmax和dmin為節(jié)點(diǎn)到基站的距離的最大值和最小值；Rc為節(jié)點(diǎn)的最大競爭半徑.

每個節(jié)點(diǎn)將競爭半徑內(nèi)的區(qū)域作為自己的競爭區(qū)域，將競爭區(qū)域內(nèi)的所以其他節(jié)點(diǎn)看做是自己的鄰居.節(jié)點(diǎn)以半徑Rc廣播消息E＿message（ID，Eresidual）并根據(jù)鄰居節(jié)點(diǎn)發(fā)送的 E＿message消息更新鄰居表，得到其開始簇首競爭的時刻tc.

式中：μ為分布在［0.9，1］的隨機(jī)實(shí)數(shù)；T為事先規(guī)定的簇首競爭持續(xù)時間；ˉE為鄰居節(jié)點(diǎn)的平均剩余能量；Eresidual為節(jié)點(diǎn)的剩余能量.

若節(jié)點(diǎn)在競爭時刻到來之前已經(jīng)收到鄰居節(jié)點(diǎn)的簇首申明消息 HEAD－message（ID），則退出競爭并加入以鄰居節(jié)點(diǎn)為簇首的簇.否則，節(jié)點(diǎn)統(tǒng)計(jì)鄰居節(jié)點(diǎn)中已加入簇的節(jié)點(diǎn)數(shù)并與閾值k（t）進(jìn)行比較.當(dāng)節(jié)點(diǎn)數(shù)小于閾值k（t）時，節(jié)點(diǎn)廣播簇首申明消息宣布競爭成功.

閾值k（t）的計(jì)算公式如下

式中：t為當(dāng)前時間；m為全部鄰居節(jié)點(diǎn)數(shù).

2.2 簇成員加入簇算法

網(wǎng)絡(luò)的簇頭確定后，普通節(jié)點(diǎn)選擇合適的簇加入.普通節(jié)點(diǎn)選擇轉(zhuǎn)發(fā)功耗最小的簇頭作為自己的簇頭.首先所有的簇頭廣播自己的節(jié)點(diǎn)號和接收到Sink的信號強(qiáng)度，在簇頭通信半徑內(nèi)，普通節(jié)點(diǎn)接收并將簇頭信息存儲到自己的簇頭集合中，并依據(jù)信號強(qiáng)度計(jì)算自己經(jīng)過簇頭轉(zhuǎn)發(fā)到Sink的能量消耗（計(jì)算按照式（1））；選取轉(zhuǎn)發(fā)能量消耗最小的簇頭加入［4］.

簇首競爭結(jié)束后，鄰居節(jié)點(diǎn)中有多個簇首的節(jié)點(diǎn)加入距自己最近的簇以減少通信干擾，未加入簇的節(jié)點(diǎn)發(fā)送消息J＿JOIN＿message（ID，JumpID）至剩余能量最小的鄰居節(jié)點(diǎn)，通過該鄰居節(jié)點(diǎn)成為其他簇的多跳成員.

2.3 候選節(jié)點(diǎn)的處理

由無線通信模型可知，節(jié)點(diǎn)的傳輸能耗隨傳輸距離的增加顯著增大.為降低傳輸能耗，EECRA不僅采用基于樹結(jié)構(gòu)的多跳路由方式，而且在選擇路由候選節(jié)點(diǎn)時選擇距離自己較近的節(jié).因此，在簇生成后，每個簇首向全網(wǎng)廣播消息RELAY＿message（ID，Eresidual，di－BS），根據(jù)其他簇首發(fā)送的消息強(qiáng)度計(jì)算得到距其他簇首的距離，依據(jù)距離值選擇路由候選節(jié)點(diǎn).這里引入一個閾值DBS，若簇首節(jié)點(diǎn)si到基站的距離大于DBS，則路由候選節(jié)點(diǎn)集合為SCH（i）＝ ｛sj｜dj－BS≤di－BS且di－j≤kRi｝，其中k是使得sj存在的最小整數(shù)；否則路由候選節(jié)點(diǎn)集合為SCH（i）＝ ｛sj｜dj－BS≤di－BS且di－j≤Ri｝，當(dāng)且僅當(dāng)集合為空集（即沒有可用于數(shù)據(jù)中繼的路由候選節(jié)點(diǎn)）時，si將數(shù)據(jù)直接傳送至基站［5］.

為了均衡網(wǎng)絡(luò)能耗，避免節(jié)點(diǎn)由于能量消耗過多導(dǎo)致提前死亡，簇首節(jié)點(diǎn)應(yīng)當(dāng)在路由候選節(jié)點(diǎn)中選擇剩余能量較多的節(jié)點(diǎn)作為其中繼節(jié)點(diǎn).然而網(wǎng)絡(luò)能耗還與中繼節(jié)點(diǎn)的位置有關(guān)，僅考慮剩余能量選擇中繼節(jié)點(diǎn)往往會造成網(wǎng)絡(luò)能耗增大，因此選擇中繼節(jié)點(diǎn)時還需考慮節(jié)點(diǎn)位置.

假設(shè)通信采用式（1）中的自由空間模型，中繼節(jié)點(diǎn)sj直接與基站通信，則si通過sj傳輸l比特數(shù)據(jù)至基站時，節(jié)點(diǎn)si和sj的總能耗為

可以看出，d2i－j＋d2j－BS越小則傳輸總能耗越小.因此為減小網(wǎng)絡(luò)能耗，EHUC協(xié)議的路由樹構(gòu)造策略為：節(jié)點(diǎn)有多個路由候選節(jié)點(diǎn)時，從剩余能量最大的兩個節(jié)點(diǎn)中選擇d2i－j＋d2j－BS最小的節(jié)點(diǎn)作為中繼節(jié)點(diǎn).

3 算法的正確性和復(fù)雜度分析

性質(zhì)1整個網(wǎng)絡(luò)的控制消息復(fù)雜度為O（N）.

證明協(xié)議開始時，每個節(jié)點(diǎn)廣播一條E＿message消息.簇生成過程中，每個簇首廣播一條HEAD＿message消息，每個單跳簇成員最多廣播兩條JOIN＿message消息，每個多跳簇成員廣播一條J＿JOIN＿message消息.假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為N，生成簇首數(shù)為X，單跳簇成員數(shù)為Y，則多跳簇成員數(shù)為N－X－Y.在路由樹構(gòu)造過程中，每個簇首廣播一條RELAY＿M(jìn)SG消息［6］.因此網(wǎng)絡(luò)中總的控制消息開銷為

所以整個網(wǎng)絡(luò)的控制消息復(fù)雜度為O（N）.證畢

性質(zhì)2整個網(wǎng)絡(luò)中，節(jié)點(diǎn)的存儲開銷為O（N）.

證明協(xié)議中節(jié)點(diǎn)存儲開銷在于每個節(jié)點(diǎn)保存所有鄰居節(jié)點(diǎn)的信息以及簇首節(jié)點(diǎn)保存路由路徑里中繼簇首節(jié)點(diǎn)的信息.網(wǎng)絡(luò)模型為高密度靜態(tài)網(wǎng)絡(luò)，節(jié)點(diǎn)隨機(jī)分布在整個監(jiān)測區(qū)域A內(nèi)，由此可知節(jié)點(diǎn)si的鄰居數(shù)量期望為.其中：為網(wǎng)絡(luò)監(jiān)測區(qū)域的面積.同樣設(shè)協(xié)議生成X個簇，則每個簇首的鄰簇首數(shù)量期望最大為網(wǎng)絡(luò)中任一節(jié)點(diǎn)的存儲復(fù)雜度最大為

所以節(jié)點(diǎn)的存儲開銷為O（N）.證畢.

4 仿真實(shí)驗(yàn)結(jié)果分析

通過對LEACH和EECRA算法的仿真比較來評估算法的平均性能，在仿真實(shí)驗(yàn)中由改進(jìn)的NS2軟件包生成，無線通信模塊的參數(shù)與文獻(xiàn)［3］相同.節(jié)點(diǎn)數(shù)為300，主要比較了2種算法在不同網(wǎng)絡(luò)負(fù)載情況下的存活節(jié)點(diǎn)數(shù)量，平均能量消耗和網(wǎng)絡(luò)負(fù)載平衡值等方面對它們進(jìn)行性能對比.曲線上每點(diǎn)是40次仿真結(jié)果的平均值，每次仿真產(chǎn)生50次連接請求，請求產(chǎn)生服從呼叫的源節(jié)點(diǎn)和目的節(jié)點(diǎn)對以均勻的概率隨機(jī)地從節(jié)點(diǎn)中選取.

圖1為平均能量耗費(fèi)與網(wǎng)絡(luò)規(guī)模大小的關(guān)系，顯示了2種協(xié)議的網(wǎng)絡(luò)平均能量消耗情況，當(dāng)網(wǎng)絡(luò)通信負(fù)載較大時，所有協(xié)議的能耗都在增加，但是EECRA協(xié)議的能量消耗比LEACH少，這是由于負(fù)載較高時，所有協(xié)議的簇頭節(jié)點(diǎn)工作的時間都很長，而LEACH還存在調(diào)度開銷比EECRA要大.由圖還可以看出，EECRA的網(wǎng)絡(luò)能耗都低于LEACH，這是因?yàn)長EACH采用單跳通信方式，使得簇首與基站之間的遠(yuǎn)距離無線通信消耗了大量能量.EECRA都采用多跳通信來克服LEACH的不足，降低了網(wǎng)絡(luò)能耗，從而延長網(wǎng)絡(luò)的壽命.

圖2表示存活節(jié)點(diǎn)數(shù)量與時間關(guān)系，說明了EECRA協(xié)議在存活節(jié)點(diǎn)數(shù)量方面比LEACH要強(qiáng)，這是因?yàn)镋ECRA算法能夠根據(jù)簇成員數(shù)目和它們的負(fù)載動態(tài)地調(diào)整幀的長度，提高了信道的利用率，使節(jié)點(diǎn)的傳輸能量力增強(qiáng)，因而數(shù)據(jù)包的時間延遲較小，數(shù)據(jù)包接收率增大.

圖3表示網(wǎng)絡(luò)負(fù)載平衡值與網(wǎng)絡(luò)規(guī)模大小的關(guān)系，圖中結(jié)果可以看出，EECRA算法隨著網(wǎng)絡(luò)節(jié)點(diǎn)增加而負(fù)載平衡值基本不變，而LEACH算法的值波動相對較大，說明EECRA算法更加穩(wěn)定.

圖1 平均能量耗費(fèi)與網(wǎng)絡(luò)規(guī)模

圖2 存活節(jié)點(diǎn)數(shù)量與時間關(guān)系

圖3 網(wǎng)絡(luò)負(fù)載與網(wǎng)絡(luò)規(guī)模大小

5 結(jié)束語

文章分析了無線傳感器網(wǎng)絡(luò)路由協(xié)議的發(fā)展現(xiàn)狀，討論了各類路由協(xié)議的優(yōu)缺點(diǎn).從延長網(wǎng)絡(luò)生存時間的角度出發(fā)，提出一種能量有效分簇路由算法，為了縮短節(jié)點(diǎn)間的平均通信距離，在LEACH算法的基礎(chǔ)上提出了一種基于能量最小的分簇路由算法，此算法充分利用了分簇狀路由算法的優(yōu)點(diǎn)，通過高能量的基站完成諸多的高能耗任務(wù)，比如簇的建立、簇頭節(jié)點(diǎn)的選舉、路由機(jī)制的選擇等，因此算法取得了較好的節(jié)能效果，通過NS2進(jìn)行了仿真驗(yàn)證，EECRA算法相比LEACH算法和在能量有效性和能耗均衡方面具有更優(yōu)越的性能，更適合應(yīng)用于大規(guī)模的傳感器網(wǎng)絡(luò)，也更適合于未來無線傳感網(wǎng)面向?qū)嶋H應(yīng)用要求的通用結(jié)構(gòu)配置方案.

［1］李臘元，李春林.動態(tài)QoS多播路由協(xié)議［J］.電子學(xué)報.2003，9（9）：1 345－1 453.

［2］Soro S，Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering［J］.In：Proc.of the 19th IEEE Int＇l on Parallel and Distributed Processing Symposium.San Francisco：IEEE Computer Society Press，2005：236－240.

［3］Heinzelman W R，Chandrakasan A，Balakrishman H.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Trans.On Wireless Communications，2002，1（4）：660－670.

［4］李成法，陳貴海，葉 懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)學(xué)報，2007，30（1）：27－36.

［5］Chan H，Perrig A.ACE：An emergent algorithm for highly uniform cluster formation［C］／／Proc.of the 1st European Workshop on Sensor Networks（EWSN）.LNCS 2920，Berlin：Springer－Verlag，2004：154－171.

［6］劉 明，曹建農(nóng)，陳貴海，等.EADEEG：能量感知的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議［J］.軟件學(xué)報，2007，18（5）：1 092－1 109.