機會網(wǎng)絡(luò)中基于社會信任的數(shù)據(jù)轉(zhuǎn)發(fā)算法

袁江濤，張振宇，楊文忠

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

2 基于社會信任的轉(zhuǎn)發(fā)算法

2.1 社會信任的度量

在社會網(wǎng)絡(luò)中，社會信任是指一定社會成員之間相互認同、信任并進行真誠交往的現(xiàn)象［13］。社會信任可由社會關(guān)系決定，而社會關(guān)系又是由社會成員的社會屬性構(gòu)成，所以根據(jù)不同的社會屬性可以構(gòu)建節(jié)點的社會信任，并反映節(jié)點間的信任強度［14］。基于這種聯(lián)系，可引入社會信任的思想解決機會網(wǎng)絡(luò)信任轉(zhuǎn)發(fā)問題。

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

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

2.1.1 熟悉度

機會網(wǎng)絡(luò)中每個節(jié)點的地位都是相互平等的，隨著節(jié)點的移動，節(jié)點會接觸若干不同的節(jié)點，并且與不同節(jié)點的接觸頻率各不相同。在轉(zhuǎn)發(fā)數(shù)據(jù)的過程中，可以選取較熟悉的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，節(jié)點熟悉度的定義如下

2.1.2 親密度

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

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

2.1.3 服務(wù)度

由于正常節(jié)點能幫助其它節(jié)點及時轉(zhuǎn)發(fā)數(shù)據(jù)，自私節(jié)點只能接收數(shù)據(jù)不轉(zhuǎn)發(fā)數(shù)據(jù)，網(wǎng)絡(luò)中節(jié)點可通過交換各自記錄的數(shù)據(jù)接收和轉(zhuǎn)發(fā)次數(shù)衡量對方的服務(wù)度。所以通過服務(wù)度不僅可以反映節(jié)點的轉(zhuǎn)發(fā)可靠性，而且能有效地區(qū)分出自私節(jié)點和正常節(jié)點。服務(wù)度的定義如下

式中：servi，j——節(jié)點j對節(jié)點i 的服務(wù)程度，且servi，j∈［0，1］，trani，j——節(jié)點j幫助節(jié)點i完成的數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)，recei，j——節(jié)點j接收節(jié)點i的數(shù)據(jù)次數(shù)，此處節(jié)點j接收次數(shù)recei，j必然大于或等于節(jié)點轉(zhuǎn)發(fā)次數(shù)trani，j。

2.1.4 信任計算

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

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

考慮到節(jié)點的社會信任是從3個不同的社會屬性角度進行描述，共同構(gòu)成節(jié)點社會信任的基礎(chǔ)，權(quán)值的具體分配如下

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

在節(jié)點i計算出節(jié)點j 的社會信任Ti，j后，規(guī)定θ為信任轉(zhuǎn)發(fā)閾值，當(dāng)Ti，j≥θ時，認為該節(jié)點為信任節(jié)點并向該節(jié)點發(fā)送數(shù)據(jù)；當(dāng)Ti，j≤θ時，認為該節(jié)點為自私節(jié)點。拒絕向該節(jié)點發(fā)送數(shù)據(jù)。

2.2 基于社會信任的轉(zhuǎn)發(fā)過程

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

算法1：ST－Epidemic數(shù)據(jù)轉(zhuǎn)發(fā)算法

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

輸出：信任節(jié)點集合TR［j］節(jié)點

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

2.3 算法復(fù)雜度分析

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

3 實驗仿真

本文利用仿真工具ONE 1.4.1［15］設(shè)計的場景對提出的轉(zhuǎn)發(fā)算法進行評估。節(jié)點移動方式為ShortestPathMap－BasedMovement（SPMBM），具體仿真環(huán)境參數(shù)設(shè)置見表1。

表1 實驗仿真環(huán)境

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

3.1 傳輸成功率

圖1和圖2分別展示了在30%和70%的自私節(jié)點比例情況下4種轉(zhuǎn)發(fā)方式的傳輸成功率。

圖1 傳輸成功率

圖2 傳輸成功率

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

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

圖3 傳輸成功率

3.2 平均延遲時間

圖4和圖5展示了在30%和70%的自私節(jié)點比例情況下4種轉(zhuǎn)發(fā)方式的平均延遲時間。

圖4 平均延遲時間

圖5 平均延遲時間

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

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

圖6 平均延遲時間

4 結(jié)束語

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

［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，F(xiàn)ischer 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.