中继卫星多址链路调度问题的约束规划模型及算法研究.pdf-淘文阁

资源描述

《中继卫星多址链路调度问题的约束规划模型及算法研究.pdf》由会员分享，可在线阅读，更多相关《中继卫星多址链路调度问题的约束规划模型及算法研究.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、中继卫星多址链路调度问题的约束规划模型及算法研究方炎申?陈英武?王军民(国防科技大学信息系统与管理学院,长沙?410073)摘?要?中继卫星多址链路调度问题是中继卫星系统应用中必须解决的重要问题,其重要特点在于,中继卫星与用户航天器之间并非时时可见,因此通信任务存在可见时间窗口约束。只有在可见时间窗口内,通信任务才可能执行并完成。在进行合理假设的基础上,采用人工智能中的约束规划技术,建立中继卫星多址链路调度问题的约束规划模型,并提出了基于时间窗口期望值的多步迭代算法。应用结果表明,中继卫星多址链路调度模型的建立与求解是合理的。关键词?跟踪与数据中继卫星系统?多址链路?调度?约束规划收稿日期:2

2、006-08-29Constraint Programming Model and Algorithms for Multiple Access LinksScheduling of Tracking and Data Relay Satellite System(TDRSS)Fang Yanshen?Chen Yingwu?Wang Junmin(College of Information Systems andManagement,National University of Defense Technology,Changsha?410073)Abstract?Multiple acc

3、ess links scheduling of Tracking and Data Relay Satellite System(TDRSS)isto support taskplan making of TDRSS scientifically?One of the most important characteristics of the scheduling problem lies in that thereis time windows constraint between Tracking and Data Relay Satellite(TDRS)and user spacecr

4、aft?The tasks can only becompleted within the given time windows?The paper builds the constraint programming model of the scheduling problembased on reasonable assumptions?The model is solved with Multiple Pass Algorithm based on Time Windows PositionRanking(MPATWPR)?On the basis of a limited experi

5、ment,we observe that the algorithm is very effective in obtainingnear-optimal solutions?Key Words?Tracking and data relay satellite system(TDRSS)?Multiple access links?Scheduling?Constraintprogramming1?引言跟踪与数据中继卫星系统(TDRSS,Tracking andData Relay Satellite System)是为中、低轨道的航天器与航天器之间、航天器与地面站之间提供数据中继、连续跟踪

6、与轨道测控服务的系统。中继卫星系统通常包括中继卫星(TDRS,Tracking and Data Relay Sate-llite)、用户航天器与地面站3 个部分 1。20世纪80 年代以来,以美国为代表的许多国家竞相发展以跟踪与数据中继卫星系统为核心的航天通信测控网,即航天通信测控天基网。航天通信测控天基网与以地球站组网为主的地基网相比,具有许多优点,例如两颗卫星经过适当的组网,可以基本覆盖整个中、低轨道航天器。中继卫星多址链路调度问题是根据中继卫星系统应用的任务需求,对中继卫星系统多址链路资源62?航天返回与遥感SPACECRAFT RECOVERY&REMOTE SENSING第 27

7、卷第 4期2006 年 12月进行优化配置,对信息的获取、处理与传输活动进行优化调度,制定出满足中继卫星应用任务需求的资源分配和活动调度方案。中继卫星多址链路调度是中继卫星应用中的重要问题,对于中继卫星系统资源的充分利用、有效发挥中继卫星系统的性能具有重要意义。目前,国内外关于中继卫星系统的应用研究大多注重于中继卫星系统的链路分析,主要是中继卫星与用户航天器之间、不同的中继卫星之间的通信链路研究,包括天线的捕获跟踪与伪随机码的捕获,采用的方法多为模拟仿真方法。关于中继卫星多址链路调度问题的模型与算法方面的研究,可参见文献 2、3。中继卫星多址链路调度问题可以看作具有时间窗口约束的并行机调度问题

8、。目前,关于具有时间窗口约束的并行机调度问题的研究主要包括:所有任务具有公共的时间窗口约束,表现形式是所有任务具有公共交货期 4 6;每个任务具有不同的时间窗口约束,表现形式是每个任务具有自己的交货期,并且每个任务具有的可见时间窗口数量有且仅有一个7。文章根据中继卫星系统及其应用的特点,建立了中继卫星多址链路调度问题的约束规划模型,并提出了基于时间窗口期望值的多步迭代算法。2?中继卫星多址链路调度中的活动与资源?中继卫星的天线包括单址天线与多址天线,是中继卫星系统中的重要有效载荷。单址天线提供不同波段的单址链路,不同波段的信号都可以通过这条单址天线进行传输。多址天线可同时提供若干条前向链路与返

9、回链路。中继卫星多址链路调度问题中的要素包括:(1)活动中继卫星多址链路调度问题中的活动指中继卫星与用户航天器之间的信号传输活动,既包括前向链路中的活动,也包括返回链路中的活动。中继卫星与用户航天器都是在太空高速运动的飞行器,其相对位置实时改变,因此它们之间的星间链路建立(包括天线捕获与跟踪等)与信号传输,是一个复杂的过程。(2)资源中继卫星多址链路调度问题中的资源是中继卫星的多址天线。通过多址天线的信号,采用码分多址进行区别,每种信号具有特定的伪随机码(PN码)。(3)约束条件根据任务需求与中继卫星系统的工作特点,需要考虑以下主要约束条件:1)中继卫星星座。如果采用多颗中继卫星组成星座,则可

10、实现全球覆盖。任何时刻,用户航天器都能直视至少一颗中继卫星。对于给定的用户航天器,同一时刻可能直视多颗中继卫星,这时需要确定向哪一颗中继卫星发送航天信号。2)星蚀及日凌中断。中继卫星除了围绕地球运转之外,还随地球一起环绕太阳公转。每年在春分及秋分前后各 23 天中,每天当卫星的星下点进入当地时间午夜前后,卫星、地球、太阳共处在一条直线上。此时,地球挡住了太阳光,卫星处于地球的阴影区,这种现象称为星蚀。在此期间,每天发生星蚀的持续时间不等。当卫星天线波束对准太阳时,天线的有效噪声温度增加,有时甚至使通信中断,这种现象称为日凌中断。对于极窄的天线波束来说,这种效应极为严重,此时太阳光可能会充满整个

11、波束,噪声温度将会提高数千度。3)通信链路的同频干扰。中继卫星系统中的通信链路采用天线的相反极化、波束的不同指向,来减小链路之间的相互干扰。但是如果链路非常接近,链路之间的相互干扰将很突出。4)用户航天器与中继卫星之间的可见时间窗口。只有用户航天器与中继卫星之间能够直视时,用户航天器才能给中继卫星发送航天信号。在一段给定时间内,用户航天器同中继卫星之间可能存在多个可见时间窗口,这时就需要确定采用哪个可见时间窗口来执行通信任务以及通信的起始时刻。5)任务优先级。任务的优先级越高,其活动越需要优先安排。3?中继卫星多址链路调度问题的特点中继卫星多址链路调度问题具有以下特点:1)中继卫星多址链路调度

12、问题的重要特点在于编制任务计划时需要调度的任务具有可见时间窗口约束,并且在一定的调度周期内往往具有多个时间窗口。对于中继卫星系统的某一多址链路(如 S 波段方炎申?等:中继卫星多址链路调度问题的约束规划模型及算法研究63?多址链路),中继卫星与用户航天器之间并非时时可见,而是具有时间窗口限制,即中继卫星与用户航天器之间的通信任务在可见时间窗口内才能进行,如图1 所示。STWi,j表示时间窗口的开始时刻,ETWi,j表示时间窗口的结束时刻,di表示通信任务ri的持续时间。图 1?通信任务的时间窗口约束中继卫星多址链路调度问题中,如果通信任务安排调度过程中不能被中断(非抢占式调度),并且某个时间窗

14、刻。2)对于中继卫星与用户航天器之间的某一多址链路,任务可以并行执行,并行执行的任务数量取决于多址链路的多址能力。3)对于中继卫星多址链路调度,不能采用一般的线性规划方法建立调度模型,可以考虑采用人工智能中的约束规划方法建立调度模型。4?中继卫星多址链路调度问题的约束规划模型?中继卫星多址链路调度问题可以看作一类约束满足问题(CSP,Constraint Satisfaction Problem),使用人工智能中的约束规划技术进行求解。约束满足问题是计算机科学和人工智能研究的核心问题之一。现实生活中的许多组合、调度优化问题都可以描述为约束满足问题。一个 CSP 由一个变量集合、每个变量的值域以

15、及一个限制变量取值的约束的集合组成。约束满足问题的任务就是在各变量的值域范围内,为所有的变量找到一个赋值,尽可能使所有的约束得到满足 8。中继卫星多址链路调度问题的约束规划模型如下:Max:?xi,jpi(1)?R=r1,r2,?r|R|L=l1,l2,?l|L|xx,j?0,1,i=1,2,?,|R|,j=1,2,?,|L|VtWki,j?(0,1),i=1,2,?,|R|,j=1,2,?,|L|,k=1,2,?,|TWi,j|pi?1,2,?,p,i=1,2,?,|R|Ti,j?STWki,j,if?vtwki,j=1Ti,j+di,j?ETWki,j,if?vtwki,j=1TS?Ti,

16、j?TE,TS?Ti,j+di,j?TE,i=1,2,?,|R|,j=1,2,?|L|(2)?目标函数Max:?xi,jpi明确了调度的目标是保证系统完成尽可能多的高优先级任务。约束条件说明:通信任务集 R=r1,r2,?,r|R|,|R|表示需要安排调度的通信任务数量。多址链路集 L=l1,l2,?,l|L|,|L|表示中继卫星系统中的多址链路所包含的链路数量。任务变量集 X=x1,1,x1,2,?,xi,j,?,x|R|L|(i=1,2,?,|R|,j=1,2,?,|L|),且 xi,j?0,1。xi,j=1 表示通信任务 ri在链路lj上安排调度;xi,j=0 表示通信任务 ri不在链路

17、lj上安排调度。时间窗口决策变量 vtwki,j,如果通信任务 ri在链路 lj上安排调度,在时间窗口 TWki,j内执行任务(TWki,j=STWki,j,ETWki,j),则 vtwki,j=1,否则 vtwki,j64?方炎申?等:中继卫星多址链路调度问题的约束规划模型及算法研究=0。任务的优先级 pi?1,2,?,p,i=1,2,?,|J|,p 为正整数。任务的优先级越高,任务越优先执行。任务 ri在链路lj上安排调度时必须满足时间窗口约束。任务开始执行的时刻为 Ti,j,任务的持续时间为 di,j。Ti,j?STWki,j(1?k?|TWi,j|)表示任务 ri必须在可见时间窗口 T

18、Wki,j的开始时刻STWki,j之后开始执行,Ti,j+di,j?ETWki,j表示任务ri必须在可见时间窗口TWki,j的结束时刻 ETWki,j之前执行完毕。|TWi,j|表示通信任务 ri在链路 lj上安排调度时的可见时间窗口数量。TS?Ti,j?TE,TS?Ti,j+di,j?TE(i=1,2,?,|R|,j=1,2,?,|L|)表示所有的通信任务必须在给定的调度时间段 TS,TE 内安排调度。TS表示调度时间段的开始时刻,TE表示调度时间段的结束时刻。5?基于时间窗口期望值的多步迭代算法5?1?算法思想中继卫星多址链路调度问题中,任务往往具有多个时间窗口约束,因此不能采用一般的精确

19、算法与启发式算法求解,文章提出了一种基于时间窗口期望值的多步迭代算法(MPATWPR,Multiple Pass A-lgorithm based on Time Windows Position Ranking)。运行MPATWPR需要首先运行One Pass 算法(OPA,OnePass Algorithm),下面先分析 OPA 的基本思想。OPA 按照任务的优先级决定分配资源的顺序,当优先级相同时,根据任务的顺序确定分配资源的先后顺序。当一个任务具有多个时间窗口时,根据时间窗口的期望值(Position Ranking)决定在哪一个时间窗口中执行任务,优先选择期望值高的时间窗口。对每个任

20、务,都尽可能早地分配资源,以使其尽早执行。MPATWPR的基本思想:多次利用 OPA,在每次使用 OPA 之前,对任务次序、时间窗口次序进行调整,并利用专家系统规则生成可能的任务和时间窗口列表。每次调用 OPA 生成的调度方案,都给出一个评价指数 FOM(Figure of Merit),最后选择出 FOM最大的方案作为最终的调度方案 9。OPA 算法简单,易于理解,执行速度快,整个调度方案一次完成,即使存在冲突也不进行调整,适用于对资源的利用冲突少的问题。相对于 OPA,MPATWPR 需要更多的计算时间,但能产生较好的调度方案,适合中等资源冲突的问题。5?2?时间窗口期望值的计算时间窗

21、口的期望值 Position Rankingi是当任务具有多个时间窗口时,对每个时间窗口根据用户调度的偏好所赋予的一个位置级别值。时间窗口期望值的计算方法如下:1)根据调度偏好确定出每个时间窗口的期望值Desirabilityi调度偏好为 Early 时,任务的第一个时间窗口的开始时刻设为 100,即期望值也为 100,最后一个时间区间的开始时刻设为 0,其期望值也为 0,其余时间窗口的期望值按其开始时刻在第一个和最后一个时间窗口开始时刻的相对位置比例进行计算。调度偏好为Middle 时,调度周期的中间时刻设为 100,开始时刻、结束时刻设为 0。所有时间窗口的期望值按其开始时刻的位置比例进行

22、计算。调度偏好为Late 时,任务的第一个时间窗口的开始时刻设为 0,其期望值也为 0,最后一个时间窗口的开始时刻设为 100,其期望值也为 100,其余时间窗口的期望值按其开始时刻在第一个和最后一个时间窗口开始时刻的相对位置比例进行计算。2)计算每个时间窗口的位置级别值每个时间窗口的位置级别值计算公式如下:PositionRankingi=Desirabilityi100(3)PositionRankingNom为任务所有可执行时间窗口位置级别值的最大级别值,即PositionRankingNom=MaxPositionRankingi(4)5?3?评价指数的确定利用某种调度算法对调度问题进

23、行调度时,可能会产生几种不同的调度方案。通过计算每一种方案的评价指数 FOM,对每一种方案进行比较评价,最后挑选出 FOM 最大的调度方案作为最终的调度方案。中继卫星多址链路调度问题中,最终显示出来的调度方案即为一系列调度方案中 FOM 最大的调度方案。方炎申?等:中继卫星多址链路调度问题的约束规划模型及算法研究65?6?仿真算例下面考虑中继卫星系统的某一多址数传链路,多址数传链路能够并行执行的任务数量为 2。仿真时间段为:调度开始时刻:15 Sep 2006 12:00;调度结束时刻:15 Sep 2006 20:00。在给定的时间段中,根据中继卫星与各用户航天器的空间轨道参数,利用 STK

24、(Satellite Tool Kits)进行模拟仿真9,得到通信任务 r1的可见时间窗口。通信任务 r1的可见时间窗口见表 1。表 1?通信任务的可见时间窗口时间窗口开始时刻结束时刻时间窗口长度/s第 1 个12:00:0012:25:221522第 2 个13:06:5214:16:134161第 3 个14:56:1816:11:094491第 4 个16:47:3618:12:195083第 5 个18:46:1820:00:004422针对中继卫星与各用户航天器之间的时间窗口、通信任务的优先级等各种约束条件,建立调度问题的约束规划模型,并采用基于时间窗口期望值的多步迭代算法对约束规划

25、模型进行求解。调度结果见表 2 和表 3,调度结果的甘特图见图 3。表 2?安排调度的任务任务名称优先级持续时间任务开始时刻任务结束时刻r111000:34:0012:00:0012:34:00r13800:59:0012:17:0013:16:00r10200:23:0012:34:0012:57:00r1300:31:0013:06:5213:37:52r12300:51:0013:16:0014:07:00r3200:32:0013:43:1914:15:19r2300:44:0014:19:4615:03:46r7301:02:0014:36:3915:38:39r4200:43:00

26、15:03:4615:46:46r8200:47:0015:52:4916:39:49r5201:00:0015:59:2316:59:23r9200:40:0017:07:0617:47:06r6200:56:0017:12:2318:08:23r15201:02:0018:42:4019:44:40表 3?不能安排调度的任务及原因任务名称优先级完成任务所需时间不能调度的原因r14101:13:00资源冲突可见,针对给定的中继卫星多址链路,因为多址链路上同一时刻能安排两个通信任务并行执行,因此大部分任务能够安排调度执行。只有任务 r14因为资源冲突,不能在给定调度区间内安排执行。图 3?调度

27、结果的甘特图7?结论中继卫星任务规划与调度是中继卫星系统应用中的重要问题。根据中继卫星与航天器的空间轨道参数,得到通信任务的时间窗口约束。常用的线性规划方法不能有效求解中继卫星多址链路调度问题。本文通过分析中继卫星系统中各种资源之间的约束关系、任务优先级与调度准则,建立中继卫星多址链路调度问题的约束规划模型,并提出了基于时间窗口期望值的多步迭代算法。约束规划理论与方法不仅可用于解决中继卫星多址链路调度问题,还可用于求解其他类似问题。参考文献1?Daniel L Brandel,William A Watson,Aaron Weinberg?NASA?s Advanced Tracking

28、 and Data Relay Satellite Systemfor the years 2000 and beyond J?Proceedings of the IEEE,1990,78(7):1141-1151?2?Marco Adinolfi,Amedeo Cestal?Heuristic scheduling of theDRS communication system J?Engineering Applications of66?方炎申?等:中继卫星多址链路调度问题的约束规划模型及算法研究Artificial Intelligence,1995,8(2):147-156?3?S

29、Rojanasoonthon,JF Bard,SD Reddy?Algorithms for parallelmachine scheduling:a case study of the Tracking and Data Re-lay Satellite SystemJ?Journal of the Operational Research So-ciety,2003,54(8):806-821?4?Zhi-Long Chen,Chung-Yee Lee?Parallel machine schedu-ling with a common due windowJ?European Journ

30、al of Opera-tional Research,2002,136:512-527?5?Gur Mosheiov?A common due-date assignment problem onparallel identical machines J?Computers&Operations Re-search,2001,28:719-732?6?Farouk Yalaoui,Chengbin Chu?Parallel machine scheduling tominimize total tardinessJ?International Journal of ProductionEco

31、nomics,2002,76:265-279?7?V Gabrel?Scheduling jobs within timewindows on identical par-allel machines:New model and algorithmsJ?European Jour-nal of Operational Research,1995,83:320-329?8?方炎申,陈英武,顾中舜?中继卫星调度问题的 CSP 模型J?国防科技大学学报,2005,27(2):6-10?9?Analytical Graphics Incorporation(AGI)?Satellite Tool Ki

32、t 5?0Z?2003?作者简介:方炎申,男,1976年生。2003年毕业于国防科技大学军事运筹学专业,获军事学硕士学位。现为国防科技大学管理科学与工程专业博士研究生,主要研究方向:系统规划与管理决策技术。陈英武,男,1963年生。1994 年毕业于国防科技大学系统工程专业,获工学博士学位。现为国防科技大学教授,博士生导师,主要研究方向:系统规划与管理决策技术、装备采办与项目管理。王军民,男,1973年生。2000 年毕业于国防科技大学系统工程专业,获工学硕士学位。现为国防科技大学信息系统与管理学院博士研究生,研究方向:系统优化与综合集成技术。方炎申?等:中继卫星多址链路调度问题的约束规划模型及算法研究67?

展开阅读全文