М.Ш. Левин, Р.И. Нуриахметов

Многокритериальная задача дерева Штейнера для коммуникационной сети

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

КЛЮЧЕВЫЕ СЛОВА: многокритериальная задача, коммуникационная сеть, дерево Штейнера, топология сети