王亮云 陳建 馬宇豪 管星宇

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

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

0 引言

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

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

1 ? LEACH協(xié)議

1.1 ?LEACH原理

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

1.2 簇頭選舉方式

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

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

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

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

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

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

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

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

簇頭發(fā)送Kbit數(shù)據(jù)到基站并進(jìn)行數(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é)議的不足

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

2 LEACH改進(jìn)算法

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

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

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

3 仿真試驗(yàn)分析

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

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

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

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

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

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

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

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

[參考文獻(xiàn)]

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

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

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

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

（編輯 傅金睿）