On Designing Modulation for Over-the-Air Computation — Part II: Pyramid Sampling

Over-the-air computation (OAC) harnesses the natural superposition of wireless signals to compute aggregate functions during transmission, thereby collapsing communication and computation into a single step and significantly reducing latency and resource usage. In Part I, digital OAC was formulated as a noise-aware constellation design problem by casting encoder design as a max–min optimization that aligns minimum Euclidean distances between superimposed constellation points with squared differences of their corresponding function outputs. In this paper, Part II, we address the prohibitive complexity and quantization challenges inherent in digital OAC constellation design for large-scale edge networks. More precisely, we introduce a pyramid sampling strategy that selects a subset of superimposed constellation points to reduce constellation-design complexity by decreasing the worst-case number of pairwise constraints from $\mathcal{O}(q^{2K})$ to $\mathcal{O}(q^{2K/p})$, where $p\in\{1,\dots,K\}$ denotes the sampling order, $q$ denotes the number of modulation levels, and $K$ denotes the number of nodes in the network. Under the assumption of symmetric aggregation, this approach enables a controlled trade-off between computational complexity and function computation accuracy. As a special case, we propose majority-based sampling ($p = K$), which retains $q$ sampled histograms whose received constellation points are distinct for distinct transmitted symbols. This sampling scheme allows us to use standard digital modulations, such as QAM, PSK, and ASK, for the sampled constellation. We also show via several simulations, across various aggregation functions, modulation levels, and noise levels, that moderate sampling orders attain acceptable performance with orders-of-magnitude fewer constraints than exhaustive designs.