一種適用于衛(wèi)星DTN網(wǎng)絡(luò)的擁塞控制算法

李靜森

(太原學(xué)院,山西 太原 030032)

隨著航天事業(yè)的持續(xù)高速發(fā)展,衛(wèi)星網(wǎng)絡(luò)受到越來越多的重視,因衛(wèi)星網(wǎng)絡(luò)通信具有不同于地面有線網(wǎng)絡(luò)的特點,如通信時延大、鏈路誤碼率高、間斷連接等特點和DTN網(wǎng)絡(luò)非常相似,因此衛(wèi)星網(wǎng)絡(luò)可以看成一種典型的DTN網(wǎng)絡(luò)[1],可以使用DTN的一些協(xié)議和機(jī)制解決衛(wèi)星網(wǎng)絡(luò)中的問題,但由于衛(wèi)星節(jié)點的資源有限,使用長期保存數(shù)據(jù)的方式會導(dǎo)致?lián)砣?。一旦出現(xiàn)擁塞會導(dǎo)致衛(wèi)星通信的時延變大、誤碼率增大。

衛(wèi)星DTN網(wǎng)絡(luò)即衛(wèi)星延遲容忍網(wǎng)絡(luò)中含有大量鏈路可預(yù)測以及運行軌跡具有固定性、周期性的衛(wèi)星節(jié)點,這類節(jié)點的特性對解決衛(wèi)星DTN網(wǎng)絡(luò)的擁塞問題起了很重要的作用。

本文針對衛(wèi)星DTN網(wǎng)絡(luò)采用保管傳輸易引起節(jié)點擁塞和流量過載引起鏈路擁塞的問題,提出了一種區(qū)分鏈路擁塞和節(jié)點擁塞的控制算法DLNC(Distinguish Link and Node Congestion algorithm),該算法考慮到鏈路連通時間可預(yù)測的特性,根據(jù)節(jié)點空閑比判斷鏈路是否流量過載,并通過連通圖判斷鏈路是否擁塞,根據(jù)信息、節(jié)點的因素判斷節(jié)點是否發(fā)生擁塞;若擁塞則通過該概率圖查找保管節(jié)點來緩解擁塞,該算法大大降低了丟包率,提高了數(shù)據(jù)投遞率。

1 相關(guān)工作

對于DTN的擁塞控制,根據(jù)引起中斷的原因不同可以分為鏈路擁塞、節(jié)點擁塞和區(qū)域級擁塞[2],對于區(qū)域級擁塞是一種局部擁塞現(xiàn)象,可以通過鏈路擁塞和節(jié)點擁塞的處理來避免區(qū)域級擁塞。

在鏈路擁塞方面,張國華等人提出了解決DTN在鏈路能力隨時間變化以及鏈路間歇連接環(huán)境下的擁塞控制策略[3],并把擁塞歸結(jié)為最優(yōu)化的問題,在鏈路能力隨時間變化方面采用的是凸優(yōu)化方法,而在鏈路間歇方面使用的是動態(tài)規(guī)劃以及博弈論方法以此來決定節(jié)點是否接收保管傳輸。針對衛(wèi)星網(wǎng)絡(luò)的鏈路擁塞問題,現(xiàn)已有較好的解決方案如TCP Westwood、Delayed ACK等。

在節(jié)點擁塞方面,Burleigh等人提出了一種基于利益模型的被動擁塞控制算法(ACC),該算法根據(jù)節(jié)點的剩余緩存、信息的優(yōu)先級以及接收一個消息的風(fēng)險和收益等本地信息決定是接收還是拒絕信息,并且該算法沒有充分使用緩存空間,因此只適合于節(jié)點比較小的網(wǎng)絡(luò)。R.Das在ACC和CM的基礎(chǔ)上提出了一種新的使用于DTN的擁塞控制算法(CC),該算法根據(jù)信息的優(yōu)先級、TTL等對節(jié)點中的信息進(jìn)行排序,并通過計算頭部擁塞(HLB)情況、節(jié)點等級以及丟失概率與設(shè)置的門限值的比較決定是接收還是拒絕新到的信息。而Ying an等人針對節(jié)點擁塞提出了一種新的擁塞控制算法MACRE[4],該算法根據(jù)節(jié)點的發(fā)送數(shù)據(jù)的速率和接收數(shù)據(jù)的速率之差與節(jié)點的剩余緩存時間之積的大小來決定是接收還是拒絕新到的數(shù)據(jù),該算法通過控制節(jié)點發(fā)送速率和接收數(shù)據(jù)的速率來控制擁塞,使節(jié)點達(dá)到了一種平衡的狀態(tài),但該算法忽略了信息的大小、優(yōu)先級等因素且不適應(yīng)具有突發(fā)性的網(wǎng)絡(luò)。

2 DLNC算法

衛(wèi)星DTN網(wǎng)絡(luò)是拓?fù)鋭討B(tài)變化的網(wǎng)絡(luò),但每個衛(wèi)星的運行軌跡是固定的。為了獲取最大的報文投遞率,要有針對性的發(fā)送信息,即在發(fā)送信息時要盡可能快地找到目的節(jié)點。

2.1 鏈路的擁塞控制算法

在衛(wèi)星DTN網(wǎng)絡(luò)中,由于衛(wèi)星通信具有高動態(tài)的連接特征,對于在軌道上運行的衛(wèi)星來說,相互之間的連接可能會因為網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化、障礙物的阻擋、大氣流的阻礙以及地面站的切換等多種原因造成連接被周期性的中斷。但也可能由于衛(wèi)星通信過程中,某條鏈路上的負(fù)載流量過快引起的鏈路中斷,即鏈路的擁塞。

定義衛(wèi)星節(jié)點空閑比公式如下:

Lcon=1-U/L

(1)

空閑比是指節(jié)點中剩余緩存隊列長度與最隊列長度的比值。

在文獻(xiàn)[5]中,王占偉等人提出在適合的衛(wèi)星周期T內(nèi),通過STK軟件,計算T時間內(nèi)衛(wèi)星各個節(jié)點的鏈路通斷時間圖,構(gòu)建連通圖。該連通圖的每個元素格式如圖1所示,每一個元素代表一條單向可用鏈路,發(fā)送節(jié)點表示連接的源節(jié)點,接收節(jié)點即連接的目的節(jié)點,由開始時間和結(jié)束時間可以計算出連接的持續(xù)時間。衛(wèi)星DTN網(wǎng)絡(luò)中的每個節(jié)點都含有與其他節(jié)點相連的節(jié)點的連通圖。

發(fā)送節(jié)點接收節(jié)點開始時間結(jié)束時間

圖1連通圖時間圖的元素格式圖

在文獻(xiàn)[6]的基礎(chǔ)上,構(gòu)建了本文仿真模型的連通圖。表1是GEO衛(wèi)星與其中一顆中軌衛(wèi)星MEO2在2018-3-6到2018-3-7的24個小時內(nèi),相通的時間段。

表1 周期T內(nèi)的連通時間表

根據(jù)以上過程,設(shè)計鏈路擁塞算法。算法首先獲取節(jié)點中的信息的個數(shù)以及最多能容納的信息的個數(shù),得出鏈路的狀況,若鏈路處于擁塞狀態(tài)就進(jìn)行擁塞處理操作,來緩解鏈路擁塞。算法描述見算法1。

算法1:鏈路擁塞的控制算法

Input

U:節(jié)點能容納的最小數(shù)據(jù)的個數(shù)。

L:節(jié)點中已含有的數(shù)據(jù)包個數(shù)。

Output

Lcon:鏈路擁塞的程度。

Step:

1)根據(jù)式(1)得出當(dāng)前鏈路擁塞程度Lcon,并設(shè)置擁塞的門限值λ;

2)if(Lcon≤λ) 說明鏈路流量過載,判斷節(jié)點是否能通信;

3)if(不能通信)即鏈路中斷,通過查詢連通圖判斷此時該連接是否中斷;

4)if(查詢是中斷)即該次中斷是正常中斷,由于節(jié)點到達(dá)了流量過載;

5)while(空閑比>λ) 轉(zhuǎn)移節(jié)點中最大的信息到鏈路擁塞程度不大的鄰節(jié)點;

6)end while;

7)else 即該中斷是由鏈路擁塞引起的,不斷檢查節(jié)點緩存中剩余時間最短的信息,進(jìn)行丟棄;

8)else(能通信)進(jìn)行第5步操作;

9)else 說明鏈路處于正常狀態(tài),接收信息;

10)end else;

11)end if。

2.2 節(jié)點擁塞的控制算法

在衛(wèi)星DTN網(wǎng)絡(luò)中,由于衛(wèi)星易中斷、通信時延長等特征,造成衛(wèi)星節(jié)點需要長時間保存收到的信息,這易引起節(jié)點擁塞。本文針對節(jié)點擁塞分為擁塞避免和擁塞控制兩部分。

2.2.1擁塞避免處理過程

由于衛(wèi)星通信的時延較長,若在通信過程中經(jīng)過的跳數(shù)過多會增大時延,對于有N個節(jié)點的Ad Hoc網(wǎng)絡(luò),平均跳數(shù)約為InN,對于衛(wèi)星DTN網(wǎng)絡(luò)中,由于節(jié)點個數(shù)比較少,據(jù)此可設(shè)定節(jié)點跳數(shù)的最大門限值公式如(2):

Hmax=In(N)+1

(2)

在DTN網(wǎng)絡(luò)中,HLB(即頭部隊列阻塞)是一種很常見的擁塞現(xiàn)象,嚴(yán)重影響了數(shù)據(jù)的傳輸速率、延遲和網(wǎng)絡(luò)的公平性,因此應(yīng)避免在衛(wèi)星DTN網(wǎng)絡(luò)中出現(xiàn)HLB現(xiàn)象。計算HLB的公式如下:

(3)

其中Sd表示與新到bundle的目的地址一致的信息大小之和,S表示節(jié)點緩存大小,并設(shè)置HLB的門限值為γ(取值0.35),防止節(jié)點發(fā)生HLB擁塞。

在衛(wèi)星DTN網(wǎng)絡(luò)中,可能由于發(fā)送速率與接收速率相差過大,易造成瓶頸擁塞丟失大量新到的數(shù)據(jù)包,針對該問題,本算法通過加權(quán)平均速率方式計算節(jié)點的發(fā)送速率和接收速率,而不是采用節(jié)點的瞬時速率,通過瞬時速率與平均速率得出加權(quán)速率,速率的計算公式如下:

Rnew=αRcurrent+(1-α)Rmena

(4)

其中Rcurrent表示節(jié)點的瞬時速率,Rmean表示節(jié)點在新信息到達(dá)時速率的平均值,α是影響速率的因素,0≤α<1,若α很接近于零,說明加權(quán)速率和平均速率相比變化不大；若α很接近于1,說明加權(quán)速率受到瞬時速率的影響很大,考慮到平均速率根據(jù)說服性,因此本算法設(shè)置α=0.45。

因該算法是在Epidemic Router路由策略下進(jìn)行的,會產(chǎn)生大量的副本易造成網(wǎng)絡(luò)擁塞,應(yīng)該限制副本的數(shù)量為M。M的公式如下:

(5)

根據(jù)以上計算公式,設(shè)計擁塞避免算法,算法首先獲取信息的跳數(shù),并盡可能把新到的信息通過查詢相鄰的節(jié)點是否是目的節(jié)點的過程把信息盡快地發(fā)送出去。再根據(jù)HLB、發(fā)送速率和接收速率等決定是否接收數(shù)據(jù)。算法的描述見算法2。

算法2:擁塞避免算法

Input:

N:表示網(wǎng)絡(luò)中的節(jié)點數(shù);

新到的bundle;

Output:

避免擁塞;

Step:

1)根據(jù)公式(2)得出跳數(shù)的門限值Hmax,if(Hop>Hmax)拒收;

2)else if(新bundle的目的節(jié)點就是該節(jié)點) 接收;

3)else if(該節(jié)點的通信范圍內(nèi)沒有目的節(jié)點)根據(jù)擁塞控制算法,決定拒絕還是接受該bundle;

4)else if(該節(jié)點的下一跳節(jié)點含有該bundle且是目的節(jié)點) 拒收并通知含有該bundle的其它節(jié)點刪除該bundle;

5)else if(該節(jié)點的下一跳節(jié)點中含有該bundle的個數(shù)超過M時) 拒收;

6)else根據(jù)公式(3)計算出HBL值,if(HBL>λ)拒收;

7)else 根據(jù)公式(4)計算出Rout,Rin速率,if((Rout-Rin)*Rttl

8)else 拒收;

9)end else;

10)end if。

2.2.2擁塞控制過程

對于新到的數(shù)據(jù)包,要計算節(jié)點被占用緩存的程度,計算公式如下:

(6)

其中m表示信息的大小,fsize表示剩余緩存大小,Bsize是節(jié)點的緩存大小,并設(shè)定擁塞的門限值為β。

當(dāng)節(jié)點發(fā)生擁塞時,該算法并不是直接丟棄過期的信息,而是把節(jié)點中權(quán)值小的信息轉(zhuǎn)移到保管節(jié)點中,從此該保管節(jié)點全權(quán)管理該信息。權(quán)值的計算公式如下:

(7)

Hop表示節(jié)點中信息所經(jīng)過的跳數(shù),m表示信息的大小,fsize表示節(jié)點剩余緩存的大小,Rttl表示信息的剩余生存時間,Tttl表示信息的生存時間。

保管節(jié)點就是該節(jié)點的鄰節(jié)點,關(guān)于該保管節(jié)點的選擇,通過與連接圖相同的方式,構(gòu)建連接概率圖,記為G,連接概率圖中G的各個元素格式如圖2所示,鄰節(jié)點表示在源節(jié)點的通信范圍內(nèi)所有能夠通信的節(jié)點,目的節(jié)點是消息的目的接單。連接概率代表目的節(jié)點與鄰節(jié)點在周期T中持續(xù)時間之和與周期T的比較值,值越大表示在周期T中通信的時間越大,即相遇的概率越大。在每個節(jié)點上都定義了G,在選擇鄰節(jié)點時,就根據(jù)概率值的大小來選擇要保存轉(zhuǎn)移信息的節(jié)點,即保管節(jié)點。一旦保管節(jié)點接收了數(shù)據(jù),該數(shù)據(jù)就有保管節(jié)點全權(quán)代為管理。通過連接概率圖G,能夠很好地反應(yīng)節(jié)點的移動性。

鄰節(jié)點目的節(jié)點連接概率

擁塞控制的算法描述如下:

算法3:擁塞控制算法

Input:

新到的bundle;

Output:

緩解擁塞;

Step:

1)根據(jù)公式(6)計算出節(jié)點擁塞程度,if(Ncon<β)接收;

2)else 根據(jù)公式(7)計算每個bundle的權(quán)值if(該bundle的權(quán)值<該節(jié)點中所有bundle權(quán)值)拒收;

3)else 把權(quán)值最小的信息轉(zhuǎn)移到保管節(jié)點中;

4)end if。

3 仿真與性能評價

3.1 仿真平臺與仿真環(huán)境

本文采用是ONE1.5仿真軟件,這是一款專門為DTN網(wǎng)絡(luò)所設(shè)計的軟件,由于本軟件不支持衛(wèi)星網(wǎng)絡(luò),為了能很好地模擬衛(wèi)星的運行,本文通過STK軟件把衛(wèi)星的運行軌跡導(dǎo)出,并把衛(wèi)星運行軌跡中的經(jīng)緯度轉(zhuǎn)化為平面地圖上的x和y軸數(shù)據(jù)，并在OpenJUMP中編輯、定義,真實顯示衛(wèi)星在二維圖中的運行軌跡。

本文設(shè)計了一個三層衛(wèi)星模型,仿真的模擬場景如圖3所示,部分仿真參數(shù)配置如表2所示。該場景包括一個高軌衛(wèi)星(GEO)、兩顆中軌衛(wèi)星(MEO1、MEO2)、三顆低軌衛(wèi)星(LEO1、LEO2、LEO3)、三個位于喀什、北京、拉薩的地面站。衛(wèi)星是發(fā)送數(shù)據(jù)的源節(jié)點,地面站是接收數(shù)據(jù)的目的節(jié)點。

圖3 仿真模擬場景圖

表2 部分仿真參數(shù)配置

3.2 結(jié)果分析

本文在傳染路由(ER,Epidemic Routing)下,對DLNC、DO、CC和MACRE四種擁塞控制算法進(jìn)行了仿真驗證,分析了四種算法的數(shù)據(jù)投遞率、丟包率、平均開銷和平均時延。

3.2.1數(shù)據(jù)傳輸率與丟包率

圖4是在相同的仿真時間下四種擁塞控制算法的報文投遞率、丟包率的對比分析。由圖4可知,DLNC算法的投遞率、丟包率優(yōu)于其他三種算法,由于ER會產(chǎn)生大量的副本易引起擁塞, 其中DO算法是丟棄過期的數(shù)據(jù)包,因衛(wèi)星DTN網(wǎng)絡(luò)中易中斷、長時延會導(dǎo)致過期的數(shù)據(jù)包增加,使丟包率增加、投遞率降低, MACRE根據(jù)數(shù)據(jù)的發(fā)送速率與接收速率決定接收還是丟棄數(shù)據(jù)包,因衛(wèi)星網(wǎng)絡(luò)的數(shù)據(jù)發(fā)送具有突發(fā)性,易造成大量數(shù)據(jù)包丟失,而CC算法雖提高了投遞率,但其丟包率相比較大。

圖4 報文投遞率與丟包率的比較圖

3.2.2網(wǎng)絡(luò)開銷

圖5是在相同的仿真時間下四種擁塞控制算法的平均開銷對比分析,由圖5可知,DLNC算法的平均開銷優(yōu)于DO、CC兩種算法,而差于MACRE算法,其中O算法中數(shù)據(jù)包經(jīng)過了多次轉(zhuǎn)發(fā)而成功到達(dá)目的節(jié)點的數(shù)據(jù)包很少,MACRE算法通過節(jié)點的轉(zhuǎn)發(fā)速率與發(fā)送速率相比轉(zhuǎn)發(fā)數(shù)據(jù),盡量使發(fā)送速率與轉(zhuǎn)發(fā)速率達(dá)到平橫狀態(tài),因此大大降低了網(wǎng)絡(luò)開銷,DLNC算法雖考慮了發(fā)送速率與轉(zhuǎn)發(fā)速率,但只是用于擁塞避免,沒有使兩者達(dá)到平衡狀態(tài)。 因此與MACRE算法相比,網(wǎng)絡(luò)開銷較大。

圖5 網(wǎng)絡(luò)開銷比較圖

3.2.3平均時延

圖6是在相同的仿真時間下四種擁塞控制算法的平均時延對比分析,DLNC算法考慮到了數(shù)據(jù)的重要性,不會直接丟棄過期的數(shù)據(jù),因此會有大量數(shù)據(jù)等待,造成排隊時延過大,增大了平均時延。

4 結(jié)束語

通過分析衛(wèi)星DTN網(wǎng)絡(luò)中發(fā)生擁塞的現(xiàn)象,把擁塞情況分為鏈路擁塞、節(jié)點擁塞。針對這兩種擁塞,本文提出了一種區(qū)分鏈路擁塞與節(jié)點擁塞的控制算法DLNC。首先,該算法針對不同的擁塞情況,采取了不同的策略,并綜合考慮了信息大小、TTL、HLB、跳數(shù)以及節(jié)點的緩存、發(fā)送速率與接收速率等因素來解決了擁塞問題;然后,在ONE仿真軟件下,在ER路由策略環(huán)境下,通過該算法與已有的三種算法DO、CC、MACRE在報文投遞率、丟包率、網(wǎng)絡(luò)開銷、平均時延四個方面的比較表明,DLNC更能很好地解決衛(wèi)星DTN網(wǎng)絡(luò)的擁塞問題,有更好的投遞性能和丟包率性能。

圖6 平均時延比較圖