Телетраффика. Издание второе, переработанное и дополненное
 Скачать 3.77 Mb.
|
|
1.2. Математические модели систем распределения информации Как и любая другая математическая теория, теория телетрафика оперирует нес самими системами распределения информации, ас их математическими моделями. Математическая модель системы распределения информации включает следующие три основных элемента входящий поток вызовов требований на обслуживание, схему системы распределения информации, дисциплину обслуживания потока вызовов. В гл. 2 и 3 учебника подробно изучаются свойства и параметры случайных потоков вызовов и нагрузки. Колеблемость интенсивности нагрузки, распределение ее во времени и по направлениям рассмотрены в гл. 10, а измерение параметров нагрузки на действующих системах распределения информации – в гл. 12. Схемы систем распределения информации подробно изучаются в курсе Автоматические системы коммутации. Простейшей схемой является однозвеньевая полнодоступная схема. Процессы ее взаимодействия с различными потоками сообщений при обслуживании с потерями и с ожиданием подробно рассматриваются в гл. 4, 5 и 6. Методы расчета пропускной способности однозвеньевых неполнодоступных схем описаны в гл. 8, а полнодоступных и не-полнодоступных многозвеньевых схем – в гл. 9. 10 Дисциплина обслуживания характеризует взаимодействие потока вызовов с системой распределения информации. В теории телетрафика дисциплина обслуживания в основном описывается следующими характеристиками способами обслуживания вызовов (с потерями, с ожиданием, комбинированное обслуживание порядком обслуживания вызовов (в порядке очередности, в случайном порядке, обслуживание пакетами и др режимами искания выходов схемы (свободное, групповое, индивидуальное законами распределения длительности обслуживания вызовов (показательный закон, постоянная или произвольная длительность обслуживания наличием преимуществ (приоритетов) в обслуживании некоторых категорий вызовов наличием ограничений при обслуживании всех или некоторых категорий вызовов (по длительности ожидания, числу ожидающих вызовов, длительности обслуживания законами распределения вероятностей выхода из строя элементов схемы. Некоторые из перечисленных характеристик могут быть связаны с потоком вызовов и или) схемой, другие характеристики могут не зависеть ни от потока, ни от схемы. Например, закон распределения длительности обслуживания может быть связан с потоком вызовов, порядок обслуживания вызовов может зависеть и от потока вызовов и от схемы, а способ обслуживания вызовов, как правило, не зависит ни от потока, ни от схемы. В научной литературе для компактной записи математических моделей часто пользуются обозначениями, предложенными Д. Кендаллом, и модифицированными – Г. П. Башариным. Математическую модель обозначают последовательностью символов. Первый символ обозначает функцию распределения промежутков между вызовами, второй – функцию распределения длительности обслуживания, третий и последующие символы – схему и дисциплину обслуживания. Для обозначения распределений введены следующие символы М – показательное, Е – эрланговское, D – равномерной плотности, G – произвольное. Для многомерного случая над символами ставятся стрелки. Схема системы телетрафика обозначается символом S. Если схема представляет собой полнодоступный пучок линий, то вместо S пишется υ, где υ – число линий. Если вызовы обслуживаются с ожиданием, то число мест для ожидания обозначают символом r. Символ f с индексами вводится для обозначений приоритетов в обслуживании. Приведем несколько примеров. Так, M/M/S обозначает схему S, на которую поступает поток с показательной функцией распределения промежутков между вызовами и показательной функцией распределения длительности обслуживания (простейший поток вызовов. Запись ММ обозначает полнодоступный пучок с конечным числом линий, который обслуживает с потерями простейший поток вызовов. Запись r r 0 обозначает полнодоступный пучок из линий, который обслуживает с ожиданием k потоков с показательными функциями распределения промежутков между вызовами каждый поток имеет произвольную функцию распределения длительности обслуживания число мест для ожидания r < ∞; постановка вызовов в очередь осуществляется без приоритетов – f 0 , выборка из очереди – также без приоритетов – f 0 . Построение математической модели, адекватно отображающей реальную систему распределения информации, во многих случаях является нетривиальной задачей. От правильного выбора модели в конечном счете зависит успех решения всей задачи. 1.3. Основные задачи теории телетрафика Основная цель теории телетрафика заключается в разработке методов оценки качества функционирования систем распределения информации. В соответствии с этим на первом месте в теории телетрафика стоят задачи анализа, те. отыскание зависимостей и значений величин, характеризующих качество обслуживания, от характеристики параметров входящего потока вызовов, схемы и дисциплины обслуживания. Эти задачи в начальный период развития телефонной техники были более актуальными, чем задачи синтеза, и решались, как правило, с помощью теории вероятностей. 11 Поэтому наиболее значительные результаты на сегодняшний день получены при решении задач анализа. Развитие координатной и особенно квазиэлектронной и электронной коммутационной техники поставило перед теорией телетрафика сложные вероятностно-комбинаторные задачи синтеза, в которых требуется определить структурные параметры коммутационных систем при заданных потоках, дисциплине и качестве обслуживания. Близкими к задачам анализа и синтеза являются задачи оптимизации. Эти задачи при проектировании систем распределения информации формулируются следующим образом определить такие значения структурных параметров коммутационной системы (алгоритмы функционирования, для которых 1) при заданных потоках, качестве и дисциплине обслуживания стоимость или объем оборудования системы распределения информации минимальны и 2) при заданных потоках, дисциплине обслуживания и стоимости качественные показатели функционирования системы распределения информации оптимальны. При эксплуатации систем распределения информации задача оптимизации формулируется как задача управления потоками вызовов или структурой системы для достижения наилучших показателей качества функционирования. Из-за больших вычислительных трудностей задачи оптимизации систем распределения информации начали ставиться и решаться в последние два десятилетия после появления быстродействующих ЭВМ. Некоторые результаты решения задач этого класса для станций и узлов автоматической коммутации излагаются в курсе Автоматические системы коммутации, а для сетей связи – в курсе Теория сетей связи. 1.4. Общие сведения о методах решения задач теории телетрафика Основным математическим аппаратом теории телетрафика являются теория вероятностей, математическая статистика и комбинаторика. Значительные результаты теории телетрафика получены благодаря сформулированному А. К. Эрлангом понятию статистического равновесия, вероятностный процесс находится в состоянии статистического равновесия, если его вероятностные характеристики не зависят от времени. Понятие статистического равновесия не только стимулировало развитие теории телетрафика, но и способствовало практическому применению и дальнейшему развитию теории вероятностей. Методы математической статистики применяются при оценке результатов наблюдений за параметрами потоков вызовов и показателями качества обслуживания в действующих системах распределения информации, а также при моделировании таких систем. При анализе, синтезе и оптимизации структурно-сложных систем распределения информации кроме вероятностных методов используются комбинаторные и алгебраические методы, теория множеств, принципы системного подхода (системотехники. Основными методами решения задач в теории телетрафика являются аналитические, численные и метод статистического моделирования. Аналитические методы позволяют решать задачи теории телетрафика в тех случаях, когда структура системы, характеристики потока и дисциплина обслуживания относительно просты. При этом рассматриваются всевозможные состояния системы, определяемые положением каждой точки коммутации или другого элемента системы при наиболее подробном ее описании. Такие состояния называются микросостояниями системы. Каждый раз, когда поступает новый вызов, заканчивается какая-либо фаза работы управляющего устройства по установлению соединения или заканчивается соединение, система меняет свое микросостояние. Для каждого микросостояния записывается уравнение статистического равновесия. Решая систему таких уравнений, находят точное решение задачи в пределах принятой модели. Для сложных систем число микросостояний так велико, что решить систему уравнений статистического равновесия не представляется возможным даже с помощью самых быстродействующих ЭВМ. Более перспективным является так называемый макроподход. В сложной системе сочень большим числом микросостояний имеется тот или иной признак, по 12 которому микросостояния объединяются в классы-макросостояния. Путем усреднения определяются интенсивности переходов из одних макросостояний в другие. Для каждого макросостояния записывается уравнение статистического равновесия. В результате решения системы таких уравнений выводятся точные или приближенные формулы для вероятностей макросостояний. Чтобы представить трудности, связанные с использованием аналитических методов, достаточно указать, что число микросостояний неполнодоступного пучка из v линий оценивается как 2 υ . Например, при υ = 20 число состояний более 10 6 . Для решения задач такой размерности с помощью ЭВМ используются специальные алгоритмы, позволяющие находить приближенные решения итерационными или другими численными методами. Изложение этих методов дано в монографии МА. Шнепса [57]. Наиболее универсальным методом, который пригоден для решения задач практически любой сложности, является метод статистического моделирования. Метод заключается в построении математической модели системы, реализация которой осуществляется в виде программы для ЭВМ. Моделирование позволяет получить численные результаты, характеризующие качество обслуживания при заданных параметрах потока, схемы и дисциплины обслуживания. Однако в силу специфики метода он менее удобен по сравнению с аналитическими численным методами при определении скрытых закономерностей функционирования или зависимостей между отдельными характеристиками системы. Метод статистического моделирования как наиболее универсальный метод решения сложных задач подробно рассматривается в гл. 7. Во многих случаях разумное сочетание аналитических и численных методов с методом статистического моделирования позволяет детально проанализировать исследуемую систему. При малых значениях параметров системы удается получить решение точными аналитическими методами и проанализировать предельные случаи при асимптотическом поведении характеристик изучаемой системы. Полученные сведения дополняются результатами статистического моделирования в области реальных значений параметров системы. Оценивая результаты исследований систем распределения информации любыми математическими методами, следует помнить, что математика оперирует нес реальными системами, ас их математическими моделями. Так как математические модели всегда лишь приближенно описывают реальные системы, то никакие математические методы не могут заменить исследований, проводимых на реально функционирующих системах. 1.5. Краткий исторический обзор развития теории телетрафика Основы теории телетрафика были заложены в работах А. К. Эрланга в 1908–1918 гг. по исследованию пропускной способности полнодоступного пучка линий, обслуживающего простейший поток вызовов с потерями и с ожиданием. По-видимому, под влиянием статистической механики А. К. Эрланг ввел понятие статистического равновесия и использовал его как теоретическую основу для получения своих широко известных формул для вероятности потерь и ожидания. Он рассматривал входящий поток вызовов от бесконечного числа источников при показательном и постоянном времени обслуживания. Труды А. К. Эрланга послужили толчком для других работ, которые были связаны с подтверждением, развитием или опровержением его результатов. В 1918 г. Т. Энгсет обобщил результаты А. К. Эрланга на случай обслуживания полнодоступным пучком потока вызовов от конечного числа источников нагрузки, в 1927 г. ГО Делл опубликовал результаты исследований по неполнодоступным ступенчатым включениям, Э. Молина – по теории группо-образования, в 1928 г. Т. Фрай написал первую книгу по теории вероятностей, в которой одна из глав была посвящена теории телетрафика. В 1933 г. советский математик АН. Колмогоров выполнил свою классическую работу по аксиоматическому обоснованию теории вероятностей, в которой идея А. К. Эрланга о статистическом равновесии была отождествлена со стационарной мерой марковского процесса. В этот период появились первые работы А. Я. Хинчина по исследованию систем с ожиданием. В 1943 г. шведский ученый К. Пальм обобщил результаты А. К. Эрланга на случай обслуживания потока с ограниченным последействием, получил важные результаты по изучению колеблемости телефонной нагрузки. К этому времени в связи с разработкой координатных АТС появилась необходимость в методах расчета пропускной способности многозвеньевых коммутационных систем. Первое большое исследование в этом направлении было выполнено в 1950 г. К. Якобеусом и основывалось на априорных распределениях вероятностей состояний системы. Другой метод расчета потерь в таких системах – метод вероятностных графов – был предложен К. Ли в 1955 г. Обобщение и развитие методов теории телетрафика ив первую очередь, работ А. К. Эрланга и К. Пальма были выполнены А. Я. Хинчиным в 1955 г. В виде отдельной книги работа издана в 1963 г. [56]. Автоматизация междугородной телефонной связи поставила перед теорией телетрафика задачу расчета пропускной способности сетей с обходными направлениями. Первые работы поэтому вопросу были опубликованы в 1956 г. Р. Вилкинсоном и независима Г. Бретшнайдером. Исследование параметров избыточной нагрузки на таких сетях выполнено Д. Риорданом [51]. С автоматизацией междугородной связи тесно связана проблема повторных вызовов. Этой проблемой занимались ученые многих стран Л. Костен,. Ж. Коэн Нидерланды, А. Эллдин (Швеция, П. Ле-Галль (Франция, МА. Шнепс, ГЛ. Ионин, ЮН. Корнышев (СССР. Развитие квазиэлектронной техники поставило перед теорией телетрафика проблему синтеза многозвеньевых коммутационных систем. В 1953 г. Ч. Клоз опубликовал первую работу по многозвеньевым неблокирующим коммутационным схемам, а вначале х годов серию работ по анализу и синтезу многозвеньевых схем выполнил В. Бенеш. Результаты этой работы изложены в его монографии [37]. В перечисленных выше работах исследования выполнялись аналитическими или численными методами. Первые попытки статистического моделирования систем распределения информации относятся км годам. Для этих целей использовались специальные машины искусственной телефонной нагрузки. Основным недостатком таких машин по сравнению с ЭВМ является их узкая специализация. Машины искусственной телефонной нагрузки создавались годами, в то время как написание программ моделирования на ЭВМ занимает от нескольких недель до нескольких месяцев и программы сравнительно легко поддаются изменению. Впервые системы телетрафика на ЭВМ начали изучать в Швеции Г. Неовиус (1955 г) и Б. Валлстрем (1958 гав СССР вначале х годов Г. П. Башарин в Москве, Б. С. Лившиц в Ленинграде, МА. Шнепс в Риге. В настоящее время во всех странах, где ведутся работы по теории телетрафика, используется и метод статического моделирования. Большое влияние на развитие теории телетрафика оказывают организованные в 1955 г. и проводимые каждые три года Международные конгрессы по телетрафику. Восьмой конгресс состоялся в 1976 г. в Австралии, очередной, девятый конгресс состоится в 1979 г. в Испании. Последнее десятилетие в развитии теории телетрафика характеризуется стремлением к обобщению накопленных результатов. Кроме названных выше монографий А. Я. Хинчина, В. Бенеша, Д. Риордана на русском языке по теории телетрафика изданы книги [42–45, 54, 57, 58]. Многие вопросы теории телетрафика рассмотрены в книгах по теории массового обслуживания [36, 39, 46]. Обширная библиография по теории массового обслуживания и теории телетрафика (1289 наименований) содержится в монографии Т. Л. Саати [52]. Из большого числа нерешенных проблем, которыми занимается в настоящее время теория телетрафика, остановимся здесь лишь на двух, которые представляются нам наиболее важными. 1. Разработка методов анализа, синтеза и оптимизации систем распределения информации в целом. Необходимость решения данной проблемы диктуется введением программного управления в системы распределения информации, интеграцией систем распределения, передачи информации и ЭВМ. Будущие системы электросвязи будут совмещать в себе функции обработки, распределения и передачи информации. Ясно, что при разработке методов анализа, синтеза и оптимизации таких систем должен использоваться системный подход. 2. Разработка методов анализа, синтеза, управления и оптимизации сетей электросвязи. 14 Трудности решения задачи связаны со сложной структурой сетей, передачей различных видов информации, непрерывным развитием сетей, неопределенностью многих исходных данных, большой размерностью задачи. При решении указанных задач приходится использовать не только методы теории телетрафика, но и других областей знаний ив первую очередь, общей теории систем. Приведенный краткий обзор развития теории телетрафика далеко не охватывает всех направлений, по которым получены результаты или выполняются исследования, однако позволяет проследить общую тенденцию развития теории отрешения частных задач к разработке все более общих методов. Контрольные вопросы 1. Назовите основные элементы математических моделей систем распределения информации. 2. Назовите основные характеристики дисциплин обслуживания. 3. Сформулируйте задачи анализа, синтеза и оптимизации в теории телетрафика. 4. Поясните способ записи математических моделей систем телетрафика, предложенный Д. Кендаллом. 5. Назовите основные методы решения задач в теории телетрафика. 6. Что такое микро- и макросостояния систем распределения информации 7. Назовите основные недостатки метода исследования с помощью машин искусственной телефонной нагрузки. 15 ГЛАВА ВТОРАЯ Потоки вызовов. Основные понятия Потоком вызовов (в общем случае – событий) называется последовательность вызовов, поступающих через какие-либо интервалы или в какие-либо моменты времени. В теории массового обслуживания под потоком вызовов принято понимать не только последовательность вызовов, поступающих от группы абонентов или группы устройств телефонной сети, но и другие последовательности событий, например поток телеграмм, поток писем, поток неисправностей отдельных коммутационных устройств или телефонных сооружений в целом, поток информации, поступающей на ЭВМ, поток неисправностей в станках и т. п. Рассматриваемые в настоящей главе свойства, характеристики, закономерности потоков вызовов не ограничиваются узкими рамками изучения потоков телефонных вызовов, а имеют более широкую область применения. Следует различать детерминированный и случайный потоки вызовов. Детерминированный поток вызовов – последовательность вызовов, в которой вызовы поступают в определенные, строго фиксированные неслучайные моменты или через определенные, строго фиксированные, неслучайные промежутки времени. Случайный поток вызовов отличается от детерминированного теми только тем, что моменты поступления вызовов и промежутки времени между вызовами являются нестрого фиксированными, а случайными величинами. Детерминированные потоки являются частным случаем случайных потоков и на практике встречаются редко. Примерами их могут служить поток сеансов связи с искусственными спутниками Земли, поток поступления деталей и выхода изделий ритмично работающего завода и т. п. Строго говоря, даже в таких потоках часто имеют место случайности. В связи с этим в теории телетрафика основное внимание уделяется рассмотрению случайных потоков вызовов. Условимся в дальнейшем случайные величины обозначать прописными (большими) буквами, а их возможные значения – соответствующими строчными (малыми) буквами. Поток вызовов может быть определен тремя эквивалентными способами последовательностью вызывающих моментов t 1 , t 2 ,..., t n , последовательностью промежутков времени между вызывающими моментами z 1 , z 2 ,..., z n и последовательностью чисел k 1 , k 2 ,..., k n , определяющих количество вызовов, поступающих в течение заданных отрезков времени [ t 0 , t 1 ), [ t 0 , t 2 ),..., [ t 0 , t n ). При этом под вызывающим моментом понимается момент одновременного поступления одного, двух и более вызовов для вызывающих моментов всегда, если t i > t i-1 , тов то время как для момента поступления вызова t i ≥t i-1 и z i ≥0. Определение случайного потока вызовов связано с определением в вероятностном смысле либо последовательности вызывающих моментов, либо последовательности промежутков между вызывающими моментами, либо последовательности чисел вызовов, поступающих в течение отрезков времени [ t 0 , t 1 ) , [t 0 , t 2 ) ,...,[t 0 , t n ) . Для задания случайных потоков вызовов, как и любых других случайных величин и процессов, используются функции распределения. Функцией распределения вероятностей некоторой случайной величины X называется функция определяющая вероятность того, что Х<х, где х – определенная, заданная величина. С учетом изложенного, для задания случайного потока вызовов могут быть использованы следующие эквивалентные способы 1) совместный закон распределения п случайных вызывающих моментов где T i – й вызывающий момент п может принимать любое значение 2) совместный закон распределения п случайных промежутков времени между 16 вызывающими моментами где Z i – промежуток времени между (i–1)- им вызывающими моментами п может принимать любое значение 3) совместный закон распределения числа вызовов К на n отрезках времени [t 0 , t 1 ) , [t 0 , t 2 ) , ..., [t 0 , t n ): Введем некоторые ограничения на рассматриваемые случайные потоки вызовов. Потоки вызовов подразделяются на неоднородные и однородные. В неоднородном потоке вызовов каждый вызов имеет две и более характеристики. Например, вызовы, поступающие от абонентов телефонной сети, определяются моментами их поступления, направлениями установления соединений, длительностью их обслуживания и другими характеристиками. Аналогично телеграммы, поступающие на телеграф, характеризуются моментами их поступления, направлениями их передачи, количеством слов в телеграмме и т. д. Однородный поток вызовов характеризуется последовательностью, определяющей только закономерность поступления вызовов, те. последовательностью моментов поступления вызовов или промежутков времени между вызовами, либо иным способом задания потока вызовов. На практике потоки вызовов, как правило, являются неоднородными. Несмотря на это, целесообразно отдельно от других характеристик потоков вызовов изучить последовательности моментов поступления вызовов. Поэтому в дальнейшем под потоком вызовов будем понимать однородный поток вызовов. Ограничимся рассмотрением потоков, в которых на любом конечном отрезке времени поступает конечное число вызовов и математическое ожидание числа поступающих вызовов также является конечной величиной. Такие потоки называются финитными Математическое ожидание числа вызовов, поступающих в интервале времени [0, t), называется ведущей функцией потока. Обозначим эту функцию ∆(0, t). Функция ∆(0, t) – неотрицательная, неубывающая ив практических задачах принимает конечное значение. Потоки с непрерывной ведущей функцией называются регулярными, а со ступенчатой – сингулярными. Вероятность поступления хотя бы одного вызова в определенный момент времени для регулярного потока равна нулю, а для сингулярного потока в моменты разрыва ведущей функции отлична от нуля. Нас интересуют только потоки вызовов с непрерывной ведущей функцией, те. регулярные потоки. Таким образом, в дальнейшем рассматриваются случайные однородные финитные регулярные потоки. |