基于LEACH協(xié)議的能量優(yōu)化方法

李 波，郝麗君，陳嵩杰，唐孟麒

(遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001)

0 引 言

在無線傳感器網(wǎng)絡(luò)[1](wireless sensor network，WSN)中，路由協(xié)議主要負(fù)責(zé)將節(jié)點采集的數(shù)據(jù)逐跳轉(zhuǎn)發(fā)至基站(base station，BS)。而傳感器節(jié)點計算、存儲和通信能力有限，其資源的局限性[2]給路由協(xié)議的設(shè)計帶來一定的挑戰(zhàn)[3]。研究與之相適應(yīng)的路由協(xié)議已成為當(dāng)今熱點[4，5]。

現(xiàn)有路由協(xié)議研究分為平面路由[6，7]和分簇路由[8]。代表性的低功耗自適應(yīng)分簇路由[9](low energy adaptive clustering hierarchy，LEACH)協(xié)議可將每個工作周期分為成簇和數(shù)據(jù)傳輸兩階段。其中，成簇階段包括簇頭選取和普通節(jié)點入簇兩個步驟。該協(xié)議在一定程度上延長了網(wǎng)絡(luò)的生命周期，但在兩個階段考慮的影響因素欠缺，存在網(wǎng)絡(luò)能耗不均和邊緣節(jié)點早亡問題。針對成簇階段，文獻(xiàn)[10]引入成本函數(shù)計算最佳簇頭數(shù)目，利用優(yōu)化檢測范圍內(nèi)簇頭分布來均衡網(wǎng)絡(luò)能耗。文獻(xiàn)[11]借助于節(jié)點能量和簇內(nèi)平均距離改進(jìn)成簇方式，利用不均勻成簇分配網(wǎng)絡(luò)能耗。文獻(xiàn)[12]引入剩余能量因子與節(jié)點密度，提出了一種簇頭節(jié)點和非簇頭節(jié)點間雙向選取模式，實現(xiàn)了簇頭和非簇頭間的能耗平衡。針對數(shù)據(jù)傳輸階段，文獻(xiàn)[13]引入了中繼節(jié)點用于均衡簇頭能耗。文獻(xiàn)[14]由節(jié)點與BS間距離，采用單跳與多跳相結(jié)合的數(shù)據(jù)傳輸方式，延長了邊緣節(jié)點的生命周期。而文獻(xiàn)[15]由節(jié)點間距離動態(tài)調(diào)整發(fā)射功率，延長了網(wǎng)絡(luò)節(jié)點的生命周期。可見，這些路由協(xié)議在不同程度上延長了網(wǎng)絡(luò)生命周期，但網(wǎng)絡(luò)能耗不均、節(jié)點早亡問題依然存在。

針對上述問題，本文對LEACH協(xié)議在成簇和數(shù)據(jù)傳輸兩個階段分別進(jìn)行優(yōu)化。在成簇階段，結(jié)合距離與剩余能量改進(jìn)閾值公式，由節(jié)點密度限制成簇規(guī)模。在數(shù)據(jù)傳輸階段，簇內(nèi)采用結(jié)合輪詢機(jī)制的單跳傳輸方式。

1 系統(tǒng)模型

1.1 能量模型

本文對WSN做出如下假設(shè)：100個WSN節(jié)點隨機(jī)分布在面積為100×100 m2的監(jiān)測區(qū)域內(nèi)。各節(jié)點同構(gòu)、編號獨立、能量有限；BS能量無限且位于監(jiān)測區(qū)域的中心位置；BS和節(jié)點一經(jīng)布置，位置固定；所有節(jié)點可感知自身位置；通信鏈路具有對稱性，可由收到的信息信號強(qiáng)度計算同發(fā)送者的近似距離；所有滿足條件的節(jié)點可作為簇頭，不滿足條件則退化為普通節(jié)點。

由一階無線電模型[16]知，在節(jié)點i和節(jié)點j間傳輸Lbit數(shù)據(jù)所需能量由式(1)給出

(1)

式中：Eelec為節(jié)點收發(fā)單位數(shù)據(jù)所需的能量，dij分別為節(jié)點i和節(jié)點j間的距離，εmp和εfs分別為電路放大器在多徑衰落和自由衰落情形下的功放系數(shù)。

于是，能量模型的距離閾值d0可定義為

(2)

假設(shè)普通節(jié)點與簇頭通信采用自由衰落模型，簇頭間通信采用多徑衰落模型，能耗模型如圖1所示。其中，節(jié)點接收數(shù)據(jù)所需的能量與節(jié)點間距離無關(guān)，接收Lbit數(shù)據(jù)所需的能量E為

E=L×Eelec

(3)

簇頭節(jié)點融合Lbit數(shù)據(jù)所需的能量EDA為

EDA=L×Epda

(4)

式中：Epda為簇頭融合單位數(shù)據(jù)所需的能量。

1.2 LEACH協(xié)議的分析

在LEACH協(xié)議中，簇的形成包括簇頭選取和成簇兩個階段。簇頭選取是節(jié)點在每周期內(nèi)獲得一個[0，1]之間的隨機(jī)數(shù)，若該數(shù)小于閾值Ti，則為簇頭。普通節(jié)點入簇可采用就近原則。簇頭在數(shù)據(jù)傳輸階段與BS進(jìn)行單跳通信，閾值Ti定義為[17]

(5)

式中：p為簇頭的占比，r為當(dāng)前網(wǎng)絡(luò)周期數(shù)目，G為在前序周期中未作為簇頭的節(jié)點集合。由于LEACH協(xié)議在選取簇頭時未充分考慮節(jié)點剩余能量和位置等因素，隨機(jī)選取簇頭會導(dǎo)致距BS較遠(yuǎn)的簇頭因較大的數(shù)據(jù)傳輸能耗而早亡；距離BS較近的簇頭因承擔(dān)自身數(shù)據(jù)傳輸和作為中繼節(jié)點，在BS附近的簇頭能耗較大，消亡速度快，易出現(xiàn)“熱區(qū)”。

2 LEACH協(xié)議的改進(jìn)

在簇頭數(shù)優(yōu)化階段，可根據(jù)能量模型計算節(jié)點數(shù)目與簇頭數(shù)目的比例。在簇頭選取階段，可由節(jié)點剩余能量、位置和簇密度改進(jìn)閾值公式。在歸屬成簇階段，可引入簇規(guī)模密度限制成簇規(guī)模。在簇頭更新階段，可引入能耗速率，利用周期總能耗與各簇平均能耗判定簇頭是否更換。在傳輸數(shù)據(jù)階段，可融合采用“熱區(qū)”內(nèi)單跳方式與非“熱區(qū)”多跳方式，自適應(yīng)選擇傳輸路徑，防止“熱區(qū)”簇頭能耗過大。

2.1 簇頭數(shù)目的優(yōu)化

首先，由能量模型計算WSN的節(jié)點總數(shù)和簇頭數(shù)目間的比例，用于數(shù)據(jù)融合與數(shù)據(jù)發(fā)送簇頭的能耗ECH定義為

(6)

用于感知和數(shù)據(jù)發(fā)送的普通節(jié)點能耗Enon-CH為

(7)

由此，周期內(nèi)總能耗Etotal可表示為

Etotal=ECH+Enon-CH=(2N-k)LEelec+NLEpda+

(8)

?r2ρ(r，θ)drdθ

(9)

假設(shè)覆蓋區(qū)域面積大小為M×M，簇覆蓋范圍為圓形，則每個簇的覆蓋半徑r記為

(M×M)/k=πr2

(10)

于是，式(9)可改寫為

(11)

由于節(jié)點均勻分布，將密度函數(shù)ρ=1/M2k代入式(11)有

(12)

令?Etotal/?k=0，則最優(yōu)簇頭的數(shù)目kopt為

(13)

由此，網(wǎng)絡(luò)總節(jié)點與新的簇頭比例p可表示為

p=kopt/N

(14)

2.2 簇頭選取的改進(jìn)

(15)

式中：Ei(t) 為t時刻節(jié)點i剩余能量，Ei(0) 為節(jié)點i的能量初值。

為避免低能量節(jié)點當(dāng)選簇頭，即節(jié)點的剩余能量低于所在簇平均能量i(0) 被使用，在簇頭更新時，令此類節(jié)點沒有機(jī)會競選簇頭。隨著網(wǎng)絡(luò)整體能量降低，相對低能節(jié)點仍有機(jī)會競選簇頭。低能節(jié)點判斷條件如下

(16)

(17)

接下來，計算網(wǎng)絡(luò)中BS與存活節(jié)點間的平均歐幾里得距離Dave(t)

(18)

(19)

由于節(jié)點能量與網(wǎng)絡(luò)總能量隨運行次數(shù)增加而降低，所以節(jié)點剩余能量的比重應(yīng)降低，而距離應(yīng)增加。為此，引入?yún)?shù)α自適應(yīng)調(diào)節(jié)剩余能量和距離因素的權(quán)重

(20)

α=1/γ(t)

(21)

其中，γ(t) 為t時刻簇頭更新次數(shù)。可以看出，在初始簇頭更新時，剩余能量權(quán)重α較小。隨著運行周期的增加，節(jié)點能量與網(wǎng)絡(luò)總能量均降低，剩余能量權(quán)重α逐漸增大。

綜上，改進(jìn)后閾值Ti可定義為

(22)

2.3 普通節(jié)點歸屬成簇的改進(jìn)

LEACH協(xié)議易產(chǎn)生過大簇或過小簇，不利于均衡網(wǎng)絡(luò)能量和延長工作周期。

(23)

式中：kopt限制成簇的最大密度。

(24)

可以看出，上述公式的成簇方式均為就近原則，即一次成簇。首輪簇頭選取完成后進(jìn)行廣播，普通節(jié)點聯(lián)合就近原則和簇密度規(guī)模申請入簇。當(dāng)簇密度到達(dá)上限時，拒絕節(jié)點入簇請求并指示其應(yīng)加入次優(yōu)簇。以此類推，保證所有WSN內(nèi)的節(jié)點都有歸屬。

2.4 簇頭更新的改進(jìn)

若每周期都采取泛洪式方法更新簇頭，則會增加網(wǎng)絡(luò)負(fù)載。由于節(jié)點能耗受周圍環(huán)境和感知數(shù)據(jù)量影響，還需考慮能耗速率參數(shù)。當(dāng)周期內(nèi)簇頭更替方法為簇內(nèi)更替時，能耗速率決定是否更換簇頭。

假設(shè)所有簇合集為C={c1，c2，c3，…，c?}，每周期內(nèi)簇ci的能耗為Eci，則周期內(nèi)總能耗Etotal可表示為

(25)

于是，周期內(nèi)的各簇平均能耗Eave為

(26)

這樣，是否在下周期內(nèi)簇需更換簇頭，只需判斷Eci和Eave：當(dāng)Eci≤Eave時，表明簇頭承擔(dān)負(fù)載較小，預(yù)測簇頭下周期可正常工作，無需更換；當(dāng)Eci>Eave時，表明簇頭承擔(dān)負(fù)載較大，為保證下周期正常工作，應(yīng)更換簇頭。

2.5 傳輸數(shù)據(jù)的改進(jìn)

本文對簇內(nèi)數(shù)據(jù)采用結(jié)合輪詢機(jī)制的單跳方式傳輸。若節(jié)點因能量耗盡而消亡，則在輪詢表中刪除該節(jié)點，順序更新其它節(jié)點的位置。簇間數(shù)據(jù)傳輸采用“熱區(qū)”內(nèi)單跳與非“熱區(qū)”多跳相結(jié)合方式。由節(jié)點剩余能量權(quán)重自適應(yīng)選擇路徑傳輸，避免“熱區(qū)”簇頭能耗過大，其“熱區(qū)”的范圍Range記為

(27)

式中：Dis(ci，BS) 為BS與簇頭的距離，?為網(wǎng)絡(luò)中簇頭數(shù)目，位于“熱區(qū)”范圍的簇頭采用單跳方式傳輸數(shù)據(jù)，無需中繼節(jié)點。其判斷條件為

Dis(ci，BS)≤Range，(i=1，2，…，?)

(28)

(29)

3 仿真實驗與結(jié)果分析

3.1 仿真場景與參數(shù)設(shè)置

本文仿真實驗環(huán)境為：Window10 64 bit，CPU i5，8 GB內(nèi)存，MATLAB 2019b軟件。在成簇方面，對比本文方法、LEACH、LEACH-I、基于k均值聚類的均勻分簇路由(uniform clustering routing base onk-means，KUCR)算法和FCM(fuzzy C means，F(xiàn)CM)聚類算法，將成簇規(guī)模、首節(jié)點消亡周期、網(wǎng)絡(luò)工作周期、簇頭能耗標(biāo)準(zhǔn)差、數(shù)據(jù)吞吐量作為衡量指標(biāo)，相關(guān)仿真參數(shù)見表1。

表1 仿真參數(shù)設(shè)置

3.2 仿真結(jié)果與分析

圖2為LEACH協(xié)議的成簇結(jié)果。可以看出，成簇數(shù)目為8個，由于采用就近原則入簇方式，最大簇規(guī)模和最小簇規(guī)模相差13%，導(dǎo)致成簇不均。

圖2 LEACH協(xié)議成簇效果

圖3為LEACH-I協(xié)議的成簇結(jié)果。可以看出，成簇數(shù)目為10個，簇規(guī)模差距仍較大。在成簇數(shù)目上，LEACH-I算法比LEACH算法更為均衡。

圖3 LEACH-I協(xié)議成簇效果

圖4為FCM算法在初始聚類中心為12時的成簇效果。可以看出，成簇數(shù)目為11個，簇11為網(wǎng)絡(luò)中的最大簇，其節(jié)點數(shù)目占20%左右，但簇頭位置并非盡量居中，不利各節(jié)點間的相互通信。

圖4 FCM算法成簇效果

圖5為KUCR算法成簇效果。可以看出，成簇數(shù)目為8個，最大簇規(guī)模與最小簇規(guī)模相差10%，但仍存在成簇不均問題。

圖5 KUCR算法成簇效果

圖6為本文方法成簇效果。可以看出，成簇數(shù)目為11個。由于簇密度的引入控制了成簇規(guī)模與均勻性，最大簇規(guī)模與最小簇規(guī)模僅相差3%。由于邊界附近節(jié)點為線狀分布，若簇頭位于近中心位置，則不利于網(wǎng)絡(luò)能量均衡。

圖6 本文方法成簇效果

圖7為本文方法與其它算法對首節(jié)點消亡時的網(wǎng)絡(luò)運行周期數(shù)對比(網(wǎng)絡(luò)節(jié)點數(shù)目100個，測試次數(shù)10次)。可以看出，F(xiàn)CM算法給出的首節(jié)點消亡出現(xiàn)的周期數(shù)目有較大波動。LEACH-I算法對首節(jié)點消亡的周期數(shù)目體現(xiàn)出了改進(jìn)優(yōu)勢。而KUCR算法則與LEACH-I算法的整體差別不大。本文方法增加了剩余能量和距離約束，降低了簇頭選取與低能節(jié)點作為簇頭的概率，緩解了網(wǎng)內(nèi)節(jié)點早亡問題。

圖7 首節(jié)點消亡時周期數(shù)目

圖8為網(wǎng)絡(luò)最大生存周期數(shù)目對比。可以看出，相對于傳統(tǒng)的周期性更換簇頭與泛洪式搜索方式，本文方法由能耗速率判定簇頭是否更新，縮減了簇頭更新次數(shù)與泛洪搜索所需的額外能耗，延長了網(wǎng)絡(luò)的工作周期，優(yōu)化了網(wǎng)絡(luò)所需能量。

圖8 最大生存周期數(shù)目

表2為死亡節(jié)點不同占比出現(xiàn)時的周期數(shù)比較。可以看出，由于簇頭數(shù)目的優(yōu)化、閾值公式的改進(jìn)、簇密度及能耗速率的引入，本文方法較對比算法，網(wǎng)絡(luò)的工作周期分別提高了10.6%、15.9%、13.9%和27%。

表2 消亡節(jié)點不同占比出現(xiàn)時的周期數(shù)目

圖9為簇頭能耗標(biāo)準(zhǔn)差對比。可以看出，本文方法成簇規(guī)模較均勻，簇頭能耗標(biāo)準(zhǔn)差比其它算法小且簇頭能耗均衡。其原因在于在數(shù)據(jù)傳輸階段，簇內(nèi)采用單跳和輪詢機(jī)制的傳輸，降低了所需節(jié)點的能耗；簇間采用多跳與單跳的傳輸，降低了“熱區(qū)”內(nèi)的簇頭能耗，其“非熱區(qū)簇頭”采用了自適應(yīng)路徑傳輸，降低了遠(yuǎn)離BS簇頭節(jié)點的傳輸能耗。

圖9 簇頭能量消耗標(biāo)準(zhǔn)差

表3為在BS處于監(jiān)測區(qū)域不同位置時的簇頭能耗標(biāo)準(zhǔn)差、首節(jié)點消亡出現(xiàn)周期數(shù)目等各方法的對比。可以看出，當(dāng)BS位于非監(jiān)測中心位置時，本文方法存在小幅波動，其原因為當(dāng)BS處于中心區(qū)域時更有利于全網(wǎng)的輻射通信，進(jìn)而節(jié)約了能量。

表3 不同情況下的性能

圖10為網(wǎng)絡(luò)存活周期內(nèi)BS接收數(shù)據(jù)量對比。可以看出，隨著網(wǎng)絡(luò)中最后一個節(jié)點的消亡，本文方法給出的BS接收總數(shù)據(jù)量趨于穩(wěn)定且為最大。同時，在數(shù)據(jù)傳輸穩(wěn)定時的周期數(shù)目也明顯延后，傳輸數(shù)據(jù)量有所提高。

圖10 BS接收數(shù)據(jù)量

表4為當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)目不同時各算法的有效性對比。可以看出，隨著節(jié)點數(shù)目的增加，各算法的用時也逐漸增大。本文方法可達(dá)到均衡網(wǎng)絡(luò)能耗、延長網(wǎng)絡(luò)工作周期的目的。

表4 算法有效性/s

4 結(jié)束語

針對LEACH協(xié)議在簇頭選取、成簇和數(shù)據(jù)傳輸階段引發(fā)的WSN生命周期短、網(wǎng)絡(luò)能耗不均等問題，本文提出了一種的改進(jìn)的能量優(yōu)化方法，均衡了網(wǎng)絡(luò)能耗，延長了網(wǎng)絡(luò)工作周期，提高了數(shù)據(jù)吞吐量。

為提高節(jié)點間的輻射通信能力，需在WSN內(nèi)節(jié)點分布大范圍聚集成片的情況時進(jìn)一步優(yōu)化各項指標(biāo)。因此，接下來的主要工作是在頻域內(nèi)進(jìn)行數(shù)據(jù)分析，由節(jié)點的功率譜與能量譜間的相似性完成分簇操作，自適應(yīng)調(diào)節(jié)節(jié)點的功率實現(xiàn)數(shù)據(jù)傳輸。