2.1 Построение модели

Реальный тракт передачи информации на междугородной сети состоит из большого числа участков, каждый из которых соответствует одному или нескольким этапам установления соединения. Примером такого тракта может служить упрощенная схема, приведенная на рисунке 2.1, где показан участок тракта (АТС-А), с помощью которого вызывающий абонент подключается к входящей линии междугородной станции АМТС-1. Далее соединение проходит через тракт исходящей междугородной станции АМТС-1, междугородный канал, входящую междугородную станцию АМТС-2 и городской участок тракта (УВСМ, АТС-в) вызываемого абонента. Часть элементов тракта для простоты на рисунке 2.1 не показана.

Рисунок 2.1 - Упрощенная схема подключения к АМТС

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

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

В результате получаем модель массового обслуживания устроенную следующим образом. Имеется полнодоступный пучок, который является аналогом пучка междугородных каналов. Процесс установления соединения разделен на шесть этапов. Первые три имеют нулевую длительность, длительности других - отличны от нуля. В модели различаем абонентов, повторяющих вызов трех видов, в соответствии с тремя типами отказов, различаемых абонентом: потери до входа в систему (после набора "8"), различные виды блокировок и занятость вызываемого абонента, а также отказы из-за неответа вызываемого абонента.

2.2 Процесс установления соединения на междугородней телефонной сети

Схема процесса установления соединения показана в приложении В. Установление соединения на междугородной сети происходит следующим образом: абонент А снимает трубку, слышит сигнал "ответ станции" РАТС 1, для выхода на АМТС 1 он набирает "8", после чего происходит занятие линии от РАТС 1 к АМТС 1, затем АМТС 1 посылает запрос АОН и получает комбинацию АОН абонента А. Далее абонент А слышит сигнал "ответ станции" от АМТС 1 и набирает номер абонента Б. Затем последовательно происходит передача начальных адресных сообщений (IAM) соответственно к МЦК 2 и к АМТС 2. От АМТС 2 идет занятие к РАТС 2 абонента Б и РАТС 2 посылает подтверждение занятия на АМТС 2. Затем АМТС 1 получает от АМТС 2 запрос на передачу последующего адресного сообщения (CR) и отправляет это последующее адресное сообщение (SAM).Далее РАТС 2 посылает адресное сообщение, что абонент Б свободен и от РАТС 1 к абоненту А идет сигнал "контроль посылки вызова", а в этот момент АМТС 2 посылает вызов РАТС 2 и от РАТС 2 к абоненту Б идет сигнал "посылка вызова". Абонент Б снимает трубку, устанавливается соединение и происходит фаза разговора. Затем происходит отбой абонента Б и РАТС 1 посылает сигнал разъединения к РАТС 2, а АМТС 1 посылает РАТС 1 сигнал освобождения и абонент А получает сигнал "занято" и устанавливается исходное состояние.

2.3 Два варианта модели прямого пучка каналов МТС

Первая (базовая) модель характеризуется наличием нескольких этапов в процессе установления соединения, после неудачного завершения каждого из которых абонент может повторить вызов. В результате выделяются три группы абонентов, повторяющих вызов соответственно из-за отказа станции после набора "8", после всех видов блокировок (включая занятость вызываемого абонента) н после неответа вызываемого абонента.

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

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

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

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

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

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

3. Расчет уточненной модели прямого пучка междугородной телефонной сети

3.1 Базовая модель

На полнодоступный пучок из х линий, являющихся аналогом прямого пучка каналов МТС, поступает пуассоновский поток первичных вызовов интенсивности л. Поступивший вызов занимает произвольную свободную линию на первый этап установления соединения, распределенный экспоненциально с параметром б1. После завершения первого этапа с вероятностью p1 вызов занимает линию на второй этап установления соединения или с вероятностью (1-p1) получает отказ. Длительность второго этапа имеет экспоненциальное распределение с параметром б2. После завершения второго этапа с вероятностью p2p3 вызов продолжает занимать линию на третий и четвертый этапы, длительностью которого будет иметь экспоненциальное распределение с параметрами соответственно б3ґ, б4, а с вероятностю p2 (1-p3) вызов продолжает занимать линию только на третий этап, длительность которого будет иметь экспоненциальное распределение с параметром б3ґ, и после его завершения вызов освободит линию. Так описывается процесс занятия линии вызовом. Перейдем к образованию источников повторных вызовов (ИПВ).

Первичный или повторный вызовы при поступлении в систему с вероятностью a1 получают отказ до попадания на вход пучка. Это событие с вероятностью с 1 приводит к появлению ИПВ первого типа, от которого следующий повторный вызов поступит через случайное время, имеющее экспоненциальное распределение с параметром м1. Пройдя первый барьер, первичный или повторный вызовы до попадания на вход пучка могут опять получить отказ уже с вероятностью a2. В этом случае следующий повторный вызов поступит через случайное время, имеющее экспоненциальное распределение с параметром м2. Далее ИПВ второго типа будет образовываться во всех случаях, когда абонент объясняет отказ в обслуживании блокировкой. а именно: это событие с вероятностями H1 и H2 (для первичной и повторной попытки) происходит, если заняты все каналы пучка, а также после неудачного завершения соответственно первого и второго этапа обслуживания с вероятностями z1 и z2.

ИIIВ третьего типа образуется после пеудачного завершения третьего этапа установления соединения. В этом случае с вероятностью z3 абонент повторит вызов через случайное время, имеющее экспоненциальное распределение с параметром м3.

Здесь напомним только, что; а 1 - вероятность получить отказ после набора "8", а 2 - после полного набора номера, но до попадания на канал; 1/б1- среднее время прохождения вызова по ГТС вызываемого города; 1/б2 - среднее время прохождения вызова по ГТС вызываемого города до вызываемого абонента, (1-р 2) - вероятность того, что вызываемый абонент занят, (1-р 3) - вероятность того, что вызываемый абонент не отвечает; 1/б3ґ - среднее время слушания сигнала контроля посылки вызова, в случае когда разговор не состоится, 1/б3ґґ - то же, но в случае, если разговор состоится, и 1/б4 - среднее время разговора.

Введем обозначения: jn(t), n=1,2,3, - число ИПВ n-го типа, повторяющих вызов в момент времени t; im(t) - число линий, занятых в момент времени t на m-й этап обслуживания; i3ґґ(t) - число линий, занятых в момент времени t на третий этап обслуживания, переходящего затем с вероятностью, равной единице, на четвертый этап (разговор); i3ґ- число линий, занятых в момент времени t на третий этап обслуживания, после завершения которого линия освобождается. Функционирование модели описывается марковским процессом

о(t) = { j1 (t), j2 (t), j2 (t), i1 (t), i2 (t), i3ґ (t), i3ґґ (t), i4(t) }

Рассмотрим некоторые пучки утончения базовой модели. Некоторые рассуждения, предваряющие введение утонченной модели. Обсудим мотивы, которыми вызвано уточнение базовой модели. Когда говорят о сложности той или иной модели с повторными вызовами, то обычно под этим понимают число компонент в случайном процессе, описывающем ее функционирование. Это формально отражает ту точность, а скорее детальность в описании взаимодействия абонента и обслуживающей системы, которая достигнута в модели. Отметим, что детальность можно понимать как вширь, так и вглубь, когда более точно учитывается предыстория взаимодействия вызова и обслуживающей системы, началом которой является первичная попытка установить соединение. В моделях с потерями предыстории нет, все вызовы для системы первичные (новые). В обычных моделях с повторными вызовами можно проследить предысторию на один шаг назад (если вызов повторный, то в предыдущей попытке соединения он получил отказ). Приведем пример модели, когда предыстория вызова прослеживается до конца. Речь идет о системе М|М|v с (Hi мi) - настойчивым абонентом. Используя понятие предыстории взаимодействия вызова и обслуживающей системы, можно модели с повторными вызовами разбить на классы по уровню сложности, где численным выражением уровня сложности будет число предыдущих попыток соединения, результат которых известен.

Таким образом. базовая модель имеет первый уровень сложности; модель пучка с учетом функции настойчивости до m-й попытки имеет m-й уровень сложности; модель М|М|v с (Hi мi) - настойчивым абонентом имеет бесконечный уровень сложности. Переход на следующий уровень для базовой модели прямого пучка даст возможность учесть ряд дополнительных аспектов взаимодействия абонента с междугородной телефонной сетью. Их можно условно разбить на две группы: 1) учет инерции состояния вызываемого абонента, состоящей в том, что, получив отказ из-за занятости (неответа) вызываемого абонента, вызывающий абонент в следующей попытке соединения уже стбольшей вероятностью получит отказ из-за занятости (неответа) вызываемого абонента; 2) более точный учет психологического фактора. Например, теперь мы можем отразить в модели следующее свойство функции настойчивости: если абонент получил сначала отказ из-за занятости вызываемого абонента, затем из-за блокировки, то это с большей вероятностью приведет к появлению повторного вызова, чем, скажем, после получения подряд двух отказов из-за неответа. К этим свойствам можно добавить еще некоторые.

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

Схема функционирования уточненной модели. Законы сохранения. Сначала условимся о некоторых обозначениях. Входные параметры в системе вызова, снабдим индексами, отражающими предысторию отношений рассматриваемого вызова с обслуживающей системой (на две попытки назад) в случае, если первая из них по времени была вызвана состоянием вызываемого абонента. Если обозначение параметра имеет вид p…,то речь идет о вероятности перехода с этапа на этап, если H…, - о функции настойчивости, причем для H… индексы в конце (1 или 2) говорят о том, что рассматривается соответственно первичная или повторная попытка. Состояние вызываемого абонента в попытке соединения обозначим НО (неответ) или НЗ (номер занят). Кроме того, буквой Б будем в случае необходимости обозначать блокировку, а Бґ - блокировку, не вызванную занятостью вызываемого абонента. Если в обозначении нет изменений указанного типа, то смысл параметра или характеристики остается тем же, что и в базовой модели.

Рассмотрим некоторые примеры: вероятность (1-рНЗНЗ) - это вероятность получить зависимость вызываемого абонента для вызова, имевшего отказ в предыдущей попытке соединения из-зи занятости вызываемого абонента; (1-рНЗНО) - вероятность оплучить неответ вызываемого абонента для вызова, получившего отказ из-за занятости вызываемого абоннета в предыдущей попытке соединения; ННОБ - натсойчивость абонента в случае, когда он сначала получил отказ из-за неответа вызываемого абонента, а затем из-за блокировки; ННО 1 - настойчивость абонента в случае, когда он в первичной попытке получил отказ из-зи неответа вызываемого абонента и так далее.

Результат взаимодействия абонента, получившего k отказов, и обслуживающей системы для модели исследуемого типа можно записать в виде вектора (И1, И2, И3,..., Иk), где Иi - принимает значения 8, Бґ, НЗ, НО. Здесь Иi - условный символ для обозначения причины появления повторного вызова, а i - номер неудачной попытки соединения i=1, 2,..., k. Чтобы упростить запись окончательных результатов, сделаем несколько предположений. Как было условлено ранее, в предыстории взаимодействия вызова и обслуживающей системы будем фиксировать лишь отказы после набора "8" и всех видов блокировок (кроме НЗ). Это приведет к тому, что объединяются в одну группу абоненты, имеющие, например, предыстории вида (НЗ, Бґ, Бґ, Бґ) = (НЗ) = (НЗ, 8, 8, 8, Бґ, Бґ) = (НЗ, НЗ).

Перейдем к определению компонент марковского процесса, описывающего функционирование модели. Чтобы сохранить изложение материала, проследим лишь, какие изменения произойдут в определении аналогичных компонент базовой модели. Число ИПВ 1-го и 2-го типов разделится на три составляющих. Обозначим {Бґ, 8} любую конечную комбинацию символов Бґ, 8. тогда компоненты марковского процесса, описывающего функционирование модели, можно определить следующим образом:

jНЗ 1(t) - …(…, НЗ, {Бґ, 8}, 8); jНО 1(t) - …(…, НЗ, {Бґ, 8}, 8); j2(t) - …({Бґ, 8}, Бґ); jНЗ 2(t) - …(..., НЗ,{Бґ, 8}, Бґ), (..., НЗ, {Бґ, 8}, НЗ), ({Бґ, 8}, НЗ), (..., НО,{Бґ, 8}, НЗ); jНО 2(t) - …(..., НО,{Бґ, 8}, Бґ).

Число повторяющих вызовы абонентов 3-го типа остается без изменения. Рассмотрим занятость линий на этапы обслуживания. Число линий, занятых на тот или иной этап, разделится на четыре состовляющих (например, для 1-го типа):

iП 1(t) - число линий, занятых в момент времени t, на 1-й этап обслуживания в первичной попытке соединения;

iПВ 1(t) - число линий, занятых в момент времени t, на 1-й этап обслуживания в повторной попытке, не вызванной состоянием вызываемого абонента;

iНЗ 1(t) - число линий, занятых в момент времени t, на 1-й этап обслуживания в повторной попытке, вызванной занятостью вызываемого абонента;

iНО 1(t) - число линий, занятых в момент времени t, на 1-й этап обслуживания в повторной попытке, вызванной неответом вызываемого абонента, и так далее.

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

J1µ1 = a1c1(л + J1µ1 + J2µ2); (3.1)

JНЗ 1µ1 = a1c1(JНЗ 1µ1 + JНЗ 2µ2);

JНО 1µ1 = a1c1(JНО 1µ1 + J2µ2 + JНО 2µ2);

J2µ2 = (1 - а 1) (а 2 (лH1 + J1µ1H2 + J2µ2H2) + (1 - а 1)(лрH1 + J1ґµ1H2 + J2ґµ2H2)) + ІП 1б1 (1 - p1) H1 + ІПВ1б1(1 - p1) H2;

JНЗ 2µ2 = (1 - а 1) (а 2(JНЗ 2µ1+ JНЗ 2µ2) + (1 - а 1) (JґНЗ 2µ1+ JґНЗ 2µ2))H2 + JНЗ 1б1(1 - p1) H2 + JР1б1(1 - p1) H1 + JРВ2б2(1 - p2) H2 + JНЗ 2б2(1 - pНЗНЗ) H2 + JНО 2б2(1 - pНОНЗ) HНОБ;

JНО 2µ2 = (1 - а 1) (а 2(JНО 1µ1+ JНО 2µ2 + J3µ3) + (1 - а 1) (JґНO1µ1 + JґНO2µ2 + Jґ3µ3)) HНОБ + JHO1б1(1 - p1) HНОБ;

J3µ3 = IґР3бґ3HНО 1 + IґРВ 3бґ3HНО 2 + IґНЗ 3бґ3HБНО + IґНО 3бґ3HНОНО;

IР1б1р 1 = IР2б2; IР2б2р 2р 3 = IґґР3бґґ3;

IРВ 1б1р 1 = IРВ 2б2; IРВ 2б2р 2р 3 = IґґРВ 3бґґ3;

IРВ 2б2р 2 (1 - р 3) = IґРВ 3бґ3; IґґРВ 3бґґ3 = IРВ 4б4;

IНЗ 1б1р 1 = IНЗ 2б2; IНЗ 2б2рНЗНЗрНЗНО = IґґНЗ 3бґґ3;

IНЗ 2б2рНЗНЗ(1 - рНЗНО) = IґНЗ 3бґ3; IґНЗ 3бґ3 = IНЗ 4б4

IНО 1б1р 1 = IНО 2б2; IНО 2б2рНОНЗрНОНО = IґґНО 2бґґ3;

IНО 2б2рНОНЗ(1 - рНОНО) = IНО 3бґ3; IґґНО 3бґґ3 = IНО 4б4;

л(1 - р) (1 - а 1) (1 - а 2) = ЙР1б1;

[(J1 - Jґ1)µ1 + (JНЗ 2 - JґНЗ 2) µ2](1 - а 1) (1 - а 2) = ЙРВ 1б1;

[(JНЗ 1 - JґНЗ 1)µ1 + (JНЗ 2 - JґНЗ 2) µ2](1 - а 1) (1 - а 2) = ЙНЗ 1б1;

[(JНО 1 - JґНО 1)µ1 + (JНО 2 - JґНО 2) µ2(JЗ - JґЗ)µ3](1 - а 1) (1 - а 2) = ЙНО 1б1.

3.2 Приближенный алгоритм расчета модели, основанный на использовании формулы Эрланга

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

Введем обозначения:

x1=J1µ1+J2µ2; x2=JНЗ 1µ1+JНЗ 2µ2; x3=JНО 1µ1+JНО 2µ2+J3µ3.

Тогда интенсивность потока повторных вызовов х определяют из решения неявного уравнения

х = х 1 + х 2 + х 3, (3.2)

где х 1, х 2, х 3 находят из формул

x1 = [л(а 1с 1 + (1 - а 1)(а 2 + (1 - а 2)(1 - р 1(1 - р(х))H1)]/[1 - a1c1 - (1 - a1)(a2 + (1 - a2)(1 - p1(1 - р(x))) H2],

x2 = xґ2/ xґґ2,

xґ2 = (1 - a1)(1 - a2)(1 - р(x))p1(лH1(1 - p2) + x1(H2(1 - p2) - HНОБ)1 - pНОНЗ)) + x HНОБ(1 - pНОНЗ)),

x3 = xґ3/ xґґ3,

xґ3 = (1 - р(х)(1 - а 1)(а 2 + (1 - а 2)р 1((лHНО 1 + x1HНО 1)р 2(1 - p3) + x2 HБНОрНЗНЗ(1 - pНЗНО)),

xґґ3 = 1 - a1c1 - (1 - a1)(a2HНОБ + (1 - a2)(р(х)HНОБ + (1 - а 2)(р(х)HНОБ + (1 - р(х))((1 - p1)HНОБ + p1 pНОНЗ(1 - pНОНО) HНОНО))).

В записи х 1, х 2, х 3 использованы следующие обозначения:

причем константы P*, N*z, N*0 зависят только от входных параметров модели и определяются из выражений:

P* = 1 + б1p1/б2 + б1p1p2p3/бґґ3 + б1p1p2(1 - p3)/бґ3 + б1p1p2p3/б4;

N*z = 1 + б1p1/б2 + б1p1pНЗНЗpНЗНО/бґґ3 + б1p1pНЗНЗ(1 - pНЗНО)/бґ3 + б1p1pНЗНЗpНЗНО/б4;

N*0 = 1 + б1p1/б2 + б1p1pНОНЗpНОНО/бґґ3 + б1p1pНОНЗ(1 - pНОНО)/бґ3 + б1p1pНОНЗpНОНО/б4.

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

(3.3)

3.3 Преобразование модели полнодоступного пучка простейшего типа

При нахождении оценок вероятностных характеристик исследуемой модели МТС прямого пучка МТС существенно предположение о том, что поток повторных вызовов является пуассоновским. В области малой и большой нагрузки, а также для больших пучков это допущение оказывается вполне приемлемым. Дальнейшее уточнение оценок, естественно, должно идти по пути устранения тех причин, которые эту "пуассоновость" нарушают. Рассмотрим абонентов, которые в последней попытке соединения получили отказ из-за занятости всех линий пучка. Очевидно, что следующая попытка соединения от таких абонентов с большей вероятностью попадет в состояние занятости всех линий пучка, чем первичная попытка. Это свойство модели нарушает нашу гипотезу о пуассоновости суммарного потока повторных вызовов, поскольку при ее выполнении все состояния системы для поступающих повторных вызовов равновероятны.

Теперь понятно, как можно уточнить приближенный метод, используемый в предыдущем разделе. Сохраним в упрощенной модели абонентов, повторяющих вызов из-за занятости всех доступных линий, а на пуассоновский заменим все оставшиеся потоки повторных вызовов. Для того чтобы это сделать, необходимо провести уточнение процесса взаимодействия абонента и обслуживающей системы, позволяющее выделить в общей массе повторяющих вызов абонентов тех, что получили в последней попытке отказ из-за занятости доступных линий. Сделаем некоторые изменения в символах, для обозначения причины отказа в обслуживании. Теперь символ ЛЗ будет означать отказ по причине занятости линий пучка, а Бґ - все прочие отказы из-за блокировки (кроме НЗ). Чтобы несколько упростить дальнейшее изложение, предположим, что а 1 = а 2 = 0. смысл оставшихся символов тот же, что и в утонченной модели, рассмотренной в предыдущем разделе.

Перейдем к определению компонент марковского процесса, описывающего функционирование модели. По аналогии с разделом 4 посмотрим, какие изменения произойдут в определении компонент по сравнению с утонченным вариантом модели. Поскольку мы предположили, что а 1 = 0, то ИПВ 1-го типа не будет. Зато ИПВ, образующиеся из-за блокировки, разделяются уже на шесть групп. Любую конечную комбинацию символов Бґ, ЛЗ обозначим { Бґ, ЛЗ }. Тогда определение компонент марковского процесса, описывающего функционирование модели, имеет вид: : j2(t) - число абонентов, имеющих в момент времени t предысторию взаимодействия с обслуживающей системой вид

({Бґ, ЛЗ}, Бґ); jЛЗ 2(t) - … - ({Бґ, ЛЗ}, ЛЗ); jНЗ 2(t) - … (..., НЗ, {Бґ, ЛЗ}; (..., НЗ, {Бґ, ЛЗ}, НЗ), ({Бґ, ЛЗ}, НЗ), (..., НО, {Бґ, ЛЗ}, НЗ); jНЗЛЗ 2(t) -,…, (..., НЗ,{Бґ, ЛЗ}, ЛЗ); jНО 2(t) - …, (..., НО,{Бґ, ЛЗ}, Бґ); jНОЛЗ 2(t) - …, (..., НО,{Бґ, ЛЗ}, ЛЗ).

Построение приближенного метода начнем в записи законов сохранения. В принятых обозначениях они имеют вид:

J2µ2 = (1 - р 1)(IР1б1H1 + IР1б1H2); (3.4)

JЛЗ 2µ2 = (JґЛЗ 2µ2 + Jґ2µ2)H2 + лрH1;

JНЗ 2µ2 = (IНЗ 1б1(1 - р 1)Н 2+ Jґ2µ2)H2 + IР2б2(1 - р 2)H1 + IРВ 2б2(1 - р 2)H2+ IНЗ 2б2(1 - рНЗНЗ)H2 + IНО 2б2(1 - рНОНЗ)HНОБ;

JНЗЛЗ 2µ2 = (JґНЗ 2µ2 + JґНЗЛЗµ2)H2;

JНО 2µ2 = (IНО 1б1 (1 - р 1)HНОБ;

JНОЛЗ 2µ2 = (JґНО 2µ2 + JґНОЛЗµ2 + JґЗµ3)HНОБ;

JЗµ3 = IґП 3бґ3HНО 1 + IґПВ 3бґ3HБНО + IґНЗ 3бґ3HБНО + IґНО 3бґ3HНОНО;

IР1б1р 1 = IР2б2; IР2б2р 2р 3 = IґґР3бґґ3;

IР2б2р 2(1 - р 3) = IґР3бґ3; IґґР3бґґ3 = IР4б4;

IРВ 1б1р 1 = IРВ 2б2; IРВ 2б2р 2р 3 = IґґРВ 3бґґ3;

IРВ 2б2р 2 (1 - р 3) = IґРВ 3бґ3; IґґРВ 3бґґ3 = IРВ 4б4;

IНЗ 1б1р 1 = IНЗ 2б2; IНЗ 2б2рНЗНЗрНЗНО = IґґНЗ 3бґґ3;

IНЗ 2б2рНЗНЗ(1 - рНЗНО) = IґНЗ 3бґ3; IґНЗ 3бґ3 = IНЗ 4б4

IНО 1б1р 1 = IНО 2б2; IНО 2б2рНОНЗрНОНО = IґґНО 2бґґ3;

IНО 2б2рНОНЗ(1 - рНОНО) = IНО 3бґ3; IґґНО 3бґґ3 = IНО 4б4;

л(1 - р) = ЙР1б1; ((J2 - JЛЗ 2) - (Jґ2 - JґЛЗ 2))µ2 = ЙРВ 1б1;

((JНЗ 2 + JНЗЛЗ 2) - (JґНЗ 2- JґНЗЛЗ 2))µ2 = ЙНЗ 1б1;

((JНО 2µ2 + JНОЛЗ 2µ2 + J3µ3) - (JґНО 2µ2 + JґНОЛЗ 2µ2 + Jґ3µ3) = ЙНО 1б1.

Упрощенная модель, которая будет использоваться при построении оценок вероятностных характеристик исходной модели, имеет вид М/М/v с (Н 1*, Н 2*; µ2) - настойчивым абонентом. Чтобы свести исходную модель к моедли такого типа, мы, как условились ранее, заменим пуассоновский только поток повторных вызовов, образованный не по причине занятости всех линий пучка, и многоэтапное обслуживание заменим на одноэтапное. Обозначим х интенсивность пуассоновского потока повторных вызовов, а г(х) - параметр одноэтапного обслуживания. Тогда система уравнений статистического равновесия марковского имеет вид:

(л + x + jµ2 + iг(x))P(i,j) = (л+х) P(j,i + 1)(i + 1) г(x), i = 0, 1, …,N - 1, i = 0, 1, …,х - 1; (3.5)

(л + x + jµ2 + iг(x))P(i,j) = (л+х) P(j,i - 1)(i + 1) (i +1)г(x), j = N, i = 0, 1, …,х - 1;

((л + x)H*1 + jµ2(1 - H*2) + iг(x))P(i,j) = (л+х)P(j,i - 1) + P(j + 1, i - 1)(j + 1)µ2 + (л+х) H*1P(j - 1,i) + P(j + 1, i)(j + 1) µ2 (1 - H*2), j = 0, 1, …,N - 1, i = х;

(jµ2(1 - H*2) + iг(x))P(i,j) = (л+х)P(j,i - 1) + (л+х) H*1P(j - 1,i), j = N, i = х.

Здесь Р(j,i) - стационарные вероятности модели (j - число абонентов, повторяющих вызов; i - число занятых линий в пучке); Н 1* и Н 2* - обощенные значения функции настойчивости (их определение будет дано несколько позднее); N - максимально допустимое число ИПВ. Для Р(j,i) выполнено условие нормировки:



Введем основные вероятностные характеристики модели:

вероятность потерь по времени;

среднее число занятых линий;

среднее число повторяющих вызовы абонентов;

Среднее число повторяющих вызовы абонентов, находящихся в системе в момент занятости всех линий. Вероятностные характеристики упрощенной модели р*, I*, J*, J*ґ будут оценками соотвестсвующих характеристик исходной модели. Вероятности Р(j,i), а следовательно, и р*, I*, J*, J*ґ, являются функциями неизвестного параметра х. Для определения х вновь воспользуемся законами сохранения, превратив их в неявные уравнения относительно х. Для определения вероятностных характеристик р*, I*, J*, J*ґ необходимо найти x, г(x), Н 1*, Н 2*. Введем обозначения:

x1 = [(1 - p1)(лH1(1 - р*(x)) + (JЛЗµ2 - JґЛЗµ2) H2)]/[1 - (1 - р 1)H2(1 - р*(x))];

xґ2 = р 1(1 - p2)(л(1 - р*(x)) H1 + x1(1 - р*(x)Н 2 + (JЛЗ - JґЛЗ)µ2H2) + р 1(1 - р*(x)) + (JНОЛЗµ2 - JґНОЛЗ)µ2)HНОБ + (1 - p1pНЗНЗ)*(JНОЛЗµ2 - JґНОЛЗ) µ2Н 2;

xґґ2 = 1 - (1 - р*(x))(1 - p1pНЗНЗ)Н 2 - p1pНЗНЗ HНОБ);

x3 = xґ3/xґґ3,

xґ3 = p1p2(1 - pЗ)((лHНО 1 + х 2HБНО)(1 - р*(x)) + (JЛЗ - JґЛЗ)µ2HБНО + p1pНЗНЗ(1 - p1pНЗНО)(х 2HБНО)(1 - р*(x)) + (JНЗЛЗ - JґНЗЛЗ) µ2Н 2) + (JНОЛЗ - JґНОЛЗ) µ2(p1pНОНЗ(1 - pНОНО)HНОНО + (1 - p1)HНОБ),

xґґ3 = 1 - (1 - р*(x))((1 - p1)HНОБ + p1pНОНЗ(1 - p1pНОНО)(HНОНО).

Тогда неизвестная интенсивность х находится из решения неявного уравнения:

х = х 1 + х 2 + х 3. (3.6)

Дадим определение отдельных величин, входящих в выражение (3.6).

1 значения JЛЗ, JНЗЛЗ, JНОЛЗ, JґЛЗ …определяются соотношениями:

JЛЗ =

JНЗНЗ =

JНОЛЗ =

JґЛЗ = JЛЗ

JґНЗЛЗ = JНЗЛЗ

JґНОЛЗ = JНОЛЗ

2 обощенные значения настойчивости абонента определяются формулами:

3

где

4 параметр одноэтапного обслуживания имеет вид:

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

. и так далее.

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

4. Моделирование алгоритма маршрутизации

4.1 Модель сети связи

Рассмотрим модель сети связи с коммутацией сообщений, имеющей M каналов и N узлов. В этой модели предполагается, что M каналов являются абсолютно надежными, а пропускная способность i-го канала равна Ci (бит в секунду). Все N узлов, соответствующих центрам коммутации сообщений (пакетов), предполагаются абсолютно надежными и выполняющими операции по коммутации сообщений, включая, например, декомпоновку сообщений, выбор маршрутов, хранение в буфере, уведомление и тому подобное. Считается, что времена обработки в узлах равны K и являются постоянными (обычно величина K предполагается пренебрежимо малой при реализации алгоритма отыскания потока К считалось равным нулю). Кроме того, в модели имеются очереди к каналам и задержки при передаче. Трафик, поступающий в сеть из внешних источников (например, из хостов) образует пуассоновский процесс со средним значением jk (сообщений в секунду) для тех сообщений, которые возникают в узле j и предназначаются для узла k. Полный внешний трафик, поступающий в сеть (и следовательно, покидающий ее), определим как

(4.1)

Заметим, что величина i имеет вид

(4.2)

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

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

(4.3)

Выше была определена задержка сообщения как полное время, которое сообщение проводит в сети. Наибольший интерес представляет средняя задержка сообщения

T = M [задержка сообщения],которая будет принята за главную характеристику сети. Определим среднюю величину Zjk.

Zjk = M [задержка сообщения, которое возникло в j и имеет место назначения k].Эти две средние величины связаны равенством

(4.4)

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

4.2 Задача распределения потока

В качестве исходного выражения для характеристики Т здесь используется формула:

, (4.5)

представляющая среднюю задержку сообщения, проходящего по сети. Все вопросы, связанные с массовым обслуживанием, учтены и отражены этим выражением; остается лишь задача оптимизации потоков, которая входит в теорию потоков в сетях. Теорема о максимальном потоке и минимальном сечении, которая гласит, что поток в канале не может превышать максимальной пропускной способности, является основой, на которой строится эта теория. В данной задаче распределения потока, так же как и в задаче распределения потоков различных грузов, требуется минимизировать нелинейную функцию Т по потокам {i}, чтобы удовлетворялись внешние требования к потокам jk Минимизация проводится в предположении, что пропускные способности заданы. Кроме того, нужно не нарушить обычный закон сохранения потоков. Согласно этому закону, суммарный трафик jk, поступающий в узел n, равен суммарному трафику jk, выходящему из узла n, за исключением случая n=j (узел n является узлом-источником) или случая n=k (узел n является узлом назначения). Далее, имеется ограничение на пропускную способность каждого канала, состоящее в том, что поток лi в канале i должен быть неотрицательным и меньшим пропускной способности, т. е. 0 лi < C. Это ограничение показывает, что характеристика Т обладает свойством безграничного возрастания при стремлении какого-либо потока к пропускной способности соответствующего канала (т. е. при стремлении множества потоков в сети к верхней границе для этих потоков, определенной ограничениями на пропускные способности). Это означает, что характеристика Т включает дополнительное ограничение на пропускную способность как функцию штрафа. Это важное свойство обеспечивает реализуемость решения при использовании любого метода минимизации, который представляется в виде последовательности "небольших шагов" и на начальном шаге оперирует с реализуемым решением. Таким образом, если начать с реализуемого решения, то можно пренебречь ограничением на пропускную способность, и вследствие этого задача, которая выглядит как задача оптимизации с ограничением, фактически будет представлять собой задачу без ограничений по оптимизации потоков различных грузов.

Ниже рассматривается метод, который дает точное решение задачи оптимального распределения потока, которое удобно использовать при численном расчете. Начнем с рассмотрения выражения (4.5) для T. Заметим, что эта характеристика является разделимой в том смысле, что она выражается просто как сумма слагаемых, каждое из которых зависит лишь от потока в одном канале. Кроме того, из (4.5) следует, что

, i = 1, 2, …, M. (4.6)

Отсюда видно, что T/(лi) > 0 при всех i; аналогичные рассмотрения показывают, что T/(лi)2 > 0 (оба эти неравенства справедливы при удовлетворении ограничений на пропускные способности). Таким образом, можно сделать вывод, что Т выпуклая функция потоков. Кроме того, множество реализуемых потоков само является выпуклым многогранником. Итак, если задача имеет реализуемое решение, то любой локальный минимум является глобальным минимумом для Т. Следовательно, любой метод отыскания локального минимума может быть использован при решении задачи поиска глобального минимума.

4.3 Метод отклонения потока

Метод, который применяется здесь, называется методом отклонения потока, он предназначен для поиска глобального минимума. Уясним вначале такое важное понятие как поток по кратчайшим путям. Предположим, что мы имеем сеть, каждый канал которой имеет надписанную на нем длину li,. В такой сети, естественно, можно найти кратчайший путь между узлом-источником j и узлом назначения k и пытаться посылать требуемый поток jk по этому пути. Если поступить так для всех пар (j,k), то в результате получится поток, который называется потоком по кратчайшим путям. Существует ряд хорошо известных и эффективных алгоритмов отыскания множества кратчайших путей jk.

4.3.1 Алгоритм Флойда отыскания множества кратчайших путей

Рассмотрим сеть с N узлами. Пусть D0=(djk) - матрица порядка N*N, элемент которой djk дает длину канала (которая при этом вычислении считается заданной), прямо соединяющего узел j с узлом k, если такого канала нет, то этот элемент равен бесконечности (кроме того, djj=0). При рассмотрении любого пути jk соединяющего узел j с узлом k, будем обозначать через l(jk) его длину (т. е. сумму длин каналов). Задача состоит в вычислении матрицы Н=(hjk) порядка N*N, где hjk - длина кратчайшего пути, соединяющего узел j и узел k; итак, H- матрица кратчайших путей, представляющая для нас интерес. Алгоритм кратчайших путей Флойда начинает с матрицы расстояний D0 и итеративно изменяет ее, проходя последовательность из N матриц (на n-м шаге матрица обозначается через Dn); в конце он приходит к матрице кратчайших путей DN=H. Если начать с n=0 и djk(0)=djk, то матрица Dn+1 получится из Dn с помощью итерации (7).

 (4.7)

Найдя D1, мы замечаем, что djk (1) (элемент j, k в матрице D1) представляет собой длину кратчайшего пути из узла j в узел k при условии, что допускаются лишь пути с узлом 1 в качестве промежуточного. Аналогично после отыскания Dn на n-й итерации получим, что djk(n) - кратчайшее расстояние от узла j к узлу k по путям, в которых промежуточные узлы принадлежат множеству {1, 2, ..., n}.

Таким образом, дойдя до N-ой итерации, получаем искомый результат djk (N) = hjk. Весь алгоритм требует около N3 сложений и вычитаний и N3 сравнений.

Cущество метода определения потока связано с сопоставлением "длины" с i-м ребром, величина которого дается равенством

(4.8)

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

Приведем конкретный алгоритм, который использует эти идеи. Для этого введем вектор потока на n-й итерации алгоритма:

(4.9)

i-я компонента которого представляет собой полный поток по i-му каналу на n-й итерации. Будем считать, что начальный поток f(0) является реализуемым. Теперь можно представить следующий алгоритм, который используется при нахождении реализуемого начального потока (вернее, при нахождении данного потока использовались шаги 2, 4, 7 и 8).

4.3.2 Оптимальный алгоритм отыскания потока для выбора маршрутов

Шаг 1. Положить n=0.

Шаг 2. Для каждого i=1, 2,..., М найти

.

Шаг 3. Найти n - добавочный стоимостный коэффициент для этого потока.

.

Шаг 4. Решить задачу отыскания потоков по кратчайшим маршрутам, используя длины li. Пусть i - результирующий поток по i-му каналу, который получается, если весь поток направляется по этим кратчайшим путям. Обозначим вектор потоков через = (1,2, ..., M).

Шаг 5. Найти bn - добавочный стоимостный коэффициент для потока по кратчайшему маршруту,

bn = li i.

Шаг 6. (Правило остановки.) Если n - bn <, где >0, надлежащим образом выбранный допуск, то STOP. В противном случае перейти к шагу 7.

Шаг 7. Найти такое значение a из интервала 0a1, для которого поток (1 - a) f(n)+a минимизирует Т. Пусть это оптимальное значение обозначается через a. Оптимальное значение a можно найти с помощью любого подходящего метода поиска (например, с помощью метода Фибоначчи [107]).

Шаг 8. (Отклонение потока) Положить

f(n+1) = (l - a) f(n) + a.

Шаг 9. Положить

n = n + 1.

Перейти к шагу 2.

Обратимся теперь к вопросу отыскания реализуемого начального потока f(0). Еще раз предположим, что задан внешний поток:

(4.10)

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

4.3.3 Алгоритм отыскания реализуемого начального потока

Шаг 1. Положить h0=1 и считать, что f(0) - решение задачи отыскания потоков по кратчайшим маршрутам в сети с длинами

li = 1/Ci

[заметим, что эти длины совпадают с длиной, представленной формулой (8) при нулевом потоке]. На этом шаге весь поток h0 направляется по сети; обозначим через i(0)/ поток в i-м канале на этом этапе. Положить n=0.

Шаг 2. Пусть

.

Если hn < 1, то положить

f(0) = f(n)/hn;

STOP (это реализуемый начальный поток). Если hn больше 1, то положить

hn+1 = hn[1-1(1n)]/n,

где 1 - надлежащий параметр точности, такой, что 0<1<l.

Шаг 3. Положить

g(n+1) = (hn+1/hn)f(n).

Это реализуемый поток различных грузов, который несет полный трафик с интенсивностью hn+1 < 1.

Шаг 4. Теперь провести операцию отклонения потока на потоке g(n+1); это значит, что нужно выполнить шаги 2, 4, 7 и 8 алгоритма ОП, найти (поток по кратчайшим маршрутам с длинами, основанными на потоке g(n+1)) и оптимальное значение (т.е. a), такие, чтобы поток

f(n+i) = (l-a) g(n+1) +a

минимизировал T. Если n = 0, то перейти к шагу 6; в остальных случаях перейти к шагу 5.

Шаг 5. Если

и ,

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

Шаг 6. Положить

n = n + 1

и перейти к шагу 2.

Эта процедура либо находит реализуемый начальный поток, либо объясняет, что задача не имеет реализуемого решения в пределах выбранных допусков.

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

Приложение 1

Размещено на http://www.allbest.ru/

Приложение 2

Приложение 3

Приложение 4

Приложение 5

Рисунок - Существующая междугородняя телефонная сеть Республики

Размещено на Allbest.ru

...