基于社會屬性的PSN消息路由算法

曹玖新，陳高君，楊婧，朱子青，劉波

（東南大學 計算機科學與工程學院，江蘇 南京 211189）

1 引言

隨著手機等手持設備的大量普及，利用手持設備實現信息傳輸并提供網絡服務功能的口袋交換網絡（PSN， pocket switched network）受到了廣泛的關注，它是一種由人隨身攜帶的手持設備組成的特殊的延遲容忍網絡（DTN， delay tolerance network）網絡，由2005年劍橋大學和Intel研究院提出[1]。它利用人類的移動性和局域連通性，采用“存儲—攜帶—轉發”的傳輸模式，利用節點移動而進入彼此的通信范圍所產生的數據交換機會進行通信，在移動用戶的設備之間傳遞數據。

設備隨著設備攜帶者移動，而設備攜帶者的移動往往具有目的性和規律性，因而PSN網絡具有社會網絡特征。研究PSN網絡中節點之間構成的社會網絡有助于發現節點行為規律，預測這些無線通信設備構成的通信網絡的變化趨勢，有利于更好地發現信息攜帶節點、實現PSN網絡中的信息路由。

路由問題作為 PSN網絡中一個獨立開放的研究領域，其當前研究的熱點是如何更好地選擇中繼節點以獲得更高的傳遞成功率和更低的網絡負載。目前已有越來越多的研究[2～6]開始關注通過挖掘PSN網絡中節點的社會信息來優化路由算法。

通過社交網絡分析可知，大部分人的活動范圍都是局限于一定的區域或社區。社區（community）是一些節點所組成的子集，而它的內部節點之間的聯系比社區之間的聯系要緊密。為了充分利用 PSN網絡中節點的社會運動規律，本文將社會網絡中節點重要性與移動社會網絡的特征相結合，考慮節點社區關系和節點活躍度對路由算法的影響，提出了基于社區關系的BridgingCom路由算法。算法首先通過每個節點識別出自己所在社區，獲得局部社區信息，作為節點關系的判斷依據；然后使用橋接中心度（bridging centrality）作為選擇中繼節點的依據，使消息傳遞更有方向性和目的性，盡快從本地傳遞到目標節點。

2 相關工作

2.1 PSN中的“存儲—攜帶—轉發”模型

PSN網絡作為一種特殊的DTN具有網絡位置稀疏、高延遲、低數據傳輸率、節點間間歇性連接、消息排隊時間較長和節點資源有限等特征。因此，傳統移動自組織網絡中的路由技術不再適用。為了能夠充分利用節點移動帶來的連接機會，PSN在數據傳輸時采用的是“存儲—攜帶—轉發”的模式來克服鏈接的頻繁斷開。

圖1所示為PSN路由過程，即一個消息的交付過程。源節點S欲發送信息至目標節點D，然而在t1時刻節點S與D并未發生接觸且節點S沒有路徑可以到達D；于是節點S將信息數據轉發至鄰居節點1，節點1在t2將數據轉發給節點3，最后在t3時刻節點3與目標節點D相遇并將信息數據發送給D。從上面的示例可以看出，“存儲—攜帶—存儲”模型是“存儲—轉發”模型的拓展，它充分利用了節點的移動能力和存儲能力，為PSN中的信息發布提供了一個非常有效的方法。通過該轉發策略，使源節點不需與目標節點發生接觸，轉而通過中間節點的運載和轉發，成功的將數據發送給目標節點。

圖1 “存儲—攜帶—轉發”實例

2.2 現有PSN網絡中的路由算法

由于“存儲—攜帶—轉發”模式的存在，中繼節點的選擇以及副本數的確定顯得尤為重要。與傳統Internet以最小跳數、最短路徑為路由目標不同，PSN中不同的應用場景可能具有不同特征與不同的目標，主要有最小化傳輸延遲、最大化消息傳遞成功率以及最小化緩沖、網絡帶寬和能量消耗等目標。目前已有的PSN的路由算法從不同的角度有不同的分類方法[7]。按照消息復制策略，已有的PSN路由算法可以分為3大類：單副本路由、傳染路由以及基于知識的路由。

在單副本路由中，任何時間網絡中只有一個節點攜帶同一消息。單副本路由的開銷很小，但通常交付延遲較高，可靠性相對較低。

傳染路由(epidemic routing)[8]中每個節點都不進行路由決策，而將消息泛洪給自己所有的鄰居節點。如果所有的節點都能夠充分移動，傳染路由能夠幾乎將所有的數據都正確分發，由于傳染路由窮舉了所有可能的傳輸路徑，消耗資源嚴重，在現實中，能量、帶寬、緩沖等資源缺乏而造成資源競爭，傳染路由性能會嚴重降級。

不依賴于網絡知識的路由方式中消息傳輸顯得較盲目，為了充分利用資源，基于知識啟發的路由決策可使消息傳遞的方向明確。根據依據的網絡知識不同可以細分為基于上下文的路由、基于歷史信息的路由和基于社交信息的路由。如基于傳輸預測的路由算法[9]利用歷史連接數據計算傳遞概率，預測節點相遇概率，為每個節點計算到達目標節點的傳輸預測值，將消息副本向傳輸預測值大的節點傳遞。與傳統的不考慮歷史數據的路由算法相比它們具有更好的性能。

近年來，基于社交信息的 DTN路由研究受到了廣泛的關注，PSN作為典型的具有社交屬性的DTN網絡表現出小世界[10]、有差異的節點中心度[11，12]、有周期規律性的活動、節點分布廣等特征。利用PSN網絡中節點的內在社會關系，可有效地解決移動社會網絡中信息傳輸效率和準確性較低的問題。SimBet路由算法[2]同時考慮以當前節點為中心的Ego網絡的中心度（Ego-centric centrality）和社會相似性決定消息轉發。消息向中心度高的節點轉發，提高成功選擇有效中繼節點的可能性。文獻[13]基于地理位置進行網絡劃分，獲得節點社區關系，但這種劃分方法根據位置進行劃分而不是根據節點本身劃分。Bubble Rap算法[3]選擇介數中心度（betweenness centrality）高的節點和目標節點所在社區節點作為中繼。消息到達目標社區前，相遇節點之間比較全局中心度，到達目標社區后，相遇節點比較局部中心度。因此，消息在傳輸過程中會涌向中心度高的節點，這些節點的資源被迅速消耗掉。Hu等人在Bubble Rap算法的基礎上加入SRL（social relation level），提出了 BiBUBBLE 算法[14]，在中繼節點選擇時除了考慮節點的介數中心度外，也考慮節點的SRL值，增加中繼節點數目，提高傳輸效率。CAF算法[15]在原有路由算法的基礎上加入多宿主節點（multi-homed node）概念，在社區之間通過多宿主節點傳遞消息，提高消息傳遞準確性。文獻[16]發現具有相似偏好的設備攜帶者更有可能相遇，因此文章提出使用k維向量表示其偏好并將消息轉發給具有相似偏好的節點。文獻[17]同時考慮中心度及用戶偏好，基于用戶偏好信息計算中心度。2012年 Matthew Orlinski等人提出了基于Epidemic算法的 QualityEpidemic算法[18]，使用已有的社區識別算法將節點劃分為不同社區，節點只把消息傳遞給與目標節點相同社區的節點。該算法適用性比較強，但是否能夠將消息傳遞到目標節點依賴于節點的移動性。文獻[19]基于分簇結構將移動規律相似的節點聚合為最近社交圈的節點簇，并提出基于分簇結構的路由協議，路由分為簇外噴射、簇間轉發和簇內傳染3個階段。

由于PSN網絡中節點移動模式、應用場景、路由優化目標都有所不同，因此每個PSN中路由算法的側重點都不同。在沒有基礎設施的情況下，充分利用便攜設備節點的數據存儲、數據處理以及網絡通信功能，研究人的移動和相遇規律，PSN可以更高效地完成數據在不同節點間傳輸，實現數據的交換和信息共享。在信息服務、災難救援、軍事領域等很多方面都具有良好的應用前景。

3 相關概念

本章首先給出PSN形式化網絡模型，然后基于此模型介紹局部社區識別算法中使用到的基本概念，最后給出節點中心度的定義和計算方法。

3.1 網絡模型

為了便于網絡中節點關系分析，方便地表達社會網絡的統計性質，更準確地進行社區關系分析，這里將PSN網絡建模為具有時間屬性的無向圖，其形式化描述如下。

給定Gt(V，E)，其中，V是網絡中的頂點集合，|V|=n；E為網絡中2個正在通信的節點之間連接邊的集合，|E|=m。節點u、v之間的邊權重用T(u，v)表示，本文使用節點間累計通信時間作為T(u，v)的度量。

3.2 熟知集合和局部社區

為了便于下文描述局部社區識別算法，首先定義社區識別算法中的基本概念。

定義1熟知集合（familiar set）。對于一個給定的頂點vi，它的完整的熟知集合形式化表示為Fi

其中，T(vj，vi)表示vj與vi之間的累計連接時間，Tth是時間閾值，Ni表示節點vi的鄰居節點集合。節點的熟知集合保存的是當前節點的鄰居集合中節點的累積連接時間超過閾值Tth的所有節點。

定義2局部社區（local community）。對于一個給定的頂點vi，它的局部社區表示為Ci，它包括熟知集合Fi中的所有節點和通過局部社區識別算法獲取的節點。

一般社區識別算法需要通過分析整個網絡結構，將網絡劃分為若干個相互分離的社區[20]，本文中使用的社區識別算法是通過節點局部知識獲得節點所在的社區信息，因此稱為局部社區。由于網絡動態變化和有限的網絡信息知識，可能本屬于同一社區的節點會分配到不同的局部社區。

定義3Ego網絡(Ego network)[21]。對于給定的節點v，它的 Ego網絡是指節點v本身、v的直接鄰居以及它們之間的連接關系組成的子網。

3.3 節點中心度定義

為了使消息能夠盡快進入目標節點所在社區，識別出可以在2個社區之間起到溝通橋梁作用的節點成為關鍵。因此，本文使用橋接中心度作為節點中心度[11]的排名依據。

橋接中心度(bridging centrality)[22]能夠很好地識別出位于不同社區之間的起到橋梁溝通作用的節點。橋接中心度BC定義如式(1)所示。

其中，Csoc(v)表示節點v的介數中心度[23]，如式(2)所示。

β(v) 為橋接系數（bridging coefficient），如式(3)所示。

其中，gjk表示j與k之間的最短路徑數，gjk(pi)表示j與k之間的最短路徑中通過i的數目，d(i)表示節點i的度（degree）值。

Csoc(v)可以衡量網絡中通過該節點的最短路徑的數目，表示節點在網絡中的社會重要性；β(v)表示節點在信息流中的重要性，反映了節點位于緊密連接的區域之間的程度，衡量節點在拓撲結構中的重要性。

在PSN中，網絡動態變化，節點之間沒有穩定的連接，網絡拓撲Gt(V，E)隨時發生著改變，2個相遇節點很難獲得整個網絡的拓撲結構。因此，本文利用當前節點的局部社區信息，在當前節點的Ego網絡中計算節點的橋接中心度，式(4)為本文使用的橋接中心度計算公式。

考慮到PSN中很可能在某一時刻不是一個完全連通圖，網絡連接圖中有度為0的局部獨立節點存在，也就意味著不會有其他節點的消息通過此節點。為了保證在計算β(v)時不發生除以 0溢出問題，式(4)設定如果節點V的度d(v)為0，將(v)賦值為0。

4 基于社會屬性的BridingCom路由算法

由社交網絡分析可知，大部分人的活動范圍都是局限于一定的區域或社區。如果目標節點與源節點并不在同一個活躍社區，消息在超時之前被傳遞到目標節點可能需要經過其他中間社區，成功傳遞的概率將會受限。如果消息的傳播范圍被限制在“局部”，不僅造成消息無法成功投遞，還占用了中繼節點寶貴的緩存空間，影響其他有可能成功送達目的地的消息接收。有效利用節點的節點歷史運動軌跡和社會活動關系可以使消息傳遞更有方向性和目的性，提高路由效率，降低傳輸延遲。

但是，PSN網絡結構實時發生改變，并且節點沒有辦法通過統一平臺（如 Internet等）獲得統一服務器提供的網絡全局數據，網絡中每一個節點無法獲得整個網絡的實時結構。目前已有的根據整個網絡拓撲對網絡社團結構進行的研究[20]都不適合PSN這種動態變化的網絡，因此本文通過局部社區識別算法獲得節點的社區信息。

在局部社區識別的基礎上，本文基于節點歷史運動軌跡和社會學研究理論，提出了一種基于社會信息的BridgingCom路由算法。該算法的基本思想是通過節點之間的社區關系為不同節點選擇不同的路由方向，防止社區內部消息在社區間的傳遞以及減少社區間的消息在社區內部的傳遞，從而使消息傳遞更有方向性、降低網絡負載。當消息未達到目標節點所在社區，選擇全局中心度高的節點，增加接觸到目標節點的機會；當消息已經傳遞到目標節點所在社區時，選擇本地中心度高的節點，防止消息擴散。

4.1 局部社區識別算法

為了根據社區信息選擇合適的中繼節點，節點能夠正確、高效地識別出自己所在的社區信息是需要解決的首要問題。為了獲得節點的社區信息，本文從節點局部出發，采用局部社區識別算法，根據節點歷史通信記錄，尋找節點所在的社區信息并實時更新。

2007年Pan Hui等人提出的Simple局部社區識別算法[24]通過進入彼此通信范圍的節點交換獲得彼此的局部信息，更新局部知識，計算節點所在社區。在Simple局部社區識別算法中，節點不斷累加與鄰居節點的連接時間，隨著時間推移，每個節點存儲的歷史信息會逐步增加。

長時間未聯系的節點信息不僅浪費存儲空間，而且還可能會對未來行為預測產生錯誤的指導作用。因此，在Simple局部社區識別算法的基礎上加入連接老化機制，算法基本思想如算法1所示。

算法1帶有老化機制的局部社區識別算法

輸入：本節點s的局部社區Cloc(s)=φ；

熟知集合F(s)；

連接節點的u的局部社區Cloc(u)；

熟知集合F(u)。

輸出：節點s所在的局部社區Cloc(s)；

更新后的熟知集合F(s)。

①從源節點s的開始，初始化

②當s與節點u相遇時，交換彼此的本地信息；

③節點s根據連接老化閾值T更新局部社區，刪除超過時間T未再遇到的節點；

④若節點u不在s的熟知集合F(s)中，s更新與u之間的連接時間記錄，若連接時間超過設定閾值，將u并入F(s)和Cloc(s)；

⑤節點u不在Cloc(s)時，若，將u并入到Cloc(s)，其中λ為并入閾值；

⑥若u已經通過前幾步被加入到Cloc(s)，則考慮是否合并2個局部社區：如果2個局部社區的重疊區域中的節點數則合并2個局部社區，其中γ為合并閾值。

網絡中每個節點需要保存的信息包括需傳遞的消息列表，以及本節點的熟知集合F和目前的局部社區標識C及社區內成員，以便當節點相遇時交換彼此攜帶的信息，更新節點的局部社區知識。

算法1中的連接老化機制主要通過時間閾值T控制熟知集合和局部社區中節點增刪發揮作用。當節點s遇到其他節點后，首先更新節點的局部社區信息，然后根據相遇節點是否在s的熟知集合和局部社區集合內做不同的操作：如果節點已經在s的局部社區內，則根據2個節點的熟知集合和局部社區集合的重合度更新節點s的局部社區集合。這樣不僅可以節約緩存空間，而且還可以減弱過時的歷史信息對算法的影響，使算法更加準確地反映網絡節點實時的傳輸能力。

4.2 BridgingCom路由算法

在PSN網絡中，消息是在相遇節點之間不斷復制傳遞的，節點在網絡拓撲中的重要性影響了消息傳播的效率，例如，處于網絡核心地帶的節點更容易將消息傳遞出去，而在網絡邊緣的節點則不具備這種能力。因此，在4.1節中局部社區識別算法獲得的局部社區信息的基礎上，BridingCom算法根據要傳遞消息的目標節點與相遇節點的社區關系，選擇不同的路由策略。

1)跨社區傳遞：如果消息攜帶節點s及相遇節點都不知道目標節點d的方位（都不在目標節點所在的社區），將消息發送到橋接中心度高的節點，增加接觸到目標節點所在社區的機會。

2)社區內傳遞：當目標節點與相遇節點處于相同社區，表明消息已經接近目標節點，因此將消息推送到社區內重要性高的節點，這里使用節點u的Ego網絡中的邊數作為局部中心度，使用LocalRank(u)表示。

圖2描述了BridingCom算法的基本思想，展示了具有3個社區的網絡中2個消息的傳遞路徑。設網絡中的3個社區分別為社區A、社區B與社區C。當社區A中節點S有消息要傳遞到社區A中的節點D1時，社區內節點S與節點D1雖然無法直接通信，此時選取中心度高的節點，可以高效地將消息傳遞給D1。當社區A中節點S有消息要傳遞到社區C中的節點D2時，假設最佳路徑需要通過社區B中節點才能到達社區C中的節點D2。此時根據BridgingCom算法選取位于2個社區之間的“橋節點”，盡快將消息推送出S所在的社區A，傳遞到邊界節點N1，然后通過連接社區A與社區B的節點B1傳遞到社區B，進而獲得到達社區C中節點D2的路徑。

圖2 “消息傳遞”實例

BridgingCom路由算法如算法2所示。其中，節點的社區信息通過局部社區識別算法獲得。

算法2BridgingCom路由算法

輸入：本地節點s；相遇節點u；要傳遞的消息m；m的目標節點t

輸出：消息是否復制傳遞成功；

① 當節點s遇到節點u，更新節點s的局部社區集合C(s)；

② 當目標節點t在節點s所在社區t∈C(s)，如果u∈C(s)，則轉到③，否則算法結束；

③ 計算節點s的局部中心度LocalRank（s）與節點u的局部中心度LocalRank（u），如果LocalRank（s） ≤LocalRank（u），則將消息復制傳遞給u，否則算法結束；

④ 當目標節點t不在節點s所在社區即t?C(s)，如果相遇節點u與目標節點t在同一社區t∈C(u)時，則將消息復制傳遞給u，否則轉到⑤；

⑤ 如果沒有傳遞消息，則計算節點s的橋接中心度(s)和節點u的橋接中心度(u)，如果(u)≥(s)，則同樣將消息復制傳遞給u。

BridgingCom路由算法的有效運作依賴于局部社區識別算法和節點重要性度量策略。因此當2個節點相遇時，首先交換彼此存儲的局部網絡信息，包括節點熟知集合、局部社區集合，節點更新自己的局部社區知識和節點中心度。

5 實驗與分析

為了評價 BridgingCom算法的性能，在 The ONE[25]仿真平臺上比較了本文提出的BridgingCom算法與Direct算法、Epidemic算法、Bubble算法[3]、BiBUBBLE算法[14]以及 QualityEpidemic算法[18]在不同的TTL（time to live）情況下的傳遞性能。

Direct算法使源節點只與目標發生消息傳遞，因此消息傳遞延遲非常大，不進行消息復制，網絡負載最低。Epidemic算法與Direct算法相反，將消息復制傳遞給所有相遇節點，能夠獲得較短傳輸延遲，但毫無選擇地盲目復制使傳輸能耗巨大，嚴重影響網絡壽命。Bubble算法、BiBUBBLE算法以及QualityEpidemic算法為近幾年提出的基于節點社會關系進行路由決策的代表算法。

5.1 實驗目標

PSN中消息傳輸失敗的原因可能有：由于 PSN間歇連通，消息傳輸過程中鏈路中斷；消息在應用能夠容忍的時間內不能到達目標節點，被節點丟棄；節點為了有效利用有限的緩存或節約能量而選擇性的丟棄部分消息。PSN路由的目標是以較少的資源消耗獲得較高的消息交付比率（可靠性）和較低的交付延遲。主要從以下幾個方面來評估相關算法的性能。

1) 消息傳遞成功率（delivery ratio）：路由算法的終極目標就是獲得更高的傳遞成功率。消息交付比率就是在整個通信過程中目標節點成功接收到數據分組數量與在源節點所傳遞的所有數據分組比值，反映了傳遞成功率。

2) 平均延時（average delay）：消息延時是節點在發送數據時數據塊從源節點到達目標節點所需的時間。平均消息延時體現了網絡的實時性，同時也間接反應了整個網絡消息流通是否正常。另外，盡管PSN中應用能夠容忍一定的延遲，但傳輸延遲越短，將使得應用的時效性越強，網絡資源將越早得到釋放，網絡資源的利用率也將得以提高。

3) 網絡傳輸冗余比（overhead ratio）：網絡傳輸冗余比是指在PSN中副本消息與成功傳遞的消息之差除于成功遞交的消息數目。此參數反應了網絡的冗余消息量，如果比值高，則說明網絡性能差，網絡中充斥著很多沒法交付的消息；若比值低，說明網絡有較好的傳輸能力，能將較多的消息成功交付。

5.2 實驗數據

為了驗證算法在真實場景中的性能，本文使用以下2個數據集，并對數據進行了處理，刪除連接時間為0的無效連接信息，防止瞬時連接影響實驗效果，數據集基本信息如表1所示。

數據1MIT Reality Mining Project[26]數據集（簡稱Reality數據）

Reality Mining項目包括75個來自MIT Media實驗室學生，25個來自MIT Media實驗室附近的MIT Sloan Business School的學生。該數據集中有效節點數為97。由于Reality數據集時間跨度比較長，因此這里只選用實驗數據中4段比較穩定而且沒有額外的假期干擾的連接數據，每段數據包含一周的連接信息。

數據2Haggle Project[27]數據集（簡稱Infocm2006數據）

該數據集是98個Infocom2006的與會人員攜帶iMotes設備產生的記錄數據。由于此組數據集合時間跨度比較短，因此選用整個數據集合進行實驗。

表1 Reality和Infocom2006數據集基本信息

這2組數據的一些基本特征如表1所示。Reality數據集和 Infocom2006數據集中的連接間隔（granularity）分別為 300 s和 120 s，連接事件（number of internal contacts）分別為54 667次和191 336次，平均每天每2個節點之間發生的連接事件數目分別為0.024次和6.7次。可以看出，Reality數據集的持續周期長，用戶活動范圍比較廣，連接事件間隔比較長，連接發生頻率比較低；Infocom2006數據集的持續周期短，用戶活動范圍小，記錄周期短，連接發生頻率高。

圖3為Reality數據集和Infocom 2006數據集在實驗周期中每個節點與其他節點發生連接的總次數、每個節點曾遇到過的節點總數。從圖3可以看出來節點活動具有社會規律：節點活動范圍具有局限性，發生的大部分連接都是與某一固定節點集合中節點之間發生的；節點活躍程度不同，某些節點表現出明顯高于其他節點的活躍度。選擇合適的中繼節點，將消息盡快推送出局部社區，將有助于增加接觸到目標節點的機會。

圖3 節點連接次數與連接節點數統計

5.3 實驗方法

本實驗采用網絡仿真工具The ONE[25]，此平臺是專為評估 DTN網絡路由和應用協議設計的。本文通過The ONE提供的導入式移動模式（external movement）將處理過的2組數據導入到仿真平臺。

為了能更好評估算法性能，模擬時節點緩存大小設為10 MB，消息大小為5～10 kB。采取以下2種消息生成機制。

1) 每隔60～120 s隨機產生一條新消息，消息的源節點與目標節點隨機生成。消息產生位置和目標節點均勻分布在整個網絡，防止由于消息的局部性對實驗結果造成影響。

2) 每隔60～120 s隨機產生一條新消息，消息的源節點與目標節點之間一跳可達。消息目標節點選擇受到源節點的限制，目標節點距離源節點不遠，減少了“不存在路徑”的消息傳遞對實驗結果的影響。

BridgingCom算法能夠準確運行的前提是局部社區識別算法能準確獲知節點的社區信息。經過實驗發現[30]，連接時間閾值Fi確定時，算法2的并入閾值vj和合并閾值Fi～在0.5到0.9之間變化對獲得的局部社區劃分結果影響不大，且在一般情況下推薦閾值設置為0.6，因此本文采用如表2所示的參數。

表2 分布式社區識別算法基本參數

5.4 結果分析

為了模擬真實場景，使通信網絡中一直有新的消息加入，本文首先采用消息生成機制 1)，每隔60～120 s隨機選擇一個源節點產生一條新消息，然后隨機選擇消息的目標節點。在Reality數據集合和Infocom 2006數據集合上的不同TTL（time to live）下獲得仿真結果，并對各個路由算法的消息傳遞成功率、網絡傳輸冗余比和消息傳遞成功的平均延遲時間進行了詳細的分析和比較。

從圖4可以看出，隨著TTL增大，消息將有更大的機會到達目標節點，因此每種路由的傳遞成功率都隨著TTL的變化而逐漸提高。與其他算法相比，本文提出的BridgingCom算法在TTL比較小時優勢并不明顯，各個算法差異不大；但當TTL增大，特別是超過12 h后，由于BridgingCom算法有策略的限制消息復制，其傳遞性能優勢開始體現，表現出優于其他算法的傳遞成功率（除Epidemic算法外）。另外，當TTL繼續增大時，直到TTL等于模擬周期（也就是網絡中的消息會一直存在，不會因為TTL超時而被刪除）時，各個路由算法的傳遞成功率增長開始變得緩慢，特別是Epidemic算法表現最為明顯。

圖4 消息交付比率

圖 4 (b)中結果與圖 4 (a)整體趨勢一致，BridgingCom算法獲得了優于其他算法的傳遞成功率。不同的是，在 Infocom2006數據集中QualityEpidemic算法獲得了異常高的傳遞成功率，這是因為Infocom2006數據集中節點密度大（節點活動范圍小，連接事件發生頻繁），基于洪泛的QualityEpidemic算法無法有效選擇中繼節點，產生大量消息副本，可以從圖5(b)看出，雖然消息傳遞成功率提高，但是網絡副本數卻也同時大大增加，并沒有有效的控制副本數量。

圖5為各算法的傳輸冗余比結果。基于洪泛的Epidemic算法和 QualityEpidemic算法在網絡中副本數目最多，遠遠大于其他算法。BridgingCom算法在不同TTL下，產生的冗余消息數目穩定，冗余比增長緩慢。原因是BridgingCom算法根據目標節點的位置，選擇不同的中繼節點，與Epidemic算法相比，能夠顯著減少網絡開銷。

圖5 網絡傳輸冗余比

從圖6可以看到，隨著TTL增大，各個算法的平均延遲時間呈現增長趨勢。當TTL較小時，各個算法的消息平均延遲時間差別不大，但是當在圖6(a)中TTL增大到24 h、圖6(b)中TTL增大到3 h，各個算法產生的消息平均延遲時間差異變大。BridgingCom路由算法在提高消息傳遞成功率的同時能有效控制消息的平均傳遞延遲時間，特別是在網絡負載比較高時，BridgingCom路由算法有相對比較低的延遲時間，如圖 6(a)中TTL大于48 h之后，圖6(b)中TTL大于6 h之后。這是由于BridgingCom路由算法對有不同目的地的消息選擇不同路由策略，能有效控制消息的復制和傳遞方向。

圖6 消息平均延遲時間

可以從圖6(a)觀察到，Direct算法在TTL為6 h、12 h和24 h時的平均延時并沒有明顯大于其他算法。一般認為，Direct算法沒有消息復制，并且只當源節點遇到目標節點時才傳遞消息，應該是獲得傳遞機會最少的一種路由算法，而消息傳遞出去機會少，傳遞成功的延時應該會變大。

為了找到出現這個“異常結果”的原因，本文采用消息生成機制 2）控制消息的目標節點范圍，進行了一組新的實驗，在產生新消息時不再隨機設定目標節點，而是根據源節點不同選擇不同的目標節點，實驗結果如圖7所示。

從圖7可以發現，隨著TTL增大，各個算法的傳遞成功的消息的平均延時都逐步增大。當TTL比較小時，新產生的消息獲得的傳遞機會較小，這時各個算法之間的差異體現不大，因此各個算法的傳遞成功的消息的平均延時差不多。隨著TTL增大，雖然消息在網絡中保存時間增長，但Direct路由算法可供選擇的中繼節點有限，獲得的傳遞機會最少，呈現出較高的消息延時。因此，出現圖6(a)中的特殊情況的原因是其他算法傳遞成功的消息不僅包含直接傳遞成功的消息還包含大量的、花費較長時間間接傳遞成功的消息，大量需要長時間傳遞的消息將消息的傳輸延遲平均值提高。

圖7 消息平均延遲時間

另外，通過圖4可以看出，當完全隨機選擇新產生消息的源節點和目標節點時（消息生成機制1）），隨著TTL變化，各個算法在Reality數據集合和Infocom2006數據集合上的結果雖然整體變化趨勢類似，但也可以看出網絡連接密度對網絡傳輸效率的影響：網絡密度大，節點單位時間接觸到的鄰居多，消息有更多的轉發機會，也可能會產生更多的消息副本，增加網絡運行時的系統開銷和網絡資源消耗。

6 結束語

本文的貢獻是在 PSN中基于節點移動性和連接時間分析節點社會關系，引入橋接中心度（bridging centrality）作為中繼節點的選擇依據，提出了基于社會屬性的BridgingCom路由算法，并且在真實數據集合上驗證本算法的性能。實驗證明BridgingCom路由算法能以較低的網絡負載獲得較高的傳遞成功率。

PSN路由算法的研究難點在于如何在連接非持續、傳輸高延遲及資源受限的情況下，選定合適的數據傳輸路徑以完成高效的端到端傳輸，并實現數據傳輸成功率、傳輸能耗以及傳輸延遲之間的有效平衡。PSN作為一種具有社會規律性的 DTN，通過挖掘節點之間的社會關系可以更加可靠地預測節點移動規律，提高消息傳遞的效率。在完善現有的方法的同時，將密切關注當前國內外對 PSN路由提出的新理論新方法，深入研究 PSN中節點社會特征的理論支撐，考慮如何動態適應網絡實時變化調節社區識別的算法的閾值，以及有效的中繼節點度量等。

[1] HUI P， CHAINTREAU A，et al. Pocket switched networks and human mobility in conference environments[A]. Proc of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking[C]. ACM， 2005.244-251.

[2] DALY E， HAAHR M. Social network analysis for routing in disconnected delay-tolerant manets[A]. Proc of ACM MobiHoc[C]. ACM，2007. 32-40.

[3] HUI P， CROWCROFT J， YONEKI E. Bubble rap： social-based forwarding in delay-tolerant networks[J]. Mobile Computing， IEEE Transactions， 2011， 10(11)： 1576-1589.

[4] ZHU Y， XU B， SHI X，et al. A survey of social-based routing in delay tolerant networks： positive and negative social effects[J]. IEEE Communications Surveys & Tutorials， 2012， 15(1)： 387-401.

[5] EAGLE N， PENTLAND A. Reality mining： sensing complex social systems[J]. Personal and Ubiquitous Computing， 2006， 10(4)：255-268.

[6] DIOT C，et al. Haggle project[EB/OL]. http：//www.haggleproject.org，2004.

[7] 蘇金樹，胡喬林，趙寶康，彭偉.容延容斷網絡路由技術[J]. 軟件學報，2010，21(1)：119-132.SU J S， HU Q L， ZHAO B K， PENG W. Routing techniques on delay/disruption tolerant networks[J]. Journal of Software， 2010，21(1)：119-132.

[8] VAHDAT A， BECKER D. Epidemic routing for partially connected ad hoc networks[R]. Technical Report， 2000.

[9] ANDERS L， AVRI D， OLOV S. Probabilistic routing in intermittently connected networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review， 2003， 7(3)： 19-20.

[10] MILGRAM S. The small world problem[J]. Psychology Today， 1967，2： 60-67.

[11] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social networks， 1979，1(3)： 215-239.

[12] DALY E M， HAAHR M. Social network analysis for information flow in disconnected delay-tolerant MANETs[J]. IEEE Transactions on Mobile Computing， 2009， 8(5)： 606-621.

[13] SARAFIJANOVIC-DJUKIC M P N， GROSSGLAUSER M. Island hopping： efficient mobility-assisted forwarding in partitioned networks[A].Proc of Sensor and Ad Hoc Communications and Networks[C]. IEEE，2006. 226-235.

[14] HU T， HONG F， ZHANG X Q. BiBUBBLE： social-based forwarding in pocket switched networks[A].Proc of UIC/ATC[C]. IEEE， 2010.195-199.

[15] MTIBAA A， HARRAS K A. Social forwarding in large scale networks：insights based on real trace analysis[A].Proc of Computer Communications and Networks[C]. IEEE， 2011. 1-8.

[16] MEI A， MORABITO G， SANTI P，et al. Social-aware stateless forwarding in pocket switched networks[A].Proc of IEEE INFOCOM[C].IEEE， 2011. 251-255.

[17] GAO W， CAO G. User-centric data dissemination in disruption tolerant networks[A].Proc of IEEE INFOCOM[C]. IEEE， 2011.3119-3127.

[18] ORLINSKI M， FILER N. Quality distributed community formation for data delivery in pocket switched networks[A].Proc of SIMPLEX[C]. ACM， 2012. 31-36.

[19] LI Z， LI Q M， ZHANG H，et al.Closely social circuit based routing in social delay tolerant networks[J].Journal of Computer Research and Development，2012，49(6)：1185-1195.

[20] 程學旗， 沈華偉. 復雜網絡的社區結構[J].復雜系統與復雜性科學，2011(8)：57-70.CHENG X Q， SHEN H W. Community structure of complex networks[J].Complex Systems and Complexity Science，2011(8)：57-70.

[21] MARSDEN P V. Egocentric and sociocentric measures of network centrality[J]. Social Networks， 2002(24)： 407-422.

[22] HWANG W， CHO Y， ZHANG A.et al. Bridging centrality： identifying bridging nodes in scale-free networks[A].Proc of ACM SIGKDD[C].ACM， 2006.20-23.

[23] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social networks， 1979， 1(3)： 215-239.

[24] PAN H， EIKO Y， SHU Y C， JON C. Distributed community detection in delay tolerant networks[A].Proc of 2nd ACM/IEEE International Workshop on Mobility in the Evolving Internet Architecture[C].2007.27-30.

[25] ONE： Opportunistic Network Environment[EB/OL]. http：//www.netlab.tkk.fi/tutkimus/dtn/theone/. 2009.

[26] EAGLE N， PENTLAND A. Reality mining： sensing complex social systems[J]. Personal and Ubiquitous Computing， 2006， 10(4)：255-268.

[27] DIOT C，et al. Haggle project[EB/OL]. http：//www.haggleproject.org，2004.