趙開新，魏 勇，王東署

（1.河南機(jī)電高等?？茖W(xué)校，河南 新鄉(xiāng) 453002；2.鄭州大學(xué)電氣工程學(xué)院，鄭州 450001）

改進(jìn)蟻群算法在P2P網(wǎng)絡(luò)資源搜索中的應(yīng)用*

趙開新1，魏 勇1，王東署2

（1.河南機(jī)電高等專科學(xué)校，河南 新鄉(xiāng) 453002；2.鄭州大學(xué)電氣工程學(xué)院，鄭州 450001）

針對P2P網(wǎng)絡(luò)搜索算法中冗余查詢消息過多，資源搜索效率低的問題，提出了基于改進(jìn)蟻群算法的P2P資源搜索算法，算法中在選擇鄰節(jié)點查詢時，綜合考慮到本地資源情況、鄰節(jié)點資源情況、鄰節(jié)點資源相似度等因素，盡量避開了資源搜索中的惡意節(jié)點，并改進(jìn)了基本蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則，從而避免了查詢消息的盲目發(fā)送。仿真實驗表明，與傳統(tǒng)資源搜索算法K-radom-walks和Flooding相比，該算法在搜索命中率和帶寬利用率方面有明顯提高。

改進(jìn)蟻群算法，P2P，資源搜索，查詢消息

0 引言

P2P技術(shù)已經(jīng)廣泛應(yīng)用于科學(xué)計算、即時消息傳遞和資源共享等領(lǐng)域，其中應(yīng)用最廣泛的是資源共享，而資源搜索機(jī)制的好壞在很大程度上決定了P2P網(wǎng)絡(luò)資源共享的成功與否，因此，有效的資源搜索機(jī)制是P2P網(wǎng)絡(luò)發(fā)展和應(yīng)用的核心技術(shù)之一［1-2］。P2P網(wǎng)絡(luò)中節(jié)點可以自由地加入或退出，資源分散地分布在網(wǎng)絡(luò)中各節(jié)點，每個節(jié)點既可以從其它節(jié)點獲得資源，也可以為其他節(jié)點提供資源，這使P2P網(wǎng)絡(luò)中資源處于不斷的動態(tài)變化中，增加了P2P網(wǎng)絡(luò)資源搜索技術(shù)的難度［3-4］，因此，有必要對P2P資源搜索技術(shù)進(jìn)行研究，以便更準(zhǔn)確、高效地搜索到用戶所需資源，本文把改進(jìn)蟻群算法的思想引入到P2P資源搜索過程中，縮小了查詢信息的轉(zhuǎn)發(fā)范圍，減少了查詢信息的轉(zhuǎn)發(fā)量，提高了P2P網(wǎng)絡(luò)帶寬利用率和資源搜索效率。

1 P2P網(wǎng)絡(luò)的資源搜索

1.1 P2P網(wǎng)絡(luò)的搜索機(jī)制

P2P網(wǎng)絡(luò)可以被看成由許多節(jié)點組成的一個無向圖，無向圖中的頂點由動態(tài)加入或者離開的節(jié)點組成，頂點中存放著各種共享資源，網(wǎng)絡(luò)中頂點之間的66連線組成了圖中的搜索路徑，若兩個頂點之間有直連線，說明兩頂點是相鄰節(jié)點，當(dāng)用戶提交資源搜索請求時，源節(jié)點首先在本地進(jìn)行資源查找，若找到，把搜索結(jié)果返回給用戶，否則，該節(jié)點把該資源查詢信息轉(zhuǎn)發(fā)給其相鄰的一個或多個節(jié)點，若鄰節(jié)點存在著所搜索的資源，則把該資源立即返回給用戶。否則，將資源查詢消息向其鄰節(jié)點繼續(xù)轉(zhuǎn)發(fā)，直至找到所搜索的資源或者遍歷完所有節(jié)點而所搜索的資源沒有被找到［5-6］。

1.2 P2P網(wǎng)絡(luò)的搜索機(jī)制存在的問題

P2P網(wǎng)絡(luò)中由于節(jié)點不斷地加入或離開，使得網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不斷發(fā)生變化，如何準(zhǔn)確定位到所查找的資源是P2P網(wǎng)絡(luò)資源共享的一個難點［7-8］，現(xiàn)有的資源搜索機(jī)制主要以泛洪和隨機(jī)漫步為主，泛洪搜索機(jī)制存在著查詢盲目性，并會在網(wǎng)絡(luò)中產(chǎn)生大量的查詢信息而占用網(wǎng)絡(luò)中大量的帶寬，隨機(jī)漫步算法隨機(jī)向K個鄰節(jié)點轉(zhuǎn)發(fā)查詢信息，減少了查詢信息的轉(zhuǎn)發(fā)量，但K個節(jié)點的選擇仍然具有盲目性，導(dǎo)致搜索效率不如泛洪好，并且對網(wǎng)絡(luò)中的惡意節(jié)點行為考慮不足。

2 改進(jìn)蟻群算法在P2P網(wǎng)絡(luò)中的應(yīng)用

2.1 問題分析

P2P網(wǎng)絡(luò)資源搜索模型，可以看作一個由多個蟻穴和連接這些蟻穴的通路共同構(gòu)成的網(wǎng)絡(luò)。在此網(wǎng)絡(luò)中進(jìn)行資源搜索類似于螞蟻尋找食物，每一只搜尋食物的螞蟻相當(dāng)于一個查詢信息，待搜索的資源看作螞蟻尋找的食物，存儲待搜索的資源節(jié)點看作食物源。螞蟻從蟻穴尋找食物的過程，就是用戶發(fā)送資源請求在P2P網(wǎng)絡(luò)中搜尋資源的過程，螞蟻在尋找食物的過程中選擇下一個節(jié)點時，會根據(jù)各路徑上信息素濃度，選擇一條離食物最近路徑進(jìn)行搜索，當(dāng)螞蟻找到了搜尋食物的最佳路徑，也就找到了資源搜索的最佳路徑。

2.2 蟻群算法的改進(jìn)

基本蟻群算法存在著時間復(fù)雜度大，容易出現(xiàn)停滯等缺陷，并且在資源搜索的過程中過分依賴信息素濃度，導(dǎo)致過早地生成最優(yōu)路徑，易得出局部最優(yōu)解，并且P2P網(wǎng)絡(luò)中搜索路徑的選擇不僅依靠信息素的濃度，還要考慮到節(jié)點資源相似度，網(wǎng)絡(luò)中是否存在惡意節(jié)點等。所以需要對基本蟻群算法進(jìn)行改進(jìn)后，才能應(yīng)用到P2P網(wǎng)絡(luò)資源搜索過程中。

2.2.1 信息素濃度的更新

在P2P網(wǎng)絡(luò)中，選擇鄰節(jié)點搜索時不僅要考慮到節(jié)點信息素濃度，還需考慮節(jié)點資源的相似度，令P1為：

其中τij是路徑eij上的信息素濃度，ηij是路徑的啟發(fā)式因子，即節(jié)點資源的相似度，φ為信息素衰減因子，改進(jìn)后的信息素局部更新如式（2）。

令P2為：

其中Sgbest為全局最優(yōu)路徑信息素，信息素的全局更新公式如式（4）。

其中ρ為信息素?fù)]發(fā)因子，當(dāng)螞蟻每完成一次搜索后，所經(jīng)過路徑上的信息素都會揮發(fā)，此機(jī)制可以使螞蟻盡量探索未訪問過的路徑，避免了算法的早熟現(xiàn)象，具有較高τ和η的路徑又會被優(yōu)先遍歷。

2.2.2 惡意節(jié)點的懲罰

如果網(wǎng)絡(luò)中存在著惡意的服務(wù)節(jié)點，那么在資源搜索時要盡量避開，這可以通過對路徑上的信息素值進(jìn)行修改進(jìn)行實現(xiàn)，根據(jù)惡意節(jié)點離本節(jié)點的距離不同，可以對各條路徑設(shè)置不同的懲罰力度，本文定義的距離因素如式（5）。

式（5）中L是整個路徑的實際長度，dij是從本節(jié)點到目標(biāo)節(jié)點的距離，懲罰后的信息素值如式（6）。其中φ為信息素懲罰因子。

2.2.3 螞蟻狀態(tài)的轉(zhuǎn)移規(guī)則

位于節(jié)點i的螞蟻根據(jù)式（7）選擇下一節(jié)點j，其中j為從式（8）給出的概率分布選出的一個隨機(jī)變量［9-10］。

式（7）中q為大于0小于1的一個隨機(jī)數(shù)，值的大小決定下一個節(jié)點選擇是在已經(jīng)過的較優(yōu)路徑上，還是未探索的新的路徑上，q0是確定選擇某個最有希望訪問的節(jié)點概率，當(dāng)q≤q0時，由啟發(fā)信息和信息素濃度共同決定下一個節(jié)點的選擇，當(dāng)q＞q0時，由基本蟻群算法選擇下一個待搜索的節(jié)點，引導(dǎo)算法趨向收斂。蟻群算法轉(zhuǎn)移規(guī)則的改進(jìn)，避免了螞蟻僅根據(jù)信息素濃度選擇路徑，增強(qiáng)了算法的隨機(jī)搜索性能，擴(kuò)大了搜索范圍，有效避免了算法過早陷入局部最優(yōu)。

2.3 相關(guān)描述

把改進(jìn)的蟻群算法應(yīng)用到P2P網(wǎng)絡(luò)資源搜索中，網(wǎng)絡(luò)中的每個節(jié)點，需要存儲3個表，分別是本地共享資源表、資源緩存表和信息素表，其中本地共享資源表，保存本地共享的所有資源，包括資源ID，資源分類名，關(guān)鍵詞以及關(guān)鍵詞在該資源中的權(quán)重等信息，資源緩存表保存近期被本地用戶訪問過的非本地資源的實際節(jié)點地址，當(dāng)多次訪問同一資源信息時，用戶可以從該表中直接找到該資源所在的節(jié)點獲得所需資源。信息素表是一個M×N的二元矩陣，其中，M表示最近由此節(jié)點發(fā)起或由其他鄰節(jié)點轉(zhuǎn)發(fā)過的所查詢關(guān)鍵字的總數(shù)，N表示當(dāng)前節(jié)點Pi所有鄰節(jié)點個數(shù)，矩陣中的值τkn表示節(jié)點Pi到鄰節(jié)點Pn路徑上關(guān)于關(guān)鍵詞k的信息素濃度的大小，ηkn表示點Pi在鄰節(jié)點Pn上所獲資源與所查找資源的相似度，其取值在0和1之間，初始階段所有節(jié)點間關(guān)鍵詞K的信息素值為最小值Kmin，資源相似度ηkn為0，如表1所示。

表1 信息素表

2.4 算法的步驟

Step1：節(jié)點i收到關(guān)鍵字為K的資源查詢信息時，首先在本地查詢共享資源表、資源緩存表，若找到了所要搜索的資源，則執(zhí)行步驟Step5。否則執(zhí)行步驟Step2。

Step2：根據(jù)公式狀態(tài)轉(zhuǎn)移式（7）、式（8）選擇下一個待搜索的節(jié)點j，當(dāng)螞蟻到達(dá)節(jié)點j后，首先查詢j節(jié)點共享資源表、資源緩存表，若找到了所要搜索的資源，則執(zhí)行步驟Step5，否則，搜索螞蟻將自己剛訪問過的節(jié)點加入到自己的禁忌表中，根據(jù)信息素表中信息素和節(jié)點相似度選擇下一個節(jié)點。

Step3：每個節(jié)點經(jīng)過一個t時間間隔，通過式（2）、式（4）進(jìn)行信息素的揮發(fā)操作。

Step4：若網(wǎng)絡(luò)中的節(jié)點都已被遍歷，并沒有找到所搜索的資源則搜索失敗，算法結(jié)束。

Step5：生成返回螞蟻，沿原路反饋給源節(jié)點，并根據(jù)式（2）、式（4）修改搜索路徑上各節(jié)點關(guān)鍵字為K的信息濃度τ和節(jié)點資源相似度η，源節(jié)點螞蟻根據(jù)反饋的路徑，去搜索所需的資源，搜索算法結(jié)束。

3 仿真實驗

實驗中采用均勻隨機(jī)圖作為網(wǎng)絡(luò)拓?fù)?，設(shè)非結(jié)構(gòu)化網(wǎng)絡(luò)中有5 000個網(wǎng)絡(luò)對等體節(jié)點，在5 000個節(jié)點中隨機(jī)選擇1 000個節(jié)點放置查詢資源，P2P網(wǎng)絡(luò)中共有50種不同的資源，隨機(jī)給每個節(jié)點分配20個資源，蟻群算法中信息啟發(fā)算子α和期望啟發(fā)算子β分別為0.5，0.6；信息素?fù)]發(fā)因子ρ=0.65，信息素衰減因子φ=0.5，仿真實驗中搜索算法分別采用改進(jìn)的蟻群算法（Improved ant），隨機(jī)漫步算法（K-radom-walks）和泛洪算法（Flooding），從搜索的命中率、搜索的平均響應(yīng)時間和網(wǎng)絡(luò)帶寬利用率3個方面，來比較3種搜索算法的性能。

圖1 搜索命中率

由圖1可以看出，在搜索的初始階段，與K-radom-walks、Flooding算法相比，改進(jìn)的蟻群算法的搜索命中率提高并不明顯，但隨著系統(tǒng)時間的推移，改進(jìn)蟻群算法搜索命中率增加的速度明顯大于K-radom-walks和Flooding，并且最后保持一個較高的命中率狀態(tài)，因為隨著時間的推移，節(jié)點根據(jù)本地存儲的共享資源表、資源緩存表和信息素表的信息找到了搜索資源的較優(yōu)路徑，所以搜索效率有明顯的提高，而K-radom-walks、Flooding算法中查詢消息的轉(zhuǎn)發(fā)路徑存在一定的盲目性，查詢消息的轉(zhuǎn)發(fā)路徑不會根據(jù)歷史查詢信息進(jìn)行動態(tài)調(diào)整，所以搜索的命中率和系統(tǒng)運行的時間相關(guān)性不大。

圖2 平均發(fā)送查詢消息數(shù)

由圖2可以看出，F(xiàn)looding算法平均發(fā)送的查詢消息量最大，K-radom-walks次之，改進(jìn)蟻群算法最少，因為Flooding將查詢消息發(fā)給自己所有的鄰節(jié)點，而K-radom-walks將查詢消息發(fā)給K個鄰節(jié)點，所以查詢消息量有所減少，而改進(jìn)的蟻群算法利用信息素參數(shù)來指導(dǎo)節(jié)點選擇概率大的路徑進(jìn)行搜索，且有自我學(xué)習(xí)的功能，并能夠盡量避免惡意節(jié)點，減少查詢信息的轉(zhuǎn)發(fā)量，從而提高了帶寬的利用率。

圖3 平均響應(yīng)時間

由圖3可以看出，在資源數(shù)相同的情況下，F(xiàn)looding算法所需平均響應(yīng)時間最短，而K-radom-walks最長，改進(jìn)的蟻群算法位于兩者之間。由于Flooding算法向所有鄰節(jié)點轉(zhuǎn)發(fā)查詢信息，所以能夠也在較短時間內(nèi)得到響應(yīng)，但這種響應(yīng)時間短是以發(fā)送大量查詢包，占用大量帶寬為代價的。而K-radom-walks算法由于是隨機(jī)選擇K個鄰節(jié)點進(jìn)行轉(zhuǎn)發(fā)查詢包，所以這種查詢的盲目性的代價是響應(yīng)速度的降低。而改進(jìn)的蟻群算法利用信息素來指導(dǎo)查詢消息的轉(zhuǎn)發(fā)，并通過對惡意節(jié)點進(jìn)行懲罰，盡量避開了查詢概率小的節(jié)點和路徑，因此，可以在發(fā)送較少查詢信息的情況下，快速查詢到滿足條件的資源，從而減少了查詢的響應(yīng)時間。

4 結(jié)束語

針對P2P網(wǎng)絡(luò)搜索算法存在的冗余查詢消息占用大量網(wǎng)絡(luò)帶寬，搜索效率降低的問題，提出了一種基于改進(jìn)蟻群算法的P2P網(wǎng)絡(luò)搜索算法，算法中在查詢節(jié)點的選擇時，綜合考慮本地資源情況、鄰節(jié)點資源的情況、鄰節(jié)點資源的相似度，以及鄰節(jié)點是否惡意節(jié)點的情況，從而避免了查詢消息的盲目發(fā)送，提高了搜索的效率。仿真實驗證明，與傳統(tǒng)資源搜索算法K-radom-walks和Flooding相比，隨著時間的推移本文提出的算法搜索命中率和帶寬利用率有了明顯提高，而資源的平均響應(yīng)時間本文提出的算法比Flooding算法稍有增加，因此，降低資源平均響應(yīng)時間，是本算法進(jìn)一步改進(jìn)的方向。

［1］黃海.p2p網(wǎng)絡(luò)技術(shù)研究現(xiàn)狀與展望［J］.計算機(jī)科學(xué)，2012，39（6）：178-183.

［2］錢寧，吳國新.無結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源搜索機(jī)制研究綜述［J］.計算機(jī)科學(xué)，2010，37（4）：7-10.

［3］高磊.基于信任迭代的P2P網(wǎng)絡(luò)信任管理模型［J］.計算機(jī)工程，2012，38（19）：92-95.

［4］周蓮英，閆報.p2p網(wǎng)絡(luò)中基于蟻群算法的資源搜索研究［J］.計算機(jī)工程與設(shè)計，2012，33（1）：32-35.

［5］彭建，周歡.非結(jié)構(gòu)化p2p網(wǎng)絡(luò)資源搜索改進(jìn)算法［J］.計算機(jī)工程與設(shè)計，2012，33（11）：4071-4075.

［6］黎梨苗.基于優(yōu)先權(quán)的P2P網(wǎng)絡(luò)信任模型［J］.計算機(jī)工程，2013，39（5）：148-151.

［7］陳珊珊.P2P網(wǎng)絡(luò)中基于權(quán)重因素的信任模型［J］.計算機(jī)應(yīng)用，2013，33（6）：1612-1614.

［8］陳光喜.基于改進(jìn)粒子群算法的P2P流媒體數(shù)據(jù)調(diào)度策略［J］.計算機(jī)應(yīng)用，2013，33（4）：931-934.

［9］李春秀.基于蟻群算法的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源搜索策略［J］.計算機(jī)工程與應(yīng)用，2012，48（4）：97-99.

［10］蔡康.基于改進(jìn)型蟻群算法的P2P網(wǎng)絡(luò)資源搜索的研究［J］.電信科學(xué)，2013（3）：34-42.

［11］雷磊，周青松.基于小生境遺傳算法的干擾資源調(diào)度研究［J］.現(xiàn)代防御技術(shù)，2014，42（1）：94-99.

Study on Resource Search in P2P Networks Based on Improved Ant Algorithm

ZHAO Kai-xin1，WEI Yong1，WANG Dong-shu2
（1.Henan Mechanical and Electrical Engineering College，Xinxiang 453002，China；
2.Electrical Engineering School of Zhengzhou University，Zhengzhou 450001，China）

For many redundant messages resources search algorithm and low efficiency issues in P2P network，the P2P resource search algorithm based on improved ant colony algorithm is proposed in this paper.The local resources，the neighbor node resources，the neighbor node resource similarity factors in selecting query neighbor are considered，avoiding the malicious node in resources searching as far as possible.And the basic ant colony algorithm state transition rules is improved.Query messages blind sending is avoiding.Simulation results shows the algorithm in search hit rate and bandwidth utilization improved obviously compare with traditional resource search algorithm K-radom-walks and Flooding.

improved ant colony algorithm，peer-to-peer，resource search，query message

TP391.41

A

1002-0640（2015）05-0139-04

2014-03-05

2014-04-17

國家自然科學(xué)基金（61174085）；高等學(xué)校博士學(xué)科點專項科研基金資助項目（20114101110005）

趙開新（1979- ），男，河南項城人，碩士。研究方向：路徑規(guī)劃技術(shù)、計算機(jī)網(wǎng)絡(luò)技術(shù)。