一種基于能量和區(qū)域密度的LEACH算法的改進(jìn)

章成學(xué)，王 霄，楊 靖，張靜靜

（貴州大學(xué) 電氣工程學(xué)院，貴陽550025）

0 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，簡稱WSN）是應(yīng)用于環(huán)境監(jiān)測、工業(yè)監(jiān)控和交通監(jiān)控等諸多重要應(yīng)用領(lǐng)域中，最新興、最有前途和最領(lǐng)先的技術(shù)之一［1］。網(wǎng)絡(luò)中的節(jié)點(diǎn)采集環(huán)境數(shù)據(jù)，通過單跳或者多跳的方式傳輸給基站。由于其節(jié)點(diǎn)能量較少，電池更換不便，節(jié)點(diǎn)的能耗對于WSN特別重要。如何更高效地利用有限的節(jié)點(diǎn)能量來延長網(wǎng)絡(luò)的生存周期，是一個重要的設(shè)計目標(biāo)。

分簇算法常常被用來優(yōu)化WSN的能耗，低功率自適應(yīng)集簇分層（LEACH）算法是現(xiàn)有比較經(jīng)典的分簇路由算法之一，但是其會因為隨機(jī)分簇而導(dǎo)致簇首能量消耗較大，從而導(dǎo)致部分節(jié)點(diǎn)過早死亡。有文獻(xiàn)在研究了LEACH-C算法后，提出LEACH-m算法。通過引入剩余能量、節(jié)點(diǎn)覆蓋率和半徑內(nèi)節(jié)點(diǎn)通信代價來選舉簇首節(jié)點(diǎn)［2］；有文獻(xiàn)提出了LEACH-ED算法，引入剩余能量因素和鄰居節(jié)點(diǎn)數(shù)量因素來優(yōu)化選舉閾值，雖然延長了網(wǎng)絡(luò)的生命周期，但是該算法未考慮穩(wěn)定階段的傳輸問題，也未引入節(jié)點(diǎn)與匯聚節(jié)點(diǎn)的距離因素［3］；有文獻(xiàn)考慮了節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離和每輪運(yùn)行結(jié)束后節(jié)點(diǎn)的剩余能量情況，優(yōu)化了簇首節(jié)點(diǎn)的選取方法，提出了MEC-LEACH（Minimum Energy Consumption based LEACH）算法［4］。但是該算法在簇首節(jié)點(diǎn)的選舉并未考慮網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)部署情況，可能出現(xiàn)在節(jié)點(diǎn)密集區(qū)域選擇的簇首個數(shù)較少，稀疏區(qū)域選擇的簇首個數(shù)較多的情況，造成部分節(jié)點(diǎn)能耗加劇，從而降低網(wǎng)絡(luò)生存周期。

本文在以上研究基礎(chǔ)上，對LEACH算法進(jìn)行改進(jìn)，改進(jìn)的算法考慮了網(wǎng)絡(luò)中的平均剩余能量，節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離與網(wǎng)絡(luò)不同區(qū)域節(jié)點(diǎn)密度3種情況，根據(jù)穩(wěn)定傳輸?shù)哪芰肯那蟪鲎罴汛厥讉€數(shù)，引入?yún)^(qū)域密度來調(diào)節(jié)不同疏密程度下的簇首個數(shù)，利用剩余能量和到匯聚節(jié)點(diǎn)距離的加權(quán)值來優(yōu)化選舉閾值，從而改善網(wǎng)絡(luò)性能。

1 無線傳感器網(wǎng)絡(luò)和能量模型

1.1 無線傳感器模型

無線傳感器網(wǎng)絡(luò)由不同功能的節(jié)點(diǎn)構(gòu)成［5］。對于單跳網(wǎng)絡(luò)，由終端節(jié)點(diǎn)和匯聚節(jié)點(diǎn)構(gòu)成。而對于多跳網(wǎng)絡(luò)，由終端、路由器、協(xié)調(diào)器，3種功能節(jié)點(diǎn)構(gòu)成。在多跳網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)部署在一個目標(biāo)區(qū)域中，傳感器節(jié)點(diǎn)測得的信息（如溫度、濕度、光照、壓力、速度等）通過多跳的方式，經(jīng)路由節(jié)點(diǎn)傳送到匯聚節(jié)點(diǎn)［6］。節(jié)點(diǎn)部署在偏遠(yuǎn)地區(qū)，由于不便更換電池，為了延長網(wǎng)絡(luò)的生存周期，如何盡可能保持節(jié)點(diǎn)的能耗均衡就是所有路由算法所追求的。

WSN網(wǎng)絡(luò)模型的假設(shè)：

（1）WSN是由n個傳感器節(jié)點(diǎn)和一個基站組成，節(jié)點(diǎn)隨機(jī)分布在區(qū)域A＝M×M空間中；

（2）每個節(jié)點(diǎn)的結(jié)構(gòu)相同，即有效感知范圍，存儲空間和通信的范圍相同；

（.3）匯聚節(jié)點(diǎn)（s i nk節(jié)點(diǎn)）具有無限的能量和存儲空間；

（4）每個節(jié)點(diǎn)始終都有自己的采集休眠周期，在各自指定的時間發(fā)送信息；

（5）所有節(jié)點(diǎn)和基站在部署后就不再移動；

（6）傳感器節(jié)點(diǎn)在部署后都知曉部署位置。

其節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)鋱D如圖1所示。

圖1 節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)鋱DFig.1 Node network topology

1.2 無線傳感器網(wǎng)絡(luò)的能耗模型

無線傳感器網(wǎng)絡(luò)的能耗主要來自2個方面，一個是節(jié)點(diǎn)接收數(shù)據(jù)的能耗，另一個是節(jié)點(diǎn)發(fā)送數(shù)據(jù)的能耗［7］。發(fā)送端發(fā)送Lbit數(shù)據(jù)的能耗公式（1）如下：

其中，E elec為發(fā)送電路的能耗，其取決于數(shù)字編碼、調(diào)制、濾波和信號擴(kuò)展等因素［8］；εfs和εamp分別為自由空間能耗和多徑衰落能耗中的功率放大系數(shù)是劃分空間模型的閾值。若節(jié)點(diǎn)間的距離d＜d0，則采用自由空間模型，若d＞d0則采用多徑衰落模型。

節(jié)點(diǎn)接收Lbit消息的能耗如公式（2）所示：

簇首節(jié)點(diǎn)處理簇內(nèi)成員發(fā)送過來的信息的能耗如公式（3）所示：

其中，E da為單位數(shù)據(jù)消息聚合處理器耗能大小。

2 LEACH算法的改進(jìn)

2.1 LEACH算法介紹

LEACH算法是采用“輪”的思想進(jìn)行操作的，每一輪分為分簇階段和簇內(nèi)成員數(shù)據(jù)穩(wěn)定傳輸階段［9］。在第一階段通過讓各個節(jié)點(diǎn)在［0，1］中生成一個隨機(jī)數(shù)，若產(chǎn)生的隨機(jī)數(shù)小于計算出的閾值T（n），則該節(jié)點(diǎn)當(dāng)選為簇首節(jié)點(diǎn)，并廣播成為簇首節(jié)點(diǎn)的消息，其它節(jié)點(diǎn)根據(jù)消息的RSSI來判斷加入到哪一個簇，并發(fā)送加入到簇的消息請求到該簇首節(jié)點(diǎn)，簇首節(jié)點(diǎn)建立簇內(nèi)成員表。分簇完成后，系統(tǒng)就會開始節(jié)點(diǎn)數(shù)據(jù)的傳輸，在開始此階段前普通節(jié)點(diǎn)使用時分多址（TDMA）協(xié)議來進(jìn)行數(shù)據(jù)的傳輸，簇首節(jié)點(diǎn)會將簇內(nèi)成員的信息進(jìn)行處理和發(fā)送給sink節(jié)點(diǎn)。每一輪都重復(fù)這個過程。在簇頭的形成階段，網(wǎng)絡(luò)的閾值T（n）的表達(dá)式為式（4）［10］：

其中：p為預(yù)期的簇首節(jié)點(diǎn)占網(wǎng)絡(luò)中節(jié)點(diǎn)的比例，r為網(wǎng)絡(luò)現(xiàn)階段運(yùn)行的輪次；G為候選節(jié)點(diǎn)的集合，其為在1／p輪內(nèi)沒有當(dāng)選簇首的傳感器節(jié)點(diǎn)集合。在后續(xù)的傳輸階段，節(jié)點(diǎn)根據(jù)劃分好的時隙傳輸數(shù)據(jù)給各自的簇首節(jié)點(diǎn)，簇首節(jié)點(diǎn)融合數(shù)據(jù)后發(fā)送給si nk節(jié)點(diǎn)。

2.2 LEACH算法的不足

由于算法采用輪的思想，用產(chǎn)生隨機(jī)數(shù)的方法使得所有的傳感器節(jié)點(diǎn)成為簇首的概率都相等，但是隨機(jī)產(chǎn)生的簇首可能自身的剩余能量較低，在擔(dān)任簇首的周期內(nèi)加劇剩余能量的消耗，加速節(jié)點(diǎn)的死亡。遠(yuǎn)離匯聚節(jié)點(diǎn)的節(jié)點(diǎn)和靠近匯聚節(jié)點(diǎn)的節(jié)點(diǎn)具有相同的概率當(dāng)選簇首，這也會導(dǎo)致遠(yuǎn)離匯聚節(jié)點(diǎn)的節(jié)點(diǎn)過早的死亡。

2.3 改進(jìn)的LEACH算法

本文在LEACH算法的基礎(chǔ)上進(jìn)行改進(jìn)，首先利用在穩(wěn)定傳輸階段的網(wǎng)絡(luò)能耗來求出此時的最佳簇首數(shù)，在穩(wěn)定傳輸?shù)碾A段，網(wǎng)絡(luò)的能耗主要有簇首數(shù)據(jù)收集，普通節(jié)點(diǎn)的采集，簇首節(jié)點(diǎn)將收集的數(shù)據(jù)融合后發(fā)送s i nk節(jié)點(diǎn)的能耗。所以可以得到公式（5）：

其中，n為現(xiàn)輪節(jié)點(diǎn)存活的數(shù)量，d toB S為上一輪簇首到s i nk節(jié)點(diǎn)的平均距離，其改進(jìn)的p的公式（7）為：

其中，E re（i）為節(jié)點(diǎn)的剩余能量；E ave為節(jié)點(diǎn)的平均能耗，將節(jié)點(diǎn)部署的區(qū)域根據(jù)d0劃分為q＝個相同面積的區(qū)域；ρre（i）為節(jié)點(diǎn)所在區(qū)域的密度；ρ為整個區(qū)域的節(jié)點(diǎn)密度。當(dāng)某區(qū)域的密度小于某一閾值時，該節(jié)點(diǎn)不參與選取簇首節(jié)點(diǎn)，加入到離自身最近的簇。

針對LEACH沒有考慮簇首節(jié)點(diǎn)剩余能量和簇首節(jié)點(diǎn)與s i nk節(jié)點(diǎn)的距離，本文構(gòu)建一個閾值調(diào)節(jié)因子f來改進(jìn)原來的閾值表達(dá)式，其具體公式（8）如下：

其中，d a vgnt os i nk為節(jié)點(diǎn)到s i nk節(jié)點(diǎn)的平均距離，d nt o si nk為該節(jié)點(diǎn)到si nk節(jié)點(diǎn)的距離。λ1和λ2的和為1，節(jié)點(diǎn)剩余能量較多時f越大，節(jié)點(diǎn)離s i nk節(jié)點(diǎn)較近時f也越大。f越大，所求的閾值也越大，節(jié)點(diǎn)有更大的概率當(dāng)選簇首節(jié)點(diǎn)。改進(jìn)的閾值表達(dá)式（9）為：

其簇的半徑為公式（10）：

其中，節(jié)點(diǎn)在加入簇的算法流程，如圖2所示。

在下一輪選舉開始前，若有節(jié)點(diǎn)死亡，分2種情況進(jìn)行處理，若死亡的節(jié)點(diǎn)是普通節(jié)點(diǎn)，即簇首節(jié)點(diǎn)在正常傳輸階段沒有收到該節(jié)點(diǎn)的數(shù)據(jù)，簇首節(jié)點(diǎn)進(jìn)行查詢。廣播該節(jié)點(diǎn)死亡，并將該節(jié)點(diǎn)的信息刪除。若死亡的是簇首節(jié)點(diǎn)，則簇內(nèi)的普通節(jié)點(diǎn)在該節(jié)點(diǎn)的TDMA片段沒有收到簇首節(jié)點(diǎn)的確定幀，則向s i nk節(jié)點(diǎn)發(fā)送簇首節(jié)點(diǎn)死亡的消息包，s i nk節(jié)點(diǎn)給簇內(nèi)普通節(jié)點(diǎn)發(fā)送選舉消息，簇內(nèi)成員選出簇首節(jié)點(diǎn)。這種部分選舉避免每次節(jié)點(diǎn)死亡后進(jìn)行全局節(jié)點(diǎn)選舉而增加的能量消耗。

S i nk節(jié)點(diǎn)記錄每一輪簇首節(jié)點(diǎn)在此輪消耗的能量，若此輪消耗的能量小于上一輪消耗的能量，則下一輪不進(jìn)行分簇，保持該簇首繼續(xù)進(jìn)行下一輪傳輸，直至略過的輪數(shù)大于r y u輪時，繼續(xù)上述分簇過程。這樣避免了該網(wǎng)絡(luò)分配了最優(yōu)簇首，因為頻繁的分簇選出劣質(zhì)的簇首節(jié)點(diǎn)，降低網(wǎng)絡(luò)生命周期。

3 仿真結(jié)果分析

3.1 仿真環(huán)境和仿真參數(shù)的設(shè)定

為了驗證本文改進(jìn)算法的有效性，本文采用Matlab仿真平臺對本文算法與MEC-LEACH算法進(jìn)行了仿真對比。假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)死亡個數(shù)超過80%后，導(dǎo)致網(wǎng)絡(luò)失去大部分功能。在實驗環(huán)境中，將100個節(jié)點(diǎn)隨機(jī)的分布在范圍為（0，0）和（100，100）內(nèi)，一個匯聚節(jié)點(diǎn)（x m，y m）位于（50，125），λ1和λ2分別為0.6和0.4。具體的參數(shù)配置，見表1。

表1 實驗參數(shù)Tab.1 Experimental parameter

3.2 結(jié)果分析

本文考慮各個算法的網(wǎng)絡(luò)生命周期，網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量，網(wǎng)絡(luò)的總傳輸數(shù)據(jù)量幾個方面，將改進(jìn)算法與LEACH算法、MEC-LEACH算法進(jìn)行比較。

網(wǎng)絡(luò)節(jié)點(diǎn)死亡個數(shù)隨時間（輪數(shù)）增大的變化狀態(tài)如圖3所示。LEACH算法首次出現(xiàn)死亡節(jié)點(diǎn)的周期為第632輪，MEC-LEACH算法首次出現(xiàn)死亡節(jié)點(diǎn)的周期為第911輪，而本文算法首次出現(xiàn)死亡節(jié)點(diǎn)的周期為第942輪。假定網(wǎng)絡(luò)中節(jié)點(diǎn)死亡數(shù)量達(dá)到80%后，整個網(wǎng)絡(luò)死亡。本文算法的網(wǎng)絡(luò)生存周期大約為986輪，LEACH算法和MEC-LEACH算法的網(wǎng)絡(luò)生存周期分別為921輪和936輪。這主要是因為LEACH算法隨機(jī)產(chǎn)生不均勻簇，導(dǎo)致部分節(jié)點(diǎn)因為能量消耗較大而過早的死亡。MECLEACH算法由于考慮了剩余能量和與匯聚節(jié)點(diǎn)的距離，相比LEACH算法，網(wǎng)絡(luò)的能量消耗比較均衡，但是沒有考慮不同區(qū)域內(nèi)的節(jié)點(diǎn)密度對簇首個數(shù)的影響。本文算法考慮到上述的3種因素，使網(wǎng)絡(luò)生存周期相比MEC-LEACH算法有一定的提高。由于LEACH算法造成網(wǎng)絡(luò)中節(jié)點(diǎn)消耗能量不均衡，使得部分節(jié)點(diǎn)率先死亡，其它節(jié)點(diǎn)可能保留較多的能量，因此在節(jié)點(diǎn)首次死亡后，后續(xù)節(jié)點(diǎn)是陸續(xù)逐個死亡，呈現(xiàn)較緩的上升曲線。MEC-LEACH算法和本文的算法由于在節(jié)點(diǎn)首次死亡前，網(wǎng)絡(luò)能量消耗較為均衡，所以在節(jié)點(diǎn)首次死亡后，由于剩余的節(jié)點(diǎn)自身能量并不是很高，后續(xù)就出現(xiàn)了大量的節(jié)點(diǎn)死亡，呈現(xiàn)較陡的上升曲線。

圖3 3種算法網(wǎng)絡(luò)節(jié)點(diǎn)生存周期比較Fig.3 Comparison of network node life cycles of the three algorithms

網(wǎng)絡(luò)系統(tǒng)總的能量消耗是衡量網(wǎng)絡(luò)系統(tǒng)好壞的一個重要指標(biāo)。3種不同算法的網(wǎng)絡(luò)剩余能量的比較如圖4所示，可以看出本算法在運(yùn)行過程中較前2種算法有較高的剩余能量，這是因為本文算法動態(tài)調(diào)整簇首節(jié)點(diǎn)，使網(wǎng)絡(luò)簇首數(shù)始終處于網(wǎng)絡(luò)能量消耗較優(yōu)的個數(shù)。并且考慮節(jié)點(diǎn)剩余能量，與匯聚節(jié)點(diǎn)距離以及節(jié)點(diǎn)密度等，動態(tài)調(diào)整選舉閾值，使合適的節(jié)點(diǎn)當(dāng)選簇首，減小網(wǎng)絡(luò)能量消耗延長網(wǎng)絡(luò)生存周期。

圖4 網(wǎng)絡(luò)剩余能量Fig.4 Residual energy of the network

網(wǎng)絡(luò)中節(jié)點(diǎn)最小剩余能量，如圖5所示。LEACH算法運(yùn)行的網(wǎng)絡(luò)中，每周期節(jié)點(diǎn)的剩余能量最小的值比另外2種算法低，這是因為在分簇時未考慮節(jié)點(diǎn)剩余能量，所以剩余能量較低的節(jié)點(diǎn)有幾率繼續(xù)當(dāng)選簇首節(jié)點(diǎn)，加快其能量消耗。因為簇首節(jié)點(diǎn)隨機(jī)選舉，每輪周期節(jié)點(diǎn)消耗的能量不均衡。所以圖5中LEACH算法的曲線波動較為明顯。MECLEACH算法和本文算法都考慮了節(jié)點(diǎn)剩余能量，網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗比較均勻，因此網(wǎng)絡(luò)中節(jié)點(diǎn)最小剩余能量相差不大。在節(jié)點(diǎn)首次死亡后，由于剩余的節(jié)點(diǎn)自身能量并不是很高，后續(xù)出現(xiàn)大量的節(jié)點(diǎn)死亡。

圖5 網(wǎng)絡(luò)中節(jié)點(diǎn)最小剩余能量Fig.5 Minimum residual energy of nodes in the network

LEACH算法中匯聚節(jié)點(diǎn)接收了大約87 155個數(shù)據(jù)包，MEC-LEACH算法中的匯聚節(jié)點(diǎn)接收了大約89 860個數(shù)據(jù)包，本文算法中的匯聚節(jié)點(diǎn)接收了大約96 870個數(shù)據(jù)包。

4 結(jié)束語

本文在LEACH算法的基礎(chǔ)上，針對隨機(jī)分簇和簇首能耗不均的問題，通過最小網(wǎng)絡(luò)能耗來得到最優(yōu)的簇首個數(shù)。在簇首節(jié)點(diǎn)選取上，考慮節(jié)點(diǎn)的剩余能量，與匯聚節(jié)點(diǎn)間的距離和節(jié)點(diǎn)所在區(qū)域密度，使剩余能量較高，距離匯聚節(jié)點(diǎn)較近，所在區(qū)域節(jié)點(diǎn)密度較大的節(jié)點(diǎn)更容易成為簇首節(jié)點(diǎn)。仿真實驗表明，相比與LEACH算法和其它改進(jìn)LEACH算法，本文的改進(jìn)算法可以更有效的延長網(wǎng)絡(luò)生存周期，降低和均衡網(wǎng)絡(luò)能耗，提高網(wǎng)絡(luò)匯聚節(jié)點(diǎn)接收的數(shù)據(jù)量，提高網(wǎng)絡(luò)性能。