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

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

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

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

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

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

Наличие требований к продолжительности доставки сообщений от узлов до базовой станции – для протоколов MAC-уровня, основанных на волнообразном упорядочении участков активности узлов, продолжительность доставки определяется глубиной узлов Актуальность учета ограничений на глубину узлов в конфигурации v0v0 v1v1 v2v2 v3v3

Постановка задачи Заданы: – граф сети – начальный запас энергии узлов b i – характеристики потребления энергии узлов e r и e s – максимальная глубина узлов h max Требуется построить расписание конфигураций максимальной продолжительности Ограничения: – корректность конфигураций: глубина узлов в каждой из конфигураций расписания не должна превосходить заданную: h(v i ) h max – корректность расписания: ни один из узлов сети не израсходует запас энергии до окончания использования расписания

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

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

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

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

Исследование эффективности [1] 225 узлов в форме сетки 15x15 максимальный радиус передачи 10 (слева) и 20 (справа) размер области 100x100

Исследование эффективности [2] 200 узлов, расположены случайным образом максимальный радиус передачи 25 размер области 100x100 усреднение по 10 испытаниям

Дальнейшее развитие подхода Учет дополнительных затрат энергии на передачу потока сообщений Учет дополнительных ограничений на конфигурации для различных протоколов MAC-уровня

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

max h(v) = 7

max h(v) = 14