MP2P网络基于动态分组的超级节点选取

陶 洋，王成宇，潘蕾娜，杨 柳，王 进

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 引 言

在移动对等(mobile peer-to-peer，MP2P)网络中，节点间可以进行自由交易，并且节点经常连接并离开网络，这将动态地改变网络拓扑。因此，在选取超级节点时，必须要考虑到超级节点的可靠性和稳定性。近年来，MP2P网络中的超级节点选取策略也是受到了研究人员的广泛关注。

贾美娟等[1]提出一种根据节点兴趣相似度进行动态分组的超级节点选取机制，引入了中继节点用于组与组间的信息交换，根据节点的资源类型进行分组。郭良敏等[2]提出了一种将物理位置相近的节点分在一个簇中，使同组中的节点在物理位置上相近，降低普通节点与超级节点间的信息检索延迟。朱广辉等[2]提出了一种根据信息相关度进行节点分组的超级节点选取机制。Saghiri A M等[3]提出了一种考虑节点的容量的对等关系进行超级对等点选择的算法，通过节点的数量和节点的容量率方面提升网络的动态性。文献[4-6]主要从网络拓扑方面出发，将节点进行分层，分区处理，从而进行超级节点的选取，但是主要研究点集中在单个超级节点的选取，以及若干个备选节点的选取工作。文献[7,8]主要从节点的物理位置、IP地址作为分组分簇依据，将网络拓扑中相近较近的节点分为一组，从而减少组间节点交易的传输距离，降低信息传输时延。

研究发现，大多数文献主要考虑了单一因素对网络中的节点进行分组，并且在选取组内超级节点时都只考虑了单一或者固定节点数的超级节点[9,10]，但是没有考虑到根据群组的规模大小进行动态的超级节点群组的选取。因此，本文提出一种基于动态分组的超级节点选取机制(dynamic grouping-based super node selection mechanism，DGSM)。该机制考虑节点的兴趣向量相似性和物理拓扑中节点间的距离两个因素进行节点的动态分组，然后根据阈值过滤算法和节点综合能力计算选出每组的超级节点群组和备选超级节点集合，根据每组的超级节点负载情况动态更新该组的超级节点群组。实验结果表明，通过该机制选出的超级节点在一定程度下，提供了较低的信息检索延迟，更少的网络资源定位消耗和更大的网络资源定位成功率。

1 相关工作

1.1 节点定义

在每一组中，我们为节点定义3个角色：超级节点、普通节点和中转节点。

超级节点(super node，SN)：维护了一个信任表和一个组中所有节点的文件列表的节点。信任表记录组中所有节点的信任信息。当节点请求一些文件时，它将请求发送给超级节点。超级节点根据该节点的请求，首先在本组中查找是否有符合的资源。如果该资源存在，且拥有资源的节点的信任度较高，则超级节点告诉请求节点哪个组成员节点拥有所请求的文件。如果本组中无请求的资源，则超级节点将请求信息转发给本组的中转节点，由中转节点向其它组转发该节点请求。

中转节点(relay node，RN)：主要用来连接两个相邻的组。来自不同组的节点之间的交易信息存储在中转节点中。如图1所示，首先，ON10请求ON11拥有的文件。ON10向该组超级节点SN1发送一个查询。如果SN1或该组的其它节点有被请求的文件，SN1向ON10发送响应，该组中某个节点拥有ON10 所请求的文件，则ON10就可以与该节点进行交易。如果SN1所在组中没有ON10所请求的文件，SN1将查询发送给该组的中转节点RN7。RN7将查询转发到不同的组的中转节点，RN8和RN9。中转节点将查询发送给组中的超级节点。因为SN3是ON11所在组的超级节点，所以它有该组中所有节点的文件列表。SN3发现ON11有被请求的文件。P2通过RN9发送响应给RN7，该组超级节点SN1向ON10发送应答响应，SN3所在组中的ON11具有请求的目标文件。

图1 动态分组示例

普通节点(ordinary node，ON)：ON是群组中一个不担任转发任务的普通节点。它可以请求来自于其它节点的资源，也可以将资源分享给其它节点。在与其它节点交易完成后，ON会更新与交易节点之间的信任值，用于其它节点与该节点进行交易时的推荐。交易完成后将信息发送给该组的超级节点。

1.2 节点的管理

1.2.1 节点加入

一个新节点加入一个MP2P网络，首先为这个新的节点设置初始的信任值，这可以保证其它节点可以与之进行交易。当一个节点连接到MP2P网络时，该节点与其它节点之间没有交互的信息，该节点与各组的超级节点的资源兴趣相似度和与各组超级节点间的往返距离是可以计算出来的。这个节点将被添加到兴趣与之最相似且距离又相对较近的组中。如果新节点与所有的超级节点的兴趣相似度和往返距离都相差较大，则新节点自己成为一组，并作为该组的初始超级节点。当许多节点加入MP2P网络时，节点之间的信任关系会不断发生变化。

1.2.2 节点离开

普通节点离开网络的情况。普通节点离开网络时，会向同组的其它节点发送其离开信息。同一组的其它普通节点更新邻居的信息并重新计算信任值。同时，组中的超级节点群组更新其路由信息表和节点资源列表。

中转节点离开网络的情况。如果中转节点离开一个组，它会向同组的其它节点广播其离开的消息。离开的中转节点将其信息传递给同一组中的选出的继任的中转节点。新的中转节点向超级节点发送信息以确认担当继任中转节点的角色。超级节点在接收来自新的中转节点的信息后，向组中的所有节点成员广播关于新的中转节点的消息。收到消息后，所有节点成员更新了关于中转节点的信息。

超级节点离开网络的情况。在一个组中，超级节点管理组中所有节点的信任消息和文件列表。因此，重要的是考虑一个超级节点离开的情况。首先，超级节点被要求广播它的离开消息，然后从备选超级节点群组中选择综合能力值最高的节点作为新的超级节点。新的超级节点接收并存储离开的超级节点传输的组中节点的信任消息和文件列表。组中的所有节点更新关于新超级节点的信息。

备选超级节点离开网络的情况。备选超级节点因为还未担任超级节点的工作，所以当其离开网络时，会像普通节点离开时一样向其邻居节点广播其离开的消息，同一组的其它普通节点更新邻居的信息并重新计算信任值。同时，同组中的超级节点群组更新其路由表和文件列表。如果该节点离开后，组中没有剩余的备选超级节点，则触发备选超级节点更新机制，动态变更备选超级节点能力阈值，选举出新的备选超级节点集合。

2 基于动态分组的超级节点选取机制

2.1 动态分组流程

2.1.1 初始分组

在MP2P网络中，节点包括资源属性和能力属性。本文选择将节点的资源属性作为动态分组的依据之一，节点的能力属性作为超级节点选取的依据。节点的资源属性由兴趣集来表示，节点i的兴趣集定义为Ii={a1，a2，a3，…，ak}。 两节点之间的兴趣相似度计算如下式

(1)

式中：k代表节点的兴趣集的个数。

在初始阶段，首先使用K-Means算法[11]随机选择k个节点作为初始的超级节点，在选择时尽量考虑选择距离位置相距较远的节点。然后，通过k个初始的超级节点建立k个对应的初始组。对于新加入的节点，可以通过式(1)计算它与k个初始超级节点的兴趣相似度。

新加入的节点通过向各组的初始超级节点发送探测消息,计算其与各组的初始超级节点的距离，用RTT来表示。

通过式(2)计算它与k个初始超级节点的综合考量值。节点i和节点j之间的综合考量值计算如下式

(2)

式中：α，β分别表示兴趣相似度和节点间RTT的权重，α+β=1，且满足0<α<1, 0<β<1。RTTmax为网络中两节点间最大的往返距离值，RTTi,j为节点i和节点j之间的往返距离值。

选择新加入节点和各区域超级节点综合考量值最大的超级节点所在组，并加入该组；通过重复这个过程，直至所有的节点都被添加到相应的组中。

初始分组完成后，继续重复不断地计算各组的超级节点并重新分组，直到所有节点不再改变分组(超级节点位置不再改变)。即动态分组完成。

2.1.2 阈值过滤筛选备选超级节点集合

首先对每组内所有节点进行阈值过滤，定义普通节点i的能力属性集合为Capi={Trui,Cali,Stoi,Timi,Bani}，分别代表节点的信任度，计算能力，存储能力，平均在线时间，带宽等。在MP2P网络中对超级节点的能力阈值定义为：Capt={Trut,Calt,Stot,Timt,Bant}。 各项能力均超过超级节点能力需求阈值的进入备选超级节点集合。其中节点的平均在线时间计算如下式

(3)

式中：TotTi代表节点的累积在线时间总长，n代表节点的上线次数。

2.1.3 超级节点选取策略

通过备选超级节点阈值筛选的备选超级节点,根据式(4)对备选超级节点的综合能力进行计算,从中选择综合能力值最大的节点确定为初始的超级节点

PVal=w1PTru+w2PCal+w3PSto+w4PTim+w5PBan

(4)

式中：w1+w2+w3+w4+w5=1，PTru表示节点的信任度，PCal表示节点的计算能力，PSto表示节点的存储能力，PTim表示节点的平均在线时间，PBan表示节点的带宽。其中w1、w2、w3、w4、w5分别为5个能力因素的权重，需满足w1+w2+w3+w4+w5=1。

为防止恶意节点和临时节点被误评为超级节点,造成网络的不稳定,因此在选取机制中赋予w1和w4更大的权重。由此选出的超级节点可靠性较高，形成的网络比较稳定。

2.1.4 备选超级节点选取策略

超级节点离开时首先广播它的离开消息，然后根据选择备选超级节点群组中综合能力最高的备选节点成为该组新的超级节点。一个新的超级节点确认后，所有的信任消息和该组的文件列表都被转移到新的超级节点上。新的超级节点接收原超级节点接传输的信息。新超级节点信息接收完毕后，原超级节点正式退出。该组中的所有节点更新它们对新超级节点的信息。

选取备选超级节点群组中综合能力最强的备选节点加入现有超级节点，成为超级节点群组，为剩余负载能力不足的超级节点承担一定的负载请求。超过超级节点负载阈值后，启动选举策略，选取备选超级节点集合中综合能力最强的备选节点加入超级节点群组，与原先的若干超级节点共同承担超级节点的工作。备选节点加入后，原超级节点将拥有的本组的信任表和该组中所有节点的文件列表发送给该备选节点。

2.2 算法流程

本文算法的总体步骤如算法1所示。

算法1：动态分组

步骤1 首先确定节点的资源类型个数，记为k个，随机选取k个节点作为初始超级节点，选取时尽量选择物理位置相距较远的节点；

步骤2 建立k个初始组，并将初始超级节点加入对应组中；

步骤3 将加入的新节点根据式(2)得到与各初始超级节点的综合考量值，选择综合考量值最大的超级节点所在组，并加入该组；循环此步骤直到所有节点全部加入对应组中；

步骤4 所有节点加入对应组后，根据算法2提出的组内超级节点选取算法进行组内超级节点群组与备选超级节点集合的选取；

步骤5 如果组内的超级节点群组与上次超级节点选取后的超级节点群组相同，则动态分组完成；否则重复算法2。

超级节点群组和备选超级节点集合的选取算法如算法2所示。

算法2：超级节点群组和备选超级节点集合选取

步骤1 对每组内所有节点进行综合能力的筛选，通过阈值筛选的节点进入每组的初始备选超级节点集合;

步骤2 根据系统中对于超级节点不同能力的需求，确定各个能力属性的权重因子;

步骤3 根据式(4)计算出所有备选超级节点的综合能力值;

步骤4 选择综合能力值最大的节点作为该组的超级节点，其它节点则作为备选超级节点，当超级节点退出或者被评定为恶意节点后，由备选超级节点中选择综合能力值最大的节点作为继任的超级节点。

3 仿真分析

3.1 仿真场景

利用Matlab在DGSM、基于兴趣动态分组的超级节点选取机制(dynamic grouping trust model，DGTM)、基于区域划分的超级节点选取机制(super node selection mechanism，SNSM)和传统的未分组的SNSM进行对比验证。仿真参数设置见表1。

表1 仿真参数设置

3.2 仿真结果分析

3.2.1 动态分组后的节点分布

图2、图3分别是动态分组前后的节点分布情况。会发现此种分组下会有一部分物理位置距离稍远但兴趣相似的节点会分到一组中，这样的分组方式保证了即使同组内相距较远的两节点进行交易时，虽然两节点的物理位置相距较远，但因为在同一个分组下，省去了不同组间超级节点和中转节点的信息传递和请求转发的时间，减少了网络中的整体的信息检索延迟。在网络规模越大的系统中，该种分组方式在网络中信息检索延迟和网络资源定位成功率越好。

图2 动态分组前的节点分布

图3 动态分组后的节点分布

3.2.2 信息检索延迟比较

在本实验中，采用类Flooding的算法，检索延迟是消息在传播路径上的延迟总和，根据传播路径上每一跳的节点间的距离之和来计算。

图4、图5是节点数为200的情况下，节点请求次数分别从0到200和0到1000时，DGSM和其它3种超级节点选取机制下网络中信息检索延迟。图中横坐标代表节点的请求次数，纵坐标代表信息检索延迟。从图中可知，DGTM和基于区域划分的超级节点选取机制下当节点请求次数分别到达550和700时，其信息检索延迟增长率会突然升高，而此时DGSM下的信息检索延迟还处在一个较低的水平。DGSM通过形成在网络物理拓扑中距离相近的相似兴趣节点进行聚类分组，更大程度地使得资源在组内共享，减少了由超级节点组成的高速转发层的带宽损耗，降低了网络中信息检索延迟。

图4 请求次数从0到200时各机制信息检索延迟比较

图5 请求次数从0到1000时各机制信息检索延迟比较

3.2.3 网络资源定位成功率比较

图6是各机制下网络资源定位成功率的比较，如图所示，随着节点请求次数的增加，本文提出的机制在资源定位成功率上一直保持较高的资源定位成功率。相比于其余几种机制，资源成功率随着节点请求次数的增加下降数率明显较低。且当节点资源请求次数达到1000次时，相比于其它3种超级节点机制，本文提出的机制在资源定位成功率上分别提高了15.4%、20%、157%，验证本文提出的超级节点选取机制可以有效的提高网络中资源定位成功率。

图6 各机制网络资源定位成功率比较

4 结束语

本文提出了一种基于动态分组的超级节点选取机制(DGSM)。通过综合仿真结果表明本算法与其它最新算法相比，经过动态分组的超级节点选取机制可以有效地降低MP2P网络的信息检索延迟，提高网络中资源定位成功率，并且具有较好的扩展性。因此，本文提出的基于动态分组的超级节点选取机制可有效提升MP2P网络的动态适应性，降低了网络的信息检索延迟,提高了网络资源定位成功率。