基于模擬退火算法的頻率指配算法優化

王更輝

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

?

基于模擬退火算法的頻率指配算法優化

王更輝

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

模擬退火算法是最早應用于頻率指配的智能算法之一，具有設計簡單、頻率指配合理等優點。但在某些具體頻率指配環境中，模擬退火算法存在運算時間較長的缺點。通過分析頻率指配影響算法的條件，深入剖析模擬退火算法在頻率指配中的運行機制，縮小鄰域選擇范圍、引進貪婪原則改進新解產生方式、增加升溫過程和初始解重新設置等方式，對模擬退火算法在頻率指配中的應用進行了優化，在保證符合頻率指配約束條件的情況下，提升了模擬退火算法的運算效率。

模擬退火；頻率指配；貪婪原則

0 引言

隨著現代無線通信技術的快速發展，各種新型無線通信系統不斷涌現，通信網絡結構日趨復雜，無線通信設備急劇增加，高速增長的無線頻率的需求與有限的頻率資源的矛盾變得更加突出。頻率指配作為研究頻率能夠合理規劃和有效利用的重要內容，就是為每個通信設備在規定的頻率范圍內指定一個合理的工作頻率，使得頻譜整體得以有效利用，并且各個通信設備的工作頻率不互相干擾。頻率指配算法作為頻率指配的核心，決定了頻率指配的工作效率和頻率指配結果的合理性[1]。

1 頻率指配簡介

頻率指配是優化頻率利用、提高信道容量和減少干擾的主要手段，通過頻率指配將無線電頻率指定給相應的無線電設備，使其在規定的條件下使用。當前頻率指配主要應用于無線通信網絡，其最終目的是在保證網絡中無線通信設備能夠正常通信的情況下，最大限度地提高頻率利用率[2-3]，影響頻率指配的主要因素是頻率干擾和可用頻率。

1.1 頻率干擾

頻率干擾是頻率指配考慮的重要因素，頻率干擾的類型包括：同頻干擾、互調干擾、雜散干擾和鄰道干擾。同頻干擾是指相鄰2個或多個無線設備的覆蓋重疊內，接收點場強是來自各無線設備信號場強之和，從而產生了互相干擾。互調干擾是由于不同頻率的2個或多個射頻信號在某臺無線設備經非線性作用產生了新的等于另一頻點的頻率分量而引起的干擾，一般情況下，互調干擾主要考慮二階互調干擾和三階互調干擾。雜散干擾主要是指由于無線設備中的濾波特性不好，使得一些二次和三次諧波分量在輸出時產生雜波輻射信號。鄰道干擾是指相鄰的或鄰近波道之間的干擾。其中雜波干擾和鄰道干擾主要因為無線設備的技術指標不合格引起的干擾，因此在頻率指配過程中主要考慮同頻干擾和互調干擾。

頻率指配通過頻率間隔合理利用頻率，避免無線設備間的頻率干擾。頻率間隔由工作頻率特性和無線設備的技術指標來決定，對可用頻率的利用效率產生影響。一般情況下，無線設備的技術指標確定了該設備避免頻率干擾的頻率間隔。

干擾數據模型是描述無線設備之間頻率干擾約束關系的模型[4-5]，主要以矩陣的方式進行表示。無線設備之間的干擾約束關系函數如下：

根據干擾約束關系，可以得到總的干擾數目[5]，干擾數目的目標函數如下：

當無線設備的數量確定后，干擾數目對頻率指配算法產生影響，隨著干擾數目的增大，頻率指配算法的效率迅速降低。

1.2 可用頻率

可用頻率是指無線設備在指配頻率時可以使用的頻率。為了保證所有無線設備的正常工作，需要對每類無線設備的工作頻率范圍進行劃分。并且根據電磁環境的復雜性和有意無意的電磁干擾，無線設備在頻率指配之前需要提前將一些被干擾的頻點進行剔除。

Fv=FD-Ff，

式中，Fv為頻率指配時無線設備可以使用的頻率，FD為無線設備的頻率工作范圍，Fv為頻率指配時無線設備禁止使用的頻率，包括電磁環境中被干擾的頻率、已分配給其他無線設備的頻率等。當無線設備的數量確定后，可用頻率Fv越多，頻率指配算法的效率越高。

2 基于模擬退火算法的頻率指配算法

2.1 模擬退火算法概述

模擬退火算法最早由Metropolis等人于1953年提出，1983年Kirkpatrick將它應用于組合優化問題[6-7]，Duque等人在1993年首先使用模擬退火算法解決頻率指配問題[8]。模擬退火算法是一種基于迭代求解策略的隨機搜索算法[9]，用于在一個解空間內尋找問題最優解。模擬退火算法模擬了整個物理退火過程：將固體加熱至足夠高的溫度，使固體內粒子變為隨機無序狀態；然后逐步降溫冷卻，使粒子在每個溫度下漸趨有序狀態，達到平衡；最后在常溫時，固體粒子達到穩定狀態。

模擬退火算法的核心是基于Metropolis接受準則[10]，避免模擬退火算法在搜索過程中陷入局部最優的同時趨向全局最優解，在解空間內隨機選擇最新解，再以Metropolis接受準則，判斷是否接受最新解替代當前解，最終收斂于當前最優解。

Metropolis接受準則確定如下：

式中，P為溫度tk下i狀態向j狀態轉變時接受j狀態的概率，f(i)為i狀態下的能量函數，f(j)為j狀態下的能量函數。

2.2 基于模擬退火算法頻率指配

基于模擬退火算法的頻率指配算法的主要結構如下。

2.2.1 解結構

模擬退火算法的解的結構如下：

2.2.2 評價函數

評價函數是判斷算法取得解的判定標準[11]，主要用于判定解是否滿足頻率指配要求和比較2個解的優劣程度。模擬退火算法的評價函數如下：

2.2.3 鄰域結構

在模擬退火算法中，鄰域結構是最重要的概念之一 。頻率指配中鄰域結構的定義：有當前解v0，當解空間Vl0中任意解vi有且只有一個無線設備所指配的頻率與當前解中的無線設備頻率不同，Vl0就是v0的鄰域。算法新解的產生就是在當前解的鄰域中隨機選擇，并不斷重復這個過程。

基于模擬退火算法的頻率指配算法描述如下[12]：

① 初始化算法參數。設置初始溫度T、降溫衰減值K(一個接近于1的常數)、迭代次數N等參數。

② 隨機產生初始解v0為當前解V=v0，并計算當前解的代價Cost(V)。

③ 在當前解的鄰域中隨機選擇解vi，計算新解的代價Cost(vi) 。

④ 如果Cost(vi)

⑧若迭代次數n≥N，則T=T*K。

⑨ 算法是否結束，是則停止，否則轉③。

基于模擬退火算法的頻率指配算法的流程圖如圖1所示。

圖1 基于模擬退火算法的頻率指配算法流程圖

3 算法的分析與優化

3.1 算法分析

模擬退火算法應用于頻率指配時能夠收斂到一個最優解，從而獲得無干擾的頻率解。然而，模擬退火算法是一個極其耗時的迭代計算過程,理論上算法需要訪問無窮多個狀態[13-14],在實際頻率指配過程中發現了以下特性:

① 頻率解的產生隨機性太大，造成許多不必要的重復，在整個迭代過程中不能快速地收斂，成為算法運行耗時的主要原因。

② 當頻率干擾密度較小且頻率資源遠遠大于所需頻率時，能夠快速獲得最優頻率解。

③ 當頻率干擾密度較大且頻率資源不太充足時，算法運行時間較長，甚至陷入局部最優，不能獲得最優頻率解。

④ 當算法能夠獲取最優解的情況下，算法結束時間的溫度都處于較高位置，即當溫度降低到一定程度后算法能夠獲取最優解的概率大大降低。

試驗表明，初始溫度值為T=10，溫度冷卻衰減函數K=0.9。獲取最優解的概率如表1所示。

表1 不同溫度下獲取最優解的概率

3.2 算法優化

3.2.1 頻率新解的產生

模擬退火算法新解是從當前解的鄰域中隨機選擇產生的，搜索的解空間很大，新解被拒絕的概率大大增加，在約束條件苛刻時產生新解將是一個耗時的過程。

本文針對頻率新解產生進行了以下優化：

(1)優化鄰域結構

針對上述問題，首先重新構建當前解的鄰域，從而增加新解被接受的概率。

首先，計算每個無線設備的評價函數，即每個無線設備與其他無線設備的干擾評估。

式中，Cost(vi)為無線設備i的評估函數，hvi(j)為無線設備i與無線設備j的違約代價。

其次，根據每個無線設備的評價函數確定每個無線設備增加選擇權重，就是增大評估函數大的無線設備的選擇權重。

最后，隨機選擇一個無線設備，通過變換其頻率解(其他無線設備的頻率不變)組成當前解的鄰域，縮小了鄰域范圍。

(2)優化新解產生方式

在新解產生過程中引進貪婪算法[15]，通過在鄰域中多次隨機選擇頻率解，根據Metropolis接受準則，接受選擇的頻率解。產生頻率解的過程如下：

① 初始化新解為當前新解s0，計算當前解的代價Cost(s0)。

② 隨機從鄰域中選擇新解si，計算當前解的代價Cost(si)。

③ 若Cost(s0)≥Cost(si)，則轉⑤，否則在(0,1)區間上產生一個均勻分布的隨機數ξ。

⑤s0=si，并令Cost(s0)=Cost(si)。

⑥若 完成M次選擇，則將當前新解最為最終解返回，否則轉②。

在優化的新解產生過程中，選擇次數M尤其重要，如果M過大則使模擬退火算法迅速收斂到局部最優，M過小則使模擬退火算法收斂效果不明顯。通過試驗證明M值與可用頻率數基本一致。

3.2.2 溫度控制和初始解重置

模擬退火算法在溫度較高時，接受大于當前解代價的新解的概率比較大，從而跳出局部極值，使當前狀態落入包含最優解的全局中；而當溫度降低時，接受的概率迅速減小。當溫度降低到一定程度，算法只接受比當前干擾評估低的新解，算法最終退化為局部搜索。

初始解是模擬退火算法開始迭代的起點。模擬退火算法是一種“健壯”的算法，初始解的優劣不是使算法導出質量高的最優解必要條件。但初始解是模擬退火算法在解空間中隨機選取的解，使得各無線設備的頻率處于隨機狀態。在算法陷入局部最優時可以作為突發狀態，重新設置初始解可以使算法跳出局部搜索。

依據以上特性，模擬退火算法運算過程中在陷入局域搜索時通過重置初始溫度和初始解，使算法的狀態跳出局部搜索，重新在全局搜索最優解，增加獲取最優解的概率。

4 算法性能驗證

為了驗證優化后的算法的性能對比，本節將在相同的模擬環境下，通過運行2種算法分別進行試驗。模擬環境的條件如下：選用相同的無線設備參數，無線設備的數量為50臺；計算無線設備的干擾，選取干擾數目為20、60、100、150、180。

在相同模擬環境下，當無線設備的可用頻率數量為50個時，2種算法計算8次的試驗數據如表2所示。當無線設備的可用頻率數量為75個時，2種算法計算8次的試驗數據如表3所示。

表2 可用頻率為50個的性能對比

表3 可用頻率為75個的性能對比

從表3中可以看出，在相同模擬環境中進行頻率指配時，優化的模擬退火算法雖然在干擾數目少時出現了性能略微下降，但隨著干擾數目的增加，優化的模擬退火算法的性能比原有算法有了大幅提升，最終能夠穩定在一個可接受的范圍。通過對2個表中的數據進行對比，在頻率資源不同的情況下，頻率資源的多少對優化模擬算法的影響要小于對原有算法的影響。

5 結束語

針對基于模擬退火算法的頻率指配算法，通過頻率干擾模型對頻率指配算法的影響，對基于模擬退火算法的頻率指配算法進行了深入的分析，主要包括頻率指配解的獲取方法、模擬退火算法的溫度控制和初始解對最終解的影響。根據模擬退火算法運行機制的特點，對基于模擬退火算法的頻率指配算法進行了優化設計。仿真結果表明，優化后的頻率指配算法效率大大提高，盡最大努力避免了頻率指配算法陷入局部最優解的可能性。

[1] 丁鮮花,方箭,劉艷潔,等.無人機通信鏈路頻率劃分研究[J].無線電工程,2015,45(5):76-80.

[2] 李銳，周自力，劉松淘，等.一種提高頻普利用率的航空導航臺站頻率指配算法[J].電訊技術，2016(12)：1359-1364.

[3] 李軍芳,韓建敏.基于Bertrand博弈論的動態頻譜分配算法[J].無線電工程,2011,41(8)：44-46.

[4] 譚云婷,熊珊.基于空間相鄰分析的基站數據模型與算法研究[J].移動通信，2016,40(1)：34-38.

[5] 王海超,王樂,劉杰群,等.基于頻率和時間的蜂窩間干擾管理方法研究[J].移動通信,2016,40(1)：54-58.

[6] 陳浩.遺傳算法在頻率指配問題中的應用研究[D].北京：北京交通大學，2009.

[7] Kirkpartrick S，Gelatt C D，Vecchi M P．Optimization by Simulated Annealing[J]．Science，1983，220：671-680．

[8] Duque-Ant on M，Kunz D，Ruber B.Channel Assignment for Cellular Radio Using Simulated Annealing[J].IEEE Transactions on Vehicular Technology,1993,42:14-21.

[9] 朱顥東,鐘勇.一種改進的模擬退火算法[J].計算機技術與發展,2009,19(6):32-35.

[10]盧才武,唐曉靈,張志霞,等.計算智能[M].西安：陜西科學技術出版社，2008.

[11]肖劍.無線電磁頻率管理中頻率指配技術的研究[D].長沙：中南大學，2012.

[12]陳華根,吳建生,王家林,等.模擬退火算法機理研究[J].同濟大學學報,2004,32(6):802-805.

[13]王強.模擬退火算法的改進及其應用[J].應用數學,1993,4(3):392-397.

[14]孫坪，吳建軍.直接搜索模擬退火算法的自適應改進[J].計算機工程與應用，2015，51(23)：31-37.

[15]張超.基于貪婪算法的遙感地面站任務調度技術[J].無線電工程,2011,41(1)：58-60.

Frequency Assignment Algorithm Optimization Based on Simulated Annealing Algorithm

WANG Geng-hui

(The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China)

Simulated annealing algorithm is one of the earliest intelligent algorithms applied in frequency assignment，which has the advantages of simple design and reasonable frequency assignment.However，in some specific frequency assignment environments，simulated annealing algorithm has the disadvantage of long run time.In order to optimize the application of simulated annealing algorithm in frequency assignment，a variety of research methods are used in this paper，including analyzing the condition that affects the frequency assignment algorithm，making a deep analysis on the operating mechanism of annealing algorithm in frequency assignment，narrowing the range of neighborhood selection，introducing the greedy principle to improve the way of creating new solutions，adding the process of temperature rising and resetting the initial solution.The operating efficiency of simulated annealing algorithm is promoted while the compliance with frequency assignment constraint condition is ensured.

simulated annealing；frequency assignment；greedy principle

2017-05-18

王更輝(1977—)男，高級工程師，主要研究方向：通信網絡管理。

10.3969/j.issn.1003-3114.2017.05.13

王更輝.基于模擬退火算法的頻率指配算法優化[J].無線電通信技術,2017,43(5):57-61.

[ WANG Genghui.Frequency Assignment Algorithm Optimization Based on Simulated Annealing Algorithm[J].Radio Communications Technology，2017,43(5):57-61.]

TP393

A

1003-3114(2017)05-57-5