一種改進的動態信任信息聚合算法

王春紅,任姚鵬,姚喜妍

(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