移動機會網絡中一種輕量級的分布式社會距離路由算法

袁培燕，宋明陽

(河南師范大學 計算機與信息工程學院，河南 新鄉 453007)(*通信作者電子郵箱peiyan@htu.cn)

0 引言

隨著短距離無線通信以及傳感器技術的飛速發展，目前的智能移動設備，如智能手機、平板電腦和筆記本電腦擁有了強大的移動通信與數據感知功能。利用這些設備組成的移動機會網絡可以通過使用本地無線鏈路來進行復雜情況下的自組織通信。目前，移動機會網絡不僅支持新興的應用，比如移動電子商務服務、災難搜救服務以及移動社交服務，也支持傳統的服務，如內容分發、萬維網應用等。不同于存在端到端數據傳輸路徑的傳統無線傳感網絡或自組織網絡。在移動機會網絡中，數據包的源節點和目的節點之間不存在可靠的端到端路徑，數據包的傳輸依賴于節點的移動性和機會性接觸，并以“存儲、攜帶、轉發”的模式工作[1]，因此，如何在鏈路間歇性連接的情況下有效地傳輸數據是移動機會網絡面臨的一大挑戰。洪泛[2]是最早提出的一種機會路由算法。它通過向網絡中擴散數據包的備份的方式(每當兩個節點相遇時它們都會將自己的數據包的備份復制給對方)來將數據包投遞至其目的節點，該方式并不需要復雜的路由決策(當兩節點相遇時判斷將數據包發送給對方是否對該數據包到達其目的節點具有正面影響)。洪泛算法雖然擁有最優的包的投遞率和投遞延遲性能，但由于網絡中存在較多的數據包備份，因此傳輸代價也較高。研究人員提出了一些更為智能化的方案來改善洪泛的高負載問題。這些方案可以分為兩類：基于節點接觸信息的路由策略和基于節點社會關系信息的路由策略。基于節點接觸信息的路由通常利用節點間接觸概率、歷史接觸記錄、接觸位置和次數以及節點間運動相似度來幫助路由決策。基于節點社會關系的路由通常將數據包投遞至具有較高中心性的節點或選擇與數據包目的節點具有相似性(興趣、上下文、朋友、社區)的中繼節點。上述兩類路由算法的共同點在于它們使用了額外信息(接觸信息、社會信息)來為數據包選擇具有更高轉發效率的中繼節點。這些運用到額外信息(本文稱之為輔助信息)幫助數據包轉發的路由策略統稱為信息輔助型路由算法[3]。信息輔助型路由策略雖然解決了洪泛路由由于過多的數據包備份而造成的網絡開銷過大問題，但是節點之間的輔助信息的共享方式依然采用類似于洪泛的方式進行(每當兩個節點接觸時會交換并更新彼此的輔助信息)。這樣會造成兩方面的網絡開銷：首先，網絡中節點每進行一次輔助信息的交換會浪費電量與帶寬；其次，過多的輔助信息會占用設備有限的存儲空間。由此可見，傳統的輔助信息型路由算法在大型的移動機會網絡中依然會造成較大的網絡開銷。

針對此問題，本文提出一種結合節點接觸信息與社會關系的輕量級分布式社會距離機會路由算法。該算法首先通過分析節點間接觸的穩定性與規律性來確立節點間的朋友關系，然后利用朋友關系來構建出節點之間的關系親疏程度(親密和疏遠的程度)。如圖1所示，該圖描述了一個擁有8個節點的小型機會網絡在某時刻內節點間接觸以及朋友關系。從圖中可以看出，節點之間雖然不能兩兩互為朋友，但是可以通過朋友節點之間多跳傳輸完成數據投遞。本文使用社會距離來量化節點之間的朋友關系。以節點a為例，a與b為朋友，它們的社會距離為1，而a與b的朋友d和e的距離則為2，依此類推。由于朋友節點之間接觸頻繁且有規律，因此由朋友關系所構成的節點間社會距離越短則代表節點間關系越密切。當a中有一個目的節點為g的數據包并且a與d接觸時，由于d與g的社會距離更短，d具有更大的幾率遇到g，所以a將數據包發送給d。總之，與包的目的節點社會距離越短的節點，其投遞該包效率也就越高。

圖1 節點間社會距離示例

此外社會距離的建立并不需要通過所有節點進行洪泛式的信息交換來完成，只需要通過朋友節點之間進行信息交換和共享即可。由于所有節點并不能兩兩建立朋友關系，所以信息的共享僅發生在有限的節點對之間，因此可以大量減少信息的交換次數。

本文的貢獻如下：1)通過分析節點間的接觸規律性與穩定性提出了一種節點間朋友關系識別方法，為機會網絡中節點之間的社會性研究提供了新的依據。2)在朋友關系的基礎上，提出了一種輕量級的分布式距離向量機會路由算法，節點之間通過有選擇地信息共享方式來構建節點間社會距離，并以此作為輔助信息來協助路由決策。

實驗結果顯示，該算法與經典的輔助信息型路由算法在投遞率、包傳輸延時指標有所提升的前提下，輔助信息的交換次數大幅減少，節省了網絡資源。

1 相關工作

利用一些額外的信息協助節點進行數據包轉發決策是當前機會網絡路由算法研究的重點之一。下面來介紹一些相關的工作。

基于節點接觸信息的路由策略：文獻[4]根據節點間的接觸次數以及接觸時長，提出了利用接觸和傳輸記錄的概率路由(Probabilistic Routing Protocol using History of Encounters and Transitivity， PRoPHET)算法。PRoPHET通過記錄并分析接觸歷史記錄來計算節點之間的接觸概率，當兩個節點發生接觸時，它們的接觸概率相應增加，而當它們經過一段時間沒有發生接觸時，接觸概率相應下降。文獻[5]提出了一種結合噴霧—等待策略并考慮到緩沖區管理的多備份概率路由。文獻[6]提出了利用直接接觸的節點和兩跳鄰居節點的歷史接觸信息計算接觸概率的改進型概率路由。文獻[7]結合節點間最大相遇次數、數據包最大化投遞概率以及最小化目標節點的距離等三個指標提出了多目標函數，并將該函數優化后作為數據包的路由轉發的依據。文獻[8]提出了一種基于數據包傳遞概率機會路由算法，其中數據包的傳遞概率的計算結合了節點的接觸頻率以及接觸持續時間。

基于節點社會關系信息的路由策略：文獻[9]提出利用節點的接觸頻率、平均接觸時長、接觸的規律性來識別節點的社會關系。文獻[10]利用鄰居節點的接觸信息，分布式地估計節點的中心度和相似度,并融合二者提出基于中心度與相似度的路由(routing based on Betweenness centrality and Similarity， SimBet)算法。當兩個節點相遇時，需要交換各自鄰域知識，計算中心度和相似度,然后將數據包轉發給效用值較高的節點。此外，文獻[11]提出了經典的人群排名(PeopleRank)路由算法分布式地計算節點的中心度，降低了傳統社會化網絡分析方法計算節點中心度的算法復雜度，取得了比較好的效果。文獻[12]提出以模糊推理方法來對節點位置相似性以及社會相似性信息進行處理來得到輔助信息，并以此作為數據包轉發的依據。文獻[13]首先通過分析網絡中節點的實時數據來提取影響節點間社會關系的因素；然后對這些因素的復雜性和動態性進行推理和評估，并從其中計算出每個節點的社會關系值；最后基于社會關系值來建立鄰居節點的拓撲信息來為數據包選擇下一跳中繼節點。

上述類型的信息輔助型路由算法所關注的是數據包的轉發問題。然而，對于從減少節點間輔助信息交換次數的角度來提升路由算法的性能，據作者所知尚無相關工作。而本文則圍繞這一問題進行討論，并提出了分布式社會距離機會路由算法，致力于在保證數據包轉發效率基礎上減少輔助信息的交換次數。

2 路由算法設計

在以往的機會路由算法中輔助信息的交換與共享是所有節點共同參與的，然而，這將消耗大量的網絡帶寬與存儲資源(當信息交換時，接收方首先需要存儲接收到的信息；然后更新自己的輔助信息；最后將收到的信息刪除，但是在刪除之前，即時性保存接收到信息的依然會占用存儲空間，進而導致影響數據包的接收與存儲。在本文的方法中由于減少了信息的交換次數，因此有大量的節點無需進行臨時信息的存儲，減少了存儲資源的浪費)，因此在設計路由算法時應當考慮減少過多的信息交換。此外，在減少信息交換的前提下，應該保證信息共享的高效性與正確性；否則，錯誤的輔助信息會引導數據包到一條較差的路徑，進而影響到路由性能(投遞率與投遞延時)。下面來介紹本文的解決方案。

2.1 節點間朋友關系識別

信息的高效共享依賴于節點之間是否擁有緊密的聯系，但是與傳統強連通自組織網絡中顯性的節點關系不同，移動機會網絡中，節點的接觸情況是時變的、復雜的。有的節點對頻繁接觸，有的偶爾接觸，有的接觸時間長，有的間隔時間長。節點之間呈現一種動態變化的連接方式。針對這種連接方式，本文聯合節點接觸情況的穩定性、規律性來判別節點的朋友關系：如果一對節點在接觸時長和接觸時間間隔方面有較高的穩定性和較好的規律性，則將它們定義為朋友。通過識別節點的朋友關系，一方面可以將機會網絡中具有緊密關系的節點對更清晰地刻畫出來，另一方面輔助信息在朋友節點之間可以更高效地共享。

本文觀察兩節點在時間段內的接觸總時長的長短來判斷節點間的接觸穩定性。圖2描述了a,b∈V兩節點在19 s的時間段內的兩種接觸情況。通過對比可以發現，在圖2(b)所描述的接觸情況中a、b兩節點的總接觸時間(16 s)遠遠大于圖2(a)(8 s)，并且在接觸間隔時間方面前者也遠遠小于后者。如果節點之間每隔固定時間(比如1 s)進行一次信息交換與更新的話，那么在時間段內節點間接觸時間越多(圖2(b))則越能保證信息更新的實時性與正確性。如果節點間接觸間隔時間越長(圖2(a))，則節點間的信息更新將會受到較大的影響(間隔時間內節點間無法進行信息更新)而導致信息陳舊與無法保證信息更新實時性。因此本文對機會網絡中節點間接觸的穩定性描述為：在時間段內，如果兩個節點的平均接觸時長較大(對于節點a來說則是大于該節點與其所有接觸過的節點的平均接觸時間，節點b同理)，則說明這兩個節點的接觸是穩定的。

圖2 節點間接觸穩定性

圖3 節點間接觸規律性

2.2 節點間社會距離

在社交網絡中，節點(手持移動設備的人)通常會較為頻繁地、有規律地與其熟悉的節點相遇，如在一起工作和學習的同事、同學、朋友或家人等。這些相互熟悉的節點在數據轉發中扮演了重要的角色[14]。通常這些節點之間具有最為緊密的社會關系。而在以人為本的機會網絡中，如果可以充分利用熟悉的節點之間的緊密關系，則可以確定出機會網絡中節點之間的社會關系的緊密程度。在本文中，首先定義具有最高緊密度社會關系的節點對互為朋友節點(朋友關系)。然后聯系朋友關系，將節點之間社會關系的緊密程度用社會距離來量化。社會距離越大則代表兩節點的社會關系越疏遠；反之越緊密。

2.2.1 朋友節點間接觸時社會距離的構建

假設機會網絡G(V)中的任意節點a∈V維護了一張社會距離表用來記錄與其他節點的社會距離。表的每一行代表一個條目，每個條目中包括三個項：①需要計算社會距離的目的節點；②社會距離；③該條目的來源節點ID。節點的社會距離表的構建主要分為以下步驟：

1)當兩節點被檢測互為朋友時，其將對方的相關信息加入到社會距離表中：以節點a為例，在T0時刻a與節點b被識別為朋友關系(如圖4(a)所示)。然后a將節點b的相關信息作為條目插入到表中，由于兩節點互為朋友，所以a與b的社會距離項為最小值1，并且該條目的來源節點項與目的節點項一致為b(如圖5(a)所示)。由于a、b兩節點是由相互接觸而識別對方為朋友關系并將對方的信息記錄在表中，因此在上述步驟中并沒有發生信息的交換。

圖4 機會網絡朋友關系以及接觸的變化示例

2)當兩節點在互為朋友的基礎上接觸時交換并更新各自的社會距離表：在T1時刻，a與b在互為朋友的情況下相互接觸(如圖4(b)所示)。首先a獲取b的表中記錄的關于目的節點c、d、e的條目，由于在a的表中不存在關于目的節點c、d、e的條目，因此a將這些獲取到的條目中的社會距離項+1并將來源節點項設置為b之后直接插入到表中(如圖5(b)所示)。

圖5 節點a的社會距離表變化情況(對照圖4)

3)當獲取到的新條目與表中已存在的條目中的目的節點項相同時，則分以下兩種情況進行更新：

①已有條目的來源節點項與新條目來源節點相同時，無條件使用新條目更新已有條目：如圖4(c)所示，在T2時刻b、c的朋友關系斷開，b、e互為朋友關系，并且b的社會距離表完成了更新。此時a與b在互為朋友的情況下相互接觸后，a獲取b的表中關于目的節點c、d、e的條目，將社會距離項+1并將來源節點項設置為b之后直接覆蓋更新相應的原有條目(如圖5(c)所示)。

②已有條目的來源節點項與新條目的來源節點不同時則比較它們的社會距離，如果新條目的社會距離+1仍小于已有條目的社會距離，則使用新條目更新已有條目：如圖4(d)所示，在T3時刻，a、c在互為朋友的基礎上進行接觸并且a獲取節點c中關于目的節點d、e的條目。通過對比發現，從節點c獲取的關于目的節點d的條目的社會距離項+1小于表中已有的條目(2<3)，因此將新的條目社會距離項+1且來源節點項設置為c后覆蓋更新舊的條目。然而從c獲取的關于目的節點e的條目的社會距離項+1大于表中已有的相應的條目(3>2)，因此保留原表項不進行更新(如圖5(d)所示)。

上述是節點a與其朋友節點接觸之后社會距離表的更新過程。同樣的，a的朋友節點也會采取同樣的策略來進行表的更新。上述過程中，一個節點獲取另一個節點的信息(條目)，本文稱之為一次輔助信息的交換。相比傳統機會路由算法中洪泛式的信息交換策略，在該算法中由于節點間在接觸的基礎上互為朋友才交換信息，并且節點間并非兩兩互為朋友，因此該算法可以減少大量的信息交換次數。

2.2.2 朋友關系斷開時社會距離的更新

當兩節點的朋友關系斷開時，為了保證社會距離表能夠正確更新，令節點將以對方為來源節點的條目中社會距離設置為無窮大，并且將這些條目擴散至其接觸到的其他的朋友節點。這樣一來其他節點能迅速得知周圍節點的社會距離變化情況。如圖6所示，a與d的朋友關系在某時刻內斷開，此時，a會將自己表中來源節點為d的條目的社會距離設置為無窮大(如圖7(a)所示)。當a與其朋友節點b接觸時，a將社會距離被設置為無窮大的條目發送至其朋友節點b，b則無條件根據接收到條目來更新對應舊的條目(如圖7(b)所示)。對于節點d而言也會重復同樣的操作進行更新。

圖6 節點a與d的朋友關系斷開

Fig. 6 Breaking up of friend relationship between nodeaandb

圖7 朋友關系斷開后節點a與b的表的更新(對照圖6)

2.2.3 環路更新問題及解決

然而上述的更新規則會產生環路問題。如圖8(a)所示，在T0時刻，a與c的朋友關系斷開，a將自己表中來源節點為c的條目設置為無窮大，而在b中存有通過節點a更新的關于節點c的條目(目的節點為c、來源節點為a、社會距離為2)。在T1時刻如果節點b首先將該條目發送給a，那么根據上述的信息更新規則，a無條件根據新的條目更新舊的條目，這樣導致了a更新了錯誤的關于節點c的條目(目的節點為c、來源節點為b、社會距離為3)。在T2時刻，a又會將錯誤的條目繼續發送給b。依此循環，兩節點始終更新的是錯誤的條目。產生這種錯誤的原因在于：b在收到a的條目并使用其更新自己的條目之后，b又將通過a更新過的條目發回給了節點a，這樣造成了a的錯誤更新，并在后續的時間里a與b交換錯誤的條目造成了環路更新。

如果b不將通過a更新的條目發回給節點a，則可以避免a進行錯誤的更新，進而避免a、b進行環路更新。如圖8(b)所示，在T1時刻，b拒絕將條目(目的節點為c、來源節點為a、社會距離為2)發送給a。在T2時刻，b接收a發送的關于節點c的條目(目的節點為c、來源節點為a、社會距離為∞)并且通過新收到的條目將自己的關于節點c的條目進行更新(目的節點為c、來源節點為a、社會距離為∞)，至此a、b完成了正確的更新。

綜上所述，對于節點的社會距離表中的每一個條目來說，令其不能更新其來源節點的社會距離表，則可以解決節點之間的環路更新問題。

圖8 環路更新問題

2.2.4 節點間社會距離構建流程

在這里給出了節點間社會距離的計算流程，大致如下：

1)首先識別節點間的朋友關系(2.1節)。

2)檢測節點間朋友關系是否有斷開情況(如果在上個時間段內兩節點被判定為朋友，而在目前時間段內不為朋友，則可以判定兩節點的朋友關系斷開)。如果斷開的話則根據2.2.2節的規則進行社會距離表的更新。這樣的好處在于節點能夠在第一時間內發現朋友關系的斷開情況，并且在后續的社會距離構建過程中可以這些把斷開情況通知給其他接觸到的朋友節點，以便讓這些節點能夠及時感知到與其他節點的社會距離變化情況，避免錯誤的更新。

3)當朋友節點之間接觸時根據2.2.1節的規則進行社會距離表的構建。需要注意的是，在更新的過程中對于表中的任意條目而言，不能用于更新其來源節點的社會距離表，以防出現環路更新問題(如2.2.3節所述)。

4)每當節點間進行一次社會距離表的交換時，記錄一次信息交換次數，以便和傳統的輔助信息路由算法進行對比。社會距離的詳細構建流程已寫成偽碼，如算法1所示。

算法1 節點間社會距離構建流程。

輸入：機會網絡節點集合V。

輸出：輔助信息交換次數。

1)

FOR 任意節點a,b∈VDO

2)

IFa與b的鄰居關系斷開 THEN

3)

FORa中的社會距離表中的任意條目ENaDO

4)

IFENa的來源節點為bTHEN

5)

ENa的社會距離=∞

6)

END IF

7)

END FOR

8)

END IF

9)

IFa與b互為鄰居關系 ANDa與b接觸 THEN

10)

a獲取b的社會距離表，輔助信息交換次數++

11)

FORa獲取的b的社會距離表中的任意條目ENbDO

12)

ENexist← false

13)

FORa中的社會距離表中的任意條目ENaDO

14)

IFENb的目的節點項==ENa的目的節點項ANDENb的來源節點項!=aTHEN

15)

ENexist← true

16)

IFENa的來源節點項==bTHEN

17)

ENa的社會距離項=ENb的社會距離項+1 ANDENa的來源節點項=b

18)

ELSE IFENb的社會距離+1

19)

ENa的社會距離項=ENb的社會距離項+1 ANDENa的來源節點項=b

20)

END IF

21)

END IF

22)

IFENexist=false THEN

23)

ENb的社會距離項+1，來源節點項設置為b

24)

將ENb插入a的社會距離表

25)

END IF

26)

END FOR

27)

END FOR

28)

a完成社會距離表更新并刪除獲取到的社會距離表

29)

END IF

30)

END FOR

31)

RETURN 輔助信息交換次數

算法1)～8)行判斷a和b兩節點在當前時間段內是否斷開，如果是則a將自己表中來源節點為b的條目中社會距離項設置為無窮大。算法9)～10)行判斷節點a與b是否在互為朋友的情況下相互接觸，如果是則a獲取b的社會距離表并記錄一次信息交換次數。算法11)～21)行a將獲取到的b的社會距離表中的任意條目ENb和a的社會距離表中的任意條目ENa進行對比。如果ENb與ENa的目的節點項相同并且ENb的來源節點不是a(這里保證社會距離構建時不產生環路)，則滿足信息更新條件：如果ENa的來源節點項為b，則ENa的社會距離項被ENb的社會距離項+1賦值，來源節點項設置為b(算法16)～17)行)；否則如果ENb的社會距離+1小于ENa的社會距離那么執行與算法17)行相同操作。算法22)～27)行，如果a的社會距離表中不存在與ENb具有相同目的節點項的條目，則將ENb的社會距離項+1且來源節點項設置為b，然后將該項插入到自己的社會距離表中。算法28)～31)行，當a完成社會距離表的更新后刪除獲取到的b的社會距離表釋放空間。最后返回信息的交換次數。

2.3 分布式社會距離路由算法

在路由決策(數據包傳遞)方面，節點總是將數據包發送到距離其目的節點社會距離最短的節點。如圖1所示，以節點a為例，a中攜帶有一個目的節點為g的數據包，當a與d接觸時，通過判斷d與g的社會距離小于a與g，因此，a將數據包發送給d。由d攜帶該數據包將會更高效地將其發送到其目的節點g。

下面總結了分布式社會距離路由算法并給出了偽碼，如算法2所示。

算法2 分布式社會距離機會路由算法。

1)

根據鄰居發現算法計算節點間鄰居關系

2)

檢測鄰居關系斷開情況并進行節點內社會距離表的更新

3)

FOR 任意節點a,b∈VDO

4)

IFa與b接觸 THEN

5)

IFa與b互為鄰居 THEN

6)

交換并更新各自的社會距離表

7)

END IF

8)

FOR 在a的緩沖區中的任意數據包PKaDO

9)

IFPKa的備份不存在于b的緩沖區中 THEN

10)

IFa和b的社會距離表中都存在有目的節點項為PKa的目的節點的條目(分別為ENa和ENb) THEN

11)

IFENa的社會距離>ENb的社會距離 THEN

12)

a轉發PKa的備份至b

13)

END IF

14)

END IF

15)

END IF

16)

END FOR

17)

b接收a轉發的包的備份

18)

END IF

19)

END FOR

算法1)～2)行首先通過朋友發現算法確定節點間朋友關系，檢測節點間朋友關系是否有斷開情況并進行相應的社會距離表的更新。算法3)～7)行對于任意節點a和b判斷是否互為朋友并且相互接觸，如果滿足則交換并更新社會距離表。算法8)～16)行對于在a的緩沖區中的任意數據包PKa，如果該包的備份不存在于b的緩沖區內，并且a與b的社會距離表中都存在有目的節點項為PKa的目的節點的條目，其分別為ENa和ENb，那么比較ENa與ENb的社會距離，如果前者大于后者則證明b到PKa的目的節點的社會距離小于a，因此a將包PKa轉發給b。算法17)～19)行節點b接收a轉發的包的備份。算法結束。

下面對輔助信息的交換次數進行量化分析。將兩節點相互接觸設為隨機事件C，互為朋友設為隨機事件F，那么兩事件發生的概率分別為P(C)和P(F)。在傳統的機會路由算法中輔助信息的交換概率為P(C)，因為當兩節點接觸時就交換輔助信息。下面分兩種情況進行討論：當兩事件為獨立事件，在社會距離路由算法中交換輔助信息的概率為P(C∩N)=P(C)*P(N)，即兩節點同時相互接觸并且互為朋友的概率。設P(C)與P(N)分別為0.5與0.4，那么P(C∩N)=0.2

3 實驗結果與分析

本文對所提出的社會距離路由算法在Visual C++ 6.0平臺上面進行了集成，并以經典的輔助信息路由算法——PRoPHET算法(基于接觸信息的路由)與SimBet算法(基于社會信息的路由)進行性能上的對比與分析。實驗場景如下：節點間最大通信距離為25 m，每隔1 s搜索一次鄰居(接觸關系)節點，仿真時間為15 000 s。采用的真實節點移動數據集來源于韓國科學技術院(Korea Advanced Institute of Science and Technology， KAIST)，其記錄了大學校園內人群的日常活動行為軌跡。共有34人參與到數據的收集過程，每人手持全球定位系統(Global Positioning System， GPS)設備收集其92天的日常移動軌跡，關于該數據集的具體細節可以在文獻[15]中查閱。本文使用3個指標來評價路由算法的性能：

1)投遞率。網絡中被成功接收的包的數量和產生的包的數量的比值，其代表了網絡中包可以被成功投遞到目的節點的比率。

2)包傳輸延時。網絡中所有到達目的地的包從產生到傳輸至目的節點所需的時間的平均值。

3)輔助信息交換次數。網絡中所有節點通過其他節點獲取輔助信息的總次數。

圖9～11分別展示了3種算法在投遞率、延時以及輔助信息交換次數的對比。對于投遞率方面，如圖9所示，從整體上來看，社會距離算法要高于PRoPHET與SimBet約0.6左右。而在仿真時間的初期(也就是0～2 800 s時)社會距離算法的投遞率略低，這是因為在算法執行的初期，由于節點間接觸次數有限，導致了節點的社會距離表更新的不完整，使用不完整的社會距離會導致將包引入較差的路徑，進而導致投遞率較低，但是隨著社會距離表的更新完整，數據包可以被正確的輔助信息來引導入一條較高的轉發效率的路徑。對于包傳輸延時方面，如圖10所示，在仿真時間0～4 200 s時社會距離算法要高于PRoPHET與SimBet，而在4 200 s到仿真時間結束時，傳輸延時則逐漸降低，平均降低250 ms。其原因與投遞率類似：由于仿真前期社會距離表的不完整，導致包的投遞效率不高，投遞一個包需要花費較多的時間；隨著社會距離表的更新趨于完善，包的投遞效率上升，進而投遞數據包需要花費的時間減少，延時因此下降。

圖9 投遞率指標對比

對于輔助信息的交換總次數，從圖11可以看出，從仿真時間開始社會距離算法就遠遠低于PRoPHET與SimBet，并且隨著時間的推移，社會距離算法輔助信息交換次數的漲幅也遠遠低于洪范機制，在仿真時間的最后，PRoPHET與SimBet的交換次數約在76萬次左右，而選擇性移交機制則只有28萬次左右，增益超過63%。其原因如下：對于PRoPHET而言，每當兩節點接觸時需要通過獲取對方節點中對于其他節點的接觸概率來計算接觸概率的傳遞性。而對于SimBet而言，當兩節點相遇時，需要交換各自的鄰域知識來計算中心度與相似度。上述兩種算法的輔助信息的交換是洪泛式的，也就是說，節點間的接觸總次數即是信息的交換次數。而對于社會距離路由算法來說，輔助信息(社會距離表)的交換是節點間在互為朋友的基礎上進行的，而機會網絡中節點間的朋友個數是有限的，因此朋友間的接觸次數即是信息的交換次數。對比與洪泛式的信息交換策略，該方式明顯可以減少大量信息交換。

圖10 包傳輸延時指標對比

圖11 輔助信息交換次數對比

4 結語

本文針對信息輔助型機會路由算法的洪泛式信息交換方式所造成的網絡資源浪費問題，提出了分布式的社會距離路由算法。首先通過分析機會網絡中節點間接觸的規律性和穩定性提出了機會網絡中朋友關系識別算法。然后聯合朋友關系確定出節點間親疏度關系并用社會距離來量化。一方面，輔助信息限于朋友節點間進行交換與共享，減少了信息的交換次數。另一方面，數據包交付給與其目的節點社會距離較短的節點來攜帶，可以提高數據包的投遞效率。最后實驗結果證明了算法的有效性。未來的工作是基于該路由算法考慮緩沖區管理策略，以便進一步優化該算法的性能。

References)

[1] YUAN P, FAN L, LIU P, et al. Recent progress in routing protocols of mobile opportunistic networks [J]. Journal of Network & Computer Applications, 2016, 62: 163-170.

[2] VAHDAT A, BECKER D. Epidemic routing for partially-connected Ad Hoc networks, technical report CS- 200006 [R]. Durham: Duke University, 2000: 5.

[3] 馬華東,袁培燕,趙東.移動機會網絡路由問題研究進展[J].軟件學報,2015,26(3):600-616.(MA H D, YUAN P Y, ZHAO D. Research progress on routing problem in mobile opportunistic networks [J]. Journal of Software, 2015, 26(3): 600-616.)

[4] LINDGREN A, DORIA A, SCHELéN O, et al. Probabilistic routing in intermittently connected networks [J]. ACM SIGMOBILE Mobile Computing & Communications Review, 2004, 7(3): 239-254.

[5] LI Z, SHEN H. Probabilistic routing with multi-copies in delay tolerant networks [C]// Proceedings of the 2008 International Conference on Distributed Computing Systems Workshops. Piscataway, NJ: IEEE, 2008: 471-476.

[6] WANG X, HE R, LIN B, et al. Probabilistic routing based on two-hop information in delay/disruption tolerant networks [J]. Journal of Electrical & Computer Engineering, 2015, 2015(3): Article No. 9.

[7] BORAH S J, DHURANDHER S K, WOUNGANG I, et al. A multi-objectives based technique for optimized routing in opportunistic networks [J]. Journal of Ambient Intelligence & Humanized Computing, 2017, 2017(1): 1-12.

[8] YU C, TU Z, YAO D, et al. Probabilistic routing algorithm based on contact duration and message redundancy in delay tolerant network [J]. International Journal of Communication Systems, 2016, 29(16): 2416-2426.

[9] BULUT E, SZYMANSKI B K. Exploiting friendship relations for efficient routing in mobile social networks [J]. IEEE Transactions on Parallel & Distributed Systems, 2012, 23(12): 2254-2265.

[10] DALY E M, HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANETs [C]// Proceedings of the 2007 International Symposium on Mobile Ad Hoc Networking and Computing. New York: ACM, 2007: 32-40.

[11] MTIBAA A, MAY M, DIOT C, et al. PeopleRank: social opportunistic forwarding [C]// Proceedings of the 2010 Conference on Information Communications. Piscataway, NJ: IEEE, 2010: 111-115.

[12] JANG K, LEE J, KIM S K, et al. An adaptive routing algorithm considering position and social similarities in an opportunistic network [J]. Wireless Networks, 2016, 22(5): 1537-1551.

[13] WU X H, GU X F, POSLAD S. Routing algorithm based on social relations in opportunistic networks [C]// Proceedings of the 2015 International Computer Conference on Wavelet Active Media Technology and Information Processing. Piscataway, NJ: IEEE, 2015: 146-149.

[14] CHAINTREAU A, HUI P, CROWCROFT J, et al. Impact of human mobility on the design of opportunistic forwarding algorithms [C]// Proceedings of the 2006 International Conference on Computer Communications. Piscataway, NJ: IEEE, 2006: 1-13.

[15] RHEE I, SHIN M, HONG S, et al. On the levy-walk nature of human mobility [J]. IEEE/ACM Transactions on Networking, 2011, 19(3): 630-643.

This work is partially supported by by the National Natural Science Foundation of China (U1404602), the Science and Technology Foundation of Henan Province (172102210341), the Young Scholar Program of Henan Province (2015GGJS086), the Doctoral Research Startup Project of Henan Normal University (qd14136), the Young Scholar Program of Henan Normal University (15018).

YUANPeiyan, born in 1978, Ph. D., associate professor. His research interests include mobile communication and group intelligence computation.

SONGMingyang, born in 1991, M. S. candidate. His research interests include mobile opportunity network.