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

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

КОЕЛЯКОВ Владимир Андреевич

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

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

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

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

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

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

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

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

профессор Крук Евгений Абрамович

кандидат технических наук, старший научный сотрудник Егоров Владимир Викторович

Ведущая организация - ОАО «Всероссийский Научно-исследовательский институт радиоаппаратуры», г. Санкт-Петербург.

Защита состоится « » ¿>^¿¿¿¿^'2006 г. в /-^Сф часов на заседании диссертационного совета Д 2*12.233.оУ при Государственном образовательном учреждения высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу: 190000, Санкт-Петербург, ул.Б Морская, 67, ГУАП.

С диссертацией можно ознакомиться в библиотеке ГУАП.

Автореферат разослан » 2006 г.

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

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

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

Актуальность темы. Активное развитие сетей передачи данных обуславливает необходимость исследования распространенного метода, используемого при передаче в этих сетях - множественного доступа абонентов к общему каналу связи. Множественный доступ предполагает разделение ресурсов канала между абонентами. Такое разделение каналов может быть частотным, временным или кодовым. Множественный доступ применяется и в проводных и в беспроводных сетях. Различают бесконфликтные и конфликтные методы доступа. Бесконфликтные методы множественного доступа используют в сотовых сетях стандартов AMPS, NAMPS, GSM (в режиме передачи речи) и других. Среди конфликтных методов доступа широкое распространение получил стандарт для локальных проводных сетей IEEE 8023 (Ethernet) и стандарт для локальных беспроводных сетей - IEEE 802.11. В настоящее время идет активное внедрение стандарта для беспроводных MAN-сегеЙ — IEEE 802,16. Данный стандарт, как и стандарт для проводных сетей IEEE 802.14, характеризуется наличием центральной станции. Особенностью стандартов IEEE 802.16 и IEEE 802.14 д ля сетей с центральной станцией (централизованные сета) является использование конкурентного интервала в процессе передачи. В конкурентном интервале абоненты передают запросы к центральной станции на предоставление канальных ресурсов. Абонент передает запрос случайным образом. Если передачи запросов от разных абонентов накладываются друг на Друга, то возникает конфликт. В этом случае абоненты делают повторную передачу в соответствии с определенными правилами. И так далее. Ясно, что правила управления передачей в конкурентном интервале могут оказывать большое влияние на задержку передачи запроса. А это, в конечном счете, повлияет на время, которое затратит абонент на передачу данных. Диссертационная работа посвящена исследованию алгоритмов управления передачей в конкурентном интервале, которые принято называть алгоритмами случайного множественного доступа. Основная идея метода случайного множественного доступа (СМД) предложена в начале 70-х годов прошлого века и развита в работах Капетанакиса, Цыбакова, Михайлова, Месси и др. Специально для централизованных сетей в 1999 году Блондн и другими разработан алгоритм СМД, получивший название «FS-ALOHA».

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

Задачами диссертационного исследования являются:

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

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

3). Анализ предложенных алгоритмов дм различных видов входного потока.

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

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

- метод расчета скорости и метод расчета распределения вероятностей для задержки запроса в алгоритме FS-ALOHA в канапе с шумом;

- алгоритм управления передачей запроса в конкурентном интервале централизованных сетей - Multi FS-ALOHA;

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

Научная новизна.

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

2). Вычислено критическое значение вероятности ложного конфликта, при котором скорость для оптимальных относительно скорости параметров алгоритма FS-ALOHA равна нулю.

3). Разработан метод расчета распределения вероятностей для задержки передачи запроса в алгоритме FS-ALOHA в канале с шумом.

4). Предложен класс алгоритмов СМД С очередью для централизованных сетей.

5). Разработан метод вычисления скорости алгоритма для подкласса алгоритмов СМД из предложенного класса. Разработан метод определения параметров алгоритма из данного подкласса, при которых его скорость максимальна. Разработан метод вычисление скорости при входном потоке со всплесками интенсивности для алгоритмов из подкласса. -------

Практическая ценность.

1). Предложена модификация алгоритма FS-ALOHA - алгоритм Multi FS-ALOHA. Модификация решила проблему уменьшения скорости в алгоритме FS-ALOHA при увеличении размера конкурентного интервала.

2). Предложены древовидные алгоритмы СМД для централизованных сетей. Данные алгоритмы обладают большей скоростью в сравнении с Multi FS-ALOHA, но при этом имеют н большею вычислительную сложность.

3). Получены численные значения характеристик алгоритма FS-ALOHA в канале с шумом. Численные характеристики рассчитаны для предложенных алгоритмов СМД при различных значениях их параметров.

4). Произведено сравнение алгоритма ВЕВ, используемого в стандарте IEEE 802.16, с одним из древовидных алгоритмов СМД для централизованных сетей.

Внедрение н реализация результатов работы. Результаты диссертационной работы получены при выполнении госбюджетной научно-исследовательской работы (РК 01200501975), проведенной Санкт-Петербургским государственным университетом аэрокосмического приборостроения.

Полученные в диссертационной работе результаты используются в учебном процессе кафедры информационных систем ГУАП и кафедры АСОИУ ЛЭТИ.

Апробация работы. Основные результаты работы докладывались на пятой научной сессии аспирантов ГУАП (Санкт-Петербург, 12 — 18 апреля 2002г.), на шестой научной сессии аспирантов ГУАП (Санкт-Петербург, 14 - 18 апреля 2003г.), на седьмой научной сессии аспирантов ГУАП (Санкт-Петербург, 12 - 16 апреля 2004г.), на конференции «Информационные технологии в науке, образовании, искусстве» (Санкт-Петербург, 29 — 31 марта 2005г.), на восьмой научной сессии ГУАП (Санкт-Петербург, 11 — 15 апреля 2005г.), на политехническом симпозиуме «Молодые ученые - промышленности Северо-Западного региона» (декабрь 2005 г.), на научной сессии ГУАП, посвященной всемирному Дню авиации и космонавтики и 65-летию ГУАП (Санкт-Петербург, 10 - 14 апреля 2006г.), на международной научной конференции IEEE "ISCE 2006" (Санкт-Петербург, 28 июня - 1 июля 2006г.). Зарегистрированы программные разработки в отраслевом фонде алгоритмов и программ: регистрационный номер Гос. ФАП 50200501138,2005 г.; регистрационный номер Гос. ФАП 50200501139, 2005 г.; регистрационный номер Гос. ФАП 50200501140,2005 г.

Публикации. По теме диссертационной работы опубликовано 13 печатных

работ.

Объем и структура работы. Диссертационная работа состоит из введения, 4 разделов, заключения, списка использованных источников и 4 приложений. Работа содержит 151 страницу машинописного текста, включая 40 рисунков, и б рисунков на 3 страницах. В списке используемой литературы 79 наименований.

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

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

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

Структура централизованной системы предполагает разделение общего канала связи между абонентскими станциями (АС) и центральной станцией (ЦС) на два подканала: восходящий канал и нисходящий канал. Восходящий канал множественного доступа служит для передачи данных от абонентских станций к центральной станции. АС «не слышат» друг друга. Коммуникация между ними осуществляется посредством ЦС. Нисходящий канал предназначен для передачи данных от ДС к АС. Передача происходит в широковещательном режиме. Поэтому ее «слышат» все АС.

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

< ■■ ■■" Ниемодящ^й канал--■ г« ■■ ■ Восходящий канал............>.

азгаговок интервал передачи пакетов конкурент интервал интервал передачи пакетов вреа*

Рисунок 1 — Общая структура кадра

Модель СМД централизованной сети состоит в следующем:

- рассматривается только конкурентный интервал;

- в слотах возможна либо ситуация «пусто» — передачи отсутствовали, либо ситуация «успех» - произошла успешная передача, либо ситуация «конфликт» -произошла одновременная передача двух или более запросов;

- АС получают информацию о ситуациях в слотах в начале следующего кадра;

- каждая АС не может иметь больше одного запроса в один момент времени.

В качестве модели шумов используется модель ложных конфликтов, полностью определяемая двумя вероятностями: q„- вероятность, с которой ЦС из-за шума воспринимает слот с ситуацией «пусто» как слот с ситуацией «конфликт» и <7, - вероятность, с которой ЦС из-за шума воспринимает слот с ситуацией «успех» как слот с ситуацией «конфликт». Шумы в нисходящем канале отсутствуют (в предположении большой мощности передатчика ЦС).

Применяются две модели поступления запросов в систему. В первой модели число поступающих запросов распределено по закону Пуассона с параметром Л, определяющим интенсивность поступления запросов в расчете на кадр. Вторая модель описывается дискретным пачечным марковским входным процессом (D-ВМАР).

Алгоритм СМД рассматривается как алгоритм, решающий две задачи: -

- задача управления передачей новых запросов (за данную задачу отвечает алгоритм доступа к каналу)',

- задача управления повторной передачей запросов после возникновения конфликтов (эту задачу решает алгоритм разрешения конфликтов (АРК)).

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

Задержкой запроса называется время от момента возникновения запроса до момента его успешной передачи (единица времени - один кадр).

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

Средней виртуальной задержкой запроса называется величина

DSlim supМ\5,].

Скорость R алгоритма СМД — это верхняя грань интенсивности входного потока, для которой средняя задержка конечна:

R ± supfa I < 00),

где D(a) — средняя задержка при интенсивности а запросов входного потока в расчете на слот конкурентного интервала.

В разделе 2 рассматривается известный алгоритм СМД с очередью для централизованных сетей - FIFO by Sets ALOHA (FS-ALOHA). Алгоритм является базовым по отношению к другим алгоритмам СМД с очередью, которые исследуются в диссертационной работе.

В FS-ALOHA все L слотов конкурентного интервала разбиты на два непересекающихся подмножества. Первое подмножество содержит S слотов доступа, второе— N=L-S слотов разрешения конфликтов. Первую попытку передачи запроса абоненты производят случайным образом с помощью равномерного выбора в одном из S слотов доступа. Запросы, которые не были успешно переданы в слотах доступа одного кадра, образуют конфликтное подмножество (КГГ). Данное КП становится в конец очереди из таких же КП, которые ожидают обслуживания. Передача запросов из КП происходит случайным образом с помощью равномерного выбора в одном из N слотов разрешения конфликтов. КП находится в начале очереди до тех пор, пока все его запросы не будут успешно переданы. Если очередь пустая, то все L слотов конкурентного интервала используются для передачи новых запросов. Пример передачи запросов с помощью алгоритма FS-ALOHA показан на рисунке 2. На рисунке использованы следующие обозначения: у - успешная передача, к — конфликтная передача, A¡ — абонент с номером / и овал с цифрами -КП с номерами абонентов. -

S=2 3

Для вычисления скорости FS-ALOHA функционирование алгоритма можно описать в терминах теории систем массового обслуживания как очередь FIFO GI/GI/1. Условие устойчивости данной системы:

—►

время

Рисунок 2 - Пример функционирования алгоритма FS-ALOHA

где - это среднее количество КП, образующихся в течение одного кад-

ра. Л интенсивность обслуживания может быть вычислена как среднее

количество КП, которые обслуживаются за один кадр, при условии, что в системе присутствует хотя бы одно КП. В диссертационной работе условие устойчивости (1) принимает следующий вид:

ТОи0,*,)<1, (2)

где Величина Т, - это математическое ожидание

/

числа кадров, необходимых для обслуживания одного КП, содержащего ) запросов. Вероятность - это вероятность того, что в канале с пуассонов-ским входным потоком интенсивности Л запросов в расчете на кадр и с ложными конфликтами, определяемыми вероятностями на 5 слотах доступа образуется КП, содержащее ] запросов.

Предельная интенсивность , при которой система устойчива, может быть определена как максимальная интенсивность л, при которой выполняется неравенство (2). Тогда скорость алгоритма Рв-ЛЬОНА вычисляется так:

Из работ Блонди следует, что алгоритм БЗ-ЛЬОНА имеет максимальную скорость в бесшумном канале при параметрах ¿ = 1 и ^=2. В диссертационной работе показано, что это справедливо и в канале с шумом. Именно для параметров 5 = 1 и N—2 вычислено критическое значение д, вероятности ложного конфликта, при котором скорость Р5-АШНА равна нулю, то есть при одинаковой вероятности ложных конфликтов <?=■=?(,=>?, скорость равна нулю, если выполняется следующее неравенство:

■ <3)

Более сложный подход к описанию функционирования алгоритма FS-ALOHA позволяет найти распределение вероятностей для задержки запроса.

Процесс функционирования алгоритма FS-ALOHA описывается многомерным марковским процессом, состоящим из трех компонент:

(G,r,fe), (4)

где О - количество КП, г — количество запросов в обслуживаемом КП. Третья компонента представляет собой вектор ¿ = где Ъ, ~ количество запросов

в (-том КП.

В диссертационной работе доказано, что если многомерный марковский процесс {G,r,b) описать двумерным процессом (С,г), то для стационарного режима двумерный процесс тоже будет марковским. Метод расчета распределения вероятностей для задержки запроса основан на анализе именно двумерной марковской иепн. При этом рассчитывается стационарное распределение вероятностей для состояний системы с помощью матрицы переходных вероятностей марковской цепи.

В разделе 3 представлены алгоритмы, которые эффективны для передачи запросов при большом размере конкурентного интервала. Алгоритмы разработаны на базе FS-ALOHA. Из работ Блонди известно, что при увеличении размера конкурентного интервала эффективность алгоритма FS-ALOHA относительно задержки резко снижается. В разделе 3 представлены алгоритмы, решающие проблему снижения эффективности. Первым рассматривается алгоритм, функционирование которого упрощенно можно описать как параллельную работу нескольких алгоритмов FS-ALOHA с одним слотом доступа и двумя слотами разрешения конфликтов. В этом алгоритме количество слотов разрешения конфликтов N, зависит от числа КП в очереди в кадре с номером f. В диссертационной работе приводятся строгие правила работы данного алгоритма, который получил название Multi FS-ALOHA. Пример его функционирования изображен на рисунке 3 для размера L = 5 конкурентного интервала и при максимальном количестве N=4 слотов разрешения конфликтов.

Рисунок 3 - Пример функционирования алгоритма Multi FS-ALOHA

Для нахождения скорости Multi FS-ALOHA функционирование алгоритма можно описать в терминах теории систем массового обслуживания как очередь FIFO Gl/GI}{N! 2). В этом случае условие устойчивости системы задается в виде неравенства

—

время

ч N

где х — интенсивность входного потока запросов в расчете на слот доступа, а 7*0,определяется так:

+ Тае-д0 + Т^'д,. (б)

/■3 } *

Таким образом, скорость алгоритма вычисляется следующим образом: Я = где - это максимальная величина х, для которой выполняется не-

равенство (5}.

С целью нахождения оптимальных параметров которые максимизи-

руют скорость алгоритма МиШ БЗ-АШНА при фиксированном размере £ конкурентного интервала, определяется величина 1'— такая величина х, при которой достигает максимума следующее отношение:

1 + 27Ч*,?(|,91)' ('>

Причем величина х' в (7) находится в предположении, что параметры алгоритма 5 и N могут быть сколь угодно большими и выбраны так, чтобы максимизировать (7).

Искомые параметры 5 и N для заданной величины I вычисляются с помощью следующей системы уравнений:

В третьем разделе рассматриваются алгоритмы СМД для централизованных сетей с использованием древовидных АРК. В данных алгоритмах СМД для обслуживания одного КП выделяется только один слог из слотов разрешения конфликтов. Также как и в МиШ РЯ-АЬОНА, в одном кадре может обслуживаться сразу несколько КП. Обслуживание запросов из КП происходит с помощью древовидного АРК того или иного вида. Алгоритмы СМД дня централизованных сетей, в которых используются древовидные АРК, в диссертационной работе названы древовидными алгоритмами СМД. Вид АРК является отличительной чертой одного древовидного алгоритма СМД от другого. Скорость древовидных алгоритмов СМД и их оптимальные параметры рассчитываются тем же методом, что и в алгоритме МиШ РБ-А1,ОНА (получены условие устойчивости аналогичное (5) и система уравнений аналогичная (8)). Результаты расчета показаны на рисунке 4.

Рисунок 4 - Зависимость скорости МиШ АЬОНА, РБ-ЛЬОНА и древовидного алгоритма от размера 1 конкурентного интервала

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

В разделе 4 обобщены результаты в двух направлениях. Первое направление — предложен класс алгоритмов СМД с очередью КП для централизованных сетей, который включает в себя как алгоритмы с очередью КП, рассмотренные в разделах 2 и 3, так и другие алгоритмы. Второе направление - рассматривается входной поток 1>ВМАР, частным случаем которого является пуассоновский входной поток, исследования д ля которого произведены в предыдущих разделах.

Предложенный класс алгоритмов СМД для централизованн ых сетей является достаточно широким. Он включает в себя алгоритм Рв-АЬОНА, а также алгоритмы СМД, которые характеризуются тем, что КП образуется из запросов попавших в конфликт на одном слоте, и другие алгоритмы СМД для централизованных сетей (рис. 5). Для конкретных условий передачи из предложенного класса можно выбрать весьма эффективный алгоритм СМД. Например, для децентрализованных сетей разработан алгоритм дробления, обладающий максимальной величиной скорости Я = 0.487 среди известных алгоритмов СМД. В предложенном классе имеется подобный алгоритм, который в диссертационной работе условно называется ана-

а

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

В предложенном классе алгоритмов в произвольном кадре с номером ( все £ слотов конкурентного интервала разбиты на два непересекающихся подмножества, первое из которых содержит слотов доступа, а второе - ДГ, = £ - $ слотов разрешения конфликтов. Причем слоты доступа всегда находятся в начале конкурентного интервала. Параметр алгоритма 5 > 1 определяет минимальное допустимое значение 5,. Поэтому для любого кадра / верно неравенство 1 < 5 < < X. Параметр алгоритма N> I определяет максимальное допустимое значение М- Для любого кадра/выполняется соотношение 0 < Л*1, < N <£. Все слоты доступа разбиваются на группы слотов таким образом, что они образуют -интервалы формирования конфликтного подмножества. Запросы, попавшие в конфликт на интервале формирования КП, формируют конфликтное подмножество, которое становится в очередь КП. Все слоты разрешения конфликтов разбиваются на группы слотов таким образом, что они образуют интервалы обслуживания конфликтного подмножества, в которых происходит передача запросов из одного КП.

Условие устойчивости для подкласса алгоритмов (аналогичное (5)) имеет

Рисунок 5 - Структура класса алгоритмов СМД с очередью

вид:

где Г"<» определяется формулой Т"(х)^^^{передавалось Iг} запросов, } запросов образована ¡СП), (Ю)

1 - размер интервала формирования КП, л - размер интервала обслуживания КП.

В формуле (10) величина ту — это математическое ожидание числа кадров, необходимых для обслуживания одного КП, содержащего } запросов. Выражения дня величин Т^ определяются конкретным алгоритмом а, в соответствии с которым происходит разрешение конфликта для абонентов из КП.

Таким образом, скорость алгоритма вычисляется следующим образом: л) = / ь, где - это максимальная величина для которой выполняется неравенство (9).

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

г+пГ(х)

(И)

Величина х' в (11) находится в предположении (также как в (7)), что параметры алгоритма $ к N могут быть сколь угодно большими и выбраны так, чтобы максимизировать (11).

Затем вычисляются непосредственно сами искомые параметры 5 и N для заданной величины £ с помощью следующей системы уравнений:

(12)

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

ловле устойчивости (9). В этом случае величина Т*(х) определяется таким образом:

, (13)

j-z ■>•< 1 • I

где d — количество состояний марковской цепи процесса D-BMAP, v„ — стационарная вероятность нахождения марковской цепи в состоянии m (в котором интенсивность входного потока в расчете на один кадр - Л,, а в расчете на слот дос-

4

тупа— xm =A,!S ). Величина х представляет собой сумму; *=£• Вероятность

»-I

Pt(c,i,s)- это вероятность успешной передачи с запросов на интервале, состоящем из s слотов, при условии, что в этом интервале всего передавалось случайным образом j запросов.

С помощью формул (13) и (9) в диссертационной работе произведен расчет скорости древовидного модифицированного алгоритма со стеком бесконечной глубины для канала со всплесками входной интенсивности. Полученные результаты свидетельствуют о высокой эффективности древовидного алгоритма СМД в таком канале. Кроме того, для канала со всплесками входной интенсивности продемонстрировано, что алгоритмы из предложенного класса позволяют достигать лучших характеристик по задержке, чем алгоритм BEB, используемый в стандарте IEEE 802.16. Преимущество показано на примере процесса D-BMAP, в котором имеются два состояния марковской цепи - состояние всплеска и нормальное состояние. Данный процесс задается матрицей переходных вероятностей, интенсивностью Л, пуассоновского входного потока в первом состоянии (состояние всплеска) марковской цепи и интенсивностью Л^ пуассоновского входного потока во втором состоянии (нормальное состояние) марковской цепи. Интенсивности Л, и ylj определены в расчете на кадр. Если цепь находится в состоянии <", то интенсивность пуассоновского входного потока будет а, = Л, / L запросов в расчете на один слот. Оценки средней задержки, найденные с помощью имитационного моделирования, изображены на рисунке 6.

Рисунок 6 - Зависимость средней задержки (измеряется в кадрах) от интенсивности а, входного потока в состоянии всплеска для древовидного модифицированного алгоритма со стеком бесконечной глубины и алгоритма ВЕВ

Результаты, показанные на рисунке 6, демонстрируют зависимость средней задержки от величины щ при фиксированной величине л, = 0,1. Вектор стационарных вероятностей для марковской цепи представляет собой следующий вектор: V - (0,1 0,9). На рисунке б показано, что при всплесках интенсивности входного потока древовидный алгоритм СМД имеет лучше показатели средней задержки, чем алгоритм ВЕВ. Эффективность древовидных алгоритмов в канале со всплесками, которая подтверждается в частности данным примером, имеет большое значение на практике, где в произвольный момент времени у абонентов может возникнуть большое количество новых запросов.

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

Приложения. В приложении А даны аналитические выражения для вычисления вероятностей, используемых при анализе алгоритма РЭ-ЛЬОНА. В остальных приложениях приведены аналитические выражения, определяющие среднее количество кадров, необходимых для обслуживания одного КП с заданным числом запросов: в приложении Б — для алгоритма РБ-АЬОНА, в приложении В — для алгоритма МиМ Р&АЬОНА и в приложении Г — для модифицированного алгоритма со стеком бесконечной глубины.

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

1. Исследован базовый алгоритм FS-ALOHA с очередью для канала с шумом. Получены аналитические выражения для численного расчета скорости FS-ALOHA. Выявлены оптимальные относительно скорости параметры алгоритма и доказано, что при достижении уровнем шума определенной величины, скорость алгоритма станет равной нулю. Разработан метод расчета распределения вероятностей для задержки запроса. Показано преимущество в цепом алгоритма FS-ALOHA перед В ЕВ, который используется в стандарте ШЕЕ 802.16.

2. Предложен алгоритм, являющийся модификацией алгоритма FS-ALOHA -Multi FS-ALOHA. В отличие от FS-ALOHA, в алгоритме Mult! FS-ALOHA не снижается скорость при увеличении размера конкурентного интервала. Получены аналитические выражения для численного расчета скорости алгоритма Multi FS-ALOHA в канале с шумом. Указан способ определения параметров алгоритма, при которых его скорость максимальна. Показано, что алгоритм FS-ALOHA более подвержен воздействию шумов в сравнении с Multi FS-ALOHA.

3. Предложены древовидные алгоритмы для централизованных сетей. Алгоритмы являются аналогами высокоскоростных древовидных алгоритмов с оконным доступом для децентрализованных сетей. Древовидные алгоритмы во многом схожи с Multi FS-ALOHA, но благодаря использованию древовидного АРК имеют более высокую скорость. Но при этом Multi FS-ALOHA имеет меньшую вычислительную сложность. Получены аналитические выражения для численного расчета скорости древовидных алгоритмов и определения их оптимальных параметров. Эффективность использования таких алгоритмов продемонстрирована на примере модифицированного алгоритма со стеком бесконечной глубины. Алгоритм показал высокие результаты, как относительно скорости, так и относительно средней задержки. Особенно эффективен алгоритм в канале со всплесками входной интенсивности.

4. Предложен класс алгоритмов СМД с очередью для конкурентного канала централизованных сетей. Данный класс содержит широкий спектр алгоритмов от базового алгоритма с очередью (FS-ALOHA) до аналога алгоритма дробления для централизованных сетей. Разработан метод вычисления скорости для алгоритмов СМД, входящих в подкласс алгоритмов введенного класса. Разработан метод определения оптимальных относительно скорости параметров алгоритма из подкласса алгоритмов СМД. Получен метод вычисления скорости алгоритма из подкласса алгоритмов СМД для различных видов входных потоков, описываемых марковской цепью (D-BMAP).

5. Разработан комплекс программ имитационного моделирования И численного расчета скорости для предложенных алгоритмов.

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

1. Кобляков В А, Вычисление коэффициента полезного использования канала для упрощенной модели протокола TCP// Сб. тез. докл. 5 научн. сессии аспирантов ГУАП - СПб.: ГУАП, 2002, С. 237-241 ■

2. Кобляков ВА. Исследование алгоритма разрешения конфликтов FS-ALOHA в канале с ложными конфликтами// Сб. тез. докл. 6 научн. сессии аспирантов ГУАП - СПб.: ГУАП, 2003, С. 166-168.

3. Кобляков В А. Исследование устойчивости алгоритма разрешения конфликтов FS-ALOHA в канале с ложными конфликтами// Сб. тез. докл. 7 научн. сессии аспирантов ГУАП - СПб.: ГУАП, 2004.

4. Кобляков В.А. Исследование производительности алгоритмов случайного доступа для простой модели MAC подуровня в беспроводных централизованных сетях// Восьмая научная сессия ГУАП: Сб. докл./ ГУАП. СПб., 2005.

5. Кобляков ВА. Комбинированный алгоритм случайного доступа для беспроводных централизованных сетей// Восьмая научная сессия ГУАП: Сб. дохл,/ ГУАП. СПб., 2005.

6. Вин ель A3., Кобляков ВА. Алгоритмы случайного множественного доступа для централизованных беспроводных сетей передачи данных// Молодые ученые - промышленности Северо-Западного региона. Материалы семинаров политехнического симпозиума/ Издательство Политехнического университета, 2005.

7. Кобляков ВА. Программа демонстрации работы протокола TCP и исследования его числовых характеристик/ Регистрационный номер Гос. ФАЛ 50200501138,2005.

§. Кобляков ВА. Программа исследования производительности алгоритмов случайного доступа в централизованных компьютерных сетях/ Регистрационный номер Гос. ФАП 50200501139,2005.

9. Кобляков ВА. Программа исследования производительности алгоритмов случайного доступа для простой модели подуровня управления доступом к среде/ Регистрационный номер Гос. ФАП 50200501140,2005.

10. Кобляков В.А. Аналог алгоритма дробления для централизованных сетей// Научная сессия ГУАП, посвященная всемирному Дню авиации и космонавтики и 65-летию ГУАП: Сб.доклУ ГУАП. СПб., 2006.

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

12. Винель A.B., Кобляков В.А. Разработка и анализ алгоритмов случайного множественного доступа для беспроводных централизованных сетей передачи данных// Информационно-телекоммуникационные системы — Сборник материалов Всероссийского конкурса инновационных проектов аспирантов и студентов по

is

приоритетному направлению развития науки и техники/ Под ред. А.О. Сергеева, Москва, ГНИИ ИТТ Информика, 2006, С. 149-150.

13. Винель A.B., Кобляков В А., Тюрликов A.M. Класс алгоритмов случайного множественного доступа с очередью для централизованных сетей передачи данных// Информационные технологии. 2007. №5. Принято в печать.

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. _Тираж 100 экз. Заказ Jfe Si С

Отпечатано в отделе оперативной полиграфии ГУАП

190000, Санкт-Петербург, ул.Б.Морская,67

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

Введение.

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

1.2 Особенности МАС-уровня централизованных сетей.

1.2.1 Общие сведения.

1.2.2 Структура МАС-уровня.

1.2.3 Соединения и сервисные потоки.

1.2.4 Общая структура кадров IEEE 802.16.

1.2.5 Пакеты МАС-уровня.

1.2.6 Принцип предоставления канальных ресурсов.

1.2.7 Механизмы подтверждение приема и быстрой обратной связи.

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

1.3.1 Модель канала.

1.3.1.1 Восходящий и нисходящий канал. Структура кадра.

1.3.1.2 Модель шумов.

1.3.2 Модель входного потока.

1.3.2.1 Общие замечания.

1.3.2.2 Дискретный пачечный марковский входной процесс (D-BMAP).

1.3.2.3 Пуассоновский входной процесс с дискретным временем.

1.3.2.4 Пуассоновский входной процесс с дискретным временем, модулируемый цепью Маркова.

1.3.2.5 Особенности D-BMAP как входного процесса.

1.3.2.6 Модели абонентов.

1.4 Алгоритмы случайного множественного доступа

1.4.1 Определение алгоритма СМД. Задержка и скорость.

1.4.2 Алгоритмы ALOHA и Slotted ALOHA.

1.4.3 Алгоритм Binary Exponential Backoff.

1.4.4 Алгоритмы СМД с очередью.

1.4.5 Древовидные АРК.

1.5 Исследование алгоритма Binary Exponential Backoff.

1.5.1 Допущения имитационного моделирования.

1.5.2 Канал со всплесками интенсивности входного потока.

1.5.3 Канал с ложными конфликтами.

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

2 Анализ базового алгоритма СМД с очередью.

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

2.2 Описание алгоритма FS-ALOHA.

2.3 Вычисление скорости алгоритма FS-ALOHA в канале с ложными конфликтами.

2.3.1 Допущения аналитической модели.

2.3.2 Метод вычисления скорости.

2.3.3 Влияние шумов на скорость при разных параметрах алгоритма.

2.3.4 Вычисление скорости при параметрах алгоритма S=\ и N=2.

2.4 Вычисление распределения вероятностей для задержки запроса в алгоритме FS-ALOHA.

2.4.1 Допущения аналитической модели.

2.4.2 Марковская цепь. Укрупнение состояний.

2.4.3 Марковская цепь с укрупненными состояниями.

2.4.4 Метод вычисления распределения вероятностей для задержки запроса.

2.4.5 Сравнение результатов аналитического моделирования и имитационного моделирования.

2.5 Сравнение алгоритмов FS-ALOHA, Slotted ALOHA и ВЕВ.

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

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

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

3.2 Анализ алгоритма Multi FS-ALOHA.

3.2.1 Описание алгоритма Multi FS-ALOHA.

3.2.2 Вычисление скорости алгоритма Multi FS-ALOHA в канале с ложными конфликтами.

3.2.2.1 Метод вычисления скорости.

3.2.2.2 Метод определения оптимальных параметров алгоритма для максимизации скорости.

3.2.2.3 Результаты вычисления скорости.

3.2.3 Оценка характеристик задержки запроса.

3.3 Анализ древовидных алгоритмов СМД.

3.3.1 Описание древовидных алгоритмов СМД.

3.3.2 Вычисление скорости древовидных алгоритмов.

3.3.2.1 Метод вычисления скорости.

3.3.2.2 Метод определения оптимальных параметров алгоритма для максимизации скорости.

3.4 Оценка характеристик задержки запроса.

3.5 Сравнение алгоритмов СМД с очередью относительно скорости и распределения вероятностей для задержки.

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

4 Класс алгоритмов СМД с очередью.

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

4.2 Описание класса алгоритмов СМД с очередью.

4.3 Анализ алгоритмов СМД с очередью при пуассоновском входном потоке

4.3.1 Описание подкласса алгоритмов СМД с очередью.

4.3.2 Метод вычисления скорости для заданных параметров алгоритма.

4.3.3 Метод определения оптимальных параметров алгоритма S и N для максимизации скорости при заданном размере конкурентного интервала.

4.4 Метод вычисления скорости при входном процессе D-BMAP.

4.5 Результаты вычисления скорости при входном потоке со. всплесками интенсивности.

4.6 Результаты для средней задержки при входном потоке со. всплесками интенсивности.

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

Актуальность темы. Активное развитие сетей передачи данных обуславливает необходимость исследования распространенного метода, используемого при передаче в этих сетях - множественного доступа абонентов к общему каналу связи. Множественный доступ предполагает разделение ресурсов канала между абонентами. Такое разделение каналов может быть частотным, временным или кодовым. Множественный доступ применяется и в проводных и в беспроводных сетях. Различают бесконфликтные и конфликтные методы доступа. Бесконфликтные методы множественного доступа используют в сотовых сетях стандартов AMPS, NAMPS, GSM (в режиме передачи речи) и других. Среди конфликтных методов доступа широкое распространение получил стандарт для локальных проводных сетей IEEE 802.3 (Ethernet) и стандарт для локальных беспроводных сетей - IEEE 802.11. В настоящее время идет активное внедрение стандарта для беспроводных MAN-сетей - IEEE 802.16. Данный стандарт, как и стандарт для проводных сетей IEEE 802.14, характеризуется наличием центральной станции. Особенностью стандартов IEEE 802.16 и IEEE 802.14 сетей с центральной станцией (централизованные сети) является использование конкурентного интервала в процессе передачи. В конкурентном интервале абоненты передают запросы к центральной станции на предоставление канальных ресурсов. Абонент передает запрос случайным образом. Если передачи запросов от разных абонентов накладываются друг на друга, то возникает конфликт. В этом случае абоненты делают повторную передачу в соответствии с определенными правилами. И так далее. Ясно, что правила управления передачей в конкурентном интервале могут оказывать большое влияние на задержку передачи запроса. А это, в конечном счете, повлияет на время, которое затратит абонент на передачу данных. Диссертационная работа посвящена исследованию алгоритмов управления передачей в конкурентном интервале, которые принято называть алгоритмами случайного множественного доступа. Основная идея метода случайного множественного доступа предложена в начале 70-х годов прошлого века. Максимальное число работ в области СМД относится к середине 80-х годов прошлого века. В последующие пятнадцать лет интерес к исследованиям в этом направлении постепенно уменьшался. Тем не менее, появление беспроводных сетей привело к тому, что в последние годы снова наблюдается тенденция к увеличению числа работ, посвященных СМД.

Первым алгоритмом случайного множественного доступа был алгоритм ALOHA. В стандартах IEEE 802.16 и IEEE 802.14 в качестве алгоритма СМД применяется модификация ALOHA - алгоритм Binary Exponential Backoff (ВЕВ). Алгоритм FS-ALOHA, предложенный специально для централизованных сетей, во многом превосходит алгоритм ВЕВ в характеристиках задержки передачи и в тоже время его реализация не намного сложнее, чем реализация ВЕВ. В FS-ALOHA все множество запросов, попавших в конфликт, разбивается на подмножества, образующие очередь. Запросы из одного подмножества обслуживаются отдельно от другого подмножества. Алгоритм FS-ALOHA представляет собой простейший способ управления передачей запросов с использованием очереди. Алгоритм является базовым по отношению к другим алгоритмам СМД с очередью, которые исследуются в данной работе.

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

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

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

2). Предложить алгоритмы СМД, обеспечивающие меньшую задержку при доставке запроса, чем ранее известные алгоритмы.

3). Проанализировать предложенные алгоритмы для различных видов входного потока.

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

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

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

2). Вычислено критическое значение вероятности ложного конфликта, при котором скорость для оптимальных относительно скорости параметров алгоритма FS-ALOHA равна нулю.

3). Разработан метод расчета распределения вероятностей для задержки передачи запроса в алгоритме FS-ALOHA в канале с шумом.

4). Предложен класс алгоритмов СМД с очередью для централизованных сетей.

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

Практическая ценность и реализация результатов.

1). Предложена модификация алгоритма FS-ALOHA - алгоритм Multi FS-ALOHA. Модификация решила проблему уменьшения скорости в алгоритме FS-ALOHA при увеличении размера конкурентного интервала.

2). Предложены древовидные алгоритмы СМД для централизованных сетей. Данные алгоритмы обладают большей скоростью в сравнении с Multi FS-ALOHA, но при этом имеют и большею вычислительную сложность.

3). Получены численные значения характеристик алгоритма FS-ALOHA в канале с шумом. Численные характеристики рассчитаны для предложенных алгоритмов СМД при различных значениях их параметров.

4). Произведено сравнение алгоритма ВЕВ, используемого в стандарте IEEE 802.16, с одним из древовидных алгоритмов СМД для централ изованных сетей.

Результаты диссертационной работы получены при выполнении госбюджетной научно-исследовательской работы (РК 01200501975), опубликованы и представлены в отчетах НИР. Эти результаты использованы в учебном процессе кафедры информационных систем ГУАП и кафедры АСОИУ ЛЭТИ. Использование результатов диссертационной работы подтверждается соответствующими актами.

Апробация работы. Основные результаты работы докладывались на пятой научной сессии аспирантов ГУАП (Санкт-Петербург, 12-18 апреля 2002г.), на шестой научной сессии аспирантов ГУАП (Санкт-Петербург, 14-18 апреля 2003г.), на седьмой научной сессии аспирантов ГУАП (Санкт-Петербург, 12-16 апреля 2004г.), на конференции «Информационные технологии в науке, образовании, искусстве» (Санкт-Петербург, 29-31 марта 2005г.), на восьмой научной сессии ГУАП (Санкт-Петербург, 11-15 апреля 2005г.), на политехническом симпозиуме «Молодые ученые - промышленности Северо-Западного региона» (декабрь 2005 г.), на научной сессия ГУАП, посвященная всемирному Дню авиации и космонавтики и 65-летию ГУАП (Санкт-Петербург, 10-14 апреля 2006г.), на межи дународной научной конференции IEEE "ISCE 2006" (Санкт-Петербург, 28 июня - 1 июля 2006г.). Зарегистрированы программные разработки в отраслевом фонде алгоритмов и программ: регистрационный номер Гос. ФАП 50200501138, 2005 г.; регистрационный номер Гос. ФАП 50200501139, 2005 г.; регистрационный номер Гос. ФАП 50200501140,2005 г.

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

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

- метод расчета скорости и метод расчета распределения вероятностей для задержки запроса в алгоритме FS-ALOHA в канале с шумом;

- алгоритм управления передачей запроса в конкурентном интервале централизованных сетей - Multi FS-ALOHA;

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

Объем и структура работы. Диссертационная работа состоит из введения, 4 разделов, заключения, списка использованных источников и 4 приложений. Работа содержит всего 154 страницы, в том числе 151 страница машинописного текста, включая 40 рисунков, и 6 рисунков на 3 страницах. В списке используемой литературы 79 наименований.

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

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

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

3). Разработан метод определения параметров алгоритма, которые максимизируют скорость алгоритма (метод для подкласса алгоритмов СМД).

4). Разработан метод вычисления скорости алгоритма для подкласса алгоритмов СМД при входном потоке, который описывается входным процессом D-ВМАР.

5). Выполнен сравнительный анализ численных характеристик алгоритмов СМД в канале со всплесками интенсивности входного потока. Показано, что в таком канале древовидный модифицированный алгоритм со стеком бесконечной глубины значительно превосходит алгоритм Multi FS-ALOHA относительно скорости. Также показано превосходство древовидного алгоритма в величинах средней задержки перед алгоритмом ВЕВ.

ЗАКЛЮЧЕНИЕ

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

Получены следующие основные результаты.

1). Исследован базовый алгоритм FS-ALOHA с очередью для канала с шумом. Получены аналитические выражения для численного расчета скорости FS-ALOHA. Выявлены оптимальные относительно скорости параметры алгоритма и доказано, что при достижении уровнем шума определенной величины, скорость алгоритма станет равной нулю. Разработан метод расчета распределения вероятностей для задержки запроса. Показано преимущество в целом алгоритма FS-ALOHA перед ВЕВ, который используется в стандарте IEEE 802.16.

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

3). Предложены древовидные алгоритмы для централизованных сетей. Алгоритмы являются аналогами высокоскоростных древовидных алгоритмов с оконным доступом для децентрализованных сетей. Древовидные алгоритмы во многом схожи с Multi FS-ALOHA, но благодаря использованию древовидного АРК имеют более высокую скорость. Но при этом Multi FS-ALOHA имеет меньшую вычислительную сложность. Получены аналитические выражения для численного расчета скорости древовидных алгоритмов и определения их оптимальных параметров. Эффективность использования таких алгоритмов продемонстрирована на примере модифицированного алгоритма со стеком бесконечной глубины. Алгоритм показал высокие результаты, как относительно скорости, так и относительно средней задержки. Особенно эффективен алгоритм в канале со всплесками входной интенсивности.

4). Предложен класс алгоритмов СМД с очередью для конкурентного канала централизованных сетей. Данный класс содержит широкий спектр алгоритмов от базового алгоритма с очередью (FS-ALOHA) до аналога алгоритма дробления для централизованных сетей. Разработан метод вычисления скорости для алгоритмов СМД, входящих в подкласс алгоритмов введенного класса. Разработан метод определения оптимальных относительно скорости параметров алгоритма из подкласса алгоритмов СМД. Получен метод вычисления скорости алгоритма из подкласса алгоритмов СМД для различных видов входных потоков, описываемых марковской цепью (D-BMAP).

5). Разработан комплекс программ имитационного моделирования и численного расчета скорости для предложенных алгоритмов.

1. Draft IEEE standard for local and metropolitan area networks, Part 16: Air Interface for Fixed Broadband Wireless Access Systems. IEEE P802.16-REVd/D5-2004.

2. Олифер В.Г., Олифер H.A. Компьютерные сети. Принципы, технологии, протоколы СПб. Питер. 2001. С. 67-70.

3. A. Vinel, Y. Zhang, М. Lott and A. Tiurlikov Performance Analysis of the Random Access in IEEE 802.16// in Proceedings of the 16th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC'05). Berlin. Germany. 2005.

4. Винель A.B. Анализ случайного доступа протокола IEEE 802.16 при большом числе абонентов// Восьмая научная сессия ГУАП: Сб. докл./ ГУАП. СПб., 2005.

5. D. Vazquez, J. Garcia, С. Blondia and В. Van Houdt, FIFO by Sets ALOHA (FS-ALOHA): A Collision Resolution Algorithm for the Contention Channel in Wireless ATM Systems// Performance Evaluation 99. Istanbul. 1999. pp. 401-427.

6. Кобляков В.А. Программа исследования производительности алгоритмов случайного доступа в централизованных компьютерных сетях// Регистрационный номер Гос. ФАП 50200501139. 2005.

7. Кобляков В.А. Программа исследования производительности алгоритмов случайного доступа для простой модели подуровня управления доступом к среде// Регистрационный номер Гос. ФАП 50200501140. 2005.

8. Кобляков В.А. Исследование производительности алгоритмов случайного доступа для простой модели MAC подуровня в беспроводных централизованных сетях// Восьмая научная сессия ГУАП: Сб. докл./ ГУАП. СПб., 2005.

9. Кобляков В.А. Программа демонстрации работы протокола TCP и исследования его числовых характеристик// Регистрационный номер Гос. ФАП 50200501138. 2005.

10. Кобляков В.А. Вычисление коэффициента полезного использования канала для упрощенной модели протокола TCP// Сб. тез. докл. 5 научн. сессии аспирантов ГУАП- СПб.: ГУ АД 2002, С. 237-241.

11. J.L.Massey. Collision-Resolution Algorithms and Random-Access Communications// In Multi-User Communications, ed. G.Longo. Springer-Verlag, New York. 1981.

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

13. А.Н.Рябко, С.Б.Шлосман. Пуассоновская гипотеза: Комбинаторный аспект// Проблемы передачи информации, 2005. Т.41. №3 С. 51-57.

14. С. Blondia A discrete-time batch Markovian arrival process as B-ISDN traffic model// Belgian Journal of Operations Research, Statistical and Computer Science. №32(3,4). 1993.

15. C. Blondia and O. Casals. Statictical multiplexing of VBR sources: A matrix-analytical approach//Perfomance Evaluation, 1992. 16. pp. 5-20.

16. M.F. Neuts Matrix-Geometric Solutions in Stochastic Models// An Algorithmic Aproach. John Hopkins University Press, 1981.

17. M.F. Neuts Structured Stochastic Matrices of M/G/l type and their applications// Marcel Dekker, Inc., New York and Basel. 1989.

18. D.M. Lucantoni. New results on the single server queue with a batch Markovian arrival process// Stochastic Models, 1991. №7(1). pp. 1-46.

19. D.M. Lucantoni, K.S. Meier-Hellstern, and M.F. Neuts. A single server queue with server vacations and a class of non-renewal process// Adv. in Applied Probability, 1990. №22. pp. 676-705.

20. Wolfner G., Telek M. Numerical analysis of queues with batch arrivals// Performance evaluation, 2000. №41. pp. 179-194.

21. Beritelli F., Lombardo A., Palazzo S., Schembra G. Performance analysis of an ATM multiplexer loaded with VBR traffic generated by multimode speech coders// IEEE Journal on Selected Areas in Communications. 1999. vol. 17. pp. 1123-1134.

22. Lombardo A., Schema G. Traffic description and performance evaluation in multimedia ATM environment// IEEE GLOBECOM, 1996. pp. 327-332.

23. Yousef S. Performance, interarrival and correlation analysis of four-state MMPP model in ATM-based B-ISDN// IEEE Conference on Communications, Proceedings. 1996. pp. 363-368.

24. Kang S.H., Sung D.K. Two-state MMPP modeling of ATM superposed traffic streams based on the characterization of correlated interarrival times// IEEE GLOBECOM, 1995 pp. 1422-1426.

25. B. Van Houdt and C. Blondia Maximum Stable Throughput of FS-ALOHA under Delay Constraints// In Proc. of ITC18, Berlin. Germany. 2003.

26. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х томах. Т. 1: пер. с англ. М.: Мир, 1984. 528 с.

27. Blondia С., Casals О. Statistical multiplexing of VBR sources: a matrix-analytic approach// Performance Evaluation, 1992. 16. pp. 5-20.

28. T. Daniels. Asymptotic Behavior of Queueing Systems/ Phd thesis, University of Antwerp (UA), 1999.

29. Li S.Q., Sheng H.D. Spectral analysis of access rate control in high-speed networks// IEEE INFOCOM: Proceedings, 1993. pp. 662-671.

30. Li S.Q., Sheng H.D. Discrete queueing analysis of multimedia traffic with diversity of con-elation and burstness properties// IEEE Transactions on Communications, 1994. vol. 42. pp. 1339-1351.

31. I. Cidon and M. Sidi. Conflict multiplicity estimation and batch resolution algorithms// IEEE Trans. On Information Theory, IT-34(1). 1988. pp. 101-110.

32. A.G. Greenberg, P. Flajolet, and R.E. Ladner. Estimating the multiplicity of conflicts to speed their resolution in multiple access channels// Journal of the Association of Computing Machinery, 34(2). 1987. pp. 289-325.

33. J.L. Massey. Some new approaches to random-access communications// Per-fomance. 1987.

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

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

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

37. Capetanakis J.I. Tree Algorithms for Packet Broadcast Channels// IEEE Trans, on Information Theory. 1979. V.25. №5. pp. 505-515.

38. Mathys P. and Flajolet P. Q-ary Collision Resolution Algorithms in Random-Access Systems with Free or Blocked Channel Access// IEEE Transactions on Information Theory. 1985. V.31. №2. pp. 217-243.

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

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

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

42. Цыбаков Б.С., Федорцов С.П. Передача пакетов с помощью блокированного немодифицированного стек-алгоритма СМД// Проблемы передачи информации. 1986. Т.22. №3. С. 96-102.

43. F.P. Kelly and I. М. MacPhee. The number of packets transmitted by collision detect random access schemes//Annals of Probability. 1987. 15. pp. 1557-15568.

44. D. J. Aldous, Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels// IEEE Trans. Inf. Theory 33(2). 1987. pp. 219-223.

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

46. Tsybakov B.S. Packet Multiple Access for Channel with Binary Feedback, Capture and Multiple Reception// IEEE Trans on Information Theory. 2004. V.50. №6. pp. 10731085.

47. Tsybakov B. S. Survey of USSR contributions to random multiple-access communications// IEEE Transactions on Information Theory, vol. IT-31. 1985. pp. 143-165.

48. Tsybakov B.S., Fayngold V.B. Blocked RMA Stack Algorithm in Networks with Finite Number of Users// Proc. Fourth Joint Swedish-Soviet Workshop Inform. Theory. Gotland. Sweden. August. 1989. pp. 185-188.

49. Abramson. N. The ALOHA system Another alternative for computer communications// Proc. Of Fall Joint Computer Conference. 1970. Vol.37, pp. 281-285.

50. Бертсекас Д., Галлагер P. Сети передачи данных: Пер. с англ. Н.Б.Лиханова и др. под ред. Б.С.Цыбакова. М.: Мир, 1989. 544 с.

51. A.G. Greenberg, P. Flajolet, and R.E. Ladner. Estimating the multiplicity of conflicts to speed their resolution in multiple access channels// Journal of the Association of Computing Machinery. 1987. 34(2) pp. 289-325.

52. N. O. Song, B. J. Kwak, and L. E. Miller. On the Stability of Exponential Backoff// Journal of Research of the National of Standards and Technology. Gaithersburg. 2003. 108(4). pp. 289-297.

53. D. Vazquez-Cortizo. C. Blondia. and J. Garcia. Fs-aloha++, a collision resolution algorithm with qos support for the contention channel in multi-service wireless Ian// In Globecom'99 IEEE. 1999.

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

55. R. G. Gallager Conflict Resolution in Random Access Broadcast Networks// Proc. of the AFOSR Workshop in Communication Theory and Applications. 1978. pp. 74-76.

56. M. Paterakis and P. Papantoni-Kazakos. A Simple Window Random Access Algorithm with Advantageous Properties// IEEE Transactions on Information Theory 35(5). 1989. pp. 1124-1130.

57. J. Mosely and P. A. Humblet A Class of Efficient Contention Resolution Algorithms for Multiple Access// IEEE Transactions on Communications 33(2). 1985. pp. 145-151.

58. J. L. Massey Collision-Resolution Algorithms and Random-Access Communications// in Multi-User Communications, ed. G. Longo, Springer-Verlag, New York. 1981.

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

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

61. Capetanakis J.I. Tree Algorithms for Packet Broadcast Channels// IEEE Trans, on Information Theory. 1979. V.25. №5. pp. 505-515.

62. Кобляков В.А. Комбинированный алгоритм случайного доступа для беспроводных централизованных сетей// Восьмая научная сессия ГУАП: Сб. докл./ ГУАП. СПб, 2005.

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

64. Кобляков В.А. Аналог алгоритма дробления для централизованных сетей// Научная сессия ГУАП, посвященная всемирному Дню авиации и космонавтики и 65-летию ГУАП: Сб. докл./ ГУАП. СПб, 2006.

65. J. Goodman, A. G. Greenberg, N. Madras, and P. March Stability of binary exponential backoff// ACM 35(3). 1988. pp. 579-602.

66. Кобляков В.А. Исследование алгоритма разрешения конфликтов FS-ALOHA в канале с ложными конфликтами// Сб. тез. докл. 6 научн. сессии аспирантов ГУАП СПб.: ГУАП, 2003, С. 166-168.

67. Кобляков В.А. Исследование устойчивости алгоритма разрешения конфликтов FS-ALOHA в канале с ложными конфликтами// Сб. тез. докл. 7 научн. сессии аспирантов ГУАП СПб.: ГУАП, 2004.

68. В. Van Houdt and С. Blondia Robustness of FS-ALOHA// 4th Int. Conf. on Matrix Analytic Methods (MAM4). Adelaide (Australia). 2002. pp. 381-402.

69. Pahlavan K., Levesque A. Wireless Information Network. John Wiley & Sons. 1995.

70. F. Baccelli, S. Foss On the saturation rule for the stability of queues// Journal of Applied Probability. Vol. 32. 1995. pp. 494-507.

71. Д. Кемени, Д Снелл Конечные цепи Маркова. Главная редакция физико-математической литературы изд-ва «Наука», 1970. 271 с.

72. Клейнрок JI. Теория массового обслуживания: Пер. с англ./Пер. И.И. Грушко; ред. В. И. Нейман. -М.: Машиностроение, 1979. 432 с.

73. Крейн, О. Лемуан. Введение в регенеративный метод анализа моделей: Пер. с англ. Н. Я. Ривеса/ Под ред. В. В. Калашникова. М.: Наука, 1982. 104 с.

74. Кобляков В.А., Смирнов А.О., Тюрликов A.M. Автоматизированная система контроля знаний по курсу высшей математики// Информационные технологии в науке, образовании, искусстве: Сборник научных статей СПб.: Изд-во РГПУ им. А.И. Герцена, 2005.

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

76. Кобляков В.А. Аналог алгоритма дробления для централизованных сетей// Научная сессия ГУАП, посвященная всемирному Дню авиации и космонавтики и 65-летию ГУАП: Сб. докл./ ГУАП. СПб., 2006.