夏銘遠，吳比，王菲，姜勝明

（上海海事大學信息工程學院，上海201306）

0 引言

機會網(wǎng)絡是一種特殊的移動自組織網(wǎng)絡[1]，源于延遲容忍網(wǎng)絡[2]和移動自組網(wǎng)[3]。其主要的特點是其不依賴于固定的基礎設施，節(jié)點之間的通信完全是靠節(jié)點自身的移動帶來通信范圍的重合。由于機會網(wǎng)絡的這種通信方式，導致傳輸時延長，且傳輸成功率較低。路徑的選擇在提高傳輸成功率和降低傳輸時延中具有極其重要的作用，因此準確地獲取路徑以及節(jié)點的相關信息對于更好地輔助路由選擇具有十分重要的意義[4]。

在之前的研究中，基于發(fā)送探測包的方法探測路徑和節(jié)點信息在路徑尋找中雖然起到一定作用，但是針對不同長度的數(shù)據(jù)包，探測信息的收集方法沒有較好的自適應性[5]。本文針對上述問題提出一種自適應路徑狀態(tài)探測方法，可以更加準確地反映路徑狀況，更加可靠地用于估算后續(xù)不同長度數(shù)據(jù)包的時延信息，從而更好地輔助路由選擇。

1 相關方法與優(yōu)化

1.1 基于探測包的機會網(wǎng)絡信息收集方法

（1）基于探測包的機會網(wǎng)絡連通性量化方法

機會網(wǎng)絡的連通性量化方法的基本思想是：源節(jié)點向目的節(jié)點發(fā)送探測包，然后根據(jù)收到的目的節(jié)點發(fā)送的返回包ACK 來大致估算網(wǎng)絡的連通性。圖1為測量連通性方法流程圖，一共包括下面三個部分：①發(fā)送探測包，其中探測包的發(fā)包頻率由源節(jié)點根據(jù)收包和發(fā)包的關系來進行變化和調整；②應答探測包，其中應答探測包分為兩種，一種發(fā)送方是目的節(jié)點，另一種發(fā)送方是非目的節(jié)點；③源節(jié)點根據(jù)收到的應答包數(shù)量與發(fā)送的探測包數(shù)量的比值來衡量網(wǎng)絡連通狀態(tài)。

源節(jié)點在T 時間段內向目的節(jié)點發(fā)送探測包，探測包的發(fā)送頻率為fs，發(fā)送數(shù)量為num 個，若目的節(jié)點向源節(jié)點發(fā)送的連通應答包為m 個，那么在時間T 內的數(shù)據(jù)成功傳輸概率為P=m/num。由此，使用此比值P 來量化機會網(wǎng)絡連通性，同時也用P 來衡量機會網(wǎng)絡中兩個節(jié)點之間路徑存在的機會程度[6]。

圖1 連通性測試流程圖

（2）基于探測包的剩余路徑投遞時間估計

在剩余路徑投遞時間的研究中，路徑中的所有經(jīng)歷的節(jié)點都發(fā)送帶有時間戳的探測包給其鄰居節(jié)點，當鄰居節(jié)點收到探測包以后，同時加入自己的時間戳，并將探測包繼續(xù)轉發(fā)給其他鄰居節(jié)點，這樣根據(jù)兩個時間戳的差值即可得到一個單向的時延[7-8]，節(jié)點不僅可以獲取到自身的時延還可以獲取到鄰居節(jié)點發(fā)送數(shù)據(jù)分組的時延。所有節(jié)點共同維護一個時延表，節(jié)點可以通過廣播時延表的操作使鄰居節(jié)點收到表后立即更新自己的時延表，并且將時延表中改變的部分繼續(xù)廣播給其他節(jié)點。

這種基于發(fā)送探測包的剩余路徑投遞時間估計方式主要特點在于可以利用所有節(jié)點共同維護的時延表來估計剩余路徑的投遞時間[9]。

（3）探測包研究方法分析

利用探測包獲取網(wǎng)絡信息存在的最大的問題是由探測包和數(shù)據(jù)包長度的不同而帶來的在網(wǎng)絡中的差異，無法對數(shù)據(jù)包有較好的適用性，想要將發(fā)送探測包探測的結果應用到后續(xù)發(fā)送不同數(shù)據(jù)包的過程中具有一定的困難。

1.2 基于發(fā)送探測包的自適應性路徑信息的探測方法

（1）探測包在路徑中探測的信息及具體探測方法

為了提高探測信息對數(shù)據(jù)包的適用性，本文提出的一種基于發(fā)送探測包的自適應性路徑信息的收集方法。該方法主要通過源節(jié)點向目的節(jié)點發(fā)送探測包，目的節(jié)點接收到探測包后將探測信息以回復包的方式反饋給源節(jié)點實現(xiàn)的。其中，探測包在路徑中所收集的信息主要包括路徑上節(jié)點的總發(fā)送時延倒數(shù)之和、路徑的平均等待時延以及鏈路可靠性。探測收集到的信息可以用于估算后續(xù)發(fā)送不同長度的數(shù)據(jù)包所經(jīng)歷的時延信息，同時可以更加精確地獲取節(jié)點以及路徑狀況，源節(jié)點可以通過探測包收集到的信息進行不同路徑的選擇。

①路徑總發(fā)送時延的信息收集及其方法

針對路徑中總發(fā)送時延的信息收集方法，即源節(jié)點通過探測包計算發(fā)送不同數(shù)據(jù)包時路徑中的總發(fā)送時延，這里所述的計算不同數(shù)據(jù)包在路徑中總發(fā)送時延的方法是：將探測包所經(jīng)歷所有節(jié)點的發(fā)送速率的倒數(shù)進行求和，且用S 表示：

然后用上述求和結果S 與H 的乘積求出發(fā)送不同長度的數(shù)據(jù)包時路徑中總發(fā)送時延Ts，即：

其中Vi代表探測包在第i 個節(jié)點的發(fā)送速率，H代表發(fā)送的不同數(shù)據(jù)包長度。

②路徑平均等待時間的信息收集及其方法

源節(jié)點通過探測包獲取路徑的平均等待時間，這里所述路徑的平均等待時間是用路徑中所有節(jié)點的平均等待時間之和計算的，假設路徑中每個節(jié)點的平均等待時間為，路徑平均等待時間為

路徑中每個節(jié)點的平均等待時間，是指經(jīng)歷某個節(jié)點的所有包的等待時間的平均值，具體計算方法是：將到達某一節(jié)點的所有包的發(fā)送時刻與到達時刻分別求和并相減，最后除以包的數(shù)量，假設n 個包經(jīng)歷某一節(jié)點時，到達時刻分別為t1,t2,…,tn，即將發(fā)送的時刻分別為T1,T2,…,Tn，該節(jié)點的平均等待時間為：

②鏈路可靠性信息的收集及其方法

鏈路可靠性反映的是某條路徑的可靠程度，本文將其具體量化為目的節(jié)點的收包數(shù)量與源節(jié)點發(fā)包數(shù)量的比值。相對于源節(jié)點的發(fā)包數(shù)量而言，目的節(jié)點收到的包的數(shù)量越多，說明這條路徑上的丟包率越少，路徑越可靠。節(jié)點轉發(fā)數(shù)據(jù)分組并進行選路的過程中也更傾向于選擇這樣相對穩(wěn)定的路徑。因此，我們用目的節(jié)點收到的探測包數(shù)量a 與源節(jié)點的發(fā)出探測包的數(shù)量b 的比值P 來反映該鏈路的可靠性，即：

④方法的優(yōu)點與合理性

機會網(wǎng)絡中由于探測包較短而數(shù)據(jù)包較長，使得探測包探測的數(shù)據(jù)一直沒有較好的方法可以應用數(shù)據(jù)包。而上述提出新的方法可以通過向目的節(jié)點發(fā)送探測包來獲取整個鏈路的總發(fā)送時延、平均等待時延以及鏈路可靠性，并且這種方法對于數(shù)據(jù)包具有較強的適應性，可以用于估算后續(xù)不同長度的數(shù)據(jù)包所經(jīng)歷的時延信息，獲取的結果具有廣泛性和準確性。同時，可以更加準確地獲取節(jié)點以及路徑狀況，大大提高通信效率，這對于機會網(wǎng)絡中路由的選擇和路徑的評價具有十分重要的意義。

（2）探測包信息收集過程

源節(jié)點根據(jù)探測包收集的信息進行不同路徑的選擇首先需要得到目的節(jié)點的反饋信息，因此我們將路徑總發(fā)送時延信息、路徑平均等待時延信息以及鏈路可靠性信息全部放在目的節(jié)點發(fā)送的反饋包中一起返回給源節(jié)點。

源節(jié)點只有在收到目的節(jié)點發(fā)來的反饋信息才能得到整個鏈路的信息。但是在探測包被轉發(fā)過程中可能會由于丟包等問題無法到達目的節(jié)點，此時目的節(jié)點將無法向源節(jié)點發(fā)送反饋包，該條記錄的信息收集失敗。所以探測包在每到達一個節(jié)點時首先要判斷當前節(jié)點是否為目的節(jié)點，然后做出相應回復。

①若當前節(jié)點為目的節(jié)點，則目的節(jié)點回復一個帶有所有節(jié)點發(fā)送速率的倒數(shù)求和S、路徑平均等待時間和目的節(jié)點實際收包數(shù)量b 信息的確認包給源節(jié)點，如圖2；

圖2 目的節(jié)點回復確認包示意圖

②若當前節(jié)點為非目的節(jié)點，則偵聽在Δσ時間里是否有其他節(jié)點轉發(fā)該探測包，若沒有，當前節(jié)點回復失敗反饋包給源節(jié)點，說明該探測包無法到達目的節(jié)點，若有，則繼續(xù)轉發(fā)探測包，如圖3；

圖3 非目的節(jié)點回復失敗反饋包示意圖

其中上述Δσ 的取值為源節(jié)點平均每發(fā)送兩個探測包之間的時間間隔，若源節(jié)點在Time 時間內發(fā)送m個數(shù)據(jù)包，Δσ 取值為

具體探測過程如圖4 所示。

圖4 節(jié)點轉發(fā)探測包流程圖

2 仿真和結果

利用探測包估計的數(shù)據(jù)包總發(fā)送時延的精度的大小作為網(wǎng)絡路徑信息收集方法性能的主要評價參數(shù)，在對提出的基于發(fā)送探測包的自適應性路徑信息的收集方法的性能測試中，本文將其作為主要的評判標準。

2.1 仿真場景及參數(shù)設置

為了搭建符合機會網(wǎng)絡特征的仿真場景，驗證探測包估計的數(shù)據(jù)包時延信息與發(fā)送真實數(shù)據(jù)包的時延信息的差異性，分別在節(jié)點靜止和節(jié)點隨機移動的場景中進行試驗。兩個場景的基本參數(shù)大致相同，表1為場景一的基本參數(shù)信息，表2 為場景二的基本參數(shù)信息，分別在EXata 仿真平臺上進行五次實驗。

表1 場景一參數(shù)設置

表2 場景二參數(shù)設置

2.2 仿真結果

實驗主要是通過控制節(jié)點保持靜止或運動這兩個狀態(tài)下，研究發(fā)送數(shù)據(jù)包的總發(fā)送時延的真實值與通過探測包估計的值之間的差異。靜態(tài)實驗的設計是為了模擬在網(wǎng)絡拓撲不發(fā)生變化的情況下，研究探測估計值的準確性。通常情況下靜態(tài)屬于機會網(wǎng)絡中的一個短暫的中間狀態(tài)，這樣的實驗設計有利于分析估計精度與兩個狀態(tài)之間存在關系，從而更加全面的分析探測結果的準確性。

圖5 場景一估計值與真實值對比圖

在場景一中節(jié)點保持靜止狀態(tài)的實驗中，五次試驗的估計值并無明顯差異，且較為穩(wěn)定；而真實值雖然有略微變化，但變化不大。從縱向上來看，每次試驗結果的真實值與估計值都無顯著差異。這個結果說明在拓撲結構不發(fā)生改變時，用探測包估計的數(shù)據(jù)包路徑總發(fā)送時延與真實時延并無較明顯差異，估計值較為準確，可以用探測包的方法來估計數(shù)據(jù)包在路徑中的總發(fā)送時延。

圖6 場景二估計值與真實值對比圖

在場景二中節(jié)點保持運動狀態(tài)的實驗中，五次試驗的估計值無明顯差異，且較為穩(wěn)定；而真實值雖然有略微變化，但變化不大。從縱向上來看，每次試驗結果的真實值與估計值都無顯著差異。這個結果說明在拓撲結構發(fā)生變化時，用探測包估計的數(shù)據(jù)包路徑總發(fā)送時延與真實數(shù)據(jù)包仿真結果也無較明顯差異，且估計值較為準確，可以用探測包的方法來估計拓撲結構發(fā)生變化的網(wǎng)絡中數(shù)據(jù)包在路徑中的總發(fā)送時延。

圖7 兩個場景誤差比對比圖

為了將估計的總發(fā)送時延與真實數(shù)據(jù)包在路徑中總發(fā)送時延進行比較，并得到誤差的準確情況，本節(jié)將探測包估計的總時延Te和數(shù)據(jù)包實際發(fā)送的總時延Ta之差與數(shù)據(jù)包實際發(fā)送的總時延之Ta比求得誤差比B作為衡量估計精度的性能指標：

通過上述圖7 可以看出：橫向上，場景一和場景二中五次試驗的誤差比雖然都有差異，但是由于其誤差比數(shù)值差別較小，并且兩個場景的五次試驗誤差比有差異的原因可能是由于網(wǎng)絡中環(huán)境位置等因素所帶來的影響，因此在拓撲結構不發(fā)生變化的情況下，認為實驗一中兩個場景的五次試驗其各自的誤差比無顯著差異。從縱向上看，五次試驗中場景二的誤差比總是高于場景一，反映了本方法在動態(tài)網(wǎng)絡的估計精度相對于靜態(tài)網(wǎng)絡要低一些，產(chǎn)生這樣結果的主要還是由于動態(tài)網(wǎng)絡中節(jié)點的移動、找路、轉發(fā)等過程帶來的影響。

3 結語

通過仿真實驗，分析了優(yōu)化后的基于探測包的自適應性路徑信息收集方法在靜態(tài)和動態(tài)拓撲環(huán)境下的性能。實驗證明，無論是在靜態(tài)拓撲結構還是動態(tài)拓撲結構的網(wǎng)絡中，本文提出的基于發(fā)送探測包的自適應性路徑信息的收集方法都具有較好的性能，其探測信息可以應用到預估數(shù)據(jù)包的發(fā)送過程中。