Содержание к диссертации
Введение
Глава 1. Обзор основных результатов исследования сетей массового обслуживания с управлением распределением нагрузки 10
1.1. Динамическое распределение нагрузки 10
1.2. Оптимальное распределение нагрузки 15
1.3. Анализ сетей обслуживания с управлением распределением нагрузки 21
Глава 2. Динамическое распределение нагрузки в сетях массового обслуживания 26
2.1. Постановка задачи 27
2.2. Формирование оптимального вектора интенсивностей обслуживания 29
2.3. Выбор базового состояния 33
2.4. Метод динамического управления распределением нагрузки в сети обслуживания 40
2.5. Анализ сетей обслуживания с динамическим управлением распределением нагрузки 44
Глава 3. Динамическое распределение нагрузки между подсетями в сетях массового обслуживания 51
3.1. Постановка задачи 51
3.2. Формирование оптимальной маршрутной матрицы 54
3.3. Алгоритм формирования коррективных маршрутных матриц 60
3.4. Стационарное распределение сети обслуживания 65
Глава 4. Исследование сетей массового обслуживания с управлением распределением нагрузки 75
4.1. Исследование методов динамического управления распределением нагрузки в сети обслуживания 75
4.2. Исследование эффективности метода управления распределением нагрузки в сети обслуживания 81
4.3. Исследование эффективности метода управления распределением нагрузки между подсетями в сети обслуживания 89
Заключение 94
Список литературы 95
- Анализ сетей обслуживания с управлением распределением нагрузки
- Формирование оптимального вектора интенсивностей обслуживания
- Анализ сетей обслуживания с динамическим управлением распределением нагрузки
- Алгоритм формирования коррективных маршрутных матриц
Введение к работе
При проектировании и эксплуатации больших сложных систем с сетевой структурой и стохастическим характером функционирования (БСС), имеющих на современном этапе развития общества широкое распространение и использование, возникает необходимость решения задач анализа, синтеза и оптимизации систем этого класса. Примерами БСС могут служить информационно-вычислительные сети, сети передачи данных, гибкие производственные системы. Использование в системах этого класса развитых подсистем управления со сложными алгоритмами управления существенно повышает уровень требований к используемым при решении задач анализа, синтеза и оптимизации математическим моделям и методам. Практический опыт решения этих задач показал перспективность и эффективность использования сетей массового обслуживания в качестве математических моделей БСС. Это обусловило интенсивное развитие в течение последних четырех десятилетий теории сетей массового обслуживания и методов их анализа и синтеза [3-8, 11, 12, 16-19, 23, 27, 28, 30, 45, 52, 58, 60-62, 67, 69, 82]. Большой вклад в развитие теории, методов анализа, оптимизации и синтеза сетей массового обслуживания внесли А. А. Боровков, Г. П. Башарин, В. М. Вишневский, П. П. Бочаров, В. А. Ивницкий, В. В. Рыков, А. В. Печинкин, В. А. Жожиканшили. Среди зарубежных специалистов необходимо отметить значительный вклад в развитие этого научного направления таких ученых как Дж. Джексон, Л. Клейнрок, Ф. Келли, К. Чэнди, Д. Тауслей, М. Райзер, Дж. Уолрэнд.
Отображение в модельных сетях массового обслуживания средств и методов управления БСС приводит к построению сетей обслуживания с управлением, которые фактически являются подклассом сетей массового обслуживания. Сети обслуживания с управлением обеспечивают не только принципиальную возможность решения целого класса задач анализа и синтеза БСС, но и возможность решения ряда задач, связанных с повышением эффективности управления БСС.
Исследование и разработка методов управления распределением нагрузки в сетях массового обслуживания и методов анализа сетей обслуживания с управлением являются актуальными направлениями развития теории
сетей массового обслуживания. Динамическое распределение нагрузки в сети массового обслуживания (распределение требований между системами обслуживания или подсетями в процессе эволюции сети) существенно влияет на качество ее функционирования. В сети массового обслуживания со случайными длительностями обслуживания требований в системах массового обслуживания, случайными потоками и постоянными маршрутными вероятностями распределение нагрузки является случайным, что делает возможным возникновение в процессе эволюции сети чрезмерных скоплений требований в отдельных системах или подсетях. Такие скопления могут существовать в сети в течение достаточно длительных интервалов времени. Образование таких скоплений приводит к резкому ухудшению временных характеристик сети обслуживания и характеристик использования ресурсов сети. Поэтому проблеме динамического управления распределением нагрузки в сетях массового обслуживания уделяется значительное внимание при рассмотрении как теоретических, так и прикладных аспектов сетей массового обслуживания.
В основу диссертации положены результаты научных исследований, выполненных при участии автора в Саратовском государственном университете по темам, включенным в план НИР СГУ: «Теория и методы управления сетями массового обслуживания» (шифр «Звено», гос. per. № 01960007744), «Синтез сетей массового обслуживания с управлением» (шифр «Такт», гос. per. № 01200001098), «Динамическое управление сетями массового обслуживания» (шифр «Темп», гос. per. № 01200201953), «Анализ сетей массового обслуживания с динамическим управлением» (шифр «Тракт», гос. per. № 01200602692), «Разработка и применение фундаментальных методов исследования задач математического анализа, дифференциальных уравнений, дискретной математики, теории упругости и газодинамики» (шифр «Интеграл», гос. per. № 01200002986).
Целью диссертационной работы является развитие теории сетей массового обслуживания с управлением и методов их анализа, разработка эффективных методов динамического управления распределением нагрузки в сетях массового обслуживания.
Основными задачами, решаемыми в диссертации, являются следующие.
Исследование зависимости эволюции сетей массового обслуживания от их параметров.
Разработка и исследование методов управления распределением нагрузки в сетях массового обслуживания.
Разработка и исследование методов анализа сетей массового обслуживания с управлением распределением нагрузки.
В диссертационной работе использовались результаты теории вероятностей, теории марковских процессов, теории массового обслуживания, теории сетей массового обслуживания.
В диссертационной работе получены следующие основные результаты.
Разработаны методы динамического управления распределением нагрузки в сетях массового обслуживания.
Разработаны методы анализа сетей массового обслуживания с динамическим управлением распределением нагрузки.
Проведено исследование эффективности методов динамического управления распределением нагрузки в сетях массового обслуживания.
Проведено исследование точности методов анализа сетей массового обслуживания с динамическим управлением распределением нагрузки.
Постановка задач, методы решения и полученные результаты являются новыми.
Практическая значимость представленных в диссертационной работе результатов заключается в возможности применения рассмотренных методов динамического управления распределением нагрузки в сетях массового обслуживания и методов анализа сетей массового обслуживания с управлением в математических моделях больших сложных систем с сетевой структурой и стохастическим характером функционирования. Использование моделей этого вида позволит расширить круг задач анализа систем этого класса и повысить эффективность их решения.
Научные положения и методы, разработанные в диссертации, используются в учебном процессе Саратовского государственного университета.
Результаты диссертации докладывались и обсуждались на научных семинарах кафедры системного анализа и автоматического управления Саратовского государственного университета, Международной научной конференции «Компьютерные науки и информационные технологии» (14-18 мая
2002 года, г. Саратов), Международной конференции «Проблемы и перспек-
тивы прецизионной механики и управления в машиностроении» (14-19 октября 2002 года, г. Саратов), Ежегодной межвузовской научной конференции «Компьютерные науки и информационные технологии» (27 апреля 2005 года, 19 мая 2006 года, г. Саратов), представлены и обсуждались на Шестом и Седьмом Всероссийских симпозиумах по прикладной и промышленной математике (1-7 октября 2005 года, г. Сочи-Дагомыс; 2-8 мая 2006 года, г. Кисловодск).
Основные результаты диссертации опубликованы в работах [32-37, 41]. Результаты диссертационной работы получены автором самостоятельно.
В работе [32] Е. С. Рогачко принадлежат метод анализа сетей массового обслуживания с управлением распределением нагрузки между системами (теорема 2.10, 2.11) и результаты исследования методом численного моделирования эффективности метода управления. Ю. И. Митрофанову принадлежат принципы динамического управления распределением нагрузки между системами в сетях массового обслуживания.
В работе [33] Е. С. Рогачко принадлежит метод анализа сетей массового обслуживания с управлением распределением нагрузки между подсетями (теорема 3.3). Ю. И. Митрофанову принадлежат основные положения метода динамического управления распределением нагрузки между подсетями в сетях массового обслуживания.
В работе [34] Е. С. Рогачко принадлежат метод динамического управления распределением нагрузки между подсетями в сетях массового обслуживания и результаты исследования методами численного и имитационного моделирования сетей с управлением распределением нагрузки. Ю. И. Митрофанову принадлежат концепция динамического управления распределением нагрузки между подсетями в сети массового обслуживания и модель эволюции сети с управлением распределением нагрузки между подсетями.
В работе [35] Е. С. Рогачко принадлежат метод динамического управления распределением нагрузки между системами в сетях массового обслуживания (теоремы 2.8,2.9), приближенный метод анализа сетей с управлением (теоремы 2.12, 2.13) и результаты исследования методами численного и имитационного моделирования точности метода анализа сетей обслуживания с управлением. Ю. И. Митрофанову принадлежат постановка задачи управ-
ления распределением нагрузки в сетях массового обслуживания и модели эволюции сети с управлением распределением нагрузки между системами.
В работе [36] Е. С. Рогачко принадлежит метод формирования маршрутных матриц, используемых при управлении распределением нагрузки между подсетями в сетях массового обслуживания. Ю. И. Митрофанову принадлежат принципы управления распределением нагрузки между подсетями в сетях массового обслуживания.
В работе [37] Е. С. Рогачко принадлежит метод формирования маршрутных матриц, используемых при оптимизации потоков в сетях массового обслуживания. Ю. И. Митрофанову принадлежит постановка задачи оптимизации потоков в сетях массового обслуживания.
В работе [41] Е. С. Рогачко принадлежат постановка задачи исследования методов управления распределением нагрузки между системами в сетях массового обслуживания, имитационные модели сетей массового обслуживания с различными методами управления распределением нагрузки и результаты исследования методом имитационного моделирования эффективности различных методов управления распределением нагрузки. Н. П. Фокиной принадлежат алгоритмы методов маршрутизации, использованные при разработке программы имитационного моделирования.
Диссертация состоит из введения, четырех глав, заключения, списка литературы. Объем диссертации 102 страницы. Диссертация содержит 15 таблиц. Список литературы включает 94 наименования.
В первой главе представлен обзор основных результатов по теории сетей массового обслуживания с динамическим и оптимальным управлением распределением нагрузки, а также методам анализа сетей массового обслуживания с динамическим управлением распределением нагрузки, с динамическим управлением интенсивностями обслуживания или маршрутизацией.
Во второй главе предлагается новый метод динамического управления распределением нагрузки между системами в замкнутых экспоненциальных сетях массового обслуживания с одним классом требований. Предлагаемый метод управления распределением нагрузки основан на одновременном использовании управления маршрутизацией и управления интенсивностями обслуживания. Используется метод формирования вектора интенсивностей обслуживания для замкнутых экспоненциальных сетей массового обслуживания, предложенный Ю. И. Митрофановым в работе [29], который обеспе-
чивает получение требуемых значений математических ожиданий числа требований, пребывающих в системах обслуживания. Рассматриваются модель эволюции сети обслуживания с управлением распределением нагрузки и методы анализа сетей массового обслуживания этого типа [35].
В третьей главе предлагается новый метод динамического управления распределением нагрузки между подсетями замкнутой экспоненциальной сети массового обслуживания [34, 36]. При разработке данного метода управления предполагалось, что в сети обслуживания реализована централизованная система управления, обеспечивающая идентификацию состояния сети в заданные моменты времени и использование в сети в процессе ее функционирования различных маршрутных матриц. Приводится алгоритм формирования маршрутных матриц, используемых при реализации метода управления. Предлагаются методы анализа сетей обслуживания с управлением распределением нагрузки между подсетями [34].
В четвертой главе полученные в главах 2 и 3 результаты прилагаются для исследования гипотетических замкнутых сетей обслуживания с динамическим управлением распределением нагрузки между системами или подсетями. Проводится сравнительный анализ методов динамического управления распределением нагрузки между системами в сети массового обслуживания, основанных на использовании управления интенсивностями обслуживания и маршрутизацией [41]. Приводятся результаты исследования методами численного и имитационного моделирования эффективности предложенных методов динамического управления распределением нагрузки в сетях массового обслуживания [34, 35].
Анализ сетей обслуживания с управлением распределением нагрузки
В работах [59, 68] рассматриваются методы анализа открытых сетей массового обслуживания, образованных параллельными системами обслуживания, при динамическом управлении распределением нагрузки. В работе [59] маршрутизация требований в систему с наименьшей длиной очереди основывается на «устаревшей» информации о состоянии сети. Входящий в сеть поток требований является пуассоновским с интенсивностью LX. Интенсивность обслуживания в каждой из L систем обслуживания типа МІМ/1 равна //. Состояние сети определяется вектором распределения требований по системам s = (s{,...,sL). Информация о состоянии сети, на которой основывается управление, обновляется в некоторые детерминированные моменты времени. Интенсивность поступления требований в систему с номером / в момент времени t, когда прогнозируемое состояние сети определяется вектором is = ( i,..., sL), ф\r(t) равна LA/n, если і є А, и равна 0 иначе, где A = {i: Sj =min(si,...,sL)}, п = \А\. Пусть ps s (t) - вероятность того, что сеть находится в состоянии (s, s). Эволюция сети описывается следующей системой дифференциальных уравнений: где є, - вектор, у которого і -ая компонента равна 1, а остальные - 0. Используя приближенный метод анализа, показывается, что среднее время пребывания в сети не всегда минимизируется на основе рассмотренного алгоритма маршрутизации при устаревшей информации для принятия решения. В работе [68] рассматриваются приближенные методы анализа сетей обслуживания в режиме тяжелой загрузки. Работы [13, 20-22, 24, 26,29,38-40, 43, 44, 55, 57, 72-74,77,79, 81, 85, 92] посвящены анализу сетей массового обслуживания, в которых реализованы методы динамического управления интенсивностями обслуживания или маршрутизацией. Для замкнутых и открытых сетей обслуживания с зависимым обслуживанием в работах [40, 44] доказывается существование стационарного распределения в мультипликативной форме. Результаты работ [21, 57, 79, 81] могут быть использованы для создания эффективных алгоритмов вычисления приближенных характеристик сетей обслуживания большой размерности с зависящими от состояния интенсивностями обслуживания.
Примерами работ анализа сетей обслуживания с методами маршрутизации, зависящей от состояния сети, являются [13,20,22,43,55,77, 85, 92]. В работе [13] рассматривается замкнутая звездообразная сеть массового обслуживания с экспоненциальным распределением длительностей обслуживания, состоящая из центральной системы S0 и L систем обслуживания 5,. В сети обслуживании находятся Q требований. Интенсивности обслуживания fij(Sj) систем Sj зависят от числа требований sit г = 0,1,2,...,L. В маршрутной матрице 0 = (ву), i,j = 0,1,2,...,1, элементы ві0 = 1 и Теорема 1.7. Стационарное распределение вероятностей состояний P(s0,...,sL) замкнутой звездообразной сети массового обслуживания определяется выражением если знаки у а и i\,...,bL различны. В работах [55, 77, 92] используется представление сети как набора связанных подсетей. В работе [92] рассматривается замкнутая сеть массового обслуживания с L системами и Q требованиями одного класса. Дисциплина обслуживания в системе St, / = 1,...,/,, когда в ней st требований, может быть определена параметрами bj(q\Sj) - вероятностью поступления требования на станцию q и /)( 1 ) - объемом обслуживания, получаемого требованием на станции q.
Станция q в общем случае является местом с номером q в очереди системы St. Состояние сети определяется вектором = ( ,... ), где х{=(хп,...,х15), xiq - число единиц обслуживания требования на станции q, оставшееся до завершения обслуживания этого требования. Вводится в рассмотрение также вектор s = {sx,...,sL). Стратегия маршрутизации в сети определяется множеством маршрутных вероятностей 0y(s - і) - вероятностей того, что требование, выходящее из Sf, поступает в Sj при условии, что сеть непосредственно перед выходом требования находилась в состоянии S. Параллельной р -подсетью называется подсеть, состоящая из / непересекающихся множеств систем обслуживания, названных р -ветвями. Требования могут войти в р -подсеть только через одну входную систему и выйти из р -подсети только через одну выходную систему. Пусть сеть содержит / р-подсетей с номерами m = l,...,J; р-подсеть т состоит из множества систем, которое разбито на 1т р -ветвей; р -ветвь с номером / состоит из множества S(m,l) систем. Пусть Qm - число требований в р -подсети с номером т, a Qm! - число требований в /-ой р-ветви ;?-подсети с номером т. Если Sj является входом в р-подсеть т и jeS(m,l) для некоторого /, то вц может иметь форму Здесь p\j - неотрицательная константа, a hm и hm! - произвольные вещественные неотрицательные функции. Пусть Sf является входом в Jtj- р-подсетей, к которым принадлежит S.-, с номерами ml,m2,...,mJ. Тогда где Sj принадлежит p -ветви lk внутри p -подсети mk. Все другие маршрутные вероятности остаются постоянными. Вводятся функции Теорема 1.8. Бели маршрутные вероятности из систем-входов в параллельные подсети имеют вид (1.11), маршрутные вероятности остальных систем постоянны, и каждая система удовлетворяет условию локального равновесия, то 1) стационарная плотность распределения сети имеет вид V m=l где G - нормализующая константа, a pt{xt) - плотность распределения системы St в изолированном состоянии с интенсивностью входящего потока су\. Параметры у\ являются решениями системы уравнений где dp = Ojj, если Op постоянна, и в р = р р, если ejt - функция, определенная выражением (1.10); 2) сеть обслуживания удовлетворяет условию локального равновесия. В работах [24, 26, 29, 38, 39] рассматриваются методы анализа замкнутых экспоненциальных сетей массового обслуживания с динамическим управлением. Содержание методов управления связано с обеспечением пребывания сети в заданном множестве состояний и возвращения в это множество, если сеть вышла из него. При реализации управления процесс функционирования сети представляет собой последовательность фрагментов, в течение которых используются различные интенсивности обслуживания в системах сети [24, 29] или различные маршрутные матрицы [26,38,39]. Методы анализа открытых сетей массового обслуживания с несколькими классами требований и динамической маршрутизацией рассмотрены в работах [72-74]. В момент поступления требования класса к в сеть из источника в соответствии со стратегией маршрутизации определяется маршрут требования из множества маршрутов, доступных требованиям класса к. Сети обслуживания общего вида с динамической маршрутизацией рассматриваются в [72], а экспоненциальные сети - в [73]. В работах [72, 74] основное внимание уделяется анализу открытых сетей обслуживания с тяжелой загрузкой. При изучении методов оптимальной динамической маршрутизации в таких сетях используется броуновская модель эволюции сети [74], флюидные модели и марковские процессы принятия решений [72].
Формирование оптимального вектора интенсивностей обслуживания
Далее рассматривается сеть N, в которой реализован метод динамического управления распределением нагрузки. Различаются два режима функционирования сети N - нормальный и коррективный. Периоды функционирования сети в этих режимах называются соответственно нормальными и коррективными тактами. Вид очередного такта определяется типом состояния (доминантное или ординарное) сети в момент завершения предшествующего такта. Основным назначением коррективных тактов является возвращение сети в множество доминантных состояний. Нормальный такт длительности р начинается в некотором доминантном состоянии, а заканчивается или в доминантном состоянии или в ординарном состоянии. Коррективный такт начинается в некотором ординарном состоянии, а заканчивается либо в базовом состоянии s в момент перехода в него сети, если это собы- тие происходит до завершения такта длительности р, либо в доминантном или ординарном состоянии в момент завершения такта длительности р.
Обозначим через rf длительность коррективного такта, начавшегося в состоянии s Y+J\ J є {1,..., cz}. Нормальный и коррективный такты отличаются способами маршрутизации требований и используемыми в течение тактов интенсивностями обслуживания в системах. В нормальном такте маршрутизация осуществляется с использованием маршрутной матрицы 0, в коррективном такте- с использованием матриц передач N() (локальных маршрутных матриц). В нормальном такте используется вектор интенсивно-стей обслуживания / = (//,), і = 1,...,L, в коррективном такте, если предшествующий такт закончился в ординарном состоянии ,у(Су+,/), - вектор Матрица передач N(w) =(vw)), /, у = 1,...,Z, является нуль-единичной матрицей и определяет маршруты требований, завершивших обслуживание в одной из систем при пребывании сети в состоянии s [39]. Метод формирования матрицы передач для состояния s{"] єХ Определяется номер системы у є/, переход в которую требования из Sj обеспечит переход сети из состояния s в принадлежащее От" состояние, имеющее наибольший потенциал по сравнению с другими состояниями множества Q- . Если в Q имеется несколько состояний с одинаковыми наибольшими потенциалами, то из них выбирается состояние с наименьшим м. о. длительности пребывания сети в этом состоянии. Если же в Qjw) имеется несколько состояний с одинаковыми наименьшими м. о. длительности пребывания в них, то из этих состояний (для определенности) выбирается состояние с наименьшим номером у системы, в которую переходит требование из Sj. Значение элемента vfj матрицы полагается равным 1, а значения элементов vj"\ l j, / = 1,...,L, - равными 0. Если s$n) =0, то полагается Метод формирования вектора juJ = (Д )
Обозначим через D, и v,- интенсивности потоков требований, входящего в Sj и выходящего из Sj в течение коррективного такта х длительности р, начальным состоянием которого является s CY+J\ Алгоритм формирования J1J содержит один вспомогательный и несколько основных шагов, число которых зависит от требуемой точности определения вектора fiJ [29]. При выполнении вспомогательного шага предполагается, что 1),=//,, / = 1,...,1. Обозначим На вспомогательном шаге определяются величины При выполнении следующих основных шагов производится подстановка в правую часть выражения (2.50) величин Д/, / = 1,...,/,, определенных на предыдущем основном шаге, вычисление vit gj и следующих значений Д7. D Теорема 2.8. Матрицы передач N() обеспечивают в течение коррективного такта эволюцию сети JV в направлении базового состояния s. Доказательство. Пусть эволюция сети N в течение коррективного такта, начавшегося в состоянии s Y+J , описывается цепью Маркова С"7 с множеством состояний В и непрерывным временем (все состояния этой цепи являются устойчивыми). Длительность реализации цепи СJ равна длитель- ности коррективного такта rf. Множество состояний цепи С разбивается на два класса, из которых один класс В1 является существенным, а второй класс В2 - несущественным. Класс Вг - возвратный класс, а класс В2 - невозвратный. Таким образом, цепь CJ - приводимая цепь, содержащая одну неприводимую цепь Маркова с множеством состояний Вг. Класс Вх обязательно включает состояние s" и множество смежных ему состояний. Способ формирования матриц передач обеспечивает переход сети из некоторого состояния в состояние из множества Вх, имеющее, как правило, больший потенциал по сравнению с данным состоянием. Последовательное применение матриц передач приводит к эволюции сети N в направлении со стояний с большими потенциалами, т. е. в направлении доминантных состоя ний и, в частности, в направлении s. Теорема 2.9. Если коррективный такт начинается в состоянии s(cY+J) е % t то вектор интенсивностей обслуживания fiJ обеспечивает в течение этого такта эволюцию сети N в направлении базового состояния s. Доказательство. Обозначим через о( интенсивность потока требований, входящего в Si в течение коррективного такта JC длительности р, начальным состоянием которого является s Y+J\ Предполагается, что в систему S{ в течение такта х поступит в среднем ot p требований. Следовательно, чтобы в момент окончания такта JC в S, осталось s требований, необходимо обслужить в течение такта х в среднем sjCr+J +Uj p-s требований. Это и реализуется в методе формирования вектора интенсивностей обслуживания ju , используемого в течение коррективного такта х.
Анализ сетей обслуживания с динамическим управлением распределением нагрузки
Множество номеров состояний сети В = {1,..., сх}. Предполагается, что для каждого s є X определена характеристика V - потенциал этого состояния. Значение потенциала состояния отражает уровень значимости пребывания сети в этом состоянии с точки зрения обеспечения заданных характеристик качества ее функционирования -чем более значимо состояние, тем больше его потенциал. Нумерация состояний производится с учетом их потенциалов: если у V(-n\ то т п, т,пеВ. Введем в рассмотрение вектор г =(а ), F = 1,...,«/, к є {!,...,К}, определяющий к -й способ распределения Q требований между J подсетями, Тр) - число требований, находящихся в NF, К - число способов распределения требований между подсетями. В случае, когда распределение требований в сети N определено вектором а к\ сеть будем называть к-й реализацией сети N и обозначать N(k). Пусть cr определяет требуемое распределение требований по подсетям, это распределение будет называться базовым. Учитывая все способы распределения и соответственно все реализации сети N, можно считать, что сеть N является совокупностью всех реализаций N(k) этой сети. Реализация N(k) имеет множество состояний Хк, сХк =\Хк\. Множество номеров принадлежащих Хк состояний обозначим Вк. Очевидно, Вектор а назовем макросостоянием сети N, множество макросостояний сети N обозначим через Е, Щ = К. В сети N используется динамическое управление распределением нагрузки посредством управляющих воздействий, формируемых в процессе функционирования сети системой управления.
Целью управления является достижение максимального значения стационарной вероятности ж(Щ пребывания сети в подмножестве макросостояний Я, называемом множеством доминантных макросостояний, сн = \Н\. Макросостояния сети, принадлежа- щие множеству U = E\H, называются ординарными, %=f7. Обозначим через D и W множества номеров соответственно доминантных и ординарных макросостояний. К доминантным относятся макросостояния, при пребывании в которых распределение требований между подсетями ближе к требуемому, чем при пребывании в ординарных макросостояниях, в частности, сг(1)єЯ. При формировании множеств Н и U используются векторы )=(4 ), граничных значений числа требований в подсетях. Макросостояния т , к е {!,..., К}, для относятся к множеству Н, остальные макросостояния - к множеству U. Различаются два режима функционирования сети N - нормальный и коррективный. Периоды функционирования сети в этих режимах называются соответственно нормальным и коррективным тактами. Все такты имеют фиксированную длительность р. Режимы функционирования отличаются используемыми в сети маршрутными матрицами - в нормальном такте используется всегда матрица 0 = (0 ), в коррективном такте - матрица = (0.J )), соответствующая макросостоянию сети сг( \ к є W, в момент окончания предшествующего такта. Нормальный такт начинается всегда в одном из доминантных, а коррективный такт - в одном из ординарных макросостояний. Заканчиваться такты могут как в доминантном, так и в ординарном макросостоянии. В момент окончания каждого такта формируются управляющие воздействия, направляемые системам обслуживания с целью идентификации макросостояния сети в данный момент времени и определяющие новые значения элементов маршрутной матрицы сети. Предполагается, что функционирование сети N начинается в нормальном режиме в некотором состоянии 5(и) є11; т. е. в макросостоянии ст , в момент времени t = О. В данном разделе рассматривается сеть N без управления.
В качестве матрицы может рассматриваться маршрутная матрица, при которой достигается математическое ожидание числа требований в подсетях в соответствии с их базовым распределением jw. Для формирования такой матрицы могут быть использованы, в частности, методы, рассмотренные в [25]. Матрицу = (6у), i,j = \,...,L, назовем оптимальной маршрутной матрицей сети N, если при ней достигаются значения математических ожиданий числа требований в подсетях, близкие к базовому распределению ст( \ определенному для однозначности некоторым состоянием s єХ), которое будем обозначать s. Рассмотрим метод формирования оптимальной маршрутной матрицы сети N, при этом используем понятие виртуальных сетей массового обслуживания [28]. Сети массового обслуживания, являющиеся моделями соответствующих дискретных систем, будем называть объектными. Параметры виртуальных сетей массового обслуживания формируются на основе параметров соответствующих объектных сетей. Виртуальные сети массового обслуживания могут отличаться от соответствующей объектной сети только своими маршрутными матрицами. Формирование виртуальной сети массового обслуживания является синтезом сети обслуживания определенного класса, некоторые стационарные характеристики которой должны удовлетворять заданным требованиям. Не исключены случаи, когда для конкретной объектной сети обслуживания невозможно сформировать виртуальную сеть обслуживания.
Алгоритм формирования коррективных маршрутных матриц
В работе [36] описан метод управления распределением нагрузки в сети массового обслуживания, состоящей из двух подсетей, и алгоритм формирования маршрутных матриц, используемых при управлении. Построим ал- горитм формирования маршрутных матриц, используемых на коррективных тактах, для случая разбиения сети обслуживания на J подсетей. Пусть коррективный такт начинается в ординарном макросостоянии 7( \ к є W. Определяются подсети Nx и Ny такие, что Обозначим Qx и Qy множества номеров подсетей, смежных соответственно подсети Nx и подсети Nv. Используемая в течение коррективного такта маршрутная матрица 0( ) должна обеспечить увеличение интенсивности потоков требований в Nx из смежных подсетей NG, GeQ.x, и уменьшение интенсивности потоков требований в Ny из смежных подсетей NG, GeQy, по сравнению с интенсивностями этих потоков при матрице 0. Различаются два вида систем массового обслуживания в подсетях -внутренние и граничные. Граничными называются системы, непосредственно связанные с системами обслуживания из других подсетей. Граничные системы могут быть трех типов - входные, выходные и стандартные. Входной называется система, в которую могут только поступать требования из других подсетей. Выходной - система, из которой возможен только переход требований в другие подсети. Стандартной - система, в которую могут поступать требования из других подсетей и из которой могут переходить требования в другие подсети.
При формировании матрицы 0 в качестве исходной используется матрица 0, которая модифицируется соответственно концепции «замыкания» потоков требований в сети обслуживания [28]. При реализации этой концепции производится, во-первых, изменение направления потоков требований, выходящих из граничных выходных или стандартных систем подсети Nx в граничные входные или стандартные системы смежных подсетей NG, G є Qx; эти потоки направляются в соответствующие системы подсети Nx. Во-вторых, для всех подсетей NG, GeCly, производится изменение направления потоков требований, выходящих из граничных выходных или стандартных систем подсети NG в граничные входные или стандартные системы подсети Nv; эти потоки направляются в соответствующие системы подсети NG. Если, например, до выполнения «замыкания» потоков связи между граничной выходной или стандартной системой 5,, ієІх,и некоторой системой Sj, jelx, в которую требуется направить поток из Slt не существовало и Оу = 0, то при выполнении «замыкания» такая связь будет установлена и 9{j 0. При определении систем подсети, в которые необходимо направить выходные потоки, учитываются коэффициенты использования систем: для оптимизации распределения нагрузки выходные потоки направляются в системы с наименьшими коэффициентами использования.
Обозначим LFu, LFv, LFw, LFe соответственно число входных, выходных, стандартных и внутренних систем обслуживания в подсети NF, FeR; lFu, IFv, IFw, IFe соответственно множество номеров входных, выходных, стандартных и внутренних систем обслуживания в подсети NF; h,u,w=h,u h,w h,v,w=h,vKJh,w ф/ множество номеров смежных системе Sj систем обслуживания, в которые поступают требования непосредственно из системы Sj. Предполагается, что LFv+LFw 0, LF,U + При формировании 0( используются вектор # = (#,), / = 1,..., L, относительных интенсивностей потоков требований в сети N, вектор = (У, ) коэффициентов использования систем обслуживания в сети N и относительные интенсивности потоков требований из системы St в систему Sj сети N Эти стационарные характеристики сети могут быть вычислены известными методами [23]. Рассмотрим основные действия, выполняемые при формировании M=(0to),i,j = l,...,L,keW. 1. Формирование начального значения матрицы 0 : и формирование множества Y = {g/ }, 1 = 1,..., Lxv+Lxw, gt elxvw, номеров выходных и стандартных систем подсети Nx; предполагается, что элементы множества Y упорядочены по убыванию соответствующих этим элементам величин 0.
