蔣萍，唐天兵

（1.廣西大學(xué)計算機與電子信息學(xué)院，南寧530004；2.廣西政法管理干部學(xué)院信息工程系，南寧530023）

復(fù)合形遺傳算法求解功率優(yōu)化分配研究?

蔣萍1，2，??，唐天兵1

（1.廣西大學(xué)計算機與電子信息學(xué)院，南寧530004；2.廣西政法管理干部學(xué)院信息工程系，南寧530023）

傳統(tǒng)遺傳算法存在過早收斂及局部搜索能力差的缺點，在求解無線網(wǎng)絡(luò)協(xié)作通信功率優(yōu)化分配等NP難問題時難以求得最優(yōu)解。通過小生境策略解決遺傳算法過早收斂問題，引入復(fù)合形法提高局部搜索能力，構(gòu)造了兼顧廣度搜索與深度搜索的高性能混合算法，并對上述問題進行求解。實驗結(jié)果表明，所提算法與已有算法相比有一定優(yōu)勢，有效延長了協(xié)作網(wǎng)絡(luò)壽命，穩(wěn)定性較好，分配的功率波動范圍小。

協(xié)作通信；遺傳算法；功率分配；小生境策略

1 引言

協(xié)作通信基于多用戶環(huán)境獲得發(fā)射分集的增益，實現(xiàn)通信效果的增強。針對協(xié)作通信，學(xué)者研究的方向涉及中繼協(xié)作策略［1］、協(xié)作信號的設(shè)計與檢測［2］、協(xié)作中繼節(jié)點選擇及功率最優(yōu)分配［3］等方面。

協(xié)作通信功率最優(yōu)分配問題是一個NP難問題，在考慮誤碼率等約束條件時其目標(biāo)函數(shù)具有高度非線性特征，常規(guī)算法求解效果欠佳。如文獻(xiàn)［4］基于中斷概率提出的拉格朗日乘數(shù)法能快速求解，但精度較低；文獻(xiàn)［5］基于放大轉(zhuǎn)發(fā)中繼模式提出兩種分配方案，即自適應(yīng)功率分配方案和等功率分配策略方案，前者要稍優(yōu)于后者，但前者從一組人為設(shè)計的初始值開始，非最優(yōu)最初值形成的分配序列也并非最優(yōu)。

遺傳算法是一種具有很強魯棒性的智能算法，其適合對NP難等問題的求解，但會過早收斂且局部搜索能力差，在求解該類問題時效果有時也不理想。本文以小生境引入復(fù)合形的思路，構(gòu)造兼顧廣度搜索及深度搜索的高效混合算法，最后通過仿真實驗驗證了設(shè)計算法求解協(xié)作網(wǎng)絡(luò)功率分配問題的有效性。與已有文獻(xiàn)相比，本文算法優(yōu)于自適應(yīng)最大化剩余能量與最小化分配功率分配策略，表現(xiàn)出較好性能。

2 協(xié)作通信網(wǎng)絡(luò)壽命問題及建模

2.1 問題描述

功率分配是影響協(xié)作網(wǎng)絡(luò)壽命的最重要因素，若每次能分配一個滿足條件而數(shù)值較小的功率，則整個協(xié)作網(wǎng)絡(luò)的壽命可能獲得延長。協(xié)作網(wǎng)絡(luò)中的總功率為源節(jié)點功率和被選擇作為協(xié)作伙伴的中繼節(jié)點對應(yīng)的功率之和，各方案中對應(yīng)的源節(jié)點功率均一樣，因此只考慮將中繼節(jié)點的功率和作為性能參數(shù)。功率分配問題表示對一組數(shù)量固定的中繼節(jié)點分配一定的功率的問題，其既要使整個網(wǎng)絡(luò)能正常工作（即能滿足一定的約束條件），又要使網(wǎng)絡(luò)的總功能最小。本文以誤碼率作為約束條件對功率的分配進行研究，即在滿足既定誤碼率的條件下實現(xiàn)對網(wǎng)絡(luò)分配較小的功率，為此首先對問題進行建模。

2.2 數(shù)學(xué)建模

設(shè)包含在協(xié)作網(wǎng)絡(luò)中可用中繼節(jié)點數(shù)為n，功率分配的一個方案可表示為

p＝｛p1，p2，…，pn｝

其中，pi∈［0，eiu］，i＝1，2，…，n，eiu表示第i個中繼節(jié)點當(dāng)前擁有能量的上限值。當(dāng)pi取值為0，表示對應(yīng)中繼節(jié)點沒有參與該次的協(xié)同通信。對協(xié)作通信的功率分配問題建立的數(shù)學(xué)模型如下：

其中，C（m）的計算方法為

3 算法設(shè)計

3.1 復(fù)合形法

復(fù)合形法是一種直接搜索方法，它只通過比較各設(shè)計點的目標(biāo)函數(shù)和約束條件的數(shù)值來進行搜索，基本步驟是：首先在N維設(shè)計空間中構(gòu)成頂點數(shù)P大于（N＋1）的復(fù)合形，然后進行尋優(yōu)搜索，包括反射、延伸和搜索，替代復(fù)合形中目標(biāo)函數(shù)最大的點——最差點，如此反復(fù)進行，使復(fù)形逐步縮小，逼近最優(yōu)點。對于功率分配問題，將每個中繼節(jié)點所取功率作為一個維度，所有節(jié)點的取值對應(yīng)一種功率分配方案，構(gòu)成一個頂點，此頂點的好壞則根據(jù)2.2節(jié)中描述的模型進行評判。

3.2 小生境操作

小生境技術(shù)產(chǎn)生于對自然界“物以類聚，人以群分”現(xiàn)象的模擬，在群體中構(gòu)造不同的和特定的個體生存環(huán)境，并對各生存環(huán)境中優(yōu)秀個體實施保護措施，使之在進化過程中不至于被迅速同化，也就使具有不同適應(yīng)度和潛力的個體得以生存，因此能有效維持群體多樣性，從而防止群體過早收斂。

3.3 基于小生境的復(fù)合形混合遺傳算法

根據(jù)前文構(gòu)造混合算法的思想，設(shè)計的混合遺傳算法如圖1所示。從圖中可以看到，混合遺傳算法的主體分為三部分，即遺傳操作、小生境操作與復(fù)合形法。遺傳操作從整體出發(fā)進行搜索，然后針對未被小生境操作淘汰的個體執(zhí)行復(fù)合形法。在算法執(zhí)行結(jié)束后，算法輸出的最優(yōu)個體即對應(yīng)功率分配方案。

圖1 求解功率分配問題的小生境復(fù)合形遺傳算法Fig.1 Niching complex genetic algorithm for solving power allocation problem

為實現(xiàn)對協(xié)作網(wǎng)絡(luò)功率優(yōu)化問題的求解，算法實現(xiàn)如下所述。

（1）編碼

采用浮點數(shù)編碼，即其每一個基因位上的取值為一個浮點數(shù)，且表示的意義為分配給與基因位標(biāo)號一致的中繼節(jié)點的工作功率，各基因取值時最大不超過各中繼節(jié)點擁有的能量。

（2）個體

對功率分配問題，其對應(yīng)個體為由一系列實數(shù)組成的數(shù)組，表示為（p1，p2，p3，…，pn），pi表示第i個中繼節(jié)點對應(yīng)功率值，其中n表示協(xié)作網(wǎng)絡(luò)中需分配功率的中繼節(jié)點的數(shù)量。

（3）種群及其初始化

功率分配對應(yīng)種群也可形式化表示為（ch1，ch2，ch3，…，chm），其中chi（i＝1，2，3，…，）表示各個個體，而m表示種群的規(guī)模大??；而在當(dāng)進行種群的初始化時，需根據(jù)各中繼節(jié)點當(dāng)前擁有的能量來產(chǎn)生在該數(shù)值范圍內(nèi)的隨機數(shù)組成初始種群。

（4）評價函數(shù)

對功率分配問題，其評價函數(shù)在滿足誤碼率約束條件的下協(xié)作伙伴的功率和達(dá)到最小，因此建立的評價函數(shù)如式（5）所示的評價函數(shù)為

式中，p表示一個功率分配方案，最后輸出得分最高的方案為問題求解結(jié)果。若某一選擇方案違反相應(yīng)約束時，返回的函數(shù)值為0，代表算法對該方案進行了舍棄。

（5）選擇操作

采用聯(lián)賽選擇策略實現(xiàn)選擇算子，即每次隨機選擇一定數(shù)量的個體并進行逐一比較，最后將最好的個體則加到新種群中。重復(fù)多次，直至新種群達(dá)到設(shè)計規(guī)模大小。在選擇操作結(jié)束時實施精英保存策略，將上一代最優(yōu)秀個體替換掉新種群中最差的個體。

（6）交叉操作

對浮點數(shù)編碼的個體，本文選擇算術(shù)交叉完成對個體基因的重組。

（7）變異操作

（8）小生境操作

對進行遺傳操作后的種群，分別兩兩計算各個個體間的歐氏距離［6］，當(dāng)歸一化的歐氏距離（如式（6））小于設(shè)定值D時則對較差個體的適應(yīng)度值設(shè)為0，以將其清除。最后未被清除的個體作為小生境中心成員，所有與中心成員距離小于D的，重新構(gòu)成一小種群，最后對這些小種群分別執(zhí)行復(fù)合形法，實現(xiàn)對個體適應(yīng)度值的提升。下式為歸一化歐氏距離的計算方法，其中N表示遺傳算法種群設(shè)計的規(guī)模，n為求解變量個數(shù)，本文中對應(yīng)中繼節(jié)點的數(shù)量。

（9）復(fù)合形法

此法針對每個小生境進行，其操作過程如下：

1）找出小生境內(nèi)的最差點及最優(yōu)點，設(shè)為Xw及Xb；

2）計算除最差點外所有點對應(yīng)的中心，設(shè)為Xc；

3）以中心Xc為映射中心，按式（7）計算壞點Xw的映射點Xr：

式中，a為映射系數(shù)，通常取值大于1；

4）比較Xr與Xw，若Xr優(yōu)于Xw，則以Xr替換Xw，否則令a＝0.5a，重新計算式（7），直至替換成功；

5）為平衡遺傳算法及復(fù)合形的搜索性能，上述替換一旦成功或映射次數(shù)達(dá)設(shè)定次數(shù)時，則結(jié)束當(dāng)前復(fù)合形操作，而繼續(xù)圖2所示迭代過程。

圖2 能量受限基于遺傳算法的功率分配算法Fig.2 Power allocation based on genetic algorithm with energy limited

4 實驗與結(jié)果分析

4.1 實驗環(huán)境

本文實現(xiàn)算法的編程語言為matlab，實驗環(huán)境為：Intel E5400 2.70 GHz Pentium（R）雙核CPU，含2MB二級cache；2G DDR3內(nèi)存；WindowsXP SP3的操作系統(tǒng)。對各控制參數(shù)進行如下設(shè)置：算法迭代500次，種群規(guī)模100，交叉概率0.85，變異概率0.50，小生境容量為1，復(fù)合形映射次數(shù)為5。

4.2 結(jié)果分析

實驗場景設(shè)計如下：

（1）源目節(jié)點距離歸一化為1，而所有中繼節(jié)點則隨機分布在邊長為1的正方形內(nèi)；

（2）場景中源節(jié)點與中繼節(jié)點的發(fā)射功率設(shè)為在區(qū)間［5，10］取的隨機數(shù)；

（3）誤碼率約束上限S取值為10－5，目的節(jié)點的實際誤碼率根據(jù)公式（3）與選擇的中繼節(jié)點具體狀況進行計算，計算時路徑耗損指數(shù)v取2，并且采用BPSK方式進行調(diào)制，因此公式中系數(shù)k為2；

（4）對源節(jié)點功率，在第一部分實驗分別取6 dB、8 dB與10 dB 3個值，第二部分實驗則分別在［0，20］區(qū)間內(nèi)進行采樣；

（5）噪聲量化為1，即各節(jié)點工作功率與信噪比在數(shù)值上相等；協(xié)作網(wǎng)絡(luò)中各中繼節(jié)點具有100倍于源節(jié)點功率的電量。在進行實驗時，文獻(xiàn)［7］設(shè)計了兩種算法，分別為自適應(yīng)最大化剩余能量算法（Adaptive Power Maximal Residual Energy，APMRE）與最小化分配功率算法（Minimum Power Allocation，MPA），本文與這兩種算法的比較結(jié)果如圖3所示。與此同時，該文獻(xiàn)還以MPA算法考察了不同源功率時固定14個中繼節(jié)點對應(yīng)協(xié)作網(wǎng)絡(luò)的功耗情況，本文算法與之進行比較結(jié)果如圖4所示。在下述圖中，HGA代表本文基于小生境復(fù)合形遺傳算法取得的結(jié)果。

圖3 本文算法延長網(wǎng)絡(luò)壽命效果比較Fig.3 Life time comparison based on proposed algorithm

圖4 中繼網(wǎng)絡(luò)平均功率比較Fig.4 Average power comparison of relay network

在圖3中，有3組不同濃度的曲線，分別為深色、灰色與淺色，其中淺色曲線與灰色曲線分別為文獻(xiàn)［7］中MPA與APMRE算法對應(yīng)結(jié)果，深色曲線為本文算法實驗對應(yīng)結(jié)果。

從圖3可知，與文獻(xiàn)結(jié)果，本文算法在延長協(xié)作網(wǎng)絡(luò)使用壽命方面更具有效性，在相同源功率時幾乎均能取得更長的網(wǎng)絡(luò)工作時長，存在少數(shù)部分情況效果變差或者波動在、穩(wěn)定性欠佳的情況，這是由于遺傳算法是一種隨機性搜索算法原故，即使對于相同的場景與模擬參數(shù)，求解的結(jié)果仍有可能不完全相同。總體上本文方法仍然具有一定的優(yōu)勢。

而從圖4可知，兩種算法均有中繼網(wǎng)絡(luò)消耗功率隨源功率增大而減小的趨勢，而本文中基于遺傳算法的策略則具有更好的性能，取得了更小的功率消耗，最好情況約節(jié)省25％。

5 結(jié)束語

本文針對能量上限的協(xié)作網(wǎng)絡(luò)功率優(yōu)化分配問題，提出了一種基于混合遺傳算法的功率分配算法。與已有算法相比，本文算法能有效地延長協(xié)作網(wǎng)絡(luò)壽命，每次分配的功率較小且僅在小范圍內(nèi)波動，有較好的穩(wěn)定性，是一種有效的協(xié)作網(wǎng)絡(luò)功率優(yōu)化分配算法。這為解決協(xié)作通信功率分配提供了新思路。

［1］季薇.無線通信中的若干關(guān)鍵問題研究［D］.上海：上海交通大學(xué)，2009. JIWei.Research on Key Techniques ofWireless Cooperative Communication［D］.Shanghai：Shanghai Jiaotong University，2009.（in Chinese）

［2］Li R K，Bai Z Q，Kwak K.Space frequency codes based amplify and forward cooperative system［C］//Proceedings of 9th International Symposium on Communications and Information Technology.Lcheon：IEEE，2009：1185－1188.

［3］張國鵬，顧潔，劉鵬，等.無線傳感器網(wǎng)絡(luò)中基于博弈論的協(xié)作通信策略［J］.武漢理工大學(xué)學(xué)報，2010，32（19）：133－136. ZHANG Guo-peng，GU Jie，LIU Peng，et al.Cooperative Communication Strategy forWireless Sensor Networks Based on Cooperative Game Theory［J］.JournalofWuhan University of Technology，2010，32（19）：133－136.（in Chinese）

［4］唐倫，王歡，陳前斌，等.認(rèn)知OFDM網(wǎng)絡(luò)中基于中斷概率約束的功率分配［J］.北京郵電大學(xué)學(xué)報，2010，33（1）：120－123. TANG Lun，WANGHuan，CHENQian-bin，etal.Power Allocation for Cognitive OFDM Radio Networksunder Primary User′s Outage Probability Constraint［J］.Journalof Beijing University of Posts and Telecommunications，2010，33（1）：120－123.（in Chinese）

［5］Maham B，Hj?rungnes A.Minimum Power Allocation in SER Constrained Amplify-and-Forward Cooperation［C］//Proceedings of 2008 67th IEEE Vehicular Technology Conference. Calgary，Canada：IEEE，2008：2431－2435.

［6］周明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京：國防工業(yè)出版社，2005. ZHOU Ming，SUN Shu-dong.Principle and Application of Genetic Algorithm［M］.Beijing：National Defence Industry Press，2005.（in Chinese）

［7］Maham B，Hj?rungnes A，Debbah M.Power allocations in minimum-energy SER-constrained cooperative networks［J］. Annals of Telecommunications，2009，64（7）：545－555.

蔣萍（1981—），女，廣西資源人，現(xiàn)為講師、碩士研究生，主要研究方向為并行分布式計算和優(yōu)化算法；

JIANG Ping was born in Ziyuan，Guangxi Zhuang Autonomous Region，in 1981.She isnow a lecturer and also a graduate student.Her research concerns parallel distributed computing and optimization algorithm.

Email：j－pingzi＠163.com

唐天兵（1972—），男，四川成都人，1997年于廣西大學(xué)獲控制理論與控制工程專業(yè)碩士學(xué)位，現(xiàn)為副教授、碩士生導(dǎo)師，主要研究方向為并行分布式計算和計算智能。

TANG Tian-bing was born in Chengdu，Sichuan Province，in 1972.He received the M.S.degree from Guangxi University in 1997.He is now an associate professor and also the instructor of graduate students.His research concerns parallel distributed computing and computational intelligence.

Optimal Power Allocation Based on Com plex Genetic Algorithm

JIANG Ping1，2，TANG Tian-bing1
（1.School of Computer，Electronics and Information，GuangxiUniversity，Nanning 530004，China；2.Departmentof Information Engineering，Guangxi Administrative Cadre Institute of Politics and Law，Nanning 530023，China）

The traditional genetic algorithm，which has the shortcomings of premature convergence and poor local search ability，is hard to solve the power allocation problem（NP-hard problem）of wireless network cooperative communication.This paper conqueres the premature convergence by introducing niche strategy，and improves the local search capabilities by combining complexmethod，constructs a high-performance algorithm taking accountof the breadth and depth in searching，and then solves the power allocation problem.The simulation results show that the proposed strategy is better than the existing algorithms.It is able to effectively extend network lifetime，generatesmore stable values，and performs a good stability.

cooperative communication；genetic algorithm；power allocation；niche strategy

TN911

A

1001－893X（2013）02－0195－05

10.3969/j.issn.1001－893x.2013.02.016

2012－06－29；

2012－09－05 Received date：2012－06－29；Revised date：2012－09－05

國家自然科學(xué)基金資助項目（61102090）

Foundation Item：The National Natural Science Foundation of China（No.61102090）

??通訊作者：j－pingzi＠163.com Corresponding author：j－pingzi＠163.com