基于遺傳算法和蟻群算法的LEACH改進協議

徐 巍，鐘宇超，余成成

(湖北工業大學 機械工程學院，湖北 武漢 430068)

0 引言

在無線傳感器網絡中,無線傳感器節點一般由電池供電,但是電池的電量有限且不便于更換,無線傳感器網絡節點的工作壽命受到很大限制[1],因此如何降低無線傳感器網絡的能量損耗是該領域的研究重點[2-3]。

低功耗自適應集簇分層(Low Energy Adaptive Clustering Hierarchy,LEACH)型協議是一種能夠延長無線傳感器網絡生命周期的經典分簇路由協議[4],但是該協議選舉簇頭節點隨機性太強,可能選出較差的簇頭節點,而且傳輸路徑較采取單跳模式會消耗大量能量。目前已有許多學者針對上述問題提出了一些新的改進算法。池濤等[5]采用K-means聚類算法進行分簇,將簇內的節點基于所在的位置進行分層,簇頭節點根據節點所處層次和剩余能量進行選舉,可以延長網絡運行時間,但前層節點死亡過早會造成網絡的節點能耗不均衡。Heinzelman等[6]在LEACH協議的基礎上提出了LEACH-C協議,解決了節點根據隨機數決定是否當選為簇頭節點的問題,并確定了每輪的簇頭節點數量,提高了簇頭選舉的合理性,但并沒有減少傳輸數據階段的能量損耗。杜永文等[7]根據節點剩余能量和節點的位置用模糊算法選舉簇頭節點,并在數據傳輸階段采用多跳傳輸模式。Kulik等[8]提出了一種定向擴散的路由協議,外部節點會根據基站發出的信息選擇合適的方向進行數據傳輸。王波等[9]通過節點的剩余能量、當前節點未成為簇頭節點的輪數來選舉簇頭節點。苗俊先等[10]提出一種非均勻的分簇路由算法,引入雙簇頭機制,并采用單跳和多跳相結合的方式進行數據傳輸。喻小惠等[11]改進了狀態轉移函數,使節點更容易選擇周邊節點密集度較高的節點作為下一跳,但是沒有考慮方向,若朝反方向移動反而會增大傳輸路徑。

綜合考慮上述情況,本文在簇頭選舉和數據傳輸階段都進行改進。在分簇階段用遺傳算法選出剩余能量多、距離基站距離近及周圍節點多的節點作為簇頭節點,并在沒有節點死亡的情況下進行簇內選舉簇頭;在數據傳輸階段,綜合考慮路徑上節點的剩余能量和節點的位置2個因素,用蟻群算法得到最佳傳輸路徑,最終通過仿真實驗可以證明本文改進算法的網絡生命周期得到了顯著延長。

1 LEACH協議分析

1.1 LEACH協議介紹

LEACH協議是周期性的分簇路由協議,每輪循環分為簇頭選舉階段和數據傳輸階段。每一輪開始前,所有節點都會取一個[0,1]的隨機數,如果該節點的隨機值小于這一輪的閾值T(n),則該節點被選為這一輪的簇頭[12];否則該節點為普通節點。閾值T(n)可表示為:

(1)

式中:p為簇頭節點在網絡中所占的比例,r為已經循環的輪數,G為這一輪循環之前還未當選簇頭的節點集合。

簇頭節點產生后,簇頭節點把自己成為簇頭節點的消息向周邊廣播,普通節點根據信號的強弱選擇想要加入的簇頭節點,并給該簇頭節點發送加入請求,當簇頭接收到普通節點的請求后,采用TDMA的方式為其分配一個傳輸數據的時隙。分簇完成后,普通節點把數據發送給該簇的簇頭節點,簇頭對數據進行融合壓縮處理后,采用單跳的方式把數據轉發給基站。

1.2 LEACH協議的不足

1.2.1 傳統LEACH協議的不足

①簇頭節點的選舉具有隨機性,能量較低的節點被選為簇頭節點后,該節點會因消耗過多能量而死亡,進而影響整個網絡的節點分布。

②如果普通節點到簇頭節點的距離比該普通節點到基站之間的距離更遠,普通節點先把數據傳輸給簇頭節點,簇頭節點再轉發給基站會消耗更多的能量。

③簇頭節點與基站采取的是單跳的傳輸方式,如果簇頭節點與基站相距較遠,超出了閾值d0,采用多路徑衰減模型進行傳輸會消耗簇頭節點大量能量,導致其死亡。

1.2.2 現有LEACH改進協議的不足

目前已有許多針對傳統LEACH協議的不足之處進行改進的算法,但這些算法存在一定的缺陷。

①采用簇內分層模型會導致整個網絡的能量消耗不均。前層節點的能量消耗較大,會過早耗盡能量而死亡,進而影響網絡節點的分布。

②只是對簇頭選舉的閾值函數進行改進,簇頭與基站的傳輸方式依然為單跳模式,傳輸距離過大會增大簇頭節點的能耗,最終會導致優化效果不佳。

③優化傳輸路徑一般只考慮了路徑的剩余能量和路徑的長度,如果忽略傳輸的方向,傳輸距離反而會因此增加。

2 系統模型

2.1 網絡模型

本文對無線傳感器網絡節點做出以下假設[13]:

①每個節點都是獨一無二的且帶有編號;

②所有節點的初始能量和功能完全一樣,彼此之間能正常通信且都具有成為簇頭節點的資格;

③整個網絡處在靜態環境下,節點的位置隨機分布且不會發生任何改變;

④基站的計算和處理能力非常強大,且擁有無限的能量供給;

⑤節點可以根據信號的強度計算傳輸距離。

2.2 能耗模型

LEACH協議使用的是一階無線電模型,發送端節點與接收端節點之間的距離會影響傳輸數據階段的能量消耗,設發送端節點與接收端節點之間的距離為d,數據包大小為lbit,發送單位比特電路所消耗的能量為Eelec,自由空間信道模型及多路徑衰減模型下的放大器的功率放大倍數分別為εfs與εamp。能耗模型示意如圖1所示。

圖1 能耗模型Fig.1 Energy consumption model

發送電路消耗的能量為:

(2)

接收電路消耗的能量為:

Erx(l)=lEelec,

(3)

式中:d0為數據傳輸距離的一個閾值,如果2個節點的傳輸距離大于d0時,則采用多路徑衰減模型進行傳輸,否則將采用自由空間信道模型進行傳輸[14-15]。d0可以直接計算得到:

(4)

3 LEACH協議的改進

針對以上LEACH協議的不足之處,本文分別對簇頭的選舉和數據傳輸路徑進行優化改進。

3.1 基于遺傳算法選舉簇頭節點

LEACH協議中,簇頭節點會比普通節點消耗更多能量,能量較少的節點無法完成簇頭節點需要完成的工作,因此需要選出最合適的節點擔任簇頭節點。為了防止剩余能量不足或者距離基站較遠的節點被選舉為簇頭節點,本文采用遺傳算法來優化簇頭節點的選舉。

3.1.1 編碼方式

本文采用二進制的編碼方式對網絡節點進行編碼,即由二進制數0和1組成的字符串來表示,這種編碼方式簡單易于操作[16]。網絡中所有節點都有唯一的節點編號,在遺傳算法中這些編號隨意排列組成多條染色體。每個節點編號對應的位置表示該節點的狀態,如圖2所示,數字0代表普通節點,數字1代表簇頭節點。

圖2 染色體示意Fig.2 Chromosome diagram

3.1.2 適應度函數選取

本文把節點的能量、所在位置以及周邊節點數量3個因素列入簇頭節點選舉的條件,并根據這3個因素設計出適應度函數,計算所有節點的適應度函數值,適應度函數值高的節點被選為簇頭節點。

首先考慮能量因子,讓剩余能量更多的節點選為簇頭節點。設節點i的剩余能量為Ei,網絡中節點剩余能量的最大值和最小值分別為Emax和Emin。本文衡量節點剩余能量的計算如下:

(5)

然后考慮位置因子,讓離基站更近的節點成為簇頭節點。令簇頭節點i與基站之間的距離為di,節點到基站距離的最小值和最大值分別為dmin和dmax,本文衡量節點位置的計算如下:

(6)

最后考慮鄰居節點密度因子,讓周邊節點數目多的節點成為簇頭節點。網絡中共有n個節點,節點i在一定的半徑內含有的鄰居節點的數目為ni。衡量節點鄰居節點密度的計算如下:

(7)

節點的能量因子、位置因子以及鄰居節點密度因子的權重系數分別用fE、fD、fN表示,權重系數的取值為[0,1],且滿足α、β、γ的取值之和為1,適應度函數的計算如下:

Fit_function=αfE+βfD+γfN。

(8)

若節點的剩余能量越多、位置距基站越近且周邊鄰居節點數目眾多,則該節點的適應度函數值就越大,該節點成為簇頭節點的概率越大。

3.1.3 選擇操作

本文采用比例選擇方法和精英選擇方法相結合的選擇方式[17],計算出所有節點的適應度函數值。為了避免遺傳算法出現早熟現象,把適應度函數值排在前20%的節點作為精英個體并遺傳給下一代;其他節點進行交叉和變異操作。

3.1.4 交叉和變異

本文采用兩點交叉方式,隨機選擇2條染色體進行交叉操作,計算生成的子染色體的適應度函數并與父染色體進行比較,適應度函數值大的遺傳至下一代;適應度函數值較小的染色體進行變異處理,變異后再計算其適應度函數。如果多次迭代后滿足:

(9)

則算法停止計算,其中ε0為一個任意小的正數,本文設為10-5。適應度函數最大的個體為最優解,并把其值加入下一輪運算,加快算法的收斂性。

將適應度函數數值高的節點作為最初始的簇頭節點,并完成分簇,下一輪的簇頭節點將在已劃分好的簇中進行簇內選舉。

3.1.5 優化簇頭閾值函數

若直接采用LEACH協議的簇頭選舉閾值函數進行簇內簇頭選舉,通過遺傳算法形成的初始簇群將會受到破壞,因此本文對LEACH協議的簇頭閾值選舉函數進行改進,把遺傳算法的適應度函數加入到閾值函數中,改進后的簇頭閾值函數為:

(10)

式中:popt為最佳簇頭的選舉概率。

(11)

多次進行簇內選舉簇頭會造成各個簇群的剩余能量不平衡,因此本文在基于遺傳算法的簇內簇頭選舉階段提出一種簇群重新劃分機制:若有節點出現死亡現象,則在下一輪簇頭選舉階段之前,重新用遺傳算法進行簇頭選舉并劃分新的簇群。

3.2 基于蟻群算法尋找最佳傳輸路徑

由于LEACH協議在簇頭與基站進行數據傳輸階段統一采用單跳模式,這會導致距離基站較遠的簇頭節點在該階段消耗過多能量并死亡,因此本文采用蟻群算法尋找簇頭節點到基站的最佳傳輸路徑。

3.2.1 螞蟻的轉移概率

(12)

式中:τij(t)為節點i到節點j路徑上的信息素量,其權重為α1,權重越大,螞蟻更可能選擇之前已經探索過的路徑;ηij為啟發函數,其權重為β1,權重越大,蟻群就更容易選擇最短的路徑;Jk(i)為第k只螞蟻下一跳的所有節點集合,節點u為螞蟻的下一跳為節點,τiu(t)、ηiu(t)分別為節點i到節點u路徑上的信息素和啟發函數[18]。

3.2.2 改進信息素因子

為了使整個網絡的能耗相對均衡,需要讓螞蟻進行均衡分流,從而得到最優解,因此本文信息素的更新方式加入了能量因素。

(13)

(14)

3.2.3 改進啟發函數

由于啟發函數ηij(t)的值只取決于2個節點之間的距離,如果螞蟻選擇一個離基站更遠的節點作為下一跳節點,傳輸路徑反而增大了。因此本文加入第三個節點u對啟發函數進行改進,3個節點的位置關系如圖3所示。節點i、j、u之間的距離分別為dij,、diu、duj,改進后的啟發函數為:

(15)

圖3 節點位置關系Fig.3 Node location relationship

若節點i、j之間的中間跳點u距離直線ij更近,ηij(t)的值就更大,螞蟻選擇節點u作為下一跳的概率更大。

3.3 算法流程

本文改進算法流程如圖4所示。首先對網絡參數進行初始化;然后在簇建立階段使用遺傳算法得到最佳簇頭節點并劃分簇群,當算法進行下一輪時,若沒有節點死亡,則采取簇內選取簇頭節點,否則再次進行遺傳算法重新得到新的簇頭群;最后在數據傳輸階段采用蟻群算法尋找最佳傳輸路徑,簇頭節點將其簇群普通節點采集到的數據融合整理后轉發至基站,發送完成之后開始下一輪,直至程序運行到設定的輪數,算法結束。

圖4 改進算法流程Fig.4 Improved algorithm flowchart

4 算法仿真與分析

4.1 仿真環境

為檢驗本文改進算法的可行性,用Matlab軟件對LEACH、LEACH-C和本文改進算法分別進行仿真實驗,仿真數據如表1所示。

表1 仿真數據Tab.1 Simulation data

4.2 仿真結果與分析

圖5為改進算法程序后期節點死亡情況。由于簇頭選舉時考慮了簇頭節點與基站的距離因素,因此靠近基站的節點更容易被選為簇頭節點。簇頭節點消耗的能量要遠大于普通節點,更容易優先死亡,所以程序后期時,靠近基站的節點基本上已經死亡。

圖5 程序后期節點死亡情況Fig.5 Node death situation in the later stage of the program

圖6為LEACH、LEACH-C以及本文算法在相同環境下的節點死亡情況。可以看出,LEACH與LEACH-C在分別在第750輪和第850輪左右時出現節點死亡,且分別在第1 300輪和第1 400輪左右時全部節點死亡。而本文算法在第1 400輪左右時才出現節點死亡且在第1 550輪左右時節點全部死亡,可見本文算法的節點耗能更加平均、節點不容易過早死亡,而且網絡的生命周期也得到了延長。

圖6 網絡節點死亡數目比較Fig.6 Comparison of the number of death network node

由于節點是隨機分布的,整個網絡的生命周期會因此受到影響,為了避免單次仿真的偶然性,進行多次實驗并記錄每次實驗中第一個死亡節點出現的輪數。圖7為3種算法多次仿真實驗得到的第一節點死亡的輪數,可以看出,本文算法出現第一個節點死亡的時間遠晚于另外2種算法,再次驗證了本文算法的能耗更加均衡、節點不容易過早死亡。

圖7 第一死亡節點出現的輪數Fig.7 Number of rounds in which the first death node occurs

圖8為3種算法在相同環境下的能耗情況。可以看出,本文算法的能耗曲線一直位于LEACH、LEACH-C能耗曲線的上方,LEACH協議與LEACH-C協議分別在第1 300輪和第1 400輪左右耗盡能量,但本文算法的能量維持到第1 600輪左右才耗盡。由此可見本文算法的網絡總能量消耗速度更慢、網絡的生命周期更長。

圖8 網絡總能量消耗比較Fig.8 Comparison of total network energy consumption

圖9為3種算法第一個節點死亡、最后一個節點死亡、節點平均生命周期及首尾2節點死亡間隔的輪數對比圖。可以看出,LEACH和LEACH-C的首尾2個節點死亡相隔了550輪左右,而本文算法只經歷了141輪,遠小于LEACH和LEACH-C協議經歷的輪數,說明改進算法的網絡能耗更均衡、所有節點的死亡時間更接近。

圖9 節點死亡情況比較Fig.9 Comparison of death node situations

5 結束語

本文主要研究無線傳感器網絡中的節點能耗問題,希望在隨機分布的網絡區域內能夠選出最合適的簇頭節點并找到最節能的傳輸路徑。由于LEACH路由協議在選舉簇頭節點和數據傳輸2個地方都有一定的缺陷,因此本文針對該缺陷進行一定改進:用遺傳算法解決簇頭節點選擇不當的問題,隨后用蟻群算法解決數據傳輸階段能量消耗過大的問題。通過仿真實驗,可以驗證改進后的LEACH協議能夠更好地使網絡能耗更均勻,網絡的生命周期更長。