陳彥斌 高越
【摘要】??? 本文針對我國測控接收一體化站網(wǎng)調(diào)度業(yè)務(wù)和資源現(xiàn)狀,開展了兼顧精確任務(wù)和模糊需求的任務(wù)需求建模;采用基于貪婪策略的啟發(fā)式算法,以最大化安排重要任務(wù)、分配最合適弧段為目標(biāo),實現(xiàn)任務(wù)沖突消解、應(yīng)急任務(wù)常態(tài)化插入的資源調(diào)度能力;最后通過仿真試驗證明了該方法的有效性。
【關(guān)鍵字】??? 遙感衛(wèi)星??? 資源調(diào)度??? 測控接收一體化
一、引言
航天站網(wǎng)資源作為航天系統(tǒng)的重要組成部分,承擔(dān)著對航天器的跟蹤測量、監(jiān)視控制和上下行信息交換等任務(wù)。隨著多年來的我國站網(wǎng)基礎(chǔ)設(shè)施建設(shè)以及應(yīng)用場景的不斷豐富,長管需求與應(yīng)急需求并存、測控任務(wù)與接收任務(wù)并存、狀態(tài)各異的衛(wèi)星和站網(wǎng)設(shè)備并存,使得站網(wǎng)資源承擔(dān)的任務(wù)類型和復(fù)雜性不斷增加、沖突日趨嚴(yán)重。鑒于這些現(xiàn)實的情況,迫切需要研究高效實用的調(diào)度系統(tǒng),充分發(fā)揮站網(wǎng)資源的服務(wù)效能。
世界各航天大國在該領(lǐng)域均取得了一定程度的研究成果[1-5]并建立了各自的業(yè)務(wù)系統(tǒng)。為適應(yīng)國內(nèi)應(yīng)用實際情況,楊永安等[6]確定了測控弧段優(yōu)先級及量化方法和沖突消解方法,已成功應(yīng)用于陸基測控網(wǎng)的工程應(yīng)用;金光[7]采用CSP模型描述測控調(diào)度中的約束條件;陶孫杰[8]設(shè)計了一種啟發(fā)式算法與遺傳算法組合的站網(wǎng)資源調(diào)度方法,以天線及配套鏈路為站網(wǎng)資源的調(diào)度粒度。
本文針對我國站網(wǎng)調(diào)度需求開展任務(wù)需求建模、約束條件梳理、優(yōu)化目標(biāo)設(shè)計,采用基于貪婪策略的啟發(fā)式算法,設(shè)計具備前瞻沖突消解、滿足應(yīng)急任務(wù)常態(tài)化插入的貪婪規(guī)則,最后通過仿真試驗證明了該方法的有效性。
二、問題建模
衛(wèi)星測控接收資源調(diào)度問題包含了復(fù)雜的約束關(guān)系、不確定性、優(yōu)先級關(guān)系,本文結(jié)合測控接收特點對任務(wù)、優(yōu)化目標(biāo)進行建模。
2.1任務(wù)需求建模
為了支持指定資源和模糊需求兩種資源申請方式,建立了如下的8元組任務(wù)需求模型:
t={TaskId,SatId,Type,TStart,TEnd,Station,UserPref,TPri}
其中,t:任務(wù)需求;TaskId:任務(wù)編號;SatId:衛(wèi)星代號;Type:任務(wù)類型,如接收、測控、一體化;TStart:任務(wù)最早開始時刻;TEnd:任務(wù)有效期結(jié)束時刻;Station:可用的站列表;UserPref:用戶的偏好,包括任務(wù)來源、弧段數(shù)量偏好、時長偏好、時效性偏好、設(shè)備偏好、弧段間隔等;TPri:任務(wù)的重要程度。
2.2約束條件分析
調(diào)度過程中主要考慮如下幾種約束條件:
(1)能力約束:根據(jù)資源能力進行星站匹配;
(2)可見性約束:星站在任務(wù)有效時段內(nèi)物理可見;
(3)狀態(tài)約束:只有空閑狀態(tài)的弧段可以使用;
(4)時長約束:弧段長度應(yīng)不小于本次任務(wù)最短時長要求;
(5)關(guān)聯(lián)約束檢查:多個弧段的總時長不小于最短任務(wù)時間;兩個弧段的時間間隔應(yīng)滿足最大/小任務(wù)間隔;測控任務(wù)不能在數(shù)傳任務(wù)之后;
(6)資源獨占約束:一個波束、一條鏈路、一個通道同一時刻只能給一顆衛(wèi)星使用;
(7)任務(wù)間隔約束:同一套設(shè)備相鄰任務(wù)間隔應(yīng)大于最短任務(wù)切換時間。
2.3優(yōu)化目標(biāo)設(shè)計
在構(gòu)造目標(biāo)函數(shù)時,針對多星測控接收問題提出的優(yōu)化目標(biāo)包括:成功執(zhí)行的任務(wù)數(shù)目最大化、成功執(zhí)行的任務(wù)加權(quán)優(yōu)先級最大化、任務(wù)的弧段質(zhì)量最高等。對于任務(wù)列表T中的每個任務(wù)t,本文在此基礎(chǔ)上定義目標(biāo)函數(shù)為:
Max{∑t∈T? F(t)×P(t)×S(t)}
其中,F(xiàn)(t)表示任務(wù)是否可以被安排,任務(wù)優(yōu)先度P(t)表示了任務(wù)的重要程度,需求滿足度S(t)表示該任務(wù)是否被安排了最合適的弧段。
在計算P(t)時,采用德爾菲法并根據(jù)實際工程經(jīng)驗[6]確定每個任務(wù)的優(yōu)先級,優(yōu)先級原則:優(yōu)先響應(yīng)重大、應(yīng)急任務(wù);上行任務(wù)優(yōu)先于無上行的任務(wù);有關(guān)聯(lián)關(guān)系的任務(wù)優(yōu)先于無關(guān)聯(lián)的任務(wù);可用弧段少的任務(wù)優(yōu)先于可用弧段多的任務(wù)。
在計算S(t)時,根據(jù)實際工程經(jīng)驗確定每個弧段wti對任務(wù)t的滿足度,并綜合考慮如下原則:用戶推薦設(shè)備、時長長的弧段、時間早的弧段滿足度加分。
三、問題求解
本文采用基于貪婪策略的啟發(fā)式算法完成求解。貪婪算法是一種解決最優(yōu)化問題的近似方法,對于一些大規(guī)?;蛏婕皬?fù)雜約束的任務(wù)規(guī)劃問題,其計算速度較快 [10]。
3.1貪婪準(zhǔn)則設(shè)計
該算法的關(guān)鍵在于貪婪準(zhǔn)則的設(shè)定,即在求解的每一步依據(jù)何種標(biāo)準(zhǔn)對變量進行賦值。具體規(guī)則如下:
(1)弧段選用規(guī)則:優(yōu)選非保留圈次弧段(保留中繼資源、出境圈弧段);根據(jù)前瞻策略,優(yōu)先選用與其它弧段沖突少的弧段;根據(jù)用戶偏好,優(yōu)選用戶指定的設(shè)備、跟蹤質(zhì)量較好的弧段。
(2)沖突消解規(guī)則:排除優(yōu)先級低的任務(wù)占用的弧段;排除可用弧段多的任務(wù)占用的弧段;對于弧段被排除的任務(wù),重新加入隊列編排。
(3)應(yīng)急響應(yīng)規(guī)則:優(yōu)選空閑弧段、保留弧段;被調(diào)整任務(wù)優(yōu)先安排到原有站、原有圈次;限定調(diào)整深度。
3.2算法流程
根據(jù)每個任務(wù)的優(yōu)先級,從高到低插入到已有的任務(wù)隊列,在資源約束、任務(wù)約束等條件都滿足的條件下為所有任務(wù)選擇合適的弧段:
Step1:循環(huán)從任務(wù)隊列中取出未分配、優(yōu)先級最高的需求;
Step2:從可用弧段列表中選擇滿足度最高的空閑弧段作為預(yù)分配結(jié)果;
Step3:查看該設(shè)備兩個相鄰弧段之間間隔是否滿足任務(wù)切換時間;
Step4:如果被占用則按下列規(guī)則消解沖突:排除優(yōu)先級低的任務(wù)占用的弧段,排除可用弧段多的任務(wù)占用的弧段,將弧段被排除的任務(wù)重新加入任務(wù)隊列;
Step5:對于沖突的任務(wù),將沖突次數(shù)加1,標(biāo)記被搶占的弧段;
Step6:當(dāng)任務(wù)沒有可用弧段可用時,標(biāo)記任務(wù)分配失敗,并記錄失敗原因;
Step7:當(dāng)所有任務(wù)都處理完畢時,規(guī)劃完成。
四、試驗結(jié)果與分析
為了驗證本文算法的性能,搭建試驗環(huán)境進行測試。試驗環(huán)境使用Win7 64bit系統(tǒng)、Oracle 12c數(shù)據(jù)庫,CPU為3.6GHz四核,內(nèi)存16GB,采用C++語言實現(xiàn)。試驗中使用仿真衛(wèi)星300顆,仿真測控接收設(shè)備100套,中繼星10顆。算法性能對比如表1所示。
由試驗結(jié)果可見,本文方法能夠快速完成多星、多站、多需求的天地測控接收資源一體化調(diào)度問題,并且在大量任務(wù)安排后支持快速滾動插入應(yīng)急任務(wù)。
五、結(jié)論
本文從我國航天站網(wǎng)管理業(yè)務(wù)需求和資源實際情況出發(fā),提出了一種遙感衛(wèi)星測控接收資源一體化調(diào)度方法,先后完成了任務(wù)需求建模、約束條件分析、優(yōu)化目標(biāo)設(shè)計,最后采用基于貪婪策略的啟發(fā)式算法,以最大化安排重要任務(wù)、分配最合適弧段為目標(biāo)完成問題求解。與其它方法相比,本文方法以工程應(yīng)用為目的,支持地基單天線、中繼星、多波束設(shè)備,支持精確任務(wù)和模糊需求,支持快速調(diào)度計算和應(yīng)急任務(wù)滾動插入,并通過仿真實例驗證了模型和算法的有效性。由于站網(wǎng)資源調(diào)度問題是一件非常復(fù)雜的系統(tǒng)工程,該項工作還需在實踐應(yīng)用中不斷完善。
參? 考? 文? 獻
[1] CASTAING J. Scheduling downloads for multi-satellite,multi-ground station missions[C]. //Proceedings of 28thAnnual AIAA/ USU Conference on Small Satellites. Utah,USA:AIAA,2014:1-12.
[2] SPANGELO S,CUTLER J,GILSON K,et al. Optimization-based scheduling for the single-satellite,multi-groundstation communication problem[J]. Computers & OperationsResearch,2015,57(C):1-16.
[3] 唐旻.衛(wèi)星系統(tǒng)數(shù)傳與測控服務(wù)策略研究[D],國防科學(xué)技術(shù)大學(xué)研究生院碩士論文,2013.11.
[4] Burrowbridge. Optimal Allocation of Satellite Network Resources[D]. in Ph.D Thesis.1999, Virginia Tech: Virginia.
[5] Edwards B L, Israel D, Wilson K E, et al. An Optical CommunicationsPathfinder for the Next Generation Tracking and Data Relay Satellite[C].International Conference on Space Operations, Pasadena, USA, 2015.
[6] 楊永安,樊恒海,馮祖仁等.一種基于 ES 法的衛(wèi)星測控資源調(diào)度仿真及實現(xiàn)[J].系統(tǒng)仿真學(xué)報,2005,17(4):982—985.