機會網絡中基于社會信任的數據轉發算法

袁江濤，張振宇，楊文忠

（新疆大學 信息科學與工程學院，新疆 烏魯木齊830046）

0 引 言

機會網絡不需要源節點和目的節點之間存在完整鏈路，通過節點移動帶來的相遇機會以 “存儲－攜帶－轉發”的方式實現節點間通信［1，2］，但在真實網絡環境中，節點的內存、能量等資源有限，節點基于自身利益可能會拒絕轉發消息而表現出自私行為［3］，嚴重影響網絡服務的可靠性，甚至破壞網絡正常運行。

針對機會網絡中的自私節點，一些信任轉發方法被提出，這些方法在經典的Epidemic［4］、Prophet［5］、Sprayand－Wait［6］等數據轉發算法基礎上，利用節點的相關信息評價節點信任，找出信任節點作為可靠轉發節點。其中，信任的評價方式可以分為基于反饋信息、基于交互信息和基于跳數距離3類。目前，由人攜帶的移動設備構成的機會網絡在社會中得到普遍的應用，如何確保數據轉發在此種機會網絡中不受自私節點干擾是一個重要問題。

1 相關工作

文獻 ［7］在Prophet基礎上，引入 “看門狗”機制統計反饋消息數量度量節點信任值，選取合適的節點轉發數據，但這種方法在網絡規模較大時，對網絡資源的消耗過大；文獻 ［8］在Spray－and－Wait基礎上，每個節點通過歷史交互次數評價相遇節點的信任等級，利用信任級別繞過自私節點，但是在自私節點數量較多時，其信任評價的準確度較差；文獻 ［9］按照路徑上每個節點到目的節點的跳數度量節點信任值，再將數據依次從低信任節點發往高信任節點，該方法雖然可以抵抗自私節點的攻擊，但在自私節點較多時，部分自私節點依然可以僥幸獲得數據。

當網絡設備由人來攜帶時，節點設備會具備人的社會屬性，比如：熟悉度、親密度等。不同的社會屬性可以構成節點的社會信任，反映節點的信任強度［10］。基于這種聯系，可引入社會網絡思想研究機會網絡信任轉發問題［11］。文獻［12］提出一種基于社會信任的機會網絡信任模型，該模型利用網絡拓撲結構和跳數距離建立的節點關系和歷史交互信息確認的節點友好度來評價節點信任，有效抵抗了女巫攻擊。

為了能在具有社會屬性的機會網絡中避免將數據轉發到自私節點，同時克服以往信任轉發算法在自私節點較多時，存在轉發延遲較高、信任評價不準確等問題。本文在Epidemic的基礎上，提出一種基于社會信任的數據轉發算法ST－Epidemic（social trust Epidemic），利用Epidemic高轉發效率，依據節點接觸次數、連接時間、接收次數、轉發次數描述機會網絡節點的社會屬性，構建節點間的信任關系，選取信任節點作為轉發節點，避開自私節點對數據轉發的干擾。

2 基于社會信任的轉發算法

2.1 社會信任的度量

在社會網絡中，社會信任是指一定社會成員之間相互認同、信任并進行真誠交往的現象［13］。社會信任可由社會關系決定，而社會關系又是由社會成員的社會屬性構成，所以根據不同的社會屬性可以構建節點的社會信任，并反映節點間的信任強度［14］。基于這種聯系，可引入社會信任的思想解決機會網絡信任轉發問題。

社會心理學認為信任關系是通過人與人之間的交流建立的［12］。通常相見頻率越高，彼此間就越熟悉。在地理位置上距離越近，相互交流的時間越長，親密度就越高。此外根據人的歷史行為可判斷其可靠性，如商人間的信任度會隨著成功交易次數的增加而提高。

因此通過機會網絡節點模仿人的移動方式，完成與其它節點必要的交互，根據節點間的相見頻率、交流時間、歷史行為構建節點的熟悉度、親密度、服務度3個社會屬性，共同構建節點的社會信任。

2.1.1 熟悉度

機會網絡中每個節點的地位都是相互平等的，隨著節點的移動，節點會接觸若干不同的節點，并且與不同節點的接觸頻率各不相同。在轉發數據的過程中，可以選取較熟悉的節點作為轉發節點，節點熟悉度的定義如下

2.1.2 親密度

一般網絡中可能存在不同節點與某一節點熟悉度相近情況，此時熟悉度不能全面衡量節點的社會信任，這主要有兩個方面原因，一方面是實際場景中存在的自私節點在不停地移動，自私節點可能與正常節點具有較高的接觸頻率，自私節點會依此騙取正常節點的信任；另一方面，在數據轉發過程中要保證數據有足夠的時間發送到下一跳節點，只有節點之間連接時間越長，才能保證轉發數據的完整性。

所以根據社會網絡熟人圈思想［11］，在節點的接觸頻率基礎上，同時考慮節點間的連接時間，可以更加準確地描述節點的社會信任。所以節點親密度的定義如下

2.1.3 服務度

由于正常節點能幫助其它節點及時轉發數據，自私節點只能接收數據不轉發數據，網絡中節點可通過交換各自記錄的數據接收和轉發次數衡量對方的服務度。所以通過服務度不僅可以反映節點的轉發可靠性，而且能有效地區分出自私節點和正常節點。服務度的定義如下

式中：servi，j——節點j對節點i 的服務程度，且servi，j∈［0，1］，trani，j——節點j幫助節點i完成的數據轉發次數，recei，j——節點j接收節點i的數據次數，此處節點j接收次數recei，j必然大于或等于節點轉發次數trani，j。

2.1.4 信任計算

由于社會信任是通過綜合考慮不同社會屬性得出，所以社會信任的計算采取加權求和的方式，具體表示為

式中：Ti，j——節點j對節點i的社會信任，α、β、γ——熟悉度、親密度、服務度在社會信任中的權重，α，β，γ ∈（0，1］且α＋β＋γ＝1。

考慮到節點的社會信任是從3個不同的社會屬性角度進行描述，共同構成節點社會信任的基礎，權值的具體分配如下

為了體現信任評價的主觀性［11］，在確定3個權重系數的過程中，首先給定γ，因為在3個社會屬性中，服務度不僅描述了節點的社會屬性，而且能逐漸區分出自私節點和正常節點，服務度對社會信任的貢獻最大。其次，節點間的接觸頻率和連接時間各不相同，在不同的情況下節點會偏重不同的社會屬性度量與其它節點的信任強度。所以利用不同節點對熟悉度和親密度的偏重程度，由節點的熟悉度和親密度確定α和β，如式 （5）、式 （6）所示。

在節點i計算出節點j 的社會信任Ti，j后，規定θ為信任轉發閾值，當Ti，j≥θ時，認為該節點為信任節點并向該節點發送數據；當Ti，j≤θ時，認為該節點為自私節點。拒絕向該節點發送數據。

2.2 基于社會信任的轉發過程

ST－Epidemic是通過判斷節點的社會信任值進行數據轉發。若節點i首次向節點j 轉發數據，則根據節點的初始信任值直接向節點j 轉發數據，若非首次轉發，則通過fami，j、intii，j、servi，j計算節點j 對源節點i 的社會信任Ti，j，如果Ti，j達到信任轉發閾值，則向節點j轉發數據，反之，則拒絕向節點j轉發數據，具體如算法1所示。

算法1：ST－Epidemic數據轉發算法

輸入：fami，j、intii，j、servi，j、Ti，j←θ、trani，j←0

輸出：信任節點集合TR［j］節點

上述算法過程中設置節點的初始信任值θ是為了更快地促使節點建立信任關系，為后續數據轉發提供更好的信任基礎。比如初次向某個節點轉發數據，若該節點是正常節點，它會繼續向其它節點轉發數據，若該節點是自私節點，它不會向其它節點轉發任何數據，通過這種試探性的方法可能會丟失小部分數據包，但可以幫助節點更快地分辨出正常節點和自私節點，所以設置初始信任值為θ是有必要的。

2.3 算法復雜度分析

從上述轉發算法流程看，整個算法的計算復雜度取決于相遇節點的數量、待轉發的數據包數量以及信任轉發閾值θ。場景中節點數量為n，待轉發的最大數據包數量為m，信任轉發閾值θ∈（0，1）。如果θ設定較高，則會提高相遇節點的信任要求，使得數據轉發次數下降、轉發延遲過高，降低算法效率。如果θ設定較低，則會提高數據的轉發次數，但也會提高自私節點對數據轉發的影響。因此，算法最壞的情況為某一節點與其它n－1個節點相遇且所有相遇節點的信任都滿足θ，此時算法的計算復雜度為O（nm）。最好的情況為相遇節點的信任都不滿足θ，此時算法的計算復雜度為O（n）。考慮到現實網絡中的情況，該算法的計算復雜度介于O（n）和O（nm）之間。

3 實驗仿真

本文利用仿真工具ONE 1.4.1［15］設計的場景對提出的轉發算法進行評估。節點移動方式為ShortestPathMap－BasedMovement（SPMBM），具體仿真環境參數設置見表1。

表1 實驗仿真環境

為了考察ST－Epidemic數據轉發算法的優劣，本文從傳輸成功率和平均延遲時間兩個指標進行衡量。實驗分為兩組，分別對比在不同自私節點比例時，ST－Epidemic、Epi－demic、Prophet、Spray－and－Waits4種轉發方式的傳輸成功率和平均延遲時間，同時給出實驗仿真結果，并分析其原因。

3.1 傳輸成功率

圖1和圖2分別展示了在30%和70%的自私節點比例情況下4種轉發方式的傳輸成功率。

圖1 傳輸成功率

圖2 傳輸成功率

實驗初期，ST－Epidemic 的傳輸成功率與Epidemic、Prophet、Spray－and－Wait轉發方式相近，但隨著節點交互次數增多，ST－Epidemic的傳輸成功率逐漸高于Epidemic、Prophet、Spray－and－Wait這3 種轉發方式。由于實驗初期節點間的信任關系還處在建立過程中，可能存在正常節點被暫時誤判為自私節點的情況，所以ST－Epidemic的傳輸成功率增長趨勢較緩。而在實驗后期，一方面是由于正常節點之間逐漸建立起良好的信任關系，數據在信任節點之間被安全地轉發；另一方面由于自私節點拒絕幫助其它節點轉發數據，自私節點的服務度較低，致使自私節點的社會信任值也較低，正常節點通過信任判斷逐漸避開向自私節點轉發數據，從而使ST－Epidemic的傳輸成功率快速增長。

圖3展示了ST－Epidemic、Epidemic、Prophet、Sprayand－Wait這4種轉發方式的在不同自私節點比例的情況下的傳輸成功率。隨著自私節點比例增大，ST－Epidemic、Epidemic、Prophet、Spray－and－Wait這4 種轉發方式的傳輸成功率都在下降，而ST－Epidemic的下降趨勢較緩。雖然在自私節點比例小于30% 時，Epidemic、Prophet、Spray－and－Wait這3種轉發方式的傳輸成功率高于ST－Epi－demic轉發方式，但是在自私節點比例大于30%時，STEpidemic轉發方式的傳輸成功率卻高于其它3種轉發方式。主要原因是自私節點對Epidemic、Prophet、Spray－and－Wait的轉發過程造成了嚴重的影響，大量的轉發數據被自私節點截獲并刪除，導致數據的傳輸成功率快速下降。而ST－Epidemic在不同自私節點比例的情況下，通過已建立的信任關系確保了數據在信任節點之間有效地轉發，減緩了傳輸成功率的下降趨勢。

圖3 傳輸成功率

3.2 平均延遲時間

圖4和圖5展示了在30%和70%的自私節點比例情況下4種轉發方式的平均延遲時間。

圖4 平均延遲時間

圖5 平均延遲時間

實驗初期ST－Epidemic的平均延遲時間基本介于Epidemic和Spray－and－Wait之間，而在實驗后期ST－Epidemic的平均延遲時間短于其它3種轉發方式，這是由于在實驗初期存在正常節點被誤判為自私節點的情況，造成ST－Epidemic的平均延遲時間與其它轉發方式相近，實驗后期由于節點之間的信任關系已經開始建立，正常節點逐漸避開向自私節點轉發數據，數據被自私節點干擾的情況減少，所以平均延遲時間得到較大地縮短。

圖6展示了ST－Epidemic、Epidemic、Prophet、Sprayand－Wait這4種轉發方式的在不同自私節點比例的情況下的平均延遲時間。隨著自私節點比例的不斷增加，ST－Epidemic、Epidemic、Prophet、Spray－and－Wait這4 種轉發方式的平均延遲時間都在增加，但ST－Epidemic的上升趨勢較緩。在自私節點比例小于30%時，ST－Epidemic的平均延遲時間略長于Epidemic和Spray－and－Wait轉發方式。而在自私節點比例大于30%時，ST－Epidemic的平均延遲時間短于其它3種轉發方式的平均延遲時間。這是因為ST－Epidemic建立的信任關系有效阻止了自私節點的干擾，減緩了平均延遲時間的上升，而Epidemic、Prophet、Spray－and－Wait在數據轉發過程中被自私節點嚴重影響，降低了數據發送到目的節點的概率，從而使平均延遲時間迅速增加。

圖6 平均延遲時間

4 結束語

本文從社會學的角度出發，針對由人攜帶移動設備的機會網絡，提出一種基于社會信任的轉發策略。利用節點的接觸次數、連接時間、接收次數、轉發次數衡量了節點的社會信任，一方面完善了機會網絡節點的信任評價過程，另一方面有效解決了自私節點對數據轉發的影響。仿真結果表明，與經典轉發方式對比，所提出的轉發方式在自私節點較多情況下能保證數據的高效傳遞。

［1］Boldrini C，Conti M，Passarella 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］Liu L，Jing Y.A survey on social－based routing and forwar－ding protocols in opportunistic networks［C］／／IEEE 12th International Conference on Computer and Information Technology，2012：635－639.

［3］Zhang S，Qiu H，Liu Y，et al.Evolutionary reputation model for node selfishness resistance in opportunistic networks ［J］.Concurrency and Computation：Practice and Experience，2012，24 （11）：1261－1269.

［4］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.

［5］Huang T K，Lee C K，Chen L J.Prophet＋：An adaptive prophet－based routing protocol for opportunistic network［C］／／24th IEEE International Conference on Advanced Information Networking and Applications，2010：112－119.

［6］Huang W，Zhang S，Zhou W.Spray and wait routing based on position prediction in opportunistic networks ［C］／／3rd International Conference on Computer Research and Development.IEEE，2011：232－236.

［7］Li N，Das S K.A trust－based framework for data forwarding in opportunistic networks ［J］.Ad Hoc Networks，2013，11（4）：1497－1509.

［8］Al－Hinai 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.

［9］Gupta S，Dhurandher S K，Woungang I，et al.Trust－based Security Protocol against blackhole attacks in opportunistic networks［C］／／IEEE 9th International Conference on Wireless and Mobile Computing， Networking and Communications，2013：724－729.

［10］Conti M，Kumar M.Opportunities in opportunistic computing ［J］.Computer，2010，43 （1）：42－50.

［11］Conti M，Giordano S，May M，et al.From opportunistic networks to opportunistic computing ［J］.Communications Magazine，IEEE，2010，48 （9）：126－139.

［12］Trifunovic S，Legendre F，Anastasiades C.Social trust in opportunistic networks ［C］／／INFOCOM IEEE Conference on Computer Communications Workshops，2010：1－6.

［13］Grabner－Kruter S，Bitter S.Trust in online social networks：A multifaceted perspective［J］.Forum for Social Economics，2013，44 （1）：1－21.

［14］Becker C，Schlinga S，Fischer S.Trustful data forwarding in social opportunistic networks ［C］／／Ubiquitous Intelligence and Computing，IEEE 10th International Conference on and 10th International Conference on Autonomic and Trusted Computing，2013：430－437.

［15］Keranen A.Opportunistic network environment simulator［EB／OL］.［2008－05－29］.http：／／www.netlab.tkk.fi／tutkimus／dtn／theone.