Формирование топологии радиосети с размещением подвижных радиостанций при минимизации мощности излучения радиосигналов

Демичев Максим Сергеевич Инженер-конструктор по защите информации, Акционерное общество «Научно-производственное предприятие «Радиосвязь» 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 Другие публикации этого автора     Королев Евгений Михайлович старший преподаватель, Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнева 660037, Россия, Красноярский край, г. Красноярск, пр. Красноярский Рабочий, 31 Korolev Evgenii Mikhailovich Senior Lecturer, Department of Military Training Center, Reshetnev Siberian State University of Science and Technology 660037, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Pr. Krasnoyarskii Rabochii, 31 boxkem@mail.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 Другие публикации этого автора

Введение

Быстрое развитие беспроводных технологий, привело к появлению нового типа организации сетей, сетей типа mesh. Mesh узлы как правило располагаются в беспорядочном состоянии, их позиции могут быть как зафиксированными или же могут перемещаться в пространстве. Применение таких сетей нашло в системах умный дом, IoT(internet of thing), по этому принципу строятся сети стандарта zigbee, IEEE 802.15. Также организация таких сетей будет выгодна при организации взаимодействий между созвездием спутников или группы беспилотных дронов. Как правило, в таких сетях полагают, что часть или даже все беспроводные mesh узлы являются автономными, со своим внутренним источником электроэнергии, поэтому для таких сетей одним из основных требований к их функционированию является время автономной работы. В связи, с чем при развертывании беспроводной mesh сети, необходимо располагать mesh узлы таким образом, чтобы энергия, затрачиваемая на поддержание связи, была минимальной, но достаточной для поддержания соединения между парами mesh узлов. Одним из ограничений такой задачи является то, что часть mesh узлов должна быть зафиксирована в пространстве, а другая часть произвольно располагаться, так чтобы суммарная энергия излучения всех mesh узлов была минимальна.

Поставленная задача, очевидно, сводится к поиску некой древовидной топологии. Анализ существующих алгоритмов на графах для решения поставленной задачи показал, что алгоритмы по поиску минимальных остовных деревьев, работают только в том случае если позиции всех узлов считать фиксированными в связи, с чем они и не подходят. Алгоритмы построения дерева Штейнера ^{[1, c. 1813-1844]}, является наиболее подходящими алгоритмами, так как позволяет определить дополнительные узлы в графе, обеспечивая самую минимальную сумму длин всех расстояний между узлами, проблема заключается в том, что число дополнительных узлов, которое требуется для построения дерева Штейнера, может оказаться больше чем имеется подвижных mesh узлов, таким образом, данный алгоритм не полностью удовлетворяет требованиям поставленной задачи. Отмети также, что задача Штейнера относится к классу так называемых NP-полных задач, поэтому алгоритмы, дающие точные решения, как правило, не могут быть использованы в САПР из-за неприемлемой временной сложности ^{[3, c. 96]}. Также известно достаточно большое количество подходов к решению задачи о построении связной топологии сети, однако многие из известных результатов, как показано в работе ^{[4, c. 465-508]} не лишены недостатков. Данная статья является дополнением к статье ^{[5, c. 1-23]}, вместе с которой производится формирование топологии сети, а также распределение частотного ресурса оптимальным способом.

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

Пусть имеется N стационарных радиостанций (далее – СРС), где для каждой РС известны координаты, а также имеется M подвижных радиостанций ретрансляторов (далее – ПРС), причем M+2 ≤ N. Все РС имеют круговую диаграмму направленности. Необходимо оптимально распределить мощность излучения сигналов от СРС и ПРС, а также определить оптимальное месторасположение ПРС, где под оптимальностью понимается минимизация затраченной мощности для передатчиков. Требуется получить топологию радиосети, при которой передача от любой РС к другой может осуществляться посредством ретрансляции.

Ход работы

Данная статья описывает математическую модель, в которой не учитывается рельеф местности, диаграмма направленности каждой РС представляет собой окружность. Также предположим, что все РС расположены на плоскости в декартовой системе координат.

Основные этапы алгоритма:

1. Построение матрицы R;

2. Составление первичных соединений;

3. Нахождение координат для ПРС, а также распределение мощности излучения сигналов для ПРС.

4. Построение матрицы А.

5. Нахождение мощности излучения сигналов от рассчитанного радиуса действия.

Построение матрицы R

В матрице R описываются расстояния от СРС_i до СРС_j, а также расстояния от СРС_i до ПРС_k, с использованием координат, по формуле (1).

, где i, j – номера СРС (i, j∈ N^{[1, N]}), x_i, y_iи x_j, y_j – координаты СРС_i и СРС_j (или ПРС_k) соответственно. k – номера ПРС (k∈ ^{[1, M]}). На данном этапе рассчитываются только расстояния от СРС до СРС, расстояния от СРС до ПРС и от ПРС до ПРС рассчитываются в других этапах.

Результат записывается на пересечении строк i и столбцов j матрицы R. Шаблон матрицы представлен на рисунке 1. Ячейки главной диагонали не вычисляются и не заполняются.

Рисунок 1. Шаблон матрицы R

Составление первичных соединений

В результате составления первичной топологии формируется матрица V, в заголовках матрицы указывается номер СРС или ПРС, ячейки v_i, где i – номер СРС или ПРС (i ∈ ^{[1, N+M]}). Значение v_i соответствует максимальному назначенному расстоянию передачи для СРС_i или ПРС_i, до выполнения алгоритма матрица V заполняется нулями.

Введем понятие группа СРС – G_k, где k – номер группы. Элементы G_k состоят из номеров СРС таких, что осуществима передача от СРС_i до СРС_j, входящих в G_k. Формирование групп происходит в процессе работы алгоритма составление первичной топологии. До начала выполнения алгоритма количество групп равно количеству СРС.

Так как ПРС выполняет роль ретранслятора, то ее использование способно уменьшить потребляемую мощность при передаче от одной СРС к другой. Алгоритм построения первичной топологии, описанный ниже, основывается на соединении СРС с минимальными расстояниями согласно матрице R. Наилучшим вариантом соединения является объединение СРС с минимальными расстояниями в группы, и последующее соединение групп с использованием ПРС. В связи с этим возникает вопрос о необходимом количестве G_k, используемых для оптимального расположения ПРС. Наихудшим случаем является соединение одной ПРС только двух групп, следовательно необходимое количество групп равно M + 1.

Алгоритм составления первичных соединений:

1. В матрице R выбирается ячейка r_ij с наименьшим значением, где рассматривается соединение СРС (СРС_i и СРС_j), соответствующих индексу этой ячейки, при выполнении следующего условия: СРС_i и СРС_j находятся в группах G_x и G_y соответственно, где x ≠ y переходим в п. 2, иначе данное соединение игнорируется, ячейки r_ij и r_ji не учитываются при дальнейшей работе алгоритма, выполняем повторно п. 1.
2. В матрицу V на позиции i и j записывается значение ячейки r_ij и r_ji . Ячейки r_ij и r_ji не учитываются при дальнейшей работе алгоритма.
3. При соединении СРС_i и СРС_j находящихся в группах G_x и G_y соответственно, где x ≠ y, элементы данных групп объединяются в единую группу. При этом общее количество групп сокращается на единицу.

Нахождение координат для ПРС, а также распределение мощности излучения сигналов для ПРС

Введем матрицу GD, которая описывает минимальные расстояния от группы G_i до G_j, а также пара СРС, входящие в данные группы, которые соответствуют данным расстояниям. Заголовки матрицы формируются из номеров групп G_k, полученных после выполнения алгоритма составления первичной топологии, главная диагональ заполняется нулями.

Введем матрицу К, которая определяет отношения для расстояний от СРС, входящей в группу до ПРС, элементы матрицы рассчитываются по формуле (2, 3).

, где k_ij – элемент матрицы K, i,j – ребра маршрута, t_i – ближайшее расстояние от СРС до ПРС для ребра i, t_j – ближайшее расстояние от СРС до ПРС для ребра j, gd_i – расстояние ребра согласно матрице gd, В – количество ПРС, назначенных на ребро i. t_i рассчитывается по формуле (3).

С точки зрения затрачиваемой мощности оптимальное расположения ПРС между двумя СРС должно быть таким, чтобы ПРС находилась на одинаковом расстоянии от СРС. Это можно доказать следующим образом – пусть расстояние между двумя СРС равно x, при этом расстояние от одной из СРС до ПРС равно y, тогда расстояние от второй СРС до ПРС равно x – y. Исходя из формулы (5), затрачиваемая мощность пропорциональна квадрату расстояния, тогда:

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

Расположение s штук ПРС между двумя СРС должно быть таким, чтобы каждая ПРС находилась на одинаковом расстоянии от СРС и друг от друга. Исходя из предыдущего доказательства, данное расстояние будет иметь значение у = х / (s+1).

Матрица K предназначена для выявления ПРС, которые необходимо перераспределить с одних ребер другим. Таким образом, значение k_ij не должно превышать значения 2 для оптимального распределения ПРС между двумя СРС.

Введем, матрицу P, которая определяет принадлежность ПРС к соответствующему ребру маршрута. Матрица представлена в виде двух столбцов: первый содержит номера ПРС, второй – определенное ребро маршрута (соединения СРС и/или ПРС).

Алгоритм нахождения координат для ПРС, а также распределение мощности излучения сигналов для ПРС:

1. Составление матрицы GD. Заголовками матрицы являются номера групп G. Находим минимальное значение в матрице r_ij на пересечении строк, соответствующих СРС, входящих в группу G_i, со столбцами, соответствующих СРС, входящих в группу G_j, значение записываем в gd_ij, а также пары СРС, соответствующие записанным расстояниям. В случае, если минимальному значению соответствуют несколько пар СРС, тогда в соответствующей ячейке будет содержаться значение расстояния, а также пары СРС, соответствующие им. Добавляем в матрицу дополнительные столбцы, заголовки которых соответствуют номерам ПРС, ячейки которых остаются незаполненными.

2. Из матрицы GD формируем первичный маршрут между группами, где маршрут представлен в виде ребер: СРС_i– СРС_j, СРС_i– СРС_k, …, СРС_p– СРС_r, где i, j, i, k, p, r – номера СРС. Формирование маршрута осуществляется с помощью поиска минимумов в матрице GD, минимальные расстояния не рассматриваются повторно после внесения ребра в маршрут. Пусть первое минимальное расстояние найдено между группами G_iи G_j, тогда второе минимальное расстояние ищется на пересечении строк групп G_iи G_j, со столбцами, номера групп которых отличны от рассмотренных групп G_iи G_j. Пусть столбец, соответствующий второму минимальному расстоянию, соответствует группе G_k, тогда поиск третьего минимального расстояния будет осуществляться на пересечении строк групп G_i, G_jи G_k, со столбцами, номера групп которых отличны от рассмотренных групп G_i, G_jи G_k. Поиск других минимальных расстояний осуществляется аналогично. Построение маршрута заканчивается, когда количество ребер в маршруте равно M. Полученный маршрут зап