李靜森

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

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

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

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

1 相關(guān)工作

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

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

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

2 DLNC算法

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

2.1 鏈路的擁塞控制算法

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

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

Lcon=1-U/L

(1)

空閑比是指節(jié)點(diǎn)中剩余緩存隊(duì)列長(zhǎng)度與最隊(duì)列長(zhǎng)度的比值。

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

發(fā)送節(jié)點(diǎn)接收節(jié)點(diǎn)開(kāi)始時(shí)間結(jié)束時(shí)間

圖1連通圖時(shí)間圖的元素格式圖

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

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

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

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

Input

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

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

Output

Lcon:鏈路擁塞的程度。

Step:

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

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

3)if(不能通信)即鏈路中斷,通過(guò)查詢(xún)連通圖判斷此時(shí)該連接是否中斷;

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

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

6)end while;

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

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

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

10)end else;

11)end if。

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

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

2.2.1擁塞避免處理過(guò)程

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

Hmax=In(N)+1

(2)

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

(3)

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

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

Rnew=αRcurrent+(1-α)Rmena

(4)

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

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

(5)

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

算法2:擁塞避免算法

Input:

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

新到的bundle;

Output:

避免擁塞;

Step:

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

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

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

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

5)else if(該節(jié)點(diǎn)的下一跳節(jié)點(diǎn)中含有該bundle的個(gè)數(shù)超過(guò)M時(shí)) 拒收;

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

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

8)else 拒收;

9)end else;

10)end if。

2.2.2擁塞控制過(guò)程

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

(6)

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

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

(7)

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

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

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

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

算法3:擁塞控制算法

Input:

新到的bundle;

Output:

緩解擁塞;

Step:

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

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

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

4)end if。

3 仿真與性能評(píng)價(jià)

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

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

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

圖3 仿真模擬場(chǎng)景圖

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

3.2 結(jié)果分析

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

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

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

圖4 報(bào)文投遞率與丟包率的比較圖

3.2.2網(wǎng)絡(luò)開(kāi)銷(xiāo)

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

圖5 網(wǎng)絡(luò)開(kāi)銷(xiāo)比較圖

3.2.3平均時(shí)延

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

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

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

圖6 平均時(shí)延比較圖