PaperlayerView exact revision on arXiv

Source-linked AI summary

Computation Rate Maximization for Wireless Powered Mobile-Edge Computing with Binary Computation Offloading

Suzhi Bi, Ying-Jun Angela Zhang

arXiv:1708.08810v4cs.DCcs.IT

TL;DR

The paper addresses weighted sum computation-rate maximization in wireless powered MEC when tasks must be executed wholly locally or remotely, making mode selection combinatorial and coupled with transmission-time allocation. It proposes decoupled coordinate-descent and jointly optimized ADMM methods, with simulations showing near-optimal performance under varied network setups. The study assumes an MEC server with unlimited computing capacity.

  • Problem

    Binary offloading design for multi-user wireless powered MEC remains insufficiently studied because mode selection is combinatorial and coupled with time allocation.

  • Method

    The paper proposes a decoupled coordinate-descent method and an ADMM-based method that jointly optimize computing modes and transmission time allocation.

  • Results

    Both proposed CD-based and ADMM-based methods achieve near-optimal computation-rate performance under different network setups.

  • Takeaways & Limitations

    The methods provide efficient solution approaches for difficult combinatorial mode selection in multi-user wireless powered MEC.

  • Takeaways & Limitations

    The analysis assumes that the MEC server has unlimited computing capacity.

Abstract

from arXiv · show

In this paper, we consider a multi-user mobile edge computing (MEC) network powered by wireless power transfer (WPT), where each energy-harvesting WD follows a binary computation offloading policy, i.e., data set of a task has to be executed as a whole either locally or remotely at the MEC server via task offloading. In particular, we are interested in maximizing the (weighted) sum computation rate of all the WDs in the network by jointly optimizing the individual computing mode selection (i.e., local computing or offloading) and the system transmission time allocation (on WPT and task offloading). The major difficulty lies in the combinatorial nature of multi-user computing mode selection and its strong coupling with transmission time allocation. To tackle this problem, we first consider a decoupled optimization, where we assume that the mode selection is given and propose a simple bi-section search algorithm to obtain the conditional optimal time allocation. On top of that, a coordinate descent method is devised to optimize the mode selection. The method is simple in implementation but may suffer from high computational complexity in a large-size network. To address this problem, we further propose a joint optimization method based on the ADMM (alternating direction method of multipliers) decomposition technique, which enjoys much slower increase of computational complexity as the networks size increases. Extensive simulations show that both the proposed methods can efficiently achieve near-optimal performance under various network setups, and significantly outperform the other representative benchmark methods considered.

I. INTRODUCTION

The paper studies weighted sum computation-rate maximization in wireless powered MEC with binary offloading, jointly selecting local or remote execution and allocating WPT and offloading time. It develops decoupled and ADMM-based joint optimization methods to address the resulting combinatorial complexity.

  • Problem setting: Binary offloading executes each task wholly either locally at the wireless device or remotely at the MEC server, unlike partial offloading.Binary offloading is easier to implement and suits simple, non-partitionable tasks.
  • Motivation: Wireless powered MEC combines WPT and edge computing to address IoT devices’ limited energy and computing capability.WPT supplies energy to wireless devices, while MEC offloads intensive computations to nearby edge servers.
  • Challenges: The optimization is difficult because multi-user mode selection is combinatorial and strongly coupled with WPT and offloading time allocation.Prior wireless powered MEC studies considered partial offloading, leaving optimal binary-offloading design insufficiently studied.
  • Problem formulation: The paper maximizes the weighted sum computation rate by jointly optimizing each device’s computing mode and system transmission time allocation.The computation rate measures processed bits per second and directly reflects overall system computing capability.
  • Proposed methods: The decoupled method fixes mode selection, optimizes conditional time allocation, and then uses coordinate descent to improve the modes.The method is simple to implement but its complexity can grow like O(N^3) with network size N.
  • Proposed methods: The ADMM-based method jointly optimizes mode selection and time allocation, with computational complexity increasing linearly at O(N).Simulations report near-optimal performance under different network setups and significant improvement over representative benchmarks.

II. SYSTEM MODEL

The system is a wireless-powered MEC network in which an AP transfers energy to multiple WDs, which then compute locally or offload tasks to an AP-integrated MEC server. Binary offloading and TDD separate energy harvesting from communication.

  • The network contains an AP with an integrated MEC server and multiple single-antenna WDs equipped with energy-harvesting circuits and rechargeable batteries.
  • WPT and communication share a frequency band, so each WD uses TDD to prevent simultaneous energy harvesting and communication interference.
  • Channel gains are reciprocal and static within each frame but may vary between frames; the algorithms can also extend to unequal uplink and downlink channels.
  • Each WD performs a task either locally on its constrained processor or remotely after offloading data to the MEC server.
  • The binary rule assigns mode 0 to local computing and mode 1 to whole-task offloading in each time frame.

B. Computation Model

The computation model divides each frame into WPT and computation or offloading operations, with local WDs computing throughout the frame and offloading WDs transmitting sequentially after harvesting energy.

  • The AP broadcasts RF energy for aT seconds, after which offloading WDs use the remaining (1−a)T seconds for uplink transmission.
  • Offloading WDs take turns transmitting to avoid co-channel interference, with each WD assigned an individual transmission duration τiT.
  • 1) Local Computing Mode: A local WD can harvest energy and compute simultaneously, allowing computation throughout the entire frame.
  • 1) Local Computing Mode: Local computation depends on processor speed, computation duration, cycles per bit, maximum speed, and processor power coefficient.
  • 2) Offloading Mode: Offloading capacity is determined by transmission power, duration, bandwidth, receiver noise, and the data-transmission overhead ratio.
  • 2) Offloading Mode: Because AP computation and feedback are much faster than WD transmission and the output is small, their time and energy costs are neglected.

III. PROBLEM FORMULATION

The paper formulates weighted sum computation-rate maximization over computing modes and transmission times, then reduces the problem and develops lower-complexity optimization procedures.

  • III. PROBLEM FORMULATION: The objective maximizes the weighted sum computation rate of all WDs by jointly selecting modes and allocating WPT and offloading time.
  • III. PROBLEM FORMULATION: The original formulation is non-convex because mode selection is combinatorial and objective and constraint expressions contain multiplicative terms.
  • III. PROBLEM FORMULATION: For fixed WPT time, local WD speed and computation duration can be optimized independently, and the maximum local rate uses the full frame.
  • III. PROBLEM FORMULATION: With local computing variables eliminated, the reduced problem remains hard because of combinatorial mode selection, although fixed modes yield a convex time-allocation problem.
  • III. PROBLEM FORMULATION: Enumerating all 2^N mode selections is suitable only for small networks, such as N≤10, and becomes computationally infeasible as N increases.
  • IV. DECOUPLED OPTIMIZATION USING COORDINATE DESCENT METHOD: The decoupled method combines conditional time allocation, bisection search, and coordinate descent, with additional insights for homogeneous WDs.
  • A. Optimal Transmission Time Allocation Given M0: Given modes, the proposed bisection method finds the unique optimal multiplier and recovers time allocation using convex duality and monotonicity.
  • A. Optimal Transmission Time Allocation Given M0: The bisection method has O(N) complexity versus O(N^3) for an interior-point method and uses basic function evaluations suitable for constrained IoT hardware.

B. Coordinate Descent Method for Computing Mode Optimization

The coordinate descent method optimizes binary computing modes one coordinate at a time, accepting the most beneficial positive mode swap at each iteration.

  • The method represents each WD’s computing mode with an auxiliary binary variable and optimizes one variable at a time to seek a local maximum.
  • For each WD, the swap reward is the increase in the objective value after changing that WD’s current computing mode.
  • The modulo-2 operation flips the selected binary mode, and the WD with the highest positive reward performs the swap.
  • The objective value increases monotonically and is bounded above, so the coordinate descent method is guaranteed to converge.
  • Its convergence speed can be slow in large networks with many searching dimensions.

C. A Homogeneous Special Case

For homogeneous WDs, optimal offloading is favored by stronger channels, while local computation is less sensitive to channel quality. The resulting mode selection has a channel-based threshold structure.

  • Mode-1 WDs use the same spectral efficiency but receive offloading durations proportional to squared wireless channel gain.Their computation rates are likewise proportional to h^2 because both downlink energy harvesting and uplink offloading depend on channel conditions.
  • A ten-times stronger channel can yield 100 times higher computation rate for a mode-1 WD.The reported example contrasts a 1/10 channel with a 1/100 computation rate relative to another mode-1 WD.
  • Mode-1 computation rates are more sensitive to wireless channel conditions than mode-0 rates.Local computation depends only on the WD's own channel and decays more slowly; a ten-times stronger channel gives only 2.15 times higher local rate.
  • Relatively weak-channel WDs tend to use local computing, because offloading can leave them with very little allocated offloading time.Conversely, stronger-channel WDs are more likely to operate in offloading mode.
  • The optimal computing mode selection has a threshold structure based on wireless channel strength.At optimum, every mode-1 WD has a stronger channel than every mode-0 WD.

V. JOINT OPTIMIZATION USING ADMM-BASED METHOD

The ADMM-based method reformulates the coupled mixed optimization so that mode selection and time allocation can be optimized jointly through smaller subproblems. Its per-iteration complexity grows linearly with network size.

  • The method targets large networks because coordinate descent can have high computational complexity in high-dimensional mode-selection searches.The proposed alternative jointly optimizes computing modes and transmission time allocation.
  • The ADMM-based approach has computational complexity that increases slowly with network size N.The algorithm is designed for networks ranging from tens to several hundred of WDs.
  • ADMM decomposes the hard combinatorial problem into N parallel smaller subproblems.The reformulation introduces binary mode variables and auxiliary variables to remove coupling among users.
  • Each local subproblem has O(1) complexity, so Step 1 has overall complexity O(N).The local mode is selected by comparing the objective values for mi = 0 and mi = 1.

2) Step 2:

The remaining ADMM updates optimize the coupling variables and dual variables using convex optimization and bi-section search. Each of the three steps has O(N) complexity, while nonconvexity can prevent exact primal optimality.

  • The coupling-variable update is formulated as a convex optimization problem and solved with a low-complexity bi-section search.The search over ψ has computational complexity O(N).
  • Each ADMM iteration has O(N) complexity because all three update steps have O(N) complexity.Step 3 is also linear in N.
  • The dual variables are updated sequentially after the local and coupling-variable updates.The ADMM iterations repeat these three updates until specified stopping thresholds are met.
  • The ADMM algorithm may not exactly reach the primal optimum because nonconvexity can create a duality gap.The terminated solution is therefore treated as an approximate solution, whose gap is evaluated through simulations.

VI. EXTENSIONS AND DISCUSSIONS

The proposed methods extend to fairness-oriented max-min optimization, partial-offloading relaxations, and unequal uplink/downlink channels. Simulations examine channel, efficiency, and algorithmic effects under specified wireless-powering settings.

  • Extensions: The CD and ADMM algorithms extend to unequal uplink and downlink channels without changing their structure.This also covers systems with separate RF energy-transmitter and edge-server nodes.
  • Extensions: The methods can solve max-min computation-rate optimization, which maximizes the minimum WD rate and supports user fairness.The max-min problem has a dual form resembling weighted-sum-rate maximization.
  • Extensions: Linear relaxation permits each WD to divide harvested energy between local computation and offloading.Its convex optimum provides an upper bound for the binary-offloading problem, while LR-Round creates a feasible binary solution.
  • Extensions: At the relaxed optimum, some WDs generally perform both local computation and offloading.This differs from binary offloading, where EO,i is either zero or the full harvested energy Ei.
  • Simulation results: In homogeneous simulations, the optimal mode selection remains threshold-based as computing efficiency changes, while fewer WDs choose local mode as ki increases.For the studied 10-WD case, stronger-channel WDs use mode 1 and offloading improves their computation rates.
  • Simulation results: In heterogeneous simulations, weighting factors dominate mode selection under small channel disparity, whereas channel conditions dominate as disparity increases.At de = 2, the four higher-weight WDs use mode 1; at de = 2.8, the four strongest-channel WDs do so.

B. Computation Rate Performance Comparison

The proposed CD and ADMM methods maintain near-optimal computation-rate performance across network setups and outperform fixed-mode and relaxed-rounding benchmarks.

  • Varying path-loss exponent: At most 0.05% performance gap separates the proposed CD and ADMM methods from the optimal value across path-loss exponents.Their curves overlap the optimal solution over de from 2 to 3.6.
  • Varying AP-to-WD distance: The proposed CD and ADMM methods achieve near-optimal performance for all average AP-to-WD distances.The offloading-only and local-computing-only schemes instead favor small and large distances, respectively.
  • Varying network size: 86.3% of the upper-bound performance is achieved on average by CD/ADMM, while their computation rate is 6.3% higher than LR-Round.The upper bound is obtained by linearly relaxing the binary offloading constraint.
  • Varying network size: For some placement scenarios, LR-Round is more than 10% lower than CD/ADMM and is strictly worse across all reported placement scenarios.The LR-Round scheme’s performance is sensitive to WD placement because mode choices can be mismatched to locations.
  • Overall comparison: CD/ADMM is on average 18.5% and 26.2% higher than the offloading-only and local-computing-only schemes, respectively.Across path loss, placement, and network-size changes, fixed-mode benchmarks can perform poorly in practical setups.

C. Computational Complexity Evaluation

The complexity evaluation contrasts CD’s faster small-network implementation with ADMM’s slower growth in complexity as the number of WDs increases.

  • CD complexity: The CD method’s total time complexity is O(N3), because its iteration count, per-iteration executions, and subproblem cost scale with N.The CD iteration count is O(N), Algorithm 1 executes O(N2) times overall, and each execution costs O(N).
  • ADMM complexity: The ADMM-based method has O(N) overall complexity because its iteration count remains approximately O(1) and each iteration costs O(N).This slower growth makes ADMM more manageable in networks ranging from tens to several hundred WDs.
  • Practical trade-off: CD may take less computation time for small N, whereas ADMM’s complexity increases much more slowly as network size grows.CD uses basic function evaluations, while ADMM requires more complex convex optimization algorithms.
  • Algorithm design: The optimization jointly handles computing-mode selection and transmission-time allocation, with CD decoupling them and ADMM optimizing them jointly.Both methods target the combinatorial mode-selection difficulty in the weighted sum computation-rate problem.
  • Practical trade-off: The paper recommends CD for small networks or hardware-constrained MEC servers and ADMM for large-scale networks.The recommendation follows the O(N3) versus O(N) complexity contrast.

APPENDIX A PROOF OF LEMMA 2

The appendix proves optimality conditions for the time-allocation subproblem by establishing a unique root of a monotonically decreasing function.

  • Optimality condition: The optimal multiplier ν* is characterized by the condition Q(ν*) = 0 for the convex subproblem given M0.This condition is sufficient for optimality.
  • Monotonicity: Q(ν) is monotonically decreasing because its component terms decrease with ν.The proof uses the increasing behavior of p1(ν) and decreasing behavior of ϕj(ν) to establish the aggregate monotonicity.
  • Existence and uniqueness: Q(ν) approaches positive infinity as ν approaches zero and negative infinity as ν approaches infinity.These endpoint limits establish existence of a root when combined with monotonicity.
  • Existence and uniqueness: Therefore, a unique ν* > 0 satisfies Q(ν*) = 0 at the optimum.The appendix completes the proof by combining the endpoint limits with strict monotonic behavior.
Loading 1708.08810v4…