杜傳報(bào)　全厚德　唐友喜　劉建成　梁偉,3

(1.軍械工程學(xué)院信息工程系,石家莊 050003;2.電子科技大學(xué) 通信抗干擾技術(shù)

國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室,成都 611731;3.清華大學(xué)自動(dòng)化系,北京 100084)

?

基于膜量子布谷鳥搜索的雙通道網(wǎng)絡(luò)頻譜資源分配

杜傳報(bào)1全厚德1唐友喜2劉建成1梁偉1,3

(1.軍械工程學(xué)院信息工程系,石家莊 050003;2.電子科技大學(xué) 通信抗干擾技術(shù)

國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室,成都 611731;3.清華大學(xué)自動(dòng)化系,北京 100084)

摘要無(wú)線雙通道Ad Hoc網(wǎng)絡(luò)中,有效分配簇間碼分頻譜資源是提高資源利用效率的關(guān)鍵技術(shù)之一.綜合考慮子簇碼分頻譜資源需求和分配公平性,給出了簇間碼分頻譜資源分配數(shù)學(xué)模型,并轉(zhuǎn)換為以最大化碼分頻譜資源效益和分配公平性為多目標(biāo)的受約束離散優(yōu)化問題.結(jié)合膜結(jié)構(gòu)、量子計(jì)算和布谷鳥搜索算法,提出一種新的離散組合優(yōu)化算法——膜量子布谷鳥搜索算法.該算法使用量子鳥窩表征問題潛在解,利用布谷鳥尋窩產(chǎn)卵的演化方法在基礎(chǔ)膜中尋求單目標(biāo)最優(yōu)解,通過膜間信息共享和非支配解等級(jí)排序求出具有多目標(biāo)最優(yōu)解的表層膜Pareto前端解集.仿真結(jié)果證明,與經(jīng)典優(yōu)化算法相比,該算法不僅能夠同時(shí)求解單目標(biāo)和多目標(biāo)最優(yōu)解,而且具有更優(yōu)的收斂性能,能更好地實(shí)現(xiàn)碼分頻譜資源效益最優(yōu)化.

關(guān)鍵詞雙通道網(wǎng)絡(luò)；碼分頻譜資源；膜結(jié)構(gòu)；量子計(jì)算

DOI10.13443/j.cjors.2015040901

Frequency spectrum resource allocation based on membrane-inspired quantum cuckoo search for wireless dual-channel ad hoc network

DU Chuanbao1QUAN Houde1TANG Youxi2LIU Jiancheng1LIANG Wei1,3

(1.DepartmentofInformationEngineering,OrdnanceEngineeringCollegeShijiazhuang050003,China；2.NationalKeyLabofScienceandTechnologyonCommunication,UniversityofElectronicScienceandTechnologyofChina,Chengdu611731,China； 3.DepartmentofAutomation,TsinghuaUniversity,Beijing100084,China)

Abstract In wireless dual-channel ad hoc network, allocating the inter-cluster code resource efficiently is the key to improve the code frequency resource utilization efficiency. Taken the code spectrum resource requirement and assignment fairness for each cluster into account, a mathematical model of inter-cluster code frequency spectrum resource allocation is proposed, and converted into a constrained discrete multi-objective optimization problem. In addition, a novel discrete combinator optimization algorithm called membrane-inspired quantum cuckoo search algorithm (MQCSA) is presented based on membrane structure, quantum computation and cuckoo search algorithm(CSA). In MQCSA, quantum nest is used to represent the potential solutions, and the global optimal solution of single objective in the elementary membranes is searched with CSA, and then the optimal Pareto front solutions are calculated for obtaining multi-objective optimal solutions from the skin membrane according to inter-membrane searched information sharing and non-dominated solutions sorting. Finally, a novel code resource allocation method based on MQCSA is designed. The results show that, both the optimal solutions for single-objective and multiple-objective optimization problems can be solved, and higher efficiency on convergence performance can be obtained, which leads to the maximization of code frequency spectrum resource.

Keywords dual-channel network； code frequency spectrum resource； membrane structure； quantum computing

引言

無(wú)線雙通道Ad Hoc網(wǎng)絡(luò)是針對(duì)某現(xiàn)役電臺(tái)設(shè)計(jì)的新型戰(zhàn)術(shù)超短波自組織網(wǎng)絡(luò)[1].該網(wǎng)絡(luò)基于分層分布式同步組網(wǎng)體制,使用由控制通道和數(shù)據(jù)通道組成的雙通道結(jié)構(gòu)實(shí)現(xiàn)在大規(guī)模戰(zhàn)術(shù)環(huán)境下電臺(tái)群之間的互聯(lián)互通,能夠有效地解決傳統(tǒng)組網(wǎng)方式產(chǎn)生的碼分頻譜資源浪費(fèi)問題.無(wú)線雙通道網(wǎng)絡(luò)在兼顧效率和公平性的條件下如何有效分配簇間碼分頻譜資源成為急需解決的問題.碼分頻譜資源分配可參考目前主流研究的認(rèn)知無(wú)線電網(wǎng)絡(luò)頻譜分配模型[2],如圖論著色模型[3]、定價(jià)拍賣模型[4]、干擾溫度模型[5]和博弈論模型[6]等.

目前認(rèn)知無(wú)線網(wǎng)絡(luò)頻譜分配主要是基于圖論著色模型的群智能優(yōu)化算法,包括量子遺傳算法(Quantum Genetic Algorithm, QGA)[7]、量子粒子群算法(Quantum-behaved Particle Swarm Optimzation, QPSO)[8-9]和膜量子人工蜂群優(yōu)化算法(Membrane-inspired Quantum Artificial Bee Colony Optimization, MQABCO)[10]等.這些算法在求解低維問題時(shí),其收斂性能和速度能夠滿足工程要求,但在解決頻譜資源分配等高維離散優(yōu)化問題時(shí),其收斂性嚴(yán)重惡化,存在維數(shù)災(zāi)問題.QGA、QPSO等智能優(yōu)化算法僅考慮了單目標(biāo)優(yōu)化問題,不能解決碼分頻譜資源分配中兼顧利用效率和分配公平性的多目標(biāo)優(yōu)化問題.MQABCO是一種利用膜結(jié)構(gòu)的群智能優(yōu)化算法,能夠解決多目標(biāo)優(yōu)化問題,但是存在收斂速度較慢的問題.因此,將在具有更快收斂速度的群智能算法基礎(chǔ)上引入生物膜結(jié)構(gòu)以設(shè)計(jì)新的優(yōu)化算法解決此問題.

布谷鳥搜索算法(Cuckoo Search Algorithm, CSA)是粒子群優(yōu)化算法的一種變種,是對(duì)布谷鳥借其他鳥類的窩哺育幼雛行為的模擬[11].現(xiàn)有研究[11-12]表明,CSA不僅具有流程簡(jiǎn)單、參數(shù)少、易于實(shí)現(xiàn)和收斂速度快的優(yōu)點(diǎn),其尋優(yōu)性能優(yōu)于粒子群算法和遺傳算法,但不能解決離散多目標(biāo)優(yōu)化問題.因此,使用CSA作為基礎(chǔ)群智能算法.

引入膜結(jié)構(gòu)[13]和量子計(jì)算[14],提出了膜量子布谷鳥搜索算法(Membrane-inspired Quantum CSA, MQCSA).MQCSA使用非支配解排序[15],使用量子鳥窩表征潛在解,利用布谷鳥群尋窩演化方法,在表層膜內(nèi)獲得均勻分布的非支配解集和Pareto前端解,并依據(jù)擁擠度排序,在Pareto前端解中選擇合適的解作為多目標(biāo)優(yōu)化的最優(yōu)解集輸出.其次,提出了基于MQCSA的碼分頻譜資源分配方法,給出了資源分配數(shù)學(xué)模型.仿真結(jié)果驗(yàn)證了方案的有效性.

1膜量子布谷鳥搜索算法

1.1膜結(jié)構(gòu)數(shù)學(xué)模型

P系統(tǒng)[16-17]是指由包含不同對(duì)象集的多個(gè)膜組成的系統(tǒng),其中不同的對(duì)象集在不同的膜限定的區(qū)域內(nèi)具有特定的進(jìn)化規(guī)則,并對(duì)這些對(duì)象集定義不同的輸入輸出.所有的對(duì)象集以并行的方式同時(shí)進(jìn)化,并且不同對(duì)象集可通過膜間交換進(jìn)行信息交流.設(shè)膜量子布谷鳥搜索算法的膜系統(tǒng)結(jié)構(gòu)為[16]

Π=(V,T,μ,w0,w1,…,wf,R0,R1,…,Rf,i0).

(1)

式中: V是字母表,V中的元素被稱為對(duì)象； T?V表示輸出字母表；μ表示度數(shù)為f+1的膜結(jié)構(gòu),其中每個(gè)膜使用{0,1,2,…，f}標(biāo)號(hào)集加以表示； wr(0≤r≤f)表示膜結(jié)構(gòu)μ中膜r區(qū)域中所包含的對(duì)象集；Rr(0≤r≤f)是膜結(jié)構(gòu)μ中膜r區(qū)域所包含的進(jìn)化規(guī)則的有限集,表示wr中使用的參數(shù)配置和進(jìn)化規(guī)則；i0表示輸出范圍在0到f之間的任一整數(shù),表層膜標(biāo)號(hào)為0,故使用表層膜0作為輸出膜.

1.2量子窩數(shù)學(xué)模型

本文使用量子鳥窩表示問題潛在解.量子計(jì)算是一種雙態(tài)量子系統(tǒng),其不同于傳統(tǒng)二進(jìn)制系統(tǒng),是在于它能夠落在狀態(tài)|0〉和|1〉的任何線性組合狀態(tài)上.量子比特狀態(tài)通常被表示為[14]

|φ〉=α|0〉+β|1〉.

(2)

式中,α和β分別代表狀態(tài)|0〉和|1〉的概率幅度,且有|α|2+|β|2=1.測(cè)量量子狀態(tài)時(shí)|0〉和|1〉的量子測(cè)量概率分別為|α|2和|β|2.量子測(cè)量是通過將處于疊加狀態(tài)的量子比特塌縮到特定的狀態(tài)來(lái)實(shí)現(xiàn)量子狀態(tài)的轉(zhuǎn)換.

膜結(jié)構(gòu)中包含的對(duì)象是量子比特和二進(jìn)制比特,分別表示量子窩的量子位置和測(cè)量位置.量子窩由量子比特構(gòu)成的向量表示,量子比特?cái)?shù)目取決于解的維數(shù).因此,有量子窩i為

(3)

式中,量子比特滿足|αij|2+|βij|2=1和0≤αij,βij≤1,且有αij=cosθij,βij=sinθij,其中θij為量子窩i的量子比特vij的量子旋轉(zhuǎn)角度.通過對(duì)量子窩的量子位置測(cè)量可得到由二進(jìn)制比特向量表示的測(cè)量位置.

(4)

(5)

MQCSA采用量子Hadamard門[18]取代量子非門進(jìn)行量子比特內(nèi)部的變異操作,旨在增加種群多樣性,以避免早熟收斂.設(shè)變異概率為pm,對(duì)每個(gè)量子窩產(chǎn)生介于0和1之間的隨機(jī)數(shù)randi.如果randi

(6)

1.3算法描述

MQCSA中量子布谷鳥和量子窩相同(即量子位置),對(duì)量子窩進(jìn)行量子測(cè)量得到由二進(jìn)制表示的測(cè)量位置.MQCSA尋優(yōu)過程主要有種群初始化、擇優(yōu)選擇和隨機(jī)遷移三個(gè)步驟.

在MQCSA中,Rr(0≤r≤f)代表膜r的進(jìn)化規(guī)則,并且所有量子布谷鳥平均分配給f個(gè)基礎(chǔ)膜和1個(gè)表層膜,故每個(gè)膜有h/(f+1)只量子布谷鳥.因?yàn)榱孔硬脊萨B使用1,2,…,h標(biāo)號(hào),則基礎(chǔ)膜r(1≤r≤f)內(nèi)的量子布谷鳥編號(hào)為

(7)

表層膜中的量子布谷鳥編號(hào)為

(8)

在基礎(chǔ)膜r內(nèi)量子窩i的第j維量子比特的進(jìn)化方程為

(9)

(10)

(11)

式中:a0是固定值；e1表示搜索步長(zhǎng)受膜內(nèi)全局最優(yōu)位置的影響程度.Lévy(β)～μ=t-1-β可簡(jiǎn)化[18]為

(12)

式中,u和r均服從正態(tài)分布,且有

(13)

(14)

基礎(chǔ)膜中的每只量子布谷鳥的量子旋轉(zhuǎn)角和量子位置均是通過式(9)、(10)更新.

在每次迭代過程中,MQCSA會(huì)以發(fā)現(xiàn)概率pd來(lái)淘汰種群中較差的個(gè)體,通過隨機(jī)生成相同數(shù)量的新個(gè)體替代,以增加種群的變異性,其量子旋轉(zhuǎn)角度更新公式為

(15)

基于量子布谷鳥搜索的膜框架結(jié)構(gòu)構(gòu)成如下:

1) 設(shè)標(biāo)號(hào)為0的表層膜內(nèi)部共有f個(gè)區(qū)域,膜結(jié)構(gòu)記作[0[1]1[2]2…[f]f]0；

2) 字母表V為由量子位置和二進(jìn)制的測(cè)量位置向量構(gòu)成的集合；

3) 字母表T表示二進(jìn)制的測(cè)量位置向量輸出集合；

4) 膜r包含的多重對(duì)象集合wr由量子位置集合構(gòu)成,每個(gè)膜內(nèi)的量子布谷鳥數(shù)目為nj=h/(f+1),多重對(duì)象集合wr可分別記作:

w0={v1,v2,…,vn0},

w1={vn0+1,vn0+2,…,vn0+n1},

wf={vn0+n1+…+nf-1+1,vn0+n1+…+nf-1+2,…,

5) 膜r的規(guī)則Rr(0≤r≤f)包含膜內(nèi)種群的進(jìn)化規(guī)則和通信規(guī)則.

(16)

(17)

非支配精英解集主要用于多目標(biāo)優(yōu)化問題的求解中.量子位置更新時(shí)使用的表層膜中全局最優(yōu)位置要從非支配精英解集合中按解等級(jí)和擁擠度排序的前50%的解中隨機(jī)選擇.非支配排序過程見文獻(xiàn)[10].對(duì)于某非支配等級(jí)中的多個(gè)解進(jìn)行擁擠度排序,擁擠度表示為某解z相鄰兩個(gè)解的目標(biāo)函數(shù)值除以最大目標(biāo)函數(shù)和最小目標(biāo)函數(shù)的差值.某個(gè)解的所有目標(biāo)函數(shù)所對(duì)應(yīng)的擁擠度的和為此解的最終擁擠度,公式為

(18)

據(jù)此可知,通過向非支配解等級(jí)排序?yàn)?且擁擠度較大的位置進(jìn)化可保證得到均勻的Pareto前端解集.

最后,MQCSA算法使用如下公式對(duì)量子比特進(jìn)行量子測(cè)量:

(19)

2基于MQCSA的碼分頻譜資源分配方案

2.1雙通道網(wǎng)絡(luò)簇間碼分頻譜資源分配模型

假設(shè)網(wǎng)絡(luò)由N個(gè)全連通子簇組成,所有子簇在地理位置上均勻分布,相鄰子簇之間不發(fā)生重疊.每個(gè)子簇由1條控制通道和多條數(shù)據(jù)通道組成,且所有子簇使用相同控制通道.假設(shè)網(wǎng)絡(luò)使用同步非正交組網(wǎng)方式,因此需要考慮簇內(nèi)數(shù)據(jù)通道間友鄰干擾和鄰簇間數(shù)據(jù)通道友鄰干擾問題.為便于分析作如下假設(shè): 1) 發(fā)射功率等參數(shù)相同； 2) 相鄰子簇不重疊； 3) 鄰簇的數(shù)據(jù)通道會(huì)產(chǎn)生友鄰干擾.借鑒認(rèn)知無(wú)線電網(wǎng)絡(luò)頻譜規(guī)劃思想[20],雙通道網(wǎng)絡(luò)簇間碼分頻譜資源分配模型包括子簇位置分布矩陣D、簇內(nèi)可用序列矩陣L、業(yè)務(wù)需求矩陣RT、干擾矩陣C、無(wú)干擾分配矩陣A、效益矩陣B.

子簇位置分布矩陣D指子簇相鄰關(guān)系,表示如下:

(20)

當(dāng)dn,k=1時(shí),表示子簇n和k相鄰；當(dāng)dn,k=0時(shí),表示子簇n和k不相鄰；當(dāng)n=k時(shí),設(shè)dn,k=0.設(shè)子簇位置分布在單位分配周期內(nèi)不發(fā)生變化.

簇內(nèi)可用序列矩陣L表示子簇在某分配周期內(nèi)序列使用情況.通過使用1或0表示某序列m對(duì)于子簇m為可用或不可用,因此序列集的空閑情況用簇內(nèi)可用序列矩陣L加以表示:

(21)

式(21)中,Mintra=M-Mmax,inter表示簇內(nèi)數(shù)據(jù)通道最多可用序列數(shù)目,設(shè)序列集為{S1,S2,…,SMintra},M指雙通道網(wǎng)絡(luò)使用的序列集數(shù)目,Mmax,inter指全網(wǎng)可允許的最大簇間數(shù)據(jù)通道數(shù)目.當(dāng)ln,m=1表示子簇n可以使用序列m,ln,m=0表示子簇n不能使用序列m.

業(yè)務(wù)需求矩陣RT由雙通道網(wǎng)絡(luò)中每個(gè)子簇在某分配周期內(nèi)需要建立的數(shù)據(jù)通道數(shù)目構(gòu)成.數(shù)據(jù)通道類型分為簇內(nèi)數(shù)據(jù)和簇間數(shù)據(jù),某子簇需要占用的可用序列數(shù)目取決于將要建立的簇內(nèi)數(shù)據(jù)通道數(shù)目和簇間數(shù)據(jù)通道數(shù)目.設(shè)某分配周期內(nèi)各子簇的數(shù)據(jù)通道數(shù)目保持不變,業(yè)務(wù)需求矩陣為

(22)

式中:rn表示指子簇n(1≤n≤N)的數(shù)據(jù)通道數(shù)目,其中rn,1表示簇內(nèi)數(shù)據(jù)通道，rn,2表示簇間數(shù)據(jù)通道，N為子簇?cái)?shù)目；Maxintra指不考慮簇間干擾環(huán)境下簇內(nèi)可允許的最大簇內(nèi)數(shù)據(jù)通道數(shù)目；Maxinter表示簇內(nèi)可允許的最大簇間數(shù)據(jù)通道數(shù)目．

干擾矩陣C表示子簇使用某序列的干擾情況,矩陣表達(dá)式為

(23)

式中,cn,k,m=1表示子簇n和k(1≤n,k≤N)同時(shí)使用序列m時(shí)會(huì)產(chǎn)生干擾,相反cn,k,m=0表示不會(huì)產(chǎn)生干擾.當(dāng)n=k時(shí),有cn,k,m=1-ln,m,并且矩陣元素滿足cn,k,m≤ln,m×lk,m,即只有序列m對(duì)子簇n和k均可用時(shí),才可能會(huì)產(chǎn)生干擾.

無(wú)干擾分配矩陣A表示子簇的可用序列,表示為

(24)

式中,an,m=1表示序列m分配給子簇n,an,m=0表示序列m沒有分配給子簇n.矩陣A必須滿足如下的約束條件:

an,m×ak,m=0,ifcn,k,m=1.

(25)

由上述定義可知,滿足約束條件的無(wú)干擾分配矩陣A不止一個(gè),用Λ(D,L,C)表示滿足條件的分配矩陣A的集合.雙通道網(wǎng)絡(luò)碼分頻譜資源分配任務(wù)就是從所有可行的分配方案中找到使某種網(wǎng)絡(luò)效益函數(shù)Fi(A)達(dá)到最優(yōu)的分配矩陣A.

不同的網(wǎng)絡(luò)效益函數(shù)的求解就是指求解不同目標(biāo)的優(yōu)化函數(shù)問題,設(shè)A*為滿足要求的最優(yōu)解,則有

(26)

擬采用如下兩種網(wǎng)絡(luò)效益函數(shù):

1) 最大和碼分頻譜資源效益(Max-Sum-Profit,MSP)FMSP(A),定義為

(27)

最佳無(wú)干擾分配矩陣A*指FMSP(A)的最大值求解,有

(28)

2) 最小供需誤差函數(shù)(Min-Supply-Require Error, MSRE)FMSRE(A).

雙通道網(wǎng)絡(luò)使用同步非正交組網(wǎng)方式,鄰簇間數(shù)據(jù)通道存在頻點(diǎn)碰撞干擾,通過最小供需誤差函數(shù)FMSRE(A)表征每個(gè)子簇預(yù)分配的碼分頻譜資源和考慮簇間友鄰干擾條件下的簇內(nèi)理想碼分頻譜資源分配數(shù)目之間的匹配程度.

設(shè)效益矩陣為B,兩者越是匹配,說(shuō)明碼分頻譜資源利用程度越高,分配越公平.B表示為B={b1,b2,…,bn},且n∈(1,N).bn表達(dá)式如下:

(29)

式中,Nn指考慮鄰簇干擾條件下子簇n的最佳碼分頻譜資源分配數(shù)目,表達(dá)式為

Nn=Nnointerf-Maxinter-Snei-Sexchnl.

(30)

式中:Nnointerf表示無(wú)干擾時(shí)子簇最多可同時(shí)存在的數(shù)據(jù)通道數(shù)目；簇間Sexchnl指子簇n和鄰簇現(xiàn)已存在的數(shù)據(jù)通道數(shù)目之和；Snei指矩陣A中鄰簇預(yù)分配的碼分頻譜資源數(shù)目和,

(31)

式中,Nnei為子簇n的鄰簇?cái)?shù)目.由

(32)

可知,最佳無(wú)干擾分配矩陣A*指FMSRE(A)的最小值求解,有

(33)

2.2基于MQCSA的碼分頻譜資源分配方法

1) 根據(jù)系統(tǒng)參數(shù)初始化D、L、RT和C.確定優(yōu)化問題最優(yōu)解維數(shù)為

(34)

優(yōu)化問題的解矢量Vq維數(shù)是Dim,由L中值為1的元素按n和m遞增的方式排列,維數(shù)的值等于L中值為1元素的數(shù)目.

2) 初始化量子布谷鳥群,設(shè)有h只量子布谷鳥,初始化量子布谷鳥的量子窩量子位置,并通過測(cè)量得到二進(jìn)制測(cè)量位置.采用膜結(jié)構(gòu)為[0[1]1[2]2]0的膜系統(tǒng),基礎(chǔ)膜1以最大和碼分頻譜資源效益函數(shù)FMSP(·)為單目標(biāo)函數(shù)進(jìn)行量子窩位置更新,基礎(chǔ)膜2以最小供需誤差函數(shù)FMSRE(·)為單目標(biāo)函數(shù)進(jìn)行量子窩位置更新,通過信息傳遞表層膜0實(shí)現(xiàn)兼顧資源利用效率和分配公平性的多目標(biāo)優(yōu)化.然后將種群平均分配到3個(gè)膜中,并對(duì)所有的量子窩位置初始化.

3) 對(duì)種群的量子窩的位置進(jìn)行無(wú)干擾約束處理.首先,通過子簇位置分布矩陣D確定干擾矩陣C.然后將量子窩的測(cè)量位置xi中的元素一一映射到分配矩陣A中,然后利用干擾矩陣C檢查A的干擾情況,對(duì)所有m(1≤m≤Mintra),尋找滿足cn,k,m=1的n和k,再檢查A中的第m列第n和k項(xiàng)的元素是否均為1.如果是,則隨機(jī)置其中一個(gè)為0,并對(duì)相應(yīng)的測(cè)量位置也進(jìn)行調(diào)整,使其為資源分配的可行解.

5) 使用不同的方式更新基礎(chǔ)膜和表層膜中量子窩的全局最優(yōu)位置,并通過量子測(cè)量獲得測(cè)量位置.

6) 使用步驟3)調(diào)整每個(gè)量子窩的新位置為可行解,并計(jì)算相應(yīng)的適應(yīng)度值.更新基礎(chǔ)膜中的局部最優(yōu)位置和全局最優(yōu)位置以及表層膜的單目標(biāo)最優(yōu)解集.并將表層膜中的新解放入非支配精英解集合中.

8) 對(duì)表層膜內(nèi)生成的新解和非支配精英解集進(jìn)行非支配解等級(jí)排序和擁擠度計(jì)算,選擇最優(yōu)秀的部分解作為新的非支配精英解集.

9) 如果迭代次數(shù)未終止,則迭代次數(shù)加1,跳到步驟5)；否則,將非支配精英解集中的非支配解等級(jí)為1的解作為最終Pareto前端解集輸出,并把所有基礎(chǔ)膜至今搜索到的各單目標(biāo)最優(yōu)解傳遞到表層膜中的單目標(biāo)最優(yōu)解集中,再?gòu)谋韺幽ぶ休敵龈鲉文繕?biāo)最優(yōu)解,算法結(jié)束.

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

本節(jié)使用MATLAB仿真所提方法,其中碼分頻譜資源分配模型的主要參數(shù)設(shè)置如下:全連通子簇?cái)?shù)目N=10,碼分頻譜資源序列數(shù)目M和矩陣D、L、RT需提前設(shè)定,詳見后文.采用敏感圖著色法CSGC、QGA、QPSO和MQABCO作為對(duì)照優(yōu)化算法,種群數(shù)目均設(shè)置為20,其他具體參數(shù)設(shè)置詳見文獻(xiàn)[7-10].

MQCSA主要參數(shù)設(shè)置如下:種群總數(shù)目h=60,所有膜內(nèi)包含的種群數(shù)目相同；固定搜索步長(zhǎng)a0=0.01,影響因子e1=0.02.非支配精英解集的解數(shù)目he是當(dāng)前迭代過程中非支配解等級(jí)1的解數(shù)目的0.5倍.所有優(yōu)化算法的迭代過程均為1 000次,其中MQCSA的膜間信息交流間隔為50.

3.1Pareto輸出多目標(biāo)優(yōu)化解集實(shí)驗(yàn)

分別設(shè)雙通道網(wǎng)絡(luò)可用的序列數(shù)目M為256和128,由MQCSA表層膜輸出Pareto前端解集,仿真結(jié)果如圖1和2所示.因?yàn)閷?duì)照優(yōu)化算法中只能求解單目標(biāo)優(yōu)化問題,故QPSO-MSP和CSGC-MSP是對(duì)MSP求單目標(biāo)最優(yōu)解；而針對(duì)資源分配公平性,QPSO-MSRE和CSGC-MSRE是對(duì)MSRE求單目標(biāo)最優(yōu)解.由圖1可知,Pareto前端解集中的最優(yōu)解的MSP和MSRE函數(shù)值分別為250.2和5.142 2,此解能夠同時(shí)支配QPSO、CSGC和MQABCO的MSP和MSRE函數(shù)值,但并不能完全支配Pareto前端解集中的其他解.

圖1　N=10,M=256時(shí),MSP和MSRE仿真結(jié)果

圖2　N=10,M=128時(shí),MSP和MSRE的仿真結(jié)果

由圖2可知,Pareto前端解集中的最優(yōu)解的MSP和MSRE函數(shù)值分別為120.9和0.150 6,此解能夠完全支配QPSO、CSGC、MQABCO以及Pareto中的其他解,為MQCSA的非支配解.此外,MQABCO的多目標(biāo)解均被MQCSA支配,故MQCSA更優(yōu).由圖1和2可知,當(dāng)碼分頻譜資源數(shù)目減少時(shí),同樣網(wǎng)絡(luò)規(guī)模條件下,每個(gè)子簇可用的序

列數(shù)目減小,造成最大和碼分頻譜資源效益下降.因此可知,MQCSA在針對(duì)多目標(biāo)優(yōu)化問題的Pareto前端解集中,不僅存在優(yōu)于其他單目標(biāo)優(yōu)化算法的解,而且能夠兼顧考慮網(wǎng)絡(luò)碼分頻譜資源分配的資源利用效率和用戶公平性.

表1給出了當(dāng)碼分頻譜資源數(shù)目M=256時(shí)的一種雙通道網(wǎng)絡(luò)的最佳碼分分配方案.鄰簇ID可知每個(gè)子簇周圍的鄰簇情況,已用序列ID可知在分配前子簇中正在使用的序列數(shù)目,業(yè)務(wù)需求提供在此分配周期內(nèi)需要建立的數(shù)據(jù)通道數(shù)目,分配方案是在考慮簇間干擾情況下,使用MQCSA得到的能夠任意使用的序列情況.據(jù)先前研究工作可知,在不考慮鄰簇?cái)?shù)據(jù)通道友鄰干擾的條件下,子簇中最多可同時(shí)存在的數(shù)據(jù)通道數(shù)目為30.以子簇5為例,其周圍有5個(gè)鄰簇,盡管該子簇內(nèi)沒有正在使用的數(shù)據(jù)通道,且需要在此分配周期內(nèi)建立8條數(shù)據(jù)通道,但考慮到其他子簇的數(shù)據(jù)通道使用數(shù)目很大,本方案只提供了序列57供使用.盡管對(duì)子簇5而言,有很高的業(yè)務(wù)阻塞概率,但全網(wǎng)卻能獲得最優(yōu)的最大和碼分頻譜資源效益和最小供需誤差值.

3.2單目標(biāo)最優(yōu)解集實(shí)驗(yàn)

針對(duì)MQCSA的單目標(biāo)最優(yōu)解集仿真,采用100次仿真結(jié)果的平均值.設(shè)雙通道網(wǎng)絡(luò)的子簇?cái)?shù)目和序列集數(shù)目仍為10和256,則最大和碼分頻譜資源分配效益和最小供需誤差的平均值與迭代次數(shù)關(guān)系曲線分別如圖3和圖4所示.從圖3和4可看出,與QGA、QPSO、MQABCO、CSGC相比,MQCSA在單目標(biāo)優(yōu)化問題求解過程中,具有更快的收斂速度和優(yōu)化性能,這是因?yàn)镸QCSA同時(shí)具有膜結(jié)構(gòu)的并行處理、膜間搜索信息共享特點(diǎn)以及CSA的父代子代擇優(yōu)保留和非線性空間搜索機(jī)制.

表1　N=10, M=256時(shí)Pareto輸出的最佳無(wú)干擾分配矩陣A實(shí)驗(yàn)結(jié)果

圖3　單目標(biāo)最優(yōu)解集的網(wǎng)絡(luò)效益MSP VS迭代次數(shù)

圖4　單目標(biāo)最優(yōu)解集的網(wǎng)絡(luò)效益MSRE VS迭代次數(shù)

4結(jié)論

針對(duì)無(wú)線雙通道Ad Hoc網(wǎng)絡(luò)的簇間碼分頻譜資源分配多目標(biāo)優(yōu)化問題,本文提出MQCSA算法,該算法在標(biāo)準(zhǔn)布谷鳥算法基礎(chǔ)上,引入具有并行處理和膜間搜索信息共享的膜結(jié)構(gòu),并使用量子系統(tǒng)將優(yōu)化問題離散化,通過量子旋轉(zhuǎn)門和量子Hadamard門等操作對(duì)量子鳥窩的量子位置演化,結(jié)合非支配解等級(jí)排序和擁擠度計(jì)算求出多目標(biāo)Pareto前端解集.同時(shí),提出了基于MQCSA的雙通道網(wǎng)絡(luò)碼分頻譜資源分配方法,建立了碼分頻譜資源分配數(shù)學(xué)模型,并通過仿真進(jìn)行了對(duì)比分析.仿真結(jié)果表明,MQCSA可以有效求解單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化問題,具有更快的收斂性能,基于MQCSA的簇間碼分頻譜資源分配算法能夠在保證資源利用效率和簇間資源分配公平性基礎(chǔ)上給出滿足應(yīng)用需求的有效解.

參考文獻(xiàn)

[1] DU C B, QUAN H D, CUI P Z, et al. A routing protocol for utilizing code resources in tactical ad hoc networks with a single transceiver[J]. WSEAS transactions on communications, 2014, 13(1): 298-308.

[2]賈玉榮, 胡虹梅. 動(dòng)態(tài)頻譜分配的連通分支并行處理[J]. 電波科學(xué)學(xué)報(bào), 2012, 27(1): 152-156.

JIA Y R, HU H M. Parallel process of connected branch in dynamic spectrum allocation[J]. Chinese journal of radio science, 2012, 27(1): 152-156.(in Chinese)

[3] PENG C, ZHENG H, ZHAO B Y. Utilization and fairness in spectrum assignment for opportunistic spectrum access [J]. ACM mobile networks and applications, 2006, 11(4): 555-560.

[4] KIM S. Trust-based bargaining game model for cognitive radio spectrum sharing scheme[J]. IEICE transactions on communications, 2012, E95-B(12): 3925-3928.

[5] 趙陸文, 繆志敏, 周志杰, 等. 適用于認(rèn)知無(wú)線網(wǎng)絡(luò)的寬帶公共協(xié)同信道[J]. 系統(tǒng)工程與電子技術(shù), 2010, 32(5): 1078-1082.

ZHAO L W, MIAO Z M, ZHOU Z J, et al. Novel wide-band common coordinate channel for coginitive radio networks[J]. Systems engineering and electronics, 2010, 32(5): 1078-1082. (in Chinese)

[6] WANG B B, WU Y L, LIU K J R. Game theory for cognitive radio networks: an overview[J]. Computer networks, 2010, 54(14): 2537-2561.

[7] 趙知?jiǎng)? 彭振, 鄭仕鏈, 等. 基于量子遺傳算法的認(rèn)知無(wú)線電頻譜分配[J]. 物理學(xué)報(bào), 2009, 58(2): 1358-1363.

ZHAO Z J, PENG Z, ZHENG S L, et al. Cognitive radio spectrum assignment based on quantum genetic algorithm[J]. Acta physica sinica, 2009, 58(2): 1358-1363. (in Chinese)

[8] 李金金, 田雨波. 基于量子粒子群改進(jìn)算法的直線陣綜合[J]. 電波科學(xué)學(xué)報(bào), 2012, 27(2): 255-259.

LI J J, TIAN Y B. Patten synthesis of linear antenna array based on improved quantum particle swarm optimization[J]. Chinese journal of radio science, 2012, 27(2): 255-259. (in Chinese)

[9] GAO H Y, CAO J L. Non-dominated sorting quantum particle swarm optimization and its application in cognitive radio spectrum allocation[J]. Journal of Central South University, 2013, 20(7): 1878-1888.

[10]高洪元, 李晨琬. 膜量子蜂群優(yōu)化的多目標(biāo)頻譜分配[J]. 物理學(xué)報(bào), 2014, 63(12): 128802-128810.

GAO H Y, LI C W. Membrane-inspired quantum bee colony algorithm for multi-objective spectrum allocation[J]. Acta physica sinica, 2014, 63(12): 128802-128810. (in Chinese)

[11]YANG X S, DEB S. Cuckoo search via Lévy flights [C]//Proceeding of World Congress on Nature and Biologically Inspired Computing, 2012: 210-214.

[12]YANG X S, DEB S. Engineering optimization by cuckoo search [J]. International journal of mathematic modelling numerical optimization, 2010, 1(4): 330-343.

[13]GAO H Y, CAO J L, ZHAO Y N. Membrane quantum particle swarm optimization for cognitive radio spectrum allocation[J]. International journal of computer applications in technology, 2012, 43(4): 359-365.

[14]HO S L, YANG S Y, NI P H, et al. A quantum-inspired evolutionary algorithm for multi-objective design [J]. IEEE transactions on magnetics, 2013, 49(5): 1609-1612.

[15]DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II [J]. IEEE transactions on evolutionary computation, 2002, 6(2): 182-197.

[18]袁國(guó)斌, 梁濤, 倪艷. 船舶編隊(duì)電磁頻譜管理輔助決策模型研究[J]. 電波科學(xué)學(xué)報(bào), 2013, 28(4): 730-734.

YUAN G B, LIANG T, NI Y. Assistant decision model for vessel formation electromagnetic spectrum management[J]. Chinese journal of radio science, 2013, 28(4): 730-734. (in Chinese)

[19]YANG X S, DEB S. Multi-objective cuckoo search for design optimization[J]. Computers & operations research, 2013, 40(6): 1616-1624.

[20]甘小鶯, 陳時(shí)陽(yáng), 王路洋, 等. 認(rèn)知無(wú)線電中能效優(yōu)先的多用戶隨機(jī)接入方法[J]. 電波科學(xué)學(xué)報(bào), 2013, 28(4): 648-654.

GAN X Y, CHEN S Y, WANG L Y, et al. Energy efficient multi-user random access in cognitive radio[J]. Chinese journal of radio science, 2013, 28(4): 648-654. (in Chinese)

杜傳報(bào)(1987-),男,陜西人,軍械工程學(xué)院導(dǎo)航、制導(dǎo)和控制專業(yè)博士研究生,研究方向?yàn)闊o(wú)線通信網(wǎng)絡(luò)研究.

全厚德(1963-),男,遼寧人,軍械工程學(xué)院信息工程系教授,博士生導(dǎo)師,主要研究方向?yàn)樾畔⒑屯ㄐ殴こ?、通信網(wǎng)絡(luò).

唐友喜(1964-),男,河南人,電子科技大學(xué)教授,博士生導(dǎo)師,主要研究方向?yàn)闊o(wú)線通信網(wǎng)絡(luò)、MIMO等.

作者簡(jiǎn)介

中圖分類號(hào)TN925

文獻(xiàn)標(biāo)志碼A

文章編號(hào)1005-0388(2016)01-0129-09

收稿日期：2015-04-09

杜傳報(bào), 全厚德, 唐友喜, 等. 基于膜量子布谷鳥搜索的雙通道網(wǎng)絡(luò)頻譜資源分配[J]. 電波科學(xué)學(xué)報(bào),2016,31(1):129-137.DOI: 10.13443/j.cjors.2015040901

DU C B, QUAN H D, TANG Y X, et al. Frequency spectrum resource allocation based on membrane-inspired quantum cuckoo search for wireless dual-channel ad hoc network[J]. Chinese journal of radio science,2016,31(1):129-137.(in Chinese). DOI:10.13443/j.cjors.2015040901

資助項(xiàng)目: 國(guó)家自然科學(xué)基金(U1035002/L05)； 國(guó)家無(wú)線重大專項(xiàng)(2014ZX03003001-002)

聯(lián)系人： 杜傳報(bào) E-mail: leopard0306@126.com