改進的蟻群算法在無線傳感器網(wǎng)絡中的應用

無線傳感器網(wǎng)絡WSN是由許多傳感器節(jié)點協(xié)同組織起來的，具有無線通信、數(shù)據(jù)采集和處理、協(xié)同合作等功能的網(wǎng)絡系統(tǒng)。它的節(jié)點可以隨機或者特定地布置在目標環(huán)境中，它們之間通過特定的協(xié)議自組織起來，能夠獲取周圍環(huán)境的信息并且相互協(xié)同工作完成特定任務。蟻群算法在求解復雜優(yōu)化問題方面具有一定的優(yōu)勢，本文首先對基本蟻群算法進行了改進。仿照自然界種群中個體的多樣性，在蟻群優(yōu)化算法中引入了群體多樣性選路策略。使ACO算法的全局搜索能力和收斂速度得到了增強，可提高解的質(zhì)量。根據(jù)無線傳感器網(wǎng)絡所具有能量受限、網(wǎng)絡節(jié)點不斷變化的特性，利用蟻群算法在無線傳感器網(wǎng)絡動態(tài)路由中求解最佳路徑。

一、 蟻群算法的改進

（一） 基本蟻群算法

基本蟻群算法可以簡單表述如下：初始化，將m個螞蟻隨機放在n個城市上，城市間的每一條邊都有初始化信息素，每個螞蟻的禁忌表Tabu（k）的第一個元素設置為其初始城市。然后每只螞蟻開始選路，即選擇下一步要去的城市。在選路中螞蟻依據(jù)概率函數(shù)選擇將要去的城市，這個概率取決于城市間的距離和信息素的強度。在選路中螞蟻依據(jù)概率函數(shù)

p■■=■0， 其它 j?綴allowed■ （1）

選擇將要去的城市，這個概率取決于城市間的距離和信息素的強度。其中?子■t表示邊?。╥，j）上信息素的強度（i為出發(fā)城市，j為到達城市）；?濁■表示城市間距離因子，通常取值為1/dij（dij為兩個城市間的距離）；α表示信息素在選擇概率上的作用；β是指路徑長度在選擇概率上的作用。在n次循環(huán)后，所有螞蟻的禁忌表都已填滿，此時計算每個螞蟻走過的路徑的長度，并找到最短路徑保存，記錄此路徑并更改信息素。重復這一過程直至達到最大周游值結(jié)束。

信息素更新的公式是：

?子ij（t+n）=ρ?子ij（t）+?葒?子ij .（2）

?葒?子ij=■ ?葒?子■■（3）

其中?葒?子ij表示在某條邊上的累加新增信息素的和，ρ表示信息素消散的等級，?葒?子■■表示t和t+n之間第k個螞蟻在此邊上留下的信息素的數(shù)量。?葒?子■■的計算公式為：

?葒?子■■= ■，如果在t和t+n之間第k個螞蟻使用此邊0，其它 （4）

其中Q 為常量，Lk為第k個螞蟻周游的路徑長度。

（二） 改進的蟻群算法

1、群體行為多樣性策略

我們在基本的蟻群算法中引入了群體行為多樣性，群體中的每個螞蟻選路的概率函數(shù)p中的參數(shù)α、β值并非完全相同，而且還將在算法每輪循環(huán)執(zhí)行后不斷變化。在這種算法中螞蟻的行為策略是多樣性的。

我們將改進的蟻群算法叫做HSIV算法。在此算法的每輪循環(huán)中，修改得到最優(yōu)解的螞蟻的α、β參數(shù)，漸進加重信息素在選路的概率函數(shù)p中的作用，相應減小距離在選路的概率函數(shù)p中的作用，我們稱這種方法為獎勵機制，同時修改得到最差解得的。這種機制可以在蟻群中實現(xiàn)不同選路策略的螞蟻協(xié)同工作。

2、群體多樣性算法HSIV算法實現(xiàn)

我們在算法中以文獻[2]提出的算法HBACA模型為基礎，在算法中定義了四種行為模式：

（1） 使公式（1）中的參數(shù)α為0，參數(shù)β為0。

（2） 按公式（1）進行選路。

（3） 按個體差異策略進行選路，提高α的值，增大信息素在選路中的作用；同時降低β的值，減小距離因子在選路中的作用。

將四種策略按0.05：0.1：0.4：0.45的比例來設置蟻群的行為策略，算法的性能最好。

HSIV算法可描述如下：

步驟1：初始化各參數(shù);

步驟2：將m個螞蟻按照不同行為策略隨機放到n個城市

步驟3：for 每個螞蟻k

Repeat

按選路策略選擇下個城市；將螞蟻k所在的城市放到螞蟻k的禁忌表

Until 禁忌表滿 ； End for

步驟4：選擇走過路徑最短的螞蟻min； 根據(jù)禁忌表計算螞蟻min 的路徑長度Lk；

更新當前最短路徑Lmin；

步驟5：

將當前最短路徑上的每條邊上的信息素按公式（3）更新?葒?子i

if (ANT[min].alpha>=5)ANT[min].alpha：= ANT[min].alpha+5；

elseANT[min].alpha:=5；ANT[min].beta：=1；

步驟6：

if（NC<預定迭代次數(shù)）and（無退化行為）then 清空禁忌表，回到步驟3

else 打印最短路徑 ；算法結(jié)束

二、無線傳感器網(wǎng)絡

（一）無線傳感器網(wǎng)絡的概念

無線傳感器網(wǎng)絡由多個功能相同或不同的無線傳感器節(jié)點組成，每個節(jié)點在網(wǎng)絡中可以充當數(shù)據(jù)采集者、數(shù)據(jù)中轉(zhuǎn)站或類頭節(jié)點。作為數(shù)據(jù)采集者，節(jié)點可以收集周圍環(huán)境的數(shù)據(jù)，通過通信路由協(xié)議直接或間接將數(shù)據(jù)傳輸給基站或網(wǎng)關節(jié)點；作為數(shù)據(jù)中轉(zhuǎn)站，節(jié)點除了完成采集任務外，還要接收鄰居節(jié)點的數(shù)據(jù)，將其轉(zhuǎn)發(fā)給距離基站更近的鄰居節(jié)點或者直接轉(zhuǎn)發(fā)到基站或網(wǎng)關節(jié)點；作為類頭節(jié)點，節(jié)點負責收集該類內(nèi)所有節(jié)點采集的數(shù)據(jù)。

（二）無線傳感器網(wǎng)絡的相關數(shù)據(jù)計算

在傳感網(wǎng)絡中，稱兩個節(jié)點是相鄰的，當且僅當此兩個節(jié)點在彼此有效通信距離之內(nèi)。假定相鄰節(jié)點之間只存在一條鏈路，則傳感網(wǎng)絡的拓撲結(jié)構(gòu)可以看作是一個無向圖G=（V，E），其中V為所有傳感節(jié)點構(gòu)成的頂點集合，E為所有鏈路構(gòu)成的邊集合。由傳感網(wǎng)絡節(jié)點部署的稠密性，本文假定圖G是連通的。

定義1 （相鄰節(jié)點）：設節(jié)點w和節(jié)點u在彼此有效通信距離之內(nèi)。稱為相鄰節(jié)點，簡稱相鄰。

定義2（物理距離）：設節(jié)點w 和節(jié)點u相鄰，則w到u的實際距離，稱為w和u的物理距離，表示為：L。其中w（x，y）是w的坐標，u（x，y）是u的坐標。L=sqrt（（w.x-u.x）2+（w.y-u.y）2）

定義3（臨界電壓）使傳感器能夠正常工作的最小電壓值稱為臨界電壓。

定義4（通信距離）：設節(jié)點w和節(jié)點u相鄰，稱WL為w和u的通信距離。WL=K?觹（L）2

其中，K為比例系數(shù)，K=1/（V0-Vmin），其中V0是傳感器當前工作電壓值，Vmin是臨界電壓且Vmin是常量。公式WL=K*（L）2考慮到節(jié)點間傳播信息所消耗的能量與節(jié)點間距離的平方成正比例，并且考慮了K值的收斂速度。

1、每節(jié)點物理位置坐標：可以人為設置或由全球定位系統(tǒng)（GPS）獲得。

2、物理距離：設有兩個節(jié)點w，u 是相鄰節(jié)點。w（x，y）是w 的坐標，u（x，y）是u 的坐標。L=sqrt（（w.x-u.x）2+（w.y-u.y）2）。

3、V0：V0是傳感器節(jié)點的當前工作電壓值（初始化時為3V）。當系統(tǒng)運行時，V0是由無線傳感器節(jié)點定時向匯節(jié)點發(fā)送自身的電壓值。

4、Vmin：Vmin是臨界電壓值（初始化時為2.7V）。

5、通信距離：WL= K*（L）2，K=1/（V0-Vmin）。

三、改進的蟻群算法在無線傳感器網(wǎng)絡中的應用

（一） 算法的基本思路

（1）通過一組“螞蟻”人工代理遍歷網(wǎng)絡節(jié)點來產(chǎn)生Sink節(jié)點到達目標節(jié)點的最優(yōu)路徑；（2）通過螞蟻的局部搜索以遞增的方式來建立路徑；（3）使用試探獲得的信息來指導各個螞蟻的搜索，使各路徑趨于匯合，最終達到數(shù)據(jù)匯集的目的。（4）算法不需要網(wǎng)絡中各傳感節(jié)點維護全局網(wǎng)絡狀態(tài)；（5）螞蟻不必遍歷節(jié)點拓撲圖中的所有節(jié)點。因而具備更好的可伸縮性。測試結(jié)果也表明新路由算法具有較好的路由性能。

（二）算法實現(xiàn)

1、初始化過程

Q=200；α=1；β=4；ρ=0.5；iAntCount=20；

iMoteCount=30；iItCount=500；將m只螞蟻置于起始節(jié)點。

2、初始化網(wǎng)絡節(jié)點拓撲圖；

3、循環(huán)開始并設置最大循環(huán)次數(shù)。

4、所有螞蟻依次遍歷網(wǎng)絡節(jié)點；

5、計算每個螞蟻的路徑長度，將最優(yōu)解存儲到全局變量中。

6、對每個螞蟻更新信息素。

7、重復3，直到輸出結(jié)果。

四、結(jié)論

不同的參數(shù)對最優(yōu)解和循環(huán)次數(shù)有著不同的影響。算法中對螞蟻個數(shù)要求有較寬松的范圍，取節(jié)點的個數(shù)即可。參數(shù)α對循環(huán)次數(shù)不敏感，對解路徑的長度影響較大。參數(shù)β和Q正相反，對解路徑影響不大，但是對循環(huán)次數(shù)反應較為靈敏。因此在傳感器網(wǎng)絡的路由問題中應該著重留意。對于無線傳感器網(wǎng)絡中的路由問題，蟻群算法可以在較少的循環(huán)之內(nèi)取得比較滿意的最優(yōu)解或次優(yōu)解。由于改進的蟻群算法不要求螞蟻必須遍歷所有的網(wǎng)絡節(jié)點便可以找到最優(yōu)或次優(yōu)解，而且收斂速度較快，當數(shù)據(jù)采集區(qū)域內(nèi)分布著較多的節(jié)點時，可以較好地適應實時的數(shù)據(jù)傳輸要求。

參考文獻：

[1]周春光，梁艷春.計算智能.吉林大學出版社，2001.

[2]胡小兵，黃席樾.基于混合行為蟻群算法的研究[J].控制與決策，2004.

[3] Dorige M，Maniezzo V，Colorni A. Ant system： Optimization by a colony of cooperating agents.IEEE Trans. on SMC. 1996.

（作者簡介：趙艷偉（1968-），女，漢族，吉林長春人，副教授，碩士學歷，吉林工商學院信息工程分院，研究方向：算法及其應用。）

注：本文是吉林省教育廳“十一五”科學技術(shù)研究項目，項目名稱：改進的蟻群算法在優(yōu)化問題上的應用，項目編號：吉教科合字[2008]第411號。