衛(wèi)星網(wǎng)絡(luò)中基于時(shí)變圖的節(jié)能資源分配策略*

帥家成，劉雨,2**，望育梅,2

（1.北京郵電大學(xué)人工智能學(xué)院，北京 100876；2.鵬城實(shí)驗(yàn)室網(wǎng)絡(luò)與通信研究中心，廣東 深圳 518000）

0 引言

衛(wèi)星網(wǎng)絡(luò)由于其覆蓋范圍廣、不受地理因素影響等特點(diǎn)，被廣泛用于自然災(zāi)害的檢測(cè)、災(zāi)害損失評(píng)估等多種地球觀測(cè)任務(wù)。由于衛(wèi)星網(wǎng)絡(luò)的高動(dòng)態(tài)性、鏈路的不連續(xù)性與高時(shí)延等特征，其資源的時(shí)變表示是當(dāng)前研究難點(diǎn)之一[1-2]。此外，由于衛(wèi)星節(jié)點(diǎn)能量主要由太陽(yáng)能電池板提供，所以衛(wèi)星在太陽(yáng)光被遮擋時(shí)無(wú)法獲得能量，這就導(dǎo)致能量同樣成為衛(wèi)星網(wǎng)絡(luò)路由的稀缺資源[3]。文獻(xiàn)[4] 用時(shí)變圖（TEG,Time-Expanded Graph）來(lái)表示衛(wèi)星網(wǎng)絡(luò)的時(shí)變拓?fù)洳⒀芯苛水?dāng)衛(wèi)星節(jié)點(diǎn)資源受限時(shí)網(wǎng)絡(luò)中的資源分配問(wèn)題，解決了當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)資源受限時(shí)的最大流問(wèn)題，但并沒(méi)有考慮能量消耗。文獻(xiàn)[5]、文獻(xiàn)[6] 討論了衛(wèi)星網(wǎng)絡(luò)中的資源分配策略，但沒(méi)有降低網(wǎng)絡(luò)中的能量消耗。文獻(xiàn)[7] 提出了一種從用戶行為分析的角度研究了數(shù)據(jù)中繼衛(wèi)星（DRS,Data Relay Satellite）系統(tǒng)中的資源分配問(wèn)題，然而仍沒(méi)有將傳輸能耗作為優(yōu)化指標(biāo)。文獻(xiàn)[8]、文獻(xiàn)[9] 提出了基于時(shí)變圖的低能耗路由算法，但會(huì)降低網(wǎng)絡(luò)的吞吐量性能。

為了解決觀測(cè)任務(wù)中資源分配的傳輸能耗問(wèn)題，本文提出了一種貪心迭代式算法，來(lái)對(duì)觀測(cè)任務(wù)中的能耗進(jìn)行優(yōu)化，同時(shí)保證網(wǎng)絡(luò)吞吐量不減少。首先，為了表示網(wǎng)絡(luò)動(dòng)態(tài)變化的拓?fù)洌捎昧藭r(shí)變圖[10]來(lái)表示網(wǎng)絡(luò)中的連接情況、能耗水平等，在時(shí)間與空間兩個(gè)維度上的關(guān)系。由于衛(wèi)星節(jié)點(diǎn)的資源受限，當(dāng)一顆衛(wèi)星的傳輸資源小于能與其建立連接的鏈路容量之和時(shí)，需要進(jìn)行傳輸資源的分配。本文在時(shí)變圖中添加了虛擬節(jié)點(diǎn)來(lái)表示受限的衛(wèi)星傳輸資源，并添加了虛擬起點(diǎn)、虛擬終點(diǎn)與虛擬邊來(lái)簡(jiǎn)化問(wèn)題。此外，能耗水平被添加至圖中構(gòu)成資源能耗時(shí)變圖（RCTEG,Resource-Cost Time-Expanded Graph）?；赗CTEG，將本文提出的算法與文獻(xiàn)[4] 中的Ford-Fulkerson 算法和文獻(xiàn)[11] 中 的Boykov-Kolmogorov 算法進(jìn)行了對(duì)比，驗(yàn)證了本文提出算法在減少能耗的同時(shí)不損耗網(wǎng)絡(luò)吞吐量。

1 系統(tǒng)模型

1.1 任務(wù)模型

假設(shè)在網(wǎng)絡(luò)中存在R顆衛(wèi)星，一個(gè)地面目標(biāo)S，一個(gè)地面站D。R顆衛(wèi)星中存在R1顆遙感衛(wèi)星與R2顆中繼衛(wèi)星。遙感衛(wèi)星從地面目標(biāo)S獲取數(shù)據(jù)后，如果存在連接，其可以選擇直接將數(shù)據(jù)傳至地面站D，也可以選擇將數(shù)據(jù)傳至中繼衛(wèi)星，最終將數(shù)據(jù)傳至地面站，中繼衛(wèi)星只能從遙感衛(wèi)星獲取數(shù)據(jù)，無(wú)法直接從地面目標(biāo)獲取數(shù)據(jù)，其任務(wù)過(guò)程如圖1 所示。由于衛(wèi)星節(jié)點(diǎn)的資源受限，在衛(wèi)星可同時(shí)與多個(gè)節(jié)點(diǎn)建立連接且無(wú)法同時(shí)以所有鏈路的最大容量進(jìn)行傳輸時(shí)，需要進(jìn)行傳輸資源的分配，以使網(wǎng)絡(luò)能耗減小的同時(shí)不以犧牲吞吐量為代價(jià)。設(shè)需要進(jìn)行資源分配的衛(wèi)星節(jié)點(diǎn)數(shù)目為R3。

圖1 地球觀測(cè)任務(wù)

1.2 能耗模型

衛(wèi)星網(wǎng)絡(luò)中，星間鏈路的傳輸會(huì)受到衰減，其中最主要的是自由空間傳播衰減。衛(wèi)星的接收功率PR由式(1)決定[12]：

式中，PT為發(fā)射功率，GT為發(fā)射天線增益，GT為接收天線增益，LP為自由空間傳播衰減，LP由式(2) 決定：

式中d為傳播距離，λ為工作波長(zhǎng)，c為光速，f為工作頻率。假設(shè)星間與星地通信的工作頻率相同，接收與發(fā)射增益相同，則當(dāng)接收功率相同時(shí)，衛(wèi)星節(jié)點(diǎn)的發(fā)射功率僅與兩點(diǎn)的傳輸距離相關(guān)，假設(shè)傳輸時(shí)間t相同，則衛(wèi)星節(jié)點(diǎn)的傳輸能耗e僅與傳輸節(jié)點(diǎn)之間的距離相關(guān)，如式(3) 所示，式中k可以看作一個(gè)常數(shù)。

由于衛(wèi)星節(jié)點(diǎn)的高度移動(dòng)性，兩節(jié)點(diǎn)之間在連接窗口內(nèi)的距離不斷變化，將單次連接窗口內(nèi)的衛(wèi)星傳輸能耗視為由兩節(jié)點(diǎn)之間的平均距離決定。由于無(wú)需研究衛(wèi)星傳輸?shù)木唧w能量，將能耗進(jìn)行了歸一化，將平均距離為6 300 km 的衛(wèi)星傳輸能耗設(shè)為1。通過(guò)式(3)得到其他鏈路的傳輸能耗水平。

1.3 資源能耗時(shí)變圖

為了表示網(wǎng)絡(luò)中傳輸資源，能耗在時(shí)間與空間上的關(guān)系，本文將傳輸能耗的概念引入TEG[10]，得到RCTEG。在RCTEG 中，時(shí)間T被分為h個(gè)時(shí)隙T=｛t1,t2,……,th｝，每個(gè)時(shí)隙的長(zhǎng)度為Δτ，每個(gè)時(shí)隙內(nèi)的拓?fù)涫枪潭ú蛔兊摹CTEG 由節(jié)點(diǎn)集V、鏈路集A、容量集C與能耗集E構(gòu)成，RCTEG={(V,A,C,E)}。

節(jié)點(diǎn)集V包括：源點(diǎn)集VS={Si|1≤i≤h}表示h個(gè)時(shí)隙內(nèi)的地面目標(biāo)；遙感衛(wèi)星節(jié)點(diǎn)集1≤l≤R1}表示h個(gè)時(shí)隙內(nèi)的遙感衛(wèi)星；中繼衛(wèi)星節(jié)點(diǎn)集表示h個(gè)時(shí)隙內(nèi)的中繼衛(wèi)星；終點(diǎn)集VD={Di|1≤i≤h}表示h個(gè)時(shí)隙內(nèi)的地面站；虛擬節(jié)點(diǎn)集表示h個(gè)時(shí)隙內(nèi)需要進(jìn)行資源分配的衛(wèi)星節(jié)點(diǎn)對(duì)應(yīng)的虛擬節(jié)點(diǎn)。此外，節(jié)點(diǎn)集還包括虛擬起點(diǎn)Sv與虛擬終點(diǎn)Dv，通過(guò)虛擬起點(diǎn)與終點(diǎn)可以使網(wǎng)絡(luò)的多源多匯問(wèn)題轉(zhuǎn)化為單源單匯問(wèn)題。

鏈路集A包括：傳輸鏈路集1≤i≤h,v∈V-VD,v∈V-VS-VR3}表示在同一時(shí)隙內(nèi)的星間鏈路或星地鏈路；存儲(chǔ)鏈路集表示同個(gè)實(shí)體節(jié)點(diǎn)在不同時(shí)隙間的存儲(chǔ)能力；虛擬鏈路集表示需要進(jìn)行資源分配的節(jié)點(diǎn)與其虛擬節(jié)點(diǎn)之間的連接；輔助鏈路集Aa={(Sv,Si),(Di,Dv)|1≤i≤h}表示虛擬起點(diǎn)、虛擬終點(diǎn)與起點(diǎn)和終點(diǎn)之間的連接。

由TEG（圖2（a））改造后的RCTEG={(V,A,C,E)}如圖2（b）所示。圖中，Sv為虛擬起點(diǎn)，S1與S2為前兩個(gè)時(shí)隙內(nèi)的地面目標(biāo)，A1與A2分別同時(shí)與兩個(gè)節(jié)點(diǎn)存在連接，且這兩個(gè)鏈路的容量之和比A1與A2的傳輸資源大，A1與A2無(wú)法同時(shí)滿足兩個(gè)鏈路的最大容量傳輸，所以需要進(jìn)行傳輸資源的分配。而B(niǎo)1、B2、C1與C2的傳輸資源等于與其連接的鏈路容量，所以無(wú)需建立虛擬節(jié)點(diǎn)。為A1與A2的虛擬節(jié)點(diǎn)，用來(lái)表示兩節(jié)點(diǎn)資源的受限。D1與D2為前兩個(gè)時(shí)隙內(nèi)的地面終點(diǎn)站，Dv則為虛擬終點(diǎn)。在RCTEG 中，除虛擬節(jié)點(diǎn)外，所有節(jié)點(diǎn)都與其在其他時(shí)隙的對(duì)應(yīng)節(jié)點(diǎn)由存儲(chǔ)鏈路相連。構(gòu)造RCTEG 的關(guān)鍵為，得到需要進(jìn)行資源分配的節(jié)點(diǎn)添加虛擬節(jié)點(diǎn)集VR3和通過(guò)節(jié)點(diǎn)之間的距離從而得到其能耗集E。

圖2 兩個(gè)時(shí)隙內(nèi)的RCTEG

2 基于RCTEG的節(jié)能資源分配算法

2.1 問(wèn)題模型

本文需要解決的問(wèn)題是尋找一種使網(wǎng)絡(luò)流量達(dá)到最大同時(shí)能耗較低的傳輸資源分配方案。在時(shí)間T內(nèi)，問(wèn)題可被描述為：

流守恒限制：流入節(jié)點(diǎn)與流出節(jié)點(diǎn)的流量相等。

在滿足容量限制與流守恒限制的條件下，本文問(wèn)題的優(yōu)化目標(biāo)為在不損耗網(wǎng)絡(luò)流量的同時(shí)降低能量消耗。

2.2 基于RCTEG的節(jié)能資源分配算法

基于RCTEG，本文提出了一種貪心的迭代尋找網(wǎng)絡(luò)中最小能耗資源分配方案的流擴(kuò)充算法（EERA,Energy Efficient Resource Allocation），在不損耗網(wǎng)絡(luò)吞吐量的同時(shí)，盡可能地減少網(wǎng)絡(luò)的總能耗。此算法在搜尋路徑時(shí)總是優(yōu)先尋找能耗較小的路徑并將節(jié)點(diǎn)的資源分配到此路徑內(nèi)，從而得到能耗較小的分配方案。

算法步驟如下。

首先，根據(jù)網(wǎng)絡(luò)的連通情況找到需要進(jìn)行資源分配的節(jié)點(diǎn)并構(gòu)造虛擬節(jié)點(diǎn)集VR2，此后，根據(jù)節(jié)點(diǎn)之間的距離獲得鏈路的能耗集E，構(gòu)造出當(dāng)前網(wǎng)絡(luò)的RCTEG。

第二步，在圖中，根據(jù)能耗集E找到網(wǎng)絡(luò)中從虛擬起點(diǎn)Sv到虛擬終點(diǎn)Dv的一條最小能耗路徑Pmin_cost，作為一條可擴(kuò)充流路徑。

第三步，根據(jù)容量集C沿此條路徑尋找各個(gè)鏈路的可擴(kuò)充流量，選擇各個(gè)鏈路中可擴(kuò)充流量的最小值作為該路徑的可擴(kuò)充流Δfp進(jìn)行流的擴(kuò)充，得到fp并更新容量集C。

此后，經(jīng)過(guò)流擴(kuò)充之后，進(jìn)行能耗集E的重構(gòu)，在E中為有流流過(guò)但未達(dá)到鏈路最大容量的邊添加反向邊能耗，達(dá)到鏈路容量的邊則只存在反向邊能耗。

最后，回到第二步，直到無(wú)法找到圖中從虛擬起點(diǎn)Sv到虛擬終點(diǎn)Dv的一條最小能耗路徑時(shí)，算法結(jié)束，并得到網(wǎng)絡(luò)的節(jié)能最大流量資源分配方案。

以圖2 中的兩個(gè)時(shí)隙內(nèi)網(wǎng)絡(luò)拓?fù)錇槔?，圖3 為EERA算法與Ford-Fulkerson 算法的分配方案對(duì)比。圖中綠色邊表示有流經(jīng)過(guò)，綠色數(shù)字表示經(jīng)過(guò)流的大小，紅色邊與紅色數(shù)字表示EERA 算法的不同資源分配選擇。

Ford-Fulkerson 算法得到的分配方案中（圖3（a）），鏈路中流過(guò)的流量為5，鏈路中流過(guò)的流量為15，而EERA 算法得到的分配方案中（圖3（b）），鏈路中流過(guò)的流量為15，鏈路中流過(guò)的流量為5。Ford-Fulkerson 算法與EERA 算法得到的網(wǎng)絡(luò)流量同為40，但EERA 算法網(wǎng)絡(luò)的總能耗為255，而Ford-Fulkerson 算法所得到的網(wǎng)絡(luò)能耗為300。

圖3 EERA算法與Ford-Fulkerson算法的資源分配對(duì)比

3 仿真實(shí)驗(yàn)

利用STK（Satellite Tool Kit，衛(wèi)星工具包），可以獲得衛(wèi)星網(wǎng)絡(luò)的連通情況與網(wǎng)絡(luò)各節(jié)點(diǎn)的距離，通過(guò)計(jì)算平均距離可得到衛(wèi)星鏈路的歸一化能耗。在仿真中，本文在兩個(gè)不同的網(wǎng)絡(luò)中對(duì)算法的性能進(jìn)行了驗(yàn)證。

兩種網(wǎng)絡(luò)場(chǎng)景下的地面目標(biāo)均為羅馬，地面站均為北京，仿真時(shí)間兩個(gè)小時(shí)。遙感衛(wèi)星的數(shù)目設(shè)置為2，位于太陽(yáng)同步軌道，高度為631 km，傾角為97.9°。中繼衛(wèi)星軌道高度為1 414 km，傾角為52°。遙感衛(wèi)星從地面獲取數(shù)據(jù)的速率設(shè)置均為120 Mbit/s，星間鏈路容量設(shè)置為20 Mbit/s，星地鏈路容量設(shè)置為30 Mbit/s。第一種網(wǎng)絡(luò)下中繼衛(wèi)星為(12/6/4)Walker 星座，共12 顆衛(wèi)星，第二種網(wǎng)絡(luò)下中繼衛(wèi)星為(18/6/4)Walker 星座，共18 顆衛(wèi)星。

在每種網(wǎng)絡(luò)場(chǎng)景中，分別進(jìn)行了兩組實(shí)驗(yàn)，第一組實(shí)驗(yàn)中將存儲(chǔ)能力設(shè)置為5 000 MB。傳輸資源在10～50 Mbit/s 之間變化。第二組實(shí)驗(yàn)中，傳輸資源設(shè)置為30 Mbit/s，存儲(chǔ)能力在3 500～6 500 MB 之間變化。對(duì)比算法采用了文獻(xiàn)[4]中采用的Ford-Fulkerson算法與Boykov-Kolmogorov算法[11]。

網(wǎng)絡(luò)中存在12 顆中繼衛(wèi)星時(shí)，三種算法的能耗、吞吐量隨傳輸資源變化而變化的對(duì)比如圖4。由圖4 可見(jiàn)，三種算法在不同傳輸資源下的吞吐量相同，而本文提出的EERA 算法的網(wǎng)絡(luò)總能耗小于其他兩種算法。網(wǎng)絡(luò)中存在18 顆中繼衛(wèi)星時(shí)的三種算法的性能對(duì)比如圖5。同樣地，三種算法的吞吐量相同，而EERA 算法的能耗要明顯小于其他兩種算法。且在相對(duì)復(fù)雜的網(wǎng)絡(luò)中，EERA 的節(jié)能效果較明顯。

圖4 12顆中繼衛(wèi)星時(shí)三種算法性能隨傳輸資源變化的對(duì)比

圖5 18顆中繼衛(wèi)星時(shí)三種算法性能隨傳輸資源變化的對(duì)比

第一種網(wǎng)絡(luò)下，三種算法的能耗與吞吐量隨衛(wèi)星節(jié)點(diǎn)的存儲(chǔ)能力變化的對(duì)比如圖6 所示。同樣可以看出，存儲(chǔ)能力變化的同時(shí)，三種算法的吞吐量相同，而EERA算法的能耗要小于其他兩種算法。第二種網(wǎng)絡(luò)下的三種算法隨存儲(chǔ)能力變化的性能對(duì)比如圖7。同樣地，EERA算法與其他兩種最大流算法得到的吞吐量相同而能耗要少于另外兩種算法。且在較為復(fù)雜的第二種網(wǎng)絡(luò)中，其能量消耗的減少較為明顯。

圖6 12顆中繼衛(wèi)星時(shí)三種算法性能隨存儲(chǔ)能力變化的對(duì)比

圖7 18顆中繼衛(wèi)星時(shí)三種算法性能隨傳輸能力變化的對(duì)比

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

本文考慮了衛(wèi)星網(wǎng)絡(luò)中地球觀測(cè)任務(wù)中，在衛(wèi)星節(jié)點(diǎn)傳輸資源受限情況下的傳輸資源分配問(wèn)題。基于時(shí)變圖，提出了一種貪心的迭代尋找網(wǎng)絡(luò)中最小能耗資源分配方案的流擴(kuò)充算法EERA，此算法可以在不損耗網(wǎng)絡(luò)吞吐量的條件下降低網(wǎng)絡(luò)能耗。通過(guò)與當(dāng)前已有研究的對(duì)比得到，此算法可有效降低能耗并不已犧牲吞吐量為代價(jià)。此外，算法在較復(fù)雜網(wǎng)絡(luò)中的效果更優(yōu)。下一步將考慮地面網(wǎng)絡(luò)與更復(fù)雜的衛(wèi)星星座融合的低能耗資源分配策略。