一種基于遺傳算法的干擾鏈路選擇方法

孟 娟，洪 利，李亞南，韓智明，郭麗麗

（防災(zāi)科技學(xué)院防災(zāi)儀器系 三河 065201）

1 引言

干擾是無(wú)線通信面臨的關(guān)鍵問(wèn)題之一，其限制了無(wú)線通信系統(tǒng)的吞吐量，降低了無(wú)線頻譜的利用率。干擾對(duì)齊（interference alignment）技術(shù)通過(guò)將干擾信號(hào)壓縮到更低維度的信號(hào)空間，增加期望信號(hào)占據(jù)的信號(hào)空間維度，能夠極大地提高無(wú)線通信系統(tǒng)的信道容量。理論上，在K用戶(hù)干擾信道中，干擾對(duì)齊技術(shù)能使系統(tǒng)的總自由度比傳統(tǒng)正交化干擾管理方式增加K/2倍[1]。在理論上，干擾對(duì)齊可在時(shí)域[1]、頻域[2]、空間域[3,4]、幅度域，甚至復(fù)數(shù)域中進(jìn)行。在多用戶(hù)MIMO(multiple input multiple output,MIMO)系統(tǒng)中，通過(guò)預(yù)編碼技術(shù)實(shí)現(xiàn)干擾信號(hào)在空間域中的對(duì)齊，是實(shí)際中最容易實(shí)現(xiàn)的干擾對(duì)齊技術(shù)，成為干擾對(duì)齊研究的熱點(diǎn)[3,4]；在多蜂窩MIMO網(wǎng)絡(luò)中，干擾對(duì)齊技術(shù)能夠有效消除小區(qū)內(nèi)干擾和小區(qū)間干擾，以提高系統(tǒng)的總吞吐量[5,6]。當(dāng)小區(qū)數(shù)量較多時(shí)，為實(shí)現(xiàn)完全干擾對(duì)齊，發(fā)射機(jī)或接收機(jī)必須配置大量天線，導(dǎo)致系統(tǒng)變得難以實(shí)現(xiàn)。然而在實(shí)際的多小區(qū)網(wǎng)絡(luò)中，由于移動(dòng)終端的隨機(jī)分布，其與基站間的距離相差較大，也導(dǎo)致小區(qū)間干擾有強(qiáng)有弱。當(dāng)天線配置不足以實(shí)現(xiàn)完全干擾對(duì)齊時(shí)，僅對(duì)部分較強(qiáng)的干擾鏈路進(jìn)行干擾對(duì)齊，也可能取得接近最優(yōu)的系統(tǒng)性能，但所需要的天線數(shù)量將大大降低。然而，當(dāng)前關(guān)于部分干擾對(duì)齊的研究主要是基于預(yù)先確定的部分拓?fù)浣Y(jié)構(gòu)，并沒(méi)有解決如何選擇干擾鏈路的問(wèn)題[7,8]。參考文獻(xiàn)[9]對(duì)空間相關(guān)蜂窩網(wǎng)絡(luò)部分干擾對(duì)齊進(jìn)行了研究，但其復(fù)雜性過(guò)高而難以應(yīng)用到實(shí)際系統(tǒng)中。而參考文獻(xiàn)[10]基于移動(dòng)用戶(hù)的分布提出了一種基于分組的部分干擾對(duì)齊機(jī)制，但該算法性能相對(duì)較低，并沒(méi)有充分利用干擾對(duì)齊技術(shù)的優(yōu)勢(shì)。

在部分干擾對(duì)齊技術(shù)的研究中，如何合理選擇最優(yōu)的干擾鏈路進(jìn)行干擾對(duì)齊，合理地利用有限的天線資源，是需要重點(diǎn)研究的問(wèn)題。在對(duì)干擾鏈路選擇問(wèn)題進(jìn)行建模的基礎(chǔ)上，本文提出了一種基于遺傳算法的干擾鏈路選擇機(jī)制，在給定的天線數(shù)量條件下，能夠通過(guò)部分干擾對(duì)齊技術(shù)實(shí)現(xiàn)更優(yōu)的系統(tǒng)性能，最后通過(guò)仿真分析證明算法的優(yōu)勢(shì)。

2 系統(tǒng)模型

設(shè)多小區(qū)網(wǎng)絡(luò)中有G個(gè)小區(qū)，為簡(jiǎn)化分析，設(shè)每個(gè)小區(qū)中有1個(gè)基站和K個(gè)移動(dòng)終端。基站和移動(dòng)終端分別配置M和N根全向天線。本文僅研究下行鏈路，且設(shè)每個(gè)用戶(hù)的自由度為D。設(shè)小區(qū)g中的第k個(gè)用戶(hù)為(g,k)，其接收信號(hào)為：

其中，式（1）右邊第一項(xiàng)為期望信號(hào)，第二項(xiàng)為小區(qū)內(nèi)干擾，第三項(xiàng)為小區(qū)間干擾，最后一項(xiàng)為噪聲。其中xg,k=且為移動(dòng)終端(g,k)的第d個(gè)子數(shù)據(jù)流。為對(duì)移動(dòng)終端(g,k)的預(yù)編碼矩陣為移動(dòng)終端(g,k)的接收重組矩陣。為從基站g’到移動(dòng)終端(g,k)的信道狀態(tài)矩陣，且為塊衰落信道，其由路徑損耗和兩部分組成，即小尺度衰落的元素為獨(dú)立同分布的零均值單位方差隨機(jī)變量。路徑損耗是無(wú)線信號(hào)傳輸距離與信號(hào)載波頻率的函數(shù)，單位為dB。本文采用國(guó)際電信聯(lián)盟無(wú)線通信局（Radiocommunication Sector of the International Telecommunication Union,ITU-R）提出的信道模型，如下所示：

3 多小區(qū)網(wǎng)絡(luò)部分干擾對(duì)齊

3.1 問(wèn)題描述

對(duì)于大規(guī)模的多小區(qū)網(wǎng)絡(luò)，要滿(mǎn)足完全干擾對(duì)齊的可行性條件，必須要在基站或移動(dòng)端配置足夠數(shù)量的天線[11]。當(dāng)天線數(shù)量不足以實(shí)現(xiàn)完全干擾對(duì)齊時(shí)，可以?xún)H將部分較強(qiáng)的干擾鏈路對(duì)齊到更低維度的信號(hào)空間，而將其他干擾作為加性噪聲處理。通過(guò)部分干擾對(duì)齊，基于有限的天線數(shù)量，可以選擇性地消除部分干擾信號(hào)以獲得較高的系統(tǒng)性能。當(dāng)然，為了實(shí)現(xiàn)部分干擾對(duì)齊，需要配置一個(gè)服務(wù)器從其他用戶(hù)收集信道狀態(tài)信息 （channel state information,CSI），計(jì)算預(yù)編碼矩陣和接收重組矩陣并發(fā)送到相應(yīng)的基站。具體細(xì)節(jié)可參考文獻(xiàn)[7]，在此不再贅述。

要使移動(dòng)終端(g,k)獲得最優(yōu)的傳輸速率，需要求解最優(yōu)的預(yù)編碼矩陣與干擾選擇標(biāo)志。在固定干擾選擇標(biāo)志的條件下，若可行性條件滿(mǎn)足，可將干擾對(duì)齊作為求解最優(yōu)預(yù)編碼矩陣和接收重組矩陣的方法，則最優(yōu)系統(tǒng)設(shè)計(jì)問(wèn)題可建模為一個(gè)混合整數(shù)雙層非線性規(guī)劃問(wèn)題：

其中fIA為基于干擾對(duì)齊設(shè)計(jì)最優(yōu)預(yù)編碼矩陣的函數(shù)。式(4)所示的最優(yōu)化問(wèn)題中，干擾選擇標(biāo)志的設(shè)計(jì)依賴(lài)于預(yù)編碼矩陣，而預(yù)編碼矩陣的設(shè)計(jì)又依賴(lài)于干擾選擇標(biāo)志。這種分層的結(jié)構(gòu)正是雙層規(guī)劃的主要特點(diǎn)。

3.2 基于部分干擾拓?fù)浣Y(jié)構(gòu)的干擾對(duì)齊

式(5)與多小區(qū)網(wǎng)絡(luò)干擾對(duì)齊約束條件類(lèi)似，而針對(duì)多小區(qū)網(wǎng)絡(luò)的干擾對(duì)齊，學(xué)術(shù)界提出了多種求解方法[12～14]，由于篇幅限制，在此不再贅述。

4 干擾鏈路選擇

為獲得最優(yōu)的系統(tǒng)吞吐量，必須求解式(4)所示的混合整數(shù)雙層非線性規(guī)劃問(wèn)題。雙層規(guī)劃問(wèn)題通常難以求解，最簡(jiǎn)單的線型規(guī)劃已被證明是強(qiáng)NP難問(wèn)題。遺傳算法（genetic algorithm,GA）是由Holland J H基于生物遺傳進(jìn)化機(jī)制提出的一種智能優(yōu)化算法，它通過(guò)模擬物種的遺傳與進(jìn)化過(guò)程，能夠有效地求解各類(lèi)復(fù)雜優(yōu)化問(wèn)題，其求解最優(yōu)可行解的可行性由模式定理得到保證。由于其簡(jiǎn)單高效的特點(diǎn)，遺傳算法在無(wú)線通信中也得到了廣泛的應(yīng)用[15]，因此本文采用遺傳算法進(jìn)行干擾鏈路的選擇。

4.1 遺傳算法相關(guān)參數(shù)和操作定義

4.1.1 遺傳算法基本參數(shù)

在本文的遺傳算法實(shí)現(xiàn)中，設(shè)種群的大小為popSize，交叉概率為Pc，變異概率為Pm，最大進(jìn)化代數(shù)為maxIA。

4.1.2 染色體編碼

4.1.3 染色體校驗(yàn)

需要注意的是，染色體的編碼還受到干擾對(duì)齊可行性條件的約束，否則函數(shù)fIA不能求得最優(yōu)的發(fā)送預(yù)編碼矩陣和接收重組矩陣，導(dǎo)致系統(tǒng)總?cè)萘康南陆怠Ｓ蓞⒖嘉墨I(xiàn)[7]可知染色體編碼必須滿(mǎn)足：

不滿(mǎn)足式（6）約束的染色體稱(chēng)為奇異染色體。

4.1.4 初始化種群

要保證遺傳算法的正常有效進(jìn)行，在算法初始化階段，需要生成一定數(shù)量的染色體。傳統(tǒng)遺傳算法一般采用隨機(jī)生成的方式，但在干擾鏈路選擇中，這種完全隨機(jī)的辦法不利于算法的快速收斂。從提高系統(tǒng)容量的角度，應(yīng)優(yōu)先選擇較強(qiáng)的干擾鏈路進(jìn)行干擾對(duì)齊。因此，在初始化過(guò)程中，對(duì)強(qiáng)干擾鏈路以較大的概率選中，而對(duì)于弱干擾鏈路給予較小的選中概率，這樣在保證種群多樣性的同時(shí)又提高了初始種群的質(zhì)量。與此同時(shí)，種群的初始化還需要滿(mǎn)足染色體的可行性。綜上所述，本文采用的種群初始化算法如下所示。

算法1種群初始化算法

步驟1坌1≤g’≤G，計(jì)算每個(gè)從基站g’到移動(dòng)終端(g,k)∈的初始化概率：

步驟3初始化染色體s，s為G×G×K的矩陣，且對(duì)于s(g’,g,k)，如果鏈路(g’,g,k)被選中對(duì)齊，則置s(g’,g,k)為0，否則置s(g’,g,k)為1。

步驟4若生成的染色體數(shù)量達(dá)到種群規(guī)模，則算法結(jié)束，否則轉(zhuǎn)至步驟2。

4.1.5 適度評(píng)價(jià)

對(duì)于確定的干擾鏈路選擇方案，可利用函數(shù)fIA求出一組最優(yōu)發(fā)送預(yù)編碼矩陣和接收濾波矩陣，在此基礎(chǔ)上，由式(3)求出系統(tǒng)吞吐量作為適應(yīng)度評(píng)價(jià)準(zhǔn)則fitness(s)，系統(tǒng)吞吐量越大，則適應(yīng)度越高。

4.1.6 選擇操作

根據(jù)計(jì)算出的適應(yīng)度函數(shù)，采用輪盤(pán)賭的方式隨機(jī)選擇一些染色體構(gòu)成新的種群，為提高算法收斂的速度，原種群中適應(yīng)度函數(shù)最高的染色體不參與輪盤(pán)賭，直接復(fù)制到新的種群中。在輪盤(pán)賭中，每條染色體被選中的概率為：

4.1.7 交叉操作

采用雙親雙子交叉法，以交叉概率Pc在種群中隨機(jī)選擇兩個(gè)染色體s1和s2，根據(jù)鏈路選擇標(biāo)志為多維矩陣的特點(diǎn)，先將s1和s2拉直為矢量，隨機(jī)選擇交叉點(diǎn)進(jìn)行交叉，再將得到的矢量還原為G×G×K的矩陣。需要說(shuō)明的是，交叉操作可能產(chǎn)生奇異染色體，因此交叉之后必須對(duì)其進(jìn)行校驗(yàn)，若為奇異染色體，則重新選擇交叉點(diǎn)進(jìn)行交叉。

4.1.8 變異操作

為提高算法尋優(yōu)的能力，對(duì)染色體的每一位均以變異概率進(jìn)行變異操作，即通過(guò)將該位置的值取反來(lái)產(chǎn)生新的個(gè)體。與交叉操作類(lèi)似，變異操作同樣有可能產(chǎn)生奇異染色體。因此也必須對(duì)新的染色體進(jìn)行校驗(yàn)，若為奇異染色體，則不發(fā)生變異。

4.2 基于遺傳算法的干擾鏈路選擇

本文提出的基于GA的干擾鏈路選擇算法如下所示。

算法2基于GA的干擾鏈路選擇算法

步驟1參數(shù)初始化。對(duì)遺傳算法參數(shù)進(jìn)行初始化操作，包括種群數(shù)量popSize、變異概率Pc、變異概率Pm、最大進(jìn)化代數(shù)maxIA；

步驟2種群初始化。隨機(jī)生成數(shù)量為popSize的非奇異染色體；

步驟3計(jì)算每個(gè)個(gè)體的適應(yīng)度函數(shù)fitness；

步驟4判斷是否滿(mǎn)足算法終止條件，若滿(mǎn)足條件則轉(zhuǎn)到步驟9；否則轉(zhuǎn)到步驟5。采用復(fù)合終止條件，只要滿(mǎn)足設(shè)定的收斂條件或達(dá)到最大進(jìn)化代數(shù)，則視為算法滿(mǎn)足終止條件；

步驟5執(zhí)行選擇操作，生成新的種群；

步驟6依概率Pm執(zhí)行交叉操作；

步驟7依概率Pc按位執(zhí)行變異操作；

步驟8計(jì)算每個(gè)個(gè)體的適應(yīng)度函數(shù)fitness，轉(zhuǎn)至步驟4；

步驟9輸出最優(yōu)的染色體及相應(yīng)的發(fā)送預(yù)編碼矩陣和接收重組矩陣。

5 仿真分析

為驗(yàn)證本文提出算法的有效性，本文將算法與完全干擾對(duì)齊算法、經(jīng)典的多小區(qū)網(wǎng)絡(luò)匹配濾波算法[16]、僅相鄰小區(qū)干擾鏈路被消除的部分干擾對(duì)齊算法所達(dá)到的容量進(jìn)行比較。仿真網(wǎng)絡(luò)結(jié)構(gòu)為19個(gè)六邊形多小區(qū)網(wǎng)絡(luò)，其中每個(gè)小區(qū)內(nèi)包含1個(gè)位于小區(qū)中心的基站和2個(gè)移動(dòng)終端。多蜂窩網(wǎng)絡(luò)干擾對(duì)齊的目標(biāo)是提高小區(qū)邊緣用戶(hù)的吞吐量，因此設(shè)移動(dòng)終端位于半徑為0.9r～r的環(huán)型區(qū)域。采用Montecarlo方法隨機(jī)生成100組小尺度衰落，并計(jì)算總吞吐量取平均值。

圖1為4種算法小區(qū)總吞吐量的比較，其中本文算法實(shí)現(xiàn)干擾對(duì)齊的干擾鏈路數(shù)量為12，每個(gè)小區(qū)內(nèi)移動(dòng)終端數(shù)量K=2，每個(gè)用戶(hù)自由度d=1，小區(qū)半徑r=500 m。當(dāng)發(fā)送功率小于25 dBm時(shí)，本文提出的基于遺傳算法的干擾鏈路選擇算法性能與完全干擾對(duì)齊基本相同，均低于傳統(tǒng)匹配濾波算法。而當(dāng)發(fā)送功率大于25 dBm時(shí)，兩種干擾對(duì)齊算法性能均優(yōu)于匹配濾波算法。而本文算法性能低于完全干擾對(duì)齊，但完全干擾對(duì)齊需要配置的天線數(shù)量為(G-1)K2d+Kd=74，而本文算法需要的天線數(shù)量?jī)H為26，遠(yuǎn)少于完全干擾對(duì)齊所需要的天線數(shù)量。匹配濾波算法僅從期望信號(hào)功率最大化的角度進(jìn)行預(yù)編碼，完全忽略了干擾信號(hào)的影響，因此在干擾信號(hào)較弱時(shí)性能較好，但在干擾信號(hào)較強(qiáng)時(shí)，則系統(tǒng)吞吐量遠(yuǎn)低于干擾對(duì)齊算法。由圖1中還可以看出，當(dāng)僅考慮基站對(duì)相鄰小區(qū)移動(dòng)終端的干擾時(shí)，系統(tǒng)性能不僅遠(yuǎn)低于干擾對(duì)齊，還低于匹配濾波算法，這說(shuō)明在多蜂窩網(wǎng)絡(luò)中，僅對(duì)相鄰小區(qū)間的干擾信號(hào)進(jìn)行消除，是不能達(dá)到最優(yōu)系統(tǒng)性能的。

圖1 算法吞吐量性能對(duì)比

圖2為本文算法與參考文獻(xiàn)[10]提出的基于用戶(hù)分組的部分干擾對(duì)齊算法對(duì)比。根據(jù)參考文獻(xiàn)[10]的圖2中的系統(tǒng)配置，采用三元組(7,12,1)表示系統(tǒng)由7個(gè)小區(qū)組成，而每個(gè)小區(qū)內(nèi)用戶(hù)數(shù)量為12，且每個(gè)用戶(hù)傳輸1個(gè)數(shù)據(jù)流。理論上，若采用參考文獻(xiàn)[10]算法，每個(gè)基站能夠?qū)崿F(xiàn)12個(gè)干擾鏈路對(duì)齊并消除干擾，因此仿真中設(shè)對(duì)齊的干擾鏈路數(shù)量為12。從圖2中可以看出，本文所提的算法所獲得的系統(tǒng)吞吐量要遠(yuǎn)高于參考文獻(xiàn)[10]的算法，這是因?yàn)樵诒疚乃岬乃惴ㄖ校邮諡V波器能夠消除小區(qū)的所有用戶(hù)間干擾；但在參考文獻(xiàn)[10]所提算法中，接收濾波器僅能夠消除分組內(nèi)部的用戶(hù)間干擾，而同小區(qū)內(nèi)部其他組用戶(hù)產(chǎn)生的用戶(hù)間干擾會(huì)嚴(yán)重降低用戶(hù)的SINR，從而導(dǎo)致系統(tǒng)吞吐量的降低。

圖2 本文算法與參考文獻(xiàn)[10]算法對(duì)比

6 結(jié)束語(yǔ)

在實(shí)際多小區(qū)網(wǎng)絡(luò)中，基站端的天線數(shù)量往往不足以實(shí)現(xiàn)完全干擾對(duì)齊，限制了系統(tǒng)整體性能的提升。針對(duì)網(wǎng)絡(luò)中干擾信號(hào)衰減非均勻的特性，本文提出了一種基于遺傳算法的干擾鏈路選擇算法，選擇調(diào)度合理的干擾鏈路進(jìn)行部分干擾對(duì)齊，以達(dá)到最優(yōu)的系統(tǒng)性能。仿真實(shí)驗(yàn)表明，本文提出的算法能夠以較少的天線數(shù)量獲得較好的系統(tǒng)性能。但是，本文結(jié)論是在沒(méi)有考慮信道估計(jì)和反饋的誤差條件下得到的，對(duì)包括信道估計(jì)、反饋和干擾鏈路調(diào)度在內(nèi)的系統(tǒng)性能進(jìn)行綜合研究和評(píng)估，還需要進(jìn)一步深入研究。

1 Cadambe R,Jafar S.Interference alignment and degrees of freedom of the K-user interference channel.IEEE Transactions on Information Theory,2008,54(8):3425～3441

2 Suh C,Tse D.Interference alignment for cellular networks.Proceedings of 46th Annual Allerton Conference on Communication,Control,and Computing,Monticello,IL,USA,2008:1037～1044

3 Gomadam K,Cadambe V,Jafar S.A distributed numerical approach to interference alignment and applications to wireless interference networks.IEEE Transactions on Information Theory,2011,57(6):3309～3322

4 章?lián)P,周正,石磊等.基于嚴(yán)格勢(shì)博弈的干擾對(duì)齊.北京郵電大學(xué)學(xué)報(bào),2013,36(2):50～54 Zhang Y,Zhou Z,Shi L,et al.Interference alignment based on exact potential game.Journal of Beijing University of Posts and Telecommunications,2013,36(2):50～54

5 Suh C,Ho M,Tse D.Downlink interference alignment.IEEE Transactions on Communications,2011,59(9):2616～2626

6 章?lián)P,周正,石磊等.蜂窩網(wǎng)絡(luò)下行鏈路單反饋干擾對(duì)齊算法研究.電子與信息學(xué)報(bào),2012,34(12):2816～2822 Zhang Y,Zhou Z,Shi L,et al.Interference alignment with single feedback for downlink cellular networks.Journal of Electronics & Information Technology,2012,34(12):2816～2822

7 Guillaud M,Gesbert D.Interference alignment in partially connected interfering multiple-access and broadcast channels.Procreedings of IEEE Global Telecommunications Conference(GLOBECOM),Houston,TX,USA,2011:1～5

8 Westreicher M,Guillaud M.Interference alignment over partially connected interference networks:application to the cellular case.Proceedings of IEEE Wireless Communications and Networking Conference:PHY and Fundamentals,Paris,France,2012:647～651

9 Rao X,Ruan L,Lau V K N.Limited feedback design for interference alignment on MIMO interference networks with heterogeneous path loss and spatial correlations.IEEE Transactions on Signal Processing,2013,61(10):2598～2607

10 Zhang W F,Yu Y,Wang C,et al.Partial interference alignment for multi-cell and multi-user MIMO downlink transmission.Proceedings of IEEE 78th Vehicular Technology Conference(VTC Fall),Las Vegas,NV,USA,2013:1～5

11 Liu T T,Yang C Y.On the feasibility of linear interference alignment for MIMO interference broadcast channels with constantcoefficients.IEEE Transactions on Signal Processing,2013,61(9):2178～2191

[12]Shin W,Lee N,Lim J B,et al.On the design of interference alignment scheme for two-cell MIMO interfering broadcast channels.IEEE transactions on Wireless Communications,2011,10(2):437～442

13 Liu T T,Yang C Y.Interference alignment transceiver design for MIMO interference broadcast channels.Proceedings of IEEE Wireless Communications and Networking Conference(WCNC),Shanghai,China,2012:641～646

14 Tang J,Lambotharan S.Interference alignment techniques for MIMO multi-cell interfering broadcast channels.IEEE Transactions on Communications,2013,61(1):164～175

15 張養(yǎng)瑞，李云杰，高梅國(guó).協(xié)同干擾資源優(yōu)化分配模型及算法.系統(tǒng)工程與電子技術(shù),2014,36(9):1744～1749 Zhang Y R,Li Y J,Gao M G.Optimal assignment model and solution of cooperative jamming resources.Systems Engineering and Electronics,2014,36(9):1744～1749

16 Pan Z,Wong K,Ng T.Generalized multiuser orthogonal space-division multiplexing.IEEE transactions on Wireless Communications,2004,3(6):1969～1973