一種自適應路徑狀態探測方法

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

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

0 引言

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

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

1 相關方法與優化

1.1 基于探測包的機會網絡信息收集方法

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

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

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

圖1 連通性測試流程圖

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

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

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

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

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

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

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

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

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

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

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

其中Vi代表探測包在第i 個節點的發送速率，H代表發送的不同數據包長度。

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

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

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

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

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

④方法的優點與合理性

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

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

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

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

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

圖2 目的節點回復確認包示意圖

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

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

其中上述Δσ 的取值為源節點平均每發送兩個探測包之間的時間間隔，若源節點在Time 時間內發送m個數據包，Δσ 取值為

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

圖4 節點轉發探測包流程圖

2 仿真和結果

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

2.1 仿真場景及參數設置

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

表1 場景一參數設置

表2 場景二參數設置

2.2 仿真結果

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

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

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

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

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

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

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

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

3 結語

通過仿真實驗，分析了優化后的基于探測包的自適應性路徑信息收集方法在靜態和動態拓撲環境下的性能。實驗證明，無論是在靜態拓撲結構還是動態拓撲結構的網絡中，本文提出的基于發送探測包的自適應性路徑信息的收集方法都具有較好的性能，其探測信息可以應用到預估數據包的發送過程中。