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

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

АНДРЕЕВ Сергей Дмитриевич р £ д д р 2009

ЦЕНТРАЛИЗОВАННОЕ УПРАВЛЕНИЕ

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

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

003475101

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

Научный руководитель - кандидат технических наук, доцент

Тюрликов Андрей Михайлович

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

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

кандидат технических наук Дехканбаев Дмитрий Саттаркулович

Ведущая организация - ОАО «Мощная аппаратура

радиовещания и телевидения»

Защита состоится « <2-2- » семТдьЬ.Я. 2009 г. в Ж часов на заседании диссертационного совета Д 2f2.233.02 при Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу: 190000, г. Санкт-Петербург, ул. Большая Морская, д. 67

С диссертацией можно ознакомиться в библиотеке университета Автореферат разослан « » июл^, 2009 г.

Ученый секретарь

диссертационного совета

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

Осипов Л. А.

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

Актуальность темы. В последние десятилетия наблюдается увеличение числа телекоммуникационных сетей локального и регионального (городского) масштаба, где применение беспроводных технологий связи обеспечивает гибкость топологии сети, включая поддержку мобильных абонентов, быстроту проектирования и низкие затраты на реализацию. Бесспорными лидерами на рынке технологий, использующих каналы множественного доступа, являются протокол региональных (городских) сетей IEEE 802.16 и протокол локальных сетей IEEE 802.11. Активный процесс международной стандартизации, производства беспроводного оборудования и развертывания сетей передачи информации традиционно выводит на передний план задачи так называемого физического уровня. Как следствие, на порядки возрастает скорость работы оборудования, а также значительно усложняется его структура. Возникает ситуация, в которой алгоритм управления доступом к среде зачастую представляет собой «узкое место» всей системы связи и существенно снижает ее потенциальную производительность.

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

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

Основные положения данной работы сформулированы, в основном, на примере протокола региональной (городской) сети IEEE 802.16. Тем не менее, большинство полученных результатов может быть использовано и в других централизованных сетях передачи информации, таких как Универсальная система мобильной связи (universal mobile telecommunications system, UMTS) и новый протокол передачи данных для сетей мобильной связи Long term evolution (LTE).

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

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

2. Выяснить предельную эффективность стандартного алгоритма резервирования в централизованной сети при высокой загрузке.

3. Исследовать зависимость общей задержки передачи сообщения от параметров алгоритма резервирования.

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

5. Провести анализ одновременной работы протоколов региональной (городской) и локальной сети.

Теоретическую основу исследования составили классические труды таких отечественных и зарубежных ученых, как Дж. Месси, Ф. Келли, Л. Клейнрок, С. Лэм, Дж. Капетанакис и И. Рабин, а также современные работы таких ученых и исследователей, как Дж. Бианки, Л. Голдберг, Г. Гианнакис, В. М. Вишневский и А. И. Ляхов.

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

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

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

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

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

4. Исследован режим одновременного функционирования протоколов региональной (городской) и локальной сети передачи информации и предложен алгоритм координирования их совместной работы.

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и симпозиумах в период с 2006 по 2008 гг.: на научных сессиях ГУАГГ; на форуме «Information Systems. Problems, Perspectives, Innovation Approaches»; на семинаре «On Distributed Computer and Communication Networks»; на 11-м симпозиуме «On Problems of Redundancy in Information and Control Systems»; на 14-й конференции «On Analytical and Stochastic Modeling Techniques and Applications»; на семинаре «On Multiple Access Communications»; на 8-й конференции «On Next Generation Teletraffic and Wired/Wireless Advanced Networking»; па 15-й конференции «On Analytical and Stochastic Modeling Techniques and Applications»; на 11-м симпозиуме «On Wireless Personal Multimedia Communications».

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

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

Основные положения, выносимые на защиту.

1. Обобщенный анализ производительности алгоритма разрешения конфликтов в сети передачи информации.

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

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

4. Алгоритм координирования совместной работы протоколов региональной (городской) и локальной сети передачи информации.

Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка цитированных источников и приложения. Работа содержит 155 страниц основного машинописного текста, 40 рисунков и 6 таблиц. Список литературы включает 101 наименование.

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

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

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

В современных телекоммуникационных системах для организации взаимодействия абонентов широко используется множественный доступ, предполагающий коллективное использование канала связи абонентами системы. При этом канал представляет собой общий ресурс, разделение которого необходимо для обеспечения эффективной работы системы связи. Алгоритмы, предназначенные для такого разделения, носят название алгоритмов множественного доступа и располагаются на специальном подуровне управления доступом к среде (УДС или media access control, MAC). Они входят в состав современных протоколов связи, в частности, IEEE 802.11 (Wi-Fi) и IEEE 802.16 (WiMAX).

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

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

Известно, что алгоритм ДЭО описывается двумя параметрами - И-о и т, где первый представляет собой размер начального окна «отсрочки», а второй - максимальную степень «отсрочки». Рядом авторов предлагается рассмотреть алгоритм ДЭО в условиях насыщения, то есть когда у каждого абонента всегда имеется готовый для передачи пакет данных. Можно показать, что в этих условиях последовательность состояний системы в начале каждого временного слота описывается двумерной марковской цепью, что позволяет найти вероятность (повторной) передачи рг абонента в некотором слоте.

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

Результаты расчета Т предложенным в работе способом и полученные имитационным моделированием алгоритма ДЭО представлены на рисунке 1 в логарифмическом масштабе. Приведенная кривая иллюстрирует зависимость времени Т от интенсивности входного потока Л новых пакетов в систему с М абонентами. Данная зависимость представляет собой верхнюю оценку для значений времени достижения Г.

Интенсивность входного потока, Л

Рисунок 1. Время первого выхода из рабочей области для алгоритма ДЭО: 1 - аналитическая верхняя оценка; 2 — результаты имитационного моделирования

В реальных системах связи, например, в протоколе IEEE 802.11, рассматриваемая проблема стабильности до недавнего времени не была актуальной в силу относительно небольшого числа абонентов, а также особенностей построения протокола подуровня УДС. Тем не менее, вопрос стабильности становится важным при работе региональной (городской) сети по протоколу IEEE 802.16, который предполагает одновременное взаимодействие с базовой станцией сотен абонентов.

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

Протокол JEEE 802.16 специфицирует физический уровень и подуровень УДС, предоставляя динамическое выделение ресурса по запросу. Архитектура IEEE 802.16 предполагает наличие одной базовой станции (БС) и одной или нескольких абонентских станций (АС), которые ниже для краткости именуются абонентами. БС организует опрос абонентов и составляет расписание их работы. Обмен данными ведется временными кадрами по двум раздельным каналам. В нисходящем канале передается трафик от БС к абонентам, тогда как в восходящем канале поток данных направлен в противоположную сторону.

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

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

Задержкой передачи запроса 5а {К, Л) назовем случайную величину, равную интервалу времени от момента поступления запроса в систему до момента окончания его успешной передачи или до момента, когда он был отброшен. Здесь К - число конкурентных слотов в кадре, а Л - интенсивность входного потока. Введем в систему новый запрос в

некотором слоте s и обозначим его задержку через Л). Среднюю

задержку передачи запроса определим как

LU(tf,A)4limsup£[4s)(K,A)]. (1)

■у—>оо

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

Ra(K) ^ sup{A : Da(K, А) < оо}. (2)

Рассмотрим случайную величину которая принимает значение 1 в случае успеха в конкурентном слоте i. Величина зависит от

s — 1

К и Л. Рассмотрим также случайную функцию A,s) = У]

j=о

Определим интенсивность выходного потока на слот для алгоритма А в системе с потерями как

ФА(*, A^liminfMM^MI. (з)

s—юо S

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

адг)= sup Фл(М. (4)

A:Da(K, А)<оо

Вычислим скорость алгоритма ДЭО в системе с потерями для случая минимально возможной задержки, обозначая ее Rbeb{i){K)> гЛе 1 означает единственную попытку передачи. Максимальное число Q повторных передач запроса установим равным 0. Допустим также бер-пуллневский входной поток и наличие буфера для хранения одного запроса. Такая система допущений практически оправдана при передаче чувствительного к задержке трафика (например, голосового потока VoIP). В диссертационной работе для заданного числа абонентов М показана справедливость следующего утверждения.

Утверждение 1. Скорость алгоритма ДЭО в системе без повторных передач пакетов данных не зависит от К и вычисляется как

( 1 Пвев( 1) = - м) , (5)

где С? - общее число групп абонентов.

Приведенное у тверждение! позволяет сделать вывод, что при групповом опросе абонентов максимально возможный выигрыш незначителен по сравнению с величиной скорости алгоритма ДЭО. Следовательно, в системе без повторных передач ((2 = 0) разбиение абонентов па группы нецелесообразно.

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

Можно показать, что наибольшая вероятность успеха в условиях насыщения совпадает со скоростью передачи алгоритма ДЭО в смысле определений (2) и (4). Для произвольно выбранного слота в кадре вычислим две вероятности: вероятность (повторной) передачи запроса некоторым меченым абонентом (р4) и условную вероятность возникновения конфликта при условии передачи запроса меченым абонентом (рс). Легко показать, что

рс = 1-(1-л)Л'-1. (6)

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

Утверждение 2, Вероятность передачи запроса меченым абонентом Рь в системе с потерями пакетов данных вычисляется как

= _2(1 — 2рс)(1 ~Рс+1)__(7)

Ш0(1-рс)(1-(2р^)+К(1-2рс)(1-р9+гУ если (2 < т и

_2(1-2ре)(1-р?+1)_

(1 - 2рс)(1¥0(1 - 2™р?+1) + К( 1 - р?+1)) +рМ1 - (2рс)т)' если <2 > т.

Отметим, что в пределе при <3, стремящемся к бесконечности, вы-ражешю (7) справедливо для системы без потерь пакетов данных.

Рг

Выражения (6) и (7) представляют собой нелинейную систему уравнений с двумя неизвестными рс ир(, которая может быть решена численно. Тогда значение скорости алгоритма ДЭО в случае не более (¿3+1) попытки передачи запроса вычисляется как

Двевю+х)^) = Мрг{ 1 - р,.)м~1. (8)

Скорость алгоритма ДЭО для общего опроса с М = 40 и К = 8 показана на рисунке 2. Предложенный аналитический подход позволяет максимизировать скорость алгоритма при \¥0,л = 2М — К и т — 0, то есть в приведенном примере \Vopt = 72. Для такой оптимальной системы скорость не зависит от максимального числа передач. Кроме того, существует такое значение величины ф, при котором алгоритму ДЭО с нсоптимальиыми параметрами удастся достичь скорости в системе с потерями пакетов данных, равной его скорости в системе без потерь.

0,4

/ 1^0 = 16,01 = 12

'О 5 10 15 20

Максимальное число попыток передачи, 0+1

Рисунок 2. Эффективность общего опроса при ограничении на число повторных передач

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

А = £>Г + а + £>? + г, (9)

где компоненты Вг определены следующим образом. D\ - задержка резервирования, равная интервалу времени от момента поступления меченого сообщения к абоненту с номером i до момента начала отправки этим абонентом соответствующего запроса в восходящем канале; а -время передачи запроса (длительность конкурентного слота); Df - задержка обслуэюивания, равная интервалу времени от момента окончания отправки абонентом с номером г запроса на меченое сообщение до момента начала успешной передачи соответствующего ему пакета данных в восходящем канале; т - длительность передачи пакета данных.

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

Утверждение 3. Верхняя оценка для общей задержки передачи сообщения в централизованной системе связи вычисляется как

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

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

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

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

В последнее время стало возможным использование на физическом уровне системы связи процедуры последовательного погашения интерференции (succcssive interference cancellation, SIC). Процедура SIC позволяет восстанавливать попавшие в конфликт пакеты данных от различных абонентов беспроводного канала связи. Использование процедуры SIC, тем не менее, целесообразно только в восходящем канале централизованных сетей передачи информации, поскольку для работы процедуры необходима информация, доступная на базовой станции. Таким образом, описываемый подход может быть естественно применен в централизованной сети IEEE 802.16.

Работу рассматриваемых алгоритмов удобно представлять в виде двоичного дерева (рисунок 3,а), в котором корневая вершина соответствует множеству абонентов, вступивших в первоначальный конфликт. Остальные вершины соответствуют подмножествам абонентов, передающих свои пакеты в каждом слоте периода разрешения конфликта. Ребра дерева разрешения конфликта (ДРК) отражают процесс разбиения, то есть из вершин с двумя и более абонентами «вырастает» по две ветви.

| А.В.С |. с - | /и | , '.j'A.B \ а | < ~| ^ | .< а с | с | | Т~|

Рисунок 3. Пример работы древовидных алгоритмов: а — СДА; б —

В приведенном ДРК СДА один из конфликтов неизбежен. Целесообразно пропускать слот с неизбежным конфликтом и переходи ть непосредственно на следующий уровень ДРК. Такое усовершенствование определяет МДА (рисунок 3,6). Пропуск слота повышает скорость МДА по сравнению со скоростью СДА с 0,346 до 0,375 в рамках классической модели СМД.

Вреия

Время

| л.в.с | с •!• <я )

МДА; в - SICTA

Недавно рядом авторов был предложен алгоритм (см. рисунок 3,в), сочетающий использование традиционного древовидного алгоритма с преимуществами процедуры SIC (SIC in a tree algorithm, SICTA). При его работе процедура SIC обрабатывает принятые сигналы, содержащие информацию о конфликте. Такие конфликтные сигналы сохраняются до своей обработки в памяти приемника, которая предполагается неограниченной. Базовый алгоритм SICTA позволяет пропустить все левое поддерево ДРК СДА и имеет скорость 0,693, то есть вдвое превосходит СДА.

Наличие на приемной стороне неограниченного объема памяти для хранения принятых конфликтных сигналов практически нереализуемо. Кроме того, в реальных приемных устройствах с процедурой SIC возможно появление ошибок восстановления пакета данных, вызванных наличием остаточных сигналов после нейтрализации принятого сигнала в исходном составном сигнале. Предложенная в диссертационной работе; модификация алгоритма SICTA использует единичную память па приемной стороне и устойчива к ошибкам восстановления пакета, что приводит к снижению скорости до 0,515. Увеличение объема доступной памяти приведет к росту скорости алгоритма (которая ограничена сверху скоростью SICTA), но затруднит его практическую реализацию.

Основная идея предложенного алгоритма заключается в отказе от пропуска некоторых конфликтных слотов, пропуск которых мог бы привести к эффекту запирания из-за ошибок восстановления пакета. Ниже будем называть данный алгоритм устойчивым алгоритмом SICTA (robust SICTA, R-SICTA). Опишем общий подход к вычислению скорости древовидных алгоритмов с последовательным погашением интерференции, модифицируя способ пересчета среднего времени разрешения конфликта. Рассмотрим некоторый древовидный алгоритм А с процедурой SIC. Обозначим среднее время разрешения конфликта кратности к для данного алгоритма Используя отношение ^х, можно установить пределы для скорости древовидного алгоритма А, которую обозначим Ra■ Будем рассматривать ДРК алгоритма А как ДРК СДА, в котором время просмотра некоторых вершин дерева равно нулю в силу функционирования процедуры SIC.

Утверждение 4. Среднее число вершин с ненулевым временем просмотра в ДРК R-SICTA (T^s) вычисляется как

где Тк - среднее число вершин в ДРК СДА; Nk - среднее число конфликтов кратности два в ДРК СДА начальной кратности k; q - ошибка восстановления пакета после нейтрализации успешно принятого сигнала, a q' - после нейтрализации конфликтного сигнала.

Данное утверждение позволяет получить приближение для скорости предложенного алгоритма Я-БЮТА следующим образом:

Rns * 2Тттщтч^ГШУ (12)

где R - скорость СДА и 7 = 0,721. В работе также указан способ получения точных границ для скорости алгоритма R-SICTA.

В диссертационной работе предлагается заменить алгоритм ДЭО, используемый в конкурентном интервале кадра IEEE 802.16, на предложенный алгоритм 11-SICTA. На рисунке 4 проведено сравнение общей задержки передачи сообщения в системе IEEE 802.16 для М = 6 и К = 1. Видно, что при отсутствии ошибок восстановления пакета предложенный алгоритм R-SICTA демонстрирует выигрыш по задержке в 50 - СО % по сравнению со стандартным алгоритмом ДЭО. В худшем случае, когда восстановление пакетов данных невозможно и q' = q = 1, величина выигрыша снижается до 25 - 5G %.

Рисунок 4. Общая задержка передачи сообщения в IEEE 802.16: 1 — ДЭО; 2 - СДА; 3 - МДА; 4 - R-SICTA, q' = q = 0; 5 -SICTA

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

Помимо развития телекоммуникационных протоколов в отдельности, наблюдается тенденция к созданию универсального оборудования. Следуя ей, ряд авторов предлагает объединить функциональность различных протоколов в рамках многопротокольного абонента. Такой абонент может одновременно работать в нескольких сетях передачи информации. В диссертационной работе рассматривается наиболее интересный для исследования случай совместной работы протоколов IEEE 802.11 и IEEE 802.16. Ставится задача обеспечения совместной работы непосредственно па подуровне УДС двухпротоколъного абонента.

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

Координатор УДС осуществляет контроль передачи данных двух-протокольным абонентом в обеих сетях передачи информации и, таким образом, обеспечивает их сосуществование. Учитывая тот факт, что работа протокола IEEE 802.16 построена па составлении общего расписания, Координатор ограничивается лишь наблюдением активности, связанной с получением и отправкой пакетов данных в этой сети, непосредственно влияя лишь на работу сети IEEE 802.11. В частности, Координатор разрешает или запрещает доступ IEEE 802.11 к среде передачи в зависимости от текущего расписания IEEE 802.16.

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

Как базовый алгоритм координирования, так и его улучшение используют только паузы в расписании работы сети IEEE 802.16. Снимая данное ограничение, можно достичь более высокой производительности. Однако одновременный прием и передача данных могут быть технически реализованы только в случае наличия двух раздельных антенн у двухпротокольпого абонента. Будем называть алгоритм, использую-

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

Выше отмечалось, что работа Координатора непосредственно не влияет на расписание сети IEEE 802.16. Сосредоточимся па анализе сети IEEE 802.11. Определим производительность (goodput) двухпротокольного абонента как долю физической скорости передачи данных в сети IEEE 802.11, доступную для отправки пакетов данных на подуровне УДС. Производительность при введенных в диссертационной работе ограничениях представляет собой оценку сверху для производительности, которая может быть достигнута в реальной системе связи.

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

Физическая скорость передачи данных, Мбит/с

Рисунок 5. Эффективность алгоритмов координирования: 1 — базового; 2 — улучшенного; 3 — улучшенного с подавлением

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

В приложении А собраны известные результаты относительно алгоритма двоичной экспоненциальной «отсрочки».

В приложении Б дан способ расчета скорости древовидных алгоритмов с последовательным погашением интерференции.

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

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

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

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

3. Проведена оптимизация работы алгоритма двоичной экспоненциальной «отсрочки» на стадии резервирования ресурса.

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

5. Разработан эффективный древовидный алгоритм со свойством последовательного погашения интерференции.

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

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

8. Предложен способ вычисления производительности двухпрото-колыюго абонента.

Основное содержание работы изложено в следующих публикациях (статьи 1-4 опубликованы в изданиях, включенных в перечень ВАК):

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

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

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

4. Андреев С. Д. Управление работой двухпротокольного абонента в беспроводных телекоммуникационных сетях / / Системы управления и информационные технологии. 2009. № 1.1. С. 108-112.

5. Андреев С. Д. Исследование стабильности систем случайного множественного доступа под управлением алгоритма А Л ОХ А // Тр. научной сессии ГУАП. 2006. Т. 1. С. 237-240.

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

7. Андреев С. Д., Пустовалов Е. В. Древовидные алгоритмы разрешения конфликтов с использованием подавления интерференции в условиях капала с шумом // Тр. научной сессии ГУАП. 2008. Т. 1. С. 82-85.

8. Винель А. В., Андреев С. Д. Оценка среднего времени пребывания алгоритма Binary Exponential Backoff в устойчивом состоянии // Тр. научной сессии ГУАП. 2006. Т. 1. С. 250-253.

9. Andreev S. Throughput estimation for a personal wireless networks standard // Proc. of the. Forum «Information Systems. Problems, Perspectives, Innovation Approaches». Vol. 2. 2007. P. 33-38.

10. Andreev S., Dubkov K., Turlikov A. IEEE 802.11 and 802.16 cooperation within multi-radio stations // Proc. of the 11th WPMC Symposium. 2008. P. 1-5.

11. Andreev S., Pustovalov E., Turlikov A. Si СТА modifications with single memory location and resistant to cancellation errors // Proc. of the 8th NEW2AN Conference. 2008. P. 13-24.

12. Andreev S., Pustovalov E., Turlikov A. Tree algorithms with free access and interference cancellation in presence of cancellation errors // Proc. of the 11th WPMC Symposium. 2008. P. 1-5.

13. Andreev S., Suffer Zs., Anisimov A. Overall delay analysis of IEEE 802.16 network // Proc. of the IEEE ICC. 2009. P. 1-6.

14. Andreev S., Turlikov A., Vinel A. Performance analysis of a high-speed ultra-wideband WPAN MAC // Proc. of the 14th ASMTA Conference. 2007. P. 44-49.

15. Andreev S., Turlikov A., Vinel A. Contention-based polling efficiency in broadband wireless networks // Proc. of the 15th ASMTA Conference. 2008. P. 295-309.

16. Andreev S., Turlikov A., Vinel A. Symmetric user grouping for multicast and broadcast polling in IEEE 802.16 networks // Selected Lectures on Multiple Access and Queuing Systems / Ed. by V. Vishnevsky, A. Vinel, Y. Koucheryavy, D. Staehle. SPb.: SUAI, 2008. P. 52-62.

17. Andreev S., Vinel A. Gilbert-Elliott model parameters derivation for the IEEE 802.11 wireless channel // Proc. of the DCCN Workshop. Vol. 1. 2007. P. 101-107.

18. Andreev S., Vinel A. Performance analysis and enhancement of an ultrawideband WPAN MAC in the presence of noise // Proc. of the 11th Symposium on Problems of Redundancy in Information and Control Systems. 2007. P. 117-122.

19. Saffer Zs., Andreev S. Delay analysis of IEEE 802.16 wireless metropolitan area network // Proc. of the 15th 1CT Conference. 2008. P. 1-5.

Формат бумаги 60 X 84 1/16. Бумага офсетная. Печ. л. 1,25. Тираж 100 экз. Зак. № 489

Отпечатано в редакционно-издательском центре ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67

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

Введение

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

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

1.2 Классификация сетей передачи данных.

1.3 Классификация алгоритмов множественного доступа.

1.4 Классическая модель системы связи с СМД.

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

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

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

1.4.4 Абонент.

1.4.5 Разнообразие моделей

1.5 Характеристики алгоритмов СМД.

1.6 Стабильность алгоритма А ЛОХ А.

1.7 Время стабильной работы алгоритма ДЭО.

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

2. Эффективность конкурентного резервирования в централизованной системе связи

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

2.2 Обзор протокола IEEE 802.

2.3 Общая модель системы связи

2.4 Обобщенные характеристики алгоритмов СМД.

2.4.1 Система без потерь пакетов данных

2.4.2 Система с потерями пакетов данных.

2.5 Эффективность конкурентного резервирования.

2.5.1 Усеченный алгоритм ДЭО.

2.5.2 Система без повторных передач пакетов данных.

2.5.3 Система без потерь пакетов данных

2.5.4 Система с потерями пакетов данных.

2.5.5 Практические замечания.

2.6 Общая задержка передачи сообщения.

2.6.1 Модификация общей модели системы связи.

2.6.2 Способ оценки средней задержки.

2.6.3 Численные результаты.

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

3. Древовидные алгоритмы разрешения конфликта со свойством погашения интерференции

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

3.2 Модель системы и описание алгоритмов.

3.2.1 Традиционные древовидные алгоритмы.

3.2.2 Последовательное погашение интерференции.

3.2.3 Описание процедуры погашения интерференции.

3.2.4 Ограничение памяти на приемной стороне.

3.2.5 Учет неполного погашения интерференции

3.3 Анализ древовидных алгоритмов с погашением интерференции

3.3.1 Общая процедура вычисления скорости.

3.3.2 Базовый алгоритм SICTA.

3.3.3 Предлагаемый алгоритм R-SICTA

3.4 Сравнение алгоритмов

3.4.1 В рамках классической модели СМД.

3.4.2 В рамках протокола IEEE 802.

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

4. Управление работой двухпротокольного абонента в беспроводных сетях связи

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

4.2 Раздельное функционирование сетей связи.

4.2.1 Протокол IEEE 802.

4.2.2 Протокол IEEE 802.16 со схемой OFDMA.

4.3 Совместное функционирование сетей связи.

4.3.1 Принцип координирования на подуровне УДС

4.3.2 Базовый алгоритм координирования.

4.3.3 Улучшенный алгоритм координирования.

4.3.4 Улучшенный алгоритм координирования с подавлением сигнала занятости канала связи.

4.4 Анализ производительности алгоритмов.

4.4.1 Описание модели системы.

4.4.2 Случай единственного захвата за кадр.

4.4.3 Случай нескольких захватов за кадр.

4.4.4 Улучшенный алгоритм координирования

4.4.5 Улучшенный алгоритм координирования с подавлением сигнала занятости канала связи.

4.5 Численные результаты.

4.5.1 Описание системы имитационного моделирования.

4.5.2 Сравнительный анализ алгоритмов.

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

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

В первую очередь это справедливо для сетей локального и регионального (городского) масштаба, где применение беспроводных технологий связи обеспечивает гибкость топологии сети, включая поддержку мобильных абонентов, быстроту проектирования и низкие затраты па реализацию. Бесспорными лидерами на рынке технологий, использующих каналы множественного доступа, являются протокол региональных (городских) сетей IEEE 802.16 [58] и протокол локальных сетей IEEE 802.11 [57]. Первый протокол задает централизованную сеть связи, в которой базовая станция регламентирует передачу множества абонентов, второй - распределенную сеть, в которой может отсутствовать центральный координирующий узел.

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

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

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

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

Вышеупомянутый протокол региональной (городской) сети IEEE 802.16 предназначен для построения системы связи, объединяющей абонентов с разнородным характером трафика: от традиционного голосового сервиса до современной потоковой видеоинформации. Растущая популярность данного протокола приводит к увеличению числа абонентов системы связи, которое уже на современном этапе развития протокола может достигать нескольких сотен. Дальнейшее увеличение числа абонентов и интенсивности их трафика неизбежно приведет к выявлению «узких мест» протокола, одним из которых, бесспорно, является алгоритм резервирования ресурса канала связи. Дело в том, что для многих типов трафика протоколом на этом этапе предусмотрен способ случайного множественного доступа, известный как алгоритм двоичной экспоненциальной «отсрочки», основная идея которого была предложена еще в 1975 году и с тех пор практически не изменилась. Более того, множеством авторов показано, что в условиях достаточно высокой входной загрузки данный алгоритм нестабилен в том смысле, что задержка резервирования ресурса неограниченно возрастает. Как следствие, общая задержка передачи сообщения в системе может оказаться неприемлемой.

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

Основные положения данной работы сформулированы, в основном, на примере протокола региональной (городской) сети IEEE 802.16. Тем не менее, большинство полученных результатов может быть использовано и в других централизованных сетях связи, таких как Универсальная система мобильной связи (universal mobile telecommunications system, UMTS) и новый протокол передачи данных для мобильных сетей Long term evolution (LTE).

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

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

2. Выяснить предель?1ую эффективность стандартного алгоритма резервирования в централизованной сети при высокой загрузке.

3. Исследовать зависимость общей задержки передачи сообщения от параметров алгоритма резервирования.

4. Разработать новый алгоритм резервирования ресурса канала связи в централизованной системе передачи информации для повышения уров-?1Я качества обслуживания абонентов.

5. Провести анализ одновременной работы протоколов региональной (городской) и локальной сети.

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

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

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

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

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

4. Исследован режим одновременного функционирования протоколов региональной (городской) и локальной сети передачи информации и предложен алгоритм координирования их совместной работы.

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

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

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

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

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

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

1. На научных сессиях ГУАП, посвященных всемирному Дню авиации и космонавтики (Санкт-Петербург, Россия, 2006 - 2008).

2. На международном форуме «Information Systems. Problems, Perspectives, Innovation Approaches» (Санкт-Петербург, Россия, 2007).

3. На международном семинаре «On Distributed Computer and Communication Networks» (Москва, Россия, 2007).

4. На 11-м международном симпозиуме «On Problems of Redundancy in Information and Control Systems» (Санкт-Петербург, Россия, 2007).

5. На 14-й международной конференции «On Analytical and Stochastic Modeling Techniques and Applications» (Прага, Чешская Республика,

2007).

6. На международном семинаре «On Multiple Access Communications» (Санкт-Петербург, Россия, 2008).

7. На 8-й международной конференции «On Next Generation Teletraffic and Wired/Wireless Advanced Networking» (Санкт-Петербург, Россия, 2008).

8. На 15-й международной конференции «On Analytical and Stochastic Modeling Techniques and Applications» (Никосия, Республика Кипр,

2008).'

9. На 11-м международном симпозиуме «On Wireless Personal Multimedia Communications» (Финляндия, 2008).

Зарегистрирована программная разработка в отраслевом фонде алгоритмов и программ: ВНТИЦ, регистрационный номер 50200702303, 2007 [3].

Публикации. Материалы, отражающие основное содержание и результаты диссертационной работы, опубликованы в 19 печатных работах. Из них 4 работы [4,5,7,8] опубликованы в рецензируемых научных журналах, утвержденных в перечне ВАК.

Основные положения, выносимые на защиту.

1. Обобщенный анализ производительности алгоритма разрешения конфликтов в сети передачи информации.

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

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

4. Алгоритм координирования совместной работы протоколов региональной (городской) и локальной сети передачи информации.

Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка использованных источников и приложения. Работа содержит 155 страниц основного машинописного текста, 40 рисунков и 6 таблиц. Список литературы включает 101 наименование.

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

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

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

3. Проведена оптимизация работы алгоритма двоичной экспоненциальной «отсрочки» на стадии резервирования ресурса.

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

5. Разработан эффективный древовидный алгоритм со свойством последовательного погашения интерференции.

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

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

8. Предложен способ вычисления производительности двухпротокольного абонента.

Заключение

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

Для повышения эффективности резервирования ресурса канала связи был разработан альтернативный стандартному древовидный алгоритм со свойством последовательного погашения интерференции, а также был выявлен выигрыш от замены алгоритма резервирования в сети IEEE 802.16. Была разработана аналитическая модель для оценки общей задержки передачи сообщения в рассматриваемой системе связи и исследованы вопросы одновременного функционирования региональной (городской) и локальной сети передачи данных. Полученные в работе результаты могут быть также использованы в протоколах Универсальной системы мобильной связи (UMTS) и Long term evolution (LTE).

1. Андреев С. Д. Исследование стабильности систем случайного множественного доступа под управлением алгоритма AJIOXA // Тр. научной сессии ГУАП. 2006. - Т. 1. — С. 237-240.

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

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

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

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

6. Андреев С. Д., Пустовалов Е. В. Древовидные алгоритмы разрешения конфликтов с использованием подавления интерференции в условиях канала с шумом // Тр. научной сессии ГУАП.~ 2008.— Т. 1.— С. 8285.

7. Андреев С. Д. Управление работой двухпротокольного абонента в беспроводных телекоммуникационных сетях // Системы управления и информационные технологии. — 2009. — Т. 35, № 1.1. — С. 108-112.

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

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

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

11. Винель А. В., Андреев С. Д. Оценка среднего времени пребывания алгоритма Binary Exponential Backoff в устойчивом состоянии // Тр. научной сессии ГУАП. 2006. - Т. 1. - С. 250-253.

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

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

14. Кемени Дою., Снелл Дэ/с. Конечные цепи Маркова. М.: Наука, 1970. 272 с.

15. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение,1979. 432 с.

16. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. 600 с.

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

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

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

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

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

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

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

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

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

26. Al-Ammal H., Goldberg L., MacKenzie P. Binary exponential backoff is stable for high arrival rates // Proc. of the 17th Annual Symposium on Theoretical Aspects of Computer Science. — 2000. — P. 169-180.

27. Al-Ammal H., Goldberg L., MacKenzie P. An improved stability bound for binary exponential backoff // Theory of Computing Systems. — 2001. — Vol. 34, № 3. P. 229-244.

28. Alanen 0. 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.

29. 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.

30. Andreev S. Throughput estimation for a personal wireless networks standard // Proc. of the International Forum «Information Systems. Problems, Perspectives, Innovation Approaches». — Vol. 2. — 2007. — P. 33-38.

31. 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. — P. 1-5.

32. Andreev S., Pustovalov E., Turlikov A. Tree algorithms with free access and interference cancellation in presence of cancellation errors // Proc. of the 11th International Symposium on Wireless Personal Multimedia Communications. 2008. — P. 1-5.

33. Andreev S., Saffer Zs., Anisimov A. Overall delay analysis of IEEE 802.16 network // Proc. of the IEEE International Conference on Communications. — 2009. P. 1-6.

34. 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.

35. 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.

36. Andreev S., Vinel A. Gilbert-Elliott model parameters derivation for the IEEE 802.11 wireless channel // Proc. of the International Workshop on Distributed Computer and Communication Networks. — Vol. 1.— 2007.— P. 101-107.

37. Andreev S., Vinel A. Performance analysis and enhancement of an ultra-wideband WPAN MAC in the presence of noise // Proc. of the 11th International Symposium on Problems of Redundancy in Information and Control Systems. 2007. - P. 117-122.

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

39. Berlemann L., Hoymann C., Hiertz G., Mangold S. Coexistence and in-terworking of IEEE 802.16 and IEEE 802.11(e) // Proc. of the 63rd IEEE Vehicular Technology Conference. Vol. 1. - 2006. — P. 27-31.

40. 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.

41. Boggs D., Mogul J., Kent C. Measured capacity of an Ethernet: myths and reality // Proc. of the Symposium on Communications Architectures and Protocols. Vol. 18. — 1988. — P. 222-234.

42. Bordenave C., McDonald D., Proutiere A. Random multi-access algorithms: a mean field analysis // Proc. of the 43rd Annual Allerton Conference on Communication, Control, and Computing. — 2005. — P. 494-503.

43. Capetanakis J. Tree algorithms for packet broadcast channels // IEEE Transactions on Information Theory. — 1979. — Vol. 25, № 5. — P. SOS-SIS.

44. Chlebus B. Handbook of Randomized Computing / Ed. by P. Pardalos, S. Rajasekaran, J. Reif, J. Rolim. — K. A. Publishers, 2001, — P. 401-456.

45. Cho D., Song J., Kim M., Han K. Performance analysis of the IEEE 802.-16 wireless metropolitan network // Proc. of the 1st International Conference on Distributed Frameworks for Multimedia Applications. — 2005. — P. 130136.

46. Djukic P., Valaee S. 802.16 MCF for 802.11a based mesh networks: a case for standards re-use // Proc. of the 23rd Biennial Symposium on Communications. 2006. - P. 186-189.

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

48. Goldberg L., MacKenzie P. Analysis of practical backoff protocols for contention resolution with multiple servers // Proc. of the 7th Symposium on Discrete Algorithms. — 1996. — P. 554-563.

49. Goodman J., Greenberg A., Madras N., March P. Stability of binary exponential backoff 11 Journal of the ACM. 1988,- Vol. 35, № 3,- P. 579602.

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

51. 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.

52. Hastad J., Leighton Т., Rogoff B. Analysis of backoff protocols for multiple access channels // SIAM Journal on Computing. — 1996. — Vol. 25, № 4. — P. 740-774.

53. 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.

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

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

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

57. Jeong D.; Jeon W. Performance of an exponential backoff scheme for slotted-ALOHA protocol in local wireless environment // IEEE Transactions on Vehicular Technology. 1995. — Vol. 44, № 3. — P. 470-479.

58. Kamerman A. Coexistence between Bluetooth and IEEE 802.11 CCK solutions to avoid mutual interference: Tech. rep. IEEE 802.11-00/162: Lucent Technologies Bell Laboratories, 1999/2000.

59. Kelly F., MacPhee I. The number of packets transmitted by collision detect random access schemes // Annals of Probability. — 1987. — Vol. 15, № 4. — P. 1557-1568.

60. 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.

61. 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.

62. 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.

63. 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. 249 p.

64. 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.

65. Mangold S. Analysis of IEEE 802.lie and application of game models for support of quality-of-service in coexisting wireless networks: Ph.D. thesis / RWTH Aachen University. — 2003. 266 p.

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

67. 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.

68. Merakos L., Bisdikian C. Delay analysis of the n-ary stack random-access algorithm // IEEE Transactions on Information Theory. — 1988. — Vol. 34, № 5. P. 931-942.

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

70. 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.

71. 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.

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

73. 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.

74. Ramakrishnan K., Yang H. The Ethernet capture effect: analysis and solution // Proc. of the 19th Conference on Local Computer Networks. — 1994. — P. 228-240.

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

76. 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.

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

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

79. Sakakibara K., Muta H., Yuba Y. The effect of limiting the number of retransmission trials on the stability of slotted ALOHA systems // IEEE Transactions on Vehicular Technology. — 2000. — Vol. 49, № 4. — P. 14491453.

80. Shoch J., Hupp J. Measured performance of an Ethernet local network // Communications of the ACM. — 1980. — Vol. 23, № 12. — P. 711-721.

81. Sivchenko D., Bayer N., Xu В., Rakocevic V, Habermann J. Internet traffic performance in IEEE 802.16 networks // Proc. of the 12th European Wireless Conference. — 2006. — P. 1-5.

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

83. Szpankowski W. Average Case Analysis of Algorithms on Sequences / Wiley, New York., 2001. 576 p.

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

85. Tsybakov B. One stochastic process and its application to multiple access in supercritical region // IEEE Transactions on Information Theory. — 2001. — Vol. 47, № 4. P. 1561-1569.

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

87. Vinel A., Zhang Y., Ni Q., Lyakhov A. Efficient request mechanisms usage in IEEE 802.16 // Proc. of the 49th IEEE Global Telecommunications Conference. — 2006. — P. 1-5.

88. Walke В., Mangold S., Berlemann L. IEEE 802 Wireless Systems: Protocols,4

89. Multi-Hop Mesh/Relaying, Performance and Spectrum Coexistence / Wiley, Chichester, 2007. 382 p.

90. Wang F., Nallanathan A., Garg H. Introducing packet segmentation for the IEEE 802.11b throughput enhancement in the presence of Bluetooth // Proc. of the 59th IEEE Vehicular Technology Conference.— Vol. 4.— 2004. — P. 2252-2256.

91. Wang X., Yu Y., Giannakis G. Combining random backoff with a cross-layer tree algorithm for random access in IEEE 802.16 // Proc. of the IEEE Wireless Communications and Networking Conference. — Vol. 2. — 2006. — P. 972-977.

92. Wang X., Yu Y., Giannakis G. A deadlock-frce high-throughput tree algorithm for random access over fading channels // Proc. of the 40th Annual Conference on Information Sciences and Systems. — 2006. — P. 420-425.

93. Wang X., Yu Y., Giannakis G. A robust high-throughput tree algorithm using successive interference cancellation // IEEE Transactions on Communications. 2007. - Vol. 55, № 12. — P. 2253-2256.

94. Wang X., Yu Y., Giannakis G. Design and analysis of cross-layer tree algorithms for wireless random access // IEEE Transactions on Wireless Communications. — 2008. — Vol. 7, № 3. — P. 909-919.

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

96. 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.

97. 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.

98. Zhang C., Yang S., Pan II. Fa,thy A., El-Ghazaly S. Nair V. Reconfig-urable antenna for simultaneous multi-service wireless applications // Proc. of the IEEE Radio and Wireless Symposium. — 2007. — P. 543-546.

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