王文君

（中國(guó)電波傳播研究所 青島 266107）

1 引言

隨著無線電業(yè)務(wù)的迅速發(fā)展與普及，各類無線電設(shè)備的數(shù)量與日俱增，電磁環(huán)境日益復(fù)雜，頻率擁擠問題受到廣泛關(guān)注。造成這種用頻緊張的狀況主要有兩個(gè)原因：一是頻率資源少；二是頻率使用效率低。因此，必須考慮將現(xiàn)有的頻率資源進(jìn)行有效的利用和科學(xué)的管理，智能選頻技術(shù)正是優(yōu)化頻率資源分配、有效利用頻率資源的一種有效手段。通常解決無線網(wǎng)絡(luò)選頻問題的傳統(tǒng)方法主要有順序選頻法[1]和窮舉搜索法[2]。對(duì)于中小規(guī)模無線電網(wǎng)絡(luò)，一般采用順序選頻法根據(jù)設(shè)備頻段對(duì)鏈路進(jìn)行逐一選頻；而對(duì)于大規(guī)模無線電網(wǎng)絡(luò)，則采用窮舉搜索法進(jìn)行選頻。這種傳統(tǒng)的確定性算法在尋找最優(yōu)解時(shí)會(huì)耗費(fèi)大量的計(jì)算時(shí)間，而且選頻結(jié)果對(duì)于單設(shè)備或中小網(wǎng)絡(luò)也適用，但對(duì)于大規(guī)模用頻網(wǎng)絡(luò)還無法實(shí)現(xiàn)頻率的整體協(xié)同使用，仍然存在著用頻沖突的問題。鑒于此，本文提出一種全新的智能選頻算法，結(jié)合全局搜索的智能優(yōu)化思想，考慮對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行整體配置頻率優(yōu)化，根據(jù)當(dāng)時(shí)當(dāng)?shù)仉姶怒h(huán)境的復(fù)雜程度和實(shí)時(shí)網(wǎng)絡(luò)用頻狀態(tài)自適應(yīng)地選擇設(shè)備使用頻率。

遺傳算法[3,4]（genetic algorithm，GA）作為一種智能優(yōu)化算法，具有內(nèi)在的隱并行性和良好的隨機(jī)搜索能力，近年來已被廣泛應(yīng)用于系統(tǒng)優(yōu)化工程。基本遺傳算法存在整體尋優(yōu)能力差、局部搜索能力低的不足，由于在選擇過程中種群適應(yīng)度過于集中，在進(jìn)行遺傳迭代過程中容易發(fā)生過早收斂的現(xiàn)象。本文提出的基于自適應(yīng)遺傳算法的智能選頻技術(shù)，主要是以遺傳算法為基礎(chǔ)，針對(duì)基本遺傳算法的不足，對(duì)遺傳編碼、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作的設(shè)計(jì)和算法參數(shù)控制進(jìn)行改進(jìn)，從而提高了遺傳迭代的效率，較好地避免了在搜索過程中出現(xiàn)的過早收斂現(xiàn)象，明顯改善了計(jì)算穩(wěn)定性，使選頻結(jié)果的質(zhì)量大大提高，在解決大規(guī)模無線電網(wǎng)絡(luò)選頻問題時(shí)有較大的優(yōu)勢(shì)。

2 系統(tǒng)模型

所謂無線網(wǎng)絡(luò)選頻，是指在無線電網(wǎng)絡(luò)中，給網(wǎng)絡(luò)中的所有用頻設(shè)備指定使用頻率，使其在規(guī)定的條件下正常工作。選頻的最終目的是減少用頻設(shè)備之間的互擾和自擾，規(guī)避網(wǎng)絡(luò)中的用頻沖突現(xiàn)象，以最大限度地提高頻率使用效率。在選頻過程中一般遵循以下原則。

·對(duì)選頻網(wǎng)絡(luò)進(jìn)行詳細(xì)的電磁兼容性（EMC）分析[5]。進(jìn)行電磁兼容性分析需要大量的地理高程數(shù)據(jù)和收發(fā)設(shè)備特性參數(shù)，其計(jì)算量是非常大的。很多人都想避開詳細(xì)的EMC分析，于是做了理想的假定或以簡(jiǎn)單保守的算法進(jìn)行代替，而建立在此基礎(chǔ)上的選頻模型很多時(shí)候并不是相對(duì)最優(yōu)的。因此，既要避免用頻沖突，又要提高頻率使用效率，必須進(jìn)行EMC分析，通過精確的電波傳播預(yù)測(cè)模型和高效的數(shù)值計(jì)算方法來使其實(shí)用化。

· 選頻的依據(jù)是以網(wǎng)絡(luò)中的干擾程度作為依據(jù)。產(chǎn)生用頻沖突的原因很多，系統(tǒng)互擾和自擾是其中之一。當(dāng)干擾總功率比較小時(shí)，干擾對(duì)用頻的影響較小，這將大大提高選頻的自由度，提高頻譜利用率。

在選頻過程中，通常用干擾余量（IM）來表示干擾程度，干擾余量可表示為[5]：

其中，PT(fE)為發(fā)射機(jī)功率（dBm），GT(fE,t,d,p)為接收天線方向的發(fā)射天線增益（dB），L(fE,t,d,p)為收發(fā)天線間的傳播路徑損耗（dB），GR(fE,t,d,p)為發(fā)射天線方向的接收天線增益（dB），PR(fE)為接收機(jī)敏感度門限（dBm），CF(BT,BR,Δf)為校正系數(shù)（dB）。

3 算法設(shè)計(jì)與參數(shù)控制

基于基本遺傳算法的智能優(yōu)化思想，結(jié)合遺傳算法的全局搜索機(jī)制，通過對(duì)遺傳算法各遺傳要素的改進(jìn)與參數(shù)的控制，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)選頻技術(shù)的數(shù)學(xué)建模，具體算法設(shè)計(jì)思路如下。

3.1 遺傳編碼的設(shè)定

采用實(shí)數(shù)編碼[6]，設(shè)置個(gè)體的長(zhǎng)度為N，即網(wǎng)絡(luò)中的用頻設(shè)備數(shù)為N。個(gè)體中的每一個(gè)元素對(duì)應(yīng)一個(gè)可用頻率，即存在以下映射A：

其中，fi(i=1,2,…,N)代表設(shè)備所選的頻率。

3.2 初始群體的設(shè)定

候選群體中每個(gè)個(gè)體對(duì)應(yīng)一種選頻方案的編碼表示（即映射A），每一次新的選頻方案的產(chǎn)生則代表一個(gè)新個(gè)體的生成。初始群體是隨機(jī)產(chǎn)生的，即對(duì)于每一個(gè)個(gè)體，從可用頻率集合中為每個(gè)用頻設(shè)備隨機(jī)選擇一個(gè)頻率。假設(shè)種群規(guī)模為M，則初始種群如下：

3.3 適應(yīng)度函數(shù)設(shè)計(jì)

對(duì)指定地域范圍內(nèi)的所有用頻設(shè)備進(jìn)行電磁干擾分析。根據(jù)干擾總功率，可將適應(yīng)度函數(shù)設(shè)計(jì)如下：

其中，eval為適應(yīng)度值，Pi為設(shè)備i所受的干擾總功率。

3.4 交叉概率和變異概率設(shè)計(jì)

本文提出了改進(jìn)的交叉概率和變異概率，是根據(jù)種群適應(yīng)度值的集中程度，自適應(yīng)地對(duì)整個(gè)群體的交叉概率和變異概率進(jìn)行調(diào)整。按照當(dāng)代種群適應(yīng)度值的分布情況，交叉概率和變異概率設(shè)計(jì)如下[7]：

其中，pc為交叉概率，pm為變異概率，fmax為種群中最大的適應(yīng)度值，favg為每代種群中的平均適應(yīng)度值，fmin為種群中最小的適應(yīng)度值，f′為待交叉?zhèn)€體中較大的適應(yīng)度值，f為待變異個(gè)體的適應(yīng)度值，kc1>kc2>kc3，km1>km2>km3且為(0,1)的隨機(jī)值。

（1）選擇

采用賭盤算法[8]進(jìn)行選擇操作。應(yīng)該滿足的條件的數(shù)學(xué)描述為：

其中，Pi為設(shè)備所受的干擾總功率，Li為設(shè)備i的接收機(jī)干擾門限，i=1,2,…,N。

進(jìn)行選擇操作M次，產(chǎn)生種群v1′,v2′,…,vM′。

（2）交叉

采用算術(shù)交叉[8]方法，對(duì)v1′,v2′,…,vM′進(jìn)行交叉操作。產(chǎn)生隨機(jī)數(shù)序列r1,r2,…,rM，若ri

（3）變異

采用非均勻變異[8]，根據(jù)變異概率對(duì)該種群進(jìn)行變異操作。假設(shè)個(gè)體v=[f1,…,fk，…，fN]中的基因fk被選中進(jìn)行變異，則產(chǎn)生的后代為v′=[f1,…,fk′，…，fN]。

4 無線網(wǎng)絡(luò)智能選頻算法實(shí)現(xiàn)流程

基于以上算法設(shè)計(jì)思路，設(shè)定種群規(guī)模為M，算法實(shí)現(xiàn)流程如下。

（1）對(duì)于網(wǎng)絡(luò)中給定的N個(gè)用頻設(shè)備，在已知設(shè)備頻段或頻點(diǎn)中隨機(jī)產(chǎn)生M種選頻方案，即隨機(jī)產(chǎn)生一個(gè)初始種群：v1,v2,…,vM，其中個(gè)體長(zhǎng)度為N。

（2）進(jìn)行電磁干擾分析，計(jì)算每種選頻方案所對(duì)應(yīng)的干擾功率。

（3）根據(jù)干擾功率計(jì)算群體中的個(gè)體適應(yīng)度值，并計(jì)算選擇概率和累積概率。

（4）對(duì)初始種群進(jìn)行選擇操作M次，生成種群v1′,v2′,…,vM′。

（5）對(duì)種群v1′,v2′,…,vM′進(jìn)行交叉操作。

（6）對(duì)種群v1′,v2′,…,vM′進(jìn)行變異操作。

（7）在步驟（5）和步驟（6）后的子代和父代中選擇適應(yīng)度最大的M個(gè)個(gè)體組成新的種群，并在新種群中用最優(yōu)個(gè)體替換最差個(gè)體。

（8）判斷：若當(dāng)前進(jìn)化代數(shù)小于最大進(jìn)化代數(shù)，則轉(zhuǎn)到步驟（2），并繼續(xù)進(jìn)行下一次遺傳迭代；否則，算法終止，返回當(dāng)前最優(yōu)解，從而得到最優(yōu)選頻方案。

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

5.1 收斂性

為了分析驗(yàn)證算法的收斂性，在山東青島和河南鄭州兩個(gè)地區(qū)分別采用傳統(tǒng)選頻算法（以下簡(jiǎn)稱傳統(tǒng)方法）、粒子群優(yōu)化（particle swarm optimization，PSO）算法[9]（以下簡(jiǎn)稱粒子群算法）、貪心算法[10]和基于自適應(yīng)遺傳算法的智能選頻算法（以下簡(jiǎn)稱本文算法）進(jìn)行無線通信網(wǎng)絡(luò)選頻仿真實(shí)驗(yàn)。

5.1.1 青島地區(qū)

在青島地區(qū)分別部署中波通信網(wǎng)、短波通信網(wǎng)、超短波通信網(wǎng)和微波接力網(wǎng)（其中各含50個(gè)臺(tái)站），采用傳統(tǒng)方法、貪心算法、粒子群算法和本文算法分別對(duì)這4種網(wǎng)絡(luò)進(jìn)行選頻仿真實(shí)驗(yàn)，結(jié)果如圖1所示。對(duì)于中波通信網(wǎng)，傳統(tǒng)方法在120代達(dá)到收斂，貪心算法在110代達(dá)到收斂，粒子群算法在140代達(dá)到收斂，本文算法在160代達(dá)到收斂；對(duì)于短波通信網(wǎng)，傳統(tǒng)方法在140代達(dá)到收斂，貪心算法在120代達(dá)到收斂，粒子群算法在150代達(dá)到收斂，本文算法在170代達(dá)到收斂；對(duì)于超短波通信網(wǎng)，傳統(tǒng)方法在150代達(dá)到收斂，貪心算法在130代達(dá)到收斂，粒子群算法在160代達(dá)到收斂，本文算法在180代達(dá)到收斂；對(duì)于微波接力網(wǎng)，傳統(tǒng)方法在160代達(dá)到收斂，貪心算法在150代達(dá)到收斂，粒子群算法在170代達(dá)到收斂，本文算法在190代達(dá)到收斂。結(jié)果數(shù)據(jù)統(tǒng)計(jì)見表1～表4。

圖1 青島地區(qū)最大適應(yīng)度對(duì)比

5.1.2 鄭州地區(qū)

在鄭州地區(qū)分別部署中波通信網(wǎng)、短波通信網(wǎng)、超短波通信網(wǎng)和微波接力網(wǎng) （其中各含50個(gè)臺(tái)站），采用傳統(tǒng)方法、貪心算法、粒子群算法和本文算法分別對(duì)這4種網(wǎng)絡(luò)進(jìn)行選頻仿真實(shí)驗(yàn)，結(jié)果如圖2所示。對(duì)于中波通信網(wǎng)，傳統(tǒng)方法在150代達(dá)到收斂，貪心算法在130代達(dá)到收斂，粒子群算法在170代達(dá)到收斂，本文算法在190代達(dá)到收斂；對(duì)于短波通信網(wǎng)，傳統(tǒng)方法在 160代達(dá)到收斂，貪心算法在150代達(dá)到收斂，粒子群算法在180代達(dá)到收斂，本文算法在200代達(dá)到收斂；對(duì)于超短波通信網(wǎng)，傳統(tǒng)方法在180代達(dá)到收斂，貪心算法在160代達(dá)到收斂，粒子群算法在210代達(dá)到收斂，本文算法在220代達(dá)到收斂；對(duì)于微波接力網(wǎng)，傳統(tǒng)方法在200代達(dá)到收斂，貪心算法在180代達(dá)到收斂，粒子群算法在220代達(dá)到收斂，本文算法在230代達(dá)到收斂。結(jié)果數(shù)據(jù)統(tǒng)計(jì)見表5～表8。

表1 青島地區(qū)中波通信網(wǎng)仿真實(shí)驗(yàn)結(jié)果數(shù)據(jù)統(tǒng)計(jì)

表2 青島地區(qū)短波通信網(wǎng)仿真實(shí)驗(yàn)結(jié)果數(shù)據(jù)統(tǒng)計(jì)

表3 青島地區(qū)超短波通信網(wǎng)仿真實(shí)驗(yàn)結(jié)果數(shù)據(jù)統(tǒng)計(jì)

表4 青島地區(qū)微波接力網(wǎng)仿真實(shí)驗(yàn)結(jié)果數(shù)據(jù)統(tǒng)計(jì)

通過以上仿真實(shí)驗(yàn)可以看出，用傳統(tǒng)方法和貪心算法進(jìn)行選頻時(shí)，算法收斂速度較快，多數(shù)情況下只能得到局部最優(yōu)解，尋優(yōu)效率比較低；用粒子群算法進(jìn)行選頻時(shí)，尋優(yōu)效果比傳統(tǒng)算法和貪心算法好，但最終得到的選頻結(jié)果也很難達(dá)到全局最優(yōu)，在求解大規(guī)模無線網(wǎng)絡(luò)選頻問題時(shí)存在缺陷。而用本文算法進(jìn)行選頻時(shí)，算法在進(jìn)行遺傳迭代過程中最大適應(yīng)度值曲線比較平滑，收斂速度比較平穩(wěn)，最終得到的選頻結(jié)果的適應(yīng)度值也比前面3種算法高。由此可見，本文提出的基于自適應(yīng)遺傳算法的智能選頻算法有較強(qiáng)的尋優(yōu)能力，其收斂性能優(yōu)于前面3種算法。

表5 鄭州地區(qū)中波通信網(wǎng)仿真實(shí)驗(yàn)結(jié)果數(shù)據(jù)統(tǒng)計(jì)

圖2 鄭州地區(qū)最大適應(yīng)度對(duì)比

表6 鄭州地區(qū)短波通信網(wǎng)仿真實(shí)驗(yàn)結(jié)果數(shù)據(jù)統(tǒng)計(jì)

表7 鄭州地區(qū)超短波通信網(wǎng)仿真實(shí)驗(yàn)結(jié)果數(shù)據(jù)統(tǒng)計(jì)

表8 鄭州地區(qū)微波接力網(wǎng)仿真實(shí)驗(yàn)結(jié)果數(shù)據(jù)統(tǒng)計(jì)

5.2 穩(wěn)定性

為了分析驗(yàn)證算法的穩(wěn)定性，在以東經(jīng)120°、北緯36°為中心的區(qū)域內(nèi)隨機(jī)部署中波通信網(wǎng)、短波通信網(wǎng)、超短波通信網(wǎng)和微波接力網(wǎng)，分別采用傳統(tǒng)方法、貪心算法、粒子群算法和本文算法進(jìn)行100次300代迭代的選頻仿真實(shí)驗(yàn)，其結(jié)果如圖 3所示。

不難看出，用傳統(tǒng)方法和貪心算法進(jìn)行選頻時(shí)，每次試驗(yàn)得到的最大適應(yīng)度值都比較低，最優(yōu)解適應(yīng)度曲線波動(dòng)較大，穩(wěn)定性較差；用粒子群算法進(jìn)行選頻時(shí)，雖然最大適應(yīng)度值比傳統(tǒng)方法和貪心算法高，在穩(wěn)定性上也有所增強(qiáng)，但還是沒有達(dá)到理想要求；相比之下，本文算法得到的最優(yōu)解適應(yīng)度曲線比較平穩(wěn)，而且最大適應(yīng)度值基本保持在一個(gè)很高的水平，可以滿足目前無線網(wǎng)絡(luò)選頻工程計(jì)算的要求。因此，從算法穩(wěn)定性的角度看，本文提出的基于自適應(yīng)遺傳算法的智能選頻算法優(yōu)于前面3種算法。

6 結(jié)束語

無線網(wǎng)絡(luò)選頻是電磁頻譜管理領(lǐng)域中非常重要且困難的研究課題，前人在此項(xiàng)研究上也做出了很多努力，取得了一些可喜的成果。在此基礎(chǔ)上，本文從智能優(yōu)化的角度提出了一種新的智能選頻技術(shù)，結(jié)合遺傳算法的全局搜索機(jī)制，通過對(duì)遺傳操作的改進(jìn)和搜索過程的控制來尋求最優(yōu)選頻結(jié)果。仿真結(jié)果證明，該技術(shù)不僅能夠滿足大規(guī)模無線電網(wǎng)絡(luò)選頻的要求，而且尋優(yōu)速度快、精度高，有較強(qiáng)的通用性和穩(wěn)定性，可應(yīng)用于目前的頻譜管理工程計(jì)算。

圖3 算法穩(wěn)定性曲線對(duì)比

1 Maniezzo V,Carbonaro A.An ants heuristic for the frequency assignment problem.Future Generation Computer Systems,2000,16(8):927～935

2 ProsserP.Hybrid algorithm forthe constraintsatisfaction problem.Computational Intelligence,1993,9(3):268～297

3 Holland J H.Adaptation in Nature and Artificial System:an Introductory Analysis with Application to Biology,Control,and Artificial Intelligence.MI:The University of Michigan Press,1975

4王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn).西安：西安交通大學(xué)出版社，2002

Wang X P,Cao L M.Genetic Algorithm——The Theory,Application and Software Implementation.Xi’an:Xi’an Jiaotong University Press,2002

5 陳窮.電磁兼容性工程設(shè)計(jì)手冊(cè).北京：國(guó)防工業(yè)出版社，1993

Chen Q.Electromagnetic Compatibility Engineering Design Manual.Beijing:National Defense Industry Press,1993

6 Alabau M,IdoumgharL,SchottR.New hybrid genetic algorithms for the frequency assignment problem. IEEE Transactions on Broadcasting,2002,48(3):27～34

7 閆妍.一種新的自適應(yīng)遺傳算法 （碩士學(xué)位論文）.哈爾濱工程大學(xué),2007

Yan Y.A new adaptive genetic algorithm (master dissertation).Harbin Engineering University,2007

8 玄光男,程潤(rùn)偉.遺傳算法與工程優(yōu)化.北京：清華大學(xué)出版社，2004

Xuan G N,Cheng R W.Genetic Algorithms and Engineering Optimization.Beijing:Tsinghua University Press,2004

9 Kennedy J,Eberhart R.Particle swarm optimization.Proceedings of the 4th IEEE International Conference on Neural Networks,Dallas,Texas,USA,1995:1942～1948

10 Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms(the Second Edition).Cambrideg:The MIT Press,2001