服務(wù)組合中保障公平性的信譽(yù)傳播算法

張 濤,馬建峰,莫 若,李 琦,習(xí) 寧

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071)

?

服務(wù)組合中保障公平性的信譽(yù)傳播算法

張 濤,馬建峰,莫 若,李 琦,習(xí) 寧

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071)

摘要:在面向服務(wù)的環(huán)境中,服務(wù)的不透明性、組合結(jié)構(gòu)的復(fù)雜性以及用戶評(píng)價(jià)的主觀性使得用戶難以對(duì)組件服務(wù)進(jìn)行有效的信譽(yù)評(píng)估.針對(duì)此問(wèn)題,提出適用于服務(wù)組合的信譽(yù)傳播算法,將復(fù)合服務(wù)的信譽(yù)評(píng)估值公平地傳播到各個(gè)組件服務(wù).首先,將復(fù)合服務(wù)建模為Beta混合模型,通過(guò)最大期望算法學(xué)習(xí)復(fù)合服務(wù)中各個(gè)組件的責(zé)任及信譽(yù)度.其次,基于Shapley值的合作博弈模型計(jì)算各個(gè)組件服務(wù)對(duì)復(fù)合服務(wù)的貢獻(xiàn)度,確保所組合的各個(gè)服務(wù)不會(huì)受到額外的獎(jiǎng)勵(lì)或懲罰.最后,理論分析與實(shí)驗(yàn)結(jié)果表明該算法在保證公平性的前提下,能夠正確地將用戶提交的信譽(yù)評(píng)估層次化傳播到各個(gè)組件服務(wù).

關(guān)鍵詞:面向服務(wù)的架構(gòu);服務(wù)組合;Web服務(wù);信譽(yù)傳播;公平性

在面向服務(wù)架構(gòu)(Service-Oriented Architecture,SOA)中,服務(wù)表現(xiàn)為自治、平臺(tái)獨(dú)立的可重用計(jì)算實(shí)體,能夠以統(tǒng)一的標(biāo)準(zhǔn)進(jìn)行描述、發(fā)布、發(fā)現(xiàn)和組合,為多機(jī)構(gòu)跨平臺(tái)軟件開發(fā)提供基礎(chǔ).面向服務(wù)架構(gòu)的主要目標(biāo)是在開放的網(wǎng)絡(luò)環(huán)境中利用Web服務(wù)自動(dòng)化構(gòu)造滿足業(yè)務(wù)邏輯的復(fù)雜應(yīng)用[1].然而,開放網(wǎng)絡(luò)內(nèi)在的不確定性使用戶需要承擔(dān)未知服務(wù)交互的風(fēng)險(xiǎn).基于信譽(yù)的信任機(jī)制能夠?qū)Υ嬖诶娼换ヒ环降姆?wù)質(zhì)量(Quality of Service,QoS)進(jìn)行度量,激勵(lì)合法的服務(wù)行為,為用戶提供參考信息以降低與惡意服務(wù)交互的幾率,從而降低開放網(wǎng)絡(luò)中的交互風(fēng)險(xiǎn)[2-3].

然而,在服務(wù)組合中對(duì)組件服務(wù)的信譽(yù)評(píng)估十分困難.首先,由于服務(wù)的不透明性[4],用戶無(wú)法得知評(píng)價(jià)對(duì)象是原子服務(wù)或是復(fù)合服務(wù),從而無(wú)法全面進(jìn)行各個(gè)組件的信譽(yù)評(píng)估[5].其次,服務(wù)組合結(jié)構(gòu)的復(fù)雜性導(dǎo)致組合結(jié)構(gòu)服務(wù)質(zhì)量的多樣性,需要針對(duì)不同服務(wù)質(zhì)量特性建立不同的信譽(yù)計(jì)算規(guī)則[6].最后,即便用戶能夠掌握復(fù)合服務(wù)組合結(jié)構(gòu)及其服務(wù)質(zhì)量特性,其對(duì)各個(gè)服務(wù)組件評(píng)價(jià)的主觀性也導(dǎo)致難以實(shí)現(xiàn)組件服務(wù)信譽(yù)分配的公平性.因此,在服務(wù)組合中需要將用戶對(duì)復(fù)合服務(wù)的評(píng)估值公平傳播到所構(gòu)成該服務(wù)的各個(gè)組件.

目前對(duì)服務(wù)組合的信譽(yù)傳播問(wèn)題已有了初步研究.文獻(xiàn)[7]最先定義服務(wù)組合中公平信譽(yù)傳播需滿足如下兩規(guī)則:組件服務(wù)不應(yīng)由于其他組件較差的信譽(yù)而受到懲罰;組件服務(wù)不應(yīng)由于其他組件較好的信譽(yù)而受到獎(jiǎng)勵(lì).并提出服務(wù)組件重要性與服務(wù)質(zhì)量一致性相結(jié)合的信譽(yù)分配算法.文獻(xiàn)[8]依據(jù)服務(wù)組件歷史信譽(yù)值和服務(wù)質(zhì)量,建立補(bǔ)償函數(shù)實(shí)現(xiàn)用戶評(píng)價(jià)值分解.文獻(xiàn)[9]結(jié)合信任趨勢(shì)與信譽(yù)評(píng)估值,建立層次結(jié)構(gòu)與水平結(jié)構(gòu)的信譽(yù)傳播方法.然而,上述工作均在服務(wù)組合結(jié)構(gòu)可觀測(cè)的前提下進(jìn)行組件信譽(yù)度量,缺少對(duì)所提方案信譽(yù)傳播公平性的理論證明.此外,文獻(xiàn)[10]基于Shapley值的數(shù)學(xué)特性,提出公平保障的信譽(yù)傳播方法.其工作雖然在理論上保證了公平性,然而該方法假設(shè)服務(wù)組件服務(wù)質(zhì)量完全可觀察,并需要用戶提供對(duì)各個(gè)組件服務(wù)質(zhì)量的最佳值和最差值的數(shù)學(xué)期望,仍未解決服務(wù)不透明性所造成的信譽(yù)評(píng)估問(wèn)題.

針對(duì)上述問(wèn)題,筆者從服務(wù)組合的特征出發(fā),提出適應(yīng)于Web服務(wù)組合的公平信譽(yù)傳播算法(FGRP).首先針對(duì)服務(wù)不透明性及組合結(jié)構(gòu)特點(diǎn),將復(fù)合服務(wù)建模為Beta混合模型,利用最大期望算法學(xué)習(xí)出各個(gè)服務(wù)組件責(zé)任和信譽(yù)度.其次,基于Shapley值的合作博弈模型計(jì)算組件貢獻(xiàn)度,并依據(jù)該貢獻(xiàn)度將用戶對(duì)復(fù)合服務(wù)的主觀評(píng)價(jià)層次化分配到各個(gè)服務(wù)組件,保障信譽(yù)傳播的公平性.

1 FGRP信譽(yù)傳播算法

1.1 服務(wù)信譽(yù)表示

面向服務(wù)架構(gòu)的主要特性是利用平臺(tái)獨(dú)立的服務(wù),通過(guò)組合的方式為用戶提供增值的服務(wù).復(fù)合服務(wù)通常作為整體與用戶交互.在特定情況下(如遺產(chǎn)系統(tǒng)),服務(wù)以黑盒的方式提供給用戶,用戶難以分析其組合邏輯的依賴關(guān)系.為了評(píng)估各個(gè)組件服務(wù)對(duì)復(fù)合服務(wù)信譽(yù)的貢獻(xiàn)度,算法用Beta概率模型[11]建模所交互服務(wù)的信譽(yù)記錄.

Beta概率模型將信譽(yù)表示為二元證據(jù)模型θ=〈α,β〉(α≥0,β≥0),其中α和β分別表示滿意和未滿意的交互次數(shù).其概率密度函數(shù)表示為

服務(wù)si的信譽(yù)表示為Beta概率模型的數(shù)學(xué)期望,即

1.2 組件服務(wù)責(zé)任及信譽(yù)的統(tǒng)計(jì)學(xué)習(xí)

不透明性表示用戶無(wú)法區(qū)分所交互的服務(wù)是原子服務(wù),或是多個(gè)服務(wù)所組成的復(fù)合服務(wù),從而無(wú)法對(duì)組件服務(wù)直接進(jìn)行信譽(yù)評(píng)估.為了將復(fù)合服務(wù)的評(píng)價(jià)值公平地分配到各個(gè)組件服務(wù),在獲得復(fù)合服務(wù)信譽(yù)的觀察之后,利用有限混合模型統(tǒng)計(jì)學(xué)習(xí)出各個(gè)組件的責(zé)任和信任度,從而解決服務(wù)的不透明性.

有限混合模型將每個(gè)數(shù)據(jù)對(duì)象建模為混合分支,合并不同混合分支為描述整個(gè)數(shù)據(jù)特征的混合分布,通過(guò)統(tǒng)計(jì)實(shí)現(xiàn)數(shù)據(jù)識(shí)別.筆者用Beta混合模型建模復(fù)合服務(wù)的信譽(yù)混合.在由K個(gè)組件服務(wù)構(gòu)成的服務(wù)組合中,組件服務(wù)si建模為參數(shù)θi=〈αi,βi〉的Beta概率模型,則復(fù)合服務(wù)的Beta混合表示為

最大期望算法通過(guò)期望步(E-step,E步)和極大化步(M-Step,M步)兩過(guò)程的不斷迭代,最終收斂到似然函數(shù)的最優(yōu)解,其執(zhí)行流程如下.

重復(fù)E步和M步,直至參數(shù)θnew下對(duì)數(shù)似然函數(shù)收斂.此時(shí),參數(shù)πn ew i和θnew i分別表示當(dāng)前復(fù)合服務(wù)中組件服務(wù)si的責(zé)任和信譽(yù)度的統(tǒng)計(jì)值.

1.3 基于Shapley值的貢獻(xiàn)度計(jì)算

算法FGRP引入符號(hào)ωi,ωi∈(0,1],表示組件服務(wù)si在服務(wù)組合中執(zhí)行的概率.服務(wù)組合結(jié)構(gòu)主要包括確定組合模式(包括順序、循環(huán)、并發(fā)等)和概率組合模式兩類[4,6].在確定組合模式中,各個(gè)組件按照組合順序依次執(zhí)行,其ωi=1.在概率組合模式中,組件執(zhí)行概率表示為責(zé)任值歸一化后的比率.例如,假設(shè)服務(wù)集si,j∈{si,1,…,si,m},構(gòu)成概率模型,其責(zé)任值πi,j∈{πi,1,…,πi,m},則概率ωi,j∈{ωi,1,…,ωi,m}=πi,j/ (πi,1+…+πi,m).在得到組件服務(wù)執(zhí)行概率及證據(jù)模型后,服務(wù)組件的組合信譽(yù)值根據(jù)文獻(xiàn)[12]提出的聚合規(guī)則進(jìn)行計(jì)算.

算法FGRP依據(jù)組件服務(wù)si對(duì)復(fù)合服務(wù)的貢獻(xiàn)度Δi(c)進(jìn)行信譽(yù)傳播.為了保證公平性,算法利用合作博弈理論的Shapley值[13]計(jì)算各個(gè)組件服務(wù)si的貢獻(xiàn)Δi(c),表示為

1.4 信譽(yù)傳播

根據(jù)上述分析,算法FGRP在保障公平性的基礎(chǔ)上,能夠有效地解決由服務(wù)不透明性、組合結(jié)構(gòu)復(fù)雜性和用戶評(píng)價(jià)主觀性所造成的信譽(yù)傳播問(wèn)題,其算法流程如下:

步驟1(服務(wù)不透明性) 通過(guò)觀察值學(xué)習(xí)各個(gè)組件的責(zé)任及信譽(yù)度,見(jiàn)1.2節(jié).

步驟2(組合結(jié)構(gòu)復(fù)雜性) 根據(jù)Shapley值計(jì)算組件服務(wù)在組合結(jié)構(gòu)下對(duì)復(fù)合服務(wù)的貢獻(xiàn)度,見(jiàn)1.3節(jié).

步驟3(用戶評(píng)價(jià)主觀性) 將用戶的主觀評(píng)價(jià)根據(jù)貢獻(xiàn)度傳播到組件服務(wù)之上,見(jiàn)本節(jié)前段.若該組件仍是復(fù)合服務(wù),則轉(zhuǎn)至步驟1.

2 FGRP分析

2.1 FGRP特性分析

算法FGRP基于Shapley值進(jìn)行組件服務(wù)的信譽(yù)分配,將用戶對(duì)復(fù)合服務(wù)的主觀信譽(yù)評(píng)估公平傳播于所組成的各個(gè)服務(wù)組件.因此,算法FGRP能夠繼承Shapley值的特性.

對(duì)稱性(Symmetry) 對(duì)于?T∈c{si,sj},若R( c|T∪{si} )=R ( c|T∪{sj} ) ,則Δi(c)=Δj(c).

貢獻(xiàn)平衡性(Balanced Contribution) 對(duì)于?si,sj∈c,Δi(c)-Δi( c|c{sj} )=Δj(c)-Δj( c|c{si} ),其中Δi(c|T)表示在復(fù)合服務(wù)c的組合結(jié)構(gòu)中,組件服務(wù)si對(duì)給定子集T的貢獻(xiàn)度.平衡性確保各個(gè)組件的貢獻(xiàn)度在各個(gè)組件中能夠平均分配,從而保證服務(wù)組件的信譽(yù)傳播的公平性.

2.2 FGRP公平性分析

通過(guò)組件信任度的變化證明算法FGRP的公平性.在證明中,令Rt(s)、Rt′(s)和et(s)、et′(s)分別表示在連續(xù)等長(zhǎng)時(shí)間t、t′時(shí)組件服務(wù)s的信譽(yù)值和證據(jù)數(shù),則信譽(yù)差和證據(jù)差分別表示為ΔR(s)=Rt(s)-Rt′(s)和Δe(s)=et(s)-et′(s).首先考慮當(dāng)Δe(s)=0,ΔR(s)＞0時(shí)的信譽(yù)變化情況.對(duì)于任意的組合結(jié)構(gòu),當(dāng)單個(gè)組件信譽(yù)提升時(shí),以下命題始終成立.

命題1 組件服務(wù)si信譽(yù)值的提升不會(huì)導(dǎo)致復(fù)合服務(wù)c信譽(yù)值的下降[8],即

同時(shí),對(duì)于?sj∈c,sj≠si,ΔR(sj)=0時(shí),由式(7)可得對(duì)稱性表示若不同組件與其他組件組合時(shí)信譽(yù)度相同,則其貢獻(xiàn)度相同.

其中,ΔR(c|si)=0,表示組件服務(wù)si的信譽(yù)提升并未導(dǎo)致復(fù)合服務(wù)c的信譽(yù)提升.例如,組件服務(wù)sA和sB以概率模式組成復(fù)合服務(wù)c,并且ΔR(sA)＞0.若復(fù)合服務(wù)中sA的執(zhí)行概率較低,則存在特定時(shí)間t中未提升復(fù)合服務(wù)信譽(yù)的可能性,從而ΔR(c|sA)=0.為了表示復(fù)合服務(wù)信譽(yù)值改變,提出有效信譽(yù)提升的定義,當(dāng)信譽(yù)下降時(shí)能夠得出類似結(jié)論.

定義1(有效信譽(yù)提升) 組件服務(wù)si的有效信譽(yù)提升表示其信譽(yù)提升導(dǎo)致復(fù)合服務(wù)c的信譽(yù)提升,即

根據(jù)定義1,可得如下推論.

推論1 給定復(fù)合服務(wù)c={s1,…,sK}以及T∈c{si},若R(si)＞R(c),則

下面,考慮組件服務(wù)信譽(yù)的改變對(duì)信譽(yù)傳播配額的影響,并證明算法FGRP的公平性.

引理1 若組件服務(wù)si具有的有效信譽(yù)提升,則v(si)＞Ru.

證明 令T∈c{si},考慮如下兩種情況:

情況1 若T=?,則ΔR( c|T∪{si} )-ΔR(c|T)=ΔR( c|{si} )-ΔR(c|?)=ΔR( c|{si} )＞0;

情況2 若T≠?,根據(jù)推論1,可得ΔR( c|T∪{si} )-ΔR(c|T)≥0.

根據(jù)式(5),可得Δi(c)＞0.因此,由式(6),可得v(si)＞Ru.證畢.

引理2 對(duì)于?sj∈c,sj≠si,若Rt(si)＜Rt′(si),且Rt(sj)=Rt′(sj),則vt(si)＜vt′(si).

證明 令T∈c{si},已知?sk∈c,Δe(sk)=0,則ΔR(c|si)＜0且ΔR(c|sj)=0.考慮如下兩種情況:

情況1 若T=?,則Rt( c|T∪{si} )-Rt′(c|T∪{si} )=Rt(c|si)-Rt′(c|si)＜0;

情況2 若T≠?,根據(jù)命題1,可得Rt( c|T∪{si} )-Rt′(c|T∪{si} )≤0.

此外,對(duì)于?sj∈c,sj≠si,已知Rt(sj)=Rt′(sj),則對(duì)于?T,可得Rt(c|T)=Rt′(c|T).由

引理3 ?sj∈c,sj≠si,若Rt(si)＞Rt′(si),且Rt(sj)=Rt′(sj),則vt(si)＞vt′(si).

引理4 ?sj∈c,sj≠si,若Rt(si)=Rt′(si),且Rt(sj)=Rt′(sj),則vt(si)=vt′(si).

引理3和引理4的證明與引理2的證明類似,在此省略.

上述引理證明了在證據(jù)數(shù)目不變(Δe(s)=0)的條件下信譽(yù)傳播的公平性.當(dāng)證據(jù)數(shù)Δe(s)≠0時(shí),首先假設(shè)單個(gè)組件的證據(jù)數(shù)增加或減少時(shí)信譽(yù)傳播配額的變化下的公平性,之后利用歸納法證明當(dāng)多個(gè)組件證據(jù)數(shù)的信譽(yù)傳播的配額變化.其證明與引理2的證明類似,在此省略.

定理1 在服務(wù)組合中,所提出算法能夠公平地將信譽(yù)傳播到組件服務(wù)之中.

證明 根據(jù)上述引理,定理1成立.

3 仿真評(píng)估

3.1 實(shí)驗(yàn)環(huán)境

以圖1為例對(duì)不同結(jié)構(gòu)下算法FGRP信譽(yù)傳播的公平性進(jìn)行實(shí)驗(yàn)評(píng)估(實(shí)驗(yàn)以順序結(jié)構(gòu)為例說(shuō)明確定結(jié)構(gòu)下的信譽(yù)傳播結(jié)果).在圖1中,假設(shè)用戶希望將漢語(yǔ)翻譯至盧森堡語(yǔ),但網(wǎng)絡(luò)中并不存在直接的翻譯器.服務(wù)提供商通過(guò)組合漢語(yǔ)至英語(yǔ)(Chi-to-Eng)、英語(yǔ)至德語(yǔ)(Eng-to-Deu)、德語(yǔ)至盧森堡語(yǔ)(Deu-to-Lux)的組件服務(wù)實(shí)現(xiàn)翻譯功能.同時(shí),存在3個(gè)不同服務(wù)商GOG、MIC和BAI來(lái)提供英語(yǔ)至德語(yǔ)的翻譯服務(wù),其調(diào)用概率分別為60%、20%和20%.

圖1 漢語(yǔ)至盧森堡語(yǔ)翻譯服務(wù)

兩組實(shí)驗(yàn)分別對(duì)不同組合結(jié)構(gòu)進(jìn)行獨(dú)立實(shí)驗(yàn)評(píng)估.每組實(shí)驗(yàn)生成100組觀察值,并利用文獻(xiàn)[14]方法對(duì)最大期望算法進(jìn)行初值選取以減少組件責(zé)任及信譽(yù)度計(jì)算的誤差.同時(shí),實(shí)驗(yàn)與特征類似的文獻(xiàn)[7]方案進(jìn)行對(duì)比.對(duì)比中令用戶評(píng)價(jià)值Ru=0.7,Shapley值計(jì)算常數(shù)L= R(c).其他參數(shù)與實(shí)驗(yàn)結(jié)果如表1和表2所示.

表1 確定組合模式的信譽(yù)傳播

表2 概率組合模式的信譽(yù)傳播

3.2 評(píng)估結(jié)果

表1描述圖1中順序模式服務(wù)s1、s2和s3信譽(yù)傳播實(shí)驗(yàn)結(jié)果,其包含信譽(yù)評(píng)估較好的服務(wù)s1和較差的服務(wù)s3以及中性服務(wù)s2.如表1所示,在算法FGRP中s1始終獲得正向貢獻(xiàn)度,而s3獲得負(fù)向貢獻(xiàn)度.此外,當(dāng)中性服務(wù)證據(jù)值改變時(shí)(第2行數(shù)據(jù)),復(fù)合服務(wù)信譽(yù)度向其逼近,其他服務(wù)的貢獻(xiàn)度因此減少,而算法FGRP能夠有效地反映出貢獻(xiàn)改變的情況并計(jì)算正確的傳播值.最后,當(dāng)特定組件信譽(yù)改變時(shí)(第3行數(shù)據(jù)),其余組件的貢獻(xiàn)度也會(huì)相應(yīng)改變,而在文獻(xiàn)[7]提出的算法中,在各個(gè)組件的信譽(yù)度不變而證據(jù)值變化時(shí),其傳播值不變,從而無(wú)法正確表征組件的貢獻(xiàn)度.

對(duì)于確定模式組合結(jié)構(gòu),實(shí)驗(yàn)中各算法統(tǒng)計(jì)學(xué)習(xí)的最大誤差為22%.這是由于在確定性模式中,Beta混合模型的概率分布疊加在特定觀察值下呈現(xiàn)單峰分布,從而無(wú)法很好地進(jìn)行統(tǒng)計(jì)學(xué)習(xí).由于算法引入一致性因子μ,μ∈(0,1),在一定程度上能夠減少誤差帶來(lái)的影響,實(shí)現(xiàn)公平的信譽(yù)傳播.此外,表1還能夠證明Shapley值的有效性,即正向貢獻(xiàn)和與負(fù)向貢獻(xiàn)和始終相等.

表2描述了圖1中概率模式服務(wù)s4、s5和s6信譽(yù)傳播的實(shí)驗(yàn)結(jié)果.由于概率組合模式特性與最大期望算法的乘法疊加特性類似,在算法中統(tǒng)計(jì)學(xué)習(xí)的最大誤差僅為4.6%.表2結(jié)果與表1結(jié)果類似,均能夠很好地反映各個(gè)組件貢獻(xiàn)度及信譽(yù)傳播的公平性.而文獻(xiàn)[7]所提出算法由于不支持概率組合模式,其傳播值無(wú)法表征信譽(yù)傳播的公平性以及組件證據(jù)數(shù)變化時(shí)傳播值變化的正確性.

3.3 方案對(duì)比

算法FGRP與相關(guān)信譽(yù)傳播算法的對(duì)比如表3所示.首先,FGRP通過(guò)統(tǒng)計(jì)學(xué)習(xí)方法對(duì)組件的責(zé)任及信譽(yù)度進(jìn)行學(xué)習(xí),不依賴已有算法對(duì)服務(wù)組件信譽(yù)或服務(wù)質(zhì)量值可觀察性的假設(shè),從而解決了不透明性問(wèn)題.其次,算法FGRP不僅考慮文獻(xiàn)中的確定性模型,而且支持對(duì)部分工作[7-9]中缺少的概率模式的信譽(yù)傳播,從而全面解決了服務(wù)組合結(jié)構(gòu)的復(fù)雜性問(wèn)題.再次,FGRP無(wú)須用戶對(duì)最優(yōu)和最差情況組件的服務(wù)質(zhì)量值進(jìn)行估計(jì)[10],將用戶對(duì)復(fù)合服務(wù)的評(píng)價(jià)值公平傳播到各個(gè)組件,從而解決了用戶評(píng)價(jià)的主觀性問(wèn)題.最后,筆者基于Shapley值特性對(duì)算法FGRP進(jìn)行證明,確保所提算法的公平性.

表3 信譽(yù)傳播方案對(duì)比

4 結(jié)束語(yǔ)

針對(duì)服務(wù)的不透明性、組合結(jié)構(gòu)的復(fù)雜性以及用戶評(píng)價(jià)的主觀性所造成的信譽(yù)傳播問(wèn)題,筆者提出一種適用于服務(wù)組合的公平信譽(yù)傳播算法,即FGRP.該算法具有如下特征:基于Beta混合模型對(duì)組件責(zé)任及信譽(yù)度學(xué)習(xí),解決服務(wù)的不透明性;對(duì)確定組合模式與概率組合模式分別建模,解決服務(wù)結(jié)構(gòu)組合的復(fù)雜性;基于合作博弈Shapley值進(jìn)行服務(wù)貢獻(xiàn)計(jì)算,消除用戶評(píng)價(jià)的主觀性.算法FGRP在無(wú)須用戶提供服務(wù)質(zhì)量估計(jì)值的基礎(chǔ)上,實(shí)現(xiàn)了復(fù)合服務(wù)到組件服務(wù)信譽(yù)的層次化公平傳播.理論分析與實(shí)驗(yàn)結(jié)果均能夠證明所提方法的合理性和有效性.

下一步研究工作的重點(diǎn)首先在于提高信譽(yù)傳播的精確性,其主要來(lái)源于兩個(gè)方面:減少由于概率疊加所造成的統(tǒng)計(jì)誤差;服務(wù)信譽(yù)變化的動(dòng)態(tài)性對(duì)信譽(yù)傳播變化的影響.其次,對(duì)于海量服務(wù)的貢獻(xiàn)度計(jì)算,Shapley值在計(jì)算時(shí)需要考慮所有組合情況,因而存在開銷過(guò)大的問(wèn)題.所以,提高計(jì)算性能也是將來(lái)研究需要考慮的問(wèn)題之一.

參考文獻(xiàn):

[1]PAPAZOGLOU M P,TRAVERSO P,DUSTDAR S,et al.Service-oriented Computing:a Research Roadmap[J].International Journal of Cooperative Information Systems,2008,17(2):223-255.

[2]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.

[3]孟憲佳,馬建峰,盧笛,等.面向可信和行為模式匹配的兩層服務(wù)選擇方法[J].西安電子科技大學(xué)學(xué)報(bào),2014,41(4): 198-204.MENG Xianjia,MA Jianfeng,LU Di,et al.Trust and Behavioral Modeling Based Two Layer Service Selection[J].Journal of Xidian University,2014,41(4):198-204.

[4]ZHANG T,MA J F,SUN C,et al.Service Composition in Multi-domain Environment under Time Constraint[C]// Proceedings of the IEEE 20th International Conference on Web Services.Piscataway:IEEE Computer Society,2013: 227-234.

[5]ZHANG T,MA J F,XI N,et al.Trustworthy Service Composition in Service-oriented Mobile Social Networks[C]// Proceedings of the IEEE 21th International Conference on Web Services.Piscataway:IEEE Computer Society,2014: 684-687

[6]ZHANG T,MA J F,LI Q,et al.Trust-based Service Composition in Multi-domain Environments under Time Constraint[J].Science China Information Sciences,2014,57(9):092109(16).

[7]NEPAL S,MALIK Z,BOUGUETTAYA A.Reputation Propagation in Composite Services[C]//Proceedings of the IEEE International Conference on Web Services.Piscataway:IEEE,2009:295-302.

[8]Da SILVA I,ZISMAN A.Decomposing Ratings in Service Compositions[C]//Lecture Notes in Computer Science:8274 LNCS.Heidelberg:Springer Verlag,2013:474-482.

[9]SADEGHI R,AZGOMI M A.A Method for Fair Propagation of User Perceptions for Trust Management in Composite Services[J].Service Oriented Computing and Applications,2015,9(2):157-176.

[10]LIU A,LI Q,ZHOU X F,et al.Rating Propagation in Web Services Reputation Systems:A Fast Shapley Value Approach[C]//Lecture Notes in Computer Science:8421 LNCS.Heidelberg:Springer Verlag,2014:466-480.

[11]HANG C W,SINGH M P.Trustworthy Service Selection and Composition[J].ACM Transactions on Autonomous and Adaptive Systems,2011,6(1):5-22.

[12]LI L,WANG Y.Trust Evaluation in Composite Services Selection and Discovery[C]//Proceedings of the IEEE International Conference on Services Computing.Piscataway:IEEE Computer Society,2009:482-485.

[13]SHAPLEY L S.Theory of GamesⅡ[M].Princeton:Princeton University Press,1953:307-317.

[14]BOUGUILA N,ZIOU D,MONGA E.Practical Bayesian Estimation of a Finite Beta Mixture through Gibbs Sampling and Its Applications[J].Statistics and Computing,2006,16(2):215-225.

(編輯:郭 華)

Fairness-guaranteed reputation propagation in Web service composition

ZHANG Tao,MA Jianfeng,MO Ruo,LI Qi,XI Ning
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

Abstract:In service-oriented environment,it is difficult to evaluate component services because of the opaque characteristic of composite services,the complex invocation structures and the subjective reputation rating of service consumers.To address these issues,this paper proposes a reputation propagation algorithm for service composition,in which the subjective ratings can be fairly propagated to each component service.The algorithm first models service composition as the Beta-mixture,and learns the reputation and responsibility of each component by the EM algorithm.Then,based on the characteristics of Shapley values in cooperative gaming theory,the algorithm computes the contribution of each component to its composition,ensuring that no component would obtain extra rewards or punishments.Finally,theoretical analysis and experimental results demonstrate the fairness of the algorithm to hieratically propagate the consumer’s rating to each component service.

Key Words:service-oriented architecture;service composition;Web services;reputation propagation; fairness

作者簡(jiǎn)介:張 濤(1986-),男,西安電子科技大學(xué)博士研究生,E-mail:tzhang@stu.xidian.edu.cn.

基金項(xiàng)目:長(zhǎng)江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃資助項(xiàng)目(IRT1078);國(guó)家自然科學(xué)基金委員會(huì)-廣東聯(lián)合基金重點(diǎn)基金資助項(xiàng)目(U1135002);國(guó)家科技部重大專項(xiàng)資助項(xiàng)目(2011ZX03005-002);國(guó)家自然科學(xué)基金資助項(xiàng)目(61370078)

收稿日期:2014-10-17 網(wǎng)絡(luò)出版時(shí)間:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.013

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

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

文章編號(hào):1001-2400(2016)02-0070-07

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.010.html