王文君

（中國電波傳播研究所 青島 266107）

1 引言

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

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

2 系統(tǒng)模型

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

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

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

在選頻過程中，通常用干擾余量（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è)計與參數(shù)控制

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

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

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

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

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

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

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

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

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

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

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

其中，pc為交叉概率，pm為變異概率，fmax為種群中最大的適應(yīng)度值，favg為每代種群中的平均適應(yīng)度值，fmin為種群中最小的適應(yīng)度值，f′為待交叉?zhèn)€體中較大的適應(yīng)度值，f為待變異個體的適應(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]方法，對v1′,v2′,…,vM′進(jìn)行交叉操作。產(chǎn)生隨機(jī)數(shù)序列r1,r2,…,rM，若ri

（3）變異

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

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

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

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

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

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

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

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

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

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

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

5 仿真實驗及結(jié)果分析

5.1 收斂性

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

5.1.1 青島地區(qū)

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

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

5.1.2 鄭州地區(qū)

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

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

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

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

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

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

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

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

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

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

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

5.2 穩(wě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代迭代的選頻仿真實驗，其結(jié)果如圖 3所示。

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

6 結(jié)束語

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

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

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)用與軟件實現(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è)計手冊.北京：國防工業(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 玄光男,程潤偉.遺傳算法與工程優(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