автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Исследование оптимизационных моделей сетей сбора и передачи данных при ресурсных ограничениях

На правах рукописи

Плотников Роман Викторович

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

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание учёной степени кандидата физико-математических наук

2 4 ОКТ 2013

Новосибирск — 2013

005535540

005535540

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования "Новосибирский национальный исследовательский государственный университет"

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Ерзин Адиль Ильясович

Родионов Алексей Сергеевич, доктор технических наук, профессор, Федеральное государственное бюджетное учреждение науки Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук, заведующий лабораторией

Кочетов Юрий Андреевич, доктор физико-математических наук, доцент, Федеральное государственное бюджетное учреждение науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, ведущий научный сотрудник Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Омский государственный технический университет"

Защита состоится «<2. » НОА&р'З. 2013 г. в час. 0 О мин. на заседании диссертационного совета Д 003.061.02 на базе Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук по адресу: 630090, г. Новосибирск, проспект Академика Лаврентьева, 6. С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук. (— Автореферат разослан «/ !■ » ОКТЛ О^Л, 2013 года.

Ученый секретарь диссертационного совета д.ф.-м.н. 1 Сорокин Сергей Борисович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Все перечисленные задачи в общих постановках являются ИР-трудными [2,6-8,23,26], следовательно для них актуальна проблема построения приближенных эффективных алгоритмов и анализа их качества.

Проблемам, связанным с максимизацией времени жизни БСС, посвя-щело немалое количество публикаций. Так как для полноценного функционирования БСС требуется связность выбранного подмножества сенсоров, одной из важнейших проблем в БСС является задача построения связных покрытий. В [2] доказано, что задача нахождения максимального числа непересекающихся связных покрытий ОТ-трудна. Приближенные алгоритмы нахождения связных покрытий предлагаются в работах [3-5]. В [6] рассмотрена задача выбора совокупности связных покрытий, обеспечивающих максимальное время жизни сети и предлагается эвристический метод ее решения. Эффективным способом продления времени жизни БСС является возможность регулирования областей мониторинга и дальности передачи. В [7] предложено

3

несколько моделей покрытия области сенсорами с адаптивными радиусами мониторинга и связи. В [8] рассмотрены новые модели покрытия с адаптивными радиусами мониторинга и связи, которые обеспечивают существенный выигрыш в экономии энергии по сравнению с известными ранее. Работа по отысканию эффективных моделей покрытия с адаптивными радиусами мониторинга и связи продолжена в [9,10]. В статических БСС зачастую происходит неравномерное использование ресурсов сенсоров, поэтому мобильность сенсоров также может быть использована как средство продления жизни БСС. В [11-15] исследованы различные модели БСС с использованием мобильных устройств. Результаты экспериментов показали, что мобильность сенсоров и базовых станций позволяет существенно продлить время жизни БСС.

Часто детерминированное размещение сенсоров оказывается нецелесообразным (например, при большом числе сенсоров) или неосуществимым (театр боевых действий или зараженная территория), а различные препятствия и другие внешние факторы могут привести к помехам при обмене данными и мониторинге. В связи с этим для поддержания функционирования БСС часто требуется учитывать вероятностный характер расположения сенсоров и других характеристик. В [16] рассмотрен случай, когда сенсоры распределены случайно в соответствии с распределением Гаусса. В [17] экспериментально исследована возможность обеспечения гарантированного покрытия при случайном распределении сенсоров за счет незначительного увеличения радиусов мониторинга. Анализ влияния неопределенностей, связанных с передачей информации, проведен в [18]. В [19] впервые найдены аналитические оценки снизу на время жизни БСС в случае равномерного случайного распределения сенсоров в плоской области мониторинга. В традиционных моделях БСС зона мониторинга (покрытия) сенсора - это круг, радиус которого может меняться в заданных пределах. При этом энергозатраты сенсора пропорциональны покрытой им площади, и задача энергоэффективного мониторинга сводится к задаче построения наименее плотного покрытия плоской области кругами различных радиусов. Подобные задачи сравнительно хорошо изучены и им посвящено множество публикаций по комбинаторной (вычислительной) геометрии, среди которых выделим монографии [20-22].

В работе [23] сформулирована задача максимизации времени жизни БСС в виде частного случая задачи линейного программирования (packing linear program) и предлагается метод ее решения, основанный на алгоритме Гарга-Кенеманна (Garg-Konemann) [24]. В первой главе данной диссертационной работы рассматривается аналогичная задача в условиях заданного избыточного множества покрытий и дискретных переменных, соответствующих количеству временных раундов, в течение которых покрытие функционирует.

В работе [26] сформулирована задача построения минимального коммуникационного дерева в простом реберно-взвешенном неориентированном графе. Эта задача возникает при минимизации энергозатрат активных элементов сети на связь, в случае когда элементы сети способны регулировать дальность передачи. В работах [28, 29] доказана NP-трудность различных частных случаев данной задачи. В работе [31] доказана (1 + jgo)-неаппроксимируемость задачи. Авторами работы [26] для метрической задачи предложены вполне полиномиальная схема построения 5/3-приближенного решения, полиномиальный алгоритм, строящий 11/6-приближенное решение, а также точный алгоритм — метод ветвей и границ, в котором используется постановка в виде задачи целочисленного линейного программирования (ЦЛП). Дальнейшему исследованию этой задачи посвящена вторая глава диссертации.

Объектом исследования в диссертации является беспроводная сеть, состоящая из множества элементов, способных осуществлять мониторинг (покрытие) заданной области или множества объектов и обмениваться информацией. Исследуемые в работе оптимизационные задачи возникают из необходимости экономии энергии элементов сети. Для предметности изложения в качестве такой сети рассматривается БСС, однако исследуемые проблемы актуальны для многих других сетей сбора и передачи данных.

Предметом исследования являются проблемы дискретной оптимизации, связанные с минимизацией энергозатрат сетей сбора и передачи данных на примере БСС. Это задача определения оптимального расписания активности сенсоров при заданном множестве покрытий и задача минимизации энергозатрат на связь элементов одного покрытия в течение одного временного такта (раунда) его активности.

Целью данной работы является построение математических моделей и исследование задач дискретной оптимизации, связанных с минимизацией энергопотребления БСС, а также разработка эффективных приближенных алгоритмов их решения, программная реализация разработанных алгоритмов и оценка их качества.

Методы исследований. В работе используются методы математического моделирования, дискретной оптимизации, исследования операций, целочисленного линейного программирования и теории графов. Для проведения численных экспериментов применялись современные методы программирования на языке С++, а также пакет программ IBM ILOG CPLEX, предоставленный в рамках программы IBM Academic Initiative.

Научная новизна. Впервые сформулирована задача максимизации времени функционирования БСС при заданном наборе покрытий в виде за-

дачи ЦЛП, показана NP-трудность задачи, найдены условия при которых задача принадлежит классу АРХ, рассмотрены полиномиально разрешимые частные случаи задачи, для некоторых из них предложены новые (менее трудоёмкие по сравнению с существующими) алгоритмы точного решения. Для приближенного решения задачи предложены новые эффективные эвристические алгоритмы и осуществлен их апостериорный анализ. Получены новые результаты для задачи построения минимального коммуникационного дерева, известной как Min-Power Symmetric Connectivity Problem [26]. Уточнена априорная оценка точности и найдены новые полиномиально разрешимые частные случаи. Предложены новые эффективные приближенные эвристические алгоритмы решения задачи и осуществлен их апостериорный анализ, который показал высокую эффективность предложенных алгоритмов.

Практическая значимость. Одной из наиболее важных проблем, связанных с минимизацией энергозатрат БСС является задача максимизации времени функционирования БСС. На практике эту задачу часто решают в два этапа: на первом этапе строятся эффективные покрытия, учитывая расход энергии элементов как на мониторинг области, так и на связь [3,27], а на втором — определяется время функционирования каждого покрытия [6,23]. Исследованию задачи максимизации времени жизни БСС при заданном множестве покрытий посвящена первая глава работы. Целочисленность переменных времени в исследуемой задаче имеет практический смысл: т.к. сенсор — это электронное интеллектуальное устройство, работа которого состоит из выполнения некоторых операций, уместно измерять время работы сенсора в количестве т.н. "временных тактов".

Задача построения минимального коммуникационного дерева, которой посвящена вторая глава, возникает в различных беспроводных сетях и, в частности, в современных сенсорных сетях, когда сенсоры способны регулировать дальность передачи. В этой задаче требуется минимизировать суммарные потери энергии сенсоров на связь в течение одного временного такта.

Апробация работы. Основные результаты работы докладывались на Международной научной студенческой конференции (г. Новосибирск, 2010), на Российской конференции «Дискретная оптимизация и исследование операций» (с. Чемал, Республика Алтай, 2010г.), на Международной конференции «The llth International Conference on Computational Science and Its Applications» (ICCSA'2011) (Испания, г. Сантандер, 2011г.), на 8-й Азиатской международной школе-семинаре «Проблемы оптимизации сложных систем» (Казахстан, г. Щучинск, 2012г.), на 5-ой Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Россия, г. Омск, 2012г.), на семинарах Института математики им. C.JL Соболева СО РАН и кафедры

Теоретической кибернетики Новосибирского государственного университета (2010-2013гг.), на Международной конференции «Дискретная оптимизация и исследование операций» (г. Новосибирск, 2013 г.), на Международной конференции «Numerical Computations: Theory and Algorithms» (NUMTA2013) (Италия, г.Фалерна, 2013г.).

Публикации. Основные результаты по теме диссертации изложены в 8 печатных работах, среди которых 3 статьи в рецензируемых журналах и 1 свидетельство о государственной регистрации программы ЭВМ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы (63 наименований). Общий объем работы — 89 страниц.

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

В первой главе исследуется задача максимизации времени жизни БСС в условиях ограниченности ресурсов сенсоров, в которой при заданном множестве покрытий требуется определить время функционирования каждого покрытия.

Раздел 1.1 содержит основные определения и постановку проблемы в виде задачи ЦЛП. Пусть J — множество сенсоров, \J\ = тг, и каждый сенсор j Е J обладает ограниченным ресурсом г,- е . Предположим, что задано множество различных покрытий С = {Сь..., Ст}, С< С 3. Введем параметры Ьд = 1, если сенсор j £ С* и Ь^ = 0 в противном случае, а также вектор переменных у = (у\,..., ут), где ук е Z+ — время функционирования (жизни) покрытия С к (т.е. количество временных раундов, в течение которых элементы покрытия активны). Тогда задача максимизации времени жизни БСС запишется следующим образом:

£=1

Данная задача является ЫР-трудной в сильном смысле. Кроме того, она неаппроксимируема с коэффициентом 0(тп1-£) \/е > 0. Эти утверждения обоснованы в замечаниях 1 и 2 раздела 1.2.

7

СОДЕРЖАНИЕ РАБОТЫ

m

(1)

тп

(2)

Похожая постановка была предложена в работе [23]. Авторы сформулировали задачу максимизации времени жизни БСС в случай, когда множество покрытий не задано, а переменные непрерывны в виде частного случая задачи линейного программирования (packing linear program) и предложили метод ее решения, основанный на алгоритме Гарга-Кенеманна (Garg-Konemann) [24].

В разделе 1.3 предложены способы упрощения БСС.

В разделе 1.4 приведены условия, при которых задача (1)-(2) принадлежит классу АРХ, т.е для неё существует полиномиальный субоптимальный алгоритм.

Пусть заданы фиксированные параметры a, b и Д: 0 < а < 6, Д > 3. Пусть Ра,ь,л подкласс индивидуальных задач (1)-(2), в которых ресурс каждого сенсора принадлежит фиксированному отрезку [а, 6], и каждое покрытие пересекается не более чем с Д другими покрытиями. Доказана

Теорема 1. Задача Р0,ь,д принадлежит классу АРХ.

В разделе 1.5 рассмотрены случаи, когда задача (1)-(2) полиномиально разрешима. Особое внимание уделяется ситуации, когда матрица ограничений абсолютно унимодулярна. Показано, что задача полиномиально разрешима в случае, если граф пересечений покрытий является двудольным. Для случая, когда граф пересечений покрытий — дерево, и ресурсы всех вершин одинаковые, предложен полиномиальный алгоритм, строящий оптимальное решение задачи с трудоемкостью 0(т2). В случае, если каждое покрытие состоит из двух сенсоров, строится граф G', вершины которого соответствуют сенсорам, а ребра — покрытиям. Показано, что задача полиномиально разрешима в случае, если G' — двудольный граф. Для случая, когда граф G' — дерево (частный случай двудольного графа), предложен полиномиальный алгоритм, строящий оптимальное решение задачи с трудоемкостью 0(п).

В разделе 1.6 предложены 2 эвристических алгоритма, строящих приближенное решение задачи (1)-(2). Для оценки качества предложенных алгоритмов проведен численный эксперимент, описание которого приведено разделе 3.1 главы 3. Результаты численного эксперимента демонстрируют высокую эффективность предложенных методов, что особенно заметно при малых значениях начальных ресурсов сенсоров.

Вторая глава посвящена исследованию задачи синтеза оптимального коммуникационного дерева БСС.

В разделе 2.1 приводятся основные определения и математическая постановка задачи, состоящая в следующем.

Задан простой неориентированный взвешенный граф С = (V, Е) с множеством вершин V, = п, и множеством ребер Е. Пусть су > 0 — вес ребра (г,7") е Е. Требуется найти остовное дерево Т* графа О, являющееся решением задачи:

где Ni(T) — множество вершин, смежных с вершиной i в дереве Т. В англоязычной литературе такую задачу принято называть Min-Power Symmetric Connectivity Problem [26]. В дальнейшем любое допустимое решение задачи (3) остовное дерево мы будем называть также коммуникационным деревом (подграфом).

Известно, что рассматриваемая задача NP-трудна в сильном смысле [28,29].

Теорема 2. Если задача построения Я-приближенного решения задачи построения минимального вершинного покрытия на графе, степень вершин которого не превосходит к (fc-МВП), NP-трудна, то задача построения (1 + (Д-1 )/{к + 1))-приближенного решения задачи (3) NP-трудна.

Замечание 1. Известно, что задача построения (1 + приближенного решения для 4-МВП NP-трудна [30]. Тогда из Теоремы 2 следует NP трудность построения (1 + -приближенного решения задачи (3)

Замечание 2. В работе [31] доказано, что если Р ф NP, то не существует полиномиального алгоритма, решающего с гарантированной оценкой точности (1 + щ) частный случай задачи (3), в котором вершины графа расположены в R3, а веса ребер соответствуют расстояниям между вершинами, возведенным в степень а, где а > 1. Авторы использовали другое сведение задачи k-МВП к данному частному случаю, при этом использовалось дополнительное ограничение на степень графа: к < 5. Доказательство Теоремы 2 значительно проще доказательства, предлагаемого авторами работы [31], и формула, отражающая зависимость границы аппроксимируемости задачи (3) от границы аппроксимируемости задачи к-МВП (при произвольном к > 3) является новым результатом.

В разделе 2.2 рассмотрены некоторые полиномиально разрешимые частные случаи задачи (3). Так как остов минимального веса — это приближенное решение задачи (3), то особый интерес представляют случаи, когда минимальный остов является оптимальным коммуникационным деревом, т.е. решением задачи (3).

(3)

В разделе 2.3 уточнена гарантированная оценка погрешности для минимального остова.

Теорема 3. Пусть веса ребер, вошедших в минимальный остов Р, принадлежат отрезку [а, Ь], Т* оптимальное решение задачи (3). Тогда справедлива следующая достижимая оценка

и при п —У +оо

Этот результат позволяет, в частности, более точно оценить относительную погрешность для минимального остова на известных бесконечных регулярных решётках (например, в моделях покрытия, предложенных в [7]).

В разделе 2.4 предложены эвристические алгоритмы для приближенного решения задачи. Первый алгоритм (Ы) состоит из двух этапов. На первом этапе строится нижняя оценка оптимума задачи (3) путем решения задачи о минимальном остовном дереве относительно специальных весов ребер. На втором этапе к полученному дереву применяется процедура локальных улучшений. В качестве второго приближенного алгоритма (СА_Ы) предложен генетический алгоритм, который использует процедуру локальных улучшений алгоритма Ы к каждому новому решению, полученному в результате скрещивания. В начальную популяцию входит как минимальный остов для исходных весов графа б, так и минимальный остов для специальных весов, построенный на первом этапе алгоритма Ы.

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

В разделе 2.5 предлагается новая постановка рассматриваемой задачи в виде ЦЛП. Эта постановка использовалась для построения оптимального решения задачи с помощью СРЬЕХ при малой размерности. Предположим, что одна из вершин графа (пусть это вершина 1) является корнем искомого дерева Т, и будем считать, что все дуги дерева Т ориентированы от корня. Обозначим V] = {г € У|(г,.7') € Е}. Пусть переменная щ равна количеству дуг из корня в вершину г в искомом остовном дереве Т (при этом -щ = 0), а переменная х^ = 1, если дуга (г, принадлежит дереву Т и хц = 0 в противном случае. Тогда задача может быть записана в следующем виде:

а + Ь + 2Ь/(п-2)

2а

(4)

djXij < Ci, djXij < Cj, iev, j 6 V \ {1};

(7)

5>о = 1, jev\{i}-, (8)

iev,

1 - n(l - Xij) <UJ-Ui< 1 + n(l - Xij), (i,j) e E- (9)

Xij S {0,1}; щ G {l,...,n- 1; щ = 0. (10)

В третьей главе описывается комплекс программ, который был разработан на языке С++ для проведения численных экспериментов.

В разделе 3.1 описаны детали реализации программного комплекса, разработанного для осуществления численного эксперимента, который проводился для апостериорной оценки качества эвристических алгоритмов HI и Н2, предлагаемых в разделе 1.5. Для построения индивидуальной задачи UM2) на квадратной области случайно равномерно размещались сенсоры — точки с вещественными координатами. Для каждого сенсора случайным образом определялось исходное значение его ресурса. Для построения каждого покрытия случайным образом строилась регулярная треугольная решетка, и в качестве элементов покрытия выбирались сенсоры, ближайшие к узлам решетки. Таким образом строилась модель БСС для заданных входных параметров {п, т, d, rmin, rmax}, где п — количество сенсоров, m — количество покрытий, d — шаг треугольной решетки, и гтах — минимальное и максимальное значения исходного ресурса сенсора. Для каждого случайно сгенерированного тестового примера строилось точное решение задачи (1)-(2) с помощью пакета CPLEX, которое использовалось для вычисления относительной погрешности решений, построенных приближенными алгоритмами. Решения, построенные предложенными алгоритмами HI и Н2, сравнивались с решениями, построенными другими приближенными алгоритмами. Первый метод — это жадный алгоритм, в котором на каждом шаге выбирается покрытие с максимальным значением минимального ресурса входящих в него сенсоров, после чего ресурсы всех сенсоров выбранного покрытия пересчиты-ваются. Процесс продолжается, пока хотя бы у одного покрытия минимальный ресурс входящих в него сенсоров положительный. Второй метод состоит из симплекс-метода, решающего линейную релаксацию задачи (1)-(2) и последующего округления построенного симплекс-методом решения. Для одних и тех же входных параметров {n, т, d, rmin, гшах} запускалось 100 экспериментов. В конце раздела приведены таблицы и графики, на которых отражены полученные результаты. В частности, по графикам и таблицам видно,

11

что в большинстве случаев алгоритмы HI и Н2 работают лучше жадного алгоритма, а при малых значениях начальных ресурсов сенсоров — лучше симплекс-метода с округлением.

В разделе 3.2 приводится описание программы, разработанной для апостериорного анализа качества эвристических алгоритмов, предлагаемых в разделе 2.4 для приближенного решения задачи (3). Для построения одной индивидуальной задачи элементы сети случайно равномерно распределялись внутри квадратной области. В качестве весов ребер брались квадраты расстояний между вершинами. Для построения точного решения задачи использовался пакет CPLEX, на вход которого подавалась запись задачи в виде ЦЛП, сформулированная в разделе 2.5. Для одной и той же размерности генерировалось 100 различных примеров при п < 100, 50 примеров — при п — 150 и 25 примеров — при п > 200. В ходе эксперимента сравнивались решения, построенные различными приближенными алгоритмами: алгоритмом построения минимального остовного дерева, алгоритмом локальных улучшений, гибридным генетическим алгоритмом, в котором в качестве мутаций использовались локальные улучшения, и генетическим алгоритмом со случайными мутациями. Результаты эксперимента отражены в таблицах и графиках в конце раздела. Так, при п < 30 гибридный генетический алгоритм в среднем строил решение, отличающееся от оптимального не более чем на 0,6%, при этом при п = 10 оптимальное решение строилось в 98% случаев, при п = 20 — в 75% случаев, при п = 35 — в 28% случаев. При п = 30 алгоритм в среднем работал около 3 секунд, при п = 100 — около 85 секунд. С помощью CPLEX задачу удалось решить за приемлемое время (до 520 секунд) только при п < 35.

В заключении работы приведены основные результаты:

1. Предложена модель беспроводной сенсорной сети при заданном множестве покрытий. Предложена модель коммуникационной сети в виде произвольного графа с неотрицательными весами рёбер.

2. Осуществлён анализ сложности задач дискретной оптимизации в рамках предложенных моделей сетей сбора и передачи данных. Найдены новые полиномиально разрешимые случаи и определены достаточные условия существования полиномиальных алгоритмов решения поставленных задач с гарантированными оценками точности.

3. Разработаны новые приближенные алгоритмы решения рассматриваемых задач с апостериорной оценкой точности.

4. Создан и зарегистрирован комплекс программ и проведены численные эксперименты, показавшие высокую эффективность разработанных алгоритмов.

Список литературы

1. Dargie, W. and Poellabauer, С., Fundamentals of wireless sensor networks: theory and practice // John Wiley and Sons, 2010

2. Cardei, M, Du, D.-Z. Improving wireless sensor network lifetime through power aware organization // ACM Wireless Networks, 11, 2005, 333-340.

3. Jaggi, N, Abouzeid, A.A.: Energy-efficient connected coverage in wireless sensor networks // Proc. 4th Asian Int. Mobile Computing Conference (AMOC) 2006 - P. 77-86.

4. Zhao Q., Gurusamy M. Lifetime maximization for connected target coverage in wireless sensor networks // IEEE/ACM Transactions on Networking 16(6) 2008, 1378-1391.

5. Cardei I., Cardei M. Energy-efficient connected-coverage in wireless sensor networks // Int. J. of Sensor Networks, 3(3), 2008, 201-210.

6. Ерзин А.И., Залюбовский В.В. Задача выбора совокупности связных покрытий в беспроводных сенсорных сетях // Труды ИВМиМГ СО РАН. Новосибирск. Серия: Информатика. Вып. 8, 2008. - 23-28.

7. J. Wu, S. Yang Energy-Efficient Node Scheduling Models in Sensor Networks with Adjustable Ranges. - Int. J. of Foundations of Computer Science 2005 v 16, No. 1, p. 3-17.

8. Астраков C.H., Ерзин А.И., Залюбовский B.B. Сенсорные сети и покрытие плоскости кругами // Дискретный анализ и исследование операций, Т 16 № 3, 2009, 3-19.

9. Nguyen N.D., Zalyubovskiy V., На М.Т., Choo Н. Area coverage patterns for node scheduling problem to extend the network lifetime. Int. Conference on Information Networking 2010 (ICOIN 2010), Jan. 27-29, 2010, Busan, Korea.

10. Nguyen N.D., Zalyubovskiy V., На M.T., Choo H. Energy-efficient models for coverage problem using sensors with adjustable sensing range. IEEE Wireless Communication and Networking Conference (WCNC 2010), April 18-21, 2010, Sydney, Australia.

11. Wang W., Srivastan V., Chua K.-C. Using mobile relays to prolong the lifetime of wireless sensor networks // MobiCom'05, Cologne, Germany, 2005, 270-283.

12. Tong L., Zhao Q., Adireddy S. Sensor networks with mobile agents // Proc. Of IEEE Military Conference, MILCOM'03, 2003.

13. Somasundara A.A., Kansal A., Jea D.D., Estrin D., Srivastava M.B. Controllably mobile infrastructure for low energy embedded networks // IEEE Transaction on Mobile Computing, 2006.

14. Bi Y., Sun L., Ma J., Li N. Khan I.A., Chen C. HUMS. An autonomous moving strategy for mobile sinks in data-gathering sensor networks // Eurasip, 2007.

15. Marta M., Cardei M. Improved sensor network lifetime with multiple mobile sinks // Pervasive and Mobile Computing, 5(5), 2009, 542-555.

16. Wang D., Xie В., Agrawal D.P. Coverage and lifetime optimization of wireless sensor networks with Gaussian distribution // IEEE Transactions on Mobile Computing, 2008, 1444-1458.

17. Zalyubovskiy V., Erzin A., Astrakov S., Choo H. Energy-efficient Area Coverage by Sensors with Adjustable Ranges // Sensors, 9(4), 2009, 2446-2460.

18. Kulakov A., Davcev D.: Distributed algorithm for a mobile wireless sensor network for optimal coverage of non-stationary signals // Proc. 1st Workshop on Spatial Stochastic Modeling of Wireless Networks (SpaSWiN05), Riva del Garda, Italy, 2005.

19. Алдын-оол T.A., Ерзин А.И., Залюбовский B.B. Покрытие плоской области случайно распределенными сенсорами // Вестник НГУ. Серия: математика, механика, информатика. Т. 10, № 4, 2010, 7-25.

20. К. Роджерс. Укладки и покрытия. - М.: Мир. 1968. 137 с.

21. Л.Ф. Тот. Расположения на плоскости, на сфере и в пространстве. - М.: Изд. Физ.-мат. литературы. 1958. 365 с.

22. К. Boroczky, Jr. Finite Packing and Covering. Cambridge: Cambridge University Press. 2004. 398 p.

23. Berman, P., Galinescu, G., Shan, C., Zelikovsky, A. Power efficient monitoring management in sensor networks // Proc. of IEEE Wireless Communications and Networking Conference (Atlanta, USA, March 21 - 25, 2004) - P. 2329-2334.

24. Garg, N., Konemann, J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems // Proc. of FOCS, 1997.

25. Zuckerman, D. Linear degree extractors and the inapproximability of max clique and chromatic number // Proc. 38th ACM Symp. Theory of Computing, pp. 681-690

26. E. Althaus, et al. Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks. - Wireless Networks, 2006, v. 12, No. 3, p. 287-299.

27. Ghosh A., Das S.K. Coverage and connectivity issues in wireless sensor networks: A survey// Pervasive and Mobile Computing, 4(3), 2008. - P. 303 334.

28. L.M. Kirousis, E. Kranakis, D. Krizanc, A. Pelc. Power consumption in packet radio networks. - Theoretical Computer Science, 2000, No. 243, p. 289-305.

29. A.E.F. Clementi, P. Penna, R. Silvestri. On the Power Assignment Problem, in Radio Networks. - Electronic Colloquium on Computational Complexity (ECCC), (054), 2000.

30. Chlebik, M., Chlebikova, J. Inapproximability results for bounded variants of optimization problems - Electronic Colloquium on Computational Complexity, Report No. 26, 2003.

31. Fuchs, B. On the Hardness of Range Assignment Problems // Electronic Colloquium on Computational Complexity, Report No. 113, 2005.

Публикации автора по теме диссертации

1. Erzin A., Plotnikov R. Wireless sensor network's lifetime maximization problem in case of given set of covers // LNCS No.6786. 2011. P. 44-57.

2. Ерзин А.И., Плотников P.B. О максимизации времени функционирования сенсорных сетей при ресурсных ограничениях // Дискретный анализ и исследование операций. 2011. Т. 18, № 6. С. 17— 32.

3. Ерзин А.И., Плотников Р.В., Шамардин Ю.В. О некоторых полиномиально разрешимых случаях и приближенных алгоритмах

для задачи построения оптимального коммуникационного дерева // Дискретный анализ и исследование операций. 2013. Т. 20, № 1. С. 12-27.

Перевод: A. I. Erzin, R. V. Plotnikov, Yu. V. Shamardin. On Some Poly nomially Solvable Cases and Approximate Algorithms in the Optimal Com munication Tree Construction Problem. // Journal of Applied and Ihdustrial Mathematics, 2013, Vol. 7, No. 2, pp 142-152.

4. Ерзин А.И. Плотников P.B. Максимизация времени жизни сенсорной сети в случае заданного множества покрытий // Рос. конф. «Дискретная оптимизация и исследование операций». Новосибирск. 2010. с. 170.

5. Ерзин А.И. Плотников Р.В. Шамардин Ю.В. Об одной задаче построения коммуникационного остовного дерева // Мат. 5 Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск. 2012. с. 122.

6. Р.В. Плотников. Гибридный генетический алгоритм для задачи построения оптимального коммуникационного дерева // Мат. Межд. конф. «Дискретная оптимизация и исследование операций». Новосибирск. 2013. с. 141.

7. A.I. Erzin R.V. Plotnikov Y.V. Shamardin. Communication Spanning Tree Problem in Wireless Sensor Networks // Proc. of Int. Conf. and Summer School «Numerical Computations: Theory and Algorithms». Falerna, Italy, 2013, p. 119.

8. Р.В. Плотников. Апостериорный анализ качества эвристических алгоритмов для приближенного решения двух задач минимизации энергозатрат в сетях сбора и передачи данных (программа) // ФАП СО РАН, 2013. — Св-во о регистрации программы № PR13021 от 6 июня 2013 года.

Плотников Роман Викторович

ИССЛЕДОВАНИЕ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ СЕТЕЙ СБОРА И ПЕРЕДАЧИ ДАННЫХ ПРИ РЕСУРСНЫХ ОГРАНИЧЕНИЯХ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 9.10.2013 Формат 60x84 1/16

Усл. печ. л. 1 Уч.- изд. л. 1. ' Тираж 100 эк.

Заказ №249

Редакционно-издательский центр НГУ 630090, Новосибирск-90, ул. Пирогова, 2

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «НОВОСИБИРСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

04201 363378 На правах рукописи

ПЛОТНИКОВ РОМАН ВИКТОРОВИЧ

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

Специальность 05.13.18 — Математическое моделирование, численные методы и

комплексы программ

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель: д.ф-м.н., проф. Ерзин А.И.

Новосирибиск — 2013

Содержание

Введение 4

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

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

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

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

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

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

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

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

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

1.6.1 Описание алгоритмов........................................................28

1.7 Результаты и выводы к Главе 1....................................................31

2 Задача построения оптимального коммуникационного дерева 32

2.1 Постановка задачи и анализ сложности............................................33

2.2 Частные случаи......................................................................36

2.3 Оценки точности полиномиальных алгоритмов..................................37

2.4 Эвристические алгоритмы..........................................................39

2.4.1 Минимальный остов для специальных весов ребер графа..............40

2.4.2 Процедура локальных улучшений..........................................42

2.4.3 Гибридный генетический алгоритм........................................43

2.5 Постановка задачи в виде ЦЛП....................................................45

2.6 Результаты и выводы к Главе 2....................................................46

3 Комплекс программ для апостериорного анализа эвристических алгорит-

мов 48

3.1 Численный эксперимент для оценки эффективности алгоритмов решения задачи максимизации времени жизни БСС при заданном множестве покрытий 49

3.1.1 Программная реализация алгоритмов......................................49

3.1.2 Результаты численного эксперимента......................................53

3.2 Численный эксперимент для оценки эффективности алгоритмов решения задачи построения оптимального коммуникационного дерева..................63

3.2.1 Программная реализация алгоритмов......................................63

3.2.2 Результаты численного эксперимента......................................71

3.3 Результаты и выводы к Главе 3....................................................78

Заключение 80

Литература 81

Введение

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

а также дальности передачи и поиск оптимального расписания активности каждого сенсора.

Все перечисленные задачи в общих постановках являются КР-трудными [2,7,21,23,28,60], следовательно для них актуальна проблема построения приближенных эффективных алгоритмов и анализа их качества.

Проблемам, связанным с максимизацией времени жизни БСС, посвящено немалое количество публикаций. Так как для полноценного функционирования БСС требуется связность выбранного подмножества сенсоров, одной из важнейших проблем в БСС является задача построения связных покрытий. В [28] доказано, что задача нахождения максимального числа непересекающихся связных покрытий КтР-трудна. Приближенные алгоритмы нахождения связных покрытий предлагаются в работах [27,45,63]. В [7] рассмотрена задача выбора совокупности связных покрытий, обеспечивающих максимальное время жизни сети и предлагается эвристический метод ее решения. Эффективным способом продления времени жизни БСС является возможность регулирования областей мониторинга и дальности передачи. В [60] предложено несколько моделей покрытия области сенсорами с адаптивными радиусами мониторинга и связи. В [60] предложено несколько моделей покрытия области сенсорами с адаптивными радиусами мониторинга и связи. В [2] рассмотрены новые модели покрытия с адаптивными радиусами мониторинга и связи, которые обеспечивают существенный выигрыш в расходе энергии но сравнению с известными ранее. Работа по отысканию эффективных моделей покрытия с адаптивными радиусами мониторинга и связи продолжена в [52,53]. В статических БСС зачастую происходит неравномерное использование сенсоров, поэтому мобильность сенсоров также может быть использована как средство уменьшения энергопотребления. В [25,50,56-58] исследованы различные модели с использованием мобильных устройств. Результаты экспериментов показывают, что мобильность позволяет существенно продлить время жизни БСС. Часто детерминированное размещение сенсоров оказывается пецелесо-

образным (например, при большом числе сенсоров) или неосуществимым (театр боевых действий или зараженная территория), а различные препятствия и другие внешние факторы могут привести к помехам при обмене данными и мониторинге. Поэтому для поддержания функционирования БСС часто требуется учитывать вероятностный характер расположения сенсоров и других характеристик. В [59] рассмотрен случай, когда сенсоры распределены случайно в соответствии с распределением Гаусса. В [61] экспериментально исследована возможность обеспечения гарантированного покрытия при случайном распределении сенсоров за счет незначительного увеличения радиусов мониторинга. Анализ влияния неопределенностей, связанных с передачей информации, проведен в [49]. В [1] впервые найдены аналитические оценки снизу на время жизни БСС в случае равномерного случайного распределения сенсоров в плоской области мониторинга. В [44] рассматривается задача минимизации энергопотребления БСС в случае если сенсоры прерывают работу в соответствии со случайным процессом Маркова. В традиционных моделях БСС зона мониторинга (покрытия) сенсора - это круг, радиус которого может меняться в заданных пределах. При этом энергозатраты сенсора пропорциональны покрытой им площади, и задача эпергоэффективпого мониторинга сводится к задаче построения наименее плотного покрытия плоской области кругами различных радиусов. Подобные задачи сравнительно хорошо изучены и им посвящено множество публикаций по комбинаторной (вычислительной) геометрии, среди которых выделим монографии [18,19,26]. Различные модели сетей передачи данных исследованы в работах [15] [17].

В работе [23] сформулирована задача максимизации времени жизни БСС в случае, когда множество покрытий не задано, а переменные, соответствующие временам функционирования покрытий, непрерывны, в виде частного случая задачи линейного программирования (packing linear program) и предлагается метод ее решения, основанный на алгоритме Гарга-Кенеманна (Garg-Konemann) [40]. В работе [36] рассматривается более общая задача с

регулируемыми радиусами мониторинга в аналогичной постановке. Для её приближенного решения авторам удалось обобщить метод, предложенный в [23]. В работе [47] рассматривается задача максимизации времени жизни БСС в случае, когда ресурсы всех вершин одинаковые. Для приближенного решения задачи предложен алгоритм, который строит множество покрытий с минимальным количеством многократно покрываемых объектов, используя метод ветвей и границ, н работает, пока сенсоры, ресурс которых не израсходован, покрывают все объекты. При этом время функционирования одного покрытия задано входным параметром w. В ходе численного эксперимента предложенный алгоритм сравнивался с алгоритмом Grccdy-MSC [28]. В работе [27] для каждого сенсора задано множество объектов, которые он покрывает, и требуется построить множество непересекающихся покрытий, суммарное время жизни которых максимально.

В работе [21] рассматривается задача построения минимального коммуникационного дерева в простом реберно-взвешенном неориентированном графе в евклидовом пространстве. Эта задача называется Min-Power Symmetric Connectivity Problem [21]. Подобные задачи возникают, например, в беспроводных сенсорных сетях, когда расположение сенсоров известно, элементы сети способны регулировать дальность передачи, и требуется синтезировать эпергоэффективиый граф, связывающий все сенсоры [60]. Если предположить, что радиосигнал одинаково распространяется во всех направлениях, то все элементы, находящиеся в зоне передачи (не далее, чем дальность передачи), получат сообщение. В этом случае можно считать, что коммуникационная сеть (остовный подграф по рёбрам которого осуществляется передача) — это полный граф [21,29,48,54]. Однако не всегда сигнал распространяется одинаково во всех направлениях и на любое расстояние. Поэтому в общем случае следует считать, что коммуникационный граф G — (V, Е) может быть произвольным остовным подграфом, как и потери энергии по обеспечению передачи по ребру графа. Часто в литературе в качестве коммуникационного

графа сенсорной сети принято рассматривать остовнос дерево минимального веса Р, когда вес ребра, связывающего пару вершин, — это квадрат расстояния между этими вершинами [60]. Однако минимальный остов не всегда является оптимальным коммуникационным графом сенсорной сети.

Известно, что рассматриваемая задача МР-трудпа в сильном смысле [21, 39,48] и при условии N ф NP задача неаппроксимируема с коэффициентом

1 + 250 [39].

В работе [48] исследовалась задача определения дальности передачи каждой вершины, размещённой в евклидовом пространстве таким образом, чтобы индуцировать сильно связный граф, в котором общие энергозатраты на связь минимальны. Для частных случаев, когда вершины расположены на прямой, предложены полиномиальные алгоритмы решения задачи. Доказана ХР-трудность задачи в трехмерном евклидовом пространстве.

Авторами работы [21] для метрической задачи предложен алгоритм с асимптотической точностью 5/3, полиномиальный алгоритм, строящий 11/6-приближённос решение, а также точный алгоритм — метод ветвей и границ, в котором используется новая постановка задачи в виде задачи целочисленного линейного программирования.

В работе [29] рассмотрена задача определения мощностей радиопередатчиков для передачи данных на два расстояния: "малое" и "большое". Показана КР-трудность этой задачи. Предложен полиномиальный алгоритм, который строит решение с числом передатчиков на большие расстояния, не превосходящим 11/6 от числа таких передатчиков в оптимальном решении. Также предложен экспоненциальный 9/5-приближенный алгоритм. Эти результаты получены для случая, когда элементы распределены в евклидовом пространстве, однако легко обобщаются и на произвольную метрику.

Все рассматриваемые в диссертации проблемы являются ИР-трудными задачами дискретной оптимизации. Введем ряд основных определении, относящихся к исследованию таких задач.

Задачей оптимизации называют всякую задачу, в которой требуется найти наилучшее (по указанному критерию) решение из заданного множества допустимых решений. Математической моделью задачи оптимизации, согласно [5], называют описание задачи в математических терминах. При этом, как правило, множество допустимых решений задастся в виде списка ограничений — равенств или неравенств, а качество решения численно оценивается целевой функцией. Оптимальным решением задачи оптимизации является допустимое решение, при котором значение целевой функции минимально (или максимально).

Среди задач оптимизации выделяют задачи

• линейного программирования: тах{сж : Ах < Ь, х £ М+};

• целочисленного линейного программирования: тах{сх : Ах < 6, ж £

• булевого линейного программирования: тах{сж : Ах < 6, ж £ В71},

где векторы с € М", Ь Е Мт и матрицы А. В £ Ятхп заданы, а х является п-мерный вектором переменных. Если целевая функция или ограничения нелинейные, то такая задача называется нелинейной.

Задачами дискретной (или комбинаторной) оптимизации называют задачи оптимизации, в которых переменные принимают значения из конечного множества. Такие задачи могут быть решены за конечное время методом полного перебора, в связи с этим их также называют переборными [6]. Обычно трудоемкость полного перебора экспоненциально зависит от размерности задачи, поэтому основной целью исследования задач дискретной оптимизации является разработка наименее трудоемких алгоритмов, строящих оптимальное или близкое к оптимальному решение.

Введем основные определения, связанные с теорией КтР-полных задач, которые понадобятся для дальнейшего изложения. Согласно определению,

предложенному в работе [32], класс NP (от англ. поп-deterministic polynomial time) — это класс задач распознавания свойств (т.е. задач, решением которых может быть либо «да», либо «нет»), разрешимых за полиномиальное время на недетерминированном вычислительном устройстве. Задача из класса NP называется NP-полгюй, если к ней полиномиально сводится любая задача из класса NP. До сих пор остается открытым вопрос о полиномиальной разрешимости NP-полных задач. NP-трудной, согласно [12], называется любая задача (не обязательно из класса NP), к которой полиномиально сводится любая задача из класса NP.

Пусть задача дискретной оптимизации сформулирована следующим образом: «Найти в заданном множестве допустимых решений Q решение, при котором функция / достигает минимального значения». Такой задаче соответствует следующая задача распознавания: «Найдется ли в множестве Q решение, при котором выполнено неравенство: f(x) < L?», где L некоторое заданное число. Класс задач дискретной оптимизации, которым соответствуют задачи распознавания из класса NP, называется NPO (от англ. поп-deterministic polynomial time optimization). Решить задачу из NPO достаточно для того, чтобы решить соответствующую задачу распознавания, а значит из NP-полноты задачи распознавания следует NP-трудность соответствующей ей задачи дискретной оптимизации. Для доказательства NP-трудности задачи дискретной оптимизации достаточно показать, что задача распознавания, соответствующая некоторому частному случаю рассматриваемой задачи, NP-полна.

Для каждой индивидуальной задачи I из класса NP определим две величины: N(I) — размерность задачи, М(1) — максимальный числовой параметр в I. Согласно [6], алгоритм, решающий некоторую массовую задачу Р из класса NP обладает псевдополиномиальной трудоемкостью, если его временная функция ограничена сверху некоторым полиномом от двух аргументов N(1) и М(1). Для произвольной задачи Р из NP и полинома р обозначим

через Рр подзадачу задачи Р, для которой выполняется следующее условие: V/ £ Рр М{1) < p{N{I)). Задача Р из NP является NP-полной в сильном смысле, если существует такой полином р, что задача Рр NP-полпа. Из этого определения следует, что NP-полная в сильном смысле задача не может быть решена псевдополиномиальным алгоритмом в случае, если Р ф NP. Задача из NPO называется NP-тпрудпой в сильном смысле, если ей соответствует NP-полная в сильном смысле задача распознавания.

Существование полиномиальных алгоритмов для точного решения NP-трудных задач является открытым вопросом, поэтому для них актуальны разработка и анализ эффективных приближенных алгоритмов. Качество приближенных алгоритмов часто оценивается относительной точностью и а (/) = либо относительной погрешностью (Тд(1) = ^, где

fA(I) — значение целевой функции на решении индивидуальной задачи I, построенн