一种基于节点兴趣的移动P2P 网络动态分组算法

◆石曦彤

（四川大学网络空间安全学院 四川 610065）

1 引言

随着无线通信技术的迅速发展，移动P2P 作为一种新型覆盖网络技术也在不断发展中。移动P2P 网络中节点的地位是对等的，每个节点既是资源下载者，也是资源提供者，这种资源共享模式解决了传统C/S 模式下服务器性能瓶颈的问题，更能充分利用网络中节点的计算资源。现有的移动P2P 网络的拓扑结构分为集中式、完全分布式（结构化和非结构化）、混合式三种类型[1]。

集中式P2P 网络以目录服务器为中心形成星形结构，维护简单且搜索效率高，但同时也容易造成单点故障、访问的“热点”现象等问题，同时网络缺乏可扩展性。

完全分布式结构化P2P 网络，又称为DHT 网络，在完全分布式结构化网络中引入了分布式散列表（Distributed Hash Table，DHT）技术，经典的DHT 算法有Chord[2]、Pastry[3]和Kademlia[4]等。DHT 网络的优点是采用了确定性拓扑结构，能够精确地定位资源。缺点是DHT 的维护机制比较复杂，尤其是当节点频繁加入、退出网络时造成的网络波动会极大增加系统的维护代价。完全分布式非结构化网络采用完全随机的组织结构，优点是所有节点是完全对等的，所以网络的可扩展性和容错性较强。缺点是由于采用泛洪式的消息传播方式增加了网络的负载。

混合式P2P 网络结合了集中式和完全分布式两种方式，把移动节点分成多个域，每个域内有一个超级节点，功能是存储普通节点信息、内容管理和与有线P2P 网络的通信，普通节点发出文件查询请求之后，该请求在超级节点间进行转发，之后该节点获得一个反馈结果列表，然后选择与之进行交易的节点。

本文提出一种基于节点兴趣的移动P2P 网络动态分组算法，其基本思想是：考虑到相同兴趣的节点间交易概率比较大，另外，移动P2P 网络是一种覆盖网络，其在设计之初并未考虑到与物理网络的结合，导致逻辑拓扑结构与物理拓扑结构不匹配，相邻节点间的信息延迟较大，故根据节点间的兴趣相似度、资源相似度以及物理距离对节点进行动态分组，从而提高整个网络的资源共享效率。

2 相关工作

2.1 节点聚类方式

聚类是指将物理或抽象的对象集合分成由类似的对象组成的多个类的过程。由聚类所生成的簇是一组对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。为了提高移动P2P 网络的资源共享效率及安全性，研究者提出了许多移动P2P 网络的分组算法。曹晓梅等人[5]提出一种改进的分组P2P 信任模型，该模型利用模糊推理规则结合信任值和贡献值，将网络中节点划分为若干不同等级的小组，通过小组等级限制节点的资源访问权限，实验表明该模型能有效抑制恶意节点的攻击。为了提高移动P2P 网络的覆盖层拓扑稳定性，宋人杰等人[6]提出了一种基于节点移动特性的移动P2P 网络分簇算法，实验表明该算法使簇内节点能够最大程度地保持覆盖层拓扑结构的稳定性。

2.2 超级节点选取方式

文献[7]通过分析影响超级节点选取的各种因素，将这些因素分为效益型属性和成本型属性，建立超级节点选取的带约束多目标优化模型，利用免疫克隆算法对超级节点选取问题进行求解。文献[8]选取服务能力强和节点活跃度高的节点作为超级节点，主要考虑的影响因素有CPU 速度、带宽大小和内存容量以及节点单位时间的贡献度。文献[9]提出了一种基于信任模式的P2P 超级节点选取机制，主要思想是通过计算节点的总体信任度作为评选超级节点的一项重要指标，在选取超级节点时采用阈值过滤算法从普通节点中筛选备选超级节点集合，然后再从备选超级节点集合中选取最优的节点作为超级节点。王秀娟等人[10]提出一种基于区域划分的超级节点选取机制，将P2P 网络中的节点按照物理位置划分成若干区域，保证区域内节点在物理位置上是相近的。

3 基于节点兴趣的动态分组算法

本文提出一种移动P2P 网络中基于节点兴趣的动态分组算法，首先根据资源类型的个数，将移动P2P 覆盖网络划分为若干个组，动态分组的依据是网络中节点的兴趣相似度，资源相似度、节点的移动特性以及节点的物理位置因素，然后根据交易信息动态的更新分组。

3.1 节点角色

（1）超级节点

超级节点具有更高的计算能力和稳定性，其维护一个组中所有节点的文件列表和不同组节点之间交易的事务信息，文件列表记录了组内所有节点的文件，当一个节点请求一些文件时，它可以将请求发送给超级节点，超级节点告诉请求者哪个组成员拥有请求的文件。

（2）普通节点

不是超级节点的节点，它可以向其他节点请求资源，也可以为其他节点提供资源。普通节点在每次事务后将事务信息发送给对应的超级节点。

3.2 节点管理

（1）节点加入

当一个新节点加入网络时，根据兴趣相似节点间交易概率比较大的思想，首先计算该新节点与所有超级节点的兴趣相似度，使节点能够加入到与其兴趣相似度较高的组中；然后考虑到一个组内的节点之间拥有的资源重叠较少时能更好地为其他节点提供分享资源，故通过计算节点间的资源相似度，使分组后组内节点资源尽可能更丰富；最后计算该新节点与所有超级节点的物理距离，使其能被添加到距离相对近的组中。

（2）普通节点离开

当一个普通节点离开网络时，节点向同一组中的其他节点广播离开的消息。同一组中的其他节点更新邻居的信息并重新计算信任值。同时，组中的超级节点更新路由表和文件列表。

图1 动态分组示意图

（3）超级节点离开

当一个超级节点离开网络时，首先要求超级节点广播其离开消息，然后根据超级节点选择机制重新选择新的超级节点。一旦确定了新的超级节点，组的所有文件列表和节点间交易的事务信息都将传输到新的超级节点。新的超级节点响应它从原超级节点接收到的信息。然后，原超级节点退出网络。

3.3 动态分组流程

在移动 P2P 网络中，资源节点i的兴趣集Ipi表示为：Ipi = {a1,a2,…al}，l 为文件类型个数，对于第k个兴趣ak ∈{0,1}，表示节点i是否拥有至少一个该类型的文件，若拥有则ak =1，否则ak =0。资源节点j的兴趣集Ipj表示为：Ipj ={b1,b2,…bl}，l 为文件类型个数，对于第k个兴趣bk ∈{0,1}，表示节点j是否拥有至少一个该类型的文件，若拥有则bk = 1，否则bk =0。节点i和节点j之间的兴趣相似度ISimi,j计算如下：

式中，si,j表示Ipi和Ipj中对应位置的值相同的个数，l 表示文件类型总数。

资源节点i所拥有的文件集Fpi表示为：Fpi ={f1,f2,…fn}，n为节点i所拥有的文件资源个数。资源节点j所拥有的文件集Fpj表示为：Fpj ={f1,f2,…fm}，m为节点j所拥有的文件资源个数。节点i和节点j之间的资源相似度FSimi,j计算如下：

在初始阶段，因为l 是节点兴趣集中的类型数，故选择l 个节点作为初始中心节点。然后，得到l 个中心节点和l 个对应的初始群。为改善移动P2P 网络中逻辑拓扑结构与物理拓扑结构不匹配而带来的P2P 节点间的延迟增大的问题，故在分组时还需考虑节点之间的物理位置，使各组内节点尽量靠近，在新节点加入时，通过向各中心节点发送探测消息，获得往返时延值RTT。

给定一个节点，我们可以通过公式（3）分别计算它与l 个中心节点的综合分组考量值。

式中，δ1、δ2和δ3分别为节点兴趣相似度、资源相似度和物理距离的权重，且δ1+δ2+δ3 =1，如果给定节点和中心节点之间的分组考量值最终得分最大，则将给定节点添加到中心节点的组中。通过重复此过程，将所有节点添加到相应的组中。之后，我们使用K-means[11]中采用的方法更新每组的中心点。然后，通过计算节点与更新中心节点的相似度，得到l 个新的节点群。如果每个组中的节点停止更改，则终止此进程。

在网络交易阶段，如果节点成功收到请求的文件，则更新该节点拥有的文件集。若系统中的事务成功交易率小于阈值θ，或者网络中节点加入/离开的比例大于阈值∂，则重新进行动态分组。

3.4 超级节点选取机制

在资源搜索时，为了减少响应时间，提高搜索效率，查询信息请求应该发送给性能和稳定性相对较高的节点，即超级节点。本文在选择超级节点时把节点的能力因素作为主要参考指标，主要考虑的性能指标参数有：在线时间（OT）、CPU 的有效处理能力（Speed）、带宽（BW）、存储空间（Memory）。用Ability变量来表示节点的能力值，节点的Ability值越大，则表示该节点处理能力越强。节点i的Ability值计算公式如下：

其中，OTmin表示超级节点的最短在线时间，单位是秒；Speedmin表示超级节点的最小有效处理能力，单位是MIPS；BWmin表示超级节点的最小带宽，单位是kpbs；Memorymin表示最小存储空间，单位是GB。

另外在选取超级节点时还考虑了节点对系统的贡献度，即主动提供的资源数、成功转发其他节点的请求消息数。为每个节点定义一个贡献度变量Contribution，计算公式如下：

其中Fupload表示表示在时间T内节点成功上传的文件数，Fforward表示节点成功转发的消息数，即间接为系统做出的贡献，T表示系统运行的时间周期。

节点i的Utility值计算公式如下：

其中，γ1和γ2分别为节点能力值和贡献值的权重，且γ1+γ2 =1。系统中的每个节点都有其对应的Utility值，周期性地对它们的Utility值进行评估，拥有最大Utility值的节点将成为本分组中的超级节点。

4 实验与分析

本文仿真基于 PeerSim1.0.5 仿真系统，PeerSim 支持2 种仿真模式，即 Cycle-based 模式和传统的 Event-based 模式，Cycle-based 拥有更好的伸缩性及性能，本文采用Cycle-based 模式进行仿真，对传统的半分布式移动P2P 网络和基于节点兴趣的动态分组算法的移动P2P 网络进行信息检索延迟的比较。

具体仿真环境为：节点总数为250 个，文件个数为1000 个，文件种类为8 个，文件在各节点均匀随机分布。其他仿真参数如表1 所示：

表1 仿真参数

数轴中横坐标代表请求次数，纵坐标代表网络延时（从源节点到目的节点的所有路径延时之和）。实验结果如图2、3 所示。

图2 请求次数从0 到500 时的信息检索时延

图3 请求次数从0 到1000 时的信息检索时延

由以上仿真结果可以看出，基于节点兴趣的动态分组算法的转发延时比传统半分布式的延时低30%～40%左右，所以基于节点兴趣的动态分组算法能够一定程度地降低网络的信息检索延迟，提高资源检索的效率，并且具有较好的可扩展性。

5 结束语

为了提高移动P2P 网络的资源共享效率，本文根据兴趣相似节点间交易概率比较大的思想，提出一种基于节点兴趣的动态分组算法，并在分组时考虑到节点拥有的资源类型及节点间的物理位置，从仿真实验可以得出此算法能够降低节点间通信延时，提高移动P2P 网络中的文件共享效率，并具有一定的扩展性。