авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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

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

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

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

АЛГОРИТМЫ РАЗРЕШЕНИЯ КОНФЛИКТОВ

В СИСТЕМАХ ПЕРЕДАЧИ ИНФОРМАЦИИ

СО СЛУЧАЙНЫМ МНОЖЕСТВЕННЫМ

ДОСТУПОМ

Специальность 05.13.01 — Системный анализ, управление и

обработка информации (в технике и технологиях)

АВТОРЕФЕРАТ

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

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

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

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

Научный консультант: Засл. деятель науки РФ, доктор технических наук, профессор Крук Евгений Аврамович

Официальные оппоненты: доктор технических наук, профессор Богатырев Владимир Анатольевич доктор технических наук, профессор Зеленцов Вячеслав Алексеевич доктор технических наук, профессор Яновский Геннадий Григорьевич

Ведущая организация: «Всероссийский научно-исследовательский институт радиоаппаратуры»

(ОАО «ВНИИРА»)

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

– Всесоюзных школах-семинарах по вычислительным сетям (1982г.– 1990г.);

– Симпозиумах по проблемам избыточности в информационных си стемах (1983г., 1986г., 1989г., 2007г., 2009г.);

– Советско-шведских симпозиумах по теории информации (1991г., 1993г.);

– Международных симпозиумах по теории информации (1994г., 1995г.);

– Международном семинаре «On Multiple Access Communications»

(Санкт-Петербург, Россия, 2008г.);

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

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

– семинарах кафедры информационных систем и кафедры безопас ности информационных систем Санкт-Петербургского государственно го университета аэрокосмического приборостроения;

– семинарах Института проблем передачи информации РАН (Москва).

Публикации. По теме диссертации опубликовано более 50 печат ных трудов в научно-технических журналах, сборниках докладов и научно-технических сборниках, в том числе 18 статей в журналах, включенных в Перечень ВАК.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Допущение 5. В системе имеется бесконечное число абонентов.

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

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

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

– вторым аргументом является последовательность событий () = (1,..., ) в канале связи. Здесь =, если окно пусто, =, если окно содержит успешную передачу, и =, если в окне произошел конфликт;

– третьим аргументом является последовательность значений () () () () = (1,..., ), связанная с абонентом, у которого в момент () возник пакет;

здесь = 0, если в окне абонент не передавал па () кет, и = 1, если передавал.

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

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

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

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

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

Считается, что эта информация передается мгновенно и безошибочно.

Пусть в окне два абонента передают пакеты и одновременно, что приводит к их наложению. Через обозначим сигнал, принятый к концу окна, а через и – сигналы, соответствующие пакетам дан ных и соответственно. В конце окна приемник получает сигнал, который формируется в результате наложения на входе приемника сигналов, и шумов. Эту «смесь» сигналов и условно бу t t+1 t+ A,B A A A,B B Рисунок 1. Пример работы процедуры компенсации конфликтных сигналов дем обозначать как = +. После обработки сигнала приемник выносит решение о том, что произошел конфликт. Исходная смесь со храняется. Участки конфликта с вероятностью 2 принимают решение о повторной передаче. Предположим, что в окне принял решение переда вать только один из участников конфликта. Получив сигнал +1 = в конце окна + 1, приемник успешно выделяет сигнал. По выде ленному сигналу восстанавливается пакет.





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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это поддерево будем называть деревом разрешения конфликта (ДРК).

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

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

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

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

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

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

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

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

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

При этом построение ДРК завершается.

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

В первом окне сеанса передают пакеты все участники сеанса.

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

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

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

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

Условное математическое ожидание = [ |разрешается конфликт кратности k ] будем называть средним временем разрешения конфликта кратности.

В разделе сначала приводится известный результат для базового алгоритма. Если – значение скорости некоторого блокированного ал горитма, то в работах Б.С.Цыбакова было показано, что справедливы следующие оценки lim inf lim sup. (1) Известно, что в асимптотике для базового алгоритма справедливо равенство 2 = + sin (2 log2 () + ) + ( ), (2) ln (2) где = 3.127 · 106, = 0.9826.

Из (2) и (1) непосредственно следует )1 ) ( ( 2 +, (3) ln (2) ln (2) где – скорость базового алгоритма. Таким образом. (4) ln (2) После рассмотрения базового алгоритма предлагается общий метод анализа произвольного блокированного древовидного алгоритма. Клю чевая идея предлагаемого метода состоит в том, что работу любого из известных древовидных алгоритмов разрешения конфликта можно описать с помощью ДРК базового алгоритма, но при этом на пометку некоторых вершин не затрачивается времени. При проведении анализа выполняются следующие шаги:

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

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

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

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

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

2 ln (2) Затем в разделе исследуется работа базового алгоритма в условиях описанного в первом разделе расширения классической модели на слу чай канала, в котором воздействие шума может приводить к возник новению ложных конфликтов. Доказано, что для базового алгоритма при любом 1 среднее время разрешения конфликта для канала с шумом и среднее время разрешения конфликта для бесшумного канала связаны соотношением 0 0 + + (1 0 ) + =, (6) 2 где 0 =, 1 1 20 + 1 =, (1 1 )(1 20 ) где 0 и 1 – вероятности ложного конфликта для пустого окна и окна, в котором передавал один абонент. Обозначим скорость базового алгорит ма в канале с шумом через. Для вычислены верхняя и нижняя оценки, на основании которых получено приближенное значение ) ( 1 20 1 2(1 0 ) +.

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

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

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

– смежная с вершиной нижняя вершина;

– вершина, для которой вершины и являются потомками;

( ) – значение сигнала для произвольной вершины.

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

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

Ситуация 1. Если в окне вершина получает пометку, то в этом окне пометка вершины не производится. B окне + 1 текущей вершиной становится верхний потомок вершины.

Ситуация 2. Если в окне вершина получает пометку (см.

рисунок 2, a), то в этом же окне вершина получает пометку и ( ) := ( ). B окне +1 текущей вершиной становится верхний потомок вершины.

Pcur E P prev Ptmp C a) C Vtmp:=V(Pprev ) C V(Pprev ) Окно t Окно t + Pcur Пометка вершины Ptmp производится в зависимости от значения сигнала Vtmp S P prev Ptmp C б) C Vtmp:=V(Pprev )-V(Pcur ) V(Pprev ) Окно t Рисунок 2. Пометка вершин и вычисление значений сигналов в ДРК для алгоритма с компенсацией конфликтных сигналов: а – в окне вершина получает пометку ;

б – в окне вершина получает пометку Ситуация 3. Если в окне вершина получает пометку (см.

рисунок 2, б), то применительно к вершине выполняются дей ствия:

Действие 1. Вычисляется = ( ) ( ).

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

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

Действие 3. Устанавливаются значения сигналов для вершин и : ( ) =, ( ) =.

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

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

= + 1, (7) где – среднее время разрешения конфликта для алгоритма с ком пенсацией конфликтных сигналов.

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

)1 ) ( ( 1 1 1 + (. (8) ln (2) 2 ln (2) Для реализации алгоритма с компенсацией конфликтных сигналов требуется иметь неограниченную память. Кроме того, данный алгоритм неустойчив к ошибкам, которые могут возникать при компенсации кон фликтных сигналов. В диссертационной работе предложен алгоритм, свободный от этих недостатков. Основная идея алгоритма состоит в том, что разрешается компенсировать только один конфликтный сиг нал. По сравнению с исходным алгоритмом изменяются действия в Си туации 1 и Ситуации 3. Данный алгоритм будем называть алгорит мом с компенсацией одного конфликтного сигнала, а скорость этого алгоритма обозначим через 1. Для 1 вычислены верхняя и нижняя оценки, на основании которых получено приближенное значе ние 2 ln (2) 1, (9) 2 + + ln (2)(1 ( )0, 721) где и – вероятность ошибки восстановления после компенсации успешно принятого сигнала и конфликтного сигнала соответственно.

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

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

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

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

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

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

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

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

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

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

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

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

Если множество просматривается, то при () = оно оказывает ся просмотренным, и частично просмотренным – в противном случае (т.е. при () = ). Объединение просмотренных множеств является просмотренным множеством, т.е. если некоторое множество являет ся таковым к концу окна, то это означает, что все пакеты, которые возникли в моменты времени из этого множества, получили успешную передачу в окне или ранее, и покинули систему.

Используя вышевведенную терминологию, опишем функционирова ние алгоритма. Все время работы разбито на сеансы. Временная ось делится на (полу)интервалы длины +, где числа и явля ются параметрами алгоритма. Сеанс с номером 0 завершается в мо мент времени 0. Сеанс с номером начинается с просмотра интервала [( 1)( + ), ( + )). При 1 обозначим через и момен ты, соответственно, начала и окончания -го сеанса. При завершении очередного сеанса (скажем, с номером 1) следующий (-й) сеанс начинается сразу же ( = 1 ), если 1 ( + ). В противном случае происходит «простой» (интервалы не просматриваются, пакеты не передаются) в течение (( + ) 1 ) окон и после этого -й сеанс начинает работу, т.е. = 1 + (( + ) 1 ), где. – ближайшее целое сверху.

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

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

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

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

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

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

Шаг 2.1. Если отложенных интервалов нет в наличии, то проце дура просмотра непустого множества применяется к интервалу.

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

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

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

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

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

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

Действие 2. Множество 0 просматривается с вероятностью.

Если событие в канале, то Действие 2 повторяется снова – до тех пор, пока не произойдет событие. Это означает, что был успешно передан пакет, который появился в некоторый момент времени 0.

Точка удаляется из множества 0. Устанавливаем 0 := 0 {} и переходим снова к Действию 1.

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

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

– длинами интервалов и ;

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

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

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

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

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

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

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

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

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

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

+ { } = sup, (10) T(,, 0, 1, 2 ) где T(,, 0, 1, 2 ) – средняя длина сеанса при интенсивности вход ного потока равной единице и фиксированных параметрах алгоритма, (длины интервалов), 0, 1, 2 (вероятности передачи, которые ис пользуются в процедуре просмотра непустого множества). При этом супремум берется по всем возможным значениям 0, 1, 2, лежащим в интервале (0, 1), и неотрицательным значениям параметров,, для 1 которых 1.

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

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

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

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

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

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

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

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

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

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

Доказано, что скорость алгоритмов не зависит от вероятности лож ного конфликта в пустом окне 0 и при большом числе абонентов зна 1 чение скорости приблизительно равно, где 1 – вероятность лож 2 ного конфликта в окне, в котором передавал один абонент.

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

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

min(,21 ) (11), = 1 +,, (,1 +,1 ), =max(0,21 ) (21 )(21 ) 0, = { 1, = где,, =, = (2 ) 1, 2.

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

1 0,0 =, 1,0 =.

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

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

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

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

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

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

Длительность передачи пакета совпадает с длительностью окна. Числа и полагаются постоянными в течение всего периода времени ра боты системы. Базовая станция и все абоненты знаютмоменты начала -го кадра ( 1)( + ), -го окна 1 + и -го слота опроса ( 1) + 1, где,, 1, 2,...,. – ближайшее целое, не превосходящее аргумент.

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

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

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

() – ни один из абонентов не передает запрос ( = 0 или );

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

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

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

один раз за слотов опроса.

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

БС П л аниров ание перед ач и пак етов Ус пеш но перед анны е запрос ы К ад р (восход ящ ая перед ач а ) И нтерв ал д л я И нтервал д л я пакетов запрос ов В рем я З апрос ы перед аю тс я П ак еты перед аю тс я в с л отах опрос а в назнач енны х ок нах ч и сл о а бо нен тов А бон ент А бо нент А бо нент n Б ес к оне ч ное......

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

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

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

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

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

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

– Третьим аргументом является () = ( 1, 2,..., ) – последова тельность векторов обратной связи, известных к началу кадра.

– Четвертым аргументом является последовательность векторов (, ) = ( 1 (), 2 (),..., ()), связанная с абонентом, который сге нерировал пакет в момент времени. Компоненты вектора (1) (2) () () = ( (), (),..., ()) принимают следующие значения:

() () = 0, если абонент, пакет которого был сгенерирован в момент, () не передавал запрос в -м слоте опроса ( 1)-го кадра и () = 1 – в противном случае.

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

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

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

Средней задержкой пакета для заданной интенсивности входного потока, числа слотов опроса, числа окон и алгоритма СМД назовем () (,, ) lim sup [ (,, )]. (12) Скоростью алгоритма назовем верхнюю грань интенсивностей входного потока, который может быть передан с конечной средней задержкой посредством некоторого алгоритма СМД, и некоторой структуры кадра, :

sup{ : (,, ) }.

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

(, ) sup (, ), (14) (,) где (, ) – множество всех алгоритмов СМД, определенных для си стемы с слотами опроса и с окнами.

В диссертационной работе доказывается, что пропускная способ ность ограничена сверху величиной, (15) 1 + / где – пропускная способность классической модели СМД ( 0.568).

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

Доказано, что при = 1 эта функция принимает максимальное зна чение равное, +, где 0, 4877 – скорость алгоритма дробления для классической модели.

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

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ Основные результаты, полученные в диссертационной работе, мож но сформулировать следующим образом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ (статьи 1–18 опубликованы в изданиях, включенных в Перечень ВАК.) 1. Евсеев Г. С., Тюрликов А. М. Анализ пропускной способности одного алгоритма свободного множественного доступа, устойчивого к воздействию шумов // Проблемы передачи информации. — 1986. — Т. 22, № 2. — С. 104–109.

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

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

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

5. Беляев Е. А., Тюрликов А. М., Уханова А. С.

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

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

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

8. Винель А. В., Кобляков В. А., Тюрликов А. М.

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

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

10. Ni Q., Vinel A., Xiao Y., Turlikov A., Jiang T. In vestigation of bandwidth request mechanisms under point-to multipoint mode of WiMAX networks // IEEE Communica tions Magazine. — 2007. — Vol. 45, N. 5. — P. 132–138.

11. Андреев С. Д., Нилова А. В., Тюрликов А. М.

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

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

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

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

15. Андреев С. Д., Пустовалов Е. В., Тюрликов А. М.

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

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

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

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

18. Винель А. В., Дудин А. Н., Андреев С. Д., Тюрликов А. М. Анализ алгоритмов распространения тревожного сообщения c глобальным знанием в беспроводных сетях передачи данных с линейной топологией // Информационно-управляющие системы. — 2010. — T. 3. — С. 56–60.

19. Andreev S., Dubkov K., Turlikov A. IEEE 802.11 and 802.16 coopera tion within multi-radio stations // Wireless Personal Communications Journal. — 2010.

20. Vinel A., Qiang N., Staehle D., Turlikov A. Capacity analysis of reservation-based random access for broadband wireless access net works // IEEE Journal on Selected Areas in Communications. — 2009. — Vol. 27, no. 2. — P. 172–181.

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

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

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

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

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

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

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

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

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

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

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

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

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

34. Turlikov A., Markovsky S. Improved blocked algorithm in the channel of multiple access with false conflicts // ISC-NET’97. — St-Petersburg – 1997. — P. 31–32.

35. Lott M., Vinel A., Zhang Y., Turlikov A.Performance analysis of ran dom access in IEEE 802.16 // Proc. of the IEEE International Sympo sium on Personal, Indoor and Mobile Radio Communications. — 2005. — P. 1596–1600.

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

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

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

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

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

41. Andreev S., Dubkov K., Turlikov A. IEEE 802.11 and 802.16 coopera tion within multi-radio stations // Proc. of the 11th International Sym posium on Wireless Personal Multimedia Communications. — 2008. — P. 1–5.

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

Формат бумаги 60 84 1/16. Бумага офсетная. Печ. л. 1,25.

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

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.