The probabilistic model of sharing system with collisions, H-persistence and rejections data processing.pdf Развитие современных инфокоммуникационных систем и сетей связи открывает множество различных услуг для использования абонентами. В современных условиях пользователем выступает не только человек, но и многообразие устройств, подключенных к сети. Стремительный рост генерируемой нагрузки при этом вызывает перегрузки на отдельных участках сети, что ведет к ухудшению качества предоставляемых услуг. Пользователь имеет все больше возможностей влиять своим поведением на формирование входящих потоков, частоту посылки вызова, длину сообщений, их количество и т.д. В условиях, когда возникает временная недоступность сервиса, важным фактором становится повторный запрос (вызов) на предоставление услуги или сервиса. Множество мультимедийных и служебных приложений на абонентских устройствах может в автоматическом режиме генерировать подобные запросы, не имея при этом каких-либо ограничений, связанных, например, с временем набора номера или терпеливостью абонента. Такой неучтенный трафик будет занимать канальный ресурс сверх запланированного под нагрузку от первичных потоков вызовов. На участках сети возможны переполнения, которые приводят к отказу в обслуживании заявок, что порождает, в свою очередь, множество повторных обращений к системе. Нагрузка от потока повторных вызовов, как правило, не является учтенной, что приводит к выходу из строя сегментов сети до полного отказа ее работы. Выявление и исследование влияния подобных аспектов поведения на качество работы сети позволяет заранее спланировать и подготовить сеть таким образом, чтобы снизить потери вызовов на ее участках. Наибольший интерес для практики представляет рассмотрение экстремальных условий работы, т.е. условий перегрузки, отличающих ее от нормального (планируемого) состояния. Все это определяет актуальность создания теоретических основ для построения математических моделей, позволяющих модифицировать, совершенствовать и разрабатывать методы анализа и расчета показателей качества обслуживания в инфокоммуникационных системах и сетях связи. Теория систем массового обслуживания с повторными вызовами (Retrial Queueing Systems; RQ-системы) является важным разделом современной теории телетрафика: актуальность обусловлена широкими практическими приложениями в области оценивания производительности и проектирования широковещательных и мобильных сотовых радиосетей, локальных вычислительных сетей с протоколами случайного множественного доступа. В таких системах запрос, поступивший в систему (запрос на соединение с сотой) и не получивший обслуживания, не уходит из системы (как в системах с отказами) и не становится в очередь (как в системах с ожиданием), а повторяет попытки через случайное время, пока не поступит на обслуживание. Явление повторных попыток является неотъемлемой чертой вышеуказанных систем передачи данных, и игнорирование его может привести к значительным погрешностям при принятии инженерных решений. Исследованию RQ-систем посвящено большое количество работ. Например, в монографии J.R. Artalejo, A. Gomez-Corral [1] приведено более семисот ссылок на публикации по этой тематике. В работах R. Wilkinson, J. Cohen, G. Gosztony и др. [2-5] отмечено, что математические модели RQ-систем применяются для проектирования и оптимизации реальных информационно-коммуникационных систем различного уровня (локальных, глобальных), управляемых протоколами случайного множественного доступа, цифровых сетей связи, а также сетей сотовой связи, вычислительных кластеров, call-центров и др. Имеющиеся на сегодняшний день научные публикации в данной области предлагают достаточно много различных задач и подходов к их решению. Наиболее полно исследованы марковские и немарковские RQ-системы с настойчивыми повторными заявками (базовая модель), получены рекуррентные формулы для вычисления распределения вероятностей числа заявок на орбите как для конечного, так и для бесконечного размера орбиты. Основными методами исследования RQ-систем являются матричные методы, численные методы, имитационное моделирование, так как точные аналитические формулы удается получить лишь для самых простых моделей [6-8]. Более сложными для исследования являются модели с конфликтами заявок. Рассмотрение RQ-систем с ситуацией конфликта заявок подразумевает, что заявка, нашедшая прибор занятым в момент прибытия ее в систему, и заявка, находящаяся на обслуживании, вступают в конфликт [9-13]. RQ-системы с конфликтами заявок имитируют поведение многих реальных ситуаций, например в телекоммуникационных сетях с протоколами множественного доступа с обнаружением коллизий (CSMA-CD), где передача данных должна быть гарантирована с безошибочной точностью с некоторой заданной вероятностью [14-18]. RQ-системы с нетерпеливостью заявок возникают при моделировании процессов обращения в call-центры [16-18]. Для характеристики поведения нетерпеливых клиентов помимо терминов «нетерпеливость», «^-настойчивость» используется термин «отказ», понимаемый как решение не присоединяться к линии (прибору) после неудачной попытки получить обслуживание с последующим уходом из системы. Учет таких особенностей существенно усложняет математическую модель и ограничивает возможность получения аналитических выражений, поэтому применяют аппроксимационные методы [19-25]. Настоящая статья посвящена исследованию RQ-системы с одним обслуживающим прибором с коллизиями (конфликтами) заявок, Н-настойчивостью и отказами. 1. Функциональная модель системы совместного доступа с коллизиями и отказами Прежде чем построить математическую модель анализируемой системы связи, определим функциональную модель, являющуюся ее функциональным прототипом. Формализуем работу системы: выделим перечень событий, которые имеют существенное значение при использовании анализируемого ресурса передачи информации [26]. Рассмотрим однолинейную (с одним обслуживающим прибором) систему с конфликтами заявок, Н-настойчивостью и отказами. На вход системы поступает простейший поток заявок с интенсивностью X. Заявка, заставшая прибор свободным, занимает его, и начинается обслуживание, которое заканчивается успешно, если во время него другие заявки не поступали. Если прибор занят, то между пришедшей на обслуживание и обслуживаемой заявками возникает конфликт (коллизия), и в общем случае [16-17] обе заявки мгновенно переходят на орбиту и повторяют попытку успешно обслужиться через случайное время. В настоящей статье в случае возникновения коллизии заявка, находившаяся на обслуживании (на приборе), уходит на орбиту с вероятностью 1, а поступившая на прибор и вызвавшая конфликт заявка с вероятностью H уходит на орбиту, а с вероятностью (1 - Н) отказывается от обслуживания и покидает систему. Рис. 1. Схема моделирования суммарного входящего потока заявок Fig. 1. Scheme for modeling the total incoming arrival process Конфликт Абоненты, формирующие первичный поток заявок Случайное число абонентов, формирующих поток повторных ЗЯБОК Успешное обслуживание Повторное обслуживание 1 - Н Отказ А + io Суммарная интенсивность потока заявок зависит от числа заявок на орбите i V Рис. 2. RQ-система с коллизиями, H-настойчивостью и отказами Fig. 2. RQ-system with collisions, H-persistence and rejections - > А о ■ - о 0 ■ ■ а о > - о Будем разделять поступающие на прибор заявки на две категории: первичные и повторные. Первичные - это заявки, поступившие в систему извне; повторные - заявки, оказавшиеся на орбите системы в результате коллизии и осуществляющие повторную попытку занять прибор для обслуживания. Суммарный входящий поток обращений в систему состоит из потока первичных заявок и потока повторных заявок. На рис. 1 приведена схема формирования суммарного входящего потока. Время обслуживания первичной или повторной заявки не зависит от ее типа и имеет экспоненциальное распределение с параметром ц, и для обслуживания заявок используется одна единица ресурса линии. Случайная задержка, которую осуществляет заявка на орбите, экспоненциально распределена с параметром о. Описанная процедура доступа к канальному ресурсу (обсуживающему прибору) и образования орбиты показана на рис. 2 как модель RQ-системы с коллизиями, Н-настойчивостью и отказами. В работе решается задача определения вероятностных характеристик работы системы: среднего числа повторных попыток соединения на одну первичную; среднего числа отказов на одно установленное соединение; доли повторных вызовов в общем потоке поступающих, - которые позволяют оценить работоспособность системы. 2. Математическая модель Обозначим i(t) - случайный процесс, который описывает число заявок на орбите в момент времени t и задается следующим образом: i(t) = 0,1, 2,... , k(t) - случайный процесс, определяющий состояние прибора в момент времени t: k(t)= °, если прибор свободен, 1, если прибор занят. Так как входящий поток - простейший, а время обслуживания - экспоненциальное, то случайный процесс [k (t), i (t)} изменения во времени состояний описанной RQ-системы является двумерной цепью Маркова с непрерывным временем. Обозначим через P[k(t)=k,i(t)=i}=Pk (i,t), i= 0,1,2,..., k = 0,1, вероятность того, что в момент времени t прибор находится в состоянии k и на орбите i заявок. Ставится задача нахождения распределения вероятностей случайного процесса - числа абонентов, повторяющих вызов, и состояния прибора в стационарном режиме функционирования системы. Для распределения вероятностей Pk (i,t ) согласно теореме о полной вероятности можно составить равенства: Для i = 0: P (°,t + At) = р (°,t)(1 -kAt) + P (°,t)pAt + o(At), < P (°,t + At) = р (°,t)(1 -kAt)(1 -pAt) + р (°,t)kAt + р (1,t)(1 -kAt)cAt + o(At). Для i = 1: P (1, t + At)=P0 (1, t )(1 - kAt )(1 - cAt)+P1 (1, t )pAt + P1 (0, t )kAt (1 - Н)+P1 (1, t )sAt (1 - Н)+o(At), [P1 (1, t + At)=P1 (1, t )(1 -kAt )(1 - pAt )(1 -cAt)+P0 (1, t )(1 - cAt )kAt+P0 (2, t )(1 - kAt )2cAt + o(At) Для i > 2: P (i,t + At) = P (i, t)(1 - kAt)(1 -icAt)+P (i,t)pAt+P (i - 2, t)kAtH + P (i -1, t)kAt(1 - H) ' + P1(i-1,t )(i-1)cAtH + P1(i,t)icAt(1 - H )+o(At), P1 (i, t + At) = P1 (i, t )(1 - kAt )(1 - pAt )(1 - icAt)+P0 (i, t )(1 - icAt )kAt + P0 (i +1, t )(1 - kAt )(i + 1)cAt + o(At). Отсюда нетрудно получить систему дифференциальных уравнений Колмогорова: Для i = 0: = -XPo (0, t )+MP1 (0, t), ^0^ = -(X + ц)Р1 (0, t)+ XPo (0, t)+ vPo (1, t). Для i = 1: 'P0(1',] = -(X + П1/0 (1, t)+ ЦР1 (1, t)+ X(1 - H )P1 (0, t)+ c(1 - H )P1 (1, t), ^P^ = -(X + ц + a)P1 (1, t)+XP0 (1, t)+20P0 (2, t). Для i > 2: iPXX = -(X + ic)P0 (i, t)+ gP[ (i, t)+ XHP1 (i - 2, t)+X(1 - H )P1 (i -1, t) + (i - 1)cHP1 (i -1, t)+ ic(1 - H )P1 (i, t), ^P1dt t) = -(X + Ц + i°)P1 (i,t)+ XP0 (i,t)+(i + 1)cP0(i +1,t). Обозначим через Пk (i) стационарные вероятности случайного процесса {k(t), i(t)} , перепишем для них систему (1). Для i = 0: - Xn 0 (0)+цП1 (0) = 0, -(Х + ц)П1 (0 )+Xn 0 (0 )+сП 0 (1) = 0. < -(X + cH(1)+X(1 -H)n(0)+[ц + с(1 -H)]ft(1)=0, (2) - (X + ц + с)п1 (1)+Xn 0 (1)+2сП 0 (2) = 0. Для i > 2: - (X + ia)n 0 (i)+ [ц + ic(1 - H )]п1 (i)+[x(1 - H)+(i - 1)cH ]п1 (i -1)+XHn1 (i - 2) = 0, - (X + ц + ic)n1 (i)+ХП 0 (i)+(i + 1)гП 0 (i +1) = 0. Для решения системы (2) построим итерационный (рекуррентный) алгоритм. Положим П( 0) = a, где a - некоторая произвольная положительная константа, П( i) = П 0 (i) + П1 (i), i = 0,1,2.., и запишем следующие равенства: Для i = 0: П1 (0 )=Хп 0 (0), П 0 (1)=X {(Х + ц)П1 (0)-ХП 0 (0)}. Для i = 1: 2: П1 (i)= П0 (i +1)= ц + 4-Я){(Х + /Ъ)П 0 (i )-[x(1 - H )+(i - 1)cH Ш1 (i -1)-ХЯП1 (i - 2)}, ^1^{(Х + ц + 7'а)П 10')- ХП 0 (i)}. С помощью системы (3) найдем П(i) = П0(i) + П1 (i), i = 0,1,2..., после чего нормируем ПП(i) = П(i)ДП(i). i=0 Этот алгоритм довольно прост в реализации и позволяет численно получить допредельные характеристики исследуемой RQ-системы. Следует отметить, что алгоритм применим только для исследования RQ-системы с простейшим входящим потоком, но позволяет сделать предположения о виде распределения вероятностей числа заявок на орбите при различных параметрах системы. 3. Численный анализ В результате численных экспериментов выявлено, что при уменьшении случайной задержки, которую осуществляет заявка на орбите в случае возникновения конфликта, распределение числа заявок на орбите имеет вид гауссовского. На рис. 3, 4 изображены графики распределения вероятностей числа заявок на орбите, полученного с помощью рекуррентного алгоритма и дискретизированного нормального распределения при разных значениях вероятности H и параметра о. Рис. 3. Изменение числа заявок на орбите для RQ-системы с коллизиями, H-настойчивостью и отказами при H = 0,4: a - X = 0,4, ц = 1, о = 0,1; b - X = 0,4, ц = 1, о = 0,001 Fig. 3. Variation the number of calls in orbit for RQ-system with collisions, H-persistence and rejections under H = 0,4: a - X = 0,4, ц = 1, о = 0,1; b - X = 0,4, ц = 1, о = 0,001 Рис. 4. Изменение числа заявок на орбите для RQ-системы с коллизиями, H-настойчивостью и отказами при H = 0,6: a - о = 0,1; b - о = 0,001 Fig. 4. Variation the number of calls in orbit for RQ-system with collisions, H-persistence and rejections under H = 0,6: a - о = 0,1; b - о = 0,001 Для сравнения распределения вероятностей, полученного с помощью рекуррентного алгоритма пп (z), и дискретизированного нормального распределения G, воспользуемся расстоянием Колмогорова: £ппф-ZGz >. i-0 i-0 _ Результаты сравнения для различных значений параметра о приведены в табл. 1. Таблица 1 Расстояние Колмогорова для RQ-системы с коллизиями при уменьшении о о о = 0,1 о = 0,05 о = 0,01 Значение Д для параметров Л = 0,4, ц = 1, H = 0,4 0,049 0,023 0,004 Значение Д для параметров Л = 0,4, ц = 1, H = 0,8 0,022 0,01 0,0018 Значение Д для параметров Л = 0,8, ц = 1, H = 0,4 0,010 0,005 0,0009 Значение Д для параметров Л = 0,8, ц = 1, H = 0,8 0,002 0,01 0,0002 Приведенные в таблице значения показывают, что с уменьшением значения параметра о точность аппроксимации возрастает. Следует отметить, что существование стационарного режима в рассматриваемой системе зависит от значения H. Для H < 1 стационарный режим существует для любых значений интенсивности поступления первичных заявок. Если выполняется соотношение H = 1, то для существования стационарного режима необходимо ограничить поток первичных заявок [17]. 4. Вероятностные характеристики и показатели качества Выражения для вычисления показателей качества обслуживания заявок [27] следуют из их физического смысла и определяются через отношение интенсивностей анализируемых событий или суммирование стационарных вероятностей модели; к ним относятся: доля потерянных первичных и повторных заявок; среднее число повторных попыток соединения на одну первичную; среднее число отказов на одно установленное соединение; доля повторных вызовов в общем потоке поступающих заявок. Для анализа представляются технические характеристики рассматриваемой системы, значения которых приведены в табл. 2. Таблица 2 Технические характеристики функционирования RQ-системы с коллизиями и отказами Характеристики системы Параметры входящего потока Л = 0,2, ц = 1 Л = 0,4, ц = 1 Л = 0,6, ц = 1 Л = 1, ц = 1 о = 0,1 о = 0,001 о = 0,1 о = 0,001 о = 0,1 о = 0,1 o' II 00 о' II о' II ос о' II о' II ос о' II о' II оу. о' II о' II оо о' и о' II оу. о' II Интенсивность суммарного потока поступающих заявок N х + сту/пп(/) z=0 0,264 00 о си о' 0,264 СП о сп о' 0,665 1,005 0,667 о о о 1,176 2,288 2,363 5,833 Среднее число абонентов, повторяющих вызов N Е*пп(г) z=0 0,644 о 00 о 63,769 102,83 2,651 6,053 266,648 600,045 О ■п r-( ■п 16,877 13,629 48,327 Интенсивность отказов первичных и повторных заявок (1 - H )^ + сту/пп(/)^ 0,159 0,062 0,158 0,061 СП с*у о' О ГЧ о' О о о' О о ГЧ о' 0,705 0,458 00 1,167 Окончание табл. 2 Характеристики системы Параметры входящего потока X = 0,2, р = 1 X = 0,4, р = 1 X = 0,6, р = 1 X = 1, р = 1 о = 0,1 о = 0,001 о = 0,1 о = 0,001 о = 0,1 о = 0,1 o' II ОС о' II о' II ОС о' II о' II ОС о' II о' II ОС о' II о' II ОС о' II о' II ОС о' II Среднее число повторных попыток соединения на одну первичную N о^гПП(г) i=0 X 0,322 0,540 0,319 0,514 0,663 1,513 0,667 1,500 0,959 2,813 1,363 4,833 Доля повторных вызовов в общем потоке поступающих заявок N inn(i) i=0 N X + о^ inn(i) i=0 СП сд о' 0,351 0,242 о сп о' 0,399 0,602 О о о' 0,600 0,490 00 СП Г-; о' 0,577 0,829 Полученные данные показывают, что среднее число абонентов, повторяющих вызов, пропорционально растет с уменьшением значений параметра о, на долю повторных вызовов в общем потоке этот параметр особого влияния не оказывает. В области малых значений загрузки системы (р = Х/ц< 0,5) влияние повторных заявок несущественно, но при высокой загрузке и повышенной настойчивости абонента нарастающие потоки повторных вызовов, инициированные настойчивостью абонента в установлении соединения, приводят к лавинообразному росту трафика и переходу сети в состояние перегрузки. Это влияние становится особенно заметным, когда абонент абсолютно настойчив в установлении соединения, а значение интенсивности поступления первичных заявок близко к максимальной пропускной способности системы. Заключение В настоящей статье представлено исследование системы массового обслуживания с повторными вызовами и одним обслуживающим прибором, коллизиями заявок, Н-настойчивостью и отказом от обслуживания. С помощью разработанного авторами рекуррентного алгоритма сделан вывод об асимптотически гауссовском распределении вероятностей числа заявок на орбите и найдены технические характеристики системы, имеющие практическое значение для ее проектирования. Полученные результаты будут полезны при проектировании реальных информационных и телекоммуникационных систем. Вместе с тем следует отметить, что представленный алгоритм работает только для марковской модели, поэтому альтернативным подходом является применение метода асимптотического анализа, что позволяет найти асимптотическое распределение вероятностей числа заявок в источнике повторных вызовов. В дальнейших работах планируется обобщение результатов на случай с различными вероятностями настойчивости заявок, а также применение метода асимптотического анализа для модели с непуассоновскими входящими потоками.

Скачать электронную версию публикации