基于混合遺傳算法的OFDMA資源分配方法

孫 明，翟康樂，曹 偉，張 輝

(齊齊哈爾大學(xué)計算機與控制工程學(xué)院，黑龍江 齊齊哈爾 161006)

1 引言

在過去的二十年中，隨著手機等電子設(shè)備的逐漸普及，人們對無線網(wǎng)絡(luò)有了更高的需求。但頻譜資源作為無線資源的稀缺資源早已成為不爭的事實，因此，如何高效利用頻譜資源已成為無線通信技術(shù)的重要研究內(nèi)容。

正交頻分多址(Orthogonal Frequency Division Multiple Access，OFDMA)[1，2]是一種多址接入技術(shù)，它是將高速傳輸?shù)臄?shù)據(jù)帶寬劃分成相互正交、互不重疊的低速傳輸?shù)淖虞d波集，能夠動態(tài)將子載波分配給需要的用戶并有效降低信號間的干擾[3]。目前，在速率自適應(yīng)(Rate adaptive，RA)準(zhǔn)則上，多用戶OFDMA系統(tǒng)自適應(yīng)資源分配中的系統(tǒng)速率和用戶間公平度已經(jīng)有若干成果[4-11]。例如，Shen等[8]提出的算法在實現(xiàn)最大化系統(tǒng)速率的同時也保證了速率比例的公平，仿真結(jié)果表明該算法幾乎實現(xiàn)了絕對公平，但忽略了系統(tǒng)速率的提升。Wong等[9]基于Shen的算法提出了一種通過近似速率比例系數(shù)來提升系統(tǒng)速率的分配算法，然而該算法卻犧牲了部分公平度；在Wong的基礎(chǔ)上，袁建國、汪照等通過對功率分配采用人工蜂群算法[4]或魚群算法[7]進(jìn)一步提高系統(tǒng)速率。雖然文獻(xiàn)[4，7，9]通過犧牲公平度的方式提高了系統(tǒng)速率，但都無法保障所要求的用戶間比例公平。

設(shè)置公平度閾值可實現(xiàn)公平度和系統(tǒng)速率的折中，能夠在保證公平度的同時有效地提高系統(tǒng)速率和系統(tǒng)靈活性[6，10，11]。例如，張春發(fā)等[6]基于公平度閾值在等功率子載波分配階段對子載波采用貪婪算法進(jìn)行分配，再對其功率采用粒子群算法進(jìn)行分配，來保證系統(tǒng)的公平度閾值；然而由于粒子群算法的“早熟”，基于粒子群算法的功率分配極易降低系統(tǒng)的速率水平[12]。Sharma等提出一種人工蜂群算法[10]和遺傳算法[11]對子載波進(jìn)行分配的算法，該算法能夠從全局尋優(yōu)對子載波進(jìn)行分配；然而，該算法隨著子載波數(shù)量的增加，需要優(yōu)化的維度也隨之增加，增加了優(yōu)化問題的難度，極易降低優(yōu)化性能。

針對以上不足，本文提出一種基于混合遺傳算法的OFDMA資源分配方法，該方法將基于速率比例公平的貪婪子載波分配方法有效地嵌入遺傳算法中，實現(xiàn)了貪婪算法局部尋優(yōu)能力和遺傳算法全局尋優(yōu)能力的有機結(jié)合。所提出的方法不僅能使種群個體在初始化時具有一定的公平度水平，還能有效減少個體待優(yōu)化維度的數(shù)量并降低了計算復(fù)雜度。仿真結(jié)果表明，所提出的方法可在子載波分配階段就能滿足公平度閾值，而且還能有效提高系統(tǒng)速率。

2 系統(tǒng)模型

本文考慮如圖1所示的下行多用戶OFDM系統(tǒng)模型。在發(fā)送端，通過用戶信息和對K個用戶的信道估計來獲取實時信道狀態(tài)信息(CSI)，再利用自適應(yīng)資源分配方法對各個子信道進(jìn)行分配來獲得不同用戶的分配信息，并將信息進(jìn)行OFDM調(diào)制發(fā)送到接收端，接收端利用自適應(yīng)解調(diào)器對信息進(jìn)行解調(diào)來得到相應(yīng)信息。

圖1 下行多用戶OFDMA系統(tǒng)

假定某OFDMA系統(tǒng)共有K個用戶和N個子載波，總的可用功率為Ptotal，且所有子載波的瞬時增益都是已知的。

系統(tǒng)在滿足總功率約束的條件下，對子載波進(jìn)行分配以最大限度的提高總?cè)萘?。其中用戶k的容量Rk為

(1)

RA準(zhǔn)則下的系統(tǒng)容量最大化可表示為

(2)

并受以下條件約束

(3)

其中hk，n為信道增益，N0為加性高斯白噪聲的功率譜密度，B為總信道寬度。C1表示子載波的功率和不超過總的可用功率Ptotal；C2表明每一個子載波分配的功率必須大于等于0；C3中ρk，n∈{0，1}表示該子載波是否分配給用戶；C4表示同一個子載波只能分配給一個用戶；C5表示公平度閾值約束。F為公平度計算公式；ε是公平度閾值；λk是用戶k的預(yù)定數(shù)據(jù)速率比例值。F的變化范圍從0到1，F(xiàn)的值越接近于1表示用戶之間的公平度越大。如果式(4)嚴(yán)格成立，則F等于1。

R1：R2：R3：…：Rk=λ1：λ2：λ3：…：λk

(4)

由式(2)和式(3)可知，以上問題為一個非凸優(yōu)化問題。本文將貪婪算法嵌入遺傳算法中，提出了一種混合遺傳算法，通過貪婪算法為遺傳算法個體維持一定的公平度水平、減少遺傳算法的搜索維度，以降低遺傳算法的計算復(fù)雜度、提高遺傳算法的優(yōu)化性能。

3 基于混合遺傳算法的OFDMA資源分配方法

遺傳算法是一種模仿大自然生物體進(jìn)化規(guī)律的啟發(fā)式算法，其中一個種群個體對應(yīng)一個優(yōu)化問題的解，而種群個體不斷進(jìn)化的過程對應(yīng)于優(yōu)化問題的求解過程，將遺傳算法用于子載波分配時，種群個體的維度大小由子載波的數(shù)量決定；然而，規(guī)模較大的子載波分配無疑會增加遺傳算法優(yōu)化的難度，進(jìn)而降低優(yōu)化解的質(zhì)量。

為了使遺傳算法能有效保障公平度閾值并提高OFDMA系統(tǒng)的子載波利用率和系統(tǒng)容量，本文基于速率比例公平的貪婪子載波分配方法可獲得較高公平度的特點，將基于速率比例公平的貪婪子載波分配方法用于遺傳算法的個體初始化上，提出了一種保障公平度閾值的基于混合遺傳算法的資源分配方法，即首先對種群個體進(jìn)行分組并為個體分組設(shè)置個體更新量，并在此基礎(chǔ)上采用基于速率比例公平的貪婪子載波分配方法初始化種群個體，然后再利用所設(shè)置的個體更新量，對個體的相應(yīng)維度進(jìn)行搜索和更新。

本文所提出的保障公平度閾值的混合遺傳資源分配算法包括種群個體初始化，個體的適應(yīng)度計算，選擇復(fù)制階段，交叉變異階段，基因突變階段，最優(yōu)個體儲存等部分，現(xiàn)對每一部分進(jìn)行闡述。

3.1 種群個體初始化

根據(jù)系統(tǒng)中子載波的數(shù)量N，本文將種群個體定義為維度H等于N的向量，即H=N。記V為種群的大小，xi為第i個種群個體，xi，h為第i個種群個體xi在維度h上的元素，其中xi，h∈[1，K]，i∈{1，2，…，V}，h∈{1，2，…，H}。

本文將種群個體初始化分為以下3步：

Step 2.2：

n=arg maxn∈Γ{|hk，n|2}，

Rk=Rk+log2(1+pT|hk，n|2/(N0B))，

Γ=Γ-{n}，k=k+1；}

Step 2.3：

k=arg mink∈{1，2，…，K}{Rk/λk}，

n=arg maxn∈Γ{|hk，n|2}，

Rk=Rk+log2(1+pT|hk，n|2/(N0B))，

Γ=Γ-{n}。}

(5)

式中，km∈{1，2，…，K}，nm∈{1，2，…，N}。

(6)

3.2 種群的適應(yīng)度計算

由于所要求解的多用戶OFDMA資源分配問題(6)-(9)是約束優(yōu)化問題，因此設(shè)計的適應(yīng)度函數(shù)需要考慮滿足約束的可行解和不滿足約束的非可行解，并能夠引導(dǎo)遺傳算法從不滿足約束的非可行解空間過渡到滿足約束的可行解空間。同時，設(shè)計的適應(yīng)度函數(shù)應(yīng)該遵循較好解具有較大適應(yīng)度的原則。基于上述考慮，本文構(gòu)建的適應(yīng)度函數(shù)如式(7)：

(7)

其中，F(xiàn)(xi)是種群個體xi的適應(yīng)度；x′i是對種群個體xi的元素進(jìn)行四舍五入后得到的向量；f(x′i)表示為

(8)

其中，fr為一正常數(shù)；β(·)=F-ε為公平度閾值約束函數(shù)；Xi表示由向量x′i轉(zhuǎn)換得到的K行N列的子載波分配矩陣，由向量x′i到矩陣Xi的轉(zhuǎn)換如式(9)所示

(9)

圖2 種群個體初始化結(jié)果示意圖

其中[Xi]k，n為子載波分配矩陣Xi的第k行、第n列的元素，[x′i]n為向量x′i在維度n上的元素。Ζ(Xi)如式(10)所示

(10)

首先，由式(7)、(8)可以看出，滿足公平度閾值約束的可行解和不滿足公平度閾值約束的非可行解通過式(8)影響適應(yīng)度函數(shù)式(7)，且滿足公平度閾值約束的可行解的適應(yīng)度值大于不滿足公平度閾值約束的非可行解的適應(yīng)度值；其次，由(7)、(8)、(10)不難發(fā)現(xiàn)，在滿足公平度閾值約束的可行解中，較好的可行解有較大的系統(tǒng)容量，且較好的可行解有較大的適應(yīng)度值；最后，由式(7)、(8)可以發(fā)現(xiàn)，在不滿足公平度閾值約束的非可行解中，與較劣的非可行解相比，較好的非可行解也具有較大的適應(yīng)度值。以上分析說明所設(shè)計的適應(yīng)度函數(shù)(7)-(10)體現(xiàn)了較好解具有較大適應(yīng)度的原則，從而有利于引導(dǎo)遺傳算法從不滿足公平度閾值約束的非可行解空間過渡到滿足公平度閾值約束的可行解空間，并能在滿足公平度閾值約束的可行解空間中搜索得到較好的可行解。

3.3 選擇復(fù)制階段

在選擇復(fù)制階段，首先通過式(7)-(10)計算各個種群個體的適應(yīng)度函數(shù)F(xi)，然后根據(jù)個體的F(xi)值從大到小排序并選擇前H/2個種群個體作為親代以輪盤賭的方式選擇復(fù)制生成V個種群個體，其中個體被選擇復(fù)制概率P(xi)，如式(11)所示

(11)

3.4 交叉變異階段

如果rn≥pc，執(zhí)行：

否則，執(zhí)行

圖3 以圖2種群個體3和12為例的個體搜索的計算和更新示意圖

3.5 基因突變階段

在基因突變階段，種群個體中待優(yōu)化的個體維度通過突變概率pm的調(diào)整，小范圍內(nèi)進(jìn)一步搜索的計算和更新，如式(12)所示

(12)

3.6 最優(yōu)個體儲存

在基因突變階段后，從種群中找出適應(yīng)度最大的種群個體，并將該個體保存為當(dāng)前的最優(yōu)解。并判斷遺傳算法當(dāng)前的迭代數(shù)Cycle是否等于最大迭代數(shù)Maxcycle，若等于則停止計算并輸出最優(yōu)解及其對應(yīng)的公平度與系統(tǒng)和速率；否則令Cycle=Cycle+1，并轉(zhuǎn)入選擇復(fù)制階段繼續(xù)執(zhí)行。

由以上步驟可知，本文所提出的混合遺傳算法有效地結(jié)合了貪婪算法的局部尋優(yōu)和遺傳算法的全局尋優(yōu)，因此，與遺傳算法和貪婪算法相比，本文所提出的算法具有尋優(yōu)能力強、靈活性高等特點。

4 仿真與分析

仿真中假設(shè)多用戶OFDMA系統(tǒng)的無線信道采用瑞利衰落信道，信道帶寬B為1M Hz，噪聲的功率譜密度N0為10-8W/Hz，子載波數(shù)N為64，基站總發(fā)射功率Ptatol為1W。為了減少樣本誤差對算法性能的影響，本文不同用戶K產(chǎn)生200個不同的樣本實例，并取其均值比較各種算法的性能。

為了驗證本文提出的算法具有保障公平度閾值的同時提高系統(tǒng)速率的能力，將公平度閾值ε設(shè)置為0.96，并將本文所提出的遺傳算法(Proposed HGA)、Sharma等的遺傳算法(GA)和人工蜂群算法(ABC)、張春發(fā)的粒子群算法(PSO-EQ)以及Wong的貪婪算法(Wong)用于資源分配當(dāng)中去，其中算法Wong沒有設(shè)置公平度閾值。遺傳算法的參數(shù)設(shè)置為種群大小V=40、fr=1、交叉概率pc=0.7、基因突變概率pm=0.01、最大迭代數(shù)為1000，種群個體的分組V′=6，對應(yīng)的個體更新力量分別為1、4、6、8、10、12；速率比例系數(shù)λ1：λ2：…：λK分別為1：1：…：1、8：1：…：1、16：1：…：1，用戶數(shù)K由6逐漸增加到16。

圖4 當(dāng)公平度閾值ε=0.96且速率比例系數(shù)λ1：λ2：…：λK=1：1：…：1時各算法的公平度與和速率

由圖4、圖5和圖6可知隨著用戶數(shù)的增加，相比于各個算法，本文所提算法(Proposed HGA)不僅公平度始終穩(wěn)定在公平度閾值之上，而且系統(tǒng)速率始終大于其它各算法，這說明了本算法具有較強靈活性和尋優(yōu)能力，有效提高了子載波的利用率；其中，算法Wong對等功率子載波采用貪婪算法進(jìn)行分配，因而無法保證公平度，造成其公平度曲線有較大的震蕩起伏現(xiàn)象；算法PSO-EQ由于其子載波分配階段所采用貪婪算法的局限性，以及PSO在功率分配上的“早熟”，導(dǎo)致其無法產(chǎn)生較高的系統(tǒng)速率；算法ABC-OSA、GA隨著速率比例系數(shù)的提升，逐漸無法達(dá)到公平度閾值，且容量也無法進(jìn)一步提升，說明簡單地將ABC-OSA、GA算法應(yīng)用到子載波分配無法有效地提高系統(tǒng)性能。

圖5 當(dāng)公平度閾值ε=0.96且速率比例系數(shù)λ1：λ2：…：λK=8：1：…：1時各算法的公平度與和速率

圖6 當(dāng)公平度閾值ε=0.96且速率比例系數(shù)λ1：λ2：…：λK=16：1：…：1時各算法的公平度與和速率

為了體現(xiàn)在較高公平度閾值時本文所提算法依然具有良好性能，圖7和圖8中給出了本算法在公平度閾值為0.99、用戶數(shù)K=8、以及λ1分別等于1、8、16時與各個算法的公平度和系統(tǒng)速率的比較。通過與各算法比較可知，隨著速率比例系數(shù)λ1的提升，算法ABC和GA的公平度逐漸達(dá)不到公平度閾值，系統(tǒng)速率也逐漸降低；算法PSO-EQ始終滿足公平度閾值，但系統(tǒng)容量卻沒有顯著的提高；而本文所提出的算法滿足公平度閾值的同時依然能保持良好的尋優(yōu)能力，并有效提高對子載波的利用率。主要原因是，本文所提出的混合遺傳算法能夠充分利用貪婪算法局部尋優(yōu)和遺傳算法全局尋優(yōu)的優(yōu)點，既能保障種群個體有較高的公平度水平，又能降低了待優(yōu)化的個體的維度數(shù)量，從而以利于提高子載波利用率和系統(tǒng)容量。

圖7 當(dāng)公平度閾值ε=0.99時各算法的平均公平度

圖8 當(dāng)公平度閾值ε=0.99時各算法的平均系統(tǒng)和速率

5 結(jié)論

為了保障公平度閾值、提高子載波利用率和系統(tǒng)容量，本文提出了一種基于混合遺傳算法的資源分配方法，所提出的資源分配算法充分利用了貪婪算法在局部尋優(yōu)和遺傳算法在全局尋優(yōu)的優(yōu)點，既保障種群個體有較高的公平度水平，又降低了待優(yōu)化的個體的維度數(shù)量，有利于提高子載波利用率和系統(tǒng)容量。仿真結(jié)果表明，所提出的算法能夠在等功率的子載波分配階段即可實現(xiàn)所要求的公平度閾值并能有效地提升系統(tǒng)容量。