基于社會關系和信任關系的機會網絡路由算法

竇 沖，王小明，林亞光，王冉茵，王新燕

(1.陜西師范大學 現代教學技術教育部重點實驗室，陜西 西安 710119； 2.陜西師范大學 計算機科學學院，陜西 西安 710119)

0 引 言

近年來，隨著移動通信技術的快速發展，便攜式智能設備(如智能手機、PDA等)已經成為人們日常生活的必備品，用戶可以利用移動帶來的相遇機會形成以通信為目的的自組織網絡，進而對數據進行共享。機會網絡[1]是一種具有一般延遲容忍網絡[2]特征的移動自組織網絡[3]，基于“存儲-攜帶-轉發”的消息傳輸機制，節點接收到消息時，先將消息存儲在本地緩存中，然后攜帶該消息移動直到遇到合適的中繼節點進行轉發。然而，節點設備資源包括的能量和緩存通常是有限的，轉發消息將會導致資源的額外開銷，大多節點都會表現出一定的自私性，即拒絕轉發消息或者先答應幫助轉發，然后將接收到的消息進行丟棄[4]，導致網絡性能受到很大的影響。因此，解決自私節點行為的影響變得至關重要。

在機會網絡中，如果用戶間具有一定的社會關系，則他們的聯系會更加頻繁。研究表明，社會網絡中節點的移動具有規律性，表現出節點間重復或者周期性的交互。因此可以利用節點的社會關系，因為節點間社會特征的相似程度在一定程度上可以反映為用戶間聯系的頻繁程度[5]。

機會網絡具有端到端連接易斷、節點經常移動等特點，導致現有的信任模型很難直接運用到網絡中。其存在的問題包括：大多信任機制無法適應信任關系的動態變化，不支持推薦信任關系的自動形成與更新；沒有利用信任關系防止協同的自私行為；沒有考慮到將社會關系和信任關系結合起來。

針對上述問題，提出一種基于社會關系和信任關系的路由算法SRTR，主要內容如下：

(1)從節點間的歷史交互信息和可信鄰居節點的推薦信息兩個角度出發，綜合考慮直接信任度和間接信任度，通過總體信任度的計算建立信任矩陣。根據信任矩陣篩選出當前周期內的可信節點，建立本地信任列表，確保具有較高信任水平的節點參與消息的安全轉發過程。

(2)采用向量形式表示節點的社會屬性特征，并根據交互信息進行更新。通過計算和目的節點的社會相似度，選擇信任列表中社會相似度更大的節點作為中繼節點。確保消息到達目的節點的最佳路徑，提高消息投遞率，降低平均延遲。

(3)對于已選擇的中繼節點，根據社會相似度大小按比例分配消息副本，確保消息副本的高效傳輸。

1 相關工作

相關研究人員提出了多種經典的路由協議。文獻[6]提出了基于洪泛的Epidemic協議。當前節點復制一份消息傳輸給相遇節點，直到傳輸給目的節點，該協議具有較大的投遞率，但是存在大量的副本冗余。PROPHET[7]協議根據相遇概率選擇性地復制數據分組。

相關文獻基于用戶間的交互行為，將用戶的活躍度或者中心性作為轉發消息的重要參考指標。文獻[8]提出了一種基于活躍度的路由協議Bubble Rap，該協議為每個節點設定活躍度等級，節點將消息轉發至活躍度排名高的節點，直至遇到目的節點。文獻[9]基于數據挖掘中PageRank算法的思想，將消息轉發至重要性大的節點，直至遇到目的節點。文獻[10]基于興趣社區的思想選擇中繼節點進行數據包的轉發。文獻[11]提出dLife算法，根據節點間歷史相遇信息來預測下一周期的相遇情況。

以上算法雖然考慮了節點間的交互行為或社會關系，但通常認為節點是相互信任的，忽略了網絡中存在的自私行為。文獻[12]提出基于Credit的激勵機制，節點轉發消息可以獲得虛擬貨幣，付出虛擬貨幣購買其他節點提供的轉發服務。文獻[13]提出一種基于Reputation的激勵機制—IRONMAN，根據節點間的歷史交互信息來檢測網絡中節點的行為，節點通過主動合作來改善自己的信任度。

然而，現有的激勵策略通常只檢測相遇節點能否作為中繼節點，忽視了使用信任機制檢測節點間存在的合作自私行為。同時，也沒有將信任關系和社會關系結合起來。

2 用戶社會和信任關系的評估模型

2.1 網絡模型

2.2 信任評估模型

根據節點間的歷史交互信息以及可信鄰居節點的推薦信息建立信任評估模型，能夠及時準確地對節點的可信狀態進行分析和判斷。可以拒絕自私節點參與到消息轉發的過程中，同時避免與網絡中低信任度的節點建立合作關系，保證節點之間安全、可靠的通信。

通過周期性觀察節點間的交互行為，對節點間的直接信任關系進行估計和判斷。同時根據可信鄰居節點的推薦信息對節點間的間接信任關系進行估計和判斷，因此判斷信任關系時綜合考慮直接信任關系和間接信任關系。

定義1(直接信任度)：根據節點間歷史交互信息所估計的直接信任水平。

用DTi,j(t+Δt)表示t+Δt時刻節點i對節點j的直接信任評估值，其計算公式如下：

(1)

(2)

定義2(信任相似度)：節點i和節點j對共同相遇節點(如共同相遇節點集合NS中節點)信任度的相似程度。

假設節點i和節點j為鄰居節點，共同相遇節點集合為NS，具體的計算公式如下：

(3)

其中，NS=[N1,N2,…,Nn]表示節點i和節點j的共同相遇節點集合，采用信任評價向量的方式表示節點i對每一個相遇節點的信任評價情況，表示形式為：TiS=[TiN1,TiN2,…,TiNp,…,TiNn]，其中TiNp(Np∈NS,1≤p≤n)表示當前節點i對節點Np的直接信任度。利用定義2的計算公式，可以得出節點i和每一個鄰居節點的相似性，從而得到m個最相似的鄰居節點，進而得出定義3。

定義3(間接信任度)：網絡中和當前節點具有較高信任相似度的節點所推薦的直接信任度。綜合考慮具有較高信任相似度節點的直接信任度，能夠可靠、準確地反映出推薦的信任水平。

間接信任度ITi,j的計算公式為：

(4)

其中，M={k1,k2,…,km}表示和節點i最相似的m個鄰居節點集；DTk,j表示節點k對節點j的直接信任度。顯然，0

定義4(信任度)：包含直接信任度和間接信任度的綜合信任水平。

根據定義1、3的計算公式得出節點i對節點j的信任度Ti,j：

Ti,j=αDTi,j+(1-α)ITi,j

(5)

其中，0<α<1,0≤Ti,j≤1。根據實際的網絡情況對α進行取值。

根據上述計算，則整個網絡的信任關系可抽象成如下n×n的二維矩陣：

對于網絡中任一節點i，其儲存矩陣T中對應的第i個行向量：存儲Ti=(Ti1,Ti2,…,Tin)，該行向量由節點i維護，同時進行周期性更新，并反饋到網絡。每一個周期中，節點i需要建立本地信任列表Tlist(i)，用于存放可以信任的其他節點，同時根據交互信息對本地信任列表進行周期性更新。

2.3 社會關系評估模型

機會網絡中，如果用戶間具有一定的社會關系，則他們之間的聯系會更加頻繁。社會關系可以反映為用戶間具有某些共同的社會特征。因此，共同的社會特征的多少在一定程度上可以反映用戶間聯系的頻繁程度。

由圖1可看出，隨著共同社會特征個數的增加，相遇頻率也隨之增加。因此可以將節點的社會屬性特征作為中繼節點選擇的重要依據。

圖1 相遇頻率和共同特征數的關系

下面給出量化的社會屬性特征定義以及節點間聯系程度的計算公式。

定義5(社會特征向量)：用于描述節點的社會屬性特征，表示如下：

FNi={f1,f2,…,fm}

(6)

其中，FNi表示節點Ni的社會特征向量；fi表示第i種社會屬性，網絡中共有m種社會屬性。

定義6(靜態社會特征向量)：靜態社會特征向量根據用戶的自身信息得到，用于表示用戶節點的初始社會特征向量，xi表示屬性fi對應的權重大小。

隨著網絡中節點之間的交互，對節點的靜態社會特征向量進行更新，公式如下：

(7)

其中，0≤xi≤1，1≤i≤m；Mi表示節點Ni和具有屬性fi的節點的相遇次數；Mtotal表示節點Ni和所有節點的相遇總次數。

定義7(社會相似度)：用于衡量用戶間社會屬性特征的相似程度，計算公式如下：

(8)

其中，sim(i,j)表示用戶節點i和j的社會相似度；Fi表示用戶i的社會特征向量。

3 SRTR算法步驟

SRTR算法采用有限消息副本轉發策略，依據節點間的交互信息和可信鄰居節點的推薦信息建立信任矩陣，根據信任矩陣建立本地信任列表，用于存放可信任的鄰居節點，然后根據目的節點對中繼節點的社會相似度實現轉發決策和分割消息副本數。當前節點Ni如果存在需要轉發的消息集M，算法具體步驟如下：

(1)當前周期中，根據信任矩陣T，節點Ni存儲信任矩陣T中的行向量Ti=(Ti1,Ti2,…,Tin)。根據系統環境設定信任度閾值Tth，由行向量分別獲取節點Ni對其他節點的信任度，將滿足信任度閾值條件的節點添加至節點的本地信任列表Tlist(i)，同樣，刪除本地信任列表中不符合閾值條件的節點。

(2)對于節點Ni攜帶的消息m∈M，獲取消息m的目的節點ND。當節點Ni遇到節點Nj時，如果Nj=ND，則節點Ni將消息直接發送至目的節點。如果節點Nj∈Tlist(i)，則進入步驟3；否則，節點Ni繼續攜帶消息直到遇到目的節點或者本地信任列表Tlist(i)中的節點。

(3)根據節點的社會特征向量分別計算當前節點Ni、相遇節點Nj和目的節點的社會相似度sim(Ni,ND)以及sim(Nj,ND)，如果sim(Nj,ND)>sim(Ni,ND)，則節點Ni需要分割消息m的副本數Ncj，將副本數為Ncj的消息m轉發給Nj，更新節點Ni的消息副本數Nci←Nci-Ncj，消息副本數分割計算如下式：

(9)

(4)否則當sim(Nj,ND)≤sim(Ni,ND)，節點Ni繼續攜帶消息直到遇到目的節點或者本地信任列表Tlist(i)中的節點。

4 實 驗

4.1 仿真環境設置

文中利用基于Java的機會網絡仿真平臺ONE[14](opportunistic network environment)進行實驗仿真，使用Infocom 2006 trace[15]數據集，源節點和目的節點從85個節點中隨機選擇。選取數據庫中的6個特征[5]，分別是國籍、語言、城市、公司、職業、教育背景等。具體參數設置如表1所示。

表1 仿真環境參數設置

4.2 性能指標

為了驗證SRTR算法的性能，選取的指標如下：

(1)消息投遞率：網絡中成功交付到目的節點的消息數與源節點產生的消息總數的比值。

(2)平均延遲：消息從源節點產生到交付到目的節點所花費時間的平均值。

(3)路由開銷：網絡中消息副本總數和成功傳輸到目的節點的消息數的比值。

(4)丟包數目：網絡中自私節點所丟棄的消息總數。

4.3 仿真結果分析

實驗過程中通過調整自私節點的比率得到不同算法的四個性能指標，用于分析SRTR算法與Epidemic、dLife和IRONMAN算法的性能。

4.3.1 消息投遞率

不同自私節點比率下四種算法的消息投遞率如圖2所示。

圖2 消息投遞率vs自私節點比率

隨著自私節點比率的增加，4種路由算法的投遞率都呈下降的趨勢。由于沒有自私節點檢測機制，和SRTR、IRONMAN算法相比，Epidemic和dLife算法的投遞率下降得比較迅速。和IRONMAN算法相比，SRTR算法仍然具有較高的消息投遞率。IRONMAN算法沒有考慮到節點間的信任評估和社會關系，而SRTR算法能夠確保具有較高信任水平的節點參與到消息轉發的過程中，并且根據社會關系選擇中繼節點。因此，SRTR算法的表現總體上優于IRONMAN算法。

4.3.2 平均延遲

不同自私節點比率下四種算法的平均延遲如圖3所示。

圖3 平均延遲vs自私節點比率

隨著自私節點比率的增大，4種路由算法的平均轉發延時均呈現出上升的趨勢。主要是隨著自私節點比率的增大，更多的消息長時間等待傳輸或者被重新傳輸。由于沒有自私節點檢測機制，不能避免自私節點轉發消息，因此Epidemic路由的平均轉發延時增長最快。雖然dLife算法不能檢測到自私節點，但是該算法基于社會關系選擇中繼節點，一定程度上能夠避免選擇自私節點轉發消息，相對而言具有較為穩定的時延。和Epidemic、dLife算法相比，SRTR、IRONMAN算法具有較低的時延，因為這兩種算法具有相應的自私節點檢測機制。根據之前所述，和IRONMAN算法相比，SRTR算法能夠更為準確地檢測到自私節點，并且根據社會相似度動態分配消息副本，當自私節點比例超過50%時，SRTR算法的表現優于IRONMAN算法。

4.3.3 路由開銷

在不同自私節點比率下四種算法的路由開銷如圖4所示。

圖4 路由開銷vs自私節點比率

隨著網絡中更多的正常節點變為自私節點，Epidemic算法的傳輸開銷呈現增長的趨勢，且該算法的路由開銷最大。當自私節點比率低于40%時，隨著自私節點的增多導致更多的消息副本被丟棄，因此dLife算法的路由開銷呈現增長的趨勢，該算法根據社會關系選擇中繼節點，當自私節點比率超過40%時，被選擇的中繼節點逐漸減少，使得消息被丟棄的速率逐漸下降，傳輸開銷呈現下降的趨勢，因此dLife算法的表現優于Epidemic路由。SRTR算法和IRONMAN算法的路由開銷呈現下降的趨勢，因為這兩種算法能夠檢測到自私節點，IRONMAN算法的路由開銷更小，因為該算法借鑒于SAW算法的思想，采用有限消息副本轉發的策略[15]。

4.3.4 丟包數目

在不同自私節點比率下四種算法的丟包數目如圖5所示。

圖5 丟包數目vs自私節點比率

可以看出，相比dLife和Epidemic算法，IRONMAN算法和SRTR算法具有較少的丟包數目，因為dLife算法和Epidemic算法沒有自私節點檢測機制。和IRONMAN算法相比，SRTR算法能夠更為準確地檢測到自私節點，相比而言，SRTR算法具有更少的丟包數目。相比Epidemic算法，dLife算法根據社會關系選擇下一跳節點，因此該算法的表現優于Epidemic算法。

5 結束語

文中提出一種機會網絡中基于社會關系和信任關系的路由算法SRTR，該算法綜合考慮直接信任度和間接信任度，根據總體信任度建立節點間的信任矩陣。特別是在獲取推薦信息時，通過建立信任相似關系對鄰居節點進行信任評估，并以信任相似度作為約束條件來避免自私節點出現謊報推薦信息的可能。建立節點本地信任列表確保具有較高信任水平的節點參與到消息的安全轉發過程中。并且結合社會關系，選擇本地信任列表中和目的節點社會相似度更大的節點作為轉發消息副本的中繼節點，并根據社會相似度動態分配消息副本。在確保中繼節點可靠的前提下，使得消息沿著社會相似度遞增的方向傳遞，可以避免節點間自私行為的發生，確保消息到達目的節點的最佳路徑，提高整個網絡的消息投遞率，降低網絡中消息轉發時延，使得消息副本得以高效、可靠的傳輸。