一種自適應(yīng)路徑狀態(tài)探測方法

夏銘遠(yuǎn)，吳比，王菲，姜?jiǎng)倜?/p>

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

0 引言

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

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

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

1.1 基于探測包的機(jī)會(huì)網(wǎng)絡(luò)信息收集方法

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

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

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

圖1 連通性測試流程圖

（2）基于探測包的剩余路徑投遞時(shí)間估計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 目的節(jié)點(diǎn)回復(fù)確認(rèn)包示意圖

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

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

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

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

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

2 仿真和結(jié)果

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

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

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

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

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

2.2 仿真結(jié)果

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

圖5 場景一估計(jì)值與真實(shí)值對比圖

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

圖6 場景二估計(jì)值與真實(shí)值對比圖

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

圖7 兩個(gè)場景誤差比對比圖

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

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

3 結(jié)語

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