A combinatorial auction mechanism for time-varying multidimensional resource allocation and pricing in fog computing

Li, Shiyong ; Zhang, Yanan ; Sun, Wei ; Liu, Jia 

International Journal of Applied Mathematics and Computer Science, Tome 33 (2023) no. 2, pp. 327-339.

Résumé

It is a hot topic to investigate resource allocation in fog computing. However, currently resource allocation in fog computing mostly supports only fixed resources, that is, the resource requirements of users are satisfied with a fixed amount of resources during the usage time, which may result in low utility of resource providers and even cause a waste of resources. Therefore, we establish an integer programming model for the time-varying multidimensional resource allocation problem in fog computing to maximize the utility of the fog resource pool. We also design a heuristic algorithm to approximate the solution of the model. We apply a dominant-resource-based strategy for resource allocation to improve resource utilization as well as critical value theory for resource pricing to enhance the utility of the fog resource pool. We also prove that the algorithm satisfies truthful and individual rationality. Finally, we give some numerical examples to demonstrate the performance of the algorithm. Compared with existing studies, our approach can improve resource utilization and maximize the utility of the fog resource pool.

Détail

Keywords: fog computing, combinatorial auction, time varying multidimensional resource allocation, resource pricing
Mots-clés : mgła obliczeniowa, aukcja kombinatoryczna, wycena zasobów

Bibliographie

[1] [1] Aggarwal, A., Kumar, N., Vidyarthi, D. and Buyya, R. (2021). Fog-integrated cloud architecture enabled multi-attribute combinatorial reverse auctioning framework, Simulation Modelling Practice and Theory 109: 102307.

[2] [2] Alibaba (2019). Alibaba cloud, https://tianchi.aliyu n.com/.

[3] [3] Angelelli, E. and Filippi, C. (2011). On the complexity of interval scheduling with a resource constraint, Theoretical Computer Science 412(29): 3650-3657.

[4] [4] Bandyopadhyay, A., Roy, T., Sarkar, V. and Mallik, S. (2020). Combinatorial auction-based fog service allocation mechanism for IoT applications, 2020 10th International Conference on Cloud Computing, Data Science and Engineering (Confluence), Noida, India, pp. 518-524.

[5] [5] Baranwal, G. and Kumar, D. (2020). DAFNA: Decentralized auction based fog node allocation in 5G era, 2020 IEEE 15th International Conference on Industrial and Information Systems (ICIIS), Rupnagar, Punjab, India, pp. 575-580.

[6] [6] Bermbach, D., Maghsudi, S., Hasenburg, J. and Pfandzelter, T. (2020). Towards auction-based function placement in serverless fog platforms, 2020 IEEE International Conference on Fog Computing (ICFC), Sydney, Australia, pp. 25-31.

[7] [7] Besharati, R., Rezvani, M. and Sadeghi, M. (2021). An incentive-compatible off loading mechanism in fog-cloud environments using second-price sealed-bid auction, Journal of Grid Computing 19(3): 37.

[8] [8] Chang, B.-J., Hwang, R.-H., Tsai, Y.-L., Yu, B.-H. and Liang, Y.-H. (2019). Cooperative adaptive driving for platooning autonomous self driving based on edge computing, International Journal of Applied Mathematics and Computer Science 29(2): 213-225, DOI: 10.2478/amcs-2019-0016.

[9] [9] Ghobaei-Arani, M., Souri, A. and Rahmanian, A. (2020). Resource management approaches in fog computing: A comprehensive review, Journal of Grid Computing 18(1): 1-42.

[10] [10] Guo, Y., Saito, T., Oma, R., Nakamura, S., Enokido, T. and Takizawa, M. (2020). Distributed approach to fog computing with auction method, Advanced Information Networking and Applications 1151: 268-275.

[11] [11] Han, C., Zhang, P., Wang, W., Wang, W., Wang, Y. and Zhang, Z. (2019). Delay-optimal joint processing in computation-constrained fog radio access networks, IEEE Access 7: 58857-58865.

[12] [12] Houshyar, M., Seyyed, J., Hamidreza, N. and Afshin, R. (2021). A new resource allocation method in fog computing via non-cooperative game theory, Journal of Intelligent & Fuzzy Systems 41(2): 3921-3932.

[13] [13] Junior, F., Dias, K., d’Orey, P. and Kokkinogenis, Z. (2021). Fogwise: On the limits of the coexistence of heterogeneous applications on fog computing and Internet of vehicles, Transactions on Emerging Telecommunications Technologies 32(1): e4145.

[14] [14] Kayal, P. and Liebeherr, J. (2019). Distributed service placement in fog computing: An iterative combinatorial auction approach, 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), Richardson, USA, pp. 2145-2156.

[15] [15] Leao, A., Cherri, L. and Arenales, M. (2014). Determining the k-best solutions of knapsack problems, Computers & Operations Research 49: 71-82.

[16] [16] Lee, Y., Jeong, S., Masood, A., Park, L., Dao, N. and Cho, S. (2020). Trustful resource management for service allocation in fog-enabled intelligent transportation systems, IEEE Access 8: 147313-147322.

[17] [17] Li, S., Liu, H., Li, W. and Sun, W. (2023). An optimization framework for migrating and deploying multiclass enterprise applications into the cloud, IEEE Transactions on Services Computing 16(2): 941-956.

[18] [18] Li, S. and Sun, W. (2021). Utility maximisation for resource allocation of migrating enterprise applications into the cloud, Enterprise Information Systems 15(2): 197-229.

[19] [19] Li, S., Zhang, Y., Wang, Y. and Sun, W. (2019). Utility optimization-based bandwidth allocation for elastic and inelastic services in peer-to-peer networks, International Journal of Applied Mathematics and Computer Science 29(1): 111-123, DOI: 10.2478/amcs-2019-0009.

[20] [20] Mashayekhy, L., Nejad, M., Grosu, D. and Vasilakos, A. (2016). An online mechanism for resource allocation and pricing in clouds, IEEE Transactions on Computers 65(4): 1172-1184.

[21] [21] Peng, X., Ota, K. and Dong, M. (2020). Multiattribute-based double auction toward resource allocation in vehicular fog computing, IEEE Internet of Things Journal 7(4): 3094-3103.

[22] [22] Sharghivand, N., Derakhshan, F. and Siasi, N. (2021). A comprehensive survey on auction mechanism design for cloud/edge resource management and pricing, IEEE Access 9: 126502-126529.

[23] [23] Song, F., Ai, Z., Zhang, H., You, I. and Li, S. (2021a). Smart collaborative balancing for dependable network components in cyber-physical systems, IEEE Transactions on Industrial Informatics 17(10): 6916-6924.

[24] [24] Song, F., Li, L., You, I. and Zhang, H. (2021b). Enabling heterogeneous deterministic networks with smart collaborative theory, IEEE Network 35(3): 64-71.

[25] [25] Sun, H., Yu, H. and Fan, G. (2020). Contract-based resource sharing for time effective task scheduling in fog-cloud environment, IEEE Transactions on Network and Service Management 17(2): 1040-1053.

[26] [26] Tasiopoulos, A., Onur, A., Ioannis, P. and George, P. (2018). Edge-map: Auction markets for edge resource provisioning, 2018 IEEE 19th International Symposium “A World of Wireless, Mobile and Multimedia Networks (WoWMoM)”, Chania, Greece, pp. 14-22.

[27] [27] Zaman, S. and Grosu, D. (2012). Combinatorial auction-based allocation of virtual machine instances in clouds, Journal of Parallel and Distributed Computing 73(4): 495-508.

[28] [28] Zhang, J., Li, J., Li, W. and Zhang, X. (2019). A fair distribution strategy based on shared fair and time-varying resource demand, Journal of Computer Research and Development 56(7): 1534-1544.

[29] [29] Zhang, J., Yang, X., Xie, N., Zhang, X., Vasilakos, A. and Li, W. (2020). An online auction mechanism for time-varying multidimensional resource allocation in clouds, Future Generation Computer Systems 111: 27-38.

[30] [30] Zhu, L., Sun, L. and Yan, Y. (2020). Parking assistance scheme based on reverse auction in vehicle fog computing, Computer Engineering 46(7): 14-20.