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

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

0 引 言

相對于地面網(wǎng)絡(luò),衛(wèi)星網(wǎng)絡(luò)具有覆蓋面超廣、速度快等獨特優(yōu)點。盡管衛(wèi)星網(wǎng)絡(luò)建設(shè)費用昂貴,但因其具有獨特的優(yōu)勢而一直備受關(guān)注。一方面,雖然5G網(wǎng)絡(luò)正在不斷完善,但邊緣地區(qū)以及海上用戶服務(wù)一直沒能得到很好的解決。因此,為了進一步提升用戶的服務(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ò)信息傳輸方法是非常重要的。然而,對衛(wèi)星網(wǎng)絡(luò)的研究也存在著一些挑戰(zhàn)。

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

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

2 算法設(shè)計

2.1 基本約束

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

(1)

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

(2)

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

(3)

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

(4)

(5)

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

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

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

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

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

3.1 基于匹配理論的方案

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

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

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

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

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

對于最大加權(quán)匹配,下面給出一個圖來展示具體的流程。如圖2所示,根據(jù)網(wǎng)絡(luò)的可見性分析,首先建立網(wǎng)絡(luò)的拓撲連通關(guān)系,然后根據(jù)一定的規(guī)則,對每條邊進行一定的權(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)匹配的求解。對于權(quán)重的設(shè)置而言,考慮到每個時隙的匹配具有時間相關(guān)性,為了將時間上的耦合分解,這里將時間上的相關(guān)性轉(zhuǎn)換到權(quán)重的設(shè)置上,從而實現(xiàn)時間上的分離。也就是說,當(dāng)前時隙每條邊權(quán)重的設(shè)置要根據(jù)之前時隙的邊匹配情況來設(shè)置。下面將描述具體的賦權(quán)規(guī)則。

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

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

(11)

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

(12)

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

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

(13)

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

(14)

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

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

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

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

(15)

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

證畢

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

(16)

(17)

將問題進行整理可以得到

(18)

(19)

證畢

(20)

(21)

(22)

(23)

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

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

3.4 算法分析

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

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

4 延遲最小化的路由方案

4.1 路由算法設(shè)計

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

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

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

(24)

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

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

算法 2 不同優(yōu)先級數(shù)據(jù)包的路由算法1. 輸入:時隙分配表, 數(shù)據(jù)包基本信息2. 輸出:每個數(shù)據(jù)包的路由表3. 檢測當(dāng)前節(jié)點中緩存中的數(shù)據(jù), 選取出當(dāng)前時隙可以發(fā)送的數(shù)據(jù)4. 將這些數(shù)據(jù)包按照優(yōu)先級從高到低排序, 并假設(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ù)包進行等待, 重新規(guī)劃路由10. end11. end

4.2 算法擴展

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

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

(25)

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

(26)

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

5 仿真分析

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

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

表1 仿真參數(shù)

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

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

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

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

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

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

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

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

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

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

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

6 結(jié) 論

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