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

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

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

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

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

5、给出了用HOP方法实现新加坡的蜂窝移动通信服务系统的网络规划的模拟结果。n问题陈诉如图1所示，假如我们想要发展一个蜂窝移动通信系统为新加坡地区提供服务。整个地区将覆盖三种类型的土地：市区，郊区和农村。我们需要考虑非一致的话务分布：话务高峰通常在市中心，局部话务高峰在郊区中心。给定与覆盖性能相关的地区覆盖概率Pa。边界处的定位概率Pl和覆盖边界处接收信号强度的门限电平Pceii可以从覆盖概率Pa和要求的信号强度，即载十比C/N2中推导得出。服务等级被设定为在忙时发起呼叫的阻塞概率Pbiock。为满足业务要求在系统中采用了频率复用方案。问题是怎样设计一个最优网络结构，即确定小区的数量，小区的大小，

6、每个基站的位置和基站及移动单元的参数，以保证达到要求的性能目标，并使总的系统成本最小化。基站设备的成本是由机器设备及安装，天线，建筑物及铁塔和发射机及收信机等的成本决定的。为了设计这样一个系统，必须考虑许多因素1,9,需要作出许多不同层次的决策。涉及的主要因素如下：系统性能的详述，小区的覆盖，话务分布，地形，传播数据和系统成本因素。所有的这些因素相互影响，它们之间的复杂关系需要确定。由于系统的复杂性，在实际中网络规划过程是分层次的。规划活动包括：性能的说明和分析，从小区的数量及小区的位置方面来说的形式上的小区规划，和关于射频小区参数的设置及信道分配的详细小区设计。m网络规划和设计方法我们提出了

7、蜂窝移动通信网络设计的三层HOP方法。网络规划的三层结构如图2所示。在第一层，决定了小区数量的上界和相应的小区覆盖范围。HOP的输入参数如下：忙时的话务负荷，覆盖要求和整个服务区域的地形特征。并选择典型情况下的传播参数。任务为用最小的小区数量覆盖整个区域并满足平均话务需求。在第二层，小区的数量和最佳的小区位置由大型的组合优化模型决定。模型的规划目标是使总的系统成本最小化，同时确保覆盖的质量，并努力符合非一致话务负载的要求。我们考虑到了不同用户的话务密度和不同类型服务区域的地形特征。如图1所示，整个区域被划分为市区，郊区和农村。这些区域进一步被划分为更小的网格。环境结构方面的信息，用户密度和每个

8、网格的平均俯角等都可以从地理信息系统(GIS)的数据库里得到。详细规划在第三层进行，每个小区的具体参数，如天线模型及其增益，发射功率,天线高度和信道利用率等都在这一层设置。最后，把成本估计出来。规划过程的总体系统性能很大程度上取决于不同层次上的不同活动和决策相结合的程度。如图2所示，决策必须在双向上相互调整和加强。为了获得这个HOP方法和最优成本模型，需要考虑几个复杂的关系：覆盖率的要求，小区的覆盖范围和小区边界信号强度之间的关系2;传播损失和具体的人造建筑物及地形外表之间的关系17;设备和成本之间的关系。传播损失可以用Hata传播模型预测18。Hata模型刻划了对于市区，郊区和农村等地形是准

9、光滑或不规则的不同环境下无线传播的特性。在蜂窝系统的设计中这个模型广泛应用于预测不同环境下的路径损失1719。关于市区内基本传输损耗的Hata公式由下式给出：Lu(db)=69.55+26.26-log(f)-13.82-log(hb)-a(hm)+44.9-6.55log(hb)log(d)(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，且频率f400MHz。郊区和农村的传播损失Lsu和Lrqo由下式给出：Lsu=Lu-2-lo

10、g(f/28)2-5.4(2)Lrqo=Lu-4.78-log(f)2+18.33-log(f)-35.94(3)Hata公式适用的范围为频率f在150MHz到1000MHz之间，基站天线高度hb介于30m和100m之间，移动台天线高度hm介于1m和10m之间，距离d的变化范围为从1km到20km。在以下各节中，将给出HOP方法每一层的细节。A.第一层：小区数量和小区大小的最初决定首先，根据整个地区的覆盖性能和平均话务需求决定需要的最小基站数。为了确定系统设计中需要的小区数的上界，这个最小的基站数是在最差的情况下计算的的。在此我们取小区复用因子k=7，并给定地区覆盖概率Pa和用户阻塞率Pblo

11、ck。把覆盖区域对移动话务量的要求考虑为在忙时由在此区域内的移动单元发起的所有呼叫尝试。它是根据覆盖区域内车辆的交通流量来预测的。给定预估的呼叫尝试率，该区域的话务负载就转化为忙时在此区域内的移动用户数。我们定义以下符号：Cpt根据每个小区的信道数和给定的阻塞率Pbiock得到的每个小区可以提供的话务量（用户数/小时）。Ctt整个服务区的总话务量（用户数/小时）。Pcell覆盖边界处的接收信号强度的门限电平。Ppp射频输出的峰值功率（dbW）。Pt发射天线的输入功率（dbW）。Pr接收天线的接收功率（dbW）。gb,gm分别为基站和移动单元的天线增益（db）。hb,hm分别为基站和移动单元的天

12、线高度。d小区的平均辐射半径（km）。S服务区的总面积（km2）。首先考虑覆盖性能。从发射机到接收机射频功率的链接预算资源由下列方程给出1,9：Pr=Pt+gb-L（d）+gmPt=Ppp-l其中L（d）是传输损耗（db），而l是绝缘体，组合器和射频电缆的复合损耗。整个地区小区数量的上界由关于市区的Hata传播模型决定。关于郊区和农村的模型将在规划的下一层考虑。假设有下列条件hm=3m,gb=12dBi,gm=2dBi,l=4dB的公式变为：L(d)=123.73+35.22log(d)为保证满足覆盖要求，我们有Pr=-73.73-1,9:Ppp=10W,hb=30m,f=900MHz。则关丁

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

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

15、00个网格。表1列出了关丁每个网格的话务密度和地面类型等信息。服务区域S有625km2,每个网格的区域面积约为2.5*2.5km2。在系统设计中采用了7小区频率复用模型。假设要达到Pa=90%的区域覆盖率并且忙时初始呼叫的阻塞率Pb=5%。当p/np2.3时，相应丁90%的区域覆盖率，边界处的位置覆盖Pl=75%,其中p是接收信号的慢衰落部分的标准偏差，np是距离因子的指数2。对丁给定的位置覆盖概率Pl和要求的C/N和C/I,设置边界处的接收信号强度Pcell=一93dbm19。假设每个小区的信道数为45,平均通话时长为1.76min/call，呼叫尝试率为0.9call/h，则每小区可提供的

16、话务负载为39.6爱尔兰，能为Cpt=(39.6*60)/(1.76*0.9)=1500subscribers/h的总移动单元数提供服务。首先，开始进行设计时先需要确定小区数的上界。从一(6)我们可得n1=17,dmax=3.53km。从(7)我们有匚=29400/150020。同时考虑覆盖和话务性能，我们选择n=max(n1,n2)=20。接着，来确定20个小区的安置，假设给出系统成本的标准化参数如下：Cceii=1000,Ca=5.0,Ct=10.0,Ctraf=0.5。基站和移动单元的参数选择如下9:对所有的小区k,gL8dBi,gU18dBi,PL30dBm,PU36dBm,gmk0d

17、Bi。根据24和25，我们得到了天线成本和其增益及发射机(或接收机)成本和其发射功率之间的逼近线性关系。假设给出关丁天线增益g的成本函数CA(g)如下：CA(g)=40+Ca-g0ggUMggU关丁发射功率P的成本函数CT(P)如下：CT(P)=60+Ct-P0PPuMPPu其中M是一个大的正数。我们根据上面的具体参数应用模拟退火算法SAEOM来求解EOM问题。冷却进度表的控制参数如下：初始接受率x=0.9,次数内目标=0.38*3*20*100,最大容许偏差=0.62*(3*m*n)，最大生成极限=4*Mub21。在HP-C180的UNIX系统上用C语言执行了这个算法。图3给出了一个初始可行

18、解(初始设计)。具有相同阴影的相邻网格组成一个小区。总系统成本为24349.68。图4给出了用SAEOM算法求出的最优解。这个最优解是在用不同的初始可行解运行程序10次后才获得的。最终设计fc(s)的邻近最优系统成本是20139.20。小区数进一步减少了6个。图5显示了收敛记录，即用SAEOM算法求解EOM问题的退火曲线。退火需要的平均CPU时间为34.65分钟。为了评估SA方法求得的解，我们把它与用Aarts和Korst15的本地搜索过程求得的最佳解和用随机生成过程获得的解比较。用本地搜索过程求得的最佳解为系统成本fc(s)=20452.4和小区数n=13。如成本函数(19)所示，每个小区的

19、固定成本Ccell决定总系统成本。这意味着成本有效设计应该有较少的小区数和每个小区较高的平均话务负载。图6和图7分别表示用SAEON和本地搜索方法求得的最佳解中的话务量柱形图。图8表示在小区数也是13这种情况下，随机生成过程获得的解的话务量分布。虚线和实心条分别代表每个小区能提供的话务负载和需要的话务负载。从图6-8，我们观察到用SAEON求得的逼近最优解在能提供的话务负载和需要的话务负载之间取得了好的折衷。与其它两个过程相比，每个小区的话务负载也呈均匀分布。如图4的最终设计所示，这个设计能满足覆盖要求，同时也努力用最小的小区数和最佳的小区安置适应非一致话务负载。天线增益和发射功率的逼近最优值

20、可从最佳解中获得。在最后一步，基站和移动单元的所有参数都要根据所在小区内具体的地形数据和覆盖特征进行调整。从上面两层获得的结果能满足覆盖的质量要求，但并不能提供每个小区的所有预期话务量。在最后一层，Gamst23技巧被用来确定要分配的信道数下界。然后进一步应用Dugue-anton20的信道分配过程去满足话务要求和避免十扰。B.SA算法的性能模拟退火方法SAEOM的性能研究分两个方面：解的质量和执行时间13。我们把SAEOM求得的次优解比作用本地搜索方法及随机生成过程获得的最优解。如表II和m所示的四种不同大小的问题都应用了这些方法。本地搜索算法是一种由Aarts15提出的贪婪算法，用本地搜索算法求得的解严重地依赖于初始解。计算时间的上界，即最差情况下的时间复杂度对很多问题而言都不可知1513。给定次数Npt对相同的问题用不同的初始值运行本地搜索算法，我们就得到了平均时间，平均CPU时间，最佳结