朱大偉,李紀(jì)欣

1(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,太原 030024)

2(中國(guó)電子科技集團(tuán)公司第三十三研究所 科技發(fā)展事業(yè)部,太原 030032)

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)[1]是由大量靜止或移動(dòng)的傳感器節(jié)點(diǎn)組成,節(jié)點(diǎn)通過(guò)自組織的無(wú)線通信協(xié)議實(shí)現(xiàn)數(shù)據(jù)處理、傳輸以及通訊等功能形成的分布式并行系統(tǒng).近年來(lái)在野外監(jiān)控、軍事監(jiān)測(cè)等眾多領(lǐng)域受到廣泛關(guān)注和應(yīng)用.WSN 節(jié)點(diǎn)[2]一般隨機(jī)部署在目標(biāo)監(jiān)測(cè)區(qū)域內(nèi),節(jié)點(diǎn)能量通過(guò)自身干電池提供,由于地理環(huán)境和節(jié)點(diǎn)的分布特點(diǎn),更換電源的可操作性差,所以能量成為制約無(wú)線傳感器網(wǎng)絡(luò)生命周期的首要因素.為了充分合理利用無(wú)線傳感器網(wǎng)絡(luò),依據(jù)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布和節(jié)點(diǎn)能量有限的兩個(gè)特性.兩個(gè)問(wèn)題需要著力解決,一個(gè)是在隨機(jī)分布的節(jié)點(diǎn)之中盡快找到一條盡可能最優(yōu)的收斂路徑,另一個(gè)是保證收斂路徑上的節(jié)點(diǎn)消耗盡可能少的能量且相對(duì)負(fù)載均衡,以延長(zhǎng)節(jié)點(diǎn)使用時(shí)長(zhǎng)和網(wǎng)絡(luò)的生命周期.

為了尋找最佳路徑,國(guó)內(nèi)外展開(kāi)廣泛深入的研究,很多切實(shí)有效的方法被提出.其中最具代表性的是將蟻群算法與無(wú)線傳感器網(wǎng)絡(luò)路由算法相結(jié)合.蟻群優(yōu)化算法將問(wèn)題求解的快速性、全局優(yōu)化性以及高度的自組織性等特點(diǎn)合理結(jié)合,與無(wú)線傳感器網(wǎng)絡(luò)低能耗、自組織的大規(guī)模網(wǎng)絡(luò)路由快速建立要求極其相似,有助于建立面向數(shù)據(jù)為中心的匯聚路由[3].梁華為將蟻群算法與無(wú)線傳感器網(wǎng)絡(luò)路由算法相結(jié)合,提出了最基本的蟻群無(wú)線傳感器路由算法ARA (ACO-Based Routing Algorithm)[4],尋優(yōu)能力十分有限.在此基礎(chǔ)上,焦斌改進(jìn)的蟻群算法IARA (Improved Ant-based Routing Algorithm)[5],綜合考慮了節(jié)點(diǎn)剩余能量,傳輸方向和節(jié)點(diǎn)距離等因素,重點(diǎn)改進(jìn)了蟻群算法的概率公式.此外,羅旭提出了改進(jìn)的蟻群算法OARA (Optimization in Ant-based Routing Algorithm)[6],考慮到節(jié)點(diǎn)之間的距離和節(jié)點(diǎn)的剩余能量,在概率公式中引入罰函數(shù)和動(dòng)態(tài)權(quán)重因子.然而上述的各種改進(jìn)蟻群算法綜合起來(lái)存在蟻群算法收斂與否取決于搜索半徑的選擇、路徑存在往返跳躍導(dǎo)致額外能量消耗、選取節(jié)點(diǎn)能量過(guò)低無(wú)法支持信息傳輸?shù)葐?wèn)題.

為了克服上述弊端,本文通過(guò)采取“三步遞進(jìn)式”尋找下一跳候選節(jié)點(diǎn)的方法來(lái)優(yōu)化傳統(tǒng)蟻群算法,并分別提出了DEARA (Dynamic Energy ARA)和DDEARA(Dynamic Direction Energy ARA)蟻群算法.首先,DEARA 算法通過(guò)分別引入動(dòng)態(tài)半徑搜索因子保證蟻群算法能夠收斂和能量預(yù)測(cè)因子避免節(jié)點(diǎn)能量過(guò)度消耗出現(xiàn)負(fù)值的不合理現(xiàn)象.其次,DDEARA 算法在DEARA 算法基礎(chǔ)之上引入方向因子[7],避免反方向無(wú)關(guān)節(jié)點(diǎn)被選為下一跳候選節(jié)點(diǎn),進(jìn)一步提高算法尋優(yōu)能力.DEARA 和DDEARA 蟻群算法優(yōu)化措施是在逐步縮小下一跳候選節(jié)點(diǎn)的范圍,這一具體的確定性因素,而不是僅僅提高了某些節(jié)點(diǎn)被選為下一跳節(jié)點(diǎn)的概率值,這一隨機(jī)性因素,使得尋優(yōu)結(jié)果符合預(yù)期設(shè)想.

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

本文研究的無(wú)線傳感器網(wǎng)絡(luò)模型如圖1所示,由N個(gè)隨機(jī)分布的無(wú)線傳感器節(jié)點(diǎn)構(gòu)成自組網(wǎng)多跳網(wǎng)絡(luò)模型[8].圖中,無(wú)線傳感器節(jié)點(diǎn)隨機(jī)的部署在一定區(qū)域內(nèi),位置相對(duì)固定且具備自定位功能.無(wú)線傳感器網(wǎng)絡(luò)可以通過(guò)區(qū)域內(nèi)分布的無(wú)線傳感器節(jié)點(diǎn),實(shí)時(shí)采集區(qū)域內(nèi)的相關(guān)信息,并以“自組織”的方式構(gòu)建一條通路,通過(guò)最外側(cè)的節(jié)點(diǎn)(網(wǎng)關(guān)),將信息經(jīng)基站sink 節(jié)點(diǎn)匯總到因特網(wǎng)中,以便后期的分析處理.為了分析方便且不失一般性,考慮網(wǎng)絡(luò)中分布的所有節(jié)點(diǎn)一致,即符合相同的能量傳輸模型,且初始能量相同為E0(不妨設(shè)E0為單位1 J).定義剩余能量值小于Einit(Einit=0.1 J)的節(jié)點(diǎn)為死亡節(jié)點(diǎn),該節(jié)點(diǎn)的剩余能量已無(wú)法成功傳輸一次完整數(shù)據(jù),因此不能被選為下一跳候選節(jié)點(diǎn).為了便于死亡節(jié)點(diǎn)的分析,下面重點(diǎn)分析節(jié)點(diǎn)能量傳輸模型.

圖1 無(wú)線傳感器網(wǎng)絡(luò)模型

1.2 能量傳輸模型

在無(wú)線通信過(guò)程中,網(wǎng)絡(luò)節(jié)點(diǎn)能耗主要包括電路損耗與功率放大損耗[9],文獻(xiàn)[10]給出了相應(yīng)的能量損耗模型,當(dāng)前節(jié)點(diǎn)W向距離為d的節(jié)點(diǎn)傳輸Bbit數(shù)據(jù)時(shí),如果兩通信節(jié)點(diǎn)之間間距為d(d≤d0)就選取自由空間模型,通信節(jié)點(diǎn)數(shù)據(jù)傳播速率衰減和d2成正比.當(dāng)位置間距為d(d>d0)就選取多路徑衰減模型,且數(shù)據(jù)傳輸所損耗能量和d4成正比.由此給出節(jié)點(diǎn)傳輸數(shù)據(jù)能耗如式(1)所示:

在節(jié)點(diǎn)通信過(guò)程中,每個(gè)節(jié)點(diǎn)接收并處理B bit數(shù)據(jù)時(shí)所需要消耗的能量如式(2)所示:

其中,Eelec表示傳感器網(wǎng)絡(luò)在傳輸或者接收數(shù)據(jù)時(shí)電路上的損耗.εamp代表數(shù)據(jù)在多路徑衰落模型傳輸過(guò)程中的損耗.

2 蟻群系統(tǒng)(ACS)算法模型

1992年Dorigom 在他的博士論文中首次引入了蟻群算法(Ant Colony Optimization,ACO)[11].蟻群算法是一種啟發(fā)式的仿生進(jìn)化算法,屬于隨機(jī)搜索算法的一種[12].螞蟻從巢穴出發(fā)尋找食物的過(guò)程中,根據(jù)其他螞蟻在路徑上留下的“信息素”濃度,最高效率的尋找到離巢穴最近的食物.基本蟻群算法作為最原始的蟻群算法,在解決小規(guī)模旅行商問(wèn)題時(shí)全局收斂速度快,但是在面對(duì)大規(guī)模旅行商問(wèn)題時(shí)全局收斂速度較慢.針對(duì)這些問(wèn)題,Dorigo 和Gambardella 在1997年共同提出了蟻群系統(tǒng)(Ant Colony System,ACS)[13].在基本螞蟻算法基礎(chǔ)之上提出了3 點(diǎn)改進(jìn).首先,下一跳狀態(tài)轉(zhuǎn)移規(guī)則得到優(yōu)化.其次,只在最優(yōu)路徑上作全局信息素更新.最后,全局信息素的更新的同時(shí)結(jié)合局部信息素更新規(guī)則.

2.1 下一跳狀態(tài)轉(zhuǎn)移規(guī)則的優(yōu)化

在ACS 中,螞蟻 對(duì)下一跳節(jié)點(diǎn)的選擇都是根據(jù)一個(gè)偽隨機(jī)比例[14]來(lái)進(jìn)行的,從當(dāng)前節(jié)點(diǎn)i到下一節(jié)點(diǎn)j的選擇遵循式(3)～式(5).

其中,α表示信息啟發(fā)因子,表明軌跡的相對(duì)重要性.β表示期望啟發(fā)因子,表明能見(jiàn)度的相對(duì)重要性.τij表示信息素濃度,ηij為路徑啟發(fā)因子,q0(0

2.2 局部信息素的更新

為了加強(qiáng)螞蟻的搜索能力,結(jié)合極大極小蟻群算法[15],引入信息素的最小濃度 τmin,信息素的最大濃度τmax,這樣能夠避免因?yàn)槟承┞窂降男畔⑺貪舛冗^(guò)大或者過(guò)小,導(dǎo)致螞蟻過(guò)分集中而陷入局部最優(yōu),制約了蟻群算法的全局搜索能力.局部信息素更新公式如式(6)～式(8).

其中,τmin表示信息素最小濃度,τmax是信息素的上限值最大濃度,ρ為信息素的揮發(fā)系數(shù),其值越大意味著路徑上的信息素?fù)]發(fā)越快,取值范圍在(0,1).? τij表示本次循環(huán)中路徑 (i,j)上 的信息素增量,表示螞蟻k在(t,t+1)的時(shí)間段內(nèi)留在路徑(i,j)上的信息素量.Q表示信息素強(qiáng)度,是常量固定值,Lk為螞蟻k在本次循環(huán)中經(jīng)過(guò)的路徑長(zhǎng)度.

2.3 全局信息素的更新

在ACS 算法中,當(dāng)所有螞蟻完成一次迭代后,會(huì)對(duì)螞蟻搜尋到的最優(yōu)路徑進(jìn)行全局信息素更新.而其它非最優(yōu)路徑的信息素則按一定的系數(shù)不斷減少.這樣可以使大多數(shù)的螞蟻下一次優(yōu)先選擇最優(yōu)路徑,提升了ACS 算法收斂速度.信息素全局更新公式如式(9)、式(10).

其中,Lelite表示一代所有螞蟻搜索完成后全局最優(yōu)路徑的長(zhǎng)度.

3 算法改進(jìn)

傳統(tǒng)蟻群優(yōu)化算法均集中在提高節(jié)點(diǎn)被選中的概率值(隨機(jī)事件發(fā)生的概率值),依然存在很大的盲目性與不確定性.本文改進(jìn)算法通過(guò)逐步縮小下一跳候選節(jié)點(diǎn)的范圍,然后在有限的候選節(jié)點(diǎn)范圍內(nèi)依照概率值進(jìn)行選取下一跳節(jié)點(diǎn),這樣擺脫了傳統(tǒng)蟻群算法的完全隨機(jī)性.

3.1 動(dòng)態(tài)半徑搜索因子

利用動(dòng)態(tài)半徑搜索因子尋找下一跳候選節(jié)點(diǎn)能夠提高蟻群算法的收斂性.動(dòng)態(tài)半徑搜索因子使得螞蟻在當(dāng)前半徑圓內(nèi)找不到下一跳候選節(jié)點(diǎn)時(shí),即可通過(guò)擴(kuò)大搜索半徑直至能夠找到下一跳候選節(jié)點(diǎn)為止,從而保證蟻群算法最終能夠收斂.

螞蟻k首先在以當(dāng)前節(jié)點(diǎn)W為圓心,半徑為r的圓內(nèi)尋找符合條件的下一跳候選節(jié)點(diǎn),如果半徑為r的圓內(nèi)沒(méi)有符合條件的下一跳候選節(jié)點(diǎn),則擴(kuò)大搜索半徑r至 2r,在半徑為 2r的圓內(nèi)繼續(xù)尋找符合條件的下一跳候選節(jié)點(diǎn).圖2中顯示有符合條件的節(jié)點(diǎn)1 和節(jié)點(diǎn)2,因此將節(jié)點(diǎn)1 和節(jié)點(diǎn)2 選為下一跳候選節(jié)點(diǎn).動(dòng)態(tài)半徑搜索因子優(yōu)勢(shì)在于能夠避免螞蟻直接在較大半徑范圍內(nèi)尋找下一跳候選節(jié)點(diǎn).雖然下一跳節(jié)點(diǎn)離當(dāng)前節(jié)點(diǎn)距離越遠(yuǎn),本次螞蟻尋找路徑越容易收斂,但是由于距離較遠(yuǎn),根據(jù)能量消耗公式可知,距離越大消耗的能量越大.經(jīng)過(guò)一次完整數(shù)據(jù)傳輸之后,節(jié)點(diǎn)可能消耗了所有的能量,間接導(dǎo)致本次尋優(yōu)的路徑失效又要重新尋找最優(yōu)路徑.所以要限制螞蟻搜索半徑范圍,優(yōu)先在小范圍內(nèi)尋找下一跳候選節(jié)點(diǎn),這樣能夠使更多節(jié)點(diǎn)參與到收斂路徑中,通過(guò)多點(diǎn)參與均衡相鄰節(jié)點(diǎn)之間距離,降低單個(gè)節(jié)點(diǎn)能耗,提高單個(gè)節(jié)點(diǎn)傳輸數(shù)據(jù)的次數(shù),進(jìn)而達(dá)到延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)壽命的目標(biāo).

圖2 動(dòng)態(tài)半徑搜索因子示意圖

3.2 能量消耗預(yù)測(cè)因子

節(jié)點(diǎn)能量消耗預(yù)測(cè)因子的引入,能夠規(guī)避當(dāng)節(jié)點(diǎn)消耗完剩余能量卻沒(méi)有傳完所有數(shù)據(jù)的不利情況發(fā)生.螞蟻在尋找下一跳候選節(jié)點(diǎn)時(shí),首先要判斷當(dāng)前節(jié)點(diǎn)W和下一跳候選節(jié)點(diǎn)1 傳輸kbit數(shù)據(jù)時(shí)所要消耗的能量值E2是否大于當(dāng)前節(jié)點(diǎn)W的剩余能量值E1.只有當(dāng)(E2≤E1)時(shí)節(jié)點(diǎn)1 才會(huì)被成功選為下一跳候選節(jié)點(diǎn).傳統(tǒng)蟻群算法一方面由于沒(méi)有能量消耗預(yù)測(cè)機(jī)制,很可能造成當(dāng)前節(jié)點(diǎn)剩余能量值消耗完卻只傳輸了部分?jǐn)?shù)據(jù),這樣的一次傳輸工作是失敗的,不僅浪費(fèi)了當(dāng)前節(jié)點(diǎn)和之前所有節(jié)點(diǎn)傳輸數(shù)據(jù)消耗的能量,而且還造成當(dāng)前路徑終點(diǎn)不可達(dá).另一方面?zhèn)鹘y(tǒng)蟻群算法默認(rèn)節(jié)點(diǎn)只要有能量就能繼續(xù)工作且能夠傳完整數(shù)據(jù),可能造成節(jié)點(diǎn)工作一次后剩余能量值為負(fù)的不合理現(xiàn)象.

3.3 方向因子

通過(guò)引入方向因子尋找下一跳候選節(jié)點(diǎn),避免了反方向的無(wú)關(guān)節(jié)點(diǎn)被選中成為下一跳候選節(jié)點(diǎn).傳統(tǒng)的蟻群算法搜索下一跳候選節(jié)點(diǎn)時(shí),都是在以當(dāng)前節(jié)點(diǎn)W為圓心,半徑為r的整個(gè)圓內(nèi)尋找下一跳候選節(jié)點(diǎn),可能尋找到與當(dāng)前節(jié)點(diǎn)W和sink 節(jié)點(diǎn)N連線反方向范圍內(nèi)的節(jié)點(diǎn)2 作為下一跳候選節(jié)點(diǎn),這樣就增加了路徑長(zhǎng)度,既浪費(fèi)節(jié)點(diǎn)能量又弱化算法尋優(yōu)能力.方向因子的引入,可以限制下一跳候選節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)W和sink 節(jié)點(diǎn)N連線正方向的正負(fù) 90?范圍內(nèi)尋找.如圖3所示,當(dāng)前節(jié)點(diǎn)W在r半徑圓內(nèi)有符合條件的節(jié)點(diǎn)1 和節(jié)點(diǎn)2,因?yàn)楣?jié)點(diǎn)2、當(dāng)前節(jié)點(diǎn)W以及sink 節(jié)點(diǎn)N形成的夾角 β (β>90?),因此直接舍棄節(jié)點(diǎn)2.同理根據(jù)方向因子在節(jié)點(diǎn)3 和節(jié)點(diǎn)4 中選擇節(jié)點(diǎn)3 作為下一跳候選節(jié)點(diǎn).這樣有利于螞蟻一直在往 sink 節(jié)點(diǎn)N的方向?qū)ふ蚁乱惶蜻x節(jié)點(diǎn),避免找到反方向的無(wú)關(guān)節(jié)點(diǎn),減少路徑長(zhǎng)度節(jié)約節(jié)點(diǎn)能量消耗,提高算法尋優(yōu)能力.

圖3 方向因子示意圖

3.4 最優(yōu)路徑評(píng)價(jià)公式

傳統(tǒng)蟻群算法依據(jù)路徑最短評(píng)價(jià)指標(biāo)尋找最優(yōu)路徑,僅僅考慮路徑的距離長(zhǎng)短,評(píng)價(jià)指標(biāo)非常單一,本文算法評(píng)價(jià)指標(biāo)引入了節(jié)點(diǎn)平均剩余能量、節(jié)點(diǎn)最小剩余能量、最短路徑長(zhǎng)度、條數(shù)、節(jié)點(diǎn)剩余能量方差.

其中,Eaver表示節(jié)點(diǎn)平均剩余能量,Emin表示路徑所經(jīng)過(guò)節(jié)點(diǎn)中消耗能量的最小值,表示第m只螞蟻第k次迭代后走過(guò)的路徑長(zhǎng)度,表示第m只螞蟻第k次迭代后走過(guò)的路徑上的節(jié)點(diǎn)個(gè)數(shù),表示第m只螞蟻第k次迭代后走過(guò)的路徑上所有的節(jié)點(diǎn)剩余能量值的標(biāo)準(zhǔn)差.

的數(shù)值越大代表的路徑越好,每迭代完一次將最大值對(duì)應(yīng)的路徑作為本次迭代最優(yōu)路徑,然后更新此路徑上的信息素,便于后繼的螞蟻尋找路徑時(shí)優(yōu)先考慮這條路徑,所有的迭代完成后即可選出符合上述條件的最優(yōu)路徑.評(píng)價(jià)指標(biāo)中引入節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差,有利于最優(yōu)路徑上各節(jié)點(diǎn)剩余能量值大小接近.如果各節(jié)點(diǎn)剩余能量值懸殊太大,這樣的路徑可能發(fā)送一次完整數(shù)據(jù)就出現(xiàn)了死亡節(jié)點(diǎn),此條路徑就不能繼續(xù)使用,必須重新尋找一條最優(yōu)路徑.

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

為了驗(yàn)證上述的優(yōu)化蟻群算法DDEARA 的有效性,采用蒙特卡洛方法進(jìn)行計(jì)算機(jī)模擬仿真實(shí)驗(yàn).在一個(gè)(10×10)的范圍內(nèi),隨機(jī)布置S(S=100)個(gè)傳感器節(jié)點(diǎn).為了便于描述且不失一般性,不妨設(shè)點(diǎn)(0,0)為起始發(fā)送節(jié)點(diǎn),點(diǎn)(10,10)為終端sink 節(jié)點(diǎn),整個(gè)仿真實(shí)驗(yàn)中共有t(t=100)代螞蟻且每一代螞蟻有n(n=100)只.每次傳輸2 000 bit數(shù)據(jù).仿真結(jié)果如圖4.

4.1 最優(yōu)路徑連線圖

圖4對(duì)比了ARA、IARA、OARA、DEARA、DDEARA 5 種算法最終收斂的最優(yōu)路徑連線圖,直觀顯示了各種算法路徑經(jīng)過(guò)的節(jié)點(diǎn)個(gè)數(shù)以及節(jié)點(diǎn)分布情況.

從表1中可以看出ARA、OARA、IARA 算法各方面性能效果都差,由于ARA、OARA 算法路徑中參與的中間節(jié)點(diǎn)個(gè)數(shù)非常少,導(dǎo)致收斂路徑消耗的能量也非常小,但是相鄰節(jié)點(diǎn)之間的距離很大.IARA 算法中參與的中間節(jié)點(diǎn)過(guò)多,尤其是存在很多反向節(jié)點(diǎn),導(dǎo)致最終收斂路徑長(zhǎng)度較長(zhǎng)以及路徑耗能非常大.DEARA算法相比上述3 種算法收斂效果明顯改善,最優(yōu)路徑長(zhǎng)度適中,最關(guān)鍵的是相鄰節(jié)點(diǎn)距離適中,但路徑中仍然有較多中間節(jié)點(diǎn)尤其是反向的無(wú)關(guān)節(jié)點(diǎn),導(dǎo)致路徑消耗的能量?jī)H次于IARA 算法.DDEARA 算法相比上述4 種算法性能效果最好,最優(yōu)路線長(zhǎng)度短,相鄰節(jié)點(diǎn)之間距離適中,參與的中間節(jié)點(diǎn)個(gè)數(shù)合理,路徑消耗的能量也很合理.由此可見(jiàn)動(dòng)態(tài)半徑搜索因子能夠提高算法收斂能力,能量預(yù)測(cè)因子能夠減少節(jié)點(diǎn)能量消耗,方向因子能夠避免反向無(wú)關(guān)節(jié)點(diǎn)選取.

圖4 5 種對(duì)比算法最優(yōu)路徑連線圖

表1 不同算法性能對(duì)比

4.2 節(jié)點(diǎn)消耗總能量、剩余總能量

圖5對(duì)比了ARA、IARA、OARA、DEARA、DDEARA 5 種算法各個(gè)節(jié)點(diǎn)最終平均能量消耗和剩余能量情況,直觀顯示了各個(gè)節(jié)點(diǎn)能耗分布情況.

從圖5中可以看到,ARA、OARA、IARA 算法出現(xiàn)節(jié)點(diǎn)消耗能量值E2(E2>1J)、剩余能力值E1(E1<0J)的不合理現(xiàn)象,而DEARA、DDEARA 算法中節(jié)點(diǎn)消耗能量值E2(E2≤1J)、節(jié)點(diǎn)剩余能量值E1(E1≥0.1J),能量預(yù)測(cè)因子避免了節(jié)點(diǎn)能量過(guò)度消耗,不會(huì)出現(xiàn)節(jié)點(diǎn)剩余能量值為負(fù)的不合理現(xiàn)象.

圖5 5 種算法節(jié)點(diǎn)能耗

4.3 DEARA、DDEARA 算法節(jié)點(diǎn)能耗

圖6對(duì)比了DEARA、DDEARA 2 種算法各個(gè)節(jié)點(diǎn)平均能量消耗和剩余能量情況,直觀顯示了各個(gè)節(jié)點(diǎn)能耗分布情況.

圖6 DEARA、DDEARA 算法節(jié)點(diǎn)能耗

圖6顯示了在DEARA 算法中節(jié)點(diǎn)消耗能量值E2普遍在(0.8?1J)范 圍內(nèi),剩余能量值E1普遍在(0?0.2J)范圍內(nèi).在DDEARA 算法中接近2/3 的節(jié)點(diǎn)產(chǎn)生了能量消耗且能量消耗值均勻分布在(0?1J)范圍內(nèi).表明DDEARA 算法中參與的節(jié)點(diǎn)數(shù)目適中,節(jié)點(diǎn)位置分布均勻.

4.4 DEARA、DDEARA 算法每一代節(jié)點(diǎn)死亡個(gè)數(shù)

圖7對(duì)比了DEARA、DDEARA 2 種算法每一輪迭代過(guò)程中出現(xiàn)的死亡節(jié)點(diǎn)個(gè)數(shù),直觀顯示了首次出現(xiàn)死亡節(jié)點(diǎn)的迭代次數(shù),以及每一代死亡節(jié)點(diǎn)個(gè)數(shù)分布情況.

圖7 DEARA、DDEARA 算法每一代死亡節(jié)點(diǎn)個(gè)數(shù)

由圖7可知 DEARA 和DDEARA 算法都是在45 代首次出現(xiàn)了死亡節(jié)點(diǎn).DEARA 算法單次迭代死亡節(jié)點(diǎn)個(gè)數(shù)最多為8 個(gè),而DDEARA 單次迭代死亡節(jié)點(diǎn)個(gè)數(shù)最多為2 個(gè).DDEARA 算法死亡節(jié)點(diǎn)個(gè)數(shù)以及死亡節(jié)點(diǎn)出現(xiàn)的代數(shù)明顯優(yōu)于DEARA 算法.

4.5 DEARA、DDEARA 算法收斂路徑長(zhǎng)度

圖8對(duì)比了DEARA、DDEARA 算法最終收斂路徑的長(zhǎng)度,直觀顯示了兩種算法在整個(gè)迭代過(guò)程中最優(yōu)路徑的長(zhǎng)度趨勢(shì).

圖8 DEARA、DDEARA 算法收斂路徑長(zhǎng)度

圖8顯示DEARA 算法最終收斂路徑長(zhǎng)度在18.37,DDEARA 最終收斂路徑長(zhǎng)度在15.77,DDEARA 算法由于方向因子的引入,避免選取反向無(wú)關(guān)節(jié)點(diǎn),使得尋優(yōu)效果非常好,收斂路徑更短.

5 結(jié)論與展望

針對(duì)現(xiàn)有的蟻群算法無(wú)法保證路徑最終收斂,節(jié)點(diǎn)能量過(guò)度消耗,路徑上存在無(wú)關(guān)節(jié)點(diǎn)等情況.本文首先通過(guò)引入動(dòng)態(tài)半徑搜索因子和能量預(yù)測(cè)因子,提出了改進(jìn)的蟻群算法DEARA,一方面動(dòng)態(tài)半徑搜索因子能夠保證蟻群算法最終收斂并提高了蟻群算法的收斂效果.另一方面能量預(yù)測(cè)因子使得節(jié)點(diǎn)能耗均勻且不會(huì)出現(xiàn)消耗完節(jié)點(diǎn)剩余能量卻不能成功傳輸完整數(shù)據(jù)的情況.但是在DEARA 算法收斂路徑中仍然存在部分反方向的無(wú)關(guān)節(jié)點(diǎn),因此在DEARA 算法基礎(chǔ)上通過(guò)引入方向因子提出了DDEARA 算法,方向因子避免了路徑中反方向無(wú)關(guān)節(jié)點(diǎn)的選取,優(yōu)化效果非常明顯.經(jīng)過(guò)“三步遞進(jìn)式”的蟻群算法優(yōu)化,首先,使得最終的最優(yōu)路徑長(zhǎng)度較短,經(jīng)過(guò)的中間節(jié)點(diǎn)數(shù)目適中且位置分布均勻.其次,使得節(jié)點(diǎn)能耗較少,不會(huì)出現(xiàn)某區(qū)域節(jié)點(diǎn)集中死亡的現(xiàn)象.最后,使得路徑上沒(méi)有反方向的無(wú)關(guān)節(jié)點(diǎn)存在,減小路徑長(zhǎng)度,節(jié)約節(jié)點(diǎn)能耗.“三步遞進(jìn)式”蟻群算法DDEARA 尋優(yōu)能力更強(qiáng)且尋優(yōu)效果更好,提高了無(wú)線傳感器網(wǎng)絡(luò)的使用性能和壽命.

未來(lái)一方面可以著重研究“過(guò)載”節(jié)點(diǎn)能耗問(wèn)題,本文沒(méi)有考慮某個(gè)節(jié)點(diǎn)被多條路徑同時(shí)選中為下一跳節(jié)點(diǎn)的情況,這樣的“過(guò)載”節(jié)點(diǎn)由于承擔(dān)多條線路的數(shù)據(jù)傳輸任務(wù),導(dǎo)致這樣的“過(guò)載”節(jié)點(diǎn)耗能嚴(yán)重,相比其他節(jié)點(diǎn)過(guò)早成為死亡節(jié)點(diǎn),嚴(yán)重影響網(wǎng)絡(luò)使用壽命.未來(lái)應(yīng)該考慮節(jié)點(diǎn)的“負(fù)重”系數(shù),嚴(yán)格限制節(jié)點(diǎn)同時(shí)被多條路徑經(jīng)過(guò).另一方面可以考慮路徑中一旦出現(xiàn)死亡節(jié)點(diǎn)之后,怎么樣快速尋找其他節(jié)點(diǎn)代替死亡節(jié)點(diǎn),恢復(fù)正常工作.