中继卫星调度问题的CSP模型.pdf

《中继卫星调度问题的CSP模型.pdf》由会员分享，可在线阅读，更多相关《中继卫星调度问题的CSP模型.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、文章编号:1001-2486(2005)02-0006-05中继卫星调度问题的 CSP 模型?方炎申,陈英武,顾中舜(国防科技大学 信息系统与管理学院,湖南 长沙?410073)摘?要:中继卫星在地球同步静止轨道上运行,既能直视中、低轨道用 户航天器,又能直视地面站,是沟通用户航天器与地面站的桥梁。中继卫星调度问题是一类 非常重要的调度问题。基于约束满足理论,通过分析中继卫星调度问题的特点与约束条件,建立了中继卫星调度问题的 CSP 模型。利用卫星工具箱 STK 进行模拟仿真,对 CSP 模型进行了 求解。结果表明,所建立的 CSP 模型是合理的。关键词:跟踪与数据中继卫星系统;活动;资源;约

2、束满足问题;STK中图分类号:C93?文献标识码:ACSP Model of the Relay Satellite SchedulingFANG Yan-shen,CHEN Ying-wu,GU Zhong-shun(College of Information System and Management,National Univ.of Defense Technology,Changsha 410073,China)Abstract:The relay satellite,circulating on the GEO(Geogra phic Earth Orbit),can view t

3、he user spacecraft on the LEO(LowEarth Orbit)and the MEO(Middle Earth Orbit)directly as well,and view the ground station dire ctly.T he relay satellite can be seenas the bridge between the user spacecrafts and th e ground station.The scheduling problem withinTDRSS(Tracking and Data Relay Satellite S

4、ystem)is a very important problem.It analyses the characteristics and the constraintsof the relay satellite scheduling,andthenbuilds the CSP(Cons traints Satisfaction Problem)model of the problem based on CSP theory.The CSP model is solved with STK(Satellite Tool Kits)and simulation method.Computati

5、o nal experiments indicate that the performance of the CSP model is quite good.Key words:tracking and data relay satellite system;job;machin e;constraints satisfaction problem;satellite tool kits20 世纪 80 年代以来,以美国为代表的许多国家竞相发展以中继卫星系统为核心的航天通信测 控网,即航天通信测控天基网。与以地球站组网为主的地基网相比,航天通信测控天基网具 有许多优点,例如两颗中继卫星经过适当

6、的组网,可以基本覆盖整个中、低轨道航天器。因 此,由几颗中继卫星和一个地面测控终端站就可组成天基跟踪与通信系统,从而解决全轨道 跟踪多个航天器和高速数据传输的问题。目前世界上航天技术先进的国家,都十分重视发展 中继卫星系统。跟踪与数据中继卫星系统(TDRSS,Tracking and Data Relay Satellite System)是为中、低轨道的航天器与航天器之间、航天器与地面站之间提供数据中继、连续跟踪与轨道测控服 务的系统 1,2。中继卫星系统的链路分为前向链路与返回链路 3。前 向链路指地面站经数据中继卫星转发信号,向用户航天器(包括成像侦察卫星、航天飞机与 载人飞船等)发送跟

7、踪、遥测与控制指令。返回链路指用户航天器经数据中继卫星转发信号,向地面站回传航天信号(见图 1)。由于中继卫星的数量有限,中继卫星所包含的有效载荷数量与容量有限,用户航天器的跟踪、测控与数据中继需求不一定能全部被满足。因此,中继卫星调度的目标就是选择需要发送 航天信号的用户航天器,确定与用户航天器进行通信的中继卫星及其有效载荷,科学合理地 分配中继卫星系统资源以满足跟踪、测控与数据中继需要。目前,国内外关于中继卫星调度问题的研究大多注重于中继卫星系统的链路分析,主要是中 继卫星与用户航天器之间、不同的中继卫星之间的通信链路研究,包括天线的捕获跟踪与伪 随机码(PN 码)?收稿日期:2004-1

8、1-01基金项目:高校博士点专项科研基金资助项目(20049998022);国家部委 资助项目作者简介:方炎申(1976?),男,博士生。国?防?科?技?大?学?学?报?第 27卷第 2 期?JOURNAL OF NA TIONAL UNIVERSI TY OF DE FENSE TEC HNOLOGY?Vol.27 No.2 2005图 1?中继卫星系统的通信链路Fig.1?Communications links of TDRSS的捕获4,5,采用的方法多为模拟仿真方法。Marco Adinolfi 等6对欧洲空间局的数据中继卫星(DRS,Data Relay Satellite)调度问题

9、进行了研究,采用基于知识的启发式调度,开发了中继卫星调度系统;Rojanasoonthon 等 7针对美国的TDRSS,采用并行机调度理论对中继卫星调度问题进行了研究。调度的目标是在 规划的时间段内,分配中继卫星的天线资源,最大程度地完成用户所提交的任务需求数,将用户航天器视为工件,天线视为机器,并采用贪婪随机自适应搜索算法对问题进行求解。1?中继卫星调度问题中的活动与资源中继卫星调度问题中的要素包括:(1)活动中继卫星调度问题中的活动指中继卫星与用户航天器之间的信号传输活动,既包括前向链路 中的活动,也包括返回链路中的活动。中继卫星与用户航天器都是在太空高速运动的飞行器,其相对位置实时改变。

10、因此它们之间的星间链路建立(天线捕获与跟踪等)与信号传输,是一个复杂的过程。(2)资源中继卫星调度问题中的资源是中继卫星的天线,具体可分为单址天线与多址天线。单址天线 提供不同波段的单址链路,不同波段(S 波段、Ku 波段、Ka 波段)的信号都可以通过这条单址 天线进行传输。中继卫星一般配有两个单址天线。多址天线可同时提供若干条前向链路与返 回链路。通过多址天线的信号,采用码按多址进行区别,每种信号具有特定的伪随机码(PN 码)。(3)约束条件根据任务需求与中继卫星系统的工作特点,需要考虑以下主要约束条件:?中继卫星星座。如果采用多颗中继卫星组成星座,则可实现全球覆盖。任何时刻,用户 航天器都

11、能直视至少一颗中继卫星。对于给定的用户航天器,同一时刻可能直视多颗中继卫 星,这时需要确定向哪一颗中继卫星发送航天信号。?星蚀及日凌中断。每年在春分及秋分前后的 23 天中,每天当卫星的星下点进入当地时间 午夜前后,卫星、地球、太 阳共处在一条直线上。此时,地球挡住了太阳光,卫星处于地球的阴影区,这种现象称为星 蚀。在此期间,每天发生星蚀的持续时间不等。当卫星天线波束对准太阳时,天线的有效噪声温度增加,有时甚至使通信中断,这种现象称为日凌中断。对于极窄的天线波束来说,这 种效应极为严重,此时太阳光可能会充满整个波束,噪声温度将会提高数千度。?通信链路的同频干扰。TDRSS 中的通信链路采用天线

12、的相反极化、波束的不同指向,以减 小链路之间的相互干扰。但如果链路非常接近,链路之间的相互干扰将很突出。?用户航天器与中继卫星之间的可见时间窗口。只有用户航天器与中继卫星之间能够直视 时,用户航天器才能给中继卫星发送航天信号。在一段给定时间内,用户航天器同中继卫星 之间可能存在多个可见时间窗口,这时就需要确定采用哪个可见时间窗口来执行通信任务以 及通信的起始时刻。7方炎申,等:中继卫星调度问题的 CSP 模型?任务优先级。任务的优先级越高,其活动越需要优先安排。2?中继卫星调度问题的 CSP 模型基于约束满足的中继卫星调度建模,关键是要确定问题的约束条件,因此首先需要讨论中继 卫星调度问题的约

13、束类型。中继卫星调度问题是一种有限资源调度问题,本质上可以看成是 一种关联和互斥的资源分配问题(BERAP,Bunlded&Exclusion Resource Allocation Prob lem),其约束分为三类:(1)任务约束(Task Constraints)。主要表示一个任务是否必须被执行,用 Ct表示。(2)关联约束(Bunlded Constraint)。表示一旦任务被规划,则必须分配给一定的 资源,包括通信链路和可见时间窗口,用 Cb表示。(3)互斥约束(Exclusion Constraints)。表示同一种资源(主要是同一条通信链路的某个时 间窗口)不能同时分配给两个及两

14、个以上的任务,用 Ce表示。中继卫星调度问题的主要约束为:C=Ct?Cb?Ce(1)符号约定如下:任务变量:T=T1,T2,?,Tn,?i?n,Ti?0,1,Ti=1表示被规 划,Ti=0表示未被规划;资源集:M=m1,m2,?,m|M|,|M|为通信链路数目。对于一个任务变量,由于完成该任务的通信链路及可见时间窗口可能有多个,并且相互之间 可能具有可替换性。因此,在调度过程中,首先要选择能够完成任务的中继卫星通信链路,再选择卫星可见时间窗口。需求变量 Qij为第i 个任务对第k 个中继卫星通信链路的可 见时间窗口需求。虚拟资源(可见时间窗口):TW=TW11,1,TW11,2,?,TW11,

15、m,TW12,1,TW12,2,?,TW|M|2,p,?,TW|M|1,1,T W|M|1,2,?,TW|M|1,r(2)式中,TWni,k表示第i 个任务对第k 个中继卫星通信链路的时间窗口中的第 n 个,1?i?|J|,1?k?|M|,1?n?|TW|,|TW|表示时间窗口总数目,|TW|的取值由 实际计算得到。这里的可见时间窗口与中继卫星通信链路资源有对应关系。P=p1,p2,?,pn,pi为任务ji的优先级,1?i?|J|。基于以上约定,可以建立中继卫星调度问题的约束满足问题(CSP,Constraints Satisfac tion Problem)模型如下8,9:max:?piTi

16、(3)s.t.Ti?0,1pi?1,2,?,p Ct:Ct=(Tk=1),k?K?N;?Ct=?i?(N-K)(Ti=1)Cb:Cb(Ti)=?(Ti=0)?(?Ss?),i=1,2,?,n;?Cb(Ti)=?(Ti=0)?(?Qi,j?),i=1,2,?,n;Ce:Ce(TWsi,k)=?(Qi,s=TWsi,k)?(Qq,s=TWsi,k),if?q,r,st.TWsi,k?TWsq,r?(4)目标函数 max:?piTi明确了调度的目标是保证系统完成尽可能多的高优先级任务。约束条件说明:Ct:Ct=(Tk=1),k?K?N,N=1,2,?,n,表示任务变量集 T 的下标集。该约束 表示存

17、在一个任务的子集,其下标集为 K,该子集中的任何任务必须被规划执行。Ct=?i?(N-K)(Ti=1)则表示除去必须执行的任务之外,剩余的任务可以执行,也可以不执行,即约束 Ti=1 可满足,也可不满足。当然,对于调度的目标来讲,满足该条 件的调度方案更好。Cb:Cb(Ti)=?(Ti=0)?(?Qi,j?)表示或者 Ti=0 成立,或者?Ss?成立,即要么任务没8?国 防 科 技 大 学 学 报?2005年第 2 期有被规划(Ti=0),要么被规划(Ti=1),此时?Ss?,即至 少有一个卫星资源被分配给该任务。Ce:Ce(TWsi,k)=?(Qi,s=TWsi,k)?(Qq,s=TWsi,

18、k),if?q,r,st.TWsi,k?TWsq,r?,表示中继卫星的某 一条通信链路在一个时间段内,不能同时分配给两个需求变量。3?应用实例及结果分析考虑中继卫星TDRS-X1 的单址天线的任务调度问题。单址天线的可通信波段为 S 波段(SSA,S-band Single Access)、Ka 波段(KaSA,Ka-band Single Access),考虑的通信链路为返 回链路。仿真时间段:开始时刻为 15 Sep 2006 12:00,结束时刻为15 Sep 2006 20:00。在这给定的 时间段中,根据TDRS-X1 与各用户航天器的空间轨道参数,利用卫星工具箱 STK 10(Sa

19、tellite Tool Kits)进行模拟仿真,得到TDRS-X1 与各用户航天器之间的可见时间窗 口,将其作为中继卫星有效载荷与用户航天器有效载荷之间的可见时间窗口。表 1是 TDRS-X 1 与用户航天器 Spacecraft01 之间的可见时间窗口。表 1?TDRS-X1与 Spacecraft01 之间的可见时间窗口Tab.1?Time windows between TDRS-X1 and Spacecraft01时间窗口开始时刻结束时刻时间窗口长度(s)第 1 个12?00?0012?25?221 522第 2 个13?06?5214?16?134 161第 3 个14?56?1

20、816?11?094 491第 4 个16?47?3618?12?195 083第 5 个18?46?1820?00?004 422?各任务的优先级、持续时间以及所需资源见表 2。表 2?各任务的优先级与持续时间Tab.2?Priority and duration of task任务名称优先级持续时间所需用户航天器通信波段Comm01 of Inter-Orbit Link91h10minSpacecraft01SComm02 of Inter-Orbit Link21h22minSpacecraft02KaComm03 of Inter-Orbit Link21h11minSpacecra

21、ft03KaComm04 of Inter-Orbit Link31h44sSpacecraft04KaComm05 of Inter-Orbit Link259min11sSpacecraft05KaComm06 of Inter-Orbit Link257min9sSpacecraft06SComm07 of Inter-Orbit Link235min14sSpacecraft07SComm08 of Inter-Orbit Link738min57sSpacecraft08SComm09 of Inter-Orbit Link249min27sSpacecraft09SComm10 o

22、f Inter-Orbit Link252min43sSpacecraft10SComm11 of Inter-Orbit Link246min58sSpacecraft11SComm12 of Inter-Orbit Link357min18sSpacecraft12KaComm13 of Inter-Orbit Link242min11sSpacecraft13KaComm14 of Inter-Orbit Link252min42sSpacecraft14KaComm15 of Inter-Orbit Link21h3min11sSpacecraft15S?调度结果见表 3 和表 4。9

23、方炎申,等:中继卫星调度问题的 CSP 模型表 3?已完成任务及起始时刻Tab.3?Scheduled tasks and scheduling start and stop time任务名称通信波段优先级持续时间任务开始时刻任务结束时刻Comm08 of Inter-Orbit LinkS738min57s12?00?0012?38?57Comm07 of Inter-Orbit LinkS235min14s12?38?5713?14?11Comm06 of Inter-Orbit LinkS257min9s13?31?0514?28?14Comm01 of Inter-Orbit Link

24、S91h10min14?56?1816?06?18Comm10 of Inter-Orbit LinkS252min43s16?20?1317?12?56Comm11 of Inter-Orbit LinkS246min58s17?36?5418?23?52Comm09 of Inter-Orbit LinkS249min27s18?56?5519?46?22Comm04 of Inter-Orbit LinkKa31h44s12?52?5713?53?41Comm13 of Inter-Orbit LinkKa242min11s14?07?1114?49?22Comm12 of Inter-

25、Orbit LinkKa257min18s15?00?1115?57?29Comm05 of Inter-Orbit LinkKa259min11s15?59?2316?58?34Comm02 of Inter-Orbit LinkKa21h22min18?05?4119?27?41?表 4?未完成任务Tab.4?Unscheduled tasks任务名称通信波段优先级完 成任务所需时间未完成原因Comm03 of Inter-Orbit LinkKa21h11min资源冲突Comm14 of Inter-Orbit LinkKa252min42s资源冲突Comm15 of Inter-Orb

26、it LinkS21h3min11s资源冲突?结果分析如下:(1)调度的目标是完成尽可能多的优先级任务,因此优先级高的任务先安排调度。优先 级相同时,持续时间短的任务先安排调度。(2)中继卫星任务调度问题研究中,考虑了中继卫星与用户航天器之间的可见时间窗口约 束,即在给定的时间窗口内,中继卫星与用户航天器之间的信号传输活动才能进行。(3)在给定的时间段中,中继卫星与用户航天器之间的可见时间窗口往往存在多个,如果 信号传输过程不能被中断(非抢占式调度),并且某个时间窗口长度小于活动持续时间,则 时间条件不满足,应考虑其他的时间窗口。(4)在给定的时间段中,因为资源冲突,任务 3、任务 14 和任

27、务15 无法安排调度。4?结束语对于中继卫星调度问题,需要根据链路的方向、通信波段进行分类,然后在每一子类中 针对中继卫星与用户航天器之间的可见时间窗口、任务优先级,根据调度目标、调度准则进 行调度。采用约束满足理论,建立中继卫星调度问题的CSP 模型,是一种有效的方法。参考文献:1?总装备部卫星有效载荷及应用技术专业组应用技术分组.卫星应用现状与 发展M.北京:中国科学技术出版社,2001.2?王大珩,王淦昌,杨嘉墀,等.高技术辞典M.北京:清华大学出版社,科学出 版社,2000.3?夏南银.航天测控系统 M.北京:国防工业出版社,2002.4?Zillig D J.Perko K L,Ne

28、lson K G.New TDRSS Communications Options for S mall Satellites C.Space Operations 96,1996.5?马雨出.中继卫星系统星间链路建立中若干问题的研究D.哈尔滨工业大学,20 01.6?Adinolfi M,Cestal A.Heuristic Scheduling of the DRS Communication Syste m J.Engineering Applications of Artificial Intelligence,1995,8(2):147-156.7?Rojanasoonthon S,

29、Bard J F,Reddy S D.Algorithms for Parallel Machine Sc he duling:A Case Study of the Tracking and Data Relay SatelliteSystem J.Journ al of the Operational Research Society,2003,54(8):806-821.8?王正元,谭跃进,狄东宁,等.目标选择的一个优化模型 J.国防科技大学学报,2002,24(5):88-92.9?贺仁杰.成像侦察卫星调度问题研究 D.国防科技大学,2004.10?Analytical Graphics Inc.Satellite Tool Kit 5.0Z.2003.10?国 防 科 技 大 学 学 报?2005年第 2 期