Лившиц Б. С. и др. 2 страница

Автоматизация междугородной телефонной связи поставила перед теорией телетрафика задачу расчета пропускной способности сетей с обходными направлениями. Первые работы по этому вопросу были опубликованы в 1956 г. Р. Вилкинсоном и независима Г. Бретшнайдером. Исследование параметров избыточной нагрузки на таких сетях выполнено Д. Риорданом [51]. С автоматизацией междугородной связи тесно связана проблема повторных вызовов. Этой проблемой занимались ученые многих стран: Л. Костен,. Ж. Коэн (Нидерланды), А. Эллдин (Швеция), П. Ле-Галль (Франция), М. А. Шнепс, Г. Л. Ионин, Ю. Н. Корнышев (СССР).

Развитие квазиэлектронной техники поставило перед теорией телетрафика проблему синтеза многозвеньевых коммутационных систем. В 1953 г. Ч. Клоз опубликовал первую работу по многозвеньевым неблокирующим коммутационным схемам, а в начале 60-х годов серию работ по анализу и синтезу многозвеньевых схем выполнил В. Бенеш. Результаты этой работы изложены в его монографии [37].

В перечисленных выше работах исследования выполнялись аналитическими или численными методами. Первые попытки статистического моделирования систем распределения информации относятся к 20-м годам. Для этих целей использовались специальные машины искусственной телефонной нагрузки. Основным недостатком таких машин по сравнению с ЭВМ является их узкая специализация. Машины искусственной телефонной нагрузки создавались годами, в то время как написание программ моделирования на ЭВМ занимает от нескольких недель до нескольких месяцев и программы сравнительно легко поддаются изменению. Впервые системы телетрафика на ЭВМ начали изучать в Швеции Г. Неовиус (1955 г.) и Б. Валлстрем (1958 г.), а в СССР в начале 60-х годов Г. П. Башарин в Москве, Б. С. Лившиц в Ленинграде, М. А. Шнепс в Риге. В настоящее время во всех странах, где ведутся работы по теории телетрафика, используется и метод статического моделирования.

Большое влияние на развитие теории телетрафика оказывают организованные в 1955 г. и проводимые каждые три года Международные конгрессы по телетрафику. Восьмой конгресс состоялся в 1976 г. в Австралии, очередной, девятый конгресс состоится в 1979 г. в Испании.

Последнее десятилетие в развитии теории телетрафика характеризуется стремлением к обобщению накопленных результатов. Кроме названных выше монографий А. Я. Хинчина, В. Бенеша, Д. Риордана на русском языке по теории телетрафика изданы книги [42–45, 54, 57, 58]. Многие вопросы теории телетрафика рассмотрены в книгах по теории массового обслуживания [36, 39, 46]. Обширная библиография по теории массового обслуживания и теории телетрафика (1289 наименований) содержится в монографии Т. Л. Саати [52].

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

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

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

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

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

Контрольные вопросы

1. Назовите основные элементы математических моделей систем распределения информации.

2. Назовите основные характеристики дисциплин обслуживания.

3. Сформулируйте задачи анализа, синтеза и оптимизации в теории телетрафика.

4. Поясните способ записи математических моделей систем телетрафика, предложенный Д. Кендаллом.

5. Назовите основные методы решения задач в теории телетрафика.

6. Что такое микро- и макросостояния систем распределения информации?

7. Назовите основные недостатки метода исследования с помощью машин искусственной телефонной нагрузки.

ГЛАВА ВТОРАЯ

Потоки вызовов

2.1. Основные понятия

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

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

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

Поток вызовов может быть определен тремя эквивалентными способами: последовательностью вызывающих моментов t ₁, t ₂,..., t_n, последовательностью промежутков времени между вызывающими моментами z ₁, z ₂,..., z_n и последовательностью чисел k ₁, k ₂,..., k_n, определяющих количество вызовов, поступающих в течение заданных отрезков времени [ t ₀, t ₁), [ t ₀, t ₂),..., [ t ₀, t_n). При этом под вызывающим моментом понимается момент одновременного поступления одного, двух и более вызовов; для вызывающих моментов всегда, если t_i > t_{i -1}, то z_i >0, в то время как для момента поступления вызова t_i. ³ t_{i -1} и z_i ³0.

Определение случайного потока вызовов связано с определением в вероятностном смысле либо последовательности вызывающих моментов, либо последовательности промежутков между вызывающими моментами, либо последовательности чисел вызовов, поступающих в течение отрезков времени [ t ₀, t ₁), [ t ₀, t ₂) ,..., [ t ₀, t_n).

Для задания случайных потоков вызовов, как и любых других случайных величин и процессов, используются функции распределения. Функцией распределения вероятностей некоторой случайной величины X называется функция

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

1) совместный закон распределения п случайных вызывающих моментов

где T_i – i -й вызывающий момент; п может принимать любое значение;

2) совместный закон распределения п случайных промежутков времени между вызывающими моментами

где Z_i – промежуток времени между (i –1)- и i -м вызывающими моментами; п может принимать любое значение;

3) совместный закон распределения числа вызовов К на n отрезках времени [ t ₀, t ₁), [ t ₀, t ₂) ,..., [ t ₀, t_n):

Введем некоторые ограничения на рассматриваемые случайные потоки вызовов.

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

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

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

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

Математическое ожидание числа вызовов, поступающих в интервале времени [0, t), называется ведущей функцией потока. Обозначим эту функцию D(0, t). Функция D(0, t) – неотрицательная, неубывающая и в практических задачах принимает конечное значение. Потоки с непрерывной ведущей функцией называются регулярными, а со ступенчатой – сингулярными. Вероятность поступления хотя бы одного вызова в определенный момент времени для регулярного потока равна нулю, а для сингулярного потока в моменты разрыва ведущей функции отлична от нуля. Нас интересуют только потоки вызовов с непрерывной ведущей функцией, т. е. регулярные потоки.

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

2.2. Принципы классификации потоков вызовов

Потоки вызовов классифицируются с точки зрения стационарности, ординарности и последействия.

Стационарность потока. Поток вызовов является стационарным, если при любом п совместный закон распределения числа вызовов за промежутки времени [ t ₀, t ₁), [ t ₀, t ₂) ,..., [ t ₀, t_n)

зависит только от длины промежутков времени и не зависит от момента t ₀. Иными словами, независимо от того, где на оси времени расположен промежуток времени [ t ₀, t ₁), вероятность поступления K (t ₀, t _t)вызовов одна и та же. Это значит, что для стационарного потока вероятность поступления некоторого числа вызовов за какой-то промежуток времени зависит от длины этого промежутка и не зависит от его начала. В противном случае поток является нестационарным.

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

Ординарность потока. Обозначим через p _k (t, t+ t ) вероятность поступления k и более вызовов за промежуток [ t, t+ t). Поток вызовов является ординарным, если при t®0

т. е. p₂(t, t +t)= o (t), где o (t) – величина более высокого порядка малости по отношению к t.

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

Последействие потока. Поток вызовов является потоком без последействия, если вероятность поступления K (t ₀, t_i) вызовов за промежутки [ t ₀, t_i), i= 1, 2, ..., п

не зависит от вероятностного процесса поступления вызовов до момента t ₀. Иными словами, отсутствие последействия потока означает независимость течения случайного потока вызовов после какого-либо момента времени от его течения до этого момента. Примером потока без последействия может служить поток телефонных вызовов, поступающих от большой группы источников. Действительно, лишь небольшая часть (10–20%) абонентской труппы одновременно участвует в телефонных соединениях. Поэтому вероятность поступления какого-либо числа вызовов от большой группы источников на любом отрезке времени практически не зависит от процесса поступления вызовов до начала данного отрезка. Заметам, что эта вероятность, как и вероятность (2.7), может зависеть от момента t ₀начала этого отрезка времени. Так, различные значения принимает вероятность поступления некоторого числа телефонных вызовов за равные промежутки времени в различные часы суток в силу нестационарности потока телефонных вызовов в течение суток.

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

2.3. Характеристики потоков вызовов

К основным характеристикам потока вызовов следует отнести ведущую функцию потока, его параметр и интенсивность.

Под параметром потока l(t) в момент времени t понимается предел отношения вероятности поступления хотя бы одного вызова за время [t, t + t ) к длине этого отрезка времени t при t®0:

т. е. параметр потока есть плотность вероятности наступления вызывающего момента в момент t. Исходя из (2.8), находим вероятность поступления одного и более вызовов за время [t, t + t ):

Согласно определению стационарного потока, вероятность поступления определенного числа вызовов за некоторый промежуток времени одна и та же и не зависит от месторасположения на оси времени этого промежутка. Следовательно, и плотность вероятности поступления вызовов стационарного потока, т. е. его параметр l (t), есть величина постоянная, не зависящая от момента t, т. е. l (t)= l. Отсюда для стационарных потоков

В отличие от ведущей функции потока L(0, t), определяющей математическое ожидание числа вызовов, поступающих в промежутке времени [0, t), параметр потока l (t) характеризует не поток вызовов, а поток вызывающих моментов, и эта характеристика относится не ко всему отрезку [0, t), а лишь к фиксированному моменту t.

Интенсивностью стационарного потока m называется математическое ожидание числа вызовов, поступающих в единицу времени. Единица времени может быть выбрана произвольно, однако в теории телетрафика в качестве такой единицы большей частью принимают среднюю длительность одного занятия. Вследствие аддитивности математического ожидания для стационарного потока ведущая функция за промежуток времени [0, t)равна L(0, t)=m t.

Для нестационарных потоков используются понятия средней и мгновенной интенсивностей. Средняя интенсивность потока на отрезке времени [t₁, t₂) есть

а мгновенная интенсивность потока в момент t

Согласно определению (2.12) мгновенная интенсивность потока представляет производную ведущей функции потока. Так же как и параметр потока l (t), мгновенная интенсивность потока m (t) относится не к отрезку времени поступления вызовов, а только к моменту t. В то же время, в отличие от параметра потока, характеризующего поток вызывающих моментов, мгновенная интенсивность потока характеризует поток поступления вызовов.

Для любых потоков вызовов m(t)³l(t), причем для ординарных потоков m (t)= l (t). Для стационарных потоков интенсивность и параметр постоянны: m (t)= m, l (t)= l. Следовательно, для любых стационарных потоков m³l, а для стационарных ординарных m = l.

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

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

2.4. Простейший поток вызовов

Определение. Простейшим потоком называется стационарный ординарный поток без последействия. Простейший поток вызовов является наиболее распространенной моделью реального потока вызовов, применяемой в системах массового обслуживания, в том числе в теории телетрафика. Действительно, как отмечалось при рассмотрении принципов классификации потоков вызовов, поток телефонных вызовов от большой группы абонентов характеризуется отсутствием последействия. Его можно считать ординарным, а при ограничении исследуемого промежутка времени 1–3 ч и стационарным. Аналогичные случайные потоки событий характерны для многих отраслей народного хозяйства.

Математическая модель простейшего потока. Определим вероятности поступления точно k(k= 0,1, 2,...) вызовов на отрезке времени [ t₀, t₀+t): p_k (t₀, t₀+t).Исследования будем проводить на отрезке времени [ t ₀, t ₀ +t+ t), который можно представить состоящим из двух примыкающих друг к другу отрезков: [ t ₀, t ₀+ t+ t) = [ t ₀ ,+t ₀ +t) + [ t, t+ t).

Для того чтобы в течение отрезка [ t ₀, t ₀ +t+ t)поступило точно k вызовов, необходимо, чтобы за первый промежуток времени [ t ₀, t ₀+ t) поступило k, или k –1,..., или k–i,..., или 0 вызовов и соответственно за второй промежуток 0, или 1,..., или i,..., или k вызовов.

Введем обозначения: p_k (t ₀, t ₀ +t+ t) – вероятность поступления точно k вызовов за отрезок времени [ t ₀, t ₀ +t+ t); p_k-i (t ₀, t ₀ +t) – вероятность поступления точно k–i вызовов за первый отрезок времени [ t ₀, t ₀ +t); p_i (t, t+ t) – вероятность поступления точно i вызовов за второй отрезок времени [ t, t+ t). Согласно определению простейший поток является стационарным. Из этого следует, что вероятности поступления того или иного числа вызовов за отрезки времени [ t ₀, t ₀ +t+ t), [ t ₀, t ₀ +t), [ t, t+ t)не зависят от моментов начала отсчета времени, а зависят только от длины отрезков времени. Поэтому упростим обозначения как отрезков времени, так и вероятностей: [ t ₀, t ₀ +t+ t)будем обозначать [ t+ t); [ t ₀, t ₀ + t) – [ t); [ t, t+ t)– [t) и соответственно p_k (t ₀, t ₀ +t+ t) – p_k (t +t); p_k-i (t ₀ ,t ₀+ t) –p_k-i (t); p_i (t, t+ t)– p_i (t).

Простейший поток является потоком без последействия. Поэтому независимыми являются события, заключающиеся в поступлении какого-либо числа вызовов за первый и второй промежутки времени, и вероятность поступления точно k вызовов за время [ t+ t)для каждой реализации i= 0, 1,..., k составляет p_k (t+ t) _i=p_k-i (t) p_i (t), i =0, 1,..., k. Поскольку реализации с i =0, 1,..., k представляют несовместимые события, то согласно формуле полной вероятности имеем

Выражение (2.13) представляет собой систему, состоящую из бесконечного числа уравнений. Устремим отрезок времени tк нулю. Вследствие ординарности простейшего потока p₂(t, t +t) =o (t),t®0. Тем более вероятности поступления точно 2, 3,... вызовов – p ₂(t), p ₃(t), ... – есть бесконечно малые более высокого порядка по отношению к t. Следовательно, в системе ур-ний (2.13) вероятности p_i имеют конечные значения только при i, равном 0 и 1. На основании этого (2.13) преобразуются к виду

Определяем вероятности p ₁(t)и p ₀(t):

С учетом (2.10) и (2.6)

(p₀(t) – вероятность поступления 0 и более вызовов, т. е. вероятность достоверного события, она равна 1).

Подставим в систему ур-ний (2.14) полученные значения вероятностоей p ₁(t) и p ₀(t). Затем, перенеся в левую часть уравнений p_k (t), поделим левые и правые части уравнений на t. Переходя к пределу, получим

Решив систему дифференциальных ур-ний (2.16), получим формулу Пуассона

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

Основные характеристики простейшего потока. При объединении п независимых простейших потоков с параметрами l₁, l₂,..., l _n образуется общий простейший поток с параметром l₁+l₂+...+l _n. Вероятность поступления точно k вызовов за отрезок времени t определяется формулой Пуассона

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

Сумма вероятностей всех возможных значений числа поступающих вызовов за рассматриваемый промежуток времени t равна 1. Действительно,

Функция p_k(t) есть функция распределения дискретной случайной величины К. Из (2.17) следует, что она зависит от l t и k, а при t =1 – от l и k.

Как и для любой дискретной случайной величины, распределенной по закону Пуассона, математическое ожидание М(К), дисперсия D(K) и среднеквадратическое отклонение s (К) числа вызовов простейшего потока, поступающих за отрезок времени t, равны

Из этого следует, что интенсивность простейшего потока равна его параметру m =М(К)= l.Равенство m=l справедливо не только для простейшего потока, но и для любого стационарного ординарного потока.

Характер зависимости p_k(t) от k при l t =const (l t = 5) показан на рис. 2.1. Влияние l t на характер этой зависимости иллюстрируется рис. 2.2. На нем приведены огибающие значений функции p_k(t) при l t=1, 5 и 10. С возрастанием величины l t (при t =1с возрастанием параметра потока) огибающие кривые принимают все более симметричный вид, приближаясь к нормальному закону распределения непрерывной случайной величины. При l t =10 имеет место хорошее совпадение огибающей значений p_k(t) с нормальным законом распределения (пунктирная кривая).

Вероятность поступления k и более вызовов определяется по формуле

Вероятности p_k(t) и p_i ³ k(t) для различных значений k и l t табулированы [29]. Представляет практический интерес также зависимость p_{i £ k} (t) от k при l t –const. Огибающие кривые значений p_{i £ k} (t) такой зависимости представлены на рис. 2.3 при l t= 1, 5 и 10. При этом p_i£k(t) определяется по таблицам p_i³k(t) с учетом того, что p_i£k(t)= 1 –p_i³k(t).

Дата добавления: 2014-11-29