機(jī)會(huì)網(wǎng)絡(luò)中考慮緩存的ProPhet路由算法

張 峰，王小明，張珊珊

（陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安710119）

0 引 言

如何充分利用設(shè)備的通信功能，在不需要進(jìn)行預(yù)先部署和建設(shè)基礎(chǔ)設(shè)施的情況下，快速完成這些不同設(shè)備之間的自動(dòng)組網(wǎng)，達(dá)到網(wǎng)內(nèi)信息傳遞以及信息共享的目的，成為當(dāng)前無線自組織網(wǎng)絡(luò)領(lǐng)域內(nèi)的熱點(diǎn)問題。另外，在救災(zāi)區(qū)域等場(chǎng)合，經(jīng)常會(huì)面臨無可靠的預(yù)先部署的基礎(chǔ)通訊設(shè)施的情況，如何在這些場(chǎng)合下進(jìn)行有效地通信是目前急待解決的一個(gè)問題。為了有效地解決上述問題，研究人員結(jié)合－（delay－tolerant network，DTN）網(wǎng)絡(luò)和MANET－（mobile ad hoc network）的特點(diǎn)，提出機(jī)會(huì)網(wǎng)絡(luò)－（opportunistic networks）的概念［1，2］。機(jī)會(huì)網(wǎng)絡(luò)的目標(biāo)是解決實(shí)際自組織網(wǎng)絡(luò)中由于網(wǎng)絡(luò)無法保持長(zhǎng)時(shí)間連通的情況下的數(shù)據(jù)通信問題，可在無線鏈路頻繁斷開和網(wǎng)絡(luò)分裂情況下完成通信任務(wù)，實(shí)現(xiàn)消息的逐跳轉(zhuǎn)發(fā)，并最終傳送到目的節(jié)點(diǎn)［3，4］。機(jī)會(huì)網(wǎng)絡(luò)中的相遇概念是指節(jié)點(diǎn)之間具備可以進(jìn)行通信的條件，這樣的條件由于節(jié)點(diǎn)的移動(dòng)而導(dǎo)致存在不確定性。某一時(shí)刻，在節(jié)點(diǎn)之間的距離小于彼此的通信范圍時(shí)發(fā)生通信；下一時(shí)刻隨著節(jié)點(diǎn)的移動(dòng)，節(jié)點(diǎn)之間的距離可能大于彼此的通信范圍，則通信隨即中斷。由于機(jī)會(huì)網(wǎng)絡(luò)在數(shù)據(jù)的傳輸過程中，不需要存在穩(wěn)定的一條或者多條源端到目的端的路徑，因此具有更強(qiáng)的環(huán)境適應(yīng)性。

1 相關(guān)工作

由于機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)性，網(wǎng)絡(luò)中節(jié)點(diǎn)之間的無線連接大部分時(shí)候是暫時(shí)，而且節(jié)點(diǎn)的相遇不可以預(yù)測(cè)。因此，假定消息傳遞過程中源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間存在端到端連接的傳統(tǒng)路由協(xié)議不適應(yīng)這種場(chǎng)景。為了解決機(jī)會(huì)網(wǎng)絡(luò)中這種節(jié)點(diǎn)之間連接的不可靠和不可以預(yù)測(cè)情況下消息傳遞問題，一種新的路由方式存儲(chǔ)－攜帶－轉(zhuǎn)發(fā)應(yīng)運(yùn)而生［5］。

基本的機(jī)會(huì)網(wǎng)絡(luò)路由算法主要可分為基于復(fù)制的路由算法和基于轉(zhuǎn)發(fā)的路由算法兩大類。在復(fù)制副本的數(shù)量和轉(zhuǎn)發(fā)時(shí)機(jī)方面進(jìn)行不斷的改進(jìn)和優(yōu)化是目前機(jī)會(huì)路由算法最主要的發(fā)展方向。其中典型的基于復(fù)制的路由算法包括Epidemic［6］路由和ProPhet［7］路由。

Epidemic路由協(xié)議中，每個(gè)節(jié)點(diǎn)對(duì)本地的消息需要維護(hù)一個(gè)摘要矢量 （summary vector，SV），摘要矢量里包含節(jié)點(diǎn)的本地消息編號(hào)，網(wǎng)絡(luò)中的每個(gè)消息的編號(hào)都是唯一的。節(jié)點(diǎn)在移動(dòng)過程中和其它節(jié)點(diǎn)相遇時(shí)，首先交換各自的摘要矢量SV，然后根據(jù)對(duì)端SV 里消息編號(hào)判斷本地沒有包含但對(duì)端節(jié)點(diǎn)包含的消息，并請(qǐng)求對(duì)方發(fā)送自己沒有的消息，并完成節(jié)點(diǎn)維護(hù)SV 的更新。隨著網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)，最終每個(gè)節(jié)點(diǎn)都會(huì)緩存網(wǎng)絡(luò)中沒有到達(dá)目的節(jié)點(diǎn)的所有消息。

在Epidemic路由算法中，不需要任何的節(jié)點(diǎn)信息，消息的轉(zhuǎn)發(fā)有一定的盲目性，網(wǎng)絡(luò)中會(huì)存儲(chǔ)著大量消息副本，消息傳遞的開銷比較大，但是卻提高了消息的傳遞率。為了降低Epidemic路由協(xié)議消息轉(zhuǎn)發(fā)的盲目性，Lindgren等人提出的一種基于概率的ProPhet路由協(xié)議。這種路由協(xié)議通過比較自身和相遇節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)概率大小來決定是否把消息投遞給其相遇的節(jié)點(diǎn)。節(jié)點(diǎn)a、b間鏈路概率大小按照下面的公式進(jìn)行更新

其中，Pinit是網(wǎng)絡(luò)預(yù)先設(shè)定的節(jié)點(diǎn)a 和b 之間的初始概率，γ∈ ［0，1］，稱為老化因子，k 是距離上次更新的單位時(shí)間數(shù)。

ProPhet中概率的更新還使用了概率的傳遞性，即節(jié)點(diǎn)a有可能遇到節(jié)點(diǎn)b，而b有可能遇到節(jié)點(diǎn)c，則a 可以為目標(biāo)節(jié)點(diǎn)為c 的消息轉(zhuǎn)發(fā)節(jié)點(diǎn)。節(jié)點(diǎn)a、b和c 間鏈路概率大小按照下面的公式進(jìn)行更新

其中，β∈ （0，1）是個(gè)常數(shù)，其值決定了經(jīng)過中間節(jié)點(diǎn)傳遞以后對(duì)總的成功傳輸概率影響的程度。

在Epidemic路由、概率路由等協(xié)議中，沒有考慮節(jié)點(diǎn)間接觸時(shí)間和中間轉(zhuǎn)發(fā)節(jié)點(diǎn)剩余緩存對(duì)數(shù)據(jù)包傳遞的影響，因此，具有一定的局限性和缺失性［8，9］。尤其是組移動(dòng)模型的情況下，這種移動(dòng)模型的特點(diǎn)是節(jié)點(diǎn)在一定范圍內(nèi)隨機(jī)移動(dòng)，節(jié)點(diǎn)的數(shù)量相對(duì)固定。例如實(shí)驗(yàn)室，體育館以及各種運(yùn)動(dòng)場(chǎng)所，學(xué)生宿舍等。這種情況下，節(jié)點(diǎn)之間的相遇持續(xù)時(shí)間會(huì)比較長(zhǎng)，而某些節(jié)點(diǎn)之間會(huì)頻繁接觸。如果節(jié)點(diǎn)間接觸比較頻繁，并且接觸以后節(jié)點(diǎn)之間連接持續(xù)時(shí)間比較長(zhǎng)，那么這些頻繁接觸的節(jié)點(diǎn)之間消息傳遞成功的可能性就比較大。并且節(jié)點(diǎn)的接觸頻率和接觸時(shí)間有傳遞性，為了提高機(jī)會(huì)網(wǎng)絡(luò)中數(shù)據(jù)傳遞的成功率，降低數(shù)據(jù)傳遞的延時(shí)，總是要把數(shù)據(jù)包傳遞給和目的節(jié)點(diǎn)頻繁接觸，并且接觸時(shí)間長(zhǎng)的中間節(jié)點(diǎn)。同時(shí)必須要考慮中間節(jié)點(diǎn)剩余緩存，避免中間節(jié)點(diǎn)由于緩存不足引起數(shù)據(jù)丟棄。

本文在研究傳統(tǒng)的ProPhet路由算法的前提下，結(jié)合考慮上述條件下節(jié)點(diǎn)移動(dòng)模型的特性，節(jié)點(diǎn)之間相遇持續(xù)時(shí)間特性以及節(jié)點(diǎn)間消息傳遞過程中中間節(jié)點(diǎn)剩余緩存的使用情況，提出一種考慮緩存的改進(jìn)的ProPhet路由算法－BAProphet（buffer aware ProPhet）。仿真結(jié)果表明，在給定的移動(dòng)模型下，該算法能夠有效提高消息傳遞成功率，降低網(wǎng)絡(luò)開銷，同時(shí)有效地減少消息的傳遞次數(shù)。

2 考慮緩存的ProPhet機(jī)會(huì)網(wǎng)絡(luò)路由

2.1 節(jié)點(diǎn)相遇持續(xù)時(shí)間

機(jī)會(huì)網(wǎng)絡(luò)路由算法在分析時(shí)經(jīng)常假設(shè)節(jié)點(diǎn)一旦相遇，消息就能夠成功轉(zhuǎn)發(fā)。但是當(dāng)節(jié)點(diǎn)間相遇的持續(xù)時(shí)間很短、鏈路帶寬較小或節(jié)點(diǎn)間需要交換的數(shù)據(jù)量較大時(shí)，消息傳輸過程中鏈路可能突然中斷，導(dǎo)致消息傳送失?。?0］。因此有必要考慮兩節(jié)點(diǎn)間通信鏈路持續(xù)時(shí)間的長(zhǎng)短，盡量將消息轉(zhuǎn)發(fā)給相遇持續(xù)時(shí)間更長(zhǎng)的節(jié)點(diǎn)，以免數(shù)據(jù)傳輸失敗。

節(jié)點(diǎn)相遇定義為：節(jié)點(diǎn)a 和節(jié)點(diǎn)b 的通信半徑分別Ra和Rb，當(dāng)節(jié)點(diǎn)a和節(jié)點(diǎn)b 進(jìn)入到彼此的通信范圍，即節(jié)點(diǎn)a和節(jié)點(diǎn)b 之間的距離小于Ra和Rb之間較小的值，其數(shù)學(xué)表達(dá)式為Dab＜MIN （Ra，Rb），如圖1所示。節(jié)點(diǎn)相遇的持續(xù)時(shí)間就是Dab的值小于MIN （Ra，Rb）之間的時(shí)間T［11］。

圖1 節(jié)點(diǎn)通信范圍

由于節(jié)點(diǎn)的移動(dòng)，兩個(gè)節(jié)點(diǎn)之間每次相遇的持續(xù)時(shí)間都可能不同，在本文中，需要分別統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)和其它任意節(jié)點(diǎn)之間的相遇持續(xù)時(shí)間。例如節(jié)點(diǎn)a 和節(jié)點(diǎn)b 第n 次相遇時(shí)，節(jié)點(diǎn)a 和節(jié)點(diǎn)b 的累積相遇持續(xù)時(shí)間Tab的計(jì)算公式為

2.2 節(jié)點(diǎn)緩存空閑比

機(jī)會(huì)網(wǎng)絡(luò)中的路由機(jī)制以 “存儲(chǔ)－攜帶－轉(zhuǎn)發(fā)”的模式工作。存儲(chǔ)和攜帶消息的個(gè)數(shù)與消息大小以及節(jié)點(diǎn)緩存大小密切相關(guān)，存儲(chǔ)和攜帶的消息越多，能夠通過該節(jié)點(diǎn)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)的消息可能性就越大。消息的大小是隨機(jī)產(chǎn)生的，一般不具有可預(yù)測(cè)性，但是網(wǎng)絡(luò)中節(jié)點(diǎn)的緩存大小一般是固定的［12］。

機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)一般都是便攜式的終端，其具有體積小、重量輕、移動(dòng)方便等特點(diǎn)，同時(shí)由于受限于體積和重量等因素，節(jié)點(diǎn)上用于緩存消息的空間有限。節(jié)點(diǎn)上的剩余緩存空間越大，對(duì)于經(jīng)過該節(jié)點(diǎn)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)的消息在緩存中存放的時(shí)間就越長(zhǎng)，轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)的概率也就越大。

在這里定義節(jié)點(diǎn)緩存的空閑比的計(jì)算公式如下所示

式中：mi——消息i的數(shù)量；Si——消息i的大小 （單位：MB）；Btotal——節(jié)點(diǎn)緩存的總數(shù) （單位：MB）。

2.3 路由算法描述

2.3.1 傳統(tǒng)ProPhet算法存在的不足

在已有的基于概率的機(jī)會(huì)網(wǎng)絡(luò)路由算法ProPhet中，每次兩個(gè)節(jié)點(diǎn)相遇，都通過式 （1）來更新彼此之間的傳遞概率。可以看出，兩個(gè)節(jié)點(diǎn)之間傳遞概率的大小只和相遇的次數(shù)以及固定的初始化值有關(guān)，體現(xiàn)不出機(jī)會(huì)網(wǎng)絡(luò)的中不同節(jié)點(diǎn)的不同特性。例如，兩個(gè)節(jié)點(diǎn)如果一直保持連接狀態(tài)，其投遞的概率不會(huì)發(fā)生變化，只和最初計(jì)算時(shí)的Pab以及Pinit有關(guān)。

另外，在兩個(gè)節(jié)點(diǎn)a 和b 連接的持續(xù)時(shí)間段內(nèi)，每次對(duì)數(shù)據(jù)轉(zhuǎn)發(fā)之前都不會(huì)對(duì)Pab進(jìn)行更新。但實(shí)際情況并非如此，極端的情況下，在節(jié)點(diǎn)a和b 處于連接狀態(tài)過程中時(shí)，有大量的數(shù)據(jù)需要發(fā)往同一目的的時(shí)候，由于Pab值的計(jì)算存在上述特點(diǎn)，所以該值在整個(gè)連接持續(xù)時(shí)間內(nèi)不會(huì)發(fā)生變化，都會(huì)通過某個(gè)固定的節(jié)點(diǎn)進(jìn)行投遞，或者中轉(zhuǎn)，沒有考慮這個(gè)特定節(jié)點(diǎn)的緩存使用情況。如果中間節(jié)點(diǎn)緩存不足時(shí)，由于Pab的值不會(huì)更新，通過算法計(jì)算出來的結(jié)果是把所有發(fā)往相同目的地的消息發(fā)到了同一個(gè)中間節(jié)點(diǎn)上。而中間節(jié)點(diǎn)由于緩存有限，勢(shì)必會(huì)將前面發(fā)來的未完成轉(zhuǎn)發(fā)的消息進(jìn)行老化，只能保留最近的發(fā)往目的地的節(jié)點(diǎn)消息；而同時(shí)緩存比較空閑的節(jié)點(diǎn)由于傳遞概率的值比較低，根據(jù)ProPhet路由算法的特性，不會(huì)成為這個(gè)特定消息的中間節(jié)點(diǎn)，這樣會(huì)造成節(jié)點(diǎn)資源的使用不均衡，緩存的浪費(fèi)，從而會(huì)影響到整個(gè)路由協(xié)議的傳輸成功率。

2.3.2 節(jié)點(diǎn)傳輸概率計(jì)算

在ProPhet路由算法中，當(dāng)節(jié)點(diǎn)a和b 相遇時(shí)，根據(jù)式（1）進(jìn)行更新。由式 （1）可以看出，兩個(gè)節(jié)點(diǎn)之間相遇概率只是和兩個(gè)節(jié)點(diǎn)的相遇次數(shù)以及初始設(shè)定的Pinit有關(guān)。Pinit為設(shè)定的固定值，不能完全體現(xiàn)節(jié)點(diǎn)相遇以后的傳輸概率，兩個(gè)相遇頻繁但是每次相遇持續(xù)時(shí)間都比較短的節(jié)點(diǎn)之間的傳輸概率通過式 （1）計(jì)算出來的結(jié)果一定會(huì)大于兩個(gè)相遇次數(shù)相對(duì)較少，但是相遇持續(xù)時(shí)間長(zhǎng)的節(jié)點(diǎn)。但是對(duì)于數(shù)據(jù)傳輸來說，相遇持續(xù)時(shí)間長(zhǎng)的節(jié)點(diǎn)一定會(huì)獲得比相遇頻繁更好的消息傳遞可靠性和成功率。

基于上述考慮，我們改進(jìn)了兩個(gè)節(jié)點(diǎn)之間的傳輸概率的計(jì)算公式，公式如下所示

Ttotal表示整個(gè)網(wǎng)絡(luò)從運(yùn)行開始到當(dāng)前節(jié)點(diǎn)a 和節(jié)點(diǎn)b相遇時(shí)的運(yùn)行時(shí)間。節(jié)點(diǎn)之間傳遞概率的老化以及概率的傳遞公式和ProPhet 保持一致，分別參見式 （2）和式 （3）。

2.3.3 路由算法設(shè)計(jì)

本文提出改進(jìn)的ProPhet路由算法—BAProPhet路由算法，其核心思想是在現(xiàn)有的ProPhet路由算法中，進(jìn)行節(jié)點(diǎn)間消息傳遞前，將中間轉(zhuǎn)發(fā)節(jié)點(diǎn)的消息緩沖占用比作為消息傳遞概率的因素，其算法步驟描述如下：

（1）節(jié)點(diǎn)a 和節(jié)點(diǎn)b 進(jìn)入彼此的通信范圍，兩個(gè)節(jié)點(diǎn)之間建立連接；

（2）節(jié)點(diǎn)a和節(jié)點(diǎn)b 交換彼此的SV 信息以及各自在本地保存的與其它節(jié)點(diǎn)的傳遞概率；

（3）根據(jù)式 （6）重新計(jì)算節(jié)點(diǎn)a 和節(jié)點(diǎn)b 之間的傳遞概率。并計(jì)算通過節(jié)點(diǎn)b可以到達(dá)的節(jié)點(diǎn)c 的傳遞概率；

（4）判斷節(jié)點(diǎn)a 緩存中的消息是否為空，若為空，則結(jié)束本次循環(huán)，若不為空，則進(jìn)入下一步；

（5）節(jié)點(diǎn)a上有發(fā)往節(jié)點(diǎn)d 的消息M 不存在于節(jié)點(diǎn)b的SV 里，節(jié)點(diǎn)a 根據(jù)首先獲取節(jié)點(diǎn)b 的當(dāng)前剩余緩存比Rfree，如果P （b，d）＊Rfree＞P （a，d），節(jié)點(diǎn)a 開始把消息發(fā)往節(jié)點(diǎn)b；

（6）轉(zhuǎn)到步驟 （4）。

該路由算法運(yùn)行的流程如圖2所示。

圖2 節(jié)點(diǎn)相遇消息處理流程

3 系統(tǒng)仿真及性能分析

3.1 仿真場(chǎng)景設(shè)置

本文以赫爾辛基理工大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室開發(fā)的ONE［13］（opportunistic network environment simulator）為仿真平臺(tái)進(jìn)行實(shí)驗(yàn)測(cè)試。ONE 是一款專門針對(duì)DTN 和機(jī)會(huì)網(wǎng)絡(luò)環(huán)境開發(fā)的仿真平臺(tái)，可較為理想地模擬出機(jī)會(huì)網(wǎng)絡(luò)在多種運(yùn)行環(huán)境下的參數(shù)。

在通常情況下，社區(qū)內(nèi)的或者團(tuán)體內(nèi)的移動(dòng)節(jié)點(diǎn)的移動(dòng)范圍都是固定，并且移動(dòng)范圍和移動(dòng)時(shí)間是有規(guī)律的。本文仿真的場(chǎng)景為固定時(shí)間內(nèi)小范圍內(nèi)的節(jié)點(diǎn)移動(dòng)情況下的消息傳遞，例如實(shí)驗(yàn)室、宿舍、圖書館以及體育館等，這些場(chǎng)景的特點(diǎn)是節(jié)點(diǎn)的移動(dòng)范圍較為固定，但是在范圍內(nèi)節(jié)點(diǎn)移動(dòng)的速度以及方向是隨機(jī)，所以采用組移動(dòng)模型來刻畫這類移動(dòng)場(chǎng)景。仿真過程各參數(shù)設(shè)置見表1。

表1 仿真場(chǎng)景設(shè)置

在上述場(chǎng)景下，使用本文提出的BAProPhet路由算法，在仿真時(shí)間為3600s時(shí)分別與經(jīng)典的基于泛洪的傳染路由Epidemic協(xié)議和基于節(jié)點(diǎn)相遇頻率轉(zhuǎn)發(fā)的ProPhet協(xié)議（ProPhet和BAProPhet算法中的老化間隔設(shè)為2s）從4個(gè)指標(biāo)進(jìn)行比較，這4個(gè)指標(biāo)分別為傳輸成功率、網(wǎng)絡(luò)開銷比、傳輸延遲和傳遞次數(shù)。

傳輸成功率：遞交成功的數(shù)據(jù)包數(shù)量 （Ndelivered）與總的投遞數(shù)據(jù)包數(shù)量 （Ncreated）的比值。傳輸成功率的計(jì)算公式為

網(wǎng)絡(luò)開銷比：指網(wǎng)絡(luò)中被中繼的數(shù)據(jù)包個(gè)數(shù) （Nrelayed）與成功遞交的數(shù)據(jù)包個(gè)數(shù) （Ndelivered）之差與成功遞交的數(shù)據(jù)包個(gè)數(shù) （Ndelivered）的比值。網(wǎng)絡(luò)開銷比率的計(jì)算公式為

傳輸延遲：端到端延遲就是一個(gè)數(shù)據(jù)包從源節(jié)點(diǎn)發(fā)送到首次有這個(gè)數(shù)據(jù)包的某個(gè)副本到達(dá)目的節(jié)點(diǎn)之間的時(shí)間間隔。

傳遞次數(shù)：在整個(gè)仿真時(shí)間內(nèi)，所有節(jié)點(diǎn)成功轉(zhuǎn)發(fā)消息的次數(shù)總和。由于節(jié)點(diǎn)能耗主要集中在消息的轉(zhuǎn)發(fā)上，因此傳遞次數(shù)是能耗的一種體現(xiàn)。

3.2 仿真結(jié)果與性能分析

本文以表1場(chǎng)景為基礎(chǔ)設(shè)計(jì)了多種場(chǎng)景，分別對(duì)Epidemic、ProPhet和BAProPhet這3種路由策略分別在節(jié)點(diǎn)個(gè)數(shù)變化時(shí)上述4個(gè)指標(biāo)性能的變化情況進(jìn)行了仿真。仿真結(jié)果如圖3～圖6所示。

圖3 消息遞交率與節(jié)點(diǎn)數(shù)之間的關(guān)系

從圖3可以看出，隨著節(jié)點(diǎn)數(shù)目的增加，傳統(tǒng)的Epidemic和ProPhet路由算法的消息遞交成功率在降低，這主要是由于節(jié)點(diǎn)數(shù)目越大，Epidemic以及ProPhet路由算法導(dǎo)致機(jī)會(huì)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)之間的接觸的機(jī)會(huì)越多，從而導(dǎo)致消息在網(wǎng)絡(luò)內(nèi)傳播的次數(shù)增加。由于節(jié)點(diǎn)的緩存有限，當(dāng)緩存滿了以后，會(huì)將消息丟棄從而降低了消息的遞交率。而BAProPhet充分考慮了中間節(jié)點(diǎn)的緩存使用情況，當(dāng)相遇節(jié)點(diǎn)的剩余緩存不足時(shí)，不會(huì)接收其它的節(jié)點(diǎn)的消息，因此能保證每個(gè)節(jié)點(diǎn)上緩存的消息盡可能的不被丟棄，在遇到目的節(jié)點(diǎn)時(shí)能夠成功的將消息傳遞到目的節(jié)點(diǎn)，提高網(wǎng)絡(luò)內(nèi)消息的遞交比例。

圖4 開銷比與節(jié)點(diǎn)數(shù)之間的對(duì)應(yīng)關(guān)系

從圖4可以看出，隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目的增加，傳統(tǒng)的Epidemic和ProPhet路由算法的開銷與節(jié)點(diǎn)數(shù)據(jù)之間的比例近似線性，但是BAProPhet路由算法的開銷一直保持一個(gè)較低的水平，基本不隨著網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)的增加而增加。這是由于Epidemic和ProPhet路由算法都是基于泛洪的路由算法。節(jié)點(diǎn)數(shù)目的增加同時(shí)伴隨著消息數(shù)量的增加。網(wǎng)絡(luò)中消息數(shù)量多了，所以泛洪的比例也就隨著消息個(gè)數(shù)的增加而增加。而BAProPhet在泛洪時(shí)優(yōu)先考慮了節(jié)點(diǎn)的緩存情況，盡量避免將消息復(fù)制到緩存使用率高的相遇節(jié)點(diǎn)，除非消息的目的節(jié)點(diǎn)和該中間轉(zhuǎn)發(fā)節(jié)點(diǎn)之間的傳輸概率相對(duì)較高，從而有效降低了算法的開銷。

圖5 平均端到端延時(shí)與節(jié)點(diǎn)數(shù)之間的對(duì)應(yīng)關(guān)系

從圖5可以看出，BAProphet路由算法的消息傳遞平均延時(shí)略大于Epidemic和Prophet路由算法，這主要是由于以下兩個(gè)方面的原因引起的：首先是由于BAProphet路由算法在網(wǎng)絡(luò)中攜帶消息副本的節(jié)點(diǎn)比較少，和目的節(jié)點(diǎn)相遇的機(jī)會(huì)降低，所以轉(zhuǎn)發(fā)消息的延時(shí)就會(huì)比其它兩個(gè)基于泛洪的路由協(xié)議要大一些；其次是由于BAProphet路由算法在消息傳遞過程中，考慮了中間節(jié)點(diǎn)的緩存情況，在中間節(jié)點(diǎn)上剩余緩存不太充足的情況下，會(huì)將消息在本地節(jié)點(diǎn)上繼續(xù)存儲(chǔ)，等待更合適的轉(zhuǎn)發(fā)機(jī)會(huì)，從而增加了消息轉(zhuǎn)發(fā)的延時(shí)。

圖6 傳遞次數(shù)與節(jié)點(diǎn)數(shù)之間的對(duì)應(yīng)關(guān)系

從圖6可以看出，對(duì)于這3種協(xié)議中，在到達(dá)各自消息傳遞目標(biāo)的情況下，Epidemic和Prophet路由算法的消息傳遞次數(shù)隨著節(jié)點(diǎn)的增加而顯著提升。這是由于這兩種路由算法是基于泛洪的機(jī)制的，網(wǎng)絡(luò)中節(jié)點(diǎn)越多，其相遇的節(jié)點(diǎn)個(gè)數(shù)以及產(chǎn)生的消息也就越多，所以消息轉(zhuǎn)發(fā)和傳遞的次數(shù)也就越多。而BAProPhet中消息的傳遞次數(shù)在網(wǎng)絡(luò)節(jié)點(diǎn)增加的情況下，和其余兩種路由算法相比只有輕微的增長(zhǎng)，這是由于該路由算法在進(jìn)行數(shù)據(jù)傳遞之前進(jìn)行相遇概率計(jì)算的時(shí)，考慮了相遇持續(xù)時(shí)間的因素。這樣，消息傳遞的中間節(jié)點(diǎn)一定是和目標(biāo)節(jié)點(diǎn)相遇次數(shù)多，并且相遇持續(xù)時(shí)間比較長(zhǎng)的節(jié)點(diǎn)。將消息復(fù)制到這樣的中間節(jié)點(diǎn)，一定會(huì)獲得比當(dāng)前攜帶消息的節(jié)點(diǎn)更好的傳輸成功率，減少消息復(fù)制的盲目性，從而有效的降低了消息傳遞的次數(shù)，減少了消息在不同節(jié)點(diǎn)之間互相洪泛而引起節(jié)點(diǎn)能量的不必要消耗。

4 結(jié)束語(yǔ)

本文分析了目前機(jī)會(huì)網(wǎng)絡(luò)中主流的基于泛洪的Epidemic和Prophet路由協(xié)議的特點(diǎn)以及不足。針對(duì)目前機(jī)會(huì)網(wǎng)絡(luò)中一種典型的社區(qū)移動(dòng)模型應(yīng)用場(chǎng)景中節(jié)點(diǎn)在某個(gè)范圍內(nèi)移動(dòng)的特點(diǎn)，根據(jù)相遇節(jié)點(diǎn)的相遇持續(xù)時(shí)間對(duì)消息的轉(zhuǎn)發(fā)概率進(jìn)行更新，并且在比較消息轉(zhuǎn)發(fā)概率時(shí)充分考慮中間節(jié)點(diǎn)剩余緩沖的情況，提出一種考慮緩存的BAProPhet路由算法。仿真結(jié)果表明，在相同環(huán)境下，該算法相比現(xiàn)有的Prophet以及Epidemic路由算法具有更高的消息傳遞成功率、更低的路由開銷以及更少的消息傳遞次數(shù)。雖然該算法的消息傳遞延時(shí)相比ProPhet和Epidemic算法略有增加，但是在網(wǎng)頁(yè)瀏覽，文件下載等消息傳遞延時(shí)要求不苛刻的數(shù)據(jù)業(yè)務(wù)中，這一點(diǎn)對(duì)于用戶的使用并無明顯的影響。因此，本文所提出的BAProPhet算法在非實(shí)時(shí)性的多節(jié)點(diǎn)數(shù)據(jù)傳輸場(chǎng)合具有良好的應(yīng)用前景。

［1］Davies E.DTN－the state of the art［EB／OL］.http：／／www.n4c.eu／Download／n4c－wp2－012－state－of－the－art－101.pdf，2009.

［2］Puneet Kumar Bhardwaj，Shipra Sharma，Vandana Dubey.Comparative analysis of reactive and proactive protocol of mobile ad－h(huán)oc network ［J］.International Journal on Computer Science and Engineering，2012，4 （7）：1281－1288.

［3］Hsu CJ，Liu HI，Seah WKG.Opportunistic routing－a review and the challenges ahead ［J］.Computer Networks，2011，55（15）：3592－3603.

［4］Mota VFS，Cunha FD，Macedo DF，et al.Protocols，mobility models and tools in opportunistic networks：A survey ［J］.Computer Communications，2014，48：5－19.

［5］XIONG Yongping，SUN Limin，NIU Jianwei，et al.Opportunistic networks［J］.Journal of Software，2009，20 （1）：124－137 （in Chinese）.［熊永平，孫利民，牛建偉，等.機(jī)會(huì)網(wǎng)絡(luò) ［J］.軟件學(xué)報(bào)，2009，20 （1）：124－137.］

［6］Li Yong，Wang Zhaocheng，Jin Depeng，et al.Optimal Beaconing control for epidemic routing in delay－tolerant networks［J］.IEEE Transactions on Vehicular Technology，2012，61（1）：311－320.

［7］Huang Tingkai，Lee Chiakeng，Chen Lingjyh.PRoPHET＋：An adaptive PRoPHET－based routing protocol for opportunistic network ［C］／／24th IEEE International Conference on Advanced Information Networking and Applications，2010：112－119.

［8］REN Zhi，HUANG Yong，CHEN Qianbin.Routing protocols for opportunistic networks ［J］.Journal of Computer Application，2010，30 （3）：723－728 （in Chinese）. ［任智，黃勇，陳前斌.機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議 ［J］，計(jì)算機(jī)應(yīng)用，2010，30（3）：723－728.］

［9］DUAN Pengrui，MA Huadong，LUO Hong.A gradient based routing algorithm for delay tolerant networks［J］.Journal of Beijing University of Posts and Telecommunications，2011，34 （2）：63－66（in Chinese）.［段鵬瑞，馬華東，羅紅.基于梯度的DTN路由算法［J］.北京郵電大學(xué)學(xué)報(bào)，2011，34 （2）：63－66.］

［10］Jouni Karvo，Jrg Ott.Time scales and delay－tolerant routing protocols［C］／／Proceedings of the Third ACM Workshop on Challenged Networks，2008：33－40.

［11］Pan Daru，Lin Mu，Chen Liangjie.Space－aware spray and transfer routing protocol for opportunistic networks［J］.Chinese Journal of Electronics，2013，22 （2）：363－358.

［12］Shen Jian，Zheng Wenying.An improvement of buffer scheme for delay tolerant networks［J］.International Journal of Future Generation Communication ＆Networking，2013，6（4）：263－271.

［13］Ari Keranen.Opportunistic network environment simulator［R］.Helsinki University of Technology Department of Communications and Networking Special Assignment，2008.