宋煒琳， 楊道寧

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

0 引言

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

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

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

1 模型構建

1.1 問題描述

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

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

1.2 分析與建模

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

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

對m×n矩陣Schedule_Table，

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

(1)

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

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

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

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

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

Task_Time=Task_Uplink_Time+
Task_Downlink_Time.

(2)

2 調度方法

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

圖1 調度方法流程圖Fig.1 Flow chart of scheduling method

2.1 可見性分析

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

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

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

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

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

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

2.3 星地資源調度

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

調度流程如下：

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

Sat_Idle_Timej=T-2×Task_Time.

(3)

2)調度資源完成獨立衛(wèi)星的任務，該部分衛(wèi)星包含未匹配成功的節(jié)點衛(wèi)星。對任意獨立衛(wèi)星p，將Fac_Sat第p列中與其可見的地面站對應元素全部置1. 并將計算衛(wèi)星p剩余可用資源時長

Sat_Idle_Timep=T-Task_Time.

(4)

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

4)調度資源完成未匹配節(jié)點衛(wèi)星的任務。對任意未匹配非節(jié)點衛(wèi)星q，隨機選擇一個可見節(jié)點衛(wèi)星k，獲取其可用資源時長Sat_Idle_Timek，將該部分資源用來完成衛(wèi)星q的任務，如果

Sat_Idle_Timek

(5)

則

Sat_Idle_Timek=0.

(6)

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

Sat_Idle_Timex=
Task_Time-Sat_Idle_Timek-…，

(7)

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

2.4 負載均衡

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

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

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

N=T-Sat_Idle_Timed.

(8)

然后將Schedule_Table中第d列的第一個元素置為該地面站編號。

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

2.5 結果輸出

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

3 仿真及結果分析

3.1 場景設置

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

表3 仿真場景設置

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

3.2 仿真結果

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

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

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

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

對于各地面站的各個天線在整個分析周期內的資源利用率如圖5～圖7所示。由于大部分任務周期內，各地面站只需要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 結論

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