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

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

1 引言

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

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

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

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

2 系統(tǒng)模型

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

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

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

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

(1)

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

(2)

并受以下條件約束

(3)

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

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

(4)

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

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

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

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

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

3.1 種群個體初始化

根據系統(tǒng)中子載波的數量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 種群的適應度計算

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

(7)

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

(8)

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

(9)

圖2 種群個體初始化結果示意圖

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

(10)

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

3.3 選擇復制階段

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

(11)

3.4 交叉變異階段

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

否則，執(zhí)行

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

3.5 基因突變階段

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

(12)

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

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

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

4 仿真與分析

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

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

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

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

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

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

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

圖7 當公平度閾值ε=0.99時各算法的平均公平度

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

5 結論

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