中文摘要：

本项目以任务调度的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问题）是有力支撑。