Task scheduling for optimal power management and quality-of-service assurance in nanosatellites

Abstract

O escalonamento de tarefas é uma abordagem eficaz para aumentar a extração de valor de uma missão espacial, podendo proporcionar uma melhor gestão de recursos e garantias de qualidade de serviço. Apesar de estar sujeito a muitas restrições, o escalonamento de tarefas em um satélite é, em última análise, restringido pela quantidade de energia disponível a qualquer momento. Nesta tese, é desenvolvido um framework para escalonamento de tarefas em nanossatélites focado no gerenciamento ótimo da energia disponível, enquanto garantindo qualidade de serviço. Uma formulação matemática de programação inteira (IP), projetada para maximizar o número de tarefas a serem executadas por um satélite, restrita à quantidade de potência disponível, momento a momento, ao longo de uma órbita é apresentada. O modelo de otimização é formulado para contemplar a prioridade da tarefa, número mínimo e máximo de ativação, tempo mínimo e máximo de execução, período mínimo e máximo e janela de execução. A decomposição de Dantzig-Wolfe é usada para explorar a estrutura especial da formulação mista inteira (MILP), decompondo-a por tarefas, o que resulta em uma nova formulação baseada em colunas para o problema. Para resolver a formulação resultante, é proposto um algoritmo branch-and-price (B&P) adequado para o escalonamento de um grande número de tarefas em um horizonte de tempo expandido. O vetor variante de energia de entrada foi calculado com base na eficiência das células solares e em um modelo analítico usado para estimar o campo de irradiância segundo parâmetros de órbita e atitude. Para demonstrar a aplicabilidade da metodologia, vários experimentos foram conduzidos considerando quatro tamanhos de satélites com diferentes órbitas e parâmetros de tarefa. Os resultados mostram que a estratégia de escalonamento offline proposta gera um plano de escalonamento eficiente e ótimo, permitindo o melhor uso possível dos recursos energéticos disponíveis e garantindo a qualidade de serviço. Além disso, a metodologia de solução B\&P se mostrou 88% mais eficiente computacionalmente para chegar a escalonamentos ótimos contraposto ao MILP.

Abstract: Task scheduling is an effective approach to increase the value of a satellite mission, which leads to improved resource management and quality of service. Despite subject to many constraints, satellite task scheduling is ultimately restricted by the amount of power available at any given moment. In this thesis, a nanosatellite task scheduling framework for optimal power management and quality-of-service assurance is developed. A mixed-integer linear programming (MILP) formulation is proposed, designed to maximize the number of tasks to be executed by a satellite, constrained to the amount of power available at any moment along the course of an orbit is presented. The optimization model is formulated to contemplate task priority, minimum and maximum number of task activation, minimum and maximum execution time, minimum and maximum period of a given task and execution window. The Dantzig-Wolfe decomposition is used to explore the special structure of the (MILP) formulation, decomposing it by tasks, which results in a novel profile-based formulation for the problem. To solve the resulting formulation, a branch-and-price (B&P) algorithm is developed, that is suitable for the scheduling of a large number of tasks over an expanded time horizon. The variant power input vector was calculated based on the solar cells efficiency and on an analytical model used to estimate the irradiance field according to parameters of orbit and attitude. To demonstrate the applicability of the methodology several experiments were conducted considering four satellite sizes with different orbits and task parameters. The results show that the proposed offline scheduling algorithm generates an optimal energy effective scheduling plan, allowing the best possible use of available energy resources while ensuring the quality of service (QoS). Furthermore, the B\&P methodology proved to be 88% more computationally efficient to reach optimal schedules as opposed to the MILP.