一種能量高效的分布式非均勻分簇路由算法*

孫彥景，林昌林，江海峰

(1.中國礦業大學信息與電氣工程學院，江蘇徐州221116；2.江蘇省煤礦電氣與自動化工程實驗室，江蘇徐州221008；3.中國礦業大學計算機科學與技術學院，江蘇徐州221116)

一種能量高效的分布式非均勻分簇路由算法*

孫彥景1，2*，林昌林1，江海峰3

(1.中國礦業大學信息與電氣工程學院，江蘇徐州221116；2.江蘇省煤礦電氣與自動化工程實驗室，江蘇徐州221008；3.中國礦業大學計算機科學與技術學院，江蘇徐州221116)

針對分布式分簇路由多跳通信方式中出現的“熱區”問題，在現有的分布式分簇路由協議的基礎上改進，并提出了能量均衡前行路由算法（EBFA）。該算法采用非均勻分簇和簇間多跳轉發策略，在多跳轉發階段，引入社會福利函數預先評估數據轉發路徑上節點間的能量均衡程度，選擇能量均衡程度較好的作為轉發節點。仿真結果表明：相比于LEACH和EEUC，此算法最大程度上延長了網絡的生存周期，較好地均衡了節點間的能量，解決了多跳路由中熱區的問題。

WSNs；非均勻分簇；社會福利函數；多跳轉發

無線傳感器網絡(Wireless Sensor Networks，WSNs)分簇路由協議按照控制方式可分為集中式路由協議［1-3］和分布式路由協議［4-10］。相比于集中式算法，分布式分簇路由協議只需獲得網絡的局部信息，并且具有良好的拓展性，適合大規模的WSNs網絡。在以分簇方式自組織的WSNs網絡中，節點被分為簇頭和簇成員，簇頭作為簇的中心負責簇的的構建，收集和融合簇成員新數據并轉發給基站，這使得簇頭的能量消耗速度遠遠高于其他簇成員。為解決這一問題，LEACH［4］協議采用隨機分簇和周期性簇頭輪換策略，把簇頭的負載分散到網絡中；文獻［5］［6］在LEACH的基礎上改進了分簇算法，將剩余能量、節點度等考慮在內，克服了LEACH中簇頭產生的隨機性，保證了簇頭的質量。上述協議中，簇頭與基站均采用單跳方式直接通信，遠離基站的簇頭具有較大的能耗，易造成這些節點較早失效。然而，在簇頭與基站采用多跳方式通信的網絡中，距離基站較近的節點由于需要大量轉發其他簇頭的數據給基站，能耗較高，也容易較早失效，影響整個網絡的性能。

因此分簇路由中無論采用單跳或多跳方式轉發數據，簇首間能耗不均衡的問題仍然存在。針對這一問題，UCS［7］采用了非均勻分簇和簇間多跳的思想，在簇頭產生后首先構造簇間多跳路由，根據期望轉發負荷，通過調整簇的大小的方式，減小簇頭間能耗的差距，解決能耗不均衡的問題；EEUC［8］則根據距基站的遠近來調整簇的大小，距基站較近的簇具有較小的規模，從而節省能量用來轉發其他簇頭的數據。以上方法通常是在評估當前網絡狀態后做出選擇，對于節點執行后的網絡狀態沒有預先考慮。

因此，本文在EEUC非均勻分簇的基礎上，對簇頭的產生和多跳路徑的建立進行了改進，依據經濟學領域度量收入分配不平等程度的社會福利函數預先評估下一跳中繼節點選擇后的網絡狀態，從而選擇下一跳簇頭節點，提出能量均衡前行算法(Energy Balanced Forwarding Algorithms，EBFA)，解決多跳通信方式中節點的能耗不均衡的問題，以延長WSNs網絡的生存時間。

1 網絡模型與假設

1.1 網絡模型和定義

本文中路由協議的應用場景為周期性數據收集，即在一個M×M二維正方形區域A的隨機部署N個傳感器節點，區域A中的傳感器節點定時地將采集到的數據（如溫度，濕度和氣壓等）匯聚到基站。假設該網絡有如下幾個特性：①基站（匯聚節點）位于一個正方形監測區域A的外側，地理位置固定，計算能力較強，能量不受限制；②所有節點結構相同，隨機分布在監測區域內，具備數據融合功能和唯一的標識(ID)，并且能保證時間同步；③鏈路是對稱的。若已知對方發射功率，節點可以根據接收信號的強度計算出發送者到自己的近似距離；④節點可以根據與接收者的傳輸距離，自由調整其通訊功率，既能滿足通訊的需求，也可以節省節點的能量消耗。

1.2 無線通信能耗模型

本文采用與文獻［4］相同的無線通信能耗，在該模型中，發送端所消耗的能量用于無線電通信發送和功率放大兩部分，而接收端消耗的能量僅僅用于無線電通信接收。該模型如1圖所示。

圖1 無線通信模型

無線信號的能量衰減根據接收端和發送端的距離的不同，分別使用Friss自由空間模型(Friss Free Space Model)和多徑衰落信道模型(Multi-path Fading Channel Model)。若兩者間的距離小于d0使用自由空間模型，傳播能量損失與d2成反比；若距離大于d0則使用多徑衰落信道模型，傳播能量損失與d4成反比。為了保證接收方正常接收數據，發送方必須具有功率控制能力，以抵消無線信號在傳播過程中的能量損耗。因此，發一個l比特的數據包到距離發送端d的節點需要消耗的能量為：

而接收到這個數據包需要消耗的能量為：

本文考慮簇內數據有較大冗余，可以數據融合，簇間轉發則不考慮數據融合。數據融合消耗的能量EDA為5 nJ·bit-1·signal-1，εfs為10 pJ·bit-1·m-2，εmp為0.001 3 pJ·bit-1·m-4），Eelec為50 nJ·bit-1，d0=87 m。

2 算法詳述

EBFA協議采用經典的輪循機制，每一輪包括四個階段：簇頭競爭，簇間多跳路由路徑建立，簇的形成和穩定階段。

2.1 簇首競爭算法

EBFA協議在簇頭競選階段采用計時廣播［9］代替EEUC的協商機制。為了控制候選簇頭的比例，網絡中的節點在每輪開始時以概率T選擇自己作為候選簇頭，其他節點則進入休眠狀態直到被喚醒。候選簇頭Vi根據公式計算等待時間ti，等待時間ti到達則廣播FINAL_HEAD_MSG消息，宣布自己成為簇頭，在其競爭范圍內的其他簇頭則退出競選。

式中：λ是在0.9～1.0之間的隨機數，用于避免廣播消息發生沖突；TCH是預先定義的簇頭競爭所需要的最大時間；Ei是Vi的剩余能量；E0是Vi節點的初始能量。根據上述公式，廣播時間ti很大程度上取決于節點的剩余能量。如果節點比其所處區域的其他節點具有較大的能量，則它成為簇頭的等待時間較短，概率較大。但是，當網絡運行了相當一段時間之后，所有節點的剩余能量Ei變得非常低，等待時間ti則會變得相當大。為此我們又改進了ti的計算方法：

這樣，等待時間會在（0.5～1.0）TCH之間變化，盡可能地減少了網絡的延時。根據公式，在簇頭的競爭的競爭階段，只有少量候選簇頭廣播競選成功消息，這樣在簇頭競選階段候選簇頭之間的通信減少，可以有效減少簇頭的通信消耗。

簇頭選舉的偽代碼如下：

同時，每個候選簇頭設置一個競爭范圍Rcomp，它是該節點與基站距離的函數［8］，用于控制簇頭在網絡中的分布。假設是預先定義的最大競爭半徑，候選簇頭Vi的Rcomp為：

式中：dmax和dmin分別代表節點和基站的最大距離和最小距離，d(Vi，BS)代表Vi和基站的距離，c是位于0和1之間的常數。根據上述公式，候選簇頭的競爭范圍在(1-c)到之間變化，并且隨著候選簇頭到基站距離的減小，其競爭半徑應該隨之減少。因此距離基站較近的區域選舉簇頭簇頭較多，簇的幾何尺寸也較小。較小的幾何尺寸是為了減少簇內通信消耗，節省下來的能量則用于簇間轉發，避免過早死亡。

下圖給出了一張候選簇頭的競爭示意圖，其中圓圈表示候選簇頭的競爭區域。由公式可知，V1和V2不互為鄰居節點，V3位于V4的競爭范圍內，而V4不位于V3的競爭范圍，所以V1和V2可以同時成為簇頭，當V4首先成為簇頭后，V3則不能成為簇頭。

圖2 候選簇頭的競爭區域

2.2 簇間多跳路由協議

EBFA協議采用簇內單跳和簇間多跳相結合的數據傳輸方式。每個成功競選的簇頭選擇其他簇頭作為中繼節點，轉發數據分組至基站，這就需要提前建立多跳傳輸路徑。我們假設數據冗余度有限，中繼節點無法融合其他簇頭和自身數據，只能簡單轉發來自其他簇頭的數據。

首先，競選成功的簇頭CHi(i=1，2，3，4，...，K，K為簇頭數量)，已經廣播一條FINAL_HEAD_MSG消息，廣播功率覆蓋xi,yi倍簇頭競爭半徑范圍內的節點。這條消息包括簇頭ID，剩余能量Ei，競爭半徑Rcomp和到基站距離dtoBS等。簇頭CHi接收到簇頭CHj信息后，計算CHi到CHj的大概距離，建立一個候選中繼節點信息表，如表1所示：在多跳路由建立過程中，簇首CHi的中繼候選節點集合N(i)為：

式中：k∈［1，3］，k取值越大，中繼候選節點集合中節點越多。簇頭CHi運用貪婪算法在其候選中繼集合中，選擇其中中繼節點N(i)，中繼節點N(i)在所有候選節點中具有最小的代價函數。

代價函數參考阿特金森福利函數設計［11］。社會福利函數是經濟學領域度量收入分配不平等程度的一種方法，社會收入差距越小，阿特金森指數值也就越小。阿特金森指數值的取值范圍為［0，1］，其中0代表了社會達到了收入的完全公平分配。代價函數如下：

EUB描述了節點在單跳通信可達區域范圍H內的能量平衡狀態，其中n是區域內的節點的個數，E(i)表示節點的剩余能量，Eˉ表示區域內所有節點的平均剩余能量。nj≥2,j=1,2,3,4是不平等厭惡指數，在0到正無窮取值，常用的取值為1.5、2.0、2.5。

在選擇中繼節點時，簇頭CHi運用貪婪算法在其候選簇頭節點中，計算將數據傳給其中一個候選中繼節點的EUB的預測值，最終代價函數值最小的一個候選中繼節點將作為中繼節點。詳述其過程：我們假定將候選中繼節點k作為下一跳的中繼節點，并假設將數據分組傳給候選中繼節點k，我們能計算出候選中繼節點k預期中的剩余能量為：

候選中繼節點k接收到數據分組后，還要將數據分組傳送給基站，則它預期中的剩余能量為：

而其他的候選中繼節點則沒有消耗能量，它們的剩余能量為：

根據上述公式，估算作為當前CHi節點的候選中繼節點集合N(i)中每一個節點的EUBik，即阿特金斯福利指數：

其中

當前節點CHi從中繼節點集合N(i)中選擇阿特金斯福利指數EUBik最小的節點作為下一跳節點。

下面對此代價函數做幾點說明：

①單跳通信可達區域范圍H即可與簇頭通信的候選中繼節點集合，候選中繼節點到基站都比簇頭到基站的距離小，最終的中繼節點都是從候選中繼節點選取出來的，所以每一跳數據分組都是向基站方向單向流動。不可能出現為了消除區域內的能量不平衡狀態，數據分組在一個回路上反復轉發；②多跳路由的最終目的是將數據轉發到基站，供用戶使用。有兩種情況簇頭會將數據發送給基站，完成多跳路由的建立：一是簇頭距離基站較近，候選中繼節點為空；二是假若基站在簇頭可通信范圍(本文中簇頭的可通信范文半徑為)內，預先評估將數據分組直接發送給基站的EUB值，若其代價函數最小則簇頭發送給基站。

2.3 分簇算法

簇間的多跳路徑建立完成后，簇頭廣播公告消息，普通節點從休眠狀態被喚醒，進入分群階段。公告消息是控制信息短消息，包含發送節點的ID，剩余能量（簇間轉發后的預期值）和到基站距離等，消息的廣播半徑是簇頭競爭半徑的δ倍，其中δ∈［1，3］。每個普通節點按照以下方法確定自己本輪的簇頭：節點接收簇頭的廣播信息后，在競爭半徑覆蓋到自己的幾個簇頭中，選擇剩余能量較大的節點加入；若沒有簇頭覆蓋到自己，則主動廣播請求消息并加入首先回復確認消息的簇頭。

2.4 穩定階段

穩定階段，非簇頭的無線通訊模塊關閉，直到分配的傳輸數據時間到來，這樣可以節約節點能量。簇首完成所有節點數據收集后，進行數據融合，然后經由簇間多跳路由傳送數據至基站。

3 仿真結果及分析

為了驗證EBFA協議的性能，利用MATLAB在相同條件下仿真LEACH、EEUC和EBFA協議并對比多項性能。仿真參數如表1所示，其中網絡參數取自文獻［8］，協議中的參數通過運行多次實驗來找出其最優值。

表1 網絡環境與參數

3.1 簇頭數量

在網絡拓撲結構相對穩定的情況下，一個優秀的分簇算法每輪選出的簇頭數量應該比較穩定，集中于簇頭數量最優值的附近，以優化網絡的結構。在沒有任何節點死亡的情況下，圖3比較了LEACH、EEUC和EBFA路由協議算法隨機選取的100輪種的簇頭數量的分布情況。

圖3 簇頭的數量分布統計

由圖3可見，LEACH的簇頭數量波動范圍較大，而EEUC和EBFA的波動范圍較小，其中EBFA產生的簇頭成正態分布更為穩定。這樣的結果與算法的簇頭選舉算法密切相關，LEACH的簇頭選舉采用隨機數和閥值的控制機制，難以控制每輪生成的簇頭數量，而EEUC和EBFA采用了候選簇頭局部競爭的方法，所生成的簇頭的數量得到很好的控制，并使之分布于簇頭最優數量作于很小的鄰域內。相比EEUC，EBFA采用計時廣播的方式代替了競爭協商，減少了用于控制信息的開銷；并且EBFA不再維護候選簇頭的鄰居候選節點，競選成功的簇頭只需要通知其競爭半徑范圍的其他候選推出競選。

3.2 網絡生命周期

本協議的思想之一就是利用非均勻分簇的思想來解決熱點問題，延長網絡的存存時間。下面首先通過網絡生存周期來驗證3種協議的能量有效性。

圖4顯示了存活節點數隨著仿真周期的變化情況。從圖中可以看出，本協議相對于LEACH和EEUC明顯提高了網絡生存周期。由于采用了非均勻分簇和簇間多跳路由有機結合的方式，本協議有效地平衡了靠近基站的簇和遠離基站的簇之間的數據傳輸能耗。LEACH的網絡生命周期與另外兩種協議相差很大這是因為LEACH只適合小型網絡不適合本文仿真的網絡環境。相比于EEUC，本協議采用計時廣播方式代替協商機制，有效減少了簇頭競爭階段的通信耗能；并且依據阿特金森福利函數建立的簇間優化路由不僅有效的平衡了不同位置簇頭的能耗，也減少了網絡的整體能量消耗。

圖4 三種協議存活節點數隨著時間的變化曲線

表2是三種協議的網絡生命周期。EBFA與LEACH、EEUC相比，在LT1上分別提高了169.3%和54.5%，在LT2上分別提高了90.8%和39.4%，網絡生命周期最大程度上得到延長。

表2 網絡生命周期

3.3 網絡的能量均衡性

本文主要從節點剩余能量方差、節點剩余能量分布和死亡節點分布來衡量網絡的能量均衡性［12］。

圖5 網絡節點剩余能量方差變化曲線

圖5給出了三種協議節點能量方差隨時間變化的比較，本協議的網絡節點能量方差一直都很低變化不大，表明本協議能有效的均衡網絡及節點能量，從圖5可以看出，LEACH簇頭的產生具有隨機性，且不同位置的簇頭能量消耗差異很大，所以均衡性較差；EEUC采用非均勻分簇的思想來平衡簇頭之間的能耗，達到了較好的均衡效果；EBFA協議同樣采用非均勻分簇，但能量均衡性能表現最好，這說明通過福利函數評價建立的簇間多跳路徑在平衡能量消耗方面發揮了較好的作用。

本文還比較了節點剩余能量的分布情況。圖6中三圖是當網絡中第一個節點死亡時，網絡中所有節點剩余能量的數量分布，直觀顯示了網絡中節點之間剩余能量的差距。LEACH協議中，當第一個節點死亡時，仍有大量節點剩余較多的能量，能量均衡性較差；EEUC中引入非均勻分簇的多跳路由機制，較好解決了這個問題，當第一個節點死亡時，沒有節點仍剩余較多能量，其他節點剩余能量差距不大；EBFA中，當網絡中出現第一個死亡節點時，網絡已經運行了相當一段時間，并且節點剩余能量都都在20%左右，節點間的能量均能最好。

圖6 剩余節點能量分布

圖7中三圖是網絡中死亡節點到達20%時，死亡節點的分布情況，圖中‘o’代表存活節點，‘x’表示死亡節。從圖中我們可以看出：LEACH死亡節點全都集中在距離基站較遠的區域，這是因為它們需要消耗大量能量轉發簇內節點收集的信息，EEUC則由于靠近基站的節點承擔過量的轉發任務而大量死亡，EBFA協議很好地解決了能量均衡性的問題，死亡節點分布比較均勻，網絡未出現嚴重的“能量空洞”現象。

圖7 死亡節點分布圖

4 總結

本文汲取EEUC非均勻分簇和簇間多跳路由的算法思想，提出了改進的分布式非均勻分簇路由算法，即EBFA。EBFA協議在簇頭競爭階段采用計時廣播機制，降低了控制消息的開銷；簇間多跳的建立引入依據社會福利函數設計的代價函數，優化了中繼節點的選擇。仿真結果表明，EBFA能夠有效均衡網絡能量消耗，延長網絡的生命周期。

［1］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4)：660-670.

［2］雷霖，李偉峰，王厚軍.基于遺傳算法的無線傳感器網絡路徑優化［J］.電子科技大學學報，2009，38(2)：227-230.

［3］陳曉娟，王卓，吳潔.一種基于LEACH的改進WSN路由算法［J］.傳感技術學報，2013(1)：116-121.

［4］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000.IEEE，2000：10 pp.vol.2.

［5］Younis O，Fahmy S.Distributed Clustering in Ad-Hoc Sensor Networks：A Hybrid，Energy-Efficient Approach［C］//INFOCOM 2004.Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE，2004，1.

［6］蔡鑌，陳向東，楊英.節點密度自適應的傳感器網絡加權分簇算法［J］.傳感技術學報，2009，22(4)：558-562.

［7］Soro S，Heinzelman W B.Prolonging the Lifetime of Wireless Sensor Networks Via Unequal Clustering［C］//Parallel and Distributed Processing Symposium，2005.Proceedings.19th IEEE International.IEEE，2005：8.

［8］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007，30(1)：27-36.

［9］蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網絡非均勻分簇路由協議［J］.軟件學報，2012，23(5)：1222-1232.

［10］曾華圣，熊慶宇，杜敏，等.一種分布式能量高效的WSNs非均勻分簇路由協議［J］.傳感器與微系統，2014，33(3)：146-149.

［11］Jiang H，Sun Y，Sun R，et al.Fuzzy-Logic-Based Energy Optimized Routing for Wireless Sensor Networks［J］.International Journal of Distributed Sensor Networks，2013.

［12］黃丹.無線傳感器網絡分簇路由協議研究［D］.大連：大連海事大學，2013.

孫彥景(1977-)，男，山東滕州，博士，教授，博士生導師，主要研究領域為礦井無線通信與監控，礦山物聯網等，yanjingsun_cn@163.com；

林昌林（1990-），男，碩士研究生，主要研究領域為無線通信和自組織網絡，mymail1991@163.com

An Energy Efficient Distributed Uneven Clustering Routing Algorithm for WSNs*

SUN Yanjing1，2*，LIN Changlin1，JIANG Haifeng3
(1.School of Information and Electrical Engineering，China University of Mining and Technology，Xuzhou Jiangsu 221116，China；2.Coal Mine Electrical Engineering and Automation Laboratory in JiangSu Province，Xuzhou Jiangsu 221008，China；3.School of Computer Science and Technology，China University of Mining and Technology，Xuzhou Jiangsu 221116，China)

To solve the"hot zone"problem appearing in distributed clustering routing multi-hop communication，this paper proposes an energy balanced forwarding algorithm(EBFA)based on distributed clustering routing protocols.EBFA adopts the uneven clustering techniques and multi-hop inter-cluster strategy.During the multi-hop forwarding，the social welfare function is introduced to pre-assess the extent of energy balance between nodes in the data forwarding path，and the node with a better energy balance is chosen as the forwarding node.Simulation results show that：Compared to LEACH and EEUC，EBFA prolongs the lifetime of the network and balances the energy consumption among sensor nodes，which solves the hot zone problem in the multi-hop routing.

WSNs；uneven clustering；social welfare function；multi-hop forwarding

TP92

A

1004-1699(2015)08-1194-07

??7230；6150P

10.3969/j.issn.1004-1699.2015.08.016

項目來源：國家自然科學基金面上項目(51274202)；中央高?；究蒲袠I務費專項資金項目(2013RC11)；江蘇省科技成果轉化項目(子課題)(BA2012068)；江蘇省自然科學基金面上項目(BK20130199，BK20131124)；江蘇省產學研前瞻性聯合研究項目(BY2014028-01)；中國礦業大學重大項目培育專項(2014ZDPY16)

2015-02-12 修改日期：2015-05-28