Содержание к диссертации
Введение
1 Принципы функционирования протоколов подуровня УДС современных беспроводных централизованных сетей передачи данных 11
1.1 Вводные замечания 11
1.2 Протокол подуровня УДС беспроводной сети стандарта IEEE 802.16 11
1.2.1 Общие сведения 11
1.2.2 Структура подуровня УДС 12
1.2.3 Основные режимы работы 13
1.2.4 Принципы предоставления канальных ресурсов 17
1.3 Обзор исследований систем случайного множественного доступа 19
1.4 Базовая модель случайного множественного доступа 23
1.5 Вспомогательные результаты для базовой модели 27
1.6 Обзор исследований систем поллинга 28
1.7 Постановка задачи исследования 30
1.8 Выводы по главе 31
2 Исследование протокола УДС централизованной беспроводной сети 32
2.1 Использование СМД при резервировании 32
2.2 Модель централизованной сети с резервированием 34
2.3 Показатели производительности централизованной сети 37
2.4 Оценка пропускной способности централизованной сети 38
2.5 Учет особенностей беспроводной сети протокола IEEE 802.16 44
2.6 Выводы по главе 46
3 Исследование механизма резервирования посредством СМД в централизованных вычислительных сетях 47
3.1 Модель системы для исследования механизма резервирования 47
3.2 Описание алгоритма СМД binary exponential backoff. 49
3.3 Анализ алгоритма binary exponential backoff в условиях насыщения 50
3.3.1 Подход с цепью Маркова и биномиальным распределением 51
3.3.2 Подход с цепью Маркова и дополнительными состояниями простоя .56
3.4 Сравнение результатов аналитического и имитационного моделирования 60
3.5 Оценка эффективности случайного доступа в IEEE 802.16 61
3.5.1 Оптимизация размера конкурентного окна 61
3.5.2 Чувствительность задержки к изменению числа станций 64
3.5.3 Производительность алгоритма ВЕВ для различного числа абонентов и оптимизированных значений параметров 65
3.6 Анализ алгоритма binary exponential backoff в условиях произвольной нагрузки 67
3.7 Выводы по главе 70
4 Сравнительный анализ методов выполнения резервирования в централизованных вычислительных сетях 71
4.1 Вводные замечания 71
4.2 Модель канала с шумом 71
4.3 Анализ циклического опроса абонентов 72
4.4 Сравнительный анализ эффективности алгоритма ВЕВ и метода циклического опроса 77
4.5 Выводы по главе 81
Заключение 82
Приложение. Вычисление станционарного распределения цепи (3.2) 90
- Протокол подуровня УДС беспроводной сети стандарта IEEE 802.16
- Обзор исследований систем случайного множественного доступа
- Модель системы для исследования механизма резервирования
- Сравнительный анализ эффективности алгоритма ВЕВ и метода циклического опроса
Введение к работе
Актуальность темы. В настоящее время стремительными темпами происходит развитие сетей передачи данных. Это особенно заметно по активным процессам международной стандартизации, производства оборудования и развертывания беспроводных вычислительных сетей. Среди них все большее распространение получают, например, такие технологии как персональные сети IEEE 802.15 (Bluetooth), применяемые для связи компьютера с периферийным оборудованием и локальные сети IEEE 802.11 (Wi-Fi), активно используемые для организации зон общего доступа (hot-spot) в глобальную сеть Интернет. К настоящему моменту также принят международный стандарт универсальных городских сетей IEEE 802.16 (WiMAX), в которых беспроводной широкополосный доступ будет использоваться очень широким спектром приложений - от традиционного голосового сервиса до современных мультимедиа-приложений.
Все упомянутые технологии включают в себя специальные протоколы взаимодействия узлов сети для управления передачей пакетов по общему каналу связи. Наличие общего канала связи, коллективно используемого абонентами (зачастую очень большим их числом), является общей чертой современных и перспективных беспроводных вычислительных сетей. Вызванная практикой необходимость обеспечения максимально эффективного использования ограниченного ресурса беспроводного канала большим числом абонентов определяет огромный интерес и актуальность исследований в области анализа и разработки соответствующих протоколов множественного доступа. В частности, значительный интерес представляют исследования централизованных вычислительных сетей, в которых имеется центральная станция, координирующая работу остальных абонентов. Именно такая сетевая архитектура является основной в стандарте IEEE 802.16. Отличительными особенностями этого стандарта являются высокая сложность протокола подуровня управления доступом к среде (УДС), отвечающего, в частности, за организацию доступа абонентов к общему каналу связи, а также наличие большого числа неопределенных (vendor-dependent) частей, в которых стандарти-
зированы лишь некоторые механизмы сетевого взаимодействия, эффективное использование которых возлагается на производителя оборудования. Эти особенности технологии WiMAX, а также ее новизна, приводят к необходимости разработки методов анализа протоколов УДС для централизованных вычислительных сетей такого типа.
Согласно стандарту ШЕЕ 802.16 для резервирования ресурса канала абонентскими станциями используются либо методы случайного множественного доступа (СМД), либо упорядоченного опроса (поллинга). В первом случае абоненты передают запросы центральной станции в интервале передачи запросов и, если запросы от разных абонентов накладываются друг на друга, то возникает конфликт. Абоненты, попавшие в конфликт, осуществляют повторную передачу в соответствии с определенными правилами. Во втором случае центральная станция по некоторому алгоритму назначает каждое мини-окно для передачи запроса в точности одному абоненту и конфликтов не возникает. В обоих случаях, если запрос успешно принимается центральной станцией, то ею осуществляется распределение ресурса канала между абонентами, выполнившими резервирование, на основе метода временного разделения.
Разработке методов анализа описанных выше процессов, применительно к сети IEEE 802.16, посвящена диссертационная работа. Среди трудов по теории СМД можно выделить работы Дж. Месси, Б.С. Цыбакова, Дж. Капетанакиса, И. Рабина и др.; по анализу систем поллинга - Л. Клейнрока, X. Такаги, С. Борста и др. Аналитические методы анализа подуровня УДС современных беспроводных сетей, в частности, применительно к сетям IEEE 802.11 разрабатываются в работах Дж. Бьянки, Ф. Кали, В.М. Вишневского, А.И. Ляхова и др. Однако, в них практически не рассматриваются особенности управления доступом к среде в централизованных сетях стандарта IEEE 802.16.
Основной целью работы является разработка методов анализа протокола УДС стандарта IEEE 802.16 и оценка показателей производительности централизованной вычислительной сети передачи данных этого стандарта. Для достижения поставленной цели в работе решались следующие задачи:
1). Разработка модели централизованной системы СМД с резервированием, отражающей особенности функционирования сети ШЕЕ 802.16.
2). Разработка метода построения границ пропускной способности централизованной системы СМД с резервированием. Определение оптимального соотношения длительностей интервала передачи запросов и интервала передачи пакетов в восходящем канале централизованной сети.
3). Разработка метода расчета характеристик алгоритма СМД, используемого в централизованных сетях IEEE 802.16.
4). Разработка метода расчета характеристик алгоритма циклического опроса абонентов в централизованных сетях стандарта IEEE 802.16.
Методы исследования. Для решения поставленных задач использованы методы теории вероятностей, теории цепей Маркова, теории систем массового обслуживания, комбинаторного анализа, а также имитационное моделирование.
Научная новизна диссертационной работы заключается в следующем:
1). Разработана модель централизованной системы СМД с резервированием, которая в отличие от известных моделей, отражает существенные особенности протокола УДС перспективных беспроводных сетей IEEE 802.16.
2). Получены верхняя и нижняя границы пропускной способности централизованной системы СМД с резервированием. Найдено оптимальное по пропускной способности соотношение длительностей интервала передачи запросов и интервала передачи пакетов и показано, что оно не зависит от соотношения между длительностями передачи запроса и пакета.
3). Разработаны методы расчета средней задержки при выполнении резервирования с использованием алгоритма binary exponential backoff и с использованием циклического опроса абонентов, учитывающие, в отличие от известных методов, специфику формирования и передачи запросов в IEEE 802.16.
Практическая ценность и реализация результатов. Полученные результаты позволяют оценивать характеристики производительности перспективной беспроводной сети IEEE 802.16, что может быть использовано при ее построении. Найденное оптимальное соотношение длительностей интервала передачи запро-
сов и интервала передачи пакетов может использоваться производителями оборудования для повышения эффективности алгоритма распределения ресурсов восходящего канала планировщиком центральной станции.
Результаты диссертационной работы получены при выполнении госбюджетной НИР «Анализ и оптимизация производительности широкополосной беспроводной сети протокола IEEE 802.16» (Per. № 01200603037), выполненной под руководством автора диссертации, в Санкт-Петербургском Государственном Университете Аэрокосмического Приборостроения (ГУАП) по заказу Федерального агентства по образованию.
Полученные в диссертационной работе результаты используются в учебном процессе кафедры ИС ГУАП и АСОИУ ЛЭТИ.
Апробация работы. Основные результаты работы докладывались на следующих научно-технических конференциях: международной молодежной школе-семинаре БИКАМП'03 (Санкт-Петербург, 23 - 27 июня 2003 г.), VII научной сессии аспирантов ГУАП (Санкт-Петербург, 12-16 апреля 2004 г.), VIII научной сессии ГУАП (Санкт-Петербург, 11-15 апреля 2005 г.), на 16th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications -IEEE PIMRC'05 (Берлин, Германия, 11-14 сентября 2005 г.), политехническом симпозиуме «Молодые ученые - промышленности Северо-Западного региона» (Санкт-Петербург, 15 декабря 2005 г.), научной сессии ГУАП (Санкт-Петербург, 10-14 апреля 2006 г.), на 10th IEEE International Symposium on Consumer Electronics - ISCE'06 (Санкт-Петербург, 29 июня - 1 июля 2006 г.), Всероссийской школе-конференции «Мобильные системы передачи данных» (Москва, 11 -17 сентября 2006 г.), на 49th IEEE Global Telecommunications Conference -GLOBECOM'06 (Сан-Франциско, США, 27 ноября - 1 декабря 2006 г.), Всероссийской научно-практической конференции молодых ученых, аспирантов и студентов в рамках Программы «Участник молодежного научно-инновационного конкурса «Электроника 2006-2007» (Москва, 28 ноября 2006 г.), политехническом симпозиуме «Молодые ученые - промышленности Северо-Западного региона» (Санкт-Петербург, 8 декабря 2006 г.).
Публикации. По теме диссертационной работы опубликовано 17 печатных работ (из них 2 - статьи в ведущих научных журналах).
Основные положения, выносимые на защиту:
1). Метод расчета границ пропускной способности централизованной сети с резервированием посредством случайного доступа.
2). Метод расчета средней задержки передачи запроса для алгоритма случайного доступа стандарта IEEE 802.16;
3). Метод расчета средней задержки передачи запроса при использовании в IEEE 802.16 циклического опроса абонентов.
Объем и структура работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка использованных источников и приложения.
В первой главе работы описаны особенности подуровня управления доступом к среде в беспроводных централизованных сетях передачи данных на примере стандарта IEEE 802.16. Приведена базовая модель системы, используемая для анализа функционирования алгоритмов СМД, и введены определения основных характеристик системы СМД. Для базовой модели доказано несколько вспомогательных утверждений. Проведен обзор используемых для централизованных сетей алгоритмов СМД, а также методов упорядоченного опроса абонентов.
Во второй главе на основе базовой модели разработана модель централизованной сети с резервированием. Для такой сети введены определения протокола множественного доступа, скорости протокола множественного доступа и пропускной способности системы СМД с резервированием. Получены верхняя и нижняя границы пропускной способности такой системы.
Третья глава посвящена исследованию алгоритма СМД binary exponential backoff, используемого в сетях IEEE 802.16. Разработан метод расчета его характеристик. В частности, приведены способы расчета средней задержки передачи запроса для постоянного числа активных абонентов в сети и для произвольной интенсивности входного потока. Выполнена оптимизация параметров алгоритма ВЕВ.
В четвертой главе разработан метод расчета средней задержки передачи запроса при использовании в стандарте IEEE 802.16 циклического поллинга абонентов в канале с шумом. Результаты главы 3 также обобщены на случай наличия шума в канале связи. Выполнен сравнительный анализ случайного доступа и циклического поллинга в сети IEEE 802.16.
В заключении перечислены основные результаты, полученные в диссертационной работе.
В приложении приведен метод расчета стационарного распределения цепи (3.2).
Протокол подуровня УДС беспроводной сети стандарта IEEE 802.16
IEEE 802.16 [5] является стандартом перспективной технологии широкопо лосного беспроводного доступа городского масштаба. Основной задачей, возлагаемой на сети ШЕЕ 802.16, должно стать обеспечение беспроводного выхода домашних и корпоративных пользователей в глобальные сети (чаще всего Интернет) и обеспечение сервисов различного класса (от просмотра HTML страниц до передачи видеоданных в реальном масштабе времени).
Стандарт IEEE 802.16 определяет радио интерфейс, включающий в себя подуровень УДС и множество спецификаций физического уровня для неподвижных (а в IEEE 802.1 бе - мобильных) систем широкополосного беспроводного доступа. Согласно определению, данному в стандарте, это означает, что используемые соединения имеют ширину полосы пропускания свыше 1 МГц и поддерживают скорости передачи выше порядка 1.5 Мбит/с. Кроме того, ожидается, что рассматриваемые беспроводные системы будут поддерживать большое разнообразие мультимедийных служб со скоростями передачи от нескольких Мбит/с до 100 Мбит/с или выше в широком диапазоне различных условий, включая поддержку мобильности. Все эти технические требования приводят к значительной сложности рассматриваемой системы.
В связи с тем, что для используемой в стандарте англоязычной терминологии до сих пор нет устоявшихся русскоязычных аналогов, иногда мы будем использовать собственный перевод.
В настоящее время, согласно стандарту, подуровень УДС разделяется на три дополнительных подуровня. Эти подуровни следующие:
1. Зависящий от типа службы подуровень сопряжения (the service specific convergence sublayer, CS), выполняющий следующие функции: прием данных с вышележащего уровня; осуществление классификации пакетов вышележащего уровня; обработка (если требуется) пакетов вышележащего уровня, основываясь на классификации; доставка пакетов на подходящую точку доступа к службам нижнего уровня; прием пакетов от других уровней CS. В настоящее время существует 2 спецификации подуровня сопряжения: подуровень сопряжения с сетями ATM и пакетный подуровень сопряжения.
2. Основной подуровень (common part sublayer) включает в себя типичные функции УДС подуровня, а именно эффективное разделение беспроводной среды между группами абонентских станций. Этот подуровень более детально описан далее.
3. Подуровень безопасности (security sublayer) - обеспечивает конфиденциальность абонентов широкополосной беспроводной сети, путем шифрования данных между центральной и абонентскими станциями. Система защиты также включает в себя клиент/серверный протокол обмена ключами, в котором центральная станция (сервер) контролирует распределение ключей клиентским абонентским станциям.
Стандартом ШЕЕ 802.16 определено две архитектуры беспроводной сети передачи данных:
1. Режим точка-многоточка (pointo-multipoint, РМР). В этом случае центральная станция имеет секторную антенну, которая позволяет одновременно управлять множеством независимых секторов. В пределах заданного частотного диапазона и сектора антенны, все абонентские станции получают одинаковые данные (или их часть). Центральная станция является единственным передатчиком, работающим в этом направлении, называемым нисходящим (downlink). Таким образом, она может передавать, не осуществляя координации с другими абонентами (за исключением режима временного разделения, при котором происходит разделение времени на восходящий и нисходящий интервалы передачи). В общем случае нисходящий трафик передается в широковещательном режиме. При передаче информации в восходящем направлении - от абонентов к центральной
станции возникает задача организации множественного доступа, которая подробно исследуется ниже.
2. Режим Mesh-mode (дополнительный). В противоположность к РМР, где трафик передается только между центральной станцией и абонентами, в режиме Mesh, трафик может маршрутизироваться через другие абонентские станции и передаваться напрямую между абонентскими станциями. В зависимости от алгоритма, используемого в протоколе передачи, это может быть выполнено либо на базе распределенного планирования, в равной степени осуществляемого абонентами, либо на базе центральной Mesh-станции, которая эффективно осуществляет централизованное планирование, либо на основе комбинации обоих методов.
В режиме РМР время разделено на кадры (frames) фиксированной длительности. УДС-протокол поддерживает несколько способов разделения канала. В случае системы с частотным разделением (frequency division duplexing, FDD), восходящий и нисходящий каналы располагаются на отдельных частотах. Как для восходящей, так и для нисходящей передач используется кадр фиксированной длины. В случае временного разделения (time division duplexing, TDD), восходящая и нисходящая передачи происходят в различные моменты времени, используя, при этом, весь частотный диапазон. Кадр TDD имеет фиксированную длину и содержит один подкадр восходящей передачи и один подкадр нисходящей (рисунок 1.1). Разделение времени в TDD адаптивно в том смысле, что соотношение между восходящей и нисходящей передачами может отличаться от кадра к кадру. Порог между восходящей и нисходящей передачами является параметром системы и управляется вышележащими уровнями.
Обзор исследований систем случайного множественного доступа
Как показано в предыдущем параграфе на примере стандарта IEEE 802.16, в восходящем канале централизованных беспроводных сетей возникает задача совместного использования абонентскими станциями общего канала связи. Согласно классификации из [8], основанной на работе [9], методы разделения ресурса подразделяются на статические (фиксированные) и динамические (рисунок 1.2).
При статическом разделении ресурса в системе канал связи жестко закрепляется за конкретным абонентом системы, на все время ее работы, путем частотного разделения (каждому абоненту назначается своя частота), временного разделения (каждому абоненту выделяется свой временной интервал) или кодового разделения (сигнал каждого абонента специальным образом кодируется).
При динамическом разделении ресурса в процессе функционирования системы, тем или иным способом, определяется потребность абонента в ресурсе, и ресурс отдается одному из пользователей, нуждающихся в нем в данный момент времени. Динамические методы разделения ресурса включают два класса методов: методы выделения ресурса по запросу и методы случайного доступа к ресурсу.
Основная идея метода случайного доступа (предложенного в начале 70-х годов прошлого века) заключается в том, что абонент источник практически сра зу после появления у него сообщения осуществляет его передачу в канал. Если при этом в канале отсутствуют сообщения от других абонентов, то абонент получатель успешно принимает это сообщение. В противном случае, в канале происходит наложение сообщений от различных абонентов, так называемый конфликт. При возникновении конфликта каждый из участников конфликта через случайное время повторяет передачу. Такой класс методов использования ресурса канала получил название СМД. СМД целесообразно применять при условиях большого числа абонентов и пульсирующего входного трафика. Эти условия часто имеют место, в частности, в современных централизованных беспроводных сетях.
Общепризнанно, что первой системой, в которой был использован СМД, явилась система, созданная для связи между вычислительными машинами Гавайского университета. Эта система получила название АЛОХА. В дальнейшем, вышеописанный простейший алгоритм разрешения конфликта получил название АЛОХА [10].
Уже с момента появления алгоритма АЛОХА наметилось некоторое разделение направлений, по которым развивались теоретические и практические исследования.
В теоретических исследованиях основной упор был сделан на изучение поведения алгоритма АЛОХА при большом числе абонентов. При этом было доказано, что увеличение числа абонентов приводит к катастрофическому увеличению задержки. В работах Цыбакова, Михайлова [10,12] и Капетанакиса [13] были предложены так называемые древовидные алгоритмы разрешения конфликта и доказано, что с помощью этих алгоритмов можно получить конечную задержку при доступе к общему каналу бесконечного числа абонентов. Таким образом, автоматически обеспечивалась работа и при любом конечном числе абонентов. С этого момента начался бурный рост числа работ, посвященных исследованию методов СМД. Максимальное число работ относится к середине 80-х годов прошлого века. Однако в последующие пятнадцать лет интерес к исследованиям в этом направлении постепенно уменьшался. Тем не менее, появление беспроводных сетей привело к тому, что в последние годы снова наблюдается тенденция к увеличению числа работ, посвященных СМД. Наиболее полный обзор современных работ по данной тематике содержится в [14-17].
В практических разработках, начиная с середины семидесятых годов прошлого века, основной средой передачи для вычислительных сетей являлся кабель. Поэтому основной задачей для практики стала адаптация алгоритма АЛОХА к особенностям кабельных сетей. При тех скоростях передачи, которые использовались в таких сетях, время передачи сообщения существенно превышало время распространения физического сигнала. Данная особенность позволила значительно уменьшить как вероятность возникновения конфликта, так и время, затрачиваемое на обнаружение конфликта за счет использования алгоритма CSMA/CD (множественный доступ с прослушиванием несущей и обнаружением коллизий [7]). В этом алгоритме абонент может через короткий промежуток времени, равный времени распространения физического сигнала, определить, передают другие абоненты в этот момент времени или нет. Кроме того, проверка канала осуществляется также и во время передачи пакета. В том случае, когда абоненты слышат, что в канале произошел конфликт, они могут прервать передачу своих пакетов. CSMA/CD был впервые применен в сети Ethernet, разработанной фирмой Xerox в 1975 г., а затем вошел в стандарт ШЕЕ 802.3
Модель системы для исследования механизма резервирования
Рассмотрим п абонентов, имеющих буфер, достаточный для хранения только одного запроса (рассмотрение очередей запросов не имеет смысла). Согласно [5], как это описано в параграфе 1.2, каждый абонент может потенциально установить несколько соединений с различными, согласованными с центральной станцией, параметрами качества обслуживания, и запросы могут быть сгенерированы либо на одно соединение, либо на все соединения абонента. Таким образом, мы предполагаем, что каждый абонент имеет в каждый момент времени только одно соединение. В случае наличия нескольких соединений у абонента, я можно интерпретировать как общее число соединений в системе.
Определим величину номинального входного потока запросов Л как среднее число запросов, появляющихся в системе за длительность кадра, при условии, что в системе нет активных абонентов. За длительность кадра каждый пассивный абонент генерирует запрос с вероятностью л = Л1п. Таким образом, чем больше активных абонентов имеется в системе, тем меньше величина реального входного потока в системе. Новый запрос помещается в буфер и передается не ранее чем в следующем кадре. Как и в главе 2, будем полагать, что в каждом кадре имеется К мини-окон для случайного доступа.
Как и ранее будем считать, что канал является бесшумным, т.е. если в точности один абонент передает в мини-окне, то передача является успешной. В противном случае происходит конфликт. Более того, будем считать, что абоненты получают информацию обратной связи о ситуациях в мини-окнах текущего кадра от центральной станции к началу следующего кадра. Согласно [5] данная информация не передается явно, а для принятия решения о конфликте используется специальный интервал ТІ6. Если абонент, не получает от центральной станции грант в течение этого интервала, то он считает, что запрос не был доставлен.
Для разрешения возникающих конфликтов используется специальный вариант алгоритма ВЕВ. Перед каждой попыткой передачи, абонент равномерно выбирает целое число из интервала [0,JV, -1], где Wi - текущее значение его конкурентного окна. Выбранное значение {счетчик отложенной передачи), показывает количество мини-окон, которое абонент должен ждать перед попыткой передачи запроса. Для первой попытки передачи величина конкурентного окна устанавливается равной \УШ. В случае конфликта абонент удваивает значение конкурентного окна, так что после / конфликтов, Wn оно становится равным 2 W . Конкурентное окно не удваивается в том случае, если оно достигло максимального значения JFmax =2mWmin, где т максимальная стадия отката. Как и в IEEE 802.11 в случае успешной передачи конкурентное окно устанавливается в минимальное значение Wmin.
Стандарт IEEE 802.16 не определяет никакой взаимосвязи между параметрами IFmin, fFmax и К. Заметим, что если W a К, тогда некоторые мини-окна никогда не будут использоваться в течение первой попытки передачи. Более того, мы устанавливаем W = IK, где / - натуральное число, для того чтобы равномерно распределить попытки передачи по доступным мини-окнам. Как показано ниже, это допущение приводит к значительному упрощению аналитического анализа.
Несложно видеть, что работу системы, описанной в параграфе 3.2 можно описать многомерным Марковским процессом с дискретным временем: {Ь{0,си)(0Ж0) У = 1,"/ = 0,1,2,. (3.1) где c(j)(t) - стадия откатау-го абонента, bU)(i) - счетчик отложенной передачи 7-го абонента, d(t) - номер мини-окна в текущем кадре. Интервал времени между двумя последовательными моментами времени t и /+1 соответствует одному мини-окну.
Пусть работа системы описывается процессом (3.1). Введем в рассмотрение Pu\t)- вероятность того, что в момент времени t абонент с номером/ попадет в конфликт. Понятно, что эта вероятность определена лишь в тех случаях, когда абонент в момент времени t начинает передачу, т.е. при условии, что su)(t) = 0 и зависит от того, в каком состоянии находится система.
Сравнительный анализ эффективности алгоритма ВЕВ и метода циклического опроса
Рассмотрим типовой сценарий со следующими параметрами « = 30, К = 5 и рассчитаем среднюю задержку при передаче запроса для номинальной интенсивности входного потока на мини-окно пліК (Рисунок 4.3) для случая бесшумного канала связи (ре=0). Аналогичные значения рассчитаны для алгоритма ВЕВ с использованием метода, разработанного в главе 3. Заметим, что результаты, полученные с помощью нашей аналитической модели (линии) полностью совпадают с результатами имитационного моделирования (символы). Можно видеть, что для рассмотренного сценария центральной станции целесообразно производить переключение со случайного доступа на циклический опрос абонентов, когда величина плі К выше, чем 0.4.
На рисунке 4.5. показана зависимость средней задержки при передаче запроса от вероятности возникновения запроса у абонента и вероятности искажения запроса ре. Видно, что вероятность искажения запроса оказывает существенное влияние на производительность циклического опроса и влияние шума в канале связи должно быть учтено при анализе работы системы.
Сравним производительность алгоритма ВЕВ и циклического опроса абонентов в условиях канала с шумом (Рисунок 4.5). Интересным результатом является тот факт, что точка пересечения кривых сдвигается влево с увеличением вероятности искажения запроса шумом ре. Это означает, что для канала с шумом (например, когда ре = 0.3) целесообразно переключаться на поллинг когда п становится больше, чем примерно 0.3 (а не 0.4 как для условий идеального канала).
Мы не приводим никаких типовых значений для вероятности п поскольку эта вероятность сильно зависит от работы алгоритма планирования абонента, который является зависимым от реализации (vendor-dependent) равно как и от типа трафика. С одной стороны, результаты показывают, что метод опроса является предпочтительным в подавляющем большинстве случаев. С другой стороны, важно отметить, что если будет использоваться механизм "piggybacking" (параграф 1.2), в реальной системе вероятность л скорее всего будет иметь достаточно маленькие значения, что является подходящим сценарием для использования случайного доступа.
1) Работа метода циклического поллинга, используемого для управления передачей запросов в централизованной сети стандарта IEEE 802.16, описана с использованием методов теории цепей Маркова.
2) Разработан метод вычисления средней задержки при передаче запроса при использовании метода циклического поллинга для случая произвольной интенсивности входного потока.
3) Исследовано влияние шума в канале связи на производительность алгоритма ВІВ и циклического опроса.
4) Выполнен сравнительный анализ алгоритма ВЕВ и алгоритма циклического опроса в бесшумном канале и канале с шумом.
Заключение
1). Разработана модель централизованной беспроводной сети с резервированием посредством случайного доступа. Для такой сети введены понятия алгоритма СМД, задержки передачи пакета, скорости алгоритма СМД, пропускной способности сети, протокола множественного доступа.
2). Построены нижняя и верхняя границы пропускной способности централизованной беспроводной сети.
3). Найдено отношение длительностей интервала передачи пакетов и интервала передачи запросов, при котором пропускная способность сети максимальна.
4). Разработано два метода анализа алгоритма СМД ВЕВ, применяемого для управления передачей запросов в централизованной сети стандарта IEEE 802.16, для случая фиксированного числа активных абонентов.
5). Разработан метод вычисления распределения вероятностей числа абонентов в системе и средней задержки при передаче запроса с использованием алгоритма ВЕВ для случая переменного числа активных абонентов.
6). Разработан метод вычисления средней задержки передачи запроса при использовании метода циклического поллинга для резервирования в IEEE 802.16 в случае произвольной интенсивности входного потока. Выполнен сравнительный анализ алгоритма ВЕВ и алгоритма циклического опроса в бесшумном канале и в канале с шумом.
7). Разработан комплекс программ имитационного моделирования и численного расчета вероятностно-временных характеристик протоколов множественного доступа централизованных беспроводных сетей.
