（成都理工大學(xué)工程技術(shù)學(xué)院 樂山 614000）

1 引言

非結(jié)構(gòu)化對等網(wǎng)絡(luò)系統(tǒng)以其結(jié)構(gòu)簡單、易于組織大規(guī)模網(wǎng)絡(luò)資源共享而得到廣泛應(yīng)用。資源的搜索效率決定了系統(tǒng)的可用性和系統(tǒng)的關(guān)鍵性。平面對等結(jié)構(gòu)由多層組成，分為上層節(jié)點(diǎn)管理部分、下層節(jié)點(diǎn)部分以及同層節(jié)點(diǎn)相互連接部分。如文獻(xiàn)［1］中使用超級節(jié)點(diǎn)，在一定程度上緩解了流量問題，但超級節(jié)點(diǎn)可能會(huì)導(dǎo)致該區(qū)域內(nèi)的單點(diǎn)故障，并成為系統(tǒng)性能的瓶頸。隨機(jī)Walker搜索是非結(jié)構(gòu)化對等網(wǎng)絡(luò)的另一種基本搜索方法，但由于其效率低，延遲時(shí)間過長因此該技術(shù)極少應(yīng)用。洪泛法是非結(jié)構(gòu)化對等網(wǎng)絡(luò)的初始基本搜索方法，由于開銷過大導(dǎo)致系統(tǒng)可擴(kuò)展性差［1］。

部分路由索引方法中，路由索引只維護(hù)最流行的請求內(nèi)容索引，其他內(nèi)容則仍采用傳統(tǒng)的擴(kuò)散方法。選擇性路由可以搜索方向，搜索結(jié)果的基礎(chǔ)選擇的目的可以是索引，也可以是節(jié)點(diǎn)之間存儲(chǔ)的內(nèi)容之間的階段以及其他歷史信息。分類節(jié)點(diǎn)和資源的目的是縮小搜索范圍，加快搜索速度，分類可以基于地理、單位、興趣或內(nèi)容。節(jié)點(diǎn)分為多個(gè)組，每個(gè)節(jié)點(diǎn)屬于不同的類別，每個(gè)節(jié)點(diǎn)類別形成一個(gè)相對獨(dú)立的邏輯網(wǎng)絡(luò)，搜索消息只與搜索內(nèi)容相關(guān)的邏輯網(wǎng)絡(luò)泛濫有關(guān)，從而減少了搜索范圍，在一定程度上減少了冗余流量。采用分層與分類相結(jié)合的方法，將節(jié)點(diǎn)劃分為超級節(jié)點(diǎn)，刪除門節(jié)點(diǎn)和本地節(jié)點(diǎn)。根據(jù)網(wǎng)絡(luò)分層分類的主題，不同類型的節(jié)點(diǎn)分布在不同的層次上。概率路由表用于根據(jù)路由表維護(hù)鄰居信息。搜索請求可以以更高的概率和更短的路徑到達(dá)目的地節(jié)點(diǎn)。一些研究人員利用基于興趣的分組和引導(dǎo)請求來降低帶寬消耗［2］。緩存和多個(gè)副本策略可以提高系統(tǒng)的可伸縮性。結(jié)合統(tǒng)一和相稱的資源復(fù)制方法，通過控制副本的放置來降低搜索范圍，具體取決于所請求的比率和固定副本的分配比率［2］。

以上對等系統(tǒng)提出了多種方式來提高搜索效率，但仍存在重復(fù)消息，搜索效率低或延遲等問題。在本文中，我們提出了一個(gè)基于K均值搜索樹的非結(jié)構(gòu)化搜索模型。該模型構(gòu)建基于K樹的搜索結(jié)構(gòu)，并采用升降機(jī)制。根據(jù)查詢命中率排列樹中每個(gè)節(jié)點(diǎn)的位置，并在樹的上層設(shè)置權(quán)重較大的節(jié)點(diǎn)，以使系統(tǒng)中的節(jié)點(diǎn)有規(guī)律地分布，上層的節(jié)點(diǎn)越多節(jié)日，有熱點(diǎn)的可能性越大。并且使用建立搜索結(jié)果的歷史索引，并且搜索啟動(dòng)一個(gè)節(jié)點(diǎn)索引，緩存上層節(jié)點(diǎn)，部分覆蓋資源拷貝，并且是葉節(jié)點(diǎn)增加遠(yuǎn)端鄰居等方法，進(jìn)一步提高搜索效率和平衡性負(fù)面包含。分析和仿真結(jié)果表明，我們可以顯著減少低效率流量并提高搜索效率，而搜索樹維護(hù)開銷非常小。

2 K樹模型

非結(jié)構(gòu)化對等系統(tǒng)拓?fù)浣Y(jié)構(gòu)是一個(gè)冪律分布和高度聚合的邏輯網(wǎng)絡(luò)。在維護(hù)系統(tǒng)結(jié)構(gòu)完整性、可靠性以及容錯(cuò)性方面，原有網(wǎng)絡(luò)具有良好的性能，因此仍然保留原有網(wǎng)絡(luò)的存在。在樹狀結(jié)構(gòu)中，節(jié)點(diǎn)的鄰居只有父節(jié)點(diǎn)，子節(jié)點(diǎn)和極少數(shù)的冗余節(jié)點(diǎn)，節(jié)點(diǎn)度很小，系統(tǒng)結(jié)構(gòu)維護(hù)成本很小，并且在搜索請求被傳播。而原有網(wǎng)絡(luò)基于搜索效率低，流量效率低下，因此原有網(wǎng)絡(luò)構(gòu)建K樹進(jìn)行資源搜索。進(jìn)一步優(yōu)化樹的搜索屬性，為樹中的每個(gè)節(jié)點(diǎn)分配權(quán)重，并給節(jié)點(diǎn)定期排列權(quán)重，獲得K加權(quán)搜索樹。

定義1：如果滿足下列條件，樹就是K搜索樹［3］：

1）只有樹的底層和子層有節(jié)點(diǎn)少于K節(jié)點(diǎn)的葉節(jié)點(diǎn)；

2）每個(gè)節(jié)點(diǎn)最多有K個(gè)子節(jié)點(diǎn)；

3）對于任何節(jié)點(diǎn)，其權(quán)重小于或等于父節(jié)點(diǎn)的權(quán)重，并且大于或等于所有子節(jié)點(diǎn)的權(quán)重。

為了保證搜索樹結(jié)構(gòu)的可靠性和容錯(cuò)性，除了父節(jié)點(diǎn)和子節(jié)點(diǎn)之外，每個(gè)節(jié)點(diǎn)中都有少量的備份節(jié)點(diǎn)。假設(shè)系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)為N，節(jié)點(diǎn)i表示為Ni，Ni的子節(jié)點(diǎn)集合表示為S(i)，Ni的兄弟節(jié)點(diǎn)集合表示為B(i)，F(xiàn)(i)表示父節(jié)點(diǎn)集。根節(jié)點(diǎn)和第一個(gè)節(jié)點(diǎn)定義為備份節(jié)點(diǎn)，其他節(jié)點(diǎn)的備份節(jié)點(diǎn)為祖父節(jié)點(diǎn)。初始化搜索樹算法如下［3，11］：

3 上升下降算法

歷史查詢命中率是搜索樹中節(jié)點(diǎn)的權(quán)重，節(jié)點(diǎn)的權(quán)重是命中率，從節(jié)點(diǎn)加入系統(tǒng)到當(dāng)前查詢命中率的綜合評估值，反映了節(jié)點(diǎn)擁有網(wǎng)絡(luò)資源的熱量。從樹頂向下，節(jié)點(diǎn)命中率和穩(wěn)定性逐漸減小，上層節(jié)點(diǎn)資源越多，而非熱量資源越低，因?yàn)樵蕉?，這就提供了更加準(zhǔn)確的冷熱源分布，系統(tǒng)結(jié)構(gòu)趨于穩(wěn)定。任何節(jié)點(diǎn)的熱點(diǎn)區(qū)域的方向都可以很容易地確定，并且可以在很短的時(shí)間內(nèi)達(dá)到非熱點(diǎn)資源的節(jié)點(diǎn)，利用遠(yuǎn)程連接來增強(qiáng)它們之間的關(guān)系同樣可以提高不受歡迎資源的效率搜索。同時(shí)采取部分熱點(diǎn)資源復(fù)制，索引和上層節(jié)點(diǎn)緩存機(jī)制來進(jìn)一步提高搜索效率，同時(shí)解決部分節(jié)點(diǎn)負(fù)載較重導(dǎo)致的樹狀結(jié)構(gòu)發(fā)生。從較低層次加入新節(jié)點(diǎn)，頻繁接入系統(tǒng)，節(jié)點(diǎn)的總不穩(wěn)定性處于樹的較低層次，所以系統(tǒng)搜索性能的穩(wěn)定性可以得到保證。

設(shè)置節(jié)點(diǎn)到達(dá)系統(tǒng)時(shí)刻為0，每個(gè)時(shí)間段的長度為τ。在此期間的第 j次，達(dá)到Ci的次數(shù)表示為CN，其中命中次數(shù)為HN，Ri(j) 表示Ci在第 j次的命中率，α為命中率系數(shù)。

Wi(j)表示Ci在[0 ， jτ]期間的查詢命中率，表示如下：

根據(jù)文獻(xiàn)［3］結(jié)論。對于任何節(jié)點(diǎn)Ci，Wi(j)的值在0和1之間。

由于請求是在樹結(jié)構(gòu)中的節(jié)點(diǎn)的鄰居之間轉(zhuǎn)發(fā)的，因此相鄰節(jié)點(diǎn)接收到的請求數(shù)相近，因此相鄰節(jié)點(diǎn)的命中率具有可比性，命中率可以反映節(jié)點(diǎn)資源滿足請求的程度。

根據(jù)前述定義條件，當(dāng)節(jié)點(diǎn)的命中率發(fā)生變化或者被做成系統(tǒng)初始化過程時(shí)，需要對樹中的節(jié)點(diǎn)位置做適當(dāng)?shù)恼{(diào)整，調(diào)用整個(gè)過程稱為剝離過程，對應(yīng)于上升下降算法。從當(dāng)前層到上層的節(jié)點(diǎn)稱為升級，反之亦然。

對于節(jié)點(diǎn)Ci，父節(jié)點(diǎn)為Cf，兄弟節(jié)點(diǎn)Cb屬于集合兄弟節(jié)點(diǎn)(i)，子節(jié)點(diǎn)Cs屬于son(i)，每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)包含子節(jié)點(diǎn)及其自己的列表的表。上升和下降是逐步優(yōu)化搜索樹的過程。當(dāng)Ci高于兄弟和父節(jié)點(diǎn)的命中率時(shí)，Ci與父節(jié)點(diǎn)交換并更新一次。新添加到搜索樹中的節(jié)點(diǎn)始終位于樹的底部或子層作為葉節(jié)點(diǎn)。當(dāng)系統(tǒng)運(yùn)行一段時(shí)間時(shí)，搜索樹的結(jié)構(gòu)趨于相對穩(wěn)定，穩(wěn)定和可靠，命中率較高的節(jié)點(diǎn)總是位于樹的上層，穩(wěn)定但命中率低的節(jié)點(diǎn)不穩(wěn)定命中率高的節(jié)點(diǎn)，樹的相對中間層不穩(wěn)定，命中率低的節(jié)點(diǎn)位于樹的下層。

上升下降算法如下［13］：

1）如果Cs發(fā)現(xiàn)定時(shí)器變?yōu)榱悖瑒t計(jì)算最新的查詢命中率Ws，并通過發(fā)送消息新命中率給Ci，并更新命中率隊(duì)列，重置定時(shí)器。

2）Ci從Cs收到新命中率消息，取出消息Ws，并更新命中率隊(duì)列。如果Wi仍然是最大值，則查看命中率隊(duì)列中所有子節(jié)點(diǎn)的命中率，然后完成；否則實(shí)施更新。假設(shè)Cs的HR最大，則發(fā)送請求更新消息給Cs，請求上升和下降處理。

3）當(dāng)Cs收到請求更新消息時(shí)，如果同意升級，發(fā)送消息同意更新給Ci；否則發(fā)送拒絕更新消息。

4）如果Ci收到拒絕更新，則完成；否則開始上升和下沉操作：Cs以Cf作為新的父節(jié)點(diǎn)，并且Ci和{s o n(i)-Cs}指向一個(gè)子節(jié)點(diǎn)，原始的Cs子節(jié)點(diǎn)到Ci為新的父節(jié)點(diǎn)，算法結(jié)束。

4 K樹查詢算法

基本的搜索方法不會(huì)生成重復(fù)的消息，并且搜索延遲（跳躍）的上限是樹高度的兩倍。隨著系統(tǒng)運(yùn)行時(shí)間的增加，系統(tǒng)搜索樹逐漸趨于有序且相對穩(wěn)定，節(jié)點(diǎn)積累了一定的搜索體驗(yàn)信息，可以優(yōu)化搜索算法。

圖1 搜索效率比較

沒有可用的歷史搜索體驗(yàn)數(shù)據(jù)，或者在系統(tǒng)操作的初始狀態(tài)或在系統(tǒng)的短期內(nèi)不存在可用的歷史搜索體驗(yàn)數(shù)據(jù)或其他需求，該請求被轉(zhuǎn)發(fā)給所有鄰居，當(dāng)前節(jié)點(diǎn)的容錯(cuò)備份不參與搜索。搜索停止條件是TTL=0或搜索成功或沒有節(jié)點(diǎn)轉(zhuǎn)發(fā)?；镜乃阉鞣椒ú粫?huì)產(chǎn)生重復(fù)的消息，并且搜索延遲（跳躍）的上限是樹高度的兩倍。隨著系統(tǒng)運(yùn)行時(shí)間的增加，搜索樹逐漸趨于有序且相對穩(wěn)定，節(jié)點(diǎn)積累了一定的搜索體驗(yàn)信息，可以優(yōu)化搜索算法。

本文使用基于搜索結(jié)果索引的緩存策略來提高搜索效率［13］?；诨緮U(kuò)散和緩存索引，建立搜索算法，算法偽代碼如下：

BOOL SP（QR）｛//QR為搜索請求

dPN=RetriveRL（QR ，RL）；//在隊(duì)列RL中查找，dPN一個(gè)搜索成功的節(jié)點(diǎn)

if（dPN==Null）｛

dPN=RetriveSPL（QR，SPL）；//在隊(duì)列SPL中查找

｝

UpdateSPL（QR，dPN）；//更新隊(duì)列 SPL

if（dPN ！ =Null）｛

Send（QR，dPN）；//dPN節(jié)點(diǎn)發(fā)送信息

UpdateSPL（QR，dPN）；//更新隊(duì)列 SPL

ModiHR（）；//更新最近的命中率

return TRUE；

｝

if RetrieveLocal（QR）！=NULL｛//本地搜索

SendTo（resultSet，sourcePeer）//返回源節(jié)點(diǎn)

SendTo（resultSetAbstract，lastPeer）//

ModiHR（）；//更新最近的命中率

return TRUE；

｝

if（TTL ＞ 0）｛

SendTo（QR，除前一個(gè)節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)）；

return FALSE；

｝

｝

5 結(jié)語

和其他對等網(wǎng)絡(luò)中的搜索算法進(jìn)行比較，圖1是本文搜索算法和參考文獻(xiàn)［1］其他搜索算法效率的比較模擬結(jié)果。本文提出的搜索算法具有更高的搜索效率以及更小的延遲等優(yōu)點(diǎn)。模擬時(shí)對等節(jié)點(diǎn)是采用隨機(jī)安排在搜索樹中，并且按照自上而下的搜索的命中率逐漸進(jìn)行排序，樹中起始節(jié)點(diǎn)最初返回系統(tǒng)節(jié)點(diǎn)變化的結(jié)果。由于搜索方向比較明確，節(jié)點(diǎn)發(fā)送的大部分消息都可以很快地到達(dá)網(wǎng)絡(luò)熱點(diǎn)區(qū)域，因?yàn)樗惴ň哂斜容^小的延遲時(shí)間，使得查找目的節(jié)點(diǎn)的速度和命中率都有所提高。