Исследование оптимизационных моделей сетей сбора и передачи данных при ресурсных ограничениях тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Плотников, Роман Викторович

• Плотников, Роман Викторович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Плотников, Роман Викторович

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

мов

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

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

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

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

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

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

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

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Исследование оптимизационных моделей сетей сбора и передачи данных при ресурсных ограничениях»

Введение

Работа посвящена исследованию задач дискретной оптимизации, связанных с минимизацией энергопотребления сетей сбора и передачи данных на примере беспроводных сенсорных сетей (БСС). В современной литературе [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, построенном алгоритмом А, /* — оптимальное значение целевой функции для индивидуальной задачи I. Если для некоторой NP-трудной задачи Р на минимум (или па максимум) удается построить такой алгоритм А, что Зе > 0 : V/ £ Р ша{1) < £ (или cja(I) > е), то про алгоритм А говорят, что он обладает гарантированной оценкой точности е. Классом АРХ (от англ. approxirnable) называется множество задач из класса NPO, для которых существуют полиномиальные алгоритмы с гарантированными оценками точности.

Если Me > 0 и V/ € Р алгоритм А строит приближенное решение задачи с гарантированной оценкой относительной погрешности оа{1) < то такой алгоритм называется аппроксимационной схемой. Если при любом фиксированном значении £ трудоемкость алгоритма А ограничена полиномом от длины входа, то он называется полиномиальной приближенной схемой (PTAS — polynomial time approximation scheme). Если трудоемкость алгоритма А ограничена полиномом от длины входа и величины 1/е, то он называется

вполне полиномиальной приблиэюениой схемой (FPTAS — fully polynomial time approximation schcmc).

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

Изложение материала организовано следующим образом.

В главе 1 рассматривается задача минимизации времени жизни сенсорной сети, аналогичная по постановке задаче, сформулированной авторами работы [23], в условиях заданного избыточного множества покрытий и целочисленных переменных, соответствующих количеству временных раундов, в течение которых покрытие функционирует. Задача сформулирована в виде ЦЛП и показано, что частный случай рассматриваемой задачи является NP-трудной в сильном смысле Задачей о максимальной упаковке миоснсеслпв (МУМ). Следовательно, известные результаты по неаппроксимируемости задачи МУМ актуальны для рассматриваемой проблемы. Найдены дополнительные условия, при которых существует полиномиальный алгоритм решения задачи с гарантированной оценкой точности. Для некоторых полиномиально разрешимых частных случаев предложены новые эффективные алгоритмы построения точного решения. Для построения приближенного решения предложены эвристические алгоритмы и проведен апостериорный анализ качества, показавший их высокую эффективность.

Результаты автора, изложенные в данной главе, опубликованы в работах [8,9,37].

В главе 2 исследуется задача построения оптимального коммуникационного дерева в произвольном графе с неотрицательными весами ребер. Найдена более точная гарантированная оценка точности для решения рассматриваемой проблемы построением минимального остовного дерева и приведены полиномиально разрешимые частные случаи задачи. Найдена новая формула для определения границы аппроксимируемости задачи, которая, в частности, доказывает неаппроксимируемость задачи с коэффициентом 1 + ^ (при Р Ф NP) проще, чем в работе [39]. Для приближенного решения предлагаются эвристические алгоритмы и проведен численный эксперимент, показавший их высокую эффективность.

Результаты автора, изложенные в данной главе, опубликованы в работах [10,11,14,38].

В главе 3 описаны детали реализации программного комплекса, разработанного для апостериорной оценки качества эвристических алгоритмов, которые предлагаются в главах 1 и 2 для построения приближенного решения рассматриваемых задач. Также, в главе 3 приводятся таблицы и графики, отражающие результаты экспериментов и сформулированы выводы, вытекающие из них. В целом, численные эксперименты подтвердили высокую эффективность предлагаемых алгоритмов. Разработанная программа зарегистрирована в Фонде алгоритмов и программ СО РАН [13].

Работа завешается заключением, в котором кратко перечислены основные результаты.

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

2012г.), на 5-ой Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Россия, г. Омск, 2012г.), на семинарах Института математики им. C.JT. Соболева СО РАН и кафедры Теоретической кибернетики Новосибирского государственного университета (2010-2013гг.); на Международной конференции «Дискретная оптимизация и исследование операций» (г. Новосибирск, 2013 г.), на Международной конференции «Numerical Computations: Theory and Algorithms» (NUMTA2013) (Италия, г.Фалерна, 2013г.).

Глава 1

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

В данной главе исследуется модель БСС в случае, когда множество покрытий задано, расход энергии в единицу времени одинаковый для всех сенсоров, и время активности каждого сенсора измеряется в количестве временных тактов, т.е. принимает целочисленные значения. При таких условиях ресурс сенсора можно выразить в максимальном количестве временных тактов, в течение которых сенсор может находиться в активном состоянии. Тогда задача максимизации времени жизни БСС записывается в виде задачи целочисленного линейного программирования. Показана ^тР-трудность в сильном смысле рассматриваемой задачи, а также отсутствие полиномиальной приближенной схемы для ее решения в том случае, если Р ф NP. Найдены полиномиально разрешимые частные случаи задачи. Определены дополнительные условия, при которых существует полиномиальный алгоритм решения задачи с гарантированной оценкой точности. Предложены эвристические алгоритмы для приближенного решения задачи. Эффективность предложенных алгоритмов подтверждена численным экспериментом, описание которого приведено в главе 3.

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

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

т

^гдь-^тах; (1.1)

к= 1

3 £ 3 . (1.2)

к= 1

Для каждого покрытия Ск Е С определим его ресурс гк, который равен минимальному начальному ресурсу входящих в него сенсоров. Очевидно, величина гк ограничивает сверху время жизни покрытия Ск- Минимальный и максимальный начальные ресурсы сенсоров множества 3 обозначим через Гщш и гтах соответственно. Назовем сенсор дефицитным, если его ресурс меньше суммы ресурсов содержащих его покрытий.

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

Расмотрим частный случай задачи (1.1)-(1.2) (когда ресурс каждого сенсора единичный):

> Ук тах ; (1.3)

¿Г

т

Х>ш<1, (1-4)

к=\

Замечание 1.1. Задача (1.3)-(1.4) состоит в поиске максимального количества непересекающихся подмножеств заданного множества. Это известная АгР-трудная в сильном смысле задача о максимальной упаковке множеств (МУМ) [6]. Из N ¡^-трудности задачи (1.:!)-(!.4) следует МР-трудность более общей задачи (1.1)-(1.2)

Замечание 1.2. Известно, что задача МУМ полиномиально эквивалент,-на задаче о максимальной клике (МК) с совпадением целевых функций [46], и, следовательно, она также полиномиально эквивалентна задаче о максимальном независимом множестве (МНМ) на графе пересечений покрытий. Наиболее сильным из известных результатов по неаппроксимируемости задачи МК является утверждение, доказанное в работе /64/ о толь, что при условии Р ф МР МК не может быть полиномиально аппроксимирована с точностью 0(гп}~£) при произвольном е > 0. Следовательно, задача (1.!)-(!.2) не аппроксимируема с коэффпщиентом 0{тХ е) для любого е > 0.

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

Иногда БСС содержит сенсоры, которые можно (виртуально) исключить, а также множество покрытий иногда удастся сократить, не уменьшая время жизни БСС. Рассмотрим следующие случаи.

1. Cj С Сг. Очевидно, в этом случае покрытие Сг- можно (виртуально) удалить, т.к. при его активности расходуются ресурсы как вершин покрытия С3, так и других сенсоров, входящих в Сг-.

Будем говорить далее, что вектор а = (аь ..., ап) доминирует, вектор Ь = (Ь\,... ,Ьп) если для всех г £ {1,... ,п} а^ < Заметим, что опи-

санное выше исключение покрытий равносильно удалению из матрицы ограничений задачи (1.1)-(1.2) доминируемых столбцов.

2. Два сенсора входят в одни и те же покрытия. В этом случае их ресурсы расходуются одновременно, поэтому сенсор с большим ресурсом может быть (виртуально) исключен из J. Следовательно, если к сенсоров принадлежат одним и тем же покрытиям, то из них можно оставить один сенсор с минимальным ресурсом.

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

После применения описанных выше правил, останутся только дефицитные сенсоры, в матрице ограничений В = ||&jj|| всс строки будут различны, и ни один столбец не будет доминировать какой-либо другой столбец.

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

Зафиксируем значения параметров a, b и S: 0 < а < Ь, 5 > 3 Пусть задача Ра.ь,б ~~ сужение задачи (1.1)-(1.2), в котором ресурс каждого сенсора принадлежит отрезку [а, 6], и каждое покрытие пересекается не более чем с S другими покрытиями.

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

Доказательство. Рассмотрим МНМ для графа, степень которого равна S, и обозначим такую задачу как МНМ-i. Известно [22], что эта задача принадлежит классу АРХ: для любого фиксированного значения s > 0 найдется такой полиномиальный алгоритм Ае, что для любой индивидуальной задачи МНМ-$ выполняется неравенство

где Р£ — мощность независимого множества, построенного алгоритмом А£, Р* — оптимальное значение функционала. Для произвольной индивидуальной задачи I Е Ра.ь,б рассмотрим граф пересечений покрытий Степень этого графа не превосходит 6. Пусть 5 > 0. Применим алгоритм Ае к МНМ-<5 в графе (7. Пусть Р£ — мощность независимого множества вершин графа, построенного алгоритмом А£, Г* — мощность максимального независимого множества графа С. Согласно (1.5) выполняется неравенство

£> 5 .

р* ~ 8 + 3 + е

Алгоритм Ае выбирает непересекающиеся покрытия, а значит строит допустимое решение задачи I. Пусть \¥£ — время жизни БСС, определяемое построенным решением, а Ш* — максимальное время жизни БСС. Время жизни каждого выбранного покрытия равно ресурсу этого покрытия, поэтому Щ: > Гти^е- Пусть к — хроматическое число графа С. Тогда Р* > Известно [20], что к < 5 + 1. Поэтому Р* > Так как \¥* < гтахт, то И'*<($ + 1 )ГпиасГ*, и

Список литературы диссертационного исследования кандидат наук Плотников, Роман Викторович, 2013 год

Литература

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

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

3. Ван дер Варден Б.Л. Математическая статистика. М.: ИЛ. 1960. 436 с.

4. Гамма Э., Хслм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования - СПб.: Питер. 2001. 366 с.

5. Гимади Э. X., Глебов Н. И. Экстремальные задачи принятия решений // Учеб. пособие. Новосибирск: Изд-во НГУ. 1982. 79с.

6. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М: Мир. 1982. 416 с.

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

8. Ерзин А.И., Плотников Р.В. Максимизация времени жизни сенсорной сети в случае заданного множества покрытий // Рос. конф. «Дискретная опти-

мизация и исследование операций». Новосибирск: Изд-во Института математики. 2010. С. 170.

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

10. Ерзин А.И., Плотников Р.В., Шамардин Ю.В. О некоторых полиномиально разрешимых случаях и приближенных алгоритмах для задачи построения оптимального коммуникационного дерева. Дискретный анализ и исследование операций, Т. 20, № 1, 2013, с.12-27.

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

12. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир. 1985. 512 с.

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

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

15. Подкорытов Д.И. Агептно-ориентированная среда моделирования сетевых систем AGNES // Ползуновский вестник. 2012. № 2/1. С. 94-99.

16. Попков В. К. Математические модели связности. Новосибирск: ИВМиМГ СО РАН. 2006. 490 с.

17. Попков В. К., Блуккс В. П., Дворкин А. Б. Модели анализа устойчивости и живучести информационных сетей // Проблемы информатики. 2009. №4. С. 63-78.

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

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

20. Харари Ф. Теория графов. М: Мир. 1973. 296 с.

21. Althaus Е., et al. Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks. - Wireless Networks. 2006. Vol. 12. No. 3. P. 287-299.

22. Bcrman P., Fnjito T. Approximating independent sets in degree 3 graphs // Proc. 4th Workshop on Algorithms and Data Structures, LNCS Vol. 955. Springer-Verlag. 1995. P. 449-460.

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. Berman P., Karpinski M. On some tighter inapproximability results. Tech. Report TR98-065. ECCC. 1998.

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

26. Boroczky K., Jr. Finite Packing and Covering. Cambridge: Cambridge University Press. 2004. 398 p.

27. Cardci M., Ding-Zhu D. Improving wireless sensor network Lifetime through power aware organization // Springer Science, Business Media, Wireless Networks 11, Netherlands. 2005. P. 333-340.

28. Cardei M., Thai M. T., Li Y., Wu W. Energy-efficient target coverage in wireless sensor networks // In IEEE Infocom 2005. 2005. Vol. 3. P. 1976-1984.

29. Carmi P., Katz M.L. Power Assignment in Radio Networks with Two Power Levels. - Algorithinica. 2007. No. 47. P. 183-201.

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

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

32. Cook S.A., The complexity of theorem-proving procedures, // Proc. 3rd Ann. ACM Symp. on Theory of Computing. 1971. P. 151-158.

33. Dreo J., Petrowski A., Siarry P., Taillard E. Metaheuristics for Hard Optimization // Springer, 2006. 369 p.

34. Diane M., Plesnik J. An Integer Programming Formulation of the Sterner Problem in Graphs. - Methods and Models of Operations Research. 1993. No. 37. P. 107-111.

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

36. Dhawan A., Vu C. T., Zelikovsky A., Li Y., Prasad S. K. Maximum lifetime of sensor networks with adjustable sensing range // 7th ACIS Int. Conf. on Software Engineering, Artificial Intelligence, Networking, and

Parallel/Distributed Computing (SNPD'06) (Las Vegas, Nevada, USA, June 19-20, 2006). - P. 285-289.

37. 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.

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

38. Erzin A.I., Plotnikov R.V., Shamardin Y.V. Communication Spanning Tree Problem in Wireless Sensor Networks // Proc. of the Int. conf. «Numerical Computations: Theory and Algorithms». Falerna, Italy, June 17-23 2013. P. 119.

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

40. Gar g N., Konernann J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems // Proc. 39th Annual Symposium on Foundations of Computer Science (Palo Alto, CA, USA, November 8-10, 1997). - P. 300-309.

41. Gavril F. Algorithms on circular-arc graphs // Networks 4, 1974 - P. 357-369.

42. Ghouila-IIouri A. Caract'erisation des matrices totalement unimodulaircs // Comptes Rendus Hebdomadaires des S'eances de l'Acad'cmie des Sciences, Paris, 1962. - P. 1192-1194.

43. Hopcroft J., Karp R,. An n5/2 algorithm for maximum matchings in bipartite graphs // SI AM Journal on Computing 2, 1973. - P. 225-231.

44. Inane M., Magdon-Ismail M., Yener B. Power Optimal Connectivity and Coverage in Wireless Sensor Networks // Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, 2003.

45. 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.

46. Karp R. Reducibility Among Combinatorial Problems // In Complexity of Computer Computations. 1972. P. 85-103

47. Kim Y., Lee H., Han, Y. Jcongc, Y. A Branch and Bound Algorithm for extending the lifetime of wireless sensor networks // IEEE 70th Vehicular Technology Conference Fall (VTC 2009-Fall) (Anchorage, AK, September 20-23, 2009). P. 1-5.

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

49. Kulakov A., Davccv 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.

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

51. Mucha M., Sankowski P. Maximum Matchings via Gaussian Elimination // Proc. 45th Annual IEEE Symposium on Foundations of Computer Science 2004 (Washington, DC, USA, October 17-19, 2004 ). P. 248-255.

52. Nguyen N.D., Zalyubovskiy V., Ha M.T., Choo H. 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.

53. Nguyen N.D., Zalyubovskiy V., Ha M.T., Choo H. Energy-efficient models for coverage problem using sensors with adjustable sensing range. IEEE Wireless Communication and Networking Conference (WCNC 2010). IEEE. 2010. P. 1-6.

54. Pottic G.J., Kaiser W.J. Wireless Integrated Network Sensors. -Communications ACM. 2000. Vol. 43. No. 5. P. 51-58.

55. Prim R. C. Shortest connection networks and some generalizations. In: Bell System Technical Journal, 36. 1957. P. 1389-1401

56. 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.

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

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

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

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

61. Zalyubovskiy V., Erzin A., Astrakov S.; Choo II. Energy-efficient Area Coverage by Sensors with Adjustable Ranges // Sensors. 2009. 9(4). P. 24462460.

62. Zhang H., Hou J.C. Maintaining Sensing Coverage and Connectivity in Large Sensor Networks. - Ad Hoc & Sensor Wireless Networks. 2005. Vol. 1. No. 1-2. P. 89-124.

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

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