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

　　1引言

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

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

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

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

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

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

　　2.1頻率指配概念

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

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

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

　　2.2干擾約束條件

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

　　2.2.1同臺(tái)頻道間隔

　　對于大部分情況，指配給同一臺(tái)站的任何兩個(gè)頻率都應(yīng)有一定的間隔。約束條件可以表示為：

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

　　2.2.2同頻復(fù)用約束條件

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

　　fi-fj≠0

　　2.2.3鄰頻約束條件

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

　　∣fi-fj∣>1

　　2.2.4鏡頻約束條件

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

　　∣fi-fj∣≠m

　　3模擬退火算法及其在頻率指配中的應(yīng)用

　　3.1模擬退火算法簡介 

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

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

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

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

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

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

　　3.2.1實(shí)現(xiàn)步驟

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

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