基于蟻群優(yōu)化算法的路由協(xié)議的研究

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

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

0 引言

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

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

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

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

2 Pro-antnet蟻群算法的路由機(jī)制

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

2.1 路由建立

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

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

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

圖1 路由尋找過(guò)程分析

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

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

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

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

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

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

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

2.2 路由更新

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

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

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

2.3 路由維護(hù)

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

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

3 結(jié)語(yǔ)

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

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

[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] 左國(guó)明,于萬(wàn)鈞,胡兆瑋,等. 基于改進(jìn)蟻群算法的 Ad hoc路由算法[J].計(jì)算機(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.