基于多徑的低軌衛(wèi)星網(wǎng)絡(luò)路由擁塞控制策略

焦媛媛，田 豐，石 神 ，劉 潔，劉會(huì)杰1，，3

（1.中國(guó)科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所上海200050；2.中國(guó)科學(xué)院上海微小衛(wèi)星工程中心上海201203；3.上海科技大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海201210；4.中國(guó)科學(xué)院大學(xué)北京100049）

隨著星上處理技術(shù)的發(fā)展與星上存儲(chǔ)能力的增 強(qiáng)，衛(wèi)星通信因其獨(dú)特的優(yōu)勢(shì)（覆蓋范圍廣、不受地理?xiàng)l件影響等）與地面通信系統(tǒng)形成互補(bǔ)，廣泛應(yīng)用于地面通信系統(tǒng)不易覆蓋或建設(shè)成本過(guò)高的領(lǐng)域。其中LEO衛(wèi)星相對(duì)于靜止軌道衛(wèi)星來(lái)說(shuō)具有更低的傳輸時(shí)延、能夠覆蓋較高的維度區(qū)域和更低的終端發(fā)射功率要求等優(yōu)點(diǎn)，使得LEO衛(wèi)星通信占據(jù)優(yōu)勢(shì)地位，眾多LEO衛(wèi)星系統(tǒng)成功運(yùn)營(yíng)是最好的證明，如Iridium、Teledesic、Orbcomm等[1-2]。

與高軌通信衛(wèi)星相比，低軌衛(wèi)星功率較小、覆蓋面積較小，需要構(gòu)建低軌衛(wèi)星網(wǎng)絡(luò)，進(jìn)行組網(wǎng)通信[3]?，F(xiàn)實(shí)場(chǎng)景中，業(yè)務(wù)需求分布不均勻，例如發(fā)達(dá)國(guó)家業(yè)務(wù)需求高于發(fā)展中國(guó)家，陸地業(yè)務(wù)需求高于海洋業(yè)務(wù)請(qǐng)求，使得低軌衛(wèi)星通信網(wǎng)絡(luò)出現(xiàn)鏈路阻塞，從而影響通信質(zhì)量[4]。針對(duì)這一挑戰(zhàn)，本文提出一種新的網(wǎng)絡(luò)擁塞控制策略，利用多徑均衡整網(wǎng)流量，減小擁塞，提高網(wǎng)絡(luò)魯棒性。

目前已有許多常用擁塞控制算法，如主動(dòng)隊(duì)列管理、丟包策略、數(shù)據(jù)包管理[5-6]。前兩種方法都有一定的丟包概率，數(shù)據(jù)包調(diào)度最適用于路由算法改進(jìn)達(dá)到擁塞控制目的，是一種能盡量降低丟包率的一種方法，他通過(guò)感知節(jié)點(diǎn)自身?yè)砣麪顩r與周?chē)従庸?jié)點(diǎn)的擁塞狀況，及時(shí)分流給鄰居節(jié)點(diǎn)，然而是以犧牲實(shí)時(shí)性能、可靠性等性能指標(biāo)實(shí)現(xiàn)的?，F(xiàn)有的以時(shí)延或跳數(shù)為目標(biāo)的單徑路由算法（如Dijkstra、BellmanFord算法等）在網(wǎng)絡(luò)任務(wù)數(shù)較少的情況下性能較優(yōu)，但是在任務(wù)量較多的情況下易造成擁塞狀況[7-8]。

多徑路由有利于均衡負(fù)載，減少網(wǎng)絡(luò)擁塞[9-10]?？紤]低軌衛(wèi)星網(wǎng)絡(luò)（LEO）是高度確定的網(wǎng)絡(luò)（衛(wèi)星在確定的軌道上運(yùn)動(dòng)），在特定時(shí)間每顆衛(wèi)星路由的流量大致可以估計(jì)，我們可以提前對(duì)網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)流量的分配，而不是被動(dòng)地分流[11]。為了盡可能降低丟包率同時(shí)不犧牲路由算法的實(shí)時(shí)性和可靠性，本算法同時(shí)將路徑的時(shí)延和跳數(shù)考慮在內(nèi)作為網(wǎng)絡(luò)帶寬的開(kāi)銷(xiāo)指標(biāo)，采用多徑，以最小化整網(wǎng)鏈路傳輸帶寬方差與整網(wǎng)鏈路傳輸帶寬開(kāi)銷(xiāo)總和為目標(biāo)，得出多徑路徑帶寬分配系數(shù)，當(dāng)網(wǎng)絡(luò)任務(wù)數(shù)增多時(shí)，與單徑路徑對(duì)比能夠大幅度降低網(wǎng)絡(luò)中超負(fù)荷鏈路數(shù)，同時(shí)達(dá)到實(shí)時(shí)分流的效果。

1 模型的建立

銥星星座共有66顆衛(wèi)星（有6個(gè)軌道，每個(gè)軌道有11顆）[1]。假設(shè)衛(wèi)星彼此可視，且在一定的通信距離下，可以通信[13]。網(wǎng)絡(luò)中任意一對(duì)節(jié)點(diǎn)間存在多條路徑，為每一條路徑設(shè)置傳輸帶寬上限。當(dāng)任務(wù)超過(guò)一定數(shù)目時(shí)，多個(gè)任務(wù)的路徑存在部分鏈路重合現(xiàn)象，即存在鏈路同時(shí)傳送多個(gè)任務(wù)的帶寬。如下圖1。

圖1 部分鏈路重合

此時(shí)網(wǎng)絡(luò)存在多條鏈路擁塞，導(dǎo)致網(wǎng)絡(luò)魯棒性下降。然而，即使有些鏈路如此“繁忙”，網(wǎng)絡(luò)中仍存在鏈路處于“閑置”狀態(tài)。如何均衡整網(wǎng)流量成為以銥星星座為代表的LEO網(wǎng)絡(luò)亟待解決的問(wèn)題。

將上述低軌衛(wèi)星星座抽象為一個(gè)有N（對(duì)于銥星N為66）個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)。假設(shè)網(wǎng)絡(luò)中大部分點(diǎn)對(duì)之間存在超過(guò)M條鏈路。網(wǎng)絡(luò)中共有taskNum個(gè)任務(wù)數(shù)，即taskNum對(duì)通信衛(wèi)星[12]。將每個(gè)任務(wù)的帶寬按照相應(yīng)的比例分配到M條路徑上。則網(wǎng)絡(luò)中共有taskNum*M條傳輸數(shù)據(jù)的路徑。記第i顆衛(wèi)星到第j顆衛(wèi)星的鏈路給整網(wǎng)帶來(lái)的代價(jià)為costij。cost由時(shí)延、跳數(shù)等一系列影響網(wǎng)絡(luò)中鏈路好壞的參數(shù)決定，后文將根據(jù)低軌衛(wèi)星網(wǎng)絡(luò)的特點(diǎn)給出詳細(xì)的定義。BWi為傳輸?shù)趇個(gè)任務(wù)所需的帶寬。于是整網(wǎng)的任務(wù)模型圖如圖2所示。

圖2 多徑帶寬分配模型

2 基于多徑的低軌衛(wèi)星網(wǎng)絡(luò)路由擁塞控制算法

2.1 一般情況

圖2中每一對(duì)下標(biāo)相同的(s,d)節(jié)點(diǎn)對(duì)表示網(wǎng)絡(luò)中的一個(gè)任務(wù)，每個(gè)節(jié)點(diǎn)對(duì)之間均存在多條路徑，圖中為簡(jiǎn)化模型，實(shí)際的網(wǎng)絡(luò)中各任務(wù)的多條路徑間可能存在中間節(jié)點(diǎn)重合或部分路徑重合的情況。整網(wǎng)鏈路數(shù)學(xué)表達(dá)式如式（1）所示：

∑i表示第i個(gè)任務(wù)。規(guī)模為S個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中每一條路徑均可以用一個(gè)S*S的矩陣表示[13]。上式中的每一行中的矩陣表示每個(gè)任務(wù)選擇的前M條路徑，為了方便說(shuō)明，這里的所有路徑均用相同的矩陣表示，實(shí)際的矩陣顯然是不同的。λ為每一路徑的權(quán)值，表示該路徑傳輸該任務(wù)(λ*100)%帶寬的數(shù)據(jù)量。λ滿足下式：

為了評(píng)價(jià)每一條路徑性能的好壞，我們給每一條路徑設(shè)置一個(gè)cost值。在實(shí)際衛(wèi)星網(wǎng)絡(luò)中，評(píng)價(jià)一條路徑的好壞主要有兩個(gè)指標(biāo)，時(shí)延和跳數(shù)。為了同時(shí)綜合考慮這兩個(gè)指標(biāo)，將cost值定義如下：

α和β分別表示在該網(wǎng)絡(luò)中我們分別對(duì)路徑時(shí)延和跳數(shù)的重視程度。delayij為任務(wù)i的第j條路徑的時(shí)延，delaymin為第i個(gè)任務(wù)最短路徑的時(shí)延；hopij為任務(wù)i的第j條路徑的跳數(shù)，hopmin任務(wù)i最少跳數(shù)的路徑的跳數(shù)。分別計(jì)算每個(gè)任務(wù)的cost值，取每個(gè)任務(wù)前M條最小cost的路徑作為我們要傳輸數(shù)據(jù)的多徑路徑。

X為維度(S*S)*(N*M)的矩陣。令

λ為N*M維度的列向量。則多徑策略的整網(wǎng)路徑的流量方差為：

設(shè)μ為整網(wǎng)路徑帶寬的平均值，U=[μ μ…μ]T，U為S*S維列向量，則

這里ones(n,m)表示n行m列的元素全為1的矩陣。故

同時(shí)網(wǎng)絡(luò)所有鏈路傳輸帶寬的開(kāi)銷(xiāo)為SUM=||X*λ||1=sum(X)*λ。sum(X)表示以矩陣X的每一列為對(duì)象，對(duì)一列內(nèi)的數(shù)字求和。

這里的sum(X)為N*M維的行向量。

令fT=sum(X)，則SUM=fT*λ。

我們的目標(biāo)是求出λ行向量使得整網(wǎng)鏈路傳輸帶寬方差VAR和整網(wǎng)鏈路傳輸帶寬TOTAL加和最小。即TATOL=VAR+SUM。

綜上所述，可轉(zhuǎn)化為一個(gè)二次規(guī)劃問(wèn)題[14]：

其中λ為帶求系數(shù)向量；G'和fT在上文已給出詳細(xì)定義，均可由已經(jīng)量表示；

每一行有M個(gè)如圖所示的連續(xù)的1；

由二次規(guī)劃得到的網(wǎng)絡(luò)中所有路徑權(quán)值向量λ。即可得到整網(wǎng)鏈路的傳輸帶寬。

2.2 特殊情況

隨著任務(wù)數(shù)的增多，可能出現(xiàn)某任務(wù)的可行路徑不足M條的情況，不滿足二次規(guī)劃的條件，需要進(jìn)行以下處理。

對(duì)cost進(jìn)行采樣，去除cost矩陣中值為Inf和NaN的元素；采樣路徑矩陣X，去除不存在路徑的列；對(duì)于Aeq，若存在極端情況，即某個(gè)任務(wù)一條可行路徑都不存在，則Aeq存在全零行，則需要去除該全零行，與此同時(shí)beq的列數(shù)減一。

實(shí)驗(yàn)表明，以上情況只會(huì)在任務(wù)數(shù)超過(guò)一定數(shù)量時(shí)會(huì)出現(xiàn)。

2.3 策略分析

本策略提出一個(gè)綜合考慮時(shí)延和跳數(shù)的cost標(biāo)準(zhǔn)。取每個(gè)任務(wù)路徑時(shí)延最短的前M條路徑，綜合考慮跳數(shù)，得出該任務(wù)的多條路徑的cost值。對(duì)整網(wǎng)的每個(gè)任務(wù)均采用多徑路由，以最小化整網(wǎng)鏈路傳輸帶寬方差與整網(wǎng)鏈路傳輸帶寬開(kāi)銷(xiāo)總和為目標(biāo)，將問(wèn)題轉(zhuǎn)化為二次規(guī)劃問(wèn)題，最終得出每條路徑應(yīng)分配的帶寬比例。既最大可能地均衡了整網(wǎng)的流量，避免了擁塞，也同時(shí)考慮到多條路徑的優(yōu)劣，最小化整網(wǎng)鏈路傳輸帶寬的開(kāi)銷(xiāo)。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)步驟及參數(shù)設(shè)置

3.1.1 星座的建立

在STK中插入一顆衛(wèi)星，以這顆星為母星建立6個(gè)軌道，每個(gè)軌道11顆星的Walker星座。設(shè)置衛(wèi)星軌道高度780 km[15-16]，衛(wèi)星軌道偏心率0度，軌道傾角86.4度，軌道近地點(diǎn)角度0度，升交點(diǎn)赤經(jīng)0度，真近點(diǎn)角0度，星座相位因子為2，衛(wèi)星軌道在赤道上的分布范圍為180度，星座可建立星間鏈路的最大距離為5000 km，仿真時(shí)長(zhǎng)7200*12 s（24 h），仿真時(shí)間內(nèi)的取樣時(shí)間步長(zhǎng)60 s。

3.1.2 參數(shù)的設(shè)置

生成星座后，從STK中導(dǎo)出星座各節(jié)點(diǎn)的坐標(biāo)，對(duì)整網(wǎng)節(jié)點(diǎn)進(jìn)行可見(jiàn)性分析（衛(wèi)星全向天線，兩星之間超過(guò)5000 km不可見(jiàn)），生成66*66的可見(jiàn)性矩陣。矩陣中1表示兩點(diǎn)可見(jiàn)，0表示不可見(jiàn)。顯然生成的可見(jiàn)性矩陣為對(duì)稱矩陣。

本實(shí)驗(yàn)我們比較看重時(shí)延，令cost中的α=0.7，β=0.3。取多徑數(shù)M=4。對(duì)于每次仿真，依次設(shè)置5～30個(gè)節(jié)點(diǎn)的任務(wù)數(shù)。對(duì)于每個(gè)任務(wù)，生成N（N=5，6，…，29，30）個(gè) 0～1024 M的隨機(jī)傳輸帶寬和N個(gè)均為1024 M的固定帶寬。為網(wǎng)絡(luò)中的每條鏈路設(shè)置負(fù)載上限loadMax為500 M，超過(guò)上限認(rèn)為鏈路超過(guò)負(fù)荷，每次仿真記錄整網(wǎng)鏈路的超負(fù)載數(shù)，并與以最小時(shí)延為目標(biāo)的路由算法進(jìn)行對(duì)比。

3.2 實(shí)驗(yàn)結(jié)果與分析

路徑權(quán)值為該路徑傳輸所屬任務(wù)的帶寬比例。同一任務(wù)的路徑權(quán)值之和為1。生成使得整網(wǎng)鏈路代價(jià)最小的多徑路徑的權(quán)值λ。圖3和圖4分別為5個(gè)和30個(gè)任務(wù)帶寬均為1024 Mbps時(shí)的整網(wǎng)路徑的權(quán)值。

圖3 5個(gè)任務(wù)時(shí)整網(wǎng)路徑權(quán)值

圖4 30個(gè)任務(wù)時(shí)整網(wǎng)路徑權(quán)值

當(dāng)只有5個(gè)任務(wù)時(shí)，路徑序號(hào)最大為20，此時(shí)說(shuō)明每個(gè)任務(wù)均有大于4條的路徑。觀察同屬一個(gè)任務(wù)的路徑（例如1～4和9～12）的權(quán)值可發(fā)現(xiàn)，本算法得到的序號(hào)小的權(quán)值較大?？赡茉蚴?，我們是以時(shí)延最短為目標(biāo)依次生成的路徑（時(shí)延越短，路徑序號(hào)越靠前），取前4條最短路徑，而這幾條路徑的跳數(shù)差別并不大，甚至是相同的。而我們最終的二次規(guī)劃優(yōu)化目標(biāo)的一次項(xiàng)是網(wǎng)絡(luò)所有傳輸數(shù)據(jù)的鏈路帶寬的開(kāi)銷(xiāo)，所以同任務(wù)中序號(hào)靠前的路徑代價(jià)（cost）較小，是完全合理的。

隨著任務(wù)逐漸增多時(shí)，當(dāng)任務(wù)數(shù)為30時(shí)，路徑序號(hào)最大為113，小于120。說(shuō)明存在某個(gè)任務(wù)的路徑數(shù)不足4條，例如序號(hào)為108的路徑權(quán)值為1，即該路徑所屬任務(wù)只有一條路徑。這種情況本算法已按照2.2節(jié)所述的特殊情況處理方案進(jìn)行了解決。

圖5和圖6分別為任務(wù)帶寬隨機(jī)和任務(wù)帶寬均為1024 Mbps情況下5到30個(gè)任務(wù)的整網(wǎng)鏈路超過(guò)500 Mbps鏈路數(shù)。

圖5 任務(wù)帶寬隨機(jī)情況下的超負(fù)載鏈路數(shù)

仿真結(jié)果顯示，隨著任務(wù)數(shù)的增多兩種負(fù)載情況下的單徑和多徑路由方案的超負(fù)載鏈路數(shù)都整體呈現(xiàn)遞增趨勢(shì)。但是優(yōu)化后的多徑路由方案的整網(wǎng)超負(fù)載鏈路數(shù)明顯少于以時(shí)延為代價(jià)的單徑路由方案，并且隨著任務(wù)數(shù)的增多和任務(wù)負(fù)載的加重多徑路由方案的優(yōu)勢(shì)愈加明顯。

圖6 任務(wù)帶寬均為1024 Mbp情況的超負(fù)載鏈路數(shù)

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

文中基于低軌衛(wèi)星網(wǎng)絡(luò)的特點(diǎn)，針對(duì)衛(wèi)星網(wǎng)絡(luò)中存在的負(fù)載非均衡問(wèn)題，提出了一種基于多徑的低軌衛(wèi)星網(wǎng)絡(luò)擁塞控制算法，并以典型的低軌衛(wèi)星網(wǎng)絡(luò)銥星系統(tǒng)為背景進(jìn)行了仿真，得出每個(gè)任務(wù)多條路徑傳輸帶寬的比例和整網(wǎng)的超負(fù)載鏈路數(shù)，并與以時(shí)延為目標(biāo)的單徑路由方案對(duì)比，能夠有效地均衡負(fù)載，達(dá)到控制擁塞的目的。本算法適合多數(shù)點(diǎn)對(duì)間存在多徑路徑的網(wǎng)絡(luò)，且多徑數(shù)目越多，本算法的優(yōu)越性愈顯著，具有擴(kuò)展性，使用范圍廣的優(yōu)點(diǎn)。