Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

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

Демичев Максим Сергеевич

Инженер-конструктор по защите информации, Акционерное общество «Научно-производственное предприятие «Радиосвязь»

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
Другие публикации этого автора
 

 

DOI:

10.25136/2644-5522.2018.1.24983

Дата направления статьи в редакцию:

13-12-2017


Дата публикации:

10-01-2018


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


Ключевые слова:

Мощность излучаемого сигнала, Топология связной сети, Стационарная радиостанция, Подвижная радиостанция, Алгоритм, Координаты, Радиосеть, Передача данных, Диаграмма направленности, Декартова система координат

Abstract: The subject of the study is the formation of a radio network topology with placement of mobile radio stations, in which the total radiated signal power for radio stations will be minimized. The radiation power of signals for all radio stations and the coordinates for mobile radios are determined in the article, it is also assumed that the transmitting antennas of all radio stations have a circular pattern. To solve this problem, a mathematical model is constructed that has a number of assumptions that imply ideal conditions for the propagation of radio waves, as well as the location of radio stations in a Cartesian coordinate system. The development of the algorithm was carried out by an experimental-theoretical method, based on known facts of radio transmission and a mathematical solution of the Steiner problem for four and five vertices. The novelty of the study is the developed algorithm for determining the coordinates of mobile radio stations, as well as the radiation power of signals for stationary and mobile radios with a circular pattern of directionality. The result of the algorithm works is to determine the topology of the network and the range of operation of each radio station, which consumes the lowest radiation power of the transmitting antennas of radio stations.


Keywords:

Radiated signal power, Topology of a connected network, Stationary radio station, Mobile radio station, Algorithm, Coordinates, Radio network, Data transfer, Directional diagram, Cartesian coordinate system

Введение

Быстрое развитие беспроводных технологий, привело к появлению нового типа организации сетей, сетей типа 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).

_23122017_220542, где i, j – номера СРС (i, j N[1, N]), xi, yiи xj, yj – координаты СРСi и СРСj (или ПРСk) соответственно. k – номера ПРС (k∈ [1, M]). На данном этапе рассчитываются только расстояния от СРС до СРС, расстояния от СРС до ПРС и от ПРС до ПРС рассчитываются в других этапах.

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

_31122017_230707

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

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

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

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

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

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

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

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

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

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

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

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

_30122017_210409

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

_30122017_210432

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

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

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

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

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

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

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

4. Рассчитываем матрицу R для ячеек, содержащих в своих заголовках ПРС. Пересчитываем матрицу GD для внесенных ПРС. Расстояние от СРС до ПРС осуществляется по формуле (1), где xm, ymи xk, yk – координаты СРС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, в матрице Kkij. Из ребра, соответствующего j, убираем ПРС (количество ПРС ребра j уменьшается на 1) и переносится в ребро, соответствующему i (количество ПРС ребра i увеличивается на 1). Данные изменения также вносятся в матрицу принадлежности P. В матрице K удаляется столбец j, пересчет значений матрицы осуществляется с учетом перераспределенных ПРС. Координаты ПРСd определяются по формуле (4), где принадлежность ПРС какому либо ребру определяется по матрице P, и в матрицу V, добавляется максимальное назначенное расстояние передачи для ПРСd:

6.1 Если от ПРСd не исходит никаких ребер, то vd=rij/(Bij +1), где rij – расстояние между СРСi и СРСj, на ребре которых расположена ПРСd, Bij – количество ПРС, также расположенных на рассматриваемом ребре.

6.2 Если от ПРСd исходит ребро, то vd=rdk/(Bdk +1), где rdk – расстояние между ПРСd и СРСk, с которой соединяется ребром, Bdk – количество ПРС на ребре ПРСd и СРСk.

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

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

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

_30122017_210326, где Xk, Yk координаты ПРС, Xj, Xi, Yj, Yi – координаты вершин ребра,k [1, n], где n - число ПРС размещенных на ребре.

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

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

Для СРСi, где i [1, N+M], в матрице V выполняется условие: если значение vi ≥ rij (проверяется строка i в матрице R), при j [1, N+M], то в матрице А в ячейку аij записывается 1.

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

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

_30122017_215242

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

Пример

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

_31122017_110955

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

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

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

_31122017_214729

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

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

_31122017_124356

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

_31122017_174354

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

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

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

_31122017_213156

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

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

СРС9 – СРС10, СРС2– СРС4, СРС3 – СРС7, СРС13 – СРС12. Полученный маршрут запишем в матрицу MR.

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

_31122017_223845_02

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

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

_31122017_214044

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

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

_31122017_232103_01

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

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

СРС9 – СРС10, СРС2– СРС4, ПРС2 – СРС7, СРС13 – СРС12, который запишем в матрицу MR. Вид матрицы MR представлен на рисунке 10.

_01012018_094354

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

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

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

_01012018_094410

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

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

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

_01012018_101548

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

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

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

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

_01012018_124623

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

_01012018_124712

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

_01012018_094410_01

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

_01012018_124610

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

_31122017_1109551

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

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

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

_01012018_130656_01

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

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

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

Вывод

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

Библиография
1. А. О. Иванов, А. А. Тужилин, Задача Штейнера на плоскости или плоские минимальные сети, Матем. сб., 1991, том 182, номер 12, с. 1813–1844.
2. Препарата Ф., Шеймос М. Вычислительна геометрия: Введение. М.: Мир, 1989, с. 478.
3. Н.В. Рыженко. САПР. Задача построения дерева Штейнера для этапа глобальной трассировки, с. 96-105 .
4. Кормен Т. Алгоритмы: построение и анализ. М.: МЦНМО, 2001, с. 958.
5. Демичев М.С., Гаипов К.Э., Демичева А.А., Нарожный А.И. Радиочастотное планирование радиосети с исключением интерференции радиоволн // Кибернетика и программирование. — 2017. - № 4, с.1-23.
6. Н. В. Рыженко. Алгоритм построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. Труды ИМВС РАН, 2002, с. 48-61.
7. А. О. Иванов, А. А. Тужилин, “Геометрия минимальных сетей и одномерная проблема Плато”, УМН, 47:2(284) (1992), с. 53–115.
References
1. A. O. Ivanov, A. A. Tuzhilin, Zadacha Shteinera na ploskosti ili ploskie minimal'nye seti, Matem. sb., 1991, tom 182, nomer 12, s. 1813–1844.
2. Preparata F., Sheimos M. Vychislitel'na geometriya: Vvedenie. M.: Mir, 1989, s. 478.
3. N.V. Ryzhenko. SAPR. Zadacha postroeniya dereva Shteinera dlya etapa global'noi trassirovki, s. 96-105 .
4. Kormen T. Algoritmy: postroenie i analiz. M.: MTsNMO, 2001, s. 958.
5. Demichev M.S., Gaipov K.E., Demicheva A.A., Narozhnyi A.I. Radiochastotnoe planirovanie radioseti s isklyucheniem interferentsii radiovoln // Kibernetika i programmirovanie. — 2017. - № 4, s.1-23.
6. N. V. Ryzhenko. Algoritm postroeniya minimal'nykh svyazyvayushchikh derev'ev s dopolnitel'nymi vershinami (derev'ev Shteinera) dlya sluchaya pryamougol'noi metriki. Trudy IMVS RAN, 2002, s. 48-61.
7. A. O. Ivanov, A. A. Tuzhilin, “Geometriya minimal'nykh setei i odnomernaya problema Plato”, UMN, 47:2(284) (1992), s. 53–115.