基于半衰期的剩余路徑投遞時間估計優化

吳比，王菲，姜勝明

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

0 引言

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

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

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

1 相關方法與優化

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

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

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

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

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

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

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

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

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

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

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

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

1.2 剩余投遞時間估計方法的優化過程

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

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

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

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

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

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

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

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

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

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

（2）目的節點向源節點的回包機制

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

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

圖2 數據分組攜帶的信息標記位

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

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

圖3 目的節點向源節點回包機制流程圖

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

2 仿真和結果

2.1 仿真參數

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

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

本實驗主要分五個場景：

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

表2 場景參數設置

表3 仿真場景節點平均移動速度參數信息

2.2 仿真結果

在實驗中，通過調節節點的平均移動速度，得到各個場景數據分組的估計精度區間。需要說明的是，在本節仿真實驗中，將優化后與優化前基于半衰期剩余路徑投遞時間估計方法的差分隊列服務分別設為DQS1和DQS2。此外，在估計精度區間結果圖中，橫坐標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%以內的比例最大，因此可以大致認為，該基于半衰期的剩余路徑投遞時間估計方法在多數情況下，估計精度較高。而同時，仍然有較高比例其估計精度大于40%，說明存在著較大的估計誤差。并且，優化前后其估計精度在10%以內和大于40%以外的差異最為明顯，分別代表著估計最準確和最不準確的比例。也是最能體現估計精度差異的兩個精度區間，下面圖6與圖7分別對比這兩個估計精度區間的情況。圖6為其估計精度在10%以內的比例，圖7其為估計精度在40%以外的比例：

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

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

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

3 結語

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