摘要 现有的信任模型在信任路径搜索方面存在两个方面的不足：搜索过程中影响信任值的因素考虑得尚不够全面，或者同一而论；同时，对邻居节点选取时，忽略了双方交互次数的重要性。针对以上两点问题，基于图论提出了一种路径过滤性搜索算法。该算法首先引入基于交互次数的诚实可信度，用以进一步衡量节点的可信程度，并作为搜索优先级的依据，使得搜索的优先顺序更加合理。同时基于影响节点可信度的多重因素进行过滤性搜索。通过算法分析，该算法算法复杂度（n-m2量级，比原一般细粒度算法n2量级明显降低。实验结果表明，该算法能够更好地过滤掉恶意节点，提高信任路径搜索算法的准确性，抵制恶意节点攻击。
关键词 分布式网络；推荐信任；路径搜索；诚实可信度
中图分类号 TP18
文献标志码 A
0引言
目前，信任机制是解决大规模分布式系统安全威胁的有效可靠途径。信任机制指的是在复杂的网络环境中，对所有实体的关系建立合理的信任模型，从而获得它们之间的信任关系，继而基于信任的一系列相关性质以及信任在网络中传递的性质，在信任网中进行信任值计算，从而作出信任决策。
由此看出，如何建立有效的信任计算模型至关重要。建模包括，如何对信任关系进行形式化描述；如何对两个即将交互的节点之间的信任路径进行搜索，以及如何合并来自第三方推荐得到的推荐信息，并将直接交互经验与这些推荐信息结合；如何对信任值进行更新，都是要解决的问题。这里重点解决路径搜索问题。
针对现有模型存在的问题，充分考虑不同因素对信任的不同影响，从而设置合理的过滤性条件，简化搜索过程，并结合交互次数对信任信息的影响，提出了一种过滤性路径搜索算法。
本文第1节介绍了近几年国内外的相关研究工作，第2节对信任以及信任网络进行了相关的解释，第3节描述了影响路径搜索的多个因素以及算法，第4节进行仿真分析，最后第5节对全文进行总结。
1相关工作
近年来，为解决分布式系统的安全问题，学者们用各种数学理论及方法对信任机制进行研究。1996年，Blaze等[1]首次提出“信任管理”的概念，其目的是解决Internet网络服务的安全问题，并首次在分布式系统中引入了信任管理机制。其后众多学者们展开了对信任机制的研究，他们提出了很多适用于不同分布式应用系统的信任模型。
在信任的形式化表示方面：Jsang等[2]利用了证据空间和观念空间来度量信任关系，并提出信任是主观臆断的，因而有主观性及不确定性，需要多次的交互经验得到。随后又有Jameel等[3]引入向量运算机制来描述信任关系，该模型对于一些不确定的因子进行了数学量化。Theodorakopoulos等[4]引入了有向图来描述信任传递的路径，用图搜索来表示信任传递路径的搜索。另外，在信任关系及其性质方面，童向荣等[5]研究了合作环境下的信任节点关系以及各种信任传递性质，为信任的推荐链搜索提供了理论依据。对性质的应用也已有研究，如龙宇等[6]给出了信任关系的一系列性质的具体应用。
在信任传递路径搜索方面，Jsang等[7]提出了基于主观逻辑折扣算子和合意算子的传递信任计算模型，认为在一致的信任目的的语义约束下，信任是可以传递的。该算子的不足是：没有处理复杂的冗余信息，信任路径搜索的时间复杂度高。Chen等[8]提出了一种面向无线传感器网络的信任传播计算机制以及邻居节点之间信任评价的聚合方法。随后又通过计算推荐链上所有节点的信任值的平均值来得到传递信任值，这就是信任传递值的一种平均算法，这种信任计算模型的不足在于没有给出信任因素的度量方法和置信因子的确定方法，同时，未对冗余信息进行处理，使得信任路径搜索耗时较多。Massa等[9]提出典型的Mole Trust算法，设置了一个最大路径长度，在计算信任值的同时，还进行了回溯搜索策略。童向荣等[10]研究了动态的信任机制，将交互历史分段计算，提高了平均计算的准确度。蒋黎明等[11]对信任传递路径中的依赖关系进行了消除，提出了结合DS（Dempster/Shafer证据理论和图论的消除依赖关系的信任传递方法，但其路径搜索具体算法未详细给出。
在信任值的聚合与更新这一方面，田俊峰等[12]提出基于推荐的信任链管理模型，主要是利用加权紧密度，对信任链上的推荐信任进行合并，降低了信任链搜索的时间复杂度，但是对于搜索方法，考虑因素不全面，降低了信任值的准确性。张琳等[13]164提出了基于多影响因素的信任评估算法，在对信任值进行更新的计算中，考虑了时间环境等多重影响因素，并引入节点交互能力、诚实能力等细节因子，但模型的动态性差。李峰等[14]将可信任推荐以及历史交互窗口引入到了信任评估模型中，采用实体稳定度实现了激励和惩罚。
可以发现，目前研究工作者们在大规模分布式网络环境中的安全问题解决上，已找到了切实有效的方法，即建立信任计算模型。但在路径搜索方面仍然存在一些问题：首先，搜索时的约束条件考虑不充分，或是推荐信息丢失，或是重复计算，可基于影响信任传递的多重因素进行搜索；其次，未对考虑的多重因素区分重要性，导致准确性不高。同时，很多文献忽略了双方交互次数的重要性，交互次数是影响路径搜索准确度的重要因素，将其引入搜索算法可提高信任路径搜索的准确性。
2信任及信任网络
2.1相关概念
信任是基于自身知识和经验基础上的判断，信任关系是社会学角度上最复杂的社会关系之一，是较难度量的心理认知，实体之间的信任关系是不稳定的而且很难明确定义。为方便后面的说明，本文引入了一些与信任相关的名词的描述性定义。
定义1服务请求节点（Service Requestor。网络中需要服务资源的节点。记作“Re”。
定义2服务提供节点（Service Provider。网络中为服务请求节点提供所需资源的节点。 记作“Pr”。