基于半衰期的剩余路徑投遞時(shí)間估計(jì)優(yōu)化

吳比，王菲，姜?jiǎng)倜?/p>

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

0 引言

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

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

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

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

1.1 一種基于半衰期的剩余投遞時(shí)間估計(jì)方法

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

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

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

信息有效性v的計(jì)算公式如下：

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

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

（2）剩余路徑投遞時(shí)間估計(jì)方法介紹

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

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

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

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

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

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

原方法中半衰期使用網(wǎng)絡(luò)場(chǎng)景參數(shù)通過計(jì)算獲得，是一個(gè)固定值，雖然基于網(wǎng)絡(luò)場(chǎng)景參數(shù)，卻難以適應(yīng)動(dò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的計(jì)算公式如下：

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

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

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

圖1 實(shí)際路徑時(shí)間信息有效性衰減信息圖

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

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

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

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

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

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

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

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

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

2 仿真和結(jié)果

2.1 仿真參數(shù)

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

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

本實(shí)驗(yàn)主要分五個(gè)場(chǎng)景：

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

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

表3 仿真場(chǎng)景節(jié)點(diǎn)平均移動(dòng)速度參數(shù)信息

2.2 仿真結(jié)果

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

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

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

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

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

圖6 實(shí)驗(yàn)一中DQS1與DQS2估計(jì)精度在10%以內(nèi)對(duì)比圖

圖7 實(shí)驗(yàn)一中DQS1與DQS2估計(jì)精度在40%以內(nèi)對(duì)比圖

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

3 結(jié)語

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