Введение к работе
Актуальность темы. Работа посвящена исследованию задач дискретной оптимизации, связанных с минимизацией энергопотребления сетей сбора и передачи данных на примере беспроводных сенсорных сетей (БСС). В современной литературе [1] под БСС понимается распределённая, самоорганизующаяся сеть множества датчиков (сенсоров) — интеллектуальных автономных электронных устройств, каждое из которых, находясь в активном состоянии, способно собирать информацию в пределах заданной области мониторинга, частично ее обрабатывать и передавать другим сенсорам или иным объектам посредством радиосвязи. В диссертации исследуются модели БСС, в которых каждый сенсор оснащен элементом питания ограниченной емкости, потери которой в единицу времени зависят от значений параметров сенсоров в активном состоянии. При этом считается, что возобновление энергии сенсора невозможно. В неактивном состоянии (состоянии сна) потери энергии сенсора пренебрежимо малы. На практике мощность элемента питания одного сенсора невысока, однако избыточное количество сенсоров, а также правильная организация их функционирования (расписание активности) и топологии сенсорной сети позволяет существенно увеличить время бесперебойной работы (время жизни) БСС. Основным критерием качества БСС является время ее жизни, увеличение которого достигается, в частности, минимизацией энергозатрат БСС. Для увеличения времени жизни БСС необходимо решить целый ряд оптимизационных задач. Среди них оптимальное размещение сенсоров, определение зоны действия (мониторинга или покрытия), а также дальности передачи и поиск оптимального расписания активности каждого сенсора.
Все перечисленные задачи в общих постановках являются NP-трудными [2,6-8,23,26], следовательно для них актуальна проблема построения приближенных эффективных алгоритмов и анализа их качества.
Проблемам, связанным с максимизацией времени жизни БСС, посвящено немалое количество публикаций. Так как для полноценного функционирования БСС требуется связность выбранного подмножества сенсоров, одной из важнейших проблем в БСС является задача построения связных покрытий. В [2] доказано, что задача нахождения максимального числа непересекающихся связных покрытий NP-трудна. Приближенные алгоритмы нахождения связных покрытий предлагаются в работах [3-5]. В [6] рассмотрена задача выбора совокупности связных покрытий, обеспечивающих максимальное время жизни сети и предлагается эвристический метод ее решения. Эффективным способом продления времени жизни БСС является возможность регулирования областей мониторинга и дальности передачи. В [7] предложено
несколько моделей покрытия области сенсорами с адаптивными радиусами мониторинга и связи. В [8] рассмотрены новые модели покрытия с адаптивными радиусами мониторинга и связи, которые обеспечивают существенный выигрыш в экономии энергии по сравнению с известными ранее. Работа по отысканию эффективных моделей покрытия с адаптивными радиусами мониторинга и связи продолжена в [9,10]. В статических БСС зачастую происходит неравномерное использование ресурсов сенсоров, поэтому мобильность сенсоров также может быть использована как средство продления жизни БСС. В [11-15] исследованы различные модели БСС с использованием мобильных устройств. Результаты экспериментов показали, что мобильность сенсоров и базовых станций позволяет существенно продлить время жизни БСС.
Часто детерминированное размещение сенсоров оказывается нецелесообразным (например, при большом числе сенсоров) или неосуществимым (театр боевых действий или зараженная территория), а различные препятствия и другие внешние факторы могут привести к помехам при обмене данными и мониторинге. В связи с этим для поддержания функционирования БСС часто требуется учитывать вероятностный характер расположения сенсоров и других характеристик. В [16] рассмотрен случай, когда сенсоры распределены случайно в соответствии с распределением Гаусса. В [17] экспериментально исследована возможность обеспечения гарантированного покрытия при случайном распределении сенсоров за счет незначительного увеличения радиусов мониторинга. Анализ влияния неопределенностей, связанных с передачей информации, проведен в [18]. В [19] впервые найдены аналитические оценки снизу на время жизни БСС в случае равномерного случайного распределения сенсоров в плоской области мониторинга. В традиционных моделях БСС зона мониторинга (покрытия) сенсора - это круг, радиус которого может меняться в заданных пределах. При этом энергозатраты сенсора пропорциональны покрытой им площади, и задача энергоэффективного мониторинга сводится к задаче построения наименее плотного покрытия плоской области кругами различных радиусов. Подобные задачи сравнительно хорошо изучены и им посвящено множество публикаций по комбинаторной (вычислительной) геометрии, среди которых выделим монографии [20-22].
В работе [23] сформулирована задача максимизации времени жизни БСС в виде частного случая задачи линейного программирования (packing linear program) и предлагается метод ее решения, основанный на алгоритме Гарга-Кенеманна (Garg-Konemann) [24]. В первой главе данной диссертационной работы рассматривается аналогичная задача в условиях заданного избыточного множества покрытий и дискретных переменных, соответствующих количеству временных раундов, в течение которых покрытие функционирует.
В работе [26] сформулирована задача построения минимального коммуникационного дерева в простом реберно-взвешенном неориентированном графе. Эта задача возникает при минимизации энергозатрат активных элементов сети на связь, в случае когда элементы сети способны регулировать дальность передачи. В работах [28, 29] доказана NP-трудность различных частных случаев данной задачи. В работе [31] доказана (1 + ^)-неаппроксимируемость задачи. Авторами работы [26] для метрической задачи предложены вполне полиномиальная схема построения 5/3-приближенного решения, полиномиальный алгоритм, строящий 11/6-приближенное решение, а также точный алгоритм — метод ветвей и границ, в котором используется постановка в виде задачи целочисленного линейного программирования (ЦЛП). Дальнейшему исследованию этой задачи посвящена вторая глава диссертации.
Объектом исследования в диссертации является беспроводная сеть, состоящая из множества элементов, способных осуществлять мониторинг (покрытие) заданной области или множества объектов и обмениваться информацией. Исследуемые в работе оптимизационные задачи возникают из необходимости экономии энергии элементов сети. Для предметности изложения в качестве такой сети рассматривается БСС, однако исследуемые проблемы актуальны для многих других сетей сбора и передачи данных.
Предметом исследования являются проблемы дискретной оптимизации, связанные с минимизацией энергозатрат сетей сбора и передачи данных на примере БСС. Это задача определения оптимального расписания активности сенсоров при заданном множестве покрытий и задача минимизации энергозатрат на связь элементов одного покрытия в течение одного временного такта (раунда) его активности.
Целью данной работы является построение математических моделей и исследование задач дискретной оптимизации, связанных с минимизацией энергопотребления БСС, а также разработка эффективных приближенных алгоритмов их решения, программная реализация разработанных алгоритмов и оценка их качества.
Методы исследований. В работе используются методы математического моделирования, дискретной оптимизации, исследования операций, целочисленного линейного программирования и теории графов. Для проведения численных экспериментов применялись современные методы программирования на языке C++, а также пакет программ IBM ILOG CPLEX, предоставленный в рамках программы IBM Academic Initiative.
Научная новизна. Впервые сформулирована задача максимизации времени функционирования БСС при заданном наборе покрытий в виде за-
дачи ЦЛП, показана NP-трудность задачи, найдены условия при которых задача принадлежит классу АРХ, рассмотрены полиномиально разрешимые частные случаи задачи, для некоторых из них предложены новые (менее трудоёмкие по сравнению с существующими) алгоритмы точного решения. Для приближенного решения задачи предложены новые эффективные эвристические алгоритмы и осуществлен их апостериорный анализ. Получены новые результаты для задачи построения минимального коммуникационного дерева, известной как Min-Power Symmetric Connectivity Problem [26]. Уточнена априорная оценка точности и найдены новые полиномиально разрешимые частные случаи. Предложены новые эффективные приближенные эвристические алгоритмы решения задачи и осуществлен их апостериорный анализ, который показал высокую эффективность предложенных алгоритмов.
Практическая значимость. Одной из наиболее важных проблем, связанных с минимизацией энергозатрат БСС является задача максимизации времени функционирования БСС. На практике эту задачу часто решают в два этапа: на первом этапе строятся эффективные покрытия, учитывая расход энергии элементов как на мониторинг области, так и на связь [3,27], а на втором — определяется время функционирования каждого покрытия [6,23]. Исследованию задачи максимизации времени жизни БСС при заданном множестве покрытий посвящена первая глава работы. Целочисленность переменных времени в исследуемой задаче имеет практический смысл: т.к. сенсор — это электронное интеллектуальное устройство, работа которого состоит из выполнения некоторых операций, уместно измерять время работы сенсора в количестве т.н. "временных тактов".
Задача построения минимального коммуникационного дерева, которой посвящена вторая глава, возникает в различных беспроводных сетях и, в частности, в современных сенсорных сетях, когда сенсоры способны регулировать дальность передачи. В этой задаче требуется минимизировать суммарные потери энергии сенсоров на связь в течение одного временного такта.
Апробация работы. Основные результаты работы докладывались на Международной научной студенческой конференции (г. Новосибирск, 2010), на Российской конференции «Дискретная оптимизация и исследование операций» (с. Немал, Республика Алтай, 2010г.), на Международной конференции «The 11th International Conference on Computational Science and Its Applications» (ICCSA'2011) (Испания, г. Сантандер, 2011г.), на 8-й Азиатской международной школе-семинаре «Проблемы оптимизации сложных систем» (Казахстан, г. Щучинск, 2012г.), на 5-ой Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Россия, г. Омск, 2012г.), на семинарах Института математики им. С.Л. Соболева СО РАН и кафедры
Теоретической кибернетики Новосибирского государственного университета (2010-2013гг.), на Международной конференции «Дискретная оптимизация и исследование операций» (г. Новосибирск, 2013 г.), на Международной конференции «Numerical Computations: Theory and Algorithms» (NUMTA2013) (Италия, г.Фалерна, 2013г.).
Публикации. Основные результаты по теме диссертации изложены в 8 печатных работах, среди которых 3 статьи в рецензируемых журналах и 1 свидетельство о государственной регистрации программы ЭВМ.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы (63 наименований). Общий объем работы — 89 страниц.
