分层优化网络资源规划方法

1、分层优化网络资源规划方法I介绍随着对移动通信业务需求的巨大增长， 系统设计优化和无线网络规划的问题变得 越来越重要。虽然在移动蜂窝网络规划领域作了很多关于覆盖分析，信道分配，路 由选择和传播等方面的研究，但在关于成本有效系统设计的网络规划方面的研究却 不多 1-5 。实际上，在复杂的移动通信设计中必须考虑很多因数，如系统性能， 系统容量，小区覆盖，话务量，地形和传播特征等。关于小区数量，小区位置，基 站和移动单元的设计参数及信道分配的决定必须根据相互之间的关系作出。小区的 位置可以根据给定的小区数量，覆盖性能，话务分布和传播环境来确定。基站和移 动单元的设计参数必须要等到小区的部署全部完成后才

2、能具体化。最后，在话务和 避免干扰等方面能改善系统性能的信道分配 6-8 只有在移动蜂窝网络的结构被详 细说明后才能决定。在决定任何通信系统经济上的可行性时成本都是一个关键因素。 一个好的设计方 法应该能在诸如网络性能标准，话务量和技术升级等因素中进行权衡，使成本最优 化9 。至今已有几个商用软件包被成功应用于移动蜂窝系统的网络规划中，如 plaNET 软件。但不管怎样，它们在规划中都没有直接包括金融上的规划或者考虑 成本。另一方面，如 Analysis STEM 建模系统等的一些软件是决策支持工具以获 得金融模型并提供蜂窝移动系统的成本分析。但在它们的成本模型中又没有考虑网 络规划。这篇论文

3、试图同时考虑成本和网络规划因数以填补这个缺口。这种唯一的 组合对移动网络业务的供应商有极大的意义。它发展了最优化的网络规划方法，在系统设计上既使总的系统成本最小化同时又保证了好的系统性能。可操作的研究策略分层优化的规划早已被成功应用于大规模制造系统的生产 规划和健康关心及服务系统的决策制定中 10-12 。在这些事例中，集合规划通常 是不可行的，因为对于大型的复杂系统的集合规划模型通常不能被公式化或无法求 解。在本论文中，我们描述了关于移动蜂窝通信系统设计的网络规划的分层特性， 提出了一个分层优化规划方法 (HOP) 以确定无线网络的结构，即小区的数量，小区 的大小，小区的安置，天线增益及天线

4、高度的参数和基站及移动单元的发射功率。 一个组合优化模型被推导出来以确定小区的最佳数量和基站的最佳位置使得在总的 系统成本最小化的同时又能保证良好的覆盖质量和话务性能。规划模型是一个有难度的组合优化问题 13 。诸如分支界限法和动态规划法之类 的优化算法不能在合理的时间内求得优化解 13 。因为牵涉到很多变量和复杂的约 束，被用来解决大型组合优化问题的分解法和拉格朗日松驰法 14 可能也无法应用 到规划模型中。在本论文中，一个建立在模拟退火 (SA) 基础上的算法被推导出来用 于解决此问题，并在合理的计算量内求得了逼近的最优结果。本论文的安排如下。 在第二节， 我们描述了蜂窝无线网络规划问题。

5、 第三节提出 了解决这个问题的分层优化规划方法。在这一节还提出了组合优化模型和模拟退火 算法。最后，在第四节给出了用 HOP 方法实现新加坡的蜂窝移动通信服务系统的 网络规划的模拟结果。II问题陈诉如图 1 所示，假如我们想要发展一个蜂窝移动通信系统为新加坡地区提供服务。 整个地区将覆盖三种类型的土地：市区，郊区和农村。我们需要考虑非一致的话务 分布：话务高峰通常在市中心，局部话务高峰在郊区中心。给定与覆盖性能相关的 地区覆盖概率 Pa 。边界处的定位概率 PL 和覆盖边界处接收信号强度的门限电平 Pcell 可以从覆盖概率 Pa 和要求的信号强度，即载干比 C/N2 中推导得出。服务等 级被

6、设定为在忙时发起呼叫的阻塞概率 Pblock 。为满足业务要求在系统中采用了频 率复用方案。问题是怎样设计一个最优网络结构， 即确定小区的数量， 小区的大小， 每个基站 的位置和基站及移动单元的参数，以保证达到要求的性能目标，并使总的系统成本 最小化。基站设备的成本是由机器设备及安装，天线，建筑物及铁塔和发射机及收 信机等的成本决定的。为了设计这样一个系统， 必须考虑许多因素 1,9 ，需要作出许多不同层次的决 策。涉及的主要因素如下：系统性能的详述，小区的覆盖，话务分布，地形，传播 数据和系统成本因素。所有的这些因素相互影响，它们之间的复杂关系需要确定。 由于系统的复杂性，在实际中网络规划过

7、程是分层次的。规划活动包括：性能的说 明和分析，从小区的数量及小区的位置方面来说的形式上的小区规划，和关于射频 小区参数的设置及信道分配的详细小区设计。皿网络规划和设计方法我们提出了蜂窝移动通信网络设计的 三层 HOP 方法。网络规划的三层结构如图 2 所示。在第一层，决定了小区数量的上界和相应的小区覆盖范围。 HOP 的输入参数如 下：忙时的话务负荷，覆盖要求和整个服务区域的地形特征。并选择典型情况下的 传播参数。任务为用最小的小区数量覆盖整个区域并满足平均话务需求。在第二层，小区的数量和最佳的小区位置由大型的组合优化模型决定。 模型的规 划目标是使总的系统成本最小化，同时确保覆盖的质量，并

8、努力符合非一致话务负 载的要求。我们考虑到了不同用户的话务密度和不同类型服务区域的地形特征。如 图 1 所示，整个区域被划分为市区，郊区和农村。这些区域进一步被划分为更小的 网格。环境结构方面的信息，用户密度和每个网格的平均俯角等都可以从地理信息 系统(GIS)的数据库里得到。详细规划在第三层进行， 每个小区的具体参数， 如天线模型及其增益， 发射功率， 天线高度和信道利用率等都在这一层设置。最后，把成本估计出来。规划过程的总体系统性能很大程度上取决于不同层次上的不同活动和决策相结 合的程度。如图 2 所示，决策必须在双向上相互调整和加强。为了获得这个 HOP 方法和最优成本模型，需要考虑几个

9、复杂的关系：覆盖率的 要求，小区的覆盖范围和小区边界信号强度之间的关系 2 ；传播损失和具体的人造 建筑物及地形外表之间的关系 17 ；设备和成本之间的关系。传播损失可以用 Hata 传播模型预测 18 。 Hata 模型刻划了对于市区，郊区和 农村等地形是准光滑或不规则的不同环境下无线传播的特性。在蜂窝系统的设计中 这个模型广泛应用于预测不同环境下的路径损失 1719 。关于市区内基本传输损耗的 Hata 公式由下式给出：Lu (db) = 69.55 + 26.26 log(f) - 13.82 log( hb) - a( hm)+ 44.9 - 6.55 log( hb) log(d)(

10、1)其 中 移 动 台 天 线 高 度 的 校 正 因 子 a( hm ) 为 ： 对 于 中 小 城 市 ，a( hm )=1.1 log(f)-0.7 hm -1.56 log(f)-0.8;对于大城市，a(hm )=3.2 log(11.75 hm)2-4.97，且频率 f 400MHz。郊区和农村的传播损失 Lsu 和 Lrqo 由下式给出：Lsu = Lu - 2 log(f/28)2 - 5.4(2)Lrqo = Lu - 4.78 log(f) 2 + 18.33 log(f) - 35.94(3)Hata 公式适用的范围为频率 f 在 150 MHz 到 1000 MHz 之间

11、，基站天线高度 hb介于30m和100m之间，移动台天线高度hm介于1m和10m之间，距离d的 变化范围为从 1km 到 20km 。在以下各节中，将给出 HOP 方法每一层的细节。A. 第一层：小区数量和小区大小的最初决定首先，根据整个地区的覆盖性能和平均话务需求决定需要的最小基站数。 为了确 定系统设计中需要的小区数的上界， 这个最小的基站数是在最差的情况下计算的的。 在此我们取小区复用因子 k=7 ，并给定地区覆盖概率 Pa 和用户阻塞率 Pblock 。把覆盖区域对移动话务量的要求考虑为在忙时由在此区域内的移动单元发起的 所有呼叫尝试。它是根据覆盖区域内车辆的交通流量来预测的。给定预估

12、的呼叫尝 试率，该区域的话务负载就转化为忙时在此区域内的移动用户数。我们定义以下符号：C pt 根据每个小区的信道数和给定的阻塞率 Pblock 得到的每个小区可以提 供的话务量 (用户数/ 小时)。C tt 整个服务区的总话务量 (用户数 / 小时 )。Pcell覆盖边界处的接收信号强度的门限电平。P pp射频输出的峰值功率(dbW) 。Pt发射天线的输入功率(dbW) 。Pr接收天线的接收功率(dbW) 。gb , gm 分别为基站和移动单元的天线增益 (db)。hb,hm分别为基站和移动单元的天线高度。d小区的平均辐射半径 (km) 。S服务区的总面积 (km 2 )。首先考虑覆盖性能。

13、从发射机到接收机射频功率的链接预算资源由下列方程给出1 ，9 ：Pr=Pt+g b-L(d)+g m(4)Pt=P PP-I(5)其中L(d)是传输损耗(db)，而I是绝缘体，组合器和射频电缆的复合损耗。整个地区小区数量的上界由关于市区的 Hata 传播模型决定。 关于郊区和农村的模型将在规划的下一层考虑。假设有下列条件 hm=3m， g b =12dBi ， g m = 2dBi ，l = 4dB 的公式(1)变为：L(d) = 123.73 + 35.22-log(d)为保证满足覆盖要求，我们有Pr=-73.73-1 , 9 : Ppp = 10W , hb=30m ,f = 900MHz

14、 。则关于传播损失L35.22- log(d) Pcell即log(d) random0,1)then s := sEnd ；k := k+1 ；计算 tk ；Until 停止准则成立End与 Kirpatrick16 提出的模拟退火技巧相比，这个用 Huang 方法 21 的新 SA 技巧能通过退火过程动态调节马尔可夫链的长度达到平衡，退火需要的 CPU 时间 也大大地下降了。C. 详细规划和准确的成本估计在这一层， 确定每个小区内的基站位置， 诸如天线塔高度， 天线增益和发射功率 等参数都进一步根据每个小区的地形不规则性的特征，表面覆盖和环境进行调整。 从上面两层得到的结果已满足了覆盖性能

15、，并试图满足话务要求。但不管怎样，在 某些小区的话务过载可能仍然存在。在这一层，可以用 Hale6 和 Gamst23 的信 道分配策略来提供信道数的下界。 把在 7820 中提到的固定和动态信道分配策略 应用于蜂窝系统的网络规划以提供足够的容量来为预期的话务量服务，并保持无线 干扰到最小限度。如果系统性能在调整后达到了要求，最后的系统设计就确定了，也就可以估计出 蜂窝系统的成本。否则在这一层的结果将反馈到第一层和第二层。然后重复整个过 程。在这种情况下，可能需要增加小区的数量以满足规定的服务质量。W模拟结果A. HOP模型的应用分层优化方法被用来设计提供如图1和图3所示的为新加坡地区提供服务

16、的蜂 窝系统。在我们的研究中使用了模仿新加坡地形，话务分布和人口的数据。整个地 区被分为三种类型和100个网格。表1列出了关于每个网格的话务密度和地面类型 等信息。服务区域S有625km 2，每个网格的区域面积约为km 2。在系 统设计中采用了 7小区频率复用模型。假设要达到 Pa = 90%的区域覆盖率并且忙 时初始呼叫的阻塞率Pb = 5 %。当p np 2.3时，相应于90 %的区域覆盖率，边界处的位置覆盖 Pl = 75 %， 其中p是接收信号的慢衰落部分的标准偏差，np是距离因子的指数2。对于给定 的位置覆盖概率Pl和要求的C/N 和C/I，设置边界处的接收信号强度 Pcell二 9

17、3dbm19。假设每个小区的信道数为 45 ,平均通话时长为1.76min/call，呼叫尝试率为 0.9call/h，则每小区可提供的话务负载为39.6爱尔兰，能为Cpt 的总移动单元数提供服务。首先，开始进行设计时先需要确定小区数的上界。从-(6)我们可得x二17，dmax = 3.53km。从我们有n? = 29400/150020。同时考虑覆盖和话务性能，我们选择 n = max（门！，n 2） = 20。接着，来确定 20个小区的安置，假设给出系统成本的标准化参数如下：Ccell =1000 , Ca =5.0 , Ct = 10.0 , Ctraf = 0.5。基站和移动单元的参数

18、选择如 下9:对所有的小区 k , gL 8dBi, gU 18dBi ,PL 30dBm, FU 36dBm, gmk 0dBi。根据24和25，我们得到了天线成本和其增益及发射机（或接收机）成本和其发射功率之间的逼近线性关系。假设给出关于天线增益g的成本函数CA（g）如下：CA（g） =40+C a g0 g guMg gu关于发射功率F的成本函数CT（P）如下：CT（P） =60 + C t F0 P PuImp Pu其中M是一个大的正数。我们根据上面的具体参数应用模拟退火算法 SAEOM来求解EOM问题。冷却 进度表的控制参数如下：初始接受率X = 0.9，次数内目标二0.38*3*2

19、0*100 ，最 大容许偏差=0.62*（3*m*n），最大生成极限=4*M ub21。在HP-C180 的UNIX 系统上用C语言执行了这个算法。图3给出了一个初始可行解（初始设计）。具有相同阴影的相邻网格组成一个小区。 总系统成本为24349.68。图4给出了用SAEOM算法求出的最优解。这个最优解 是在用不同的初始可行解运行程序 10次后才获得的。最终设计fc（s）的邻近最优系 统成本是 20139.20 。小区数进一步减少了 6个。图5显示了收敛记录，即用 SAEOM 算法求解 EOM 问题的退火曲线。退火需要的平均 CPU 时间为 34.65 分钟。为了评估 SA 方法求得的解， 我

20、们把它与用 Aarts 和 Korst15 的本地搜索过程 求得的最佳解和用随机生成过程获得的解比较。用本地搜索过程求得的最佳解为系 统成本fc(s) = 20452.4和小区数n = 13。如成本函数(19)所示，每个小区的固定成 本 C cell 决定总系统成本。 这意味着成本有效设计应该有较少的小区数和每个小区较 高的平均话务负载。 图 6 和图 7 分别表示用 SAEON 和本地搜索方法求得的最佳解 中的话务量柱形图。图 8 表示在小区数也是 13 这种情况下，随机生成过程获得的 解的话务量分布。虚线和实心条分别代表每个小区能提供的话务负载和需要的话务 负载。从图 6-8 ，我们观察到

21、用 SAEON 求得的逼近最优解在能提供的话务负载和 需要的话务负载之间取得了好的折衷。与其它两个过程相比，每个小区的话务负载 也呈均匀分布。如图 4 的最终设计所示，这个设计能满足覆盖要求，同时也努力用 最小的小区数和最佳的小区安置适应非一致话务负载。天线增益和发射功率的逼近最优值可从最佳解中获得。 在最后一步，基站和移动单元的所有参数都要根据所在小区内具体的地形数据和 覆盖特征进行调整。从上面两层获得的结果能满足覆盖的质量要求，但并不能提供 每个小区的所有预期话务量。在最后一层， Gamst23 技巧被用来确定要分配的信 道数下界。然后进一步应用 Dugue-anton20 的信道分配过程去满足话务要求和 避免干扰。B.SA 算法的性能模拟退火方法 SAEOM 的性能研究分两个方面：解的质量和执行时间 13 。我 们把 SAEOM 求得的次优解比作用本地搜索方法及随机生成过程获得的最优解。 如 表U和川所示的四种不同大小的问题都应用了这些方法。本地搜索算法是一种由 Aarts15 提出的贪婪算法， 用本地搜索算法求得的解严 重地依赖于初始解。计算时间的上界，即最差情况下的时间复杂度对很多问题而言 都不可知 1513 。给定次数 Nopt 对相同的问题用不同的初始值运行本地搜索算法 , 我们就得到了平均