WSN中基于改進(jìn)蟻群的能量優(yōu)化路由算法

蔣占軍,周 濤,楊永紅

(蘭州交通大學(xué) 電子與信息工程學(xué)院,蘭州 730070)

0 概述

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)由大量的微型節(jié)點組成,其依靠微電池供電,組網(wǎng)靈活、成本較低,廣泛應(yīng)用于野外監(jiān)測、抗震救災(zāi)等場景中。然而,大部分節(jié)點分布在荒野地區(qū),一般情況下無法及時更換[1],一旦節(jié)點損壞,將對網(wǎng)絡(luò)產(chǎn)生重大影響,特別是當(dāng)關(guān)鍵節(jié)點因能量耗盡而失效時,會出現(xiàn)“熱點”問題,網(wǎng)絡(luò)的連通性被破壞而進(jìn)入癱瘓狀態(tài)。因此,降低節(jié)點能耗、優(yōu)化網(wǎng)絡(luò)路由,從而延長網(wǎng)絡(luò)壽命是亟待解決的一個問題。

針對上述問題,國內(nèi)外專家學(xué)者對原有的路由協(xié)議提出許多優(yōu)化方案。然而,與傳統(tǒng)的路由協(xié)議相比,WSN通過節(jié)點間的主動探索來完成通信任務(wù),但節(jié)點的計算和存儲能力有限,只能存儲相鄰節(jié)點的路由信息。生物智能算法因其能有效地完成WSN中的分簇與路徑規(guī)劃任務(wù)而受到廣泛關(guān)注。其中最具有代表性的是基于蟻群優(yōu)化(Ant Colony Optimization,ACO)的WSN路由算法,其利用蟻群的智能功能高效地在復(fù)雜的網(wǎng)絡(luò)拓?fù)渲姓业阶顑?yōu)路徑。此外,ACO具有正反饋、分布式并行計算機(jī)制和魯棒性強(qiáng)等特點,在WSN中易于實現(xiàn)。因此,研究人員通常使用ACO來解決WSN路由中的能量利用問題。

ARA(Ant-based Routing Algorithm)[2]是最早將ACO應(yīng)用到移動自組織網(wǎng)絡(luò)中的被動式多路徑路由算法。該算法通過減少數(shù)據(jù)包類型,在節(jié)點信息素低于某個閾值時進(jìn)入休眠模式以節(jié)約能量,但節(jié)點間存在不必要的網(wǎng)絡(luò)開銷和時延。IARA(Improved Ant-based Routing Algorithm)[3-4]對ARA中的冗余鄰居節(jié)點進(jìn)行篩選,采用角度因子和距離因子限制搜索方向,避免無關(guān)路徑的產(chǎn)生,但該算法的節(jié)點計算復(fù)雜度高、收斂速度慢。LEACH-VA(Low-Energy Adaptive Clustering Hierarchy Voronoi Algorithm)[5]是一種基于分層結(jié)構(gòu)的路由協(xié)議算法,其純粹利用幾何關(guān)系改進(jìn)螞蟻包的數(shù)據(jù)結(jié)構(gòu)和信息素更新規(guī)則,在簇內(nèi)運(yùn)用多跳的路由方式進(jìn)行傳輸,引入尋徑螞蟻收集跳數(shù)信息以及所經(jīng)路徑對其他路徑的負(fù)反饋條件,綜合多方面因素規(guī)劃路由,得到全局最優(yōu)解。但是,LEACH-VA算法存在頻繁的動態(tài)分簇,導(dǎo)致能量浪費(fèi)。ARAMA(Ant Routing Algorithm for Mobile Ad-hoc)[6]利用梯度值對節(jié)點中的路由表進(jìn)行更新,其缺點是在大型網(wǎng)絡(luò)中,隨著每個螞蟻的記憶列表變長,節(jié)點間傳輸螞蟻包的能耗會增加。EEABR(Energy-Efficient Ant-Base Routing)[7]將節(jié)點平均能量水平與螞蟻經(jīng)過的跳數(shù)引入ACO的信息素增量公式中,并在節(jié)點上將螞蟻攜帶的信息進(jìn)行融合,可減少節(jié)點傳輸?shù)臄?shù)據(jù)量。但是,EEABR在螞蟻靠近Sink節(jié)點等較為密集的區(qū)域時存在頻繁的數(shù)據(jù)轉(zhuǎn)發(fā),若單純通過加減運(yùn)算進(jìn)行更新,其結(jié)果不夠準(zhǔn)確且消耗的能量較多。此外,由于螞蟻包中只存放2條節(jié)點ID信息,易形成螞蟻環(huán)路,不利于全網(wǎng)能量均衡。IEEABR(Improved Energy-Efficient Ant-Base Routing)[8]在設(shè)計報文時,分別定義了2類螞蟻的數(shù)據(jù)結(jié)構(gòu),將鄰居節(jié)點的剩余能量引入螞蟻路徑的鏈路啟發(fā)信息公式中,減少在尋路過程中選擇能量較小的下一跳節(jié)點概率。在信息素更新公式方面,IEEABR的尋徑螞蟻與回退螞蟻使用不同的更新公式,引導(dǎo)后來的螞蟻選擇能量較大的鄰居作為下一跳。IEEABR的缺點在于ACO中的信息素更新是一個正反饋過程,螞蟻完成最短路徑的搜索后會聚集在該路徑上,造成最佳路徑節(jié)點能量耗盡而過早死亡,而非最佳路徑的信息素濃度釋放量不斷減小。同時,隨著時間推移,該算法會導(dǎo)致路徑荒廢但節(jié)點能量充足。

本文在IEEABR算法的基礎(chǔ)上,提出一種增強(qiáng)型的能量優(yōu)化路由算法E-EEABR。在尋找下一跳節(jié)點時綜合距離帶、搜索角度和距離因子3個因素選取下一跳節(jié)點,利用激勵策略使最優(yōu)路徑周圍的剩余能量充足,并通過跳數(shù)較少的節(jié)點來均衡負(fù)載過重的“熱”節(jié)點的傳輸任務(wù)。此外,采用一種含能量因子的偽隨機(jī)比例規(guī)則策略優(yōu)化概率轉(zhuǎn)移函數(shù),降低“熱”節(jié)點失效的概率,以增強(qiáng)算法的尋優(yōu)能力。

1 蟻群算法原理

ACO算法是指WSN中的源節(jié)點通過發(fā)送人工螞蟻來模擬自然界中的螞蟻。人工螞蟻在尋找食物的過程中,通過分泌高濃度的信息素來吸引更多的螞蟻加入到尋徑路徑中,然后利用算法的正向反饋機(jī)制找出一條到達(dá)食物的最優(yōu)路徑。在ACO算法中,螞蟻分為尋徑螞蟻和回退螞蟻2類。螞蟻尋徑原理如圖1所示。

圖1 螞蟻尋徑示意圖Fig.1 Schematic diagram of ant path finding

假設(shè)在WSN尋徑的初始階段,節(jié)點個數(shù)為m,螞蟻個數(shù)為n,尋徑螞蟻k從源節(jié)點出發(fā),通過式(1)所示的狀態(tài)概率轉(zhuǎn)移公式選擇下一跳節(jié)點。式(2)表示螞蟻k對下一跳節(jié)點的期望值,一般來講,距離dij(見式(3))越小,螞蟻對下一跳的期望值越大。尋徑螞蟻通過彼此間的自主探索,在經(jīng)過多個節(jié)點后抵達(dá)Sink節(jié)點,然后在Sink節(jié)點消亡,生成回退螞蟻?；赝宋浵佈刂畔⑺貪舛茸畲蟮穆窂交氐皆垂?jié)點,完成一次尋徑過程。在該過程中,各路徑在初始化時被賦予了相同的信息素濃度τij(t)=C且其會以一定的速度揮發(fā)。在回退螞蟻返回更新的信息素時,各路徑由于自身距離、剩余能量等因素存在差異,導(dǎo)致計算的信息素增量也不相同,得到較優(yōu)解的路徑擁有的信息素濃度更高,吸引更多的螞蟻,而剩余路徑的信息素則不斷揮發(fā)。ACO的這種正反饋機(jī)制使得螞蟻可以不斷探索最優(yōu)路徑。

(1)

(2)

(3)

目前,蟻群算法基本模型有3種,其信息素更新策略各不相同,主要差別在于Δτij(t)求法不同[9]。本文采用蟻量(Ant-Quantity,AQ)模型,按照式(4)～式(6)進(jìn)行信息素更新,使路徑上的每個節(jié)點都能生成一個相應(yīng)的路由表,其中包含該節(jié)點到下一跳節(jié)點的相應(yīng)信息。

τij(t+n)=(1-ρ)τij(t)+Δτij(t)

(4)

(5)

(6)

2 ACO的作用

在ACO算法中,螞蟻根據(jù)信息素濃度、能量等啟發(fā)式信息來規(guī)劃最優(yōu)路徑[10]。將ACO應(yīng)用到WSN中是為了利用ACO的自組織性、正反饋性和魯棒性等,降低路由過程中的能量消耗[11]。在WSN中引入ACO的原因主要有以下4點:

1)節(jié)點能量有限

WSN中的節(jié)點能量、存儲容量有限,運(yùn)算資源相對匱乏,在設(shè)計WSN路由協(xié)議時,需優(yōu)先考慮路由過程中的節(jié)點能耗與負(fù)載均衡問題。將ACO引入到WSN路由中,利用其群體智能特征可自主地尋找最優(yōu)路徑,節(jié)省節(jié)點能量,平衡網(wǎng)絡(luò)負(fù)載。此外,ACO算法簡單,更容易實現(xiàn)。

2)自組織網(wǎng)絡(luò)

WSN的傳感器節(jié)點通過飛機(jī)播撒的方式投放到野外環(huán)境中,隨機(jī)性強(qiáng)且各節(jié)點之間無固定的中心,需根據(jù)野外環(huán)境、拓?fù)湟?guī)則以及路由算法,在無人監(jiān)管的條件下,自主生成一個網(wǎng)絡(luò),完成各項任務(wù)。ACO中的螞蟻通過正向反饋原則逐步探索,獲取最優(yōu)路徑。在尋徑螞蟻找到最優(yōu)路徑后,會吸引更多的螞蟻參與到該路徑中,可以在得到最優(yōu)路徑的同時,提高節(jié)點能量的利用率。

3)網(wǎng)絡(luò)結(jié)構(gòu)的動態(tài)性

WSN中的節(jié)點由于能量耗盡或不能及時更換,導(dǎo)致部分節(jié)點死亡,加上通信環(huán)境和應(yīng)用場景的變化等因素,使得WSN的拓?fù)浣Y(jié)構(gòu)會經(jīng)常發(fā)生變化,ACO利用其本身的魯棒性,能夠很好地應(yīng)對這一情況。在網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時,螞蟻采用啟發(fā)式的路徑搜索方式,及時做出調(diào)整并再次尋找最優(yōu)路徑,其適應(yīng)性較好且反應(yīng)速度較快。

4)多跳傳輸

多跳傳輸是通過多個節(jié)點的協(xié)助轉(zhuǎn)發(fā)到達(dá)Sink節(jié)點,這種通信方式能夠有效地利用全網(wǎng)絡(luò)資源,盡可能以低能耗、短時延在復(fù)雜的拓?fù)渲姓业阶顑?yōu)路徑。在多跳傳輸?shù)倪^程中,如何選擇合適的下一跳節(jié)點是路由算法中影響能耗的一個重要問題。在WSN中引入ACO算法,可以根據(jù)節(jié)點信息素、剩余能量等因素來進(jìn)行決策,經(jīng)過多輪執(zhí)行后,逐漸接近最優(yōu)路徑,減少尋找最優(yōu)路徑的時間和能耗,平衡網(wǎng)絡(luò)負(fù)載。

3 E-EEABR算法

3.1 網(wǎng)絡(luò)距離帶和搜索角度

在經(jīng)典的蟻群算法中,螞蟻下一步的轉(zhuǎn)移由狀態(tài)轉(zhuǎn)移概率函數(shù)決定,該函數(shù)取決于下一跳節(jié)點對螞蟻的啟發(fā)作用和信息素濃度,而信息素濃度的使用導(dǎo)致在尋徑后期易陷入局部最優(yōu)路徑[9]。此外,無線傳感器節(jié)點數(shù)量巨大且隨機(jī)分布,節(jié)點會因能量耗盡而失效,同時會有新節(jié)點加入通信過程中,使得WSN的網(wǎng)絡(luò)拓?fù)浣?jīng)常性發(fā)生變動。因此,若螞蟻在尋找下一跳節(jié)點時沒有明確的目的,則既浪費(fèi)了節(jié)點能量又延長了尋徑時間[10]。為了充分利用有限的節(jié)點能量和當(dāng)前的信息素濃度,在蟻群路由優(yōu)化算法中引入距離帶的概念[11],優(yōu)化螞蟻尋找下一跳節(jié)點的方式,避免節(jié)點的盲目轉(zhuǎn)發(fā),其原理如圖2所示。

圖2 距離帶示意圖Fig.2 Schematic diagram of distance band

在圖2中,假設(shè)處于n層的節(jié)點i為源節(jié)點,它在選擇下一跳節(jié)點時,限定只能選擇當(dāng)前層n或鄰近層n-1、n+1內(nèi)的節(jié)點,則其鄰近節(jié)點只有節(jié)點A～節(jié)點F和節(jié)點j。按照上述規(guī)則,節(jié)點i的下一跳節(jié)點只能選擇鄰近層節(jié)點,即節(jié)點A～節(jié)點F和節(jié)點j,而不能選擇節(jié)點G,即將遠(yuǎn)離源節(jié)點i的節(jié)點排除出去。同時,該方法可減少螞蟻向Sink節(jié)點轉(zhuǎn)移的跳數(shù)和能耗。由于節(jié)點A距離Sink節(jié)點較遠(yuǎn),節(jié)點i下一跳的重點選擇對象集中在節(jié)點B、節(jié)點C、節(jié)點D、節(jié)點E、節(jié)點F和節(jié)點j。

然而,依靠距離帶只能決定下一跳節(jié)點的選擇區(qū)域,并不能確定最佳路徑的方向?，F(xiàn)有的蟻群優(yōu)化算法在選取下一跳節(jié)點時,并沒有考慮該節(jié)點是否靠近Sink節(jié)點,導(dǎo)致尋徑螞蟻有時會選擇與Sink節(jié)點相反的方向,產(chǎn)生無關(guān)路徑,浪費(fèi)節(jié)點能量。因此,在距離帶的基礎(chǔ)上引入搜索角度的概念,具體原理如圖3所示。

圖3 搜索角度示意圖Fig.3 Schematic diagram of search angle

本文通過計算源節(jié)點i到Sink節(jié)點的連線與源節(jié)點i到下一跳節(jié)點連線的夾角,結(jié)合角度因子和距離因子來確定最佳路徑方向。搜索角度一般限制在0°～90°,θ越小表示螞蟻從源節(jié)點i到Sink節(jié)點的距離越接近直線,在尋徑過程中,節(jié)點越靠近源節(jié)點i到Sink節(jié)點間的直線,能量消耗越少,則其成為下一跳節(jié)點的概率越大。從圖2可以看出,0°<θ1<θ2<θ3<θ4<90°,其中,θ1最小表示節(jié)點j成為下一跳節(jié)點的可能性最大。

3.2 改進(jìn)的路徑啟發(fā)函數(shù)

雖然上述方案能夠精確引導(dǎo)螞蟻尋找下一跳節(jié)點,但是當(dāng)多個候選節(jié)點的角度和距離相差不大時,節(jié)點之間會出現(xiàn)回旋式跳轉(zhuǎn)以及能耗不均等問題。尤其是Sink節(jié)點附近的“熱”節(jié)點相比其他位置的節(jié)點,更容易因負(fù)載過重而導(dǎo)致出現(xiàn)能量“熱區(qū)”。當(dāng)這些節(jié)點的能量耗盡后,網(wǎng)絡(luò)的連通性被嚴(yán)重破壞,出現(xiàn)“熱點”問題,使網(wǎng)絡(luò)進(jìn)入癱瘓狀態(tài)?！盁狳c”問題的出現(xiàn)在一定的程度上降低了ACO自身的搜索速度和收斂速度,網(wǎng)絡(luò)的生存周期也受到影響[12]。

為有效地解決Sink節(jié)點附近“熱”節(jié)點的失效問題,本文采用一種激勵策略,篩選出能量較低且距離較遠(yuǎn)的“熱”節(jié)點,并禁止其加入到傳輸路徑中。同時,把剩余的能量充足且距Sink節(jié)點較近的節(jié)點加入到傳輸路徑中,以均衡“熱”節(jié)點的平均剩余能量,延長網(wǎng)絡(luò)的生存時間。該策略的主要原理如圖4所示。

圖4 激勵策略示意圖Fig.4 Schematic diagram of incentive strategy

(7)

假設(shè)D、E、Sink節(jié)點處在網(wǎng)絡(luò)節(jié)點能量傳輸負(fù)載過重的“熱區(qū)”中,并且節(jié)點D和節(jié)點E是利用距離帶、搜索角度和距離因子篩選出來的距離Sink節(jié)點最近的“熱”節(jié)點,當(dāng)節(jié)點D、節(jié)點E與Sink節(jié)點的距離較近時,會存在能耗不均和回旋式跳轉(zhuǎn)等問題。

圖5 節(jié)點激勵值更新示意圖Fig.5 Schematic diagram of incentive value update of node

從上述分析可以得出,本文提出的激勵值策略與原始ACO算法通過信息素濃度與啟發(fā)函數(shù)的大小進(jìn)行交流相比,螞蟻更傾向于更新短路徑上的信息。同時,該策略使得螞蟻之間的交流除了依靠信息素之外,還會參考訪問過的節(jié)點信息,從而能夠平衡Sink節(jié)點周圍的整體能量水平,促進(jìn)螞蟻之間的交流,加快算法的收斂速度。

為更好地利用激勵值,避免由于“熱”節(jié)點的失效而出現(xiàn)網(wǎng)絡(luò)空洞現(xiàn)象,引導(dǎo)螞蟻更趨向于Sink節(jié)點,本文提出的優(yōu)化信息素啟發(fā)公式如下:

Ωi,Sink=di,j+dj,Sink

(8)

(9)

3.3 狀態(tài)轉(zhuǎn)移公式改進(jìn)

在WSN路徑建立的初始階段,各路徑信息素和啟發(fā)函數(shù)的作用區(qū)分不明顯,導(dǎo)致信息素對路徑建立的作用很小,尋徑螞蟻難以在短時間內(nèi)搜索到一條到Sink節(jié)點的最優(yōu)路徑。大多數(shù)現(xiàn)有的改進(jìn)算法在確定下一跳節(jié)點的概率時,只考慮源節(jié)點與候選節(jié)點的距離以及信息素濃度2個方面,并沒有考慮候選節(jié)點的剩余能量大小、是否與Sink節(jié)點同徑等因素,造成長度較短且剩余能量充足的路線被大量螞蟻頻繁訪問,節(jié)點能量損耗嚴(yán)重,失效節(jié)點數(shù)目增多[13]。

針對上述問題,本文引入一個含能量因子的偽隨機(jī)比例(見式(10)和式(11))估測策略來優(yōu)化狀態(tài)轉(zhuǎn)移公式[14],使得螞蟻能夠在算法初期各路徑信息素和啟發(fā)信息作用不明顯的情況下,快速集中到概率最大的路徑上,提高算法的收斂速度。同時,平衡最優(yōu)路徑上節(jié)點能量較少但螞蟻頻繁訪問的節(jié)點的能耗,延長網(wǎng)絡(luò)壽命,避免算法出現(xiàn)過早停滯的現(xiàn)象[15]。

(10)

(11)

其中,q是尋徑螞蟻在選擇下一跳節(jié)點之前產(chǎn)生的一個隨機(jī)數(shù),且q∈(0,1],q0∈[0,1],α、β、γ分別是信息素濃度、啟發(fā)函數(shù)和能量影響因子的權(quán)重系數(shù),其數(shù)值越大,說明該項被重視的程度越高,Ei(t)表示源節(jié)點i的剩余能量,Ej(t)表示候選節(jié)點j的剩余能量。若螞蟻在當(dāng)前節(jié)點產(chǎn)生的隨機(jī)數(shù)q滿足q≤q0,則選擇[τij(t)]α[ηij(t)]β[κij(t)]γ最大的節(jié)點作為下一跳,否則按照式(12)選擇下一跳。

(12)

在改進(jìn)的狀態(tài)轉(zhuǎn)移函數(shù)中,尋徑螞蟻在尋找下一跳節(jié)點時,首先根據(jù)距離帶和搜索角的規(guī)則,對源節(jié)點附近的節(jié)點進(jìn)行篩選,然后考慮下一跳節(jié)點的信息素濃度、剩余能量等影響因素。通過上述兩個步驟,進(jìn)一步優(yōu)化節(jié)點概率選擇,避免網(wǎng)絡(luò)延時、不必要的能耗和局部最優(yōu)等問題。尋徑螞蟻能夠根據(jù)自身位置與下一跳節(jié)點之間的關(guān)系進(jìn)行自適應(yīng)調(diào)節(jié),使得下一跳能量充足且距離Sink節(jié)點較近的節(jié)點加入到螞蟻的最優(yōu)路徑中,避免由于最優(yōu)路徑上節(jié)點負(fù)載過重導(dǎo)致出現(xiàn)網(wǎng)絡(luò)癱瘓的問題。

3.4 信息素更新規(guī)則改進(jìn)

尋徑螞蟻從源節(jié)點出發(fā)到達(dá)Sink節(jié)點后,Sink節(jié)點會根據(jù)尋徑螞蟻包攜帶的信息,計算螞蟻經(jīng)過的路徑長度以及路徑中的信息素濃度,并將計算結(jié)果反饋給回退螞蟻,完成信息素更新。當(dāng)回退螞蟻到達(dá)源節(jié)點后,一次完整的螞蟻包收發(fā)過程結(jié)束,同時算法完成一次路由優(yōu)化,源節(jié)點將回退螞蟻消亡并生成新的尋徑螞蟻進(jìn)行下一輪的路徑尋優(yōu),如此重復(fù)循環(huán)此過程,直至達(dá)到算法設(shè)置的最大迭代次數(shù),找到最優(yōu)路徑[16]。

然而,從ACO的生物特性上講,螞蟻的信息素更新是一個正反饋過程,螞蟻在完成最短路徑搜索后,利用釋放的信息素吸引大量螞蟻加入此路徑,造成該最“佳”路徑的節(jié)點能量耗盡而過早死亡[17]。此外,從算法運(yùn)行的角度來講,傳統(tǒng)ACO的信息素采用累加的方式,不斷地增加上一輪找到的最優(yōu)路徑上的信息素濃度,導(dǎo)致算法容易陷入局部最優(yōu),而不是全局最優(yōu)。特別地,對于Sink節(jié)點附近分布比較密集的“熱”節(jié)點來講,雖然它們的信息素濃度以一定的速度揮發(fā),但信息素增加次數(shù)高于揮發(fā)量[18],且網(wǎng)絡(luò)節(jié)點的能量充足。此時,距離Sink節(jié)點最近的非最佳路徑會成為螞蟻進(jìn)行下一跳的最佳路徑。同時,源節(jié)點到Sink節(jié)點的路徑上還存在能耗不均、網(wǎng)絡(luò)全局活躍度低等問題,而在Sink節(jié)點附近的“熱區(qū)”內(nèi),存在路由跳數(shù)較多、節(jié)點間隔較小的路徑,影響Δτk的準(zhǔn)確性[19]。

本文利用節(jié)點能量與平均能量的偏離值作為信息素增量公式的參考因子。當(dāng)偏離值較大時,增加的信息素會相應(yīng)地減少,使得回退螞蟻能夠自適應(yīng)地進(jìn)行調(diào)整,避免源節(jié)點在發(fā)送下一輪螞蟻包時加入到能量相差過大的路徑中。具體計算過程如下:

τij(t)=(1-ρ)×τij(t)+Δτij(t)

(13)

(14)

其中,Fdk表示尋徑螞蟻的能量消耗,σk(s)表示回退螞蟻k從Sink節(jié)點回到源節(jié)點時,源節(jié)點的能量es與路徑平均能量Eavg k的偏離值,σk(s)的計算過程如下:

σk(s)=(es-Eavg k)2

(15)

信息素函數(shù)的增量計算如下:

(16)

通過對信息素公式進(jìn)行優(yōu)化,使得通過路徑上節(jié)點剩余能量較大時積累的信息素增多[20],從而有效避免路徑上能量較少的節(jié)點因負(fù)載過重而失效,同時提高對非最佳路徑的信息素補(bǔ)償,有效地解決全局網(wǎng)絡(luò)的能量均衡問題。

4 算法流程

4.1 具體實現(xiàn)步驟

本文E-EEABR算法的具體實現(xiàn)步驟如下:

步驟1初始化各項參數(shù)。在t=0時刻,設(shè)置節(jié)點的初始能量為E0,初始信息素濃度τij(0)=0,迭代次數(shù)為N=0,允許最大迭代次數(shù)為Nmax。

步驟3螞蟻按照k=k+1搜尋路線。

步驟6判斷螞蟻是否到達(dá)Sink節(jié)點,即k

步驟7繼續(xù)執(zhí)行步驟1～步驟6,直到k只螞蟻都能到達(dá)Sink節(jié)點。

步驟8判斷區(qū)域內(nèi)螞蟻可能經(jīng)過的路徑,如果有螞蟻,則利用式(13)和式(14)進(jìn)行信息素更新。

4.2 改進(jìn)的E-EEABR算法流程

本文改進(jìn)的E-EEABR算法流程如圖6所示。

圖6 E-EEABR算法流程Fig.6 Procedure of E-EEABR algorithm

5 仿真結(jié)果與分析

本文在Matlab 2016a環(huán)境下進(jìn)行仿真,并將E-EEABR算法與IEEABR算法、IARA算法進(jìn)行對比。為了確保仿真結(jié)果的穩(wěn)定性與可靠性,取多次仿真結(jié)果的平均值,并分別從路徑平均跳數(shù)、節(jié)點平均能量消耗、網(wǎng)絡(luò)能耗方差、網(wǎng)絡(luò)生命周期4個方面驗證E-EEABR算法的有效性。本文使用First-order Radio Model(FRM)能量傳輸模型。仿真參數(shù)設(shè)置如表1所示,傳感器節(jié)點在100 m×100 m區(qū)域內(nèi)隨機(jī)分布,螞蟻遍歷次數(shù)Nmax=30。

表1 仿真參數(shù)設(shè)置Table 1 Simulation parameter settings

5.1 路徑平均跳數(shù)

路徑跳數(shù)可以反映算法中螞蟻尋找最優(yōu)路徑的能力。圖7給出3種算法平均路徑跳數(shù)的變化趨勢?？梢钥闯?IEEABR、IARA和E-EEABR算法分別在第25跳、第18跳和第13跳時達(dá)到收斂,說明E-EEABR算法相比其他2種算法,能夠降低數(shù)據(jù)包的丟失率,提高數(shù)據(jù)的傳輸效率。

圖7 路徑平均跳數(shù)對比Fig.7 Comparison of average hop counts of paths

5.2 節(jié)點平均能量消耗

網(wǎng)絡(luò)生存周期與總能量消耗成反比,網(wǎng)絡(luò)節(jié)點的總能耗越小,網(wǎng)絡(luò)生存周期越長。圖8給出3種算法的節(jié)點平均能量消耗的仿真結(jié)果?？梢钥闯?E-EEABR算法的節(jié)點平均能量消耗最少,這是因為該算法在計算下一跳節(jié)點的轉(zhuǎn)移概率之前,采用含能量因子的偽隨機(jī)比例規(guī)則策略對下一跳節(jié)點進(jìn)行篩選,避免了對無關(guān)路徑的搜索,減少冗余節(jié)點的網(wǎng)絡(luò)開銷和能量的傳輸損耗。IEEABR算法和IARA算法在選擇下一跳節(jié)點時重點關(guān)注與下一跳節(jié)點的距離以及剩余能量的大小,導(dǎo)致螞蟻在尋徑時產(chǎn)生大量的無關(guān)路徑,增大節(jié)點能量的損耗[20]。

圖8 節(jié)點平均能量消耗對比Fig.8 Comparison of average energy consumption of nodes

5.3 網(wǎng)絡(luò)能耗方差

在WSN中,由于節(jié)點隨機(jī)分布、環(huán)境復(fù)雜多樣,因此網(wǎng)絡(luò)區(qū)域內(nèi)各節(jié)點能耗也不盡相同。對于新部署的網(wǎng)絡(luò)或者某些由于大量節(jié)點失效而必須重新部署的區(qū)域,必須要考慮整體節(jié)點的均衡程度。能耗方差常用來反映WSN整體節(jié)點的均衡情況,網(wǎng)絡(luò)能耗的方差越小,表示網(wǎng)絡(luò)區(qū)域內(nèi)的能耗越均衡。本文從E-EEABR的30輪遍歷結(jié)果中隨機(jī)抽取10輪的節(jié)點總能量損耗,然后對3種算法的能耗方差進(jìn)行對比,結(jié)果如圖9所示。

圖9 網(wǎng)絡(luò)能耗方差對比Fig.9 Comparison of variance of network energy consumption

可以看出,E-EEABR算法的方差最小,其主要原因是另外2種算法在尋找下一跳時,可能會選擇那些距離較遠(yuǎn)且與最優(yōu)路徑偏差較大的節(jié)點,導(dǎo)致大量無關(guān)路徑產(chǎn)生,能量損耗較大。此外,IEEABR和IARA算法采用累加的信息素更新方式,螞蟻尋徑過程經(jīng)常陷入局部最優(yōu),能耗均衡性差,而E-EEABR算法中的螞蟻在尋找下一跳節(jié)點時,綜合考慮候選節(jié)點的剩余能量、距Sink節(jié)點的偏離角度等因素,并在信息素更新公式中添加σk(s),當(dāng)下一跳節(jié)點與最優(yōu)路徑相差較大時,可以及時修正該節(jié)點的信息素濃度,優(yōu)化路徑上節(jié)點能量與跳數(shù)的關(guān)系,在一定程度上均衡網(wǎng)絡(luò)能耗。

5.4 網(wǎng)絡(luò)生存周期

將網(wǎng)絡(luò)區(qū)域內(nèi)的節(jié)點數(shù)量從100遞增到500,每次增加100個。定義首個節(jié)點死亡的時間為網(wǎng)絡(luò)生存周期,網(wǎng)絡(luò)生存周期的結(jié)果對比如圖10所示?？梢钥闯?當(dāng)節(jié)點數(shù)量一定時,E-EEABR算法出現(xiàn)首個節(jié)點死亡的時間比其他2種算法晚,說明其對網(wǎng)絡(luò)的生存周期有延長作用。這是因為E-EEABR算法改進(jìn)了信息素公式,對最優(yōu)路徑上的節(jié)點進(jìn)行了篩選。同時,E-EEABR算法的首個節(jié)點死亡的時間波動幅度不大,其網(wǎng)絡(luò)擴(kuò)展性和魯棒性較好,而其他2種算法沒有對運(yùn)行路徑上的低能節(jié)點采取維護(hù)措施,導(dǎo)致首個節(jié)點的死亡時間提前,網(wǎng)絡(luò)生存周期縮短。

圖10 網(wǎng)絡(luò)生存周期對比Fig.10 Comparison of network lifetime

6 結(jié)束語

本文在EEABR算法的基礎(chǔ)上,提出改進(jìn)蟻群的能量優(yōu)化路由算法E-EEABR。綜合考慮距離帶、搜索角度和距離因子3個因素,精確選取下一跳路由,利用激勵策略均衡負(fù)載過重的“熱”節(jié)點的傳輸任務(wù),通過偽隨機(jī)比例規(guī)則優(yōu)化概率轉(zhuǎn)移函數(shù),增強(qiáng)算法的尋優(yōu)能力。仿真結(jié)果表明,E-EEABR算法能夠有效均衡全局網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)生存周期。然而,本文的仿真環(huán)境設(shè)置較為理想化,未考慮其他因素,如針對Sink節(jié)點的逐跳回溯追蹤攻擊等的影響,下一步可對WSN的安全機(jī)制進(jìn)行研究,以提高傳輸可靠性。