機(jī)會網(wǎng)絡(luò)中基于最短路徑的路由協(xié)議的穩(wěn)定性研究

王菲，吳比，姜勝明

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

機(jī)會網(wǎng)絡(luò)（OppNets,Opportunistic Networks）是一種特殊的移動自組織網(wǎng)絡(luò)[1]，其源于移動自組織網(wǎng)絡(luò)（MANETs）[2]與延遲容忍網(wǎng)絡(luò)（DTN）[3]。但與移動自組織網(wǎng)絡(luò)不同的是，機(jī)會網(wǎng)絡(luò)不要求源節(jié)點與目的節(jié)點存在完整的端到端的鏈路，而是通過節(jié)點移動帶來的相遇實現(xiàn)信息的傳送。即在整個過程中節(jié)點通過“存儲-攜帶-轉(zhuǎn)發(fā)”[4]方式進(jìn)行通信。

機(jī)會網(wǎng)絡(luò)雖然能實現(xiàn)極端環(huán)境下不存在端到端鏈路的通信，但是與傳統(tǒng)的通信相比，機(jī)會網(wǎng)絡(luò)存在著低傳輸成功率、低安全性、高路由開銷以及高傳輸時延等缺點,為了解決低傳輸成功率以及高傳輸時延的問題。一種基于洪泛的傳染病路由協(xié)議[5]應(yīng)用于機(jī)會網(wǎng)絡(luò)。該協(xié)議能充分利用節(jié)點相遇帶來的機(jī)會性，解決高傳輸率等問題，然而由于過渡的洪泛使得網(wǎng)絡(luò)中的消息冗余過多，網(wǎng)絡(luò)資源消耗過大。甚至?xí)a(chǎn)生數(shù)據(jù)安全隱患。

現(xiàn)有的研究要不強(qiáng)調(diào)傳輸?shù)某晒β剩粶p少網(wǎng)絡(luò)的資源消耗。但是在既保證傳輸成功率又能降低網(wǎng)絡(luò)開銷獲得很好的進(jìn)展；其次節(jié)點的稀疏，移動性將如何影響網(wǎng)絡(luò)的收包率及穩(wěn)定性并沒有被研究。

本文通過對上述問題的分析，首先，提出了在保證傳輸成功率的前提下降低了網(wǎng)絡(luò)開銷的路由協(xié)議，本文把該協(xié)議命名為EPIDEMIC；其次，將該協(xié)議在EX?ata仿真平臺上編程實現(xiàn)；最后，在仿真平臺上通過改變節(jié)點的密度以及節(jié)點的移動速度來模擬機(jī)會網(wǎng)絡(luò)，并探究在不同的節(jié)點密度與移動速度的環(huán)境下該協(xié)議與無線自組織網(wǎng)絡(luò)協(xié)議DSR的收包率以及穩(wěn)定性情況。

1 相關(guān)工作

目前，基于機(jī)會網(wǎng)絡(luò)的研究，主要有以下典型的路由協(xié)議。

Direct Delivery[6]路由協(xié)議，該協(xié)議是基于轉(zhuǎn)發(fā)策略的協(xié)議，是一種最為簡單直接的路由協(xié)議，只有當(dāng)目的節(jié)點在源節(jié)點的輻射范圍之內(nèi)，數(shù)據(jù)分組才會被交付。該算法的特點是無路由開銷，但是對于機(jī)會網(wǎng)絡(luò)而言，由于源節(jié)點與目的節(jié)點之間不存在固定的鏈路，源節(jié)點要經(jīng)過很長時間才能把數(shù)據(jù)交付，因此，該協(xié)議的傳輸率較低。

EPIDEMIC[7]路由協(xié)議也是基于轉(zhuǎn)發(fā)的路由協(xié)議。該協(xié)議有點類似于傳染病，在該路由協(xié)議下，節(jié)點會抓住每次相遇的機(jī)會。相遇的兩個節(jié)點會互相傳遞它們的沒有數(shù)據(jù)分組。可想而知，經(jīng)過一段時間后網(wǎng)絡(luò)中將存在大量的數(shù)據(jù)分組節(jié)點的緩存空間也會被大量地占用。雖然該協(xié)議能實現(xiàn)最大化的數(shù)據(jù)交換成功率，但是網(wǎng)絡(luò)開銷過大，信息的利用率較低。

Spray and Wait[8]路由協(xié)議是Direct Delivery路由協(xié)議的基礎(chǔ)上進(jìn)行了該進(jìn)。該協(xié)議分為兩個階段Spray和Wait階段。Spray階段：源節(jié)點為其每個數(shù)據(jù)分組生成L個數(shù)據(jù)分組副本，這些數(shù)據(jù)分組通過“噴灑”的方式傳遞給鄰居節(jié)點，每個鄰居節(jié)點在收到該分組后再進(jìn)行數(shù)據(jù)的傳遞，重復(fù)上面的過程，此方法有點類似于Epidemic路由協(xié)議。Wait階段：假如在Spray階段數(shù)據(jù)分組沒有到達(dá)目的節(jié)點，那存儲了數(shù)據(jù)分組的節(jié)點只能采用Direct Delivery方式進(jìn)行消息的交付。該算法縮短了消息的傳播時間，但是網(wǎng)絡(luò)開銷同樣很大。

DSR路由協(xié)議主要特征是在消息發(fā)送之前，源節(jié)點已經(jīng)知道到達(dá)目的節(jié)點路徑。為了節(jié)省路由發(fā)現(xiàn)的開銷，每個節(jié)點都擁有一個路由緩存區(qū)。機(jī)會網(wǎng)絡(luò)中路徑一般是不存在的，當(dāng)源節(jié)點發(fā)送消息時，而目的節(jié)點不在其路由表內(nèi)，便要開啟路由發(fā)現(xiàn)機(jī)制，動態(tài)地尋找一條路徑。DSR只采用源路由和路由緩沖區(qū)，而不需要專門的環(huán)路檢測機(jī)制，同時每個節(jié)點在在路由發(fā)現(xiàn)過程中已經(jīng)建立自己的路由緩沖區(qū)。

通過相關(guān)工作的分析及研究，本文將設(shè)計一種能靈活應(yīng)用于機(jī)會網(wǎng)絡(luò)，并且能改善相關(guān)工作遺留下的問題。最后將該協(xié)議與DSR路由協(xié)議進(jìn)行比較。

2 機(jī)會網(wǎng)絡(luò)中最快路徑協(xié)議設(shè)計

2.1 協(xié)議的基本思想

在機(jī)會網(wǎng)絡(luò)中，消息的傳遞需要依靠節(jié)點的移動來完成，所以要充分地抓住節(jié)點相遇的機(jī)會來傳遞消息。

如圖1所示，以節(jié)點2作為源節(jié)點，節(jié)點7作為目的節(jié)點。尋找一條從節(jié)點2到節(jié)7的最快路徑，首先，節(jié)點2通過洪泛的方式向周圍節(jié)點發(fā)送消息（p21代表節(jié)點2向節(jié)點1發(fā)送的消息），節(jié)點1與節(jié)點4最先收到消息，然后又以同樣的方式廣播出去。但是需遵循以下幾點:

①反方向不接受消息（節(jié)點2向節(jié)點1發(fā)送消息，對于同樣的消息節(jié)點1向節(jié)點2發(fā)送時，節(jié)點2不接收）。

②節(jié)點只接受和記錄最先到達(dá)的消息（節(jié)點4只接收了節(jié)點2發(fā)來的消息而節(jié)點1轉(zhuǎn)發(fā)來的同種消息節(jié)點4是不接收的。

通過這種方式能找到一種最快的方式到達(dá)目的節(jié)點。

圖1 協(xié)議的基本思想

2.2 協(xié)議的具體實現(xiàn)過程

（1）數(shù)據(jù)包的發(fā)送

數(shù)據(jù)包的格式如圖2所示，其攜帶的信息包括源地址、目的地址、消息號、消息類型、生存期。

圖2 數(shù)據(jù)包格式

①源地址與目的地址各占2個字節(jié)。

②消息號占4個字節(jié)，每個節(jié)點按序增加數(shù)據(jù)包的序號，用于表示是第幾個數(shù)據(jù)。

③消息類型0代表數(shù)據(jù)包，非0代表確認(rèn)包。

源節(jié)點在發(fā)送數(shù)據(jù)包時首先先給要發(fā)送的數(shù)據(jù)包進(jìn)行標(biāo)號，然后通過洪泛的方式將數(shù)據(jù)包發(fā)送出去。鄰居節(jié)點收到該數(shù)據(jù)包時，首先，通過查找消息號來判斷該數(shù)據(jù)包有沒被接收過，假如該數(shù)據(jù)包接收過就拒絕接收。假如沒有接收過，就立馬把該消息廣播出去。通過這種方式將消息發(fā)送給目的節(jié)點。

（2）確認(rèn)包的發(fā)送

確認(rèn)包分為兩個類型。一種是由目的節(jié)點發(fā)送的確認(rèn)包ACK，另一種是由非目的節(jié)點發(fā)送的確認(rèn)包NULL_ACK，兩者在結(jié)構(gòu)上是一致的，不同在于消息類型。其結(jié)構(gòu)如圖3所示。

圖3 確認(rèn)包的格式

①源地址與目的地址：應(yīng)答包的源地址與目的地址分別取當(dāng)前節(jié)點的地址和數(shù)據(jù)包的地址。

②消息號：節(jié)點每收到一個探測包消息號就+1。

③消息類型：1代表連通應(yīng)打包，2代表非連通應(yīng)打包。

④確認(rèn)號：取對應(yīng)探測包的消息號。例如，探測包的消息號為2，那么確認(rèn)包的確認(rèn)號就為2。

當(dāng)目的節(jié)點收到數(shù)據(jù)包時，就會判斷是不是第一次收到該數(shù)據(jù)包，假如是第一次收到該數(shù)據(jù)包就發(fā)送一個連通的確認(rèn)包，確認(rèn)包的消息號+1，確認(rèn)號為該數(shù)據(jù)包的標(biāo)號，假如目的節(jié)點不是第一次收到該數(shù)據(jù)包，就不回復(fù)確認(rèn)包。由于機(jī)會網(wǎng)絡(luò)中鏈路存在多變性與間歇性，所以消息不一定能發(fā)送到目的節(jié)點。當(dāng)中間節(jié)點收到數(shù)據(jù)包時，就會開啟偵聽模式，假如在時間T內(nèi)該數(shù)據(jù)包沒有被轉(zhuǎn)發(fā)（時間T的取值是發(fā)送數(shù)據(jù)包的間隔），就會向源節(jié)點發(fā)送一個非連通確認(rèn)包。

3 協(xié)議的收包率與穩(wěn)定性比較

3.1 仿真環(huán)境

（1）仿真工具

本文采用了EXata仿真平臺，該平臺網(wǎng)絡(luò)層次劃分清楚并且提供了可視化的界面來搭建仿真場景。

（2）參數(shù)設(shè)置

機(jī)會網(wǎng)絡(luò)的收包率與穩(wěn)定性與節(jié)點的密度，移動速度密不可分。考慮到這點原因，本文的移動模型均采用隨機(jī)停留點移動模型RWP（Random WayPoint）,如表1所示。其中，為了模擬真實場景，停留時間設(shè)置為0妙，節(jié)點的速度區(qū)間為0-100m/s，節(jié)點的移動精度為1m。

如表2所示，為節(jié)點的物理層設(shè)計，下列的值均為默認(rèn)值，傳輸功率，接收靈敏度決定了節(jié)點的傳輸距離。

表1 移動模型設(shè)置

表2 物理層設(shè)置（取自EXata物理層參數(shù)設(shè)置）

為了使對比結(jié)果具有說服性，我們對包的大小、發(fā)包的頻率及時間也有要求。包的大小為512bit，發(fā)包的時間間隔為3.9ms,發(fā)包起始時間為1s，結(jié)束時間為30s.這樣能保證網(wǎng)絡(luò)的帶寬達(dá)到1MB。根據(jù)這個發(fā)包的數(shù)量是7346個。表3是CRB的設(shè)置。

表3 CBR參數(shù)設(shè)置

（3）場景設(shè)置

實驗中分別在1500m×1500m的平面內(nèi)放了2-15個節(jié)點共14個場景。并且在每個場景下節(jié)點的移動速度從0m/s增長到100m/s，區(qū)間為5m/s。共21種情況。仿真時長均為30s。為了避免冗余，本文只去了一張仿真場景圖。如圖4所示，所有的場景都是以1為源節(jié)點，2為目的節(jié)點。

圖4 10個節(jié)點場景圖（取自EXata場景圖）

3.2 仿真分析

（1）節(jié)點密度與收包數(shù)、收包穩(wěn)定性的關(guān)系

圖5，橫軸為節(jié)點的數(shù)目，縱軸為在節(jié)點數(shù)一定的情況下不同的移動模型下收到的數(shù)據(jù)包的平均值。（例如，節(jié)點數(shù)目為5的場景下，分別測出速度為0m/s、5m/s、10m/s...100m/s目的節(jié)點收包的數(shù)目，在把這些收到的數(shù)據(jù)包個數(shù)加起來做平均值。）

圖5 節(jié)點密度與收到數(shù)據(jù)包平均值的關(guān)系圖

通過實驗可以發(fā)現(xiàn)，節(jié)點密度越高，收到的數(shù)據(jù)包會增多，不過節(jié)點密度對DSR路由協(xié)議的影響會很大。總體來說，EPIDEMIC路由協(xié)議的收到的數(shù)據(jù)包比DSR協(xié)議多。

圖6所示，橫軸為節(jié)點個數(shù)，縱軸為在節(jié)點數(shù)一定的情況下不同的速度移動的模型下收到數(shù)據(jù)包的方差。

由圖可知，DSR在節(jié)點少的時候方差較小，穩(wěn)定性不錯，但當(dāng)節(jié)點多了穩(wěn)定性就差了。而EPIDEMIC方差一直很穩(wěn)定，隨著節(jié)點的增加方差在減少，穩(wěn)定性在增加。

（2）節(jié)點的移動速度與收包數(shù)、收包穩(wěn)定性的關(guān)系如圖7所示，橫軸為節(jié)點的移動速度，縱軸為在速度一定的情況下在不同的節(jié)點密度收到的數(shù)據(jù)包的平均值。（例如，速度為60m/s，分別把該速度下的節(jié)點為2-15所收到的數(shù)據(jù)包求平均值。）

圖6 節(jié)點密度與收到數(shù)據(jù)包的方差關(guān)系圖

圖7 節(jié)點移速與收到數(shù)據(jù)包平均值關(guān)系圖

從圖中可以發(fā)現(xiàn)DSR收到的數(shù)據(jù)包呈現(xiàn)一種波狀圖，而且當(dāng)速度增加時，收到的數(shù)據(jù)包反而在減少，而EPIDEMIC隨著節(jié)點速度的增長，收到的數(shù)據(jù)包越來越多。

如圖8所示，橫軸為節(jié)點的移動速度，縱軸為在速度一定的情況下不同的節(jié)點密度下收到數(shù)據(jù)包的方差。

圖8 節(jié)點移速與收到數(shù)據(jù)包的方差關(guān)系圖

由圖可知EPIDEMIC的穩(wěn)定性比DSR的穩(wěn)定性好。隨著速度的增長EPIDEMIC的方差幾乎達(dá)到0。

（3）低節(jié)點密度、高節(jié)點移動速度與收包數(shù)，收包穩(wěn)定性的關(guān)系

我們?yōu)榱耸箼C(jī)會網(wǎng)絡(luò)特性更加明顯，選取了節(jié)點數(shù)為2-10，節(jié)點的移動速度為60m/s-100m/s的那部分實驗數(shù)據(jù)。分別重復(fù)了以上的數(shù)據(jù)處理方法。

由圖9可知，EPIDEMIC的收到的數(shù)據(jù)包明顯多于DSR收到的數(shù)據(jù)包個數(shù)，但是隨著節(jié)點數(shù)的增加，收到的數(shù)據(jù)包個數(shù)沒有明顯增加。

由圖10所示，EPIDEMIC收到數(shù)據(jù)包的方差明顯小于DSR路由協(xié)議。說明在節(jié)點數(shù)較少的情況下EP?IDEMIC路由協(xié)議比DSR路由協(xié)議穩(wěn)定。

由圖11所示，在移動速度較高的情況下，EPI?DEMIC收到的數(shù)據(jù)包多余DSR，隨著速度的增加，EPI?DEMIC收到的數(shù)據(jù)包較多。

由圖12所示，在較高移動速度下，EPIDEMIC路由算法的穩(wěn)定性較好，而DSR路由算法方差呈現(xiàn)一種波形，說明穩(wěn)定性較差。

4 結(jié)語

本文主要對機(jī)會網(wǎng)絡(luò)中自編協(xié)議與無線自組織網(wǎng)絡(luò)DSR路由協(xié)議在收包數(shù)和收包穩(wěn)定性兩方面進(jìn)行比較，發(fā)現(xiàn)自編協(xié)議能更好地適應(yīng)機(jī)會網(wǎng)絡(luò)中節(jié)點密度稀少，節(jié)點移動頻繁的情況。而DSR協(xié)議對節(jié)點密度有較高的要求，而且在節(jié)點密度較高的情況下，隨著速度的增長，DSR收到數(shù)據(jù)包的量反而在減少。總體而言，自編協(xié)議在保持較高收包數(shù)的同時，而且能保持信息在網(wǎng)絡(luò)中穩(wěn)定的傳輸。

圖9 節(jié)點個數(shù)與收到數(shù)據(jù)包的平均值關(guān)系圖

圖10 節(jié)點密度與收到數(shù)據(jù)包方差關(guān)系圖

圖11 節(jié)點移速與收到數(shù)據(jù)包平均值的關(guān)系圖

圖12 節(jié)點移速與收到數(shù)據(jù)包的方差關(guān)系圖