基于蟻群優化算法的路由協議的研究

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

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

0 引言

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

1 蟻群算法應用到路由的可行性分析

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

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

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

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

2.1 路由建立

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

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

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

圖1 路由尋找過程分析

在Pro-antnet協議中，為了有效地緩解網絡的擁塞現象，在選擇較短路徑的同時希望避開負載較重的鏈路，保持網絡負載分布平衡。源節點到目的節點間維護多條冗余路徑，通過對信息素更新來動態進行路由選擇，同時利用信息素揮發機制，對節點所維護的路由做老化處理，能夠動態適應網絡變化。

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

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

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

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

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

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

2.2 路由更新

首先路由經過初始化，每個節點的信息素初始化為1.0/N，源節點每隔一段時間t發送一個前向螞蟻，該螞蟻按決策表中概率來選擇下一跳進行單播發送，當前向螞蟻到達目的節點后，通過后向螞蟻對路徑信息素進行更新。為避免殘留信息素過多導致殘留信息淹沒啟發信息，在 Pro-antnet蟻群算法體系中加入信息素揮發機制，通過調整揮發系數使螞蟻找到的每條路由都有一個恰當的生存時間。在t+△t時刻，在路由的節點i上信息素更新為：

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

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

2.3 路由維護

由于Ad Hoc網絡的移動性使得正在使用的路由經常出現中斷。當算法檢測到所維護的路徑上的節點有鏈路中斷時，首先緩存數據分組，看是否有其他的到目的節點的路由，如果有，選擇最大轉移概率的下一跳進行轉發；如果沒有，則向源節點發送錯誤消息進行路由重建。

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

3 結語

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

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

[1] 段海濱. 蟻群算法原理及其應用[M].北京:科學出版社. 2005.

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

[3] 左國明,于萬鈞,胡兆瑋,等. 基于改進蟻群算法的 Ad hoc路由算法[J].計算機應用研究,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.