基于蟻群算法的LEACH協議改進研究

侯佩

（山西師范大學 物理與信息工程學院，山西 太原 030092）

1 引言

無線傳感器網絡（Wireless Sensor Network，WSN）是將大量能夠感知濕度、溫度和壓力等物理量的傳感器節點組成可進行數據采集、控制和處理等多種功能的多跳自組織測控網絡系統[1]。得益于其自動管理、節點之間高度協調、動態拓撲、無中心和抗毀性強等特點，已經成為無線通信研究的熱點領域。由于節點放置位置的隨機性以及應用領域的特殊性，WSN節點電池的維護或更換面臨著比傳統網絡更大的挑戰[2]。與此同時，用于尋找從源節點到目的節點最優路徑的路由技術已成為無線傳感器開發與應用的關鍵技術[3]。因此在無線傳感器網絡的研究中，不僅需要建立以電池能效為優化目標的智能算法以延長網絡與應用的使用壽命，而且要選擇合適的路由協議來保障信息傳遞的有效性與可靠性。

在WSN能耗均衡及路由選擇的研究領域中，國內外眾多學者指向性地提出了大量新的想法和措施。唐泉等人[4]分析了LEACH協議的優缺點，對節點分布情況、數量與能量進行仿真實驗，推薦對兩跳路由以及閾值選擇方法進行改進。胡彧等人[5]結合節點的剩余能量改變閾值公式來保證產生簇頭的均衡性，但在簇頭之間的路由中只是簡單引入蟻群算法中的多跳形式進行數據傳輸，缺少對簇頭能量的考量。劉熙[6]提出了蟻群算法的網絡路由優化方法，根據正反饋性，增強信息表，搜索最優路徑。HEINZELMAN W R等人[7]對通信協議進行詳細描述，重點介紹LEACH的工作原理，對能量進行分析，但沒有優化簇頭路由算法，使路由過程整體能耗高。Kulik J等人[8]提出了定向擴散的平面路由方法，當基站發出消息，進行查詢，外部節點會有方向地向內部節點傳送數據，當節點大范圍分布時，該路由方法會使節點能量迅速降低。

通過調研發現，眾多學者在研究過程中忽視了簇頭能量及其與簇頭路由路徑長度間的關系問題。為此，本文提出基于蟻群算法的LEACH-IMPANT(Low Energy Adaptive Clustering Hierarchy-Improved Ant Colony Algorithm)協議，在以傳統蟻群算法為前提的LEACH協議中，通過剩余能量改變簇頭下一轉發路徑，從而優化路由尋址方式，提高信息傳輸量，進而達到降低節點能量損耗與增加網絡生命周期的目的。

2 LEACH協議分析

低功耗自適應聚類分層協議（LEACH）通過分簇形成多簇結構，一個簇由簇頭和大量簇成員組成[9]。簇頭通過與基站直接交互壓縮融合來自簇成員采集的數據，在節約能量的同時也增加網絡使用壽命[10]。

LEACH協議在設置過程中分為兩個階段：簇的建立階段和數據傳輸階段，兩個階段共同構成一個循環[11]。傳感器節點在簇的建立階段生成一個隨機數R∈(0~1)，當R

閾值T(n)定義如式(1)所示：

式中，r為當前進行輪數，p為節點當選簇頭的期待概率，G為在最近1 p輪循環中沒有當選的簇頭集[14]。

在數據傳輸階段，簇頭隨時與簇成員和基站進行通信。根據成員的數量，簇頭將生成只允許在分配時隙內傳輸數據的TDMA(Time Division Multiple Access)時間調度表，隨后簇頭向基站發送成員數據[15,16]。當數據傳輸到一定的次數時，LEACH協議將重新開始下一個周期，進行新簇頭的選舉。

然而，LEACH協議中對簇頭的依賴性強、多跳路由功能較弱，當通信傳輸距離較大時，簇頭采用單跳形式與基站通信，能量損耗將以原能耗的2次方加倍消耗，單個簇頭能量會大幅衰減，網絡生命周期急劇下降，影響網絡的性能。因此亟待引進一種探索簇頭剩余能量的算法，避免簇頭能量提前衰竭。

3 蟻群算法

3.1 蟻群算法基本原理

蟻群算法(Ant colony algorithm)是一種源于螞蟻覓食路徑尋優方式的仿生算法。在相同時間的情況下，螞蟻探索路徑較短時會留下更多的分泌物——信息素[17]，周圍的蟻群會感知信息素濃度并會被促使朝著該路徑探索。隨著該路徑上信息素的逐漸增加，螞蟻的數量也逐漸增加，最終整個蟻群在信息素集中的正反饋機制作用下[18]，達到收斂狀態，尋找到一條最優的路徑。

3.2 蟻群算法的數學模型

在給定若干個節點及坐標的前提下，尋求由出發點訪問所有節點并返回的最短回路問題可通過蟻群算法的數學模型進行描述：

首先將n只螞蟻置于出發點v1，設定每次僅讓一只螞蟻進行隨機探索，其探索行為通過轉移概率C來表示，對于第k只螞蟻，從i節點選擇到j節點路徑的概率如式(2)所示：

式中τij(t)為路徑ij上的信息素量，ηij表示啟發信息，一般取i至j的距離的倒數，α為信息素權重，強調了信息素濃度的重要性，其值越大，說明蟻群在該路徑積累的信息素濃度高，則該螞蟻傾向于選擇其他螞蟻經過的路徑，增強螞蟻間的協作性；β為距離啟發信息權重，指出啟發信息的重要性，其值越大，則該狀態轉移概率越接近于貪心規則[5]。allowedk為第k只螞蟻可以探索的下一跳節點集合，s為螞蟻探索的下一跳節點，τis(t)為本次探索節點i到s節點的信息素，ηis(t)為本次探索i節點到s節點的啟發函數。

第t輪結束，開始第t+1輪，其信息素更新如式(3)所示：

式中，ρ為信息素揮發系數，隨著時間進行，留下的信息素濃度降低，用參數(1-ρ)表示信息消逝的程度。為防止信息素無限累積，ρ∈[0,1)。Δτkij為螞蟻k在本次循環中留在路徑上的信息素增量，定義如式(4)所示：

Q為螞蟻在尋徑過程中信息素濃度的總量，Lk為螞蟻本次循環路徑的總長度[19]。螞蟻每完成一次對路徑的搜索，對信息素進行全局更新。

當n只螞蟻完成了對節點的探索，并在探索過程中留下了信息素，表示完成一次迭代。蟻群算法不斷收斂迭代，最終尋找到最優路徑，故可將其應用到WSN中，用于尋求最短路由。但該算法僅考慮了路徑的長短，忽略了簇頭傳輸數據時剩余能量問題帶來的弊端，若下一跳路徑較長，則構建時間延長，簇頭的剩余能量不足以到達下一節點，使信息傳輸率降低，網絡生命周期縮短。為此，針對蟻群算法簇頭剩余能量在路由過程中存在的問題，本文采用蟻群算法改進能量因子來對LEACH協議進行優化。

4 LEACH-IMPANT協議

4.1 原理分析

剩余能量因子h表征為簇頭剩余能量與網絡剩余總能量的比值。將蟻群算法中的啟發函數ηij=1 dij更改為由剩余能量因子和路徑距離共同決定，即新的啟發函數如下式(5)所示：

其中Etot是當前輪數所有節點的剩余能量總和，Ec是當前簇頭能量，在啟發函數中添加了剩余能量因子對路徑的啟示作用。當h較小且路由距離較長時，節點剩余能量較少，啟發函數的值減小，選擇此路徑的可能性降低，數據轉發量減少。

在數據傳輸階段，相較于LEACH協議中簇內節點不與基站直接通信，只負責采集與轉發數據，每個簇頭均需要耗費大量能量且要歷經不同的距離將信息傳送到基站，蟻群算法克服了單跳的缺陷，簇頭相互協作找到最優路徑并集中轉發數據，同時在改進算法中引入剩余能量因子，簇頭在探索下一轉發路徑時會根據剩余能量確定轉移概率的大小，合理規劃距離，防止由于能量不足而過度傳輸數據和盲目地遍歷整個網絡區域。綜合對節點剩余能量的分析，通過重新定義啟發函數加速算法收斂，使算法更具針對性、可擴展性，整體提高數據聚合能力、工作負載分布能力與能量效率[20]。

4.2 能耗分析

LEACH算法的耗能模型包括如下：

發射機發送m位數據所消耗的能量如式(6)所示：

接收機接收m位數據需要消耗能量如式(7)所示：

式中，發射和接收1bit數據電路所消耗的能量通過Eele表示，ξfs與ξmp分別表示自由空間模型和多路徑衰減模型中單位功率放大器的能量消耗，d0表示距離門限，。具體模擬參數設置見表1。

首先初始化參數，賦予x個節點相同的能量E1、E2…Ex，隨后在數據的傳輸階段，由于改進啟發函數，簇頭探索下一轉發節點位置時轉移概率函數中添加了能量對概率的影響。則在t時刻，處于節點i的簇頭k選擇節點j的概率如式(8)所示：

當簇頭探索完該節點后，i節點與j節點進行能量更新，此時i節點能量如式(9)所示：

j節點能量如式(10)所示：

經過分析，表征節點剩余能量越高的h越大，轉移概率越大，簇頭從i探索j的傾向性越高，同時節點i發射功耗和節點j接收功耗降低，減少了損耗，能量利用率提高，生命周期變長。

4.3 程序流程圖

LEACH-IMPANT算法的程序流程如圖1所示。在開始時，初始化設置系統參數，接著進行LEACH算法的兩個階段：簇的建立和數據傳輸。在數據傳輸過程中應用改進的蟻群算法，簇頭通過轉移概率的影響、信息素不斷更新、迭代建立路由，最終記錄到達基站的最優路徑，將來自簇內成員的數據融合轉發至基站，數據傳輸完成之后開始新一輪回，直至節點全部死亡，算法結束。

圖1 LEACH-IMPANT算法程序流程圖

5 仿真實驗與結果分析

通過MATLAB軟件設置基礎參數，將傳感器節點分布在100m×100m范圍內，控制包/廣播包的長度為100bit，基站坐標（48,180），節點個數為100，LEACH算法中使用的p值為0.1，α為1.2，β為1.6，ρ為0.2，螞蟻個數n為20，迭代次數為50，循環次數為1500。假設所有節點均保持靜止狀態，初始能量相同，數據的接收和轉發消耗相等的能量，設置對網絡的生命周期（即節點存活輪數）和基站接收數據包進行監測實驗。

表1 仿真基礎參數取值

圖2是LEACH-IMPANT算法與LEACH算法存活節點數隨時間變化的比較情況，結合表2可知LEACH協議首節點死亡時間在750輪附近，LEACH-IMPANT協議約為930輪，即采用LEACH-IMPANT協議的首節點死亡時間推遲23%左右。當存活節點個數為0時，LEACH協議進行約1200輪，LEACH-IMPANT協議進行1300輪左右，所有節點死亡時間大約延遲100輪，網絡壽命延長約7%。

圖2 網絡生命周期對比情況

圖3是基站接收數據包的個數隨時間變化的比較情況。可以看出當節點全部死亡時，無線傳感網絡結束生命，此時基站接收數據包個數達到最大值。結合表3可以看出LEACH-IMPANT算法提高了無線傳感網絡中基站接收數據包的個數，數據信息傳輸量大約得到17%的提高。

圖3 基站接收數據包對比情況

在蟻群算法的基礎上，在簇頭向基站數據通信時結合多跳路由的優勢，改進能量因子從而在獲得最短路由的條件下使網絡中的能量消耗更加均衡，提高了無線傳感網絡中基站的數據接收量，降低出現某些能量低的簇頭長距離轉發數據而過早死亡帶來的影響，從而使得整個網絡的生存時間進一步延長。

6 結論

本文通過對基于蟻群算法的LEACH協議改進研究，結合蟻群算法具有較強的全局探索能力和較好的收斂能力，解決了LEACH協議中簇頭與基站單跳通信的問題。在將簇頭抽象為螞蟻探尋的節點的前提下，保證節點能量不提前衰減。針對探尋路徑規劃問題，進行了多次的仿真實驗，得出以下結論：

表2 網絡死亡周期和網絡壽命五次實驗對比

表3 兩種算法基站接收數據包個數實驗對比

（1）改進的蟻群算法在求解路徑規劃問題方面具有良好的性能。當剩余能量因子為5時，信息量的傳輸獲得較好的增長比例。

（2）得益于啟發函數的優化，將節點剩余能量與基站之間的跳數等作為考量，減少簇頭的轉發數據量，降低了能量消耗，延長節點死亡時間，網絡壽命增加。

（3）在網絡規模較大的情況下，螞蟻探索范圍和方向增加了不確定性，仍然具有較大的改進空間。