Вагиф Ш. Фейзиев НАХОЖДЕНИЕ ОПТИМАЛЬНОЙ СТРАТЕГИИ ВКЛЮЧЕНИЯ РЕЗЕРВНЫХ КАНАЛОВ В МНОГОСКОРОСТНЫХ СИСТЕМАХ ОБСЛУЖИВАНИЯ
Решается задача нахождения оптимальной стратегии включения в многоскоростных системах обслуживания без очередей. Цель управления включением резервных каналов состоит в минимизации суммарных экономических издержек в единицу времени стационарного режима, связанных с потерями вызовов и использованием резервных каналов.
Приводятся результаты численных экспериментов.Вирішується завдання знаходження оптимальної стратегії включення в багатошвидкісних системах обслуговування без черг. Мета управління включенням резервних каналів полягає в мінімізації сумарних економічних витрат в одиницю часу стаціонарного режиму, пов'язаних з втратами викликів і використанням резервних каналів. Наводяться результати чисельних експериментів.
The task of finding optimal strategy of including is solved in the multispeed systems of service without turns. The purpose of management including of the reserve ductings consists of minimization of total economic costs in time of the stationary mode unit, calls related to the losses and by the use of the reserve ductings. The results over of numeral experiments are brought.
Введение. Модели многоскоростных систем обслуживания (Multi Rate Queue, MRQ) достаточно адекватно описывают работу современных мультисервисных сетей обработки разнотипных вызовов. Анализ доступной литературы показал, что задачи расчета показателей качества обслуживания (Quality of Service, QoS) таких моделей достаточно подробно исследованы (см. например, [1;3] и приведенные там списки использованной литературы). Однако задачи оптимизации показателей QoS этих сетей не достаточно исследованы. Исходя из этого, в настоящей работе рассматривается одна задача такого рода. Здесь предлагается метод решения задачи нахождения оптимальной (в заданном смысле) стратегии включения резервных каналов в моделях MRQ без очередей.
Описание модели и постановка задачи.
Рассмотрим модель MRQ, в которой N > 1 каналов разделены на две группы: активные и резервные, т.е. N = A + R, где A > 1 указывает число активных каналов и R > 1 означает число резервных каналов, при этом все каналы являются идентичными. Активные каналы используются согласно полнодоступной схеме, а включение резервных каналов поддается управлению. Это означает, что использование резервных каналов связано с определенными экономическими издержками, и потому в моменты поступления разнотипных вызовов необходимо принимать решение об использование таких каналов.Входящие потоки вызовов являются пуассоновскими, при этом интенсивность i-го потока равна λi, i = 1,...,K, и вызовы из i-го потока требуют одновременно bi каналов. Время обслуживания вызовов i-го типа является показательно распределенной случайной величиной со средним μi-1, i=1,...,K. Если в момент поступления вызова любого типа количество свободных активных каналов является достаточным, то необходимое число активных каналов назначается для его обслуживания; в противном случае для этой цели могут быть использованы свободные резервные каналы. Вместе с тем, если суммарное число свободных каналов (активных и резервных) окажется недостаточным для обслуживания поступившего вызова, то он теряется с вероятностью 1.
Предположим, что потеря одного вызова i-го типа оценивается штрафом в c(i) условных единиц, i=1,...,K, а включение j резервных каналов в единицу времени приводит к штрафу d(j) условных единиц, j=1,...,R. Тогда задача нахождения оптимальной стратегии включения резервных каналов формулируется следующим образом: требуется найти такую стратегию включения резервных каналов, чтобы минимизировать суммарные штрафы в единицу времени стационарного режима, связанные с потерями вызовов различных типов и включением резервных каналов.
Алгоритм решения задачи. Состояние данной системы в произвольный момент времени можно описать K-мерным вектором n=(n1,...,nκ), где ni указывает число вызовов i-го типа в системе.
Множество возможных состояний системы определяется так:
число свободных активных каналов в этом состояние определяется как f(n) = A - (n,b), если f(n) ≥ 0, т.е. если f(n) < 0, то это означает, что в состояние n число используемых резервных каналов равно - f(n). Отсюда заключаем, что величина f(n)+R равна суммарному числу свободных активных и резервных каналов в состоянии n∈.S'. если f(n) > 0, а в случае f(n) < 0 указанная величина означает число свободных резервных каналов в состоянии n∈S. Поскольку активные каналы системы используются согласно полнодоступной схеме, то если в момент поступления вызова i-го типа система находится в состоянии n∈S, в котором f(n) ≥ bi, то поступивший вызов с вероятностью 1 принимается и для его обслуживания выделяются bi любых свободных активных каналов. Если в этот момент компоненты вектора состояния n удовлетворяют неравенству bi>f(n)+R, то поступивший вызов i-го типа теряется с вероятностью 1.
Альтернативные решения возможны в моменты поступления вызовов i-го типа, если в эти моменты система находится в одном из подклассов множества возможных состояний (1):
Ограничениями этой задачи являются (4) и система уравнений равновесия, которая составляется на основе соотношений (5):
Задача (11) - (15) всегда имеет оптимальное решение, согласно которому для каждого состояния n∈S1* лишь один параметр УМП может быть положительным, а другие, соответственно, равны нулю. Этот факт позволяет разработать нерандомизированную стратегию оптимального включения резервных каналов в моменты поступления разнотипных вызовов.
Численные результаты. На практике, особенно при исследовании моделей MRQ с большим числом типов вызовов, состояние системы не наблюдается полностью, т.е.
наблюдается лишь общее число занятых (свободных) каналов. Оптимальную стратегию, основанную лишь на информации о числе занятых (свободных) каналов, назовем субоптимальной. Здесь рассмотрим подход на основе имитационного моделирования к нахождению субоптимальной стратегии включения резервных каналов и покажем возможности этого подхода для исследования подобных задач.Пусть активные каналы, как и прежде, используются согласно полнодоступной схеме, а количества резервных каналов, которые могут быть использованы для обслуживания вызовов /-го типа, ограничены величиной ri, при этом r1 +... +rκ ≥ R. Здесь задача оптимизации системы заключается в нахождении таких значений ri, i=1,...,K, чтобы минимизировать суммарные штрафы (6).
Программа имитационного моделирования разработана и использована для нахождения субоптимальной стратегии в модели MRQ с параметрами A=20, R=10, K=2, b1=1, b2=6, c(1)=c(2)=1, d(i)=i, i=1,...,6. В каждом прогоне имитационной программы были использованы 100.000 вызовов, полностью завершивших обслуживание. Количество повторений каждого эксперимента равно 5, а их средние были выбраны в качестве основных показателей QoS системы.
Соответствующие результаты показаны в табл.1. Субоптимальные решения из табл.1 определяются обычным способом выбора соответствующего элемента матрицы.
Таблица 1. Субоптимальная стратегия включения резервных каналов
Так, например, субоптимальной стратегии при ρ1=7 эрл и p2=3 эрл соответствует символ “о” на пересечении третьей строки и седьмого столбца, т.е. при этих нагрузках субоптимальной стратегией является r1=10 и r2=1.
Следует отметить, что с целью уменьшения числа переключений различных субоптимальных стратегий (что приводит к упрощению в реализации субоптимальных стратегий) отмеченные звездочкой стратегии могут быть заменены стратегией (10,1), так как максимальная разность между минимальными значениями соответствующих целевых функций (т.е.
суммарные штрафы) не превышает 0.5%.Заключение. В настоящей работе решена задача марковского программирования для нахождения оптимальной нерандомизированной стратегии включения резервных каналов в многоскоростных системах обслуживания с чистыми потерями. Рассмотрена также задача нахождения субоптимальной стратегии включения резервных каналов. Последная стратегия является эффективной в системах, в которых отсутствует полная информация об их состояниях в моменты принятия решений.
ЛИТЕРАТУРА
1. Башарин, Г.П. Лекции по математической теории телетрафика [Текст] / Г.П. Башарин. - М.:РУДН, 2007. - 268 с.
2. Меликов А.З. Телетрафик. Модели, методы, оптимизация [Текст] / А.З. Меликов, Л.А. Пономаренко, В.В. Паладюк. - К.: Политехника, 2007. - 256 с.
3. Меликов А.З. Приближенный расчет характеристик совместной передачи речи и данных в беспроводных сетях сотовой связи [Текст] / А.З. Меликов, В.Ш. Фейзиев // Электронное моделирование, 2007. - Т.29, №6. - С.47-59.
4. Melikov A.Z. Markov decision process approach to finding state-dependent CAC algorithm in broadband integrated network node [Text] / A.Z. Melikov, V.S. Feyziyev // Proc. of Int. conf. “Mathematical Methods for Increasing Efficiency of Information Telecommunication Networks”. - Minsk, 2007. - Vol.19. - РР. 142-146.
УДК 656.7