Towards Revenue-Driven Multi-User Online Task Offloading in Edge Computing

Zhi Ma, Sheng Zhang, Zhiqi Chen, Tao Han, Zhuzhong Qian, Mingjun Xiao, Ning Chen, Jie Wu, Sanglu Lu

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

Mobile Edge Computing (MEC) has become an attractive solution to enhance the computing and storage capacity of mobile devices by leveraging available resources on edge nodes. In MEC, the arrivals of tasks are highly dynamic and are hard to predict precisely. It is of great importance yet very challenging to assign the tasks to edge nodes with guaranteed system performance. In this article, we aim to optimize the revenue earned by each edge node by optimally offloading tasks to the edge nodes. We formulate the revenue-driven online task offloading (ROTO) problem, which is proved to be NP-hard. We first relax ROTO to a linear fractional programming problem, for which we propose the Level Balanced Allocation (LBA) algorithm. We then show the performance guarantee of LBA through rigorous theoretical analysis, and present the LB-Rounding algorithm for ROTO using the primal-dual technique. The algorithm achieves an approximation ratio of $2(1+\xi)\ln (d+1)$2(1+ξ)ln(d+1) with a considerable probability, where $d$d is the maximum number of process slots of an edge node and $\xi$ξ is a small constant. The performance of the proposed algorithm is validated through both trace-driven simulations and testbed experiments. Results show that our proposed scheme is more efficient compared to baseline algorithms.

Original languageEnglish (US)
Pages (from-to)1185-1198
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Volume33
Issue number5
DOIs
StatePublished - May 1 2022

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • Mobile edge computing
  • online computation offloading
  • primal-dual technique
  • revenue-optimal

Fingerprint

Dive into the research topics of 'Towards Revenue-Driven Multi-User Online Task Offloading in Edge Computing'. Together they form a unique fingerprint.

Cite this