吳比，王菲，姜勝明

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

0 引言

無線自組織網(wǎng)絡(luò)[1]中由于節(jié)點具有較強(qiáng)的移動性使得網(wǎng)絡(luò)自身動態(tài)性很強(qiáng)，如何才能提供更優(yōu)的服務(wù)質(zhì)量（Quality of Service,QoS）成為了無線自組織網(wǎng)絡(luò)面臨的一個重要問題。差分隊列服務(wù)[2][3]（Differentiated Queueing Service,DQS）作為一種以數(shù)據(jù)包為粒度的隊列調(diào)度算法，可在無線自組織網(wǎng)絡(luò)這種環(huán)境下根據(jù)服務(wù)質(zhì)量要求和路徑狀況調(diào)整包的發(fā)送次序，致力于將真正緊急的數(shù)據(jù)分組優(yōu)先轉(zhuǎn)發(fā)。路徑狀況主要指剩余路徑的投遞時間，即該數(shù)據(jù)分組在離開本節(jié)點到達(dá)目的節(jié)點這段路徑上還需要的時間信息。由此，如何進(jìn)行剩余投遞時間估計成了差分隊列服務(wù)的核心問題。

文獻(xiàn)[4]給出了機(jī)會網(wǎng)絡(luò)是一種源節(jié)點和目的節(jié)點之間不需要存在完整鏈路，而是利用節(jié)點移動所帶來的相遇機(jī)會實現(xiàn)通信的自組織網(wǎng)絡(luò)。具體表現(xiàn)形式就是，機(jī)會網(wǎng)絡(luò)中節(jié)點依靠移動形成通信機(jī)會，進(jìn)行逐跳地傳輸消息，以“存儲-攜帶-轉(zhuǎn)發(fā)”的路由模式實現(xiàn)節(jié)點間通信。

文獻(xiàn)[5]提出了一種應(yīng)用于DQS的基于半衰期的剩余路徑投遞時間的估計方法，該方法包含了一種基于半衰期的歷史信息有效性計算方法，但是在該方法中半衰期值是根據(jù)場景參數(shù)計算得來的固定值，無法適用動態(tài)拓?fù)渚W(wǎng)絡(luò)的變化，本文提出一種自適應(yīng)的半衰期獲取方法，通過仿真測試了優(yōu)化前后剩余路徑投遞時間估計方法的精度。

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

1.1 一種基于半衰期的剩余投遞時間估計方法

（1）基于半衰期的歷史信息有效性計算方法

歷史信息有效性是指在當(dāng)前時間，一個歷史信息用于估計或預(yù)測時所具有的價值。該方法依據(jù)歷史信息記錄的登記時間距離當(dāng)前時間的跨度，每經(jīng)過一個半衰期時間信息有效性減半的原則，計算歷史信息記錄在當(dāng)前時間的有效性。信息有效性υ的數(shù)值范圍是（0，1）。

設(shè)網(wǎng)絡(luò)場景的平均通信半徑為l,單位為米，場景面積為r單位平方米,網(wǎng)絡(luò)系統(tǒng)中節(jié)點個數(shù)為n，單位米，網(wǎng)絡(luò)節(jié)點的平均移動速度為s單位為秒，半衰期λ的計算公式如下：

信息有效性v的計算公式如下：

公式中，τn表示該信息的登記時間m與當(dāng)前時間tn的時長差，即τn=tn-m。

在實現(xiàn)過程當(dāng)中，網(wǎng)絡(luò)節(jié)點需要記錄當(dāng)前時間與數(shù)據(jù)分組在源節(jié)點的生成時間之差并將其作為一個歷史信息記錄，即當(dāng)前節(jié)點與源節(jié)點之間所在路徑上的歷史實際投遞時間，從源節(jié)點到當(dāng)前節(jié)點的相反路徑方向定義為反向路徑，當(dāng)有數(shù)據(jù)分組經(jīng)過此節(jié)點到達(dá)源節(jié)點時，此記錄作為該分組的一次剩余路徑時間。

（2）剩余路徑投遞時間估計方法介紹

一個分組剩余投遞時間的估計值等于其剩余路徑的反向路徑上的歷史實際投遞時間以其信息有效性為權(quán)重的加權(quán)均值。例如，從本節(jié)點到目的節(jié)點d的投遞時間估計值：

其中τd,j表示保存在此節(jié)點上的從d節(jié)點到本節(jié)點的第j個歷史實際投遞時間，vd,j表示反向路徑歷史實際投遞時間τd,j所對應(yīng)的歷史信息有效性。

在實現(xiàn)的過程中，數(shù)據(jù)分組需要在頭部攜帶兩個字段：該數(shù)據(jù)分組的最大端到端時延與源節(jié)點的生成時間。數(shù)據(jù)分組的離開時間等于數(shù)據(jù)分組生成時間加上其自身最大端到端時延，然后減去剩余路徑時間，最后節(jié)點依據(jù)數(shù)據(jù)分組的離開時間進(jìn)入隊列，使緊急的數(shù)據(jù)分組優(yōu)先轉(zhuǎn)發(fā)。

雖然這種估計方法在相對短暫且穩(wěn)定的時間內(nèi)有較好的準(zhǔn)確性，但是這種方法是基于半衰期值計算歷史信息記錄有效性的，而半衰期值使用的是基于場景參數(shù)計算而來，包括了場景面積、節(jié)點數(shù)量、移動速度，節(jié)點通信半徑等，該半衰期值是一個固定值。而無線自組織網(wǎng)絡(luò)中，節(jié)點移動具有很強(qiáng)的隨機(jī)性，難以獲取這些參數(shù)信息，因而這種半衰期在實際部署時不具有可行性。而且，當(dāng)中間節(jié)點沒有有效的歷史信息記錄時，該方法失去了估計的依據(jù)，而變得不再可用。

1.2 剩余投遞時間估計方法的優(yōu)化過程

（1）自適應(yīng)半衰期的獲取方法

原方法中半衰期使用網(wǎng)絡(luò)場景參數(shù)通過計算獲得，是一個固定值，雖然基于網(wǎng)絡(luò)場景參數(shù)，卻難以適應(yīng)動態(tài)拓?fù)渚W(wǎng)絡(luò)環(huán)境造成的歷史信息記錄準(zhǔn)確性較低的情況，因而提出一種自適應(yīng)的半衰期[6]獲取方法，自適應(yīng)網(wǎng)絡(luò)的變化。

為了方便介紹該自適應(yīng)半衰期獲取方法，引入以下變量：

表1 自適應(yīng)半衰期獲取方法中變量名稱與含義

其中，關(guān)于thalf的計算公式如下：

然后在歷史信息記錄表中選擇登記時間與thalf時間最接近那條歷史信息記錄，設(shè)其登記時間tmid。則當(dāng)歷史信息記錄條目數(shù)量大于等于3時可得半衰期值：

而當(dāng)歷史記錄數(shù)只有一條，其信息衰減的意義不大，半衰期可以設(shè)為一個任意大于零的常數(shù)。因為在這種情況下，在對一條歷史信息記錄求加權(quán)均值，其有效性大小不影響最終結(jié)果。當(dāng)歷史記錄數(shù)只有兩條時：

歷史信息記錄表中所有歷史信息記錄的登記時間跨度為信息有效性的衰減過程，將中間值時間定義為半衰時間，即thalf，找到臨近中間時間的歷史信息記錄條目，可認(rèn)為該歷史記錄為半衰的歷史信息記錄條目，即tmid，當(dāng)前時間與其相減得出半衰期值。為了更直觀地描述上述自適應(yīng)半衰期方法，如圖1中，在整個歷史信息記錄表中，最新歷史信息記錄到最舊歷史信息記錄，其信息有效性依次衰減。其中ti最接近中間時間，則認(rèn)為ti到tn的時間跨度為一個半衰期值：

圖1 實際路徑時間信息有效性衰減信息圖

這樣處理，一方面有利于提高歷史信息記錄表的利用率，更加符合半衰期定義的本意，同時，無需得知網(wǎng)絡(luò)場景中諸如節(jié)點移動速度、節(jié)點數(shù)量、場景面積等等復(fù)雜又難以獲取的參數(shù)信息，可以適應(yīng)網(wǎng)絡(luò)中不同的數(shù)據(jù)分組傳輸速率，都將進(jìn)行信息有效性區(qū)分。

（2）目的節(jié)點向源節(jié)點的回包機(jī)制

具體方法：當(dāng)節(jié)點收到一個數(shù)據(jù)分組，而節(jié)點在本地又缺乏有效歷史信息記錄，通過改變該數(shù)據(jù)分組攜帶的“標(biāo)記位”，并最終轉(zhuǎn)發(fā)到目的節(jié)點，目的節(jié)點識別該“標(biāo)記位”后，會反向給源節(jié)點回復(fù)一個數(shù)據(jù)分組，其回復(fù)的數(shù)據(jù)分組采用與接收到的分組同樣的大小。因此該回復(fù)數(shù)據(jù)分組機(jī)制將有利于補(bǔ)充中間節(jié)點缺乏歷史信息記錄的情況，從而增強(qiáng)該估計方法的應(yīng)用性。

其中“標(biāo)記位”的結(jié)構(gòu)如圖2，次末位置1代表節(jié)點無該數(shù)據(jù)分組的路由：

圖2 數(shù)據(jù)分組攜帶的信息標(biāo)記位

該方法具體處理過程可用下面的流程圖說明，如圖3所示。

信息有效性總和是否為0的判斷，在于確定節(jié)點歷史信息記錄是否已全部老化，當(dāng)歷史信息記錄過于陳舊則進(jìn)行剩余路徑投遞時間估計時精度難以保證。因此需要回包機(jī)制以補(bǔ)充有效的歷史信息記錄，提高剩余路徑投遞時間的估計精度。

圖3 目的節(jié)點向源節(jié)點回包機(jī)制流程圖

該回復(fù)數(shù)據(jù)分組的機(jī)制不同于廣播探測包的過程[7-8]，而是普通的源節(jié)點與目的節(jié)點之間正常的單播發(fā)送數(shù)據(jù)包過程，而且如圖3所示的控制機(jī)制，可以有效控制發(fā)包量，僅僅進(jìn)行最低限度的發(fā)包，在一定程度上可以避免增大網(wǎng)絡(luò)擁塞。但是可以有效獲得剩余路徑投遞時間，創(chuàng)建有效的歷史信息記錄，提高該基于半衰期剩余路徑投遞時間估計方法的應(yīng)用性。

2 仿真和結(jié)果

2.1 仿真參數(shù)

本文所涉及的所有實驗都使用的是EXata，此平臺由美國SNT公司所開發(fā)的，允許用戶更加快速真實地評估網(wǎng)絡(luò)性能。本文將機(jī)會網(wǎng)絡(luò)的鏈路連通性低、拓?fù)浣Y(jié)構(gòu)變化頻繁這個特點用節(jié)點移動速度的改變來模擬，從而測試在五個不同場景下的剩余投遞時間估計方法優(yōu)化前后的估計精度。

考察數(shù)據(jù)分組剩余路徑投遞時間估計方法的估計精度關(guān)鍵在于估計值與實際值的差異。這兩者差異越小可認(rèn)為估計的剩余路徑投遞時間準(zhǔn)確性越高。因此，為了將剩余路徑投遞時間的估計值與數(shù)據(jù)分組實際的剩余路徑投遞時間進(jìn)行比較，并得到其誤差情況，本節(jié)將估計誤差比當(dāng)作估計精度的性能指標(biāo)：

本實驗主要分五個場景：

2.拓寬綠色通道范圍。在活畜禽流通免收過路費的基礎(chǔ)上，對鮮畜禽產(chǎn)品運輸及當(dāng)日當(dāng)次返空車輛實行“綠色通道”。

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

表3 仿真場景節(jié)點平均移動速度參數(shù)信息

2.2 仿真結(jié)果

在實驗中，通過調(diào)節(jié)節(jié)點的平均移動速度，得到各個場景數(shù)據(jù)分組的估計精度區(qū)間。需要說明的是，在本節(jié)仿真實驗中，將優(yōu)化后與優(yōu)化前基于半衰期剩余路徑投遞時間估計方法的差分隊列服務(wù)分別設(shè)為DQS1和DQS2。此外，在估計精度區(qū)間結(jié)果圖中，橫坐標(biāo)10代表估計精度10%以內(nèi)，20代表估計精度位于10%到20%之間，30代表估計精度位于20%到30%之間，40代表估計精度位于30%到40%之間。而50代表了所有估計精度大于40%的情況。

DQS1的估計結(jié)果如圖4所示，DQS2的估計結(jié)果如圖5所示。

圖4 DQS1估計精度結(jié)果圖

圖5 DQS2估計精度結(jié)果圖

通過觀察圖4與圖5可以大致看出，估計精度位于10%到40%之間，其比例都比較小，位于10%以內(nèi)的比例最大，因此可以大致認(rèn)為，該基于半衰期的剩余路徑投遞時間估計方法在多數(shù)情況下，估計精度較高。而同時，仍然有較高比例其估計精度大于40%，說明存在著較大的估計誤差。并且，優(yōu)化前后其估計精度在10%以內(nèi)和大于40%以外的差異最為明顯，分別代表著估計最準(zhǔn)確和最不準(zhǔn)確的比例。也是最能體現(xiàn)估計精度差異的兩個精度區(qū)間，下面圖6與圖7分別對比這兩個估計精度區(qū)間的情況。圖6為其估計精度在10%以內(nèi)的比例，圖7其為估計精度在40%以外的比例：

圖6 實驗一中DQS1與DQS2估計精度在10%以內(nèi)對比圖

圖7 實驗一中DQS1與DQS2估計精度在40%以內(nèi)對比圖

從橫向看，場景一到場景五，節(jié)點移動速度在持續(xù)增大，而不同的節(jié)點移動速度下節(jié)點相遇的情況是不同的，擁塞程度、信道競爭激烈程度也有差異，因而各個仿真場景中的仿真結(jié)果不具有必然的聯(lián)系。從縱向看，每一個仿真場景中節(jié)點的運動軌跡是固定的，拓?fù)浣Y(jié)構(gòu)的變化是固定的。觀察估計精度10%以內(nèi)的情況，DQS1的比例要高于DQS2的，在估計精度大于40%的情況看，DQS1的比例要低于DQS2的。因此，從總體而言，優(yōu)化后的基于半衰期剩余路徑投遞時間估計方法，其估計精度是有所提高的，具體表現(xiàn)為：估計精度較高比例有所提高的同時，其估計精度較低的比例明顯下降。

3 結(jié)語

通過仿真實驗，分析優(yōu)化前后基于半衰期的剩余路徑投遞時間估計方法的估計精度并比較其性能。實驗證明，優(yōu)化后的剩余路徑投遞時間估計方法的剩余路徑投遞時間估計精度從總體上有顯著提高。