Построение минимального доминирующего множества при проектировании wi-fi-сети

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