Исследователи НГУ доработали труднорешаемую задачу на построение энергоэффективных беспроводных коммуникационных сетей. При использовании нового алгоритма на решение уходит всего 10 секунд вместо прежних 16 минут.
Фундаментальная задача заключалась в том, чтобы построить связную коммуникационную сеть с минимальной суммарной мощностью передачи узлов. В 2017 году теоретическое решение было найдено заведующим лабораторией алгоритмики ММФ НГУ Рене ван Беверном и его берлинскими коллегами, за что ученые удостоились премии большого Европейского конгресса по алгоритмам.
Однако вопрос о практической ценности изобретенного алгоритма остался незатронутым. В 2018 году Павел Смирнов (сейчас аспирант 1-го курса ММФ НГУ) занялся изучением этого вопроса и пришел к выводу, что в предложенной форме на практике алгоритм практически неконкурентоспособен. Студент ускорил алгоритм как в теоретическом, так и в практическом аспектах.
«Есть практический интерес в том, чтобы решать ее за разумное время. С теоретической же точки зрения, более близкой лично для меня, задача интересна тем, что она NP-трудна, то есть решать быстро в общем случае ее, по-видимому, нельзя. Предыдущие подходы к решению основывались на решении задачи целочисленного программирования. Мы же попытались потягаться с этими подходами методами параметризации и достигли определенного успеха», - пояснил Павел Смирнов.
Беспроводные датчиковые сети применяют для мониторинга экологической обстановки. Чаще всего они работают на батареях, поэтому вопрос энергоэффективности беспроводной коммуникационной сети напрямую связан с длительностью их эксплуатации.
