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

焦媛媛，田 豐，石 神 ，劉 潔，劉會杰1，，3

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

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

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

目前已有許多常用擁塞控制算法，如主動隊列管理、丟包策略、數(shù)據(jù)包管理[5-6]。前兩種方法都有一定的丟包概率，數(shù)據(jù)包調(diào)度最適用于路由算法改進(jìn)達(dá)到擁塞控制目的，是一種能盡量降低丟包率的一種方法，他通過感知節(jié)點自身擁塞狀況與周圍鄰居節(jié)點的擁塞狀況，及時分流給鄰居節(jié)點，然而是以犧牲實時性能、可靠性等性能指標(biāo)實現(xiàn)的。現(xiàn)有的以時延或跳數(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)動），在特定時間每顆衛(wèi)星路由的流量大致可以估計，我們可以提前對網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)流量的分配，而不是被動地分流[11]。為了盡可能降低丟包率同時不犧牲路由算法的實時性和可靠性，本算法同時將路徑的時延和跳數(shù)考慮在內(nèi)作為網(wǎng)絡(luò)帶寬的開銷指標(biāo)，采用多徑，以最小化整網(wǎng)鏈路傳輸帶寬方差與整網(wǎng)鏈路傳輸帶寬開銷總和為目標(biāo)，得出多徑路徑帶寬分配系數(shù)，當(dāng)網(wǎng)絡(luò)任務(wù)數(shù)增多時，與單徑路徑對比能夠大幅度降低網(wǎng)絡(luò)中超負(fù)荷鏈路數(shù)，同時達(dá)到實時分流的效果。

1 模型的建立

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

圖1 部分鏈路重合

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

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

圖2 多徑帶寬分配模型

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

2.1 一般情況

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

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

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

α和β分別表示在該網(wǎng)絡(luò)中我們分別對路徑時延和跳數(shù)的重視程度。delayij為任務(wù)i的第j條路徑的時延，delaymin為第i個任務(wù)最短路徑的時延；hopij為任務(wù)i的第j條路徑的跳數(shù)，hopmin任務(wù)i最少跳數(shù)的路徑的跳數(shù)。分別計算每個任務(wù)的cost值，取每個任務(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的矩陣。故

同時網(wǎng)絡(luò)所有鏈路傳輸帶寬的開銷為SUM=||X*λ||1=sum(X)*λ。sum(X)表示以矩陣X的每一列為對象，對一列內(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)化為一個二次規(guī)劃問題[14]：

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

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

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

2.2 特殊情況

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

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

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

2.3 策略分析

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

3 實驗與分析

3.1 實驗步驟及參數(shù)設(shè)置

3.1.1 星座的建立

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

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

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

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

3.2 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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