Содержание к диссертации
Введение
ГЛАВА 1. Анализ и использование многопотоковых моделей систем связи
1 -1 . Многопотоковые модели информащїонїшх систем
1 .2. Многопотоковые модели, учитывающие особенности взаимодействия абонента и обслуживающей системы .- -
1.2.1. Схема функционирования модели
1.2-2. Марковский процесс
1.2.3. Система уравнений статистического равновесия -
1.2-4, Характеристики качества функционирования
1.2.5. Законы сохранения
1.3. Многопотоковые модели с приоритетами
1.3-1, Обобщенная модель полнодоступной системы с повторными вызовами и приоритетами
1.3.2. Марковский процесс, описываиций функционирование системы:
1.3.2, Характеристики качества функционирования .
1.4. Особенности анализа многопотоковых моделей
1.5. Задачи работы
Глава 2. Многопотоковые модели, учитывающие особенности взаимодействия вызывающего абоненента и обслуживании системы
2.1. Переход к конечному числу состояний
2.2, Система уравнений равновесия вспомогательной модели
2.3. Определение вероятностных характеристик урезанной модели
2.4. Законы сохранения
2.5. Оценка характеристик итерационным методом
2.6. Общие принципы построения оценок
2.7. Анализ упрощенной модели
2.7.1-Схема функционирования
2.7.2.Система уравнений статистического равновесия
2.7.4Вычисление стационарных вероятностей
2,7-5. Определение параметров упрощенной модели .
2.7-6- Решение системы неявных уравнений
Глава 3- Расчет многопотоковой модели с приоритетами и повторными вызовами
3.1. Переход к модели с явным заданием функции настойчивости абонента
3.2. Определение характеристик и соотношения между ними
3.3. Расчет двухпотоковой модели
3.3.1. Точное решение системы уравнений статистического равновесия
3.3.2. Приближенное решение, основанное на использовании упрощенных уравнений равновесия
3,3-3. Расчет модели в случае большой нагрузки .
3.3.4. Расчет модели в случае малой нагрузки
3.3.4. Расчет модели в случае малой нагрузки
3.4. Схема расчета многопотоковой модели
ГЛАВА 4. Решение двух практических задач
4.1. Оценка числа каналов» необходимого для обеспечения заданного процента потерь вызовов
4.2. Определение вероятности и среднего времени доставки сообщения для модели с приоритетами
4.2.1. Постановка задачи -
4.2.2. Эквивалентное определение для вероятности доставки сообщения
4.2.3. Определение среднего времени доставки сообщения
4.2.4. Пример формулировки и решения задачи оптимизации процедуры повторения
Заключение
Список литературы
Приложение 1
Приложение 2
- Многопотоковые модели информащїонїшх систем
- Переход к конечному числу состояний
- Переход к модели с явным заданием функции настойчивости абонента
- Оценка числа каналов» необходимого для обеспечения заданного процента потерь вызовов
Введение к работе
Развитие современной техники связи идет по пути увеличения количества услуг, представляемых абоненту, и улучшения качества его обслуживания. Современные средства телекоммуникации проектируются с учетом возможности передачи разнородной информации, требующей различного качества обслуживания и имеющей различные приоритеты при ее обработке. Технически поставленные задачи решаются переходом на цифровую передачу информации по каналам связи, применением микропроцессоров и других элементов вычислительной техники для контроля за установлением соединения и осуществлением диалога между абонентом и обслуживающей системой ([6,15, 25.381).
Все перечисленные выше факторы осложняют схемы функционирования сетей связи и приводят к адекватным по сложности математическим моделям. Сложность соответствукщих моделей вытекает из того обстоятельства, что они должны достаточно подробно описы-вать потоки нагрузки, поступающие на каналы связи и, насколько это возможно» отражать специфику взаимодействия абонента и системы. Для более точного описания поступающей нагрузки приходится рассматривать входной поток не как нечто единое, а разбивать его на несколько потоков с разными законами или параметрами распределения, т.е. рассматривать многопотоковые модели.
Необходимость и важность исследования многопотоковых моделей с учетом реакции абонента на отказ в обслуживании находит свое отражение в постоянно возрастающем числе публикаций, посвященных этой теме ([19,26-30,33-36,43,53,54,56-72,75-83,85,87]).
Наиболее существенный вклад внесли следующие отечественные и зарубежные ученые: А *М. Зелинский, Г.Л.Ионин, Ю.Н.Корнышев, С,Н.Степанов, Г.М.Фалин, Й.И.Цитович, Е.И.Школьный, М.А.Шнепс, J.Cohen, R.Evere, G.Gosatony и другие авторы.
Анализируя состояние проблемы оценки характеристик многопотоковых моделей с учетом реакции абонента на отказ в обслуживании необходимо отметить, что для решения поставленной задачи в основном использовались стандартные методы, развитые в теории массового обслуживания ([1,19,26,34,781). Такое состояние дел, с одной стороны, ограничивало класс рассматриваемых моделей достаточно простыми ситуациями, а с другой, в значительной степени сужало диапазон изменения структурных параметров (например, число обслуживающих устройств и потоков не должно быть слишком велико, чтобы ответ можно было бы получить за конечное, с точки зрения практики, время). Поставленную задачу можно решить, разработав эффективные в вычислительном смысле приближенные методы оценки характеристик многопотоковых моделей с созданием на их основе соответствующего программного обеспечения.
Решение поставленной задачи и является целью настоящей работы. Причин, из-за которых появляется многопотоковость, можно выделить в основном две: либо входной поток первичных вызовов состоит из нескольких потоков, требующих различного обслуживания и имещих различные параметры распределения; либо при детальном рассмотрении взаимодействия абонента с обслуживающей системой приходится вводить в рассмотрение несколько потоков повторных вызовов, каждый из которых появляется на своем этапе обслуживания. Естественно, обе эти причины могут действовать одновременно, и тогда число потоков еще более возрастает. Проведенное в
диссертации исследование выполнено на примере модели с подробным учетом потерь на различных этапах установления соединения по ме-вдугородному телефонному тракту и модели с произвольным числом входных потоков и абсолютным приоритетом. Таким образом, тематика диссертационной работы актуальна и отвечает нуждам и запросам практики.
Целью диссертации является разработка, теоретическое обоснование и практическая реализация методов оценки характеристик качества обслуживания моделей систем массового обслуживания, у которых входной поток состоит из нескольких потоков, имещие различные интенсивности и приоритеты в обслуживании, либо возникающие из-за различных аспектов взаимодействия абонента с системой.
Для решения поставленных в диссертации задач использовались методы теории телетра^ика, теории вероятностей, математической статистики и вычислительной математики,
Научная новизна работы состоит в следующем:
I. Разработаны математические модели многопотоковых систем, в которых учитывается:
наличие произвольного числа входных потоков первичной нагрузки;
приоритетность в обслуживании поступающих вызовов;
возможность получить отказ с последующим повторением вызова из-за занятости всех приборов, занятости или неответа вызываемого абонента, старения передаваемой информации, вытеснения с обслуживания вызовом с более высоким приоритетом, превышения отведенного на повторение времени, потерь на этапах установления соединения, предшествующих обслуживающим приборам системы-
2. Для введенных моделей получены соотношения мезду вероят
ностными характеристиками, облегчающие их вычисление или измере
ние и разработаны оптимальные метода оценки характеристик, осно
ванные на решении системы уравнений равновесия. Оптимальность
алгоритмов достигнута за счет удаления из расчетной области сос
тояний, имеющих пренебрежительно малые вероятности.
3. Разработаны приближенные методы оценки характеристик
многопотоковых моделей с учетом реакции абонентов на отказ в об
служивании и приоритетами, обеспечивающие удовлетворительную
точность оценки характеристик для любых практически интересных
значений входных параметров. Метод основан на последовательном
упрощении структуры входного потока и изменении правила обслужи
вания вызовов. Указанное преобразование совершается с помощью
введения в рассматриваемую модель дополнительных входных параме
тров. Получены неявные уравнения для их определения и разработан
алгоритм решения этих уравнений.
Все научные результаты, изложенные в диссертации, а также разработанные на их основе алгоритмы и программы, получены лично автором.
Формулы и алгоритмы вычисления вероятностных характеристик многопотоковых моделей, полученные в диссертации, могут быть использованы для создания инженерных методов расчета систем связи, при моделировании которых необходимо учитывать влияние поведения абонента на процесс формирования входного потока вызовов. Для обеспечения более простого внедрения результатов диссертации в практическую деятельность инженеров и проектировщиков систем связи все все полученные в диссертации алгоритмы доведены до программных продуктов и сданы в ГосФАП.
Результаты диссертации нашли практическое применение на Московской междугородной телефонной сети и на Московской городской телефонной сети, что подтверждается соответствующими актами об использовании.
Основные положения работы докладывались и обсуждались на 4-м меящународном семинаре по теории телетрафика и компьютерному моделированию (Москва, 1992 г.). XLVII научной сессии, посвященной Дню радио (Москва, 1992), IX и X Белорусской зимней школе-семинаре "Анализ и применение систем и сетей массового обслуживания* (Минск, 1993 г., 1994 г.), Санкт-Петербургском международном семинаре "Управление цифровыми сетями связи" (1993г.), семинаре "Методы расчета характеристик сетей связи" Института проблем передачи информации РАН (1991 Г-И992 г., !ЭЭЗ г.).
Основные результаты диссертационной работы изложены в одиннадцати печатных работах.
Текст диссертации состоит из введения, четырех глав, заключения, списка литературы и двух приложений.
Многопотоковые модели информащїонїшх систем
Исследование современных систем связи методами математического моделирования приводит к необходимости разработки и изучения таких моделей, в которых входной поток вызовов состоит из нескольких потоков, различакщихся структурой, характером поведения, причиной появления, разными требованиями к обслуживанию и т.д. Таким образом» актуальной является задача оценки характеристик моделей с более чем одним потоком входных вызовов В разделе 1.1. обсуждается необходимость исследования таких моделей, рассматриваются классы многопотоковых моделей. Раздел 1.2. посвящен обсуждению многопотоковых моделей, которые возникают из-за учета особенностей взаимодействия вызываемого и вызыващего абонента. Здесь приводится модель такого класса, определяется марковский процесс, связанный с моделью. Далее определяются основные статистические характеристики модели, приводятся уравнения статистического равновесия, приводятся законы сохранения. В разделе 1.3. определяется модель с наличием нескольких потоков первичных вызовов,, имеющих разные приоритеты при обслуживании, определяется набор характеристик качества функционирования этой модели. Особенности анализа многопотоковых моделей обсуадаются в разделе 1.4. Раздел 1.5. содержит постановку задач» решению которых посвящена данная работа - 11 1.1 .Многопотоковые модели информационных систем.
Рассмотрим простейшую модель системы массового обслуживания с повторными вызовами. Пусть имеется полнодоступная система из v обслуживающих устройств, на которую поступает пуассо-новский поток первичных вызовов некоторой заданной интенсивности к, а также поток повторных вызовов, образованных по причине занятости всех обслуживающих устройств. Поступивший вызов занимает свободное обслуживающее устройство» если такое имеется. Если же все устройства заняты, то абонент с вероятностью Н через случайное время, распределенное экспоненциально с некоторой интенсивностью ц, повторяет попытку вызова. Эта модель подробно изучена (см. [57],[61]Дбб],[701,[71]). Такая модель уже, вообще говоря, является многопотоковой, поскольку поток поступающих вызовов является суммой двух потоков - пуассоновс-кого потока первичных вызовов и потока повторных вызовов. Ввод в рассмотрение повторных вызовов позволяет более точно приблизить входной поток к реальному, но требует развития более сложных методов анализа модели, чем для классических моделей, в которых входной поток считается пуассоновским.
Дальнейшее приближение математических моделей к реальным системам связи вызывает необходимость еще большего усложнения модели за счет более детального рассмотрения структуры поступающих вызовов: поток первичных вызовов образован наложением несколько потоков, повторные вызовы также получаются путем суммирования нескольких потоков, которые имеют свои законы или параметры распределения и образованы по тем или иным причинам, введенным в рассмотрение для более точного соответствия математической модели реальной системе массового обслуживания.
В данной работе рассматриваются модели, в которых присутствуют либо несколько потоков первичных вызовов, каждый из которых имеет свою специфику обслуживания, либо несколько потоков повторных вызовов, каждый из которых образован из-за своего аспекта взаимодействия абонента с системой- Суммарный входной поток вызовов в системе не обязательно пуассоновский, поскольку получается путем сложения одного или нескольких пу-ассновских потоков первичных вызовов и различных наслоений, образованных в результате взаимодействия абонента и обслуживающей системы. Такая форма реконструкции входного потока вызовов дает более точное приближение к действительности, чем допущение о пуассоновском характере входного потока, йце раз подчеркнем, что одно только введение в рассмотрение повторных вызовов приводит к наличию нескольких (как минимум двух) потоков вызовов в системе Причин, из-за которых возникает шюгопотоковость в моделях систем массового обслуживания, можно выделить, в основном, две: либо приходится рассматривать несколько потоков первичных вызовов, каждый из которых имеет свои параметры распределения и требует учета своей специфики при обслуживании; либо, для более точного отображения реальной системы, в математической модели приходится вводать в рассмотрение несколько потоков повторных вызовов. Естественно» обе эти причины могут действовать одновременно, и тогда число потоков еще более возрастает.
В дальнейшем, из всего многообразия многопотоковых моделей будем рассматривать только два класса:
- модели, в которых есть один пуассоновский поток первичных вызовов и несколько потоков повторных вызовов, каждый из кото - 13 рых имеет свои параметры и возникает из-за отказов на различных этапах взаимодействия с системой- Рассмотрению этих моделей посвящена глава 2;
Переход к конечному числу состояний
В данной главе исследуются способы оценки характеристик функционирования полнодоступной системы, введенной в разделе t.2. Раздел 2.1 данной главы посвящен описанию вспомогательной модели, отличавдейся от исходной тем, что марковский процесс, описывающий ее функционирование, имеет, в отличие от исходной, конечное число состояний. Система уравнений статистического равновесия для вспомогательной модели приведена в разделе 2.2. Раздел 2.3. содержит определения основных вероятностных характеристик урезанной модели. Законы сохранения, связывающие между собой характеристики моделиf обсуждаются в разделе 2.4. Способ оценки характеристик модели путем решения системы уравнений итерационным методом описан в разделе 2.5. Раздел 2.7 посвящен принципам приближенного расчета характеристик, которые для данной конкретной модели детализируются в разделе 2.8. Здесь проведено дальнейшее упрощение схемы функционирования, заключающееся в замене потоков повторных вызовов на пуассонов-ские с некоторыми неизвестными интенсивностями, приведена система уравнений равновесия и выписаны формулы определения стационарных вероятностей через параметры упрощенной модели. Далее приведен алгоритм нахождения неизвестных параметров упрощенной модели (интенсивноетей потоков повторных вызовов). 3.5. Переход к конечному числу состояний
Многопотоковая модель системы массового обслуживания, введенная в п-1.2., имеет бесконечное число состояний и, соответственно, система (1.1) уравнений статистического равновесия, приведенная в п. 1.2.3. содержит бесконечное число неизвестных стационарных вероятностей P(j fj ltj ti, fi ,i.) и имеет бесконечное число уравнений (система (1.1) содержит бесконечное число неизвестных поскольку целочисленные индексы J+PJ I и J f означающие число абонентов, повторяющих по разным причинам вызов, меняются от О ДО со ) m
Для решения этой системы необходимо перейти от системы с бесконечным числом неизвестных к системе, имевдей конечное число неизвестных. В теории моделей с учетом эффекта повторных вызовов существует стандартная процедура перехода к моделям, определенным на конечном пространстве состояний.
Предположим, что число абонентов, повторяющих вызов, (напомним, что в системе уравнений равновесия (1.1) в зависимости от причины отказа они задаются символами Jftj.ltj ) не пре-восходит некоторых целых чисел N tNhl, Nnat выбранных достаточно большими, т.е. выполняются неравенства J- №- J.-.KN.., j і . Для этого в схеме функционирования базовой модели сделаем следующие изменения. Если по схеме функционирования базовой модели у нас должен появиться новый источник повторных вызовов, а соответствующая очередь заполнена, то предполагается, что с вероятностью единица происходит потеря вызова. Чтобы не усложнять запись формул, сохраним для компонент марковского процесса, описыващего функционирование редуцированной модели те же обозначения, которые использовались в базовй модели. Модель описывается марковским процессом
Переход к модели с явным заданием функции настойчивости абонента
Пребывание в системе вызова потока 1-го приоритета связано с реализациями четырех случайных величин;
- - временем старения распределенным экспоненциально с
- параметром, равным а (это время отсчитывается с момента попадания вызова в систему до момента окончания обслуживания);
- ТІ - ограничением на общее время, отведенное на повторение заблокированного вызова, распределенным экспоненциально с параметром, равным 1 (это время отсчитывается с момента начала процедуры повторения вызова до моментов попадания на обслуживание или ухода из системы, вызванного старением информации);
- временем обслуживания, распределенным экспоненциально с параметром, равным S (это время отсчитывается с момента попадания вызова на обслуживание до момента его окончания);
- временем между последовательными повторными вызовами, распределенным экспоненциально о параметром, равным г, (это время отсчитывается с момента принятия решения о повторении вызова до момента поступления повторного вызова на вход системы).
Теперь воспользуемся основным свойством экспоненциально распределенных случайных величин, которое говорит, что если е - случайная величина, имеющая экспоненциальное распределение, а г 0 случайный момент, который не зависит от е, то P(& t+x\e v) - Р(в х), х 0. Словесная формулировка этого утверждения звучит понятно в терминах занятия линий на обслуживание. Если прибор занят на обслуживание, длительность которого имеет экспоненциальное распределение и известно, что время занятия превысило некоторый уровень г, то остаточное время занятия прибора также имеет экспоненциальное распределение с тем же параметром. То есть мы можем считать, что после прохождения уровня % случайное время занятия моделируется заново.
Воспользуемся этим свойством и перемоделируем процесс пребывания вызова і - го потока в системе;
а) процедура занятия вызовом обслуживающего устройства. В момент занятия канала вызовом еще не завершился процесс старения передаваемой информации. Тогда в силу упомянутого свойства экспоненциально распределенных случайных величин можно считать, что, начиная с момента занятия канала, процесс старения можно моделировать заново. В результате время занятия канала будет распределено как mind 1,?8), т.е. имеет экспоненциальное распределение с параметром (a + S). С вероятностью обслужшзание вызова завершится без прерывания из-за старения информации и с вероятностью обслуживание вызова прервется из-за старения передаваемой информации.
б) процедура повторения заблокированного вызова.
В момент получения отказа в обслуживании из-за занятости всех линий или после вытеснения с обслуживания вызовом более высокого приоритета еще не завершился процесс старения передаваемой информации и не реализовано (не началось) время, отведенное на повторение заблокированного вызова. Тогда так же, как в предыдущем случае, можно считать, что в рассматриваемый момент эти случайные величины моделируются заново. Таким образом, для вызова і го потока, получившего отказ в обслуживании, время до наступления следующего события, связанное с его пребыванием в системе, распределено как w.in( la,TlyTvf), т.е. имеет экспоненциальное распределение с параметром (a+Z +г ). По завершении этого времени с вероятностью абонент покинет систему нвобслуженным из-за наличия ограничения на общее время повторения и с вероятностью Р» = РШП(Т],Г.) ! ) = о, абонент покинет систему необслуженным из-за старения передаваемой информации. Изменения, которые коснулись условий пребывания вызова і - го потока в системе, приводят к следующим изменениям в схеме функционирования модели.
Как и: прежде, у нас имеется полнодоступная система из v приборов с п поступающими потоками первичных вызовов с инте-нсивностями л р і - 1,2,.,.,71. Получив отказ в обслуживании (в первичной или повторной попытках, а также после вытеснения с обслуживания вызовом более высокого приоритета), абонент из і - го потока нагрузки с вероятностью Prt повторяет требование к соединению через случайное время, имеющее экспоненциальное распределение с параметром, равным (afii+ri), и с вероятностью \-Рг. покидает систему необслуженным. Время занятия канала рас-пределено экспоненциально с параметром (a+S). По его окончании с вероятностью Р3 считается, что обслуживание завершилось, а с дополнительной вероятностью предполагается, что обслуживание вызова не произошло из-за старения информации.(Схема функционирования модели представлена на рис.3)
Часть стационарных характеристик процесса (t) такие, как: вероятность доставки, время доставки, среднее число повторных вызовов на один первичный, вероятность потерь, совпадают с аналогичными характеристиками процесса at) , часть -нет (к ним относится, например, число абонентов г - го потока, повторяющих вызов). Если совпадения нет, то можно выписать простые формулы, позволяющие находить одну характеристику по значению другой.
Оценка числа каналов» необходимого для обеспечения заданного процента потерь вызовов
Аппаратура, имеющаяся на автоматической междугородной станции, позволяет измерять нагрузку, поступившую на станцию за определенный интервал времени- Кроме того, определяется число вызовов, получивших отказ за этот интервал времени и среднее число линий, обслуживавших поступающую нагрузку- Необходимо определить число каналов, обеспечивающее общую вероятность отказов не боль - 39 ше заданной при данной общей входной нагрузке.
Поток входной нагрузки состоит из потока первичных вызовов и потоков повторных вызовов. Недостаточное число каналов увеличивает поток повторных вызовов. Измерения, производящиеся на станции, не разделяют поступащиэ вызовы на первичные и повторные. Стандартные методы расчета необходимого числа каналов, используемые инженерами на телефонных станциях, основаны на применении формулы Зрланга и не учитывают влияния повторных вызовов-Вследствие этого происходит завышение требуемого числа каналов.
Для решения этой задачи воспользуемся методами оценки характеристик модели МТС, представленными в главе 3. Считаем, что известны все входные параметры системы, перечисленные в п.1-2.1., за исключением интенсивности потока первичных вызовов Л.. Кроме того, задано общее число поступивших вызовов с оттоп
По значению Noomtian и длине интервала измерения Т определяем экспериментальное значение общей интенсивности входного потока
Лэксп как отношени9 ооштюг/ этим пзРаметРам определяем значоние интенсивности потока первичных вызовов А, как решение неявного уравнения
Здесь Л(М - значение общей интенсивности входного потока, являющееся функцией от X. Значение общей интенсивности входного потока Л определяется по формуле
Л = К + Щъг- \хы + MJr + Ют м а (здесь №jbl №j и #/ш среднее число повторяющих абонентов ддя каждого из трех потоков повторных вызовов).
Уравнение 4.1) имеет единственное решение. Действительно, очевидно, что функция Aft) является монотонно возрастающей. Кроме тоге, при к - О Л (АО стремится к нулю; при X «? А (А.) - да. Отсюда видно, что для любого А решение уравнения,{IГсущест- вует и оно единственно. Найти его можно, например, методом половинного деления. Определим вначале интервал [А№_»\_3, на кото-ром находится решение. Алгоритм следующий:
а) А, полагаем равным А_„ хтр икон
б) А. .полагаем равным Х/2\
Далее определяем значение А. Зададим значение е относительной точности, с которой будем искать решение. Алгоритм такой:
После определения интенсивности потока первичных вызовов можно определить требуемое число каналов, обеспечивающее вероятность потери вызова не больше заданной. Например, можно последовательно увеличивать число каналов, пока полная вероятность потерь Рг не станет меньше заданного уровня.
Алгоритм, изложенный выше, реализован в виде программы LAMBDA-EXE для компьютеров типа IBM PC XT/AT. Описание программы см- приложение 1 4.2. Определение вероятности и среднего времени доставки сообщения для модели с приоритетами Рассмотрим модель с приоритетами, определенную в главе 1. Методы оценки вероятностных характеристик, входящих в запись законов сохранения для этой модели, подробно обсуждены в главе 3 данной работы,
