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 judiciously selects a subset of superimposed constellation points to reduce the encoder design complexity from O(qK) to O(qK-p+1), where p∈1,dots, K denotes the sampling order, q levels of modulation, and K denotes the number 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 confines aggregation to only q consensus points, inherently avoiding destructive overlaps and permitting the use of standard digital modulations (e.g., QAM, PSK, ASK) without bespoke constellation designs. 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.