张　涛，马建峰，习　宁，刘西蒙，熊金波

(1．西安电子科技大学计算机学院，陕西西安710071; 2．福建师范大学软件学院，福建福州350108; 3．西安电子科技大学陕西省网络与系统安全重点实验室，陕西西安710071)



面向服务移动社交网络中基于信任的分布式服务组合方法

张涛1，3，马建峰1，3，习宁1，3，刘西蒙3，熊金波2

(1．西安电子科技大学计算机学院，陕西西安710071; 2．福建师范大学软件学院，福建福州350108; 3．西安电子科技大学陕西省网络与系统安全重点实验室，陕西西安710071)

摘要:针对服务不透明性、信任需求主观性及移动参与者连接机会性对面向服务移动社交网络中可信服务组合带来的问题，提出基于信任的分布式服务组合方法．该方法基于格模型建立分布式服务信任评估框架，分别在组件和组合级评估服务信任度以避免不可信的数据传输;通过分析服务依赖关系，实现满足全局和局部信任约束可信服务选择;基于蒙特卡洛方法建立可信路径选择、优化和容错算法传输服务评估调用信息．实验结果表明所提方法在服务评估开销低，在路径选择成功率和信任度高，是适应面向服务移动社交网络的服务组合方法．

关键词:信任;分布式服务评估;路径选择;服务组合;面向服务的移动社交网络

1　引言

移动操作系统的发展扩展了基于互联网的服务资源，移动设备也从简单的通信器件演化为提供多样服务的智能终端．除蜂窝式通信模式外，这些智能终端能够利用短距离通信技术进行交互［1］．移动社交网络(Mobile Social Networks，MSN)随着移动操作系统的兴起而发展起来，移动服务为手持智能终端的参与者提供交互的平台［2～4］．面向服务的移动社交网络(Serviceoriented Mo-bile Social Networks，S-MSN)进一步扩展了MSN，其包含大量基于位置的应用，能够被临近参与者所感知并为这些参与者提供服务．即使不存在网络基础设施，这些服务仍能够通过S-MSN中参与者的社交关系快速构建新型服务［5］．S-MSN中存在大量功能类似的服务，从而信任也是服务选择的重要因素［6］．

概念上讲，基于信誉的信任是主体对存在利益的客体交互意愿和能力的度量，同样是对客体执行特定行为主观信念的描述［7］．在S-MSN中，信任机制能够激励合法行为并降低与未知服务交互的风险［7］．参与者也希望尽可能与可信参与者交互并远离恶意参与者．一旦大量恶意的参与者存在，信息共享将变得闭塞［8］．

然而，S-MSN中可信的服务组合十分困难［9，10］．可信服务组合问题通常假设备选集合中的服务组件能够直接访问［11～13］，并缺少对服务组合结构、信任需求和网络特性的考虑．因此，现有方案均存在局限性而难以适用于S-MSN环境．

首先，由于服务的不透明性［14，15］，用户难以选择完全可信的服务．大多数工作均假设备选服务为原子服务，并依据服务的评价［16，17］或对等体的反馈［18］计算服务的信任度．然而，网络中存在大量复合服务，即便该服务可信，其仍可能由信任度较低的其它服务构成．因此，在服务组合的过程中，需要确保数据不会传递到低信任度的服务组件．

其次，服务选择时忽略了用户和服务提供商的需求．现有基于信任的服务选择机制均选择最可信或者局部最可信的服务组件构成复合服务，从而造成多方面问题．一方面，可信度越高的服务往往更加繁忙，其服务质量随之下降［19］．因此，服务组合过程中的服务选择应是用户需求相关的．另一方面，服务提供商同样希望减少与低信任度的服务进行组合以避免某些服务较差的服务质量造成的信誉损失［20］．所以，组合时应按需设定服务信任度以提高服务选择的效率．

最后，由于移动参与者的机会连接特性，难以通过S-MSN建立信任社交路径进行有效的服务组合路径．在大规模在线社交网络中，源参与者到目的参与者间存在大量的信任路径［21］．基于所建立信任路径，社交网络能够承担丰富的网络活动．然而在S-MSN中，机会连接特性导致存在信任关系多方可能无法直接通信，使得已有可信路径选择机制［22～25］失效而增加服务组合的困难度．此外，即使参与者之间的信任路径已经建立，路径中某些节点的移动或失效同样会中断服务组合．因此，不但需要确保路径本身可信，而且需要建立高效的服务评估机制以提高路径建立的成功率．

针对上述问题，本文提出一种适应S-MSN环境的分布式服务组合方法，主要贡献如下:

(1)建立服务组件信任评估方法．通过切片技术分析服务组件内部调用关系并建立服务内依赖集，基于格模型在组件级评估各个服务的信任度，确保数据在复合服务内可信传输．

(2)建立分布式复合服务评估方法．通过分析服务间依赖关系，建立需求相关的分布式评估与选择机制．该机制在组合级分析服务间数据流，以分布式的方式按需评估后续服务组件信任度，有效减少服务组合过程中评估开销．

(3)建立适用于S-MSN的路径选择方法．社交参与者通过感知临近参与者的信任度，基于蒙特卡洛方法建立信任路径传递分布式服务评估与调用信息，确保S-MSN中可信的服务组合．

2　模型与定义

2.1网络模型

S-MSN包含大量静态的服务提供商及动态的网络参与者．服务提供商通过近距离无线通信技术为参与者提供基于位置的服务．当所需服务距离较近时，能够直接调用目标服务;若超出服务通信范围，需要借助参与者转发服务调用请求．S-MSN结构如图1所示．

定义1 S-MSN表示为〈S，P，IS，TMA〉，其中S = { s1，…，sp}为基于位置的服务节点集; P为参与者集合，负责转发服务评估和调用信息; IS为全局可信目录服务器，负责服务的功能和位置查询; TMA为全局可信管理中心，负责生成服务信任度证书．

2.2服务模型

在数据流服务模型中，服务接收前驱服务的输出消息，读取本地数据和服务组件进行业务逻辑处理，存储部分数据回本地资源和服务组件并产生对后继服务的消息输出，其结构如图2所示．

定义2服务s =〈id，F，I，O，T〉，其中id为服务标识符; F为服务功能，表示服务所执行的业务逻辑; I为服务输入集合; O为服务输出集合; T为服务的信任等级．

服务s的输入I = { IM，IC}，其中和分别表示从前驱服务和内部组件服务的数据输入．

服务s的输出O = { OM，OC}，其中分别表示对后继服务和内部组件服务的数据输出．

2.3服务路径

为了建立有效的服务组合，需要借助网络中的参与者共同转发服务评估及调用信息．针对该特点，本文考虑一种顺序的服务组合结构——服务路径，描述服务和参与者共同建立的服务组合关系．

定义3服务路径SP=〈SP，In，Out〉，其中SP = 〈S0，P0，S1，P1，…，Si，Pi，…Sn〉表示服务的执行序列，In表示执行路径中所有服务的输入集合，Out表示执行路径中所有服务的输出集合．在SP中，Si=〈si1，…，sim〉(m1)表示存在直接调用关系的服务序列; Pi=〈pi1，…，pik〉(k1)表示转发服务消息的参与者序列．

2.4信任模型

2．4．1服务信任等级

服务信任度表示为离散信任模型［7，26］．该模型能够形式化对存在依赖关系的信任度进行表示和证明，其关系建模为信任控制模型［5］．

定义4信任控制模型定义为格(TL，≤)，其中TL为信任等级，是偏序关系≤上的有限集合．

2．4．2社交网络信任度

在社交路径中源参与者到目的参与者的信任度能够表示为路径中所有参与者信任度的聚合［27］．根据信任传递机制，聚合信任值会随着路径长度的增加而降低．本文用分别表示参与者信任度和路径的聚合信任值．

定义6路径聚合信任度ρst表示从源到目的参与者信任的聚合值，其计算规则为:

建立参与者的全局信任度十分复杂．在信任度计算的过程中需要考虑社会关系、社会影响、喜好相似度、居住位置以及上下文等多种社会学因素．其建立方法已超出本文范围，具体参阅信任度计算相关算法［28～30］．

3　基于信任的分布式服务组合

在S-MSN，可信的服务组合问题在于构造服务路径Sp，路径中服务组件信任度均大于用户指定的全局约束τu，接受数据服务组件信任度大于服务提供商指定的局部约束τ(s)，在路径Sp中，每个服务能够独立评估后继的信任度．在无法直接通信的任意服务组件序列Si和Si +1之间，构造参与者序列Pi为传递分布式服务评估信息的可信路径．方法中主要符号如表1所示．

表1　主要符号及其描述

3.1分布式服务信任级评估

服务的不透明性使得用户无法掌握服务的内部逻辑［19］．因此，备选服务可能为原子服务，也可能为通过服务调用关系构造的复合服务．为了确保数据在可信的服务组件传播，首先分析输入与输出数据的依赖关系．根据服务定义，服务s接收输入s．I经业务逻辑s．F计算后产生输出s．O．s．F能够建模为处理内部业务逻辑的反应系统［31］，其语法表示如下:

服务业务逻辑包含的活动中，一部分与服务逻辑相关，用来控制服务功能并计算执行结果，另一部分与数据相关，用来操作服务的输入与输出．本文利用程序依赖图［32］建模s．F中的各个活动，通过程序后向切片分析不同活动及表达式的依赖关系，以消除服务的不透明性并评估该服务的信任等级．计算时定义服务内依赖集Dn(o)存储对象o在服务内依赖的服务组件．基于Dn(o)，能够计算对象o的聚合信任等级TA(o)．即u∈si．O，可得:

式(1)表示服务的聚合信任等级等于其自身信任等级及其依赖对象信任等级的最小值．简单起见，令服务si∈Dn(u)，则聚合信任等级简化为:

其中，T(si)表示服务si本身的信任等级，T(v)表示该服务内依赖集中对象v的信任等级．

服务组合过程中，参与者不希望数据交由不可信的服务组件处理，任意组件的信任度应大于用户指定的信任约束τu．此外，各个服务提供者也不希望服务与其他信任度较低的服务组件进行组合并指定信任约束τ(s)，以减少由其他服务较差信任度对其造成信誉损失．

为了表示上述约束关系，定义数据信任等级δ，表示数据在各个组件传输过程中应满足的信任等级．根据全局约束τu、局部约束τ(s)和Dn(o)，δ的计算规则如下:

上述方程表示各个服务组件的输出信任等级满足用户按需指定的全局信任约束和其依赖服务组件的局部信任约束，即任何服务组件输出的信任等级均不低于其所依赖服务组件的信任等级．因此，输出对象的信任等级能够简化为Dn(o)中依赖组件信任度的最大值．根据式(3)，数据约束关系计算如下:

根据式(4)，可得如下定理:

对于特定的复合服务的组件级评估，需保证高可信的数据不会传递到低可信度的服务组件之中．即数据依赖的服务组件中，不存在低于预设信任度的服务组件．

定义8(服务组件可信)在服务组件si中服务的信息是可信的，当且仅当u∈s．O，满足

在Sp中，服务si所产生的输出数据会传递给服务si +1．这些数据再经过后继服务si +2，…sj－1，并最终交给sj进行计算．不同服务中对象的依赖关系称为服务间依赖．对象o的服务间依赖集表示为Dt(o)，其定义如下:

定义9(服务间依赖)［33］对于数据对象u、v，存在v∈si，u∈sj(i＜j)，称v在u的服务间依赖集Dt(u)中，当且仅当满足如下条件之一:

(1) : i = j－1

基于服务间依赖关系，定义服务路径可信如下．

定义10(服务路径可信)在服务路径中数据是可信的，当且仅当对于u∈Out，满足

其中，v∈In∧(v∈Dn(u)∨v∈Dt(u) )．

服务输出数据信任度计算的独立性保证服务路径中已评估的服务能够评估其后续依赖服务的信任等级．本文提出以下引理和定理证明分布式服务评估的正确性．

证明首先，令m =1，则服务路径中存在两个服务s0和s1．

情况1 j =1，v∈s1．I∧v∈Dn(u)，定理1保证δ(u)δ(v)．

情况2 j =0，v∈s0．I∧v∈Dt(u)，此时存在服务间依赖，则w1，w2，使得

从而

定理1保证

由式(8)、式(9)和式(10)，可得

因此，当m =1时，引理得证．

需要证明当m = k时，定理成立．

情况1当j = i，那么v∈sn．I∧v∈Dn(u)，与之前证明类似，可证δ(u)δ(v)．

从而

由定理1，可得

由等式(11)、(12)和(13)，可得:

因此，当m = k时，引理1得证．

引理2在服务路径Sp中，若数据在前m个服务组件中是可信传输的，那么u∈si．O，0≤i≤m，满足

引理2通过定义7及引理1进行证明，证明过程与引理1类似，在此省略．

定理2(分布式可信服务评估)服务路径Sp中，如果数据在任意服务均可信，则该服务路径可信．

证明令m = n +1，根据引理2，定理2得证．

基于定理2，Sp中各个服务能够分布式评估后继服务的信任度，从而保证数据在满足全局和局部信任级别的服务路径中传输．

3.2信任路径

在S-MSN的参与者之间相互连接，则两个相距很远的服务能够建立路径转发服务调用信息．基于社交关系所建立的图中包含大量复杂的交互关系，在MSN中难以避免环路．为了建立一条信任路径，需要在含环路网络中提取简单(无环)路径，该问题已证明为NP完全问题［24］．此外，为了减少移动网络中的路径失效问题，在路径选择时需考虑容错机制，该问题与移动Ad-Hoc网络中的容错路由具有相同属性，同样证明为NP完全问题［34］．

针对上述问题，提出一种能够应用于S-MSN的可信路径选择算法，用于传递分布式服务评估与调用信息．首先，基于蒙特卡洛方法建立M条从源服务到其所调用服务的信任路径．其次，对于交汇路径建立有向图，基于Dijkstra算法建立优化策略．最后，建立尽可能少的冗余节点以避免由于参与者移动所导致的路径失效．

3．2．1路径建立

蒙特卡洛方法［35］是一种依赖随机重复采样来计算输出结果的算法，主要用于无法利用确定性算法来计算精确结果的环境之中，是解决NP完全问题的主要技术手段之一．然而，直接利用蒙特卡洛方法也存在缺陷．首先，网络服务池中的邻接节点都会被选作候选节点进行服务选择，从而产生大量的候选空间;其次，每次算法模拟中，都会以特定的概率存在不优于前一次选择结果．

为此，本文扩展现有适用于在线社交网络路径选择的MONTE－K［36］算法到S-MSN环境．参与者获取目标服务位置并感知与服务同方向上的其他参与者，从中选择信任度最高的K个参与者作为候选节点转发数据．参与者的信任度越大，其成为最优路径上的节点的概率越大．之后，产生满足均匀分布的随机数对选择集合中的目标参与者以建立信任路径．重复该过程，直到建立从源到目标服务的信任路径，其步骤如下:

Step 1源服务发起路径建立请求并从IS获取目标位置．

Step 2参与者感知与服务同向的参与者并按信任度排序，并将信任度最大的至多K个参与者节点放入队列MaxK(MaxK．size()≤K)中．

Step 3每个参与者节点的信任度为TP(pi)，则其被选择的概率为

Step 4产生均匀分布随机数rand∈［0，1］，选择第m个节点Pm，使得

Step 5对Pm重复该过程，直到能够在备选节点中感知到目标服务，则从源服务到目标服务建立一条信任路径PT．

每个节点在不裁剪感知节点数量的前提下仅需要维护一个较小的搜索空间，从而在保证算法高效的基础上以高概率找到最优路径．算法的时间复杂度为O(lwK)，其中l表示从源服务到目的服务的平均路径长度，w表示节点所感知到的最大邻接节点数目，即w = max{ adj{ ui} } (1≤i＜n－1)．K表示信任值最大的节点数目，即路径中每个节点的搜索空间．因此，若基于蒙特卡洛方法建立多条路径，则算法复杂度为O(lwKM)，其中M表示算法执行次数，即建立路径数．

3．2．2优化策略与容错机制

在S-MSN中，参与者通过感知临近参与者所建立的多条信任路径中会存在路径覆盖的问题，因而MONTE－K中路径优化策略无法直接应用．同时，在移动社交网络中存在由于参与者位置改变所导致路径失效问题．因此，本文将对路径中汇聚点记作支配点．通过在支配点处进一步对路径进行局部优化，最终在网络中计算出全局近似最优路径，其步骤如下:

Step 1从源服务到目标服务产生M(M＞1)条路径，置于备选路径集，并计算该路径聚合的信任度．

Step 2若各条路径没有交汇点，则聚合信任度最大的路径作为最优路径，路径选择结束．其余M-1条路径作为备选路径防止路径失效．

Step 3否则，若路径中存在支配点，则对存在支配点的路径构造为有向图，利用Dijkstra算法计算出该图中聚合信任度最大的路径作为备选最优路径．若存在非交汇路径，则备选最优路径与非交汇路径集合中的各条路径进行对比，选出信任值最大的路径作为备选路径，其余路径作为备选路径防止路径失效．

Step 4若每条路径中存在支配点，且不存在非交汇路径，则首先将所有路径构造为有向图并利用Dijkstra算法计算出图中信任度最大的路径作为最优路径，同时记录各个节点的访问次数．

Step 5若某节点访问次数等于K，则该节点为关键点出现于每条备选路径中．将这些节点存入关键点集合中找寻冗余节点，规则为:找该节点的前驱和后继节点，分别记录前驱节点和后继节点所感知的参与者节点集合，计算两者的交集．若该交集非空，则从集合中找寻信任度最大的节点作为备选节点;否则，该节点为危险节点，其失效会导致路径失效．

3.3服务组合

在S-MSN存在大量具有相同类型但实现方式不同的服务．为了评估服务信任度，服务请求者首先通过IS查询所需服务集合，随后逐一评估该集合中备选后继服务sc是否满足所需信任度约束．服务评估框架如图3所示，其中TMA为全局可信第三方，能够被网络中所有服务感知并为其生成服务证书．服务评估主要包括两个阶段: (1)服务证书生成; (2)服务信任度评估．

服务证书生成用于生成备选服务的可信证书．在该阶段，服务sc首先提交包含服务功能代码授权请求，信任管理机构能够通过所提交代码识别服务内部逻辑关系并计算服务信任级别．服务证书授权通过离线模式进行以减少评估开销．若服务实现方式改变(如增加功能、替换服务组件)则重新交由服务提供商进行授权并生成新的服务证书．

信任度评估主要评估备选服务信任度是否满足全局与局部信任约束．在该阶段中，首先根据服务证书计算目标服务聚合信任等级．对于满足信任度需求的服务，可以通过直接调用或者社交信任路径传递服务调用信息．分布式信任度评估能够基于评估信息独立进行后续服务评估，有效减少由于机会网络所带来的评估中断．基于服务聚合信任度和数据信任度，满足定理2的分布式评估规则如下:

在服务组合过程中，组合者需要评估大量的备选来发现合适的服务集合．在需要n个服务实现业务逻辑且每个服务存在n＇个备选服务时，最差情况下需评估O (nn＇)个候选结果．同时，在社交网络中，路径的信任度随着参与者数目的增多而降低，若服务间转发消息的路径过长，这条路径的聚合信任度下降很快．

针对上述问题，若服务对〈si，si +1〉无法评估通过，则在备选集合中排除所有包含该服务对的备选服务组合项以减少服务评估开销．同时，根据服务位置计算备选服务间平均距离，距离越短则负责转发服务调用信息的路径信任度越高．算法流程如下．

本文中假设IS提供可信的服务位置信息．若IS提供不可信的服务信息或者服务没有及时更改注册信息，会导致在建立社交路径后无法在预定位置查找到目标服务，此时则排除所有包含该服务的备选集．

4　实验与分析

服务组合包括分布式服务评估与信任路径选择两部分．本节分别对这两部分进行仿真分析，仿真环境如表2所示．

在分布式服务评估中，每个服务评估路径中后续服务的信任级别是否满足约束．为了对比实验效果，在相同环境中实现集中式评估方式，其服务信任等级由服务发起者进行评估．服务评估仿真中，数据与服务的信任级别设定为不可信(Untrustworthy，UT)，低可信(Low Trustworthy，LT)，可信(Normal Trustworthy，NT)与高可信(High Trustworthy，HT)四个等级，是满足定义4信任控制模型上的偏序关系．

表2　仿真配置环境

在路径选择实验中，对S-MSN中选取不同距离的目标服务进行实验分析，分别测试移动社交网络中路径建立成功率及聚合信任度．通信范围r = 10，源服务坐标设置为(0，0)，目的服务坐标选取(x = 10a，y = 10b)，其中a，b为整数且不同时为0．这样，能够对从最短通信距离10(目标服务坐标(0，10)或(10，0) )到最长通信距离141．4(目标服务坐标(100，100) )之间结果进行对比．在S-MSN中生成满足均匀分布的参与者信任度，参与者数量和最大随机游走步长在下节中详述．

4.1实验结果与分析

4．1．1服务评估

图4描述集中式和分布式评估中对服务请求节点的评估时间．在集中式评估中，服务评估时间随着路径的增长而明显增加．这是由于随着评估数量的增加，请求节点的时间开销会随着路径长度的增加而呈指数增长．而本文分布式评估方法中，每个服务节点负责评估下一跳服务节点，各个节点的评估时间并不会由于路径长度的增长而显著增长．

图5描述集中式和分布式评估中服务请求节点的通信开销．图5能够看出，集中式评估方式评估开销明显大于分布式所需的评估开销．这是由于集中式评估时，请求节点需要集中评估路径中每个服务的信任等级，而分布式评估方式，每个服务仅需要评估下一跳服务的信任等级并传输数据到满足信任等级的服务之中．实验分析可得，文中分布式评估方法能够有效减少计算时间及通信开销，降低机会连接的路径失效问题，更适应于半可信的移动社交网络环境．

4．1．2路径建立

本节对S-MSN中路径建立的成功率、聚合信任度进行对比分析．在每组实验中，每个节点感知临近5个参与者(K =5)．在源服务到目的服务间分别建立5条(M =5) 和10条(M =10)路径进行对比分析．每组实验中分别在特定最大游走步长(1，3)的条件下，对比不同参与者数目(n =400，n =800)对成功率及聚合信任度的影响．

图6和图7分别表示不同条件下的信任路径建立成功率的实验结果．图6表示在源服务和目的服务之间建立5条(M =5)信任路径的成功率，其中实线和虚线分别表示参与者数目为400和800的情况．从图6中可得，随着参与者的增多，路径建立的成功率也会升高．同时，参与者移动步长的增加也会降低路径成功率．图7表示在源服务和目的服务之间建立10条(M = 10)信任路径的成功率情况．从图7中能够看出，随着路径数量的增加会导致成功率也会大幅增加．这是由于随着路径数目的增长，由于路径中某些节点失去连接的概率便会降低，从而保证路径的有效性．因此，在实际应用中，根据实际网络规模在较小的时间复杂度下设定路径数目以建立高成功率的社交路径．

图8和图9分别表示不同条件下的路径聚合信任度的实验结果．本方案在所建立的聚合信任度与直接利用蒙特卡洛方法的信任度进行对比．图中实线和虚线分别表示参与者数目为400和800的情况．黑线表示本方案在随机游走状态下的聚合信任值，而灰线表示利用蒙特卡洛方法在相同随机游走状态的聚合信任值．从图8中能够看出，即便在移动的情况下，本方案所建立聚合信任度同样大于蒙特卡洛方法的聚合信任值．同时，随着移动步长的增加，本方案与蒙特卡洛方法的路径聚合信任值差距缩小．从图9中能够看出，当建立更多的路径时，路径聚合信任值的降低幅度低于路径较少的情况．这是由于当路径更多时，能够选择的优化与冗余节点更多，避免了聚合信任度快速下降．最后，结合成功率和聚合信任度能够得出，路径成功率的增长并不会导致信任度的降低．实验分析可得，本文方法在路径建立时成功率和信任度高，能够较好适应于移动社交网络．

5　总结

本文提出适用于S-MSN的服务组合方法．通过服务内和服务间依赖集并建立基于格模型信任控制模型与分布式服务评估方法，在组件级和组合级进行服务评估保证数据均传输于满足按需设定信任等级的服务组件之中．同时，在无法与目标服务直接通信时，基于蒙特卡洛方法及其优化方法建立社交信任路经实现分布式服务评估和组合．在描述服务组合方法流程的基础上，通过模拟数据进行大量仿真验证所提方法的合理性和有效性．实验结果表明本文方法在服务验证时开销小，路径建立时成功率及信任度高，是适应S-MSN的服务组合方法．

参考文献

［1］Kyu-Han K，Min A W，Gupta D，et al．Improving energy efficiency of Wi-Fi sensing on smartphones［A］．Proceedings of 2011 IEEE INFOCOM［C］．Shanghai，China: 2011．2930－2938．

［2］Wei D，Dave V，Lili Q，et al．Secure friend discovery in mobile social networks［A］．Proceedings of 2011 IEEE INFOCOM［C］．Shanghai，China: 2011．1647－1655．

［3］Fan J，Du Y，Gao W，et al．Geography-aware active data dissemination in mobile social networks［A］．IEEE 7th International Conference on Mobile Adhoc and Sensor Systems［C］．San Francisco，CA: 2010．109－118．

［4］Liang X H，Li X D，Shen X S．Enabling trustworthy service evaluation in service-oriented mobile social networks［J］．IEEE Trans on Parallel and Distributed Systems，2014，25 (2) : 310－320．

［5］Zhang T，Ma J，Xi N，et al．Trustworthy service composition in service-oriented mobile social networks［A］．21th IEEE International Conference on Web Services［C］．Anchorage，Alaska: 2014．684－687．

［6］Vu L H，Hauswirth M，Aberer K．QoS-based service selection and ranking with trust and reputation management ［A］．Proceedings of On the Move to Meaningful Internet Systems 2005: CoopIS，DOA，and ODBASE［C］．Berlin Heidelberg: 2005．466－483．

［7］J? sang A，Ismail R，Boyd C．A survey of trust and reputation systems for online service provision［J］．Decision Support Systems，2007，43(2) : 618－644．

［8］Al-Oufi S，Kim H N，El Saddik A．A group trust metric for identifying people of trust in online social networks［J］．Expert Systems with Applications，2012，39 (18) : 13173 －13181．

［9］Noor T H，Sheng Q Z，Zeadally S，et al．Trust management of services in cloud environments: Obstacles and solutions ［J］．ACM Comput Surv，2013，46(1) : 1－30．

［10］Wang Y，Lin K J，Wong D，et al．Trust management towards service-oriented applications［J］．Service Oriented Computing and Applications，2009，3(2) : 129－146．

［11］Li L，Wang Y，Lim E P．Trust-oriented composite service selection and discovery［A］．7th International Joint Conference of Service-Oriented Computing［C］．Berlin，Heidelberg: 2009: 50－67．

［12］Hang C W，Singh M P．Trustworthy service selection and composition［J］．ACM Trans Auton Adapt Syst，2011，6 (1) : 1－17．

［13］Nepal S，Malik Z，Bouguettaya A．Reputation management for composite services in service-oriented systems［J］．International Journal of Web Services Research．2011，8 (2) : 29－52．

［14］Zhang T，Ma J，Li Q，et al．Trust-based service composition in multi-domain environments under time constraint ［J］．Science China Information Sciences，2014，57: 092109(16)．

［15］Liu Y，Ngu A H，Zeng L Z．QoS Computation and Policing in Dynamic Web Service Selection［M］．Proceedings of the 13th international World Wide Web conference on Alternate track papers＆posters．New York，NY: 2004．66 －73．

［16］Li L，Wang Y，Lim E P．Trust-oriented composite service selection with QoS constraints［J］．Journal of Universal Computer Science．2010，16(13) : 1720－1744．

［17］王尚广，孙其博，杨放春．Web服务选择中信誉度评估方法［J］．软件学报，2012，23(6) : 1350－1367．Wang S G，Sun Q B，Yang F C．Reputation evaluation approach in Web service selection［J］．Journal of Software，2012，23(6) : 1350－1367．(in Chinese)

［18］Malik Z，Bouguettaya A．RATEWeb: Reputation assessment for trust establishment among Web services［J］．The VLDB Journal，2009，18(4) : 885－911．

［19］Zhang T，Ma J，Sun C，et al．Service composition in multidomain environment under time constraint［A］．IEEE 20th International Conference on Web Services［C］．Santa Clara，CA: 2013．227－234．

［20］Nepal S，Malik Z，Bouguettaya A．Reputation propagation in composite services［A］．IEEE 7th International Conference on Web Services［C］．Los Angeles，CA: 2009．295－302．

［21］Kunegis J，Lommatzsch A，Bauckhage C．The slashdot zoo: mining a social network with negative edges［A］．Proceedings of the 18th international conference on World Wide Web［C］．Madrid，Spain: ACM．2009．741－750．

［22］Hang C W，Wang Y，Singh M P．Operators for propaga-ting trust and their evaluation in social networks［A］．Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems［C］．Budapest，Hungary: 2009: 1025－1032．

［23］Lin CY，Cao N，Liu SX，et al．SmallBlue: Social network analysis for expertise search and collective intelligence ［A］．IEEE 25th International Conference on Data Engineering［C］．Shanghai，China: 2009．1483－1486．

［24］Liu G F，Wang Y，Orgun M A．Discovering trust networks for the selection of trustworthy service providers in complex contextual social networks［A］．IEEE 19th International Conference on Web Services［C］．Honolulu，HI: 2012．384－391．

［25］Liu G F，Wang Y，Orgun M A．Finding K optimal social trust paths for the selection of trustworthy service providers in complex social networks［A］．IEEE 9th International Conference on Web Services［C］．Washington DC: 2011．41－48．

［26］Abdul-Rahman A，Hailes S．Supporting trust in virtual communities［A］．Proceedings of the 33rd Annual Hawaii International Conference on System Sciences［C］．Hawaii: 2000．1－9．

［27］Golbeck J，Hendler J．Inferring binary trust relationships in Web-based social networks［J］．ACM Trans Internet Technol，2006，6(4) : 497－529．

［28］王勇，代桂平，侯亚荣．信任感知的组合服务动态选择方法［J］．计算机学报，2009，32(8) : 1668－1675．Wang Y，Dai G P，Hou Y R．Dynamic methods of trust-aware composite service selection［J］．Chinese Journal of Computers．2009，32(8)，1668－1675．(in Chinese)

［29］乔秀全，杨春，李晓峰，等．社交网络服务中一种基于用户上下文的信任度计算方法［J］．计算机学报，2011，34 (12) : 2403－2413．Qiao X Q，Yang C，Li X F，et al．A trust calculating algorithm based on social networking service users' context ［J］．Chinese Journal of Computers 2011，34(12)，2403－2413．(in Chinese)

［30］王刚，桂小林．社会网络中交易节点的选取及其信任关系计算方法［J］．计算机学报，2013，36(2) : 368－383．Wang G，Gui X L．Selecting and trust computing for transaction nodes in online social networks［J］．Chinese Journal of Computers．2013，36(2)，368－383．(in Chinese)

［31］Xi N，Ma J，Sun C，et al．Decentralized information flow verification framework for the service chain composition in mobile computing environments［A］．IEEE 20th International Conference on Web Services［C］．Santa Clara，CA: 2013．563－570．

［32］Ferrante J，Ottenstein K J，Warren J D．The program dependence graph and its use in optimization［J］．ACM Trans Program Lang Syst，1987，9(3) : 319－349．

［33］Wei S，Yen I L，Thuraisingham B，et al．Rule-based runtime information flow control in service cloud［A］．2011 IEEE International Conference on Web Services［C］．Washington DC: 2011．524－531．

［34］Xue Y，Nahrstedt K．Fault tolerant routing in mobile ad hoc networks［A］．IEEE Wireless Communications and Networking Conference［C］．New Orleans，Louisiana: 2003．1174－1179．

［35］Gentle J E，H? rdle W K，Mori Y．Handbook of Computational Statistics: Concepts and Methods［M］．2nd edition．Springer，2012．

［36］Liu G F，Wang Y，Orgun M A．Optimal social trust path selection in complex social networks［A］．Proceedings of the 24th AAAI Conference on Artificial Intelligence［C］．Atlanta，Georgia: 2010．1397－1398．

张涛男，1986年7月出生于陕西省西安市．博士生，主要研究方向为服务计算、可信计算、社交网络．

E-mail: tzhang@ stu．xidian．edu．cn

马建峰(通信作者)男，1963年10月出生于陕西省西安市．博士，西安电子科技大学计算机学院党委书记、教授、博士生导师，主要研究方向为密码学、计算机网络与信息安全．

E-mail: jfma@ mail．xidian．edu．cn

Trust-Based Decentralized Service Composition Approach in Service-Oriented Mobile Social Networks

ZHANG Tao1，3，MA Jian-feng1，3，XI Ning1，3，LIU Xi-meng3，XIONG Jin-bo2
(1．School of Computer Science and Technology，Xidian University，Xi'an，Shaanxi 710071，China; 2．Faculty of Software，Fujian Normal University，Fuzhou，Fujian 350108，China; 3．Shaanxi Key Laboratory of Network and System Security，Xidian University，Xi'an，Shaanxi 710071，China)

Abstract:Trustworthy service composition in service-oriented mobile social networks suffers from the opaque characteristics of service components，the subjective interpretation of trust requirements，and the opportunistic connectivity of social participants．To tackle these issues，we propose a trust-based decentralized service-composition approach．The proposed approach decentralizedly evaluates the trustworthiness of target services at both component and composite levels based on a lattice-based trust model to prevent data from being transmitted to untrustworthy counterparts．Moreover，by analyzing the dependency relationships，service are selected satisfied both global and local constraints specified by service consumers and vendors respectively．Finally，based on Monte Carlo method，a trustworthy social path selection，optimization and fault-tolerant approach is developed to deliver service evaluation and invocation information．Experimental results demonstrate its practical suitability of service composition for service-oriented mobile social networks，which leads to low cost for service evaluation，as well as high success rate and aggregated trust value for path selection．

Key words:trust; decentralized service evaluation; path selection; service composition; service-oriented mobile social networks

作者简介

基金项目:国家自然科学基金重点资助项目(No．U1405255，No．U1135002) ;国家自然科学基金(No．61370078) ;国家科技部重大专项(No．2011ZX03005-002)

收稿日期:2014-07-28;修回日期: 2014-12-19;责任编辑:马兰英

DOI:电子学报URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．003

中图分类号:TP309

文献标识码:A

文章编号:0372-2112 (2016) 02-0258-10