基于LEACH的低能耗改進算法研究

曹喜珠，丁緒星，馮友宏，凌 敏，王再見

(安徽師范大學 物理與電子信息學院，安徽 蕪湖 241000)

?

基于LEACH的低能耗改進算法研究

曹喜珠，丁緒星，馮友宏，凌 敏，王再見

(安徽師范大學 物理與電子信息學院，安徽 蕪湖 241000)

為了解決LEACH協議在簇頭分布不均和能量消耗集中等方面的缺陷，提出一種基于LEACH協議的距離調控改進路由算法LEACH-D。在簇頭選取階段，充分考慮簇頭選擇的個數和相對分布位置；在簇形成階段，采用節點維護的路由屬性表和分布的密集程度及相對距離確定入簇方式。仿真結果表明，相較于LEACH算法，改進后的算法有效均衡了網絡能耗，延長了網絡生存周期。

LEACH協議；路由屬性表；無線傳感網絡；均衡能耗

0 引言

無線傳感器網絡(Wireless Sensor Networks,WSNs)是由大量的靜止或移動的傳感器以自組織和多跳的方式構成的無線網絡[1]。與傳統無線通信網絡不同，WSN中節點帶寬、內存資源更為匱乏，在一些特殊場合其電池不能更換和有效補充，進而直接影響感知網絡的生存周期和傳輸的信息質量，基于此，感知網絡中節點通信協議應該能有效地利用節點有限的能量，盡可能地延長網絡的生存周期。其中經典的LEACH(Low Energy Adaptive Clustering Hierarchy)協議是應用于無線傳感網絡中的一種典型的層次型路由算法，與一般的平面多跳路由協議和靜態分層算法相比，該算法可以將網絡生命周期延長15% 以上[2-3]。

1 LEACH算法

LEACH算法是層次型路由算法的基礎，提出將網絡分成若干個簇，每個簇選取簇頭節點匯聚簇成員信息，融合后發送至網絡的BS(Base Station)節點[4]。該算法仍存在一些不足之處，如：LEACH路由算法中簇頭的產生方法在數量上常常呈現不穩定狀態；LEACH路由算法中簇頭的分布往往不均勻,失去了分層的意義[4];LEACH路由算法簇頭的選擇沒有考慮節點自身的剩余能量[5-6]；LEACH路由算法采用簡單的分層方式，這樣限制了網絡的規模擴展[7]。LEACH路由算法中的成簇階段沒有考慮節點傳送信息的相關性和冗余性[8-9]。

文獻[10]中提出將蟻群算法應用到LEACH協議中，通過動態改變成簇半徑，以及簇頭間通信采用蟻群算法；文獻[11] 提出將網絡根據節點與sink節點的距離分為兩層；文獻[3]提出基于基站距離與基站方向的成簇路由算法。以上算法不同程度上降低了網絡能耗，但是在整體網絡的簇頭分布隨機性很大，同時存在簇頭節點負荷比較大的問題沒有有效解決，且在成員節點入簇階段沒有考慮成簇的成員節點之間的相對距離。

基于此本文算法具有如下的特點：① 在簇頭產生階段為每個傳感節點分配選擇簇頭的參考半徑；② 同時節點維護自身的路由屬性表，候選簇頭節點根據屬性表判斷是否可競選簇頭角色；③ 在節點入簇階段，通過查詢自身屬性表選擇不同的入簇方式；④ 充分考慮了普通節點信息的冗余性和相關性，為此采用休眠機制來降低信息的相關性；⑤ 簇頭融合簇成員信息與基站通信，根據與基站之間的距離選擇單跳或者多跳路由方式。

2 改進的算法

2.1 算法詳述

LEACH算法在簇頭產生階段存在簇頭分布集中，造成網絡局部負載大等問題，本文算法的主要思想是選擇位置分布相對均勻的簇頭節點，同時優化分簇結構，從而平衡網絡能量消耗，延長無線傳感網絡的壽命。該算法過程如下：

① 設置5%的網絡節點數目作為閾值門限；

② 非簇頭節點根據本文提出的屬性表選擇不同的入簇方式；

③ 處理本文定義的游離節點的入簇方式；

④ 為了降低信息采集的冗余性，根據周圍是否有活躍節點來決定休眠還是激活采集并傳輸信息；

⑤ 對于遠離基站節點的簇頭采用多跳路由方式進行通信。

下面對于本算法中的關鍵部分進行說明：對于采用分簇路由方式的無線傳感網絡，簇頭節點在網絡通信中占據著非常重要的角色，因此簇頭節點的選取和產生方式至關重要。如表1所示，本文算法中，網路各節點維護自身路由屬性表。其中，字段ID表示該節點的唯一編號，在網絡初始化時隨機分配；字段Alive表示該節點是否為存活節點，取值為0(死亡)或者1(存活)；字段Sleep表示該節點是否為休眠節點，取值為0(休眠)或者1(活躍)；字段Head表示該節點是否為簇頭節點，取值為0(否)或者1(是)，在網絡初始化階段，該屬性統一設置為0；字段Active表示該節點在簇頭選取階段是否參與，取值為0表示該節點在本輪選取簇頭階段沒有當選簇頭或者沒有收到簇頭廣播的消息，或者收到至少兩個簇頭節點廣播的消息，為游離節點，取值為1表示該節點當選為簇頭或者在參考范圍內只接收到一個簇頭廣播的消息，該屬性初始值為0；字段Cluster表示節點是否入簇屬性，取值為0(未入簇)或者1(已入簇)，初始值為0。該路由屬性表在網絡初始化時候被寫入初始值，在分簇建立階段和穩定階段被改寫和讀取。

表1 節點路由屬性表

2.2 選取簇頭階段

為了避免簇頭節點分布集中的情況，該階段綜合考慮簇頭剩余能量以及簇頭之間相對位置因素，采取局部集中原則選取簇頭節點。對于節點數為N的無線傳感網絡，預設簇頭節點的百分比為P，網絡進行初始化后，BS根據式(1)通過廣播的方式為每個節點分配分簇參考距離Rre，Active屬性值為0的節點產生0～1之間的隨機數，當該隨機數小于式(1)設定的閾值，則當選為候選簇頭節點；第一個當選為候選簇頭的節點則為第一個簇頭節點，該節點向周圍廣播消息并且將自身Head屬性置為1，BS記錄下簇頭節點個數，同時在Rre半徑內的節點接收到消息后將自身屬性表的Active屬性置為1，該節點在本階段不參與簇頭競選。遵循該過程依次產生其他簇頭節點，由BS控制本階段產生簇頭節點的個數。當簇頭節點數達到N*P后，本輪簇頭選取結束。式(1)中，S為無線傳感網絡的面積大小，N為網絡中節點個數，P為節點成為簇頭節點的百分比：

(1)

2.3 節點入簇階段

由于在簇頭產生階段遵循每個簇頭節點的參考半徑范圍內不產生其他簇頭節點，則存在部分非簇頭節點的參考半徑內沒有簇頭節點，或者在參考距離內有多個簇頭節點，稱為活躍節點，如圖1所示。對于路由屬性表的Active屬性為1的非簇頭節點，選擇參考距離內最近距離的簇頭節點單播消息入簇，如式(2)，計算d最小的情況；對于Active屬性為0的非簇頭節點，在該階段計算各自的入簇閾值Tclu，如式(2)，選擇閾值Tclu最大的簇頭節點入簇，即選擇距離較近且剩余能量較高的簇頭節點入簇。

(2)

式中，d為當前節點到簇頭節點的距離，dmax為網絡中任意節點間的最大距離值，Einit為節點的初始能量值，Ecur為節點的當前剩余能量值。

圖1 節點入簇圖

節點之間的通信 ：LEACH-D算法在簇內采取近距離內能量較低的節點輪流進入休眠狀態，從而降低節點信息的冗余。簇頭負責與基站的通信，當簇頭離基站較遠時，要以較大的功率發送數據，這會造成簇頭節點能量的過快消耗。LEACH-D處理方法是，當簇頭節點距離基站較近時，簇頭節點直接與基站通信，當簇頭節點距離基站較遠時，簇頭節點把融合后的數據發送到適宜的臨近簇頭節點，臨近簇頭節點再把數據轉發給下一個適宜轉發的簇頭節點，以此類推，直到把數據交付給基站。

3 仿真分析

選擇針對無線傳感網絡仿真的平臺Atos-SensorSim，對本文算法和LEACH進行了對比仿真。在300m*100m環境中隨機分布200個節點。仿真網絡環境選擇基站位于(150,50)和(300,100)兩個位置的無線傳感網絡，參數設置如表2所示。

表2 仿真參數

3.1 基站位置位于(150,50)

3.1.1 網絡生命周期

對該環境下，通過網絡節點的存活數和分簇的輪數的關系，對LEACH算法和本文算法進行對比仿真，如圖2所示。

圖2 節點存活數-輪數

由圖2可以看出，本文改進的LEACH分簇路由算法提高了節點的存活率，LEACH算法在20輪之前便出現節點死亡，改進算法在75輪以后出現；在輪數300之前，LEACH算法的節點存活率高于45%，本文改進的算法節點存活率高于60%，提高了15%。所以，在基站距離較近的隨機分布無線傳感網絡環境中，改進算法提高了節點存活率，延長網絡壽命。

3.1.2 網絡能耗

同樣對該環境下，通過網絡總能耗和分簇的輪數的關系，對LEACH算法和本文算法進行對比仿真，如圖3所示。

圖3 網絡總能耗-輪數

從圖3 可以看出，本文算法在網絡能耗的統計上低于LEACH算法，在輪數為30時，網絡能耗節約2 000 J左右；在輪數150以后，相較于LEACH算法，本文算法平均降低網絡能耗750 J左右。所以，在隨機分布的無線傳感網絡中，本文算法通過平衡網絡簇頭節點的負載分配，能有效降低網絡能耗。

3.2 基站位置位于(300,100)

3.2.1 網絡生命周期

通過網絡節點的存活數和分簇的輪數的關系，對LEACH算法和本文算法進行對比仿真，如圖4所示。

圖4 節點存活數-輪數

從圖4可以看出， 相較于基站位于中心位置的環境，該環境下節點存活率降低，這也證明了LEACH協議在簇頭節點與基站通信耗能多的不足。本文改進的分簇路由算法針對簇頭與基站之間的通信處理方法提高了節點的存活率，LEACH算法在25輪以前出現節點的死亡，改進算法在75輪以后出現；在輪數為350之前，LEACH算法的節點存活率高于42%，本文改進的算法存活率高于60%，提高了18%。所以，在基站距離較遠的隨機分布無線傳感網絡環境中，改進算法能有效提高節點存活率，延長網絡壽命。

3.2.2 網絡能耗

通過網絡總能耗和分簇的輪數的關系，對LEACH算法和本文算法進行對比仿真，如圖5所示。

圖5 網絡總能耗-輪數

由圖5可以看出，本文算法同樣在網絡能耗的統計上低于LEACH算法，在輪數為25時，網絡能耗節約2 500 J左右；在輪數50以前，相較于LEACH算法，本文算法平均降低網絡能耗2 250 J左右；在輪數100以后，平均節約網絡能耗1 500 J左右。所以，在基站分布較遠的隨機分布無線傳感網絡中，本文算法通過簇頭節點間多跳配合的方式完成與基站的通信，能有效降低網絡能耗。

4 結束語

分層協議LEACH相較于平面多跳路由等協議能有效地提高網絡壽命，但存在能量消耗不均勻、局部負載大等局限性。本文提出一種基于LEACH的改進分層路由算法，每個節點維護自身路由屬性表，節點根據距離和能量兩個因素選擇入簇，同時根據距離調整了簇成員以及簇與簇之間的通信方式。仿真結果表明，改進的分層路由算法能有效降低網絡能耗，延長網絡壽命。該算法思路適應于傳感器節點隨機分布的大中型傳感采集場景，如圖書管理、倉儲管理管理等。

[1] 任豐原,黃海寧,林 闖.無線傳感器網絡[J].軟件學報,2003,14(7):1282-1291.

[2] Jisoo S,Chang J S.CREEC:Chain Routing with Even Energy Consumption[J].Communications and Networks,2011,13(1):17-25.

[3] 馮友宏，關 可.基于OMNET的無線傳感器網絡算法的改進[J].傳感技術學報，2010,23(6):859-862.

[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,Jan.2000,2:10-15.

[5] Himanshu B P,Devesh C J.E-LEACH:Improving the LEACH Protocol for Privacy Preservation in Secure Data Aggregation in Wireless Sensor Networks[C]∥IEEE International Conference on Industrial and Information Systems (ICIIS),Gwalior:IEEE Press,2014:1-5.

[6] 胡 鋼，謝冬梅，吳元忠.無線傳感器網絡路由協議LEACH 的研究與改進[J].傳感技術學報，2007，20(6):1391-1396.

[7] XIE Wei-xian,ZHANG Qi-ye,SUN Ze-ming,et al.A Clustering Routing Protocol for WSN Based on Type-2 Fuzzy Logic and Ant Colony Optimization [J].Wireless Personal Communications,2015,84(2):1165-1196.

[8] Masaeli N,Javadi H H S,NOORI E.Optimistic Selection of Cluster Heads Based on Facility Location Problem in Cluster-Based Routing Protocols[J].Wireless Personal Communications,2013,72(4):2721-2740.

[9] 李燈熬，郝海龍，郭錦龍，等.一種能量有效的無線傳感器網絡分簇及簇間路由算法[J].自動化儀表,2015,36(12):4-7.

[10]段 軍.蟻群算法在LEACH 路由協議中的應[J].計算機技術與發展,2014,24(1):65-68.

[11]Navin G,Pyun J Y.Distance Aware Intelligent Clustering Protocol for Wireless Sensor Networks[J].Communications and Networks,2010,12(2):122-129.

Research of Low-energy Consumption Routing Algorithm Based on LEACH

CAO Xi-zhu,DING Xu-xing,FENG You-hong,LING Min,WANG Zai-jian

(College of Physics and Electronic Information,Anhui Normal University,Wuhu Anhui 241000,China)

Low-Energy Adaptive Clustering Hierarchy (LEACH) is a kind of hierarchical routing protocol,but some drawbacks exist,such as uneven distribution of Cluster Heads (CHs),centralized energy consumption and so on.In this paper,an improved algorithm in distance control based on LEACH is proposed to solve the problems above,which is called LEACH-D (LEACH-Distance).In the step of selecting CHs,the number of CHs and the relative distribution position of them are considered.In the step of clusters formation,the way that the nodes join the cluster is decided by the routing attribute tables and the density.Simulation results show that the improved algorithm balances the network energy consumption effectively,and prolongs the lifetime of networks compared with LEACH.

LEACH;routing attribute tables;wireless sensor networks;balancing the energy consumption

10.3969/j.issn.1003-3114.2016.06.12

曹喜珠,丁緒星,馮友宏,等.基于LEACH的低能耗改進算法研究[J].無線電通信技術,2016,42(6):48-51.

2016-07-14

國家自然科學基金項目(61401004)；江蘇省2015年高校研究生科研創新計劃項目(KYLX15_0833)

曹喜珠(1980—) ，女，碩士研究生，主要研究方向：無線傳感網、物理層安全。丁緒星( 1970—) ，男，教授，主要研究方向：智能儀器、無線傳感器網絡。馮友宏( 1979—) ，男，副教授，主要研究方向：無線通信、物理層安全。

TP212

A

1003-3114(2016)06-48-4