PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Multi-User Computation Offloading for Mobile-Edge Cloud Computing

Xu Chen, Lei Jiao, Wenzhong Li, Xiaoming Fu

arXiv:1510.00888v1cs.NI

TL;DR

The paper addresses multi-user computation offloading for mobile-edge cloud computing when centralized optimization is difficult and wireless users interact across channels. It formulates a game, analyzes its equilibrium properties, and designs a distributed algorithm. The algorithm achieves efficient offloading performance and scales well as the user population grows.

  • Problem

    Centralized optimal multi-user computation offloading is NP-hard in multi-channel wireless interference environments, making distributed decision-making important.

  • Method

    The paper formulates users’ offloading decisions as a multi-user computation offloading game and designs a distributed algorithm that reaches a Nash equilibrium.

  • Results

    Up to 30% more beneficial cloud-computing users and up to 68%, 55%, and 51% lower system-wide computation overhead are reported against the stated comparison solutions.

  • Takeaways & Limitations

    The proposed distributed offloading approach achieves superior computation offloading performance and scales well as the number of users increases.

Abstract

from arXiv · show

Mobile-edge cloud computing is a new paradigm to provide cloud computing capabilities at the edge of pervasive radio access networks in close proximity to mobile users. In this paper, we first study the multi-user computation offloading problem for mobile-edge cloud computing in a multi-channel wireless interference environment. We show that it is NP-hard to compute a centralized optimal solution, and hence adopt a game theoretic approach for achieving efficient computation offloading in a distributed manner. We formulate the distributed computation offloading decision making problem among mobile device users as a multi-user computation offloading game. We analyze the structural property of the game and show that the game admits a Nash equilibrium and possesses the finite improvement property. We then design a distributed computation offloading algorithm that can achieve a Nash equilibrium, derive the upper bound of the convergence time, and quantify its efficiency ratio over the centralized optimal solutions in terms of two important performance metrics. We further extend our study to the scenario of multi-user computation offloading in the multi-channel wireless contention environment. Numerical results corroborate that the proposed algorithm can achieve superior computation offloading performance and scale well as the user size increases.

I. INTRODUCTION

Mobile-edge cloud computing places cloud capabilities near mobile users, but efficient offloading requires coordinating local-versus-cloud decisions and channel selection under interference. The paper models these distributed decisions as a game and develops an algorithm with equilibrium, convergence, and scalability guarantees.

  • Motivation: Mobile-edge cloud computing provides nearby cloud capabilities to support resource-hungry applications on resource-constrained mobile devices.The paradigm addresses latency concerns associated with remote public clouds by placing cloud-computing capabilities at the edge of radio access networks.
  • Problem: Users must decide whether to compute locally or offload, and offloading users must select channels while avoiding interference from simultaneous transmissions.Too many users on one channel can reduce data rates, energy efficiency, and transmission performance.
  • Approach: The centralized optimal multi-user offloading problem is NP-hard, motivating a distributed game-theoretic formulation that accounts for communication and computation.The formulation targets decentralized decisions among users with potentially different interests and reduces reliance on complex centralized management.
  • Game Properties: The multi-user computation offloading game is a potential game with the finite improvement property and a Nash equilibrium.These properties follow from constructing a potential function for the game.
  • Algorithm and Evaluation: The distributed algorithm reaches a Nash equilibrium, has a derived convergence-time upper bound, and is extended to multi-channel wireless contention.The study also quantifies efficiency using the number of beneficial cloud-computing users and system-wide computation overhead.

2) Cloud Computing:

Cloud offloading adds wireless transmission and cloud-execution overhead to mobile computation. The model combines these costs while neglecting outcome-return time under a stated application-size assumption.

  • Offloading incurs transmission time and energy for sending input data of size b_n through wireless access.The model accounts for additional time and energy associated with wireless transmission.
  • The cloud assigns user n a computation capability f_n^c, interpreted as CPU cycles per second.
  • The cloud computes task J_n execution time from the task and assigned cloud computation capability.
  • The offloading overhead aggregates wireless transmission and cloud-processing time and energy.The overhead is computed from the communication and execution models.
  • Return-transmission time is neglected because computation outputs are generally much smaller than input data.The paper also treats wireless spectrum as the most constrained resource.

III. MULTI-USER COMPUTATION OFFLOADING GAME

The section formulates multi-user offloading under interference as a centralized optimization and shows that finding its optimum is computationally difficult. This motivates distributed game-theoretic offloading based on users’ coupled channel decisions.

  • Users’ offloading decisions are coupled because sharing a wireless channel can create severe interference and lower data rates.Low data rates can increase wireless-access energy and processing time, making local computation preferable.
  • Beneficial cloud computing means offloading does not incur higher overhead than local computing.The definition compares cloud and local computation for a given decision profile.
  • More users achieving beneficial cloud computing implies higher utilization of cloud resources, while preserving individual rationality.
  • The centralized objective first maximizes the number of beneficial cloud-computing users and later considers system-wide computation overhead.
  • The maximum number of beneficial cloud-computing users is NP-hard to compute.The proof reduces maximum-cardinality bin packing to a special case of the offloading problem.
  • System-wide overhead minimization is also NP-hard because it requires combinatorial optimization over {0, 1, ..., M}^N.
  • The proposed game-theoretic solution achieves superior performance for system-wide computation overhead according to the paper’s reported evaluation.

B. Game Formulation

The paper models each user’s local-versus-cloud decision as a strategic game whose costs depend on other users’ channel choices. Its potential-game structure guarantees equilibrium existence and finite better-response convergence.

  • B. Game Formulation: Each user selects local computing or cloud computing through a wireless channel to minimize its computation overhead given other users’ decisions.
  • B. Game Formulation: The multi-user computation offloading game consists of users, strategy sets, and overhead functions treated as individual cost functions.
  • B. Game Formulation: At Nash equilibrium, no user can further reduce overhead by unilaterally changing strategy.
  • B. Game Formulation: Any user choosing cloud computing at Nash equilibrium must be a beneficial cloud-computing user.
  • C. Structural Properties: The game is analyzed as a potential game, using a potential function to establish its structural properties.
  • C. Structural Properties: A user’s cloud decision is beneficial when received interference on its chosen channel is no greater than its threshold T_n.
  • C. Structural Properties: The game therefore has a Nash equilibrium and finite improvement property, so asynchronous better responses reach equilibrium in finitely many iterations.
  • C. Structural Properties: The potential-game proof shows that a user’s overhead decrease produces a corresponding potential-function decrease across the considered decision-update cases.

IV. DISTRIBUTED COMPUTATION OFFLOADING ALGORITHM

The distributed algorithm lets users iteratively evaluate and contend for beneficial decision updates. The cloud authorizes at most the contending updates needed to implement the distributed process until termination.

  • Algorithm 1 is designed to achieve a Nash equilibrium of the multi-user computation offloading game.
  • Each user initializes its computation decision to a_n(0) = 0.
  • Users repeatedly act in parallel during decision slots and transmit pilot signals on their selected channels.
  • The base station reports received powers on all channels, enabling each user to compute its best-response set.
  • Users with nonempty best-response sets send RTU messages to contend for an update opportunity.
  • A user receiving an UP message selects a best response for the next slot; otherwise it retains its original decision.
  • The procedure repeats until the cloud sends an END message.

A. Algorithm Design

The distributed algorithm coordinates users’ offloading decisions through interference measurement and sequential best-response updates. It exploits the game’s finite improvement property to seek mutually satisfactory decisions before task execution.

  • Wireless Interference Measurement: The algorithm measures total received power on every channel and feeds these measurements back to users.Users selecting cloud computing transmit pilot signals on their chosen channels.
  • Wireless Interference Measurement: Each user derives channel-specific interference by subtracting its own received power on its selected channel.On channels where it does not transmit, the measured total power equals received interference.
  • Offloading Decision Update: Using measured interference, each user computes its best-response updates and identifies whether it can improve its current decision.The update rule relies on the finite improvement property of the multi-user computation offloading game.
  • Offloading Decision Update: Users with improving decisions send request-to-update messages, after which the cloud randomly selects one contender and grants update permission.Users without an improving decision retain their current choices for the next decision slot.

B. Convergence Analysis

The algorithm converges by repeatedly decreasing the game’s potential function, with a finite upper bound on decision slots. Its per-slot computation is dominated by sorting channel measurements.

  • Termination: The algorithm terminates when the cloud receives no request-to-update messages, then broadcasts an END message before task execution.Finite improvement property guarantees convergence to a Nash equilibrium within finitely many decision slots.
  • Computational Complexity: O(M log M) is the typical per-slot complexity because computing each best response requires sorting M channel measurements.Most other operations involve basic arithmetic calculations.
  • Convergence Bound: Theorem 3 bounds termination by at most Q^2_min N^2 + Q_max T_max Q_min N decision slots when T_n and Q_n are non-negative integers.The bound is presented as a quadratic convergence-time upper bound under mild conditions.
  • Potential Decrease: Each improving update decreases the potential function by at least Q_min, driving the algorithm toward a minimal potential point.The proof analyzes a user changing from a current decision to an improving alternative.
  • Practical Timing: A roughly 70-microsecond LTE slot makes decision updates short relative to computation execution times of hundreds of milliseconds for mobile gaming.The paper therefore characterizes update time as negligible compared with execution time.

V. PERFORMANCE ANALYSIS

The paper evaluates worst-case Nash-equilibrium efficiency against centralized optima using beneficial cloud-computing users as one metric. The bound becomes closer to optimal when user access conditions are more similar.

  • Metric I: Beneficial Users: The price of anarchy compares the worst-case Nash equilibrium with the centralized optimum for the number of beneficial cloud-computing users.This metric favors a larger price of anarchy.
  • Metric I: Beneficial Users: When the centralized optimum offloads every user, the price of anarchy for beneficial cloud-computing users equals 1.The centralized optimum is defined to maximize the number of beneficial cloud-computing users.
  • Metric I: Beneficial Users: The worst-case Nash equilibrium is closer to the centralized optimum when differences in wireless access performance and interference tolerance are small.The relevant user parameters are q_n, g_n,s, and T_n.

B. Metric II: System-wide Computation Overhead

For system-wide computation overhead, the paper compares Nash equilibria with the centralized overhead-minimizing solution. Greater wireless access and lower local-computing costs improve worst-case equilibrium performance.

  • Metric II: System-wide Computation Overhead: The system-wide computation-overhead metric sums users’ overhead functions, and its centralized benchmark minimizes that total.Unlike the beneficial-user metric, a smaller price of anarchy is more desirable here.
  • Metric II: System-wide Computation Overhead: Theorem 5 provides a price-of-anarchy bound for system-wide computation overhead in the multi-user computation offloading game.The centralized optimum gives the baseline with price of anarchy at least 1.
  • Metric II: System-wide Computation Overhead: At Nash equilibrium, users cannot reduce overhead through unilateral channel changes, constraining the interference patterns considered in the proof.The analysis bounds the interference received by users who offload.
  • Metric II: System-wide Computation Overhead: Greater wireless access, represented by a larger number of channels M, improves worst-case Nash-equilibrium performance.The paper links more channels with smaller K^c_n,max.
  • Metric II: System-wide Computation Overhead: Lower local-computing costs make the worst-case Nash equilibrium closer to the centralized optimum and reduce the price of anarchy.The paper denotes these costs through K^m_n.

VI. EXTENSION TO WIRELESS CONTENTION MODEL

The paper extends the computation offloading game to packet-level wireless contention, preserving its potential-game structure, Nash equilibrium, and finite improvement property. The existing distributed algorithm therefore retains its performance and convergence guarantees in this setting.

  • Wireless contention model: The extension models shared-spectrum access at the packet level, as in CSMA-based WiFi-like networks.Users contend to capture the channel for packet transmission over periods ranging from hundreds of milliseconds to several seconds.
  • Beneficial offloading condition: A user benefits from cloud computing when the aggregated contention weight on its chosen channel satisfies µ_n(a) ≤ T_n.The threshold compares received contention with the user-specific threshold T_n.
  • Game structure: The contention-model offloading game is a potential game, so it always has a Nash equilibrium and the finite improvement property.Its potential function is given in equation (31).
  • Game structure: The contention model has the same structural property as the wireless interference model.The potential function becomes identical after defining q_ng_n,s = W_n.
  • Algorithmic implication: The distributed computation offloading algorithm applies to the contention model by treating aggregated contention weights as received interference.The same performance and convergence guarantees therefore apply.

VII. NUMERICAL RESULTS

Numerical studies evaluate the distributed offloading algorithm under heterogeneous users and compare it with local, all-cloud, and centralized optimization baselines. The algorithm converges to equilibrium, improves performance across both reported metrics, remains close to the centralized solution, and scales well as users increase.

  • Experimental setup: The evaluation uses a 50m small-cell coverage range, M = 5 channels, heterogeneous device capabilities, and a face recognition task.Device CPU capability is randomly assigned from {0.5, 0.8, 1.0} GHz, while the cloud capability is 10 GHz.
  • Convergence: The algorithm converges to a stable point, while beneficial cloud computing users and system-wide computation overhead move toward equilibrium.These dynamics are shown for users’ overhead, beneficial users, and system-wide overhead.
  • Performance comparison: Up to 30% more beneficial cloud computing users are achieved than with cloud computing by all users.The comparison uses experiments with N = 15, ..., 50 users and averages over 100 repetitions per user number.
  • Performance comparison: Performance loss relative to the centralized Cross Entropy solution is at most 12% for beneficial users and 14% for system-wide computation overhead.The Cross Entropy method is used to compute a near-optimal centralized solution.
  • Scalability: Average convergence time increases almost linearly with the number of mobile device users.The result demonstrates fast convergence and practical scalability with user size.

VIII. RELATED WORK

Prior work largely addressed single-user or restricted multi-user offloading, whereas this paper studies the harder multi-channel setting and identifies extensions for future study.

  • Earlier studies primarily examined single-user computation offloading, including wireless access, energy savings, adaptive policies, and timeout schemes.
  • Only a few prior works considered multiple users, including shared-bandwidth optimization and single-channel binary offloading decisions.
  • The multi-channel generalization is NP-hard, unlike the single-channel case, and its price of anarchy depends partly on the number of available channels.
  • Compared with work assuming more channels than users, this paper considers limited channels where users may experience interference.
  • Future work extends the setting to dynamically departing users and joint power-control and offloading decisions.
Loading 1510.00888v1…