О максимизации времени функционирования сенсорных сетей при ресурсных ограничениях

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