Уточнение формул для дисциплины обслуживания с приоритетами по результатам моделирования

УДК 629.735.015:681.3

УТОЧНЕНИЕ ФОРМУЛ ДЛЯ ДИСЦИПЛИНЫ ОБСЛУЖИВАНИЯ С ПРИОРИТЕТАМИ ПО РЕЗУЛЬТАТАМ МОДЕЛИРОВАНИЯ

К.А. ГЛАГОВСКИЙ, О.В. МОИСЕЕВ, Л.Е.РУДЕЛЬСОН

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

Ключевые слова: воздушное пространство, имитационная модель сбора и обработки.

Введение

Одной из главных задач аэронавигационной системы (АНС) является создание условий, гарантирующих всем пользователям воздушного пространства (ВП) доступ к ее ресурсам, необходимым для удовлетворения эксплуатационных потребностей и обеспечения высокого уровня безопасности полетов. На ее решение нацелена модернизация аэронавигационной службы России. С этой целью создается единая федеральная электронная база аэронавигационной информации (АНИ). Осуществляется реформирование системы планирования использования воздушного пространства (ИВП) и подсистемы организации потоков воздушного движения (ОПВД). Изменены функции оперативных органов Единой системы организации воздушного движения (ЕС ОрВД) России, их организационная структура. Объединены военные и гражданские секторы центров ЕС ОрВД. На первый план выдвинуты интеграция планирования на трассах и вне трасс в главном, зональных и районных центрах (ГЦ, ЗЦ, РЦ), создание централизованной федеральной системы планирования ИВП (ПИВП).

Эти мероприятия намечены на самом высоком уровне: постановление Аэронавигационного совета (Коллегии) [1], распоряжение Правительства [2], указ Президента РФ [3]. Техническая реализация принятых решений требует их тщательного научного анализа и обоснования. Необходимо определить условия работы системы, при соблюдении которых новые организационные решения будут максимально способствовать достижению поставленной цели. В статье на примере централизации обработки планов полетов обсуждаются некоторые результаты исследований, проводимых специалистами МГТУ Г А.

1. Постановка задачи

Концепция централизованной службы обработки планов полетов (ЦСОПП), заложенная в программу реформирования ПИВП, отвергает традиционный порядок рассылки плановых сообщений из аэропорта вылета во все органы ОВД по маршруту полета и в специальные адреса, заменяя его требованием отправки сообщений в единственный адрес ГЦ ЕС ОрВД. Специалисты ГЦ уполномочены исправлять противоречия в тексте заявки и согласовывать с составителем новую редакцию, которая затем включается в суточный план ИВП и рассылается из ГЦ по адресам согласно Табелю сообщений о движении воздушных судов (ВС).

Преимущества централизации очевидны. Только в центре, владеющем всей полнотой актуальной аэронавигационной и плановой информации, возможно оптимальное планирование и регулирование потоков ВС. Очевидны и недостатки: рост риска ошибочного решения, замедле-

ние реакции системы на изменения условий выполнения полетов, возрастание трафика в линиях связи и нагрузки на персонал, снижение живучести.

Задачей исследования в ситуации, когда организационное решение уже принято к исполнению, становится выбор параметров системы, обеспечивающих рациональное выполнение ее функций. В этом направлении получены обнадеживающие теоретические результаты для оценки эффективности «в среднем по времени» централизованной обработки данных различной приоритетности по известным критериям длительности ожидания и вероятности отказа в обслуживании. Задачи систем с приоритетами возникают в авиации не только при анализе показателей работы авиационной электросвязи, но и при формировании очередности аэродромных операций, распределении частот радиообмена по каналам автоматического зависимого наблюдения и вообще в случаях ограниченности ресурсов обслуживания.

Отправным пунктом служит предположение о правомерности замены случайной величины длины очереди заявок в системе ее наиболее вероятным значением [4]. Рассмотрим для конкретных соотношений параметров модели области их изменения, в которых использование предлагаемых методов не связано с высокой погрешностью расчетов.

Состояние очереди сообщений (заявок) в общем буферном накопителе (БН) можно пояснить простыми рассуждениями. Согласно правилам приоритетного обслуживания все ресурсы системы предпочтительно предоставлены заявкам высокого приоритета (ЗВП). Они обрабатываются в порядке поступления, они принимаются в БН, а если в системе нет свободных мест для ожидания, тогда поступившая ЗВП вытесняет из очереди заявку низкого приоритета (ЗНП) и занимает ее место. Гипотеза равновесного состояния говорит о том, что процесс обслуживания ЗВП описывается марковской цепью, что заявки менее высоких приоритетов в условиях динамического равновесия не оказывают на него существенного влияния, и характеристики работы можно рассчитать по классическим формулам.

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

Следующий шаг - исследование условий обслуживания потока ЗНП. В штатных (равновесных) условиях ему предоставлена часть БН, свободная от ЗВП, т.е. известное количество г мест для ожидания за вычетом случайной величины длины Ь1 очереди заявок первого типа. Нужно научиться рассчитывать эту величину. Далее, ЗНП назначаются на обслуживание только при отсутствии ЗВП. Нужно научиться рассчитывать либо время, в течение которого система массового обслуживания (СМО) свободна от ЗВП, либо оперировать параметром создаваемой ими загрузки, чтобы оценить ресурсы, предоставленные ЗНП. Тогда можно представить марковской цепью и процесс обслуживания второго потока, чтобы найти количественные соотношения, связывающие вероятность потери заявки и время ожидания с параметрами СМО. В дополнение к штатному режиму, как и при анализе условий обслуживания ЗВП, следует учесть ситуации, при которых БН переполняется заявками второго типа, и в системе возникает поток отказов в их обслуживании, не учтенный известными формулами.

2. Формализация задачи

С помощью аналогичных рассуждений нетрудно [4] сформулировать гипотезу равновесного состояния для общего БН с приоритетным приемом заявок произвольного количества т входящих потоков, упорядоченных шкалой относительных приоритетов.

Выдвигаемая гипотеза состоит в том, что равновесное состояние СМО с относительными приоритетами и приоритетным приемом заявок т потоков в общий БН емкостью г мест для

ожидания может быть представлено композицией т моделей с однородными входящими потоками. Для каждой 1-й составляющей, описывающей условия обслуживания /-го потока, должно вычисляться собственное значение количества г/ мест для ожидания и создаваемая всеми более приоритетными потоками загрузка канала. Учитываются дополнительные потери в условиях выбросов, когда ЗВП переполняют ограниченный БН и теряются в сеансах обслуживания неприоритетных заявок. В такой постановке удается формализовать задачу и получить аналитические выражения для оценки вероятностей отказа по каждому входному потоку. Расчетные формулы распространены на случай произвольного количества каналов СМО и проверены методом статистического моделирования [4] (рис. 1).

Пі

0,3

0,2

0,1

Параметры СМО: п = 1; т = 5; рг = 0.18 и г = 10 Результаты расчета

1 2 3 5 10 20 30 50 1п у

Рис. 1. Графики зависимостей пі = /(у) для СМО с приоритетами

Моделирование показывает, что расчетные кривые дают завышенные оценки потерь заявок по приоритетным потокам справа от точек излома кривых пі = /(у).

Вероятность пк потери заявки для к-го потока

к-1

Ър,

С к у -(1+}2 К Ъ ^ Гр і с к \

1 - Ъа

V і=1 у

1 -

Ър,

V і=1 у

( \ ук ' ^ р ^

если (1 + $2 )ук ^ —- < г, где Уг = /Л} /щ - со-

1= V У/ у

отношение параметров обслуживания или обратных им величин среднего времени Т/ хранения заявки в БН у, = Т /Т}.

к-1

Ър,

п

_ У і=1 У

1 - Ър,

V і=1 у

+

с к у г -(1+«2Ьъ[р) +1 ]=к

' і=1V г у

1 - Ър,

V ,=1 у

к-1 С р У , к с р У

Ъ8к р,

1+Ър,

і=1

1-

г-(і + }) у} Ъ

к-1

к1 ^ рг

і=1

Пг

если (1 + в2) п Ъ ~ £ г < (1 + 'в1 П Ъ ~ , где 6к - символ Кронекера; ], к = {1, т },

V П у

V П у

т - количество входных потоков; и - коэффициент вариации времени обслуживания Т/.

1

г =1

г=1

!л

I=1

к

1 +

/ \ к 1 \ Р = —*=т-----, если (1 + 3)у £ —

1=1 V у J

> г.

I =1

На первый взгляд создается впечатление, что потоки заявок в модели механически разделены по признаку приоритетности, что они рассматриваются автономно друг от друга. Однако в формулах учтены зависимости каждого потока от других по параметрам: интенсивности поступления Хи соотношения средних значений времени обслуживания уи от создаваемой ими загрузки р1, от места I в шкале приоритетов, от длины Ь1 очереди ожидания для каждого из потоков.

Создатели авиационной электросвязи понимали, что каждая телеграмма должна поступить к адресату, но в реальной системе достичь стопроцентной вероятности невозможно. Были разработаны инженерные идеи, позволившие решить проблему за счет перезапросов пропущенных телеграмм и повторных запросов некорректных сообщений. Как следствие, потерь телеграмм практически нет, но если система организована плохо, то она сама себя перегружает потоком повторных запросов. И задача состоит в том, чтобы рационально организовать процесс сбора и обработки, чтобы вероятности перезапросов и потери заявок стремились к минимуму и были упорядочены по приоритетам (рис. 1).

3. Уточнение формул по результатам моделирования

Вероятность потери заявки справа от точки излома определена из физического смысла модели и ее особенностей: при невыполнении неравенства (1 + 3 — У< г весь БН предоставлен в распоряжение потока ЗВП. Рассмотрим систему с двумя входными потоками. Заявки второго типа, даже если они ожидают в очереди, вытесняются из системы и, следовательно, их обслуживание осуществляется справа по оси у от точки (1 + З2 — у = г по правилам для СМО без БН (г = 0). Вероятность их потерь

Р2 = А1(- Ах) = , если (1 + $2 ^ 7> г.

1 Ръ 1 + ръ

Суммирование загрузки по обоим потокам рЕ = р1 + р2 подчеркивает тот факт, что обслуживание ЗНП производится лишь при отсутствии ЗВП. Вероятность Р2 обслуживания ЗНП в условиях приоритетной записи справа от точки (1 + 3 )Р1 у = г по оси у вычисляется как дополнение п2 до единицы

Р2 = 1 - Р2 = 1-А— = —1—, если (1 + З2 р у > г.

1 + ръ 1 + ръ

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

г

Р = рГ1(1 -р1 > + 8-—1 -рГ2 1+Ръ

1 (1 + 3 —у _

[о, если (1 + 3 — у< г, где 8 = < , остальные символы определены выше.

[ 1 в противном случае

Результаты статистического моделирования показывают, что слева от точки излома кривых П = / (у) расчетные значения несколько занижены, а справа от нее - завышены относительно данных имитационного эксперимента. Простые рассуждения позволяют объяснить причины обнаруженной тенденции.

Из рис. 1 нетрудно видеть, что справа от точки излома имеет место резкий рост величины

Вход

Инициализация параметров

Расчет начальных значений п

I

Организация итерационной процедуры

вероятности п1 потери ЗВП, и реальная загрузка СМО потоком высокого приоритета р1г соответственно снижается до р1г = (1 - п^рь В формулах для п1 и п2 используется суммарная загрузка р£, вычисленная из исходных интенсивностей приоритетного входных потоков и номинальной пропускной способности канала обслуживания. Однако в процессе работы СМО оба потока заявок прореживаются в связи с переполнением буферного накопителя, и реальные значения р^ уменьшаются. Для преодоления этого затруднения следует использовать итеративную процедуру уточнения расчета, состоящую из трех шагов (рис. 2).

1. Вычислить значения вероятностей п потери заявки по формулам раздела 2 настоящей статьи с целью уточнения условий обработки каждого из них.

2. Для каждой расчетной точки по оси у вычислить величину уточненной загрузки в ней рг = (1-п1)рг- и найти суммарную загрузку р^ обслуживаемыми потоками.

3. Рассчитать новые значения слева и справа от точки излома кривой щ = / (у).

Выход из процедуры производится по достижении заданной замыслом задачи разности е между результатами предыдущей и последующей итераций.

Блок-схема процедуры уточнения величин п представлена на рис. 2.

Пример. Исходные данные и алгоритм итерационной процедуры уточнения значений щ приведены на рис. 3. Исследовалась система с параметрами п = 1, т = 2 , г = 10, и = 0, р1 = р2 = 0.45. Значения п = /(у), рассчитанные по исходным формулам, представлены на рис. 4 пунктирными линиями. В качестве условия 8 выхода из процедуры уточнения использовано достижение разницей Ал между текущим и предшествующим вычисленными значениями п десяти процентов.

На первом же шаге итерации получены новые значения пг-, удовлетворяющие заданному условию. Уточненные кривые даны сплошными линиями.

В качестве инструмента для тестирования системы использовался математический редактор МаШСаё, на вход которого подавались указанные выше параметры СМО (рис. 3). Графики функций п = /(у) приведены на рис. 4.

Расчетные значения для п1,2 сведены в таблицу исходных и выходных (с указанием номера итерации) данных. Уже на второй итерации результаты уточнения сходятся к асимптотическому значению с точностью до процента, причем на каждой очередной итерации значения переходят через асимптотическую кривую, оказываясь то выше, то ниже нее. Объяснение данного эффекта состоит в том, что каждый шаг итерации приводит к скачкообразному перераспределению долей загрузки системы обслуживанием потоков разных приоритетов. В результате обе кривые, как рычажные весы, раскачиваются с уменьшающейся амплитудой.

Расчет новых значений Пі

Нет г\ н с о \ к о \ ° г вление

Ал < 8?

Да

Рис. 2. Блок-схема процедуры расчета

Рис. 3. Исходные данные и алгоритм преобразования

Таблица 1

В области слева от точки укр излома кривых щ = /(у),

определенной как укр = г / (1 + в2)р1, значения вероятностей потери заявки достигают необходимой точности уже на первой итерации. В критической точке результаты расчетов начинают уменьшаться относительно прогноза изначальных формул вследствие предсказанного прореживания входных потоков, заявки которых не находят места в ограниченном объеме БН. Нарушение плавности кривой п2 в окрестности укр вызвано отступлением от целочисленности значений показателя степени при р1, которые вычисляются при подстановке очередного нового у в исходные расчетные формулы.

Справа от точки излома кривых значения п2 оказываются ниже первоначально рассчитанных, так как в связи с резким возрастанием вероятности п1 потери заявок высокого приоритета заметно улучшают условия обслуживания заявок низкого приоритета.

У п1 п2 У п1 п2

расчет итерация ша расчет итерация шаг расчет итерация шаг расчет итерация шаг

1 0.000084 0.000084 0 0.046749 0.046749 0 49 0.258946 0.214806 2 0.473684 0.392915 2

2 0.000084 0.000084 0 0.050041 0.050041 0 50 0.263242 0.218179 2 0.473684 0.392571 2

3 0.000084 0.000084 0 0.053644 0.053644 0 51 0.26737 0.221415 2 0.473684 0.392242 2

4 0.000084 0.000084 0 0.057599 0.057599 0 52 0.271339 0.224522 2 0.473684 0.391929 2

5 0.000084 0.000084 0 0.061955 0.061955 0 53 0.275159 0.227508 2 0.473684 0.391629 2

6 0.000084 0.000084 0 0.066771 0.066771 0 54 0.278837 0.230381 2 0.473684 0.391343 2

7 0.000084 0.000084 0 0.072117 0.072117 0 55 0.282381 0.233145 2 0.473684 0.391069 2

8 0.000084 0.000084 0 0.078079 0.078079 0 56 0.285799 0.235808 2 0.473684 0.390806 2

9 0.000084 0.000084 0 0.084763 0.084763 0 57 0.289096 0.238375 2 0.473684 0.390554 2

10 0.000084 0.000084 0 0.092297 0.092297 0 58 0.29228 0.240851 2 0.473684 0.390312 2

11 0.000084 0.000084 0 0.100846 0.100846 0 59 0.295356 0.243241 2 0.473684 0.390079 2

12 0.000084 0.000084 0 0.110617 0.110617 0 60 0.29833 0.245549 2 0.473684 0.389856 2

13 0.000084 0.000084 0 0.121879 0.121879 0 61 0.301206 0.247779 2 0.473684 0.389641 2

14 0.000084 0.000084 0 0.134986 0.134986 0 62 0.303989 0.249936 2 0.473684 0.389434 2

15 0.000084 0.000084 0 0.150413 0.150413 0 63 0.306684 0.252023 2 0.473684 0.389235 2

16 0.000084 0.000084 0 0.168811 0.168811 0 64 0.309295 0.254043 2 0.473684 0.389043 2

17 0.000084 0.000084 0 0.191106 0.191106 0 65 0.311825 0.255999 2 0.473684 0.388858 2

18 0.000084 0.000084 0 0.218644 0.218644 0 66 0.314279 0.257895 2 0.473684 0.388679 2

19 0.000084 0.000084 0 0.253478 0.253478 0 67 0.316659 0.259733 2 0.473684 0.388507 2

20 0.000084 0.000084 0 0.298893 0.298893 0 68 0.31897 0.261516 2 0.473684 0.388340 2

21 0.000084 0.000084 0 0.360490 0.360490 0 69 0.321213 0.263246 2 0.473684 0.388180 2

22 0.000084 0.000084 0 0.448672 0.383703 1 70 0.323393 0.264926 2 0.473684 0.388024 2

23 0.016103 0.014145 2 0.473684 0.415794 2 71 0.325511 0.266558 2 0.473684 0.387873 2

24 0.035172 0.030735 2 0.473684 0.413790 2 72 0.32757 0.268143 2 0.473684 0.387728 2

25 0.052716 0.045859 2 0.473684 0.411973 2 73 0.329572 0.269684 2 0.473684 0.387587 2

26 0.06891 0.059703 2 0.473684 0.410319 2 74 0.331521 0.271183 2 0.473684 0.387450 2

27 0.083905 0.072425 2 0.473684 0.408808 2 75 0.333418 0.272641 2 0.473684 0.387317 2

28 0.097829 0.084156 2 0.473684 0.407424 2 76 0.335264 0.274060 2 0.473684 0.387189 2

29 0.110792 0.095009 2 0.473684 0.406152 2 77 0.337063 0.275442 2 0.473684 0.387064 2

30 0.122891 0.105079 2 0.473684 0.404980 2 78 0.338816 0.276787 2 0.473684 0.386943 2

31 0.13421 0.114449 2 0.473684 0.403897 2 79 0.340524 0.278098 2 0.473684 0.386826 2

32 0.144821 0.123191 2 0.473684 0.402893 2 80 0.34219 0.279376 2 0.473684 0.386712 2

33 0.154789 0.131365 2 0.473684 0.401962 2 81 0.343814 0.280622 2 0.473684 0.386601 2

34 0.164171 0.139025 2 0.473684 0.401094 2 82 0.345399 0.281837 2 0.473684 0.386493 2

35 0.173017 0.146220 2 0.473684 0.400286 2 83 0.346945 0.283022 2 0.473684 0.386388 2

36 0.181371 0.152991 2 0.473684 0.399530 2 84 0.348455 0.284178 2 0.473684 0.386286 2

37 0.189273 0.159374 2 0.473684 0.398823 2 85 0.349929 0.285307 2 0.473684 0.386187 2

38 0.19676 0.165402 2 0.473684 0.398159 2 86 0.351369 0.286410 2 0.473684 0.386090 2

39 0.203863 0.171104 2 0.473684 0.397536 2 87 0.352776 0.287486 2 0.473684 0.385996 2

40 0.210611 0.176506 2 0.473684 0.396950 2 88 0.354151 0.288538 2 0.473684 0.385905 2

41 0.217029 0.181632 2 0.473684 0.396397 2 89 0.355495 0.289566 2 0.473684 0.385815 2

42 0.223142 0.186502 2 0.473684 0.395875 2 90 0.356809 0.290571 2 0.473684 0.385728 2

43 0.22897 0.191134 2 0.473684 0.395382 2 91 0.358095 0.291554 2 0.473684 0.385644 2

44 0.234534 0.195547 2 0.473684 0.394915 2 92 0.359352 0.292514 2 0.473684 0.385561 2

45 0.23985 0.199756 2 0.473684 0.394473 2 93 0.360582 0.293454 2 0.473684 0.385480 2

46 0.244936 0.203774 2 0.473684 0.394053 2 94 0.361786 0.294374 2 0.473684 0.385401 2

47 0.249804 0.207614 2 0.473684 0.393655 2 95 0.362965 0.295274 2 0.473684 0.385324 2

Рис. 4. Результаты уточнения графиков функций = /(у) итеративной процедурой

Заключение

В статье рассмотрена частная модель системы обслуживания с приоритетами, позволяющая оценить пропускную способность централизованной службы обработки планов полетов, разрабатываемой для решения задач планирования использования воздушного пространства в главном центре ЕС ОрВД. Полученные результаты распространены на случай произвольного количества приоритетных потоков заявок и каналов обслуживания. Материалы, положенные в основу статьи, использованы в техническом проекте автоматизированной системы АС ПИВП ГЦ [5, 6].

ЛИТЕРАТУРА

1. Постановление Аэронавигационного совета (Коллегии) № 2 от 12.09.07.

2. О концепции федеральной целевой программы «Модернизация Единой системы организации воздушного движения Российской Федерации (2009 - 2015 годы): Распоряжение Правительства РФ № 1974-р от 29.12.2007.

3. О федеральной аэронавигационной службе от 24.09.2007 № 1274: Указ Президента РФ.

4. Ребров В.А., Рудельсон Л.Е., Черникова М.А. Модель сбора и обработки заявок на полеты в задаче планирования авиарейсов // Известия Российской академии наук. Теория и системы управления. - 2007. - № 3.

5. Автоматизированная система планирования использования воздушного пространства и организации потоков воздушного движения для Главного центра ЕС ОрВД. Технический проект ПАВУ.466453.001ПЗ. - М., 2010.

6. О ходе работ по созданию Единой системы планирования использования воздушного пространства РФ: ОАО «НТЦ «ПРОМТЕХАЭРО» // Вестник авиации и космонавтики. - 2011. - № 5.

IMPROVING OF FORMULAS FOR PRIORITY SERVICE DISCIPLINE BASED ON THE RESULTS OF MODELING

Glagovskiy K.A., Moiseev O.V., Rudelson L.E.

Reforming the common system of air traffic in Russia put forward a series of engineering and theoretical problems, such as the choice of a rational scheme for the collection, processing, storage and distribution of air-navigation and planning information. This paper discusses an analytical model of a centralized system for collecting and processing of flight plans of the main center of planning and regulation of traffic flows, allowing the work to organize a rational system based on new information technology in civil aviation.

Key words: using of air space, imitation model of data collection and processing.

Сведения об авторах

Глаговский Кирилл Андреевич, 1989 г.р., окончил МГТУ ГА (2011), аспирант кафедры вычислительных машин, комплексов и сетей МГТУ ГА, автор 5 научных работ, область научных интересов -вычислительные системы и методы, распределенные системы, организация вычислений.

Моисеев Олег Владимирович, 1988 г.р., окончил МГТУ ГА (2010), аспирант кафедры вычислительных машин, комплексов и сетей МГТУ ГА, автор 5 научных работ, область научных интересов -вычислительные системы и методы, распределенные системы, организация вычислений.

Рудельсон Лев Ефимович, 1944 г.р., окончил МЭИ (1968), доктор технических наук, профессор МГТУ ГА, автор более 140 научных работ, область научных интересов - программное обеспечение автоматизированных систем организации воздушного движения.