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

劉紫燕，唐思騰，馮 麗，毛 攀，張達(dá)敏

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

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

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

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

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

1.1 系統(tǒng)模型

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

圖1 系統(tǒng)模型

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

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

1.2 問題論述

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

子載波約束條件為

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

最優(yōu)化問題

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

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

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

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

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

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

2.1 交換子和交換序［7］

1)交換子

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

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

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

2)交換序

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

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

3)交換序的構(gòu)造

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

基本交換序流程如圖2 所示，構(gòu)造交換序舉例如下:

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

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

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

4)sNodeA(4)= sNode23(4)，即sNode=sNode3，經(jīng)過以上步驟，基本交換序?yàn)?/p>

圖2 基本交換序構(gòu)造流程

這里為符號(hào)“－”也賦予了新的含義，即sNodeA 和sNodeB進(jìn)行操作后，得到一個(gè)交換序，符號(hào)“－”記為交換操作。

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

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

速度公式為

式中:rand 是在［0，1］之間的隨機(jī)數(shù);Pib(t－1)是前一時(shí)刻種群最好位置的青蛙;Piw(t－1)是前一時(shí)刻種群最壞位置的青蛙。式(20)表示操作后得到的青蛙的移動(dòng)速度以概率rand被保留下來，V(t)是當(dāng)前時(shí)刻青蛙的移動(dòng)速度。這里符號(hào)“－”為交換操作，例如: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}。

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

式中:Piw(t)表示經(jīng)過交換序V(t)操作后得到的新解序列;Vmax表示青蛙的最大移動(dòng)速度。這里符號(hào)“+”為交換操作，若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;每個(gè)模因組中的青蛙數(shù)目m_frog，整個(gè)蛙群大小滿足F=m_Memeplex×m_frog;種群迭代次數(shù)MAXGEN 和模因組內(nèi)迭代次數(shù)Ne。

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

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

4)構(gòu)建模因組Y。對(duì)青蛙進(jìn)行分組，分組方式為

5)模因組進(jìn)化，即對(duì)每個(gè)模因組內(nèi)的最差的青蛙進(jìn)行局部搜索。

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

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

(2)im=im+1。

(3)iN=0。

(4)iN=iN+1。

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

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

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

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

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

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

3 仿真結(jié)果與分析

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

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

表1 中繼位置

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

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

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

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

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

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

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

4 結(jié)論

本文針對(duì)雙向OFDM 多中繼協(xié)作通信系統(tǒng)，以最小化傳輸功率為目標(biāo)提出了基于混合蛙跳算法的資源分配策略，利用混合蛙跳算法求解出每一跳鏈路的最優(yōu)子載波對(duì)和最小功率。當(dāng)?shù)谝惶偷诙俾氏嗤瑫r(shí)并且采用較少的中繼數(shù)，基于混合蛙跳算法的資源分配方案所需的功率最小;與基于第一跳最優(yōu)子載波資源分配方案、固定子載波對(duì)分配方案相比，本文提出的基于混合蛙跳算法的資源分配方案更節(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］.電子技術(shù)應(yīng)用，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.