Новый метод оценки алгоритмов распределения OVSF-кодов в стандарте WCDMA

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004.3. 067
НОВЫЙ МЕТОД ОЦЕНКИ АЛГОРИТМОВ РАСПРЕДЕЛЕНИЯ ОУБГ-КОДОВ В СТАНДАРТЕ ШСОМА
И. А. Мельник,
ведущий инженер-программист
ООО «Научно-производственная фирма „Беркут“»
OVSF (Orthogonal Variable Spreading Factor) коды используются для поддержки разных скоростей передачи данных для различных пользователей в WCDMA системах. В данной работе, проанализированы существующие алгоритмы распределения кодов и решаемые ими проблемы. Для того чтобы оценить эффективность алгоритмов, мы предлагаем метод, который учитывает возникающие блокировки между кодами во время распределения. На базе этого метода можно построить аналитические модели для оценки алгоритмов.
Orthogonal Variable Spreading Factor (OVSF) codes are used to support different transmission rates for different users in WCDMA systems. In this paper, we analyze existing code allocation algorithms and problems that they have to solve. To estimate the efficiency of the algorithms we propose a method, which consider blockings between codes during assignment. On basis of this method it is possible to build analytical models for an estimation of different algorithms.
Введение
WCDMA (Wideband CDMA) — системы третьего поколения (3G), которые поддерживают переменную скорость передачи данных для приложений с различным «качеством услуги» (QoS — Quality of Service). Появление 3G систем было связано с появлением возможности передачи данных на больших скоростях (до 2 Мбит/с). В любой CDMA системе множественный доступ к каналам передачи данных обеспечивается с помощью кодов, при этом полоса частот — одна на всех пользователей, Поэтому схемы управления кодами являются составляющей частью системы, и главной целью их является эффективное использование ресурсов сети. В данной статье предлагается вероятностный метод оценки алгоритмов распределения OVSF-кодов в стандарте WCDMA.
Каналообразующие коды в WCDMA
WCDMA — это телекоммуникационная система, которая разделяется на две основные части: радиосеть (UTRAN) и проводная сеть. В радиосети передаваемые пакеты информации распределяются с помощью RNC (Radio Network Controller), а именно, распределение представлено МАС-протоколом. MAC распределяет пакеты данных в оба выделенных канала: контрольный канал (DPCCH — Dedicated
Physical Control Channel) и канал данных (DPDCH -Dedicated Physical Data Channel), а также в разделяемый канал (PDSCH — Physical Dedicated Shared Channel, далее DSCH). В DSCH может происходить распределение каналообразующих кодов между подключенными абонентами или мобильными станциями каждый раз для фрейма данных [1 ].
Отображение каналов в системе следующее. Логические каналы отображаются на транспортные, которые характеризуются тем, как информация будет передаваться по радиоинтерфейсу. Они предоставляются физическим уровнем для МАС-уровня. Транспортные каналы отображаются в физические (DPCH — Dedicated Physical Channel) на физическом уровне. В DPCH транспортные каналы мультиплексируются с помощью каналообразующих кодов. Далее информация из всех DPCH суммируется и скремблируется с помощью кода Голда. Одна базовая станция использует один код Голда, т. е. с помощью кодов Голда разделяются между собой сигналы базовых станций в прямом канале (от базовой станции к мобильной). Физический уровень контролируется с помощью RRC (Radio Resource Controller) [2].
В WCDMA в качестве каналообразующих кодов используются ортогональные OVSF-коды (Orthogonal Variable Spreading Factor), которые обеспечивают множественный доступ, а также используются для
¦ Рис. 1. OVSF-кодовое дерево
расширения спектра сигнала. Расширение спектра достигается путем отображения каждого бита данных на выделенную кодовую последовательность. Длина последовательности называется расширяющим коэффициентом (SF — Spreading Factor). Возможные OVSF-коды могут быть представлены узлами полного двоичного дерева, которое изображено на рис. 1 [3].
На каждом уровне дерева все кодовые последовательности ортогональны. Более того, последовательности разной длины на разных уровнях тоже ортогональны друг другу, за исключением случая, когда более короткая последовательность является родительской ДЛЯ более ДЛИННОЙ. Обозначим КОД Сj как родитель кода с-. Выделяются следующие важные признаки дерева [4]:
1. Каждый узел Cj, за исключением корня, может быть сгенерирован из предка с,. Допустим, с, естьх. Далее мы можем получить су = [х, х], если Cj — правый потомок с, или су = [х, -х], если су-левый потомок С/, где -х- инвертированная последовательность х.
2. Если SF с, -2k, тогда SF су = 2к+ Следовательно, если скорость передачи данных с, -2Г, то скорость передачи с- = 2Г~1, Таким образом, листы имеют минимальную скорость передачи данных, а корень — максимальную.
Одновременное использование потомков или предков не может быть разрешено, потому что коды, имеющие прямые родственные связи, не ортогональны.
Стандартом определены два критерия при распределении OVSF-кодов [5].
1. Использование. Схема выделения кодов, которая сохраняет большее количество кодов с малыми SF, имеет больший шанс на использование. Дело в том, что мобильная станция имеет ограничение к на количество одновременно используемых кодов. Если стратегия определила л кодов для передачи больше к, то мобильная станция блокируется.
2. Сложность. Чем больше используется кодов, тем сложнее система. Возможна ситуация, когда согласно первому критерию есть, например, две альтернативы из одного и двух кодов. В этом случае предпочтительнее выбор схемы с меньшим количеством кодов, т. е. выбор одного кода.
Существующие алгоритмы распределения кодов
Описание основных (классических) стратегий распределения кодов можно найти в работе [6].
Целью или задачей стратегий и алгоритмов управления 0/ЭР-кодами служит разрешение двух основных проблем [6]: 1) проблемы распределения (выдачи) кодов- 2) проблемы перераспределения кодов. Обе проблемы связаны с возникающими блокировками родительских и дочерних кодов при выделении кода. Чем больше блокировок — тем меньше емкость дерева (т. е. количество кодов, которые могут быть выделены новым МС), и тем больше вероятность отклонения запросов на подключение к системе. На рис. 2 показан пример дерева из четырех уровней, в котором выделено три кода.
Проблема распределения кодов возникает в момент запроса при наличии нескольких подходящих кандидатов. Должна быть выбрана такая стратегия, которая при увеличении нагрузки стремится уменьшить количество блокируемых кодов при выделении кода. Также стратегия должна стремиться оставить коды с меньшим ЭР (скоростные коды) для удовлетворения запросов услуг с высокой скоростью.
Проблема перераспределения кодов возникает тогда, когда емкость дерева позволяет удовлетворить запрос, но подходящего свободного кода нет, т. е. он блокирован из-за занятых потомков с большими ЭР В этом случае можно «освободить» требуемый код путем размещения занятых потомков в соседних частях дерева на тех же БР-уровнях. Здесь должна быть выбрана такая стратегия, которая минимизирует затраты в процессе перераспределения кодов, чтобы уменьшить задержку при обработке запроса. Например, в ситуации, изображенной на рис. 2, коды с ЭР = 2 заблокированы и запрос на код будет отклонен. Если освободить код с14, то коды с7 и с3 будут разблокированы и запрос на код с ЭР = 2 может быть удовлетворен. Алгоритм перераспределения в момент запроса на код с ЭР = 2 должен поменять выделенный мобильной станции код с14 на код с10.
Перераспределение включает определение поддерева, которое должно быть освобождено (т. е.
¦ Рис, 2. Пример используемого (Э/5Р-дерева: # - выделенные коды- й-г — заблокированные коды-
О — свободные коды
поддерева с подходящим блокированным корневым кодом, выделение которого произойдет в соответствии со стратегией выдачи кодов). Помимо этого, алгоритм перераспределения должен определить, куда будут перемещены занятые коды (т. е. поиск свободных кодов в соседних частях кодового дерева, в соответствии со стратегией выдачи кодов, с SF, равными SF занятых потомков подходящего заблокированного кода).
Основными можно назвать три стратегии [6]:
1. Случайный доступ (random).
2. Использование самого левого (leftmost).
3. Самый заполненный — первый (crowded-first).
Первая стратегия представляет собой случайный доступ кузлам дерева с требуемым SF с равными вероятностями. Если при поступлении вызова есть несколько свободных кодов с нужным SF, то случайным образом выбирается какой-нибудь код. В противном случае запрос отклоняется.
Суть второй стратегии состоит в том, что при наличии нескольких подходящих кодов выбирается самый левый. Другими словами, правая часть дерева оставляется для кодов с меньшим SF, или в правой части концентрируется вся оставшаяся емкость дерева.
В случае использования третьей стратегии при наличии нескольких подходящих кодов выбирается тот, чье поддерево до ближайшего корня заполнено в большей степени. При повторном возникновении конфликта уровень корня понижается, и сравниваются полученные поддеревья. Если конфликт не разрешен с учетом описанного алгоритма, то выбирается либо самый левый, либо самый правый коды, в зависимости от настройки.
Стратегии перечислены в порядке увеличения эффективности и увеличения вычислительных затрат при реализации.
Примеры других стратегий и алгоритмов можно найти в работах [1], [7] - [10].
Вероятностный метод оценки
Определим состояние как количество занятых кодов на уровнях дерева. Предположим, что имеется дерево из четырех уровней. Тогда состояние -это вектор из Kj элементов, /=1,2,3, 4- К, — число занятых кодов на уровне /'-. Увеличение значения К, или переход в другое состояние означает выдачу кода, уменьшение — высвобождение. Первый переход происходит с интенсивностью запросов с QoS, требующих коды на различных уровнях дерева. Второй переход происходит с интенсивностью обработки вызова или, другими словами, зависит от среднего времени использования абонентом услуги (среднего времени занятости кода).
Прием запроса ограничивается емкостью дерева или выражением
К- + 2К2 + 4К& quot-з + 8К4 & lt- Стах, (1)
где Стах — количество листов кодового дерева- К (-коды с наибольшим SF и наименьшей скоростью (листы).
В начальном состоянии все значения элементов К, равны нулю. Построим граф возможных переходов из начального состояния. Пусть поток запросов кодов, поступающий в систему, — простейший. Простейший поток характеризуется следующими свойствами.
1. Интенсивность потока постоянна и не зависит от времени.
2. События в потоке появляются по одному, а не группами, одновременно по несколько событий сразу.
3. События, образующие поток, появляются в те или иные моменты времени независимо друг от друга- каждое из них вызвано своими собственными причинами.
В этом случае переход из состояния в новое состояние означает увеличение или уменьшение какого-то элемента /С, на единицу. Интенсивность переходов при увеличении значения /С, может быть неодинаковой и зависеть от скоростных характеристик кода или от услуг, запрашиваемых абонентами. Сопоставим каждому переходу, или ребру графа, вероятность перехода, или вероятность запроса абонентом услуги, которая предоставляется с помощью кода с определенными скоростными характеристиками. Сумма вероятностей переходов из состояния в другие возможные состояния равна единице.
В случае, когда используется алгоритм перераспределения кодов, то можно сказать, что если при поступлении запроса емкость дерева позволяет «вместить» его, то он будет обработан с вероятностью 1, т. е. если при поступлении запроса выполняется неравенство (1), то запрос будет обработан.
Вероятность блокировки запросов — это доля времени, в течение которого система находится в состояниях, когда переход в новое состояние нарушает условие (1).
Общая пропускная способность системы — это сумма произведений пропускной способности каждого состояния на долю времени, в течение которого система находится в этом состоянии (предельная вероятность). Пропускная способность состояния -это количество информации, например, в байтах, которое можно передать с помощью кодов, используемых в этом состоянии.
В случае, если алгоритм перераспределения не используется, то даже при выполнении условия (1) возможны ситуации, когда код не выдается. Это может происходить ввиду блокировок, возникающих при выдаче кода. Для отражения состояния по блокированным кодам, каждому К, сопоставим значение В/, которое показывает количество заблокированных кодов на этом уровне. Теперь состояние -это количество занятых кодов и количество блокированных кодов на каждом уровне дерева, т. е. состояние описывается двумя векторами: {К}м, {В}ы, где N — количество уровней дерева.
При запросе кода на уровне / вероятность перехода на следующий уровень будет равняться нулю или блокировка вызова будет возникать тогда, ког-
да ВI + К, = С/, где с, — максимальное количество кодов на уровне /'-. Соответственно, для принятия вызова необходимо, чтобы выполнялось условие
В, + (К, + 1) & lt- С-,. (2)
Выражение (1) при этом дополняется выражением (2), т. е. невыполнение одного из условий влечет за собой отказ в обработке запроса на код.
Вероятность блокировки в этом случае — доля времени, в течение которого система находится в состояниях, переход из которых в следующее нарушит условие (1) или (2).
Выдача кода дерева влечет за собой блокировку всех потомков и родителей кода из-за отсутствия ортогональности между ними. Таким образом, увеличение К, влечет за собой увеличение значений В на всех уровнях, меньших / (дочерние коды), и может повлечь увеличение значений В на следующих уровнях, больших /'- (родительские коды).
Обозначим N количество уровней в дереве, л- уровень, на котором происходит выдача кода, л = 1 — уровень кодов с наибольшим ЭР и наименьшей скоростью (листы). Тогда при выдаче кода на уровне л количество блокируемых кодов на уровнях 1 & lt- / & lt- (ЛI — п) (все дочерние) равно В, = 2Л/~П_-+1. Общее количество блокируемых дочерних кодов равно
Л/-п
12
/=1
Л/-П-/+1
(3)
Таким образом, если не учитывать количество блокируемых родительских кодов, то при обработке запроса на код уровня л, т. е. при увеличении Кп, изменение вектора К будет следующим:
Кы, Кы_ь …, Кп + 1, К,.
При этом вектор В изменится следующим образом:
Вы, е"_,… В"_"+ 2, 4… 8,4−2"--"- (4)
Следовательно, выдача любого кода на уровне п всегда влечет за собой блокировку фиксированного количества дочерних кодов, рассчитываемых по формуле (3), при этом вектор В принимает вид (4). Другими словами, количество блокируемых дочерних кодов для каждого уровня фиксировано,
или наличие вектора В не увеличивает количество состояний, в которые можно перейти из текущего состояния.
На рис. 3 показан пример дерева, где выдан код с2. Количество заблокированных дочерних кодов равно шести. При выдаче кода с3 количество заблокированных дочерних кодов будет тем же.
Рассмотрим блокировку родительских кодов. Количество блокируемых кодов зависит от того, какие «родственники» кода уже выданы. Интерес представляет любой «родственник» натом же уровне, что и целевой код, у которого родительский код является родителем целевого и имеет наименьшее расстояние (в уровнях) до него. Количество блокированных кодов выражается формулой
Ва5С = 1−1-1, (5)
где / - уровень целевого кода с/ у- / - уровень родительского кода С/, который одновременно является родителем выданного кода с, к. Из всех имеющихся с1к — занятых кодов на уровне/-выбирается такой С/, что расстояние от С/ у до с, минимально
тіпВа
1-і-1.
В случае, если с, у — первый выдаваемый код во всем дереве, то количество блокируемых родительских кодов всегда равно Л/-/'-, где N — общее количество уровней в дереве. Нужно отметить, что на каждом уровне, большем, чем л, может быть заблокирован только один родительский код. Например, если количество блокируемых родительских кодов равно двум, то это означает, что один из двух кодов находится на уровне л + 1, а второй — на уровне л + 2.
На рис. 4 для кода сп занятыми родственниками натом же уровне являются коды с9 и с12. Ближайший общий родитель у кодов сл и с12 — ЭТО КОД С-,. Ближайший общий родитель у КОДОВ Си и Сд — это код с2. В качестве / выбираем уровень 3, так как код с2 ближе к коду с) 1(чем код Су По формуле (5) рассчитываем, что количество блокируемых родительских кодов при выдаче кода си, равно 1 — это код с5. Если бы код сэ был свободен, то в качестве / мы выбрали бы уровень 4, и тогда количество блокируемых кодов равнялось бы 2 — это коды с5 и с2.
усі л л л (У- ьмз & lt-рп" і. -ч О [і ,-1,-1 л]
Рис. 3. Пример блокировки дочерних кодов при выдаче кода на третьем уровне:
# - выделенные коды-
% - заблокированные коды-
О — свободные коды
Уровень 4
Уровень 3
Уровень 2
Уровень 1 К
¦ Рис. 4. Пример блокировки родительских кодов при выдаче кода на первом уровне: ф — выделенные коды- ф — заблокированные коды-
О — свободные коды
Определение количества блокируемых родительских кодов при выдаче кода Су можно описать следующим алгоритмом.
1. Если с, у — это первый выдаваемый код, то вазс = А/ - где N — общее количество уровней в дереве. Переход на шаг 5.
2. Отбросим все уровни, меньшие /, так, чтобы в полученном дереве код с, у оказался листом.
3. Понизим корень текущего дерева и рассмотрим одно из двух поддеревьев, в котором находится С, — у.
4. Есть ли хоть один занятый код на уровне / ?
4.1. Если истина и длина рассматриваемого поддерева равна 2, то Вазс = 0. Переход на шаг 5.
4.2. Если истина и длина рассматриваемого поддерева больше 2 — переход на шаг 3.
4.3. Если ложь, то Вазс = N -1, где N — длина рассматриваемого поддерева. Переход на шаг 5.
5. Конец.
При начальном условии, когда все К, равны нулю (т. е. ни один код не выдан), то количество блокируемых родительских кодов всегда фиксировано и равно N — /, где N — общее количество уровней в дереве- / -уровень выдаваемого кода. В случае, если хоть один /& lt-, не равен нулю, то количество блокируемых кодов в общем случае может быть от нуля до N — / -1. Элементы Вк, к & gt-/, увеличиваются на единицу у всех уровней из промежутка
N & lt- к & lt- /.
Так как количество блокируемых дочерних кодов всегда фиксировано, то максимальное количество возможных новых состояний (альтернатив для перехода), при вводе вектора В, при выдаче кода на уровне / равно Л/-/-1, в зависимости от раскладки уже занятых кодов на этом уровне.
Перестраивая граф состояний, получим дополнительные альтернативы перехода из состояния. Например, если дерево имеет четыре уровня и поступил запрос на код второго уровня, то до ввода вектора В была возможна только одна альтернатива, т. е. переход, после которого вектор состояний К имеет элемент К2 (на единицу больше). После ввода вектора В изменения вектора достаются теми же, но появляются три новых варианта.
1. Блокировка двух родительских кодов по одному на уровнях 3 и 4.
2. Блокировка одного родительского кода на уровне 3.
3. Ни один родительский код не блокируется.
Первый вариант возможен только в том случае,
если выдаваемый код — первый во всем дереве. Таким образом, количество альтернатив перехода такое же, как и до ввода вектора В. Если выдаваемый код — не первый, то появляется дополнительная альтернатива, т. е. в данном случае имеется два возможных варианта перехода вместо одного. По большому счету, количество имеющихся альтернатив определяет минимально возможное количество ко-дов-кандидатов для выдачи: если есть две альтер-//
нативы, то, как минимум, есть два подходящих кандидата для выдачи. Какой из вариантов будет выбран, зависит от используемого алгоритма выдачи кодов. Например, если используется случайный выбор (стратегия random), то вероятность переходов в обоих случаях равна 0,5, или, другими словами, данный алгоритм выбирает код из всех имеющихся кандидатов с равной вероятностью.
Таким образом, мы можем построить граф состояний, вероятности переходов у которого определены используемым алгоритмом распределения кодов, вероятностью запросов кодов различных характеристик, а также средней продолжительностью использования услуг абонентами. Далее, применяя к описанной системе известные формулы из теории массового обслуживания, можно получить характеристики системы, которые будут отражать работу того или иного алгоритма распределения кодов.
Заключение
В данной статье проведен обзор алгоритмов распределения каналообразующих кодов в стандарте WCDMA. Предложен вероятностный метод оценки алгоритма распределения кодов, который позволяет получить такие характеристики, как блокировка вызова, средняя пропускная способность при использовании того или иного алгоритма. Дальнейшие исследования будут направлены на получение графа состояний для конкретного OVSF-дерева, на применение к полученной системе формул и оценке имеющихся на текущий момент алгоритмов распределения кодов данным методом.
1. Legg P., Villier E. Efficient channelisation code allocation in UMTS 2001 (http: //www. priorartdatabase. com/IPCOM/ 4 839/).
2. TSG RAN WG1 Physical layer — General description Tech. Spec. TS25. 201, 3GPP, December 2003 (http: //www. 3gpp. org).
3. TSG RAN WG1 Spreading and modulation (FDD) Tech. Spec. TS25. 213, 3GPP, September 2003 (http: //www. 3gpp. org).
4. Yu C. W., Huang R. O. OVSF Code Management Schemes on Ad Hoc Networks ICC, 2004, Paris (http: //www. chu. edu. tw/ ~cwyu/pu blication. htm).
5. TSG RAN WG1 Radio resource management strategies Tech. Rep. TS25. 922,3GPP, December 2003(http: //www. 3gpp. org).
6. Tseng Yu-Chee, Chao Chih-Min Code Placement and Replacement Strategies for Wideband CDMA OVSF Code Tree Management IEEE Transactions on Mobile Computing 1(4): 293−302 (2002)
7. Chen Wen-Tsuen, Wu Ya-Ping, Hsiao Hung-Chang A Novel Code Assignment Scheme for W-CDMA Systems, Taiwan 300, R.O.C.
8. Dell’Amico M., Merani M. L., Maffio F. li A Tree Partitioning Dynamic Policy for OVSF Codes Assignment in Wideband CDMA, DISMI, DSI, DEI, Italy, March 2003.
9. Park Jun-Seong, Lee D. C. Enhanced Fixed and Dynamic Code Assignment Policies for OVSF-CDMA Systems, Los Angeles, CA 90 089, U.S. A.
10. Rouskas A. N., Skoutas D. N. Comparison of Code Reservation Schemes at the Forward Link in WCDMA, Samos 83 200, Greece.

ПоказатьСвернуть
Заполнить форму текущей работой