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

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

?

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

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

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

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

LEACH協(xié)議；路由屬性表；無線傳感網(wǎng)絡(luò)；均衡能耗

0 引言

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

1 LEACH算法

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

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

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

2 改進的算法

2.1 算法詳述

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

① 設(shè)置5%的網(wǎng)絡(luò)節(jié)點數(shù)目作為閾值門限；

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

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

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

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

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

表1 節(jié)點路由屬性表

2.2 選取簇頭階段

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

(1)

2.3 節(jié)點入簇階段

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

(2)

式中，d為當(dāng)前節(jié)點到簇頭節(jié)點的距離，dmax為網(wǎng)絡(luò)中任意節(jié)點間的最大距離值，Einit為節(jié)點的初始能量值，Ecur為節(jié)點的當(dāng)前剩余能量值。

圖1 節(jié)點入簇圖

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

3 仿真分析

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

表2 仿真參數(shù)

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

3.1.1 網(wǎng)絡(luò)生命周期

對該環(huán)境下，通過網(wǎng)絡(luò)節(jié)點的存活數(shù)和分簇的輪數(shù)的關(guān)系，對LEACH算法和本文算法進行對比仿真，如圖2所示。

圖2 節(jié)點存活數(shù)-輪數(shù)

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

3.1.2 網(wǎng)絡(luò)能耗

同樣對該環(huán)境下，通過網(wǎng)絡(luò)總能耗和分簇的輪數(shù)的關(guān)系，對LEACH算法和本文算法進行對比仿真，如圖3所示。

圖3 網(wǎng)絡(luò)總能耗-輪數(shù)

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

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

3.2.1 網(wǎng)絡(luò)生命周期

通過網(wǎng)絡(luò)節(jié)點的存活數(shù)和分簇的輪數(shù)的關(guān)系，對LEACH算法和本文算法進行對比仿真，如圖4所示。

圖4 節(jié)點存活數(shù)-輪數(shù)

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

3.2.2 網(wǎng)絡(luò)能耗

通過網(wǎng)絡(luò)總能耗和分簇的輪數(shù)的關(guān)系，對LEACH算法和本文算法進行對比仿真，如圖5所示。

圖5 網(wǎng)絡(luò)總能耗-輪數(shù)

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

4 結(jié)束語

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

[1] 任豐原,黃海寧,林 闖.無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報,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] 馮友宏，關(guān) 可.基于OMNET的無線傳感器網(wǎng)絡(luò)算法的改進[J].傳感技術(shù)學(xué)報，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] 胡 鋼，謝冬梅，吳元忠.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH 的研究與改進[J].傳感技術(shù)學(xué)報，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] 李燈熬，郝海龍，郭錦龍，等.一種能量有效的無線傳感器網(wǎng)絡(luò)分簇及簇間路由算法[J].自動化儀表,2015,36(12):4-7.

[10]段 軍.蟻群算法在LEACH 路由協(xié)議中的應(yīng)[J].計算機技術(shù)與發(fā)展,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].無線電通信技術(shù),2016,42(6):48-51.

2016-07-14

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

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

TP212

A

1003-3114(2016)06-48-4