改進(jìn)的蟻群算法在無線傳感器網(wǎng)絡(luò)中的應(yīng)用

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

一、 蟻群算法的改進(jìn)

（一） 基本蟻群算法

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

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

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

信息素更新的公式是：

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

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

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

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

其中Q 為常量，Lk為第k個(gè)螞蟻周游的路徑長(zhǎng)度。

（二） 改進(jìn)的蟻群算法

1、群體行為多樣性策略

我們?cè)诨镜南伻核惴ㄖ幸肓巳后w行為多樣性，群體中的每個(gè)螞蟻選路的概率函數(shù)p中的參數(shù)α、β值并非完全相同，而且還將在算法每輪循環(huán)執(zhí)行后不斷變化。在這種算法中螞蟻的行為策略是多樣性的。

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

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

我們?cè)谒惴ㄖ幸晕墨I(xiàn)[2]提出的算法HBACA模型為基礎(chǔ)，在算法中定義了四種行為模式：

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

（2） 按公式（1）進(jìn)行選路。

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

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

HSIV算法可描述如下：

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

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

步驟3：for 每個(gè)螞蟻k

Repeat

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

Until 禁忌表滿 ； End for

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

更新當(dāng)前最短路徑Lmin；

步驟5：

將當(dāng)前最短路徑上的每條邊上的信息素按公式（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<預(yù)定迭代次數(shù)）and（無退化行為）then 清空禁忌表，回到步驟3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、改進(jìn)的蟻群算法在無線傳感器網(wǎng)絡(luò)中的應(yīng)用

（一） 算法的基本思路

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

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

1、初始化過程

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

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

2、初始化網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)鋱D；

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

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

5、計(jì)算每個(gè)螞蟻的路徑長(zhǎng)度，將最優(yōu)解存儲(chǔ)到全局變量中。

6、對(duì)每個(gè)螞蟻更新信息素。

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

四、結(jié)論

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

參考文獻(xiàn)：

[1]周春光，梁艷春.計(jì)算智能.吉林大學(xué)出版社，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.

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

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