Identification of the sensors configuration and flows control

  • Ludmila A. Pilipchuk Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus
  • Andrei S. Pilipchuk Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus
  • Eugene N. Polyachok Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus
  • Artem I. Farazei Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

Abstract

The article is devoted to the development of strategies for identifying the location of special programmable devices (sensors) in network nodes for collecting, processing, analyzing information about the flow function in order to evaluate arc flows in that part of the network that is not directly observed. One of the ways to solve this problem is to search through possible placements, based on heuristic considerations. In work as a model of a flow network with sensors, a sparse underdetermined system of linear algebraic equations is used. The conditions for the uniqueness of the solution of a special kind of system obtained as a result of the use of a priori information from sensors installed in the monitored nodes of the network are determined. However, checking these conditions with a full search can only be used for small networks. The estimations limiting the number of viewed configurations of nodes are obtained and the interval of changing the number of monitored nodes that guarantee the complete observability of the network is justified. These results make it possible to increase the dimensionality of the problems being solved. Methods are developed for finding suboptimal solutions to establish the complete observability of the network for a given intensity threshold. Numerical results of constructing suboptimal solutions for various values of the intensity threshold are obtained. The results of visualization of the sensory configuration of the observed nodes are presented, which guarantee complete observability of the network. Conditions for effective applicability of exact methods are obtained for problems of the investigated class.

Author Biographies

Ludmila A. Pilipchuk, Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

PhD (physics and mathematics); associate professor at the department of computer applications and systems, faculty of applied mathematics and computer sciences

Andrei S. Pilipchuk, Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

postgraduate student at the department of optimal control methods, faculty of applied mathematics and computer sciences

Eugene N. Polyachok, Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

masterʼs degree student at the department of computer applications and systems, faculty of applied mathematics and computer sciences

Artem I. Farazei, Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

student at the faculty of applied mathematics and computer sciences

References

  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.
Published
2019-01-19
Keywords: graph, sparse system, modeling, configuration of sensors, optimal and suboptimal solutions, visualization
How to Cite
Pilipchuk, L. A., Pilipchuk, A. S., Polyachok, E. N., & Farazei, A. I. (2019). Identification of the sensors configuration and flows control. Journal of the Belarusian State University. Mathematics and Informatics, 2, 67-76. Retrieved from https://journals.bsu.by/index.php/mathematics/article/view/785
Issue
No 2 (2018): Journal of the Belarusian State University. Mathematics and Informatics
Section
Informatics, Computer Science and Management

Copyright (c) 2018 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)