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

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

?

基于LEACH的低能耗改進(jìn)算法研究

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

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

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

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

0 引言

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

1 LEACH算法

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

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

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

2 改進(jìn)的算法

2.1 算法詳述

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

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

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

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

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

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

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

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

2.2 選取簇頭階段

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

(1)

2.3 節(jié)點(diǎn)入簇階段

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

(2)

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

圖1 節(jié)點(diǎn)入簇圖

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

3 仿真分析

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

表2 仿真參數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由圖5可以看出，本文算法同樣在網(wǎng)絡(luò)能耗的統(tǒng)計(jì)上低于LEACH算法，在輪數(shù)為25時(shí)，網(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左右。所以，在基站分布較遠(yuǎn)的隨機(jī)分布無線傳感網(wǎng)絡(luò)中，本文算法通過簇頭節(jié)點(diǎn)間多跳配合的方式完成與基站的通信，能有效降低網(wǎng)絡(luò)能耗。

4 結(jié)束語(yǔ)

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

[1] 任豐原,黃海寧,林 闖.無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào),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ìn)[J].傳感技術(shù)學(xué)報(bào)，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ìn)[J].傳感技術(shù)學(xué)報(bào)，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].自動(dòng)化儀表,2015,36(12):4-7.

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

2016-07-14

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

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

TP212

A

1003-3114(2016)06-48-4