基于信任和可靠性的P2P安全路由算法

刘 浩

(湖南人文科技学院信息科学与工程系，湖南娄底417000)

P2P 网络［1］(Peer-to-Peer network)中每个节点的地位都是对等的。P2P技术以其特有的分布式和自组织等优势迅速发展，已成为互联网络的重要组成部分。根据路由选择的拓扑结构不同，可将P2P网络分为三种类型:集中式拓扑、结构化拓扑和无结构拓扑。Napster是集中式拓扑的典型代表，它具有可扩展性差和单点失效等问题。结构化拓扑，如Chord［2］，对网络资源的存储方法和路由算法都有很精确的定义，因此当节点状态变化频繁时，系统需要很大的开销来维护其拓扑结构。无结构拓扑，如Gnutella，对网络资源的存储和路由机制的管理比较松散，路由机制往往采用泛洪方法。因此，当系统规模较大时，基于泛洪方法的路由机制将会给系统带来较大的网络负载［3］。针对P2P网络中采用的随机选择邻居节点的方法会降低路由效率以及增大网络开销方面的问题，文献［4］在基于Chord协议的P2P网络路由决策过程中，提出一种结构化P2P网络环境下乐观路由思想的路由决策方法。王浩云等人在对中继节点的安全度进行评估的基础上提出了一种基于节点安全度的P2P网络分布式多路径中继路由协议［5］。文献［6］在分析 Chord方法特点的基础上，提出一种改进的Chord构建的路由算法。然而，当前大多数的 P2P 路由算法［2，4－6］并不考虑安全性问题。因此，在P2P网络的路由算法中引入安全机制对提高系统的安全性、可靠性具有重要的意义。

本文使用信任度和路径可靠性来衡量节点的路由转发能力，以指导路由表中“下一跳节点”的选择，从而建立安全可靠的路由路径，并且引入加密、多路径传输等方法以抑制篡改、窃听等典型攻击。在此，我们称该路由算法为SRATR(A Secure Routing Algorithm of P2P based on Trust and Reliability)。

一 路由算法SRATR

(一)SRATR的路由表设计

SRATR的节点路由表与传统的网络路由表是基本一致的(如表1)。路由表包括5项:目标节点、下一跳节点、下一跳节点的信任度(包括直接信任度和推荐信任度)、平均路径长度和路径稳定性参数。路由表将所有能够到达目标节点的路径的下一跳节点全部列出，下一跳路径的选择则根据下一跳节点的信任度、平均路径长度和路径的稳定性参数以一定的概率方法进行选择。一般情况下，信任度高、平均路径长度短和路径稳定性高的下一跳节点被选择的概率要高。这样，一方面可尽可能地保证选择由路由转发能力强的下一跳节点进行路由转发;另一方面在转发过程中路由路径不固定，能提高转发信息的安全性。

表1 SRATR路由表

(二)节点的信任度

在社会网络中，个体之间的信任往往来自于相互之间的直接交往历史与其他个体的推荐。由此建立的信任关系构成了一个社会信任网络，作为个体决定其交互行为的重要依据［7］。参考社会网络的基本原理，我们将P2P网络中用户节点的信任关系也分为:直接信任和推荐信任。

在SRATR中，假定每个节点具有有效的监控机制，通过该监控机制可以获得邻居节点的信息，以判断其邻居节点是否正常处理所传输过去的包。监控时间周期为π，评价每个邻居节点在该时间周期内的行为好坏。若在某监控时间周期π内节点i一共向它的邻居节点j发送了F次包，其中节点j正常处理了f次。如果正常处理率f/F大于约定的参数α，则节点j的直接信任值则线性增加，反之则指数减少(这样做的目的主要是为了给恶意节点较为严厉的惩罚，使其信任度失掉容易，建立难)。那么，

定义1 设节点i对节点 j直接信任度为DTij，其计算公式如下:

其中，DTij的初始值为0，ΔT是每个监控时间周期π内的变化值基数，α为约定的参数，可根据系统的安全需求而定，一般设定为0．5。

定义2 设节点i对节点 j推荐信任度为RTij，其计算公式如下:

其中，Kj为与节点j发生过交互的节点集合(以节点j为出度的节点)。wp是节点p的推荐可信度，一般情况下，它正比于节点p本身的信任值。在此，假设信任值高的节点推荐可信度要高，信任值低的节点推荐可信度同样要低。根据社会网络的原理，这一假设往往是正确的。

定义3 设节点 i对节点 j的综合信任度为Tj。

最后，节点i得到待测节点j的综合信任值Tij，表达式如下:

公式(3)中的β是一个自定义常数，用以衡量直接信任度和推荐信任度的权重。如果节点i为新加入节点，β会选择较小的值;若节点i更相信自己的交互历史，β会选择较大的值。

(三)路径可靠性

在P2P网络中，路由路径的优劣最终反映在信息传输的点到点平均时延和该路径的稳定性。因此，本文利用点到点的平均时延和该路径稳定性作为衡量路径可靠性的依据。

在SRATR中，把源节点s通过某下一跳节点到目标节点d的平均传输延时定义为该路径的平均长度，其大小为源节点收到路由应答信息的累计延时的一半。那么，平均传输延时越小，该路径的可靠性越高。平均传输延时可以通过历史数据统计得到。若在某监控时间周期π内，为达到目标节点d，节点s向其邻居节点i共发出n次路由请求，则通过节点i的平均路径长度可表示为:

其中，Li

s是通过节点i的平均路径长度，tin是通过节点i到目标节点d第n次路由请求的延时。

路径稳定性参数可以使用路径延时的标准差来表示，公式描述如下:

显然，路径延时的标准差越小，路径的可靠性越高。综合起来，通过节点i的路径可靠性可以表示为:

(四)SRATR的工作机制

1．路由信息扩散方式

系统内各个节点向它所有的直接邻居节点发送它对系统内其他节点的可达信息，并通过逐级扩散的方式使这种可达信息在系统内传播，从而使各个节点能推算出自己到系统内其他非邻接节点的路由。

2．初始化过程

当系统刚刚启动时，系统中的节点很少，每个节点的路由表均为空，需要经过一段时间的广播扩散才能建立起各节点的路由表。随着扩散的不断进行，系统内的节点路由表会不断的完备。随着节点数目的增加，系统覆盖范围更广，可选路径随之不断增加，各节点的路由表也会变得更加完备，并且路径的可选择范围会更多。

3．路由表的更新与维护

为了使系统内各节点的路由信息保存最新状态，每隔一段时间，节点将自己的路由信息发送给相邻节点，为了防止反弹效应，信息中不包含从对方节点获得的路由信息。若某节点退出系统或被邻居节点检测到不可达，则邻居节点将该节点从自己路由表中删除去掉，同时将该信息在系统内广播。为了防止节点定期同时进行路由信息交换，在系统内产生周期性的流量高峰，需要为各节点随机地设置不同的广播间隔。

4．信息发送与转发

先给出以下相关定义。

定义4 假设以节点i为观测点，其某一邻居节点j的路由转发能力为:

当节点i需要发送信息时，则其某一邻居节点j以概率

被选择为下一跳节点，并在发送报文中加入源节点到目的节点的路径信息，其中λ为归一化常数，即为直接邻居节点集。中间节点收到信息后以同样的方法进行信息转发，同时将自身节点id加入到传输路径中。为了防止循环路由，若发现下一跳节点与收到的路径信息中节点有重复，则重新选择下一跳节点。

系统内的任何节点在转发(或发送)信息后，都要通过监控机制监控“下一跳节点”的行为，并进行信任度的计算，同时需要反馈给相应的节点，以更新该“下一跳节点”的推荐信任度。

为了防止路由信息在系统永久性的转发，每个路由信息包设置TTL(time of life，TTL初始值可根据系统的安全性需求而定)，当路由信息包转发一次，TTL属性值就减1，若某个路由信息包的TTL值为0，则停止继续转发，丢弃该路由信息包。

(五)安全性

1．防窃听

在SRATR中，系统采用报文拆分与组装技术对每一段报文发送之前进行加密处理，发送节点将每个待发信息拆分成若干段，分开发送，再由接收节点完成信息的组装。由于采用了拆分和组装技术通过多路径传输，窃听者很难找出不同报文段之间的相关性，通过组装恢复出报文，而且，数据加密技术使系统的防窃听能力更强。

2．防篡改

发送节点使用MD5对报文进行信息摘要，当传输路径中有恶意节点，并对传输数据进行了篡改，数据接收节点很容易辨别出来，并通知发送节点重新传输数据。

3．防路由失效

为了防止路由失效，接收节点在收到信息后需向发送节点返回一个确认信息ACK，若在约定时间内没有收到ACK，源节点会重新选择路径进行数据重传。为了防止恶意节点伪造ACK造成数据传输的失效，接收方不按照原路径返回ACK。

二 仿真试验与分析

为了评价SRATR的性能，本文采用JAVA语言设计了一个类似P2Psim的系统模拟软件，通过该模拟软件设计SRATR的网络模型，以实现信任的评价、路由的选择。

实验假设的应用场景为文件共享应用，系统节点总数为1000，每个节点管理50个不同文件。系统中只有行为良好节点和纯恶意节点两类，所谓行为良好节点，是对其他节点的评价上都是真实的，并且转发信息行为良好。而纯恶意节点只是转发信息行为恶意，如不转发路由信息。其中系统参数α和β均设定为0．5，TTL设置为5。

首先考察在恶意节点为20%的情况下，随机从10个相同的节点分别发起10次文件查询请求，当节点总数变化时，比较SRATR和Gnutella的平均查找时间。从图1可以看出，当节点数目较少时，平均查找时间相差不大，但随着节点数目的增多，SRATR明显比Gnutella的平均查找时间要少得多。

图1 模拟仿真实验得出的两种平均查找时间分布图

现在考察在节点总数不变为1000的情况下，随机从10个相同的节点分别发起10次文件查询请求，当恶意节点的百分比变化时，比较SRATR和Gnutella的平均查找时间。从图2可以看出，当恶意节点的百分比增大时，SRATR和Gnutella的平均查找时间都会增大，但是SRATR增大幅度要比Gnutella小得多(如图2)。

图2 平均查找时间比较图

总之，SRATR的路由性能要优于Gnutella，并且SRATR能有效抑制恶意节点，安全性好。

三 结语

本文给出了一种P2P网络的安全路由算法SRATR，系统节点以一定的概率方法选择信任度高、路径可靠性高的邻居节点进行信息转发，有效地提高了系统的安全性、可靠性和资源定位能力。下一步工作将研究SRATR路由算法的消息控制策略。

［1］陈贵海，李振华．对等网络:结构应用与设计［M］．北京:清华大学出版社，2007:1－5．

［2］ION STOIEA，ROBERT MORRIS，DAVID KARGE．Chord:A scalable Peer-to-Peer lookup service for internet applications［M］//Proeeeding of ACM SIGCOMM 2001-Applications，Technologies，Architectures，and Protocols for Computers Communications．New York:Association for Computing Machinery，2001:149-160．

［3］刘浩，张连明，朱同林．基于Cayley图的P2P覆盖网络模型研究［J］．吉林大学学报:工学版，2011，41(5):1414－1420．

［4］杨 磊，秦志光，蓝天等．结构化对等网络中基于信誉的乐观路由决策［J］．控制与决策，2012，27(6):839－844，849．

［5］王浩云，徐焕良，任守纲．基于节点安全度的PP网络分布式多路径中继路由协议［J］．计算机科学，2012，39(10):54－59．

［6］王传殊，王意洁．基于网络延迟的 P2 P路由算法的研究［J］．计算机科学，2007，34(6):41－44．

［7］PAUL C，JAMESD，VICTOR G．Social network model of construction［J］．Journal of construction Engineering and Manage-ment，2008 ，134(10):804 －812．