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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、）對(duì)組成的表項(xiàng)，其中，v代表矢量，指出該路由器可以達(dá)到的目的地；d表示去往目的地v的距離。各個(gè)路由器根據(jù)收到的信息，按照分布式B—F算法重新計(jì)算到各目的節(jié)點(diǎn)的距離，并對(duì)自己的路由表進(jìn)行修正。這種一步一步的處理使得每一個(gè)路由器都可以知道其他路由器的情況，并形成關(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>　?。?）每一個(gè)路由器啟動(dòng)后，首先執(zhí)行對(duì)相鄰節(jié)點(diǎn)的發(fā)現(xiàn)工作，并獲得它們的地址，這個(gè)過(guò)程在具體實(shí)施時(shí)是通過(guò)發(fā)送特殊的Hello分組實(shí)現(xiàn)的；</p><p>　?。?）各路由器主動(dòng)測(cè)試到每一個(gè)相鄰路由器

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

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

31、適用于規(guī)模較小和拓?fù)浣Y(jié)構(gòu)變化不快的網(wǎng)絡(luò)；鏈路狀態(tài)路由選擇算法能夠及時(shí)反映網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，收斂速度很快，適應(yīng)于規(guī)模較大和拓?fù)渥兓^快的網(wǎng)絡(luò)，但由于每一個(gè)路由器均需要實(shí)時(shí)形成全網(wǎng)的拓?fù)鋱D及構(gòu)造以自己為節(jié)點(diǎn)的樹(shù)，所以對(duì)處理器性能要求比較高，另外，路由信息是以廣播的形式傳播的，占用的網(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兩大類。簡(jiǎn)單的定義是，內(nèi)部網(wǎng)關(guān)協(xié)議是用于自治系統(tǒng)內(nèi)部的動(dòng)態(tài)路由協(xié)議，包括RIP、OSPF等；而外部網(wǎng)關(guān)協(xié)議是用于自治系統(tǒng)之間的拓?fù)湫畔⒔粨Q的路由協(xié)議，包括BGP等。本設(shè)計(jì)將基于OSPF協(xié)議，下面將詳細(xì)討論該協(xié)議。</p><p>　　開(kāi)放最短路徑優(yōu)先協(xié)議OSPF[17]是一種基于區(qū)域（路由域）實(shí)現(xiàn)的、建立在Dijkstra算法和鏈路狀態(tài)算法基礎(chǔ)之上的內(nèi)部網(wǎng)關(guān)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

56、t;　　6)在點(diǎn)到點(diǎn)接口類型中,通過(guò)配置按需播號(hào)屬性(OSPF over On Demand Circuits),使得ospf不再定時(shí)發(fā)送hello報(bào)文及定期更新路由信息?只在網(wǎng)絡(luò)拓?fù)湔嬲兓瘯r(shí)才發(fā)送更新信息?</p><p>　?。?）通過(guò)嚴(yán)格劃分路由的級(jí)別(共分四極),提供更可信的路由選擇?</p><p>　?。?）良好的安全性,ospf支持基于接口的明文及md5 驗(yàn)證?</p

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

72、短路徑，對(duì)于復(fù)雜問(wèn)題來(lái)說(shuō)，大的會(huì)導(dǎo)致更差的收斂性能。</p><p>　　3.3 蟻群算法的主要特點(diǎn)</p><p>　　ACO算法的主要特點(diǎn)概括如下：</p><p>　　1）采用分布式控制，不存在中心控制;</p><p>　　2）每個(gè)個(gè)體只能感知局部的信息，不能直接使用全局信息;</p><p>　　3）個(gè)體可改

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

93、信息來(lái)更新信息素濃度，Q是正的常量。</p><p><b>　　對(duì)于最大化問(wèn)題：</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)過(guò)的螞蟻數(shù)量有關(guān)。邊上經(jīng)過(guò)的螞蟻越多，該邊越有可能成為最終路徑的一部分。</p><p><b>　?。?）蟻量系統(tǒng)：</b></p><p><b>　　（4.8）</b></p><p>　　在該情況下，信息素濃度的更新

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

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

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

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

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

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

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

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

103、>　　stack <-( j1 , di, j1 )</p><p>　　current <-j1</p><p>　　if 節(jié)點(diǎn)j1 存在到達(dá)目的節(jié)點(diǎn)的路由</p><p>　　then生成Bant 返向源節(jié)點(diǎn), 更新路由信息表</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é)點(diǎn)的次序計(jì)算出當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)的時(shí)延, 并根據(jù)節(jié)點(diǎn)數(shù)計(jì)算出跳數(shù), 然后

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

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