淺談計算機資源搜索的具體算法

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

1概述

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

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

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

3相關描述

3.1節(jié)點價值

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

3.2興趣因子

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

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