基于蟻群算法的典型路由協(xié)議的比較研究

郭彥芳

（重慶郵電大學重慶市移動通信重點實驗室，重慶400065）

基于蟻群算法的典型路由協(xié)議的比較研究

郭彥芳

（重慶郵電大學重慶市移動通信重點實驗室，重慶400065）

針對Ad hoc網絡拓撲結構的多變和基本蟻群算法易失去多解的情況，在對算法的節(jié)點選擇進行改進后，提出把蟻群算法與DSR、AODV和DSDV相結合，即ant－DSR、ant－AODV和ant－DSDV。利用改進的蟻群算法尋找最優(yōu)路徑，在節(jié)點速率、停留時間這2種不同場景下分析比較了端到端時延、吞吐量、路由開銷和跳數等參數的性能。仿真結果表明，先應式路由協(xié)議比按需路由協(xié)議在提高性能上更適合于蟻群算法，但卻增加了路由開銷，并且每個節(jié)點產生最優(yōu)路徑時需要更多的計算。

Ad Hoc網絡；DSR；AODV；DSDV；蟻群算法；路由

0 引言

Ad hoc網絡中，每個節(jié)點能通過路由協(xié)議找到最優(yōu)路徑來進行彼此通信。因為尋找最優(yōu)路徑的過程比較復雜，所以路由協(xié)議對網絡性能的要求極大。目前Ad Hoc網絡中已經在使用的路由協(xié)議有DSR、AODV和DSDV等。DSDV代表了基于表驅動的先應式路由協(xié)議，而AODV和DSR代表了按需的反應式路由協(xié)議。路由協(xié)議中的算法是用于改善發(fā)送消息的節(jié)點尋找出最優(yōu)路由的過程，而蟻群算法是目前路由協(xié)議選擇的算法之一。重點討論了采用改進蟻群算法尋找最佳路徑的3種典型路由性能的比較研究。基于改進蟻群算法的DSR、AODV和DSDV稱為ant－DSR、ant－AODV和ant－DSDV。用QoS參數中的時延和吞吐量對3種基于蟻群算法的路由協(xié)議的性能進行衡量，而為了了解尋找最優(yōu)和最短路由過程的復雜性，使用路由開銷和跳數衡量路由協(xié)議的性能。若路由協(xié)議能產生較好的路由開銷和最短跳數、較高的吞吐量和較短的時延則此算法比較可行。

1 3種路由協(xié)議簡單介紹

1.1 Ad Hoc網絡

Ad Hoc網絡是有一組帶有無線收發(fā)裝置的移動節(jié)點組成的一個多跳臨時性的自治系統(tǒng)，它不依賴預設的基礎設施而臨時組建，網絡中的移動節(jié)點利用自身的無線收發(fā)設備交換信息，當它們之間不在彼此的通信范圍內時，可以借助于其他中間節(jié)點來實現多跳通信。網絡上的每個節(jié)點通信均是依賴于路由協(xié)議進行，路由協(xié)議在Ad Hoc網絡中是不可或缺的。

1.2 DSDV、DSR和AODV

目的距離路由矢量（DSDV）是一種先應式路由協(xié)議。DSDV中，每個節(jié)點都保存一個路由表，路由表維護本節(jié)點到網絡內所有可達目的節(jié)點的路由。路由更新是通過檢查每個節(jié)點到來的序列號進行的。動態(tài)源路由協(xié)議（DSR）是一種反應式路由協(xié)議，最重要的特點就是利用了源路由算法，每一個給定路線的數據分組都在報頭帶有完整、有序的此分組必經節(jié)點列表。每個節(jié)點把自己所知的任何新的路由信息都存儲在Cache中，而不管是以何種方式獲得路由信息的。自組織網按需距離矢量路由（AODV）是一種反應式路由協(xié)議。在AODV協(xié)議中，當一段時期內不用一個路由時將會失效或被丟棄，這減少了路由維護需求并使得路由數量最小化。當一個路由被使用時，其周期表將進行更新。

例如在圖1中，節(jié)點1若向節(jié)點6發(fā)送一條消息，但路由表中不存在此路由信息，然后它將發(fā)送RREQ到它的鄰居節(jié)點，即節(jié)點2和節(jié)點3。由于還沒有找到目的節(jié)點，節(jié)點3將把RREQ發(fā)送到它的鄰居節(jié)點，即節(jié)點4和節(jié)點5。由于節(jié)點4中已有關于節(jié)點6的消息，那么節(jié)點6將發(fā)送RREP到節(jié)點3，接著到節(jié)點1。當節(jié)點1更新路由表后，一條消息就能被發(fā)送到節(jié)點6。

圖1 AODV路由請求消息發(fā)送和路由應答

2 蟻群算法

2.1 蟻群算法思想

蟻群算法首先由意大利學者Dorigo［1－3］于1991年提出，并用該方法解決了一系列的組合優(yōu)化問題。通過分析發(fā)現，螞蟻覓食過程，與Ad Hoc網絡路由問題有很多相似之處。結合Ad Hoc網絡環(huán)境進行模擬，將螞蟻覓食過程中的“蟻穴”和“食物源”當作Ad Hoc網絡中的源結點和目的結點，將螞蟻的行為當作網絡中的數據通信，蟻群算法中有一個螞蟻決策表，它包括所有結點選擇下一路徑的轉移概率和關于結點的本地信息，螞蟻使用這個表來指導其搜索朝著搜索空間中最有吸引力的區(qū)域移動，這正是網絡通信中路由表的形成過程。因此，蟻群算法能夠應用于Ad Hoc網絡的路由，通過信息素的釋放尋找并維護從源結點到達目的結點的最優(yōu)路由，按照信息素的揮發(fā)算法不斷對各結點的信息素值進行更新，以適應網絡動態(tài)變化的需要。

2.2 改進蟻群算法的數學模型

首先引入一些符號參數［4，5］。設總結點數n，所組成的集合是C，坐標系（x，y），源節(jié)點s，目的節(jié)點d，m只螞蟻，用dij（i，j＝1，2，…，n）表示節(jié)點i和節(jié)點j之間的距離。τij（t）表示t時刻在節(jié)點i和節(jié)點j之間的路徑上殘留的信息素強度。初始時刻，各條路徑上信息素強度相等，設τij（0）＝const（const）。螞蟻k（k＝1，2，…，m）在運動過程中，根據各條路徑上的信息素強度決定轉移方向，同時用禁忌表tab uk（k＝1，2，…，n）來記錄螞蟻k當前已走過的節(jié)點，禁忌表tab uk隨進化過程作動態(tài)調整。pkij（t）表示在t時刻螞蟻k由節(jié)點i轉移到節(jié)點j的狀態(tài)轉移概率，其表達為［6，7］：

而為了避免螞蟻一開始就失去解的多樣性，在式（1）的基礎上，第k只螞蟻按以下概率從位置i到位置j：

式中：r和λ為（0，1）中均勻分布的隨機數，參數λ的大小決定了利用先驗知識與探索新路徑之間的相對重要性；每當一只位于位置i的螞蟻選擇下一個要達到的位置j時，它選取一個隨機數r，如果r≤λ，則根據式（2）選擇最好的路徑，否則按式（1）的概率來選擇一條路徑，因此增加了所得解的多樣性，在一定程度上削弱了蟻群陷入局部最優(yōu)的趨勢。

為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻走完一個循環(huán)后，要對殘留信息進行更新處理。引入信息素揮發(fā)系數ρ，1－ρ稱為信息素殘留因子且0＜ρ≤1，以防止痕跡上無窮大的信息素。經過n時刻，螞蟻完成一次循環(huán)，各路徑上信息素強度進行以下調整，表達式為［4］：

式中，Δτij表示本次循環(huán)留在路徑（i，j）上的信息素強度；表示第k只螞蟻在本次循環(huán)中留在路徑（i，j）上的信息素強度的增量，其表達式為［5，6］：

式中，Q是與第k只螞蟻所攜帶的信息度強度和本次循環(huán)所走過路徑長度有關的量，它影響算法的收斂速度；Lk是螞蟻k在本次循環(huán)中所走路徑的長度，其計算公式為：

2.3 改進蟻群算法的實現步驟

基于上述計算公式，下面給出蟻群算法的實現步驟：

①參數初始化。令t＝0時，循環(huán)次數NC＝0，循環(huán)次數的最大值為NCmax，將m只螞蟻隨機放到n個初始節(jié)點處，Δτij（0）＝0；

②循環(huán)次數NC＝NC＋1；

③螞蟻數目k＝k＋1；

④選取r值，與λ進行比較判斷；

⑤每只螞蟻根據式（1）或（2）選擇下一節(jié)點j并前進；

⑥更新禁忌表，并將螞蟻移到新的節(jié)點；

⑦若節(jié)點j不是目的節(jié)點，則跳轉⑤繼續(xù)執(zhí)行；

⑧若k＜m，則跳轉③繼續(xù)執(zhí)行；

⑨根據式（3）、式（4）和式（5）對路徑上的信息素進行更新；

⑩如果螞蟻全部收斂到一條路徑上或NC＞NCmax，則結束。并輸出結果，否則清空禁忌表并跳轉②繼續(xù)執(zhí)行。

3 仿真場景

在MANET中，DSR、AODV和DSDV已被廣泛進行研究。蟻群算法在尋找最短路徑的路由協(xié)議中得到了廣泛的應用，研究和分析在各種測試情況下的路由協(xié)議的性能，并且比較QoS的一些參數的性能。

3.1 仿真參數設置

仿真工具選用NS2，模擬環(huán)境使用的MAC層采用IEEE802.11協(xié)議，天線模式全方位，排隊模型Droptail，節(jié)點總數為50個，所有節(jié)點隨機分布在500×500 m2的范圍內，節(jié)點可以隨機移動，物理層采用TwoRayGround無線傳播模型，并且模擬持續(xù)時間為100 s。揮發(fā)系數ρ取0.5，信息啟發(fā)式因子α取1，期望啟發(fā)式因子β取0.7。由延遲、吞吐量、路由開銷、跳數來對ant－DSR、ant－AODV和ant－DSDV的路由協(xié)議性能進行仿真分析。

3.2 仿真環(huán)境

使用2個場景分別對MANET中ant－DSR、ant－AODV和ant－DSDV的網絡性能進行評估。每次結果都取5次仿真的平均值。

第1個場景：增加節(jié)點運動速度。這種情況下，使用2～18 m/s的9種不同的速度對路由協(xié)議性能進行評估。

第2個場景：不同停留時間。這種情況下使用停頓時間在10～100 s之間，以評估在動態(tài)網絡中的路由協(xié)議的性能。停留時間取值為0時對應最大移動性場景，取值為100 s對應靜止場景，隨著停留時間的增加，節(jié)點移動性隨之減弱。越小的暫停時間值將會造成更加復雜的網絡拓撲變化，對尋找最佳路徑的過程也會產生影響。

4 結果分析

4.1 速率方案

圖2顯示了不同速率下3種路由協(xié)議的仿真結果。ant－DSDV有最小的延遲和跳數，然而有最高的路由開銷，ant－DSR可能是較高的吞吐量和最低的路由開銷。ant－AODV具有最高的跳數參數。

在這個場景中可以看出在較高吞吐量和較小路由開銷是上ant－DSR性能要優(yōu)于ant－AODV和ant－DSDV。同時，找到最佳路徑的復雜過程依賴于設備的功耗。路由開銷的增加表示為了在網絡上分組發(fā)送，路由協(xié)議找到最佳路由需要額外的能量。此外，ant－DSDV由于增加了復雜的流程，導致路由開銷和額外能量的增加。此種情況下，ant－AODV是最高的跳數參數，但性能最低，而對于按需路由協(xié)議，ant－DSR比ant－AODV好。由于數據傳輸路徑上的改變，用戶速度的改變可能影響網絡配置，這些狀況也可能導致較高的誤比特率和短暫性的網絡分區(qū)。

圖2 不同速率下各個參數的性能

4.2 停留時間方案

圖3顯示了不同停留時間下3種路由協(xié)議的仿真結果。ant－DSDV在延遲、路由開銷和跳數方面比其他的路由協(xié)議有較好的性能。

圖3 不同停留時間下各個參數的性能

由于網絡拓撲可以隨意地改變，停留時間的減少會引起路由改變。在這種情況下，路由算法必須解決復雜的情況才能，ant－AODV有最高的路由開銷和跳數，而ant－DSR有較長的延遲。這一結果表明，ant－AODV或ant－DSR這2種協(xié)議由于網絡的復雜性在找到最好的路徑情況下可能效果較小，此種情況下ant－DSDV路由協(xié)議比按需路由協(xié)議更好。

5 結束語

引入的蟻群算法能較好地適應Ad Hoc網絡的動態(tài)變化，比較了在使用不同的仿真場景下路由協(xié)議的整體性能。仿真結果表明，在提高性能方面，ant－DSDV比ant－DSR和ant－AODV較好些。然而由于揮發(fā)系數的存在，今后蟻群算法的改進必須考慮路徑規(guī)劃的最優(yōu)性和尋找最佳路線過程的復雜性。下一步可以對信息素的更新進行改進，使得算法的性能達到更好的效果。

［1］Dorigo M，Gambardella L M.Ant Colonies for the Traveling Salesman Problem［J］.BioSystems，1997，43（2）：73－81.

［2］Dorigo M，Di C G，Gambardella L M.Ant Algorithms for Discrete Optimization.［J］.Artif Life，2000，5（2）：137－72.

［3］Dorigo M，Gambardella L M.Ant Colonies for the Traveling Salesman Problem［J］.BioSystems，1996（3）1－10.

［4］吳華鋒，陳信強，毛奇凰，等.基于自然選擇策略的蟻群算法求解TSP問題［J］.通信學報，2013，34（4）：165－170.

［5］王越，葉秋冬.蟻群算法在求解最短路徑問題上的改進策略［J］.計算機工程與應用，2012，48（13）：35－38.

［6］任興田，王勇.基于蟻群算法的自適應Ad hoc路由協(xié)議［J］.北京工業(yè)大學學報，2012，38（5）：744－748.

［7］王學峰，周繼鵬.基于蟻群算法的Ad Hoc網絡能量均衡路由協(xié)議［J］.計算機技術與發(fā)展，2014，24（2）：25－28.

［8］周少瓊，徐祎，姜麗，等.蟻群優(yōu)化算法在Ad Hoc網絡路由中的應用［J］.計算機應用，2011，31（2）：332－334.

［9］任敬安，涂亞慶.基于蟻群優(yōu)化的Ad Hoc網絡路由協(xié)議實現［J］.計算機工程，2012，38（21）：114－118，122.

［10］馮勇，廖瑞華，饒妮妮，等.基于改進蟻群算法的Ad Hoc路由協(xié)議的研究［J］.電子與信息學報，2008，30（10）：2472－2475.

［11］鄭衛(wèi)國，田其沖，張磊..基于信息素強度的改進蟻群算法［J］.計算機仿真，2010.27（7）：191－193.

［12］曹潔，王思樂，帥立國.多機器人Ad Hoc路由協(xié)議中蟻群算法的改進［J］.蘭州理工大學學報，2012，38（6）：73－77.

Comparative Research on Typical Routing Protocols Based on Ant Colony Algorithm

GUO Yan－fang
（Chongqing Key lab of Mobile Communications Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

Aiming at Ad hoc network changing topology and basic ant colony easy to losemultiple solutions，this paper proposes the combiningmethod of ant colony algorithm and DSR，AODV and DSDV，called ant－DSR，ant－AODV and ant－DSDV after improving the next hop node selection.The improved ant colony algorithm is used to find the optimal path.The end to end delay，throughput，routing overhead，and hop count performance parameters are analyzed and compared in such two scenarios as node rate and pause time.The simulation results show that the first routing protocol ismore adaptable to the ant colony algorithm to improve performance compared with on－demand routing protocols，but it increases routing overhead and requiresmore calculation to find the optimal path in each node.

Ad hoc network；DSR；AODV；DSDV；ant colony algorithm；routing

TP393

A

1003－3114（2015）04－08－4

10.3969/j.issn.1003－3114.2015.04.02

郭彥芳.基于蟻群算法的典型路由協(xié)議的比較研究［J］.無線電通信技術，2015，41（4）：08－11.

2015－01－21

長江學者和創(chuàng)新團隊發(fā)展計劃（IRT1299）；重慶市科委項目（CSTC2012jjA40044，cstc2013yykfA40010）；重慶市科委重點實驗室專項經費

郭彥芳（1989—），女，碩士研究生，主要研究方向：移動通信、無線Ad Hoc網絡。