An Efficient Approach to Data Transfer Scheduling for Long Range Space Exploration

Long range space missions, such as Rosetta/Philae, require robust plans of data-acquisition activities and of the resulting data transfers. In this paper we revisit the problem of assigning priorities to data transfers in order to maximize safety margin of onboard memory. We propose a fast sweep algorithm to verify the feasibility of a given priority assignment and we introduce an efficient exact algorithm to assign priorities on a single downlink window. We prove that the problem is NP-hard for several windows, and we propose several randomized heuristics to tackle the general case. Our experimental results show that the proposed approaches are able to improve the plans computed for the real mission by the previously existing method, while the sweep algorithm yields drastic accelerations.

诸如罗塞塔（Rosetta）与菲莱（Philae）探测器在内的深空长距离航天任务，均需要针对数据采集活动及由此产生的数据传输制定严谨可靠的实施方案。本文重新探讨了为数据传输分配优先级以最大化星载内存安全余量的问题。我们提出了一种快速遍历算法以验证给定优先级分配方案的可行性，并针对单个下行链路窗口设计了一种高效的精确优先级分配算法。我们证明了多下行链路窗口场景下该问题属于NP难问题，并针对一般场景提出了多种随机启发式求解方法。实验结果表明，相较于现有方法为实际航天任务生成的实施方案，本文所提方法可有效优化方案效果，且所提出的遍历算法可实现计算效率的大幅提升。