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

袁培燕，宋明陽

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

0 引言

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

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

圖1 節(jié)點間社會距離示例

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

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

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

1 相關工作

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

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

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

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

2 路由算法設計

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

2.1 節(jié)點間朋友關系識別

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

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

圖2 節(jié)點間接觸穩(wěn)定性

圖3 節(jié)點間接觸規(guī)律性

2.2 節(jié)點間社會距離

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

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

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

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

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

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

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

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

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

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

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

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

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

圖6 節(jié)點a與d的朋友關系斷開

Fig. 6 Breaking up of friend relationship between nodeaandb

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

2.2.3 環(huán)路更新問題及解決

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

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

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

圖8 環(huán)路更新問題

2.2.4 節(jié)點間社會距離構建流程

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

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

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

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

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

算法1 節(jié)點間社會距離構建流程。

輸入：機會網絡節(jié)點集合V。

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

1)

FOR 任意節(jié)點a,b∈VDO

2)

IFa與b的鄰居關系斷開 THEN

3)

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

4)

IFENa的來源節(jié)點為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的目的節(jié)點項==ENa的目的節(jié)點項ANDENb的來源節(jié)點項!=aTHEN

15)

ENexist← true

16)

IFENa的來源節(jié)點項==bTHEN

17)

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

18)

ELSE IFENb的社會距離+1

19)

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

20)

END IF

21)

END IF

22)

IFENexist=false THEN

23)

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

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

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

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

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

1)

根據鄰居發(fā)現算法計算節(jié)點間鄰居關系

2)

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

3)

FOR 任意節(jié)點a,b∈VDO

4)

IFa與b接觸 THEN

5)

IFa與b互為鄰居 THEN

6)

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

7)

END IF

8)

FOR 在a的緩沖區(qū)中的任意數據包PKaDO

9)

IFPKa的備份不存在于b的緩沖區(qū)中 THEN

10)

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

11)

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

12)

a轉發(fā)PKa的備份至b

13)

END IF

14)

END IF

15)

END IF

16)

END FOR

17)

b接收a轉發(fā)的包的備份

18)

END IF

19)

END FOR

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

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

3 實驗結果與分析

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

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

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

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

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

圖9 投遞率指標對比

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

圖10 包傳輸延時指標對比

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

4 結語

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

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.