pith. sign in

arxiv: 1906.09762 · v1 · pith:UW22SNTDnew · submitted 2019-06-24 · 📡 eess.SP · cs.IT· math.IT

Closed-Form Delay-Optimal Computation Offloading in Mobile Edge Computing Systems

Xianling Meng , Wei Wang , Yitu Wang , Vincent K. N. Lau , Zhaoyang Zhang This is my paper

Pith reviewed 2026-05-25 17:41 UTC · model grok-4.3

classification 📡 eess.SP cs.ITmath.IT
keywords computation offloadingmobile edge computingdelay optimizationMarkov decision processwater-fillingqueue state informationvirtual continuous time system
0
0 comments X

The pith

A closed-form multi-level water-filling solution optimizes delay in MEC offloading by using both local and remote queue states.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper models computation offloading in resource-constrained mobile edge computing as an infinite-horizon average-cost MDP where the task queue at the mobile terminal and the constrained queue at the MEC server are coupled in cascade. It approximates the discrete MDP by a virtual continuous time system with reflections and derives closed-form approximate priority functions through dynamic instantaneous rate estimation. From these functions the authors construct a multi-level water-filling policy that explicitly incorporates both local queue state information and remote queue state information. The same construction is extended to the multi-user multi-server case. A reader would care because the resulting policy is closed-form and therefore implementable without solving the original MDP at runtime.

Core claim

A closed-form multi-level water-filling computation offloading solution, obtained from approximate priority functions derived via dynamic instantaneous rate estimation in the virtual continuous time system, characterizes the influence of both local and remote queue state information and thereby achieves delay optimality in computation-constrained MEC systems.

What carries the argument

Closed-form multi-level water-filling computation offloading solution derived from approximate priority functions of the virtual continuous time system approximation.

If this is right

  • The policy extends directly from single-MT single-server to multiple-MT multiple-server scenarios.
  • Offloading decisions now depend on both local and remote queue lengths rather than local information alone.
  • Several explicit insights on the relative weighting of LQSI and RQSI follow from the water-filling levels.
  • Simulation results indicate lower average delay than conventional schemes that ignore the remote queue.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same rate-estimation-plus-water-filling pattern could be tested on other cascade-queue resource-allocation problems that are currently solved only by value iteration.
  • Because the policy is closed-form, it could be embedded in low-power firmware without requiring an online MDP solver.
  • The approximation quality may degrade when channel coherence time becomes comparable to the MDP decision interval; that regime could be checked by varying Doppler spread in simulation.

Load-bearing premise

The dynamic instantaneous rate estimation step yields sufficiently accurate closed-form approximate priority functions for the virtual continuous time system approximation of the original MDP.

What would settle it

Compare average delay of the proposed policy against the optimal policy obtained by solving the original MDP (or a high-fidelity simulator) in a scenario where remote queue length varies rapidly while local queue length is held fixed.

Figures

Figures reproduced from arXiv: 1906.09762 by Vincent K. N. Lau, Wei Wang, Xianling Meng, Yitu Wang, Zhaoyang Zhang.

Figure 1
Figure 1. Figure 1: Cascade queue system the cases with symmetric arrivals. Lyapunov optimization [26] is an effective approach on queue stability, but it is effective only when the queue backlog is large. MDP [12] is a systematic approach to minimize the delay. In general, the optimal control policy can be obtained by solving the well-known Bellman equation. Conventional solutions to the Bellman equation, such as brute-force… view at source ↗
Figure 2
Figure 2. Figure 2: Performance Analysis random task arrivals based on an open dataset Mobile Open Data by MobiPerf [32], which aver￾age arrival rates are 5.54 packet/s and 8.46 packets/s, respectively. Under the same environment conditions except for the average arrival rate, the six curves below are in computation sufficient scenario, and the six curves above are in computation constrained scenario. It can be observed that … view at source ↗
Figure 3
Figure 3. Figure 3: Delay performance with different environment condi [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Delay performance with different computation capab [PITH_FULL_IMAGE:figures/full_fig_p027_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Delay performance with different numbers of MTs and M [PITH_FULL_IMAGE:figures/full_fig_p028_5.png] view at source ↗
read the original abstract

Mobile edge computing (MEC) has recently emerged as a promising technology to release the tension between computation-intensive applications and resource-limited mobile terminals (MTs). In this paper, we study the delay-optimal computation offloading in computation-constrained MEC systems. We consider the computation task queue at the MEC server due to its constrained computation capability. In this case, the task queue at the MT and that at the MEC server are strongly coupled in a cascade manner, which creates complex interdependencies and brings new technical challenges. We model the computation offloading problem as an infinite horizon average cost Markov decision process (MDP), and approximate it to a virtual continuous time system (VCTS) with reflections. Different to most of the existing works, we develop the dynamic instantaneous rate estimation for deriving the closed-form approximate priority functions in different scenarios. Based on the approximate priority functions, we propose a closed-form multi-level water-filling computation offloading solution to characterize the influence of not only the local queue state information (LQSI) but also the remote queue state information (RQSI). A extension is provided from single MT single MEC server scenarios to multiple MTs multiple MEC servers scenarios and several insights are derived. Finally, the simulation results show that the proposed scheme outperforms the conventional schemes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper models delay-optimal computation offloading in MEC systems with cascade-coupled queues at the mobile terminal and MEC server as an infinite-horizon average-cost MDP. It approximates the discrete MDP by a virtual continuous-time system (VCTS) with reflections, applies dynamic instantaneous rate estimation to obtain closed-form approximate priority functions, and derives a multi-level water-filling offloading policy that incorporates both LQSI and RQSI. The approach is extended to multi-MT/multi-MEC scenarios, with simulation results claimed to outperform conventional schemes.

Significance. If the VCTS approximation and rate-estimation step are shown to be accurate, the closed-form multi-level water-filling policy would offer a tractable, analytically insightful solution for delay minimization under queue coupling, which is a practically relevant extension beyond single-queue MEC offloading analyses.

major comments (3)
  1. [§4] §4 (VCTS approximation step): the manuscript invokes the VCTS with reflections to replace the original discrete-time MDP but supplies no error bound, convergence rate, or regime of validity for the approximation error relative to the coupled LQSI/RQSI dynamics; without this, the subsequent priority functions cannot be guaranteed to inherit delay optimality.
  2. [§5] §5 (dynamic instantaneous rate estimation): the derivation of the closed-form approximate priority functions relies on this step, yet no quantitative comparison (e.g., mean-squared deviation or policy-value gap) is provided against the true discrete MDP transition probabilities, especially under cascade queue coupling; this is load-bearing for the central claim of closed-form optimality.
  3. [Simulation results] Simulation section (results and baselines): outperformance is asserted without reported error bars, sensitivity to rate-estimation parameters, or explicit description of the conventional schemes and MDP solver used for comparison, preventing assessment of whether the gains are attributable to the proposed policy or to the unvalidated approximation.
minor comments (2)
  1. [§5] Notation for the priority functions and water-filling thresholds should be introduced with explicit dependence on the estimated rates to avoid ambiguity when moving between the VCTS and the original MDP.
  2. [Multi-user extension] The extension to multiple MTs/MECs in the final section would benefit from a brief statement of how the per-user priority functions are coordinated across servers.

Simulated Author's Rebuttal

3 responses · 1 unresolved

We thank the referee for the constructive feedback on our manuscript. The comments highlight important aspects regarding the theoretical justification of our approximations and the presentation of simulation results. We address each major comment below and indicate the revisions we will make.

read point-by-point responses

  1. Referee: [§4] §4 (VCTS approximation step): the manuscript invokes the VCTS with reflections to replace the original discrete-time MDP but supplies no error bound, convergence rate, or regime of validity for the approximation error relative to the coupled LQSI/RQSI dynamics; without this, the subsequent priority functions cannot be guaranteed to inherit delay optimality.

    Authors: The VCTS approximation is employed to enable tractable closed-form derivations for the priority functions, consistent with fluid-limit techniques used in related MDP analyses of queueing systems. The resulting policy is presented as an approximate solution rather than an exactly optimal one. We will revise §4 to explicitly clarify the approximate nature of the approach, discuss the expected validity regime (e.g., large queue lengths or high system load), and add a remark noting that a rigorous error bound remains an open direction for future work. revision: partial

  2. Referee: [§5] §5 (dynamic instantaneous rate estimation): the derivation of the closed-form approximate priority functions relies on this step, yet no quantitative comparison (e.g., mean-squared deviation or policy-value gap) is provided against the true discrete MDP transition probabilities, especially under cascade queue coupling; this is load-bearing for the central claim of closed-form optimality.

    Authors: We acknowledge the absence of direct quantitative validation for the rate-estimation step against the exact MDP. In the revision, we will add a new subsection or appendix that provides numerical comparisons in small-scale instances (where the true MDP can be solved exactly), including metrics such as the deviation in priority function values and the resulting average delay gap between the approximate policy and the optimal MDP policy. This will strengthen the evidence for the accuracy of the estimation under cascade coupling. revision: yes

  3. Referee: [Simulation results] Simulation section (results and baselines): outperformance is asserted without reported error bars, sensitivity to rate-estimation parameters, or explicit description of the conventional schemes and MDP solver used for comparison, preventing assessment of whether the gains are attributable to the proposed policy or to the unvalidated approximation.

    Authors: We agree that the simulation results section requires additional details for reproducibility and robustness assessment. In the revised manuscript, we will: include error bars or standard deviations for all plotted metrics across multiple random seeds; provide explicit descriptions of the conventional schemes (e.g., threshold-based and myopic policies) and the numerical MDP solver employed; and add sensitivity plots with respect to key rate-estimation parameters. These changes will allow readers to better evaluate the source of the observed performance gains. revision: yes

standing simulated objections not resolved
  • A formal derivation of error bounds or convergence rates for the VCTS approximation under cascade-coupled LQSI/RQSI dynamics would require substantial new theoretical analysis that is beyond the scope of the current work.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation models the offloading problem as an infinite-horizon average-cost MDP, approximates it to a VCTS with reflections, applies dynamic instantaneous rate estimation to obtain closed-form approximate priority functions, and then constructs a multi-level water-filling policy that incorporates both LQSI and RQSI. No quoted equation or step in the provided text reduces a claimed prediction or optimality result to a fitted parameter or self-citation by construction. The approximations are presented explicitly as such rather than as exact identities, and the final policy is offered as an approximate solution whose performance is checked via simulation against conventional schemes. This keeps the central claim independent of the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed from abstract only; no explicit free parameters, axioms, or invented entities can be extracted.

pith-pipeline@v0.9.0 · 5772 in / 1166 out tokens · 37267 ms · 2026-05-25T17:41:13.237556+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [1]

    Delay -optimal computation offloading for computation- constrained mobile edge networks,

    X. Meng, W. Wang, Y . Wang, V . K. N. Lau, and Z. Zhang, “Delay -optimal computation offloading for computation- constrained mobile edge networks,” in Proc. IEEE Globecom , Abu Dhabi, United Arab Emirates, 2018, pp. 1-7. 35

    work page 2018

  2. [2]

    Dynamic computation offloading for mobile-edge computing with energy harvestin g devices,

    Y . Mao, J. Zhang, and K. B. Letaief, “Dynamic computation offloading for mobile-edge computing with energy harvestin g devices,” IEEE J. Sel. Areas Commun. , vol. 34, no. 12, pp. 3590-3605, Dec. 2016

    work page 2016

  3. [3]

    A dynamic bandwidth allocat ion algorithm in mobile networks with big data of users and networks,

    B. Fan, S. Leng, and K. Yang, “A dynamic bandwidth allocat ion algorithm in mobile networks with big data of users and networks,” IEEE Netw., vol. 30, no. 1, pp. 6-10, Feb. 2016

    work page 2016

  4. [4]

    Mobile edge computing: A survey on architecture and computation offloading,

    P . Mach and Z. Becvar, “Mobile edge computing: A survey on architecture and computation offloading,” IEEE Commun. Surveys Tuts., vol. 19, no. 3, pp. 1628-1656, 3rd Quart., 2017

    work page 2017

  5. [5]

    Toward a theory of in-networ k computation in wireless sensor networks,

    A. Giridhar and P . R. Kumar, “Toward a theory of in-networ k computation in wireless sensor networks,” IEEE Commun. Mag., vol. 44, no. 4, pp. 98-107, Apr. 2006

    work page 2006

  6. [6]

    Join t scheduling of communication and computation resources in multiuser wireless application offloading,

    M. Molina, O. Muoz, A. Pascual-Iserte and J. Vidal, “Join t scheduling of communication and computation resources in multiuser wireless application offloading,” in Proc. IEEE PIMRC , Washington, DC, USA, Sep. 2014, pp. 1093-1098

    work page 2014

  7. [7]

    ECCN: Orchestration of edge-c entric computing and content-centric networking in the 5G radio access network,

    H. Li, K. Ota, and M. Dong, “ECCN: Orchestration of edge-c entric computing and content-centric networking in the 5G radio access network,” IEEE Wireless Commun. , vol. 25, no. 3, pp. 8893, Jun. 2018

    work page 2018

  8. [8]

    Edge computing: Vision and challenges,

    W. Shi, J. Cao, Q. Zhang, Y . Li, and L. Xu, “Edge computing: Vision and challenges,” IEEE Internet Things J. , vol. 3, no. 5, pp. 637-646, Oct. 2016

    work page 2016

  9. [9]

    Collab orative mobile edge computing in 5G networks: New paradigms , scenarios, and challenges,

    T. X. Tran, A. Hajisami, P . Pandey and D. Pompili, “Collab orative mobile edge computing in 5G networks: New paradigms , scenarios, and challenges,” IEEE Commun. Mag. , vol. 55, no. 4, pp. 54-61, Apr. 2017

    work page 2017

  10. [10]

    Mobile-edge computing and the internet of things for consumers: Extending cloud compu ting and services to the edge of the network,

    P . Corcoran and S. K. Datta, “Mobile-edge computing and the internet of things for consumers: Extending cloud compu ting and services to the edge of the network,” IEEE Consum. Electron. Mag. , vol. 5, no. 4, pp. 73-74, Oct. 2016

    work page 2016

  11. [11]

    Distributed O ptimization of Collaborative Regions in Large-Scale Inhomogeneous Fog Computing,

    X. Lyu, C. Ren, W. Ni, H. Tian and R. P . Liu, “Distributed O ptimization of Collaborative Regions in Large-Scale Inhomogeneous Fog Computing,” IEEE J. Sel. Areas Commun. , vol. 36, no. 3, pp. 574-586, Mar. 2018

    work page 2018

  12. [12]

    D. P . Bertsekas, Dynamic Programming and Optimal Control , 3rd ed. Boston, MA, USA: Athena Scientific, 2005

    work page 2005

  13. [13]

    A dynamic offloading al gorithm for mobile computing,

    D. Huang, P . Wang, and D. Niyato, “A dynamic offloading al gorithm for mobile computing,” IEEE Trans. Wireless Commun., vol. 11, no. 6, pp. 1991-1995, Jun. 2012

    work page 1991

  14. [14]

    Energy delay trade-off in cloud offl oading for multi-core mobile devices,

    Z. Jiang and S. Mao, “Energy delay trade-off in cloud offl oading for multi-core mobile devices,” in Proc. IEEE Globecom , San Diego, CA, USA, Dec. 2015, pp. 1-6

    work page 2015

  15. [15]

    Stochasti c Joint Radio and Computational Resource Management for Multi-User Mobile-Edge Computing Systems,

    Y . Mao, J. Zhang, S. H. Song and K. B. Letaief, “Stochasti c Joint Radio and Computational Resource Management for Multi-User Mobile-Edge Computing Systems,” IEEE Trans. Wireless Commun. , vol. 16, no. 9, pp. 5994-6009, Sept. 2017

    work page 2017

  16. [16]

    T hinkAir: Dynamic resource allocation and parallel executi on in the cloud for mobile code offloading,

    S. Kosta, A. Aucinas, P . Hui, R. Mortier, and X. Zhang, “T hinkAir: Dynamic resource allocation and parallel executi on in the cloud for mobile code offloading,” in Proc. IEEE INFOCOM , 2012, pp. 945-953

    work page 2012

  17. [17]

    Joint op timization of radio and computational resources for multic ell mobile edge computing,

    S. Sardellitti, G. Scutari and S. Barbarossa, “Joint op timization of radio and computational resources for multic ell mobile edge computing,” IEEE Trans. Signal Inf. Process. Netw. , vol. 1, no. 2, pp. 89-103, Jun. 2015

    work page 2015

  18. [18]

    To offload or not to of fload: An efficient code partition algorithm for mobile cloud computing,

    Y . Zhang, H. Liu, L. Jiao, and X. Fu, “To offload or not to of fload: An efficient code partition algorithm for mobile cloud computing,” in Proc. CLOUDNET , Paris, France, 2012, pp. 80-86

    work page 2012

  19. [19]

    Delay-optim al computation task scheduling for mobile-edge computing systems,

    J. Liu, Y . Mao, J. Zhang, and K. B. Letaief, “Delay-optim al computation task scheduling for mobile-edge computing systems,” in Proc. IEEE ISIT , Barcelona, Spain, 2016, pp. 1451-1455

    work page 2016

  20. [20]

    Energy-optimal r esource scheduling and computation offloading in small cell networks,

    W. Labidi, M. Sarkiss, and M. Kamoun, “Energy-optimal r esource scheduling and computation offloading in small cell networks,” in Proc. ICT , Sydney, NSW, Australia, 2015, pp. 313-318

    work page 2015

  21. [21]

    Efficient multi-user c omputation offloading for mobile-edge cloud computing,

    X. Chen, L. Jiao, W. Li, and X. Fu, “Efficient multi-user c omputation offloading for mobile-edge cloud computing,” IEEE/ACM Trans. Netw. , vol. 24, no. 5, pp. 2795-2808, Oct. 2016

    work page 2016

  22. [22]

    Optimizat ion of radio and computational resources for energy efficien cy in latency-constrained application offloading,

    O. Mu˜ noz, A. Pascual-Iserte, and J. Vidal, “Optimizat ion of radio and computational resources for energy efficien cy in latency-constrained application offloading,” IEEE Trans. V eh. Technol., vol. 64, no. 10, pp. 4738-4755, Oct. 2015. 36

    work page 2015

  23. [23]

    Delay-aware cross-layer desig n for device-to-device communications in future cellular systems,

    W. Wang and V . K. N. Lau, “Delay-aware cross-layer desig n for device-to-device communications in future cellular systems,” IEEE Commun. Mag. , vol. 52, no. 6, pp. 133-139, Jun. 2014

    work page 2014

  24. [24]

    A surv ey on delay-aware resource control for wireless systems: Large derivation theory, stochastic Lyapunov drift and dis tributed stochastic learning,

    Y . Cui, V . K. N. Lau, R. Wang, H. Huang and S. Zhang, “A surv ey on delay-aware resource control for wireless systems: Large derivation theory, stochastic Lyapunov drift and dis tributed stochastic learning,” IEEE Trans. Inf. Theory , vol. 58, no. 3, pp. 1677-1700, Mar. 2012

    work page 2012

  25. [25]

    E. M. Yeh, Multiaccess and Fading in Communication Networks , Ph.D. dissertation, MIT, Sept. 2001

    work page 2001

  26. [26]

    Stochastic network optimization with app lication to communication and queueing systems,

    M. J. Neely, “Stochastic network optimization with app lication to communication and queueing systems,” Synthesis Lectures on Communication Networks , vol. 3, no. 1, pp. 1-211, May 2010

    work page 2010

  27. [27]

    Queue-aware dynamic clus tering and power allocation for network MIMO systems via distributed stochastic learning,

    Y . Cui, Q. Huang, V . K. N. Lau, “Queue-aware dynamic clus tering and power allocation for network MIMO systems via distributed stochastic learning,” IEEE Trans. Signal Process. , vol. 59, no. 3, pp. 1229-1238, Mar. 2011

    work page 2011

  28. [28]

    Dynamic power control for delay-aware device-to-device communications,

    W. Wang, F. Zhang, and V . Lau, “Dynamic power control for delay-aware device-to-device communications,” IEEE J. Sel. Areas Commun. , vol. 33, no. 1, pp. 14-27, Jan. 2015

    work page 2015

  29. [29]

    En ergy optimal mobile cloud computing under stochastic wireless channel,

    W. Zhang, Y . Wen, K. Guan, D. Kilper, H. Luo, and D. Wu, “En ergy optimal mobile cloud computing under stochastic wireless channel,” IEEE Trans. Wireless Commun. , vol. 12, no. 9, pp. 4569-4581, Sep. 2013

    work page 2013

  30. [30]

    Closed-form delay-optimal po wer control for energy harvesting wireless system with finit e energy storage,

    F. Zhang and V . K. N. Lau, “Closed-form delay-optimal po wer control for energy harvesting wireless system with finit e energy storage,” IEEE Trans. Signal Process. , vol. 62, no. 21, pp. 5706-5715, Nov. 2014

    work page 2014

  31. [31]

    Delay-aware massive random access for machine-type communications via hierarchical stochastic learning,

    Y . Ruan, W. Wang, Z. Zhang, and V . K. N. Lau, “Delay-aware massive random access for machine-type communications via hierarchical stochastic learning,” in Proc. IEEE ICC W orkshop, Paris, France, May 2017, pp. 16

    work page 2017

  32. [32]

    Available: http s://console.developers.google.com/storage/openmobiledata public/

    Open Mobile Data by MobiPerf [Online]. Available: http s://console.developers.google.com/storage/openmobiledata public/

    work page

  33. [33]

    Optima l energy management policies for energy harvesting sensor nodes,

    V . Sharma, U. Mukherji, V . Joseph, and S. Gupta, “Optima l energy management policies for energy harvesting sensor nodes,” IEEE Trans. Wireless Commun. , vol. 9, no. 4, pp. 1326-1336, Apr. 2010

    work page 2010

  34. [34]

    Utility optimal scheduling in en ergy-harvesting networks,

    L. Huang and M. Neely, “Utility optimal scheduling in en ergy-harvesting networks,” IEEE/ACM Trans. Netw., vol. 21, no. 4, pp. 1117-1130, Aug. 2013

    work page 2013

  35. [35]

    Scheduling in a queueing system with asynchronously varying service rates,

    M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijay akumar, and P . Whiting, “Scheduling in a queueing system with asynchronously varying service rates,” Probability in the Engineering and Informational Sciences , vol. 18, no. 2, pp. 191-217, 2004

    work page 2004

  36. [36]

    A. D. Polyanin, V . F. Zaitsev, and A. Moussiaux, Handbook of First Order Partial Differential Equations, 2n d ed. Taylor & Francis, 2002

    work page 2002