基于蟻群算法的LEACH協(xié)議改進(jìn)研究

侯佩

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

1 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是將大量能夠感知濕度、溫度和壓力等物理量的傳感器節(jié)點(diǎn)組成可進(jìn)行數(shù)據(jù)采集、控制和處理等多種功能的多跳自組織測(cè)控網(wǎng)絡(luò)系統(tǒng)[1]。得益于其自動(dòng)管理、節(jié)點(diǎn)之間高度協(xié)調(diào)、動(dòng)態(tài)拓?fù)洹o中心和抗毀性強(qiáng)等特點(diǎn)，已經(jīng)成為無線通信研究的熱點(diǎn)領(lǐng)域。由于節(jié)點(diǎn)放置位置的隨機(jī)性以及應(yīng)用領(lǐng)域的特殊性，WSN節(jié)點(diǎn)電池的維護(hù)或更換面臨著比傳統(tǒng)網(wǎng)絡(luò)更大的挑戰(zhàn)[2]。與此同時(shí)，用于尋找從源節(jié)點(diǎn)到目的節(jié)點(diǎn)最優(yōu)路徑的路由技術(shù)已成為無線傳感器開發(fā)與應(yīng)用的關(guān)鍵技術(shù)[3]。因此在無線傳感器網(wǎng)絡(luò)的研究中，不僅需要建立以電池能效為優(yōu)化目標(biāo)的智能算法以延長(zhǎng)網(wǎng)絡(luò)與應(yīng)用的使用壽命，而且要選擇合適的路由協(xié)議來保障信息傳遞的有效性與可靠性。

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

通過調(diào)研發(fā)現(xiàn)，眾多學(xué)者在研究過程中忽視了簇頭能量及其與簇頭路由路徑長(zhǎng)度間的關(guān)系問題。為此，本文提出基于蟻群算法的LEACH-IMPANT(Low Energy Adaptive Clustering Hierarchy-Improved Ant Colony Algorithm)協(xié)議，在以傳統(tǒng)蟻群算法為前提的LEACH協(xié)議中，通過剩余能量改變簇頭下一轉(zhuǎn)發(fā)路徑，從而優(yōu)化路由尋址方式，提高信息傳輸量，進(jìn)而達(dá)到降低節(jié)點(diǎn)能量損耗與增加網(wǎng)絡(luò)生命周期的目的。

2 LEACH協(xié)議分析

低功耗自適應(yīng)聚類分層協(xié)議（LEACH）通過分簇形成多簇結(jié)構(gòu)，一個(gè)簇由簇頭和大量簇成員組成[9]。簇頭通過與基站直接交互壓縮融合來自簇成員采集的數(shù)據(jù)，在節(jié)約能量的同時(shí)也增加網(wǎng)絡(luò)使用壽命[10]。

LEACH協(xié)議在設(shè)置過程中分為兩個(gè)階段：簇的建立階段和數(shù)據(jù)傳輸階段，兩個(gè)階段共同構(gòu)成一個(gè)循環(huán)[11]。傳感器節(jié)點(diǎn)在簇的建立階段生成一個(gè)隨機(jī)數(shù)R∈(0~1)，當(dāng)R

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

式中，r為當(dāng)前進(jìn)行輪數(shù)，p為節(jié)點(diǎn)當(dāng)選簇頭的期待概率，G為在最近1 p輪循環(huán)中沒有當(dāng)選的簇頭集[14]。

在數(shù)據(jù)傳輸階段，簇頭隨時(shí)與簇成員和基站進(jìn)行通信。根據(jù)成員的數(shù)量，簇頭將生成只允許在分配時(shí)隙內(nèi)傳輸數(shù)據(jù)的TDMA(Time Division Multiple Access)時(shí)間調(diào)度表，隨后簇頭向基站發(fā)送成員數(shù)據(jù)[15,16]。當(dāng)數(shù)據(jù)傳輸?shù)揭欢ǖ拇螖?shù)時(shí)，LEACH協(xié)議將重新開始下一個(gè)周期，進(jìn)行新簇頭的選舉。

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

3 蟻群算法

3.1 蟻群算法基本原理

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

3.2 蟻群算法的數(shù)學(xué)模型

在給定若干個(gè)節(jié)點(diǎn)及坐標(biāo)的前提下，尋求由出發(fā)點(diǎn)訪問所有節(jié)點(diǎn)并返回的最短回路問題可通過蟻群算法的數(shù)學(xué)模型進(jìn)行描述：

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

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

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

式中，ρ為信息素?fù)]發(fā)系數(shù)，隨著時(shí)間進(jìn)行，留下的信息素濃度降低，用參數(shù)(1-ρ)表示信息消逝的程度。為防止信息素?zé)o限累積，ρ∈[0,1)。Δτkij為螞蟻k在本次循環(huán)中留在路徑上的信息素增量，定義如式(4)所示：

Q為螞蟻在尋徑過程中信息素濃度的總量，Lk為螞蟻本次循環(huán)路徑的總長(zhǎng)度[19]。螞蟻每完成一次對(duì)路徑的搜索，對(duì)信息素進(jìn)行全局更新。

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

4 LEACH-IMPANT協(xié)議

4.1 原理分析

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

其中Etot是當(dāng)前輪數(shù)所有節(jié)點(diǎn)的剩余能量總和，Ec是當(dāng)前簇頭能量，在啟發(fā)函數(shù)中添加了剩余能量因子對(duì)路徑的啟示作用。當(dāng)h較小且路由距離較長(zhǎng)時(shí)，節(jié)點(diǎn)剩余能量較少，啟發(fā)函數(shù)的值減小，選擇此路徑的可能性降低，數(shù)據(jù)轉(zhuǎn)發(fā)量減少。

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

4.2 能耗分析

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

發(fā)射機(jī)發(fā)送m位數(shù)據(jù)所消耗的能量如式(6)所示：

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

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

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

當(dāng)簇頭探索完該節(jié)點(diǎn)后，i節(jié)點(diǎn)與j節(jié)點(diǎn)進(jìn)行能量更新，此時(shí)i節(jié)點(diǎn)能量如式(9)所示：

j節(jié)點(diǎn)能量如式(10)所示：

經(jīng)過分析，表征節(jié)點(diǎn)剩余能量越高的h越大，轉(zhuǎn)移概率越大，簇頭從i探索j的傾向性越高，同時(shí)節(jié)點(diǎn)i發(fā)射功耗和節(jié)點(diǎn)j接收功耗降低，減少了損耗，能量利用率提高，生命周期變長(zhǎng)。

4.3 程序流程圖

LEACH-IMPANT算法的程序流程如圖1所示。在開始時(shí)，初始化設(shè)置系統(tǒng)參數(shù)，接著進(jìn)行LEACH算法的兩個(gè)階段：簇的建立和數(shù)據(jù)傳輸。在數(shù)據(jù)傳輸過程中應(yīng)用改進(jìn)的蟻群算法，簇頭通過轉(zhuǎn)移概率的影響、信息素不斷更新、迭代建立路由，最終記錄到達(dá)基站的最優(yōu)路徑，將來自簇內(nèi)成員的數(shù)據(jù)融合轉(zhuǎn)發(fā)至基站，數(shù)據(jù)傳輸完成之后開始新一輪回，直至節(jié)點(diǎn)全部死亡，算法結(jié)束。

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

5 仿真實(shí)驗(yàn)與結(jié)果分析

通過MATLAB軟件設(shè)置基礎(chǔ)參數(shù)，將傳感器節(jié)點(diǎn)分布在100m×100m范圍內(nèi)，控制包/廣播包的長(zhǎng)度為100bit，基站坐標(biāo)（48,180），節(jié)點(diǎn)個(gè)數(shù)為100，LEACH算法中使用的p值為0.1，α為1.2，β為1.6，ρ為0.2，螞蟻個(gè)數(shù)n為20，迭代次數(shù)為50，循環(huán)次數(shù)為1500。假設(shè)所有節(jié)點(diǎn)均保持靜止?fàn)顟B(tài)，初始能量相同，數(shù)據(jù)的接收和轉(zhuǎn)發(fā)消耗相等的能量，設(shè)置對(duì)網(wǎng)絡(luò)的生命周期（即節(jié)點(diǎn)存活輪數(shù)）和基站接收數(shù)據(jù)包進(jìn)行監(jiān)測(cè)實(shí)驗(yàn)。

表1 仿真基礎(chǔ)參數(shù)取值

圖2是LEACH-IMPANT算法與LEACH算法存活節(jié)點(diǎn)數(shù)隨時(shí)間變化的比較情況，結(jié)合表2可知LEACH協(xié)議首節(jié)點(diǎn)死亡時(shí)間在750輪附近，LEACH-IMPANT協(xié)議約為930輪，即采用LEACH-IMPANT協(xié)議的首節(jié)點(diǎn)死亡時(shí)間推遲23%左右。當(dāng)存活節(jié)點(diǎn)個(gè)數(shù)為0時(shí)，LEACH協(xié)議進(jìn)行約1200輪，LEACH-IMPANT協(xié)議進(jìn)行1300輪左右，所有節(jié)點(diǎn)死亡時(shí)間大約延遲100輪，網(wǎng)絡(luò)壽命延長(zhǎng)約7%。

圖2 網(wǎng)絡(luò)生命周期對(duì)比情況

圖3是基站接收數(shù)據(jù)包的個(gè)數(shù)隨時(shí)間變化的比較情況?？梢钥闯霎?dāng)節(jié)點(diǎn)全部死亡時(shí)，無線傳感網(wǎng)絡(luò)結(jié)束生命，此時(shí)基站接收數(shù)據(jù)包個(gè)數(shù)達(dá)到最大值。結(jié)合表3可以看出LEACH-IMPANT算法提高了無線傳感網(wǎng)絡(luò)中基站接收數(shù)據(jù)包的個(gè)數(shù)，數(shù)據(jù)信息傳輸量大約得到17%的提高。

圖3 基站接收數(shù)據(jù)包對(duì)比情況

在蟻群算法的基礎(chǔ)上，在簇頭向基站數(shù)據(jù)通信時(shí)結(jié)合多跳路由的優(yōu)勢(shì)，改進(jìn)能量因子從而在獲得最短路由的條件下使網(wǎng)絡(luò)中的能量消耗更加均衡，提高了無線傳感網(wǎng)絡(luò)中基站的數(shù)據(jù)接收量，降低出現(xiàn)某些能量低的簇頭長(zhǎng)距離轉(zhuǎn)發(fā)數(shù)據(jù)而過早死亡帶來的影響，從而使得整個(gè)網(wǎng)絡(luò)的生存時(shí)間進(jìn)一步延長(zhǎng)。

6 結(jié)論

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

表2 網(wǎng)絡(luò)死亡周期和網(wǎng)絡(luò)壽命五次實(shí)驗(yàn)對(duì)比

表3 兩種算法基站接收數(shù)據(jù)包個(gè)數(shù)實(shí)驗(yàn)對(duì)比

（1）改進(jìn)的蟻群算法在求解路徑規(guī)劃問題方面具有良好的性能。當(dāng)剩余能量因子為5時(shí)，信息量的傳輸獲得較好的增長(zhǎng)比例。

（2）得益于啟發(fā)函數(shù)的優(yōu)化，將節(jié)點(diǎn)剩余能量與基站之間的跳數(shù)等作為考量，減少簇頭的轉(zhuǎn)發(fā)數(shù)據(jù)量，降低了能量消耗，延長(zhǎng)節(jié)點(diǎn)死亡時(shí)間，網(wǎng)絡(luò)壽命增加。

（3）在網(wǎng)絡(luò)規(guī)模較大的情況下，螞蟻探索范圍和方向增加了不確定性，仍然具有較大的改進(jìn)空間。