基于模擬退火算法的地面電視頻率指配方法研究

　　1引言

　　隨著廣播電視數字化技術的發展與應用，新型數字地面業務，如高清晰度電視、移動電視、數據廣播、手機電視正逐步走進千家萬戶。新型業務的引入，使得頻率資源越來越緊張。

　　為了提高頻譜使用效率，各國在頻率指配方法上展開了深入研究。在模擬廣播電視時代，歐洲在1961年Stockholm會議上通過了基于格網法的地面電視規劃方案。我國也在80年代初基于格網法完成了全國地面電視覆蓋網的規劃。

　　在模擬向數字過渡期間，隨著計算機技術的快速發展，各種更高效的頻率指配方法被廣泛應用于頻率優化。美國聯邦通信委員會(FCC)于1996年著手研究全境的地面數字電視覆蓋網頻率規劃問題，通過使用"模擬退火"算法和開發相應的規劃軟件，完成了美國的模數過渡方案。該算法的應用降低了美國模擬向數字過渡期間的轉換成本，提高了頻率資源的使用效率，并帶來了巨大的商業效益。

　　我國地面電視業務可用的頻道數量共有48個，指配給了數量眾多的模擬發射機，承擔著公共服務和各地節目的播出任務。模數同播及諸多新業務的開展對地面電視頻譜資源及廣播電視覆蓋網規劃帶來極大的挑戰。

　　頻道指配可以歸結為在一定約束條件下的線性優化問題。在滿足覆蓋網中各臺站頻道數量要求的基礎上，覆蓋網的綜合干擾水平應最小，占用頻道數量應盡可能少，有效覆蓋的面積和人口應盡可能大。目前已有許多方法用于解決此類問題，如順序圖著色算法、禁忌搜索算法、遺傳算法、模擬退火算法等。本文將就頻率指配的數學模型、模擬退火算法及其在地面電視頻率指配中的應用進行闡述。

　　2頻率指配數學模型

　　2.1頻率指配概念

　　頻率指配的任務就是給每部發射機指配不產生干擾或干擾最小的頻率。

　　指配是一個函數(或映射)。即

　　A：X→Y， x∈X， A(x)∈Y。
　　(X，Y為集合， 表示任取， 表示存在。)
　　設V是發射臺集合，F是可指配的工作頻率集合，則頻率指配可以表示為：
　　A：V→F，V，F為集合， v∈V， A(v)∈F。

　　2.2干擾約束條件

　　頻率指配數學模型建立在相應的干擾和約束條件之上。在地面電視業務規劃中，同一發射臺址上的發射頻率必須滿足必要的同、鄰、鏡像頻道約束條件，不同發射臺址還需滿足頻率復用的約束條件。

　　2.2.1同臺頻道間隔

　　對于大部分情況，指配給同一臺站的任何兩個頻率都應有一定的間隔。約束條件可以表示為：

　　∣fi-fj∣≥m，其中m代表發射機i與j之間所需的頻道間隔數。

　　2.2.2同頻復用約束條件

　　一對發射機除非在地理上有足夠的間距，否則不能指配相同的頻道。如果fi和fj分別為指配給發射機i和j(i≠j)的頻率．那么可以用下式描述：

　　fi-fj≠0

　　2.2.3鄰頻約束條件

　　當不同發射臺址上的兩部發射機使用相鄰的頻道時，可能存在鄰頻干擾。鄰頻約束條件可以表示為：

　　∣fi-fj∣>1

　　2.2.4鏡頻約束條件

　　不同發射臺址上的兩部發射機使用鏡像頻道時，高于接收機本振頻率的非欲收圖像或伴音載頻信號與接收機本振頻率信號混頻后，進入接收機中頻范圍內的頻率信號可能會造成鏡頻干擾。如果用m表示鏡頻頻道間隔，鏡頻約束條件可以表示為：

　　∣fi-fj∣≠m

　　3模擬退火算法及其在頻率指配中的應用

　　3.1模擬退火算法簡介 

　　固體退火是指先將固體加熱至融化，再徐徐冷卻使之凝固成規整晶體的熱力學過程。可大致描述如下：

　　固體加熱熔解為液體后，內部的粒子排列由比較有序的結晶態轉變為無序的液態，系統能量也隨溫度提高不斷增大，冷卻時，液體粒子的熱運動漸漸減弱，溫度降至結晶溫度時，粒子運動變為圍繞晶體格點的微小震動，液體開始凝固成固體的晶態，這個過程稱為"退火"，退火過程必須徐徐進行，以使系統在每一溫度下都達到平衡態，最終達到固體的基態，此時系統能量最小。冷卻時若急劇降低溫度，將引起淬火效應，固體將冷凝為非均勻的亞穩態，系統能量無法達到最小值。

　　根據Boltzmann有序性原理，退火過程遵循熱平衡封閉系統的熱力學過程--自由能減少定律：

　　"對于與周圍環境交換熱量而溫度保持不變的封閉系統，系統狀態的自發變化總是朝著自由能減少的方向進行，當自由能達到最小值時，系統達到平衡態"。

　　通過對固體退火過程的研究，于1982年首先意識到固體退火過程與離散系統模型中的組合優化問題之間存在著某種相似性，同時，受到Metropolis等對固體在常溫下達到熱平衡過程所做的模擬中的啟發，Kirkpatrick提出把Metropolis準則引入到優化過程中，建立一種對Metropolis算法進行迭代的組合優化算法，由于該算法模擬固體退火的過程，因此經常稱之為"模擬退火算法"。

　　3.2頻率指配中的模擬退火算法

　　3.2.1實現步驟

　　3.2.2目標函數
　　在頻率指配過程中，目標函數E可包含以下幾項：

 
　　目標函數E可用于評估頻率指配方案的優劣。其中(i=1，2，…，6)是加權系數，用來反映上述各因子的相對重要程度。除上述指標外，其他指標如覆蓋及干擾的人口和面積等也可以作為加權因子。