《聚集系数在对等网路由搜索算法中的应用》由会员分享，可在线阅读，更多相关《聚集系数在对等网路由搜索算法中的应用（8页珍藏版）》请在金锄头文库上搜索。
1、 聚集系数在对等网路由搜索算法中的应用 摘要：针对对等网搜索技术结构化拓扑中不支持复杂查询以及非结构化拓扑中搜索的可扩展性差等问题，本文提出一种新的搜索算法，将现有的对等网拓扑结构进行改良，让结点以flood方式与DHT方式结合起来进行信息搜索。该算法以域为基础，域内根据聚集度来提高对普通结点进行搜索的命中率，域间使用Chord协议来完成搜索。通过这样的结合提高搜索的效率以及响应的速度。实验结果验证了搜索算法的有效性。为进一步的研究提供了有力的理论分析基础。关键字：聚集系数、对等网络、路由算法、搜索策略TN393：A：1673-1131(2010)05-030-02一、引言网格计算和对等网计算
2、是网络计算领域中最重要的研究方向虽然两者面向的应用领域不同，但在技术上却有大量相通的地方。特别是对等计算领域中获得的大量研究成果已经被广泛应用于网格系统的设计和实现中，用于解决资源发现和系统可扩展性等问题，取得显著成效。对等网络通常简称为P2P (Peer to Peer)。对等网络作为最近几年的一种热门网络技术，在很多方面有重要应用。如NapsterGnutella. eDonkey. BitTorrent等P2P软件提供文件和其它内容共享：SETlhome. Avaki. Popular Power等可挖掘P2P对等计算能力和存储共享能力：JXTA、Magi. Groove.NET My
3、Service等软件可提供基于P2P方式的协同处理与服务共享平台；而QQ. Yahoo Messenger. Skype等是在P2P对等网络基础上开发的即时通讯软件。随着P2P应用规模的日益增大P2P系统产生的网络流量已经超过http访问产生的网络流量，成为占据Internet带宽的首要应用。在P2P模式中，节点均离散地分布在物理网络的不同地方P2P系统通过在应用层建立的网络(即覆盖网Overlay Network)将这些节点连接起来。每个节点各自存储与覆盖网中部分节点之间的路由信息，通过节点间的合作转发实现覆盖网中的消息路由，并以此为基础，为丰富多样的网络应用提供支持。如何在庞大的分布式网络
4、中高效地查询并有效地定位资源是P2P技术的关键与研究的热点。由于对等网络系统的可扩展性和网络节点的不确定性，设计一个良好的搜索机制比较困难。研究结果表明，基于对等网络技术的应用软件在选择通信路由时具有非常大的灵活性，它们必须克服Internet的不稳定性、多变性，并且根据网络性能，智能地选择相应的路由来通信。因此，对有效的搜索机制进行研究必然在对等网络研究领域产生巨大的推动力。二，基于拓扑结构的路由查找算法对等网络领域一个很重要的研究就是对路由查找算法的研究。对等网络搜索技术从结构角度出发又可以分为四类：集中式对等网络的搜索技术，结构化对等网络的搜索技术，非结构化对等网络的搜索技术，混合式对等
5、网络的搜索技术。结构化对等网络搜索算法是一种采用纯分布式的消息传递机制和根据关键字进行查找的定位服务模型，结构化搜索方法与其覆盖网络拓扑结构、路由表结构密切相关虽然结构化搜索策略看上去方法众多，各有所长，但本质都是采用分布式、局部性的贪心路由算法，逐步缩小当前节点与目标节点之间的ID差异。所谓非结构化就是节点之间没有任何的组织规则，完全随机的散布在网络中。非结构化对等网络路由搜索算法是建立在无结构对等网络拓扑结构的基础上，在重叠网络(Overlay Network)上建立随机图的方式这些系统对结点的加入和退出没有强硬的结构限制甚至大部分系统并没有限定的结构。非结构化对等网络路由搜索算法主要分为
6、盲目搜索算法(BlindSearch Algorithms)和启发式搜索算法(Informed SearchAlgorithms)两类。另外，我们还可根据所构造网络的拓扑结构，有效地利用其中有用的统计特征，进行高效的路由。三、具有小世界特性的路由查找算法 我们将非结构化和结构化P2P网络结合起来构建一个包含两层节点的网络。在这种路由算法中，包含两层的结构，中心层的拓扑结构是结构化的网络，我们用CHORD算法来构建拓扑结构，外围层的拓扑结构是非结构化的网络。在外围层中，结点首先组织在一个小型的非结构化网络里，结点之间的消息是在小世界模型的基础上使用最大度搜索的启发式的洪泛算法来传递的。我们将这个
7、小型的非结构化网络称为域。然后让域组成一个结构化的网络。每个域在中心层拓扑结构里可以看成一个结点。这个系统的结构图如图1所示。外围层的拓扑结构是非结构化的，它具有高聚集度而低特征路径长的特征，符合小世界网络特性。其中，聚集系数(clustering coefficient)也称为小集团系数，或聚集度。一般的，假设网络中的一个节点i有K条边将它和其他节点相连，这K个节点就称为节点i的邻居。这K个节点之间的实际存在的边E的总和与这K个节点之间总的可能的边数K(K -l)/之比就定义为节点i的聚类系数。即：G=2%(K1)平均路径长度03“51是指任意两节点间最短路径的边数的平均值。平均路径长度是网
8、络的全局特征。己知一个有n个结点的无向图G，任意两节点u.v间最短路径上的边数为Duv，则其特征路径长根据节点的聚集度将节点划分为一个个的Clusters域。按照对等网络节点的存储能力、运算能力、带宽能力和稳定性等功能将节点分为两类：一是普通节点，令普通结点为聚集度为Co的节点，其中Co的值大于某一规定阀值。我们把普通结点作为外围层的域的构成节点，具有本域内的资源定位能力。当域中没有所要查找的资源时，需要超级节点的帮助：二是超级节点，这种结点聚集度为本域中的聚集度的平均期望值。这种结点不仅参与本域的资源定位和共享，并且帮助域内的其他节点完成域外的资源查找操作。另外，所有超级节点之间互相协作，构
9、成中心层。如图l，在域l中，用户l发出查询请求，在域1内的所有普通节点中先找到离自己最近且聚集度最高的节点，聚集度最高的节点收到请求后，如果发现发现索引记录列表有所找的关键值，则将查询结果返回给用户l。如果没有，则用户l的普通结点找到离自己最近，且聚集度次高的结点。如果域中没有找到，则将请求发给超级节点。超级节点l收到请求后，如果发现索引记录列表有所找的关键值，则将查询结果返回给用户1用户l根据返回的结果下载资源。如果域l内的超级节点l收到请求后，发现自己的索引记录列表和查询缓冲区内并没有所找的关键值，则超级节点l在主干网中发送资源查询请求。请求经过主干网的Chordil略由，到达了目标域2中
10、的超级节点2超级节点2查询自己的索引记录列表，发现有匹配的索引记录在用户2发送应答消息给域的超级节点l。超级节点l将结果返回给查询节点用户l。用户1根据返回的结果链接资源所在的用户2，下载资源。如果所有域都没有查询到所需资源，则没有此资源，查询失败。四、实验结果及分析仿真实验在一台PC机上进行，软硬件环境如下：CPU为Intel Pentium l.8GHz微处理器，内存512MB运行Windows 2000 Professional操作系统。为了对upload/download系统的性能进行评估，我们把实验分为两部分：网络模拟和实际环境测试。我们选用PEERSIM来对基于聚集系数的网络(CC
11、N)进行模拟。试验参数如下：结点规模最小210，最大218，群内TTL为5域内泛洪转发邻居数为5域个数与域内结点个数为1/10。每次试验重复20次，实验结果为平均值。图2显示了CCN与其他两种网络的平均查询跳数对比。我们从图中可以看出，两者的信息查询跳数很接近，这说明我们的系统具有较小的查询延迟。当结点超过215时，我们所设计的系统的平均跳数小于Chord。这是因为我们的外围域内固定TTL的限制，使得我们的跳数增长速度下降，同时查询效率也是在下降的。五、结论本文主要通过研究现有Chord的构造特点，在其节点构造路由以及路由查找的过程中加入对结点聚集度的考虑，以获得更好的路由性能。本文首先总结对
12、比了结构化P2P网络拓扑结构与非结构化网络拓扑结构算法的优缺点，然后提出一个建立在新的P2P的网络结构上路由搜索策略。我们设计的算法结合了泛洪和DHT两种方法，利用将结点按聚集度的方式组织成非结构化的域来加入DHT网络的方式，提高了DHT面对动荡网络时的稳定性，将DHT引入到了实用的地步。最后，我们给出了有关仿真实验的结果。经过实验分析，我们的路由策略是一个可扩展、查询效率高、稳定性好的算法。参考文献1D ej an.Miloj ieie,Vana Kalogerki,R aj anLukose,KiranNagarajal,JimPruyne,Bruno Richehard,SamiRoll
13、insZ,Z hichenXu Jj .http:/w w.h Pl.h P.eoln/teehrePOrts/2002/H PL-2002-57RI.Pdf2陈贵海，须成忠，沈海英一种新的常数度数的P2P覆盖网络计算机学报，2007,10(01):1084-1095.3D.J. Watts, S.H. Strogatz, Collective dynamics of´small-world´ networks, Nature 393 (1998) 440-442.4庄雷，潘春建，郭永强.Gnutella网络的连接管理，软件学报，2005,16(1):158-1645lX. Li, and X.Wang, Controlling the Spreading inSmall-World Evolving Networks: Stability, Oscillation, andTopology, IEEE Trans. Automatic Control, Vol. 51, No.3,pp. 534-540, 2006.6徐非，杨广文，鞠大鹏基于Peer-to-Peer的分布式存储系统的设计软件学报，2004,15(2):268-277 -全文完-
