Предлагается обзор математических постановок и современных методов решения проблем дискретной оптимизации, которые возникают в беспроводных сенсорных сетях (БСС). Представлены новые результаты для 1) задачи построения совокупности связных покрытий в условиях ограниченности ресурсов сенсоров; 2) задачи максимизации времени жизни БСС; 3) задачи поиска энергоэффективных регулярных покрытий плоскости сенсорами с регулируемыми радиусами мониторинга и связи; 4) задачи построения оптимального коммуникационного графа БСС; 5) задачи вероятностной оценки эффективности сенсорной сети при случайном распределении сенсоров в области мониторинга; 6) задачи максимизации времени жизни БСС в случае мобильных сенсоров. Например, для проблемы 3 предложены новые регулярные покрытия, которые превосходят по эффективности известные ранее и являются оптимальными в некоторых классах покрытий. Решение задачи 4 в литературе сводится к построению минимального остовного дерева. Нами показано, что такое дерево не всегда является оптимальным. Более того, мы доказали, что задача построения оптимального коммуникационного дерева в БСС является NP-трудной проблемой и предложили приближенные алгоритмы с априорными оценками. Предложен алгоритм решения задачи 6 в частном случае.
Примечание. Тезисы докладов публикуются в авторской редакции
Ваши комментарии Обратная связь |
[Головная страница] [Конференции] |
© 2009, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 1996-2009, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:52)