Автоматика и телемеханика, № 5, 2014
© 2014 г. Ю.В. СОЛОДЯННИКОВ, д-р техн. наук (solo-dialog@mail.ru) (ЗАО "Самара-Диалог", Самара)
УПРАВЛЕНИЕ И НАБЛЮДЕНИЕ ДЛЯ ДИНАМИЧЕСКИХ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ. II1
Изучается задача оптимального управления в сети массового обслуживания в условиях неполных данных. Методом динамического программирования решается задача оптимального управления состоянием сети и наблюдениями. Дается методика ответа на вопросы: что, где, когда и как проводить сетевые измерения(сетеметрию) при решении задач динамической маршрутизации. Определены общие понятия и методы теории сетеметрии. Приводятся примеры решения задач совместного оптимального управления и наблюдения для элементарных сетевых структур и современных систем телекоммуникаций.
1. Введение
Эта статья представляет собой вторую часть общей работы, посвященной решению задачи оптимального управления и наблюдения в системах (СМО) и сетях (СеМО) массового обслуживания. В первой части [1] были рассмотрены математические методы синтеза оптимальных управлений в СМО и СеМО по полным данным, т.е. в предположении, что вектор состояния системы точно известен в каждый момент времени. Основным методом исследования выбран классический математический аппарат динамического программирования.
В представляемой второй части эта же задача рассматривается в условиях неполноты данных. Предполагается, что вектор состояния системы доступен для наблюдения не в каждый момент времени: либо наблюдения запаздывают по времени, либо имеются помехи. При этом ставится и решается задача построения стратегии совместного управления сетевыми состоянием и наблюдениями путем ответа на вопросы: что, где, когда и как измерять на сети при динамической маршрутизации. Основные результаты в более сжатой форме были изложены ранее в [2-4].
В условиях неполноты данных свойство марковости управляемой системы, вообще говоря, не выполняется. Этот факт вносит дополнительные сложности в постановку и решение задач оптимального управления и наблюдения. В этих условиях видятся три возможных пути решения таких задач. Первый путь состоит в построении в некотором смысле оптимальных децентрализованных структур управления и наблюдения в сети, обеспечивающих полноту данных и сохраняющих марковость управляемых процессов. Второй путь состоит в применении "жидкостной" модели объекта. И, наконец, третий путь
1 Работа поддержана ЗАО "Самара-Диалог".
связан с использованием методов стохастического анализа, нелинейной фильтрации и аппарата скрытых марковских моделей [5] и мартингального подхода [2].
Вторая часть работы состоит из введения, пяти основных разделов и заключения. Раздел 2 посвящен общим теоретическим вопросам организации управления и наблюдения для СМО и СеМО. Здесь определяются основные понятия и методы теории сетеметрии, в частности понятие сетевой информационной структуры.
Раздел 3 посвящен примерам решения задачи синтеза сетевой информационной структуры с минимальным количеством наблюдений, обеспечивающей оптимальное управление состоянием по полным данным для элементарных сетевых структур — тандема и роутера.
В разделе 4 приведены примеры синтеза информационных структур, обеспечивающих оптимальное управление состоянием по полным данным, для сложных сетевых структур. В телекоммуникационной системе мобильной связи с хендовером заявок синтезируется централизованная информационная структура.
В разделе 5 приводится пример "жидкостной" модели СеМО с шумом в измерении состояний. Модель в описании объекта ограничивается конечным числом независимых переменных и приводит к значительно более обозримому уравнению Беллмана конечной размерности и возможностью явного решения.
В разделе 6 рассмотрен еще один практический пример постановки и решения задачи совместного оптимального управления и наблюдения. В качестве объекта исследования взята СМО с потерями и управлением наблюдением за процессом потерь, возникающих при переполнении очереди. Для решения используются методы стохастического анализа и нелинейной фильтрации.
2. Общие вопросы управления и наблюдения на сети
2.1. Обозначения и сокращения
Будем использовать в дальнейшем изложении следующие обозначения: СВ — случайная величина;
(О, Р} — ассоциированное с сетью вероятностное пространство;
| А | — мощность множества А, для конечного множества — число его элементов;
= Ах ... хА — ?г-кратное прямое произведение множества А;
п
^ — счетное множество целых чисел;
= (0,1, • • • } — счетное множество неотрицательных целых чисел;
ZN = (0,1, • • • , N} — конечное множество неотрицательных целых чисел от 0 до N;
1(А) = ^ — индикаторная функция множества А, а индикатор-
ную функцию 1(х) от числового аргумента х определим через индикаторную функцию множества как 1({х > 0});
/(*) © д&) = /о /(* - У)д(у)Лу — свертка функций /(у) и д(у); /*(в) = [/(у)]* = Г е-вУ/(У)^У — преобразование Лапласа функции /(у); (•, ■) — символ скалярного произведения.
2.2. Сетевая информационная структура
Рассмотрим некоторые общие теоретические вопросы организации управления и наблюдения для СМО и СеМО. Пусть имеется сеть из N узлов. Сетевая информационная структура (ИС) Z — множество {ъ\,..., гдг} вектор-функций Хг = щ(у\,..., у™, т), г = 1, N от результатов измерений каких-либо величин у3(и, X, г)), ] = 1, т в узлах сети, т — вектор запаздываний в доставке информации в г-й узел из других узлов. Управление в г-м узле является функцией от г^: « = «¿(г^).
Приведем своеобразную классификацию сетевых ИС. Будем различать сильную (классическую) г* = {2(5), в < ¿}, со скользящей памятью г*(Д) = = {г(в),£ — Д < в ^ ¿} и слабую ИС; централизованную, централизованно-децентрализованную, децентрализованную, распределенную и иерархическую ИС; частично упорядоченную, статическую и динамическую ИС; ИС с последовательной декомпозицией, с п-шаговым запаздывающим разделением.
Централизованная ИС задает поступление всех измерений г в центральный узел, где формируются управления щ = «¿(г) по каждому узлу, которые рассылаются этим узлам. Централизованная ИС имеет вид Zc = = {г1,...,г^}, т^ — время доставки в центральный узел информации из ^-го узла. Если каждый узел сам получает информацию от всех других узлов, то имеем частично централизованную ИС.
В децентрализованной ИС каждый узел г собирает информацию лишь от множества Г (г) соседних с ним узлов (либо от узлов некоторого более широкого окружающего региона Г(г)) и формирует управление щ. В частном случае децентрализованной ИС г й узел имеет лишь информацию о собственном состоянии.
Распределенная ИС характеризуется тем, что информация для управления в узле формируется всеми узлами сети на основе нескольких серий (итераций) обменов и промежуточных вычислений.
Отличительной особенностью иерархической сетевой ИС является наличие подчиненности между узлами в формировании и использовании необходимой для управления информации.
Будем говорить, что информация г^- вложена в С г^), если существует измеримая функция /^ : г^- = /^ (г^) (зная г^, можно узнать г^-). Пусть обозначение j{г} означает, что узел г в момент принятия решения имеет информацию, которую имеет узел j в момент принятия своего решения. Говорят, что сеть имеет частично упорядоченную ИС, если из j{г} следует г^ С г^. ИС называется статической, если г = г(Х, п), и динамической, если г = г(Х, и, п).
2.3. Общая постановка .задачи оптимизации управления и наблюдения на сети
При реализации адаптивных алгоритмов в СеМО желательно организовывать измерения таким образом, чтобы, во-первых, точность определения требуемых параметров была максимальной и не ниже заданной; во-вторых, суммарная длительность или стоимость наблюдений и их количество были минимальными; в-третьих, чтобы оперативность получения результатов наблюдений была достаточно высокой и обоснованной. Выполнение этих условий позволяет сократить накладные расходы, повысить пропускную способность сети и другие показатели эффективности ее функционирования.
Модель сети очередей [2] представляется стохастическими управляемыми по неполным данным функционально-дифференциальными уравнениями состояния с мерами обобщенных рекуррентных (иначе, точечных, мультива-риантных точечных, маркированных точечных) процессов. Это представление дается на вероятностном пространстве (О, З, Р) с потоком ст-алгебр З = = {ЗгЬ^о в условиях существования единственного слабого решения уравнения состояния, а также управления состоянием и(-) и управления наблюдением г(-) в следующем виде:
(1) (2)
(3)
dXt = В(*, г*)^^*^ + г^^СТ^, г*))), (в) =
у(в) = Н(в, X(в, Т), и1, п(0) + СТ2(в)),
2/1 (в) = Ф(п(в))
Т
. (и, г) = Еи
Ф(Т, ит,Ут) + У ЦХ4, щ, гt)dt
— шт,
ил
где X, п, С, т, и1, и2,г — соответственно векторы состояния (длин очередей), внешних потоков сообщений, ошибок измерений, запаздываний в доставке измерительной информации, управления состояниями(маршрутные переменные), ограничения нагрузки, управления наблюдениями, и = [и1,и2]»; В(-) — случайная матричная функция, задающая переменную структуру связей в сети; — сетевая ИС; Н(■) и Ф(-) — случайные матричные функции, описывающие состав проводимых измерений состояний у(-) и входящих потоков У1(-), » — знак транспонирования. Множество моментов времени наблюдений является множеством из борелевской ст — алгебры на [0, ¿) € ©[о,*), в частности = [0, ¿)), .(и, г) — функционал потерь(состоит из суммы терминальной и интегральной частей).
2.4. Принцип разделения
Теорема разделения (ТР), или принцип разделения (ПР), в теории управления устанавливает условия, при которых задачу управления по неполным данным можно свести к двум независимым задачам — фильтрации (оценивания) и управления по полным данным. Принцип разделения обнаруживает естественную связь со свойствами достаточных статистик. Обзор ТР можно найти в [6], применительно к сетевым задачам управления — в [7].
г
г
Как отмечалось выше, имеется большое разнообразие сетевых ИС. Ряд их особенностей нашел свое отражение в известных ТР, в частности, децентрализованное управление. Как правило, эти особенности исследуются в рамках л
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.