分层优化方法被用来设计提供为新加坡地区提供服务的蜂窝系统。在我们的研究中使用了模仿新加坡地形,话务分布和人口的数据。整个地区被分为三种类型和 100 个网格。表 1 列出了关于每个网格的话务密度和地面类型等信息。服务区域 S 有 625km ,每个网格的区域面积约为 2.5*2.5 km 。在系统设计中采用了 7 小区频率复用模型。假设要达到 = 90% 的区域覆盖率并且忙时初始呼叫的阻塞率 = 5 %。
当 2.3 时,相应于 90 %的区域覆盖率,边界处的位置覆盖 = 75 %,其中 是接收信号的慢衰落部分的标准偏差, 是距离因子的指数 [2] 。对于给定的位置覆盖概率 和要求的 C/N 和 C/I ,设置边界处的接收信号强度 =- 93dbm[1][9] 。假设每个小区的信道数为 45 ,平均通话时长为 1.76min/call ,呼叫尝试率为 0.9call/h ,则每小区可提供的话务负载为 39.6 爱尔兰,能为 =(39.6*60)/(1.76*0.9)=1500subscribers/h 的总移动单元数提供服务。
首先,开始进行设计时先需要确定小区数的上界。从 (4) - (6) 我们可得 = 17 , d = 3.53km 。从 (7) 我们有 = 29400/1500 20 。同时考虑覆盖和话务性能,我们选择 n = max( , ) = 20 。
接着,来确定 20 个小区的安置,假设给出系统成本的标准化参数如下: =1000 , =5.0 , = 10.0 , = 0.5 。基站和移动单元的参数选择如下 [9] :对所有的小区 k , 。
根据 [24] 和 [25] ,我们得到了天线成本和其增益及发射机 ( 或接收机 ) 成本和其发射功率之间的逼近线性关系。假设给出关于天线增益 g 的成本函数 如下:
= 40+C a · g
M
关于发射功率 P 的成本函数 如下:
= 60 + C t · P
M
其中 M 是一个大的正数。
我们根据上面的具体参数应用模拟退火算法 SAEOM 来求解 EOM 问题。冷却进度表的控制参数如下:初始接受率χ= 0.9 , 次数内 目标= 0.38*3*20*100 , 最大容许偏差 = 0.62*(3*m*n) ,最大生成极限= 4*M UB [21] 。在 HP-C180 的 UNIX 系统上用 C 语言执行了这个算法。
图 3 给出了一个初始可行解 ( 初始设计 ) 。具有相同阴影的相邻网格组成一个小区。总系统成本为 24349.68 。图 4 给出了用 SAEOM 算法求出的最优解。这个最优解是在用不同的初始可行解运行程序 10 次后才获得的。最终设计 f c (s) 的邻近最优系统成本是 20139.20 。小区数进一步减少了 6 个。图 5 显示了收敛记录,即用 SAEOM 算法求解 EOM 问题的退火曲线。退火需要的平均 CPU 时间为 34.65 分钟。
为了评估 SA 方法求得的解,我们把它与用 Aarts 和 Korst[15] 的本地搜索过程求得的最佳解和用随机生成过程获得的解比较。用本地搜索过程求得的最佳解为系统成本 f c (s) = 20452.4 和小区数 n = 13 。如成本函数 (19) 所示,每个小区的固定成本 决定总系统成本。这意味着成本有效设计应该有较少的小区数和每个小区较高的平均话务负载。图 6 和图 7 分别表示用 SAEON 和本地搜索方法求得的最佳解中的话务量柱形图。图 8 表示在小区数也是 13 这种情况下,随机生成过程获得的解的话务量分布。虚线和实心条分别代表每个小区能提供的话务负载和需要的话务负载。从图 6-8 ,我们观察到用 SAEON 求得的逼近最优解在能提供的话务负载和需要的话务负载之间取得了好的折衷。与其它两个过程相比,每个小区的话务负载也呈均匀分布。如图 4 的最终设计所示,这个设计能满足覆盖要求,同时也努力用最小的小区数和最佳的小区安置适应非一致话务负载。
天线增益和发射功率的逼近最优值可从最佳解中获得。
在最后一步,基站和移动单元的所有参数都要根据所在小区内具体的地形数据和覆盖特征进行调整。从上面两层获得的结果能满足覆盖的质量要求,但并不能提供每个小区的所有预期话务量。在最后一层, Gamst[23] 技巧被用来确定要分配的信道数下界。然后进一步应用 Dugue-anton[20] 的信道分配过程去满足话务要求和避免干扰。
B. SA 算法的性能
模拟退火方法 SAEOM 的性能研究分两个方面:解的质量和执行时间 [13] 。我们把 SAEOM 求得的次优解比作用本地搜索方法及随机生成过程获得的最优解。如表 Ⅱ 和 Ⅲ 所示的四种不同大小的问题都应用了这些方法。
本地搜索算法是一种由 Aarts[15] 提出的贪婪算法,用本地搜索算法求得的解严重地依赖于初始解。计算时间的上界,即最差情况下的时间复杂度对很多问题而言都不可知 [15][13] 。给定次数 N 对相同的问题用不同的初始值运行本地搜索算法 , 我们就得到了平均时间,平均 CPU 时间,最佳结果及进行大量优化获得最佳结果所花的总 CPU 时间 [15][8] 。
在对同样的问题运行 SAEOM10 次后就得到了模拟退火算法 SAEOM 的 CPU 时间和最佳结果的平均值。
表 Ⅱ 和 Ⅲ比较了这些算法的解。从中可注意到模拟退火方法能在较短的时间内求得较好的解。由于固定小区成本 决定总系统成本,如 表 Ⅱ所示在 SAEOM 的平均结果和本地搜索的最佳结果之间没有发现什么显著区别。当话务成本因子 增加时,与 表 Ⅱ相比,表Ⅲ中的 SAEOM 的解和本地搜索的解的差别变大。从 表 Ⅱ 和 Ⅲ可以看出,每次执行本地搜索所需的 CPU 时间远远小于模拟退火所需的 CPU 时间。但与模拟退火相比,本地搜索需要多得多的时间去得到最优解。
一般情况下模拟退火算法解的质量可以通过调节控制参数 ( λ , χ ,etc) 的值,减慢冷却过程和增加马尔可夫链的长度 [15] 来得到改善。图 9 显示了应用 SAEOM 算法时,解的质量和运行时间之间的折衷。成本为 的最终解的质量由如下定义的相当误差 ε 决定:
ε =
其中 是曾经求得的最佳值。对于大型案例的广泛研究表明一个具有良好质量的解能通过降低λ和增加χ来得到。
本论文研究了对于蜂窝移动通信网络规划的经济优化建模问题。提出了一个分层优化规划方法,它既考虑到覆盖的要求又考虑到话务负载。发展了一个组合优化模型去确定合适的小区数量和选择最佳的基站位置。一个建立在改进的模拟退火基础上的算法被用来求解这个模型并取得了逼近最优解。大型的复杂移动通信系统的资源管理和网络规划的最优化技术的发展和应用将是我们未来的研究课题。
图 2 :无线网络规划的分层结构