衛(wèi)星網(wǎng)絡(luò)時(shí)隙分配算法與路由規(guī)劃優(yōu)化

王瑞松, 馬若飛, 王 琦, 鐘志聰, 劉功亮,*, 張 楊

(1. 哈爾濱工業(yè)大學(xué)(威海)信息科學(xué)與工程學(xué)院, 山東 威海 264209;2. 北京跟蹤與通信技術(shù)研究所, 北京 100094;3. 航天東方紅衛(wèi)星有限公司, 北京 100094)

0 引 言

相對(duì)于地面網(wǎng)絡(luò),衛(wèi)星網(wǎng)絡(luò)具有覆蓋面超廣、速度快等獨(dú)特優(yōu)點(diǎn)。盡管衛(wèi)星網(wǎng)絡(luò)建設(shè)費(fèi)用昂貴,但因其具有獨(dú)特的優(yōu)勢(shì)而一直備受關(guān)注。一方面,雖然5G網(wǎng)絡(luò)正在不斷完善,但邊緣地區(qū)以及海上用戶服務(wù)一直沒能得到很好的解決。因此,為了進(jìn)一步提升用戶的服務(wù)質(zhì)量,一些學(xué)者提出了星地一體化網(wǎng)絡(luò)來解決這一問題。另一方面,衛(wèi)星網(wǎng)絡(luò)與人們息息相關(guān)并且已經(jīng)應(yīng)用到生活中的方方面面,如導(dǎo)航服務(wù)、地球觀測、深空探測等。因此,研究高效的衛(wèi)星網(wǎng)絡(luò)信息傳輸方法是非常重要的。然而,對(duì)衛(wèi)星網(wǎng)絡(luò)的研究也存在著一些挑戰(zhàn)。

(1) 網(wǎng)絡(luò)的動(dòng)態(tài)性。每個(gè)衛(wèi)星都按照自己的軌道進(jìn)行周期性的運(yùn)動(dòng),因此衛(wèi)星之間的相對(duì)位置是動(dòng)態(tài)變化的,也就是網(wǎng)絡(luò)拓?fù)涫菚r(shí)變的?？紤]到地球的遮擋,這種動(dòng)態(tài)性會(huì)影響到衛(wèi)星間的可見性,從而使得鏈路被迫中斷,進(jìn)而對(duì)網(wǎng)絡(luò)性能產(chǎn)生巨大影響。

(2) 資源的限制性。衛(wèi)星網(wǎng)絡(luò)的資源相比地面網(wǎng)絡(luò)是極其匱乏的。受限的資源包括能量、軌道、頻率、天線數(shù)目等。如何充分利用有限的資源來完成高質(zhì)量的服務(wù)是一個(gè)值得研究的問題。

正如上面所說,衛(wèi)星網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)性刻畫一直是當(dāng)前研究的重點(diǎn)。作為新興的方法,時(shí)間演化圖是當(dāng)前最有效的工具之一。文獻(xiàn)[7]提出了小衛(wèi)星網(wǎng)絡(luò)的資源沖突分析框架。首先將衛(wèi)星網(wǎng)絡(luò)周期劃分為多個(gè)時(shí)隙,每個(gè)時(shí)隙假設(shè)網(wǎng)絡(luò)拓?fù)涫遣蛔兊?。此時(shí),每個(gè)時(shí)隙的網(wǎng)絡(luò)拓?fù)淇梢韵鄳?yīng)地轉(zhuǎn)換為一個(gè)靜態(tài)圖。然后,考慮到衛(wèi)星網(wǎng)絡(luò)“接收-儲(chǔ)存-轉(zhuǎn)發(fā)”的特殊機(jī)制,引進(jìn)了儲(chǔ)存弧將每個(gè)時(shí)隙的靜態(tài)圖連接起來,從而形成一個(gè)整體的網(wǎng)絡(luò)拓?fù)鋱D。利用時(shí)間演化圖,文獻(xiàn)[8]和文獻(xiàn)[9]分析了衛(wèi)星網(wǎng)絡(luò)中的任務(wù)調(diào)度問題,包括衛(wèi)星建鏈與任務(wù)路由等問題。盡管時(shí)間演化圖對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涞奶幚砣〉昧撕芎玫男Ч?但是該方法難以面對(duì)長時(shí)間的拓?fù)渥兓?。這是由于圖的規(guī)模隨著時(shí)間而不斷增加。為了降低圖的復(fù)雜度,文獻(xiàn)[10]提出一種時(shí)間聚合圖的方法。雖然圖的規(guī)模始終固定,但是網(wǎng)絡(luò)的拓?fù)渥兓ㄟ^邊上的權(quán)重來刻畫。邊上的權(quán)重不再是一個(gè)數(shù)值,而是一個(gè)關(guān)于時(shí)間序列的向量,每個(gè)節(jié)點(diǎn)也賦予一個(gè)向量來刻畫每個(gè)時(shí)隙衛(wèi)星的儲(chǔ)存能力。相比于時(shí)間演化圖,時(shí)間聚合圖的復(fù)雜度降低了,但一些圖論知識(shí)并不能直接應(yīng)用。對(duì)于一些經(jīng)典問題,如最大流問題,一些新的求解方法需要進(jìn)一步研究。因此,文獻(xiàn)[10]和文獻(xiàn)[11]分別研究了“單源單目的”和“兩源兩目的”兩種場景下最優(yōu)任務(wù)流分配算法。

前面的工作在動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涮幚矸矫嬉呀?jīng)做出了先鋒性的工作,接下來重點(diǎn)研究的問題則是如何優(yōu)化網(wǎng)絡(luò)拓?fù)?也就是如何更好地規(guī)劃星間鏈路的建立以便于提升網(wǎng)絡(luò)的性能。一些學(xué)者針對(duì)不同的應(yīng)用場景已經(jīng)進(jìn)行了初步研究。在文獻(xiàn)[12]中,作者提出了一個(gè)理論模型用來估計(jì)兩個(gè)地面用戶之間的星間鏈路的跳數(shù),并且給出了跳數(shù)的空間分布特性。文獻(xiàn)[13]提出了一個(gè)協(xié)作方案,允許衛(wèi)星在與地面站接觸之前使用星間鏈路作為輔助方式來卸載數(shù)據(jù)。這樣衛(wèi)星將根據(jù)它們與地面站接觸的時(shí)間長度合理地分配數(shù)據(jù)量。在文獻(xiàn)[14]中,作者研究了星間鏈路衛(wèi)星導(dǎo)航網(wǎng)絡(luò)中的應(yīng)用,并且在全球?qū)Ш叫l(wèi)星系統(tǒng)精確定軌的測距約束下優(yōu)化了網(wǎng)絡(luò)時(shí)延與吞吐量。文獻(xiàn)[15]考慮了地球自轉(zhuǎn)和平面間相位差,給出了一種優(yōu)化的星間鏈路建立方法來最大化可用鏈路。一些學(xué)者還研究了星間鏈路在衛(wèi)星光網(wǎng)絡(luò)中的應(yīng)用。文獻(xiàn)[18]研究了一種基于編碼輔助技術(shù)的全球?qū)Ш叫l(wèi)星系統(tǒng)星間鏈路自適應(yīng)窄帶干擾抑制方案,從而保證星間鏈路的可靠性。因此,星間鏈路的優(yōu)化是十分必要的,這也促使了本文的研究。

對(duì)于給定的網(wǎng)絡(luò)拓?fù)?路由協(xié)議設(shè)計(jì)則是影響網(wǎng)絡(luò)性能的關(guān)鍵因素。然而,隨著衛(wèi)星網(wǎng)絡(luò)規(guī)模的不斷增大和任務(wù)類型的復(fù)雜性越來越高,路由問題也面臨更多挑戰(zhàn)。為了克服這些難點(diǎn),各種先進(jìn)的路由技術(shù)被研究。例如,文獻(xiàn)[19]采用了一種時(shí)態(tài)網(wǎng)格模型來描述大規(guī)模網(wǎng)絡(luò)的時(shí)變拓?fù)洹Ｈ缓?取代了傳統(tǒng)的坐標(biāo)定位方法,衛(wèi)星可以通過網(wǎng)格來進(jìn)行定位。文獻(xiàn)[20]提出了一種基于網(wǎng)絡(luò)編碼的協(xié)同路由方法。通過編碼的方法,數(shù)據(jù)可以通過多條路徑協(xié)同傳輸從而加快傳輸速度。文獻(xiàn)[21]提出了聯(lián)合路由和調(diào)度的跨層機(jī)載處理設(shè)計(jì),推導(dǎo)了聯(lián)合分組路由和波束調(diào)度的最佳策略。文獻(xiàn)[22]分析了“存儲(chǔ)-轉(zhuǎn)發(fā)”模式下最優(yōu)路由的計(jì)算復(fù)雜度,證實(shí)了獲得最優(yōu)路由是十分困難的。文獻(xiàn)[23-25]從能量的角度設(shè)計(jì)了路由算法。文獻(xiàn)[26]用增強(qiáng)學(xué)習(xí)的方法求解了多目標(biāo)路由規(guī)劃。文獻(xiàn)[27]則研究了超大規(guī)模衛(wèi)星網(wǎng)絡(luò)下的路由分發(fā)機(jī)制。文獻(xiàn)[28-30]從服務(wù)質(zhì)量、實(shí)時(shí)性以及安全性的角度對(duì)路由方案進(jìn)行了研究。

綜合上面的分析,本文研究了星間鏈路規(guī)劃和路由規(guī)劃。首先,利用時(shí)間演化圖的方法,將衛(wèi)星網(wǎng)絡(luò)的動(dòng)態(tài)性變化刻畫在一張靜態(tài)圖上。然后,著重考慮衛(wèi)星網(wǎng)絡(luò)的資源限制條件,提出一種基于最大加權(quán)匹配的建鏈方法。為了降低求解算法的復(fù)雜度,利用拉格朗日松弛法來設(shè)計(jì)一個(gè)低復(fù)雜度的分布式算法。然后對(duì)于給定建鏈方法,設(shè)計(jì)不同優(yōu)先級(jí)任務(wù)的路由規(guī)劃。從仿真結(jié)果來看,通過提出的算法得到的解與最優(yōu)解基本沒有差別。

1 系統(tǒng)模型

本文考慮了一個(gè)一般的動(dòng)態(tài)衛(wèi)星網(wǎng)絡(luò),包含多個(gè)軌道,每個(gè)軌道上又分布著多個(gè)衛(wèi)星,用來覆蓋全球的區(qū)域。假設(shè)整個(gè)衛(wèi)星網(wǎng)絡(luò)由個(gè)衛(wèi)星組成。由于衛(wèi)星的軌道是確定的且衛(wèi)星的運(yùn)轉(zhuǎn)是周期的,因此衛(wèi)星網(wǎng)絡(luò)的拓?fù)渥兓彩侵芷诘?。所以只需要研究衛(wèi)星網(wǎng)絡(luò)在一個(gè)周期內(nèi)的拓?fù)錉顩r就可以了,也就是[0,]。

圖1給出了衛(wèi)星網(wǎng)絡(luò)時(shí)間演化圖的具體例子。其中紅色的弧表示儲(chǔ)存弧,黑色的表示鏈路弧。由于鏈路弧是雙向的,在演化圖中兩個(gè)節(jié)點(diǎn)之間的建鏈?zhǔn)菍?duì)稱的。儲(chǔ)存弧是單向的,表明數(shù)據(jù)只能從當(dāng)前時(shí)隙儲(chǔ)存在下一時(shí)隙,而不能反向?yàn)橹＞唧w地,假設(shè)源節(jié)點(diǎn)為第2個(gè)節(jié)點(diǎn),目的節(jié)點(diǎn)為第5個(gè)節(jié)點(diǎn),所有邊權(quán)重都一樣。通過最短路徑算法可以得到最優(yōu)結(jié)果為第2個(gè)節(jié)點(diǎn)首先傳到第4個(gè)節(jié)點(diǎn),節(jié)點(diǎn)數(shù)據(jù)在第4個(gè)節(jié)點(diǎn)緩存一個(gè)時(shí)隙,接著下一時(shí)隙第4個(gè)節(jié)點(diǎn)傳到第5個(gè)節(jié)點(diǎn)。

圖1 衛(wèi)星網(wǎng)絡(luò)時(shí)間演化圖Fig.1 Time evolution graph of satellite network

2 算法設(shè)計(jì)

2.1 基本約束

首先,考慮網(wǎng)絡(luò)中的數(shù)據(jù)流在每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的流通情況。對(duì)于給定的時(shí)間擴(kuò)展圖,由于衛(wèi)星網(wǎng)絡(luò)中的數(shù)據(jù)流通采用的是“接收-儲(chǔ)存-轉(zhuǎn)發(fā)”的機(jī)制,因此對(duì)于每個(gè)時(shí)隙而言,每個(gè)衛(wèi)星接收到的數(shù)據(jù)量加上上一時(shí)隙緩存下來的數(shù)據(jù)量應(yīng)該等于當(dāng)前時(shí)隙發(fā)送出去的數(shù)據(jù)量加上未發(fā)送而儲(chǔ)存在該節(jié)點(diǎn)中的數(shù)據(jù)量。因此,可以給出以下約束:

(1)

對(duì)于任務(wù)的起始點(diǎn)來說,任務(wù)的發(fā)出總量應(yīng)該等于當(dāng)前時(shí)隙任務(wù)成功發(fā)送出去的數(shù)據(jù)量加上儲(chǔ)存在節(jié)點(diǎn)的數(shù)據(jù)量,具體地,

(2)

對(duì)于任務(wù)的目的節(jié)點(diǎn)來說,任務(wù)只允許到達(dá)目的節(jié)點(diǎn)并存儲(chǔ),而不允許再次發(fā)送,因此需要將目的節(jié)點(diǎn)的發(fā)送量設(shè)為0。

(3)

根據(jù)前文敘述,由于資源的限制,對(duì)每個(gè)時(shí)隙而言,即使每個(gè)衛(wèi)星可能與多個(gè)衛(wèi)星可見,但是每個(gè)衛(wèi)星只能與一個(gè)衛(wèi)星進(jìn)行建鏈。即

(4)

(5)

考慮到網(wǎng)絡(luò)傳輸機(jī)制的特殊性,每條鏈接都是一個(gè)雙向鏈接。相應(yīng)地,在圖中也就是無向邊。因此,有如下約束:

(6)

然而,考慮到鏈路資源的限制,對(duì)于給定的時(shí)隙,如果兩個(gè)節(jié)點(diǎn)建立鏈路,則傳輸?shù)目倲?shù)據(jù)量不能超出鏈路最大傳輸能力;如果兩個(gè)節(jié)點(diǎn)沒有建立鏈路,則不能傳輸數(shù)據(jù)。對(duì)于這一限制,可以通過如下約束來表示:

(7)

2.2 目標(biāo)函數(shù)與模型

(8)

本文致力于一個(gè)公平性的資源分配規(guī)劃,也就是最小化每個(gè)衛(wèi)星節(jié)點(diǎn)花費(fèi)的最大值。

(9)

通過上面的敘述,最終的優(yōu)化問題可以表示如下:

(10)

通過上面給定的變量與約束條件,最終將衛(wèi)星網(wǎng)絡(luò)中資源分配優(yōu)化問題建模為一個(gè)整數(shù)線性規(guī)劃問題。這樣一個(gè)優(yōu)化問題的求解是十分困難的。窮舉法是處理整數(shù)規(guī)劃的一個(gè)可行方法,但是窮舉法的求解復(fù)雜度為指數(shù)復(fù)雜度,僅對(duì)于規(guī)模較小的整數(shù)規(guī)劃是很有效的。對(duì)于上述的大規(guī)模優(yōu)化問題而言,即便是能夠?qū)⒆顑?yōu)解找出,付出的計(jì)算代價(jià)也是十分大的,并且計(jì)算時(shí)間過長從而難以滿足實(shí)時(shí)性的要求。因此,計(jì)算才是該問題的最大難點(diǎn)。為了保證在實(shí)際應(yīng)用中的可行性,本文將原問題分解為兩個(gè)子問題,分別為時(shí)隙分配方案設(shè)計(jì)與路由規(guī)劃設(shè)計(jì)。雖然這并不是等價(jià)的轉(zhuǎn)化,但是分解后的求解效率顯著提升。

3 時(shí)隙分配方案設(shè)計(jì)

本節(jié)將上面的整數(shù)線性規(guī)劃問題分解為兩個(gè)問題,分別為時(shí)隙分配方案設(shè)計(jì)與路由規(guī)劃設(shè)計(jì)。對(duì)于時(shí)隙分配方案,本節(jié)采用了最大加權(quán)匹配與拉格朗日松弛相結(jié)合的方法來設(shè)計(jì)低復(fù)雜度的算法。

本文提出的算法充分利用了衛(wèi)星網(wǎng)絡(luò)拓?fù)涞囊阎蛩?包括星間可行性關(guān)系、軌道、星間距離等。在初始階段,通過地面站或者高軌控制衛(wèi)星將網(wǎng)絡(luò)的全局信息發(fā)送給每個(gè)衛(wèi)星。然后,每個(gè)衛(wèi)星可以獨(dú)立地運(yùn)行提出的算法,計(jì)算出整個(gè)網(wǎng)絡(luò)的時(shí)隙分配結(jié)果,并且所有衛(wèi)星計(jì)算的結(jié)果都是相同的。將當(dāng)前計(jì)算的結(jié)果作為下一次算法運(yùn)行的初始條件,則算法可以一直運(yùn)行下去,并能保證所有衛(wèi)星的同步。通過這樣的方式就可以實(shí)現(xiàn)網(wǎng)絡(luò)的全局控制而不需要特意的控制器。

3.1 基于匹配理論的方案

對(duì)于衛(wèi)星系統(tǒng)時(shí)隙分配而言,一方面,在每個(gè)時(shí)刻,給定衛(wèi)星可見性分析表,盡管每顆衛(wèi)星可能與多個(gè)衛(wèi)星可見,但每顆衛(wèi)星仍然只與一顆衛(wèi)星建立鏈接;另一方面,由于數(shù)據(jù)的發(fā)送通常需要多跳才能到達(dá),而每個(gè)時(shí)隙最多只能完成一跳傳輸,網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)男阅芤笸Q于多個(gè)時(shí)隙的聯(lián)合分配結(jié)果。

根據(jù)上面的模型與問題分析,可以看到時(shí)隙分配方案在一個(gè)周期內(nèi)是相關(guān)的。每個(gè)時(shí)隙的匹配結(jié)果不僅受到之前時(shí)隙的匹配結(jié)果的影響,而且將影響到后續(xù)時(shí)隙的匹配結(jié)果。然而,對(duì)于一個(gè)長周期內(nèi)的時(shí)隙分配而言,直接求解是十分復(fù)雜的。因此,有必要將問題的求解在時(shí)間上進(jìn)行分解。

給定一個(gè)無向圖,如果存在一個(gè)子圖?使得圖中每個(gè)節(jié)點(diǎn)只與一個(gè)節(jié)點(diǎn)相鄰,則稱其為一個(gè)匹配。如果||最大,則稱其為最大匹配。其中||表示圖中邊的總數(shù)目。

然而,最大匹配僅僅能保證每個(gè)時(shí)隙衛(wèi)星之間盡可能建鏈,但是不能保證網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)男阅?。因?為了保證數(shù)據(jù)傳輸?shù)男阅?需要介紹最大加權(quán)匹配的概念,通過對(duì)每個(gè)邊進(jìn)行賦權(quán)來盡可能達(dá)到數(shù)據(jù)傳輸?shù)囊欢ㄐ阅?。最大加?quán)匹配的概念如下。

給定一個(gè)無向圖,如果存在一個(gè)子圖?使得圖中每個(gè)節(jié)點(diǎn)只與一個(gè)節(jié)點(diǎn)相鄰,則稱其為一個(gè)匹配。如果圖的總權(quán)重值最大,則稱其為最大加權(quán)匹配。

對(duì)于最大加權(quán)匹配,下面給出一個(gè)圖來展示具體的流程。如圖2所示,根據(jù)網(wǎng)絡(luò)的可見性分析,首先建立網(wǎng)絡(luò)的拓?fù)溥B通關(guān)系,然后根據(jù)一定的規(guī)則,對(duì)每條邊進(jìn)行一定的權(quán)重設(shè)置。當(dāng)權(quán)重設(shè)置完畢之后,通過特定的算法求解最大加權(quán)匹配,得到最終結(jié)果。

圖2 最大加權(quán)匹配流程圖Fig.2 Maximum weighted matching flow chart

圖2中的最大加權(quán)匹配主要涉及到兩方面的內(nèi)容,分別為權(quán)重的設(shè)置和最大加權(quán)匹配的求解。對(duì)于權(quán)重的設(shè)置而言,考慮到每個(gè)時(shí)隙的匹配具有時(shí)間相關(guān)性,為了將時(shí)間上的耦合分解,這里將時(shí)間上的相關(guān)性轉(zhuǎn)換到權(quán)重的設(shè)置上,從而實(shí)現(xiàn)時(shí)間上的分離。也就是說,當(dāng)前時(shí)隙每條邊權(quán)重的設(shè)置要根據(jù)之前時(shí)隙的邊匹配情況來設(shè)置。下面將描述具體的賦權(quán)規(guī)則。

3.2 權(quán)重設(shè)置規(guī)則

(1) 持續(xù)建鏈規(guī)則。如果上一時(shí)隙衛(wèi)星節(jié)點(diǎn)沒有與其他節(jié)點(diǎn)進(jìn)行建鏈,則在上一時(shí)隙衛(wèi)星所儲(chǔ)存的任務(wù)就會(huì)有一定程度的堆積?？紤]到這種情況,這里采取了一種補(bǔ)償機(jī)制,也就是這類衛(wèi)星節(jié)點(diǎn)優(yōu)先與其他節(jié)點(diǎn)建立鏈接, 則權(quán)重賦值數(shù)學(xué)表示如下:

(11)

(2) 不重復(fù)鏈路建立。如果兩個(gè)衛(wèi)星上一個(gè)時(shí)隙或在一定時(shí)間內(nèi)已經(jīng)建立過通信鏈路,則在當(dāng)前時(shí)隙傾向不再重復(fù)建立鏈路。這是因?yàn)椴煌瑪?shù)據(jù)的目的節(jié)點(diǎn)也是不同的,更換鏈路有助于保證資源分配的公平性,避免某一數(shù)據(jù)長時(shí)間等待。因此,對(duì)于重復(fù)的鏈路,在邊的權(quán)重賦值上進(jìn)行減少,在規(guī)定的時(shí)間內(nèi),建鏈次數(shù)越多,則權(quán)重越小。最終權(quán)重賦值數(shù)學(xué)表達(dá)為

(12)

式中:是一個(gè)正常數(shù)，表示時(shí)間的范圍。

(3) 跨軌道建鏈。網(wǎng)絡(luò)中衛(wèi)星分布在不同的軌道上,每個(gè)衛(wèi)星都需要向其他所有衛(wèi)星發(fā)送信息。為了保證信息能夠均勻地發(fā)送,衛(wèi)星建鏈對(duì)象應(yīng)該考慮軌道之間的差異性。為了盡可能使網(wǎng)絡(luò)連通,給定上一時(shí)隙衛(wèi)星匹配對(duì)象的軌道,則在當(dāng)前時(shí)刻衛(wèi)星旨在與其他軌道的衛(wèi)星進(jìn)行建鏈。具體的權(quán)重賦值規(guī)則表示如下:

(13)

(4) 短距離建鏈。這一權(quán)重賦值在時(shí)間上并沒有相關(guān)性,僅僅考慮網(wǎng)絡(luò)傳輸?shù)目煽啃?即衛(wèi)星之間相同情況下以短距離傳輸為準(zhǔn)則,則權(quán)重賦值數(shù)學(xué)表示如下:

(14)

式中:,,是正常數(shù),表示權(quán)重更新步長。上面4個(gè)鏈路加權(quán)規(guī)則可以分為3個(gè)優(yōu)先級(jí)。其中,持續(xù)建鏈規(guī)則為第一優(yōu)先級(jí);不重復(fù)鏈路建立規(guī)則和跨軌道建鏈規(guī)則為第二優(yōu)先級(jí);短距離建鏈規(guī)則為第三優(yōu)先級(jí)。在持續(xù)建鏈規(guī)則中,如果上一時(shí)隙衛(wèi)星節(jié)點(diǎn)沒有與其他節(jié)點(diǎn)進(jìn)行建鏈,則在上一時(shí)隙衛(wèi)星所儲(chǔ)存的任務(wù)就會(huì)有一定程度的堆積。因此,為了公平性原則,務(wù)必要保證衛(wèi)星在當(dāng)前時(shí)隙成功建鏈。所以,在持續(xù)建鏈規(guī)則中的權(quán)重更新步長是比較大的,以此來體現(xiàn)其高優(yōu)先級(jí)。對(duì)于兩個(gè)第二優(yōu)先級(jí)的規(guī)則,從本文的角度來說,兩者并沒有什么特別的差異性。這兩個(gè)規(guī)則本質(zhì)上都是保證衛(wèi)星建鏈的多樣性。因此,將這兩個(gè)規(guī)則設(shè)為同一優(yōu)先級(jí)。對(duì)于處在最低優(yōu)先級(jí)的短距離建鏈規(guī)則,這個(gè)規(guī)則的設(shè)計(jì)初衷是防止出現(xiàn)兩個(gè)相同的權(quán)重值。原因是相同的權(quán)重值在問題求解時(shí)會(huì)導(dǎo)致多個(gè)解的產(chǎn)生。對(duì)于相同權(quán)重值的情況,我們傾向于短距離的鏈路,因?yàn)檫@樣的鏈路通常通信質(zhì)量更有保障。因此,考慮到優(yōu)先級(jí)的差異性,在最終確定權(quán)重的時(shí)候只要保證一個(gè)原則即可,那就是第一優(yōu)先級(jí)的權(quán)重更新步長要大于第二優(yōu)先級(jí)的權(quán)重更新步長,第二優(yōu)先級(jí)的權(quán)重更新步長要大于第三優(yōu)先級(jí)的權(quán)重更新步長。也就是說,要滿足>>1,>>1。

3.3 基于拉格朗日松弛的求解算法

通過上面的賦權(quán)規(guī)則,已經(jīng)對(duì)每條邊上的權(quán)重做了設(shè)置,整個(gè)時(shí)隙分配問題可以轉(zhuǎn)化為每個(gè)時(shí)隙上的一個(gè)最大加權(quán)匹配問題。對(duì)于這樣一個(gè)問題,本文采用了基于拉格朗日松弛的求解方法,設(shè)計(jì)了一個(gè)低復(fù)雜度的算法。

最大加權(quán)匹配問題可以建模為一個(gè)0～1線性規(guī)劃問題。具體地,給定當(dāng)前時(shí)隙演化圖中邊的權(quán)重,則最大加權(quán)匹配問題可以轉(zhuǎn)化為如下優(yōu)化問題:

(15)

對(duì)于這樣的一個(gè)整數(shù)線性規(guī)劃,雖然最優(yōu)解可以通過分支定界法來求得,但是求解復(fù)雜度極高。因此,本文采用拉格朗日松弛的方法設(shè)計(jì)一個(gè)低復(fù)雜度算法并求得一個(gè)次優(yōu)解。

證畢

根據(jù)以上說明, 優(yōu)化問題(15)等價(jià)于如下問題:

(16)

(17)

將問題進(jìn)行整理可以得到

(18)

(19)

證畢

(20)

(21)

(22)

(23)

通過上面的置零操作,已經(jīng)得到了一個(gè)可行解。但是,這個(gè)可行解里面可能存在多個(gè)未匹配節(jié)點(diǎn)。因此,為了進(jìn)一步提升性能,可以對(duì)未匹配的節(jié)點(diǎn)進(jìn)行一次檢測,重新再做一次匹配。具體地,從得到的解中提取出與任何節(jié)點(diǎn)都沒建鏈的節(jié)點(diǎn)集合,記錄彼此之間的權(quán)重值,構(gòu)成新的權(quán)重矩陣。執(zhí)行上面的步驟求得新集合的最大加權(quán)匹配結(jié)果,將匹配結(jié)果添加到原來求解的結(jié)果中去。如果還有未匹配的節(jié)點(diǎn),則繼續(xù)執(zhí)行上面的步驟,直到最終匹配結(jié)果不再改變。具體的內(nèi)容可以參考下面的算法1。

算法 1 時(shí)隙分配求解算法1. 輸入:初始的權(quán)重矩陣, 拉格朗日乘子, 時(shí)間長度T, 最大迭代次數(shù)Imax, 門限值ε, 衛(wèi)星可見性分析表。2. 輸出:每個(gè)時(shí)隙的衛(wèi)星匹配建鏈表##拉格朗日松弛算法求解過程(3～15行)3. 根據(jù)式(11)～式(14)更新權(quán)重矩陣4. fort=1:T5. fork=1:Imax6. 根據(jù)式(19), 計(jì)算時(shí)隙分配結(jié)果7. 計(jì)算問題(17)中的目標(biāo)函數(shù)值F(i)8. if |F(k)-F(k-1)|/F(k)<ε9. 停止迭代10. else11. 根據(jù)式(20)更新拉格朗日乘子12. end13. end 14. 根據(jù)式(22),計(jì)算新的權(quán)重矩陣β15. 根據(jù)式(23),對(duì)結(jié)果進(jìn)行處理##優(yōu)化解提升過程(16～22行)16. while存在衛(wèi)星尚未匹配17. 對(duì)權(quán)重矩陣,刪除已匹配衛(wèi)星對(duì)應(yīng)的行與列,形成新的權(quán)重矩陣18. 執(zhí)行步驟3～步驟15, 獲得新的匹配結(jié)果,更新匹配表19. if匹配表不再變化20. 跳出循環(huán),輸出最終匹配表21. end22. end23.end

3.4 算法分析

從算法1可以看出,對(duì)于給定的時(shí)間長度,所提出的算法是對(duì)每個(gè)時(shí)隙進(jìn)行求解的。對(duì)于每個(gè)時(shí)隙而言,總共的變量數(shù)為個(gè),其中為衛(wèi)星數(shù)目,對(duì)于每一次的迭代,只需要對(duì)每個(gè)變量進(jìn)行直接更新就可以,且算法在有限步內(nèi)收斂,因此每個(gè)時(shí)隙的求解復(fù)雜度為(),整個(gè)算法的復(fù)雜度為()。

提出的時(shí)隙分配算法主要應(yīng)用了衛(wèi)星網(wǎng)絡(luò)拓?fù)涞目深A(yù)測性。盡管衛(wèi)星網(wǎng)絡(luò)是動(dòng)態(tài)變化的,但是它與普通的時(shí)變網(wǎng)絡(luò)是不同的,由于軌道是固定的,衛(wèi)星每時(shí)每刻的位置都是可以提前計(jì)算的。算法的實(shí)際應(yīng)用可通過兩種方法實(shí)現(xiàn)。第一種方法是地面站將一段時(shí)間內(nèi)的時(shí)隙分配結(jié)果提前計(jì)算好,然后將其發(fā)送給每個(gè)衛(wèi)星。這樣雖然會(huì)增加衛(wèi)星通信成本,但是增加不是很顯著,這是因?yàn)橐欢螘r(shí)間內(nèi)只需要通信一次即可。另一種方法是每個(gè)衛(wèi)星獨(dú)立地執(zhí)行相同的算法,不需要進(jìn)行信息的交換與收集就可以得到相同的結(jié)果。采用這個(gè)方法不需要任何通信成本,但是每個(gè)衛(wèi)星需要付出計(jì)算成本。

4 延遲最小化的路由方案

4.1 路由算法設(shè)計(jì)

通過上面的時(shí)隙分配方法,可以得到每個(gè)時(shí)隙各個(gè)衛(wèi)星的建鏈情況。然后,通過儲(chǔ)存弧,可以將一個(gè)周期內(nèi)動(dòng)態(tài)圖轉(zhuǎn)化為一個(gè)靜態(tài)圖。在知道網(wǎng)絡(luò)全局信息的前提下,多個(gè)信息流的路由規(guī)劃可以通過求解一個(gè)大型線性規(guī)劃來得到相應(yīng)的路由。然而,對(duì)于衛(wèi)星網(wǎng)絡(luò)而言,每個(gè)衛(wèi)星都掌握整個(gè)網(wǎng)絡(luò)的全局信息是十分困難的。相反,每個(gè)衛(wèi)星通常只知道臨近衛(wèi)星的信息或者不知道任何衛(wèi)星的具體信息。

給定網(wǎng)絡(luò)拓?fù)鋱D,對(duì)于單個(gè)的任務(wù)流,其路由問題可以轉(zhuǎn)化為網(wǎng)絡(luò)中的最短路徑問題。 Dijkstra最短路徑算法是求解單源單目的數(shù)據(jù)流的一個(gè)最優(yōu)路由算法。給定每條路徑的權(quán)重,Dijkstra算法即可在多項(xiàng)式復(fù)雜度內(nèi)找到從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最優(yōu)路徑。

本文考慮以延遲作為每條路徑的花費(fèi)。因此,根據(jù)前面提出的網(wǎng)絡(luò)模型,定義每一條邊的權(quán)重為當(dāng)前鏈路的傳輸時(shí)延:

(24)

對(duì)于每個(gè)數(shù)據(jù)流來說,由于鏈路容量限制,不一定在同一時(shí)隙全部到達(dá)目的節(jié)點(diǎn)。因此對(duì)于每個(gè)節(jié)點(diǎn),還需要設(shè)置一個(gè)虛擬目的節(jié)點(diǎn),用來連接每一個(gè)時(shí)隙的節(jié)點(diǎn)。此虛擬節(jié)點(diǎn)與每個(gè)時(shí)隙對(duì)應(yīng)節(jié)點(diǎn)進(jìn)行建鏈,每條鏈路的權(quán)重設(shè)置為0,表示該數(shù)據(jù)流在任意時(shí)隙到達(dá)都可以。另一方面,考慮到不同的數(shù)據(jù)流之間是有差異性的,先入先出的規(guī)則不再適用,而改為高優(yōu)先級(jí)數(shù)據(jù)先出,低優(yōu)先級(jí)數(shù)據(jù)后出。數(shù)據(jù)的優(yōu)先級(jí)是根據(jù)業(yè)務(wù)的類型來確定的。例如,衛(wèi)星網(wǎng)絡(luò)中支持的業(yè)務(wù)包括自主導(dǎo)航業(yè)務(wù)、遙測回傳業(yè)務(wù)、全球短報(bào)文業(yè)務(wù)、其他擴(kuò)展服務(wù)業(yè)務(wù)等。與之對(duì)應(yīng),星間鏈路支持傳輸?shù)臄?shù)據(jù)類型包括:自主導(dǎo)航數(shù)據(jù)、遙控?cái)?shù)據(jù)、遙測數(shù)據(jù)、確認(rèn)數(shù)據(jù)、擴(kuò)展應(yīng)用數(shù)據(jù)、備用數(shù)據(jù)類型等。這些數(shù)據(jù)的服務(wù)質(zhì)量要求也不完全相同。像導(dǎo)航業(yè)務(wù)這種對(duì)實(shí)時(shí)性要求很強(qiáng)的通常優(yōu)先級(jí)較高,需要盡快傳輸。而像一些長期觀測業(yè)務(wù)則對(duì)實(shí)時(shí)性要求不強(qiáng),只需要能夠最終能夠準(zhǔn)確傳到目的地即可,因此這類業(yè)務(wù)優(yōu)先級(jí)則較低。

當(dāng)一個(gè)數(shù)據(jù)流產(chǎn)生時(shí),源節(jié)點(diǎn)首先為每個(gè)數(shù)據(jù)根據(jù)其優(yōu)先級(jí)依次進(jìn)行路由規(guī)劃。然后,每個(gè)數(shù)據(jù)按照相應(yīng)的路由進(jìn)行發(fā)送。然而,當(dāng)衛(wèi)星節(jié)點(diǎn)發(fā)送數(shù)據(jù)的時(shí)候,由于鏈路弧容量有限,不能保證所有的數(shù)據(jù)都能在此時(shí)隙成功發(fā)送。當(dāng)產(chǎn)生擁塞時(shí),高優(yōu)先級(jí)的數(shù)據(jù)首先進(jìn)行發(fā)送,剩余的低優(yōu)先級(jí)的數(shù)據(jù)由于當(dāng)前時(shí)隙發(fā)送失敗從而導(dǎo)致原來的路由不再適用。為了保證剩余的緩存包能夠成功發(fā)送出去,則當(dāng)前的衛(wèi)星節(jié)點(diǎn)必須為它重新規(guī)劃路由。為了保證數(shù)據(jù)的成功發(fā)送,衛(wèi)星接收到的數(shù)據(jù)包應(yīng)該包含以下基本信息:基本數(shù)據(jù),目的節(jié)點(diǎn),數(shù)據(jù)包長度,初始路由,優(yōu)先級(jí)等。具體的步驟可以參考算法2。

算法 2 不同優(yōu)先級(jí)數(shù)據(jù)包的路由算法1. 輸入:時(shí)隙分配表, 數(shù)據(jù)包基本信息2. 輸出:每個(gè)數(shù)據(jù)包的路由表3. 檢測當(dāng)前節(jié)點(diǎn)中緩存中的數(shù)據(jù), 選取出當(dāng)前時(shí)隙可以發(fā)送的數(shù)據(jù)4. 將這些數(shù)據(jù)包按照優(yōu)先級(jí)從高到低排序, 并假設(shè)總數(shù)目為M,包的長度為p(m)5. form=1:M6. ifC>p(m)7. 準(zhǔn)備發(fā)送該數(shù)據(jù)包,更新鏈路容量C=C-p(m)8. else9. 該數(shù)據(jù)包進(jìn)行等待, 重新規(guī)劃路由10. end11. end

4.2 算法擴(kuò)展

盡管算法2考慮了以延遲為目標(biāo)的路由設(shè)計(jì)方案,但是該算法仍可以進(jìn)一步擴(kuò)展從而可以滿足業(yè)務(wù)多樣性的要求。主要從兩方面進(jìn)行擴(kuò)展:一個(gè)是權(quán)重函數(shù)的設(shè)計(jì);另一個(gè)為業(yè)務(wù)優(yōu)先級(jí)的權(quán)衡。

首先是權(quán)重函數(shù)的設(shè)計(jì),權(quán)重的設(shè)計(jì)根據(jù)目標(biāo)的不同可以進(jìn)行自適應(yīng)更改,并不一定非要將延遲作為鏈路的權(quán)重。比如,將跳數(shù)作為評(píng)判鏈路的準(zhǔn)則,權(quán)重的賦值規(guī)則就可以更改為

(25)

式中:≠表示數(shù)據(jù)要經(jīng)過一跳來進(jìn)行發(fā)送,因此將權(quán)值設(shè)置為1;而=表示數(shù)據(jù)將會(huì)緩存而等待下一個(gè)時(shí)隙發(fā)送,因此將權(quán)值設(shè)置為0。更進(jìn)一步,一些業(yè)務(wù)對(duì)跳數(shù)和時(shí)延具有雙重要求,則在權(quán)重設(shè)計(jì)時(shí)通過加權(quán)的方法兼顧考慮,通過設(shè)置權(quán)重因子的大小,自適應(yīng)加權(quán)規(guī)則如下:

(26)

當(dāng)業(yè)務(wù)產(chǎn)生的時(shí)候,衛(wèi)星可以根據(jù)數(shù)據(jù)類型的不同,自適應(yīng)地選擇賦權(quán)規(guī)則,然后執(zhí)行該路由算法。

5 仿真分析

如圖3所示,通過STK軟件,本文建立了一個(gè)由32顆中軌衛(wèi)星組成的網(wǎng)絡(luò)。網(wǎng)絡(luò)包含4個(gè)軌道,每個(gè)軌道上均勻地分布著8顆衛(wèi)星。對(duì)于這樣一個(gè)網(wǎng)絡(luò),衛(wèi)星之間的距離比較大,通信成本比較高,不適合過多地進(jìn)行信息交換。此網(wǎng)絡(luò)正好適用于本文提出的低通信成本算法,因此本文將其作為代表來評(píng)估算法的性能。根據(jù)第2節(jié)的網(wǎng)絡(luò)模型描述,衛(wèi)星網(wǎng)絡(luò)運(yùn)行周期被劃分為多個(gè)時(shí)隙,在每個(gè)時(shí)隙內(nèi),每個(gè)衛(wèi)星至多與一個(gè)衛(wèi)星建立鏈接。一旦鏈路建立,則鏈路一直持續(xù)到該時(shí)隙結(jié)束,單個(gè)時(shí)隙內(nèi)不允許重新建鏈。在當(dāng)前時(shí)隙,如果任務(wù)不能完全發(fā)送,則儲(chǔ)存到本地儲(chǔ)存器并等待下一時(shí)隙建鏈后發(fā)送或者繼續(xù)儲(chǔ)存。詳細(xì)的參數(shù)設(shè)置請(qǐng)參考表1。

圖3 衛(wèi)星網(wǎng)絡(luò)組成圖Fig.3 Satellite network composition

表1 仿真參數(shù)

為了展示提出算法的性能,在仿真時(shí)將本文提出的算法與對(duì)應(yīng)的算法進(jìn)行了對(duì)比。仿真圖中的“基于拉格朗日松弛的方案”為本文提出的算法的性能,而“基于最優(yōu)匹配的方案”是相應(yīng)的對(duì)比算法。

基于最優(yōu)匹配的方案采用整數(shù)規(guī)劃算法(例如,分支定界法、枚舉法等)求解對(duì)應(yīng)的匹配問題式(16),因此得到的是一個(gè)最優(yōu)匹配方案,其他部分與算法1和算法2的操作部分一樣。

在圖4和圖5中,假設(shè)每個(gè)衛(wèi)星都要向剩余的31個(gè)衛(wèi)星傳遞相同優(yōu)先級(jí)的數(shù)據(jù)。衛(wèi)星與衛(wèi)星之間發(fā)送的數(shù)據(jù)量為1～6數(shù)據(jù)包。圖4和圖5給出的是所有任務(wù)的平均時(shí)延和平均跳數(shù)。從圖4中可以看出,平均時(shí)延隨著數(shù)據(jù)包數(shù)量的增長而快速增長。原因是隨著數(shù)據(jù)包數(shù)量的不斷增長,同一時(shí)隙共同發(fā)送的數(shù)據(jù)增多。然而,鏈路容量是有限的,因此這就導(dǎo)致了數(shù)據(jù)發(fā)送時(shí)產(chǎn)生擁擠,一部分?jǐn)?shù)據(jù)被迫只能暫時(shí)緩存在中繼節(jié)點(diǎn)并重新規(guī)劃路由,進(jìn)而導(dǎo)致了任務(wù)時(shí)延的增加。另外,從圖中可以看出,本文提出的“基于拉格朗日松弛的方案”與“基于整數(shù)規(guī)劃的方案”具有相近的性能。

圖4 數(shù)據(jù)包數(shù)目與平均延遲的關(guān)系Fig.4 Number of data packets vs delay

圖5 數(shù)據(jù)包數(shù)目與平均跳數(shù)的關(guān)系Fig.5 Number of data packets vs average number of hops

與圖5的場景基本相同,假設(shè)每個(gè)衛(wèi)星都要向剩余的31個(gè)衛(wèi)星傳遞相同優(yōu)先級(jí)的數(shù)據(jù),每個(gè)衛(wèi)星發(fā)送的數(shù)據(jù)包個(gè)數(shù)分別為2和4。圖6展示了緩存溢出比率與緩存容量的關(guān)系,其中緩存溢出比的定義如下:

圖6 緩存溢出比與緩存容量的關(guān)系Fig.6 Overflow ratio vs storage capacity

可以看出隨著緩存溢出比要求的不斷降低,對(duì)衛(wèi)星緩存容量的要求也不斷降低。例如,當(dāng)發(fā)送的數(shù)據(jù)包個(gè)數(shù)為2,緩存溢出比要求為0.1的時(shí)候,要求緩存容量為630 kB;而當(dāng)緩存溢出比要求為0.3的時(shí)候,要求緩存容量為520 kB,下降了21%。另一方面,緩存容量還與整個(gè)網(wǎng)絡(luò)中的總數(shù)據(jù)量息息相關(guān)。例如,當(dāng)緩存溢出比要求為0.3的時(shí)候,對(duì)于發(fā)送2個(gè)數(shù)據(jù)包的情況,要求緩存容量為520 kB;而對(duì)于發(fā)送4個(gè)數(shù)據(jù)包的情況,要求緩存容量為1 250 kB,提升了1.4倍。

圖7與圖8分別展示的是不同優(yōu)先級(jí)數(shù)據(jù)的平均時(shí)延與平均跳數(shù)性能。在這個(gè)場景下,每個(gè)衛(wèi)星都要向其他31個(gè)衛(wèi)星發(fā)送具有不同優(yōu)先級(jí)的數(shù)據(jù), 每個(gè)優(yōu)先級(jí)數(shù)據(jù)包的個(gè)數(shù)為1。從圖7可以看出,平均延遲隨著數(shù)據(jù)優(yōu)先級(jí)的降低而不斷升高。這是因?yàn)楦邇?yōu)先級(jí)的數(shù)據(jù)優(yōu)先發(fā)送,當(dāng)鏈路容量不足時(shí),低優(yōu)先級(jí)的數(shù)據(jù)被迫只能等待。所提出的“基于拉格朗日松弛的方案”與“基于整數(shù)規(guī)劃的方案”具有相近的性能。

圖7 不同優(yōu)先級(jí)數(shù)據(jù)的平均延遲Fig.7 Average delay of data with different priorities

在平均跳數(shù)方面,根據(jù)圖8,可以看出隨著數(shù)據(jù)優(yōu)先級(jí)的降低,平均跳數(shù)呈現(xiàn)先增加后減小的趨勢(shì)。原因是對(duì)于高優(yōu)先級(jí)的數(shù)據(jù),享有絕對(duì)的資源占有權(quán),因此可以隨時(shí)發(fā)送,但是隨著優(yōu)先級(jí)的降低,數(shù)據(jù)必須為高優(yōu)先級(jí)的數(shù)據(jù)讓路,從而導(dǎo)致數(shù)據(jù)不斷地切換中繼衛(wèi)星,進(jìn)而使得跳數(shù)加大,最后,對(duì)于優(yōu)先級(jí)極低的數(shù)據(jù)來說,由于鏈路容量限制,數(shù)據(jù)不得不一直在一個(gè)衛(wèi)星中持續(xù)緩存,直到其他高優(yōu)先級(jí)數(shù)據(jù)傳輸完畢,此時(shí)網(wǎng)絡(luò)不再擁塞,數(shù)據(jù)可以直接發(fā)送,因此這一部分?jǐn)?shù)據(jù)只會(huì)在延遲上增加,在跳數(shù)上并沒有增加。

圖8 不同優(yōu)先級(jí)數(shù)據(jù)的平均跳數(shù)Fig.8 Average number of hops of data with different priorities

圖9展示的是基于拉格朗日松弛的求解算法的收斂性,對(duì)比了通過整數(shù)線性規(guī)劃求得的最優(yōu)解與用拉格朗日松弛方法所得到的解的差異性?？梢钥闯?拉格朗日松弛方法提供的是原問題的一個(gè)上界,通過不斷迭代,逐漸逼近最優(yōu)解。

圖9 算法1的收斂性Fig.9 Convergence of Algorithm 1

6 結(jié) 論

本文研究了衛(wèi)星網(wǎng)絡(luò)中的資源調(diào)度問題,包括時(shí)隙規(guī)劃與路由規(guī)劃。對(duì)于時(shí)隙規(guī)劃,綜合考慮軌道、距離、時(shí)間相關(guān)性等具體細(xì)節(jié),致力于最大化網(wǎng)絡(luò)的連通性,最終將其建模為最大加權(quán)匹配問題。為了減少問題求解復(fù)雜度,本文提出基于拉格朗日松弛的分布式算法來設(shè)計(jì)時(shí)隙規(guī)劃。仿真結(jié)果表明,提出的算法與最優(yōu)解之間的間隙幾乎為零,從而展示了提出算法的有效性?；诮o定的時(shí)隙規(guī)劃,本文進(jìn)一步考慮了多優(yōu)先級(jí)業(yè)務(wù)的路由問題。仿真展示,高優(yōu)先級(jí)業(yè)務(wù)傳輸時(shí)延較低,但在跳數(shù)方面沒有太大的差別。