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

田 濤

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

1.2 Nest

對(duì)等網(wǎng)中的Peer用蟻群系統(tǒng)中的節(jié)點(diǎn)Nest代替，對(duì)等網(wǎng)由大量互相連接的Nest構(gòu)成。由圖1可知每個(gè)Nest由3個(gè)模塊組成：螞蟻調(diào)度器、通訊傳輸層和資源管理器。每個(gè)組成模塊完成不同的功能，圖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)新加入對(duì)等網(wǎng)的Nest，將其插入當(dāng)前Nest的鄰居列表；網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)管理；負(fù)責(zé)螞蟻在對(duì)等網(wǎng)中各Nest之間的移動(dòng)。設(shè)計(jì)中，為每個(gè)Nest設(shè)置唯一的標(biāo)識(shí)符。Nest在和遠(yuǎn)程N(yùn)est進(jìn)行通訊時(shí)，需確認(rèn)對(duì)方的標(biāo)識(shí)符，所有操作均依賴Nest標(biāo)識(shí)符。同時(shí)，引入鄰居Nest的概念：當(dāng)一組Nest都清楚同一個(gè)Nest的標(biāo)識(shí)符時(shí)，這組Nest被稱為當(dāng)前Nest的鄰居節(jié)點(diǎn)。需注意的是，引入鄰居Nest的概念不包含任何距離量度。鄰居Nest的收集充分說(shuō)明了對(duì)等網(wǎng)絡(luò)的高度動(dòng)態(tài)性。3）資源管理器：Nest通過(guò)一個(gè)或更多的資源管理器對(duì)到訪的Ant進(jìn)行資源分配并管理共享資源。

1.3 Ant

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

1.4 消息

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

1.5 螞蟻的行為

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

2 對(duì)等網(wǎng)仿真模型的實(shí)現(xiàn)及測(cè)試

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

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

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

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

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

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

2.3 仿真結(jié)果

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

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

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

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

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

3 結(jié)論

仿真結(jié)果證明J對(duì)等網(wǎng)仿真模型設(shè)計(jì)的正確性。本文對(duì)等網(wǎng)仿真模型的設(shè)計(jì)基于蟻群算法，優(yōu)勢(shì)在于只需對(duì)單個(gè)螞蟻行為的簡(jiǎn)單設(shè)計(jì)即可獲得整體的智能性；只需將不同的P2P系統(tǒng)協(xié)議用螞蟻算法實(shí)現(xiàn)，通過(guò)仿真模型提供的接口即可實(shí)現(xiàn)仿真，適應(yīng)于各類(lèi)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] 樂(lè)光學(xué),李仁發(fā),周祖德.基于Region多層結(jié)構(gòu)P2P計(jì)算網(wǎng)絡(luò)模型[J].軟件學(xué)報(bào).2005,16(6):1140-1150.