EN|RU

Том 18, номер 6, 2011 г., Стр. 17-32

УДК 519.8
Ерзин А. И., Плотников Р. В.
О максимизации времени функционирования сенсорных сетей при ресурсных ограничениях

Аннотация:
Рассматривается задача максимизации времени жизни сенсорной сети в условиях ограниченности ресурсов сенсоров в виде задачи целочисленного линейного программирования, в которой при заданном множестве покрытий требуется определить время функционирования каждого покрытия. При этом ресурс сенсора задаётся количеством временных раундов, в течение которых он может находиться в активном состоянии. Доказана NP-трудность задачи в сильном смысле. Предложены способы её упрощения. Показано, что для любого $\varepsilon>0$ задача в общем случае не аппроксимируема полиномиальными алгоритмами с точностью $O(m^{1-\varepsilon})$, где $m$ – число покрытий. Найдены частные случаи, когда задача полиномиально разрешима. Предложено несколько эвристических алгоритмов построения приближённого решения задачи и проведён апостериорный анализ.
Табл. 1, библиогр. 18.

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

Ерзин Адиль Ильясович 1,2
Плотников Роман Викторович 2

1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: adilerzin@math.nsc.ru, nomad87@ngs.ru

Статья поступила 12 апреля 2011 г.
Исправленный вариант — 16 июня 2011 г.

 © Институт математики им. С. Л. Соболева, 2015