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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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