基于延長(zhǎng)WSN生命周期的LEACH算法的改進(jìn)

聶芯雨 李勤勤 李 竹*

（山西師范大學(xué)物理與信息工程學(xué)院，山西 臨汾 041004）

1 引言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)是一種分布式傳感網(wǎng)絡(luò)，由大量靜止或移動(dòng)的傳感器組成，通過無(wú)線通信方式形成的一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng)，是21 世紀(jì)最重要的技術(shù)之一。WSN的網(wǎng)絡(luò)設(shè)置靈活，設(shè)備位置可以隨時(shí)更改，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對(duì)象的信息，并發(fā)送給觀察者。與傳統(tǒng)的網(wǎng)絡(luò)相比，傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)一般采用電池供電，而WSN 節(jié)點(diǎn)電池充電和更換困難，因此在保證網(wǎng)絡(luò)連通性和覆蓋度的情況下，合理利用有限的能量，令其進(jìn)行最長(zhǎng)時(shí)間的工作成為無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)考慮的首要目標(biāo)。

國(guó)內(nèi)外的研究者做了大量研究，將WSN 的路由算法分為平面型路由算法、層次型路由算法和基于定位的路由算法[1]。其中在層次型路由算法方面，提出了LEACH（Low-Energy Adaptive Clustering Hierarchy）算法，本文以LEACH算法為基礎(chǔ)，提出了一種新的算法——NLEACH（New-Low-Energy Adaptive Clustering Hierarchy）算法。該算法對(duì)LEACH算法的簇頭選舉機(jī)制進(jìn)行了改進(jìn)，新的閾值計(jì)算方案使剩余能量多的節(jié)點(diǎn)能夠以大概率擔(dān)任簇頭，使節(jié)點(diǎn)能量消耗更合理，節(jié)點(diǎn)能夠最大限度地存活，從而有效利用了每一個(gè)節(jié)點(diǎn)的能量，相較于LEACH 算法，延長(zhǎng)了網(wǎng)絡(luò)生命周期，增加了數(shù)據(jù)傳輸量。

2 層次型路由協(xié)議

無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議按照通信的邏輯結(jié)構(gòu)可分為平面型路由協(xié)議和層次型路由協(xié)議。在層次拓?fù)錂C(jī)制下，傳感器節(jié)點(diǎn)可分為骨干網(wǎng)節(jié)點(diǎn)和普通節(jié)點(diǎn)，骨干網(wǎng)節(jié)點(diǎn)是簇頭，普通節(jié)點(diǎn)是簇內(nèi)節(jié)點(diǎn)，簇頭節(jié)點(diǎn)對(duì)簇內(nèi)節(jié)點(diǎn)負(fù)責(zé)管理。層次型路由協(xié)議較平面型路由協(xié)議性能更好，層次型路由協(xié)議在運(yùn)行中簇頭節(jié)點(diǎn)會(huì)對(duì)簇內(nèi)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)進(jìn)行融合，減少不必要的信息傳輸，降低能量的消耗，而各節(jié)點(diǎn)可以等概率地當(dāng)選為簇頭，均衡了網(wǎng)絡(luò)的能量消耗，延長(zhǎng)了網(wǎng)絡(luò)生存周期。在路由計(jì)算中只有部分節(jié)點(diǎn)參與其中，大大節(jié)省了能量消耗，同時(shí)層次型路由協(xié)議可用于大規(guī)模部署的網(wǎng)絡(luò)。

3 LEACH協(xié)議

3.1 LEACH原理

LEACH協(xié)議通過隨機(jī)選擇簇頭節(jié)點(diǎn)來平均分擔(dān)網(wǎng)絡(luò)中的數(shù)據(jù)傳輸，使傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)能量得以平衡。該協(xié)議的執(zhí)行過程是周期性的，分為兩個(gè)階段：簇的建立階段和數(shù)據(jù)傳輸階段，這兩個(gè)階段一起構(gòu)成一個(gè)輪回。為了減少分簇帶來的額外能耗，簇穩(wěn)定階段遠(yuǎn)遠(yuǎn)長(zhǎng)于簇形成階段[2]。在簇的形成階段，相鄰節(jié)點(diǎn)動(dòng)態(tài)地形成簇，隨機(jī)產(chǎn)生簇頭；簇頭向外廣播消息，其它節(jié)點(diǎn)收到消息后，選擇最近的簇頭加入；在數(shù)據(jù)傳輸階段，簇內(nèi)節(jié)點(diǎn)把數(shù)據(jù)發(fā)送給簇頭，簇頭進(jìn)行數(shù)據(jù)融合并把結(jié)果發(fā)送給匯聚節(jié)點(diǎn)。

3.2 簇頭選舉方式

LEACH 算法選舉簇頭的過程如下：節(jié)點(diǎn)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)，如果生成的隨機(jī)數(shù)小于閾值T(n)，就當(dāng)選為簇頭。在每輪循環(huán)中，如果節(jié)點(diǎn)已經(jīng)當(dāng)選過簇頭，則把T(n)設(shè)置為0，該節(jié)點(diǎn)不會(huì)再次當(dāng)選為簇頭。未當(dāng)選過簇頭的節(jié)點(diǎn)，則將以T(n)的概率當(dāng)選；隨著當(dāng)選過簇頭的節(jié)點(diǎn)數(shù)目增加，剩余節(jié)點(diǎn)當(dāng)選簇頭的閾值T(n)隨之增大，節(jié)點(diǎn)產(chǎn)生小于T(n)的隨機(jī)數(shù)的概率隨之增大，所以節(jié)點(diǎn)當(dāng)選簇頭的概率增大。當(dāng)只剩下一個(gè)節(jié)點(diǎn)未當(dāng)選時(shí)，T(n)=1，表示這個(gè)節(jié)點(diǎn)一定當(dāng)選。T(n)可表示為：

其中，P是簇頭在所有節(jié)點(diǎn)中所占的百分比，即節(jié)點(diǎn)當(dāng)選為簇頭的概率，r是選舉輪數(shù)，rmod(1/P)代表這一輪循環(huán)中當(dāng)選過簇頭的節(jié)點(diǎn)個(gè)數(shù)，G是這一輪循環(huán)中未當(dāng)選過簇頭的節(jié)點(diǎn)集合[3]。

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

LEACH 算法的無(wú)線網(wǎng)絡(luò)傳輸能量模型主要由發(fā)射電路、放大電路和接收電路組成。

節(jié)點(diǎn)將Kbit的數(shù)據(jù)發(fā)送到距離為d的接收節(jié)點(diǎn)時(shí)，發(fā)射裝置消耗的能量為ETX(K,d)，由發(fā)射電路和放大電路消耗的能量所組成[4]：

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

接收節(jié)點(diǎn)接收Kbit的數(shù)據(jù)時(shí)消耗的能量為[6]：

因此，簇內(nèi)成員對(duì)簇頭進(jìn)行選舉時(shí)，普通節(jié)點(diǎn)發(fā)送Kbit的數(shù)據(jù)到簇頭后的剩余能量Ersd為：

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ù)所消耗的能量。其中EDA、Eel、ξfs、ξmp和K按照表1進(jìn)行初始化。

表1 LEACH算法部分仿真參數(shù)

3.4 LEACH協(xié)議的不足

LEACH 算法主要通過隨機(jī)選取簇頭，平均分擔(dān)通信中的數(shù)據(jù)傳輸來延長(zhǎng)生命周期，它能夠保證各節(jié)點(diǎn)等概率擔(dān)任簇頭。但在選取簇頭的過程中，因?yàn)榇仡^需要完成數(shù)據(jù)融合、與匯聚節(jié)點(diǎn)通信等工作，工作耗能大，LEACH 算法沒有考慮到節(jié)點(diǎn)的剩余能量與節(jié)點(diǎn)成為簇頭的關(guān)系，選舉簇頭存在很大的隨機(jī)性，任何節(jié)點(diǎn)都可以等概率當(dāng)選簇頭，如果能量低的節(jié)點(diǎn)擔(dān)任簇頭，在穩(wěn)定工作階段消耗能量過多時(shí)，節(jié)點(diǎn)能量會(huì)提前衰減，導(dǎo)致節(jié)點(diǎn)死亡速度加快，各節(jié)點(diǎn)的能量消耗沒有合理地均衡分配，網(wǎng)絡(luò)利用率偏低，隨之網(wǎng)絡(luò)生命周期縮短。

4 LEACH改進(jìn)算法

4.1 改進(jìn)方案

針對(duì)LEACH 協(xié)議的不足，在閾值計(jì)算中引入了表征節(jié)點(diǎn)剩余能量與系統(tǒng)剩余總能量之間比值關(guān)系k倍的剩余能量因子，將改進(jìn)算法簡(jiǎn)稱為NLEACH，改進(jìn)公式（1）如下：

其中Etot是當(dāng)前輪數(shù)所有節(jié)點(diǎn)的剩余能量總和；在簇頭選取的閾值計(jì)算方案中考慮了剩余能量因子，其中參數(shù)k越小，剩余能量因子越小，生命周期越長(zhǎng)，數(shù)據(jù)傳輸量越大，簇頭數(shù)越少，經(jīng)過多次試驗(yàn)，參數(shù)k的取值范圍為8~27。對(duì)于不同剩余能量的節(jié)點(diǎn)而言，剩余能量高的節(jié)點(diǎn)能夠以大概率當(dāng)選為簇頭，使簇頭選舉機(jī)制更為合理，節(jié)點(diǎn)能量消耗較為均衡，從而有效地利用了每一個(gè)節(jié)點(diǎn)的能量，節(jié)點(diǎn)死亡時(shí)間延遲，網(wǎng)絡(luò)生命周期延長(zhǎng)。

4.2 程序流程圖

圖1 是NLEACH 算法的程序流程圖。NLEACH 算法每輪包括簇的建立階段和數(shù)據(jù)傳輸?shù)姆€(wěn)定階段。開始時(shí)先按表1對(duì)其中的參數(shù)值進(jìn)行初始化。接著進(jìn)行簇的建立，每個(gè)節(jié)點(diǎn)隨機(jī)選擇0～1之間的數(shù)值，計(jì)算節(jié)點(diǎn)的剩余能量，如果剩余能量為0，則該節(jié)點(diǎn)死亡，如果選取的數(shù)值小于公式（6）得到的閾值，該節(jié)點(diǎn)被選為簇頭，并向全網(wǎng)廣播成為簇頭的信息。其余節(jié)點(diǎn)接收到簇頭的廣播信息后，根據(jù)廣播信號(hào)強(qiáng)度決定要加入的簇，并按照簇頭分配的時(shí)間片將采集到的數(shù)據(jù)發(fā)送給簇頭[7]，簇頭將數(shù)據(jù)融合，發(fā)送到匯聚節(jié)點(diǎn)。

5 仿真實(shí)驗(yàn)分析

利用MATLAB作為分析工具，設(shè)計(jì)以下仿真系統(tǒng)：傳感器節(jié)點(diǎn)總數(shù)為100，均勻分布在100m×100m 的被測(cè)區(qū)域中，sink節(jié)點(diǎn)位于(50，50)，循環(huán)次數(shù)r=5000。所有節(jié)點(diǎn)初始能量相同，初始值為0.5 J，數(shù)據(jù)包長(zhǎng)度為4000 bit，發(fā)送和接收數(shù)據(jù)1bit數(shù)據(jù)消耗的能量為50 nJ/bit。對(duì)生命周期和數(shù)據(jù)傳輸進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)在LEACH算法達(dá)到最優(yōu)的情況下進(jìn)行，經(jīng)過多次實(shí)驗(yàn)后，得出參數(shù)k的取值范圍為8~27。圖2 為取k=8，k=15，k=27時(shí)得出的結(jié)果。

圖2 是k為8、15、27 時(shí)的NLEACH 算法和LEACH 算法存活節(jié)點(diǎn)數(shù)和數(shù)據(jù)傳輸量及產(chǎn)生簇頭數(shù)隨時(shí)間的變化對(duì)比，橫坐標(biāo)表示時(shí)間，即當(dāng)前的輪數(shù)r，縱坐標(biāo)分別表示每一輪的存活節(jié)點(diǎn)數(shù)、數(shù)據(jù)傳輸量和產(chǎn)生簇頭數(shù)。當(dāng)存活節(jié)點(diǎn)數(shù)為0時(shí)，表示該無(wú)線傳感器網(wǎng)絡(luò)的所有節(jié)點(diǎn)死亡，即無(wú)線傳感器網(wǎng)絡(luò)生命結(jié)束，對(duì)應(yīng)時(shí)刻的數(shù)據(jù)傳輸量達(dá)到最大值。

經(jīng)過多次實(shí)驗(yàn)，結(jié)果表明：在參數(shù)k的取值范圍8~27 之間，網(wǎng)絡(luò)的生命周期會(huì)得到延長(zhǎng)。k越小，網(wǎng)絡(luò)生命周期越長(zhǎng)，數(shù)據(jù)傳輸量越大，簇頭數(shù)越少。k<8時(shí)，簇頭數(shù)不合理，產(chǎn)生的簇頭數(shù)幾乎為0；k>27時(shí)，網(wǎng)絡(luò)的生命周期幾乎得不到延長(zhǎng)。

表2 兩種算法節(jié)點(diǎn)的生命周期（輪）5次實(shí)驗(yàn)對(duì)比（k=15時(shí)）

選取k=15 的條件下，經(jīng)過5 次實(shí)驗(yàn)的對(duì)比，得到表2 的數(shù)據(jù)。LEACH算法節(jié)點(diǎn)的生命周期平均為2966輪，而改進(jìn)的NLEACH算法節(jié)點(diǎn)生命周期平均為3199輪，由此可知，改進(jìn)后的NLEACH 算法相較于LEACH 算法大約延長(zhǎng)了7.856%的網(wǎng)絡(luò)生命周期。

表3 兩種算法傳輸?shù)目倲?shù)據(jù)量（bit）5次實(shí)驗(yàn)對(duì)比（k=15時(shí)）

選取k=15 的條件下，經(jīng)過5 次實(shí)驗(yàn)的對(duì)比，得到表3 的數(shù)據(jù)。NLEACH 算法的數(shù)據(jù)傳輸量平均為158366.8bit，而LEACH算法的數(shù)據(jù)傳輸量平均為50495.2bit，故NLEACH算法與LEACH算法相比，數(shù)據(jù)傳輸量增長(zhǎng)了大約214.28%。

6 結(jié)論

在LEACH 算法的基礎(chǔ)上，NLEACH 算法通過引入節(jié)點(diǎn)剩余能量與系統(tǒng)剩余總能量之間比值關(guān)系的k倍剩余能量因子，改進(jìn)了LEACH 算法的簇頭選舉機(jī)制。NLEACH 算法的簇頭選舉機(jī)制使得傳輸過程中剩余能量多的節(jié)點(diǎn)以大概率擔(dān)任簇頭，使節(jié)點(diǎn)能量消耗更合理，從而有效地利用了每一個(gè)節(jié)點(diǎn)的能量，引入?yún)?shù)k，其取值在8~27的范圍內(nèi)，在簇頭數(shù)更合理的情況下，使算法的性能更加完善。仿真實(shí)驗(yàn)表明，參數(shù)k越小，剩余能量因子越小，網(wǎng)絡(luò)生命周期越長(zhǎng)，數(shù)據(jù)傳輸量越大。