基于能量優(yōu)化的三維空間LEACH改進算法研究

于 雷，劉海隆

(電子科技大學(xué)資源與環(huán)境學(xué)院，四川成都 611731)

1 引言

近年來，隨著無線通信技術(shù)和物聯(lián)網(wǎng)技術(shù)發(fā)展的成熟，關(guān)于無線傳感器網(wǎng)絡(luò)(WirelessSensorNetwork，WSN)的研究更注重于解決實際應(yīng)用問題[1]。WSN由大量傳感器節(jié)點和匯聚節(jié)點組成，用于監(jiān)測特定區(qū)域內(nèi)的環(huán)境參數(shù)[2]。由于WSN終端節(jié)點能量有限、分布不均等原因，可能導(dǎo)致某些節(jié)點能量消耗過快、過早死亡，縮短網(wǎng)絡(luò)的整體壽命[3]。因此，針對不同應(yīng)用場景的網(wǎng)絡(luò)設(shè)計一種低能量損耗的路由算法成為當(dāng)前WSN領(lǐng)域研究的熱點。

LEACH算法是一種最為常用的分簇式路由算法，適用于大規(guī)模、運行周期長的無線傳感器網(wǎng)絡(luò)[4]。但LEACH算法在每輪初始化階段沒有考慮節(jié)點能量，可能會加速某些網(wǎng)絡(luò)節(jié)點的死亡。另外LEACH算法默認WSN是同構(gòu)平面網(wǎng)絡(luò)[5]，能量模型過于理想化，與實際應(yīng)用場景間存在較大差異。因而出現(xiàn)了一些針對LEACH算法缺陷的改進算法。例如TEEN算法[6]通過設(shè)置閾值減少冗余信息，節(jié)約網(wǎng)絡(luò)節(jié)點能量。PEGASIS算法[7]將節(jié)點組成鏈?zhǔn)浇Y(jié)構(gòu)，每個節(jié)點只與鄰居節(jié)點通信，并選擇一個鏈?zhǔn)坠?jié)點與sink節(jié)點通信，節(jié)約了遠距能耗，也減少了簇重構(gòu)的代價。以上改進算法或沒有考慮節(jié)點剩余能量，或附帶較多的約束條件，不能很好地維持算法復(fù)雜度和算法有效性之間的平衡。

針對以上算法的不足，本文提出了一種LEACH-RE算法，該算法在簇頭選取階段考慮節(jié)點當(dāng)前的相對剩余能量，并將異構(gòu)網(wǎng)絡(luò)模型部署至立體空間中，綜合考慮電磁衰落建立能量模型，模擬真實環(huán)境中的WSN。

2 LEACH算法概述

LEACH(Low Energy Adaptive Clustering Hierarchy)算法是典型的分簇式路由協(xié)議，適用于低功耗需求下的WSN[8]。分簇式協(xié)議將網(wǎng)絡(luò)節(jié)點劃分至不同簇內(nèi)，簇頭負責(zé)收集簇內(nèi)節(jié)點的數(shù)據(jù)并匯聚到基站，因此簇頭的能耗高于其它節(jié)點。LEACH算法的基本思路就是輪換簇頭節(jié)點，使網(wǎng)絡(luò)的能量負載趨于均衡，避免少數(shù)節(jié)點的死亡導(dǎo)致網(wǎng)絡(luò)癱瘓。LEACH算法將網(wǎng)絡(luò)的整個生命周期分為多輪，每輪又分為初始化階段和穩(wěn)定運行階段。初始化階段負責(zé)簇頭選擇、網(wǎng)絡(luò)分簇及簇內(nèi)信息同步，建立樹型拓撲網(wǎng)絡(luò)。穩(wěn)定運行階段負責(zé)數(shù)據(jù)的路由傳輸。LEACH算法流程圖如圖1所示。

2.1 初始化階段

LEACH協(xié)議在初始化階段，每個網(wǎng)絡(luò)節(jié)點會產(chǎn)生一個(0，1)內(nèi)的隨機數(shù)，再與預(yù)設(shè)門限比較，如果隨機數(shù)小于門限值，則當(dāng)選為簇頭。門限值定義如下式[9]：

(1)

其中p為當(dāng)選簇頭節(jié)點概率，r為當(dāng)前周期的輪數(shù)，rmod(1/p)為該輪當(dāng)選過簇頭的節(jié)點數(shù)，G為該輪中未當(dāng)選過簇頭的節(jié)點集合。該式在網(wǎng)絡(luò)節(jié)點中平等選舉簇頭，使能量消耗不會集中在某些節(jié)點。

簇頭當(dāng)選后會向網(wǎng)絡(luò)中其它節(jié)點發(fā)送廣播信息，其它節(jié)點接收到該信號，并通過RSSI(Received Signal StrengthIndicator)判斷自身與發(fā)送節(jié)點的大致距離。節(jié)點通過比較不同的RSSI，選擇最大值加入該簇。節(jié)點請求簇頭為自己分配一個時隙。簇頭收到所有請求，并為每個節(jié)點分配獨立的時間片。

2.2 網(wǎng)絡(luò)穩(wěn)定運行階段

WSN進入穩(wěn)定運行階段后，簇頭會根據(jù)時間切片收集簇內(nèi)各節(jié)點的數(shù)據(jù)并融合，將其匯聚到sink節(jié)點，完成數(shù)據(jù)傳輸。經(jīng)過較長時間的穩(wěn)定傳輸后，網(wǎng)絡(luò)進入下一輪初始化階段。

3 LEACH算法改進

由于LEACH協(xié)議的傳輸機制是基于節(jié)點當(dāng)選簇頭次數(shù)的，算法不能兼容異構(gòu)網(wǎng)絡(luò)；其次在網(wǎng)絡(luò)初始化階段也沒有考慮網(wǎng)絡(luò)節(jié)點的當(dāng)前剩余能量。大大降低了普適性。

因此本文提出了LEACH-RE算法，主要針對兩個方面對LEACH算法進行改進，簇頭選舉閾值和原算法適用范圍。

3.1 三維空間傳感器節(jié)點布設(shè)

假設(shè)WSN由m個隨機部署在三維空間中的傳感器組成，網(wǎng)絡(luò)節(jié)點分布如圖2所示，對應(yīng)的網(wǎng)絡(luò)節(jié)點集合為：

N={n1，n2，n3，…，nm}

(2)

其它條件假設(shè)如下：

1)匯聚節(jié)點位于立方體空間S的中央，傳感器節(jié)點在部署后位置不再改變。

2)傳感器節(jié)點之間、傳感器節(jié)點和匯聚節(jié)點之間可以數(shù)據(jù)傳輸。并且網(wǎng)絡(luò)節(jié)點能夠通過信號接受強度(RSSI)近似計算發(fā)送者信號直線傳輸距離。

3)發(fā)送節(jié)點會根據(jù)接收節(jié)點的距離自動調(diào)節(jié)功率，減少能量消耗冗余。

4)網(wǎng)絡(luò)節(jié)點在空閑時處于休眠狀態(tài)，即不考慮能量消耗。

3.2 異構(gòu)網(wǎng)絡(luò)

LEACH算法的一個重要前提為分布均勻的同構(gòu)網(wǎng)絡(luò)，即網(wǎng)絡(luò)節(jié)點初始能量是相同的；不同節(jié)點每次收發(fā)信號所消耗的能量也是相同的。滿足以上的假設(shè)條件，根據(jù)節(jié)點當(dāng)選簇頭次數(shù)考慮簇頭選舉概率才是有效的，但是在真實的復(fù)雜環(huán)境下，很難滿足上述條件。首先WSN的特點是低成本和高可靠性，大規(guī)模網(wǎng)絡(luò)中不同節(jié)點在硬件和軟件上實現(xiàn)統(tǒng)一標(biāo)準(zhǔn)難度很大，并且會影響網(wǎng)絡(luò)可擴展性。其次WSN一般是自組織網(wǎng)絡(luò)，復(fù)雜環(huán)境下設(shè)備節(jié)點會因意外情況容易掉電、重新入網(wǎng)，或者因后續(xù)網(wǎng)絡(luò)規(guī)模的擴展需求而加入新的節(jié)點設(shè)備，如果每次設(shè)備入網(wǎng)都需要考慮網(wǎng)絡(luò)整體拓撲結(jié)構(gòu)保證每個節(jié)點的分布均勻性，會造成大量人力成本浪費，也會破壞WSN的自組織性。所以選取異構(gòu)網(wǎng)絡(luò)作為LEACH協(xié)議的使用對象是合理的，同時也拓寬了原算法的適用范圍。

本文將網(wǎng)絡(luò)節(jié)點分為一般節(jié)點和高級節(jié)點，不同節(jié)點的初始能量不同，并且當(dāng)選簇頭的概率也不同。

3.3 基于相對剩余能量的簇頭選舉

LEACH算法選舉簇頭時只考慮當(dāng)前節(jié)點當(dāng)選簇頭的次數(shù)，無法很好地解決復(fù)雜環(huán)境下的WSN能耗問題。參選節(jié)點的當(dāng)前剩余能量在一定程度上能夠反映節(jié)點未來的生存狀況。網(wǎng)絡(luò)節(jié)點剩余能量越多，則該節(jié)點的生存周期期望越大，有能力承擔(dān)較多信號收發(fā)帶來的能量消耗，因此更適合當(dāng)選簇頭節(jié)點。在此基礎(chǔ)上，再考慮參選節(jié)點的初始能量，如果網(wǎng)絡(luò)節(jié)點的當(dāng)前剩余能量與初始能量的比值越小，則說明此節(jié)點在歷史周期中消耗的能量比網(wǎng)絡(luò)節(jié)點平均能量消耗要多，為了減輕該節(jié)點的負載，改善生存狀況，應(yīng)該減少它當(dāng)選簇頭的概率。

綜上所述，本文的一般節(jié)點簇頭選舉概率公式和高級節(jié)點簇頭選舉概率用公式可以分別表示為

(3)

(4)

其中En為當(dāng)前節(jié)點的剩余能量，E0表示一般網(wǎng)絡(luò)節(jié)點的初始能量，1+α表示高級網(wǎng)絡(luò)節(jié)點初始能量和一般網(wǎng)絡(luò)節(jié)點初始能量的倍數(shù)，因此E0(1+α)表示高級節(jié)點的初始能量。pn表示每輪選舉中一般節(jié)點當(dāng)選簇頭的概率，pa表示每輪選舉中高級節(jié)點當(dāng)選簇頭的概率，Gn為該輪中未當(dāng)選過簇頭的一般網(wǎng)絡(luò)節(jié)點的集合，Ga為該輪中未當(dāng)選過簇頭的高級網(wǎng)絡(luò)節(jié)點的集合。簇頭選舉階段結(jié)束，進行簇內(nèi)信息同步。當(dāng)整個網(wǎng)絡(luò)初始化完成后，節(jié)點便按照正常流程進入穩(wěn)定運行階段。

無線通信能量消耗模型為文獻[10]中收發(fā)機通信模型，構(gòu)成如圖3所示。模型包含發(fā)送信號能量消耗和接收信號能量消耗，其中發(fā)送信號消耗的能量又可分為發(fā)射電路損耗和功率放大損耗，公式如下式所示[11]：

(5)

(6)

其中，l表示網(wǎng)絡(luò)節(jié)點發(fā)送或接收的數(shù)據(jù)包長度(bit)，Eelec表示網(wǎng)絡(luò)節(jié)點發(fā)送或接收單位bit的數(shù)據(jù)所消耗的能量，d表示發(fā)送節(jié)點和接收節(jié)點之間的直線傳播距離，節(jié)點i和節(jié)點j之間的距離如下式

(7)

當(dāng)傳輸距離小于閾值d0時，只考慮電磁波的直射，功率放大損耗采用自由空間損耗模型；當(dāng)傳輸距離大于閾值d0時，還考慮電磁波的反射、折射和繞射，功率放大損耗采用多徑損耗模型。

接收信號消耗的能量為

ERX(l)=lEelec

(8)

因此無線傳感器網(wǎng)絡(luò)節(jié)點收發(fā)信號的能量模型如圖3所示。

數(shù)據(jù)融合過程極其復(fù)雜[11]，本文將其消耗的能量過程簡化為

EDA(l)=lEda

(9)

其中Eda為融合單位bit所消耗的能量。本文假設(shè)簇頭節(jié)點會根據(jù)事先設(shè)定的數(shù)據(jù)融合率將本簇簇內(nèi)節(jié)點上傳的數(shù)據(jù)進行融合，去除部分?jǐn)?shù)據(jù)冗余。

4 仿真及結(jié)果分析

通過MATLAB對LEACH-RE算法進行驗證。假設(shè)100個網(wǎng)絡(luò)節(jié)點(包含一般節(jié)點和高級節(jié)點)隨機分布在100m×100m×40m空間中，sink節(jié)點位于空間正中心，即(50m，50m，20m)，其它仿真參數(shù)初始化如下表所示：

表1 仿真參數(shù)

通過仿真運行，結(jié)果下圖所示。

從仿真結(jié)果中可以分析得出循環(huán)周期與網(wǎng)絡(luò)節(jié)點存活數(shù)量的關(guān)系以及循環(huán)周期與無線傳感器網(wǎng)絡(luò)剩余能量的關(guān)系。在圖4和圖5中，‘x’表示死亡節(jié)點，可見LEACH-RE算法節(jié)點存活情況優(yōu)于LEACH算法。從圖6可知，在1000輪周期后，LEACH-RE算法中的節(jié)點生存狀況明顯優(yōu)于LEACH算法中的節(jié)點生存狀況，這是因為LEACH-RE算法改善單個節(jié)點的生存狀況，從而均衡網(wǎng)絡(luò)節(jié)點的能量負載。從圖7可知WSN的能量變化，曲線斜率表示網(wǎng)絡(luò)能量消耗速度，可以看出LEACH-RE算法的整體網(wǎng)絡(luò)剩余能量高于LEACH算法中的整體網(wǎng)絡(luò)剩余能量，且網(wǎng)絡(luò)能量消耗速度慢于原算法，證明改進路由協(xié)議能夠有效均衡網(wǎng)絡(luò)能量，延長網(wǎng)絡(luò)生存周期。

5 結(jié)語

通過在三維空間的LEACH算法的基礎(chǔ)上結(jié)合網(wǎng)絡(luò)節(jié)點的異構(gòu)性，引入相對剩余能量減少低能量節(jié)點當(dāng)選簇頭的概率，從而實現(xiàn)算法有效改進，通過MATLAB平臺對WSN存活節(jié)點數(shù)量和整體網(wǎng)絡(luò)剩余能量兩項指標(biāo)進行仿真驗證，得到如下結(jié)論：

1)設(shè)置100個網(wǎng)絡(luò)節(jié)點，網(wǎng)絡(luò)經(jīng)過1500輪周期運行后，LEACH-RE算法存活28個節(jié)點，原算法只存活8個節(jié)點，改進算法較原算法提升250%；

2)LEACH-RE算法在1500輪周期左右耗盡能量，LEACH算法在1300輪周期耗盡能量，改進算法較原算法提升15%。結(jié)果證明改進算法能夠有效均衡網(wǎng)絡(luò)能量，延長網(wǎng)絡(luò)生存周期。