黃亞玲

摘要：網(wǎng)絡(luò)的發(fā)展刺激路由器的市場需求與日俱增，路由算法也因此備受青睞。該文主要敘述對距離矢量路由算法的基本認識，淺析了它的工作原理和現(xiàn)存的路由缺陷，并利用蟻群算法原理提出優(yōu)化方案。

關(guān)鍵詞：距離矢量路由算法；路由缺陷；蟻群算法

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2015）13-0041-02

Abstract： Stimulate development of the network router's market demand is growing， routing algorithm is becoming popular. This paper mainly described the basic understanding of distance vector routing algorithm， analyses its working principle and the existing routing defects， and use the principle of ant colony algorithm optimization scheme is put forward.

Key words： distance vector routing algorithm； routing defects； ant colony algorithm

距離矢量算法和鏈路狀態(tài)算法是現(xiàn)代計算機網(wǎng)絡(luò)中最為流行兩大路由算法。距離矢量路由算法在能夠自適應(yīng)網(wǎng)絡(luò)拓撲結(jié)構(gòu)和流量變化，簡單快速的實現(xiàn)的網(wǎng)絡(luò)連接。雖然距離矢量路由算法實現(xiàn)簡單，但是也存在著一定的缺陷。蟻群算法是通過模擬螞蟻覓食規(guī)律設(shè)計出的一種需找最優(yōu)路徑的算法。它具備的正反饋性和并行性等特性可以有效的改善距離矢量算法。本文簡單的介紹了距離矢量路由算法的工作過程和原理，并提出利用蟻群算法對距離矢量算法的優(yōu)化方案。

1 距離矢量路由算法

1.1距離矢量路由算法的基本認識

現(xiàn)在的距離矢量路由算法（Distance Vector Routing，DV算法）主要應(yīng)用在因特網(wǎng)的路由通信協(xié)議（RIP協(xié)議）中。同一網(wǎng)絡(luò)區(qū)域中的每個路由器都動態(tài)保存著到達其他路由器路徑的路由表。然而，這一路徑是根據(jù)“跳”來計算的，即數(shù)據(jù)包每經(jīng)過一個路由器稱為一跳。同時各路由器也只能與相鄰的路由器進行數(shù)據(jù)交互，更新路由表信息。這一過程類似于“傳話”游戲。

1.2 DV算法的工作過程及缺陷

如上圖1，假設(shè)A要向B發(fā)送一條消息，這個數(shù)據(jù)包可以利用不同的路徑將數(shù)據(jù)傳輸?shù)紹。根據(jù)DV算法的原理，它會選擇一條跳數(shù)最少的最佳路徑，就是從R0傳遞到R1，再傳遞到R2，再傳遞到R5，最后將數(shù)據(jù)發(fā)送到B。

我們很快可以發(fā)現(xiàn)一個問題，DV算法僅僅是選擇跳數(shù)最少的路徑，它并沒有考慮路線消耗和時延問題。這就是類似我們打出租車是選擇路徑最短還是用時最少是一樣的道理。有時候最短的路出租車走的比較多就會造成擁堵現(xiàn)象，此時繞遠一點反而一路暢通，在更短的時間內(nèi)到達目的地。就如圖1所示，R0到R1到R2到R5是四跳，而R0到R3到R4到R2到R5是五跳，看似跳數(shù)少的前者更為合理，但是在這條鏈路擁堵的時候需要更多的等待時間，此時選擇后者反而能更快的將數(shù)據(jù)包發(fā)送出去。所以原始的DV算法只適合網(wǎng)絡(luò)負荷可以預(yù)測的簡單網(wǎng)絡(luò)。

此外，原始DV算法在正常的網(wǎng)絡(luò)中總能夠正確傳輸，但是它的收斂速度非常慢。對于好的消息傳輸?shù)姆浅？?，對于壞的消息傳輸?shù)膮s非常的慢。例如R2去往網(wǎng)絡(luò)的路由故障了，但是消息沒有及時更新，R1依舊保存著R2可以到達網(wǎng)絡(luò)的舊信息，以至于R2從R1的信息里錯誤的認為R1可以到達網(wǎng)絡(luò)。它們同時認為可以通過彼此到達網(wǎng)絡(luò)，從而形成了路由環(huán)路。

2 DV算法的優(yōu)化方案

2.1 蟻群算法的工作原理

蟻群算法是模擬螞蟻在復(fù)雜的自然環(huán)境中覓食過程，通過釋放信息素的方式找出最優(yōu)路徑。信息素是螞蟻在覓食路徑上釋放的能夠互相檢測到分泌物。當(dāng)一只螞蟻在盲目找路的過程中檢測到其他螞蟻留下的信息素后，就會沿此路線前進并釋放信息素，加強信息素濃度方便其他的螞蟻盡快找到路線。

2.2 利用蟻群算法優(yōu)化DV算法

蟻群通過個體之間的相互協(xié)作和信息交流而具備發(fā)現(xiàn)最優(yōu)解的能力，這種能力的本質(zhì)在于以下三種機制：

（1） 選擇機制：選擇信息素濃度大的路徑作為移動方向。

（2） 更新機制：路徑的上的信息素濃度會因為走過的螞蟻數(shù)量增加而濃，也會因為時間的推移而揮發(fā)。

（3） 協(xié)作機制：蟻群利用信息素互相協(xié)作和交流信息。

為了更好的實現(xiàn)距離矢量算法選擇最優(yōu)路徑和路由信息表的更新，我們定義正向蟻群[Rant]和反向蟻群[Bant]這兩種人工蟻群。正向蟻群[Rant]主要用來收集從初始路由節(jié)點到目的路由節(jié)點的跳數(shù)和延時等路由開銷信息，并釋放食物源信息素。反向蟻群[Bant]根據(jù)正向蟻群[Rant]收集到的信息從目的路由節(jié)點到初始節(jié)點途中所有節(jié)點的路由信息表，并且反向蟻群[Bant]具有記憶功能，將保存路由節(jié)點序號和路由表所有信息，并釋放巢穴信息素。將這兩種螞蟻抽象的放到網(wǎng)絡(luò)拓撲結(jié)構(gòu)中，通過它們頻繁的移動探測周圍網(wǎng)絡(luò)信息，選擇最優(yōu)的路由路徑以及完成路由表更新。

2.2.1 路由節(jié)點的選擇

在有n個節(jié)點的網(wǎng)絡(luò)環(huán)境中，正向蟻群[Rant]從路由節(jié)點i出發(fā)，在所有鄰接節(jié)點選擇下一跳的路由節(jié)點j，目的路由節(jié)點為d。若所有鄰接節(jié)點都未訪問過，則隨機選擇下一跳，否則選擇概率[Pij]最大的鄰接節(jié)點，那么[P'ij]的表達式為：

[Pij（t）=ωij（t）αξij（t）βs?Nkωis（t）αξis（t）β，j∈Nk]

[ξij=1dij]

其中[Nk]表示[Rant]的下一跳路由節(jié)點集合，[ωij]表示路由節(jié)點i到路由節(jié)點j路徑上的信息素值，[ξij]表示從路由節(jié)點i移動到路由節(jié)點j的啟發(fā)因子。

若正向螞蟻[Rant]在移動過程中訪問到已訪問的路由節(jié)點，可判斷為進入路由環(huán)路，則刪除整個環(huán)路上的所有信息并返回環(huán)路初始節(jié)點重新移動。同時若正向螞蟻[Rant]的移動時間超過了它的生存周期，為了避免將未知路由信息帶入網(wǎng)絡(luò)引發(fā)死循環(huán)，則丟棄這類正向螞蟻。最先到達目的路由節(jié)點d的正向螞蟻觸發(fā)創(chuàng)建逆向螞蟻[Bant]，并將搜索過程中的路由信息（跳數(shù)，時延，路由開銷等）傳遞給逆向螞蟻后，正向螞蟻被殺死。

2.2.2 路由信息表的更新

逆向螞蟻[Bant]接受到正向螞蟻的所有信息后，沿著正向螞蟻反向路徑隨機選擇一條可行路徑移動，并更新途中的所有路由節(jié)點的信息素值。若因路徑故障導(dǎo)致逆向螞蟻無法返回到初始路由節(jié)點，則殺死這類逆向螞蟻，使得優(yōu)化后的距離矢量算法更好的適應(yīng)網(wǎng)絡(luò)環(huán)境的變化，及時調(diào)整路由路徑。

（1）若路由節(jié)點i的下一跳節(jié)點j是逆向螞蟻移動過來的節(jié)點，則增加下一跳節(jié)點的信息素值[ωij]，表達式為：

[ωij（t+1）=（1-η）ωij（t）+ηΔωij（t），η∈（0，1）]

[Δωij（t）=1dij]

其中[η]為信息素揮發(fā)因素系數(shù)，[dij]是螞蟻構(gòu)建的i到j(luò)的路徑長度。

（2）若路由節(jié)點i選擇其他鄰接路由節(jié)點，則需要揮發(fā)信息素，保證路由路徑中信息素的平衡，揮發(fā)信息素表達式為：

[ωij=（1-r）ωij]

其中[i≠j，j∈Nk]。

目前人們對于基于蟻群算法的路由優(yōu)化并在應(yīng)用中取得一定的成果，但是怎樣更好的提高蟻群算法的收斂性和速度依舊是未來路由優(yōu)化研究的熱點。

3 結(jié)束語

距離矢量算法在Internet通信網(wǎng)絡(luò)中的作用是不容小覷的，雖然在一個靜態(tài)網(wǎng)絡(luò)中總能夠到達目的地，但是它的收斂性非常慢，尤其是壞消息傳遞的非常慢。本文通過定義正反向螞蟻對距離矢量算法的慢收斂性進行分析改進，得以優(yōu)化距離矢量算法的思想。

參考文獻：

[1] 賈云富， 秦勇， 段富， 等. 蟻群算法及其在路由優(yōu)化中的應(yīng)用綜述[J]. 計算機工程與設(shè)計， 2009.

[2] 衛(wèi)海亮. 蟻群算法及其在網(wǎng)絡(luò)優(yōu)化中的應(yīng)用研究[D]. 西安電子科技大學(xué)， 2012.

[3] 朱永利， 李麗芬. 長鏈樹狀無線傳感器網(wǎng)絡(luò)中遺傳蟻群路由優(yōu)化算法[J]. 小型微型計算機系統(tǒng)， 2012.