基于K樹的搜索算法研究?

（成都理工大學工程技術學院 樂山 614000）

1 引言

非結構化對等網絡系統以其結構簡單、易于組織大規模網絡資源共享而得到廣泛應用。資源的搜索效率決定了系統的可用性和系統的關鍵性。平面對等結構由多層組成，分為上層節點管理部分、下層節點部分以及同層節點相互連接部分。如文獻［1］中使用超級節點，在一定程度上緩解了流量問題，但超級節點可能會導致該區域內的單點故障，并成為系統性能的瓶頸。隨機Walker搜索是非結構化對等網絡的另一種基本搜索方法，但由于其效率低，延遲時間過長因此該技術極少應用。洪泛法是非結構化對等網絡的初始基本搜索方法，由于開銷過大導致系統可擴展性差［1］。

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

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

2 K樹模型

非結構化對等系統拓撲結構是一個冪律分布和高度聚合的邏輯網絡。在維護系統結構完整性、可靠性以及容錯性方面，原有網絡具有良好的性能，因此仍然保留原有網絡的存在。在樹狀結構中，節點的鄰居只有父節點，子節點和極少數的冗余節點，節點度很小，系統結構維護成本很小，并且在搜索請求被傳播。而原有網絡基于搜索效率低，流量效率低下，因此原有網絡構建K樹進行資源搜索。進一步優化樹的搜索屬性，為樹中的每個節點分配權重，并給節點定期排列權重，獲得K加權搜索樹。

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

1）只有樹的底層和子層有節點少于K節點的葉節點；

2）每個節點最多有K個子節點；

3）對于任何節點，其權重小于或等于父節點的權重，并且大于或等于所有子節點的權重。

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

3 上升下降算法

歷史查詢命中率是搜索樹中節點的權重，節點的權重是命中率，從節點加入系統到當前查詢命中率的綜合評估值，反映了節點擁有網絡資源的熱量。從樹頂向下，節點命中率和穩定性逐漸減小，上層節點資源越多，而非熱量資源越低，因為越多，這就提供了更加準確的冷熱源分布，系統結構趨于穩定。任何節點的熱點區域的方向都可以很容易地確定，并且可以在很短的時間內達到非熱點資源的節點，利用遠程連接來增強它們之間的關系同樣可以提高不受歡迎資源的效率搜索。同時采取部分熱點資源復制，索引和上層節點緩存機制來進一步提高搜索效率，同時解決部分節點負載較重導致的樹狀結構發生。從較低層次加入新節點，頻繁接入系統，節點的總不穩定性處于樹的較低層次，所以系統搜索性能的穩定性可以得到保證。

設置節點到達系統時刻為0，每個時間段的長度為τ。在此期間的第 j次，達到Ci的次數表示為CN，其中命中次數為HN，Ri(j) 表示Ci在第 j次的命中率，α為命中率系數。

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

根據文獻［3］結論。對于任何節點Ci，Wi(j)的值在0和1之間。

由于請求是在樹結構中的節點的鄰居之間轉發的，因此相鄰節點接收到的請求數相近，因此相鄰節點的命中率具有可比性，命中率可以反映節點資源滿足請求的程度。

根據前述定義條件，當節點的命中率發生變化或者被做成系統初始化過程時，需要對樹中的節點位置做適當的調整，調用整個過程稱為剝離過程，對應于上升下降算法。從當前層到上層的節點稱為升級，反之亦然。

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

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

1）如果Cs發現定時器變為零，則計算最新的查詢命中率Ws，并通過發送消息新命中率給Ci，并更新命中率隊列，重置定時器。

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

3）當Cs收到請求更新消息時，如果同意升級，發送消息同意更新給Ci；否則發送拒絕更新消息。

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

4 K樹查詢算法

基本的搜索方法不會生成重復的消息，并且搜索延遲（跳躍）的上限是樹高度的兩倍。隨著系統運行時間的增加，系統搜索樹逐漸趨于有序且相對穩定，節點積累了一定的搜索體驗信息，可以優化搜索算法。

圖1 搜索效率比較

沒有可用的歷史搜索體驗數據，或者在系統操作的初始狀態或在系統的短期內不存在可用的歷史搜索體驗數據或其他需求，該請求被轉發給所有鄰居，當前節點的容錯備份不參與搜索。搜索停止條件是TTL=0或搜索成功或沒有節點轉發。基本的搜索方法不會產生重復的消息，并且搜索延遲（跳躍）的上限是樹高度的兩倍。隨著系統運行時間的增加，搜索樹逐漸趨于有序且相對穩定，節點積累了一定的搜索體驗信息，可以優化搜索算法。

本文使用基于搜索結果索引的緩存策略來提高搜索效率［13］。基于基本擴散和緩存索引，建立搜索算法，算法偽代碼如下：

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

dPN=RetriveRL（QR ，RL）；//在隊列RL中查找，dPN一個搜索成功的節點

if（dPN==Null）｛

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

｝

UpdateSPL（QR，dPN）；//更新隊列 SPL

if（dPN ！ =Null）｛

Send（QR，dPN）；//dPN節點發送信息

UpdateSPL（QR，dPN）；//更新隊列 SPL

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

return TRUE；

｝

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

SendTo（resultSet，sourcePeer）//返回源節點

SendTo（resultSetAbstract，lastPeer）//

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

return TRUE；

｝

if（TTL ＞ 0）｛

SendTo（QR，除前一個節點的所有鄰居節點）；

return FALSE；

｝

｝

5 結語

和其他對等網絡中的搜索算法進行比較，圖1是本文搜索算法和參考文獻［1］其他搜索算法效率的比較模擬結果。本文提出的搜索算法具有更高的搜索效率以及更小的延遲等優點。模擬時對等節點是采用隨機安排在搜索樹中，并且按照自上而下的搜索的命中率逐漸進行排序，樹中起始節點最初返回系統節點變化的結果。由于搜索方向比較明確，節點發送的大部分消息都可以很快地到達網絡熱點區域，因為算法具有比較小的延遲時間，使得查找目的節點的速度和命中率都有所提高。