基于能耗均衡的均勻分簇算法研究

雷宇飛，簡必建

(泉州信息工程學院，福建泉州 362000)

無線傳感器網絡(WSN)是由大量廉價的、低成本的感知設備組成的網絡。具有實時性、低能耗、低成本、低速率、自適應等特點，由于能量由一次性微型電池供應，因此能量有限成為了WSN的最大限制，而通信部分消耗的能耗最大[1]，所以如何設計能量高效的路由協議是無線傳感器網絡的關鍵問題之一。

無線傳感器網絡路由協議是面向應用的，不同的應用場合有著不同的路由協議，隨著無線傳感器網的發(fā)展，近年來國內外學者提出了大量的路由協議。根據網絡拓撲結構的不同，路由協議分為平面路由協議和分簇路由協議。研究表明，無線傳感器網絡采用分簇的路由協議以及簇間通過多跳轉發(fā)發(fā)送數據能夠明顯地降低網絡能耗[2-3]。因此，近年來學者們提出了許多能量高效的分簇路由協議。分簇算法根據成簇階段簇的形成方式的不同，分為均勻分簇算法和非均勻分簇算法，主要的均勻分簇算法有LEACH算法、LEACH-C和HEED協議[4]等，該類協議將目標區(qū)域劃分為大小相同的小區(qū)域，每個區(qū)域中有且只有一個簇頭節(jié)點，普通節(jié)點只能和所在區(qū)域的簇頭進行數據傳輸，最后由簇頭節(jié)點將數據發(fā)送至網關節(jié)點。其中，LEACH算法是典型的低功耗自適應的分簇算法，能有效地提高節(jié)點的能量效率，是一種高效的路由協議。主要的非均勻分簇算法有UCS協議[5]、EEUC協議[6]等，此類協議的基本思想是將網絡的區(qū)域根據節(jié)點距離網關節(jié)點的遠近不同，劃分為大小不一的簇，遠離網關節(jié)點的簇的規(guī)模較大，更多地承擔收集采樣數據的功能，靠近網關節(jié)點的簇則更多地擔任數據轉發(fā)的任務，通過多跳的方式將數據傳輸至網關節(jié)點，從而實現全局范圍內簇頭節(jié)點能耗的均衡。

1 LEACH算法與問題分析

1.1 LEACH協議

LEACH[7](Low Energy Adaptive Clustering Hierarchy)是MIT研究人員A.Chandrakasan等為無線傳感器網絡設計的低功耗的自適應分簇路由協議。它打破了原有成簇算法中固定簇頭的思想，采用本地簇頭隨機輪流當選簇頭的機制將能量負載均勻分布到網絡中的所有節(jié)點，提高了網絡壽命。LEACH路由協議網絡模型如圖1所示。

圖1 LEACH路由協議網絡模型

LEACH協議執(zhí)行過程是周期性的，稱為“輪”(Rounds)，每個周期分為簇的建立階段和穩(wěn)定狀態(tài)階段。簇的建立階段又可以分為簇頭選舉階段和成簇階段，一般規(guī)定簇的建立階段比穩(wěn)定階段的時間短，算法流程圖如圖2所示。

圖2 LEACH算法流程圖

簇的建立階段，網絡中的每個節(jié)點都產生一個0到1之間的隨機數用于與閾值T(si)比較，如果節(jié)點產生的隨機數小于閾值則成為本輪簇首，閾值T(si)的計算公式為：

(1)

其中，p是一個預先設定的常量，表示期望簇頭節(jié)點占所有節(jié)點的比例；r為當前輪數；si表示傳感器節(jié)點標識；G表示在過去rmod(1/p)中簇頭競選失敗的節(jié)點。由公式(1)可以看出，每1/p輪網絡所有節(jié)點均依照一定概率當選過一次簇頭，直到所有節(jié)點都當選過簇頭后才重新獲得競選簇頭的權利。簇頭節(jié)點競選成功之后，則向全網發(fā)布一條消息宣布自己成為簇頭。未成為簇頭的節(jié)點根據接收到信號強度加入到離自己最近的簇頭，并發(fā)送申請加入請求消息，簇頭根據成員數量建立一個TDMA調度，并將這個調度發(fā)送給所有成員，防止節(jié)點數據傳輸發(fā)生沖突，節(jié)點收到調度之后整個網絡就進入穩(wěn)定狀態(tài)階段。

在穩(wěn)定狀態(tài)階段，普通節(jié)點只能在簇內指定的持續(xù)時間內(時隙)發(fā)送自己感知的數據給簇頭節(jié)點。普通節(jié)點在沒有發(fā)送數據時，將進入休眠狀態(tài)以節(jié)省能量，而簇頭則保持工作狀態(tài)以接收數據。簇頭節(jié)點接收數據后經融合處理后，最后由單跳發(fā)送至Sink節(jié)點。

1.2 LEACH協議的問題分析

LEACH算法采用隨機選舉簇首的機制，在新一輪競選的過程中，最近幾輪為當選過簇首的節(jié)點隨機產生(0,1)的隨機數，然后與閾值T(si)比較，如果節(jié)點產生的隨機數小于閾值則成為本輪簇首。由于競選過程中未考慮節(jié)點的位置，導致產生的簇頭節(jié)點會出現位置集中的情況，同時會出現簇頭節(jié)點位置不理想導致節(jié)點間的通信能耗浪費的情況，如圖3所示。

圖3 LEACH算法分簇結果圖

在LEACH算法中，在簇頭選舉階段若只考慮節(jié)點的當選簇首的頻率，未考慮簇頭節(jié)點能量因素，會導致某些節(jié)點因距離網關節(jié)點遠近差異或者由于簇成員數目不一致而導致能量消耗不均衡的問題。

2 LEACH-M算法

基于對現有路由算法的研究與分析，本文提出了基于能量均衡的均勻分簇路由算法(LEACH-M)。采用二次競選的方法來產生最終簇首，綜合考慮節(jié)點的能量因素，通過輪換的機制首先產生候選簇首，然后根據節(jié)點的通信半徑，綜合考慮節(jié)點的能耗產生最終簇首。

2.1 網絡模型與通信模型

考慮一個由N個傳感器節(jié)點隨機均勻分布的方形監(jiān)測區(qū)域，檢測數據被周期性地收集，定義周期為輪，由Sink節(jié)點根據實際應用背景在初始化時設置并廣播，每輪包括分簇階段和數據傳輸階段，在數據傳輸階段普通節(jié)點將采集數據直接傳輸給簇頭，簇頭對收集到的數據進行數據融合處理,然后通過多跳方式發(fā)送給匯聚節(jié)點。對于網絡模型有以下假設：

(1)Sink節(jié)點位于監(jiān)測區(qū)域外，且Sink節(jié)點和傳感器節(jié)點在部署后處于靜止狀態(tài)，位置不再變化。

(2)傳感器節(jié)點si,i=1,2,…,N的初始能量相同，功能、結構也相同，每個節(jié)點均有唯一的標識(ID)。

(3)傳感器節(jié)點的地理位置可知，通過接收信號強度來估計二者之間的距離。

(4)傳感器節(jié)點可以根據接收方的距離來自主調節(jié)發(fā)送功率。

LEACH-M協議采用典型的無線通信能耗模型[8]傳輸k比特的數據包通過距離d的能耗為：

(2)

其中，Etx為傳輸電路能耗；Eamp為放大電路的能耗；β是一個路徑損耗常數，依賴于傳輸環(huán)境。當d≤d0和d>d0時，功率放大損耗分別采用“自由空間模型”和“多路徑衰減模型”，d0的取值如式(3)所示。

(3)

接收k比特數據能耗的計算公式：

Erx(k,d)=kErx.

(4)

其中，Erx表示接收電路能耗；融合k比特數據包的能耗Eag(k)=kEag。

2.2 簇的建立階段

2.2.1 簇首選舉策略

簇首選舉流程如圖4所示。

圖4 LEACH-M算法分簇流程圖

假設監(jiān)測區(qū)域中有N個節(jié)點，監(jiān)測區(qū)域的面積為S，假設簇的通信半徑為Rc，規(guī)定小區(qū)域的簇內有且只有一個節(jié)點成為簇頭節(jié)點，監(jiān)測區(qū)域內最多有個ceil(S/(πRc_min2))簇頭節(jié)點，進而可以得到期望簇首與節(jié)點的比例：

(5)

每經過1/pt輪后所有節(jié)點同時獲得競選簇首的權利，因此可通過輪流競選簇首方式來產生最終簇首。在新一輪中，節(jié)點si,i=1,2,…,N是否成為候選簇首由動態(tài)閾值T(si)決定，T(si)的計算公式：

(6)

其中，p表示期望候選簇首占所有節(jié)點的百分比；rm=rmod(1/pt)表示輪換周期的臨界值；pt表示期望最終簇首占所有節(jié)點的最大百分比；G表示在前(r-1)mod(rm)未當選為最終簇首的集合；si表示節(jié)點標識。

由式(6)首先隨機產生候選簇首節(jié)點，通過輪換的機制，保證所有節(jié)點在一定周期內當選簇首的頻率是相同的，從而在時間分布上消除節(jié)點因當選簇首頻率差異導致過早失效的情況。如果僅考慮節(jié)點當選簇首的頻率而不考慮節(jié)點位置以及能量因素會導致節(jié)點間能耗不均衡的情況。因此首先引入通信半徑Rc來構造鄰居簇首集合SCH，候選簇首sj的鄰簇首集sj·SCH為：

sj·SCH={sm|sm∈tentativeCHs,d(sj,sm)≤Rc}.

(7)

如果候選簇首sj一旦發(fā)現自身在鄰簇首集合中自身的剩余能量最大，則競選成功并廣播獲勝消息給其鄰居候選簇首，成為最終簇首。如果在鄰居簇首集中自身的剩余能量不是最大，則需等待鄰居簇首集中剩余能量大的節(jié)點先做出決策：若收到剩余能量比自己大的鄰簇首sk競選成功的消息，則候選簇首sj立即宣布退出競選，成為普通節(jié)點；若候選簇首sj收到剩余能量比自己大的鄰簇首sm退出競選的消息，則將sm在鄰簇首集合sj·SCH中刪除。由此整個簇首選舉過程結束。

2.2.2 分簇階段

簇首產生之后，未參與競選的節(jié)點被重新喚醒，然后簇首向全網廣播自身成為簇首的消息，普通節(jié)點選擇加入信號強度強的簇，成為該簇的成員節(jié)點，并向對應的簇首發(fā)送加入消息。

簇頭節(jié)點根據簇成員數目，全網廣播的形式向所有簇成員節(jié)點發(fā)送一個TDMA調度表，保證所有節(jié)點不沖突地發(fā)送數據給簇頭。

2.3 數據傳輸階段

2.3.1 簇內數據傳輸

為了便于實現，簇內數據通信采用與EEUC協議相同的通信方式——單跳通信，具體過程不再贅述。

2.3.2 簇間數據傳輸

為了驗證LEACH-M算法的有效性，簇間采用單跳通信，即簇頭節(jié)點直接和網關節(jié)點通信。

3 實驗仿真與結果分析

通過MATLAB進行實驗仿真，分析LEACH-M協議的能量效率和網絡的能量分布情況,并和LEACH協議進行比較。為了便于分析，假設采用理想的MAC協議，忽略無線通信發(fā)生丟包情況。仿真過程中應考慮路由建立過程中所有的通信能耗，包括廣播包、數據包的能耗及數據融合的能耗，為了保證數據的精度，只融合本簇內數據。具體仿真數據如表1所示。

表1 仿真參數

3.1 網絡拓撲分析

圖5顯示了LEACH-M協議的網絡拓撲?？梢钥闯?，LEACH-M協議在分簇階段采用了競選的機制,綜合考慮了位置和能量，保證了簇首的均勻分布，避免了簇首扎堆的情況，有利于均衡簇首間的能耗。

圖5 LEACH-M協議網絡拓撲

圖6 兩種算法網絡生存時間曲線圖

3.2 網絡的能量效率

由圖6可以看出，LEACH算法的第一個節(jié)點死亡時間為202，LEACH-M算法的第一個節(jié)點死亡時間為668,結果表明LEACH-M算法能夠有效延長網絡的生存時間。圖7是網絡總能量隨工作時間變化的曲線圖，可以看出LEACH-M算法每輪能耗相對均衡，能量總量值與工作時間成反比關系，而LEACH算法網絡總能耗隨工作時間變化關系不是曲線關系，輪與輪之間能耗不均衡。圖8為每輪網絡能耗隨工作時間變化曲線圖?？梢钥闯鯨EACH-M算法的節(jié)點能耗相對于LEACH算法更均衡、更穩(wěn)定。

圖7 網絡剩余總能量變化曲線圖

圖8 平均能耗使用曲線

4 結語

本文在現有均勻分簇算法研究與分析基礎上，提出了一種基于能耗均衡的均勻分簇算法(LEACH-M)。首先以輪換的機制先產生候選簇首，然后綜合考慮候選簇首的位置和能量因素，競爭產生最終簇首。仿真結果表明，LEACH-M算法能夠有效地延長網絡的生存時間，而且均衡整個網絡的能耗，提高網絡的性能。

[參考文獻]

[1]Tashtarian,E Haghighat,A T Honary,et al.A new energy-efficient cluster algorithm for wireless sensor networks[C].Sofiware,Telecommunications and Computer Networks,15th Intemational Conferenee on,2007.

[2]孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005.

[3]Mhatre V,Rosenberg C.Design guidelines for wireless sensor networks:communication,clustering and aggregation[J]. Ad Hoc Networks,2004(1):45-63.

[4]Younis O,Fahmy S.HEED:A Hybrid,Energy-efficient,distributed clustering approach for Ad Hoc sensor networks[J]. IEEE Transactions on Mobile Computing,2004(4):366-379.

[5]Akyildiz LF, Su W,Sankara subramaniam Y.Wireless sensor network[J].A survey Computer Networks,2002(4):22-34.

[6]Zhiyuan S,Liu F,Hou B,et al.Energy-efficient uneven clustering routing protocol for wireless sensor networks[J].Transducer & Microsystem Technology,2013(12):67-60.

[7]Holger K,Andreas W.Protocols and architectures for wireless sensor networks[M].Beijing: Publishing House of Electronics Industy,2007.

[8]Zheng L,Gao L,Yu T.An Energy-balanced clustering algorithm for wireless sensor networks based on distance and distribution[C].Proceedings of the 6th International Asia Conference on Industrial Engineering and Management Innovation,Atlantis Press,2016:229-240.