機(jī)會網(wǎng)絡(luò)中利用博弈論的可信路由協(xié)議

楊 震，趙 麗

(1.四川省裝備制造業(yè)機(jī)器人應(yīng)用技術(shù)工程實(shí)驗(yàn)室， 四川 德陽 618000；2.山西大學(xué) 軟件學(xué)院， 太原 030013)

在移動自組織網(wǎng)絡(luò)(mobile ad hoc network，MANET)[1]中，節(jié)點(diǎn)的移動性、網(wǎng)絡(luò)的劃分、鏈路的不穩(wěn)定性等都會影響網(wǎng)絡(luò)性能，而機(jī)會網(wǎng)絡(luò)(opportunistic network，OppNet)[2]的使用可以很好地解決上述問題。在OppNet中，由于不存在端到端的路徑，節(jié)點(diǎn)之間通過可伸縮移動性、聯(lián)系機(jī)會、節(jié)點(diǎn)協(xié)作以及存儲轉(zhuǎn)發(fā)機(jī)制，使得源或中間節(jié)點(diǎn)能夠?qū)⑺璧南⑥D(zhuǎn)發(fā)到目的地。為了應(yīng)對端到端路徑的缺失問題，OppNet有效地利用了現(xiàn)有的通信媒介，如WiFi、藍(lán)牙和蜂窩等技術(shù)實(shí)現(xiàn)相關(guān)節(jié)點(diǎn)之間的消息交換。在OppNet中，節(jié)點(diǎn)之間只有在通信范圍相同的情況下，或有機(jī)會互相接觸時(shí)，才能進(jìn)行通信和交換，否則節(jié)點(diǎn)的內(nèi)部機(jī)制將把消息存儲在緩沖區(qū)，直到出現(xiàn)進(jìn)一步的機(jī)會。以這種方式，所需的消息分組從一跳轉(zhuǎn)發(fā)到另一跳，并且最終更快地到達(dá)目的地。

在OppNet中由于缺乏對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的先驗(yàn)知識以及定位參與節(jié)點(diǎn)的不確定性，網(wǎng)絡(luò)安全性及路由選擇是一個非常大的挑戰(zhàn)。本文的目標(biāo)是為OppNet設(shè)計(jì)一個有效的路由協(xié)議。該協(xié)議中可有效用于優(yōu)化路由的可能信息包括：節(jié)點(diǎn)的移動性和方向、與目的節(jié)點(diǎn)的接觸次數(shù)，以及相對于特定目的地的距離。此外，本文還提出使用博弈論[3]模型用來設(shè)計(jì)協(xié)議。使用博弈論的原因是可以從模擬網(wǎng)絡(luò)中收集不同的案例研究，然后為沖突和合作情景制定一個優(yōu)化的數(shù)學(xué)模型。利用博弈論處理決策參數(shù)之間的沖突情況，以便從可用的參數(shù)中找出最合適的響應(yīng)策略。在本文中，節(jié)點(diǎn)的上下文信息被視為其戰(zhàn)略配置，在此基礎(chǔ)上構(gòu)建戰(zhàn)略博弈，實(shí)現(xiàn)信息上下文的穩(wěn)定組合，然后選擇獲得的策略將消息轉(zhuǎn)發(fā)到目的地方向的下一跳。

1 相關(guān)研究

目前，學(xué)者們設(shè)計(jì)出了很多用于OppNet的協(xié)議。文獻(xiàn)[4]提出了Prophet路由協(xié)議，在該協(xié)議中，如果一個節(jié)點(diǎn)過去遇到過另一個節(jié)點(diǎn)，或者曾經(jīng)多次訪問過一個位置，那么在不久的將來，它被認(rèn)為更有可能遇到同一個節(jié)點(diǎn)或訪問同一個位置。關(guān)于每個已知目的地的傳遞概率度量由源節(jié)點(diǎn)估計(jì)?；诖耍色@得節(jié)點(diǎn)向目的地成功傳送消息的傳送可預(yù)測性。文獻(xiàn)[5]提出了基于歷史的路由預(yù)測協(xié)議(HBPR)，該協(xié)議基于網(wǎng)絡(luò)中移動節(jié)點(diǎn)的歷史。HBPR的3個特征階段分別是：① 位置識別：在這個階段，假定節(jié)點(diǎn)的移動與人類移動模型相似。在某些地方，節(jié)點(diǎn)的移動非常頻繁，而在其他一些地方，節(jié)點(diǎn)的移動較少?？赏ㄟ^利用節(jié)點(diǎn)移動的歷史預(yù)測該節(jié)點(diǎn)的下一個位置；② 消息生成和歸屬位置更新：在這個階段為節(jié)點(diǎn)生成一組新的消息，然后記錄每個新生成消息的目的地ID；③ 下一跳選擇：為了識別下一跳，基于3個參數(shù)來考慮效用度量：節(jié)點(diǎn)移動的穩(wěn)定性、未來移動的預(yù)測以及相鄰節(jié)點(diǎn)距離源目的地的垂直距離。文獻(xiàn)[6]提出了PRoWait的路由協(xié)議，該協(xié)議使用一個簡單的轉(zhuǎn)發(fā)策略：當(dāng)兩個節(jié)點(diǎn)處于相同的通信范圍內(nèi)時(shí)，在數(shù)據(jù)傳輸過程中，具有較低傳送可預(yù)測性的節(jié)點(diǎn)與具有較高傳送可預(yù)測性的節(jié)點(diǎn)交換數(shù)據(jù)包。根據(jù)Prophet協(xié)議的規(guī)則計(jì)算節(jié)點(diǎn)的傳遞可預(yù)測性，并將其用于下一跳節(jié)點(diǎn)選擇，以減少資源消耗。文獻(xiàn)[7]提出一種數(shù)據(jù)發(fā)送策略，它根據(jù)節(jié)點(diǎn)的特征優(yōu)化路由，增強(qiáng)了數(shù)據(jù)傳輸性能。文獻(xiàn)[8]根據(jù)時(shí)間序列參數(shù)和傳輸過程參數(shù)評價(jià)節(jié)點(diǎn)的優(yōu)劣，以選擇合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)。文獻(xiàn)[9]提出了一種基于遺傳算法的能量有效路由協(xié)議(GARE)，利用遺傳算法(genetic algorithm，GA)[10]將消息從源路由傳遞到目的地。

文獻(xiàn)[11]提出了一種基于博弈論的路由協(xié)議(GTR)。它在有限的資源下將消息傳輸建模為多玩家Nash議價(jià)模型，并設(shè)計(jì)了一個效用函數(shù)。它決定了一個節(jié)點(diǎn)在傳遞概率方面的能力以及當(dāng)前的剩余資源。文獻(xiàn)[12]提出了一種消息轉(zhuǎn)發(fā)機(jī)制，即利用基于概率的路由方案刺激自選節(jié)點(diǎn)參與路由選擇。使用這種機(jī)制，每當(dāng)轉(zhuǎn)發(fā)源來自具有較低傳送概率的節(jié)點(diǎn)的分組時(shí)，具有較高傳送概率的節(jié)點(diǎn)就會被用來進(jìn)行補(bǔ)償。該協(xié)議被建模為一系列議價(jià)博弈，包括轉(zhuǎn)發(fā)算法和傳遞概率計(jì)算。文獻(xiàn)[13]提出了另一種基于博弈論的轉(zhuǎn)發(fā)機(jī)制，該機(jī)制考慮了節(jié)點(diǎn)的上下參數(shù)，利用卡爾曼濾波器對這些參數(shù)進(jìn)行預(yù)測，根據(jù)這些參數(shù)設(shè)計(jì)一個雙機(jī)非合作博弈，然后用這兩個參數(shù)來決定兩個節(jié)點(diǎn)之間的數(shù)據(jù)轉(zhuǎn)發(fā)。

以上協(xié)議大多數(shù)會因?yàn)榫W(wǎng)絡(luò)擁塞造成性能下降，因此需要更多的網(wǎng)絡(luò)資源。另外，就下一跳選擇而言，計(jì)算上下文信息需要額外的時(shí)間，并且在制定基于博弈論的傳播和基于上下文情景的解決方案時(shí)沒有考慮除能量和安全性之外的任何參數(shù)。本文提出一種機(jī)會網(wǎng)絡(luò)中基于博弈論的可信路由協(xié)議，從而以最小的延遲和開銷比傳遞消息。

2 本文協(xié)議

2.1 本文協(xié)議假設(shè)及相關(guān)術(shù)語定義

本文假定一個由N個移動節(jié)點(diǎn)組成的機(jī)會網(wǎng)絡(luò)場景，所有移動節(jié)點(diǎn)之間存在合作意識。另外，假定這些節(jié)點(diǎn)具有足夠的緩沖區(qū)來存儲它們各自的上下節(jié)點(diǎn)信息。一旦源或中間節(jié)點(diǎn)產(chǎn)生并廣播HELLO分組，每個節(jié)點(diǎn)就相對于相應(yīng)的目的地動態(tài)地計(jì)算它的相遇值和歐幾里德距離，這些數(shù)據(jù)被存儲在節(jié)點(diǎn)的緩沖區(qū)中。節(jié)點(diǎn)特定的上下文信息進(jìn)一步用于制定戰(zhàn)略博弈，以便從下一跳選擇中找到可用的最佳策略。在這里，戰(zhàn)略博弈被假定為一個有限的、合作的和非零合作博弈。最后，本文還假定參與消息轉(zhuǎn)發(fā)的每個節(jié)點(diǎn)都有足夠的能量，沒有惡意節(jié)點(diǎn)的行為。

本文相關(guān)術(shù)語定義如下：

1)G代表博弈。{S}、f(u)和z分別表示博弈的策略、實(shí)用功能和收益價(jià)值。

2) {N}和{M}分別表示網(wǎng)絡(luò)中的節(jié)點(diǎn)和源或中間節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。

3)K和L表示從{N}和{M}中選擇的一組節(jié)點(diǎn)。

4)P表示從{K}和{L}中選擇的節(jié)點(diǎn)集合。

5)σ表示相遇的閾值，ω表示距離的閾值，λ是相遇的常數(shù)值，μ是距離的常數(shù)值。

6) 相遇轉(zhuǎn)發(fā)參數(shù)：該參數(shù)用于根據(jù)相關(guān)節(jié)點(diǎn)和目的地之間相遇的次數(shù)選擇下一跳。α表示N個節(jié)點(diǎn)的相遇轉(zhuǎn)發(fā)參數(shù)；α1表示M中節(jié)點(diǎn)的相遇轉(zhuǎn)發(fā)參數(shù)。

7) 距離轉(zhuǎn)發(fā)參數(shù)：該參數(shù)用于根據(jù)相關(guān)節(jié)點(diǎn)和目的地之間的距離來選擇下一跳。β表示N個節(jié)點(diǎn)的距離轉(zhuǎn)發(fā)參數(shù)；β1表示M中節(jié)點(diǎn)的距離轉(zhuǎn)發(fā)參數(shù)。

8) 最佳轉(zhuǎn)發(fā)參數(shù)：該參數(shù)用于根據(jù)相遇和距離參數(shù)選擇下一個最佳跳躍。γ表示N個節(jié)點(diǎn)的最佳轉(zhuǎn)發(fā)參數(shù)；γ1表示M中節(jié)點(diǎn)的最佳轉(zhuǎn)發(fā)參數(shù)。

9) Sum Encounter和Sum Encounter1分別表示N中節(jié)點(diǎn)的相遇次數(shù)總和以及M中所有節(jié)點(diǎn)的相遇次數(shù)總和。

10) Sum Distance和Sum Distance1分別表示N中所有節(jié)點(diǎn)與目的節(jié)點(diǎn)的距離之和，以及M中所有節(jié)點(diǎn)與目的節(jié)點(diǎn)的距離之和。

11)T表示用于選擇集合K和L的閾值。

2.2 博弈模型

本文協(xié)議傾向于將博弈定義為一個元組G={N,S,U}，其中N是移動節(jié)點(diǎn)集合，S={Si}是可用策略集合，U={Ui}是同一個博弈的一組實(shí)用參數(shù)。設(shè)E是節(jié)點(diǎn)從源或中間節(jié)點(diǎn)相對于目的節(jié)點(diǎn)的相遇值，D為節(jié)點(diǎn)相對于同一目的地的歐幾里德距離，則S={E,D}為該博弈的策略配置集合。類似地，di, j是相鄰節(jié)點(diǎn)i相對于目的地j的歐幾里德距離，ei, j是相鄰節(jié)點(diǎn)i相對于目的地j的相遇值。在制定的戰(zhàn)略博弈中，博弈是在源節(jié)點(diǎn)或中間節(jié)點(diǎn)與鄰居節(jié)點(diǎn)i之間進(jìn)行的，i=1,2,3,…,m。 這里，鄰居節(jié)點(diǎn)是位于源節(jié)點(diǎn)或中間節(jié)點(diǎn)的通信范圍內(nèi)的節(jié)點(diǎn)。

根據(jù)制定的戰(zhàn)略博弈的結(jié)果，源或中間節(jié)點(diǎn)將選擇來自鄰居節(jié)點(diǎn)i的下一跳將消息轉(zhuǎn)發(fā)到其目的地。對于兩個合作者而言，制定的戰(zhàn)略博弈是一個非零和博弈，可根據(jù)納什均衡[14]導(dǎo)出結(jié)果。納什均衡的詳細(xì)推導(dǎo)和證明如下。

在博弈中，協(xié)議根據(jù)節(jié)點(diǎn)的相遇值E=(ei, j)和距離D=(di, j)來考慮4種可能的策略，這些策略如下：

1) 大的相遇值(eh)和大的距離值(dh)；

2) 大的相遇值(eh)和小的距離值(dl)；

3) 小的相遇值(el)和大的距離值(dh)；

4) 小的相遇值(el)和小的距離值(dl)。

在上述策略中，效用函數(shù)表述如下：

f(u)=ei, j×λ+di, j×μ

(1)

其中ei, j和di, j由下式給出：

(2)

(3)

其中：σ和ω是閾值；λ和μ是在效用函數(shù)的公式中分別考慮相遇值和距離的恒定值。類似地，基于這個效用函數(shù)，玩家/節(jié)點(diǎn)的收益值z計(jì)算如下：

zhh=eh+dh

(4)

zhl=eh+dl

(5)

zll=el+dh

(6)

zlh=el+dl

(7)

節(jié)點(diǎn)的收益矩陣如表1所示。同樣，如果z和Z分別是兩個移動節(jié)點(diǎn)/玩家的收益值，則其博弈收益矩陣表如表2所示。

表1 節(jié)點(diǎn)的收益矩陣

表2 博弈收益矩陣

2.3 最佳跳躍選擇

本文協(xié)議的主要目標(biāo)是基于α、β和γ從網(wǎng)絡(luò)中選擇消息的下一個最佳跳躍，該選擇過程包括：① 從網(wǎng)絡(luò)中選擇最佳轉(zhuǎn)發(fā)參數(shù)γ；② 從源節(jié)點(diǎn)的鄰居中選擇最佳轉(zhuǎn)發(fā)參數(shù)γ1。

2.3.1從網(wǎng)絡(luò)中選擇最佳轉(zhuǎn)發(fā)參數(shù)γ

希望傳達(dá)消息的源節(jié)點(diǎn)或中間節(jié)點(diǎn)首先向整個網(wǎng)絡(luò)廣播HELLO消息，假設(shè)N個節(jié)點(diǎn)在網(wǎng)絡(luò)中是可用的且可以接收到HELLO消息，同時(shí)這N個節(jié)點(diǎn)相對于目的地的相遇值是動態(tài)計(jì)算的。在這里，每個節(jié)點(diǎn)的相遇值顯示了過去與其他節(jié)點(diǎn)相遇的次數(shù)。這些相遇值的總和被存儲在名為SumEncounter的變量中。類似地，計(jì)算N個節(jié)點(diǎn)中的所有節(jié)點(diǎn)相對于目的地的歐幾里德距離，并且將它們的距離值的總和存儲在名為SumDistance的變量中。

為了選擇下一跳，針對N中的每個節(jié)點(diǎn)計(jì)算α。對于給定節(jié)點(diǎn)，α的值是其自身相遇值與所有對應(yīng)節(jié)點(diǎn)的相遇值的總和的比，即：

α=Node’s encounter/SumEncounter

(8)

類似地，針對N中的每個節(jié)點(diǎn)計(jì)算β。β的值是節(jié)點(diǎn)相對于目的地的歐幾里德距離與所有相應(yīng)節(jié)點(diǎn)相對于目的地的歐幾里德距離的總和的比，即

β=Node’s encounter/SumDistance

(9)

為了從N個節(jié)點(diǎn)中選擇下一個最好的轉(zhuǎn)發(fā)節(jié)點(diǎn)，本文協(xié)議需要使該節(jié)點(diǎn)與目的地節(jié)點(diǎn)間的相遇的次數(shù)最大化，并且使該節(jié)點(diǎn)與目的地節(jié)點(diǎn)間的距離最小化。網(wǎng)絡(luò)的γ計(jì)算如下：

γ=α/β

(10)

閾值T可以表示為N中所有節(jié)點(diǎn)的γ值的平均值，本文協(xié)議僅選擇γ≥T的節(jié)點(diǎn)集合。

2.3.2從源鄰居中選擇最佳轉(zhuǎn)發(fā)參數(shù)γ1

假設(shè)在給定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中一個節(jié)點(diǎn)有M個相鄰節(jié)點(diǎn)，這些相鄰節(jié)點(diǎn)能夠相互通信。這M個節(jié)點(diǎn)相對于目的地節(jié)點(diǎn)的相遇值是動態(tài)計(jì)算的，M個節(jié)點(diǎn)的相遇值的總和存儲在名為SumEncounter1的變量中。類似地，這M個節(jié)點(diǎn)相對于目的地節(jié)點(diǎn)的歐幾里德距離也是動態(tài)計(jì)算的，并且它們對應(yīng)的和存儲在名為SumDistance1的變量中。為了選擇下一跳，每個相鄰節(jié)點(diǎn)計(jì)算α1，α1的值表示如下：

α1=Node’s encounter/SunEncounter1

(11)

類似地，每個相鄰節(jié)點(diǎn)計(jì)算β1：

β1=Node’ distance/SumDistance1

(12)

為了從相鄰節(jié)點(diǎn)中為源/中間節(jié)點(diǎn)選擇下一個最好的轉(zhuǎn)發(fā)節(jié)點(diǎn)，本文協(xié)議需要最大化節(jié)點(diǎn)與目的地的相遇次數(shù)，并且最小化與目的地的歐幾里德距離。另外，協(xié)議對從源/中間的每個相鄰節(jié)點(diǎn)獲得的α1和β1值的均值進(jìn)行歸一化，并計(jì)算γ1：

γ1=α1/β1

(13)

源/中間節(jié)點(diǎn)的閾值T可以表示為對應(yīng)于相鄰節(jié)點(diǎn)的γ1值的平均值。所提出的協(xié)議從γ1值大于或等于T的相鄰節(jié)點(diǎn)集合中僅選擇一組L個節(jié)點(diǎn)。從該集合中最后選擇一組P個節(jié)點(diǎn)，源/中間節(jié)點(diǎn)將向其轉(zhuǎn)發(fā)消息，其中P=K∩L。

2.4 本文協(xié)議詳述

本文協(xié)議將整個網(wǎng)絡(luò)劃分為由N個節(jié)點(diǎn)組成的r個均勻區(qū)域，稱為k1,…,kr，r=1,2,…,p是不同邏輯劃分的區(qū)域，其中kr代表區(qū)域r。令nk,i為區(qū)域k中的一個節(jié)點(diǎn)，k=1,2,…,l;i=1,2,…,m。其中n1,1表示屬于區(qū)域1的節(jié)點(diǎn)1，n2,1表示屬于區(qū)域2的節(jié)點(diǎn)1，依此類推。在初始化步驟中，算法向網(wǎng)絡(luò)中的每個節(jié)點(diǎn)發(fā)送或者廣播HELLO分組報(bào)文。在收到HELLO報(bào)文后，每個節(jié)點(diǎn)計(jì)算其上下文信息，如歐幾里德距離、相遇值等。

假設(shè)Ek,n是屬于區(qū)域k的節(jié)點(diǎn)n相對于目的地的相遇值。相應(yīng)區(qū)域中所有節(jié)點(diǎn)的相遇值的總和計(jì)算如下：

(14)

其中k=1，n=1,2,…,p。為了計(jì)算屬于特定區(qū)域的特定節(jié)點(diǎn)的最佳計(jì)數(shù)值，本文協(xié)議計(jì)算節(jié)點(diǎn)與屬于該特定區(qū)域的所有節(jié)點(diǎn)的總相遇值的比值為

(15)

類似地，屬于網(wǎng)絡(luò)中的每個邏輯劃分區(qū)域的所有節(jié)點(diǎn)的相遇值SumEncounter的累積總和可表示為：

TE,N=TE,1+TE,2+…+TE,r

(16)

其中：TE,1和TE,2分別表示區(qū)域1和區(qū)域2中所有可用節(jié)點(diǎn)的相遇值的總和。

(17)

其中：E=1；k=1,2,…,r。本文協(xié)議通過將特定區(qū)域節(jié)點(diǎn)的相遇值與網(wǎng)絡(luò)中所有邏輯劃分區(qū)域的SumEncounter值的比率表示為一個新的參數(shù)：

(18)

由下式可得α的值：

(19)

類似的，假設(shè)Dk,n是屬于區(qū)域k的節(jié)點(diǎn)n相對于目的地的歐幾里德距離。相應(yīng)區(qū)域中所有節(jié)點(diǎn)的歐幾里德距離的總和計(jì)算如下：

(20)

其中：k=1；n=1,2,…,p。為了達(dá)到最優(yōu)化結(jié)果，本文協(xié)議計(jì)算一個節(jié)點(diǎn)與屬于該特定區(qū)域的所有節(jié)點(diǎn)的歐幾里德距離之和的比值，即

(21)

計(jì)算屬于網(wǎng)絡(luò)中每個邏輯分離區(qū)域的所有節(jié)點(diǎn)的SumDistance的值，即

(22)

其中：D=1；k=1,2,…,r。本文協(xié)議通過將區(qū)域內(nèi)節(jié)點(diǎn)的歐幾里德距離值與對應(yīng)于每個邏輯分區(qū)的所有可用節(jié)點(diǎn)的SumDistance值的比率表示為新的參數(shù)：

(23)

由下式可得β的值：

(24)

為了從網(wǎng)絡(luò)中可用的N個節(jié)點(diǎn)中選擇下一個最佳轉(zhuǎn)發(fā)節(jié)點(diǎn)，本文協(xié)議需要最大化節(jié)點(diǎn)與目的地的相遇次數(shù)，且最小化與預(yù)期相鄰節(jié)點(diǎn)的目的地的歐幾里德距離。將每個分割區(qū)域的所有節(jié)點(diǎn)獲得的α和β值的均值進(jìn)行歸一化，并從所有區(qū)域中計(jì)算γ：

(25)

考慮到前面討論的閾值T，確定滿足條件γ≥T的可用節(jié)點(diǎn)的集合K。這里，T值被認(rèn)為是所有節(jié)點(diǎn)的相遇值的最大值或所有節(jié)點(diǎn)的歐氏距離的最小值。

假設(shè)r是消息的源/中間節(jié)點(diǎn)所屬的區(qū)域之一，它由M個節(jié)點(diǎn)組成。以上述類似的方式計(jì)算α1、β1和γ1。

(26)

接下來，通過將閾值T與區(qū)域r中的相應(yīng)節(jié)點(diǎn)的所有γ1值進(jìn)行比較，本文協(xié)議找到集合L。在此基礎(chǔ)上，協(xié)議選擇最可能的最佳轉(zhuǎn)發(fā)者的集合{P}：

{P}={K}∩{L}

(27)

3 仿真結(jié)果和分析

使用機(jī)會網(wǎng)絡(luò)模擬器ONE[15]來評估提出協(xié)議的性能，并與Prophet協(xié)議、HBPR協(xié)議和PRoWait協(xié)議進(jìn)行比較。模擬區(qū)域呈矩形，其中節(jié)點(diǎn)的位置由笛卡兒x和y坐標(biāo)系表示。表3為仿真參數(shù)的值。

表3 仿真參數(shù)

1) 平均延遲

圖1～3顯示了TTL、節(jié)點(diǎn)數(shù)量和消息生成間隔對平均延遲的影響。在圖1中可以看到：在變化的TTL值下，本文協(xié)議的平均延遲約為2 513 s，而HBPR協(xié)議、PRoWait協(xié)議和Prophet 協(xié)議的平均延遲分別為3 318、3 165和3 228 s。本文協(xié)議的平均延遲時(shí)間小于其余3種協(xié)議，這是由于本文協(xié)議根據(jù)節(jié)點(diǎn)相對于目的地的相遇值和距離來適當(dāng)選擇下一個轉(zhuǎn)發(fā)節(jié)點(diǎn)。從圖2中可以看到：當(dāng)節(jié)點(diǎn)數(shù)量變化時(shí)，本文協(xié)議的平均延遲約為2 325 s，而HBPR協(xié)議、PRoWait協(xié)議和Prophet 協(xié)議的平均延遲分別為2 731、2 557和2 560 s。本文協(xié)議的平均延遲相對于其余3種協(xié)議分別降低了14.9%、9.1%和9.2%，性能較好。同樣地，在圖3中，當(dāng)消息生成間隔逐漸增加時(shí)，本文協(xié)議的平均延遲呈現(xiàn)下降的趨勢，且相對于其余3種協(xié)議而言，平均延遲最小。

圖1 TTL對平均延遲的影響

圖2 節(jié)點(diǎn)數(shù)量對平均延遲的影響

2) 丟棄的消息數(shù)

圖4～6顯示了TTL、節(jié)點(diǎn)數(shù)量和消息生成間隔對于丟棄的消息數(shù)量的影響。從圖4可以看出：在變化的TTL下，本文協(xié)議平均丟失消息數(shù)為91 041，HBPR協(xié)議、PRoWait協(xié)議和Prophet 協(xié)議的平均丟失消息數(shù)分別為111 440、108 362和104 110。本文協(xié)議平均丟失消息數(shù)相對于其余3種協(xié)議而言分別降低了18.3%、16.0%和12.6%。這主要是由于在本文協(xié)議中，當(dāng)消息轉(zhuǎn)發(fā)時(shí)，其首先保存在緩沖區(qū)中，當(dāng)找到下一個最佳跳躍時(shí)，才從緩沖區(qū)中讀取消息并轉(zhuǎn)發(fā)。從圖5中可以看到：當(dāng)節(jié)點(diǎn)數(shù)量變化時(shí)，本文協(xié)議的平均丟失消息數(shù)為152 661，HBPR協(xié)議為189 743，PRoWait協(xié)議為174 374，Prophet協(xié)議為156 082，本文協(xié)議優(yōu)于其余3種協(xié)議。從圖6可以看出：在消息生成間隔逐漸增加時(shí)，本文協(xié)議的平均丟失消息數(shù)為69 335，與Prophet協(xié)議相差不大，均優(yōu)于其余兩種協(xié)議。在本文協(xié)議中，當(dāng)消息生成間隔增加時(shí)，網(wǎng)絡(luò)中生成的消息數(shù)量減少，導(dǎo)致丟棄的消息數(shù)量減少。

圖4 TTL對丟棄的消息的影響

圖5 節(jié)點(diǎn)數(shù)量對丟棄的消息的影響

圖6 消息間隔對丟棄的消息的影響

3) 開銷比

圖7～9描述了TTL、節(jié)點(diǎn)數(shù)量和消息生成間隔對于消息開銷比的影響。在圖7中，可以觀察到當(dāng)TTL變化時(shí)，本文協(xié)議的平均開銷比為52.1，HBPR協(xié)議為70.1，PRoWait協(xié)議為58.2，Prophet協(xié)議為59.4。與HBPR協(xié)議、PRoWait協(xié)議和Prophet協(xié)議相比，本文協(xié)議的平均消息開銷比最低。這是由于本文協(xié)議使用節(jié)點(diǎn)的上下文信息向目的地傳送消息期間選擇下一個可能的最佳跳躍的方式。從圖8中可以看出：當(dāng)節(jié)點(diǎn)數(shù)量變化時(shí)，所有協(xié)議的消息開銷比也隨之增加，這是由于當(dāng)節(jié)點(diǎn)數(shù)量增加時(shí)，在網(wǎng)絡(luò)中生成和轉(zhuǎn)發(fā)的消息數(shù)量增加。在這種情況下，本文協(xié)議的開銷比小于其余協(xié)議。從圖9中可以看出：當(dāng)消息生成間隔時(shí)間增加時(shí)，4種協(xié)議的開銷比同樣逐漸增加。本文協(xié)議的平均開銷比為42.5，HBPR協(xié)議為71.4，PRoWait協(xié)議為51.6，Prophet為49.4，本文協(xié)議的開銷比小于其余3種協(xié)議，因?yàn)楸疚膮f(xié)議使用基于上下文的機(jī)制來進(jìn)行消息轉(zhuǎn)發(fā)。

圖7 TTL對開銷比的影響

圖8 節(jié)點(diǎn)數(shù)量對開銷比的影響

圖9 消息間隔對開銷比的影響

4 結(jié)束語

本文提出了一種新的機(jī)會網(wǎng)絡(luò)路由協(xié)議，它依賴于節(jié)點(diǎn)最重要屬性的標(biāo)識，即一個節(jié)點(diǎn)的相遇值以及該節(jié)點(diǎn)到目的地節(jié)點(diǎn)間的距離值。在該協(xié)議中，通過非零和合作博弈技術(shù)來確定給定節(jié)點(diǎn)的最佳消息轉(zhuǎn)發(fā)者的選擇。使用最佳響應(yīng)分析方法，本文提出的協(xié)議可以從其可用鄰居的集合中有效地識別和選擇給定節(jié)點(diǎn)的下一個最佳消息轉(zhuǎn)發(fā)器。仿真結(jié)果表明：在平均延遲、丟棄消息數(shù)和開銷比等方面，本文協(xié)議的性能均優(yōu)于Prophet、HBPR和PRoWait路由協(xié)議。