Authors A.A. Kochkarov, D.V. Yatskin, O.A. Rahmanov
Month, Year 02, 2016 @en
Index UDC 004.021
Abstract The problem of limited space monitoring is formulated. The connection between the monitoring space and the detection of objects in this space sets up. After introducing some assumptions we conclude the necessity of solving the covering set (connected space) problem. The presence of obstacles in the monitoring area is the characteristic feature of the problem. “Obstacle” means a connected space area each point of which can not accommodate any object. However, as obstacles may lie in the monitoring area, the coverage of monitoring area should include the obstacles points. It is proposed to use an ad hoc network of mobile robots to solve the problem. The advantage of this approach is the high level of adaptability to changes in external parameters, as well as the resistance to failure of individual network elements. Coverage problem is described mathematically, the conclusion about necessity a sampling problem is made. All functions and parameters are replaced by digital analogues, the sampling steps are chosen to be small compared with the characteristic dimensions of the problem. We formulate and prove a couple of lemmas through which we study the properties and characteristics of various kinds of coverages. The smallest and minimum coverages are defined and ratio therebetween is set up. The mechanism of solution the covering problem by building a complete loaded graph according to certain rules, and the analysis of this graph is provided. We study the sufficient conditions for the construction of the smallest coverage. The algorithm for constructing the smallest coverage using a decentralized ad hoc network of mobile robots is developed. The efficiency of the algorithm follows from the lemmas and propositions set out above. The complexity of the algorithm is estimated. It is concluded that this algorithm is applicant and can solve the real problems related to space monitoring that arise.

Download PDF

Keywords Monitoring; detection problem; set theory; cover set; covering algorithms; graph theory, discrete optimization; mobile robot; group control.
References 1. Enck W. et al. TaintDroid: an information-flow tracking system for realtime privacy monitoring on smartphones, ACM Transactions on Computer Systems (TOCS), 2014, Vol. 32, No. 2, pp. 5.
2. Moore J.W., Ramamoorthy S. Heavy metals in natural waters: applied monitoring and impact assessment. Springer Science & Business Media, 2012.
3. Heyer R. et al. (ed.). Measuring and monitoring biological diversity: standard methods for amphibians. Smithsonian Institution, 2014.
4. Liu Y. et al. Mining frequent trajectory patterns for activity monitoring using radio frequency tag arrays, Parallel and Distributed Systems, IEEE Transactions on, 2012, Vol. 23, No. 11, pp. 2138-2149.
5. Krysin L.P. Tolkovyy slovar' inoyazychnykh slov [Explanatory dictionary of foreign words]. Moscow: Eksmo, 2008, 944 p.
6. Izrael' Yu.A. Global'naya sistema nablyudeniy. Prognoz i otsenka okruzhayushchey prirodnoy sredy. Osnovy monitoringa [The global observing system. Forecast and assessment of the natural environment. Monitoring framework], Meteorologiya i gidrologiya [Meteorology and Hydrology], 1974, No. 7, pp. 3-8.
7. Kondrat'ev A.D., Koroleva T.V., Puzanov A.V., Chernitsova O.V., Efremenkov A.A., Sharapova A.V., Gorbachev I.V., Dvurechenskaya E.B. Sovershenstvovanie sistemy ekologicheskogo monitoringa rayonov padeniya otdelyayushchikhsya chastey raket-nositeley [Improvment of environmental monitoring in areas of falling of detachable parts of carrier rockets], MNKO [The world of science, culture, education], 2012, No. 6 (37).
8. Kul'ba V.V., Somov D.S., Kochkarov A.A. Primenenie strukturno-integrirovannykh indikatorov v monitoringe slozhnykh tekhnicheskikh sistem [The use of structure-integrated indicators in complex technical systems monitoring], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 3 (116), pp. 52-64.
9. Chen X. et al. Aircraft detection by deep belief nets,Pattern Recognition (ACPR), 2013 2nd IAPR Asian Conference on. IEEE, 2013, pp. 54-58.
10. Hailong L. Study on the dust particles parameter with rocket detection in Earth's mesopause, Antennas, Propagation & EM Theory (ISAPE), 2012 10th International Symposium on. IEEE, 2012, pp. 1026-1028.
11. Lobell D.B. et al. Satellite detection of earlier wheat sowing in India and implications for yield trends, Agricultural Systems, 2013, Vol. 115, pp. 137-143.
12. Held D., Levinson J., Thrun S. A probabilistic framework for car detection in images using context and scale, Robotics and Automation (ICRA), 2012 IEEE International Conference on. IEEE, 2012, pp. 1628-1634.
13. Hlawatsch F. Time-frequency analysis and synthesis of linear signal spaces: time-frequency filters, signal detection and estimation, and Range-Doppler estimation. Springer Science & Business Media, 2013, Vol. 440.
14. Ramнrez D. et al. Detection of rank-signals in cognitive radio networks with uncalibrated multiple antennas, Signal Processing, IEEE Transactions on, 2011, Vol. 59, No. 8, pp. 3764-3774.
15. Yang X. et al. Blind detection for primary user based on the sample covariance matrix in cognitive radio, Communications Letters, IEEE, 2011, Vol. 15, No. 1, pp. 40-42.
16. Hu D., Ronhovde P., Nussinov Z. Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives, Philosophical Magazine, 2012, Vol. 92, No. 4, pp. 406-445.
17. Ventresca M. Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem, Computers & Operations Research, 2012, Vol. 39, No. 11, pp. 2763-2775.
18. Fan C. M. et al. Numerical solutions of boundary detection problems using modified collocation Trefftz method and exponentially convergent scalar homotopy algorithm, Engineering Analysis with Boundary Elements, 2012, Vol. 36, No. 1, pp. 2-8.
19. Yatskin D.V. Samoorganizatsiya i komandno-informatsionnoe vzaimodeystvie abonentov v detsentralizovannykh setevykh sistemakh [Self-organization and team-communication subscribers in a decentralized network systems], Materialy semnadtsatogo nauchno-prakticheskogo seminara “Novye informatsionnye tekhnologii v avtomatizirovannykh
sistemakh”, Moskva, 2014 [Proceedings of the seventeenth scientific-practical seminar “New information technologies in automated systems”, Moscow, 2014].

Comments are closed.