RADIOELECTRONIC AND COMPUTER SYSTEMS

To ensure the life of society, it becomes necessary to create systems for monitoring processes or objects using a network of sensors that can control part of the space (territory). Monitoring is understood as a systematic observation of the parameters of an object to obtain information on their compliance with the initial assumptions. Simultaneously, a physical model is constructed that links the characteristics of the object and information about the observation, which making it possible to identify the properties of the object. Such information is based on the processing of signals received using special control sensors. These signals are digitized to provide data on the coverage areas of the sensors. Thus, the physical model is associated with measuring the ability and quality of perception of control sensors, fixing the geometric relationship between them and points in space. The specified physical model corresponds to the geometric statement of the problem of covering the monitoring area with a set of geometric objects, the shape and size of which is determined by the coverage areas of the sensors. With a limited number of sensors, the problem arises of the maximum possible coverage of the area. In this article, we digress from the type of monitoring object and consider the geometric features of coverage problems that arise when designing systems for monitoring a space of various purposes. The current article presents constructive means of mathematical modeling for solving geometric problems of maximum coverage. To formalize the coverage conditions, the concept of constructing the configuration space of geometric objects and a special class of functions are used to establish the dependence of the measure (area, volume) of the coverage configuration on the placement parameters of the covering objects. Since it is extremely difficult to obtain an analytical form of these functions, an algorithmic approach to their calculation is proposed. The approach was implemented on the Pyton algorithm using the Shapely library. A computational experiment was planned and carried out to establish the dependence of the computation time on the number of geometric objects that make up the coverage configuration. To find the maximum coverage, the BFGS local optimization method of the Scipy.optimize package is used. Numerous examples of the implemenation of the proposed approach are given. Conclusions. The article substantiates the use of a software-algorithmic approach for formalization, calculation and optimization of maximum coverage configurations, which makes it possible to effectively solve complex problems of monitoring space and territories.

space monitoring; sensor network; coating; geometric object; mathematical model; optimization

Fei, Z., Li, B., Yang S., et. al. A survey of multi-objective optimization in wireless sensor networks: metrics, algorithms and open problems, IEEE Communications Surveys & Tutorials, 2017, vol. 19, iss. 1, pp. 550-586. DOI: 10.1109/ comst.2016.2610578

Wei, R. Coverage location models: alternatives, approximation, and uncertainty. International Regional Science Review, 2017, vol. 39, iss. 1, pp. 48-76. DOI: 10.1177/0160017615571588.

Zafari, F., Gkelias, A., and Leung, K. A survey of indoor localization systems and technologies. IEEE Commun. Surveys Tuts, 2019, vol. 21, no. 3, pp. 2568–2599. DOI: 10.1109/COMST.2019.2911558.

Wu, C. Q., Wang, L. On efficient deployment of wireless sensors for coverage and connectivity in constrained 3D space. Sensors, 2017, vol. 17, iss. 2304, pp. 1-26. DOI: 10.3390/s17102304.

Zhyla, S., Volosyuk, V., Pavlikov V., et.al. Statistical synthesis of aerospace radars structure with optimal spatio-temporal signal processing, extended observation area and high spatial resolution. Radioelectronic and Computer Systems, 2022, no. 1(101), pp. 178-194. DOI: 10.32620/reks.2022.1.14.

Yaloveha, V., Podorozhniak, A., Kuchuk, H. Convolutional neural network hyperparameter optimization applied to land cover classification. Radioelectronic and Computer Systems, 2022, no. 1(101), pp. 115-128. DOI: 10.32620/reks.2022.1.09.

Murray, A. T. Optimising the spatial location of urban fire stations. Fire Safety Journal, 2013, vol. 62, pp. 64–71. DOI: 10.1016/j.firesaf.2013.03.002.

Adesina, E. A., Odumosu, J. O., Morenikeji, O. O., Umoru, E., Ayokanmbi, A. O., Ogunbode, E. B. Optimization of fire stations services in Minna metropolis using maximum covering location model (MCLM). J Appl Sci Environ Sustain, 2017, vol. 3, iss. 7, рр. 172–187.

Hashemi, A., Gholami, H., Venkatadri, U., Wojciechowski, A., Streimikiene, D. A new direct coefficient-based heuristic algorithm for set covering problems. International Journal of Fuzzy Systems, 2022, vol. 24, iss. 2, pp. 1131–1147. DOI: 10.1007/s40815-021-01208-5.

Li, Xu, Fletcher, G., Nayak, A., and Stojmenovic, I. Placing sensors for area coverage in a complex environment by a team of robots. ACM Transactions on Sensor Networks, 2014, vol. 11, iss. 1, pp. 1–22. DOI: 10.1145/2632149.

Kliushnikov, I. M., Fesenko, H. V., Kharchenko, V. S. Scheduling UAV fleets for the persistent operation of UAV-enabled wireless networks during NPP monitoring. Radioelectronic and Computer Systems, 2020, no. 1(93), рр. 29-36. DOI: 10.32620/reks.2020.1.03.

Song, P. and Yonghua, X. A new sensing direction rotation approach to area coverage optimization in directional sensor network. J. Adv. Comput. Intell. Inform, 2020, vol. 24, iss. 2, pp. 206-213. DOI: 10.20965/jaciii.2020.p0206.

Dorninger, D. On a conjecture of L. Fejes Tóth and J. Molnár about circle coverings of the plane. Period Math Hung, 2019, vol. 78, pp. 242–253. DOI: 10.1007/s10998-018-0254-z.

Rvachev, V. L. Teoriya R-funktsii i nekotoryye yeye prilozheniya: monografiya [Theory of the R-function and some of its applications: monograph]. Kyiv: “Nauk. Dumka” Publ., 1982. 552 p.

Stoyan, Y., Scheithauer, G., Gil, N., Romanova, T. Φ-functions for complex 2D-objects. 4OR, 2004, vol. 2, iss. 1, pp. 69-84. DOI: 10.1007/s10288-003-0027-1.

Bennell, J., Scheithauer, G., Stoyan, Y., Romanova, T. Tools of mathematical modeling of arbitrary object packing problems. Annals of Operations Research, 2010, vol. 179, iss. 1, pp. 343–368. DOI: 10.1007/s10479-008-0456-5.

Gaspar, Z., Tarnai, T., Hincz, K. Partial covering of a circle by equal circles. Part 1: The mechanical models. Journal of Computational Geometry, 2014, vol. 5, iss. 1, pp. 104–125. DOI: 10.20382/jocg.v5i1a6.

Stoyan, Y. G., Patsuk, V. M. Covering a compact polygonal set by identical circles. Comp. Opt. and Appl., 2010, vol. 46, iss.1, pp. 75-92. DOI: 10.1007/s10589-008-9191-8.

Antoshkin, O. A., Pankratov, O. V. Uzahalʹnena mate-matychna modelʹ zadachi pokryttya oblasti identychnymy kolamy ta yiyi osnovni realizatsiyi [The mathematical model of the problem covering the areas of identical stakes and the main implementations has been elaborated]. Systemy obrobky informatsiyi [Information processing systems], 2019, no. 1(156), pp. 44-49. DOI: 10.30748/soi.2019.156.06.

Pankratov, A., Romanova, T., Litvinchev, I., Marmolejo-Saucedo, J. A. An optimized covering spheroids by spheres. Applied Sciences (Switzerland), 2020, 10 (5), paper № 1846, DOI: /10.3390/app10051846

Stoyan, Y. G., Romanova, T., Scheithauer, G., Krivulya, A. Covering a polygonal region by rectangles. Computational Optimization and Applications, 2011, vol. 48, iss.3, pp. 675-695. DOI: 10.1007/s10589-009-9258-1.

Li, J., Wang, R., Huang, H. and Sun, L. Voronoi based area coverage optimization for directional sensor networks. Proc. of the 2009 2nd Int. Symp. on Electronic Commerce and Security, 2009, pp. 488-493. DOI: 10.4236/wsn.2009.15050.

Kiseleva, E., Hart, L., Prytomanova, O., Kuzenkov, O. An algorithm to construct generalized Voronoi diagrams with fuzzy parameters based on the theory of optimal partitioning and neuro-fuzzy technologies. CEUR Workshop Proceedings, 2019, vol. 2386, pp. 148-162.

Sung, T.-W., Yang, C.-S. Localised sensor direction adjustments with geometric structures of Voronoi diagram and Delaunay triangulation for directional sensor networks. Int. J. of Ad Hoc and Ubiquitous Computing, 2015, vol. 20, no. 2, pp. 91-106. DOI: IJAHUC.2015.071694.

Kiseleva, E. M. The emergence and formation of the theory of optimal set partitioning for sets of the n-dimensional Euclidean space. Theory and application Journal of Automation and Information Sciences, 2018, vol. 50, no. 9, pp. 1-24. DOI: 10.1615/JAutomatInfScien.v50.i9.10.

Kiseleva, Е. М., Kadochnikova, Y. E. Solving a Continuous Single-product Problem of Optimal Partitioning with Additional Conditions. Journal of Automation and Information Science, 2009, vol. 41, no. 7, pp. 48-63. DOI: 10.1615/JAutomatInfScien.v41.i7.30.

Stoyan, Y. G., Yakovlev, S. V. Configuration Space of Geometric Objects. Cybernetics and Systems Analysis, 2018, vol. 54, no. 5, pp. 716–726. DOI: 10.1007/s10559-018-0073-5.

Yakovlev, S. V. On some classes of spatial configurations of geometric objects and their formalization. Journal of Automation and Information Sciences, 2018, vol. 50, iss. 9, pp. 38–50. DOI: 10.1615/JAutomatInfScien.v50.i9.30.

Berge, C. Principes de combinatoire. Paris, Dunod Publ., 1968. 146 p.

Yakovlev, S. V. Formalizing spatial configuration optimization problems with the use of a special function class. Cybernetics and Systems Analysis, 2019, vol. 55, iss. 4, pp. 581-589. DOI: 10.1007/s10559-019-00167-y.

Gillies, S. The Shapely User Manual. Available at: https://shapely.readthedocs.io/en/stable/manual.html (accessed 12.03.2022).

Pankratov, A. V., Romanova, T. Ye., Subbota, I. A. Development of effective algorithms for optimal packing of ellipses. Eastern-European Journal of Enterprise Technologies, 2014, vol. 5, no. 4 (71), pp. 28-35. DOI: 10.15587/1729-4061.2014.28015.