基于移動代理的結構化P2P網絡模型

王永偉，樊建席，劉文軍，沈海飛

（蘇州大學 計算機科學與技術學院，江蘇 蘇州215006）

0 引 言

P2P網絡改變了傳統的C／S模式，使得擁有資源的用戶可以與需求資源的用戶直接連接進行資源的共享，將網絡中的資源合理有效地組織利用起來。

P2P網絡分為結構化P2P網絡和非結構化P2P網絡。結構化P2P網絡區別于非結構化P2P網絡的最大特點在于：結構化P2P網絡都有一個嚴格的覆蓋網拓撲結構［1］。在最短的時間內找到所需要的資源是P2P網絡所需解決的首要問題。結構化P2P網絡主要就是實現了資源的快速查找，典型的結構化 P2P網絡協議有 Chord［2］，CAN［3］等。但是這些典型的拓撲模型沒有考慮網絡中的節點在處理能力和在線時長等方面的差異。若充分利用這種差異即異質性則可以對網絡的性能做出極大的改善。此外，在如今的網絡中，用戶常希望在輸入一些所需資源的某些特點以后能篩選出某一類資源，這就要求網絡應具有語義查詢的能力。

文獻 ［4］考慮了節點的異質性，但是沒有語義查詢功能。文獻 ［5］提出了基于雙層P2P結構的語義服務發現模型。文獻 ［6］改進了雙層P2P網絡模型并作了相關分析。將自組織和結構化P2P網絡相結合可得到自組織網絡，如文獻 ［7，8］將生物激勵算法用到結構化P2P網絡Chord中，得到Self－Chord模型。文獻 ［9］利用移動Agent預見性的處理負載問題達到負載均衡。文獻 ［10］通過利用自組織的方式均衡負載。文獻 ［11］給出了兩層非結構化的語義發現模型。

本文結合網絡中節點的異質性提出的一種基于移動代理的結構化 P2P網絡模型 （mobile agent based structured P2Pnetwork：AS－P2P），在移動代理的作用下，AS－P2P不僅具有資源索引分類、模糊查詢、負載均衡等優點，而且平均查找長度更短，更加能夠適應網絡的動態變化。

1 AS－P2P網絡模型

1.1 相關定義

定義1 一般節點NP（normal peer），可以是網絡中的任意節點。它可以隨時加入和離開網絡而只需要較少的網絡修復操作。一般節點上存有資源供其它節點請求，也可以向其它節點請求資源。一般節點上存有自身資源的資源索引，這些資源索引項為 （key，Location（ID）），其中：key是數值型資源關鍵字，假設相似資源的key相近。是為此資源索引負責的超級節點的標識。

定義2 超級節點SP （super peer），是指在網絡中在線時間長、處理能力強、可靠性高的節點。它主要負責若干個NP的資源請求和相應種類的資源索引。它負責維護的索引數據庫為

其中：Location（key，NP）是資源關鍵字為key的資源所在的路徑，如可由NP的IP地址和資源在NP上的路徑組成。此外，每個SP還需要維護一個中心關鍵字CK（central key）以表征此超級節點所負責的索引項的資源種類，CK可以由下式得到其中：表示索引數據庫中所有資源索引的關鍵字之和，表示資源索引項項數。超級節點還需要維護一個索引網絡的路由表。

定義3 移動代理 MA （mobile agent），是運行在超級節點上的程序。它負責超級節點的索引數據庫中資源索引項的轉移。當超級節點的索引數據庫有資源索引項更新時，便運行此程序。它把超級節點的索引數據庫中離CK較遠的鍵索引帶離該超級節點并放置到合適的超級節點上。MA是實現資源索引分類的關鍵。

AS－P2P網絡模型的上層為索引網絡，是由在線時間長、處理能力強和可靠性高的超級節點組成的結構化P2P網絡。網絡中的超級節點在更新資源索引時運行移動代理程序，此程序負責索引網絡中的資源索引的移動。一般節點組成下層網絡，稱為資源網絡。資源網絡的節點可以與任意的超級節點建立主仆關系，從而適應高度動態的網絡環境。

1.2 一般節點上線和資源發布

一般節點可以是網絡中的任意節點，它可以隨意的加入網絡并依附于超級節點。

1.3 節點下線和資源撤銷

1.3.1 一般節點下線

一般節點NP下線時根據每項資源對應的資源索引項的找出對應的負責超級節點SP，然后向SP發送下線消息DOWN＿MSG，SP收到消息后把相應的資源索引項刪除，并返回一個DOWN＿OK消息給NP，當NP收到所有資源的DOWN＿OK消息后正常下線，對應的資源也正常撤銷。另外，SP周期性檢測每個資源是否有效，以排除一般節點意外下線造成的資源無效的情況。

1.3.2 超級節點下線

當超級節點SP需要下線時，SP會把索引數據庫中存儲在SP上的資源索引刪除，并按照上述一般節點下線時的操作刪除SP在其他超級節點上的資源索引，然后在SP負責的一般節點NP中找到一個備選超級節點SPB，最后SP把索引數據庫和路由表復制給SPB。SPB繼承SP的ID號，并通知SP所負責的資源索引對應的資源所在的節點，現在由其負責該索引，SPB按照索引網絡層所用的結構化P2P網絡協議加入索引網絡。至此，超級節點正常下線，對應的資源也正常撤銷。

1.4 一般節點加入與離開索引網絡

索引網絡按照所有超級節點的CK從小到大排列，所以擁有相似CK的超級節點是相鄰的。

1.4.1 一般節點加入索引網絡

當一個超級節點SP的資源索引項過多，即超過設定的最高負載INDEX＿HIGH 時，SP在其負責的一般節點中選出一個備選超級節點設為SPB，作為SP的后繼加入上層索引網絡。SP將索引數據庫中排序靠后的一半資源索引項復制給SPB。SP通知相應超級節點現由SPB負責相應的資源。這些操作結束以后，SP刪除這些資源索引。SP和新加入的SPB都重新計算自己的CK。一個一般節點就成功加入索引網絡成為超級節點。

1.4.2 超級節點離開索引網絡

當某超級節點SP1的資源索引項過少，即低于設定的最低負載INDEX＿LOW 時，SP1向其鄰居節點SP2發送一個INFO＿MSG消息詢問SP2的索引數據庫中的索引項的個數。SP1得到SP2的索引項個數以后，SP1比較自身的索引項數與SP2索引項數之和是否大于INDEX＿HIGH 。若SP1的索引項數大于SP2的索引項數，則由SP2將索引數據庫中的前 （Index ＿SP2－Index ＿SP1）／2索引項轉移給SP1，（其中，Index＿SP1和Index＿SP2是SP1和SP2的索引數據庫中的索引項數）；否則，SP1把自己的索引項和負責的一般節點交由SP2負責。一個負載過低的超級節點成功離開索引網絡成為一般節點。

1.5 超級節點上移動代理的工作過程

步驟1 當有新節點加入并由超級節點SPM 負責時，SPM的MA激活比較函數用以找出其索引數據庫中與CK較遠的對應的索引項，這可根據與的相似度函數確定

其中，key＿max是資源關鍵字的最大差。給定一個Ptake，當時，SPM 就找出關鍵字為key的資源索引項。

步驟2 MA復制步驟1找出的資源索引項，在路由表項中找到一個超級節點SP1，使得SP1的CK與索引項對應的資源關鍵字最近。MA與SP1建立連接，設SP1的CK為，計算。在SP1的路由表中找出超級節點SP2使其CK與key最相近，設SP2的CK 為CK2，計算。若f（key，CK1）＞f（key，CK2），則把key放置在SP1上；否則，與SP2建立連接。重復步驟2的前述過程，直到找到一個超級節點SPD，最終將key放置到SPD上。SPD根據索引項中包含的源ID號給SPM發送一個確認消息，SPM 再告訴該資源的擁有者NP，NP相應改動自己的資源索引，知道自己的資源是由SPD所負責的。然后SPM 刪除此項資源索引。

步驟3 MA重復步驟2將所有資源索引安排給合適的超級節點，一次移動代理的工作過程結束。

2 AS－P2P網絡模型的實驗仿真和性能分析

2.1 平均查找長度

設網絡中節點進行資源請求的概率相同，索引網絡使用結構化P2P模型。設網絡中總節點數為N，超級節點個數占總節點個數的比例為α，超級節點的個數為α＊N，一般節點的個數為（1－α）＊N。

定理 AS－P2P網絡中的平均查找長度較傳統結構化P2P網絡模型更短。

證明 以索引網絡層使用Chord為例，當超級節點查找資源時，直接在索引網絡層進行查找，平均查找長度為log（α＊N）；當一般節點查找資源時，會向為其負責的超級節點發出請求，長度為1，之后由超級節點查找資源，平均查找長度為log（α＊N）；由于超級節點、一般節點占總節點個數的比例分別為α、1－α，因此在Chord中平均查找長度

在實際網絡中，超級節點的比例α較小，所以平均查找長度log（α＊N）＋1－α相對于chord來說更小。相類似的，當索引網絡層使用其它結構化P2P網絡模型如CAN時，由于規模變小，平均查找長度也較傳統結構化P2P網絡模型也更短。

2.2 資源分類和語義查詢

網絡在多個移動代理的協同工作下，每個超級節點維護的索引數據庫中，偏離該超級節點CK較遠的資源索引項都會被轉移到合適的超級節點的索引數據庫中，即資源索引會按照資源種類被安放在相應超級節點的索引數據庫中。

在穩定的網絡中，各超級節點的索引數據庫中，索引項關鍵字key都距離CK較近，它們屬于相似資源。因此，一個超級節點是存儲以CK為中心的一類資源，這達到資源索引分類效果。如果對于網絡中的某個關鍵字key的資源請求沒有找到，那么超級節點也可以返回索引數據庫中與key相近的資源，因而可以實現語義查詢。為評估超級節點的索引數據庫中資源索引項的相似程度，現作如下定義。

定義4 超級節點上資源索引純度ρ定義為

其中，CKi是超級節點i的關鍵字，N是超級節點i的索引數據庫中資源索引項數，key＿max是資源關鍵字的最大差。

模擬實驗參數如表1所示，其中資源關鍵字最大差為512，網絡中超級節點的動蕩時的資源純度和執行移動代理后的資源純度如圖1所示。

表1 模擬實驗參數

圖1 超級節點的資源索引純度

從模擬實驗結果數據來看，資源鍵值均勻分布時，網絡經過動蕩后，部分超級節點的資源純度下降；在移動代理程序運行作調整后，所有超級節點上的資源純度又重新恢復到很高的狀態，這表明網絡具有資源索引分類的功能。

2.3 負載均衡

從一般節點加入索引網絡和超級節點離開索引網絡的過程來看，超級節點的資源索引項數會分布在INDEX＿LOW和INDEX＿HIGH 之間，從而實現超級節點上資源索引項的負載均衡。這對于網絡性能和可靠性十分重要。例如，當一個超級節點存儲的資源索引屬于熱門資源，那么對它的查詢會很頻繁，如果它存儲的資源索引項過多，那么熱點問題就很突出，而這里的負載均衡很好的解決了這個問題。若超級節點所負責的一般節點過多可通過向鄰居超級節點轉移部分一般節點的方式進行一般節點負載的均衡，且此操作不會影響上層的索引網絡。

模擬實驗參數如表1所示，網絡動蕩期及穩定后超級節點上擁有的資源索引項數如圖2所示。

圖2 超級節點上資源索引項的個數

從實驗結果數據來看，資源鍵值均勻分布時，網絡在有節點和資源的加入和離開后，部分超級節點索引數據庫中的資源索引項數發生了較大變化；經過調整，超級節點上的資源索引項數都處于3000和7000之間，即分布在INDEX＿LOW 和INDEX＿HIGH 之間。這說明網絡中超級節點上的資源負載是相對均衡的。

3 結束語

理論分析和模擬實驗表明，充分利用節點的異質性，并選擇使用雙層網絡結構后，AS－P2P具有對資源索引分類，負載均衡，能很好地適應網絡的動態變化等優點。需要指出的是，AS－P2P沒有考慮網絡帶寬因素。實際上，為了達到資源索引的分類，移動代理在網絡中移動時會消耗索引網絡帶寬。后續的工作可以對移動代理的工作進行優化，以期以更小代價換取資源分類和負載均衡，這對于支持語義查詢和后續的P2P網絡擴展具有重要的作用。

［1］CHEN Guihai，LI Zhenhua.Peer－to－peer structure，application and design ［M］.Beijing：Tsinghua University Press，2007 （in Chinese）.［陳貴海，李振華.對等網絡：結構、應用與設計［M］.北京：清華大學出版社，2007.］

［2］Stoica I，Morris R，Karger D.Chord：A scalable peer－to－peer lookup service for Internet applications ［C］／／ACM SIGCOMM，2001：149－160.

［3］Sylvia R，Paul F，Mark H，et al.A scalable contentaddressable network ［C］／／San DiegoCA， ACM SIGCOMM，2001：161－172.

［4］XIA Qizhi，XIE Gaogang，MIN Yinghua，et al.IS－P2P：Index－based structured P2Pnetworks ［J］.Chinese Journal of Computers，2006，29 （4）：604－607 （in Chinese）. ［夏啟志，謝高崗，閔應驊，等.IS－P2P：一種基于索引的結構化P2P網絡模型 ［J］.計算機學報，2006，29 （4）：604－607.］

［5］LIU Zhizhong，WANG Huaimin，ZHOU Bin.A two layered P2Pmodel for semantic service discovery ［J］.Journal of Software，2007，18 （8）：1925－1926 （in Chinese）.［劉志忠，王懷民，周斌.一種雙層P2P結構的語義服務發現模型 ［J］.軟件學報，2007，18 （8）：1925－1926.］

［6］MING Deting，LI Juan，QIU Xiaohong，et al.Simulation on improved two－tier hybrid P2Pnetwork model ［J］.Computer Engineering and Design，2009，30 （24）：5609－5611 （in Chinese）.［明德廷，李娟，邱曉紅，等.改進的雙層混合式P2P網絡模型的仿真與分析 ［J］.計算機工程與設計，2009，30（24）：5609－5611.］

［7］Agostino F，Carlo M，Michela M.Self－chord：A bio－inspired algorithm for structured P2Psystems ［C］／／USA：IEEE／ACM Symposium on Cluster Computing and the Grid，2009：45－47.

［8］Agostino F，Emilio L，Carlo M，et al.Self－chord：A bio－inspired P2Pframework for self－organizing distrubuted systems［J］.IEEE／ACM Transactions on Networking，2010，18 （5）：1653－1658.

［9］LI Hui.An active load balancing algorithm for P2Psystems based on mobile agent ［J］.Microelectronics and Computer，2012，29 （11）：92－93 （in Chinese）.［李慧.一種基于移動代理的P2P系統主動負載均衡算法 ［J］.微電子學與計算機，2012，29 （11）：92－93.］

［10］Giuseppe V，Paul L S，Daniel J D，et al.A self－organized loadbalancing algorithm for overlay－based decentralized service networks［C］／／IEEE International Conference on Self－Adaptive and Self－Organizing Systems，2011：170－172.

［11］LIU Zhizhong，LIU YuLan，HE Yihui.A two－layered P2P model for semantic service discovery ［C］／／ New Trends in Information Science and Service Science，2010：42－45.