一種改進的多用戶OFDM系統跨層分配優化算法

潘亞芹，張麗，張士兵

（南通大學電子信息學院，江蘇 南通 226001）

一種改進的多用戶OFDM系統跨層分配優化算法

潘亞芹，張麗，張士兵

（南通大學電子信息學院，江蘇 南通 226001）

提出了一種多用戶正交頻分復用系統的跨層資源分配模型，結合了物理層中信道狀態和媒體接入控制層中用戶的隊列信息，能更好地滿足用戶的服務質量要求。改進的混合優化算法結合了遺傳算法與禁忌搜索算法的優點，并且對遺傳算法的交叉因子進行改進，提高了全局搜索能力，能夠更好地收斂于全局最優值，這樣能更好地解決跨層資源分配問題。仿真結果表明，在此模型下利用改進的混合算法能有效地提高系統吞吐量，減小用戶的平均時延，提高服務質量。

OFDM；跨層；資源分配；混合算法

1 引言

隨著無線通信技術的發展，不斷擴展的業務種類要求數據速率、帶寬和 QoS（quality of service，服務質量）不斷地增長。但是，由于無線信道存在著嚴重的多徑衰落，這就在一定程度上限制了數據傳輸速率和用戶QoS的提高。由于OFDM（orthogonal frequency division multiplexing，正交頻分復用）技術具有高速傳輸的速率、抗多徑衰落能力強以及抑制 ISI（inter symbol interference，符號間干擾）的優點，因此OFDM技術被看作無線通信系統中的關鍵技術。多用戶OFDM系統是基于OFDM技術發展的，多用戶OFDM系統把資源分配的方法分為靜態資源分配方法和動態資源分配方法。靜態資源分配方法是把固定的資源分配給不同的用戶，而動態資源分配方法是根據各個用戶自身的信道狀態，自適應地把資源分配給用戶，這樣能更好地滿足用戶的要求，也能夠使有限的資源得到充分的利用。

隨著無線通信技術的快速發展，對傳統分層結構的資源分配已經不能滿足不同用戶、不同業務以及高QoS的要求，還會因為資源分配時不進行變通而導致資源利用率低［1，2］。針對子載波、比特以及功率的分配采用的是自適應分配算法［3，4］，這種算法主要是在物理層上，首先假設一個確定的業務到達率，這就不能正確地反映出MAC（media access control，媒體接入控制）層實時隊列的特征，而在實際過程中，數據和業務的到達都具有突發性和隨機性。MAC層資源進行分組調度時設定物理信道是靜態的，并且是沒有差錯的［5］，又因為無線信道的特性是時變、移動以及高誤碼率。因此，在進行無線資源分配時，僅僅考慮用戶某種特定的需求而忽視無線信道的特點是很難滿足用戶需求的。相應地，只有在同時考慮用戶的和無線信道的特性時才能使用戶的需求得到最大的滿足。所以，在無線通信中，跨層設計變得越來越重要。

跨層設計是建立在傳統的分層結構上的，并不改變原有的分層結構，而是模糊化層與層之間的界限，把原來各層上相對獨立的參數進行融合，在系統整體的約束條件下進行聯合優化設計。在OSI 7層網絡結構中，物理層和MAC層是相鄰的兩層，MAC層是數據鏈路層中更接近物理層的，所以對聯合物理層與MAC層的跨層資源分配算法的研究也越來越多［6-8］，但是這些算法計算復雜度高且公平性較差。基于效用函數［9］的分配方法采用了數學優化方法來解決資源優化的分配，計算復雜度和求解難度都比較高。基于遺傳算法的跨層資源分配［10］不但降低了計算的復雜性，而且還提高了系統的性能。由于遺傳算法具有局部搜索能力差、爬山能力差以及容易陷入局部最優的缺點，使得遺傳算法不能獲得較好的資源分配方案。

禁忌搜索算法具有更好的局部搜索能力，而且收斂速度較快，能更好地收斂到全局最優解。所以遺傳算法與禁忌搜索算法兩者的結合能互相取長補短，提高算法的有效性。本文利用改進的混合遺傳禁忌算法來解決跨層優化的問題，利用改進混合算法較好的全局搜索能力和更好地收斂到全局最優解的特點，提高多用戶OFDM系統的性能。

2 多用戶OFDM系統跨層優化的系統模型

2.1 系統模型

多用戶OFDM系統的跨層優化模型如圖1所示。在此模型中，上層分組數據到達數據鏈路層之后，物理層根據MAC層用戶的緩沖隊列信息來決定資源如何分配。將用戶緩沖隊列的情況和子載波的信道狀態信息輸入調度器中，調度器根據這兩種信息把不同用戶的數據分配到物理層進行處理。這個跨層設計結合了物理層的信道信息和MAC層的用戶隊列信息，使多用戶OFDM系統能更好地滿足QoS的需求。

圖1 多用戶OFDM系統的跨層模型

2.2 MAC層的資源調度

假設多用戶OFDM系統有K個用戶，且每個用戶的隊列長度是相同的，M代表隊列的最大長度，隊列中的數據按照FIFO（first in first out，先進先出）方式進行傳輸。每個用戶的業務數據到達緩沖區服從泊松分布，到達率為λk，傳輸周期為 Ts。在［tTs，（t+1）Ts］時間（即第 t個時隙）內，用戶k傳輸業務的服務率為用戶從基站發送的數據量rk（t），在第 t-1 個時隙內用戶 k 到達的數據量是 Ak（t）。根據泊松分布的定義［11］可知：

由泊松分布的性質可知，第t-1個時隙內到達的分組數為：

其中，E{Ak（t）}為 Ak（t）的期望。所以用戶 k 在 Ts時刻的隊列長度 Qk（t）為：

用戶隊列模型如圖2所示。

圖2 用戶隊列模型

再根據排隊論里的Little定理，用戶k在t時刻的平均等待時間 wk（t）為：

在MAC層，用戶時延和分組丟失率是重要的指標。若用戶時延減小，則會減少分組丟失率和分組損耗，提高用戶的 QoS。

2.3 PHY層的資源分配模型

圖3給出了K個用戶、N個子載波的多用戶OFDM系統的跨層資源分配過程，同時考慮到MAC層的資源分組和物理層信道信息。物理層獲得的信道狀態為N×K的矩陣。代表時隙t時用戶k在子載波n上的信道衰落。定義比特分配 Bt=，…），功率分配 Pt=（，…）。

跨層資源的分配問題可以通過構造效用函數得到更好的解決［12］。為簡便起見，令瞬時隊列長度為{qkt，k=1，…，K}，瞬時速率{rkt，k=1，…，K}，則效用函數 Ut為：

假設每個子載波上最多分配比特數為C，令fk（C）代表用戶k采用了2C階調制并且滿足指定BER條件需要的SNR。

假設傳輸一個OFDM符號需要的功率為P，所以，跨層資源分配的問題可以描述為：

圖3 多用戶OFDM系統的跨層資源分配過程

3 基于改進的混合遺傳禁忌算法的跨層資源分配

3.1 遺傳算法與禁忌搜索算法原理

遺傳算法是一種全局優化算法，其基本原理是模仿生物界中的“物競天擇、適者生存”的演化規律［13］。遺傳算法［14］把問題參數編碼為每個個體的染色體，再利用迭代方式進行選擇、交叉和變異，來交換種群中每個染色體間的信息，最終生成的染色體是符合優化目標的。

遺傳算法［15］的缺點是收斂速度慢和算法容易進入早熟的狀態，而造成早熟的原因主要是兩個：一是遺傳算法中的交叉算子，交叉算子使得種群中的染色體之間具有局部的相似性，可能導致搜索停滯不前；二是遺傳算法中的變異概率一般比較低，變異操作帶來的種群多樣性不夠。這兩點均導致了遺傳算法的爬山能力比較差。

禁忌搜索算法擴展了局部搜索的能力，它模仿人類的記憶功能，使用禁忌表來封鎖剛搜索過的區域來避免迂回搜索，如果禁忌區域中的某個個體達到一定的限制，則可以進行釋放，因此可以保證搜索的多樣性以及達到全局最優化。禁忌搜索算法的優點是具有較快的收斂速度，但是禁忌搜索算法的搜索性能很大程度上依賴于給定的初始解。一個較好的初始解能使禁忌搜索算法更快地收斂于全局最優解。

3.2 改進的混合遺傳禁忌算法

在禁忌搜索與遺傳算法的混合策略中，由于遺傳算法的廣域搜索能力較強，主要作為“主算法”；而禁忌搜索算法的局部搜索能力較強，所以作為“從算法”。本文運用的是引入禁忌搜索思想的遺傳算法，這種混合策略把禁忌搜索算法的“禁忌”和“特赦”思想加入遺傳算法中，對遺傳算法的交叉因子進行一定的改進。并且在初始化種群中加入優秀基因，這樣可以加快搜索過程。混合算法的選擇策略是“精英保留”機制，主要是為了把性能較好的染色體直接保留到下一代。引入禁忌搜索思想后，不但可以保留性能較好的個體，而且禁忌區域還有記憶功能，這就限制了優良個體被替換的頻率，能很好地改進搜索性能。

改進的混合遺傳禁忌算法利用了禁忌搜索算法的局部搜索能力和“爬山”能力強的特點，與遺傳算法的并行性和全局搜索能力相結合，因此具有收斂速度快、爬山能力強等優點。引入禁忌搜索的遺傳算法流程如圖4所示。

圖4 引入禁忌搜索的遺傳算法流程

3.3 跨層資源分配優化算法的實現

（1）編碼

首先生成長度為N的一維數組，每個元素都對應OFDM系統的一個子載波，數組元素對應系統中的各個用戶。每個數組就對應一種子載波分配方案。子載波分配情況如圖5所示。

圖5 子載波編碼方式

（2）種群初始化

本文通過式（12）得到初始解：

式（12）表示把子載波 n分配給用戶K*，其中，λk代表平均業務量，Qk代表用戶隊列長度。當每個子載波上分配的功率一定時，hn，k越大，子載波能發射的比特數就越多，Qk／λk相當于用戶k的平均時延。這樣就能產生一個較好的初始種群，能更好地滿足用戶的QoS。

（3）適應度函數

采用效用函數作為改進的混合遺傳禁忌算法的適應度函數。

（4）選擇

采用精英保留機制，將群體中適應度值按升序進行排列，選擇適應度最高的Y個個體直接進入下一代，來進行下一步的操作。

（5）引入禁忌搜索的交叉

設禁忌表Tlist為空，長度為L。禁忌對象為染色體的基因，以每代中父代染色體平均適度值作為渴望水平。

禁忌交叉算子的操作過程大致如下。

步驟1 初始化禁忌表，禁忌長度為L，設為空。

步驟2 給每一個染色體產生一個0～1之間的隨機數d，Pc為交叉概率，如果 d＜Pc，則選擇其作為父代染色體，否則不會被選中。

步驟3 對每對父代染色體按交叉方法進行交叉操作，產生兩個子代新個體。

步驟4 計算子代染色體的適應度值是否優于渴望水平。如果優于渴望水平，則進入下一代；否則就把該子代染色體放入禁忌表中，選擇父代染色體進入下一代。

步驟5 判斷是否達到最大交叉次數。若已經達到最大交叉次數，則退出循環；否則進入步驟2。

本處采用的交叉方法是均勻交叉，在群體中按交叉概率Pc隨機選取兩個個體，根據交叉概率Pc決定是否交叉，再隨機選取交叉的長度，進行交叉。比如個體A（1100110110）、個體 B（0110100011），選擇交叉位是第 2位以及交叉長度為4之后產生的兩個新個體：個體A（1110110110）、個體 B（0100100011）。交叉之后的兩個新個體進行禁忌搜索的判斷，若新個體已經存在于Tlist表中，則跳過不再進行訪問，這樣避免重新訪問已經訪問過的個體，能更快地跳出局部最優解。

（6）變異

本文采用多點均勻變異，即以變異概率Pm隨機指定某一位或某幾位基因座上的基因做變異運算。對于個體A（1100110110），根據變異概率Pm隨機選擇變異位置第4位以及變異長度為4，則變異后A*為（1101001110）。Pm的取值一般在0.01～0.1，為了增加種群的多樣性，本文把Pm調整到 0.2。

4 性能仿真

為了驗證本文提出的算法性能，利用MATLAB軟件進行了實驗仿真。仿真中，考慮多用戶OFDM系統的帶寬為1 MHz，子載波為128個，總功率P=1。信道采用瑞利衰落模型，每個用戶的分組數據到達服從泊松分布，業務數據到達率 λk取值范圍為 5～30 kbit／s，Ts取值為 2 ms，每個OFDM符號內允許最大傳輸比特數C為4，每個數據分組長度M=200 bit。信道的噪聲功率譜密度N0為10-8，誤碼率BER≤10-3。混合遺傳禁忌算法的參數設定：最大迭代次數D為100，種群規模為S為 100，交叉概率Pc=0.9，變異概率Pm=0.2。

圖6是多用戶OFDM系統在用戶數K=4時，比較遺傳算法與本文提出的改進混合遺傳禁忌算法的收斂曲線。從圖6中可以看出，在相同的迭代次數下，本文提出的改進混合算法能獲得較大的效用函數值，也就是說，在發射功率相同的情況下，本文提出的算法能夠發射更多比特數據。從圖6還能看出，本文提出的改進混合遺傳禁忌算法在開始時就能得到較優解，隨著迭代次數的增加，效用函數值也有所提高，能夠更快地收斂于全局最優解，也就是用戶能發送的信息總量。

圖6 遺傳算法與改進的混合遺傳禁忌算法收斂性能比較

圖7比較了3種算法的平均時延，在用戶數不斷增加的情況下，本文提出算法的系統時延要低于其他兩種算法的系統時延。

圖7 3種算法的平均時延比較

本文提出的改進混合遺傳禁忌的算法復雜度主要集中在遺傳算法中的選擇、禁忌交叉和變異中，個體的適應度函數選擇的是效用函數，復雜度為O（N），一個種群中含有 S個個體，復雜度為 SO（N），經過選擇之后的復雜度為（1-Y／S）O（S2）。禁忌交叉步驟的復雜度為 SO（N），變異操作的復雜度為 SO（N），所以本文提出的改進混合算法總 的復雜度為 D［3SO（N）+（1-Y／S）O（S2）］。對于線性算法 LP，Karmarkar算法［17］的時間復雜度是 O（n3.5L），其中，L 代表線性方程組的輸入規模，n代表變量的個數。由此可以看出，LP的復雜度比混合遺傳禁忌算法大。

由圖8可知用戶數為4時，線性算法、遺傳算法以及改進的混合遺傳禁忌算法下每個用戶的分組丟失率。本文提出的改進混合算法的分組丟失率略低于遺傳算法和線性算法的分組丟失率，而且混合遺傳禁忌算法的復雜度也低于前兩種算法。

圖8 3種算法的用戶分組丟失率

5 結束語

本文研究了多用戶OFDM系統中的跨層資源分配問題，結合了物理層的信道狀態信息和MAC層的隊列狀態信息，并利用改進的混合遺傳禁忌算法進行優化，利用遺傳算法全局搜索能力強和禁忌搜索算法局部能力強進行互補，使得算法的性能得到提高。仿真結果表明，本文提出的改進混合算法與線性算法和遺傳算法相比，可以提高系統的吞吐量且減小用戶的平均時延，還能更好地滿足用戶的QoS要求。

［1］SHAKKOTTAIST，RAPPAPORTS，KARLSSON PC.Cross-layer design for wireless networks ［J］. IEEE Communications Magazine，2003，41（10）：74-80.

［2］ GOLDSMITH A J，WICKER SB.Designchallengesfor energy-constrained Ad Hoc wireless networks ［J］.IEEE Transactions on Wireless Communications，2002，9（4）：8-27.

［3］TANG M，WANG X.Joint subcarrier and power allocation with threshold in cooperative multiuser networks ［J］.High Technology Letters，2011，17（4）：360-365.

［4］LI M，WANG X，ZHANG H.Resource allocation with subcarrier cooperation in OFDM-based wireless multicast system ［C］／／2011 IEEE 73rd Vehicular Technology Conference，May 15-18，2011，Budapest，Hungary.New Jersey：IEEE Press，2011：1-5.

［5］ YU X， NAVARATAM P， MOESSNER K.Distributed interference-aware admission control with soft resource allocation for hybrid MAC in wireless mesh networks ［C］／／2012 IEEE InternationalConference on Communications，June 10-15，2012，Ottawa，ON，Canada.New Jersey：IEEE Press，2012：455-460.

［6］SONG G，LI Y，ZHENG H.Joint channel-aware and queue-aware data scheduling in multiple shared wireless channels［C］／／IEEE Wireless Communications and Networking Conference，March 21-25，2004，Atlanta，USA.New Jersey：IEEE Press，2004：1939-1944.

［7］ WEIC，PINGYF，ZHIGC.Waterfillingincellar：theoptimal power allocation policy with channel and buffer state information ［C］／／IEEE International Conference on Communications，May 16-20，2005，Seoul，Korea.New Jersey：IEEE Press，2005：537-541.

［8］ SUN Y，YU L，ZHANG J.Joint MAC-PHY layer resource allocation algorithm based on triangle module operator for multi-service OFDM system［J］.Procedia Environmental Sciences，2011，10（1）：163-169.

［9］ KUO W H，LIAO W.Utility-based resource allocation in wireless networks ［J］.IEEE Transactions on Wireless Communications，2007，6（10）：3600-3606.

［10］郁宇，周武旸.OFDMA系統中基于遺傳算法的資源分配［J］.計算機仿真，2008，25（5）：143-146.YU Y，ZHOU W Y.Resource allocation for OFDMA system based on genetic algorithm［J］.Computer Simulation，2008，25（5）：143-146.

［11］趙芝衛，張琳.一種新的 OFDMA系統功率與比特分配算法［J］.通信技術，2011，44（5）：31-33.ZHAO Z W，ZHANG L.A new power and bit allocation algorithm for OFDMA systems［J］.Communications Technology，2011，44（5）：31-33.

［12］SONG G，LI Y.Cross-layer optimization for OFDM wireless networks-part I：theoretical framework ［J］.IEEE Transactions on Wireless Communications，2005（4）：614-624.

［13］MENG Q C，FENG T J，CHEN Z.Genetic algorithms encoding study and a sufficient convergence condition of GAs ［C］／／1999 IEEE International Conference on Systems， Man， and Cybernetics，Oct 12-15，1999，Tokyo，Japan.New Jersey：IEEE Press，1999：649-652.

［14］王凌.智能優化算法及其應用 ［M］.北京：清華大學出版社，2001.WANG L.Intelligent optimization algorithm and application ［M］.Beijing：Tsinghua University Press，2001.

［15］雷英杰，張善文，李續武，等.遺傳算法工具箱及應用 ［M］.西安：西安電子科技大學出版社，2004.LEI Y J，ZHANG S W，LI X W，et al.Genetic algorithm toolbox and application ［M］.Xi’an：Xi’an University of Electronic Science and Technology Press，2004.

［16］徐偉堯.OFDMA系統中資源分配方案的研究 ［J］.廣東通信技術，2010（9）：39-43.XU W Y.Research on resource allocation scheme in OFDMA system ［J］.Guangdong Communication Technology，2010 （9）：39-43.

［17］RUDAN J，SZEDERKENYI G，HANGOS K M.Efficient computation of alternative structures for large kinetic systems using linear programming［J］.Communications in Mathematical and in Computer Chemistry，2014，71（1）：71-92.

An improved optimization algorithm in cross-layer allocation for multi-user OFDM system

PAN Yaqin，ZHANG Li，ZHANG Shibing
School of Electronics and Information，Nantong University，Nantong 226001，China

A cross-layer resource allocation model in multiuser OFDM system was proposed，which combined the channel state in physical layer and the user’s queue in MAC layer.The proposed hybrid optimization algorithm made use of the advantages of genetic algorithm and tabu search algorithm to improve the crossover of genetic algorithm.It would improve the global search ability，converge to the global optimal value faster，solve the cross-layer resource allocation problem more effectively and meet the user’s quality of service better.The simulation results show that the improved hybrid algorithm increases the throughput，reduces the average delay and improves the QoS of the system.

OFDM，cross-layer，resource allocation，hybrid algorithm

s：The National Natural Science Foundation of China（No.61371112），Application Basic Research Project of Transportation Department（No.2014319813220）

TN914

A

10.11959／j.issn.1000-0801.2016188

2016-01-22；

2016-07-08

張士兵，zhangshb@ntu.edu.cn

國家自然科學基金資助項目（No.61371112）；交通運輸部應用基礎研究項目（No.2014319813220）

潘亞芹（1990-），女，南通大學碩士生，主要研究方向為通信信號處理、頻譜資源分配。

張麗（1989-），女，南通大學碩士生，主要研究方向為通信信號處理、認知無線電。

張士兵（1962-），男，博士，南通大學教授、博士生導師，主要研究方向為寬帶無線通信、通信信號處理、認知無線電以及中繼協作等。