結構化P2P網絡上基于類別樹的索引機制

蘭明敬，胡建偉

（解放軍信息工程大學 信息工程學院，河南 鄭州450002）

0 引 言

DHT機制具有單值映射的特點，即為實體選取一個關鍵字，系統通過哈希算法將關鍵字一對一映射為空間標識，使用此標識與結點標識相匹配以決定存儲位置；發現過程中，若選取的關鍵字與存儲過程使用的關鍵字相等，則能夠快速定位到存儲點，取出實體信息；若不相等，則無法查找到實體。但很多情況下，人們無法準確描述所搜索的目標，無法給出實體存儲時所使用的關鍵字，只能給出搜索目標的大致特征描述。

一般的解決方法是使用多個關鍵字存儲實體，增大發現概率，同時建立集中式服務器存儲關鍵字信息用于模糊檢索。這種方法一定程度上損失了P2P技術的優勢，重新帶來單點失效和性能瓶頸風險，并可能涉及到版權問題。人們還利用語義思想來改善結構化P2P系統的搜索［1－3］，文獻 ［2］提出了一種向量空間模型，首先將描述實體的多個關鍵詞向量化，然后再使用哈希函數處理該向量，得到一個空間標識符；檢索文檔時，將檢索關鍵詞進行同樣的向量化操作，通過比較兩個向量的相似程度來判斷兩文檔是否匹配。相對于傳統的關鍵字相等，這種機制在一定程度上擴充了搜索關鍵字檢索的范圍，但距離模糊搜索還有一定差距，其缺陷主要體現在兩個方面：一是受限于標識符長度，一個特征向量中包含的特征詞數目是十分有限的，當搜索關鍵字與特征向量中的特征詞差別較大時即難以成功檢索；二是特征詞的選取和向量距離計算算法較為復雜，不合適的特征詞選取和距離計算算法將嚴重降低檢索效果。

本文在傳統的Kademlia算法基礎上進行改進，提出了一種基于類別樹的、靜態和動態描述相結合的索引機制。歸納應用系統涉及到的實體類別建立類別樹，依據類別樹形成結點、實體以及查詢所需的標識，使得結點組織、實體存儲、結點和實體發現均圍繞類別分布、實施。為每個類別編制描述該類別實體特征的靜態描述，實體發現過程中，先使用關鍵字列表檢索類別的靜態描述，綜合考慮關鍵字匹配情況、樹結點深度、結點祖先匹配程度、查詢者喜好等各類因素，得到若干最為滿足查詢需求的類別，將查詢聚焦到類別對應的若干P2P結點上。得到正確結果時，發現算法將查詢所用關鍵字添加到對應類別的動態描述中，以此在發現過程中進一步過濾不滿足查詢需求的目標結點，使查詢始終圍繞關鍵字列表進行，逐步收斂到滿足需求的P2P結點上。

為不引起混淆，將改進后的P2P結構簡稱為SKad。SKad由若干結點組成，結點是互聯網上的主機，結點間相互路由形成P2P覆蓋網絡。Skad可用于分享書籍、文獻、影音、程序等電子文件，實體是描述這些文件的信息單元，也是Skad存儲、管理的基本元素。

1 類別樹和類別靜態、動態描述

在搭建P2P系統之前，搭建者需要充分分析應用特征，歸納系統涉及到的實體類別，建立類別樹。

類別樹的結構及例子如圖1、圖2所示，樹結點 （C）枚舉了給定P2P系統中可能存儲的所有實體的類別，樹結點間的父子關系等價于對應類別的包含關系。

樹結點表示為：C＝ （cn，sd，ddi）。其中cn為類別名；sd為類別的靜態描述；ddp為動態描述標識，用于查找類別的動態描述。

靜態描述（sd）記錄了本類別所涵蓋實體的詳細特征，直接存儲在對應的樹結點中。實體存儲、發現過程中，算法首先依據描述實體的關鍵字列表，檢索類別樹中各類別的靜態描述，獲得若干與實體相匹配的類別，以此定位實體的存儲結點，縮減查詢范圍。P2P系統搭建者需要在建立類別樹的同時，為每個類別編制詳細的靜態描述。可通過互聯網搜索引擎或其他途徑，搜集某類別相關的各類文字描述，整理、合到該類別的靜態描述中。靜態描述的格式可以是字符串文本，也可以是數據庫或其他格式，前提是該格式能夠支持上述關鍵字檢索過程，且易于增量式擴充。

靜態描述存儲在類別樹中，而類別樹則和其他實體一樣存儲在P2P網絡中 （如圖3所示）。一般情況下，類別樹使用一個全局唯一且公開的標識符，以單一文件的方式存儲在P2P中。若類別樹較大，也可按類別劃分為若干子樹，分布存儲在P2P中。劃分的數目不宜過多，過多的子樹將帶來更多的流量開銷和管理負擔。

圖3 類別樹和類別描述存儲方法

在系統運行過程中，類別樹結構應較為固定。類別樹應具有明確且固定的分類方法，系統運行過程中，分類方法不能改變，類別樹中已經存在樹結點的名稱、動態描述標識以及樹結點間的連接關系不能改變。類別樹創建者（或其他人）可低頻度地、增量式地更新完善類別樹，包括增加樹結點，豐富類別靜態描述信息。盡管不是所有應用都滿足上述要求，但大部分的、常見的互聯網P2P應用都是滿足此要求的。比如音樂、軟件分享類應用，不難確定一種可用的、無需經常改變、易于維護的音樂、軟件分類方法。

動態描述同樣記錄了類別所包含實體的特征，差別在于動態描述是在系統運行過程中由發現算法動態地生成并不斷擴充的。類別樹按其動態描述標識 （ddp），分散存儲在P2P網絡中 （如圖3所示），其存儲格式也應支持關鍵字檢索以及增量式擴充。類別樹創建者在建立類別樹的同時應為每個類別設定相應的動態描述標識，此標識一般為從類別樹根到所在類別的路徑向量經過編碼得到的二進制串，動態描述標識直接存儲在類別樹的樹結點中。

實體存儲、發現過程中，算法得到下一跳結點列表時，使用描述實體的關鍵字列表檢索下一跳結點對應類別的動態描述，判斷該結點是否符合實體特征，進一步縮減路由目標，提高結點和實體發現效果。

2 結點和實體標識

結點和實體標識決定了P2P網絡拓撲結構和實體存儲位置，本文中，實體和結點的標識均來源于類別樹。

實體標識的產生方法為：從實體相關信息 （如音樂文件的名稱、作者、描述信息）中抽取若干有代表性的關鍵字，遍歷類別樹各結點，檢索結點的靜態描述和動態描述文本，獲得與實體相匹配的樹結點列表；從列表中選擇一個匹配度最高的結點，設為Cij，則實體標識eid為

eid ＝hash （cn1，cn2，…，cni，en）

其中cn1、cn2、…、cni為類別樹從根結點到Cij結點路徑上各樹結點的結點名；en為實體名稱；hash是哈希函數，將字符串轉變二進制碼。哈希函數與具體的P2P系統相關，本文中不做要求，但建議類別相近的實體，其標識距離也應相近，這樣會使得實體按照類別聚集，從而使P2P網絡具有更好的收斂特性，采用合適的搜索算法可以有效降低一次查詢所需的消息交換次數。

參考以下條件并采用加權的方式，從匹配的樹結點列表中選擇最匹配的樹結點：樹結點靜態、動態描述文本中，與關鍵詞匹配的詞匯數越多則樹結點匹配度越高；深度越大則樹結點匹配度越高；父結點越匹配則樹結點匹配度越高；越多祖先結點匹配則樹結點匹配度越高。選擇樹結點的過程就是依據類別樹對實體進行分類的過程，為使這種分類更為精確，可讓人參與到最優結點的選擇過程中，即由程序給出推薦的樹結點列表，由實體發布者從中選擇一個最合適的。

結點標識的產生過程與實體標識類似，不同之處在于由于結點沒有適于檢索類別樹的描述信息，因此在優先考慮路徑較深樹結點的前提下，采用隨機的方法為結點分配樹結點，設為Cij，結點標識nid為：nid ＝hash （cn1，cn2，…，cni，nn），nn為結點名稱。

將與實體／結點相匹配并用于生成實體／結點標識的類別，稱為該實體／結點的所屬類別。

3 發現算法

以結點發現為核心的發現算法，是新增、更新、檢索結點和實體等管理過程的基礎，下面以實體發現過程為例，闡述基于類別樹和靜態、動態描述的發現算法。

實體發現過程可劃分為生成檢索和查找實體兩個階段：

生成檢索階段：①拆分用戶的檢索請求，得到描述待發現實體的關鍵字列表keys＝ ｛key，key2，…｝；②使用上述關鍵字列表遍歷類別樹，檢索樹結點的靜態描述描述，得到若干匹配的樹結點，從中選取k個匹配度較高的樹結點。k為系統參數，k越大則查全率越高但消耗的帶寬和計算資源也越多；③依據上述k個樹結點生成實體標識列表ids＝ ｛id1，id2，…，idk｝；④使用實體標識列表和關鍵字生成k個查詢請求reqs＝ ｛req1，req2，…，reqi，… ｝，其中reqi＝ （idi，keys）。每個請求中均附帶完整的關鍵字列表，此列表用于在查詢過程中進一步過濾不滿足條件的路由目標 （見查找實體階段第3步）；⑤分別使用上述查詢請求查找實體。

查找實體階段：①訪問P2P的任一結點提交查詢請求，稱此結點為起始點；②依據路由算法，起始點返回若干備選下一跳結點；③考察查詢點和備選下一跳結點，從中選取p個更為匹配的結點形成下一跳結點列表。p為并行度，更大的并行度意味著更全面的查詢結果和更大的計算、帶寬消耗。選擇下一跳結點的方法有兩種：一是結點id與請求id距離更小；二是結點描述與請求中的關鍵字列表更為匹配。可綜合考慮上述兩種方法得到更優的下一跳結點列表；④分別向下一跳結點列表中的結點提交查詢請求，得到更多的備選下一跳結點；依據步驟3的方法，從中選擇p個更為匹配的結點形成新的下一跳結點列表；循環此步驟，直至下一跳結點列表不再變化；⑤訪問下一跳結點列表中的結點，從其實體表中獲取備選實體。依據步驟3中的選擇方法，選擇若干更為匹配的實體返回給查詢者。

上述過程中可以明顯地看出類別樹、靜態描述和動態描述的作用。類別樹將實體、結點與類別關聯起來，形成按類別的實體、結點分布。靜態描述用在檢索階段，依托靜態描述，以字符串匹配的方式且同時使用多個關鍵字，檢索類別樹，綜合考慮匹配數目、樹結點深度、祖先匹配度甚至和人工選擇結合在一起，優選出若干用于查詢的標識。而傳統算法只能夠對單一關鍵字進行哈希運算產生單一標識，多個關鍵字分別產生不同的標識符，相互之間完全獨立。

在傳統算法中，查詢所用的標識符與被查詢的目標結點是一一對應的，前者一旦確定，后者則相應地也被確定，查詢過程只是按路由算法找到標識符對應的這個目標點。而本文中，檢索階段將查詢聚焦到與關鍵字相匹配的若干類別上，查詢這些類別對應P2P結點的過程中，使用關鍵字列表檢索下一跳結點的動態描述，修正查詢路線，使得查詢過程始終圍繞關鍵字進行，不斷收斂到與關鍵字最為匹配的結點上。

查詢者在每次查詢過程中都要去訪問類別樹、靜態描述和相關類別的動態描述，可采用兩種方法降低此過程所需要的帶寬開銷。對于類別樹以及存儲在樹結點中的靜態描述，由于其唯一性且變動頻率較小，因此可將其內置到P2P軟件中，定期更新即可，無需每次查詢都去存儲點下載。對于動態描述，考慮到其動態且分散存儲的特點，可在P2P系統軟件中增加動態描述更新、檢索模塊，與系統軟件一起部署在所有的P2P結點上，需要檢索動態描述時，查詢者只需發送檢索請求至對應的存儲點即可。

4 實 驗

依據上述方法，我們對p2psim仿真環境進行改造，設計并實現了一個原型系統 （簡稱SKad）。在Skad存儲了若干書籍、文獻信息，就信息檢索效果做了與Kademlia的對比測試。表1羅列了測試環境及數據構成。

表1 測試環境及數據構成

依托上述環境共進行了五次試驗，分別編號為實驗1、實驗2、…、實驗5，各實驗得到的總正確結果如圖4所示。

圖4 總正確結果對比

實驗結果顯示SKad正確結果明顯高于Kademlia，這是符合預期的，因為Skad支持模糊檢索而Kademlia只能進行精確匹配。

下面就實驗3結果數據進行具體分析。圖5描述了本次實驗每次查詢Skad和Kademlia分別得到的正確結果數。可以看到，50次查詢中Kademlia共得到21個正確結果，正確率為0.42；每次查詢的正確結果數大多為0、1，很少達到2；結果為非零的查詢有20次。對于Kademlia來說，某個查詢關鍵字能否得到有效結果取決于此關鍵字是否是某實體發布時所使用的關鍵字。在本實驗中，實體發布時所使用的關鍵字是從5＊2000個關鍵字中隨機選取的2＊2000個關鍵字；而查詢關鍵字是從5＊2000個關鍵字中隨機選取的50個關鍵字；因此，對于每個查詢關鍵字來說，其等同于發布關鍵字的概率為0.4。基于此，查詢關鍵字能夠查得結果的概率為0.4，這與實驗結果相符。第9次查詢結果數為2，這意味著存在兩個使用同樣關鍵字進行存儲的實體。

圖5 實驗3正確查詢結果對比

觀察Skad的查詢結果，正確結果數為305，平均每次查詢得到6.1個正確結果，顯然，在類別樹和靜態、動態描述的輔助下，Skad查詢效果得到顯著提升。但同時Skad的正確結果數目波動較大，第21次查詢結果數為39，第33次查詢結果數為0。考察第21次查詢，此次查詢選取的查詢關鍵字為 “醫療”，對比類別樹可以發現，這種關鍵字具有較大的覆蓋范圍，描述醫療類別的書籍和文獻都滿足條件，因此得到了大量的查詢結果。而第33次查詢使用的關鍵字為 “洞室襯護”，此關鍵字出現在文獻 “巖石流變力學及其工程應用研究的若干進展”的摘要中，考察類別樹我們發現在此關鍵字既非類別結點，也未出現在靜態描述中，也沒有使用此關鍵字存儲或查詢過SKad（即未加入動態描述中），故此次查詢沒有得到正確結果。查詢結果的這種波動現象反映出Skad的特點，即SKad的查詢效果與類別樹結構是否合理、靜態描述是否完善、動態描述是否充分、查詢關鍵字選取是否合理等因素緊密相關，第1、2點是系統構建者需要考慮的問題，構建一個較完善合理的類別樹、編制詳細的類別描述可有效提高查詢效果；第3點取決于系統的運行時間和使用頻度，運行時機越長，經歷的查詢越多，則系統累積的動態描述越充分；第4點取決于P2P系統查詢者，按照人們的行為習慣，人們往往并不是隨機選擇關鍵字，而是選取那些與所查目標關系較為緊密，能夠直觀描述所查目標的詞匯作為查詢關鍵字，這有助于提升Skad發現效果。

5 結束語

本文提出一種基于類別樹的、靜態和動態相結合的索引機制。類別樹中歸納了系統所存儲實體的類別，用于形成結點、實體以及查詢所需的標識，使得結點組織、實體存儲、結點和實體發現均圍繞類別分布、實施。靜態描述用于依據關鍵字為結點、實體和查詢請求選擇類別，選擇過程是模糊的，采用字符串匹配的方式，綜合考慮各關鍵字匹配程度、樹結點深度、祖先結點匹配程度、查詢者喜好等各因素，能夠取得充分的、滿足查詢需求的若干實體類別。當查詢成功時，系統會搜集查詢所用關鍵字，累積到對應類別的動態描述中，用于豐富類別描述信息，在查詢過程中動態地過濾不滿足請求的類別結點，使查詢始終圍繞查詢關鍵字，不斷收斂到滿足需求的類別上。

本文同時給出了類別樹和靜態描述、動態描述的生成時機、管理方法。

本文提出的基于類別樹的、靜態和動態描述相結合的索引機制，適用于能夠對所存儲實體進行明確分類的應用領域，實現了結構化P2P中的模糊檢索功能。無需集中式索引服務器，無需大量的索引管理工作，有效避免單點失效和性能瓶頸問題。實驗證明，本方法相對于傳統的結構化P2P網絡，具有較好的查詢效果。算法已在某服務計算平臺中成功應用，此平臺已通過驗收并連續運行近一年。

今后，我們將研究、測試類別樹的結構對網絡拓撲和網絡負載的影響，同時尋求合適的分詞算法，應用到關鍵字與類別描述文本的匹配過程中，提高檢索效果。

［1］Zhu X S.Research on semantic peer－to－peer overlay route model［J］.Computer Engineering，2008，43 （13）：110－112.

［2］Wang Z X，Zhang D L，Liu L.Study on semantic－supporting search in P2P ［J］.Computer Engineering and Applications，2007，43 （3）：8－11.

［3］Zhang Y J，Gu J H，Wang X Z.A hierarchical P2Psemantic overlay network architecture based on topic and physical proximity ［J］.Journal of Electronics ＆Information Technology，2008，30 （8）.

［4］Wang C Z，Yang N，Chen H W.Improving lookup performance based on kademlia ［C］／／ Proc of the Second International Conference on Networks Security，Wireless Communications and Trusted Computing，2010：446－449.

［5］Chand R，Cosnard M，Liquori L.Powerful resource discovery for Arigatoni overlay network ［J］.Future Generation Computer Systems，2008，24 （1）：31－38.

［6］Stevens T，Wauters T，Develder C，et al.Analysis of an anycast based overlay system for scalable service discovery and execution ［J］.Computer Networks，2010，54 （1）：97－111.

［7］Liu Z Z，Wang H M，Zhou B.A two layered P2Pmodel for semantic service discovery ［J］.Journal of Software，2007，18（8）：1922－1932.

［8］Wu W M，Wu Y J，Zhao W Y.Chord－based semantic web service discovery ［J］.Acta Electronica Sinica，2007，35 （B12）：152－155.

［9］Zhang Y，Huang H，Yang D，et al.Bring QoS to P2P－based semantic service discovery for the universal network ［J］.Personal and Ubiquitous Computing，2009，13 （7）：471－477.

［10］Di Stefano A，Morana G，Zito D.A P2Pstrategy for QoS discovery and SLA negotiation in grid environment ［J］.Future Generation Computer Systems，2009，25 （8）：862－875.

［11］Zhou J，Dou W.A QoS－aware service selection approach on P2Pnetwork for dynamic cross－organizational workflow development ［C］／／Proc of the International Conference on Web Information Systems and Mining.Berlin：Springer－Verlag，2009：289－298.

［12］Xie C G，Guo D K，Chen H H.Research on service discovery protocol of global information grid based on peer－to－peer network ［J］.Computer Engineering，2007，33 （2）：97－98.