袁培燕，宋明陽

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

0 引言

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 路由算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

圖4 機會網(wǎng)絡(luò)朋友關(guān)系以及接觸的變化示例

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

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

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

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

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

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

2.2.2 朋友關(guān)系斷開時社會距離的更新

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

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

Fig. 6 Breaking up of friend relationship between nodeaandb

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

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

然而上述的更新規(guī)則會產(chǎn)生環(huán)路問題。如圖8(a)所示，在T0時刻，a與c的朋友關(guān)系斷開，a將自己表中來源節(jié)點為c的條目設(shè)置為無窮大，而在b中存有通過節(jié)點a更新的關(guān)于節(jié)點c的條目(目的節(jié)點為c、來源節(jié)點為a、社會距離為2)。在T1時刻如果節(jié)點b首先將該條目發(fā)送給a，那么根據(jù)上述的信息更新規(guī)則，a無條件根據(jù)新的條目更新舊的條目，這樣導(dǎo)致了a更新了錯誤的關(guān)于節(jié)點c的條目(目的節(jié)點為c、來源節(jié)點為b、社會距離為3)。在T2時刻，a又會將錯誤的條目繼續(xù)發(fā)送給b。依此循環(huán)，兩節(jié)點始終更新的是錯誤的條目。產(chǎn)生這種錯誤的原因在于：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ā)送的關(guān)于節(jié)點c的條目(目的節(jié)點為c、來源節(jié)點為a、社會距離為∞)并且通過新收到的條目將自己的關(guān)于節(jié)點c的條目進行更新(目的節(jié)點為c、來源節(jié)點為a、社會距離為∞)，至此a、b完成了正確的更新。

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

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

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

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

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

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

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

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

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

輸入：機會網(wǎng)絡(luò)節(jié)點集合V。

輸出：輔助信息交換次數(shù)。

1)

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

2)

IFa與b的鄰居關(guān)系斷開 THEN

3)

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

4)

IFENa的來源節(jié)點為bTHEN

5)

ENa的社會距離=∞

6)

END IF

7)

END FOR

8)

END IF

9)

IFa與b互為鄰居關(guān)系 ANDa與b接觸 THEN

10)

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

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é)點項設(shè)置為b

24)

將ENb插入a的社會距離表

25)

END IF

26)

END FOR

27)

END FOR

28)

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

29)

END IF

30)

END FOR

31)

RETURN 輔助信息交換次數(shù)

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

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

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

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

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

1)

根據(jù)鄰居發(fā)現(xiàn)算法計算節(jié)點間鄰居關(guān)系

2)

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

3)

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

4)

IFa與b接觸 THEN

5)

IFa與b互為鄰居 THEN

6)

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

7)

END IF

8)

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

9)

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

10)

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

11)

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

12)

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

13)

END IF

14)

END IF

15)

END IF

16)

END FOR

17)

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

18)

END IF

19)

END FOR

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

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

3 實驗結(jié)果與分析

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

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

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

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

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

圖9 投遞率指標(biāo)對比

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

圖10 包傳輸延時指標(biāo)對比

圖11 輔助信息交換次數(shù)對比

4 結(jié)語

本文針對信息輔助型機會路由算法的洪泛式信息交換方式所造成的網(wǎng)絡(luò)資源浪費問題，提出了分布式的社會距離路由算法。首先通過分析機會網(wǎng)絡(luò)中節(jié)點間接觸的規(guī)律性和穩(wěn)定性提出了機會網(wǎng)絡(luò)中朋友關(guān)系識別算法。然后聯(lián)合朋友關(guān)系確定出節(jié)點間親疏度關(guān)系并用社會距離來量化。一方面，輔助信息限于朋友節(jié)點間進行交換與共享，減少了信息的交換次數(shù)。另一方面，數(shù)據(jù)包交付給與其目的節(jié)點社會距離較短的節(jié)點來攜帶，可以提高數(shù)據(jù)包的投遞效率。最后實驗結(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] 馬華東,袁培燕,趙東.移動機會網(wǎng)絡(luò)路由問題研究進展[J].軟件學(xué)報,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.