基于行为特征的超级节点节流算法研究

电子科技大学 电子科学技术研究院，成都 611731

电子科技大学 电子科学技术研究院，成都 611731

1 引言

P2P网络技术具有良好的可扩展性和健壮性，当前已被广泛使用。由最初的有中心节点的集中式网络结构，到完全随机的泛洪方式（全分布式非结构化网络），到分布式散列表（DHT）结构。P2P网络拓扑在不断变化和发展。超级节点是一个子P2P网络的中心，一般通过P2P子网中的节点选举担任。超级节点负责收集子网中其他节点的索引信息，以提高整个P2P网络的搜索查询效率。目前，超级节点普遍采用终身制，即超级节点一旦被选出，就会一直工作到节点失效[1]。超级节点网络的流量包括控制流和数据流两部分[2]。目前对数据流量的优化主要依靠查询算法和数据压缩，对于网络控制流量的优化则主要依靠改进超级节点选举算法。

P2P网络中节点具有动态性和不稳定性，可能发生断开、崩溃或拥堵等现象。由于超级节点比普通节点掌握更多的网络资源，因此其突然失效会对网络查询效率产生很大影响。文献[3]给出了chord网络中查询效率和节点失效率的关系公式。其中，p为chord网络中平均节点失效率（即网络中失效的节点占总节点数百分比），n为网络中节点数，h(n)为网络中平均查询跳数。h(n)越大，则查询效率越低。

公式（1）是一个递归公式，由公式可以看出，随着网络中参与查询的节点失效率增加，查询跳数非线性增大，导致较大的网络延时。

当超级节点失效时，重构网络造成的开销是相当大的。子网先要通过泛洪或DHT的方式通知各子网节点进行新一轮的选举，在选出新继任的超级节点后，新超级节点还要重新收集子网中的资源信息，以重建子网索引。

P2P网络的带宽占用问题一直是制约P2P技术推广和应用的一个关键问题。目前，对超级节点网络降低流量的研究较多集中于对超级节点的选择标准上。文献[4]提出以CPU动态处理能力为考量标准，建立一套超级节点选取算法。文献[5]为每个节点设置了能力值作为选举超级节点的标准，并结合候补节点达到降低失效率的目的。文献[6]为超级节点选举设计了多个标准，普通节点根据需要加入到以不同标准选择出的子网中，通过分类的方式减少查询次数。文献[7]提出了一种基于信誉感知的超级节点选择算法，在选举超级节点的时候不仅以节点性能做参考标准，还增加了安全属性。文献[8]提出了根据节点的ISP信息选择查询路由，从而减少查询跳数达到节流的目的。文献[9]通过监测局域网内的P2P流量，合并对外的网络报文达到降低下载流量的目的。文献[10]针对P2P流媒体流量提出了利用随机网络编码实现全局网络流量优化。但这些研究只关注了超级节点的选取对网络查询算法流量的优化，却忽略了超级节点产生和失效时重新收集资源对网络带宽产生的负担。文献[11]提出通过建立备选超级节点的方式减少单点失效问题，与本文的思想比较相近，但对候补超级节点的选择没有给出依据，具有很大的随机性。

为降低网络单点失效而重新枚举资源所产生控制流量的问题，本文提出了一种超级节点禅让算法。通过统计用户行为特征，对网络节点失效问题进行预判，从而尽量避免不必要的流量开销，达到网络节流的目的。并且通过与常用选举算法配套做对比仿真实验，说明算法取得了很好的降低通信流量的效果。

2 算法原理

图1为一个混合型P2P网络常见的拓扑结构。P2P网络的每个节点是由人操作的，因此节点的存活状态也会受人的生活状态影响，存在一定的规律。比如上班族的工作主机通常早上9点左右开机，下午5点左右关机；学生寝室晚上11点停电；一些服务器设定早上自动开启，晚上自动关闭等。这一类节点可以通过统计其生存周期，从而预先估计失效时间。对用户行为进行分析建模是近年来十分活跃的研究课题[12]，这种行为分析方式同样可以引入节点节流算法研究中来。

图1 混合型P2P网络拓扑图

基于这种规律，本文提出了一种超级节点禅让算法（Super-Peers Abdication Algorithms，SPAA），通过一种新的方式达到控制节点失效开销的目的。SPAA算法作用于超级节点选举产生之后，与各种选举算法不冲突，可以叠加使用。使用SPAA算法能够减少由于超级节点失效产生的控制流量，并且降低了超级节点失效率，从而间接也能降低查询流量。

Fernandez等人认为超级节点选举与领导人选举有相似的思想，可以借鉴其选举机制[13]。但其实选举超级节点与选领导人在实际应用中有一个本质不同。不同之处在于人类社会关系中上一届领导的决策会受包括个人因素在内的多种因素影响，因此用上级指派方式无法选出真正合适的人选，需要以选举方式加以规范和制约。但在计算机的世界中不会存在这些不确定因素，对节点性能可以有标准统一的评价，超级节点也不会徇私舞弊，因此用指派方式能获得更高的效率。

超级节点的功能就是将大网络划分为小网络，作为小网络对外的代理，发现算法仅在超级节点之间转发[14]。因此当一个超级节点失效时，自然应当从其所在子网中选择一个继任者。SPAA算法的基本思想就是在失效时间到来之前，超级节点通过主动退位的方式，将超级节点的地位和所掌握的资源通过指派的方式禅让给子网中另一个更稳定的节点。由于是主动退位而不是忽然失效，超级节点有充裕的时间将自己所掌握的资源转移，并通知子网其他节点，避免重新投票和重新收集资源的开销。

3 算法实现

3.1 流程

超级节点的首次产生依然采用选举算法，如果超级节点由于预测算法失败而忽然失效，SPAA算法会退化回重新选举型算法。

根据SPAA算法原理，图2给出使用SPAA算法节点登录的流程图，其中PSnew为更新的节点存活率时刻表，用于估计当前节点在接下来的一段时间内的存活率变化情况。K为网络中对存活率设定的阈值，一旦超级节点的存活率低于阈值，就要启动禅让流程。t为从注册时刻之后节点低于阈值的时刻，作为禅让流程中继任节点的选择依据。

图2 节点登录流程图

算法说明：

（1）普通节点登录首先要进行初始化，根据前次登录情况更新上线概率PSnew。PSnew的计算方法将会在3.2节中具体给出。

（2）然后节点连接到P2P网络，从超级节点获取网络的配置阈值K。阈值K的选择需要根据具体应用的稳定性而定，本次仿真实验得到的一个经验值为8 700左右。如果阈值选取过高，而会导致频繁的超级节点更替，选取过低则容易导致预测失败。

（3）普通节点计算本机存活率低于阈值的时刻t。根据普通用户的作息规律，实验的统计周期为一天，t值即为当天节点下线时间的估计值。

（4）节点将计算得到的t值注册到子网的超级节点中，作为超级节点禅让的选择依据。同时进行动态身份认证，双方记录身份密钥作为禅让时广播继任节点信息的身份依据（密钥安全认证问题不作为本文研究重点，在此不做详细分析）。

（5）之后普通节点进行正常的P2P通信，并监听超级节点更换消息。

开销比较：

与普通P2P网络节点登录相比，SPAA算法增加了K值获取和t值注册几个环节，只有几个字节的通信数据增加。这些数据也可以附加在正常P2P登录通信中，基本没有增加开销。并且节点注册时间都相对分散，不会造成网络的短期数据拥堵。

图3为使用SPAA算法进行超级节点禅让的流程图。当超级节点自己的存活概率低于阈值时，启动禅让流程。从登陆流程中可以看到，此时超级节点已经建立了一份子网节点的信息列表，记录了子节点的存活情况。

图3 超级节点禅让流程图

算法说明：

（1）原超级节点从子节点列表中查询剩余在线时间t最长的节点作为继任超级节点。

（2）原超级节点对继任超级节点进行任命通知，并将现有在线子节点列表和身份密钥信息移交给继任超级节点。

（3）继任超级节点根据子网节点列表和身份密钥信息向所有子网节点通知超级节点已经移交。

（4）子网节点更新超级节点信息，并重新与新任超级节点商定身份密钥。

（5）原超级节点降级为普通子节点，等待失效。

开销比较：

与普通P2P网络超级节点失效后进行重新选举相比，SPAA算法只增加了一次换届信息广播和密钥更新，只需要建立n次连接（n为子网节点数）。同时省去了重新选举的网络开销，具体开销视选举算法而定，至少为2n～3n。另外省去了为重新收集索引信息而分散连接子节点的开销，改为新旧超级节点间一次性数据拷贝，具体开销视子节点所含资源量而定。

3.2 节点存活率计算

节点存活率的计算可以以相对开机的关机时间或绝对的关机时刻为时间单位，根据上一章中描述的场景，用时刻更能反映个人电脑的工作规律。节点的开关机时刻数据可通过在各节点中加入服务程序或守护进程，定时记录在线时间。在系统再次启动时就能通过读取开机记录，自行统计到主机的失效数据，并计算出下线概率。

根据统计学原理，节点在一次检测到的关机时刻周围关机的概率满足正态分布：

其中μ为服从正态分布的均值，应用中指检测到的单次关机时刻。σ为标准差，反映数值分布的集中率，σ越小，分布越集中在μ附近，σ越大，分布越分散。

存活率的计算遵循统计规律，统计结果是否精确取决于样本的数量和质量两个因素。样本数量通过测量多个周期的节点上下线情况来确保，算法运行周期越多越精确。样本的质量指的样本方差或标准差，即计算每个周期中关机曲线的变化差异情况。在公式（2）中标准差σ就反映了节点使用者的作息规律性。通过比较一个节点多个周期的关机曲线的变化差异情况，可以计算出节点的方差和标准差。节点上下线时间越规律，则σ越小。如果σ过大说明该节点用户作息时间极不规律，不适合作为候补超级节点。σ过大会导致关机概率曲线变缓，影响阈值的选取，在小范围内变化则不影响算法的正确性。由于实验条件所限，无法对真实用户样本方差做大范围全面统计，但根据简单的抽样结果，有30%的普通用户主机的作息规律能够满足统计质量要求。限于篇幅限制和仿真方法的局限，本文没有对样本方差和标准差的计算仿真作深入讨论，仅假设参与仿真的节点都有一致的规律性。为简化计算，可以将满足规律性的节点的σ值设为1。

设已知μ时刻节点产生失效事件，某个时刻的关机率为万分之p，则公式（3）可以计算出此次失效事件发生后x时刻的失效率：

公式（3）为连续数值的表达式，而实际应用中时刻和计算机的存储数据都是离散数值，因此为便于计算，将公式转为离散型表达式。 p(x，μ)的计算以时间刻度为单位，由经验可知，当将一天24 h分成72份，即以每20 min为单位检测一次节点失效情况时，曲线在前后20 min内的变化最陡峭，比较符合实际中人们的使用情况。则μ的取值范围为（0，71）。当|x-μ|大于4后，正态分布值小于万分之一，概率影响可以忽略不计。因此认为μ时刻节点产生的失效事件，只会对(μ-4，μ+4)范围内时刻的概率产生影响，只需要重新计算前后4个点的概率值。

公式（4）将积分表达式 p(x，μ)转换为近似的离散型求和表达式 pd(x，μ)：

在时间刻度单位选定后，μ和x都是有限的离散值，如按当前取值范围，pd(x，μ)有72×9个。使用时可以在每个节点以μ和x为坐标保存一张二维表，在每次初始化启动时通过查表计算出 pdnew(x，μ)，不需要重复进行公式计算。

设每个时刻节点的最终存活率为PS，初始情况下令每个时刻的值PS(x)=10 000。发生一次失效事件后导致该事件时刻周围9个时刻的存活率发生变化。计算得新失效率为 pdnew(x，μ)，则新存活率曲线为：

其中λ为新计算的存活率占总存活率的权值。λ越大，新事件对总存活率的影响越大，反之则存活率曲线变化更平缓。

4 实验仿真

4.1节的实验通过实际统计主机的开关机情况，为算法提供数据支持。4.2节通过将常用的选举算法和搭载了SPAA算法的网络的失效开销做对比仿真实验，说明了算法的作用。

4.1 在线概率统计

首先验证测试节点存活率PSnew的计算准确性。实验通过后台服务，记录了一台主机两周的离线情况，再根据第3章的算法得到主机的在线时间概率统分布计图。图4中横坐标为每天开机时刻，以20 min为单位，纵坐标表示每个时刻的存活概率，以万分之一为单位。

图4 主机在线时间概率统计图

由图4可知，该主机在每天17：00和24：00附近关机可能性较大，并且近期的关机时间集中在24：00点。

4.2 流量统计

由于本算法工作在超级节点后期，作用是降低由超级节点失效导致的控制流量开销，因此无法与各类选举算法做直接比较，需要与选举算法配合工作。若SPAA算法对超级节点的关机时间预测失败，则整个网络退化为重新选举状态。仿真通过5台主机和虚拟机建立的一个chord网络，用网络抓包工具了记录网络中接入和断开的情况，并将超级节点设在虚拟机中。通过关闭虚拟机网络模拟超级节点失效，并将多次抓包记录导入到matlab程序中作为连接数基础值。用matlab程序根据需要仿真的失效次数或节点数，随机选择一次数据作为某次节点失效连接次数的累积值，计算对应使用禅让方式的连接次数，然后绘制出坐标图。

选举算法中通信复杂度和时间复杂度通常是互为矛盾的，为减少选举时间通常要以增加连接数为代价。表1中给出几种选举算法做比较[15]，通信复杂度反映了选举算法在流量上的占用量，时间复杂度则反映一次选举所需要通信转发的时间计数。其中n为网络中节点个数，m为节点组成的联通图中无向边的条数，d为无向图的网络直径。通过比较可以看出各种算法在时间复杂度和通信复杂度上是一种此消彼长的关系，使用单一的选举算法无法同时在时间上和空间上对超级节点网络进行优化。

表1 选举算法性能比较

由选举算法性能比较可知，就通信复杂度而言环选举算法是开销最低的，因此用环选举算法与SPAA搭配环选举算法做对比实验更能表现SPAA算法的作用。一次环选举算法超级节点节点失效的开销为2n～3n-1，加上重新收集节点索引开销为n，则总开销为3n～4n-1。SPAA算法开始会预测失败，经过两个周期的失效信息记录后就能进行失效概率的计算，但需要5～7次周期后节点的失效曲线才不会出现大幅波动。预测失败时算法退化为重新环选举算法。预测成功则只需要向网络广播一次更换超级节点消息，所需开销为n。

实验时为提高速度，将节点影响周期单位缩小为标准的万分之一，即每1.2 s为一个时刻，约1.5 min为一周期。参数n为一次仿真中P2P子网的节点总数，参数t为一次仿真时超级节点的失效次数，参数y为统计在网络中超级节点失效到新超级节点产生所需要的网络连接总次数。

图5反映了在拥有相同节点的P2P网络中，在两种算法下超级节点失效次数与网络开销的关系。其中O形线条代表在未加入SPAA算法前节点环选举失效次数和网络失效开销的关系，+号线代表加入SPAA算法后二者的增长关系。

图5 超级节点失效次数与网络失效开销关系图

由图5可见，随着网络超级节点失效次数增大，采用SPAA算法的网络所花费的开销约等于重新选举开销的1/3，与理论推导结论相符。

图6反映了在相同超级节点失效次数下，两种算法下网络节点规模与网络开销的关系。其中O形线段表示了在未加入SPAA算法前网络中节点数量增加与网络失效开销的比例关系，+号线段代表加入SPAA算法后二者的比例关系。

图6 网络节点规模网络失效开销关系图

由图6可见，随着网络节点数增加，采用禅让机制的网络所花费的开销约等于重新选举开销的1/3，与理论推导结论相符。

5 结束语

本文针对P2P应用中超级节点失效时带来网络波动问题，提出了一种基于用户行为统计规律的超级节点禅让机制。在该机制中，首先通过统计节点的历史失效情况，计算出在线概率分布曲线。再选取在线可能性最长的节点作为超级节点。当超级节点在线概率低于阈值时，通过禅让机制选取网络中在线率最长的节点作为新超级节点。从而避免再次选举带来的网络开销。仿真实验和结果表明，在节点作息时间规则的情况下，采用禅让机制能够有效减小由超级节点失效带来的网络开销。

由于研究精力和实验条件有限，本文提出的方法存在一些不足。SPAA算法较适用于由个人用户组成的P2P网络（如电驴的kad网络），目前的方法是统计节点开机、关机的规律，对用户的作息规律有很大依赖，应用上存在一定的局限性。节点间由于减少了控制流量通信，可能导致较大的信息不同步。这些问题有待进一步研究。

[1]谭义红，罗立，林亚平，等.超级节点网络的构建与搜索机制研究[J].小型微型计算机系统，2008，29（11）：1-4.

[2]张国强，唐明董，程苏琦，等.P2P流量优化[J].中国科学：信息科学，2012，42（1）：1-5.

[3]Luis G E，Keith W R，Guillaume U K，et al.Hierarchical peer-to-peerlook-up services[C]//Proc ofIEEE Infocom，2003：1-3.

[4]陈水平，吴开贵.P2P网络基于CPU动态处理能力的超级节点选取[J].计算机工程与应用，2011，47（19）：1-2.

[5]相有桓，熊焰，苗付友.移动P2P网络中超级节点的选择[J].计算机工程，2010，36（10）：1-5.

[6]杨寿保，许通，胡云.用户需求适应的P2P超级节点选取机制[J].电子科技大学学报，2009，38（3）：1-4.

[7]刘玉枚，杨寿保，陈万明，等.P2P系统中基于信誉感知的超级节点选择算法研究[J].中国科学院研究生院学报，2008，25（2）：1-6.

[8]余兆.基于ISP主动参与的P2P下载流量优化研究[D].武汉：湖北工业大学，2011：3-7.

[9]梁卓明，黄伟强，郑凯.P2P流量本地优化综合机制[J].计算机系统应用，2012，21（1）：1-5.

[10]Tomozei D C，Massoulie L.Flow control for cost-efficient peer-to-peer streaming[C]//Proc of IEEE Infocom，2010：1-6.

[11]柴勇，刘一松，曹阳.基于分层P2P系统的失效恢复机制的改进[J].微计算机信息，2006，30（22）：1-5.

[12]李瑾，周竹荣.基于用户行为和社区发现的P2P资源检索方法[J].计算机工程与应用，2012，48（21）：1-2.

[13]Fernandez A，Jimenez E，Raynal M.Eventual leader election with weak assumptions on initial knowledge，communication reliability，and synchrony[C]//Proceedings of Dependable Systems and Networks，2006：165-179.

[14]廖小伟，王敏，王晓国.一种基于超级节点的半分布式P2P系统改进策略[J].计算机应用与软件，2007，11（24）：1-2.

[15]杜丽娟，余镇危.分布式超级节点选举算法[J].计算机工程与应用，2011，47（14）：1-5.

基于行为特征的超级节点节流算法研究

何 钦，刘 丹，周 明

HE Qin,LIU Dan,ZHOU Ming

Research Institute of Electronic Science and Technology,University of Electronic Science and Technology of China,Chengdu 611731,China

In a super-peers-based P2P network,if super-peers fail or leave,it may bring many problems,such as resource losing, network topology changing and increasing bandwidth occupancy for re-election.To solve these problem,this paper brings up a super-peers abdicate algorithm based on user’s behavior characteristic.According to statistic characteristic of the node failure, the SPAA algorithm can forecast the node leave time and appoint next super-peer.Simulation and analysis show that the SPAA algorithm can effectively reduce the net churn by super-peer failure and reduce network traffic.

super-peer;node failure;abdicate algorithm;reduce network traff

针对P2P网络中超级节点失效时带来的资源流失、网络拓扑结构变化和重新选举网络开销增加等问题，提出了一种基于用户行为特征统计的超级节点禅让算法。根据节点的失效统计特征预估失效时间，预先指定继任超级节点。仿真实验对比结果表明，该算法可以有效降低超级节点失效时带来的网络波动，降低网络流量消耗。

超级节点；节点失效；退位算法；降低网络流量

A

TP393.0

10.3778/j.issn.1002-8331.1211-0245

HE Qin,LIU Dan,ZHOU Ming.Research on algorithm for low bandwidth super-peers network based on user’s behavior characteristic.Computer Engineering and Applications,2013,49（11）：61-65.

宁波市科技局工业、农业与民生领域重大科技攻关项目（No.2011C51007）。

何钦（1987—），男，硕士研究生，主要研究方向为计算机网络安全及开发；刘丹（1969—），男，博士，副教授，主要研究方向为计算机网络安全和物联网开发；周明（1976—），男，研究员。E-mail：hunterheqin@163.com

2012-11-21

2013-01-23

1002-8331（2013）11-0061-05