宋煒琳， 楊道寧

(1.北京航空航天大學(xué) 經(jīng)濟(jì)管理學(xué)院, 北京 100191; 2.航天工程大學(xué) 宇航科學(xué)與技術(shù)系， 北京 101416)

0 引言

衛(wèi)星導(dǎo)航系統(tǒng)是一個(gè)國家綜合國力的重要象征，目前只有美國、俄羅斯、歐盟、中國有能力建設(shè)具備全球服務(wù)能力的衛(wèi)星導(dǎo)航系統(tǒng)，現(xiàn)已形成了GPS、GLONASS、Galileo和北斗4大衛(wèi)星導(dǎo)航系統(tǒng)。同時(shí)日本和印度也開發(fā)了主要服務(wù)于本國的區(qū)域衛(wèi)星系統(tǒng)QZSS和IRNSS.

維持導(dǎo)航衛(wèi)星的時(shí)間和空間基準(zhǔn)是衛(wèi)星導(dǎo)航系統(tǒng)提供穩(wěn)定、可靠、連續(xù)的導(dǎo)航定位和授時(shí)服務(wù)的前提。在衛(wèi)星導(dǎo)航系統(tǒng)正常運(yùn)行模式下，導(dǎo)航衛(wèi)星時(shí)空基準(zhǔn)的生成依賴于地面站對(duì)衛(wèi)星的跟蹤觀測(cè)，時(shí)空基準(zhǔn)生成后則需要由地面站上注給衛(wèi)星。隨著衛(wèi)星導(dǎo)航系統(tǒng)的發(fā)展，星間鏈路逐漸成為衛(wèi)星導(dǎo)航系統(tǒng)發(fā)展的重要技術(shù)特征之一。星間鏈路是導(dǎo)航衛(wèi)星之間建立的具有精密測(cè)量和通信功能的無線網(wǎng)絡(luò)系統(tǒng)。星間鏈路能夠支持衛(wèi)星導(dǎo)航系統(tǒng)在一段時(shí)間內(nèi)脫離地面站自主維持時(shí)空基準(zhǔn)，也就是常說的自主運(yùn)行。而在地面站和星間鏈路聯(lián)合工作的情況下，星間鏈路系統(tǒng)能夠大大改善地面站的觀測(cè)幾何，提高時(shí)空基準(zhǔn)的精度。尤其是對(duì)于難以在全球布設(shè)地面站的國家，星間鏈路能夠解決區(qū)域觀測(cè)網(wǎng)難以完成的全球衛(wèi)星跟蹤觀測(cè)和時(shí)空基準(zhǔn)上注任務(wù)，是衛(wèi)星導(dǎo)航系統(tǒng)提供全球服務(wù)的關(guān)鍵技術(shù)手段。

基于星間鏈路的衛(wèi)星導(dǎo)航系統(tǒng)業(yè)務(wù)信息傳輸規(guī)劃調(diào)度是一個(gè)十分復(fù)雜的問題，該問題涉及星地、星間測(cè)量數(shù)據(jù)下傳匯總和時(shí)空基準(zhǔn)上注以及星地、星間連接關(guān)系的調(diào)度等因素。在星間鏈路條件下，可以大大簡(jiǎn)化地面段的工作，給衛(wèi)星導(dǎo)航系統(tǒng)的業(yè)務(wù)信息傳輸規(guī)劃調(diào)度帶來了更多選擇，但同時(shí)也進(jìn)一步增加了調(diào)度難度。由于星間鏈路是導(dǎo)航系統(tǒng)的一個(gè)相對(duì)較新的研究領(lǐng)域，目前相關(guān)研究相對(duì)較少，張忠山等提出了一種考慮星間鏈路的星地時(shí)間同步與上注調(diào)度的啟發(fā)式算法[1]，但該算法對(duì)星間鏈路的利用存在一定局限性中，并未考慮對(duì)地面站不可見衛(wèi)星的上注。谷宏志等提出了基于啟發(fā)式算法的地面站資源調(diào)度方法[2]。魯志勇等針對(duì)導(dǎo)航衛(wèi)星系統(tǒng)上注調(diào)度問題的約束特點(diǎn)，設(shè)計(jì)了一種多個(gè)地面站協(xié)同選星策略[3]。謝平等[4]、向尚等[5]闡述了衛(wèi)星自主調(diào)度問題的研究現(xiàn)狀。巫震宇等研究了基于本體的衛(wèi)星資源調(diào)度方法[6]。唐銀銀等針對(duì)上注調(diào)度問題，提出了一種基于差分進(jìn)化的調(diào)度方法[7]。但上述方法都只考慮了地面資源。還有部分學(xué)者研究了利用星間鏈路開展導(dǎo)航系統(tǒng)的相關(guān)業(yè)務(wù)的調(diào)度方法[8-9]?？傊紤]星間鏈路的星地資源聯(lián)合調(diào)度方法很少，且針對(duì)導(dǎo)航系統(tǒng)的衛(wèi)星資源調(diào)度研究也相對(duì)不足，但是地面資源調(diào)度方法和其他衛(wèi)星資源調(diào)度方法的研究也為后續(xù)研究提供了很好的借鑒。本文構(gòu)建了衛(wèi)星導(dǎo)航系統(tǒng)業(yè)務(wù)信息傳輸規(guī)劃調(diào)度問題的數(shù)學(xué)模型，提出一種解決該問題的實(shí)現(xiàn)算法，并通過仿真驗(yàn)證了算法的有效性。

1 模型構(gòu)建

1.1 問題描述

對(duì)于一個(gè)衛(wèi)星導(dǎo)航系統(tǒng)，空間段由若干顆衛(wèi)星組成，地面段由多個(gè)地面站組成。為保證導(dǎo)航系統(tǒng)時(shí)空基準(zhǔn)穩(wěn)定，空間段的衛(wèi)星需要每小時(shí)下傳星間測(cè)量數(shù)據(jù)給地面站，地面站收集星間測(cè)量數(shù)據(jù)和地面可見衛(wèi)星的星地測(cè)量數(shù)據(jù)，聯(lián)合解算生成廣播星歷等信息，再上注給衛(wèi)星，地面站可見衛(wèi)星由地面站直接上注，地面站不可見衛(wèi)星由可見衛(wèi)星通過星間鏈路上注。

將分析周期劃分為整小時(shí)的任務(wù)周期，每個(gè)任務(wù)周期內(nèi)每顆衛(wèi)星需要分別與地面完成數(shù)據(jù)下傳和星歷等信息上注各一次，地面不可見衛(wèi)星可通過星間鏈路轉(zhuǎn)發(fā)。每顆衛(wèi)星只能與一個(gè)地面站建立星地鏈路，且星地鏈路收發(fā)不能同時(shí)進(jìn)行。每個(gè)地面站配備若干部天線，可同時(shí)跟蹤多顆可見衛(wèi)星，并與其建立星地鏈路。則問題可以描述為：如何配置地面站與衛(wèi)星的連接關(guān)系，并安排其業(yè)務(wù)信息傳輸任務(wù)時(shí)間，保證每個(gè)任務(wù)周期內(nèi)全網(wǎng)順利完成業(yè)務(wù)信息傳輸任務(wù)，確保導(dǎo)航系統(tǒng)時(shí)空基準(zhǔn)穩(wěn)定可靠。

1.2 分析與建模

問題的核心是在每個(gè)任務(wù)周期內(nèi)為所有衛(wèi)星安排地面站與之建立星地鏈路，完成業(yè)務(wù)信息傳輸任務(wù)。對(duì)地面站可見衛(wèi)星，可以直接選擇可見地面站建立鏈路；對(duì)于地面站不可見衛(wèi)星，其業(yè)務(wù)信息傳輸任務(wù)需要通過星間鏈路轉(zhuǎn)發(fā)給地面站可見星完成，這可以視為給轉(zhuǎn)發(fā)的地面站可見衛(wèi)星增加了一次業(yè)務(wù)信息傳輸任務(wù)。本文不考慮星間轉(zhuǎn)發(fā)過程，設(shè)想星間鏈路系統(tǒng)有足夠的能力來轉(zhuǎn)發(fā)相關(guān)數(shù)據(jù)。對(duì)于一臺(tái)地面站天線而言，其從跟蹤一顆衛(wèi)星到跟蹤另一顆衛(wèi)星一般需要重新調(diào)整天線指向，對(duì)于非相控陣天線，切換時(shí)間不可忽略。

根據(jù)上述分析，將星地資源調(diào)度問題建模，模型主要參數(shù)見表1. 模型參數(shù)分為兩類，包括資源參數(shù)和目標(biāo)參數(shù)，其中資源參數(shù)主要描述調(diào)度方法中可以用來調(diào)度的資源，目標(biāo)參數(shù)則描述了調(diào)度要達(dá)到的目標(biāo)。輸出目標(biāo)參數(shù)為任務(wù)規(guī)劃表Schedule_Table，該參數(shù)為任務(wù)規(guī)劃表，共有m行n列的矩陣，每一列代表了該衛(wèi)星的任務(wù)調(diào)度了哪些資源來完成，行數(shù)m則為最大調(diào)用資源數(shù)。對(duì)于地面站可見衛(wèi)星，通過直接與地面站建立星地鏈路完成業(yè)務(wù)信息傳輸，因此對(duì)應(yīng)列的第一個(gè)元素則為地面站對(duì)應(yīng)編號(hào)，該列其余元素為0. 對(duì)于地面站不可見衛(wèi)星，其對(duì)應(yīng)列中的元素則為與其建立星間鏈路，轉(zhuǎn)發(fā)其業(yè)務(wù)信息傳輸數(shù)據(jù)的地面站可見星編號(hào)。則調(diào)度目標(biāo)可以通過(1)式描述為

對(duì)m×n矩陣Schedule_Table，

?Columni∈Schedule_Table，
?c∈Columni≠0,i∈[1,n]，

(1)

即矩陣中的任意列中都有非0元素c，也就是所有衛(wèi)星的任務(wù)都通過調(diào)度得以完成，(1)式中的Columni代表規(guī)劃矩陣Schedule_Table中的第i行。

表1 星地資源調(diào)度模型參數(shù)表

顯然，調(diào)度過程中還要受到各類約束條件的制約，各約束條件參數(shù)見表2. 首先是任務(wù)周期時(shí)長(zhǎng)T和上注任務(wù)時(shí)長(zhǎng)Task_Uplink_Time和下傳任務(wù)時(shí)長(zhǎng)Task_Downlink_Time，本文不考慮同一鏈路切換收發(fā)轉(zhuǎn)換時(shí)長(zhǎng)，僅考慮地面站天線切換目標(biāo)時(shí)間T_Shift. 星地可見性Acc則將衛(wèi)星分為地面站可見衛(wèi)星和地面站不可見衛(wèi)星兩類。衛(wèi)星間可見性Sat_Acc則制約著完成地面站不可見衛(wèi)星的業(yè)務(wù)信息傳輸任務(wù)的可調(diào)度資源。

由于本文不考慮天線收發(fā)狀態(tài)切換的時(shí)延，可以統(tǒng)一將上注任務(wù)與下傳任務(wù)視為對(duì)地面站天線的占用。因此對(duì)每顆衛(wèi)星而言，其對(duì)地面站天線的占用時(shí)長(zhǎng)為

表2 約束條件參數(shù)表

Task_Time=Task_Uplink_Time+
Task_Downlink_Time.

(2)

2 調(diào)度方法

調(diào)度方法流程圖如圖1所示。主要分以下幾個(gè)部分，首先是星地、星間可見性分析，然后是衛(wèi)星分類與匹配，接下來星地資源調(diào)度，最后是負(fù)載均衡和結(jié)果輸出，下面分別描述。

圖1 調(diào)度方法流程圖Fig.1 Flow chart of scheduling method

2.1 可見性分析

星間鏈路建立的前提是2顆衛(wèi)星分別在對(duì)方星間鏈路天線的波束指向范圍內(nèi)，并且中間沒有地球遮擋。而星地鏈路的建立同樣需要滿足可見性關(guān)系。星間可見性基于衛(wèi)星間相互位置和星間鏈路天線設(shè)置計(jì)算得到，星地可見性基于衛(wèi)星軌道參數(shù)、地面站坐標(biāo)以及地面站天線最低仰角計(jì)算得到。

2.2 衛(wèi)星分類與匹配

為簡(jiǎn)化分析，根據(jù)星地可見性分析結(jié)果，將衛(wèi)星分為3類(見圖2)：將任務(wù)周期內(nèi)地面站始終可見的衛(wèi)星作為節(jié)點(diǎn)衛(wèi)星，節(jié)點(diǎn)衛(wèi)星在通過星地鏈路完成自身業(yè)務(wù)信息傳輸任務(wù)的同時(shí)，還能夠通過星間鏈路協(xié)助其他衛(wèi)星完成業(yè)務(wù)信息傳輸任務(wù)；將任務(wù)周期內(nèi)地面站間歇可見的衛(wèi)星按照可見弧段時(shí)長(zhǎng)是否大于任務(wù)時(shí)長(zhǎng)，劃分為獨(dú)立衛(wèi)星和非節(jié)點(diǎn)衛(wèi)星，其中可見弧段大于任務(wù)時(shí)長(zhǎng)的衛(wèi)星作為獨(dú)立衛(wèi)星，獨(dú)立衛(wèi)星能夠通過星地鏈路完成自身任務(wù)，但不再協(xié)助完成其他衛(wèi)星的任務(wù)?？梢娀《螘r(shí)長(zhǎng)小于任務(wù)周期的衛(wèi)星和任務(wù)周期內(nèi)持續(xù)不可見衛(wèi)星劃分為非節(jié)點(diǎn)衛(wèi)星，非節(jié)點(diǎn)衛(wèi)星自身無法完成任務(wù)，需要通過星間鏈路與節(jié)點(diǎn)衛(wèi)星建立連接，在節(jié)點(diǎn)衛(wèi)星的協(xié)助下完成任務(wù)。

圖2 衛(wèi)星分類Fig.2 Classification of satellites

非節(jié)點(diǎn)衛(wèi)星的任務(wù)完成需要節(jié)點(diǎn)衛(wèi)星協(xié)助，需要確定非節(jié)點(diǎn)衛(wèi)星與節(jié)點(diǎn)衛(wèi)星的一一對(duì)應(yīng)關(guān)系，也就是任一非節(jié)點(diǎn)衛(wèi)星需要一個(gè)可見節(jié)點(diǎn)衛(wèi)星與之匹配，同樣為了簡(jiǎn)化分析，只有任務(wù)周期內(nèi)2顆衛(wèi)星持續(xù)可見，才認(rèn)定為2顆衛(wèi)星可見。匹配方法利用二分圖的匹配算法實(shí)現(xiàn)。

將節(jié)點(diǎn)衛(wèi)星和非節(jié)點(diǎn)衛(wèi)星作為分別作為點(diǎn)，節(jié)點(diǎn)衛(wèi)星與非節(jié)點(diǎn)衛(wèi)星之間可見，則在它們之間連接一條邊，構(gòu)建二分圖，然后利用匹配算法獲取最大匹配。當(dāng)節(jié)點(diǎn)衛(wèi)星多時(shí)，未匹配節(jié)點(diǎn)衛(wèi)星作為獨(dú)立衛(wèi)星處理；當(dāng)非節(jié)點(diǎn)衛(wèi)星多時(shí)，未匹配節(jié)點(diǎn)衛(wèi)星留待下一流程處理。將Schedule_Table中與匹配成功的非節(jié)點(diǎn)衛(wèi)星對(duì)應(yīng)列的第一個(gè)元素置為與之匹配的節(jié)點(diǎn)衛(wèi)星編號(hào)。

2.3 星地資源調(diào)度

構(gòu)建星地鏈路矩陣Fac_Sat。Fac_Sat為l行30列矩陣，l為地面站數(shù)量。行代表地面站，列代表衛(wèi)星，初始元素全部為0，當(dāng)調(diào)度某一地面站資源給某一衛(wèi)星時(shí)，則對(duì)應(yīng)元素置1，代表建立對(duì)應(yīng)地面站與對(duì)應(yīng)衛(wèi)星之間的星地鏈路。

調(diào)度流程如下：

1)調(diào)度資源完成節(jié)點(diǎn)衛(wèi)星的任務(wù)，該部分任務(wù)包含與之匹配的非節(jié)點(diǎn)星的任務(wù)，匹配成功的節(jié)點(diǎn)衛(wèi)星對(duì)地面站天線的占用時(shí)長(zhǎng)則為2倍任務(wù)時(shí)長(zhǎng)，對(duì)任意匹配成功節(jié)點(diǎn)衛(wèi)星j，將Fac_Sat第j列中與其可見的地面站對(duì)應(yīng)元素全部置1. 并將計(jì)算衛(wèi)星j剩余可用資源時(shí)長(zhǎng)

Sat_Idle_Timej=T-2×Task_Time.

(3)

2)調(diào)度資源完成獨(dú)立衛(wèi)星的任務(wù)，該部分衛(wèi)星包含未匹配成功的節(jié)點(diǎn)衛(wèi)星。對(duì)任意獨(dú)立衛(wèi)星p，將Fac_Sat第p列中與其可見的地面站對(duì)應(yīng)元素全部置1. 并將計(jì)算衛(wèi)星p剩余可用資源時(shí)長(zhǎng)

Sat_Idle_Timep=T-Task_Time.

(4)

3)如果有未匹配非節(jié)點(diǎn)衛(wèi)星，轉(zhuǎn)步驟4，否則該步驟結(jié)束，轉(zhuǎn)2.4節(jié)負(fù)載均衡。

4)調(diào)度資源完成未匹配節(jié)點(diǎn)衛(wèi)星的任務(wù)。對(duì)任意未匹配非節(jié)點(diǎn)衛(wèi)星q，隨機(jī)選擇一個(gè)可見節(jié)點(diǎn)衛(wèi)星k，獲取其可用資源時(shí)長(zhǎng)Sat_Idle_Timek，將該部分資源用來完成衛(wèi)星q的任務(wù)，如果

Sat_Idle_Timek

(5)

則

Sat_Idle_Timek=0.

(6)

從剩余可見節(jié)點(diǎn)星中選擇一個(gè)衛(wèi)星重復(fù)上述步驟，直至分配資源滿足任務(wù)時(shí)長(zhǎng)，并將計(jì)算最后選擇的節(jié)點(diǎn)衛(wèi)星x的剩余可用資源時(shí)長(zhǎng)

Sat_Idle_Timex=
Task_Time-Sat_Idle_Timek-…，

(7)

將Schedule_Table中第q列中從第一個(gè)元素開始依次置為k，…，x，結(jié)束該步驟，轉(zhuǎn)2.4節(jié)負(fù)載均衡。

2.4 負(fù)載均衡

對(duì)任一地面站f，考慮地面站天線數(shù)量足夠，構(gòu)建地面站資源矩陣Facility，F(xiàn)acility為不定行T列矩陣，不同行對(duì)應(yīng)地面站不同天線，列代表對(duì)應(yīng)時(shí)段的資源。

對(duì)Fac_Sat中任一列d，根據(jù)該列中1元素的個(gè)數(shù)分別做如下操作：

1) 1個(gè)1元素情況。在該元素對(duì)應(yīng)地面站的Facility矩陣中增加一行，將該行從1開始的N個(gè)元素置為d，則

N=T-Sat_Idle_Timed.

(8)

然后將Schedule_Table中第d列的第一個(gè)元素置為該地面站編號(hào)。

2) 多個(gè)1元素情況。計(jì)算這些元素對(duì)應(yīng)地面站的Facility矩陣中非0元素的個(gè)數(shù)，選擇非0元素最少的地面站，在對(duì)應(yīng)地面站的Facility矩陣中增加一行，將該行從1開始的N個(gè)元素置為d，N同樣利用(8)式計(jì)算。然后將Schedule_Table中第d列的第一個(gè)元素置為該地面站編號(hào)。對(duì)所有列都執(zhí)行上述操作后，對(duì)于同一個(gè)地面站的Facility矩陣中的各行，如果某一行R1的0元素?cái)?shù)大于另一行R2的非0元素個(gè)數(shù)與T_Shift之和，則將R1行中前T_Shift個(gè)元素置-1，代表切換指向，將R2行中的非0元素移至-1后，并刪除R2行，重復(fù)上述操作，直至所有行都無法再合并。

2.5 結(jié)果輸出

輸出任務(wù)規(guī)劃表Schedule_Table和地面站地面站資源矩陣Facility.

3 仿真及結(jié)果分析

3.1 場(chǎng)景設(shè)置

本文以北斗衛(wèi)星導(dǎo)航系統(tǒng)的參數(shù)設(shè)置場(chǎng)景，通過仿真分析驗(yàn)證了調(diào)度方法的有效性。仿真場(chǎng)景設(shè)置見表3[10-12].

表3 仿真場(chǎng)景設(shè)置

空間段由30顆衛(wèi)星組成，其中中軌道(MEO)衛(wèi)星24顆，地球同步軌道(GEO)衛(wèi)星3顆，傾斜地球同步軌道(IGSO)衛(wèi)星3顆。地面段考慮中國大陸境內(nèi)的區(qū)域觀測(cè)網(wǎng)，選取位于中國境內(nèi)距離相對(duì)較遠(yuǎn)的北京、新疆和海南3個(gè)區(qū)域設(shè)置地面站。星間鏈路天線中心指向地心，波束覆蓋角度為±60°. 地面站天線最低仰角為10°. 分析周期24 h，任務(wù)周期1 h，上注任務(wù)時(shí)長(zhǎng)20 min，下傳任務(wù)時(shí)長(zhǎng)5 min，地面站天線切換目標(biāo)時(shí)間1 min.

3.2 仿真結(jié)果

首先分析了24個(gè)任務(wù)周期輸出的24個(gè)任務(wù)規(guī)劃表Schedule_Table，其所有列中都有非0元素，滿足式的調(diào)度目標(biāo)，證明該調(diào)度方法能夠滿足任務(wù)調(diào)度需求。圖3給出了某一任務(wù)周期內(nèi)各個(gè)衛(wèi)星的任務(wù)調(diào)度情況，可以看到，10顆衛(wèi)星通過北京站完成業(yè)務(wù)信息傳輸任務(wù)，9顆衛(wèi)星通過新疆站完成業(yè)務(wù)信息傳輸任務(wù)，11顆衛(wèi)星通過海南站完成了業(yè)務(wù)信息傳輸任務(wù)。

圖3 某一任務(wù)周期內(nèi)各衛(wèi)星任務(wù)調(diào)度情況Fig.3 Satellite task scheduling in a certain task cycle

接下來分析了地面資源占用數(shù)，如圖4所示。不同任務(wù)周期內(nèi)，各地面站分別需要4～6個(gè)不等的天線。所需天線總數(shù)最少13個(gè)，最多16個(gè)，平均15.375個(gè)。為滿足任務(wù)需求，可將各地面站分別配置6部天線。

圖4 各任務(wù)周期內(nèi)需要的地面站天線資源數(shù)Fig.4 Number of antennas required in each task cycle

對(duì)于各地面站的各個(gè)天線在整個(gè)分析周期內(nèi)的資源利用率如圖5～圖7所示。由于大部分任務(wù)周期內(nèi)，各地面站只需要5部天線，因此第6部天線普遍利用率較低，而前5部天線的利用率基本都在70%以上。

圖5 北京站各天線資源利用率Fig.5 Resource utilization rate of Beijing satellite ground station

圖6 新疆站各天線資源利用率Fig.6 Resource utilization rate of Xinjiang satellite ground station

圖7 海南站各天線資源利用率Fig.7 Resource utilization rate of Hainan satellite ground station

4 結(jié)論

本文研究了星間鏈路條件下的衛(wèi)星導(dǎo)航系統(tǒng)運(yùn)行管理中的星地資源調(diào)度問題，建立了該問題的數(shù)學(xué)模型，并提出一種解決該問題的實(shí)現(xiàn)算法。利用北斗三號(hào)衛(wèi)星導(dǎo)航系統(tǒng)的場(chǎng)景設(shè)置，仿真驗(yàn)證了該方法的有效性，并分析了該方法的資源占用情況。分析結(jié)果表明，利用該方法，僅在北京、新疆、海南3個(gè)區(qū)域配置地面站構(gòu)成區(qū)域監(jiān)測(cè)網(wǎng)的條件下，每個(gè)地面站僅需6部天線，就能完成各個(gè)衛(wèi)星的業(yè)務(wù)信息傳輸任務(wù)，確保導(dǎo)航衛(wèi)星時(shí)空基準(zhǔn)穩(wěn)定，導(dǎo)航系統(tǒng)工作正常。下一步研究工作，將結(jié)合北斗三號(hào)衛(wèi)星導(dǎo)航系統(tǒng)的工程實(shí)踐，進(jìn)一步驗(yàn)證本文方法的可行性和有效性。