Программные продукты и системы

Введение. Методы оптимизации лежат в основе подавляющего большинства алгоритмов управления, широко используются при проектировании архитектур различных технических и социальных систем [1]. Если пространство поиска решений непрерывно, для нахождения оптимальной стратегии используют методы дифференциальных и интегральных исчислений, аналоговые вычисления. В случае дискретной модели пространства для решения  задач используют методы дискретной оптимизации. К подобным задачам сводятся многие практические приложения. Для них существуют алгоритмы, позволяющие находить приемлемое по точности решение за ограниченное время. Однако если необходимо получить точное решение, выбор алгоритмов для его поиска ограничен и сводится к методу полного перебора (Brute Force Algorithm, BFA)  и его вариациям в виде метода ветвей и границ (Branch and Bound, BB) [2]. Эти алгоритмы имеют высокую вычислительную сложность, что ограничивает их практическое применение. В работе [3] на нескольких примерах  показано, что учет особенностей решаемой задачи позволяет существенно сократить пространство поиска решения и, следовательно, вычислительную сложность алгоритма без потери точности решения. В данной работе рассматривается возможность использования BFA для решения еще одной практической задачи – поиска варианта оптимального размещения антенн, которая может быть сведена к задаче дискретной оптимизации.

Цель проводимых исследований заключается в оценке эффективности методов снижения вычислительной сложности BFA. Рассматриваются возможные подходы к ускорению вычисления критериальной функции применительно к задаче нахождения оптимального варианта размещения всенаправленных антенн.

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

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

Введем следующие обозначения:

П – пространство поиска решения или область размещения антенн;

A = {Ai}, i = 1, N – множество подлежащих размещению всенаправленных антенн;

Si = π·R2i – площадь зоны покрытия i-й антенны, где Ri – дальность действия антенны;

 – площадь пересечения зоны покрытия i-й антенны и области размещения антенн;

 – площадь пересечения зоны покрытия i-й антенны со всеми остальными антеннами.

Критериальные функции, определяющие цель оптимизации:

 – максимизация площади покрытия области поиска решения заданным набором антенн;

 – минимизация площади зон покрытия антенн, выходящих за границу области поиска решения;

 – минимизация площади пересечения зон покрытия антенн;

F3 = 0 – зоны покрытия антенн не должны иметь пересечения, предельный случай критерия F3;

F2 = 0 – области зон покрытия антенн не должны выходить за границу области поиска решения, предельный случай критерия F2.

На рисунке 1 показаны несколько примеров, иллюстрирующих выполнение описанных условий.

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

Обзор исследований

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

В статье [4] описан алгоритм нахождения оптимального размещения дискообразных объ- ектов для максимизации зоны покрытия. Показано, что использование имитационного отжига в контексте максимизации зоны покрытия может быть применимо для решения сложных задач пространственной оптимизации, а параллельный вариант алгоритма обеспечивает и сокращение времени вычислений.

В работе [5] представлен алгоритм, направленный на оптимизацию размещения беспроводных датчиков с различными диапазонами передачи для достижения максимально возможного охвата в пределах региона наблюдения. Авторы реализуют задачу максимизации зоны покрытия в WSNs с использованием генетического алгоритма, который модифицирован для этой проблемы и снижения времени выполнения.

Еще один подход описан в работе [6]. Авторы предлагают решать проблему позиционирования антенн в сотовых сетях с помощью эвристического подхода, основанного на алгоритме табуированного поиска, который, кроме запретов, использует целевые критерии и диверсификацию для снижения сложности проблемы. Показано, что высокая вычислительная сложность и ресурсоемкость алгоритма определяются большим количеством рассматриваемых поисковых комбинаций и требованиями  к памяти.

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

Возможность использования методов математического моделирования для оптимизации покрытия в беспроводных сетях 5G обсуждается в статье [8]. Анализ сложности задачи позволил авторам отнести ее к классу NP-полных, что определяет и выбор алгоритмических подходов к решению.

В работе [9] обсуждается комбинированный эвристический алгоритм для оптимизации зоны покрытия WSNs. Описаны оригинальный алгоритм и его авторская модификация, приводятся экспериментальные результаты, демонстрирующие эффективность предложенного метода для оптимизации параметров WSNs.

Анализ и сравнение различных алгоритмов размещения антенн представлен в статье [10]. Отмечается, что размещение антенн является важнейшим этапом в процессе проектирования сотовых сетей. Эта задача включает в себя принятие решений о нахождении мест установки антенн, а также их типах и количестве для каждой вышки. Классические алгоритмы дискретной оптимизации, обладающие высокой сложностью, применимы только для ограниченного числа антенн, поэтому авторы предлагают использовать генетический алгоритм. Резуль-таты вычислений с применением реальных наборов данных свидетельствуют об эффек- тивности предложенного эвристического подхода.

В работе [11] обсуждается фундаментальная проблема назначения диапазона в WSNs  и ставится цель минимизировать стоимость покрытия за счет оптимизации радиусов обнаружения и связи для сенсорных узлов. Такая оптимизация необходима для сокращения затрат времени и энергии на передачу показаний датчиков, что в итоге повышает эффективность  и быстродействие WSNs.

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

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

Всенаправленные антенны являются важным компонентом систем радиосвязи для приема и передачи сигналов во всех направле-ниях. Такая схема приема позволяет устранять мертвые зоны для приложений, требующих равномерного покрытия зоны приема [12].  Их проще устанавливать благодаря 360-градусной диаграмме направленности и отсутствию необходимости в точном позиционировании.  В работе [13] выделены следующие области применения всенаправленных антенн: сотовая связь, мобильные устройства, беспроводные телефоны, беспроводные компьютерные сети, антенны радиовещания, точки беспроводного доступа, базовые станции полиции и такси, связь с самолетами, интернет вещей (IoT). Всенаправленные антенны часто используются и в беспроводных сенсорных сетях (WSN).

В работе [14] уже были определены универсальные способы снижения вычислительной сложности BFA. К ним относятся уменьшение пространства поиска решения, сокращение времени расчета критериальной функции, использование эффективных методов генерации вариантов решения, распараллеливание.

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

1.    Уменьшение пространства поиска. Метод BFA предполагает, что должны быть исследованы все возможные варианты расположения антенн на заданной территории [15].  В случае дискретного пространства число позиций, которые могут занимать антенны, задается количеством шагов сетки Mx и My по осям X и Y соответственно. Если Mx = My = M, то количество положений антенны равно K = M2.  Тогда общее количество вариантов решения для N антенн составит KN. Если используется критерий F2 = 0, то при размере сетки меньше радиуса антенны крайние позиции можно исключить (рис. 2).

Тогда количество положений антенны уменьшится и составит K1 = (M – 2)2. Разница будет K – K1 = M2 – (M – 2)2 = 4(M – 1). При этом ускорение для N элементов определяется как .

2.    Сокращение времени расчета критериальной функции. В рассматриваемой задаче выполнение критерия F3 = 0 предполагает, что расстояние между центрами расположения пары антенн будет больше суммы их радиусов покрытия. Пусть первая антенна A1 расположена в позиции с координатами (x1, y1), а вторая A2 – в позиции (x2, y2). Тогда для проверки выполнимости критерия необходимо проверить условие:

+.             (1)

Отметим, что координаты расположения антенны необходимо предварительно вычислить, используя номер занимаемой ею позиции. Реализация алгоритма, когда для вычисления критерия используется выражение (1), обозначена в таблицах как Pcalc.

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

(R1 + R2) ≤ D1,2,                                       (2)

где

Вычисленные значения расстояний Di,j между центрами всех возможных мест расположения антенн формируют матрицу, и для проверки условия (2) достаточно взять нужное значение из памяти. Реализация алгоритма,  в котором для вычисления критерия используются табличные значения (2), обозначена  как Ptabl.

3.    Использование эффективных методов генерации вариантов решения. В исследова- нии [16] показано, что генерация вариантов размещения с помощью метода лексикографических перестановок обеспечивает ускорение решения задачи.

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

Тестовая задача

Условия тестовых задач приведены в таблице 1, характеристики антенн – в таблице 2. Общее число размещаемых антенн N = 6, пространство поиска решения или область размещения антенн П представляет собой квадрат размером 9×9 км, шаг сетки 1×1 км. В первой задаче размещаются антенны трех разных типов, а во второй все антенны одинаковые.

Целью оптимизации является максимизация покрытия F1→ max при условии равенства критериев F2 и F3 нулю.

Таблица 1

Условия задач

Table 1

Task conditions

Таблица 2

Параметры всенаправленных антенн

Table 2

Parameters of omnidirectional antennas

Решением задачи является N-мерный вектор P = {Pi}, i = 1,6, элементы которого определяют номер позиции, которую занимает соответствующая антенна.

Проводимые исследования направлены на оценку эффекта, который дает сокращение времени вычисления критериального выражения. Для этого сравним время решения задачи для двух реализаций алгоритма – Pcalc и Ptabl. Теоретический анализ сложности показывает, что реализация Ptabl должна работать быстрее.

Программная реализация алгоритма

Основные процедуры алгоритма полного перебора вариантов применительно к задаче нахождения максимального покрытия включают следующие этапы.

1. Задание параметров пространства поиска П.

2. Чтение матриц описания антенн A = {Ai}.

3. Расчет матрицы расстояний D = {Di,j}.

4. Генерация варианта решения P = {Pi}.

5. Проверка выполнимости критериев и запись рекорда.

6. Проверка завершения поиска, если нет,  то повтор п. 4.

7. Завершение работы.

В параллельной реализации алгоритма процедуры 4–6 исполняются на разных ядрах. Для этого используется технология многопоточ- ных вычислений, а распределение вычислений между потоками производится с помощью функции omp parallel for из библиотеки OpenMP (https://hpc-tutorials.llnl.gov/openmp/). При этом каждый поток формирует свой массив найденных локальных оптимумов, а глобальный оптимум будет найден после объединения всех локальных массивов. Такой подход исключает зависимость по данным между потоками и минимизирует взаимодействие потоков.

Результаты эксперимента

Для оценки эффективности замены вычислений на использование табличных значений при проверке выполнимости критерия проведены вычислительные эксперименты.

В экспериментах использован компьютер  с процессором Intel Xeon Processor E5-2630 v2 с 12 физическими ядрами, работающими на частоте 2,6 ГГц. Запуск приложения на одном ядре соответствовал последовательному варианту программы. Для параллельного приложения использованы все 12 физических ядер без режима гипертрединга. Программирование проведено в среде разработки Visual Studio 2019 на языке С++ с использованием библиотеки OpenMP.

Результаты работы последовательного приложения представлены в таблице 3.

Таблица 3

Сокращение времени проверки  выполнимости критерия F3 (задача 1)

Table 3

Reducing time for verifying the feasibility  of criterion F3 (task 1)

Результаты подтверждают эффективность применения табличных значений для проверки выполнимости критерия. Табличный вариант обеспечивает значительное ускорение вычислений:

Acc = T_calc/T_tabl = 19012,4/1100,45 = 17,28.

Оба варианта программы находят все 38 016 возможных вариантов решения задачи. Несколько решений приведены в таблице 4.

Один из представленных вариантов (выделен цветом в таблице) показан на рисунке 3.

На следующем этапе исследований была проверена эффективность табличного варианта проверки выполнимости критерия и при парал- лельной реализации алгоритма. Отметим, что для достижения максимального ускорения  вычислений в многопоточном приложении все ядра процессора должны быть загружены одинаково. Это условие выполнимо, если количе- ство итераций кратно числу инициируемых потоков, а в данном случае – числу физических ядер процессора. В противном случае на последнем этапе не все ядра будут участвовать в вычислениях. Поясним это на небольшом примере. Пусть процессор имеет 12 ядер, а количество итераций внешнего цикла for равно 122. Тогда на первом этапе все 12 ядер выполнят по 10 итераций, а на втором будут работать только 2 ядра. В результате максимально ожидаемое ускорение, которое мы сможем получить, уменьшится с 12 до 11,1. По мере увеличения сложности задачи влияние этого фактора на эффективность вычислений будет уменьшаться. В реализованном приложении выравнивание нагрузки ядер производится в генераторе вариантов решения.

Время работы параллельного приложения при решении задач 1 и 2 показано в таблице 5.

Проанализируем полученные в экспериментах результаты.

1.    Точность решения. Использование предварительно сформированной таблицы расстояний сохраняет основное достоинство BFA – нахождение точного решения задачи.

2.    Сокращение времени решения задачи. Табличный метод обеспечивает значимое ускорение вычислений. В рассмотренной задаче удалось более чем в 17 раз сократить время вычислений. Следует отметить, что размерность матрицы расстояний (N2) позволяет кешировать ее в памяти каждого ядра. Матрица {Di,j} симметрична относительно главной диагонали, что дает возможность хранить в памяти только одну ее половину, но это усложняет процесс чтения данных. Следует заметить, что эффективность табличного хранения данных будет зависеть от вида критериальной функции. Полученное значение ускорения справедливо  в отношении критерия F3 = 0.

3.    Масштабируемость. Эксперименты с параллельной реализацией алгоритма позволили сделать вывод о достаточно хорошей масштабируемости приложения. Однако следует отметить, что в данном случае не исследовалась возможность распараллеливания процедуры вычисления критерия, поскольку для табличной реализации это не имеет смысла.  Эксперименты подтвердили только функциональность табличной реализации и в параллельной версии алгоритма.

Причина ограниченности полученных ускорений связана с другими компонентами прило- жения, а не с табличным методом вычисления критерия. В первую очередь, это относится  к используемому для генерации вариантов  методу лексикографических перестановок. Эффективно устраняя необходимость проверки получаемого вектора, он не позволяет сделать нагрузку ядер одинаковой. Деградация ускорения наблюдается при числе потоков более 8. Метод, используемый для ограничения размерности пространства поиска, не ограничивает масштабируемость. Параллельная реализация алгоритма с табличным методом вычисления критерия обеспечила значительное ускорение вычислений: Acc = 17,28×6,29 = 108,69.

Выводы

Использование различных подходов к снижению вычислительной сложности отдельных этапов алгоритма полного перебора вариан- тов позволяет значительно расширить границы его применимости при решении практических задач. Низкие требования к межузловому взаимодействию дают возможность реализации BFA не только на суперкомпьютерах, но  и в распределенной среде.

В дальнейших работах планируется исследование эффективности табличного метода  и для других задач дискретной оптимизации.

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

1.   Zou Y., Zhan Q., Xiang K. A comprehensive method for optimizing the design of a regular architectural space to improve building performance. Energy Reports, 2021, vol. 7, pp. 981–996. doi: 10.1016/j.egyr.2021.01.097.

2.   Тайк А.М., Лупин С.А., Кхаинг М.Т. Методы повышения эффективности алгоритма полного перебора  на примере решения задачи о неограниченном ранце // INJOIT. 2023. Т. 11. № 5. С. 41–46.

3.   Lupin S., Thike A.M., Tun H. Comparison the various criteria in wireless network topology optimization task. Proc. OPTIMA-2017, 2017, pp. 370–377.

4.   Coll N., Fort M., Saus M. Coverage area maximization with parallel simulated annealing. Expert Systems with Applications, 2022, vol. 202, art. 117185. doi: 10.1016/j.eswa.2022.117185.

5.   Hanh N.T., Binh T.T.H., Hoai N.X., Palaniswami M.S. An efficient genetic algorithm for maximizing area coverage in wireless sensor networks. Information Sci., 2019, vol. 488, pp. 58–75. doi: 10.1016/j.ins.2019.02.059.

6.   Benmezal L., Benhamou B., Boughaci D. Evolutionary Iterated Local Search meta-heuristic for the antenna positioning problem in cellular networks. Computational Intelligence, 2022, vol. 38, no. 3, pp. 1183–1214. doi: 10.1111/ coin.12454.

7.   Parnianifard A., Mumtaz S., Chaudhary S., Imran M.A., Wuttisittikulkij L. A data driven approach in less expensive robust transmitting coverage and power optimization. Sci. Reports, 2022, vol. 12, art. 17725. doi: 10.1038/s41598-022-21490-z.

8.   Seda P., Seda M., Hosek J. On mathematical modelling of automated coverage optimization in wireless 5G and beyond deployments. Applied Sci., 2020, vol. 10, no. 24, art. 8853. doi: 10.3390/app10248853.

9.   Zhu F., Wang W. A coverage optimization method for WSNs based on the improved weed algorithm. Sensors, 2021, vol. 21, no. 17, art. 5869. doi: 10.3390/s21175869.

10. Calles-Esteban F., Olmedo A.A., Hellín C.J. et al. Optimizing antenna positioning for enhanced wireless coverage: A genetic algorithm approach. Sensors, 2024, vol. 24, no. 7, art. 2165. doi: 10.3390/s24072165.

11. Das S.K., Kapelko R. On the range assignment in wireless sensor networks for minimizing the coverage-connectivity cost. ACM TOSN, 2021, vol. 17, no. 4, art. 46, pp. 1–48. doi: 10.1145/3457408.

12. Yang C., Huo X., Wang X., Yang B., Zhang G. Design of an omnidirectional antenna with a compact size.  Proc. IRC, 2019, vol. 2019, no. 19, pp. 6268–6271. doi: 10.1049/joe.2019.0254.

13. Qing X., Ning C.Z. Omnidirectional antennas. Handbook of Antenna Technologies, 2016, pp. 1415–1478. doi: 10. 1007/978-981-4560-44-3_52.

14. Ай Мин Тайк, Лупин С.А., Федяшин Д.А. Использование библиотеки MPI для параллельной реализации алгоритма полного перебора вариантов // Программные продукты и системы. 2023. Т. 36. № 4. С. 607–614.  doi: 10.15827/0236-235X.144.607-614.

15. Liu Y., Jian Y., Sivakumar R., Blough D.M. Maximizing line-of-sight coverage for mmWave wireless LANs with multiple access points. IEEE/ACM Transactions on Networking, 2022, vol. 30, no. 2, pp. 698–716. doi: 10.1109/TNET. 2021.3122378.

16. Лупин С.А., Ай Мин Тайк. Сравнение методов перестановки с двумя типами структур данных // Международный научно-исследовательский журнал. 2023. № 9. C. 1–5.

References

1. Zou, Y., Zhan, Q., Xiang, K. (2021) ‘A comprehensive method for optimizing the design of a regular architectural space to improve building performance’, Energy Reports, 7, pp. 981–996. doi: 10.1016/j.egyr.2021.01.097.

2. Thike, A.M., Lupin, S., Khaing, M.T. (2023) ‘Methods for improving the efficiency of Brute-force algorithm by the example of solving an Unbounded Knapsack Problem’, INJOIT, 11(5), pp. 41–46 (in Russ.).

3. Lupin, S., Thike, A.M., Tun, H. (2017) ‘Comparison the various criteria in wireless network topology optimization task’, Proc. OPTIMA-2017, pp. 370–377.

4. Coll, N., Fort, M., Saus, M. (2022) ‘Coverage area maximization with parallel simulated annealing’, Expert Systems with Applications, 202, art. 117185. doi: 10.1016/j.eswa.2022.117185.

5. Hanh, N.T., Binh, T.T.H., Hoai, N.X., Palaniswami, M.S. (2019) ‘An efficient genetic algorithm for maximizing area coverage in wireless sensor networks’, Information Sci., 488, pp. 58–75. doi: 10.1016/j.ins.2019.02.059.

6. Benmezal, L., Benhamou, B., Boughaci, D. (2022) ‘Evolutionary Iterated Local Search meta-heuristic for the an-tenna positioning problem in cellular networks’, Computational Intelligence, 38(3), pp. 1183–1214. doi: 10.1111/coin.12454.

7. Parnianifard, A., Mumtaz, S., Chaudhary, S., Imran, M.A., Wuttisittikulkij, L. (2022) ‘A data driven approach in less expensive robust transmitting coverage and power optimization’, Sci. Reports, 12, art. 17725. doi: 10.1038/s41598-022-21490-z.

8. Seda, P., Seda, M., Hosek, J. (2020) ‘On mathematical modelling of automated coverage optimization in wireless 5G and beyond deployments’, Applied Sci., 10(24), art. 8853. doi: 10.3390/app10248853.

9. Zhu, F., Wang, W. (2021) ‘A coverage optimization method for WSNs based on the improved weed algorithm’, Sensors, 21(17), art. 5869. doi: 10.3390/s21175869.

10. Calles-Esteban, F., Olmedo, A.A., Hellín, C.J. et al. (2024) ‘Optimizing antenna positioning for enhanced wireless coverage: A genetic algorithm approach’, Sensors, 24(7), art. 2165. doi: 10.3390/s24072165.

11. Das, S.K., Kapelko, R. (2021) ‘On the range assignment in wireless sensor networks for minimizing the coverage-connectivity cost’, ACM TOSN, 17(4), art. 46, pp. 1–48. doi: 10.1145/3457408.

12. Yang, C., Huo, X., Wang, X., Yang, B., Zhang, G. (2019) ‘Design of an omnidirectional antenna with a compact size’, Proc. IRC, 2019(19), pp. 6268–6271. doi: 10.1049/joe.2019.0254.

13. Qing, X., Ning, C.Z. (2016) ‘Omnidirectional antennas’, Handbook of Antenna Technologies, pp. 1415–1478. doi: 10.1007/978-981-4560-44-3_52.

14. Aye Min Thike, Lupin, S.A., Fedyashin, D.A. (2023) ‘Using MPI library for parallel implementation of a brute-force algorithm’, Software & Systems, 36(4), pp. 607–614 (in Russ.). doi: 10.15827/0236-235X.144.607-614.

15. Liu, Y., Jian, Y., Sivakumar, R., Blough, D.M. (2022) ‘Maximizing line-of-sight coverage for mmWave wireless LANs with multiple access points’, IEEE/ACM Transactions on Networking, 30(2), pp. 698–716. doi: 10.1109/TNET. 2021.3122378.

16. Lupin, S.A., Aye Min Thike (2023) ‘Comparison of permutation methods with two types of data structures’, Int. Research J., (9), pp. 1–5.