Исследование оптимизационных моделей сетей сбора и передачи данных при ресурсных ограничениях

• Автор: Плотников, Роман Викторович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Новосибирск
• Количество страниц: 88 с. : ил.

Содержание
Введение
1 Максимизация времени жизни беспроводной сенсорной сети при заданном множестве покрытий

1.1 Постановка задачи

1.2 Вычислительная сложность задачи

1.3 Упрощение сенсорных сетей

1.4 Аппроксимируемость задачи

1.5 Полиномиально разрешимые случаи

1.5.1 Абсолютная унимодулярность матрицы ограничений

1.5.2 Другие частные случаи

1.6 Приближённые алгоритмы

1.6.1 Описание алгоритмов
1.7 Результаты и выводы к Главе
2 Задача построения оптимального коммуникационного дерева
2.1 Постановка задачи и анализ сложности
2.2 Частные случаи
2.3 Оценки точности полиномиальных алгоритмов
2.4 Эвристические алгоритмы
2.4.1 Минимальный остов для специальных весов ребер графа
2.4.2 Процедура локальных улучшений
2.4.3 Гибридный генетический алгоритм
2.5 Постановка задачи в виде ЦЛП
2.6 Результаты и выводы к Главе

3 Комплекс программ для апостериорного анализа эвристических алгоритмов
3.1 Численный эксперимент для оценки эффективности алгоритмов решения
задачи максимизации времени жизни БСС при заданном множестве покрытий
3.1.1 Программная реализация алгоритмов
3.1.2 Результаты численного эксперимента
3.2 Численный эксперимент для оценки эффективности алгоритмов решения
задачи построения оптимального коммуникационного дерева
3.2.1 Программная реализация алгоритмов
3.2.2 Результаты численного эксперимента
3.3 Результаты и выводы к Главе
Заключение
Литература

Введение
Работа посвящена исследованию задач дискретной оптимизации, связанных с минимизацией энергопотребления сетей сбора и передачи данных на примере беспроводных сенсорных сетей (БСС). В современной литературе [35] под БСС понимается распределенная, самоорганизующаяся сеть множества датчиков (сенсоров) —- интеллектуальных автономных электронных устройств, каждое из которых, находясь в активном состоянии, способно собирать информацию в пределах заданной области мониторинга, частично се обрабатывать и передавать другим сенсорам или иным объектам посредством радиосвязи. В диссертации исследуются модели БСС, в которых каждый сенсор оснащен элементом питания ограниченной емкости, потери которой в единицу времени зависят от значений параметров сенсоров в активном состоянии. При этом считается, что возобновление энергии сенсора невозможно. В неактивном состоянии (состоянии сна) потери энергии сенсора пренебрежимо малы. На практике мощность элемента питания одного сенсора невысока, однако избыточное количество сенсоров, а также правильная организация их функционирования (расписание активности) и топологии сенсорной сети позволяет существенно увеличить время бесперебойной работы (время жизни) БСС. Основным критерием качества БСС является время се жизни, увеличение которого достигается, в частности, минимизацией энергозатрат БСС [2, 54, 62]. Для увеличения времени жизни БСС необходимо решить целый ряд оптимизационных задач. Среди них оптимальное размещение сенсоров, определение зоны действия (мониторинга или покрытия),

Рисунок 2.1: Пример задачи (2.1), полученной из индивидуальной задачи МП
Предположим, что задача построения /г-приближённого {В, > 1) решения для МВП является КР-трудной. Следовательно,
п' У(ТА) - т > д
п* 'Щ* — т
Из (2.2) имеем IV{ТА) < Значит, - т > В{Ш* - т) и <2 >
Я - {В - 1)т/ИЖ
Предположим, что степень графа С (максимальная степень вершин) равна А < к. Пусть &-МВП — это задача МВП на графе, степень которого не превосходит к. Известно, что /с-МВП Ж'-трудна для каждого класса графов при к > 3 [24]. Так как в данном случае каждый элемент покрывает не более к объектов, то п* > т/к. Следовательно, IV* > т/к + т и С} > 1 + (І? — 1 )/{к + 1). Таким образом, доказана
Теорема 2. Если задача построения Л-приближснного решения для А:-МВП ИР-трудна, то задача построения (1+(Д—1)/(&+1))-приближснного решения задачи (2.1) ИР-трудна.
Замечание 2.1. Известно, что задача построения (1 + ^)-приближенного решения для, 4-МВП ЫР-трудна [30]. Тогда из Теоремы 2 следует, ВР-трудность построения (1 + -приближенного решения задачи (2.1)