能量感知非均勻成簇路由優化算法

侯 華，宋 彬，周武旸

(1.河北工程大學 移動通信研究室，河北 邯鄲 056038；2.中國科學技術大學 無線信息網絡實驗室，安徽 合肥 230027)

能量感知非均勻成簇路由優化算法

侯 華1，宋 彬1，周武旸2

(1.河北工程大學 移動通信研究室，河北 邯鄲 056038；2.中國科學技術大學 無線信息網絡實驗室，安徽 合肥 230027)

無線傳感器網絡(WSN)具有的能量有限，其能量利用效率的高低直接影響著網絡的生命周期。為了提高無線傳感器網絡的能量利用效率，提出了一種能量感知非均勻成簇路由優化算法(Energy Awareness Unequal Clustering Routing Optimization Algorithm，EUCR)。該算法通過節點在網絡中所處的位置確定各節點的鄰居節點，并以局部能量選舉簇頭，各簇頭根據其鄰居節點構建非均勻分簇網絡。同時該算法在路由階段考慮了簇頭的剩余能量和轉發代價。仿真結果表明，EUCR算法能有效提高網絡的能量利用效率，并延長網絡的生命周期。

無線傳感器網絡；能量感知；非均勻分簇；多跳路由

無線傳感器網絡(Wireless Sensor Network，WSN)因其快速方便的部署特性和完備的監控能力被廣泛應用于軍事、救災、環境、醫療、智能家居等領域[1]。但由于傳感器節點采用電池供電的模式，且節點一旦部署之后，其電池不可更換，因此如何延長網絡的生命周期是WSN面臨的主要問題之一[2-3]。

以LEACH[4]和空間信息與梯度協議[5]為代表的分簇算法均衡了節點的能量消耗，但由于該類協議采用的都是單跳路由模型，因此在大規模網絡中所提算法涉及到的距離基站比較遠的節點能量消耗比較快，很容易使這類節點過早死亡。文獻[6-7]采用多跳的路由協議，克服了上述單跳路由模型中部分節點過早死亡的不足。但多跳路由模型容易出現能量空洞現象。

為了解決能量空洞問題，本文提出了能量感知非均勻成簇路由優化算法(EUCR)算法。該算法采用先尋找鄰居節點，再成簇的思想，提高了成簇效率。同時，EUCR算法通過局部能量選舉簇頭，使能量大的節點盡可能地當選為簇頭，提高了網絡的能量利用效率。在數據傳輸階段，EUCR算法將節點的剩余能量和轉發代價[7]的比值作為尋找路由的依據，使得選出的簇頭更適合擔當數據轉發任務。通過仿真驗證，該算法能有效地均衡網絡中各節點之間的能量消耗，延長網絡的生命周期。

1 系統模型

1.1 網絡模型

為了便于研究，本文作出如下假設：N個節點隨機地分布在一個正方形區域，網絡中的第i個傳感器節點用si表示，其中i={1,2,…,N}，基站位于正方形區域外的一側。節點一旦部署之后不可再移動，且每個節點在部署時都會被分配一個唯一的ID標識符。

1.2 能量消耗模型

本文采用與文獻[6]相同的能量消耗模型。傳感器節點將lbit的數據發送到與其距離為d的目的節點時需要消耗的能量為

(1)

節點接收lbit數據包需要消耗的能量為

ERX(l)=lEelec

(2)

式中：Eelec代表收發電路的損耗能量，εfs和εmp為放大器系數，d0表示臨界距離。當數據傳輸距離小于臨界距離d0時，采用自由空間模型，此時的能量消耗和距離的2次方成正比；當數據傳輸距離大于臨界距離d0時，采用多徑衰落模型，此時的能量消耗和距離的4次方成正比。d0的取值為

(3)

2 算法設計

2.1 簇頭選舉

在LEACH協議中，網絡中的每個節點產生一個隨機數，若隨機數大于簇頭選舉的閾值T(si)，則該節點就當選為簇頭。每個節點參加簇頭選舉的閾值為

(4)

由式(4)可以看出，在LEACH協議中，每個節點參加簇頭選舉的概率都為P。而在無線傳感器網絡中，隨著網絡的長時間運行，網絡中各節點的能量都會出現很大的差異，這時能量小的節點可能會被當選為簇頭，而簇頭的能量消耗要比簇內節點大很多，這會致使網絡中的節點能量更加不均衡。本文利用節點的當前能量和局部最大能量的比值作為簇頭選舉概率P的調節參數，增大了高能量節點當選為簇頭的概率。局部最大能量可由式(6)確定，在確定局部最大能量時，需要先尋找節點的鄰居節點，鄰居節點的確定在后文會有介紹。改進后的簇頭選舉概率Psi,CH如

(5)

(6)

式中：Psi,CH為網絡中的任意節點si參加簇頭選舉的概率；Esi為節點si的當前能量；ELocalMax為節點si的鄰居節點中的最大能量；NEIGHBORSsi為節點si的鄰居節點集。

改進后簇頭的選舉閾值可表示為

廣告商定義了產品的調性，消費者趨之若鶩，走進一些人滿為患的性冷淡風店鋪，嘗試一些沒多驚艷的網紅食品。錦鯉的獎品就是欲望的合集，獲得它，你就是擁有品位和運氣的女孩。

(7)

2.2 非均勻分簇算法

為了構建非均勻分簇網絡，本文提出了一個與節點在網絡中位置相關的節點成簇通信半徑Rsi·comp，即

(8)

式中：dmax為網絡中節點距基站的最遠距離；dmin為網絡中節點距基站的最近距離；dsi,BS為網絡中任意節點si距基站的距離。

在網絡啟用時的第一次成簇階段，網絡中的任意節點si在半徑為Rsi·comp的通信范圍內尋找自己的鄰居節點。首先，節點si隨機地退避一段時間，退避時間結束后，節點si發送廣播消息Node_Find_Neighbor_MSG尋找自己的鄰居節點，收到Node_Find_Neighbor_MSG消息的節點sj根據信號強度求得其與節點si的距離dsi,sj。為了保持網絡的連通性，本文規定只有當dsi,sj≤Rsi·comp且dsi,sj≤Rsj·comp時，節點sj才為節點si的鄰居節點，反之則不是。若節點sj為節點si的鄰居節點，則節點sj向節點si返回一個包含自己能量信息的確認消息Node_Neighbor_ACK_MSG。節點si收到確認消息Node_Neighbor_ACK_MSG后，會將節點sj記錄到自己的鄰居節點集NEIGHBORSsi中。鄰居節點集確定后，各節點按式(7)參加簇頭選舉。節點當選為簇頭后，該節點與其鄰居節點集就組成一個簇。對于同時屬于多個簇頭的鄰居節點，依據式(9)判斷其應加入哪個簇。

sj∈CCHsi:dsj,CHsi≤dsj,CHsk

(9)

式中：CHsi和CHsk為簇頭，sj為簇頭CHsi和CHsk的鄰居節點，CCHsi代表簇頭為CHsi的簇。

在網絡經歷了第一次成簇之后，網絡中的各個節點都保存了一個自己的鄰居節點集，由于每個節點的通信半徑是固定的，所以在網絡啟用時的第一次成簇階段，節點所確定的鄰居節點集即為該節點的最大鄰居節點集，當網絡中有節點死亡時，相應的節點就會從自己的鄰居節點集中刪除死亡節點。在本文中，每個節點和其鄰居節點集被稱為一個偽簇，在網絡第一次成簇之后的生存周期中，只要確定了簇頭，簇頭節點所確定的偽簇就自動升級為簇。這種先確定鄰居節點再分簇的方法相對于傳統的先確定簇頭再分簇的方法，減少了成簇階段所耗費的時間，同時也簡化了成簇的復雜度，提高了成簇的效率。

2.3 路由

本文在選擇下一跳路由時，對簇頭的通信范圍和簇頭到基站的距離等參數做了限制，同時從能量利用效率的角度考慮了下一跳路由的轉發代價。

(10)

3 算法評價

本文通過與LEACH和NEW-LEACH算法的仿真對比來評估EUCR算法的有效性和可行性。本文所有的仿真實驗在MATLAB環境下進行。在仿真實驗中，網絡為200 m×200 m正方形區域，基站位于(100，250)m處，節點總數為400個，節點的初始能量為0.5 J，Eelec為50 nJ/bit，εfs為10 pJ/(bit·m2)，εamp為0.001 3 pJ/(bit·m4)，數據包大小為4 000 bit，控制包大小為200 bit。

圖1為3種算法網絡生命周期的對比。其中LEACH，NEW-LEACH和EUCR算法中第1個節點的死亡時間分別為220，700和921，可見EUCR的網絡生命周期比NEW-LEACH的提高了32%，比LEACH的提高了319%。原因在于，在LEACH中，簇頭采用單跳的方式與基站進行數據交換，使距離基站較遠的簇頭能量消耗較大，導致其過早死亡。而NEW-LEACH和EUCR都采用多跳的通信方式與基站進行數據交換，延長了網絡的生命周期。由于EUCR算法采用的簇頭選舉策略和路由協議，比NEW-LEACH算法的更加合理，所以EUCR的網絡生命周期比NEW-LEACH要長。

圖1 網絡生存周期

本文以網絡中第1個節點的死亡時間和最后1個節點的死亡時間的比值作為網絡生存周期的能量平衡率。算法的能量平衡率越高，網絡的能量利用效率就越好。由圖2可知LEACH，NEW-LEACH和EUCR算法的能量平衡率分別為36%，52%，60%。其中LEACH的能量平衡率最低，EUCR的能量平衡率較NEW-LEACH有所提高。說明EUCR的能量利用效率最高，NEW-LEACH次之，LEACH的最差。

圖2 能量平衡率

本文對隨機選取的20輪簇頭能量消耗進行了對比，如圖3所示。其中，LEACH算法中的簇頭能量消耗波動較大，NEW-LEACH和EUCR兩種算法中的簇頭能量消耗波動較小。這說明NEW-LEACH和EUCR能更好地平衡簇頭之間的能耗。由圖3還可以看出，EUCR中簇頭的能耗最低，說明EUCR的簇頭能量利用效率最高。

圖3 簇頭的能耗

4 結論

本文提出的能量感知非均勻成簇路由優化算法由于只需在第一次啟用網絡時尋找一次鄰居節點，所以與其他傳統的算法相比提高了網絡的成簇效率。簇頭選舉策略和路由的改進，提高了網絡的能量利用效率。但本文提出的算法只考慮了網絡的局部能量消耗，使得選出的簇頭和路由不是最優的。下一步的工作，將考慮全局能量消耗對網絡的影響。

[1] KUILA P，GUPTA S K，JANA P K. A novel evolutionary approach for load balanced clustering problem for wireless sensor networks[J].Swarm and Evolutionary Computation，2013(12)：48-56.[2] YAN R，SUN Hanghang，QIAN Yuning.Energy-aware sensor node design with its application in wireless sensor networks[J]. IEEE Trans. Instrumentation and Measurement，2013，62(5)：118-1191.

[3] SUN Hanghang，QIAN Yuning，YAN Ruqiang.Design and realization of an intelligent sensor node with its application in energy-aware WSNs[C]//Proc. IEEE International Conference on Instrumentation and Measurement Technology. [S.l.]：IEEE Press，2012：941- 946.

[4] HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[EB/OL].[2014-12-12].IEEE Trans. Wireless Communications，2002，1(4)：660 - 670.

[5] 廖惜春，楊志高，任敬哲. 基于空間信息與梯度的WSN分簇路由算法[J].電視技術，2014，38(5)：120-123.

[6] LI Chengfa，YE Mao，CHEN Guihai，et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]//Proc. IEEE International Conference on Mobile Adhoc and Sensor Systems.[S.l.]：IEEE Press，2005：8- 604.

[7] 胡峰松，肖球.一種基于LEACH的能耗均衡多跳路由算法[J].小型微型計算機系統，2014(1)：70-73.

宋 彬(1987— )，研究生，研究方向為無線傳感器網絡；

周武旸(1972— )，博士，教授，博士生生導師， 研究方向為多載波技術跨層協議處理。

責任編輯：許 盈

Energy Awareness Unequal Clustering Routing Optimization Algorithm

HOU Hua1, SONG Bin1,ZHOU Wuyang2

(1.HebeiUniversityofEngineering,MobileCommunicationsResearchLaboratory,HebeiHandan056038,China;2.USTC,WirelessInformationNetworkLab,Hefei230027,China)

Wireless sensor networks (WSN) have limited energy, so its energy efficiency directly affects the life cycle of the network. In this paper, a new kind of energy awareness unequal clustering routing optimization algorithm (EUCR) is put forward. EUCR algorithm selects cluster head by local energy, and it expressly makes an optimization in clustering method and route. The simulation results show that EUCR can effectively improve the network energy efficiency, and prolong the life cycle of the network.

WSN; energy awareness; unequal clustering; multi-hop routing

【本文獻信息】侯華，宋彬，周武旸.能量感知非均勻成簇路由優化算法[J].電視技術,2015，39(13).

河北省高等學校科學技術研究重點項目(ZH2011222)

TP393

A

10.16280/j.videoe.2015.13.016

侯 華(1980— )，女，博士，副教授，研究生導師，研究方向為移動通信、無線通信和認知無線電技術；

2015-01-13