畢業(yè)論文---基于蟻群算法的網(wǎng)絡(luò)多節(jié)點路由優(yōu)化

1、<p><b>　　1 緒論</b></p><p>　　通信網(wǎng)絡(luò)的迅速發(fā)展，新業(yè)務(wù)的不斷出現(xiàn)，使多點通信成為網(wǎng)絡(luò)必須支持的功能。傳統(tǒng)網(wǎng)絡(luò)中使用一對一的通信協(xié)議支持多點協(xié)議，數(shù)據(jù)需要做多個拷貝，分別傳送，極大的浪費了網(wǎng)絡(luò)資源。未來的多媒體通信，將帶來大量的多點通信，使用點對點協(xié)議將造成網(wǎng)絡(luò)效率的低下；另外，多媒體通信的業(yè)務(wù)通常需要達成一定的同步關(guān)系，使用點對點協(xié)議完成多點通信不再有

2、效；而復用技術(shù)的發(fā)展使組播在共同的鏈路上共享帶寬成為可能。由于上述原因必須考慮多點路由問題。</p><p>　　由于網(wǎng)絡(luò)是動態(tài)變化的，網(wǎng)絡(luò)拓撲結(jié)構(gòu)的變化的不可預(yù)測性和變化的頻繁性和不確定性是網(wǎng)絡(luò)多點路由問題與其他常見的組合優(yōu)化問題的根本不同之處，網(wǎng)絡(luò)流量的隨機性和偶然性也是網(wǎng)絡(luò)動態(tài)變化的主要因素。有效快捷的網(wǎng)絡(luò)路由算法是網(wǎng)路發(fā)展的重要問題。</p><p>　　而蟻群算法的出現(xiàn)和廣泛應(yīng)用

3、，提供了多點路由優(yōu)化設(shè)計的新的思想。蟻群算法是一種模擬進化算法，它是在對自然界中真實蟻群的集體行為研究的基礎(chǔ)上，由意大利學者M.Dorigo等人首先提出的。M.Dorigo等人充分利用了蟻群搜索食物的過程與著名的旅行商問題（TSP）之間的相似性，通過人工模擬螞蟻搜索食物的過程（即通過個體之間的信息交流與相互協(xié)作最終找到從蟻穴到食物源的最短路徑）來求解TSP問題。仿生學家通過大量細致觀察研究發(fā)現(xiàn)，螞蟻個體之間是通過一種被稱為外激素的物質(zhì)進

4、行信息傳送，從而能相互協(xié)作，完成復雜的任務(wù)。螞蟻在運動過程中，能在它所經(jīng)過的路徑上留下該物質(zhì)，而且螞蟻在運動過程中能夠感知這種物質(zhì)的存在及其強度，并以此指導自己的運動方向，螞蟻傾向于朝著這種物質(zhì)強度高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻個體之間就是通過這種信息的交流達到搜索食物的目的。蟻群算法是一種隨機搜索算法，與其它模擬進化算法一樣，

5、通過候選解組成的群體的進化過程來尋求最優(yōu)解，該過程包含兩個基本階段：適應(yīng)階段和協(xié)作階段。在適應(yīng)</p><p>　　蟻群算法之所以能引起相關(guān)領(lǐng)域研究者的注意，是因為這種求解模式能將問題求解的快速性、全局優(yōu)化特征以及有限時間內(nèi)答案的合理性結(jié)合起來。其中，尋優(yōu)的快速性是通過正反饋式的信息傳遞和積累來保證的。而算法的早熟性收斂又可以通過其分布式計算特征加以避免，同時，具有貪婪啟發(fā)式搜索特征的蟻群系統(tǒng)又能在搜索過程的早期

6、找到可以接受的問題解答。這種優(yōu)越的問題分布式求解模式經(jīng)過相關(guān)領(lǐng)域研究者的關(guān)注和努力，已經(jīng)在最初的算法模型基礎(chǔ)上得到了很大的改進和拓展?；谙伻核惴ǖ囊陨咸攸c，將蟻群算法用于OSPF協(xié)議的網(wǎng)絡(luò)中，根據(jù)不同網(wǎng)絡(luò)的需要尋找最優(yōu)路徑（可以是時延、中間路由器個數(shù)或者費用等參數(shù)最優(yōu)化），將是一個非常值得我們?nèi)パ芯康恼n題。</p><p>　　1.1 本設(shè)計研究的目的意義</p><p>　　人們生活的

7、現(xiàn)代社會是一個由計算機信息網(wǎng)絡(luò)、電話通信網(wǎng)絡(luò)、運輸服務(wù)網(wǎng)絡(luò)、能源和物流分配網(wǎng)絡(luò)等各種網(wǎng)絡(luò)組成的復雜的網(wǎng)絡(luò)系統(tǒng)。網(wǎng)絡(luò)優(yōu)化的目的就是研究如何有效地計劃、控制和管理這個網(wǎng)絡(luò)系統(tǒng)，使之發(fā)揮最大的社會效益和經(jīng)濟效益。網(wǎng)絡(luò)優(yōu)化是運籌學的是一個經(jīng)典和重要的分支，所研究的問題涉及諸多領(lǐng)域，一方面是如何最大限度的節(jié)省資源，如最短路徑、最小費用等；另一方面是在網(wǎng)絡(luò)資源有限的情況下如何發(fā)揮其最大效益，如最大物流問題、最優(yōu)資源配置問題等。網(wǎng)絡(luò)優(yōu)化問題是一類特殊

8、的組合優(yōu)化問題，屬于NP難問題。對于此類NP問題，傳統(tǒng)運籌學的優(yōu)化方法顯得無能為力，尋找、研究、應(yīng)用啟發(fā)式智能化的優(yōu)化方法顯得尤為重要。螞蟻算法就是其中一種有效的啟發(fā)式智能優(yōu)化算法。</p><p>　　本設(shè)計就是要在掌握蟻群算法的基礎(chǔ)上，將其用于網(wǎng)絡(luò)路由優(yōu)化問題，根據(jù)不同網(wǎng)絡(luò)的特點和需求，對算法進行相應(yīng)修改，編寫出優(yōu)化軟件。由于這種求解模式能將問題求解的快速性、全局優(yōu)化特征以及有限時間內(nèi)答案的合理性結(jié)合起來，因

9、而能適應(yīng)網(wǎng)絡(luò)各種因素隨機變化的的特性，將其用于OSPF協(xié)議的工作過程中，可以快速有效的找出其所需的最優(yōu)路徑。最終，實現(xiàn)網(wǎng)絡(luò)資源的合理利用和高效的數(shù)據(jù)傳輸，提高網(wǎng)絡(luò)的運行速度，這對于互聯(lián)網(wǎng)今后的快速發(fā)展起著重要的促進作用。</p><p>　　1.2 本設(shè)計的研究現(xiàn)狀</p><p>　　蟻群算法誕生于1991年，是一類新穎而前沿的問題求解算法。在算法改進與理論問題的應(yīng)用領(lǐng)域，這種算法很快就

10、得到了國內(nèi)外學者們的關(guān)注。在國外，學者們提出了不同版本的蟻群算法，進一步地提高算法的性能；同時，他們也把蟻群算法應(yīng)用到眾多復雜的經(jīng)典理論問題中，包括旅行商、車輛路由、二次指派、工序調(diào)度、背包問題、群組規(guī)劃等等。在某些具體問題中，蟻群算法的性能更是達到乃至超越了用于該問題的其它經(jīng)典的求解算法。　　國內(nèi)在最近幾年也掀起了一股研究蟻群算法的熱潮，與蟻群算法相關(guān)的學術(shù)著作層出不窮，算法的應(yīng)用領(lǐng)域得到了不斷的拓廣，算法的性能也得到了不斷的提高。

11、</p><p>　　在工業(yè)社會的實際應(yīng)用領(lǐng)域，蟻群算法的成功正引起了國際上眾多企業(yè)的關(guān)注。EuroBios公司首先把蟻群算法應(yīng)用于求解現(xiàn)實世界中不同類型的調(diào)度問題。同時，AntOptima公司以蟻群算法為工具，成功地開發(fā)出多種工業(yè)優(yōu)化的軟件工具，例如DYVOIL產(chǎn)品成功地解決了瑞士某企業(yè)的車輛燃油分配管理問題；ANTROUTE產(chǎn)品則解決了一些大型連鎖超市集團企業(yè)的運輸車輛調(diào)度與路由問題。此外，國外的企業(yè)還把蟻群

12、算法應(yīng)用于大型制造商生產(chǎn)線的設(shè)計、平衡的規(guī)劃、水利設(shè)施的建設(shè)、數(shù)據(jù)挖掘、金融現(xiàn)金流的分析與預(yù)測等廣泛的實際應(yīng)用領(lǐng)域。</p><p>　　蟻群算法在通信網(wǎng)絡(luò)領(lǐng)域（特別是解決網(wǎng)絡(luò)領(lǐng)域問題）的應(yīng)用受到越來越多的學者的關(guān)注。網(wǎng)絡(luò)信息的分布式性、動態(tài)性、隨機性和異步性與蟻群算法非常相似，如利用局部信息發(fā)現(xiàn)解，間接地通訊方式和隨機狀態(tài)的轉(zhuǎn)換。在網(wǎng)絡(luò)多點路由優(yōu)化方面，已經(jīng)取得了不錯的進展。Di Caro和Dorigo已經(jīng)在相

13、關(guān)文獻中將蟻群算法應(yīng)用于網(wǎng)絡(luò)路由問題，并稱這種算法為AntNet。根據(jù)網(wǎng)絡(luò)的不同特點以及路由算法的不同，研究人員提出了各種改進的蟻群算法，提高了算法的性能和在實際中的應(yīng)用價值。例如，在傳感器網(wǎng)絡(luò)中，充分考慮了網(wǎng)絡(luò)能量有限的特點，提出了ACRA算法，提高了網(wǎng)絡(luò)的壽命；高程ACS算法提高了算法的質(zhì)量和收斂速度，引入螞蟻回退機制則使得所有螞蟻都能到達目的節(jié)點；最大-最小螞蟻系統(tǒng)為信息素設(shè)置上下限避免了算法出現(xiàn)停滯的現(xiàn)象；基于混沌蟻群算法的路由

14、模型，降低了時間復雜度，避免了蟻群算法陷入局部最優(yōu)解。此外，還有利用遺傳算法和蟻群算法的融合算法進行路由優(yōu)化算法，WDM網(wǎng)絡(luò)中基于較少波長的組播路由優(yōu)化算法等。　　但是蟻群算法的研究時間不是很長，還沒有形成系統(tǒng)的分析方法和具有堅實的數(shù)學理論基礎(chǔ)。參數(shù)的選擇更多的是依靠實驗和經(jīng)驗．</p><p>　　1.3 本課題要研究與解決的問題</p><p>　　本課題首先要研究基于兩種不同路由算

15、法的路由協(xié)議：基于距離矢量算法的RIP協(xié)議和基于鏈路狀態(tài)算法的OSPF協(xié)議，其中重點學習OSPF協(xié)議的具體工作過程及其特點。</p><p>　?。?）本課題將詳細探討蟻群算法基本原理、蟻群優(yōu)化的一般過程、SACO算法以及其改進算法。我們知道，使用OSPF協(xié)議的路由器在工作過程中首先是通過發(fā)送Hello報文等方法與其他路由器建立連接并交換信息（包括鏈路狀態(tài)、可達信息等），利用Dijkstra算法構(gòu)造出網(wǎng)絡(luò)的拓撲結(jié)

16、構(gòu)，尋找最短路徑。然而網(wǎng)絡(luò)是動態(tài)的，它的拓撲結(jié)構(gòu)、流量隨時變化，不同鏈路的帶寬、時延也不相同，我們希望能找到一種更快速有效的優(yōu)化算法，以適應(yīng)這種動態(tài)的、復雜的網(wǎng)絡(luò)，提高網(wǎng)絡(luò)的效率。蟻群算法給我們提供了一條很好的思路，它最初的提出正是用于尋找最短路徑問題。</p><p>　　在本課題的研究過程中，我們首先不考慮其他鏈路狀態(tài)的因素，將最優(yōu)路徑問題簡化為僅僅是與中間路由器跳數(shù)有關(guān)的最短路徑問題，則利用蟻群算法計算出的

17、最短路徑就是最小跳數(shù)的路徑。</p><p>　　考慮時延等不同代價的最佳路徑，對基本算法做如下改動：根據(jù)每條鏈路信息的不同，考慮時延、帶寬等的作用的大小，給每條鏈路賦予一個不同權(quán)值，在計算路徑長度時乘上權(quán)值（本設(shè)計中為了方便以鏈路的物理長度來代表其時延），修改信息素時加入權(quán)值因素的影響，這樣得出的最優(yōu)路徑即最少開銷的路徑。</p><p>　?。?）最后，編寫出相應(yīng)的軟件，進行計算機仿真

18、，找出不同代價下的最佳路徑，實現(xiàn)多點路由優(yōu)化。</p><p>　　2 路由選擇的基本概念</p><p><b>　　2.1 路由技術(shù)</b></p><p>　　路由技術(shù)其實是由兩項最基本的活動組成，即決定最優(yōu)路徑和傳送數(shù)據(jù)包。其中，數(shù)據(jù)包的傳送相對較為簡單和直接，而路徑的確定則更加復雜一些。路由算法在路由表中寫入各種不同的信息，路由器會根

19、據(jù)數(shù)據(jù)包所要到達的目的地，選擇最佳路徑把數(shù)據(jù)包發(fā)送到可以到達該目的地的下一臺路由器處。路由器之間可以進行相互通信，它們通過傳送不同類型的路由更新信息來維護各自的路由表。路由更新信息一般是由部分或全部路由表組成。通過分析其他路由器發(fā)出的路由更新信息，路由器可以掌握整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。鏈路狀態(tài)廣播是另外一種在路由器之間傳遞的信息，它可以把信息發(fā)送方的鏈路狀態(tài)及時的通知給其他路由器。</p><p>　　路由器要實現(xiàn)數(shù)

20、據(jù)轉(zhuǎn)發(fā)的功能，至少要完成兩方面的內(nèi)容：①根據(jù)數(shù)據(jù)包的目的地址和網(wǎng)絡(luò)拓撲選擇一條最佳路徑，把對應(yīng)不同目的地址的最佳路徑在路由表中；②搜索路由表，決定向哪個端口轉(zhuǎn)發(fā)數(shù)據(jù)，并執(zhí)行相應(yīng)的操作。在上面的兩方面工作中，前者是選擇策略問題，而后者是選路機制問題。</p><p>　　選路策略的實質(zhì)就是如何確定數(shù)據(jù)傳送的最佳路徑，它是通過建立和維護路由表來實現(xiàn)的。選路策略的不同，從本質(zhì)上講就是建立和維護路由表的方式不同。事實上，

21、無論是靜態(tài)路由選擇還是各種動態(tài)路由選擇協(xié)議，它們都是圍繞選路策略站開的。選路機制實質(zhì)上就是如何查找路由表，并根據(jù)查表的結(jié)果把數(shù)據(jù)轉(zhuǎn)發(fā)出去。一般來說，路由器首先搜索匹配的主機地址，如果沒有，再搜索匹配的網(wǎng)絡(luò)地址（可能需要子網(wǎng)掩碼），最后搜索默認路由。一旦查到匹配表項，路由器就會把數(shù)據(jù)從相應(yīng)的接口發(fā)送出去。在具體查找路由表時，可以使用不同的算法，常見的路由查詢算法有二進制Trie樹算法、路徑壓縮Trie樹算法、多分支Trie樹算法、基于前綴

22、長度空間的二分查找法、基于地址區(qū)間的二分查找法以及基于硬件的TCAM機制等。衡量這些算法的指標包括時間復雜度（即查表的速度）、空間復雜度（路由表占用內(nèi)存的大?。㈩A(yù)處理和更新速度（增加、刪除、變更路由表條目時，路由表的更新速度）、可擴展性等。路由查詢算法的好壞直接影響路由查詢的效率。一般來說，很難有哪算法可以同時在上述幾個指標上達到最優(yōu)。選路策略只影響路由表的內(nèi)容，比如對同一個目的IP地址來說，由于選路策略的不</p>&

23、lt;p>　　2.2 路由選擇算法</p><p>　　路由選擇算法是指路由器獲得對網(wǎng)絡(luò)拓撲結(jié)構(gòu)的認知，并為數(shù)據(jù)包選擇正確的傳輸路徑的方法或者策略[2]。一個理想的路由選擇算法至少應(yīng)該具備以下幾點特征：①完整性和正確性，即每個路由器中的路由表都必須給出到所有可能目的節(jié)點的下一跳該怎么走，且給出的走法是正確的；②簡單性，即路由選擇的計算不應(yīng)使網(wǎng)絡(luò)的通信量增加太多額外的開銷；③健壯性，主要指當某些節(jié)點、鏈路出現(xiàn)

24、故障不能工作，或故障恢復后投入運行，算法能及時改變路由；④公平性，即算法對所有用戶都是公平的；⑤最佳性，即以最低的成本實現(xiàn)路由算法。為了降低數(shù)據(jù)包在網(wǎng)絡(luò)中的傳輸開銷和時延，要求為數(shù)據(jù)選擇的路徑是最短的。這里的“最短”在不同場合有著不同的含義，它可以是跳數(shù)的多少，物理距離的長短或者時延的大小等。互聯(lián)網(wǎng)中使用的各種路由選擇協(xié)議或者算法，其根本目的就是尋找源節(jié)點和目的節(jié)點之間最短的一條路徑，即最短路由。</p><p>

25、;　　路由算法的分類標準很多。按照能否根據(jù)網(wǎng)絡(luò)狀況的變化而動態(tài)調(diào)整可以分為靜態(tài)（非自適應(yīng)）和動態(tài)（自適應(yīng)）兩大類；按照工作的模式可以分為集中式和分布式兩大類，前者由路由控制中心集中收集網(wǎng)絡(luò)拓撲結(jié)構(gòu)信息并計算路由，后者由網(wǎng)絡(luò)中所有路由器通過交換路由信息，各自獨立的計算路由?；ヂ?lián)網(wǎng)的復雜性使得當前使用的路由算法主要是動態(tài)的、分布式的。目前互聯(lián)網(wǎng)上的動態(tài)路由協(xié)議主要基于兩種動態(tài)分布式路由選擇算法：距離矢量路由算法和鏈路狀態(tài)路由算法。</

26、p><p>　　2.2.1 距離矢量路由算法</p><p>　　距離矢量路由算法的基礎(chǔ)是分布式的B—F算法。在距離矢量路由中，各個路由器都維持一個距離矢量表，對每個目的節(jié)點都有一個對應(yīng)的表項，包括兩部分內(nèi)容：到該目的節(jié)點最短路徑上的下一個路由器；到該目的節(jié)點的最短路徑長度。在工作時，路由器周期性地和相鄰的路由器交換路由表中的信息，即向鄰居路由器發(fā)送路由表的全部或部分。這種信息是由若干（v，d

27、）對組成的表項，其中，v代表矢量，指出該路由器可以達到的目的地；d表示去往目的地v的距離。各個路由器根據(jù)收到的信息，按照分布式B—F算法重新計算到各目的節(jié)點的距離，并對自己的路由表進行修正。這種一步一步的處理使得每一個路由器都可以知道其他路由器的情況，并形成關(guān)于網(wǎng)絡(luò)“距離”的累積透視圖。</p><p>　　2.2.2 鏈路狀態(tài)路由算法</p><p>　　鏈路狀態(tài)路由算法也被稱為最短路徑

28、優(yōu)先SPF算法，它的提出主要是為了克服距離矢量路由算法所存在的收斂速度慢，難以適應(yīng)大型網(wǎng)絡(luò)等缺陷。</p><p>　　鏈路狀態(tài)路由算法的基本步驟如下：</p><p>　?。?）每一個路由器啟動后，首先執(zhí)行對相鄰節(jié)點的發(fā)現(xiàn)工作，并獲得它們的地址，這個過程在具體實施時是通過發(fā)送特殊的Hello分組實現(xiàn)的；</p><p>　?。?）各路由器主動測試到每一個相鄰路由器

29、的鏈路時延或成本，并根據(jù)測試結(jié)果設(shè)置相關(guān)的鏈路的狀態(tài)；</p><p>　?。?）各路由器構(gòu)造自己的L—S（鏈路狀態(tài)）信息包，L—S信息的內(nèi)容包括本路由器的標號、本路由器的鄰居路由器的鏈路狀態(tài)、該L—S信心包的序號和生存時間等；</p><p>　?。?）各路由器向所有參與SPF的路由器廣播其L—S信息，可以周期性地發(fā)送，也可以在鏈路狀態(tài)發(fā)生變化時發(fā)送；</p><p&

30、gt;　　（5）每個路由器的收聽到所有的L—S信息后，可以構(gòu)造或更新表示整個網(wǎng)絡(luò)拓撲結(jié)構(gòu)的圖G（V，E），頂點V表示路由器，邊E表示連接路由器的鏈路，這時路由器就可以用Dijkstra算法從圖G中計算出到所有目的路由器的最短路徑，也就是構(gòu)造以自己為根節(jié)點的SPF樹。</p><p>　　對比距離矢量路由算法和鏈路狀態(tài)路由算法，總結(jié)它們各自特點如下：距離矢量路由算法實現(xiàn)簡單，對路由器處理能力要求不高，但收斂速度慢，

31、適用于規(guī)模較小和拓撲結(jié)構(gòu)變化不快的網(wǎng)絡(luò)；鏈路狀態(tài)路由選擇算法能夠及時反映網(wǎng)絡(luò)拓撲結(jié)構(gòu)的變化，收斂速度很快，適應(yīng)于規(guī)模較大和拓撲變化較快的網(wǎng)絡(luò)，但由于每一個路由器均需要實時形成全網(wǎng)的拓撲圖及構(gòu)造以自己為節(jié)點的樹，所以對處理器性能要求比較高，另外，路由信息是以廣播的形式傳播的，占用的網(wǎng)絡(luò)帶寬比較多。</p><p><b>　　2.3 路由協(xié)議</b></p><p>　

32、　路由協(xié)議可以分為內(nèi)部網(wǎng)關(guān)協(xié)議IGP和外部網(wǎng)關(guān)協(xié)議EGP兩大類。簡單的定義是，內(nèi)部網(wǎng)關(guān)協(xié)議是用于自治系統(tǒng)內(nèi)部的動態(tài)路由協(xié)議，包括RIP、OSPF等；而外部網(wǎng)關(guān)協(xié)議是用于自治系統(tǒng)之間的拓撲信息交換的路由協(xié)議，包括BGP等。本設(shè)計將基于OSPF協(xié)議，下面將詳細討論該協(xié)議。</p><p>　　開放最短路徑優(yōu)先協(xié)議OSPF[17]是一種基于區(qū)域（路由域）實現(xiàn)的、建立在Dijkstra算法和鏈路狀態(tài)算法基礎(chǔ)之上的內(nèi)部網(wǎng)關(guān)

33、動態(tài)路由協(xié)議。最初提出OSPF主要目的是為了距離矢量路由協(xié)議RIP等所存在的收斂速度慢、采用固定度量以及不能動態(tài)負荷平衡等缺陷。目前OSPF由于其優(yōu)異的性能，已經(jīng)成為應(yīng)用最廣泛的內(nèi)部網(wǎng)關(guān)協(xié)議之一。</p><p>　　OSPF的基本思想如下：</p><p>　　每個OSPF路由器都維護一個用于跟蹤網(wǎng)絡(luò)狀態(tài)的鏈路狀態(tài)數(shù)據(jù)庫（Link State Data-Base ，LSDB)。數(shù)據(jù)庫中的

34、內(nèi)容是反映路由器狀態(tài)的各種鏈路狀態(tài)通告（Link State Advertisement，LSA），這些狀態(tài)包括路由器可用接口、已知可達路由和鏈路狀態(tài)信息，各OSPF路由器都會主動測試所有與之相鄰的路由器的狀態(tài)，并根據(jù)測試結(jié)果設(shè)置相關(guān)鏈路狀態(tài)。利用LSDB，路由器就可以得到一張整個網(wǎng)絡(luò)拓撲結(jié)構(gòu)的圖。在圖論中,OSPF計算出的路由也是一種無環(huán)路的路由?為了減小路由器的LSDB，不同的LSA又有不同的作用范圍，這就使得OSPF具有一定的路由

35、層次性。這種路由層次性是用劃分區(qū)域的方法來實現(xiàn)的。OSPF的管理距離是110。最佳路徑的度量有：①路徑長度—它是最常用的路由度量，一般定義為跳數(shù)，即從源端到目的端所經(jīng)過的路由器個數(shù)；②可靠性—在路由算法中指網(wǎng)絡(luò)鏈接的可依賴性，有些網(wǎng)絡(luò)鏈接可能比其他的失效的更多，網(wǎng)絡(luò)失效后，一些網(wǎng)路鏈接可能比其他的更容易或更快修復，通常是網(wǎng)管給網(wǎng)絡(luò)鏈接賦以度量值；③時延—路由時延指分組從源端到達目的端所花時間，影響時延的因素有中間的網(wǎng)絡(luò)鏈接的帶寬<

36、/p><p>　　（2） OSPF基于Dijkstra算法和自治系統(tǒng)中路由器的鏈路狀態(tài)進行路由計算。路由器在計算路由表時要借助于Dijkstra算法建立起來的最短路徑樹。路由器把自己作為樹根，用該樹跟蹤系統(tǒng)中每個目標的最短路徑，并由此計算出區(qū)域內(nèi)路由；接著，通過查看區(qū)域間LSA計算到自治系統(tǒng)內(nèi)部其他區(qū)域目的地的路由；最后，檢查自治系統(tǒng)外部LSA，計算到自治系統(tǒng)外部目的地的路由。路由表更新通過LSA發(fā)送給在同一個路由域

37、內(nèi)的所有其他路由器。</p><p>　　OSPF協(xié)議工作過程：</p><p>　　OSPF的工作過程可以分為三個互相關(guān)聯(lián)的主要部分：稱為“呼叫”（Hello）協(xié)議、近鄰關(guān)系建立和“可靠洪泛”機制。呼叫協(xié)議、近鄰關(guān)系建立和可靠洪泛機制完成了OSPF包的交互過程，并最終實現(xiàn)同一個路由域中所有路由器的LSDB一致。與RIP等路由協(xié)議不同，OSPF的各類報文都是直接封裝在IP報文中的，不需要使

38、用傳輸層協(xié)議（TCP、UDP等）的支持。OSPF有五種報文：Hello報文（發(fā)現(xiàn)及維持鄰居關(guān)系，選舉DR，BDR）、DD報文（本地LSDB的摘要）、</p><p>　　LSR報文（向?qū)Χ苏埱蟊径藳]有或?qū)Χ说母碌腖SA)、LSU報文（向?qū)Ψ桨l(fā)送其需要的LSA）、LSAck報文（收到LSU之后，進行確認）。</p><p>　　OSPF路由協(xié)議針對每一個區(qū)域分別運行一套獨立的計算法則，對于

39、ABR來說，由于一個區(qū)域邊界路由器同時與幾個區(qū)域相聯(lián)，因此一個區(qū)域邊界路由器上會同時運行幾套OSPF計算方法，每一個方法針對一個OSPF區(qū)域。下面對OSPF協(xié)議運算的全過程作一概括性的描述。 </p><p>　　當一個OSPF路由器初始化時，首先初始化路由器自身的協(xié)議數(shù)據(jù)庫，然后等待低層次協(xié)議（數(shù)據(jù)鏈路層）提示端口是否處于工作狀態(tài)。</p><p>　　如果低層協(xié)議得知一個端口處于工作狀

40、態(tài)時，OSPF會通過其Hello協(xié)議數(shù)據(jù)包與其余的OSPF路由器建立交互關(guān)系。一個OSPF路由器向其相鄰路由器發(fā)送Hello數(shù)據(jù)包，如果接收到某一路由器返回的Hello數(shù)據(jù)包，則在這兩個OSPF路由器之間建立起OSPF交互關(guān)系，這個過程在OSPF中被稱為adjacency。在廣播性網(wǎng)絡(luò)或是在點對點的網(wǎng)絡(luò)環(huán)境中，OSPF協(xié)議通過Hello數(shù)據(jù)包自動地發(fā)現(xiàn)其相鄰路由器，在這時，OSPF路由器將Hello數(shù)據(jù)包發(fā)送至一特殊的多點廣播地址，該多

41、點廣播地址為ALLSPFRouters。在一些非廣播性的網(wǎng)絡(luò)環(huán)境中，我們需要經(jīng)過某些設(shè)置來發(fā)現(xiàn)OSPF相鄰路由器。在多接入的環(huán)境中，例如以太網(wǎng)的環(huán)境，Hello協(xié)議數(shù)據(jù)包還可以用于選擇該網(wǎng)絡(luò)中的指定路由器DR。</p><p>　　一個OSPF路由器會與其新發(fā)現(xiàn)的相鄰路由器建立OSPF的adjacency，并且在一對OSPF路由器之間作鏈路狀態(tài)數(shù)據(jù)庫的同步。在多接入的網(wǎng)絡(luò)環(huán)增中，非DR的OSPF路由器只會與指定路

42、由器DR建立adjacency，并且作數(shù)據(jù)庫的同步。OSPF協(xié)議數(shù)據(jù)包的接收及發(fā)送正是在一對OSPF的adjacency間進行的。</p><p>　　OSPF路由器周期性地產(chǎn)生與其相聯(lián)的所有鏈路的狀態(tài)信息，有時這些信息也被稱為鏈路狀態(tài)廣播LSA（Link State Advertisement）。當路由器相聯(lián)接的鏈路狀態(tài)發(fā)生改變時，路由器也會產(chǎn)生鏈路狀態(tài)廣播信息，所有這些廣播數(shù)據(jù)是通過Flood的方式在某一個O

43、SPF區(qū)域內(nèi)進行的。Flooding算法是一個非?？煽康挠嬎氵^程，它保證在同一個OSPF區(qū)域內(nèi)的所有路由器都具有一個相同的OSPF數(shù)據(jù)庫。根據(jù)這個數(shù)據(jù)庫，OSPF路由器會將自身作為根，計算出一個最短路徑樹，然后，該路由器會根據(jù)最短路徑樹產(chǎn)生自己的OSPF路由表。</p><p>　　OSPF路由協(xié)議通過建立交互關(guān)系來交換路由信息，但是并不是所有相鄰的路由器會建立OSPF交互關(guān)系。下面將OSPF建立adjacenc

44、y的過程簡要介紹一下。</p><p>　　OSPF協(xié)議是通過Hello協(xié)議數(shù)據(jù)包來建立及維護相鄰關(guān)系的，同時也用其來保證相鄰路由器之間的雙向通信。OSPF路由器會周期性地發(fā)送Hello數(shù)據(jù)包，當這個路由器看到自身被列于其它路由器的Hello數(shù)據(jù)包里時，這兩個路由器之間會建立起雙向通信。在多接入的環(huán)境中，Hello數(shù)據(jù)包還用于發(fā)現(xiàn)指定路由器DR，通過DR來控制與哪些路由器建立交互關(guān)系。</p>&l

45、t;p>　　兩個OSPF路由器建立雙向通信這后的第二個步驟是進行數(shù)據(jù)庫的同步，數(shù)據(jù)庫同步是所有鏈路狀態(tài)路由協(xié)議的最大的共性。在OSPF路由協(xié)議中，數(shù)據(jù)庫同步關(guān)系僅僅在建立交互關(guān)系的路由器之間保持。</p><p>　　OSPF的數(shù)據(jù)庫同步是通過OSPF數(shù)據(jù)庫描述數(shù)據(jù)包（Database Des cription Packets）來進行的。OSPF路由器周期性地產(chǎn)生數(shù)據(jù)庫描述數(shù)據(jù)包，該數(shù)據(jù)包是有序的，即附帶有

46、序列號，并將這些數(shù)據(jù)包對相鄰路由器廣播。相鄰路由器可以根據(jù)數(shù)據(jù)庫描述數(shù)據(jù)包的序列號與自身數(shù)據(jù)庫的數(shù)據(jù)作比較，若發(fā)現(xiàn)接收到的數(shù)據(jù)比數(shù)據(jù)庫內(nèi)的數(shù)據(jù)序列號大，則相鄰路由器會針對序列號較大的數(shù)據(jù)發(fā)出請求，并用請求得到的數(shù)據(jù)來更新其鏈路狀態(tài)數(shù)據(jù)庫。</p><p>　　我們可以將OSPF相鄰路由器從發(fā)送Hello數(shù)據(jù)包，建立數(shù)據(jù)庫同步至建立完全的OSPF交互關(guān)系的過程分成幾個不同的狀態(tài)，分別為：</p>&l

47、t;p>　　Down：這是OSPF建立交互關(guān)系的初始化狀態(tài)，表示在一定時間之內(nèi)沒有接收到從某一相鄰路由器發(fā)送來的信息。在非廣播性的網(wǎng)絡(luò)環(huán)境內(nèi)，OSPF路由器還可能對處于Down狀態(tài)的路由器發(fā)送Hello數(shù)據(jù)包。</p><p>　　Attempt：該狀態(tài)僅在NBMA環(huán)境，例如幀中繼、X.25或ATM環(huán)境中有效，表示在一定時間內(nèi)沒有接收到某一相鄰路由器的信息，但是OSPF路由器仍必須通過以一個較低的頻率向該相

48、鄰路由器發(fā)送Hello數(shù)據(jù)包來保持聯(lián)系。</p><p>　　Init：路由器的各個接口發(fā)送Hello數(shù)據(jù)報文到其他運行OSPF的路由器，當鄰接路由器收到第一個Hello數(shù)據(jù)報文，這時就進入Init狀態(tài)。在該狀態(tài)時，OSPF路由器已經(jīng)接收到相鄰路由器發(fā)送來的Hello數(shù)據(jù)包，但自身的IP地址并沒有出現(xiàn)在該Hello數(shù)據(jù)包內(nèi)，也就是說，雙方的雙向通信還沒有建立起來。</p><p>　　2-

49、Way：這個狀態(tài)可以說是建立交互方式真正的開始步驟。在這個狀態(tài)，路由器看到自身已經(jīng)處于相鄰路由器的Hello數(shù)據(jù)包內(nèi)，雙向通信已經(jīng)建立。指定路由器及備份指定路由器的選擇正是在這個狀態(tài)完成的。在這個狀態(tài)，OSPF路由器還可以根據(jù)其中的一個路由器是否指定路由器或是根據(jù)鏈路是否點對點或虛擬鏈路來決定是否建立交互關(guān)系。</p><p>　　Exstart：這個狀態(tài)是建立交互狀態(tài)的第一個步驟。在這個狀態(tài)，路由器要決定用于數(shù)

50、據(jù)交換的初始的數(shù)據(jù)庫描述數(shù)據(jù)包的序列號，以保證路由器得到的永遠是最新的鏈路狀態(tài)信息。同時，在這個狀態(tài)路由器還必須決定路由器之間的主備關(guān)系，處于主控地位的路由器會向處于備份地位的路由器請求鏈路狀態(tài)信息。</p><p>　　Exchange：在這個狀態(tài)，路由器向相鄰的OSPF路由器發(fā)送數(shù)據(jù)庫描述數(shù)據(jù)包來交換鏈路狀態(tài)信息，每一個數(shù)據(jù)包都有一個數(shù)據(jù)包序列號。在這個狀態(tài)，路由器還有可能向相鄰路由器發(fā)送鏈路狀態(tài)請求數(shù)據(jù)包來

51、請求其相應(yīng)數(shù)據(jù)。從這個狀態(tài)開始，我們說OSPF處于Flooding狀態(tài)。</p><p>　　Loading：在loading狀態(tài)，OSPF路由器會就其發(fā)現(xiàn)的相鄰路由器的新的鏈路狀態(tài)數(shù)據(jù)及自身的已經(jīng)過期的數(shù)據(jù)向相鄰路由器提出請求，并等待相鄰路由器的回答。</p><p>　　Full：這是兩個OSPF路由器建立交互關(guān)系的最后一個狀態(tài)，在這時，建立起交互關(guān)系的路由器之間已經(jīng)完成了數(shù)據(jù)庫同步的

52、工作，它們的鏈路狀態(tài)數(shù)據(jù)庫已經(jīng)一致，這個狀態(tài)稱為“全毗鄰狀態(tài)”，每臺路由器保存著一張毗鄰路由器列表稱為“毗鄰數(shù)據(jù)庫”。兩個OSPF路由器數(shù)據(jù)庫同步是所有鏈路狀態(tài)路由協(xié)議的最大共性。在OSPF路由協(xié)議中，數(shù)據(jù)庫同步關(guān)系僅僅建立在交互關(guān)系的路由器之間保存。</p><p>　　OSPF協(xié)議的優(yōu)點：</p><p>　　（1）OSPF是真正的LOOP- FREE(無路由自環(huán))路由協(xié)議?源自其算法

53、本身的優(yōu)點?(鏈路狀態(tài)及最短 路徑樹算法)</p><p>　?。?）OSPF收斂速度快:能夠在最短的時間內(nèi)將路由變化傳遞到整個自治系統(tǒng)?</p><p>　?。?）提出區(qū)域(area)劃分的概念,將自治系統(tǒng)劃分為不同區(qū)域后,通過區(qū)域之間的對路由信息的摘要,大大減少了需傳遞的路由信息數(shù)量?也使得路由信息不會隨網(wǎng)絡(luò)規(guī)模的擴大而急劇膨脹?</p><p>　　（4）將協(xié)

54、議自身的開銷控制到最小?</p><p>　　1)用于發(fā)現(xiàn)和維護鄰居關(guān)系的是定期發(fā)送的是不含路由信息的hello報文,非常短小?包含路由信息的報文時是觸發(fā)更新的機制?(有路由變化時才會發(fā)送)?但為了增強協(xié)議的健壯性,每1800秒全部重發(fā)一次?</p><p>　　2)在廣播網(wǎng)絡(luò)中,使用組播地址(而非廣播)發(fā)送報文,減少對其它不運行ospf 的網(wǎng)絡(luò)設(shè)備的干擾?</p><

55、p>　　3)在各類可以多址訪問的網(wǎng)絡(luò)中(廣播,NBMA),通過選舉DR,使同網(wǎng)段的路由器之間的路由交換(同步)次數(shù)由 O(N*N)次減少為 O (N)次?</p><p>　　4)提出STUB區(qū)域的概念,使得STUB區(qū)域內(nèi)不再傳播引入的ASE路由?</p><p>　　5)在ABR(區(qū)域邊界路由器)上支持路由聚合,進一步減少區(qū)域間的路由信息傳遞?</p><p&g

56、t;　　6)在點到點接口類型中,通過配置按需播號屬性(OSPF over On Demand Circuits),使得ospf不再定時發(fā)送hello報文及定期更新路由信息?只在網(wǎng)絡(luò)拓撲真正變化時才發(fā)送更新信息?</p><p>　　（5）通過嚴格劃分路由的級別(共分四極),提供更可信的路由選擇?</p><p>　?。?）良好的安全性,ospf支持基于接口的明文及md5 驗證?</p

57、><p>　?。?）OSPF適應(yīng)各種規(guī)模的網(wǎng)絡(luò),最多可達數(shù)千臺?</p><p><b>　　3 蟻群算法</b></p><p>　　3.1 蟻群優(yōu)化的原理分析</p><p>　　AC O是受自然界中真實蟻群的集體覓食行為的啟發(fā)而發(fā)展起來的一種基于群體的模擬進化算法，屬于隨機搜索算法。M.Dorigo等人充分利用了蟻群搜

58、索食物的過程與著名TSP問題之間的相似性，通過人工模擬蟻群搜索食物的行為來求解TSP問題。從下面的的“雙橋?qū)嶒灐笨梢钥闯?，像螞蟻這類社會性動物，雖然個體的行為極其簡單，但由這些簡單個體所組成的蟻群卻表現(xiàn)出極其復雜的行為特征。如蟻群除了能夠找到蟻巢與食物源之間的最短路徑外，還能適應(yīng)環(huán)境的變化，即在蟻群運動的路線上突然出現(xiàn)障礙物時，螞蟻能夠很快地重新找到最短路徑。蟻群是如何完成這些復雜任務(wù)的呢?仿生學家經(jīng)過大量地觀察、研究發(fā)現(xiàn)，螞蟻在尋找食

59、物時，能在其經(jīng)過的路徑上釋放一種螞蟻特有的分泌物一外激素，使得一定范圍內(nèi)的其它螞蟻能夠感覺到這種物質(zhì)，且傾向于朝著該物質(zhì)強度高的方向移動。因此，蟻群的集體行為表現(xiàn)為一種信息正反饋現(xiàn)象:某條路徑匕經(jīng)過的螞蟻數(shù)越多，其上留下的外激素的跡也就越多(當然，隨時間的推移會逐漸蒸發(fā)掉一部分)，后來螞蟻選擇該路徑的概率也越高，從而更增了該路徑上外激素的強度。蟻群這種選擇路徑的過程被稱之為自催化行為，由于其原理是一種正反饋機制，因</p>

60、<p>　　接下來簡單解釋一下蟻群發(fā)現(xiàn)最短路徑的原理和機制。</p><p>　　在蟻巢和實物之間有兩條道路，Nest-A-B-D-Food和Nest-A-C-D-Food，其長度分別為4和6。單位時間內(nèi)螞蟻可移動一個單位長度的距離。開始時所有路徑上都沒有外激素。</p><p>　　在t=0時刻，20只螞蟻從蟻巢出發(fā)移動到A。由于路徑上沒有</p><p&

61、gt;　　外激素，它們以相同概率選擇左側(cè)或右側(cè)道路，因此平均有10只螞蟻走左側(cè)，另外10只走右側(cè)。</p><p>　　在t-4時刻，第一組先到達食物源的螞蟻將折回。</p><p>　　在t=5時刻，兩組螞蟻將在D點相遇。此時BD上的外激素數(shù)量與CD上的相同，因此返回的10只螞蟻中有5只選擇BD而另5只選擇CD.</p><p>　　在t-S時刻，前5個螞蟻將返回

62、巢穴，而在AC.C D和AB上各有5個螞蟻。</p><p>　　在t=9時刻，前5個螞蟻又回到A并且再次面對往左還是往右的選擇這時，AB上的軌跡數(shù)是20而AC上是15，因此將有較為多數(shù)的螞蟻選擇往右，從而增強了AB上外激素的量。隨著該過程的繼續(xù)，兩條道路上外激素數(shù)量的差距將越來越大，直至絕大多數(shù)螞蟻都選擇了最短的路徑。正是由于一條道路要比另一條道路短，因此，在相同的時間間隔內(nèi)，短的路線會有更多的機會被選則。&l

63、t;/p><p>　　3.2 簡單蟻群優(yōu)化SACO</p><p>　　介紹蟻群算法前我們首先來介紹以下雙橋?qū)嶒灒?lt;/p><p>　　在該實驗中，巢穴和食物之間用等長度的雙分支橋連接。最初橋的兩個分支都沒有任何信息素，過了一段時間之后，盡管這兩個分支長度相等，還是有一個分支被絕大多數(shù)螞蟻所選擇。原因是隨機的路徑選擇促使所隨機選擇到的分支上信息素濃度積累。通過該實驗，研

64、究人員建立了一個形式化的模型來描述螞蟻選擇路徑的過程。建模過程中，他們假設(shè)各螞蟻分泌等量的信息素且不考慮信息素的揮發(fā)，得出螞蟻在t+1時刻選擇路徑A的概率如下所示（其中和分別表示在t時刻路徑A、路徑B上所經(jīng)過的螞蟻數(shù)量）</p><p><b>　　（3.1）</b></p><p>　　式中，c代表未開發(fā)路徑（不含信息素的路徑分支）對螞蟻的吸引度，表示螞蟻選擇路徑的

65、過程中受信息素的影響程度。的值越大，螞蟻選擇高信息素濃度路徑的可能性越大，即便兩條路徑的信息素濃度差別很小。c越大，則需要越高的信息素濃度來影響螞蟻的下一步選擇。實驗表明，當時，該概率模型與實際相符。</p><p>　　我們以常見的尋找圖中兩節(jié)點間最短路徑問題為例，G=（V，E），其中V表示圖節(jié)點的集合，E表示圖中邊的集合。圖中共有個節(jié)點，表示螞蟻k所經(jīng)歷的路徑的長度—兩節(jié)點間跳轉(zhuǎn)邊的數(shù)量。對于每個邊（i，j）

66、，都賦予了相應(yīng)的信息素濃度。</p><p>　　對于SACO[21]來說，每個邊地信息素濃度都被初始化為一個小的隨機值。 嚴格來講，初始時每個邊應(yīng)該不含信息素，螞蟻隨機的選擇路徑。根據(jù)上述算法，給每個邊的信息素濃度一個小的隨機值更容易實現(xiàn)。每個螞蟻k（k=1,2，,）都被置到源節(jié)點。對于SACO的每次迭代，每只螞蟻逐漸建立一條到達終節(jié)點的路徑。在每個節(jié)點，螞蟻都會進行決策選擇下一段路徑。如果螞蟻k當前節(jié)點是i，

67、那么它選擇下一結(jié)點j的概率為</p><p><b>　?。?.2）</b></p><p>　　式中是對于螞蟻k來說，跟節(jié)點i相連接的可選節(jié)點的集合。如果螞蟻k在節(jié)點i時，，那么把節(jié)點i加入到中，這么做會導致路徑中有環(huán)出現(xiàn)，而這些環(huán)將會在形成完整路徑后去除。</p><p>　　上式中是一個正的常量，用于放大信息素濃度的影響。太大的會過度增大

68、信息素的影響，尤其是初期隨機的信息素濃度，從而會導致算法快速收斂到次優(yōu)路徑。</p><p>　　一旦所有螞蟻到達終結(jié)點，并去除了路徑中的環(huán)，每只螞蟻會沿原路徑回到源節(jié)點，并沿途在每個邊（i，j）上釋放一定的信息素，其中是該路徑第t步那段路徑的長度：</p><p><b>　?。?.3）</b></p><p>　　即

69、 （3.4）</p><p>　　式中表示螞蟻的總數(shù)量。</p><p>　　由上式可知，一條邊的信息素濃度跟該邊所在的路徑的優(yōu)良程度成正比—路徑越短越優(yōu)。計算出的所應(yīng)釋放的信息素量代表相應(yīng)的路徑的優(yōu)良度。對于SACO，解（建立的路徑）的優(yōu)良簡單地表示為該路徑的長度（也就是經(jīng)歷的邊地數(shù)量）的倒數(shù)。而其他的測量度同樣適用，比如所經(jīng)歷每條邊所帶來的

70、開銷，或者路徑的物理長度。一般來說，用表示時刻t的解，用f（）表示解的估量。如果不與解的質(zhì)量成比例，且所有的螞蟻釋放相同的信息素量，那么僅僅是路徑的長度影響（短的返回時間造成信息素釋放頻率增大）螞蟻傾向于選擇短路徑。由此我們得出螞蟻算法中兩種形式的解估量：隱式估量（路徑長度的差異造成螞蟻間的相互影響）、顯示估量（信息素的釋放量跟路徑的優(yōu)良程度成正比）。</p><p>　　但是我們應(yīng)該注意到，這種決策信息僅限于螞

71、蟻的局部環(huán)境，SACO適用于簡單圖和螞蟻數(shù)量較少的情況，這樣大多能找到最短路徑。但是當圖較大時，算法變得不魯棒，對參數(shù)敏感，性能較差。此外，對于螞蟻數(shù)目很多的情況，可能導致算法不收斂。</p><p>　　對于復雜的圖來說，信息素的揮發(fā)變得更為重要。當=0時（信息素不揮發(fā)），算法不收斂；當信息素揮發(fā)過多（過大）會導致算法收斂到次優(yōu)路徑。</p><p>　　對于較小的，算法一般可以收斂到最

72、短路徑，對于復雜問題來說，大的會導致更差的收斂性能。</p><p>　　3.3 蟻群算法的主要特點</p><p>　　ACO算法的主要特點概括如下：</p><p>　　1）采用分布式控制，不存在中心控制;</p><p>　　2）每個個體只能感知局部的信息，不能直接使用全局信息;</p><p>　　3）個體可改

73、變環(huán)境，并通過環(huán)境來進行間接通訊(Stigmergy機制);</p><p>　　4）具有自組織性，即群體的復雜行為是通過個體的交互過程中突現(xiàn)出來的智能;</p><p>　　5）是一類概率型的全局搜索方法，這種非確定性使算法能夠有更多的機會求得全局最優(yōu)解 ;</p><p>　　6）其優(yōu)化過程不依賴于優(yōu)化問題本身的嚴格數(shù)學性質(zhì)，諸如連續(xù)性、可導性，及目標函數(shù)和約束

74、函數(shù)的精確數(shù)學描述;</p><p>　　7）是一類基于多主體(MultiA gent)的智能算法，各主體間通過相互協(xié)作來更好的適應(yīng)環(huán)境;</p><p>　　8）具有潛在的并行性，其搜索過程不是從一點出發(fā)，而是同時從多個點同時進行。這種分布式多智能體的協(xié)作過程是異步并發(fā)進行的，分布并行模式將大大提高整個算法的運行效率和快速反應(yīng)能力。</p><p>　　4 基于蟻

75、群算法的網(wǎng)絡(luò)多點路由的優(yōu)化與仿真</p><p>　　4.1 網(wǎng)絡(luò)路由優(yōu)化問題的描述</p><p>　　網(wǎng)絡(luò)是指把某些元件有目的的、按一定形式連接起來、完成特定任務(wù)的總體。從抽象的數(shù)觀點來看，網(wǎng)絡(luò)實質(zhì)上是一個賦權(quán)的有向圖，它由節(jié)點和連接這些節(jié)點的弧及其方向組成。自然界和人類社會中的大量事物及事物之間的相互關(guān)系(例如物質(zhì)結(jié)構(gòu)、城市規(guī)劃、交通運輸、信息的傳遞、工作的調(diào)配、事物關(guān)系等等)都可以

76、用點與線連接起來的網(wǎng)絡(luò)圖來描述。網(wǎng)絡(luò)圖是從實際模型中抽象出來的，因此可以根據(jù)問題的實際需要給弧和節(jié)點賦予一個數(shù)來表明它所對應(yīng)元件的不同物理意義。這個具有特殊意義的數(shù)，我們稱之為節(jié)點或弧的權(quán)。例如，在公路運輸網(wǎng)絡(luò)中，弧的權(quán)可以為路的長度或單位長度的運費；在供水網(wǎng)絡(luò)系統(tǒng)中，弧的權(quán)可以是水流量或水管的直徑；在電網(wǎng)絡(luò)中，弧的權(quán)可以為元件的電阻、電壓或電流等。網(wǎng)絡(luò)最短路徑是在網(wǎng)絡(luò)圖中尋求邊權(quán)和最小的最小路。而網(wǎng)絡(luò)中的這個權(quán)可以是鏈路的帶寬、時延、

77、開銷等，或者它們的綜合。</p><p>　　所謂的網(wǎng)絡(luò)路由優(yōu)化問題是指在一個網(wǎng)絡(luò)中，要求在某些約束條件下找出從節(jié)點A到B之間的最佳路由，即是在某些含義下的最佳路由（即上面所說的加權(quán)最優(yōu)值）。目前已經(jīng)有許多智能化算法，如遺傳算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)等用于網(wǎng)絡(luò)路由優(yōu)化，已取得較好的結(jié)果。</p><p>　　4.2 基于蟻群算法來選擇路由算法的思想的概述</p><p

78、>　　通過前面對蟻群算法和網(wǎng)絡(luò)優(yōu)化問題的研究我們發(fā)現(xiàn)，可以將實際中的路由選擇問題抽象成求最短路徑問題的模型，進而利用蟻群算法求出最佳路徑。該模型如下：</p><p>　　用一種控制報文( 又稱螞蟻) 來搜集路徑信息進行路由選擇。本文用移動代理來模擬螞蟻,分為兩種,即前向螞蟻Fant和后向螞蟻Bant , 并通過移動代理的復雜交互來決定路由。用前向螞蟻（表示從源節(jié)點到目的節(jié)點的移動代理）搜集從源節(jié)點到目的節(jié)

79、點的路徑信息( 包括端到端的延遲、所經(jīng)過的跳數(shù)等);后向螞蟻（表示從目的節(jié)點返回到源節(jié)點的移動代理）據(jù)此來改變所經(jīng)過的各個節(jié)點的路由信息。本文在研究過程中將問題簡化，用端到端所經(jīng)過的跳數(shù)來表示信息素值（時延等可以利用對邊進行權(quán)值的設(shè)定來實現(xiàn)）。將網(wǎng)絡(luò)中各節(jié)點的路由表用用一種概率表表示，其中概率表示信息素強度，即信息素表。 </p><p>　　初始狀態(tài)時，所有路徑上的信息素均勻分布，螞蟻

80、不斷對信息素進行更新，信息素本身也在隨著時間不斷減少。從源點發(fā)送一組螞蟻，按上面的規(guī)則進行移動，螞蟻可以遍歷所有節(jié)點，并且螞蟻能夠記住所經(jīng)過路徑的信息，包括跳數(shù)和時延，并最終到達目的節(jié)點。顯然走路徑短的螞蟻最先到達目的節(jié)點，目的節(jié)點只接收最先到達的螞蟻。最先到達終點的螞蟻（即全局最優(yōu)螞蟻）按原路徑返回，并修改沿途節(jié)點的路由表（信息素表），增大相應(yīng)邊上的信息素濃度（即增大選擇該路徑的概率）。如此不斷地迭代運算，算法將收斂于最短路徑。<

81、;/p><p>　　為了完成建立最優(yōu)路徑的任務(wù)，螞蟻擁有如下屬性和特點：1）螞蟻有記憶功能來保存建立的路徑信息。該記憶主要用于保證滿足約束條件，比如每個節(jié)點只允許訪問一次。該記憶還用于按原路徑返回，來釋放信息素，增強對應(yīng)邊上的信息素濃度。2）螞蟻為每個狀態(tài)決定一些可選的鄰節(jié)點。其中包括所有的從當前節(jié)點有效轉(zhuǎn)移的可達節(jié)點。之后螞蟻進入一個新的狀態(tài)（部分解）。3）每只螞蟻都被分配一個初始狀態(tài)，對應(yīng)初始節(jié)點。4）每只螞蟻都

82、對應(yīng)一個或多個終止條件，終止條件包括路徑達到限定的最大節(jié)點數(shù)、找到可接受的解、或者到達終節(jié)點。5）每只螞蟻依據(jù)概率轉(zhuǎn)移規(guī)則從可選鄰節(jié)點中選取下一結(jié)點。6）每只螞蟻都擁有修改所經(jīng)歷路徑上的信息素濃度的能力，作為與其他螞蟻通信的方式。</p><p>　　4.3 基于蟻群算法的路由優(yōu)化具體過程</p><p>　　螞蟻系統(tǒng)在以下方面改進簡單蟻群優(yōu)化算法：增加啟發(fā)式信息，改變轉(zhuǎn)移概率；增加禁忌表

83、，來增加記憶功能。因此，本課題在研究過程中將采用螞蟻系統(tǒng)算法，并基于OSPF協(xié)議進行路由優(yōu)化。</p><p>　　4.3.1 最優(yōu)路徑的建立</p><p>　　在基于蟻群算法的最優(yōu)路徑建立過程中，每個節(jié)點包含一個緩存器，存放著近學習到的和用過的路由信息。源節(jié)點s要發(fā)送數(shù)據(jù)到目的節(jié)點d，它首先在自己的路由表里查找是否存在一條到d的路由。如果沒有到d的路由信息時，就進行路由發(fā)現(xiàn)過程。具體過

84、程如下:</p><p>　?、?每個節(jié)點初始化連接鄰居節(jié)點鏈路的信息素；</p><p>　　② 源節(jié)點產(chǎn)生m只前向螞蟻；</p><p>　　③ 第k只前向螞蟻所在的當前節(jié)點i首先檢查路由表中是否有到目的節(jié)點d 的路徑，如果有則前向螞蟻單播，否則前向螞蟻按概率選擇其鄰居節(jié)點j，并且在前向螞蟻中插入中間節(jié)點i的編號、地址和路徑信息。節(jié)點i選擇下一跳j的規(guī)則為<

85、;/p><p><b>　　（4.1）</b></p><p>　　式中代表從節(jié)點i移動到節(jié)點j的后驗效應(yīng)，以邊（i，j）上的信息素濃度表示；代表從節(jié)點i移動到節(jié)點j的先驗效應(yīng)，通過啟發(fā)式信息計算得出。信息素濃度表示過去從節(jié)點i到j(luò)移動帶來的影響，是對過去優(yōu)質(zhì)移動的記憶。上式中的轉(zhuǎn)移概率跟SACO有兩方面的不同：</p><p>　　1) 螞蟻系統(tǒng)

86、中的轉(zhuǎn)移概率是在信息素濃度（代表之前較優(yōu)的移動）和啟發(fā)式信息（下一移動的傾向性）之間的平衡。這樣做可以很好的處理探索-開發(fā)之間的關(guān)系。算法的搜索傾向于過去一段時間搜索中較優(yōu)的路徑，從而探索搜索空間以獲取信息。同時，為了發(fā)現(xiàn)類似的優(yōu)質(zhì)路徑，算法會開發(fā)以前未涉及到的路徑。而探索與開發(fā)之間最好的平衡是通過調(diào)節(jié)參數(shù)得到的。當時，將不會利用信息素信息，也就是忽略之前的搜索經(jīng)驗。搜索降級為隨機貪心搜索。當時，下一節(jié)點的吸引性將被忽略，算法在某些問題

87、上變得跟SACO很相似。</p><p>　　啟發(fā)式信息增加了對有吸引力的解的顯式傾向性，它通常是問題獨立的函數(shù)。比如說對于最小化路徑長度問題，它可以表示為</p><p><b>　?。?.2）</b></p><p>　　式中表示節(jié)點i與節(jié)點j之間的距離或者開銷。</p><p>　　2）集合表示螞蟻k在節(jié)點i可選后

88、續(xù)節(jié)點集合?？蛇x節(jié)點集合可以直接包含節(jié)點i的相鄰節(jié)點?；蛘?，為了避免環(huán)的出現(xiàn)，在中僅包含螞蟻k未訪問過的節(jié)點。為此，為每只螞蟻建立一個禁忌表。當螞蟻訪問一新節(jié)點時，就把該節(jié)點加入到禁忌表中。禁忌表中的節(jié)點將不會被包含在中，確保每個節(jié)點只被訪問一次。</p><p>　?、?中間節(jié)點接收到前向螞蟻后按照③的規(guī)則進行轉(zhuǎn)發(fā),直到前向螞蟻到達目的節(jié)點d停止。中間節(jié)點和目的節(jié)點可能收到同一個前向螞蟻的復制品。此節(jié)點只接收最

89、早到達且跳數(shù)最少的那個前向螞蟻，將其余的丟棄。源節(jié)點到目的節(jié)點的過程中，每個前向螞蟻記錄所訪問過的節(jié)點和所經(jīng)過的每條鏈路上的時延及跳數(shù)，保存在前向螞蟻本身的一個棧中。Bant可據(jù)此信息在返回途中對個節(jié)點的信息素表進行修改，并可根據(jù)節(jié)點的數(shù)目計算出跳數(shù)h。當出現(xiàn)環(huán)路時，即Fant又返回到一個已經(jīng)訪問過的節(jié)點時，則將所有與形成環(huán)路的節(jié)點有關(guān)的信息全部去掉，F(xiàn)ant按相同的概率值在鄰居節(jié)點中選擇一個作為下一跳，以免再次進入環(huán)路；</p&

90、gt;<p>　　⑤ 當Fant到達目的節(jié)點d 后，則轉(zhuǎn)換成后向螞蟻Bant，Bant中包含了Fant收集到的所有的路徑信息。Bant根據(jù)該路徑信息以更高優(yōu)先級按原路路徑返回源節(jié)點i，并根據(jù)時延和跳數(shù)信息在返回途中對每個節(jié)點上的信息素表進行更新。在每個中間節(jié)點i上，Bant可以讀出從該節(jié)點到鄰居節(jié)點的時延，由此可計算出從此節(jié)點經(jīng)其相鄰節(jié)點到達目的節(jié)點的時延和跳數(shù)，據(jù)此信息可以進一步計算信息素增量。后向螞蟻到達源節(jié)點s后一次

91、路由建立過程完畢。信息素的揮發(fā)采用跟SACO相同的形式，當每只螞蟻搜索完一條路徑后，每條邊的信息素進行如下更新：</p><p><b>　?。?.3）</b></p><p><b>　　而：</b></p><p><b>　?。?.4）</b></p><p>　　式中表

92、示螞蟻在時刻在邊（,）上釋放的信息量。Dorigo等人研究出螞蟻系統(tǒng)的三個變種，它們的區(qū)別在于的計算方式（針對最小化問題）。</p><p><b>　?。?）蟻周系統(tǒng)：</b></p><p><b>　?。?.5）</b></p><p>　　對于蟻周系統(tǒng)來說信息素的釋放量，跟螞蟻建立的路徑質(zhì)量成反比。因此，是用全局的

93、信息來更新信息素濃度，Q是正的常量。</p><p><b>　　對于最大化問題：</b></p><p><b>　?。?.6）</b></p><p><b>　　（2）蟻密系統(tǒng)：</b></p><p><b>　?。?.7）</b></p&g

94、t;<p>　　每只螞蟻在建立的路徑邊上相同量的信息素。信息素濃度只跟邊(i,j)上經(jīng)過的螞蟻數(shù)量有關(guān)。邊上經(jīng)過的螞蟻越多，該邊越有可能成為最終路徑的一部分。</p><p><b>　?。?）蟻量系統(tǒng)：</b></p><p><b>　?。?.8）</b></p><p>　　在該情況下，信息素濃度的更新

95、僅僅考慮局部信息，低開銷的路徑更具有吸引性。如果表示邊地長度，那么蟻量系統(tǒng)傾向于選擇最短邊。</p><p>　　在初始化階段，螞蟻的放置根據(jù)問題的特殊性而定。如果目標是在源節(jié)點和目標節(jié)點之間選擇尋找最短路徑，那么將所有只螞蟻放置到源節(jié)點；如果目標是尋找最短哈密頓路徑（一條連接所有節(jié)點僅一次的路徑），那么所有只螞蟻將被隨機放到圖中。把螞蟻放置到隨機選擇的節(jié)點，有利于改進算法的探索能力。信息素值可以初始化為一個常量

96、，或者小的隨機值。</p><p>　　研究人員還提出精英策略—除了有上述的更新信息素策略外，最優(yōu)路徑上的邊信息素被再次增強，增強量正比于最優(yōu)路徑的長度。信息素更新公式變?yōu)椋?lt;/p><p><b>　?。?.9）</b></p><p><b>　　式中：</b></p><p><b>

97、;　?。?.10）</b></p><p>　　e代表精英螞蟻的數(shù)量。表示當前最優(yōu)路徑，而。精英策略目標是引導所有螞蟻在建立解時包含當前最優(yōu)路徑的一些邊。</p><p>　?、?重復上述過程，直到滿足終止條件，包括超過了最大迭代次數(shù)、已經(jīng)建立了一個可接受解、有停滯現(xiàn)象發(fā)生等。在螞蟻找到的路徑中選擇合適的一條或多條路徑(其他的作為備用路徑) 作為路由發(fā)現(xiàn)的最終結(jié)果。</p

98、><p>　　上述算法可描述如下：</p><p>　　Procedure ANT( S, D) / /利用ANT 發(fā)起建立路由過程</p><p><b>　　begin</b></p><p>　　stack <-NULL / /棧stack 為存放Fant訪問過的節(jié)點, 初始時為空</p><

99、p>　　di , j = 0 / /di, j 表示Fant從節(jié)點i 到j(luò) 所需的時延</p><p>　　if 節(jié)點i 需要發(fā)送數(shù)據(jù)then</p><p>　　if 節(jié)點i 存在到達目的節(jié)點的路由</p><p>　　then按照信息素概率高的路由進行數(shù)據(jù)分組轉(zhuǎn)發(fā)</p><p><b>　　else</b>&

100、lt;/p><p><b>　　begin</b></p><p>　　stack <-( S, ds, s ) / /將Fant訪問過的節(jié)點放入棧中</p><p>　　current <-S / / current 為當前Fant所在的節(jié)點</p><p>　　while( current ! = D)<

101、;/p><p><b>　　begin</b></p><p>　　current 向其鄰居節(jié)點廣播Fant</p><p>　　j 1 <-Fant / /鄰居j1 接收到Fant</p><p>　　i <-current / /為Fant 訪問的上一節(jié)點</p><p>　　if s

102、tack 中存在j1 節(jié)點</p><p>　　then將stack 中j1 之后所有節(jié)點彈出</p><p>　　current <-j1</p><p>　　continue / /退出本次循環(huán), 繼續(xù)從j1 向鄰居節(jié)點廣播Fant</p><p><b>　　else</b></p><p

103、>　　stack <-( j1 , di, j1 )</p><p>　　current <-j1</p><p>　　if 節(jié)點j1 存在到達目的節(jié)點的路由</p><p>　　then生成Bant 返向源節(jié)點, 更新路由信息表</p><p><b>　　end if</b></p>

104、<p><b>　　end if</b></p><p><b>　　end while</b></p><p>　　Bant <-Fant / /將Fant搜索到的信息傳送給Bant</p><p>　　Bant按照stack 棧中節(jié)點的次序計算出當前節(jié)點到目的節(jié)點的時延, 并根據(jù)節(jié)點數(shù)計算出跳數(shù), 然后

105、依據(jù)⑤中的規(guī)則更新路由信息表, 直到源節(jié)點</p><p><b>　　end if</b></p><p><b>　　end if</b></p><p><b>　　End</b></p><p>　　4.3.2 路由的維護與更新</p><p>

106、　　經(jīng)過路由初始化過程后，網(wǎng)絡(luò)中存在著一系列保存有“由信息素計算出的路由信息表”的節(jié)點。節(jié)點會按照一定的算法對路由表進行維護和更新。當源節(jié)點發(fā)送數(shù)據(jù)時，多個數(shù)據(jù)包在一條路由上同時傳送。由于網(wǎng)絡(luò)本身寬帶的受限，導致數(shù)據(jù)包發(fā)生擁塞，從而致使現(xiàn)存的路由可能不再是最優(yōu)路由。源節(jié)點在每發(fā)送n個數(shù)據(jù)包的同時，發(fā)送前向螞蟻進行維護與探索。一般來說這些前向螞蟻是單播( unicast) ，它們根據(jù)③中的規(guī)則計算出來的概率選擇下一跳，有時也可能以一定的概