Reliable Over-the-Air Computation by Amplify-and-Forward Based Relay

We first introduce the basic AirComp model [9]. A sensor network is composed of $K$ sensor nodes and 1 sink. The sensing result at the $k_{th}$ node is represented by the signal $x_{k}\in[-v,v]\in\mathbb{C}$, which has zero mean and unit variance ($E(|x_{k}^{2}|)=1$). The sink will compute the sum of sensing data from all nodes. Both the nodes and the sink have a single antenna. To overcome channel fading, the $k_{th}$ node pre-amplifies its signal by a Tx-scaling factor $b_{k}\in\mathbb{C}$. The channel coefficient between sensor $k$ and the sink is $h_{k}\in\mathbb{C}$. The sink further applies a Rx-scaling factor $a\in\mathbb{C}$ to the received signal, as follows

where $n\in\mathbb{C}$ is the additive white Gaussian noise (AWGN) at the sink with zero mean and power being $\sigma^{2}$. It is assumed that channel coefficient $h_{k}$ is known by both node $k$ and the sink. Then, in a centralized way, the sink can always adjust $b_{k}$ to ensure that $h_{k}b_{k}$ is real and positive. Therefore, in the following, it is assumed that $h_{k}\in\mathbb{R^{+}}$, $b_{k}\in\mathbb{R^{+}}$, and $a\in\mathbb{\mathbb{R^{+}}}$ for the simplicity of analysis.

The computation error is defined as the mean squared error (MSE) between the received signal sum $s$ and the target signal $\sum_{k=1}^{K}x_{k}$, as follows (by using the facts that signals are independent of each other and independent of noise, $E(x_{k})=0$, $E(|x_{k}^{2}|)=1$)

With the maximal power constraint, $|b_{k}x_{k}|^{2}$ should be no more than $P^{\prime}$, the maximal power. Let $P_{max}$ denote $P^{\prime}/v^{2}$. Then, we have $b_{k}^{2}\leq P^{\prime}/v^{2}=P_{max}$. By sorting the channel coefficient ($h_{k}$) in the increasing order, the optimal solution (under the power constraint $|b_{k}|^{2}\leq P_{max},k=1,\cdots,K$) depends on a critical number, $i^{\star}$ [9]. A node whose index is below $i^{\star}$ uses the maximal power $P_{max}$, and otherwise uses a power inversely proportional to the channel gain. Then, the computation MSE is computed as follows:

This computation MSE may be caused by channel fading or noise. The former decides the error in the signal magnitude of $i^{\star}$ weak signals and the latter decides the term $\sigma^{2}|a|^{2}$.

When some nodes are far away from the sink, the magnitudes of their signals cannot be aligned with that of other signals from nearer nodes. Some efforts have been devoted to solving this problem. The work in [9] studies the power control policy, aiming to minimize the computation error by jointly optimizing the transmission power and a receive scaling factor at the sink node. Generally, the principle of channel inversion is adopted. Specifically, with the common signal magnitude being $\alpha$ ($\alpha=1/a$), the transmission power of node $k$ is computed as $b_{k}=min\{\alpha/h_{k},\sqrt{P_{max}}\}$, being the former if $\alpha/h_{k}$ is below the power constraint, and otherwise, using the maximal power. In [10], the authors further consider the time-varying channel by regularized channel inversion, aiming at a better tradeoff between the signal-magnitude alignment and noise suppression. Antenna array was also investigated in [19, 20] to support vector-valued AirComp.

AirComp is an efficient solution in federated learning, where the model update is to be transmitted from each node to the common sink, aggregated there, and then sent back to each node for future data processing. Specific consideration on AirComp is also studied. Because information from some of the nodes is sufficient, node selection based on the channel gain is suggested in [21], although this does not apply to general AirComp where signals from all nodes are needed. Sery et al. further suggests precoding and scaling operations to gradually mitigate the effect of the noisy channel so as to facilitate the convergence of the learning process [22].

The network consists of $K$ sensor nodes, a relay $r$ and a sink $d$. Sink $d$ will compute the sum of sensing data from all nodes, via the help of relay $r$. All nodes, relay $r$ and sink $d$ use a single antenna. Each node has a constraint of the maximal transmission power. But we assume that the relay has no constraint of transmission power, and investigate how much power is required for relaying signals. Nodes near to the sink can directly communicate with the sink, while nodes farther away can rely on the relay to help. Then, all nodes are divided into two groups. A node $k$ is either a neighbor of $r$ ($k\in N_{r}$) and will use relay $r$, or a non-neighbor of $r$ ($k\in N_{d}$) and will directly transmit its signal to sink $d$. Fig.1 shows an analogy to a conventional relay network. The difference is that there are more than one node in $N_{r}$ and $N_{d}$.

We assume that (i) the sensor network is fixed without node mobility, and channel coefficients ($h_{k,r}\in\mathbb{C}$ and $h_{k,d}\in\mathbb{C}$, representing channel coefficients from node $k$ to relay $r$ and sink $d$, respectively) are constant within a period of time, (ii) each node (and relay $r$) knows channel coefficients of its links to sink $d$ and relay $r$, and (iii) channel coefficients of all links are known to sink $d$¹¹1It is common to assume that the sink knows the CSI of node-relay links and node-sink links in the AF-based relay control [11] and the IRS-based relay control [18]. , which decides the node grouping policy (decides which nodes to use the relay) and other parameters.

Similar to the conventional AF method, the whole transmission is divided into two slots. But the transmission powers (Tx-scaling factor $b_{k,1}\in\mathbb{C}$ and $b_{k,2}\in\mathbb{C}$ in two time slots) are adjusted per node per slot. The detailed process is shown in Fig.2.

In the first slot, a neighbor node ($k\in N_{r}$) of relay $r$ transmits its signal using a Tx-scaling factor $b_{k,1}$. The signals received at relay $r$ and sink $d$ are

where $a_{r,1}\in\mathbb{C}$ and $a_{d,1}\in\mathbb{C}$ are Rx-scaling factors, and $n_{r,1}$ and $n_{d,1}$ are AWGN noises with zero mean and variance being $\sigma^{2}$.

In the second slot, all nodes transmit their signals to sink $d$, and node $k$ uses a Tx-scaling factor $b_{k,2}$. Meanwhile relay $r$ also forwards its received signal, using a Tx-scaling factor $b_{r,2}$. Signals arriving at sink $d$ are composed of 3 parts, as follows:

where $s^{\prime}_{d,2}$ is the signal from $k\in N_{r}$, $s^{\prime\prime}_{d,2}$ is the signal from $k\in N_{d}$, and $s^{\prime\prime\prime}_{d,2}$ is the relayed signal. Then, the overall signal at the second slot is

where $a_{d,2}\in\mathbb{C}$ is a Rx-scaling factor, and $n_{d,2}$ is AWGN noise with zero mean and variance being $\sigma^{2}$.

Sink $d$ adds the signals received in the two slots. For a signal from a neighbor ($k\in N_{r}$) of relay $r$, its overall coefficient at the sink is

Its first term corresponds to the signal directly received in the first slot, its second term corresponds to the signal directly received in the second slot, and its third term corresponds to the relayed signal.

For a signal from a node not a neighbor ( $k\in N_{d}$) of relay $r$, its coefficient at sink $d$ is

The overall noise is

All the parameters are to be solved by minimizing the following computation MSE (under the power constraint $|b_{k,1}|^{2}\leq P_{max},|b_{k,2}|^{2}\leq P_{max},k=1,\cdots,K$).

It is difficult to directly solve this problem. In the following, we discuss its solution under several relay policies.

Different from a conventional relay method, relay $r$ has to amplify $|N_{r}|$ signals, and the overall signal to be relayed is

To ensure that all signals are aligned in magnitude at sink $d$, the magnitude of the relayed signals ($a_{d,2}h_{r,d}b_{r,2}\cdot a_{r,1}h_{k,r}b_{k,1}$, $k\in N_{r}$) should approach that of directly received signals ($a_{d,2}h_{k,d}b_{k,2}$, $k\in N_{d}$). Here, relay $r$ will use a Tx-scaling factor $b_{r,2}$ which depends on node transmission power ($b_{k,1}$), channel gains ($h_{r,d}$, $h_{k,r}$), and alignment with other nodes ($a_{d,2}$, $a_{r,1}$). The transmission power required at the relay node is

Obviously, the relay transmission power linearly increases with the number of nodes using the relay, which is a big problem. Therefore, it is impractical to use relay for all nodes.

To solve this problem, we propose that nodes far away from sink $d$ while near to relay $r$ should use the relay. Therefore, nodes are sorted in the ascending order of $|h_{k,d}|^{2}-|h_{k,r}|^{2}$, the difference of channel gain to sink $d$ and relay $r$. The top nodes will use relay $r$, and the percentage of nodes using relay $r$ is a parameter.

We first consider a simple relay (SimRelay) policy. $s_{d,1}$ is neglected ($a_{d,1}=0$) and $s^{\prime}_{d,2}$ is not transmitted ($b_{k,2}=0,k\in N_{r}$). In other words, in the first slot, signals from $k\in N_{r}$ are sent to relay $r$, and in the second slot, signals from $k\in N_{d}$ are directly sent to sink $d$ and signals from $k\in N_{r}$ are forwarded to sink $d$ by relay $r$. This is the most simple relay method: the direct link is neglected once the relay is used.

With $a_{d,1}=0$, $b_{k,2}=0$ ($k\in N_{r}$), and $a_{d,2}h_{r,d}b_{r,2}=c$, the computation MSE in Eq.(13) can be rewritten as

Because $c$ can be merged into $a_{r,1}$, we denote their product as $a^{\prime}_{r,1}=ca_{r,1}$, and the computation MSE can be computed as the sum of

Because $MSE_{r}$ and $MSE_{d}$ depend on different nodes and different parameters, the relay problem is equivalent to two AirComp problems, one from $k\in N_{r}$ to relay $r$ in the first slot, and the other from $k\in N_{d}$ to sink $d$ in the second slot. Each can be solved by using the power control algorithm suggested in [9]. Because $b_{k,1}$ and $b_{k,2}$ can be adjusted to ensure $h_{k,r}b_{k,1}$ and $h_{k,d}b_{k,2}$ are positive real numbers, in the analysis, $h_{k,r}\in\mathbb{R^{+}}$, $h_{k,d}\in\mathbb{R^{+}}$, $b_{k,1}\in\mathbb{R^{+}}$, $b_{k,2}\in\mathbb{R^{+}}$, $a^{\prime}_{r,1}\in\mathbb{R^{+}}$, $a_{d,2}\in\mathbb{R^{+}}$ are assumed for the simplicity of analysis.

In SimRelay, relay $r$ has to amplify the whole signals from $|N_{r}|$ nodes, which requires much transmission power.

To reduce relay transmission power, we consider a coherent relay (CohRelay) policy. A node using relay divides its power into two parts, and transmits its signal twice. Sink $d$ receives two coherent copies of the same signal and adds them together.

In this case, $s_{d,1}$ is neglected ($a_{d,1}=0$) but $s^{\prime}_{d,2}$ ($k\in N_{r}$) is transmitted. Compared with SimRelay, the difference is that in the second slot, nodes $k\in N_{r}$ transmit their signals again. With $a_{d,1}=0$, $a_{d,2}h_{r,d}b_{r,2}=c$, and $a^{\prime}_{r,1}=ca_{r,1}$, the computation MSE in Eq.(13) can be rewritten as

Because $a_{d,2}$ also appears in the first sum, this cannot be simply divided into two AirComp problems like SimRelay. But $h_{k,r}\in\mathbb{R^{+}}$, $h_{k,d}\in\mathbb{R^{+}}$, $b_{k,1}\in\mathbb{R^{+}}$, $b_{k,2}\in\mathbb{R^{+}}$, $a^{\prime}_{r,1}\in\mathbb{R^{+}}$, $a_{d,2}\in\mathbb{R^{+}}$ can be assumed in the analysis. Then, $a_{d,2}h_{k,d}b_{k,2}$ in the first sum is a positive real number. Without this term, like SimRelay, an initial estimation of $a^{\prime}_{r,1}$ and $a_{d,2}$ can be computed, by minimizing $MSE_{r}$ and $MSE_{d}$ in Eq.(17), respectively.

Next consider the presence of $a_{d,2}h_{k,d}b_{k,2}$ in the first sum of Eq.(18). Assume originally some $a^{\prime}_{r,1}$ and $b_{k,1}$ make $a^{\prime}_{r,1}h_{k,r}b_{k,1}$ equal to 1.0 (or approach 1 under the maximal power constraint). If $b_{k,1}$ is fixed, the presence of $a_{d,2}h_{k,d}b_{k,2}$ (a positive number) makes it possible to use a smaller $a^{\prime}_{r,1}$ to make $a_{d,2}h_{k,d}b_{k,2}+a^{\prime}_{r,1}h_{k,r}b_{k,1}$ reach 1.0. Meanwhile, the term $\sigma^{2}|a^{\prime}_{r,1}|^{2}$ also decreases. In other words, it is possible to decrease $a^{\prime}_{r,1}$ in a certain range to reduce the first sum in Eq.(18). Therefore, a heuristic algorithm is to use the initial estimation of $a^{\prime}_{r,1}$ as a seed, and then gradually decrease it to find the minimum while fixing $a_{d,2}$ (ensuring the minimum of the second sum in Eq.(18)).

Actually, $b_{k,1}$ and $b_{k,2}$ depend on the setting of $a^{\prime}_{r,1}$ and $a_{d,2}$. In addition, to ensure a fair comparison with SimRelay, it is assumed that the overall power, $|b_{k,1}|^{2}+|b_{k,2}|^{2}=P$, should be no more than $P_{max}$. Then, the power allocation for $b_{k,1}$ and $b_{k,2}$ ($k\in N_{r}$) is to maximize the term $a_{d,2}h_{k,d}b_{k,2}+a^{\prime}_{r,1}h_{k,r}b_{k,1}$, under the power constraint. According to the Cauchy–Schwarz inequality [23]

and the equality holds if and only if

Then, with $|b_{k,1}|^{2}+|b_{k,2}|^{2}=P\leq P_{max}$, $\rho_{k}$ can be computed as

On this basis, $b_{k,1}$ and $b_{k,2}$ are computed from Eq.(20), and the value of $a_{d,2}h_{k,d}b_{k,2}+a^{\prime}_{r,1}h_{k,r}b_{k,1}$ is computed as

If $\gamma_{k}(P_{max})$ is greater than 1.0, setting $\gamma_{k}(P)=1$ can find $\rho_{k}(P)$ and the powers ($b_{k,1}$ and $b_{k,2}$) that lead to 0 error in the signal magnitude.

The whole process of finding optimal parameters and the corresponding computation MSE is described in Algorithm 1.

In CohRelay, $a_{d,2}h_{k,d}b_{k,2}+a^{\prime}_{r,1}h_{k,r}b_{k,1}\approx 1$ so $a^{\prime}_{r,1}h_{k,r}b_{k,1}$ is less than 1. This helps to reduce the relay transmission power in Eq.15.

Here, we evaluate the relay methods discussed in the previous sections, by comparing them with the AirComp method [9] that only exploits the direct link.

Figure 3 shows the simulation scenario. 50 sensor nodes are randomly and uniformly distributed in a rectangle area. The path loss model uses a hybrid free-space/two-ray model and each link experiences independent slow Rayleigh fading (channel gains are the same in two slots). We assume that the link $rd$ does not experience fading by properly selecting a relay node not in fading (the relay selection itself is left as future work). The noise level is -90dBm. It is assumed that both sink $d$ and relay $r$ amplifies the signal with a gain of 90dB. The simulation is run 10,000 times using the Matlab software. Main parameters are listed in Table I.

Figure 4 shows the cumulative distribution functions (CDF) of computation MSE, average node transmission power and relay transmission power in different methods. Obviously, AirComp using only direct links has much larger computation MSE than relay methods. SimRelay and CohRelay have almost the same performance in reducing the computation MSE, but CohRelay has much smaller relay transmission power than SimRelay. Surprisingly, both CohRelay and SimRelay require more node transmission power than AirComp.