摘 要： 针对在非结构化对等网络(Unstructured Peer to Peer)中查找资源时传统资源搜索方法的检索效率不高、通信开销过大的问题，提出了一种新的基于访问兴趣相似性P2P网络模型。在对网络结构不作全面改变的情况下，通过发现访问频谱相似节点，建立少量访问频谱相似节点间的远程连接，可以改善传统的非结构化对等网络资源搜索，并在此基础上设计了一种资源搜索算法。仿真试验证明，该模型在一定程度上提高了非结构化P2P资源搜索的效率，同时减少了网络中的通信冗余信息量。

关键词： P2P网络; 搜索; 访问频谱; 相似性

0 引言

　　以小世界理论构建的无结构P2P网络融合了规则网和随机网的特点，可以明显改善网络的查询性能[1-3]。其实它所反映的特性从生活中就能观察到，两个从未有过交往的家庭会因一对儿女的联姻而逐渐熟悉,最终所有家庭成员的交往都会变得更直接和密切。在P2P网络中也一样，只要增加少量节点间的远程连接，不用全面改变网络原有的结构就可以有效地缩短节点间相互访问路径的长度,进而改善整个网络的综合效能。但参考文献[4-5]的研究表明，远程连接节点的选择是有条件的，随意建立起的连接并不能达到预想的效果。仿真实验也证实了这点。

1 相关工作

　　参考文献[6]采用随机均匀分布策略建立节点的远程连接，并证明检索路径长度可以缩短并低于O(log2n)。参考文献[4]根据网络节点的流行度服从Zipf分布的特性提出了新方法，得到比参考文献[6]更好的检索结果。它们采用的方法是借助节点的本地信息去选择要建立远程连接的节点，使算法简单且开销比较小，但只利用了节点的静态信息。旧的节点信息对当前或未来的行为和兴趣的描述作用会随时间而衰减，进而对行为预测会产生较大的偏差[7-9]。另一方面，参考文献[6-8]的研究表明，网络节点产生的访问兴趣和行为通常存在一个稳定期，即使访问兴趣开始改变,发生突变的可能性也比较小。正是人们兴趣的持续性促成了网络上交易圈的形成并产生交织，从而引发网络的小世界现象。并且交际圈的范围和交织部分的大小对小世界效应的影响很大。因此，本文提出基于访问兴趣相似性P2P网络模型，通过节点行为特征（简称访问谱线）的比较，发现节点访问谱线的相似性，从而选出具有访问谱线稳定性高且兴趣覆盖宽的节点作为远程连接节点，进而达到缩短查找路径的效果。

2 访问谱线检索模型

　　2.1 基本思想

　　访问谱线相似的原因是节点访问了相同的目标节点集合。但现实网络中节点的访问谱线存在较大差异，因为节点包涵的信息不均衡，被重复访问的几率也不同。仿真实验对网络节点形成的访问谱线及其相似性进行了比对，结果表明，在规定时间段内节点对网络资源的访问形成了非常相似的访问谱线片段。另一个实验则表明，将有相似兴趣的节点连接起来，可以使它们以及与它们有相似兴趣的节点的平均查询路径长度大为缩短。如果节点兴趣面较广，则可以大范围影响节点的性能。

　　利用以上特性，模型的设计原则是建立远程连接时应选择交易活跃、兴趣广泛、访问谱线相似的节点。

　　2.2 模型建立

　　首先约定在理想网络状态下讨论模型，即任何节点都可以随意地访问到网络中的其他节点。设P2P网络节点集合为G={v1,v2,…,vn}。

　　定义1. 时段T（时长为L）内节点vi访问G中节点的次数称为vi的交易活跃度，即：

　　其中，分别为vi在时刻t和时刻t-L的访问次数，μ为交易活跃阈值。若A>M，则称vi为交易活跃节点，M为交易数阈值（一般为网络节点单位时段平均访问次数）。

　　定义2. 时段T内节点vi超过μ的访问节点的数量称为vi的交易覆盖度，即：

　　若C>F，则称vi为交易广泛节点，F为交易覆盖度阈值（一般为网络节点单位时段平均交易覆盖度）。

　　定义3. 时段T内节点vi与vj访问相同节点的差异量与访问节点总数之比称为vi与vj的访问谱线相似度，即：

　　其中，分别为 vi与vj在时刻t的请求访问次数，

　　若Sij>S，则称vi与vj为访问谱线相似节点，记为，S为访问谱线相似度阈值。

　　定义4. 若，则称为G的共有访问谱线相似节点集。

　　定理1. 节点的访问路径长度与节点在G中所占的比例成反比。

　　证明：假设为建立一个长度为的索引表，记录节点的IP地址，借助索引表a对其他节点的访问路径长度不会超过，如果所有节点索引表的内容不重复且都是访问谱线相似节点，那么节点的访问路径长度不会超过。所以节点的访问路径长度与节点在G中所占的比例成反比，即节点越多，节点的访问路径长度越短。

　　因此，建立模型的目的就是产生尽量多的访问谱线相似节点，并且形成共有访问谱线相似节点集。

2.3 检索算法

　　检索时消息M的传播方式是：一般节点以随机漫步方式转发给邻居节点，遇到有远程连接的节点，则利用远程连接和邻居节点一起转发，直到找到目标节点。算法如下：

　　输入：源节点vs发出检索请求M

　　输出：检索到目标节点vd或检索失败

　　(1) 接收M

　　(2) 查询本节点ν有没有所要找的资源，有则向vd返回结果，转步骤 (5)

　　(3) IF TTL=0 Then Goto (5)

　　(4) IF missing image file Then

　　由远程连接节点转发M和以随机漫步方式向邻节点转发M

　　Else

　　以随机漫步方式向邻节点转发M

　　(5) 继续侦听消息

3 仿真实验

　　仿真实验的目的是验证模型缩短检索路径长度的有效性。对网络节点形成的访问谱线进行相似性分析，选择符合模型要求的节点建立远程连接进行检索测试，分析节点检索路径长度的变化。测试网络设置1 000个网络节点，在10 min内每个节点以每秒随机产生1个对其他网络节点的访问，并统计它们的平均查询路径长度。随机抽取20个节点，分析所形成的访问谱线及其相似性，发现有3个节点的谱线满足相似性标准。结果如图1所示。不难发现节点的2、4、6、7、9频段的访问谱线相似度较高，表明它们在测试时段内对相同节点进行了满足谱线相似度的访问。接着，挑选符合标准的访问谱线相似节点建立远程连接，并构成不同覆盖度的共有访问谱线相似节点集，随后再进行同规模的测试（查询将借助远程连接实现），统计平均查询路径长度的变化。结果如图2所示。可以看出覆盖度的扩大对访问路径的缩短有较大影响。

4 结论

　　本文根据网络的小世界特性，提出用新方法对节点在资源查找过程中形成的访问频谱进行相似性对比分析，通过发现网络中具有访问频谱相似的节点，再从中筛选出交易活动能力强、交易范围广的节点，利用它们形成的超出一般节点的交易集合及其交集建立节点间的远程连接。仿真实验对模型的有效性给予了验证，实验结果表明，新方法使网络通信范围和访问路径长度大幅度缩短，改善了网络的资源检索效能，减少了网络带宽资源的消耗。

参考文献

　　[1] Newman M E J, Barabasi A L,Watts D J. The structure and dynamics of networks[M]．Princeton，New Jersey：Princeton University Press，2006．

　　[2] Hui K Y K，Lui J C S，Yau D K Y．Small-world overlay P2P networks：construction，management and handling of dynamic flash crowds[J]．Computer Networks，2006，50(15)：2727-2746．

　　[3] Zhang Yuxiang, Zhang Hongke. A load balancing method in superlayer of hierarchical DHT-based P2P network[J]. Chinese Journal of Computers, 2010, 33(9):1580-1590.

　　[4] Shen Jingbo, Li Jinlong，Wang Xufa. Efect of long-distance connections selection method on object lookup in P2P network[J]. Journal of Chinese Computer Systems, 2011, 32(1):99-102.

　　[5] Li Zhen, Duan Hancong, Nie Xiaowen, et al. Routing optimization on the layered peer-to-peer management network[J]. Journal of Chinese Computer Systems, 2012, 31(1):54-57.

　　[6] Kleinberg J．The small—world phenomenon：an algorithm perspective[C]. Proceedings of 32nd Annual ACM Symposium on Theory of Computing，2000:163-170.

　　[7] Huang Yongsheng, Meng Xiangwu, Zhang Yujie. Strategy of content location of P2P based on the social network[J]. Journal of Software, 2010,21(10):2622-2630.

　　[8] Zheng Xiaojian, Zheng Xiaolan, Li Tong, et al. High frequency access areas discovery algorithm in peer-to-peer network[J]. Computer Engineering and Design, 2014,35(3):780-784.

　　[9] Li Pu, Chen Shiping, Li Jianfeng. Cloud resources locating algorithm based on peer-to-peer network[J]. Application Research of Computers, 2013, 30(2):570-573.