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

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

Централизованный подход к управлению сенсорной сетью Каждый узел может функционировать в одной из двух ролей: – маршрутизатор – листовой узел Базовая станция определяет динамику изменения ролей узлов на основе графа сети Задача – максимизировать продолжительность функционирования сети до исчерпания запаса энергии первого узла

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

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

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

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

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

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

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

Предлагаемый подход к решению задачи Двухшаговая схема: 1.сформируем подмножество конфигураций, удовлетворяющих ограничению на глубину узлов 2.для построенного подмножества конфигураций выполним решение задачи линейного программирования

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

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

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

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

Спасибо за внимание