Содержание к диссертации
Введение
Глава 1. Исследование принципов построения бортовых информационно-управляющих систем с параллельной архитектурой 11
1.1. Анализ функционального и алгоритмического облика бортовых информационно-управляющих систем 12
1.2. Принципы структурной организации современных бортовых информационно-управляющих систем 22
1.3. Особенности архитектуры параллельных вычислительных комплексов...29
1.4. Планирование и диспетчеризация вычислительных процессов в БИУС с параллельной архитектурой 37
Основные результаты и выводы по первой главе. Постановка задачи исследования 48
Глава 2. Совмещенный синтез алгоритмического обеспечения и топологии автоматической бортовой системы управления с параллельной архитектурой 51
2.1. Формализация процедуры формирования архитектуры автоматической бортовой системы управления 52
2.2. Аналитическая модель для описания вычислительных процессов в автоматической бортовой системе управления 65
2.3. Процедура совмещенного синтеза алгоритма управления и топологии многопроцессорной БИУС ,. 77
Основные результаты и выводы по второй главе 89
Глава 3. Выбор оптимальной архитектуры бортовых информационно-вычислительных систем с использованием адаптивного генетического алгоритма 91
3.1. Разработка алгоритма глобального распараллеливания задачи спутниковой навигации 92
3.2. Разработка метода диспетчеризации вычислительных процессов на базе адаптивного генетического алгоритма 104
3.3. Разработка алгоритма выбора структуры БИВС, оптимальной по заданной совокупности показателей 116
Основные результаты и выводы по третьей главе 125
Глава 4. Программный комплекс исследования и оптимизации архитектуры бортовых информационно-управляющих систем 127
4.1. Программная реализация алгоритмов глобального и локального распараллеливания задачи спутниковой навигации 127
4.2. Программная реализация методики диспетчеризации вычислительных процессов на базе адаптивного генетического алгоритма 146
4.3. Программное обеспечение процедуры поиска оптимальной топологии бортовой информационно-управляющей системы 149
Основные результаты и выводы по четвертой главе 154
Заключение 156
Список литературы 159
- Анализ функционального и алгоритмического облика бортовых информационно-управляющих систем
- Формализация процедуры формирования архитектуры автоматической бортовой системы управления
- Разработка алгоритма глобального распараллеливания задачи спутниковой навигации
- Программная реализация алгоритмов глобального и локального распараллеливания задачи спутниковой навигации
Введение к работе
Актуальность темы. Повышение эффективности эксплуатации воздушного транспорта тесно связано с необходимостью увеличения пропускной способности воздушного пространства и, как следствие, с увеличением пассажиропотоков и регулярности выполнения авиарейсов, с сокращением эксплуатационных затрат за счет выбора кратчайших и наиболее экономичных маршрутов к пунктам назначения, а также с повышением безопасности полетов при росте интенсивности воздушного движения. Чтобы выполнить такие, во многом противоречивые требования, международное авиационное сообщество разработало концепцию CNS/ATM, согласно которой каждому летательному аппарату, находящемуся в установленном воздушном пространстве, должна быть задана индивидуальная траекторию движения, оптимальная с точки зрения эффективности выполнения его полетного задания. При этом задача обеспечения высокоточной реализации индивидуальных траекторий движения возлагается на автоматическую бортовую систему управления (АБСУ), способную управлять всеми фазами полета от запуска до посадки. Функции АБСУ предусматривают также выполнение всех сложных навигационных расчетов, включая наиболее точную оценку местоположения самолета по информации, собранной из всех навигационных датчиков, и прогноз поведения других участников воздушного движения с целью предотвращения конфликтных ситуаций.
Большая заслуга в разработке современных бортовых систем управления принадлежит видным отечественным ученым и конструкторам Белому Ю.И., Крюкову СП., Парамонову П.П., Петрову В.М., Солдаткину В.М., Федосову Е.А., Федунову Б,Е. Вопросам повышения эффективности систем авиационной автоматики посвящены работы Петрова Б.Н., Рутковского В.Ю, Васильева В.И., Гуревича О.С., Гусева Ю.М., Землякова С.Д., Ильясова Б.Г., Лебедева Г.Н., Крымского В.Г., Куликова Г.Г., Юсуповой Н.И.
Однако по мере усложнения функций, возлагаемых на АБСУ, и увеличения их количества на повестку дня выходит задача разработки интегрированной системы управления полетом на базе многопроцессорных вычислительных
комплексов с параллельной архитектурой. Дело в том, что АБСУ относятся к
системам жесткого реального времени, работающим в широком диапазоне температурных и других неблагоприятных внешних воздействий. В связи с этим к ним предъявляются повышенные требования по быстродействию и, в то же время, накладываются ограничения на применение перспективных высокопроизводительных микропроцессоров из-за бортовых условий эксплуатации. Одним из наиболее перспективных решений данной задачи является распараллеливание алгоритмов управления и их реализация в форме параллельно протекающих вычислительных процессов. В настоящее время достигнуты значительные успехи в области создания высокопроизводительных вычислительных систем с массовым параллелизмом, которые закреплены в целом ряде международных стандартов или стали общепризнанными из-за их широкого применения в различных технических приложениях.
Тем не менее, ряд важных аспектов построения бортовых информационных и управляющих вычислительных систем с параллельной архитектурой остается не достаточно исследованным. В первую очередь это относится к взаимной увязке процедур синтеза алгоритмов управления, планирования вычислительного процесса и выбора структурной организации аппаратной части комплекса, поскольку независимое осуществление этих этапов может привести к неэффективному, в целом, решению задачи проектирования. Кроме того, существующие методы планирования и диспетчеризации вычислительных процессов либо ориентируются на поиск любого допустимого варианта распараллеливания вычислений, что не гарантирует оптимального решения, либо нацеливаются на поиск наилучшего расписания, поиск которого может занимать слишком долгое время. Указанные обстоятельства определяют актуальность диссертационной работы.
Цель работы состоит в повышении эффективности автоматических бортовых систем управления за счет совмещения процедур синтеза алгоритмов управления, планирования вычислительных процессов, выбора оптимальной структурной организации аппаратной части и формирования на этой основе бортовых информационно-управляющих систем с параллельной архитектурой.
Задачи исследования. Для достижения поставленной цели в диссертационной работе на основе проведенных системных исследований принципов построения бортовых информационно-управляющих систем были сформулированы следующие задачи:
Провести исследование условий, при выполнении которых последовательность операций синтеза алгоритмов управления, планирования вычислительных процессов и выбора оптимальной структурной организации аппаратной части приводит к формированию архитектуры бортовых информационно-управляющих систем с заданным набором свойств.
Разработать метод совмещенного синтеза алгоритмов управления и топологии автоматических бортовых систем управления с параллельной архитектурой.
Разработать процедуру формирования алгоритмического облика бортовой информационно-вычислительной системы на основе глобального и локального распараллеливания задачи спутниковой навигации.
Разработать методика составления расписания, обеспечивающего оптимальную загрузку вычислительных модулей при реализации параллельных процессов, протекающих в бортовых информационно-управляющих системах, на основе адаптивного генетического алгоритма.
Разработать программное обеспечение для бортовых информационно-управляющих систем с параллельной архитектурой, с помощью которого оценить эффективность предложенных подходов к синтезу алгоритмов управления, планированию и диспетчеризации вычислительных процессов, а также к выбору оптимальной топологии систем данного класса.
Методы исследования. При решении поставленных задач использовались методы теории управления, системного анализа, композиционного проектирования, искусственного интеллекта, линейной алгебры, теории вероятностей, структурного программирования, компьютерного моделирования. Основные результаты, полученные в диссертационной работе: 1. Метод совмещенного синтеза алгоритмов управления и топологии автоматических бортовых систем управления с параллельной архитектурой.
Аналитическая модель вычислительных процессов, позволяющая с точностью до такта макрокоманд описывать состояние последних при реализации рекурсивных алгоритмов управления с контекстными переключениями.
Процедура формирования алгоритмического облика бортовой информационно-вычислительной системы на основе глобального и локального распараллеливания задачи спутниковой навигации.
Адаптивный генетический алгоритм, обеспечивающий поиск оптимального плана загрузки многопроцессорной бортовой информационно-управляющей системы посредством достижения компромисса между скоростью сходимости и качеством найденного решения.
Результаты исследования эффективности предложенных методов синтеза алгоритмов управления, планирования и диспетчеризации вычислительных процессов, а также выбора оптимальной топологии бортовых информационно-управляющих систем с параллельной архитектурой, выполненные с использованием разработанного программного комплекса.
Научная новизна.
Разработан метод совмещенного синтеза алгоритмов управления и топологии автоматических бортовых систем управления, отличающийся тем, что выбор структуры управляющей части осуществляется с учетом показателей эффективности вычислительного процесса, реализующего синтезируемые алгоритмы, в результате чего последовательная оптимизация локальных критериев обеспечивает формирование системы с заданным набором свойств.
Предложена аналитическая модель для описания вычислительных процессов, отличающаяся способом решения системы уравнений, описывающей состояние исследуемого вычислительного процесса, который позволяет исключить операцию обращения матриц высокой размерности и представить в аналитической форме результаты распределения множества фрагментов алгоритма управления между виртуальными вычислительными процессами.
Научная новизна процедуры формирования алгоритмического облика бортовой информационно-вычислительной системы состоит в механизме объединения ресурсов ВСС, ВСУП и других бортовых вычислительных систем для
реализации заданной совокупности совместно протекающих вычислительных процессов, полученных в результате глобального и локального распараллеливания задачи спутниковой навигации.
4. Научная новизна генетического алгоритма состоит в способе автоматической настройки параметров генетических операторов, которые меняются в зависимости от предыстории поиска наилучшего варианта с целью достижения компромисса между шириной и глубиной поиска оптимального решения.
Практическая значимость и реализация результатов работы.
Метод совмещенного синтеза алгоритмов управления и топологии автоматических бортовых систем управления позволяет повысить производительность комплекса бортового оборудования при одновременном обеспечении требуемого качества управления, что особенного важно для систем жесткого реального времени, к которым предъявляются требования безусловного, мгновенного, непрерывного, длительного выполнения всех запланированных функций.
Предложенная процедура формирования алгоритмического облика бортовой информационно-вычислительной системы позволяет сократить время на поиск оптимального созвездия, обеспечивающего максимальную точность позиционирования летательного аппарата, примерно в 3 раза при переходе к 3-процессорной системе и почти в 1.1 раз при переходе к 12-процессорной системе.
Адаптивный генетический алгоритм находит оптимальное решение в 2 - 2,5 раза быстрее по сравнению со стандартным, что обеспечивает существенное повышения эффективности бортовых информационно-управляющих систем.
Программный комплекс исследования и оптимизации архитектуры бортовых информационно-управляющих систем (свидетельства об официальной регистрации программ для ЭВМ № 2006611926 «Поиск оптимального созвездия навигационных спутников с использованием принципа глобального распараллеливания» и № 2006611927 «Оптимальное распределение загрузки
между узлами многопроцессорной вычислительной системы с использованием
адаптивного генетического алгоритма») обеспечивает совместимость с широким классом программно-аппаратных средств, что делает его доступным для применения на многих предприятиях авиаприборостроительного профиля.
Практическая значимость полученных результатов подтверждается актом внедрения в производственную деятельность корпорации «Аэрокосмическое оборудование».
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих научных конференциях: Международная молодежная научная конференция «XXX Гагаринские чтения» (г. Москва, 2004), Всероссийская научно-практическая конференция «Авиакосмические технологии и оборудование, Казань-2004» (г. Казань, 2004), 3-я международная выставка и конференция «Авиация и космонавтика-2004» (г. Москва, 2004), Международная молодежная научная конференция «XII Туполевские чтения» (г. Казань, 2004), VII Всероссийская научная конференция молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г, Таганрог, 2004), Международная конференция «CSIT'2005» (г. Уфа, 2005), IV Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (г. Томск, 2006), 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2006» (г. Москва, 2006).
Публикации. Основные результаты исследований по теме диссертации опубликованы в 16 работах, включая 2 статьи в научных изданиях из списка ВАК, 12 публикаций в центральных журналах, трудах и материалах конференций, 2 свидетельства об официальной регистрации программ для ЭВМ по теме диссертации.
Структура и объем работы. Диссертация состоит из перечня сокращений, введения, четырех глав, заключения и списка литературы. Основное содержание работы изложено на 158 страницах машинописного текста, включая 32 рисунка и 19 таблиц. Список литературы включает 142 наименования и занимает 13 страниц.
Анализ функционального и алгоритмического облика бортовых информационно-управляющих систем
Современные бортовые информационно-управляющие системы представляют собой совокупность подсистем управления летательным аппаратом, позволяющих реализовывахь все фазы полета от взлета до посадки, и подсистем обработки информации, поступающей от многочисленных источников для повышения достоверности оценки текущей полетной ситуации. Рассмотрим комплекс условий, обусловливающих необходимость проведения исследований, направленных на повышение эффективности подобных систем, и определяющих выбор средств и способов достижения поставленной цели. К числу таких условий относится совокупность функций, которые возлагаются на различные подсистемы БИУС. Эту совокупность можно условно разделить на два подмножества, первое из которых объединяет основные функции, непосредственно связанные с решением задач управления полетом, а второе - дополнительные информационно-вычислительные функции, направленные на поддержку решения этих задач. К числу таких дополнительных функций относится выполнение всех сложных навигационных расчетов, включая наиболее точную оценку местоположения самолета по информации, собранной со всех навигационных датчиков, и прогноз поведения других участников воздушного движения с целью предотвращения столкновений. Перечень основных и дополнительных функций БИУС содержится, соответственно в табл. 1.1 и 1.2.
Перечисленный набор функций определяет состав аппаратуры, необходимой для их исполнения. При этом аппаратура, выполняющая основные функции БИУС, образует инвариантное ядро комплекса бортового оборудования - автоматическую бортовую систему управления (АБСУ), состав которой остается практически неизменным для большинства типов используемых летательных аппаратов и регламентируется рядом международных стандартов, в частности, стандартом ARINC 700 /26/. Согласно этому стандарту к АБСУ относятся следующие системы /57/: вычислительная система самолетовождения (ВСС); вычислительная система управления полетом (ВСУП); вычислительная система управления тягой (ВСУТ); вычислительная система устойчивости и управляемости (ВСУУ); электродистанционная система управления (ЭДСУ).
В процессе функционирования аппаратура АБСУ взаимодействует со следующими устройствами и системами: инерциальной навигационной системой (ИНС); радиотехнической системой ближней навигации (РСБН); приемником глобальной навигационной спутниковой системы (ГНСС); комплексной системой предупреждения столкновений, контроля и регистрации (СПС), к которой относятся - система предупреждения о наступлении критических режимов полета, система сигнализации опасной скорости сближения с землей, система предупреждения столкновений самолетов в воздухе, система контроля, сбора и локализации отказов бортового электронного оборудования; радиотехнической системой посадки (РСП); метеонавигационной радиолокационной станцией (МНРЛС); комплексом датчиков первичной пилотажной информации, системы полного и статического давления, параметров работы силовой установки; системой воздушных сигналов (СВС); системой электронной индикации (СЭИ); системой связи и передачи данных (СС и ПД). В табл. 1.1 и 1.2 также указаны бортовые вычислительные системы, выполняющие соответствующие функции, и типовые этапы полета, на которых возникает необходимость решения соответствующих функциональных задач.
Для реализации перечисленных функций в АБСУ используется целый набор алгоритмов, состав которых зависит от назначения используемого лета телы-юго аппарата, от характера выполняемого полетного задания и отражает набор оптимальных программ управления применительно к типовым этапам полета.
При выполнении разворотов, требующих существенного изменения энергетической высоты, расчет оптимальных траекторий осуществляется с применением энергетического метода. Этот метод использует в качестве одной из основных переменных состояния энергетическую высоту E=h+v /2g. Задачи оптимизации пространственного маневра на основе энергетического метода рассмотрены, например, в работах /85/, /129/, Основная особенность полученных решений заключается в иереализуемости управлений, связанной с разрывностью скорости движения летательного аппарата и её производной на энергетически оптимальных траекториях,
Анализ функционального и алгоритмического облика БИУС позволяет сделать следующие выводы:
на бортовую информационно-управляющую систему возлагается целый комплекс ответственных задач, направленных на выполнение полетного задания и что требующих реализации сложных алгоритмов управления летательным аппаратом и его силовой установкой;
функциональные задачи и соответствующие алгоритмы управления распределены достаточно неравномерно как среди основных подсистем БИУС, так и применительно к различным этапам полета, что приводит к необходимости высокой пиковой производительности вычислительных устройств на одних фазах выполнения полетного задания и к недостаточной загрузке - на других.
Формализация процедуры формирования архитектуры автоматической бортовой системы управления
Как отмечалось в первой главе, синтез алгоритмов управления, планирование вычислительного процесса и выбор структурной организации аппаратной части необходимо осуществлять в рамках единой процедуры, обеспечивающей направленное формирование архитектуры автоматической бортовой системы управления (АБСУ) с заданным набором свойств. Рассмотрим условия, при выполнении которых последовательность операций выбора оптимальных алгоритмов управления и структурной организации аппаратной части позволяет получить оптимальный облик разрабатываемой многопроцессорной АБСУ. Обозначим через Х(1) и Х(2), соответственно, множество вариантов алгоритмов управления и топологических вариантов построения АБСУ. Для оценки эффективности рассмотренных вариантов введем две совокупности локальных критериев є(1) и (2Ї, первая из которых определяет качество синтезированных алгоритмов управления, а вторая - оценивает вычислительную эффективность работы многопроцессорной системы. Полное множество возможных вариантов построения бортовой АБСУ обозначим через X.
Важным критерием соблюдения условий совместимости является существование монотонных преобразований, переводящих области значений функций s в области значений є /37/, /74/. Сформулируем указанное требование применительно к рассматриваемой задаче формирования облика многопроцессорной АБСУ в виде следующего утверждения.
Утверждение 2.1. Если существует множество монотонных преобразований W,(a), i=l, 2,..., т, таких, что /-е преобразование переводит область значений г -й компоненты критерия є\ (X) в область значений критерия є,- (X) и ,-()(Х) = Wj{ /2J(X)} для всего множества X, то последовательная оптимизация локальных критериев s[\X), 1=1, 2, приводит к формированию оптимального варианта облика системы.
Доказательство: Рассмотрим случай максимизации критериев є/1-1 и є/2) при монотонно-возрастающем преобразовании W,(a), остальные случаи доказываются аналогично.
Пусть Х,,Х2 єХ - такие, что є}2 (Х,) 42 (Х2), z = l,2,...,m. По условию %\EJ2XXI)} %$2XX2)\, следовательно є (Х}) ef\x2). Данное неравенство выполняется для всех элементов соответствующих классов эквивалентности X] є X[l,l], Х2 є X[l,2]. В свою очередь, каждому классу эквивалентности соответствует определенное множество вариантов алгоритмического обеспечения МВС Х о X[l,lJ Х 1 2 о x[l,2]. Отсюда получаем
Таким образом, предпочтительный вариант в смысле критерия еи принадлежит, при выполнении заданных условий, к множеству предпочтительных вариантов в смысле критерия є(!), что соответствует результату, сформулированному в утверждении.
Доказанное утверждение служит методической основой для разработки процедуры совмещенного синтеза алгоритмов управления, планирования вычислительного процесса и выбора структурной организации аппаратной части, поскольку условия существования монотонных преобразований диктуют способ диспетчеризации вычислительного процесса, обеспечивающий совместимость локальных целей формирования алгоритмического обеспечения и топологии многопроцессорной АБСУ.
Чтобы получить аналитическое выражение для множества монотонных преобразований W,-(ct), i=l,2,...,m, необходимо выразить характеристики возможных вариантов алгоритмов управления через соответствующие характеристики вариантов структурной организации аппаратной части. Для этого предлагается математическая модель, позволяющая описывать управляющую часть АБСУ с учетом специальных структурных матриц, определяющих состав процессорных блоков и модулей памяти, а также структуру связей между ними. На базе этой модели реализуется процедура совмещенного синтеза алгоритмов управления и вариантов структурной организации бортовой многопроцессорной АБСУ.
Рассмотрим, вначале, основные свойства вычислительных алгоритмов, существенные с точки зрения разработки алгоритмического обеспечения АБСУ.
Под вычислительным алгоритмом в общем случае понимают /17/, /78/, /89/ точное предписание, которое задает ход некоторого конструктивного процесса, начинающегося с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленного на получение полностью определяемого этим исходным данным результата. Любой алгоритм может быть представлен в виде совокупности более простых составных частей - фрагментов алгоритма. Исходные данные и возможные результаты выполнения отдельных фрагментов алгоритма образуют совокупность возможных промежуточных результатов. В свою очередь, каждый фрагмент алгоритма представляет собой определенную последовательность операций. Число таких операций зависит от уровня детализации алгоритма и характеризует собой его сложность. Обычно различают временную сложность алгоритма, связанную с количеством тактов выполнения элементарных операций, и емкостную сложность, связанную с объемом аппаратуры, которая обеспечивает выполнение заданной совокупности элементарных операций (например, объем памяти вычислительной системы).
Для каждого алгоритма можно выделить семь характеризующих его параметров: 1) совокупность возможных исходных данных; 2) совокупность возможных результатов; 3) совокупность возможных промежуточных результатов; 4) правило начала; 5) правило непосредственной переработки; 6) правило окончания; 7) правило извлечения результата.
Возможные уточнения понятия алгоритма связаны, как правило, с конкретизацией перечисленных параметров применительно к соответствующей области знания. Что касается рассматриваемых в данной главе алгоритмов управления, то для них указанные параметры получают простую интерпретацию. Совокупность исходных данных представляет собой множество измеренных с помощью датчиков и чувствительных элементов переменных величин, определяющих состояние процесса управления; совокупность возможных результатов - это множество допустимых управляющих воздействий, изменяющих характер рабочего процесса в объекте управления; текущие значения внутренних управляющих переменных образуют совокупность возможных промежуточных результатов; правило начала задается системой инициализации; правило непосредственной переработки реализуется в выбранном законе управления; правило окончания задает требуемую точность достигнутого результата управления; наконец.
Разработка алгоритма глобального распараллеливания задачи спутниковой навигации
Возможности предлагаемого подхода к распараллеливанию вычислений, которые необходимо производить на борту летательного аппарата в ходе навигационных расчетов, мы продемонстрируем на примере системы глобальной спутниковой навигации /47/, /55/, /96/. Этот выбор связан с теми существенными преимуществами, которые спутниковые средства навигации предоставляют своим пользователям: размер рабочей зоны по поверхности земного шара не ограничен; высокоточное трехмерное определение координат местоположения и вектора скорости в реальном масштабе времени; неограниченная пропускная способность системы и высокая помехозащищенность; относительно невысокая стоимость навигационной бортовой аппаратуры потребителей; автоматизированное самолетовождение по запрограммированным оптимальным траекториям с соблюдением норм продольного, бокового и вертикального эшелонирования на всех этапах полета, включая посадку по нормам категории Ш; повышение безопасности полетов при росте интенсивности воздушного движения; снижение эксплуатационных затрат на техническое обслуживание за счет максимальной экономии топлива.
Реализация этих преимуществ в значительной степени зависит от достигнутого уровня качества навигационных измерений в СНС. Точность, достоверность и надежность навигационных измерений определяются тремя основными обстоятельствами; движением навигационных спутников (НИСЗ), большой высотой орбит спутников и особенностями использования пассивного способа определения навигационных параметров (НП).
Первое обстоятельство требует, чтобы в момент измерения были точно известны координаты НИСЗ и их производные. В большинстве СНС эти параметры спутника определяются процессором бортовой аппаратуры потребителя по эфемеридным данным, включенным в служебную информацию, которая передается с НИСЗ вместе с навигационным сигналом. Второе обстоятельство связано с наличием дополнительной задержки сигнала в атмосфере, которая может быть учтена по данным служебной информации с использованием моделей атмосферы в процессоре бортовой аппаратуры, либо должна быть исключена, например, с помощью двухчастотного метода, предусматривающего измерение НП на двух частотах. Пассивный способ определения НП, принятый в большинстве СНС, приводит к необходимости синхронизации шкал времени всех НИСЗ (единое системное время). Синхронизация обеспечивается применением на НИСЗ водородного стандарта частоты с долговременной стабильностью не хуже 3-Ю""14 и передачей поправок времени бортовых эталонов в служебном сообщении. Пассивный характер работы АП влияет также на выбор метода расчета НП. Координаты летательного аппарата определяются по рассчитанным псевдодальностям до выбранных НИСЗ. В свою очередь псевдодальность (беззапросная дальность) рассчитывается по измеренной временной задержке Т-, прохождения радиосигнала от г -го НИСЗ до летательного аппарата: Dt=cTit (3.1) где с - скорость распространения радиосигнала.
Рассчитанная подобным образом псевдодальность связана с истинной дальностью D от летательного аппарата до НИСЗ следующим соотношением: где Т - сдвиг бортовой шкалы времени летательного аппарата относительно единого системного времени СНС, SDi - погрешность определения г-той псев-додальности.
Для расчета пространственных координат летательного аппарата достаточно системы из четырех уравнений, полученных на основе (3.2): Ач - № - Хп + & - Уп У + & - Zn Y+cT + SDn Di2 = c Xi2f+(Y Yi2f+(Zc-Zi2f + cT + SDi2; Аз = V W )2 + fc - b f + (Zc - Ze У +cT + 5Di3; DiA = (Xc-XiAf +(7c-r/4)2 +(ZC-Zi4f +cT + SDi4.
Специфика решения навигационной задачи связана с перемещением НИСЗ относительно потребителя, при котором непрерывно изменяется взаимное положение потребителя и спутников, что приводит к изменению геометрического фактора и необходимости перехода на другую группу НИСЗ с лучшим геометрическим расположением.
Рассмотрим основные факторы, влияющие на точность навигационных измерений. Их можно объединить в несколько характерных групп: геометрические факторы; факторы распространения радиоволн в атмосфере (приводят к появлению тропосферных, ионосферных погрешностей и погрешности из-за многолучевого распространения сигнала); факторы, обусловленные качеством навигационных сигналов; факторы, обусловленные несовершенством аппаратуры потребителя. Проведенный анализ факторов, влияющих на точность навигационных измерений, позволяет сделать вывод о том, что максимальная величина тропосферных и ионосферных погрешностей наблюдается у спутников, которые находятся в зените, а максимальная погрешность из-за многолучевости - у приго-ризонтных спутников. Следовательно, созвездие с минимальной погрешностью от геометрических факторов характеризуется максимальным уровнем погрешности от распространения радиоволн в атмосфере. По мере удаления спутников от горизонта и зенита первый вид погрешностей будет расти, а второй — убывать. Очевидно, что существует такая конфигурация созвездия, при которой суммарная погрешность окажется минимальной.
Однако поиск такого оптимального созвездия требует чрезвычайно больших временных затрат, поскольку существует несколько десятков тысяч возможных комбинаций. Число возможных комбинаций существенно зависит от состава используемой орбитальной группировки. Если ориентироваться на полностью развернутую группировку ГЛОНАСС, то число возможных комби 4 12! наций равно Ci2 = = 495. При совместном использовании систем ГЛО НАСС и Navstar число возможных комбинаций достигает СІЛ =-=- = 10626. 24 20!-4! В перспективе необходимо также учитывать развертывание Европейской СНС Galileo. В то же время максимальная продолжительность первого сеанса навигации в многоканальной НАЛ определяется длительностью выполнения следующих операций: поиск и вхождение в синхронизм слежения за псевдослучайной последовательностью - 5 с, поиск и вхождение в синхронизм слежения за несущим колебанием - 2 с, выделение меандра - 1 с, ожидание метки времени - 2 с, выделение цифровой информации - 30 с, итого 40 с. Если в сеансе навигации проводится обновление альманаха (2,5 мин), то продолжительность сеанса составит 2 мин 40 с.
Программная реализация алгоритмов глобального и локального распараллеливания задачи спутниковой навигации
Описанный в разделе 3.1 параллельный алгоритм реализован в виде параллельной программы, представленной на языке высокого уровня C++ с использованием библиотеки MPI /122/, /127/. MPI обеспечивает взаимодействие между параллельными процессами с помощью передачи сообщений, а также переносимость данной программы между различными параллельными вычислительными комплексами.
Рассмотрим основные принципы разработки параллельного ПО с использованием библиотеки MPI.
Процесс - это исполнение программы на одном процессоре, безотносительно к тому, содержит эта программа внутри параллельные ветви или операции ввода-вывода или просто последовательный программный код.
МРІ-программа - это множество параллельных взаимодействующих процессов, число которых обычно равно числу задействованных процессоров. Все процессы порождаются один раз, образуя параллельную часть программы. Каждый процесс работает в своем адресном пространстве, никаких общих переменных или данных в МРІ нет. Основным способом взаимодействия между процессами является посылка сообщений.
Группа процессов представляет собой совокупность процессов, каждый из которых имеет внутри группы уникальный номер (целое неотрицательное число), используемый для взаимодействия с другими процессами группы посредством коммуникатора группы. Состав образуемых групп произволен.
Коммуникатор - это среда, реализующая обмен данными между процессами и их синхронизацию. Коммуникатор определяет контекст передачи сообщения. Каждый коммуникатор имеет собственное коммуникационное пространство. При запуске программы поиска оптимального созвездия считается, что все порожденные процессы работают в рамках всеобъемлющего коммуникатора, имеющего предопределенное имя MPI_COMM_WORLD.
Сообщение — это набор данных некоторого типа. Каждое сообщение имеет несколько атрибутов: номер процесса-отправителя, номер процесса-получателя и идентификатор сообщения. Идентификатор сообщения - это атрибут сообщения, являющийся целым неотрицательным числом. По идентификатору процесс, принимающий сообщение, например, может различить два сообщения, пришедшие к нему от одного и того же процесса.
Взаимодействие между процессами в рамках коммуникатора реализуется с помощью функции широковещательной рассылки MPIJBcast и функции сборки данных от нескольких процессов MPI__Gatherv. Для определения времени выполнения параллельной программы используется функция MPIJWtime. Программа /10/ состоит из следующих модулей:
Модуль формирования исходных данных (МФИД). Выполняет расчет псевдодальности от летательного аппарата до НИСЗ по временной задержке, рассчитанной бортовой аппаратурой. Для погрешности измерения псевдодальности принята гипотеза о нормальном законе распределения с нулевым математическим ожиданием и стандартным отклонением d, которое зависит от конкретного спутника. Для моделирования нормально распределенной псевдослучайной последовательности используется алгоритм Марсальи-Брея, Исходные данные рассылаются другим процессам с помощью библиотечной функции MPI Bcast,
Модуль генерации выборки по номеру (МГВН). Вычисляет выборку четырех из исходных N спутников по номеру созвездия і, в которой номера спутников упорядочены по возрастанию;
Модуль оценки погрешности конфигурации (МОПК). Включает в себя подмодуль решения навигационной задачи по описанному ранее алгоритму с контролем степени обусловленности системы уравнений относительно искомых координат. В качестве показателя обусловленности используется норма матрицы коэффициентов системы: если норма оказывается меньше установленной минимальной величины, то это означает, что решить навигационную задачу по данной конфигурации невозможно, и вычисления прекращаются. В противном случае решение можно получить, и итерационный процесс доводится до конца. Процедура решения навигационной задачи повторяется 1000 раз, а результаты запоминаются в массивах Хс, Ус, Zc, Т. На основании этих данных находятся статистические оценки, позволяющие рассчитать показатель S по формуле (3.11).
