Приложения алгоритмов на графах для оптимизации работы орбитальной группировки дистанционного зондирования Земли

Авторы
Сазонова С.В.(1,2), Яганов Р.Т. (1)
Организации
Факультет Космических Исследований МГУ (1)
Центр фундаментальной и прикладной математики МГУ (2)
Сессия
Дистанционное зондирование Земли
Форма представления
Устный
Текст тезисов
\begin{document}
\maketitle
Управление системой дистанционного зондирования Земли (ДЗЗ) с большим количеством наземных станций и космических аппаратов (КА) является очень ресурсоемкой задачей. При планировании работы системы необходимо учитывать не только требования к качеству изображения, что влечет за собой ограничение на время и угол съемки, погодные условия и т.д., но и технические ограничения аппарата: объем памяти на борту КА, запас электроэнергии, орбитальные маневры КА и многое другое.

Рассмотрим систему с $N >= 1$ спутниками ДЗЗ, движущимися по заранее известным на рассматриваемый период времени траекториям. Ожидают исполнения $M$ заявок на съемку, для которых указаны область наблюдения и требования к качеству и характеристикам изображения. Заявка считается выполненной, если наземная станция получила требуемые видео- и/или фото данные. Необходимо сформировать полетные задания для каждого КА, обеспечивающие исполнение заявок наилучшим возможным способом. Выполнение полетного задания можно разделить на три этапа: передача задания с наземной станции на один из аппаратов, непосредственно съемка и передача информации с аппарата на наземную станцию.

Начнем с построения последовательности команд для КА, реализующей наилучшее выполнение заявок. Формирование соответствующих критериев качества заслуживает отдельного исследования. В нашей работы мы предполагали, что определен набор характеристик съемки, которые влияют на качество выполнения заявки. Обозначим этот набор $\overline{\omega} \in \Omega$, где $\Omega$ -- пространство допустимых значений выбранных характеристик.Определим некоторую функцию $P: \Omega \rightarrow \mathbb{R}$. В таком случае задача сводится к определению последовательности съемок $S$, дающей наибольшую сумму $\sum_{\omega \in \Omega_S} P(\omega_i)$, где $\Omega_S \in \Omega$ -- множество характеристик реализованных съемок.

Рассмотрим работу одного КА (случай $N=1$). Пусть для заявки $k = \overline{1,M}$ возможно $L_k$ наборов параметров съемки: $\omega_{ik}, \ i = \overline{1,L_k}$, -- каждый из которых может быть реализован на отрезке времени $(t_{\omega_{ik}1},t_{\omega_{ik}2})$. Определим $d(\omega_{mn},\omega_{kl})$ -- время, необходимое для настройки аппаратуры спутника для съемки с параметрами $\omega_{kl}$ после съемки с параметрами $\omega_{mn}$. Рассмотрим все $\omega_{ik}$ как вершины графа $G$ c весами $ P(\omega_{ik})$. Для любой пары вершин $(\omega_{mn},\omega_{kl})$ существует ребро, если $\Delta t = t_{\omega_{kl}1} - t_{\omega_{mn}2} >0 $ и $d(\omega_{mn},\omega_{kl}) < \Delta t$.
Добавим в граф $G$ вершины $A$ и $B$ с нулевыми весами, такие что $t_{A2} < \min_{\omega \in G} t_{\omega 1}$, $t_{B1} > \max_{\omega \in G} t_{\omega 2}$.

С использованием этих обозначений, задачу поиска оптимальной последовательности съемок для одного КА можно переформулировать как задачу поиска такого пути по графу из вершины $A$ в вершину $B$, что сумма весов входящих в него вершин максимальна. Возможно наложить дополнительные условия на переходы по дугам, соответствующие техническим ограничениям аппарата, например, запретить переход по дугам, если суммарная длительность съемок в соответствующих вершинах превышает некоторую величину $T$.

Данный подход был реализован нами для оптимизации работы полезной нагрузки аппарата EgyptSat-A ([1],[2]). В настоящее время мы работаем над развитием алгоритма для применения к системе из нескольких спутников.

Перейдем к задаче оптимизации связи между КА и наземными станциями. Как правило, каждый КА осуществляет лишь несколько сеансов связи в день, а необходимость в передаче команд может возникнуть в любое время. Предположим, что КА в рамках одной системы могут обмениваться информацией, когда находятся в пределах радиовидимости. Таким образом можно передавать команды с наземной станции на любой КА системы.
Рассмотрим мультиграф $G = \{V,E\}$, где $V =\{v_1,...,v_n\}$ --- множество вершин графа, соответствующих КА или наземным станциям, $E = \{e_1,...,e_m\}$ --- множество рёбер графа -- сеансов связи между элементами системы. Каждое ребро $e_j$ может быть охарактеризовано временем сеанса связи $(t_{j,0},t_{j,1})$ и пропускной способностью $D$. Предположим, что данные передаются пакетами объема $d$.
Каждый элемент системы можно рассматривать как действующий самостоятельно агент, который, зная топологию сети, стремиться оптимальным образом передать хранящиеся у него пакеты данных ([3],[4],[5]). Необходимо найти стратегию маршрутизации для каждого аппарата, которая обеспечивала бы максимальную эффективность передачи данных внутри системы.


Для описанных задач нами была построена модель спутниковой системы, реализован алгоритм планирования полезной нагрузки с возможностью ввода дополнительных ограничений. Были рассмотрены несколько примеров низкоорбитальных группировок спутников с различными наклонениями орбит и проведен ряд численных экспериментов для сравнения различных стратегий маршрутизации пакетов.

Список литературы:
\begin{enumerate}

\item Сазонова С. В., Строченкин А. В., Самыловский И. А. Дистанционное зондирование Земли: планирование и рациональный выбор маршрутов космических съемок // Тезисы XXI Научно-технической конференции молодых ученых и специалистов. — Т. 2. — г.Королёв, 2017. — С. 309–310.

\item Scalable real-time planning and optimization software complex for the purposes of earth remote sensing / V. Sazonov, S. a. Sazonova, I. Samylovskiy et al. // IFAC PapersOnLine. — 51-32. — Elsevier, 2018. — P. 451–455.

\item Fraire, J. A., P. Madoery, S. Burleigh, M. Feldmann, J. Finochietto, A. Charif, N. Zergainoh, и R. Velazco. «Assessing Contact Graph Routing Performance and Reliability in Distributed Satellite Constellations». Journal of Computer Networks and Communications 2017 (2017 г.): 1–18.

\item Merugu, Shashidhar, и Ellen Zegura. «Routing in space and time in networks with predictable mobility», январь 2004 г.

\item Xuan, B. Bui, A. Ferreira, и A. Jarry. «Computing shortest, fastest, and foremost journeys in dynamic networks». International Journal of Foundations of Computer Science 14, вып. 02 (апрель 2003 г.): 267–85. https://doi.org/10.1142/S0129054103001728.

\end{enumerate}


\end{document}