基于螢火蟲算法的多中繼選擇策略

程銅龍, 張　涵

(華南師范大學物理與電信工程學院,廣州 510006)

?

基于螢火蟲算法的多中繼選擇策略

程銅龍, 張涵*

(華南師范大學物理與電信工程學院,廣州 510006)

中繼選擇(RS)和功率控制是無線中繼網(wǎng)絡(luò)的2個重要組成部分.當中繼節(jié)點以全功率協(xié)作和不協(xié)作時,中繼選擇等同于功率控制.因此,最佳信噪比(SNR)被描述稱為0-1非線性整數(shù)規(guī)劃問題(0-1 nonlinear programming integer problem,NLIP).文中提出了基于螢火蟲算法(Glowworm Swarm Optimization, GSO)的多中繼選擇策略,仿真結(jié)果表明,基于GSO算法的多中繼選擇能夠獲得最佳信噪比值,且性能優(yōu)于窮舉搜索、單一RS方案及其他次優(yōu)化方案.

無線網(wǎng)絡(luò)； 多中繼選擇； 螢火蟲算法

隨著無線通信技術(shù)的發(fā)展和通信需求的日益提高,追求更高效的通信網(wǎng)絡(luò)結(jié)構(gòu)、組網(wǎng)方式已經(jīng)成為研究的熱點問題[1-2].引入中繼的協(xié)作通信能夠在不降低發(fā)射功率的前提下,提高系統(tǒng)容量,減少多徑衰落[3],適用于分散控制的異構(gòu)通信網(wǎng)絡(luò)環(huán)境.用于協(xié)作通信的中繼方案主要有：放大轉(zhuǎn)發(fā)(Amplify-and-Forward,AF)[3]、解碼轉(zhuǎn)發(fā)(Decode-and-Forward,DF)[4]和編碼協(xié)作(Coded Cooperation,CC)[5],其中, AF方式操控簡單,被視為協(xié)作通信的主流方法.

作為協(xié)作通信的關(guān)鍵問題,中繼選擇和功率控制受到了廣泛研究.研究中繼傳輸最優(yōu)節(jié)點選擇問題,得到次優(yōu)結(jié)果[6-8],但是，當最優(yōu)節(jié)點不能工作或選擇錯誤時,此策略將大幅度降低系統(tǒng)性能.分析多中繼選擇問題,可得到比最優(yōu)中繼選擇更優(yōu)的系統(tǒng)性能[9-11]. JING和JAFARKHANI[9]針對協(xié)作通信的功率控制和中繼選擇提出了0或最大功率傳輸模式,即1個中繼節(jié)點采取0或最大功率進行傳輸(對中繼節(jié)點進行選擇),得到了次優(yōu)結(jié)果,但當中繼節(jié)點數(shù)增加時,卻無法進一步提高系統(tǒng)性能.

DU等[12]將螢火蟲算法和粒子群算法[13]、遺傳算法[14]、魚群算法[15]進行比較,發(fā)現(xiàn)螢火蟲算法的不同在于螢火蟲種群可隨機更新并根據(jù)適應(yīng)度函數(shù)評價個體優(yōu)劣,尋找更優(yōu)個體,具有更快的收斂速度和更強的搜索能力,已被成功應(yīng)用于多模態(tài)函數(shù)優(yōu)化、多信號源追蹤定位和機器人學習等領(lǐng)域[16-19].

目前將螢火蟲算法應(yīng)用到解決中繼節(jié)點選擇問題尚無文獻報道.本文在文獻[9]1415模型基礎(chǔ)上,提出了一種基于螢火蟲算法的AF模式多中繼節(jié)點選擇策略,建立0-1非線性整數(shù)規(guī)劃問題(0-1 NLIP)模型,通過離散化螢火蟲算法搜索選擇最優(yōu)中繼節(jié)點,實現(xiàn)系統(tǒng)信噪比最大化.

1　研究方法

1.1系統(tǒng)模型

圖1　系統(tǒng)模型

1.2問題描述

系統(tǒng)1次中繼傳輸分為2步.

第一步,源節(jié)點s以功率P向中繼節(jié)點i發(fā)送信號x,第i個中繼接收信號為：

(1)

其中，vi為均值0、方差1的高斯噪聲.

第二步,中繼節(jié)點i對接收到的源節(jié)點信號放大處理并轉(zhuǎn)發(fā)給目的節(jié)點,放大信號[9]1415為：

(2)

目的節(jié)點接收信號為：

(3)

其中,wi為均值0、方差1的高斯噪聲.

根據(jù)式(1)～(3),得到目的節(jié)點接收信號為：

(4)

由式(4)可知,目的節(jié)點接收信號分為信號和與噪聲和2部分.由于vi和wi具有相同的分布,所以式(4)可以改寫為

(5)

其中,ni為均值0、方差1的高斯噪聲.

根據(jù)式(5)得到目的節(jié)點信噪比為：

(6)

則式(6)為

(7)

本文考慮中繼節(jié)點選擇問題,不考慮功率分配問題,因此得到如下優(yōu)化問題：

(8)

由于優(yōu)化問題式(8)中含有整數(shù)變量αi,目標函數(shù)SNR是關(guān)于變量αi的非線性函數(shù),因此優(yōu)化問題式(8)為典型的NP-hard問題中的0-1 NLIP問題[20].

1.3螢火蟲算法和多中繼選擇

GSO算法是由KRISHNANAND和GHOSE[21]提出,最早用于求解多個連續(xù)函數(shù)最優(yōu)值問題上,近年來受到多方面學者關(guān)注和應(yīng)用[22-23].在該算法中,包含M個螢火蟲的種群隨機分配到目標函數(shù)定義域內(nèi),每只螢火蟲j(j=1,2,…,M)隨機分配位置lj,熒光素Bj(取決于螢火蟲所在位置的目標值),視野范圍rdj(稱為決策半徑).螢火蟲j根據(jù)決策半徑尋找比其熒光素更高的螢火蟲m(m=1,2,…,M),并向其移動.最后,所有螢火蟲都聚集在函數(shù)最優(yōu)解周圍,實現(xiàn)目標函數(shù)最優(yōu)值的搜索和優(yōu)化.算法開始,每只螢火蟲分配相同的熒光素和決策半徑,通過迭代尋找函數(shù)最優(yōu)解,每次搜索過程包含2個階段[24]：

(1)更新階段：螢火蟲j根據(jù)式(9)更新熒光素值：

Bj(t)=(1-rh)×Bj(t-1)+γ×f(lj),

(9)

其中,Bj(t-1)為螢火蟲j之前熒光素值.rh(0

(2)移動階段:螢火蟲j利用式(10)得到?jīng)Q策范圍內(nèi)比自己熒光素更高的螢火蟲個體.

Nmtj(t)={m:‖lm-lj‖

(10)

其中,Nmtj(t)為螢火蟲j當前時刻決策范圍內(nèi)熒光素較高的螢火蟲個體,rdj為螢火蟲j視野范圍(決策半徑),Bm和Bj分別為螢火蟲m和j的熒光素,‖lm-lj‖為螢火蟲位置距離.

根據(jù)式(10)得出螢火蟲j向Nmtj內(nèi)螢火蟲移動的概率：

(11)

螢火蟲j通過輪盤方法在Nmtj內(nèi)選擇移動概率最大的螢火蟲并向其移動,移動公式為：

(12)

其中，step0為移動步長.

位置更新后,螢火蟲j利用式(12)更新決策半徑：

rdj(t)=min{rs,max[0,rdj(t-1)+

(13)

Step1：初始化螢火蟲相關(guān)參數(shù)值,收斂常數(shù)e=1×10-5.由于待解決問題為0-1問題,所以需要對螢火蟲初始位置進行離散化操作：

(14)

收斂條件為：bestfun(t)-bestfun(t-1)≤e&bestfun(t)>bestfun(t-1)，其中bestfun(t)表示第t次迭代的最佳值.

Step2：根據(jù)式(7)～(9)設(shè)置每只螢火蟲的熒光素.

Step3：根據(jù)式(10)選擇螢火蟲j視野范圍內(nèi)的螢火蟲數(shù)目.

Step4：根據(jù)式(11)計算螢火蟲向Nmtj內(nèi)每只螢火蟲移動的概率,利用輪盤方法找出螢火蟲j移動方向.

Step5：根據(jù)式(15)更新螢火蟲j的位置

(15)

由于本文解決的問題為0-1 NLIP問題,所以需要將基于連續(xù)的位置更新策略改變?yōu)檫m應(yīng)于離散狀態(tài)下的位置更新策略(具體更新方式為式(15)).

Step6：根據(jù)式(13)更新螢火蟲決策半徑.

Step7：滿足最大迭代次數(shù)或收斂條件,返回最優(yōu)解；否則t=t+1,返回Step2.

2　結(jié)果與討論

仿真平臺為Matlab2010a,CPU為Intel(R) i3,2.1 GHz,內(nèi)存2 GB,Win7操作系統(tǒng).仿真假設(shè)在靜態(tài)瑞利信道且L=1的無線環(huán)境下進行,中繼節(jié)點數(shù)為N(N=4,5,6,7,8),所有中繼節(jié)點采用(1)相同功率P1=P2=…=PN=10 dB;(2)不同功率Pmax=10 dB,路徑損耗因子為4.螢火蟲算法詳細參數(shù)設(shè)置如表1所示,中繼距離參數(shù)(為便于計算,取相對值)dsn和dnd取分布區(qū)間為[0.1,2]范圍內(nèi)的隨機值，dsn(n=1,2,…,N)表示源節(jié)點到中繼節(jié)點的距離;dnd(n=1,2,…,N)表示目的節(jié)點到中繼節(jié)點的距離.表1同時列出了當N=4時的中繼距離參數(shù).

表1　GSO參數(shù)及節(jié)點距離

在上述參數(shù)設(shè)定下,對螢火蟲算法(GSO)與傳統(tǒng)的窮舉搜索(Exhaustive)、單個中繼選擇[6]662及次優(yōu)中繼選擇方案[9]1417進行了比較仿真.圖2表明,螢火蟲算法和窮舉搜索得出了相同的信噪比值,同時,顯示了螢火蟲算法中繼選擇的信噪比明顯優(yōu)于單個最優(yōu)中繼選擇和次優(yōu)中繼選擇,說明螢火蟲算法在解決中繼節(jié)點問題上是可行的.

圖2　不同策略下的最大信噪比 (N=4)

為驗證所提螢火蟲算法的有效性,圖3給出了相同條件下螢火蟲算法和窮舉搜索計算所需要的運行時間,螢火蟲算法耗時為0.385 s,僅為窮舉搜索所需時間(0.765 s)的50%,說明螢火蟲算法能夠更快地獲得搜索結(jié)果.圖4驗證了螢火蟲算法與次優(yōu)中繼選擇方案在中繼節(jié)點數(shù)增加時的復雜度.當中繼節(jié)點數(shù)增加時,螢火蟲算法和次優(yōu)化算法計算所需時間基本上與節(jié)點數(shù)N呈線性關(guān)系,但是理論上當N增大時,窮舉所搜所需要的時間與2N-1有關(guān),將呈級數(shù)增長,因此螢火蟲算法在多中繼節(jié)點選擇問題中可以有效地縮減選擇時間,提升系統(tǒng)性能.

圖3　不同源節(jié)點功率模擬的運行時間 (N=4)

圖4　不同中繼節(jié)點數(shù)量模擬的運行時間(P=10 dB)Figure 4　Running time by different relay node numbers (P=10 dB)

3　結(jié)論

本文將螢火蟲算法應(yīng)用于解決認知無線電多中繼選擇問題中,對螢火蟲算法進行適當變化,使之適應(yīng)0-1 NLIP模型,給出了目標函數(shù)和基于螢火蟲算法的中繼選擇步驟,通過多次迭代得到多中繼節(jié)點的選擇方案.相較傳統(tǒng)的窮舉搜索算法、最優(yōu)節(jié)點選擇算法和次優(yōu)節(jié)點選擇算法,所提方案性能更優(yōu),獲得結(jié)果更快.因此,應(yīng)用螢火蟲算法解決協(xié)作通信多中繼選擇問題具有明顯的優(yōu)越性.

[1]FRANK H P, KATZ F. Cooperation in wireless networks: principles and applications: real egoistic behavior is to cooperate![M].New Jersey:Springer,2006:13-26.

[2]SENDONARIS A, ERKIP E, AAZHANG B. User co-operation diversity. Part I. System description[J]. IEEE Transactions on Communications, 2003, 51(11): 1927-1938.

[3]SENDONARIS A, ERKIP E, AAZHANG B. User co-operation diversity. Part II. Implementation aspects and performance analysis[J]. IEEE Transactions on Communications, 2003, 51(11): 1927-1948.

[4]LANEMAN J N, TSE D N C, WORNELL G W. Cooperative diversity in wireless networks: efficient protocols and outage behavior[J]. IEEE Transactions on Information Theory, 2004, 50(12): 3062-3080.

[5]HUNTER T E. Diversity through coded cooperation[J]. IEEE Transactions on Wireless Communications, 2006, 5(2): 283-289.

[6]BLETSAS A, KHISTI A, REED D P, et al. A simple cooperative diversity method based on network path selection[J]. IEEE Journal on Selected Areas in Communications, 2006, 24(3): 659-672.

[7]IBRAHIM A S, SADEK A K, SU W, et al. SPC12-5: relay selection in multi-node cooperative communications: when to cooperate and whom to cooperate with?[C]∥Global Telecommunica-tions Conference, GLOBECOM06. San Francisco: IEEE, 2006: 1-5.

[8]SOYSA M, SURAWEERA H A, TELLAMBURA C, et al. Partial and opportunistic relay selection with outdated channel estimates[J]. IEEE Transactions on Communications,2012, 60(3): 840-850.

[9]JING Y, JAFARKHANI H. Single and multiple relay selection schemes and their achievable diversity orders[J]. IEEE Transactions on Wireless Communications, 2009, 8(3): 1414-1423.

[10]JING Y, JAFARKHANI H. Network beamforming using relays with perfect channel information[J]. IEEE Transactions on Information Theory, 2009, 55(6): 2499-2517.

[11]ATAPATTU S, JING Y, JIANG H, et al. Relay selection and performance analysis in multiple-user networks[J]. IEEE Journal on Selected Areas in Communications, 2013, 31(8): 1517-1529.

[12]DU M, LEI X, WU Z. A simplified glowworm swarm optimization algorithm[C]∥2014 IEEE Congress on Evolutionary Computation (CEC). Beijing: IEEE, 2014: 2861-2868.

[13]KUO R J, YANG C Y. Simulation optimization using particle swarm optimization algorithm with application to assembly line design[J]. Applied Soft Computing, 2011, 11(1): 605-613.

[14]LIANG Y, LEUNG K S. Genetic Algorithm with adaptive elitist-population strategies for multimodal function optimization[J]. Applied Soft Computing, 2011, 11(2): 2017-2034.

[15]LEI X, HUANG X, ZHANG A. Improved artificial bee colony algorithm and its application in data clustering[C]∥Bio-Inspired Computing: 2010 IEEE Fifth International Conference on Theories and Applications (BIC-TA). Shanghai: IEEE,2010: 514-521.

[16]KRISHNANAND K N, GHOSE D. Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications[J]. Multiagent and Grid Systems, 2006, 2(3): 209-222.

[17]KRISHNANAND K N, GHOSE D. Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations[J]. Robotics and Autonomous Systems, 2008, 56(7): 549-569.

[18]KRISHNANAND K N, GHOSE D. Glowworm swarm optimisation: a new method for optimising multi-modal functions[J]. International Journal of Computational Intelligence Studies, 2009, 1(1): 93-119.

[19]KRISHNANAND K N, GHOSE D. Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions[J]. Swarm Intelligence, 2009, 3(2): 87-124.

[20]HANSEN P. Methods of nonlinear 0-1 programming[J]. Annals of Discrete Mathematics, 1979, 5(8): 53.

[21]KRISHNANAND K N, GHOSE D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]∥ Proceedings of the 2005 IEEE Swarm Intelligence Symposium. Piscatawag: IEEE, 2005: 86.

[22]ALJARAH I, LUDWIG S A. A new clustering approach based on glowworm swarm optimization[C]∥ 2013 IEEE Congress on Evolutionary Computation (CEC). Cancun: IEEE,2013: 2642-2649.

[23]HE D X,LIU G Q,ZHU H Z.Glowworm swarm optimization algorithm for solving multi-objective optimization problem[C]∥Proceedings of the 9th International Conference on Compu-tational Intelligence and Security.Le-shan: IEEE,2013:11-15.

[24]唐思騰,劉紫燕,帥暘.基于螢火蟲算法的多中繼功率分配[J]. 電訊技術(shù),2014, 54(10):1407-1412.

TANG S T,LIU Z Y,SHUAI Y.Power allocation for multi-relay cooperative systems based on glowworm swarm optimization algorithm[J].Telecommunication Engineering,2014,54(10):1409.

【中文責編：成文英文責編：肖菁】

Multiple Relay Selection Scheme Based on Glowworm Swarm Optimization Algorithm

CHENG Tonglong, ZHANG Han*

(School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China)

Relay selection (RS) and power control are two essential parts in wireless relay network. RS is equal to power control in the condition that a relay cooperates with its full power or without any cooperation. Thus, the optimal signal-to-noise ratio (SNR) is interpreted as a 0-1 nonlinear programming integer problem (NLIP). A Glowworm Swarm Optimization (GSO) based multiple relay selection (MRS) scheme is proposed, which can fully obtain the optimal SNR value. Simulations results show that the proposed GSO-aided MRS scheme is superior to the conventional schemes, including the exhaustive search methods, single RS scheme and other suboptimal MRS schemes.

wireless network; multiple relay selection; glowworm swarm optimization

2015-04-27《華南師范大學學報(自然科學版)》網(wǎng)址：http://journal.scnu.edu.cn/n

國家自然科學基金項目(61471176,61002012)；廣東省自然科學基金項目(S2013010016297);廣東省數(shù)字信號與圖像處理技術(shù)重點實驗室開放基金項目(2015)；廣東省高等學校優(yōu)秀青年教師培養(yǎng)計劃項目(YQ2015046)

張涵,教授,Email: zhanghan@scnu.edu.cn.

TN929.5

A

1000-5463(2016)03-0088-05