Application of genetic algorithm to design the structure of an optimal wireless sensor network on a 3D building model

全文:

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

Для решения задачи оптимальной расстановки хабов комбинируется радиоволновая модель – дополненная модель Мотли-Кинана [2], которая учитывает затухание сигнала в стенах и межэтажных перекрытиях, и оптимизационный метод – классический генетический алгоритм [3]. Генетические алгоритмы относятся к стохастическим методам, имитирующим процессы, происходящие в природе, и широко применяются для решения задач оптимизации [4], в том числе при проектировании БСС [5-9]. Хотя полученное с их помощью решение может быть квазиоптимальным, но при большом объеме входных данных они имеют существенно меньшую вычислительную сложность, чем детерминированные методы. Например, в работе [8] генетический алгоритм применялся для структурной оптимизации БСС с целью обеспечения надежности в условиях случайных отказов узлов. В работе [9] с помощью генетического алгоритма решается задача покрытия в коммутационном поле действия интернета вещей и учитываются препятствия на рассматриваемой территории. Задача оптимизации решается для двумерного пространства, хотя и предлагается расширение для трехмерного.

2. Постановки задачи оптимизации. В предыдущей работе была поставлена задача оптимизации для оптимального размещения связующих узлов (хабов) в БСС [1]. Задача оптимизации заключается в оптимальной расстановке хабов на трехмерной модели здания с учётом максимально возможного уровня мощности сигнала и минимально возможных затрат на оборудование и коммуникации. В настоящей работе задача оптимизации решается в модифицированной постановке (уровень мощности сигнала рассчитывается во всем здании, а не только в контрольных точках, как в предыдущей постановке):

$f_1={\sum }_{i=1}^{Np}RS{S}_i\to \max , f_2={\sum }_{i=1}^{Np}(C_i+H_i)x_i\to \min$, (1)

здесь N_p – количество клеток, на которое разбивается исследуемое здание, RSS_i – уровень мощности сигнала в i-ой клетке, C_i, H_i – стоимость коммуникаций и оборудования соответственно, булевый вектор x_i = {0, 1}, где 1 – хаб установлен в i-ой клетке, 0 – нет.

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

$F\left(x\right)=\sum _{i=1}^K{\omega }_i{f}_i\left(x\right), {\omega }_i\in \left[0; 1\right], \sum _{i=1}^K{\omega }_i=1$.

где f_i (x) – целевые функции, ω_i – соответствующие веса, K – количество целевых функций.

Для согласования оптимумов в целевой функции f₂ стоимость хабов и коммуникаций была взята отрицательной:

$\overline{f_2}=\sum _{i=1}^{N_p}\left(\overline{C_i}+\overline{H_i}\right)x_i\to \max , \overline{C_i}=-C_i, \overline{H_i}=-H_i$

Таким образом, задача многокритериальной оптимизации имеет вид:

${\omega }_1{f}_1+{\omega }_2\overline{f_2}\to \max$, (2)

где веса ω₁, ω₂ выбираются в зависимости от приоритизации целевых функций.

3. Реализация генетического алгоритма. Для реализации генетического алгоритма здание научного института было разбито на клетки. Каждая клетка – это куб размером 3000 × 3000 × 3000 мм. Всего получилось 484 клетки. На рис. 1 приведен пример разбиения этажа здания на клетки.

 

Рис. 1. Разбиение на клетки первого этажа здания научного института

 

В качестве хромосомы выбран булевый вектор x_i, который описывает расстановку хабов во всём здании. Каждый ген в хромосоме принимает значения 0 или 1 в зависимости от того, установлен хаб в рассматриваемой клетке или нет.

Генетический алгоритм представляет собой имитацию эволюционного процесса (рис. 2) и включает следующие этапы: отбор, скрещивание и мутацию [3].

 

Рис. 2. Схема генетического алгоритма

 

В нашем случае в качестве метода отбора выбран турнирный отбор, метод k-скрещивания и мутация в виде инвертирования бита. Приспосабливаемость для каждого индивидуума вычисляется, как сумма двух целевых функций с соответствующими весами по формуле (2). Условием окончания работы ГА является прохождение заданного количества поколений, после которого функция приспосабливаемости выходит на плато. Для проектирования структуры оптимальной БСС на основе генетического алгоритма была разработана программа на языке Python [10]. На вход программы подается конфигурация здания, чтобы учесть наличие стен и перекрытий этажей.

Проведена серия модельных расчетов для трёх этажей одного крыла здания научного института. В ходе работы программы варьировались параметры расчета, такие, как размер популяции, количество поколений, вероятность мутации хромосомы и гена, вероятность и количество точек при k-скрещивании. Для того, чтобы оптимизировать количество хабов в рассматриваемом здании, была проведена серия расчетов и выбраны следующие веса для целевых функций: 0,8 для стоимости оборудования и коммуникаций; 0,2 для уровня мощности сигнала. В таблице 1 приведены оптимальные параметры, при которых были получены представленные в настоящей работе результаты.

 

Таблица 1. Параметры расчета для генетического алгоритма

Затухание в стенах	–15 дБм
Затухание в перекрытиях этажей	–20 дБм
Затухание в несущих стенах	–30 дБм
Длина хромосомы	108
Количество поколений	50
Размер популяции	150
Вероятность скрещивания	0,5
Вероятность мутации хромосомы	0,1
Вероятность мутации гена	1/108
RSS	0,2

 

По результатам работы генетического алгоритма были получены варианты оптимальной расстановки хабов для БСС. На рис. 3 представлена схема оптимальной расстановки трех хабов и тепловая карта уровней мощности сигнала в каждой клетке.

 

Рис. 3. Схема оптимального размещения трех хабов. Слева – план здания, зеленым обозначены места установки хабов. Справа – тепловая карта уровней мощности сигнала

 

При таком количестве хабов и их расстановки достигается практически полная зона покрытия, но при этом имеются несколько зон со слабым уровнем сигнала (≤ –100 дБм), что является недостаточным для связи с сенсорными устройствами. Для решения этой проблемы в программу было добавлено ограничение на минимальный уровень мощности сигнала (≥ –100 дБм) для всей рассматриваемой зоны покрытия в здании. Как следствие введенного ограничения, увеличилось количество хабов. На рис. 4 представлена схема оптимальной расстановки шести хабов и тепловая карта уровней мощности сигнала в каждой клетке. При анализе тепловой карты видно, что уровень мощности сигнала во всей области покрытия не менее –95 дБм.

 

Рис. 4. Схема оптимального размещения шести хабов. Слева – план здания, зеленым обозначены места установки хабов. Справа – тепловая карта уровней мощности сигнала

 

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

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

作者简介

Anatoly Sirotinin

Institute of Computational Modeling of the Siberian Branch of RAS

编辑信件的主要联系方式.
Email: slitch@icm.krasn.ru
SPIN 代码: 9617-6083

Postgraduate Student

俄罗斯联邦, Bldg. 44, 50, Akademgorodok, Krasnoyarsk, 660036

Olga Volodko

Institute of Computational Modeling of the Siberian Branch of RAS

Email: osv@icm.krasn.ru
ORCID iD: 0000-0002-0580-9103
SPIN 代码: 8080-9331

Candidate of Physical and Mathematical Sciences

俄罗斯联邦, Bldg. 44, 50, Akademgorodok, Krasnoyarsk, 660036

参考

补充文件