混合蛙跳在網(wǎng)絡編碼協(xié)作系統(tǒng)資源分配的應用

劉紫燕，唐思騰，馮 麗，毛 攀，張達敏

(1.貴州大學 大數(shù)據(jù)與信息工程學院，貴州 貴陽550025;2.國網(wǎng)重慶市電力公司，重慶400014)

協(xié)作通信系統(tǒng)通過節(jié)點協(xié)作傳輸信號來獲得空間分集增益，能有效提高系統(tǒng)的傳輸速率和吞吐量［1］。由于協(xié)作中繼系統(tǒng)采用半雙工工作方式，物理層網(wǎng)絡編碼(PNC)被應用到雙向中繼協(xié)作系統(tǒng)提高頻譜效率，相比傳統(tǒng)的雙向中繼協(xié)作系統(tǒng)，采用PNC 協(xié)議的系統(tǒng)一次傳輸僅需要兩個時隙就能完成點對點通信。在節(jié)點的轉發(fā)方式上，放大轉發(fā)AF(Amplify and Forward)只需將源節(jié)點的信息直接做放大處理，簡單易實現(xiàn)，更容易在實際系統(tǒng)中實現(xiàn)。此外，由于OFDM 技術能克服多徑衰落，所以基于PNC－AF 的OFDM 協(xié)作系統(tǒng)有很大的研究意義。

資源分配能有效提高OFDM 雙向中繼協(xié)作系統(tǒng)的性能［2－4］。文獻［5］研究了QoS 約束下OFDM 雙向中繼協(xié)作系統(tǒng)的資源分配，然而沒有考慮AF 中繼協(xié)作方式，文獻［5］研究了QoS 約束下OFDM 雙向AF 中繼協(xié)作系統(tǒng)的資源分配問題。混合蛙跳算法［6－7］將局部搜索和重新混合過程相間進行，有效地將全局信息交互和局部進化搜索相結合，具有高效的計算性能和優(yōu)良的全局搜索能力。已有的OFDM 雙向AF 中繼系統(tǒng)資源分配文獻中，還沒有考慮混合蛙跳算法對資源分配的優(yōu)化。本文考慮文獻［6］中基于能效的資源分配模型，利用混合蛙跳算法優(yōu)化系統(tǒng)資源。

本文將混合蛙跳算法引入到網(wǎng)絡編碼協(xié)作的多中繼通信系統(tǒng)中，在考慮系統(tǒng)能量效率的情況下，以最小化系統(tǒng)傳輸功率為目標，利用混合蛙跳算法搜索的優(yōu)勢，實現(xiàn)節(jié)點的資源分配，降低了系統(tǒng)的傳輸功率，使系統(tǒng)性能得到優(yōu)化。該資源分配算法不受優(yōu)化目標函數(shù)特性的影響，能實現(xiàn)快速優(yōu)化，算法簡單，收斂速度快。

1 系統(tǒng)模型及問題論述

1.1 系統(tǒng)模型

考慮基于網(wǎng)絡編碼的雙向多中繼協(xié)作OFDM 系統(tǒng)。如圖1 所示，一個源節(jié)點S 通過K 個中繼節(jié)點Rk(k=1，2，…，K)與目的節(jié)點D 進行通信。每個中繼節(jié)點R 采用PNC－AF轉發(fā)協(xié)議和半雙工工作方式進行轉發(fā)信息。每個信道被劃分為N 個相互正交的子信道，為了方便，假設每個信道的信道狀態(tài)信息都已知，且每個子信道經(jīng)歷獨立的平坦衰落。S 和D 交換一次信息只需要兩個時隙，第一個時隙:R 通過子載波i(i=1，2，…，N)同時接收S 和D 發(fā)送的信息，第二個時隙，R將接收的信息進行XOR 操作后，通過子載波j(j=1，2，…，N)同時轉發(fā)給S 和D，子載波i 可能不等于子載波j，形成子載波對(i，j)。為了避免干擾，每個子載波對分配給一個中繼，記第k 個中繼上的子載波對為(i，j，k)。和分別為S 和D通過子載波i 到中繼Rk的信道因子，同時和分別為Rk通過子載波j 到中繼S 和D 的信道因子。

圖1 系統(tǒng)模型

第i 個子載波在中繼k 上的放大因子［5］為

因此，通過第k 個中繼轉發(fā)，在子載波對(i，j)上的S 到D以及D 到S 的信息速率分別為

1.2 問題論述

記ρi，j∈(0，1)為子載波對分配因子，若第一跳第i 個子載波成功配對第二跳第j 個子載波，則ρi，j=1;相反，則ρi，j=0。記rs，i，j和rd，i，j為S 到D 以及D 到S 鏈路所要求的信息速率。在子載波配對過程中，每個子載波只能唯一配對另一個子載波，因此變量ρi，j必須滿足如下約束條件:

子載波約束條件為

雙向多中繼OFDM 系統(tǒng)的總功率為

最優(yōu)化問題

為了滿足用戶QoS，由約束條件可知

在滿足用戶QoS 下，由式(9)、(10)可知，最小節(jié)點功率為

由式(1)、(4)、(5)、(11)、(12)可得出最優(yōu)aki的表達式為

式中:ms=－1，md=－1。從式(1)、(11)、(12)、(13)可以得出

由式(11)、(12)、(14)重寫式(8)的最優(yōu)化問題為

2 基于混合蛙跳的資源分配算法

2.1 交換子和交換序［7］

1)交換子

假設n 個節(jié)點的資源分配解序列為sNode=(sNodei)，i=1，2，…，n。定義交換子swap(i1，i2)為解序列sNode 中的點sNode1和sNode2，則為解sNode 經(jīng)過算子swap(i1，i2)操作后的新解。

例如有4 個子載波，記sNode=(1，2，3，4)為某條鏈路的待分配子載波，若交換子為swap(2，3)，則經(jīng)過這個交換子運算后，得到的新解為

這里為符號“+”賦予了新的含義:經(jīng)過算子swap(i1，i2)操作后，sNode 中的i1和i2進行交換，符號“+”記為交換操作。

2)交換序

不同的解序列相互作用，形成一個或多個交換子所構成的有序序列即為交換序，記為SwapQ，即

式中:swapi(i=1，2，…，n)為其中一個交換子。交換子之間的先后順序是有意義的，不同順序的交換子作用于同一個解會得到不同的解序列。交換序作用于某個解序列，意味著交換序中的交換子依次作用于這個解序列，記為

3)交換序的構造

若兩個交換序SwapQ1和SwapQ2作用于同一個解sNode得到的新解相同，則記為等價交換序列集，在等價交換序列中，最少交換子的交換序稱為基本交換序。所以構造交換序只需構造基本交換序即可，假設兩個解序列sNodeA 和sNodeB，其基本交換序為swap，滿足sNodeA=sNodeB+swap。sNodeA=(1 2 3 4);sNodeB=(4 3 1 2)。

基本交換序流程如圖2 所示，構造交換序舉例如下:

1)sNodeA(1)=1，查看sNodeB 中各值可以看出，sNodeB中的第3 個位置需要和第1 個位置交換才能使sNodeA(1)=sNodeB(1)，所以第1 個交換子為swap1(1，3)，得到sNodeB1=sNodeB+swap1(1，3)=(1 3 4 2);

2)sNodeA(2)=2，查看sNodeB 中各值可以看出，sNodeB1中的第2 個位置需要和第4 個位置交換才能使sNodeA(2)=sNodeB1(2)，所以第2 個交換子為swap2(2，4)，sNodeB2=sNodeB1+swap2(2，4)=(1 2 4 3);

3)sNodeA(3)=3，查看sNodeB 中各值可以看出，sNodeB2中的第3 個位置需要和第4 個位置交換才能使sNodeA(3)=sNodeB2(3)，所以第3 個交換子為swap3(3，4)，sNodeB3=sNodeB2+swap3(3，4)=(1 2 3 4);

4)sNodeA(4)= sNode23(4)，即sNode=sNode3，經(jīng)過以上步驟，基本交換序為

圖2 基本交換序構造流程

這里為符號“－”也賦予了新的含義，即sNodeA 和sNodeB進行操作后，得到一個交換序，符號“－”記為交換操作。

2.2 基于交換序的混合蛙跳算法

基本的SFLA［8－9］速度公式和位置更新公式不能滿足資源分配問題，將交換子和交換序的概念引入到SFLA 中，重新定義速度公式和位置更新公式如下:

速度公式為

式中:rand 是在［0，1］之間的隨機數(shù);Pib(t－1)是前一時刻種群最好位置的青蛙;Piw(t－1)是前一時刻種群最壞位置的青蛙。式(20)表示操作后得到的青蛙的移動速度以概率rand被保留下來，V(t)是當前時刻青蛙的移動速度。這里符號“－”為交換操作，例如:Pib(t－1)=(1 2 3 4);Piw(t－1)=(4 3 1 2)，則V(t)=Pib(t－1)－Piw(t－1)={1 3 2 4 3 4}。

位置更新公式(最壞青蛙進化后)為

式中:Piw(t)表示經(jīng)過交換序V(t)操作后得到的新解序列;Vmax表示青蛙的最大移動速度。這里符號“+”為交換操作，若Piw(t－1)=(4 3 1 2)，V(t)=Pib(t－1)－Piw(t－1)={1 3 2 4 3 4}，則Piw(t)=Piw(t－1)+(1，3)+(2，4)+(3，4)={1 2，3，4}。

2.3 基于混合蛙跳算法的功率分配流程

步驟如下:

1)初始化。選擇模因組數(shù)目m_Memeplex;每個模因組中的青蛙數(shù)目m_frog，整個蛙群大小滿足F=m_Memeplex×m_frog;種群迭代次數(shù)MAXGEN 和模因組內迭代次數(shù)Ne。

2)構造模因組。生成F 個青蛙U(1)，U(2)，…，U(F)。每一個青蛙表示解空間的一個候選解，計算每一個青蛙U(ib)的適配值fitness，即總傳輸功率。

3)整個蛙群排序。按2)中計算的適配值對整個蛙群的青蛙進行升序排列，因此，U(1)就代表了整個種群中最好的青蛙。

4)構建模因組Y。對青蛙進行分組，分組方式為

5)模因組進化，即對每個模因組內的最差的青蛙進行局部搜索。

模因組進化(局部搜索)流程如下:

(1)設置im=0 表示種群計數(shù)，最大值為模因組數(shù)目m，滿足0≤im≤m。設置iN=0 為種群進化次數(shù)，最大值為每個模因組青蛙的數(shù)目N，滿足0≤iN≤N。

(2)im=im+1。

(3)iN=0。

(4)iN=iN+1。

(5)改善最壞青蛙位置:模因組內青蛙根據(jù)式(20)和(21)來更新自己的移動距離和位置。如果新青蛙的適配值較原來的適配值好，則用新產生的青蛙Pib(t)代替原來的青蛙并跳轉到步驟(4)，否則，用U(1)代替Pib(t－1)重新計算青蛙的位置和適配值，如果還沒有改善，則隨機產生一個新的青蛙r 取代原來的青蛙。計算fitness=f(r)。

(6)更新模因組。將模因組按降序排列。

(7)如果iN ＜N，跳轉到(4)。

(8)如果im ＜m，跳轉到(2)，否則，返回到全局搜索。

6)整個蛙群進化:將青蛙混合，即青蛙在模因組之間跳躍。當每個模因組內完成進化之后，將各個子群Y1，Y2，…，Ym重新混合成X，即X={Yk|k=1，2，…，m_frog}。將X 按升序排列，更新種群中最好的青蛙Px。

7)迭代終止條件。如果滿足迭代條件，則輸出結果，否則轉到步驟3)。一般而言，當?shù)揭欢ù螖?shù)后，代表最好解的青蛙位置就不會再改變，跳出循環(huán)。也可以設置迭代次數(shù)來作為循環(huán)終止條件。

3 仿真結果與分析

為了驗證本文算法的性能，本文仿真對比了其他兩種資源分配方案:基于第一跳最優(yōu)子載波(Optimal Subcarrier for First Hop)資源分配方案、固定子載波對(Fixed Subcarrier Pairing)分配方案。

假設在靜態(tài)瑞利信道無線環(huán)境下對資源分配方案進行仿真，源節(jié)點與目的節(jié)點的距離為3 km，隨機分配5 個中繼，具體位置如表1 所示。子載波數(shù)N=16，路徑損耗因子為3，混合蛙跳的參數(shù)設置如表2 所示。

表1 中繼位置

表2 混合蛙跳參數(shù)設置

圖3 比較了第一跳和第二跳的信息速率相等時，基于混合蛙跳(SLFA)的資源分配方案、基于第一跳最優(yōu)子載波(Optimal Subcarrier for First Hop)資源分配方案、FSP(Fixed Subcarrier Pairing)分配算法下的總傳輸功率。從圖中可以看出，當?shù)谝惶偷诙目傂畔⑺俾氏嗟葧r，即R1=R2，3 種資源分配方案下系統(tǒng)所的傳輸功率隨鏈路的速率增大而增加。在相同的信息速率下，基于SLFA 的資源分配方案比其他兩種資源分配方案所需的傳輸功率少。

圖3 相同速率下3 種資源分配方案的傳輸功率比較

圖4 比較了第一跳和第二跳的信息速率不相等時基于混合蛙跳的資源分配方案、基于第一跳最優(yōu)子載波資源分配方案、FSP 分配算法下的總傳輸功率。總信息速率不變，即，第一跳的信息速率R1占總傳輸功率比例分別設置為［0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9］，可以明顯看出，當R1=R2時，3 種資源分配方案下系統(tǒng)所需的傳輸功率最少;此外，本文提出的基于混合蛙跳(SLFA)的資源分配方案優(yōu)于基于其他兩種資源的分配方案。

圖4 不同速率下3 種資源分配方案的傳輸功率比較

圖5 比較了在不同中繼協(xié)作個數(shù)下基于混合蛙跳(SLFA)資源分配方案的總傳輸功率。從圖中可以看出，設置中繼個數(shù)為{2，4，6，8}，在相同的環(huán)境下，參與協(xié)作的中繼個數(shù)越少，傳輸功率越小;當協(xié)作中繼數(shù)目為2 時，此時系統(tǒng)消耗的功率最少。

圖5 不同中繼協(xié)作下基于SFLA 資源分配方案的傳輸功率比較

4 結論

本文針對雙向OFDM 多中繼協(xié)作通信系統(tǒng)，以最小化傳輸功率為目標提出了基于混合蛙跳算法的資源分配策略，利用混合蛙跳算法求解出每一跳鏈路的最優(yōu)子載波對和最小功率。當?shù)谝惶偷诙俾氏嗤瑫r并且采用較少的中繼數(shù)，基于混合蛙跳算法的資源分配方案所需的功率最小;與基于第一跳最優(yōu)子載波資源分配方案、固定子載波對分配方案相比，本文提出的基于混合蛙跳算法的資源分配方案更節(jié)省能量，該算法為多中繼協(xié)作通信系統(tǒng)的資源分配提供了一種優(yōu)化解決方案。

［1］KRISHNA R，CUMANAN K，XIONG Z L，et al. A novel cooperative relaying strategy for wireless networks with signal quantization［J］.IEEE Trans.Vehicular Technology，2010，59(1):485－489.

［2］ZHAO Hanhua，ILOW J. Adaptive resource allocation in OFDMA relay networks with network coding［C］//Proc. IEEE International Conference on Communications.［S.l.］:IEEE Press，2011:1－5.

［3］XIONG Ke，F(xiàn)AN Pingyi，LETAIEF B，et al. Resource allocation for minimal downlink delay in two－way OFDM relaying with network coding［C］//Proc. IEEE International Conference on Communications.［S.l.］:IEEE Press，2012:5343－5347.

［4］劉紫燕，唐思騰，馮亮，等.多中繼協(xié)作系統(tǒng)量子遺傳算法的功率分配仿真［J］.電子技術應用，2014，40(11):113－115.

［5］LIU Yuan，MO Jianhua，TAO Meixia.QoS－aware transmission policies for OFDM bidirectional decode－and－forward relaying［J］.IEEE Trans.Wireless Communications，2013，12(5):2206－2216.

［6］LIU Yinjun，CUI Qimei，F(xiàn)U Ting，et al.Energy－efficient resource allocation for two－way multiple relay OFDM system［C］//Proc.2013 IEEE Vehicular Technology Conference.［S.l.］:IEEE Press，2013:1－5.

［7］WANG Kangping，HUANG Lan，ZHOU Chunguang，et al.Particle swarm optimization for traveling salesman problem［C］//Proc.2003 International Conference on Machine Learning and Cybernetics.［S.l.］:IEEE Press，2003:1583－1585.

［8］EUSUFF M，LANSEY K，PASHA F. Shuffled frog－leaping algorithm:a memetic meta－h(huán)euristic for discrete optimization［J］.Engineering Optimization，2006，38(2):129－154.

［9］BABAK A，MOHAMMAD F，ALI M.Application of shuffled frogleaping algorithm on clustering［J］.The International Journal of Advanced Manufacturing Technology，2009，45(1/2):199－209.