В настоящее время технология беспроводной передачи данных становится предпочтительной, а в некоторых случаях единственно возможной для коммуникации информационных устройств. При необходимости охвата сетью большого пространства со сложной конфигурацией возникает необходимость рационально разместить несколько Wi-Fiизлучателей, обеспечивающих устойчивую связь с каждой точкой возможного расположения приёмника сигналов. Тогда задача размещения Wi-Fi излучателей может быть сформулирована как определение дискретного множества точек размещения излучателей, удовлетворяющего условию. Иначе, необходимо определить положения всех излучателей, полностью покрывающих заданную территорию, причём количество излучателей должно быть минимально. В такой постановке это задача о наименьшем покрытии – поиск наименьшего множества столбцов матрицы, «покрывающих» все её строки. С точки зрения постановки задачи о наименьшем покрытии, возможны два случая конфигурации области охвата окружающего пространства Wi-Fi излучателями: 1. Безвариативный. Его особенность состоит в том, что зона покрытия полностью определяется точкой размещения излучателя. Это возможно в том случае, когда зона охвата симметрична или ориентация диаграммы направленности излучения строго фиксирована. В этом случае можно построить граф, ассоциированный с набором точек размещения излучателей, в котором каждой точке размещения ставятся в соответствие смежные вершины. В такой постановке мы приходим к задаче о наименьшем доминирующем множестве графа. 2. Вариативный. Он имеет место в том случае, когда диаграммы излучения направлена, и зона охвата может меняться в зависимости от ориентации излучателя. То есть реальный излучатель можно развернуть в бесконечное количество различных положений, однако конечность охватываемых точек существенно ограничивает число различных ориентаций. В этом случае каждой точке положения излучателя можно поставить в соответствие несколько строк матрицы и каждой покрываемой точке будет соответствовать ровно один столбец.

Wi-Fi сеть, алгоритм бинарного программирования, задача о наименьшем покрытии

1. Новиков Ф. А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. / Ф. А. Новиков. СПб: Питер, 2009. – 374 с.

2. Заозерская Л. А. Исследование и решение двухкритериальной задачи о покрытии множества / Л. А. Заозерская, А. А. Колоколов // Проблемы информатики. 2009. № 1. С. 14–23.

3. Дасгупта С. Алгоритмы / С. Дасгупта, Х. Пападимитриу, У. Вазирани // Пер. с англ. М.: МЦНМО, 2014. – 320 с.

4. Иванов Б. Н. Дискретная математика. Алгоритмы и программы. Расширенный курс / Б. Н. Иванов. М.: Известия, 2011. – 512 с.

5. Бугаев Ю. В. Приближенный метод синтеза моделей выбора на основе экстраполяции экспертных оценок / Ю. В. Бугаев, И. Е. Медведкова, Б. Е. Никитин, А. С. Чайковский / Вестник Тамбовского государственного технического университета. 2009. Т. 15. № 4. С. 766–776.