無線傳感器網絡中能量有效分簇路由算法＊

周則順 李臘元 許 毅 高 玉

（武漢理工大學計算機學院 武漢 430063）

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

1 EECRA的網絡描述

無線傳感網絡由N個隨機部署的節點組成，因此可有如下描述定義.

定義1設圖G＝（V，E）為簡單連通無向圖，當且僅當圖G為無自圈的、連通的無向圖；且G中任意2個節點之間最多有一條邊，其中V為所有節點構成的頂點集合，E為所有鏈路構成的邊集合.

定義2假定傳感器網絡G中各節點均具有相同的初始能量E0，對G中的任意節點v，可用E（v）表示節點v的當前剩余能量；同時，節點具備數據融合功能，每個節點都有一個惟一的標識（ID）.

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

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

2 EECRA的實現

EECRA算法是按輪運行，每輪分為成簇階段和數據傳輸階段.在成簇階段首先將所有節點組織成簇，然后構造路由樹，在數據傳輸階段把網絡采集的數據融合后傳遞到基站.為了減小簇頭節點的能量開銷，簇頭之間采用了多跳中繼的方式將采集的數據發送到基站.

2.1 簇及簇頭的選擇算法

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

式中：c為控制取值范圍的參數，依網絡規模在［0，1］內取值，其值確定后固定不變；dmax和dmin為節點到基站的距離的最大值和最小值；Rc為節點的最大競爭半徑.

每個節點將競爭半徑內的區域作為自己的競爭區域，將競爭區域內的所以其他節點看做是自己的鄰居.節點以半徑Rc廣播消息E＿message（ID，Eresidual）并根據鄰居節點發送的 E＿message消息更新鄰居表，得到其開始簇首競爭的時刻tc.

式中：μ為分布在［0.9，1］的隨機實數；T為事先規定的簇首競爭持續時間；ˉE為鄰居節點的平均剩余能量；Eresidual為節點的剩余能量.

若節點在競爭時刻到來之前已經收到鄰居節點的簇首申明消息 HEAD－message（ID），則退出競爭并加入以鄰居節點為簇首的簇.否則，節點統計鄰居節點中已加入簇的節點數并與閾值k（t）進行比較.當節點數小于閾值k（t）時，節點廣播簇首申明消息宣布競爭成功.

閾值k（t）的計算公式如下

式中：t為當前時間；m為全部鄰居節點數.

2.2 簇成員加入簇算法

網絡的簇頭確定后，普通節點選擇合適的簇加入.普通節點選擇轉發功耗最小的簇頭作為自己的簇頭.首先所有的簇頭廣播自己的節點號和接收到Sink的信號強度，在簇頭通信半徑內，普通節點接收并將簇頭信息存儲到自己的簇頭集合中，并依據信號強度計算自己經過簇頭轉發到Sink的能量消耗（計算按照式（1））；選取轉發能量消耗最小的簇頭加入［4］.

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

2.3 候選節點的處理

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

為了均衡網絡能耗，避免節點由于能量消耗過多導致提前死亡，簇首節點應當在路由候選節點中選擇剩余能量較多的節點作為其中繼節點.然而網絡能耗還與中繼節點的位置有關，僅考慮剩余能量選擇中繼節點往往會造成網絡能耗增大，因此選擇中繼節點時還需考慮節點位置.

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

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

3 算法的正確性和復雜度分析

性質1整個網絡的控制消息復雜度為O（N）.

證明協議開始時，每個節點廣播一條E＿message消息.簇生成過程中，每個簇首廣播一條HEAD＿message消息，每個單跳簇成員最多廣播兩條JOIN＿message消息，每個多跳簇成員廣播一條J＿JOIN＿message消息.假設網絡節點數為N，生成簇首數為X，單跳簇成員數為Y，則多跳簇成員數為N－X－Y.在路由樹構造過程中，每個簇首廣播一條RELAY＿MSG消息［6］.因此網絡中總的控制消息開銷為

所以整個網絡的控制消息復雜度為O（N）.證畢

性質2整個網絡中，節點的存儲開銷為O（N）.

證明協議中節點存儲開銷在于每個節點保存所有鄰居節點的信息以及簇首節點保存路由路徑里中繼簇首節點的信息.網絡模型為高密度靜態網絡，節點隨機分布在整個監測區域A內，由此可知節點si的鄰居數量期望為.其中：為網絡監測區域的面積.同樣設協議生成X個簇，則每個簇首的鄰簇首數量期望最大為網絡中任一節點的存儲復雜度最大為

所以節點的存儲開銷為O（N）.證畢.

4 仿真實驗結果分析

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

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

圖2表示存活節點數量與時間關系，說明了EECRA協議在存活節點數量方面比LEACH要強，這是因為EECRA算法能夠根據簇成員數目和它們的負載動態地調整幀的長度，提高了信道的利用率，使節點的傳輸能量力增強，因而數據包的時間延遲較小，數據包接收率增大.

圖3表示網絡負載平衡值與網絡規模大小的關系，圖中結果可以看出，EECRA算法隨著網絡節點增加而負載平衡值基本不變，而LEACH算法的值波動相對較大，說明EECRA算法更加穩定.

圖1 平均能量耗費與網絡規模

圖2 存活節點數量與時間關系

圖3 網絡負載與網絡規模大小

5 結束語

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

［1］李臘元，李春林.動態QoS多播路由協議［J］.電子學報.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］李成法，陳貴海，葉 懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，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］劉 明，曹建農，陳貴海，等.EADEEG：能量感知的無線傳感器網絡數據收集協議［J］.軟件學報，2007，18（5）：1 092－1 109.