Автоматика и телемеханика, № 2, 2019

О.Г. МЕЛЕНТЬЕВ, д-р техн. наук (melog.aes@gmail.com)

(Сибирский государственный университет телекоммуникаций и информатики,

Новосибирск),

Д.В. КЛЕЙКО, д-р философии (denis.kleyko@gmail.com)

(Технологический университет Лулео, Швеция, Лулео),

А.Г. ШАПИН, канд. техн. наук (alexshapin@gmail.com)

(Исследовательский центр Эрикссон, Швеция, Лулео)

ОЦЕНКА ПАРАМЕТРОВ РЕЗУЛЬТИРУЮЩЕГО

ЛОГИЧЕСКОГО КАНАЛА, ОБРАЗОВАННОГО

ПУТЕМ МИНИМИЗАЦИИ ПЕРЕКЛЮЧЕНИЯ КАНАЛОВ

Предложена методика расчета параметров результирующего дискрет-

ного канала для вторичных пользователей в системах когнитивного ра-

дио, образованного алгоритмом минимизации смен каналов. Доступность

слотов каналов описывается простой марковской цепью. Получены мате-

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

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

Ключевые слова: когнитивное радио, оппортунистический доступ, пер-

вичный пользователь, вторичный пользователь, логический канал, мар-

ковская цепь, агрегирование состояний.

DOI: 10.1134/S0005231019020065

1. Введение

Отрасль информационных технологий является одной из наиболее дина-

мично развивающихся как в мире, так и в России, что приводит к быстрому

увеличению потребностей частотных ресурсов. В то же время использование

уже задействованных частот не превышает 15 % [1, 2]. Одним из подходов

к решению проблемы эффективного использования частотных ресурсов яв-

ляется использование когнитивного радио [3, 4]. Системы когнитивного ра-

дио обычно предполагают наличие группы каналов, временные слоты кото-

рых синхронизированы и имеют одинаковую длительность t. Слоты каналов

предоставляются для передачи данных первичных (PU) и вторичных поль-

зователей (SU). В начале каждого слота SU определяет доступность пер-

вичных каналов и при наличии свободных ресурсов может передавать ин-

формацию [5]. В данной статье предполагается, что время определения до-

ступности слота мало и влияния на систему не имеет [6]. PU имеют высший

приоритет и получают при необходимости все слоты одного канала. Стати-

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

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

описан марковской цепью с двумя состояниями [7-9]. Как показывают ис-

следования [10], в большинстве случаев процессы активности PU являются

независимыми между собой.

101

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

налов можно организовать логический канал, динамически выделяя свобод-

ные слоты первичных каналов.

В [7, 11, 12] предложены алгоритмы построения логического канала, ис-

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

их классификация и получены количественные оценки эффективности их

применения с помощью имитационного моделирования. Сложность опера-

тивного принятия решения о целесообразности применения подобных алго-

ритмов в тех или иных условиях определяется отсутствием математических

моделей, связывающих параметры выделенного логического канала с пара-

метрами первичных каналов.

В данной статье предлагается аналитическая модель, позволяющая опера-

тивно принимать решение о достаточности ресурсов и качестве логического

канала для обслуживания требований SU, используя алгоритм с минимиза-

цией смен каналов А1-МСК [11]. Как показано в [11], данный алгоритм имеет

лучшие результаты по сравнению с алгоритмом, предложенным в [7].

2. Постановка задачи

Пусть имеется N первичных каналов PU, характер занятости слотов в

каждом из этих каналов задается марковской цепью с двумя состояниями и

известной матрицей переходных вероятностей:



 P111 P112



 P²¹¹

P²¹²



P¹ =^

P² =

,

P¹²¹

P¹²²

 P221 P2

...,



−1



 P11

PN-112



PN12



PN-1 =



,

P^N =



 PN-121 PN-122



 PN21

PN22



В использованных обозначениях верхний индекс соответствует порядко-

вому номеру канала. По аналогии с [13] P₁₁ соответствует состоянию паузы

активности PU, P₂₂ — состоянию активности, P₁₂ и P₂₁ — вероятности пере-

хода между состояниями соответственно.

Выбирая слоты первичных каналов в соответствии с алгоритмом, строит-

ся логический канал для SU. Логика принятия решения алгоритма А1-МСК

I к анал

II канал

N канал

Рис. 1. Пример работы алгоритма.

102

такова: если доступность последнего слота, выделенного логическому каналу,

не отличается от доступности слотов в других первичных каналах, то не ме-

няем текущий канал, в противном случае выбираем слот в одном из каналов

со свободными слотами. Пример работы алгоритма приведен на рис. 1.

Целью анализа является определение переходных вероятностей для логи-

ческого канала, полученного посредством алгоритма А1-МСК, т.е.



P^SU12



P^SU =P1



 PSU21 PSU22



3. Случай двух каналов

Логику работы алгоритма можно описать марковской цепью, включающей

в себя состояния системы и все возможные переходы между ними. Состояние

системы учитывает состояние текущего канала и одно из возможных сочета-

ний состояний других каналов. Например, обозначение G1|G2 означает, что

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

состоянии (G1), при этом второй канал также находится в доступном состоя-

нии (G2). Всего таких состояний восемь.

Данная цепь интересна тем, что переходные вероятности между ее со-

стояниями можно получить аналитически, используя лишь характеристики

первичных каналов. Переходные вероятности, описывающие данную цепь,

представлены в табл. 1.

Например, вероятность сохранения состояния G1|G2 на следующем шаге

равна произведению вероятностей сохранения доступных состояний слотов

первичных каналов P¹¹¹P²¹¹.

Ноль в табл. 1 означает отсутствие перехода между состояниями и соот-

ветственно нулевую вероятность подобного события.

Следующий этап включает в себя объединение состояний системы для

каждого из первичных каналов. Важно отметить, что, как правило, сумма

переходных вероятностей, выходящих из одного состояния после агрегации,

не будет равна единице, поэтому полученные вероятности должны быть нор-

Таблица 1. Переходные вероятности для случая двух каналов

Сост. G1|G2 G1|B2 B1|G2 B1|B2 G2|G1 G2|B1 B2|G1 B2|B1

G1|G2

P¹¹¹P²¹¹

P¹¹¹P²¹²

P¹¹²P²¹¹

P¹¹²P²¹²

G1|B2

P¹¹¹P²²¹

P¹¹¹P²²²

P¹¹²P²²¹

P¹¹²P²²²

B1|G2

P¹¹²P²¹¹

P¹²²P²¹¹

P¹²¹P²¹²

P¹²²P²¹²

B1|B2

P¹²¹P²¹²

P¹²¹P²²²

P¹²²P²²¹

P¹²²P²²²

G2|G1

P¹¹¹P²¹¹

P¹¹²P²¹¹

P¹¹¹P²¹²

P¹¹²P²¹²

G2|B1

P¹²¹P²¹¹

P¹²²P²¹¹

P¹²¹P²¹²

P¹²²P²¹²

B2|G1

P¹¹¹P²²¹

P¹¹¹P²²²

P¹¹²P²¹²

P¹¹²P²²²

B2|B1

P¹²¹P²²¹

P¹²²P²²¹

P¹²¹P²²²

P¹²²P²²²

103

мализованы относительно их суммы для каждого состояния. Для этого тре-

буется знание стационарных вероятностей состояний. Стационарные вероят-

ности можно получить как предельные значения при возведении матрицы

переходных вероятностей (табл. 1) в бесконечность; обозначим их как век-

тор f_i, i ∈ {1, . . . , 8}, номер состояния соответствует позиции в табл. 1.

Формально стационарные вероятности получаются путем решения систе-

мы линейных уравнений, где количество уравнений на единицу больше ко-

личества состояний в цепи (обозначено как δ) за счет дополнительного усло-

вия нормировки:

^∑f_i = 1. Остальные уравнения системы формируются для

каждого состояния с использованием матрицы переходных вероятностей:

∑m

f_i =

T_jif_j, где T - матрица, содержащая значения переходных веро-

j=1

ятностей из табл. 1.

Зная переходные и стационарные вероятности, элементы матрицы пере-

ходных вероятностей агрегированной цепи V рассчитаем следующим обра-

зом:

(

)

(

)

f₁

P¹

P²¹¹ + P¹¹¹P²¹²

+f₂

P¹¹¹P²²¹ + P¹¹¹P²

V₁₁ =

²² ;

f₁ + f₂

(

)

(

)

f₁

P¹¹²P²¹¹ + P¹¹²P²¹²

+f₂

P¹¹²P²²¹ + P¹¹²P²

V₁₂ =

²² ;

f₁ + f₂

(

)

(

)

f₄

P¹²¹P²¹² + P¹²¹P²

f₄

P¹²²P²²¹ + P¹²²P²

V₂₁ =

;

V₂₂ =

²² ;

f₃ + f₄

(

)

(

)

f₃

P¹¹²P²¹¹ + P¹²²P²

f₃

P¹²¹P²¹² + P¹²²P²

V₂₃ =

;

V₂₄ =

¹² ;

f₃ + f₄

(

)

(

)

f₅

P¹¹¹P²¹¹ + P¹¹²P²¹¹

+f₆

P¹²¹P²¹¹ + P¹²²P²

V₃₃ =

¹¹ ;

f₅ + f₆

(

)

(

)

f₅

P¹¹¹P²¹² + P¹¹²P²¹²

+f₆

P¹²¹P²¹² + P¹²²P²

V₃₄ =

¹² ;

f₅ + f₆

(

)

(

)

f₇

P¹¹¹P²²¹ + P¹¹¹P²

f₇

P¹¹²P²¹² + P¹¹²P²

V₄₁ =

;

V₄₂ =

²² ;

f₇ + f₈

(

)

(

)

f₈

P¹²¹P²²¹ + P¹²²P²

f₈

P¹²¹P²²² + P¹²²P²

V₄₃ =

;

V₄₄ =

²² .

f₇ + f₈

Остальные вероятности равны нулю. Граф системы после первой агрега-

ции приведен на рис. 2.

Стационарные вероятности, необходимые для второй агрегации, вычис-

ляются аналогично рассчитанному выше случаю и обозначаются как m_i,

i ∈ {1,...,4}.

Зная переходные и стационарные вероятности второй цепи, объединяем

все доступные состояния каналов в одно и все недоступные состояния — в дру-

гое. В результате получаем марковскую цепь с двумя состояниями (рис. 3).

104

Рис. 2. Граф системы после первой агрегации.

Рис. 3. Марковская цепь с двумя состояниями.

Результаты свертки второй цепи:

m₁V₁₁ + m₃V₄₄

P^SU

;

m₁ + m₃

m₁V₁₂ + m₃V₃₄

P^SU

;

m₁ + m₃

m₂ (V₂₁ + V₂₃) + m₄ (V₄₁ + V₄₃)

P^SU

;

M₂ + M₄

m₂ (V₂₂ + V₂₄) + m₄ (V₄₂ + V₄₄)

P^SU

m₂ + m₄

Результаты последних четырех выражений являются искомыми переход-

ными вероятностями, характеризующими результирующий логический ка-

нал. Аналогичный метод применялся в [13].

4. Методика расчета для случая N каналов

Рассмотрим общий случай, когда число каналов равно N. Число состояний

системы, приходящихся на один физический канал, — ψ = 2^N .

Общее число состояний системы (δ) определится всеми возможными со-

четаниями состояний каналов при условии, что каждый из них может быть

текущим, т.е. δ = Nψ = N2^N . Таким образом, канал, построенный по алго-

ритму А1-МСК для произвольного числа первичных каналов, будет иметь

105

степенную зависимость, что затрудняет его реализацию при большом чис-

ле каналов. В будущем планируется провести оптимизацию предложенной

модели для снижения вычислительной сложности.

Расположим вероятности в векторе таким образом, чтобы все состояния

одного текущего канала шли непрерывно. При этом сначала размещаются

состояния, когда текущий канал доступен для SU, затем — состояния, в ко-

торых текущий канал занят PU, т.е. недоступен.

При формировании матрицы состояний системы S для обозначения до-

ступности канала будем использовать 1, для недоступности — 2. Для примера

приведем транспонированную матрицу для случая трех первичных каналов.

Каждая строка описывает состояния соответствующего канала.

Первые восемь столбцов соответствуют первому текущему каналу, из них

с первого по четвертый столбцы текущий канал доступен, с пятого по вось-

мой — недоступен. Аналогично для двух других каналов. Здесь и далее S_ij

обозначает состояние j-го канала, когда SU пребывает в i-м состоянии систе-

мы.

Далее формируем матрицу переходных вероятностей T системы, отража-

ющую построение логического канала для SU. Переберем все состояния си-

стемы i ∈ {1, . . . , δ}.

Определим, какому текущему каналу принадлежит состояние системы c =⌈

⌉

Если текущий канал в доступном состоянии S_ic = 1 или все каналы недо-

ступны, то смены канала не происходит. Это значит, что переходы возможны

только между состояниями данного канала. Состояние текущего канала при-

надлежит диапазону j ∈ {(c - 1)ψ + 1, . . . , cψ}.

Таким образом, значения переходных вероятностей системы определятся

выражением

∏

T_ij =

P^k

j ∈ {(c - 1)ψ + 1,...,cψ}.

S_ikS_jk

k=1

В оставшихся случаях, когда есть хотя бы один доступный канал, но при

этом текущий канал находится в недоступном состоянии, формируем век-

тор λ, включающий в себя номера доступных каналов. Для всех элементов

в λ вычисляем переходные вероятности из текущего состояния i в другие

доступные состояния системы:

∏

T_ij =

P^k

S_ikS_jk

k=1

j ∈ {[(λ₁ - 1)ψ + 1,λ₁ψ],...,[(λ_n - 1)ψ + 1,λ_nψ]},n ∈ {1,...,|λ|}.

106

Вероятности вне диапазона равны нулю. После вычисления всех элементов

матрицы T необходимо провести нормализацию и вычислить вектор стацио-

нарных вероятностей состояний f.

Далее приступаем к первой агрегации. Агрегируем все ψ состояний каждо-

го канала до двух состояний, соответствующих доступному и недоступному

состояниям текущего канала. В результате δ состояний системы уменьшается

до 2N агрегированных.

Номер агрегированног⌈ сост⌉яния, в которое войдет текущее, можно опре-

делить выражением a =

. Тогда в агрегированное состояние a войдут

2N-1

состояния с номерами из диапазона j ∈ {(a - 1)2N-1, . . . , a2^N }.

Сумма стационарных вероятностей всех состояний, входящих в a-е агре-

гированное, определится выражением

∑

d(a) =

f_i.

i=(a-1)2N-1 +1

Перебирая все i = 1, . . . , ψ и все агрегированные состояния j = 1, . . . , 2N,

формируем матрицу переходных вероятностей системы после первой агрега-

ции V , размеров 2N × 2N:

∑

V_aj =

f_i

T_in.

d(a)

i=1

n=(j-1)2N-1+1

Полученная матрица соответствует требованиям нормировки, поэтому

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

состояний m.

Остается совершить второй этап агрегации. После первой агрегации пер-

вым является состояние доступности первого канала, третьим — доступности

второго. Второе и четвертое состояния являются состояниями недоступности

соответствующего канала. Вторая агрегация попарно объединяет доступные

и недоступные состояния. В результате получаем матрицу переходных веро-

ятностей результирующей марковской цепи с двумя состояниями. Для раз-

личия четных и нечетных состояний введем переменную: b = 2 - mod(i, 2),

которая возвращает значения 1 или 2.

Суммируем стационарные вероятности нечетных и четных состояний:

⎧

⎪

∑

⎪

m2n-1 — для нечетных b,

⎨

n=1

d(b) =

⎪

∑

⎪

⎩ m2n — для четных b,

n=1

107

Для каждого состояния первого шага агрегации i = 1, . . . , 2N модифици-

руем переходные вероятности выходной матрицы j = 1, 2:

⎧

⎪

∑ N∑

⎪

m_i Vi[2n-1] для j = 1,

⎨

d(b)

i=1

n=1

PSUbj =

⎪

∑ N∑

⎪

⎩

m_i Vi[2n] для j = 2.

d(b)

i=1

n=1

В результате преобразований получаем матрицу переходных вероятностей

марковской цепи с двумя состояниями (см. раздел 2), описывающую логи-

ческий канал, построенный алгоритмом с минимизацией смен каналов для

произвольного количества первичных физических каналов. Стоит отметить,

что процесс агрегации может осуществляться в один этап, однако это услож-

няет интуитивное понимание основной идеи предложенной математической

модели.

5. Имитационное моделирование

Для проверки корректности предложенной математической модели было

проведено имитационное моделирование, использующее результаты оценок

параметров занятости каналов PU для реальных систем связи, представлен-

ных в [14-16]. При моделировании генерировалось от одного до шести ка-

нальных массивов, представляющих первичные каналы. Количество слотов

в каждом канальном массиве 10000.

В табл. 2 приведены переходные вероятности и коэффициент доступности

первичных каналов, коэффициенты доступности результирующих каналов,

Таблица 2. Характеристики каналов, используемых в имитационном моделирова-

нии, и полученные результаты коэффициентов доступности

Переходные

вероятности

Коэффициент доступности

первичных каналов

Ссылка

Первичный Аналитическое Результат

P₁₁

P₂₂

на

канал

решение

моделирования

источник

0,99 0,99999

[15]

0,000999

0,2

0,7

[16]

0,272727

0,275928

0,273464

0,001232

0,95

0,96

[15]

0,444444

0,576558

0,556511

0,010024

0,98

0,97

[16]

0,6

0,817738

0,802608

0,007565

0,8

0,3

[14]

0,777778

0,89789

0,900176

0,001143

0,88

0,46

[14]

0,818182

0,920392

0,91575

0,002321

108

полученные путем имитационного моделирования и аналитически, и средне-

квадратическое отклонение (СКО). В ходе эксперимента количество первич-

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

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

шесть каналов не будут включены. Результаты, полученные аналитически

и методом имитационного моделирования, очень близки, что позволяет су-

дить о состоятельности предложенной математической модели расчета. Как

видно из табл. 2, доступность логического канала, построенного алгоритмом

А1-МСК, выше доступности любого первичного канала, используемого при

его построении. Данный результат подтверждает целесообразность примене-

ния алгоритма А1-МСК при выделении ресурсов для SU.

6. Заключение

В статье предложен новый математический подход для определения пе-

реходных вероятностей логического канала SU, построенного посредством

алгоритма А1-МСК, в системах когнитивного радио. Матрица переходных

вероятностей результирующего логического канала SU позволяет получить

количественные оценки многих вторичных параметров, например скорости

передачи [9], коэффициента доступности (или коэффициента потерь паке-

тов), среднего времени задержки [17] и т.д. Эти параметры дают возмож-

ность оперативно принимать решение о достаточности ресурсов и качестве

логического канала для обслуживания требований SU.

Авторы выражают благодарность Н.В. Лямину из Halmstad University за

его ценные замечания, существенно улучшившие качество данной статьи.

СПИСОК ЛИТЕРАТУРЫ

1. Ghosh G., Das P., Chatterjee S. Cognitive Radio and Dynamic Spectrum Access —

a Study // Int. J. Next-Generation Networks. 2014. V. 6. No. 1. P. 43-60.

2. McHenry M.A. NSF Spectrum Occupancy Measurements Project Summary //

Shared Spectrum Company Report, 2005.

3. Huang S., Liu X., Ding Z. Opportunistic Spectrum Access in Cognitive Radio

Networks // IEEE INFOCOM Conf. 2008. Phoenix, AZ, USA.

4. Senhua Huang, Xin Liu, Zhi Ding. On Optimal Control for Opportunistic Spectrum

Access of Cognitive Radio Networks // IEEE INFOCOM Conf. 2010. San Diego,

CA, USA.

5. Ferrari L., Qing Zhao, Scaglione A. Utility Maximizing Sequential Sensing Over a

Finite Horizon // IEEE Trans. Signal Process. 2017. V. 65 No. 13. P. 3430-3445.

6. Bowen Li, Panlong Yang, Jinlong Wang, Qihui Wu, Shaojie Tang, Xiang-Yang Li,

Yunhao Liu. Almost Optimal Dynamically-Ordered Channel Sensing and Accessing

for Cognitive Networks // IEEE Trans. Mobile Computing. 2014. V. 13. No. 10.

P. 2215-2228.

7. Qing Zhao, Bhaskar Krishnamachari, Keqin Liu. On Myopic Sensing for Multi-

Channel Opportunistic Access: Structure, Optimality, and Performance // IEEE

Wireless Commun. 2008. V. 7. No. 12. P. 5431-5440.

8. Hueda M.R., Rodriguez C.E. On the Relationship Between the Block Error and

Channel-State Markov Models in Transmissions Over Slow-Fading Channels // IEEE

Trans. Commun. 2004. V. 52. No. 8. P. 1269-1275.

109

Shibing Zhang, Huijian Wang, Xiaoge Zhang. Estimation of Channel State Transition

Probabilities Based on Markov Chains in Cognitive Radio // J. Commun. 2014. V. 9.

No. 6. P. 468-474.

10.

Thakur P., Kumar A., Pandit S., Singh G., Satashia S.N. Performance Analysis

of Cognitive Radio Networks Using Channel-Prediction-Probabilities and Improved

Frame Structure // Digital Commun. and Networks. 2018. V. 1. No. 8. P. 1-9.

11.

Мелентьев О.Г., Шевнина И.Е. Сравнение алгоритмов выбора логического ка-

нала, с учетом приоритетов // Электросвязь. 2010. № 2. С. 50-52.

12.

Yuan Zhao, Luyi Bail. Performance Analysis and Optimization for Cognitive Radio

Networks with Classified Secondary // Mobile Inform. Syst. 2017. No. 3613496.

P. 1-8.

13.

Мелентьев О.Г., Клейко Д.В. Расчет параметров результирующего дискретно-

го канала, образованного хоппингом, для общего случая // АиТ. 2013. № 7.

С. 84-88.

Melent’ev O.G., Kleiko D.V. Computing the Parameters of the Discrete Channel

Resulting under Frequency Hopping in the General Case // Autom. Remote Control.

2013. V. 7. No. 7. P. 1128-1131.

14.

László Csurgai-Horváth, János Bitó. Primary and Secondary User Activity Models

for Cognitive Wireless Network // IEEE 11th Int. Conf. Telecomm. 2011. Graz,

Austria.

15.

Barnes S.D., Maharaj B.T. Performance of a Hidden Markov Channel Occupancy

Model for Cognitive Radio // IEEE Africon Conf. 2011. Livingstone, Zambia.

16.

Мелентьев О.Г., Клейко Д.В. Оценка параметров логических каналов для вто-

ричных абонентов // Науч. вестн. НГТУ. 2012. № 4. С. 56-62.

17.

Jinbei Zhangy, Yixuan Liy, Zhuotao Liuy, Fan Wuz, Feng Yangy, Xinbing Wang. On

Multicast Capacity and Delay in Cognitive Radio Mobile Ad-hoc Networks // IEEE

Trans. Wireless Commun. 2015. V. 14. No. 10. P. 5274-5286.

Статья представлена к публикации членом редколлегии А.И. Ляховым.

Поступила в редакцию 18.12.2018

После доработки 27.07.2018

Принята к публикации 08.11.2018

110