Исследование математических моделей потоков в сетях случайного множественного доступа

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

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

Очевидно, что возникает вопрос, что мы понимаем под потоком? Под потоком мы понимаем случайный поток однородных событий, который может задаваться одним из трех способов:

1. ?! < ?2 < ¿-з < • • • -временем наступления событий,.

2. Ti, T2, T3,. — длинами интервалов между моментами наступления событий,.

3. n (t) — числом событий, наступивших за время t.

В данной работе используется третий способ задания потоков.

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

1. построение математических моделей потоков в сетях связи с протоколом случайного множественного доступа с оповещением о конфликте;

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

3. построение оценок параметра Л входящего потока и нормированного асимптотического среднего значения 6 числа заявок находящихся в ИПВ по результатам наблюдений за выходящими потоками сети связи;

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

5. исследование влияния явления бистабильности сети на структуру потока.

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

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

2. предложен метод асимтотического анализа потоков в сетях связи случайного множественного доступа;

3. показана асимптотическая нормальность исследуемых потоков в моделях: a) сети связи, управляемой динамическим протоколом случайного множественного доступаb) сети связи с конечным и бесконечным числом станций, управляемой статическим протоколом случайного множественного доступа;

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

5. показано существование явления бистабильности в потоках сетей связи со статическим протоколом случайного множественного доступа для конечного числа абонентских станций;

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

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

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

Публикации. По материалам данной работы опубликовано 7 работ:

1. Колоусов Д. В., Назаров А. А. Дважды стохастический поток, управляемый марковским процессом с дискретным множеством состояний// Материалы Всероссийской конференции «Новые технологии и комплексные решения: наука, образование и производство», г. Анжеро-Судженск 2001 г. Часть II (математика), — КемГУ, 2001. — С.33−37.

2. Колоусов Д. В., Назаров A.A. Исследование выходящего потока локальной вычислительной сети с протоколом случайного доступа// Вестник ТГУ 2002. — № 275. — С.193−194.

3. Колоусов Д. В., Назаров A.A. Исследование выходящего потока локальной вычислительной сети с протоколом случайного доступа// Вестник ТГУ 2002. Приложение 1. Материалы IV Всероссийской конференции «Новые информационные технологии в исследовании сложных стуктур— С.68−72.

4. Колоусов Д. В., Назаров A.A. Исследование выходящего потока сети случайного доступа с конечным числом станций// Материалы Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование», 15 ноября 2002 г., г. Анжеро-Судженск. — Томск: «Твердыня» 2002. — 368с. С.173−174.

5. Колоусов Д. В. Исследование потока заявок, отправленных в источник повторных вызовов сети связи случайного доступа с конечным числом станций// Обработка данных и управление в сложных системах. — Вып.5. — Томск: Изд-во Том. ун-та, 2003. — 238с. С.57−66.

6. Колоусов Д. В., Назаров A.A. Исследование двумерного выходящего потока сети связи случайного доступа с конечным числом станций// Вестник ТГУ 2003. — № 280. — С.217−221.

7. Колоусов Д. В., Назаров A.A. Оценки параметров сети случайного доступа с конечным числом станций по наблюдениям за двумерным выходящим потоком// Материалы международной научной конференции «Современные математические методы анализа и оптимизации телекоммуникационных сетей». — Минск: БГУ, 2003. — С.139−143.

Апробация работы. Основные положения диссертации и отдельные ее результаты докладывались и обсуждались:

1. на Всероссийской конференции «Новые технологии и комплексные решения: наука, образование и производство», (г. Анжеро-Судженск, 2001 г.);

2. на IV Всероссийской конференции «Новые информационные технологии в исследовании сложных стуктур» (г. Томск, 2002 г.);

3. на Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» (г. Анжеро-Судженск, 2002 г.);

4. на международной научной конференции «Современные математические методы анализа и оптимизации телекоммуникационных сетей», (г. Минск, 2003 г.);

5. на научных семинарах кафедры теории вероятностей и математической статистики факультета прикладной ¿-математики и кибернетики Томского государственного университета 2001;2004гг.

Обзор литературы. Моделирование является одним из основных методов научного познания, при котором исследуемый объект заменяется другим объектом, называемым моделью, которая, в свою очередь представляет собой совокупность связей, определяющих процесс изменения состояний системы в зависимости от ее параметров, начальных условий и времени. Методы математического моделирования удобно использовать для изучения тенденций поведения системы при определенных условиях [3, 7, 18, 37], они позволяют эффективно исследовать достаточно сложные реальные системы, такие, как сети связи, управляемые протоколами случайного множественного доступа [11]. Такой подход реализован в работах [61, 62] для исследования компьютерных оптоволоконных сетей связи, реализованных на топологии двойной шины с протоколом распределенной очереди (DQDB — distributed queue dual bus — распределенная очередь к двойной шине), в рабспах [63, 66, 101,102] для исследования сетей случайного доступа с динамическими протоколами. Аналогично определены математические модели и проведено их исследование в работах [42, 45, 58, 51, 120], где рассмотрены сети, управляемые адаптивными протоколами и в работах [56, 73, 74, 75], где рассмотрены /¿—настойчивые протоколы. В этих работах определены математические модели рассматриваемых сетей случайного доступа в виде однолинейных марковских либо немарковских систем массового обслуживания [29] с повторными требованиями, к исследованию которых применяются различные варианты метода асимптотического анализа [52].

Также математическое моделирование используется при оптимизации и проектировании сетей передачи данных [32], позволяет получа! ь количественные оценки для сетей, находящихся в стадии проектирования [100], с его помощью разрабатываются модели [8, 59], воссоздающие информационные процессы, протекающие в сетях.

Одной из проблем, возникающих в сетях связи, является потеря данных вследствие нестабильного функционирования сети. Исследованию проблемы нестабильного функционирования сети связи посвящены работы [40, 48, 93, 98]. Динамические [64, 65], адаптивные [43, 44] и h-настойчивые [57, 68, 72] протоколы позволяют стабилизировать функционирование сети связи.

Для описания процессов, протекающих в сетях связи, обычно используются модели теории массового обслуживания в виде систем массового обслуживания, исследованию которых посвящено достаточно большое количество научных трудов [33, 50, 83, 84, 87, 88, 115]. Аппарат теории массового обслуживания дает исследователям возможность строить адекватные модели сетей связи и проводить аналитические исследования их функционирования [60, 94], для чего используются различные методы исследований [2, 12, 22, 52, 124].

В работах Ивановой О. В. [27], Юревич Н. М. [67, 69, 70], Одышева Ю. Д. [76, 77, 78], Цыбакова Б. С. [99] исследуются вероятностно-временные характеристики сетей связи с протоколом случайного множественного доступа Алоха, рассматривается возникающий в подобных сетях эффект бистабилыюсти [54], предлагаются пути стабилизации состояний сети [55]. Свойство бистабильности возникает в так называемых дважды стохастических потоках [13, 20] или случайных потоках однородных событий, управляемых стохастическими процессами. Такие потоки в диссертации названы бистабильными.

Знание распределения вероятностей состояний исследуемой сети, ее вероятностно-временных характеристик, дает возможность прогнозировать и контролировать процессы, протекающие в сетях [6, 9, 30]. Так, в работах Фалина Г. И. [108, 109, 110, 111, 112], Степанова С. Н. [85, 121, 122, 123], Клименок В. И. [116], Назарова А. А. [53, 63], Хомичкова И. И. [98, 114] проводится анализ систем массового обслуживания с повторными вызовами, которые служат адекватными моделями одноканальных сетей связи с протоколами случайного множественного доступа. Также широко известными системами массового обслуживания являются системы с потерями, с ожиданием, а также комбинированный класс — системы с ограниченным числом мест для ожидания [34, 89, 91].

Примерами протоколов случайного множественного доступа являются ALOHA [103], CSMA/CD [118], CSMA/CD© [36, 105, 117] и TCP [1, 21, 79, 90], входящий в стек протоколов TCP/IP.

За время, прошедшее с появления первых локальных сетей, было разработано множество самых разных сетевых технологий, однако заметное распостранение получили всего несколько из них. Прежде всего, это связано с поддержкой технологий известными фирмами и с высоким уровнем стандартизации принципов их организации. Наибольшее распостранение среди стандартных сетей получила сеть Ethernet. Сеть Ethernet стала международным стандартом (IEEE 802.3) и она является наиболее популярной в мире [97]. Стандарт определяет множественный доступ к моноканалу типа «шина» с обнаружением конфликтов и контролем передачи, то есть с методом доступа CSMA/CD [95, 96].

Также, большое внимание уделяется протоколу DQDB, принятому в качестве стандарта IEEE 802.6 для городских сетей связи [82, 119]. В соответствии с IEEE 802.6 стандарт DQDB может быть использован для построения частных, базирующихся на волоконно-оптических носителях сетей MAN.

В современных телекоммуникационных сетях потоки часто имеют существенно не пуассоновский характер. Они могут быть коррелироваными и обладать «взрывным» трафиком, при котором интенсивность поступления вызовов может существенно колебаться в течении суток, а также существует вероятность поступления группы вызовов сколь угодно большого размера. Хорошие модели таких потоков — марковские потоки с групповыми поступлениями, или ВМАР — потоки (Batch Markovian Arrival Process) [35, 107]. Более подробное описание ВМАР — потока, его свойств и известных ранее случаев в [24].

В последние годы беспроводные сети передачи данных становятся одным из основных направлений развития сетевой индустрии. Успех беспроводных сетей во многом связан с разработкой сетевых программных продуктов, обеспечивающих множественный доступ к беспроводной среде, и наличием соответствующих стандартов. Один из таких международных стандартовэто протокол IEEE 802.11 [14,126], обеспечивающий детальные спецификации уровней MAC и PHY для беспроводных локальных сетей. В протоколе IEEE 802.11 фундаментальным механизмом доступа к беспроводной среде является Функция Распределенной Координации (DCF), реализующая метод CSMA/CD.

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

Таким образом, для СМО, функционирующей в условиях частичной априорной неопределенности, важной задачей является оценка тех или иных параметров входящих потоков заявок. В научной литературе данные потоки исследуются с двух точек зрения: построения оценок состояний и параметров ненаблюдаемой интенсивности потока [10, 15, 19, 31, 38, 71, 86, 92, 125] и анализа процессов функционирования СМО с такого рода входящими потоками [23, 25, 39, 49, 80, 81, 106, 113]. Анализ СМО можег производиться, в частности, по наблюдениям за выходящими потоками систем массового обслуживания, так как, но наблюдениям за такими потоками удается диагностировать состояние сети, а также оценивать ее некоторые параметры, такие как загрузка сети, ее производительность или пропускная способность и т. д. Можно отметить несколько работ, в которых проводится исследование выходящих потоков систем массового обслуживания. Это работы A.M. Александрова [4, 5], Е. В. Глуховой [16, 17], В. А. Ивницкого [28j, Р. В. Амбарцумяна [104] и некоторых других.

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

Заключение

.

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

В Главе 1 исследована математическая модель выходящих потоков успешно обслуженных заявок и заявок, выходящих из ИПВ, сети связи с динамическим протоколом случайного множественного доступа с оповещением о конфликте, в случае бесконечного числа станций. Длительность интервала оповещения о конфликте и время передачи сообщения распределены по экспоненциальному закону. Доказано, чю число успешно обслуженных заявок п (£) за время в асимптотике, при Т —У оо, подчиняется нормальному закону. Найдены в явном виде параметры распределения числа успешно обслуженных заявок, а также параметры распределения вероятностей состояний системы. Доказано, что процесс является диффузионным процессом арифметическо1 о броуновского движения. Показана применимость полученных результатов в вопросе получения оценки интенсивности входящего потока заявок, по наблюдениям за выходящим потоком успешно обслуженных заявок. Кроме того, доказано, что число заявок, вышедших из ИПВ з[Ь) с обращениями на повторное обслуживание за время ?, в асимптотике, при Т —> оо, подчиняется нормальному закону. Найдены в явном тт виде параметры распределения. Доказано, что процесс является диффузионным процессом арифметического броуновского движения.

В Главе 2 исследованы математические модели выходящего потока успешно обслуженных заявок, выходящего потока сигналов оповещения о конфликте, двумерного выходящего потока успешно обслуженных заявок и сигналов оповещения о конфликте бистабильной сети связи случайного множественного доступа с конечным числом абонентских станций и оповещением о конфликте. Исследованы вероятностно-временные характеристики данной сети связи. Длительность интервала оповещения о конфликте и время передачи сообщения распределены по экспоненциальному закону. Доказано, что число успешно обслуженных заявок п (£) за время в асимптотике, при Т —> оо, подчиняется нормальному закону. Найдены в явном виде параметры распределения числа успешно обслуженных заявок, а также распределения вероятностей состояний системы, в асимптотике при.

N —у оо. Доказано, что процесс является диффузионным процессом арифметического броуновского движения. Доказано, что число сигналов оповещения о конфликте за время ?, в асимптотике, при Т —>¦ оо, подчиняется нормальному закону. Найдены в явном виде параметры распределения, в асимптотике при N -> оо. Доказано, что процесс является диффузионным процессом арифметического броуновского движения. Кроме того, найдена матрица ковариаций процессов п (£), з (£), в асимптотике, при N —> оо. Показана применимость полученных результатов в вопросе получения оценки интенсивности входящего, но I ока заявок, оценки асимптотического среднего нормированного числа заявок, находящихся в ИПВ, по наблюдениям за выходящими потоками успешно обслуженных заявок и сигналов оповещения о конфликте. Теоретически показана возможность существования в таких сетях явления бистабильности, определяемого наличием двух точек стабилизации, в окрестности которых флуктуируют значения фазовых координат сети. Найдено в явном виде время пребывания в окрестности каждого из стабильных состояний бистабильной сети связи. Как видно из данных формул, время пребывания в окрестности стабильного состояния стремится к оо, при N —> оо.

В Главе 3 рассмотрена оценка интенсивности входящего потока, А по наблюдениям за выходящим потоком успешно обслуженных заявок в сетях связи, управляемых динамическим протоколом случайною множественного доступа в случае бесконечного числа станций. Доказана несмещенность и эффективность данной оценки. Также рассмотрены оценки 6-асимптотического среднего нормированного числа заявок, находящихся в источнике повторных вызовов и интенсивности — обращения каждой из N абонентских станций к обслуживающему прибору по наблюдениям за двумерным выходящим потоком успешно обслуженных заявок и сигналов оповещения о конфликте в бистабильных сетях связи случайного множественного доступа с конечным числом абонентских станций. Доказана несмещенность и эффективность данных оценок.

В Главе 4 исследована математическая модель выходящего потока заявок из ИПВ, сети связи с протоколом случайного множественного доступа с оповещением о конфликте, в случае бесконечного числа станций. Длительность интервала оповещения о конфликте и время передачи сообщения распределены, но экспоненциальному закону. Доказано, что число успешно обслуженных заявок за время ?, в асимптотике, при Т —> оо, подчиняется нормальному закону. Найдены в явном виде параметры распределения в асимптотике, при <т 0. Кроме того, реализована программа имитационного моделирования рассматриваемой сети связи, с помощью которой удалось показать непротиворечивость полученых данных гипотезе об инвариантности распределения состояний канала и интенсивности выходящего потока заявок из ИПВ к виду распределения длительности задержки заявки перед повторным обращением из ИПВ на обслуживающий прибор для математической модели рассматриваемой сети случайного доступа.

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