РЕШЕНИЕ ЗАДАЧИ УПРАВЛЕНИЯ ЧАСТОТНЫМ РЕСУРСОМ В КРУПНОМАСШТАБНЫХ MESH-СЕТЯХ

OPTIMIZED SOLUTION TO THE PROBLEM OF FREQUENCY PLANNING MESH NETWORKS

Maksim Demchev

4th year student, Department of Information Technology Security SibSAU,

Russia, Krasnoyarsk

Konstantin Gaipov

phD. tehn. Sciences, associate professor of Siberian State Aerospace University,

Russia, Krasnoyarsk

АННОТАЦИЯ

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

ABSTRACT

In this article the algorithm of frequency planning in wireless MESH network with any topology, without restriction on the number of transceivers on one MESH node and with frequency separation of channels is described. The mathematical distribution model of frequency channels between each couple of interacting MESH nodes which is written down in the form of system of the linear equations is result of work of an algorithm.

Ключевые слова: частотное планирование, MESH – сеть, управление частотным спектром.

Keywords: radio stations, reception and transmission matrix, combination signal, element, single-frequency signals.

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

Постановка задачи. Исходными данными для начала работы алгоритма является следующая топологическая информация: количество MESH узлов, координатные данные радиостанций, область действия каждой MESH станции, а также выделенный диапазон частот ΔF. Таким образом, сеть подобного типа можно описать матрицей связности, которая обозначена в алгоритме, как матрица А. Матрица А составляется из предположения, что если узел i входит в зону действия узла j, то связь между узлами существует и элемент a_ij в матрице А элемент равен 1, в противном случае 0.

В результате алгоритма будет определено общее число непересекающихся частотных диапазонов Δf_i, с каждым из таких частотных диапазонов будет ассоциирован симплексный частотный канал связи Δf_ij между парой узлов i и j.

Описание алгоритма. Опираясь на статью [5]:

1. составим матрицу А;
2. оптимизируем матрицу А.

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

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

Критерий 1.Если сумма единиц по строке i не меньше половины от общего количества элементов в строке (критерий исключения по строке);

Критерий 2.Если сумма единиц по столбцу i не меньше половины от общего количества элементов в столбце (критерий исключения по столбцу);

Критерий 3.Если сумма единиц по столбцу i не меньше половины от общего количества элементов в столбце и сумма единиц по строке i не меньше половины от общего количества элементов в строке (критерий исключения по столбцу и строке).

 Данные критерии были получены из многократного применения алгоритма над разными топологиями, в результате исключения элементов по критериям 1, 2, 3 получим матрицу А`.

Оптимизируем матрицу А` по аналогии с матрицей А.

Алгоритм разделения на кластеры, где каждый кластер это совокупность MESH-узлов, топология каждого кластера будет описана в матрице А`_j:

1. в матрицы А` выделяем i-строку и i-столбец матрицы А` (с наибольшей суммой по строке i);
2. в выделенной строке выделим единичные элементы и их столбцы;
3. в выделенных столбцах выделим единичные элементы и их строки;
4. из пункта 2 выделяем одноименные строки;
5. из пункта 3 выделяем одноименные столбцы;
6. выписываем в подматрицу А``_j элементы, выделенные в матрице А (j – номер, от 1 до количества подматриц);
7. если в матрице А остались невыделенные элементы, то необходимо повторить с пункта 1, где поиск следующих кластеров, осуществляется по невыделенным элементам.
8. исключенные i-ые строки и i-ые столбцы по критериям 1, 2, 3, и оптимизации матрицы А`, добавляются в подматрицу А``<sub>j</sub>, если имеют пересечение по i-ому столбцу или i-ой строки, в матрице А с одноименными строками матрицы А``_j, в матрице А.

Примечание: одинаковые элементы могут находиться в нескольких подматрицах.

В результате получим подматрицы А`<sub>j</sub> , количество подматриц А`_j показывает число кластеров, а количество и номера радиостанций входящих в кластер соответствует количеству и номерам столбцов подматрицы А`.

Алгоритм поиска одночастотных сигналов. Введем понятие комбинации сигналов (далее комбинация), под комбинацией будем понимать сигналы, которые могут находиться на одной и той же частоте.

Опираясь на алгоритм статьи [5]:

1. составим подматрицы B_j;
2. при оптимизации подматриц B_j (оптимизация матрицы или подматрицы B_j описана в статье [5]), получаем подматрицы B`_j , при этом сигналы, соответствующие строка и столбцам, которые были исключены из подматриц B_j, вносятся в список комбинаций.
3. найдем комбинации сигналов для каждой подматрицы.

Для дальнейшей работы рассмотрим запись сигнала: , где n – номер передающей станции, m - номер принимающей станции.

Алгоритм поиска частотных симплексных каналов, работающих на одной частоте:

1. сортируем список комбинаций, по количеству элементов (сигналов) в комбинации принимаем комбинацию с наибольшим количеством элементов, принятую комбинацию убираем;
2. рассматриваем каждый из сигналов Fn/m, находящихся в принятой комбинации. Из не принятых комбинациях убираем сигналы, содержащие элементы n и m в сигналах принятой комбинации.
3.  обращаемся к матрице A:

• По матрице А определим, кому передают станции n, где принимающие станции m_i, тогда временно исключим сигналы из списка комбинации по маске Fx/m_i, где x – любое число.
• По матрице А определим, от кого принимают станции m, где передающие станции n_i, тогда временно исключим сигналы из списка комбинации по маске Fn_i/x, где x – любое число.

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

Пример. Пусть имеются произвольное количество узлов, координаты радиостанций, круговая диаграмма направленности и дальность распространения радиоволн каждой радиостанцией, в результате, которого получили топологию радиостанций, изображенной на рис. 1. Алгоритм, описывает ситуацию с количеством радиостанций более 50, но для примера возьмём меньше количество радиостанций равную 15, из соображений масштабности описания примера в данной статье. Найти сигналы, которые могут находиться на одних и тех же частотах и распределить выделенный диапазон частот .

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

Составим матрицу А, опираясь на топологию из рис.1. Радиостанцию будем обозначать как R№, где № – номер радиостанции. Получим матрицу А (таблица 1).

Таблица 1.

Матрица А

Оптимизируем матрицу А, исключая радиостанции, имеющие в сумме по строке и столбцу ноль. Получившую оптимизированную матрицу, также обозначим за A.

Т. к. матрица А, содержит 15 элементов, то половина =7,5 (в округлении 8, что и будем считать за половину элементов), то исключим элементы содержащие сумму по строке или столбцу более 8. Из таблицы 1 видно, что таковых элементов нет, поэтому никакие элементы исключаться не будут а, следовательно, из алгоритма разбиения матрицы приема-передачи А, не будет матрицы А` и подматриц А`j.

Выполним алгоритм разбиения матрицы А, описанного в данной статье в разделе «Алгоритм разбиения матрицы приема-передачи А». Результатом разбиения является подматрицы А1, А2, А3 представленные в таблицах 2, 3, 4 соответственно.

Таблица 2.

Подматрица А₁

∑₁ – сумма по строкам; ∑₂ – сумма по столбцам

Таблица 3.

Подматрица А₂

∑₁ – сумма по строкам; ∑₂ – сумма по столбцам

Таблица 4.

Подматрица А₃

∑₁ – сумма по строкам; ∑₂ – сумма по столбцам

Из подматриц А1, А2, А3 составим подматрицы B1, B2, B3 соответственно, опираясь на алгоритм описанный в статье [5], с выделением сигналов по строке и столбцу, которые имеют сумму по строке равную нолю, результаты примера представлены в таблицах 5,6,7 соответственно.

Таблица 5.

Подматрица B₁

Таблица 6.

Подматрица B₂

Таблица 7.

Подматрица B₃

Из выше представленных матриц B1, B2, B3, можем сразу записать в список комбинаций следующие комбинации (состоящие из одного элемента), те сигналы, которые не могут находиться на одной частоте с другими сигналами, в своей подматрицы Bj:

F15/5, F15/6, F15/9, F15/12, F15/14, F2/8, F2/10, F8/2, F8/10, F10/8, F1/13, F7/1, F7/13, F11/1.

Рассматриваем подматрицы B1, B2, B3, для поиска комбинаций сигналов, которые могут находиться на одних и тех же частотах. Поиск комбинаций одночастотных сигналов проводим по алгоритму, описанному в [5], без учета выделенных элементов в подматрицах B1, B2, B3.

Выписываем найденные комбинации и не учтенные сигналы из подматриц B1, B2, B3:

F3/14—F5/9          F11/14—F5/9      F14/3—F5/9       F5/9—F14/6

F3/14—F5/15                 F11/14—F5/15    F14/3—F5/15     F5/9—F6/12

F3/14—F9/5          F11/14—F9/5      F14/3—F9/5       F5/9—F6/14

F3/14—F9/12                 F11/14—F9/12    F14/3—F9/12     F5/15—F6/12

F3/14—F9/15                 F11/14—F9/15    F14/3—F9/15     F5/15—F6/14

F3/14—F12/6                 F11/14—F12/6    F14/3—F12/6     F5/15—F14/6

F3/14—F12/9                 F11/14—F12/9    F14/3—F12/9     F9/5—F6/14

F3/14—F12/15               F11/14—F12/15  F14/3—F12/15   F9/5—F14/6

F9/15—F6/14                 F9/15—F14/6      14/6—F9/12      

F15/5  F15/6          F15/9          F15/12        F15/14        F2/8            F2/10

F8/2    F8/10          F10/8          F1/13          F7/1            F7/13          F11/1

По алгоритму необходимо провести сортировку списка комбинаций по количеству элементов в комбинациях, но на этом примере видно, что сигналы достигают максимального количества элементов равного двум, поэтому в нашем случае выберем любую комбинацию с количеством элементов равная двум и примем: F3/14–F9/12.

Временно исключим сигналы, которые содержат 3, 14, 9, 12, в позиции приёма и передачи, получим:

F15/5           F15/6          F15/9          F2/8            F2/10          F8/2

F8/10           F10/8          F1/13          F7/1            F7/13          F11/1

Обратимся к матрице А. На строках R3, R9 находим единицы, которые пересекаются по столбцу, получаем R5, R6, R9, R12, R14, R15 значит, исключим временно элементы в непринятых комбинациях по виду Fx/5, Fx/6, Fx/9, Fx/12, Fx/14, Fx/15, где x – любое число. Получаем:

F2/8    F2/10    F8/2    F8/10    F10/8    F1/13    F7/1    F7/13    F11/1

Обратимся к матрице А. На столбцах R12, R14 находим единицы, которые пересекаются по строке, получаем R3, R6, R9, R11, R15 значит, исключим временно элементы в непринятых комбинациях по виду F3/x, F5/x, F6/x, F9/x, F11/x, F12/x, F14/x, F15/x, где x –любое число. Получаем:

F2/8    F2/10    F8/2    F8/10    F10/8    F1/13    F7/1    F7/13

Из полученного списка примем комбинацию с максимальным количеством элементов, в нашем случае любой из сигналов: F10/8.

Принятая комбинация записывается как F3/14—F9/12—F10/8.

Исключим временно сигналы, которые содержат 8,10, в позиции приёма и передачи, получим:

F1/13    F7/1    F7/13

Обратимся к матрице А. На строке R10 находим единицу на пересечение по столбцу, получаем R8, значит, исключим временно элементы в непринятых комбинациях по виду Fn/8, где n – любое число. Получаем:

F1/13    F7/1    F7/13

Обратимся к матрице А. На столбце R8 находим единицы на пересечении по строке, в нашем случае получаем R2, R10, значит, исключим временно элементы в непринятых комбинациях по виду F2/n, F10/n, где n –любое число. Получаем:

F1/13    F7/1    F7/13

Из полученного списка примем любой из сигналов: F7/1.

На данный момент приятая комбинация записывается как F3/14–F9/12 – F10/8 – F7/1.

Исключим временно сигналы, которые содержат 1,7, в позиции приёма и передачи, получим:

пустой список комбинаций.

Значит F3/14–F9/12 – F10/8 – F7/1 записываем в список одночастотных сигналов.

Теперь возвращаем исходный список комбинаций, но исключаем в нем элементы F3/14–F9/12 – F10/8 – F7/1, получаем:

F11/14—F5/9                 F14/3—F5/9                 F5/9—F14/6

F11/14—F5/15               F14/3—F5/15               F5/9—F6/12

F11/14—F9/5                 F14/3—F9/5                 F5/9—F6/14

F11/14—F9/15               F14/3—F9/15               F5/15—F6/14

F11/14—F12/6               F14/3—F12/6               F5/15—F14/6

F11/14—F12/9               F14/3—F12/9               F9/5—F6/14

F11/14—F12/15             F14/3—F12/15             F9/5—F14/6

F9/15—F6/14                 F9/15—F14/6               F5/15—F6/12     

F15/5           F15/6          F15/9          F15/12        F15/14        F2/8            F2/10

F8/2             F8/10          F1/13          F11/1          F5/9            F5/15          F9/5

F12/6           F14/3          F12/9          F12/15        F14/6

Принимаем список комбинации с изменениями как исходный.

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

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

Список литературы:

1. Альшаев И.А., Лаврухин В.А. О ПРОЕКТИРОВАНИИ И ОПТИМИЗАЦИИ СЕТЕЙ WI-FI // Информационные технологии и телекоммуникации. 2016. Том 4. № 1. С. 87–95.
2. Гаркуша С.В. Анализ результатов распределения частотных каналов в многоканальных многоинтерфейсных MESH-сетях стандарта IEEE 802.11 // Сборник научных трудов «Цифровые технологи». – 2011 – № 10 – С. 51–62.
3. Гаркуша С.В. Иерархическо-координационный метод распределения частотных каналов MESH-сети IEEE 802.11 на основе принципа прогнозирования взаимодействий // Управление, вычислительная техника и информатика. – 2014 – С. 156–166.
4. Гаркуша C.В. Модель сбалансированного распределения подканалов в MESH-сети, использующей технологию WiMax // Инфокоммуникационные системы. – 2013 – С. 135–140.
5. Демичев М.С. РЕШЕНИЕ ЗАДАЧИ ЧАСТОТНОГО ПЛАНИРОВАНИЯ MESH СЕТЕЙ // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. XLIV междунар. студ. науч.-практ. конф.
6. Лемешко A.В. Разработка и анализ двухиндексной модели распределения каналов в многоканальной MESH-сети стандарта IEEE 802.11 // Электронное научное специализированное издание.