何書前 嚴晨 鄧正杰 石春

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

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

中圖分類號： TN919?34? ? ? ? ? ? ? ? ? ? ? ? ?文獻標(biāo)識碼： A? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號： 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é)點能量受限的條件下，通過網(wǎng)絡(luò)協(xié)議有效保證整個網(wǎng)絡(luò)的生命周期和傳輸數(shù)據(jù)量，一直是無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）研究的熱點問題[1]。LEACH協(xié)議[2]作為WSNs能量有效分簇路由選擇協(xié)議的代表，在分層次無線傳感器路由協(xié)議應(yīng)用中得到了很高的關(guān)注，并在其基礎(chǔ)上發(fā)展了很多路由協(xié)議，如EEHC[3]，HEED[4]，DEEC[5]等。

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

1? LEACH算法概述

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

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

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

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

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

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

2? 改進的LEACH算法

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

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

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

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

[d0=EfsEmp]? （2）

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

2） 計算節(jié)點剩余能量[El]。

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

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

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

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

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

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

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

3? 仿真實驗與分析

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

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

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

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

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

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

簇頭接收和融合[k] bit數(shù)據(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個節(jié)點且隨機地分布在100 m×100 m范圍內(nèi)，Sink節(jié)點的位置固定，每個節(jié)點的初始能量為0.5 J，仿真參數(shù)如表1所示。

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

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

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

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

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

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

4? 結(jié)? 語

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

參考文獻

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

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

[8] 劉云翔，張偉.礦井無線通信網(wǎng)絡(luò)中LEACH協(xié)議的改進[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] 孔國利，蘇玉.基于扇形分簇的無線傳感器網(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.