Институт вычислительной математики и математической геофизики СОРАН

Тезисы докладов

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

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 2007, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 2007, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:51)