社會機會網(wǎng)絡(luò)中基于節(jié)點相似性的信任轉(zhuǎn)發(fā)算法

袁江濤　張振宇　楊文忠

(新疆大學信息科學與工程學院　新疆 烏魯木齊 830046)

?

社會機會網(wǎng)絡(luò)中基于節(jié)點相似性的信任轉(zhuǎn)發(fā)算法

袁江濤張振宇*楊文忠

(新疆大學信息科學與工程學院新疆 烏魯木齊 830046)

針對社會機會網(wǎng)絡(luò)中存在的自私節(jié)點，提出一種基于節(jié)點相似性的信任轉(zhuǎn)發(fā)算法。該算法首先計算了節(jié)點的路徑相似性和社交相似性；然后根據(jù)相似性強度確定節(jié)點間的信任關(guān)系，并將其量化為具體的信任值；最后引入消費心理學思想，選取穩(wěn)定性較高的信任節(jié)點作為轉(zhuǎn)發(fā)節(jié)點。實驗表明，與經(jīng)典轉(zhuǎn)發(fā)算法對比，該算法在含有自私節(jié)點的網(wǎng)絡(luò)環(huán)境中能保證數(shù)據(jù)可靠傳遞。

社會機會網(wǎng)絡(luò)節(jié)點相似度信任關(guān)系數(shù)據(jù)轉(zhuǎn)發(fā)自私節(jié)點

0　引　言

近年來，隨著智能手機、穿戴設(shè)備、平板電腦等短距離無線移動設(shè)備的普及，使得以人為載體的移動設(shè)備利用相遇機會進行通信成為可能，這種通過人類移動進行機會式通信的網(wǎng)絡(luò)一般稱為社會機會網(wǎng)絡(luò)[1]。由于真實網(wǎng)絡(luò)環(huán)境中，節(jié)點設(shè)備的移動規(guī)律和活動區(qū)域會受到人類行為的影響，節(jié)點經(jīng)常表現(xiàn)出“小世界”現(xiàn)象[2]，同時網(wǎng)絡(luò)中節(jié)點內(nèi)存、能量、帶寬等資源有限，所以節(jié)點基于自身利益可能會拒絕轉(zhuǎn)發(fā)數(shù)據(jù)而表現(xiàn)出自私行為[3]，嚴重影響網(wǎng)絡(luò)性能的可靠性。

機會網(wǎng)絡(luò)中已有的信任轉(zhuǎn)發(fā)算法主要通過節(jié)點的相關(guān)信息評價節(jié)點信任，從而找出信任節(jié)點作為可靠轉(zhuǎn)發(fā)節(jié)點。文獻[4]在不同的中間節(jié)點尋找不同轉(zhuǎn)發(fā)節(jié)點的共同興趣和朋友，以此衡量信任關(guān)系，但是在大規(guī)模的機會網(wǎng)絡(luò)會造成較高延遲時間。文獻[5]引入社會網(wǎng)絡(luò)的朋友關(guān)系，依據(jù)節(jié)點間共同朋友數(shù)量、Prophet預測轉(zhuǎn)發(fā)能力、節(jié)點流行度算法綜合評價節(jié)點信任度，有效提高了數(shù)據(jù)轉(zhuǎn)發(fā)效率，但該方法需要較長的準備時間建立節(jié)點間的朋友關(guān)系。文獻[6]通過目的節(jié)點發(fā)送給源節(jié)點的反饋數(shù)據(jù)包數(shù)量衡量節(jié)點信任度，并利用反饋數(shù)據(jù)包識別自私節(jié)點，但有時大量的反饋數(shù)據(jù)包會造成網(wǎng)絡(luò)局部擁堵的情況。文獻[7]利用機會網(wǎng)絡(luò)網(wǎng)絡(luò)拓撲結(jié)構(gòu)、跳數(shù)距離、交互時間、交互頻率建立節(jié)點間的信任關(guān)系，通過該關(guān)系進一步確定節(jié)點的真實身份，從而有效抵抗“女巫”攻擊，但是在節(jié)點松散的網(wǎng)絡(luò)環(huán)境中，網(wǎng)絡(luò)的轉(zhuǎn)發(fā)效率較低。文獻[8]在Spray-and-Wait基礎(chǔ)上，每個節(jié)點通過歷史交互次數(shù)評價相遇節(jié)點的信任等級，利用信任級別避開向自私節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。但是在自私節(jié)點數(shù)量較多時，其信任評價的準確性較差。社會機會網(wǎng)絡(luò)作為一種特殊的機會網(wǎng)絡(luò)，目前針對該網(wǎng)絡(luò)的信任轉(zhuǎn)發(fā)算法相對較少，如何確保數(shù)據(jù)轉(zhuǎn)發(fā)在社會機會網(wǎng)絡(luò)中不受自私節(jié)點干擾是一個重要問題。

本文從社會學的角度出發(fā)，提出一種基于社會節(jié)點相似性的信任轉(zhuǎn)發(fā)算法。通過對網(wǎng)絡(luò)整體區(qū)域的劃分，對比不同節(jié)點間的移動軌跡和不同區(qū)域內(nèi)節(jié)點的社交情況，計算節(jié)點間的路徑相似性和社交相似性，從而量化節(jié)點間的信任度；同時依據(jù)消費心理學思想計算信任穩(wěn)定性，選擇穩(wěn)定性較強的節(jié)點作為數(shù)據(jù)的轉(zhuǎn)發(fā)節(jié)點，降低自私節(jié)點對數(shù)據(jù)轉(zhuǎn)發(fā)的影響。

1　基于節(jié)點相似性的信任轉(zhuǎn)發(fā)算法

1.1計算路徑相似性和社交相似性

結(jié)合現(xiàn)實社會環(huán)境與社會成員的生活經(jīng)驗，經(jīng)常在相同區(qū)域內(nèi)活動的不同社會成員可以得到較多的交互機會，可逐漸建立起較為熟悉的關(guān)系[9]，例如學生在上課時間段內(nèi)會聚集在學校、喜愛電影的人經(jīng)常會在休閑時間段內(nèi)聚集在電影院、消費者在市場的正常營業(yè)時間段內(nèi)聚集在市場等。根據(jù)活動場合的性質(zhì)和類型，不同的社會成員會聚集成不同的團體，使得不同社會成員間活動范圍經(jīng)常重疊在一起。

通過分析社會網(wǎng)絡(luò)中同一區(qū)域內(nèi)具有相同移動路徑的社會成員關(guān)系，以及社會成員在不同區(qū)域內(nèi)的關(guān)系，了解到社會成員間的關(guān)系與其活動的場合密切相關(guān)，經(jīng)常在相同區(qū)域內(nèi)活動的不同社會成員可以得到較多的交互機會，逐漸建立起較為熟悉的關(guān)系。因此，社會機會網(wǎng)絡(luò)節(jié)點通過模仿上述關(guān)系的建立過程，根據(jù)節(jié)點的路徑相似性和社交相似性，共同構(gòu)建節(jié)點的信任關(guān)系，抵抗節(jié)點自私行為對數(shù)據(jù)轉(zhuǎn)發(fā)的影響。

1.1.1路徑相似性

在社會機會網(wǎng)絡(luò)中，節(jié)點的移動速度、方向、線路等都是由社會成員控制的，社會成員利用社會活動建立社會關(guān)系的同時，也給節(jié)點之間帶來了建立關(guān)系的機會，例如經(jīng)常在同一條路徑上相遇的社會成員更容易建立一定的社會關(guān)系。因此，可以對比不同節(jié)點的路徑相似性，從而確定節(jié)點間的信任關(guān)系。

(1)

另外，隨著節(jié)點不斷移動，每個節(jié)點的移動路徑也在不斷變化，對于一定時間內(nèi)不再訪問的區(qū)域，需要對移動路徑進行更新，以保證最近時間內(nèi)經(jīng)過的區(qū)域為當前移動路徑。所以，每個節(jié)點記錄了前一次進入某一子區(qū)域的時間tin、前一次移出某一子區(qū)域的時間tout和當前時間tnow，對位置矩陣進行更新的計算方法如下式所示：

(2)

式中round()為取整函數(shù)，LUpdate(tin,tout,tnow)表示某一子區(qū)域的更新值，只有更新值低于閾值φ，才將位置矩陣中該區(qū)域的標記位重置為0，反之，則維持標記位的原狀態(tài)。

1.1.2社交相似性

一般情況下，不同社會成員的共同朋友數(shù)量可以在一定意義上說明成員間的關(guān)系強度[11]，共同朋友的數(shù)量越多，兩者之間的關(guān)系越緊密，例如同一個班的學生往往認識全班的所有同學，彼此之間能建立良好的信任關(guān)系。所以，在社會機會網(wǎng)絡(luò)中可以對比節(jié)點間的社交相似性，反映節(jié)點間的信任關(guān)系。

首先，節(jié)點需要用鄰接鏈表記錄各子區(qū)域內(nèi)的交互節(jié)點數(shù)量，鄰接鏈表的頭結(jié)點由子區(qū)域名稱的數(shù)據(jù)域和指向鏈表第一個節(jié)點的指針組成，表節(jié)點是由鄰節(jié)點域、記錄交互節(jié)點名稱的數(shù)據(jù)域、指向鏈表下一個節(jié)點的指針組成。如果節(jié)點i在1區(qū)域分別與節(jié)點b和節(jié)點u交互，則將節(jié)點b和節(jié)點u按照相遇順序添加到1區(qū)域后面，表示節(jié)點i在1區(qū)域有兩次交互記錄。

(3)

Deci,j(tlast,tnow)=e-round(tnow-tlast)

(4)

1.1.3信任計算

在社會機會網(wǎng)絡(luò)中，對比不同節(jié)點的路徑相似性和社交相似性即可確定節(jié)點間的信任關(guān)系。采用加權(quán)求和的方法結(jié)合節(jié)點間的路徑相似性和社交相似性，即可得到節(jié)點間的信任度Ti,j，如式(5)和式(6)所示：

Simi,j=α·LSim(Li,Lj)+β·FSim(Fi,Fj)

(5)

Ti,j=Simi,j

(6)

式(5)中Simi,j表示節(jié)點j和i的總體相似度，α和β分別表示路徑相似性和社交相似性在總體相似度中所占的權(quán)重系數(shù)，α,β∈(0,1)且α+β=1，由于α和β的權(quán)重控制要依據(jù)節(jié)點評價信任的環(huán)境來確定，同時要體現(xiàn)信任評價的主觀性和動態(tài)性[12]，所以權(quán)重分配方法如式(7)和式(8)所示：

(7)

(8)

1.2信任轉(zhuǎn)發(fā)過程

從消費心理學[13]可知，社會成員在商場購買商品時，更傾向于選擇質(zhì)量具有穩(wěn)定性保障的商品。本算法在選擇信任節(jié)點作為轉(zhuǎn)發(fā)節(jié)點時，可以根據(jù)節(jié)點的歷史評價信任值考察節(jié)點信任的穩(wěn)定性，在信任節(jié)點中選擇穩(wěn)定性最佳的節(jié)點作為數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳節(jié)點，進一步描述信任評價的準確性，保證數(shù)據(jù)轉(zhuǎn)發(fā)的可靠性。

假設(shè)節(jié)點i對節(jié)點j的歷史信任值序列為T1 i,j,T2 i,j,T3 i,j,…,Th i,j，h表示節(jié)點i對節(jié)點j的第h次信任評價，其信任穩(wěn)定性的計算方法如式(9)和式(10)所示：

(9)

(10)

信任轉(zhuǎn)發(fā)的具體過程可分為如下幾步：

1.3算法復雜度分析

算法的時間復雜度主要取決于交互節(jié)點的數(shù)量和網(wǎng)絡(luò)劃分的規(guī)模。假設(shè)場景中節(jié)點數(shù)量m，網(wǎng)絡(luò)劃分的規(guī)模為n×n，算法最壞的情況為某一節(jié)點與其他n-1個節(jié)點相遇，此時算法的復雜度為O(mn2)，最好的情況為某個節(jié)點只與單個節(jié)點相遇，此時算法的計算復雜度為O(n2)?？紤]到現(xiàn)實網(wǎng)絡(luò)中的情況介于最壞的情況與最好的情況之間，該算法的計算復雜度介于O(n2)和O(mn2)之間。另外，由于整個評價算法的存儲數(shù)據(jù)和輸入輸出數(shù)據(jù)中包含二維表和一維數(shù)組等，所以該評價算法的空間復雜度為O(n)。

2　實驗仿真

本文使用仿真工具ONE 1.4.1[14]對提出的信任轉(zhuǎn)發(fā)算法進行評估，先將城市街道地圖劃分為若干200 m×200 m的放行區(qū)域，同時設(shè)置200個節(jié)點，每個節(jié)點采用藍牙通信方式，通信半徑為10 m，節(jié)點移動速度為1～3 km/h，數(shù)據(jù)傳輸速率為200 Kbps，環(huán)境參數(shù)具體設(shè)置如表1所示。

表1　仿真環(huán)境參數(shù)設(shè)置

為了考察提出算法優(yōu)劣，本文以傳輸成功率和平均延遲時間兩個指標進行衡量。實驗分為兩組，分別對比在不同自私節(jié)點情況下，Epidemic[15]、Prophet[16]、Spray-and-Waits[17]三種轉(zhuǎn)發(fā)方式，在沒有使用信任算法和使用信任算法情況下的傳輸成功率和平均延遲時間，同時給出仿真結(jié)果，并分析其原因。

2.1傳輸成功率

如圖1、圖2、圖3所示，分別在1000 m×1000 m、2000 m×2000 m、3000 m×3000 m的區(qū)域內(nèi)，不同自私節(jié)點比例下，對比沒有使用信任算法的Epidemic、Prophet、Spray-and-Wait和在使用信任算法的T-Epidemic、T-Prophet、T-Spray-and-Wait傳輸成功率。

圖1　1000 m×1000 m區(qū)域內(nèi)的傳輸成功率

圖2　2000 m×2000 m區(qū)域內(nèi)的傳輸成功率

圖3　3000 m×3000 m區(qū)域內(nèi)的傳輸成功率

從圖1-圖3可知，3種轉(zhuǎn)發(fā)方式在沒有使用信任算法的情況下，隨著網(wǎng)絡(luò)區(qū)域面積的增大，傳輸成功率逐漸降低，總體趨勢都是隨著自私節(jié)點比例的增加而降低。當自私節(jié)點比例增長到50%或60%時，三種路由的傳輸成功率基本為0，只有極少量的數(shù)據(jù)可以傳輸成功，網(wǎng)絡(luò)已基本處于崩潰狀態(tài)。在使用信任算法的情況下，雖然傳輸成功率的趨勢是隨著自私節(jié)點比例的增高而降低，然而通過建立的信任關(guān)系，有效保證了數(shù)據(jù)轉(zhuǎn)發(fā)的可靠性，降低了自私節(jié)點對數(shù)據(jù)轉(zhuǎn)發(fā)過程的影響。

另外，通過對比同一網(wǎng)絡(luò)區(qū)域面積內(nèi)三種轉(zhuǎn)發(fā)方式的傳輸成功率，Epidemic在自私節(jié)點比例較低時，其傳輸成功率比其他兩種路由模式的傳輸成功率較高； Prophet在自私節(jié)點比例較高時，其傳輸成功率較高；Spray-and-Wait的傳輸成功率總體表現(xiàn)較為一般。這種情況可能是由于Epidemic在自私節(jié)點影響較小的情況下，其洪泛轉(zhuǎn)發(fā)機制提高了數(shù)據(jù)的傳輸成功率，但是在自私節(jié)點影響較大的情況下，Epidemic的大量數(shù)據(jù)包被自私節(jié)點劫持，只有少量的數(shù)據(jù)在部分信任度較高的節(jié)點之間傳遞，使其傳輸成功率急速下降。Prophet由于本身帶有目的節(jié)點預測能力，再配合信任策略建立節(jié)點間的信任關(guān)系，使其在隨著自私節(jié)點比例增高的情況下，傳輸成功率下降速度較慢。Spray-and-Wait是在Epidemic基礎(chǔ)上改進的轉(zhuǎn)發(fā)算法，其性能介于Prophet和Epidemic之間。

2.2平均延遲時間

如圖4、圖5、圖6所示，分別在1000 m×1000 m、2000 m×2000 m、3000 m×3000 m的區(qū)域內(nèi)，不同自私節(jié)點比例下，對比沒有使用信任算法的Epidemic、Prophet、Spray-and-Wait和在使用信任算法的T-Epidemic、T-Prophet、T-Spray-and-Wait平均延遲時間。

圖4　1000 m×1000 m的區(qū)域內(nèi)的平均延遲時間

圖5　2000 m×2000 m的區(qū)域內(nèi)的平均延遲時間

圖6　3000 m×3000 m的區(qū)域內(nèi)的平均延遲時間

從圖4-圖6可知，隨著網(wǎng)絡(luò)區(qū)域面積的增大，數(shù)據(jù)傳輸?shù)钠骄舆t時間逐漸增長。3種轉(zhuǎn)發(fā)方式在沒有使用信任算法的情況下，數(shù)據(jù)轉(zhuǎn)發(fā)的平均延遲時間是隨著自私節(jié)點比例的增加而快速增長；在使用信任算法的情況下，隨著自私節(jié)點比例的增高，數(shù)據(jù)傳輸?shù)难舆t時間得到了有效降低，減緩了平均延遲時間的增長趨勢。

通過對比觀察同一網(wǎng)絡(luò)區(qū)域面積內(nèi)三種轉(zhuǎn)發(fā)方式的平均延遲時間，當自私節(jié)點比例低于50%或60%時，Spray-and-Wait的平均延遲時間低于Prophet和Epidemic的平均延遲時間， Prophet由于其轉(zhuǎn)發(fā)數(shù)據(jù)包相對較少，在自私節(jié)點的影響下，其平均延遲時間比Epidemic和Spray-and-Wait都高。當自私節(jié)點比例低于50%或60%時，Prophet通過自身預測轉(zhuǎn)發(fā)并配合信任算法，在自私比例相對較高時，平均延遲時間要低于Epidemic和Spray-and-Wait。

3　結(jié)　語

本文從社會學角度出發(fā)，在社會機會網(wǎng)絡(luò)中，提出一種基于節(jié)點相似性的信任轉(zhuǎn)發(fā)算法。利用節(jié)點的移動路徑和社交情況描述節(jié)點間的相似性，從而反映出節(jié)點間的信任關(guān)系，一方面完善了社會機會網(wǎng)絡(luò)節(jié)點的信任評價過程，另一方面有效解決了自私節(jié)點對數(shù)據(jù)轉(zhuǎn)發(fā)的影響。仿真結(jié)果表明，與經(jīng)典轉(zhuǎn)發(fā)算法相比，該轉(zhuǎn)發(fā)算法在含有自私節(jié)點的網(wǎng)絡(luò)環(huán)境中能保證數(shù)據(jù)的高效傳遞。

[1] Boldrini C,Conti M,Passarelia A.Exploiting users’ social relations to forward data in opportunistic networks:The HiBOp solution[J].Pervasive and Mobile Computing,2008,4(5):633-657.

[2] Golbeck J,Hendler J.Inferring binary trust relationships in web-based social networks[J].ACM Transactions on Internet Technology (TOIT),2006,6(4):497-529.

[3] Mtibaaa,Harras K A.Social-Based Trust Mechanisms in Mobile Opportunistic Networks[J].Proc.IEEE SIMNA,2011,2011,5(3):34-39.

[4] Becker C,Schlinga S,Fischer S.Trustful Data Forwarding in Social Opportunistic Networks[C]//Ubiquitous Intelligence and Computing,2013 IEEE 10th International Conference on and 10th International Conference on Autonomic and Trusted Computing (UIC/ATC).IEEE,2013:430-437.

[5] Premaltha S,Mary Anita Rajam V.Reputation management for data forwarding in opportunistic networks[C]//Computer Communication and Informatics (ICCCI),2014 International Conference on.IEEE,2014:1-7.

[6] Trifunovic S,Legendre F,Anastasiades C.Social trust in opportunistic networks[C]//INFOCOM IEEE Conference on Computer Communications Workshops,2010.IEEE,2010:1-6.

[7] Al-hinal A,Zhang H,Chen Y,et al.TB-SnW:Trust-based Spray-and-Wait routing for delay-tolerant networks[J].The Journal of Supercomputing,2014,69(2):1-17.

[8] Dend S,Hhang L,Xu G.Social network-based service recommendation with trust enhancement[J].Expert Systems with Applications,2014,41(18):8075-8084.

[9] Gallos L K,Makse H A,Sigman M.A small world of weak ties provides optimal global integration of self-similar modules in functional brain networks[J].Proceedings of the National Academy of Sciences,2012,109(8):2825-2830.[10] Callahan E,Agarwal A,Cheever C,et al.Determining a trust level of a user in a social network environment:U.S.Patent 8,656,463[P].2014-2-18.

[11] Conti M,Giordano S,May M,et al.From opportunistic networks to opportunistic computing[J].Communications Magazine,IEEE,2010,48(9):126-139.

[13] Keranen A.Opportunistic network environment simulator[OL].[2008-5-29],http://www.netlab.tkk.fi/tutkimus/dtn/theone.

[14] Ramanathan R,Hansen R,Basu P,et al.Prioritized epidemic routing for opportunistic networks[C]//Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking.ACM,2007:62-66.

[15] Huang T K,Lee C K,Chen L J.Prophet+:An adaptive prophet-based routing protocol for opportunistic network[C]//Advanced Information Networking and Applications (AINA),2010 24th IEEE International Conference on.IEEE,2010:112-119.

[16] Huang W,Zhang S,Zhou W.Spray and wait routing based on position prediction in opportunistic networks[C]//Computer Research and Development (ICCRD),2011 3rd International Conference on.IEEE,2011,2:232-236.

TRUST FORWARDING ALGORITHM IN SOCIAL OPPORTUNISTIC NETWORKS BASED ON NODE SIMILARITY

Yuan JiangtaoZhang Zhenyu*Yang Wenzhong

(School of Information Science and Engineering,Xinjiang University,Urumqi 830046,Xinjiang,China)

To address the problem of existence of selfish nodes in social opportunistic networks,we propose a node similarity-based trust forwarding algorithm.First the algorithm calculates the node path similarity and social similarity; then it determines the trust relationships between nodes based on the similarity strength,and quantifies them to specific trust value; finally it introduces the consumer psychology idea,and chooses the trust nodes with higher stability as the forwarding nodes.It is demonstrated by experiment that comparing with traditional forwarding algorithm,this algorithm guarantees the reliable messages transmission in a network environment containing selfish nodes.

Social opportunistic networksNode similarityTrust relationshipData forwardingSelfish node

2015-04-05。國家自然科學基金項目(61262089,61262087);新疆教育廳高校教師科研計劃重點項目(XJEDU2012I09)。袁江濤，碩士生，主研領(lǐng)域：機會網(wǎng)絡(luò)。張振宇，副教授。楊文忠，副教授。

TP393

A

10.3969/j.issn.1000-386x.2016.09.023