Задача построения расписания конфигураций с ограничением на максимальную глубину узлов Евгений Наградов

Описание проблемы Конфигурация, расписание конфигураций Актуальность учета ограничений по глубине конфигурации Алгоритм решения задачи – сведение задачи к задаче LP – алгоритм формирования набора конфигураций – подзадача формирования конфигурации минимальной стоимости Эффективность алгоритма

Задача построения расписания конфигураций Ограничения – граф сети не изменяется в процессе функционирования – в данной работе рассматривается упрощенная модель энергопотребления Конфигурация сети Расписание конфигураций

Пусть задан граф сети с базовой станцией Конфигурация – остовное дерево в графе сети с корнем в базовой станции Конфигурация определяет для каждого узла: – является ли узел маршрутизатором – родительский маршрутизатор Конфигурация сети

Расписание конфигураций Расписание – последовательность – q i – конфигурация сети – t i – продолжительность использования конфигурации Продолжительность расписания Ограничение корректности: ни один узел не израсходует запас энергии до окончания использования расписания

Расписание конфигураций, S = { (q 1,t 1 ), (q 2,t 2 ) } q1:q1: q2:q2:

Ограничение на максимальную глубину узлов в конфигурации Наличие требований к продолжительности доставки сообщений от узлов до базовой станции Снижение продолжительности доставки сообщений

TODO: картинка с распределением максимальной глубины узлов для одного из расписаний

Формальная постановка задачи Условия корректности конфигурации – связность – ограничение на максимальную глубину узлов Корректность расписания – расписание корректно, если ни один из узлов не израсходует полностью запас энергии до окончания расписания

Сведение задачи к задаче непрерывного линейного программирования Описание сведения Проблема – построение всего множества корректных конфигураций не эффективно

Построение подмножества конфигураций Построение конфигураций с непересекающимися множествами маршрутизаторов – преимущества: малое количество конфигураций, вычислительная сложность – проблема: низкая эффективность Алгоритм Гарга-Конеманна

TODO: описание алгоритма Позволяет свести задачу к многократному решению подзадачи построения корректной конфигурации минимальной стоимости

Алгоритм решения подзадачи построения конфигурации минимальной стоимости Проблемы алгоритмов, основанных на построении конфигурации посредством фиксации маршрутизаторов TODO: описание алгоритма

Исследование эффективности предложенной схемы решения задачи TODO: 2 рисунка (для различных графов сети) Сравниваются 3 алгоритма: – жадный алгоритм – алгоритм Гарга-Конеманна без последующего решения задачи LP – предлагаемая схема

Проблемы предлагаемого подхода Проблема одновременной смерти большего количества узлов чем требуется Учет дополнительных ограничений на конфигурации для различных протоколов MAC-уровня – например, для ZigBee требуется учитывать требование непересечения активных участков различных ветвей дерева конфигураций (для снижения коллизий при передаче маяков) – вариант решения – использование алгоритма, основанного на муравьиных колониях

Спасибо за внимание Вопросы?