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

　　1引言

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

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

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

　　我國地面電視業(yè)務可用的頻道數(shù)量共有48個，指配給了數(shù)量眾多的模擬發(fā)射機，承擔著公共服務和各地節(jié)目的播出任務。模數(shù)同播及諸多新業(yè)務的開展對地面電視頻譜資源及廣播電視覆蓋網(wǎng)規(guī)劃帶來極大的挑戰(zhàn)。

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

　　2頻率指配數(shù)學模型

　　2.1頻率指配概念

　　頻率指配的任務就是給每部發(fā)射機指配不產(chǎn)生干擾或干擾最小的頻率。

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

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

　　2.2干擾約束條件

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

　　2.2.1同臺頻道間隔

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

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

　　2.2.2同頻復用約束條件

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

　　fi-fj≠0

　　2.2.3鄰頻約束條件

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

　　∣fi-fj∣>1

　　2.2.4鏡頻約束條件

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

　　∣fi-fj∣≠m

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

　　3.1模擬退火算法簡介 

　　固體退火是指先將固體加熱至融化，再徐徐冷卻使之凝固成規(guī)整晶體的熱力學過程?？纱笾旅枋鋈缦拢?/p>

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

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

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

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

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

　　3.2.1實現(xiàn)步驟

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

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