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