Содержание к диссертации
Введение
1 Анализ применения У5АГ-технологии при построении корпоративных сетей спутниковой связи и пути повышения эффективности их функционирования 8
1.1 Требования к видам услуг, предоставляемых корпоративными сетями спутниковой связи, и технологии их построения 8
1.2 Методы многостанционного доступа и способы предоставления ресурса, используемые в VSAT-сетях спутниковой связи 17
1.3 Сравнительный анализ и обоснование целесообразных методов МД и способов предоставления ресурсов для корпоративных VSAT-CCC 23
1.4 Принципы построения автоматизированной подсистемы управления VSAT-сети спутниковой связи 34
1.5 Постановка задачи управления порогами резервирования ресурса ретранслятора (зонами доступности к ресурсу) при обслуживании многоприоритетных потоков заявок пользователей
Выводы по главе 1 42
2 Модели многоприоритетных потоков требований и методы оценки состояния и анализа эффективности функционирования КССС 44
2.1 Обоснование модели многоприоритетного потока требований на основе аппарата управляемых цепей Маркова 44
2.2 Принцип разделения и сущность этапов разработки алгоритма текущей оценки интенсивности входящего потока требований, оптимального в смысле МСКО и алгоритма управления при зашумленных наблюдениях за состоянием нагрузки на основе метода динамического программирования 47
2.3 Методы оценки эффективности функционирования корпоративной сети спутниковой связи 55
Выводы по главе 2 61
3 Алгоритмы управления качеством обслуживания многоприоритетного трафика в VSA Т-корпоративных сетях спутниковой связи и предложения по его реализации в составе АСУ КССС 63
3.1 Рекуррентный алгоритм оптимизации порогов резервирования ресурса ретранслятора при обслуживании многоприоритетного потока требований пользователей 63
3.2 Разработка итерационного алгоритма оптимизации порогов резервирования ресурса ретранслятора при обслуживании многоприоритетного потока требований пользователей 67
3.3 Примеры решения задачи оптимизации порогов резервирования при обслуживании заявок различных приоритетов на основе предложенного итерационного алгоритма 73
3.4 Сравнительная оценка эффективности функционирования КССС при обслуживании многоприоритетных потоков требований пользователей и использовании в системе распределения ресурсов ретранслятора разработанного алгоритма оптимизации порогов резервирования 85
Выводы по главе 3 91
Заключение 92
Литература
- Методы многостанционного доступа и способы предоставления ресурса, используемые в VSAT-сетях спутниковой связи
- Принципы построения автоматизированной подсистемы управления VSAT-сети спутниковой связи
- Принцип разделения и сущность этапов разработки алгоритма текущей оценки интенсивности входящего потока требований, оптимального в смысле МСКО и алгоритма управления при зашумленных наблюдениях за состоянием нагрузки на основе метода динамического программирования
- Разработка итерационного алгоритма оптимизации порогов резервирования ресурса ретранслятора при обслуживании многоприоритетного потока требований пользователей
Введение к работе
Актуальность темы. Анализ задач информационного обеспечения показал, что для их эффективного решения современная система связи уже на сегодняшний день должна предоставлять возможность:
передачи мультимедийного трафика;
передачи файлов большого объема, содержащих мультимедийную информацию;
удаленного доступа к базам данных в реальном масштабе времени;
организации видеоконференций;
обмена электронной почтой (электронного документооборота).
Устойчивая тенденция значительного роста информационных потоков, необходимых для принятия решений в органах управления обусловлена, с одной стороны, ростом обмена официальными документами, с другой стороны, сокращением сроков их прохождения. Все это требует существенного роста пропускной способности существующих сетей связи (особенно спутниковых) и поиска путей по ее обеспечению в изменяющихся условиях функционирования. При этом развитие телекоммуникационной составляющей системы информационного обеспечения должно осуществляться в направлении создания мультисервисной транспортной сети, позволяющей осуществлять высокоскоростной обмен цифровой информацией и организовывать территориально распределенные вычислительные сети, при безусловном соблюдении требований информационной безопасности и интеграции с действующими сетями связи.
Особую роль в создании корпоративных систем связи и управления в последние десятилетия играют сети спутниковой связи в силу наличия у них таких свойств как глобальность связи, устойчивость к наземным катаклизмам (землетрясению, наводнению, урагану, селям и т.п.) мобильность, высокое качество услуг связи и оперативность их предоставления.
Широко используемая в настоящее время для построении коммерческих сетей спутниковой связи технология VSAT (Very small aperture terminal) ори-
ентирована на значительное повышение пропускной способности (расширение перечня и качества услуг), малые апертуры антенн абонентских станций, использование ретрансляторов связи на геостационарных ИСЗ, а также методы обработки радиосигналов и сетевые технологии, особо чувствительные к нестабильности характеристик и параметров линий (сети) связи, что делает затруднительным прямое использование технологии VSAT в выделенных (корпоративных) сетях спутниковой связи. Кроме того, VSAT-сети практически не имеют энергетического запаса на решение вопроса помехоустойчивости, не обеспечивают встречной работы со старым парком средств и требуют серьезных финансовых затрат на дооборудование существующих наземных терминалов. С другой стороны, заложенные в семидесятые годы прошлого столетия технические решения по построению ретрансляторов связи и парка наземных средств ведомственных сетей спутниковой связи фиксированной службы принципиально не позволяют реализовать в них современные перечень и качество услуг связи, сравнимые с VSAT-сетями.
Проблемам повышения эффективности функционирования сетей связи, как систем массового обслуживания (СМО), предоставляющим ресурс ретранслятора случайным потокам заявок пользователей посвящено значительное число работ отечественных и зарубежных авторов. К ним, в первую очередь, относятся работы А.Я. Хинчина, А. Д. Харкевича, Л. Я. Кантора, В. И.Тихонова, Н. П. Бусленко, А. Г. Зюко, Л. Клейнрока, Скляра Б., Спилкера Дж.и др. Однако обеспечение эффективного функционирования современных сетей связи при обслуживании многоприоритетных и мульти-сервисных потоков заявок пользователей требует разработки новых, более эффективных алгоритмов динамической оптимизации ресурсов сети, а, следовательно, требует адаптации технологии VSAT к специфическим условиям функционирования корпоративных сетей спутниковой связи, и в частности, разработки эффективных алгоритмов обеспечения требуемой безопасности и помехозащищенности этих сетей связи, а также текущего управления качеством обслуживания абонентов в условиях изменяющейся и многоприоритетной нагрузки пользователей и наличия технических отказов бортовой и наземной аппаратуры.
Последние определяет актуальность темы проводимого в работе исследования - «Разработка алгоритмов оптимального управления качеством
обслуживания в У5ЛГ-корпоративных сетях спутниковой связи в условиях изменяющейся многоприоритетной нагрузки» и позволяет сформулировать цель и решаемую в ней научную задачу.
Цель и задачи работы. Целью проводимого в работе исследования является повышение эффективности функционирования корпоративных VSAT — сетей спутниковой связи (по вероятностным показателям качества обслуживания и своевременности доставки сообщений, а также степени использования ресурсов) при обслуживании многоприоритетной нагрузки от абонентов на основе совершенствования алгоритмов динамической оптимизации плана распределения радиоресурсов ретранслятора.
Научная задача состоит в разработке алгоритма оптимального управления объемом (числом единиц) радиоресурса ретранслятора, выделяемого для обслуживания потока заявок каждого приоритета и соответствующими зонами доступности к ресурсу ретранслятора (порогами резервирования), обеспечивающего максимизацию суммарной обслуженной нагрузки при гарантированном выполнении требований к качеству обслуживания высокоприоритетных заявок пользователей.
Методы исследования. В процессе выполнения диссертации использовались математический аппарат теорий вероятности и случайных процессов, сложных систем, стохастического оптимального управления, чувствительности и эффективности целенаправленных процессов, а также методы имитационного моделирования.
Научная новизна.
-
Разработаны математические методы представления потоков требований от многоприоритетных пользователей, методы оценки и прогнозирования их параметров, предложен адекватный критерий оптимальности функционирования КССС, а также метод анализа эффективности управления зонами доступности к ресурсу ретранслятора со стороны многоприоритетных заявок пользователей.
-
Разработан рекуррентный и итерационный алгоритмы динамической оптимизации порогов резервирования (зон доступности) ресурса ретранслятора в условиях изменяющейся многоприоритетной нагрузки от пользователей и заданных требованиях к качеству обслуживания
высокоприоритетных заявок, реализующий принцип коммутации сообщений и не допускающий прерывания обслуживания низкоприоритетных заявок.
3. Предложена модель функционирования КССС, использующей алгоритмы управления ресурсом, обеспечивающая возможность вероятностной оценки показателей эффективности функционирования КССС при оптимизации плана распределения ресурсов с учетом многоприоритет-ности и временных изменений нагрузки.
Практическая ценность и реализация результатов. На основе разработанных в диссертации алгоритмов динамической оптимизации плана распределения ресурсов ретранслятора могут быть легко реализованы как бортовые, так и наземные подсистемы управления ресурсом в условиях обслуживания многоприоритетного трафика, позволяющие без использования дополнительного оборудования обеспечить существенное (до 10%) повышение эффективности использования ресурса ретранслятора в сетях спутниковой связи.
На защиту выносятся следующие основные научные результаты:
аналитическая модель и методика анализа эффективности функционирования КССС, использующих технологию VSAT, учитывающие наличие в составе СМО АСУ КССС алгоритма оптимального управления ресурсом ретранслятора при обслуживании многоприоритетного потока заявок пользователей;
рекуррентный и итерационный алгоритмы оптимального управления планом резервирования радиоресурсов ретранслятора и зонами доступности к ресурсу для потоков заявок различного приоритета, обеспечивающий максимизацию суммарной обслуженной нагрузки при гарантированном качестве обслуживания требований высшего приоритета в условиях изменяющейся нагрузки пользователей;
результаты оценки эффективности функционирования и предложения по программно-аппаратной реализации алгоритмов управления качеством обслуживания многоприоритетных потоков требований, использующих в составе СМО АСУ перспективных КССС разработанные ал-
горитмы управления качеством обслуживания многоприоритетных потоков заявок пользователей.
Апробация работы. Основные результаты работы докладывались на 7-й Научно-практической конференции «Проблемы развития технологических систем государственной охраны, специальной связи и специального информационного обеспечения», (Академия ФСО России, Орёл, Россия, 2011 г.), Конференции молодых ученых и специалистов, посвященная 55-летию со дня образования НИИ автоматической аппаратуры им.В.С.Семенихина (НИИ АА им. В.С.Семенихина, Москва, Россия, 2011 г.), Всероссийской молодежной научно-технической конференции на тему «Прикладные научно-технические проблемы современной теории управления системами и процессами» (ОАО «Концерн «Вега», Москва, Россия, 2012 г.), а также на семинарах отдела математического моделирования систем проектирования Вычислительного центра им. А.А.Дородницына РАН (Москва, Россия, 2012-2013 гг.).
Публикации. По теме диссертации опубликовано 9 научных работ, в том числе 4 из них в рекомендуемых ВАК РФ научных журналах и 1 патент на полезную модель.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, приложения, списка литературы, включающего 76 наименований. Основное содержание работы изложено на 94 страницах машинописного текста. Работа содержит 5 таблиц и 27 рисунков.
Методы многостанционного доступа и способы предоставления ресурса, используемые в VSAT-сетях спутниковой связи
Таким образом, предположение о постоянстве числа пользователей в среднем и статическое разделение канала на частотные подканалы является неэффективным решением с позиции степени использования ресурса, так как большую часть времени каналы связи простаивают.
При множественном доступе с разделением во времени (протокол TDMA) на основе самого низкоскоростного (опорного) сигнала сети формируется временной кадр, включающий одно временное окно для этого сигнала и временные окна для всех оставшихся сигналов в пропорции, равной отношению их скоростей к скорости опорного сигнала. В своей простейшей форме время кадра Тт №а, является достаточно большим, чтобы содержать хотя бы по одному временному интервалу (окну), выделенному каждой станции. При этом длительность интервалов, выделенных каждой станции, в общем случае может быть различной, а часть временных окон должна быть задействована для выполнения сервисных функций.
Протокол передачи при фиксированном распределении времени доступа заключается в том, что на каждой УбТІТ-станции известны моменты появления выделенных ей временных интервалов по отношению к единому времени (наличие цикловой синхронизации) и она передает в эти временные интервалы любые ожидающие своей очереди пакеты. Каждая станция постоянно контролирует спутниковый канал «вниз», проверяя каждый получаемый пакет, чтобы определить, ей ли он адресован. Если да, то станция доставляет пакет своему пользователю, в противном случае пакет сбрасывается.
В основе кодового многостанционного доступа (протокол CDMA) лежат различающиеся по форме сигналы, которые могут передаваться одновременно во времени и иметь перекрывающиеся частотные спектры, но, тем не менее, их разделение на приемной стороне возможно при выполнении для них условий ортогональности. В системах многостанционного доступа с кодовым разделением радиосигналов (МДКР) переносчиками информации являются широкополосные сигналы сложной формы, имеющие для каждой земной станции индивидуальную кодовую структуру. Широкое применение в КССС с МДКР находят бинарные коды на основе последовательностей Уолша и М-последовательностей, что обусловлено их хорошими авто- и взаимнокор-реляционными свойствами. При внутриимпульсной фазовой манипуляции псевдослучайной последовательностью (ПСП) несущего колебания формируется система ортогональных ФМ ШПС радиосигналов, а при манипуляции ПСП частоты несущего колебания формируется ансамбль сигналов с псевдослучайной перестройкой рабочих частот (ППРЧ).
Многостанционный доступ с кодовым разделением радиосигналов (CDMA) объединяет достоинства и недостатки методов МДЧР (FDMA) и МДВР (TDMA). однако обладает наличием дополнительных помех неортогональности, высокой чувствительностью к неравенству мощностей радиосигналов на входе ретранслятора, что несколько снижает допустимое число станций, обслуживаемых в сети спутниковой связи с МДКР с требуемой достоверностью приема, по сравнению с другими методами фиксированного закрепления ресурса.
Если трафик пользователей носит случайный характер, то применение МД с фиксированным закреплением ресурса становится неэффективным за счет резкого снижения степени использования ресурса ретранслятора и растущей с увеличением числа ЗС задержки в обслуживании [7, 20, 75). Поэтому при построении сетей VSAT, где загрузка каналов, как правило, невелика, а нагрузка может иметь импульсный (пачечный) характер, применяются статистические (динамические) методы предоставления каналов отдельным пользователям [16, 20, 24, 27].
Методы статистического (динамического) предоставления ресурса
1. Протоколы случайного многостанционного доступа ALOHA [20, 59, 75] «Чистая» ALOHA.
Идея «чистой» ALOHA заключается в возможности любого пользователя в случайный момент генерации им сообщения воспользоваться общим ресурсом ретранслятора (каналом связи) для его передачи. Полная доступность к ресурс} ретранслятора и асинхронность работы всех станций сети порождает возможность столкновений (коллизий) их радиосигналов в общем канале связи. Благодаря тому, что в канале связи пользователь имеет обратную связь, имеется информация о возникновении столкновения при передаче своего радиосигнала. Эта обратная связь в геостационарных системах спутниковой связи происходит с задержкой около 250 мс.
Обнаружив конфликт, пользователь ожидает некоторый случайный отрезок времени, после чего повторяет попытку. Ожидание должно быть случайным, иначе конкуренты будут повторять попытки в одно и то же время, что приведет к блокировке работы сети. Системы массового обслуживания подобного типа, где пользователи конкурируют за получение общего канала, называются системами с состязаниями.
Если произошел конфликт, т. е. бит пакета одной станции случайным образом наложился на бит пакета другой станции, оба пакета считаются испорченными и должны быть переданы повторно. Неопределенность времени обнаружения конфликта в «чистой» ALOHA может составлять удвоенное время передачи сообщения. Как будет показано ниже, максимальная реализуемая пропускная способность в «чистой» ALOHA (P-ALOHA) составляет лишь 18,4% от потенциальной.
Слотированная ALOHA (S-ALOHA) является модификацией «чистой» ALOHA. При способе S-ALOHA все время кадра разделяют на слоты - отрезки времени, необходимые для передачи одного сообщения (пакета), а сама передача радиосигналов каждой станции осуществляется синхронно с временем слота. Поскольку передачу теперь можно начинать не в любой момент времени, а только в момент начала слота, то время на обнаружение коллизии и число возможных столкновений заявок на единице ресурса сокращается вдвое по сравнению с «чистой» ALOHA. Каждая несущая передается в форме пакета с длительностью, равной слоту времени. Синхрониза ция между К5ЛГ-станциями осуществляется сигналами, передаваемыми центральной либо опорной станцией, а степень использования пропускной способности при протоколе S-ALOHA в два раза выше по сравнению с P-ALOHA и может достигать 36,8%.
В целом статистические методы многостанционого доступа на основе случайного доступа ALOHA и их синхронных модификаций имеют высокую эффективность лишь при относительно низких значениях нагрузки, а их основной недостаток связан с потерей устойчивости процесса обслуживания в условиях значительных флуктуации нагрузки пользователей и ухудшении условий связи.
Протоколы МД, в которых выделение ресурса ретранслятора по заявкам (запросам) пользователей КССС откладывается и может быть реализовано лишь в определенные периоды времени, называются протоколами с резервированием. Среди протоколов с резервированием в настоящее время выделяют следующие [20, 59, 75]: ALOHA с резервированием, PODA, RRR, FIFOR.
Достоинства и недостатки методов многостанционного доступа с динамическим предоставлением ресурса по требованиям
Протокол ALOHA с резервированием является децентрализованным синхронным протоколом предоставления ресурсов ретранслятора по требованиям пользователей с внутренним резервированием ресурса (слота временного кадра, частотного канала в полосе ретрансляции и т. д.). Протокол ориентирован на коммутацию каналов и предназначен для обслуживания многопакетных сообщений. Процесс доступа включает обнаружение в текущем кадре свободного j-ro слота и заполнение его первым пакетом сообщения. Если в следующем кадре на этом слоте не возникло столкновений, то он используется для передачи остальных пакетов сообщения. При возникновении коллизии попытка занять слот повторяется. Число слотов в кадре должно быть не меньше числа ЗС. Длительность кадра должна быть не меньше времени распространения сигнала до самой удаленной ЗС так, чтобы до занятия слота на текущем кадре у ЗС была информация о состоянии слота на предыдущем кадре. В текущем кадре j-w. слот доступен для занятия, если на предыдущем кадре он находился в состояниях «свободен», «конфликт» либо в нем передавался последний пакет сообщения.
Достоинством ALOHA с резервированием является его способность обслуживать мультисервисный трафик с разным числом пакетов в сообщении. Недостатками этого протокола являются большие задержки, вызванные использованием коммутации канала, а не сообщения; трудность поддержки интерактивного обмена из-за большой длительности кадра Тк траспр , что приводит к задержкам в ответе TV 2траспр. Данный протокол в децентрализованном варианте лег в основу алгоритма предоставления ресурса в стволах с радио-АТС ретранслятора «Глобус-1» ЕССС-2.
Принципы построения автоматизированной подсистемы управления VSAT-сети спутниковой связи
Рассмотрим математическое представление процессов изменения состояния объекта управления - системы распределения ресурса ретранслятора и общие принципы решения сформулированной в п. 1.4 задачи управления порогами резервирования при обслуживании многоприоритетных потоков заявок пользователей.
В настоящее время для описания потоков требований часто используют модели временных рядов: линейной регрессии; авторегрессии; смешанную модель авторегрессии и скользящего среднего (АРСС(р, q))\ авторегрессии проинтегрированного скользящего среднего (АРПСС(р,d,p)) [17, 23, 28, 31, 44, 49, 55, 61, 71].
Достаточно общая модель временного ряда х(к) (последовательности значений интенсивности потока требований) может быть представлена как результат действия определенного механизма обработки предшествующих членов ряда и некоторого числа членов возбуждающей белой последовательности, т. е. в виде смешанной модели авторегрессии и скользящего среднего [36, 59]: V V х(к) = - 53 агх{к - і) + ]Г 6 Ф - г ), (2.1) i=i t =i где аг,Ьг - параметры авторегрессии и скользящего среднего, оцениваемые по вре менному ряду на основе методов математической статистики; є (к)- случайная белая гауссовская последовательность независимых величин с нулевым математическим ожиданием, дельта-функцией корреляции и известной дисперсией.
Если 9 = 0, Ь(0) = 1, то уравнение описывает модель авторегрессии, которая интерпретируется как механизм, генерирующий временной ряд, в котором наблюдение переменной х(к) в некоторый момент к выражается через систематическую зависимость от той же самой переменной в р моментах времени, непосредственно предшествующих к моменту плюс значение случайного возмущения е(/с) в момент к.
Непараметрический уровень задания вероятностных характеристик ряда и трудность получения оценок коэффициентов авторегрессии и скользящего среднего, а также дисперсии шума возбуждения в модели АРССС (p,q), основанные на решении уравнения Юла-Уолкера, либо рекуррентного алгоритма наименьших квадратов (РНК) делает практическое использование этого класса моделей весьма проблематичным [44, 59].
Поэтому далее будем опираться на частный случай модели временного ряда — параметрические марковские модели [5, 32, 50, 53, 66] потоков требований, что потребует параметрического уровня априорных данных, но позволит значительно уменьшить временные затраты на процесс оценивания.
Пусть дискретному множеству состояний входящего потока требований хгг(к) Є Xr,i = 1,1 (числу заявок одного приоритета \Т1(к) = хп(к), поступивших за интервал времени Т = const) в дискретные моменты времени к Є {1,..., К}, кТ — Ьк и состоянию занятости ресурса ретранслятора обслуживанием требований соответствует конечное множество управлений us(k) Є U, s = 1,5 (решений относительно числа резервируемых в интересах каждого приоритета каналов и соответствующих им значений порогов резервирования).
Простейшей моделью такой управляемой случайной последовательности - входящего потока требований одного приоритета, является однородная управляемая цепь Маркова [5, 32, 53], которая задается вектором вероятностей начальных состояний процесса Р(0) = {рг(0)},г = 1,1, (2.13) матрицей одношаговых переходных вероятностей Г»(к/к - 1) = {pl (k/k - 1)},г = TJ,j = Ї7Т, (2.2) множеством возможных управлений U = {иДй:)}, а также неизменным периодом смены состояния Т = tk — tk-\.
Для эргодических цепей Маркова вероятности состояния на к-м шаге определяются уравнением Маркова, а пошаговые значения матрицы одношаговых переходных вероятностей уравнением Колмогорова-Чепмена [8, 66] и быстро устанавливаются, стремясь к так называемым «финальным» вероятностям.
По аналогии с непрерывнозначными последовательностями [53] для случая цепи Маркова х(к) = хг{к) = Ст6(к) вероятностно-временной механизм смены ее состоя ний описывается следующим разностным стохастическим уравнением [5, 35]: х{к + 1) = [РиТ{к + 1/кЩк)]тС + Тх{к + l)v(fc),
Формирующий фильтр зашумленной цепи Маркова Таким образом, предложенная модель потока требований на основе УЦМ поз воляет в отличие от классических вероятностных моделей [16, 22, 24, 27] учесть динамику и переходной процесс изменения состояния нагрузки, а для установившихся состояний УЦМ использовать апробированный для стационарных потоков требований традиционный аппарат анализа вероятностно-временных характеристик качества обслуживания нагрузки. В то же время запись модели в терминах теории переменных состояния (в виде стохастических разностных уравнений состояния) делает возможным последующее применение к исследованию процессов обслуживания требований в КССС современного математического аппарата теории стохастического оптимального управления (методов теории стохастического оценивания и динамического программирования).
2.2 Принцип разделения и сущность этапов разработки алгоритма текущей оценки интенсивности входящего потока требований, оптимального в смысле МСКО и алгоритма управления при за-шумленных наблюдениях за состоянием нагрузки на основе метода динамического программирования
В многочисленных работах [53, 59, 66), рассматривающих случаи оптимизации управлений в условиях параметрической априорной неопределенности, показывается асимптотическая эффективность принципа разделения, в соответствии с которым процесс оптимизации решений выполняется в два взаимосвязанных этапа: стохастического оптимального оценивания состояния объекта управления х(к) = M{x(k)/z(k)} на основе алгоритмов, оптимальных в смысле минимума средне-квадратической ошибки оценивания (МСКО) либо максимума апостериорной вероятности значений процесса; оптимизации детерминированных управляющих воздействий (решений) на основе полученных на первом этапе оценочных значений переменных состояния объекта на основе итерационного алгоритма Ховарда, методов линейного и динамического программирования [8, 36, 53, 72].
Рассмотрим сущность обоих этапов применительно к задаче управления порогами резервирования ресурса ретранслятора. Так как параметры трафика пользователей, задержки, очереди, помеховой обстановки и т.д. передаются по каналам ТУ-ТС с помехами и случайно изменяются во времени, то для поддержания заданного качества обслуживания заявок пользователей необходимо осуществлять текущую фильтрацию и краткосрочный прогноз параметров состояния сети с целью предотвращения устаревания данных.
Для решения задачи текущей оценки и прогноза величины нагрузки от пользователей различных приоритетов рассмотрим обобщение алгоритма фильтрации, оптимального в смысле минимума среднеквадратической ошибки (МСКО) [53], на случай оценки состояния зашумленной цепи Маркова (2.5, 2.6).
Можно показать, что для принятой модели состояния и наблюдения (2.5, 2.6) текущая оценка состояния процесса х(к) может быть найдена на основе следующего рекуррентного алгоритма [36, 38]:
Принцип разделения и сущность этапов разработки алгоритма текущей оценки интенсивности входящего потока требований, оптимального в смысле МСКО и алгоритма управления при зашумленных наблюдениях за состоянием нагрузки на основе метода динамического программирования
Теперь рассмотрим как именно должны выбираться Дь чтобы повысить эффективность работы алгоритма. Одно ограничение уже получено выше на основании здравого смысла: А! не должно быть настолько большим, чтобы выражение в (3.7) принимало отрицательные значения, однако одно это условие довольно слабое, т.к. всё равно ведёт к линейному росту вариантов с увеличением Vs.
Как показывают многочисленные расчёты и примеры решения задач оптимизации порогов резервирования с разными параметрами и исходными данными, функция Р бсл. і А + тахд.2 .._дя (Р0"сл г" + X)f=2 Рбс г zA является невыпуклой по переменной Ді, однако аналитического доказательства её невыпуклости пока получить не удаётся из-за сложной рекуррентной структуры функции и зависимости от Ді отстаточной нагрузки { , которая, в свою очередь, влияет на вероятность обслуживания заявок второго приоритета. И хотя, безусловно, строгое доказательство необходимо для последующего применения в улучшении работы алгоритма свойств невыпуклой целевой функции, оно, видимо, представляет собой отдельную сложную математическую проблему и выходит за рамки данной работы, поэтому далее ограничимся лишь предположением о невыпуклости данной функции,
Очевидно, что при невыпуклости по переменной Ді функция (Робел, %1 + Ylr=2 -Робел, г zr) имеет единственный (с точностью до эквивалентности) максимум. При этом перебор Ді можно производить, например, методом дихотомии.
Таким образом, на каждом шаге рекурсии производится перебор порядка lnVg вариантов, а общая сложность алгоритма составляет 0{R lnVs). Поскольку, как правило, на практике R — количество приоритетов — не слишком велико, a Vj; — количество единиц ресурса наоборот, может достигать больших значений, данная асимптотическая оценка является очень хорошей при решении реальных задач оптимизации порогов резервирования.
Полученный алгоритм стал предметом заявки на полезную модель, по которой автором получен патент РФ [40]. Существенное снижение вычислительных затрат на программно-аппаратную реализацию разработанного алгоритма может быть обеспечено за счет распараллеливания ряда операций [73] и использования перспективной вычислительной базы [57].
Разработка итерационного алгоритма оптимизации порогов резервирования ресурса ретранслятора при обслуживании многоприоритетного потока требований пользователей
Точный аналитический метод решения задачи оптимизации плана распределения ресурса ретранслятора рассмотрен в п.3.1. В тоже время, наличие априорной неонре деленности относительно параметров марковских моделей потоков требований, высокая размерность решаемой задачи с учетом необходимости сохранения промежуточных результатов пошаговой оптимизации плана распределения ресурсов ретранслятора для потоков заявок различного приоритета делает проблематичным массовую реализацию данных алгоритмов при ограниченных возможностях вычислительной базы ретрансляторов, используемых в настоящее время.
В связи с этим возникает проблема разработки численных, но легко реализуемых алгоритмов оптимизации числа резервных каналов и порогов резервирования для заявок различного приоритета, удовлетворяющих критерию (2.12). Переход от задачи (2.12) к упрощенному ее варианту связан с допущениями о наличии интервалов квазистационарности (сохранения постоянства значений) состояния потоков требований (сопоставимых со средним временем занятия) и ресурса ретранслятора, а также возможности реализации всех процедур управления планом распределения ресурсов в интервал времени не более нескольких секунд.
Рассмотрим особенности приближенного решения задачи одним из численных методов [4, 11, 74]. Один из вариантов такого алгоритма представлен на рисунке 3.1. Суть предлагаемого алгоритма заключается в замене общей многопараметрической задачи оптимизации плана распределения ресурса ретранслятора на последовательность однопараметрических задач (по каждому из приоритетных потоков заявок), решаемых при фиксированных значениях ранее полученных параметров плана. Основным содержанием работы алгоритма является организация итерационного процесса перераспределения общего имеющегося числа единиц ресурса ретранслятора Vj; на минимально-необходимые объемы Аг(к), резервируемые для высокоприоритетных потоков требований с целью обеспечения выполнения заданных априори требований к качеству их обслуживания, а также определения значений зон доступности к ресурсу dr(k) для потоков заявок низшего приоритета, обеспечивающих максимизацию коэффициента обслуженности суммарной нагрузки на ресурс ретранслятора Kn,(k.dr,Ar) . Соответствующие максимуму коэффициента обслуженности значения объемов резервирования и зон доступности (d , Д ) формируют искомый оптимальный план распределения ресурсов ретранслятора. Необходимость проведения нескольких этапов итераций в ходе оптимизации плана распределения ресурсов ретранслятора при наличии на входе ретранслятора потоков требований с тремя и более приоритетами обусловлена необходимостью уточнения на каждом из этапов итерации параметров плана распределения ресурсов для потока заявок каждого приоритета с учетом ранее выделенных ресурсов для обслуживания других приоритетных потоков заявок.
Разработка итерационного алгоритма оптимизации порогов резервирования ресурса ретранслятора при обслуживании многоприоритетного потока требований пользователей
В соответствии с методикой и алгоритмом векторного анализа эффективности, рассмотренных в п.2.3. определим класс КССС, число сравниваемых вариантов построения системы распределения ресурса ретранслятора, а также обоснуем вектор показателей эффективности функционирования КССС и метод его оценки.
Пусть VSAT-сеть типа «звезда» состоит из одной центральной и N абонентских станций, генерирующих два потока заявок на ресурс ретранслятора первый из которых является приоритетным. Поток пакетов (заявок) каждого приоритета на входе системы распределения ресурса ретранслятора описывается нуассоновским процессом с интенсивностью А (пакетов (заявок) в секунду) и средним объемом пакета L бит (либо средним временем занятия ресурса Тгш). Максимальная скорость передачи данных по выделенному каналу (пропускная способность единицы ресурса) составляет Дк.
Представляет интерес сравнение эффективностей функционирования КССС для трех возможных алгоритмов и соответствующих им планов, используемых в системе распределения ресурсов ретранслятора:
1. Полнодоступной (бесприоритетной) схемы распределения ресурса ретранслятора, использующей алгоритм «синхронная ALOHA».
2. Алгоритма распределения ресурсов с использованием абсолютного приоритета на ресурс ретранслятора заявок высокоприоритетного потока и прерыванием обслуживания низкоприоритетных заявок при появлении высокоприоритетных.
3. Разработанного итеративного алгоритма оптимизации порогов резервирования единиц ресурса ретранслятора для заявок высокоприоритетных пользователей, обеспечивающего максимум коэффициента обслуживания суммарной нагрузки от пользователей.
В соответствии с [9, 11, 54] для соблюдения свойства полноты вектора показателей качества при выполнении требований к его минимальной размерности и коррелированное компонентов целесообразно ограничить его состав следующими частными показателями качества:
Средним временем обслуживания (задержки) заявки пользователя на ресурс ретранслятора (согласно п. 1.3.) Т = Ts ALOHA = Тр + р + (eG - 1) (гр + T-f + тпп ) ; (3.17) 7г = Гр + тпп; Тз = Тр + тпп; где Тр 0, 26с - время распространения сигнала в спутниковом канале между ЗС-РС-ЗС; тпп - среднее время передачи пакета (заявки); G - общее число пакетов (заявок), подлежащих передаче, учитывающее число повторных вызывов; К - интервал повторных передач. Времена задержки Т2, Г3 для второго и третьего алгоритмов распределения ресурса определены для заявок первого приоритета, обслуживание которых осуществляется без столкновений на ресурсе. Так как качество обслуживания заявок низших приоритетов не нормируется, то значение времен задержек для них не влияет на оценку эффективности КССС. алгоритмов распределения ресурсов ретранслятора будет сохраняться неизменным, а меняются лишь значения соответствующих вероятностей обслуживания заявок различных приоритетов Р0бСЛг 3. Вероятностью ошибки передачи одного бита информации Рош.
Общими затратами радиоресурсов ретранслятора Vv , выделяемыми для обслуживания суммарного потока требований пользователей в КССС.
С целью сокращения размерности векторного показателя эффективности функционирования КССС два последних показателя целесообразно вывести в разряд ограничений, а дальнейший анализ провести по первым двум показателям Т и К0(к), так как требования по достоверности передачи сообщений Рош и затраты ресурса ретранслятора VE в КССС должны выполняться всегда и одинаковы для всех режимов работы системы распределения ресурсов а, следовательно, при их выполнении не влияют на сравнительную оценку эффективности но остальным показателям.
В качестве метода векторной оценки эффективности функционирования КССС согласно выводам, сделанным в п.2.3, целесообразно использовать метод идеальной (утопической) точки, предполагающий выполнение этапов: нормирования (приведение к одной точке отсчета и одинаковой размерности) вектора показателей качества КССС и его скаляризации на основе введения евклидовой метрики обобщенный (скалярный), частный и «идеальный» показатели эффективности функционирования КССС, Y вектор показателей качества КССС; х — вектор параметров КССС; д=1,2,... — степень целевой функции.
В таблице 3.1, полученной по результатам п.1.3.(TV = 30; Vs = 16; тпп = 0, 2с; Тр = 0,26с), представлены зависимости среднего времени задержки передачи пакета (обслуживания заявки) для различных алгоритмов распределения ресурса ретранслятора при изменении степени загрузки ретранслятора р — д, .т"".
