PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Subcarrier and CPU Time Allocation for Mobile Edge Computing

Yinghao Yu, Jun Zhang, Khaled Ben Letaief

arXiv:1608.06128v2cs.IT

TL;DR

Mobile edge computing must allocate scarce radio and cloudlet compute resources together rather than separately. The paper proposes coordinated OFDMA subcarrier and non-preemptive CPU-time scheduling, and simulations show substantially better energy saving and offloading support than per-resource allocation.

  • Problem

    Cloudlets have constrained radio and compute resources, while separate resource allocation can waste one resource when the other is congested.

  • Method

    The paper jointly schedules OFDMA subcarriers and non-preemptive cloudlet CPU time slots, using coordinated resource allocation for offloaded tasks.

  • Results

    Per-resource allocation achieves only half the energy saving of joint allocation, while CPU constraints reduce the number of offloaded users by nearly 50%.

  • Takeaways & Limitations

    Joint scheduling is more critical when computation offloading can provide more prominent energy savings.

Abstract

from arXiv · show

In mobile edge computing systems, mobile devices can offload compute-intensive tasks to a nearby cloudlet,so as to save energy and extend battery life. Unlike a fully-fledged cloud, a cloudlet is a small-scale datacenter deployed at a wireless access point, and thus is highly constrained by both radio and compute resources. We show in this paper that separately optimizing the allocation of either compute or radio resource, as most existing works did, is highly suboptimal: the congestion of compute resource leads to the waste of radio resource, and vice versa. To address this problem, we propose a joint scheduling algorithm that allocates both radio and compute resources coordinately. Specifically, we consider a cloudlet in an Orthogonal Frequency-Division Multiplexing Access (OFDMA) system with multiple mobile devices, where we study subcarrier allocation for task offloading and CPU time allocation for task execution in the cloudlet. Simulation results show that the proposed algorithm significantly outperforms per-resource optimization, accommodating more offloading requests while achieving salient energy saving.

I. INTRODUCTION

Mobile edge computing lets devices offload compute-intensive tasks to cloudlets, but cloudlets constrain both radio and compute resources. The paper therefore studies coordinated allocation in an OFDMA cloudlet system.

  • Cloudlets help extend smartphone battery life by trading heavy local CPU cycles for lightweight communication.
  • Offloading performance depends jointly on radio resources, which determine transmission speed and communication energy, and compute resources, which determine cloudlet execution time.
  • Many existing works assumed effectively unlimited cloudlet compute capacity, reducing offloading scheduling to radio-resource allocation.
  • The proposed approach jointly schedules OFDMA subcarriers and non-preemptive cloudlet CPU time slots with varied lengths.
  • Joint scheduling addresses resource congestion by coordinating radio and compute allocation rather than combining separate per-resource policies.

B. Energy Consumption

The paper models local execution and remote offloading energy under deadline constraints. It derives local CPU settings and transmission-power optimization for energy-efficient task execution.

  • 1) Local execution: Local execution sets each device’s CPU frequency so the job deadline is met exactly, because energy per CPU cycle increases with frequency.
  • 1) Local execution: Local execution is assumed feasible because each device’s maximum CPU frequency exceeds its deadline-meeting frequency.
  • 2) Remote execution: Offloading energy accounts for transmitting input data to the cloudlet while ignoring result-reception energy because output data are much smaller.
  • 2) Remote execution: For an allocated subcarrier group, bisection search finds the transmit power minimizing transmission energy while meeting the task deadline.

C. Time for Offloading

Remote execution combines transmission, cloudlet queuing, and computation time. The model uses water-filling for power allocation and non-preemptive CPU scheduling for cloudlet execution.

  • 1) Transmission: The power allocation matrix is obtained by water-filling, after which each user’s aggregated data rate is determined from its assigned subcarriers and powers.
  • 2) Queuing and remote execution: Non-preemptive CPU allocation assigns one user a time slot until its job completes.
  • 2) Queuing and remote execution: The cloudlet executes jobs according to an ordered sequence, with each job’s queuing time determined by earlier scheduled jobs.

D. Problem Formulation

The paper formulates joint radio–compute resource allocation as an energy-minimization problem and develops subcarrier-allocation strategies under unlimited cloudlet computation. The formulation is difficult because it is a mixed-integer nonlinear program with non-convex components.

  • D. Problem Formulation: The total-energy objective combines local execution and offloading energy under subcarrier, CPU, power, and deadline constraints.Constraint (9a) assigns each subcarrier exclusively, (9b) enforces non-preemptive execution, (9c)–(9d) determine power-related quantities, and (9e)–(9g) handle energy and deadlines.
  • D. Problem Formulation: The resource-allocation problem is a mixed-integer nonlinear program that is generally NP-hard and difficult because of combinatorial variables and non-convex functions.The paper therefore seeks efficient algorithms with near-optimal performance.
  • III. CLOUDLET WITH UNLIMITED COMPUTATION CAPABILITY: Under unlimited cloudlet computation, the paper develops radio-allocation methods that provide a performance upper bound for limited-computation settings.This special case assumes cloudlet computation capability far exceeds user offloading demands.
  • III. CLOUDLET WITH UNLIMITED COMPUTATION CAPABILITY: The remaining unlimited-computation subproblem is to allocate subcarriers after transmit power and power allocation are obtained by bisection search and water-filling.Closed-form comparisons among subcarrier allocations are difficult because these procedures determine the resulting outcomes.
  • III. CLOUDLET WITH UNLIMITED COMPUTATION CAPABILITY: Users executing locally can waste assigned subcarriers, so the algorithm allocates minimum subcarrier groups that guarantee beneficial offloading.Each user’s minimum group is evaluated for energy consumption, and users with the greatest energy savings receive priority.
  • III. CLOUDLET WITH UNLIMITED COMPUTATION CAPABILITY: Algorithm 1 iteratively processes users and available subcarriers, finds each user’s minimum group, and removes the selected group and user from further consideration.The supplied algorithm passages show the loop and updates for the selected user, subcarrier set, and user set.
  • III. CLOUDLET WITH UNLIMITED COMPUTATION CAPABILITY: Algorithm 1 records the selected user’s allocation and marks that user as served before continuing until users or subcarriers are exhausted.The supplied implementation fragments include the allocation and user-removal updates.

IV. CLOUDLET WITH LIMITED COMPUTATION CAPABILITY

When cloudlet computation is limited, queuing and execution delays become non-negligible and can violate task deadlines. The paper therefore schedules compute resources alongside radio resources and uses per-resource allocation as a baseline for joint scheduling.

  • IV. CLOUDLET WITH LIMITED COMPUTATION CAPABILITY: Unlimited-computation assumptions simplify offloading, but practical cloudlets have limited computation capability.Cloudlets are small-scale deployments, so their computation capacity may not be far beyond user demand.
  • IV. CLOUDLET WITH LIMITED COMPUTATION CAPABILITY: With limited computation, cloudlet queuing delay and execution time are non-negligible.These delays must be included when evaluating offloading decisions.
  • IV. CLOUDLET WITH LIMITED COMPUTATION CAPABILITY: Cloudlet congestion can violate deadlines, so compute resources must be scheduled to maximize offloading gain.The section first introduces per-resource allocation as a baseline before joint scheduling.

A. Per-Resource Allocation

The per-resource baseline allocates subcarriers first and schedules non-preemptive CPU execution afterward. Its dynamic program optimizes execution order and energy saving while checking whether queued jobs meet their deadlines.

  • A. Per-Resource Allocation: The baseline assigns subcarriers first and schedules CPU time slots in a second stage, while incorporating cloudlet execution time into deadline checks.Subcarrier allocation follows Algorithm 1 with an additional deadline constraint.
  • A. Per-Resource Allocation: Non-preemptive CPU scheduling determines job execution order, queuing time, deadline satisfaction, and ultimately offloading acceptance.A job is accepted when its deadline can be met after cloudlet execution.
  • A. Per-Resource Allocation: The CPU scheduling problem is NP-hard, so the paper uses dynamic programming with pseudo-polynomial complexity.The dynamic program decomposes the problem into states indexed by the number of considered users.
  • A. Per-Resource Allocation: For each user subset, the dynamic program groups possible execution sequences by their last executed job.Previously computed savings and execution times are reused to avoid duplicated iterations.
  • A. Per-Resource Allocation: When user i is considered last, the algorithm combines the prior subset’s savings and time with transmission readiness before checking its deadline.The ready time is the longer of the prior queuing time and user i’s transmission time.
  • A. Per-Resource Allocation: Algorithm 2 implements the dynamic-programming CPU scheduling procedure for the per-resource baseline.The algorithm evaluates temporary savings and times before selecting the maximizing candidate.
  • A. Per-Resource Allocation: The algorithm selects the candidate ordering with the greatest energy saving and stores its corresponding execution time.The final state over all M users gives the optimal solution to the original CPU scheduling problem.

B. Joint Allocation

Separate allocation can waste subcarriers when CPU congestion makes assigned users miss deadlines. Joint allocation instead selects users using both minimum beneficial subcarrier groups and required CPU time, with queuing known before scheduling.

  • B. Joint Allocation: Separate allocation may assign subcarriers to users who ultimately execute locally because CPU queuing can cause deadline violations.The radio stage lacks the queuing information needed to determine whether offloading will succeed.
  • B. Joint Allocation: Joint allocation seeks the least radio and compute resources that ensure successful offloading and assigns them to users with the most efficient energy savings.This coordinates resource sufficiency with user selection.
  • B. Joint Allocation: For each user, the joint algorithm finds a minimum beneficial subcarrier group and calculates the CPU time required for remote processing.Users saving the most energy per CPU cycle receive the corresponding subcarriers and CPU time slots.
  • B. Joint Allocation: Joint allocation optimizes radio and compute utilization by identifying minimum subcarrier groups and energy saving per CPU cycle.Knowing queuing time before scheduling helps avoid resource waste caused by congestion.
  • B. Joint Allocation: Algorithm 3 summarizes the joint-allocation procedure over users and available subcarriers.The supplied algorithm fragments show its iterative processing and minimum-group search.
  • B. Joint Allocation: The joint procedure uses transmission and execution timing when determining whether an allocation can satisfy a user’s requirements.The supplied fragments include updates involving the selected user’s timing quantities.

V. PERFORMANCE EVALUATIONS

The evaluation examines energy savings from offloading, the benefit of joint versus per-resource allocation, algorithm quality against optimal allocation, and the effects of limited cloudlet computation.

  • The evaluation asks how much energy offloading saves compared with local execution.
  • It compares joint allocation with per-resource allocation.
  • It assesses proposed algorithms against optimal allocation and studies how limited computation capability affects system performance.

A. System Setting

The simulations model users distributed around a cloudlet, use a specified path-loss model, and set channel, radio, workload, deadline, and energy parameters.

  • Users are randomly located in a circle centered at the cloudlet.
  • Large-scale channel fading is modeled with PL = 20 log(dkm) + 20 log(f kHz) + 32.45 dB.
  • The simulations use Rayleigh small-scale fading and subcarriers spanning 1850–1960 kHz with 18.75 kHz bandwidth each.
  • Users have 50 mW circuit power, 1 W maximum transmission power, 900–1100-bit inputs, and 50–150 ms deadlines.

B. Simulations

The simulation section reports exhaustive-search baselines and introduces figures examining energy consumption and offloaded-user counts as the user population changes.

  • Optimal energy savings are obtained by exhaustively searching the subcarrier allocation matrix.
  • With limited CPU capability, exhaustive subcarrier search is combined with optimal CPU scheduling.
  • Figure 2 plots energy consumption against total users for N = 4, r = 0.2 km, and fc = 600 MHz.
  • Figure 3 plots the number of offloaded users against total users under N = 4, r = 0.2 km, and fc = 600 MHz.

1) Number of users:

The experiments show that joint allocation retains near-optimal energy performance, while resource constraints, coverage radius, and CPU frequency materially affect offloading outcomes.

  • 1) Number of users:: Per-resource allocation achieves only half the energy saving of joint allocation, despite near-optimal subcarrier and optimal CPU time allocation.
  • 1) Number of users:: CPU capability constraints reduce the number of offloaded users by nearly 50%.
  • 2) Coverage of the cloudlet:: As cloudlet radius increases, offloading gain shrinks because users are farther from the cloudlet on average and fewer can be supported.
  • 2) Coverage of the cloudlet:: Satisfactory offloading services require cloudlets to be close to users and densely deployed.
  • 3) CPU frequency of the cloudlet:: Energy saving saturates around 800 MHz for a 3-user system but keeps increasing for 7 users because of richer user-diversity.
  • 3) CPU frequency of the cloudlet:: Joint allocation gains greater advantage over per-resource allocation as cloudlet CPU frequency increases and approaches the optimal policy without CPU constraint beyond a threshold.
  • VI. CONCLUSIONS: The proposed joint scheduling algorithms are efficient and near-optimal for mobile-device energy saving.
Loading 1608.06128v2…