Содержание к диссертации
Введение
1. Модели систем со случайным множественным доступом абонентов в общий канал связи 18
1.1 Вводные замечания и классификация систем множественного доступа 18
1.2 Развитие методов СМД и актуальные задачи теории и практики применения методов СМД 23
1.3 Классическая модель СМД
1.3.1 Принцип построения классической модели 27
1.3.2 Система связи 27
1.3.3 Канал связи 30
1.3.4 Обратная связь 31
1.3.5 Абонент 33
1.3.6 Классические модели СМД
1.4 Понятие и характеристики алгоритма СМД, пропускная способность системы СМД 36
1.5 Описание алгоритмов для классической модели
1.5.1 Общие замечания по классификации алгоритмов СМД 40
1.5.2 Алгоритмы АЛОХА и ДЭО 42
1.5.3 Базовый и модифицированный древовидные алгоритмы 45
1.6 Разнообразие моделей систем со случайным множественным до ступом в канал 49
1.6.1 Классическая модель системы СМД как основа для построения моделей и исследования реальных систем 49
1.6.2 Изменение модели относительно абонента для учета особенностей реальных потоков 50
1.6.3 Уточнение понятия алгоритма СМД
1.6.4 Изменение модели относительно канала связи для учета шумов в канале связи 58
1.6.5 Учет различных видов обратной связи в модели
1.7 Базовый и модифицированный алгоритмы с компенсацией конфликтных сигналов 64
1.8 Заключительные замечания 70
2. Методы анализа характеристик древовидных алгоритмов разрешения конфликтов 72
2.1 Роль древовидных алгоритмов разрешения конфликта в развитии теории случайного множественного доступа 72
2.2 Вычисление оценок скорости для базового алгоритма разрешения конфликта 74
2.3 Использование свойств базового алгоритма разрешения конфликта для анализа характеристик блокированных алгоритмов
и основное свойство дерева разрешения конфликтов 79
2.4 Вычисление скорости алгоритма для канала с шумом 84
2.5 Вычисление скорости для алгоритмов с компенсацией конфликтных сигналов 2.5.1 Вычисление скорости для базового алгоритма с компенсацией конфликтных сигналов 90
2.5.2 Вычисление скорости для модифицированного алгоритма с компенсацией конфликтных сигналов
2.6 Неблокированные древовидные алгоритмы и анализ их характеристик 100
2.7 Выводы по разделу 107
3. Случайный множественный доступ при двоичной обратной связи успех неуспех 109
3.1 Обеспечение устойчивой работы системы при двоичной обратной связи успех-неуспех - одна из открытых проблем теории случайного множественного доступа 109
3.2 Модель системы 112
3.3 Неблокированный стек-алгоритм в системе с обратной связью типа успех-неуспех 114
3.3.1 Описание работы алгоритма 114
3.3.2 Вычисление скорости алгоритма и средней виртуальной задержки 115
3.4 Алгоритмы СМД с отложенными интервалами 119
3.4.1 Частный случай алгоритма 119
3.4.2 Класс алгоритмов доступа с отложенными интервалами 122
3.5 Пропускная способность алгоритма 124
3.5.1 Уточнение понятия скорость и пропускная способность 124
3.5.2 Изменение масштаба времени и марковская цепь, описывающая функционирование алгоритма 125
3.5.3 Вероятности событий в сеансе 127
3.5.4 Вложенная цепь Маркова 128
3.5.5 Просмотр непустого множества 129
3.5.6 Средняя длительность сеанса 130
3.5.7 Условия положительной возвратности и эргодичности
3.6 Вычисление значения пропускной способности алгоритма и обобщение результатов на весь класс алгоритмов с отложенными интервалами 135
3.7 Расширение класса алгоритмов 138
3.8 Выводы по разделу 140
4. Использование адресов абонентов при разрешении конфликтов 145
4.1 Использование адресов абонентов при разрешении конфликтов как альтернатива чисто случайным механизмам разрешения конфликтов 145
4.2 Модель системы и уточнение понятия скорости
4.2.1 Особенности классической модели для случая конечного числа абонентов 147
4.2.2 Дисциплины работы абонентов с очередью 148
4.2.3 Модель с двухпакетной очередью 151
4.2.4 Понятие скорости алгоритма доступа для системы с конечным числом абонентов 153
4.3 Методы анализа систем СМД при использовании адресов абонентов для разрешения конфликтов 154
4.3.1 Алгоритмы СМД для канала без шума 154
4.3.2 Случайные процессы, описывающие поведение системы 157
4.3.3 Определение скорости алгоритмов 161
4.3.4 Метод расчета средней задержки 162
4.3.5 Алгоритм расчета средней задержки и результаты расчета 165
4.4 Алгоритмы, использующие адреса абонентов для разрешения конфликтов в канале с шумом 167
4.4.1 Алгоритмы доступа для канала с шумом 167
4.4.2 Расчет скорости для канала с ложными конфликтами 171
4.4.3 Расчет средней задержки для канала с шумом 172
4.4.4 Средняя длина сеанса 173
4.4.5 Распределение длины сеанса 177
4 4.6 Среднее время выхода 180
4.4.7 Результаты расчета средней задержки 181
4.5 Выводы по разделу 189
5. Организация случайного доступа в централизованных сетях передачи данных , 191
5.1 Особенности организации множественного доступа в централизованных сетях передачи данных 191
5.2 Расширение классической модели на случай централизованной системы 195
5.3 Обобщение понятия и характеристик алгоритма СМД, пропускная способность централизованной системы СМД с резервированием 197
5.4 Оценка пропускной способности централизованной сети 200
5.5 Общее описание централизованных телекоммуникационных протоколов 205
5.5.1 Вводные замечания 205
5.5.2 Общая структура и эволюционное развитие протокола 205
5.5.3 Основные особенности протокола 208
5.5.4 Известные результаты относительно алгоритма резервирования 211
5.5.5 Способы предоставления канальных ресурсов 213
5.6 Анализ и предложения по улучшению централизованных теле
коммуникационных протоколов 215
5.6.1 Анализ существующего протокола 215
5.6.2 Предложения по улучшению протокола 222
5.7 Использование СМД для повышения эффективности передачи
видеоинформации в централизованных сетях передачи данных 226
5.7.1 Необходимость учета специфики видеоинформации при передаче в централизованных сетях 226
5.7.2 Модель системы передачи видеоинформации в нисходящем канале централизованной сети передачи данных 228
5.7.3 Постановка задачи выбора параметров кодирования видеоисточника и канала 229
5.8 Выводы по разделу 234
Заключение 236
Список использованных источников
- Принцип построения классической модели
- Вычисление оценок скорости для базового алгоритма разрешения конфликта
- Вычисление значения пропускной способности алгоритма и обобщение результатов на весь класс алгоритмов с отложенными интервалами
- Алгоритмы, использующие адреса абонентов для разрешения конфликтов в канале с шумом
Введение к работе
Актуальность проблемы. В последние десятилетия отмечается тенденция активного роста числа систем передачи информации, построенных на основе каналов множественного доступа, таких как радиоканалы и спутниковые каналы связи. Среди методов управления доступом большого числа абонентов к общему каналу особое место занимают методы случайного множественного доступа с разрешением конфликтов. При достаточно низкой интенсивности входного потока сообщений к абонентам конфликты возникают редко, и задержка сообщения оказывается существенно меньше, чем при использовании других методов множественного доступа.
Первой системой, в которой был использован случайный множественный доступ, являлась система «АЛ ОХ А», созданная в конце шестидесятых годов двадцатого века для связи между вычислительными машинами Гавайского университета. Алгоритм разрешения конфликта, используемый в данной системе, был предложен и исследован Н.Абрамсоном, а затем улучшен Ф.Тобаги. Этот алгоритм прост в реализации, при относительно небольшом числе абонентов обеспечивает низкую задержку, и по этим причинам до сих пор широко используется в современных системах. Однако в работах Д.Алдоуса и ряда других авторов было доказано, что даже при постоянной суммарной интенсивности входного потока увеличение числа абонентов приводит к катастрофическому увеличению задержки. Путь решения данной проблемы был предложен Б.С.Цыбаковым, В.А.Михайловым и Дж.Капетанакисом. Этими авторами была впервые введена модель системы случайного множественного доступа бесконечного числа абонентов к общему каналу передачи данных при пуассоновском входном потоке сообщений. Применительно к этой модели были предложены так называемые древовидные алгоритмы разрешения конфликта и было доказано, что с помощью этих алгоритмов можно получить конечную среднюю задержку при некоторой ограниченной интенсивности входного потока. В теории случайного множественного доступа данная модель является классической и используется в научных трудах отечественных и зарубежных ученых, таких как Н.Д.Введенская, Г.С.Евсеев, Н.Б.Лиханов, Б.Гаек, Дж.Месси, Р.Галлагер и др.
В конце последнего десятилетия прошлого века случайный множественный доступ получил новый импульс в развитии в связи с его применением в беспроводных сетях. В первую очередь это относится к сетям стандарта IEEE 802.11 (Wi-Fi). Анализу соответствующего протокола множественного доступа посвящены работы Дж.Бианки, А.И.Ляхова, В.М.Вишневского и ряда других авторов. Случайный множественный доступ с разрешением конфликтов используется для резервирования общего канала в региональных беспроводных сетях, соответствующих стандартам IEEE 802.16 и 3GPP LTE. Имеются лишь единичные работы (Г.Гианнакис, К.Блондиа), в которых предлагаются методы, позволяющие повысить эффективность алгоритмов разреше-
ния конфликта, используемых в таких системах. В этих работах рассматривается весьма упрощенная модель системы.
Эффективность работы алгоритмов разрешения конфликта, используемых в современных системах передачи информации, существенно снижается с увеличением числа абонентов. Учитывая тенденцию к дальнейшему росту числа абонентов, можно ожидать, что в ближайшем будущем этот недостаток окажет негативное влияние на развитие систем передачи информации в целом. Алгоритмы, разработанные для классической модели, свободны от этого недостатка. Однако эти алгоритмы не могут быть непосредственно использованы в современных системах, так как в классической модели не отражены особенности таких систем (изменение интенсивности потока во времени, отсутствие достоверной информации о событиях в канале, наличие механизмов резервирования канала и т.п.). Таким образом, одной из основных проблем в теории и практике случайного множественного доступа в настоящее время является разработка новых алгоритмов разрешения конфликта, которые могут быть использованы как в существующих, так и в перспективных системах передачи информации с большим числом абонентов.
Цель диссертационной работы. Целью диссертационной работы является разработка и исследование алгоритмов случайного множественного доступа, имеющих существенное значение для повышения эффективности функционирования современных беспроводных систем передачи информации.
В соответствии с целью исследования были поставлены следующие основные задачи.
Создание методологической основы для исследования систем случайного множественного доступа.
Разработка общего метода исследования древовидных алгоритмов случайного множественного доступа.
Разработка новых алгоритмов случайного множественного доступа, учитывающих особенности современного приемо-передающего оборудования.
Обеспечение стабильной работы системы случайного множественного доступа для случая, когда наблюдения канала не позволяют различить отсутствие передачи в канале от конфликта.
Разработка алгоритмов случайного множественного доступа, использующих адреса абонентов для разрешения как подлинных, так и ложных конфликтов.
Построение модели централизованной системы случайного множественного доступа с резервированием, с учетом основных особенностей современных региональных сетей.
Построение оценок для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с резервированием.
Использование предложенных методов и алгоритмов для повышения эффективности функционирования централизованной системы случайного множественного доступа.
Методы исследования. При получении основных результатов работы использовались общие методы системного анализа, методы теории вероятностей, теории случайных процессов, в частности регенерирующих и марковских процессов, теории систем массового обслуживания, численные методы, а также методы имитационного моделирования.
Научная новизна диссертационной работы заключается в следующем.
Впервые классифицированы допущения, используемые при изучении систем случайного множественного доступа, и сформулирована методологическая основа для исследования существующих и новых систем.
Предложен новый метод анализа характеристик древовидных алгоритмов случайного множественного доступа, основанный на взаимосвязях между алгоритмами.
Разработаны новые алгоритмы случайного множественного доступа, использующие возможность приема нескольких сообщений одновременно.
Впервые предложен класс алгоритмов, обеспечивающий устойчивую работу системы случайного множественного доступа для случая, когда наблюдения канала не позволяют отличить конфликт от отсутствия передачи в канале.
Впервые разработаны алгоритмы случайного множественного доступа, использующие адреса абонентов для разрешения как подлинных, так и ложных конфликтов.
Предложена новая модель централизованной системы случайного множественного доступа с резервированием, отражающая основные особенности современных региональных сетей.
Впервые построены оценки для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с резервированием.
Предложены новые способы повышения эффективности функционирования централизованной системы случайного множественного доступа.
Практическая ценность работы. На основе результатов работы сформулирован ряд модификаций существующего протокола региональной беспроводной сети передачи информации, позволяющих существенно повысить уровень качества обслуживания абонентов. Результаты диссертационной работы могут быть использованы при проектировании систем передачи информации с большим числом абонентов, а также для разработки новых телекоммуникационных протоколов, в которых используются алгоритмы случайного множественного доступа.
Теоретические и практические результаты работы использованы в учебном процессе кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения. Результаты работы используются в разработках ЗАО «Интел А/О». Использование результатов подтверждено соответствующими актами.
Апробация работы. Основные результаты работы докладывались и обсуждались на:
Всесоюзных школах-семинарах по вычислительным сетям (1982г.-1990г.);
Симпозиумах по проблемам избыточности в информационных системах (1983г., 1986г., 1989г., 2007г., 2009г.);
Советско-шведских симпозиумах по теории информации (1991г., 1993г.);
Международных симпозиумах по теории информации (1994г., 1995г.);
Международном семинаре «On Multiple Access Communications» (Санкт-Петербург, Россия, 2008г.);
15-й Между нар одной конференции «On Analytical and Stochastic Modeling Techniques and Applications» (Никосия, Республика Кипр, 2008г.);
- 11-м Международном симпозиуме «On Wireless Personal
Multimedia Communications» (Финляндия, 2008г.);
- семинарах кафедры информационных систем и кафедры безопас
ности информационных систем Санкт-Петербургского государственно
го университета аэрокосмического приборостроения;
- семинарах Института проблем передачи информации РАН
(Москва).
Публикации. По теме диссертации опубликовано более 50 печатных трудов в научно-технических журналах, сборниках докладов и научно-технических сборниках, в том числе 18 статей в журналах, включенных в Перечень ВАК.
Основные положения, выносимые на защиту.
Общий метод анализа характеристик древовидных алгоритмов случайного множественного доступа, основанный на взаимосвязях между алгоритмами.
Класс алгоритмов случайного множественного доступа, использующих возможность приема нескольких сообщений одновременно.
Класс алгоритмов, обеспечивающих стабильную работу системы случайного множественного доступа для случая, когда наблюдения канала не позволяют отличить отсутствие передачи от конфликта.
Алгоритмы случайного множественного доступа, использующие адреса абонентов для разрешения как подлинных, так и ложных конфликтов.
Модель централизованной системы случайного множественного доступа с резервированием.
Оценки для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с резервированием.
Структура и объем работы. Диссертационная работа состоит из введения, пяти разделов, заключения, списка использованных источников и пяти приложений. Работа содержит 255 страниц основного машинописного текста, 60 рисунков и 8 таблиц. Список литературы включает 178 наименований.
Принцип построения классической модели
Как отмечалось выше, основная идея метода СМД заключается в том, что абонент источник практически сразу после появления у него сообщения осуществляет его передачу в канал. Если при этом в канале отсутствуют сообщения от других абонентов, то абонент получатель успешно принимает это сообщение. В противном случае, в канале происходит наложение сообщений от различных абонентов, так называемый конфликт. При возникновении конфликта каждый из участников конфликта через случайное время повторяет передачу. В энциклопедии [6] в статьях «Множественный доступ» и «Случайный множественный доступ» приводятся следующие трактовки данных понятий: «Множественный доступ (multiple access)- организация коллективного использования ресурса многими пользователями» ( [6] с.355), «Случайный множественный доступ (random multiple access) - множественный доступ с конфликтом, при разрешении которого требования, ждущие обслуживания, пытаются выйти на ресурс через случайные времена» ( [6] с.605).
Общепризнанно, что первой системой, в которой был использован СМД, явилась система, созданная для связи между вычислительными машинами Гавайского университета. Эта система получила название АЛОХА. В дальнейшем, вышеописанный простейший алгоритм разрешения конфликта получил название АЛОХА [5].
Уже с момента появления алгоритма АЛОХА наметилось некоторое разделение направлений, по которым развивались теоретические и практические исследования.
В теоретических исследованиях основной упор был сделан на изучение поведения алгоритма АЛОХА при большом числе абонентов. При этом бы ло доказано, что увеличение числа абонентов приводит к катастрофическому увеличению задержки и начались поиски альтернативных алгоритмов. В работах Цыбакова, Михайлова [7] и Капетанакиса [8] были предложены так называемые древовидные алгоритмы разрешения конфликта и доказано, что с помощью этих алгоритмов можно получить конечную задержку при доступе к общему каналу с бесконечным числом абонентов. Таким образом, автоматически обеспечивалась работа и при любом конечном числе абонентов. С этого момента начался бурный рост количества работ, посвященных исследованию методов СМД. Максимальное число работ относится к середине 80-х годов прошлого века. В 1985 году выходит специальный выпуск журнала IEEE Transactions on Information Theory [9], целиком посвященный исследованию методов СМД. Однако в последующие пятнадцать лет интерес к исследованиям в этом направлении постепенно уменьшался.
В практических разработках, начиная с середины семидесятых годов прошлого века, основной средой передачи для вычислительных сетей являлся кабель. Поэтому основной задачей для практики стала адаптация алгоритма АЛОХА к особенностям кабельных сетей. При тех скоростях передачи, которые использовались в таких сетях, время передачи сообщения существенно превышало время распространения физического сигнала. Данная особенность позволила значительно уменьшить как вероятность возникновения конфликта, так и время, затрачиваемое на его обнаружение за счет использования алгоритма CSMA/CD (множественный доступ с прослушиванием несущей частоты и обнаружением конфликтов). В этом алгоритме абонент может через короткий промежуток времени, равный времени распространения физического сигнала, определить, передают другие абоненты в этот момент времени или нет. Кроме того, проверка канала осуществляется также и во время передачи пакета. В том случае, когда абоненты «слышат», что в канале произошел конфликт, они могут прервать передачу своих пакетов. CSMA/CD был впервые применен в сети Ethernet, разработанной фирмой Xerox в 1975 г., а затем вошел в стандарт IEEE 802.3. При относительно небольшом числе абонентов CSMA/CD делает конфликты маловероятными, и поэтому собственно алгоритм разрешения конфликта слабо влияет на характеристики сети. По-видимому, именно широкое распространение сетей на основе стан дарта IEEE 802.3 и создавшаяся при этом иллюзия, что все проблемы СМД для практики решены и послужили причиной снижения интереса исследователей к проблематике СМД.
Тем не менее, широкое распространение беспроводных сетей привело к тому, что в с начала двадцать первого века снова наблюдается тенденция к увеличению числа работ, посвященных СМД. Наиболее полный обзор современных работ по данной тематике содержится в [10] и [11]. Выше обсуждалось, что СМД целесообразно применять в условиях большого числа абонентов и пульсирующего входного трафика малой интенсивности. Эти условия часто имеют место в локальных сетях (Ethernet, протоколы IEEE 802.3, IEEE 802.11). В региональных сетях стандарта IEEE 802.16 [12,13] и LTE [14] СМД используют для резервирования времени при передаче данных от абонентов к базовой станции, а в сотовых сетях стандарта GSM - в канале управления для резервирования времени при пакетной передаче. В этих случаях конфликты возникают редко, и задержка сообщения оказывается существенно меньше, чем при использовании других методов разделения ресурса.
В настоящее время как в теории, так и в практике применения методов СМД имеется ряд нерешенных задач. При этом интенсивное развитие современных систем передачи данных и, в особенности, беспроводных систем, ставит новые задачи и делает вновь актуальными те задачи, которым ранее не уделялось должного внимания. Из всего множества таких задач кратко охарактеризуем те задачи, которые рассматриваются в настоящей работе.
Задача 1). Во всех реальных системах в качестве алгоритма СМД используется модификация алгоритма АЛОХА, так называемый алгоритм двоичной экспоненциальной «отсрочки» (binary exponential backoff, ВЕВ) или его разновидности. Известно, что этот алгоритм не обеспечивает устойчивой работы системы при бесконечном числе абонентов. Хотя в реальных системах число абонентов всегда конечно, такая особенность алгоритма может привести к тому, что даже при конечном, но достаточно большом числе абонентов, задержки сообщений в системе могут быть весьма значительными даже при сравнительно низкой интенсивности входного потока. Свободны от этого недостатка так называемые древовидные или стек-алгоритмы, впервые предложенные и исследованные в работах [7] и [8].
Вычисление оценок скорости для базового алгоритма разрешения конфликта
Использование в классической модели входного пуассоновского потока обусловлено в первую очередь тем, что для этого потока могут быть сравнительно просто получены такие основные характеристики различных алгоритмов СМД как скорость, средняя задержка и т.п. Кроме того, для пуассоновского входного потока при вычислении средней задержки не существенно задержка какого именно пакета вычисляется (значения актуальной и виртуальной средних задержек совпадают [23,24]). Можно сказать, что пуассонов-ский входной поток играет в теории СМД такую же роль, как пуассоновский входной поток заявок и экспоненциальное время обслуживания в теории систем массового обслуживания.
Кроме того, для пуассоновского потока существенным образом может быть уменьшено множество исследуемых алгоритмов СМД. В работе [46] показано, что любому алгоритму СМД А из множества Л может быть поставлен в соответствие алгоритм AQ ИЗ подмножества Дуд С Л (см. пункт 1.5.1). При этом соответствие всегда может быть установлено таким образом, что для алгоритма AQ скорость, средняя задержка и другие характеристики при пуас-соновском входном потоке будут такими же, что и для алгоритма А. В работе [46] алгоритм Ао называется алгоритмом ассоциированным с алгоритмом А. Любой алгоритм Ао Є ANR может быть интерпретирован как некоторое правило «просмотра» временной оси, на которой расположены «точки» пуас-соновского потока. В энциклопедии [6] в статье «Случайный множественный доступ» исследование свойств именно таких алгоритмов рассматривается как одна из типовых задач случайного множественного доступа. В работе [47] описывается общий подход к построению правил «просмотра» временной оси для любого древовидного алгоритма.
Многочисленные исследования, которые начали особенно активно проводиться с начала 90-х годов двадцатого века показали, что потоки в современных сетях часто весьма далеки от пуассоновского (см., например, [48]). Среди множества моделей, которые используются в настоящее время для описания потоков, наиболее привлекательной является модель пуассоновского потока со случайной интенсивностью (см., например, [49]). Эта модель с одной стороны позволяет достаточно точно описывать реальные потоки, а с другой стороны допускает использование при анализе известных аналитических и численных методов. Пуассоновский поток со случайной интенсивностью часто называют марковски-модулированным или процессом Кокса [50], а его обобщение - дважды стохастическим случайным процессом. В работе [51] рассматривается один весьма наглядный пример дважды стохастического процесса. Сначала автором вводится случайная величина распределенная по биномиальному закону: где тир- некоторые константы являющиеся параметрами биномиального распределения, а к = 0,1,2,..., т. Затем предлагается обобщение биномиального распределения. Для этого обобщенного распределения параметр р является непрерывной случайной величиной и описывается некоторой плотностью вероятности w(p), где р Є (0,1). В работе [51] для закона распре деления случайной величины р используется термин «управляющий закон-распределенпе». Для вычисления распределения вероятности случайной величины необходимо выполнить вероятностное усреднение функции (1.7) по значениям р Є (О,1): Pr{ = к}= Q J\k(l-p)m-kw(p)dp, (1.8) Кроме того, в [51] со ссылкой на [52] приводятся соотношения, которые показывают связь между математическим ожиданием Е[ ] и дисперсией _D[] случайной величины с соответствующими параметрами Е[р] и D\p] случайной величины р: Е[] = mE\p),D[$] = тЕ\р}(1 - Е\р]) + т(т - l)D\p]. (1.9) Из приведенных выше соотношений следует, что для обобщенного биномиального распределения дисперсия возрастает пропорционально квадрату т, а для обычного биномиального распределения эта зависимость линейная. Приведенный в [51] подход впрямую может быть использовані для исследования влияния случайных изменений характеристик входных потоков на характеристики алгоритмов СМД. Для упрощения изложения, продемонстрируем это на примере простейшего алгоритма СМД - алгоритма АЛОХА (см. пункт 1.5.2). Рассмотрим модель с конечным числом абонентов и бернуллиев-ским входным потоком (см. пункт 1.3.6). Данная модель полностью задается двумя параметрами: интенсивностью входного потока А и числом абонентов М. При этом вероятность появления пакета у абонента равна Л/М — р. Для этой модели бернуллиевский входной поток играет такую же роль, как и пуассоновский поток для классической модели СМД с бесконечным числом абонентов. В [1] применительно к этой модели описывается способ анализа алгоритм АЛОХА. Этот способ заключается в том, что рассматривается последовательность случайных величин N1, где N - число активных абонентов (т.е. абонентов имеющих готовый для передачи пакет) к началу окна , и показывается, что эта последовательность является цепью Маркова. В [1] описывается алгоритм вычисления переходных вероятностей этой цепи в виде некоторых функций (рог(М,р) от М, р — М/Х: Pr{Nt+1 = i/N = j} = Vji(M,p), (1.10) гдег = 0,1,2,...,М, j = 0,1,2,...,M. Можно показать, что эта цепь всегда эргодична и, следовательно, у цепи существует стационарное распределение: где і = 0,1,2,..., М / = Km Рг{М1 = і}, (1.11) t—юс. Это стационарное распределение может быть легко вычислено на основе переходных вероятностей (1.10). Так как далее будет рассматриваться только стационарный случай, индекс t у переменных Nb будем опускать. Стационарное распределение позволяет вычислить такие характеристики алгоритма, как математическое ожидание и дисперсия числа активных абонентов в стационарном режиме: м E[N] = Y,ifu (1-12) М D[N] = J2i2fi-(E[N})2- (1.13) Следуя работе [51] будем теперь полагать, что параметр модели р является непрерывной случайной величиной. Для различных окон случайные величины р независимы и одинаково распределены. При этом задана некоторая функция плотности вероятности w(p). Используя подход, описанный в работе [51] можно показать, что и в этом случае последовательность случайных величин iV4 является марковской цепью, а переходные вероятности данной цепи вычисляются следующим образом: Pr{Nt+1 = i/N1 = j}= f ipji(M,p)w(p)dp. (1.14)
Как и в работе, [1] па основе этих переходных вероятностей могут быть вычислены такие характеристики алгоритма как математическое ожидание и дисперсия числа активных абонентов в стационарном режиме. Рассматриваемый поход позволяет учесть влияние характеристик случайной величины р на характеристики алгоритма. Проиллюстрируем сказанное на следующем примере. Зафиксируем число абонентов М и интенсивность входного потока Л. Выберем некоторое распределение случайной величины р, которое полностью задается двумя параметрами - математическим ожиданием Е\р\ и дисперсией D\p]. При этом зададим Е\р] = Л/М, aD[p] будем изменять в некотором диапазоне, начиная с нуля. Случай D\p\ = 0 соответствует ситуации рассмотренной в работе [1]. На рисунке 1.6 приведены зависимости E[N] и л/ЩЩ от стандартного отклонения случайной величины р (т.е. от і/Щр\).
Вычисление значения пропускной способности алгоритма и обобщение результатов на весь класс алгоритмов с отложенными интервалами
В данном разделе будем рассматривать классическую модель системы случайного множественного доступа с бесконечным числом абонентов и пуас-соновским входным потоком (см. подраздел 1.3).
Рассматриваемые здесь алгоритмы относятся к классу алгоритмов, для которых работа системы описывается последовательностью сеансов [7]. Каждому сеансу соответствует некоторое подмножество абонентов, передавших свои пакеты в первом окне сеанса (окно іо)- Число одновременно переданных пакетов к называется кратностью конфликта в окне. При наблюдении в окне to событий Е (к = 0) и S (к = 1) первое окно сеанса является также его последним окном. В противном случае сеанс завершается не раньше, чем будут успешно переданы все пакеты, столкнувшиеся в окне іо- При. этом правило определения последнего окна сеанса основано на анализе наблюдаемой последовательности событий в окнах, поэтому решения абонентов о последнем окне сеанса совпадут и будут приняты одновременно. Сеансы во времени следуют друг за другом без пропусков, т.е. первое окно следующего сеанса непосредственно граничит с последним окном предыдущего сеанса. Рассматриваются так называемые блокированные алгоритмы [7], для которых все пакеты, возникшие у абонентов во время текущего сеанса, могут быть переданы только в следующем сеансе, т.е. в окнах каждого сеанса передают пакеты только те абоненты, чьи пакеты столкнулись в первом окне сеанса.
Говорят, что на протяжении сеанса в системе разрешается конфликт кратности к, если в первом окне этого сеанса было передано к пакетов. Алгоритм разрешения конфликта (АРК) задается, во-первых, правилом, согласно которому все абоненты определяют последнее окно сеанса, и, во-вторых, правилом, согласно которому каждый участник сеанса определяет в сеансе те окна, в которых будет производиться повторная передача.
Для описания АРК удобно ввести в рассмотрение неориентированный граф G, представляющий собой бесконечное двоичное дерево, вершины которого соответствуют окнам в канале связи, а корневая вершина соответствует первому окну сеанса to, в котором произошел конфликт кратности к. Пару вершин в дереве G будем называть смежными, если они имеют общего непосредственного предка. При этом одну из этих вершин будем называть для определенности верхним нижними и верхними потомками, будем для краткости называть верхними и нижними вершинами соответственно. В процессе разрешения конфликта абоненты наблюдают на выходе канала последовательность событий из множества {Е, S, С} и помечают соответствующие вершины дерева G символами Е, S и С. В результате разрешения конфлик та в дереве G будут помечены все вершины, соответствующие окнам сеанса, и в дереве G будет выделено конечное двоичное поддерево потомком, а другую - нижним потомком (эти названия оправданы, если дерево рисовать слева направо от предков к потомкам). Вершины дерева G, являющиеся с корневой вершиной Proot, соответствующее сеансу. Это поддерево будем называть деревом разрешения конфликта (ДРК). Таким образом, для описания алгоритма разрешения конфликта необходимо, во-первых, указать соответствие между окнами сеанса и вершинами ДРК, и, во-вторых, указать, в каких окнах должен передавать пакеты каждый участник сеанса. Для базового алгоритма соответствующие указания приведены ниже.
Соответствие между окнами сеанса и вершинами ДРК зададим по ин дукции. Первому окну сеанса to соответствует корневая вершина дерева G; Если текущему окну сеанса соответствует вершина Рсц,. в G, помеченная символом С, то следующему окну сеанса соответствует верхний потомок вершины Рсиг в G (см. рисунок 2.1, а). Если текущему окну сеанса соответствует вершина Р в G, помеченная символом Е или символом 5", то следующему окну сеанса соответствует вершина P„ext в G со следующими свойствами (см. рисунок 2.1, б) - вершина Pnext еще не помечена; - вершина, смежная с Pnext, уже помечена; - из всех вершин с указанными свойствами выбирается та, от которой путь до вершины Per содержит наименьшее число ребер. Если вершина Pnext с требуемыми свойствами отсутствует (см. рисунок 2.1, в), то это возможно только в том случае, когда все вершины дерева помечены. При этом построение ДРК завершается.
2. Правило выбора окон для передачи пакетов участниками сеанса также зададим по индукции. В первом окне сеанса передают пакеты все участники сеанса. Если абонент-участник сеанса передавал пакет в окне, соответствующем вершине Рсиг, которая в конце этого окна получила метку S, то больше этот пакет не передается.
Если абонент-участник сеанса передавал пакет в окне, соответствующем вершине Рсиг, которая в конце этого окна получила метку С, то он с равными вероятностями ставит временную метку SfT (Selected for Transmit) на одну Окно t Окно t + Окно t Рисунок 2.1. Пометка вершин в ДРК для базового алгоритма из двух вершин, являющихся непосредственными потомками вершины Рыт В дальнейшем абонент будет передавать пакет в том окне t, которое будет соответствовать вершине с временной меткой SfT. В конце окна t временная метка SfT удаляется.
В построенном по вышеописанным правилам ДРК все концевые вершины дерева имеют метки Е пли S, остальные вершины дерева имеют метку С.
Число единиц времени, которое затрачивается на построение дерева, называется временем разрешения конфликта. Для базового алгоритма число вершин в ДРК равно времени разрешения конфликта. Обозначим через т случайную величину, равную времени разрешения конфликта. Условное математическое ожидание Тк = Е[тJразрешается конфликт кратности к] будем называть средним временем разрешения конфликта кратности к. Далее при рассмотрении условных математических ожиданий в целях упрощения обозначений условие, указывающее, что разрешается конфликт кратности к , будем опускать.
В работе [7] было показано, что на основе отношения —могут быть установлены следуютцие границы для скорости алгоритма В работах [7] и [8] предлагаются способы оценки для нижнего и верхнего пределов из (2.4) и приводятся численные значения верхней и нижней границ для скорости базового алгоритма (2.1).
В работе [83] рассматривалось обобщение базового алгоритма на случай, когда «ветвление» в дереве происходит не на две, а на т ветвей и, в частности, исследовалось поведение величины Тк при больших значениях кратности конфликта к. Формула (28) из этой работы описывает асимптотический вид для отношения 2 для любого т 2. Частный случай для т = 2 и к » 1 приведен в работе [84] в виде
Алгоритмы, использующие адреса абонентов для разрешения конфликтов в канале с шумом
В предыдущем разделе диссертационной работы были рассмотрены алгоритмы, которые работают при полной троичной обратной связи (см. раздел 1.3, Допущение CHAN.INFO.TERN). Напомним, что полная троичная обратная связь предполагает, что абоненты постоянно наблюдают выход канала и по результатом наблюдений могут различить три события - в канале нет передачи (событие Е), в канале передавалось сообщение от одного абонента (событие S) и в канале произошло наложение сообщений от двух и более абонентов (событие С). Именно для этого вида обратной связи в работах [7] и [8] впервые были предложены алгоритмы, которые обеспечивают конечную среднюю задержку при бесконечном числе абонентов. После появления этих работ сравнительно быстро были предложены и исследованы алгоритмы для двоичной обратной связи вида «ПУСТО» - «НЕ ПУСТО» (Е - NE) и «КОНФЛИКТ» - «НЕ КОНФЛИКТ» (С - JVC). Охарактеризуем эти виды двоичной обратной связи.
По сигналу обратной связи типа С - NC абоненты в конце каждого окна узнают, был ли в том конце конфликт или нет. Этот тип двоичной обратной связи является наиболее исследованным. Во многих алгоритмах СМД используется именно этот тип обратной связи, хотя в работах, в которых эти алгоритмы исследуются, не всегда впрямую указывается на двоичный характер обратной связи. К таким алгоритмам относятся, например, немоди-фицированный блокированный и неблокированный стек-алгоритмы [90, 91] (см. подраздел 1.5).
По сигналу обратной связи типа Е - NE абоненты в конце каждого окна узнают, было ли оно пустым или нет. Такая обратная связь может встретиться в системах связи, использующих криптографическое кодирование с открытым ключом [92]. Предположим, что некоторый абонент Азгс является единственным абонентом, который передавал пакет в окне t получателю A t и пакет был зашифрован с помощью открытого ключа получателя. Тогда простым прослушиванием канала передававший абонент Asrc узнает, был ли пакет передан успешно или нет. Получатель Adst узнает о успешном приеме используя свой закрытый ключ. Все остальные абоненты имеют информацию только о том, что в данном окне была передача, но успешна эта передача или нет другие абоненты не знают. СМД с обратной связью типа Е - NE исследовался в работах [92-97].
Теперь перейдем к рассмотрению обратной связи вида «УСПЕХ» -«НЕУСПЕХ» (S - NS). По сигналу обратной связи типа S - NS абоненты в конце каждого окна определяют был ли в данном окне успешно передан пакет или нет. Обратная связь такого типа может встретиться, например, в широкополосных системах множественного доступа, в которых абоненты стремятся скрыть факт передачи пакета, поддерживая удельную (на единицу полосы) мощность передатчика на низком уровне. Использование шумоподобных сигналов приводит к тому, что абоненты не могут надежно отличить наложение низких пакетов от шума [92].
Другим примером системы в которой может встретиться обратная связь типа S - NS, является система с передачей положительных квитанций. Такая система состоит из центрального абонента (ретранслятора) и периферийных абонентов. Периферийные абоненты передают пакеты центральному абоненту по прямому каналу. Периферийные абоненты не имеют возможности непосредственно прослушать входной канал и узнают о результатах своей передачи но квитанции, посылаемой центральным абонентом по каналу обратной связи. Квитанция формируется и передается лишь в случае успешного приема пакета. Очевидно, что в такой системе периферийные абоненты не имеют возможности отличить отсутствие передачи от наложения нескольких пакетов.
В 1988 В.Н.Михайлов в работе [32] описал класс алгоритмов, в котором существуют алгоритмы, обеспечивающие устойчивую работу как при троич ной обратной связи, так и при обратной связи вида Е - NE и С - NC, и не существует таких алгоритмов для обратной связи S — NS. Различные алгоритмы, предложенные для такого вида обратной связи в работах [95], [93] и [94], обеспечивают устойчивое функционирование СІЇстемы, лишь за счет некоторых расширений модели системы типа введения специального тестирующего пакета и т.п.
В 1989 году Б. С. Цыбаков и Н. Б. Лиханов в работе [61] указали способ вычисления пропускной способности системы СМД для троичной обратной связи при наличии ложных конфликтов, которые могут ошибочно наблюдаться абонентами в пустом окне с вероятностью q0 и с вероятностью q\ в окне, в котором передавал только один абонент (данная модель введена в подразделе 1.6, см. Допущение CHAN.TYPE.NOISE). Из результатов работы следовало, что пропускная способность системы отлична от нуля при любых значениях вероятности q , если q\ 0. С учетом того, что случай qo = 1 при gi = 0 приводит троичную обратную связь к двоичной вида S -NS, из данной работы следовало, что могут существовать алгоритмы, обеспечивающие устойчивую работу при обратной связи S — NS без расширения модели системы.
В 1992 в работе [97] была предложена идея обеспечения устойчивой работы при обратной связи S - NS, которая, в данной работе не была доведена до уровня алгоритма. Затем в 1995 году в работе [98] впервые было дано четкое описание одного алгоритма; выписаны уравнения баланса, которым должно удовлетворять стационарное распределение соответствующей цепи Маркова, и численно найдено такое значение интенсивности входного потока До, что уравнения баланса имеют решение тогда и только тогда, когда А До- Автору диссертационной работы неизвестно о каких-то последующих публикациях работ, посвященных исследованию алгоритмов для случая обратной связи S -NS.
Раздел организован следующим образом. В подразделе 3.2 уточняется модель системы случайного множественного доступа для случая обратной связи S — NS. Затем в следующем подразделе применительно к этой модели предлагается модификация стек-алгоритма, которая позволяет за счет потери части пакетов обеспечить устойчивую работу системы. Последующие
