ВИКОРИСТАННЯ  АЛГОРИТМУ РОЗФАРБОВУВАННЯ ГРАФА ДЛЯ ВИЗНАЧЕННЯ ПОРЯДКУ ЗБОРУ ДАНИХ РАДІАЦІЙНОГО МОНІТОРИНГУ З ТОЧОК «РАНДЕВУ» БЕЗДРОТОВОЇ  ЛІТАЮЧОЇ МЕРЕЖІ

H. V. Fesenko; I. M. Kliushnikov

doi:10.32836/2521-6643-2018.2-56.1

H. V. Fesenko Associate Professor at the Department of Computer Systems, Networks and Cybersecurity
I. M. Kliushnikov Senior Researcher, PhD. tehn. Sciences Kharkiv National University of Air Force

DOI: https://doi.org/10.32836/2521-6643-2018.2-56.1

Abstract

Wired networks, connecting monitoring stations (MS) of the automated radiation monitoring system (ARMS) to the crisis centre (CrS), can be damaged as a result of an NPP accident. To cope with the problem, an unmanned aerial vehicle (UAV)-enabled wireless network (UEWN), can be deployed. The aim of the paper is to develop an approach based on a graph coloring algorithm to determine the number of UAVs of an airplane-type and define the order of their use for gathering data from rendezvous points of a deployed UEWN during Zaporizhzhia NPP (ZNPP) post-accident monitoring missions. The existing graph coloring algorithms are analyzed and presented as a table. For later use, the greedy graph coloring algorithm based on bitwise operations on the adjacency matrix is selected. A simplified scheme of deployment of a UEWN for transmitting the data from the MS to the CrS during NPP post-accident monitoring missions was developed and described. Two segments within the UEWN were considered: 1) Wi-Fi segment, comprising the WiFi equipment of the MS, the onboard WiFi equipment of the UAVs of a multi-rotor type (MUAVs), and onboard WiFi equipment of the UAV of an airplane-type (AUAV); 2) LoRaWAN segment, comprising the LoRaWAN equipment of the AUAV and the LoRaWAN equipment of the CrS. А scheme of UEWN subsystems deployment for the organization of data transfer between four monitoring stations of ARMS for ZNPP and rendezvous points in case of loss of wired networks. Using the selected graph coloring algorithm, it has been determined that three AUAVs are required for gathering and transmitting the data from four MSs to the CrS. Further studies should focus on investigating the effect of the location of the automatic battery replacement stations and their features on the UEWN’s functioning.

References

1. Kochan V. V., Sachenko A. A., Kharchenko V. S., Yatskiv V. V., Cher-nyshov M. A., Bykovyi P. Ye., Roshchupkin O. Yu. and Koval V. S. (2016), “Kontseptsiia pobudovy mobilnykh system post-avariinoho monitorynhu AES z vykorystanniam flotu kvadrokopteriv” [“Concept of building of NPP post-emergency monitoring mobile systems using quadrocopter fleet”], Journal Radi-oelektronni i komp’iuterni systemy [Radioelectronic and Computer Systems], vol. 5(79), pp. 207–214 [Ukraine].
2. Kharchenko V. S., Jastrebeneckij M. A., Fesenko H. V., Sachenko A. A. and Kochan V. V. (2017), “Sistema posleavarijnogo monitoringa AJeS s ispol'zovaniem bespilotnyh letatel'nyh apparatov: modeli nadezhnosti” [“NPP post-accident monitoring system based on unmanned aircraft vehicle: Concept, design principles”], Journal Yaderna ta radiatsiina bezpeka [Nuclear and Radia-tion Safety], vol. 4 (76), pp. 50–55 [Ukraine].
3. Fesenko H., Kharchenko V., Sachenko A., Hiromoto R. and Kochan V. (2018),“An Internet of Drone-based multi-version post-severe accident monitoring system: structures and reliability”. Dependable IoT for Human and Industry Modeling, Architecting, Implementation, River Publishers, Denmark, The Netherlands, pp. 197–217.
4. Moiseev V. S. (2017), Gruppovoye primeneniye bespilotnykh letatel'nykh apparatov [Group use of unmanned aerial vehicles], Monograph, Kazan', 572 p. [Russia].
5. Kučera L. (1991) “The greedy coloring is a bad probabilistic algorithm”. // Journal of Algorithm, vol. 12, pp. 674–684.
6. Kosowski A. and Manuszewski K. (2011), “Classical coloring of graphs”. Contemporary Mathema, vol. 352, pp. 1–20.
7. Hansen J., Kubale M., Kuszner Ł. and Nadolski A. (2004), “Distributed largest-first algorithm for graph coloring”. Lecture Notes in Computer Science, vol. 3149, pp. 804–811. DOI:10.1007/978-3-540-27866-5.
8. Matula D. and Beck L. (1983), “Smallest-last ordering and clustering and graph coloring algorithms”. Journal of the ACM (JACM), vol. 30, pp. 135–145.
9. Read R. (2014), Graph theory and computing, Academic Press, USA, New York, 344 p.
10. Matula D., Marble G. and Isaacson J. (2014), “Graph coloring algorithms”. Graph Theory and Computing, Academic Press, USA, New York, pp. 109–122.
11. Hertz A. and Werra D. (1989), “Connected Sequential Colorings”. Annals of Discrete Mathematics, vol. 39, pp. 51–59. DOI: 10.1016/S0167-5060(08)70297-8.
12. Wu Q. and Hao J.-K. (2012), “Coloring large graphs based on independent set”. Computers & OR, vol. 39, pp. 283–290. DOI:10.1016/j.cor.2011.04.002.
13. Komosko L., Batsyn M., Segundo P. and Pardalos P. (2016). “A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations”. Journal of Combinatorial Optimization, vol. 4, pp. 1665–1677.
14. Vestron. Avtomatizirovannaya sistema kontrolya radiatsionnoy ob-stanovki ZAES. Tehnicheskoe zadanie. TZ - VN. 702.410.34 [Westron. Automat-ed system for Radiation situation monitoring. Technical Task. TZ - VN. 702.410.34] (2011). Kharkiv, 124 p. [Ukraine]

USING A GRAPH COLORING ALGORITHM TO DETERMINE THE ORDER OF GATHERING RADIATION MONITORING DATA FROM RENDEZVOUS POINTS OF A WIRELESS FLYING NETWORK

Abstract

References