ЗАДАЧА ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ ЗАДАННОГО МНОЖЕСТВА БАЗОВЫХ СТАНЦИЙ БЕСПРОВОДНОЙ СЕТИ СВЯЗИ С ЛИНЕЙНОЙ ТОПОЛОГИЕЙ

摘要

В настоящее время в промышленных системах сбора информации с контролируемой территории все большее распространение получают беспроводные сети широкополосной связи. Существенное значение для эффективного проектирования таких сетей имеет выбор оптимального размещения заданного множества базовых станций, обладающих различными характеристиками, позволяющий осуществить покрытие максимальной ло размеру территории при выполнении технологических требований. В статье рассматривается актуальный специальный случай задачи размещения базовых станций беспроводной сети связи для контроля линейной (одномерной) территории. В нефтегазовой отрасли примерами таких объектов могут служить линейные участки магистральных трубопроводов, коридоры промысловых коммуникаций, автомобильные трассы и т. п. В статье дается математическая формулировка задачи в виде экстремальной комбинаторной модели. Анализируется специфика модели и на ее основе предлагается алгоритм метода ветвей и границ (МВиГ). Рассмотрен числовой пример, позволяющий показать преимущества предложенного алгоритма МВиГ для решения данной задачи. Алгоритмы запрограммированы на языке Python и в статье приводятся результаты вычислительного эксперимента.