Диссертация (1154395), страница 13

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

Текст из файла (страница 13)

Поэтому методнахождения вероятностей блокировок непосредственно по формулам (2.3)–(2.6)применим лишь для простейших случаев. Более того, для сети произвольнойтопологии вычисление нормировочной константы G( N ) по формуле (2.4)относится к NP-полным проблемам, для которых не существует эффективныхкомбинаторных алгоритмов.

Поэтому много внимания уделялось [91] иуделяется разработке приближенных методов вычисления вероятностныххарактеристик модели, пригодных для анализа широкого класса моделей.Приближенным методам расчета сетей рассматриваемого типа посвящена,например, глава 5 книги [93].В этом разделе диссертации показано основное свойство моделеймультисервисных сетей, приведенное в теореме 2.1 на примере классическихсетей Келли для случай одноадресных соединений [193, 194]. Целью даннойглавы является анализ мультипликативных решений для сетей с одноадресными- 63 -имногоадреснымисоединениями,атакжесоответствующиеимвычислительные алгоритмы для основных вероятностных характеристик. Вразделе 2.2 исследованы сети с многоадресными соединениями, т.н.

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

В разделах 2.4 и 2.5 показано применениеразработанных методов к двум важным моделям сетей 4G и 5G. Первая модель[237] показывает мультипликативное решение для беспроводной сети 5G, гденаряду с традиционным речевым трафиком (H2H) обслуживается трафикмежмашинных взаимодействий (M2M). Вторая модель [16, 17] построена дляназемных коммуникаций - пассивных оптических сетей с реализованной на нихтехнологией мультиплексирования по длине волны (wave division multipexing,WDM).2.2.Модель мультисервисной сети с многоадресным трафикомВ этом разделе в соответствии с [91] проведен анализ модели отдельногозвена сети мультивещания и ее вероятностных характеристик, а также полученрекурсивный алгоритм для вычислений.

Напомним, что обозначения общеймодели и основная теорема о мультипликативнсти (теорема 1.1.) для модели П1введены в главе 1 диссертационной работы.Модель отдельного звена сетиРассмативается сеть с многоадресными соединениями, в которой длянекоторогозвенаl*  Lвыполняютсясоотношения  bms  ClsSl**;mMs  bms  Cl , l  L \{l} . Это сеть мультивещания, в которой емкостей всехsS l mMs- 64 -звеньев, кроме одного, достаточно для установления любых многоадресныхсоединений и их сочетаний, т.н.

«сеть с выделенным звеном». Блокировкизапросов пользователей на установление многоадресного соединения могутвозникнуть только на единственном звене l , и их анализ можно проводить спомощью модели сети, состоящей из одного звена L  {l *} . При этом к узлу наодном конце звена l подключен единственный источник, предоставляющийуслуги из множестваMMs , а к другому – пользователи сетиsSl*мультивещания с выделенным звеном. Для краткости далее в разделе 2.2индексы l и s будем опускать: C  Cl* , P  P l .*Моделью отдельного звена служит многопотоковая СМО без накопителя,состоящая из Cприборов. На СМО поступает M | M | пуассоновскихнезависимых в совокупности потоков заявок.

В модели при поступленииm-заявки производится одно из трех действий.1.Заявка поступает на обслуживание с выделением для этого bm приборов,если в момент ее поступления в системе имеются bm свободных приборов инет ни одной заявки этого потока. Принятая заявка занимает их наслучайное время, распределенное экспоненциально с параметром m , независящееот длительности обслуживания заявок других потоков и отпроцессов поступления заявок.2.Заявкапоступаетнаобслуживаниебезвыделениядляэтогодополнительных приборов, если в момент ее поступления в системе ужеобслуживается хотя бы одна заявка этого потока. Вновь принятая заявкаобслуживается теми же приборами, что и уже имеющиеся в системеm-заявки, и по истечении интервала обслуживания первой заявки,определенного в п.1, одновременно с ними покидает систему, при этом bmприборов освобождаются.3.В противном случае m-заявка теряется из-за отсутствия свободныхресурсов.Таким образом, поступившая в систему заявка будет принята наобслуживание в систему даже если нет достаточного количества свободныхприборов, но уже обслуживаются заявки того же потока.- 65 -Введем обозначения 1,..., M для интенсивностей входящих потоков иобозначим m  m / m .

В [91] показано, что параметр m-потока  m зависитот интенсивностей  mp потоков запросов на включение соответствующихлогических путей в сети следующим образом:m   (1  mp )  1, m  1,..., M .(2.7)pPДля случая C   потери на отдельном звене (и в сети) отсутствуют, всепоступившие в систему заявки принимаются на обслуживание.

Введемслучайный процесс {Ym (t ), t  0} , m  1,..., M , который может находиться всостоянии 1, если в момент t  0 в системе обслуживается хотя бы одна mзаявка, и в состоянии 0 в противном случае. Процесс {Ym (t ), t  0} являетсяо.м.п. и имеет стационарное распределениеmym m ( ym )  P{Ym (t )  ym } , ym {0,1} .1  m(2.8)Рассмотрим многомерный м.п. Y (t )  Ym (t ) mM , t  0 , определенный наMмножестве Y  {0,1} . По построению на этом множестве он является о.м.п.

иимеет стационарное распределениеM (y )  G 1 ( Y ) mym , y  Y ,(2.9)m1где для любого множества   Y функция G() имеет видG ( ) M  mym.(2.10)y m1Последнее соотношение определяет нормирующую константуG( Y )распределения м.п.

{Y (t ), t  0} :MG ( Y )   (1  m ) .(2.11)m1М.п. {Y (t ), t  0} с пространством состояний Y и распределением (2.9)описывает состояние модели при C   . Пусть теперь C   и, следовательно,возможны потери заявок. Будем считать, что потерянные заявки не оказываютвлияние на интенсивность соответствующего входящего потока. В этом случае- 66 -функционирование системы описывает м.п. {Y (t ), t  0} , как сужение м.п.{Y (t ), t  0} на множествоY  {y  Y : c(y)  C} ,(2.12)Mгде c(y )   bm ym – число занятых приборов в состоянии y  Y .

Как сужениеm1обратимого процесса м.п. Y (t ) также обратим, и, следовательно, справедливаследующая теорема.Теорема 2.2.Стационарноераспределением.п.{Y (t ), t  0}имеетмультипликативный видM (y )  G 1 ( Y ) mym , y  Y ,(2.13)m1где G ( Y ) M  mym.yY m1Длярасчетахарактеристикотдельногозвенаможноиспользоватьполученное для модели сети соотношение (2.10), где функция G() зависит отсоответствующегоподмножествапространствасостояний.Ктакимхарактеристикам относятся вероятность потери заявок, вероятность наличия всистеме m-заявки, вероятность приема на обслуживание m-заявки при условииотсутствиявсистемезаявокэтогопотока.Последняявероятностнаяхарактеристика отражает свойство мультивещания: даже если в моментпоступления m-заявки свободных приборов недостаточно для обслуживаниязаявок этого потока, но в системе уже есть m-заявка, блокировки не происходит.Введем подмножества пространства состояний, которые позволят рассчитатьэти характеристики.Множество потерь m-заявок:Bm  {y  Y : c(y)  bm  C, ym  0} .(2.14)Множество состояний, в которых m-заявки имеются на обслуживании:Fm  y  Y : ym  1 .(2.15)Множество приема на обслуживание m-заявки при условии отсутствия всистеме заявок:Hm  y  Y : c(y)  bm  C, ym  0 .(2.16)- 67 -Первое событие включает состояния системы, в которых соответствующиеm-услуге данные передаются через рассматриваемое звено.

В состоянияхсистемы, составляющих второе событие, на звене достаточно ресурсов, чтобыначать предоставление m-услуги по звену по запросу пользователя, причемm-услуга ещѐ не предоставляется по звену.Здесь для любого m  1,..., M система множеств Bm , Fm , H m являетсяразбиением пространства состояний Y . Для них верно соотношениеBm  Fm  H m  1 .В [91] доказаны лемма 2.1 и следствие 2.1 из нее, которые связывают триуказанные вероятностные характеристики.Лемма 2.1. Для любого m  1,..., M выполняется соотношение Fm  m H m .Следствие 2.1. Для любого m  1,..., M верно соотношение Fm m1  Bm  .1  mНиже изложен полученный автором [36] эффективный метод численногоанализа системы, основанный на рекурсивном вычислении нормирующейконстанты G( Y ) .Алгоритм свертки для отдельного звена сети мультивещанияДля вывода алгоритма расчета вероятностных характеристик моделипрежде всего необходимо исследовать свойства множества Y и получитьалгоритм для расчета нормирующей константы G( Y ) .ВведемдляиmMY  m, n   y(m)  ( y1,..., ym ) : c  y(m)   n .n  0,..., CДоопределиммножестваданнуюсистемумножеств для значений m  0 и n  0 следующим образом: Y (m, n), m  1,..., M , n  1,..., C ;{0}, m  0,..., M , n  0;Y (m, n)  , m  0, n  1,..., C ;, m  0,..., M , n  0.ПопостроениюмножестваY (m, n)(2.18)удовлетворяютY (m, n) Y (m, n)  , n  n , для любого m  0,..., M и Y соотношениямCY ( M , n) .

Для всехn 0m  1,..., M и n  1,..., C множество Y (m, n) представимо в виде- 68 -Y (m, n)  Y (m  1, n)  0ВведемY (m  1, n  bm )  1 .mg (m, n) функцию(2.19) iyiизаметим,чтоy ( m )Y ( m,n ) i 1CG ( Y )   g ( M , n) .n 0Лемма 2.2.Функция g (m, n) вычисляется рекурсивно по формуле0, m  0, n  1,..., C;0, m  0,..., M , n  0;g (m, n)  1, m  0,..., M , n  0;m  1,..., M , g (m  1, n)   m g (m  1, n  bm ),n  1,..., C.(2.20)Доказательство. Первые три строки формулы очевидным образом следуютиз (2.18). Докажем утверждение четвертой строки. По построению имеем:g (m, n) m iyiy ( m )Y ( m,n ) i 1m iyi y ( m )Y  m1,n 0 i 1 y ( m1)Y( m1,n bm ) iyi  y ( m1)Y ( m1,n ) i 1 iyiy ( m)Y  m1,n bk 1 i 1mmmi 1 iyi  m  g  m  1, n   m g  m  1, n  bk  .

Характеристики

Список файлов диссертации