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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Аннотация

В данном документе содержится описание программного комплекса "Комплексная имитационно-функциональная модель управления информационными потоками в многоспутниковой низкоорбитальной сетевой системе на основе диффузионной аппроксимации", предназначенного для моделирования вектора состояний многоспутниковой низкоорбитальной сетевой системы (МНСС) в каждый момент времени.

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

Программный комплекс позволяет оценивать следующие показатели качества:

измерение интенсивности потоков пакетов, входящих в узел сети, выходящих из общей очереди;

расчет загруженности узлов сети в требуемые моменты времени;

расчет оптимальных путей для пакетов.

При этом разработка имитационной модели позволяет:

обеспечивать прохождение пакета высокого приоритета по самому короткому пути, а пакетов низкого приоритета по путям, обеспечивающим минимальную загрузку;

прогнозировать задержку пакета на пути от источника до получателя и в случае необходимости корректировать маршрут пакета;

адаптироваться при выборе маршрута к изменениям структуры и связанности МНСС.

Функциональное назначение программы, область применения, ее ограничения

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

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

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

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

Основными показателями качества функционирования сетевой системы на сетевом уровне взаимодействия открытых систем являются среднее время доставки сообщения (для сообщений высших приоритетов) и производительности сети (для сообщений низших приоритетов).

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

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

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

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

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

Программный комплекс "Комплексная имитационно-функциональная модель управления информационными потоками в многоспутниковой низкоорбитальной сетевой системе на основе диффузионной аппроксимации", предназначен для моделирования процессов прохождения информации в МНСС и определения основных показателей качества функционирования таких систем.

Программный комплекс позволяет осуществлять:

определение целевых функций и решение задачи управления информационным обменом;

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

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

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

где ?- "полезная" производительность, которую определим как объем переданных пользователями НСС сообщений всех приоритетов (в пакетах), обслуженных сетью полностью и с заданным качеством за единичный интервал времени, здесь К - количество приоритетов сообщений;

?- объем сообщений всех приоритетов, передача которых по различным причинам (ошибочный прием пакета, отказ в постановке в очередь и другим) была повторена в межузловых каналах передачи данных в единицу времени;

? - объем служебных сообщений, передаваемых в единицу времени в НСС в полях управления сетью и реализации адаптивного алгоритма маршрутизации.

При заданной интенсивности входящего в НСС потока полезная производительность сети по каждому виду информации, передаваемой с некоторым r-ым приоритетом, является функцией интенсивности входного потока, где - элементы матрицы интенсивностей потоков пакетов между абонентами сети.

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

где - средняя задержка, переданный и необходимый для передачи МСС объем сообщений высокого приоритета в единицу времени;

где - реальная и максимально допустимая средняя задержка и объем сообщений низких приоритетов, переданных НСС в единицу времени.

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

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

Анализ особенностей рассмотренных алгоритмов маршрутизации, в том числе используемых в настоящее время в наземных СПД и пакетных радиосетях, показал целесообразность использования в НСС алгоритмов маршрутизации информационных потоков, отвечающих следующим требованиям:

1. Децентрализованности управления, когда решения по выбору маршрутов принимаются в каждом узле самостоятельно. Централизованное управление имеет серьезные недостатки, не позволяющие использовать этот метод в НСС, а именно служебная информация о состоянии сети, передаваемая к центральному узлу, и управляющая информация от него к узлам сети создают значительный дополнительный трафик в сети; низкая надежность системы управления: наличие центрального управляющего узла может привести к потере управления маршрутизацией в сети, например, при отказе центрального узла или при изоляции от него участка сети. Таким образом, повышенные требования к живучести НСС и надежности передачи информации обусловливают необходимость использования в рассматриваемой сети децентрализованного управления информационными потоками.

Представим рассматриваемую НСС в виде неориентированного графа , где - множество вершин графа (соответствующих спутникам-«узлам» МСС), пронумерованных в некоторой последовательности; -множество ветвей (дуг) графа. Пропускные способности дуг графа - каналов передачи данных НСС, - одинаковы, т.е. .

Пусть - s-ый маршрут пакетов от i-ого к j-му узлу сети, а - множество всевозможных соответствующих маршрутов. При этом задержка пакета r-ого приоритета, передаваемого по маршруту , определяется как

(1)

где - задержка передачи и обслуживания соответствующего пакета в линии (l, m) с учетом возможных повторов передачи; - задержка пакета в очереди узла

Задачу минимизации среднего времени доставки сообщений высокого приоритета можно сформулировать следующим образом. Считаются заданными: топология НСС, определяемая матрицей расстояний и матрицей связности ; интенсивности входящих в сеть потоков ; надежности каналов передачи данных . Необходимо минимизировать , распределяя оптимальным образом потоки в каналах передачи данных при ограничении

.

Здесь - вероятность повторной передачи пакета в линии (l, m), а - внутренний поток, направляемый в соответствующую линию.

Поскольку особенностью рассматриваемой задачи является то, что интенсивность потоков пакетов высокого приоритета в НСС невысока и объем этих сообщений достаточно мал, для пакетов высокого приоритета целесообразно использовать алгоритм маршрутизации кратчайших путей, когда под длиной маршрута s понимается задержка

, (2)

а кратчайшим считается такой маршрут, для которого выполняется условие

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

(3)

(4)

Пусть и - загрузка пути и канала передачи данных соответственно. Здесь - вероятность повторной передачи пакета в линии (l, m); - доля потока пакетов, направляемая в линию (l, m). Определим, что наилучшим следует считать такой путь w, для которого при выполняется условие

Если , то w является наилучшим путем, когда

.

При этом задержка пакета, определяемая выражением (2), не должна превышать максимально допустимую.

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

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

Рассмотрим диффузионную модель НСС. Обозначим количество пакетов r-ого приоритета в сети вектором

где - количество r-ого приоритета в i-ом узле сети.

Определим вектор «локальных» коэффициентов сноса , элементы которого представляют коэффициенты сноса диффузионного процесса изменения очереди на i-ом участке сети и рассчитываются согласно выражению

(5)

Отметим, что выражение (1.5) определяет «локальный» коэффициент сноса, который рассчитывается на основе интенсивностей входящих в некоторый узел МСС и исходящих из него информационных потоков. Первый момент приращения для многомерного процесса определяется как

,

Плотность вероятности перехода для рассматриваемого многомерного процесса

где - вектор сетевых коэффициентов сноса, элементы которого определяются согласно выражению

(6)

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

(7)

Второй момент приращения для многомерного процесса определяется соотношением

Матрица «сетевых» коэффициентов диффузии

, (8)

элементы которой рассчитываются согласно соотношению

(9)

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

Управление сетью в реальном масштабе времени и аппроксимация процессов сетевого уровня диффузионной моделью требуют определения процедур оценивания параметров потоков пакетов на узлах НСС.

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

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

Следует отметить, что в некоторых случаях при соответствующей нормировке предлагаемый алгоритм основан на полной рассылке всем узлам сетевой информации и состоит из четырех частей: измерение интенсивности потоков пакетов, циркулирующих на узлах сети; распространение служебной информации; расчет загруженности узлов сети в требуемые моменты времени на основе разработанной диффузионной модели сетевого уровня НСС; расчет оптимальных путей для пакетов с использованием алгоритма динамической оптимизации (рисунок 1).

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

Для работы программного комплекса необходимы следующие средства:

IBM PC-совместимые ПК с процессорами Pentium IV или выше;

Microsoft Windows (версии 2000, XP, 2003);

программное обеспечение TURBO PASСAL 7.0.

3. Специальные условия применения и требования организационного, технического и технологического характера

Программный комплекс "Комплексная имитационно-функциональная модель управления информационными потоками в многоспутниковой низкоорбитальной сетевой системе на основе диффузионной аппроксимации", предназначен для специалистов в области радиотехники, телекоммуникаций, систем управления и позволяет оценивать следующие показатели качества:

измерение интенсивности потоков пакетов, входящих в узел сети, выходящих из общей очереди;

расчет загруженности узлов сети в требуемые моменты времени;

расчет оптимальных путей для пакетов.

При этом разработка имитационной модели позволяет:

обеспечивать прохождение пакета высокого приоритета по самому короткому пути, а пакетов низкого приоритета по путям, обеспечивающим минимальную загрузку;

прогнозировать задержку пакета на пути от источника до получателя и в случае необходимости корректировать маршрут пакета;

адаптироваться при выборе маршрута к изменениям структуры и связанности МНСС.

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

4. Условия передачи программной документации или ее продажи

Передача материалов для их использования в каких-либо целях происходит с письменного согласия Санкт-Петербургского государственного университета аэрокосмического приборостроения.

Литература

Многоспутниковые сетевые системы: принципы построения, управления и передачи информации. Сборник научных трудов. - С-Пб: ВИКА, 1988. - 166с.

Бестугин А.Р., Богданова А.Ф., Стогов Г.В. Контроль и диагностирование телекоммуникационных сетей. СПб.: Политехника, 2003г.

Ададуров С.Е., Смирнов В.В. Управление передачей информации в многоспутниковых сетевых системах// Приборостроение, 2001г., с.163-171.

Ададуров С.Е. Пути повышения устойчивого функционирования высокодинамичных спутниковых систем,// Тез. докл. Третья Международная конференция «Экология и развитие Северо-Западного региона Российской Федерации», СПб.5-8 июля 1998г.,Спб: Изд-во: СпбТУ, 1998г., с.71.

Бестугин А.Р., Стогов Г.В.Особенности организации управления потоками сообщений в средне -и высокоскоростных сетях связи. // I Всероссийская научно-техническая конференция «Радиовысотометрия-2004», Сборник трудов, г.Каменск-Уральский, 2004 г., с.307-308.

Размещено на Allbest.ru