Моделирование в теории телетрафика

 

При моделировании реальный объект (или процесс) обычно представляется в идеализированной форме, упрощающей исследование. Выбор модели – сложная задача. Ее решение осуществляется с учетом множества факторов.

Во-первых, следует четко выделить цель моделирования. Одна и та же система телетрафика может изучаться с помощью разных моделей, если исследуются, например, свойства выходящего потока и влияние дисциплины обслуживания на вероятность потери заявок. Во-вторых, должны быть установлены основные причинно-следственные связи, важные для решаемой задачи. В-третьих, следует оценить желаемую точность результатов моделирования.

Существует несколько видов моделирования. Сначала в теории телетрафика были использованы методы моделирования, основанные на реальных аппаратных средствах. В частности, искусственное замыкание и размыкание шлейфа абонентской линии может считаться простейшим примером такого моделирования. Подобные эксперименты часто связывают с физическими моделями. Этим моделям свойственно изменение масштаба. К достоинствам физических моделей следует отнести их адекватность реальным объектам (или процессам). Обычно реализация этих моделей (если речь не идет об эксперименте на уже готовом оборудовании) обходится довольно дорого. Существенно то, что данный вид моделей не годится в тех случаях, когда оборудование только разрабатывается.

В настоящее время в теории телетрафика широко используется математическое моделирование. Оно незаменимо в тех случаях, когда исследование системы с помощью аналитических методов не представляется возможным. Также полезным математическое моделирование становится для проверки ряда допущений, свойственных аналитическим методам исследования систем телетрафика. Еще одна сфера применения – выбор числа членов в рядах, включающих бесконечное количество слагаемых.

Математическое моделирование систем телетрафика выполняется на ЭВМ за счет составления программы или набора программ. Эти программы имитируют процессы по обслуживанию заявок. Поэтому в теории телетрафика очень часто используется термин " имитационное моделирование".

Иногда используется сочетание физических и математических моделей. В частности, японские специалисты при изучении вероятностно-временных характеристик системы общеканальной сигнализации изготовили оборудование, а на его входе имитировали с помощью программного датчика случайных чисел входящий поток заявок – сигнальных единиц.

Моделирование случайных чисел – важный этап создания имитационных моделей. Известны два способа получения случайных чисел:

· использование физических генераторов (датчиков) случайных чисел (шум в радиоэлектронных приборах и трактах, радиоактивное излучение);

· составление программ, позволяющих получить псевдослучайные числа (они могут быть очень близки к случайным числам).

В настоящее время используются исключительно программные датчики. Обычно случайные числа генерируются так, чтобы они принадлежали интервалу . При этом закон распределения должен быть равномерным. Известно, что для интервала  функции  и  определяются следующим образом:

, .

 

На рисунке показаны функции  и . Основные характеристики равномерного распределения представлены в таблице.

Равномерное распределение на интервале

 

Математическое ожидание	Дисперсия	Асимметрия	Эксцесс
		0	–1, 2

 

Очевидно, что для интервала  среднее значение равно , а дисперсия – .

Моделированием случайной величины называют процесс получения ее значений. Это означает, что для формирования потока вызовов, поступающих, например, в АТС, следует разработать процесс, который позволяет выделять моменты занятия входов на ступени абонентского искания. Ступень абонентского искания в АТС – с точки зрения имитационной модели – может рассматриваться как система телетрафика.

Случайные числа, получаемые с помощью программных генераторов, необходимо проверить с точки зрения закона их распределения на интервале . Для этого можно использовать сравнение статистического и эмпирического распределений, выбрав заранее критерий согласия. Часто используется критерий Пирсона – .

Для того чтобы убедиться в " похожести" полученного распределения и закона равномерной плотности, целесообразно проверить математическое ожидание случайной величины (оно должно быть близким к 0, 5), коэффициент вариации (он должен быть равен примерно 0, 577), коэффициент асимметрии (он должен быть близок к нулю) и коэффициент эксцесса (он не должен заметно отличаться от минус 1, 2).

Получив случайные (псевдослучайные) числа, необходимо перейти к формированию последовательности случайных величин с исследуемым законом распределения. Обычно используется один из следующих приемов:

· метод обратных функций (то есть, прямого преобразования равномерно распределенных случайных чисел);

· приближенные методы;

· метод отсеивания чисел из первоначальной последовательности случайных чисел (метод генерации Неймана);

· методы, основанные на центральной предельной теореме.

Допустим, что случайная величина  непрерывна, а соответствующая плотность распределения вероятности задана функцией . Тогда функция распределения задана известным выражением:

.

Обычно в качестве нижнего предела интегрирования в теории телетрафика используется ноль.

Теорема. Если случайная величина  имеет плотность распределения вероятности , то распределение случайной величины

является равномерным на интервале . Из этой теоремы следует Правило: для того чтобы найти возможное значение  непрерывной случайной величины , надо выбрать случайное число  и решить относительно  такое уравнение:

.

Справедливо и обратное утверждение. Если  – функция распределения непрерывной случайной величины , а  – случайная величина с равномерным законом распределения на интервале , то случайная величина  имеет функцию распределения . В данном случае  – функция, обратная по отношению к .

Таким образом, необходимо:

· реализовать случайную величину , которая распределена равномерно на интервале ;

· вычислить значение случайной величины  по формуле .

Один из важных для теории телетрафика случаев – простейший входящий поток. Это означает, что случайная величина  подчиняется экспоненциальному закону:

.

Необходимо найти формулу для моделирования случайной величины  с помощью равномерно распределенной случайной величины .

Шаг 1. Находится функция, обратная по отношению к . Известно, что . Решение относительно  тривиально: .

Шаг 2. Очевидно, что случайная величина  (так же как и случайная величина ) равномерно распределена на отрезке . Поэтому справедлива также и формула следующего вида:  

Шаг 3. Теперь числа с экспоненциальным распределением могут быть получены из значений  по такой формуле: .

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

Три других метода получения требуемых законов распределения описаны в работах по моделированию. Одна из последних публикаций – монография [1].

Входящий поток заявок на входе СМО (системы телетрафика) может быть задан последовательностью появления требований: . С практической точки зрения удобнее оперировать длительностью промежутка между соседними требованиями: . Способ формирования величин  с заданным законом распределения был изложен выше. Теперь необходимо определить свойства СМО и проследить за временами обслуживания заявок и соответствующими процессами (потери и задержки).

В качестве примера моделирования рассматривается алгоритм, предложенный в монографии [2].

 

Рисунок 1

 

Рисунок 2

Оператор П₁ осуществляет ввод следующей исходной информации: Т_м – интервал моделирования; lkλ _вх, lkλ _обсл – коды закона распределения входящего потока и закона распределения длительности обслуживания заявок (здесь l – условный номер закона, а k и λ – его параметры¹⁾), t_осв0=0 – момент освобождения канала после обслуживания " нулевой" заявки; τ _{ож пред} – предельная длина ожидания; τ _{преб зад} – заданная длительность пребывания в системе заявки, обслуживание которой было завершено (на рисунках, в целях экономии места, индекс " преб" заменен на " пр" ).

Оператор Ф₂ производит выборку, случайного числа η в соответствии с установленным законом распределения входящего потока.

Оператор Фз формирует момент поступления очередной заявки t_j =t_j-1 + η, где t_j – момент поступления очередной заявки; t_j-1 – момент поступления предыдущей заявки.

Естественно, что в начале моделирования t_j-1=t₀=0. С помощью оператора р₄ осуществляется проверка, не вышел ли момент t_j поступления заявки за пределы интервала моделирования [0, Т_м] по условию t_j < Т_м.

Если условие не выполняется, то есть интервал моделирования исчерпан, следует переходить к обработке результатов моделирования, то есть к оператору A₃₁. Если же условие выполняется, то осуществляется подсчет числа поступивших заявок с помощью оператора А₅ по правилу j: =j+1.

Оператор А₆ подсчитывает текущее число заявок в очереди (m: = m+1), где m – длина очереди (число заявок в очереди), а также производит расчет квадрата длины очереди – m².

Оператор A₇ определяет длительность пребывания заявки в очереди τ _{ож j} : = t_осв – t_j, где τ _{ож j} – длительность пребывания, j-й заявки в очереди; t_осв – момент освобождения канала.

Оператор Р₈ проверяет, должна ли j-я заявка ждать в очереди или ее обслуживание начинается немедленно: τ _{ож j} ≤ 0.

При τ _{ож j} = 0 заявка поступает в систему точно в момент освобождения канала. Отрицательное значение τ _{ож j} показывает, что j-я заявка не ждала в очереди, а ждал канал, поскольку он освободился до прихода j-й заявки. Поэтому при выполнении условия управление передается оператору Ф₉, который фиксирует для j-й заявки факт отсутствия ожидания обслуживания (τ ож j: = 0), и далее оператору A₁₀ для подсчета общего числа заявок a, обслуженных без ожидания (a: =a+1).

Затем оператор A₁₁ подсчитывает длительность простоя канала τ _{прост j} перед обслуживанием j-й заявки (τ _{прост j} = t_j – t_осв), после чего управление передается оператору Р₁₂. Если же условие не выполняется, что свидетельствует об отсутствии простоя канала, управление от оператора Р₈ непосредственно передается оператору Ρ ₁₂. Последний проверяет, не превышает ли длительность ожидания j-й заявки предельного времени ожидания по условию τ _{ож j} ≤ τ _{ож пред}.

Если условие не выполняется, то есть длительность ожидания j-й заявки превышает предел, то такая заявка в соответствии с установленной нами дисциплиной ожидания должна покинуть систему по истечении τ _{ож пред}. С этой целью управление передается оператору Ф₁₃. Для этой заявки формируется предельная длительность пребывания в очереди τ _{ож j} = τ _{ож пред}. Поскольку такая заявка покидает систему необслуженной, ей присваивается нулевая длительность обслуживания τ _{обсл j}: =0, где τ _{обсл j} – длительность обслуживания j-й заявки. При этом число заявок в очереди уменьшается на единицу (m: =m – 1).

В рассматриваемом случае анализ судьбы j-й заявки на этом заканчивается и управление от оператора Ф₁₃ передается оператору А₂₃ для частной обработки данных и последующего моделирования поступления очередных заявок, что будет рассмотрено ниже.

Если условие выполняется, то есть заявка не покидает систему, управление от оператора P₁₂ передается оператору Ф₁₄ для формирования длительности обслуживания τ _{обсл j}, как случайной величины, подчиненной соответствующему закону распределения.

Затем оператор А₁₅ определяет момент освобождения канала после окончания обслуживания j-й заявки:

Оператор А₁₆ уменьшает число заявок в очереди на единицу (m: = m – 1) и подсчитывает новое значение m², а оператор А₁₇ подсчитывает длительность пребывания заявки в системе:

Оператор Р₁₈ осуществляет проверку условия

,

используемого при расчете закона распределения длительности пребывания заявки в системе, что будет показано ниже.

Оператор A₁₉ подсчитывает число заявок d, то есть определяет d: =d+1, а оператор А₂₀ находит общее число обслуженных заявок (с: =с+1). На этом заканчивается рассмотрение судьбы j-й заявки в системе, и управление передается оператору A21 для частной обработки данных и моделирования следующих заявок. Частная обработка заключается в подготовке некоторых сумм, необходимых для последующего статистического расчета соответствующих математических ожиданий и дисперсий ряда избранных величин, а также для расчета вероятностей некоторых величин, выбранных нами в качестве показателей, оценивающих эффективность системы массового обслуживания.

Вероятность появления любой из интересующих нас величин приближенно можно рассчитать через частость

,

где p(у) – вероятность появления величины y; j* – число заявок, поступивших в систему в течение интервала моделирования; y_j – значение величины у для j-й заявки.·

Статистическая оценка математического ожидания величины X рассчитывается по формуле

,

где x_j – значение величины X для j-й заявки.

Для расчета статистической оценки дисперсии величины X воспользуемся известной формулой

,

где  – дисперсия X; М[Х²] — математическое ожидание X²; (М[Х])² – квадрат математического ожидания величины X.

Соответственно статистическая оценка среднеквадратического отклонения величины X определяется по формуле:

.

Частная обработка данных по j-й заявке производится цепочкой операторов A₂₁–H₃₀. Для обслуженных заявок она заключается в последовательном накоплении следующих величин, необходимых для дальнейшего использования формул:

; ; ; ; ; ; ; ; .

Для необслуженных заявок, выбывших из очереди вследствие превышения предельной длительности ожидания, управление передается для частной обработки от оператора Ф₁₃ непосредственно оператору A₂₃, минуя операторы А₂₁ и A₂₂, поскольку нет необходимости вычислять величины τ _преб и . Накопление всех остальных сумм для необслуженных заявок ничем не отличается от аналогичных операций для обслуженных заявок.

После окончания всех этих подсчетов управление передается оператору H₃₀ для присвоения нулевых значений всем текущим величинам, связанным с судьбой j-й заявки, а затем оператору Ф₂ для моделирования судьбы следующей заявки.

Вернемся к оператору Р₄, когда условие не выполняется, то есть когда поступление очередной заявки происходит за пределами интервала моделирования и следует переходить к Общей обработке данных. При этом управление от оператора Р₄ передается оператору A₃₁. Цепочка операторов A₃₁ – A₃₆ производит общую обработку данных, то есть последовательный расчет оценок математических ожиданий и среднеквадратических отклонений для следующих величин:

–·длительности пребывания обслуженной заявки в системе (заявки, обслуживание которой завершено):

;

 

– длительности пребывания заявки в очереди

 

;

– длины очереди

;

После этого цепочка операторов A₃₇ – A₄₀:

– вероятность обслуживания заявки р_обсл=с/j^*;

– вероятность отказа в обслуживании р_отк=1 – с/j^*;

– вероятность обслуживания заявки без ожидания р_обо=а/j^*;

– вероятность пребывания обслуженной заявки в системе в течение времени, не превышающего заданного: p_преб (τ < τ _{преб зад})=d/j^* (под временем пребывания обслуженной заявки в системе понимается время нахождения заявки в очереди и под обслуживанием).

Оператор П₄₁ осуществляет печать рассчитанных величин.

Затем рассчитываются аналогичные статистические оценки простоя канала операторами А₄₂, A₄₃, А₄₄:

– длительность простоя канала

 

– среднеквадратическое отклонение

– вероятность простоя канала

Оператор П45 осуществляет печать этих величин, после чего оператор Я46 останавливает моделирование.

Следует отметить, что если провести по заданной модели дополнительные расчеты, изменяя величину τ _{преб зад} от нуля до бесконечности, то, используя полученный ряд величин p(τ < τ _{преб зад}), можно построить график функции p(τ < τ _{преб зад})=F(τ _{преб зад}). Этот график представляет собой функцию распределения длительности пребывания заявки в системе – основную интегральную характеристику СМО.

 

 

Литература

 

1. О.И. Шелухин, А.М. Тенякшев, А.В. Осин. Модели информационных систем. – М.: Радиотехника, 2005.

2. А.Л. Лифшиц, Э.А. Мальц. Статистическое моделирование систем массового обслуживания. – М.: Советское радио, 1978.

 

Лекция 15

⇐ Предыдущая9101112131415161718Следующая ⇒

Поделиться: