邢 鋒 ， 顧 燕 ， 王 超 ， 許小飛

（河海大學(xué) a. 計算機及信息工程學(xué)院；b. 電氣工程學(xué)院 江蘇 南京 211100）

0 引言

蟻群算法最早由意大利學(xué)者M(jìn).Dorigo引入，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。在自然界中螞蟻雖然沒有視覺，卻能發(fā)現(xiàn)食物與蟻穴之間的最短路徑。蟻群在從蟻穴到食物源并返回的過程中，能在其走過的路徑上分泌一種揮發(fā)性的化學(xué)物質(zhì)——信息素。螞蟻在開始時隨機選擇運動方向，釋放的信息素與路徑長度成反比。隨后的螞蟻能感知這種信息素的存在及其強度，并傾向于朝著信息素強度高的方向移動。單位時間里在較短的路徑上走過的螞蟻數(shù)目較多，則該路徑留下的信息素也更多，就會吸引更多的螞蟻，因此該路徑的信息素濃度得到進(jìn)一步的加強，形成一個正反饋，直到大多數(shù)螞蟻都集中到一條最短的路徑。蟻群算法就是通過螞蟻尋找食物過程中與環(huán)境之間的信息交換而實現(xiàn)螞蟻群體之間的信息傳遞，并最終達(dá)到尋找最優(yōu)路徑的目的[1]。

1 蟻群算法應(yīng)用到路由的可行性分析

由于蟻群算法具有的多樣性和正反饋等特點[2-4]，使得螞蟻總能找到較優(yōu)路徑，可以很好的應(yīng)用于通信網(wǎng)絡(luò)中。

在 Antnet協(xié)議中，螞蟻之間通過信息素這個紐帶相聯(lián)系，當(dāng)大量螞蟻選擇同一條路徑的時候容易造成擁塞。為了有效克服上述問題，本文提出了一種基于蟻群優(yōu)化算法的負(fù)載均衡路由算法Pro-antnet，有效結(jié)合了蟻群算法的正反饋、分布式計算和啟發(fā)性搜索等特點，通過對螞蟻收集到的網(wǎng)絡(luò)信息所對應(yīng)的參數(shù)賦予不同加權(quán)值的方法對路由表進(jìn)行控制，有效地緩解了網(wǎng)絡(luò)的擁塞問題。該算法設(shè)計的目標(biāo)是在選擇較短路徑的同時又能夠避開負(fù)載較重的鏈路，保持網(wǎng)絡(luò)負(fù)載分布平衡。

2 Pro-antnet蟻群算法的路由機制

Pro-antnet算法由路由建立，路由更新和路由維護(hù)三部分組成，完全按需操作。

2.1 路由建立

在算法中構(gòu)造了兩類結(jié)構(gòu)相同的人工螞蟻：前向螞蟻（Forward Ant）和后向螞蟻(Bckward Ant)。其中前向螞蟻表示從源節(jié)點到目的節(jié)點的螞蟻，用于收集該路徑信息到路由決策表（Memory），包括螞蟻所經(jīng)過的節(jié)點和到達(dá)的時間；而后向螞蟻表示找到目的節(jié)點后從目的節(jié)點返回源節(jié)點的螞蟻，在返回途中根據(jù)收集的信息對路徑上的節(jié)點進(jìn)行信息素更新。

當(dāng)源節(jié)點欲發(fā)送數(shù)據(jù)到目的節(jié)點，首先查找路由表，看是否有到達(dá)目的節(jié)點的路由信息。如果有，數(shù)據(jù)分組根據(jù)決策表中到目的節(jié)點概率最大的下一跳鄰居節(jié)點選擇路由；如果沒有，則將待發(fā)送的數(shù)據(jù)保存到緩存中，生成前向螞蟻，通過按需方式廣播給所有鄰居節(jié)點。中間節(jié)點i接收到來自i-1的前向螞蟻后，對沒有出現(xiàn)環(huán)路的前向螞蟻進(jìn)行轉(zhuǎn)發(fā)。轉(zhuǎn)發(fā)時判斷i是否有到目的節(jié)點的路由，如果有則按單播的形式轉(zhuǎn)發(fā)，否則，繼續(xù)進(jìn)行廣播。

前向螞蟻到達(dá)目的節(jié)點后將被丟棄，節(jié)點生成后向螞蟻以單播形式沿前向螞蟻的傳播路線原路返回。目的節(jié)點會在一定時期內(nèi)，在收到來自同一個源節(jié)點的多個前向螞蟻后返回后向螞蟻，以此建立源節(jié)點到目標(biāo)節(jié)點的多條路徑。后向螞蟻鏈路隊列的處理優(yōu)先級較高，目的是將收集的路由信息快速傳播回去，及時地更新各節(jié)點的路由決策表，螞蟻進(jìn)行路由尋找的過程如圖1所示。

圖1 路由尋找過程分析

在Pro-antnet協(xié)議中，為了有效地緩解網(wǎng)絡(luò)的擁塞現(xiàn)象，在選擇較短路徑的同時希望避開負(fù)載較重的鏈路，保持網(wǎng)絡(luò)負(fù)載分布平衡。源節(jié)點到目的節(jié)點間維護(hù)多條冗余路徑，通過對信息素更新來動態(tài)進(jìn)行路由選擇，同時利用信息素?fù)]發(fā)機制，對節(jié)點所維護(hù)的路由做老化處理，能夠動態(tài)適應(yīng)網(wǎng)絡(luò)變化。

節(jié)點中保存的路由決策表包含節(jié)點的本地信息和節(jié)點選擇下一跳鄰居節(jié)點的轉(zhuǎn)移概率，螞蟻選取螞蟻決策表項中概率最大的鄰居節(jié)點作為下一跳路由。

為簡化問題本文只考慮節(jié)點i和j的擁塞情況。假設(shè)qij(t)為節(jié)點i中發(fā)送到j(luò)的等待分組長度，qtotal（t）為i到所有相鄰節(jié)點的等待分組長度總和，q’total是j節(jié)點所有等待分組的長度總和，M為節(jié)點緩存隊列的長度。若用ψij(t)表示路徑的擁塞狀態(tài)，那么有：

其中α為信息素啟發(fā)因子，表示軌跡的相對重要性，其值越大則螞蟻越傾向于選擇其他螞蟻己經(jīng)經(jīng)過的路徑。

設(shè)τij（t）表示t時刻節(jié)點i到目的節(jié)點的路由中，選擇j作為下一跳的路徑上的信息素的值；ηij(t)是節(jié)點i到j(luò)的啟發(fā)式值，該啟發(fā)式值為到目節(jié)點跳數(shù)的倒數(shù)；那么在t時刻節(jié)點i選擇下一跳節(jié)點j的概率Pij(t)為：

其中β為跳數(shù)啟發(fā)因子,表示跳數(shù)的相對重要性，其值越大螞蟻越傾向于選擇較短的跳數(shù)到達(dá)目的節(jié)點。γ為負(fù)載啟發(fā)因子,反映節(jié)點負(fù)載的相對重要性,該值越大則越傾向于選擇負(fù)載較輕的節(jié)點傳送數(shù)據(jù)。

本算法在式（1）中既考慮了MAC層接口緩沖隊列中剩余空間占緩存隊列的大小，同時考慮了節(jié)點 i發(fā)送到節(jié)點 j時的堵塞程度。結(jié)合二者很好的選擇了下一條節(jié)點，減少了分組等待時間，很好的預(yù)防了網(wǎng)絡(luò)的擁塞。

2.2 路由更新

首先路由經(jīng)過初始化，每個節(jié)點的信息素初始化為1.0/N，源節(jié)點每隔一段時間t發(fā)送一個前向螞蟻，該螞蟻按決策表中概率來選擇下一跳進(jìn)行單播發(fā)送，當(dāng)前向螞蟻到達(dá)目的節(jié)點后，通過后向螞蟻對路徑信息素進(jìn)行更新。為避免殘留信息素過多導(dǎo)致殘留信息淹沒啟發(fā)信息，在 Pro-antnet蟻群算法體系中加入信息素?fù)]發(fā)機制，通過調(diào)整揮發(fā)系數(shù)使螞蟻找到的每條路由都有一個恰當(dāng)?shù)纳鏁r間。在t+△t時刻，在路由的節(jié)點i上信息素更新為：

在其他節(jié)點(k≠j)更新為：

其中r表示信息揮發(fā)系數(shù)，取值在（0，1），則1-r表示信息素濃度殘留因子。

2.3 路由維護(hù)

由于Ad Hoc網(wǎng)絡(luò)的移動性使得正在使用的路由經(jīng)常出現(xiàn)中斷。當(dāng)算法檢測到所維護(hù)的路徑上的節(jié)點有鏈路中斷時，首先緩存數(shù)據(jù)分組，看是否有其他的到目的節(jié)點的路由，如果有，選擇最大轉(zhuǎn)移概率的下一跳進(jìn)行轉(zhuǎn)發(fā)；如果沒有，則向源節(jié)點發(fā)送錯誤消息進(jìn)行路由重建。

該算法采用了多條備用路由，增強了網(wǎng)絡(luò)的穩(wěn)定性，提高了網(wǎng)絡(luò)的吞吐量和分組投遞率。另外算法考慮了網(wǎng)絡(luò)的擁塞，自適應(yīng)的選擇負(fù)載輕的路由，在一定程度上減少了端到端延時。

3 結(jié)語

單純的基于蟻群優(yōu)化的路由算法目前存在一些缺點：節(jié)點只是單獨依靠螞蟻代理來尋找最短路由，網(wǎng)絡(luò)動態(tài)變化劇烈和路由生命周期較小時，效果不會很好；存在較長的時延；在路由算法執(zhí)行過程中，容易陷入局部最優(yōu)。在網(wǎng)絡(luò)負(fù)載較輕但對時延有比較高的要求時需要引入主動式的路由維護(hù)來保證路由質(zhì)量，在路由開銷增加不大的情況下達(dá)到較短時延和較高的QoS。

本文對蟻群算法應(yīng)用到路由進(jìn)行了詳細(xì)的可行性分析，對蟻群算法的路由機制進(jìn)行了詳細(xì)的介紹，并從網(wǎng)絡(luò)均衡負(fù)載方面進(jìn)行改進(jìn)，從全局角度對蟻群算法進(jìn)行了優(yōu)化。由于信息素增量的計算以及信息素表的更新是建立最優(yōu)路由以及維護(hù)路由的重要方面，怎樣采用更好的控制參數(shù)來進(jìn)行信息素表的更新將是進(jìn)一步研究的方向。將來工作的重點是將算法加到NS2中進(jìn)行網(wǎng)絡(luò)模擬，用實驗證明算法的有效性。

[1] 段海濱. 蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社. 2005.

[2] Caro G D, Dorigo M. AntNet: A Mobile Agents Approach to Adaptive Routing [C].Belgium: Technical Report IRIDIA, 1997.

[3] 左國明,于萬鈞,胡兆瑋,等. 基于改進(jìn)蟻群算法的 Ad hoc路由算法[J].計算機應(yīng)用研究,2008,(25)1:59-61.

[4] Ziane S, Mellouk A. A swarm intelligent multi-path routing for multimedia traffic over mobile ad hoc networks[C]. USA:In Proceedings of the 1st ACM international workshop on Quality of service and security in wireless and mobile networks,2005:55-62.