Web服務中的推薦機制的研究
2016-04-11 01:44:12毛莉娜唐林燕王曉軍
計算技術與自動化 2016年1期
毛莉娜 唐林燕 王曉軍
摘要：借助社會的人際關系網，提出web服務中基于信任網的推薦機制用于實現信任關系的傳遞，給出信任網的數學表達、生成算法和聚集算法，并歸納信任網推薦鏈之間的各種依賴關系及相應的處理策略，最后的實驗結果證明了其有效性。
關鍵詞：信任評估；WEB服務；信任網；推薦機制
中圖分類號：TP3文獻標識碼：A
1引言
由于WEB服務網絡中存在海量的WEB服務。服務請求者與通過UDDI搜索得到的WEB服務之間往往不存在或只有少數的直接交互經驗。直接經驗的不足或缺乏使得服務請求者經常無法評估對對方的信任關系，特別是當服務請求者碰到一個陌生的服務或服務提供者時，如何對其進行信任度或聲譽的評估成了一個關鍵問題。
常見的解決方法是利用其它實體的推薦信息作為評估參考。信任和聲譽可以通過”口碑”或其他實體的推薦進行，這也就為WEB服務網絡中對陌生實體的評估提供了一個有效的解決途徑。本文研究重點是分析如何構造實體間的信任網來實現信任關系的傳播，以獲取對陌生實體的間接信任，提出在WEB服務中基于信任網的推薦機制，給出相應的數學表述以及生成算法，給出推薦鏈之間的各種依賴關系以及相應的處理策略。
2Web服務中基于信任網的推薦機制
在一般的社會網絡中，信任關系是通過個體間的相互關系推薦而形成。然而其中某一個體的聲譽一般又取決于其他個體的推薦，同時推薦本身的聲譽也決定所推薦的信息的可信度。此種相互依賴的信任度的關系也就構成了整個實體間的信任網絡，如實體A向實體B進行信任評估（圖1所示）。信任網中任何個體的聲譽可以作為對陌生實體的評估參考。
推薦機制是信任和聲譽模型的重要組成部分，許多學者也將其作為研究的重點。本文提出兩個問題：
利用Jacobi迭代對信任關系矩陣進行迭代收斂來獲取任意節點的全部可信度，但沒有分析迭代過程中信任關系之中的相互依賴情況；
節點之間的每一次交易都會在與這些節點有過交易的所有實體中引起迭代，因而無法適應大規模的Web服務網絡。
現有的研究大多對信任網中推薦鏈的依賴關系缺乏缺乏深入的分析。
2.1基本定義和概念
本文提出的關于信任網中的基本定義和概念。
定義1認識關系（acquaintancerelationship）：如果實體a認識b，那么稱a和b間存在認識關系，則記為Know（a，b）。
定義2熟人關系（familiartiesfamiliarties）：如果Acq（a，b）=Know（a，b）∧Know（b，a），那么就稱實體a和b是具有熟人關系。
定義3熟人關系集（acquaintanceset）：如果實體a的熟人關系集Acq（a）是所有熟人組成的集合，則可記為：Acq（a）={b∈A∧Acq（a，b）}。
定義4推薦關系（recommendrelationship）：r
定義5推薦鏈（recommendchain）：如果對i∈[1，2，…，n-1]都有Acq（ci，ci+1），同時滿足Acq（a，c1和Acq（cn，b），那么就稱e=
定義6信任網（WebofTrust）：假設Wot（C，R，W，a，b）為一加權有向圖，其中C為有限Agent集{c1，c2，…，cn}，R={r1，r2，…，rn}是C中節點組成的有序推薦集，是由直接經驗帶來的信任關系，W為b的所有見證者集合，可用W（b），表示a為評估主體，b為評估客體。
定義7信任強度（trustIntensity）：這里是指在推薦信任傳遞過程中所能直接信任的可靠程度，信任強度可以通過實體間的直接信任關系推導得出，用Ti表示。
定義8推薦信任（RecommendationTrust）：這里是指包括了對目標客體的直接信任以及對直接信任的可靠程度，可以用向量（Td，Ti）來表示，稱其為推薦信任Tr。
本文是以主觀邏輯的合意規則作為對于Td和Ti的聚集函數。其中，對Tr的計算本質實際上就是對Td和Ti進行合成，而信任強度Ti稱為權重值。
2.2推薦信息可信度分析
推薦信息是推薦實體在收到推薦請求之后，可能如實地提供推薦信息，也可能出于本身的利益考慮或其他目的而故意給出錯誤的推薦信息。對推薦信息的可信度評估就反映為對信任強度的計算。
對信任強度的計算方法主要有以下三種：①歷史推薦信息，即Ci根據Cj以往給出的推薦情況來衡量推薦信息的可靠度，確定對推薦信息的采納程度。②Cj的全局聲譽，即通過其他實體的綜合評價來考慮推薦信息的可信度，其前提是假定聲譽越高的實體所提供的推薦信息越可信。③Cj的本地聲譽，即根據Ci與Cj以往的直接交互經驗計算的Cj本地聲譽，并以此來衡量推薦信息的可信度。
本文結合第一種和第二種方法，也就是綜合考慮Cj的歷史推薦情況及Cj在Ci中的本地聲譽來計算Cj所提供的推薦信息的可靠度。
2.3信任網生成算法
信任策略1：若兩個實體之間即存在直接的推薦信任關系的話，則也會存在通過其他實體的推薦信任連接起來的間接推薦信任關系，也就是說直接經驗比間接經驗的信任度更高。如果只是采納直接推薦信任關系的話，就可忽略間接的推薦信任關系。
信任策略2：如果推薦實體不能對獲取的間接信任進行推薦的話，那么就只允許推薦直接信任。
以上兩個策略用于約束信任網的拓撲結構，減少復雜性。其生成算法CreateWebTrust是一個深度優先的有向圖遍歷過程，其偽代碼表示如下：
功能描述：
輸入：評估主體a，目標客體b，a的熟人關系集Acq（a）。輸出：信任網Wot（C，R，W，a，b），推薦鏈集E。變量：E（推薦鏈集變量），e（推薦鏈變量，以隊列形式表示），Nt（節點變量），Ld（推薦鏈長度）。
算法描述：
E=，a=，a→e
Nt=FirstAcq（a）//獲取a的第一熟人
Ld=1//推薦鏈深度置1
Dfs（Nt）//開始進行深度優先搜索，得到推薦鏈E
RestrictWebofTrust（Wot）//對信任網增加信任策略1的限制
根據推薦鏈集E產生Wot（C，R，W，a，b）
Dfs（Nt）的過程：
功能描述：尋求滿足條件的結點Nt的推薦對象，輸入：節點Nt，輸出：滿足條件的下一節點
算法描述：
Ife=andNt=0then//結束搜索
Exit
Endif
IfLd IfAcq（Nt，b）then//找到一條合法的推薦鏈 Nt→e，b→e，e→E//將e添加到推薦鏈集E中 Delete{Nt，b}frome//將{Nt，b}從e中刪除 Nt=NextAcq（1astnode（e））//獲取e最后一個節點的下一個熟人 Endif IfnotAcq（Nt，b）andNt≠0then//Nt不是的b見證者，且不為空 Nt→eLd=Ld+1//將Nt添加到e的尾部，并將推薦鏈長度加1 Nt=FirstAcq（Nt）//獲取Nt的第一個熟人 Dfs（Nt）//繼續搜索 Endif IfNt=0then//節點不存在 deletelastnode（e）frome//刪除e中的最后一個節點 Ld=Ld-1//推薦鏈長度減1 Nt=NextAcq（node（e）） （Nt） Endif Else//已經達到推薦鏈的最大深度限制，需要回避 Delete1astnode（e）frome//刪除e中的最后一個節點 Ld=Ld-1 Nt=NextAcq（node（e）） （Nt） Endif 2.4推薦鏈的依賴關系分析 因為對于b的信任評估主要通過合理地綜合推薦鏈上的信任關系，所以要求同一推薦關系就不能在其計算過程中不斷地進行重復的使用。依據信任網中的推薦鏈之間不同的依賴程度，將推薦鏈之間的依賴關系區可以分為以下兩種： 無依賴關系（NoDependentRelationship） 若推薦鏈ei和ej滿足條件：如果x∈ei/{a，b}，y∈ej/{a，b}，ei≠ejx∩y=φ，那么就稱ei和ej之間是相互獨立的，并無依賴關系（說明：ei/{a，b}為ei中去除a和b后剩下的節點集合）。 聚集算法（AggregateWitnessRep）描述了對無依賴關系推薦鏈上的信任觀念的綜合過程。假設信任網Wot（C，R，W，a，b）中集合C的節點個數n，設（n+1）×（n+1）階矩陣M=（mij）為Wot中的推薦路徑表示，矩陣中行節點排列順序為c1，c2，…，cn，b，列的排列順序為a，c1，c2，...，cn，且mij滿足：1（若ci為起點，cj為終點）；-1（cj為起點，ci為終點）；0（無連接關系）。 聚集算法（AggregateWitnessRep）偽代碼描述： 輸入：信任網Wot（C，R，W，a，b）；輸出：a對wi的信任觀念awi（信任強度Ti），b對wi的信任觀念wib（信任強度Td）；變量：CH和Cr為節點，t為信任觀念變量。算法描述： Foreachiin[1..n+1]do Ifm[i，n+1]=1then//說明節點ci-1∈w（b） CT=ci-1 CH=GetConverseRecNode（CT）//逆向獲取對CT作出推薦的另一個節點 t=dCHCTCHrCT//計算CH對CT的信任強度，并賦予變量t WhileCT≠ado//若CH為評估主體a，說明推薦鏈終止，否則繼續 CT=CH//以CH為起點，逆向繼續查找推薦路徑中的其他節點 CH=GetConverseNode（CT） t=（CHdCtCHrCTCHCT）t//利用推薦規則進行綜合 Endwhile awi=t//輸出a對wi的綜合信任觀念 wib=ci-1b//輸出wi對b的信任觀念 Endif Endof 依賴關系（DependentRelationship） 若推薦鏈ei和ej滿足條件：如果x∈ei/a，b，y∈ej/a，b，ei≠ejx∩y=φ，那么就稱ei和ej之間存在依賴關系。根據依賴程度的不同，可分為： e1∩e2={a，c1，cn，b}。 圖2部分依賴關系的推薦鏈 a對b的綜合信任觀念正確的計算方法為：從全局的角度出發，將e1和e2結合在一起分析，認為a對b只存在一條推薦路徑，而推薦路徑中間存在著分叉。則a對b綜合信任觀念的計算過程用ac1（（c1c2…c1cn）（c1ci+1…c1cn））cnb，以a（c1c2…ci，c1ci+1…cj）cnb表示。
PreTreatDependentLink算法的偽代碼：
ForeachwinW（b）do
Ei=getAllRecLinks（E，w）//求出所有以a為起點，以w為終點的推薦鏈
Ifcount（Et≠1then//說明推薦鏈的個數大于1
N=getAllPulicNodes（Et）//求出所有推薦鏈中公共節點
Ifcount（N）≠0then//推薦鏈有公共節點，即存在著部分依賴關系
WhileN≠do
NT=lastnode（N）//最后一個節點
DeleteNTfromN
NH=lastnode（N）//最后一個節點的前一個節點
DeleteNHfromN
t={0，0，1}
ForeacheinEtdo
If{NH，NT}inethen//說明推薦鏈e經過了節點Nt和w
t=rNtw//對推薦鏈規則計算后的信任觀念使用合意規則合并
Endif
Endfor
Endfor
函數GetAllPulicNodes的算法描述：
ForeiinEtdo
ForejinEt//ei≠ej
Ni=firstnode（ei）
WhileNt≠0do
If（Niinej）and（nextnode（Nt）notej）then//從Nt開始分叉
Nt→N
Nt→nextnode（Nt）
Endif
If（Ntnotinej）and（nextnode（Nt）inej）then//說明在下一個節點收斂
Nextnode（Nt）→N//將下一個節點添加到N中
Nt=nextnode（Nt）//前進下一個節點
Endif
Endwhile
Endfor
Endfor
Sort（N）//對N中的節點進行排序。按照這些節點在推薦鏈上的先后順序對N排序
完全依賴（FullyDependent）完全依賴關系的推薦鏈如圖3所示，當推薦實體c4和c5滿足c5∈Acq（c4）和c4∈Acq（c5）時，計算a對b的信任觀念將變得非常困難。
當推薦鏈之間存在完全依賴關系時，將使得交集中實體的信任觀念無法合理地進行綜合。對于此類問題，本文提出以下的解決策略如下：
信任策略3（悲觀策略，Thepessimisticstrategy）：此策略禁止信任網依賴關系產生，只能允許存在相互獨立的推薦鏈。它能夠有效地防止完全依賴關系的產生，但是也部分依賴關系的存在關系被禁止了。
信任策略4（樂觀策略，OptimisticStrategy）：此策略允許部分依賴關系和完全依賴關系，對于完全依賴關系的推薦鏈上的信任觀念在進行綜合時，則需要采用特殊的策略才行。
信任策略5（折衷策略，Thecompromisestrategy）：此策略在生成信任網的過程中可以允許依賴關系的產生，但是必須要區分完全依賴關系和部分依賴關系。其中對于存在完全依賴關系的推薦鏈可全部忽略掉，而對于部分依賴關系的推薦鏈則可采用上述方法進行解決。
本文采用的是折衷策略。但是在實際應用過程中，則可以根據具體的實際情況來確定采用與其相符合的解決策略。
2.5算法復雜度分析
以下是對本文提出的各種算法的時間復雜度進行分析
2.5.1信任網生成算法CreateWebofTrust
深度優先搜索過程Dfs（Nt）
Dfs（Nt）的時間復雜度隨著NAN和Nd值的增長而迅速增長。最差情況下，信任網中每個推薦節點的熟人個數均NAN，每一條推薦路徑的深度均為Nd，這時計算復雜度為NAN的指數級，即O（NANNd）。
約束算法RestrictWebofTrust（Wot）
此算法所耗費的時間取決于推薦鏈集E的存儲結構。當采用二維數組表示鄰接矩陣作為E的存儲結構時，所需的時間為O（n3），其中n為E中的節點數；當用鄰接表作E的存儲結構時，所花的時間為O（H2×Nd），其中H為推薦鏈的個數。
2.5.2聚集算法AggregateWitnessRep
此算法的時間復雜度取決于信任網的存儲結構，當采用二維數組表示鄰接矩陣作為信任網的存儲結構時，花費的時間為O（n2），當采用鄰接表時，花費的時間為O（n+H），其中n為信任網中的節點數。
預處理算法PreTreatDependenLink
此算法的時間復雜度主要依賴于函數GetAllPulicNodes，其中Sort（N）所需要的時間為O（Nd2）。總的時間復雜度為O（H2×Nd+Nd2）。
對整個推薦機制而言，最困難的地方在于如何快速地找到從a到b的合法路徑。當各個推薦節點的熟人集變得很大時，推薦機制的計算時間會快速地增加。在實際應用中，需有效地限制NAN和Nd的值。
對整個推薦機制來說，如何快速找到從a到b的合法推薦路徑是一個難點。因為當熟人集很大時，推薦機制的計算時間會快速增加，須有效限制NAN和Nd的值。
3實驗
用例描述
假設推薦鏈的深度Nd為3，在提供服務的過程中，誠實SP提供良好服務率為80%以上，惡意SP進行的欺騙性在80%以上。各種參數設置如表1。
從圖4可得出結論，所考慮推薦鏈和信任強度越多，SR所訪問到的惡意SP的可能性越小。
4結束語
WEB服務中的推薦信任是各種信任和聲譽模型的重要組成部分，它有效地緩解了實體間由于直接信息的不足而帶來的評估風險。本文借助社會學的信任網從直接信任和信任強度進行分析，描述了推薦信任在傳遞過程中的變化，歸納推薦鏈之間的依賴關系并提出相應的解決策略。
參考文獻
[1]張仕斌；許春香.基于云模型的信任評估方法研究[J].計算機學報，2013，369（2）：433-431.
[2]胡春華；吳敏；劉國平.Web服務工作流中基于信任關系的QoS調度[J].計算機學報，2009，32（1）：43-53.
[3]LIJT，WANGXP，Liu.BPEER-TO-PEER環境下的TRUST模型[J].環境下的模型軟件學報，2004，15（14）：571-580.
[4]陳剛.關系網模型-基于社會合作機制的多AGENT協作組織方法[J].計算機研究與發展，2003，40（1）：107-114.
[5]杜靜.基于貝葉斯網絡的多Agent服務推薦機制研究[J].計算機科學，2010，38（4）：214-217.
[6]程冬，董才林，喻瑩.一種基于模糊理論的Web服務信任評估模型[J].計算機應用與軟件，2012，29（10）：83-84.
[7]申利民.基于博弈論的Web服務信任評估模型[J].小型微型計算機系統，2014，36（8）：1681-1686.
[8]袁東維，李蜀瑜.一種基于信任的Web服務發現方法，2011，33（3）：194-198.
第35卷第1期2016年3月計算技術與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016第35卷第1期2016年3月計算技術與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016endprint
