王春红,任姚鹏,姚喜妍

(1.运城学院 计算机科学与技术系，山西 运城 044000;2.运城学院 应用数学系，山西 运城 044000)

一种改进的动态信任信息聚合算法

王春红1,任姚鹏1,姚喜妍2

(1.运城学院 计算机科学与技术系，山西 运城 044000;2.运城学院 应用数学系，山西 运城 044000)

随着分布式应用系统的发展，系统形态正从相对静态的形式向开放的、动态的服务模式转变。在这动态环境中，基于证书的静态信任机制就不再适应，就出现了动态信息机制管理问题。其中，核心问题之一是动态反馈信息的聚合。而现有的动态信任聚合算法基本都采用基于信任链或广播方式，这样往往导致了系统运算收敛慢、可扩展性差等问题。文中提出一种改进的动态信任信息聚合算法。首先，利用一种反馈信任值聚合方法获得反馈信任值；接着，在此基础上，基于蚁群算法通过多次循环寻找出多条较优的独立信任路径，并获得最终的反馈信任值。实验结果表明，该算法效率较高，可扩展性较好，可以获得较合理的反馈信任值，而且可在一定程度上有效防止联合欺诈行为。

动态信任；反馈信任；蚁群算法；信任路径

0 引 言

伴随着面向Internet的企业资源规划系统(ERP)、客户关系管理系统(CRM)、供应链管理系统(SCM)、电子商务系统(e-Business)等大型分布式商业软件系统的大量涌现，其系统模式已从较为封闭的运行环境转变为高度变化的开放性运行环境。由于分布式的开放环境使得各资源实体分布于网络的不同位置，且不存在一个中央控制主体，因此传统的ACL和基于公钥的证书体系等集中式安全控制机制就不能很好地满足这种分布式系统的安全需求。因此，在开放式的网络环境中，信息安全的管理就不能采用传统静态的信任管理模型，而转化为动态信任管理的问题[1-3]。

在动态的信任管理中，如何有效地进行信任反馈信息的聚合成为了其中一核心问题[4-8]。在目前的信息聚合算法中，大都采用信任链或广播方式来计算推荐信任值，这对算法的收敛性和可扩展性都是极大的挑战[9-12]。因此文中从信任路径的寻找和算法的可扩展性两方面着手，提出一种改进的动态信任聚合算法。该算法首先采用了一种反馈信任值聚合函数，来获得实体的推荐信任值，增强在大规模网络环境中算法的可扩展性；再利用蚁群算法在较短的时间内获取多条较优信任路径；最后聚合算法获取最终的信任值。

1 反馈信任值聚合方法

在网络环境中，为了保证信息的安全，实体之间要进行交互，需要通过测评要进行交互的实体的信任度，来确定是否与其交互。实体信任度的计算分为三种情况：

(1)两实体之间最近有直接交互的记录；

(2)两实体没有交互记录；

(3)两实体交互的记录比较陈旧[12]。

对于第一种情况，就可以利用两实体直接交互后实体间的直接评价来获取，也就是直接信任值；对于第二、三种情况，需要借助于其他实体侧面获取实体信任值。

文中采用了一种反馈信任值聚合方法。该方法是基于其他相关联的实体之间的直接信任值来获得实体的反馈信任值。多数情况下是要获取实体的反馈信任值。

1.1 直接信任值

直接信任是指实体Pi在与实体Pj直接交互后，Pi对Pj的满意程度。这里，用E(Pi,Pj)表示Pi对Pj的信任满意程度，且E(Pi,Pj)∈[0,1]，值越大表示Pi对Pj越信任越满意。

假设实体Pi和Pj在最近T次交互中，Pi对Pj的信任值为集合Eij={e(1)ij,e(2)ij,…,e(h)ij}。其中，0≤e(k)ij≤1。则Pi与Pj的直接信任值可借用人工智能理论中的可信度推算公式,通过合成计算方法求出其信任值：

CF1,2(H)=CF1(H)+CF2(H)-CF1(H)*CF2(H)

这样，Pi与Pj的直接信任值Eh(Pi,Pj)可采用式(1)逐步合并：

E1(Pi,Pj)=e(1)ij*r(1)+e(2)ij*r(2)-e(1)ij*r(1)*e(2)ij*r(2)

Eh(Pi,Pj)=e(h)ij*r(h)+Eh-1(Pi,Pj)-e(h)ij*r(h)*Eh-1(Pi,Pj)(h>1)

(1)

其中，根据人类交往经验，最近一次的交往能更好反映人与人之间的关系。因此，网络中计算实体的信任度时，模拟了人的行为，引入一个r(k)函数。它是一个随时间逐渐衰减的函数，其值在0，1之间，定义如下：

(2)

1.2 反馈信任值

反馈信任主要是通过信息的传递性来计算的(a信任b，b信任c，则a信任c)。假设实体Pi需要测评实体Pj的反馈信任度，来确定是否与Pj发生交互。则实体Pj的反馈信任值可通过下面的反馈信任值聚合函数来求得。

R(PiPj)=∑E(Wk,Pj)/n

(3)

其中：Wk表示实体Pj的第k个反馈者；E(Wk,Pj)表示实体Wk对实体Pj的直接信任值；n表示实体Pj反馈者的数目。

利用上述公式求得的反馈信任值只是一种情况下的反馈信任值，因为对于实体Pj的反馈者选择时，可能会出现多种情况。也就是说仅利用公式一次计算出的反馈信任值并不一定正确，可能存在联合欺诈的行为。因此，文中在获得反馈信任值的基础上，又采用了蚁群算法，选取多条较优的信任路径，最后计算出最终的反馈信任值。这样，就可以有效避免网络中的联合欺诈。

2 信任路径的寻找

2.1 信任路径

这里，把网络中的信任关系抽象为一带权有向图G=((V,E),S,D,L)。其中：V为图顶点集，代表网络中的各个资源实体；E为有向弧集，代表实体间的相互信任关系，并用每条弧上标记的权重Wij∈[0,1]表示实体i对实体j的推荐信任值；S∈V表示源实体顶点；D∈V表示目标实体顶点；L表示信任路径的最大长度，用来控制算法的搜索范围。

假若搜索的信任路径为S→V1→V2→…→Vl-1→D，其信任路径长度则为l(l≤L)。同时，一条信任路径上的反馈信任值可用式(4)求得。

Pathi=∑R(Vi,Vj)

(4)

其中，Vi,Vj都在第i条信任路径上，R(Vi,Vj)表示实体Vi对实体Vj的反馈信任值，利用式(3)便可以求得。

2.2 基于蚁群算法的信任路径寻找

用m表示蚂蚁数量，dij表示实体顶点间的距离。τij(t)表示t时刻i→j路径上残留的信息素量，物理意义为记录实体i对实体j的反馈信任值[13-14]。m只蚂蚁从源顶点S出发，移动过程中蚂蚁运动的转移按一定转移概率进行，其转移概率计算公式如下：

(5)

当蚂蚁从源顶点出发到达目标顶点D或当移动的长度大于L时，蚂蚁停止运动。当所有的蚂蚁都停止寻径时，一次循环结束。

在寻径过程中，随着时间的推移各个弧上原有的信息素会逐渐降低，有蚂蚁经过的路径信息素会相应增加，其信息素按式(6)调整：

(6)

其中，Δτij表示第k只蚂蚁本次循环中在弧ij上信息素的增量。

经过多次循环选出信息素浓度最高的路径，也就是最优的信任路径。接着，在图G中去掉该信任路径中的中间顶点，得到G'；再基于蚁群算法找到下一条次优的信任路径。

这样循环k次，便可得到k条独立的较优信任路径。

3 改进的动态信任信息聚合算法

该算法的基本思想是：首先计算出各实体的反馈信任值，接着基于信任值，采用蚁群算法获取k条较优的信任路径，最后获取最终的反馈信任值。

最终动态反馈信任值计算公式为：

FR(S,D)=∑Pathi/K

(7)

下面是改进的动态信任信息聚合算法描述。

For(number_betterpath=1;number_betterpath

{for(number_cycle=1;number_cycle

{for(ant_steps=1;ant_steps

{for(i=0;i

{Ifant[i].endstate=falsethen

按式(5)计算转移概率，选择下一个顶点；

记录第i只蚂蚁走的路径；

}

}

一个循环结束；按式(6)调整值;

}

按式(4)计算路径的推荐信任值；

记录路径及推荐信任值；

在图G中删除这条路径中的节点;

}

按式(7)计算K条信任路径综合后得到最终的推荐信任值

4 实验结果及分析

4.1 算法性能分析

从收敛性和算法可扩展性两方面来评估算法的性能。其中，算法的收敛性主要通过算法的运行时间来进行衡量；算法的可扩展性通过平均存储空间开销来衡量。平均存储空间=占有的总存储空间/顶点个数。

图1和图2分别是时间和存储空间与顶点规模的关系图。

图1 时间与顶点规模的关系图

图2 平均空间开销与顶点规模的关系图

从图1和图2可以获知，文中算法无论在时间上还是空间上，随着顶点规模的变大，其变化均为平缓，这就说明了该算法具有较好的收敛性和可扩展性。

4.2 算法有效性分析

文中构建了一个具有80个顶点的有向图，来模拟现实具有80个实体的网络环境；并假设每个顶点至少与15个顶点有弧，来表示实际网络中每个实体至少和15个实体发生了直接交互；其弧上的数值是随机产生的，且属于[0,1]范围，代表实体间的直接信任值。同时，蚁群的数量为30，α，β都为1。

图3给出了信任路径长度与寻找到的信任路径的关系。

图3 信任路径长度与所寻找到的信任路径数的关系

由图3可知，当选取的信任路径长度越大，所寻找的信任路径就越多，则找到最佳信任路径的可能性就越大，从而可更加有效地避免联合欺诈行为，但算法效率将有所降低。

5 结束语

文中提出了一种改进的动态信任信息聚合算法。该算法利用蚁群算法和一种反馈信任值聚合函数，通过寻找多条较优信任路径，得到较为准确的最终反馈信任值，能在一定程度上有效避免联合欺诈行为。通过实验验证了该算法具有较好的收敛性和可扩展性，从而能够适应现实复杂的、动态多变的网络环境。下一步的研究工作是如何通过调整算法中的相关参数，实现在保证反馈信任值准确的情况下进一步提高算法的效率。

[1] 李小勇，桂小林.大规模分布式环境下动态信任模型研究[J].软件学报，2007,18(6)：1510-1521.

[2] 易 磊.网格环境下信任模型及其应用研究[D].长沙:中南大学，2008.

[3] 农 毅，古天龙.基于网格环境中的量化评估信任模型[J].计算机科学，2007，34(6)：88-91.

[4]YuB，SinghM.Developingtrustinlarge-scalepeer-to-peersystems[C]//ProceedingsofthefirstIEEEsymposiumonmulti-agentsecurityandsurvivability.LosAlamims，USA：IEEEComputerSocietyPress，2004：1-10．

[5]ZhouRF，HwangK．PowerTrust：arobustandscalablereputationsystemfortrustedpeer-to-peercomputing[J]．IEEETransactionsonParallelandDistributedSystems，2007，18(4)：460-473.

[6] 李小勇，桂小林，毛 倩，等.基于行为监控的自适应动态信任度测模型[J].计算机学报，2009，32(4)：664-674.

[7] 常俊胜，王怀民，尹 刚．DyTrust：一种P2P系统中基于时间帧的动态信任模型[J].计算机学报，2006，29(8)：1301-1307．

[8] 吴 鹏，吴国新，方 群．P2P网络信誉机制研究综述[J].计算机科学，2009，36(6)：26-28.

[9] 田春岐，江建慧，胡治国，等．一种基于聚集超级节点的P2P网络信任模型[J]．计算机学报，2010，33(2)：345-355.

[10]FengQY，SunYL，LiuL，etal.Votingsystemswithtrustmechanismsincyberspace：vulnerabilitiesanddefenses[J]．IEEETransactionsonKnowledgeandDataEngineering，2010，22(12)：1766-1780.

[11]ChenJG，BrudaSD．Anefficientfeedbackbasedtrustmodelforpervasivecomputing[J]．InternationalJournalofDigitalContentTechnologyandItsApplications，2010，4(7)：215-225.

[12] 李小勇，桂小林，赵 娟，等.一种可扩展的反馈信任信息聚合算法[J].西安交通大学学报，2007,41(8):879-883.

[13] 高承实，王建政，张 栋.基于蚁群算法的信任路径寻找算法[J].计算机工程与应用，2007，43(15)：131-133.

[14] 张 潇.基于蚁群算法的动态信任模型研究[J].计算机与数字工程，2010，38(8)：93-94.

An Improved Aggregation Algorithm of Dynamic Trust Information

WANG Chun-hong1，REN Yao-peng1，YAO Xi-yan2

(1.Department of Computer Science and Technology,Yuncheng University,Yuncheng 044000,China;2.Department of Math,Yuncheng University,Yuncheng 044000,China)

With the development of the distributed application system,the system form is changing from the relatively static form to the open and dynamic server mode.Among the dynamic environment,the trust mechanism based on the certificate is no longer adapted.So the problem of dynamic mechanism of information management issues.Always based on the trust chain or the broadcast way,current dynamic trust aggregation algorithm leads system operation convergence slowly and scalability badly.In this paper,an improved aggregation algorithm of dynamic trust information is proposed,which uses a aggregation method of feedback trust values to calculate the feedback trust value and adopts a method of searching trust path based on ant colony algorithm which can choose many better independence paths by a few circles,and then can obtain the final feedback trust value.The experimental results show that this algorithm has high efficiency and good scalability,and can get a reasonable feedback trust value,and prevent unites cheat behavior in a certain extent.

dynamic trust;feedback trust;ant colony algorithm;trust path

2015-06-18

2015-09-22

时间：2016-02-18

国家自然科学基金资助项目(11241005)

王春红(1965-)，女，教授，研究方向为文本处理、数据挖掘。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1634.056.html

TP393

A

1673-629X(2016)03-0117-04

10.3969/j.issn.1673-629X.2016.03.028