社會機會網絡中基于節點相似性的信任轉發算法

袁江濤　張振宇　楊文忠

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

?

社會機會網絡中基于節點相似性的信任轉發算法

袁江濤張振宇*楊文忠

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

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

社會機會網絡節點相似度信任關系數據轉發自私節點

0　引　言

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

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

本文從社會學的角度出發，提出一種基于社會節點相似性的信任轉發算法。通過對網絡整體區域的劃分，對比不同節點間的移動軌跡和不同區域內節點的社交情況，計算節點間的路徑相似性和社交相似性，從而量化節點間的信任度；同時依據消費心理學思想計算信任穩定性，選擇穩定性較強的節點作為數據的轉發節點，降低自私節點對數據轉發的影響。

1　基于節點相似性的信任轉發算法

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

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

通過分析社會網絡中同一區域內具有相同移動路徑的社會成員關系，以及社會成員在不同區域內的關系，了解到社會成員間的關系與其活動的場合密切相關，經常在相同區域內活動的不同社會成員可以得到較多的交互機會，逐漸建立起較為熟悉的關系。因此，社會機會網絡節點通過模仿上述關系的建立過程，根據節點的路徑相似性和社交相似性，共同構建節點的信任關系，抵抗節點自私行為對數據轉發的影響。

1.1.1路徑相似性

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

(1)

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

(2)

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

1.1.2社交相似性

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

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

(3)

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

(4)

1.1.3信任計算

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

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

(5)

Ti,j=Simi,j

(6)

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

(7)

(8)

1.2信任轉發過程

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

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

(9)

(10)

信任轉發的具體過程可分為如下幾步：

1.3算法復雜度分析

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

2　實驗仿真

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

表1　仿真環境參數設置

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

2.1傳輸成功率

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

圖1　1000 m×1000 m區域內的傳輸成功率

圖2　2000 m×2000 m區域內的傳輸成功率

圖3　3000 m×3000 m區域內的傳輸成功率

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

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

2.2平均延遲時間

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

圖4　1000 m×1000 m的區域內的平均延遲時間

圖5　2000 m×2000 m的區域內的平均延遲時間

圖6　3000 m×3000 m的區域內的平均延遲時間

從圖4-圖6可知，隨著網絡區域面積的增大，數據傳輸的平均延遲時間逐漸增長。3種轉發方式在沒有使用信任算法的情況下，數據轉發的平均延遲時間是隨著自私節點比例的增加而快速增長；在使用信任算法的情況下，隨著自私節點比例的增高，數據傳輸的延遲時間得到了有效降低，減緩了平均延遲時間的增長趨勢。

通過對比觀察同一網絡區域面積內三種轉發方式的平均延遲時間，當自私節點比例低于50%或60%時，Spray-and-Wait的平均延遲時間低于Prophet和Epidemic的平均延遲時間， Prophet由于其轉發數據包相對較少，在自私節點的影響下，其平均延遲時間比Epidemic和Spray-and-Wait都高。當自私節點比例低于50%或60%時，Prophet通過自身預測轉發并配合信任算法，在自私比例相對較高時，平均延遲時間要低于Epidemic和Spray-and-Wait。

3　結　語

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

[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)。袁江濤，碩士生，主研領域：機會網絡。張振宇，副教授。楊文忠，副教授。

TP393

A

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