Ученые исследовали фундаментальную труднорешаемую задачу на построение энергоэффективной беспроводной коммуникационной сети: требуется назначить каждому узлу сети такую мощность передачи, чтобы они смогли передавать свои данные на базовую станцию, возможно, через другие узлы. Иными словами, требуется построить связную коммуникационную сеть с минимальной суммарной мощностью передачи узлов.  

Беспроводные датчиковые сети используются для мониторинга экологической обстановки (загрязнения воздуха и водоемов, лесных пожаров, оползней). Часто датчики питаются от батареек, так что срок эксплуатации датчиковой сети зависит от энергоэффективности их беспроводной коммуникационной сети. 

В 2017 году заведующий лабораторией алгоритмики ММФ Рене ван Беверн вместе с Берлинскими коллегами доказали, что теоретически задача имеет эффективный алгоритм решения, когда сеть с n узлами уже состоит из O (log n) связных компонент, которые нужно связать при минимальном увеличении суммарной мощности передачи. Эта ситуация возникает, например, когда ранее связанная сеть распадается на несколько компонент впоследствии выхода из строя узлов сети, или когда мониторятся несколько областей, в каждой из которых узлы расположены с достаточно регулярной структурой. Структура же возникает, когда минимизируются пересечения области сканирования датчиков (тоже в целях энергоэффективности). За теоретический результат ученые из НГУ и Берлина в 2017 году получили премию на большом Европейском конгрессе по алгоритмам. Математически было доказано, что их алгоритм для достаточно больших n будет работать во сколько угодно раз быстрее, чем известные алгоритмы: трудоемкость их алгоритма растет полиномиально по n, в то время как трудоемкость ранее известных алгоритмов растет экспоненциально. 

Оставался открытым вопрос о практической ценности алгоритма: а не получится ли так, что новый алгоритм будет быстрее только для таких n, превышающих число частиц во Вселенной? Этим вопросом в 2018 году занялся Павел Смирнов, тогда магистрант ФИТ НГУ и теперь аспирант 1-го курса ММФ НГУ. Выяснив, что алгоритм в самом деле в предложенной форме практически неконкурентоспособен, он ускорил алгоритм и на практике, и в теории, что стало главным результатом его магистерской работы и статьи в Q1-журнале INFORMS Journal on Computing.

— С одной стороны, у самой задачи есть приложения в области беспроводных сетей. Есть практический интерес в том, чтобы решать ее за разумное время, — прокомментировал Павел. — С теоретической же точки зрения, более близкой лично для меня, задача интересна тем, что она NP-трудна, то есть решать быстро в общем случае ее, по-видимому, нельзя. Предыдущие подходы к решению основывались на решении задачи целочисленного программирования. Мы же попытались потягаться с этими подходами методами параметризации и достигли определенного успеха.​

Даже на маленьких сетях с n=200 узлами и пятью несвязными компонентами новый алгоритм (слева в рисунке) работает до 100 раз быстрее, чем ранее известный алгоритм (справа) для оптимального решения задачи: новый алгоритм справляется за 10 секунд вместо 16 минут, при этом преимущество нового алгоритма только возрастает по увеличению сети. Стоит отметить, что обоим алгоритмам была поставлена задача только «досвязать» сеть, то есть они оба используют особенную структуру датчиковой сети, подаваемой на входе.   

Алгоритм_2.png

Источник: www.nsu.ru 

Похожие новости

  • 08/08/2020

    «Академгородок 2.0» будут копировать и масштабировать

    ​​​Новосибирскую программу перезапуска развития территории с повышенной концентрацией науки и инноваций берут в другие регионы. Пожалуй, наиболее востребованная новость из недавней рабочей поездки в Новосибирск министра науки и высшего образования Валерия Фалькова была про увеличение бюджетных мест в вузах региона.
    2323
  • 09/11/2020

    «Фабрика программирования. Путь профессионала» - новая образовательная программа для молодежи Красноярского края

    ​​В Красноярске при поддержке куратора Цифрового кластера Красноярского края (центр «Мой бизнес») - Ассоциации технологичных компаний «ИТЭРА» и пространства коллективной работы «Точка кипения – Красноярск» реализуется проект интенсивных школ обучения по созданию цифровых продуктов «Фабрика программирования.
    832
  • 26/08/2021

    Чемпионы Школьной лиги CASE-IN из Новосибирска совершат поездку на крупнейший нефтегазохимический комплекс

    В конце августа победители двух сезонов Школьной лиги Международного инженерного чемпионата «CASE-IN» из Новосибирска и Кемерово отправятся в образовательное путешествие в Тобольск на крупнейший в России нефтегазохимический комплекс СИБУРа «ЗапСибНефтехим».
    153
  • 20/07/2021

    Акселератор новосибирского Академпарка научит инноваторов создавать комплексные продукты

    ​​Технопарк Новосибирского Академгородка продолжает прием заявок на осенний бизнес-ускоритель А:СТАРТ, который пройдет с 17 сентября по 28 октября 2021 года. Авторы инновационных проектов получат навыки в области продуктового менеджмента и смогут создать новый или масштабировать действующий стартап.
    343
  • 24/06/2020

    «100 лучших изобретений»: российская вакцина против оспы, гибридная мультироторная летающая платформа, технологии распознавания текста с использованием искусственного интеллекта

    ​По итогам анализа патентного массива 2019 года и 1 полугодия 2020 года Роспатент по традиции выделил «100 лучших изобретений». Список опубликован на сайте ведомства с указанием авторов, патентообладателей, номеров патентов и патентных заявок, а также контактов патентообладателей или их представителей.
    760
  • 11/11/2020

    Автоматическая блинная печь и калькулятор генов: учащиеся инженерных курсов СУНЦ НГУ представили новые проекты

    ​​В Лаборатории инженерного конструирования СУНЦ НГУ прошел дистанционный семинар, на котором учащиеся представили темы своих проектов и рассказали об их реализации. Лучшие проекты весной будут представлены на школьной секции Международной научной студенческой конференции (МНСК).
    926
  • 23/03/2021

    Что значит наука без свободы?

     Валентин Иванов работал в трёх ведущих американских лабораториях, участвовал в крупнейших международных проектах по созданию линейных и циклических коллайдеров, а также проводил расчёты для космической отрасли.
    212
  • 19/03/2015

    Что вырастим, то вырастим: 3D-индустрия

    ​В стакан с песком мы кольцами, одно поверх другого, наливаем клей, он застывает, затем снова и снова льем клей и подсыпаем песку... Потом отряхиваем лишнее и получаем нечто вроде трубы. Заменим песок специально подготовленным порошком из металла, керамики или композита, струйку клея - лучом лазера или потоком электронов, а собственную руку - системами точного, до микрон, позиционирования и интеллектуального управления.
    1984
  • 01/09/2021

    Финал IX Национального чемпионата «Молодые профессионалы» (WorldSkillsRussia) – 2021

    В Уфе подвели итоги самых масштабных в России соревнований профессионального мастерства по стандартам WorldSkills среди студентов профессиональных образовательных учреждений и школьников – финала IX Национального чемпионата «Молодые профессионалы» (WorldSkillsRussia) – 2021.
    212
  • 20/09/2021

    Школьный технический форум НГУ

    ​В конце октября в пятый раз пройдет Школьный технический форум НГУ – ежегодное мероприятие для всех, кто увлечен робототехникой и инженерным конструированием. Из-за сложной эпидемической ситуации форум проведут в смешанном формате.
    239