Authors A. B. Klimenko, I. B. Safronenkova
Month, Year 08, 2018 @en
Index UDC 004.75; 519.687.1
DOI 10.23683/2311-3103-2018-8-83-94
Abstract Fog computing concept is quite new but applied almost everywhere. This is due to the fact of intensive processed data capacity growth, so the cloud computing architectures, which were used successfully before, become insufficient in the conditions of Internet of Things (IoT). A workload allocation problem in heterogeneous computing environment is not new and has been solved many times. However, the known problem models neglect some special aspects of fog computing such as: inequality of computation nodes; mandatory participation of cloud layer in the computing process. The current paper focuses on the problem formalizing the workload allocation problem in view of fog computing special aspects by using the device “offload” strategy. In this case the task subgraph reallocation on some computing device subsets of fog layer takes place. A constraint which is peculiar to the fog computing is added to the workload allocation problem in heterogeneous computing environment. This is a multicriteria optimization problem with multiple constraints, which are determined by the system peculiarities, so the optimization problem is NP- hard. It puts a question of quality decisions getting in the limited time conditions. In this paper an approach based on the optimization problem search space reduction through the candidate computing device set selecting is proposed. An ontological approach is used for this purpose: ontology structure that classifies the reallocated subgaph respectively to available resources has been developed. The rules, which are based on developed ontology, apply to candidate nodes choosing for task subgraph allocation. This allows to efficiently reduce the solution search space.

Download PDF

Keywords Workload allocation; fog computing; distributed computing; Internet of Things, ontology; optimization problem.
References 1. Chiang M. and Zhang T. Fog and IoT: An Overview of Research Opportunities, IEEE Internet of Things Journal, 2016, pp. 854-864. Doi: 10.1109/JIOT.2016.2584538.
2. Bonomi F. et al. Fog Computing and Its Role in the Internet of Things, Proceedings of the first edition of the MCC workshop on Mobile cloud computing, 2012, pp. 13-16. Doi: 10.1145/2342509.2342513.
3. Moysiadis V., Sarigiannidis P. and Moscholios I. Towards Distributed Data Management in Fog Computing, Wireless Communications and Mobile Computing, 2018. Doi: 10.1155/2018/7597686.
4. Pinedo M. L. Scheduling: Theory, algorithms, and systems, fifth edition, Scheduling: Theory, Algorithms, and Systems, Fifth Edition, 2016. Doi: 10.1007/978-3-319-26580-3.
5. Konvey R.V., Maksvell V.L., Miller L.V. Teoriya raspisaniy [Theory of scheduling]. Moscow: Nauka, 1975, 360 p.
6. Barskiy A.B. Parallel'nye protsessy v vychislitel'nykh sistemakh: planirovanie i organizatsiya [Parallel processes in computing systems: planning and organization]. Moscow: Radio i svyaz', 1990, 256 p.
7. Khoroshevskiy V.G. Arkhitektura vychislitel'nykh system [Architecture of computing systems]. Moscow: Izd-vo MGTU imeni N.E. Baumana. 2008, 520 p.
8. Gonchar D.R., Furugyan M.G. Effektivnye algoritmy planirovaniya vychisleniy v mnogoprotsessornykh sistemakh real'nogo vremeni [Effective algorithms of calculation planning in multiprocessor real-time systems], UBS [Large-Scale Systems Control], 2014, No. 49. Available at: (accessed 19 November 2018).
9. Kostenko V.A. Zadachi sinteza arkhitektur: formalizatsiya, osobennosti i vozmozhnosti razlichnykh metodov dlya ikh resheniya [Problems of synthesis of architectures: formalization, features and possibilities of different methods for their solution], Programmnye sistemy i instrumenty: Tematicheskiy sbornik [Software systems and tools: Thematic collection], 2000, No. 1. Moscow: MAKS Press, pp. 31-41.
10. Cisco, Affiliates, and/or its affiliates. Fog Computing and the Internet of Things: Extend the Cloud to Where the Things Are, 2015. Available at: trends/iot/docs/computing-overview.pdf (accessed 19 November 2018).
11. Wang Y., Uehara T. and Sasaki R. Fog computing: Issues and challenges in security and forensics, in Proceedings - International Computer Software and Applications Conference, 2015, pp. 53-59. Doi: 10.1109/COMPSAC.2015.173.
12. Noy N., McGuinness D. Ontology development 101: a guide to creating your first ontology. stanford knowledge systems laboratory Technical report KSL-01–05 and Stanford Medical Informatics Technical report SMI-2001-0880, 2001.
13. Gavrilova T.A., Kudryavtsev D.V., Muromtsev D.I. Inzheneriya znaniy. Modeli i metody: uchebnik [Knowledge engineering. Models and methods: tutorial]. Saint Petersburg: Lan', 2016, 324 p. Available at:
14. Melnik E.V., Klimenko A B. and Ivanov D.Y. Distributed Information and Control system reliability enhancement by fog-computing concept application, in IOP Conference Series: Materials Science and Engineering, 2018. Doi: 10.1088/1757-899X/327/2/022070.
15. Melnik E.V. and Klimenko A.B. Informational and control system configuration generation problem with load-balancing optimization, in Application of Information and Communication Technologies, AICT 2016 - Conference Proceedings, 2017. Doi: 10.1109/ICAICT.2016.7991750.
16. Klimenko A.B., Ivanov D. and Melnik E.V. The configuration generation problem for the informational and control systems with the performance redundancy, in 2016 2nd International Conference on Industrial Engineering, Applications and Manufacturing, ICIEAM 2016 - Proceedings, 2016. Doi: 10.1109/ICIEAM.2016.7910901.
17. David Linthicum. Edge computing vs. fog computing: Definitions and enterprise uses // CISCO. Available at:
18. Ingber L. Very fast simulated re-annealing, Mathematical and Computer Modelling, 1989, No. 12 (8), pp. 967-973. Doi: 10.1016/0895-7177(89)90202-1.
19. Dorigo M., Maniezzo V. and Colorni A. Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996. Doi: 10.1109/3477.484436.
20. Iba H. and Aranha C.C. Introduction to genetic algorithms, Adaptation, Learning, and Optimization, 2012. Doi: 10.1007/978-3-642-27648-4_1.
21. Goldberg D.E. and Holland J.H. Genetic Algorithms and Machine Learning, Machine Learning, 1988. Doi: 10.1023/A:1022602019183.
22. Kholod I.I. Metod opredeleniya vozmozhnostey parallel'nogo vypolneniya funktsiy algoritmov analiza dannykh [Method for determining the capabilities of parallel functions of data analysis algorithms], Programmnye produkty i sistemy [Software products and systems], 2018, No. 2, pp. 268-274.
23. Kholod I.I., Karshiev Z.A. Metod postroeniya parallel'nykh algoritmov intellektual'nogo analiza dannykh iz potokonezavisimykh funktsional'nykh blokov [A method of constructing parallel algorithms for data mining from photocontainer functional blocks], Izvestiya SPbGETU «LETI» [Izvestiya SPbGETU «LETI], 2013, No. 8, pp. 38-45.
24. Kholod I.I. Modeli i metody postroeniya parallel'nykh algoritmov analiza raspredelennykh dannykh: diss. … d-ra tekhn. nauk [Models and methods of construction of parallel algorithms for analysis of distributed data: dr. of eng. sc. diss.]. Saint Petersburg, 2018.
25. Kalyaev I.A., Gayduk A.R., Kapustyan S.G. Samoorganizatsiya v mul'tiagentnykh sistemakh [Self-organization in multi-agent systems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 3 (104), pp. 14-20.

Comments are closed.