張　濤，馬建峰，習(xí)　寧，劉西蒙，熊金波

(1．西安電子科技大學(xué)計(jì)算機(jī)學(xué)院，陜西西安710071; 2．福建師范大學(xué)軟件學(xué)院，福建福州350108; 3．西安電子科技大學(xué)陜西省網(wǎng)絡(luò)與系統(tǒng)安全重點(diǎn)實(shí)驗(yàn)室，陜西西安710071)

?

面向服務(wù)移動(dòng)社交網(wǎng)絡(luò)中基于信任的分布式服務(wù)組合方法

張濤1，3，馬建峰1，3，習(xí)寧1，3，劉西蒙3，熊金波2

(1．西安電子科技大學(xué)計(jì)算機(jī)學(xué)院，陜西西安710071; 2．福建師范大學(xué)軟件學(xué)院，福建福州350108; 3．西安電子科技大學(xué)陜西省網(wǎng)絡(luò)與系統(tǒng)安全重點(diǎn)實(shí)驗(yàn)室，陜西西安710071)

摘要:針對(duì)服務(wù)不透明性、信任需求主觀性及移動(dòng)參與者連接機(jī)會(huì)性對(duì)面向服務(wù)移動(dòng)社交網(wǎng)絡(luò)中可信服務(wù)組合帶來的問題，提出基于信任的分布式服務(wù)組合方法．該方法基于格模型建立分布式服務(wù)信任評(píng)估框架，分別在組件和組合級(jí)評(píng)估服務(wù)信任度以避免不可信的數(shù)據(jù)傳輸;通過分析服務(wù)依賴關(guān)系，實(shí)現(xiàn)滿足全局和局部信任約束可信服務(wù)選擇;基于蒙特卡洛方法建立可信路徑選擇、優(yōu)化和容錯(cuò)算法傳輸服務(wù)評(píng)估調(diào)用信息．實(shí)驗(yàn)結(jié)果表明所提方法在服務(wù)評(píng)估開銷低，在路徑選擇成功率和信任度高，是適應(yīng)面向服務(wù)移動(dòng)社交網(wǎng)絡(luò)的服務(wù)組合方法．

關(guān)鍵詞:信任;分布式服務(wù)評(píng)估;路徑選擇;服務(wù)組合;面向服務(wù)的移動(dòng)社交網(wǎng)絡(luò)

1　引言

移動(dòng)操作系統(tǒng)的發(fā)展擴(kuò)展了基于互聯(lián)網(wǎng)的服務(wù)資源，移動(dòng)設(shè)備也從簡(jiǎn)單的通信器件演化為提供多樣服務(wù)的智能終端．除蜂窩式通信模式外，這些智能終端能夠利用短距離通信技術(shù)進(jìn)行交互［1］．移動(dòng)社交網(wǎng)絡(luò)(Mobile Social Networks，MSN)隨著移動(dòng)操作系統(tǒng)的興起而發(fā)展起來，移動(dòng)服務(wù)為手持智能終端的參與者提供交互的平臺(tái)［2～4］．面向服務(wù)的移動(dòng)社交網(wǎng)絡(luò)(Serviceoriented Mo-bile Social Networks，S-MSN)進(jìn)一步擴(kuò)展了MSN，其包含大量基于位置的應(yīng)用，能夠被臨近參與者所感知并為這些參與者提供服務(wù)．即使不存在網(wǎng)絡(luò)基礎(chǔ)設(shè)施，這些服務(wù)仍能夠通過S-MSN中參與者的社交關(guān)系快速構(gòu)建新型服務(wù)［5］．S-MSN中存在大量功能類似的服務(wù)，從而信任也是服務(wù)選擇的重要因素［6］．

概念上講，基于信譽(yù)的信任是主體對(duì)存在利益的客體交互意愿和能力的度量，同樣是對(duì)客體執(zhí)行特定行為主觀信念的描述［7］．在S-MSN中，信任機(jī)制能夠激勵(lì)合法行為并降低與未知服務(wù)交互的風(fēng)險(xiǎn)［7］．參與者也希望盡可能與可信參與者交互并遠(yuǎn)離惡意參與者．一旦大量惡意的參與者存在，信息共享將變得閉塞［8］．

然而，S-MSN中可信的服務(wù)組合十分困難［9，10］．可信服務(wù)組合問題通常假設(shè)備選集合中的服務(wù)組件能夠直接訪問［11～13］，并缺少對(duì)服務(wù)組合結(jié)構(gòu)、信任需求和網(wǎng)絡(luò)特性的考慮．因此，現(xiàn)有方案均存在局限性而難以適用于S-MSN環(huán)境．

首先，由于服務(wù)的不透明性［14，15］，用戶難以選擇完全可信的服務(wù)．大多數(shù)工作均假設(shè)備選服務(wù)為原子服務(wù)，并依據(jù)服務(wù)的評(píng)價(jià)［16，17］或?qū)Φ润w的反饋［18］計(jì)算服務(wù)的信任度．然而，網(wǎng)絡(luò)中存在大量復(fù)合服務(wù)，即便該服務(wù)可信，其仍可能由信任度較低的其它服務(wù)構(gòu)成．因此，在服務(wù)組合的過程中，需要確保數(shù)據(jù)不會(huì)傳遞到低信任度的服務(wù)組件．

其次，服務(wù)選擇時(shí)忽略了用戶和服務(wù)提供商的需求．現(xiàn)有基于信任的服務(wù)選擇機(jī)制均選擇最可信或者局部最可信的服務(wù)組件構(gòu)成復(fù)合服務(wù)，從而造成多方面問題．一方面，可信度越高的服務(wù)往往更加繁忙，其服務(wù)質(zhì)量隨之下降［19］．因此，服務(wù)組合過程中的服務(wù)選擇應(yīng)是用戶需求相關(guān)的．另一方面，服務(wù)提供商同樣希望減少與低信任度的服務(wù)進(jìn)行組合以避免某些服務(wù)較差的服務(wù)質(zhì)量造成的信譽(yù)損失［20］．所以，組合時(shí)應(yīng)按需設(shè)定服務(wù)信任度以提高服務(wù)選擇的效率．

最后，由于移動(dòng)參與者的機(jī)會(huì)連接特性，難以通過S-MSN建立信任社交路徑進(jìn)行有效的服務(wù)組合路徑．在大規(guī)模在線社交網(wǎng)絡(luò)中，源參與者到目的參與者間存在大量的信任路徑［21］．基于所建立信任路徑，社交網(wǎng)絡(luò)能夠承擔(dān)豐富的網(wǎng)絡(luò)活動(dòng)．然而在S-MSN中，機(jī)會(huì)連接特性導(dǎo)致存在信任關(guān)系多方可能無法直接通信，使得已有可信路徑選擇機(jī)制［22～25］失效而增加服務(wù)組合的困難度．此外，即使參與者之間的信任路徑已經(jīng)建立，路徑中某些節(jié)點(diǎn)的移動(dòng)或失效同樣會(huì)中斷服務(wù)組合．因此，不但需要確保路徑本身可信，而且需要建立高效的服務(wù)評(píng)估機(jī)制以提高路徑建立的成功率．

針對(duì)上述問題，本文提出一種適應(yīng)S-MSN環(huán)境的分布式服務(wù)組合方法，主要貢獻(xiàn)如下:

(1)建立服務(wù)組件信任評(píng)估方法．通過切片技術(shù)分析服務(wù)組件內(nèi)部調(diào)用關(guān)系并建立服務(wù)內(nèi)依賴集，基于格模型在組件級(jí)評(píng)估各個(gè)服務(wù)的信任度，確保數(shù)據(jù)在復(fù)合服務(wù)內(nèi)可信傳輸．

(2)建立分布式復(fù)合服務(wù)評(píng)估方法．通過分析服務(wù)間依賴關(guān)系，建立需求相關(guān)的分布式評(píng)估與選擇機(jī)制．該機(jī)制在組合級(jí)分析服務(wù)間數(shù)據(jù)流，以分布式的方式按需評(píng)估后續(xù)服務(wù)組件信任度，有效減少服務(wù)組合過程中評(píng)估開銷．

(3)建立適用于S-MSN的路徑選擇方法．社交參與者通過感知臨近參與者的信任度，基于蒙特卡洛方法建立信任路徑傳遞分布式服務(wù)評(píng)估與調(diào)用信息，確保S-MSN中可信的服務(wù)組合．

2　模型與定義

2.1網(wǎng)絡(luò)模型

S-MSN包含大量靜態(tài)的服務(wù)提供商及動(dòng)態(tài)的網(wǎng)絡(luò)參與者．服務(wù)提供商通過近距離無線通信技術(shù)為參與者提供基于位置的服務(wù)．當(dāng)所需服務(wù)距離較近時(shí)，能夠直接調(diào)用目標(biāo)服務(wù);若超出服務(wù)通信范圍，需要借助參與者轉(zhuǎn)發(fā)服務(wù)調(diào)用請(qǐng)求．S-MSN結(jié)構(gòu)如圖1所示．

定義1 S-MSN表示為〈S，P，IS，TMA〉，其中S = { s1，…，sp}為基于位置的服務(wù)節(jié)點(diǎn)集; P為參與者集合，負(fù)責(zé)轉(zhuǎn)發(fā)服務(wù)評(píng)估和調(diào)用信息; IS為全局可信目錄服務(wù)器，負(fù)責(zé)服務(wù)的功能和位置查詢; TMA為全局可信管理中心，負(fù)責(zé)生成服務(wù)信任度證書．

2.2服務(wù)模型

在數(shù)據(jù)流服務(wù)模型中，服務(wù)接收前驅(qū)服務(wù)的輸出消息，讀取本地?cái)?shù)據(jù)和服務(wù)組件進(jìn)行業(yè)務(wù)邏輯處理，存儲(chǔ)部分?jǐn)?shù)據(jù)回本地資源和服務(wù)組件并產(chǎn)生對(duì)后繼服務(wù)的消息輸出，其結(jié)構(gòu)如圖2所示．

定義2服務(wù)s =〈id，F(xiàn)，I，O，T〉，其中id為服務(wù)標(biāo)識(shí)符; F為服務(wù)功能，表示服務(wù)所執(zhí)行的業(yè)務(wù)邏輯; I為服務(wù)輸入集合; O為服務(wù)輸出集合; T為服務(wù)的信任等級(jí)．

服務(wù)s的輸入I = { IM，IC}，其中和分別表示從前驅(qū)服務(wù)和內(nèi)部組件服務(wù)的數(shù)據(jù)輸入．

服務(wù)s的輸出O = { OM，OC}，其中分別表示對(duì)后繼服務(wù)和內(nèi)部組件服務(wù)的數(shù)據(jù)輸出．

2.3服務(wù)路徑

為了建立有效的服務(wù)組合，需要借助網(wǎng)絡(luò)中的參與者共同轉(zhuǎn)發(fā)服務(wù)評(píng)估及調(diào)用信息．針對(duì)該特點(diǎn)，本文考慮一種順序的服務(wù)組合結(jié)構(gòu)——服務(wù)路徑，描述服務(wù)和參與者共同建立的服務(wù)組合關(guān)系．

定義3服務(wù)路徑SP=〈SP，In，Out〉，其中SP = 〈S0，P0，S1，P1，…，Si，Pi，…Sn〉表示服務(wù)的執(zhí)行序列，In表示執(zhí)行路徑中所有服務(wù)的輸入集合，Out表示執(zhí)行路徑中所有服務(wù)的輸出集合．在SP中，Si=〈si1，…，sim〉(m1)表示存在直接調(diào)用關(guān)系的服務(wù)序列; Pi=〈pi1，…，pik〉(k1)表示轉(zhuǎn)發(fā)服務(wù)消息的參與者序列．

2.4信任模型

2．4．1服務(wù)信任等級(jí)

服務(wù)信任度表示為離散信任模型［7，26］．該模型能夠形式化對(duì)存在依賴關(guān)系的信任度進(jìn)行表示和證明，其關(guān)系建模為信任控制模型［5］．

定義4信任控制模型定義為格(TL，≤)，其中TL為信任等級(jí)，是偏序關(guān)系≤上的有限集合．

2．4．2社交網(wǎng)絡(luò)信任度

在社交路徑中源參與者到目的參與者的信任度能夠表示為路徑中所有參與者信任度的聚合［27］．根據(jù)信任傳遞機(jī)制，聚合信任值會(huì)隨著路徑長(zhǎng)度的增加而降低．本文用分別表示參與者信任度和路徑的聚合信任值．

定義6路徑聚合信任度ρst表示從源到目的參與者信任的聚合值，其計(jì)算規(guī)則為:

建立參與者的全局信任度十分復(fù)雜．在信任度計(jì)算的過程中需要考慮社會(huì)關(guān)系、社會(huì)影響、喜好相似度、居住位置以及上下文等多種社會(huì)學(xué)因素．其建立方法已超出本文范圍，具體參閱信任度計(jì)算相關(guān)算法［28～30］．

3　基于信任的分布式服務(wù)組合

在S-MSN，可信的服務(wù)組合問題在于構(gòu)造服務(wù)路徑Sp，路徑中服務(wù)組件信任度均大于用戶指定的全局約束τu，接受數(shù)據(jù)服務(wù)組件信任度大于服務(wù)提供商指定的局部約束τ(s)，在路徑Sp中，每個(gè)服務(wù)能夠獨(dú)立評(píng)估后繼的信任度．在無法直接通信的任意服務(wù)組件序列Si和Si +1之間，構(gòu)造參與者序列Pi為傳遞分布式服務(wù)評(píng)估信息的可信路徑．方法中主要符號(hào)如表1所示．

表1　主要符號(hào)及其描述

3.1分布式服務(wù)信任級(jí)評(píng)估

服務(wù)的不透明性使得用戶無法掌握服務(wù)的內(nèi)部邏輯［19］．因此，備選服務(wù)可能為原子服務(wù)，也可能為通過服務(wù)調(diào)用關(guān)系構(gòu)造的復(fù)合服務(wù)．為了確保數(shù)據(jù)在可信的服務(wù)組件傳播，首先分析輸入與輸出數(shù)據(jù)的依賴關(guān)系．根據(jù)服務(wù)定義，服務(wù)s接收輸入s．I經(jīng)業(yè)務(wù)邏輯s．F計(jì)算后產(chǎn)生輸出s．O．s．F能夠建模為處理內(nèi)部業(yè)務(wù)邏輯的反應(yīng)系統(tǒng)［31］，其語法表示如下:

服務(wù)業(yè)務(wù)邏輯包含的活動(dòng)中，一部分與服務(wù)邏輯相關(guān)，用來控制服務(wù)功能并計(jì)算執(zhí)行結(jié)果，另一部分與數(shù)據(jù)相關(guān)，用來操作服務(wù)的輸入與輸出．本文利用程序依賴圖［32］建模s．F中的各個(gè)活動(dòng)，通過程序后向切片分析不同活動(dòng)及表達(dá)式的依賴關(guān)系，以消除服務(wù)的不透明性并評(píng)估該服務(wù)的信任等級(jí)．計(jì)算時(shí)定義服務(wù)內(nèi)依賴集Dn(o)存儲(chǔ)對(duì)象o在服務(wù)內(nèi)依賴的服務(wù)組件．基于Dn(o)，能夠計(jì)算對(duì)象o的聚合信任等級(jí)TA(o)．即u∈si．O，可得:

式(1)表示服務(wù)的聚合信任等級(jí)等于其自身信任等級(jí)及其依賴對(duì)象信任等級(jí)的最小值．簡(jiǎn)單起見，令服務(wù)si∈Dn(u)，則聚合信任等級(jí)簡(jiǎn)化為:

其中，T(si)表示服務(wù)si本身的信任等級(jí)，T(v)表示該服務(wù)內(nèi)依賴集中對(duì)象v的信任等級(jí)．

服務(wù)組合過程中，參與者不希望數(shù)據(jù)交由不可信的服務(wù)組件處理，任意組件的信任度應(yīng)大于用戶指定的信任約束τu．此外，各個(gè)服務(wù)提供者也不希望服務(wù)與其他信任度較低的服務(wù)組件進(jìn)行組合并指定信任約束τ(s)，以減少由其他服務(wù)較差信任度對(duì)其造成信譽(yù)損失．

為了表示上述約束關(guān)系，定義數(shù)據(jù)信任等級(jí)δ，表示數(shù)據(jù)在各個(gè)組件傳輸過程中應(yīng)滿足的信任等級(jí)．根據(jù)全局約束τu、局部約束τ(s)和Dn(o)，δ的計(jì)算規(guī)則如下:

上述方程表示各個(gè)服務(wù)組件的輸出信任等級(jí)滿足用戶按需指定的全局信任約束和其依賴服務(wù)組件的局部信任約束，即任何服務(wù)組件輸出的信任等級(jí)均不低于其所依賴服務(wù)組件的信任等級(jí)．因此，輸出對(duì)象的信任等級(jí)能夠簡(jiǎn)化為Dn(o)中依賴組件信任度的最大值．根據(jù)式(3)，數(shù)據(jù)約束關(guān)系計(jì)算如下:

根據(jù)式(4)，可得如下定理:

對(duì)于特定的復(fù)合服務(wù)的組件級(jí)評(píng)估，需保證高可信的數(shù)據(jù)不會(huì)傳遞到低可信度的服務(wù)組件之中．即數(shù)據(jù)依賴的服務(wù)組件中，不存在低于預(yù)設(shè)信任度的服務(wù)組件．

定義8(服務(wù)組件可信)在服務(wù)組件si中服務(wù)的信息是可信的，當(dāng)且僅當(dāng)u∈s．O，滿足

在Sp中，服務(wù)si所產(chǎn)生的輸出數(shù)據(jù)會(huì)傳遞給服務(wù)si +1．這些數(shù)據(jù)再經(jīng)過后繼服務(wù)si +2，…sj－1，并最終交給sj進(jìn)行計(jì)算．不同服務(wù)中對(duì)象的依賴關(guān)系稱為服務(wù)間依賴．對(duì)象o的服務(wù)間依賴集表示為Dt(o)，其定義如下:

定義9(服務(wù)間依賴)［33］對(duì)于數(shù)據(jù)對(duì)象u、v，存在v∈si，u∈sj(i＜j)，稱v在u的服務(wù)間依賴集Dt(u)中，當(dāng)且僅當(dāng)滿足如下條件之一:

(1) : i = j－1

基于服務(wù)間依賴關(guān)系，定義服務(wù)路徑可信如下．

定義10(服務(wù)路徑可信)在服務(wù)路徑中數(shù)據(jù)是可信的，當(dāng)且僅當(dāng)對(duì)于u∈Out，滿足

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

服務(wù)輸出數(shù)據(jù)信任度計(jì)算的獨(dú)立性保證服務(wù)路徑中已評(píng)估的服務(wù)能夠評(píng)估其后續(xù)依賴服務(wù)的信任等級(jí)．本文提出以下引理和定理證明分布式服務(wù)評(píng)估的正確性．

證明首先，令m =1，則服務(wù)路徑中存在兩個(gè)服務(wù)s0和s1．

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

情況2 j =0，v∈s0．I∧v∈Dt(u)，此時(shí)存在服務(wù)間依賴，則w1，w2，使得

從而

定理1保證

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

因此，當(dāng)m =1時(shí)，引理得證．

需要證明當(dāng)m = k時(shí)，定理成立．

情況1當(dāng)j = i，那么v∈sn．I∧v∈Dn(u)，與之前證明類似，可證δ(u)δ(v)．

從而

由定理1，可得

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

因此，當(dāng)m = k時(shí)，引理1得證．

引理2在服務(wù)路徑Sp中，若數(shù)據(jù)在前m個(gè)服務(wù)組件中是可信傳輸?shù)模敲磚∈si．O，0≤i≤m，滿足

引理2通過定義7及引理1進(jìn)行證明，證明過程與引理1類似，在此省略．

定理2(分布式可信服務(wù)評(píng)估)服務(wù)路徑Sp中，如果數(shù)據(jù)在任意服務(wù)均可信，則該服務(wù)路徑可信．

證明令m = n +1，根據(jù)引理2，定理2得證．

基于定理2，Sp中各個(gè)服務(wù)能夠分布式評(píng)估后繼服務(wù)的信任度，從而保證數(shù)據(jù)在滿足全局和局部信任級(jí)別的服務(wù)路徑中傳輸．

3.2信任路徑

在S-MSN的參與者之間相互連接，則兩個(gè)相距很遠(yuǎn)的服務(wù)能夠建立路徑轉(zhuǎn)發(fā)服務(wù)調(diào)用信息．基于社交關(guān)系所建立的圖中包含大量復(fù)雜的交互關(guān)系，在MSN中難以避免環(huán)路．為了建立一條信任路徑，需要在含環(huán)路網(wǎng)絡(luò)中提取簡(jiǎn)單(無環(huán))路徑，該問題已證明為NP完全問題［24］．此外，為了減少移動(dòng)網(wǎng)絡(luò)中的路徑失效問題，在路徑選擇時(shí)需考慮容錯(cuò)機(jī)制，該問題與移動(dòng)Ad-Hoc網(wǎng)絡(luò)中的容錯(cuò)路由具有相同屬性，同樣證明為NP完全問題［34］．

針對(duì)上述問題，提出一種能夠應(yīng)用于S-MSN的可信路徑選擇算法，用于傳遞分布式服務(wù)評(píng)估與調(diào)用信息．首先，基于蒙特卡洛方法建立M條從源服務(wù)到其所調(diào)用服務(wù)的信任路徑．其次，對(duì)于交匯路徑建立有向圖，基于Dijkstra算法建立優(yōu)化策略．最后，建立盡可能少的冗余節(jié)點(diǎn)以避免由于參與者移動(dòng)所導(dǎo)致的路徑失效．

3．2．1路徑建立

蒙特卡洛方法［35］是一種依賴隨機(jī)重復(fù)采樣來計(jì)算輸出結(jié)果的算法，主要用于無法利用確定性算法來計(jì)算精確結(jié)果的環(huán)境之中，是解決NP完全問題的主要技術(shù)手段之一．然而，直接利用蒙特卡洛方法也存在缺陷．首先，網(wǎng)絡(luò)服務(wù)池中的鄰接節(jié)點(diǎn)都會(huì)被選作候選節(jié)點(diǎn)進(jìn)行服務(wù)選擇，從而產(chǎn)生大量的候選空間;其次，每次算法模擬中，都會(huì)以特定的概率存在不優(yōu)于前一次選擇結(jié)果．

為此，本文擴(kuò)展現(xiàn)有適用于在線社交網(wǎng)絡(luò)路徑選擇的MONTE－K［36］算法到S-MSN環(huán)境．參與者獲取目標(biāo)服務(wù)位置并感知與服務(wù)同方向上的其他參與者，從中選擇信任度最高的K個(gè)參與者作為候選節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)．參與者的信任度越大，其成為最優(yōu)路徑上的節(jié)點(diǎn)的概率越大．之后，產(chǎn)生滿足均勻分布的隨機(jī)數(shù)對(duì)選擇集合中的目標(biāo)參與者以建立信任路徑．重復(fù)該過程，直到建立從源到目標(biāo)服務(wù)的信任路徑，其步驟如下:

Step 1源服務(wù)發(fā)起路徑建立請(qǐng)求并從IS獲取目標(biāo)位置．

Step 2參與者感知與服務(wù)同向的參與者并按信任度排序，并將信任度最大的至多K個(gè)參與者節(jié)點(diǎn)放入隊(duì)列MaxK(MaxK．size()≤K)中．

Step 3每個(gè)參與者節(jié)點(diǎn)的信任度為TP(pi)，則其被選擇的概率為

Step 4產(chǎn)生均勻分布隨機(jī)數(shù)rand∈［0，1］，選擇第m個(gè)節(jié)點(diǎn)Pm，使得

Step 5對(duì)Pm重復(fù)該過程，直到能夠在備選節(jié)點(diǎn)中感知到目標(biāo)服務(wù)，則從源服務(wù)到目標(biāo)服務(wù)建立一條信任路徑PT．

每個(gè)節(jié)點(diǎn)在不裁剪感知節(jié)點(diǎn)數(shù)量的前提下僅需要維護(hù)一個(gè)較小的搜索空間，從而在保證算法高效的基礎(chǔ)上以高概率找到最優(yōu)路徑．算法的時(shí)間復(fù)雜度為O(lwK)，其中l(wèi)表示從源服務(wù)到目的服務(wù)的平均路徑長(zhǎng)度，w表示節(jié)點(diǎn)所感知到的最大鄰接節(jié)點(diǎn)數(shù)目，即w = max{ adj{ ui} } (1≤i＜n－1)．K表示信任值最大的節(jié)點(diǎn)數(shù)目，即路徑中每個(gè)節(jié)點(diǎn)的搜索空間．因此，若基于蒙特卡洛方法建立多條路徑，則算法復(fù)雜度為O(lwKM)，其中M表示算法執(zhí)行次數(shù)，即建立路徑數(shù)．

3．2．2優(yōu)化策略與容錯(cuò)機(jī)制

在S-MSN中，參與者通過感知臨近參與者所建立的多條信任路徑中會(huì)存在路徑覆蓋的問題，因而MONTE－K中路徑優(yōu)化策略無法直接應(yīng)用．同時(shí)，在移動(dòng)社交網(wǎng)絡(luò)中存在由于參與者位置改變所導(dǎo)致路徑失效問題．因此，本文將對(duì)路徑中匯聚點(diǎn)記作支配點(diǎn)．通過在支配點(diǎn)處進(jìn)一步對(duì)路徑進(jìn)行局部?jī)?yōu)化，最終在網(wǎng)絡(luò)中計(jì)算出全局近似最優(yōu)路徑，其步驟如下:

Step 1從源服務(wù)到目標(biāo)服務(wù)產(chǎn)生M(M＞1)條路徑，置于備選路徑集，并計(jì)算該路徑聚合的信任度．

Step 2若各條路徑?jīng)]有交匯點(diǎn)，則聚合信任度最大的路徑作為最優(yōu)路徑，路徑選擇結(jié)束．其余M-1條路徑作為備選路徑防止路徑失效．

Step 3否則，若路徑中存在支配點(diǎn)，則對(duì)存在支配點(diǎn)的路徑構(gòu)造為有向圖，利用Dijkstra算法計(jì)算出該圖中聚合信任度最大的路徑作為備選最優(yōu)路徑．若存在非交匯路徑，則備選最優(yōu)路徑與非交匯路徑集合中的各條路徑進(jìn)行對(duì)比，選出信任值最大的路徑作為備選路徑，其余路徑作為備選路徑防止路徑失效．

Step 4若每條路徑中存在支配點(diǎn)，且不存在非交匯路徑，則首先將所有路徑構(gòu)造為有向圖并利用Dijkstra算法計(jì)算出圖中信任度最大的路徑作為最優(yōu)路徑，同時(shí)記錄各個(gè)節(jié)點(diǎn)的訪問次數(shù)．

Step 5若某節(jié)點(diǎn)訪問次數(shù)等于K，則該節(jié)點(diǎn)為關(guān)鍵點(diǎn)出現(xiàn)于每條備選路徑中．將這些節(jié)點(diǎn)存入關(guān)鍵點(diǎn)集合中找尋冗余節(jié)點(diǎn)，規(guī)則為:找該節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)，分別記錄前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)所感知的參與者節(jié)點(diǎn)集合，計(jì)算兩者的交集．若該交集非空，則從集合中找尋信任度最大的節(jié)點(diǎn)作為備選節(jié)點(diǎn);否則，該節(jié)點(diǎn)為危險(xiǎn)節(jié)點(diǎn)，其失效會(huì)導(dǎo)致路徑失效．

3.3服務(wù)組合

在S-MSN存在大量具有相同類型但實(shí)現(xiàn)方式不同的服務(wù)．為了評(píng)估服務(wù)信任度，服務(wù)請(qǐng)求者首先通過IS查詢所需服務(wù)集合，隨后逐一評(píng)估該集合中備選后繼服務(wù)sc是否滿足所需信任度約束．服務(wù)評(píng)估框架如圖3所示，其中TMA為全局可信第三方，能夠被網(wǎng)絡(luò)中所有服務(wù)感知并為其生成服務(wù)證書．服務(wù)評(píng)估主要包括兩個(gè)階段: (1)服務(wù)證書生成; (2)服務(wù)信任度評(píng)估．

服務(wù)證書生成用于生成備選服務(wù)的可信證書．在該階段，服務(wù)sc首先提交包含服務(wù)功能代碼授權(quán)請(qǐng)求，信任管理機(jī)構(gòu)能夠通過所提交代碼識(shí)別服務(wù)內(nèi)部邏輯關(guān)系并計(jì)算服務(wù)信任級(jí)別．服務(wù)證書授權(quán)通過離線模式進(jìn)行以減少評(píng)估開銷．若服務(wù)實(shí)現(xiàn)方式改變(如增加功能、替換服務(wù)組件)則重新交由服務(wù)提供商進(jìn)行授權(quán)并生成新的服務(wù)證書．

信任度評(píng)估主要評(píng)估備選服務(wù)信任度是否滿足全局與局部信任約束．在該階段中，首先根據(jù)服務(wù)證書計(jì)算目標(biāo)服務(wù)聚合信任等級(jí)．對(duì)于滿足信任度需求的服務(wù)，可以通過直接調(diào)用或者社交信任路徑傳遞服務(wù)調(diào)用信息．分布式信任度評(píng)估能夠基于評(píng)估信息獨(dú)立進(jìn)行后續(xù)服務(wù)評(píng)估，有效減少由于機(jī)會(huì)網(wǎng)絡(luò)所帶來的評(píng)估中斷．基于服務(wù)聚合信任度和數(shù)據(jù)信任度，滿足定理2的分布式評(píng)估規(guī)則如下:

在服務(wù)組合過程中，組合者需要評(píng)估大量的備選來發(fā)現(xiàn)合適的服務(wù)集合．在需要n個(gè)服務(wù)實(shí)現(xiàn)業(yè)務(wù)邏輯且每個(gè)服務(wù)存在n＇個(gè)備選服務(wù)時(shí)，最差情況下需評(píng)估O (nn＇)個(gè)候選結(jié)果．同時(shí)，在社交網(wǎng)絡(luò)中，路徑的信任度隨著參與者數(shù)目的增多而降低，若服務(wù)間轉(zhuǎn)發(fā)消息的路徑過長(zhǎng)，這條路徑的聚合信任度下降很快．

針對(duì)上述問題，若服務(wù)對(duì)〈si，si +1〉無法評(píng)估通過，則在備選集合中排除所有包含該服務(wù)對(duì)的備選服務(wù)組合項(xiàng)以減少服務(wù)評(píng)估開銷．同時(shí)，根據(jù)服務(wù)位置計(jì)算備選服務(wù)間平均距離，距離越短則負(fù)責(zé)轉(zhuǎn)發(fā)服務(wù)調(diào)用信息的路徑信任度越高．算法流程如下．

本文中假設(shè)IS提供可信的服務(wù)位置信息．若IS提供不可信的服務(wù)信息或者服務(wù)沒有及時(shí)更改注冊(cè)信息，會(huì)導(dǎo)致在建立社交路徑后無法在預(yù)定位置查找到目標(biāo)服務(wù)，此時(shí)則排除所有包含該服務(wù)的備選集．

4　實(shí)驗(yàn)與分析

服務(wù)組合包括分布式服務(wù)評(píng)估與信任路徑選擇兩部分．本節(jié)分別對(duì)這兩部分進(jìn)行仿真分析，仿真環(huán)境如表2所示．

在分布式服務(wù)評(píng)估中，每個(gè)服務(wù)評(píng)估路徑中后續(xù)服務(wù)的信任級(jí)別是否滿足約束．為了對(duì)比實(shí)驗(yàn)效果，在相同環(huán)境中實(shí)現(xiàn)集中式評(píng)估方式，其服務(wù)信任等級(jí)由服務(wù)發(fā)起者進(jìn)行評(píng)估．服務(wù)評(píng)估仿真中，數(shù)據(jù)與服務(wù)的信任級(jí)別設(shè)定為不可信(Untrustworthy，UT)，低可信(Low Trustworthy，LT)，可信(Normal Trustworthy，NT)與高可信(High Trustworthy，HT)四個(gè)等級(jí)，是滿足定義4信任控制模型上的偏序關(guān)系．

表2　仿真配置環(huán)境

在路徑選擇實(shí)驗(yàn)中，對(duì)S-MSN中選取不同距離的目標(biāo)服務(wù)進(jìn)行實(shí)驗(yàn)分析，分別測(cè)試移動(dòng)社交網(wǎng)絡(luò)中路徑建立成功率及聚合信任度．通信范圍r = 10，源服務(wù)坐標(biāo)設(shè)置為(0，0)，目的服務(wù)坐標(biāo)選取(x = 10a，y = 10b)，其中a，b為整數(shù)且不同時(shí)為0．這樣，能夠?qū)淖疃掏ㄐ啪嚯x10(目標(biāo)服務(wù)坐標(biāo)(0，10)或(10，0) )到最長(zhǎng)通信距離141．4(目標(biāo)服務(wù)坐標(biāo)(100，100) )之間結(jié)果進(jìn)行對(duì)比．在S-MSN中生成滿足均勻分布的參與者信任度，參與者數(shù)量和最大隨機(jī)游走步長(zhǎng)在下節(jié)中詳述．

4.1實(shí)驗(yàn)結(jié)果與分析

4．1．1服務(wù)評(píng)估

圖4描述集中式和分布式評(píng)估中對(duì)服務(wù)請(qǐng)求節(jié)點(diǎn)的評(píng)估時(shí)間．在集中式評(píng)估中，服務(wù)評(píng)估時(shí)間隨著路徑的增長(zhǎng)而明顯增加．這是由于隨著評(píng)估數(shù)量的增加，請(qǐng)求節(jié)點(diǎn)的時(shí)間開銷會(huì)隨著路徑長(zhǎng)度的增加而呈指數(shù)增長(zhǎng)．而本文分布式評(píng)估方法中，每個(gè)服務(wù)節(jié)點(diǎn)負(fù)責(zé)評(píng)估下一跳服務(wù)節(jié)點(diǎn)，各個(gè)節(jié)點(diǎn)的評(píng)估時(shí)間并不會(huì)由于路徑長(zhǎng)度的增長(zhǎng)而顯著增長(zhǎng)．

圖5描述集中式和分布式評(píng)估中服務(wù)請(qǐng)求節(jié)點(diǎn)的通信開銷．圖5能夠看出，集中式評(píng)估方式評(píng)估開銷明顯大于分布式所需的評(píng)估開銷．這是由于集中式評(píng)估時(shí)，請(qǐng)求節(jié)點(diǎn)需要集中評(píng)估路徑中每個(gè)服務(wù)的信任等級(jí)，而分布式評(píng)估方式，每個(gè)服務(wù)僅需要評(píng)估下一跳服務(wù)的信任等級(jí)并傳輸數(shù)據(jù)到滿足信任等級(jí)的服務(wù)之中．實(shí)驗(yàn)分析可得，文中分布式評(píng)估方法能夠有效減少計(jì)算時(shí)間及通信開銷，降低機(jī)會(huì)連接的路徑失效問題，更適應(yīng)于半可信的移動(dòng)社交網(wǎng)絡(luò)環(huán)境．

4．1．2路徑建立

本節(jié)對(duì)S-MSN中路徑建立的成功率、聚合信任度進(jìn)行對(duì)比分析．在每組實(shí)驗(yàn)中，每個(gè)節(jié)點(diǎn)感知臨近5個(gè)參與者(K =5)．在源服務(wù)到目的服務(wù)間分別建立5條(M =5) 和10條(M =10)路徑進(jìn)行對(duì)比分析．每組實(shí)驗(yàn)中分別在特定最大游走步長(zhǎng)(1，3)的條件下，對(duì)比不同參與者數(shù)目(n =400，n =800)對(duì)成功率及聚合信任度的影響．

圖6和圖7分別表示不同條件下的信任路徑建立成功率的實(shí)驗(yàn)結(jié)果．圖6表示在源服務(wù)和目的服務(wù)之間建立5條(M =5)信任路徑的成功率，其中實(shí)線和虛線分別表示參與者數(shù)目為400和800的情況．從圖6中可得，隨著參與者的增多，路徑建立的成功率也會(huì)升高．同時(shí)，參與者移動(dòng)步長(zhǎng)的增加也會(huì)降低路徑成功率．圖7表示在源服務(wù)和目的服務(wù)之間建立10條(M = 10)信任路徑的成功率情況．從圖7中能夠看出，隨著路徑數(shù)量的增加會(huì)導(dǎo)致成功率也會(huì)大幅增加．這是由于隨著路徑數(shù)目的增長(zhǎng)，由于路徑中某些節(jié)點(diǎn)失去連接的概率便會(huì)降低，從而保證路徑的有效性．因此，在實(shí)際應(yīng)用中，根據(jù)實(shí)際網(wǎng)絡(luò)規(guī)模在較小的時(shí)間復(fù)雜度下設(shè)定路徑數(shù)目以建立高成功率的社交路徑．

圖8和圖9分別表示不同條件下的路徑聚合信任度的實(shí)驗(yàn)結(jié)果．本方案在所建立的聚合信任度與直接利用蒙特卡洛方法的信任度進(jìn)行對(duì)比．圖中實(shí)線和虛線分別表示參與者數(shù)目為400和800的情況．黑線表示本方案在隨機(jī)游走狀態(tài)下的聚合信任值，而灰線表示利用蒙特卡洛方法在相同隨機(jī)游走狀態(tài)的聚合信任值．從圖8中能夠看出，即便在移動(dòng)的情況下，本方案所建立聚合信任度同樣大于蒙特卡洛方法的聚合信任值．同時(shí)，隨著移動(dòng)步長(zhǎng)的增加，本方案與蒙特卡洛方法的路徑聚合信任值差距縮小．從圖9中能夠看出，當(dāng)建立更多的路徑時(shí)，路徑聚合信任值的降低幅度低于路徑較少的情況．這是由于當(dāng)路徑更多時(shí)，能夠選擇的優(yōu)化與冗余節(jié)點(diǎn)更多，避免了聚合信任度快速下降．最后，結(jié)合成功率和聚合信任度能夠得出，路徑成功率的增長(zhǎng)并不會(huì)導(dǎo)致信任度的降低．實(shí)驗(yàn)分析可得，本文方法在路徑建立時(shí)成功率和信任度高，能夠較好適應(yīng)于移動(dòng)社交網(wǎng)絡(luò)．

5　總結(jié)

本文提出適用于S-MSN的服務(wù)組合方法．通過服務(wù)內(nèi)和服務(wù)間依賴集并建立基于格模型信任控制模型與分布式服務(wù)評(píng)估方法，在組件級(jí)和組合級(jí)進(jìn)行服務(wù)評(píng)估保證數(shù)據(jù)均傳輸于滿足按需設(shè)定信任等級(jí)的服務(wù)組件之中．同時(shí)，在無法與目標(biāo)服務(wù)直接通信時(shí)，基于蒙特卡洛方法及其優(yōu)化方法建立社交信任路經(jīng)實(shí)現(xiàn)分布式服務(wù)評(píng)估和組合．在描述服務(wù)組合方法流程的基礎(chǔ)上，通過模擬數(shù)據(jù)進(jìn)行大量仿真驗(yàn)證所提方法的合理性和有效性．實(shí)驗(yàn)結(jié)果表明本文方法在服務(wù)驗(yàn)證時(shí)開銷小，路徑建立時(shí)成功率及信任度高，是適應(yīng)S-MSN的服務(wù)組合方法．

參考文獻(xiàn)

［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服務(wù)選擇中信譽(yù)度評(píng)估方法［J］．軟件學(xué)報(bào)，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］王勇，代桂平，侯亞榮．信任感知的組合服務(wù)動(dòng)態(tài)選擇方法［J］．計(jì)算機(jī)學(xué)報(bào)，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］喬秀全，楊春，李曉峰，等．社交網(wǎng)絡(luò)服務(wù)中一種基于用戶上下文的信任度計(jì)算方法［J］．計(jì)算機(jī)學(xué)報(bào)，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］王剛，桂小林．社會(huì)網(wǎng)絡(luò)中交易節(jié)點(diǎn)的選取及其信任關(guān)系計(jì)算方法［J］．計(jì)算機(jī)學(xué)報(bào)，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月出生于陜西省西安市．博士生，主要研究方向?yàn)榉?wù)計(jì)算、可信計(jì)算、社交網(wǎng)絡(luò)．

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

馬建峰(通信作者)男，1963年10月出生于陜西省西安市．博士，西安電子科技大學(xué)計(jì)算機(jī)學(xué)院黨委書記、教授、博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)與信息安全．

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，F(xiàn)ujian Normal University，F(xiàn)uzhou，F(xiàn)ujian 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

作者簡(jiǎn)介

基金項(xiàng)目:國(guó)家自然科學(xué)基金重點(diǎn)資助項(xiàng)目(No．U1405255，No．U1135002) ;國(guó)家自然科學(xué)基金(No．61370078) ;國(guó)家科技部重大專項(xiàng)(No．2011ZX03005-002)

收稿日期:2014-07-28;修回日期: 2014-12-19;責(zé)任編輯:馬蘭英

DOI:電子學(xué)報(bào)URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．003

中圖分類號(hào):TP309

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):0372-2112 (2016) 02-0258-10