基于自適應遺傳算法的無線網絡智能選頻技術研究

王文君

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

1 引言

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

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

2 系統模型

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

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

· 選頻的依據是以網絡中的干擾程度作為依據。產生用頻沖突的原因很多，系統互擾和自擾是其中之一。當干擾總功率比較小時，干擾對用頻的影響較小，這將大大提高選頻的自由度，提高頻譜利用率。

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

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

3 算法設計與參數控制

基于基本遺傳算法的智能優化思想，結合遺傳算法的全局搜索機制，通過對遺傳算法各遺傳要素的改進與參數的控制，實現對網絡選頻技術的數學建模，具體算法設計思路如下。

3.1 遺傳編碼的設定

采用實數編碼[6]，設置個體的長度為N，即網絡中的用頻設備數為N。個體中的每一個元素對應一個可用頻率，即存在以下映射A：

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

3.2 初始群體的設定

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

3.3 適應度函數設計

對指定地域范圍內的所有用頻設備進行電磁干擾分析。根據干擾總功率，可將適應度函數設計如下：

其中，eval為適應度值，Pi為設備i所受的干擾總功率。

3.4 交叉概率和變異概率設計

本文提出了改進的交叉概率和變異概率，是根據種群適應度值的集中程度，自適應地對整個群體的交叉概率和變異概率進行調整。按照當代種群適應度值的分布情況，交叉概率和變異概率設計如下[7]：

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

（1）選擇

采用賭盤算法[8]進行選擇操作。應該滿足的條件的數學描述為：

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

進行選擇操作M次，產生種群v1′,v2′,…,vM′。

（2）交叉

采用算術交叉[8]方法，對v1′,v2′,…,vM′進行交叉操作。產生隨機數序列r1,r2,…,rM，若ri

（3）變異

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

4 無線網絡智能選頻算法實現流程

基于以上算法設計思路，設定種群規模為M，算法實現流程如下。

（1）對于網絡中給定的N個用頻設備，在已知設備頻段或頻點中隨機產生M種選頻方案，即隨機產生一個初始種群：v1,v2,…,vM，其中個體長度為N。

（2）進行電磁干擾分析，計算每種選頻方案所對應的干擾功率。

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

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

（5）對種群v1′,v2′,…,vM′進行交叉操作。

（6）對種群v1′,v2′,…,vM′進行變異操作。

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

（8）判斷：若當前進化代數小于最大進化代數，則轉到步驟（2），并繼續進行下一次遺傳迭代；否則，算法終止，返回當前最優解，從而得到最優選頻方案。

5 仿真實驗及結果分析

5.1 收斂性

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

5.1.1 青島地區

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

圖1 青島地區最大適應度對比

5.1.2 鄭州地區

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

表1 青島地區中波通信網仿真實驗結果數據統計

表2 青島地區短波通信網仿真實驗結果數據統計

表3 青島地區超短波通信網仿真實驗結果數據統計

表4 青島地區微波接力網仿真實驗結果數據統計

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

表5 鄭州地區中波通信網仿真實驗結果數據統計

圖2 鄭州地區最大適應度對比

表6 鄭州地區短波通信網仿真實驗結果數據統計

表7 鄭州地區超短波通信網仿真實驗結果數據統計

表8 鄭州地區微波接力網仿真實驗結果數據統計

5.2 穩定性

為了分析驗證算法的穩定性，在以東經120°、北緯36°為中心的區域內隨機部署中波通信網、短波通信網、超短波通信網和微波接力網，分別采用傳統方法、貪心算法、粒子群算法和本文算法進行100次300代迭代的選頻仿真實驗，其結果如圖 3所示。

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

6 結束語

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

圖3 算法穩定性曲線對比

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王小平，曹立明.遺傳算法——理論、應用與軟件實現.西安：西安交通大學出版社，2002

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

5 陳窮.電磁兼容性工程設計手冊.北京：國防工業出版社，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 閆妍.一種新的自適應遺傳算法 （碩士學位論文）.哈爾濱工程大學,2007

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

8 玄光男,程潤偉.遺傳算法與工程優化.北京：清華大學出版社，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