基于节点移动特性的移动P2P网络分簇算法

宋人杰，邹振婉，周欣欣

(东北电力大学 信息工程学院，吉林 吉林 132012)



基于节点移动特性的移动P2P网络分簇算法

宋人杰，邹振婉，周欣欣

(东北电力大学 信息工程学院，吉林 吉林 132012)

摘要：为了提高移动P2P网络的覆盖层拓扑稳定性，提出一种基于节点移动特性的移动P2P网络分簇算法。该算法通过对移动P2P网络的覆盖层拓扑变化与节点移动特性的关系的研究，将具有相同运动特性且物理位置临近的节点聚集成簇，并选取性能较好的节点作为簇首，使得簇内节点能够最大程度的保持覆盖层拓扑结构的稳定性。最后通过实验验证了该算法的有效性。

关键词：移动P2P网络；分簇算法；运动特性；拓扑变化

作为一种新兴的移动数据共享方式，移动P2P网络以其具有无中心、自组织等特性，在军事战场、抢险救灾以及用户信息共享等领域有着重要的实用价值和广阔的应用前景[1，2]。然而，由节点的移动性造成的覆盖层拓扑频繁变化问题[3]，不仅减低了覆盖层的数据传输速率，同时会产生大量的冗余信息，对底层物理网络造成巨大的带宽压力，降低网络的整体工作性能。

能够感知网络拓扑的分簇方法虽然可以解决覆盖层拓扑的频繁变化问题，但网络开销较大且缺乏对节点的移动特性的考量。通过对节点移动特性的研究发现，在实际应用环境中，移动节点的行为通常不是随机的，节点间的关系和覆盖层拓扑变化与现实社会有联系，呈现分组活动特性[4，5]。因此，本文从节点移动特性出发，充分利用这种潜在关系，提出一种基于节点移动特性的移动P2P网络分簇算法，从而解决网络拓扑的频繁变化问题，减少拓扑维护费用、提高系统稳定程度，对提高移动P2P网络服务质量具有重要意义。

1基于节点移动特性的分簇算法

研究发现在实际的环境中，比如参观者在参观博物馆时，每个参观者都根据自身的不同兴趣以不同的速度循着不同的路线行进。因为参观者之间有相同兴趣和爱好，参观者在走动中常常会表现出分组特征，如图1、图2所示。所以，本文提出的分簇算法的核心思想是：根据节点移动特性，将具有相同移动特性且物理位置临近的节点聚集成簇，使得簇内节点由于具有相同运动特性，从而能够最大程度的保证分簇的稳定程度。

图1 参观者初始位置图2 一段时间后参观者的位置

1.1相关定义

定义1：无向图G(V，E)表示移动P2P网络的覆盖层拓扑关系，V表示移动节点集合，E表示边集合。

定义2：如果节点u和v之间有如下关系边(u，v)∈E，那么节点u和v互为相邻节点。

定义4：如果节点u和v是朋友节点，节点v和w也是朋友节点，那么节点u和w是朋友节点。

定义4将相邻节点间的朋友节点关系扩展到了不相邻的节点之间，节点u与v的距离、平均值以及标准方差的计算方法如下：

(1)

(2)

(3)标准方差δ的计算方法：

(3)

1.2簇首节点的选取

在移动P2P网络的维护和查询过程中需要簇首不仅有较强的计算能力，能够及时响应并处理查询请求，而且需要簇首拥有充足的存储空间以便于容纳更多的节点信息。因此这里选择节点的CPU处理速率、存储容量以及有效带宽作为衡量节点性能的重要因子。节点性能Ability的计算方法如下：

Ability[u]=α×B[u]+β×C[u]+γ×S[u]，

(4)

1.3簇生成算法

分簇算法的步骤如下：

步骤S1，按照公式(4)计算节点的性能Ability值。

步骤S2，按照公式(1)、(2)、(3)计算节点与其相邻节点的距离、平均值以及标准方差。

步骤S3，依据节点的移动特性，节点建立自身的朋友节点列表，具体方法是：假设节点u和v满足定义3，则节点u将节点v加入到自己的朋友节点列表中，节点u与节点v周期性地交换彼此处的朋友节点列表，若节点w是节点v的朋友节点，但节点w不在节点u的朋友列表中，则将节点u将节点w加入到其朋友列表中；若节点u的朋友列表中已经存在节点w，但其全部朋友节点发来的朋友节点列表内并不存在节点w，则将节点w从节点u的朋友列表内删除。

步骤S4，依据节点的移动特性，选取簇首节点，构建分簇结构，具体方法是：将节点u的Ability值与其朋友列表中的节点进行比较，如果节点u的Ability值最大，则节点u升级成簇首，并将此消息广播给它的朋友节点，同时邀请朋友节点进入该节点所在的簇；若节点u的Ability值不是最大，则申请加入以Ability值最大的朋友节点为簇首的簇中。

步骤S5，重复步骤S2-步骤S4，直到网络中所有节点或成为簇首节点，或从属于某一个簇内。

1.4簇动态维护算法

新节点加入过程：节点首先向周围节点发送HELLO消息以获取与邻近节点之间的距离，然后根据距离关系构建朋友节点列表，并向其所有朋友节点发送信息以获取其所有朋友节点所属簇对应的簇首信息，最后向这些簇首发送HELLO消息以获取两者之间的距离，通过比较，选取相距最近的簇首申请加入其簇。

节点离开：若离开节点是普通节点，该节点会向其所有朋友节点及簇首发送离开消息，簇首在收到消息后，更新簇成员列表。若离开节点是簇首，簇首会向其朋友节点及簇成员发送离开消息，以便朋友节点能及时更新朋友节点列表，簇成员能及时重新选取簇首避免发生网络故障。

节点失效处理：若网络中的某个节点已经失效，那么其朋友节点能够通过定期的心跳函数检测到该情况。若失效节点是普通节点，那么在朋友节点检测出其失效后，该朋友节点首先会把其从朋友节点列表删除，其次检查两者是否属于同一个簇，若属于同一个簇，则通知簇首该节点已失效，否则仅更新自身朋友节点列表；若失效节点是簇首，当朋友节点检测到该节点已失效后，该朋友节点首先更新自身的朋友节点列表，其次检查两者是否属于同一个簇，若属于同一个簇，则通知其它节点，簇首已失效，并再次选择簇首，否则仅做更新朋友节点列表处理。

2仿真分析

本文采用NS-2.4[6]仿真工具对提出的分簇算法C-MP2P和Clustering Scheme[7]进行对比。80个移动节点都基于组移动模型RPGM[8]且分布在200×200 m的正方形内，节点所具有的最大移动速度是20 m/s，天线覆盖范围被设置成100 m，实验进行300 s，每隔2 s节点与相邻节点进行一次HELLO消息传输。

簇首的变化速率和节点状态的变化速率被用来衡量C-MP2P算法的性能，簇首变化速率是指簇首在单位时间范围内的变化次数，用模拟时间段内簇首的改变次数除以模拟时间来对其进行表示，簇结构的稳定程度取决于簇首的变化频率，频率越小，越稳定；节点状态变化速率是指成员节点在单位时间内的状态变化次数，其值表示为模拟时间内成员节点发生改变的次数与模拟时间的商，簇结构的稳定度与节点状态的发生改变的次数有关，次数越小越稳定[9,10]。

图3和图4分别表示簇首的变化速率和节点状态的变化速率随节点速度变化的情况。由图3和图4可知，伴随节点的移动速度的不断增加，这两种算法对应的簇首变化率和节点状态变化率均随之增加，这说明节点移动的速率越快，簇结构的稳定性也会随之降低。由于C-MP2P算法对节点的移动特性考虑的较为充分，同簇节点具有相同的运动特征，速度变化大致相同，而Clustering Scheme算法并未考虑这些因素，因此C-MP2P算法的性能受速度变化的影响较小，性能明显优于Clustering Scheme算法。

图3 簇首变化速率图4 节点状态变化速率

3总结

本文根据移动P2P网络覆盖层拓扑结构变化与节点的移动特性之间的联系，提出一种基于节点移动特性的移动P2P网络分簇算法。该算法将物理位置临近且具有相同运动特征的两个相邻节点划分到一个簇内，使得在分簇时可以产生更稳定的簇结构。由仿真结果可知，该算法可以有效提升分簇的稳定程度，适应于具备高度移动性的无线网络环境，有很大的实用价值。

参考文献

[1]Xin-Xin Z，Zhen-Wan Z，Peng K，et al.A Survey of Resource Discovery in Mobile Peer-to-Peer Networks[C]//Communication Systems and Network Technologies (CSNT)，2015 Fifth International Conference on.IEEE，2015:122-125.

[2]Waluyo A B，Taniar D，Rahayu W，et al.Mobile Peer-to-Peer data dissemination in wireless ad-hoc networks[J].Information Sciences，2013，230:3-20.

[3]欧中洪，宋美娜，战晓苏，宋俊德.移动对等网络关键技术[J].软件学报，2008，19(2):404-418.

[4]张斯捷，柏青，苏旸.移动P2P网络中基于稳定组的双向匿名通信方案[J].计算机应用，2013，33(6):1615-1618.

[5]吴旭.基于增强稳定组模型的移动P2P网络信任评估方法[J].计算机学报，2014，37(10):2118-2127.

[6]Ns-2 network simulator [EB/OL].[2013-05-16].http://www.Isi.edu/nsnam/ns/.

[7]杨忠仪，左克.一种适用于移动对等网络的分簇算法[J].计算机工程与科学，2014，26(7):1268-1274.

[8]Wang K H，Li B.Efficient and guaranteed service coverage in partitionable mobile ad-hoc networks[C]//INFOCOM 2002.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings.IEEE.IEEE，2002，2:1089-1098.

[9]张强，胡光明，陈海涛等.MANET基于客观信任度建模的分簇算法与分析[J].通信学报，2009，30(2):12-21.

[10] 宋人杰，史长东，崔卫丽.复杂场景中多细节层次模型生成新算法[J].东北电力大学学报，2014，34(13)：80-84.

A Clustering Algorithm Based on Node Mobility for Mobile P2P Network

SONG Ren-jie，ZOU Zhen-wan，ZHOU Xin-xin

(School of Information Engineering，Northeast Dianli University，Jilin Jilin 132012)

Abstract：Aiming at the problem that layer topology changes frequently in mobile P2P network which is caused by node mobility，a clustering algorithm based on node mobility is proposed.By studying the relationship between the changes of the topology structure and the changes of node mobility，this algorithm divide the nodes with adjacent physical location and same mobility into a cluster，and select the nodes which has the best performance as the cluster-head，which makes the nodes in the same cluster can maintain the maximum degree of network topology stability.Experimental results show the effectiveness of proposed algorithm.

Key words：Mobile P2P networks；Clustering；Mobility；Topology change

中图分类号：TP393

文献标识码：A

文章编号：1005-2992(2016)01-0087-04

作者简介：宋人杰(1963-)，女，吉林省吉林市人，东北电力大学信息工程学院教授，硕士，硕士生导师，主要研究方向:计算机在电力系统中的应用.

收稿日期：2015-12-18