{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T06:24:44Z","timestamp":1766298284073,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Chinese Natural Science Foundation","award":["11361048"],"award-info":[{"award-number":["11361048"]}]},{"DOI":"10.13039\/501100011002","name":"National Natural Science Foundation of China-Yunnan Joint Fund","doi-asserted-by":"publisher","award":["2017FH001-014"],"award-info":[{"award-number":["2017FH001-014"]}],"id":[{"id":"10.13039\/501100011002","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Yunnan Science Foundation","award":["2019J0613"],"award-info":[{"award-number":["2019J0613"]}]},{"name":"Qujing Normal University Science Foundation","award":["ZDKC2016002"],"award-info":[{"award-number":["ZDKC2016002"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cloud Comp"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Mobile edge computing (MEC) allows a mobile device to offload tasks to the nearby server for remote execution to enhance the performance of user equipment. A major challenge of MEC is to design an efficient algorithm for task allocation. In contrast to previous work on MEC, which mainly focuses on single-task allocation for a mobile device with only one task to be completed, this paper considers a mobile device with multiple tasks or an application with multiple tasks. This assumption does not hold in real settings because a mobile device may have multiple tasks waiting to execute. We address the problem of task allocation with minimum total energy consumption considering multi-task settings in MEC, in which a mobile device has one or more tasks. We consider the binary computation offloading mode and formulate multi-task allocation as an integer programming problem that is strongly <jats:italic>NP<\/jats:italic>-hard. We propose an approximation algorithm and show it is a polynomial-time approximation scheme that saves the maximum energy. Therefore, our proposed algorithm achieves a tradeoff between optimality loss and time complexity. We analyze the performance of the proposed algorithm by performing extensive experiments. The results of the experiments demonstrate that our proposed approximation algorithm is capable of finding near-optimal solutions, and achieves a good balance of speed and quality.<\/jats:p>","DOI":"10.1186\/s13677-022-00342-1","type":"journal-article","created":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T19:08:05Z","timestamp":1666897685000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Energy-efficient allocation for multiple tasks in mobile edge computing"],"prefix":"10.1186","volume":"11","author":[{"given":"Jun","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8011-5419","authenticated-orcid":false,"given":"Xi","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,27]]},"reference":[{"issue":"1","key":"342_CR1","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1109\/MCOM.2014.6710075","volume":"52","author":"S Davy","year":"2014","unstructured":"Davy S, Famaey J, Serrat J, Gorricho LJ, Miron A, Dramitinos M, Neves MP, Latre S, Goshen E (2014) Challenges to support edge-as-a-service. IEEE Commun Mag 52(1):132\u2013139","journal-title":"IEEE Commun Mag"},{"issue":"4","key":"342_CR2","doi-asserted-by":"publisher","first-page":"2322","DOI":"10.1109\/COMST.2017.2745201","volume":"19","author":"Y Mao","year":"2017","unstructured":"Mao Y, You C, Zhang J, Huang K, Letaief KB (2017) A survey on mobile edge computing: the communication perspective. IEEE Commun Surv Tutor 19(4):2322\u20132358","journal-title":"IEEE Commun Surv Tutor"},{"key":"342_CR3","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1186\/s13677-020-0158-3","volume":"9","author":"L Kuang","year":"2020","unstructured":"Kuang L, Tu S, Zhang Y, Yang X (2020) Providing privacy preserving in next POI recommendation for Mobile edge computing. J Cloud Comput Adv Syst Appl 9:10","journal-title":"J Cloud Comput Adv Syst Appl"},{"issue":"5","key":"342_CR4","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1109\/MNET.2013.6616113","volume":"27","author":"W Zhang","year":"2013","unstructured":"Zhang W, Wen Y, Wu J, Li H (2013) Toward a unified elastic computing platform for smartphones with cloud support. IEEE Netw 27(5):34\u201340","journal-title":"IEEE Netw"},{"issue":"5","key":"342_CR5","doi-asserted-by":"publisher","first-page":"3170","DOI":"10.1109\/TWC.2020.2970920","volume":"19","author":"F Zhou","year":"2020","unstructured":"Zhou F, Hu QR (2020) Computation efficiency maximization in wireless-powered mobile edge computing networks. IEEE Trans Wirel Commun 19(5):3170\u20133184","journal-title":"IEEE Trans Wirel Commun"},{"key":"342_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Keller","year":"2004","unstructured":"Keller H, Pferschy U, Pisinger D (2004) Knapsack Problems. Springer, Berlin, Heidelberg"},{"issue":"1","key":"342_CR7","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1109\/TETC.2014.2387688","volume":"3","author":"Z Cheng","year":"2015","unstructured":"Cheng Z, Li P, Wang J, Guo S (2015) Just-in-time code offloading for wearable computing. IEEE Trans Emerg Top Comput 3(1):74\u201383","journal-title":"IEEE Trans Emerg Top Comput"},{"issue":"1","key":"342_CR8","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1109\/TWC.2014.2331051","volume":"14","author":"W Zhang","year":"2015","unstructured":"Zhang W, Wen Y, Wu OD (2015) Collaborative task execution in mobile cloud computing under a stochastic wireless channel. IEEE Trans Wirel Commun 14(1):81\u201393","journal-title":"IEEE Trans Wirel Commun"},{"issue":"10","key":"342_CR9","doi-asserted-by":"publisher","first-page":"4738","DOI":"10.1109\/TVT.2014.2372852","volume":"64","author":"O Mu\u00f1oz","year":"2015","unstructured":"Mu\u00f1oz O, Pascual-Iserte A, Vidal J (2015) Optimization of radio and computational resources for energy efficiency in latency-constrained application offloading. IEEE Trans Veh Technol 64(10):4738\u20134755","journal-title":"IEEE Trans Veh Technol"},{"key":"342_CR10","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.future.2020.05.025","volume":"112","author":"Y Zhang","year":"2020","unstructured":"Zhang Y, Liu Y, Zhou J, Sun J, Li K (2020) Slow-movement particle swarm optimization algorithms for scheduling security-critical tasks in resource-limited mobile edge computing. Futur Gener Comput Syst 112:148\u2013161","journal-title":"Futur Gener Comput Syst"},{"issue":"3","key":"342_CR11","doi-asserted-by":"publisher","first-page":"3341","DOI":"10.1109\/TVT.2020.2966500","volume":"69","author":"W Zhan","year":"2020","unstructured":"Zhan W, Luo C, Min Wang C, Zhu Q, Duan H (2020) Mobility-aware multi-user offloading optimization for mobile edge computing. IEEE Trans Veh Technol 69(3):3341\u20133356","journal-title":"IEEE Trans Veh Technol"},{"key":"342_CR12","doi-asserted-by":"publisher","first-page":"1776","DOI":"10.1007\/s12083-020-00880-y","volume":"13","author":"J Huang","year":"2020","unstructured":"Huang J, Li S, Chen Y (2020) Revenue-optimal task scheduling and resource management for IoT batch jobs in mobile edge computing. Peer Peer Netw Appl 13:1776\u20131787","journal-title":"Peer Peer Netw Appl"},{"key":"342_CR13","doi-asserted-by":"publisher","unstructured":"Liu X, Liu J, Wu H (2022) Energy-aware allocation for delay-sensitive multitask in mobile edge computing. J Supercomput. https:\/\/doi.org\/10.1007\/s11227-022-04550-z","DOI":"10.1007\/s11227-022-04550-z"},{"issue":"3","key":"342_CR14","doi-asserted-by":"publisher","first-page":"1405","DOI":"10.1109\/TNET.2020.2983119","volume":"28","author":"AP Apostolopoulos","year":"2020","unstructured":"Apostolopoulos AP, Tsiropoulou EE, Papavassiliou S (2020) Risk-aware data offloading in multi-server multi-access edge computing environment. IEEE\/ACM Trans Netw 28(3):1405\u20131418","journal-title":"IEEE\/ACM Trans Netw"},{"key":"342_CR15","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.future.2020.02.045","volume":"108","author":"Y Chen","year":"2020","unstructured":"Chen Y, Li Z, Yang B, Nai K, Li K (2020) A stackelberg game approach to multiple resources allocation and pricing in mobile edge computing. Future Gener Comput Syst 108:273\u2013287","journal-title":"Future Gener Comput Syst"},{"issue":"12","key":"342_CR16","doi-asserted-by":"publisher","first-page":"3887","DOI":"10.1109\/JSAC.2016.2624118","volume":"34","author":"L Pu","year":"2016","unstructured":"Pu L, Chen X, Xu J, Fu X (2016) D2D fogging: an energy-efficient and incentive-aware task offloading framework via network-assisted d2d collaboration. IEEE J Sel Areas Commun 34(12):3887\u20133901","journal-title":"IEEE J Sel Areas Commun"},{"issue":"4","key":"342_CR17","doi-asserted-by":"publisher","first-page":"974","DOI":"10.1109\/TPDS.2014.2316834","volume":"26","author":"X Chen","year":"2015","unstructured":"Chen X (2015) Decentralized computation offloading game for mobile cloud computing. IEEE Trans Parallel Distrib Syst 26(4):974\u2013983","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"5","key":"342_CR18","doi-asserted-by":"publisher","first-page":"2795","DOI":"10.1109\/TNET.2015.2487344","volume":"24","author":"X Chen","year":"2016","unstructured":"Chen X, Jiao L, Li W, Fu X (2016) Efficient multi-user computation offloading for mobile-edge cloud computing. IEEE\/ACM Trans Netw 24(5):2795\u20132808","journal-title":"IEEE\/ACM Trans Netw"},{"issue":"10","key":"342_CR19","doi-asserted-by":"publisher","first-page":"2398","DOI":"10.1109\/TMC.2015.2504091","volume":"15","author":"Y Liu","year":"2016","unstructured":"Liu Y, Lee JM, Zheng Y (2016) Adaptive multi-resource allocation for cloudlet-based mobile cloud computing system. IEEE Trans Mob Comput 15(10):2398\u20132410","journal-title":"IEEE Trans Mob Comput"},{"issue":"11","key":"342_CR20","doi-asserted-by":"publisher","first-page":"2606","DOI":"10.1109\/JSAC.2017.2760186","volume":"35","author":"X Lyu","year":"2017","unstructured":"Lyu X, Ni W, Tian H, Liu PR, Wang X, Giannakis BG, Paulraj A (2017) Optimal schedule of mobile edge computing for internet of things using partial information. IEEE J Sel Areas Commun 35(11):2606\u20132615","journal-title":"IEEE J Sel Areas Commun"},{"issue":"6","key":"342_CR21","doi-asserted-by":"publisher","first-page":"2603","DOI":"10.1109\/TCOMM.2018.2799937","volume":"66","author":"X Lyu","year":"2018","unstructured":"Lyu X, Tian H, Ni W, Zhang Y, Zhang P (2018) Energy-efficient admission of delay-sensitive tasks for mobile edge computing. IEEE Trans Commun 66(6):2603\u20132616","journal-title":"IEEE Trans Commun"},{"issue":"3","key":"342_CR22","doi-asserted-by":"publisher","first-page":"1784","DOI":"10.1109\/TWC.2017.2785305","volume":"17","author":"F Wang","year":"2018","unstructured":"Wang F, Xu J, Wang X, Cui S (2018) Joint offloading and computing optimization in wireless powered mobile-edge computing systems. IEEE Trans Wirel Commun 17(3):1784\u20131797","journal-title":"IEEE Trans Wirel Commun"},{"issue":"3","key":"342_CR23","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1109\/JSAC.2018.2815360","volume":"36","author":"M Chen","year":"2018","unstructured":"Chen M, Hao Y (2018) Task offloading for mobile edge computing in software defined ultra-dense network. IEEE J Sel Areas in Commun 36(3):587\u2013597","journal-title":"IEEE J Sel Areas in Commun"},{"issue":"9","key":"342_CR24","doi-asserted-by":"publisher","first-page":"8419","DOI":"10.1109\/JIOT.2020.2992522","volume":"7","author":"Y Chen","year":"2020","unstructured":"Chen Y, Zhang Y, Wu Y, Qi L, Chen X, Shen X (2020) Joint task scheduling and energy management for heterogeneous mobile edge computing with hybrid energy supply. IEEE Internet Things J 7(9):8419\u20138429","journal-title":"IEEE Internet Things J"},{"issue":"11","key":"342_CR25","doi-asserted-by":"publisher","first-page":"7140","DOI":"10.1109\/TCOMM.2020.3011990","volume":"68","author":"F Wang","year":"2020","unstructured":"Wang F, Xing H, Xu J (2020) Real-time resource allocation for wireless powered multiuser mobile edge computing with energy and task causality. IEEE Trans Commun 68(11):7140\u20137155","journal-title":"IEEE Trans Commun"},{"issue":"3","key":"342_CR26","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1109\/TNET.2020.2979807","volume":"8","author":"Y Zhang","year":"2020","unstructured":"Zhang Y, Lan X, Ren J, Cai L (2020) Efficient computing resource sharing for mobile edge-cloud computing networks. IEEE\/ACM Trans Netw 8(3):1227\u20131240","journal-title":"IEEE\/ACM Trans Netw"},{"issue":"2","key":"342_CR27","doi-asserted-by":"publisher","first-page":"1038","DOI":"10.1109\/TWC.2020.3030178","volume":"20","author":"C Park","year":"2021","unstructured":"Park C, Lee J (2021) Mobile edge computing-enabled heterogeneous networks. IEEE Trans Wirel Commun 20(2):1038\u20131051","journal-title":"IEEE Trans Wirel Commun"},{"key":"342_CR28","doi-asserted-by":"publisher","unstructured":"Liu X, Liu J (2021) A truthful double auction mechanism for multi-resource allocation in crowd sensing systems. IEEE Trans Serv Comput. https:\/\/doi.org\/10.1109\/TSC.2021.3075541","DOI":"10.1109\/TSC.2021.3075541"},{"issue":"1","key":"342_CR29","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1109\/TCCN.2021.3093436","volume":"8","author":"C Zhao","year":"2022","unstructured":"Zhao C, Lei Z, Yukui P, Chunxiao J, Liuguo Y (2022) NOMA-based multi-user mobile edge computation offloading via cooperative multi-agent deep reinforcement learning. IEEE Trans Cogn Commun Netw 8(1):350\u2013364","journal-title":"IEEE Trans Cogn Commun Netw"},{"issue":"4","key":"342_CR30","doi-asserted-by":"publisher","first-page":"2763","DOI":"10.1109\/JIOT.2019.2957313","volume":"7","author":"N Nima","year":"2020","unstructured":"Nima N, Ahmadreza E, Jamshid A, Muhammad J, Alagan A (2020) Dynamic power-latency tradeoff for mobile edge computation offloading in NOMA-based networks. IEEE Internet Things J 7(4):2763\u20132776","journal-title":"IEEE Internet Things J"},{"key":"342_CR31","doi-asserted-by":"publisher","unstructured":"Zhao C, Xiaodong W (2020) Decentralized computation offloading for multi-user mobile edge computing: a deep reinforcement learning approach. EURASIP J Wireless Commun Netw 188. https:\/\/doi.org\/10.1186\/s13638-020-01801-6","DOI":"10.1186\/s13638-020-01801-6"},{"issue":"4","key":"342_CR32","doi-asserted-by":"publisher","first-page":"2410","DOI":"10.1109\/TNSM.2020.3020249","volume":"17","author":"AT Elgendy","year":"2020","unstructured":"Elgendy AT, Zhang W, Zeng Y, He H, Tian Y, Yang Y (2020) Efficient and secure multi-user multi-task computation offloading for mobile-edge computing in mobile iot networks. IEEE Trans Netw Serv Manag 17(4):2410\u20132422","journal-title":"IEEE Trans Netw Serv Manag"},{"issue":"10","key":"342_CR33","doi-asserted-by":"publisher","first-page":"6790","DOI":"10.1109\/TWC.2018.2864559","volume":"17","author":"M Chen","year":"2018","unstructured":"Chen M, Liang B, Dong M (2018) Multi-user multi-task offloading and resource allocation in mobile cloud systems. IEEE Trans Wirel Commun 17(10):6790\u20136805","journal-title":"IEEE Trans Wirel Commun"},{"issue":"6","key":"342_CR34","doi-asserted-by":"publisher","first-page":"1446","DOI":"10.3390\/s19061446","volume":"19","author":"L Huang","year":"2019","unstructured":"Huang L, Feng X, Zhang L, Qian L, Wu Y (2019) Multi-server multi-user multi-task computation offloading for mobile edge computing networks. Sensors (Basel) 19(6):1446","journal-title":"Sensors (Basel)"},{"issue":"6","key":"342_CR35","doi-asserted-by":"publisher","first-page":"726","DOI":"10.1109\/TSC.2018.2826544","volume":"12","author":"W Chen","year":"2019","unstructured":"Chen W, Wang D, Li K (2019) Multi-user multi-task computation offloading in green mobile edge cloud computing. IEEE Trans Serv Comput 12(6):726\u2013738","journal-title":"IEEE Trans Serv Comput"},{"key":"342_CR36","doi-asserted-by":"publisher","first-page":"119700","DOI":"10.1109\/ACCESS.2021.3108342","volume":"9","author":"X Liu","year":"2021","unstructured":"Liu X, Liu J, Wu H (2021) Energy-efficient task allocation of heterogeneous resources in mobile edge computing. IEEE Access 9:119700\u2013119711","journal-title":"IEEE Access"},{"issue":"11","key":"342_CR37","doi-asserted-by":"publisher","first-page":"2666","DOI":"10.1109\/JSAC.2020.3007035","volume":"38","author":"T Bai","year":"2020","unstructured":"Bai T, Pan C, Deng Y, Elkashlan M, Nallanathan A, Hanao L (2020) Latency minimization for intelligent reflecting surface aided mobile edge computing. IEEE J Sel Areas Commun 38(11):2666\u20132682","journal-title":"IEEE J Sel Areas Commun"},{"issue":"1","key":"342_CR38","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1109\/SURV.2013.062613.00160","volume":"16","author":"AR Khan","year":"2014","unstructured":"Khan AR, Othman M, Madani SA, Khan SU (2014) A survey of mobile cloud computing application models. IEEE Commun Surv Tutor 16(1):393\u2013413","journal-title":"IEEE Commun Surv Tutor"},{"issue":"2","key":"342_CR39","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1109\/TSC.2014.2381227","volume":"8","author":"X Lin","year":"2015","unstructured":"Lin X, Wang Y, Xie Q, Pedram M (2015) Task scheduling with dynamic voltage and frequency scaling for energy minimization in the mobile cloud computing environment. IEEE Trans Serv Comput 8(2):175\u2013186","journal-title":"IEEE Trans Serv Comput"},{"issue":"2","key":"342_CR40","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0377-2217(99)00261-1","volume":"123","author":"A Caprara","year":"2000","unstructured":"Caprara A, Kellerer H, Pferschy U, Pisinger D (2000) Approximation algorithms for knapsack problems with cardinality constraints. Eur J Oper Res 123(2):333\u2013345","journal-title":"Eur J Oper Res"},{"key":"342_CR41","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1613\/jair.2950","volume":"37","author":"S Dobzinski","year":"2010","unstructured":"Dobzinski S, Nisam N (2010) Mechanisms for multi-unit auctions. J Artif Intell Res 37:85\u201398","journal-title":"J Artif Intell Res"},{"key":"342_CR42","volume-title":"Integer Programming","author":"SR Garfinkel","year":"1972","unstructured":"Garfinkel SR, Nemhauser LG (1972) Integer Programming. Wiley, New York"}],"container-title":["Journal of Cloud Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13677-022-00342-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13677-022-00342-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13677-022-00342-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,30]],"date-time":"2022-10-30T22:03:09Z","timestamp":1667167389000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofcloudcomputing.springeropen.com\/articles\/10.1186\/s13677-022-00342-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,27]]},"references-count":42,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["342"],"URL":"https:\/\/doi.org\/10.1186\/s13677-022-00342-1","relation":{},"ISSN":["2192-113X"],"issn-type":[{"type":"electronic","value":"2192-113X"}],"subject":[],"published":{"date-parts":[[2022,10,27]]},"assertion":[{"value":"11 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare there is no conflicts of interest regarding the publication of this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"71"}}