多用戶MIMO系統(tǒng)中一種自由度分配算法

高 慧,周欣瑞,吳仁銘,朱 謙

(1.復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院,上海200433; 2.國立清華大學(xué)通訊工程研究所,中國臺灣新竹30013)

·移動互聯(lián)與通信技術(shù)·

多用戶MIMO系統(tǒng)中一種自由度分配算法

高 慧1,周欣瑞2,吳仁銘2,朱 謙1

(1.復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院,上海200433; 2.國立清華大學(xué)通訊工程研究所,中國臺灣新竹30013)

近年來迭代干擾對齊技術(shù)得到了較多的關(guān)注,通過迭代干擾對齊算法可設(shè)計線性預(yù)編碼矩陣,以最大化多輸入多輸出系統(tǒng)的總速率。但目前將自由度(DoF)分配方式作為系統(tǒng)總速率影響因素的研究較少。為此,提出一種DoF分配算法,通過改進(jìn)模擬退火算法從而得到可使系統(tǒng)總速率達(dá)到最大的DoF分配方式。DoF分配問題是組合優(yōu)化問題,采用模擬退火算法可較好地解決該問題。仿真結(jié)果表明,該算法所獲得的系統(tǒng)總速率接近遍歷算法的性能,具有更低的復(fù)雜度。尤其當(dāng)系統(tǒng)變得復(fù)雜(用戶數(shù)目增加,或者天線數(shù)目增加)時,改進(jìn)模擬退火算法的低復(fù)雜度優(yōu)勢更為明顯。

多輸入多輸出;迭代干擾對齊;自由度分配;模擬退火算法;總速率

1 概述

多輸入多輸出(Multiple-input Multiple-output, MIMO)技術(shù)可以在不增加發(fā)射功率和不占用更多頻率資源的情況下,極大地提高系統(tǒng)總速率。因此,自被文獻(xiàn)[1-2]提出以來,已成為無線通信領(lǐng)域的研究熱點。對于多用戶MIMO系統(tǒng),當(dāng)天線數(shù)目及用戶數(shù)量增加時,多用戶干擾會成為制約系統(tǒng)總速率增加的重要因素[3],這點可通過干擾對齊技術(shù)解決。

干擾對齊作為一種有效的干擾管理技術(shù)[4],由于能夠顯著提高系統(tǒng)總速率,因此受到了廣泛關(guān)注[5-6]。它最先由文獻(xiàn)[7]提出,通過在接收方給干擾信號分配一部分可用的資源(時間,頻率,空間)使得所有干擾項目被壓縮在這部分空間。此外,文獻(xiàn)[8]已經(jīng)證明:干擾對齊技術(shù)可使得多用戶MIMO干擾信道的自由度達(dá)到最大。

前人的研究大都是從消除干擾的角度使得多用戶MIMO系統(tǒng)獲得最大總速率,卻忽視了自由度(Degree of Freedom,DoF)分配對系統(tǒng)總速率的影響。本文基于迭代干擾對齊(Iterative Interference Alignment,IIA)技術(shù)[9]探索一種使多用戶MIMO系統(tǒng)的總速率最大化的具有低復(fù)雜度的DoF分配優(yōu)選算法。

對多用戶MIMO干擾信道做DoF分配事實上是一種組合優(yōu)化問題。該類問題即是解決具有很多獨立變量的函數(shù)的最大值或最小值問題。對于組合優(yōu)化問題,直觀的方式是通過遍歷法(Exhausting search,EX)搜尋所有可能解,從而選出最優(yōu)的DoF分配策略。然而,很多組合優(yōu)化問題實質(zhì)上是NP完全問題[10],得到精確解所需的收斂時間隨著問題的規(guī)模增加呈指數(shù)增長。因此,運用啟發(fā)式算法來解決此類NP完全問題是一種行之有效的方法。

模擬退火算法是一種啟發(fā)式的全局優(yōu)化算法,已被應(yīng)用到許多領(lǐng)域。它可以在一個可接受的收斂時間內(nèi)給出一個滿意的次優(yōu)解,相比遍歷算法大大減少了算法的復(fù)雜度及收斂時間。

本文基于迭代干擾對齊[9]技術(shù),旨在通過改進(jìn)的模擬退火算法搜索到可使多用戶MIMO系統(tǒng)總速率最大的DoF分配方案。

2 K-user MIMO干擾信道模型

圖1描述了K-user MIMO干擾高斯信道模型, K-user MIMO干擾信道由K對發(fā)射機(jī)-接收機(jī)組成,每個發(fā)射機(jī)具有M根天線,每個接收機(jī)具有N根天線。假設(shè)信道參數(shù)與時間和頻率無關(guān),一個發(fā)射機(jī)只與與其匹配的接收機(jī)發(fā)送信號,對于其他接收機(jī)而言,該信號是干擾信號。接收機(jī)k的接收信號表達(dá)如下:

其中,yk表示接收機(jī)k收到的信號;Hk,l是接收機(jī)k與發(fā)送機(jī)l之間的平坦衰落信道矩陣;Fl與nl表示預(yù)編碼矩陣和滿足正態(tài)分布的N(0,N0I)加性高斯白噪聲;sk是發(fā)射機(jī)k傳送給接收機(jī)l的信號向量。

令Ω表示所有可能的DoF分配方式的集合,即K-user MIMO干擾信道的DoF域。Si=[s1,sk,…,sK]表示一種具體的DoF方案,其中,sk表示用戶k被分得的DoF數(shù)目。

圖1 K-user MIMO干擾高斯信道

因此可將問題描述如下:讓C:Ω→R表示定義在DoF域上的目標(biāo)函數(shù)(即K用戶MIMO干擾信道的總速率),目標(biāo)是找到一種最佳的DoF分配方式S?,使得對于任意一種 DoF分配方式Si,都有C(Si)＜C(S?)。

文獻(xiàn)[11]已經(jīng)證明對于K-user MIMO干擾系統(tǒng),當(dāng)K≤R時,總自由度數(shù)目可以達(dá)到min(M,N)K;而當(dāng)K＞R時,總自由度數(shù)目為,其中,。因此,DoF搜索域Ω為:

由于min(M,N),本文選取一個較大的上限:min(M,N)。

此外,在文獻(xiàn)[9]提出的迭代式的干擾對齊算法可在不用考慮用戶數(shù)目、獲得CSI的方式以及DoF的分配下獲得預(yù)編碼Fl與干擾空間的正交基Ck,從而將干擾信號壓縮在部分自由度上。

因此,K-user MIMO干擾高斯信道的總速率可以表達(dá)如下:

其中,Fl表示發(fā)送機(jī)的預(yù)編碼;Wk表示接收信號空間的正交基(表示接收機(jī)干擾空間的正交基,是Ck的共軛轉(zhuǎn)置矩陣);與分別表示W(wǎng)kHk,kFk與WkHk,lFl的Frobenius范數(shù)。

綜上所述,可將尋求K-user MIMO系統(tǒng)的最大總速率問題表述為:

3 基于模擬退火算法與IIA的DoF分配

模擬退火的概念源自一個特殊的領(lǐng)域:統(tǒng)計物理學(xué)[12]。退火過程如下:為使一塊固體物質(zhì)達(dá)到最低能量基態(tài),首先將其加溫至其粒子可自由移動,然后徐徐的降溫,粒子會逐漸形成低能級晶格。若降溫速度足夠慢,固體物質(zhì)必會達(dá)到最低能量的基態(tài)。類似的,將不同的DoF分配方式Si看做固體物質(zhì)中的每一個粒子,將對應(yīng)的K-user MIMO系統(tǒng)的總速率C(Si)看做固體物質(zhì)的能量函數(shù),通過緩慢減少模擬溫度進(jìn)行迭代優(yōu)化,則可使系統(tǒng)的總速率最終達(dá)到最大。

本文旨在找到K-user MIMO干擾系統(tǒng)總速率的最大值,有必要對退火算法中的Metroplis概率接受準(zhǔn)則做些調(diào)整。做法如下:

其中,Pij為狀態(tài)接受概率,即表示狀態(tài)Si產(chǎn)生Sj后,接受Sj作為新狀態(tài)的概率;ΔCij表示總速率的增量, ΔCij=C(Sj)-C(Si);Tm為退火溫度,m為迭代次數(shù);C(Si)為K用戶MIMO系統(tǒng)的總速率;Si表示DoF分配方式,Si∈Ω。

除了概率接受準(zhǔn)則,模擬退火算法還需要其他4個重要的因素:

(1)解空間:所有的DoF分配策略,用集合Ω表示,見式(2)。

(2)新解產(chǎn)生函數(shù):候選解一般按照某一概率密度分布函數(shù)對解空間進(jìn)行隨機(jī)采樣所得,本文中選取平均密度分布函數(shù)從Ω中對DoF分配策略采樣。

(3)目標(biāo)函數(shù):K-user MIMO系統(tǒng)所獲得的最大總速率,見式(3)。

(4)冷卻進(jìn)度表:溫度控制著整個退火過程,包括初始溫度、降溫因子及退火終止條件。

1)初始溫度:設(shè)為T0,應(yīng)足夠高以便所有的可行解都能被遍及。然而溫度越高意味著收斂速度越慢。事實上它是一個經(jīng)驗值;

2)降溫因子:設(shè)為r,直接控制了退火算法的收速度,Tm+1=r×Tm(0＜×＜1);

3)終止條件:包含特定溫度(Tm)下熱平衡判決條件(內(nèi)循環(huán))及退火過程的終止判斷(外循環(huán))。在Tm下,如果最新幾次所獲得的目標(biāo)函數(shù)的值的方差在[0,ξ]內(nèi)變化,則認(rèn)為系統(tǒng)在Tm下已達(dá)到熱平衡。ξ是一個很小的正整數(shù)(本文取ξ=0.01)。對于退火過程的終止,如果最新所獲得的一些目標(biāo)函數(shù)值(在極低的幾個溫度下)“足夠平坦”,即目標(biāo)函數(shù)值均方差在[0,ε]內(nèi)浮動(本文中ε=0.01),則認(rèn)為退火結(jié)束。

以上的設(shè)計思想充分表述了模擬退火算法。然而在溫度不為0℃時,跳出區(qū)域最優(yōu)解總有可能會發(fā)生。最終得到的解可能不是最優(yōu)的,因為模擬退火算法是一種概率算法。因此,有必要對模擬退火算法做一些改進(jìn)以便增加獲得最優(yōu)解的概率。

本文為避免搜索過程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當(dāng)前遇到的最優(yōu)解,增加了存儲環(huán)節(jié),將每個Tm溫度下獲得的最優(yōu)解記憶下來。待退火過程結(jié)束后,從中選取出最大值作為最優(yōu)解。

基于模擬退火算法及干擾對齊技術(shù),可使K-user MIMO系統(tǒng)的總速率達(dá)到最大,DoF分配流程如圖2所示。

圖2 基于模擬退火的K-user MIMO系統(tǒng)DoF分配流程

該算法具體步驟如下:

(1)選取模擬退火算法的初始溫度T0,退火系數(shù)r。

(2)從解空間Ω中選取一組DoF分配Sj,計算系統(tǒng)總速率C(Sj)及其改變量ΔCij=C(Sj)-C(Si)。若ΔCij≤0,或者exp(-ΔCij)＞random(0,1)則接受新狀態(tài)Sj令Si=Sj;否則保持Si狀態(tài)。

(3)如果在該溫度下達(dá)到內(nèi)循環(huán)收斂準(zhǔn)則,轉(zhuǎn)到步驟(4);否則轉(zhuǎn)到步驟(2)。

(4)先保存“中間最優(yōu)解”,然后執(zhí)行外循環(huán)收斂準(zhǔn)則,若滿足則退火過程結(jié)束,跳至步驟(5);否則繼續(xù)降溫:Tm+1=r×Tm,轉(zhuǎn)至步驟(2)。

(5)從迭代過程中遇到的所有“中間最優(yōu)解”中,選出最佳解,退火過程結(jié)束。

4 實驗結(jié)果及算法復(fù)雜度分析

本節(jié)給出以下仿真結(jié)果來驗證模擬退火算法的性能。在本文實驗中,K=4,SNR是常量。

圖3刻畫了SA-IIA算法的收斂過程(M=8,N=7,SNR=60 dB,T=30,r=0.9)。在開始時,目標(biāo)函數(shù)值的幅度跳躍很大,這點可由Metropolis算法解釋:在溫度較高時,從最佳值跳到較次的值的概率很大。隨著溫度降至0°C,這種概率也幾乎為0。最終在溫度趨于0°C時,系統(tǒng)總速率收斂到最優(yōu)解。

圖3 模擬退火算法的性能

本文中SA-IIA算法得到的收斂解是30.36,同最優(yōu)解一致;在收斂時間方面,SA-IIA是80.8 s,而EXIIA是317.2 s,因此收斂時間大致是EX-IIA的1/4。

需要說明的是,本文SA-IIA算法在迭代第14次時,搜索到了最優(yōu)解。如若未采用“Best So Far”最終的收斂解是29.36。由此可見,補充搜索確實提高了收斂解的質(zhì)量。

表1給出了不同天線數(shù)目下SA-IIA與EX-IIA的計算量比較,清晰地表明了SA-IIA在計算復(fù)雜度上的優(yōu)勢。事實上,exhausting search的計算次數(shù)是可以預(yù)期的。觀察式(3),執(zhí)行exhausting search所需的計算次數(shù)為min(M,N)K。對于SA-IIA雖然每次收斂次數(shù)并不固定,但是可以由內(nèi)外循環(huán)次數(shù)控制。

表1 模擬退火算法與遍歷法的計算量比較

5 結(jié)束語

本文基于模擬退火算法與迭代干擾對齊算法,提出一種DoF分配方法,即改進(jìn)模擬退火算法。該算法可以大大降低計算復(fù)雜度,縮減收斂時間,并給出一個可滿足需要的次優(yōu)解。并且當(dāng)用戶數(shù)目增加或者天線數(shù)目增加時,本文算法的計算復(fù)雜度具有明顯的優(yōu)勢。

[1] Foschini J G,GansM J.On LimitsofWireless Communications in a Fading Environment when Using Multiple Antennas[J].Wireless Personal Communications,1998,6(3):311-335.

[2] Emre T.Capacity ofMulti-antenna Gaussian Channels[J].European Transactions on Telecommunications, 1999,10(6):585-595.

[3] Shyamnath G,David P S,Dina K.Interference Alignment and Cancellation[J].SIGCOMM Communi-cation Review,2009,39(4):159-170.

[4] Shen H,Lin B,Luo Y,et al.Iterative Minimum Mean Square Error Interference Alignment Scheme for the MIMO X Channel[J].IEICE Transactions on Communications,2011,94(5):1348-1354.

[5] Nosrat M B,AndrewsJG,HeathR W.MIMO Interference Alignment over Correlated Channels with Imperfect CSI[J].IEEE Transactions on Signal Processing,2011,59(6):2783-2794.

[6] 王勤民,張忠培,常青美,等.干擾信道中一種權(quán)值可調(diào)的迭代算法[J].電子與信息學(xué)報,2012,34(12): 2850-2854.

[7] Maddah-Ali M A,MotahariA S,KhandaniA K. Signaling over MIMO Multi-base Systems:Combination of Multi-access and Broadcast Schemes[C]//Proceedings of IEEE International Symposium on Information Theory.Seattle,USA:[s.n.],2006:214-222.

[8] Cadambe V R,Jafar S A.Interference Alignment and the Degrees of Freedom for the K User Interference Channel[J].IEEE Transactions on Information Theory,2008, 54(8):3425-3441.

[9] Peters S,Heath R W.Interference Alignment via Alternating Minimization[C]//Proceedings of ICASSP’09.[S.1.]: IEEE Press,2009:159-167.

[10] Reingold E M,NievergeltJ,Deo N.Combinatorial Algorithms:Theory and Practice[M].Englewood Cliffs, USA:Prentice-Hall,1977.

[11] Gou Tiangao,Jafar S A.Degrees of Freedom of the K UserM×NMIMO Interference Channel[J].IEEE Transactions on Information Theory,2010,56(12): 6040-6057.

[12] Kirkpatrick S,Gelatt C D,Vecchi M P.Optimization by Simulated Annealing[J].Science,1983,220(4598): 671-680.

編輯 索書志

A Degrees of Freedom Allocation Algorithm in Multi-user MIMO System

GAO Hui1,CHOU Hsin Jui2,WU Renming2,ZHU Qian1
(1.School of Information Science and Technology,Fudan University,Shanghai 200433,China; 2.Institute of Communications Engineering,National Tsinghua University,Hsinchu 30013,Taiwan,China)

This paper considers the joint interference alignment and allocation of Degrees of Freedom(DoF)in multiple access K-user Multiple-Input Multiple-Output(MIMO)interference channel to maximize the sum capacity. Because a set of linear precode and corresponding combining matrices can be designed to maximize the sum rate,while joint consideration of sum capacity and distribution of DoF is less addressed.Therefore,this paper proposes an improved DoF allocation algorithm to search ideal DoF allocation which can maximize the sum rate.The essence of DoF allocation is a combinational optimization problem.SA algorithm has notable advantage over this.Simulation results show that the proposed modified SA algorithm achieves sum rate performance near that of the Exhausting search(EX)asymptotically, while the SA has lower computation complexity.Especially,when the system becomes more complicated(increasing user numbers or antennas),the low complexity advantage of SA algorithm is much more notable.

Multiple-input Multiple-output(MIMO);Iterative Interference Alignment(IIA);Degrees of Freedom (DoF)allocation;Simulated Annealing(SA)algorithm;sum-rate

1000-3428(2015)01-0071-04

A

TP391

10.3969/j.issn.1000-3428.2015.01.013

高 慧(1989-),女,碩士,主研方向:無線通信,MIMO技術(shù),無線傳感器網(wǎng)絡(luò);周欣瑞,博士;吳仁銘、朱 謙,副教授。

2014-01-24

2014-03-06 E-mail:huigao11@fudan.edu.cn

中文引用格式:高 慧,周欣瑞,吳仁銘,等.多用戶MIMO系統(tǒng)中一種自由度分配算法[J].計算機(jī)工程,2015, 41(1):71-74.

英文引用格式:Gao Hui,Chou HsinJui,Wu Renming,et al.A Degrees of Freedom Allocation Algorithm in Multi-user MIMO System[J].Computer Engineering,2015,41(1):71-74.