Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

Radio frequency planning in the radio network involving exclusion of the radio wave interference.

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
Other publications by this author
 

 
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
Other publications by this author
 

 
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
Other publications by this author
 

 
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
Other publications by this author
 

 

DOI:

10.25136/2644-5522.2017.4.23786

Received:

04-08-2017


Published:

23-08-2017


Abstract: The object of study involves radio frequency planning when designing a radio network.  The frequency allocation within the provided range is one of the key problems in radio networks, since when the frequency is incorrectly provided for the radio station, there may be the radio wave interference effect, and the information transfer becomes distorted.  The article provides an algorithm for frequency planning, which may be used for providing  frequency for the radio stations within radio networks, the algorithm involves circular pattern, known radio station coordinates and the emitted radio power. The development of the algorithm involved experimental theoretical method based upon the known facts regarding radio broadcast and result modeling, as well as use of software. The novelty of the study is due to the development of an algorithm for frequency planning when designing a radio network for a provided frequency resource for a radio station with the circular pattern, known coordinates and emitted radio power. The result of its application involves distribution of radio frequency with their dual use, while excluding interference effect.


Keywords:

frequency division multiple access, frequency planning algorithm, wireless connection, cellular network, frequency spectrum control, mesh network, frequency planning, radio network, interference, radio access


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

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

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

Ход решения

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

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

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

_1

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

Алгоритм заполнения матрицы приема-передачи

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

Lij = ` ` , расстояние от РСi к РСjбудем обозначать L ij.

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

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

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

Номер принимающей РС

R1

R2

R3

R4

R5

R6

R7

R8

R9

R10

R11

R12

R13

R14

R15

Номер передающей РС

R1

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

R2

0

0

0

0

0

0

0

1

0

1

0

0

0

0

0

R3

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

R4

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

R5

0

0

0

0

0

0

0

0

1

0

0

0

0

0

1

R6

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

R7

1

0

0

0

0

0

0

0

0

0

0

0

1

0

0

R8

0

1

0

0

0

0

0

0

0

1

0

0

0

0

0

R9

0

0

0

0

1

0

0

0

0

0

0

1

0

0

1

R10

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

R11

1

0

0

0

0

0

0

0

0

0

0

0

0

1

0

R12

0

0

0

0

0

1

0

0

1

0

0

0

0

0

1

R13

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

R14

0

0

1

0

0

1

0

0

0

0

0

0

0

0

0

R15

0

0

0

0

1

1

0

0

1

0

0

1

0

1

0

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

a1

Рис. 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. В результате задачу примера можно разделить на три задачи, таким образом данный алгоритм позволяет выделить из матрицы А независимые топологии радиосети и получить матрицы Aj, где 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. Матрица А с выделенными РС первой подзадачи

Номер принимающей РС

R1

R2

R3

R4

R5

R6

R7

R8

R9

R10

R11

R12

R13

R14

R15

Номер передающей РС

R1

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

R2

0

0

0

0

0

0

0

1

0

1

0

0

0

0

0

R3

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

R4

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

R5

0

0

0

0

0

0

0

0

1

0

0

0

0

0

1

R6

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

R7

1

0

0

0

0

0

0

0

0

0

0

0

1

0

0

R8

0

1

0

0

0

0

0

0

0

1

0

0

0

0

0

R9

0

0

0

0

1

0

0

0

0

0

0

1

0

0

1

R10

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

R11

1

0

0

0

0

0

0

0

0

0

0

0

0

1

0

R12

0

0

0

0

0

1

0

0

1

0

0

0

0

0

1

R13

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

R14

0

0

1

0

0

1

0

0

0

0

0

0

0

0

0

R15

0

0

0

0

1

1

0

0

1

0

0

1

0

1

0

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

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

Номер принимающей РС

R1

R3

R5

R6

R7

R9

R11

R12

R13

R14

R15

Номер передающей РС

R1

0

0

0

0

0

0

0

0

1

0

0

R3

0

0

0

0

0

0

0

0

0

1

0

R5

0

0

0

0

0

1

0

0

0

0

1

R6

0

0

0

0

0

0

0

1

0

1

0

R7

1

0

0

0

0

0

0

0

1

0

0

R9

0

0

1

0

0

0

0

1

0

0

1

R11

1

0

0

0

0

0

0

0

0

1

0

R12

0

0

0

1

0

1

0

0

0

0

1

R13

0

0

0

0

0

0

0

0

0

0

0

R14

0

1

0

1

0

0

0

0

0

0

0

R15

0

0

1

1

0

1

0

1

0

1

0

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

Номер принимающей РС

R2

R4

R8

R10

Номер передающей РС

R2

0

0

1

1

R4

0

0

0

0

R8

1

0

0

1

R10

0

0

1

0

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

Номер принимающей РС

R2

R4

R8

R10

Номер передающей РС

R2

0

0

1

1

R8

1

0

0

1

R10

0

0

1

0

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

Номер принимающей РС

R4

Номер передающей РС

R4

0

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

a2

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

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

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

Алгоритм заполнения матрицы В (матриц Вj)

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

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

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

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

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

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

Номер принимающей РС

R1

R3

R5

R6

R7

R9

R11

R12

R13

R14

R15

Номер передающей РС

R1

0

0

0

0

0

0

0

0

1

0

0

R3

0

0

0

0

0

0

0

0

0

1

0

R5

0

0

0

0

0

1

0

0

0

0

1

R6

0

0

0

0

0

0

0

1

0

1

0

R7

1

0

0

0

0

0

0

0

1

0

0

R9

0

0

1

0

0

0

0

1

0

0

1

R11

1

0

0

0

0

0

0

0

0

1

0

R12

0

0

0

1

0

1

0

0

0

0

1

R13

0

0

0

0

0

0

0

0

0

0

0

R14

0

1

0

1

0

0

0

0

0

0

0

R15

0

0

1

1

0

1

0

1

0

1

0

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

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

Номер принимающей РС

R1

R3

R5

R6

R7

R9

R11

R12

R13

R14

R15

Номер передающей РС

R1

1

R3

1

R5

0

R6

0

R7

1

R9

0

R11

1

R12

0

R13

1

R14

0

R15

0

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

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

Номер принимающей РС

R1

R3

R5

R6

R7

R9

R11

R12

R13

R14

R15

Номер передающей РС

R1

0

1

1

1

0

1

0

1

0

1

1

R3

1

0

1

0

1

1

0

1

1

0

0

R5

1

1

0

1

1

0

1

0

1

1

0

R6

1

0

1

0

1

0

0

0

1

0

0

R7

0

1

1

1

0

1

0

1

0

1

1

R9

1

1

0

0

1

0

1

0

1

1

0

R11

0

0

1

0

0

1

0

1

1

0

0

R12

1

1

0

0

1

0

1

0

1

0

0

R13

0

1

1

1

0

1

1

1

0

1

1

R14

1

0

1

0

1

1

0

0

1

0

0

R15

1

0

0

0

1

0

0

0

1

0

0

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

Номер принимающей РС

R2

R8

R10

Номер передающей РС

R2

0

0

0

R8

0

0

0

R10

0

0

0

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

Номер принимающей РС

R4

Номер передающей РС

R4

0

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

a3

Рис. 4. Блок схема алгоритма заполнения матрицы В (матриц Вj)

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

  • W - вспомогательная переменная.
  • Buf[i] - вспомогательный массив, содержащий, номер строк для матрицы В, где найденный номер строки будет равен единице при заполнении того же номера столбца матрицы В.
  • B[i][j] - матрица В.

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

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

  1. Выделим строку с минимальной построчной суммой (строка W), не равной нулю, если таких строк несколько выделяем любую, в случае если построчная сумма равна нулю, значит РС данной строки уже входит в группу одночастотных РС;
  2. На строке W находим единичные элементы bwn, где 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. Из п.1 вышеописанного алгоритма, выделим минимальную построчную сумму в матрице В1 – строка R15. Далее в соответствии п. 2 выделим строки R1, R7 и R13 и столбцы с тем же номером, результат представлен в таблице 12.

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

Номер принимающей РС

R1

R3

R5

R6

R7

R9

R11

R12

R13

R14

R15

Номер передающей РС

R1

0

1

1

1

0

1

0

1

0

1

1

R3

1

0

1

0

1

1

0

1

1

0

0

R5

1

1

0

1

1

0

1

0

1

1

0

R6

1

0

1

0

1

0

0

0

1

0

0

R7

0

1

1

1

0

1

0

1

0

1

1

R9

1

1

0

0

1

0

1

0

1

1

0

R11

0

0

1

0

0

1

0

1

1

0

0

R12

1

1

0

0

1

0

1

0

1

0

0

R13

0

1

1

1

0

1

1

1

0

1

1

R14

1

0

1

0

1

1

0

0

1

0

0

R15

1

0

0

0

1

0

0

0

1

0

0

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

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

Номер принимающей РС

R3

R5

R6

R7

R9

R11

R12

R13

R14

Номер передающей РС

R3

0

1

0

1

1

0

1

1

0

R5

1

0

1

1

0

1

0

1

1

R6

0

1

0

1

0

0

0

1

0

R7

1

1

1

0

1

0

1

0

1

R9

1

0

0

1

0

1

0

1

1

R11

0

1

0

0

1

0

1

1

0

R12

1

0

0

1

0

1

0

1

0

R13

1

1

1

0

1

1

1

0

1

R14

0

1

0

1

1

0

0

1

0

R1-R15

0

0

0

0

0

0

0

0

0

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

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

Номер принимающей РС

R11

Номер передающей РС

R11

0

R3-R12

0

R9-R13-R14

0

R5-R6-R7

0

R1-R15

0

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

Номер принимающей РС

R2

R8

R10

Номер передающей РС

R2

0

0

0

R8

0

0

0

R10

0

0

0

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

Номер принимающей РС

R4

Номер передающей РС

R4

0

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

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

a4

Рис. 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 – полоса защиты.

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

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

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

f0 = R5, R6, R7

f1 = R9, R13, R14

f2 = R1, R15

f3 = R3, R12

f4 = R11

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

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

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

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

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

f0 = [100;119.9] МГц f1 = [120;139.9] МГц f2 = [140;159.9] МГц

f3 = [160;179.9] МГц f4 = [180;200] МГц

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

f0 = R2 f0 = [100;133.2] МГц

f1 = R8 f1 = [133.3;166.5] МГц

f2 = R10 f2 = R2 [166,6;200] МГц

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

f0 = R4 f0 = [100;200] МГц

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

a5

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

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

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

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

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

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

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

Номер принимающей РС

R1

R3

R5

R6

R7

R9

R11

R12

R13

R14

R15

Номер передающей РС

R1

0

1

1

1

0

1

0

1

0

1

1

R3

1

0

1

0

1

1

0

1

1

0

0

R5

1

1

0

1

1

0

1

0

1

1

0

R6

1

0

1

0

1

0

0

0

1

0

0

R7

0

1

1

1

0

1

0

1

0

1

1

R9

1

1

0

0

1

0

1

0

1

1

0

R11

0

0

1

0

0

1

0

1

1

0

0

R12

1

1

0

0

1

0

1

0

1

0

0

R13

0

1

1

1

0

1

1

1

0

1

1

R14

1

0

1

0

1

1

0

0

1

0

0

R15

1

0

0

0

1

0

0

0

1

0

0

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

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

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

Полоса частот

Основная

Дополнительная

Номер РС

R1

[140;159.9] МГц

[160;179.9] МГц

R3

[160;179.9] МГц

отсутствует

R5

[100;119.9] МГц

[180;200] МГц

R6

[100;119.9] МГц

отсутствует

R7

[100;119.9] МГц

[160;179.9] МГц

R9

[120;139.9] МГц

[180;200] МГц

R11

[180;200] МГц

[180;200] МГц отсутствует

R12

[160;179.9] МГц

[180;200] МГц

R13

[120;139.9] МГц

[160;179.9],[160;179.9] МГц

R14

[120;139.9] МГц]

отсутствует

R15

[140;159.9] МГц

отсутствует

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

Полоса частот

Основная

Дополнительная

Номер РС

R2

[100;133.2] МГц

отсутствует

R8

[133.3;.166.5] МГц

отсутствует

R10

[166.6;200] МГц

отсутствует

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

Полоса частот

Основная

Дополнительная

Номер РС

R4

[100;200] МГц

отсутствует

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

a6

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

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

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

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

_04082017_225703

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

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

Вывод

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

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

References
1. Marcel Rocha Da Silva M., Ferreira De Rezende J. TDCS: A new mechanism for automatic channel assignment for independent IEEE 802.11 networks // 8th IFIP Annual Mediterranean Ad Hoc Networking Workshop. – 2009.– P. 27–33.
2. Garkusha S. V. Analiz rezul'tatov raspredeleniya chastotnykh kanalov v mnogokanal'nykh mnogointerfeisnykh mesh-setyakh standarta IEEE 802.11 // Sbornik nauchnykh trudov «Tsifrovye tekhnologi». – 2011 – №10 – s. 51 – 62.
3. Garkusha S.V. Ierarkhichesko-koordinatsionnyi metod raspredeleniya chastotnykh kanalov mesh-seti IEEE 802.11 na osnove printsipa prognozirovaniya vzaimodeistvii // Upravlenie, vychislitel'naya tekhnika i informatika. – 2014 – c. 156 – 166.
4. Garkusha C.V. Model' sbalansirovannogo raspredeleniya podkanalov v mesh-seti, ispol'zuyushchei tekhnologiyu WiMax // Infokommunikatsionnye sistemy. – 2013 – c. 135–140.
5. Gogoleva M.A., Garkusha S.V., Akhmed Kh. Abed eksperimental'noe issledovanie matematicheskoi modeli raspredeleniya kanalov v mnogokanal'nykh mesh-setyakh standarta IEEE 802.11 // Radiotekhnika: Vseukr. mezhved. nauch.-tekhn. sb. – 2010. – Vyp. 163. – S. 99‒107.
6. Demichev M.S., Gaipov K.E. REShENIE ZADAChI UPRAVLENIYa ChASTOTNYM RESURSOM V KRUPNOMASShTABNYKh MESH-SETYaKh // Tekhnicheskie nauki - ot teorii k praktike: sb. st. po mater. LXV mezhdunar. nauch.-prakt. konf. № 12(60). – Novosibirsk: SibAK, 2016. – S. 130-142.
7. Lemeshko A.V., Gogoleva M.A. Model' strukturnoi samoorganizatsii mnogokanal'noi mesh–seti standarta IEEE 802.11 [Elektronnyi resurs] // Problemi telekomunіkatsіi. – 2010. – № 1 (1). – S. 83–95. – Rezhim dostupa k zhurn.: http://pt.journal.kh.ua/2010/11/101_lemeshko_mesh.pdf
8. Lemeshko A.V. Gogoleva M.A. Trekhindeksnaya matematicheskaya model' raspredeleniya chastotnykh kanalov v mnogokanal'nykh mesh-setyakh // Zbіrnik naukovikh prats' «Modelyuvannya ta іnformatsіinі tekhnologії» – Kiїv, 2009. – №54. – S. 94–103.
9. Lemeshko A.V., Garkusha S.V. Klassifikatsiya metodov raspredeleniya chastotnykh kanalov v mnogointerfeisnykh mnogokanal'nykh mesh-setyakh standarta IEEE 802.11 [Elektronnyi resurs] // Problemi telekomunіkatsіi. – 2011. – № 2 (4). – S. 139–149. – Rezhim dostupa k zhurn.: http://pt.journal.kh.ua/2011/2/1/112_ lemeshko_classification.pdf.
10. Pustogarov I.A., Lyakhov A.I., Shpilev S.A. Mnogokanal'nye mesh-seti: analiz podkhodov i otsenka proizvoditel'nosti [Elektronnyi resurs] // Informatsionnye protsessy (Information processes). – 2008. – Tom 8 (3). – S. 173-192. – Rezhim dostupa k zhurn.: http://www.jip.ru/2008/173-192-2008.pdf .