PaperlayerView exact revision on arXiv

Source-linked AI summary

Hierarchical Fog-Cloud Computing for IoT Systems: A Computation Offloading Game

Hamed Shah-Mansouri, Vincent W. S. Wong

arXiv:1710.06089v1cs.DCcs.GTcs.NI

TL;DR

Fog systems must allocate limited edge resources among IoT users whose individual QoE objectives may conflict with aggregate optimization. The paper models this competition as a potential offloading game, proves equilibrium properties, and introduces a faster near-optimal mechanism. Numerical studies report more beneficial users than an existing mechanism and substantially lower delay with fog nodes.

  • Problem

    Existing fog offloading work optimizes overall system performance, while selfish IoT users seek individual QoE under limited fog resources.

  • Method

    The paper formulates a potential computation-offloading game, analyzes its Nash equilibrium and price of anarchy, and proposes a near-optimal resource allocation algorithm.

  • Results

    The proposed mechanism provides up to 20% more beneficial users than the compared offloading mechanism and reduces delay as fog-node availability increases.

  • Takeaways & Limitations

    Fog nodes can provide low-latency computing services for delay-sensitive IoT applications while the equilibrium remains close to the optimal social cost.

Abstract

from arXiv · show

Fog computing, which provides low-latency computing services at the network edge, is an enabler for the emerging Internet of Things (IoT) systems. In this paper, we study the allocation of fog computing resources to the IoT users in a hierarchical computing paradigm including fog and remote cloud computing services. We formulate a computation offloading game to model the competition between IoT users and allocate the limited processing power of fog nodes efficiently. Each user aims to maximize its own quality of experience (QoE), which reflects its satisfaction of using computing services in terms of the reduction in computation energy and delay. Utilizing a potential game approach, we prove the existence of a pure Nash equilibrium and provide an upper bound for the price of anarchy. Since the time complexity to reach the equilibrium increases exponentially in the number of users, we further propose a near-optimal resource allocation mechanism and prove that in a system with $N$ IoT users, it can achieve an $ε$-Nash equilibrium in $O(N/ε)$ time. Through numerical studies, we evaluate the users' QoE as well as the equilibrium efficiency. Our results reveal that by utilizing the proposed mechanism, more users benefit from computing services in comparison to an existing offloading mechanism. We further show that our proposed mechanism significantly reduces the computation delay and enables low-latency fog computing services for delay-sensitive IoT applications.

I. INTRODUCTION

The paper addresses fog-resource allocation when selfish IoT users compete for limited processing power while seeking individual QoE. It formulates a potential offloading game, analyzes equilibrium efficiency, and proposes a faster near-optimal mechanism evaluated numerically.

  • Fog computing can reduce backbone traffic and latency for delay-sensitive IoT applications, but fog nodes have limited processing power.
  • B. Motivation and Contributions: Existing offloading studies primarily optimize aggregate system objectives, whereas selfish IoT users seek to maximize their individual QoE.
  • B. Motivation and Contributions: The paper models competition among IoT users as a potential game for determining computation offloading decisions.
  • B. Motivation and Contributions: The game has a pure Nash equilibrium, but reaching it may require time exponential in the number of IoT users.
  • B. Motivation and Contributions: O(N/ε) steps achieve an ε-Nash equilibrium with the proposed near-optimal resource allocation algorithm.
  • B. Motivation and Contributions: Fog nodes reduce computation time for delay-sensitive applications by up to 70%, and the proposed mechanism yields higher QoE in numerical experiments.

A. Hierarchical Computing Structure

The system lets each IoT user execute locally or offload an entire task to one accessible fog node or remote cloud server. QoE is defined through reductions in computation energy and delay, with fog resources shared among competing users.

  • A. Hierarchical Computing Structure: IoT users can execute tasks locally or offload them through access points to nearby fog nodes or remote cloud servers.
  • A. Hierarchical Computing Structure: Remote cloud servers are modeled as virtual machines with sufficient and dedicated processing power f0.
  • A. Hierarchical Computing Structure: Fog nodes have limited processing power fs that is equally shared among applications offloaded by IoT users.
  • B. IoT Users and Computation Task Models: Each task is either executed locally or offloaded entirely to one computing server, subject to user-server connectivity.
  • B. IoT Users and Computation Task Models: QoE is the cost reduction from offloading, where task cost combines computation energy and delay; local execution gives zero QoE.
  • A. Hierarchical Computing Structure: Task computation time at fog nodes increases with competing workloads, whose processing power is equally shared and later reassigned as tasks depart.

III. COMPUTATION OFFLOADING GAME

The paper models selfish IoT users’ offloading decisions as a weighted potential game in which each user maximizes individual QoE. The game has a pure Nash equilibrium reachable by best-response updates, but exact convergence can be exponential in the number of users.

  • Game formulation: Each user chooses a feasible offloading strategy that maximizes its own QoE in response to other users’ strategies.Feasibility enforces at most one destination per task and requires an available wireless link to an offloading server.
  • Potential-game formulation: The users’ interactions form a weighted potential game with a potential function based on weighted aggregate QoE.The associated weights are stated as w_n = λT_n.
  • Equilibrium existence: A pure Nash equilibrium exists because the game is finite and has the finite improvement property.At equilibrium, no user can unilaterally improve its QoE by changing strategy.
  • Equilibrium computation: Best-response adaptation converges to an equilibrium in finite time by repeatedly updating each user to its best response.Users need only delay information from nearby fog nodes when computing their responses.

B. Price of Anarchy (PoA)

The paper evaluates how selfish offloading affects social cost using the price of anarchy, comparing equilibrium outcomes with centralized optimal allocation. It proves a constant upper bound and identifies local execution by all users as the worst equilibrium in the relevant case.

  • PoA formulation: The price of anarchy measures how much social cost increases under selfish equilibrium behavior relative to the optimal centralized allocation.The analysis uses a cost-minimization formulation with the same equilibrium as the QoE-maximization game.
  • PoA formulation: The social cost is the aggregate cost of all IoT users, and the PoA compares its worst equilibrium value with the centralized minimum.The equilibrium set and joint strategy space are explicitly used in defining the ratio.
  • PoA bound: Theorem 2 proves that the PoA is bounded by a constant, including an upper bound of N_s.N_s denotes the maximum number of IoT users allocated to a fog node.
  • PoA proof: The PoA bound is derived by comparing equilibrium and socially optimal strategies across local execution and offloading cases.The proof obtains a lower bound on optimal social cost when users face no competition.
  • Worst equilibrium: When all users choose local execution in a Nash equilibrium, that equilibrium is the worst one in terms of social cost.The proof establishes this by showing that any higher-cost equilibrium would give a user an incentive to switch to local execution.

IV. NEAR–OPTIMAL RESOURCE ALLOCATION MECHANISM

The paper proposes a better-response resource allocation algorithm that reaches an ε-Nash equilibrium in polynomial time, addressing the best-response algorithm’s time complexity. The method permits bounded incentives to deviate while reducing computational effort.

  • ε-Nash equilibrium: An ε-Nash equilibrium allows each user’s incentive to deviate from the equilibrium to be bounded by ε.Unlike an exact Nash equilibrium, users may retain a small bounded gain from changing strategy.
  • Better-response algorithm: The algorithm updates each user to a feasible strategy that improves QoE by more than ε, stopping when no such strategy exists.This stopping condition corresponds to reaching a near-Nash equilibrium.
  • Complexity guarantee: For any ε>0, Algorithm 2 reaches an ε-Nash equilibrium in O(N/ε) steps.The result establishes polynomial time complexity in the number of IoT users N.
  • Complexity guarantee: Each better-response update increases the potential function by at least ε/λ^T, while the potential function remains bounded above.The weighted potential-game property supports the convergence and complexity proof.

V. PERFORMANCE EVALUATION

The performance evaluation compares the proposed algorithm with socially optimal allocation and an existing offloading mechanism, focusing on equilibrium QoE and efficiency.

  • Evaluation scope: The evaluation examines users’ QoE at equilibrium, social optimum, and under an existing offloading algorithm.These comparisons assess both the proposed algorithm’s user-level outcomes and equilibrium efficiency.

A. Simulation Setup

The simulation setup models heterogeneous IoT devices, workloads, communication interfaces, and fog-cloud delays to evaluate computation offloading under varied operating conditions.

  • Device and workload models: IoT device CPU clock speeds are sampled uniformly from 100 MHz to 1 GHz.The range reflects processor speeds from ARM Cortex–M3 devices to smartphones using ARM Cortex–A8 processors.
  • Communication and energy models: CPU energy consumption is modeled as α_n z_n γ_n/f_n for a task of size z_n and processing density γ_n.The parameter α_n depends on the CPU model, with κ_n = 0.33, ϕ_n = 3, and ϱ_n = 0.1 used for all users.
  • Communication and energy models: Each IoT device uses LTE for remote-cloud communication and WiFi or Bluetooth to connect to at most two nearby fog nodes.The communication model includes three wireless interfaces and user-dependent transmission-energy parameters.
  • Communication and energy models: The assumed remote-cloud roundtrip delay is 200 msec, while the roundtrip delay between IoT devices and fog nodes is negligible.This setup distinguishes remote-cloud latency from nearby fog communication.
  • Device and workload models: Task sizes and processing densities are uniformly distributed over [100 B, 0.5 MB] and [100, 600] cycles per bit, respectively.The setup covers diverse computing jobs and IoT applications.

B. Computation Offloading Game

The study compares exact and ε-Nash equilibria using average perceived QoE. Small ε preserves equilibrium QoE closely, while larger ε trades QoE for lower computational complexity.

  • QoE at equilibria: For ε = 0.01, average QoE at the ε-Nash equilibrium is almost the same as at the exact Nash equilibrium.When ε is very small, users may choose the same strategy as at the Nash equilibrium.
  • QoE at equilibria: Increasing ε trades lower QoE for reduced computational complexity while retaining the polynomial convergence guarantee.The trade-off follows from using a near-equilibrium condition instead of requiring exact best responses.

1) Average QoE:

Average QoE is higher with more fog nodes because nearby resources reduce offloading delay, but it declines as the number of IoT users increases and fog-node workloads grow.

  • More fog nodes increase average user QoE by providing nearby computing resources that reduce delay for offloaded tasks.The resulting delay reduction consequently improves user QoE.
  • More IoT users reduce average QoE because each fog node handles a higher workload.

2) Average Delay:

Fog nodes reduce task-processing delay relative to remote-cloud-only offloading, while larger cloud roundtrip delays and heavier workloads increase delay. More fog nodes shift delay components by reducing computation and roundtrip time but increasing communication time.

  • Adding fog nodes significantly reduces task delay by enabling low-latency offloading to nearby computing resources.With no fog nodes, users can only offload to remote cloud servers and tasks experience huge delay.
  • The study categorizes average task delay into computation time, communication time, and roundtrip delay.
  • Larger remote-cloud roundtrip delays substantially increase average task delay when 50 fog nodes are available.Limited fog-node processing power and reduced interest in remote cloud servers contribute to the increase.
  • When fog resources are limited and user numbers increase, users may avoid fog nodes because their computation time becomes long.
  • More fog nodes reduce computation time and roundtrip delay but increase communication time for tasks.More users choose offloading rather than local computing; local computing has zero communication time.

3) Number of Beneficial Users:

The number and share of beneficial users depend on cloud roundtrip delay, fog availability, and system load. The proposed mechanism benefits more users than the compared offloading mechanism, especially when fog nodes are available.

  • When N = 50, roundtrip-delay effects are negligible because nearby computing resources are sufficient and users avoid remote-cloud offloading.
  • More fog nodes reduce tasks offloaded to remote cloud servers, while increasing N produces a larger rise in cloud offloading than fog-node offloading.
  • Up to 20% more users benefit from computing services under the proposed mechanism than under the mechanism in.
  • 18% more users benefit with the proposed mechanism than with when varying the number of fog nodes.The number of beneficial users significantly decreases when no fog node is available.

C. Social Cost and PoA

The proposed offloading mechanism achieves a social cost close to the optimum, so the efficiency loss from strategic IoT-user behavior is negligible. Compared with local computing, hierarchical fog-cloud computing substantially reduces total user cost.

  • Beneficial users: The proposed mechanism increases the number of beneficial users by up to 20% compared with the offloading mechanism proposed in [8], with S = 60.
  • Beneficial users: When S = 0, only remote cloud services are available in the comparison of beneficial users across fog-node counts.
  • Social cost and equilibrium efficiency: The computation offloading game’s total cost is close to the socially optimal cost, indicating a price of anarchy close to 1.This supports the theoretical result that the game’s price of anarchy is bounded by a constant.
  • Social cost and equilibrium efficiency: Local computing imposes a huge total cost on IoT users, whereas the hierarchical fog-cloud paradigm significantly reduces it.The comparison includes local computing, remote cloud computing, and the computation offloading game.
  • Social cost and equilibrium efficiency: The proposed computation offloading mechanism achieves a close-to-optimal social cost.
Loading 1710.06089v1…