Оценка характеристик многопотоковых моделей с фиксированным числ. Параметры загрузки ip 82. 145. 210. 147 17 мая 2022 г., 00 30 05 Автоматика и телемеханика, 5, 2001 Системы массового обслуживания
 Скачать 302.89 Kb.
|
|
Math-Net.Ru Общероссийский математический портал В. Б. Иверсен, С. Н. Степанов, Оценка характеристик многопотоковых моде- лей с фиксированным числом повторений, Автомат. и телемех., 2001, вы- пуск 5, 105–115 Использование Общероссийского математического портала Math-Net.Ru подразумевает, что вы прочитали и согласны с пользовательским соглашением http://www.mathnet.ru/rus/agreement Параметры загрузки: IP: 82.145.210.147 17 мая 2022 г., 00:30:05 Автоматика и телемеханика, № 5, 2001 Системы массового обслуживания УДК 621.391:395 c ⃝ 2001 г. В. Б. ИВЕРСЕН, д-р техн. наук (Датский технический университет), С. Н. СТЕПАНОВ, д-р техн. наук (Институт проблем передачи информации РАН) ОЦЕНКА ХАРАКТЕРИСТИК МНОГОПОТОКОВЫХ МОДЕЛЕЙ С ФИКСИРОВАННЫМ ЧИСЛОМ ПОВТОРЕНИЙ 1 Излагается алгоритм приближенной оценки показателей обслуживания мно- гопотоковой модели цифровой линии в случае перегрузки и в ситуации, ког- да заблокированное сообщение имеет право на ограниченное число повторных передач. Метод расчета основан на предположении о пуассоновском характе- ре поступления повторных вызовов, позволяющем свести процедуру оценки к соответствующей модели с потерями, для которой существует эффективный алгоритм вычисления характеристик, основанный на алгоритме свертки. 1. Введение В сетях связи передача сообщения состоит из нескольких этапов. При переходе с одного этапа на другой сообщение может получить отказ из-за недостаточности ресурса или по каким-то другим причинам. В этой ситуации в протокол переда- чи обычно закладывается возможность ограниченного числа повторных попыток получить требуемое обслуживание. Если все они окончатся неудачно, сообщение считается потерянным и не возобновляется. В условиях перегрузки число таких по- вторных попыток может значительно увеличить входной поток нагрузки и серьезно ухудшить работу системы связи. Теоретическое исследование соответствующей проблемы может быть выполнено в рамках класса моделей систем массового обслуживания с повторными вызовами (см. обзоры соответствующих публикаций в [1–2]). Однако в проделанных иссле- дованиях практически отсутствуют результаты, которые можно использовать для анализа моделей с фиксированным числом попыток соединения. Это объясняет- ся сложным характером случайных процессов, описывающих функционирование соответствующих моделей. Количество попыток соединения, которое имеет право сделать абонент (или программное обеспечение, управляющее процессом передачи сообщения), приводит к появлению такого же количества компонент в случайном процессе, описывающем функционирование модели. Каждая компонента принима- ет бесконечное число значений, что делает нереальным получение численных и тем более аналитических решений. Если в модели с повторными вызовами положить вероятность повторного вызова равной нулю, то мы получаем обычную модель массового обслуживания с потеря- ми. Будем называть соответствующую модель базовой. Часто базовая модель имеет аналитическое решение или обладает каким-либо свойством, облегчающим расчет характеристик, например мультипликативной формой представления вектора ста- ционарных вероятностей. В данной работе предлагается процедура приближенной 1 Работа поддержана грантами Российского фонда фундаментальных исследований № 99-01- 00386 и INTAS 96-0828. 105 оценки характеристик обслуживания модели полнодоступной системы с произволь- ным числом пуассоновских входных потоков нагрузки, ограниченным доступом и конечным числом попыток соединения, основанная на замене потоков повторных вызовов на пуассоновские с соответствующим образом подобранными интенсивно- стями. Реализация данного подхода отличается эффективностью особенно в услови- ях большой загрузки и сводится к использованию эффективных методик расчета, развитых для базовой модели [3–4]. Материал распределен следующим образом. В разделе 2 приводится схема функ- ционирования модели. В следующем разделе обсуждаются эвристические предполо- жения, лежащие в основе метода и приводятся формулы для оценки неизвестных интенсивностей повторения и характеристик обслуживания. В разделе 4 рассмотре- ны численные примеры, иллюстрирующие эффективность использования метода. В Приложении к работе приведено краткое описание алгоритма оценки характеристик базовой модели, основанного на алгоритме свертки и игнорировании в процессе его реализации несущественных состояний. 2. Схема функционирования модели Рассмотрим цифровую линию, работающую со скоростью 𝑣, выраженной в ос- новных передаточных единицах. В качестве таковой может быть взята, например, скорость 64 Кбит/с или, как принято в технологии АТМ, наибольший общий дели- тель числа единиц ресурса цифровой линии, используемого для передачи каждым сообщением. На цифровую линию поступает 𝑘 потоков нагрузки. Сообщение 𝑠-го потока требует для своей передачи одну единицу ресурса цифровой линии и удер- живает этот ресурс в течение времени, имеющего экспоненциальное распределение с параметром, равным единице. Заметим, что основные результаты, полученные в данной работе, аналогичным образом переносятся и на случай произвольного рас- пределения длительности передачи. Если сообщению 𝑠-го потока не хватает ресурса для его обслуживания или на передаче уже находятся 𝑛 𝑠 сообщений данного пото- ка, то оно получает отказ и не возобновляется. Последняя из упомянутых причин отказа может привести к потере поступившего вызова несмотря на наличие ресур- са, достаточного для его обслуживания. Значение 𝑛 𝑠 может иметь интерпретацию величины полосы передачи, выраженной в основных передаточных единицах, мак- симально доступной сообщениям 𝑠-го потока (скорость доступа). Поток с номером 𝑠, 𝑠 = 1, . . . , 𝑘 представляет собой суперпозицию пуассонов- ского потока первичных вызовов интенсивности 𝜆 𝑠 и 𝑚 соответствующих потоков повторных вызовов, обусловленных одним, двумя, . . . , 𝑚 отказами в обслуживании. Предположим, что после отказа с номером 𝑟, 𝑟 = 1, 2, . . . , 𝑚 сообщение повторя- ется с вероятностью единица через случайное время, имеющее экспоненциальное распределение с параметром 𝜇. После (𝑚 + 1)-го отказа сообщение теряется без воз- обновления (детали исследуемой схемы передачи показаны на рисунке). Обозначим через 𝑗 𝑠,𝑟 (𝑡) число сообщений, составляющих 𝑠-й поток нагрузки, 𝑠 = = 1, . . . , 𝑘, и находящихся в момент времени 𝑡 в состоянии 𝑟-й повторной попытки, 𝑟 = 1, . . . , 𝑚, а через 𝑖 𝑠 (𝑡) обозначим число передаточных единиц линии, занятых в момент времени 𝑡 сообщениями 𝑠-го потока, 𝑠 = 1, . . . , 𝑘. Функционирование модели описывается многомерным марковским процессом 𝜉(𝑡) с компонентами 𝜉(𝑡) = ( 𝑗 1,1 (𝑡), . . . , 𝑗 1,𝑚 (𝑡), . . . , 𝑗 𝑘, 1 (𝑡), . . . , 𝑗 𝑘,𝑚 (𝑡), 𝑖 1 (𝑡), . . . , 𝑖 𝑘 (𝑡) ) Процесс 𝜉(𝑡) определен на пространстве состояний Ω, состоящем из векторов 𝜔 с компонентами 𝜔 = ( 𝑗 1,1 , . . . , 𝑗 1,𝑚 , . . . , 𝑗 𝑘, 1 , . . . , 𝑗 𝑘,𝑚 , 𝑖 1 , . . . , 𝑖 𝑘 ) , 106 107 удовлетворяющими свойствам 𝑗 𝑠,𝑟 = 0, 1, . . . , 𝑠 = 1, . . . , 𝑘; 𝑟 = 1, . . . , 𝑚; 0 ≤ 𝑖 𝑠 ≤ 𝑛 𝑠 , 𝑠 = 1, . . . , 𝑘; 𝑘 ∑ 𝑠 =1 𝑖 𝑠 ≤ 𝑣. Переходы 𝜉(𝑡) из 𝜔 приводят либо к увеличению, либо к уменьшению компонент вектора 𝜔 на единицу. Чтобы упростить обозначения состояний, будем с помощью верхних индексов + или − показывать только те компоненты, которые соответствен- но увеличиваются или уменьшаются на единицу. Например, (𝑖 + 𝑠 ) = (. . . , 𝑖 1 , . . . , 𝑖 𝑠− 1 , 𝑖 𝑠 + 1, 𝑖 𝑠 +1 , . . . , ), (𝑗 + 𝑠,𝑟 , 𝑗 − 𝑠,𝑟 +1 ) = (. . . , 𝑗 𝑠,𝑟− 1 , 𝑗 𝑠,𝑟 + 1, 𝑗 𝑠,𝑟 +1 − 1, 𝑗 𝑠,𝑟 +2 , . . . , ). В исследуемом случае стационарное распределение для 𝜉(𝑡) существует для всех ненулевых значений входных параметров модели. Обозначим стационарные вероят- ности 𝜉(𝑡) через 𝑃 (𝜔). Система уравнений равновесия, связывающая вероятности 𝑃 (𝜔), имеет вид 𝑘 ∑ 𝑠 =1 ( 𝜆 𝑠 + (𝑗 𝑠, 1 + ⋅ ⋅ ⋅ + 𝑗 𝑠,𝑚 )𝜇 + 𝑖 𝑠 ) 𝑃 (𝜔) = (1) = 𝑘 ∑ 𝑠 =1 𝜆 𝑠 𝑃 (𝑖 − 𝑠 )𝐼((𝑖 − 𝑠 ) ∈ Ω) + 𝑘 ∑ 𝑠 =1 𝜆 𝑠 𝑃 (𝑗 − 𝑠, 1 )𝐼((𝑗 − 𝑠, 1 ) ∈ Ω, (𝑖 + 𝑠 ) / ∈ Ω)+ + 𝑘 ∑ 𝑠 =1 𝑚 ∑ 𝑟 =1 (𝑗 𝑠,𝑟 + 1)𝜇𝑃 (𝑗 + 𝑠,𝑟 , 𝑖 − 𝑠 )𝐼((𝑖 − 𝑠 ) ∈ Ω)+ + 𝑘 ∑ 𝑠 =1 𝑚− 1 ∑ 𝑟 =1 (𝑗 𝑠,𝑟 + 1)𝜇𝑃 (𝑗 + 𝑠,𝑟 , 𝑗 − 𝑠,𝑟 +1 )𝐼((𝑗 − 𝑠,𝑟 +1 ) ∈ Ω, (𝑖 + 𝑠 ) / ∈ Ω)+ + 𝑘 ∑ 𝑠 =1 (𝑗 𝑠,𝑚 + 1)𝜇𝑃 (𝑗 + 𝑠,𝑚 )𝐼((𝑖 + 𝑚 ) / ∈ Ω) + 𝑘 ∑ 𝑠 =1 (𝑖 𝑠 + 1)𝑃 (𝑖 + 𝑠 )𝐼((𝑖 + 𝑠 ) ∈ Ω). Уравнение (1) справедливо для всех 𝜔 ∈ Ω. Здесь 𝐼(⋅) – индикаторная функция, принимающая значение единица, если условие, сформулированное в скобках выпол- нено, и значение ноль в противоположном случае. Для значений 𝑃 (𝜔) выполнено нормирующее условие ∑ 𝜔∈ Ω 𝑃 (𝜔) = 1. Поток нагрузки с номером 𝑠 характеризуется средним числом основных переда- точных единиц, занятых сообщениями соответствующего потока, 𝐼 𝑠 ; средним числом сообщений, находящихся в состоянии 𝑟-й попытки повторения 𝐽 𝑠,𝑟 , 𝑟 = 1, 2, . . . , 𝑚; средним числом сообщений, находящихся в состоянии 𝑟-й попытки повторения в ситуации блокировки для сообщений 𝑠-го потока 𝑊 𝑠,𝑟 , 𝑟 = 1, 2, . . . , 𝑚 и долей вре- мени нахождения модели в состоянии блокировки для сообщений 𝑠-го потока 𝜋 𝑠,𝑡 Введенные характеристики формально определяются из следующих соотношений 𝐼 𝑠 = ∑ 𝜔∈ Ω 𝑃 (𝜔)𝑖 𝑠 , 𝜋 𝑠,𝑡 = ∑ 𝜔∈𝐵 𝑠 𝑃 (𝜔), (2) 𝐽 𝑠,𝑟 = ∑ 𝜔∈ Ω 𝑃 (𝜔)𝑗 𝑠,𝑟 , 𝑊 𝑠,𝑟 = ∑ 𝜔∈𝐵 𝑠 𝑃 (𝜔)𝑗 𝑠,𝑟 , 𝑟 = 1, 2, . . . , 𝑚, 108 где 𝑠 = 1, 2, . . . , 𝑘, а во множество 𝐵 𝑠 включаются состояния, удовлетворяющие свойствам {𝜔 ∈ 𝐵 𝑠 ∣ 𝑖 𝑠 = 𝑛 𝑠 или 𝑖 1 + ⋅ ⋅ ⋅ + 𝑖 𝑘 = 𝑣 }. Назовем (2) основными стационарными характеристиками 𝑠-го потока нагрузки. Другие характеристики могут быть выражены через основные с помощью простых соотношений. Например, доля потерянных сообщений 𝜋 𝑠,𝑐 , определяемая как отно- шение интенсивности всех потерянных сообщений к суммарной интенсивности их поступления, может быть найдена с помощью равенства 𝜋 𝑠,𝑐 = 𝜆 𝑠 𝜋 𝑠,𝑡 + (𝑊 𝑠, 1 + ⋅ ⋅ ⋅ + 𝑊 𝑠,𝑚 )𝜇 𝜆 𝑠 + (𝐽 𝑠, 1 + ⋅ ⋅ ⋅ + 𝐽 𝑠,𝑚 )𝜇 (3) Основные характеристики 𝑠-го потока нагрузки 𝑠 = 1, . . . , 𝑘 связаны законами со- хранения, имеющими вид 𝜆 𝑠 + (𝐽 𝑠, 1 + ⋅ ⋅ ⋅ + 𝐽 𝑠,𝑚 )𝜇 = 𝜆 𝑠 𝜋 𝑠,𝑡 + (𝑊 𝑠, 1 + ⋅ ⋅ ⋅ + 𝑊 𝑠,𝑚 )𝜇 + 𝐼 𝑠 , (4) 𝐽 𝑠, 1 𝜇 = 𝜆 𝑠 𝜋 𝑠,𝑡 , 𝐽 𝑠, 2 = 𝑊 𝑠, 1 , . . . , 𝐽 𝑠,𝑚 = 𝑊 𝑠,𝑚− 1 Для доказательства (4), достаточно умножить систему уравнений (1) последова- тельно на 𝑖 𝑠 , 𝑗 𝑠, 1 , . . . , 𝑗 𝑠,𝑚 и просуммировать полученные соотношения по всем 𝜔 ∈ Ω (более детально вывод законов сохранения для моделей с повторными вызовами ис- следован в [1, 5]). 3. Приближенный метод Понятно, что процесс поступления повторных вызовов зависит от предыстории функционирования модели. Повторное обращение к обслуживанию после отказа, вызванного блокировкой, с б´ольшей вероятностью закончится неудачно, чем в пер- вичной попытке. Ясно, что данная зависимость убывает с увеличением интервала времени между повторными вызовами. В этой ситуации можно приближенно счи- тать поток повторных вызовов пуассоновским с некой неизвестной интенсивностью. Соответствующий подход довольно часто используется при построении приближен- ных методов оценки характеристик моделей с повторными вызовами [1, 6]. Объясня- ется это тем, что здесь процедура расчета сводится к применению методов, развитых для базовой модели. В исследуемом случае для оценки показателей обслуживания нагрузки в базовой модели можно использовать эффективный алгоритм, основан- ный на использовании свертки [3, 4]. Поскольку в этой модели рассчитываемые характеристики не зависят от типа распределения времени передачи, то данный подход можно также использовать и для оценки соответствующей схемы передачи с повторными вызовами и произвольным распределением времени занятия переда- точного ресурса линии. Построим упрощенную версию исследуемой модели предположив, что для 𝑠-го потока нагрузки поток повторных вызовов, обусловленных 𝑟 подряд отказами в об- служивании, будет пуассоновским с интенсивностью 𝑥 𝑠,𝑟 . Проблему определения 𝑥 𝑠,𝑟 обсудим несколько позднее. Все остальные предположения, сделанные при постро- ении анализируемой модели, остаются неизменными. Обозначим через Λ 𝑠 общую интенсивность 𝑠-го потока нагрузки. Значение Λ 𝑠 находится из соотношения Λ 𝑠 = 𝜆 𝑠 + 𝑥 𝑠, 1 + ⋅ ⋅ ⋅ + 𝑥 𝑠,𝑚 , 𝑠 = 1, . . . , 𝑘. (5) Обозначим через 𝑖 𝑠 (𝑡) число передаточных единиц линии, занятых в момент вре- мени 𝑡 на обслуживание сообщений 𝑠-го потока. Вспомогательная модель описыва- ется марковским процессом 𝜉(𝑡) = (𝑖 1 (𝑡), 𝑖 2 (𝑡), . . . , 𝑖 𝑘 (𝑡)), определенным на простран- стве состояний 𝑆 со свойствами (𝑖 1 , . . . , 𝑖 𝑘 ) ∈ 𝑆, 0 ≤ 𝑖 𝑠 ≤ 𝑛 𝑠 , 𝑠 = 1, . . . , 𝑘, 𝑘 ∑ 𝑠 =1 𝑖 𝑠 ≤ 𝑣. 109 Обозначим через 𝑃 (𝑖 1 , . . . , 𝑖 𝑘 ) стационарные вероятности процесса 𝜉(𝑡). Значения 𝑃 (𝑖 1 , . . . , 𝑖 𝑘 ) обладают свойством мультипликативности 𝑃 (𝑖 1 , . . . , 𝑖 𝑘 ) = 𝑃 (0, . . . , 0) Λ 𝑖 1 1 𝑖 1 ! Λ 𝑖 2 2 𝑖 2 ! Λ 𝑖 𝑘 𝑘 𝑖 𝑘 ! , (𝑖 1 , . . . , 𝑖 𝑘 ) ∈ 𝑆. (6) Во вспомогательной модели все входные потоки являются пуассоновскими. Это означает, что вероятности потерь по времени и по вызовам совпадают. Обозначим соответствующую характеристику для 𝑠-го потока нагрузки через 𝑃 𝑠 . Она будет оценкой как 𝜋 𝑠,𝑡 , так и 𝜋 𝑠,𝑐 . Для других характеристик вспомогательной модели, используемых для оценки соответствующих показателей исходной модели, будем использовать те же символы, что были введены для исходной модели, только с ин- дексом 𝑎 вверху. Введем соответствующие характеристики: 𝑃 𝑠 = ∑ (𝑖 1 ,...,𝑖 𝑘 )∈𝐷 𝑠 𝑃 (𝑖 1 , . . . , 𝑖 𝑘 ), (7) 𝐼 𝑎 𝑠 = ∑ (𝑖 1 ,...,𝑖 𝑘 )∈𝑆 𝑃 (𝑖 1 , . . . , 𝑖 𝑘 )𝑖 𝑠 = (𝜆 𝑠 + 𝑥 𝑠, 1 + ⋅ ⋅ ⋅ + 𝑥 𝑠,𝑚 )(1 − 𝑃 𝑠 ), 𝐽 𝑎 𝑠, 1 = 𝑥 𝑠, 1 /𝜇, . . . , 𝐽 𝑎 𝑠,𝑚 = 𝑥 𝑠,𝑚 /𝜇, 𝑊 𝑎 𝑠, 1 = 𝑥 𝑠, 1 𝑃 𝑠 /𝜇, . . . , 𝑊 𝑎 𝑠,𝑚 = 𝑥 𝑠,𝑚 𝑃 𝑠 /𝜇, где 𝑠 = 1, . . . , 𝑘, а множество 𝐷 𝑠 состоит из состояний, имеющих свойства {(𝑖 1 , . . . . . . , 𝑖 𝑘 ) ∈ 𝐷 𝑠 ∣ 𝑖 𝑠 = 𝑛 𝑠 или 𝑖 1 + ⋅ ⋅ ⋅ + 𝑖 𝑘 = 𝑣 }. Из приведенных формул можно заключить, что все представляющие интерес ха- рактеристики можно выразить через 𝑃 𝑠 . Значение 𝑃 𝑠 легко находится с помощью алгоритма свертки, дополненного процедурой игнорирования в процессе реализации состояний, имеющих пренебрежимо малую вероятность существования [4, 5]. Вели- чина 𝑃 𝑠 зависит от неизвестных интенсивностей повторных вызовов. Рассмотрим процедуру определения 𝑥 𝑠, 1 , . . . , 𝑥 𝑠,𝑚 , 𝑠 = 1, . . . , 𝑘. Предположим, что законы сохранения (4) будут также выполняться и для вве- денных оценок 𝑃 𝑠 , 𝐼 𝑎 𝑠 , 𝐽 𝑎 𝑠, 1 , . . . , 𝐽 𝑎 𝑠,𝑚 , 𝑊 𝑎 𝑠, 1 ,. . . , 𝑊 𝑎 𝑠,𝑚 , 𝑠 = 1, 2, . . . , 𝑘. Нетрудно прове- рить, что первое из соотношений (4) выполняется для любых значений 𝑥 𝑠, 1 , . . . , 𝑥 𝑠,𝑚 , 𝑠 = 1, . . . , 𝑘. Другие дают систему неявных уравнений для определения 𝑥 𝑠, 1 , . . . , 𝑥 𝑠,𝑚 , 𝑠 = 1, . . . , 𝑘: 𝜆 𝑠 + 𝑥 𝑠, 1 + ⋅ ⋅ ⋅ + 𝑥 𝑠,𝑚 = 𝜆 𝑠 (1 + 𝑃 𝑠 + ⋅ ⋅ ⋅ + 𝑃 𝑚 𝑠 ), 𝑠 = 1, 2, . . . , 𝑘. (8) Правая часть (8) зависит от Λ 𝑠 = 𝜆 𝑠 + 𝑥 𝑠, 1 + ⋅ ⋅ ⋅ + 𝑥 𝑠,𝑚 , 𝑠 = 1, . . . , 𝑘 через 𝑃 𝑠 . Чтобы обозначить соответствующую зависимость, определим вектор Λ = (Λ 1 , . . . , Λ 𝑘 ) и перепишем (8) в виде Λ 𝑠 = 𝜆 𝑠 (1 + 𝑃 𝑠 (Λ) + ⋅ ⋅ ⋅ + 𝑃 𝑚 𝑠 (Λ)) , 𝑠 = 1, 2, . . . , 𝑘. (9) Допустим, мы нашли значения Λ 𝑠 , 𝑠 = 1, 2, . . . , 𝑘, удовлетворяющие (9). Тогда соотношения (4) дают нам величины неизвестных интенсивностей повторения 𝑥 𝑠, 1 = 𝜆 𝑠 𝑃 𝑠 (Λ), 𝑥 𝑠, 2 = 𝜆 𝑠 𝑃 2 𝑠 (Λ), . . . , 𝑥 𝑠,𝑚 = 𝜆 𝑠 𝑃 𝑚 𝑠 (Λ), 𝑠 = 1, 2, . . . , 𝑘 и, следовательно, оценки (7). Найдем решение (9). Значения Λ 𝑠 , 𝑠 = 1, 2, . . . , 𝑘 могут быть найдены очень просто, если воспользоваться рекурсивными формулами Λ (𝑓 ) 𝑠 = 𝜆 𝑠 ( 1 + 𝑃 𝑠 ( Λ (𝑓 −1) ) + ⋅ ⋅ ⋅ + 𝑃 𝑚 𝑠 ( Λ (𝑓 −1) )) , 𝑠 = 1, 2, . . . , 𝑘, 110 где 𝑓 = 1, 2, . . . , Λ (𝑓 ) = ( Λ (𝑓 ) 1 , . . . , Λ (𝑓 ) 𝑘 ) с начальными значениями Λ (0) 𝑠 = 𝜆 𝑠 , 𝑠 = 1, 2, . . . , 𝑘. Из предыдущих рассуждений следует, что для определения Λ 𝑠 , 𝑠 = 1, 2, . . . , 𝑘, а следовательно, и оценок всех характеристик исследуемой модели с повторными вы- зовами достаточно рассчитать вероятности индивидуальных блокировок в базовой модели для некоторой последовательности Λ (𝑓 ) , 𝑓 = 1, 2, . . . , значений интенсив- ностей входных потоков. В силу хорошей сходимости данная последовательность состоит из небольшого числа элементов, зависящего вообще говоря от значений входных параметров и точности расчетов. Проблему оценки индивидуальных по- терь для базовой модели нетрудно решить с помощью алгоритма свертки, допол- ненного процедурой игнорирования состояний с пренебрежимо малой вероятностью существования (см. Приложение). 4. Численные результаты Точный расчет характеристик введенной модели требует очень много усилий и может быть выполнен только на основе решения системы уравнений равновесия (1) методом последовательных приближений. Для его реализации необходимо ограни- чить число состояний в исследуемом марковском процессе. По этой причине ограни- чимся только численными результатами, полученными для однопотоковой модели с фиксированным числом повторных попыток соединения. В последующих выражени- ях опустим нижний индекс 𝑠, поскольку у нас имеется только один поток нагрузки. Входные параметры принимают значения: 𝑣 = 10, 𝜇 = 1, 𝜆 = 8, 10; 𝑚 = 1, 2, 3, 4, 5. В таблице приведены точные значения вероятности потерь по времени 𝜋 𝑡 , опре- деленной соотношением (2), и по вызовам 𝜋 𝑐 , определенной соотношением (3), и их оценка 𝑃 , определенная равенством (7) и найденная с использованием вспомогатель- ной модели. Столбец 𝐸 𝑣 (𝜆) показывает значение вероятности, найденное на основе формулы Эрланга. Из содержания таблицы можно сделать вывод о хорошей точно- сти приближенной оценки, особенно в случае перегрузки. В таблице эта ситуация соответствует случаю 𝜆 = 10. С увеличением нагрузки возрастает точность оценки вероятности потерь по времени. С уменьшением нагрузки более точно оценивается вероятность потерь по времени. 5. Заключение Рассмотрен алгоритм приближенной оценки показателей передачи многопото- ковой модели цифровой линии в случае перегрузки и в ситуации, когда абонент имеет право на ограниченное число повторных вызовов. Метод расчета основан на Сравнение точной и приближенной оценки значений потерь для однопотоковой модели с ограниченным числом повторных попыток 𝑚 𝜆 = 8 𝜆 = 10 𝜋 𝑡 𝜋 𝑐 𝑃 𝐸 𝑣 (𝜆) 𝜋 𝑡 𝜋 𝑐 𝑃 𝐸 𝑣 (𝜆) 1 0,1854 0,2088 0,1937 0,1217 0,3422 0,3670 0,3650 0,2146 2 0,2229 0,2614 0,2228 0,1217 0,4293 0,4650 0,4612 0,2146 3 0,2448 0,2937 0,2326 0,1217 0,4921 0,5329 0,5290 0,2146 4 0,2579 0,3140 0,2353 0,1217 0,5399 0,5831 0,5798 0,2146 5 0,2658 0,3269 0,2360 0,1217 0,5777 0,6220 0,6195 0,2146 111 предположении о пуассоновском характере поступления повторных вызовов. Дан- ное условие позволяет свести процедуру оценки характеристик модели с повторными вызовами к соответствующей модели с потерями, для которой существует эффек- тивный алгоритм вычисления характеристик, основанный на применении алгоритма свертки, дополненного процедурой игнорирования состояний с пренебрежимо малой вероятностью существования. П Р И Л О Ж Е Н И Е Базовая модель, используемая при построении модели с повторными вызовами, имеет мультипликативную форму представления вектора стационарных вероятно- стей. Основной вычислительной проблемой при определении характеристик соответ- ствующего класса моделей является вычисление нормировочной константы. Среди имеющихся алгоритмов, направленных на решение соответствующей задачи, наибо- лее удачным можно назвать метод, основанный на использовании свертки. Помимо легкости реализации к достоинствам данного подхода следует отнести возможность игнорировать в процессе счета состояния с пренебрежимо малой вероятностью су- ществования. Приведем основные шаги данного подхода. Основная версия алгоритма свертки. Сверткой двух векторов 𝑥 = (𝑥(0), 𝑥(1), . . . . . . , 𝑥(𝑎 𝑥 )) и 𝑦 = (𝑦(0), 𝑦(1), . . . , 𝑦(𝑎 𝑦 )) назовем вектор 𝑧 с компонентами 𝑧(𝑖) = 𝑢 (𝑖) ∑ 𝑗 =ℓ(𝑖) 𝑥(𝑖 − 𝑗)𝑦(𝑗), 𝑖 = 0, 1, . . . , 𝑎 𝑧 , где функции 𝑢(𝑖), ℓ(𝑖) определены соотношениями 𝑢(𝑖) = { 𝑖, 0 ≤ 𝑖 < 𝑎 𝑦 , 𝑎 𝑦 , 𝑎 𝑦 ≤ 𝑖 ≤ 𝑎 𝑧 , ℓ(𝑖) = { 0, 0 ≤ 𝑖 < 𝑎 𝑥 , 𝑖 − 𝑎 𝑥 , 𝑎 𝑥 ≤ 𝑖 ≤ 𝑎 𝑧 Наличие свойства мультипликативности позволяет найти оценки характеристик передачи всех потоков выполнив следующую схему действий. 1. Находятся компоненты 𝑃 𝑠 (𝑖 𝑠 ), 𝑖 𝑠 = 0, 1, . . . , 𝑛 𝑠 вектора 𝑃 𝑠 ненормированных значений стационарных вероятностей числа передаточных единиц линии, занятых сообщениями 𝑠-го потока в ситуации, когда на передачу предлагаются только сооб- щения 𝑠-го потока. Данные расчеты делаются для всех 𝑘 потоков, совместно пере- дающихся по линии. 2. В произвольном порядке (в последующих выражениях в порядке нумерации входных потоков) выполняется свертка всех 𝑘 индивидуальных распределений 𝑃 𝑠 Обозначим через 𝑃 (𝑟) результат свертки первых 𝑟 векторов 𝑃 𝑠 3. При выполнении последней свертки после нормировки находятся вероятности 𝑃 (𝑖) пребывания модели в состоянии с 𝑖 занятыми передаточными единицами 𝑃 (𝑖) = 𝑢 (𝑖) ∑ 𝑗 =𝑙(𝑖) 𝑃 (𝑘−1) (𝑖 − 𝑗)𝑃 𝑘 (𝑗), 𝑖 = 0, 1, . . . , 𝑛 и индивидуальные характеристики передачи 𝑘-го потока. 𝑃 𝑘 = 𝑃 (𝑣) + 𝑃 𝑘 (𝑛 𝑘 ) 𝑣− 1 ∑ 𝑖 =𝑛 𝑘 𝑃 (𝑘−1) (𝑖 − 𝑛 𝑘 ), 𝐼 𝑘 = 𝑣 ∑ 𝑖 =1 𝑢 (𝑖) ∑ 𝑗 =ℓ(𝑖) 𝑃 (𝑘−1) (𝑖 − 𝑗)𝑃 𝑘 (𝑗)𝑗. 112 Характеристики всех потоков находятся после выполнения введенной схемы свер- ток с каждым из потоков, поставленным последним в используемой последователь- ности. Понятно, что расчет всех характеристик потребует 𝑘(𝑘 − 1) сверток. Эффек- тивность данного подхода можно повысить как за счет уменьшения числа сверток, которые необходимо выполнить для оценки показателей обслуживания всех пото- ков, так и в результате уменьшения числа операций при проведении одной свертки, достигаемого в результате игнорирования в процессе счета несущественных состоя- ний. Выполнение процедуры свертки с запоминанием промежуточных результа- тов. Представим 𝑘 в двоичной форме 𝑘 = 2 ℓ 1 + 2 ℓ 2 + ⋅ ⋅ ⋅ + 2 ℓ 𝑛 (10) и поставим в соответствие каждому из 𝑛 слагаемых 2 ℓ 𝑟 , 𝑟 = 1, . . . , 𝑛 в (10) двоичное дерево, состоящее из (ℓ 𝑟 + 1) уровней, где нулевой уровень содержит 2 ℓ 𝑟 концевых вершин, а на уровне ℓ 𝑟 находится корневая вершина. Условимся в дальнейшем на- зывать вершины, находящиеся на одном уровне, например 𝑎-м, и связанные с общей вершиной на (𝑎 + 1)-м уровне, братьями. Общая вершина по отношению к ним будет отцом, а они по отношению к нему – сыновьями. Предположим, что все двоич- ные деревья, построенные в соответствии с представлением (10), занумерованы в порядке убывания двоичных групп, а уровни с одним и тем же номером располо- жены на одной линии. Приведем описание алгоритма оценки показателей передачи всех потоков, реализация которого потребует выполнения всего 4𝑘 − 6 операций свертки. Последовательность совершаемых действий выглядит следующим образом (тривальный случай 𝑛 = 1, ℓ 𝑛 = 0 не рассматривается). Ш а г 1. Занумеруем вершины каждого уровня слева направо. Ш а г 2. Последовательно, начиная с первого уровня, поставим в соответствие каждой вершине вектор, являющийся результатом свертки векторов, поставленных в соответствие его сыновьям. Ш а г 3. Поставим в соответствие корневой вершине двоичного дерева с номером 𝑟, 𝑟 = 1, . . . , 𝑛 свертку векторов, поставленных в соответствие корневым вершинам двоичных деревьев с номерами 𝑓 = 1, . . . , 𝑛, 𝑓 ∕= 𝑟. Ш а г 4. Для двоичного дерева 𝑟, 𝑟 = 1, . . . , 𝑛 поставим в соответствие каждой вершине уровня 𝑗 последовательно для 𝑗 = ℓ 𝑟 − 1, ℓ 𝑟 − 2, . . . , 0 вектор, являющийся результатом свертки вектора, поставленного в соответствие данной вершине, и век- тора, поставленного в соответствие его отцу, если 𝑗 = ℓ 𝑟 − 1, или брату отца, если 𝑗 < ℓ 𝑟 − 1. Данный шаг выполняется при ℓ 𝑟 > 0. Ш а г 5. На данном шаге определяются показатели передачи всех потоков. Для этого производится свертка вектора, поставленного в соответствие концевой вер- шине, с вектором, поставленным на первом шаге алгоритма в соответствие брату рассматриваемой вершины, или ей самой, если анализируемая двоичная группа со- стоит из одного элемента. Нетрудно проверить, что общее число операций свертки при реализации данного алгоритма равно 4𝑘 − 6, т.е. меньше чем четыре свертки на один входной поток. Выполнение процедуры свертки с удалением несущественных состояний. Пред- положим, что нам априори известны границы урезанного пространства состояний, где сосредоточена основная вероятностная масса, используемая при оценке харак- теристик модели. Из качественных соображений о ее функционировании можно предположить, что в пространство существенных состояний 𝑅 входят состояния 113 (𝑖 1 , . . . , 𝑖 𝑘 ), удовлетворяющие неравенствам 𝑏 ℓ 𝑠 ≤ 𝑖 𝑠 ≤ 𝑏 𝑢 𝑠 , 𝑠 = 1, 2, . . . , 𝑘, (11) 𝑏 ℓ (𝑗) ≤ 𝑗 ∑ 𝑚 =1 𝑖 𝑚 ≤ 𝑏 𝑢 (𝑗), 𝑗 = 2, 3, . . . , 𝑘. Здесь 𝑏 ℓ 𝑠 , 𝑏 𝑢 𝑠 , 𝑏 ℓ (𝑗), 𝑏 𝑢 (𝑗) – некоторые целые числа, зависящие от точности расчета характеристик передачи. Учет особенностей 𝑅 требует изменить алгоритм свертки. Выразим ненормиро- ванные значения индивидуальных распределений вероятностей через вероятность состояния, имеющего максимальную величину. Обозначим для 𝑠-го потока это со- стояние через 𝑖 ∗ 𝑠 . Ясно, что 𝑖 ∗ 𝑠 = min([𝜆 𝑠 ], 𝑛 𝑠 ), где квадратные скобки означают целую часть числа. Далее положим 𝑃 𝑠 (𝑖 ∗ 𝑠 ) = 1 и выразим через 𝑃 𝑠 (𝑖 ∗ 𝑠 ) оставшиеся вероят- ности индивидуального распределения. Данная процедура выполняется по двум или одному (это зависит от соотношения между 𝜆 𝑠 и 𝑛 𝑠 ) направлениям убывания зна- чений 𝑃 𝑠 (𝑖 𝑠 ) с использованием формул 𝑃 𝑠 (𝑖) = (𝑖 − 1)𝑃 𝑠 (𝑖 − 1) 𝜆 𝑠 , 𝑖 = 𝑖 ∗ 𝑠 + 1, 𝑖 ∗ 𝑠 + 2, . . . , 𝑏 𝑢 𝑠 , 𝑃 𝑠 (𝑖) = 𝜆 𝑠 𝑃 𝑠 (𝑖 + 1) 𝑖 , 𝑖 = 𝑖 ∗ 𝑠 − 1, 𝑖 ∗ 𝑠 − 2, . . . , 𝑏 ℓ 𝑠 Здесь 𝑏 𝑢 𝑠 , 𝑏 ℓ 𝑠 – соответственно верхний и нижний уровни урезания индивидуального распределения 𝑠-го потока. Подобные расчеты делаются для всех 𝑘 потоков. Полу- ченные распределения нормируются. Сверткой двух урезанных векторов 𝑥 = (𝑥(𝑡 ℓ 𝑥 ), 𝑥(𝑡 ℓ 𝑥 + 1), . . . , 𝑥(𝑡 𝑢 𝑥 ) ) , 𝑦 = (𝑦(𝑡 ℓ 𝑦 ), 𝑦(𝑡 ℓ 𝑦 + 1), . . . , 𝑦(𝑡 𝑢 𝑦 ) ) будет вектор 𝑧 с компонентами 𝑧(𝑖) = 𝑢 (𝑖) ∑ 𝑗 =ℓ(𝑖) 𝑥(𝑖 − 𝑗)𝑦(𝑗), 𝑖 = 𝑡 ℓ 𝑧 , 𝑡 ℓ 𝑧 + 1, . . . , 𝑡 𝑢 𝑧 , где 𝑢(𝑖), ℓ(𝑖) определены из соотношений 𝑢(𝑖) = ⎧ ⎨ ⎩ 𝑖 − 𝑡 ℓ 𝑥 , 𝑡 ℓ 𝑧 ≤ 𝑖 < 𝑡 ℓ 𝑥 + 𝑡 𝑢 𝑦 𝑡 𝑢 𝑦 , 𝑡 ℓ 𝑥 + 𝑡 𝑢 𝑦 ≤ 𝑖 ≤ 𝑡 𝑢 𝑧 , ℓ(𝑖) = ⎧ ⎨ ⎩ 𝑡 ℓ 𝑦 , 𝑡 ℓ 𝑧 ≤ 𝑖 < 𝑡 𝑢 𝑥 + 𝑡 ℓ 𝑦 𝑖 − 𝑡 𝑢 𝑥 , 𝑡 𝑢 𝑥 + 𝑡 ℓ 𝑦 ≤ 𝑖 ≤ 𝑡 𝑢 𝑧 Последовательность выполнения сверток остается прежней. При оценке харак- теристик всех потоков необходимо иметь в виду наличие верхних и нижних уровней урезания для 𝑘 индивидуальных распределений и для 4𝑘 − 6 векторов, полученных в результате свертки отдельных групп индивидуальных распределений, в соответ- ствии с шагами 1–5 введенного алгоритма свертки. Для обоснованной реализации соответствующей идеи необходимо разработать средства, позволяющие априори на- ходить границы урезанного пространства состояний, обеспечивающего вычисление характеристик с заданной точностью, и знать формулы для оценки погрешности, вносимой в значение рассчитываемой характеристики удалением части состояний. Соответствующие результаты для исследуемой модели получены в [4]. 114 СПИСОК ЛИТЕРАТУРЫ 1. Степанов С.Н. Численные методы расчета систем с повторными вызовами М.: Наука, 1983. 2. Falin G.I., Templeton J.G.C. Retrial Queues. Chapman & Hall, 1997. 3. Iversen V.B. The exact evaluation of multi-service loss system with access control // Teleteknik. 1987. No. 2. P. 56–81. 4. Iversen V.B., Stepanov S.N. Numerical aspects of evaluating of individual blocking proba- bilities for product form queueing models of circuit switched telecommunication systems // Proc. 15th Int. Teletraffic Congress. Washington, 1997. P. 1327–1336. 5. Степанов С.Н. Интегральные соотношения равновесия для неполнодоступной системы с потерями и их применение // Пробл. передачи информ. 1980. Т. 16. Вып. 4. С. 88–93. 6. Степанов С.Н. Алгоритмы приближенного расчета систем с повторными вызовами // АиТ. 1983. № 1. С. 80–90. Статья представлена к публикации членом редколлегии В. В. Рыковым. Поступила в редакцию 1.08.2000 115 |