带星间链路转发能力的卫星网络通信任务实时调度算法研究

卫星-地面站通信任务调度是卫星系统运营管理的重要任务，也是富有挑战性的难题。在二代通信卫星系统普遍采用星座网络的背景下，现在的通信任务调度模型存在诸多不足：1）通信任务的调度仅在目标星和地面站间进行，未能利用星间链路的转发能力；2）调度模型中通信任务的调度是非抢占式的，资源分配粒度过粗；3）调度周期以日为单位，调度算法以搜索算法为主，周期过长。这导致卫星系统的运营管理对地面站的依赖度高且难以满足二代卫星系统星历表更新、Rekey和自主导航等控制信息传输频繁的需求。为此，本项目提出了一种带星间链路转发能力的卫星网络通信任务调度模型，在对卫星网络通信任务调度问题的复杂性深入研究的基础上，针对性地采用半正定规划或启发策略与约束条件适当松弛相结合的思路，以期设计出实时高效的调度算法。该项研究不仅能减少卫星网络对地面站的需求，而且对提高卫星系统的稳定性、导航和定位服务的精度具有重要意义。

星座网络系统由于具有了星间链路，使其运行和维护的方式明显不同于传统的卫星通讯系统。如何利用星间链路的转发能力来提高系统资源的利用率是星座网络系统的核心课题。本项目围绕星座网络的实时信息调度、网关卫星选择和可靠路由等问题展开研究，并取得了系列成果。..我们建立了星座网络的实时信息调度模型，证明了星座网络实时任务调度问题是NP完全的，同时证明了周期性实时任务的调度问题是强NP完全的。设计分析了实时任务调度的启发式算法。对于周期性实时任务调度问题，我们着重研究了静态优先级调度策略。证明了不同周期任务集中，短周期优先策略是最优的静态优先级策略等结论。..网关卫星选择问题是星座网络的一个新问题。我们采用了一种受限的支配集问题对其进行建模，证明了即使每颗卫星支持的星间链路数为3时，该问题仍然是NP完全的。并进一步证明了当可见层卫星的星间链路数小于3时，该问题可以转换为一种图上的最大匹配问题，因此是多项式可解的。同时，我们设计了网关卫星选择的贪婪算法，通过最小次模覆盖定理证明了该贪婪算法是O(log|V|)近似的。..确保时限的卫星分组交换是一个经典的NP完全问题。我们研究了确保时限的加权分组调度。设计了一种基于最大流的逆向迭代调度算法，理论分析证明该算法是2-近似的。据我们所知，这是目前最好的近似界。.此外，本项目研究了无线网络中连接一对节点（s和t）最长生命期的2-冗余路由问题。该问题是一种特殊的网络流问题，称之为并行可分解流问题，作为流分解定理的延伸，该问题不仅具有应用价值更有理论意义。我们证明了2-均衡性是可并行分解流的充分必要条件。并且设计了2-均衡流的分解算法，该算法将2-均衡流分解为O ̃(|V| |E|)对点不相交路（即2-冗余路）。同时，我们设计了k-冗余路的线性规划算法。