Source-linked AI summary
Energy-Efficient Resource Allocation for Mobile-Edge Computation Offloading (Extended Version)
Changsheng You, Kaibin Huang, Hyukjin Chae, Byoung-Hoon Kim
TL;DR
Mobile devices have limited battery life and computing capacity, motivating computation offloading to nearby edge clouds. The paper develops priority-based TDMA allocation and a low-complexity finite-capacity algorithm, with a threshold policy and close-to-optimal performance reported for the finite-capacity search.
Problem
Mobile devices’ limited battery lives and computation capacities motivate energy-efficient offloading to nearby edge clouds.
Source: §I · p. 1Method
The paper derives a TDMA offloading-priority threshold policy and a lower-complexity algorithm for finite cloud capacity.
Source: B. Contribution and Organization · p. 2Results
The finite-capacity TDMA algorithm reduces threshold computation to a one-dimensional search and is shown by simulation to have close-to-optimal performance.
Source: B. Contribution and Organization · p. 2Takeaways & Limitations
TDMA allocation can use user priorities based on channel gains and local computing energy to select complete or minimum offloading.
Source: B. Contribution and Organization · p. 2
Abstract
from arXiv · showhide
Mobile-edge computation offloading (MECO) offloads intensive mobile computation to clouds located at the edges of cellular networks. Thereby, MECO is envisioned as a promising technique for prolonging the battery lives and enhancing the computation capacities of mobiles. In this paper, we study resource allocation for a multiuser MECO system based on time-division multiple access (TDMA) and orthogonal frequency-division multiple access (OFDMA). First, for the TDMA MECO system with infinite or finite computation capacity, the optimal resource allocation is formulated as a convex optimization problem for minimizing the weighted sum mobile energy consumption under the constraint on computation latency. The optimal policy is proved to have a threshold-based structure with respect to a derived offloading priority function, which yields priorities for users according to their channel gains and local computing energy consumption. As a result, users with priorities above and below a given threshold perform complete and minimum offloading, respectively. Moreover, for the cloud with finite capacity, a sub-optimal resource-allocation algorithm is proposed to reduce the computation complexity for computing the threshold. Next, we consider the OFDMA MECO system, for which the optimal resource allocation is formulated as a non-convex mixed-integer problem. To solve this challenging problem and characterize its policy structure, a sub-optimal low-complexity algorithm is proposed by transforming the OFDMA problem to its TDMA counterpart. The corresponding resource allocation is derived by defining an average offloading priority function and shown to have close-to-optimal performance by simulation.
I. INTRODUCTION
The paper studies energy-efficient resource allocation for multiuser mobile-edge computation offloading, where mobiles offload computation to nearby edge clouds. It develops priority-based allocation for TDMA and a low-complexity, close-to-optimal approach for OFDMA.
A. Prior Work
- Earlier MECO resource-allocation work is described as yielding little insight into optimal policy structure; this paper derives a threshold policy for TDMA and uses that insight for OFDMA.The paper distinguishes its joint optimization of computation and radio resources from traditional multiple-access allocation focused only on radio resources.Source: A. Prior Work · pp. 1–2
B. Contribution and Organization
- The optimal TDMA policy uses an offloading-priority threshold to assign complete or minimum offloading, while finite-cloud capacity motivates a lower-complexity threshold-search algorithm.For OFDMA, the paper proposes a sub-optimal algorithm based on the TDMA policy structure and reports close-to-optimal performance by simulation.Source: B. Contribution and Organization · p. 2
II. SYSTEM MODEL
- The system has multiple mobiles served by one base station connected to an edge cloud, with centralized allocation minimizing weighted mobile energy under shared latency requirements.The base station is assumed to know users’ channel gains, local computing energy per bit, and input-data sizes.Source: §II · p. 2, B. Contribution and Organization · p. 2
A. Multiple-Access Model
- TDMA allocates a time slot for offloading or local computing, while OFDMA divides bandwidth into orthogonal sub-channels assigned to at most one user each.Cloud computation and downloading of results are assumed to take negligible time relative to the first TDMA phase.Source: A. Multiple-Access Model · p. 2
B. Local-Computing Model
- Each mobile splits its input between offloading and local computing, with local energy determined by the remaining data and computing energy per bit.The local-computing latency constraint imposes a minimum offloaded data size when local CPU capacity is insufficient.Source: B. Local-Computing Model · p. 3
C. Computation-Offloading Model
- In TDMA, a mobile’s offloading energy depends on its allocated transmission time and data rate, with transmission rate fixed by offloaded data divided by allocated time.The paper also formulates OFDMA offloading using binary sub-channel assignment indicators and per-sub-channel transmission rates.Source: C. Computation-Offloading Model · p. 3
D. Cloud-Computing Model
The paper models finite edge-cloud capacity through a computation-load or computation-time constraint and formulates TDMA allocation to minimize weighted mobile energy. The TDMA problem is convex, and a two-stage solution supports the threshold-policy analysis.
D. Cloud-Computing Model
- Finite cloud capacity is represented by either a per-slot computation-load limit or a cloud-computation-time constraint, considered separately.The paper states that these constraints can be treated as equivalent, but does not model both simultaneously.Source: D. Cloud-Computing Model · p. 3
III. MULTIUSER MECO FOR TDMA: PROBLEM FORMULATION
- The TDMA allocation objective is to minimize weighted total mobile energy under time-sharing, cloud-capacity, and computation-latency constraints.The positive user weights account for fairness among mobiles.Source: §III · p. 4
- The TDMA resource-allocation problem is convex, and its feasibility depends on satisfying the cloud-capacity constraint.The time-sharing constraint can always be met and affects mobile energy consumption.Source: §III · p. 4
- A two-stage solution first relaxes the cloud-capacity constraint, then incrementally solves the original problem if the relaxed solution violates capacity.This approach exposes the threshold-based policy and facilitates a low-complexity close-to-optimal algorithm.Source: §III · p. 4
IV. MULTIUSER MECO FOR TDMA: INFINITE CLOUD CAPACITY
For infinite cloud capacity, the paper derives a threshold-based optimal TDMA allocation policy using a priority function for each mobile. The priority reflects user characteristics and predicts how much data is offloaded.
IV. MULTIUSER MECO FOR TDMA: INFINITE CLOUD CAPACITY
- The optimal TDMA allocation is characterized through a priority-based threshold policy derived by solving the resource-allocation problem.The derivation uses the Lagrange method and KKT conditions.Source: §IV · p. 4
A. Offloading Priority Function
- A mobile’s offloading priority depends on fairness, local-computing, and channel variables, and offloaded data increases with priority.The priority function is defined through an equation whose root determines the mobile’s priority value.Source: A. Offloading Priority Function · pp. 4–5
- Priority increases with fairness weight, computing cycles per bit, local energy per cycle, and channel gain; its scaling with local computing energy per bit is faster than with channel gain.The paper reports approximate scaling of (CP) ln(CP) for computing energy per bit and ln h for channel gain.Source: A. Offloading Priority Function · p. 5
B. Optimal Resource-Allocation Policy
For infinite-capacity TDMA MECO, the optimal policy uses an offloading-priority threshold to choose complete or minimum offloading. The section also characterizes when offloading is worthwhile and how radio and cloud resources constrain the allocation.
B. Optimal Resource-Allocation Policy
- Users with priority above λ* completely offload, while those below it offload only the minimum amount required by the latency constraint.The policy is threshold-based when offloading saves energy; the exact equality case is described as rare in practice.Source: B. Optimal Resource-Allocation Policy · p. 5
- Minimum offloading serves both users for whom offloading cannot save energy and energy-efficient users whose priorities fall below λ* because radio resources are limited.The first group has υk ≤ 1 and ϕk = 0; the second has υk > 1 and ϕk < λ*.Source: B. Optimal Resource-Allocation Policy · p. 5
- Offloading may be unnecessary unless local computing violates the latency constraint or a user has sufficient channel gain or local-computing energy to save energy by offloading.The paper contrasts this with conventional TDMA, where continuous transmission by at least one mobile is advantageous under minimum sum energy.Source: B. Optimal Resource-Allocation Policy · p. 5
- The offloading rate depends on channel gain and fairness factor, while local-computing parameters affect the offloading decision.A larger channel gain increases the offloading rate because it supports higher transmission rates or lower transmission power.Source: B. Optimal Resource-Allocation Policy · p. 5
- The optimal threshold can be found by a one-dimensional search, reducing computation complexity relative to iterative optimization of offloaded data and slot allocations.The algorithm uses bisection to update the threshold against the time-sharing constraint.Source: B. Optimal Resource-Allocation Policy · p. 5
- With a short slot, only the highest-priority user may offload; when the slot exceeds a threshold, all offloading-desired users can completely offload.The short-slot winner may consume all available resource if its data load is excessive.Source: B. Optimal Resource-Allocation Policy · p. 6
C. Special Cases
The special cases yield greedy allocation rules under uniform channel or computing conditions. With finite cloud capacity, the threshold policy is retained using an effective priority that reflects the cloud constraint.
C. Special Cases
- For the special cases considered, the optimal resource-allocation policies are derived under equal fairness factors.Source: C. Special Cases · p. 6
1) Uniform Channels and Local Computing:
- When channels and local-computing parameters are identical, mobiles have uniform priorities and may offload arbitrary data sizes subject to the stated total offloaded-data constraint.Source: 1) Uniform Channels and Local Computing · p. 6
2) Uniform Channels:
- With uniform channels, the optimal policy greedily selects users in descending order of energy consumption per bit for complete offloading until the slot is used.The ordering follows from the stated uniform-channel case and its optimal policy.Source: 2) Uniform Channels · p. 6
3) Uniform Local Computing:
- With uniform local-computing products CkPk, the greedy policy selects users for complete offloading in descending order of channel gain.Source: 3) Uniform Local Computing · p. 6
V. MULTIUSER MECO FOR TDMA: FINITE CLOUD CAPACITY
- The finite-capacity-cloud analysis extends the TDMA policy to finite computation capacity and also considers non-negligible cloud computing time.Source: §V · p. 6
A. Optimal Resource-Allocation Policy
- For finite cloud capacity, the optimal policy retains the threshold structure but uses an effective priority modified by the cloud-capacity multiplier.Smaller cloud capacity increases that multiplier and can change the priority ordering, reflecting a tradeoff between energy savings and computation burden.Source: A. Optimal Resource-Allocation Policy · pp. 6–7
B. Sub-Optimal Resource-Allocation Policy
The proposed sub-optimal algorithm decouples computation and radio allocation to avoid the optimal policy’s two-dimensional multiplier search. Its one-dimensional search has low complexity and simulation shows close-to-optimal performance.
B. Sub-Optimal Resource-Allocation Policy
- The algorithm decouples computation and radio allocation, first assigning computation by approximate offloading priority and then optimizing slot fractions.It allocates cloud computation in descending priority order until capacity is occupied.Source: B. Sub-Optimal Resource-Allocation… · p. 7
- The low-complexity approach reduces the two-dimensional search over Lagrange multipliers to a one-dimensional search for λ*.Source: B. Sub-Optimal Resource-Allocation… · p. 7
- The sub-optimal algorithm has complexity O(K log(1/ε)) and is reported to have close-to-optimal performance in simulation.Each iteration has resource-allocation complexity O(K), with one-dimensional search iteration complexity O(log(1/ε)).Source: B. Sub-Optimal Resource-Allocation… · p. 7
C. Extension: MECO with Non-Negligible Computing Time
With non-negligible cloud computing time, offloaded data affects energy, transmission duration, and computation time, complicating resource allocation. The optimal policy retains a threshold structure based on a modified offloading priority.
C. Extension: MECO with Non-Negligible Computing Time
- Offloaded data affects mobile energy, transmission duration, and cloud computing time, making the optimization more complicated.The cloud is assumed to proportionally allocate CPU cycles so all users experience the same computing time.Source: C. Extension: MECO with Non-Negligible… · pp. 7–8
- The stated feasibility condition is strict: if the cloud-capacity bound equals T, the resulting zero offloading time cannot enable computation offloading.The proposed policy can be computed with a one-dimensional search for bλ∗.Source: C. Extension: MECO with Non-Negligible… · p. 8
- The priority function is directly affected by finite cloud capacity through bυk, unlike the earlier priority function determined by a Lagrange multiplier.Its properties include bυ > 1 if and only if υ > 1, so the condition for energy-saving offloading is the same as for an infinite-capacity cloud.Source: C. Extension: MECO with Non-Negligible… · p. 8
- The optimal allocation retains the structure of the earlier threshold policy, expressed through a priority function for the finite-capacity cloud with non-negligible computing time.The latency constraint accounts for both transmission and cloud computation time.Source: C. Extension: MECO with Non-Negligible… · pp. 7–8
VI. MULTIUSER MECO FOR OFDMA
For OFDMA MECO, the paper develops a low-complexity sub-optimal algorithm for a difficult mixed-integer allocation problem. It transforms the problem to a TDMA counterpart using average channel gains and an average offloading priority, with close-to-optimal performance shown in simulation.
VI. MULTIUSER MECO FOR OFDMA
- The proposed low-complexity sub-optimal OFDMA algorithm transforms the problem to a TDMA counterpart using average channel gains and an average offloading priority, and achieves close-to-optimal performance in simulation.The stated scope is an infinite-capacity cloud; the paper notes the approach can be extended to finite capacity.Source: §VI · p. 8
A. Multiuser MECO for OFDMA: Infinite Cloud Capacity
- OFDMA allocation jointly optimizes continuous offloaded-data variables and integer sub-channel assignments, making the problem mixed-integer and difficult to solve.Relaxation-and-rounding and dual decomposition involve extensive iterations and provide little insight into policy structure.Source: A. Multiuser MECO for OFDMA: Infinite… · p. 8
- The algorithm decomposes allocation into initial resource and data allocation using average gains and priority, priority-ordered integer sub-channel assignment, then data-allocation adjustment.For offloading-required users, the procedure first reserves a sub-channel for each user.Source: A. Multiuser MECO for OFDMA: Infinite… · p. 9
1) Sub-Channel Reservation for Offloading-Required Users:
The OFDMA procedure reserves channels for users that require offloading, derives initial allocations through a TDMA counterpart, assigns integer channels by priority, and adjusts offloaded data to meet latency constraints.
1) Sub-Channel Reservation for Offloading-Required Users:
- The reservation phase assigns one high-priority available sub-channel to each offloading-required user, ensuring each receives a channel to satisfy latency constraints.This phase performs at most K priority-maximization iterations and has complexity O(K).Source: 1) Sub-Channel Reservation for… · p. 9
2) Initial Resource and Offloaded Data Allocation:
- The initial-allocation phase averages each user's unassigned sub-channel gains and transforms the OFDMA problem into its TDMA counterpart to derive total channel and offloaded-data allocations.An average offloading priority function supports the allocation, obtained using bisection search.Source: 2) Initial Resource and Offloaded Data… · p. 9
3) Integer Sub-Channel Assignment:
- Integer channel assignment first allocates each user the lower-rounded channel count, then gives remaining channels to the users with the highest offloading priority.This priority-based approach is presented as a lower-complexity alternative to the Hungarian Algorithm.Source: 3) Integer Sub-Channel Assignment · p. 10
4) Adjustment of Offloaded Data Allocation:
- The adjustment phase allocates each user's offloaded data across assigned channels to minimize individual energy, using a one-dimensional search for ξk.The phase complexity is O(KN log (1/ε)); the full sequential algorithm has complexity up to O(K + N + KN log (1/ε)).Source: 4) Adjustment of Offloaded Data… · p. 10
B. Multiuser MECO for OFDMA: Finite Cloud Capacity
The paper extends priority-based resource allocation to finite-capacity OFDMA and evaluates proposed TDMA and OFDMA policies against baselines. Simulations report close-to-optimal performance, energy savings, and settings where additional cloud capacity or sub-channels have little effect.
B. Multiuser MECO for OFDMA: Finite Cloud Capacity
- For finite-capacity OFDMA, the low-complexity algorithm is obtained by modifying the infinite-capacity algorithm; finite cloud capacity is handled by adapting Phase 2.The other phases are extended from the OFDMA procedure for infinite capacity.Source: B. Multiuser MECO for OFDMA: Finite… · p. 10
B. Multiuser MECO for OFDMA
- The OFDMA policy is close to relaxation-and-rounding, especially at 256 sub-channels, while using much less computation and saving energy over greedy allocation.The proposed method allocates more sub-channels to heavily loaded users; energy consumption changes little above about 64 sub-channels.Source: Figure 5 · p. 11, B. Multiuser MECO for OFDMA · p. 12
A. Multiuser MECO for TDMA
- For TDMA, total mobile energy becomes invariant once cloud capacity exceeds a threshold of about 6×10^9 cycles.The sub-optimal policy approaches the optimal policy as cloud capacity increases and saves energy over equal allocation.Source: A. Multiuser MECO for TDMA · p. 11
- The TDMA sub-optimal policy has close-to-optimal performance and consumes less than half the energy of equal allocation, especially for shorter slots.The cited comparison is for total mobile energy consumption versus time-slot duration.Source: A. Multiuser MECO for TDMA · p. 11, Figure 4 · p. 11
- For TDMA, the proposed policy’s total energy grows more slowly with user count than equal allocation and remains close to optimal.The comparison fixes cloud computation capacity at F = 6 × 10^9 cycles per slot.Source: A. Multiuser MECO for TDMA · p. 11, Figure 4 · p. 11
B. Multiuser MECO for OFDMA
- With 128 sub-channels, energy consumption rises almost linearly with user count; the proposed policy grows more slowly than greedy and approaches relaxation-and-rounding.The figure plots total mobile energy consumption against user count.Source: Figure 5 · p. 11, B. Multiuser MECO for OFDMA · p. 12
VIII. CONCLUSION
- The conclusion describes a TDMA threshold policy based on offloading priority, with complete offloading above the threshold and minimum offloading below it.For OFDMA, the paper transforms the mixed-integer problem to its TDMA counterpart and reports close-to-optimal simulation performance.Source: §VIII · p. 12
APPENDIX
The appendix establishes convexity, derives a general equation solution used in the priority analysis, and supports monotonicity and threshold-policy claims.
A. Proof of Lemma 1
- The TDMA objective is convex because its component functions and their perspective functions are convex, and the constraints are linear.The proof combines the cases where the time allocation is zero and positive.Source: A. Proof of Lemma 1 · p. 12
B. Proof of Lemma 2
- The proof of Lemma 2 derives the priority expression by solving a general equation and substituting the system-specific parameters.The passage links the substitution to v_k ≥ 1 and the expression in equation (7).Source: B. Proof of Lemma 2 · p. 12
C. Proof of Lemma 3
- The offloading priority is monotone increasing in fairness factor, local computing energy, and local computing energy per cycle.The proof states the relationships for β, C, and P.Source: C. Proof of Lemma 3 · p. 12
D. Proof of Theorem 1
- Theorem 1’s proof uses lemmas and threshold cases to relate user offloading decisions to the priority threshold and time-sharing constraint.It distinguishes cases including ϕ_k < λ* and ϕ_k = λ* and notes that time-sharing is active when remaining time can reduce transmission energy.Source: D. Proof of Theorem 1 · pp. 12–13
E. Proof of Lemma 6
The proofs solve a general logarithmic equation using the Lambert function, then use its monotonicity to establish a parameter inequality.
E. Proof of Lemma 6
- The proof solves x ln x + px = q using the Lambert function, then rewrites the equation with z_k and obtains the solution used in Lemma 6.The passages connect the transformed solution to the desired result but do not fully specify every intermediate expression.Source: E. Proof of Lemma 6 · p. 13
F. Proof of Lemma 7
- For Lemma 7, the proof reduces the claim to b ≥ a when bυ > 1, then invokes the Lambert function’s monotone increase.The monotonicity makes the preceding equivalence sufficient for the result.Source: F. Proof of Lemma 7 · p. 13