Содержание к диссертации
Список использованных сокращений , 7
Введение , 8
1 Модель системы и алгоритмы СМД для централизованных сетей 15
-
Вводные замечания по структуре раздела 15
-
Особенности МАС-уровня централизованных сетей 15
-
Общие сведения 15
-
Структура МАС-уровня 16
-
Соединения и сервисные потоки 17
-
Общая структура кадров ШЕЕ 802.16 18
-
Пакеты МАС-уровня 19
-
Принцип предоставления канальных ресурсов 20
-
Механизмы подтверждение приема и быстрой обратной связи 21
1.3 Модель системы „22
1.3.1 Модель канала 22
-
Восходящий и нисходящий канал. Структура кадра 22
-
Модель шумов 25
1.3.2 Модель входного потока 26
-
Общие замечания 26
-
Дискретный пачечный марковский входной процесс (D-BMAP) 27
-
Пуассоновский входной процесс с дискретным временем 29
-
Пуассоновский входной процесс с дискретным временем, модулируемый цепью Маркова 30
-
Особенности D-BMAP как входного процесса 31
-
Модели абонентов 32
1.4 Алгоритмы случайного множественного доступа 34
-
Определение алгоритма СМД. Задержка и скорость 34
-
Алгоритмы ALOHA и Slotted ALOHA 36
-
Алгоритм Binary Exponential Backoff. 37
L4.4 Алгоритмы СМД с очередью 39
1.4.5 Древовидные АРК 41
1.5 Исследование алгоритма Binary Exponential Backoff 43
-
Допущения имитационного моделирования 43
-
Канал со всплесками интенсивности входного потока 44
-
Канал с ложными конфликтами 46
1.6 Выводы по разделу 47
2 Анализ базового алгоритма СМД с очередью 48
-
Вводные замечания 48
-
Описание алгоритма FS-ALOHA 48
-
Вычисление скорости алгоритма FS-ALOHA в канале с ложными конфликтами , 54
-
Допущения аналитической модели 54
-
Метод вычисления скорости 54
-
Влияние шумов на скорость при разных параметрах алгоритма 59
-
Вычисление скорости при параметрах алгоритма 5=1 и /V=2 62
2.4 Вычисление распределения вероятностей для задержки запроса в алгоритме
FS-ALOHA 70
-
Допущения аналитической модели 70
-
Марковская цепь. Укрупнение состояний , 70
-
Марковская цепь с укрупненными состояниями 75
-
Метод вычисления распределения вероятностей для задержки запроса...76
2.4.5 Сравнение результатов аналитического моделирования и имитационного
моделирования 78
-
Сравнение алгоритмов FS-ALOHA, Slotted ALOHA и ВЕВ 80
-
Выводы по разделу 86
3 Организация передачи запросов для большого размера конкурентного
интервала. , 87
-
Вводные замечания 87
-
Анализ алгоритма Multi FS-ALOHA , 87
-
Описание алгоритма Multi FS-ALOHA 87
-
Вычисление скорости алгоритма Multi FS-ALOHA в канале с ложными конфликтами 92
-
Метод вычисления скорости 92
-
Метод определения оптимальных параметров алгоритма для максимизации скорости 96
-
Результаты вычисления скорости 99
3.2.3 Оценка характеристик задержки запроса 102
3.3 Анализ древовидных алгоритмов СМД 105
-
Описание древовидных алгоритмов СМД 105
-
Вычисление скорости древовидных алгоритмов 107
-
Метод вычисления скорости 107
-
Метод определения оптимальных параметров алгоритма для максимизации скорости 108
3.4 Оценка характеристик задержки запроса 109
-
Сравнение алгоритмов СМД с очередью относительно скорости и распределения вероятностей для задержки 111
-
Выводы по разделу 114
4 Класс алгоритмов СМД с очередью... .115
-
Вводные замечания 1.15
-
Описание класса алгоритмов СМД с очередью 115
-
Анализ алгоритмов СМД с очередью при пуассоновском входном потоке ..118
-
Описание подкласса алгоритмов СМД с очередью 118
-
Метод вычисления скорости для заданных параметров алгоритма 119
-
Метод определения оптимальных параметров алгоритма S и Л' для максимизации скорости при заданном размере конкурентного интервала 123
-
Метод вычисления скорости при входном процессе D-BMAP 126
-
Результаты вычисления скорости при входном потоке со 127
всплесками интенсивности 127
4.6 Результаты для средней задержки при входном потоке со 129
всплесками интенсивности 129
4.7 Выводы по разделу 131
Заключение. .....133
Список использованных источников 135
Приложение А. Вычисление вероятностей, используемых при анализе
алгоритма FS-ALOHA 143
Приложение Б. Вычисление среднего количества кадров, необходимых для
обслуживания одного КП с заданным количеством запросов в алгоритме FS-
ALOHA , 149
Приложение В. Вычисление среднего количества кадров, необходимых для
обслуживания одного КП с заданным количеством запросов в алгоритме
MULTIFS-ALOHA 152
Приложение Г. Вычисление среднего количества кадров, необходимых для
обслуживания одного КП с заданным количеством запросов в древовидном
модифицированном алгоритме со стеком бесконечной глубины 154
Список использованных сокращений
AMPS -Advanced Mobile Phone System;
AUQ - automatic repeat request;
BEB - Binary Exponential Backoff;
CRC - cyclical redundancy check;
D-BMAP - discrete time batch Markovian arrival process;
DVB - Digital Video Broadcasting;
FIFO - First Input First Output;
GSM - Global System for Mobile Communications;
IEEE - Institute of Electrical and Electronics Engineers;
LAN - local area network;
MAC - medium access control;
MAN - metropolitan area network;
NAMPS - Narrow-band Advanced Mobile Phone System;
OFDM - Orthogonal Frequency Division Multiplexing;
OFDMA - Orthogonal Frequency Division Multiplexing Access;
OSI - Open System Interconnection;
RMA - random multiple access;
SC - Single Carrier;
APK - алгоритм разрешения конфликта;
AC - абонентская станция;
ЦС - центральная станция;
КП - конфликтное подмножество;
СМД- случайный множественный доступ;
СМО - система массового обслуживания.
Введение к работе
Актуальность темы. Активное развитие сетей передачи данных обуславливает необходимость исследования распространенного метода, используемого при передаче в этих сетях - множественного доступа абонентов к общему каналу связи. Множественный доступ предполагает разделение ресурсов канала между абонентами. Такое разделение каналов может быть частотным, временным или кодовым. Множественный доступ применяется и в проводных и в беспроводных сетях. Различают бесконфликтные и конфликтные методы доступа. Бесконфликтные методы множественного доступа используют в сотовых сетях стандартов AMPS, NAMPS, GSM (в режиме передачи речи) и других. Среди конфликтных методов доступа широкое распространение получил стандарт для локальных проводных сетей IEEE 802.3 (Ethernet) и стандарт для локальных беспроводных сетей - IEEE 802.11. В настоящее время идет активное внедрение стандарта для беспроводных MAN-сетей - IEEE 802.16. Данный стандарт, как и стандарт для проводных сетей IEEE 802.14, характеризуется наличием центральной станции. Особенностью стандартов IEEE 802.16 и IEEE 802.14 сетей с центральной станцией (централизованные сети) является использование конкурентного интервала в процессе передачи. В конкурентном интервале абоненты передают запросы к центральной станции на предоставление канальных ресурсов. Абонент передает запрос случайным образом. Если передачи запросов от разных абонентов накладываются друг на друга, то возникает конфликт. В этом случае абоненты делают повторную передачу в соответствии с определенными правилами. И так далее. Ясно, что правила управления передачей в конкурентном интервале могут оказывать большое влияние на задержку передачи запроса. А это, в конечном счете, повлияет на время, которое затратит абонент на передачу данных. Диссертационная работа посвящена исследованию алгоритмов управления передачей в конкурентном интервале, которые принято называть алгоритмами случайного множественного доступа. Основная идея метода случайного множественного доступа предложена в начале 70-х годов прошлого века. Максимальное число работ в области СМД отно- сится к середине 80-х годов прошлого века. В последующие пятнадцать лет интерес к исследованиям в этом направлении постепенно уменьшался. Тем не менее, появление беспроводных сетей привело к тому, что в последние годы снова наблюдается тенденция к увеличению числа работ, посвященных СМД,
Первым алгоритмом случайного множественного доступа был алгоритм ALOHA. В стандартах IEEE 802.16 и IEEE 802.14 в качестве алгоритма СМД применяется модификация ALOHA - алгоритм Binary Exponential Backoff (ВЕВ). Алгоритм FS-ALOHA, предложенный специально для централизованных сетей, во многом превосходит алгоритм ВЕВ в характеристиках задержки передачи и в тоже время его реализация не намного сложнее, чем реализация ВБВ. В FS-ALOHA. все множество запросов, попавших в конфликт, разбивается на подмножества, образующие очередь. Запросы из одного подмножества обслуживаются отдельно от другого подмножества. Алгоритм FS-ALOHA представляет собой простейший способ управления передачей запросов с использованием очереди. Алгоритм является базовым по отношению к другим алгоритмам СМД с очередью, которые исследуются в данной работе.
При увеличении размера конкурентного интервала эффективность алгоритма FS-ALOHA относительно задержки резко снижается. В настоящей диссертации представлена модификация FS-ALOHA - алгоритм Multi FS-ALOHA, решающий проблему падения эффективности. Предлагается целый класс алгоритмов с очередью для централизованных сетей. В данном классе может быть выбран алгоритм, наиболее подходящий для конкретного канала с определенными характеристиками. В предложенном классе есть алгоритмы, дающие существенный выигрыш по средней задержке в сравнении с алгоритмом ВЕВ при высокой интенсивности входного луассоновского потока. При низкой интенсивности пуассо-новского потока нет большого различия в величинах средней задержки запроса для разных алгоритмов СМД. Для сетей передачи данных актуально изучение их поведения при входном потоке, имеющем всплески интенсивности. Если поток с низкой интенсивностью имеет всплески интенсивности, то алгоритмы из нашего класса, речь о которых шла выше, также более эффективны относительно средней задержки, чем ВЕВ.
Основной целью работы является разработка и анализ алгоритмов управления передачей запросов в конкурентном интервале, использующих случайный множественный доступ и обеспечивающих оперативную доставку запросов па центральную станцию. Для достижения поставленной цели следует решить следующие задачи.
1). Проанализировать функционирование известного алгоритма СМД с очередью для централизованных сетей.
2). Предложить алгоритмы СМД, обеспечивающие меньшую задержку при доставке запроса, нем ранее известные алгоритмы.
3). Проанализировать предложенные алгоритмы для различных видов входного потока.
Методы исследования. Для решения поставленных задач использованы методы теории вероятностей, теории случайных процессов, теории цепей Маркова, методы теории массового обслуживания и имитационное моделирование.
Научная новизна диссертационной работы заключается в следующем.
1). Разработан метод расчета скорости алгоритма FS-ALOHA для канала с шумом, приводящим к появлению ложных конфликтов.
2). Вычислено критическое значение вероятности ложного конфликта, при котором скорость для оптимальных относительно скорости параметров алгоритма FS-ALOHA равна нулю.
3). Разработан метод расчета распределения вероятностей для задержки передачи запроса в алгоритме FS-ALOHA в канале с шумом,
4). Предложен класс алгоритмов СМД с очередью для централизованных сетей.
5). Разработан метод вычисления скорости алгоритма для подкласса алгоритмов СМД из предложенного класса. Разработан метод определения параметров алгоритма из данного подкласса, при которых его скорость максимальна. Раз- работай метод вычисления скорости при входном потоке со всплесками интенсивности для алгоритмов из подкласса.
Практическая ценность и реализация результатов.
1). Предложена модификация алгоритма FS-ALOHA - алгоритм Multi FS-ALOHA. Модификация решила проблему уменьшения скорости в алгоритме FS-ALOHA при увеличении размера конкурентного интервала.
2). Предложены древовидные алгоритмы СМД для централизованных сетей. Данные алгоритмы обладают большей скоростью в сравнении с Multi FS-ALOHA, но при этом имеют и большею вычислительную сложность.
3). Получены численные значения характеристик алгоритма FS-ALOFIA в канале с шумом. Численные характеристики рассчитаны для предложенных алгоритмов СМД при различных значениях их параметров.
4). Произведено сравнение алгоритма ВЕВ, используемого в стандарте ШЕЕ 802.16, с одним из древовидных алгоритмов СМД для централизованных сетей.
Результаты диссертационной работы получены при выполнении госбюджетной научно-исследовательской работы (РК 01200501975), опубликованы и представлены в отчетах НИР. Эти результаты использованы в учебном процессе кафедры информационных систем ГУАП и кафедры АСОИУ ЛЭТИ. Использование результатов диссертационной работы подтверждается соответствующими актами.
Апробация работы. Основные результаты работы докладывались на пятой научной сессии аспирантов ГУАП (Санкт-Петербург, 12-18 апреля 2002г.), на шестой научной сессии аспирантов ГУАП (Санкт-Петербург, 14 - 18 апреля 2003г.), на седьмой научной сессии аспирантов ГУАП (Санкт-Петербург, 12-16 апреля 2004г.), на конференции «Информационные технологии в науке, образовании, искусстве» (Санкт-Петербург, 29-31 марта 2005 г.), на восьмой науч ной сессии ГУАП (Санкт-Петербург, 11-15 апреля 2005г.), на политехническом симпозиуме «Молодые ученые - промышленности Северо-Западного региона» (декабрь 2005 г.), на научной сессия ГУАП, посвященная всемирному Дню авиации и космонавтики и 65-летию ГУАП (Санкт-Петербург, 10 - 14 апреля 2006г.), на меж- дународной научной конференции IEEE "ISCE 2006" (Санкт-Петербург, 28 июня - I июля 2006г.). Зарегистрированы программные разработки в отраслевом фонде алгоритмов и программ: регистрационный номер Гос. ФАП 50200501138, 2005 г.; регистрационный номер Гос. ФАП 50200501139, 2005 г.; регистрационный номер Гос. ФАП 50200501140,2005 г.
Публикации. Материалы, отражающие основное содержание и результаты диссертационной работы, опубликованы в 13 печатных работах.
Основные положения, выносимые на защиту: метод расчета скорости и метод расчета распределения вероятностей для задержки запроса в алгоритме FS-ALOHA в канале с шумом; алгоритм управления передачей запроса в конкурентном интервале централизованных сетей - Multi FS-ALOHA; класс алгоритмов СМД для централизованных сетей. Метод расчета скорости и метод выбора оптимальных параметров для подкласса алгоритмов СМД,
Объем и структура работы. Диссертационная работа состоит из введения, 4 разделов, заключения, списка использованных источников и 4 приложений. Работа содержит всего 154 страницы, в том числе 151 страница машинописного текста, включая 40 рисунков, и 6 рисунков на 3 страницах. В списке используемой литературы 79 наименований.
В первом разделе описаны особенности подуровня управления доступом к среде в централизованных сетях передачи данных на примере стандарта IEEE 802.16. Приведена модель канала и модель входного потока. Определены основные характеристики алгоритмов СМД. Выполнен обзор используемых для централ изованных сетей алгоритмов СМД, а также древовидных АРК. Получены оценки характеристик алгоритма ВЕВ. Сделан вывод о возможных путях улучшения характеристик алгоритмов СМД в централизованных сетях.
Второй раздел посвящен исследованию алгоритма FS-ALOHA в канале с шумом. Приведено подробное описание алгоритма FS-ALOHA и результаты его исследования. Разработан метод расчета скорости алгоритма. Определены параметры алгоритма FS-ALOHA, при которых его скорость максимальна. Получен метод точного вычисления критического значения вероятности ложного конфликта, при котором скорость алгоритма равна нулю. Разработан метод расчета распределения вероятностей для задержки. Выполнен сравнительный анализ алгоритмов FS-ALOHA, Slotted ALOHA и ВЕВ.
В третьем разделе рассматривается организация передачи запросов для большого размера конкурентного интервала. В разделе описана модификация алгоритма FS-ALOHA - алгоритм Multi FS-ALOHA, исследуемый в канале с шумом. Разработан метод вычисления скорости алгоритма и метод определения параметров, которые максимизируют его скорость. Выполнен анализ скорости для разных видов ложных конфликтов. Получены оценки характеристик задержки при различных параметрах алгоритма. Введены в рассмотрение древовидные алгоритмы для централизованных сетей. Разработан метод вычисления скорости и метод определения оптимальных параметров алгоритмов, максимизирующих их скорость. Даны оценки характеристик задержки при различных параметрах древовидного модифицированного алгоритма со стеком бесконечной глубины. Сделан сравнительный анализ исследуемых алгоритмов СМД относительно скорости и средней задержки передачи запроса.
В четвертом разделе обобщены рассмотренные ранее алгоритмы СМД с очередью для централизованных сетей (определен класс алгоритмов СМД), Для класса алгоритмов разработаны следующие методы: вычисления скорости, определения оптимальных относительно скорости параметров алгоритма, вычисления скорости при входном потоке со всплесками интенсивности. Выполнен сравнительный анализ древовидного модифицированного алгоритма со стеком бесконечной глубины и алгоритма ВЕВ в предположении входного потока со всплесками интенсивности.
В заключении перечислены основные результаты, полученные в диссертационной работе.
В приложении А приведены аналитические выражения для вычисления вероятностей, используемых при анализе алгоритма FS-ALOHA.
В приложении Б - аналитические выражения для вычисления среднего количества кадров, необходимых для обслуживания одного КП с заданным числом запросов в алгоритме FS-ALOHA.
В приложении В - аналитические выражения для вычисления среднего количества кадров, необходимых для обслуживания одного КП с заданным числом запросов в алгоритме Multi FS-ALOHA.
В приложении Г - аналитические выражения для вычисления среднего количества кадров, необходимых для обслуживания одного КП с заданным числом запросов в древовидном модифицированном алгоритме со стеком бесконечной глубины.
