РЕШЕНИЕ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ПРОПУСКНОЙ СПОСОБНОСТИ 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

АННОТАЦИЯ

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

ABSTRACT

In this operation the algorithm of distribution of throughput of radio channels for network topologies with the pie chart of a directivity of radio stations is considered.

Ключевые слова: радиоканал, радиостанция, пропускная способность.

Keywords: radio channel, radio station, capacity.

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

Постановка задачи. Пусть Mesh сеть состоит из N узлов-радиостанций (далее РС) с координатами (X_i, Y_i) i 1..N, каждая РС_i имеет всенаправленную антенну, c радиусом действия R_i. Также известен выделенный диапазон частот для образованной топологии, состоящей из РС. К некоторым РС_i подключены кабельным путем локальные сети (ЛС), где обмен информацией между локальными сетями РС, осуществляется радио передачей с известной модуляцией. Также известен объем передачи данных между ЛС измеряемый в бит/сек, который записан в матрицу запросов. Необходимо определить трафик передачи данных, по радиоканалам связи.

Алгоритм решения. Для решения поставленной задачи необходимо выполнить следующий алгоритм:

1. Частотное планирование.

Из известных РС их координат, диаграммы направленности антенн, радиус действия антенн и выделенный диапазон частот, по алгоритму, описанному в [5], найдем одночастотные радиоканалы. В результате получаем на каждый радиоканал полосу частоты.

2. Поиск беспетельных маршрутов.

Общеизвестным методом анализа телекоммуникационных сетей является метод, предложенный в [1], в котором для глобальной оптимизации трафика предлагается в начале найти все маршруты от каждого источника до каждого получателя (все возможные беспетельные маршруты). В результате получаем перечень маршрутов для каждой передачи от ЛС_i к ЛС_j, где i,j – номера РС, с которыми соединены ЛС. Поиск беспетельных маршрутов осуществляем только в том случае, если в матрице запросов между двумя ЛС значение больше нуля.

3. Составить и решить систему неравенств, для определения контрольного отсчета решения. Составить и решить систему неравенств, с критерием оптимальности, учитывая решения контрольного отсчета.

Составление системы неравенств, для контрольного отсчета:

1. каждый беспетельный маршрут не меньше нуля. Количество неравенств равно числу беспетельных маршрутов, , где N – отдающая ЛС, M – принимающая ЛС, k – номер беспетельного маршрута.
2. все полосы радиоканалов не меньше нуля,  где  – радиоканал, i – отдающая РС, j – принимающая РС.
3. сумма всех радиоканалов равна выделенной полосе частот.
4. на каждый радиоканал записать сумму маршрутов, которые задействуют радиоканал, полученная сумма не меньше нуля и не больше пропускной способности данного радиоканала. Количество неравенств равно числу радиоканалов, , при , где  – коэффициент модуляции i-ой радиостанции.
5. сумма маршрутов от одной ЛС к другой ЛС равна согласно матрице запроса. Количество уравнений равно количеству ненулевых элементов из матрицы запросов,   S – значение из матрицы запросов.

В систему неравенства, с критерием оптимальности, входят выше описанные неравенства и критерий оптимальности: .

4. Распределить полученные полосы частот в выделенном частотном диапазоне.

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

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

В результате зная: задействованные маршруты и их потоки данных, задействованные радиоканалы и их минимальную пропускную способность – составим систему неравенств, аналогичной системе неравенств, с критерием оптимальности, где убираются все маршруты, радиоканалы, которые равны нулю, и учитывается повторное частотное планирование. В результате решения системы получим искомые полосы частот для радиоканалов. Распределение полученных полос в выделенном частотном диапазоне частот согласно [5].

Решение задачи. Для наглядности рассмотрим пример со следующими исходными данными.

Координаты радиостанций:

• РС1 (1;6), радиусом распространения сигнала R₁ = 2 км;
• РС2 (2;7), радиусом распространения сигнала R₂ = 2 км;
• РС3 (3;8), радиусом распространения сигнала R₃ = 2 км;
• РС4 (1;4), радиусом распространения сигнала R₄ = 2 км;
• РС5 (2;3), радиусом распространения сигнала R₅ = 2 км;
• РС6 (1;1), радиусом распространения сигнала R₆ = 2 км;
• РС7 (3;2), радиусом распространения сигнала R₇ = 2 км;
• РС8 (2;5), радиусом распространения сигнала R₇ = 2 км.

Выделенный частотный диапазон F  (3500..3600) МГц. Минимальный частотный диапазон сигнала 1 МГц. На РС3, РС6 и РС7 подсоединены ЛС А, В, С соответственно, где ЛС не имеют между собой кабельного соединения.

Модуляция: QAM-64. Таблица запросов ЛС представлена в таблице 1.

Таблица 1.

Таблица запросов ЛС

Схематичное изображение полученной топологии, представлено на рис. 1.

Рисунок 1. Топология Mesh сети

На основании топологии составим таблицу приёма и передачи (матрица А), представлена в Таблице 2.

Таблица 2.

Матрица А

Из матрицы А, составим матрицу одночастотных сигналов (матрица В), представлена в Таблице 3.

Таблица 3.

Матрица B

К матрице В применим алгоритм поиска одночастотных радиоканалов, на основании [5], в результате получим, радиоканалы, которые будут находиться на одной частоте:

Радиоканалы с индивидуальной частотой:

В результате поиска беспетельных маршрутов, получим маршруты представленные в таблице 4:

Таблица 4.

Таблица беспетельных маршрутов

На основании вышеизвестного составим систему неравенств, для получения контрольного отсчета, с учетом коэффициента модуляции QAM-64, который равен 6.

Ниже представлена система неравенств, для контрольного отсчета, представлено на рис. 2.

Рисунок 2. Система неравенств, для контрольного отсчета

Результат контрольного отсчета:

F1/2 = F5/6 = 5,017 МГц        F1/4 = F5/7 = 5,017 МГц      F2/1 = F5/4 = 0,017 МГц

F2/3 = F4/5 = 5,017 МГ\ц       F2/8 – F6/4 = 6,683 МГц      F3/2 – F4/1 = 6,683 МГц

F6/5 = F1/8= 1,683 МГц         F8/1 = 0,017 МГц                  F8/2 = 0,017 МГц

F8/4 = 5,017 МГц                    F8/5 = 5,017 МГц                  F4/6 = 0,017 МГц

F4/8 = 0,017 МГц                    F5/8 = 1,683 МГц                  F7/5 = 56,417 МГц

СА5 = 15          СВ3 = 10        ВА1 = 15        ВС2 = 10        АВ4 = 20        АС7 = 20.

Остальные маршруты равны нулю.

Система неравенств, с критерием оптимальности состоит из аналогичной системы неравенств, представленной выше, только с добавлением:

В результате решения системы было получено:

F1/2 = F5/6 = 9,447 МГц        F1/4 = F5/7 = 9,447 МГц      F2/1 = F5/4 = 0,017 МГц

F2/3 = F4/5 = 9,447 МГц        F2/8 – F6/4 = 17,165 МГц    F3/2 – F4/1 = 27,65 МГц

F6/5 = F1/8= 1,85 МГц           F8/1 = 0,017 МГц                  F8/2 = 0,017 МГц

F8/4 = 9,447 МГц                    F8/5 = 9,447 МГц                  F4/6 = 0,017 МГц

F4/8 = 0,017 МГц                    F5/8 = 1,85 МГц                    F7/5 = 2,317 МГц

СА5 = 15          СВ3 = 10        ВА1 = 15        ВС2 = 10        АВ4 = 20        АС7 = 20.

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

Выпишем задействованные маршруты:

СА5: F2/3– F1/2 – F4/1 – F6/4 – F5/6 – F7/5

СВ3: F8/4 – F5/8 – F7/5

ВА1: F4/1 – F1/2 – F2/3

ВС2: F4/1 – F1/8 – F8/5 – F5/7

АВ4: F8/4 – F2/8 – F3/2

АС7: F3/2 – F2/8 – F8/5 – F5/7

Из задействованных маршрутов, выделим радиоканалы, которые не используются:

F1/2 = F5/6 = 9,447 МГц        F1/4 = F5/7 = 9,447 МГц      F2/1 = F5/4 = 0,017 МГц

F2/3 = F4/5 = 9,447 МГц        F2/8 – F6/4 = 17,165 МГц    F3/2 – F4/1 = 27,65 МГц

F6/5 = F1/8= 1,85 МГц           F8/1 = 0,017 МГц                  F8/2 = 0,017 МГц

F8/4 = 9,447 МГц                    F8/5 = 9,447 МГц                  F4/6 = 0,017 МГц

F4/8 = 0,017 МГц                    F5/8 = 1,85 МГц                    F7/5 = 2,317 МГц

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

F1/2 = F5/6       F2/8 = F6/4     F3/2 = F4/1     F5/7 = F2/3     F7/5 = F1/8

F8/4                   F8/5                F5/8

Составим систему неравенств, с критерием оптимизации, учитывая новые изменения в связи с повторным частотным планированием и исключения незадействованных радиоканалов и маршрутов. В результате получим систему неравенства, представленную на рис. 3.

Рисунок 3. Система неравенств, с критерием неравенства, с учетом полученных маршрутов

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

F1/2 = F5/6 = 5 МГц

F5/7 = F2/3 = 9,946 МГц

F2/8 = F6/4 = 8,604 МГц

F3/2 = F4/1 = 55,67 МГц

F1/8 = F7/5 = 4,167 МГц

F8/4 =    9,946 МГц

F8/5 =    5 МГц

F5/8 = 1,667 МГц

Распределение полученных полос в выделенном частотном диапазоне частот согласно [5].

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

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

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

1. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. – М.: Мир, 1989. – 544 с., ил.
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 // Электронное научное специализированное издание.