Идентификация сенсорной конфигурации и управление потоками

  • Людмила Андреевна Пилипчук Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь
  • Андрей Степанович Пилипчук Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь
  • Евгений Николаевич Полячок Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь
  • Артем Иванович Фаразей Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

Аннотация

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

Биографии авторов

Людмила Андреевна Пилипчук, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

кандидат физико-математических наук; доцент кафедры компьютерных технологий и систем факультета прикладной математики и информатики

Андрей Степанович Пилипчук, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

соискатель кафедры методов оптимального управления факультета прикладной математики и информатики. Научный руководитель – доктор физико-математических наук; профессор кафедры методов оптимального управления факультета прикладной математики и информатики А. И. Калинин

Евгений Николаевич Полячок, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

магистрант кафедры компьютерных технологий и систем факультета прикладной математики и информатики. Научный руководитель – Л. А. Пилипчук

Артем Иванович Фаразей, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

студент факультета прикладной математики и информатики. Научный руководитель – Л. А. Пилипчук

Литература

  1. Bianco L, Confessore G, Gentili M. Combinatorial aspects of the sensor location problem. Annals of Operation Research. 2006;144(1):201–234. DOI: 10.1007/s10479-006-0016-9.
  2. Bianco L, Confessore G, Reverberi P. A network based model for traffic sensor location with implication in O/D matrix estimates. Transportation Science. 2001;35(1):50 – 60. DOI: 10.1287/trsc.35.1.50.10140.
  3. Pilipchuk LA. Sparse Linear Systems and Their Applications. Minsk: Belarusian State University; 2013.
  4. Bianco L, Cerrone C, Cerulli R, Gentili M. Locating sensors to observe network arc flows: exact and heuristic approaches. Computers and Operation Research. 2014;46:12–22. DOI: 10.1016/j.cor.2013.12.013.
  5. Pilipchuk LA, Pilipchuk AS. Sparse linear systems: theory of decomposition, methods, technology, applications and implementation in Wolfram Mathematica. AIP Conference Proceedings. 2015;1690(1):060006. DOI: 10.1063/1.4936744.
  6. Fidler M, Nedoma I, Ramik Ya, Ron I, Tsimmermann K. Zadachi lineinoi optimizatsii s netochnymi dannymi [Problems of linear optimization with inaccurate data]. Moscow: Institute for Computer Studies; 2008. Russian.
  7. Gabasov R, Kirillova FM, Kostyu kova OI. Konstruktivnye metody optimizatsii. Chastʼ 3. Setevye zadachi [Constructive optimization methods. Part 3. Network tasks]. Minsk: Belarusian State University; 1986. Russian.
  8. Pilipchuk L, Pilipchuk A, Pesheva Y. Algorithms for construction of optimal and suboptimal solutions in network optimization problems. International Journal of Pure and Applied Mathematics. 2009;54(2):193–205.
  9. Romanovskii IV. Suboptimal’nye resheniya [Suboptimal solutions]. Petrozavodsk: Izdatel’stvo Petrozavodskogo universiteta; 1998. Russian.
  10. Romanovskii I. V. [Survey of suboptimal solutions in discrete optimization problems]. Komp’yuternye instrumenty v obrazovanii. 2012;6:25–34. Russian.
Опубликован
2019-01-19
Ключевые слова: разреженная система, сенсорная конфигурация, оптимальные и субоптимальные решения, визуализация, моделирование, граф
Как цитировать
Пилипчук, Л. А., Пилипчук, А. С., Полячок, Е. Н., & Фаразей, А. И. (2019). Идентификация сенсорной конфигурации и управление потоками. Журнал Белорусского государственного университета. Математика. Информатика, 2, 67-76. Доступно по https://journals.bsu.by/index.php/mathematics/article/view/785
Выпуск
№ 2 (2018): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Информатика, вычислительная техника и управление

Copyright (c) 2018 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).