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

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

Ограничение рассматриваемого класса сетей Ограничения – граф сети не изменяется в процессе функционирования – ограниченный запас энергии узлов Разделение ролей узлов в сети на: – маршрутизаторы – листовые узлы

Централизованный подход к управлению сенсорной сетью Разделение ролей узлов в сети на маршрутизаторы и листовые узлы Базовая станция определяет динамику изменения ролей узлов на основе графа сети

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

Пример конфигурации

Расписание конфигураций Расписание определяет динамику изменения ролей узлов в сети Расписание – последовательность – q i – конфигурация сети – t i – продолжительность использования конфигурации, S = { (q 1,t 1 ), (q 2,t 2 ) } q1:q1: q2:q2:

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

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

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

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

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

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

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

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

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

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