王益亮，姜勝明，曹 軍

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

機(jī)會網(wǎng)絡(luò)剩余路徑投遞時間估計方法性能分析*

王益亮，姜勝明，曹 軍

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

差分隊列服務(wù)是一種以包為粒度的隊列調(diào)度算法，其剩余路徑投遞時間估計方法的好壞，將顯著影響其在機(jī)會網(wǎng)絡(luò)這種鏈路連通性低、拓?fù)渥兓l繁環(huán)境下的性能?，F(xiàn)有的剩余路徑投遞時間估計方法尚未驗證其在機(jī)會網(wǎng)絡(luò)中的性能。文章比較差分隊列服務(wù)與最早截止期優(yōu)先算法，通過仿真測試了一種基于歷史信息有效性的剩余路徑投遞時間估計方法在機(jī)會網(wǎng)絡(luò)場景中的性能。實驗證明應(yīng)用該方法能有效地提高傳輸成功率，也導(dǎo)致平均端到端時延的變化幅度更大。

差分隊列服務(wù)；機(jī)會網(wǎng)絡(luò)；剩余路徑投遞時間；最早截止期優(yōu)先

0 引言

在機(jī)會網(wǎng)絡(luò)中，為實現(xiàn)包粒度的服務(wù)質(zhì)量，文獻(xiàn)[1]提出差分隊列服務(wù)(Differentiated Queueing Service, DQS)算法。DQS的設(shè)計基于以下前提：網(wǎng)絡(luò)中的所有數(shù)據(jù)分組都來自于某種類型的應(yīng)用，每種類型的應(yīng)用都具有一個特定的最大端到端時延，即這種類型的應(yīng)用中所有數(shù)據(jù)分組在鏈路上的最長生存時間，作為該數(shù)據(jù)分組的服務(wù)質(zhì)量(Quality of Service, QoS)需求。所以，每當(dāng)節(jié)點新收到一個數(shù)據(jù)分組，首先需要檢查分組是否仍在其生存時間內(nèi)，如果不在，節(jié)點可立即丟棄該數(shù)據(jù)分組，因為這個數(shù)據(jù)分組已經(jīng)無法滿足其自身的QoS需求，丟棄該分組可以節(jié)約網(wǎng)絡(luò)資源。如果在，該算法就要估計該分組在剩余路徑上的傳播時延，即估計剩余路徑投遞時間，再結(jié)合數(shù)據(jù)分組自身生存時間的QoS需求，來決定該分組可容忍的最遲離開本節(jié)點的時間。然后該時間將被視為DQS調(diào)度算法所參考轉(zhuǎn)發(fā)優(yōu)先級的指標(biāo)，根據(jù)最遲離開時刻從早到晚的原則將數(shù)據(jù)分組插入到隊列中相應(yīng)位置。

因此，剩余路徑投遞時間估計方法的性能狀況對DQS有重要意義。文獻(xiàn)[2]提出了幾種應(yīng)用于DQS的方法，卻缺乏性能方面的驗證，不能夠準(zhǔn)確衡量方法在機(jī)會網(wǎng)絡(luò)環(huán)境中的性能表現(xiàn)。本文將文獻(xiàn)[2]提出的方法應(yīng)用于DQS，并對比改進(jìn)后的最早截止期優(yōu)先(Earliest Deadline First, EDF)算法進(jìn)行仿真驗證并分析其性能。

1 機(jī)會網(wǎng)絡(luò)與場景設(shè)計簡介

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

而當(dāng)前在機(jī)會網(wǎng)絡(luò)路由協(xié)議[4]方面的研究進(jìn)展緩慢，本文將使用AODV路由協(xié)議：以節(jié)點移動性以及節(jié)點數(shù)量的變化來模擬鏈路連通性低、拓?fù)渥兓l繁的機(jī)會網(wǎng)絡(luò)場景。以節(jié)點自身的隊列存儲數(shù)據(jù)包并攜帶數(shù)據(jù)包在移動中尋找下一跳的方式來模擬機(jī)會網(wǎng)絡(luò)“存儲-攜帶-轉(zhuǎn)發(fā)”場景。以不同端到端時延的數(shù)據(jù)包來模擬機(jī)會網(wǎng)絡(luò)中不同的應(yīng)用業(yè)務(wù)類型。

2 相關(guān)方法與實現(xiàn)介紹

2.1 差分隊列服務(wù)相關(guān)方法

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

該方法是根據(jù)一條信息的登記時間計算其在當(dāng)前時間的信息有效性，歷史信息有效性是指在當(dāng)前時間，一個歷史信息用于預(yù)測或估計時所具有的有用價值。信息有效性的數(shù)值范圍是(0,1)，自信息登記時刻起，其有效性每經(jīng)過一個半衰期時間減半。

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

(1)

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

(2)

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

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

2.1.2 無需發(fā)送順向探測包的剩余路徑投遞時間估計

(3)

其中，τd,j代表保存在該節(jié)點上的從反向路徑d節(jié)點到本節(jié)點的第j個歷史實際投遞時間，vd,j代表反向路徑歷史實際投遞時間τd,j根據(jù)2.1.1節(jié)方法所計算的信息有效性。

在實現(xiàn)過程中，數(shù)據(jù)分組需在頭部攜帶兩個字段：該數(shù)據(jù)分組的最大端到端時延與在源節(jié)點的生成時間。數(shù)據(jù)分組離開時間等于數(shù)據(jù)分組生成時間加上其最大端到端時延，并減去估計的剩余路徑時間，由此，DQS判斷數(shù)據(jù)分組的緊急程度考慮到了數(shù)據(jù)分組的端到端時延需求。節(jié)點依據(jù)數(shù)據(jù)分組的離開時間進(jìn)入隊列，使得緊急的數(shù)據(jù)分組排在隊列前面，優(yōu)先轉(zhuǎn)發(fā)。

2.2 最早截止期優(yōu)先調(diào)度算法

EDF[5]是一種動態(tài)優(yōu)先級調(diào)度算法，基本原理是：將所有的業(yè)務(wù)分成不同的流，依據(jù)數(shù)據(jù)包所屬的業(yè)務(wù)類型，在每個數(shù)據(jù)包到達(dá)時間的基礎(chǔ)上增加一個靜態(tài)時間期限值，調(diào)度器則以此值作為依據(jù)，每次發(fā)送該值最小的數(shù)據(jù)包。業(yè)務(wù)流的優(yōu)先級越高，相應(yīng)的數(shù)據(jù)包的期限值越小，得到優(yōu)先服務(wù)的概率也就越大。

在本實驗中，所有數(shù)據(jù)分組都包含了其最大端到端時延要求，為體現(xiàn)公平性，同時根據(jù)文獻(xiàn)[6]，對EDF進(jìn)行有效的隊列管理，對網(wǎng)絡(luò)性能的提升具有相當(dāng)大的作用。于是對EDF進(jìn)行改進(jìn)，添加了緩存準(zhǔn)入控制，丟棄超出時延的分組，提高了網(wǎng)絡(luò)利用率。

在實現(xiàn)的過程中，數(shù)據(jù)分組的本地存活時間為其端到端時延值的一半，這個本地存活時間即作為一個靜態(tài)時間期限，數(shù)據(jù)分組離開時間等于當(dāng)前時間加上本地存活時間。節(jié)點依據(jù)數(shù)據(jù)分組離開時間加入隊列。

需要說明的是，這時數(shù)據(jù)分組的端到端時延值僅代表不同類型的業(yè)務(wù)流量，EDF并沒有考慮數(shù)據(jù)分組的端到端時延需求，這也是與DQS相關(guān)方法差異明顯的地方。

3 仿真和結(jié)果分析

3.1 仿真場景及參數(shù)

本文所有實驗使用的仿真平臺是SNT公司所開發(fā)的EXATA。通過考察傳輸成功率、平均傳輸時延來測試DQS與EDF在不同場景下的性能表現(xiàn)。其中，傳輸成功率按如下公式計算：

(4)

平均傳輸時延按下式計算：

(5)

本文分3個場景，場景基本參數(shù)如表1所示。

表1 場景基本參數(shù)

場景1：考察DQS與EDF在節(jié)點移動速度變化時，其速度與傳輸成功率和平均傳輸時延的關(guān)系。表2為節(jié)點移動速度變化參數(shù)表。

表2 節(jié)點移動速度變化參數(shù)表

場景2：考察DQS與EDF在節(jié)點數(shù)量變化時，其節(jié)點數(shù)量與傳輸成功率和平均傳輸時延的關(guān)系。節(jié)點數(shù)量變化參數(shù)如表3。

表3 節(jié)點數(shù)量變化參數(shù)表

場景3：考察DQS與EDF在節(jié)點發(fā)送不同端到端時延的數(shù)據(jù)包時，其端到端時延值與傳輸成功率和平均傳輸時延的關(guān)系。相關(guān)參數(shù)如表4所示。

表4 節(jié)點發(fā)送不同端到端時延的數(shù)據(jù)包參數(shù)表

3.2 仿真結(jié)果

如圖1，在DQS與EDF策略下傳輸成功率都是先上升后下降的趨勢，DQS的傳輸成功率相對于EDF略有提升，當(dāng)節(jié)點移動速度為2 m/s～6 m/s時，傳輸成功率處于上升階段，提升最為明顯。當(dāng)速度進(jìn)一步增加時，網(wǎng)絡(luò)動態(tài)性增強(qiáng)，拓?fù)鋭×易兓?，DQS性能下降明顯，且性能優(yōu)勢不明顯。但相對于EDF，DQS依然有良好的性能。

圖1 移動速度與傳輸成功率的關(guān)系

如圖2，DQS與EDF相比，DQS的平均傳輸時延變化范圍要略大一些，并且在多數(shù)情況下略高于EDF。這是由于DQS考慮數(shù)據(jù)分組端到端的時延特征，能夠?qū)Ωo急的數(shù)據(jù)分組提供優(yōu)先級更高的服務(wù)，從而相對緊急程度較低的分組可在隊列中停留更久一點。平均傳輸時延呈現(xiàn)出先增大再減小的特征，在速度較小時，節(jié)點通信機(jī)會少，隨著速度的增加，通信機(jī)會增多，節(jié)點隊列中緩存的數(shù)據(jù)分組數(shù)增大，使得隊列時延增大，從而一定程度上增大了平均傳輸時延，但是速度進(jìn)一步增大，拓?fù)渥兓瘎×?，隊列中的分組無法在短暫的通信時間內(nèi)轉(zhuǎn)發(fā)，使得大量分組未能被目的節(jié)點成功接收。

圖2 移動速度與平均傳輸時延的關(guān)系

如圖3，同樣大小的場景，隨著節(jié)點數(shù)量的增加節(jié)點密度自然會增大，此時網(wǎng)絡(luò)中的傳輸成功率提高。DQS與EDF相比傳輸成功率略有提高，節(jié)點數(shù)由少到多，DQS優(yōu)勢呈上升趨勢，在節(jié)點數(shù)為21個時，DQS與EDF相比優(yōu)勢最為明顯。但是當(dāng)節(jié)點個數(shù)更多時，DQS優(yōu)勢開始下降。最初節(jié)點數(shù)量較少時，節(jié)點相遇機(jī)會較少，無法滿足數(shù)據(jù)分組的端到端時延需求。隨著節(jié)點數(shù)量增多，通信質(zhì)量得到改善，傳輸成功率持續(xù)提高，但是在節(jié)點密度較大時，無線信道沖突加劇。由于使用的是AODV路由協(xié)議，路由變動頻繁，這時難以體現(xiàn)機(jī)會網(wǎng)絡(luò)的場景。文獻(xiàn)[7]指出，如果在節(jié)點間不依賴完整的傳播路徑，而是機(jī)會性地選擇下一跳，能提升網(wǎng)絡(luò)分組最終到達(dá)目標(biāo)節(jié)點的概率。

圖3 節(jié)點數(shù)量與傳輸成功率的關(guān)系

如圖4，節(jié)點數(shù)量與平均傳輸時延的關(guān)系不是特別明顯，總體而言，DQS平均傳輸時延的波動范圍要大一些。結(jié)合圖3，大致上，傳輸成功率提高的同時，平均傳輸時延也在增大。節(jié)點數(shù)量的增加增大了節(jié)點的相遇機(jī)會，提高了通信質(zhì)量，隊列利用率逐步提高，當(dāng)節(jié)點較密集時，平均傳輸時延的增大幅度較小，而傳輸成功率增大幅度較大。

圖4 節(jié)點數(shù)量與平均傳輸時延的關(guān)系

如圖5，文獻(xiàn)[8]通過理論推導(dǎo)和實驗證明了當(dāng)允許網(wǎng)絡(luò)節(jié)點移動時，在增加數(shù)據(jù)分組傳輸時延的前提下，可以提高整個網(wǎng)絡(luò)中的傳輸成功率。當(dāng)數(shù)據(jù)分組平均端到端時延值為50 ms～200 ms時，其傳輸成功率顯著提高；當(dāng)數(shù)據(jù)分組平均端到端時延值繼續(xù)增大，其傳輸成功率提升幅度減小；數(shù)據(jù)分組平均端到端時延值為300 ms時，DQS相對于EDF取得最大優(yōu)勢。當(dāng)數(shù)據(jù)分組的平均端到端時延較小時，大量的分組因無法滿足其平均端到端時延需求而被中間節(jié)點丟棄，隨著數(shù)據(jù)分組平均端到端時延值增大，丟棄量下降，隊列利用率提高，提高了傳輸成功率。但是，不斷加大數(shù)據(jù)分組的平均端到端時延對傳輸成功率的提升作用，也會隨著網(wǎng)絡(luò)瓶頸的到來而受限。

圖5 平均端到端時延與傳輸成功率的關(guān)系

如圖6，增大數(shù)據(jù)分組的平均端到端時延，有更多的數(shù)據(jù)分組不再因其最大生存時間到期而被丟棄，會繼續(xù)等待轉(zhuǎn)發(fā)機(jī)會，因此網(wǎng)絡(luò)的平均傳輸時延增大了。DQS與EDF相比，其平均傳輸時延普遍較大，平均傳輸時延范圍要更大一些。DQS考慮到數(shù)據(jù)分組的端到端時延需求，對更緊急的數(shù)據(jù)分組提供更優(yōu)先的服務(wù)，比如，盡管有的數(shù)據(jù)分組其端到端時延值較小，但是其剩余路徑時間短，DQS并不一定為其提供優(yōu)先服務(wù)，可能使其在隊列中停留更久一點，以便為更緊急的數(shù)據(jù)分組提供服務(wù)，因此，DQS提高了傳輸成功率，也一定程度上增大了平均傳輸時延。

圖6 平均端到端時延與平均傳輸時延的關(guān)系

4 結(jié)論

通過仿真實驗，應(yīng)用了基于半衰期的歷史信息有效性計算方法與無需發(fā)送順向探測包的剩余路徑投遞時間估計方法的DQS，對比改進(jìn)后的EDF，傳輸成功率有效提高，傳輸時延變化范圍更大，并有增大傳輸時延的趨勢。

本實驗中，由于使用的是AODV路由協(xié)議，使得難以高效適應(yīng)機(jī)會網(wǎng)絡(luò)場景，DQS性能受到一定影響。實驗中半衰期值是由場景全局參數(shù)計算得來，總體而言，有良好的表現(xiàn)，但是在仿真過程中發(fā)現(xiàn)場景中的節(jié)點時而密集在一起，時而分散造成鏈路斷開，使得基于全局參數(shù)計算的半衰期值不能很好地體現(xiàn)場景的這種變化。所以，為進(jìn)一步提高DQS性能與精確度，一個可以基于場景自適應(yīng)的半衰期時間獲取方式應(yīng)是一個改進(jìn)的方向。

[1] Jiang Shengming. Granular differentiated queueing services for QoS: structure and cost model[J]. Acm Sigcomm Computer Communication Review, 2005, 35(2):13-22.

[2] 錢彥臻，姜勝明，楊方，等.一種用于差分隊列服務(wù)系統(tǒng)的剩余路徑投遞時間估計方法：中國， 10242993.2[P].2016-09-28.

[3] 熊永平，孫利民，牛建偉，等. 機(jī)會網(wǎng)絡(luò)[J]. 軟件學(xué)報,2009, 20(1):124-137.

[4] 任智，黃勇，陳建斌．機(jī)會網(wǎng)絡(luò)路由協(xié)議[J]．計算機(jī)應(yīng)用，2010, 30(3):723-728.

[5] GUERIN R, PERIS V. Quality-of-service in packet networks: basic mechanisms and directions [J]. Computer Networks, 1999, 31(3): 169-189.

[6] GEORGIADIS L, GUéRIN R, PAREKH A. Optimal multiplexing on a single link: delay and buffer requirements[J]. IEEE Transactions on Information Theory, 1997, 43(5):1518-1535.

[7] PELUSI L, PASSARELLA A, CONTI M. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[J].Communications Magazine, 2006,44(11):134-141.

[8] GROSSGLAUSER M, TSE D N C. Mobility increases the capacity of ad hoc wireless networks[J]. Proceedings of IEEE INFOCOM, 2001, 3(4): 477-486.

The performance analysis of the estimating of the journey time over theremaining path in opportunistic network

Wang Yiliang, Jiang Shengming, Cao Jun

(School of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

Differentiated Queueing Service (DQS) is a kind of packet-granulared queue scheduling algorithm, how good of its way to estimate the journey time over the remaining path will have a significant impact in the opportunistic network in which the network communication opportunity is very scarce. The existing way to estimate the journey time over the remaining path has not tested the performance in opportunistic network. In this paper, by comparing DQS with the Earliest Deadline First (EDF), and test the performance of a way to estimate the journey time over the remaining path based on value of history information in the scene of opportunistic network. It is proved that the way can remarkably improve the delivery ratio meanwhile make the average delivery delay more volatile or larger.

Differentiated Queueing Service(DQS); opportunistic network; the journey time over the remaining path; Earliest Deadline First (EDF)

國家自然科學(xué)基金(61472237)

TP393

A

10.19358/j.issn.1674- 7720.2017.15.019

王益亮，姜勝明，曹軍.機(jī)會網(wǎng)絡(luò)剩余路徑投遞時間估計方法性能分析[J].微型機(jī)與應(yīng)用，2017,36(15)：65-68，72.

2017-02-08)

王益亮(1992-)，男，碩士研究生，主要研究方向：無線網(wǎng)絡(luò)協(xié)議。

姜勝明(1964-)，男，博士，教授，主要研究方向：通信網(wǎng)絡(luò)結(jié)構(gòu)、協(xié)議和算法等。

曹軍(1990-)，男，碩士研究生，主要研究方向：通信網(wǎng)絡(luò)結(jié)構(gòu)。