Ученые исследовали фундаментальную труднорешаемую задачу на построение энергоэффективной беспроводной коммуникационной сети: требуется назначить каждому узлу сети такую мощность передачи, чтобы они смогли передавать свои данные на базовую станцию, возможно, через другие узлы. Иными словами, требуется построить связную коммуникационную сеть с минимальной суммарной мощностью передачи узлов.
Беспроводные датчиковые сети используются для мониторинга экологической обстановки (загрязнения воздуха и водоемов, лесных пожаров, оползней). Часто датчики питаются от батареек, так что срок эксплуатации датчиковой сети зависит от энергоэффективности их беспроводной коммуникационной сети.
В 2017 году заведующий
лабораторией алгоритмики ММФ Рене ван Беверн вместе с Берлинскими коллегами доказали, что теоретически задача имеет эффективный алгоритм решения, когда сеть с n узлами уже состоит из O (log n) связных компонент, которые нужно связать при минимальном увеличении суммарной мощности передачи. Эта ситуация возникает, например, когда ранее связанная сеть распадается на несколько компонент впоследствии выхода из строя узлов сети, или когда мониторятся несколько областей, в каждой из которых узлы расположены с достаточно регулярной структурой. Структура же возникает, когда минимизируются пересечения области сканирования датчиков (тоже в целях энергоэффективности). За теоретический результат ученые из НГУ и Берлина в 2017 году
получили премию на большом Европейском конгрессе по алгоритмам. Математически было доказано, что их алгоритм для достаточно больших n будет работать во сколько угодно раз быстрее, чем известные алгоритмы: трудоемкость их алгоритма растет полиномиально по n, в то время как трудоемкость ранее известных алгоритмов растет экспоненциально.
Оставался открытым вопрос о практической ценности алгоритма: а не получится ли так, что новый алгоритм будет быстрее только для таких n, превышающих число частиц во Вселенной? Этим вопросом в 2018 году занялся Павел Смирнов, тогда магистрант ФИТ НГУ и теперь аспирант 1-го курса ММФ НГУ. Выяснив, что алгоритм в самом деле в предложенной форме практически неконкурентоспособен, он ускорил алгоритм и на практике, и в теории, что стало главным результатом его магистерской работы и статьи в Q1-журнале INFORMS Journal on Computing.
— С одной стороны, у самой задачи есть приложения в области беспроводных сетей. Есть практический интерес в том, чтобы решать ее за разумное время, — прокомментировал Павел. — С теоретической же точки зрения, более близкой лично для меня, задача интересна тем, что она NP-трудна, то есть решать быстро в общем случае ее, по-видимому, нельзя. Предыдущие подходы к решению основывались на решении задачи целочисленного программирования. Мы же попытались потягаться с этими подходами методами параметризации и достигли определенного успеха.
Даже на маленьких сетях с n=200 узлами и пятью несвязными компонентами новый алгоритм (слева в рисунке) работает до 100 раз быстрее, чем ранее известный алгоритм (справа) для оптимального решения задачи: новый алгоритм справляется за 10 секунд вместо 16 минут, при этом преимущество нового алгоритма только возрастает по увеличению сети. Стоит отметить, что обоим алгоритмам была поставлена задача только «досвязать» сеть, то есть они оба используют особенную структуру датчиковой сети, подаваемой на входе.
