基于GAMP-MAP估計器的非對齊空中計算

摘 要：現(xiàn)有的空中計算依賴融合中心的最大似然（maximum likelihood，ML）估計恢復(fù)來自不同設(shè)備傳輸信號的算術(shù)和，但在實踐中，實現(xiàn)準(zhǔn)確的信道增益預(yù)編碼和設(shè)備之間的嚴(yán)格同步很困難，ML估計在非對齊空中計算場景中會遭受嚴(yán)重的錯誤傳播，而且計算復(fù)雜度高。針對非對齊空中計算問題，設(shè)計了一個基于廣義近似消息傳遞（generalized approximate message passing，GAMP）計算框架的最大后驗估計器，即GAMP-MAP。該估計器使用傳輸符號數(shù)據(jù)的均值和方差作為先驗以提高估計準(zhǔn)確性，利用GAMP算法標(biāo)量估計特性降低計算復(fù)雜度。在不同信道相位偏移和時間偏移下進(jìn)行仿真實驗，實驗結(jié)果表明GAMP-MAP估計器的準(zhǔn)確性明顯優(yōu)于ML估計器，其運行時間相對ML估計器和LMMSE估計器有顯著下降。

關(guān)鍵詞：非對齊空中計算；廣義近似消息傳遞；最大后驗估計；多址接入信道

中圖分類號：TN92 文獻(xiàn)標(biāo)志碼：A 文章編號：1001-3695（2023）06-034-1812-05doi：10.19734/j.issn.1001-3695.2022.11.0563Misaligned over-the-air computation based on GAMP-MAP estimator

Liu Min，Sun Chaochao，Zhang Ting，Peng Yuan

（School of Computer Science amp; Technology，Shanghai University of Electric Power，Shanghai 201306，China）

Abstract：Existing over-the-air computation relies on maximum likelihood（ML） estimation of fusion centers to recover the arithmetic sum of transmitted signals from different devices.But it is difficult to achieve accurate channel gain precoding and strict synchronization between devices in practice.ML estimation suffers from severe error propagation in misaligned over-the-air computation scenarios，and its computational complexity is high.To solve the problem of misaligned over-the-air computation，this paper designed a maximum a posteriori estimator based on generalized approximate messaging passing（GAMP） calculation framework：GAMP-MAP.It used the mean and variance of the transmitted symbol data as a priori to improve the estimation accuracy，and utilized the scalar estimation feature of the GAMP algorithm to reduce the computational complexity.Simulation experiments were carried out under different channel phase offsets and time offsets.The experimental results show that the accuracy of the GAMP-MAP estimator is significantly better than that of the ML estimator，and its running time is significantly lower than that of the ML estimator and the LMMSE estimator.

Key words：misaligned over-the-air computation；generalized approximate message passing；maximum a posteriori estimator；multiple access channels

0 引言

物聯(lián)網(wǎng)的廣泛應(yīng)用推動了大量無線邊緣設(shè)備的部署，物聯(lián)網(wǎng)實現(xiàn)面臨如下挑戰(zhàn)：a）從大量帶寬受限的無線邊緣設(shè)備收集數(shù)據(jù)［1～3］；b）對海量數(shù)據(jù)進(jìn)行融合處理［4，5］。另外，在聯(lián)邦學(xué)習(xí)中，邊緣設(shè)備使用各自的本地數(shù)據(jù)，在邊緣服務(wù)器的協(xié)調(diào)下，聯(lián)合訓(xùn)練機(jī)器學(xué)習(xí)模型。雖然聯(lián)邦學(xué)習(xí)在邊緣智能中具有獨特的優(yōu)勢，但其頻繁的模型參數(shù)傳輸匯聚過程讓邊緣設(shè)備和服務(wù)器之間的無線通信代價正在成為制約聯(lián)邦學(xué)習(xí)性能的瓶頸［6～8］。總體來說，在大規(guī)模邊緣設(shè)備的應(yīng)用場景中，采用傳統(tǒng)的通信和計算分離的方式，會增加網(wǎng)絡(luò)延遲、降低頻譜利用率。利用多址接入信道（multiple access channel，MAC）疊加特性的空中計算可以顯著提高通信和計算效率［9～12］。空中計算是一種并行通信，適用于通信受限的計算應(yīng)用場景，被廣泛應(yīng)用于分布式感知、分布式共識和分布式邊緣學(xué)習(xí)。它是一種聯(lián)合計算和通信的技術(shù)，其功能模塊分為預(yù)處理（如信道預(yù)編碼）和后處理。通常，空中計算系統(tǒng)由多個邊緣設(shè)備和一個接收器（融合中心）組成，每個設(shè)備首先通過預(yù)處理功能對傳輸?shù)臄?shù)據(jù)進(jìn)行預(yù)處理得到發(fā)送信號，例如經(jīng)過上行信道反轉(zhuǎn)對數(shù)據(jù)進(jìn)行信道預(yù)編碼，然后發(fā)送信號通過MAC同時傳輸?shù)饺诤现行模肕AC的疊加特性，融合中心對接收到的信號和進(jìn)行后處理，最后得到設(shè)備的期望數(shù)據(jù)。

已有的文獻(xiàn)工作［13～16］研究了空中計算的理論性質(zhì)以及如何設(shè)計相應(yīng)的預(yù)處理和后處理功能。通過適當(dāng)?shù)念A(yù)處理和后處理，空中計算技術(shù)可用于計算一系列統(tǒng)計函數(shù)，稱為列線函數(shù)［13］，如求和、最大最小值、算術(shù)平均值、幾何平均值、多項式疊加和歐幾里德范數(shù)。此外，信道預(yù)編碼的目的是信道補(bǔ)償，使得衰落MAC退化為高斯MAC。然而，在實踐中，實現(xiàn)準(zhǔn)確的信道增益預(yù)編碼和設(shè)備之間的嚴(yán)格同步非常具有挑戰(zhàn)性。根據(jù)信道中相位是否存在偏移和時間是否同步，空中計算可分為對齊的空中計算［9～12，17～20］和非對齊的空中計算［21，22］，以前關(guān)于空中計算的工作考慮對齊的情況較多，但后者更具有實際意義。

對齊空中計算或非對齊空中計算依賴ML估計恢復(fù)來自不同設(shè)備傳輸信號的算術(shù)和，但ML估計容易受到噪聲的影響。文獻(xiàn)［21］表明，在非對齊空中計算中，算術(shù)和估計歸結(jié)為多用戶估計，考慮到空中計算的連續(xù)性，估計空間巨大，會導(dǎo)致ML估計存在嚴(yán)重的錯誤傳播。具體來說，一個樣本的估計誤差會影響到其他樣本，導(dǎo)致后續(xù)樣本與真實值的偏差越來越大。

為了解決ML估計在非對齊空中計算中存在的問題，本文提出了一個基于GAMP計算框架［23］的最大后驗估計器：GAMP-MAP。本文主要貢獻(xiàn)為

a）本文方法是首個使用GAMP算法來解決非對齊空中計算問題的方法。GAMP算法為線性混合估計問題提供了一種通用且系統(tǒng)的方法，它通過中心極限定理及泰勒展開，對傳統(tǒng)的消息傳遞算法進(jìn)行近似，相對于ML估計算法，它沒有對大矩陣求逆，因此能有效降低計算量。

b）本文提出的GAMP-MAP估計器使用傳輸數(shù)據(jù)的均值和方差作為先驗信息，有助于縮小估計空間，提高估計準(zhǔn)確性。

c）實驗結(jié)果表明，與ML估計器相比，GAMP-MAP估計器在不同的信道相位偏移和時間偏移下獲得了顯著降低的均方誤差（mean squared error，MSE）。例如，當(dāng)符號信噪比EsN0=5 dB，最大相位偏移ф=π/2時，ML估計器的MSE值約為4 137，而GAMP-MAP估計器的MSE值約為26.54。在運行時間上，GAMP-MAP估計器也存在很大的優(yōu)勢。例如，在最大時間偏移τ_M=0.5時，GAMP-MAP估計器的運行時間相對ML估計器和LMMSE估計器分別降低了74%和65%。

在本文中，矩陣和向量分別用粗體大寫和粗體小寫字母表示。表1為主要變量符號的含義。

1 系統(tǒng)模型和問題描述

本文考慮圖1所示的空中計算系統(tǒng)模型，它由M個邊緣設(shè)備和一個融合中心組成，允許多個邊緣設(shè)備同時向融合中心發(fā)送數(shù)據(jù)。邊緣設(shè)備的數(shù)據(jù)需經(jīng)過預(yù)處理形成發(fā)送信號，然后經(jīng)過具有疊加特性的MAC，融合中心接收疊加信號并通過后處理得到期望數(shù)據(jù)。

2 現(xiàn)有的非對齊空中計算

本章介紹了白化匹配濾波和采樣（whitened matched filtering and sampling，WMFS）方法，它可以從疊加信號中生成過采樣且獨立的樣本，本文涉及的估計器都使用了該采樣方法。2.2節(jié)中介紹了非對齊空中計算解決方案，即ML估計器和LMMSE估計器。

2.1 白化匹配濾波和采樣

白化匹配濾波和采樣使用一組不同長度的匹配濾波器對收到的r（t）進(jìn)行白化處理，輸出過采樣且獨立的樣本。

3 基于GAMP-MAP估計器的非對齊空中計算方案

本章提出一種新的估計器，即GAMP-MAP，它利用GAMP算法和先驗信息已解決2.2節(jié)估計器存在的問題。此外，分析了GAMP-MAP算法的計算復(fù)雜度。

3.1 GMAP-MAP估計器

基于GAMP-MAP估計器的非對齊空中計算方案的實現(xiàn)步驟概括如下：a）每個邊緣設(shè)備在符號數(shù)據(jù)傳輸之前，將符號數(shù)據(jù)的均值和方差傳輸?shù)饺诤现行模籦）每個邊緣設(shè)備對傳輸?shù)姆枖?shù)據(jù)進(jìn)行預(yù)處理得到發(fā)送信號；c）發(fā)送信號通過MAC同時傳輸?shù)饺诤现行模肕AC的疊加特性，融合中心接收到疊加信號；d）融合中心對接收到的疊加信號使用白化匹配濾波和采樣方案生成過采樣且獨立的樣本；e）融合中心利用GAMP-MAP估計器算法估計目標(biāo)符號數(shù)據(jù)。

3.2 計算復(fù)雜度分析

4 仿真實驗與分析

本文通過仿真實驗評估GAMP-MAP估計器的性能。

4.1 仿真實驗設(shè)置

4.2 不同信道相位偏移和時間偏移下的估計準(zhǔn)確性與運行時間

4.2.1 估計準(zhǔn)確性比較

4.2.2 運行時間比較

5 結(jié)束語

與傳統(tǒng)無線網(wǎng)絡(luò)中先發(fā)送后計算的架構(gòu)相比，空中計算的集成通信和計算特性可以有效降低邊緣網(wǎng)絡(luò)的通信和計算開銷。非對齊空中計算考慮了邊緣設(shè)備之間的時間偏移和信道相位偏移現(xiàn)象。本文提出的GAMP-MAP估計器能夠較好地解決非對齊空中計算問題。該估計器利用先驗信息縮小了估計空間，相比于ML估計器，在不同的信道相位偏移和時間偏移下均顯著提高了準(zhǔn)確性。GAMP-MAP算法在計算上解決了由于矩陣求逆帶來的計算復(fù)雜度高的問題，相比于ML和LMMSE估計器，在不同的信道相位偏移和時間偏移下均有效減少了運行時間。

本文為解決無線邊緣設(shè)備在聯(lián)邦學(xué)習(xí)中的通信和計算效率問題提供了新方案。由于考慮了相位偏移和時間偏移，GAMP-MAP估計器算法能更好地適應(yīng)聯(lián)邦學(xué)習(xí)真實場景。在聯(lián)邦學(xué)習(xí)的每輪傳輸中，多個邊緣設(shè)備同時上傳數(shù)據(jù)，融合中心先對收到的疊加信號使用白化匹配濾波和采樣，再使用GAMP-MAP估計器算法估計目標(biāo)數(shù)據(jù)。空中計算和GAMP-MAP估計器算法能減少聯(lián)邦學(xué)習(xí)過程中的通信時間和計算時間。筆者下一步工作是考慮邊緣設(shè)備如何更好地傳輸先驗信息，在接下來的研究中將利用數(shù)據(jù)包的結(jié)構(gòu)特點讓融合中心獲取先驗信息。

參考文獻(xiàn)：

［1］Schulz P，Matthe M，Klessig H，et al.Latency critical IoT applications in 5G：perspective on the design of radio interface and network architecture［J］.IEEE Communications Magazine，2017，55（2）：70-78.

［2］Huang Kang，Liu Wanchun，Shirvanimoghaddam M，et al.Real-time remote estimation with hybrid ARQ in wireless networked control［J］.IEEE Trans on Wireless Communications，2020，19（5）：3490-3504.

［3］Huang Kang，Liu Wanchun，Li Yonghui，et al.To retransmit or not：real-time remote estimation in wireless networked control［C］//Proc of IEEE International Conference on Communications.Piscataway，NJ：IEEE Press，2019：1-7.

［4］Wu Xindong，Zhu Xingquan，Wu Gongqing，et al.Data mining with big data［J］.IEEE Trans on Knowledge and Data Engineering，2013，26（1）：97-107.

［5］Zhao Nan，Liu Xiaonan，Yu F R，et al.Communications，caching，and computing oriented small cell networks with interference alignment［J］.IEEE Communications Magazine，2016，54（9）：29-35.

［6］Zhu Guangxu，Liu Dongzhu，Du Yuqing，et al.Toward an intelligent edge：wireless communication meets machine learning［J］.IEEE Communications Magazine，2020，58（1）：19-25.

［7］王帥，李丹.分布式機(jī)器學(xué)習(xí)系統(tǒng)網(wǎng)絡(luò)性能優(yōu)化研究進(jìn)展［J］.計算機(jī)學(xué)報，2022，45（7）：1384-1411.（Wang Shuai，Li Dan.Research progress on network performance optimization of distributed machine learning system［J］.Chinese Journal of Computers，2022，45（7）：1384-1411.）

［8］王惜民，范睿.基于類別不平衡數(shù)據(jù)聯(lián)邦學(xué)習(xí)的設(shè)備選擇算法［J］.計算機(jī)應(yīng)用研究，2021，38（10）：2968-2973.（Wang Ximin，F(xiàn)an Rui.Device selection in federated learning under class imbalance［J］.Application Research of Computers，2021，38（10）：2968-2973.）

［9］Liu Wanchun，Zang Xin，Li Yonghui，et al.Over-the-air computation systems：optimization，analysis and scaling laws［J］.IEEE Trans on Wireless Communications，2020，19（8）：5488-5502.

［10］Cao Xiaowen，Zhu Guangxu，Xu Jie，et al.Optimized power control for over-the-air computation in fading channels［J］.IEEE Trans on Wireless Communications，2020，19（11）：7498-7513.

［11］Zhu Guangxu，Huang Kaibin.MIMO over-the-air computation for high-mobility multimodal sensing［J］.IEEE Internet of Things Journal，2018，6（4）：6089-6103.

［12］Li Xiaoyang，Zhu Guangxu，Gong Yi，et al.Wirelessly powered data aggregation for IoT via over-the-air function computation：beamforming and power control［J］.IEEE Trans on Wireless Communications，2019，18（7）：3437-3452.

［13］Goldenbaum M，Boche H，Stańczak S.Harnessing interference for analog function computation in wireless sensor networks［J］.IEEE Trans on Signal Processing，2013，61（20）：4893-4906.

［14］Goldenbaum M，Boche H，Stańczak S.Nomographic gossiping for f-consensus［C］//Proc of the 10th International Symposium on Mode-ling and Optimization in Mobile，Ad Hoc and Wireless Networks.Piscataway，NJ：IEEE Press，2012：130-137.

［15］Goldenbaum M，Stanczak S.Robust analog function computation via wireless multiple-access channels［J］.IEEE Trans on Communications，2013，61（9）：3863-3877.

［16］Abari O，Rahul H，Katabi D.Over-the-air function computation in sensor networks［EB/OL］.（2016-12-07） .https：//arxiv.org/pdf/1612.02307v1.pdf.

［17］Amiri M M，Gyundyuz D.Machine learning at the wireless edge：distributed stochastic gradient descent over-the-air［J］.IEEE Trans on Signal Processing，2020，68：2155-2169.

［18］Yang Kai，Jiang Tao，Shi Yuanming，et al.Federated learning via over-the-air computation［J］.IEEE Trans on Wireless Communications，2020，19（3）：2022-2035.

［19］Amiri M M，Gyundyuz D.Federated learning over wireless fading channels［J］.IEEE Trans on Wireless Communications，2020，19（5）：3546-3557.

［20］Ozfatura E，Rini S，Gyundyz D.Decentralized SGD with over-the-air computation［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2020：1-6.

［21］Shao Yulin，Gündüz D，Liew S C.Federated edge learning with misaligned over-the-air computation［J］.IEEE Trans on Wireless Communications，2022，21（6）：3951-3964.

［22］Shao Yulin，Gündüz D，Liew S C.Bayesian over-the-air computation［EB/OL］.（2022-10-25）.https：//arxiv.org/pdf/2109.03780v3.pdf.

［23］Rangan S.Generalized approximate message passing for estimation with random linear mixing［C］//Proc of IEEE International Symposium on Information Theory Proceedings.Piscataway，NJ：IEEE Press，2011：2168-2172.

［24］Wang Shengchu，Li Yunzhou，Wang Jing.Low-complexity multiuser detection for uplink large-scale MIMO［C］//Proc of IEEE Wireless Communications and Networking Conference.Piscataway，NJ：IEEE Press，2014：224-229.

［25］Al-Shoukairi M，Schniter P，Rao B D.A GAMP-based low complexity sparse Bayesian learning algorithm［J］.IEEE Trans on Signal Processing，2018，66（2）：294-308.