Радиочастотное планирование радиосети с исключением интерференции радиоволн

Демичев Максим Сергеевич Инженер-конструктор по защите информации, Акционерное общество «Научно-производственное предприятие «Радиосвязь» 660000, Россия, Красноярский край, г. Красноярск, ул. Красноярский Рабочий, 31 Demichev Maksim Sergeevich Design Engineer of Information Security, JSC Scientific Production Enterprise "Radiosviaz" 660000, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31 mdemichev@yandex.ru Другие публикации этого автора     Гаипов Константин Эдуардович кандидат технических наук доцент, Сибирский государственный университет науки и технологий им. академика М.Ф. Решетнёва 660000, Россия, Красноярский край, г. Красноярск, ул. Красноярский Рабочий, 31 Gaipov Konstantin Eduardovich PhD in Technical Science Docent, the department of Electronic Technology and Telecommunications, Reshetnev Siberian State University of Science and Technology 660000, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31 cyberjam@yandex.ru Другие публикации этого автора     Демичева Алёна Алексеевна студент, Сибирский государственный университет науки и технологий им. академика М.Ф. Решетнёва 660031, Россия, Красноярский край, г. Красноярск, ул. Красноярский Рабочий, 31 Demicheva Alena Alekseevna Student, the department of Security of Information Technologies, Reshetnev Siberian State University of Science and Technology 660031, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31 DemichevaAlena@yandex.ru Другие публикации этого автора

Нарожный Артём Игоревич студент, Сибирский государственный университет науки и технологий им. академика М.Ф. Решетнёва 660000, Россия, Красноярский край, г. Красноярск, ул. Красноярский Рабочий, 31 Narozhnyi Artem Igorevich Student, Department of Information Technology Security, Reshetnev Siberian State University of Science and Technology 660000, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31 artem_narozhnyi@mail.ru Другие публикации этого автора

Современные технологии беспроводной связи являются быстро развивающейся отраслью телекоммуникационной индустрии, все больше устройств поддерживают беспроводные интерфейсы различных стандартов, тем самым повышается плотность как мобильных так и стационарных беспроводных устройств. Первые методы частотного планирования в сотовых системах связи были основны на разделение всей сети радиодоступа на кластеры, а те в свою очередь на соты, в пределах кластера каждая сота имела свой частотный канал, такая структура предполагала, одинаковый размер каждой соты и одинаковое число сот в каждом кластере. Современные потребности в беспроводной связи не могут быть удовлетворены данным способом планирования, а зачастую вообще неподходят для таких сетй, которые работают в режиме Ad-hoc или в распределенном беспроводном режиме (WDS - Wireless Distribution System). В связи счем в статье предлагается универсальный алгоритм определения непересекающихся поворных частотных каналаов между парой взаимодействующих беспроводных устрой при ограничении на используемую общую полосу частот, особенностью данного алгоритма является то, что устройства с беспроводными интерфейсами могут быть распределены произвольно в пространстве, а каждый интерфейс может иметь произвольную мощьность излучения, данный алгоритм также может использоваться и при построении состовой систем, где планируется использовать повторное использование частот. Сегодня известно достаточно большое количество подходов к решению задачи распределения частотного канала [1-2, 5, 7-8, 10]. Однако многие из известных результатов, как показано в работе ^[9] не лишины недостатков.

Пусть радиосеть состоит из N узлов радиостанций (далее – РС) с координатами (X_i, Y_i), где i `in` ^[1;N], каждая РС _i имеет антенну с круговой диаграммой направленности, c радиусом R _i, необходимо определить частотную полосу `gradF_(i)` , где i `in` ^[1;N] для каждой PC с учетом повтора частотного диапазона, при условии, что общий выделяемый диапазон частот располагается от F_n до F_v , где разница F_v и F_n, и составляет `gradF`. ^[6]

Решение задачи выполняется в следующей последовательности:

1. Алгоритм заполнения матрицы приема-передачи (матрица А).
2. Алгоритм разбиения матрицы А.
3. Алгоритм заполнения матрицы В (матриц B_j).
4. Алгоритм поиска одночастотных РС по матрице В(матриц B_j).
5. Алгоритм равномерного распределения частот для групп одночастотных РС.
6. Алгоритм расширения частотного диапазона индивидуально для каждой РС.

Для наглядного выполнения алгоритмов параллельно будем рассматривать пример. Пусть имеются координаты РС, круговая диаграмма направленности и дальность распространения радиоволн каждой РС, в результате, которого получим топологию радиосети, изображенной на Рис. 1, цифры обозначают номер РС, окружность, соответствующего цвета, показывает радиус действия радиостации. В каччестве радиостаций могут выступать беспроводные Mesh узлы или базовые станции сотовой системы связи. Необходимо провести частотное планирование радиосети, если выделенный диапазон частот `gradF` = 100 МГц, где F_v= 200 МГц и F_n = 100 МГц и полоса защиты P = 0.1 МГц.

Рис. 1. Топология радиостанций

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

L_ij = ` ` , расстояние от РС_i к РС_jбудем обозначать L _ij.

Составим матрицу приема-передачи (далее – матрица А) размера N x N, N - число РС, где главная диагональ равна нулю, номер строки является номером передающей РС, а номер столбца является номер принимающей РС. Сравниваем L_ij c R_i, где R_i – радиус распространения радио волн i-ой РС, если R_i ` ` L_ij, то в матрице А ставим единицу, иначе ноль.

Пример. Составим матрицу А, опираясь на топологию из Рис.1. РС будем обозначать как Rm, где m - номер РС.

Таблица 1. Матрица А

Блок схема алгоритма заполнения матрицы приема-передачи представлена на Рис. 2. Пояснения для блок схемы ниже Рис. 2.

Рис. 2. Блок схема алгоритма заполнения матрицы приема-передачи

Пояснение элементов изображенных на Рис. 2:

• pow(a,b) - функция языка С++, описывающая возведение числа а в степень b.
• sqrt(а) - функция языка С++, описывающая подсчет квадратного корня числа а.
• N - количество РС.
• X[i], Y[i] - координаты (X;Y) для i-ой РС.
• А[i][j] - матрица А, где i - номер передающей РС, j - номер принимающей РС

Алгоритм рекомендован для разбиения исходной задачи на несколько задач, например на Рис. 1 видно что, возможно выделить три радиосети, где первая сеть состоит из РС: R1, R3, R5, R6, R7, R9, R11, R12, R13, R14, R15; вторая сеть состоит из: R2, R8, R10; третья сеть состоит из: R4. В результате задачу примера можно разделить на три задачи, таким образом данный алгоритм позволяет выделить из матрицы А независимые топологии радиосети и получить матрицы A_j, где j`in`^{[1; H]}, H – количество полученных задач, при разбиении матрицы А. Алгоритм разбиения:

1. Выделим строку и столбец i-ой РС в матрице А (с наибольшей суммой элементов по строке i);
2. В выделенной строке находим единичные элементы и выделяем столбцы с соответствующими номерами РС и строки с теми же номерами РС;
3. В выделенных столбцах находим единичные элементы и выделяем строки с соответствующими номерами РС и столбцы с теми же номерами РС;
4. Повторить с п. 2 до тех пор, пока возможно выделять новые элементы, иначе переходим на п. 5;
5. Составляем матрицу А_j из элементов, выделенные в матрице A;
6. Если в матрице A остались невыделенные элементы, то необходимо повторить с п. 1, где поиск следующих матриц А_j, осуществляется по невыделенным элементам матрицы А;
7. Выполняем алгоритм пока не будут выделены все элементы матрицы A.

Пример. Из п. 1 вышеописанного алгоритма, выделим строку и столбец R15. Из п. 2, выделим строки и столбцы R5, R6, R9, R12 и R14, переходим в п. 3. В соответвтвии которого, выделим строку и столбец R3 и R11, переходим в п. 4. Исходя из п. 4 видим, что на пересечении строки R11 и столбца R1, находится единица, следовательно, переходим в п. 2. Из п. 2, выделим строку и столбец R1. Из п. 3, выделим строку и столбец R13. Результат представлен в таблице 2.

Таблица 2. Матрица А с выделенными РС первой подзадачи

Исходя из п. 4 видим, что на пересечении строки R7 и столбца R1, находится единица, следовательно, переходим в п. 2. Из п. 2, выделим строку и столбец R7 переходим в п.3. Из п. 3, невозможно выделить строки и столбцы, переходим в п. 4. Исходя из п. 4 видим, что невозможно дальнейшее выделение, следовательно, переходим в п. 5. Результатом п. 5 будет являться матрица А₁, представленная в таблице 3. В таблице 4 представлены невыделенные РС матрицы А, по которой будет произведен дальнейший поиск матриц А_j. Дальнейшее выполнение алгоритма поиска приведет к получению матрицы А₂ иматрицы А₃, представленные в таблицах 5 и 6 соответственно.

Таблица 3. Матрица А₁

Таблица 4. Матрица А с исключением РС первой подзадачи

Таблица 5. Матрица А₂

Таблица 6. Матрица А₃

Блок схема алгоритма разбиения матрицы А представлена на Рис. 3. Пояснения для блок схемы ниже Рис. 3.

Рис. 3. Блок схема алгоритма разбиения матрицы А

Пояснение элементов изображенных на Рис. 3:

• X, T - вспомогательные переменные.
• А_к[i] - полученная матрица независимой топологии радиосети, где k`in` ^{[1; H]}, H -количество подзадач.
• Buf[i] - вспомогательный массив, содержащий номера РС, входящих в А_к[i].

Матрица В показывает могут ли РС находиться на одной и той же частоте одна РС по отношению к другой РС, если элемент b_ij равен единице, то РС могут находиться на одной и той же частоте, если элемент b_ij равен нулю – не могут.

Выполнение алгоритма заполнения для матрицы В и матриц В_j одинаково, за исключением, того что для матрицы В алгоритм строится из матрицы А, а для и матриц В_j - из матриц А_j, при наличии разбиения матрицы А. В матрице В, удаляются строки и столбцы, которые в сумме дают ноль, удаленные РС заносятся в отдельные группы одночастотных РС. Алгоритм заполнения матрицы В (матрицы В_j):

1. Выделяем строку и столбец i-ой РС в матрице А.
2. Рассматриваем элементы выделенной i-ой строки, если элемент равен единице, то выделяем данный столбец, а также строку с тем же номером РС.
3. Рассмотрим каждый выделенный столбец, если элемент выделенного столбца равен единице, то выделяем данную строку, а также столбец с тем же номером РС.
4. Записываем в i-ый столбец k-ой строки матрицы В единицу, если строка k-ой РС, не выделена в матрице А, записываем ноль, если строка k-ой РС выделена в матрице А, данный пункт выполняем пока не пройдём по всему столбцу i в матрице А.
5. Снимаем все выделения в матрице А. Если в матрице В есть незаполненные столбцы, то переходим в п. 1, где i будет являться номером следующей РС.

В случае наличия матриц А_j произвести вышеописанный алгоритм, для каждой матрицы А_j, где в результате на каждую матриц А_j получится своя матрица В_j.

Пример. Рассмотрим пример заполнения одной РС матрицы В₁ из матрицы А₁ (таблица 5). Рассмотрим заполнение R12. Из п.1 вышеописанного алгоритма, выделим строку и столбец R12 в матрице А₁, переходим в п. 2. Исходя из п. 2 выделим столбцы R6, R9 и R15 и одноименные строки R6, R9 и R15, переходим в п. 3. В соответствии с п. 3 выделим строки R5 и R14 и одноименные столбцы R5 и R14, результат представлен в таблице 7.

Таблица 7. Матрица А₁ с выделенными РС для заполнения R12 матрицы В₁

Заполняем в матрице В₁, столбец R12, результат представлен в таблице 8.

Таблица 8. Заполненый столбец R12 матрицы В₁

Далее выполняем алгоритм для остальных РС в матрице В₁. Результат выполнения алгоритма для матрицы В₁ представлен в таблице 9, для матрицы В₂ – в таблице 10, для матрицы В₃ – в таблице 11.

Таблица 9. Матрица В₁

Таблица 10. Матрица В₂

Таблица 11. Матрица В₃

Под одночастотными РС, понимаются РС, которым будет выделена одна и та же полоса частот. Поиск одночастотных РС из матрицы B и матрицы В_j одинаков. Алгоритм поиска одночастотных РС:

1. Выделим строку с минимальной построчной суммой (строка W), не равной нулю, если таких строк несколько выделяем любую, в случае если построчная сумма равна нулю, значит РС данной строки уже входит в группу одночастотных РС;
2. На строке W находим единичные элементы b_wn, где w – номер строки W, n – номера столбцов, выделяем столбцы n, а также строки n;
3. Рассмотрим пересечения каждой строки n с выделенными столбцами n из п. 2. Находим наибольшую сумму в рассматриваемых пересечениях для каждой строки n, выбираем ту, которая имеет максимальную сумму, если таких строк несколько, то выбираем ту, которая имеет наименьшую построчную сумму по всей строке матрицы В, иначе выбираем любую из рассматриваемых с максимальной суммой, получим выбранную строку M;
4. В номер передающей РС строки W дописываем номер выбранной строки M, получим строку WM. Перемножаем поэлементно строку W и строку M, результат записывается в строку WM;
5. Удаляем строку M , столбец M, и столбец W из матрицы;
6. Если в строке WM построчная сумма равна нулю, то номер строки будет являться группой одночастотных РС;
7. Выполняем с п. 1 с учетом новой полученной строки, до тех пор пока сумма элементов каждой строки в матрице В, не будет равна нулю или останется только столбец с номерами строк.

Пример. Рассмотрим матрицу В₁. Из п.1 вышеописанного алгоритма, выделим минимальную построчную сумму в матрице В₁ – строка R15. Далее в соответствии п. 2 выделим строки R1, R7 и R13 и столбцы с тем же номером, результат представлен в таблице 12.

Таблица 12. Выделенные РС алгоритма п. 1 - п. 2 в матрице В₁

Посчитаем сумму значений элементов пересечения строки R1 со строками R1, R7, R13, строки R7 со строками R1, R7, R13 и строки R13 со строками R1, R7, R13. Полученные суммы каждой строки равны между собой, значит, выбираем ту строку, которая имеет наименьшую построчную сумму в матрице В₁, в нашем случае это R1 и R7, выбираем произвольно, выберем R1. В строку R15 дописываем R1. Элементы строк перемножаем, результат перемножения записываем в строку R1-R15. Далее удаляем строку R1 и столбцы R1 и R15. Результат представлен в таблице 13.

Таблица 13. Матрица В₁ с сформированной группой одночастотных РС (R1-R15)

Так как строка R1-R15 имеет построчную сумму равную нулю, следовательно, РС R1 и R15 будут входить в отдельную группу одночастотных РС, дальнейшее выполнение алгоритма будем осуществлять по оставшимся РС. Результат выполнения алгоритма представлен в таблице 14 для матрицы В₁.

Таблица 14. Результат выполнения алгоритма для матрицы В₁

Таблица 15. Результат выполнения алгоритма для матрицы В₂

Таблица 16. Результат выполнения алгоритма для матрицы В₃

В столбце «номер передающей РС» таблицы 14, представлены группы одночастотных РС. Результат выполнения алгоритма для В₂ представлен в таблице 15. Результат выполнения алгоритма для В₃ представлен в таблице 16. Группы одночастотных РС записаны в «номер передающей РС» для матрицы В₂ и матрицы В₃ в таблице 15 и таблице 16 соответственно.

Блок схема алгоритма одночастотных РС по матрице В (матрицам Вj) представлена на Рис. 5. Пояснения для блок схемы ниже Рис. 5.

Рис. 5. Блок схема алгоритма одночастотных РС по матрице В (матрицам Вj)

Пояснение элементов изображенных на Рис. 5:

• W, T, Q, Z - вспомогательные переменные.
• Buf^[0][i] - искомые позиции по строке i матрицы В.
• Buf^[1][i] - сумма строки i в матрице В.
• Buf^[2][i] - сумма в искомых позициях строки i матрицы В.
• Group_Freq[i][j] - матрица, содержащая номера РС j, входящих в группу одночастотных РС под номеров i.
• Amount[i]^[0] - строка содержащая количество РС, входящих в группу одночастотных РС под номером i.

`gradF`делим на количество групп одночастотных РС, далее распределение полосы частот выполняется:

Пронумеруем группы одночастотных РС = f _i , где i ^{[0; k – 1]} Рассчитаем k -1 полос частот, используем: `F_(i) = [F_(n) + (gradF)/(k) * i; F_(n) +(gradF)/(k) * (i+1) - p] ` , где k – число групп одночастотных РС, p – полоса защиты.

Для расчета полосы частот группы одночастотных РС f_k, используем: `F_(k) = [F_(n) + (gradF)/(k) * (k-1); F_(v)]`, где k – число групп одночастотных РС, p – полоса защиты.

В случае наличия матриц А_j выполняем алгоритм для каждой матрицы А_j.

Пример. Для матрицы А₁, для начала каждую группу одночастотных РС пронумеруем:

f₀ = R5, R6, R7

f₁ = R9, R13, R14

f₂ = R1, R15

f₃ = R3, R12

f₄ = R11

Из условия примера знаем F_{ниж = 100 МГц, Fверх} = 200 МГц. Рассчитаем частотную полосу для f₀, по п. 1 из вышеописанного алгоритма:

`F_(0) = [100 + (100)/(5) * 0; 100 + (100)/(5) * (0+1) - 0.1] ` , по итогу получим f₀ = ^[100;119.9]. Подобным образом будем рассчитывать до f₃ включительно.

Расчет частотной полосы для f₄, по п. 2 из вышеописанного алгоритма:

`F_(4) = [100 + (100)/(5) * (5-1); 200]` по итогу получим f₄ = ^[180;200].

Результат выполнения алгоритма равномерного распределения частот для групп одночастотных РС:

f₀ = ^[100;119.9] МГц f₁ = ^[120;139.9] МГц f₂ = ^[140;159.9] МГц

f₃ = ^[160;179.9] МГц f₄ = ^[180;200] МГц

Для матрицы А₂ получим результат:

f₀ = R2 f₀ = ^[100;133.2] МГц

f₁ = R8 f₁ = ^{[133.3;166.5]} МГц

f₂ = R10 f₂ = R2 ^[166,6;200] МГц

Для матрицы А₃ получим результат:

f₀ = R4 f₀ = ^[100;200] МГц

Блок схема алгоритма равномерного распределения частот для групп одночастотных РС представлена на Рис. 6. Пояснения для блок схемы ниже Рис. 6.

Рис. 6. Блок схема алгоритма заполнения матрицы приема-передачи

Пояснение элементов изображенных на Рис. 6:

• M - количество полученных групп одночастотных РС.
• Freq[i]^[0] - нижняя граница группы одночастотных сигналов под номеров i.
• Freq[i]^[1] - верхняя граница группы одночастотных сигналов под номеров i.
• Fn - нижняя граница выделенного частотного диапазона.
• Fv - верхняя граница выделенного частотного диапазона.
• dF = Fv - Fn.
• p - полоса защиты.

Выполнение алгоритма осуществляется от изначально рассчитанной матрицы В или в случае разбиения матрицы А, от изначально рассчитанных матриц B_j. Выполнение одинаково как для матрицы B так и для матриц B_j. Алгоритм расширения частотного диапазона индивидуально для каждой РС:

1. В матрице В выбираем произвольно РС и выделяем ее строку.
2. В матрице В выделим столбцы каждой полученной группы одночастотных РС, разным цветом.
3. Рассматриваем пересечения выделенной строки и столбцов каждой полученной группы одночастотных РС, если все пересечения равны единице, то к частотному диапазону выбранной РС добавляется частотный диапазон данной группы одночастотных РС.
4. Повторяем п. 2 и п. 3 для всех оставшихся комбинаций.
5. Повторяем с п. 1 для всех оставшихся РС, не прошедших индивидуального расширения частотного диапазона, если таковые РС отсутствуют.

Пример. Рассмотрим пример для матрицы А₁, решение будет исходить из начальной матрицы В₁ (таблица 9). Выбираем произвольно строку, в соответствии с п. 1 вышеописанного алгоритма, пусть это будет R5. Выделим разными цветами полученные группы одночастотных РС, в соответствии с п. 2. Результат представлен в таблице 17.

Таблица 17. Матрица В₁ с выделенными группами одночастотных РС

В соответствии с п. 3 видим, что элементы пересечения строки R5 и столбцов зеленым цветом, равны единицы, это означает, что РС R5 имеет основную полосу частот ^[10;119.9] МГц и дополнительно выделенную полосу: ^[180;200] МГц.

Выполним алгоритм для остальных строк для таблицы 17, результат для матрицы А₁ представлен в таблице 18. Результат для матрицы A₂ и матрицы А₃ представлены в таблице 19 и таблице 20 соответственно.

Таблица 18. Основные и дополнительные полосы частот для матрицы А₁

Таблица 19. Основные и дополнительные полосы частот для матрицы А₂

Таблица 20. Основные и дополнительные полосы частот для матрицы А₃

Блок схема алгоритма расширения частотного диапазона индивидуально для каждой РС представлена на Рис. 7. Пояснения для блок схемы ниже Рис. 7.

Рис. 7. Блок схема алгоритма расширения частотного диапазона индивидуально для каждой РС

Пояснение элементов изображенных на Рис. 7:

• W, T - вспомогательные переменные.
• Individ_Freq[i][j] - матрица, содержащая для i-ой РС, диапазон частотного расширения, представленный как номера групп одночастотных сигналов записанные на i-ой строке.

Рассматриваемый пример был смоделирован в среде WiMAP-4G, результат модулирования радиосети представлен на Рис. 8.

Рис. 8. Результат моделирования радиосети

На Рис. 8 представлено изображение уровней сигналов, где синим цветом обозначен, наилучший сигнал, что говорит о правильном частотном распределении. При использовании РС дополнительных полос частот, представление результата моделирования, будет аналогичен Рис. 8.

В данной статье был разработан алгоритм распределения частотного диапазона, и справедливость алгоритма подтверждается моделью MESH-сети, созданной в среде WiMAP-4G.

Результатом работы алгоритма, также является то, что для каждой РС является выделение основной и дополнительной полосы частот, где дополнительная полоса частот это возможное или резервное частотное расширение для конкретной РС. К примеру, производительность в mesh-сетях стандарта IEEE 802.11 во многом зависит от используемого механизма распределения частотных каналов ^[2]. Если дополнительная полоса частот соседствует с основной полосой частот, то расширение основной полосы частот до границ дополнительной частоты, допустимо, тем самым увеличивая скорость передаваемой информации, при этом условие отсутствия эффекта интерференции будет удовлетворено. На основании представленных блок схем для каждого алгоритма, при самых худших условиях, общая сложность выполнение алгоритма равна `O(8*N^(3) + 2*N^(2) + 3*N)`. Стоит отметить, что выполнение алгоритма разбиения матрицы А, выполняет роль поиска независимых компонент графа, то есть упрощает решение общей задачи, разделяя сеть на более мелкие независимые сети, что приводит к уменьшению временных затрата на выполнение алгоитма.