何書前 嚴(yán)晨 鄧正杰 石春

摘? 要： 詳細(xì)分析了LEACH算法，并介紹了LEACH算法的優(yōu)缺點(diǎn)。針對(duì)LEACH算法選擇簇頭沒有考慮剩余能量，提出一種改進(jìn)后的算法LEACH?N。主要節(jié)點(diǎn)利用剩余能量和特定范圍內(nèi)相鄰節(jié)點(diǎn)數(shù)的不同，給予不同成為簇頭的概率;同時(shí)，增加普通節(jié)點(diǎn)可以直接發(fā)送數(shù)據(jù)到匯聚節(jié)點(diǎn)（Sink），減少能量的消耗。仿真結(jié)果表明，與傳統(tǒng)LEACH算法相比，LEACH?N算法能均衡節(jié)點(diǎn)能量消耗，延長(zhǎng)網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞： 改進(jìn)的LEACH算法; 無(wú)線傳感器網(wǎng)絡(luò); 路由協(xié)議; 算法分析; 能量均衡; 能耗減少

中圖分類號(hào)： TN919?34? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2020）05?0006?04

Improved LEACH algorithm based on energy balance in route optimization

of wireless sensor networks

HE Shuqian， YAN Chen， DENG Zhengjie， SHI Chun

（School of Information Science and Technology， Hainan Normal University， Haikou 571158， China）

Abstract： The LEACH algorithm is analyzed in detail， including its advantages and disadvantages. As the LEACH algorithm fails to take into account the residual energy in the selection of cluster head， an improved algorithm LEACH?N is proposed. It can get the main nodes′ different probabilities in becoming cluster heads? according to the different remaining energy and the number of adjacent nodes in specific scope，. Meanwhile， common nodes are added， which can send data directly to the aggregation node （Sink） to reduce the energy consumption. The simulation results show that， in comparison with the traditional LEACH algorithm， the LEACH?N algorithm can balance the energy consumption of the nodes， and prolong the network life cycle.

Keywords： improved LEACH algorithm; WSN; routing protocol; algorithm analysis; energy balance; energy consumption reduction

0? 引? 言

如何在網(wǎng)絡(luò)節(jié)點(diǎn)能量受限的條件下，通過網(wǎng)絡(luò)協(xié)議有效保證整個(gè)網(wǎng)絡(luò)的生命周期和傳輸數(shù)據(jù)量，一直是無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）研究的熱點(diǎn)問題[1]。LEACH協(xié)議[2]作為WSNs能量有效分簇路由選擇協(xié)議的代表，在分層次無(wú)線傳感器路由協(xié)議應(yīng)用中得到了很高的關(guān)注，并在其基礎(chǔ)上發(fā)展了很多路由協(xié)議，如EEHC[3]，HEED[4]，DEEC[5]等。

與傳統(tǒng)WSNs路由協(xié)議相比，LEACH協(xié)議節(jié)省了能量，延長(zhǎng)了網(wǎng)絡(luò)的生命周期，但也存在一定的缺陷。例如，在簇頭選擇時(shí)，只考慮節(jié)點(diǎn)成為簇頭的概率，未考慮節(jié)點(diǎn)剩余能量、消耗能量和傳輸距離等重要影響因素，導(dǎo)致剩余能量較少的節(jié)選為簇頭而造成縮短網(wǎng)絡(luò)生命周期的問題。針對(duì)LEACH協(xié)議存在的問題，近年來(lái)，很多文獻(xiàn)[5?10]提出了很多解決方案，文獻(xiàn)[5]利用仿射傳播聚類解決均衡分簇問題;文獻(xiàn)[6?9]則引入相應(yīng)的影響因素，改變分簇閾值，達(dá)到改善分簇質(zhì)量的目的;文獻(xiàn)[10?11]則將LEACH協(xié)議擴(kuò)展至多跳環(huán)境，利用聚類的方法進(jìn)行簇頭節(jié)點(diǎn)選擇，并結(jié)合最小傳輸能量（Minimum Transmission Energy，MTE）協(xié)議，大大延長(zhǎng)了生命周期。針對(duì)該問題，本文引入簇內(nèi)節(jié)點(diǎn)剩余能量消耗不均衡因素，如剩余能量、相鄰節(jié)點(diǎn)數(shù)量和傳輸距離等因素，提出了一種改進(jìn)的LEACH算法，因引入更加合理的剩余能量因素和節(jié)點(diǎn)數(shù)據(jù)傳輸機(jī)制，顯著降低了簇頭節(jié)點(diǎn)的能耗，有效延長(zhǎng)了網(wǎng)絡(luò)的生命周期和網(wǎng)絡(luò)數(shù)據(jù)吞吐量。

1? LEACH算法概述

LEACH協(xié)議具有周期性運(yùn)行過程，每輪周期由初始化和穩(wěn)定兩個(gè)階段組成，每輪則分為簇建立和數(shù)據(jù)傳輸兩個(gè)步驟。在簇建立階段，相鄰節(jié)點(diǎn)動(dòng)態(tài)成簇，并以固定規(guī)則來(lái)選擇簇頭。成簇之后，簇內(nèi)節(jié)點(diǎn)先將數(shù)據(jù)匯聚給簇頭，由簇頭將數(shù)據(jù)融合后轉(zhuǎn)發(fā)給匯聚節(jié)點(diǎn)（Sink）;在數(shù)據(jù)傳輸中有調(diào)度機(jī)制，為節(jié)點(diǎn)分配時(shí)隙進(jìn)行數(shù)據(jù)傳輸。為節(jié)約頻繁的分簇造成的資源消耗，每輪的數(shù)據(jù)傳輸時(shí)間需大于簇建立的時(shí)間。具體算法流程如下：

1） 簇建立。每個(gè)節(jié)點(diǎn)隨機(jī)生成一個(gè)0～1之間的隨機(jī)數(shù)，若該節(jié)點(diǎn)在上一輪未選為簇頭，且隨機(jī)數(shù)小于設(shè)定的閾值[T（n）]，則該節(jié)點(diǎn)在此輪成為簇頭。如果該節(jié)點(diǎn)在上一輪已經(jīng)當(dāng)選過簇頭，則該節(jié)點(diǎn)不再當(dāng)選為簇頭。[T（n）]計(jì)算如式（1）所示：

[T（n）=p1-prmod（1p），? ? ?n∈G0，? ? ?其他] （1）

式中：[p]為簇頭節(jié)點(diǎn)數(shù)目占總節(jié)點(diǎn)數(shù)的比例;[r]為當(dāng)前輪數(shù);[G]為在最近的[1p]輪中未當(dāng)選簇頭的節(jié)點(diǎn)集合。

所有簇頭節(jié)點(diǎn)確定后，簇頭節(jié)點(diǎn)向其他所有節(jié)點(diǎn)廣播當(dāng)前簇頭的消息，其他節(jié)點(diǎn)根據(jù)接收信號(hào)的強(qiáng)弱，判定傳輸距離大小，以此選擇加入哪個(gè)簇;節(jié)點(diǎn)發(fā)送加入簇請(qǐng)求成為簇成員，簇頭根據(jù)成員節(jié)點(diǎn)的信息，控制協(xié)調(diào)簇的數(shù)據(jù)傳輸，形成TDMA時(shí)間表。

2） 數(shù)據(jù)傳輸。簇內(nèi)所有節(jié)點(diǎn)將采集的數(shù)據(jù)傳輸給簇頭節(jié)點(diǎn)，簇頭保持在線狀態(tài)，接收完所有其他節(jié)點(diǎn)數(shù)據(jù)后，進(jìn)行數(shù)據(jù)融合減少數(shù)據(jù)冗余，再把整個(gè)簇的數(shù)據(jù)發(fā)送到Sink節(jié)點(diǎn)。數(shù)據(jù)傳輸過程是以幀的方式實(shí)現(xiàn)，每幀分配相應(yīng)的時(shí)隙給簇內(nèi)的節(jié)點(diǎn)[2]。

2? 改進(jìn)的LEACH算法

針對(duì)LEACH算法的不足，本文對(duì)LEACH算法的簇頭選擇和數(shù)據(jù)傳輸進(jìn)行了改進(jìn)。改進(jìn)的LEACH算法采用了與LEACH算法相同的網(wǎng)絡(luò)模型，針對(duì)LEACH算法沒有考慮節(jié)點(diǎn)剩余能量和位置的不足，改進(jìn)了LEACH算法簇頭選擇方法（簡(jiǎn)稱為L(zhǎng)EACH?N），主要依據(jù)各節(jié)點(diǎn)特定范圍內(nèi)的節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)的剩余能量，得到節(jié)點(diǎn)成為簇頭的概率。與WSNs的實(shí)際情況相符，提高簇的生成質(zhì)量，從而減少WSNs的能耗，以延長(zhǎng)WSNs的生命周期。

LEACH?N算法的基本思想是：根據(jù)當(dāng)前節(jié)點(diǎn)特定范圍內(nèi)的節(jié)點(diǎn)數(shù)、剩余能量和匯聚發(fā)送能量消耗為主要因素選取簇頭;再引入節(jié)點(diǎn)與簇頭之間的距離進(jìn)行分簇，成簇后進(jìn)行數(shù)據(jù)傳輸時(shí)，考慮普通節(jié)點(diǎn)到Sink節(jié)點(diǎn)之間的距離，在限定的短距離范圍內(nèi)，制定節(jié)點(diǎn)直接傳輸數(shù)據(jù)至匯聚節(jié)點(diǎn)，進(jìn)一步節(jié)省能量消耗，提高數(shù)據(jù)傳輸效率。

LEACH?N算法流程如圖1所示，具體步驟如下：

1） 每一個(gè)節(jié)點(diǎn)計(jì)算與其他節(jié)點(diǎn)距離小于[d0]的節(jié)點(diǎn)數(shù)[a]，[d0]的計(jì)算公式如下：

[d0=EfsEmp]? （2）

式中：[Efs]表示自由空間信道模型信號(hào)放大器功耗;[Emp]表示多路徑衰減信道模型信號(hào)放大器功耗。

2） 計(jì)算節(jié)點(diǎn)剩余能量[El]。

3） 節(jié)點(diǎn)根據(jù)剩余能量和特定范圍內(nèi)的節(jié)點(diǎn)數(shù)計(jì)算出各個(gè)節(jié)點(diǎn)可成為新的簇頭節(jié)點(diǎn)的閾值，閾值計(jì)算公式為：

[T（n）=pi1-pirmod（1pi）?ElE0，n∈G0，? ? ? 其他] （3）

式中：[pi=p?an]，[p]為整個(gè)網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)[n]的比例;[E0]為節(jié)點(diǎn)的初始能量;[G]代表在上一輪[r-1]中未當(dāng)選簇頭的節(jié)點(diǎn)集合，[r]是WSNs進(jìn)行的輪數(shù);[rmod（1pi）]為一輪循環(huán)中當(dāng)選過簇頭的傳感器節(jié)點(diǎn)個(gè)數(shù)。

4） 節(jié)點(diǎn)會(huì)產(chǎn)生一個(gè)[0，1]的隨機(jī)數(shù)。如果隨機(jī)數(shù)小于這個(gè)閾值[T（n）]，則該節(jié)點(diǎn)成為簇頭。

5） 所有簇頭選擇完成之后，廣播所有簇頭節(jié)點(diǎn)位置信息，剩余的普通節(jié)點(diǎn)選擇距離最近的簇頭入簇，并將自己的標(biāo)識(shí)記為該簇頭的標(biāo)識(shí)號(hào)。

6） 所有節(jié)點(diǎn)入簇完成，轉(zhuǎn)為數(shù)據(jù)傳輸階段，簇內(nèi)的普通節(jié)點(diǎn)比較到簇頭和Sink節(jié)點(diǎn)的距離，若到Sink節(jié)點(diǎn)的距離更小，則直接傳輸數(shù)據(jù)到Sink節(jié)點(diǎn)，減少能量的消耗。

7） 簇頭節(jié)點(diǎn)接收簇內(nèi)非簇頭節(jié)點(diǎn)的數(shù)據(jù)，通過計(jì)算、融合后將數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。該階段運(yùn)行一輪后，進(jìn)入下一輪，轉(zhuǎn)至步驟2），計(jì)算剩余能量[El]。

3? 仿真實(shí)驗(yàn)與分析

3.1? LEACH?N算法仿真實(shí)驗(yàn)環(huán)境設(shè)置

仿真實(shí)驗(yàn)采用Matlab作為實(shí)驗(yàn)平臺(tái)，對(duì)經(jīng)典的LEACH算法、LEACH?N算法和Combine LEACH & MTE算法[10]進(jìn)行仿真實(shí)驗(yàn)比較。仿真的能量模型采用Heinzelman等人提出的無(wú)線通信模型[11]，節(jié)點(diǎn)的模型使用一階無(wú)線通信模型（First Order Radio Model，F(xiàn)ORM）。在該模型中，節(jié)點(diǎn)在距離[d]上傳輸[k] bit時(shí)，若傳輸距離小于等于[d0]，采用自由空間模型;當(dāng)傳輸距離大于[d0]時(shí)，采用多路徑衰減模型。

節(jié)點(diǎn)發(fā)送[k] bit數(shù)據(jù)到Sink節(jié)點(diǎn)的能耗計(jì)算公式如下：

[ETx to BS（k，d）=（ETx+EDA）?k+Emp?k?d4，d>d0（ETx+EDA）?k+Efs?k?d2，d≤d0] （4）

節(jié)點(diǎn)發(fā)送[k] bit數(shù)據(jù)到簇頭的能耗計(jì)算公式如下：

[ETx to CS（k，d）=ETx?k+Emp?k?d4，d>d0ETx?k+Efs?k?d2，d≤d0] （5）

簇頭接收和融合[k] bit數(shù)據(jù)的能耗計(jì)算公式如下：

[ERx（k，d）=（ETx+EDA）?k] （6）

式中：[ETx]為發(fā)射1 bit數(shù)據(jù)損耗的能量;[ERx]為接收融合1 bit數(shù)據(jù)損耗的能量;[EDA]為數(shù)據(jù)聚焦單位數(shù)據(jù)的能量;[d]為數(shù)據(jù)傳輸?shù)木嚯x。

仿真網(wǎng)絡(luò)中有100個(gè)節(jié)點(diǎn)且隨機(jī)地分布在100 m×100 m范圍內(nèi)，Sink節(jié)點(diǎn)的位置固定，每個(gè)節(jié)點(diǎn)的初始能量為0.5 J，仿真參數(shù)如表1所示。

圖2中的Combine LEACH & MTE仿真圖形是Mounir Arioua等人[11]提出的一種結(jié)合LEACH和MTE協(xié)議的算法，從圖2中可以看出，LEACH?N算法比Combine LEACH & MTE生命周期長(zhǎng)，因?yàn)長(zhǎng)EACH?N算法考慮了節(jié)點(diǎn)剩余能量，而Combine LEACH & MTE沒有考慮剩余能量。但是LEACH?N算法的不足是適用于規(guī)模小的網(wǎng)絡(luò)，但是Combine LEACH & MTE可以采用不同類型的WSNs。

從圖2中可以得到LEACH算法和LEACH?N算法生命周期的比較，如表2所示。從表2中可以看出，隨著網(wǎng)絡(luò)的運(yùn)行，改進(jìn)算法的效率不斷提高。因?yàn)殡S著節(jié)點(diǎn)的不斷死亡，網(wǎng)絡(luò)區(qū)域中簇頭覆蓋范圍要更大，原始的LEACH算法選擇簇頭在節(jié)點(diǎn)稀疏的概率越大，而LEACH?N算法中簇頭的選擇考慮特定范圍內(nèi)相鄰節(jié)點(diǎn)數(shù)，從而在節(jié)點(diǎn)更密集的區(qū)域選擇簇頭，也說(shuō)明 LEACH?N算法在長(zhǎng)時(shí)間的網(wǎng)絡(luò)運(yùn)行能耗的節(jié)省更加明顯。

3.2.2? Sink節(jié)點(diǎn)接收數(shù)據(jù)量

兩種算法Sink點(diǎn)接收數(shù)據(jù)的關(guān)系多少比較如圖3所示。圖3中兩條曲線，LEACH算法在不到1 500多輪時(shí)數(shù)據(jù)量已經(jīng)不再變化，而LEACH?N算法則到了2 000多輪，而且LEACH?N的數(shù)據(jù)量是LEACH算法20多倍，得到這個(gè)結(jié)果一方面因?yàn)榫W(wǎng)絡(luò)生命周期的延長(zhǎng)，從而網(wǎng)絡(luò)整體發(fā)送數(shù)據(jù)更多了;另一方面是在數(shù)據(jù)傳輸階段增加了簇內(nèi)普通節(jié)點(diǎn)，距離Sink點(diǎn)更近，將數(shù)據(jù)直接傳輸給Sink節(jié)點(diǎn)。所以LEACH?N算法在整體上比LEACH算法更加優(yōu)化。

3.2.3? 網(wǎng)絡(luò)剩余能量

兩種算法網(wǎng)絡(luò)剩余能量與時(shí)間關(guān)系如圖4所示。從圖4中可以得到，在輪數(shù)相同的情況下，LEACH?N算法中的網(wǎng)絡(luò)剩余能量比LEACH算法網(wǎng)絡(luò)剩余能量多，說(shuō)明LEACH?N算法可以更好地平衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗，節(jié)省網(wǎng)絡(luò)能量，延長(zhǎng)網(wǎng)絡(luò)的生命周期。

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

本文針對(duì)LEACH算法的不足，提出了LEACH?N算法，進(jìn)行了相應(yīng)的仿真實(shí)驗(yàn)比較，實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法延長(zhǎng)了WSNs的生命周期。本文提出的LEACH?N算法在簇頭選舉和數(shù)據(jù)傳輸方式上進(jìn)行改進(jìn)。選擇簇頭時(shí)，考慮節(jié)點(diǎn)能量狀況和特定范圍內(nèi)相鄰的節(jié)點(diǎn)數(shù);傳輸數(shù)據(jù)中，簇內(nèi)普通節(jié)點(diǎn)距離Sink節(jié)點(diǎn)更近時(shí)，直接與Sink節(jié)點(diǎn)通信。仿真實(shí)驗(yàn)結(jié)果顯示，LEACH?N算法使節(jié)點(diǎn)的能量消耗更加平衡。LEACH?N算法也有如下不足之處：簇頭的選擇沒有充分考慮是否會(huì)在邊緣區(qū)域，會(huì)造成簇頭與Sink點(diǎn)長(zhǎng)距離的通信;LEACH?N算法中的簇頭節(jié)點(diǎn)與Sink點(diǎn)采用單跳通信，所以適用于小規(guī)模網(wǎng)絡(luò)，如果網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域大，會(huì)使簇頭節(jié)點(diǎn)能量消耗較快。

參考文獻(xiàn)

[1] LIU Xuxun. A survey on clustering routing protocols in wireless sensor networks [J]. Sensors， 2012， 12（8）： 11113?11153.

[2] SINGH A P， SHARMA N， ROY N R， et al. Residual energy and distance based energy?efficient communication protocol for wireless sensor network [J]. International journal of computer applications， 2013， 74（12）： 11?16.

[3] GUAN Xin， WU Huayang， BI Degang. EEHCA： An energy?efficient hierarchical clustering algorithm for wireless sensor networks [J]. Information technology journal， 2008， 7（2）： 245?252.

[4] CHAN T J， CHEN C M， HUANG Y F， et al. Optimal cluster number selection in ad?hoc wireless sensor networks [J]. WSEAS transactions on communications， 2008， 7（8）： 837?846.

[5] SOHN I， LEE J H， LEE S H. Low?energy adaptive clustering hierarchy using affinity propagation for wireless sensor networks [J]. IEEE communications letters， 2016， 20（3）： 558?561.

[6] MITTAL N， SINGH U， SOHI B S. A stable energy efficient clustering protocol for wireless sensor networks [J]. Wireless networks， 2017， 23（6）： 1809?1821.

[7] 徐佳，馮鑫，楊富貴，等.最大化最小能耗概率的移動(dòng)Sink無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集方法[J].電子學(xué)報(bào)，2015，43（12）：2470?2475.

[9] 楊永健，賈冰，王杰.無(wú)線傳感器網(wǎng)絡(luò)中LEACH協(xié)議的改進(jìn)[J].北京郵電大學(xué)學(xué)報(bào)，2013，36（1）：105?109.

[8] 劉云翔，張偉.礦井無(wú)線通信網(wǎng)絡(luò)中LEACH協(xié)議的改進(jìn)[J].現(xiàn)代電子技術(shù)，2017，40（9）：66?69.

[9] LINDSEY S， RAGHAVENDRA C S. PEGASIS： Power?efficient gathering in sensor information systems [C]// Proceedings of the IEEE Aerospace Conference. Big Sky， Montana： IEEE， 2002： 3， 1125?1130.

[10] 孔國(guó)利，蘇玉.基于扇形分簇的無(wú)線傳感器網(wǎng)絡(luò)路由算法[J].現(xiàn)代電子技術(shù)，2017，40（5）：22?26.

[11] ARIOUA M， ASSARI Y E， EZZAZI I， et al. Multi?hop cluster based routing approach for wireless sensor networks [C]// The 6th International Conference on Sustainable Energy Information Technology. Madrid， Spain： Elsevier， 2016： 584?591.