蔣雪婷，葛文萍（新疆大學信息科學與工程學院，烏魯木齊　830046）

?

基于人工蜂群算法的多用戶中繼選擇研究

蔣雪婷，葛文萍
（新疆大學信息科學與工程學院，烏魯木齊830046）

摘要：

關鍵詞：

0　引言

中繼技術[1-2]是無線網(wǎng)絡中一種提升系統(tǒng)性能的新興技術，中繼節(jié)點[3]（Relay Nodes，RNs）在提高網(wǎng)絡分集增益方面起到了重要作用。已有文獻針對中繼選擇、功率和帶寬分配分別做了相關研究，常見的中繼選擇[4]主要討論已知信道狀態(tài)信息（Channel Status Indicator，CSI）的信噪比（Signal to Noise Ratio，SNR），這些場景更多關注單用戶[5-6]的多中繼選擇。由于這些場景不存在干擾，所以其標準簡單明確。近來，多用戶對[7-8]的中繼選擇研究越來越多，由于用戶間的競爭增加了研究的復雜性，故單用戶中繼選擇的研究不能直接擴展到多用戶。

已有文獻的研究較有限，文獻[9]提出多用戶中繼分組算法，從而最大化部分用戶的最小可實現(xiàn)信道速率或網(wǎng)絡速率總和。文獻[10]提出一種最大化所有用戶的最小可實現(xiàn)速率的中繼方案。文獻[11]提出一種多用戶中繼網(wǎng)絡的最優(yōu)化方法，目標是最大化所有用戶的最小接收SNR，但文獻[9-11]假設多用戶間不存在CCI。文獻[12]提出一種考慮用戶間CCI的多用戶中繼選擇方案，基于求婚-拒絕算法（Gale-Shapley）的中繼選擇方案也被用于解決總速率最大化的問題，然而只能獲得一個次優(yōu)解。文獻[13]提出一種基于量子粒子群算法（Quantum Particle Swarm Optimization，QPSO）的多用戶中繼選擇方案。

本文在考慮CCI的前提下提出用ABC算法解決多用戶中繼選擇問題，即基于ABC算法的中繼選擇方案。通常，中繼選擇的問題可看作一個最優(yōu)化問題，窮舉搜索可獲得最優(yōu)解，但運算量極大。已有文獻方案通常只能獲得一個次優(yōu)解，應用本文所述的智能算法可以獲得近似窮舉搜索的最優(yōu)解，且由算法流程可看出其運算復雜度相比窮舉搜索有降低。仿真結果表明，相比已有文獻，所述方案在不同仿真條件下都有較優(yōu)系統(tǒng)性能。

1　網(wǎng)絡模型和問題描述

本文討論的多用戶中繼協(xié)作網(wǎng)絡模型[13]由多個源節(jié)點（Source Node，SN）和目的節(jié)點（Destination Node，DN）以及確定數(shù)目的潛在中繼節(jié)點（Relay Node，RN）組成。SN要把信息傳送給相應的DN，因此有N對SNDN，M個RN，通常M＞N[11]。每對SN-DN選擇一個RN用于協(xié)作傳輸，即每個RN最多協(xié)助一對SN-DN，這里只有一個可用信道。傳輸基于兩跳的譯碼轉(zhuǎn)發(fā)（De-code-and-Forward，DF）協(xié)議，分兩個時隙（Time Slot，TS）完成。RN會在TS1接收信息且DN在TS2合并接收來自SN和RN的信息，采用最大比合并（Maximum Ratio Combining，MRC）。由于SN和RN的傳輸分兩個時隙完成，故SN和RN之間不存在干擾。如圖1所示，由于僅有一個可用信道，所以TS1的多個SN信息同時傳輸以及TS2的多個RN同時傳輸會造成各個SN和RN之間的CCI。本文不考慮調(diào)度和功率控制問題，并假設傳輸功率固定。同時假設存在已知所有信道CSI的中央控制器確定中繼選擇，然后在預定信道將中繼分配廣播給SNs，RNs和DNs。

在TS1，第i個SN到第j個RN和DN之間的CSI分別定義為Gsi，rj和Gsi，dj。在TS2，第i個RN到第j個DN之間的CSI定義為Gri，dj。每次傳輸，第i個SN和第j個RN的功率分別表示為Psi和Prj，每個節(jié)點必須用全部功率傳輸。當SN和DN之間有一個傳輸任務時，RN只能選擇用全部功率協(xié)作或者不協(xié)作傳輸。

圖1　多用戶無線中繼網(wǎng)絡系統(tǒng)模型

DNi接收到的信號為：

式中w表示功率為η的加性高斯白噪聲，則SNDN鏈路的信干噪比（Signal to Interference Noise Ratio， SINR）可表示為：

RNi在TS1接收到的信號為：

在TS2，RN接收并解碼信息，再將信息編碼后轉(zhuǎn)發(fā)給DN，故DNi接收到的信號為：

其中的xi'是xi編碼后的符號。RN-DN鏈路的SINR可表示為：

在兩個時隙下的信道可實現(xiàn)速率為：

式中W是可用信道帶寬，γi是第i對SN-DN的SINR，目標是最大化網(wǎng)絡總吞吐量，這個最大化問題可以表述為：

服從：

其中R=[r1，r2，…，rN]是中繼選擇方案，每個元素ri（i=1，2，…，N）表示RN選擇第i個SN-DN傳送對，即如果RN k（k=1，2，…，M）分配給了第i個SN-DN傳送對，那么ri=k。

對于每個中繼選擇方案R，CCI增加了最優(yōu)化問題的復雜化性，窮盡搜索方式的求解包含以下幾個步驟。對所有可能的解，計算等價的SINR，然后由（8）式獲得最優(yōu)化值。因此，全部M！/（M-N）！個（N代表SNDN對個數(shù)，M代表可用RN的個數(shù)）可能的中繼選擇方案需要被計算。鑒于階乘函數(shù)的增長比指數(shù)函數(shù)更快，所以窮舉搜索的復雜度是很大的，特別是當M很大時。故本文提出用ABC算法解決這個問題。

2　中繼選擇方案

上述中繼選擇問題是一個整數(shù)優(yōu)化問題，ABC算法是一種新型的群智能優(yōu)化算法，有引導蜂、跟隨蜂、偵查蜂三種。蜜蜂在N維的空間里飛行，N代表最優(yōu)化問題的維度，此處即SN-DN傳輸對的數(shù)量。

λ表示[0，1]之間的隨機數(shù)。開始搜索后，引導蜂先在蜜源h的周圍隨機產(chǎn)生一個新蜜源，隨后的更新過程如下：

其中k表示隨機的鄰域搜索引導蜂。那么引導蜂h被選擇跟隨的概率為：

跟隨蜂的更新公式與（11）式相同。搜索過程中，當搜索次數(shù)達到閾值limit時仍未找到更好的蜜源，則放棄該蜜源，隨機產(chǎn)生一個新的，此時的引導蜂轉(zhuǎn)變?yōu)閭刹榉鋄14]。

更新了每個蜜蜂的位置后，蜜蜂位置映射為一個實數(shù)：

式中l(wèi)i和ui分別表示第i維空間的下界和上界，xhi為映射后的實數(shù)。多用戶中繼選擇方案中，M個候選中繼被選擇，故li=1，ui=M，其中i=1，2，…，N。

由于多用戶中繼選擇是一個整數(shù)優(yōu)化問題，對實數(shù)取整：

每只蜜蜂的適應度值根據(jù)（8）式計算。但如果一個解不滿足（9）式，即，則此解刪除。最后，更新局部最優(yōu)解和全局最優(yōu)解。即如果適應度值優(yōu)于，那么更新為。若適應度值優(yōu)于，那么更新為。

當?shù)螖?shù)達到最大迭代時，中央控制器輸出Pg并傳送給中繼選擇方案R，表示為：

基于上述討論，用ABC算法解決多用戶中繼選擇問題的方案流程如下：

（1）假設中央控制器已知所有CSI并完成中繼選擇過程。

（2）隨機生成初始蜂群，初始化各參數(shù)。

（3）對所有蜜蜂，根據(jù)式（13）、（14）將其位置映射到不同整數(shù)并由式（8）計算適應度值（即系統(tǒng)吞吐量）。

（4）更新每只蜜蜂的局部最優(yōu)位置并更新全局最優(yōu)位置作為整個蜂群下一次演進的目標。

（5）由式（11）更新蜜蜂位置。

（6）如果達到預先設定的最大迭代次數(shù)，停止進程并根據(jù)（15）式將結果轉(zhuǎn)發(fā)輸出給中繼選擇方案R；如未達到，則跳到（3）繼續(xù)。

（7）中央控制器在預定信道將中繼分配廣播給SNs、RNs和DNs，中繼選擇過程結束。

3　仿真結果與分析

首先比較ABC算法和窮舉搜索、QPSO以及Gale-Shapley算法之間的性能。令N=5，M=7，RN的功率為10W，SN的功率為5W～40W，仿真結果如圖2所示?；贏BC算法的中繼選擇方案性能要優(yōu)于基于QPSO和Gale-Shapley算法，其吞吐量比Gale-Shapley算法大0.6Mbit/s，且隨著中繼功率的增加，差距在不斷增大。由圖可知，ABC算法可以獲得近似于窮盡搜索算法的吞吐量性能，驗證了算法的有效性。

圖3討論總吞吐量隨中繼數(shù)目的變化。設N105，M 是20～35個，SN的功率為20W，RN是10W。由圖可知，總吞吐量基本隨中繼數(shù)目的增加呈線性增長。因為候選中繼增加，網(wǎng)絡中每對SN-DN可以選擇到更合適的中繼進而獲得更好的總吞吐量。如圖，Gale-Shapley-Min方案的性能比Gale-Shapley-Harmonic差，QPSO方案優(yōu)于PSO方案，但ABC算法方案的性能最好。與Gale-Shapley的兩種相比，ABC算法方案在吞吐量上高于二者4Mbit/s左右，高于QPSO大約2Mbit/s。

圖4討論總吞吐量隨中繼功率變化的情況。設N= 10，M=20，SN的功率為20W，RN的功率是3W～18W。如圖所示，ABC算法方案可獲得最優(yōu)性能，在總吞吐量方面明顯優(yōu)于幾種對比算法。ABC算法吞吐量高于QPSO和PSO算法2Mbit/s左右，高于Gale-Shapley算法方案5Mbit/s左右。由此可鑒，基于ABC算法的中繼選擇方案在不同的仿真條件下都有較優(yōu)性能。

圖5討論各算法方案下總吞吐量隨迭代次數(shù)變化的情況。設定N=10，M=20，SN的功率為20W，RN為12W。如圖所示，基于ABC算法的中繼選擇方案在60次迭代左右就可以獲得接近Gale-Shapley算法的結果，而QPSO算法則需要迭代250次左右。但當?shù)螖?shù)達到500次的時候，與Gale-Shapley算法相比，ABC算法方案獲得的吞吐量高出將近5Mbit/s，使得整個系統(tǒng)性能更優(yōu)，相比QPSO算法收斂性更好。

圖2　不同發(fā)送功率下ABC方案、QPSO方案、Gale-Shapley方案以及窮舉搜索方式間總吞吐量的比較

圖3　不同中繼數(shù)目下ABC方案、QPSO方案、PSO方案以及Gale-Shapley方案間總吞吐量的比較

4　結語

本文提出一種基于ABC算法的多用戶中繼選擇方案，通過考慮SN-DN傳輸對之間的CCI干擾，提出用群智能算法ABC解決多用戶中繼選擇這個優(yōu)化問題。與基于QPSO、PSO和Gale-Shapley算法的中繼選擇方案相比，從仿真結果可看出，基于ABC算法的中繼選擇方案與已有文獻的其他三種方案相比，當吞吐量作為性能衡量指標時，具有明顯優(yōu)勢。證明了ABC算法方案在不同仿真條件下均具有較優(yōu)性能，較好地解決了存在干擾的多用戶中繼選擇這樣的連續(xù)優(yōu)化問題，驗證了算法的有效性。

圖4　不同中繼功率下ABC方案、QPSO方案、PSO方案以及Gale-Shapley方案間總吞吐量的比較

圖5　不同迭代次數(shù)下ABC方案、QPSO方案以及Gale-Shapley方案間總吞吐量的比較

參考文獻：

[1]Ghosh A，Ratasuk R，Mondal B，et al.LTE-Advanced：Next-Generation Wireless Broadband Technology[Invited Paper][J].Wireless Communications，IEEE，2010，17（3）：10-22.

[2]de Moraes T M，Nisar M D，Gonzalez A A，et al.Resource Allocation in Relay Enhanced LTE-Advanced Networks[J].EURASIP Journal on Wireless Communications and Networking，2012，2012（1）：1-12.

[3]Wu X，Xie L L.A Unified Relay Framework with both DF and CF Relay Nodes[J].Information Theory，IEEE Transactions on，2014，60（1）：586-604.

[4]Zou Y，Wang X，Shen W.Optimal Relay Selection for Physical-Layer Security in Cooperative Wireless Networks[J].Selected Areas in Communications，IEEE Journal on，2013，31（10）：2099-2111.

[5]Adeleke O A，Salleh M F M.Relay Selection Mechanism for User Cooperation Networks Using a Game-Theoretic Approach[J].Journal of Electrical and Electronic Engineering Research，2013，5（3）：50-56.

[6]Liu Y，Tao M.Optimal Channel and Relay Assignment in OFDM-Based Multi-Relay Multi-Pair two-Way Communication Networks [J].Communications，IEEE Transactions on，2012，60（2）：317-321.

[7]Aldhaibani J A，Yahya A，Ahmad R B，et al.Effect of Relay Location on Two-Way DF and AF Relay for Multi-User System in LTE-A Cellular Networks[C].Business Engineering and Industrial Applications Colloquium（BEIAC），2013 IEEE.IEEE，2013：380-385.

[8]Okeke G O，Krzymien W A，Jing Y，et al.A Novel Low-Complexity Joint User-Relay Selection and Association for Multi-User Multi-Relay MIMO Uplink[J].Wireless Communications Letters，IEEE，2015，4（3）：309-312.

[9]E？li C，Wittneben A.A Hierarchical AF Protocol for Distributed Orthogonalization in Multiuser Relay Networks[J].Vehicular Technology，IEEE Transactions on，2010，59（8）：3902-3916.

[10]Sharma S，Shi Y，Hou Y T，et al.An Optimal Algorithm for Relay Node Assignment in Cooperative ad Hoc Networks[J].IEEE/ACM Transactions on Networking（TON），2011，19（3）：879-892.

[11]Atapattu S U B，Jing Y，Jiang H，et al.Relay Selection and Performance Analysis in Multiple-User Networks[J].Selected Areas in Communications，IEEE Journal on，2013，31（8）：1517-1529.

[12]Xu J，Zhou S，Niu Z.Interference-Aware Relay Selection for Multiple Source-Destination Cooperative Networks[C].Communications，2009.APCC 2009.15th Asia-Pacific Conference on.IEEE，2009：338-341.

[13]曹金龍.中繼協(xié)作網(wǎng)絡中繼選擇及資源分配技術研究[D].北京：北京郵電大學碩士學位論文，2013.

[14]秦全德，程適，李麗，等.人工蜂群算法研究綜述[J].智能系統(tǒng)學報，2014，9（02）：127-135.

蔣雪婷（1990-），女，新疆哈密人，碩士研究生，研究方向為LTE-A中繼技術

葛文萍（1969-），女，新疆伊犁人，教授，碩士生導師，研究方向為LTE-A技術、光通信技

Relay Selection Scheme Based on Artificial Bee Colony Algorithm in Multi-User Cooperative Relay Networks

JIANG Xue-ting，GE Wen-ping
（Department of Information Science and Engineering，Xinjiang University，Urumqi 830046）

Abstract：

In order to improve the wireless multi-user cooperative relay network system throughput.Considering co-channel interference，proposes a novel artificial bee colony algorithm（ABC）based relay selection scheme.It is an optimization problem for selecting suitable relay nodes，which has great impact on the system performance.The exhaustive search can solve this problem but the complexity will increase factorially with the network size，i.e.，the number of relays and users in the network.The ABC can maximize the system throughput of the cooperative relay networks but has less computational complexity.Simulation results show that ABC based has the ability to search global optimal solution compared with relay ordering schemes under different simulation scenarios in literature.

Keywords：

為提高多用戶無線中繼協(xié)作網(wǎng)絡的吞吐量，提出一種考慮共信道干擾（CCI）的基于人工蜂群算法（ABC）的中繼選擇方案。選擇哪些節(jié)點協(xié)作的最優(yōu)化問題對中繼協(xié)作網(wǎng)絡性能有重要影響。以往的窮舉搜索方式使算法的復雜度隨用戶對和中繼數(shù)目的增加呈階乘增長，用ABC算法解決此中繼選擇問題時可在最大化系統(tǒng)總吞吐量的同時相比窮舉搜索降低運算復雜度。仿真結果表明，不同仿真條件下ABC算法方案的系統(tǒng)性能均明顯優(yōu)于現(xiàn)有方案。

中繼協(xié)作網(wǎng)絡；中繼選擇；多用戶；人工蜂群算法

文章編號：1007-1423（2016）14-0026-06

DOI：10.3969/j.issn.1007-1423.2016.14.006

作者簡介：book=31,ebook=32

收稿日期：2016-03-06修稿日期：2016-04-28

Cooperative Relay Networks；Relay Selection；Multi-User；Artificial Bee Colony Algorithm