PaperlayerView exact revision on arXiv

Source-linked AI summary

Over-the-Air Computation Systems: Optimization, Analysis and Scaling Laws

Wanchun Liu, Xin Zang, Yonghui Li, Branka Vucetic

arXiv:1909.00329v2cs.ITeess.SP

TL;DR

IoT systems need efficient collection and computation of massive sensor data despite limited spectrum and edge computation capacity. The paper analyzes single-antenna AirComp, deriving a closed-form Tx-Rx policy under per-sensor peak-power constraints and studying its ergodic behavior. The computation-optimal policy achieves average computation MSE decay of O(1/sqrt(K)) and numerically exhibits vanishing average power consumption as K increases.

  • Problem

    Massive-sensor wireless data collection and large-scale edge computation are challenging under limited spectrum bandwidth and computation capacity.

  • Method

    The paper derives a closed-form computation-optimal Tx-Rx policy for single-antenna AirComp and evaluates policies under Rayleigh fading using average computation MSE and power consumption.

  • Results

    The computation-optimal policy’s average computation MSE decays at O(1/sqrt(K)) and its average power consumption approaches zero numerically as K increases.

  • Takeaways & Limitations

    AirComp can jointly support computation-effective and energy-efficient operation for large numbers of sensors under the studied setting.

Abstract

from arXiv · show

For future Internet of Things (IoT)-based Big Data applications (e.g., smart cities/transportation), wireless data collection from ubiquitous massive smart sensors with limited spectrum bandwidth is very challenging. On the other hand, to interpret the meaning behind the collected data, it is also challenging for edge fusion centers running computing tasks over large data sets with limited computation capacity. To tackle these challenges, by exploiting the superposition property of a multiple-access channel and the functional decomposition properties, the recently proposed technique, over-the-air computation (AirComp), enables an effective joint data collection and computation from concurrent sensor transmissions. In this paper, we focus on a single-antenna AirComp system consisting of $K$ sensors and one receiver (i.e., the fusion center). We consider an optimization problem to minimize the computation mean-squared error (MSE) of the $K$ sensors' signals at the receiver by optimizing the transmitting-receiving (Tx-Rx) policy, under the peak power constraint of each sensor. Although the problem is not convex, we derive the computation-optimal policy in closed form. Also, we comprehensively investigate the ergodic performance of AirComp systems in terms of the average computation MSE and the average power consumption under Rayleigh fading channels with different Tx-Rx policies. For the computation-optimal policy, we prove that its average computation MSE has a decay rate of $O(1/\sqrt{K})$, and our numerical results illustrate that the policy also has a vanishing average power consumption with the increasing $K$, which jointly show the computation effectiveness and the energy efficiency of the policy with a large number of sensors.

I. INTRODUCTION

AirComp addresses the bandwidth and computation challenges of IoT data collection by combining concurrent wireless transmissions with function decomposition. The introduction describes its use across sensing, consensus, and distributed machine-learning applications, while distinguishing it from traditional single-source estimation.

  • IoT applications face difficult wireless data collection from massive sensors under limited spectrum bandwidth, especially when timely processing is required.
  • Edge devices also face computation challenges when processing large amounts of data from many sources.
  • AirComp uses MAC signal superposition and function decomposition so sensors transmit pre-processed signals concurrently and the receiver post-processes their aggregate.
  • The approach completes transmission and computation for many sensors in one time slot rather than using a one-by-one transmit-then-compute protocol.
  • AirComp supports applications including over-the-air consensus and wireless distributed machine learning, alongside real-time sensing and data collection.
  • Unlike traditional CEO estimation, which reconstructs a single-source signal, AirComp estimates a function of distributed multi-source signals.

C. Contributions and Paper Organization

The paper develops and analyzes Tx-Rx scaling policies for single-antenna AirComp under per-sensor peak-power constraints, then extends the setting and compares related estimation problems. It derives a closed-form computation-optimal policy and studies MSE, power, scaling laws, and their tradeoff.

  • The paper minimizes the computation MSE of a single-antenna AirComp system by optimizing its Tx-Rx scaling policy under each sensor’s peak power limit.
  • Although the optimization is non-convex, the paper derives the single-antenna optimal solution in closed form and names it the computation-optimal policy.
  • The solution is extended to a receiver with N antennas, where the reported result significantly reduces computation MSE compared with existing work.
  • The paper formulates an estimation-centric MAC problem minimizing the sum of sensor estimation MSEs under per-sensor peak power and contrasts it with AirComp’s MSE-of-sum objective.
  • Under Rayleigh fading, it studies average computation MSE and average power consumption for different Tx-Rx policies as the number of sensors K increases.
  • The paper defines computation-effective policies by vanishing average computation MSE and energy-efficient policies by vanishing average power consumption, identifying a design tradeoff.
  • For the computation-optimal policy, the paper proves computation effectiveness, reports an average computation MSE decay rate of O(1/sqrt(K)), and finds numerical evidence of energy efficiency.

II. SYSTEM MODEL

The system model considers concurrent sensor transmissions over a single-antenna MAC, with Tx scaling at each sensor and Rx scaling at the receiver. It formulates peak-power-constrained computation-MSE minimization and notes the problem’s non-convexity.

  • The model contains K sensors with single antennas and a receiver, where each sensor sends a linearly scaled pre-processed signal through a MAC.
  • The received signal combines the scaled sensor signals through channel coefficients and additive white Gaussian noise, after which the receiver estimates the sum.
  • Pre-processed signals are bounded, zero-mean, normalized-variance, and mutually independent under the stated model assumptions.
  • The computation MSE measures distortion of the ideal sum, with expectation over the original signals and receiver noise.
  • Each sensor obeys a peak transmission-power constraint, while the receiver’s digital Rx-scaling factor has no constraint.
  • The resulting optimization is non-convex jointly in the Rx and Tx scaling factors, though it becomes convex when either side is fixed.
  • An alternating-direction solution may fail to converge to a global optimum, motivating the subsequent closed-form computation-optimal policy.

III. COMPUTATION-OPTIMAL AIRCOMP SYSTEM

The computation-optimal policy is obtained by partitioning the Rx-scaling factor into intervals indexed by a critical sensor number and exploiting unimodality of the resulting MSE sequence. Its structure combines maximum-power transmission for weaker channels with channel inversion for the others.

  • The critical number i indicates how many sensors use maximum transmission power under the computation-optimal Tx-Rx scaling policy.
  • The optimal Tx-Rx policy has a switching structure: sensors with the smallest channel coefficients use maximum power, while remaining sensors use channel-inversion-type power.
  • For each interval S_i of the Rx-scaling factor, the optimal Tx scaling factors yield a quadratic MSE objective in the Rx-scaling factor.
  • At least one sensor must transmit with maximum power at the minimum-MSE solution.
  • The optimal Rx-scaling factor is a_i⋆, and the optimal Tx-scaling factors follow by substituting i⋆ into the policy expression.
  • The sequence {g_i} is unimodal, increasing up to a critical index i⋆ and decreasing afterward.
  • The MSE sequence correspondingly decreases for i ≤ i⋆ and increases for i ≥ i⋆, identifying the globally optimal critical number.
  • The computation-optimal policy induces the minimum computation MSE and a corresponding power-consumption expression.

B. Extension to Multi-Antenna Receiver Case

The paper extends the single-antenna AirComp solution to a multi-antenna receiver, where exact optimization is intractable and near-optimal algorithms are developed.

  • System model: The multi-antenna receiver has N antennas, while each sensor remains single-antenna and uses a receiver scaling vector a.The channel vector for sensor k is h_k, and a is the receiver-side scaling vector.
  • Optimization challenge: The multi-antenna computation-MSE minimization problem is intractable and NP-hard.The proposed algorithms therefore build on the single-antenna solution in Theorem 1.
  • Algorithm design: For fixed unit vector v, optimal scaling can be obtained by replacing h_k with |v^⊤h_k| in Theorem 1.Writing a as |a|v reduces the receiver design to a single-antenna-like problem for a fixed v.
  • Algorithm design: Two practical methods search for suboptimal unit vectors: optimal antenna selection and random generation of candidate vectors.Antenna selection restricts v to the canonical basis vectors, while random search chooses the vector inducing minimum MSE in (18).
  • Performance and benchmarks: The two proposed multi-antenna methods achieve much better computation MSEs than the method in.The paper also presents channel-inversion and energy-greedy policies as intuitive benchmark policies.

IV. AIRCOMP SYSTEM VERSUS TRADITIONAL MAC SYSTEM

The section contrasts AirComp’s MSE-of-sum objective with traditional MAC’s sum-of-MSE objective. Their optimal Tx-Rx policies differ, although they coincide under a stated channel condition.

  • Objectives and system roles: Traditional MAC recovers every sensor signal individually, whereas AirComp computes a function of concurrent sensor transmissions using channel superposition.Both systems use coding-free sensor scaling and receiver-side linear scaling.
  • Traditional MAC optimization: The MAC design minimizes the sum of individual estimation MSEs under each sensor’s power constraint.For fixed transmit scalings, each receiver scaling factor affects only its corresponding sensor MSE.
  • Comparison: AirComp and traditional MAC optimize different objectives: AirComp is an MSE-of-sum problem, whereas MAC is a sum-of-MSE problem.Consequently, their optimal Tx-Rx scaling policies are generally different.
  • Traditional MAC optimization: Theorem 2 gives the optimal Tx-Rx scaling policy for the MAC sum-of-MSE problem.The theorem follows after substituting the optimal receiver scaling factors into the original problem.
  • Policy structure: The energy-greedy MAC policy uses the same maximum transmit power P at every sensor.This differs from the computation-optimal AirComp policy, whose transmit scalings depend on channel coefficients.
  • Comparison: When g_K=max_{1≤k≤K} g_k, AirComp’s optimal transmit scalings are identical to MAC’s, making the two policies equivalent for sum computation.Otherwise, AirComp remains distinct from conventional MAC, which first estimates individual signals and then sums them.

B. Achievable MSE Region and the Pareto Front

The section characterizes the achievable MSE region for a K-sensor MAC and identifies its Pareto front, while defining computation and energy scaling objectives for AirComp.

  • Achievable MSE region: The achievable MSE region M contains all K-tuples of sensor MSEs attainable under individual power constraint P.Each MSE_k uses the optimal receiver scaling in (23) and feasible transmit scaling ˜b_k.
  • Achievable MSE region: The achievable MSE region is convex, with (25a) and (25b) defining its inner and outer boundaries.The inner boundary is achieved by a specified sensor transmission choice, while the outer boundary satisfies MSE_k≤1.
  • Pareto front: The Pareto front consists of the intersection of M with the boundary sets B_1 through B_K.No MSE can be reduced on this front without increasing at least one other MSE.
  • Pareto front: The MSE tuple induced by the intersection of all inner boundaries belongs to the Pareto front, verifying the solution’s correctness.The optimal achievable tuple is illustrated as the intersection of the inner boundaries in Fig. 2.
  • AirComp connection: The computation-optimal AirComp policy assigns at least one sensor the maximum transmission power.This places its achievable MSE tuple on the inner boundaries of the MAC region.
  • Ergodic metrics: Average computation MSE and average power consumption are defined as E[MSE]/K and E[PW]/K under random channels.The ergodic analysis considers independently varying Rayleigh fading coefficients and studies scaling with K.
  • Scaling objectives: A computation-effective policy has average computation MSE approaching zero, while an energy-efficient policy has average power consumption approaching zero as K increases.The section tests whether benchmark and computation-optimal policies satisfy either or both properties.

A. Benchmark Policy 1: Channel-Inversion Policy

The channel-inversion policy is analyzed under Rayleigh fading as an energy-efficient but computation-ineffective benchmark, motivating comparison with alternative policies.

  • Channel model: Under Rayleigh fading, the ordered channel power gains are order statistics of K independent standard exponential samples.The analysis uses the minimum and maximum ordered gains to evaluate policy performance.
  • Computation performance: The channel-inversion policy has infinite average computation MSE and is not computation-effective.The poor result follows from the inverse behavior associated with the weakest channel gain.
  • Energy performance: The channel-inversion policy has average power consumption that follows a scaling law tending to zero with increasing K.Accordingly, the policy is classified as energy-efficient.
  • Comparison: The energy-greedy policy is not computation-effective because its average computation MSE remains bounded away from zero, despite having an upper bound of 1+ln 2.Its average MSE scaling law is therefore insufficient for convergence to zero.
  • Comparison: The energy-greedy policy is not energy-efficient because every sensor transmits with the same maximum power P.Its average power does not vanish as K increases.
  • Comparison: For large K, energy-greedy provides better computation performance but lower energy efficiency than channel inversion.The comparison establishes a tradeoff between computation effectiveness and energy efficiency.

C. The Existence of Computation-Effective and Energy-Efficient Policies

The paper characterizes when first-ı policies are computation-effective and energy-efficient, and establishes corresponding scaling laws for average computation MSE and power consumption. It also proves computation effectiveness for the computation-optimal policy while relying on numerical evidence for its energy efficiency.

  • The energy-greedy policy with lim supK→∞ı(K)/K = 1 is not computation-effective, because lim supK→∞E[MSE]/K ≥ µ(1/2) ≈ 0.12 > 0.
  • A first-ı policy is computation-effective iff ı(K) = o(K) and lim infK→∞ı(K) →∞.
  • The computation-optimal policy is computation-effective, with average computation MSE having at least a decay rate of O(1/√K).
  • An energy-efficient first-ı policy requires the critical-number function ı(K) to have a lower divergence rate of K/log(K).Its average power consumption decays no faster than O(ı(K)/K).
  • The computation-effective first-ı policy achieving minimum average power consumption has a decay rate between O(...).The supplied passage truncates the stated rate.
  • Scaling-law results for first-ı policies cannot directly characterize the computation-optimal policy because its optimal critical number depends on channel coefficients and has difficult-to-analyze statistics.The paper nevertheless numerically shows that the computation-optimal policy is energy-efficient.

VI. NUMERICAL RESULTS

Numerical evaluations compare Tx-Rx scaling policies by average computation MSE, power consumption, and variability as the sensor count K increases. The computation-optimal policy achieves lower MSE, while selected policies trade computation effectiveness against energy efficiency.

  • Critical-number scaling: The average and standard deviation of the computation-optimal policy’s critical number increase monotonically with K, scaling as K and K^1/3, respectively.The average critical number follows the stated scaling law when K > 10.
  • Computation MSE: All four finite-MSE policies have diminishing standard deviations of MSE/K, so MSE/K converges in probability to average computation MSE as K approaches infinity.For K > 10, lower average computation MSE is accompanied by smaller standard deviation.
  • Power consumption: Benchmark policies 1 and 2 have the lowest and highest power consumption, while the computation-optimal policy and the K policy approach zero average power consumption as K increases.The computation-optimal policy has better computation performance but higher power consumption than the compared K policy, illustrating a design tradeoff.
  • Power consumption: All policies’ PW/K standard deviations diminish with K; first-K policies fluctuate less because their critical number is deterministic, unlike the stochastic computation-optimal policy.With different transmission-power limits, the computation-optimal policy’s average power consumption also decays to zero as K increases.
  • Multi-antenna receiver: With N = 8 receiver antennas, optimal antenna selection achieves at least 40 times lower MSE than the method in.Optimal-selection and random-search policies have decreasing average MSE as the number of sensors increases, while the policy’s average MSE does not exist in Rayleigh fading.

VII. CONCLUDING REMARKS

The paper derives the computation-optimal AirComp policy and evaluates ergodic performance across Tx-Rx scaling policies as sensor count increases. The results show vanishing average computation MSE and power consumption, alongside a tradeoff between computation effectiveness and energy efficiency.

  • The computation-optimal policy is derived for the AirComp system, alongside comparisons with the traditional MAC system and different Tx-Rx scaling policies.
  • The computation-optimal policy has vanishing average computation MSE as the number of sensors increases.
  • The computation-optimal policy also has vanishing average power consumption with increasing sensor count.
  • Comparisons with first-i policies reveal a tradeoff between computation effectiveness and energy efficiency.The tradeoff is identified as important for implementation under practical computation-accuracy and energy-consumption constraints.
  • Energy-efficiency optimization problems are left for future work.

APPENDIX A: PROOF OF COROLLARY 3

The appendix proves Corollary 3 by rewriting the joint distribution under an ordering event and bounding terms involving exponential order statistics. It derives asymptotic bounds for average computation MSE and power consumption using inequalities, distributional properties, and large-K approximations.

  • The joint distribution is factorized conditionally on the event that U1 is no larger than the other channel-power variables.The ordered variables Uk for k > 1 are treated as independent exponential variables conditional on this event.
  • Upper and lower bounds for average computation MSE are derived from the ordered exponential variables and technical lemmas on their order statistics.The proof uses Jensen’s inequality, Cauchy-Schwarz, convexity, and bounds involving inverse gamma distributions.
  • The appendix completes the corollary by combining the derived bounds and large-K Riemann-sum approximations.The approximation uses a function that is monotonic and bounded on [0, 1/2].
  • The proof handles both cases ı(K) + 1 < K and ı(K) + 1 ≥ K, obtaining the same asymptotic results.
  • The average power consumption is bounded separately according to whether ı(K)/K converges to a nonzero value or to zero.The derivation uses the harmonic-series property in the zero-ratio case.
Loading 1909.00329v2…