基于模拟退火算法的地面电视频率指配方法研究

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)是加权系数，用来反映上述各因子的相对重要程度。除上述指标外，其他指标如覆盖及干扰的人口和面积等也可以作为加权因子。

3.2.3应用举例

问题：
　　已知现有20个台站，每个台站有20个可选频道(编号为DS-13～DS-32)。要求给每个台站指配一个频道，使得相邻发射台站的频率指配满足同频复用约束条件，同时
使用的频道数量少，且尽可能使用低频段。
分析：

　　给20个台站分别指配一个频道，共有2020种可能的覆盖组网方案。

　　如果采用世界快的超级计算机进行"穷举"，运算速度按每秒约280，6万亿次计算，需要t=2020／(280.6×1012)秒≈11849年。可见，采用此方法不可能在有生之年计算比较所有方案，从中找出的方案。因此，只能采用某些优化算法如模拟退火算法等找到满足规划要求的"近似"方案。

　　为了便于计算，可以用一个邻接矩阵N来表示上述发射台站之间的频率约束关系，发射台站之间频率约束关系对应的邻接矩阵。

　　一旦用于频率指配的邻接矩阵生成，接下来的问题是怎样用尽可能少的频道来指配。在实际频率指配中，可以采用数学中的模拟退火方法逼近解。

模拟退火算法的具体实现步骤：

　　(1)初始化：初始温度T1=500，T2=0.01

　　初始解状态S(是算法迭代的起点)

　　Freq[20]={13，14，15，16，17，18，19，20，21，22，23，24，25，26，27，28，29，30，31，32}；

　　(2)从Freq领域中产生满足约束条件的新解Freq′；

　　(3)计算增量△E=E(Freq′)-E(Freq)，其中E(Freq)为目标函数

　　E(Freq)=sum(Freq)+span(Freq)×μ(μ为加权值，span为所指配的频道与频道之差)；

　　(4)若△E<0则接受Freq′作为新的当前解，否则以概率exp(-△E／)接受Freq′作为新的当前解；

　　(5) 如果满足终止条件则输出当前解作为解，结束程序； (6) T1逐渐减少(T1=0.998T1)，且T1>T2，然后转第2步。

　　此时目标函数E(Freq)=313，迭代次数k为5751次。

　　测试结果表明，只要计算时间足够长，模拟退火算法就可以保证以概率1.0收敛于全局解。在实际应用中，由于计算速度和时间的限制，优化效果和计算时间二者之间存在矛盾，计算结果可能会陷入局部解。

　　近年来，根据"科学发展观要求"，为使频率规划决策更具科学性，我国在多次地面电视频率规划工程中，均使用了覆盖面积、人口，可用场增量等统计指标，取得了良好的收效。由于指标数据的获得需考虑复杂的台站地理关系和统计模型，耗时费力，在时间来不及时，不得已还要借助经验进行频率规划决策。分析表明，上述指标的统计方法具备一定规律，经过适当的计算机标准化处理后可降低人工依赖，自动获得，如采用模拟退火算法等进行优化处理，可极大提高频率使用效率，降低覆盖网综合干扰水平，加快我国地面数字电视频率规划进程。