М.Ш. Левин, Р.И. Нуриахметов
Многокритериальная задача дерева Штейнера для
коммуникационной сети
Данная
статья предлагает комбинаторную оптимизационную схему для решения
многокритериальной задачи дерева Штейнера применительно к проектированию
топологии коммуникационной сети (например, беспроводная wireless mesh сеть). Схема решения базируется на нескольких задачах: многокритериальное
ранжирование, кластеризация, минимальное покрывающее дерево, минимальное дерево
Штейнера. Иллюстративный численный пример соответствует проектированию покрывающей
сети для Wi-Fi сети (т.е., статическая Ad-Hoc сеть). Множество критериев (т.е., целевых
функций) включает общую стоимость, суммарную о длину парных соединений,
обобщенную пропускную способность (throughput), оценку качества обслуживания (QoS). Полученные численные результаты показали,
что предложенная схема решения обеспечивает топологию сети, которая может быть
сравнима по качеству с решениями, получаемыми на основе минимальных покрывающих
деревьев.
КЛЮЧЕВЫЕ СЛОВА: многокритериальная задача, коммуникационная
сеть, дерево Штейнера, топология сети