基于混沌蟻群的WSN移動(dòng)代理路由算法

李方宇，葛 斌，張 巖

(1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001；2.阜陽(yáng)師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，安徽 阜陽(yáng) 236037)

無(wú)線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）是以傳感器為基礎(chǔ)，以無(wú)線通信方式達(dá)到范圍內(nèi)信息共享的應(yīng)用網(wǎng)絡(luò)，常用于地質(zhì)勘測(cè)、軍事偵察等領(lǐng)域[1-2]。但該網(wǎng)絡(luò)受其固定能量的限制，生命周期有限。因此，如何設(shè)計(jì)一種兼顧能量和傳輸效率的路由算法是該領(lǐng)域當(dāng)前的研究重點(diǎn)。

相比傳統(tǒng)無(wú)線傳感器網(wǎng)絡(luò)的C/S（客戶端/服務(wù)器）計(jì)算模型，移動(dòng)代理（mobile agent，MA）更具節(jié)能型、自主性等優(yōu)勢(shì)[3-4]。匯聚節(jié)點(diǎn)派遣MA按照某種算法規(guī)則在不同的節(jié)點(diǎn)間遷移，當(dāng)完成特定節(jié)點(diǎn)的數(shù)據(jù)融合后再返回。因此，MA路由路徑的質(zhì)量將直接影響網(wǎng)絡(luò)性能。蟻群優(yōu)化算法ACO(ant colony optimization)[5-8]雖將MA路徑規(guī)劃有效地轉(zhuǎn)化為求解TSP(traveling salesman problem)問(wèn)題，但受算法本身的易陷入局部最優(yōu)解等特點(diǎn)影響，MA路徑質(zhì)量不佳。文獻(xiàn)[9-12]基于混沌粒子群思想進(jìn)行優(yōu)化，但未涉及MA路徑中失效節(jié)點(diǎn)的替換策略，產(chǎn)生了因MA重新尋點(diǎn)成路的消耗。文獻(xiàn)[13]基于混沌算子，雖解決局部最優(yōu)解問(wèn)題，但其執(zhí)行速度較慢。

針對(duì)上述問(wèn)題，本文在基于混沌算子所產(chǎn)生的種群多樣性和改進(jìn)蟻群的遍歷性等特點(diǎn)的基礎(chǔ)上，結(jié)合兼顧能耗、距離與時(shí)延為目標(biāo)的遷移因子計(jì)算MA每次遷移的節(jié)點(diǎn)位置。同時(shí)，設(shè)計(jì)自適應(yīng)擾動(dòng)策略對(duì)失效節(jié)點(diǎn)進(jìn)行替換，避免MA多次迭代。該方法增加了MA的自主性，即提高其搜索能力且減少陷入局部最優(yōu)解的概率，提升MA路徑質(zhì)量，從而延長(zhǎng)網(wǎng)絡(luò)生命周期。

1 相關(guān)工作

1.1 蟻群算法

蟻群算法ACO由Dorigo等[14]提出，其核心思想是以螞蟻覓食行為產(chǎn)生的信息素為正反饋因子，即當(dāng)某條路徑上累計(jì)的信息素越高，其他螞蟻選擇該路徑的概率越大，從而最終形成整個(gè)螞蟻種群的覓食路徑。

在狀態(tài)轉(zhuǎn)移過(guò)程中，假設(shè)網(wǎng)絡(luò)中存在n個(gè)傳感器節(jié)點(diǎn)與m只螞蟻，則螞蟻m從節(jié)點(diǎn)i向節(jié)點(diǎn)j的遷移概率：

其中:τij(t)和ηij(t)分別為時(shí)t內(nèi)節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的信息素濃度值、距離倒數(shù)函數(shù)；α和β依次為前兩者的啟發(fā)因子；Allowedm={I-Tabum}為螞蟻m的候選解集，I為所有節(jié)點(diǎn)集，Tabum表示螞蟻m已遍歷的節(jié)點(diǎn)集合；s為螞蟻m在此次遷移中的候選解。α值越大，螞蟻越易選取信息素高的路徑；β值越大，螞蟻越易選取離終點(diǎn)近的節(jié)點(diǎn)。

當(dāng)螞蟻m完成狀態(tài)轉(zhuǎn)移后，則進(jìn)行局部信息素更新：

其中：λ為局部殘留信息素因子：τ0為當(dāng)前路徑信息素初始值。

當(dāng)螞蟻群完成一次迭代后，對(duì)此次迭代中路徑最短者進(jìn)行全局信息素更新：

其中：ρ為全局殘留信息素因子；Δτij為判定因子。

1.2 混沌蟻群優(yōu)化模型

本文引入動(dòng)態(tài)混沌算子，將其作為螞蟻信息素的更新權(quán)重，解決ACO算法中在算法初始化時(shí)因螞蟻隨機(jī)選擇等量信息素濃度路徑而造成的收斂速度過(guò)慢現(xiàn)象，混沌蟻群算法避免了局部最優(yōu)解，增強(qiáng)解的精度。

1.2.1 混沌搜索

混沌搜索是一種發(fā)生在確定性非線性系統(tǒng)中的有界動(dòng)態(tài)行為[15]。該方法可以確?；煦缱兞吭谝欢ǚ秶鷥?nèi)不重復(fù)地遍歷所有狀態(tài)，從而避免算法陷入局部最優(yōu)解。故而在算法的迭代過(guò)程中縮短路徑長(zhǎng)度，且能提高種群的多樣性。

本文針對(duì)Logistic與Tent兩種混沌映射進(jìn)行對(duì)比，其迭代公式分別為：

其中：Zn、Un分別為第n次的混沌映射變量；μ為控制參數(shù)。

設(shè)定兩種混沌映射的迭代次數(shù)為5 000，其混沌變量分布對(duì)比如圖1。其中，Logistic混沌映射產(chǎn)生的變量分布不均，且在區(qū)間[38，55]內(nèi)的變量數(shù)量遠(yuǎn)遠(yuǎn)多于其他區(qū)域。而Tent混沌映射的變量分布較為均勻，變量差異性較低。根據(jù)文獻(xiàn)[16]可知混沌遍歷性與混沌軌道條數(shù)呈正比關(guān)系。故本文采用遍歷性較為均衡的Tent混沌映射作為混沌變量發(fā)生器，并使用多條混沌軌道進(jìn)行混沌搜索。

圖1 不同混沌映射下的混沌變量對(duì)比

1.2.2 動(dòng)態(tài)混沌算子

動(dòng)態(tài)混沌算子的引入是基于ACO中收斂速度慢、易陷入局部最優(yōu)解等問(wèn)題[17]。該算子在迭代前期調(diào)整路徑信息素值以增加蟻群的多樣性，在迭代后期消除混沌擾動(dòng)以提高算法收斂速度。

全局信息素更新公式(3)修改為

其中：Uij為混沌變量，且由Tent混沌映射式(5)迭代得出，σ為適應(yīng)參數(shù)，即調(diào)整混沌算子與全局信息素的均衡，T為算法當(dāng)前迭代次數(shù)，T0為迭代次數(shù)閾值，其仿真結(jié)果如表1，當(dāng)T0為20時(shí)，該系統(tǒng)所求解集較優(yōu)。

表1 不同迭代閾值T的解集對(duì)比

2 算法實(shí)現(xiàn)

2.1 MA遷移模型

其中：ηij(t)、Eij(t)、Dij(t)分別為時(shí)刻t的節(jié)點(diǎn)i到節(jié)點(diǎn)j傳輸能量、剩余能量、參照距離的啟發(fā)式信息；β、γ、v依次對(duì)應(yīng)三者的重要程度；和為偏向權(quán)重參數(shù)，且。

能量消耗與距離呈正比關(guān)系。結(jié)合文獻(xiàn)[12]所提出的能量消耗模型，修改節(jié)點(diǎn)能量消耗的信息素釋放量：

其中：λ1、λ2為偏量參數(shù)，且λ1+λ2=1；T是螞蟻所留軌跡數(shù)量的長(zhǎng)度；Lk是第k只螞蟻上次遍歷的總長(zhǎng)度。

考慮到網(wǎng)絡(luò)時(shí)延等因素，在移動(dòng)概率模型中引入Dij作為節(jié)點(diǎn)i到節(jié)點(diǎn)j的參照距離：

其中：ψ為時(shí)延系數(shù)，且滿足ξ∈(dmin/d0,dmax/d0)；dmin、dmax分別為最小與最大傳輸距離；do為傳輸距離閾值；Einit為節(jié)點(diǎn)初始能量。在節(jié)點(diǎn)未因能量耗盡死亡前，ψ以時(shí)延要求進(jìn)行動(dòng)態(tài)調(diào)整：若傳輸任務(wù)對(duì)時(shí)延要求較高，則參照距離增大；相反地，參照距離的縮短可通過(guò)多跳方式進(jìn)行調(diào)整。

由式(7)～(9)可知：節(jié)點(diǎn)在選擇下一跳節(jié)點(diǎn)時(shí)，須綜合節(jié)點(diǎn)間距離和下一跳節(jié)點(diǎn)的剩余能量，避免節(jié)點(diǎn)間最短距離下的剩余能量不足，從而無(wú)法保證MA的下一次移動(dòng)。同時(shí)，結(jié)合傳輸任務(wù)對(duì)網(wǎng)絡(luò)時(shí)延的要求，在移動(dòng)過(guò)程中兼顧時(shí)延。

2.2 自適應(yīng)擾動(dòng)策略

螞蟻的行為軌跡更新主要依據(jù)其鄰居螞蟻產(chǎn)生的信息素濃度，經(jīng)過(guò)一定的迭代次數(shù)，整個(gè)螞蟻群將會(huì)收斂至其搜索空間中的最優(yōu)解集中。但是鑒于傳統(tǒng)ACO算法就未設(shè)定全局最優(yōu)位置相關(guān)參數(shù)，所以可能導(dǎo)致螞蟻找到新的位置與最優(yōu)解存在一定距離而被遺棄。為解決因節(jié)點(diǎn)失效而造成的MA重新迭代，本文引入自適應(yīng)擾動(dòng)策略，在原有基礎(chǔ)上進(jìn)一步就維護(hù)現(xiàn)有MA最優(yōu)路徑，及時(shí)替換失效節(jié)點(diǎn)，延長(zhǎng)MA最優(yōu)路徑生存周期。

厄瓜多爾科卡科多辛克雷電站是我國(guó)在海外建成投產(chǎn)的最大水電站，該電站8臺(tái)18.75萬(wàn)千瓦高水頭沖擊式機(jī)組全部由哈電電機(jī)制造。在歷時(shí)近6年的建設(shè)中，哈電電機(jī)克服了無(wú)數(shù)技術(shù)、安裝難關(guān)，還經(jīng)歷了一次強(qiáng)震的考驗(yàn)。2016年11月，國(guó)家領(lǐng)導(dǎo)人與厄瓜多爾總統(tǒng)出席辛克雷電站投產(chǎn)發(fā)電儀式，共同按動(dòng)按鈕，8臺(tái)高水頭沖擊式機(jī)組全部投產(chǎn)發(fā)電，成為國(guó)家實(shí)施“走出去”戰(zhàn)略的成功典范。

根據(jù)式(7)中的MA遷移生成模型，在算法的搜索結(jié)尾階段，螞蟻群已臨近或搜索到全局最優(yōu)解節(jié)點(diǎn)集，那么必然存在全局最優(yōu)解在其信息素濃度最高路徑邊緣的可能性。當(dāng)Sink節(jié)點(diǎn)判定此時(shí)的全局最優(yōu)路徑中存在失效節(jié)點(diǎn)時(shí)，所以對(duì)結(jié)尾階段中搜索得出且具有較優(yōu)的節(jié)點(diǎn)進(jìn)行擾動(dòng)處理,自適應(yīng)擾動(dòng)函數(shù)如下:

其中：Δxj為xj的修正位置；εj∈(-ξj,ξj)為節(jié)點(diǎn)j的此次修正值；

特別地，當(dāng)MA需要進(jìn)行數(shù)據(jù)量較大的遷移時(shí)，此時(shí)的最優(yōu)路徑中都滿足全局最優(yōu)解，達(dá)到了路由路徑長(zhǎng)度和能量均衡的較理想狀態(tài)。

2.3 MA路徑評(píng)估函數(shù)

由2.1節(jié)可知，MA移動(dòng)概率模型的應(yīng)用背景為多目標(biāo)優(yōu)化問(wèn)題，本文采用線性加權(quán)思想，將該類(lèi)問(wèn)題主體轉(zhuǎn)化為多個(gè)單個(gè)目標(biāo)，通過(guò)設(shè)置節(jié)點(diǎn)能耗與移動(dòng)路徑長(zhǎng)度兩種權(quán)重因子，直觀顯示數(shù)據(jù)趨勢(shì)并取得一種較為平衡的MA路徑評(píng)估函數(shù)

其中：k1、k2為加權(quán)因子；Li為第i輪MA移動(dòng)路徑總長(zhǎng)度；ELi-total、ELi-max和ELi-min依次為L(zhǎng)i中節(jié)點(diǎn)的總能量、剩余能量最大值和最小值；D(Li)avg為L(zhǎng)i中節(jié)點(diǎn)的能量方差。

由式(12)可知，f(i)與路徑情況呈負(fù)相關(guān)聯(lián)系。f(i)越小表示第i次MA移動(dòng)路徑長(zhǎng)度越短，節(jié)點(diǎn)能耗綜合越少。同時(shí)，第i次MA移動(dòng)路徑中節(jié)點(diǎn)能量方差越小，節(jié)點(diǎn)的能耗也較為均衡。

2.4 MACAC算法流程

步驟1 假設(shè)Sink節(jié)點(diǎn)與一個(gè)包含c個(gè)目標(biāo)節(jié)點(diǎn)的集合N={Ni|i=1,2,…,c}存在映射關(guān)系，由Sink節(jié)點(diǎn)派遣移動(dòng)代理節(jié)點(diǎn)MA完成第次數(shù)據(jù)融合的遷移行為，且重置該移動(dòng)代理節(jié)點(diǎn)的禁忌表Tabuk={c-Nk|k=1,2,…,m}。

步驟2 MA根據(jù)式(7)得出遷移目的節(jié)點(diǎn)Ni的位置并記錄。

步驟3 如果MA的禁忌表Tabuk中不存在節(jié)點(diǎn)Ni的相關(guān)數(shù)據(jù)，將其添加至禁忌表Tabuk中，并在根據(jù)式(2)進(jìn)行局部信息素的更新后遷移至該節(jié)點(diǎn)；相反地，MA重復(fù)步驟2，直至計(jì)算出不為T(mén)abuk子集的節(jié)點(diǎn)作為其下一跳遷移位置。

步驟4 當(dāng)集合N為空時(shí)，即MA已遍歷所有目標(biāo)節(jié)點(diǎn)后返回Sink節(jié)點(diǎn)。MA將第k次遷移路徑數(shù)據(jù)及代價(jià)匯總給Sink節(jié)點(diǎn)。如果集合N非空則重復(fù)步驟2。

步驟5 當(dāng)派出m個(gè)MA之后，記錄其MA路徑評(píng)估函數(shù)值最小的路徑，并根據(jù)式(6)進(jìn)行全局信息素的更新。

步驟6 重復(fù)上述n次的算法迭代，選擇條路徑中評(píng)估函數(shù)值最小者作為最優(yōu)路徑。如果該路徑中存在節(jié)點(diǎn)失效等情況，則根據(jù)自適應(yīng)擾動(dòng)策略進(jìn)行替換，達(dá)到延長(zhǎng)MA最優(yōu)路徑可用性的目的，即延長(zhǎng)網(wǎng)絡(luò)生命周期。

3 仿真與分析

為證明本文所提出的基于混沌蟻群的自適應(yīng)MA路由優(yōu)化算法MACAC(mobile agent of chaotic ant colony)的有效性，選取以下三類(lèi)基于不同算法的MA路由算法進(jìn)行對(duì)比，依次為基于傳統(tǒng)蟻群系統(tǒng)(ACO)[18]、基于精英蟻群算法基于精英蟻群算法(elite ant colony，EAS)[19]和蟻群優(yōu)化混合算法(multi-ant routing，MAR)[20]。

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

本文運(yùn)用Matlab R2012a平臺(tái)進(jìn)行仿真，實(shí)驗(yàn)參數(shù)見(jiàn)表2。

表2 仿真實(shí)驗(yàn)參數(shù)

3.2 實(shí)驗(yàn)結(jié)果分析

為減少參照距離對(duì)MA遷移模型的影響，本文對(duì)其不同時(shí)延系數(shù)下的能耗與路徑長(zhǎng)度的實(shí)驗(yàn)結(jié)果進(jìn)行分析，如圖2。

圖2 不同時(shí)延系數(shù)下MA路徑長(zhǎng)度與能耗對(duì)比

可以看出，ψ分別與MA遷移路徑長(zhǎng)度和能耗近似呈反比和正比的關(guān)系。當(dāng)ψ=1.7時(shí)，數(shù)據(jù)傳輸需求急迫，節(jié)點(diǎn)往往以最大傳輸距離dmax進(jìn)行傳輸，參照距離增大，導(dǎo)致節(jié)點(diǎn)間通信能耗增大。當(dāng)ψ=0.1時(shí)，數(shù)據(jù)傳輸需求較低，節(jié)點(diǎn)間采用短路徑多跳方式，雖減少因通信距離過(guò)長(zhǎng)而產(chǎn)生的能量消耗，但增加了因多跳傳輸產(chǎn)生的路徑長(zhǎng)度。同時(shí)，為減少參數(shù)差異性，本文設(shè)定ψ=0.9，均衡能耗與MA遷移路徑長(zhǎng)度的變量差異因此。另，ψ作為MA遷移模型中的平衡判定因子，應(yīng)用于不同時(shí)延要求的網(wǎng)絡(luò)中，從而增強(qiáng)網(wǎng)絡(luò)可用性。

如圖3，本文選取一次MA最優(yōu)路徑作為基準(zhǔn)，以驗(yàn)證2.2節(jié)中自適應(yīng)擾動(dòng)策略的有效性，其中失效節(jié)點(diǎn)與替代節(jié)點(diǎn)依次用藍(lán)色方形與紅點(diǎn)表示。MA原最優(yōu)路徑為圖3中所示藍(lán)色實(shí)線，但因節(jié)點(diǎn)53、91和95失效，MA在遷移至該類(lèi)節(jié)點(diǎn)前進(jìn)行自適應(yīng)擾動(dòng)處理，可得出失效節(jié)點(diǎn)的替代節(jié)點(diǎn)，如：節(jié)點(diǎn)1、4、78和79。相應(yīng)地，由替代節(jié)點(diǎn)與正常節(jié)點(diǎn)構(gòu)成的MA新最優(yōu)路徑(替代部分由虛線組成)既可保留原有路徑內(nèi)相關(guān)信息，又能有效減少網(wǎng)絡(luò)派遣MA重新遍歷的次數(shù)及能量消耗。對(duì)比ACO和EAS，這兩類(lèi)算法未提出相關(guān)因節(jié)點(diǎn)失效的處理措施，若最優(yōu)路徑上存在失效節(jié)點(diǎn)，MA只能進(jìn)行下一次遍歷，增加了網(wǎng)絡(luò)負(fù)擔(dān)。而MAR算法雖在ACO的基礎(chǔ)上提出失效節(jié)點(diǎn)轉(zhuǎn)移策略，但由于ACO算法本身的缺陷，使得MA尋找的下一跳節(jié)點(diǎn)易陷入局部最優(yōu)解，導(dǎo)致MA最優(yōu)路徑中節(jié)點(diǎn)整體質(zhì)量不高。

圖3 自適應(yīng)擾動(dòng)策略前后對(duì)比

為分析不同算法間的性能差異性，本文設(shè)定算法每輪的最大迭代次數(shù)為200，分別進(jìn)行50輪，且以平均值的形式分別進(jìn)行對(duì)比，具體如表3。

MA最優(yōu)路徑長(zhǎng)度。本算法優(yōu)勢(shì)較為明顯，對(duì)于其他三種算法分別減少了59.558 4、35.193 8和11.868 2 m。其中，ACO與EAS算法均未涉及混沌算子概念，在算法執(zhí)行初期，兩者陷入局部最優(yōu)解的次數(shù)較多，導(dǎo)致MA最優(yōu)路徑中解的質(zhì)量不佳，所以整體長(zhǎng)度較長(zhǎng)；而由于MAR算法引入了節(jié)點(diǎn)替換策略，所以將本輪中MA最佳路徑中的失效節(jié)點(diǎn)進(jìn)行替換，有效的減少了其路徑長(zhǎng)度。

表3 不同算法的多性能對(duì)比

能耗。對(duì)比ACO與EAS算法，MAR與本算法能耗差異較小，差值為2.339 3 J。由于MAR算法對(duì)失效節(jié)點(diǎn)的及時(shí)替換，減少了因進(jìn)行MA的重新遍歷產(chǎn)生的能量消耗。而ACO與EAS算法中以螞蟻的信息素濃度作為螞蟻運(yùn)動(dòng)的主要依據(jù)，且易受局部最優(yōu)解的干擾，故該類(lèi)算法的能耗差值較大。

耗時(shí)。對(duì)比ACO與EAS算法，本算法的耗時(shí)約為前兩者的2倍，由于MA遷移模型中需要計(jì)算三個(gè)螞蟻種群多樣性指標(biāo)，較前兩者增加二種。同時(shí)，自適應(yīng)擾動(dòng)策略中需要對(duì)本次迭代中的次優(yōu)節(jié)點(diǎn)集進(jìn)行記錄，故節(jié)點(diǎn)替換時(shí)需耗費(fèi)一定查詢(xún)時(shí)間。對(duì)于MAR算法，由于本算法引入了混沌變量，導(dǎo)致產(chǎn)生了算法前期的混沌過(guò)程耗時(shí)，但同于MAR算法的是兩者都需要進(jìn)行失效節(jié)點(diǎn)的替換，以時(shí)間換取MA路徑中解集的精度。

4 小結(jié)

本文基于蟻群系統(tǒng)中信息素的正反饋思想，引入動(dòng)態(tài)混沌算子增強(qiáng)其搜索能力，并針對(duì)移動(dòng)代理問(wèn)題所提出的MA遷移模型，從MA路徑評(píng)估函數(shù)和自適應(yīng)擾動(dòng)策略等手段進(jìn)行求解與優(yōu)化，并構(gòu)建路由路徑。在相同的實(shí)驗(yàn)環(huán)境下，依次與ACO、EAS和MAR進(jìn)行網(wǎng)絡(luò)能耗與MA遷移路徑長(zhǎng)度等方面的比較。實(shí)驗(yàn)結(jié)果表明本算法在需要兼顧能耗和MA遷移路徑長(zhǎng)度的無(wú)線傳感器網(wǎng)絡(luò)中能夠有效優(yōu)化路徑長(zhǎng)度且有效減少網(wǎng)絡(luò)能耗，相比于同類(lèi)蟻群算法與混沌蟻群算法更好的實(shí)現(xiàn)了自適應(yīng)路由，從而延長(zhǎng)網(wǎng)絡(luò)生存周期。