缓存交换机确保时限调度的NP-C问题新解法

项目名称： 缓存交换机确保时限调度的NP-C问题新解法

项目编号： No.60873219

项目类型： 面上项目

立项/批准年度： 2009

项目学科： 金属学与金属工艺

项目作者： 李勇

作者单位： 中国科学院上海微系统与信息技术研究所

项目金额： 30万元

中文摘要： 本项目以任务调度的NP-C问题研究为理论基础，以解决建设北斗二代导航系统中实际问题为背景，从GPSIII的关键性能参数（KPP，Key Performance Parameters）和关键系统属性（KSA,Key System Attributes）入手，分别对GPSIII进行了系统分析，研究了点波束和星间链路技术的风险性，并对基于星间链路的卫星网络任务调度问题，提出了启发式的调度策略。具体内容包含：网络交换确保时限任务调度NP-C问题解法；无线信道资源优化及NP-C问题算法；星间链路任务调度NP-C问题算法（单轨道面）；GPSIII系统分析及风险性分析。带有星间链路的星座网络任务调度（SNRS问题）能有效解决星座不间断指管、减少AOD、近实时的故障处理、解决OTAR的时间周期等问题，并且与多项KPP相关。SNRS被证明一个是NP-C问题。提出了启发式策略来解决SNRS问题，指出在单轨道面的SNRS问题，EDF-MD算法的调度效果最优。并分别给出单轨道面上4、6、8、10颗卫星调度的仿真比较结果。该问题的解决对于KPP和KSA中许多参数的实现（如导航信息更新，OTAR问题）是有力支撑。

中文关键词： NP-C;导航; 调度;算法;无线电网络

英文摘要： The project study is based on NP-C issue theory of scheduling, facing the background of the real problem of building up COMPASS navigation system. The paper considers GPSIII's Key Performance Parameters (KPP), Key System Attributes (KSA), system description, spot beam, ISL/crosslink risk analyzed and satellite network range scheduling which proposes a heuristic scheduling policy. Listed below are the more concrete descriptions: The solution of deadline-guaranteed scheduling NP-C issues, radio networks resource optimization and algorithms, Satellites Network Range Scheduling (single orbit), system analysis of GPSIII and risks analysis of its critical technology. The highlight of SNRS is the constellation instantaneous commanding, age of data (AOD) reduction, near real-time failure settlement and OTAR reduction effectively, that is related to several KPP. SNRS is proved as a NP-C issue. In this paper a heuristic policy is proposed to solve the SNRS issue which points out that EDF-MD algorithm earns the best schedule effect in single orbit SNRS issue. What's more this paper gives the scheduling simulation results of the comparison in 4,6,8 and 10 satellites in single orbit respectively. The solution of SNRS issue is the powerful support of KPP and KSA parameters such as update of navigation information, OTAR etc.

英文关键词： NP-C; navigation; scheduling; algorithm; radio network