機會網絡剩余路徑投遞時間估計方法性能分析*

王益亮，姜勝明，曹 軍

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

機會網絡剩余路徑投遞時間估計方法性能分析*

王益亮，姜勝明，曹 軍

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

差分隊列服務是一種以包為粒度的隊列調度算法，其剩余路徑投遞時間估計方法的好壞，將顯著影響其在機會網絡這種鏈路連通性低、拓撲變化頻繁環境下的性能。現有的剩余路徑投遞時間估計方法尚未驗證其在機會網絡中的性能。文章比較差分隊列服務與最早截止期優先算法，通過仿真測試了一種基于歷史信息有效性的剩余路徑投遞時間估計方法在機會網絡場景中的性能。實驗證明應用該方法能有效地提高傳輸成功率，也導致平均端到端時延的變化幅度更大。

差分隊列服務；機會網絡；剩余路徑投遞時間；最早截止期優先

0 引言

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

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

1 機會網絡與場景設計簡介

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

而當前在機會網絡路由協議[4]方面的研究進展緩慢，本文將使用AODV路由協議：以節點移動性以及節點數量的變化來模擬鏈路連通性低、拓撲變化頻繁的機會網絡場景。以節點自身的隊列存儲數據包并攜帶數據包在移動中尋找下一跳的方式來模擬機會網絡“存儲-攜帶-轉發”場景。以不同端到端時延的數據包來模擬機會網絡中不同的應用業務類型。

2 相關方法與實現介紹

2.1 差分隊列服務相關方法

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

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

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

(1)

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

(2)

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

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

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

(3)

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

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

2.2 最早截止期優先調度算法

EDF[5]是一種動態優先級調度算法，基本原理是：將所有的業務分成不同的流，依據數據包所屬的業務類型，在每個數據包到達時間的基礎上增加一個靜態時間期限值，調度器則以此值作為依據，每次發送該值最小的數據包。業務流的優先級越高，相應的數據包的期限值越小，得到優先服務的概率也就越大。

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

在實現的過程中，數據分組的本地存活時間為其端到端時延值的一半，這個本地存活時間即作為一個靜態時間期限，數據分組離開時間等于當前時間加上本地存活時間。節點依據數據分組離開時間加入隊列。

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

3 仿真和結果分析

3.1 仿真場景及參數

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

(4)

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

(5)

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

表1 場景基本參數

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

表2 節點移動速度變化參數表

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

表3 節點數量變化參數表

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

表4 節點發送不同端到端時延的數據包參數表

3.2 仿真結果

如圖1，在DQS與EDF策略下傳輸成功率都是先上升后下降的趨勢，DQS的傳輸成功率相對于EDF略有提升，當節點移動速度為2 m/s～6 m/s時，傳輸成功率處于上升階段，提升最為明顯。當速度進一步增加時，網絡動態性增強，拓撲劇烈變化，DQS性能下降明顯，且性能優勢不明顯。但相對于EDF，DQS依然有良好的性能。

圖1 移動速度與傳輸成功率的關系

如圖2，DQS與EDF相比，DQS的平均傳輸時延變化范圍要略大一些，并且在多數情況下略高于EDF。這是由于DQS考慮數據分組端到端的時延特征，能夠對更緊急的數據分組提供優先級更高的服務，從而相對緊急程度較低的分組可在隊列中停留更久一點。平均傳輸時延呈現出先增大再減小的特征，在速度較小時，節點通信機會少，隨著速度的增加，通信機會增多，節點隊列中緩存的數據分組數增大，使得隊列時延增大，從而一定程度上增大了平均傳輸時延，但是速度進一步增大，拓撲變化劇烈，隊列中的分組無法在短暫的通信時間內轉發，使得大量分組未能被目的節點成功接收。

圖2 移動速度與平均傳輸時延的關系

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

圖3 節點數量與傳輸成功率的關系

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

圖4 節點數量與平均傳輸時延的關系

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

圖5 平均端到端時延與傳輸成功率的關系

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

圖6 平均端到端時延與平均傳輸時延的關系

4 結論

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

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

[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] 錢彥臻，姜勝明，楊方，等.一種用于差分隊列服務系統的剩余路徑投遞時間估計方法：中國， 10242993.2[P].2016-09-28.

[3] 熊永平，孫利民，牛建偉，等. 機會網絡[J]. 軟件學報,2009, 20(1):124-137.

[4] 任智，黃勇，陳建斌．機會網絡路由協議[J]．計算機應用，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)

國家自然科學基金(61472237)

TP393

A

10.19358/j.issn.1674- 7720.2017.15.019

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

2017-02-08)

王益亮(1992-)，男，碩士研究生，主要研究方向：無線網絡協議。

姜勝明(1964-)，男，博士，教授，主要研究方向：通信網絡結構、協議和算法等。

曹軍(1990-)，男，碩士研究生，主要研究方向：通信網絡結構。