陳彥斌 高越

【摘要】??? 本文針對(duì)我國(guó)測(cè)控接收一體化站網(wǎng)調(diào)度業(yè)務(wù)和資源現(xiàn)狀，開(kāi)展了兼顧精確任務(wù)和模糊需求的任務(wù)需求建模;采用基于貪婪策略的啟發(fā)式算法，以最大化安排重要任務(wù)、分配最合適弧段為目標(biāo)，實(shí)現(xiàn)任務(wù)沖突消解、應(yīng)急任務(wù)常態(tài)化插入的資源調(diào)度能力;最后通過(guò)仿真試驗(yàn)證明了該方法的有效性。

【關(guān)鍵字】??? 遙感衛(wèi)星??? 資源調(diào)度??? 測(cè)控接收一體化

一、引言

航天站網(wǎng)資源作為航天系統(tǒng)的重要組成部分，承擔(dān)著對(duì)航天器的跟蹤測(cè)量、監(jiān)視控制和上下行信息交換等任務(wù)。隨著多年來(lái)的我國(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ù)類(lèi)型和復(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)度方法，以天線(xiàn)及配套鏈路為站網(wǎng)資源的調(diào)度粒度。

本文針對(duì)我國(guó)站網(wǎng)調(diào)度需求開(kāi)展任務(wù)需求建模、約束條件梳理、優(yōu)化目標(biāo)設(shè)計(jì)，采用基于貪婪策略的啟發(fā)式算法，設(shè)計(jì)具備前瞻沖突消解、滿(mǎn)足應(yīng)急任務(wù)常態(tài)化插入的貪婪規(guī)則，最后通過(guò)仿真試驗(yàn)證明了該方法的有效性。

二、問(wèn)題建模

衛(wèi)星測(cè)控接收資源調(diào)度問(wèn)題包含了復(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ù)類(lèi)型，如接收、測(cè)控、一體化;TStart：任務(wù)最早開(kāi)始時(shí)刻;TEnd：任務(wù)有效期結(jié)束時(shí)刻;Station：可用的站列表;UserPref：用戶(hù)的偏好，包括任務(wù)來(lái)源、弧段數(shù)量偏好、時(shí)長(zhǎng)偏好、時(shí)效性偏好、設(shè)備偏好、弧段間隔等;TPri：任務(wù)的重要程度。

2.2約束條件分析

調(diào)度過(guò)程中主要考慮如下幾種約束條件：

（1）能力約束：根據(jù)資源能力進(jìn)行星站匹配;

（2）可見(jiàn)性約束：星站在任務(wù)有效時(shí)段內(nèi)物理可見(jiàn);

（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)滿(mǎn)足最大/小任務(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è)控接收問(wèn)題提出的優(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ù)的重要程度，需求滿(mǎn)足度S（t）表示該任務(wù)是否被安排了最合適的弧段。

在計(jì)算P（t）時(shí)，采用德?tīng)柗品ú⒏鶕?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ú)上行的任務(wù);有關(guān)聯(lián)關(guān)系的任務(wù)優(yōu)先于無(wú)關(guān)聯(lián)的任務(wù);可用弧段少的任務(wù)優(yōu)先于可用弧段多的任務(wù)。

在計(jì)算S（t）時(shí)，根據(jù)實(shí)際工程經(jīng)驗(yàn)確定每個(gè)弧段wti對(duì)任務(wù)t的滿(mǎn)足度，并綜合考慮如下原則：用戶(hù)推薦設(shè)備、時(shí)長(zhǎng)長(zhǎng)的弧段、時(shí)間早的弧段滿(mǎn)足度加分。

三、問(wèn)題求解

本文采用基于貪婪策略的啟發(fā)式算法完成求解。貪婪算法是一種解決最優(yōu)化問(wèn)題的近似方法，對(duì)于一些大規(guī)?；蛏婕皬?fù)雜約束的任務(wù)規(guī)劃問(wèn)題，其計(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ù)用戶(hù)偏好，優(yōu)選用戶(hù)指定的設(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ù)約束等條件都滿(mǎn)足的條件下為所有任務(wù)選擇合適的弧段：

Step1：循環(huán)從任務(wù)隊(duì)列中取出未分配、優(yōu)先級(jí)最高的需求;

Step2：從可用弧段列表中選擇滿(mǎn)足度最高的空閑弧段作為預(yù)分配結(jié)果;

Step3：查看該設(shè)備兩個(gè)相鄰弧段之間間隔是否滿(mǎn)足任務(wù)切換時(shí)間;

Step4：如果被占用則按下列規(guī)則消解沖突：排除優(yōu)先級(jí)低的任務(wù)占用的弧段，排除可用弧段多的任務(wù)占用的弧段，將弧段被排除的任務(wù)重新加入任務(wù)隊(duì)列;

Step5：對(duì)于沖突的任務(wù)，將沖突次數(shù)加1，標(biāo)記被搶占的弧段;

Step6：當(dāng)任務(wù)沒(méi)有可用弧段可用時(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++語(yǔ)言實(shí)現(xiàn)。試驗(yàn)中使用仿真衛(wèi)星300顆，仿真測(cè)控接收設(shè)備100套，中繼星10顆。算法性能對(duì)比如表1所示。

由試驗(yàn)結(jié)果可見(jiàn)，本文方法能夠快速完成多星、多站、多需求的天地測(cè)控接收資源一體化調(diào)度問(wèn)題，并且在大量任務(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)完成問(wèn)題求解。與其它方法相比，本文方法以工程應(yīng)用為目的，支持地基單天線(xiàn)、中繼星、多波束設(shè)備，支持精確任務(wù)和模糊需求，支持快速調(diào)度計(jì)算和應(yīng)急任務(wù)滾動(dòng)插入，并通過(guò)仿真實(shí)例驗(yàn)證了模型和算法的有效性。由于站網(wǎng)資源調(diào)度問(wèn)題是一件非常復(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.