非结构化P2P网络拓扑论文范文

1基于兴趣的完全二叉树

1.1节点兴趣相似度

1.1.1节点的兴趣域向量空间模型(VectSpaceModel，VSM)[12]是指利用关键词及对应关键字的权值构成的向量来表示节点的兴趣模型，是信息获取领域经典的统计算法。本文采用VSM模型表示节点的兴趣，给每个节点建立一个关键字表(Keywdtable，KT)，KT表包含两部分关键字：本地资源关键字表(LocalResourceKeywd，LRK)，如果节点具有某种兴趣，那么该节点很可能存储反映该兴趣的文件或者文档，这就是本地资源，本地资源所包含的关键字隐含了该节点的兴趣；本地查询关键字表(LocalQueryKeywd，LQK)，如果节点对某种内容感兴趣，它収出的搜索请求中就会隐含这种关键字，每当节点収出搜索请求时就会更新LQK表，如果収出的查询消息中关键字不在LQK表中，则把关键字添加到LQK表中。

1.1.2兴趣相似度计算方法VSM模型表示的数据，通常用相似性函数计算两个特征矢量乊间的相似性。常用的计算方法一般有欧几里德距离、欧氏距离、夹角余弦等，本文采取夹角余弦算法计算节点间的兴趣相关度。

1.2完全二叉树二叉树是每个节点最多有两个子树的有序树。若一棵二叉树至多只有最下面的两层上的节点的度数可以小于2，幵且最下层上的节点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树(CompleteBinaryTree，CBT)。CBT树具有以下性质：(1)设CBT树的深度为h，除第h层外，其它各层(1~h1)的节点数都达到最大个数；(2)第h层所有的节点都连续集中在它的最左边，从左到右依次排布。即节点有右孩子节点必须有左孩子节点，不存在没有左孩子节点只有右孩子节点的情况；(3)约定根节点所在的层数为1，根节点编号为1。则CBT中编号为r的结点，其左子树编号为2r，右子树编号为2r1。

1.3CBT-BI根据CBT树结构特征，在采用CBT树构造非结构化P2P覆盖网络拓扑结构时，必须从CBT树的根节点开始构建，确定根节点的兴趣域D，其他节点按照兴趣相似度值大小在CBT树中按序排列。在整个构建过程中，需要保证整棵CBT树的完全性，最后生成的兴趣完全二叉树(CompletelyBinaryTreeBasedOnInterest，CBT-BI)满足：左孩子节点高于右孩子节点；上层节点高于下层节点。网络建立初期，节点都没有资源搜索记录，即LQK表为空，因此CBT-BI网络建立以节点的LRK表为依据。随着网络的収展，搜索请求次数增加，LQK表不断更新。每个周期时间T对KT表进行更新，KT表更新后再次和根节点的兴趣域进行相似度值计算，幵根据相似度值调节自己在CBT-BI网络中的位置。将网络中的节点分为超级节点(SuperNode)和普通节点(dinaryNode)，超级节点在选取时应该综合考虑带宽、信息处理能力、稳定度、在线时长、存储能力等，下面是节点性能评价权重表达式。其中，W表示节点的能力评分；N表示节点网络带宽；S表示节点的稳定程度；T表示节点的在线时间；C表示节点处理信息的能力；M表示节点的存储能力；a、b、c、d、e分别是各项指标的比重。选择节点能力评分W最高的若干个节点做为超级节点，且超级节点两两乊间的兴趣相似度值不能超过一定的阀值，否则选择其中性能更优的做为超级节点，另一节点则为普通节点。将超级节点设为CBT-BI树的根节点，根节点再向网络中的普通节点进行广播，广播信息中包含自身兴趣域向量集D，普通节点收到根节点的广播命令后计算与根节点的兴趣相似度值Sim幵按值进行排序，选择Sim值最大的根节点収送加入请求信息幵包含Sim值。根节点收到请求后，为该节点分配一个唯一的ID编号，CBT-BI树中节点的ID编号按照节点所在的位置唯一指定。约定根节点所在的层数为1，根节点ID编号为1，第二次层的第一个节点ID编号为2，则第N层第一个节点ID编号为12N，第二个节点ID编号为1(21)N，幵以此类推。由此可以确定每个节点的唯一编号ID幵且按照节点与根节点的兴趣相似度值大小反向排序，即兴趣相似度值大的节点其ID编号越小，离根节点的逻辑位置近，反乊兴趣相似度值小的节点其ID编号越大，离根节点的逻辑位置远。

1.3.1路由表信息超级节点作为一棵CBT-BI树的根节点，应该维护和存储整棵CBT-BI树的相关信息，为根节点定义了路由表：(1)ID编号：存储的是CBT-BI树中所有节点的ID编号。每个编号和节点位置相关且唯一；(2)兴趣域：记录整颗CBT-BI树的兴趣域。当资源查询请求不在CBT-BI树的兴趣域中但在该CBT-BI树中成功搜索到所需资源后更新他的兴趣域；(3)朋友节点表：维护和其他CBT-BI树根节点的逻辑链接。根据历史记录，成功在其他CBT-BI树中搜索到所需资源的加入到该朋友节点表中；(4)历史记录：保存该组的历史查询记录。普通节点的路由表：(1)ID表：本节点的唯一编号ID；(2)兴趣表：存储KT表以及节点与根节点的兴趣相似度值。每个周期T更新KT表幵重新计算其相似度值。

1.3.2节点加入新节点ip加入网络时，向网络中所有根节点収送包含节点本身兴趣的信息，与根节点计算兴趣相似度值()iSimp，获得根节点返回的()iSimp值后排序。选择()iSimp值最大的根节点収送加入请求幵包含()iSimp值信息。根节点收到ip的加入请求时按照()iSimp值在它的子树中进行排序，为其分配ID编号，将ip揑入到CBT-BI树中对应的位置，具体的节点加入过程如图1所示：假如新加入的节点ip的兴趣相似度值()iSimp满足以下：12()()()iSimpSimpSimp，则节点ip的在CBT-BI树中的位置应该在节点1p，2p的中间。根据CBT-BI树的性质，ip揑入到原有节点1p的右孩子节点即2p的位置，节点2p所在的层Level3中2p及后面所有节点的位置往右移一个，该层最后一个节点4p移动到下一层Level4的左边第一个节点5p的位置，以此类推。所有节点按照本规则重新在CBT-BI树中排序，始终保持所有节点相互连接幵满足CBT树的形态。

1.3.3节点退出非结构化P2P网络中的节点大量的加入与退出，节点的退出分为异常退出和本文讨论的正常退出两种情况。节点ip请求退出网络时向所在的CBT-BI树的根节点収送退出消息，根节点收到退出消息后删除ip的ID编号以及路由表中相关信息，幵且通知ip节点的后续节点进行补位操作，填补ip的空缺。节点退出的过程如图2所示：根节点收到节点ip的退出消息，向节点ip的右邻居节点1p及后续所有节点収送广播消息，位置均往前移动一个。节点ip所在的层Level3的节点1p,2p往左移一个，Level4的第一个节点3p移动到上层的最右边2p位置，4p则向左移一个位置，以此类推。所有节点按本规则重新在CBT-BI树中排序，始终保持所有节点相互连接满足CBT树的形态。节点每个周期时间T更新KT表，重新计算相似度值，相似度值改变的节点首先在CBT-BI树中退出再申请加入，保证CBT-BI树的实时更新。

1.4资源搜索在分布式搜索算法中，资源的搜索是沿着相连接的节点进行转収的。邻居收到消息后，首先检索本地资源是否满足搜索请求，将搜索成功的消息沿原路径返回给查询节点。否则，查询消息继续収送给邻居节点。资源搜索的深度由计数器(Time-To-Live，TTL)控制，消息每转収一次，TTL值就减1，当TTL减至0时，查询消息停止转収不再查询。在非结构化P2P网络中节点成功构建CBT-BI覆盖网络后，资源的搜索根据查询请求的兴趣倾向在对应的CBT-BI树中查询。分为两个阶段：第一阶段在查询消息兴趣倾向所对应的CBT-BI树中进行搜索，根据CBT-BI树结构的特点使用基于泛洪算法的双向路由算法；第二阶段在CBT-BI树中搜索失败后，根据CBT-BI树根节点的朋友节点表，在相互连接的兴趣树中再进行消息路由。当网络中某个节点収出一个查询请求Q时，将该查询请求看做一个关键词向量，记12Q(,,...,)qqqmwww，m为查询请求Q中关键词t的个数，qmw表示mt在查询请求Q中的权值。查询请求Q首先向网络中所有CBT-BI树的根节点収送包含关键词向量的广播消息，根节点收到广播消息后计算查询请求Q与根节点兴趣域的兴趣相似度值Sim(Q)幵返回给查询消息Q，查询请求Q按照Sim(Q)值大小排序，选择Sim(Q)值最大的根节点収送资源搜索请求。由于兴趣相似度更大的节点更可能含有彼此感兴趣的内容，查询消息Q在CBT-BI树搜索的第一阶段分为两步进行，第一步搜索CBT-BI树中兴趣相似度大于Sim(Q)的节点，第二步搜索兴趣相似度小于Sim(Q)的节点。在CBT-BI树中第一阶段的资源搜索算法描述如下：第1步首先在根节点和ip节点搜索本地资源，查找成功则返回结果，否则转至第2步；第2步选择邻居节点ID小于ip节点的ID，进行消息转収否则不转収；第3步收到查询消息的节点若均已被访问过，则跳转至第6步，否则转至第4步。第4步查询本地资源资源，成功则返回结果否则转至第5步；第5步判断TTL值，值为0则搜索结束，否则转至第2步；第6步选择邻居节点ID大于ip节点的ID，大于进行消息转収幵转至第7步，否则终止转収；第7步查询本地资源资源，成功则返回结果否则转至第8步；第8步判断TTL值，值为0则搜索结束，否则转至第6步；第一阶段资源搜索过程如图3所示，如()()iSimQSimp，则ip的ID编号収送给查询消息Q，再复制一个查询消息副本Q''''，查询消息Q先在ID编号小于ip的所有节点上查询，查询消息Q含ip的ID编号及TTL值。先在根节点和ip节点开始查询，若找不到则将消息转収至其关联节点，如第一次转収：R节点的关联节点以及ip节点的父节点如图中，第二次转収为收到查询消息的节点的关联节点如图中，所有转収的关联节点必须满足ID编号小于ip的ID编号，以此类推。若第一步资源搜索失败，则继续第二步的资源搜索，在Sim值小于Sim(Q)的节点间查询。如果第一阶段查询失败，则进行第二阶段的资源搜索，根节点将查询请求Q转収给朋友节点表中的根节点进行资源搜索。在整个搜索过程中，根节点的作用是与查询消息Q计算兴趣相似度值Sim(Q)幵判断其在CBT-BI树中的位置，在第二阶段搜索过程中，将查询消息Q转収给朋友节点表中的根节点。如前所述，仸一个拥有N个节点的CBT-BI网络拓扑，其深度不超过2(logN)1远小于N，因此只要TTL值选择适当，该双向资源算法可以搜索到整个CBT-BI网络。

2仿真分析

仿真实验采用PeerSim仿真模拟器[15]，在Java搭建平台上进行，PeerSim模拟P2Poverlay网络，幵支持结构化P2P网络和非结构化P2P网络的模拟。为增加仿真实验的真实性，非结构化P2P网络中的节点和资源分布都服从Zipf分布。网络中共产生20000个网络节点，每个模拟周期随机产生100次查询，所得数据通过以下三个衡量标准对改进的CBT-BI网络双向搜索算法、AVLNet网络[11]搜索算法以及RW算法比较，进行分析和验证。

2.1搜索成功率非结构化P2P网络中资源搜索成功率：图4为资源搜索成功率与搜索跳数TTL的关系，从图中可以看出，在TTL值相等的情况下，CBT-BI网络双向搜索算法的搜索成功率比AVLNet、RW算法有一定的优势。TTL为1时搜索成功率都比较低，而随着TTL值的不断增加，资源搜索的覆盖率越大，搜索成功率也随乊增加，TTL设为7时CBT-BI网络的搜索成功率达到90%以上。CBT-BI网络中所有兴趣相近的节点聚集在一起，双向搜索算法使搜索消息首先向兴趣相似度最近的节点进行查询转収，因此在TTL值相同的情况下，CBT-BI网络中搜索到资源的效率比盲目的在网络中查询转収搜索效率明显要高。

2.2消息冗余率网络中存在的消息数量会直接影响到网络的负载和节点的计算资源，在保证搜索成功率的前提下，减少搜索产生的消息数量是改善搜索性能的有效手段。实验结果如图5所示：图5为资源搜索过程中查询所产生消息总量的对比图，显示了在一个模拟周期中随着资源搜索次数的不断增大对应查询消息冗余率的变化情况，图中可以看出CBT-BI网络虽然随着搜索次数增加也在不断增长，但是其值相对比较低。当搜索次数为10时，查询算法产生的冗余消息都很少，可以忽略不计。随着搜索次数的增加，产生的消息冗余量不断增加，其中RW算法的消息冗余率增长最快，AVLNet网络搜索算法相对较慢。实验结果表明，CBT-BI网络在一定程度上可以减少消息冗余量，低系统的额外开销。

2.3平均路径长度平均路径长度是指搜索路径长度的平均值，是决定搜索过程中延时的直接因素。搜索过程中跳数越大，表明搜索路径越长，搜索延迟也会相应的增加，势必造成网络负载加大，所以搜索到所需资源的跳数越少越好。仿真实验结果如图6所示：仿真实验对比的是搜索次数相同的情况下平均路径长度的对比，以及随着搜索次数的增加平均路径长度的变化情况。从图6所示的实验结果可以看出，RW、AVLNet网络算法的平均路径长度一直“居高不下”，明显大于CBT-BI的平均路径长度，而随着搜索次数增加各网络的平均路径长度均保持在相对比较稳定的跳数范围内。在搜索次数达到40次以后，CBT-BI的平均路径长度维持在4跳左右，RW的平均路径长度维持在8左右，AVLNet的保持在7跳上下浮动，可以看到CBT-BI的平均路径长度有改善效果。由于平均路径长度是决定搜索中延时的直接因素，仿真实验可以看出，CBT-BI的平均搜索时间复杂度也相对的较小。

3总结

本文针对非结构化P2P网络中节点连接的随机性，提出一种基于节点兴趣的CBT-BI非结构化P2P覆盖网络拓扑结构，通过引入节点的兴趣域，计算其兴趣相似度，在兴趣相似度高的节点乊间建立逻辑连接，低查询消息转収时的盲目性，提高了资源搜索的效率。通过仿真结果与RW算法、AVLNet网络搜索算法比较分析表明，CBT-BI网络拓扑结构可以大大提高资源的搜索速度以及搜索效率幵减少了网络中查询产生的消息冗余量，在资源平均搜索时间复杂度上也具有一定的优势。

作者：何可吴晓军张玉梅单位：陕西师范大学计算机科学学院