基于消息傳遞的大規模多用戶MIMO低復雜度的檢測算法

王瓊，葉偉，吉明明

（重慶郵電大學通信與信息工程學院，重慶 400065）

研究與開發

基于消息傳遞的大規模多用戶MIMO低復雜度的檢測算法

王瓊，葉偉，吉明明

（重慶郵電大學通信與信息工程學院，重慶 400065）

針對大規模多用戶多輸入多輸出（MIMO）系統中基站端檢測復雜度高的問題，提出了一種低復雜度、基于強制收斂的變量節點全信息高斯消息傳播迭代檢測（VFI-GMPID-FC）算法。首先對傳統的GMPID算法進行改進，得到VFI-GMPID算法，VFI-GMPID算法的檢測性能逼近最小均方誤差檢測（MMSE）算法，但復雜度要大大低于MMSE算法。然后結合強制收斂思想和VFI-GMPID，提出VFI-GMPID-FC算法，進一步降低算法復雜度，提升檢測效率。最后通過仿真結果表明，所提算法在保證檢測性能的同時，能有效地降低算法的復雜度。

大規模多用戶MIMO；高斯消息傳遞迭代檢測；強制收斂；低復雜度

1 引言

現代無線通信對數據傳輸速率要求不斷提高，多用戶MIMO（multiple input multiple output，多輸入多輸出）系統作為其關鍵技術之一，現已被許多國際標準納入其中。但為了追求更高的數據傳輸速率，多用戶MIMO技術不斷發展，并逐漸發展成大規模多用戶MIMO系統，該系統中基站端的天線數量達到了成百上千個，這吸引了越來越多的用戶關注[1-3]。

在大規模多用戶MIMO系統中，由于用戶數量增加、基站接收天線數量巨大、接收信號復雜和信道矩陣維度巨大等原因，基站端的檢測復雜度高、效率低，因此低復雜度信號檢測算法成為研究的熱點。眾所周知，MMSE算法是在高斯信號源的情況下表現最佳的線性檢測算法。然而，由于它存在著大規模的矩陣求逆計算使得復雜度很高，難以運用于實際工程。為了避免矩陣求逆，一些經典的迭代算法，如雅可比算法、理查德森算法、諾伊曼級數和高斯—賽德爾算法被應用于MMSE算法中來降低其復雜度[4]。雖然這些算法在一定程度上提高了檢測效率，但是它們是以犧牲檢測性能為代價的，在許多情況下無法滿足可靠性的要求。

近年來，為了使系統在滿足檢測性能的同時提高檢測效率，研究者們不斷地尋求低復雜度和性能更優的檢測算法。基于圖形檢測的消息傳遞算法由于其低復雜度和優良的檢測性能，被許多學者運用到MIMO系統的檢測當中。其消息傳遞算法一般分為兩類：一類是高斯置信度傳播（Gaussian belief propagation，GaBP）算法[5-7]，另一類是高斯消息傳播迭代檢測（Gaussian message passing iterative detection，GMPID）算法[8-15]。這兩類算法都是高效的高斯圖模型的分布式算法，特別是GMPID算法，其廣泛地運用在符號間干擾信道均衡和現代信道編碼解碼當中，如Turbo碼和低密度奇偶校驗碼（low density check code，LDPC）。參考文獻[16,17]證明了圖形結構中的因子圖具有樹型結構，消息傳遞算法中均值和方差分別收斂于真實邊際均值和近似邊際方差。然而，如果因子圖中存在著環路，消息傳遞算法中的均值和方差可能無法收斂。

本文首先針對GMPID算法收斂分析難的問題，通過改變變量節點的消息傳輸規則，改進了GMPID算法，得到了VFI-GMPID（variable node full information Gaussian message passing iterative detection，變量節點全信息高斯消息傳播迭代檢測）算法。然后對算法輸出的估計值和均方誤差進行收斂分析，并分析算法的復雜度，證明在用戶數量與基站天線數量之比小于時，VFI-GMPID算法收斂于MMSE算法。為了進一步提高VFI-GMPID算法檢測效率，結合強制收斂思想[18]優化VFI-GMPID算法，提出了VFI-GMPID-FC（variable node full information Gaussian message passing interactive detection based on forced convergence，變量節點全信息高斯消息傳播迭代檢測）算法。最后通過仿真驗證VFI-GMPID算法收斂性，比較VFI-GMPID算法和VFI-GMPID-FC算法與MMSE算法在不同的信噪比下誤碼率的差異性。

2 系統模型

假定在大規模多用戶MIMO系統中用戶端有K個單天線用戶，基站端有M根天線。上行鏈路中，多個用戶向基站端同時發送各自的信號。如果無線信道是準靜態的平坦衰落，信息傳輸過程中引入的是可加性高斯白噪聲，且在接收端正確地獲取信道的狀態信息，對于某一時刻，基站接收信號可以表示為：

系統模型寫成矩陣形式為：

基站端的多用戶檢測任務就是從所接收的信號矢量y中估計用戶發送的信號矢量x。本文中假設基站端已知H，只考慮簡單真實的大規模多用戶MIMO系統，因為其復雜的情況可以從真實情況中擴展得到。

3 VFI-GMPID算法

3.1 算法原理

VFI-GMPID是一種基于因子圖模型的算法。大規模多用戶MIMO系統因子圖模型如圖1所示。

圖1 大規模多用戶MIMO系統因子圖模型

圖2 因子節點消息更新傳遞過程

更新過程可以看成一個多址接入的過程。因子節點接收變量節點所傳來的消息，利用更新公式計算更新后的消息，再把更新后的消息傳回給變量節點。第 m個因子節點的消息更新計算式為：

變量節點消息更新傳遞過程如圖3所示。

圖3 變量節點消息更新傳遞過程

變量節點消息更新可以看成廣播過程。第k個變量節點的消息更新計算式為：

算法達到設定的迭代次數，輸出為：

當M和K比較大時，大規模多用戶MIMO系統模型因子圖是完全圖，則變量節點和因子節點之間的環路非常多。這時VFI-GMPID算法與原始的GMPID算法都存在著在消息傳遞過程中無法收斂的問題。本文提出的 VFI-GMPID算法和原始的GMPID算法相比，在變量節點的消息更新式（4）上有所不同。GMPID算法由于傳輸的是外信息，其結構性非常復雜，很難對其進行理論收斂性分析。而本文所提出的VFI-GMPID算法在因子節點傳輸給變量節點消息是全部的、完整的信息，而不僅僅是外信息。這使其結構性變得簡單，讓理論收斂分析變成了可能。當M非常大且K＜M時，VFI-GMPID算法和原始的GMPID算法中變量節點接收的消息之間的差異可以忽略不計，所以其在大規模多用戶MIMO系統中不會導致性能顯著損失。

3.2 收斂性分析

要對 VFI-GMPID算法進行收斂性分析就必須先對MMSE算法進行分析。MMSE算法對信號源估計值如下：

其中，V包含對每一個信號源的估計誤差，具體而言協方差矩陣V中的對角線上的元素vkk是表示對xk的估計誤差值。當K→∞時，由參考文獻[21]可得：

其中：

下面將從兩個方面對 VFI-GMPID算法進行收斂性分析，一方面對輸出的收斂性分析，證明其收斂于MMSE算法的均方誤差；另一方面對k收斂分析，證明其收斂于MMSE算法的估計值于。對于的收斂分析如下。

根據式（3）和式（4）可得：

當用戶數量K與接收天線數量M非常大時，由卡方分布特性，式（13）可以近似等效于：

其中，s-1相對于M-K可以忽略，比較式（10）與式（16）可以得出，收斂于MMSE算法的均方誤差。

其中，D為HTH的對角矩陣。

根據式（3）和式（4）可得：

根據經典迭代算法[22]可知，要使式（22）中 e?收斂，必須有譜半徑，即：

當式（22）收斂時可以看出，式（22）與式（6）有相同的收斂值，這說明VFI-GMPID的輸出信號估計值收斂于MMSE的信號估計值，即收斂于。

由上述分析可知，對于大規模多用戶MIMO

3.3 算法復雜度分析

通過式（6）可以看到，傳統的MMSE算法的矩陣求逆運算的復雜度為O( K3)，矩陣乘法計算的復雜度為O( MK)，則MMSE算法的復雜度為，這個計算復雜度在天線數量非常大時是非常高的。而上述的VFI-GMPID算法的復雜度主要是在消息的更新計算當中，為其中Niter為設置的迭代次數。通過復雜度分析可以得到，在大規模多用戶MIMO系統中，VFI-GMPID算法相比于MMSE算法具有較低的復雜度。

4 VFI-GMPID-FC算法

為了進一步提高VFI-GMPID的檢測效率，本文結合強制收斂的思想，提出了 VFI-GMPID-FC算法。強制收斂原理是消息在傳遞過程中會收斂于一個確定的值，但是節點的收斂速度是不固定的，因此人為給定一個門限值，當其變化速率低于這個門限值時，則停止此節點的后續消息更新過程。其本質就是挑出某些節點并停止其后續的消息更新過程，以此來降低算法的復雜度。強制收斂思想可以運用于 VFI-GMPID算法中來降低計算復雜度。在消息更新的過程中，VFI-GMPID算法中變量節點和因子節點的強制收斂速度是不固定的。對于因子節點的消息更新過程，引入兩個門限值 λe與 λv。當消息傳遞過程中，因子節點消息滿足式（24）或式（25），則停止因子節點對應的消息成分更新：

在節點消息成分停止更新后，其后面的迭代過程將保持固定的消息輸出值。

VFI-GMPID-FC算法步驟描述如下。

步驟 1 輸入信道矩陣H、接收矢量y、門限值λe和λv、迭代次數Niter。

步驟3 利用式（3）計算因子節點的消息，并利用式（24）和式（25）判斷哪些節點停止更新消息，把停止更新的節點加入停止更新列表。

步驟4 利用式（4）計算變量節點的消息。

5 仿真分析

大規模多用戶MIMO系統應用中，基站端的天線數量一般要大于用戶數量。所以仿真模型采用基站端的接收天線數量為600，單天線用戶數量為100，用戶與基站天線的比值。用戶天線到基站天線之間的信道增益 hij服從獨立同分布，且服從均值為 0、方差為 1的復高斯分布。采用16QAM調制，用戶發送的信號服從獨立同分布，且服從均值為0、方差為1的復高斯分布。Niter為迭代次數，MSE為檢測算法輸出的信號源估計值與實際的信號值之間的平均均方誤差。

本文所提出的VFI-GMPID算法的MSE收斂分析如圖4所示。從圖4中可以看出，當M=600、時，VFI-GMPID算法在一定的信噪比情況下，隨著迭代次數的增加，其平均均方誤差不斷減小，則其檢測性能也在不斷地提升，并且不斷逼近MMSE的平均均方誤差。當Niter=7時，與MMSE算法相比，VFI-GMPID算法的平均均方誤差值與達到10-4時所需的信噪比相差0.95 dB。

圖4 VFI-GMPID算法的MSE收斂分析

圖5是在不同迭代次數下，VFI-GMPID算法與參考文獻[11]中所改進的檢測性能較好的簡化期望近似消息傳遞算法（approximate message passing simplified by expection propagation，AMP-EP）、MMSE算法的誤碼率（bit error rate，BER）比較。VFI-GMPID算法的檢測性能隨著迭代次數的增加不斷提高，并且誤碼率逼近于MMSE算法。當Niter=7時，與 MMSE相比，VFI-GMPID算法的誤碼率與達到10-4時所需的信噪比相差0.55 dB，與AMP-EP算法相差0.32 dB。結合圖4和圖5可以看出，本文所提出算法有實際運用的可行性。

為了分析VFI-GMPID-FC算法中強制收斂門限值λe和λv對其檢測性能和復雜度的影響。統計的大規模多用戶MIMO系統中運用VFI-GMPID-FC算法，對于不同的λe和λv，在信噪比為5 dB、迭代次數為7、檢測20 000次符號時，因子節點停止消息更新的平均數量與不同算法的仿真運行時間。圖6（a）為只設定λ，統計因子節點中停止消息(t )的

e平均個數。圖 6（b）為只設定 λv，統計因子節點中停止消息(t )的平均個數。

圖5 VFI-GMPID不同迭代次數下誤碼率

不同算法運行時間見表1。從表1中可以看出，VFI-GMPID和AMP-EP算法在相同條件下仿真運行時間相差不多，因為兩者的計算復雜度都是在量級。而VFI-GMPID-FC算法因為引入了門限，其仿真運行時間明顯下降，說明其能有效地降低復雜度。

圖7為不同改進算法在迭代次數為7的情況下與 MMSE算法在不同信噪比的誤碼率比較。VFI-GMPID-FC算法設置合適的門限值，其性能相比于VFI-GMPID算法在較低信噪比沒有性能的太大損失，在較高信噪比端有一定的損失。當誤差率達到10-4時，VFI-GMPID-FC算法相比于VFI-GMPID算法所需的信噪比要高1.3 dB，相比于AMP-EP算法要高0.95 dB。結合表1和圖7可以得到，對于VFI-GMPID-FC算法來說，門限值設置過低，停止節點更新的數量較少，起不到降低復雜度的作用；而門限值設置過高，將有太多的節點停止更新，影響算法的檢測性能。所以選擇合適的門限值才能在不影響檢測性能的情況下，起到降低復雜度的作用。

圖6 兩種門限值平均停止節點數

表1 不同算法運行時間

圖7 VFI-GMPID-FC算法性能比較

6 結束語

本文主要研究大規模多用戶MIMO系統低復雜度的檢測算法技術。由于傳統的MMSE算法存在著矩陣求逆，復雜度高，不適用于大規模多用戶MIMO系統。本文根據消息傳遞算法的原理，提出了一種低復雜度的VFI-GMPID-FC算法。首先對GMPID改進，得到了VFI-GMPID算法。該算法在大規模多用戶 MIMO系統中時，設置合適的迭代次數，其誤碼率與MMSE算法相當，復雜度卻大大降低。之后結合強制收斂思想對 VFI-GMPID算法進行優化，提出了VFI-GMPID-FC算法，進一步地降低了 VFI-GMPID算法的復雜度。仿真結果表明，當VFI-GMPID-FC算法設置合適的門限值時，能夠在保證檢測性能的同時，又具有較低的復雜度，非常適用于大規模多用戶MIMO系統。

[1] RUSEK F, PERSSON D, LAU B K, et al. Scaling up MIMO: opportunities and challenges with very large arrays[J]. Signal Processing Magazine IEEE, 2012, 30(1): 40-60.

[2] 畢奇, 謝偉良, 陳鵬, 等. LTE多天線技術發展趨勢[J]. 電信科學, 2014, 30(10): 1-7. BI Q, XIE W L, CHEN P, et al. Progress and trends of multiple antennas technology in LTE network[J]. Telecommunications Science, 2014, 30(10): 1-7.

[3] 陽析, 金石. 大規模 MIMO系統傳輸關鍵技術研究進展[J].電信科學, 2015, 31(5): 28-35. YANG X, JIN S. Overview of key technologies of transmissionin massive MIMO system[J]. Telecommunications Science, 2015, 31(5): 28-35.

[4] 周將運. Massive MIMO系統的檢測算法研究[D]. 成都: 電子科技大學, 2015. ZHOU J Y. Research on detection algorithms for massive MIMO systems[D]. Chengdu: University of Electronic Science and Technology of China, 2015.

[5] MOALLEMI C C, VAN ROY B. Convergence of min-sum message passing for quadratic optimization[J]. IEEE Transactions on Information Theory, 2009, 55(5): 2413-2423.

[6] WEISS Y, FREEMAN W T. Correctness of belief propagation in gaussian graphical models of arbitrary topology[J]. Neural Computation, 2001, 13(10): 2173.

[7] SU Q, WU Y C. Convergence analysis of the variance in gaussian belief propagation[J]. IEEE Transactions on Signal Processing, 2014, 62(19): 5119-5131.

[8] GUO Q, PING L. LMMSE turbo equalization based on factor graphs[J]. IEEE Journal on Selected Areas in Communications, 2008, 26(2): 311-319.

[9] MONTANARI A, PRABHAKAR B, TSE D. Belief propagation based multi-user detection[C]//Allerton Conference on Communication, May 22, 2006, Monticello, USA. [S.l.:s.n.], 2006: 1-9.

[10] ABBAS S M, FAN Y Z, CHEN J, et al. Low complexity belief propagation polar code decoder[C]//2015 IEEE Workshop on Signal Processing Systems (SiPS), October 14-16, 2015, Hangzhou, China. New Jersey: IEEE Press, 2015: 1-6.

[11] WU S, KUANG L, NI Z, et al. Low-complexity iterative detection for large-scale multiuser MIMO-OFDM systems using approximate message passing[J]. IEEE Journal of Selected Topics in Signal Processing, 2014, 8(5): 902-915.

[12] YOON S, CHAE C B. Low-complexity MIMO detection based on belief propagation over pairwise graphs[J]. IEEE Transactions on Vehicular Technology, 2014, 63(5): 2363-2377.

[13] YUE Z, GUO Q, XIANG W. Complex Gaussian belief propagation algorithms for distributed iterative receiver[C]//2014 IEEE 25th Annual International Symposium on Personal, Indoor, and Mobile Radio Communication (PIMRC), September 2-5, 2014, Washington, USA. New Jersey: IEEE Press, 2014: 1908-1912.

[14] HAN K, HU J, CHEN J, et al. A high performance massive MIMO detector based on log-domain belief-propagation[C]// International Conference on Asic, November 3-6, 2015, Chengdu, China. New Jersey: IEEE Press, 2015: 1-4.

[15] YUAN Z, ZHANG C, WANG Z, et al. An Auxiliary Variable-aided hybrid message passing approach to joint channel estimation and decoding for MIMO-OFDM[J]. IEEE Signal Processing Letters, 2017(99): 1.

[16] KSCHISCHANG F R, FREY B J, LOELIGER H A. Factor graphs and the sum-product algorithm[J]. IEEE Transactions on Information Theory, 2001, 47(2): 498-519.

[17] LOELIGER H A. An introduction to factor graphs[J]. IEEE Signal Processing Magazine, 2004, 21(1): 28-41.

[18] CHOI B J, SUNWOO M H. Simplified forced convergence decoding algorithm for low power LDPC decoders[C]//2014 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS), November 17-20, 2014, Ishigaki, Japan. New Jersey: IEEE Press, 2014: 663-666.

[19] LIU X, SIMEONE O, ERKIP E. Energy-efficient sensing and communication of parallel Gaussian sources[J]. IEEE Transactions on Communications, 2012, 60(12): 3826-3835.

[20] KAFEDZISKI V. Rate allocation for transmission of two Gaussian sources over multiple access fading channels[J]. IEEE Communications Letters, 2012, 16(11): 1784-1787.

[21] VERDU S. Multiuser detection[M]. Cambridge: Cambridge University Press, 1998.

[22] AXELSSON O. Iterative solution methods[M]. Cambridge: Cambridge University Press, 1994.

A low complexity detection algorithm for large scale multiuser MIMO based on message passing

WANG Qiong, YE Wei, JI Mingming
School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

According to the problem of high complexity of base station detection in large scale multiuser multiple input multiple output (MIMO) system, a low complexity multiuser variable node full information Gaussian message passing iterative detection algorithm based on forced convergence (VFI-GMPID-FC) was proposed. Firstly, the traditional Gaussian message passing iterative detection (GMPID) algorithm was improved to obtain VFI-GMPID algorithm, the detection performance of the VFI-GMPID algorithm approximates the minimum mean square error detection (MMSE) algorithm, but the complexity was considerably less than the MMSE algorithm. Then, the VFI-GMPID-FC algorithm was proposed to reduce the complexity of the algorithm and improve the detection efficiency. Finally, the simulation results show that the proposed algorithm can effectively reduce the algorithm complexity while ensuring the detection performance.

large scale multiuser MIMO, Gaussian message passing iterative detection, forced convergence, low complexity

TN911

：A

10.11959/j.issn.1000-0801.2017213

王瓊（1971-），女，重慶郵電大學通信與信息工程學院正高級工程師、碩士生導師，主要研究方向為移動通信。

葉偉（1992-），男，重慶郵電大學通信與信息工程學院碩士生，主要研究方向為大規模MIMO系統中信號檢測技術。

吉明明（1992-），男，重慶郵電大學通信與信息工程學院碩士生，主要研究方向為非正交多址接入技術。

2017-05-10；

：2017-06-29