宋明陽，袁培燕

河南師范大學(xué) 計算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453000

1 引言

移動機(jī)會網(wǎng)絡(luò)[1]被廣泛應(yīng)用于車載通信、深空網(wǎng)絡(luò)、環(huán)境監(jiān)測等場景。在傳輸數(shù)據(jù)時，由于數(shù)據(jù)包的源節(jié)點和目的節(jié)點之間不存在可靠的端到端路徑，數(shù)據(jù)包的傳輸依賴節(jié)點的移動性和偶發(fā)性接觸，以“存儲、攜帶、轉(zhuǎn)發(fā)”的模式工作。

為了選擇有效的中繼節(jié)點，通常需要引入額外的信息進(jìn)行決策判斷（本文稱之為輔助信息），協(xié)助路由算法轉(zhuǎn)發(fā)數(shù)據(jù)包。這些輔助性信息主要包括數(shù)據(jù)屬性、節(jié)點信息、拓?fù)湫畔⒁约靶畔⑷诤系?類。比如數(shù)據(jù)包效用值和存活時間、節(jié)點的移動速度、社會關(guān)系以及節(jié)點之間的接觸概率、網(wǎng)絡(luò)的局部拓?fù)涞取?/p>

明顯地，輔助信息對于機(jī)會路由算法的性能有著重要的影響。然而，在目前的信息輔助型機(jī)會路由算法中普遍采用一種基于節(jié)點間機(jī)會接觸的洪泛型擴(kuò)散方式來共享輔助信息，即每當(dāng)兩個節(jié)點接觸時，它們就會向?qū)Ψ秸埱蟛@取相關(guān)信息來完成輔助信息的共享。然而由于便攜式設(shè)備（節(jié)點）存儲容量和能量有限，既要存儲感知數(shù)據(jù)（數(shù)據(jù)包），又要存儲輔助信息，將對移動設(shè)備的容量提出更高的要求。同時，大量的輔助信息的交換也會帶來浪費網(wǎng)絡(luò)帶寬和設(shè)備能量等問題。因此如何解決信息的共享需求與移動設(shè)備資源受限之間的矛盾是機(jī)會網(wǎng)絡(luò)中的關(guān)鍵性問題。針對此問題，本文提出了一種層次化的輔助信息獲取機(jī)制，該機(jī)制通過兩個層面來對節(jié)點進(jìn)行定義與劃分，并使節(jié)點間有選擇性地進(jìn)行輔助信息的共享：首先，為保證網(wǎng)絡(luò)中輔助信息的更新速度較快，將網(wǎng)絡(luò)中具有緊密關(guān)系的節(jié)點定義為鄰居，令互為鄰居的兩個節(jié)點間進(jìn)行信息獲取。其次，為保證輔助信息的網(wǎng)絡(luò)覆蓋率較高，將網(wǎng)絡(luò)中的節(jié)點劃分為社會性節(jié)點和普通節(jié)點，使信息的獲取主要發(fā)生在社會性節(jié)點與普通節(jié)點之間。這樣一來，理論上可以在不影響網(wǎng)絡(luò)性能的基礎(chǔ)上減少節(jié)點之間信息的獲取次數(shù)。本文的主要貢獻(xiàn)如下：

（1）通過觀察節(jié)點間的機(jī)會性接觸，分析節(jié)點間的接觸規(guī)律，將機(jī)會網(wǎng)絡(luò)中隱性的鄰居關(guān)系以顯性的方式表現(xiàn)出來，提出了一種機(jī)會網(wǎng)絡(luò)鄰居發(fā)現(xiàn)機(jī)制。

（2）在鄰居發(fā)現(xiàn)的基礎(chǔ)上，提出了一種分層的輔助信息獲取機(jī)制。一方面，令少部分社會性節(jié)點負(fù)責(zé)輔助信息的交換；另一方面，令互為鄰居的節(jié)點間進(jìn)行輔助信息的交換。

（3）提出的輔助信息獲取機(jī)制可以無縫地集成于經(jīng)典的信息輔助型機(jī)會路由算法之中。實驗結(jié)果顯示，在不顯著影響路由投遞率、延時與包投遞備份數(shù)的基礎(chǔ)上，大幅度減少了節(jié)點之間輔助信息的獲取次數(shù)，節(jié)省了網(wǎng)絡(luò)資源。

本文組織結(jié)構(gòu)如下：第2章對當(dāng)前的信息輔助型機(jī)會路由算法進(jìn)行了回顧；第3章描述了層次化輔助信息的獲取機(jī)制；第4章討論了如何將提出的輔助信息獲取機(jī)制集成到經(jīng)典的路由算法PRoPHET的過程；第5章進(jìn)行實驗分析；最后對全文進(jìn)行總結(jié)。

2 相關(guān)工作

利用一些額外的信息協(xié)助節(jié)點進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)決策是當(dāng)前機(jī)會網(wǎng)絡(luò)路由算法研究的重點之一。常用的信息主要包括數(shù)據(jù)包屬性、節(jié)點信息、拓?fù)湫畔⒁约吧鲜鲂畔⒌娜诤系?類[2]。

基于數(shù)據(jù)包屬性的路由算法主要指利用數(shù)據(jù)包的效用值、投遞優(yōu)先級、包存活時間（time to live，TTL）以及備份數(shù)目等輔助性信息來定制路由策略。如文獻(xiàn)[3]根據(jù)TTL、跳數(shù)、包的備份數(shù)量和大小等知識將節(jié)點攜帶的數(shù)據(jù)包進(jìn)行排序，并提出一種基于包存活時間的路由協(xié)議（TTL based routing，TBR），該協(xié)議根據(jù)排序結(jié)果管理節(jié)點緩沖區(qū)中數(shù)據(jù)包的轉(zhuǎn)發(fā)和刪除。文獻(xiàn)[4]提出了一種基于數(shù)據(jù)包時間敏感效用的路由協(xié)議（time-sensitive opportunistic utilitybased routing，TOUR），其中每一個包維護(hù)一個隨時間線性遞減的效用值，隨著數(shù)據(jù)包在節(jié)點間的不斷轉(zhuǎn)發(fā)，包的效用值會隨著包的投遞延時和代價的增大而逐漸遞減，當(dāng)效用值為0時包被丟棄。

基于節(jié)點信息的路由算法以節(jié)點屬性（運動模式、能量、鄰節(jié)點變化情況等）、節(jié)點社會性以及節(jié)點間接觸率為依據(jù)制定路由協(xié)議。在這方面，文獻(xiàn)[5]提出了經(jīng)典的利用接觸和傳輸記錄的概率路由算法（probabilistic routing protocol using history of encounters and transitivity，PRoPHET），其根據(jù)節(jié)點間的接觸概率進(jìn)行路由決策，當(dāng)兩個節(jié)點發(fā)生接觸時，它們的接觸概率相應(yīng)增加，而當(dāng)它們經(jīng)過一段時間沒有發(fā)生接觸時，接觸概率相應(yīng)下降。文獻(xiàn)[6]提出了一種結(jié)合噴霧-等待策略并考慮緩沖區(qū)管理的多備份概率路由（hybrid probabilistic routing scheme using multi-copies，HUM）。文獻(xiàn)[7]提出了利用直接接觸的節(jié)點和兩跳鄰居節(jié)點的歷史接觸信息計算接觸概率的改進(jìn)型概率路由（improved probabilistic routing algorithm，IPRA）。通過研究人類活動的社會性規(guī)律，文獻(xiàn)[8]提出了冒泡路由算法（BUBBLE），其根據(jù)社會性劃分節(jié)點的社會等級，并根據(jù)節(jié)點的社會等級和所處的社區(qū)來決定數(shù)據(jù)包的轉(zhuǎn)發(fā)。文獻(xiàn)[9]通過研究節(jié)點間的歷史性接觸信息、節(jié)點移動模式、節(jié)點的社會性，并受網(wǎng)頁排名算法（PageRank）[10]啟發(fā)，提出了人群排名路由算法（PeopleRank），其將機(jī)會網(wǎng)絡(luò)描繪為一個社交網(wǎng)絡(luò)圖，并通過計算節(jié)點間的社交關(guān)系來獲得節(jié)點的社會性并按其排序，最后根據(jù)節(jié)點的社會性高低進(jìn)行路由決策。文獻(xiàn)[11]利用鄰居節(jié)點的接觸信息，分布式地估計節(jié)點的中心度和相似度，并融合二者提出基于中心度與相似度的路由算法（routing based on betweenness centrality and similarity，SimBet）。當(dāng)兩個節(jié)點相遇時，需要交換各自鄰域知識，計算中心度和相似度，然后將數(shù)據(jù)包轉(zhuǎn)發(fā)給效用值較高的節(jié)點。

基于拓?fù)鋵傩缘穆酚伤惴ㄖ饕咐脵C(jī)會網(wǎng)絡(luò)的局部拓?fù)渥兓?、鏈路信息等制定路由決策。文獻(xiàn)[12]通過觀察發(fā)現(xiàn)，機(jī)會網(wǎng)絡(luò)中的一些節(jié)點在特定的時間段內(nèi)會形成一個暫時性的聯(lián)通子網(wǎng)，因而提出了瞬態(tài)社區(qū)結(jié)構(gòu)的概念。其表示在不同時間段內(nèi)，機(jī)會網(wǎng)絡(luò)中某些節(jié)點可以組成連通的社區(qū)，并且一個節(jié)點在不同的時刻可以屬于不同的社區(qū)。該概念有助于區(qū)分機(jī)會網(wǎng)絡(luò)的社區(qū)邊界，并在網(wǎng)絡(luò)中適當(dāng)?shù)姆秶鷥?nèi)評估節(jié)點的中心性。

信息融合策略是將上述方法的特點進(jìn)行結(jié)合的路由算法。文獻(xiàn)[13]提出了一種結(jié)合節(jié)點投遞概率與數(shù)據(jù)包優(yōu)先級的轉(zhuǎn)發(fā)策略。首先對節(jié)點之間的投遞概率進(jìn)行比較來決定是否轉(zhuǎn)發(fā)數(shù)據(jù)包，當(dāng)決定轉(zhuǎn)發(fā)時，優(yōu)先考慮存活時間較短的數(shù)據(jù)包。

上述類型的信息輔助型路由算法所關(guān)注的是數(shù)據(jù)包的轉(zhuǎn)發(fā)問題。然而對于節(jié)點間輔助信息如何有效地收集與獲取這一關(guān)鍵問題，尚無相關(guān)工作。本文則圍繞這一問題進(jìn)行討論，并提出層次化的輔助信息獲取機(jī)制。

3 層次化輔助信息獲取機(jī)制

3.1 節(jié)點間鄰居關(guān)系

輔助信息的高效共享依賴于節(jié)點之間的鄰居關(guān)系，但是與傳統(tǒng)強(qiáng)連通網(wǎng)絡(luò)中顯性的鄰居關(guān)系不同，移動機(jī)會網(wǎng)絡(luò)中，節(jié)點的接觸情況是時變的、復(fù)雜的。有的節(jié)點對頻繁接觸，有的偶爾接觸，有的接觸時間長，有的間隔時間長。節(jié)點之間更多時候呈現(xiàn)的是一種隱性的連接方式。針對這種隱性的連接方式，本文聯(lián)合節(jié)點接觸情況的穩(wěn)定性、規(guī)律性來判別節(jié)點的鄰居關(guān)系：如果一對節(jié)點在接觸時長和接觸時間間隔方面有較高的穩(wěn)定性和較好的規(guī)律性，則將它們定義為鄰居。通過識別節(jié)點的鄰居關(guān)系，一方面可以將機(jī)會網(wǎng)絡(luò)中具有緊密關(guān)系的節(jié)點對更清晰地刻畫出來，另一方面鄰居節(jié)點之間信息的傳播速度也更快。因此，在機(jī)會網(wǎng)絡(luò)中通過該方法確定鄰居關(guān)系，并通過鄰居關(guān)系來決定節(jié)點間信息是否進(jìn)行共享，可以在保證輔助信息更新速度較快的基礎(chǔ)上減少輔助信息的獲取次數(shù)。本文用到的主要術(shù)語見表1。

Table 1 Major used notations表1 本文主要術(shù)語

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

本文對機(jī)會網(wǎng)絡(luò)中節(jié)點間接觸的穩(wěn)定性描述為：在時間段內(nèi)，如果兩個節(jié)點的平均接觸時長大于或等于某個閾值，說明這兩個節(jié)點的接觸具有穩(wěn)定性。數(shù)學(xué)描述如下：對于時間段內(nèi)的機(jī)會網(wǎng)絡(luò)G(V)，任意節(jié)點a,b∈V并且a≠b。Ca,b表示a和b在時間段內(nèi)的接觸次數(shù)，SCa,b表示a和b在時間段內(nèi)接觸的總時長。a和b在時間段內(nèi)的單次平均接觸時長為ACa,b=SCa,b/Ca,b。a與其他節(jié)點的單次平均接觸時長之和的平均值為。若ACa,b≥ASCa，則a與b的接觸是穩(wěn)定的。

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

本文用信息熵來量化節(jié)點的接觸規(guī)律性。信息熵是用來描述一個概率事件有序化程度的度量，事件越是無序，其熵值越高，反之熵值越低。根據(jù)最大熵原理可知，如果某個隨機(jī)事件的概率分布是最平均的，也就是說該隨機(jī)事件的各種表現(xiàn)形式出現(xiàn)的概率是接近相等的，此時概率分布的信息熵最大。由于機(jī)會網(wǎng)絡(luò)中節(jié)點移動是隨機(jī)的，節(jié)點對之間的間隔時長出現(xiàn)的長短也是一個隨機(jī)事件。如果該隨機(jī)事件的信息熵越大，則節(jié)點對之間各間隔時長越趨于一致，說明節(jié)點對之間接觸越有規(guī)律。

設(shè)在時間段內(nèi)節(jié)點a和節(jié)點b有w次接觸間隔，QIal,b代表第l次接觸間隔的時長。a和b的接觸間隔時長的總和表示為SIa,b。第l次接觸間隔時長出現(xiàn)的概率用表示。根據(jù)信息熵的公式得，a和b的接觸間隔的信息熵為lgPRl a,b)。節(jié)點a與其他節(jié)點的接觸間隔信息熵之和的平均值為。由最大熵原理可知，當(dāng)節(jié)點對的接觸間隔時長信息熵越大，則代表節(jié)點對接觸間隔時長出現(xiàn)的概率越是趨于平均，節(jié)點對之間的接觸越有規(guī)律。本文定義：當(dāng)Ea,b≥AEa，則說明a和b的接觸是有規(guī)律的。

3.1.3 鄰居發(fā)現(xiàn)算法

鄰居發(fā)現(xiàn)算法主要是用于判斷機(jī)會網(wǎng)絡(luò)中的節(jié)點對是否相互為鄰居，如算法1所示。

算法1IdentifyNeighbor

輸入：機(jī)會網(wǎng)絡(luò)節(jié)點集合V，節(jié)點a,b∈V。

輸出：鄰居節(jié)點集合NE。

1.NE←?

2.for任意節(jié)點a∈Vdo

3.for任意節(jié)點b∈Vdo

4. 計算a與b在時間段內(nèi)的單次接觸平均時長ACa,b

5. 設(shè)w為a與b在時間段內(nèi)的接觸間隔次數(shù)

6. forl=1towdo

7. 計算第l次接觸間隔時長出現(xiàn)的概率

8. end for

9. 計算接觸間隔信息熵Ea,b

10.end for

11.計算a與其他節(jié)點的單次平均接觸時長之和的平均值A(chǔ)SCa

12.計算a與其他節(jié)點的接觸間隔信息熵之和的平均值A(chǔ)Ea

13.ifACa,b≥ASCa?Ea,b≥AEathen

14.NE=NE?(a,b)

15.end if

16.end for

17.returnNE

算法2～4行（進(jìn)入二層循環(huán)），對于任意節(jié)點a，計算它與任意節(jié)點b的平均接觸時長ACa,b。算法6～8行計算a和b的每一次接觸間隔時長出現(xiàn)的概率。算法9～10行計算a和b的接觸間隔時長的信息熵Ea,b，退出內(nèi)層循環(huán)。算法11～12行分別計算出a與其他節(jié)點在時間段內(nèi)平均接觸時長之和的平均值A(chǔ)SCa和接觸間隔時長信息熵之和的平均值A(chǔ)Ea。算法13～17行判斷是否ACa,b≥ASCa且Ea,b≥AEa，如滿足條件則a和b為鄰居并將該節(jié)點對加入鄰居關(guān)系集合NE中，算法最后退出循環(huán)并返回NE。

3.2 輔助信息選擇性移交

本文使用輔助信息的選擇性移交方法來減少信息的獲取次數(shù)，其核心思想如下：選取一部分節(jié)點作為社會性節(jié)點，而剩下的節(jié)點作為普通節(jié)點。當(dāng)需要進(jìn)行輔助信息共享的時候，社會性節(jié)點負(fù)責(zé)和其他節(jié)點進(jìn)行輔助信息的交換，而普通節(jié)點之間則不進(jìn)行信息交換。使用該方法，輔助信息的交換將主要發(fā)生在特殊節(jié)點與普通節(jié)點之間。這樣一來，理論上可以大量減少節(jié)點間輔助信息的獲取次數(shù)。本文將這種節(jié)點間有條件地選擇信息交換對象的方法稱為輔助信息的選擇性移交。

由文獻(xiàn)[9]可知，PeopleRank算法可以通過計算機(jī)會網(wǎng)絡(luò)中節(jié)點的社會性，并根據(jù)節(jié)點社會性的大小做出路由決策。該算法通過計算PeopleRank值來描述節(jié)點的社會性。通常具有較高社會性（People-Rank值）的節(jié)點與大部分節(jié)點具有較高的接觸可能性。圖1表示一個包含8個節(jié)點的小型機(jī)會網(wǎng)絡(luò)。

圖中節(jié)點u和v代表社會性節(jié)點（具有較高社會性的節(jié)點），而其他節(jié)點則代表普通節(jié)點，節(jié)點之間連接的虛線表示在某時間段內(nèi)它們具有較高的接觸可能性。從圖中可以看出，節(jié)點u與節(jié)點a、b、c具有較高的接觸可能性，而節(jié)點v則與節(jié)點d、e、f有較高的接觸可能性。如果將節(jié)點u、v設(shè)為一個社會性節(jié)點集合，那么在該時間段內(nèi)，該節(jié)點集合具有較大的幾率接觸到網(wǎng)絡(luò)中所有的節(jié)點。

Fig.1 Example of selective handover圖1 選擇性移交圖例

本文使用上述的社會性節(jié)點負(fù)責(zé)向其他節(jié)點進(jìn)行輔助信息的交換工作，而普通節(jié)點之間不進(jìn)行輔助信息交換而只和社會性節(jié)點進(jìn)行信息交換。如圖1所示，當(dāng)社會性節(jié)點u與普通節(jié)點a、b、c接觸時進(jìn)行輔助信息的交換，節(jié)點v與節(jié)點d、e、f同上。當(dāng)兩個社會性節(jié)點u和v相遇時也進(jìn)行信息交換。而兩個普通節(jié)點（如a和b），即使接觸也不進(jìn)行信息交換。這樣一來，可以在減少節(jié)點間信息交換次數(shù)的基礎(chǔ)上，保證輔助信息的網(wǎng)絡(luò)覆蓋率較高。

4 應(yīng)用

以下主要闡述的內(nèi)容是如何將所提出的輔助信息獲取機(jī)制集成到PRoPHET算法中。

4.1 PRoPHET算法簡介

PRoPHET算法以節(jié)點之間的接觸概率為輔助信息來為數(shù)據(jù)包選擇合適的下一跳節(jié)點。PRoPHET計算節(jié)點之間接觸概率主要包括三方面：平滑、衰退及傳遞。這里以3個節(jié)點a、b、c為例說明它們之間的信息交換過程。當(dāng)a接觸b時，其接觸概率平滑為：

其中，P(a,b)old表示a和b上一次接觸時計算的接觸概率；Pinit為節(jié)點間接觸概率的初值。

如果一段時間后兩節(jié)點沒有發(fā)生接觸，則它們的接觸概率衰退如下：

其中，γ為衰退因子；κ為上次接觸后經(jīng)歷的時間段。

如果a和b有接觸，同時b和c有接觸，而a和c無接觸，a也可以通過傳遞性（即a通過獲取b中存儲的b到c接觸概率）來計算a和c的接觸概率，公式如下：

其中，β為傳遞因子。

4.2 PRoPHET層次化輔助信息獲取機(jī)制應(yīng)用

由3.1節(jié)可知，PRoPHET算法的輔助信息交換主要發(fā)生在計算接觸概率的傳遞性過程中，因此應(yīng)用于PRoPHET算法的層次化輔助信息共享機(jī)制主要用來決定當(dāng)兩節(jié)點接觸時是否進(jìn)行接觸概率的傳遞。其一般過程如下：

首先根據(jù)PeopleRank算法計算出機(jī)會網(wǎng)絡(luò)中每個節(jié)點的社會性（PeopleRank值）。取固定值TH為區(qū)分節(jié)點社會性高低的閾值，PeopleRank值低于TH值的節(jié)點為普通節(jié)點，反之為社會性節(jié)點。本文對TH值的取值為：將所有節(jié)點按PeopleRank值從大到小排列，將TH值作為前10%的高社會性節(jié)點和剩下90%節(jié)點的PeopleRank值的分界值。接下來，對于任意節(jié)點a,b∈V，當(dāng)a和b接觸時，判斷a或b是否屬于社會性節(jié)點，或根據(jù)鄰居關(guān)系發(fā)現(xiàn)算法判斷是否a和b是鄰居。如果滿足上述任意條件，則計算接觸概率的傳遞性。應(yīng)用層次化輔助信息收集機(jī)制的PRoPHET如算法2所示。

算法2PRoPHET（選擇性移交）

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

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

1.HC←?，EAI=0

2.for任意節(jié)點a∈Vdo

3.ifa的PeopleRank值＞THthen

4.HCi+1←HCi?a

5.end if

6.end for

7.for任意節(jié)點a∈Vdo

8. for任意節(jié)點b∈Vdo

9. ifa與b接觸 then

10. 通過式（1）計算a與b的接觸概率平滑性

11. if(a,b)∈NE?a∈HC?b∈HCthen

12.a獲取b到其他節(jié)點的接觸概率

13.a根據(jù)從b獲取到的接觸概率并通過式(3)計算接觸概率的傳遞性

14.EAI++

15. end if

16. end if

17. end for

18.end for

19.returnEAI

算法2～6行將社會性節(jié)點加入集合HC中。算法7～10行進(jìn)入二層循環(huán)，首先判斷任意節(jié)點a是否與任意節(jié)點b接觸，如果是則根據(jù)式（1）計算接觸概率平滑性。算法11～14行判斷a與b是否為鄰居或者a或b是否為社會性節(jié)點，如果滿足則a獲取b對于其他節(jié)點的接觸概率，然后根據(jù)式（3）計算接觸概率的傳遞性，并記錄一次輔助信息的獲取次數(shù)。算法15～19行退出所有循環(huán)并返回輔助信息獲取次數(shù)。

5 實驗結(jié)果

本文對提出的輔助信息收集策略在Visual C++平臺上進(jìn)行了集成，并結(jié)合PRoPHET算法進(jìn)行性能分析。實驗場景如下：節(jié)點間最大通信距離為25 m，每隔30 s作為一個時間段，仿真時間為15 000 s。采用的數(shù)據(jù)集為RealTrace-KAIST，該數(shù)據(jù)集來源于韓國科學(xué)技術(shù)院（Korea Advanced Institute of Science and Technology，KAIST），其記錄了大學(xué)校園內(nèi)人群的日?；顒有袨檐壽E。共有34人參與到數(shù)據(jù)的收集過程，每人手持GPS定位系統(tǒng)收集其92天的日常移動軌跡，關(guān)于該數(shù)據(jù)集的具體細(xì)節(jié)可以在文獻(xiàn)[14]中查閱。本文使用4個指標(biāo)來評價路由算法的性能：（1）投遞率，網(wǎng)絡(luò)中被成功接收的包的數(shù)量和產(chǎn)生的包的數(shù)量的比值，其代表了網(wǎng)絡(luò)中包可以被成功投遞到目的節(jié)點的比率。（2）包傳輸延時，網(wǎng)絡(luò)中所有到達(dá)目的地的包從產(chǎn)生到傳輸至目的節(jié)點所需的時間的平均值。（3）平均備份數(shù)，平均投遞一個包所需的備份個數(shù)，即所有的包產(chǎn)生的備份數(shù)與包的個數(shù)的比值。（4）輔助信息獲取次數(shù)，網(wǎng)絡(luò)中所有節(jié)點通過其他節(jié)點獲取輔助信息的總次數(shù)。

下面對使用層次化輔助信息收集機(jī)制的PRo-PHET（信息收集機(jī)制）與未使用信息收集機(jī)制的PRo-PHET（洪泛）的各項指標(biāo)性能實驗結(jié)果進(jìn)行詳細(xì)分析。從圖2中可以看出，在仿真時間第2 250 s到14 000 s時，信息收集機(jī)制略高于洪泛約0.03左右。而在14 000 s之后則略微低于洪泛約0.02左右。圖3展示了包傳輸延時方面的性能對比情況?？梢钥闯鲈诜抡鏁r間第2 250 s到第9 000 s期間，二者無明顯差異。而在第9 000 s到15 000 s期間，信息收集機(jī)制的延時逐漸降低，二者最大差距約300 ms（＜7%）。在數(shù)據(jù)包投遞備份數(shù)方面（圖4）相比于洪泛，信息收集機(jī)制略高，但總體控制在4個數(shù)據(jù)包左右（＜4%）。

Fig.2 Comparison of packet delivery ratio圖2 投遞率指標(biāo)對比

Fig.3 Comparison of packet transmission delay圖3 包傳輸延時指標(biāo)對比

對于輔助信息的獲取次數(shù)，從圖5中可以看出，從第2 250 s開始，信息收集機(jī)制就遠(yuǎn)遠(yuǎn)低于洪泛，并且隨著時間的推移，信息收集機(jī)制的輔助信息獲取次數(shù)的漲幅也遠(yuǎn)遠(yuǎn)低于洪泛，在仿真時間第15 000 s，洪泛的信息獲取次數(shù)在76萬次，而信息收集機(jī)制則僅有12萬次左右，增益約7倍左右。其原因正如上文分析的那樣，在信息收集機(jī)制中輔助信息只是由很少的一部分節(jié)點負(fù)責(zé)交換，而洪泛則是所有的節(jié)點都參與到交換工作，因此隨著時間的推移，二者在輔助信息獲取次數(shù)上的差距將會越來越明顯。

Fig.4 Comparison of packet delivery copies圖4 包投遞備份數(shù)指標(biāo)對比

Fig.5 Comparison of auxiliary-information acquisition times圖5 輔助信息獲取次數(shù)指標(biāo)對比

6 結(jié)束語

本文針對信息輔助型機(jī)會路由算法的洪泛式信息共享方式所造成的網(wǎng)絡(luò)資源浪費問題，提出了層次化的輔助信息獲取機(jī)制。首先通過分析機(jī)會網(wǎng)絡(luò)中節(jié)點間接觸的規(guī)律性和穩(wěn)定性提出了新的機(jī)會網(wǎng)絡(luò)鄰居關(guān)系發(fā)現(xiàn)算法。其次通過結(jié)合節(jié)點的社會性提出了輔助信息的選擇性移交機(jī)制。最后將二者有機(jī)地集成在經(jīng)典的信息輔助型機(jī)會路由算法PRo-PHET中，并通過實驗驗證了其有效性。未來將本文的信息獲取機(jī)制應(yīng)用到更多的機(jī)會路由算法中，以評估其通用性。

[1]Jindal A,Psounis K.Contention-aware analysis of routing schemes for mobile opportunistic networks[C]//Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking,San Juan,Jun 11,2007.New York:ACM,2007:1-8.

[2]Ma Huadong,Yuan Peiyan,Zhao Dong.Research progress on routing problem in mobile opportunistic networks[J].Journal of Software,2015,26(3):600-616.

[3]Prodhan A T,Das R,Kabir H,et al.TTL based routing in opportunistic networks[J].Journal of Network and Computer Applications,2011,34(5):1660-1670.

[4]Xiao Mingjun,Wu Jie,Liu Cong,et al.TOUR:time-sensitive opportunistic utility-based routing in delay tolerant networks[C]//Proceedings of the 32nd IEEE International Conference on Computer Communications,Turin,Apr 14-19,2013.Piscataway:IEEE,2013:2085-2091.

[5]Lindgren A,Doria A,Schelén O.Probabilistic routing in intermittently connected networks[J].Mobile Computing and Communications Review,2003,7(3):19-20.

[6]Li Ze,Shen Haiying.Probabilistic routing with multi-copies in delay tolerant networks[C]//Proceedings of the 28th IEEE International Conference on Distributed Computing Systems Workshops,Beijing,Jun 17-20,2008.Washington:IEEE Computer Society,2008:471-476.

[7]Wang Xu,He Rongxi,Lin Bin,et al.Probabilistic routing based on two-hop information in delay/disruption tolerant networks[J].Journal of Electrical and Computer Engineering,2015,3:1-11.

[8]Hui Pan,Crowcroft J,Yoneki E.BUBBLE Rap:social-based forwarding in delay-tolerant networks[J].IEEE Transactions on Mobile Computing,2011,10(11):1576-1589.

[9]Mtibaa A,May M,Diot C,et al.PeopleRank:social opportunistic forwarding[C]//Proceedings of the 29th IEEE International Conference on Computer Communications,Joint Conference of the IEEE Computer and Communications Societies,San Diego,Mar 15-19,2010.Piscataway:IEEE,2010:111-115.

[10]Brin S,Page L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks&ISDN Systems,1998,30(1/7):107-117.

[11]Daly E M,Haahr M.Social network analysis for routing in disconnected delay-tolerant MANETs[C]//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing,Montreal,Sep 9-14,2007.New York:ACM,2007:32-40.

[12]Gao Wei,Cao Guohong,Porta T L,et al.On exploiting transient social contact patterns for data forwarding in delaytolerant networks[J].IEEE Transactions on Mobile Computing,2013,12(1):151-165.

[13]Burgess J,Gallagher B,Jensen D,et al.MaxProp:routing for vehicle-based disruption-tolerant networks[C]//Proceedings of the 25th IEEE International Conference on Computer Communications,Barcelona,Apr 23-29,2006.Piscataway:IEEE,2006:1-11.

[14]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.

附中文參考文獻(xiàn)：

[2]馬華東,袁培燕,趙東.移動機(jī)會網(wǎng)絡(luò)路由問題研究進(jìn)展[J].軟件學(xué)報,2015,26(3):600-616.