Содержание к диссертации
Введение
Глава 1. Исследование математических моделей неустойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова 23
1.1. Математическая модель неустойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова 23
1.2. Исследование асимптотических средних характеристик неустойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова 30
1.3. Исследование величин отклонения нормированного числа заявок в источнике повторных вызовов от их асимптотического среднего 34
1.4. Глобальная аппроксимация процесса изменения состояний в математической модели неустойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова 42
1.5. Численное исследование математических моделей неустойчивых » сетей множественного доступа, функционирующих в условиях предельно редких изменений состояний случайной среды 44
1.5.1. Многостабильность неустойчивых сетей множественного доступа 45
1.5.2. Многомодалыюсть плотности распределения вероятностей значений процесса изменения состояний в неустойчивых сетях множественного доступа 53
1.6. Исследование времени стабильного функционирования
Неустойчивых сетей множественного доступа в случайной среде,
Управляемой цепью маркова 56
1.7. Резюме 58
Глава 2. Исследование математических моделей устойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова 59
2.1. Математическая модель устойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова 59
2.2. Исследование асимптотических средних характеристик устойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова 67
2.3. Исследование величин отклонения нормированного числа заявок в источнике повторных вызовов от их асимптотического среднего 71
2.4. Глобальная аппроксимация процесса изменения состояний в математической модели устойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова 80
2.5. Численное исследование математических моделей устойчивых сетей множественного доступа, функционирующих в условиях предельно редких изменений состояний случайной среды 83
2.5.1. Многостабильность устойчивых сетей множественного доступа 83
2.5.2. Многомодалыюсть плотности распределения вероятностей значений процесса изменения состояний в устойчивых сетях множественного доступа ; 87
2.6. Исследование времени стабильного функционирования устойчивых" сетей множественного доступа в случайной среде, управляемой цепью маркова 88
2.7. Резюме 90
Глава 3. Исследование математических моделей неустойчивых сетей множественного доступа, функционирующих в диффузионной среде 91
3.1. Математическая модель неустойчивых сетей множественного доступа, функционирующих в диффузионной среде 91
3.2. Исследование асимптотических средних характеристик неустойчивых сетей множественного доступа, функционирующих в диффузионной среде 99
3.3. Исследование величин отклонения нормированного числа заявок В источнике повторных вызовов от их асимптотического среднего 104
3.4. Глобальная аппроксимация процесса изменения состояний в математической модели неустойчивых сетей множественного доступа, функционирующих в диффузионной среде 112
3.5. Резюме 114
Глава 4. Исследование математических моделей неустойчивых сетей множественного доступа, функционирующих в полумарковской среде 116
4.1. Математическая модель неустойчивых сетей множественного доступа, функционирующих в полумарковской среде 116
4.2. Исследование асимптотических средних характеристик неустойчивых сетей множественного доступа, функционирующих в полумарковской среде 125
4.3. Исследование величин отклонения нормированного числа заявок в источнике повторных вызовов от их асимптотического среднего 129
4.4. Глобальная аппроксимация процесса изменения состояний в математической модели неустойчивых сетей множественного доступа, функционирующих в полумарковской среде 136
4.5. Резюме 139
Заключение 140
Список литературы
- Исследование асимптотических средних характеристик неустойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова
- Исследование асимптотических средних характеристик устойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова
- Исследование величин отклонения нормированного числа заявок В источнике повторных вызовов от их асимптотического среднего
- Исследование асимптотических средних характеристик неустойчивых сетей множественного доступа, функционирующих в полумарковской среде
Введение к работе
Актуальность работы. В настоящее время бурное развитие информационных технологий и их внедрение в экономическую, производственную и образовательную деятельность расширяют сферу применения средств передачи информации. Оперативный обмен и использование новой информации позволяют повысить производительность и качество труда, организовать наиболее эффективный процесс управления. Следствием этого является необходимость усовершенствования существующих концепций и средств построения сетей передачи данных, а также внедрение инновационных технологий. Важнейшими требованиями к сетям связи в настоящее время являются высокая скорость и надежность передачи различного типа информации. В связи с этим создается новое аппаратное обеспечение, призванное расширить пропускную способность физических каналов связи; разрабатываются сетевые протоколы, целью которых является повышение производительности сетей.
Однако, несмотря на предпринимаемые усилия, полного решения выше изложенных проблем еще не существует. Именно поэтому ведется исследование математических моделей сетей передачи информации. Наибольшее распространение в современном мире получили сети, управляемые протоколами случайного множественного доступа. Такого рода сети отличаются своими стохастическими свойствами. Инструментом математического моделирования таких сетей является аппарат теории массового обслуживания [7, 8, 14, 20, 25, 39, 40, 43, 47, 48, 51, 55, 59, 74, 77, 83, 89, ПО, 114, 115, 118, 119, 123, 125], с помощью которого строятся аналитические модели сетей. Теория массового обслуживания является одним из разделов теории вероятностей [19, 44, 107]. Важнейшей составляющей является теория случайных процессов [4, 41, 79, 107]. Такие исследования служат для оценки качественных показателей функционирования систем обработки и передачи информации. Под качественными показателями здесь понимаются вероятностно-временные характеристики, такие как вероятность потерь, вероятность простоя канала, среднее время стабильного функционирования, среднее значение числа повторных попыток передачи сообщений вследствие искажения или потерь. Оценка этих параметров позволяет выработать рекомендации построения систем связи, обеспечивающих
компромисс между требованиями абонента, качеством их обслуживания и критериями эффективности сети.
Важно подчеркнуть, что для организации правильной работы сети недостаточно учитывать физические особенности построения сетей, стохастические свойства протоколов передачи данных, требования абонентов и экономические показатели. Производительность сетей связи зависит еще и от воздействий случайной среды. Случайной средой будем называть изменяющиеся неконтролируемые внешние условия, влияющие на пропускную способность каналов связи. К таким условиям можно отнести: состояние ионосферы для радиосетей, атаки вирусов на компьютерные сети связи, функционирование локальное сети, подключенной к глобальной сети, несанкционированный доступ в сети связи и т.д.
На сегодняшний день ряд вопросов, связанных с негативным влиянием случайной среды, зачастую решается системными администраторами эмпирическим путем в зависимости от конкретной ситуации. Понятно, что невозможно обойтись без антивирусной защиты, защиты от эксплоитов и т.п. Необходимость информационной безопасности вытекает из самой природы сетевых служб, сервисов и услуг. Однако, даже проведение успешной информационной защиты приводит к замедлению передачи данных в сети вследствие потери времени на обнаружение и уничтожение вредоносного кода. Более того, существует ряд факторов, против которых средства информационной безопасности бессильны. Так, например, изменение степени ионизации ионосферы, электромагнитные возмущения Земли непосредственно влияют на работоспособность спутниковых сетей связи и радиосетей.
По результатам математического моделирования сетей множественного доступа, функционирующих в случайной среде, могут быть найдены условия устойчивого функционирования таких сетей, а также решены задачи выбора оптимальных параметров работы сети, выработаны принципы создания новых, более совершенных сетей.
Таким образом, данная работа, в которой проводится математическое моделирование сетей множественного доступа, функционирующих в случайной среде, исследуются основные вероятностно-временные характеристики этих сетей, в настоящее время является весьма актуальной.
Цель данной работы - исследование математических моделей сетей множественного доступа, функционирующих в случайной среде.
При выполнении данной работы ставились следующие задачи.
(1). Построить математические модели сетей множественного доступа в виде
г - систем массового обслуживания:
Для бесконечного числа абонентских станций с функционированием в случайной среде, управляемой однородной цепью Маркова с непрерывным временем;
Для конечного числа абонентских станций с функционированием в случайной среде, управляемой однородной цепью Маркова с непрерывным временем;
Для бесконечного числа абонентских станций с функционированием в диффузионной среде;
Для бесконечного числа абонентских станций с функционированием в полумарковской среде.
(2). Применить аналитические и численные методы для исследования построенных математических моделей сетей связи с использованием аппарата теории вероятностей и теории массового обслуживания. Для математических моделей сетей
> множественного доступа, функционирующих в случайной среде, управляемой це
пью Маркова:
Найти средние характеристики сетей при больших задержках для сетей с бесконечным числом абонентских станций и при большом количестве абонентских станций для сетей с конечным числом абонентских станций;
Исследовать величины отклонения от этих средних характеристик;
Доказать возможность возникновения явления многостабильности в такого рода сетях;
Показать возможность аппроксимации числа сообщений в источнике повторных вызовов однородным диффузионным процессом;
Найти плотность распределения вероятностей значений этого процесса и до-
казать ее многомодальность;
Исследовать среднюю длительность времени стабильного функционирования сетей;
Рассмотреть функционирование сетей в условиях предельно редких изменений состояний случайной среды;
— Для математических моделей сетей множественного доступа, функционирующих в диффузионной и полумарковской средах провести аналогичные исследования.
Методика исследований. Исследование математических моделей сетей множественного доступа, функционирующих в случайной среде, проводилось с использованием аппарата теории вероятностей, теории случайных процессов, теории массового обслуживания, асимптотического анализа марковизируемых систем.
Научная новизна и результаты, выносимые на защиту.
Впервые предложен метод асимптотического анализа для исследования математических моделей сетей множественного доступа, функционирующих в случайной среде.
В условиях большой задержки для математических моделей сетей с бесконечным числом абонентских станций и в условиях большого количества абонентских станций для модели сетей с конечным числом абонентских станций найдены распределения вероятностей состояний канала, асимптотическое среднее нормированного числа заявок в источнике повторных вызовов, величины отклонения от этого среднего. Также проведена диффузионная аппроксимация процесса изменения состояний сети, найдена плотность распределения вероятностей значений процесса изменения состояний сети.
Для моделей сетей, функционирующих в случайной среде, управляемой однородной цепью Маркова с непрерывным временем доказана возможность возникновения явления многостабилыюсти, показана многомодальность плотности распределения вероятностей значений процесса изменения состояний сети, исследовано среднее значение продолжительности интервалов времени стабильного функционирования сети в окрестности точек стабилизации.
Показано, что сети множественного доступа с конечным числом абонентских станций даже в случайной среде отличаются устойчивым функционированием.
Рассмотрено функционирование математических моделей сетей множественного доступа в случайной среде, управляемой однородной цепью Маркова с непрерывным временем в условиях предельно редких изменений состояний среды.
Теоретическая ценность работы заключается в том, что метод асимптотического анализа марковизируемых систем получил свое непосредственное развитие, а
именно модифицирован для нестационарных распределений и применен для исследования математических моделей сетей множественного доступа, функционирующих в случайной среде. Построенные модели сетей связи в случайной среде могут быть использованы в качестве основы построения более сложных моделей, описывающих поведение сетей множественного доступа в случайной среде.
Практическая ценность работы состоит в том, что результаты, полученные в работе, могут быть использованы для анализа реальных сетей, определения значений параметров функционирования сетей, при проектировании новых сетей.
Апробация работы. Основные положения диссертации и отдельные ее результаты докладывались и обсуждались:
На VIII Всероссийской научно-практической конференции «Научное творчество молодежи» (г. Анжеро-Судженск, 16-17 апреля 2004 г.);
На Всероссийской научной конференции молодых ученых «Наука. Технологии. Инновации» (г. Новосибирск, 2-5 декабря 2004 г.);
На III Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» (г. Анжеро-Судженск, 11-12 декабря 2004 г.);
На Международной научной конференции «Математические методы повышения эффективности функционирования телекоммуникационных сетей» (г. Минск, 22-24 февраля 2005 г.);
На IX Всероссийской научно-практической конференции «Научное творчество молодежи» (г. Анжеро-Судженск, 15-16 апреля 2005 г.);
На IV Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» (г. Анжеро-Судженск, 18-19 ноября 2005 г.);
На научных семинарах кафедры теории вероятностей и математической статистики факультета прикладной математики и кибернетики Томского государственного университета.
Публикации. По материалам данной работы опубликовано И печатных работ.
1. Вавилов В.А., Назаров А.А. Исследование средних характеристик неустойчивых сетей множественного доступа в случайной среде // Научное творчество молодежи: Материалы VIII Всероссийской научно-практической конференции
*
(г. Анжеро-Судженск, 16-17 апреля 2004 г.) Ч. 1. - Томск: Изд-во Том. ун-та, 2004. -С. 15-17.
Вавилов В.А., Назаров А.А. Исследование средних характеристик неустойчивых сетей множественного доступа в случайной среде // Обработка данных и управление в сложных системах: Сборник статей / Под ред. А.Ф. Терпугова. -Томск: Изд-во Том. ун-та, 2004. Вып. 6. - С. 14-24.
Вавилов В.А. Исследование влияния случайной среды на величины отклонения числа заявок в источнике повторных вызовов от их асимптотического среднего в неустойчивых сетях множественного доступа // Наука. Технологии. Инновации: Материалы Всероссийской научной конференции молодых ученых в 6-ти частях (г. Новосибирск, 2-5 декабря 2004 г.). - Новосибирск: Изд-во НГТУ, 2004. Часть 1.-С. 12-13.
Вавилов В.А. Исследование асимптотических средних характеристик и величин отклонения в неустойчивых сетях множественного доступа в случайной среде // Вестник ТГУ: общенаучный периодический журнал. - Томск: Изд-во Том. ун-та, 2004. №284.-С. 130-136.
Вавилов В.А. Исследование времени стабильного функционирования неустойчивых сетей множественного доступа в случайной среде // Вестник ТГУ: общенаучный периодический журнал. - Томск: Изд-во Том. ун-та, 2004. №284. - С. 126-129.
Вавилов В.А., Назаров А.А. Исследование средних характеристик неустойчивых сетей случайного множественного доступа, функционирующих в диффузионной среде // Информационные технологии и математическое моделирование: Материалы III Всероссийской научно-практической конференции (г. Анжеро-Судженск, 11-12 декабря 2004 г.) Ч. 2. - Томск: Изд-во Том. ун-та, 2004. - С. 7-9.
Вавилов В.А., Назаров А.А. Исследование математических моделей устойчивых сетей множественного доступа, функционирующих в случайной среде // Массовое обслуживание. Потоки, системы, сети: Материалы международной научной конференции «Математические методы повышения эффективности функционирования телекоммуникационных сетей» (г. Минск, 22-24 февраля 2005 г.). Вып. 18 (редкол.: А.Н. Дудин (отв. Ред.) [и др.]). - Мн.: БГУ, 2005. - С. 226-231.
Вавилов В.А. Аппроксимация процесса изменения состояний в математической модели неустойчивых сетей множественного доступа в диффузионной среде // Научное творчество молодежи: Материалы IX Всероссийской научно-практической конференции (г. Анжеро-Судженск, 15-16 апреля 2005 г.). Ч. 1. -Томск: Изд-во Том. ун-та, 2005. - С. 12-15.
Вавилов В.А., Назаров А.А. Исследование математических моделей многостабильных сетей множественного доступа в случайной среде // Обработка данных и управление в сложных системах: Сборник статей / Под ред. А.Ф. Терпугова. -Томск: Изд-во Том. ун-та, 2005. Вып. 7. - С. 17-30.
10. Вавилов В.А., Назаров А.А. Исследование средних характеристик устойчи
вых сетей множественного доступа в диффузионной среде // Информационные
технологии и математическое моделирование: Материалы IV Всероссийской науч
но-практической конференции (г. Анжеро-Судженск, 18-19 ноября 2005 г.) Ч. 2. -
Томск: Изд-во Том. ун-та, 2005. - С. 7-9.
П.Вавилов В.А., Назаров А.А. Исследование средних характеристик неустойчивых сетей множественного доступа в полумарковской среде // Информационные технологии и математическое моделирование: Материалы IV Всероссийской научно-практической конференции (г. Анжеро-Судженск, 18-19 ноября 2005 г.) Ч. 2. -Томск: Изд-во Том. ун-та, 2005. - С. 10-12.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации составляет 158 страниц, в том числе титульный лист - 1 стр., оглавление - 3 стр., основной текст - 137 стр., библиография - 207 наименований - 17 страниц.
Состояние проблемы и обзор литературы. Небольшой исторический обзор [70, 104, 133, 134] поможет оценить состояние исследуемой проблемы. История развития сетей связи берет свое начало в конце 19 века с изобретением телефонного аппарата. Начальный этап развития сетей характеризуется передачей речи по телефонным линиям на основе аналоговых сигналов. На следующем этапе происходит развитие цифровых систем передачи данных. Телефонные сети на базе цифровой техники получили название интегральных цифровых сетей IDN (Integrated Digital Network). Предпосылкой появления вычислительных сетей можно считать телеграфные сети.
В 1964 году начала функционировать разработанная Пентагоном сеть глобальной системы раннего оповещения о пуске ракет NORAD. Станции NORAD протянулись через север Канады от Аляски до Гренландии, а подземный командный центр расположился вблизи г. Колорадо-Спрингс в недрах горы Шайенн. Основным недостатком централизованной сети была ее неустойчивость, связанная с тем, что при выходе из строя какого-либо из узлов полностью выходил из строя и весь сектор, находившийся за ним, а при выходе из строя центра управления выходила из строя и вся сеть.
Решение проблемы надежности сети было поручено Управлению перспективных разработок министерства обороны США - DARPA - Defense Advanced Research Project Agency. Основными направлениями исследований стали поиск новых протоколов обслуживания и новых принципов сетевой архитектуры. Полигоном для испытаний новых принципов стали крупнейшие университетские и научные центры США, между которыми были проложены линии компьютерной связи. В результате появилась первая вневедомственная национальная компьютерная сеть, которая получила название ARPANet [45]. Ее внедрение состоялось в 1969 году. Основная идея ARPANet состояла в построении сети из равноправных узлов, каждый из которых должен был иметь собственные блоки приема, обработки и формирования сообщений, что должно было обеспечить общую работоспособность сети даже при выходе из строя множества узлов. Сеть отличалась специально разработанным протоколом IP.
Во второй половине шестидесятых годов двадцатого века проводились серьезные исследования в области локальных сетей в Гавайском университете. Изучались различные методы случайного множественного доступа, получившие общее название ALOHA.
В 1972 году была создана группа INWG (Internet Net-working Working Group) под руководством профессора Стэндфордского университета Винтона Кирфа. Этой группой были разработаны протоколы, которые позднее превратились в протоколы семейства TCP/IP (Transmission Control Protocol / Internet Protocol).
В этом же году была запущена спутниковая сеть с Гавайским университетом, на адресном уровне реализованная на базе протокола IP.
Проверка временем протоколов TCP/IP продолжалась до начала 1983 года. В январе 1983 года Министерство обороны США объявило протоколы семейства TCP/IP своим стандартом, который и по сей день лежит в основе Всемирной сети. Решив таким образом задачу надежности сети, DARPA прекратила свое участие в проекте и передало управление сетью Национальному научному фонду NSF (National Science Foundation).
В 1983 году NSF разработал глобальную сеть NSFNet, основанную на IP- протоколе ARPANet. Потребность в построении новой сети была была обусловлена причинами появления локальных вычислительных сетей, например таких как Ethernet и др. и необходимости их подключения к ARPANet. Такую возможность и предоставила сеть NSFNet, поскольку попытка использовать непосредственно коммуникации ARPANet потерпела неудачу в связи с бюрократией оборонной отрасли.
В 1984 году была введена доменная система имен DNS (Domain Name System). С появлением доменной системы NSF утратил контроль за развитием сети. Тогда и появилось понятие Internet как саморазвивающейся децентрализованной иерархической структуры.
Рассматривая историю развития сетей с точки зрения физической основы, можно заметить явную тенденцию к интеграции всех видов сетей связи в виде единой системы [104, 133].
Так цифровые сети интегрального обслуживания (ISDN - Integrated Services Digital Network) появились как сети, объединяющие телефонные линии с линиями передачи данных, факсимильными сетями. Как стандартизированные появляются сети N-ISDN (Narrowband Integrated Services Digital Network - узкополосная цифровая сеть с интеграцией услуг). Эти сети позволяют объединять несколько видов передаваемой информации в один канал: речь, факсимильные сообщения, компьютерные данные, телеграфные сигналы.
Эти сети стали базой для создания сетей B-ISDN (Broadband Integrated Services Digital Network - широкополосная цифровая сеть с интеграцией услуг), которые интегрируют в одном канале все виды информации с возможностью доступа на скоростях в десятки Мбит/с.
В качестве узлов связи в настоящее время применяется оптоволокно и технологии на его базе [112, 117, 183, 187], которые позволяют передавать информацию с
достаточно большой скоростью (от сотен Мбит/с до десятков Гбит/с). Основными технологиями, обеспечивающими высокоскоростные соединительные линии, являются синхронная цифровая иерархия (SDN - 155 Мбит/с - 39,8 Гбит/с) и асинхронный режим передачи (ATM - 25 Мбит/с - 2,4 Гбит/с) [112, 134].
Для абонентского доступа в настоящее время используется медный кабель. Пропускную способность абонентских линий можно повысить двумя способами: заменой медного кабеля на оптический или использованием особых методов передачи по существующим линиям. Ко второму способу можно отнести технологии xDSL и ADSL - увеличение пропускной способности за счет применения дополнительного кодирования и специальных видов модуляции [38].
Основой для построения сетей интегрального обслуживания является развитие методов коммутации [104, 134]. Выделяют несколько способов коммутации: коммутация каналов, коммутация сообщений, коммутация пакетов, гибридная коммутация, быстрая коммутация.
Коммутация каналов заключается в том, что между двумя абонентами жестко закрепляется ресурс и использоваться другими источниками уже не может. В настоящее время используются следующие типы разделения каналов: временное, частотное, кодовое.
Развитием систем с временным разделением каналов является синхронная цифровая иерархия (СЦИ - SDN).
В телеграфных сетях основным средством передачи информации является коммутация сообщений, которая заключается в передаче и приеме целого сообщения без установки соединения между конечными пользователями сети. Недостатком является большой размер буфера для уменьшения вероятности потерь и сложность управляющих устройств. Достоинство - высокий коэффициент использования каналов.
Развитие коммутации сообщений привело к появлению коммутации пакетов [16]. В основе этой коммутации - разделение поступающей информации на не-сколько частей определенного размера, добавление заголовка и дальнейшей передаче сообщения по частям. Разделение на отдельные стандартные пакеты позволило уменьшить сложность управляющих устройств, уменьшить время задержки пе-
редачи сообщения, а также ограничить и стандартизировать размер буфера, что привело к снижению вероятности потерь сообщения.
Задача повышения пропускной способности сети и возможности передачи неоднородной нагрузки вызвала появление гибридной коммутации каналов. Часть информации в этом случае передается на основе коммутации каналов, а часть с использованием коммутации пакетов.
Требование широкополосной передачи, повышение скорости передачи информации - все это привело к появлению методов быстрой коммутации. Как разновидность пакетной коммутации быстрая коммутация привела к появлению сетей с ретрансляцией кадров (Frame Relay) с переменной длиной единицы информации и ретрансляцией ячеек (ATM) с постоянной длиной единицы информации, но достаточно малой, чтобы обеспечить небольшой уровень задержки.
Подводя небольшой итог, можно сказать, что для обеспечения широкополосного доступа к ресурсам, требующим малых уровней задержки, таких как диалоговый обмен, речь, видеотелефон и т.п. необходимо использовать технологии, основанные на пакетном режиме с переходом к быстрым методам, использующим виртуальные каналы внутри одного физического. Наиболее предпочтительным с точки зрения качественного представления широкополосного доступа и эффективного использования полосы пропускания является метод ретрансляции ячеек, в частности ATM.
Изучение свойств и развитие сетей продолжается и сегодня. Важным аспектом исследования сетей, как это было уже замечено выше, является математическое моделирование. Математическое моделирование сетей позволяет экспериментировать, когда это невозможно произвести на реальном объекте. Методы математического моделирования оказываются незаменимыми в процессе проектирования новых объектов [61], в частности и сетей, так как позволяют заранее получить представление о параметрах, достоинствах и недостатках разрабатываемых объектов. Математическое моделирование компьютерных сетей представляет собой описание с помощью математических объектов основных процессов функционирования системы.
Первые работы А.К. Эрланга появились в начале прошлого столетия и были вызваны практическими потребностями, в частности требованиями к проектированию
и расчету систем обслуживания телефонного трафика (телетрафика). Теорию массового обслуживания - математический аппарат, представляющий собой раздел теории вероятностей - начал свое развитие с теории телетрафика [6, 69, 100].
Основной целью моделирования сетей является прогноз производительности се-
> ти, оценка характеристик использования ее ресурсов. Согласно аппарату теории
массового обслуживания компьютерные сети рассматриваются как системы массового обслуживания, что позволяет находить распределения вероятностей состояний системы. Знание этого распределения позволяет находить и другие важные характеристики и оценивать, таким образом, поведение системы.
Основным средством исследования систем массового обслуживания являются марковские процессы. Результаты исследования марковских процессов приведены в работах [5, 20, 36,47, 74, 110, 123, 136].
Обобщением марковских процессов являются случайные процессы, называемые
полумарковскими [26]. Марковские цепи накладывают ограничение на исследуе
мые процессы из-за геометрического распределения времени пребывания в данном
состоянии, что обусловлено требованием перехода из одного состояния марков-
> ской цепи в другое в каждый единичный промежуток времени. Если же снять это
ограничение и допустить произвольное распределение времени пребывания в данном состоянии, то получится полумарковский процесс [3, 5, 12, 20, 47, 74, 110].
Проведем небольшой обзор результатов исследования систем массового обслуживания, полученных при использовании аппарата теории вероятностей и теории массового обслуживания.
В работе [ПО] были обобщены практически все предыдущие результаты и зало
жены основы дальнейшего развития теории массового обслуживания и ее прило
жений. В работе описаны как марковские так и немарковские модели массового
обслуживания. Рассмотрены математические модели, такие как детерминированная
система, вероятностная модель, пуассоновский процесс, модель Эрланга, метод
* Монте-Карло и возможности метода разложения в степенной ряд.
Дальнейшим развитием работ по теории массового обслуживания явились работы Л. Клейнрока [45-47], в которых систематизированы ранее полученные результаты и добавлены собственные разработки теории, включая практические приложения к вычислительным сетям, в частности к прародительнице сети Internet сети
ARPANet. Систематизация Клейнрока заключается в разделении теории массового обслуживания на несколько разделов: элементарную теорию массового обслуживания, промежуточную теорию массового обслуживания и общую теорию массового обслуживания.
В первом разделе автор приводит вывод вероятностно-временных характеристик для систем с пуассоновским потоком вызовов и экспоненциальным распределением обслуживания на основе процессов размножения и гибели.
Промежуточная теория массового обслуживания посвящена вопросам исследования систем массового обслуживания с произвольным распределением или времени обслуживания или времени поступления вызовов.
В общей теории массового обслуживания представлен спектральный метод решения уравнений с использованием теории функций комплексного переменного. Дальнейшее развитие идей этого метода представлено в работе [45], где Клейнрок приводит исследование сети ARPANet на основе полученных в предыдущей работе теоретических выводов.
В связи с тем, что получение точных выражений для вычисления требуемых вероятностно-временных характеристик является достаточно сложной задачей, возникло направление решения задач теории массового обслуживания с помощью асимптотических методов [2, 12, 27, 38, 49, 81]. Эти методы позволяют отойти от явной разрешимости с использованием диффузионных процессов.
Для исследования математических моделей сетей связи также активно применяются асимптотические методы. В частности, А.А. Назаровым для исследования математических моделей сетей предложен метод асимптотического анализа маркови-зируемых систем [80]. Суть этого метода заключается в приближенном описании диффузионными процессами реальных процессов, которые протекают в системе.
Потребности математического моделирования сетей связи случайного множественного доступа привели к появлению систем массового обслуживания с повторными вызовами. Исследованием систем с повторными вызовами занимались Бочаров П.П. [13, 14], Фалин Г.И. [120, 121, 156-160], Степанов СП. [196-199], Климе-нок В.И. [32-35, 147, 148, 153-155, 174, 175, 179], Назаров А.А., Хомичков И.И. [126, 127, 170, 171],ШохорС.Л. [131,132].
Метод диффузионной аппроксимации также применен в работах [166, 167, 168, 176, 184].
Сети случайного множественного доступа получили наибольшее распространение. Компьютерные сети связи, управляемые протоколами множественного доступа реализуются на основе топологий шина или звезда [10, 17, 37, 70, 103, 111, 117, 122, 134]. Характерное отличие этих сетей в обязательном наличии общего ресурса (центрального узла в звезде или моноканала в шине). Этот общий ресурс совместно используется всеми абонентскими станциями (АС). Принцип случайного множественного доступа состоит в следующем. Сформировав сообщение, АС отправляет его в общий ресурс сети, где происходит обслуживание этого сообщения, если ресурс свободен. Если же ресурс занят в это время другим сообщением, то возникает конфликт (коллизия) и оба сообщения искажаются и возвращаются на свои АС, откуда после случайной задержки вновь отправляются на общий ресурс. В случае успешной передачи сообщения по общему ресурсу, считается, что сеанс связи реализован успешно.
Метод случайного доступа был апробирован в 60-х годах в Радиосети Гавайского университета. Это был протокол ALOHA [9, 10, 38, 87, 97, 98, 102, 121, 128, 129, 130].
В сетях, управляемых протоколом ALOHA, заявки, попавшие в конфликт, продолжают обслуживание в искаженном режиме и лишь после завершения такого обслуживания переходят в источник повторных вызовов (ИПВ). Заявки, поступившие во время обслуживания искаженных заявок, также искажаются и остаются на приборе до завершения их обслуживания, после этого также переходят в ИПВ.
Математическое моделирование сетей множественного доступа, управляемых протоколом ALOHA можно найти в работах Назарова А.А. и Юревич Н.М. [97, 98], Фалина Г.И. [120, 121], Цыбакова Б.С. [128], Одышева Ю.Д. [87]. В этих работах теоретически показана возможность возникновения в такого рода сетях явления бистабильности.
Заметим, что возможность возникновения явления трехстабилыюсти также доказана. Это можно найти например в работах Назарова А.А. и Цоя С.А. [92, 93].
Сети случайного доступа с оповещением о конфликте отличаются переходом в ИПВ попавших в конфликт заявок и началом реализации от этого момента этапа
>
оповещения о конфликте. Заявки, поступившие в ресурс во время реализации этапа оповещения о конфликте, переходят в ИПВ.
Исследование сетей множественного доступа с оповещением о конфликте можно найти в работах [9, 15, 38, 52-54, 60, 62-66, 72, 73, 81, 82, 85-98, 101, 102 ] и др.
Как известно в 1980 году был принят стандарт Ethernet. В сети случайного множественного доступа Ethernet реализуется протокол доступа с резервированием канала и оповещением о конфликте. Заявками считаются сигнал-запросы на резервирование, во время реализации которого и возможны конфликты. Оповещение о конфликте начинается с момента наступления конфликта. Требования, поступившие на этапах обслуживания заявки и оповещения о конфликте, переходят в источник повторных вызовов, не искажая текущих режимов на приборе.
Исследования математических моделей сетей, управляемых протоколом Ethernet, представлено в трудах [124, 143, 178, 181].
Заметим, что много внимания уделяется проблеме устойчивости сетей связи. В работах [60, 73, 84, 90, 121, 128] показано, что сети связи с постоянной интенсивностью входящего потока и бесконечным числом АС не имеют стационарного режима. Это означает, что задержка в передаче пакетов постоянно растет по мере продолжительности работы сети связи.
Проблему стабилизации сетей решают разработкой новых протоколов. Например, в работах Кузнецова Д.Ю. и Назарова А.А. проводится исследование математических моделей сетей множественного доступа, управляемых адаптивным протоколом [62-66].
Основным толчком к исследованию характеристик потоков информации в системах связи послужило несоответствие между проектируемой нагрузкой и существующей [141, 143, 162, 181, 204, 205].
Исследования в области измерения и анализа поступающей нагрузки в основном связаны с сетью Интернет [139, 140, 141, 145, 161, 162, 163, 180, 204] и сетью Ethernet [124, 143, 178, 181]. Наибольшее внимание привлекает глобальный трафик в сети Интернет, что отображено в работах [139, 140, 145, 162, 180, 182, 188, 193]. Исследованию потоков в локальных сетях посвящены работы Богуславского Л.Б. [11], Назарова А.А. и Колоусова Д.В. [52-54], Лебедева Е.А. и Чечельницкого А.А.
[67-68], а также [165, 194, 195]. Важнейшим направлением является оптимизация сетей связи по некоторым параметрам [1, 75, 76, 78, 200].
Необходимость оптимизации сетей связи, математическими моделями которых являются системы массового обслуживания, привела к рассмотрению управляемых систем массового обслуживания [24, 56, 83, 109]. По-другому такие системы называют системами с переменными параметрами. Таким системам посвящены работы Коротаева И. А. [21-23, 56-58]. Изменение параметров может происходить как внутри системы в зависимости от ее состояния, так и иод воздействием внешних условий, например изменения случайной среды, в которой и функционирует система. В случае нестационарности внешней среды параметры системы массового обслуживания могут быть детерминированными функциями времени [144]. Впервые такие системы были рассмотрены в 1956 году. Интерес к такого рода исследованиям оживился в 1970 годах в связи с развитием вычислительных сетей и необходимостью исследования потоков событий в сетях. В работе [42] представлены исследования систем массового обслуживания со случайной интенсивностью входящего пуассоновского потока. Впервые понятие дважды стохастического входящего потока было введено Кингманом [173]. Системы массового обслуживания с входящим дважды стохастическим пуассоновским потоком не сводятся к классическим СМО с постоянными параметрами, поскольку входящий поток в данном случае не является рекуррентным.
Можно рассматривать задачу, когда изменяются не только параметры входящего потока, но и параметры обслуживания. Такие СМО принято называть системами массового обслуживания, функционирующими в случайной среде [33, 50]. Соответствующие исследования применительно не только к системам массового обслуживания, но и к сетям связи представлены в трудах Дудина А.Н. [33, 149, 150-152, 154-155, 175, 179, 186, 201, 202]. Возможные значения параметров СМО связываются со значениями некоторого случайного процесса, который еще называют управляющим процессом. Изменения значений управляющего процесса приводит к изменению параметров функционирования системы.
Примеры технических задач, приводящих к анализу СМО в случайной среде можно найти в работах [6, 28-31, 50, 113, 177, 203].
Вообще говоря, впервые понятие СМО, функционирующая в случайной среде, появилось в работе [189]. Рассматривается два вида управляющих процессов: марковский [28-30, 50, 119, 169, 177, 185, 186, 189, 190, 201, 202, 206, 207] и полумарковский [56-58, 105, 113]. Первой работой по исследованию характеристик СМО,
—^
» функционирующей в случайной среде, была статья Ехиали и Наора [207]. В этой
статье рассматривалась система массового обслуживания М \ М | 11 оо, управляемая
цепью Маркова с двумя состояниями. Этот результат вскоре был обобщен в рабо
тах Ехиали [206] и Педыо [189], где в качестве управляющего процесса фигуриро
вала цепь Маркова с произвольным конечным числом состояний. Педью [189] бы
ло получено условие существования стационарного режима в данной системе мас-
I сового обслуживания. Ньютс [185-186] свел задачу исследования данной СМО в
случайной среде для частного случая к решению матричного уравнения.
Задача исследования системы M|G|l|<» в случайной среде впервые была поставлена Ныотсом [185] и сведена к решению матричных уравнений. А.Н. Дудин [28-30] свел задачу отыскания стационарного распределения виртуального времени ожидания для СМО Л/|<7|і|оо, управляемой марковской цепью с конечным чис-
лом состояний к решению системы линейных уравнений.
Важно заметить, что СМО, функционирующая в случайной среде, как показано в
работе [192], может служить аппроксимацией СМО с пуассоновским входящим по
током периодической интенсивности при специально подобранном управляющем
процессе.
* В ряде работ при анализе СМО, функционирующей в случайной среде, также
применяется метод диффузионной аппроксимации. В этом случае задача сводится к анализу характеристик диффузионного процесса с изменяющимися в случайные моменты времени коэффициентами переноса и диффузии. Плотности распределения можно найти из системы дифференциальных уравнений Фоккера-Планка. Такой подход используется в [50, 177].
Отдельный интерес представляет случай СМО в случайной среде, когда от состояния управляющего процесса зависят параметры только входного потока (как правило пуассоновского). В случае когда входящий поток пуассоновский, а управляющий процесс есть цепь Маркова с конечным числом состояний, такой поток называется МС-потоком (Markov Chain) [6]. В работах [6, 99] под МС-иотоком иони-
мается наиболее общий поток. Для МС-потока допускается возможность одновре
менной смены состояний управляющего процесса и прихода заявки, что недопус
тимо для описанного выше потока. В терминологии [99] описанный нами поток на
зывается пуассоновским потоком на цепи Маркова или ММР-потоком (Markov
Modulated Poisson). ММР-поток является частным случаем общего МС-потока.
МС-поток хорошо аппроксимирует потоки сообщений в сетях [6, 172].
Для отыскания характеристик СМО с входящим МС-потоком Башариным Г.П. [6] был предложен так называемый метод эквивалентных замен. Суть метода состоит в замене МС-потока рекуррентным, параметры которого подбираются из условия совпадения моментов поступающей нагрузки. МС-поток вообще говоря является частным случаем дважды стохастического пуассоновского процесса [173].
Более сложной моделью управляющего процесса является полумарковский процесс. СМО, управляемая полумарковским процессом Л/|М|і|оо рассматривалась
Н.Н. Поповым [173].
Исследованию сетей связи в случайной среде уделяется недостаточно внимания. Данная работа некоторым образом восполняет этот пробел.
Исследование асимптотических средних характеристик неустойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова
В состоянии {0,/,5} по истечении промежутка времени At система останется с вероятностью 1 - (А + /у - qss)At + o(At), то есть если на прибор не поступит новая заявка (вероятность этого события равна 1 - АДґ + o{At)), ни одно требование не обратится из ИПВ (вероятность этого события равна l-iyAt + o(At)), состояние случайной среды не изменится (вероятность этого события равна 1 + qssAt + o{At)).
Из состояния {1,/,5} в состояние {0,/,5} система перейдет за время At с вероятностью \x(s)At + o(At), то есть если на приборе завершится обслуживание заявки.
Из состояния {2,/,5} в состояние {0,/,5} система перейдет за время At с вероятностью (l/a)At+o(At), то есть если завершится этап распространения сигнала о конфликте.
Из состояния {0,/,5,} в состояние {0,/,5} система перейдет за время At с вероятностью qssAt + o(At), то есть если случайная среда перейдет из состояния S S , В СОСТОЯНИе 5. ЗаМеТИМ, ЧТО 5, =1,2,...,5-1,5 + 1,...,5 .
Переход в другие состояния возможен с вероятностями, имеющими больший порядок малости, чем At. В результате получаем первые S уравнений системы. Р0 (/, 5, t + А?) = (1 - (А + /у - qss)А/)Р0 (/, 5,0 + u(5)AtP} (/, 5, t) + 1 s + -AtP2(i,s,t)+ 2 0(/,5,,/) + 0( ) a .=i
Допустим, что в момент времени t + At система будет находиться в состоянии {l,i,s], то есть прибор занят обслуживанием заявки, в ИПВ находится / требований, случайная среда в состоянии s. В это состояние система может перейти, если в момент времени t она находилась в одном из следующих состояний: 1) {1,/,5} - прибор занят обслуживанием заявки, в ИПВ содержится / требований, случайная среда в состоянии s; 2) {0,/,5} - обслуживающий прибор свободен, в ИПВ находится / требований, случайная среда в состоянии s; 3) {0,/ + 1,5} - обслуживающий прибор свободен, в ИПВ содержится / + 1 требований, случайная среда в состоянии s; 4) {1,/,-Sj} - прибор занят обслуживанием заявки, в ИПВ / требований, случайная среда в состоянии 5}, Причем Sj =1,2,...,5-1,5 + 1,...,5.
В состоянии {1,/,5} по истечении промежутка времени At система останется с вероятностью 1 - (X + /у + ц(5) - qss )At + o(At), то есть если на прибор не поступит новая заявка (вероятность этого события равна 1 - XAt + o{At)), ни одно требование не обратится из ИПВ (вероятность этого события равна 1 - /у A/ + о{Аі)), не завершится обслуживание заявки (вероятность этого события равна 1 - \\{s)At + о(А0 ), состояние случайной среды не изменится (вероятность этого события равна l + qssAt + o(At)).
Из состояния {0,/,5} в состояние {1,/,5} система перейдет за время At с вероятностью XAt + o(At), то есть если на прибор обратится новое требование. Из состояния {0,/ + 1,5} в состояние {1,/,5} система перейдет за время At с вероятностью (/+ 1)уА/+ o(Ar), то есть если на прибор обратится требование из ИПВ и встанет на обслуживание.
Из состояния {l,/,5j} в состояние {1,/,5} система перейдет за время А/ с вероятностью qssAt + o(At), то есть если случайная среда перейдет из состояния 5t 5, в состояние 5. Заметим, что sx = 1, 2,..., 5 -1,5 +1,..., S .
Переход в другие состояния возможен с вероятностями, имеющими больший порядок малости, чем At. В результате получаем вторые S уравнений системы. Р1 (/, 5, t + АО = (1 - (X + /у + [i(s) - qss )At)P (/, 5, t) + XAtP0 (і, 5,/) + + (/+і)уд 0(/ +1,5,0 + 2 ч і5Щ (i s\ 0 + (А0 5,-1 st s
Допустим, что в момент времени t + At система будет находиться в состоянии {2,i,s), то есть на приборе реализуется этап оповещения о конфликте, в ИПВ находится / требований, случайная среда в состоянии s. В это состояние система может перейти, если в момент времени / она находилась в одном из следующих состояний: 1) {2,/,s} - на приборе реализуется этап оповещения о конфликте, в ИПВ содержится / требований, случайная среда в состоянии s;
2) {1,/-2,5} - прибор занят обслуживанием заявки, в ИПВ находится і-2 требований, случайная среда в состоянии s;
3) {1,/-1,5} - прибор занят обслуживанием заявки, в ИПВ содержится /-1 требований, случайная среда в состоянии s;
4) {2,/-1,5} - на приборе реализуется этап оповещения о конфликте, в ИПВ находится /-1 требований, случайная среда в состоянии s;
5) {2,/,5j} - на приборе реализуется этап оповещения о конфликте, в ИПВ / требований, случайная среда в состоянии 5,, причем 5, =1,2,...,5-1,5 + 1,...,5.
В состоянии {2,/,5} по истечении промежутка времени А/ система останется с вероятностью 1-(Х + (1/а)-qss)At + o(At), то есть если на прибор не поступит новая заявка (вероятность этого события равна 1 - XAt + o(At)), реализация этапа оповещения о конфликте не завершится (вероятность этого события равна \-(l/a)At + o(At)), состояние случайной среды не изменится (вероятность этого , события равна 1 + qssAt + o(At) ).
Исследование асимптотических средних характеристик устойчивых сетей множественного доступа, функционирующих в случайной среде, управляемой цепью маркова
Под асимптотическими средними характеристиками устойчивых сетей множественного доступа, функционирующих в случайной среде, будем понимать распределение вероятностей Rk (х) состояний к канала и функцию х = х(т). Теорема 5. Асимптотически при N -»со распределение вероятностей Rk (х) состояний к канала имеет вид R (ЛЛ = Ц1-х) + ух + Ц(х) а(Ц1 -х) + ух)2 + 2(Х(1 -х) + ух) + \\)(х) вд= bz E , а (Х(1 -х) + ух) + 2(Ц1 - х) + ух) + г) (х) R2 W - —zz—; 7г—тгт:—; ;— тт » (2-6) а(к(1-х) + уху а(Х(1 -х) + ух)2 + 2(Ц1 - х) + ух) + ip(x) где а, X и у заданы, х = х(х) -детерминированная функция, определяемая обыкновенным дифференциальным уравнением вида х\т) = Х(1-х)-\\і(хЩ(х), (2.7) в котором ці(х) есть величина вида 5 I S у(х) = (syQ s) / Q,(x,5), (2.8) s=l / =1 здесь Qx(x,s) определяется решением Qk(x,s), к = 0,1,2 системы (2.12) и условием нормировки (2.13).
Доказательство. В системе (2.5) перейдем к пределу при є- 0 и, полагая, что существуют конечные пределы limHk(y,s,T,E) = Hk(y,s,x), (2.9) -»0 получим систему 1 s (Ц1-Х) + УХ)//0( ,5,Т) = Ц(5)Я1(У,5,Т) + -Я2( ,5,Т)+ Я0(У,51,Т) )5 5,=1 (X(l -x) + yx + \i(s))H{(y,s,x) = (7.(1 -x) + yx)HQ(y,s,x) + Я,( -,5,,T) I5 , 5,=1 1 S -Я2( 5,т) = (Ц1-л) + у )Я1(у,5,т)+ Яг .т) . (2.10) a 5,=1
В силу однородности полученной системы линейных алгебраических уравнений будем искать ее решение Hk(y,s,x) в виде Hk(y,s,x) = Qk(x,s)H(y,x), (2.11) где Н(у,х) является мультипликативной составляющей решения однородной системы, имеет смысл плотности распределения процесса у(х), a Qk(x,s), имеющая смысл условного совместного распределения вероятностей состояний к канала и s среды при условии х(х) = х, как следует из (2.10), определяется системой вида 1 s (ЦІ -х) + yx)QQ (х, s) = \i(s)Q] (х, s) + -Q2 (х, s) + ( ( , i )(7,,,, s (X(l -x) + yx + \i(s))Q{ (x, s) = (ЦІ -x) + yx)QQ (x, s) + Qx (x, s, )qSiS, 5,=1 1 S -Q2(x,s) = (X(l-x) + yx)Ql(x,s) + 62( 1).. (2.12) a «1-і Для любого значения x є [0;1] это однородная система 35 линейных алгебраических уравнений, определитель которой очевидно равен нулю, поэтому для нее существует множество нетривиальных решений, единственное из которых определяется условием нормировки 22&(х,5)-1. (2.13) =05=1 Обозначим 2 2Л )-Ф), (2.14) А-0 S 2Qk(x,s) = Rk(x), (2.15) 5=1 здесь Rk(x) маргинальное распределение вероятностей состояний к канала связи, a r(s) - маргинальное распределение вероятностей состояний s случайной среды. Для этих распределений также должны выполняться условия нормировки J ф)-1, (2.16) 5=1 2 ( )-1- (2-17) к=0
Сложим по к уравЕїения системы (2.12) и с учетом обозначения (2.14) получим систему S уравнений вида ф,) =0,s = l,2,...,S, (2.18) 5,=1 которая совместно с условием нормировки (2.16) определяет стационарное распределение вероятностей r(s) состояний цепи Маркова s(t).
Сложим по s уравнения системы (2.12), учтем (2.15) и (2.1), обозначим S ] \i(s)Qi (х, s) = -ф( )Я] ( ) , 5=1 то есть величина \\)(х) определяется равенством 5 /5 ! ( ) = 2 s)Q ,s) 2Q,(x,s), (2.19) 5=1 / 5=1 тогда система (2.12) примет вид 1 (ЦІ -х) + yx)RQ(x) = (x)R](x) + -R2(x), а (ЦІ - х) + ух + \/( ))Лі ( ) = (ЦІ -х) + yx)R0 (х), -R 2 (х) = (Ц\ -х) + yx)R] (х). (2.20) а Система (2.20) совместно с условием нормировки (2.17) дает решение X(l-x) + yx + i\ (x) я(Х.(1 - х) + ух) + 2(Х(1 - х) + ух) + гр(х) ЦІ - х) + ух я (Ці - х) + ух)2 + 2(Ц1 -х) + ух) + ty(x) J (2.21) R2(x) = а(к(1-х) + ухУ д(Х(1 - л:) + ух)2 + 2(к(1 -х) + ух) + ty(x) Вид равенств (2.21) совпадает с видом равенств (2.6). Далее покажем, что х = х(х) является детерминированной функцией. В системе (2.5) функции Hk(y±e,s,T,&) разложим в ряд по приращениям аргумента у с точностью до о(г), получим -гхЧт)дНо(У, ,Х,г)+(к(1-(х + гу)) + у(х + гу))Н0(у,5,т,Е) = ду а = [i(s)Hx(y,s,x,) + -H2(y,s,x,z)+ yH0(y,sx,x,z)q 5,=1 -ExXT)dH](y:S X e)+(X(l-(x + zy)) + y(x + By) + [i(s))H,(y,s,T,z)== ду = (\(1-(х + у)) + у(х+Еу))Н0(у, ,Т,є) + уХдНо(У 3 Х Є) + ду + 5Я1 51 Т +0 5,=1 .. dH2(y,S,X,E) 1.., ч /wi / \\ -ЕХ\Х)— - - + -H2(y,s,x,z) = (k(l-(x + Ey)) + ду а + y(x+Ey))H1(y,S,T,E)-E — $k(\-x)H2(y,S,T,E) + ду + (2Ц1- х) + ух у Е)} + H2(y,sux,E)qSiS +О(Е). (2.22) 5,=1 Все уравнения системы (2.22) просуммируем по к и по s и, учитывая (2.1) запишем - ЕХ (Х) ду S k=Qs=\ s 22я 5 т Е) =є "іу-х2Яо 5 т " s=l s -X(l-x) H2(y,s,x,E)-(2X(l-x) + yx) H](y,s,x,E) . + O(E) . I 5=1 S=\ Поделим на є обе части полученного уравнения, выполним предельный пере ход (2.9), учтем (2.11), получим -(2X(l- ) + Y )Y 6,( ) 7 -Согласно условию нормировки (2.13) и обозначению (2.15), можно записать ( (т) + yxRQ (х) - ЦІ - x)R2 (х)- (2Х(1 -х) + ух)Щ {х)}Ш У = 0. ду Поскольку производная плотности распределения Н(у,х) не может тождественно равняться нулю, следовательно, функция х — х(т) является решением обыкновенного дифференциального уравнения х (т) = yxR0 (х) + ЦІ - x)R2 (х) + (2Л.(1 -х) + yx)Rx (х). (2.23) В силу равенств (2.21) уравнение (2.23) можно представить в виде х\х) = Х(1 -х)- (ЦІ -х) + yx)(R0 (х) - Я, ( )) = X(l -х)- V (AT)/?, (Х) , (2.24) где \])(х) определяется равенством (2.19), в котором Qx(x,s) определяется решением системы (2.12) и условием нормировки (2.13). Таким образом, (2.24) совпадает с (2.7). Теорема доказана.
Исследование величин отклонения нормированного числа заявок В источнике повторных вызовов от их асимптотического среднего
Рассмотрим математическую модель сети множественного доступа с оповещением о конфликте в виде однолинейной системы массового обслуживания (СМО), на вход которой поступает простейший с параметром X ноток заявок. Прибор этой СМО может находиться в одном из трех состояний: к = О, если он свободен; к=1, если он занят обслуживанием заявки; к = 2, если на приборе реализуется этап оповещения о конфликте. Заявка, заставшая в момент поступления прибор свободным, начинает немедленно обслуживаться. Если в течение обслуживания этой заявки другие требования на прибор не поступают, то исходная заявка по завершении обслуживания покидает систему. Если во время обслуживания одной заявки поступает другая, то возникает конфликт. От этого момента начинается этап оповещения о конфликте. Заявки, попавшие в конфликт, а также поступившие на этапе оповещения о конфликте, переходят в источник повторных вызовов (ИПВ). Повторное обращение заявок к прибору из ИПВ происходит после случайной задержки, продолжительность которой имеет экспоненциальное распределение с параметром у. Число заявок в ИПВ обозначим /. Длины интервалов оповещения о конфликте также имеют экспоненциальное распределение с параметром М а, где а - средняя продолжительность этих интервалов.
Сеть функционирует в случайной среде. В качестве математической модели случайной среды рассмотрим полумарковский процесс s(t) с непрерывным временем /, то есть такой дискретный случайный процесс, который принимает значения из конечного множества состояний s = \,2,...,S и для которого вложенная по моментам времени tn изменения состояний цепь s(tn) является Марковской. Времена пребывания этого процесса в различных состояниях являются условно независимыми случайными величинами, распределение вероятностей значений которых зависит лишь от номера состояния полумарковского процесса.
Для определения полумарковского процесса s(t) зададим стохастическую матрицу одношаговых вероятностей ps s переходов вложенной цепи Маркова PSls2 = P(S(tn+l) = s2 П п) = 5l) при этом будем полагать, что pss = 0. Понятно, что » 5 2лЛ-1, = 1,2,...,Я. (4.1)
Также зададим набор функций распределения Gs(x) значений времени пребывания полумарковского процесса в -м состоянии.
Будем полагать, что влияние случайной среды на функционирование сети определяется зависимостью интенсивности обслуживания ц от состояний s случайной среды, то есть ц = n(s). Вероятность окончания обслуживания заявки на приборе за бесконечно малый промежуток времени At равна \i(s)At + o(t), при условии, что среда находится в состоянии s.
В силу свойств приведенной математической модели трехмерный случайный вектор {k(t),i(t),s(t)} изменения во времени состояний {k(t),i(t)j математической 1 модели сети связи и состояний (s(/)} математической модели случайной среды яв ляется нолумарковским процессом.
Для исследования описанной математической модели марковизируем процесс {k(t),i(t),s(t)} методом дополнительной переменной. Введем переменную C,(t), имеющую смысл длины интервала времени от момента / до момента смены текущего состояния случайной среды, тогда процесс изменения значений вектора {k(t),i(t),5(/),C,(t)} является марковским процессом. Обозначим P(k(t) = k,i(t) = і,s(t) = s,C,(t) Q = Pk(i,s,Сt).
В любой момент времени должно выполняться условие нормировки 2 оо 5 I =0/=0 s=l
Составим систему конечно-разностных уравнений для вероятностей Pk{i,s,C3,t) А/-методом.
Допустим, что в момент времени / + At система будет находиться в состоянии {О,/,s, }, то есть обслуживающий прибор свободен, в ИПВ / требований, слу чайная среда в состоянии s, до смены которого осталось времени меньше, чем С,. В это состояние система может перейти, если в момент времени t она находилась в одном из следующих состояний:
1) {0,i,s,C, + At} - обслуживающий прибор свободен, в ИПВ / требований, случайная среда в состоянии s, до смены которого осталось времени меньше, чем + At, но не меньше, чем At;
2) {\,i,s,C, + At} - прибор занят, в ИПВ / требований, случайная среда в состоянии s, до смены которого осталось времени меньше, чем С, + At, но не меньше, чем At;
3) {2,i,s,С, + At} - на приборе реализуется этап оповещения о конфликте, в ИПВ / требований, случайная среда в состоянии s, до смены которого осталось времени меньше, чем + At, но не меньше, чем At;
4) {0,i,Si,At} -обслуживающий прибор свободен, в ИПВ / требований, слу чайная среда в состоянии sx, причем s = 1,2,...,5-1,5 + 1,...,S и до изменения со стояния случайной среды осталось времени меньше, чем At.
Из состояния {0,i,s,C, + At} в состояние {0,/,5,( } по истечении промежутка времени At система перейдет с вероятностью l-(X + iy)At + o(At), то есть если на прибор не поступит новая заявка (1-XAt + o(At)), ни одно требование не обратится из ИПВ (1-iyAt + o(At)) и до изменения состояния случайной среды останется времени меньше, чем C, + At, но не меньше, чем At.
Из состояния {l,i,s,C, + At} в состояние {О, i,s,t} система перейдет за время At с вероятностью \i(s)At + o(At), то есть если на приборе завершится обслуживание заявки и до изменения состояния случайной среды останется времени меньше, чем С, + At, но не меньше, чем At.
Из состояния {2,/,5, + At} в состояние {0,/,5, } система перейдет за время At с вероятностью (l/a)At + o(At), то есть если завершится этап распространения сигнала о конфликте и до изменения состояния случайной среды останется времени меньше, чем С, + At, но не меньше, чем At.
Исследование асимптотических средних характеристик неустойчивых сетей множественного доступа, функционирующих в полумарковской среде
Покажем, что для достаточно малых значений параметра є случайный процесс z(x) = JC(T) + sy, аппроксимирующий процесс изменения числа заявок в ИПВ /(т/ ) является однородным диффузионным процессом. Докажем следующую теорему. Теорема 15. С точностью до о(є) случайный процесс z(x) является решением стохастического дифференциального уравнения dz(T) = A(z)dx + eB(z)dw(x), (4.39) где w(x) - есть стандартный винеровский процесс, функция A(z) определяется правой частью дифференциального уравнения (4.6), а функция B(z) - равенством (4.17), то есть z(x) является однородным диффузионным процессом с коэффици ентом переноса A(z) и коэффициентом диффузии є В (z).
Доказательство. Поскольку z(x) = х(х) + гу, то дифференцируя z(x) по т получаем dz(x) = x (x)dx + Edy. (4.40) В силу (4.6) и (4.16) имеем dz(x) = [-xR0(x) + XR2(x) + (2X + х)Я, (x)] dx + + zy—{- xR0 (x) +XR2 (x) + (2X. + x)R{ (x)}dx + zB(x)dw(x). dx
Так как правая часть содержит разложение в ряд по приращениям zy аргумента х, то можно записать dz(x) = [-(х + zy)R0 (х + zy) + XR2 (х + zy) + (2Х + х + zy)R{ (х + zy)]dx + + zB(z - zy)dw(x). Заметим, что z(x) = х(х) + zy, тогда с точностью до о(г), имеем dz(x) = [-zR()(z) + XR2{z) + (2Х + z)Rx (z)]dx + zB(z)dw(x) + o(z).
С учетом (4.6) уравнение (4.40) окончательно примет вид dz(x) = A(z)dx + zB(z)dw(x) + o(z). Таким образом, z(x) является однородным диффузионным процессом с ко эффициентом переноса A(z) и коэффициентом диффузии є В (z) и определяется с точностью до o(z) стохастическим дифференциальным уравнением вида (4.39). Теорема доказана.
Следствие 15.1. Плотность распределения вероятностей значений процесса г(т) имеет вид 2 А(и) . 1 2;,н2г ч .ее%« ) F(Z) = /V) г,Ю, (4 41) \-L -eA»2W dz ов \z) где A(z) определяется правой частью дифференциального уравнения (4.6), B(z) -равенством (4.17). Доказательство. Обозначим F(z,x) плотность распределения вероятностей значений процесса z(x), тогда можно записать уравнение Фоккера-Планка для плотности этого процесса dF(z,x) д , х є2 д2 = {A(Z)F(Z,X)} + - {B2(Z)F(Z,X)}, дх dz" 2 dz2 где A(z) определяется правой частью дифференциального уравнения (4.6), B(z) -равенством (4.17). Рассмотрим функционирование процесса z(x) в стационарном режиме, то есть F(z,x) = F(z), тогда стабильное распределение можно найти из уравнения Фоккера-Планка 2 2 0 = - -{A(Z)F(Z)} + - \B2(Z)F(Z)}. (4.42) dz 2 dz Данное уравнение является однородным дифференциальным уравнением второго порядка. Обозначим B2(z)F(z) = G(z). (4 A3) Понизим порядок уравнения (4.43) и, положив константу, возникшую в результате интегрирования, равной нулю, запишем dG(z) 2 A(z) G(z). dz 2 B2(z) Проинтегрируем последнее уравнение iG(u) г2І0В2(и) выполним преобразования \n\G(z)\ = ] -du + \n\C\, z2 B2(u) G(z) = C-el " " . Учтем замену (4.43) и перепишем последнее уравнение в виде 2 гг Л (и) du F(z) = - -ee2"Ii2(u) . (4.44) B2(z) Константу С найдем из условия нормировки fi z z =1, тогда о оо 4Н „1 П Ґ..\ С-1/ f-J_e« о 2 » . (4.45) Подставим (4.45) в (4.44), получим плотность распределения вероятностей для процесса Z(T) В виде (4.41). Следствие доказано.
Для математических моделей неустойчивых сетей множественного доступа, функционирующих в полумарковской среде: — Найдено асимптотическое среднее нормированного числа заявок в ИПВ; — Найдено распределение вероятностей состояний канала; — Найдены величины отклонения нормированного числа заявок в ИПВ от их асимптотического среднего значения; — Проведена аппроксимация числа сообщений в ИПВ однородным диффузионным процессом; — Найдена плотность распределения вероятностей значений этого процесса.
Итак, в данной работе представлены следующие математические модели сетей множественного доступа в виде систем массового обслуживания: 1. Для бесконечного числа абонентских станций с функционированием в случайной среде, управляемой однородной цепью Маркова с непрерывным временем; 2. Для конечного числа абонентских станций с функционированием в случайной среде, управляемой однородной цепью Маркова с непрерывным временем; 3. Для бесконечного числа абонентских станций с функционированием в диффузионной среде; 4. Для бесконечного числа абонентских станций с функционированием в полумарковской среде.
Применены аналитические и численные методы для исследования данных математических моделей сетей связи с использованием аппарата теории вероятностей и теории массового обслуживания.
Для математических моделей сетей множественного доступа, функционирующих в случайной среде, управляемой цепью Маркова с найдены средние характеристики сетей при больших задержках для сетей с бесконечным числом абонентских станций и при большом количестве абонентских станций для сетей с конечным числом абонентских станций. Также найдены величины отклонения от этих средних. Доказано существование явления многостабильности в такого рода сетях. Показана возможность аппроксимации числа сообщений в ИПВ однородным диффузионным процессом. Найдена плотность распределения вероятностей значений этого процесса и доказана ее многомодальность. Исследовано среднее значение продолжительности времени стабильного функционирования таких сетей. Рассмотрено функционирование сетей в условиях предельно редких изменений состояний случайной среды.
