Содержание к диссертации
Введение
1. Методы исследования процессов управления воздушным движением 10
1.1. Исходные положения и задачи исследования 10
1.2. Теоретическая база исследования. Критический анализ литературы по теме 17
1.2.1. Цель анализа теоретической базы 17
1.2.2. Теория массового обслуживания 17
1.2.3. Статистическое моделирование 20
1.2.4. Математическое программирование 23
1.2.4.1. Принципы математического программирования 23
1.2.4.2. Линейное программирование 24
1.2.4.3. Динамическое программирование 28
1.2.4.4. Стохастическое программирование 31
1.2.5. Приложения теории графов 34
1.3. Требования к методу оперативного регулирования потоков ВС 38
2. Информационная основа метода оперативного регулирования потоков 41
2.1. Адаптационная модель использования воздушного пространства 41
2.1.1. Словесная постановка 41
2.1.2. Формализация задачи 45
2.1.3. Фильтр загрузки 47
2.1.4. Пример оценки загрузки элементов ВП 50
2.2 Связи и ограничения модели использования воздушного пространства 53
2.2.1. Пропускная способность трасс и секторов 53
2.2.2. Обновление порогов загрузки секторов 55
2.3. Экстремальные свойства адаптационной модели 60
2.3.1. Математическая постановка задачи 60
2.3.2. Минимальная функция поиска на информационном образе 62
2.3.3. Минимальное отношение поиска запрошенного элемента 67
3. Метод оперативного регулирования потоков воздушных судов 71
3.1. Состав задач и последовательность их исполнения 71
3.1.1. Технологическая схема метода 71
3.1.2. Алгоритмическое описание метода 75
3.1.3. Фильтр конфликтов 79
3.1.4. Выявление конфликтов на основе информационных образов 81
3.2. Выработка рекомендаций по регулированию потоков ВС 88
3.2.1. Присоединение рейса к модели ИВП 88
3.2.2. Алгоритм поиска кратчайшего пути 96
4. Оценка компьютерных ресурсов для реализации метода оперативного регулирования 103
4.1. Модель вычислительной сети центра управления полетами 103
4.1.1. Постановка задачи 103
4.1.2. Формализация задачи 105
4.2. Учет связности заявок 111
4.2.1. Постановка задачи 111
4.2.2. Модель без учета корреляции заявок 113
4.2.3. Модель с учетом корреляции 115
4.3. Оценка связности вычислительных задач в центре управления 120
4.3.1. Постановка задачи 120
4.3.2. Анализ достижимости вершин графа сложной программы 124 Заключение 130 Литература
- Теоретическая база исследования. Критический анализ литературы по теме
- Пример оценки загрузки элементов ВП
- Алгоритмическое описание метода
- Модель без учета корреляции заявок
Введение к работе
Актуальность исследования. Проблемы оперативного регулирования потоков воздушного движения выступают на первый план в ходе текущего планирования и непосредственного управления полетами. Во-первых, именно здесь всплывают недочеты долговременного (составление сезонного расписания) и предварительного (уточнение графика движения на ближайшие сутки) этапов. Во-вторых, непредвиденные изменения условий выполнения рейсов, вызванные атмосферными явлениями, отказами технических средств, организационными и другими причинами приводят к необходимости перераспределения потоков самолетов, уже находящихся в воздухе.
Регламентирующие документы гражданской авиации предписывают диспетчерскому составу в критических случаях, таких как отказы средств радиолокационного наблюдения, переходить на процедурные методы контроля и, руководствуясь соображениями безопасности, направлять на ближайшие аэродромы посадки все воздушные суда, совершающие полеты в нештатной обстановке. Экономически это невыгодно всем - авиапредприятиям и пользователям - и оправдано целью сохранения жизни пассажиров и экипажей.
Такие ситуации типичны, и во многих центрах управления воздушным движением (УВД), на основе опыта воздушных перевозок, найдены обходные маршруты, следование по которым позволяет поддержать необходимый уровень безопасности при минимально возможных экономических издержках. Например, оптимально спланированные рейсы, пересекающие Иркутскую зону со стороны Омска и Новосибирска в направлении Нижнеудинска, вследствие аномальных явлений переводят на северные трассы, через Кол-пашево, Енисейск, Жигалово. В большинстве других регионов страны также эмпирически найдены и включены в должностные инструкции авиадиспетчеров правила переноса рейсов на «запасные пути» при характерных для местности атмосферных явлениях, но возможности таких действий ограничены конкретными типами обстановки и состояния техники. Существующие приемы перераспределения потоков по-прежнему принадлежат скорее искусству, чем науке планирования. Самое главное, они не учитывают последствий принимаемых мер - перевода рейсов на запасные маршруты, на невыгодные эшелоны и другие - для последующих центров УВД, т.е. на изменение их загрузки и сложности диспетчерского обслуживания полетов. Регулирование потоков выполняемых рейсов происходит в напряженной стрессовой обстановке и требует программной поддержки. В ситуации, при которой в считанные минуты нужно фактически заново создать сводный план на территории района или зоны, обоснованные предложения алгоритмов организации потоков оказали бы серьезную поддержку диспетчерскому персоналу.
Возникает актуальная научная задача создания методов оперативного регулирования потоков воздушных судов (ВС) при изменении условий выполнения полетов с учетом влияния результатов на взаимодействующие диспетчерские центры. Эти методы должны обеспечивать требования к безопасности полетов и к нормам загрузки диспетчерского персонала - при минимуме экономического ущерба и отклонений от регулярности полетов вследствие производимого вмешательства.
Цели и задачи исследования. Основная цель работы - создать, исследовать и обосновать методы оперативного регулирования потоков ВС для поддержки диспетчеров при изменении условий выполнения полетов в автоматизированной системе (АС) УВД, позволяющие обеспечить безопасность полетов при ограничениях на их экономичность и регулярность с учетом норм загрузки взаимодействующих диспетчерских центров.
Для достижения главной цели необходимо:
• разработать метод оценки загрузки воздушного пространства (ВП), работающий в реальном масштабе времени;
• разработать метод прокладки бесконфликтных кратчайших обходных маршрутов, работающий в реальном масштабе времени;
• исследовать разработанные методы по критерию минимизации компьютерных ресурсов и времени реакции системы на запросы диспетчеров;
• разработать технологическую схему оперативного регулирования потоков с использованием предложенных методов.
Объект и предмет исследования. Объектом исследования является АС УВД высокого уровня автоматизации, в программном обеспечении (ПО) которой предусмотрен комплекс программ (КП) обработки плановой информации этапа УВД, а в базе данных (БД) содержатся обновляемые в реальном масштабе времени сведения о текущем состоянии элементов структуры ВП, атмосферы и технических средств системы.
Предметом исследования является компьютерная поддержка деятельности диспетчерского персонала (руководителя полетов) при изменении условий выполнения полетов; существующие и новые методы выработки рекомендаций по оперативному регулированию потоков ВС, наследующие достоинства известных методов и свободные от их недостатков.
Основные положения, выносимые на защиту:
• адаптационная модель ИВП как инструмент оперативного регулирования потоков ВС при изменении условий выполнения полетов;
• метод формирования рельефа загрузки ВП с учетом требований по безопасности и ограничений по экономичности и регулярности движения;
• метод оперативного регулирования потоков ВС;
• метод оценки компьютерных ресурсов, необходимых для использования модели ИВП и оперативного регулирования на ее основе потоков ВС;
• методика расчета параметра связности решаемых задач, не измеряемого явно, для определения производительности вычислительной сети.
Методологическая и теоретическая основа исследования. Методологическую основу исследования составляют регламентирующие документы гражданской авиации (ГА), определяющие правила производства полетов, направление развития и модернизации существующей Единой системы (ЕС) организации воздушного движения (ОрВД) России, принципы взаимодействия служб УВД страны [1-5], а также рекомендации международной организации ГА (ИКАО) и органов Евроконтроля [6-Ю]. Теоретическую основу со ставляют труды специалистов научных и учебных центров ГА России (ГосНИИ «Аэронавигация», ГосНИИ ГА, МГТУ ГА, МАИ, и других) [11-16] и ведущих зарубежных ученых в области ОрВД [17-19].
Методы исследования. При решении поставленных задач использованы методы общей теории систем, теории АСУ и систем ОрВД, системного анализа, математической статистики, исследования операций, теории массового обслуживания, теории графов, экспертных оценок, имитационного моделирования.
Научная новизна работы состоит в том, что в ней впервые:
• дано решение задачи автоматизированного регулирования потоков ВС, отличающееся тем, что рекомендации диспетчерскому персоналу вырабатываются в реальном масштабе времени;
• использован подход к планированию потоков ВС, отличающийся тем, что производится выбор бесконфликтного рационального (субоптимального) варианта, принадлежащего области допустимых решений, без поиска глобального оптимума целевой функции;
• предложена новая для задач УВД форма представления полетных данных как композиции гистограмм распределения загрузки элементов ВП (информационный образ), которая отличается тем, что обладает свойствами минимальных потребностей в компьютерной производительности и памяти;
• построена адаптационная модель ИВП как инструмент оперативного регулирования потоков ВС, представляющая собой композицию гистограмм распределения почасовой загрузки ВП, развивающая представления о компьютерной поддержке принятия диспетчерских решений;
• созданы новые методы оценки и регулирования загрузки диспетчеров с учетом безопасных интервалов следования и расстояний опасного сближения ВС, разработаны алгоритмы работы с информационным образом (ИО) для автоматизированного регулирования потоков, отличающиеся от известных аналогов линейным (а не экспоненциальным) ростом затрат времени счета от количества планируемых рейсов;
• построена и исследована математическая модель процесса работы с ИО, получены формулы для оценки компьютерных ресурсов, необходимых для его реализации, в зависимости от значений параметров АС УВД;
• выделены области конкретных соотношений параметров АС УВД, в которых, при ограничениях на структуру потоков ВС и дисциплину обслуживания заявок, становится предпочтительным применение распределенной либо централизованной базы данных;
• формализован и исследован параметр связности (корреляции между задачами регулирования потоков по отношениям предшествования и по общим данным), не измеряемый явно, и разработана методика его вычисления.
Практическая значимость работы состоит в том, что ее результаты позволяют:
• поднять показатели эффективности ОрВД России и привлечь дополнительный поток ВС иностранных авиакомпаний через ВП страны;
• как следствие, обеспечить финансирование современных средств радионавигации, наблюдения и связи;
• научно обосновать высокие нормативные требования к перспективным АС УВД.
Предложенные методы регулирования могут использоваться не только на этапе УВД, но и на предварительных стадиях планирования потоков ВС. Они применимы также для решения задач контроля и поддержания целостности информационного обеспечения систем ОрВД.
Апробация результатов исследования. Основные результаты работы докладывались и обсуждались на международных научно-технических конференциях в МГТУ ГА (2003, 2006 г.г.), в МАИ (2004, 2005, 2006 г.г.), в Егорьевском авиационно-техническом колледже (Чкаловские чтения, 2004), в Тамбовском государственном университете (2005), в Приволжском Доме знаний (Пенза, 2005), в Московском институте электронной техники (2005). По теме диссертации опубликована 21 научная работа, среди которых: статья в журнале «Известия Академии наук. Теория и системы управления» (2005) и
ее английская версия в «Journal of Computer and Systems Sciences International»; 10 статей в «Научном вестнике МГТУ ГА» (2003 - 2006), включенном Президиумом ВАК в перечень научных изданий, в которых разрешено опубликование материалов докторских диссертаций, а также тезисы докладов международных конференций (2003 - 2006).
Среди опубликованных работ 10 написаны автором единолично, остальные - в соавторстве с научным руководителем и его учениками. В совместных публикациях руководителю принадлежат постановка задачи и общее редактирование текста, автору - формализация, анализ и программная реализация моделей, алгоритмов и методов, включенных в диссертацию.
Структура диссертационной работы. Работа состоит из введения, четырех глав, заключения и списка использованной литературы. Общий объем диссертации составляет 147 страниц и включает 34 рисунка и 14 таблиц. Список литературы содержит 84 наименования.
Теоретическая база исследования. Критический анализ литературы по теме
Особенность ОрВД состоит в том, что оптимальный по любому критерию план ИВП начинает устаревать и терять свою актуальность уже с момента своего составления. Это происходит как вследствие изменения объективной ситуации, так и воздействия человеческого фактора. Опасные метеорологические явления заставляют отказываться от экономичных маршрутов, переносятся вылеты чартерных рейсов, в связи с погодными условиями сдвигается расписание регулярных полетов; недостаточно предсказуем технический и человеческий факторы, а кратковременные режимные ограничения часто вводятся уже в процессе реализации плана. Однако, несмотря на перечисленные причины, попытки создавать оптимальные планы ИВП имеют многолетнюю историю [14,19].
Математическое обоснование эмпирических приемов и процедур достижения равномерной загрузки традиционно опиралось [14 - 19] на методы теории очередей (массового обслуживания), линейного и нелинейного программирования (например, потоки в сетях), статистическое моделирование. За годы работы специалисты, благодаря активным действиям, теоретическим и эмпирическим, накопили фундаментальные знания, факты, результаты экспериментов, которые позволяют последователям располагать компьютерными средствами определения загрузки элементов ВП в функции времени суток. Их труд, безусловно, оставил позитивный след на развитии ОрВД, однако вопросы перевода части рейсов с интенсивно используемых направлений на обходные маршруты, переносов времени вылета, смежные проблемы -продолжают активно стимулировать исследования в данной области.
Проанализируем инструменты, использованные и созданные предшественниками, с целью найти и унаследовать в новых разрабатываемых методах их достоинства и, по возможности, избежать их недостатков.
Теория массового обслуживания. Теория массового обслуживания (ТМО) - отрасль прикладной математики, использующая методы тео рий вероятностных процессов [20]. Стимулом к ее развитию послужили попытки предсказывать случайно изменяющиеся потребности по результатам наблюдений и на этой основе организовывать обслуживание, характеризующееся приемлемым временем ожидания. Дисциплина позволяет раскрывать природу очередей, что обеспечивает возможность лучшего управления процессом. В задаче оперативного регулирования потоков есть все формальные признаки системы массового обслуживания (СМО) - входной поток заявок (ВС), обслуживающий аппарат с ограниченной пропускной способностью (элемент ВП), время ожидания обслуживания, возможность отказа.
В [21] анализируется применение ТМО для организации управления движением ВС в аэропорту с максимальной слаженностью, с учетом большого числа действующих факторов и сложности взаимных связей элементов системы. Результаты помогают прогнозировать длительность ожидания, число ожидающих пассажиров (в любой момент времени), длительность периода занятости полосы и т. д. Такого рода прогнозы и рекомендации к действиям помогают предвидеть ситуацию, принимать соответствующие меры и ослаблять возможную нагрузку.
Однако, при всех положительных моментах, в приложении к организации ИВП ТМО характеризуют существенные недостатки. Рассмотрим пример. Аэропорт имеет несколько взлетно-посадочных полос (ВПП) - параллельных каналов. Эти полосы ведут к рулежным дорожкам, оканчивающимся на аэровокзале (последовательные каналы). После того как ВС, прибывшее в соответствии с определенным распределением входящего потока (расписанием), приземляется, его присоединяют к очереди ВС, ожидающих обслуживания (продвижения по дорожке к месту выгрузки). Очередь существует как на земле (взлет), так и в воздухе (посадка). Обе эти очереди имеют свои распределения входящего потока. Приземляющиеся самолеты могут прибывать группами, при этом члены каждой группы должны кружить над аэропортом и приземляться в установленном порядке. Длительность операции обслуживания (время приземления или взлета) около минуты. В обоих случаях известно распределение времени обслуживания. Если для различных типов ВС отведены разные ВПП, то распределение времени обслуживания может изменяться от одной полосы к другой. При выборе ВС для посадки руководствуются соответствующим количественным показателем. Например, если желательно минимизировать общее время ожидания пассажиров, то вначале нужно производить посадку ВС с большим количеством людей - тогда обслуженных пассажиров накопится больше, чем ожидающих обслуживания.
Другой аспект обслуживания с приоритетом проявляется в ситуациях, когда снижающемуся ВС посадка разрешается раньше, чем взлет ожидающему. Приоритетность распространяется также на случай аварийной обстановки, когда вследствие крайней необходимости разрешается посадить первым ВС, прибывший позже других. Нередко приоритетность посадки присваивается ВС из-за ограниченного запаса топлива.
Иногда вследствие определенного характера расположения ВС в зоне ожидания, прибывающий самолет присоединяется к очереди эшелонированных самолетов, ожидающих посадки, а затем выбор ВС из очереди на посадку производится случайным образом. Например, если ВС находится ближе других к точке, в которой он, согласно установленной схеме, может покинуть зону ожидания, то ему будет дана команда на посадку. В промежутке времени между получением приоритетности посадки и командой «посадку разрешаю» ВС покидает зону ожидания и направляется к аэродрому.
Методы ТМО позволяют за счет варьирования параметров СМО гарантировать поддержание требуемого уровня важнейших показателей качества работы системы, от которых зависит рентабельность авиапредприятия, таких как среднее время ожидания и дисперсия его величины, вероятность отказа в обслуживании рейса, средняя длина очереди ожидания. Эти положительные моменты использованы в настоящей работе. С помощью аппарата данной дисциплины построены и исследованы модели формирования ИО, оценены потребности в компьютерных ресурсах, гарантирующие заданные показатели быстродействия и вероятности отказа в обслуживании ВС.
Пример оценки загрузки элементов ВП
Пропускная способность трасс и секторов. Эти характеристики имитируются сочетанием хранимых в БД постоянных данных с обновляемыми сведениями о текущем состоянии среды. Это структура ВП системы в совокупности с техническими показателями работы средств навигации и связи, метеорологической обстановкой и т.п., а также характеристики управляемого процесса, т.е. сводные планы ИВП - суточный и текущий, измеренные параметры движения ВС, оценки целостности подсистем. К неизменяемым параметрам относятся, кроме того, константы технологии ОрВД, включая форматы телеграфных сообщений и банк кодов ВРЛ ИКАО, а также точки стояния радаров, летно-технические характеристики ВС и т.п. Для использования алгоритмами оперативного регулирования потоков всей доступной информации таблицы БД малопригодны по двум причинам. Во-первых, запросы к ним не могут гарантировать работу ПО в реальном масштабе времени, вследствие чего постоянные характеристики размещаются в оперативной памяти (ОП). Во-вторых, метод использует не табличное представление данных, а структурированные частотные модели полетной информации, сформированные в ИО из гистограмм распределения почасовой загрузки элементов ВП.
Формат информационного образа задается при генерации адаптационной модели ИВП следующим образом. В ОП создаются основания гистограмм распределения всех учитываемых в процессе ОрВД элементов ВП. Для централизованной службы планов полетов - это общеизвестная иерархия уровней, на вершине которой располагается ВП страны, в следующем ярусе -ЗЦ, в том числе, вспомогательные (ВЗЦ), далее следуют РЦ и вспомогательные (ВРЦ), ниже - секторы УВД, аэродромы, ПОД, другие особые точки ВП (например, пересечения трасс). В обсуждаемой иерархии на этапе генерации еще не установлены связи, и в терминах теории графов мы пока имеем несвязный граф (Санкт-Петербург с разведенными мостами), вершины которого образованы осями гистограмм почасовой загрузки всех элементов ВП. Связи, или ребра графа, задаются матрицей смежности М, введенной выше в п. 2.1.3 (рис. 2.4). На этапе генерации модели в качестве значений элементов g - пропускной способности - используются данные, известные из сборника аэронавигационной информации [4]. По мере обновления сведений о фактическом состоянии участков трасс, связывающих /-й и у -й ПОД, величины g корректируются средствами ПО в моменты включения алгоритма оперативного регулирования. Однако при запуске системы, в момент заполнения действующими справочными (нормативными) данными матрицы М, в распоряжении процедур перераспределения потоков ВС еще нет структурированного математического отображения «предмета производства» - нет сформированного рельефа загрузки ВП, который требуется изменять по условиям задачи. На этом этапе мы имеем связный граф, вершины которого соответствуют элементам структуры ВП, а ребра - участкам воздушных трасс, соединяющих эти элементы. Пока в нашем распоряжении только абстрактная полетная карта, на которую необходимо нанести рельеф загрузки системы.
Такой рельеф создается на этапе суточного планирования. В установленный момент, например - в ноль часов текущих суток, включается алгоритм активизации расписания полетов (международных, внутренних, местных) на следующие сутки. Просмотр организуется по критерию дня недели действия стандартных (повторяющихся) планов - это должен быть день недели следующих суток. Все планы рейсов, удовлетворяющие этому условию, включаются в суточный план ИВП. Считанная из БД информация фиксируется и в рельефе загрузки - в столбцы гистограмм, соответствующих затрагиваемым рейсом аэродромам, ПОД, секторам, РЦ, ЗЦ добавляется ссылка на обрабатываемый план. По завершении активизации в план ИВП вводятся заявки на полеты вне расписания, и этот процесс продолжается до окончания суток, предшествующих дате выполнения формируемого суточного плана. Теперь у нас есть компьютерная модель воздушного движения, с помощью которой можно управлять его реализацией. Уже на этом этапе можно исследовать планируемые показатели процесса и найти узкие места плана ИВП. Основным фактором, влияющим на качество решений, принимаемых диспетчером, является его загрузка, определяемая [43, 44] целым рядом воздействующих параметров. Среди них выделяют одиннадцать постоянных (средневзвешенное время нахождения ВС в секторе, сложность геометрии трасс, уровень автоматизации и т.п.) и три временных (отключение радаров, опасные явления погоды, кратковременные режимные ограничения). Загрузка вычисляется для каждого конкретного сектора УВД в форме уникального норматива, размерность которого - количество ВС, находящихся на управлении в течение часа. В процессе формирования рельефа загрузки ВП (см. рис. 2.5 и 2.6 п. 2.1.4 данной главы) на этапе суточного планирования алгоритмом учитываются нормативы, определяемые постоянно действующими факторами. При включении процедур оперативного регулирования потоков ВС порог загрузки пересчитывается для каждого сектора на основе всей информации о сложности УВД в нем согласно методике, изложенной в [43].
Таким образом, к моменту изменения условий выполнения полетов в АС УВД, приводящего к необходимости оперативного перепланирования потоков воздушного движения, в системе создана необходимая информационная база для поддержки персонала в этой деятельности. Создана адаптационная модель ИВП, обновляемая в реальном масштабе времени, отслеживающая загрузку ВП и стоимость полета по обходным направлениям. Ее нужно наделить основным свойством систем регулирования - обратной связью. Как только в ПО поступают данные об изменении пропускной способности участков трасс и секторов УВД, должно обеспечиваться автоматическое выявление рейсов, планы которых затрагивают «неблагополучные» элементы ВП, должны рассчитываться обходные маршруты, и руководителю полетов должны отображаться рекомендации по оперативному регулированию потоков. Рассмотрим возможности установления такой обратной связи.
Алгоритмическое описание метода
Поясним основные процедуры. Схема алгоритма работы фильтра маршрутов представлена на рис. 3.1. Блок «Прием заявок на ИВП» сортирует плановые сообщения по принципу принадлежности затрагиваемым элементам ВП. Далее заявка попадает в блок форматно-логического контроля (ФЛК). Каждое поле заявки имеет определенный номер и правила заполнения, общие для всех типов сообщений [2]. Блок представляет собой синтаксический анализатор [53], который проверяет каждое поле на его наличие и правильность заполнения. Любое отклонение от правил (например, недопустимые символы) ведет к выдаче диагностического сообщения (подсказки) диспетчеру и возврату заявки в блок ручного ввода для последующего редактирования.
В заявке маршрут полета указывается как перечень имен ПОД и трасс [58]. Преобразование маршрута в последовательность затрагиваемых точек ВП осуществляется путем анализа этого перечня и выяснения, по каким пунктам каждой из указанных трасс планируется произвести полет, возможно ли это, не пропущены ли элементы ВП, совпадает ли курс ВС с направленностью эшелона. Одновременно определяется принадлежность каждой точки сектору УВД. К полученному описанию добавляются точки стандартного маршрута вылета и стандартного маршрута прилета в районе аэродрома. Расписание
Далее рассчитывается высота и время пролета каждой рассматриваемой точки. Информация о расстоянии между точками каждой трассы берется из параметров системы [62]. На участках набора высоты и снижения расчет высо ты и моментов пролета точек производится на основе ЛТХ ВС, в фазе горизонтального полета - исходя из крейсерской скорости. В завершение процедуры распределения маршрут делится на участки, принадлежащие каждый одному сектору, т.е. на участки, движение по которым будет контролироваться одним диспетчером. Участки, как правило, не примыкают друг к другу вплотную, а перекрываются своими концами внахлест. Это объясняется правилами УВД, согласно которым диспетчеры могут передавать друг другу управление бортом не в одной фиксированной точке границы секторов, а в некоторой буферной зоне по обе стороны, насчитывающей несколько точек, одну из которых можно выбрать по договоренности исходя из сложившейся обстановки (текущей загрузки диспетчера). Функция распределения, таким образом, дополняет маршрут последовательностью секторов пролета, представляющей собой список его частично перекрывающихся отрезков в хронологическом порядке следования. В результате система располагает всей информацией для включения нового плана в ИО полетных данных.
Блок-схема алгоритма работы фильтра загрузки приведена на рис. 3.2. Используется информация обо всех элементах ВП, затрагиваемых рейсом и сформированная фильтром маршрутов. По значению времени входа в сектор отыскивается часовой столбец гистограммы загрузки анализируемого элемента и место новой заявки внутри найденного столбца. «Высота» столбца, т.е. новое суммарное количество рейсов в пределах часа, сравнивается с вычисленным порогом - нормативом загрузки данного сектора [43, 62].
В случае превышения порога фильтр загрузки приступает к процедуре анализа приоритета заявок, попавших в текущий столбец гистограммы. Информация о государственном приоритете известна по результатам ФЛК. Обработка планового сообщения приостанавливается, и алгоритму эксперта рекомендаций передается информация об анализируемом рейсе, о факте перегрузки текущего элемента ВП и о приоритете рейса, вызвавшего нарушение норматива работы диспетчера. Фильтр анализировался в п. 2.1.4 (рис. 2.5, 2.6), а здесь дано в виде блок-схемы рис. 3.2 его алгоритмическое описание. Рис. 3.2. Блок-схема работы алгоритма фильтра загрузки.
Блок «Получение информации» последовательно адресует алгоритм к гистограммам элементов ВП, распознанных фильтром маршрутов, к часовым столбцам и нормативам загрузки секторов. Он же организует цикл по затрагиваемым рейсом ПОД, аэродромам, секторам, РЦ для добавления в гистограммы сведений о новом рейсе. По каждому сектору принимается решение о возможности превышении норматива загрузки диспетчера. Если такой факт обнаружен, то производится анализ приоритетности всех рейсов - внутри найденного часа - и формируются данные для эксперта рекомендаций.
Фильтр конфликтов, описанный автором в [61], действует по трехступенчатой схеме. Сначала анализируется совместное распределение ранее включенных в план ИВП заявок с очередной обрабатываемой заявкой в затрагиваемых вводимым маршрутом ПОД и в точках пересечения трасс. Алгоритм последовательно обращается к гистограммам распределения загрузки указанных пунктов, отслеживая соблюдение норм эшелонирования и адресуясь к соответствующим по времени их пролета столбцам (рис. 3.3). Для фазы горизонтального полета строб по высоте составляет величину запрошенного эшелона полета. На участках набора высоты или снижения в рассмотрение включаются вышележащий и нижележащий эшелоны. Строб по времени ограничен значением минимального безопасного интервала (десятью минутами для регулярных рейсов). Претенденты на участие в конфликте сосредоточены в одном столбце гистограммы. Возможность граничных эффектов, если она обнаруживается, блокируется проверкой содержимого соседнего столбца.
Первая ступень фильтра при минимальных затратах производительности компьютера выявляет большинство возможных предпосылок к опасным сближениям, однако она не способна предсказывать конфликты в ситуациях обгона одним воздушным судном другого при следовании на одном эшелоне. Для этой цели предназначена вторая ступень, надстроенная над фрагментом ИО, затрагиваемого маршрутом. По величинам протяженности каждого участка трассы и максимальной разнице крейсерских скоростей при следовании на заданном эшелоне вычисляется безопасный интервал времени возможного сближения ВС. Все претенденты на обгон сосредоточены в соответствующем столбце гистограммы начального /-го пункта рассматриваемого участка трассы ниже (позднее по времени пролета) отметки о вводимой в план ИВП заявке. Если хотя бы одна из претендующих меток будет обнаружена в столбце гистограммы конечного j-ro пункта того же участка трассы выше (ранее по времени пролета) отметки об этой же заявке, то принимается решение о наличии ситуации обгона. Результаты передаются эксперту рекомендаций.
В своей совокупности две ступени обнаруживают конфликты на трассах, однако не обеспечивают выявления опасных сближений при полетах вне трасс. Эту задачу решает третья ступень фильтра. Предпосылки к конфликтным ситуациям оцениваются на основе имитации движения от взлета до посадки по алгоритмической схеме, изложенной ниже, и для всех пересекаемых участков трасс вводятся фиктивные краткосрочные режимные ограничения либо фиктивные навигационные пункты со своими гистограммами распределения загрузки. Все ранее включенные в суточный план заявки, затрагивающие вновь введенные ограничения, подвергаются пересмотру.
Модель без учета корреляции заявок
Для исследования тенденции изменения объема файла, необходимого для сопровождения г записей, в зависимости от количества п компьютеров сети, введем функцию /?„ относительного выигрыша, доставляемого обслуживанием поступающих заявок на /г-канальной системе в сравнении с одноканальной. На первом шаге рассмотрения ограничимся п = 2. При этом вероятность потери записи вследствие недостаточного объема г файла для одного канала (п - 1) составляет [76 - 79]: щ =B- zAt а для п = 2: к2 = 2//+2(l fj. Тогда р2 = 5., или 1 1-рг+2 2 1 + р-2рг+і И1 л-, Р2 = f— j = Р02, где Р02 есть вероятность простоя двухканальной систе мы; вообще, относительный выигрыш, как показывает анализ полученных формул, совпадает по значению с вероятностью простоя системы: Р„ = Р0п.
В предельном случае, при г — оо (неограниченный объем файла) функция относительно выигрыша не зависит от числа п каналов вычислительной системы: Рг- ъ = (1 - р) I (1 + р). Другими словами, для правильно рассчитанной по загрузке (Я р., р 1) системы безразлично число обслуживающих аппаратов, так как все записи находят место в файле. При р —» 1 выигрыш рг- ъ отсутствует вообще. Со снижением загрузки наблюдается прирост значения рп, достигающий максимума при р — 0, однако он носит чисто символический характер, объясняемый упрощениями анализируемой модели. Фактически утверждается, что с ростом п больше заявок одновременно обслуживаются в системе, т. е. больше записей разнесены по локальным БД сети и меньший (относительно одноканальной системы) объем файла с общим доступом занят очередью на удаление.
Графики зависимостей р2 = /(/?) для некоторых значений г представлены на рис. 4.4. Недостатки модели проявляются здесь наиболее наглядно. Для вычислительной сети с распределенной БД, не имеющей файла с общим доступом, в противоположном предельном случае, при г = О, даже в условиях полной загрузки выигрыш составляет двадцать процентов (р2 = 0,2). Даль 113 нейшее наращивание количества п каналов еще выше поднимает минимум /?„ для вычислительной сети без общего файла доступа. Однако использование даже небольшого общего файла (г = 5) резко снижает символический эффект вычислительной сети относительно одного канала, а при г = 10 преимущества параллельной обработки по рассматриваемому критерию практически исчерпываются. г — оо
Анализ семейства кривых / = f(p) позволяет обойти недостатки упрощенной модели. Увеличение количества п каналов системы интерпретируется в ней как тривиальное приращение числа мест для ожидания. Считается, что записи распространяются по локальным файлам распределенной БД вычислительной сети, и доступ к информации соседа возможен лишь как запрос данных, реализуемый через отдельную заявку. Для формализации модели файла с общим доступом достаточно стабилизировать в ней общее количество п + г мест в системе. Тогда увеличение количества п каналов будет компенсироваться равным ему сокращением объема г файла. В результате отношение ап+г вероятности Рг(п) потери записи в/г - канальной системе с объе мом г файла общего доступа к вероятности Pr+n.i(1) потери заявки в эквивалентной по пропускной способности и количеству размещаемых записей одноканальной системе составит (ап+г есть аналог /?„ при фиксированном значении суммы п + г):
Нетрудно видеть, что во всем диапазоне изменения загрузки р системы 0 =р =\ при любых п 1 отношение ап+г 1 и возрастает с увеличением п (п + r = Const). Это значит, что потери записей в системе, содержащей п каналов и общий буферный накопитель (БН) объемом на г заявок, выше, чем в одноканальной системе с БН длиной г + п + 1. В поставленной задаче величина Р задается априорно в качестве ограничительного параметра. Следовательно, для удовлетворения условий допустимого уровня потери записей, объем файла общего доступа в многоканальной системе необходимо резервировать более вместительным, чем в одноканальной системе. Широко известна и обратная задача: при заданных значениях интенсивности входного потока Я, параметра обслуживания /и, количества приборов п и мест ожидания г определить вероятность Р потери заявки, также решенная полученными формулами.
Для сопоставления многоканальных систем при различных Q, необходимо нормировать их суммарным зна п чением: YJQI- а первом шаге рассмотрения ограничимся сравнением СМО с одним и двумя приборами (компьютерами), в дальнейшем это ограничение будет снято. Напомним, что нерегулярность входного потока проявляется в наличии периодов спада и возрастания текущих значений частоты поступления заявок (рис. 4.5). График, изображенный на рис. 4.6, дает представление о соотношении величин вероятностей Р потери заявки для предельного слу 115 (р = 0.3), в которой БД вычислительных систем обычно не эксплуатируются, использование двух каналов дает выигрыш даже при полном запрете приема на обслуживание заявки вторым прибором, если работает первый (Q2 = 0). Соответственно, суммарная загрузка СМО достигает лишь половины показателя для случая отсутствия корреляции. Сказывается малая занятость системы в среднем. Вследствие нерегулярности входного потока типична следующая ситуация. «Сгущения» моментов поступлений расположены на оси времени таким образом, что использование второго канала в качестве БН полезнее для системы, пусть даже и вдвое менее производительной, чем один быстродействующий канал, не успевающий «захватить» (вследствие отсутствия буфера) очередную заявку и простаивающий затем в периоды относительного «разрежения» входного потока.
С увеличением загрузки при Q2 = 0 потери в двухканальной системе резко возрастают и при/? —» 1 достигают максимума, значительно превосходя соответствующий показатель для одноканалыюй системы. Вероятность потери записи для случая Q2 = 1 всегда ниже, чем при использовании одного прибора. Напомним, что функция относительного выигрыша р2 (рис. 4.4) даже при р — 1 достигает величины 0,2. Эта тенденция отчетливо прослеживается на графике рис. 4.6. Кривая, соединяющая наивысшие значения Рс для предельных случаев Q2 = 0 и Q2 = 1, есть годограф функции Pc-fiQi) ПРИ стремлении значения загрузки системы р к единице р— \. При этом суммарная загрузка двухканальной СМО поддерживается на уровне р{\ + Q2) и не достигает удвоенной величины при Q2 \.
