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

低成本的蜂窝移动通信系统：分层优化网络资源规划方法

摘要：本论文涉及蜂窝移动通信系统的设计优化和无线网络资源的规划。在移动网络规划中需要考虑的关键因数是成本。由于在大型的系统设计中必须考虑诸如系统性能，地形特征，基站参数和成本等很多因素，故分层优化规划方法(HOP)得到了应用。在此我们提出了设计蜂窝移动系统的三层优化方法。它能确定小区的数量，小区的安置和具体的基站参数以使整个系统的成本最小化并符合所要求的系统性能。我们把问题阐述为一个大型的组合优化模型，通过此模型确定小区的最优数量并选择最佳的基站位置。模拟退火方法被用来解决这个困难的组合问题。模拟结果证明了HOP方法在无线网络规划中的可行性和有效性。

关键词：蜂窝移动通信系统，最优化，无线网络规划，模拟退火

Ⅰ介绍

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

在决定任何通信系统经济上的可行性时成本都是一个关键因素。一个好的设计方法应该能在诸如网络性能标准，话务量和技术升级等因素中进行权衡，使成本最优化[9]。至今已有几个商用软件包被成功应用于移动蜂窝系统的网络规划中，如plaNET软件。但不管怎样，它们在规划中都没有直接包括金融上的规划或者考虑成本。另一方面，如Analysis STEM建模系统等的一些软件是决策支持工具以获得金融模型并提供蜂窝移动系统的成本分析。但在它们的成本模型中又没有考虑网络规划。这篇论文试图同时考虑成本和网络规划因数以填补这个缺口。这种唯一的组合对移动网络业务的供应商有极大的意义。它发展了最优化的网络规划方法，在系统设计上既使总的系统成本最小化同时又保证了好的系统性能。

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

规划模型是一个有难度的组合优化问题[13]。诸如分支界限法和动态规划法之类的优化算法不能在合理的时间内求得优化解[13]。因为牵涉到很多变量和复杂的约束，被用来解决大型组合优化问题的分解法和拉格朗日松驰法[14]可能也无法应用到规划模型中。在本论文中，一个建立在模拟退火(SA)基础上的算法被推导出来用于解决此问题，并在合理的计算量内求得了逼近的最优结果。

本论文的安排如下。在第二节，我们描述了蜂窝无线网络规划问题。第三节提出了解决这个问题的分层优化规划方法。在这一节还提出了组合优化模型和模拟退火算法。最后，在第四节给出了用HOP方法实现新加坡的蜂窝移动通信服务系统的网络规划的模拟结果。

Ⅱ问题陈诉

如图1所示，假如我们想要发展一个蜂窝移动通信系统为新加坡地区提供服务。整个地区将覆盖三种类型的土地：市区，郊区和农村。我们需要考虑非一致的话务分布：话务高峰通常在市中心，局部话务高峰在郊区中心。给定与覆盖性能相关的地区覆盖概率。边界处的定位概率和覆盖边界处接收信号强度的门限电平可以从覆盖概率和要求的信号强度，即载干比C/N[2]中推导得出。服务等级被设定为在忙时发起呼叫的阻塞概率。为满足业务要求在系统中采用了频率复用方案。

问题是怎样设计一个最优网络结构，即确定小区的数量，小区的大小，每个基站的位置和基站及移动单元的参数，以保证达到要求的性能目标，并使总的系统成本最小化。基站设备的成本是由机器设备及安装，天线，建筑物及铁塔和发射机及收信机等的成本决定的。

为了设计这样一个系统，必须考虑许多因素[1],[9]，需要作出许多不同层次的决策。涉及的主要因素如下：系统性能的详述，小区的覆盖，话务分布，地形，传播数据和系统成本因素。所有的这些因素相互影响，它们之间的复杂关系需要确定。由于系统的复杂性，在实际中网络规划过程是分层次的。规划活动包括：性能的说明和分析，从小区的数量及小区的位置方面来说的形式上的小区规划，和关于射频小区参数的设置及信道分配的详细小区设计。

Ⅲ网络规划和设计方法

我们提出了蜂窝移动通信网络设计的三层HOP方法。网络规划的三层结构如图2 所示。

在第一层，决定了小区数量的上界和相应的小区覆盖范围。HOP的输入参数如下：忙时的话务负荷，覆盖要求和整个服务区域的地形特征。并选择典型情况下的传播参数。任务为用最小的小区数量覆盖整个区域并满足平均话务需求。

在第二层，小区的数量和最佳的小区位置由大型的组合优化模型决定。模型的规划目标是使总的系统成本最小化，同时确保覆盖的质量，并努力符合非一致话务负载的要求。我们考虑到了不同用户的话务密度和不同类型服务区域的地形特征。如图1 所示，整个区域被划分为市区，郊区和农村。这些区域进一步被划分为更小的网格。环境结构方面的信息，用户密度和每个网格的平均俯角等都可以从地理信息系统(GIS)的数据库里得到。

详细规划在第三层进行，每个小区的具体参数，如天线模型及其增益，发射功率，天线高度和信道利用率等都在这一层设置。最后，把成本估计出来。

规划过程的总体系统性能很大程度上取决于不同层次上的不同活动和决策相结合的程度。如图2所示，决策必须在双向上相互调整和加强。

为了获得这个HOP方法和最优成本模型，需要考虑几个复杂的关系：覆盖率的要求，小区的覆盖范围和小区边界信号强度之间的关系[2]；传播损失和具体的人造建筑物及地形外表之间的关系[17]；设备和成本之间的关系。

传播损失可以用Hata传播模型预测[18]。Hata模型刻划了对于市区，郊区和农村等地形是准光滑或不规则的不同环境下无线传播的特性。在蜂窝系统的设计中这个模型广泛应用于预测不同环境下的路径损失[17][19]。

关于市区内基本传输损耗的Hata公式由下式给出：

Lu (db) = 69.55 + 26.26·log(f) - 13.82·log() - a()

        + [44.9 - 6.55·log()]·log(d)                         (1)

其中移动台天线高度的校正因子a()为：对于中小城市，a()=[1.1·log(f)-0.7]·-[1.56·log(f)-0.8]；对于大城市，a()=3.2·[log(11.75·)]-4.97，且频率f≥400MHz。

郊区和农村的传播损失Lsu和Lrqo由下式给出：

Lsu = Lu - 2·[log(f/28)] - 5.4                                 (2)

Lrqo = Lu – 4.78·[log(f)] + 18.33·log(f) – 35.94              (3)

Hata公式适用的范围为频率f在150 MHz到1000 MHz之间，基站天线高度介于30m和100m之间，移动台天线高度介于1m和10m之间，距离d的变化范围为从1km到20km。

在以下各节中，将给出HOP方法每一层的细节。

A.第一层：小区数量和小区大小的最初决定

首先，根据整个地区的覆盖性能和平均话务需求决定需要的最小基站数。为了确定系统设计中需要的小区数的上界，这个最小的基站数是在最差的情况下计算的的。在此我们取小区复用因子k=7，并给定地区覆盖概率和用户阻塞率。

把覆盖区域对移动话务量的要求考虑为在忙时由在此区域内的移动单元发起的所有呼叫尝试。它是根据覆盖区域内车辆的交通流量来预测的。给定预估的呼叫尝试率，该区域的话务负载就转化为忙时在此区域内的移动用户数。

我们定义以下符号：

    根据每个小区的信道数和给定的阻塞率得到的每个小区可以提供的话务量(用户数/小时)。

     整个服务区的总话务量(用户数/小时)。

    覆盖边界处的接收信号强度的门限电平。

     射频输出的峰值功率(dbW)。

      发射天线的输入功率(dbW)。

      接收天线的接收功率(dbW)。

, 分别为基站和移动单元的天线增益(db)。

,   分别为基站和移动单元的天线高度。

d        小区的平均辐射半径(km)。

S        服务区的总面积(km)。

首先考虑覆盖性能。从发射机到接收机射频功率的链接预算资源由下列方程给出[1]，[9]：

       =  +  – L(d) +                                  (4)

       =  – l                                               (5)

其中L(d)是传输损耗(db)，而l是绝缘体，组合器和射频电缆的复合损耗。

整个地区小区数量的上界由关于市区的Hata传播模型决定。关于郊区和农村的模型将在规划的下一层考虑。假设有下列条件[1]，[9]：= 10W，=30m，=3m，=12dBi，= 2dBi，l = 4dB，f = 900MHz。则关于传播损失L的公式(1)变为：

        L(d) = 123.73 + 35.22·log(d)                               (6)

为保证满足覆盖要求，我们有

            =  – 73.73 – 35.22·log(d) ≥                       (7)

即         log(d) ≤ log(d) = ( - – 73.73)/35.22                (8)

其中d是在大城市市区环境下最大的小区辐射半径。

那么，小区的最小数量为：

                                                      (9)

如果由业务量的分布情况来确定覆盖区图形，小区数量就由话务量决定[1]。在这种情况下，小区的最小数量为：

                                                          (10)

由此可以给出小区的最小数量为：

           n = max{，}                                           (11)

在最初的系统设计中，我们设n为小区数量的上界以得到成本有效的设计。在给定小区数量后，平均小区辐射半径由d = 决定。

B. 第二层：最优小区位置和小区数量及小区大小的确定

在这一层，考虑了整个区域的非一致话务分布。有关地形结构和环境的数据，话务密度，俯角均存储在每个网格中。一旦已知小区数量的上界，下一步就是要确定那一个网格属于那一个小区。进而就确定了小区的数量，不同的小区位置和小区大小。一般地，小区由相邻的具有相同分类的几个网格组成。在本论文中，建立了一个组合优化模型来确定那个网格属于那个小区和基站参数的最优值。我们考虑关于覆盖标准的“硬”约束和非一致话务需求的“软”约束，“软”约束可被放松且可通过补偿项合并入目标函数。模型的目标是使整个系统成本最小化。在轻话务量条件下，小区的数量可进一步减少。

1)经济优化模型的数学阐述：为了阐明这个问题，我们引入以下决策变量：

=   1，若网格i属于小区k   =  1，若小区k被网格占据

0，若网格i不属于小区k      0，若小区k内没有网格(节约一个小区)

进一步，我们定义如下：

           1， 网格i内的市区结构

 =   2， 网格i内的郊区结构

        3， 网格i内的农村结构

    网格i内的话务密度(用户数/小时)。

 n     总的小区数。

m         总的网格数。

          交换机房，硬件和安装的固定成本。

        基站内的硬件和安装的成本。

         考虑其增益的天线的成本系数。

         考虑其发射功率的发射机和接收机的成本系数。

         小区k内的基站发射功率，且，其中和分别是其相应的上界和下界。

  分别为小区k内的基站和移动单元的天线增益，且其中和分别是其相应的上界和下界。

  分别为小区k内的基站和移动单元的天线高度。

       小区k的辐射半径。

       网格的范围。

 关于蜂窝移动通信网络的经济优化模型(EOM)阐述如下：

 EOM：

min =+·(+·+·)                (12)

受约束于

＋＋－      k=1,2, ···,n                 (13)

                     k=1,2, ···,n                 (14)

  k=1,2, ···,n; i,=1,2, ···,m;i   (15)

                           i=1,2, ···,m                  (16)

                    k=1,2, ···,n                 (17)

       (-1)  0                k=1,2, ···,n                 (18)

        - 1                   k=1,2, ···,n                 (19)

         对所有i和k，,的值为1或0                           (20)

在EOM模型中，目标函数(12)的目的是最小化总的系统成本。约束(13)用来确保覆盖性能。约束(14)保证设计满足非一致话务量的要求。约束(15)－(17)确保小区由具有相同结构且彼此相邻的网格组成。约束(18)－(20)给出了和之间的关系，即当＝0时，＝0；当0时，＝1。

信号传播损耗通过Hata预测模型进行计算。根据以下条件[1],[9]：= 10W，=30m，=3m，=12dBi，= 2dBi，l = 4dB，f = 900MHz，我们有：

     ＝ а＋35.22·log()                               (21)

其中当小区k分别覆盖市区、郊区和农村区域时，а＝123.73,113.79和102.22。

2)用模拟退火算法求解EOM模型：EOM模型是个有难度的组合优化问题，因为在模型中有很多变量和复杂的约束[13]。没有一种优化算法能在合理的时间里求得最优解。在文献[15]和[16]中报导的建立在模拟退火(SA)基础上的算法被用来解决这个问题，并在合理的时间内求得了逼近最优解。

对于求解NP完全组合问题的逼近解来说模拟退火是种好方法[13]。它已被成功应用于某些领域，如计算机的优化设计[16]，图象处理，信道分配[8][20]和规划布局问题。算法采用一种迭代方案，它模拟物理退火过程：加热固体直到其融化，然后花最少的能量冷却它使其结晶至基态。

为了用模拟退火过程解决EOM问题，需要考虑下面四个方面：配置空间，成本函数，相邻结构和冷却进度表。

a)配置空间：对于EOM模型，配置空间S是所有满足覆盖约束(13)和其它约束(15)-(20)可行解{}的集。

b) 成本函数：在实际的系统设计中，首先要考虑覆盖性能。对于给定的小区数量，由于非一致话务分布的存在，如果要满足覆盖和话务两者的要求，没有几个可行解可被求得。因而引入话务约束(14)到目标函数，目标函数就从(12)变为最小化基站的总设备成本和破坏话务负载后引起的总补偿，即：

        (22)

其中函数[x]=max(0,x)。

因为(12)中的系统固定成本不影响EOM模型的最优解，故在成本函数中不再包含这一项。

c) 相邻结构：用N(s)表示的解s的邻域由在满足约束(15)-(17)时，移动网格k从当前小区i到相邻小区j时产生。

d) 冷却进度表：决定初始温度t以确保可接受转换与提议转换之比的特定接受率χ接近1[15]。这可以通过从一个小的正数t出发，迭代地变换它直到达到接受率χ来得到。

Huang[21]用在某一温度的成本分布的标准偏差来决定下个温度的减小量，并提出下面的温度递减规则：

                        (23)

其中是在温度t的成本分布的标准偏差；是发生在两个连续温度t和t之间的平均成本的减少量。为保持准平衡，当。的典型值0.7。

在某个温度平衡意味着齐次马尔可夫链的固定成本分布的建立。Huang假设了一个关于平衡的成本的正态分布，它们的平均值和标准偏差都由马尔可夫链估计而来。他们提出了完成固定分布检查的平衡条件：一旦平衡建立，其成本限制在范围内可接受的转换次数的比率将达到一个稳定值μ＝erf()，其中介于平均成本(它被称为次数内)和可接受转换总次数之间，erf(x)是x的误差函数[22]。的典型值为0.5，从而可得μ＝erf()＝0.38。两个平衡参数，一个目标次数内和一个最大容许偏差极限，都根据问题的大小建立。如果次数内在容许偏差次数超过最大极限值以前达到了目标值，我们就认为保持了平衡[21]。

对于我们的EOM问题，我们设置次数内＝0.38*(3*m*n)和最大容许偏差=   0.62*(3*m*n)。

我们说取得了最后温度，如果在那个温度的马而可夫链的整个轨迹里，最大和最小成本的差值等于在那个温度的一次可接受转换里的成本的最大一次变化。

下列伪代码程序描述了解决 EOM问题的模拟退火过程(SAEOM)。

解决EOM问题的模拟退火过程(SAEOM)：

Begin

  初始化()；

  k := 0；

  s := ；

  Repeat

    Until 平衡达到  do

    Begin

      从N(s)产生；

      If  ()  then  s :=

      Else

      If  exp((f(s)-f())/t) > random[0,1)   then  s :=

    End；

    k := k+1；

    计算t；

  Until 停止准则成立

End

与Kirpatrick[16]提出的模拟退火技巧相比，这个用Huang方法[21]的新SA技巧能通过退火过程动态调节马尔可夫链的长度达到平衡，退火需要的CPU时间也大大地下降了。

C.详细规划和准确的成本估计

在这一层，确定每个小区内的基站位置，诸如天线塔高度，天线增益和发射功率等参数都进一步根据每个小区的地形不规则性的特征，表面覆盖和环境进行调整。从上面两层得到的结果已满足了覆盖性能，并试图满足话务要求。但不管怎样，在某些小区的话务过载可能仍然存在。在这一层，可以用Hale[6]和Gamst[23]的信道分配策略来提供信道数的下界。把在[7][8][20]中提到的固定和动态信道分配策略应用于蜂窝系统的网络规划以提供足够的容量来为预期的话务量服务，并保持无线干扰到最小限度。

如果系统性能在调整后达到了要求，最后的系统设计就确定了，也就可以估计出蜂窝系统的成本。否则在这一层的结果将反馈到第一层和第二层。然后重复整个过程。在这种情况下，可能需要增加小区的数量以满足规定的服务质量。

Ⅳ模拟结果

A.HOP模型的应用

分层优化方法被用来设计提供如图1和图3所示的为新加坡地区提供服务的蜂窝系统。在我们的研究中使用了模仿新加坡地形，话务分布和人口的数据。整个地区被分为三种类型和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/150020。同时考虑覆盖和话务性能，我们选择n = max(,) = 20。

接着，来确定20个小区的安置，假设给出系统成本的标准化参数如下：=1000，=5.0，＝10.0，＝0.5。基站和移动单元的参数选择如下[9]：对所有的小区k，。

根据[24]和[25]，我们得到了天线成本和其增益及发射机(或接收机)成本和其发射功率之间的逼近线性关系。假设给出关于天线增益g的成本函数如下：

         =    40+Ca·g       

                   M              

关于发射功率P的成本函数如下：

            =    60 + Ct·P      

                       M              

其中M是一个大的正数。

我们根据上面的具体参数应用模拟退火算法SAEOM来求解EOM问题。冷却进度表的控制参数如下：初始接受率χ＝0.9，次数内目标＝0.38*3*20*100，最大容许偏差= 0.62*(3*m*n)，最大生成极限＝4*MUB[21]。在HP-C180的UNIX系统上用C语言执行了这个算法。

图3给出了一个初始可行解(初始设计)。具有相同阴影的相邻网格组成一个小区。总系统成本为24349.68。图4给出了用SAEOM算法求出的最优解。这个最优解是在用不同的初始可行解运行程序10次后才获得的。最终设计fc(s)的邻近最优系统成本是20139.20。小区数进一步减少了6个。图5显示了收敛记录，即用SAEOM算法求解EOM问题的退火曲线。退火需要的平均CPU时间为34.65分钟。

为了评估SA方法求得的解，我们把它与用Aarts和Korst[15]的本地搜索过程求得的最佳解和用随机生成过程获得的解比较。用本地搜索过程求得的最佳解为系统成本fc(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算法时，解的质量和运行时间之间的折衷。成本为的最终解的质量由如下定义的相当误差ε决定：

          ε=

其中是曾经求得的最佳值。对于大型案例的广泛研究表明一个具有良好质量的解能通过降低λ和增加χ来得到。

Ⅴ结论

本论文研究了对于蜂窝移动通信网络规划的经济优化建模问题。提出了一个分层优化规划方法，它既考虑到覆盖的要求又考虑到话务负载。发展了一个组合优化模型去确定合适的小区数量和选择最佳的基站位置。一个建立在改进的模拟退火基础上的算法被用来求解这个模型并取得了逼近最优解。大型的复杂移动通信系统的资源管理和网络规划的最优化技术的发展和应用将是我们未来的研究课题。