基于leader-follower算法的超级节点研究.doc

基于leader-follower算法的超级节点研究文章编号:1001-9081(2012)01-0143-04 doi:10.3724/sp.j.1087.2012.00143摘 要:基于leader-follower算法的超级节点p2p网中，研究如何处理新进节点与各超级节点语义不匹配问题，有利于提高节点匹配效率和超级节点性能。引入通用类节点和分裂算法，将与各超级节点语义不匹配的新节点交由通用类节点管理，当管理的节点数目达到一定规模后，采用分裂算法将其分裂为若干语义相似簇，最后用合并排序算法从中选择最优节点作为超级节点。实验表明所提方法提高了节点匹配效率和超级节点性能，具有良好的可行性。关键词:超级节点p2p网；超级节点；语义；分裂算法；相似簇；合并排序算法中图分类号: tp301.6 文献标志码:aabstract: analyzing how to deal with new-node that does not match the super-node in super-node p2p network based on leader-follower algorithm can help improve the efficiency and performance of super-node. the paper introduced general class node and splitting algorithm, and the nodes that do not match every super-node were managed by the general class node. when the nodes reached a certain number, the splitting algorithm was used to split these nodes into several semantic similarity clusters. finally, the merge sorting algorithm chose the optimal node as super-node. the experimental results show that the proposed method improves the efficiency and performance of super-node, and it has good feasibility.key words: super-node peer-to-peer (p2p) network; super-node; semantic; splitting algorithm; similarity cluster; merger sorting algorithm0 引言近年来，基于超级节点的对等(peer-to-peer, p2p)网络吸收了集中式对等网络资源搜索效率高和全分布式对等网络鲁棒性强的优点，克服了前者单点失效、负载不均，后者浅搜索深度和分片问题的缺陷，逐步成为人们关注的焦点1-2。基于超级节点对等网络研究的关键问题涉及到超级节点选择、超级节点个数、超级节点管理普通节点等问题。文献3采用在线聚类算法，将新加入的节点按照语义相关性动态加入相应的超级节点，如果没语义匹配的超级节点，则以新加入节点为基础创建一个超级节点。该方法的优点：只对与新到样本最相似的一个聚类中心进行调整，与该样本无关的其他类的性质得到了保留。但在效率和超级节点性能方面存在一定问题。本文对文献3-5的方法进行了改进，引入通用类节点，与各超级节点语义不匹配的新节点则交由通用类节点管理，当通用类节点管理的节点数达到一定规模后，采用分裂算法将其分裂为若干语义相似簇，最后用合并排序算法从中选择最优节点作为超级节点。本文方法提高了节点聚簇效率,增强了超级节点的性能。1 相关知识1.1 在线聚类算法在线聚类法的目的是使系统可自适应地学习新出现的数据。在对等网中，在线聚类法主要用于对新加入的节点进行管理。目前，对等网中使用的主流在线聚类法是leader-follower(领导者追随者聚类)算法，其思想为：对每个新加入的节点，计算其语义相似度，将其连接到与之匹配的超级节点，如果没有语义匹配的超级节点，则以新加入的节点为基础创建一个超级节点3。leader-follower算法的优点：该算法针对在线聚类的特点，只对与新到样本最相似的一个聚类中心进行调整，与该样本无关的其他类的性质得到了保留。实验数据表明，与传统聚类算法相比，该算法达到了可塑性与稳定性的平衡5。1.2 超级节点文献7在基于超级节点的对等网中，选择性能（处理、存储、带宽等方面）较好的节点作为超级节点，由超级节点管理普通节点。在各个超级节点上存储了系统中其他部分节点的信息，整个转发过程只发生在超级节点之间，超级节点之间构成一个高速转发层。整个对等网则是一个超级节点和其负责的普通节点构成的二层次混合模型，一个超级节点管理多个普通节点。混合模型同时吸取了完全分散式模型和层次化模型的优点，构建高效的混合拓扑结构。2 基于leader-follower算法的超级节点管理leader-follower算法用于构造超级节点p2p网络，将新加入的节点按照语义相关性动态加入相应的超级节点，如果新加入节点和超级节点之间的语义相似度超过了所定义的阈值如果新加入节点和超级节点之间这句话不太通顺，请作相应调整。超过阈值（新节点没有语义匹配的超级节点），就以自身构造新的超级节点。该方法存在效率低和超级节点性能差异大的问题。本文提出一种改进的算法，引入通用类节点，将与各超级节点语义不匹配的新节点交由通用类节点管理，当通用类节点管理的节点数达到一定规模后，采用分裂算法将其分裂为若干语义相似簇，最后用合并排序算法从中选择最优节点作为超级节点。2.1 基本概念定义1 节点。在p2p网络中，节点既是服务器又是客户端，既是资源的提供者也是资源的获取者。网络中的资源和服务分散在所有的节点上，信息的传输和服务的实现都直接在节点之间进行9。节点可形式化定义为一个三元组peer=(id,c,ic)，其中：id为节点在系统范围内的唯一标识，c表示节点性能，ic表示节点间的信息量。本文采用基于信息学模型的方法来计算节点之间的信息量(information content, ic)。信息模型的主要思想是：概念ci、cj“cicj”之间是否应该加一个顿号?请明确。之间的相似性通过它们共有的信息表示，它们共同拥有的信息越多，它们之间就越相似。根据文献10计算概念之间信息量的思想，本文用式(1)来计算节点之间的信息量。定义p(v)为节点中某个特征词出现的概率。计算某特征词的总出现次数，形式化描述为：freq(v)=vwords(c)(count(v)（1）其中words(c)为特征词在某节点中出现的次数。特征词的概率计算如下：p(v)=freq(v)/n（2）此处的freq是应该为“freq(v)”?请明确。其中n为所有特征词的数量。本文用两个对象共同拥有的信息量来表示它们之间的相似度。一个节点v的信息量可以进行如下量化：ic(v)=lg p(v)（3）log的底是多少，请补充。因此通过式(4)计算节点的相似度：sim(vi,vj)=max ic(v)=maxlg p(v)（4）定义2 簇。是按照节点对资源的需求、共享目的和属性的相似性进行划分的基本逻辑单位,簇内节点有很大的相似系数。在簇中，选择性能较好（处理、存储、在线时间长，带宽等）的节点来管理其他节点，这个节点叫超级节点(super node, sn)，被超级节点管理的节点叫普通节点(ordinary node, on)。超级节点逻辑上位于簇的中心，与簇内节点距离最短。超级节点作为簇的领导者，可以管理多个普通节点，且为簇中的普通节点提供四种基本的服务：加入、更新、离开、查询。整个p2p网可用一个无向图g来表示，其中p2p网络节点构成图的节点，节点之间的逻辑连接就是图的边。g=(v,e)是一个无向图。其中v=v1,v2,vi此处是否应该为“v=v1,v2,vi”，请明确。是节点集，e=e1,e2,ej此处是否应该为“e=e1,e2,ei”，请明确。另外v与e的下标，均用了“i”，这可能在数目表示上会相同，请对此作相应调整。是节点之间逻辑连接的边集，图g=(v,e)是簇c1,cq的集合。簇内普通节点和超级节点之间通过式（4）计算其语义相似度，建立连接。簇(cluster)可形式化定义为：cluster=clusterid,sni,subsetofordinarynodeset1）clusterid。簇的唯一标识。2）sni。簇中起领导作用的超级节点。3）sunsetofordinarynodeset。和簇中超级节点语义相似的普通节点集。在基于超级节点的对等网中,sni代表超级节点，形式化定义为：supernode=(snid,c,ic)supernodeset=sn1,sn2,snk且满足以下三个条件：1）每一个ci都是节点集(ci,civ)的非空子集，且i=1qci=v;2）任意属于相同簇ci的节点，1iqi，节点和簇ci的领导者超级节点，都是通过式（4）计算，其语义是相似的；3）任意两个属于不同的簇（例如ci和cj）的节点，它们是没有语义相似的节点。定义3 通用类节点。通用类节点(general class node, gn)是一个虚拟节点，其作用是将与各超级节点语义不匹配的新节点vi，交由gn管理。这些节点构成一个集合gn=v1,v2,vi，|gn|=n表示gn中节点的数目。定义一个max值来判断gn中的节点聚簇分裂时间，viv:|gn|max时，gn中节点根据语义相似度开始分裂，然后聚簇。2.2 算法思想文献3采用leader-follower算法创建超级节点：对每个新到来的节点v，计算其语义相似度，如果存在与之匹配的超级节点sn，则将v连接到sn；否则，则以vu此处是否应该为“v”？请明确。构造一个新的超级节点。这种方法的效率较低，并且所选择的超级节点良莠不齐。例如有k个新进节点，假设其语义相似度互不匹配，且不存在超级节点与之匹配，则文献3的方法会生成k个新的超级节点，且不能保证每个超级节点的性能都是最优的。本文对文献3,5的方法进行改进：1）提出了通用类节点gn的概念，gn是一个特殊的超级节点，该节点语义相似度为零，只有管理普通节点的功能。如果新加入节点和超级节点之间语义不匹配，则新节点都交给gn管理。2）当gn管理的节点达到了一定的规模，对gn进行分裂；对gn所管理的普通节点，根据语义相似度进行聚簇；对簇中的节点，采用合并排序算法计算出其超级节点，从而形成一个新簇；对于不能聚簇的普通节点，仍然由通用类节点管理。假设，若新到节点有语义匹配的超级节点，则将新节点加入到该超级节点中；否则加入到通用类节点，交由通用类节点管理。因此，本文方法的总体结构如图1所示。2.2.1 算法改进本文提出一种改进的算法i_lf (improved leader-follower），引入通用类节点gn，如果新加入节点和超级节点之间语义不匹配，则交由通用类节点管理，当通用类节点管理的节点数达到一定规模后，采用分裂算法将其分裂为若干语义相似簇，最后用合并排序算法从中选择最优节点作为超级节点。算法中sni是第i个聚簇中心，表示学习速度，代表阈值。具体算法描述如算法1。算法1 i_lf算法。程序前begin initialize ,snid=1for each sni in supernodeseti=1,found=falsesnixdo 接受新的xifxsnithen snisni+x,found=trueif snid0clusterid=get clusterid from sn id (snid)until 无其他模式if not foundgnx/引入通用类节点else return gnend程序后2.2.2 基于合并排序算法的超级节点为解决文献3中超级节点性能差异大的问题，本文采用合并排序选择算法。以节点的在线时长、计算能力和存储能力三个参数为依据，选择出性能最优的节点作为超级节点。合并排序算法用在初始化的时候选择超级节点和对通用类节点gn中的节点语义聚簇后从新簇中选择超级节点。本文定义表征超级节点sni性能的参数集为sni=ci,si,ti分别表示节点的计算能力、存储能力和在线时间。根据软件系统自动记录的在线时间与上线次数的比值来计算在线时长,计算公式6如式(5)：uptimeave=uptime/time（5）根据文献11，本文用式(6)来衡量超级节点的性能，如式(6)：meritvi=capacity+uptimeave（6）其中：capacity包含节点的计算能力和存储能力，它表示节点对新来的信息进行处理的能力，在所有节点的集合s中，本文根据它们的capacity与uptimeave之和为依据来选择超级节点；和分别为capacity和uptime的权重，并且+=1。权重的信息可以根据侧重点而设定。把所有的merivi进行排序，选择最好的一个作为超级节点。具体算法如算法2所示。算法2 合并排序算法。程序前int arr=meritv1,meritv2,meritvimeritvi=capacity+uptimeaveinput arrmergesort(arr)void mergesort(type a,int left,int right)if(leftmax)/gn中的节点数目超过设定的maxthen initialize ,sim(vi,vj)=max ic(v)=maxlg p(v)/根据语义相似聚簇do 接受sim(vi,vj)if sim(vi,vj)then wiwi+x/x代表和wi语义相似的任意节点，wi表示聚簇中心until 没有语义相似的节点mergesort(wi)/从类的节点中选择超级节点meritvi=capacity+uptimeaveclusterid=get clusterid from sn id (snid)return clusteridend程序后3 实验仿真3.1 实验目的和方法本实验的目的是测试基于i_lf算法的节点聚簇效率。算法使用uci数据集中iris数据集来检验算法的性能。iris是模式识别中一个经典的数据集，记录的是一些植物的特征数据。共有150条数据和3种决策值，这些数据简单记为0，1，3，149。其中049、5099、100149分别对应一种决策。对数据集分别用leader-follower算法和i_lf算法进行聚簇，分析两种算法的聚类结果,比较两种算法选择出来的超级节点的性能和聚簇的数目。3.2 实验内容与仿真3.2.1 聚类结果测试由于leader-follower算法和i_lf算法都涉及到参数，因此参数设置不同，最后得到的聚簇结果也不一样。本文设置了合适的参数，使得两种算法得到的聚簇结果都是3类，而且聚簇效果比较好。下面分别给出两种算法得到的聚簇结果。设阈值分别为0.026,0.037，0.043，在此条件下得到两种算法的聚簇结果。1) leader-follower算法聚簇结果。第1类结果如下(共50个数据项)。1,2,3,4,5,6,147,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,49,122,125。第2类结果如下(共50个数据项)。50,51,52,53,148,128,129,55,56,57,58,59,60,61,108,62,63,64,65,109,66,67,68,69,118,70,71,72,73,145,74,75,76,77,149,78,79,80,81,126,82,83,84,85,127,86,87,88,89,124。第3类结果如下。100,101,102,103,104,105,106,107,90,91,92,93,94,95,96,97,98,99,108,109,110,111,112,113,114,115,116,117,118,119,120,121,128,123,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,146,150。2)i_lf算法的聚簇结果。第1类结果如下(共50个数据项)。1,2,3,4,5,6,147,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,49,122，125。第2类结果如下(共50个数据项)。50,51,52,53,148,128,129,55,56,57,58,59,60,61,108,62,63,64,65,109,66,67,68,69,118,70,71,72,73,145,74,75,76,77,149,78,79,80,81,126,82,83,84,85,127,86,87,88,89,124。第3类结果如下。100,101,102,103,104,105,106,107,90,91,92,93,94,95,96,97,98,99,108,109,110,111,112,113,114,115,116,117,118,119,120,121,128,123,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,146,150。由此可得出，两种算法聚簇结果是一样的，i_lf算法继承了原算法的优点。3.2.2 i_lf算法本文采用计算能力、存储能力和在线时长这三个参数来衡量超级节点的性能，用式（6）计算出各个节点的性能。为了验证实验，本文有如下三元组（节点id，节点性能，节点语义相似度）数据。其中节点的性能和语义相似度分别通过式（6）和式（4）计算得来的数值，如下所示：（1,4,0.64），（2,6,0.53），（3,7,0.63），（4,6,0.50），（5,7,0.63），（6,8,0.66），（7,9,0.92），（8,5,0.89），（9,4,0.67），（10,5,0.74），（11,6,0.42），（12,6,0.41），（13,6,0.44），（14,7,0.40），（15,9,0.44），（16,6,0.43），（17,3,0.31），（18,6,0.21），（19,6,0.95），（20,7,0.93），（21,8,0.90），（22,5,0.86），分析数据，根据相似性判断标准，id=1,3,5,6,9的节点，id=2,4的节点，id=7,19,20,21的节点，id=11,12,13,14,15,16的节点，它们各自语义匹配，因此聚为一簇。id=17，id=18，id=10，id=22语义互不匹配，因此单独是一簇。下面从两方面比较分析leader-follower算法和i_lf算法。1）超级节点性能分析。分析上面节点数据，id为17的节点因为与网络中存在的各超级节点语义互不匹配，在leader-follower算法中，该节点以自身为超级节点聚为一簇，但性能值却只有3；当再来一个新节点（与id=17的节点语义相似的节点），比如（23,8,0.33）、（24,7,0.38）这两个节点，它们都会成为以id=17的节点为超级节点的普通节点。但是id=17的节点相比，id=23，id=24的节点性能较弱。引入通用类节点后，新节点交由通用类节点管理，当通用类节点管理的节点数达到一定规模后，采用分裂算法将其分裂为若干语义相似簇，最后用合并排序算法从该簇中选择最优节点作为超级节点。所以，在i_lf算法中，id=23的节点为超级节点，id=17的节点就是普通节点，遵从了性能优的节点作为超级节点使用规则。图2是leader-follower算法和i_lf算法中超级节点性能的对比，明显看出，i_lf算法中引入通用类节点后，超级节点的性能比leader-follower算法高。2）超级节点数目分析。按照leader-follower算法的思想，如果新加入节点和超级节点之间超过阈值，则本身成为超级节点。分析表中的数据，目前有8个超级节点。但i_lf算法引入通用类节点后，无法匹配的新加入节点都交由通用类节点管理，当通用类节点管理的节点数达到一定规模后，采用分裂算法将其分裂为若干语义相似簇，最后用合并排序算法从中选择最优节点作为超级节点，超级节点数目降低。图3是通过分析整个节点得出的超级节点聚簇数目。实验结果说明：因为i_lf算法是在leader-follower算法的基础上进行改进的，所以两种算法的聚簇结果相同。但i_lf算法引入通用类节点，在该算法的基础上又提出了分裂算法，所以聚簇的超级节点数目比leader-follower算法少，且所选择出的超级节点都具有良好的性能，性能高达0.9（最优值是1）。因此，比较结果证实了i_lf算法是可行的。4 结语本文提出了i_lf算法，引入通用类节点，并将与超级节点不匹配的新进节点交由通用类节点管理。当通用类节点管理的节点数达到一定规模后，采用分裂算法将其分裂为若干语义相似簇，最后用合并排序算法从分裂出的该簇中选择各方面性能最优的节点作为超级节点。本文成功地解决了原算法聚簇效率低和选择出的超级节点性能差异大的问题。但对超级节点负载过重这方面问题没有详细论述，在以后有待进一步研究。参考文献:1yang b, hector g m. designing a super-peer network c/ proceeding of the 19 international conference on data engineering. washington, dc: ieee computer society, 2003: 49-61.2李祖鹏，黄道颖，庄雷，等. peer-to-peer网络模型研究j.计算机工程，2004，30（12）: 29-31.3谭义红，罗立，林亚平，等.超级节点网络的构建与搜索机制研究j.小型微型计算机系统,2008,29(11):2046-2050.4张琼，张莹，白清源,等.一种新的基于粗糙集的leader聚类算法j.计算机科学,2008,35（3）:177-179.5王展青，郑亮，童恒庆.基于在线聚类法的药物疗效评价模型研究j.武汉理工大学学报:信息与管理工程版，2008，30（2）:236-239.6刘玉枚，杨寿保，陈万明,等.p2p系统中基于信誉感知的超级节点选择算法研究j.中国科学院研究生院学报,2008,25(2):197-203.7柴勇，刘一松, 曹阳.基于分层p2p系统的失效恢复机制的改进j.微计算机信息,2006, 22(30):16-18.8李江峰，周兴铭，张晨曦.基于自聚簇的三层结构p2p网络模型j.计算机科学,2009,36(2):66-69.9卢逗.p2p超级节点网络模式中间件平台的设计与实现d.北京：北京交通大学,2008.10宋玲.语义相似度计算及其应用研究d.济南：山东大学,2009.11相有桓,苗付友,熊焰.移动p2p网络中基于超级节点的资源发现算法j.小型微型计算机系统,2010,31(10):2065-2067.12li juan.