СЕКЦИЯ
«ТРАНСПОРТ И СВЯЗЬ, КОРАБЛЕСТРОЕНИЕ»
РЕШЕНИЕ ЗАДАЧИ УПРАВЛЕНИЯ ЧАСТОТНЫМ РЕСУРСОМ В КРУПНОМАСШТАБНЫХ MESH-СЕТЯХ
Демичев Максим Сергеевич
студент 4 курса,
кафедра безопасности информационных технологий СибГАУ, РФ,
г. Красноярск E-mail: maks15krs@gmail.com
Гаипов Константин Эдуардович
канд. техн. наук, доц. СибГАУ, РФ, г. Красноярск
OPTIMIZED SOLUTION TO THE PROBLEM OF FREQUENCY PLANNING MESH NETWORKS
Maksim Demchev
Department of Information Technology Security SibSA U,
Russia, Krasnoyarsk
Konstantin Gaipov
phD. tehn. Sciences, associate professor of Siberian State Aerospace University, Russia, Krasnoyarsk
АННОТАЦИЯ
В данной статье описан алгоритм частотного планирования в беспроводной MESH сети с произвольной топологией, без ограничения по количеству приемопередатчиков на одном MESH узле и с частотным разделением каналов. Результатом работы алгоритма является математиwww.sibac.info
ческая модель распределения частотных каналов между каждой парой взаимодействующих 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 сети, где каждый узел может выступать как в роли транзитного, так и в роли конечного узла. При этом в зависимости от применения такие сети могут иметь фиксированную топологию так и динамически изменяемую. Перспективность таких сетей обусловлено отсутствием кабельной инфраструктуры, являющейся самой дорогой частью практически любого проекта. При организации MESH-сети естественным ограничением является частотный диапазон, в котором совместно должны работать все узлы и мощность передатчика, используемого для взаимодействия между ними. В связи с чем, предлагается алгоритм получения математической модели распределения частотного ресурса при ограниченной мощности передатчика и произвольным расположением узлов. Особенностью предлагаемого алгоритма является его возможность работать с сетями, содержащими большое число MESH-узлов, так как позволяет разбить исходную сеть на кластеры, которые анализируются базовым алгоритмом распределения частотного ресурса. Применение же базового алгоритма без кластеризации приводит к резкому увеличению числа операций для получения конечной системы уравнений.
Постановка задачи. Исходными данными для начала работы алгоритма является следующая топологическая информация: количество MESH узлов, координатные данные радиостанций, область действия каждой MESH станции, а также выделенный диапазон частот AF. Таким образом, сеть подобного типа можно описать матрицей связности, которая обозначена в алгоритме, как матрица А. Матрица А
составляется из предположения, что если узел i входит в зону действия узла j, то связь между узлами существует и элемент aiJ в матрице А элемент равен 1, в противном случае 0.
В результате алгоритма будет определено общее число непересекающихся частотных диапазонов Afi, с каждым из таких частотных диапазонов будет ассоциирован симплексный частотный канал связи Mi между парой узлов i и j.
Описание алгоритма. Опираясь на статью [5]:
При анализе больших сетей, получившаяся матрица А будет иметь большое число нулевых элементов, так как каждый MESH узел связан с небольшим числом соседних узлов, поэтому для ускорения выполнения алгоритма, можно разбить матрицу А на подматрицы меньших размеров.
Алгоритм разбиения матрицы приема-передачи А. Из исходной матрицы А для более рационального разбиения необходимо временно исключить i-ые строки и i-ые столбцы, по следующим критериям:
Критерий 1. Если сумма единиц по строке i не меньше
половины от общего количества элементов в строке (критерий исключения по строке);
Критерий 2. Если сумма единиц по столбцу i не меньше
половины от общего количества элементов в столбце (критерий исключения по столбцу);
Критерий 3. Если сумма единиц по столбцу i не меньше
половины от общего количества элементов в столбце и сумма единиц по строке i не меньше половины от общего количества элементов в строке (критерий исключения по столбцу и строке).
Данные критерии были получены из многократного применения алгоритма над разными топологиями, в результате исключения элементов по критериям 1, 2, 3 получим матрицу А\\
Оптимизируем матрицу А по аналогии с матрицей А.
Алгоритм разделения на кластеры, где каждый кластер это совокупность MESH-узлов, топология каждого кластера будет описана в матрице А^:
www.sibac.info
Примечание: одинаковые элементы могут находиться в нескольких подматрицах.
В результате получим подматрицы А" , количество подматриц А" показывает число кластеров, а количество и номера радиостанций входящих в кластер соответствует количеству и номерам столбцов подматрицы А".
Алгоритм поиска одночастотных сигналов. Введем понятие комбинации сигналов (далее комбинация), под комбинацией будем понимать сигналы, которые могут находиться на одной и той же частоте.
Опираясь на алгоритм статьи [5]:
Для дальнейшей работы рассмотрим запись сигнала: Рп/т, где п -номер передающей станции, т - номер принимающей станции.
Алгоритм поиска частотных симплексных каналов, работающих на одной частоте:
• По матрице А определим, кому передают станции п, где принимающие станции т1, тогда временно исключим сигналы из списка комбинации по маске Бх/т1, где х - любое число.
• По матрице А определим, от кого принимают станции m, где передающие станции ц, тогда временно исключим сигналы из списка комбинации по маске Fni/x, где x - любое число.
Пример. Пусть имеются произвольное количество узлов, координаты радиостанций, круговая диаграмма направленности и дальность распространения радиоволн каждой радиостанцией, в результате, которого получили топологию радиостанций, изображенной на рис. 1. Алгоритм, описывает ситуацию с количеством радиостанций более 50, но для примера возьмём меньше количество радиостанций равную 15, из соображений масштабности описания примера в данной статье. Найти сигналы, которые могут находиться на одних и тех же частотах и распределить выделенный диапазон частот Д,Р.
Рисунок 1. Топология радиостанций
Составим матрицу А, опираясь на топологию из рис. 1. Радиостанцию будем обозначать как R№, где № - номер радиостанции. Получим матрицу А (таблица 1).
www.sibac.info
Таблица 1.
Матрица А
R1 К2 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
К2 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
Оптимизируем матрицу А, исключая радиостанции, имеющие в сумме по строке и столбцу ноль. Получившую оптимизированную матрицу, также обозначим за А.
Т. к. матрица А, содержит 15 элементов, то половина =7,5 (в округлении 8, что и будем считать за половину элементов), то исключим элементы содержащие сумму по строке или столбцу более 8. Из таблицы 1 видно, что таковых элементов нет, поэтому никакие элементы исключаться не будут а, следовательно, из алгоритма разбиения матрицы приема-передачи А, не будет матрицы А" и подматриц А".
Выполним алгоритм разбиения матрицы А, описанного в данной статье в разделе «Алгоритм разбиения матрицы приема-передачи А». Результатом разбиения является подматрицы А1, А2, А3 представленные в таблицах 2, 3, 4 соответственно.
Таблица 2.
Подматрица А1
R3 R5 R6 R9 R11 R12 R14 R15 71
R3 0 0 0 0 0 0 1 0 1
R5 0 0 0 1 0 0 0 1 2
R6 0 0 0 0 0 1 1 0 2
R9 0 1 0 0 0 1 0 1 3
R11 0 0 0 0 0 0 1 0 1
R12 0 0 1 1 0 0 0 1 3
R14 1 0 1 0 0 0 0 0 2
R15 0 1 1 1 0 1 1 0 5
X1 - сумма по строкам; X - сумма по столбцам
Таблица 3.
Подматрица А2
К2 R8 R10 71
К2 0 1 1 2
R8 1 0 1 2
R10 0 1 0 1
X - сумма по строкам; ^ - сумма по столбцам
Таблица 4.
Подматрица А3
R1 R7 R11 R13 7д
Ю 0 0 0 1 1
Я7 1 0 0 1 2
Я11 1 0 0 0 1
Ю3 0 0 0 0 0
X - сумма по строкам; ^ - сумма по столбцам
Из подматриц А1, А2, А3 составим подматрицы В1, В2, В3 соответственно, опираясь на алгоритм описанный в статье [5], с выделением сигналов по строке и столбцу, которые имеют сумму по строке равную нолю, результаты примера представлены в таблицах 5,6,7 соответственно.
www.sibac.info
Таблица 5.
Подматрица В1
Е3/14 0 1 1 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 8
Е5/9 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 6
Б5/15 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 6
Еб/12 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
Еб/14 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 4
Е9/5 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 5
Е9/12 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 4
Б9/15 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 5
И1/14 0 1 1 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 8
И2/6 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2
И2/9 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 3
И2/15 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 3
И4/3 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 7
И4/6 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 5
И5/5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
И5/6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
И5/9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
И5/12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
И5/14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
X1 - сумма по строкам; Х2 - сумма по столбцам
Таблица 6.
Подматрица В2
Е2/8 Е2/10 Е8/2 Е8/10 Е10/8 71
Е2/8 0 0 0 0 0 0
Е2/10 0 0 0 0 0 0
Е8/2 0 0 0 0 0 0
Е8/10 0 0 0 0 0 0
И0/8 0 0 0 0 0 0
Ь 0 0 0 0 0
XI - сумма по строкам; X2 - сумма по столбцам
Таблица 7.
Подматрица Вз
Е1/13 Е7/1 Е7/13 Е11/1 71
Р1/13 0 0 0 0 0
Р7/1 0 0 0 0 0
Р7/13 0 0 0 0 0
Р11/1 0 0 0 0 0
£1 - сумма по строкам; £2 - сумма по столбцам
Из выше представленных матриц В1, В2, В3, можем сразу записать в список комбинаций следующие комбинации (состоящие из одного элемента), те сигналы, которые не могут находиться на одной частоте с другими сигналами, в своей подматрицы Bj:
Р15/5, Р15/6, Р15/9, П5/12, Р15/14, Р2/8, Р2/10, Р8/2, Р8/10, Р10/8, Р1/13, Р7/1, Р7/13, Р11/1.
Рассматриваем подматрицы В1, В2, В3, для поиска комбинаций сигналов, которые могут находиться на одних и тех же частотах. Поиск комбинаций одночастотных сигналов проводим по алгоритму, описанному в [5], без учета выделенных элементов в подматрицах В1, В2, В3.
Выписываем найденные комбинации и не учтенные сигналы из подматриц В1, В2, В3:
БЗ/14- —Б5/9 П1/14—Б5/9 Б14/3- -Б5/9 Б5/9—Б14/6
БЗ/14- —Б5/15 Б11/14—Б5/15 Б14/3- —Б5/15 Б5/9—Б6/12
БЗ/14- —Б9/5 Б11/14—Б9/5 Б14/3- —Б9/5 Б5/9—Б 6/14
БЗ/14- —Б9/12 Б11/14—Б9/12 Б14/3- —Б9/12 Б5/15—Б6/12
БЗ/14- —Б9/15 Б11/14—Б9/15 Б14/3- —Б9/15 Б5/15—Б6/14
БЗ/14- —Б! 2/6 Б11/14—Б12/6 Б14/3- —Б12/6 Б5/15—Б14/6
БЗ/14- —Б12/9 Б11/14—Б12/9 Б14/3- —Б12/9 Б9/5—Б6/14
БЗ/14- —Б! 2/15 Б11/14—Б12/15 Б14/3- —Б12/15 Б9/5—Б14/6
Б9/15- —Б6/14 Б9/15—Б14/6 14/6— -Б9/12
Б15/5 Б15/6 Б15/9 Б15/12 Б15/14 Б2/8 Б2/10
Б 8/2 Б8/10 Б10/8 Б1/13 Б7/1 Б7/13 Б11/1
По алгоритму необходимо провести сортировку списка комбинаций по количеству элементов в комбинациях, но на этом
www.sibac.info
примере видно, что сигналы достигают максимального количества элементов равного двум, поэтому в нашем случае выберем любую комбинацию с количеством элементов равная двум и примем: 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
Технические науки — от теории к практике _№ 12 (60), 2016г.
Обратимся к матрице А. На столбце R8 находим единицы на пересечении по строке, в нашем случае получаем R2, R10, значит, исключим временно элементы в непринятых комбинациях по виду F2/n, F10/n, где n -любое число. Получаем:
F1/13 F7/1 F7/13
www.sibacinfo
Из полученного списка примем любой из сигналов: F7/1. На данный момент приятая комбинация записывается как Р3/14—Р9/12—Р10/8—Р7/1.
Исключим временно сигналы, которые содержат 1,7, в позиции приёма и передачи, получим:
пустой список комбинаций.
Значит F3/14-Р9/12 — Р10/8 — F7/1 записываем в список одночастотных сигналов.
Теперь возвращаем исходный список комбинаций, но исключаем в нем элементы F3/14—Р9/12—Р10/8—F7/1, получаем:
Fl 1/14—F5/9 Fl 1/14—F5/15 Fl 1/14—F9/5 Fl 1/14—F9/15 Fl 1/14—Fl 2/6 Fl 1/14—F12/9 Fl 1/14—F12/15 F9/15—F6/14 F15/5 Fl 5/6 F8/2 F8/10 F12/6 Fl 4/3
Fl 4/3—F5/9 F14/3—F5/15 Fl 4/3—F9/5 F14/3—F9/15 Fl 4/3—Fl 2/6 Fl 4/3—Fl 2/9 F14/3—F12/15 F9/15—F14/6 F15/9 F15/12 Fl/13 Fl 1/1 F12/9 F12/15
F5/9—F14/6 F5/9—F6/12 F5/9—F6/14 F5/15—F6/14 F5/15—F14/6 F9/5—F6/14 F9/5—Fl 4/6 F5/15—F6/12 F15/14 F2/8 F5/9 F5/15 Fl 4/6
F2/10 F9/5
Принимаем список комбинации с изменениями как исходный. Проводим поиск комбинаций сигналов, которые могут находиться на одних и тех же частотах, с учетом изменений списка комбинаций. В результате получим, решение:
www.sibac.info
F3/14 = F9/12 = F10/8 = F7/1 = ДД F11/14 = F9/5 = F8/10 = Д/2 F14/3 = F9/15 = F1/13 = Д/3 F5/15 = F6/14 = F8/2 = Д/4 F5/9 = F6/12— F11/1 = Д/5 F12/6 = F2/8 = Д/6 F15/14 = F2/10 = Д/7 F14/6 = F7/13 = Д/е F15/5 = Д/9 F15/6 = Д/ю F15/9 = Д/п F15/12 = Д/и F12/9 = Д/13 F12/15. = Д/14
Дft = ДР
Вывод. Описанный алгоритм в статье [5], выполнял задачу частотного планирования, но при анализе больших сетей алгоритм не является оптимальным, так как при его использовании будут выполняться операции сложения, перестановок и сравнения с большим числом элементов равными нулю. Алгоритм в представленной статье учитывает данный недостаток, путем разбиения топологии сети на группы и изменения поиска одночастотных сигналов, в результате чего получаем алгоритм, позволяющий за приемлемое время выполнить частотное планирование сети с большой топологией. Необходимо отметить, что алгоритм в зависимости от критерия выбора в поиске одночастотного сигнала будет давать различные списки одночастотных каналов, в данной статье критерий выбора частотных каналов был обусловлен, возможностью наибольшего переиспользования частотного ресурса, когда для решения других задач, такой критерий может оказаться не самым удачным.
Список литературы:
РЕШЕНИЕ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ПРОПУСКНОЙ СПОСОБНОСТИ MESH СЕТЕЙ
Демичев Максим Сергеевич
студент 4 курса, кафедра безопасности информационных технологий
СибГАУ, РФ, г. Красноярск E-mail: maks15krs@gmail.com
Гаипов Константин Эдуардович
канд. техн. наук, доц. СибГАУ, РФ, г. Красноярск
OPTIMIZED SOLUTION TO THE PROBLEM OF FREQUENCY PLANNING MESH NETWORKS
Maksim Demchev
Department of Information Technology Security SibSA U,
Russia, Krasnoyarsk