Книги, научные публикации

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ РАСПРЕДЕЛЕНИЕ КАНАЛЬНЫХ РЕСУРСОВ В СЕТЯХ КОГНИТИВНОГО РАДИО НА ОСНОВЕ ТЕОРИИ ИГР Д.В. Ошмарин, аспирант кафедры Теория Цепей и

Телекоммуникации Нижегородского государственного технического университета им. Р.Е. Алексеева, е-mail: dmitry.oshmarin

Адрес: г. Нижний Новгород, ул. Минина, д. 24, корп. 5.

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

Ключевые слова: когнитивное радио, теория игр, эффективное распределение спектра, потенциальные игры, беспроводные сети.

1. Введение ем своих собственных параметров (например, не сущей частоты, мощности, способа модуляции) в ак показывают современные исследования реальном времени с целью увеличения эффектив [1], использование спектра неодинаково ности использования спектрального ресурса [3].

Кэффективно по всему диапазону частот, до Теоретический и практический интерес представ ступному для беспроводных телекоммуникаций.

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

при котором достигается некое равновесное состо работа J. Mitola [2], посвященная когнитивному яние при распределении ресурсов в системе.

радио, рассматривает возможности увеличения В данной статье применяется метод распределе эффективности использования спектра за счет его ния каналов связи в сети приемопередающих пар, вторичного использования. Когнитивное радио - основанный на теории игр [4]. На основе модели это интеллектуальная беспроводная система связи, сети строится игровая модель, функции полезности способная анализировать окружающую обстановку в которой выбираются таким образом, чтобы игра и приспосабливаться к ней посредством обучения, реагируя на изменения в окружении изменени- сводилась к потенциальной [5].

БИЗНЕС-ИНФОРМАТИКА №4(14)Ц2010 г.

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ 2. Модель сети 3. Модель игры и алгоритм распределения канальных ресурсов Рассмотрим, представленную на рисунке 1, мо дель беспроводной сети, представляющую собой Игровая модель выбора канала связи в рассма совокупность приемников и передатчиков, обра- триваемой модели сети (1) может быть представле зующих пары. на в виде игры Г в нормальной форме (2):

={N,A,U}, (2) где N={i:i=1,n} Ч множество игроков;

A= Ai, i=1,n Ч пространство стратегий (действий), образованное декартовым произведением стратегий каждого игрока A={aj :j=1,m} ;

i U={Ui :i=1,n} Ч множество целевых функций, назы ваемых также функциями полезности (далее по тексту статьи будет использоваться термин лцеле вая функция).

Из (1) и (2) видно, что множество игроков Ч это Передатчик множество приемопередающих пар, пространство Приемник стратегий Ч это пространство всех возможных ком Рис. 1. Беспроводная сеть приемопередающих пар.

бинаций каналов связи, а множество целевых функ ций Ч это множество целевых функций приемопе В данной модели беспроводной сети все приемо редающих пар. Так же примем, что время дискретно передающие пары находятся в одном кластере, что k и бесконечно, т. е. T={t0,t1,...,t,...}, и, что каждый означает возможность обмена информацией без игрок будет играть стратегию, которая является наи использования маршрутизации. Другими словами, лучшим откликом на стратегии, играемые другими передача информации от передатчика к приемнику игроками. Далее примем, что понятия приемопе осуществляется непосредственно между ними без редающая пара и лигрок являются взаимозаменяе использования каких-либо промежуточных узлов мыми понятиями.

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

сети при любых условиях. Кроме того, в сети может nn использоваться определенное количество каналов Ui (ai,a )= pk gki f(ak,ai ) + pi gik f(ai,ak ) i (3) k=1,k i k=1,k i связи для передачи информации от передатчика к приемнику. При этом каждая приемопередающая где ai Ч стратегия, играемая игроком i, или, ины пара может использовать не более одного канала ми словами, выбор канала связи приемопередаю связи.

щей парой i;

a Ч стратегии, играемые остальными -i Рассматриваемая модель сети может быть форма игроками, или, иными словами, каналы связи, вы лизована в виде (1):

бранные остальными приемопередающими парами кроме i;

pi Ч мощность i-ого передатчика;

gij Ч коэф M= N,A,U,d,T, (1) фициент передачи радиочастотного тракта между i-ым передатчиком и j-ым приемником;

f (ai,a ) - j где N={i:i=1,n} Ч множество приемопередаю функция, принимающая значение 1, если выбран щих пар;

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

ние множеств действий (выборов каналов связи) Как видно, целевая функция (3) представляет со A={aj : j=1,m}, где m Ч количество каналов связи;

i бой сумму уровня помех, создаваемых остальны Ч множество целевых функций при U={Ui : i=1,n} ми передатчиками на собственном приемнике, и емопередающих пар;

d={di : i=1,n} Ч множество уровня помех, создаваемых собственным передат правил принятия решений;

T= Ti,i=1,n Ч мно- чиком на остальных приемниках. Очевидно, что жество всех моментов времени, в которых может выбор будет сделан в пользу того канала связи ai, произойти обновления состояния любой приемо- для которого значение целевой функции (3) будет Ti={ti0, ti1,..., tik,...} минимально.

передающей пары, где.

БИЗНЕС-ИНФОРМАТИКА №4(14)Ц2010 г.

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Покажем, что игра (2) с целевой функцией (3) Достаточным условием существования строгой потен сходится к равновесному состоянию по Нэшу. циальной функции является выполнение равенства:

Для этого сведем рассматриваемую игру к потен 2U (a) 2Ui (a) j =, (4) циальной игре. Потенциальная игра Ч это игра в aiaj ajai нормальной форме, в которой существует, так на где a=(a1,...,ai,...,aj,...,an ) Ч набор стратегий или зываемая, потенциальная функция, V : A элемент множества A.

которая отражает любые односторонние изменения в целевой функции каждого из игроков [5]. В данной Проверим на выполнение равенства (4) рассма работе используется строгая потенциальная игра [5], триваемую целевую функцию (3). Так как она явля т. е. игра в которой существует такая потенциальная ется дискретной функцией дискретного аргумента, функция, что выполняется равенство то для ее дифференцирования необходимо аппрок симировать дифференциальный оператор в (4). Для Ui (bi,a ) Ui (ai,a )=Vi (bi,a ) Vi (ai,a ),i N,a A. i i i i i этого введем сетку таким образом, что ai = ai+i Ч изменение канала i-ой приемопередающей парой, j В [5] так же показано, что в потенциальной игре су а a = aj + j Ч изменение канала j-ой приемопере j ществует хотя бы одно равновесное состояние по Нэшу.

дающей парой. Тогда:

, (5) (6) (7) Таким образом, вычитая из (7) сумму (5) и (6), получим искомую аппроксимацию дифференциального оператора левой части соотношения (4):

jj ii Ui (ai,a,a ) -Ui (ai,aj,a ) -Ui (ai,a,a ) +Ui (ai,aj,a ) 2Ui (a) j ij ij j ij ij = aiaj i (8) j Следуя той же процедуре, получим выражение для аппроксимации дифференциального оператора пра вой части соотношения (4):

jj ii 2U (a) U (a,ai,a ) -U (a,ai,a ) -U (aj,ai,a ) +U (aj,ai,a ) j j j ji j j ji j ji j ji = (9) aj ai i j Расписав каждое из слагаемых в числителях (8) и (9), нетрудно получить результирующие выражения (10) и (11):

2Ui (a) jj ii i = (pj g f (a,ai ) + pi gij f (ai,a ) - pj g f (aj,ai ) ji j j ji aiaj i j (10) jj i - pi gij f (ai,aj ) - pj g f (a,ai ) - pi gij f (ai,a ) + pj g f (aj,ai ) + pi gij f (ai,aj )), ji j j ji 2U (a) j jj j ii = (pi gij f (ai,a ) + pj g f (a,ai ) - pi gij f (ai,a ) - (11) j ji j j ajai i j j ii - pj g f (a,ai ) - pi gij f (ai,aj ) - pj g f (aj,ai ) + pi gij f (ai,aj ) + pj g f (aj,ai )), ji j ji ji БИЗНЕС-ИНФОРМАТИКА №4(14)Ц2010 г.

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Сравнивая правые части (10) и (11), заключаем, образом, на основе целевой функции (3) вводится что они равны. следующая потенциальная функция:

Таким образом, условие (4) выполняется, и игра с целевой функцией вида (3) является строгой по- (12) тенциальной игрой.

Из определения потенциальной игры следует, что В [5] показано, что для точных потенциальных потенциальная функция отражает любое измене- игр должно выполняться соотношение:

ние в целевой функции при изменении стратегии 2U (a) 2Ui (a) 2V (a) любого игрока. В случае строгой потенциальной j (13) == игры изменение потенциальной функции в точ- aiaj ajai ajai ности совпадает с изменением целевой функции при изменении стратегии одного из игроков. При- Ранее было показано, что первая часть соотноше чем это утверждение справедливо для всех игроков, ния (13) выполняется для игры с целевой функцией участвующих в игре. Из этого следует, что потен- вида (3). Проверим, выполняется ли вторая часть циальная функция должна содержать в себе инфор- соотношения (13). Для этого необходимо найти мацию о целевых функциях всех игроков. Таким вторую производную потенциальной функции (12).

Как и ранее, аппроксимируя дифференциальный оператор для потенциальной функции, получим:

jj ii V (ai,a,a ) -V (ai,aj,a ) -V (a,a,a ) +V (ai,aj,a ) 2V (a) j ij ij i j ij ij. (14) = aiaj i j Расписав каждое из слагаемых в (14), получим:

2V (a) jj ii i = (pi gi j f (ai, a ) + p g f (a, ai ) - pi gi j f (ai, aj) j j ji j ai aj i j (15) jj i -p g f (aj, ai ) - pi gi j f (ai, a ) - p g f (a, ai) + pi gi j f (ai,a ) + p g f (a,ai)).

j ji j j ji j j j ji j Правые части выражений (10), (11) и (15) равны, что позволяет утверждать, что функция (12) является строгой потенциальной функцией для игры с целевой функцией вида (3). Рассмотрим далее другую воз можную целевую функцию рассматриваемой игры:

n pk gki f (ak,ai ) n pi gik f (ai,ak ) (16) k=1,k i Ui (ai,a ) =+ i pi gii k =1,k i pk gkk В отличие от функции (3) она представляет собой сумму инверсного отношения сигнал/помеха на соб ственном приемнике и инверсных отношений сигнал/помеха на остальных приемниках. Проверим вы полнение соотношения (4) для игры с целевыми функциями вида (16):

j j ii pj g f (a,ai ) + pj g f (aj,ai ) - pj g f (aj,ai ) - pj g f (a,ai ) 2Ui (a) ji j ji ji ji j = ( + ai aj i pi gii j (17) jj ii pi gij f (ai,aj ) + pi gij f (ai,a ) - pi gij f (ai,aj ) - pi gij f (ai,a ) j j + ), pj g jj jj i i 2U (a) pi gij f (ai,a ) + pi gij f (ai,aj ) - pi gij f (ai,a ) - pi gij f (ai,aj ) j j j = ( + aj ai i pj g j jj jj ii p g f (a,ai ) + pj g f (aj,ai ) - pj g f (a,ai ) - pj g f (aj,ai ) (18) j ji j ji ji j ji + ).

pi gii БИЗНЕС-ИНФОРМАТИКА №4(14)Ц2010 г.

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Поскольку правые части (17) и (18) равны, то игра с целевой функцией вида (16) является строгой по тенциальной игрой.

На основе потенциальной функции (12) введём потенциальную функцию для игры с целевой функ цией (16) в виде:

n pk gki f (ak,ai ) nn 1 pi gik f (ai,ak ) k =1,k i (19) V(a) =+ () 2 pi gii k =1,k i pk gkk l= Проверим выполнение соотношения (13) для игры с потенциальной функцией:

(20) В алгоритме стоит различать шаг и раунд игры.

Шаг игры - это одна адаптация приемопередающей Правые части выражений (17), (18) и (20) равны, пары;

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

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

пар, описываемых моделью (1).

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

связи среди приемопередающих пар, содержит исходное распределение 4. Экспериментальные каналов связи.

результаты Для имитационного моделирования рассматри ваемого алгоритма распределения канальных ре сурсов в сети приемопередающих пар на основе игровой модели с целевыми функциями (3) и (16) была разработана программа на языке MATLAB.

БИЗНЕС-ИНФОРМАТИКА №4(14)Ц2010 г.

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Моделирование проводилось при следующих зна- бранный в предыдущем раунде канал связи.

чениях параметров: На рисунке 2 представлены распределения кана количество приемопередающих пар n=30;

лов связи среди приемопередающих пар до, и после количество каналов связи m=4;

игры. Оси отражают расположение приемопереда приемопередающие пары распределены равно- ющих пар на плоскости, в то время как выбранные мерно на плоскости размером 400х400 м2;

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

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

ным;

Исходное распределение каналов связи и соот распределение каналов связи производится по- ветствующие отношение сигнал/помеха, получен средством игры с целевыми функциями (3) и (16);

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

400 350 300 250 200 150 100 50 0 50 100 150 200 250 300 350 50 100 150 200 250 300 350 400 50 100 150 200 250 300 350 Рис. 2. Исходное распределение каналов (слева);

результирующее распределение каналов в игре с целевой функцией (3) (в центре);

результирующее распределение каналов в игре с целевой функцией (16) (справа).

10 5 0. 0. - 0. - 0. - - 0. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 10 n n 0. 10 0. 5 0. 0 0. -5 - -10 -10 1 2 3 4 5 1 2 3 4 5 6 7 -15 -10 -5 0 5 10 15 n n SIR Рис. 3. Исходное отношение сигнал/помеха на каждом из приемников в сети (слева);

исходная гистограмма распределения количества приемников с соответствующим отношением сигнал/помеха (справа).

БИЗНЕС-ИНФОРМАТИКА №4(14)Ц2010 г.

SIR SIR n1/n SIR SIR МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ 8 0. 0. 0. - -1 0. 1 2 3 4 5 6 1 2 3 4 5 6 7 n n 0. 8 0. 0. -2 - 1 2 3 4 5 6 1 2 3 4 5 6 7 8 -15 -10 -5 0 5 10 15 n SIR n Рис. 4. Результирующее отношение сигнал/помеха в игре с целевой функцией (3) на каждом из приемников в сети (слева);

результирующая гистограмма распределения количества приемников с соответствующим отношением сигнал/помеха в игре с целевой функцией (3) (справа).

15 3 0. 10 0. 5 0. 0 -5 - 0. 1 2 3 4 5 6 7 1 2 3 4 5 6 n n 0. 0. 0. -2 -2 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 -15 -10 -5 0 5 10 15 n n SIR Рис. 5. Результирующее отношение сигнал/помеха в игре с целевой функцией (16) на каждом из приемников в сети (слева);

результирующая гистограмма распределения количества приемников с соответствующим отношением сигнал/помеха в игре с целевой функцией (16) (справа).

БИЗНЕС-ИНФОРМАТИКА №4(14)Ц2010 г.

SIR SIR n1/n SIR SIR SIR SIR n1/n SIR SIR МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ 0.02 0. 0. 0. 0. 0. 0. 0. 0.006 0 10 20 30 40 50 60 70 80 90 0 10 20 30 40 50 60 70 80 i i Рис. 6. Изменение потенциальной функции (12) в ходе игры (слева);

изменение потенциальной функции (19) в ходе игры (справа).

Результирующее распределение каналов связи и ляется одной адаптацией одной приемопередаю соответствующее отношение сигнал/помеха, а так щей пары, а один раунд - одной адаптацией всех же гистограмма распределения количества приемни- приемопередающих пар, то можно утверждать, для обеих функций полезности (3) и (16) в при ков с соответствующим отношением сигнал/помеха веденном примере игра сходится за 90 шагов или представлены на рисунке 4 для игры с целевой функ 3 раунда.

цией (3) и на рисунке 5 для игры с целевой функци ей (16). Исходы игр являются различными для игр с 5. Заключение разными целевыми функциями, но, сравнивая по лученные в результате моделирования гистограммы с Таким образом, в статье построена игровая мо исходной, можно сделать вывод, что как для игры с дель распределения каналов связи в сетях приемо функцией полезности (3), так и для игры с функцией передающих пар. На основе игровой модели пред полезности (16) гистограмма распределения количе ложен алгоритм распределения ресурсов в сети.

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

которых игра сводится к потенциальной игре с Наконец, на рисунке 6 представлены графики потенциальными функциями (12) и (19) соответ изменения потенциальных функций в зависимо- ственно. Так же приведены результаты моделиро сти от шага игры для игр с целевыми функциями вания распределения каналов связи при использо (3) и (16) соответственно. Так как шаг игры яв- вании рассматриваемого алгоритма.

Литература 1. Cabric, D. Implementation issues in spectrum sensing for cognitive radios / D. Cabric, S.M. Mishra, R.W.

Brodersen // Signals, Systems and Computers, 2004. Conference Record of the Thirty-Eighth Asilomar Conference. 2004. Vol. 1. P. 772-776.

2. Mitola, J. Cognitive radio for flexible mobile communications / J. Mitola // Mobile Multimedia Communications, 1999. (MoMuC С99) 1999 IEEE International Workshop. 1999. P. 3-10.

3. Haykin, S. Cognitive radio: brain-empowered wireless communications/S. Haykin//Selected Areas in Communications, IEEE Journal. 2005. Vol. 23. P. 201-202.

4. Оуэн, Г. Теория игр: пер. с англ. - М.: Издательство Мир, 1971, - 230 с.

5. Monderer, D. Potential games / D. Monderer, L.S. Shapley // Games and Economic Behavior. 1996. Vol. 14.

P. 124-143.

БИЗНЕС-ИНФОРМАТИКА №4(14)Ц2010 г.

V(a) V(a)    Книги, научные публикации