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

　　1引言

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

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

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

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

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

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

　　2.1頻率指配概念

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

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

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

　　2.2干擾約束條件

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

　　2.2.1同臺頻道間隔

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

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

　　2.2.2同頻復用約束條件

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

　　fi-fj≠0

　　2.2.3鄰頻約束條件

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

　　∣fi-fj∣>1

　　2.2.4鏡頻約束條件

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

　　∣fi-fj∣≠m

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

　　3.1模擬退火算法簡(jiǎn)介 

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

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

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

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

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

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

　　3.2.1實(shí)現步驟

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

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