基于優先級與時間裕度的衛星應急觀測任務規劃*

郭 超，熊 偉，劉呈祥

(裝備學院 a.研究生管理大隊；b.復雜電子系統仿真實驗室，北京 101416)

?

基于優先級與時間裕度的衛星應急觀測任務規劃*

郭 超**a，熊 偉b，劉呈祥a

(裝備學院 a.研究生管理大隊；b.復雜電子系統仿真實驗室，北京 101416)

應急觀測是對地觀測衛星為配合地面緊急行動而執行的任務，具有緊迫性、集中性等特點，為任務規劃帶來了困難。針對應急觀測的特點，描述了影響任務規劃的衛星資源及任務的主要屬性，定義了考慮重要性與緊迫性的任務優先級，提出了一個反映任務緊迫性要求滿足程度的屬性——時間裕度。建立了任務規劃模型，構造了一個基于優先級與任務時間裕度的規劃目標，確定了一系列規劃約束，并利用遺傳算法對模型進行求解。通過與最大化任務重要度的常規任務規劃進行對比可見，所建立的模型能夠有效提高任務成功率。

對地觀測衛星；應急觀測；任務規劃；時間裕度

1 引 言

對地觀測衛星的任務規劃就是在衛星數量固定、傳感器能力有限，而任務之間存在沖突的情況下，確定任務的執行順序以及其與資源、時間的對應關系，以排除不同任務之間的沖突，并最大化滿足用戶的需求，對于提高衛星資源的利用率、優化觀測任務的執行方案具有重要的意義?，F有相關研究通過對目標觀測過程建立整數規劃[1]、約束滿足問題(Constraint Satisfied Problem，CSP)[2-4]、圖論[5]模型，并利用啟發式算法[6]或智能算法[7]來求解，取得了較好的效果。

完整的對地觀測任務包含目標觀測和數據下傳兩個步驟，現有的多數研究以目標觀測過程的規劃為主，往往假設通信資源充足，數據下傳不受約束而予以忽略。僅有少數學者研究了同時考慮目標觀測和數據下傳的情況，典型研究如：孫凱等[8]研究了成像衛星星地聯合調度問題，分別給出了成像觀測和數據回傳兩個階段調度的優化目標和約束條件，但其將成像觀測和數據回傳作為兩個獨立的過程，以前者的結果作為后者的輸入預案，后者的結果無法對前者產生影響；Wang等[9]研究了考慮數傳過程的對地觀測衛星星座的規劃問題，提出一種基于優先級的沖突避免啟發式算法，但未考慮任務截止時間的影響。

此外，現有研究多針對常規背景下的觀測任務，實際上目前對地觀測衛星在搶險救災、局部戰爭、突發事件處置等緊急活動中也發揮著重要作用。以上研究成果直接應用于此類應急背景下的觀測任務尚顯不足，因此，本文從應急觀測任務規劃的特點入手，在現有規劃模型的基礎上提出改進，建立了應急觀測任務規劃模型。

2 應急觀測任務的特點

應急觀測是衛星支持地面緊急行動時所承擔的觀測活動，任務時間和所針對的目標都無法事先確定，具有較強的時效性要求?，F有研究中對數傳過程的簡化假設，對于常規情況下的觀測任務是可行的，這是因為常規觀測任務的執行時間是確定的，不會在一定時間內集中突然出現大量緊急觀測需求，且不要求將觀測結果盡快下傳，衛星可長時間存儲觀測數據等待下傳時機。應急觀測不同于常規觀測，主要體現在緊迫性、時間集中性和空間集中性3個特點。

(1)緊迫性

應急觀測任務的緊迫性來源于兩個方面：一是觀測的緊迫性，指任務所指向的目標可能只在當前一段時間內可見，若無法及時獲得足夠目標信息，目標狀態及觀測條件可能發生變化，要求衛星在一定的截止時間內完成觀測：二是任務總體的緊迫性，指地面行動的執行者需要盡早獲得衛星的觀測數據，若目標信息無法及時下傳，其時效性會降低進而導致任務失敗，故要保證在一定截止時間內觀測數據下傳完畢。

(2)時間集中性

在地面緊急行動中，各種突發情況無法預測，造成了應急觀測任務需要隨機到來，往往表現為在一定時間內突然集中出現。

(3)空間集中性

由于作戰、搶險等緊急行動一般不會覆蓋廣大的地理空間，而只是集中在有限的空間邊界內進行，如局部戰場、受災區域等，故應急觀測任務所指向目標的地面位置也具有一定的局限性，不會出現目標大范圍分散的情況。

緊迫性使任務具有更為苛刻的時間約束，不僅需要在有限的可見的時間窗口和一定的截止時間內完成觀測，還需要在任務要求的截止時間內將觀測數據下傳，以同時滿足目標觀測的緊迫性和任務總體緊迫性的雙重要求。時間和空間上的集中性則會導致任務分布的不均勻，大大增加了不同任務間的潛在沖突，這種沖突既包括在衛星傳感器資源占用上的沖突，也包括在星地數據傳輸資源占用上的沖突，導致任務可能因兩種原因而失?。阂皇且虻却捎糜^測資源而令觀測不能及時完成；二是因等待可用通信資源而令觀測數據不能及時下傳，現有研究中對數傳過程的簡化假設將不再適用，故應急觀測任務規劃不能像常規觀測任務規劃一樣開展。

3 應急觀測任務規劃建模

假設SAT={sat1,sat2,…,satm}為對地觀測衛星集合，m為衛星總數量，TASK={task1,task2,…,taskn}為應急觀測任務集合，n為任務總數量，T為所有任務執行的總時段。實際的對地觀測任務需要考慮的因素很多，為降低建模難度，在此做如下假設：

(1)任意對地觀測衛星只擁有一個有效的觀測載荷，且任意時刻最多只能服務于一項應急觀測任務；

(2)一旦一顆衛星開始執行某一項任務后必須待此任務執行完畢方可執行其他任務，期間不允許資源搶占；

(3)一顆衛星先后執行兩個任務需要的時間間隔忽略不計。

3.1 衛星應急觀測中的資源和任務

(1)資源描述

任意衛星資源sati∈SAT可以用五元組描述：

(2)任務描述

任意任務taskj∈TASK可以用七元組描述：

3.2 任務優先級與時間裕度

圖1 任務執行時間

在常規觀測任務規劃中，重要性更大的任務應當優先執行，以獲得更高的收益。而在應急觀測任務規劃中，還要考慮到任務越緊迫越容易失敗，應該優先執行，而最大允許等待時間的長短反映了任務觀測和數傳的緊迫性，故定義任務taskj優先級為

其含義為在執行taskj過程中，實際用于等待可用資源的時間在最大允許等待時間中的比重，反映了任務執行方案滿足特定緊迫性要求的程度。Rj越大說明taskj實際觀測和數傳開始時刻相對于對應截止時刻的提前程度越大，taskj能夠盡早完成，騰出可用資源執行其他任務。

3.3 基于優先級與時間裕度的規劃模型

定義反映任務taskj規劃結果的變量xij，若任務taskj由sati執行成功，則xij=1；否則，xij=0。根據前文的描述，規劃應考慮兩類約束：任務假設約束和任務執行條件約束，各約束組含義如表1所示。

表1 應急觀測任務規劃約束

Tab.1 Constraints of emergency mission planning

類型約束組約束條件約束含義問題假設約束C1?t∈T,∑nj=1xij≤1任意時刻每個衛星只能服務于一個任務∑mi=1xij≤1每個目標只被觀測一次xij(tjse-tjsb)·xij'(t'jse-t'jsb)≤0任務之間不存在資源搶占任務執行條件約束C2C3C4∑mi=1Si≥1;?sati∈SAT,Ci>djSAT中能夠找到可用資源sati,sati滿足當前星載存儲空間大于taskj任務數據量[tjsb,tjse]?WTi,j衛星sati對taskj的目標有觀測時間窗口tjse-tjsb≥ljstaskj的觀測執行時間[tjsb,tjse]大于最短觀測時間ljmtjse≤tjsd在觀測截止時刻tjsd前完成目標觀測[tjtb,tjte]?WGisati對地面站有數傳時間窗口tjte-tjtb≥ljttaskj數傳時間執行時間[tjtb,tjte]能夠支持任務數據下傳完畢tjte≤tjtd在數傳截至時刻tjtd前完成目標數據下傳

約束組C1～C4限定了任務執行成功的條件，不滿足約束的執行方案將被過濾。在此基礎上，可以建立規劃目標：

maxf=(f1)λ1(f2)λ2,

(1)

(2)

(3)

式(1)為規劃目標，含義為令函數f的取值最大，包含子目標f1、f2。其中f1的含義為令可執行任務具有更高的優先級，使重要、更緊迫的任務優先執行；f2的含義為令可執行任務的時間裕度最大，使任務在特定的緊迫性要求下，等待可用資源的時間最短，執行更為及時，從整體上提高任務執行成功率。此外，式(1)中λ1、λ2(滿足λ1+λ2=1)分別為f1、f2在最終規劃目標中的作用權值，取值應根據實際應用中對兩個子目標的偏好，通過專家打分的方式決定。

4 模型求解

應急觀測任務規劃的目的是確定任務的執行順序，并為每個任務分配衛星資源和執行時間。針對前文建立的模型，采用遺傳算法求解任務規劃問題。本文以任務分配序列作為染色體，編碼方式見文獻[3]，以任務規劃目標函數的倒數作為適應度計算函數，即ffitness=f-1。

本文染色體的適應度的計算方法為：遍歷種群中的每個染色體，由每個染色體確定一個任務分配序列，按照該任務執行序列依次判斷每一個任務是否能夠執行成功，并確定相應的衛星資源和執行時間，而后按照式(1)計算每個染色體的適應度。對于序列中的任一任務taskj，執行結果的判斷過程如圖2所示。

圖2 任務taskj執行結果判斷

5 計算實例

5.1 算例參數設置

為檢驗任務規劃模型和求解算法的有效性，構造一個應急觀測任務規劃問題計算實例，其參數設置如下：

(1)全局參數設置

所有的應急觀測任務執行時段為

2015/11/01 04:00:00.00～2015/11/01 14:00:00.00，下行鏈路傳輸速率假設為0.5 GB/s。

(2)資源參數設置

算例最多設置6顆對地觀測衛星Sat-1～Sat-6，軌道參數如表2所示。所有衛星的初始狀態都為空閑，初始星載存儲都為150 GB；設置用于接收觀測數據的地面站20個，位置數據從STK數據庫導入。

表2 衛星參數設置

Tab.2 Configuration of parameters of satellites

序號a/mei/(°)Ω/(°)ω/(°)M/(°)Sat-169931830.00067697.763243.448258.859185.695Sat-270221810.00082297.9020.096175.699323.968Sat-370105060.00081797.727241.623101.85389.460Sat-470267030.00138997.861332.333134.543235.987Sat-568516470.00157097.366348.493193.878233.067Sat-668636780.00096997.69748.440107.11173.223

(3)任務參數設置

選定目標區域范圍：110°E～120°E，20°N～30°N，隨機產生應急觀測任務集合，各任務重要度：0～1，到達時刻為2015/11/01 04:00:00.00～2015/11/01 14:00:00.00間的隨機時間點，最短觀測時間10～1 000 s，數據量1～10 GB，觀測截止時刻為任務到達時刻至全部任務執行完畢時刻間的隨機時間點，數傳截止時刻為觀測截止時刻至全部任務執行完畢時刻間的隨機時間點。

(4)求解算法設置

遺傳算法種群數量為50，交叉概率0.6，變異概率0.05，目標函數中權值參數取λ1=0.6，λ2=0.4。

5.2 算例結果及分析

將使用本文規劃模型的算例組記為F，為了驗證規劃模型的有效性，將常規觀測中常見的、只考慮最大化任務重要度(或收益)的規劃模型[3]作為計算對照組，記為F′。

(1)全部衛星可用，觀測任務集規模分別為20、50、80、110,計算結果如表3和圖3所示?？梢娫谫Y源一定的情況下，相比單純考慮提高任務收益的最大化重要度(或收益)的規劃模型，本文提出的應急觀測任務規劃模型兼顧任務重要性、緊迫性，同時考慮時間裕度的影響，能夠提高整體任務執行成功率。這是因為應急觀測能否執行成功很大程度上取決于其能否在截止時間內完成，將時間裕度加入規劃目標可以有效地縮短任務執行中的各段空閑等待時間，提高資源利用率，從而使更多的任務及時執行。

表3 資源固定時不同規模任務集規劃結果

Tab.3 Planning results under the condition of certain resources and various task numbers

任務集規模F規劃成功率/%F'規劃成功率/%效果提升/%2080.075.05.05076.070.06.08080.075.05.011081.876.45.4

圖3 資源固定時不同規模任務集規劃結果對照

Fig.3 Comparison of planning results under the condition of certain resources and various task numbers

(2)任務集規模取定為80，可用衛星分別為2顆、4顆、6顆,規劃結果如表4和圖4所示?？捎眯l星數較少時(2顆)相比可用衛星數較多時(6顆)，F較F′在任務成功率上的增幅更大，可見任務數量一定時，本文建立的應急觀測任務規劃模型在可用資源短缺時具有更好的效果。這是因為在資源緊缺時，任務之間的沖突嚴重，將有更多的任務需要等待可用資源，通過提高任務時間裕度，可以使有條件的任務盡早執行，為其他任務騰出資源，從而使更多的任務執行成功。

表4 不同資源數目時固定規模任務集規劃結果

Tab.4 Planning results under the condition of a certain task number and various resources

可用衛星數F規劃成功率/%F'規劃成功率/%效果提升/%233.7526.257.50451.2545.006.25680.0075.005.00

圖4 不同資源數目時固定規模任務集規劃結果對照

Fig.4 Comparison of planning results under the condition of a certain task number and various resources

6 結束語

本文根據衛星應急觀測的特點，建立了考慮目標觀測和數據下傳的應急觀測任務規劃模型，定義了兼顧重要性與緊迫性的任務優先級和時間裕度。通過計算實例可見，本文所提出的模型是合理有效的。相比典型研究[8-9]，本文建立的對地觀測規劃模型更具針對性：對目標觀測與數據下傳兩個過程進行一體化規劃計算，并考慮了雙重截止時間約束，模型中的優先級反映了緊迫性特征對觀測任務執行順序的要求，而時間裕度反映了對任務緊迫性要求的滿足程度，兩者結合能夠更全面地刻畫應急觀測任務規劃目標。

相比常規觀測，應急觀測的需求更為多樣化、條件更為苛刻，其規劃問題具有較大難度。為降低困難性，本文將對地觀測衛星限定在較為簡單的工作模式，并對對地觀測任務做了一定的簡化假設，下一步將在此基礎上，分析復雜的應急觀測任務，并對其規劃問題進行更為深入和全面的探討。

[1] WANG P,TAN Y J.Column generation for the earth observation satellites scheduling problem[J].System Engineering Theory & Practice,2011,31(10):1932-1939.

[2] 高黎,李志猛.對地觀測DSS任務分配問題的CSP模型與算法[J].空間科學學報,2012,32(2):251-256. GAO Li,LI Zhimeng.CSP model and algorithm on task allocation for earth observation DSS[J].Chinese Journal of Space Science,2012,32(2):251-256.(in Chinese)

[3] 賀川,朱曉敏,邱滌珊.面向應急成像觀測任務的多星協同調度方法[J].系統工程與電子技術,2012,34(4):726-731. HE Chuan,ZHU Xiaomin,QIU Dishan.Cooperative scheduling method of multi-satellites for imaging reconnaissance in emergency condition[J].Systems Engineering and Electronics,2012,34(4):726-731.(in Chinese)

[4] 王萬玉,張志強.多站多星任務調度模型及求解[J].電訊技術,2011,51(4):1-6. WANG Wanyu,ZHANG Zhiqiang.Multi-station multi-satellite task scheduling model and solution[J].Telecommunication Engineering,2011,51(4):1-6.(in Chinese)

[5] GABREL V,VANDERPOOTEN D.Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite[J].European Journal of Operational Research,2002,139(3):533-542.

[6] 張利寧,黃小軍,邱滌珊,等.對地觀測衛星任務規劃的啟發式動態調整算法[J].計算機工程與應用,2011,47(30):241-245. ZHANG Lining,HUANG Xiaojun,QIU Dishan,et al.Heuristic dynamic adjust of task scheduling for earth observing satellite[J].Computer Engineering and Applications,2011,47(30):241-245.(in Chinese)

[7] 陳宇.基于免疫粒子群算法的多星觀測調度研究[J].計算機仿真,2012,29(12):103-106. CHEN Yu.Research on multi-satellite observation scheduling based on immune particle swarm algorithm[J].Computer Simulation,2012,29(12):103-106.(in Chinese)

[8] 孫凱,陳成,陳英武,等.成像衛星星地聯合成像調度[J].控制工程,2012,19(4):695-698. SUN Kai,CHEN Cheng,CHEN Yingwu,et al.Modeling and simulation on imaging satellites and ground stations joint scheduling problem[J].Control Engineering of China,2012,19(4):695-698.(in Chinese)

[9] WANG P,REINELT G.A heuristic for an earth observing satellite constellation scheduling problem with download considerations[J].Electronic Notes in Discrete Mathematics,2010(36):711-718.

郭 超(1987—)，男，山東濟南人，博士研究生，主要研究方向為天基信息系統任務規劃與資源調度;

GUO Chao was born in Jinan,Shandong Province,in 1987.He is currently working toward the Ph.D. degree.His research concerns mission planning and resource scheduling of space-based information system.

Email：gch_87_10_26@126.com

熊 偉(1971—)，男，山東臨邑人，研究員、博士生導師，主要研究方向為天基信息系統綜合集成;

XIONG Wei was born in Linyi,Shandong Province,in 1971.He is now a senior engineer of professor and also the Ph.D. supervisor.His research concerns comprehensive integration of space-based information system.

劉呈祥(1990—)，男，黑龍江佳木斯人，博士研究生，主要研究方向為信息系統效能評估。

LIU Chengxiang was born in Jiamusi,Heilongjiang Province,in 1990.He is currently working toward the Ph.D. degree.His research concerns information system effectiveness evaluation.

Mission Planning of Satellite Emergency Observations Based on Priority and Time Margin Degree

GUO Chaoa,XIONG Weib,LIU Chengxianga

(a. Department of Graduate Management；b. Science and Technology on Complex Electronic System Simulation Laboratory,The Academy of Equipment,Beijing 101416,China)

Emergency observations are tasks executed by earth observation satellites to support some urgent ground operations.They are usually pressing and concentrative so as to increase the difficulty of mission planning.According to the characteristics of emergency observations,main attributes of satellites and tasks influencing mission planning are described.In consideration of both importance and emergency,task priority is defined,and time margin degree,an attribute about the extent of task emergency demand satisfaction,is put forward.A planning model is constructed,including an objective based on task priority and time margin degree,and constraints to satisfy.Then genetic algorithm is used to solve the model.Comparison with conventional mission planning with the objective to maximize task importance shows the proposed model is effective on promoting success rates of tasks.

earth observation satellites;emergency observation;mission planning;time margin degree

10.3969/j.issn.1001-893x.2016.07.005

郭超，熊偉，劉呈祥.基于優先級與時間裕度的衛星應急觀測任務規劃[J].電訊技術，2016,56(7):744-749.[GUO Chao,XIONG Wei,LIU Chengxiang.Mission planning of satellite emergency observations based on priority and time margin degree[J].Telecommunication Engineering,2016,56(7):744-749.]

2015-12-22；

2016-04-05 Received date:2015-12-22；Revised date：2016-04-05

TN927

A

1001-893X(2016)07-0744-06

**通信作者：gch_87_10_26@126.com Corresponding author：gch_87_10_26@126.com