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

На правах рукописи

ТЮРЛИКОВ Андрей Михайлович

АЛГОРИТМЫ РАЗРЕШЕНИЯ КОНФЛИКТОВ В СИСТЕМАХ ПЕРЕДАЧИ ИНФОРМАЦИИ СО СЛУЧАЙНЫМ МНОЖЕСТВЕННЫМ ДОСТУПОМ

4843829

Специальность 0.5.13.01 — Системный анализ, управление и обработка информации (в технике и технологиях)

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Санкт-Петербург 2011

1 4 АПР 2011

4843829

Работа выполнена на кафедре безопасности информационных систем в Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения»

Научный консультант: Засл. деятель науки РФ,

доктор технических наук, профессор Крук Евгений Аврамович

Официальные оппоненты: доктор технических наук, профессор

Богатырев Владимир Анатольевич

доктор технических наук, профессор Зеленцов Вячеслав Алексеевич

Засл. деятель науки РФ,

доктор технических наук, профессор

Яновский Геннадий Григорьевич

Ведущая организация: «Всероссийский

научно-исследовательский институт радиоаппаратуры» (ОАО «ВНИИРА»)

Защита состоится « А? » НАЯ_ 2011 г. в )*{ часов на

заседании диссертационного совета Д 212.233.02 при Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу: 190000, г. Санкт-Петербург, ул. Большая Морская, д. 67

С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан « 01 » <40Р£ЛЯ 2011 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

<¿J Осипов Л. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

ния конфликта, используемых в таких системах. В этих работах рассматривается весьма упрощенная модель системы.

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

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

В соответствии с целью исследования были поставлены следующие основные задачи.

1. Создание методологической основы для исследования систем случайного множественного доступа.

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

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

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

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

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

7. Построение оценок для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с резервированием.

8. Использование предложенных методов и алгоритмов для повышения эффективности функционирования централизованной системы случайного множественного доступа.

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

Научная новизна диссертационной работы заключается в следующем.

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

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

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

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

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

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

7. Впервые построены оценки для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с резервированием.

8. Предложены новые способы повышения эффективности функционирования централизованной системы случайного множественного доступа.

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

Теоретические и практические результаты работы использованы в учебном процессе кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения. Результаты работы используются в разработках ЗАО «Интел А/О». Использование результатов подтверждено соответствующими актами.

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

- Всесоюзных школах-семинарах по вычислительным сетям (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. Алгоритмы случайного множественного доступа, использующие адреса абонентов для разрешения как подлинных, так и ложных конфликтов.

5. Модель централизованной системы случайного множественного доступа с резервированием.

6. Оценки для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с резервированием.

Структура и объем работы. Диссертационная работа состоит из введения, пяти разделов, заключения, списка использованных источников и пяти приложений. Работа содержит 255 страниц основного машинописного текста, 60 рисунков и 8 таблиц. Список литературы включает 178 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность проблемы.

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

Допущение 1. У абонентов возникают пакеты, которыми они обмениваются, используя канал связи. Предполагается, что все пакеты имеют одинаковую длину. Время передачи пакета принимается за единицу времени. Время передачи по каналу разделено на окна. Все окна имеют одинаковую длительность, равную времени передачи одного пакета. Окна пронумерованы целыми неотрицательными числами, окну с номером 4 соответствует интервал времени [t — 1,4). Далее в работе для краткости изложения окно с номером 4 будем называть окном 4. Моменты разделения окон известны всем абонентам. Абонент может начинать передачу сообщения только в начале очередного окна.

Допущение 2. В каждом окне может произойти одно из трех событий:

- в окне передает один абонент (событие S - success, успех);

- в окне не передает ни один абонент (событие Е - empty, пусто);

- в окне передают два или более абонентов (событие С - collision, конфликт).

Допущение 3. Абонент, наблюдая выход канала, к концу окна достоверно определяет, какое из трех возможных событий произошло в канале.

Допущение 4. У абонента имеется буфер для хранения одного пакета. Абонент хранит пакет от момента появления до момента успешной передачи. Пакет, который появился на интервале времени [4 - 2,4 - 1), может быть передан не раньше, чем в окне t > 4.

Допущение 5. В системе имеется бесконечное число абонентов. Интервалы времени между моментами появления новых пакетов в системе являются независимыми случайными величинами, распределенными по экспоненциальному закону со средним значением j (число Л называют интенсивностью входного потока пакетов в систему, эта величина равна среднему числу пакетов, которые возникают в системе за единицу времени).

Для классической модели случайного множественного доступа (СМД) алгоритм задается функцией А(х, в(Ь), принимающей

значения на интервале [0,1]. Значение, принимаемое функцией А в окне I, имеет смысл вероятности события, связанного с передачей абонентом в окне Ь пакета, поступившего в момент времени х. Аргументы этой функции имеют следующий смысл:

- первым аргументом является момент времени х поступления пакета к абоненту;

- вторым аргументом является последовательность событий в{{) — (01,...,^) в канале связи. Здесь = Е, если окно г пусто,

= 5, если окно г содержит успешную передачу, и = С, если в окне г произошел конфликт;

- третьим аргументом является последовательность значений

), связанная с абонентом, у которого в момент х возник пакет; здесь — 0, если в окне г абонент не передавал пакет, и — 1, если передавал.

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

В конце первого раздела введено расширение классической модели для учета функционирования процедуры последовательной компенсации конфликтных сигналов на физическом уровне. Использование этой процедуры применительно к алгоритмам разрешения конфликта впервые было исследовано в работах Г.Гианнакиса. Для иллюстрации того, как процедура компенсации конфликтных сигналов позволяет уменьшить время разрешения конфликта, рассмотрим простой пример, приведенный на рисунке 1.

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

Пусть в окне I два абонента передают пакеты А и В одновременно, что приводит к их наложению. Через уь обозначим сигнал, принятый к концу окна t, а через £д и хв - сигналы, соответствующие пакетам данных А и В соответственно. В конце окна t приемник получает сигнал Уг, который формируется в результате наложения на входе приемника сигналов ха, хв и шумов. Эту «смесь» сигналов хл и хв условно бу-

Рисунок 1. Пример работы процедуры компенсации конфликтных сигналов

дем обозначать как yt —Хд+Хв■ После обработки сигнала г/г приемник выносит решение о том, что произошел конфликт. Исходная смесь уь сохраняется. Участки конфликта с вероятностью 5 принимают решение о повторной передаче. Предположим, что в окне принял решение передавать только один из участников конфликта. Получив сигнал Уь+\ — '¿л в конце окна £ + 1, приемник успешно выделяет сигнал хд. По выделенному сигналу восстанавливается пакет А.

Далее процедура компенсации конфликтных сигналов снова обрабатывает сохраненный сигнал ?/г и нейтрализует сигнал хд в сохраненной смеси сигналов уг. Условно эту операцию нейтрализации будем записывать У1 — х а- Из полученного сигнала = уг — хд выделяется сигнал хв — ш, по которому успешно восстанавливается пакет В. Таким образом, дальнейшее разрешение конфликта не требуется. В рассмотренном примере длительность разрешения конфликта уменьшается на одно окно за счет процедуры последовательной компенсации конфликтных сигналов. Без использования этой процедуры в окне Ь + 2 необходимо произвести повторную передачу пакета В.

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

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

- уточняется формулировка и обосновывается актуальность рассматриваемой задачи;

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

- применительно к введенной модели формулируется алгоритм СМД (или класс алгоритмов) и вводятся в рассмотрение случайные процессы, с помощью которых описывается работа алгоритма;

- исследуются введенные случайные процессы и на основе результатов этих исследований определяются основные характеристики алгоритма СМД.

Во втором разделе рассматривается класс древовидных алгоритмов СМД и предлагается подход, позволяющий с единых позиций анализировать различные алгоритмы СМД из этого класса.

В классических работах Б.С.Цыбакова, В.А.Михайлова, Дж.Капетанакиса и Дж.Месси рассматривался древовидный алгоритм разрешения конфликта, который далее будем называть базовым алгоритмом. В этих работах также отмечалось, что из базового алгоритма можно получить алгоритм, имеющий более высокую скорость, который далее будем называть модифицированным алгоритмом. Хотя исследования древовидных алгоритмов проводятся уже более тридцати лет, остается ряд нерешенных задач. Одной из таких задач является разработка общего метода анализа характеристик древовидных алгоритмов и установление взаимосвязи характеристик различных алгоритмов из этого класса. Именно эта задача и решается во втором разделе.

Рассматриваемые во втором разделе алгоритмы относятся к классу алгоритмов, для которых работа системы описывается последовательностью сеансов. Каждому сеансу соответствует некоторое подмножество абонентов, передавших свои пакеты в первом окне сеанса (окно ¿о)- Число пакетов к, переданных в окне ¿о, называется кратностью конфликта. При наблюдении в окне ¿о событий Е (к = 0) и 5 (к = 1) первое окно сеанса является также его последним окном. В противном случае сеанс завершается не раньше, чем будут успешно переданы все пакеты, столкнувшиеся в окне ¿о- При этом правило определения последнего окна сеанса основано на анализе наблюдаемой последовательности событий в окнах, поэтому решения абонентов о завершении сеанса совпадут и будут приняты одновременно. Сеансы во времени следуют друг за другом без пропусков, т.е. первое окно следующего сеан-

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

Для древовидных алгоритмов функция А{х, 0(i), может

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

Для описания базового алгоритма в работе вводится в рассмотрение неориентированный граф G, представляющий собой бесконечное двоичное дерево, вершины которого соответствуют окнам в канале связи, а корневая вершина соответствует первому окну сеанса to, в котором произошел конфликт кратности к. Пару вершин в дереве G будем называть смежными, если они имеют общего непосредственного предка. При этом одну из этих вершин будем называть для определенности верхним потомком, а другую - нижним потомком (эти названия оправданы, если дерево рисовать слева направо от предков к потомкам). Вершины дерева G, являющиеся нижними и верхними потомками, будем для краткости называть верхними и нижними вершинами соответственно. В процессе разрешения конфликта абоненты наблюдают на выходе канала последовательность событий из множества {Е, S, С} и помечают соответствующие вершины дерева G символами Е, S я С. В результате разрешения конфликта в дереве G будут помечены все вершины, соответствующие окнам сеанса, и в дереве G будет выделено конечное двоичное поддерево с корневой вершиной Pr0ot> соответствующее сеансу. Это поддерево будем называть деревом разрешения конфликта (ДРК). Таким образом, для описания алгоритма разрешения конфликта необходимо, во-первых, указать соответствие между окнами сеанса и вершинами ДРК, и, во-вторых, указать, в каких окнах должен передавать пакеты каждый участник сеанса. Для базового алгоритма соответствующие указания приведены ниже.

1. Соответствие между окнами сеанса и вершинами ДРК зададим по индукции.

Первому окну сеанса to соответствует корневая вершина дерева G.

Если текущему окну сеанса соответствует вершина Рсиг в G, помеченная символом С, то следующему окну сеанса соответствует верхний потомок вершины Рсиг в G.

Если текущему окну сеанса соответствует вершина Рсиг в G, помеченная символом Е или символом S, то следующему окну сеанса соответствует вершина Pnext в G со следующими свойствами:

- вершина Pnext еще не помечена;

- вершина, смежная с Pnext, уже помечена;

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

Если вершина Pnext с требуемыми свойствами отсутствует, то это возможно только в том случае, когда все вершины дерева помечены. При этом построение ДРК завершается.

2. Правило выбора окон для передачи пакетов участниками сеанса также зададим по индукции.

В первом окне сеанса передают пакеты все участники сеанса. Если абонент-участник сеанса передавал пакет в окне, соответствующем вершине Pcur, которая в конце этого окна получила метку S, то больше этот пакет не передается.

Если абонент-участник сеанса передавал пакет в окне, соответствующем вершине Рсиг, которая в конце этого окна получила метку С, то он с равными вероятностями выберет для повторной передачи одну

из двух вершин, являющихся непосредственными потомками вершины р

1 cur-

В построенном по вышеописанным правилам ДРК все концевые вершины дерева имеют метки Е или S, остальные вершины дерева имеют метку С.

Число единиц времени, которое затрачивается на построение дерева, называется временем разрешения конфликта. Для базового алгоритма число вершин в ДРК равно времени разрешения конфликта. Обозначим через т случайную величину, равную времени разрешения конфликта. Условное математическое ожидание

Тк = Е[т\разрешается конфликт кратности к ]

будем называть средним временем разрешения конфликта кратности к.

В разделе сначала приводится известный результат для базового алгоритма. Если R - значение скорости некоторого блокированного алгоритма, то в работах Б.С.Цыбакова было показано, что справедливы следующие оценки

к к liminf — < R < limsup —. (1)

к-юс Тк к—*ос ¿к

Известно, что в асимптотике для базового алгоритма справедливо равенство

¥ = 1^2) + Asin(27rlog2 + + °Ф' (2)

где А = 3.127 • Ю-6, ф = 0.9826.

Из (2) и (1) непосредственно следует

(m+A)"<Jii<(bW-A)"' (3)

где Яь - скорость базового алгоритма. Таким образом

2

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

- формулируется правило установления соответствия между вершинами ДРК и числом окон в сеансе разрешения конфликта;

- на основе сопоставления этого правила с аналогичным правилом для базового алгоритма устанавливается соотношение между средним временем разрешения конфликта для базового и исследуемого алгоритма;

- с использованием соотношения (1) вычисляются оценки для скорости алгоритма.

Для классической модели установлено, что при любом к > 1 среднее время разрешения конфликта Т[ для модифицированного алгоритма и среднее время разрешения конфликта Тк для базового алгоритма связаны соотношением

Обозначим скорость модифицированного алгоритма через Rf. С использованием (1) и (5) для Л/ вычислены верхняя и нижняя оценки, на основании которых получено приближенное значение

Затем в разделе исследуется работа базового алгоритма в условиях описанного в первом разделе расширения классической модели на случай канала, в котором воздействие шума может приводить к возникновению ложных конфликтов. Доказано, что для базового алгоритма при любом к > 1 среднее время разрешения конфликта Т" для канала с шумом и среднее время разрешения конфликта для бесшумного канала связаны соотношением

(5)

грп I 1 грп _ 1

т£ = Тк-^—- + ЦТ? -1?) +

где

rpTL __^

° ~ l-2ç0'

rrm = 1 - 2g0 + qi

1 (1 — gj)(l — 2ço) '

где qo и qi - вероятности ложного конфликта для пустого окна и окна, в котором передавал один абонент. Обозначим скорость базового алгоритма в канале с шумом через Rbn- Для Щп вычислены верхняя и нижняя оценки, на основании которых получено приближенное значение

_ 1 — 2gp / 1 2(gi-g0) N"1

1-go \Rb + {l-qi)(l-q0)j ■

Далее, в рамках введенного в первом разделе расширения классической модели для учета функционирования процедуры последовательной компенсации конфликтных сигналов, выполняется анализ ранее известного алгоритма. При анализе этого алгоритма строится дерево разрешения конфликта, полностью идентичное дереву для базового алгоритма. Отличается только способ установления соответствия между нижними вершинами дерева и окнами. Кроме того, каждой вершине с пометкой С ставится в соответствие некоторое значение суммарного сигнала. Это значение либо определяется непосредственно на основе принятого из канала сигнала, либо вычисляется. Соответствие между вершинами дерева и окнами, а также способ вычисления значения сигнала задаются следующим образом. Пусть окну t соответствует верхняя вершина. Введем следующие обозначения:

V(P) - значение сигнала, соответствующего вершине Р;

Peur ~ вершина, соответствующая текущему окну i;

Ptmp - смежная с вершиной Рсиг нижняя вершина;

Pprev ~ вершина, для которой вершины Рсиг и Ptmp являются потомками.

Отметим, что с учетом введенных выше обозначений вершина Pprev имеет пометку С.

Опишем ситуации, которые могут возникать в окне t.

Ситуация 1. Если в окне t вершина Рсиг получает пометку С, то в этом окне пометка вершины Ptmp не производится. В окне t +1 текущей вершиной становится верхний потомок вершины PCUr-

Ситуация 2. Если в окне t вершина Рсиг получает пометку Е (см. рисунок 2, а), то в этом же окне вершина Ptmp получает пометку С и У {Ptmp) '■— V (Pprev). В окне i+1 текущей вершиной становится верхний ПОТОМОК верШИНЫ Ptmp-

Ситуация 3. Если в окне t вершина Рсиг получает пометку S (см. рисунок 2, б), то применительно к вершине Pprev выполняются действия:

Действие 1. Вычисляется Vtmp = V(Pwev) — V(PCUr)-

Окно t

Рисунок 2. Пометка вершин и вычисление значений сигналов в ДРК для алгоритма с компенсацией конфликтных сигналов: а - в окне t вершина Рсиг получает пометку Е; б - в окне t вершина Рсиг получает пометку S

Действие 2. Анализируется значение 14тр. Если Ц_тр соответствует успешно принятому пакету или конфликту, то в этом же окне вершина Р1тр получает пометку 3 или С соответственно.

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

Действие 3. Устанавливаются значения сигналов для вершин Рргеи и Рьтр У(Рэгеу) ~ ^¿пгр> У{Ршр) — ^шр-

Действие 4. Если УЬпр соответствует успешно принятому пакету, то вершина Рргеу временно рассматривается как текущая. Применительно к этой вершине, смежной вершине, и вершине, для которой данные две вершины являются потомками, применяются три вышеописанных действия (т.е. выполняется «просмотр» дерева от этой вершины в направлении корня, в ходе которого могут получить пометки некоторые нижние вершины). Если 1/гтр соответствует конфликту, то в окне £ + 1

текущей вершиной становится верхний потомок вершины Р(тр.

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

тсотр = + ^ (7)

где Т^отр - среднее время разрешения конфликта для алгоритма с компенсацией конфликтных сигналов.

Используя предыдущее равенство и (1), получаем следующие оценки для скорости модифицированного алгоритма:

+ И <(т~12А) ■ (8)

Для реализации алгоритма с компенсацией конфликтных сигналов требуется иметь неограниченную память. Кроме того, данный алгоритм неустойчив к ошибкам, которые могут возникать при компенсации конфликтных сигналов. В диссертационной работе предложен алгоритм, свободный от этих недостатков. Основная идея алгоритма состоит в том, что разрешается компенсировать только один конфликтный сигнал. По сравнению с исходным алгоритмом изменяются действия в Ситуации 1 и Ситуации 3. Данный алгоритм будем называть алгоритмом с компенсацией одного конфликтного сигнала, а скорость этого алгоритма обозначим через ЯСотрУ- Для ЯСОтр1 вычислены верхняя и нижняя оценки, на основании которых получено приближенное значение

д „_2М2)_

ясотр1 ~ 2 + 9с + ь (2)(1 _ (9с _ 9в)0> 721)' ^

где д, и дс - вероятность ошибки восстановления после компенсации успешно принятого сигнала и конфликтного сигнала соответственно.

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

В третьем разделе диссертационной работы рассматриваются алгоритмы случайного множественного доступа для двоичной обратной связи вида «УСПЕХ» - «НЕУСПЕХ».

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

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

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

Абонент, наблюдая выход канала, к концу окна достоверно определяет, был успех в канале или нет (т.е. абонент не может отличить событие «КОНФЛИКТ» от события «ПУСТО»).

Сначала рассматривается алгоритм, при работе которого допускаются потери пакетов. Этот алгоритм является модификацией древовидного алгоритма. Показано, что при низких интенсивностях входного потока потери пакетов незначительны. Большая часть раздела посвящена случаю, когда потери пакетов не допускаются. Для этого случая предложен класс алгоритмов, который в работе назван классом алгоритмов с отложенными интервалами. Подробно исследован «простейший» алгоритм из этого класса. Опишем этот алгоритм.

Как и для классической модели, алгоритм задается функцией А{х, в{Ь), При этом, в отличие от классической модели элемен-

ты вектора £>(£) = (01,..., в(), описывающие последовательность событий в канале, принимают следующие значения: в{ — ¿>, если окно г содержит успешную передачу, и — N5 - в противном случае.

Каждый из абонентов вычисляет эту функцию в два этапа.

1. Все абоненты на основе истории канала в(Ь — 1) к началу окна Ь одинаковым образом выбирают на временной оси некоторое множество В(Ь) и число ^ € [0,1].

2. Каждый абонент принимает индивидуальные решения о передаче пакета в окне Если х 6 В{£), то пакет х передается в окне t с вероятностью р£, иначе пакет не передается (с вероятностью единица).

При описании алгоритма будем пользоваться следующей терминологией. Моментам возникновения пакетов будем ставить в соответствие точки на временной оси - пакету х ставится в соответствие точка с координатой х. Если пакет успешно передан, то соответствующая точка удаляется. Если к началу окна £ выбрано подмножество временной оси В(£) — В и число р£ = р, то будем говорить, что множество В просматривается с вероятностью р в окне 1 Для краткости при р — 1 будем говорить, что множество просматривается, и только при р < 1 будем указывать, что множество просматривается с вероятностью р. Если множество В просматривается, то при <?(£) — 5 оно оказывается просмотренным, и частично просмотренным - в противном случае (т.е. при 9(1) — ИБ). Объединение просмотренных множеств является

просмотренным множеством, т.е. если некоторое множество В является таковым к концу окна то это означает, что все пакеты, которые возникли в моменты времени из этого множества, получили успешную передачу в окне £ или ранее, и покинули систему.

Используя вышевведенную терминологию, опишем функционирование алгоритма. Все время работы разбито на сеансы. Временная ось делится на (полу)интервалы длины А + В, где числа А и В являются параметрами алгоритма. Сеанс с номером 0 завершается в момент времени 0. Сеанс с номером к начинается с просмотра интервала [(& — 1 )(А + В),к(А + В)). При к > 1 обозначим через вк и ей моменты, соответственно, начала и окончания А'-го сеанса. При завершении очередного сеанса (скажем, с номером к — 1) следующий (/с-й) сеанс начинается сразу же (.вк = с^-х), если е^-х > к(А + В). В противном случае происходит «простой» (интервалы не просматриваются, пакеты не передаются) в течение \(к(А + В) - е^._1)] окон и после этого к-й сеанс начинает работу, т.е. вь = вк-х + \(к(А + В) - еь_х)], где [.] -ближайшее целое сверху.

В каждом очередном сеансе, например с номером к > 1, выполняются следующие действия:

Шаг 1. В окне в к + 1 просматривается интервал времени [(А — 1)(А + В), к(А + В)), который ранее не просматривался и состоит из двух последовательных непересекающихся интервалов с длинами А и В соответственно. В дальнейшем для краткости исходный интервал длины А+В и интервалы с длинами А гг В будем называть интервалом А + В, интервалом А и интервалом В соответственно.

Если в(вк + 1) = 5, то интервал А + В становится просмотренным, и сеанс заканчивается, иначе выполняется Шаг 2.

Шаг 2. В окне 5^+2 просматривается интервал А. Если в результате просмотра в(вк + 2) = N3, то весь интервал А + В ставится в очередь отложенных интервалов, и сеанс заканчивается.

В противном случае интервал А становится просмотренным, из чего следует, что интервал В непуст.

При этом есть три возможности:

Шаг 2.1. Если отложенных интервалов нет в наличии, то процедура просмотра непустого множества применяется к интервалу В. По завершении работы процедуры просмотра непустого множества интервал В оказывается просмотренным (и удаляется из дальнейшего рассмотрения), и сеанс завершается.

Шаг 2.2. Если есть только один отложенный интервал, то интервал В объединяется с отложенным интервалом, и затем к этому объединению применяется процедура просмотра непустого множества, описанная ниже. По завершении работы процедуры просмотра непустого множества как интервал В, так и присоединенный к нему интервал оказываются просмотренными (и удаляются из последующего рассмотрения), и сеанс завершается.

Шаг 2.3. Если есть более одного отложенного интервала, то интервал В объединяется с первыми двумя из отложенных интервалов, и затем к этому объединению применяется процедура просмотра непустого множества, описанная ниже. По завершении работы процедуры просмотра непустого множества как интервал В, так и присоединенные к нему два интервала оказываются просмотренными (и удаляются из последующего рассмотрения), и сеанс завершается.

Осталось описать процедуру просмотра непустого множества.

Применительно к некоторому множеству V, про которое известно, что оно не пусто, эта процедура состоит в выполнении следующих действий. Полагаем V = Ц>.

Действие 1. Множество Ц) просматривается с вероятностью единица. Если при этом происходит 5, то множество Уо оказывается просмотренным и процедура завершена. В противном случае переходим к Действию 2.

Действие 2. Множество Ц> просматривается с вероятностью а. Если событие в канале ЛГ5, то Действие 2 повторяется снова - до тех пор, пока не произойдет событие 5. Это означает, что был успешно передан пакет, который появился в некоторый момент времени х 6 Уо-Точка х удаляется из множества Ц). Устанавливаем Уо := У0 \ {х} и переходим снова к Действию 1.

Здесь а 6 (0,1) - параметр процедуры просмотра непустого множества.

Описанный выше алгоритм задается пятью параметрами:

- длинами интервалов А ж В;

- параметрами «о, «1 и аг, которые используются в процедуре просмотра непустого множества на Шагах 2.1, 2.2 и 2.3, соответственно. Индекс у параметра а показывает, сколько интервалов извлекается из очереди.

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

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

- Вводится в рассмотрение последовательность векторов (Игк,Як), где - длина непросмотренного интервала входного потока и С}к -количество отложенных интервалов в момент окончания сеанса с номером к.

-Доказывается, что последовательность (IV^, <5ь) является вложенной двухмерной марковской цепью и второе измерение С}к также является цепью Маркова.

- Вычисляется стационарное распределение этой одномерной марковской цепи (¿к-

- Исследуется работа процедуры просмотра непустого множества интервалов и вычисляется среднее время работы этой процедуры.

- На основе стационарного распределения одномерной марковской цепи и среднего времени работы процедуры просмотра непустого множества вычисляется средняя длина сеанса.

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

где Т(а,Ь, ао,а1,аг) - средняя длина сеанса при интенсивности входного потока равной единице и фиксированных параметрах алгоритма а,Ь (длины интервалов), «о, «ь а-2 (вероятности передачи, которые используются в процедуре просмотра непустого множества). При этом супремум берется по всем возможным значениям ао,оц,а2, лежащим в интервале (0,1), и неотрицательным значениям параметров а,Ь, для

В диссертационной работе описывается способ решения оптимизационной задачи (10) и показывается, что пропускная способность приведенного выше алгоритма равна 0,3098. Предложенный в разделе метод вычисления пропускной способности обобщается на весь класс алгоритмов с отложенными интервалами. В результате этого обобщения устанавливается, что в данном классе существует алгоритм с пропускной способностью 0,318, и данное значение является конструктивной нижней оценкой для пропускной способности системы СМД с таким видом обратной связи. При этом высказывается гипотеза, что верхняя граница для пропускной способности равна е-1.

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

(10)

1 - Ье~а~ь

- Ъе~а~ь - ае~а 2ае-°(1 - е~ь)

< 1.

которых

В четвертом разделе рассматривается использование адресов абонентов при разрешении конфликтов.

В современных сетях возрастает удельный вес трафика, для которого критична задержка. При использовании чисто случайного механизма для разрешения конфликтов задержка может достигать сколь угодно большой величины, что делает недопустимым использование этих механизмов для передачи такого трафика. Хотя уже в семидесятых годах двадцатого века описывались алгоритмы СМД, которые основаны на использовании адресов абонентов для разрешения конфликтов и гарантируют разрешение конфликта за заданное время, такие алгоритмы к настоящему времени исследованы недостаточно полно, особенно при наличии шумов в каналах. Это делает актуальной задачу исследования и разработки таких алгоритмов, особенно применительно к реальным каналам связи.

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

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

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

- Если абонент передавал в данном окне, то абонент повторяет свою передачу в последующих окнах до того момента, пока его пакет не будет успешно передан. После успешной передачи абонент продолжает работу по обычному алгоритму.

- Если абонент не передавал в данном окне, то абонент наблюдает за выходом канала и продолжает работу по обычному алгоритму, после того как в канале будет иметь место ситуация Е или 5.

Доказано, что скорость алгоритмов не зависит от вероятности ложного конфликта в пустом окне qo и при большом числе абонентов значение скорости приблизительно равно -——, где (h - вероятность лож-

2-<7i

ного конфликта в окне, в котором передавал один абонент.

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

min(fc,21-1)

Tk,i = l + Qk ^,¡№,¡-1+^4,1-1), (11)

¿=max(0,fe—21-1)

где - V ' ;2,\ , Qk = { <7i, к = 1

(fe) l 1Д' > 2.

Рекуррентные вычисления осуществляются с использованием начальных условий:

Т - 1 Т - 1 -io.o — -)-tl,0 — î-■

1 - go 1 - 91

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

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

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

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

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

При построении модели изменим набор допущений классической модели СМД.

Допущение 1. Время работы системы разделяется на равные интервалы времени, длительность каждого из которых соответствует длительности кадра. Кадры нумеруются целыми неотрицательными числами. Интервал резервирования каждого кадра содержит К > 1 равных слотов опроса, предназначенных для передачи запросов. Длительность передачи запроса принимается равной а < 1 единиц времени. Кроме того, кадр содержит Ь > 1 интервалов времени единичной длительности, которые называются окнами и предназначаются для передачи пакетов. Длительность передачи пакета совпадает с длительностью окна. Числа К и Ь полагаются постоянными в течение всего периода времени работы системы. Базовая станция и все абоненты знают моменты начала г-го кадра (г — 1){аК + Ь), ^'-го окна 3 — I + аК х и к-го слота опроса (к - 1)а + Ь х , где 1,2,..., [■] - ближайшее целое,

не превосходящее аргумент.

Допущение 2. Для каждого поступающего в систему пакета генерируется отдельный запрос. Моменты поступления пакетов образуют пуассоновский процесс интенсивности Л пакетов в единицу времени. Каждый абонент, имеющий новый пакет, передает базовой станции запрос для того, чтобы зарезервировать время восходящего канала. Успешная передача запроса в некотором кадре является признаком того, что в одном из последующих кадров будет зарезервировано окно для передачи пакета, который соответствует этому запросу. Для устранения неоднозначности при резервировании в каждом кадре абоненту разрешено делать не более одной попытки передачи запроса.

Допущение 3. В каждом слоте опроса I € {1,2,...,К) кадра с номером (£ — 1) возможно возникновение одного и только одного из следующих событий:

- только один из абонентов передает запрос (в[1> = 1 или 5);

- ни один из абонентов не передает запрос (0^ — 0 или Е)\

- два и более абонента передают запросы одновременно, что приводит к искажению всех передаваемых запросов на БС (0^ = 2 или С).

Допущение 4. К началу каждого ¿-го кадра базовая станция передает всем абонентам по нисходящему каналу информацию о событиях во всех слотах опроса предыдущего кадра (1—1). Эта информация представляет собой вектор обратной связи = (о[1 ^, ..., в[К^).

Допущение 5. Абонент получает от БС информацию обратной связи относительно своих передач в кадре ( — 1 к началу кадра t, т.е. один раз за К слотов опроса.

Модель полностью четырьмя параметрами К, Ь, Л, а и приведена на рисунке 3.

Время

Пакеты передаются в назначенных окнах

Пуассоновский входной поток пакетов

Рисунок 3. Модель централизованной системы случайного множественного доступа с резервированием

По аналогии с классической моделью системы случайного множественного доступа для расширенной модели вводится понятие алгоритма случайного множественного доступа и пропускной способности.

Алгоритмом СМД для централизованной системы с резервированием назовем правило, которое основывается на событиях в слотах опроса предыдущих кадров и используется абонентами в начале очередного кадра для того, чтобы

- определить, передавать ли запрос в каких-либо слотах опроса текущего кадра или отложить его передачу;

- определить, передавать ли пакет в каких-либо окнах текущего кадра или отложить его передачу.

Аналогично классической модели определим А как функцию четырех аргументов.

- Первым аргументом является К - число слотов опроса в кадре.

- Вторым аргументом является х - момент времени, когда пакет был сгенерирован.

- Третьим аргументом является 6(Ь) = (61,62, ■■■, 64) - последовательность векторов обратной связи, известных к началу кадра

- Четвертым аргументом является последовательность векторов и(Ь,х) = (1^1 (х), 1>2(х), ■ • •, связанная с абонентом, который сгенерировал пакет в момент времени х. Компоненты вектора

и^х) — ... ,и[К\х)) принимают следующие значения:

у[1\х) = 0, если абонент, пакет которого был сгенерирован в момент х,

не передавал запрос в 1-й слоте опроса (4 — 1)-го кадра и и^ (х) — 1 - в противном случае.

Областью значений функции А(К,х,6(Ь),и(1,х)) является множество векторов р = (р(1), р(2)1...; длины К, а также множество векторов г = . длины Ь. Каждый элемент пред-

ставляет собой вероятность передачи запроса в г-м слоте опроса 4-го кадра, а каждый элемент г- вероятность передачи пакета в ]-м окне 4-го кадра.

Задержкой пакета в централизованной системе с резервированием 6а(К, Ь, Л) назовем случайную величину, равную интервалу времени с момента возникновения пакета до момента его успешной передачи.

В произвольный момент времени 4 введем в систему дополнительный пакет, задержку которого обозначим через 6д\к, Ь, Л).

Средней задержкой пакета для заданной интенсивности входного потока Л, числа слотов опроса К, числа окон Ь и алгоритма СМД А назовем

ОА(К,Ь,К) ± ИШБИР Е[5{1](К,Ь,К)\. (12)

п—»оо

Скоростью алгоритма А назовем верхнюю грань интенсивностей входного потока, который может быть передан с конечной средней задержкой посредством некоторого алгоритма СМД Л, и некоторой структуры кадра К, Ь:

ЯА(К, Ц 4 вир{Л : Ба{К, Ь, Л) < оо}. (13)

Пропускной способностью централизованной системы СМД с резервированием назовем верхнюю грань скоростей передачи алгоритмов СМД:

C{K,L)± sup Ra(K,L), (14)

A€A{K,L)

где Л (К, L) - множество всех алгоритмов СМД, определенных для системы с К слотами опроса и с L окнами.

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

хТ^с- <15>

где С - пропускная способность классической модели СМД (С < 0.568).

Нижняя оценка пропускной способности построена конструктивным способом. Для этого описан конкретный алгоритм СМД и указан способ вычисления скорости алгоритма в виде некоторой функции от К, L и а. Доказано, что при = эта функция принимает максимальное зна-

R

чение равное, t, где Rpt и 0,4877 - скорость алгоритма дробления для классической модели.

В оставшейся части раздела введенная модель используется как для анализа существующего способа передачи запросов в протоколе IEEE 802.16, так и для выработки предложений по повышению эффективности передачи запросов.

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

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

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

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

. В заключении приведены основные результаты, полученные в диссертационной работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

5. В рамках классической модели установлена связь между скоростью базового алгоритма и скоростью модифицированного алгоритма в бесшумном канале.

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

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

8. Для двоичной связи вида «УСПЕХ» - «НЕУСПЕХ» предложен и исследован класс алгоритмов, обеспечивающий устойчивую работу для этого вида обратной связи.

9. Предложены и исследованы алгоритмы, использующие адреса абонентов для разрешения конфликтов в канале с шумом, который может привести к ложным конфликтам.

10. Выполнено расширение классической модели для случая централизованной системы с резервированием. Для этой модели введено понятие алгоритма случайного множественного доступа и пропускной способности.

11. Для модели централизованной системы с резервированием построены верхняя и нижняя границы для пропускной способности.

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

(статьи 1-18 опубликованы в изданиях, включенных в Перечень ВАК.)

1. Евсеев Г. С., Тюрликов А. М. Анализ пропускной способности одного алгоритма свободного множественного доступа, устойчивого к воздействию шумов // Проблемы передачи информации. — 1986. — Т. 22, № 2. — С. 104-109.

2. Тюрликов А. М., Марковский С. Г. Использование адресов абонентов для организации доступа к высокоскоростному каналу связи / / Информационно-управляющие системы. — 2003. — Т. 1. — С. 32-38.

3. Марковский С. Г., Тюрликов А. М. Использование адресов абонентов для разрешения конфликтов в канале с шумом // Информационно-управляющие системы. —

2006. — Т. 2. — С. 27-37.

4. Андреев С. Д., Семенов С. А., Тюрликов А. М. Методики оценки параметров радиоканала / / Информационно-управляющие системы. — 2007. — Т. 29, № 4. — С. 37-43.

5. Беляев Е. А., Тюрликов А. М., Уханова А. С. Адаптивное арифметическое кодирование в стандарте JPEG2000 // Информационно-управляющие системы. — 2007. — Т. 31. — С. 28-33.

6. Беляев Е. А., Тюрликов А. М. Оценка вероятности появления символа при адаптивном двоичном арифметическом кодировании в задачах сжатия видеоинформации / / Цифровая обработка сигналов. —

2007. — Т. 3. — С. 20-24.

7. Беляев Е. А., Тюрликов А. М. Управление скоростью и ошибкой кодирования в системе сжатия и передачи видеоинформации с ограничениями на память передающего и принимающего устройств / / Компьютерная оптика. — 2007. — Т. 31, № 2. — С. 69-76.

8. Винель А. В., Кобляков В. А., Тюрликов А. М. Класс алгоритмов случайного множественного доступа с очередью для централизованных сетей передачи данных // Информационные технологии. — 2007. — Т. 5. — С. 32-41.

9. Евсеев Г. С., Тюрликов А. М. Взаимосвязь характеристик блокированных стек-алгоритмов случайного множественного доступа // Проблемы передачи информации. — 2007. — Т. 43, № 4. — С. 83-92.

10. Investigation of bandwidth request mechanisras under point-to-multipoint mode of WiMAX networks / Q. Ni, A. Vinel, Y. Xiao, A. Turlikov, T. Jiang // IEEE Communications Magazine. — 2007. — Vol. 45, № 5. — P. 132-138.

11. Андреев С. Д., Нилова А. В., Тюрликов А. М. Использование конкурентного опроса в широкополосных беспроводных сетях // Информационно-управляющие системы. — 2008. — Т. 37, № 6. — С. 44-53.

12. Беляев Е. А., Тюрликов А, М. Алгоритмы оценки движения в задачах сжатия видеоинформации на низких битовых скоростях // Компьютерная оптика.— 2008.— Т. 32, № 3. — С. 403-413.

13. Марковский С. Г., Тюрликов А. М. Использование идентификаторов абонентов для резервирования канала множественного доступа / / Информационно-управляющие системы. — 2008. — Т. 2. — С. 28-35.

14. Марковский С. Г., Тюрликов А. М. Использование адресов абонентов для разрешения конфликтов при передаче запросов к базовой станции / / Вопросы радиоэлектроники. Серия: Системы и средства отображения информации и управления специальной техникой. — 2008. — Т. 1. — С. 119-126.

15. Андреев С. Д., Пустовалов Е. В., Тюрликов А. М. Древовидный алгоритм разрешения конфликта, устойчивый к неполному погашению интерференции // Автоматика и телемеханика. — 2009. — Т. 3. — С. 78-96.

16. Винелъ А. В., Тюрликов А. М., Федоров К.

A. Использование последовательного погашения интерференции при организации случайного множественного доступа в централизованных сетях // Информационно-управляющие системы.— 2009.— Т. 2.— С. 46-55.

17. Тюрликов А. М., Фосс С. Г. Об эргодических алгоритмах в системах случайного множественного доступа с обратной связью «успех-неуспех» // Проблемы передачи информации. — 2010. — Т. 46, № 2. — С. 91-109.

18. Анализ алгоритмов распространения тревожного сообщения с глобальным знанием в беспроводных сетях передачи данных с линейной топологией / Винель А.

B., Дудин А. Н., Андреев С. Д., Тюрликов А. М. // Информационно-управляющие системы. — 2010. — Т. 3. —

C. 56-60.

19. Andreev S., Dubkov К., Turlikov A. IEEE 802.11 and 802.16 coopération within multi-radio stations / / Wireless Personal Communications Journal (WIRE). - 2010.

20. Capacity analysis of reservation-based random access for broadband -wireless access networks / A. Vinel, Q. Ni, D. Staehle, A. Turlikov / / IEEE Journal on Selected Areas in Communications. — 2009. — Vol. 27, №2.-P. 172-181.

21. Евсеев Г. С., Тюрликов A. M. Оценка эффективности одного класса

алгоритмов случайного доступа к системе из двух каналов // VIII симпозиум по проблеме избыточности в информационных системах. - № 2. - 1983. - С. 15-17.

22. Евсеев Г. С., Тюрликов А. М. Алгоритм свободного множественного доступа, устойчивый к воздействию шумов // IX Всесоюзная школа-семинар по вычислительным сетям. — Т. 3. — 1984. — С. 150— 153.

23. Тюрликов А. М. Анализ вариантов использования параллельных каналов в системе со свободным доступом //IX Всесоюзная школа-семинар по вычислительным сетям. — № 3.1. — 1984. — С. 198-201.

24. Евсеев Г. С., Тюрликов А. М. Алгоритмы случайного доступа к системе параллельных каналов с зависимым шумом // X Всесоюзная школа-семинар по вычислительным сетям. — № 2,1985. - С. 18-23.

25. Тюрликов А. М. Численные оценки для вероятностно-временных характеристик стек-алгоритма множественного доступа // X Всесоюзная школа-семинар по вычислительным сетям.— № 1.— 1985.-С. 188-191.

26. Евсеев Г. С., Тюрликов А. М. Стек-алгоритм в системе с узкополосными каналами // IX симпозиум по проблеме избыточности в информационных системах. — Т. 4. — 1986. — С. 159-162.

27. Евсеев Г. С., Тюрликов А. М. Уменьшение задержки при передаче копий пакета в канале СМД // IX симпозиум по проблеме избыточности в информационных системах. — Т. 4. — 1986. — С. 163-166.

28. Малков А. Ю., Тюрликов А. М. Алгоритм случайного множественного доступа в канале с асинхронным шумом // XI Всес. семинар по вычисл. сетям. — М.-Рига: 1986. — Т. 1. — С. 166-169.

29. Малков А. Ю., Тюрликов А. М. Один подход к описанию древовидных алгоритмов множественного доступа //I Всесоюзная конференция по информационным системам множественного доступа. - 1989. - С. 166-169.

30. Малков А. Ю., Тюрликов А. М. Варианты организации передачи «нетерпеливых» пакетов в системе с СМД //X симпозиум по проблеме избыточности в информационных системах. — 1989. — С. 193-195.

31. Evseev G., Turlikov A. The multiple-random-access algorithms analysis based on tree properties // 5th Joint Soviet-Swedish International Workshop on Information Theory. — 1991.

32. Malkov A. Y., Turlikov A. M. Random-access communication with success-failure feedback // Proc. of the 6th Joint Swedish-Russian International Workshop on Information Theory. — 1993. — P. 107-111.

33. Malkov A., Turlikov A. Random multiple access protocols for commu-

nication systems with «success-failure» feedback // Proc. of the IEEE International Workshop on Information Theory. — 1995. — P. 39.

34. Turlikov A., Markovsky S. Improved blocked algorithm in the channel of multiple access with false conflicts // Proc. of the International Symposium on Problems of Modular Information Systems and Networks (ISC-NET'97). - St-Petersburg: 1997. - P. 31-32.

35. Performance analysis of the random access in IEEE 802.16 / A. Vinel, Y. Zhang, M. Lott, A. Tiurlikov // Proc. of the 16th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications. — Vol. 3. - 2005. - P. 1596-1600.

36. Kobliakov A., Turlikov A., Vinel A. Distributed queue random multiple access algorithm for centralized data networks // Proc. of the 10th IEEE International Symposium on Consumer Electronics (ISCE'06). — St,-Petersburg, Russia: 2006. - P. 290-295.

37. Turlikov A., Vinel A. Capacity estimation of centralized reservation-based random multiple-access system // Proc. of the XI International Symposium on Problems of Redundancy in Information and Control Systems. - 2007. - P. 154-160.

38. Andreev S., Turlikov A., Vinel A. Performance analysis of a high-speed ultra-wideband WPAN MAC // Proc. of the 14th International Conference on Analytical and Stochastic Modeling Techniques and Applications. - 2007. - P. 44-49.

39. Andreev S., Turlikov A., Vinel A. Contention-based polling efficiency in broadband wireless networks // Proc. of the 15th International Conference on Analytical and Stochastic Modeling Techniques and Applications. - 2008. - P. 295-309.

40. Andreev S., Dubkov K., Turlikov A. IEEE 802.11 and 802.16 cooperation within multi-radio stations // Proc. of the 11th International Symposium on Wireless Personal Multimedia Communications. — 2008.

41. Andreev S., Pustovalov E., Turlikov A. SICTA modifications with single memory location and resistant to cancellation errors // Proc. of the 8th International Conference on Next Generation Teletraffic and Wired/Wireless Advanced Networking. - 2008. - P. 13-24.

42. Overall delay in IEEE 802.16 with contention-based random access / S. Andreev, Zs. Saffer, A. Turlikov, A. Vinel // Proc. of the 16th Conference oil Analytical and Stochastic Modeling Techniques and Applications. - 2009. - P. 89-102.

Формат 60x84 1/16. Бумага офсетная. Усл. печ. л. 1,9. Тираж 100 экз. Заказ № 100 Отпечатано в Редакционно-издательском центре ГУАП 190000, Санкт-Петербург, ул. Б. Морская, 67

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

Введение

1. Модели систем со случайным множественным доступом абонентов в общий канал связи

1.1 Вводные замечания и классификация систем множественного доступа.

1.2 Развитие методов СМД и актуальные задачи теории и практики применения методов СМД.

1.3 Классическая модель СМД.

1.3.1 Принцип построения классической модели.

1.3.2 Система связи.

1.3.3 Канал связи.

1.3.4 Обратная связь.

1.3.5 Абонент.

1.3.6 Классические модели СМД.

1.4 Понятие и характеристики алгоритма СМД, пропускная способность системы СМД.

1.5 Описание алгоритмов для классической модели.

1.5.1 Общие замечания по классификации алгоритмов СМД

1.5.2 Алгоритмы АЛОХА и ДЭО.

1.5.3 Базовый и модифицированный древовидные алгоритмы

1.6 Разнообразие моделей систем со случайным множественным доступом в канал.

1.6.1 Классическая модель системы СМД как основа для построения моделей и исследования реальных систем.

1.6.2 Изменение модели относительно абонента для учета особенностей реальных потоков.

1.6.3 Уточнение понятия алгоритма СМД.

1.6.4 Изменение модели относительно канала связи для учета шумов в канале связи.

1.6.5 Учет различных видов обратной связи в модели.

1.7 Базовый и модифицированный алгоритмы с компенсацией конфликтных сигналов.

1.8 Заключительные замечания.

2. Методы анализа характеристик древовидных алгоритмов разрешения конфликтов

2.1 Роль древовидных алгоритмов разрешения конфликта в развитии теории случайного множественного доступа

2.2 Вычисление оценок скорости для базового алгоритма разрешения конфликта.

2.3 Использование свойств базового алгоритма разрешения конфликта для анализа характеристик блокированных алгоритмов и основное свойство дерева разрешения конфликтов.

2.4 Вычисление скорости алгоритма для канала с шумом.

2.5 Вычисление скорости для алгоритмов с компенсацией конфликтных сигналов.

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

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

2.6 Неблокированные древовидные алгоритмы и анализ их характеристик

2.7 Выводы по разделу.

3. Случайный множественный доступ при двоичной обратной связи успехнеуспех

3.1 Обеспечение устойчивой работы системы при двоичной обратной связи успех-неуспех - одна из открытых проблем теории случайного множественного доступа

3.2 Модель системы.

3.3 Неблокированный стек-алгоритм в системе с обратной связью типа успех-неуспех.

3.3.1 Описание работы алгоритма.

3.3.2 Вычисление скорости алгоритма и средней виртуальной задержки

3.4 Алгоритмы СМД с отложенными интервалами

3.4.1 Частный случай алгоритма.

3.4.2 Класс алгоритмов доступа с отложенными интервалами

3.5 Пропускная способность алгоритма.

3.5.1 Уточнение пон51тия скорость и пропускная способность

3.5.2 Изменение масштаба времени и марковская цепь, описывающая функционирование алгоритма.

3.5.3 Вероятности событий в сеансе.

3.5.4 Вложенная цепь Маркова.

3.5.5 Просмотр непустого множества.

3.5.6 Средняя длительность сеанса.

3.5.7 Условия положительной возвратности и эргодичности

3.6 Вычисление значения пропускной способности алгоритма и обобщение результатов на весь класс алгоритмов с отложенными интервал ами.

3.7 Расширение класса алгоритмов.

3.8 Выводы по разделу.

4. Использование адресов абонентов при разрешении конфликтов

4.1 Использование адресов абонентов при разрешении конфликтов как альтернатива чисто случайным механизмам разрешения конфликтов.

4.2 Модель системы и уточнение понятия скорости.

4.2.1 Особенности классической модели для случая конечного числа абонентов.

4.2.2 Дисциплины работы абонентов с очередью

4.2.3 Модель с двухпакетной очередью.

4.2.4 Понятие скорости алгоритма доступа для системы с конечным числом абонентов

4.3 Методы анализа систем СМД при использовании адресов абонентов для разрешения конфликтов.

4.3.1 Алгоритмы СМД для канала без шума.

4.3.2 Случайные процессы, описывающие поведение системы

4.3.3 Определение скорости алгоритмов.

4.3.4 Метод расчета средней задержки.

4.3.5 Алгоритм расчета средней задержки и результаты расчета

4.4 Алгоритмы, использующие адреса абонентов для разрешения конфликтов в канале с шумом.

4.4.1 Алгоритмы доступа для канала с шумом.

4.4.2 Расчет скорости для канала с ложными конфликтами.

4.4.3 Расчет средней задержки для канала с шумом.

4.4.4 Средняя длина сеанса.

4.4.5 Распределение длины сеанса.

4 4.6 Среднее время выхода.

4.4.7 Результаты расчета средней задержки.

4.5 Выводы по разделу.

5. Организация случайного доступа в централизованных сетях передачи данных

5.1 Особенности организации множественного доступа в централизованных сетях передачи данных.

5.2 Расширение классической модели на случай централизованной системы.

5.3 Обобщение понятия и характеристик алгоритма СМД, пропускная способность централизованной системы СМД с резервированием

5.4 Оценка пропускной способности централизованной сети.

5.5 Общее описание централизованных телекоммуникационных протоколов

5.5.1 Вводные замечания.

5.5.2 Общая структура и эволюционное развитие протокола

5.5.3 Основные особенности протокола.

5.5.4 Известные результаты относительно алгоритма резервирования

5.5.5 Способы предоставления канальных ресурсов.

5.6 Анализ и предложения по улучшению централизованных телекоммуникационных протоколов

5.6.1 Анализ существующего протокола.

5.6.2 Предложения по улучшению протокола.

5.7 Использование СМД для повышения эффективности передачи видеоинформации в централизованных сетях передачи данных

5.7.1 Необходимость учета специфики видеоинформации при передаче в централизованных сетях.

5.7.2 Модель системы передачи видеоинформации в нисходящем канале централизованной сети передачи данных.

5.7.3 Постановка задачи выбора параметров кодирования видеоисточника и канала

5.8 Выводы по разделу.

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

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

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

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

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

В соответствии с целью исследования были поставлены следующие основные задачи.

1. Создание методологической основы для исследования систем случайного множественного доступа.

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

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

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

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

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

7. Построение оценок для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с резервированием.

8. Использование предложенных методов и алгоритмов для повышения эффективности функционирования централизованной системы случайного множественного доступа.

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

Научная новизна диссертационной работы заключается в следующем.

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

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

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

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

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

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

7. Впервые построены оценки для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с резервированием.

8. Предложены новые способы повышения эффективности функционирования централизованной системы случайного множественного доступа.

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

Теоретические и практические результаты работы использованы в учебном процессе кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения. Результаты работы используются в разработках ЗАО «Интел А/О». Использование результатов подтверждено соответствующими актами.

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

- Всесоюзных школах-семинарах по .вычислительным сетям (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. Алгоритмы случайного множественного доступа, использующие адреса абонентов для разрешения как подлинных, так и ложных конфликтов.

5. Модель централизованной системы случайного множественного доступа с резервированием.

6. Оценки для показателей производительности (пропускной способности) централизованной системы случайного множественного доступа с ре1 зервированием.

Структура и объем работы. Диссертационная работа состоит из введения, пяти разделов, заключения, списка использованных источников и пяти приложений. Работа содержит 255 страниц основного машинописного текста, 60 рисунков и 8 таблиц. Список литературы включает 178 наименований.

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

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

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

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

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

5. В рамках классической модели установлена связь между скоростью базового алгоритма и скоростью модифицированного алгоритма в бесшумном канале.

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

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

8. Для двоичной связи вида «УСПЕХ» - «НЕУСПЕХ» предложен и исследован класс алгоритмов, обеспечивающий устойчивую работу для этого вида обратной связи.

9. Предложены и исследованы алгоритмы, использующие адреса абонентов для разрешения конфликтов в канале с шумом, который может привести к ложным конфликтам.

10. Выполнено расширение классической модели для случая централизованной системы с резервированием. Для этой модели введено понятие алгоритма случайного множественного доступа и пропускной способности.

11. Для модели централизованной системы с резервированием построены верхняя и нижняя границы для пропускной способности.

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

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

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

Заключение

1. Бертсекас ДГаллагер Р. Сети передачи данных. — М.: Мир, 1989.— 544 с.

2. Rom R., Sidi M. Multiple Access Protocols: Performance and Analysis.— New York: Springer-Verlag, 1990.— 172 p.

3. Kurose J., Schwartz M., Yemini Y. Controlling window protocols for time-constrained communication in multiple access networks // IEEE Transactions on Communications. — 1988. — Vol. 36, № 1. — P. 41-49.

4. Sachs S. Alternative local area network access protocols // IEEE Communications Magazine. — 1988. — Vol. 26, № 3. — P. 25-45.

5. Abramson N. The Aloha system another alternative for computer communications // Proc. of the Fall Joint Computer Conference.— 1970.— P. 281-285.

6. Вероятность и математическая статистика: Энциклопедия / Гл. ред. Ю. В. Прохоров.— М.: Большая Российская Энциклопедия, 1999.— 910 с.

7. Цыбаков Б. С., Михайлов В. А. Свободный синхронный доступ пакетов в широковещательный канал с обратной связью // Проблемы передачи информации. — 1978. — Т. 14, № 4. — С. 32-59.

8. Capetanakis J. Tree algorithms for packet broadcast channels // IEEE Transactions on Information Theory.— 1979.— Vol. 25, № 5.— P. 505515.

9. Massey J. Guest editorial, special issue on random-access communications // IEEE Transactions on Information Theory.— 1985.— Vol. 31, № 2.-P. 117-118.

10. Dimic G., Sidiropoulos N., Zhang R. Medium access control physical cross-layer design // IEEE Signal Processing Magazine. — 2004. — Vol. 21, № 5. - P. 40-50.

11. Chlebus B. Handbook of Randomized Computing / Ed. by P. Pardalos, S. Rajasekaran, J. Reif, and J. Rolim. — Kluwer Academic Publishers, 2001. P. 401-456.

12. IEEE Std 802.16-2004 (Revision of IEEE Std 802.16-2001), New York, USA, October, 2004.

13. Широкополосные беспроводные сети передачи информации / Вишневский В. М., Ляхов А. И., Портной С. Д., Шахнович И.

14. B. — М.: Техносфера, 2005. — 592 с.14. 3GPP TS 36.300 Evolved Universal Terrestrial Radio Access (E-UTRA) and Evolved Universal Terrestrial Radio Access Network (E-UTRAN); Overall description.

15. Евсеев Г. С., Тюрликов A. M. Взаимосвязь характеристик блокированных стек-алгоритмов случайного множественного доступа // Проблемы передачи информации. — 2007. — Т. 43, № 4. —1. C. 83-92.

16. Tsybakov В. Survey of USSR contributions to random multiple-access communications // IEEE Transactions on Information Theory.— 1985.— Vol. 31, № 2.-P. 143-165.

17. Paterakis M., Georgiadis L., Papantoni-Kazakos P. On the relation between the finite and the infinite population models for a class of RAA's // IEEE Transactions on Communications. — 1987. — Vol. 35, № 11. — P. 1239-1240.

18. Гнеденко Б. В. Курс теории вероятностей.— М.: Наука, 1988. — 451 с.

19. Abramson N. The throughput of packet broadcasting channels // IEEE Transactions on Communications.— 1977. — Vol. 25, № 1, — P. 117-128.

20. Kleinrock L., Lam S. Packet switching in a multi-access broadcast channel: Performance evaluation // IEEE Transactions on Communications. — 1975. Vol. 23, № 4. — P. 410-423.

21. Kleinrock L., Lam S. Packet switching in a multi-access broadcast channel: Dynamic control procedures // IEEE Transactions on Communications.— 1975. Vol. 23, № 9. - P. 891-904.

22. Цыбаков Б. С., Михайлов В. А. Эргодичность синхронной системы AJIOXA // Проблелт передачи информации. — 1979. — Т. 15, № 4. — С. 73-87.

23. Цыбаков Б. С. Случайный множественный доступ.— М.: Препринт, Академия наук СССР, 1984. — 64 с.

24. Введенская Н. Д., Цыбаков Б. С. Задержка пакетов при стек-алгоритме множественного доступа // Проблемы передачи информации. — 1984. — Т. 20, № 2. С. 77-97.

25. Foss S. Some open problems related to stability // Erlang Centennial Conference. — 2009.

26. A bound on the capacity of backoff and acknowledgment-based protocols / L. Goldberg, M. Jerrum, S. Kannan, M. Paterson // SI AM Journal on Computing. 2004. - Vol. 33, № 2. - P. 313-331.

27. Ephremides A., Hajek B. Information theory and communication networks: An unconsummated union // IEEE Transactions on Information Theory. — 1998. — Vol. 44, № 6. P. 2416-2434.

28. Цыбаков Б. С., Лиханов Н. Б. Верхняя граница для пропускной способности системы СМД // Проблемы передачи информации.— 1987. — Т. 23, 3. — С. 64-78.

29. Цыбаков В. С., Лиханов Н. Б. Нижняя граница для задержки в системе случайного множественного доступа // Проблемы передачи информации. — 1991. — Т. 27, № 3. — С. 73-88.

30. Цыбаков Б. С., Михайлов В. А. Случайный множественный доступ пакетов. Алгоритм дробления // Проблемы передачи информации. — 1980. — Т. 16, № 4. С. 65-79.

31. Михайлов В. А. Адаптивный случай доступа в широковещательный канал. — М.: Наука, 1980,— С. 80-94.

32. Михайлов В. А. Геометрический анализ устойчивости цепей Маркова в г" и его приложение к вычислению пропускной способности адаптивного алгоритма случайного множественного доступа / / Проблемы передачи информации.— 1988.— Т. 24, № 1. — С. 61-73.

33. Цыбаков Б. С. Новые алгоритмы случайного многостанционного доступа. Вопросы кибернетики. Надежность информационного обмена в вычислительных сетях // М.: АН СССР Научный совет по комплексной проблеме «Кибернетика». — 1980. — Т. 1. — С. 122-140.t

34. Metcalfe R., Boggs D. Ethernet: Distributed packet switching for local computer networks // Communications of the ACM. — 1976. — Vol. 19, jY- 7. — P. 395-404.

35. Введенская Н. Д., Пинскер М. С. Оценка пропускной способности алгоритмов множественного доступа класса FCFS // Проблемы передачи информации. — 1990. — Т. 26, № 1.— С. 58-67.

36. Фалин Г. И. Оценка эффективности одного класса алгоритмов случайного множественного доступа в радиоканал // Проблемы передачи информации. — 1982. — Т. 18, № 3. — С. 85-90.

37. Mathys P., Flajolet P. Q-ary collision resolution algorithms in random-access systems with free or blocked channel access // IEEE Transactions on Information Theory. — 1985. — Vol. 31, № 2. — P. 217-243.

38. Kelly F. Stochastic models of computer communication systems // Journal of the Royal Statistical Society. — 1985. — Vol. 47. — P. 379-395.

39. Aldous D. Ultimate instability of exponential back-off protocol for acknowledgment based transmission control of random access communication channels // IEEE Transactions on Information Theory. — 1987.— Vol. 33, № 2. — P. 219-223.

40. Lam S. Packet Switching in a Multi-Access Broadcast Channel with Application to Satellite Communication in a Computer Network: Ph.D. thesis / University of California, Los Angeles. — 1974.

41. IEEE Std 802.11-2007, New York, USA, June, 2007.

42. IEEE Std 802.16e-2005, New York, USA, February 2006.

43. Hajek В., van Loon T. Decentralized dynamic control of a multiaccess broadcast channel // IEEE Transactions on Automatic Control. — 1982. — Vol. 27. P. 559 - 569.

44. Massey J. Multiuser Communication Systems / Ed. by G. Longo.— Springer-Verlag, New York, 1981.— Vol. CISM Courses and Lectures.— P. 73-137.

45. Евсеев Г. С., Ермолаев Н. Г. Оценки характеристик разрешения конфликтов в канале со свободным доступом и шумом // Проблемы передачи информации. — 1982. — Т. 18, № 2. — С. 101-105.

46. Цыбаков Б. С. Рандомизированные и нерандомизированные алгоритмы случайного множественного доступа // Проблемы передачи информации. — 1989. — Т. 25, № 1. — С. 88-99.

47. Малков А. Ю., Тюрликов А. М. Один подход к описанию древовидных алгоритмов множественного доступа // I Всесоюзная конференция по информационным системам множественного доступа. — 1989. — С. 166— 169.

48. Blondia С. A discrete-time batch Markovian arrival process as B-ISDN traffic model // Belgian Journal of Operations Research, Statistics and Computer Science. — 1993. — Vol. 32. — P. 3-23.

49. Коваленко И. H. Итоги науки. Сер. Теор. вероятн. Мат. стат. Теор. кибернет.- М.: ВИНИТИ, 1971, — С. 5-109

50. Сох D. The analysis of non-markovian stochastic processes // Proceedings of the Cambridge Philosophical Society. — 1955. — Vol. 51, № 3. — P. 433-441.

51. Хименко В.И. Характеристики типа «превышений уровней» для случайных точечных процессов // Радиотехника и электроника.— 2000. Т. 45, № 4. - С. 436-443.

52. Хименко В. И., Тигин Д. В. Статистическая акустооптика и обработка сигналов. — СПб.: Изд-во СПб ун-та, 1996. — 291 с.

53. Blondia С., Casals О. Statistical multiplexing of VBR sources: A matrix-analytic approach // Performance Evaluation. — 1992. — Vol. 16. — P. 5-20.

54. Houdt В., Blondia C. Robustness of Q-ary collision resolution algorithms in random access systems // Performance Evaluation. — 2004. — Vol. 57, № 3. P. 357-377.

55. Houdt В., Blondia C. Stability and performance of stack algorithms for random access communication modeled as a tree structured QBD Markov chain // Stochastic Models. 2001. - Vol. 17, № 3.- P. 247-270.

56. Houdt В., Blondia C. Throughput of Q-ary splitting algorithms for contention resolution in communication network // Communications in Information and Systems.— 2005. — Vol. 4, № 2. — P. 135-164.

57. Введенская H. Д., Цыбаков Б. С. Случайный множественный доступ пакетов в канал с ошибками // Проблемы передачи информации. — 1983. Т. 19, № 2. - С. 52-68.

58. Ермолаев Н. Г. Алгоритм случайного доступа адаптивная AJIOXA в канале с шумом // VIII симпозиум по проблеме избыточности в информационых системах. — Т. 2. — 1983. — С. 18-21.

59. Евсеев Г. С., Тюрликов А. М. Алгоритм свободного множественного доступа, устойчивый к воздействию шумов //IX Всесоюзная школа-семинар по вычислительным сетям. — Т. 3. — 1984. — С. 150-153.

60. Евсеев Г. С., Тюрликов А. М. Анализ пропускной способности одного алгоритма свободного множественного доступа, устойчивого к воздействию шумов // Проблемы передачи информации.— 1986.— Т. 22, № 2. С. 104-109.

61. Цыбаков Б. С., Лиханов Н. Б. Верхняя граница для пропускной способности системы случайного множественного доступа пакетов в канал с ошибками // Проблемы передачи информации. — 1989. — Т. 25, № 4. С. 50-62.

62. Малков А. Ю., Тюрликов А. М. Алгоритм случайного множественного доступа в канале с асинхронным шумом // XI Всес. семинар по вычисл. сетям. — М.-Рига: 1986. — Т. 1.— С. 166-169.

63. Цыбаков Б. С., Михайлов В. А., Федорцов С. П. Учет времени распространения пакетов при случайном множественном доступе // Проблемы передачи информации. — 1981. — Т. 17, № 2. — С. 75-78.

64. Евсеев Г. С., Тюрликов А. М. Оценка эффективности одного класса алгоритмов случайного доступа к системе из двух каналов // VIII симпозиум по проблеме избыточности в информационных системах. — № 2. 1983. - С. 15-17.

65. Тюрликов А. М. Анализ вариантов использования параллельных каналов в системе со свободным доступом //IX Всесоюзная школа-семинар по вычислительным сетям. — № 3.1. — 1984. — С. 198-201.

66. Евсеев Г. С., Тюрликов А. М. Алгоритмы случайного доступа к системе параллельных каналов с зависимым шумом //X Всесоюзная школа-семинар по вычислительным сетям. — № 2. — 1985. — С. 18-23.

67. Евсеев Г. С., Тюрликов А. М. Стек-алгоритм в системе с узкополосными каналами //IX симпозиум по проблеме избыточности в информационных системах. — Т. 4. — 1986. — С. 159-162.

68. Евсеев Г. С., Тюрликов А. М. Уменьшение задержки при передаче копий пакета в канале СМД //IX симпозиум по проблеме избыточности в информационных системах. — Т. 4. — 1986.' — С. 163-166.

69. Hajek В., Likhanov N., Tsybakov B. On'the delay in a multiple-access system with large propagation delay // IEEE Transactions on Information Theory. 1994. - Vol. 40, № 4. - P. 1158-1166.

70. Тасака С. Протоколы, многостанционного доступа для спутниковых систем пакетной связи: сравнение характеристик // ТИИЭР. — 1984. — Т. 72, № 11.-С. 157-168.

71. Practical implementation of successive interference cancellation in DS/CDMA systems / K. Pedersen, T. Kolding, I. Seskar, J. Holtzman // Proc. of the 5th IEEE International Conference on Universal Personal Communications. — Vol. 1. — 1996. P. 321-325.

72. Andrews J., Hasan A. Analysis of cancellation error for successive interference cancellation with imperfect channel estimation: Tech. rep.: EE-381K: Multiuser Wireless Communications, 2002.

73. Iterative power control for imperfect successive interference cancellation / A. Agrawal, J. Andrews, J. Cioffi, T. Meng // IEEE Transactions on Wireless Communications. — 2005. — Vol. 4, № 3. — P. 878-884.

74. Transmission capacity of wireless ad hoc networks with successive interference cancellation / S. Weber, J. Andrews, X. Yang, G. Veciana // IEEE Transactions on Information Theory. — 2007. — Vol. 53, № 8. — P. 27992814.

75. Yu Y., Giannakis G. High-throughput random access using successive interference cancellation in a tree algorithm // IEEE Transactions on Information Theory. — 2007. Vol. 53, № 12. — P. 4628-4639.

76. Yu Y., Giannakis G. SICTA: A 0.693 contention tree algorithm using successive interference cancellation // Proc. of the 23rd Biennial Symposium on Communications. — Vol. 3. — 2005. — P. 1908-1916.

77. Peeters G., Houdt В., Blondia C. A multiaccess tree algorithm with free access, interference cancellation and single signal memory requirements // Performance Evaluation. — 2007. — Vol. 64, № 9-12. — P. 1041-1052.

78. Wang X., Yu Y., Giannakis G. A robust high-throughput tree algorithm using successive interference cancellation // Proc. of the IEEE Global Telecommunications Conference (GLOBECOM). — 2005. — Vol. 6, № 28. — P. 5-10.

79. Андреев С. Д., Пустовалов Е. В., Тюрликов А. М. Древовидный алгоритм разрешения конфликта, устойчивый к неполному погашению интерференции // Автоматика и телемеханика.— 2009.— Т. 3.— С. 78-96.

80. Houdt В., Peeters G. FCFS tree algorithms with interference cancellation and single signal memory requirements // Proc. of the 15th International Conference on Telecommunications. — 2008. — P. 1-6.

81. Gyorfi L., Gyori S., Massey J. Multiple Access Channels: Theory and Practice / Ed. by E. Biglieri, L. Gyorfi.— IOS Press, Amsterdam, 2007.— Vol. 10. P. 214-249.

82. Janssen A., de Jong M. Analysis of contention tree-algorithms // IEEE Transactions on Information Theory. — 2000. — Vol. 46, № 6. — P. 21632172.

83. Gyorfi L., Gyori S. Analysis of tree algorithm for collision resolution // Proc. of the International Conference on Analysis of Algorithms. — 2005. — P. 357-364.

84. Szpankowski W. Average Case Analysis of Algorithms on Sequences. — New York: John Wiley, 2001. 576 p.

85. Михайлов В. А. Об одном рекуррентном уравнении в теории случайного множественного доступа // Тр. IX симпозиума по проблеме избыточности в информационных системах. — 1986. — Т. 2. — С. 148— 150.

86. Введенская Н. Д. Задержка при стек-алгоритме СМД // Десятая Всесоюзная школа-семинар по вычислительным сетям.— Т. 2.— М.Тбилиси: 1985. — С. 232-235.

87. Тюрликов А. М. Численные оценки для вероятностно-временных характеристик стек-алгоритма множественного доступа // X Всесоюзная школа-семинар по вычислительным сетям.— № 1,— 1985.- С. 188-191.

88. Evseev G., Turlikov A. The multiple-random-access algorithms analysis based on tree properties // 5th Joint Soviet-Swedish International Workshop on Information Theory. — 1991.

89. Цыбаков Б. С., Введенская H. Д. Стек-алгоритм случайного множественного доступа // Проблемы передачи информации. — 1980. — Т. 16, № 3. С. 80-94.

90. Flajolet P., Jacquet. Р. Analytic models for tree communication protocols // Flow control of congested networks. — 1987.

91. Mehravan N. Random-access communication with multiple reception // IEEE Transactions on Information Theory. — 1990. — Vol. 36, № 3. — R 614-622.

92. Цыбаков Б. С., Белоярое А. H. Случайный множественный доступ в канале с двоичной обратной связью вида «успех — не успех» // Проблемы передачи информации. — 1990. — Т. 26, № 3. — С. 67-82.

93. Цыбаков Б. С., Белоярое А. Н. Случайный множественный доступ в канале с двоичной обратной связью // Проблемы передачи информации. — 1990. — Т. 26, № 4. — С. 83-97.

94. Mehravari N., Berger T. Poisson multiple-access contention with binary feedback // IEEE Transactions on Information Theory. — 1984. — Vol. 30, № 5.-P. 745-751.

95. Merakos L., Kazakos D. On retransmission control policies in multiple-access communication networks // IEEE Transactions on Automatic Control. 1985. — Vol. 30, № 2. - P. 109-117.

96. Paris В., Aazhang B. Near-optimum control of multiple-access collision channels // IEEE Transactions on Communications.— 1992.— Vol. 40, № 8. P. 1298-1309.

97. Malkov A., Turlikov A. Random multiple access protocols for communication systems with «success-failure» feedback // Proc. of the IEEE International Workshop on Information Theory. — 1995. — P. 39.

98. Цыбаков Б. С., Введенская П. Д. Случайный множественный доступ нетерпеливых пакетов в широковещательный канал // Проблемы передачи информации. — 1983. — Т. 19, № 4. — С. 72-83.

99. Цыбаков Б. С., Лиханов Н. Б. Система СМД с нетерпеливыми пакетами // Проблемы передачи информации. — 1984. — Т. 20, № 4. — С. 64-85.

100. Малков А. Ю., Тюрликов А. М. Варианты организации передачи «нетерпеливых» пакетов в системе с СМД // X симпозиум по проблеме избыточности в информационных системах. — 1989. — С. 193-195.

101. Malkov A. Y., Turlikov А. М. Random-access communication with success-failure feedback // Proc. of the 6th Joint Swedish-Russian International Workshop on Information Theory. 1993. - P. 107-111.

102. Боровков А. А. Теория вероятностей.— Эдиториал: УРСС, 1999. — 432 с.

103. Тюрликов А. М., Фосс С. Г. Об эргодических алгоритмах в системах случайного множественного доступа с обратной связью «успех-неуспех» // Проблемы передачи информации. — 2010.— Т. 46, № 2.— С. 91-109.

104. Черняк JI. Сети промышленных контроллеров // Открытые системы. 2001. - Т. 1, № 5-6. - С. 10-16.106. 15.3с MAC attributes for enhanced uses, Document 15-07-0558-00-003c, January 2007.

105. Цыбаков Б. С., Файнголъд В. Б. Блокированный стек-алгоритм СМД в сети с конечным числом станций // Проблемы передачи информации. — 1992. Т. 28, № 1. - С. 89-96.

106. Цыбаков Б. С., Федорцов С. П., Рылеева Н. А. Множественный доступ с разрешением конфликтов с помощью номеров станций // Проблемы передачи информации. — 1992. — Т. 28, № 3. — С. 27-39.

107. Тюрликов А. М., Марковский С. Г. Использование адресов абонентов для организации доступа к высокоскоростному каналу связи // Информационно-управляющие системы.— 2003.— Т. 1.— С. 32-38.

108. Марковский С. Г., Тюрликов А. М. Использование адресов абонентов для разрешения конфликтов в канале с шумом // Информационно-управляющие системы. — 2006. — Т. 2. — С. 27—37.

109. Марковский С. Г., Тюрликов А. М. Использование идентификаторов абонентов для резервирования канала множественного доступа // Информационно-управляющие системы. — 2008. — Т. 2. — С. 28-35.

110. Turlikov A. Markovsky S. Improved blocked algorithm in the channcl of multiple access with false conflicts // Proc. of the International Symposium on Problems of Modular Information Systems and Networks (ISC-NET'97). — St-Petersburg: 1997. P. 31-32.

111. Цыбаков Б. С., Федорцов С. П. Один алгоритм доступа станций в канал связи // Проблемы передачи инфорлшции. — 1992. — Т. 28, № 1. — С. 97111.

112. Sidi M., Segall A. Two interfering queues in packet-radio networks // IEEE Transactions on Communications. — 1983. — Vol. 31, № 1. — P. 123-129.

113. Szpankowski W. Bounds for queue lengths in a contention packet broadcast system // IEEE Transactions on Communications. — 1986. — Vol. 34, № 11.-P. 1132-1140.

114. Capetanakis J. Generalized TDMA. The multi-accessing tree protocol // IEEE Transactions on Communications. — 1979. — Vol. 27, № 10. — P. 1476-1484.

115. Tsybakov В., Fayngold V. Blocked RMA stack algorithm in networks with finite number of users // Proc. of the Fourth Joint Swedish-Soviet Workshop Information Theory. — Gotland, Sweden: 1989. — August. — P. 185-188.

116. Цыбаков В. С., Коган А. Я., Тафт В. В. Сети ЭВМ с использованием наземных радио и спутниковых каналов связи // Зарубежная радиоэлектроника. — 1978. — Т. 4. — С. 52-68.

117. Rubin I. Access-control disciplines for multi-access communication channels: Reservation and TDMA schemes // IEEE Transactions on Information Theory. 1979. — Vol. 25, № 5. - P. 516-536.

118. Цыбаков В. С., Берковский М. А. Множественный доступ с резервированием // Проблемы передачи информации. — 1980. — Т. 16, № 1. — С. 50-76.

119. Borst S. Polling systems // Amsterdam: Stichting Mathematisch Centrum. — 1996.

120. FIFO by sets ALOHA (FS-ALOHA): A collision resolution algorithm for the contention channel in wireless ATM systems / D. Vazquez, J. Garcia, C. Blondia, B. Houdt // Performance Evaluation. — 1999. — Vol. 36-37. — P. 401-427.

121. Redana S., Lott M. Performance analysis of IEEE 802.16a in mesh operation mode // Proc. of the 13th 1ST SUMMIT. — Lyon, France: 2004. — June.

122. Klein A., Pries R., Staehle D. Performance study of the WiMAX FDD mode // Proc. of the OPNETWORK 2006.- Washington D.C.: 2006.-August.

123. Doha A., Hassanein H., Takahara G. Performance evaluation of reservation medium access control in IEEE 802.16 networks // IEEE International Conference on Computer Systems and Applications.— 2006. — March. — P. 369-374.

124. Turlikov A., Vinel A. Capacity estimation of centralized reservation-based random multiple-access system // Proc. of the XI International Symposium on Problems of Redundancy in Information and Control Systems. — 2007. — P. 154-160.

125. Baccelli F., Foss S. On the saturation rule for the stability of queues // Journal of Applied Probability. — 1995. Vol. 32, № 2. — P. 494-507.

126. Comparative analysis of sleep mode control algorithms for contemporary metropolitan area wireless networks / A. Anisimov, S. Andreev, O. Galinina, A. Turlikov // Proc. of the 10th International NEW2AN Conference.— 2010.

127. IEEE Std 802.16-2009 (Revision of IEEE Std 802.16-2004), New York, USA, May, 2009.

128. Andreev S., Turlikov A., Vinel A. Contention-based polling efficiency in broadband wireless networks // Proc. of the 15th International Conference on Analytical and Stochastic Modeling Techniques and Applications. — 2008. P. 295-309.

129. Saffer Zs., Andreev S. Delay analysis of IEEE 802.16 wireless metropolitan area network // Proc. of the 15th International Conference on Telecommunications. — 2008.

130. Андреев С. Д. Оптимизация механизма единичного опроса в беспроводных региональных сетях // Тр. научной сессии ГУАП. — 2007.-Т. 1. —С. 78-82.

131. Multi-radio coexistence: Challenges and opportunities / J. Zhu, A. Waltho, X. Yang, X. Guo // Proc. of the 16th International Conference on Computer Communications and Networks. — 2007. — P. 358-364.

132. Andreev S., Dubkov K., Turlikov A. IEEE 802.11 and 802.16 cooperation within multi-radio stations // Proc. of the 11th International Symposium on Wireless Personal Multimedia Communications. — 2008.

133. Andreev S.; Dubkov K., Turlikov A. IEEE 802.11 and 802.16 cooperation within multi-radio stations // Wireless Personal Communications Journal (WIRE). 2010. — Published on-line.

134. Андреев С. Д., Винелъ А. В. Программа имитационного моделирования стандарта беспроводных сетей передачи данных IEEE 802.11: ВНТИЦ, 2007.

135. Андреев С. Д., Семенов С. А., Тюрликов А. М. Методики оценки параметров радиоканала // Информационно-управляющие системы. — 2007. Т. 29, № 4. - С. 37-43.

136. Stability of binary exponential backoff / J. Goodman, A. Greenberg, N. Madras, P. March // Journal of the ACM.— 1988,— Vol. 35, № 3,— P. 579-602.г!

137. Bianchi G. Performance analysis of the IEEE 802.11 distributed coordination function // IEEE Journal on Selected Areas In Communications.— 2000. Vol. 18, № 3. - P. 535-547.

138. Song N., Kwak В., Miller L. On the stability of exponential backoff // Journal of Research of the NIST. — 2003. Vol. 108, № 4. — P. 289-297.

139. Lin L., Jia W., Lu W. Performance analysis of IEEE 802.16 multicast and broadcast polling based bandwidth request // Proc. of the IEEE Wireless Communications and Networking Conference. —- 2007. — P. 1854-1859.

140. Alanen O. Multicast polling and efficient VoIP connections in IEEE 802.16 networks // Proc. of the 10th ACM Symposium on Modeling, Analysis, and Simulation of Wireless and Mobile Systems. — 2007. — P. 289-295.

141. Винелъ А. В., Кобляков В. А., Тюрликов A. M. Класс алгоритмов случайного множественного доступа с очередью для централизованных сетей передачи данных // Информационные технологии. — 2007. — Т. 5. — С. 32-41.

142. Performance analysis of the IEEE 802.16 wireless metropolitan area network / D. Cho, J. Song, M. Kim, K. Han // Proc. of the 1st International Conference on Distributed Frameworks for Multimedia Applications. — 2005. P. 130-136.

143. Moraes L., Maciel P. Analysis and evaluation of a new MAC protocol for broadband wireless access // Proc. of the International Conference on Wireless Networks, Communications and Mobile Computing. — Vol. 1. — 2005. — P. 107-112.

144. Iyengar R., Iyer P., Sikdar B. Delay analysis of 802.16 based last mile wireless networks // Proc. of the 48th IEEE Global Telecommunications Conference (GLOBECOM). — Vol. 5. — 2005. P. 3123-3127.

145. Performance analysis of the random access in IEEE 802.16 / A. Vinel, Y. Zhang, M. Lott, A. Tiurlikov // Proc. of the 16th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications. — Vol. 3. 2005. - P. 1596-1600.

146. Capacity analysis of reservation-based random access for broadband wireless access networks / A. Vinel, Q. Ni, D. Staehle, A. Turlikov // IEEE Journal on Selected Areas in Communications. — 2009. — Vol. 27, № 2. — P. 172181.

147. Андреев С. Д., Нилова А. В., Тюрликов А. М. Использование конкурентного опроса в широкополосных беспроводных сетях // Информационно-управляюище системы. — 2008. — Т. 37, № 6. — С. 4453.

148. Overall delay in IEEE 802.16 with contention-based random access / S. An-dreev, Zs. Saffer, A. Turlikov, A. Vinel // Proc. of the Conference on Analytical and Stochastic Modeling Techniques and Applications. — 2009. — P. 89-102.

149. Investigation of bandwidth request mechanisms under point-to-multipoint mode of WiMAX networks / Q. Ni, A. Vinel, Y. Xiao, A. Turlikov, T. Jiang // IEEE Communications Magazine. — 2007.— Vol. 45, № 5.— P. 132-138.

150. Andreev S., Turlikov A., Vinel A. Performance analysis of a high-speed ultra-wideband WPAN MAC // Proc. of the 14th International Conference on Analytical and Stochastic Modeling Techniques and Applications. — 2007. P. 44-49.

151. Клейнрок JI. Теория массового обслуживания.— М.: Машиностроение, 1979. 600 с.

152. Цыбаков Б. С., Лиханов Н. Б. Некоторые новые алгоритмы случайного множественного доступа // Проблемы передачи информации. — 1985. — Т. 21, № 2. — С. 69-89.

153. Kobliakov A., Turlikov A., Vinel A. Distributed queue random multiple access algorithm for centralized data networks // Proc. of the 10th IEEE International Symposium on Consumer Electronics (ISCE'06). — St.-Petersburg, Russia: 2006. — P. 290-295.

154. Винелъ А. В., Тюрликов A. M., Федоров К. А. Использование последовательного погашения интерференции при организации случайного множественного доступа в централизованных сетях // Информационно-управляющие системы. — 2009. — Т. 2. — С. 46-55.

155. Гольдштейн Б. С., Соколов Н. А., Яновский Г. Г. Сети связи. — БХВ-Петербург, 2010. — 400 с.

156. Galkin A., Simonina O., Yanovsky G. Routes building approach for multicast applications in metro Ethernet networks // Springer Verlag. Lecture Notes on Computer Science. — 2007. — Vol. 4712. — P. 187-193.

157. Jain R., Chiu D., Hawe W. A quantitative measure of fairness and discrimination for resource allocation in shared systems: DEC Research Report TR-301, 1984.

158. Кнут Д. Искусство программирования для ЭВМ, Получисленные алгоритмы, — СПб.: Вильяме, 2000. Т. 2, — 832 с.

159. Foss S., Konstantopoulos Т. An overview of some stochastic stability methods // Journal of Operation Research Society Japan.— 2004.— Vol. 47, № 4. P. 275-303.

160. Gut A. Stopped Random Walks. Limit Theorems and Applications.— Springer, Series in Operations Research and Financial Engineering, 2009. — 199 p.

161. Беляев E. А., Тюрликов A. M. Управление скоростью и ошибкой кодирования в системе сжатия и передачи видеоинформации с ограничениями на память передающего и принимающего устройств // Компьютерная оптика. — 2007. — Т. 31, № 2. — С. 69-76.

162. Беляев Е. А., Тюрликов А. М. Алгоритмы оценки движения в задачах сжатия видеоинформации на низких битовых скоростях // Компьютерная оптика. — 2008. — Т. 32, № 3. — С. 403-413.

163. Belyaev Е., Turlikov A., Ukhanova A. Low-latency video transmission over high-speed WPANs based on low-power compression // Proc. of the IEEE Wireless Communications and Networking Conference. — 2010. — P. 1-6.

164. Беляев E. А., Тюрликов A. M., Уханова А. С. Адаптивное арифметическое кодирование в стандарте JPEG2000 / / Информационно-управляющие системы.— 2007.— Т. 31.— С. 2833.

165. Беляев Е. А., Тюрликов А. М. Оценка вероятности появления символа при адаптивном двоичном арифметическом кодировании в задачах сжатия видеоинформации // Цифровая обработка сигналов. — 2007. — Т. 3. С. 20-24.

166. Shannon С. A mathematical theory of communication // Bell System Technical Journal. — 1948. — Vol. 27. — P. 379-423, 623-656.

167. Zhai F., Katsaggelos A. Joint Source-Channel Video Transmission, Synthesis Lectures on Image, Video, and Multimedia Processing. — Morgan and Claypool Publishers, 2006.— 120 p.

168. Gallant M., Kossentini F. Rate-distortion optimized layered coding with unequal error protection for robust internet video // IEEE Transactions on Circuits and Systems for Video Technology. — 2001.— Vol. 11, № 3.— P. 357 372.

169. Azami Z., Duhamel P., Rioul 0. Joint source-channel coding: Panorama of methods // Proc. of the CNES Workshop on Data Compression. — 1996.