抗扰动移动对等覆盖网的构建及性能评价

李军，张国印，王向辉

(1.哈尔滨工程大学计算机科学与技术学院，黑龙江 哈尔滨 150001;2.安庆师范学院 数学与计算科学学院，安徽 安庆246133)

随着手机的普及以及平板电脑、智能手机等移动互联网络终端设备的流行，在移动网络中应用P2P技术开始得到重视。由于移动网络的特殊性，使得互联网上的很多成熟技术无法直接应用于移动网络。因此，移动对等网络的研究还主要集中在核心机制研究上。在移动对等网络的诸多问题中，覆盖网的构造是一个关键性的问题。覆盖网的结构直接决定了移动P2P系统的可扩展性、鲁棒性、安全性和抗扰动性。在面向移动自组网的移动对等覆盖网构造算法中，使用跨层方法的占了绝大多数［1-4］。该方法能够提高查询成功率，涉及到具体的网络层路由协议和MAC层协议，通用性较差。原型改进方法能够应用于不同的底层网络，可以利用原有相对比较成熟的路由协议、资源查询算法等，并方便移动对等网络和传统P2P网络的互联［5-8］。但这种方法必然要遵循已有的框架进行改造，从而限制了算法的改进范围。利用博弈论的方法是通过定义一个节点间的博弈来构建一个达到预期目标的覆盖网，生成的覆盖网对于预期目标来说能够接近最优，但不是十分稳定，对于扰动的适应性也较差［9-10］。本文为了构建高效抗扰动的移动对等覆盖网，首先提出了一个基于k-派系社区结构的网络拓扑并设计了多种抗扰动机制，然后对其数据分发机制进行了研究，通过动态调整不同节点的数据分发概率来提高数据分发效率，最后提出了一个三维的移动对等覆盖网性能评估模型，并根据这一模型对多个覆盖网进行了性能评估。

1 基于k-派系的网络拓扑结构

针对复杂网络中社区结构的检测和发现已经提出了多种算法，但对于社区结构的构造算法还较少见。通过构建具有k-派系社区结构的覆盖网，可以保证该网络具有较高的聚集系数和较短的平均路径长度，从而使其表现出小世界特征［11-12］。

每一个节点在加入覆盖网时进行初始化，其数据结构包括跳数值、初始状态值、动态状态值等，并建立3个空列表，第1个是邻居节点列表，第2个是资源共享索引列表，最后一个是外联节点列表。其中，最先加入网络的节点称之为中心节点，跳数为0，邻居节点列表中包含其他派系节点的节点称之为外联节点。根据自身的处理能力和网络带宽等情况计算节点初始状态值S:

式中:c为节点运算能力值，m为节点存储能力值，d为节点当前电量，b为节点当前网络带宽，α、β、γ、δ为权值，α+β+γ=1，0≤S＜1。

计算节点的动态状态值Sr:

式中:j为节点跳数。

每个节点只属于一个k-派系。基于k-派系社区结构的覆盖网结构示意图如图1所示。

图1 基于k-派系的移动对等覆盖网拓扑结构图Fig.1 Topology of k-clique based mobile P2P overlay

图1中1～10号节点由1个3-派系组成，11至17号节点构成了一个2-派系。黑色节点为中心节点，灰色节点为外联节点。实线表示派系节点内链接，虚线表示相邻派系节点间链接。

2 抗扰动机制

本文提出的移动对等覆盖网络首先采取数据冗余策略，将单个节点的资源索引列表复制给同派系的多个节点进行存储，从而降低单个节点失效给系统造成的影响。过度数据冗余或者不当的数据复制策略，有可能造成系统崩溃，尤其对于移动网络节点来说，网络带宽在很多情况下无法支持大量数据进行节点间的复制。为此，本文提出了适合移动网络的数据分发机制，并在特定范围内对资源索引列表而不是资源本身进行复制，以降低网络负载。

其次，采用路由表修复技术来保证路由的有效性。采用心跳机制周期性地探测邻居节点，当节点心跳数在规定时间内不再增加时即判定其已经失效，从而主动发现失效节点并修复路由表。

最后，采用拓扑结构自适应来提高抗扰动能力。当某个节点退出或失效时，覆盖网网络拓扑自动进行修改，从而提高网络的抗扰动能力。同时，通过主动外联过程和被动外联过程保持本派系节点与其他派系的链接，确保网络的连通性。

3 性能评价模型

扰动情况下移动对等覆盖网的性能评估可以通过本文提出的三维评价模型来进行。该模型中的第1个维度包含移动对等覆盖网中影响扰动的直接因素，主要指扰动模型及其参数，扰动模型有指数分布扰动模型、重尾分布扰动模型、Pareto分布扰动模型、KAD扰动模型等;第2个维度包含移动对等覆盖网中影响扰动的间接因素，如节点的数量、节点的移动速度和节点的移动模型等。节点的移动模型可分为个体移动模型和群体移动模型，个体移动模型中使用最多的是随机路点移动模型;最后一个维度主要包含扰动情况下移动对等覆盖网的性能评价指标，如资源查找成功率、资源平均查询时间和网络负载等。

4 性能评估实验

为了验证本文提出的覆盖网在移动网络中的性能，在Peerfactsim模拟器［14］上对该网络进行模拟，并命名为KCCO(k-clique community overlay)。Peerfactsim模拟器是德国大学达姆施塔特技术大学利用Java语言开发的开源P2P网络模拟实验平台，具有通过离散事件触发的特点。实验中通过设定节点扰动模型来模拟网络的扰动情况，并改变节点数目和节点平均移动速度等参数来得到覆盖网的查询成功率和平均查询时间。

4.1 模拟实验设置

底层网络采用移动自组网，节点活动面积为1 000 m×1 000 m。每个节点的无线传输距离设置为240 m，信道容量设为2 Mb/s，节点的移动模型采用随机路点移动模型，节点的移动速度设置为1～10 m/s。节点扰动模型设为指数扰动模型。节点资源分布模型为zipf分布，系数设为0.7。

为了评估扰动情况下移动对等覆盖网的性能，本文选择了另外2种覆盖网进行对比。其中一个是GIA，它为了提高Gnutella的可扩展性，通过满意度参数使有更高能力的节点接受更多的邻居节点和查询请求，实现负载均衡并提高查找效率［13］;另一个覆盖网M-GIA是专为移动网络设计的改进GIA模型，它改变了节点ID的生成规则并增加了位置信息，通过节点ID来计算2个节点之间的距离［1］。M-GIA中的每一个节点根据满意度和与请求节点的距离来共同决定是否接受一个新的邻居节点。

实验中所评估的3种覆盖网具有一部分共同的参数，其参数名称及参数值如表1所示。此外，MGIA中的权值α和β分别设为0.5和0.5。KCCO中每一个k-派系的k值都设为5。

表1GIA、M-GIA、KCCO共同实验参数配置表Table 1 GIA，M-GIA，and KCCO's common experimental parameter settings

4.2 模拟实验结果

指数扰动模型的一个主要参数是平均会话时长，默认值设为60 min。对于3种覆盖网来说，默认的网络节点数是600个，默认的平均节点移动速度是6 m/s。接下来通过改变上述3个参数中的任意一个参数，而将其他2个参数设为默认值的方法来评估3种覆盖网的性能。

首先将平均会话时长设为60 min，平均节点移动速度设为6 m/s，将节点数目从200增加到1 000分别进行模拟实验，实验结果如图2所示。从图2可以看出，当节点数量少于800时，KCCO具有最短的平均查询时间，但是当节点数超过800时，它成了耗时最长的一个。M-GIA在节点数目较少的情况下平均查询时间高于GIA，但随着节点数目的增加，其平均查询时间逐渐接近并最终低于GIA。

图2 不同节点数目下的平均查询时间Fig.2 Average query delay with different numbers of nodes

在不同节点数目下的查询成功率如图3所示。无论节点数量是多少，与其他2种网络相比，KCCO均能取得较高的查询成功率，始终保持在其他2种覆盖网的一倍以上。当节点数少于600时，M-GIA比GIA取得了更高的查询成功率。随着节点数量的增长，3种覆盖网均表现出平均查询时间增长而查询成功率下降的情况。

图3 不同节点数目下的查询成功率Fig.3 Query success rate with different numbers of nodes

其次将平均会话时长设为60 min，节点数目设为600，将节点平均移动速度从1 m/s增加到10 m/s分别进行模拟实验，实验结果如图4所示。

图4 不同节点移动速度下的平均查询时间Fig.4 Average query delay with different moving speeds of nodes

KCCO的平均查询时间最短，随着节点移动速度的增加有所增加。当节点平均移动速度较慢时，GIA要好于M-GIA，反之则不如M-GIA。不同节点平均移动速度下的查询成功率如图5所示。KCCO的查询成功率始终远远高于其他2种覆盖网，当节点移动速度较高时略有下降。M-GIA和GIA各有优劣，多数情况下M-GIA的查询成功率略高于GIA。

图5 不同节点移动速度下的查询成功率Fig.5 Query success rate with different moving speeds of nodes

最后将节点数目设为600，节点移动速度设为6 m/s，将平均会话时长从6 min增加到60 min分别进行模拟实验。不同平均会话时长下的平均查询时间如图6所示。随着平均会话时长的增长，3种网络的平均查询时间反而增加。M-GIA的平均查询时间在绝大多数情况下都是最长的。

图6 不同平均会话时长下的平均查询时间Fig.6 Average query delay with different mean session lengths

不同平均会话时长下的查询成功率如图7所示。当网络的平均会话时长延长时，KCCO的查询成功率快速增加，而其他2种覆盖网的查询成功率基本保持不变，KCCO在扰动剧烈的情况下仍然保持了较高的查询成功率。

图7 不同平均会话时长下的查询成功率Fig.7 Query success rate with different mean session lengths

4.3 实验结果评价

3种覆盖网在所有情况下的平均查询时间相差不是很大，GIA与M-GIA在所有情况下的查询成功率比较相近。表2和表3为3种覆盖网在不同参数下的平均查询时间和查询成功率的比较。可以看到KCCO的平均查询时间是最短的，M-GIA的平均查询时间最长。KCCO的查询成功率明显高于其他2种覆盖网，M-GIA的查询成功率在节点数目变化时高于GIA。

表2 3种对等覆盖网在不同参数下的平均查询时间比较Table 2 Average query delay comparison of three overlays

表3 3种对等覆盖网在不同参数下的查询成功率比较Table 3 Query success rate comparison of three overlays

5 结束语

本文提出了一种基于k-派系社区结构的移动对等覆盖网KCCO，通过构造一个具有多个不同k-派系结构的网络拓扑，并结合数据冗余、主动路由修复和拓扑结构自适应等多种机制来提高覆盖网的性能，增强抗扰动能力。提出一种三维的移动对等覆盖网性能评估模型，包含了移动性和扰动性等多个移动对等网络的特性，并在此基础上对多个覆盖网在扰动情况下移动网络中的性能进行了比较分析。评估结果显示，本文提出的移动对等覆盖网KCCO在扰动情况下显著提高了资源查询成功率，缩短了平均查询时间。

［1］HAN D D，ZHANG J.An optimized Gnutella-like P2P protocol in mobile networks［J］.Journal of Networks，2012，7(9):1464-1471.

［2］彭利民，肖文俊.一种具有常数度的无线P2P覆盖网［J］.四川大学学报:工程科学版，2011，43(4):124-130.PENG Limin，XIAO Wenjun.A wireless P2P overlay network with constant degree［J］.Journal of Sichuan University:Engineering Science Edition，2011，43(4):124-130.

［3］MEI Jingqing，JI Hong，LI Yi.Query routing mismatch alleviation architecture for P2P file lookup in MANETs［J］.The Journal of China Universities of Posts and Telecommuni-cations，2011，18(4):111-117.

［4］ZHOU Hui，YANG Jie.Spiralchord:a space-filling curve based location awareness，cross-layering P2P file sharing system in WMNs［J］.The Journal of China Universities of Posts and Telecommunications，2012，19(3):44-53.

［5］GOUVAS P，BOURAS T.Ubi-chord:services provision in dynamic networks based on P2P protocols［C］//18th International Conference on Telecommunications.Ayia Napa，Cyprus，2011:375-380.

［6］MARIEM T，NAHIL T，TAREK B，et al.Enhanced backtracking Chord protocol for mobile Ad hoc networks［C］//International Conference on Communications and Information Technology.Hammamet，Tunisia，2012:191-195.

［7］CHANG Jianming，LIN Yihsuan，ISAAC Woungang，et al.MR-Chord:a scheme for enhancing Chord lookup accuracy and performance in mobile P2P network［C］//IEEE International Conference on Communications.Ottawa，Canada，2012:5408-5412.

［8］ZULHASNINE M，HUANG Changcheng，SRINIVASAN A.Towards an effective integration of cellular users to the structured peer-to-peer network［J］.Peer-to-Peer Networking and Applications，2012，5(2):178-192.

［9］MAWJI A，HASSANEIN H.P2P overlay topology control in MANETs［C］//IEEE International Symposium on A World of Wireless，Mobile and Multimedia Networks.Montreal，Canada，2010:1-9.

［10］MAWJI A，HASSANEIN H，ZHANG X Y.Peer-to-peer overlay topology control for mobile ad hoc networks［J］.Pervasive and Mobile Computing，2011，7(4):467-478.

［11］LUCE R D，PERRY A D.A method of matrix analysis of group structure［J］.Psychometrika，1949，14(2):95-116.

［12］LUCE R D.Connectivity and generalized cliques in sociometric group structure［J］.Psychometrika，1950，15(2):169-190.

［13］YATIN C，SYLVIA R，LEE B，et al.Making gnutellalike P2P systems scalable［C］//Conference on Applications， Technologies， Architectures， and Protocols for Computer Communications.Karlsruhe，Germany，2003:407-418.

［14］DOMINIK S，CHRISTIAN G，JULIUS R，et al.PeerfactSim.KOM:a simulation framework for peer-to-peer systems［C］//The 2011 International Conference on High Performance Computing and Simulation.Istanbul，Turkey，2011:577-584.