Kybernetika 59 no. 1, 88-109, 2023

Constrained k-means algorithm for resource allocation in mobile cloudlets

Rasim M. Alguliyev, Ramiz M. Aliguliyev and Rashid G. AlakbarovDOI: 10.14736/kyb-2023-1-0088

Abstract:

With the rapid increase in the number of mobile devices connected to the Internet in recent years, the network load is increasing. As a result, there are significant delays in the delivery of cloud resources to mobile users. Edge computing technologies (edge, cloudlet, fog computing, etc.) have been widely used in recent years to eliminate network delays. This problem can be solved by allocating cloud resources to the cloudlets that are close to users. The article proposes a clustering-based model for the optimal allocation of cloud resources among cloudlets. The proposed model takes into account user activity, usage frequency of cloud resources, the physical distance between users and cloud resources, as well as the storage capacity of cloudlets for optimal allocation of cloud resources in cloudlets. The proposed model was formalized as a constrained $k$-means method and an algorithm was developed to solve it. The MATLAB 2022a toolkit was used to evaluate the efficiency of the proposed algorithm. The obtained results revealed that the algorithm is promising.

Keywords:

mobile cloud computing, edge computing, cloudlet, cloud resources, constrained $k$-means

Classification:

90B80, 62H30, 90B18

paper.pdf

References:

  1. A. Ahmed and E. Ahmed: A survey on mobile edge computing. In: 2016 10th International Conference on Intelligent Systems and Control 2016, pp. 1-8.   DOI:10.1109/ISCO.2016.7727082
  2. E. Ahmed, A. Akhunzada, M. Whaiduzzaman, A. Gani, S. H. Ab Hamid and R. Buyya: Network-centric performance analysis of runtime application migration in mobile cloud computing. Simul. Modelling Practice Theory 50 (2015), 42-56.   DOI:10.1016/j.simpat.2014.07.001
  3. R. Alakberov: Strategy for reducing delays and energy consumption in cloudlet-based mobile cloud computing. Int. J. Wireless Networks Broadband Technol. 10 (2021), 1, 32-44.   DOI:10.4018/IJWNBT.2021010102
  4. R. G. Alakberov: Clustering method of mobile cloud computing according to technical characteristics of cloudlets. Int. J. Computer Network Inform. Security 14 (2022), 3, 75-87.   DOI:10.5815/ijcnis.2022.03.06
  5. R. Alakbarov and O. Alakbarov: Procedure of effective use of cloudlets in wireless metropolitan area network environment. Int. J. Computer Networks Commun. 11 (2019), 1 93-107.   DOI:10.5121/ijcnc.2019.11106
  6. M. Ala'anzy, M. Othman, Z. M. Hanapi and M. A. Alrshah: Locust inspired algorithm for cloudlet scheduling in cloud computing environments. Sensors 21 (2021), 7308, 1-19.   DOI:10.3390/s21217308
  7. R. M. Alguliyev and R. G. Alakbarov: Integer programming models for task scheduling and resource allocation in mobile cloud computing. Int. J. Computer Network Inform. Security, 2023 (in press).   CrossRef
  8. H. Asghar and E. S. Jung: A survey on scheduling techniques in the edge cloud: issues, challenges and future directions. arXiv.org 2022, 1-19.   https://arxiv.org/abs/2202.07799
  9. P. Azad and N. J. Navimipour: An energy-aware task scheduling in the cloud computing using a hybrid cultural and ant colony optimization algorithm. Int. J. Cloud Appl. Computing 7 (2017), 4, 20-40.   DOI:10.4018/IJCAC.2017100102
  10. A. M. Bagirov: Modified global k-means algorithm for minimum sum-of-squares clustering problems. Pattern Recognition 41 (2008), 10, 3192-3199.   DOI:10.1016/j.patcog.2008.04.004
  11. G. H. Bindu, K. Ramani and C. S. Bindu: Energy aware multi objective genetic algorithm for task scheduling in cloud computing. Int. J. Internet Protocol Technol. 11 (2018), 4, 242-249.   DOI:10.1504/IJIPT.2018.10016310
  12. P. S. Bradley, K. P. Bennett and A. Demiriz: Constrained k-means clustering. Technical Report MSR-TR-2000-65, Microsoft Research, Redmond 2000, pp. 1-8.   CrossRef
  13. X. Chen, L. Jiao, W. Z. Li and X. M. Fu: Efficient multi-user computation offloading for mobile-edge cloud computing. IEEE/ACM Trans. Networking 24 (2015), 5, 2795-2808.   DOI:10.1109/TNET.2015.2487344
  14. L. Chen, S. Zhou and J. Xu: Computation peer offloading for energy-constrained mobile edge computing in small-cell networks. IEEE ACM Trans. Networking 26 (2018), 4, 1619-1632.   DOI:10.1109/TNET.2018.2841758
  15. D. Dalan: An overview of edge computing. Int. J. Engrg. Res. Technol. 7 (2019), 5, 1-4.   CrossRef
  16. M. Hu, L. Zhuang, D. Wu, Y. P. Zhou, X. Chen and L. Xiao: Learning driven computation offloading for asymmetrically informed edge computing. IEEE Trans. Parallel Distributed Systems 30 (2019), 8, 1802-1815.   DOI:10.1109/TPDS.2019.2893925
  17. K. Liao, J. Yang and L. Miao: Mobile edge computing offload strategy based on energy aware. In: International Conference on Network Communication and Information Security 2021, pp. 1-9.   DOI:10.1117/12.2628417
  18. L. Lin, P. Li, J. Xiong and M. Lin: Distributed and application-aware task scheduling in edge-clouds. In: 2018 14th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN) 2018, pp. 165-170.   DOI:10.1109/MSN.2018.000-1
  19. R. Lin, Z. Zhou, S. Luo, Y. Xiao and M. Zukerman: Distributed optimization for computation offloading in edge computing. IEEE Trans. Wireless Commun. 19 (2020), 12, 8179-8194.   DOI:10.1109/TWC.2020.3019805
  20. Q. Luo, S. Hu, C. Li, G. Li and W. Shi: Resource scheduling in edge computing: a survey. IEEE Commun. Survey Tutorials 23 (2021), 4, 2131-2165.   DOI:10.1109/COMST.2021.3106401
  21. P. Mach and Z. Becvar: Mobile edge computing: a survey on architecture and computation offloading. IEEE Commun. Surveys Tutorials 19 (2017), 3, 1628-1656.   DOI:10.1109/COMST.2017.2682318
  22. J. Mike, J. Cao and W. Liang: Optimal cloudlet placement and user to cloudlet allocation in wireless metropolitan area networks. IEEE Trans. Cloud Computing 5 (2017), 4, 725-737.   DOI:10.1109/TCC.2015.2449834
  23. A. Mukherjee, D. Priti, D. De and R. Buyya: IoTF2N: An energy-efficient architectural model for IoT using Femtolet-based fog network. J. Supercomputing 75 (2019), 11, 7125-7146.   DOI:10.1007/s11227-019-02928-0
  24. A. Nasr, N. A. El-Bahnasawy, G. Attiya and A. El-Sayed: Cloudlet scheduling based load balancing on virtual machines in cloud computing environment. J. Internet Technol. 20 (2019), 5, 1376-1378.   CrossRef
  25. M. Sachula, Y. Wang, Z. Miao and K. Sun: Joint optimization of wireless bandwidth and computing resource in cloudlet-based mobile cloud computing environment. Peer-to-Peer Networking Appl. 11 (2018), 3, 462-472.   DOI:10.1007/s12083-017-0544-x
  26. D. K. Sajnani, A. R. Mahesar, A. Lakhan and I. A. Jamali: Latency aware and service delay with task scheduling in mobile edge computing. Commun. Network 10 (2018), 4, Article ID 87708.   DOI:10.4236/cn.2018.104011
  27. Y. Shen, Z. Bao, X. Qin and J. Shen: Adaptive task scheduling strategy in cloud: when energy consumption meets performance guarantee. World Wide Web 20 (2016), 155-173.   DOI:10.1007/s11280-016-0382-4
  28. K. Shenoy, P. Bhokare and U. Pai: Fog computing future of cloud computing. Int. J. Sci. Res. 4 (2015), 6, 55-56.   DOI:10.1891/2156-5287.5.1.55
  29. G. Shreya, A. Mukherjee, S. Ghosh and R. Buyya: Mobi-IoST: mobility-aware cloud-fog-edge-iot collaborative framework for time-critical applications. IEEE Trans. Network Science Engrg. 7 (2019), 4, 2271-2285.   DOI:10.1109/TNSE.2019.2941754
  30. R. S. Somula and S. Ra: A survey on mobile cloud computing: mobile computing$+$cloud computing (MCC$=$MC$+$CC). Scalable Computing: Practice and Experience 19 (2018) 4, 309-337.   DOI:10.12694/scpe.v19i4.1411
  31. O. Vencalek and D. Hlubinka: A depth-based modification of the k-nearest neighbour method. Kybernetika 57 (2021), 1, 15-37.   DOI:10.14736/kyb-2021-1-0015
  32. X. Y. Wang, Z. L. Ning and S. Guo: Multi-agent imitation learning for pervasive edge computing: a decentralized computation offloading algorithm. IEEE Trans. Parallel Distributed Systems 32 (2020), 2, 411-425.   DOI:10.1109/TPDS.2020.3023936
  33. L. C. Yang, H. L. Zhang, X. Li, H. Ji and V. C. M. Leung: A distributed computation offloading strategy in small-cell networks integrated with mobile edge computing. IEEE ACM Trans. Networking 26 (2018), 6, 2762-2773.   DOI:10.1109/TNET.2018.2876941
  34. M. Yuyi, C. You, J. Zhang, K. Huang and K. Letaief: A survey on mobile edge computing: the communication perspective. IEEE Commun. Surveys Tutorials 19 (2017), 4, 2322-2358.   DOI:10.1109/COMST.2017.2745201
  35. F. Zhang, J. Ge, Z. Li, C. Li, C. Wong, L. Kong, B. Luo and V. Chang: A load-aware resource allocation and task scheduling for the emerging cloudlet system. Future Generation Computer Systems 87 (2018), 438-456.   DOI:10.1016/j.future.2018.01.053
  36. P. Zhang and M. Zhou: Dynamic cloud task scheduling based on a two-stage strategy. IEEE Trans. Automat. Sci. Engrg. 15 (2018), 2, 772-783.   DOI:10.1109/TASE.2017.2693688