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

郭彥芳

（重慶郵電大學(xué)重慶市移動(dòng)通信重點(diǎn)實(shí)驗(yàn)室，重慶400065）

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

郭彥芳

（重慶郵電大學(xué)重慶市移動(dòng)通信重點(diǎn)實(shí)驗(yàn)室，重慶400065）

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

Ad Hoc網(wǎng)絡(luò)；DSR；AODV；DSDV；蟻群算法；路由

0 引言

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

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

1.1 Ad Hoc網(wǎng)絡(luò)

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

1.2 DSDV、DSR和AODV

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

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

圖1 AODV路由請(qǐng)求消息發(fā)送和路由應(yīng)答

2 蟻群算法

2.1 蟻群算法思想

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

2.2 改進(jìn)蟻群算法的數(shù)學(xué)模型

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

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

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

為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻?zhàn)咄暌粋€(gè)循環(huán)后，要對(duì)殘留信息進(jìn)行更新處理。引入信息素?fù)]發(fā)系數(shù)ρ，1－ρ稱為信息素殘留因子且0＜ρ≤1，以防止痕跡上無窮大的信息素。經(jīng)過n時(shí)刻，螞蟻完成一次循環(huán)，各路徑上信息素強(qiáng)度進(jìn)行以下調(diào)整，表達(dá)式為［4］：

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

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

2.3 改進(jìn)蟻群算法的實(shí)現(xiàn)步驟

基于上述計(jì)算公式，下面給出蟻群算法的實(shí)現(xiàn)步驟：

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

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

③螞蟻數(shù)目k＝k＋1；

④選取r值，與λ進(jìn)行比較判斷；

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

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

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

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

⑨根據(jù)式（3）、式（4）和式（5）對(duì)路徑上的信息素進(jìn)行更新；

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

3 仿真場(chǎng)景

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

3.1 仿真參數(shù)設(shè)置

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

3.2 仿真環(huán)境

使用2個(gè)場(chǎng)景分別對(duì)MANET中ant－DSR、ant－AODV和ant－DSDV的網(wǎng)絡(luò)性能進(jìn)行評(píng)估。每次結(jié)果都取5次仿真的平均值。

第1個(gè)場(chǎng)景：增加節(jié)點(diǎn)運(yùn)動(dòng)速度。這種情況下，使用2～18 m/s的9種不同的速度對(duì)路由協(xié)議性能進(jìn)行評(píng)估。

第2個(gè)場(chǎng)景：不同停留時(shí)間。這種情況下使用停頓時(shí)間在10～100 s之間，以評(píng)估在動(dòng)態(tài)網(wǎng)絡(luò)中的路由協(xié)議的性能。停留時(shí)間取值為0時(shí)對(duì)應(yīng)最大移動(dòng)性場(chǎng)景，取值為100 s對(duì)應(yīng)靜止場(chǎng)景，隨著停留時(shí)間的增加，節(jié)點(diǎn)移動(dòng)性隨之減弱。越小的暫停時(shí)間值將會(huì)造成更加復(fù)雜的網(wǎng)絡(luò)拓?fù)渥兓瑢?duì)尋找最佳路徑的過程也會(huì)產(chǎn)生影響。

4 結(jié)果分析

4.1 速率方案

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

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

圖2 不同速率下各個(gè)參數(shù)的性能

4.2 停留時(shí)間方案

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

圖3 不同停留時(shí)間下各個(gè)參數(shù)的性能

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

5 結(jié)束語

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

［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］吳華鋒，陳信強(qiáng)，毛奇凰，等.基于自然選擇策略的蟻群算法求解TSP問題［J］.通信學(xué)報(bào)，2013，34（4）：165－170.

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

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

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

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

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

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

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

［12］曹潔，王思樂，帥立國.多機(jī)器人Ad Hoc路由協(xié)議中蟻群算法的改進(jìn)［J］.蘭州理工大學(xué)學(xué)報(bào)，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］.無線電通信技術(shù)，2015，41（4）：08－11.

2015－01－21

長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃（IRT1299）；重慶市科委項(xiàng)目（CSTC2012jjA40044，cstc2013yykfA40010）；重慶市科委重點(diǎn)實(shí)驗(yàn)室專項(xiàng)經(jīng)費(fèi)

郭彥芳（1989—），女，碩士研究生，主要研究方向：移動(dòng)通信、無線Ad Hoc網(wǎng)絡(luò)。