Тюрликов, Андрей Михайлович. Алгоритмы разрешения конфликтов в системах передачи информации со случайным множественным доступом

Краткое описание

Тюрликов, Андрей Михайлович. Алгоритмы разрешения конфликтов в системах передачи информации со случайным множественным доступом : диссертация ... доктора технических наук : 05.13.01 / Тюрликов Андрей Михайлович; [Место защиты: С.-Петерб. гос. ун-т аэрокосм. приборостроения].- Санкт-Петербург, 2011.- 295 с.: ил. РГБ ОД, 71 12-5/56

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

На правах рукописи
y^f
05201і510і8 ТЮРЛИКОВ
Андрей Михайлович
АЛГОРИТМЫ РАЗРЕШЕНИЯ КОНФЛИКТОВ
В СИСТЕМАХ ПЕРЕДАЧИ ИНФОРМАЦИИ
СО СЛУЧАЙНЫМ МНОЖЕСТВЕННЫМ
ДОСТУПОМ
Специальность 05.13.01 - Системный анализ, управление и обработка информации (в технике и технологиях)
ДИССЕРТАЦИЯ
на соискание ученой степени
доктора технических наук
Научный консультант доктор технических наук профессор Е.А. Крук
Санкт-Петербург 2011

СОДЕРЖАНИЕ
Список использованных сокращений 8
Введение 9
1. Модели систем со случайным множественным доступом абонентов в
общий канал связи 18
1.1 Вводные замечания и классификация систем множественного доступа 18
1.2 Развитие методов СМД и актуальные задачи теории и практики применения методов СМД 23
1.3 Классическая модель СМД 27

1.3.1 Принцип построения классической модели 27
1.3.2 Система связи 27
1.3.3 Канал связи 30
1.3.4 Обратная связь 31
1.3.5 Абонент 33
1.3.6 Классические модели СМД 34

1.4 Понятие и характеристики алгоритма СМД, пропускная способ¬ность системы СМД 36
1.5 Описание алгоритмов для классической модели 40

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 Уточнение понятия алгоритма СМД 57
2

1.6.4 Изменение модели относительно канала связи для учета шу¬мов в канале связи 58
1.6.5 Учет различных видов обратной связи в модели 63

1.7 Базовый и модифицированный алгоритмы с компенсацией кон¬фликтных сигналов 64
1.8 Заключительные замечания 70
2. Методы анализа характеристик древовидных алгоритмов разрешения
конфликтов 72
2.1 Роль древовидных алгоритмов разрешения конфликта в разви¬тии теории случайного множественного доступа 72
2.2 Вычисление оценок скорости для базового алгоритма разреше¬ния конфликта 74
2.3 Использование свойств базового алгоритма разрешения кон¬фликта для анализа характеристик блокированных алгоритмов
и основное свойство дерева разрешения конфликтов 79
2.4 Вычисление скорости алгоритма для канала с шумом 84
2.5 Вычисление скорости для алгоритмов с компенсацией кон¬фликтных сигналов 90

2.5.1 Вычисление скорости для базового алгоритма с компенсаци¬ей конфликтных сигналов 90
2.5.2 Вычисление скорости для модифицированного алгоритма с компенсацией конфликтных сигналов 94

2.6 Неблокированные древовидные алгоритмы и анализ их характе¬ристик 100
2.7 Выводы по разделу 107
3. Случайный множественный доступ при двоичной обратной связи успех-
неуспех 109
3.1 Обеспечение устойчивой работы системы при двоичной обратной связи успех-неуспех - одна из открытых проблем теории случай¬ного множественного доступа 109
3.2 Модель системы 112
3

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 Условия положительной возвратности и эргодичности .... 132

3.6 Вычисление значения пропускной способности алгоритма и обобщение результатов на весь класс алгоритмов с отложенными интервалами 135
3.7 Расширение класса алгоритмов 138
3.8 Выводы по разделу 140
4. Использование адресов абонентов при разрешении конфликтов 145
4.1 Использование адресов абонентов при разрешении конфлик¬тов как альтернатива чисто случайным механизмам разрешения конфликтов 145
4.2 Модель системы и уточнение понятия скорости 147

4.2.1 Особенности классической модели для случая конечного числа абонентов 147
4.2.2 Дисциплины работы абонентов с очередью 148
4.2.3 Модель с двухпакетной очередью 151
4

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.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
Список использованных источников 239
ПРИЛОЖЕНИЕ А. Дискретные пачечные марковские входные процессы256
ПРИЛОЖЕНИЕ Б. Использование преобразования Пуассона при анализе
древовидных алгоритмов 259
Б.1 Определения и обозначения 259
Б.2 Вычисление преобразования Пуассона 261
Б.З Нормированное преобразование Пуассона 263
Б.3.1 Определение 263
Б.3.2 Вычисление G^r) 264
Б.3.3 Вычисление F(r) 265
Б.4 Вычисление оценок скорости для базового алгоритма 267
6

Б.5 Вычисление среднего числа конфликтов заданной кратности . . 269
ПРИЛОЖЕНИЕ В. Доказательство теорем, используемых при асимп¬
тотическом анализе алгоритма случайного множественного доступа
при обратной связи S - не S lib
8.1 Доказательство части (а) теоремы 3.1 275
8.2 Доказательство части (б) теоремы 3.1 277
8.3 Доказательство части (а) теоремы 3.2 278
8.4 Доказательство части (б) теоремы 3.2 278
8.5 Вспомогательные утверждения, используемые при доказатель¬стве теорем 279
ПРИЛОЖЕНИЕ Г. Доказательства теорем 4.2 и 4.3 281
ПРИЛОЖЕНИЕ Д. Вспомогательные результаты для классической мо¬
дели 290
ПРИЛОЖЕНИЕ Е. Основные принципы сжатия и передачи видеоинфор¬
мации 292
7

Список использованных сокращений

ATM - asynchronous transfer mode;
ВЕВ - binary exponential backoff;
CDMA - code division multiple access;
CSMA - carrier sense multiple access;
DL - downlink;
FET - first exit time;
FRT - first regeneration time;
IEEE — institute of electrical and electronic engineers;
MAC - media access control;
OFDM - orthogonal frequency division multiplexing;
OFDMA - orthogonal frequency division multiple access;
SIC — successive interference cancellation;
SICTA - successive interference cancellation in a tree algorithm;
UL - uplink;
UL-MAP - uplink map;
VoD — video on demand;
VoIP - voice over Internet protocol;
АДК - алгоритм доступа к каналу;
АРК - алгоритм разрешения конфликта;
АС - абонентская станция;
ВС - базовая станция;
ДРК - дерево разрешения конфликта;
ДЭО - двоичная экспоненциальная «отсрочка»;
КО - качество обслуживания;
МДА - модифицированный древовидный алгоритм;
ППП - передача в порядке поступления;
ПРК - период разрешения конфликта;
СДА - стандартный древовидный алгоритм;
СМД - случайный множественный доступ;
УДС - управление доступом к среде.
8

Введение
Актуальность проблемы. В последние десятилетия отмечается тенден¬ция активного роста числа систем передачи информации, построенных на основе каналов множественного доступа, таких как радиоканалы и спутни¬ковые каналы связи. Среди методов управления доступом большого числа абонентов к общему каналу особое место занимают методы случайного мно¬жественного доступа с разрешением конфликтов. При достаточно низкой ин¬тенсивности входного потока сообщений к абонентам конфликты возникают редко, и задержка сообщения оказывается существенно меньше, чем при ис¬пользовании других методов множественного доступа.
Первой системой, в которой был использован случайный множествен¬ный доступ, являлась система «АЛОХА», созданная в конце шестидесятых годов двадцатого века для связи между вычислительными машинами Га¬вайского университета. Алгоритм разрешения конфликта, используемый в данной системе, был предложен и исследован Н.Абрамсоном, а затем улуч¬шен Ф.Тобаги. Этот алгоритм прост в реализации, при относительно неболь¬шом числе абонентов обеспечивает низкую задержку, и по этим причинам до сих пор широко используется в современных системах. Однако в рабо¬тах Д.Алдоуса и ряда других авторов было доказано, что даже при по¬стоянной суммарной интенсивности входного потока увеличение числа або¬нентов приводит к катастрофическому увеличению задержки. Путь реше¬ния данной проблемы был предложен Б.С.Цыбаковым, В.А.Михайловым и Дж.Капетанакисом. Этими авторами была впервые введена модель системы случайного множественного доступа бесконечного числа абонентов к общему каналу передачи данных при пуассоновском входном потоке сообщений. При¬менительно к этой модели были предложены так называемые древовидные алгоритмы разрешения конфликта и было доказано, что с помощью этих ал¬горитмов можно получить конечную среднюю задержку при некоторой огра¬ниченной интенсивности входного потока. В теории случайного множествен¬ного доступа данная модель является классической и используется в науч¬ных трудах отечественных и зарубежных ученых, таких как Н.Д.Введенская, Г.С.Бвсеев, Н.Б.Лиханов, Б.Гаек, Дж.Месси, Р.Галлагер и др.
9

В конце последнего десятилетия прошлого века случайный множествен¬ный доступ получил новый импульс в развитии в связи с его применением в беспроводных сетях. В первую очередь это относится к сетям стандарта IEEE 802.11 (Wi-Fi). Анализу соответствующего протокола множественного досту¬па посвящены работы Дж.Бианки, А.И.Ляхова, В.М.Вишневского и ряда дру¬гих авторов. Случайный множественный доступ с разрешением конфликтов используется для резервирования общего канала в региональных беспровод¬ных сетях, соответствующих стандартам IEEE 802.16 и 3GPP LTE. Имеются лишь единичные работы (Г.Гианнакис, К.Блондиа), в которых предлагают¬ся методы, позволяющие повысить эффективность алгоритмов разрешения конфликта, используемых в таких системах. В этих работах рассматривает¬ся весьма упрощенная модель системы.
Эффективность работы алгоритмов разрешения конфликта, используе¬мых в современных системах передачи информации, существенно снижается с увеличением числа абонентов. Учитывая тенденцию к дальнейшему росту числа абонентов, можно ожидать, что в ближайшем будущем этот недостаток окажет негативное влияние на развитие систем передачи информации в це¬лом. Алгоритмы, разработанные для классической модели, свободны от этого недостатка. Однако эти алгоритмы не могут быть непосредственно использо¬ваны в современных системах, так как в классической модели не отражены особенности таких систем (изменение интенсивности потока во времени, от¬сутствие достоверной информации о событиях в канале, наличие механизмов резервирования канала и т.п.). Таким образом, одной из основных проблем в теории и практике случайного множественного доступа в настоящее время является разработка новых алгоритмов разрешения конфликта, которые мо¬гут быть использованы как в существующих, так и в перспективных системах передачи информации с большим числом абонентов.
Цель диссертационной работы. Целью диссертационной работы яв¬ляется разработка и исследование алгоритмов случайного множественного доступа, имеющих существенное значение для повышения эффективности функционирования современных беспроводных систем передачи информа¬ции.
В соответствии с целью исследования были поставлены следующие основ-
10

ные задачи.
1. Создание методологической основы для исследования систем случайно¬го множественного доступа.
2. Разработка общего метода исследования древовидных алгоритмов слу-чайного множественного доступа.
3. Разработка новых алгоритмов случайного множественного доступа, учитывающих особенности современного приемо-передающего оборудо-вания.
4. Обеспечение стабильной работы системы случайного множественного доступа для случая, когда наблюдения канала не позволяют различить отсутствие передачи в канале от конфликта.
5. Разработка алгоритмов случайного множественного доступа, использу-ющих адреса абонентов для разрешения как подлинных, так и ложных конфликтов.
6. Построение модели централизованной системы случайного множествен¬ного доступа с резервированием, с учетом основных особенностей совре¬менных региональных сетей.
7. Построение оценок для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с резервированием.
8. Использование предложенных методов и алгоритмов для повышения эффективности функционирования централизованной системы случай¬ного множественного доступа.
Методы исследования. При получении основных результатов работы использовались общие методы системного анализа, методы теории вероятно¬стей, теории случайных процессов, в частности регенерирующих и марков¬ских процессов, теории систем массового обслуживания, численные методы, а также методы имитационного моделирования.
Научная новизна диссертационной работы заключается в следующем. 1 Впервые классифицированы допущения, используемые при изучении систем случайного множественного доступа, и сформулирована мето¬дологическая основа для исследования существующих и новых систем.
11

2. Предложен новый метод анализа характеристик древовидных алгорит¬мов случайного множественного доступа, основанный на взаимосвязях между алгоритмами.
3. Разработаны новые алгоритмы случайного множественного доступа, ис-пользующие возможность приема нескольких сообщений одновременно.
4. Впервые предложен класс алгоритмов, обеспечивающий устойчивую ра¬боту системы случайного множественного доступа для случая, когда наблюдения канала не позволяют отличить конфликт от отсутствия пе¬редачи в канале.
5. Впервые разработаны алгоритмы случайного множественного доступа, использующие адреса абонентов для разрешения как подлинных, так и
.ложных конфликтов.
6. Предложена новая модель централизованной системы случайного мно-жественного доступа с резервированием, отражающая основные особен-ности современных региональных сетей.
7. Впервые построены оценки для показателей производительности (про-пускной способности) централизованной системы случайного множе-ственного доступа с резервированием.
8. Предложены новые способы повышения эффективности функциониро¬вания централизованной системы случайного множественного доступа.
Практическая ценность работы. На основе результатов работы сфор-мулирован ряд модификаций существующего протокола региональной бес-проводной сети передачи информации, позволяющих существенно повысить уровень качества обслуживания абонентов. Результаты диссертационной ра¬боты могут быть использованы при проектировании систем передачи инфор¬мации с большим числом абонентов, а также для разработки новых телеком-муникационных протоколов, в которых используются алгоритмы случайного множественного доступа.
Теоретические и практические результаты работы использованы в учебном процессе кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборо¬строения. Результаты работы используются в разработках ЗАО «Интел А/О». Использование результатов подтверждено соответствующими актами.
12

Апробация работы. Основные результаты работы докладывались и об-суждались на:
- Всесоюзных школах-семпнарах по вычислительным сетям (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 статей в журналах, включенных в Перечень ВАК.
Основные положения, выносимые на защиту.
1. Общий метод анализа характеристик древовидных алгоритмов случай¬ного множественного доступа, основанный на взаимосвязях между ал¬горитмами.
2. Класс алгоритмов случайного множественного доступа, использующих возможность приема нескольких сообщений одновременно.
3. Класс алгоритмов, обеспечивающих стабильную работу системы слу-чайного множественного доступа для случая, когда наблюдения канала не позволяют отличить отсутствие передачи от конфликта.
4. Алгоритмы случайного множественного доступа, использующие адреса абонентов для разрешения как подлинных, так и ложных конфликтов.
13

5. Модель централизованной системы случайного множественного досту¬па с резервированием.
6. Оценки для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с ре-зервированием.
Структура и объем работы. Диссертационная работа состоит из введе¬ния, пяти разделов, заключения, списка использованных источников и пяти приложений. Работа содержит 255 страниц основного машинописного текста, 60 рисунков и 8 таблиц. Список литературы включает 178 наименований.
В первом разделе описана область применения методов случайного мно-жественного доступа в современных системах передачи информации и сфор-мулирован ряд актуальных задач, связанных как с теорией, так и с практикой случайного множественного доступа. Описана классическая модель системы случайного множественного доступа. Применительно к классической модели дано понятие алгоритма случайного множественного доступа и таких основ¬ных его характеристик как средняя задержка и скорость. Описаны основ¬ные классы алгоритмов случайного множественного доступа. Введены новые расширения классической модели, позволяющие учитывать особенности со¬временных систем передачи информации. В частности, введены расширения, в которых рассматриваются дважды стохастические входные потоки. Вве¬дено расширение классической модели для учета функционирования проце¬дуры последовательной компенсации конфликтных сигналов на физическом уровне. Применительно к данной модели предложен новый алгоритм разре¬шения конфликтов, отличающийся от ранее известных тем, что обеспечивает устойчивую работу системы при неполной компенсации конфликтных сигна¬лов.
Модели систем со случайным множественным доступом в канал и способ построения таких моделей, предложенный в первом разделе являются ме-тодологической основой для исследования различных систем со случайным множественным доступом, а сформулированные задачи — как направления исследований, описанию результатов которых посвящены последующие раз¬делы диссертационной работы.
Во втором разделе описывается подход к анализу характеристик древо-
14

видных алгоритмов, позволяющий с единых позиций анализировать различ¬ные алгоритмы разрешения конфликта, используя в качестве основы анализа базовый алгоритм разрешения конфликта. Применимость данного подхода продемонстрирована как для классической модели системы случайного мно-жественного доступа, так и для ряда расширений классической модели. В рамках классической модели установлено соотношение между скоростью ба¬зового алгоритма и скоростью модифицированного алгоритма в бесшумном канапе. Для расширения классической модели на случай канала, в котором воздействие шума может приводить к возникновению ложных конфликтов, получено соотношение между скоростью базового алгоритма в канале с шу¬мом и в канале без шума. Проведен анализ для расширения классической мо¬дели на случай, когда возможна компенсация конфликтных сигналов. Уста¬новлено соотношение между скоростью базового алгоритма и скоростями как ранее известного алгоритма, так и нового алгоритма, обеспечивающего устой¬чивую работу при неполной компенсации конфликтных сигналов.
В третьем разделе рассматриваются алгоритмы случайного множествен¬ного доступа для двоичной обратной связи вида «УСПЕХ» - «НЕУСПЕХ». Как и в предыдущих разделах основой для исследования используется клас¬сическая модель системы случайного множественного доступа с бесконеч¬ным числом абонентов, обобщенная на данный вид обратной связи. Сна¬чала рассматривается алгоритм, при работе которого допускаются потери пакетов. Показано, что при низких интенсивностях входного потока поте¬ри пакетов незначительны. Большая часть раздела посвящена случаю, когда потери пакетов не допускаются. Для этого случая предложен класс алго¬ритмов, который в работе назван классом алгоритмов с отложенными ин¬тервалами. Подробно исследован «простейший» алгоритм из этого класса. В результате исследования получено, что данный алгоритм при определенном наборе параметров может обеспечить устойчивую работу. Следует отметить, что результаты, полученные в данном разделе, лишь частично решают зада¬чу обеспечения устойчивой работы системы при обратной связи «УСПЕХ» - «НЕУСПЕХ». Основным результатом является нижняя оценка для про¬пускной способности системы СМД с таким видом обратной связи, остается открытым вопрос о верхней границе.
15

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

марковских входных процессах, которые являются частным случаем дважды стохастического случайного процесса.
В приложении Б описано использование преобразования Пуассона при анализе древовидных алгоритмов.
В приложении В приводятся доказательства теорем, сформулированных в разделе 3.
В приложении Г приводятся доказательства теорем, сформулированных в разделе 4.
В приложении Д приводятся вспомогательные результаты для классиче¬ской модели случайного множественного доступа, которые используются в разделе 5 при построении границ для пропускной способности модели цен¬трализованной сети передачи информации.
В приложении Е приводятся основные принципы сжатия и передачи ви-деоинформации, которые используются в разделе 5 при описании модели цен-трализованной сети передачи видеоданных.

Список литературы

Предложения по улучшению протокола
Для упрощения изложения следующего материала абстрагируемся от про¬цесса передачи пакетов и сосредоточимся на тех улучшениях, которые мож¬но сделать для процесса передачи запросов. Напомним (см. подраздел 5.5.4), что протоколом IEEE 802.16 предусмотрена возможность использования усе¬ченного алгоритма ДЭО для разрешения возникающих конфликтов между передаваемыми запросами. С другой стороны, в. работе [39] было показано, что алгоритм ДЭО нестабилен в классической модели с бесконечным чис¬лом абонентов, то есть практически неработоспособен при увеличении числа абонентов рассматриваемой системы связи.
Для преодоления отмеченного недостатка, связанного с нестабильностью алгоритма ДЭО, можно рассматривать отдельно конкурентные слоты и ис¬пользовать применительно к передаче запросов методы СМД, которые были исследованы в предыдущих разделах в рамках классической системы СМД. Более того, наличие нескольких конкурентных слотов в кадре для переда¬чи запросов к базовой станции позволяет определенным образом упростить работу алгоритма разрешения конфликта. Будем предполагать, что число конкурентных слотов опроса зафиксировано и в этих условиях требуется вы¬брать наиболее эффективный в некотором смысле способ доставки запросов на базовую станцию. Рассмотрим сначала «чисто случайные» способы разре¬шения конфликтов.