基于蟻群算法的通用對等網(wǎng)仿真模型研究

田 濤

（廣西民族大學(xué) 商學(xué)院，南寧 530006）

0 引言

P2P應(yīng)用系統(tǒng)的特點(diǎn)在于其完全的分布式控制、節(jié)點(diǎn)的高動態(tài)性和節(jié)點(diǎn)的自治性，這和蟻群系統(tǒng)在一定程度上有相似之處。蟻群系統(tǒng)是一種模擬進(jìn)化算法，它具有分散式控制的特征，個體高度自治，通過信息素的作用、相互協(xié)作完成復(fù)雜任務(wù)。本文結(jié)合蟻群算法，構(gòu)建了一個用于對等網(wǎng)性能測試的通用仿真模型。

1 對等網(wǎng)仿真模型框架結(jié)構(gòu)

圖1所示為對等網(wǎng)仿真模型的框架結(jié)構(gòu)，由三個部分構(gòu)成：P2P應(yīng)用系統(tǒng)層、Nest和Ant。

圖1 對等網(wǎng)仿真模型框架結(jié)構(gòu)

1.1 P2P應(yīng)用系統(tǒng)層

該層任務(wù)是模擬用戶行為、初始化，根據(jù)不同類型的P2P應(yīng)用特征，對初始P2P邏輯網(wǎng)絡(luò)進(jìn)行配置，使模擬網(wǎng)絡(luò)環(huán)境符合被仿真P2P應(yīng)用的運(yùn)作環(huán)境，為仿真過程提供基礎(chǔ)參數(shù)配置。

1）仿真對象設(shè)置：指被評估的P2P應(yīng)用系統(tǒng)設(shè)計方案；包括：定義用戶請求類型，共享資源類型。在仿真中，用戶請求由系統(tǒng)隨機(jī)產(chǎn)生，用戶只需確定請求的數(shù)量。

2）隨機(jī)行為仿真：在對等網(wǎng)仿真模型中，為實現(xiàn)P2P網(wǎng)絡(luò)的高度動態(tài)性，通過P2P應(yīng)用系統(tǒng)層模擬Nest隨機(jī)的加入或退出對等網(wǎng)。控制參數(shù)包括：Nest數(shù)量及其連接度。

3）Nest中共享資源的形成：當(dāng)對等網(wǎng)形成后，P2P應(yīng)用系統(tǒng)層要根據(jù)系統(tǒng)設(shè)定的參數(shù)（Nest資源的數(shù)量和URL數(shù)量），為每個Nest分配資源，實現(xiàn)P2P網(wǎng)絡(luò)的資源共享。

4）模擬用戶請求：系統(tǒng)初始化后，開始分析測試過程，仿真模型通過應(yīng)用系統(tǒng)層預(yù)先設(shè)定的請求數(shù)量，模擬用戶請求。

5）設(shè)置響應(yīng)監(jiān)視器：在模擬請求發(fā)出后，P2P應(yīng)用系統(tǒng)層為每個發(fā)出的請求設(shè)置一個唯一的應(yīng)答監(jiān)聽器，對發(fā)出請求的響應(yīng)進(jìn)行監(jiān)聽。

6）收集評估數(shù)據(jù)：跟蹤并監(jiān)測仿真全過程，采集模擬請求的應(yīng)答信息和網(wǎng)絡(luò)的狀態(tài)參數(shù)。

1.2 Nest

對等網(wǎng)中的Peer用蟻群系統(tǒng)中的節(jié)點(diǎn)Nest代替，對等網(wǎng)由大量互相連接的Nest構(gòu)成。由圖1可知每個Nest由3個模塊組成：螞蟻調(diào)度器、通訊傳輸層和資源管理器。每個組成模塊完成不同的功能，圖2給出了節(jié)點(diǎn)的體系結(jié)構(gòu)。

圖2 節(jié)點(diǎn)的體系結(jié)構(gòu)

1）螞蟻調(diào)度器：負(fù)責(zé)為到訪螞蟻分配當(dāng)前Nest的運(yùn)算資源，負(fù)責(zé)加強(qiáng)Nest的安全性。2）通訊管理層：發(fā)現(xiàn)新加入對等網(wǎng)的Nest，將其插入當(dāng)前Nest的鄰居列表；網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)管理；負(fù)責(zé)螞蟻在對等網(wǎng)中各Nest之間的移動。設(shè)計中，為每個Nest設(shè)置唯一的標(biāo)識符。Nest在和遠(yuǎn)程N(yùn)est進(jìn)行通訊時，需確認(rèn)對方的標(biāo)識符，所有操作均依賴Nest標(biāo)識符。同時，引入鄰居Nest的概念：當(dāng)一組Nest都清楚同一個Nest的標(biāo)識符時，這組Nest被稱為當(dāng)前Nest的鄰居節(jié)點(diǎn)。需注意的是，引入鄰居Nest的概念不包含任何距離量度。鄰居Nest的收集充分說明了對等網(wǎng)絡(luò)的高度動態(tài)性。3）資源管理器：Nest通過一個或更多的資源管理器對到訪的Ant進(jìn)行資源分配并管理共享資源。

1.3 Ant

Ant在仿真模型中的作用是實現(xiàn)Nest之間的交互、完成對各種服務(wù)（用戶請求，搜索，節(jié)點(diǎn)加入、退出請求，共享請求等）的響應(yīng)、執(zhí)行蟻群算法。每個Ant都有一個接口，包含Run（）方法，用于執(zhí)行蟻群算法。Ant和Nest之間的交互通過Ant監(jiān)視器接口實現(xiàn)。接口Antview完成的功能包括：Nest通過Antview調(diào)用Ant算法；Ant通過Antview在Nest中獲取和修改信息素，比如讀取鄰居Nest列表、共享資源等、寫入路由信息素、返回請求應(yīng)答、移動到其他Nest。Antview接口的設(shè)計可以使Ant與Nest交互時，Ant不直接讀取或修改Nest中的數(shù)據(jù)，確保了一定的安全性。

1.4 消息

消息機(jī)制包括兩個部分：請求消息和響應(yīng)消息。用戶和對等節(jié)點(diǎn)之間的交互通過消息機(jī)制完成。對等網(wǎng)仿真模型對消息機(jī)制沒有特殊要求，表現(xiàn)在對請求消息和響應(yīng)消息的格式?jīng)]有特別規(guī)定，對消息的解釋由螞蟻執(zhí)行；對于不同的P2P應(yīng)用系統(tǒng)，可以設(shè)計不同的消息機(jī)制。此外，對等網(wǎng)仿真模型也不指定每個節(jié)點(diǎn)提供什么樣的服務(wù)，當(dāng)節(jié)點(diǎn)接收到一個請求消息后，它從一組已知的螞蟻類型中選擇合適的螞蟻來完成用戶的請求，螞蟻分成不同的種類，每個種類的螞蟻對應(yīng)一種消息機(jī)制。上述特征提高了對等網(wǎng)仿真模型的通用性和可擴(kuò)展性。

1.5 螞蟻的行為

當(dāng)節(jié)點(diǎn)對某個類型的螞蟻處理時，Antview接口被調(diào)用執(zhí)行，Antview規(guī)定了螞蟻的行為，這些行為包括：1）依據(jù)節(jié)點(diǎn)的標(biāo)識符移動到其他指定節(jié)點(diǎn)；2）訪問本地數(shù)據(jù)存儲器；3）通知本地節(jié)點(diǎn)有鄰居節(jié)點(diǎn)存在，并將其標(biāo)識符添加到本地節(jié)點(diǎn)的鄰居節(jié)點(diǎn)列表；4）獲取本地節(jié)點(diǎn)的鄰居節(jié)點(diǎn)列表；5）通知本地節(jié)點(diǎn)，螞蟻已經(jīng)為請求產(chǎn)生了一個響應(yīng)。

2 對等網(wǎng)仿真模型的實現(xiàn)及測試

2.1 系統(tǒng)總體流程

仿真模型執(zhí)行時，需配置大量參數(shù)，參數(shù)由XML+DTD控制。仿真模型對各種P2P應(yīng)用系統(tǒng)仿真過程如圖3所示。

圖3 仿真模型系統(tǒng)流程

2.2 P2P應(yīng)用仿真模型

為了對仿真模型進(jìn)行測試，本文設(shè)計了一個基于Gnuella協(xié)議的P2P文件共享系統(tǒng)實例，命名為DocShare，DocShare的應(yīng)用協(xié)議采用蟻群算法描述。依賴于仿真模型提供的接口，創(chuàng)建DocShare應(yīng)用比較簡單，DocShare的底層通訊由仿真模型實現(xiàn)。

圖4 DocShare體系結(jié)構(gòu)

2.3 仿真結(jié)果

為了使仿真實驗比較真實，通過對Gnutella網(wǎng)絡(luò)的監(jiān)視，文中收集了10000個搜索字符串，將這些搜索字符串命名為10000個文件。在進(jìn)行仿真之前將這些文件作為共享文件插入到模擬網(wǎng)絡(luò)的節(jié)點(diǎn)中。通過隨機(jī)產(chǎn)生的keyhash，引起螞蟻在模擬網(wǎng)絡(luò)中隨機(jī)的移動，完成RouteStorage的初始化。仿真模擬的網(wǎng)絡(luò)有2000個Nest，每個節(jié)點(diǎn)的連接度為10。

在共享資源插入完成后，仿真模型產(chǎn)生500個搜索請求，同時開始收集仿真行為的統(tǒng)計數(shù)據(jù)。為了實現(xiàn)仿真，搜索請求以遞增的方式（按照等比數(shù)列，等比系數(shù)為2）從10000個Gnutella搜索字符串中隨機(jī)產(chǎn)生。LookupAnt的TTL設(shè)置為10。

每個Nest的RouteStorage容量設(shè)置為16，共享文件的數(shù)量設(shè)置為16，UrlStorage的容量設(shè)置為64。模擬過程被重復(fù)進(jìn)行10次，以便獲取平均數(shù)據(jù)。

從圖5的曲線可以看出，搜索請求數(shù)在500時成功率為59.2%，當(dāng)請求數(shù)為64000時，成功率達(dá)到95.8%，平均成功率為74.4%，隨著時間的推移，DocShare的搜索成功率不斷提高，這是因為仿真模型產(chǎn)生的總請求數(shù)在增加，同時，DocShare中的分布式索引和路由信息也在不斷更新，以前螞蟻的搜索行為對其后螞蟻的搜索行為起到了借鑒作用。由圖也可以看出隨著搜索請求數(shù)不斷增加，失敗的響應(yīng)數(shù)也在增加，失敗率不斷提高，這就容易引起網(wǎng)絡(luò)負(fù)載過重，導(dǎo)致網(wǎng)絡(luò)崩潰。

圖5 仿真數(shù)據(jù)對比曲線

3 結(jié)論

仿真結(jié)果證明J對等網(wǎng)仿真模型設(shè)計的正確性。本文對等網(wǎng)仿真模型的設(shè)計基于蟻群算法，優(yōu)勢在于只需對單個螞蟻行為的簡單設(shè)計即可獲得整體的智能性；只需將不同的P2P系統(tǒng)協(xié)議用螞蟻算法實現(xiàn)，通過仿真模型提供的接口即可實現(xiàn)仿真，適應(yīng)于各類P2P應(yīng)用系統(tǒng)。

[1] Project JXTA.URL:Http://www.jxta.org.

[2] Todd Sundsted.The pactice of peer-to-peer computing:The P2P application framework.http://www-106.ibm.com/developerworks/java/library/j-p2ppapp.html

[3] Gnutellasim project.http://gnutellasim.limewire.org/serviets/ProjectRome.

[4] N.Minar,R.Burkhart,C.Langton,and M.Askenazi.The Swarm Simulation System,A Toolkit for Building Multi-Agent Simulations.Technical report,Swarm Development Group,June 1996.http://www.swarm.org.

[5] Clarke,I.,Sandberg,O.,Wiley,B.,Hong,T.W.:Freenet:A distributed anonymous information storage and retrieval system.Workshop on Design Issues in Anonymity and Unobservability,pages 46-66(2000).

[6] 樂光學(xué),李仁發(fā),周祖德.基于Region多層結(jié)構(gòu)P2P計算網(wǎng)絡(luò)模型[J].軟件學(xué)報.2005,16(6):1140-1150.