Over-the-Air Computation via Broadband Channels

During the past few years, over-the-air computation (AirComp) has emerged as a low-latency solution for large-scale wireless data fusion in many applications including Internet of Things [1, 2, 3, 4, 5, 6], wireless distributed machine learning [7, 8, 9], and over-the-air consensus [10]. Normally, an AirComp system consists of multiple sensors and a fusion center computing the sum of the sensor measurements. Multiple sensors send their measurement-carrying signals simultaneously to the fusion center over a multiple-access channel (MAC). The fusion center receives the superimposed signal of multiple sensors, and then estimates the sum of the sensors’ measurements (see e.g. [2] for more details).

Many existing research focuses on optimal transmitter and receiver policy design of AirComp systems for achieving the minimum computation mean-square error (MSE) of the sum sensor signals [1, 2, 3, 4, 5, 6]. In [1], the computation MSE under imperfect channel state information was investigated. In [2] and [3], the optimal transmitter (Tx) and receiver (Rx) scaling factor design of a single-antenna AirComp system under individual and sum power constraints were obtained, respectively. In particular, a comprehensive comparison study of the AirComp design problem and the conventional minimum mean-square error (MMSE) problem was included in [2], showing that the problem solutions are different. In [4], the optimal AirComp design with spatial and temporal correlated sensor signals was investigated. In [5] and [6], the transmitting and receiving beamforming design problems of multi-antenna AirComp systems were considered.

In addition to  [1, 2, 3, 4, 5, 6] that considers AirComp design over a single frequency channel, recently a broadband AirComp system with $M$ frequency channels was proposed in [9] for distributed machine learning, where $M$ AirComp tasks were performed over $M$ frequency channels separately. In other words, each frequency channel is dedicated to one AirComp task, which is the same as the single-frequency AirComp in [1, 2, 3, 4, 5, 6]. For a large-scale sensor network, the performance of AirComp over a single frequency is quite limited as many sensors may have poor conditions in that channel. Thus, it is desirable to provide more frequency channels for large-scale AirComp systems to benefit from channel diversity.

In this work, we consider an $M$-frequency AirComp system and investigate the optimal Tx and Rx policy design. Compared with the conventional single-frequency scenario, one needs to 1) determine the sensors’ transmission policy at the $M$-frequency channel to optimally utilize the channel diversity for signal aggregation, noting that each sensor has access to any subset of the $M$ frequencies; and 2) design the fusion center’s policy to optimally recover the sum of the sensor signals based on the output of the $M$-frequency channel. The system introduces an additional dimension for design compared to the single-frequency one and thus imposes the challenge. To the best of our knowledge, such a problem has not been discussed in the open literature of AirComp. The main contributions are summarized as follows.

• •

  We propose an $M$-frequency AirComp system, where each sensor decides to send its signal over a subset of the $M$ frequencies under a certain power constraint. The fusion center receives aggregated sensor signals at the parallel channels and then estimates the sum of the sensor signals.

• •

  We formulate the computation MSE minimization problem of the $M$-frequency AirComp system, separately derive the optimal Tx and Rx policies in a closed-form, and adopt an alternating minimization approach for joint design. Our numerical results show that in the high-SNR scenario, the optimized two-frequency AirComp system can reduce the computation MSE to $1/3$ compared to the single-frequency case.

• •

  After investigating the structure of the optimization problem, we obtain the property of the optimal AirComp system where the received sensor signals should be aligned onto a one-dimensional signal space at each complex (two-dimensional) frequency channel. By leveraging the property, we significantly reduce the computation complex of optimization. Furthermore, our analysis show that the real number operation based fusion center performs better than the complex number operation based one in AirComp, though the latter is commonly adopted in the literature [2, 3, 5, 6].

Notations: $\mathbb{R}$ and $\mathbb{C}$ denotes the set of real and complex numbers, respectively. $|\textbf{x}|$ denotes the Euclidean norm of vector x. $\mathsf{E}{\left[\cdot\right]}$ is the expectation operation. $\mathsf{Re}\{x\}$ and $\mathsf{Im}\{x\}$ are the real and imaginary parts of the scalar $x$.

We focus on a single-antenna AirComp system consisting of $K$ sensors, $M$ frequency channels (sub-carriers) and a fusion center (FC) as shown in Fig. 1, where $K\gg M$. The channel coefficient between sensor $k$ and the FC at frequency $m$ is $h_{km}\in\mathbb{C}$.²²2Note that the signaling cost for channel estimation grows linearly with the increasing number of frequencies. Sensor $k$’s measurement signal is $x_{k}\in\mathbb{R},\forall k\in\mathcal{K}$, where $\mathcal{K}\triangleq\{1,2,\dots,K\}$. It is assumed that $x_{k}$ has zero mean and normalized variance [2, 3, 4, 5].³³3Note that our AirComp framework of the scenario with zero-mean-normalized-variance sensor measurements can be applied to a generalized scenario with non-zero mean and non-normalized variance. Assume that sensor measurement ${x}_{k}$ has mean $\mu$ and variance $\delta^{2},\forall k\in\mathcal{K}$. The normalized measurement is $\bar{x}_{k}=\frac{x_{k}-\mu}{\delta},\forall k\in\mathcal{K}$, and is sent to the fusion center based on the AirComp protocol. Then, it is easy to have $\sum_{k=1}^{K}x_{k}=\delta\sum_{k=1}^{K}\bar{x}_{k}+K\mu.$ Since $\delta$, $\mu$ and $K$ are constant, the optimal estimation of $\sum_{k=1}^{K}x_{k}$ can be obtained by the optimal estimation of $\sum_{k=1}^{K}\bar{x}_{k}$ in the mean-square sense. Thus, in the following, we only consider the scenario with zero mean and normalized variance.

In the multi-frequency AirComp system, each sensor can simultaneously broadcast its measurement via the $M$ frequency channels under a certain power constraint, and the FC estimates the sum signal $\sum_{k=1}^{K}x_{k}$ based on the received aggregated signal at the $M$ frequencies. Let $b_{km}\in\mathbb{C}$ and $b_{km}x_{k}$ denote the Tx scaling factor and the transmitted signal of sensor $k$ at frequency $m$, respectively. Certainly, $b_{km}=0$ indicates that sensor $k$ does not select frequency $m$ for AirComp. Assuming an average sensor power constraint $P$, we have

The FC’s received signal is

where $n_{m}\in\mathcal{CN}(0,\sigma^{2})$ is the additive complex white Gaussian noise at frequency $m$.

As we consider complex channels, $r_{m}$ can be denoted as a two dimensional real vector $\textbf{r}_{m}\in\mathbb{R}^{2}$, and thus the FC receives $2\times M$ real signals in total. Then, (2) is rewritten as

where

Note that $\mathsf{Re}\{n_{m}\}$ and $\mathsf{Re}\{n_{m}\}$ are real zero-mean Gaussian signals with variance $\sigma^{2}/2$.

Let $\textbf{g}_{m}\in\mathbb{R}^{2}$ denote the Rx scaling factor at frequency $m$. The linear computation output of the FC is

and the computation MSE of the AirComp system is [5]

We note that a smaller $\mathsf{CMSE}$ indicates a better computation accuracy. Substituting (3) into (5) and then into (6), we have

After some mathematical manipulations, (7) can be simplified as

where 1 is a length-$K$ all-ones vector, $\textbf{g}^{\top}\triangleq\left[\textbf{g}_{1}^{\top}\ \textbf{g}_{2}^{\top}\ \dots\ \textbf{g}_{M}^{\top}\right]\in\mathbb{R}^{2M}$, and

From (8) and (1), the AirComp optimization problem is formulated as

It is clear that the objective function of (10) is non-convex due to the coupling of the Rx and Tx scaling factors g and $\{\textbf{b}_{km}\}$, and there is no general approach to find the joint optimal solution. In what follows, we will separately derive the optimal Rx and Tx scaling factors, and then adopt an alternating minimization approach for joint design.

It is easy to prove that problem (10) is bi-convex in terms of g and $\{\textbf{b}_{km}\}$. So we can alternately solve (10) for $\{\textbf{b}_{km}\}$ and g, respectively, while fixing the other, and then iterate until the convergence. From [11] and references therein, the alternating minimization algorithm provides low-complexity solution of bi-convex problems. We will evaluate the effectiveness of the algorithm in solving the AirComp optimal design problem in Section V. In the following, we will derive the optimal solution of the Rx and Tx scaling factors, respectively.

In the previous section, an alternating minimization algorithm has been proposed to solve the AirComp design problem (10) over multiple frequencies. Next, we will further investigate the property of the objective function of (10) to reduce its computation complexity.

First, using the Cauchy–Schwarz inequality, we have

where the equality holds once the angle between vectors $\textbf{g}_{m}$ and $\textbf{H}_{km}\textbf{b}_{km}$ is zero. From the definition of $\textbf{H}_{km}$ in (4), it is easy to show that the angle of vector $\textbf{H}_{km}\textbf{b}_{km}$ can be any value by properly designing $\textbf{b}_{km}$ without changing its norm. So the equality (25) can hold for any given $\textbf{g}_{m}$ and $|\textbf{b}_{km}|$.

Second, observing the design target function (7) and using the inequality (25), we have the inequality below with the same power constraint on $\textbf{b}_{k}$:

This is because the optimal design of the right hand side and the left hand side of (26) in terms of $\{\textbf{b}_{km}\}$ satisfy $\sum_{m=1}^{M}\textbf{g}_{m}^{\top}\textbf{H}_{km}\textbf{b}_{km}-1<0$ and $\sum_{m=1}^{M}|\textbf{g}_{m}||\textbf{H}_{km}\textbf{b}_{km}|-1<0$, respectively. Otherwise, one can always find smaller $\{|\textbf{b}_{km}|\}$ leading to smaller target functions in (26). Then, from the discussions under (25), the equality in (26) holds if we design $\textbf{b}_{km}$ such that the angle between vectors $\textbf{g}_{m}$ and $\textbf{H}_{km}\textbf{b}_{km}$ is zero.

Last, taking (26) into (7), the target function of problem (10) is equivalent to

which depends on the norms of vectors $\textbf{g}_{m}$ and $\{\textbf{H}_{km}\textbf{b}_{km}\}$ instead of the angles. Thus, without loss of optimality, it is safe to assume that the second elements of $\textbf{g}_{m}$ and $\textbf{H}_{km}\textbf{b}_{km}$ are zero, i.e.,

In other words, only the real part of the received signal carries information in each frequency channel. Therefore, in problem (10), by removing these zero elements, the sizes of g and S are reduced to half, which significantly reduces the computation complexity. Based on the computational complexity of matrix operations [14], it is easy to obtain that the computational complexity of the optimized Rx and Tx scaling factors in Propositions 1 and 2 are $\textit{O}(M^{2}K)$ and $\textit{O}(M^{3})$, respectively.

In this section, we numerically evaluate the computation MSE of the $K$-sensor-$M$-frequency AirComp system with different $K$, $M$ and power constraint $P$, where the Rx and Tx scaling factors are obtained by the low-complexity alternating minimization algorithm in Sections III and IV with $20$ iteration rounds. Note that our experiment results (not included due to the space limitation) show that the algorithm usually converges within 20 iteration rounds under a CMSE tolerance level of $10^{-3}$. Unless otherwise stated, we set $P=10$, the noise power $\sigma^{2}=1$ [2, 3], the number of sensors $K=50$. We adopt normalized Rayleigh fading channels for evaluating the computation MSE that averages over $10^{5}$ random channel realizations.

In Fig. 2, we demonstrate the effectiveness of the proposed alternating minimization method. Although the optimal joint Rx and Tx scaling factor design for a general $M$-frequency AirComp is unknown, the optimal single-frequency AirComp has been well investigated in [2]. We compare the AirComp performance achieved by the proposed algorithm and the benchmark optimal algorithm [2] for the single-frequency case with different $P$ and $K$. We see that the proposed algorithm achieves exactly the optimal performance.

In Fig. 3, we plot $\mathsf{CMSE}$ with different number of frequency channels $M$. We see that $\mathsf{CMSE}$ decreases with the increasing $M$ due to the increasing chance of having good channels for AirComp. It is interesting to see that when the transmit power is high (e.g., $P=10$), increasing $M$ cannot reduce much $\mathsf{CMSE}$ when $M>5$; while for the lower power scenario (e.g., $P=1$), increasing frequency channels is a good way to improve the AirComp performance. In particular, when $P=10$, the optimized two-frequency AirComp system can reduce the computation MSE by $2/3$ compared to the conventional single-frequency case. We also present $\mathsf{CMSE}$ of two baseline policies: 1) the Rx scaling factors are fixed and are equal to one, and the Tx scaling factors are obtained by Proposition 2; 2) the Tx scaling factors are fixed and unified, i.e., the transmit power of sensor $k$ at frequency $m$ is equal to ${P/M},\forall k\in\mathcal{K},m\in\mathcal{M}$, and the Rx scaling factors are obtained by Proposition 1. It is clear that the proposed alternating minimization method provides significant performance gain compared to the the baseline policies. In particular, baseline 1 leads to an increased CMSE when more frequencies are available, showing the importance of Rx scaling factor design.

In Fig. 4, we plot the optimized Tx scaling factors $\{|{b}_{km}|\}$ and the randomly generated channel coefficients $\{|h_{km}|\}$ at different frequencies for sensors 1 and 2 in sub-figures (1) and (2), respectively, with $M=5$, and in sub-figures (3) and (4) with $M=20$. We see that for sensor 1, a larger channel coefficient leads to a higher Tx scaling factor in some frequencies, but it does not holds for some other cases. This is because as stated in Proposition 2, the optimized Tx scaling factors for one sensor depends on both its channel coefficients and the Rx scaling factors. Thus, the Tx scaling factors are not proportional to the channel coefficients. Comparing sub-figures (3) and (4) with (1) and (2), it is interesting to see that in the case with a large number of frequencies (e.g., $M=20$), only half of the frequencies are utilized for AirComp as the allocated transmit power is zero in the other frequencies. It is because that the optimized AirComp system smartly chooses a subset of good channels for signal aggregation, instead of allocating transmit power to all frequency channels and suffering from more noise in a broader bandwidth.

We have proposed a novel $M$-frequency AirComp system, where each sensor broadcasts its signal over any a subset of the frequencies under a certain power constraint. We have derived the optimal Tx and Rx scaling factors separately in closed-form, adopted an alternating minimization approach for joint design, and further reduced the complexity of the design problem to half of it. The numerical results have shown that in the high-SNR scenario, the optimized two-frequency AirComp system can reduce the computation MSE by $2/3$ compared to the conventional single-frequency case. For future work, we will take into account the sensor signal correlation and the channel correlation at different frequencies, and study the optimal AirComp policy.