蔣萍，唐天兵

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

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

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

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

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

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

1 引言

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

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

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

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

2.1 問(wèn)題描述

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

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

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

p＝｛p1，p2，…，pn｝

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

其中，C（m）的計(jì)算方法為

3 算法設(shè)計(jì)

3.1 復(fù)合形法

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

3.2 小生境操作

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

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

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

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

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

（1）編碼

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

（2）個(gè)體

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

（3）種群及其初始化

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

（4）評(píng)價(jià)函數(shù)

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

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

（5）選擇操作

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

（6）交叉操作

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

（7）變異操作

（8）小生境操作

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

（9）復(fù)合形法

此法針對(duì)每個(gè)小生境進(jìn)行，其操作過(guò)程如下：

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

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

3）以中心Xc為映射中心，按式（7）計(jì)算壞點(diǎn)Xw的映射點(diǎn)Xr：

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

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

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

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

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

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

4.2 結(jié)果分析

實(shí)驗(yàn)場(chǎng)景設(shè)計(jì)如下：

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

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

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

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

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

圖3 本文算法延長(zhǎng)網(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)，分別為深色、灰色與淺色，其中淺色曲線(xiàn)與灰色曲線(xiàn)分別為文獻(xiàn)［7］中MPA與APMRE算法對(duì)應(yīng)結(jié)果，深色曲線(xiàn)為本文算法實(shí)驗(yàn)對(duì)應(yīng)結(jié)果。

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

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

5 結(jié)束語(yǔ)

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

［1］季薇.無(wú)線(xiàn)通信中的若干關(guān)鍵問(wè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］張國(guó)鵬，顧潔，劉鵬，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中基于博弈論的協(xié)作通信策略［J］.武漢理工大學(xué)學(xué)報(bào)，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é)報(bào)，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］周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用［M］.北京：國(guó)防工業(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àn)椴⑿蟹植际接?jì)算和優(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é)獲控制理論與控制工程專(zhuān)業(yè)碩士學(xué)位，現(xiàn)為副教授、碩士生導(dǎo)師，主要研究方向?yàn)椴⑿蟹植际接?jì)算和計(jì)算智能。

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

國(guó)家自然科學(xué)基金資助項(xiàng)目（61102090）

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

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