基于改進型蟻群算法的P2P網(wǎng)絡(luò)資源搜索的研究

蔡 康

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

1 引言

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

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

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

·當源節(jié)點發(fā)出搜索請求時，就相當于派出螞蟻到網(wǎng)絡(luò)中尋找食物。

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

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

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

（1）探查階段

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

（2）泛洪階段

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

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

蟻群算法在P2P網(wǎng)絡(luò)的應(yīng)用還存在許多問題，如網(wǎng)絡(luò)中的螞蟻數(shù)量的控制、信息素的更新機制、網(wǎng)絡(luò)動態(tài)變化的處理等，最為嚴重的問題是目前的各種研究僅僅具有理論上的價值，在實際網(wǎng)絡(luò)應(yīng)用中還不具有可行性和現(xiàn)實性。本文針對上述問題專門為蟻群算法設(shè)計一種新型的P2P文件共享構(gòu)架，嘗試將蟻群算法的理論與實際網(wǎng)絡(luò)環(huán)境相結(jié)合。

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

2 蟻群算法在P2P網(wǎng)絡(luò)中的實現(xiàn)問題

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

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

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

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

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

2.2 資源搜索與優(yōu)化相結(jié)合的問題

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

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

2.3 節(jié)點失效與可靠性問題

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

2.4 螞蟻數(shù)量問題

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

3 適合蟻群算法的新型P2P文件共享構(gòu)架

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

圖2為系統(tǒng)的邏輯連接示意。G為網(wǎng)關(guān)節(jié)點（路由），P為普通節(jié)點（PC機）。虛線框內(nèi)為骨干網(wǎng)。以上是硬件部分，該構(gòu)架還包括蟻群協(xié)議部分。

3.1 信息素存儲方式

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

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

3.2 統(tǒng)一系統(tǒng)時鐘

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

3.3 螞蟻搜索資源流程

系統(tǒng)搜索資源的原理如下。

·每個網(wǎng)關(guān)節(jié)點負責其局域網(wǎng)內(nèi)節(jié)點的加入和退出，并建立一個域共享表保存其域內(nèi)在線節(jié)點提供的所有共享文件的統(tǒng)一識別標志和關(guān)鍵詞，相同文件只留1個識別標志。

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

·如果G1在其域共享表沒有找到P1需要的內(nèi)容關(guān)鍵詞，G1發(fā)螞蟻到骨干網(wǎng)進行搜索，如果G1所在的域內(nèi)有多節(jié)點同時查找域外同一資源，G1將其合并成一個任務(wù)。

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

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

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

以上架構(gòu)對蟻群算法有以下作用。

·減少螞蟻數(shù)量，網(wǎng)關(guān)節(jié)點對域內(nèi)請求進行了過濾和合并，大幅減少了骨干網(wǎng)上的螞蟻數(shù)量。

·由于螞蟻是在網(wǎng)關(guān)與網(wǎng)關(guān)之間搜索，縮短了螞蟻的搜索路徑，使得搜索難度呈指數(shù)降低（發(fā)現(xiàn)概率隨著跳數(shù)的增加呈指數(shù)下降）。

·增大了蟻群算法搜索的網(wǎng)絡(luò)規(guī)模。在普通網(wǎng)絡(luò)中，螞蟻以單機為搜索單位；在本構(gòu)架中，螞蟻在骨干網(wǎng)上以局域網(wǎng)（網(wǎng)關(guān)）為搜索單位，規(guī)模呈千百倍增長。

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

相比目前的超級節(jié)點系統(tǒng)，本構(gòu)架有如下改進。

·超級節(jié)點系統(tǒng)中域的劃分是一個難題，本架構(gòu)以局域網(wǎng)劃分域，物理拓撲結(jié)構(gòu)和P2P邏輯結(jié)構(gòu)相吻合，節(jié)點間通信開支小、流量小。

·網(wǎng)關(guān)服務(wù)器、路由器相比其他節(jié)點更可靠，以網(wǎng)關(guān)服務(wù)器為域中心，系統(tǒng)更穩(wěn)定，并且能夠避免虛假、過時的文件信息。

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

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

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

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

3.4 P2P網(wǎng)絡(luò)拓撲仿真的改進

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

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

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

定義1（封閉式網(wǎng)絡(luò)拓撲）如果一個用于仿真的網(wǎng)絡(luò)結(jié)構(gòu)圖有確定的網(wǎng)絡(luò)邊界，數(shù)據(jù)分組只能在邊界以內(nèi)的節(jié)點之間傳遞，則稱為封閉式網(wǎng)絡(luò)拓撲。

定義2(開放式網(wǎng)絡(luò)拓撲）如果一個用于仿真的網(wǎng)絡(luò)結(jié)構(gòu)圖沒有確定的網(wǎng)絡(luò)邊界，則稱為開放式網(wǎng)絡(luò)拓撲。

開放式網(wǎng)絡(luò)拓撲如圖3所示。

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

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

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

4.1 能見度在P2P網(wǎng)絡(luò)中的副作用

在蟻群算法中，螞蟻根據(jù)概率轉(zhuǎn)移公式選擇下一條路徑：

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

（1）容易導(dǎo)致局部極小解

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

圖4中螞蟻初次從源節(jié)點c出發(fā)，因為初始信息素每條邊都相同，而源c至b點的邊比ca邊短，概率上螞蟻會選路徑：源節(jié)點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。根據(jù)經(jīng)典蟻群算法概率轉(zhuǎn)移公式，取α=β=1，算得邊ca的轉(zhuǎn)移概率為40.538%，邊cb的轉(zhuǎn)移概率為59.462%，局部解的選擇概率竟然高于全局解。

（2）容易導(dǎo)致流量集中

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

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

如果取下一個節(jié)點的排隊時延為能見度，在實際網(wǎng)絡(luò)中的實現(xiàn)有較大難度。

4.2 新的概率轉(zhuǎn)移公式

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

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

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

5 實驗與分析

采用兩個不同的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，兩個不同的長度限制，分兩部分共4個實驗。

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

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

5.1 長邊少跳數(shù)實驗

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

5.1.1 實驗1

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

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

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

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

實驗曲線如圖5所示。

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

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

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

表1 限制系數(shù)1.5的比較結(jié)果（80次）

5.1.2 實驗2

在這個實驗中，規(guī)定螞蟻的生存周期內(nèi)已經(jīng)走過的路徑長度為：

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

本實驗采用的網(wǎng)絡(luò)與實驗1相同。

實驗曲線如圖6所示。

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

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

表2 限制系數(shù)1.25的比較結(jié)果（80次）

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

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

5.2 短邊多跳實驗

總的來說，實驗1和2不利于有能見度算法，以下的2個實驗的網(wǎng)絡(luò)設(shè)置則有利于該算法。

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

5.2.1 實驗3

在這個實驗中，規(guī)定螞蟻的生存周期內(nèi)其已經(jīng)走過的路徑長度為：

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

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

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

表3 限制系數(shù)1.5的比較結(jié)果（80次）

5.2.2 實驗4

在這個實驗中，規(guī)定螞蟻的生存周期內(nèi)其已經(jīng)走過的路徑長度為：

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

本實驗采用的網(wǎng)絡(luò)與實驗3相同。

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

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

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

表4 限制系數(shù)1.25的比較結(jié)果（80次）

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

6 結(jié)束語

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

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

參考文獻

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 吳慶洪,張紀會,徐心和.具有變異特征的蟻群算法.計算機研究與發(fā)展,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文件共享系統(tǒng).計算機工程與應(yīng)用,2007,43(20):145～148

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

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

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

15 楊華江,陳巖,沈林成.基于改進蟻群算法的多約束QoS路由方法.計算機應(yīng)用與軟件,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路由算法.計算機應(yīng)用研究,2007,24(9):224～227

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

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