一种改进的无结构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).