民航空地通信中的多鏈路數(shù)據(jù)分配算法*

余 翔,程士龍,段思睿,王子怡

(重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065)

0 引 言

通信技術(shù)促進(jìn)著我國(guó)民航通信業(yè)的迅速發(fā)展,據(jù)中國(guó)民用航空局?jǐn)?shù)據(jù)顯示,民航市場(chǎng)逐年呈現(xiàn)增長(zhǎng)趨勢(shì),增加的航空旅客通信業(yè)務(wù)對(duì)維護(hù)空地通信的完整性提出了更高的要求。在空地通信過(guò)程中不可能只提供一種空地通信服務(wù)鏈路,需要根據(jù)用戶需求和當(dāng)前的飛機(jī)所處環(huán)境自動(dòng)選擇通信鏈路。

當(dāng)前民航通信架構(gòu)主要有兩種:一是空對(duì)地寬帶通信(Air to Ground,ATG),通過(guò)地面基站與飛機(jī)上的ATG專用設(shè)備建立連接,組成ATG鏈路與地面進(jìn)行信息交換,但是飛機(jī)卻不能偏移基站的信號(hào)覆蓋范圍;二是寬帶衛(wèi)星通信,主要使用Ka/Ku頻段,覆蓋空域廣,傳輸依靠衛(wèi)星轉(zhuǎn)發(fā),通信距離遠(yuǎn)[1-2]。但飛機(jī)在高速移動(dòng)狀態(tài)空地通信鏈路資源有限,單一類型的空地帶寬鏈路已然不能解決上述問(wèn)題。為了保證用戶良好體驗(yàn)與通信服務(wù)質(zhì)量,多路徑傳輸協(xié)議(Multipath TCP,MPTCP)提供了一個(gè)不錯(cuò)的解決方案。與常規(guī)TCP相比,多路徑傳輸協(xié)議是一種適用于異構(gòu)無(wú)線網(wǎng)絡(luò)和有線互聯(lián)網(wǎng)的并發(fā)傳輸協(xié)議,為了提高用戶的服務(wù)質(zhì)量,在異構(gòu)網(wǎng)絡(luò)最新的研究中重點(diǎn)在資源的使用分配方面[3-5]。MPTCP能夠利用冗余信道資源,可以將吞吐量、傳輸速率提高到所有鏈路的總和而未使用像TCP協(xié)議所要求的單個(gè)信道。與此同時(shí),MPTCP與傳統(tǒng)TCP協(xié)議向后兼容。

基于多路徑網(wǎng)絡(luò)流量分配方面一直是重要的研究領(lǐng)域[6-7]?，F(xiàn)有分配策略[8-10]有基于數(shù)據(jù)包和基于流的負(fù)載分配策略,而每種策略都有自己的特性。Prabhavat等人[11]提出了有效延遲控制負(fù)載分配的策略,即最小化在接收端數(shù)據(jù)重新排序時(shí)間以及在傳輸過(guò)程中每條鏈路的延遲差異,從而減少傳輸時(shí)延?，F(xiàn)在研究較多的多路徑TCP協(xié)議就是以數(shù)據(jù)流形式在多鏈路上將流量有效地分配?？傊?基于數(shù)據(jù)包的模型雖然可以減少端到端的延遲,但是無(wú)法維持?jǐn)?shù)據(jù)包的順序,這依然為一個(gè)嚴(yán)重的問(wèn)題;基于單個(gè)流的模型通常將單個(gè)流的數(shù)據(jù)包分發(fā)到相同路徑上,很少切換路徑,這有助于將數(shù)據(jù)包重新排序,代價(jià)就是巨大的端到端延遲。

本文考慮到民航空地通信中丟包率高、時(shí)延大、多鏈路流量擁塞等特性,提出了多鏈路數(shù)據(jù)均衡分配算法。該算法重新估量了在數(shù)據(jù)傳輸過(guò)程中的有效損失率問(wèn)題,通過(guò)漸進(jìn)近似的方法,動(dòng)態(tài)調(diào)整數(shù)據(jù)流的分割比率大小,解決了鏈路擁塞、數(shù)據(jù)損失率高以及傳輸時(shí)延大等問(wèn)題。

1 系統(tǒng)模型及公式

為了解決在民航空地通信中較低吞吐量和數(shù)據(jù)有效丟失等問(wèn)題,本文提出了MPTCP系統(tǒng)模型的解決方案,如圖1所示。本文研究了MPTCP的多條鏈路端到端通信問(wèn)題,提出的多鏈路數(shù)據(jù)均衡分配方案旨在通過(guò)約束端到端數(shù)據(jù)流的分割比率,把數(shù)據(jù)流分配給狀態(tài)良好的鏈路。數(shù)據(jù)在本地服務(wù)器端被劃分為多個(gè)子流,每個(gè)子流進(jìn)一步再被劃分為多個(gè)數(shù)據(jù)包并緩存在發(fā)送區(qū)中。在系統(tǒng)模型中,對(duì)于數(shù)據(jù)流分割以及鏈路選擇問(wèn)題主要在本地服務(wù)器端實(shí)現(xiàn),對(duì)于接收到的數(shù)據(jù)重組以及丟包率和帶寬等參數(shù)的反饋主要由接收端負(fù)責(zé)。

圖1 子流分配系統(tǒng)模型

本文考慮的是空地通信異構(gòu)覆蓋網(wǎng)絡(luò),通過(guò)配置多個(gè)通信鏈路連接服務(wù)器端并將目的地址與源地址進(jìn)行綁定來(lái)實(shí)現(xiàn)空地多鏈路通信。由于通信的多條鏈路是并行且互不影響的,因此,每條通信鏈路的有效損失率Πi、可用帶寬μi和往返時(shí)延TRT等鏈路參數(shù)是互不影響的[12-13]。

首先,假設(shè)在發(fā)送端需要發(fā)送總的數(shù)據(jù)流大小為s,每條鏈路上被劃分的子流大小為

si=s·φi,i∈(1,2,3,…,p)。

(1)

(2)

(3)

在民航空地通信的過(guò)程中,因?yàn)橥ㄐ畔到y(tǒng)是時(shí)變的,則使用狀態(tài)轉(zhuǎn)移概率對(duì)P(φi)進(jìn)行估計(jì)?；谶B續(xù)時(shí)間馬爾科夫鏈的瞬間特性,可以得到鏈路i的狀態(tài)轉(zhuǎn)移方程為

(4)

(5)

(6)

由公式(4)～(6)得,在鏈路i中第k個(gè)數(shù)據(jù)包的狀態(tài)為B時(shí)的概率表示為

(7)

(8)

在民航空地通信的過(guò)程中,由于高速的移動(dòng)性和較長(zhǎng)距離地傳輸會(huì)造成數(shù)據(jù)包傳輸?shù)挠馄趩?wèn)題。文獻(xiàn)[16]提出用M/G/1排隊(duì)時(shí)延模型近似逾期損失,而逾期丟包率與端到端數(shù)據(jù)包傳輸延遲有關(guān),因此,單條鏈路上端到端延遲遵循指數(shù)分布[17],逾期損失率表示為

(9)

式中:E(·)為期望值;T表示約束逾期時(shí)間;E(Di)的值由大量延遲統(tǒng)計(jì)數(shù)據(jù)得到的值。因此文獻(xiàn)[17]提出使用一個(gè)分?jǐn)?shù)函數(shù)來(lái)近似子流分配的延時(shí)模型:

(10)

(11)

綜上,有效損失率可表示為

(12)

最終,正如文獻(xiàn)[18]所述,為了消除民航中空地通信之間較大的延遲差異以及擁塞帶來(lái)的吞吐量問(wèn)題,本文將多鏈路P上的數(shù)據(jù)流分配問(wèn)題轉(zhuǎn)化成為一個(gè)使最大丟失率鏈路縮小化,在每一次鏈路更新時(shí)總會(huì)選出丟失率最高的鏈路,通過(guò)約束條件計(jì)算出合理的矢量分割率,基于漸進(jìn)近似的方法推導(dǎo)其解,得到每條鏈路的動(dòng)態(tài)數(shù)據(jù)流分割表達(dá)式。

(13)

2 多鏈路數(shù)據(jù)流負(fù)載均衡分配算法

本文基于實(shí)用理論的流量分配方案,把最高有效丟失率鏈路通過(guò)漸進(jìn)近似的方法最小化[19]。由于在民航空地通信的過(guò)程中,不同鏈路需要接入不同的數(shù)據(jù)鏈路網(wǎng)絡(luò),飛機(jī)高速的移動(dòng)性伴隨而來(lái)的也是較高的數(shù)據(jù)丟失,并且通信網(wǎng)絡(luò)中也伴隨有流量擁塞的問(wèn)題出現(xiàn)。為了解決出現(xiàn)的問(wèn)題,引入漸進(jìn)近似的方法。在所有的鏈路中,通過(guò)將多鏈路中丟失率最高的鏈路與丟失率最低的鏈路逐漸通過(guò)控制分割率調(diào)整子流分配的大小,使得每條鏈路的丟失率盡可能近似相同,從整體上擁塞鏈路負(fù)載均衡。

本文引入流量分割率φi參數(shù),作為為每條鏈路分割數(shù)據(jù)流大小的參照。在初始時(shí),假設(shè)流量分割比率是根據(jù)帶寬計(jì)算的,表示為

(14)

(15)

2)在所有鏈路中,選擇有效損失率最大的Πiworst,1≤iworst≤p,再選擇有效損失率最小的Πibest,1≤ibest≤p。

3)通過(guò)計(jì)算Δφ,使Πiworst和Πibest的端到端有效損失率相等:

Πiworst(φiwosrt-Δφ)=Πibest(φibest+Δφ)。

(16)

每次分割率變化量Δφ可以求得

(17)

式中:μi·(1-πi)表示為當(dāng)前鏈路i的無(wú)損帶寬。

4)為了避免路徑iworst上的分割率和路徑Πiworst上的過(guò)載為負(fù)值,所以Δφ必須由

Δφ←min(φiwosrt,Δφ)。

(18)

(19)

Δm-1。

(20)

通過(guò)以上的目標(biāo)函數(shù),可以得到

(21)

可以估計(jì)鏈路有效增量

(22)

由上式可知,通過(guò)確定子流分割率分割數(shù)據(jù)流的目的是最小化不同鏈路上的損失率的差值來(lái)解決數(shù)據(jù)擁塞的問(wèn)題。

丟包感知負(fù)載均衡分配算法偽代碼如下:

1 輸入:{μi,ξi}i∈P,D=max(Di),T

2 輸出:Si={S*φi}i∈P

3 foreachi∈Pdo

4 初始化Si,TRTi,E(Di),φi

5 while(Si≤μi·(1-πi))&&(E(Di)≤D)&&(Δφ!=0) do

6φi=φi+Δφ//計(jì)算數(shù)據(jù)流S的分割比率

7Si←S*φi

8 更新各個(gè)參數(shù)TRTi,D=E(Di),φi

9 end

10 重設(shè)上述參數(shù)Si,TRTi,E(Di)

11 while(Si≤μi(1-πi)) &&(E(Di)≤D)&&(Δ!=0) do

12φi=φi-Δφ//計(jì)算數(shù)據(jù)流S的分割比率

13 更新各個(gè)參數(shù)TRTi,D=E(Di),φi

14 end

15 確定子流的分配向量

16 end

17 特定的路徑間分配

18 找到另一條可用的路徑P

19 if(Sp′≤μp′(1-πp′))&&(E(Dp′)≤D)(Δφ!=0) do

20φi=φi+Δφorφi=φi-Δφ

21 end

22 end

因?yàn)槌跏鸡読被設(shè)置成單條鏈路帶寬與多條鏈路帶寬總和的比值,并不是從源點(diǎn)開始計(jì)算,當(dāng)計(jì)算一輪后,可能導(dǎo)致計(jì)算出分配的分割比率變化量過(guò)高問(wèn)題。為了解決這個(gè)問(wèn)題,在算法中采用了取最小變化量的方式,最終得到按照分割比率分割子流的結(jié)果。

3 仿真與分析

本節(jié)基于Exata搭建了一個(gè)仿真系統(tǒng)架構(gòu)實(shí)驗(yàn)平臺(tái),在一臺(tái)運(yùn)行Windows10的PC機(jī)上進(jìn)行仿真,如圖2所示。通過(guò)把Sender端和Receiver端映射到網(wǎng)絡(luò)里的計(jì)算機(jī)中,將要發(fā)送的數(shù)據(jù)分配給不同的鏈路,并添加了多條通信鏈路。通過(guò)將源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)都配備多個(gè)網(wǎng)絡(luò)接口,它們之間有不相交的路徑,總的帶寬可由每條鏈路帶寬聚合而成,并將每條鏈路的傳播時(shí)延設(shè)置不同的值,如表1所示。

圖2 仿真系統(tǒng)架構(gòu)

表1 多鏈路通信參數(shù)

首先,本文設(shè)置了當(dāng)通信鏈路僅有兩條時(shí),給予需要傳輸數(shù)據(jù)流大小分別為7.75 Mb、6.5 Mb、5.25 Mb和4 Mb,并統(tǒng)計(jì)了在各個(gè)分配算法下的數(shù)據(jù)重傳情況,結(jié)果如圖3所示。由圖中比較可以得出,所提算法在數(shù)據(jù)重傳方面低于其他幾種算法。本文是基于有效丟失率進(jìn)行的選擇鏈路分配,很大程度上減少了數(shù)據(jù)的損失,避免了數(shù)據(jù)的重傳,所以在數(shù)據(jù)重傳上低于其他算法重傳的數(shù)量。由于MPTCP對(duì)于TCP是友好的,因此在引入基于數(shù)據(jù)有效損失率作為考慮數(shù)據(jù)分割的一個(gè)標(biāo)準(zhǔn)后,數(shù)據(jù)重傳數(shù)量得到了明顯的降低。

圖3 數(shù)據(jù)包重傳數(shù)量

其次,數(shù)據(jù)從發(fā)送端到接收端接收重組數(shù)據(jù)的平均時(shí)延如圖4所示,圖中展示了所提算法和其他算法時(shí)延變化趨勢(shì)的對(duì)比,可見(jiàn)所提數(shù)據(jù)分配算法性能隨著傳輸?shù)逆溌返脑黾佣黾?。這是由于所提算法更加準(zhǔn)確地計(jì)算出每條鏈路的數(shù)據(jù)丟失率,給鏈路狀態(tài)較好的分配較大的子流,給鏈路狀態(tài)較差的分配較小的子流,以緩解鏈路的擁塞問(wèn)題和有效丟失率問(wèn)題,并降低了數(shù)據(jù)在端到端傳輸過(guò)程中連續(xù)丟失而導(dǎo)致在接收端產(chǎn)生的重組消耗時(shí)間。圖5給出了平均丟包損失率隨著鏈路個(gè)數(shù)的變化趨勢(shì)。

圖4 平均端到端時(shí)延

圖5 平均丟包率

最后,圖6展示了所提算法在丟包率上實(shí)時(shí)變化情況并與其他算法進(jìn)行了對(duì)比。從圖中可以看出,所提算法從整體上看實(shí)時(shí)丟包率變化表現(xiàn)得更為良好,更趨于平穩(wěn)和越來(lái)越收斂,說(shuō)明了所提算法的有效性。另外,如表2所示,雖然所提算法PL-ALB在實(shí)時(shí)丟失率以及時(shí)延等方面表現(xiàn)較好,但是在算法時(shí)間復(fù)雜度上并不是最佳的。這是因?yàn)樗崴惴ㄐ枰獙?duì)每條鏈路進(jìn)行參數(shù)更新,所以產(chǎn)生了大量的運(yùn)算時(shí)間。隨著鏈路個(gè)數(shù)的增加,算法復(fù)雜度也會(huì)逐漸增加,這也是本算法需要進(jìn)行提高和優(yōu)化的方面。

圖6 實(shí)時(shí)丟包率

表2 算法時(shí)間復(fù)雜度比較

4 結(jié)束語(yǔ)

本文提出了一種丟包感知負(fù)載均衡數(shù)據(jù)分配算法,通過(guò)計(jì)算每條鏈路的有效損失率情況,找出最佳和最差鏈路,求出合適的分割比率,通過(guò)循序漸進(jìn)的方式不斷地調(diào)整分割比率,最終達(dá)到每條鏈路的有效損失率盡量趨于相同。仿真結(jié)果表明,本文所提算法增加了傳輸?shù)耐掏铝?減少了在傳輸過(guò)程中數(shù)據(jù)丟失的比率和數(shù)據(jù)重傳個(gè)數(shù)。在未來(lái)的工作中,將繼續(xù)改進(jìn)擁塞控制和不同路徑的能耗問(wèn)題。