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

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

В 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 

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

  • 25/03/2021

    В НГУ состоялся заключительный этап Всероссийского химического турнира школьников

    XVII Всероссийский химический турнир школьников, который последние 3 года проходит на площадке НГУ, завершился. Это командное соревнование по решению творческих научных задач, позволяющее участникам расширять научный кругозор, научиться презентовать свои научные проекты, вступать в полемику и отстаивать свое мнение, применять научные знания для решения прикладных и теоретических задач.
    609
  • 28/12/2020

    Геном в режиме редактирования. Интервью с Дмитрием Жарковым

    ​Нобелевскую премию по химии в 2020 году получили Дженнифер Дудна и Эмманюэль Шарпантье за открытие системы редактирования генов CRISPR-Сas. Это стало настоящим прорывом в прикладной биологии и медицинской генетике.
    617
  • 18/06/2021

    Студент НГУ провел исследование по применению алгоритмов сегментации для обнаружения опухолей головного мозга и предсказанию временного интервала жизни пациента

    По данным Министерства здравоохранения РФ, показатель смертности от онкологических заболеваний в России в настоящее время составляет более чем 200 человек на 100 тысяч населения. При этом у 65–80% умерших от онкологии обнаруживаются опухоли в головном мозге.
    480
  • 08/08/2020

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

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

    В Новосибирске обсудят этику применения искусственного интеллекта в медицине и здравоохранении

    ​​​1 июля 2021 года на базе Точки кипения НГТУ НЭТИ состоится круглый стол «Новая медицинская парадигма: изменение роли врача и пациента (Этические вопросы применения технологий АI и генной инженерии в сфере здравоохранения)».
    305
  • 02/03/2021

    В НГУ состоится Huawei – NSU Open Day

    ​Компания Хуавей и НГУ в рамках сотрудничества в области образования приглашают всех заинтересованных студентов, аспирантов, преподавателей и научных сотрудников на Huawei – NSU Open Day 12 марта в 16:30 в аудиторию 3107 нового корпуса НГУ.
    648
  • 28/05/2020

    Ущерб от «черной пятницы» и влияние генов на характер: учащиеся СУНЦ НГУ стали призерами международной конференции

    ​В мае учащиеся СУНЦ НГУ успешно выступили на международной конференции для школьников "Сахаровские чтения". Свои доклады по информатике, физике и биологии ребята представили в режиме онлайн.
    773
  • 12/02/2021

    В НГУ завершилась стратегическая сессия у будущих инженеров

    На первой неделе февраля состоялась стратегическая сессия для студентов, преподавателей и партнеров Инженерной школы НГУ. Проект «Инженерная школа НГУ (ИШ НГУ)» уникальный: первый набор состоялся в 2019 году.
    870
  • 15/03/2021

    Всероссийский учебный фестиваль RuCode 3

    1 марта стартовал Всероссийский учебный фестиваль RuCode 3 по двум направлениям - Искусственный интеллект и Алгоритмическое программирование. НГУ – соорганизатор Всероссийского учебного фестиваля.
    604
  • 23/12/2019

    Экономисты НГУ стали экспертами на федеральном проекте для школьников

    ​Студенты Новосибирского госуниверситета и преподаватели Экономического факультета стали экспертами на федеральном проекте для школьников «Кампус на Зеленой улице». В рамках профильной смены учащиеся школ и гимназий проходят недельные курсы по хард и софт скиллам, развивают идеи для стартапов, занимаются программированием и робототехникой, изучают 3D-моделирование и учатся формировать и презентовать свои проекты.
    725