ONTOLOGY BASED WORKLOAD ALLOCATION PROBLEM SOLVING IN FOG COMPUTING ENVIRONMENT

  • A.B. Klimenko Research Institute of Multiprocessor Computation Systems n.a. A.V. Kalyaev
  • I.B. Safronenkova Southern Federal University
Keywords: Workload allocation, fog computing, distributed computing, Internet of Things, ontology, optimization problem

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 computingprocess. 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 heterogene-ous 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 de-vice 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.

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 sys-tems]. 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 plan-ning in multiprocessor real-time systems], UBS [Large-Scale Systems Control], 2014, No. 49. Available at: https://cyberleninka.ru/article/n/effektivnye-algoritmy-planirovaniya-vychisleniy-v-mnogoprotsessornyh-sistemah-realnogo-vremeni (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: https://www.cisco.com/c/dam/en_us/solutions/ 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 foren-sics, 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 In-formatics 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: https://e.lanbook.com/book/81565.
14. Melnik E.V., Klimenko A B. and Ivanov D.Y. Distributed Information and Control system reli-ability enhancement by fog-computing concept application, in IOP Conference Series: Mate-rials 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 in-formational and control systems with the performance redundancy, in 2016 2nd International Conference on Industrial Engineering, Applications and Manufacturing, ICIEAM 2016 - Pro-ceedings, 2016. Doi: 10.1109/ICIEAM.2016.7910901.
17. David Linthicum. Edge computing vs. fog computing: Definitions and enterprise uses // CISCO. Available at: https://www.cisco.com/c/en/us/solutions/enterprise-networks/edge-computing.html. 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 Optimi-zation, 2012. Doi: 10.1007/978-3-642-27648-4_1. 21. Goldberg D.E. and Holland J.H. Genetic Algorithms and Machine Learning, Machine Learn-ing, 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.
Published
2019-04-03
Issue
No 8 (2018)
Section
SECTION. II. DISTRIBUTED AND CLOUD COMPUTING