前言：本站為你精心整理了淺談計(jì)算機(jī)資源搜索的具體算法范文，希望能為你的創(chuàng)作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

1概述

近年來，利用空間上的局部性即將擁有相似資源的節(jié)點(diǎn)聚集成簇，建立不同的興趣域，實(shí)現(xiàn)資源的簇內(nèi)和簇外搜索；文獻(xiàn)中利用節(jié)點(diǎn)的信任度，提出一種激勵機(jī)制，將查詢消息轉(zhuǎn)發(fā)到信任度高的節(jié)點(diǎn)；文獻(xiàn)中引入空間向量模型，根據(jù)非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中節(jié)點(diǎn)保存的資源信息將節(jié)點(diǎn)劃分為不同的興趣域，通過興趣域進(jìn)行資源搜索。文獻(xiàn)采用分組思想，將P2P網(wǎng)絡(luò)劃分成不同的興趣組，興趣組中由中心節(jié)點(diǎn)進(jìn)行統(tǒng)一管理，并且提出了備用中心節(jié)點(diǎn)，減少了單點(diǎn)失效對系統(tǒng)造成的危害；文獻(xiàn)在P2P網(wǎng)絡(luò)資源搜索中引入蟻群算法，利用節(jié)點(diǎn)信息素和蟻群的正反饋機(jī)制智能地選擇下一跳路由。本文在以上研究的基礎(chǔ)上，提出一種基于興趣因子的蟻群資源搜索算法（AntColonyOptimizationBasedonInterestFactor，IACO），通過分析節(jié)點(diǎn)價值對資源搜索性能的影響，在蟻群算法中引入節(jié)點(diǎn)的興趣因子，動態(tài)調(diào)整節(jié)點(diǎn)價值和信息素在計(jì)算轉(zhuǎn)發(fā)概率時的權(quán)重關(guān)系，選擇概率大的鄰居節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)，在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中實(shí)現(xiàn)了資源的智能查找。最后通過仿真實(shí)驗(yàn)對該算法的性能進(jìn)行了驗(yàn)證。

2傳統(tǒng)的蟻群算法蟻群算法

經(jīng)研究發(fā)現(xiàn)，自然界中的螞蟻在找尋食物時呈現(xiàn)一定的規(guī)律性，在這個過程中它們會留下一種類似于信息素的物質(zhì)，用來指導(dǎo)后續(xù)螞蟻的覓食行為，以后的螞蟻會感知路徑中的信息素濃度來指導(dǎo)自己的下一步搜索行為。所有的螞蟻都會朝信息素濃度高的路徑搜素，這種基于信息素的正反饋機(jī)制，使得某一路徑上的信息素濃度越來越大，因此它被選擇搜索的概率也逐漸變大，搜索的螞蟻也就越多。螞蟻的這種集體激勵機(jī)制可以啟發(fā)式的促使較短的路徑優(yōu)先被選擇。研究發(fā)現(xiàn)螞蟻的這種智能行為比較適合P2P這種動態(tài)網(wǎng)絡(luò)的資源搜索。因此，蟻群算法被越來越多的應(yīng)用于非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的資源搜索中。文獻(xiàn)在P2P網(wǎng)絡(luò)資源搜索中引入蟻群算法，按照資源中的關(guān)鍵字將信息素分類，通過不同的信息素智能地選擇下一跳路由。文獻(xiàn)利用蟻群算法的正反饋機(jī)制，充分考慮了鄰居節(jié)點(diǎn)度和鄰居-鄰居節(jié)點(diǎn)信息，降低了在搜索過程中形成環(huán)路的概率，減少了網(wǎng)絡(luò)中的冗余消息量。通過研究發(fā)現(xiàn)當(dāng)前這些算法并沒有克服蟻群算法搜索初期資源查詢效率低的問題，很少考慮到節(jié)點(diǎn)價值以及所要查詢的資源與節(jié)點(diǎn)的興趣之間的相似性對資源搜索的影響，而本文的研究則正是基于此展開的。

3相關(guān)描述

3.1節(jié)點(diǎn)價值

算法都是試探性的搜索，在相同的時間內(nèi)資源搜索覆蓋度越高，則搜索成功率也就越高。本文假定在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的資源是隨機(jī)分布的，資源搜索覆蓋度指的是單位時間內(nèi)搜索到的資源數(shù)量，其中節(jié)點(diǎn)的度數(shù)和共享資源數(shù)是決定資源搜索覆蓋度的兩個重要因素。非結(jié)構(gòu)化P2P網(wǎng)絡(luò)是一個巨大的動態(tài)網(wǎng)絡(luò)，我們很難知道其中的一個節(jié)點(diǎn)相對于整個網(wǎng)絡(luò)的“全局價值”，所以我們把一個節(jié)點(diǎn)在其鄰居節(jié)點(diǎn)中的“局部價值”作為該節(jié)點(diǎn)的當(dāng)前價值。非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的資源搜索因?yàn)樵赑2P網(wǎng)絡(luò)中度數(shù)高的節(jié)點(diǎn)可以確保消息在下一跳轉(zhuǎn)發(fā)到相對多的節(jié)點(diǎn)，而共享資源多的節(jié)點(diǎn)可以保證查詢消息在當(dāng)前查詢到相對多的資源，這些都大大地增加了資源查詢的命中概率。因此，用節(jié)點(diǎn)度數(shù)和擁有的資源數(shù)來表示該節(jié)點(diǎn)的價值，指導(dǎo)生成資源查詢路徑。

3.2興趣因子

在資源搜索的不同階段，為了動態(tài)調(diào)整節(jié)點(diǎn)價值和信息素在轉(zhuǎn)發(fā)概率中的比重關(guān)系，提高資源的查詢效率，本文在蟻群算法中引入了節(jié)點(diǎn)的興趣因子，用興趣因子來表示一個節(jié)點(diǎn)當(dāng)前的查詢請求與一段時間內(nèi)歷史記錄表中記錄的查詢請求之間的相似度。經(jīng)文獻(xiàn)研究表明，P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)在資源查詢時會呈現(xiàn)一定的特點(diǎn)，即節(jié)點(diǎn)感興趣的內(nèi)容往往會表現(xiàn)出一定的集中性，很多節(jié)點(diǎn)在一段時間內(nèi)會對某一個主題的內(nèi)容表現(xiàn)出一定的興趣，因此，可以通過歷史記錄表來得到當(dāng)前的查詢請求與過去一段時間內(nèi)該節(jié)點(diǎn)的查詢請求之間的相似度，將這個相似度作為節(jié)點(diǎn)的“興趣因子”，來決定節(jié)點(diǎn)價值和信息素之間的權(quán)重關(guān)系。如果興趣因子比較大，則說明當(dāng)前查詢的資源在過去的一段時間內(nèi)出現(xiàn)過的概率比較大，該資源在路徑上留下的信息素會比較多，此時信息素在轉(zhuǎn)發(fā)概率中所占的比重會比較大；反之，該資源在過去一段時間很有可能沒有被請求過，則節(jié)點(diǎn)的價值所占的比重會比較大，查詢消息會被轉(zhuǎn)發(fā)到存在該資源可能性較大的節(jié)點(diǎn)上。在資源搜索過程中，查詢請求中可以包含多個關(guān)鍵字，這些關(guān)鍵字往往可以表現(xiàn)出一定的興趣，因此我們可以用興趣域來分別表示當(dāng)前查詢請求和節(jié)點(diǎn)歷史查詢的興趣類型。興趣域用關(guān)鍵字出現(xiàn)的頻率wi組成的特征向量d來表示，其中d=（w1,w2,…,wn），所以查詢請求q的興趣域用特征向量表示為NE（q）=（wq,1,wq,2,…,wq,n），節(jié)點(diǎn)j的興趣域NE（j）=（wj,1,wj,2,…,wj,n），其中n表示關(guān)鍵字集合。在系統(tǒng)運(yùn)行的初期，路徑上的信息素濃度均為min，此時信息素濃度并不能很好的指導(dǎo)資源的查詢，加入興趣因子，提高節(jié)點(diǎn)價值在轉(zhuǎn)發(fā)概率中的比重，可以更好的形成有效的查詢路徑，很好的解決了傳統(tǒng)蟻群算法初期資源搜索效率低的缺點(diǎn)，保證了算法自始至終的有效性，提高了系統(tǒng)在整個搜索周期中的效率。P2P網(wǎng)絡(luò)是一個動態(tài)的網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點(diǎn)和信息實(shí)時的發(fā)生變化，所以不同時間內(nèi)節(jié)點(diǎn)的興趣因子也不一樣。為了保證節(jié)點(diǎn)興趣因子的實(shí)時性，則需要實(shí)時更新節(jié)點(diǎn)歷史記錄表表中記錄的信息。為節(jié)點(diǎn)每一次保存的歷史記錄增加更新時間戳，當(dāng)節(jié)點(diǎn)的歷史記錄表存滿數(shù)據(jù)時，則根據(jù)記錄的更新時間戳將距離當(dāng)前時間最久的記錄置換出表外，以此來保證數(shù)據(jù)表中記錄的實(shí)時性和動態(tài)性，確保在不同的查詢階段節(jié)點(diǎn)興趣因子的實(shí)時性，使得IACO算法的效率和優(yōu)勢得到很好的保證。

作者:房佩閆向龍良梓吳曉軍單位：陜西師范大學(xué)