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

Демичев Максим Сергеевич Инженер-конструктор по защите информации, Акционерное общество «Научно-производственное предприятие «Радиосвязь» 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. Полученный маршрут записывается в список маршрутов MR.

3. На каждое ребро маршрута выделим по одной ПРС_d, где d – номер ПРС. В матрицу принадлежности P вписываем номер d и номера СРС. Координаты ПРС_dопределяются по формуле (4), где принадлежность ПРС какому либо ребру определяется по матрице P, и в матрицу V, добавляется максимальное назначенное расстояние передачи для ПРС_d.

4. Рассчитываем матрицу R для ячеек, содержащих в своих заголовках ПРС. Пересчитываем матрицу GD для внесенных ПРС. Расстояние от СРС до ПРС осуществляется по формуле (1), где x_m, y_mи x_k, y_k – координаты СРС_m и ПРС_kсоответственно. Область ПРС в матрице GD заполняется по столбцам, причем ячейки, соответствующие группам, ребро которых принадлежит ПРС по матрице P, не заполняются. Составляем вторичный маршрут по аналогии с п. 2, узлами которого помимо СРС рассматриваются и ПРС. Полученный маршрут дополняется в список маршрутов МR, причем маршруты, записанные ранее, сохраняются в списке.

5. Сравниваются последний mr и предпоследний mr-1 маршруты в списке МR, где mr – количество маршрутов в списке МR. Если ребро маршрута mr и маршрута mr-1 не совпадают, то в данное ребро маршрута mпереносится ПРС из ребра маршрута mr-1. В матрице принадлежности Pизменяются номера СРС для соответствующей ПРС, координаты ПРС определяются по формуле (4), где принадлежность ПРС какому либо ребру определяется по матрице P. При не совпадении, какого-либо из ребер маршрута mr и маршрута mr-1, п. 4 выполняется повторно. Если все ребра маршрута mr и маршрута mr-1 совпадают, то маршрут mr удаляется из списка МR, количество маршрутов становится равным n, и выполняем п. 6.

6. Рассчитаем матрицу K по формулам (2, 3), где заголовки матрицы K определяются по ребрам последнего маршрута. Обращение к матрице K и выполнение данного пункта осуществляется до тех пор, пока все значения ее элементов меньше 2 тогда переходим в п.7 . Находим максимальное значение, которое превышает значение 2, в матрице K – k_ij. Из ребра, соответствующего j, убираем ПРС (количество ПРС ребра j уменьшается на 1) и переносится в ребро, соответствующему i (количество ПРС ребра i увеличивается на 1). Данные изменения также вносятся в матрицу принадлежности P. В матрице K удаляется столбец j, пересчет значений матрицы осуществляется с учетом перераспределенных ПРС. Координаты ПРС_d определяются по формуле (4), где принадлежность ПРС какому либо ребру определяется по матрице P, и в матрицу V, добавляется максимальное назначенное расстояние передачи для ПРС_d:

6.1 Если от ПРС_d не исходит никаких ребер, то v_d=r_ij/(B_ij +1), где r_ij – расстояние между СРС_i и СРС_j, на ребре которых расположена ПРС_d, B_ij – количество ПРС, также расположенных на рассматриваемом ребре.

6.2 Если от ПРС_d исходит ребро, то v_d=r_dk/(B_dk +1), где r_dk – расстояние между ПРС_d и СРС_k, с которой соединяется ребром, B_dk – количество ПРС на ребре ПРС_d и СРС_k.

6.3 Если от ПРС_d исходит несколько ребер, то для каждого из них вычисляется значение v_d, как в п. 3.2, и выбирается наибольшее значение.

С известными координатами ПРС выполняем с п.4.

7. Все ПРС в конечном маршруте считаем СРС, которые дополняются в матрицу R. Дальности ПРС рассчитываются в соответствии с п. 6.

, где X_k, Y_k – координаты ПРС, X_j, X_i, Y_j, Y_i – координаты вершин ребра,k ∈ ^{[1, n]}, где n - число ПРС размещенных на ребре.

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

Матрица А, заполняется 0 и 1, где 1 показывает взаимосвязь между СРС_i и СРС_j, 0 – отсутствие взаимосвязи между СРС_i и СРС_j. Шаблон матрицы А аналогичен шаблону матрицы R.

Для СРС_i, где i ∈ ^{[1, N+M]}, в матрице V выполняется условие: если значение v_i ≥ r_ij (проверяется строка i в матрице R), при j ∈ ^{[1, N+M]}, то в матрице А в ячейку а_ij записывается 1.

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

Нахождение мощности излучения сигналов от рассчитанного радиуса действия выполняется по формуле (5), представленной на рисунке 4. Следует отметить, что мощность сигнала на входе радиоприемника и коэффициенты усиления являются регулируемыми параметрами за счет выбора антенн приема и передачи для каждой СРС на момент проектирования радиосети, получение длины волны передающей СРС рассчитывается в ^{[5, c. 1-23]}.

где Р_СРСi – мощность сигнала на выходе радиопередатчика СРС_i (ПРС_i), Р_СРСj – мощность сигнала на входе радиоприемника СРС_j (ПРС_j), G_СРСi – коэффициент усиления антенны радиопередатчика СРС_i (ПРС_i), G_СРСj – коэффициент усиления антенны радиоприемника СРС_j (ПРС_i), l - длина волны радиосигнала, v_i – назначенное расстояние из матрицы V.

Пример

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

Рисунок 2. Расположение СРС на координатной сетки

При решении примера, более детально рассмотрим этап «Нахождение координат для ПРС, а также распределение мощности передающих антенн для ПРС», так как он представляет набольшую сложность, остальные этапы представим в виде результатов.

Этап «Построение матрицы R», из координат, представленным из рисунка 2. Результат представлен на рисунке 3.

Рисунок 3. Матрица R, без заполнения области ПРС

После получения матрицы R, выполняем этап «Составления первичного соединения», где результатом является формирование групп G и составление матрицы V, результаты представлены на рисунке 4 и рисунке 5 соответственно.

Рисунок 4. Группа G

Рисунок 5. Матрица V

Этап «Нахождение координат для ПРС, а также распределение мощности передающих антенн для ПРС».

Согласно п. 1 алгоритма данного этапа, рассчитаем матрицу GD, в которой отображается кратчайшее расстояние между группами и задействованные на данных значениях расстояние СРС (ребро). Пересечения строк СРС и столбцы ПРС отставляем в матрице GD не заполненными, результат представлен на рисунке 6.

Рисунок 6. Матрица GD, без заполнения ПРС

П. 2. Найдем первичный маршрут, согласно алгоритму получим результат, представленный как:

СРС₉ – СРС₁₀, СРС₂– СРС₄, СРС₃ – СРС₇, СРС₁₃ – СРС₁₂. Полученный маршрут запишем в матрицу MR.

П. 3. Выделим ПРС на каждое ребро. Заполняем матрицу принадлежности P. Результат представлен на рисунке 7.

Рисунок 7. Матрица принадлежности Р

Рассчитаем координаты ПРС₁, согласно формуле (4), зная координаты для СРС ребра:

П.4. пересчитываем матрицу R и GD с учетом внесенных ПРС,результат представлен на рисунке 8 и 9 соответственно..

Рисунок 8. Матрица R, с заполненой областью ПРС

Рисунок 9. Матрица GD, с заполненой областью ПРС

А также составим вторичный маршрут по аналогии с п. 2. Результат представлен в виде:

СРС₉ – СРС₁₀, СРС₂– СРС₄, ПРС₂ – СРС₇, СРС₁₃ – СРС₁₂, который запишем в матрицу MR. Вид матрицы MR представлен на рисунке 10.

Рисунок 10. Список МR, не удовлетворяющий условию совпадения последнего и предпоследнего маршрута

П. 5. Сравниваем последний и предпоследний маршруты, видим, что ребра последнего и предпоследнего маршрута не совпадают, следовательно выполняем с п. 4 повторно.

После повторного выполнения п. 4 матрица GD не изменилась, а матрица MR представлена на рисунке 11.

Рисунок 11. Список МR, удовлетворяющий условию совпадения последнего и предпоследнего маршрута

Из рисунка 11 видим, что последний и предпоследний маршруты совпадают, следовательно переходим в п. 6, а последний маршрут (под номером 3) удаляем.

П. 6. Рассчитаем матрицу K по формулам (2, 3), результат представлен на рисунке 12.

Рисунок 12. Матрица К

Видим, что в матрице K имеются элементы, значения которых превышают 2. На пересечении строки СРС13-СРС12 и столбца СРС9-СРС10, располагается максимальное значение матрицы K, тогда с ребра СРС9-СРС10 переносим одну ПРС на ребро СРС13-СРС12, изменения в матрицу P, рассчитываем координаты ПРС в соответствии с формулой (4), далее выполняем с п. 4.

После выполнения некоторого количества итераций, значения в матрице K будут не превосходить 2, тогда переходим к выполнению п. 7. Все ПРС считаются стационарными, а матрицу R пересчитываем с учетом новых СРС и их координатами.

После завершения данного этапа будут сформированы матрицы: V, P, M – а также координаты ПРС и топология сети с связями между станциями, которые представлены на рисунках 13 – 17 соответственно.

Рисунок 13. Итоговая матрица V

Рисунок 14. Итоговая матрица P

Рисунок 15. Итоговый список MR

Рисунок 16. Итоговые координаты ПРС

Рисунок 17. Полученная топология

Этап «Построение матрицы А».

Результат построения матрицы А представлен на рисунке 18.

Рисунок 18. Матрица А

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

По условию задачи не были заданы: мощность сигнала на выходе радиопередатчика, мощность сигнала на входе радиоприемника, коэффициент усиления антенны радиопередатчика, коэффициент усиления антенны радиоприемника, а длина волны радиосигнала будет рассчитываться согласно ^{[5, c. 1-23]}. Поэтому формулу (5) можно представить как произведение данных параметров и коэффициента (4*пи*v_i)², который можно вычислить и сравнить для каждой рассмотренной антенны.

Вывод

Результатом работы алгоритма является формирование связной радиосети, с минимизацией передаваемой мощности сигнала, где для каждой радиостанции будет назначаться необходимая мощность излучения, а также определены координаты подвижных mesh узлов. Как отмечалось во введении, что данный алгоритм является дополнением к статье ^{[5, c. 1-23]}, где связующим элементом является формирование матрицы А. Стоит выделить, что этап данного алгоритма «Нахождение мощности излучения сигналов от рассчитанного радиуса действия» будет выполняться после выполнения алгоритма из статьи ^{[5, c. 1-23]}, так как согласно формуле (5), необходима длина волны, которую можно найти, зная частоту излучаемого сигнала. В численном примере не рассмотрен этап «Нахождение координат нераспределенных ПРС», так как нераспределенные ПРС отсутствуют. Поэтому переходим к этапу «Нахождение мощности излучения сигналов от рассчитанного радиуса действия». Для выполнения данного этапа необходима воспользоваться формулой 4, однако для расчета необходима длина радиоволны, которая рассчитывается в ^{[5, c. 1-23]}, где для расчета используется матрица А, полученная в данной работе. Остальные переменные используются исходя из типа антенны СРС.