第３期 卢建斌，等：基于非精确计算的空间探测相控阵雷达任务规划算法 １９ 来的目标观测任务，也就是在各个时刻所需要观测的目标，以及所需的引导信息。观测任务规划使得探测 系统从盲目搜索空间目标转变到有计划、有目的、有引导地主动探测和跟踪空间目标。这不仅使得整个探 测系统构成闭环处理回路，而且使处理效率大大提高。 众所周知，空间探测相控阵雷达系统作为一种新型的空间目标观测设备，具有作用距离远、跟踪目标 多、数据率高、自适应能力强等特点，具备全天候、全天时观测能力，在空间目标特别是低轨空间目标探测 中发挥着重要作用 Ｊ。相对于相控阵雷达调度器的微观驻留调度处理 Ｊ，观测任务规划是一种宏观的系 统资源分配，因此研究相控阵雷达任务规划方法，对提高相控阵雷达观测空间目标的效能有着重要意义。 对于远程空间探测相控阵雷达而言，其观测区域内的平均目标数目通常都超过１００个 Ｊ，因此相控阵 雷达一般情况下没有足够的资源来同时观测视场内所有的目标，也就是空间目标的观测任务对雷达系统 资源而言是过载的，此时相控阵雷达的观测任务规划处理，就需要考虑到任务过载下的容错处理。本文基 于实时调度系统中的非精确计算模型，提出了一种相控阵雷达观测任务规划方法，该算法通过非精确计 算，利用任务的强制执行段保证了观测任务数据对后续处理的有效性，利用任务的可选部分保证任务规划 的性能。利用实际的低轨空间目标仿真验证了算法的有效性，结果表明本文所提出的任务规划算法可以 显著提高系统的调度成功率和时间利用率，特别是在任务过载的情况下，本文的算法比传统的任务规划方 法有着明显的性能改善。 １ 观测任务规划问题描述 空间探测相控阵雷达的观测任务主要包括两个部分：搜索任务和跟踪任务。搜索任务的目的是发现 捕获新的目标，它是空间探测系统的基础，也是不断 丰富空间目标数据库的需要；跟踪任务的主要目的是 维持上述空间目标数据库，使得库中目标的轨道根数 得到不断的更新。典型的空间目标探测系统的功能 框图如图１所示。 对于空间探测相控阵雷达而言，搜索任务主要是 通过设置不同的搜索屏来完成，一旦搜索屏设置完 毕，搜索任务就完全确定，搜索任务所占用的雷达资 图１ 空间目标监视系统功能框图 源也同时确定。剩余的雷达资源就可以用来安排跟踪任务。但这里有两个问题：①在同一时间雷达探测 空域内一般都有多个目标存在，而且个数有可能超出雷达的跟踪能力上限，此时如何在这些目标中进行取 舍，即选择哪些目标进行跟踪观测？②对每一个目标而言，其在通过雷达探测空域时，雷达可观测到的弧 段（或时间）有可能较长，超出后续处理所要求的观测时间长度，那么如何在上述弧段中选择一定长的时 间段来进行雷达观测？这些就是需要任务规划来解决的问题。 ２基于非精确计算的任务模型 ２．１跟踪任务模型 根据空间探测系统的任务，任务规划应能够解决搜索任务和跟踪任务两类问题。由于相控阵雷达的 搜索任务由所设置的搜索屏确定，因此这里主要关注的是相控阵雷达的跟踪任务规划问题。对于相控阵 雷达，未来时间内的跟踪任务来源于系统内部的空间目标数据库，即根据数据库中的空间目标来规划未来 段时间内相控阵雷达的跟踪任务。 一假设依据空间目标数据库作未来［ ， ］时间段内的雷达观测任务，目标数据库中共有Ｐ个目标，针 对其中第ｉ个目标（１≤ ≤Ｐ），通过轨道外推可以预测得出该目标在［ ， ］时间段内过雷达观测区域 （也称为过境）ｎ 次，每次过境的进入时间和离开时间分别为｛ｆＪ１，￡ ｝ ＝１，２，…，ｎ 。如果没有其他特殊条 件的限制，那么对于探测系统来说，该目标的每次过境，相控阵雷达都可以进行观测，因此在［ ， ］时间 维普资讯 http://www.cqvip.com ２０ 飞行器测控学报 第２６卷 段内所需观测的总弧段有Ｎ＝∑ｎ 个，分别记为 Ａｒｃ ＝｛ｔ ｔ ，Ａｔ ，△ ｝， ｉ＝１，２，…，Ｎ （１） 其中 为相控阵雷达跟踪该目标时所选取的雷达工作波形， 为跟踪时的采样间隔时间，△ 为对该 目标进行观测的时间长度。这些参数需要依据一定的规则来确定，例如 根据雷达的探测距离来选取， 而 对于那些掌控精度较好或不重要的目标可以采用较大的跟踪采样间隔；同样，观测时长△ 对于不 同的处理任务需要不同的取值，如普通初轨计算所需的观测数据时长要比精密定轨少得多。 对于相控阵雷达系统的任务规划而言，上述的每个弧段都是一个观测任务请求，那么在［ ， ］时段 内的Ⅳ个观测弧段对相控阵雷达都会产生观测任务请求。根据实时任务调度模型，其中第ｉ个观测弧段 产生的雷达任务请求可表述为 ｒｅｑ ＝｛ｔ ｔ ，ｔ ，ｔ ，△ ， ， ｝ （２） 式中￡ 和￡ 分别为该任务的到达时间和截止期，其中到达时间指的是该任务可以安排执行的最早时刻， 截止期表示该任务必须在该时刻之前执行完毕。ｔ ，ｆ 表示该任务被安排执行的开始时间和结束时间。 为该任务的固有等级，由该任务所对应的空间目标的性质、轨道以及在空间目标数据库中的精度来确定。 为该任务所要消耗的资源，由下一节的任务资源占用模型来确定。这里有 ｔ ＝ｔ ｔ ＝ｔ （３） 在基于优先级驱动的实时任务调度中，需要确定每个任务的相对优先级，本文主要考虑任务的截止期 和任务固有等级，来确定任务的优先级。假设调度分析到ｔｐ时刻，那么任务请求ｒｅｇ 的优先级可定义为 ｐｒｉ ＝Ｒ （ｔ 一 ） （４） 上式表示每个任务的相对截止期越早、任务等级越高，该任务在调度分析中优先级越高，也就越优先得到 调度执行。 ２．２任务资源占用模型 相控阵雷达的系统资源主要根据搜索任务和跟踪任务进行分配。对于搜索任务，由于空间探测相控 阵雷达作用距离远，脉冲重复周期一般都比较长。这样就使得相控阵雷达不可能在整个监视区域进行全 空域搜索，只能是在某个或者某几个指定的仰角上设置一道或多道搜索屏来捕获新目标。。 。假定相控阵 雷达共设置ｓ道搜索屏，其中对第ｉ个搜索屏，雷达波束扫描一遍该搜索屏所有波位的时间为 ，该搜索 屏的搜索帧周期为 ，那么相控阵雷达在该搜索屏上消耗的雷达资源比率为 ／ ＝ （５） 参数 的物理意义是，表示在平均意义上该搜索屏的所有搜索任务对雷达系统时间资源所占去的份额。 由此可得相控阵雷达在全部搜索屏上所消耗总的雷达资源比率为 Ｓ １ … ｓ ｉ Ｌｏ 此外，对于相控阵雷达的跟踪任务，也就是指相控阵雷达对某个目标过境弧段的观测任务，假定相控 阵雷达对第ｉ个弧段Ａｒｃ ＝｛ｔ ｔ ，Ｗｉ，Ａｔ。，△ ｝进行观测，在对其观’坝４时间段内的雷达资源占用率为 ｎ＝Ｄｗ／Ａｔ￡，ｔ∈［ｔｎ，ｔ ２］ （７） 其中Ｄ 表示当相控阵雷达对该弧段观测采用第 种发射波形时，雷达对目标的一次波束照射时间， 也称驻留时间。这里主要考虑到相控阵雷达的跟踪波形通常有多种，如远距离跟踪波形、中距离或近距离 跟踪波形等。 ２．３非精确计算任务模型 在实际工程应用中，系统的工作负载常常会因为任务请求量的不确定而出现超载。为保证在系统超 载情况下，系统的性能不低于某个可以接受的阈值，可以引入非精确计算模型来增强整个系统的稳健 性 。非精确计算模型将任务请求分割为强制执行和可选执行两个部分。强制执行部分必须在任务的 截止期到来之前结束，以保证该任务的执行结果满足系统的最基本功能要求。对于可选执行部分的执行 维普资讯 http://www.cqvip.com
第３期 卢建斌，等：基于非精确计算的空间探测相控阵雷达任务规划算法 ２１ 可以有两种选择：一种是要么完全执行，要么完全丢弃；另一种是在时限到来前尽可能执行，以最大可能接 近精确输出。当可选执行部分在截止期前运行完成，则称该任务实现精确计算。 在系统允许的情况下，采用第二种选择可以达到更好的性能。本文就依据空间探测相控阵雷达系统 的特点，采用第二种选择方式来建立基于非精确计算的观测任务模型。对于式（２）中所建立的观测任务 模型，假定将每个任务的观测时间长度△ 分为两个部分：一个强制观测部分△ ，表示雷达系统必须在 该任务截止期到达之前观测△ 时间长度，以保证对该目标定轨、识别或者编目的最基本要求；另一部分 为可选观测时长△ ，表示在系统资源充裕的条件下，可以继续执行△ 时间长度，使得后端处理达到更 好的效果。 根据上述分析，第 个任务请求的非精确计算任务模型可表述为 ｒｅｑ ＝｛ｔ ｔ ｔ ，ｔ ，Ａ ，Ａ ，卵ｎ，Ｒ ｝ （８） 非精确计算对于实时系统而言，有着重要的意义。当系统负载出现超载时，系统在选择处理任务时可 以选择放弃部分任务的执行，以尽可能小的性能代价保证系统继续运行，并在系统负载恢复正常后获得理 想的输出。 ３任务规划算法 ３．１任务规划的基本思想 对于空间探测相控阵雷达的任务规划，搜索任务消耗固定的雷达资源叼 ，剩余的资源１一叼 可以用来 安排跟踪任务。而每个跟踪任务所消耗的资源卵 通常都小于１一叼 ，即对应着相控阵雷达可以同时跟踪 多个目标。问题的复杂性在于，一是跟踪任务具有时效性；二是每个目标跟踪参数的不同会引起雷达资源 占用率的变化，尤其是每个跟踪任务的强制执行时段一旦开始执行，就不能再被其他跟踪任务抢占，因此 这类问题可归结到实时系统非抢占式任务调度框架内。文献［９］对类似的问题进行了分析，指出该类问 题属于ＮＰ难题，通常情况下没有最优解，一般是利用启发式方法来进行求解。 针对上述任务规划问题，本文基于非精确计算的思想以及实时调度理论中经典ＥＤＦ调度算法¨ ，提 出一种非精确多任务并行ＥＤＦ（ＩＣ—ＭＴＰＥＤＦ）算法，该算法用来分析处理器可同时处理多个任务的情况， 而这正对应着相控阵雷达的多目标跟踪能力。 ＩＣ—ＭＴＰＥＤＦ算法的基本思想：将当前时刻到达的所有任务，根据其优先级的大小逐个添加到执行任 务链表中，同步地将雷达可用资源中减去每个任务所消耗的雷达资源。当有任务因为资源不足而无法添 加时，通过停止正在执行可选部分的任务来增大系统当前的可用资源，如果资源满足则添加当前最高优先 级的任务，否则将该任务推迟到有其他任务执行完毕（也就是雷达系统资源增大）的时刻。在上述过程 中，还需要不断地将超出截止期的任务删除，对已完成任务在其执行完毕时刻释放系统资源。 假设有６个等级相同的任务请求如图２所示，它 们在时间上先后依次到达。任务规划算法首先根据 任务到达时间的先后依次安排任务１—２—３，之后雷 达的剩余资源无法再安排任何任务。在任务１完成 时，由于剩余资源还不能满足任务４，只能将任务４推 迟到任务２完成的时刻，在这段时间内任务１可以执 行其可选部分。在任务２完成时，由于任务４的截止 期早于任务５而优先执行。在任务３执行完成时，任 务５由于资源仍不满足而继续推迟，最后在任务４完 成时，任务５由于超出其截止期而被删除。 ３．２任务规划算法的实现 任务编排 在任务规划处理实现时，可采用基于优先级的任 图２任务规划算法示意图 维普资讯 http://www.cqvip.com ２２ 飞行器测控学报 第２６卷 务链表，链表上的每个结点表示一个任务。对于任务规划中最多的添加、删除以及推迟等处理，在链表操 作中等同于插入或删除某个结点，这些链表中的操作都可以在线性时间内完成。 假设［ ， ］时间内的Ⅳ个任务请求｛ｒｅｑ ｝， １，２，…，Ⅳ，根据每个任务到达时间前后生成一个任务 请求链表，同时初始化任务执行链表和任务删除链表。起始条件下ｔｐ＝Ｔ１，ｒ／。 ＝１一ｒ／ ： Ｓｔｅｐｌ：针对当前时刻ｔｐ，找出任务请求链表中所有ｔ ≤ 的任务。将满足ｔ —Ａｔ７≥ｔｐ的观测任务请 求形成待处理任务集｛ｒｅｑ ｝，后＝１，２，…， ；不满足ｔ 一ａｔ７≥ 的任务将由于超出其截止期而被删除进人 任务删除链表中；同时从任务执行链表中找出所有正在执行可选部分的任务集合｛ｒｅｑ￣．｝， ＝１，２，…，ｔ，； Ｓｔｅｐ２：根据式（４）分别计算上述Ｋ个待处理观测任务集合中所有任务的优先级，并将这Ｋ个观测任 务按照优先级由大到小排列；同时暂停任务集｛ｒｅｑ￣．｝的执行，释放其占用的系统资源，得出当前ｔｐ时刻系 统的可用资源ｒ／ ；令ｋ＝１； Ｓｔｅｐ３：如果叼豫≤叼。 ，令ｔ ＝ ，将该观测任务从任务请求链表中转移到任务执行链表中，同时令 叩 ｒ／，ｐ一卵豫； ｓｔｅｐ４：令ｋ＝ｋ＋１，如果ｋ≤Ｋ且叼 ＞０，则返回到Ｓｔｅｐ３，否则进入Ｓｔｅｐ５； ｓｔｅｐ５：根据当前资源对所暂停执行可选部分的任务按照优先级的大小依次恢复执行，对由于资源限 制无法执行的任务，令其结束时间ｔ ＝ｔｐ； Ｓｔｅｐ６：找出任务执行链表中所有正在执行强制部分的任务最小完成时间ｔ ，将待处理任务集合中尚 未安排的任务推迟到时刻ｔ ；找出其他任务请求中最小的到达时间 ，令ｔｐ＝ｍｉｎ（ｔ ，ｔ ），对于所有在ｔｐ之 前完成的执行任务释放其占用的资源； ｓｔｅｐ７：若ｔｐ＜ 且任务请求链表非空，则返回到Ｓｔｅｐｌ；否则算法执行结束，输出的结果为任务执行链 表和任务删除链表。 归纳起来，Ｓｔｅｐｌ－－Ｓｔｅｐ７所描述的任务规划算法实现流程如图３所示。 开始 将时间上失效任务删除 形成待处理任务集 任霎务， 聂释放 妥系统资 ｌ源ｌ 根据优先级逐次添加执 行任务，更新系统资源 『Ｉ－ 酉 时问 根据优先级恢复所暂停 的任务，更新系统资源 否 是否完成？ 结束，输出结果 图３任务规划算法实现流程 ４任务规划效果评估 为了评估观测任务规划方法的性能，定义两个指标来反映算法对任务的调度分析能力，分别为调度成 功率和时间利用率。调度成功率定义为依据该算法在雷达资源约束条件下所能够安排的观测任务数目与 所有观测任务申请数目的比值，其表达式为 垂＝Ｎ ／Ｎ ９、） 维普资讯 http://www.cqvip.com
第３期 卢建斌，等：基于非精确计算的空间探测相控阵雷达任务规划算法 ２３ 其中 为安排执行的观测任务数目。时间利用率表示在执行完搜索和跟踪任务下雷达总的时间资源 Ｓ Ｎｓ 消耗比率，其表达式为 Ｕ＝∑ｒ／ ＋∑ｒ／巧‘（ 一 ）／（ 一Ｔ１） （１ｏ） 由此可见，调度成功率和时间利用率分别从观测任务和雷达资源两个方面反映了观测任务规划的效 果。一般情况下，当任务请求相对于雷达资源过多时调度成功率会比较低，反之时间利用率会比较低。这 两个评估指标都比较高，是最为理想的结果。 ５仿真结果与分析 假定某部典型的空间探测相控阵雷达，雷达阵面面向赤道，探测范围是方位±６０。、仰角０。～８５。。在 ＮＡＳＡ／ＧＯＤＤＡＲＤ所属ＭＵＬＴＩ—ＭＩＳＳＩＯＮ ＤＡＴＡ ＳＹＳＴＥＭ所公布的空间目标中，选取２８８６个目标（根数历 元为２００３年１１月２２日），进行２００３年１２月１日８时到２００３年１２月２日８时２４ｈ的观测任务规划。所 有目标的过境弧段总数为６８２７，本文的非精确计算模型中，要求雷达观测的最小时间长度为１ｍｉｎ，可选观 测时长为４ｍｉｎ，与之相比校的规划算法是固定观测时间长度为２ｍｉｎ。假设雷达进行目标跟踪时所选用的 波形单次驻留时间为５０ｍｓ，仿真结果如下。 当相控阵雷达对所有目标的跟踪采样间隔都为１ｓ时，在不同的可用跟踪资源条件下，两种任务规划 算法的调度成功率和时间利用率如图４和图５所示。从图中可以看出，当搜索资源占用较少，即可用的跟 踪资源较为充裕的条件下，两种任务规划算法的性能都相对较好；但是随着可用跟踪资源的减少，任务调 度的成功率都有所下降，同时时间利用率都提高。而基于非精确计算模型得到的结果明显优于传统的方 法，在搜索占用资源较少，跟踪可用资源较充裕时，基于非精确计算模型的规划方法可以保证所有任务的 执行，同时通过对任务可选部分的执行，保证了系统时间利用率；随着跟踪资源不断减少，由于任务请求量 保持不变，此时系统严重超载，传统的任务规划方法的调度性能显著下降，而基于非精确计算的规划算法 通过丢弃可选部分的执行，保证了系统的运行性能，同时由于对可选部分的灵活处理方式，时间利用率仍 然优于传统的方法。 瓣 瓣 旺 镁 ｛醚 厘 寒 茁 搜索资源占用率 搜索资源占用率 （跟踪采样间隔为１ Ｓ） （跟踪采样间隔为１ Ｓ） 图４调度成功率随搜索资源占用率的变化曲线 图５ 时间利用率随搜索资源占用率的变化曲线 图６和图７为跟踪可用资源一定的情况下，选取不同的跟踪采样间隔，也就是选取了不同的任务请求 负载量，系统调度成功率和时间利用率的变化曲线。从图中可以看出，当跟踪间隔较小时，任务请求量显 著高于可用资源，此时传统的任务规划算法由于系统严重过载而使得性能十分低下，随着跟踪间隔的加 大，任务请求负载量不断降低，此时系统的调度成功率不断升高，时间资源利用率相对下降。从调度成功 率变化曲线看，基于非精确计算的规划算法的性能一直保持在较高水平。对于时间利用率变化曲线的波 动，是由于对所有跟踪任务都选取了相同的跟踪间隔，那么在跟踪采样间隔为０．５ｓ、１ｓ、１．５ｓ和２ｓ时，每个 时刻的跟踪资源恰好整除单个目标的跟踪任务负载量，此时相当于系统的跟踪资源得到全部利用，即时间 维普资讯 http://www.cqvip.com 飞行器测控学报 … 第２６卷 利用率在这几处出现峰值。 ０．８ 褥 镫０．６ 寒 ０．４ 褥 旺 厘 曾 ０．２ ０．５ ０．７ ０．９ １．１ １．３ １．５ １．７ １．９ 跟踪间隔／ｓ （搜索资源占用率为０．４） 跟踪间隔／ｓ （搜索资源占用率为０．４） 图６调度成功率随跟踪任务采样间隔的变化曲线 图７ 时间利用率随跟踪任务采样间隔的变化曲线 需要指出的是，虽然仿真中对所有任务都采用了相同的观测参数，但是本文所提出的任务规划算法却 并没有对此进行限制。而且在实际的工程应用中，也需要对不同的目标采用不同的参数设置，同时搜索任 务可能并不是一个定值，本文所给出的任务规划算法对上述情况都能够适用。 ６ 结 论 针对空间探’钡０相控阵雷达系统，本文提出了一种基于非精确计算模型的观测任务规划算法，该算法已 在实际工程项目中得到成功应用，验证了算法的可行性。但实际中的空间探测系统是一个复杂的分布式 多传感器组合，包括光电传感器、无线电侦测以及雷达传感器，它可以提供更大范围的空间覆盖。而针对 这种多传感器分布式空间探测系统的任务规划和资源分配将是下一步的主要研究工作。 参考文献 李玉书．空间目标监视雷达技术探讨［Ｊ］．飞行器测控学报，２００３，２２（４）：６２－６６． 刘林．航天器轨道理论［Ｍ］．北京：国防工业出版社，２０００． 李元新，吴斌．空间目标编目维持中的观测需求确定方法研究［Ｊ］．飞行器测控学报，２００５，２４（１）：２６－３３． 张光义，王德纯，华海根，等．空间探测相控阵雷达［Ｍ］．北京：科学出版社，２００１． 卢建斌，胡卫东，郁文贤．多功能相控阵雷达实时任务调度算法研究［Ｊ］．电子学报，２００６，３４（４）：７３２－７３６． 超绍颖，杨文军．用于空间目标监视的相控阵雷达需求分析［Ｊ］．现代雷达，２００６，２８（１）：１６—１９． Ｃｈｕｎｇ Ｊ Ｙ，Ｌｉｕ Ｊ ｗ Ｓ，Ｌｉｎ Ｋ Ｊ．Ｓｃｈｅｄｕｌｉｎｇ Ｐｅｒｉｏｄｉｃ Ｊｏｂｓ Ｔｈａｔ Ａｌｌｏｗ Ｉｍｐｒｅｃｉｓｅ Ｒｅｓｕｌｔｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ，１９９０，３９（９）：１１５６— １１７４． ｏｓｅ Ｊ，ＴｏｗｓｌｅｙＤ．Ｏｎ—Ｌｉｎｅ ＳｃｈｅｄｕｌｉｎｇＰｏｌｉｃｉｅｓｆｏｒ ａ Ｃｌａｓｓ ｏｆＩＲＩＳ（ｉｎｃｒｅａｓｉｎｇ ｒｅｗａｒｄｗｉｔｈｉｎｃｒｅａｓｉｎｇ ｓｅｒｖｉｃｅ）Ｒｅａｌ—ｔｉｍｅＴａｓｋｓ［Ｊ］． ［８］ Ｄｅｙ Ｊ Ｋ，ＫｕｒＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ，１９９６，４５（７）：８０２４１３． ［９］ Ｊｅｆｆａｙ Ｋ，Ｓｔａｎａｔ Ｄ Ｆ，Ｍａｒｔｅｌ Ｃ Ｕ．Ｏｎ Ｎｏｎ—Ｐｒｅｅｍｐｔｉｖｅ Ｓｃｈｅｄｕｌｉｎｇ ｏｆ Ｐｅｒｉｏｄｉｃ ａｎｄ Ｓｐｏｒａｄｉｃ Ｔａｓｋｓ［Ｃ］．ＩＥＥＥ Ｒｅａｌ－Ｔｉｍｅ Ｓｙｓｔｅｍｓ Ｓｙｍｐｏｓｉｕｍ， ＵＳ，１９９１．１２９—１３９． ［１０］Ｌｉｕ Ｃ，Ｌａｙｌａｎｄ Ｊ．Ｓｃｈｅｄｕｌｉｎｇ Ａｌｇｏｉｒｔｈｍｓ ｏｆｒ Ｍｕｌｔｉｐｒｏｇｒａｍｍｉｎｇ ｉｎ ａ Ｈａｒｄ Ｒｅａｌ—Ｔｉｍｅ Ｅｎｖｉｒｏｎｍｅｎｔ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ ｈｔｅ ＡＣＭ，１９７３，２０（１） ４６－６１．
因篇幅问题不能全部显示，请点此查看更多更全内容