Exact and Approximation Algorithms for Task Offloading with Service Caching and Dependency in Mobile Edge Computing
With the continuous development of the Internet of Things (IoT) and communication technologies, the demand for low latency in practical applications is becoming increasingly significant. Mobile edge computing, as a promising computational model, is receiving growing attention. However, most existing...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-06-01
|
| Series: | Future Internet |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-5903/17/6/255 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849431908625154048 |
|---|---|
| author | Bowen Cui Jianwei Zhang |
| author_facet | Bowen Cui Jianwei Zhang |
| author_sort | Bowen Cui |
| collection | DOAJ |
| description | With the continuous development of the Internet of Things (IoT) and communication technologies, the demand for low latency in practical applications is becoming increasingly significant. Mobile edge computing, as a promising computational model, is receiving growing attention. However, most existing studies fail to consider two critical factors: task dependency and service caching. Additionally, the majority of proposed solutions are not related to the optimal solution. We investigate the task offloading problem in mobile edge computing. Considering the requirements of applications for service caching and task dependency, we define an optimization problem to minimize the delay under the constraint of maximum completion cost and present a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>+</mo><mi>ϵ</mi><mo>)</mo></mrow></semantics></math></inline-formula>-approximation algorithm and an exact algorithm. Specifically, the offloading scheme is determined based on the relationships between tasks as well as the cost and delay incurred by data transmission and task execution. Simulation results demonstrate that in all cases, the offloading schemes obtained by our algorithm consistently outperform other algorithms. Moreover, the approximation ratio to the optimal solution from the approximation algorithm is validated to be less than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>+</mo><mi>ϵ</mi><mo>)</mo></mrow></semantics></math></inline-formula>, and the exact algorithm consistently produces the optimal solution. |
| format | Article |
| id | doaj-art-39f2626b6fca4b9986a4b339f3d59743 |
| institution | Kabale University |
| issn | 1999-5903 |
| language | English |
| publishDate | 2025-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Future Internet |
| spelling | doaj-art-39f2626b6fca4b9986a4b339f3d597432025-08-20T03:27:29ZengMDPI AGFuture Internet1999-59032025-06-0117625510.3390/fi17060255Exact and Approximation Algorithms for Task Offloading with Service Caching and Dependency in Mobile Edge ComputingBowen Cui0Jianwei Zhang1School of Information Science and Engineering, Yunnan University, Kunming 650500, ChinaSchool of Information Science and Engineering, Yunnan University, Kunming 650500, ChinaWith the continuous development of the Internet of Things (IoT) and communication technologies, the demand for low latency in practical applications is becoming increasingly significant. Mobile edge computing, as a promising computational model, is receiving growing attention. However, most existing studies fail to consider two critical factors: task dependency and service caching. Additionally, the majority of proposed solutions are not related to the optimal solution. We investigate the task offloading problem in mobile edge computing. Considering the requirements of applications for service caching and task dependency, we define an optimization problem to minimize the delay under the constraint of maximum completion cost and present a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>+</mo><mi>ϵ</mi><mo>)</mo></mrow></semantics></math></inline-formula>-approximation algorithm and an exact algorithm. Specifically, the offloading scheme is determined based on the relationships between tasks as well as the cost and delay incurred by data transmission and task execution. Simulation results demonstrate that in all cases, the offloading schemes obtained by our algorithm consistently outperform other algorithms. Moreover, the approximation ratio to the optimal solution from the approximation algorithm is validated to be less than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>+</mo><mi>ϵ</mi><mo>)</mo></mrow></semantics></math></inline-formula>, and the exact algorithm consistently produces the optimal solution.https://www.mdpi.com/1999-5903/17/6/255mobile edge computing (MEC)task offloadingtask dependencyservice cachingapproximation algorithm |
| spellingShingle | Bowen Cui Jianwei Zhang Exact and Approximation Algorithms for Task Offloading with Service Caching and Dependency in Mobile Edge Computing Future Internet mobile edge computing (MEC) task offloading task dependency service caching approximation algorithm |
| title | Exact and Approximation Algorithms for Task Offloading with Service Caching and Dependency in Mobile Edge Computing |
| title_full | Exact and Approximation Algorithms for Task Offloading with Service Caching and Dependency in Mobile Edge Computing |
| title_fullStr | Exact and Approximation Algorithms for Task Offloading with Service Caching and Dependency in Mobile Edge Computing |
| title_full_unstemmed | Exact and Approximation Algorithms for Task Offloading with Service Caching and Dependency in Mobile Edge Computing |
| title_short | Exact and Approximation Algorithms for Task Offloading with Service Caching and Dependency in Mobile Edge Computing |
| title_sort | exact and approximation algorithms for task offloading with service caching and dependency in mobile edge computing |
| topic | mobile edge computing (MEC) task offloading task dependency service caching approximation algorithm |
| url | https://www.mdpi.com/1999-5903/17/6/255 |
| work_keys_str_mv | AT bowencui exactandapproximationalgorithmsfortaskoffloadingwithservicecachinganddependencyinmobileedgecomputing AT jianweizhang exactandapproximationalgorithmsfortaskoffloadingwithservicecachinganddependencyinmobileedgecomputing |