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

章成學，王 霄，楊 靖，張靜靜

（貴州大學 電氣工程學院，貴陽550025）

0 引 言

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

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

本文在以上研究基礎上，對LEACH算法進行改進，改進的算法考慮了網絡中的平均剩余能量，節點到匯聚節點的距離與網絡不同區域節點密度3種情況，根據穩定傳輸的能量消耗求出最佳簇首個數，引入區域密度來調節不同疏密程度下的簇首個數，利用剩余能量和到匯聚節點距離的加權值來優化選舉閾值，從而改善網絡性能。

1 無線傳感器網絡和能量模型

1.1 無線傳感器模型

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

WSN網絡模型的假設：

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

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

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

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

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

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

其節點網絡拓撲圖如圖1所示。

圖1 節點網絡拓撲圖Fig.1 Node network topology

1.2 無線傳感器網絡的能耗模型

無線傳感器網絡的能耗主要來自2個方面，一個是節點接收數據的能耗，另一個是節點發送數據的能耗［7］。發送端發送Lbit數據的能耗公式（1）如下：

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

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

簇首節點處理簇內成員發送過來的信息的能耗如公式（3）所示：

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

2 LEACH算法的改進

2.1 LEACH算法介紹

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

其中：p為預期的簇首節點占網絡中節點的比例，r為網絡現階段運行的輪次；G為候選節點的集合，其為在1／p輪內沒有當選簇首的傳感器節點集合。在后續的傳輸階段，節點根據劃分好的時隙傳輸數據給各自的簇首節點，簇首節點融合數據后發送給si nk節點。

2.2 LEACH算法的不足

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

2.3 改進的LEACH算法

本文在LEACH算法的基礎上進行改進，首先利用在穩定傳輸階段的網絡能耗來求出此時的最佳簇首數，在穩定傳輸的階段，網絡的能耗主要有簇首數據收集，普通節點的采集，簇首節點將收集的數據融合后發送s i nk節點的能耗。所以可以得到公式（5）：

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

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

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

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

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

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

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

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

3 仿真結果分析

3.1 仿真環境和仿真參數的設定

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

表1 實驗參數Tab.1 Experimental parameter

3.2 結果分析

本文考慮各個算法的網絡生命周期，網絡中節點剩余能量，網絡的總傳輸數據量幾個方面，將改進算法與LEACH算法、MEC-LEACH算法進行比較。

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

圖3 3種算法網絡節點生存周期比較Fig.3 Comparison of network node life cycles of the three algorithms

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

圖4 網絡剩余能量Fig.4 Residual energy of the network

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

圖5 網絡中節點最小剩余能量Fig.5 Minimum residual energy of nodes in the network

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

4 結束語

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