王春紅,任姚鵬,姚喜妍

(1.運(yùn)城學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，山西 運(yùn)城 044000;2.運(yùn)城學(xué)院 應(yīng)用數(shù)學(xué)系，山西 運(yùn)城 044000)

一種改進(jìn)的動(dòng)態(tài)信任信息聚合算法

王春紅1,任姚鵬1,姚喜妍2

(1.運(yùn)城學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，山西 運(yùn)城 044000;2.運(yùn)城學(xué)院 應(yīng)用數(shù)學(xué)系，山西 運(yùn)城 044000)

隨著分布式應(yīng)用系統(tǒng)的發(fā)展，系統(tǒng)形態(tài)正從相對(duì)靜態(tài)的形式向開放的、動(dòng)態(tài)的服務(wù)模式轉(zhuǎn)變。在這動(dòng)態(tài)環(huán)境中，基于證書的靜態(tài)信任機(jī)制就不再適應(yīng)，就出現(xiàn)了動(dòng)態(tài)信息機(jī)制管理問題。其中，核心問題之一是動(dòng)態(tài)反饋信息的聚合。而現(xiàn)有的動(dòng)態(tài)信任聚合算法基本都采用基于信任鏈或廣播方式，這樣往往導(dǎo)致了系統(tǒng)運(yùn)算收斂慢、可擴(kuò)展性差等問題。文中提出一種改進(jìn)的動(dòng)態(tài)信任信息聚合算法。首先，利用一種反饋信任值聚合方法獲得反饋信任值；接著，在此基礎(chǔ)上，基于蟻群算法通過多次循環(huán)尋找出多條較優(yōu)的獨(dú)立信任路徑，并獲得最終的反饋信任值。實(shí)驗(yàn)結(jié)果表明，該算法效率較高，可擴(kuò)展性較好，可以獲得較合理的反饋信任值，而且可在一定程度上有效防止聯(lián)合欺詐行為。

動(dòng)態(tài)信任；反饋信任；蟻群算法；信任路徑

0 引 言

伴隨著面向Internet的企業(yè)資源規(guī)劃系統(tǒng)(ERP)、客戶關(guān)系管理系統(tǒng)(CRM)、供應(yīng)鏈管理系統(tǒng)(SCM)、電子商務(wù)系統(tǒng)(e-Business)等大型分布式商業(yè)軟件系統(tǒng)的大量涌現(xiàn)，其系統(tǒng)模式已從較為封閉的運(yùn)行環(huán)境轉(zhuǎn)變?yōu)楦叨茸兓拈_放性運(yùn)行環(huán)境。由于分布式的開放環(huán)境使得各資源實(shí)體分布于網(wǎng)絡(luò)的不同位置，且不存在一個(gè)中央控制主體，因此傳統(tǒng)的ACL和基于公鑰的證書體系等集中式安全控制機(jī)制就不能很好地滿足這種分布式系統(tǒng)的安全需求。因此，在開放式的網(wǎng)絡(luò)環(huán)境中，信息安全的管理就不能采用傳統(tǒng)靜態(tài)的信任管理模型，而轉(zhuǎn)化為動(dòng)態(tài)信任管理的問題[1-3]。

在動(dòng)態(tài)的信任管理中，如何有效地進(jìn)行信任反饋信息的聚合成為了其中一核心問題[4-8]。在目前的信息聚合算法中，大都采用信任鏈或廣播方式來計(jì)算推薦信任值，這對(duì)算法的收斂性和可擴(kuò)展性都是極大的挑戰(zhàn)[9-12]。因此文中從信任路徑的尋找和算法的可擴(kuò)展性兩方面著手，提出一種改進(jìn)的動(dòng)態(tài)信任聚合算法。該算法首先采用了一種反饋信任值聚合函數(shù)，來獲得實(shí)體的推薦信任值，增強(qiáng)在大規(guī)模網(wǎng)絡(luò)環(huán)境中算法的可擴(kuò)展性；再利用蟻群算法在較短的時(shí)間內(nèi)獲取多條較優(yōu)信任路徑；最后聚合算法獲取最終的信任值。

1 反饋信任值聚合方法

在網(wǎng)絡(luò)環(huán)境中，為了保證信息的安全，實(shí)體之間要進(jìn)行交互，需要通過測(cè)評(píng)要進(jìn)行交互的實(shí)體的信任度，來確定是否與其交互。實(shí)體信任度的計(jì)算分為三種情況：

(1)兩實(shí)體之間最近有直接交互的記錄；

(2)兩實(shí)體沒有交互記錄；

(3)兩實(shí)體交互的記錄比較陳舊[12]。

對(duì)于第一種情況，就可以利用兩實(shí)體直接交互后實(shí)體間的直接評(píng)價(jià)來獲取，也就是直接信任值；對(duì)于第二、三種情況，需要借助于其他實(shí)體側(cè)面獲取實(shí)體信任值。

文中采用了一種反饋信任值聚合方法。該方法是基于其他相關(guān)聯(lián)的實(shí)體之間的直接信任值來獲得實(shí)體的反饋信任值。多數(shù)情況下是要獲取實(shí)體的反饋信任值。

1.1 直接信任值

直接信任是指實(shí)體Pi在與實(shí)體Pj直接交互后，Pi對(duì)Pj的滿意程度。這里，用E(Pi,Pj)表示Pi對(duì)Pj的信任滿意程度，且E(Pi,Pj)∈[0,1]，值越大表示Pi對(duì)Pj越信任越滿意。

假設(shè)實(shí)體Pi和Pj在最近T次交互中，Pi對(duì)Pj的信任值為集合Eij={e(1)ij,e(2)ij,…,e(h)ij}。其中，0≤e(k)ij≤1。則Pi與Pj的直接信任值可借用人工智能理論中的可信度推算公式,通過合成計(jì)算方法求出其信任值：

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)

其中，根據(jù)人類交往經(jīng)驗(yàn)，最近一次的交往能更好反映人與人之間的關(guān)系。因此，網(wǎng)絡(luò)中計(jì)算實(shí)體的信任度時(shí)，模擬了人的行為，引入一個(gè)r(k)函數(shù)。它是一個(gè)隨時(shí)間逐漸衰減的函數(shù)，其值在0，1之間，定義如下：

(2)

1.2 反饋信任值

反饋信任主要是通過信息的傳遞性來計(jì)算的(a信任b，b信任c，則a信任c)。假設(shè)實(shí)體Pi需要測(cè)評(píng)實(shí)體Pj的反饋信任度，來確定是否與Pj發(fā)生交互。則實(shí)體Pj的反饋信任值可通過下面的反饋信任值聚合函數(shù)來求得。

R(PiPj)=∑E(Wk,Pj)/n

(3)

其中：Wk表示實(shí)體Pj的第k個(gè)反饋者；E(Wk,Pj)表示實(shí)體Wk對(duì)實(shí)體Pj的直接信任值；n表示實(shí)體Pj反饋者的數(shù)目。

利用上述公式求得的反饋信任值只是一種情況下的反饋信任值，因?yàn)閷?duì)于實(shí)體Pj的反饋者選擇時(shí)，可能會(huì)出現(xiàn)多種情況。也就是說僅利用公式一次計(jì)算出的反饋信任值并不一定正確，可能存在聯(lián)合欺詐的行為。因此，文中在獲得反饋信任值的基礎(chǔ)上，又采用了蟻群算法，選取多條較優(yōu)的信任路徑，最后計(jì)算出最終的反饋信任值。這樣，就可以有效避免網(wǎng)絡(luò)中的聯(lián)合欺詐。

2 信任路徑的尋找

2.1 信任路徑

這里，把網(wǎng)絡(luò)中的信任關(guān)系抽象為一帶權(quán)有向圖G=((V,E),S,D,L)。其中：V為圖頂點(diǎn)集，代表網(wǎng)絡(luò)中的各個(gè)資源實(shí)體；E為有向弧集，代表實(shí)體間的相互信任關(guān)系，并用每條弧上標(biāo)記的權(quán)重Wij∈[0,1]表示實(shí)體i對(duì)實(shí)體j的推薦信任值；S∈V表示源實(shí)體頂點(diǎn)；D∈V表示目標(biāo)實(shí)體頂點(diǎn)；L表示信任路徑的最大長(zhǎng)度，用來控制算法的搜索范圍。

假若搜索的信任路徑為S→V1→V2→…→Vl-1→D，其信任路徑長(zhǎng)度則為l(l≤L)。同時(shí)，一條信任路徑上的反饋信任值可用式(4)求得。

Pathi=∑R(Vi,Vj)

(4)

其中，Vi,Vj都在第i條信任路徑上，R(Vi,Vj)表示實(shí)體Vi對(duì)實(shí)體Vj的反饋信任值，利用式(3)便可以求得。

2.2 基于蟻群算法的信任路徑尋找

用m表示螞蟻數(shù)量，dij表示實(shí)體頂點(diǎn)間的距離。τij(t)表示t時(shí)刻i→j路徑上殘留的信息素量，物理意義為記錄實(shí)體i對(duì)實(shí)體j的反饋信任值[13-14]。m只螞蟻從源頂點(diǎn)S出發(fā)，移動(dòng)過程中螞蟻運(yùn)動(dòng)的轉(zhuǎn)移按一定轉(zhuǎn)移概率進(jìn)行，其轉(zhuǎn)移概率計(jì)算公式如下：

(5)

當(dāng)螞蟻從源頂點(diǎn)出發(fā)到達(dá)目標(biāo)頂點(diǎn)D或當(dāng)移動(dòng)的長(zhǎng)度大于L時(shí)，螞蟻停止運(yùn)動(dòng)。當(dāng)所有的螞蟻都停止尋徑時(shí)，一次循環(huán)結(jié)束。

在尋徑過程中，隨著時(shí)間的推移各個(gè)弧上原有的信息素會(huì)逐漸降低，有螞蟻經(jīng)過的路徑信息素會(huì)相應(yīng)增加，其信息素按式(6)調(diào)整：

(6)

其中，Δτij表示第k只螞蟻本次循環(huán)中在弧ij上信息素的增量。

經(jīng)過多次循環(huán)選出信息素濃度最高的路徑，也就是最優(yōu)的信任路徑。接著，在圖G中去掉該信任路徑中的中間頂點(diǎn)，得到G'；再基于蟻群算法找到下一條次優(yōu)的信任路徑。

這樣循環(huán)k次，便可得到k條獨(dú)立的較優(yōu)信任路徑。

3 改進(jìn)的動(dòng)態(tài)信任信息聚合算法

該算法的基本思想是：首先計(jì)算出各實(shí)體的反饋信任值，接著基于信任值，采用蟻群算法獲取k條較優(yōu)的信任路徑，最后獲取最終的反饋信任值。

最終動(dòng)態(tài)反饋信任值計(jì)算公式為：

FR(S,D)=∑Pathi/K

(7)

下面是改進(jìn)的動(dòng)態(tài)信任信息聚合算法描述。

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)計(jì)算轉(zhuǎn)移概率，選擇下一個(gè)頂點(diǎn)；

記錄第i只螞蟻?zhàn)叩穆窂剑?/p>

}

}

一個(gè)循環(huán)結(jié)束；按式(6)調(diào)整值;

}

按式(4)計(jì)算路徑的推薦信任值；

記錄路徑及推薦信任值；

在圖G中刪除這條路徑中的節(jié)點(diǎn);

}

按式(7)計(jì)算K條信任路徑綜合后得到最終的推薦信任值

4 實(shí)驗(yàn)結(jié)果及分析

4.1 算法性能分析

從收斂性和算法可擴(kuò)展性兩方面來評(píng)估算法的性能。其中，算法的收斂性主要通過算法的運(yùn)行時(shí)間來進(jìn)行衡量；算法的可擴(kuò)展性通過平均存儲(chǔ)空間開銷來衡量。平均存儲(chǔ)空間=占有的總存儲(chǔ)空間/頂點(diǎn)個(gè)數(shù)。

圖1和圖2分別是時(shí)間和存儲(chǔ)空間與頂點(diǎn)規(guī)模的關(guān)系圖。

圖1 時(shí)間與頂點(diǎn)規(guī)模的關(guān)系圖

圖2 平均空間開銷與頂點(diǎn)規(guī)模的關(guān)系圖

從圖1和圖2可以獲知，文中算法無論在時(shí)間上還是空間上，隨著頂點(diǎn)規(guī)模的變大，其變化均為平緩，這就說明了該算法具有較好的收斂性和可擴(kuò)展性。

4.2 算法有效性分析

文中構(gòu)建了一個(gè)具有80個(gè)頂點(diǎn)的有向圖，來模擬現(xiàn)實(shí)具有80個(gè)實(shí)體的網(wǎng)絡(luò)環(huán)境；并假設(shè)每個(gè)頂點(diǎn)至少與15個(gè)頂點(diǎn)有弧，來表示實(shí)際網(wǎng)絡(luò)中每個(gè)實(shí)體至少和15個(gè)實(shí)體發(fā)生了直接交互；其弧上的數(shù)值是隨機(jī)產(chǎn)生的，且屬于[0,1]范圍，代表實(shí)體間的直接信任值。同時(shí)，蟻群的數(shù)量為30，α，β都為1。

圖3給出了信任路徑長(zhǎng)度與尋找到的信任路徑的關(guān)系。

圖3 信任路徑長(zhǎng)度與所尋找到的信任路徑數(shù)的關(guān)系

由圖3可知，當(dāng)選取的信任路徑長(zhǎng)度越大，所尋找的信任路徑就越多，則找到最佳信任路徑的可能性就越大，從而可更加有效地避免聯(lián)合欺詐行為，但算法效率將有所降低。

5 結(jié)束語

文中提出了一種改進(jìn)的動(dòng)態(tài)信任信息聚合算法。該算法利用蟻群算法和一種反饋信任值聚合函數(shù)，通過尋找多條較優(yōu)信任路徑，得到較為準(zhǔn)確的最終反饋信任值，能在一定程度上有效避免聯(lián)合欺詐行為。通過實(shí)驗(yàn)驗(yàn)證了該算法具有較好的收斂性和可擴(kuò)展性，從而能夠適應(yīng)現(xiàn)實(shí)復(fù)雜的、動(dòng)態(tài)多變的網(wǎng)絡(luò)環(huán)境。下一步的研究工作是如何通過調(diào)整算法中的相關(guān)參數(shù)，實(shí)現(xiàn)在保證反饋信任值準(zhǔn)確的情況下進(jìn)一步提高算法的效率。

[1] 李小勇，桂小林.大規(guī)模分布式環(huán)境下動(dòng)態(tài)信任模型研究[J].軟件學(xué)報(bào)，2007,18(6)：1510-1521.

[2] 易 磊.網(wǎng)格環(huán)境下信任模型及其應(yīng)用研究[D].長(zhǎng)沙:中南大學(xué)，2008.

[3] 農(nóng) 毅，古天龍.基于網(wǎng)格環(huán)境中的量化評(píng)估信任模型[J].計(jì)算機(jī)科學(xué)，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] 李小勇，桂小林，毛 倩，等.基于行為監(jiān)控的自適應(yīng)動(dòng)態(tài)信任度測(cè)模型[J].計(jì)算機(jī)學(xué)報(bào)，2009，32(4)：664-674.

[7] ?？伲鯌衙?，尹 剛．DyTrust：一種P2P系統(tǒng)中基于時(shí)間幀的動(dòng)態(tài)信任模型[J].計(jì)算機(jī)學(xué)報(bào)，2006，29(8)：1301-1307．

[8] 吳 鵬，吳國(guó)新，方 群．P2P網(wǎng)絡(luò)信譽(yù)機(jī)制研究綜述[J].計(jì)算機(jī)科學(xué)，2009，36(6)：26-28.

[9] 田春岐，江建慧，胡治國(guó)，等．一種基于聚集超級(jí)節(jié)點(diǎn)的P2P網(wǎng)絡(luò)信任模型[J]．計(jì)算機(jī)學(xué)報(bào)，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] 李小勇，桂小林，趙 娟，等.一種可擴(kuò)展的反饋信任信息聚合算法[J].西安交通大學(xué)學(xué)報(bào)，2007,41(8):879-883.

[13] 高承實(shí)，王建政，張 棟.基于蟻群算法的信任路徑尋找算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(15)：131-133.

[14] 張 瀟.基于蟻群算法的動(dòng)態(tài)信任模型研究[J].計(jì)算機(jī)與數(shù)字工程，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

時(shí)間：2016-02-18

國(guó)家自然科學(xué)基金資助項(xiàng)目(11241005)

王春紅(1965-)，女，教授，研究方向?yàn)槲谋咎幚?、?shù)據(jù)挖掘。

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