P2P网络中基于信任的拓扑结构与搜索机制
2010-11-26魏长明
魏长明
(低维量子结构与调控教育部重点实验室,湖南师范大学物理与信息科学学院,中国 长沙 410081)
有关数据表明P2P通信流量已经在Internet通信总量中占到了相当巨大的比例[1].在P2P系统中,用户节点既可作为客户机,又可作为服务器,它是当前的大规模分布式资源共享系统.资源搜索是节点在网络中查寻合适的信息提供者的过程,其首先需要定位相应的资源提供者,因此提高系统的资源查找效率十分关键.
根据数据的存储分配和网络拓扑,P2P系统可以分为两大类:结构化的和非结构化的[2].较早的研究已经表明了结构化P2P系统可以有效地改进系统的性能,如CAN、Tapstry和Chord[3]等.然而,结构化P2P系统的严格结构使得网络很难扩展和维护,动态性很差.非结构化P2P系统是完全自组织分布式的,资源可以随机地分配到任意节点上,如文献[4]提出了一种基于“gossip”的非结构化P2P系统的资源搜索机制.但是,它们往往搜索效率低下.有关研究表明,借鉴人类社会社区的概念之上虚拟社区方法有助于提高资源共享和发现的效率[5].节点通过更新同其他节点的链接关系来实现自组织的目的,节点以完全分布的方式来更新同其他节点的关系,使节点在拓扑上表现为虚拟社区形式的聚集[6].基于兴趣的聚集是目前拓扑研究的热点,其假定了网络中节点的交互围绕着一定的兴趣偏好,此类聚集方案都是通过度量节点间共享资源内容的相似性来更新链接关系,并利用节点的聚集效应降低网络直径、削减网络流量、改善资源发现效率等[7].实际上这类方案都是基于如下假设:具有相近兴趣的节点更能提供所需的服务.其中存在的主要问题是基于兴趣的自组织方案没有考虑节点实际提供服务的能力,即使一个节点具有相同的兴趣,但并不意味着都可以提供较好的服务质量.
目前,P2P系统中关于信任研究和应用已经涉及到了基于节点可信性的拓扑进化问题,其中使用信任来刻画节点提供服务的能力可以依据节点在网络中的活动状态来更新同它的交互关系,相应地改善网络性能.本文提出了一种基于信任的拓扑结构和资源搜索机制.首先,描述了信任计算模型,然后,对网络的拓扑结构和搜索机制进行了详细的阐述,最后通过仿真实验检验了该机制的有效性.
1 信任计算
信任是主体对客体特定行为的主观可能性预期;对这个期望可以用信任度来衡量,信任度取决于一个被信任实体完成任务的能力、诚实度、可靠性等.在P2P网络中提供服务的节点称为服务节点,享受服务的节点称为消费节点.为了便于区分善恶节点,每个节点必须被赋予一定的可信度.消费节点优先选择信任值高的服务节点进行交易.而服务节点可以根据一定的访问控制策略接受高信任值节点的请求和拒绝低信任值节点的请求.所以,每个节点应该争取提升自己信任值,以获取更好的服务.节点可以通过为别的节点提供优质可靠的服务来提高自己信任值.当然如果节点提供虚假文件下载或服务质量低,其信任值应该被降低以惩罚.把P2P网络中进行的一次消费与服务称为交易,消费节点可以对该次交易进行评价.交易评价值是消费节点对服务节点的服务质量的数量评价,它将影响服务节点信任值的高低.
因为信任的本质使得信任很难用一个精确的值来表示,因此在这里,信任度的值用[-1,1]之间的实数来表示.很多信任计算模型中使用满意的或不满意的交易次数来计算信任值[8].而实际情况是,仅仅使用“满意”和“不满意”来评价一次交易是不够精确的.该信任计算模型使用多种评价值以提高信任值的计算精度.以4种评价值为例,各种取值情况如表1 所示.实际应用时,根据具体的情况还可对评价值进一步细化.
表1 评价说明
由于本文的重点不在于对信任计算模型的研究,所以只给出一个信任计算的简单模型,需要深入研究的有关读者可以参考文献[8~9]等.
首先给出节点s的信任度基本计算公式:
TS=σTSC+E(s,i)
(1)
其中,TSC为第i次交易之前节点s的信任度,其初始值为0,TS第i次交易之后节点s的信任度;E(s,i)代表与节点s进行第i次交易后的交易评价值,其取值范围为(-1, 1),如表1所示,具体大小由交易请求者对服务的满意程度决定;信任σ为时间衰减因子,其取值范围为(0, 1).
在网络中发生的成千上万的交易中,每次交易都是和其他交易有不一样的地方,并不能够平等看待它们的重要级别.比如有的交易的规模很大,有的交易的重要性很高,有的交易的持续时间很长等等.这都是造成每次交易的权重不尽相同的原因.例如一个作电子商务的社区,那么在计算针对某次交易的反馈值的时候,那次交易的交易额就是非常重要的考虑因素.于是我们引入交易环境因子来调整公式(1),从而成功地阻止某些节点想要进行某些恶意行为的企图.比如上面我们提到过的,某个节点可能在参与许多次交易额比较小的事务时,遵守规则,表现良好,但是在参与交易额很大的事务时,因为有利可图,为了给自己获得最大的利润,它可能就利用自己以前在许多小型交易中积累的良好的信誉去欺骗另外的交易一方,从中获利.也就是说应该考虑交易的内容以及它的范围.
因此,作者引入交易环境因子来调整信任度计算公式.
TS=σTSC+E(s,i)×H(s,i)
(2)
其中H(s,i)为交易环境因子,表示节点s第i次交易的权重,具体大小与交易的种类、时间长短、规模等有关.
2 网络拓扑和搜索机制
2.1 网络拓扑构建
定义1有向图G=(P,E),其中P是节点集合,E是边的集合,(i,j)∈E,表示了节点i到j的链接,(i,j)∈P.
P2P网络可以表示为一个有向图G,P2P网络中的链接是非对称的,代表了节点的资源查询消息的转发通道.
定义2称N(i)={j|(i,j)∈E}为节点i的直接邻居节点集合,即节点i可将查询消息转发到的直接邻居节点.
为了实现同服务提供能力较强、信任度高的节点间的连接关系.一般,选取最近与节点i有过交易并且服务提供能力较强、信任度高的节点构成集合Ni.
那么,P2P网络拓扑有向图G有如下几个属性:
(1)随着节点动态的加入和退出,以及节点对直接邻居节点的选择都会导致节点间的链接的更新,网络拓扑有向图G会随时间而改变;
(2)由于没有全局知识,节点利用本地对其他节点的知识对直接邻居节点的选择可能导致节点的聚集;
(3)节点链接更新算法应该考虑节点间信息的分发.
P2P系统中每个节点都保有一张以往的交易对象列表和直接邻居节点列表,其中交易对象列表包括交易节点身份、相应的信任值以及该信任值更新时间,直接邻居节点列表包括直接邻居节点身份信息、相应的身份值以及该信任值更新时间.两个列表中的每一记录的时间都必须是最近的,可以规定一个时限(比如1个月),超过时限的信任值记录,节点可以周期性的更新本地直接邻居列表以及相应的信任值记录.
定义3记Tj为i对j的信任值.
定义4称Mi为节点i有其信任记录的节点集合.
随着关于特定目标节点的交互经验的积累,以及目标节点行为的变化等因素,都将导致对目标节点信任判断的更新,相应的,也需要更新链接以反映信任因素的变化.这里给出了一个基于信任链接更新算法,使网络中的节点同具有更强的服务能力的节点建立更为紧密的交互关系.在i与目标节点j交易完成,通过公式(2)计算获得节点j的信任值Tj后,若j∈Mi-Ni,Ni中h的信任值最小,且Tj>Th,则用j的链接替换同h的链接;若j∈Ni,Mi-Ni中h的信任值最大,且Th>Tj,则用h的链接替换同j的链接.节点i的链接更新算法伪代码如下算法1:
updateTrust(j)
if |N|<Φthen
connectTo(j);
else
ifj∈Mi-Nithen
h=chooseNodeWithMinTrustFrom(Ni);
ifTh connectionReplaceWith(h,j); endif else h=chooseNodeWithMaxTrustFrom(Mi-Ni); ifTh>Tjthen connectionReplaceWith(j,h); endif endif endif 算法1链接更新算法 这里的updateTrust()过程指的是,当本地两个列表中的信任值记录有更新的时候就触发上述的算法,进行链接的更新. 节点链接关系的更新体现为网络拓扑的变化.节点通过更新同其他节点的链接关系,实现了同服务提供能力较强、信任度高的节点之间的连接关系.这样,将会增大节点的资源搜索的内容可达性,削减网络中消息的流量,减少服务的搜索时间. P2P系统中基于前一节网络拓扑的资源搜索算法如下算法2: 1)首先请求节点q需要向其直接邻居节点中信任度最大的节点发出资源搜索消息Q,其格式为{content,IPq,TTL}.其中TTL代表该消息的生存周期,content表示请求的资源,而IPq代表了请求者的地址. 2)如果节点q的信任度最大的直接邻居节点r可以提供消息Q中所描述的资源,则向q返回一个应答消息R,其格式为{answer,IPr},其中answer代表应答消息内容,确实拥有q所需要的资源,IPr为r的地址,算法终止. 3)否则,当节点r不能提供消息Q中所描述的资源并且TTL>0;则TTL=TTL-1,节点r将{content,IPq,TTL}再转发给它自己的信任度最大的直接邻居节点,如果TTL<0,则算法终止. 4)重复顺序执行算法中第2)步和第3)步. 5)当q收到了应答消息R,表明资源搜索成功,它将根据R来定位资源提供者的位置,并同资源提供者开始一次交易. 6)如果超过一定时间,还没有q收到了应答消息,则表明资源搜索失败. 由于,本文的资源搜索机制是在基于信任链接的网络拓扑上进行的,因此,它能够有效地抑制一些恶意节点的欺骗,具有良好的安全性能. 本文的搜索机制与文献[3~4,7]是完全不同的,克服了它们现有的一些缺点.这些搜索机制的性能比较如表2 所示. 表2 几种搜索机制的性能比较 本节将通过系统模拟,通过和文献[4]中的基于“gossip”的搜索机制进行比较,来检测该搜索机制的性能.作者在PC机上做了模拟实验,其中CPU是Intel 酷睿2双核 T5900,2G内存;操作系统是Linux Ubuntu;网络拓扑结构按照前面的定义通过Internet拓扑模拟工具BRITE产生的. 图1 2种搜索机制的比较结果 在仿真实验中,资源请求节点和资源目标节点(服务节点)均是随机分布的.每次交易完成后,节点将按照公式(2)更新服务节点的信任值,同时,按照3.1节中的算法1对请求节点的直接邻居节点进行更新,相应地也改变了网络的拓扑结构.资源请求节点分别使用文献[4]中的搜索机制和本文的算法2进行资源查找.在此,给出两个定义.称资源请求节点经历过的节点数除以网络节点总数为搜索代价;称查找成功的次数比所有资源请求总数为搜索成功率.显然,一种有效的搜索机制应该搜索代价小,搜索成功率高;或者这么说在要求达到相同的搜索成功率高情况下,效率高的搜索机制应该搜索代价越小.在实验中,每进行了1 000次搜索请求后,作者就计算2种搜索机制下的平均搜索代价和搜索成功率.图1给出两种搜索机制的比较结果. 从图1可以看出,在达到相同的搜索成功率高情况下,本文搜索机制的搜索代价较小,文献[4]中的搜索机制较大.故本文搜索机制的效率要高. 在研究了已有P2P网络中资源搜索机制的若干局限性后,构建了一种基于信任的拓扑结构和资源搜索机制.未来的研究工作包括如何在此基础上建立完整的激励机制,以提高P2P系统的公平性和动力,减少“free riding”行为等. 参考文献: [1] BO ZHU, SUSHIL JAJODIA, MOHAN S. Kankanhalli. Building trust in peer-to-peer systems: a review[J]. International Journal of Security and Networks, 2006, 1(1-2): 103-112. [2] HUANG J C, LI X Q, WU J. A class-based search system in unstructured p2p networks[C]//Proceedings of the 21st International Conference on Advanced Information Networking and Applications, Niagara Falls, Canada, 2007,76-83. [3] ION S, ROBERT M, DAVID L N,etal. Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications[J]. IEEE/ACM Transations on Networking, 2003, 11(1):17-32. [4] STEPHEN B, ARPITA G, SALAJI P,etal. Gossip algorithms: design, analysis and applications[C]//Proceedings of IEEE Infocomm, Miami, 2005, 3:1 653-1 664. [5] GNASA M, ALDA S, GRILGULL J,etal. Towards Virtual Knowledge Communities in Peer-to-Peer Networks[C]//Proceeding of ACM SIGIR Workshop on Distributed Information Retrieval, Canada: ACM Press, 2003:3-8. [6] HERWIG U, MARKUS W. Cluster-building in P2P-community networks[J]. The Journal on Parallel and Distributed Computing and Systems, 2002, 12(5): 685-690. [7] SRIPANIDKULCHAI K, MAGGS B, ZHANG H. Efficient Content Location Using Interest Based Locality in Peer-to-Peer Systems[C]//Proceeding of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE Press, 2003, 2 166-2 176. [8] 窦 文,王怀民,贾 焰,等. 构造基于推荐的Peer-to-Peer环境下的Trust 模型[J]. 软件学报, 2004,15(4) :571-579. [9] LIU H, ZHANG L M, ZENG B. An Anonymous Trustful-agents-based Trust Model for P2P Network[C]//Proceeding of 2009 Asia Pacific conference on Information processing, IEEE Press, 2009:426-429.2.2 资源搜索机制
3 仿真实验
4 小结