改進的蟻群算法在無線傳感器網絡中的應用

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

一、 蟻群算法的改進

（一） 基本蟻群算法

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

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

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

信息素更新的公式是：

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

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

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

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

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

（二） 改進的蟻群算法

1、群體行為多樣性策略

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

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

2、群體多樣性算法HSIV算法實現

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

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

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

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

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

HSIV算法可描述如下：

步驟1：初始化各參數;

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

步驟3：for 每個螞蟻k

Repeat

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

Until 禁忌表滿 ； End for

步驟4：選擇走過路徑最短的螞蟻min； 根據禁忌表計算螞蟻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<預定迭代次數）and（無退化行為）then 清空禁忌表，回到步驟3

else 打印最短路徑 ；算法結束

二、無線傳感器網絡

（一）無線傳感器網絡的概念

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

（二）無線傳感器網絡的相關數據計算

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

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

定義2（物理距離）：設節點w 和節點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（通信距離）：設節點w和節點u相鄰，稱WL為w和u的通信距離。WL=K?觹（L）2

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

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

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

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

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

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

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

（一） 算法的基本思路

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

（二）算法實現

1、初始化過程

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

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

2、初始化網絡節點拓撲圖；

3、循環開始并設置最大循環次數。

4、所有螞蟻依次遍歷網絡節點；

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

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

7、重復3，直到輸出結果。

四、結論

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

參考文獻：

[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-），女，漢族，吉林長春人，副教授，碩士學歷，吉林工商學院信息工程分院，研究方向：算法及其應用。）

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