吳比，王菲，姜勝明

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）自適應半衰期的獲取方法

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

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

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

其中，關于thalf的計算公式如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

2 仿真和結果

2.1 仿真參數(shù)

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

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

本實驗主要分五個場景：

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

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

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

2.2 仿真結果

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

DQS1的估計結果如圖4所示，DQS2的估計結果如圖5所示。

圖4 DQS1估計精度結果圖

圖5 DQS2估計精度結果圖

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

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

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

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

3 結語

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