РЕШЕНИЕ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ НАГРУЗКИ В СРЕДАХ ТУМАННЫХ ВЫЧИСЛЕНИЙ НА БАЗЕ ОНТОЛОГИЙ
Аннотация
Концепция туманных вычислений относительно нова, но внедряется практически по-всеместно. Это связано с интенсивным ростом объемов обрабатываемых данных, по-скольку используемые прежде классические, «облачные» архитектуры становятся недос-таточными в условиях Интернета Вещей. Задача распределения вычислительной нагрузки в гетерогенной вычислительной среде не нова и решалась неоднократно. Однако, извест-ные модели задачи, как правило, не учитывают особенностей сред туманных вычислений, таких, как: – неравноправность вычислительных узлов; – обязательное участие облачного слоя в решении вычислительных задач. Данная статья акцентирует внимание на формаль-ной постановке задаче распределения вычислительной нагрузки с учетом особенностей среды туманных вычислений в случае применения стратегии «разгрузки» устройств. В этом случае предполагается переразмещение части графа задач на некоем подмножестве вычислительных устройств туманного слоя. К постановке задачи распределения вычисли-тельной нагрузки в гетерогенной среде добавляется ограничение, свойственное среде ту-манных вычислений. Задача является многокритериальной, с многими ограничениями, оп-ределяемыми спецификой проектируемой системы, и потому относится к классу np-сложных, что ставит вопрос о получении качественных решений в ограниченные времен-ные сроки. В данной статье предлагается подход на базе уменьшения пространства поис-ка для сформулированной задачи оптимизации путем усечения множества кандидатов вычислительных устройств. Для этого используется онтологический подход: разработана структура онтологии, позволяющей классифицировать переразмещаемый подграф отно-сительно имеющихся ресурсов. На основе разработанной онтологии сформированы прави-ла, применяемые к выбору узлов-кандидатов для размещения подграфа задач, что в итоге позволяет значительно сократить пространство поиска решений.
Литература
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.