基于改進型蟻群算法的P2P網絡資源搜索的研究

蔡 康

（華南理工大學電子與信息學院 廣州 510640）

1 引言

蟻群在覓食過程中總可以找到一條從蟻巢到食物源的最短路徑。受到這些現象的啟發，意大利學者Dorigo M等人于1991年提出了一種新穎的啟發式優化算法——蟻群算法。但是該算法并沒有引起很多人的注意，直到1996年Dorigo M發表了一篇文章，更加詳細地闡述了蟻群算法的基本原理和數學模型[1]。從此，蟻群算法吸引了廣大研究者的注意，得到了很大的發展，目前已經廣泛用于求解各種組合優化問題，如函數優化、系統辨識、機器人路徑規劃、數據挖掘、網絡路由等，取得了很好的效果，尤其適用于網絡路徑優化。

Dorigo M針對TSP問題提出了3種不同的基本蟻群算法模型，分別稱為蟻周系統（ant-cycle system）、蟻量系統（ant-quantity system）、蟻密系統 （ant-density system）。最大—最小螞蟻系統（max-min ant system，MMAS）[2～5]是到目前為止解決TSP、QAP等問題最好的ACO算法。和其他尋優算法相比，它仍然屬于最好的解決方案之一。利用蟻群算法良好的耦合能力，將蟻群算法和遺傳算法結合起來，采用遺傳算法生成信息素初始分布，利用蟻群算法求精確解，從而實現兩種算法的優勢互補[6,7]。

將蟻群算法的思想引入非結構化P2P網絡的搜索算法中，模擬螞蟻覓食行為查找用戶需要的資源，利用螞蟻的信息素軌跡指導搜索的前進方向。這種正反饋機制使得搜索可以盡快地找到目標，得到更好的搜索結果。在基于蟻群算法的P2P網絡資源搜索算法中，查詢消息分組可以看作螞蟻，搜索的目標視為食物，存在搜索目標的節點就是食物源。算法流程如下。

·當源節點發出搜索請求時，就相當于派出螞蟻到網絡中尋找食物。

·當螞蟻到達時，先看節點是否有需要的食物，如果有就返回一個命中消息分組（可看作派出一只找到食物的螞蟻沿原路返回源節點，沿途釋放信息素，即修改節點的信息素表）。

·若沒有，則根據節點中的信息素濃度，選擇離目標近的鄰居繼續爬行，直到TTL（存活時間）減為0。

[8]研究了在非結構化P2P網絡資源發現算法中蟻群算法的應用，指出在非結構化P2P網絡資源發現算法中，已有的一些算法基本采用泛洪搜索方法。泛洪搜索可以保證較高的搜索成功率，但同時也產生大量的網絡查詢信息，嚴重占用網絡帶寬，很容易造成網絡擁塞。由于搜索沒有任何指導，很多沒用的節點（如資源缺乏、信譽度比較低、計算能力差或動態性比較大等）也可能被搜索到，但這樣的搜索顯然不會得到想要的結果。如果網絡節點能夠記錄其鄰居節點的相關信息，就可以有選擇地進行搜索，避免搜索到無用節點，在提高搜索成功率的同時，也減少網絡的負擔?；谙伻核惴ǖ腜2P網絡資源發現算法，正好可以滿足上述要求。蟻群算法要求每個節點維護一張信息素表，通過信息素表中各鄰居節點的信息素量等信息來決定搜索時走向哪些鄰居節點。文中提出，基于蟻群算法的P2P網絡資源發現算法主要分為兩個階段：探查階段和泛洪階段。

（1）探查階段

當某個節點發出資源搜索請求時，首先發出探查信息分組給部分鄰居節點，并賦予探查信息分組一個較小的存活期。探查信息主要用于估計所搜索的資源的普及性。當這個小區域搜索結束后，源節點就收到關于所搜索的資源的一些統計信息，通過分析這些統計信息，源節點可以預知，搜索信息傳播給幾個鄰居，最后可以得到多少資源搜索結果。這些統計信息將被存儲在“探查表”中。

（2）泛洪階段

當“探查表”建立后，源節點需要對接下來的泛洪搜索進行兩個值的初始化：一個是k，即多少百分比的鄰居將會被傳播該泛洪搜索信息；另一個是TTL，即該泛洪搜索信息的存活期。k的值是由“探查表”中的相關信息估計此次搜索的代價決定的。泛洪搜索是一個迭代的過程，源節點計算有多少節點需要更深入的搜索，并選擇一個合適的TTL。在搜索到資源后，源節點與資源節點之間的所有節點的信息素表將會被依次更新，以標志該路徑的代價。

參考文獻[9]提出了一種基于資源相似度和信譽相似度的P2P網絡節點選取方法。該方法使用蟻群優化算法，算法要求每個節點維護兩張信息素表：資源相似度信息素表和信譽相似度信息素表。文中指出，在P2P網絡中，由于人們興趣相似的關系，很多節點擁有相似或相同的資源，如果將這些節點以一定的方式聯系起來，組成一個邏輯上的資源社區，則當其他節點發起搜索請求時，根據資源特性可以很快地在社區中找到提供資源的節點。另外，還指出研究節點信譽度衡量的重要性。高信譽度的節點在給網絡提供可靠資源的同時，也保證搜索資源的高效性，而低信譽度的節點則可能降低網絡資源的搜索率，甚至給網絡帶來某些惡意破壞。并提出兩種衡量節點信譽度的方法：直接信任和推薦。直接信任是指對與當前節點進行資源對換的鄰居節點的信譽進行衡量；推薦是指根據與當前節點的鄰居節點進行資源對換的其他節點的信譽來衡量。通過維護這兩張表，可以提高網絡資源的搜索率和成功率。

蟻群算法在P2P網絡的應用還存在許多問題，如網絡中的螞蟻數量的控制、信息素的更新機制、網絡動態變化的處理等，最為嚴重的問題是目前的各種研究僅僅具有理論上的價值，在實際網絡應用中還不具有可行性和現實性。本文針對上述問題專門為蟻群算法設計一種新型的P2P文件共享構架，嘗試將蟻群算法的理論與實際網絡環境相結合。

Dorigo M提出蟻群算法以來，能見度一直作為蟻群算法最基本、不可或缺的兩大要素之一（另一個是信息素），幾乎被所有與蟻群算法相關的研究文章所采用。參考文獻[10]認為去掉能見度更容易證明全局性，但缺乏分析和實驗比較算法效率，且僅針對TSP問題。本文分析了在P2P網絡中應用能見度帶來的3個缺點，提出了去能見度蟻群算法。一系列的實驗結果證明了本文的觀點：能見度容易導致局部極值問題，在大型網絡中去掉能見度更好。

2 蟻群算法在P2P網絡中的實現問題

蟻群算法在P2P網絡中的應用基本集中在路由和資源發現兩個方面，資源發現包括搜索文件、有多余運算能力的節點等，歸結到底是要在網絡中找出符合條件的節點以及通往該節點的最優路徑。蟻群算法在P2P網絡的應用還存在許多問題，本節將其歸納為4點，并針對這個問題給出一個新型的P2P文件共享構架。

2.1 邏輯路徑與物理路徑的不一致性

在目前的P2P系統中，每個Peer既可以是一個用戶，也可以是一個資源提供者，還可以是一個數據分組中轉者（即中間節點），此時該Peer相當于一個路由器，這就是P2P路由的原理，如圖1所示。然而當中間節點是一臺普通的個人電腦 （在目前的系統中絕大多數Peer都是個人電腦）時，P2P路由存在嚴重的問題。

圖1中3個虛線的橢圓代表局域網，有3個網關（路由），虛線的箭頭a、b代表P2P路由找到的一條Peer 1至Peer 3的路徑，即 Peer 1→Peer 2→Peer 3，其中 Peer 2充當中間節點。這條P2P路徑不是實際的路徑，而只是一條邏輯意義上的路徑，實際的物理路徑是圖1中的實線箭頭，即 1→2→3→4→5→6，在這條物理路徑中，路徑 3和路徑4構成了一個局部的回路（嚴格地說應該是閉跡），顯然路徑3和路徑4完全是多余的，去掉這兩條邊，可以直接得到一條更好的路徑：1→2→5→6，它比原來的路徑短。

P2P的物理路徑包含大量的局部回路，圖1中只有一個中間節點，實際上中間節點會有多個，一般情況下，每一個中間節點就帶來一個多余的局部回路，這將使得物理路徑極大地加長，于是從Peer 1至Peer 2的時延也顯著增加，對Peer 3而言，它下載需要的時間也相應顯著地增加。當Peer 3從Peer 1下載資源時，所有的數據分組都會經過Peer 2，由此不但給Peer 2的電腦帶來了巨大的負荷，而且占據了Peer 2的網絡帶寬，嚴重影響Peer 2的正常應用，在這種情況下，Peer 2的用戶甚至可能會退出P2P系統。假設有多條P2P路徑都經過Peer 2，則下載時多個數據流都經過Peer 2，即使該用戶不退出，系統也無法正常下載。由此可以看出，基于蟻群算法的P2P路由難以在現實網絡中實現。

2.2 資源搜索與優化相結合的問題

相對于2.1節所介紹的蟻群P2P路由問題，目前更多的理論研究集中于蟻群算法搜索P2P資源問題，一個有趣的現象是：目前絕大部分基于蟻群算法進行P2P資源搜索并不使用P2P路由，而是在找到資源之后，利用資源節點的IP地址，使用傳統的路由方式建立下載路徑[11]。一個顯而易見的問題是：為什么在發現資源之后不使用原有的路徑（即發現資源時所找到的路徑）下載，而要重新搜索一條新的路徑？

上述過程中進行了2次路徑查找，這不但浪費時間，而且加重了網絡的負擔，似乎將資源搜索與路徑優化結合起來更為合理，但是P2P的邏輯路徑與物理路徑的不一致性問題阻礙了這種結合。實際上很多學者已經發現了該問題，因此不得不把資源發現和資源下載分割成兩個獨立的部分，各自使用不同的路徑。雖然這種分割處理的辦法能夠在實際網絡中實現，并能夠避免物理路徑的局部回路（如圖1所示），但是通過網絡路由發現的下載路徑既不是P2P路由路徑（如圖1虛箭頭所示的P2P路徑），也不一定是圖1中所示的物理路徑（通常是另一條物理路徑）。這種差異造成的結果就是：通過蟻群算法找到的“優秀”資源實際上并不一定好，因為由蟻群算法所找到的“優秀”資源的邏輯路徑優于其他邏輯路徑，但是其物理路徑并不一定優于其他路徑。其本質就是：找到的路徑和實際使用的路徑不一致，找到的只是一條虛假的最優（或次優）路徑。

2.3 節點失效與可靠性問題

在P2P系統中，尤其是非結構P2P網絡中，每個Peer都有充分的自主權，可以自由地加入和退出系統。對于圖1所示的系統，因為是普通用戶的個人電腦充當中間節點，所以最容易發生的情況是一個中間節點退出，由此造成蟻群算法已經發現的一條或多條路徑失效，只能重新搜索，盡管2.2節指出蟻群算法在動態變化網絡的優化方面具有明顯優勢，但這只是相對傳統路由算法而言，中間節點的頻繁退出無疑會使得蟻群算法難以收斂。相對傳統路由，蟻群算法的搜索路徑時間肯定要長很多，時間越長，中間節點退出的可能性越大，因此在非結構P2P網絡中使用蟻群路由算法必須要考慮中間節點退出的問題，但是這方面相關的研究不多，大部分都是在理想的靜態條件下仿真。

2.4 螞蟻數量問題

目前的蟻群算法都只適合于小型網絡，在大部分關于QoS路由的文章中，其仿真節點數不超過20個[12～15]。主要的問題在于螞蟻數量。在一個節點較多的網絡中，利用螞蟻實現準確查找是一種小概率事件，除非花很長時間。因此關于QoS路由的文章使用的螞蟻數量一般和節點數量相同，甚至使用比節點數更多的螞蟻。一個具有n個節點的網絡中，一個節點的一次查詢就要n個螞蟻，n個節點需要n2個螞蟻。在一個100節點的網絡中，高達10 000只螞蟻的頻繁訪問，將使得所有節點癱瘓。然而，如果螞蟻數量不多，準確查找又難以實現或者需要很長的時間。

3 適合蟻群算法的新型P2P文件共享構架

以上詳細討論了蟻群算法應用于非結構P2P存在的諸多問題，其主要原因在于大部分的蟻群算法僅限于純粹的理論研究，實際上最初蟻群算法的原型是針對TSP問題而設計，與實際網絡條件有較大的差異。本節將針對上述問題專門為蟻群算法設計一種新型的P2P文件共享構架，嘗試將蟻群算法的理論與實際網絡環境相結合。

圖2為系統的邏輯連接示意。G為網關節點（路由），P為普通節點（PC機）。虛線框內為骨干網。以上是硬件部分，該構架還包括蟻群協議部分。

3.1 信息素存儲方式

信息素是蟻群算法的關鍵部分，從圖論的角度來看，即各條邊的權系數值。對于TSP問題，全部的程序都是在一臺計算機上運行，因此所有的信息素都可以存儲在本機上。但是對于網絡路徑優化問題，這個方法幾乎無法實現。因為信息素和多個網關、路由、網絡鏈路的實際參數有關，無法在本機（即源節點）上直接獲得。一種想法是：螞蟻經過路由和鏈路可以獲得其參數，然后發信息分組回傳源節點，由源節點在本機建立一個虛擬網絡，但這種方法需要很大的通信量，且網絡是動態變化的，螞蟻回傳的參數很快就失去時效。這種方法的本質是源路由法，每個Peer需要保存全網拓撲信息，要求很大的內存，更降低了該方法的實用性。

本文的方法是由各個路由器、網關存儲信息素，每個路由或網關只存儲與其相鏈接的邊的信息素。顯然，本文的蟻群算法是由路由器、網關來執行的，而不是P2P用戶的個人電腦，從本質上看是多節點協同完成的分布式路由法。由于螞蟻所經的路徑就是物理路徑，其信息素正是其物理路徑的參數，由此就解決了邏輯路徑與物理路徑不一致的關鍵問題，從而使得基于蟻群算法的網絡路由方法具有實際意義。因為信息素是不斷揮發的，當經過一段時間某個螞蟻的信息素揮發到一定值時，路由器就不必再存儲該信息素，從而可以解決信息素過多占據內存的問題。

3.2 統一系統時鐘

根據每次P2P任務中扮演的角色，可以將參加的全部Peer分為3類：源節點（螞蟻的起點）、中間節點、目的節點（螞蟻的終點）。由于信息素分布式存儲于多個路由、網關中，為避免沖突，整個系統有一個統一的時鐘頻率，每個上半周期所有節點更新信息素，下半周期所有節點執行對螞蟻的操作，包括接收、轉移、發出、銷毀。

3.3 螞蟻搜索資源流程

系統搜索資源的原理如下。

·每個網關節點負責其局域網內節點的加入和退出，并建立一個域共享表保存其域內在線節點提供的所有共享文件的統一識別標志和關鍵詞，相同文件只留1個識別標志。

·如果P1想查找某個感興趣的內容，它把關鍵詞發給網關G1，G1在其域共享表進行匹配，如果其域共享表有（假定P2有），把文件的統一識別標志和P2的地址返回P1，P2和P1用普通路由方式建立連接下載。

·如果G1在其域共享表沒有找到P1需要的內容關鍵詞，G1發螞蟻到骨干網進行搜索，如果G1所在的域內有多節點同時查找域外同一資源，G1將其合并成一個任務。

·G1發出的某個螞蟻A到達網關G2，G2將其域共享表與螞蟻A所帶關鍵詞進行比較，如果G2域共享表內無該詞，則轉發別的網關；如果有，則將與該關鍵詞對應的文件統一識別標志和G2域內路徑賦予螞蟻帶回，于是總的路徑為：P1至G1+G1至G2+G2至資源。

·多個螞蟻搜索到資源之后返回，并在路徑上布下信息素。

·由于螞蟻是以隨機漫游的方式進行搜索，其得到的路徑大多數情況下不是滿意解或次優解，更不是最優解，因此必須啟動蟻群路徑優化算法，確定最優資源和到最優資源的最優路徑。

以上架構對蟻群算法有以下作用。

·減少螞蟻數量，網關節點對域內請求進行了過濾和合并，大幅減少了骨干網上的螞蟻數量。

·由于螞蟻是在網關與網關之間搜索，縮短了螞蟻的搜索路徑，使得搜索難度呈指數降低（發現概率隨著跳數的增加呈指數下降）。

·增大了蟻群算法搜索的網絡規模。在普通網絡中，螞蟻以單機為搜索單位；在本構架中，螞蟻在骨干網上以局域網（網關）為搜索單位，規模呈千百倍增長。

·將蟻群資源搜索和路徑優化相結合，可以起到事半功倍的效果。

相比目前的超級節點系統，本構架有如下改進。

·超級節點系統中域的劃分是一個難題，本架構以局域網劃分域，物理拓撲結構和P2P邏輯結構相吻合，節點間通信開支小、流量小。

·網關服務器、路由器相比其他節點更可靠，以網關服務器為域中心，系統更穩定，并且能夠避免虛假、過時的文件信息。

·路由器參與蟻群算法，使得物理路徑與邏輯路徑一致。

·能最大程度地實現流量本地化。目前P2P流量本地化采用IP地址判斷，但由于運營商不同，IP地址與實際地址有較大差異，且不能準確到單個局域網。

·本文的蟻群算法能提供到資源節點的路徑，無需骨干網路由查找。普通的超級節點系統只能提供資源節點的IP地址。

·穿透內網功能。因為直接獲得資源的路徑，所以不受內網虛擬IP地址的影響，可直接穿透，無需UPnP和打洞等復雜手段。

3.4 P2P網絡拓撲仿真的改進

在研究蟻群算法應用于P2P網絡的絕大部分文獻中，從源節點至目的節點的距離一般都低于4跳，網絡的節點數一般不超過20個[12～14]，連小型局域網都算不上。然而，在實際的P2P網絡中，一般情況下Peer的數量為數千甚至數萬個，尤為重要的是這種“微型網絡”是封閉式，即螞蟻限制在這數十個點內走動，不會走到其他網絡或者外網，如internet。在這種“微型網絡”中，無論螞蟻怎么隨機游走，只需建立一個禁忌表，除非路徑出現閉鎖，絕大多數情況下都能找到目的地。因此螞蟻的生存概率比實際網絡環境高，所以基于這種網絡的仿真結果對實際P2P并沒有太多參考價值。當然這種“微型網絡”的優點也是很明顯的：其拓撲結構可以顯示和打印在一個較小的版面上，讀者一目了然，研究者能直接地研究該圖，有利于進行公平的比較。事實上這種網絡拓撲和TSP路徑優化基本相同，但其與真實的網絡環境相差甚遠。

在利用蟻群算法進行資源搜索的文章中[16～19]，因為不進行路徑優化，蟻群沒有收斂過程，功能單一，算法簡單，可以使用較多節點，有些文章在NS2環境中使用具有數百個節點的網絡進行仿真，但是這種網絡圖不容易在常用的A4版面上顯示和打印出來，尤其是對于路徑優化，必須要在圖中的每條鏈路標出時延。因此這種仿真無法使讀者看到拓撲結構的細節。

綜上所述，問題歸結為：如何通過一個較小的拓撲結構來模擬一個大型的網絡環境？似乎這兩者相互矛盾。在解決這個問題之前，本文給出一個新的網絡概念：開放式網絡拓撲。在解釋開放式網絡拓撲之前，為了清楚地解釋這個概念，先解釋其反面——封閉式網絡拓撲。

定義1（封閉式網絡拓撲）如果一個用于仿真的網絡結構圖有確定的網絡邊界，數據分組只能在邊界以內的節點之間傳遞，則稱為封閉式網絡拓撲。

定義2(開放式網絡拓撲）如果一個用于仿真的網絡結構圖沒有確定的網絡邊界，則稱為開放式網絡拓撲。

開放式網絡拓撲如圖3所示。

圖3中的小圓圈表示一個節點，線段為鏈路，實線部分表示要研究的某個大型網絡的一個局部，虛線部分表示實線部分連接到該大型網絡的其余部分。當一個螞蟻（數據分組）從P3節點到達P1節點時，如果是在封閉式的拓撲結構（忽略圖中的虛線部分，余下的實線部分就是一個封閉式的拓撲結構）中，該螞蟻只能去P2或P4節點；如果在新的開放式的拓撲結構中，該螞蟻可以去虛線節點—圖中所示為大網絡中的節點，螞蟻到達任何一個虛線節點即表示已經走到一個很大的網絡中或者其他局域網，考慮到螞蟻的生存周期有限，通常很難有機會再返回實線部分，因此僅需考慮實線部分 （源節點和目的節點都在實線部分），可以認為螞蟻一到達虛線節點就意味著螞蟻死亡。

從以上過程可以看出，通過這個較小的開放式拓撲結構可以模擬螞蟻在一個大型網絡中的行為，這種模擬環境相對于封閉式拓撲更接近實際環境。目前幾乎所有的網絡仿真實驗都采用了封閉式的拓撲結構，包括著名的NS2軟件。本文將采用開放式拓撲結構進行算法仿真實驗，顯然在開放式拓撲結構中螞蟻更難找到目的節點。

4 改進型蟻群算法——去能見度的蟻群算法

4.1 能見度在P2P網絡中的副作用

在蟻群算法中，螞蟻根據概率轉移公式選擇下一條路徑：

在研究網絡QoS問題的絕大部分文章中，都應用了小型的封閉式網絡，和TSP問題一樣，螞蟻選任何一條邊幾乎都能走到目的地，其失敗的概率極小。因此當螞蟻到達某個節點時，在與該點相關聯的所有鏈路中，選擇一條更短的鏈路具有概率上的啟發意義。然而，如果在一個開放式的網絡中，螞蟻的失敗概率很大，螞蟻選的一條邊無法保證它能走到目的地，無論其長度如何，也即在這種情況下邊的長短和成功率無任何關聯，必須先成功到達目的地之后才能考慮長度問題。另一方面，如果螞蟻成功到達目的地，它可以用路徑總長度來建立啟發信息，無需用每條邊的長度作為啟發信息。更進一步，如果用每條邊的長度作為啟發信息，即所謂能見度，會有以下3個副作用。

（1）容易導致局部極小解

下面分兩種情況進行說明。

圖4中螞蟻初次從源節點c出發，因為初始信息素每條邊都相同，而源c至b點的邊比ca邊短，概率上螞蟻會選路徑：源節點c→b→d（總時延12），因此該路徑將增加信息素，下一個螞蟻將更加偏向選該路徑，并最終收斂到該路徑，而實際上另一條路徑c→a→d（總時延10）才是最好值。

假定a、b都有螞蟻到達一次，邊ca信息素增量為1/(8+2)=1/10，能見度為1/8；邊cb的信息素增量為1/(5+7)=1/12，能見度為1/5。初始信息素殘留0.1。根據經典蟻群算法概率轉移公式，取α=β=1，算得邊ca的轉移概率為40.538%，邊cb的轉移概率為59.462%，局部解的選擇概率竟然高于全局解。

（2）容易導致流量集中

本文中的節點時延為螞蟻數據分組在路由器中的排隊時延，鏈路時延（本文所指鏈路實際為一段線路，參考文獻[20]將節點時延和線路時延合稱鏈路時延）為數據分組在一段線路（光纖）中的傳輸時延。節點時延是與該節點相連的所有鏈（線）路共有的，不能為鏈路選擇提供依據，因此實際能作為能見度的是鏈路時延，也即傳輸時延，但傳輸時延不會隨流量負載變化，基本為固定的一個較小值[21,22]。即使某條時延低的鏈路流量很大，因為其能見度不變，螞蟻仍然會選擇它，從而導致流量集中。

（3）單個鏈路（傳輸）時延在實際系統中難以準確檢測

如果取下一個節點的排隊時延為能見度，在實際網絡中的實現有較大難度。

4.2 新的概率轉移公式

令τij(t)為t時刻鏈路(i,j)上的信息素強度，每條邊有一個初始信息素c（給定的常數），在預搜索期間被選中的邊的信息素為c+b，用禁忌表tubuk來記錄螞蟻k(k=1，2，…，m)當前所走過的節點，螞蟻k根據各條邊上的信息量來計算狀態轉移概率。

其中，α為信息啟發式因子，Nk表示螞蟻k下一步允許選擇的節點：Nk=與節點i鄰接的節點集-tubuk。

式(2)中沒有ηij系數和與之相關的β系數，這與目前通用的方法不同，稱之為去能見度蟻群算法，顯然其比經典式子計算更簡單，這是它的另一個優點。

5 實驗與分析

采用兩個不同的網絡拓撲結構，兩個不同的長度限制，分兩部分共4個實驗。

基本實驗說明：開放式網絡拓撲，在這種新的結構中，當某螞蟻到達網絡邊界時，它有兩種選擇，或者向邊界內走或者死亡——實際表示螞蟻向邊界外走，走向了其他的局域網或更大的骨干網，它很難再回到本局域網。從以上過程可以看出：通過這個較小的開放式拓撲結構可以模擬螞蟻在一個大型網絡中的行為，這種模擬相對于封閉式拓撲更接近實際環境。

節點共140個，除5條邊的長度大于24但小于34，其余邊長為12～24的隨機數，精確到小數點后一位。除實驗1、2中有一條從源節點到目的節點的路徑跳數為8跳，其余都不小于14跳。顯然這個距離顯著超過了目前絕大部分有關QoS的文章中的最短距離。使用4個螞蟻，共做80次試驗。

5.1 長邊少跳數實驗

以下兩個實驗采用相同的網絡，且特地設置一條8跳的路徑，其中有幾條長度較大的邊（大于24），該路徑的總長度為194.4，為最短路徑，其余路徑的跳數都不低于14跳。

5.1.1 實驗1

在這個實驗中，規定螞蟻的生存周期內其已經走過的路徑最大長度為：限制路徑長度≤14跳×平均邊長18×系數1.5跳 =378此處采用限制最大路徑長度而非最大跳數，是基于以下考慮：

·目標是最小長度的路徑，而不是跳數；

·存在著跳數很多，但是總長度并不大的路徑；

·要公平對比無能見度和有能見度兩種方式，只有采用長度限制，關于這一點在后面的分析中有說明。

實驗曲線如圖5所示。

圖5的虛線反映了有能見度算法的運行狀態，實線反映了無能見度算法的運行狀態，考慮到版面寬度的限制，僅僅繪制到200代。顯然實線的下降速度和最小值都明顯好于虛線，即本文的無能見度算法優于經典的有能見度蟻群算法。

圖5給出了兩個實時運行的曲線，因為蟻群算法有較大的隨機性，每次運行的數據均不相同，因此曲線也不同。為公平起見，均取有代表性的某次運行畫圖。所謂有代表性，即運行的結果既不是最好，也不是最差，而是接近多次運行的平均值（參見表1）。本節的其他曲線也采用同樣的方式繪制。

分別使用有能見度的蟻群算法和無能見度的蟻群算法進行80次實驗，得到表1的結果。

表1 限制系數1.5的比較結果（80次）

5.1.2 實驗2

在這個實驗中，規定螞蟻的生存周期內已經走過的路徑長度為：

限制路徑長度=14×平均邊長18×系數1.25跳 =315

本實驗采用的網絡與實驗1相同。

實驗曲線如圖6所示。

該圖采用了與圖5不同的x軸刻度單位，其原因是在更嚴格的長度限制下，有能見度的經典蟻群算法需很長時間才能找到目的地。

圖6的曲線僅為某次結果，考慮到算法的隨機性，分別使用有能見度的蟻群算法和無能見度的蟻群算法進行80次實驗，得到表2的結果。

表2 限制系數1.25的比較結果（80次）

不同限制路徑長度對結果有一定影響：當限制路徑較短時，獲得最優值的次數增加，但平均值有所下降，其原因是螞蟻致力于尋找最小路徑，一旦某次路徑超過最小要求就死亡，因此成功率反而有所下降。

從有能見度的式(1)可以看出，該算法偏向于選擇較短的邊，而很難發現那些長邊、少跳數的路徑，也即經典算法偏向于短邊、多跳的路徑，所以采用長度限制才能公平比較兩種算法。

5.2 短邊多跳實驗

總的來說，實驗1和2不利于有能見度算法，以下的2個實驗的網絡設置則有利于該算法。

仍然保留那條8跳的路徑，其中有幾條長度較大的邊（大于24），該路徑的總長度為194.4；但是另有一條18跳，每邊都較短，總長度為190的最短路徑，其余路徑的跳數都不低于14跳。

5.2.1 實驗3

在這個實驗中，規定螞蟻的生存周期內其已經走過的路徑長度為：

限制路徑長度=14×平均邊長18×系數1.5跳 =378分別使用有能見度的蟻群算法和無能見度的蟻群算法進行實驗，得到圖7的曲線。

圖7的虛線反映了有能見度算法的運行狀態，實線反映了無能見度算法的運行狀態，考慮到版面寬度的限制，僅僅繪制到400代。

圖7的曲線僅為某次結果，考慮到算法的隨機性，分別使用有能見度的蟻群算法和無能見度的蟻群算法進行80次實驗，得到表3的結果。

表3 限制系數1.5的比較結果（80次）

5.2.2 實驗4

在這個實驗中，規定螞蟻的生存周期內其已經走過的路徑長度為：

限制路徑長度=14×平均邊長18×系數1.25跳 =315

本實驗采用的網絡與實驗3相同。

分別使用有能見度的蟻群算法和無能見度的蟻群算法進行實驗，得到圖8的曲線。

圖8采用了與圖7不同的x軸刻度單位，其原因是在更嚴格的長度限制下，有能見度的經典蟻群算法需很長時間才能找到目的地。

圖8的曲線僅為某次結果，考慮到算法的隨機性，分別使用有能見度的蟻群算法和無能見度的蟻群算法進行80次實驗，得到表4的結果。

表4 限制系數1.25的比較結果（80次）

從實驗3和4的結果可以看出：在短邊多跳的條件下，有能見度的蟻群算法的性能好于實驗1和2，但是其仍然不如無能見度算法。經過仔細分析有能見度算法的多次運行結果，發現該算法有不少次數找到一條長度為198的路徑，該路徑上有不少較短的邊，從而導致算法限于局部極小。

6 結束語

多種情況下的仿真實驗結果表明，去掉能見度的蟻群算法獲得最短路徑的次數明顯好于經典的蟻群算法，能見度容易導致局部極值。去掉能見度的蟻群算法的平均值也優于經典的蟻群算法，這也是獲得最小值次數較多的原因。總之，在開放式的網絡拓撲結構中，去掉能見度的蟻群算法明顯優于經典的蟻群算法，這也意味著去掉能見度的蟻群算法更適合應用在大型網絡中。

目前的各種蟻群算法（包括本文提出的去能見度蟻群算法）都是單目蟻群算法，即螞蟻從一個源節點尋找到一個目的節點的最佳路徑。然而，在分布式非結構化P2P文件共享系統中，大多數情況下，會有很多個節點擁有同一個想要下載的文件，這些都是候選目的節點，且它們的數量是未知的（對于源節點而言）。顯然，在這種情況下不但存在路徑優化問題，還存在目的節點選擇問題。在將來的研究工作中，將提出一種新型蟻群算法，集資源搜索、選擇目的節點和路徑優化于一體。

參考文獻

1 Dorigo M,Maniezzo V,Colorni A.Ant system:optimization by a colony of cooperating agents.IEEE Transactions on Systems,Man and Cybernetics,Part B:Cybernetics,1996,26(1):29～41

2 Stützle T,Hoos H.The max-min ant system and local search for the traveling salesman problem.Proceedings of IEEE-ICEC-EPS’97,IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference,IEEE Press,1997:309～314

3 Stützle T,Hoos H.Improvements on the ant system:introducing max-min ant system.Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms,Springer Verlag,Wien,1997:245～249

4 Stützle T,Hoos H.Max-min ant system and local search for combinatorial optimization problems.Meta-Heuristics:Advances and Trends in Local Search Paradigms for Optimization,Kluwer,Boston,1998:137～154

5 Stützle T.Max-min AntSystem forQuadratic Assignment Problems.Technical Report AIDA-97-04,Intellectics Group,DepartmentofComputerScience,DarmstadtUniversity of Technology,Germany,1997

6 吳慶洪,張紀會,徐心和.具有變異特征的蟻群算法.計算機研究與發展,1999,36(10):1 240～1 245

7 Marcin L P,Tony W.Using genetic algorithms to optimize ACSTSP.Proceedings of 3rd Int Workshop ANTS,Brussels,2002:282～287

8 Chi-Jen Wu,Kai-Hsiang Yang,Jan-Ming Ho.An ant search algorithm in unstructured Peer-to-Peer networks.Proceedings of the 11th IEEE Symposium on Computers and Communications,2006

9 Junqing Li,Quanke Pan,Shengxian Xie.Research on peer selection in Peer-to-Peer networks using ant colony optimization.Proceedings of the Fourth International Conference on Natural Computation,2008

10 Walter J,Gutjahr.ACO algorithms with guaranteed convergence to the optimal solution.Information Processing Letters,2002(82):145～153

11 吳湘寧,汪淵.基于蟻群算法的P2P文件共享系統.計算機工程與應用,2007,43(20):145～148

12 劉萍,高飛,楊云.基于遺傳算法和蟻群算法融合的QoS路由算法.計算機應用研究,2007,24(9):224～227

13 劉永娟.改進蟻群算法在QoS路由中的應用與研究.通信技術,2008,41(9):128～133

14 陳巖,楊華江,沈林成.基于再勵學習蟻群算法的多約束QoS路由方法.計算機科學,2007,134(15):25～44

15 楊華江,陳巖,沈林成.基于改進蟻群算法的多約束QoS路由方法.計算機應用與軟件,2008,25(5):15～17

16 Wu C J,Yang K H,Ho J M.Antsearch:an ant search algorithm in unstructured peer-to-peer networks.Proceedings of the 11th IEEE Symposium on Computers and Communications,Cagliari,2006:429～434

17 Wu G Y,Liu J Y,Shen X,et al.ERAntBudget:a search algorithm in unstructured P2P networks.Proceedings of the Second InternationalSymposium on IntelligentInformation Technology Application,Shanghai,2008:765～769

18 Li J Q,Pan Q K,Xie S X.Research on peer selection in peer-to-peer networks using ant colony optimization.Proceedings of the Fourth International Conference on Natural Computation,Jinan,2008:516～520

19 Cao Y,Li S Z.Research on P2P hybrid information retrieval based on antcolony algorithm.Proceedings ofthe 10th International Conference on Computer Supported Cooperative Work in Design,Nanjing,2006:1 048～1 052

20 劉萍,高飛,楊云.基于遺傳算法和蟻群算法融合的QoS路由算法.計算機應用研究,2007,24(9):224～227

21 焦利,林宇,王文東等.一種負載均衡網絡中內部鏈路時延推測算法.軟件學報,2005,16(5):886～893

22 郭小雪,秦勇,蔡昭權等.多鏈路時延反饋共享令牌流量擁塞控制.計算機工程與應用,2010,46(2):75～78