Budgeted Edge Service Selection in Mobile Edge Computing Environment
- 30 September 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Systems Journal
- Vol. 17 (2) , 2779-2790
Abstract
Mobile edge computing allows end-users to retrieve required services from edge servers with low network latency. However, when massive service instances with the same or interchangeable functionalities are available at the network edge, how to select appropriate service instances for use to minimize the overall latency perceived is a critical problem. This is not trivial due to that: 1) usually multiple service instances are involved to collectively fulfil an end-user's ever-increasing complicated need; 2) the overall cost incurred should not exceed end-user's service recruiting budget. In this article, we formally define the budgeted edge service selection (BESS) problem. Then, we model the BESS problem as a constrained optimization problem and theoretically prove its $\mathcal {NP}$ -hardness. Next, to solve the BESS problem effectively, we propose two approaches named BESS-O and BESS-A, respectively. Specifically, BESS-O is an optimal approach based on nonlinear integer programming. It can find out optimal solutions to BESS problems. Moreover, BESS-A is a greedy approach. It can find out approximate BESS solutions with higher efficiency, which is more useful for dealing with large-scale BESS problems. Finally, we conduct comprehensive experiments to evaluate our approaches against five representative approaches. Experimental results demonstrate that given a specific service usage budget, our approaches proposed in this article can achieve the highest completion ratio and the lowest service delay.Keywords
Funding Information
- National Natural Science Foundation of China (61672022, U1904186)
- Key Disciplines of Software Engineering of Shanghai Polytechnic University (XXKZD1604)
This publication has 39 references indexed in Scilit:
- Service Selection for Composition in Mobile Edge Computing Systems2018
- It's Hard to Share: Joint Service Placement and Request Scheduling in Edge Clouds with Sharable and Non-Sharable Resources2018
- Joint Service Caching and Task Offloading for Mobile Edge Computing in Dense Networks2018
- Combinational Auction-Based Service Provider Selection in Mobile Edge Computing NetworksIEEE Access, 2017
- Task Assignment on Multi-Skill Oriented Spatial CrowdsourcingIEEE Transactions on Knowledge and Data Engineering, 2016
- Mobile Service Selection for Composition: An Energy Consumption PerspectiveIEEE Transactions on Automation Science and Engineering, 2015
- Dynamic cloud service selection using an adaptive learning mechanism in multi-cloud computingJournal of Systems and Software, 2015
- Service Selection for Composition with QoS CorrelationsIEEE Transactions on Services Computing, 2014
- The Multiple-Choice Knapsack Problem2004
- A note on the complexity of Dijkstra's algorithm for graphs with weighted verticesIEEE Transactions on Computers, 1998