鄢硯軍,徐慧慧,葉 升
(1.中國人民解放軍91892部隊, 海南 三亞 572099; 2.武漢大學(xué) 電子信息學(xué)院, 武漢 430072)
當(dāng)前,地面第五代移動通信系統(tǒng)(5G)因高數(shù)據(jù)速率、低延遲和大規(guī)模連接特征成為通信業(yè)和學(xué)術(shù)界探討的熱點。然而,覆蓋面積小和小型蜂窩小區(qū)有限的回程容量仍未解決,難以單獨依靠地面網(wǎng)絡(luò)實現(xiàn)中國領(lǐng)土、領(lǐng)海內(nèi)信息網(wǎng)絡(luò)全覆蓋。隨著低軌道(low earth orbit,LEO)衛(wèi)星的快速發(fā)展,LEO衛(wèi)星網(wǎng)絡(luò)已顯示出巨大潛力,可以與地面網(wǎng)絡(luò)融合來解決上述問題。2018年,一些國家和組織宣布發(fā)射低地球軌道(LEO)通信衛(wèi)星用于構(gòu)建MSN為全球用戶提供寬帶互聯(lián)網(wǎng)連接服務(wù)。同樣,Oneweb計劃發(fā)射648顆低軌衛(wèi)星組成衛(wèi)星通信網(wǎng)絡(luò)用于全球衛(wèi)星互聯(lián)網(wǎng)寬帶服務(wù)[1]。得益于高海拔、寬廣的工作頻譜和超密集拓?fù)浣Y(jié)構(gòu),LEO衛(wèi)星網(wǎng)絡(luò)可以通過大容量回程、廣闊的覆蓋范圍和靈活的接入技術(shù)支持大量用戶通信[2],通過地面段接入移動衛(wèi)星通信網(wǎng)絡(luò)終端[3]進(jìn)行通信。
在天地一體化網(wǎng)絡(luò)中,信息數(shù)據(jù)傳輸需要高帶寬,但是終端業(yè)務(wù)存在不均衡的流量分布,難以保證最佳的端到端吞吐量,天地一體化路由算法在建立源終端與目標(biāo)終端之間的最佳路徑至關(guān)重要。研究人員對天地一體化路由方法[4-5]的研究主要方向是將地面路由協(xié)議擴(kuò)展到衛(wèi)星網(wǎng)絡(luò)中,使用預(yù)先計算的網(wǎng)絡(luò)拓?fù)鋪硐拗品汉槁酚上⒌臄?shù)量。這些研究大多數(shù)適用于預(yù)先計算的拓?fù)?,難以反映衛(wèi)星網(wǎng)絡(luò)的動態(tài)鏈路狀態(tài),對于衛(wèi)星網(wǎng)絡(luò)的高動態(tài)拓?fù)?,?yīng)解決衛(wèi)星動態(tài)路由問題。文獻(xiàn)[6]提出基于虛擬拓?fù)涞穆酚伤惴?,該算法利用衛(wèi)星軌道的周期特性和星座結(jié)構(gòu)的可預(yù)測特性,在衛(wèi)星運(yùn)轉(zhuǎn)的周期T內(nèi),將時間T離散化為n個時間片段。在某個時間片內(nèi),衛(wèi)星的拓?fù)浣Y(jié)構(gòu)可虛擬為靜態(tài)的拓?fù)鋱D,用最短路徑算法(dijkstra shortest-path,DSP)計算路由。文獻(xiàn)[7]采用周期離散化的思想,提出有限狀態(tài)的概念,將衛(wèi)星系統(tǒng)的一個周期分為多個狀態(tài),將每個狀態(tài)下的衛(wèi)星拓?fù)溥B接視為靜止,DSP算法能計算出每個狀態(tài)內(nèi)的全局最優(yōu)路徑,但該算法所有時間片內(nèi)路由表的計算操作都是預(yù)先完成的,無法應(yīng)對動態(tài)變化的網(wǎng)絡(luò)結(jié)構(gòu)。
國家安全和軍事領(lǐng)域日益增長的移動數(shù)據(jù)流量需求使衛(wèi)星網(wǎng)絡(luò)得到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注,由衛(wèi)星網(wǎng)絡(luò)與地面網(wǎng)絡(luò)互聯(lián)互通的天地一體化信息網(wǎng)絡(luò)被列入我國“十三五”規(guī)劃綱要。同時當(dāng)今世界正處于信息化戰(zhàn)爭時代,信息化戰(zhàn)爭是高度依賴信息保障的立體戰(zhàn)爭形態(tài),天地一體化網(wǎng)絡(luò)不受區(qū)域、地形影響,能夠快速建立無線網(wǎng)絡(luò),為聯(lián)合作戰(zhàn)提供通信支持。
隨著衛(wèi)星網(wǎng)絡(luò)用戶的快速增長,衛(wèi)星通信網(wǎng)絡(luò)擁塞情況已不可避免。為提高數(shù)據(jù)傳輸效率,文獻(xiàn)[8]采用了預(yù)測排隊時延的方法避免擁塞。文獻(xiàn)[9]提出基于“軌道代理”的方法,該算法收集每個相鄰鏈路的排隊時延,將時延信息轉(zhuǎn)發(fā)給軌道上的所有衛(wèi)星。在高流量負(fù)載下,由于報文傳輸時延大,收集的排隊時延可能已過時。為避免擁塞,文獻(xiàn)[10]提出了一種負(fù)載均衡(ELB)方案,在ELB中,當(dāng)衛(wèi)星鏈路變得擁塞時,它向鄰居衛(wèi)星發(fā)送擁塞通知,并要求鄰居衛(wèi)星降低發(fā)送速率。由于ELB沒有考慮下一跳鏈路的時延,仍然無法有效防止部分鏈路擁塞。為解決這個問題,文獻(xiàn)[11]提出了一種基于交通燈的智能路由策略,該策略根據(jù)當(dāng)前ISL的隊列時延來決定下一跳轉(zhuǎn)發(fā)節(jié)點。該方法降低了報文丟失率,但算法的傳輸時延是固定值,下一跳的選擇不是最佳解決方案,可能選擇更長的路徑傳輸數(shù)據(jù),導(dǎo)致端到端時延變得不穩(wěn)定,有時會異常高。
為解決天地一體化路由中擁塞問題,本文提出了一種基于擁塞狀態(tài)的路徑選擇算法(routing selection algorithm based on congestion in ITSNs,RACA)。該算法根據(jù)極軌道星座和切斜軌道星座特點提出一種新的網(wǎng)絡(luò)拓?fù)淠P?,相?yīng)給出了基于該模型的路由優(yōu)化算法。該路由算法的路由選擇以源地址和目的地址之間路徑的最小傳播時延和隊列時延為準(zhǔn)則,該算法是分布式的結(jié)構(gòu),即下一跳路由的選擇基于當(dāng)前時刻LEO衛(wèi)星中的分組來決定,與其他LEO衛(wèi)星和分組無關(guān)。然后通過模擬退火算法計算最優(yōu)的天地一體化路由集合,在端到端時延的約束條件下,最大化端到端的可用帶寬。
由LEO衛(wèi)星通信網(wǎng)絡(luò)和地面網(wǎng)絡(luò)組成的天地一體化網(wǎng)絡(luò)聯(lián)合作戰(zhàn)架構(gòu)如圖1所示。衛(wèi)星網(wǎng)絡(luò)由N個極軌道和M顆衛(wèi)星組成,每個地面終端到衛(wèi)星終端同時連接衛(wèi)星節(jié)點和地面節(jié)點。用戶終端可以通過地面節(jié)點或衛(wèi)星節(jié)點接入網(wǎng)絡(luò)。每個衛(wèi)星有5個端口,其中4個端口連接到4個相鄰衛(wèi)星,另一個端口連接到地面節(jié)點的端口。每個端口都可以配置一個性能計數(shù)器,該計數(shù)器用于計算報文的到達(dá)率和發(fā)送率,從而獲得每個鏈路的排隊時延。鏈路包含以下3種。
1) 軌內(nèi)星間鏈路,它是同一軌道平面內(nèi)相鄰2個衛(wèi)星節(jié)點之間的鏈路,記為Intra-ISL。
2) 軌間星間鏈路,它是相鄰軌道上相鄰衛(wèi)星之問的鏈路,記為Inter-ISL。
3) 星地鏈路,它是地面終端與衛(wèi)星之間的通信鏈路,記為GSL。
為了最大化源到目的終端之間的可用帶寬,本文根據(jù)地面鏈路、星地鏈路和ISL中的可用帶寬找到最佳路徑。由于衛(wèi)星的高移動性會導(dǎo)致ISL和星地鏈路的頻繁變化,衛(wèi)星路由算法直接影響天地一體化路由算法的性能。為此,本文首先基于每個ISL的通信時延,設(shè)計衛(wèi)星路由算法,得出源到目的衛(wèi)星之間的最小時延。然后,通過模擬退火算法選擇一種最佳組合,在端到端時延的約束條件下,最大化端到端可用帶寬。
文獻(xiàn)[12]使用了不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)尋找極軌道星座的最短路由,但不能用于傾斜軌道星座。本文提出了一種新型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),可以適用于極軌道星座和傾斜軌道星座。極軌道衛(wèi)星網(wǎng)絡(luò)和傾斜軌道衛(wèi)星網(wǎng)絡(luò)的拓?fù)淙鐖D2、圖3所示,本文將極軌道衛(wèi)星網(wǎng)絡(luò)和傾斜軌道衛(wèi)星網(wǎng)絡(luò)的立體星座分別從N極和S極的角度形成平面的拓?fù)浣Y(jié)構(gòu)。此時的平面網(wǎng)是由2張普通的網(wǎng)背靠背的疊加而成,這樣源衛(wèi)星在立體球面網(wǎng)絡(luò)上傳輸數(shù)據(jù)給目的衛(wèi)星的路由問題,變成了衛(wèi)星在平面網(wǎng)絡(luò)上尋找最短路由的問題。
圖2 極軌道星座網(wǎng)絡(luò)拓?fù)涫疽鈭D
圖3 傾斜軌道星座網(wǎng)絡(luò)拓?fù)涫疽鈭D
從圖2中可以看出,所有軌道面內(nèi)鏈路的長度是固定的,其計算公式為:
(1)
式(1)中:r表示軌道半徑;M為單個軌道面上的衛(wèi)星顆數(shù);L表示軌道面內(nèi)鏈路的長度。
2個相鄰軌道面上的衛(wèi)星之間鏈路長度為:
(2)
式(2)中:F代表軌道間的相位參數(shù);N表示每個軌道的衛(wèi)星個數(shù);θ表示當(dāng)前衛(wèi)星節(jié)點的緯度。
鏈路的距離決定數(shù)據(jù)包通過鏈路的傳播時延,網(wǎng)絡(luò)的擁塞程度決定數(shù)據(jù)包通過的隊列時延,本文定義鏈路的擁塞率為ci=λi/μi,i=1,2,3,4,λi是收到的相鄰4個衛(wèi)星的報文率,μi是給相鄰4個衛(wèi)星的發(fā)送率,λg是GSL報文到達(dá)率,μg是GSL報文發(fā)送率。si-sj之間的第n條鏈路的隊列時延表達(dá)式為:
(3)
(4)
定義dsg為星地鏈路的距離,則GSL的通信時延表達(dá)式為:
tsg=cg/μg(1-cg)+dsg/v
(5)
本文提出的RACA路由算法中的各個網(wǎng)絡(luò)節(jié)點只需要收集本節(jié)點和鄰居節(jié)點的網(wǎng)絡(luò)信息,對轉(zhuǎn)發(fā)的數(shù)據(jù)報文計算下一跳節(jié)點,不需要收集全網(wǎng)的時延信息,路由信息交互較少。衛(wèi)星節(jié)點地址以赤道為中心將地球分為南北2個極面,用0表示北極面,1表示南極面。我們定義源衛(wèi)星和目的衛(wèi)星的地址分別為(poles,rs,θs,ids)和(poled,rd,θd,idd),其中pole表示極面,r表示衛(wèi)星與極心的距離,θ表示極軌道星座衛(wèi)星軌道與中心線的夾角,id表示衛(wèi)星所處的軌道。
由于每個衛(wèi)星節(jié)點有4個方向的端口,當(dāng)節(jié)點收到需要轉(zhuǎn)發(fā)的數(shù)據(jù)時,首先確定可以轉(zhuǎn)發(fā)數(shù)據(jù)的端口。在當(dāng)前節(jié)點(poles,rs,θs,ids)收到發(fā)往目的節(jié)點(poled,rd,θd,idd)的數(shù)據(jù)時,首先記錄數(shù)據(jù)的入口方向,該方向在任何情況下都不會成為數(shù)據(jù)的下一跳方向;然后計算目的節(jié)點所在的方向,以保證數(shù)據(jù)包能以最少時延到達(dá)目的節(jié)點。當(dāng)前節(jié)點選擇下一跳的方法的相對地址表示如下:
(6)
式(6)中:pole的取值為0或1,0表示源節(jié)點和目的節(jié)點在相同極面,1表示在不同極面;r表示衛(wèi)星與極心的距離,當(dāng)r>0時,表示目的地址在源地址的外環(huán)上,當(dāng)r<0時,表示目的地址在源地址的內(nèi)環(huán)上;θ為正數(shù)時,表示目的節(jié)點在源節(jié)點的逆時針方向,θ為負(fù)數(shù)時,表示目的節(jié)點在源節(jié)點的順時針方向;id=0表示目的地址和源地址在相同的軌道上,id≠0表示目的地址和源地址在不同的軌道上。
2.2.1相同極面時的情況
1)id=0,進(jìn)一步對比r,r>0時,內(nèi)環(huán)方向的節(jié)點不會成為數(shù)據(jù)的下一跳方向,記錄數(shù)據(jù)的入口方向,該方向在任何情況下都不會成為數(shù)據(jù)的下一跳方向;當(dāng)r<0時,外環(huán)方向的節(jié)點不會成為數(shù)據(jù)的下一跳方向;最后對比剩下候選方向的鄰居節(jié)點的傳輸時延和隊列時延,選擇最短通信時延的候選鄰居為轉(zhuǎn)發(fā)的下一跳;當(dāng)r=0時,表示當(dāng)前衛(wèi)星就是目的節(jié)點衛(wèi)星。
2)id≠0,首先記錄數(shù)據(jù)的入口方向,該方向在任何情況下都不會成為數(shù)據(jù)的下一跳方向;然后對比r和θ,當(dāng)θ>0且r>0時,目的衛(wèi)星在當(dāng)前衛(wèi)星的右上側(cè),確定候選節(jié)點為內(nèi)環(huán)和右方向的節(jié)點;當(dāng)θ<0且r>0時,目的衛(wèi)星在當(dāng)前衛(wèi)星的左上側(cè),確定候選節(jié)點為內(nèi)環(huán)和左方向的節(jié)點;當(dāng)θ<0且r<0時,目的衛(wèi)星在當(dāng)前衛(wèi)星的左下側(cè),確定候選節(jié)點為外環(huán)和左方向的節(jié)點;當(dāng)θ>0且r<0時,目的衛(wèi)星在當(dāng)前衛(wèi)星的右下側(cè),確定候選節(jié)點為外環(huán)和右方向的節(jié)點;最后對比剩下候選方向的鄰居節(jié)點的傳輸時延及隊列時延,選擇有最短通信時延的候選鄰居為轉(zhuǎn)發(fā)的下一跳。
2.2.2不同極面的情況
基于提出的衛(wèi)星路由算法,si-sj之間的通信時延tsisj為:
(7)
對于源終端到目的終端u0-ud之間的數(shù)據(jù)傳輸,其端到端的通信時延由tu0si和tsjud組成。tussi表示源終端us到衛(wèi)星節(jié)點si的通信時延;tsjud表示衛(wèi)星節(jié)點sj到目的終端ud的通信時延,其計算公式分別為:
tussi=tusgi+tgisi,gi∈W,si∈S
(8)
tsjud=tgjud+tgjsj,gj∈W,sj∈S
(9)
式(8)~(9)中:tusgi表示u0到地面-衛(wèi)星終端gi的通信時延;tgjud表示gj到ud的通信時延;tgisi和tgjsj表示星地間的通信時延。
由于地面網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是固定的,源終端使用bellmanford 路由算法計算出u0-ud之間的路由和該路由上的地面終端節(jié)點到衛(wèi)星終端節(jié)點。并搜集u0-ud路徑上所有鏈路的流量狀態(tài)信息,然后通過路由更新周期內(nèi)的歷史鏈路流量來預(yù)測地面節(jié)點的每條鏈路流量,從而獲得該鏈路的隊列時延。由于u0-ud路徑上所有鏈路的傳播距離是固定的,傳播時延可以通過傳播距離計算,因此本文可以得到地面必經(jīng)鏈路的通信時延,即tu0gi和tgjud。
用無向圖G(V,E)表示天地一體化網(wǎng)絡(luò),其中V為網(wǎng)絡(luò)節(jié)點集(包括地面和衛(wèi)星節(jié)點),E為節(jié)點之間的物理鏈路集,鏈路權(quán)重表示節(jié)點之間的通信時延。設(shè)定地面網(wǎng)絡(luò)節(jié)點集Vc?V和地面終端到衛(wèi)星終端數(shù)目k,由于數(shù)據(jù)傳輸需要高帶寬,定義Cs、Cs分別為衛(wèi)星鏈路和地面鏈路的帶寬容量,Lsn、Lun分別為第n條衛(wèi)星鏈路和地面鏈路傳輸?shù)膱笪目傞L度,Tsn、Tun分別為數(shù)據(jù)流量在第n條衛(wèi)星鏈路和地面鏈路傳輸所需時間,本文目的是找出連接衛(wèi)星網(wǎng)絡(luò)的地面終端到衛(wèi)星終端的一個子集{g1,g2,…,gk}?W和衛(wèi)星子集{Si,…,Sj}?S,最大化源終端到目的終端的可用帶寬R,表達(dá)式為:
(10)
模擬退火算法的具體步驟為:
Input:G(V,E),tmax
Output:Wopt,Rmax;
1: Initialize 初始溫度β,終止溫度βfinal,退火系數(shù)α;
2: 從Vc集合的n個節(jié)點中隨機(jī)選擇k個初始地面-衛(wèi)星終端和為其服務(wù)的源-目的衛(wèi)星節(jié)點對集合Wopt;
3: 計算時延(tsisj+tsjud+tu0si);
4: if (tsisj+tsjud+tu0si)≤tmaxthen
5: whileβo>βfinaldo
6:Wnew=Wopt;
7: 生成新的集合Wnew;
8: 計算可用帶寬Rmax;
9:Δ=Rnew-Rmax;
10: 生成一個(0,1)的隨機(jī)數(shù);
12:Wnew=Wopt;
13:tnew=tmax;
14: end if
15:β=β.α;
16: end while
17: returnWopt,Rmax。
我們設(shè)定源節(jié)點到目的節(jié)點的地面至衛(wèi)星終端個數(shù)為k,其解空間集合的容量是k(k-1)/2,具有有限的數(shù)據(jù)量,考慮模擬退火算法過程簡單,能快速求出從所有源終端到目的終端可用帶寬的最大化最佳組合,我們采用模擬退火算法進(jìn)行計算。
仿真場景中的衛(wèi)星網(wǎng)絡(luò)由156顆衛(wèi)星組成,均勻分布在13個軌道上,高度為1 000 km,仿真參數(shù)見表1。仿真時在STK中創(chuàng)建星座模型,建立鏈路,在Qualnet中實現(xiàn)仿真模擬通信過程。在天地一體化路由算法中衛(wèi)星路由算法決定天地一體化路徑的選擇,為了驗證天地一體化路由方案,將RACA算法與ELB和DSP衛(wèi)星路由算法進(jìn)行對比。設(shè)置600條On-Off流,平均突發(fā)時間和平均空閑時間設(shè)置為200 ms,源終端和目的終端均勻分布,分為6個大陸區(qū)域,數(shù)據(jù)流分布見表2。源節(jié)點以0.8 Mbit/s至1.5 Mbit/s的恒定速率發(fā)送數(shù)據(jù)。
表1 仿真參數(shù)
表2 數(shù)據(jù)流分布 %
端到端時延是指源終端發(fā)送數(shù)據(jù)流量到目的終端需要的時間。從圖4可以看出,DSP算法的平均端到端時延要比其他算法高,原因是DSP算法一直在最短路徑上傳輸數(shù)據(jù)流量,隨著數(shù)據(jù)流量的增加,鏈路開始擁塞,所選最短路徑排隊時延增加,導(dǎo)致平均端到端時延大幅增加。ELB算法響應(yīng)擁塞動態(tài)地將流量繞道到備用路徑,因此ELB算法端到端時延低于DSP算法。
圖4 不同速率下的端到端時延曲線
對比ELB算法和RACA算法發(fā)現(xiàn)ELB的傳播延遲是恒定的,通過具有較高傳播延遲的路由發(fā)送數(shù)據(jù)包,造成ELB算法端到端時延比RACA算法高。本文提出的RACA算法在3種方案中均實現(xiàn)了最低的平均端到端時延,這是因為所提出的路由算法的傳輸時延是時變的。該算法選擇傳播時延和排隊時延中最小的路徑,一定程度緩解了擁塞。
圖5顯示了3種算法數(shù)據(jù)丟包率的變化趨勢,每條流的數(shù)據(jù)發(fā)送速率在0.8~1.5 Mbit/s的范圍內(nèi)變化,
圖5 不同速率下的丟包率曲線
從圖5可以看出,RACA算法的丟包率最低。這是因為在所有速率中,DSP算法始終選擇最短路徑傳輸數(shù)據(jù),發(fā)送速率增大時,鏈路會出現(xiàn)擁塞,造成所選路徑報文溢出,丟包率情況加大。ELB算法考慮了下一跳的擁塞,避免了隊列的溢出,但ELB算法傳輸時延是固定值,ELB算法繞行的路徑可能包括擁堵區(qū)域,造成丟包率增加。
為了驗證天地一體化路由的性能,圖6表示地面路由和天地一體化路由的吞吐量。在沒有擁塞的條件下,地面有足夠的網(wǎng)絡(luò)帶寬滿足用戶流量的需求,使用地面路由的時延最短,此時,TSHR選擇的路徑與地面路由選擇的最短路徑相同,在地面鏈路沒有擁塞時,地面網(wǎng)絡(luò)和TSHR網(wǎng)絡(luò)傳輸?shù)耐掏铝肯嗤?,?50 s時,由于流量需求的增加,節(jié)點開始擁塞。在地面路由算法中,一直選擇最短路徑會使數(shù)據(jù)流量集中該路徑上,導(dǎo)致該路徑節(jié)點負(fù)載過重。而在天地一體化路由算法中,衛(wèi)星節(jié)點參與到數(shù)據(jù)包的轉(zhuǎn)發(fā)工作,通過衛(wèi)星網(wǎng)絡(luò)更改路徑避免選擇地面擁塞的鏈路,提高數(shù)據(jù)傳輸?shù)耐掏铝俊?/p>
圖6 地面?zhèn)鬏敽吞斓匾惑w化傳輸?shù)耐掏铝壳€
本文針對通信網(wǎng)絡(luò)數(shù)據(jù)傳輸擁塞的問題,提出將衛(wèi)星網(wǎng)絡(luò)融合到地面網(wǎng)絡(luò)中,并提出一種天地一體化網(wǎng)絡(luò)傳輸路由算法RACA,根據(jù)地面段內(nèi)以及地面和衛(wèi)星段之間的流量需求調(diào)整路由。為了降低擁塞導(dǎo)致的隊列時延,首先提出基于ISL通信時延的衛(wèi)星路由算法,該算法通過計算每個方向上的ISL時延,找到最佳下一跳。然后以最大化路徑的可用帶寬為目標(biāo),通過模擬退火算法計算最優(yōu)的天地一體化路由集合。在Qualnet中對RACA算法、ELB算法和DSP算法進(jìn)行了仿真對比,結(jié)果表明,本文提出的RACA路由算法在端到端時延和丟包率方面均優(yōu)于其他2種算法。同時對比了擁塞狀態(tài)下天地一體化路由算法和地面路由算法,仿真結(jié)果表明天地一體化路由算法能為終端提供較好的吞吐量。