P2P网络通信树群发算法研究

王 欣

(安徽绿海商务职业学院 继续教育学院，安徽 合肥 230601)

近年来，点对点(Peer-to-Peer，简称P2P)技术以“将网络归还给使用网络的用户本身”为中心思想，成为了计算机网络研究领域的热点。用技术眼光来看，P2P并非是近期才出现的新技术，它仅仅体现了分布式计算在互联网中的应用而已，而采用网络终端越来越强的处理能力弥补和解决传统C/S模式的性能“瓶颈”问题日益成为P2P技术的关键［1］。

P2P技术一经推出，就立刻受到网络产品应用企业的追捧，随着P2P技术在各个领域的广泛应用，P2P通信算法日益成为影响P2P发展的一个重要因素［2］。本文正是基于P2P网络的应用，提出了一种新型的群发算法——困难节点优先群发算法，通过确认并优先考虑群发通信中的“困难节点”，提升整个P2P网络群发通信的速度，对P2P网络群发拓扑结构进行了优化。

1 P2P并发机制

一般来说，在计算机网络中，各个通信节点在通信过程中会受到多方面的影响(包括节点的分布和通信环境等)，从而导致了参与通信的各个节点之间通信权值各不相同［3］。因此，合理布局通信节点在群发拓扑结构中的位置，在最短的时间内完成全部节点的通信任务是几乎全部群发算法的核心思想。

虽然目前P2P还没有被广泛接受的定义，但具有以下明显的特征:P2P系统是自组织的、非集中式的;各节点是自治的、对等的、动态的;节点之间的交互是直接的［4］。由于P2P是一种在应用层重构覆盖网的软件技术，因此，本文所研究的群发拓扑结构是将现实网络中的节点抽象成逻辑意义上的结构进行P2P通信的。

在P2P网络中，任何拥有自己唯一网络地址的设备都是网络节点，每个节点都具有通信能力，且节点之间的通信互不干扰，在申请服务时是客户身份，而在提供服务时又转变为服务身份，这一机制使得节点在整个通信过程中能够并发的传输数据，大大提高了通信效率。P2P并发机制如下图1所示:

图1 P2P 并发机制示意图

其中，V1、V2、V3、V4、V5、V6、V7、V8 代表 P2P 网络中的节点，方框内的数字表示相连两节点进行通信的时间段。示意图表示的含义是:由V1节点向其他节点群发消息，在第一时间段，只有V2节点收到消息，在第二时间段V1节点和V2节点同时向V3节点和V4节点发送消息，以此类推，直到P2P网络中所有节点都收到消息为止。

2 困难节点优先的群发算法

2.1 通信树及通信规则

目前，网络拓扑结构有线形、星形、环形、树形、网状结构等等，由于P2P系统一般构造的是一个非集中式的层次型网络拓扑结构，因此，通信节点在P2P通信中的地址、通信环境造成的通信权值范围，以及通信结构的层次划分都是P2P通信算法的研究范畴，可以说通信算法直接影响通信形态，进而对通信时间也造成了深远的影响。本文采用树形结构对物理网络中的节点进行抽象，用“困难节点”优先的群发算法构造了一种新的群发通信树。为了研究方便，在构建通信树之前有如下两个假定:

假定一:P2P网络中每对节点之间的通信时间为aij，其中i和j为参与通信的节点编号wij，的值可以通过测试进行估算。

假定二:网络中任意两节点之间都是可以到达的，两节点之间传送数据和接收数据的通信时间相同，是一个无向完全网络。

本文沿用了通信树产生通信行为的相关规则［4］:

(1)在同一时间段内，参与通信的一个节点只能与另外一个节点进行通信，也就是说，在P2P网络的一个时间单元内不允许一对多的通信行为;

(2)在一个P2P的通信树中，能够互相通信的节点之间是父节点和该父节点的子节点;

(3)每一次通信，从一个节点掌握数据(称为通信源节点)，到所有网络中节点都收到数据的过程中，任意通信环节都发送相同的数据。将通信源节点都命名为节点V1，V1就是通信树的根节点。

(4)构建通信树采用自左向右的方式，在前一时间段，每个非叶子节点先和它的左孩子进行通信，在下一时间段，再和它的右孩子进行通信，依次类推，直到全部节点均接收到数据。

一般地，使用通信时间来衡量通信算法性能的优劣性，通信时间包括累计通信时间和并发通信时间，其中，并发通信时间是指在有N个节点的通信树中，从根节点开始通信到树中所有节点都收到数据所用的时间。本文就是以并发通信时间作为衡量依据，判断构建通信树算法的优劣。

2.2 构造连通子图

根据3.1节中的假定，通信源节点V1到其它节点都有通路，并且所有节点之间的通信代价已知，即可以得到一个通信权值矩阵，因此一个含有有限节点个数的P2P网络就可以等价于一个完全图G(V，E)，在这个完全图中，任意Vi与Vj之间的通信代价构成了与完全图对应的权值矩阵。由于矩阵是对称的，只需要为每个节点在上三角矩阵按照权值大小排序编号，就会得到一组集合M={Mij}和集合E={Eij}，其中，Mij是在第i行，按矩阵元素从大到小排序得到的所有元素的行下标i和列下标j，而Eij是在第i行，按矩阵元素从大到小排序得到的矩阵元素的值。

为了从权值矩阵中挑选出最小的权值序列，将M={Mij}中列下标等于1的元素分为一组，以9个节点组成的P2P网络为例，M1就是权值矩阵中的最小权值表，记作 M1={M11，M21，M31，M41，M51，M61，M71，M81，M91}，同理，M2是权值矩阵的次小权值表，M3是权值矩阵的第二次小权值表。

根据并发通信时间的要求，需要挑选比较小的权值来构造生成子图，而且要求这个生成子图是连通子图，并在该图中寻找V1到“困难节点”的最短路径。也就是说，当最小权值表M1构成的生成子图不是连通子图时，算法会自动将次小权值表M2中的元素加入图中，如果仍然不能构成连通子图，则依次加入第二次小权值表M3等，直到生成的子图连通为止。

在这里构造最小连通子图的目的是从开始构建通信树时，就在连通生成子图M中对源节点到“困难节点”之间的路径进行优先选择操作，令通信源节点首先针对“困难节点”的困难特性进行通信树的构造，这就排除了权值较大节点对构造通信树的干扰。

2.3 “困难节点”和最短路径约束

所谓“困难节点”是指存在这样一种节点，它与其它节点通信的代价都很大，它的最小通信权值也比其它节点的最小通信权值大，因此就可以说该节点是P2P网络通信中的“困难节点”。

当连通的生成子图构造成功后，接下来要解决的就是如何确定“困难节点”和寻找源节点到“困难节点”之间最短路径的问题。本文为寻找困难节点制定了如下两个约束条件，记为约束条件Q:

(1)找到“困难节点”的元素所在行，该行元素中的最小值仍然比其余行元素中的最小值大;

(2)“困难节点”所在行元素的最小值所对应的节点Vi和Vj不能是通信源节点V1，即Vi≠V1且Vj≠V1;

在上一节构造的最小连通子图中搜索V1到“困难节点”之间的最短路径时，除了一个“困难节点”和一条最短路径之外，还有以下两种情况，记为条件P:

如果存在多条最短路径，也就是如果路径上的累加权值相同，那就优先选择节点数多的路径为最优最短路;假设有多个节点都符合“困难节点”约束条件Q时，则把这些“困难节点”作候选节点，同时搜索源节点V1到这些“困难节点”的多个最短路径，再从结果中选择最优最短路径。

2.4 困难节点优先算法构造通信树

“困难节点”优先算法构造通信树的过程如下:

第一步:令 VT={v1|v1∈V}，ET=Ø，分组后的行列下标集合记作:M1，M2，…，Mn;

第二步:判断最小权值表M1能否构成一个连通子图，如果不能连通，则加入次小权值表M2，直到构成一个由最小权值组成的连通子图G为止，G=(V，E，W)，V代表节点，E代表边，W代表边上的权值;

第三步:若节点集合V中存在一个或多个满足条件Q的节点vi，标记为“困难节点”;

第四步:设L为通信源节点v1到vi的最短路径长度，记作:

用条件P挑选出一个最优最短路径l，路径l包括节点集 Vleft和边集 Eleft，记作 l=(Vleft，，Eleft)使 VT⇐VT∪Vleft，ET⇐ET∪Eleft，从根节点 v1开始优先构造直达“困难节点”的通信树分支，该分支即是整个通信树的最左边支路，而这条支路所花费的通信时间f(t)也正是v1到vi的最短路径长度L。

第五步:当VT=V时，则并发通信树构造完毕，并发通信时间为f(t)。当≠Φ时，则继续向该通信树添加节点。

第六步:仍然用最小权值表M1从小到大进行添加，直到=Φ为止，结束构造。

“困难节点”优先算法构造通信树流程图如下图2所示:

图2 困难节点优先算法构造通信树流程图

3 结论

本文给出了一种新型的通信树构造算法，结合P2P并发机制，在限定通信规则的基础上，提出了实现该算法的三大关键思路，即构造连通子图、确定“困难节点”和寻找最优最短路径，该算法对网络中的“困难节点”优先进行考虑，在尽可能减少“困难节点”对整个通信树并发通信时间所产生的影响的同时，兼顾其它支路通信时间最小，有效的保证了整个通信树的通信负载均衡。根据模拟结果显示，该算法的并发通信时间比其他算法有明显的提高。

［1］鲁强，陈明.基于分类节点的P2P语义路由模型［J］.计算机应用，2008，28(1):29 －32.

［2］张一鸣，卢锡城，郑倩冰，等.一种面向大规模P2P系统的快速搜索算法［J］.软件学报，2008，19(6):1473－1480.

［3］刘山，赵恒，刘轩.多播路由kpp算法的改进［J］.计算机工程与应用，2007，43(16):118 －120.

［4］Karrels D R，Peterson G L，Mullins B E.Structured P2P technologies for distributed command and control［J］.Peer－to－ Peer Networking and Applications，2009，2(4):311－333.