任智，索建偉，陳紅，徐中浩，陳前斌

(重慶郵電大學(xué) 移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

1 引言

機(jī)會(huì)網(wǎng)絡(luò)(opportunistic network)[1～4]是一種不需要在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整路徑、利用節(jié)點(diǎn)移動(dòng)帶來(lái)的相遇機(jī)會(huì)實(shí)現(xiàn)數(shù)據(jù)傳輸?shù)臅r(shí)延和分裂可容忍的自組織網(wǎng)絡(luò)。由于能夠在較為苛刻的環(huán)境下進(jìn)行通信，機(jī)會(huì)網(wǎng)絡(luò)已成為未來(lái)普適計(jì)算的重要組成部分和移動(dòng)ad hoc網(wǎng)絡(luò)（MANET, mobile ad-hoc network）的發(fā)展方向之一。

機(jī)會(huì)網(wǎng)絡(luò)拓?fù)渚哂械拈g斷或部分連接的特點(diǎn)，給路由算法的設(shè)計(jì)帶來(lái)一定挑戰(zhàn)。為了在機(jī)會(huì)網(wǎng)絡(luò)中端到端路徑不確保存在的條件下進(jìn)行路由，人們?cè)O(shè)計(jì)了多種路由算法[5～13]，其中研究與應(yīng)用較為廣泛的是基于 epidemic機(jī)制[14]的路由算法，它采用“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”（SCF, store-carry-forward）方式傳送數(shù)據(jù)，讓節(jié)點(diǎn)存儲(chǔ)收到的數(shù)據(jù)分組并攜帶它們運(yùn)動(dòng)，在運(yùn)動(dòng)中若與其他節(jié)點(diǎn)相遇，則將數(shù)據(jù)分組的副本轉(zhuǎn)發(fā)給相遇節(jié)點(diǎn)，直至數(shù)據(jù)分組到達(dá)目的節(jié)點(diǎn)。epidemic機(jī)制有助于降低分組時(shí)延和提高傳送成功率，但通過(guò)研究發(fā)現(xiàn)它在相遇節(jié)點(diǎn)感知耗時(shí)和數(shù)據(jù)分組交換開(kāi)銷方面存在冗余；因此，在前期研究[15]的基礎(chǔ)上，針對(duì)這個(gè)問(wèn)題提出一種基于相遇節(jié)點(diǎn)跨層感知的路由算法，通過(guò)采用物理層、MAC層和網(wǎng)絡(luò)層之間的跨層信息共享與協(xié)同等 5種新機(jī)制，減少控制開(kāi)銷，降低分組時(shí)延，節(jié)約機(jī)會(huì)網(wǎng)絡(luò)的帶寬和節(jié)點(diǎn)資源，提高路由算法的效率。

2 相關(guān)工作

關(guān)于機(jī)會(huì)網(wǎng)絡(luò)中基于 epidemic機(jī)制的路由算法，目前已有一些研究[9～13]。epidemic機(jī)制是由DEMERS等[14]提出的，主要用于網(wǎng)絡(luò)中不同節(jié)點(diǎn)的數(shù)據(jù)庫(kù)信息的管理與維護(hù)。VAHDAT等[9]根據(jù)機(jī)會(huì)網(wǎng)絡(luò)拓?fù)溟g斷和部分連接的特點(diǎn)改進(jìn)原有的epidemic機(jī)制，設(shè)計(jì)了epidemic routing(ER)路由算法，ER算法采用SCF方式和SV(summary vector)/數(shù)據(jù)分組交換機(jī)制，有利于數(shù)據(jù)在網(wǎng)絡(luò)中可靠傳輸，但它依靠internet MANET encapsulation protocol(IMEP)[16]實(shí)現(xiàn)相遇節(jié)點(diǎn)感知功能，難以及時(shí)發(fā)現(xiàn)相遇節(jié)點(diǎn)，而且數(shù)據(jù)交換過(guò)程也存在冗余操作。MATSUDA等[10]根據(jù)網(wǎng)絡(luò)狀態(tài)綜合使用 2-HOP算法[17]和epidemic機(jī)制，提出了(p,q)-epidemic routing算法，通過(guò)廣播已到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組信息（免疫信息）以刪除節(jié)點(diǎn)緩存中的冗余分組，節(jié)省了節(jié)點(diǎn)的存儲(chǔ)空間，但仍依靠IMEP協(xié)議感知相遇節(jié)點(diǎn)，數(shù)據(jù)分組交換也沿用了原有機(jī)制。TOWER等[11]提出的基于 epidemic機(jī)制的路由算法 ERHELLO使用周期性HELLO分組感知相遇節(jié)點(diǎn)，有利于降低相遇節(jié)點(diǎn)感知開(kāi)銷，但是仍未解決不能及時(shí)感知相遇節(jié)點(diǎn)的問(wèn)題。WANG等[12]提出了一種自適應(yīng)隨機(jī)化的 ER算法——ARER(adaptive randomized epidemic routing)，它根據(jù)式Wij=C1Ri(Ts)+C2pij+C3TTLij確定數(shù)據(jù)分組的轉(zhuǎn)發(fā)優(yōu)先級(jí)（其中，Ri(Ts)為副本密度，pij為轉(zhuǎn)發(fā)概率，TTLij為生存時(shí)間參數(shù)，C1、C2、C3是預(yù)設(shè)常數(shù)），用HELLO分組進(jìn)行相遇節(jié)點(diǎn)感知，但在HELLO分組中捎帶了免疫信息，可能導(dǎo)致節(jié)點(diǎn)相遇感知的通信開(kāi)銷增加。在前期研究中提出的基于分組索引增量交換的機(jī)會(huì)網(wǎng)絡(luò)路由算法[13]同樣只使用HELLO分組感知相遇節(jié)點(diǎn)，并設(shè)置了節(jié)點(diǎn)相遇時(shí)間間隔閾值，但當(dāng)時(shí)關(guān)注的焦點(diǎn)尚不是如何加快感知相遇節(jié)點(diǎn)。由上可知，現(xiàn)有基于epidemic機(jī)制的路由算法雖不斷演進(jìn)，但在加快相遇節(jié)點(diǎn)感知和減少數(shù)據(jù)分組交換開(kāi)銷方面仍存在不足：如根據(jù)實(shí)驗(yàn)數(shù)據(jù)，在常見(jiàn)的面積1 500 m×300 m、節(jié)點(diǎn)數(shù)50、節(jié)點(diǎn)移動(dòng)平均速率10 m/s的機(jī)會(huì)網(wǎng)絡(luò)環(huán)境中，當(dāng)節(jié)點(diǎn)通信范圍分別為10 m、25 m、50 m、75 m、100 m時(shí)，相遇節(jié)點(diǎn)感知平均耗時(shí)達(dá)到了1.6 s，控制開(kāi)銷在通信量中所占比重也一直在85%之上，因此，有進(jìn)一步改善的需要。

3 網(wǎng)絡(luò)模型與問(wèn)題描述

3.1 網(wǎng)絡(luò)模型

機(jī)會(huì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不同于傳統(tǒng)的多跳無(wú)線網(wǎng)絡(luò)，結(jié)合其特點(diǎn)，給出如下定義。

定義 1 （網(wǎng)絡(luò)模型）機(jī)會(huì)網(wǎng)絡(luò)的數(shù)學(xué)模型可表示為有向圖G=(V, E)；其中，節(jié)點(diǎn)集合V={v1,v2,…,vn}，n＞1，為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，vn表示網(wǎng)絡(luò)中第n個(gè)節(jié)點(diǎn)；鏈路集合 E=?∪{e1,e2,…,em}，1≤m≤n(n-1)，em表示網(wǎng)絡(luò)中第m條鏈路。

定義2 （機(jī)會(huì)網(wǎng)絡(luò)路由模型）用{ei,(tsi,tei)}，1≤i≤n(n-1)表示一條鏈路，tsi、tei分別表示該鏈路的生成和終止時(shí)間，且tei＞tsi。機(jī)會(huì)網(wǎng)絡(luò)路由的數(shù)學(xué)模型為：在機(jī)會(huì)網(wǎng)絡(luò)中，尋找至少一個(gè)在邏輯上有序相連的鏈路組合∑{ei,(tsi, tei)}，使該鏈路組合的首尾節(jié)點(diǎn)分別是數(shù)據(jù)分組的源和目的節(jié)點(diǎn)，且相鄰兩條鏈路中前一條鏈路的生成時(shí)間ts必須小于后一條鏈路的終止時(shí)間te，即tsi

定義3 （SV及SV分組）SV(summary vector)即“匯總矢量”，是一種二進(jìn)制的一維矢量，用于表示節(jié)點(diǎn)存有哪些數(shù)據(jù)分組。SV分組是一種含有匯總矢量的控制分組，節(jié)點(diǎn)在與其他節(jié)點(diǎn)相遇后，會(huì)將SV分組發(fā)送給相遇節(jié)點(diǎn)。

3.2 一些假設(shè)

假設(shè) 1 在足夠長(zhǎng)的網(wǎng)絡(luò)運(yùn)行時(shí)間內(nèi)，源和目的節(jié)點(diǎn)之間存在端到端的有序鏈路組合。

本文假設(shè)機(jī)會(huì)網(wǎng)絡(luò)的路由算法工作一段足夠長(zhǎng)的時(shí)間，在該時(shí)間內(nèi)任何源和目的節(jié)點(diǎn)之間存在有序的鏈路組合，這樣可以保證數(shù)據(jù)分組在正常情況下能夠被送達(dá)目的節(jié)點(diǎn)。

假設(shè) 2 機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)具有足夠的數(shù)據(jù)處理、存儲(chǔ)和轉(zhuǎn)發(fā)能力。

本文假設(shè)機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)具有足夠能力處理、存儲(chǔ)和轉(zhuǎn)發(fā)數(shù)據(jù)，系統(tǒng)性能的瓶頸主要存在于傳輸鏈路。這樣可以將研究焦點(diǎn)集中于完成數(shù)據(jù)傳輸功能的機(jī)會(huì)網(wǎng)絡(luò)路由算法上。

以上述假設(shè)為前提，在研究中發(fā)現(xiàn)現(xiàn)有基于epidemic機(jī)制的路由算法存在以下待改進(jìn)之處：

節(jié)點(diǎn)通過(guò)周期性發(fā)送HELLO分組來(lái)感知相遇節(jié)點(diǎn)，在感知時(shí)間上存在一定冗余。

節(jié)點(diǎn)將新產(chǎn)生的數(shù)據(jù)分組逐一交換給鄰居，存在通信冗余。

節(jié)點(diǎn)發(fā)送分組后，HELLO分組的發(fā)送計(jì)時(shí)起點(diǎn)沒(méi)有作相應(yīng)調(diào)整，有可能發(fā)送冗余的HELLO分組。

節(jié)點(diǎn)緩存中存在可以刪除的數(shù)據(jù)分組。

4 基于相遇節(jié)點(diǎn)跨層感知的高效低時(shí)延路由算法

為解決上節(jié)所述4個(gè)問(wèn)題，提出一種新的路由算法——ERCES（epidemic routing based on cross-layer encountered-node sensing），在其中為相遇節(jié)點(diǎn)感知和數(shù)據(jù)分組交換提出了5種已有類似算法所不具有的新機(jī)制，從而達(dá)到降低相遇節(jié)點(diǎn)感知時(shí)延和減少開(kāi)銷的效果。

4.1 ERCES算法包含的新機(jī)制

4.1.1 跨層感知相遇節(jié)點(diǎn)

當(dāng)節(jié)點(diǎn)的物理層偵聽(tīng)到其他節(jié)點(diǎn)發(fā)出的信號(hào)載波，立即通過(guò)跨層信息共享的方式向網(wǎng)絡(luò)層報(bào)告（可借鑒CSMA/CA機(jī)制中物理層向MAC層報(bào)告“偵聽(tīng)到載波”消息的方式，將MAC層接入算法實(shí)體換為網(wǎng)絡(luò)層路由算法實(shí)體來(lái)實(shí)現(xiàn)。如果同時(shí)遇到多個(gè)節(jié)點(diǎn)，物理層用同樣方式向網(wǎng)絡(luò)層跨層報(bào)告。為了降低硬件實(shí)現(xiàn)的復(fù)雜性和難度，可將MAC層作為聯(lián)系通道，在網(wǎng)絡(luò)層路由算法實(shí)體和 MAC層接入算法實(shí)體之間增加軟件接口，使接入算法實(shí)體能夠向路由算法實(shí)體發(fā)送中斷并且路由算法實(shí)體能夠調(diào)用接入算法的載波偵聽(tīng)開(kāi)關(guān)功能）。網(wǎng)絡(luò)層判斷節(jié)點(diǎn)相遇事件發(fā)生后，立即廣播一個(gè)SV分組，于是，相遇雙方進(jìn)入數(shù)據(jù)分組交換流程。這種新機(jī)制擬在解決節(jié)點(diǎn)不能及時(shí)感知相遇節(jié)點(diǎn)的問(wèn)題，有助于降低節(jié)點(diǎn)相遇感知延遲和數(shù)據(jù)分組傳輸時(shí)延。為避免對(duì)同一節(jié)點(diǎn)相遇事件的重復(fù)報(bào)告，物理層報(bào)告節(jié)點(diǎn)相遇之后網(wǎng)絡(luò)層就將該報(bào)告功能關(guān)閉，直到需要時(shí)再開(kāi)啟。

4.1.2 節(jié)點(diǎn)相遇后立即廣播新產(chǎn)生的數(shù)據(jù)分組

一個(gè)節(jié)點(diǎn)如果判斷出與其他節(jié)點(diǎn)相遇（條件{收到物理層跨層報(bào)告∪收到相遇節(jié)點(diǎn)發(fā)送的HELLO分組}成立），則立即廣播它在最近兩次節(jié)點(diǎn)相遇之間新產(chǎn)生的數(shù)據(jù)分組。這種新機(jī)制能夠解決節(jié)點(diǎn)與鄰居逐一交換新數(shù)據(jù)分組而產(chǎn)生冗余開(kāi)銷的問(wèn)題，從而減少數(shù)據(jù)分組的交互次數(shù)，降低數(shù)據(jù)分組的轉(zhuǎn)發(fā)開(kāi)銷和時(shí)延。

4.1.3 收到SV分組后優(yōu)先發(fā)送目的節(jié)點(diǎn)為對(duì)方的數(shù)據(jù)分組

若節(jié)點(diǎn)收到相遇節(jié)點(diǎn)的SV分組，會(huì)立即將目的節(jié)點(diǎn)為相遇節(jié)點(diǎn)的數(shù)據(jù)分組發(fā)送給對(duì)方，然后才發(fā)送Request分組。這種新機(jī)制擬在解決“先發(fā)送SV分組會(huì)影響數(shù)據(jù)分組時(shí)延和成功率”的問(wèn)題，有利于降低數(shù)據(jù)分組端到端時(shí)延和提高傳送成功率，而且能夠避免在收到SV分組之前發(fā)送數(shù)據(jù)分組引起的重復(fù)發(fā)送問(wèn)題。

4.1.4 動(dòng)態(tài)自適應(yīng)發(fā)送HELLO分組

在現(xiàn)有使用HELLO分組的路由算法中，每當(dāng)計(jì)時(shí)周期T到達(dá)時(shí)節(jié)點(diǎn)的網(wǎng)絡(luò)層會(huì)清零HELLO分組發(fā)送計(jì)時(shí)器并廣播HELLO分組；而在ERCES算法中，網(wǎng)絡(luò)層在收到MAC層發(fā)送幀的跨層信息后也會(huì)將HELLO分組發(fā)送計(jì)時(shí)器清零。這種結(jié)合跨層信息動(dòng)態(tài)調(diào)整發(fā)送計(jì)時(shí)起點(diǎn)的機(jī)制擬在解決發(fā)送不必要的HELLO分組的問(wèn)題，從而節(jié)約無(wú)線網(wǎng)絡(luò)帶寬和節(jié)點(diǎn)資源。

4.1.5 借助SV刪除節(jié)點(diǎn)緩存中已到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組

節(jié)點(diǎn)收到相遇節(jié)點(diǎn)的SV后，判斷是否有數(shù)據(jù)分組滿足條件{目的節(jié)點(diǎn)為相遇節(jié)點(diǎn)∩兩節(jié)點(diǎn)同時(shí)存有}，如果有，則將其從本節(jié)點(diǎn)的網(wǎng)絡(luò)層緩存中刪除。這種機(jī)制擬在解決不能及時(shí)清理已達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組的問(wèn)題，為節(jié)點(diǎn)節(jié)省存儲(chǔ)空間，而且不產(chǎn)生額外的通信開(kāi)銷。

4.2 算法操作

ERCES算法具體包含以下6個(gè)步驟。

1) 每個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)層在一跳范圍內(nèi)周期性廣播含有節(jié)點(diǎn)網(wǎng)絡(luò)地址的HELLO分組。

2) 節(jié)點(diǎn)的物理層進(jìn)行載波偵聽(tīng)；如果偵聽(tīng)到其他節(jié)點(diǎn)發(fā)出的載波，則立即通過(guò)跨層信息共享的方式報(bào)告網(wǎng)絡(luò)層，實(shí)現(xiàn)網(wǎng)絡(luò)層對(duì)相遇節(jié)點(diǎn)的跨層感知，然后關(guān)閉跨層報(bào)告功能。

3) 網(wǎng)絡(luò)層記錄物理層的跨層報(bào)告功能的開(kāi)關(guān)狀態(tài)，并且判斷條件{跨層報(bào)告功能狀態(tài)為“關(guān)”∩HELLO分組發(fā)送計(jì)時(shí)周期T到達(dá)}是否成立；若成立，則立即向物理層發(fā)送一個(gè)“開(kāi)”信息，啟動(dòng)物理層的跨層報(bào)告功能，同時(shí)向下層發(fā)送一個(gè)HELLO分組。

4) 一個(gè)節(jié)點(diǎn)感知到相遇節(jié)點(diǎn)后，立即廣播新產(chǎn)生的數(shù)據(jù)分組。若相遇節(jié)點(diǎn)是通過(guò)跨層方式感知到的，則在廣播新數(shù)據(jù)分組之后，立即產(chǎn)生一個(gè) SV分組并在一跳范圍內(nèi)廣播（以便通知未感知到的鄰居）；同時(shí)，MAC層在每發(fā)送完一幀（數(shù)據(jù)幀或控制幀）之后，都會(huì)立即跨層通知網(wǎng)絡(luò)層將 HELLO分組發(fā)送計(jì)時(shí)器的值清零以重新計(jì)時(shí)。

5) 若一個(gè)節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)發(fā)出的SV，則將滿足條件{目的節(jié)點(diǎn)為對(duì)方∩雙方共同緩存}的數(shù)據(jù)分組從自己的緩存中刪除；然后，發(fā)送目的節(jié)點(diǎn)為對(duì)方的數(shù)據(jù)分組；最后，通過(guò)Request分組將滿足{自己未存儲(chǔ)∩對(duì)方已存儲(chǔ)}條件的數(shù)據(jù)分組的信息發(fā)送給對(duì)方。

6) 若節(jié)點(diǎn)收到Request分組，則將請(qǐng)求發(fā)送的數(shù)據(jù)分組發(fā)送給對(duì)方；同時(shí)，將已到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組從緩存中刪除，但保存它們的索引信息以供更新其他節(jié)點(diǎn)的分組緩存。

4.3 相遇時(shí)間閾值計(jì)算

相遇時(shí)間閾值主要用于判斷節(jié)點(diǎn)相遇事件是再次相遇還是上次相遇的不間斷延續(xù)。

根據(jù)上述的分布函數(shù)可得概率密度函數(shù)f (x)為

因而可得節(jié)點(diǎn)B與A的平均距離，即圖2中的a為

根據(jù)圖2及余弦定理可得

圖2 節(jié)點(diǎn)相對(duì)運(yùn)動(dòng)示意

則 BB'的距離 R(θ)為

其中，θ 在[0, π]服從均勻分布（θ在[0, 2π]具有對(duì)稱性），則概率密度函數(shù)為

根據(jù)式（5）和式（6），則可得到節(jié)點(diǎn) B離開(kāi)節(jié)點(diǎn)A通信范圍的平均距離S()θ為

將式（8）代入式（7）中可得

則相遇時(shí)間閾值為

4.4 性能分析

4.4.1 相遇節(jié)點(diǎn)感知時(shí)間

關(guān)于 ERCES算法的相遇節(jié)點(diǎn)感知時(shí)間，有如下引理。

引理1 ERCES算法的相遇節(jié)點(diǎn)感知時(shí)間少于ER-HELLO算法。

證明 假設(shè)節(jié)點(diǎn)A、B發(fā)送HELLO分組的周期均為 T，發(fā)送開(kāi)始時(shí)刻分別為 t1、t2，t3、t4分別表示A、B發(fā)送非HELLO分組（如數(shù)據(jù)分組）的時(shí)刻，為具有一般性，設(shè)t1=0，t2＞0，節(jié)點(diǎn)相遇事件的發(fā)生概率為隨機(jī)均勻分布，任取一個(gè)周期的時(shí)序如圖3所示。

圖3 HELLO分組發(fā)送時(shí)序

根據(jù)圖3，可計(jì)算ER-HELLO感知相遇節(jié)點(diǎn)所需時(shí)間的數(shù)學(xué)期望為

經(jīng)過(guò)跨層協(xié)同設(shè)計(jì)后，節(jié)點(diǎn)感知相遇節(jié)點(diǎn)所需時(shí)間的數(shù)學(xué)期望為

對(duì)比式（11）與（12），有

即相遇節(jié)點(diǎn)感知時(shí)間被縮短。

證畢。

4.4.2 計(jì)算復(fù)雜度

設(shè)機(jī)會(huì)網(wǎng)絡(luò)的覆蓋面積為 S，節(jié)點(diǎn)數(shù)為 N，節(jié)點(diǎn)的通信半徑為r、平均運(yùn)動(dòng)速度為v，數(shù)據(jù)分組平均產(chǎn)生速率為 p，網(wǎng)絡(luò)運(yùn)行時(shí)間為 T。以下從時(shí)間復(fù)雜度、存儲(chǔ)復(fù)雜度和通信復(fù)雜度 3個(gè)方面推導(dǎo)ERCES算法的計(jì)算復(fù)雜度。

1）時(shí)間復(fù)雜度

由條件可知節(jié)點(diǎn)的度D為

一個(gè)數(shù)據(jù)分組在最極端的情況下需要經(jīng)過(guò)N-1次轉(zhuǎn)發(fā)才能到達(dá)目的節(jié)點(diǎn)，即需要與 N-1-D個(gè)節(jié)點(diǎn)相遇。假設(shè)節(jié)點(diǎn)在網(wǎng)絡(luò)中均勻分布，則節(jié)點(diǎn)間的平均距離為則節(jié)點(diǎn)在最極端情況下需運(yùn)動(dòng)的距離d為

消耗的時(shí)間t為

則時(shí)間復(fù)雜度Ct為

2) 存儲(chǔ)復(fù)雜度

節(jié)點(diǎn)在網(wǎng)絡(luò)運(yùn)行t之后存儲(chǔ)的數(shù)據(jù)分組與p、T、N等參數(shù)正相關(guān)，存儲(chǔ)復(fù)雜度Cs為

3) 通信復(fù)雜度

由于一個(gè)數(shù)據(jù)分組在最極端的情況下需要經(jīng)過(guò)N-1次轉(zhuǎn)發(fā)才能到達(dá)目的節(jié)點(diǎn)，因此通信復(fù)雜度Cc為

5 仿真實(shí)驗(yàn)

選取經(jīng)典的ER算法及其改進(jìn)版ER-HELLO、ARER算法作為比較對(duì)象，在相同的仿真參數(shù)條件下，比較4種算法的歸一化控制開(kāi)銷等性能。

5.1 仿真統(tǒng)計(jì)量

1) 歸一化控制開(kāi)銷

歸一化控制開(kāi)銷是所有節(jié)點(diǎn)發(fā)出的控制分組包含的比特?cái)?shù)與所有節(jié)點(diǎn)發(fā)送的控制分組和到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組包含的比特?cái)?shù)之比，計(jì)算公式為

其中，CP表示所有節(jié)點(diǎn)發(fā)送的控制分組包含的比特?cái)?shù)，DP表示所有到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組的比特?cái)?shù)。

2) 平均端到端時(shí)延

平均端到端時(shí)延是指到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組的平均耗時(shí)，計(jì)算公式為

其中，Ti表示第i個(gè)到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組的時(shí)延，D表示到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組數(shù)。

3) 節(jié)點(diǎn)平均緩存分組數(shù)

節(jié)點(diǎn)平均緩存分組數(shù)用來(lái)表明節(jié)點(diǎn)使用緩存的情況，計(jì)算公式為

其中，Ki表示第i個(gè)節(jié)點(diǎn)緩存的分組數(shù)，N為節(jié)點(diǎn)數(shù)。

4) 相遇節(jié)點(diǎn)平均感知時(shí)間

相遇節(jié)點(diǎn)平均感知時(shí)間用于顯示感知相遇節(jié)點(diǎn)的平均用時(shí)，計(jì)算公式為

其中，tall表示感知相遇節(jié)點(diǎn)總耗時(shí)，Cdiscovery表示感知到相遇節(jié)點(diǎn)的次數(shù)。

5) 數(shù)據(jù)分組傳送成功率

數(shù)據(jù)分組傳送成功率是指到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組數(shù)與所有源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組數(shù)之比，計(jì)算公式為

其中，D表示已到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組數(shù)，S表示所有源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組數(shù)。

5.2 仿真參數(shù)設(shè)置

本文以O(shè)PNET作為仿真軟件平臺(tái)，并根據(jù)文獻(xiàn)[9]設(shè)置節(jié)點(diǎn)的業(yè)務(wù)模型，節(jié)點(diǎn)移動(dòng)模型選用random waypoint，主要仿真參數(shù)設(shè)置如表1所示。

表1 主要仿真參數(shù)設(shè)置

5.3 仿真結(jié)果及分析

根據(jù)節(jié)點(diǎn)通信范圍的不同共設(shè)有 5種仿真場(chǎng)景，在每種仿真場(chǎng)景下分別運(yùn)行ERCES、ARER、ER-HELLO、ER-IMEP路由算法；每組實(shí)驗(yàn)分別進(jìn)行4次，實(shí)驗(yàn)結(jié)果取平均值；然后比較分析4種算法的歸一化控制開(kāi)銷、數(shù)據(jù)分組平均端到端時(shí)延等5方面性能。

1) 歸一化控制開(kāi)銷

從圖4可看出，ERCES算法的歸一化控制開(kāi)銷在每個(gè)場(chǎng)景中均低于 ER-IMEP算法及其改進(jìn)算法ER-HELLO、ARER，而且隨著節(jié)點(diǎn)通信范圍的增加，從0.89下降到0.82。ERCES算法能夠減少歸一化控制開(kāi)銷主要原因是通過(guò)跨層動(dòng)態(tài)調(diào)整 HELLO分組發(fā)送計(jì)時(shí)起點(diǎn)，減少了不必要HELLO分組；而控制開(kāi)銷隨節(jié)點(diǎn)通信范圍增大而降低的原因，則在于大的通信范圍能產(chǎn)生更多的通信鏈路，進(jìn)一步抑制HELLO分組的發(fā)送。

圖4 歸一化控制開(kāi)銷比較

2) 數(shù)據(jù)分組平均端到端時(shí)延

圖5顯示，與ARER等算法相比，ERCES算法能夠減小分組平均端到端時(shí)延11.3% (R=100 m：(46.959-41.673)/46.959≈0.113)～54%(R=25 m： (156.5-72.024)/ 156.5≈0.54)，產(chǎn)生這個(gè)結(jié)果的原因主要有三方面：(a) ERCES使用跨層信息共享的方式快速感知相遇節(jié)點(diǎn)，縮短了相遇節(jié)點(diǎn)感知時(shí)延；(b) 廣播新產(chǎn)生的數(shù)據(jù)分組，加快了數(shù)據(jù)分組的傳播過(guò)程；(c) 優(yōu)先發(fā)送目的節(jié)點(diǎn)為相遇節(jié)點(diǎn)的數(shù)據(jù)分組，對(duì)分組時(shí)延有降低作用。

圖5 分組平均端到端時(shí)延比較

3) 節(jié)點(diǎn)平均緩存分組數(shù)

由圖6可知，ERCES算法中節(jié)點(diǎn)的平均緩存分組數(shù)低于其他3種算法，其原因在于ERCES算法借用SV分組刪除了節(jié)點(diǎn)緩存中已到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組。ARER算法只在節(jié)點(diǎn)緩存空間受限的情況下才對(duì)緩存進(jìn)行處理，所以與另外2種算法緩存的分組數(shù)相近。

圖6 節(jié)點(diǎn)平均緩存分組數(shù)比較

4) 相遇節(jié)點(diǎn)平均感知時(shí)間

相遇節(jié)點(diǎn)感知時(shí)間與選擇的HELLO分組發(fā)送周期、相遇時(shí)間間隔閾值等因素有關(guān)。如圖7所示，ERCES算法的相遇節(jié)點(diǎn)平均感知時(shí)間在每個(gè)場(chǎng)景中均低于其他3種算法，它至少減少了16.6%(R=10 m：(1.401-1.168)/1.401≈0.166）的感知時(shí)間，其主要原因是 ERCES算法采用跨層信息共享的方式使網(wǎng)絡(luò)層更快地對(duì)節(jié)點(diǎn)相遇事件做出反應(yīng)，從而降低了相遇節(jié)點(diǎn)感知耗時(shí)。

圖7 平均相遇節(jié)點(diǎn)感知時(shí)間比較

5) 發(fā)送的HELLO分組數(shù)

如圖 8所示，在 ERCES算法中節(jié)點(diǎn)發(fā)送的HELLO分組數(shù)明顯小于其他3種算法，這主要是由于它采用了動(dòng)態(tài)自適應(yīng)的 HELLO分組發(fā)送機(jī)制，從而減少了不必要的HELLO分組發(fā)送，減少幅度為 13.6%(R=10 m)～44.3%(R=100 m)。

6) 數(shù)據(jù)分組傳送成功率

從表 2可以看出，ERCES算法與其他 3種算法一樣，在5個(gè)場(chǎng)景中的數(shù)據(jù)分組傳送成功率均達(dá)到了 100%，這說(shuō)明它保持了數(shù)據(jù)傳輸?shù)母呖煽啃浴?/p>

表2 數(shù)據(jù)分組傳送成功率比較

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

本文針對(duì)現(xiàn)有基于epidemic機(jī)制的機(jī)會(huì)網(wǎng)絡(luò)路由算法在相遇節(jié)點(diǎn)感知和數(shù)據(jù)分組交換過(guò)程中存在冗余的問(wèn)題，提出了采用跨層感知思路的ERCES路由算法加以解決，理論分析和仿真結(jié)果顯示ERCES算法較經(jīng)典的 ER算法及其多個(gè)改進(jìn)版本具有更低的控制開(kāi)銷和數(shù)據(jù)分組時(shí)延，從而提高了基于epidemic機(jī)制的機(jī)會(huì)網(wǎng)絡(luò)路由算法的可用性和用戶體驗(yàn)，有助于推動(dòng)機(jī)會(huì)網(wǎng)絡(luò)路由相關(guān)研究和應(yīng)用的深入開(kāi)展。在未來(lái)研究中，將以ERCES算法為基礎(chǔ)，設(shè)計(jì)跨層節(jié)能的路由算法，構(gòu)建綠色的機(jī)會(huì)網(wǎng)絡(luò)[18]。

[1] STAVROULAKI V, TSAGKARIS K, LOGOTHETIS M, et al. Opportunistic networks[J]. IEEE Vehicular Technology Magazine, 2011,6(3)：52-59.

[2] 熊永平, 孫利民, 牛建偉等. 機(jī)會(huì)網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 2009, 20(1)：124-137.XIONG Y P, SUN L M, NIU J W, et al. Opportunistic networks[J].Journal of Software, 2009, 20(1)：124-137.

[3] 葉暉, 陳志剛, 趙明. ON-CRP： 機(jī)會(huì)網(wǎng)絡(luò)緩存替換策略研究[J]. 通信學(xué)報(bào), 2010, 31(5)：98-107.YE H, CHEN Z G, ZHAO M. ON-CRP： cache replacement policy for opportunistic networks[J]. Journa1 on Communications, 2010, 31(5)：98-107.

[4] 劉喬壽, 周建二, 張普寧. 機(jī)會(huì)網(wǎng)絡(luò)中基于消息副本數(shù)量的自適應(yīng)緩存管理策略[J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 23(4)：394-399.LIU Q S, ZHOU J E, ZHANG P N. Adaptive cache management method for opportunistic network based on number of message copies[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2012, 23(4)：394-399.

[5] BURGESS J, GALLAGHER B, JENSEN D, et al. Maxprop： routing for vehicle-based disruption-tolerant networks[A]. The 25th IEEE International Conference on Computer Communications[C]. Washington DC, USA, 2006. 1-11.

[6] BURNS B, BROCK O, LEVINE B N. Mv routing and capacity building in disruption tolerant networks[A]. The 24th Annual Joint Conference of Conference of the IEEE Computer and Communications Societies[C]. Miami, USA, 2005. 398-408.

[7] JATHAR R, GUPTA A. Probabilistic routing using contact sequencing in delay tolerant networks[A]. 2010 the Second International Conference on Communication Systems and Networks[C]. Bangalore, India,2010.1-10.

[8] KO H, OH S, KIM C. Adaptive, asynchronous rendezvous protocol for opportunistic networks[J]. Journal of Electronic Letters, 2012, 48(8)：462-464.

[9] VAHDAT A, BECKER D. Epidemic Routing for Partially Connected Ad Hoc Networks[R]. 2000.

[10] MATSUADA T, TAKINE T. (p, q)-Epidemic routing for sparsely populated mobile ad hoc networks[J]. IEEE Journal on Selected Areas in Communications, 2008, 26(5)：783-793.

[11] TOWER J P, LITTLE T D C. A proposed scheme for epidemic routing with active curing for opportunistic networks[A]. The 22nd International Conference on Advanced Information Networking and Applications Workshops[C]. Okinawa, Japan, 2008. 1696-1701.

[12] WANG X, SHU Y T, JIN Z G, et al. Adaptive randomized epidemic routing for disruption tolerant networks[A]. The 5th International Conference on Mobile Ad Hoc and Sensor Networks[C]. Wu Yi Mountain, China, 2009. 424-429.

[13] 任智, 黃勇, 陳前斌. 基于分組索引增量交換的機(jī)會(huì)網(wǎng)路高效低時(shí)延路由算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2010, 33(9)：1634-1642.REN Z, HUANG Y, CHEN Q B. An efficient low-delay routing algorithm for opportunistic networks based on exchange of increments in packet indexes[J]. Chinese Journal of Computers, 2010, 33(9)：1634-1642.

[14] DEMERS A, GREENE D, HAUSER C, et al. Epidemic algorithms for replicated database maintenance[A]. The 6th Symposium on Principles of Distributed Computing[C]. British Columbia, Canada, 1987.8-32.

[15] 任智, 陳前斌, 黃勇. 機(jī)會(huì)網(wǎng)絡(luò)中基于跨層觸發(fā)的相遇節(jié)點(diǎn)快速感知方法[P]. 中國(guó)發(fā)明專利, 201010042051.2, 2010.REN Z, CHEN Q B, HUNAG Y. A Fast Approach for Sensing Encountered Nodes in Opportunistic Networks Based on Cross-Layer Triggering[P]. China Invention Patent, 201010042051.2, 2010.

[16] CORSON M S, PAPADEMETRIOU S, PAPADEMETRIOU P, et al. An internet MANET encapsulation protocol (IMEP) specification[EB/OL].http：//tools.ietf.org/html/draft-ietf-manet-imep-spec-00, 2011.

[17] GROSSGLAUSER M, TSE D N C. Mobility increases the capacity of ad hoc wireless networks[J]. IEEE/ACM Transactions on Networking,2002, 10(4)：477-486.

[18] 林闖, 田源, 姚敏. 綠色網(wǎng)絡(luò)和綠色評(píng)價(jià)：節(jié)能機(jī)制、模型和評(píng)價(jià)[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(4)：593-612.LIN C, TIAN Y, YAO M. Green network and green evaluation： mechanism, modeling and evaluation[J]. Chinese Journal of Computers, 2011,34(4)：593-612.