This paper investigates over-the-air computation (AirComp) over multiple-access time-varying channels, where devices with high mobility transmit their sensing data to a fusion center (FC) for averaging. To combat the Doppler shift induced by time-varying channels, each device adopts orthogonal time frequency space (OTFS) modulation. Our objective is minimizing the mean squared error (MSE) for the target function estimation. Due to the multipath time-varying channels, the OTFS-based AirComp not only suffers from noise but also interference. Specifically, we propose three schemes, namely S1, S2, and S3, for the target function estimation. S1 directly estimates the target function under the impacts of noise and interference. S2 mitigates the interference by introducing a zero padding-assisted OTFS. In S3, we propose an iterative algorithm to estimate the function in a matrix form. In the numerical results, we evaluate the performance of S1, S2, and S3 from the perspectives of MSE and computational complexity, and compare them with benchmarks. Specifically, compared to benchmarks, S3 outperforms them with a significantly lower MSE but incurs a higher computational complexity. In contrast, S2 demonstrates a reduction in both MSE and computational complexity. Lastly, S1 shows superior error performance at small SNR and reduced computational complexity.

In wireless communication systems, interference is considered one of the main bottlenecks. Because all devices share the same electromagnetic spectrum, communication protocols generally attempt to separate radio resources to avoid interference. In LTE and 5G, devices are not allowed to transmit at their own behest but must receive an uplink grant that dictates which radio resources to use. In Wi-Fi 5, devices are allowed to transmit without a grant from the router, but they have to listen to the channel and wait until it is quiet before transmitting. While these interference-avoiding methods are quite useful, they face the problem of congestion. If too many devices are communicating data simultaneously, the avoidance of interference leads to insufficient spectrum for each user, and quality of service drops dramatically.

In this thesis, we study a novel form of wireless communication that takes a different approach to sharing electromagnetic spectrum. Rather than using orthogonal resources for each device, it schedules devices on the same communication resources, resulting in electromagnetic superposition of their signals. When the receiver listens, the superimposed signal will contain so much interference that it is difficult to distinguish the individual messages. However, it is possible to compute functions of the transmitted messages. Hence, this method is often referred to as Over-the-Air Function Computation (AirComp).

The challenges of AirComp are fundamentally different from those of orthogonal communication. Well-known results on, e.g., phase acquisition, forward error correction, and modulation do not map directly to the AirComp setting. Because of this, the state-of-the-art literature on AirComp usually does not guarantee error-free function computation with a vanishing probability of error but resorts to imperfect function estimation. We have dedicated this thesis to improving the state of estimation algorithms for AirComp. For example, we have developed a power control scheme that eliminates estimation bias for fast-fading channels, and we have leveraged dimensionality-reduction methods to compute certain functions without error.

Our recent work has focused on incorporating realistic assumptions concerning time synchronization and phase acquisition. In orthogonal communication methods, phase alignment is often achieved by careful correction at the receiver side, using reference signals and phase-locked loops. In AirComp, since we are interested in the coherent superposition of signals, the phase cannot be corrected at the receiver side. Transmitter-side phase correction from UEs is challenging, and therefore we have developed non-coherent AirComp methods that avoid this problem. We also specify non-coherent AirComp schemes for digital communication problems in the sparse regime, outperforming orthogonal methods.

I trådlösa kommunikationssystem är interferens en av de mest begränsande flaskhalsarna. Eftersom alla enheter delar samma elektromagnetiska spektrum så tenderar kommunikationsprotokol att separera radioresurser för att undvika interferens. I LTE och 5G får enheterna inte ta initiativ till att sända, utan måste vänta på ett tillstånd som bestämmer vilka resurser de får använda. I Wi-Fi 5 får enheterna ta initiativ, men de måste först lyssna på kanalen och vänta tills det är tyst innan de börjar sända. Dessa interferensundvikande metoder är väldigt användbara men de påverkas oundvikligen av problem med bergänsat spektrum. Om för många enheter vill kommunicera samtidigt så kommer undvikningen av interferens leda till otillräckliga resurser för varje enhet, vilket drastiskt minskar kommunikationskvaliteten.

I den här avhandlingen studerar vi en ny metod för trådlös kommunikation som har ett annat tillvägagångssätt för att samarbeta över det elektromagnetiska spektrumet. Istället för att allokera ortogonala resurser till varje enhet så tilldelas många enheter samma kommunikationsresurser, vilket leder till elektromagnetisk superposition av deras signaler. När mottagaren lyssnar på de kombinerade signalerna, så är det så pass mycket interferens att separeringen av individuella meddelanden blir utmanande. Däremot är det möjligt att beräkna funktioner av meddelanderna, vilket är varför metoden ofta kallas Over-the-Air Function Computation (AirComp) på engelska. På svenska föreslår vi att kalla det signalfogning, för att referera till hur signaler fogas till en funktion i spektrumet.

Tekniken för signalfogning är fundamentalt annorlunda från ortogonala kommunikationsmetoder. Välkända resultat inom till exempel, fastrackning, felrättande koder och modulering fungerar inte på samma sätt för signalfogning. Pågrund av detta så brukar signalfogningslitteraturen inte garantera felfri funktionsberäkning, utan arbetar istället med estimering. Den här avhandlingen är dedikerad till att utveckla bättre estimeringsalgoritmer för signalfogning. Till exempel har vi utvecklat en effektallokeringsalgoritm för att ta bort systematiska fel under snabbfädning och vi har utvecklat kompressionsmetoder för att beräkna specifika funktioner helt utan estimeringsfel.

Våra senaste bidrag till litteraturen har fokuserat på att integrera realistiska antaganden gällande tidssynkronisering och fastrackning. Inom ortogonala kommunikationssystem så sker fastrackning ofta genom noggrann korrektion på mottagarsidan, där referenssignaler från sändaren nyttjas i regleralgoritmer för att styra mottagaroscillatorn. Inom signalfogning kan inte fasen korrigeras på mottagarsidan eftersom vi är intresserade av fasriktig superposition i det elektromagnetiska spektrumet. Samtidigt är faskorrigering på sändarsidan utmanande, och därför har vi arbetat med att utveckla signalfogningsmetoder som inte är beroende av någon faskorrigering. Vi specificerar också sådana metoder för digitala kommunikationsproblem med glesa signaler, vilket överträffar otrogonala metoder.

This paper investigates over-the-air computation (AirComp) in the context of multiple-access time-varying multipath channels. We focus on a scenario where devices with high mobility transmit their sensing data to a fusion center (FC) for averaging. To combat the time-varying channel and Doppler effect, each device adopts orthogonal time frequency space (OTFS) modulation. After signals are received by the FC, the aggregated data undergoes demodulation and estimation within the delay-Doppler domain. We leverage the mean squared error (MSE) as a metric for the computational error of OTFS-based AirComp. We then derive the optimal transmit power at each device and signal scaling factor at FC for minimizing MSE. Notably, the performance of OTFS-based AirComp is not only affected by the noise but also by the inter-symbol interference and inter-link interference arising from the multipath channel. To counteract the interference-induced computational errors, we incorporate zero-padding (ZP)-assisted OTFS into AirComp and propose algorithms for interference cancellation. Numerical results underscore the enhanced performance of ZP-assisted OTFS-based AirComp over naive OTFS-based AirComp.

We consider the problem of secure histogram es-timation, where n users hold private items xi from a size-d domain and a server aims to estimate the histogram of the user items. Previous results utilizing orthogonal communication schemes have shown that this problem can be solved securely with a total communication cost of O(n²log(d)) bits by hiding each item xi with a mask. In this paper, we offer a different approach to achieving secure aggregation. Instead of masking the data, our scheme protects individuals by aggregating their messages via a multiple-access channel. A naive communication scheme over the multiple-access channel requires d channel uses, which is generally worse than the O(n²1og(d)) bits communication cost of the prior art in the most relevant regime d >> n. Instead, we propose a new scheme that we call Over-the-Air Group Testing (AirG T) which uses group testing codes to solve the histogram estimation problem in O(n log(d)) channel uses. AirGT reconstructs the histogram exactly with a vanishing probability of error Perror= O(d-^T) that drops exponentially in the number of channel uses T.

Motivated by the increasing computational capabilities of wireless devices, as well as unprecedented levels of user- and device-generated data, new distributed machine learning (ML) methods have emerged. In the wireless community, Federated Learning (FL) is of particular interest due to its communication efficiency and its ability to deal with the problem of non-IID data. FL training can be accelerated by a wireless communication method called Over-the-Air Computation (AirComp) which harnesses the interference of simultaneous uplink transmissions to efficiently aggregate model updates. However, since AirComp utilizes analog communication, it introduces inevitable estimation errors. In this paper, we study the impact of such estimation errors on the convergence of FL and propose retransmissions as a method to improve FL accuracy over resource-constrained wireless networks. First, we derive the optimal AirComp power control scheme with retransmissions over static channels. Then, we investigate the performance of Over-the-Air FL with retransmissions and find two upper bounds on the FL loss function. Numerical results demonstrate that the power control scheme offers significant reductions in mean squared error. Additionally, we provide simulation results on MNIST classification with a deep neural network that reveals significant improvements in classification accuracy for low-SNR scenarios.

Over-the-air computation (AirComp) is a promising wireless communication method for aggregating data from many devices in dense wireless networks. The fundamental idea of AirComp is to exploit signal superposition to compute functions of multiple simultaneously transmitted signals. However, the time-and phase-alignment of these superimposed signals have a significant effect on the quality of function computation. In this study, we analyze the AirComp problem for a system with unknown random time delays and phase shifts. We show that the classical matched filter does not produce optimal results, and generates bias in the function estimates. To counteract this, we propose a new filter design and show that, under a bound on the maximum time delay, it is possible to achieve unbiased function computation. Additionally, we propose a Tikhonov regularization problem that produces an optimal filter given a tradeoff between the bias and noise-induced variance of the function estimates. When the time delays are long compared to the length of the transmitted pulses, our filter vastly outperforms the matched filter both in terms of bias and mean-squared error (MSE). For shorter time delays, our proposal yields similar MSE as the matched filter, while reducing the bias.

With the emerging Internet of Things (IoT) paradigm, more than a billion sensing devices will be collecting an unprecedented amount of data. Simultaneously, the field of data analytics is being revolutionized by modern machine learning (ML) techniques that enable sophisticated processing of massive datasets. Many researchers are envisioning a combination of these two technologies to support exciting applications such as environmental monitoring, Industry 4.0, and vehicular communications. However, traditional wireless communication protocols are inefficient in supporting distributed ML services, where data and computations are distributed over wireless networks. This motivates the need for new wireless communication methods. One such method, over-the-air computation (AirComp), promises to communicate with massive gains in terms of energy, latency, and spectrum efficiency compared to traditional methods.

The expected efficiency of AirComp is due to the complete spectrum sharing for all participating devices. Unlike in traditional physical-layer communications, where interference is avoided by allocating orthogonal communication channels, AirComp promotes interference to compute a function of the individually transmitted messages. However, AirComp can not reconstruct functions perfectly but introduces errors in the process, which harms the convergence rate and region of optimality of ML algorithms. The main objective of this thesis is to develop methods that reduce these errors and analyze their effects on ML performance.

In the first part of this thesis, we consider the general problem of designing wireless methods for ML applications. In particular, we present an extensive survey which divides the field into two broad categories, digital communications and analog over-the-air-computation. Digital communications refers to orthogonal communication schemes that are optimized for ML metrics, such as classification accuracy, privacy, and data-importance, rather than traditional communication metrics such as fairness, data rate, and reliability. Analog over-the-air-computation refers to the AirComp method and its application to distributed ML, where communication-efficiency, function estimation, and privacy are key concerns.

In the second part of this thesis, we focus on the analog over-the-air computation problem. We consider a network setup with multiple devices and a server that can be reached via a single hop, where the wireless channel is modeled as a multiple-access channel with fading and additive noise. Over such a channel, the AirComp function estimate is associated with two types of error: 1) misalignment errors caused by channel fading and 2) noise-induced errors caused by the additive noise. To mitigate these errors, we propose AirComp with retransmissions and develop the optimal power control scheme for such a system. Furthermore, we use optimization theory to derive bounds on the convergence of an AirComp-supported ML system that reveal a relationship between the number of retransmissions and loss of the ML model. Finally, with numerical results we show that retransmissions can significantly improve ML performance, especially for low-SNR scenarios. 

Med Internet of Things (IoT)-paradigmen, kommer över en miljard sensorenheter att samla en mängd data som saknar motstycke. Samtidigt har dataanalys revolutionerats av moderna maskininlärningstekniker (ML) som möjliggör avancerad behandling av massiva dataset. Många forskare föreställer sig en kombination av dessa två two teknologier för att möjliggöra spännande applikationer som miljöövervakning, Industri 4.0, och fordonskommunikation. Tyvärr är traditionella kommunikationsprotokoll ineffektiva när det kommer till att stödja distribuerad maskininlärning, där data och beräkningar är utspridda över trådlösa nätverk. Detta motiverar behovet av nya trådlösa kommunikationsprotokoll. Ett protokoll, over-the-air computation (AirComp), lovar att kommunicera med enorma fördelar när det kommer till energieffektivitet, latens, and spektrumeffektivitet jämfört med traditionella protkoll.

AirComps effektivitet beror på den fullständiga spektrumdelningen mellan alla medverkande enheter. Till skillnad från traditionell ortogonal kommunikation, där interferens undviks genom att allokera ortogonala radioresurser, så uppmuntrar AirComp interferens och nyttjar den för att räkna ut en funktion av de kommunicerade meddelanderna. Dock kan inte AirComp rekonstruera funktioner perfekt, utan introducerar fel i processen vilket försämrar konvergensen av ML-algoritmer. Det huvudsakliga målet med den här avhandlingen är att utveckla metoder som minskar dessa fel och att analysera de effekter felen har på prestandan av distribuerade ML-algoritmer.

I den första delen av avhandlingen behandlar vi det allmänna problemet med att designa trådlösa nätverksprotokoll för att stödja ML. Specifikt så presenterar vi en utförlig kartläggning som delar upp fältet i två kategorier, digital kommunikation och analog AirComp. Digital kommunikation syftar på ortogonala kommunikationsprotokoll som är optimerade för ML-måttstockar, t.ex. klassifikationskapabilitet, integritet, och data-vikt (data-importance), snarare än traditionella kommunikationsmål såsom jämlikhet, datahastighet, och tillförlitlighet. Analog AirComp syftar till AirComps applicering till distribuerad ML, där kommunikationseffektivitet, funktionsestimering, och integritet är viktiga måttstockar.

I den andra delen av avhandlingen fokuserar vi på det analoga AirComp-problemet. Vi beaktar ett nätverk med flera enheter och en server som kan nås via en länk, där den trådlösa kanalen modelleras som en multiple-access kanal (MAC) med fädning och additivt brus. Över en sådan kanal så associeras AirComps funktionsestimat med två sorters fel: 1) felinställningsfel orsakade av fädning och 2) brusinducerade fel orsakade av det additiva bruset. För att mildra felen föreslår vi AirComp med återsändning och utvecklar den optimala "power control"-algoritmen för ett sådant system. Dessutom använder vi optimeringsteori för att härleda begränsningar på konvergensen av ett AirCompsystem för distribuerad ML som tydliggör ett förhållande mellan antalet återsändningar och förlustfunktionen för ML-modellen. Slutligen visar vi att återsändningar kan signifikant förbättra ML-prestanda genom numeriska resultat, särskilt när signal-till-brus ration är låg. 

Over-the-air computation (AirComp) has recently emerged as an efficient analog method for data acquisition from wireless sensor devices. In essence, AirComp exploits the signal superposition property of a multiple access channel to estimate functions of the transmitted data points. Unless devices are excluded from participation, state-of-the-art AirComp methods do not achieve unbiased function computation, thereby introducing systematic errors in the acquired function. In this paper, we propose a new AirComp scheme that employs retransmissions to achieve probabilistically unbiased function computation. We solve a power control problem that minimizes the bias subject to a peak transmission power constraint. We show that the optimal power control follows a greedy structure that maximizes the devices' contribution to the received function at every retransmission. Numerical results show that the proposed scheme can achieve unbiased function computation with a few retransmissions and drastically reduce the mean squared error in the function estimation compared to the current state-of-the-art.

As data generation increasingly takes place on devices withouta wired connection, Machine Learning (ML) related traffic willbe ubiquitous in wireless networks. Many studies have shownthat traditional wireless protocols are highly inefficient or unsustainableto support ML, which creates the need for new wirelesscommunication methods. In this monograph, we give a comprehensivereview of the state-of-the-art wireless methods that arespecifically designed to support ML services over distributeddatasets. Currently, there are two clear themes within the literature,analog over-the-air computation and digital radio resourcemanagement optimized for ML. This survey gives an introductionto these methods, reviews the most important works, highlightsopen problems, and discusses application scenarios.