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

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

К основным задачам в беспроводных сетях относится оптимизация распределения ограниченного числа радио ресурсов между пользователями. Различные типы пакетного трафика, передаваемого по сети, предполагают динамическое выделение ресурсов пользователям. Решением задач планирования ресурсов, назначения приоритетов доступа в зависимости от типов трафика с заданными требованиями к качеству обслуживания занимаются модули управления радио ресурсами, называемые планировщиками (schedulers). Планировщики, в свою очередь, разра-батываются на базе алгоритмов, получаемых в результате решения различного рода задач оптимизации радио ресурсов. Известные на сегодняшний день задачи межуровневой оптимизации, например, задача минимизации мощности или задача максимизации скорости передачи, фактически подразумевают оптимизацию некоторой функции полезности (Utility Function), описывающей тот или иной уровень удовлетворенности пользователей для опреде-ленной схемы распределения радио ресурсов при некоторых ограничениях. В статье исследованы два алгоритма межуровневой оптимизации, предназначенных для максимизации функции полезности в различных условиях - алгоритм динамического назначения поднесущих DSA (Dynamic Subcarrier Assignment) и алгоритм адаптивного распределения мощности APA (Adaptive Power Allocation). Для рассматриваемых алгоритмов сформулированы задачи максимизации функции полезности, и, для которых получены условия оптимальности их решения.

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

Бутурлин ИА,

аспирант кафедры систем телекоммуникаций РУДН, ivan_butuiiin@mail.iv

Гайдамака Ю.В.,

к. ф.-м. н.,

доцент кафедры систем телекоммуникаций РУДН, ygaidamaka@mail.ru

Самуйлов А.К.,

студент магистратуры кафедры систем телекоммуникаций РУДН, asam 1988@gmail.com

Введение

Распределение и управление радио ресурсами в беспроводных сетях связи с мультиплексированием с разделением по ортогональным частотам OFDM (Orthogonal Frequency-Division Multiplexing) имеют решающие значение в связи с ограниченным спектральным ресурсом, который распределяется между большим количеством пользователей различных мультимедийных услуг. Одним из эффективных методов управления функционированием сетей OFDM является межуровневая оптимизация, поддерживающая связь между уровнями сетевой архитектуры. Вследствие того, что уровни модели функционируют независимо друг от друга, может возникать проблема неэффективного использования ресурсов. Для оптимального распределения радио ресурсов и эффективного планирования пакетной передачи данных принято использовать межуровнсвую оптимизацию для связи физического уровня, отвечающего за передачу данных, и уровня управления доступа к среде передачи

данных (MAC, Media Access Control), посредствам которого организуется многопользовательский доступ к распределенным радио ресурсам.

В соте сети OFDM доступная спектральная емкость разделена на множество ортогональных поднесущих, что позволяет обеспечивать высокую скорость передачи данных в условиях большой загрузки и учитывать замирание сигнала при распределении радио ресурсов [I]. Для достижения наиболее эффективного варианта распределения поднесущих между пользователями необходимо учитывать множество факторов, например, меж-символьная интерференция, частотные замирания и ограниченный спектральный ресурс. Таким образом, для предотвращения межсимвольной интерференции и обеспечения наибольшей производительности планировщик должен динамически распределять доступные поднесущие между пользователями, изменяя при этом мощность передачи сигнала, исходя из текущих характеристик радиоканалов (CSI, Channel State Information).

В статье на базе результатов [5, 6] исследованы две задачи межуровневой оптимизации для организации нисходящего канала соты сети OFDM. Рассматриваются алгоритмы динамического назначения поднесущих DSA и адаптивного распределения мощности АРА. Для обеспечения справедливого и эффективного распределения ресурсов и организации связи между уровнями сетевой архитектуры предлагается использовать функцию полезности. Понятие функции полезности детально исследовано в экономической теории, где оно применяется для количественной оценки выгоды от использования некоторых ресурсов [2]. В статье под ресурсами понимаются распределенные между пользователями поднесущие (алгоритм DSA) и выделяемая для этих поднесущих мощность (алгоритм DSA).

Работа выполнена при поддержке РФФИ (грант 10-07-00487-а) и Рособразования (проект 020619-1-174).

1. Построение модели нисходящего канала

Рассматривается отдельная сота сети OFDM, обслуживающая пользователей из множества .я =\\,2.......А'},

которым доступно множество поднесущих / =, 1,2.....Л'}

Пусть суммарная доступная пропускная способность соты составляет В [Гц] и обозначим Р общую доступную мощность передачи. Тогда ширина полосы пропускания каждой поднесущей пе .1 (п -поднесущей) эк-

D

вивалентна величине д/• = __. Таким образом, рассмат-

N

ривается дискретный случай функционирования соты.

В соте сети OFDM характеристики устанавливаемого нисходящего канала для разных пользователей независимы друг от друга. Для части пользователей может наблюдаться снижение показателей качества обслуживания вследствие эффекта частотного замирания канала. Для учета физических характеристик канала в [5] была рассмотрена модель многопользовательских частотноселективных каналов с замираниями. Состояние каждого пользовательского канала может быть представлено в виде отношения сигнал-шум SNR

(«)Г „

рк(п) =--------— [Дб], где Нк(п) - частотная харак-

Nk

теристика и-поднесущей для к -пользователя, а Nк

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

Обозначим ск(п) [(бит/с)/Гц] достижимую эффективность передачи для к -пользователя на п -поднесущей для заданного коэффициента ошибок по битам BER (Bit-Error Rate) и некоторого вектора

р = (/?(«)) t распределения мощностей между под-

несущими. Достижимая эффективность передачи с\

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

c*(w) = log2 (\ + /Зр(п)рк(п)), ке .К ,

0 1,5

где о =------------- - константа, называемая запасом

-1п

по отношению сигнал-шум (SNR gap).

Введем хкп е {0,1} состояние и-поднесущей так,

что хкп = 1, если п -поднесущая назначена к -

пользователю, и хкп = 0, в противном случае. Тогда

\к =(хкп)пе , - вектор состояния поднесущих для к -

пользователя, причем условие X хкп = 1 означает, что

*Е.>Г

п -поднесущая может быть назначена только одному пользователю. Множество Dk(\k) = {п : хкп =1} включает все поднесущие, назначенные к -пользователю в состоянии \к, а набор множеств D(x) = (Dk(xk )j ;

определяет распределение поднесущих по всем пользователям, когда система находится в состоянии

х = (хк )ке л . Тогда множество состояний системы можно определить в виде:

./• = {х = (х: Dl(xl)f\Dj(Hj) = 0, i*je Л',

U Dk(xk) с. I хкп = 1, /?€./}.

*€./»' ke.JT

Введем множество всех возможных наборов поднесущих У = {D(x) :хе .У} и множество возможных вариантов распределения мощностей

./’ = < р :0< р(п)< Р, X р(п) = Р,пе . /1. Скорость

пе./ J

передачи данных гк [бит/с] для к -пользователя в состоянии \к, представима в виде: гк (х*.Р)= I cpk(n)Af хкп = I с-Г(/!)Д/ =

пе./ «60»

= ''*(D*(X*)'P):=/V(D*-P)’ ке * •

Пусть Uк (•) - функция полезности для к -

пользователя, к е Ж . Будем рассматривать в качестве основного блага для пользователя величину скорости передачи данных гк и определим функцию полезности в следующем виде: t/(r(c/,p)):= I Uk(rk(Dk,р)).

ке.#

Таким образом, задача межуровневой оптимизации в общем случае может быть сформулирована, как максимизация полезности соты сети OFDM в виде max £ Ut

с ограничениями d е Ч и ре./1.

Пусть вектор распределения мощностей фиксирован, т.е. р = р = const. Тогда функцию полезности для алгоритма динамического назначения поднесущих DSA можно определить в виде

u(r(d))^u(r(d,-p)).

В случае алгоритма адаптивного распределения мощностей АРА фиксированным является набор множеств поднесущих d = d = cons/, и, следовательно, функция полезности имеет вид: l/(r(p))f=t/(r(^.p))-

В [5,6] используется метод релаксаций [4], идея которого заключается в том, что при разработке метода решения задач отбрасывается требование к целочислен-ности переменных. В дальнейших рассуждениях мы также будем предполагать, что функции полезности Uк (i'k ) является неубывающей выпуклой и существует

ее производная U'k (/* ).

2. Алгоритм динамического назначения поднесущих DSA

Для увеличения производительности соты сети OFDM за счёт более эффективного использования радио ресурсов в [5,6] был предложен алгоритм динамического назначения поднесущих DSA, задача которого состоит в распределении множества поднесущих .1 по всем пользователям соты сети OFDM при условии фиксиро-

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

max U (г (с/)) с ограничением d е У .

Используя метод математической индукции можно

доказать, что максимум функции полезности £/

достигается в сформулированных ниже достаточных условиях оптимальности.

Утверждение 1: Если для набора d -(d\) ,

' * 'ке.*

ВЫПОЛНЯеТСЯ уСЛОВИе V'k(rk)cVk(n)>U'j(rj)cVj(n),

к * jе Ж,we 0‘, где г‘ _ ^ с-Р(и)ДГ > тогда функция

«о;

полезности и (r(d)) достигает глобального максимума «

на наборе d = d е У .

Из полученных условий оптимальности получаем правило назначения поднесущей пользователю. Для заданного вектора р = р распределения мощности номер пользователя, которому назначается п-поднесущая, определяется формулой jt(„) = aigmaxjt/;(r**)ci(n)}-

3. Алгоритм адаптивного распределения мощности АРА

Алгоритм адаптивного распределения мощности АРА, состоит в назначении каждой поднесущей пе . Г определенной мощности передачи при условии фиксированного набора d — d распределения поднесущих между пользователями.

Задача межуровневой оптимизации для алгоритма АРА может быть сформулирована в следующем виде: maxf/

Р

с ограничением ре.?-

Ниже сформулированы необходимые условия достижения максимума функцией полезности U (/‘(р)).

Утверждение 2: Если р (п) является решением

(1),(2), тогда

г____•. . э+

где Л > О - нормирующая константа оптимального распределения мощностей.

Из полученных условий оптимальности функции и (/'(р)) очевидным образом следует правило назначения мощностей поднесущих для алгоритма АРА.

Заключение

В статье исследована модель многопользовательских частотно-селективных каналов с замираниями соты сети OFDM и построена целевая функция полезности для задачи оптимального распределения поднесущих частот и мощностей между пользователями. Для алгоритмов динамического назначения поднесущих DSA и адаптивного распределения мощности АРА сформулированы частные задачи межуровневой оптимизации. Исследованы и сформулированы достаточное условие нахождения глобального максимума функции полезности для задачи DSA и необходимое условие для задачи АРА. В дальнейшем предполагается разработать алгоритмы решения предложенных оптимизационных задач и исследовать обобщенную задачу оптимизации для случая совместного применения алгоритмов DSA и АРА. В заключение авторы выражают благодарность заведующему кафедрой систем телекоммуникаций РУДН профессору К.Е. Самуйлову за плодотворные дискуссии при подготовке статьи.

Литература

1. Вишневским В.М., Портной С.Л., Шахнович И.В.

Энциклопедия WiMAX Путь к 4G. - М.: Техносфера, 2010. -472 с.

2. Нуреев P.M. Курс микроэкономики: Учебник для вузов. - М.: Издательство НОРМА, 2001. - 572 с.

3. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с анг. - М.: Мир, 1985.-509 с.

4. Глебов Н.И., Кочетов Ю.А., Плясунов А.В. Методы оптимизации: Учебное пособие. - Новосиб. ун-т. Новосибирск, 2000.-105 с.

5. Song G., Li (G.) Y. Cross-Layer Optimization for OFDM Wireless Networks - Part 1: Theoretical Framework // IEEE Transactions Wireless Communications - Mar. 2005. - Vol.4. - №2. -P.614-624.

6. Song G., Li (G.) Y. Cross-Layer Optimization for OFDM Wireless Networks - Part II: Algorithm Development // IEEE Transactions Wireless Communications - Mar. 2005. - Vol.4. -№2. - P.625-634.

UHlity function maximization problems for two cross-layer optimization algorithms in OFDM wireless networks Buturlin Ivan A., PhD student, Telecommunication Systems Department, Peoples' Friendship University of Russia, ivan_buturlin@mail.ru Gaidamaka Yuliya V., An associate professor, Telecommunication Systems Department, Peoples' Friendship University of Russia, ygaidamaka@mail.ru Samuylov Andrey K., Student, Telecommunication Systems Department, Peoples' Friendship University of Russia,asam1988@gmail.com

Abstract: One of the main problems in wireless networks is distribution optimization of a limited number of radio resources among users. Different types traffic transmitted over the network suggest a dynamic resource allocation in order to provide a better quality of service (QoS). There are radio resource management modules, called schedulers, that are engaged in resource planning and access priority assignment depending on the types of traffic with the specified requirements for QoS. Schedulers are developed based on algorithms derived from solving various radio resources optimization problems. Known today cross-layer optimization problems, for example, the problem of minimiz'ng the transmission power or the problem of maximiz'ng the transmission rate, in fact, involve the optimization of a utility function, that describe a certain level of user satisfaction for a particular resources allocation scheme under certain restrictions. In this paper, we study two cross-layer optimization algorithms that are intended to maxmize the utility function under different conditions - dynamic subcarrier assignment (DSA) algorithm and adaptive power allocation (APA) algorithm.

Keywords: OFDM, cross-layer optimization, utility function, efficient frequency allocation.