基于延長WSN生命周期的LEACH算法的改進措施研究

王亮云 陳建 馬宇豪 管星宇

摘 要：無線傳感器網(wǎng)絡(luò)的節(jié)點總能量有限，如何有效利用節(jié)點能量，延長網(wǎng)絡(luò)節(jié)點存活時間，是網(wǎng)絡(luò)設(shè)計的重要內(nèi)容。文章在LEACH算法的基礎(chǔ)上提出一種改進算法—RLEACH算法。該算法通過在閾值計算公式中引入當前節(jié)點剩余能量與網(wǎng)絡(luò)中存活節(jié)點平均能量的比值，并且將β作調(diào)節(jié)因子，提高了剩余能量高于平均值的節(jié)點當選簇頭的概率，從而實現(xiàn)了對每一個節(jié)點能量的優(yōu)化利用。經(jīng)過試驗仿真，結(jié)果表明，RLEACH算法與LEACH算法相比，網(wǎng)絡(luò)生命周期延長約28.9%，傳輸數(shù)據(jù)量增長約196.9%。

關(guān)鍵詞：LEACH算法，無線傳感網(wǎng)絡(luò)，簇頭選取，網(wǎng)絡(luò)平均能量

0 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是一種分布式傳感網(wǎng)絡(luò)，其主要以LEACH算法為基本算法，網(wǎng)絡(luò)的末梢是一個可以感知和檢查外部世界的傳感器。WSN以無線的方式與外界進行聯(lián)系，因此其具備易隨時隨地設(shè)置和跟互聯(lián)網(wǎng)進行有線或無線方式的連接等優(yōu)點。但相較于傳統(tǒng)式的網(wǎng)絡(luò)和其他傳感器，無線傳感器網(wǎng)絡(luò)具有網(wǎng)絡(luò)拓撲結(jié)構(gòu)的不確定性、控制方式不集中，安全性不高的缺點。WSN在可靠的環(huán)境監(jiān)測、各種商業(yè)和軍事應(yīng)用中都很重要。例如，聲學(xué)、安全系統(tǒng)的各個方面，是我國科學(xué)發(fā)展的重要支柱。

WSN的路由算法以邏輯結(jié)構(gòu)方式分為平面型路由算法和層次型路由算法，其中在層次型路由算法方面，提出了LEACH（Low-Energy Adaptive Clustering Hierarchy）算法。伴隨著科技的高速發(fā)展，LEACH算法能量利用率低，生存周期短，抗干擾能力差的缺點日益突出[1]。本文提出一種新型算法—RLEACH（Radical-Low-Energy Adaptive Clustering Hierarchy），對選取簇頭節(jié)點環(huán)節(jié)進行改良。本算法對閾值進行修改，使其值與當前節(jié)點與網(wǎng)絡(luò)平均能量的比值相關(guān)聯(lián)，從而使得WSN生產(chǎn)周期延長，降低循環(huán)的總能量。

1 ? LEACH協(xié)議

1.1 ?LEACH原理

LEACH協(xié)議是一種基于分簇的路由協(xié)議，它通過在不同的時間點將負載分配給所有的節(jié)點來使全局能量使用最小化。它要求節(jié)點自愿成為高能量簇頭，在不同時刻，每個節(jié)點都有從集群中的節(jié)點獲取數(shù)據(jù)和融合數(shù)據(jù)來獲得聚合信號，并將該信號發(fā)送到基站。LEACH協(xié)議的運行過程有簇的建立階段和數(shù)據(jù)傳輸階段，在簇的建立階段，相鄰節(jié)點隨機形成簇頭;在數(shù)據(jù)通信階段，簇內(nèi)節(jié)點把數(shù)據(jù)發(fā)送給簇頭，簇頭進行數(shù)據(jù)融合并把結(jié)果發(fā)送給匯聚節(jié)點。為了減少分簇帶來的額外能耗，簇穩(wěn)定階段遠遠長于簇形成階段[2]。

1.2 簇頭選舉方式

LEACH算法在運行過程中不斷地循環(huán)執(zhí)行簇的重構(gòu)。算法按輪進行操作，每一輪操作由建立簇和傳輸數(shù)據(jù)兩個階段組成。當算法處于建立階段時，算法在每個節(jié)點中隨機產(chǎn)生一個介于0～1之間的數(shù)，并將隨機產(chǎn)生的數(shù)與閾值T（n）作比較，若隨機產(chǎn)生的數(shù)小于T（n），則命令該節(jié)點當選簇頭。若節(jié)點在運行輪數(shù)前已經(jīng)當選過簇頭，則設(shè)閾值為0，使該節(jié)點在運行輪次中不會再次成為簇頭;若節(jié)點未當選過簇頭，則該節(jié)點將以T（n）的概率當選。由此可知，隨著輪數(shù)的增加，未當選過簇頭的節(jié)點數(shù)目將會減少，剩余節(jié)點的閾值T（n）增大，從而節(jié)點產(chǎn)生小于T（n）的隨機數(shù)的概率增大，故節(jié)點當選簇頭的概率增大，最終所有節(jié)點均當選過簇頭[3]。T（n）可表示為：

公式中p是預(yù)先設(shè)定的節(jié)點當選為簇頭的概率（這里設(shè)為5%）[4]，r是當前輪次（0～1/p-1），rmod（1/p）是當前輪數(shù)中已經(jīng)當選過簇頭的節(jié)點個數(shù)，G是未當選過簇頭的節(jié)點的集合。

1.3 網(wǎng)絡(luò)傳輸能量模型

LEACH算法模型由發(fā)射、放大和接收部分組成，具體如下。

（1）發(fā)射。若已知節(jié)點發(fā)送的數(shù)據(jù)量Kbit，數(shù)據(jù)傳輸距離d，則發(fā)射裝置消耗的能量ETX（K，d）的表達式為：

其中d0為門限距離，其值為;ξfs、ξmp分別表示自由空間模型和多徑衰減模型下功率放大器的能耗系數(shù);若發(fā)射裝置到接收節(jié)點的距離d≤d0時，功率放大器采用多徑衰減模型ξmpd4;d>d0時，功率放大器采用自由空間模型ξfsd2;Eel表示每發(fā)送或者接收1bit數(shù)據(jù)時電路消耗的能量;K表示傳輸數(shù)據(jù)包的長度。

（2）接收。節(jié)點接收Kbit數(shù)據(jù)后消耗的能量為：

其中Ei是第i個節(jié)點的能量（i=1， 2， …， 100）;dmin為普通節(jié)點與簇頭的最近距離。

簇頭發(fā)送Kbit數(shù)據(jù)到基站并進行數(shù)據(jù)融合后的剩余能量為：

其中EDA為簇頭數(shù)據(jù)融合1bit數(shù)據(jù)所消耗的能量。各參數(shù)初始化值EDA=5×10-9 J、Eel=5×10-8 J、ξfs=10-11 J、ξm=1.3×10-15 J、K=4 000 bit。

1.4 ?LEACH協(xié)議的不足

由于在傳輸信息的過程中簇頭起著重要作用，故在建立傳輸模型環(huán)節(jié)選擇簇頭也至關(guān)重要。由于LEACH算法選舉簇頭的方式有很大的隨機性，所以會導(dǎo)致能量分配不均衡，進而導(dǎo)致能量傳遞速率大幅度降低。當能量低的節(jié)點當選為簇頭時，此簇頭會較快消亡，不利于生命周期的延長以及能量的傳輸。

2 LEACH改進算法

考慮到LEACH的不足以及節(jié)點剩余能量的影響，在T（n）計算式的基礎(chǔ)上引入當前節(jié)點剩余能量與網(wǎng)絡(luò)中存活節(jié)點平均能量的比值，并且為了使比值的大小更合理，再引入調(diào)節(jié)因子β，改進后的T（n）公式如下：

其中Etot是當前輪數(shù)所有節(jié)點的剩余能量總和;Nalive是當前輪數(shù)存活的節(jié)點數(shù);β是調(diào)節(jié)因子（且由實驗可得β取值范圍為0.01<β<0.314時，網(wǎng)絡(luò)生命周期與傳輸數(shù)據(jù)量得以改進，β<0.01時，選取簇頭概率過低，不利于傳輸數(shù)據(jù)量的增加，β>0.314時，選取簇頭概率過高，不利于延長網(wǎng)絡(luò)生命周期）;若對閾值進行如此設(shè)定，即致使能量高于平均值的節(jié)點大概率當選簇頭，使得能量利用更加合理，延長節(jié)點壽命，進而延長網(wǎng)絡(luò)生命周期。

圖1是RLEACH算法的程序流程圖，算法首先進行初始化參數(shù)等一系列初步準備工作，然后進入建立簇頭的階段：在每個節(jié)點中按照公式（6）T（n）隨機產(chǎn)生數(shù)值，并且將該數(shù)值作為當前輪數(shù)該節(jié)點當選為簇頭的概率，隨后計算并保存存活節(jié)點的個數(shù)，便于之后下一輪數(shù)公式（6）T（n）的計算，當隨機產(chǎn)生的數(shù)值小于公式（6）得到的閾值時，將該節(jié)點作為簇頭。簇內(nèi)節(jié)點將所要發(fā)送的數(shù)據(jù)傳輸至簇頭，簇頭接收數(shù)據(jù)，隨后將其融合，最后發(fā)送至匯聚節(jié)點。

3 仿真試驗分析

在MATLAB中按照如下方式進行節(jié)點布局：節(jié)點總數(shù)為100個，將節(jié)點隨機分布在100 m×100 m的區(qū)域中， sink節(jié)點位于中心點，進行5 000輪循環(huán)。每一節(jié)點具有的初始能量為0.5 J，故系統(tǒng)初始總能量為50 J，節(jié)點發(fā)送和接收數(shù)據(jù)消耗的能量為50 nJ/bit。在多次實驗后得出，當β值小于0.314時，網(wǎng)絡(luò)生命周期開始增大。為了使實驗現(xiàn)象更加明顯，實驗中取β值分別為0.053，0.075，0.095，開始進行仿真，并隨后做出對比。下圖為未做改進的LEACH與取β=0.095，β=0.075，β=0.053時得出的結(jié)果。

圖2體現(xiàn)了網(wǎng)絡(luò)存活周期：橫坐標為時間（輪數(shù)），縱坐標為當前剩余節(jié)點個數(shù)。由于網(wǎng)絡(luò)在傳輸后期時能量較低，故在分析剩余節(jié)點個數(shù)時，將分析基準設(shè)定在剩余節(jié)點數(shù)量為20時的輪數(shù)，并將此刻對應(yīng)的輪數(shù)設(shè)定為截至輪數(shù)。由圖2可得，RLEACH算法在實驗所給不同參數(shù)取值的條件下，生存周期有顯著提升。

圖3體現(xiàn)了傳輸?shù)男畔⒛芰浚簷M坐標為時間（輪數(shù)），縱坐標為截至當前輪數(shù)傳遞信息量。由圖3可得，RLEACH算法在實驗所給不同參數(shù)取值的條件下，傳輸數(shù)據(jù)能量有顯著提升。

由圖2、圖3可得，RLEACH算法在生命周期和傳輸數(shù)據(jù)量方面皆比LEACH算法效果好，且當參數(shù)β的取值范圍小于0.095時，網(wǎng)絡(luò)生命周期、數(shù)據(jù)傳輸量皆與β值成反比關(guān)系，故在實際應(yīng)用中應(yīng)當按照一定的前提條件選擇β值，以達到理想的效果。

為了對生命周期有更好的比較，列出表1，對生命周期的比較進行說明。為了減少實驗的偶然性，做五組實驗并得出相關(guān)數(shù)據(jù)。從結(jié)果可知，RLEACH算法在β為0.075時相較原LEACH算法延長了約28.9%的生命周期。

為了對傳輸數(shù)據(jù)量有更好的比較，列出表2，對傳輸數(shù)據(jù)量的比較進行說明。為了減少實驗的偶然性，做五組實驗并得出相關(guān)數(shù)據(jù)。從結(jié)果可知，RLEACH算法在β為0.075時相較原LEACH算法增長了約196.9%的傳輸數(shù)據(jù)量。

4 ? 結(jié)語

在原有LEACH算法的基礎(chǔ)上，RLEACH算法通過引入節(jié)點剩余能量與節(jié)點能量平均值比值的β倍作為閾值，合理地對能量進行分布與使用，在β=0.075時，相較原LEACH算法延長了約28.9%的生命周期，增長了約196.9%的傳輸數(shù)據(jù)量。該算法雖在一定程度上減弱了隨機性，但是由于選舉簇頭時根據(jù)節(jié)點生成的隨機數(shù)的大小進行選舉，因此還是有概率使得低能量的節(jié)點當選簇頭，故期待下一步在此方面做出完善。

[參考文獻]

[1]周志強，劉森，王允臣.無線傳感器網(wǎng)絡(luò)LEACH路由協(xié)議的改進算法[J].科技資訊，2012（17）：15，17.

[2]武春濤，胡艷軍.無線傳感器網(wǎng)絡(luò)LEACH算法的改進[J].計算機技術(shù)與發(fā)展，2009（3）：80-83.

[3]聶芯雨，李勤勤，李竹.基于延長WSN生命周期的LEACH算法的改進[J].電腦與電信，2020（8）：27-30.

[4]王薇.無線傳感器網(wǎng)絡(luò)低功耗分級路由協(xié)議研究[D].杭州：浙江大學(xué)，2006.

（編輯 傅金睿）