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

章成學(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é)點采集環(huán)境數(shù)據(jù)，通過單跳或者多跳的方式傳輸給基站。由于其節(jié)點能量較少，電池更換不便，節(jié)點的能耗對于WSN特別重要。如何更高效地利用有限的節(jié)點能量來延長網(wǎng)絡(luò)的生存周期，是一個重要的設(shè)計目標。

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

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

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

1.1 無線傳感器模型

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

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

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

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

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

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

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

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

其節(jié)點網(wǎng)絡(luò)拓撲圖如圖1所示。

圖1 節(jié)點網(wǎng)絡(luò)拓撲圖Fig.1 Node network topology

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

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

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

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

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

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

2 LEACH算法的改進

2.1 LEACH算法介紹

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

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

2.2 LEACH算法的不足

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

2.3 改進的LEACH算法

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

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

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

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

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

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

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

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

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

3 仿真結(jié)果分析

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

為了驗證本文改進算法的有效性，本文采用Matlab仿真平臺對本文算法與MEC-LEACH算法進行了仿真對比。假設(shè)網(wǎng)絡(luò)節(jié)點死亡個數(shù)超過80%后，導(dǎo)致網(wǎng)絡(luò)失去大部分功能。在實驗環(huán)境中，將100個節(jié)點隨機的分布在范圍為（0，0）和（100，100）內(nèi)，一個匯聚節(jié)點（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é)點剩余能量，網(wǎng)絡(luò)的總傳輸數(shù)據(jù)量幾個方面，將改進算法與LEACH算法、MEC-LEACH算法進行比較。

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

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

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

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

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

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

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

4 結(jié)束語

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