一種改進的無結構P2P網絡搜索策略

張 靜

（南京郵電大學 自動化學院 南京 210003）

0 引言

分布式非結構化P2P網絡應用十分廣泛，在Internet上，非結構化P2P系統是最常見的，比如Gnutella[7]，KaZaA[8]等。在這種系統中文件的位置和覆蓋網完全沒有關系。因為節點沒有相關文件的信息進行文件定位，所以需要查詢每個節點是否有與查詢條件匹配的文件。最常用的信息資源發現機制是在節點間或超級節點間，把信息資源查詢請求泛洪到網絡上。這種結構的優點是網絡具有很強的動態性，節點可以隨時離開和加入網絡，缺點是查找到理想的文件需要進行大范圍的搜索，帶來效率低下的問題，如通信消耗大、反應時間慢等。無結構化P2P網絡的搜索技術按照搜索策略可以分為兩大類：Flooding搜索和啟發式搜索。Flooding[9]搜索在網絡中傳播查詢數據包并且不斷擴散給每個節點，通過這種洪泛方式來搜索想要的資源，這種搜索方法引入了大量的通信開銷，它會隨著網絡規模的增加而現行增加，算法的可擴展性很差。而啟發式搜索在搜索過程中利用一些已有的信息來輔助查找過程。

本文針對常用的Flooding機制在搜索時造成嚴重的通信開銷的情況，借鑒人際傳播中謠言傳播機制，結合節點吸引因子的特性，提出一種改進的無結構P2P資源搜索策略。仿真結果表明，提出的搜索策略可以有效地減少無結構P2P網絡中資源搜索的通信開銷。

1 問題描述

1.1 基本概念

（1）謠言傳播機制 通過對謠言在人際網絡中傳播機制的研究可以得出以下事實[10]：人類個體傳播謠言的方式是從自己的鄰居每次隨機選擇一個個體進行傳播。同時，一個有趣的現象是：忽略個人的好惡因素，人類個體傳播某個謠言的興趣會隨著多次收到同樣的謠言而降低，即當多次聽說某一謠言時，個體會本能地認為該謠言已經廣泛傳播，從而停止自身的傳播，因此謠言傳播中興趣衰減機制適合于聚合網絡中信息傳播。

（2）吸引因子存在的無尺度網絡演化模型 在網絡中存在的每個節點對新加入的節點都有一定的吸引因素，節點內在具有的對新節點的吸引力定義為吸引因子，用

1）增長：從起初數量很小的節點開始，在每一個時間步里，一個具有吸引因子的新節點加入到網絡，并與m（ m≤m0，且為常數）個網絡中已經存在的點建立連接。

2）擇優連接：在選擇新節點的連接點時，新節點連接到節點i的概率取決于節點i的度數ki和吸引因子，即:

1.2 相關定義及評估標準

1.2.1 定義

設圖G表示無結構P2P網絡，v為圖G中任一節點，M為某次搜索所傳送的消息。

定義1.圖G中任意節點v的鄰居用集合Γv= {i: d( i, v )= 1}來表示，其中d( i, v)為節點i和 v間的最短路徑。

定義2圖G中任意節點v的度kv為與此節點相連的鄰居節點的個數。

定義3集合 Sv?Γv表示向節點v發送過消息M的所有節點。

定義4集合 Lv?Γv表示節點v向其發送過消息M 的所有節點。

1.2.2 評估標準

標準1（搜索通信開銷）平均每個節點在一次搜索中轉發的消息個數 f定義為系統的搜索通信開銷：

其中，R為搜索所覆蓋的節點個數（不包括消息發生節點），mi為節點i轉發的消息個數，N為系統的規模（系統的節點個數）。

標準2（冗余傳遞開銷）平均每個系統節點在一次信息搜索中收到的冗余消息個數D為冗余傳遞開銷：

其中N為系統的規模，mi為節點i轉發的消息個數，R為搜索所覆蓋的節點個數。

標準3（搜索策略覆蓋度）設在某一搜索策略下可達的節點數為R，則在該搜索策略下覆蓋度C定義為：

其中N為系統的規模。

2 搜索策略設計

2.1 搜索策略設計前提

DOU[12]等提出了一種基于概率的謠言傳播算法P-Rumor（Probability Rumor），模擬人類個體傳播某個謠言的興趣會隨著多次收到同樣的謠言而降低的特點，節點在收到某消息時，根據某一概率vP決定是否向其鄰居節點傳遞搜索消息，vP的定義如下：

定義6 在Rumor模型中，任意節點v在收到消息M時，根據概率 Pv是否向其 Γv? Sv? Lv中的鄰居節點傳遞消息M，vP定義為：

在P-Rumor算法中，vP隨常量系數h的變化而變化。當v第1次收到消息時，其發送概率 Pv≈ 1，當v收到的消息個數接近其鄰居節點數時， Pv≈ 0。

借鑒吸引因子存在的無尺度網絡模型擇優連接的模式，當節點v決定向其鄰居發送消息時，發送的概率取決于節點的吸引因子和度。此概率定義如下：

定義7如果節點v決定向其鄰居節點發送消息，那么對Γv? Sv? Lv中節點i，v依據概率Pvi決定是否向節點i傳遞消息。Pvi定義為：

由式（5），當v向鄰節點發送搜索消息時，傾向于向節點吸引因子和度數都大的節點發送搜索消息。

2.2 搜索策略的設計

綜合兩個搜索策略的前提，即式（4）和（5），我們得出節點v根據概率 PT決定是否向 Γv? Sv? Lv中節點i傳遞消息， PT定義為：

在搜索策略中，節點存在兩種狀態，即發送態T和靜默態S。搜索發起節點最初處于T態，其他節點最初處于S態，當任一節點（包括發起節點）收到搜索消息M 時，由S態轉入T態，發送完畢后，重新進入S。搜索策略如下：

（1）搜索發起者I將消息M 傳送給其所有鄰居節點集ΓI，同時轉入靜默態S。

（2）系統中任意節點v，收到消息M 時，其狀態由靜默態S轉為發送態T，根據式（6），將消息以概率PT傳遞給鄰居節點u， u ∈Γv? Sv? Lv，節點v同時進入靜默態S。

（3）處于靜默態S的節點若沒有收到消息，則保持靜默態S。

（4）當系統中沒有發送態T的節點時，搜索結束。

3 仿真和結果分析

本文采用MATLAB仿真工具來驗證改進的搜索策略的有效性。無結構P2P網絡的一個重要特性是節點度服從冪律分布。本文基于BA無標度網絡模型來產生不同節點規模的P2P網絡拓撲。圖1是由MATLAB產生的仿真網絡，有400個節點和1521條邊。

圖1 由MATLAB產生的仿真網絡

用MATLAB產生了不同尺度的仿真網絡，在這些網絡上測試了Flooding搜索策略和本文的搜索策略，并對結果做了比較。搜索通信開銷與系統尺度的關系如圖2所示，本文的搜索通信開銷比Flooding搜索策略的搜索通信開銷要小很多。圖3為冗余傳遞開銷與系統尺度的關系，本文的搜索策略冗余傳遞開銷要比Flooding方法的開銷小。圖4為覆蓋度和系統系統尺度的關系，本文的搜索策略覆蓋度相當高，與Flooding方法基本一致。

圖2 搜索通信開銷和系統尺度的關系

圖3 冗余傳遞開銷和系統尺度的關系

圖4 覆蓋度和系統尺度的關系

[1] Napster.http://www.napster.com

[2] 羅杰文.Peer to Peer 綜述[R].中科院計算技術研究所，2005.

[3] Stoica I, Morris R, Karger D, Kaashoek MF, Balakrishnan H. Chord: A scalable peer-to-peer lookup service for Internet applications[C]. In Proceedings of the ACM SIGCOMM 2001,San Diego. ACM Press, 2001.149-160.

[4] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker. A Scalable Content-Addressable Network[C]. In Proceedings of ACM SIGCOMM2001, San Diego.ACM Press, 2001.161-172.

[5] Rowstron A, Druschel P. Pastry: scalable, decentralized object location, and routing for large-scale Peerto-Peer systems[C]. In: Proc. of the 18th IFIP/ACM International Conference on Distributed Systems Platforms, ACM Press, 2001. 329-350.

[6] Zhao BY, Huang L, Jeremy S, Sean CR, Anthony DJ. Tapestry: A resilient global-scale overlay for service deployment[J]. IEEE Journal on Selected Areas inCommunications.2004,22(1):41-52.

[7] Gnutella [OL]. http://gnutella.wego.com , 2003.

[8] KaZaA [OL]. http://www.kazaa.com , 2003.

[9] 侯孟書, 盧顯良等.非結構化P2P系統的路由算法[J].電子科技大學學報, 2005, 34(1):3-6.

[10] Y H L IU , X L I. Location awareness in unstructured peer-to-peer systems [J]. IEEE Trans on Parallel and Distributed Systems , 2005 , 16 (2) : 163-173.

[11] 陶少華, 趙會洋, 平源,等. 基于吸引因子的無尺度網絡演化模型研究[J]. 復雜系統與復雜性科學, 2008, 5(2):88-92.

[12] Dou Wen , Wang Huaimin1. A rumor-spreading analog on unstructured P2P broadcast mechanism [J]. Journal of Computer Research and Development , 2004 , 41 (9) : 1460-1465 (in Chinese).