Preview

Вестник Воронежского государственного университета инженерных технологий

Расширенный поиск

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

https://doi.org/10.20914/2310-1202-2016-2-60-64

Полный текст:

Аннотация

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

Об авторах

Ю. В. Бугаев
Воронежский государственный университет инженерных технологий
Россия

д.ф.-м.н, профессор, кафедра информационных технологий моделирования и управления,

пр-т Революции, 19, г. Воронеж, 394000



С. Н. Черняева
Воронежский государственный университет инженерных технологий
к.т.н., доцент, кафедра информационных технологий моделирования и управления,

пр-т Революции, 19, г. Воронеж, 394000



О. Ю. Ойцева
Воронежский государственный университет инженерных технологий
ст. пр., кафедра информационных технологий моделирования и управления,

пр-т Революции, 19, г. Воронеж, 394000



А. И. Коробов
Воронежский государственный университет инженерных технологий
магистр, кафедра информационных технологий моделирования и управления,

пр-т Революции, 19, г. Воронеж, 394000



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

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

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

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

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

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


Для цитирования:


Бугаев Ю.В., Черняева С.Н., Ойцева О.Ю., Коробов А.И. Построение минимального доминирующего множества при проектировании Wi-Fi-сети. Вестник Воронежского государственного университета инженерных технологий. 2016;(2):60-64. https://doi.org/10.20914/2310-1202-2016-2-60-64

For citation:


Bugaev Y.V., Chernyaeva S.N., Oytceva O.Y., Korobov A.I. Construction of the minimal dominating set in the design of Wi-Fi-network. Proceedings of the Voronezh State University of Engineering Technologies. 2016;(2):60-64. (In Russ.) https://doi.org/10.20914/2310-1202-2016-2-60-64

Просмотров: 240


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-910X (Print)
ISSN 2310-1202 (Online)