WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

0,3 0,4 0,5 0,6 0,7 0,8 0,9 Интенсивность входного потока, Рисунок 1. Время первого выхода из рабочей области для алгоритма ДЭО: 1 – аналитическая верхняя оценка; 2 – результаты имитационного моделирования Время первого выхода, T В реальных системах связи, например, в протоколе IEEE 802.11, рассматриваемая проблема стабильности до недавнего времени не была актуальной в силу относительно небольшого числа абонентов, а также особенностей построения протокола подуровня УДС. Тем не менее, вопрос стабильности становится важным при работе региональной (городской) сети по протоколу IEEE 802.16, который предполагает одновременное взаимодействие с базовой станцией сотен абонентов.

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

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

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

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

Задержкой передачи запроса A(K, ) назовем случайную величину, равную интервалу времени от момента поступления запроса в систему до момента окончания его успешной передачи или до момента, когда он был отброшен. Здесь K – число конкурентных слотов в кадре, а – интенсивность входного потока. Введем в систему новый запрос в (s) некотором слоте s и обозначим его задержку через A (K, ). Среднюю задержку передачи запроса определим как (s) DA(K, ) lim sup E[A (K, )]. (1) s Скоростью алгоритма A в системе без потерь назовем верхнюю грань интенсивностей входного потока, для которых алгоритм обеспечивает конечную среднюю задержку передачи запроса:

RA(K) sup{ : DA(K, ) < }. (2) Рассмотрим случайную величину Z(i), которая принимает значение 1 в случае успеха в конкурентном слоте i. Величина Z(i) зависит от s- K и. Рассмотрим также случайную функцию A(K,, s) Z(j).

j=Определим интенсивность выходного потока на слот для алгоритма A в системе с потерями как E[A(K,, s)] A(K, ) lim inf. (3) s s Скоростью алгоритма A в системе с потерями назовем наивысшую интенсивность выходного потока успешно переданных запросов при условии, что алгоритм обеспечивает конечную среднюю задержку передачи запроса:

RA(K) sup A(K, ). (4) :DA(K,)< Вычислим скорость алгоритма ДЭО в системе с потерями для случая минимально возможной задержки, обозначая ее RBEB(1)(K), где 1 означает единственную попытку передачи. Максимальное число Q повторных передач запроса установим равным 0. Допустим также бернуллиевский входной поток и наличие буфера для хранения одного запроса. Такая система допущений практически оправдана при передаче чувствительного к задержке трафика (например, голосового потока VoIP). В диссертационной работе для заданного числа абонентов M показана справедливость следующего утверждения.

Утверждение 1. Скорость алгоритма ДЭО в системе без повторных передач пакетов данных не зависит от K и вычисляется как M -G G RBEB(1) = 1 -, (5) M где G – общее число групп абонентов.

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

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

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

Утверждение 2. Вероятность передачи запроса меченым абонентом pt в системе с потерями пакетов данных вычисляется как 2(1 - 2pc)(1 - pQ+1) c pt =, (7) W0(1 - pc)(1 - (2pc)Q+1) + K(1 - 2pc)(1 - pQ+1) c если Q m и 2(1 - 2pc)(1 - pQ+1) c pt =, (1 - 2pc)(W0(1 - 2mpQ+1) + K(1 - pQ+1)) + pcW0(1 - (2pc)m) c c если Q > m.

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

Выражения (6) и (7) представляют собой нелинейную систему уравнений с двумя неизвестными pc и pt, которая может быть решена численно. Тогда значение скорости алгоритма ДЭО в случае не более (Q+1) попытки передачи запроса вычисляется как RBEB(Q+1)(K) = Mpt(1 - pt)M-1. (8) Скорость алгоритма ДЭО для общего опроса с M = 40 и K = 8 показана на рисунке 2. Предложенный аналитический подход позволяет максимизировать скорость алгоритма при Wopt = 2M - K и m = 0, то есть в приведенном примере Wopt = 72. Для такой оптимальной системы скорость не зависит от максимального числа передач. Кроме того, существует такое значение величины Q, при котором алгоритму ДЭО с неоптимальными параметрами удается достичь скорости в системе с потерями пакетов данных, равной его скорости в системе без потерь.

0,0,72, 0,0,32, 0,0,W = 16, m = 0,0 5 10 15 Максимальное число попыток передачи, Q+Рисунок 2. Эффективность общего опроса при ограничении на число повторных передач Перейдем теперь к анализу общей задержки передачи сообщения в системе связи как на этапе поступления запросов в сеть, так и на этапе их обслуживания. Для упрощения анализа сделаем предположение о пуассоновском входном потоке новых сообщений с суммарной интенсивностью входного потока сообщений в единицу времени. Определим общую задержку передачи сообщения как интервал времени от момента его поступления до момента окончания успешной передачи соответствующего ему пакета данных. Общая задержка некоторого меченого сообщения состоит из следующих слагаемых:

r s Di = Di + + Di +, (9) (K) BEB(Q+1) на слот, R Скорость алгоритма ДЭО r где компоненты Di определены следующим образом. Di – задержка резервирования, равная интервалу времени от момента поступления меченого сообщения к абоненту с номером i до момента начала отправки этим абонентом соответствующего запроса в восходящем канале; – s время передачи запроса (длительность конкурентного слота); Di – задержка обслуживания, равная интервалу времени от момента окончания отправки абонентом с номером i запроса на меченое сообщение до момента начала успешной передачи соответствующего ему пакета данных в восходящем канале; – длительность передачи пакета данных.

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

Утверждение 3. Верхняя оценка для общей задержки передачи сообщения в централизованной системе связи вычисляется как 3 1 - pr Tframe (2 - pr) M + E[D] + Tframe + + K +, (10) 2 pr 2pr(1 - ) где pr – вероятность успешной передачи запроса в конкурентном интервале, которая может быть найдена с помощью выражения (7);

Tframe – длительность кадра; – коэффициент загрузки абонента.

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

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

Древовидные алгоритмы СМД достигают более высоких показателей производительности по сравнению с алгоритмами АЛОХА и ДЭО.

В настоящее время принято различать стандартный древовидный алгоритм (СДА) и модифицированный древовидный алгоритм (МДА).

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

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

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

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

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

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

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

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

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

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

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»