PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Over-the-Air Computation

Alphan Sahin, Rui Yang

arXiv:2210.11350v5cs.ITcs.AIeess.SP

TL;DR

Many wireless applications need functions of distributed device data, but separating communication from computation can be inefficient. This survey examines practical OAC schemes, their enabling mechanisms, applications, and trade-offs. It reports that OAC can substantially improve computation rate over separation, with the advantage increasing as more devices participate.

  • Problem

    Computation-oriented wireless applications often need functions of local device information rather than the local information itself, motivating alternatives to separated communication and computation.

  • Method

    The paper surveys practical OAC schemes, their trade-offs, channel-combatting mechanisms, applications, and future research directions.

  • Results

    Approximately 10 times faster reliable computation is promised by OAC than separation for K = 100 edge devices.

  • Takeaways & Limitations

    OAC exploits wireless signal superposition to compute functions simultaneously and can reduce distributed-learning communication cost to that of a single edge device.

Abstract

from arXiv · show

Communication and computation are often viewed as separate tasks. This approach is very effective from the perspective of engineering as isolated optimizations can be performed. However, for many computation-oriented applications, the main interest is a function of the local information at the devices, rather than the local information itself. In such scenarios, information theoretical results show that harnessing the interference in a multiple access channel for computation, i.e., over-the-air computation (OAC), can provide a significantly higher achievable computation rate than separating communication and computation tasks. Moreover, the gap between OAC and separation in terms of computation rate increases with more participating nodes. Given this motivation, in this study, we provide a comprehensive survey on practical OAC methods. After outlining fundamentals related to OAC, we discuss the available OAC schemes with their pros and cons. We provide an overview of the enabling mechanisms for achieving reliable computation in the wireless channel. Finally, we summarize the potential applications of OAC and point out some future directions.

I. INTRODUCTION

Over-the-air computation (OAC) computes functions by harnessing wireless signal superposition rather than separating communication and computation. This survey organizes OAC schemes, reliability mechanisms, applications, and open research directions.

  • I. INTRODUCTION: OAC computes mathematical functions by exploiting signal superposition in wireless multiple access channels.Devices transmit simultaneously, allowing computation through channel interference rather than first collecting each local symbol at the fusion node.
  • I. INTRODUCTION: OAC research addresses channel distortion, synchronization errors, channel-state-information requirements, security, and hardware impairments.The survey discusses mechanisms including synchronization, power management, channel estimation, security, and computation architectures.
  • I. INTRODUCTION: The survey compares state-of-the-art OAC techniques and their trade-offs for reliable and efficient wireless function computation.Its framework considers computation under fading channels and different encoding strategies.
  • I. INTRODUCTION: Nomographic representations connect target functions to the additive operation naturally performed by wireless multiple access channels.Pre-processing functions transform device symbols, signal superposition forms inner sums, and post-processing produces the computed function.
  • I. INTRODUCTION: 2K + 1 wireless resources are required to represent every continuous function in C0(EK) with the stated set of nomographic functions.The result follows because the corresponding 2K + 1 nomographic functions cannot be reduced for representing every function in C0(EK).
  • I. INTRODUCTION: Approximate nomographic functions remain incompletely characterized, with multiple possible definitions including stochastic formulations.The cited approximation example uses logarithmic pre-processing and an exponential post-processing function for p0(ϵ) > 0.

B. Common nomographic functions

The literature applies common nomographic functions across distributed learning, physical-layer network coding, key generation, and wireless sensor networks. It also explores approximation and iterative optimization-based computation for functions that are not directly represented.

  • B. Common nomographic functions: Arithmetic mean, weighted sum, and MV are used in distributed learning, while modulo-2 sum appears in physical-layer network coding.The product operation is used for key generation, and maximum, minimum, and counting support wireless sensor network alerts or histograms.
  • B. Common nomographic functions: Approximate nomographic computation can use continuous monotone post-processing with continuous pre-processing through dimensionwise function decomposition.The target function is skewed with a bijective function before approximation using a first-order analysis of variance decomposition.
  • B. Common nomographic functions: Optimization-based computation expresses a target function as an iterative solution using elementary nomographic functions.The geometric median is computed over the air through iterations based on the Weiszfeld algorithm.

III. WHAT ARE THE OAC SCHEMES?

An OAC scheme maps local function inputs into encoded, precoded transmissions, combines them over a wireless multiple-access channel, and decodes the resulting superposition into function estimates.

  • General model: An OAC scheme targets a nomographic function of distributed symbol vectors and uses local preprocessing before encoding at each edge device.The target is z[n] = f(s[n]); each device forms pre-processed symbols with a local function and then encodes them.
  • General model: Each edge device maps modulation symbols onto available resources and applies linear precoders before transmitting across N_t dimensions.The resource mapper assigns B modulation symbols to B resources, while each device processes groups of L symbols with precoders B_k.
  • General model: The fusion node receives the power-weighted sum of channel-transformed transmissions plus noise, then applies a linear decoder to mitigate channel effects.The received vector is modeled as a sum of P_kH_kB_km_k terms and noise; A^H processes the superposition.
  • Receiver processing: After resource demapping, the receiver reconstructs a superposed codeword, decodes the pre-processed symbols, and applies post-processing to obtain target-function estimates.The decoder may combine constellation, channel, and source decoding, followed by a function ϕ that produces z[n].
  • Resource domains: The generalized model leaves transmission domains unspecified, allowing time, frequency, or spatial resources depending on the OAC method.The same framework can also compute multiple nomographic functions over orthogonal resources when required.

A. Metrics

OAC schemes are assessed by estimating function outputs and measuring their errors, with expectations taken over both source symbols and the wireless channel.

  • Error metrics: Function-estimation error measures the difference between the estimated function output and the target function value.The estimate is denoted f̂(s[n]) for the target f(s[n]).
  • Error metrics: Normalized FEE scales function-estimation error when function values lie within a specified range.The range is [f_min, f_max].
  • Error metrics: MSE, normalized MSE, Bayesian MSE, and mean-squared function error provide alternative average-error measures for computation.These metrics are defined for computation in the cited formulations.
  • Evaluation setting: The expectation in the error metrics is taken over both the input symbols and the wireless channel.This incorporates source and channel randomness into the assessment.

3) Outage probability:

This section defines outage, computation-error, computation-rate, and throughput metrics, then compares OAC with separated communication and computation for arithmetic sums.

  • Outage probability: Outage probability is the probability that normalized function-estimation error exceeds a threshold ϵ, providing a statistical view of computation error.A block outage probability is also defined for a given ϵ.
  • Error rates: Computation error rate is analogous to bit error rate and evaluates errors when function arguments are discrete; block computation error rate aggregates multiple functions.The metric uses discrete random variables s_k[n] and can account for N_f functions.
  • Computation rate and throughput: Computation rate counts functions computed per channel use, while computation throughput counts functions computed per second.Throughput depends on available dimensions and the interval used for computing functions.
  • Computation rate and throughput: For K = 100 edge devices, OAC promises approximately 10 times faster reliable arithmetic-sum computation than separated communication and computation at 15 dB SNR.The example uses IID Bernoulli inputs with probability 1/2; the separation rate is calculated from the cited AWGN expression.
  • Computation rate and throughput: OAC can achieve a nonvanishing computation rate as the network grows when selected devices with the largest channel gains progressively compute the target function over fast-fading channels.This strategy assumes IID channel coefficients and constructs the target through local functions.

B. Classification criteria: Availability of CSI

OAC methods are classified by channel-state information available at transmitters and receivers, with different strategies correcting channel amplitude, phase, or energy effects.

  • Classification criteria: Multipath distortion occurs before signal superposition, so channel-aware precoding and decoding are needed to estimate the computed function reliably.The survey classifies methods by how precoders B_k and decoder A address fading under CSIT and CSIR assumptions.
  • CSIT available, CSIR unavailable: With CSIT but no CSIR, each device uses its own channel knowledge to pre-distort transmissions without coordinating with other devices.The devices may design precoders under average or instantaneous transmit-power constraints.
  • Channel inversion: Truncated-channel inversion reverses channel coefficients above a threshold, aligning with zero-forcing while limiting problematic inversions.The symbol is multiplied by the inverse channel coefficient only when its squared magnitude exceeds threshold t.
  • Phase correction: Phase correction rotates transmitted symbols to create coherent superposition without power normalization, but it does not correct amplitude mismatch.Amplitude alignment may not be necessary for some applications, including federated edge learning.
  • Amplitude correction and energy estimation: Energy-based amplitude correction lets the receiver compute received-sequence energy, requiring only modulus channel state information and reducing sensitivity to time and phase synchronization errors.The method combines channel inversion, sequence processing, energy calculation, and affine post-processing.
  • Limitations: These methods require accurate CSIT, including stringent synchronization, channel-estimation, and channel-prediction mechanisms; extension to N_r > N_t is nontrivial.For N_r > N_t, random channel inversion cannot generally be achieved without interference; coordination is identified as a possible direction.

2) CSIT: Available, CSIR: Available:

With CSI available at both edge devices and the fusion node, OAC precoders and decoder can be jointly optimized, enabling flexible coordination strategies but imposing demanding practical requirements.

  • CSI at both the edge devices and fusion node enables joint design of the precoders B_k and decoder A.
  • ZF and MMSE coordinations: ZF coordination ignores fusion-node noise and designs channel inversion to preserve the desired superposition under transmit-power constraints.
  • ZF and MMSE coordinations: The maximum number of computable functions is L ≤ min{N, M}, with computation rate L/M when both symbol components are used.
  • Multi-antenna streams can compute L functions in parallel, increasing computation throughput, while related designs include beamforming, diversity, RIS, and advanced coordination techniques.
  • ZF and MMSE coordinations: MMSE coordination jointly balances maximum-power transmission and channel inversion while incorporating the fusion node’s noise variance.
  • What can go wrong?: These methods can be computationally demanding and depend strongly on accurate, fresh CSI and precise phase, time, and frequency synchronization.

3) CSIT: Not available, CSIR: Available:

When edge devices lack CSI but the fusion node has it, OAC methods mainly use channel hardening or advanced receivers to reduce channel-estimation demands, trading reliability, rate, or complexity.

  • This category assumes blind edge devices and a fusion node with CSI, relying particularly on channel-hardening techniques.
  • Channel hardening by using the aggregated CSI: Aggregated-CSI decoding reduces channel-estimation overhead, while uncoordinated transmissions introduce interference whose variance scales as (K − 1)/N_r.
  • Advanced receivers: Advanced receivers interpret digital OAC as multi-user detection and decode superposed codewords for convolutional, LDPC, and LoRa systems.
  • What can go wrong?: Channel hardening requires many receiver degrees of freedom, which can increase cost and reduce computation rate; advanced detection may become prohibitively complex for many devices.
  • Orthogonal signaling: Orthogonal signaling supports distributed training and related computations through FSK, PPM, CSK, and other synchronization-robust schemes.
  • Joint channel and parameter estimation: Joint channel and parameter estimation uses randomly initialized Wirtinger flow and achieves small estimation errors with sufficient samples.

C. Classification criteria: Encoding

OAC encoding methods are classified as analog or digital according to how pre-processed outputs are transformed before linear transmission, with coding choices trading bandwidth, reliability, and complexity.

  • Analog encoding processes continuous-valued symbols, whereas digital encoding applies quantization, compression, or source-channel coding.
  • Linear analog encoders: A linear analog encoder projects p_k into a lower-dimensional space, reducing resources while preserving the equivalence between summing projections and projecting sums.
  • Linear analog encoders: Linear encoders suit sparse or sparsifiable vectors; distributed-learning systems project sparsified gradients and recover their superposition using approximate message passing.
  • Linear analog encoders: Sparsification can deteriorate after aggregation, while device-selected sparsity patterns can improve test accuracy under heterogeneous data distributions.
  • Affine analog encoders: Affine encoders enforce non-negative outputs to remove receiver sign ambiguity, after which inverse processing recovers the desired superposed symbol.
  • Digital encoding: Digital encoding quantizes symbols, converts groups of integers into positional-numeral messages, and uses nested lattice codes so superposed messages can be decoded linearly.
  • Digital encoding: Choosing β = K(2^b0 − 1) + 1 prevents carry digits when messages from K devices are summed.
  • Digital encoding: After channel decoding, source decoding expresses each superposed message in base β to obtain sums of the quantization results.

IV. WHAT ARE THE ENABLING MECHANISMS FOR OAC?

The study’s enabling-mechanisms section addresses how reliable wireless computation is maintained and how security issues are handled.

  • The section discusses mechanisms for maintaining reliable computation and elaborates on security issues.

A. Synchronization

Synchronization offsets distort OAC signals in waveform- and scheme-dependent ways, affecting computation rate and MSE. The survey reviews these impairments and mitigation approaches, emphasizing that non-coherent methods can tolerate some timing and phase errors.

  • Timing errors translate signals and introduce additional phase rotation, while CFO causes phase-error accumulation that grows over time.
  • In OFDM-based OAC, CFO causes inter-carrier interference, TO causes subcarrier-index-scaled phase rotations, and residual PO causes subcarrier-independent distortion.
  • PO, TO, and CFO jointly affect computation rate and MSE, with sensitivity depending on the OAC scheme and target function.
  • Phase-synchronized analog aggregation requires precise sample-level synchronization because its MSE is sensitive to synchronization errors.
  • For MV computation using keying and non-coherent detection, maintaining synchronization within the CP range can suffice without increasing MSE.
  • Slowly varying offsets may be mitigated through control loops that estimate residual TO and PO and feed compensation values back to edge devices.

B. Power Management

Power management in OAC spans receiver-side alignment and transmitter-side PAPR and back-off constraints. The survey connects these choices to fairness, computation accuracy, receiver dynamic range, cell size, interference, and computation rate.

  • B. Power Management: Power management addresses receiver-side alignment at the ES and transmitter-side PAPR and output-power back-off.
  • B. Power Management: Perfect amplitude alignment can support fairness or accurate computation, but the worst channel condition may dominate computation performance.
  • B. Power Management: A large number of devices can push the superposed signal beyond the receiver’s dynamic range, motivating transmit-power reduction or adaptive gain control.
  • B. Power Management: Large PAPR can reduce cell size through power back-off, increase adjacent-channel interference through saturation, and shorten battery life.
  • B. Power Management: A smaller OBO_min increases r_max, while reducing OBO_min requires a more linear power amplifier or an OAC scheme with low instantaneous power fluctuations.
  • B. Power Management: Power back-off can reduce cell size and deteriorate computation performance because edge devices at large link distances provide weak signals.
  • C. Architecture: Coordinated multi-cell interference may be treated as harmful or harnessed for computation, alongside uplink, downlink, and hierarchical OAC architectures.

D. Channel Estimation

Reliable OAC depends on fresh and accurate CSI, while wireless superposition creates both privacy benefits and vulnerability to malicious or failed devices. The survey discusses CSI acquisition, Byzantine-resilient aggregation, and privacy mechanisms.

  • D. Channel Estimation: Inaccurate CSI can cause incoherent aggregation, while CSI aging from residual CFO or mobility increases overhead and limits functions computed in one packet.
  • D. Channel Estimation: Precoding-based OAC requires per-device uplink CSI, acquired through downlink signals or feedback, with calibration or overhead that increases latency.
  • D. Channel Estimation: Some methods instead acquire sum-channel CSI by iteratively optimizing edge-device and ES beamforming vectors using reference symbols and common pilots.
  • D. Channel Estimation: OAC superposition can promote privacy because individual transmitted signals are not directly observable, but it also exposes computation to Byzantine attacks.
  • D. Channel Estimation: Smoothed geometric-median aggregation uses a modified Weiszfeld algorithm to improve resilience against Byzantine attacks in OAC-based model aggregation.
  • D. Channel Estimation: The Byzantine-resilient procedure adds delay by running exclusively each FEEL communication round and assumes Byzantine users follow the proposed algorithm.
  • D. Channel Estimation: Random perturbations support differential privacy for OAC model parameters or gradients, creating an accuracy–privacy trade-off.

3) Eavesdropping:

OAC applications span secure aggregation, localization, wireless control, sensing, and distributed learning, while security and scalability remain important design concerns.

  • Eavesdropping: Weaker-channel sensors can act as jammers to protect computations from eavesdroppers in TBMA and FEEL.The approaches exploit channel differences or intentionally add jamming so legitimate reception is less degraded than eavesdropping.
  • Distributed localization: In OFDM-based localization, sensors vote by activating subcarriers for grid squares consistent with their RSSI-estimated source distance.The fusion node detects the largest-magnitude subcarrier after simultaneous transmission to determine the source location.
  • Wireless control systems: OAC supports wireless control by recovering distributed plant states and computing vehicle-position averages for control actions.The surveyed control applications target many sensors and limited wireless resources, including dynamic-plant stabilization and vehicle platooning.
  • Federated learning: For FEEL, OAC reduces each iteration’s communication cost to that of a single edge device despite aggregating functions across many devices.With separate communication and computation, orthogonal access transfers N_fK parameters and latency grows linearly with K; OAC enables simultaneous transmission.
  • Federated learning: Byzantine attacks can make FEEL unreliable because the fusion server does not directly observe gradients or model parameters.Data poisoning, model poisoning, and node failures are identified as application-specific challenges for OAC-based federated learning.

2) Split learning:

The surveyed applications include split learning, neural-network and graph-based computation, wired-network replacement, network coding, overhead reduction, sensing, and security.

  • Split learning: Split learning can aggregate smashed data over wireless links, moving weighted multiplication to edge devices while retaining bias addition and activation at the server.The cited OAC implementation uses channel inversion and excludes users with deeply faded channels.
  • Neural-network applications: OAC is used in graph neural networks and message-passing networks to improve computation rate, privacy, or decentralized power allocation.The examples apply OAC to graph aggregation and device-to-device power allocation with channel inversion.
  • Future directions: Open research areas include applying OAC to additional statistical methods such as independent component analysis, k-means, and k-SVD.The passage characterizes these explorations as currently open topics.
  • Networked computing: OAC can compute arithmetic means in wireless data-center networks to address flexibility, cabling complexity, device cost, and scalability limitations of wired interconnects.Other applications include hyperdimensional-computing similarity search across in-memory-computing cores using wireless bit-wise majority voting.
  • Wireless communications: Physical-layer network coding and compute-and-forward use signal collisions or superposition to convey functions of messages through relay networks.Two-way relay examples compute XOR functions, while practical variants address synchronization, power-control, and reliability issues.
  • Overhead reduction: OAC can reduce CSI-feedback overhead by computing a receive beamforming vector through concurrent transmissions.One cited result reports 50-times-greater overhead reduction than conventional training.

I. Demonstrations

The survey reviews practical OAC demonstrations, schemes, enabling mechanisms, and research directions, emphasizing reliable function computation over wireless channels and its potential to improve computation rate.

  • Demonstrations: Early OAC demonstrations primarily target wireless sensor networks and physical-layer network coding, including RFID and software-defined-radio implementations.One implementation used twenty-one RFID tags with a trigger signal for time synchronization; another used three SDRs emulating eleven sensor nodes and a fusion center.
  • Demonstrations: FEEL demonstrations remain limited but include protocols and OFDM-based schemes designed to mitigate timing offset and carrier-frequency offset.Recent work also investigates synchronization methods that let SDRs transmit or receive in-phase/quadrature data simultaneously.
  • Encoding strategies: OAC schemes use either continuous-valued parameters with analog modulation or quantized parameters with digital modulation, including linear or affine compression and nested-lattice codes.Analog compression is effective under properties such as sparsity, whereas digital OAC commonly uses nested-lattice codes for reliable computation.
  • Evaluation: The survey evaluates OAC using computation-oriented metrics such as mean squared error, function error probability, and computation rate rather than only traditional communication metrics.These metrics reflect whether the intended function is computed accurately, especially when digital functions have discrete-valued outputs.
  • Enabling mechanisms: Reliable OAC requires synchronized simultaneous transmissions, power management, and channel estimation or feedback, with some schemes imposing sample-level timing and residual-CFO requirements.Methods avoiding phase synchronization can reduce some requirements, while practical wireless channels still distort transmitted symbols before superposition.
  • Research directions: State-of-the-art results indicate that OAC can address latency issues by improving computation rate, while practical deployment still requires stronger evaluation and supporting protocols.The survey identifies practical limitations, OAC-aware algorithms, and standards-oriented protocols as major directions for further work.
Loading 2210.11350v5…