車載異構(gòu)網(wǎng)絡(luò)中基于前向時延的多徑傳輸路徑調(diào)度優(yōu)化

趙海濤，陳躍，張?zhí)苽ィ炱嫘牵旌椴?/p>

（1.南京郵電大學(xué)教育部泛在網(wǎng)絡(luò)健康服務(wù)系統(tǒng)工程研究中心，江蘇 南京 210003；2.南京郵電大學(xué)通信與信息工程學(xué)院，江蘇 南京 210003）

1 引言

近年來，隨著工業(yè)技術(shù)和互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，硬件設(shè)備成本大大降低，網(wǎng)絡(luò)設(shè)備普及越來越廣，越來越多的終端設(shè)備裝有多個網(wǎng)絡(luò)接口，同時，裝備在車輛上的網(wǎng)絡(luò)接口也越來越復(fù)雜多樣。新一代的車載網(wǎng)絡(luò)可以實現(xiàn)移動過程中車輛之間的通信，以及低速移動或者靜止時車輛與路邊基礎(chǔ)設(shè)施之間的通信，這些能為車輛提供安全消息傳輸、智能交通信息業(yè)務(wù)、多媒體數(shù)字業(yè)務(wù)等。異構(gòu)網(wǎng)絡(luò)中，多徑傳輸技術(shù)可以同時利用多個網(wǎng)絡(luò)的資源進行傳輸，聚合多個網(wǎng)絡(luò)的傳輸能力[1-3]，有效提高吞吐量和資源利用率，實現(xiàn)負載均衡。多徑傳輸中也面臨很多問題，因為在異構(gòu)網(wǎng)絡(luò)中，為了使用多個路徑進行數(shù)據(jù)傳輸，需要一個分組調(diào)度器，它的職責(zé)是決定通過哪條路徑發(fā)送哪個數(shù)據(jù)分組。另一方面，為了獲得更高的可靠性，數(shù)據(jù)傳輸時需要按照它們在發(fā)送方傳輸?shù)南嗤樞蚨诮邮辗絺魉蛿?shù)據(jù)分組（到上層應(yīng)用程序）。然而，不同的路徑具有不同的特性，如分組丟失率、帶寬、往返時間等，不同路徑發(fā)送的數(shù)據(jù)到達接收端時會發(fā)生亂序，這就需要對數(shù)據(jù)分組重新排序。這些無序分組會被累積在有限的接收緩沖器中，有可能導(dǎo)致緩沖區(qū)阻塞并影響車輛之間的通信性能。所以，需要設(shè)計一種有效的路徑調(diào)度優(yōu)化方法來避免較少的重新排序工作，防止多徑傳輸?shù)男阅芙档汀?/p>

2 研究現(xiàn)狀

多徑傳輸可在協(xié)議棧的多個層實現(xiàn)，不同層的解決方案針對不同的問題，同時受該層特性的影響。因為應(yīng)用層可以很好地適應(yīng)應(yīng)用的特性，所以可以實現(xiàn)更好的業(yè)務(wù)優(yōu)化，但會增加應(yīng)用層的復(fù)雜度。網(wǎng)絡(luò)層對更高層透明，且對現(xiàn)有的基礎(chǔ)設(shè)施兼容性好，但數(shù)據(jù)分組亂序會造成TCP（transmission control protocol）性能下降。由于鏈路層可以獲取信道的信息，因此可以更好地適應(yīng)信道的動態(tài)變化，但鏈路層的解決方案不適應(yīng)于端到端傳播。傳輸層的解決方案可以兼顧不同層的優(yōu)缺點。本文主要針對傳輸層多徑傳輸技術(shù)進行研究，并對數(shù)據(jù)分組亂序問題提出解決方案來提高傳輸性能和資源利用率。

基于數(shù)據(jù)調(diào)度可以解決數(shù)據(jù)分組亂序問題，文獻[4]提出一種基于強化學(xué)習(xí)深度Q 網(wǎng)絡(luò)的數(shù)據(jù)調(diào)度算法，該算法先收集各條路徑的信息，依據(jù)路徑的傳輸效果對各條路徑進行獎懲，動態(tài)地估計各條路徑的傳輸能力，將數(shù)據(jù)盡可能地分配到傳輸能力強的路徑上，但會嚴重降低網(wǎng)絡(luò)利用率。文獻[5]針對路徑時延對接收端亂序的影響，提出了一種基于時延約束的主動數(shù)據(jù)調(diào)度算法，該算法的核心思想是當路徑時延小于設(shè)定的閾值時，則認為路徑可用。但是該算法忽略了分組丟失率和帶寬在實際網(wǎng)絡(luò)中與亂序的制衡關(guān)系，而且也不能保證可用路徑是全部路徑中相互時延差最小的路徑集合。文獻[6]提出了一種多路徑數(shù)據(jù)調(diào)度傳輸解決方案，該方案將單個數(shù)據(jù)流分成不同路徑上的多個單獨流，并在接收主機上將它們組合在一起，但在接收主機上組合時可能會出現(xiàn)拼接錯誤。文獻[7]提出了一種改進的數(shù)據(jù)調(diào)度算法，在計算中加入分組丟失率這個參數(shù)，對各個路徑的傳輸數(shù)據(jù)大小進行建模，通過仿真結(jié)果可知，該算法提高了吞吐量，但其不能適應(yīng)網(wǎng)絡(luò)的動態(tài)變化。文獻[8]提出了Kim-2012 算法，該算法通過發(fā)送完數(shù)據(jù)分組并收到該數(shù)據(jù)分組的確認后，然后基于往返時間（RTT,round-trip time）在每條路徑上調(diào)度數(shù)據(jù)分組。該算法使用固定的時間（）作為前向時延的估計，如圖1 所示，但是，由于前向時延和后向時延不對稱，因此這不是一個好的估計。

圖1 前向時延和后向時延說明

基于路徑調(diào)度可以解決數(shù)據(jù)分組亂序問題，文獻[9]針對目前多路徑并行傳輸過程中由于傳輸路徑質(zhì)量的差異導(dǎo)致網(wǎng)絡(luò)傳輸性能整體下降的問題，提出一種多路徑并行傳輸?shù)穆窂絼討B(tài)決策（CMT-DS,concurrent multipath transfer-dynamic selection）方法。該方法考慮到路徑傳輸質(zhì)量對網(wǎng)絡(luò)吞吐量的影響，通過測量時延、抖動、分組丟失率和緩存占用比這4 個路徑傳輸屬性，擬合成路徑質(zhì)量的關(guān)聯(lián)函數(shù)，根據(jù)該關(guān)聯(lián)函數(shù)對路徑進行動態(tài)選擇，從而實現(xiàn)動態(tài)選擇路徑的功能，以達到最理想的傳輸效果，但在室外環(huán)境或路徑更多時效果明顯降低。文獻[10]提出2 種新穎的基于塊估計調(diào)度程序和最短傳輸時間優(yōu)先的調(diào)度技術(shù)，仿真結(jié)果表明，該技術(shù)可以降低交互時延，但對提高吞吐量效果不顯著。文獻[11]提出根據(jù)應(yīng)用程序的工作量動態(tài)調(diào)整路徑解決方案，該方案首先利用TCP 建模的思想來估計正在調(diào)度的路徑上的等待時間以及同時在其他路徑上發(fā)送的數(shù)據(jù)量，然后以減少完成的目標為目的，定期確定用于某些應(yīng)用程序的路徑集，但其實現(xiàn)起來較復(fù)雜。文獻[12]提出一種基于FIFO（first input first output）的車道擁堵緩解策略，仿真實驗表明，分批策略可以使滑行流出量增加25%以上，但該方法的實時性還有待驗證。文獻[13]提出一種調(diào)度多條路徑的方法，該方法先估計亂序的數(shù)據(jù)分組，提前預(yù)測緩沖區(qū)阻塞，并阻止在性能差的路徑上傳輸數(shù)據(jù)分組。但該方法選擇路徑時僅考慮分組丟失率和帶寬，因此，選擇路徑時會出現(xiàn)偏差。文獻[14]提出一種無線多跳網(wǎng)絡(luò)環(huán)境下并行多徑傳輸中的公平機制，使用Q 學(xué)習(xí)機制來獲得網(wǎng)絡(luò)中的動態(tài)信息，根據(jù)所獲得的動態(tài)信息來選擇最佳路徑，以獲得更高的帶寬利用率并提高網(wǎng)絡(luò)公平性指數(shù)，從而有效均衡流量并提高服務(wù)質(zhì)量，但準確率還有待提高。文獻[15]提出一種基于MPSCTP（multipath stream control transmission protocal）的優(yōu)化分流技術(shù)，并提出使用一種時延不敏感的優(yōu)化的啟發(fā)式算法來研究多路徑選擇的策略，提高了對MPSCTP 中確認損耗的敏感性，從而提高了網(wǎng)絡(luò)利用率，并為終端用戶提供更好的服務(wù)質(zhì)量，但是其內(nèi)存空間占用較大，在實際應(yīng)用中不夠方便。

針對上述在解決多徑傳輸中數(shù)據(jù)分組亂序的問題，本文提出了車載異構(gòu)網(wǎng)絡(luò)中基于前向時延的多徑傳輸路徑調(diào)度優(yōu)化方案。該方案根據(jù)前向路徑之間的估計時延和帶寬差異來調(diào)度分組，可以減少重新排序工作，從而提高系統(tǒng)吞吐量。

3 基于前向時延的路徑調(diào)度算法

3.1 估計前向時延差異

本文規(guī)定前向時延為從發(fā)送方到接收方的時延，后向時延為從接收方到發(fā)送方的時延。前向時延加后向時延就是往返時間（RTT）（如圖1 所示）。因為發(fā)送器和接收器的時鐘一般存在差異，所以估計前向時延在實際中并不是微不足道的。然而，從本節(jié)證明中可以看出，即使發(fā)送器和接收器的時鐘存在差異，也可以估計得到路徑之間的前向時延差異。

時延差計算如圖2 所示，發(fā)送方通過2 條不同的路徑向接收方發(fā)送2 個分組。S 代表發(fā)送方，R代表接收方，發(fā)送方在時間經(jīng)路徑1 將分組1 發(fā)送到接收方，分組1 的到達時間為，發(fā)送方在時間將分組2 經(jīng)路徑2 發(fā)送到接收方，分組2 的到達時間為。然后利用式(1)算出2 個數(shù)據(jù)分組的發(fā)送時間差Δs，利用式(2)得到2 個數(shù)據(jù)分組的接收時間差Δr，令ΔT=clkS-clkR 為發(fā)送方和接收方之間的時鐘差，通過式(3)算出數(shù)據(jù)分組1 的前向時延。同理，利用式(4)算出數(shù)據(jù)分組2 的前向時延。最后通過式(5)得到2 條路徑之間的前向時延差。

圖2 時延差計算

3.2 調(diào)度數(shù)據(jù)分組

本節(jié)首先需要找到前向時延最短的路徑。其中P={P1,P2,…,PN}是MPTCP 傳輸數(shù)據(jù)路徑的集合，前向時延最短的pi可以由圖3 中的算法確定。

該算法的主要思想是首先輸入一條路徑pi，然后依次計算該路徑與其他所有路徑pj之間的前向時延差Δpi pj，2 條路徑之間的差異必須是一個非正數(shù)，最后計算得到最大的Sum 值對應(yīng)的路徑就是本文要找的路徑pi。

得到前向時延最短的路徑后，發(fā)送方就將調(diào)度數(shù)據(jù)分組。仿真實驗時假設(shè)發(fā)送方使用子流之間共享的緩沖區(qū)，并且應(yīng)用層的數(shù)據(jù)足夠大來填充緩沖區(qū)。將發(fā)送緩沖區(qū)中的數(shù)據(jù)分區(qū)為數(shù)據(jù)分組，每個數(shù)據(jù)分組的大小等于TCP 路徑的MSS（maximum segment size）。然后，利用本文提出的算法調(diào)度程序在前向時延小的路徑上發(fā)送序列號低的數(shù)據(jù)分組。當決定選擇路徑i上的子流來傳輸數(shù)據(jù)之前，算法調(diào)度程序?qū)⑾雀鶕?jù)式(6)計算出數(shù)值idxi，然后緩沖區(qū)中idxi處對應(yīng)的數(shù)據(jù)分組就將被傳輸。

圖3 系統(tǒng)算法流程

其中，xi代表路徑i的平均傳輸能力（B/s），MSS代表消息段大小，代表路徑i的歸一化速率，因此，乘積可以被解釋為路徑i和i*之間的“帶寬?時延乘積差”。因此，在數(shù)據(jù)分組到達路徑i之前，路徑i*上有足夠的空間來發(fā)送分組，在路徑i上發(fā)送的分組應(yīng)該在式(6)計算得出的分組之后。在發(fā)送一個數(shù)據(jù)分組之后，較大的idxi對應(yīng)的數(shù)據(jù)分組將被移位送到緩沖區(qū)，如圖4 所示。本文的分組調(diào)度算法原理是生成的數(shù)據(jù)分組先被存儲在發(fā)送緩沖器中，然后只有當用于發(fā)送數(shù)據(jù)的窗口打開時才被分配給子流。

圖4 根據(jù)前向時延差異分配數(shù)據(jù)分組

4 仿真結(jié)果與分析

本節(jié)評估了FDPS（forward delay-based packet scheduling）算法的性能，并與MPTCP[6]、FIFO[12]（具有最低RTT 的先進先出）和Kim-2012[15]的性能進行比較，重點比較的是重新排序緩沖區(qū)占用密度（RBD,reorder-buffer-occupancy density）和吞吐量這2 個參數(shù)。通過仿真得到不同參數(shù)下4 種算法的RBD 和吞吐量并進行比較。

本文的評估基于圖5 所示的拓撲結(jié)構(gòu)，并在NS-3 上進行了模擬。表1 給出了各種網(wǎng)絡(luò)條件下模擬實驗的參數(shù)。

圖5 仿真路徑拓撲

表1 仿真參數(shù)

4.1 雙路徑傳輸

本文假設(shè)數(shù)據(jù)流在沒有后臺流量的2 個單獨的路徑上傳輸。表1 是仿真參數(shù)，表2 是仿真時2 條路徑的基本參數(shù)。如圖6 所示，本文首先按照表1調(diào)整好實驗參數(shù)，然后規(guī)定路徑A 帶寬為5 Mbit/s，時延為10 ms；路徑B 帶寬為5 Mbit/s，帶寬為10 ms。通過圖6 可以看出，即使2 條路徑相同，所有算法仍然會發(fā)生無序分組現(xiàn)象。但是，4 種算法的性能仍有很大的差異，F(xiàn)IFO 和MPTCP 的表現(xiàn)是最差的，Kim-2012 的性能稍微比前兩者表現(xiàn)得要好。與其他算法相比，F(xiàn)DPS 獲得了最佳性能，其RBD 集中在零點附近。

接下來，在條件2 下進行仿真，結(jié)果如圖7 所示。規(guī)定路徑A 的帶寬為5 Mbit/s，時延為10 ms；路徑B 的帶寬為5 Mbit/s，時延為25 ms，可以看到，此次仿真路徑B 的時延增加。FIFO 和MPTCP算法的RBD 比圖6 中的性能顯著降低。在這種情況下，Kim-2012 依然比FIFO 和MPTCP 表現(xiàn)得要好，但是從圖7 中可以看出FDPS 的性能仍然是最好的，其RBD 依然集中在零點附近。

圖8 是在條件3 下進行的仿真。規(guī)定路徑A 的帶寬為4 Mbit/s，時延為10 ms；路徑2 的帶寬為8 Mbit/s，時延為30 ms。此次仿真是在具有不同時延和帶寬的2 條路徑上進行的。從圖8 中可以看出，Kim-2012的性能比FIFO 和MPTCP 的性能表現(xiàn)得要好，但FDPS 的表現(xiàn)還是最好的，F(xiàn)DPS 的分組重新排序密度密集地集中在零點附近，而其他的則比較分散。

表2 仿真時2 條路徑的基本參數(shù)

4.2 具有后臺流量的雙路徑傳輸

實際上，網(wǎng)絡(luò)中的TCP 流經(jīng)常與其他前向或后向流共享帶寬，為了評估在此類路徑上發(fā)送數(shù)據(jù)分組時數(shù)據(jù)分組調(diào)度算法的效率，本文進行了具有后臺流量的雙路徑傳輸仿真實驗，此實驗路徑參數(shù)按表2 中的條件2 進行配置。從圖9 可以看出，因為后臺流使RTT 估算的精確度降低，所以所有算法性能都大大降低，且MPTCP 和Kim-2012 的表現(xiàn)差于FIFO，因為前兩者對時變更敏感，但FDPS 的性能表現(xiàn)仍然是最好的。

4.3 3 條路徑傳輸

圖10 是本文在具有后臺流量3 條相同的路徑上進行的仿真實驗。可以看到，所有算法性能都變差了。這表明，當并發(fā)路徑數(shù)增加時，重新排序問題變得更加嚴重，但是，在這種情況下，F(xiàn)DPS 仍然表現(xiàn)最佳。

4.4 吞吐量比較

圖6 條件1 下沒有后臺流量的雙路徑傳輸仿真實驗

圖7 條件2 下沒有后臺流量的雙路徑傳輸仿真實驗

圖9 具有后臺流量的雙路徑傳輸仿真實驗

圖10 具有后臺流量3 條路徑傳輸仿真實驗

圖11 是相同條件下4 種算法的吞吐量仿真。從圖11 中可以看出，MPTCP 吞吐量在剛開始時上升的趨勢很快，但很快就開始下降然后趨于平緩，并且趨于平緩后MPTCP 吞吐量表現(xiàn)是最差的，另外，Kim-2012 和MPTCP、FIFO 的曲線走勢基本相同，但Kim-2012 的吞吐量總體比FIFO 和MPTCP 表現(xiàn)得要好，F(xiàn)DPS 的吞吐量曲線是走勢最好的，剛開始上升很快，一段時間后趨于平緩后，代表FDPS 吞吐量的曲線依然在其他3 條曲線的上方。綜合4.1～4.3 節(jié)考慮分析，因為相同條件下FDPS 始終獲得最優(yōu)的重新排序緩沖區(qū)占用密度，數(shù)據(jù)分組亂序造成緩沖區(qū)擁塞的可能性最低，從而系統(tǒng)性能處于最優(yōu)狀態(tài)，所以FDPS 獲得了最優(yōu)的吞吐量表現(xiàn)。

5 結(jié)束語

本文針對多徑傳輸中數(shù)據(jù)分組亂序問題，提出了一種基于前向時延的多徑傳輸路徑調(diào)度優(yōu)化算法，所提算法在不同條件仿真實驗中始終獲得最佳的緩沖器占用率，這表明在各種網(wǎng)絡(luò)條件下所提算法的性能表現(xiàn)都很穩(wěn)定。在本文的模擬中，使用不限大小的重新排序緩沖區(qū)，因為本文希望捕獲接收器上的所有數(shù)據(jù)分組以進行正確的RBD 和吞吐量測量。由于所提算法與其他算法相比都得到了最佳的重新排序緩沖器占用率，因此如果使用所提算法，則有限重新排序緩沖器大小的影響將是最小的，可以降低亂序問題提高吞吐量。針對本文中在數(shù)據(jù)分組調(diào)度方面仍然存在的問題，下一步的工作計劃是設(shè)計更加合理的數(shù)據(jù)調(diào)度算法，進一步提升多路徑傳輸性能。

圖11 相同條件下4 種算法的吞吐量仿真