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

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

МАРКОВСКИЙ Станислав Георгиевич С

УПРАВЛЕНИЕ ДОСТУПОМ К ОБЩЕМУ КАНАЛУ СВЯЗИ С ИСПОЛЬЗОВАНИЕМ АДРЕСОВ АБОНЕНТОВ ДЛЯ РАЗРЕШЕНИЯ

КОНФЛИКТОВ

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

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

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

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

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

кандидат технических наук, доцент Тюрликов Андрей Михайлович

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

профессор Яковлев Сергей Алексеевич кандидат технических наук, доцент Татаршкова Татьяна Михайловна

Ведущая организация - ОАО "Северо-Западный Телеком", г. Санкт-Петербург.

Защита состоится " " ^е^а^г^ 2006 г. в часов на заседании

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

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

Автореферат разослан " 7? " 2005 г.

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

Осипов Л.А.

JLC&6JL

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

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

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

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

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

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

• разработка метода расчета средней задержки передачи пакета для двухбуферной модели абонента;

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

• разработка метода управления доступом абонентов к общему каналу связи для модели с центральной станцией;

• разработка алгоритмов с пропуском уровней, определение характеристик алгоритмов в канале без шума и в канале с шумом.

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

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

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

1). Метод расчета средней задержки передачи пакета для двухбуферной модели абонента.

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

3). Метод управления доступом абонентов к общему каналу связи для модели с центральной станцией.

4). Алгоритмы с пропуском уровней в канале без шума и в канале с шумом, а также определение средней задержки и скорости предложенных алгоритмов.

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на научно-технических конференциях: ДИМЭБ-97 "Диагностика, информатика, метрология, экология и безопасность" (Санкт-Петербург, 1 - 3 июля 1997), 15С->ГЕТ97 (Санкт-Петербург, 30 сентября - 2 октября 1997 г.), "Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехнических системах" (Санкт-Петербург, 18-19 ноября 1997г.), ДИМЭБ-98 (Санкт-Петербург, 30 июня - 2 июля 1998г.), второй научной сессии аспирантов ГУАП (Санкт-Петербург, 12-16 апреля 1999г.), на международной научной конференции "Интеллектуальные технологии и дистанционное обучение на рубеже XXI века", (Санкт-Петербург, 6-9 июля 1999г.), на восьмой научной сессии ГУАП (Санкт-Петербург, 11-15 апреля 2005г.).

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

Объем и структура работы. Диссертационная работа состоит из введения, четырех разделов, списка использованных источников (54 наименования) и двух приложений. Основная часть работы изложена на 134 страницах машинописного текста, содержит 56 рисунков и 23 таблицы. Приложения насчитывают 14 страниц и содержат 14 рисунков.

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

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

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

В качестве модели системы СМД используется идеализированная модель системы СМД. Модель имеет ряд допущений:

• все пакеты имеют одинаковую длину. Интервал времени, равный времени передачи пакета, называется окном;

• синхронный доступ. Время работы системы разбивается на окна. Моменты разделения окон известны всем абонентам. Абонент может начать передачу только в начале окна;

• мгновенная обратная связь. К началу очередного окна абоненту известен результат передачи в предыдущем окне;

• троичная обратная связь. Абонент различает в канале три ситуации: "пусто", "успех" и "конфликт";

• канал без ошибок. Все абоненты правильно оценивают ситуацию в канале;

• система с конечным числом абонентов. Число абонентов равно М. Пакеты поступают в систему в соответствии с распределением Бернулли.

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

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

Рассматривается вероятностная модель поступления новых пакетов в ячейки Ш абонентов. У каждого абонента имеется источник новых пакетов. Если в некотором окне у абонента свободна ячейка Ш, то с вероятностью р у него может возникнуть новый пакет, который занимает эту ячейку. С вероятностью 1 - р ячейка ГЫ останется свободной. Описанные случайные события статистически независимы для разных абонентов.

Пусть величина описывает состояние ячейки Ш х'-го абонента: //(,) = 0 -ячейка М свободна, /¡(,) = 1 - ячейка Ш занята. Тогда вероятности событий, связанных с появлением новых пакетов в системе, могут быть заданы следующим образом:

Рг{д('> = 01 //'> = 1}= 1, Рг{#> = 11 //<'> = 1}= 0,

Рг{Д(,) = 01 = 0}= 1 - р, Рг{Д<" = 11 //<•> = 0}=р,

здесь Д(,) - число новых пакетов, появившихся у абонента с номером г в окне /, причем /?,(,> =0,1. При этом

ъ\р,=1\\£/)=М-т^=С>тА\-рГ', (1)

где Д =ХД(,).

В работе через обозначается вероятность события {число новых

пакетов, возникших на интервале заданной длины $ равно _/, при условии, что свободны ячейки Шут абонентов}. Тогда, согласно (1) имеем:

У(и,т) = С'яр'(1-рГч.

Используя данное выражение, У(з,]',М) определяется по следующей рекуррентной формуле:

ы>

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

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

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

-Нш 1>

где 5п - задержка л-го пакета (л - номер пакета, определяемый с начала работы системы). Как правило, этот пакет называют меченым. Это определение было введено Цыбаковым.

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

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

Для двухбуферной модели понятие скорости было предложено Капетанакисом. Предполагается, что все абоненты системы имеют готовый для передачи пакет. Тогда скорость алгоритма доступа (Л) - это отношение числа пакетов (М ) к длине интервала, в течение которого эти пакеты получают успешную передачу

Здесь 2Л/-1 - длина интервала.

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

В разделе 2 рассматриваются алгоритмы, использующие адреса абонентов, для разрешения конфликтов в канале без шума. В качестве алгоритмов разрешения конфликта (АРК) выбраны блокированные ^модифицированный и модифицированный стек-алгоритмы (НСА и МСА). Рассматривается представление АРК в виде дерева, так называемого дерева разрешения конфликта (ДРК). Анализ алгоритмов сводится к исследованию свойств ДРК.

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

Вводится понятие сеанса. Если в окне с номером t возникает первоначальный конфликт, в котором участвуют к абонентов, то сеанс — временной интервал, в течение которого все участники этого конфликта получают успешную передачу. Сеанс, в котором поступил меченый пакет, называется сеансом поступления, а сеанс, в котором этот пакет получает успешную передачу - меченым сеансом. В случайную величину 8, входят две составляющие (рисунок 1): - время от момента появления меченого пакета до момента окончания сеанса поступления и Sj2) - время от момента начала меченого сеанса до момента успешной передачи меченого пакета, т.е.

s,=sp+sj2). (3)

Средние задержки для величин и <У,<г) определяются следующим образом: = Нт 7)2 = 1ип Ш<2), В = Х»1 + Д2 . (4)

/-»• /-»Л

Кратность сеанса (*) - число пакетов, передаваемых в первом окне сеанса. Вводятся обозначения: кратность сеанса с номером и и ва - средняя длина сеанса с номером и.

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

Пакет 1

Меченый пакет /

пакеты, покидающие в систему

Сеанс 1

Сеанс 2

пакеты, поступающие в систему

Сеанс поступления Меченый «мне

' б® №

< -»

Пакет 1

Меченый пакет г

Рисунок 1 - Определение задержки меченого пакета

Средняя кратность сеанса К(,) определяется следующим образом:

(5)

«-♦ео ¿.4

где як ~ 1ип Рг{£ -к} • стационарные вероятности, которые могут быть найдены из системы уравнении

Е**а» = *.. *>=<),1.....М , (6)

4.0

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

Л. - £М<?„ = «I в.-, = " 51 - *}- £у{?.т,М)р1и I А), (8)

где - распределение длины сеанса, которое вычисляется по следующей

рекуррентной формуле:

я(»I*)- + (9)

здесь .$¡>3,/21.

си

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

^М'Шп^.(1°)

и—*<х>

Непосредственно из определения случайных величин следует, что Рг{0.„ = = *}= Рг^„ = к 1= *}1Рг{0„_, = 51 = =«}.

»о

Учитывая данное равенство и (10):

л„ У{*,к,М)УРо(* I О ЯГ, . (11)

Рассматривается событие Л, „ = {меченый пакет ( пакет с номером У), получил успешную передачу в сеансе с номером к}. В работе введены следующие обозначения: як = ИтРг{& =*,Д„} - стационарное распределение кратности меченого сеанса, *,($) = 1ип Рг{0„_, =к,А,„) - совместное распределение кратности меченого сеанса и длины сеанса поступления, г($) = Нт Рг{0„_, =$,Д„} -стационарное распределение длины сеанса поступления. Показано, что для марковской цепи £ справедливы следующие равенства:

Вводится в рассмотрение следующая условная вероятность Рм (Л 5)= Рг {меченый пакет поступил в окне с номером j | сеанс поступления длится «окон}. Данная вероятность не зависит от номера сеанса, в котором поступает меченый пакет. Так как по определению меченый пакет поступает в каком-то одном из 5 окон сеанса поступления, то согласно формуле Байеса:

р.им- р{1~рГ1, ■ (13)

где j = l,s.

Учитывая (12) и (13), получено выражение для £)1

D\ =

V/-' J ,

+1.

(14)

Средняя задержка D2 вычисляется по следующей формуле:

D2 -¿rfA,

(15)

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

Время выхода - это время от момента начала меченого сеанса до момента успешной передачи меченого пакета.

dt определяется по следующей рекуррентной формуле:

где: dkJ - среднее время выхода пакета из сеанса кратности к в вершине, соответствующей 2' абонентам, у - вид алгоритма (/=0 для НСА и у=1 для МСА), 7],., - средняя длина сеанса кратности i в вершине, соответствующей 2'"' абонентам, которая в свою очередь определяется по формуле:

^=1+ (17)

/-мир-2"')

Используя (14) и (15), по формуле (4) определяется средняя задержка передачи меченого пакета О. В работе отмечается, что формулы (9),(16) и (17) не зависят от интенсивности входного потока.

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

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

Рисунок 2 - Зависимость средней задержки от интенсивности входного потока в системе с 32 абонентами

В разделе 3 представлены алгоритмы, которые используют адреса абонентов для разрешения конфликтов в канале с шумом. Рассматривается модель канала с ложными конфликтами. Модель полностью задается вероятностями: -

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

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

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

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

Для канала с ложными конфликтами скорость вычисляется следующим образом:

д _ М _ М = 2' _ 1

+ м_им_±_ 2'-1 + 2'—-— I -2-' + —

1 ~Я, 1 ~9, 1-9, (18)

1-9,

2-2-'(1'

где 7; 0 - среднее число окон до наступления ситуации "успех" при возникновении в концевой вершине ложного конфликта кратности 1.

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

ти = 1 + а

+ 1-9» +90а) + \м2* -(1 ~0о)}• (19)

п«<».:м) з-1

г-оаКОЛ-У ') к-1

+ (1"9о) { " & />м(*-2|*)}. (20)

¿V = а О + ( 7^/-. + )> +

/«□»(Г,»-!1 ') * *

+ Г«, Г {^(1-в, + 900») + - ( 1-9») }• (21)

Далее, на основании метода, приведенного в разделе 2, определяется средняя задержка передачи пакета для канала с ложными конфликтами.

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

D

Рисунок 3 - Зависимость средней задержки от интенсивности для МСА

Из графика видно, что при низких интенсивностях наибольшее влияние на среднюю задержку оказывает вероятность <?„. Это объясняется тем, что возникновение ложного конфликта на пустом окне приводит к появлению двух дополнительных окон, если окно не является концевым. При высоких интенсивностях уменьшается вероятность появления пустых окон, и наибольшее влияние на величину задержки оказывает вероятность q,.

Метод управления доступом абонентов к общему каналу связи для модели с центральной станцией был обобщен на модель канала с шумом. При этом алгоритм

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

В разделе 4 введены в рассмотрение алгоритмы с пропуском уровней.

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

Алгоритм с пропуском уровней состоит в том, что в начале сеанса из ДРК исключается * уровней (jc = l.log, м). В результате вместо дерева, соответствующего первоначальному сеансу, появляется 2' поддеревьев.

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

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

2). Далее выполняются инструкции НСА или МСА.

Определение скорости для алгоритма, использующего адреса абонентов для разрешения конфликтов, не пропускающего уровни, было приведено в разделе 1. Если из ДРК максимальной кратности исключить х уровней, то число вершин в дереве уменьшится на 2*-1 и составит 2М-2'. Тогда, скорость алгоритма с пропуском уровней, при х уровнях пропуска, определяется по следующей формуле:

Я =_JL_ = _J!___1 ^ 2'" (22)

' 2М-2" 2м-2* ~ 2-2*-' 2'~'*' -1

Для канала с ложными конфликтами:

ММ 2'

Ш)"

М-Г + МЪ М_Г + М_А_ 2' -¥ + 21 —— 1-9, 1-i

J___I-ft

(23)

-2*"' + —1— 2-2'-'(1-?,)-9, 1-9,

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

■Ж«.*"1)

Т„.(9o.ii) = !>*.,,( + ). (24)

/-■и<0Л-2ы)

здесь дг=1,1ов2 А/.

^ (?О>0|) = ( (io.il) +

/-шко^г'') *

+ (90.«)+) • (25)

/>/.,(« I*) = Е^а. Цл-и-Д^ЮА-и-!^-"!*-'), (26)

где *=М/, I = l.log2А/,

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

D

Рисунок 4 - Зависимость средней задержки от интенсивности входного потока для МСА при М = 64, д0 = q, = 0,2 и разном числе пропускаемых уровней

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

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

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

Я

Рисунок 5 - Зависимость интенсивности входного потока от вероятности ложного конфликта при М = 64цда-д1 = д

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

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

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

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

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

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

дает выигрыш по средней задержке по сравнению с применением случайных паспортов.

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

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

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

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

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

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

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

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

1. Тюрликов A.M., Марковский С.Г. Вычисление средней задержки при организации случайного множественного доступа с использованием адресов абонентов. Депонированная рукопись в ВИНИТИ №782-В97.1997.

2. Тюрликов A.M., Марковский С.Г. Алгоритм доступа с фиксированными паспортами в канал с ложными конфликтами // Тезисы доклада на научно-технической конференции ДИМЭБ-97.1 - 3 июля 1997г. СПб, 1997. с.146.

3. A.Turlikov, S.Markovsky. Improved blocked algorithm in the channel of multiple access with false conflicts. ISC-NET'97.30.09 - 02.10.97r.. St-Petersburg, 1997. C.31-32.

4. Тюрликов A.M., Марковский С.Г. Алгоритм опроса абонентов для систем с низкой интенсивностью входного потока // Тезисы доклада на третьей межведомственной научно-технической конференции "Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехнических системах". 18-19 ноября 1997г. Пушкин, 1997. С.146.

5. Тюрликов A.M., Марковский С.Г. Алгоритм опроса абонентов на основе троичного дерева разрешения конфликтов // Тез. докл. на науч.-техн. конф. ДИМЭБ-98. 30 июня - 2 июля 1998г. СПб, 1998. С137-138.

6. Марковский С.Г. Сравнительный анализ методов случайного доступа в системе с конечным числом абонентов // Тез. докл. на второй науч. сессии аспирантов ГУАП. 12 -16 апреля 1999г. СПб, 1999. С.42.

7. Марковский С.Г. Алгоритм разрешения конфликта с виртуальной очередью // Тез. докл. на международной науч. конф. "Интеллектуальные технологии и дистанционное обучение на рубеже XXI века". 6-9 июля 1999г. СПб, 1999. С192-193.

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

9. Марковский С.Г. Алгоритмы, использующие маску центральной станции для разрешения конфликтов // Тез. докл. на восьмой науч. сессии ГУАП. 11-15 апреля 2005г. СПб, 2005. С.466-469.

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

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

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

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

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

Введение

1 Модели и алгоритмы СМД для системы с конечным числом абонентов

1.1 Развитие методов СМД и проблемы, возникающие в современных системах при использовании алгоритмов СМД

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

1.3 Понятие протокола СМД.

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

1.4.1 Модели абонентов с очередью.

1.4.2 Двухбуферная модель.

1.5 Основные характеристики систем СМД

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

1.7 Постановка задачи исследования

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

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

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

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

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

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

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

2.6 Метод управления доступом абонентов к общему каналу для модели с центральной станцией

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

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

3.1 Модель канала с ложными конфликтами.

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

3.3 Терминальный стек.

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

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

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

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

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

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

3.7 Метод управления доступом абонентов к общему каналу для модели с центральной станцией в канале с шумом

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

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

4.1 Алгоритмы разрешения конфликтов с пропуском уровней

4.2 Алгоритмы пропуска уровней в канале с шумом.

4.3 Расчет скорости алгоритма с пропуском уровней.

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

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

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

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

4.6 Динамический алгоритм разрешения конфликта.

4.7 Сравнительный анализ алгоритма с пропуском уровней и динамического алгоритма.

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

Актуальность темы. В настоящее время множественный доступ широко используется для передачи информации как в проводных, так и беспроводных сетях связи. Методы множественного доступа принято разделять на бесконфликтные и конфликтные. Наиболее яркими примерами использования бесконфликтных методов доступа являются сотовые сети связи стандартов AMPS, NAMPS, GSM(b режиме передачи речи) и другие, в которых используются методы частотного, временного и кодового разделения каналов. Для бесконфликтных методов доступа средняя задержка передачи сообщения зависит от числа абонентов в системе. К конфликтным методам доступа относят СМД, который целесообразно использовать при низкой интенсивности входного потока и случайном трафике сообщений. При этих условиях СМД дает среднюю задержку меньшую, чем при использовании бесконфликтных методов доступа, причем средняя задержка практически не зависит от числа абонентов в системе. СМД широко используется в локальных проводных сетях (сеть Ethernet, стандарт IEEE 802.3), в беспроводных сетях стандарта IEEE 802.11, а также для резервирования времени при пакетной передаче данных (GPRS) в стандарте GSM. В стандарте IEEE 802.16 случайный доступ используется для резервирования времени при передаче данных от абонентов к базовой станции.

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

Евсеев Г.С и Ермолаев Н.Г. исследовали характеристики (скорость и среднюю задержку) АРК со случайными паспортами в канале с шумом, и отметили тот факт, что в канале с шумом непосредственно использовать адреса абонентов для разрешения конфликтов нельзя. Поэтому, является актуальным:

• разработать алгоритмы СМД, использующие адреса абонентов для разрешения конфликтов в канале с шумом;

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

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

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

1). Разработка метода расчета средней задержки передачи пакета для двух-буферной модели абонента.

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

3). Разработка метода управления доступом абонентов к общему каналу связи для модели с центральной станцией.

4). Разработка алгоритмов с пропуском уровней. Определение характеристик алгоритмов в канале без шума и в канале с шумом.

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

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

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

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

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

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

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

Результаты диссертационной работы использованы при разработке системы мониторинга экологического состояния водной среды и в учебном процессе ГУАП. Использование результатов диссертационной работы потверждается соответствующими актами.

Апробация работы. Основные результаты работы докладывались на научно-технических конференциях: ДИМЭБ-97 (Санкт-Петербург, 1 - 3 июля 1997г.), ISC-NET'97 (Санкт-Петербург, 30 сентября - 2 октября 1997г.), "Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехнических системах" (Санкт-Петербург, 18 - 19 ноября 1997г.), ДИМЭБ-98 (Санкт-Петербург, 30 июня - 2 июля 1998г.), второй научной сессии аспирантов ГУАП (Санкт-Петербург, 12-16 апреля 1999г.), на международной научной конференции "Интеллектуальные технологии и дистанционное обучение на рубеже XXI века", (Санкт-Петербург, 6-9 июля 1999г.), на восьмой научной сессии ГУАП (Санкт-Петербург, 11-15 апреля 2005г.).

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

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

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

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

- метод управления доступом абонентов к общему каналу связи для модели с центральной станцией;

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

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

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

Сформулируем выводы по данному разделу.

1). Разработаны алгоритмы с пропуском уровней в канале без шума и в канале с шумом.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

1). Введена двухбуферная модель абонента. Абонент имеет очередь, которая состоит из двух ячеек. Пакеты поступают к абоненту в первую ячейку, а передаются в канал из второй ячейки. Момент перехода пакета из первой во вторую ячейку определяется алгоритмом доступа. У абонента в любой момент времени может находиться не более двух готовых для передачи пакетов. Описана вероятностная модель поступления новых пакетов к абоненту.

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

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

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

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

6). Метод управления доступом абонентов к общему каналу связи для модели с центральной станцией был обобщен для работы в канале с шумом. При этом алгоритм работы абонента не изменяется.

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

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

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

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

2. IEEE Std IEEE 802.16-2004 (Revision of IEEE Std IEEE 802.16 2001). IEEE Standard for Local and metropolitan area networks. Part 16: Air Interface Fixed Broadband Wireless Access Systems // IEEE. 1. October 2004.

3. Вишневский B.M. и др. Широкополосные беспроводные сети передачи информации. М.: Техносфера, 2005. 592с.

4. Закиров З.Г. и др. Сотовая связь стандарта GSM. Современное состояние, переход к сетям третьего поколения. М.: Эко-Трендз, 2004. 264с.

5. N.Abramson. The ALOHA system Another alternative for computer communications. Proc. Of Fall Joint Computer Conference. 1970. Vol.37. P.281-285.

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

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

8. IEEE Trans. Inform. Theory. Vol. IT-31. 2. 1985. Special issue on Random-Access Communication. P. 117-310.

9. G.Dimic, N.D.Sidiropoulos, R.Zhang. Medium Access Control-Physical Cross-Layer Design. // IEEE Signal Processing Magazine. September 2004. P.40-50.

10. Molle M.L., Polyzos G.C. Conflict resolution algorithms and their performance analysis. Technical report. University of Toronto, CS93-300.1993.

11. Rom R., Sidi M. Multiple Access Protocols. Springer-Verlag. New York. 1990.

12. Van Houdt B. Performance Evaluation of Contention Resolution Algorithms in Random Access Systems. Antwerpen, 2001.

13. Van Houdt В., Blondia C. Robustness of Q-ary Collision Resolution Algorithms in Random Access Systems // Performance Evaluation. 2004. V.57. P.357-377.

14. Van Houdt В., Blondia С. Throughput of Q-ary Splitting Algorithms for Contention Resolution in Communication Network // Communications in Information and Systems. 2005. Vol.4. No.2. P. 135-164.

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

16. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. ANSI/IEEE Std 802.11, 1999 Ed.

17. Bianchi G. Performance Analysis of the IEEE 802.11 Distributed Coordination Function // IEEE Journal On Selected Areas In Communications. 2000. Vol. 18. No. 3. P. 535 547.

18. Вишневский B.M. Теоретические основы проектирования компьютерных сетей. М: Техносфера, 2003. 512с.

19. Ying Dar Lin. On IEEE 802.14 Medium Access Control Protocol // IEEE Communications Surveys . Fourth Quarter. 1998. Vol. 1. No. 1. P. 2-10.

20. Gallager R.G. A Perspective on Multiaccess Channels // IEEE Trans on Information Theory. 1985. V. 31. №2. P. 124 142.

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

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

23. Tsybakov B.S. Packet Multiple Access for Channel with Binary Feedback, Capture and Multiple Reception // IEEE Trans on Information Theory. 2004. V. 50. №6. P. 1073 -1085.

24. Capetanakis J.I. Generalized TDMA. The Multi-Accessing Tree Protocol Channels. // IEEE Trans. Commun. 1979. V. 27. №10. P. 1476- 1483.

25. 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. P. 217 243.

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

27. Paterakis М., Papantoni-Kazakos P. A Simple Window Random Access Algorithm with Advantageous Properties // IEEE Transactions on Information Theory. 1989. V35. №5. P. 1124-1130.

28. Polyzos G.C., Molle M.L., Venetsanopolous A.N. Performance Analysis of Finite Nonhomogeneous Population Tree Conflict Resolution Algorithms Using Constant Size Window Access // IEEE Transactions on Communications. 1987. V35. №11. P.1124-1138.

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

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

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

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

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

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

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

36. Марковский С.Г. Сравнительный анализ методов случайного доступа в системе с конечным числом абонентов // Тез. докл. на второй науч. сессии аспирантов ГУАП. 1999г. Санкт-Петербург, 1999. С.42.

37. 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. P. 185-188.

38. D.Petras and A.Kramling. Fast Collision Resolution in Wireless ATM Networks. In 2nd Mathmod. Vienna. Austria, Feb 1997.

39. B.Van Houdt and C.Blondia. Analysis of an Identifier Splitting Algorithm Combined with Polling for Contention Resolution in a Wireless ATM Access Network.// IEEE J. on Selected Areas in Comm. 2000. V18. №11. P.2345-2355.

40. Марковский С.Г. Алгоритм разрешения конфликта с виртуальной очередью // Тез. докл. на международной науч. конф. Интеллектуальные технологии и дистанционное обучение на рубеже XXI века. 6-9 июля 1999г. СПб, 1999. С192-193.

41. M.Paterakis, L.Georgiadis, and P.Papantoni-Kazakos. On the Relation Between the Finite and the Infinite Population Models for a Class RAA's // IEEE Transactions on Communications. 1987. V35. №11. P.1239-1240.

42. P.Flajolet, PJacquet. Analytic Models for Tree Communication Protocols, INRIA Res. Rep. in print. 1987.

43. Тюрликов A.M., Марковский С.Г. Алгоритм опроса абонентов на основе троичного дерева разрешения конфликтов // Тез. докл. на науч.-техн. конф. ДИМЭБ-98. 30 июня 2 июля 1998г. СПб, 1998. С137-138.

44. Черняк JI. Сети промышленных контроллеров/Юткрытые систе-мы.2001. №5-6. С.10-16.

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

46. Марковский С.Г. Алгоритмы, использующие маску центральной станции для разрешения конфликтов // Восьмая научная сессия ГУАП. Сборник докладов в 2 частях. 4.1. Технические науки. 2005г. СПб, 2005. С.466-469.

47. Тюрликов A.M., Марковский С.Г. Вычисление средней задержки при организации случайного множественного доступа с использованием адресов абонентов. Депонированная рукопись в ВИНИТИ №782-В97.1997.

48. A.Turlikov, S.Markovsky. Improved blocked algorithm in the channel of multiple access with false conflicts. ISC-NET'97. St-Petersburg, 1997. C.31-32.

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

50. Тюрликов A.M., Марковский С.Г. Алгоритм доступа с фиксированными паспортами в канал с ложными конфликтами // Тезисы доклада на науч.-техн. конф. ДИМЭБ-97. 1 3 июля 1997г. СПб, 1997. С. 146.

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

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

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