（通信与信息系统专业论文）移动通信网络规划中用多目标优化算法进行自动基站布置的研究与实现.pdf

东北大学硕士学位论史 摘要 移动通信网络规划中用多目标优化算法进行自动基站布置的研究 与实现 摘要 随着我国移动通信事业的快速发展，移动用户迅猛增长，移动通信网络不断 升级、延伸、扩容，这就使得无线网络规划问题显得日益突出。如何在保证网络 服务等级( q o s ) 的前提下尽可能的降低成本，是移动通信运营商提高自身竞争力的 关键，也是本文的重点所在。无线网络中的基站不仅建设和维护成本极高，而且 对移动网络的服务质量有决定性的影响。过去，基站的位置主要是由工程师依靠 经验和实地测试来选择。显然，这种经验往往与实际的最优配置相差甚远。近年 来，数字地图的出现为基站的布置提供了有利的辅助信息，但目前还主要是用来 进行覆盖分析和干扰预测。本文将数字地图引入到移动网络规划中来，实现了更 科学可靠的资源配置，并解决了规划中的自动基站布置问题。 在介绍了移动通信系统设计的基本概念和所涉及的理论之后，定义了自动基 站布置问题的数学模型。研究了多目标优化问题的特点和解决优化问题的一些经 典算法。鉴于遗传算法在求解优化问题上的诸多优点，本文将一种高效的多目标 优化进化算法d c m o g a d e s 应用到无线网络规划中的自动基站布置问题中，并针 对自动基站布置问题对原算法进行改进：如在研究d c m o g a d e s 的基础上，本文 提出有向的迁徙算子，在保证计算复杂度的同时加快算法的收敛速度，能更快找 到最优解，并避免出现早熟；使用马尔可夫过程的原理描述遗传算子，改进交叉 和变异操作。仿真结果表明该算法较之目前已有的一些网络规划算法，能够快速 逼近目标空间的p a r e t o 域，并在该域中分布更均匀。同时，该算法收敛速度更快， 且经一次运行便可提供多个合理的基站分布候选方案。这些优点在实际工程规划 中有着极其重要的意义。论文在最后结台现场的实际要求，给出了一个以数字地 图为基础，应用d c m o g a d e s 多目标优化算法的网络规划软件的设计和实现。 关键字：网络规划自动基站布置多目标优化遗传算法d c m o g a d e s 东北大学顺：l 学位论文 a b s t r a c t r e s e a r c ha n d i m p l e m e n t a t i o no f a u t o m a t i c a l l yp l a c i n g b a s e s t a t i o n si nm o b i l en e t w o r k sp l a n n i n ga p p l y i n gm u l t i p l e o b j e c t i v eo p t i m i z a t i o na l g o r i t h m s a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to fc h i n e s ec o m m u n i c a t i o ni n d u s t r ya n dt h ee x p l o s i v e i n c r e a s eo fc h i n e s em o b i l e s u b s c r i b e r s ，m o b i l e c o m m u n i c a t i o nn e t w o r k s k e p t u p g r a d i n g ，w h i c hm a k e si t ah i g h l i g h tt o i m p l e m e n tt h en e t w o r kp l a n n i n g h o wt o m i n i m i z et h ef i n a n c i a lc o s to ft h ei n f r a s t r u c t u r ew i t h o u ts a c r i f i c i n gq o sa r en o to n l y t h ek e yt o p i co ft h es u r v i v a lo fm o b i l es e r v i c ep r o v i d e r , b u ta l s ot h ek e yt o p i co ft h i s t h e s i s t h eh i g hc o s to fb a s es t a t i o n si t s e l fa n dt h ei n f l u e n e eo ft h e i rp l a c e m e n tt ot h e q u a l i t yo fs e r v i c ec o n f i r mt h ei m p o r t a n c eo ft h ep r o b l e mi n t h en e t w o r kp l a n n i n go f h o wt od e t e r m i n et h en u m b e ro fb a s es t a t i o n sa n dt h e i rs i t e s i nt h ep a s t ，t h i st a s k d e p e n d e d o n e x p e r i e n c e so fe n g i n e e r sa n d f i e l dt e s t st op l a c eab a s es t a t i o n a p p a r e n t l y , t h e s e e x p e r i e n c e s a r en o ts c i e n t i f i ca n d ，o f t e n ，t h e r ee x i t sas h a r p g a pb e t w e e n e x p e r i e n c e sa n d t h er e a lw o r l d i nr e c e n ty e a r s ，t h ea p p e a r a n c eo f d i g i t a lm a pb r i n g sn s an e we r at oi m p l e m e n tc e l lp l a n n i n g h o w e v e lt h em o s tf r e q u e n tu s e so fd i g i t a lm a p s a r et oa c h i e v ec o v e r a g ea n a l y s i sa n di n t e r f e r e n c ep r e d i c t i o n i nt h i st h e s i s ，d i g i t a lm 印 w a si n t r o d u c e di n t om o b i l en e t w o r kp l a n n i n g ，a n dt h ea u t o m a t i cb a s es t a t i o np l a c e m e n t i nm o b i l en e t w o r k sw a ss o l v e d t h eb a s i cm o b i l ec o m m u n i c a t i o ns y s t e md e s i g n i n gc o n c e p t sa n d i t sr e l a t e d t h e o r i e sw e r ei n t r o d u c e d t h em a t h e m a t i c a lm o d e lo fa u t o m a t i cb a s es t a t i o np l a c e m e n t w a sd e f i n e d a n dt h ec h a r a c t e r so ft h em u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e mw e r e d i s c u s s e d t h eg e n e t i ca l g o r i t h m sw e r ea p p l i e dt os o l v et h ep r o b l e ms i n c et h e r ea r e m a n ya d v a n t a g e si nt h e m a m u c he f f i c i e n tm u l t i p l eo b j e c t i v ee v o l u t i o n a r ya l g o r i t h m ( m o e a ) ，d i s t r i b u t e dc o o p e r a t i o nm o d e lo fm u l t i o b j e c t i v e g e n e t i ca l g o r i t h mw i t h d i s t r i b u t e de n v i r o n m e n t a l s c h e m e ( d c m o g a d e s ) ，w a s u s e da n d i m p r o v e d a c c o r d i n gt ot h ep r a c t i c a lp r o b l e m f o re x a m p l e ，a r e rs t u d y o fd c m o g a d e s ，s o m e n e wo p e r a t o r s ，s u c ha s m i g r a t i o no p e r a t o r , w e r eb r o u 【g h t f o r w a r dt o e f f e c t i v e l y i i 东北大学硕+ 学位论文 a b s t r a c t a c c e l e r a t et h e c o n v e r g e n c e w i t h o u tl e a d i n gt o p r e m a t u r ec o n v e r g e n c e m a r k o v i a n p r o c e d u r ew a si n t r o d u c e dt oc l e a r l y d e s c r i b et h eg e n e t i c o p e r a t o r so fc r o s s o v e ra n d m u t a t i o n s i m u l a t i o nr e s u l t ss h o w e dt h a ts u c ha l g o r i t h mh a sm u c hm o r ea d v a n t a g e so n c e l lp l a n n i n gp r o b l e m i tc a na p p r o a c ht h ep a r e t of r o n ta sn e a ra sp o s s i b l e ，a n dc a l l s p r e a dt o w a r dt h e 、，v h o l ef r o n t 。f u r t h e r m o r e ，t h i sa l g o r i t h mn e e d sl e s sc o m p u t i n gt i m e ， a n dc a np r o v i d em a n yr e a s o n a b l es o l u t i o n sa ta s i n g l et i m er u n a l lt h i sm a k e s s e n s ei n f i e l dp r a c t i c e w h a ti s m o r e ，t h ed e s i g n a n di m p l e m e n t a t i o no fam o b i l en e t w o r k p l a n n i n gs o f t w a r ec o m b i n e d t op r a c t i c er e q u i r e m e n t sb a s e do nt h ed c m o g a d e sa n d d i g i t a lm a p w e r ei n t r o d u c e d k e y w o r d s ：m o b i l en e t w o r k sp l a n n i n g ，a u t o m a t i cb a s es t a t i o np l a c e m e n t ，m u l t i p l e o b j e c t i v eo p t i m i z a t i o n ，g e n e t i ca l g o r i t h m s ，d c m o g a d e s i i i 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或 撰写过的研究成果，也不包含本人为获得其他学位而使用过的材料。 与我共同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 本人签名： 日期： 房捩 跏吾冉j j 月勘闰 东北火学顶十学位论文第一章z 引言 1 1 研究背景 第一章引言 帚一早j l函 随着经济社会的快速发展，移动通信在人们日常生活中的地位日益提高。目 前，移动通信是发展最快、应用最广和最前沿的通信领域之一。随着我国成功加 入世贸组织，我国的电信企业也必将面l | 缶着月趋激烈的竞争。为了应对这种严峻 的挑战，我国对电信体制进行了大幅度的改革。目前，主要的电信运营商有中国 电信，中国网通，中国铁通中国移动和中国联通。在这些电信业务运营商中能 够提供移动通信服务的运营商主要有两家，即中国移动通信公司和中国联通公司。 不久的将来，会有更多的电信企业获得移动运营牌照，运营公司之间越发激烈的 竞争将不可避免。 从现在的情况来看，尽管国际电信市场正在经历着比较大的衰退，但对于我 国的电信市场来说，发展的空间依然巨大，特别是移动用户不断增长，这必然推 动着移动通信网络的建设速度越来越快。移动网络不断的以城市为中心向周围延 伸辐射，同时城市内部的移动网络也在不断的扩容改造。而如何以较低的成本建 设和维护一个服务质量得到保证的网络无疑将成为各个运营商能否在市场竞争中 取得优势和得以生存的重要因素。 我国的移动通信的发展起步比较晚，大多采用了国外已有的成熟技术和设备， 自主产权的技术和设备很少。而在相关的领域内的研究也大大滞后，从而导致了 我国移动通信网络运营成本的加大。这种情况不仅存在于较早的模拟移动通信系 统的建设中，而且也同样存在于第二代移动通信系统的建设中。在以往的移动网 络建设初期，由于大量采用设备制造商的设备，而又没有比较合适的规划工具， 因此，网络建设的初期规划常常是盲目和不可靠的。通常是由规划人员和工程师 依靠经验来完成基站的设置，频率的分配以及干扰的分析，并且在很大的程度上 受设备商的影响。这种规划方法不仅规划周期长，而且通常不能够得到最优的结 果，造成网络建设成本的增加并使以后网络的运行和维护更加困难。 在国外，移动网络智能规划系统的研究与开发受到了广泛的重视。显然移动 网络的规划属于多目标组合优化问题。对于这个最优化问题，国外进行了大量的 东北大学硕士学位论文第一章弓言 研究，尤其是欧洲国家的一些学者，提出了多种算法，并在算法基础上实现了一 些商用的规划设计软件。目前主流的用于网络规化的相关软件有：l u c e n t 公司 的c e 4 软件，e r i c s s o n 公司的e e t 软件，s a f c o 公司的w i z a r d 软件和 p l a n n e t 等大型规划软件。这些软件都是根据地理数据l d m ( 线形地物模 型) ，d e m ( 数字高程模型) ，d o m ( 地面覆盖模型) ，b d m ( 建筑物分布模型) 等，进行 参数计算，从而规划网络，提高小区的覆盖面积，消除盲区。但是，这些商用规划软 件对于网络规划所需要考虑的各个方面各有不同的侧重，不仅价格昂贵，而且不 能够很好地适应国内的业务模型和运营要求，实际应用中都有很明显的缺陷。因 而，这些国内外已有的规划软件在很大程度上都没有被实际应用，往往作为了工 程设计人员的方案验证工具。而国内的一些商业公司开发的网络规划系统功能单 一，不能有效地进行实际应用。 因此，开发出一种能够有效应用于实际工程的移动网络规划系统就具有非常 重要的意义。本题目，“蜂窝移动通信网络中的小区规划”，由联通公司提出，东 北大学网络与通信中心承担，并由李满林博士带队进行攻关。本文就其中的自动 基站布置问题根据实际工程需要，将移动网络建设的各种成本因素( 如基站设备 成本，基站地面建设成本，频率成本等) 和服务质量因素( 如区域的面积覆盖率， 业务覆盖率等) 予以综合考虑，应用多目标优化算法求解，并在此基础上设计了 一种智能规划软件。 1 2 移动通信发展史 移动通信是指通信双方或至少一方在运动中所进行的信息交换。移动通信系 统的发展经历了模拟到数字的发展过程。从最早的无线电系统，到即将到来的3 g 时代，到含苞待放的4 g 技术，移动通信技术发生了根本性的变化。总体上看，移 动通信可以大体划分为四代，即第一代移动通信( 模拟移动通信) ，第二代移动通 信( 数字移动通信) ，第三代移动通信系统( 宽带移动通信) 和第四代移动通信( 多 媒体移动通信) 。每一代的技术都是基于前一种技术的基础之上，而每一种技术上 的突破都是为了获得更好的通信质量和系统容量以及频谱利用率。 1 2 1 早期的移动无线电话 在1 9 4 6 年，第一个公众移动电话服务在美国出现。当时服务覆盖了美国的2 5 东北大学硕j 学位论文第一章引言 个主要的城市。采用了大区制，每个系统使用一个大功率的发射机和发射塔，覆 盖半径大约为5 0 公里。由于当时的滤波器不完善，因此使用了半双工的通信方式， 每路话音占用1 2 0 k h z 的带宽。 1 , 2 2 第一代移动通信系统 6 0 年代，a t & t 的贝尔实验室和其他的通信公司一起发展了一种全新的蜂窝 无线电话技术。它的基本概念是把整个覆盖范围划分成小的单元，每个单元复用 频带的一部分以提高频带的利用率，其代价是更多的系统结构开销，而获得了更 大的系统容量和频谱利用率。八十年代，美国第一个模拟蜂窝电话系统a m p s ( 高 级移动电话业务) 在美国建成。与此同时其他的一些模拟蜂窝电话系统也在世界 各地相继出现，如t a c s ，c n e t 以及n t t ( 北欧移动电话) 等。这些不同制式的 主要区别在于所使用的频段，信道间隔以及调制参数上。各个系统之间不能互通。 但在当时的情况下各个系统依然能够提供比较好的通信质量和容量。 第一代蜂窝移动网的结构如图1 1 所示。 圈1 i第一代蜂窝移动网的结构图 f i g 11a r c h i t e c t u r eo f t h ef i r s tg e n e r a t i o nm o b i l es y s t e m 东北大学f i j i ：t ：学位论文 1 2 3 第二代移动通信系统 第二代移动通信系统是在8 0 年代开发的，第一批系统于9 0 年代初投入商用。 数字蜂窝系统在许多方面都优于模拟系统。最引人之处是由于能更有效地利用无 线频谱，提高频带利用率。另外，数字传输不仅可以传输语音，而且可以传输数 据信息，支持短消息业务和e m a i l 。同时数字技术也提高了语音和数据传输的保密 性。 第二代移动通信技术的主要制式有g s m ( 全球移动通信系统) ，c d m a i s 一9 5 ， p d c ( 个人数字蜂窝) ，d c s 一1 8 0 0 ( 1 8 g 频谱上的g s m ) ，t d m a i s 1 3 6 ( 最初被 称为d a m p s ) 。 g s m 是最早投入商用的数字蜂窝网络。该标准最早由欧洲提出，e t s i 一直负 责g s m 的标准化工作。它是由网络交换子系统( n s s ) ，基站子系统( b s s ) ，操 作维护中心( o m c ) 和移动台四大部分组成。 c d m a ( i s - 9 5 ) 是一种通过使用全部无线频带来提高容量的数字通信技术， 每一个呼叫都面对一个独有的代码。目前该标准主要应用于北美和韩国。 p d c ( 个人数字蜂窝) 系统，虽然在1 9 9 4 年才推出，而且仅限于在日本使用。 该标准最初称为j d c ( 日本数字蜂窝) 。 1 2 4 第三代移动通信系统 由于第一代和第二代移动通信系统都没有统一的国际标准。当前运行的移动 蜂窝网络有许多是不相兼容的。8 0 年代后期，i t u 提出要建立一种在世界范围内 具有一致频谱和无线接口标准的新一代移动通信系统。i t u 将该系统的标准定义为 i m t - 2 0 0 0 。虽然，i m t - 2 0 0 0 仍然是一个蜂窝式网络，但它的目的是将各种不同的 服务覆盖区宏小区，微小区和微微小区地面蜂窝系统，无线接入系统以及卫 星通信系统都综合在一起，从而能够实现真正的全球漫游和全球服务。 同时i m t - 2 0 0 0 将为多种业务的融合和分配提供一个平台，无论他们是移动业 务还是固定业务，语音业务还是数据业务，电信服务还是计算机应用服务。在i t u 的建议里，主要提供的业务有： ( 1 ) 语音业务：典型的对称业务，上，下行链路的信息速率都是1 6 k b i t s ， 属于电路交换。 ( 2 ) 短消息：数据速率为1 4 k b i t s ，属于分组交换。 东北大学硕士学位论文 第一章日l 言 ( 3 ) 交换数据：属于电路交换业务。上，下行数据速率都是6 4 k b i t j s 。 ( 4 ) 非对称多媒体业务：分为中速和高速两种，中速上行6 4k b i t s ，下行 3 8 4k b i t s ：高速上行1 2 8k b i t s ，下行2 mb i t s 。 ( 5 ) 交互式多媒体业务：上下行数据流量相等。用于音频，视频应用传输， 电路交换，1 2 8k b i t s 。 m t - 2 0 0 0 的主要含义为，工作在2 0 0 0 m h z 频段上，能够承载的数据传输速率 在2 m b i t s 。 1 9 9 9 年，在芬兰首都赫尔辛基通过了“第三代移动通信系统( i m t - 2 0 0 0 ) 无 线接口技术规范”建议州t r s p c 。该规范建议将无线接入技术分为c d m a 和 t d m a 两大类。最主要的三类规范建议为w c d m a ，c d m a 2 0 0 0 和t d s c d m a 。 其中t d s c d m a 是中国提出的并被采用的第一个i t u 标准。 3 g 系统给人们展示了一个美好的通信前景，但仍然面临很多的技术难题，这 些难题有些是蜂窝系统固有的，有些是3 g 系统所特有的。第一个障碍就是多径衰 落，这是所有无线系统都存在的。第二个障碍是远近效应问题，由于3 g 中采用码 分多址技术，各移动台发出的信号在时域和频域都相互重叠，所以这种相互干扰 更加严重。第三个障碍是多址干扰。采用码分多址，是通过不同的伪随机码的正 交性来区分不同的信道，但由于这种正交性的不完备，各信道之间的干扰不能够 完全消除。因而c d m a 系统是干扰受限系统，本小区和邻近小区用户的干扰决定 系统的容量和性能。另外，从资源利用的角度来看3 g 要兼容一代和二代系统。为 了解决这些主要问题，很多的关键技术在3 g 中得到了应用，有的还在进一步的研 究之中。就目前的研究状况而言，关键的技术主要有( 1 ) 多载波调制技术；( 2 ) 多址技术 ( 3 ) 软件无线电( s o f t w a r er a d i o ) ；( 4 ) 智能天线；( 5 ) ，功率控制；( 6 ) 多用户检测：( 7 ) 切换技术等。 尽管众多的研究集中于3 g 技术的成熟和商用上，广大运营商不得不面对的另 一个问题是如何从现有的2 g 网络向3 g 网络平滑过度。这一过程里有很多需要考 虑的因素。一是成本，二是技术的成熟和可靠性，三是操作的灵活性。总体来说， 由2 g 网络向3 g 网络过度的途径主要有三种：第一，由现有g s m 网络向g p r s 网络转化，再进一步过度为3 g 网络。第二，由现有的窄带c d m a ( i s 一9 5 ) 升级 到c d m a l x ，再到c d m a 3 x 。第三，完全建立一个新的t d s c d m a 网络直接进 入3 g 时代。 就我国的具体情况来说，上述三条途径都不可避免。中国移动已采用g s m 一 一g p r s w c d m a 的路线。中国联通也已经初步建立c d m a 网络，必然会走 东北大学瑚l 学位论文 第一章0 l高 i s 一9 5 c d m a l x c d m a 3 x 的路线。除了上述两家移动运营商，国家信息产 业部必将在将来继续发放运营牌照。从趋势上，新的移动牌照有可能与我国的 t d s c d m a 标准捆绑发放。 可以预见未来的中国的3 g 服务将是多个标准共存的状态。 1 2 5 第四代移动通信系统 当3 g 试验如火如茶的时候，4 g 技术已经问世。目前包括中国在内的多个国 家及实验室，如：a t t 实验室，都正在研究4 g 技术。在今年1 1 月2 0 日由中国 科技部等部门和欧盟委员会信息社会总司联合举办的“未来移动通信国际论坛暨 中国一欧盟b e y o n d3 g 研讨会”上，中国第三代移动通信系统研究开发项目总体 组组长尤肖虎称：中国在第三代移动通信系统刚剐进入实施阶段时，国家8 6 3 计 划就启动面向第四代的移动通信计划。中国希望在一项新技术发展的初期，就介 入研究和开发，以能够真正获得核心的知识产权，对国际标准化组织作出贡献。 第四代移动通信将以几项突破性技术为基础，如一些光纤产品公司用来提高 网络主干带宽的技术。4 g 无线频率的使用将比2 g 和3 g 有效得多。按照最乐观的 情况估计，这种有效性可以让更多的人使用与以前相同数量的无线频谱做更多的 事情，而且速度相当快。下载速率有可能达到5 m b p s 到1 0 m b p s 。除了高速信息传 输技术外，它还包括高速移动无线信息存取系统、移动平台技术、安全密码技术 以及终端间通信技术等。此外，3 g 主要是以c d m a 为核心技术，4 g 则以正交多 任务分频技术( o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x e r ；o f d m ) 最受瞩目。这些 技术仍有许多问题待解决，不过部份标准化制订的工作已经接近尾声而即将商用 化，但若要应用在移动通信领域仍需时日。 第四代移动通信系统开发成功后，使用手机便能够同世界上的任何地方进行 电视电话等图像和声音的通信。4 g 移动电话不仅音质清晰，而且能进行高清晰度 的图像传输，预计用途将十分广泛。第四代移动通信的特点将主要有以下几个： 1 以移动数据为主。2 传输速率比现在高1 0 0 0 倍，达到1 0 0 兆。3 发射功率比现 在降低1 0 一1 0 0 倍，能解决电磁干扰问题。4 支持手机互助功能，采用可穿戴无 线电。5 支持更丰富的移动业务，包括高清晰度图像业务、会议电视、虚拟现实 业务等，使用户在任何地方都可以获得任何所需的信息服务。 过去的移动通信技术全球不统一，比如第二代有g s m 、c d m a ，而第三代技术有 c d m a 、c d m a 2 0 0 0 和t d s c d m a 等。不同标准对用户使用造成一定不便。未来第四 东北大学删一l 。学位论文第一章q l苦 代移动通信要求实现全球统一的标准，真1 ：f 实现一部手机在全球的任何地点都能 实现通信。因此，广泛充分的国际合作是实现这一目标的前提。 1 3 移动蜂窝网络规划在理论与实践中的发展 从整个移动通信发展的历史和现状可以看出，我国在该领域上起步较晚，虽 然现在我们f 在努力迎头赶上，但在一些关键性的技术上仍受制于人，对很多领 域没有进行深入的研究。因此对于移动通信运营商来说，运营成本不可避免地加 大。特别是在我国的移动通信网络建设初期，由于没有比较系统和科学的规划， 造成了网络建设成本的增加。而反观国外，众多学者很早就开展了网络规划领域 的系统研究。 移动通信网络的规划是包含众多领域的系统工程。从电磁波的传播特性到设 备成本的控制，不仅需要深入了解各种移动网络的运行规范，同时也要考虑运营 商的需求。特别是蜂窝式移动网络被采用以后，网络规划问题更加复杂化。由于 地形及其他因素的影响，必须充分考虑场强覆盖的需求，因此也就是需要一种方 法来设置基站的位置满足场强覆盖。这种基站位置的规划是网络规划最初需要解 决的内容。随着蜂窝移动网络用户的增长。系统容量问题又被提出。如何有效利 用有限的频率资源成为网络规划的主要解决目标。 在移动通信网络规划中，基站的布置位置和数目直接影响了网络的覆盖范围和 信号质量，又因其价格昂贵直接影响整个网络的投资成本。在网络规划中基站数 目和位置的选择是一个相当重要的问题。 随着人工智能领域的不断发展，t h o m a sf r i t s c h 提出了采用模拟退火算法 ( s i m u l a t e da n n e a l i n g ) 实现的自适应基站定位算法( a d a p t i v eb a s es t a t i o np o s i t i o n i n g a l g o r i t h m ) 。随后，k u r tt u t s c h k u 提出了集成化的蜂窝网络规划方法( a ni n t e g r a t e d a p p r o a c h t oc e l l u l a rn e t w o r kp l a n n i n g ) ，以业务需求点( d e m a n dn o d e s ) 概念为核心， 考虑了用户行为( s u b s c r i b e rb e h a v i o r ) ( 主要是静态的入口模型) ，电波传输( 包括 接收电平和干扰) 以及资源分配( 无线资源) 。 7 0 年代，遗传算法诞生。它作为一种现代启发式( m e t a h e u r i s t i c s ) 算法，因具 有很多优点而越来越受到广泛关注。c a l e g a r ip 采用经典的二进制表示法将遗传 算法应用到无线网络优化中。j i nk h 引入了实数表示方法来描述基站位置，提出 了相应的遗传算子，并考虑了成本控制。我们对j i nk h 的算法做了进一步的改进， 综合考虑了在网络规划实际工程中的多种规划目标和要求。虽然考虑到了多个目 东北人学碳j i j 学位论义 第一章引吉 标的优化，然而所采用的将多个目标加权求和转化为单目标的方法具有一定的局 限性，它不能找到非凸p a r e t o 最优域( 见后文) 中的解。因此本文采用了多目标 优化算法d c m o g a d e s ，并对算法进行了改进。 在2 0 0 2 年，中国通信学会将移动网络的规划问题列入我国移动通信领域的四 大难题之一，我们现在所取得的成果只还是整个网络规划问题的一小部分，希望 会有越来越多的人能够加入到这个行列中来，相信不久的将来网络规划这个难题 一定能够攻破。 1 4 论文结构 本文共分为六个部分。第二章移动蜂窝网络规划，主要介绍了移动蜂窝网 络规划所涉及的基本概念和理论，并介绍了传统的规划过程。第三章移动蜂 窝网络规划中的自动基站布置问题，首先定义了基站布置问题，鉴于它是一个多 目标优化问题，在第三章中本文介绍了多目标优化问题的定义和特点，同时指出 了广泛使用的一些算法( 如：加权方法) 的不足。第四章应用多目标优化算 法求解自动基站布置问题，讲述了遗传算法的原理与基本的实现方法，针对本文 所要解决的问题引入了d c m o g a d e s 多目标优化算法，详细介绍了如何应用 d c m o g a d e s 来求解自动基站布置问题，给出了对原算法的改进和仿真结果，并 将该算法与其它网络规划算法做了比较。第五章移动蜂窝网络规划软件的设 计与实现，介绍了三维数字地图，及应用数字地图进行自动基站布置的软件的设 计和实现。最后对全文做出总结并对未来研究方向做出展望。 东北人学倾| ：学位论文招_ 二章移动蜂窝l 叫络规划 第二章移动蜂窝网络规划 蜂窝的提出是移动通信发展史上一个重要的里程碑，是解决频率资源和用户 容量问题的一个重大突破。它是一个系统级的概念，其思想是用许多小功率的发 射机来代替单个的大功率发射机，每一个小覆盖区只提供服务范围内的- d , 部分 覆盖。每个基站分配了整个系统可用信道中的一部分，相邻基站则分配另外一些 不同的信道。通过给相邻基站分配不同的信道组，使基站之间及其范围内的移动 用户之间的干扰最小。这一基本原理是所有现代无线通信系统的基础，因为它通 过在整个覆盖区域内复用信道，实现了用固定数目的信道来为任意多的用户服务。 下面将首先简要介绍移动通信网络系统设计中的一些基本要素，然后给出网络规 划的设计目标和传统的规划流程，最后讨论在规划中的几个关键性问题。 2 1 移动网络系统设计基础 2 1 1 小区的概念 小区是基站的收发信机信号所能覆盖的区域。它是蜂窝网络的基本组成单元。 在工程设计中，常常用六边型来表示一个独立的小区，这是因为六边型最接近于 圆的形状，而圆也是全向的基站天线和自由空间传播的辐射模式。另一方面，采 用六边型也是蜂窝系统的分析设计更加简单。实际上，一个小区的无线覆盖是一 个不规则形状，并且决定于场强测量和传播预测模型。 小区按照覆盖范围的大小可分为四类：宏小区、微小区、微微小区和智能小 区。 宏小区提供全局的覆盖，特别是对于那些高速移动的目标的覆盖。通常小区 的基站天线安装在高于环境周围的建筑物上，小区半径为1 3 0 公里。 微小区适用于城市等业务密度较高的地区。通常基站天线安装在与街灯相似 的高度上，因此，微小区的形状通常由街道的布局所决定。小区长度不超过两公 里。 微微小区用于业务密度特别稠密和较高速率业务的地区。典型的是室内环境。 东北大学顺十学位论文第二章移动蜂窝| 叫络规划 基站天线通常设置在天棚，电梯等处。因此，小区的覆盖区由房屋结构，室内的 家具和人的移动所决定。同时服务质量也受上述因素的影响。微微小区的半径大 致为1 0 m - 2 0 m 之间。 随着移动通信的不断发展，近年来又出现了一种新型的小区形式：智能蜂窝 小区。它采用具有高分辨阵列信号处理能力的自适应天线系统，智能地监测移动 台所处的位置，并以一定的方式将确定的信号功率传递给移动台的蜂窝小区。它 可以是宏小区，也可以是微小区和微微小区。智能蜂窝小区的应用，必将极大地 改善系统性能。目前这项技术正在研制过程中。 2 1 2 频率复用 蜂窝无线系统依赖于整个覆盖区域内信道的智能分配和复用。全部可用的信道 资源被分为若干组，每一个小区都分配一组无线信道。相邻小区不能使用相同的 信道组。基站的覆盖范围被限制在小区边界内，相同的信道组就可以用于覆盖不 同的小区。只要这些小区足够远。相互之间的干扰水平在可接受的界限之内。为 整个系统中的所有基站选择和分配信道组的设计过程叫做频率复用或频率规划。 好的频率复用方案可以有效提高系统的频带利用率。相反不合理的频率复用方案 将在基站问带来严重的干扰。 图21 标有相同字母的小区使用相同的频率。簇大小为7 复用因子为l 7 ，即每个小 区可以使用信道总数的七分之一 f i g 2lc e l l sw i t hs a m el e t t e rk l s et h es a l l l ef r e q u e n c y , e v e r yc e l lu s e si 7o f a l lt h ea v a i l a b l e 网络中共同使用全部可用频率的个小区叫做一簇。如果簇在系统中被复制 了m 次，则系统的总容量为： 东北人学硕卜学位论文第二章移动蜂窝刷络规划 c = m k n ( 2 1 ) 其中七为一个小区中的信道组包含的信道数。 通常，称为簇的大小。1 n 叫做蜂窝系统的频率复用因子。n 满足下列的公 式： n = i 2 + + j 2 其中i 和j 都为整数。 典型的复用制大小是4 ，7 和1 2 。很明显，簇越小，即值越小 容量就越大，频带利用率也就越高。7 小区复用制如上图2 1 所示。 2 1 3 中继理论 ( 2 2 ) 网络的系统 对于一个g s m 网络来说，它所能容纳的移动用户数由每个用户产生的业务流 量所决定。每个用户产生的业务量由平均每秒的呼叫次数和每次呼叫的持续时间 所决定。通常用“爱尔兰”表示个完全被占用的信道的话务量强度。如果在一 个小时内的呼叫次数为 次，每次呼叫的平均持续时间为t ，则此信道的话务量为： d ：丝e r l a 馏 (23)3600 。、。 从话务量可以衡量出每个用户平均占用信道的时长。 中继的概念是指允许大量的用户在一个小区内共享相对有限数量的信道，即 在可用信道库中给每个用户按需分配信道。在中继的无线系统中，每个用户只是 在有呼叫时才给分配一个信道。一旦通话终止，原先占用的信道就立即释放。根 据用户行为的统计数据，中继使用固定数量的信道或线路可为一个数量更大的， 随机的用户群提供服务。中继理论的基本原理由丹麦数学家爱尔兰最先提出。 中继系统通常主要有两种，一是阻塞呼叫清除，一是阻塞呼叫延迟。在这两 个不同的系统中，一个拥有n 个信道的小区所能承载的最大话务量不同。中继理 论主要有三个公式，既爱尔兰a ，b ，c 三个公式。爱尔兰b 公式适用于阻塞呼叫 清除中继系统，而爱尔兰c 公式适用于阻塞呼叫延迟系统。 爱尔兰b 公式决定了呼叫阻塞的概率，也就是通过爱尔兰b 公式可以求出在 一定的阻塞概率下系统达到某种话务量时所需要的中继信道数。这个公式常常用 来在系统设计时计算所需要的实际信道数。爱尔兰b 公式的表达式如下： 东北大学硕l 学位论文 第二章移动蜂窝删络规划 p r 阻塞】( 2 4 ) 其中，c 表示中继无线系统提供的中继信道数，a 表示提供的总话务量。 爱尔兰c 公式用于估计呼叫没有立即得到信道的概率，其表达式如下： p r 趑州2 礴a c ( 2 5 ) 爿。+ c ! ( 1 一昙) 鲁 2 1 4 干扰和系统容量 干扰是蜂窝无线系统性能的主要限制因素。干扰的来源包括同小区中的另一个 移动台、相邻小区中正在进行的通话、使用相同频率的其他的基站、或者无意渗 入蜂窝系统频带范围的任何非蜂窝系统。话音信道上的干扰会导致串话。信令信 道上的干扰会导致数字信号发送上的错误，而造成呼叫遗漏或阻塞。干扰是系统 增加容量的一个熏要瓶颈。 在蜂窝系统中，主要的干扰有两种：同频干扰和邻频干扰。 频率复用意味着在一个给定的覆盖区域内，存在着许多使用同一组频率的小 区。这些小区叫做同频小区。这些小区之间的信号干扰叫做同频干扰。同频干扰 不能简单地通过增大发射机的发射功率来克服。这是因为增大发射功率会增大对 相邻同频小区的干扰。为了减小同频干扰，同频小区必须在物理隔开一个最小距 离，为传播提供充分的隔离。如果每个小区的大小相似。基站也都发射相同的功 率，则同频干扰比例与发射功率无关而变为小区半径( r ) 和相距最近的同频小 区的中心之间距离( d ) 的函数。增加d r 的值，相对于小区的覆盖范围，同频小 区内的空间隔离就会增加，从而来自同频小区的射频能量减小而使干扰减小。参 数q 叫做同频复用比例，与簇的大小有关。对于六边型小区来说q = d r = 3 。 来自所使用信号频率的相邻频率的信号干扰叫做邻频干扰。邻频干扰是由于 接收滤波器不理想，使得相邻频率的信号泄露到了传输带宽内而引起的。如果相 邻信道的用户在离用户接收机很近的范围发射，而接收机是想接收使用预设信道 的基站信号，则这个问题会变得很严重。这种现象称为远近效应。另外，当有离 著一器 东北人学颂一l “学位论文箱二章移动蜂谢网络蛳划 基站很近的移动台用了与一个弱信号移动台使用的信道邻近的信道时，也会发生 远近效应。 邻频干扰可以通过精确的滤波和信道分配而减到最小。因为每个小区只分配 可用信道中的一部分，给小区分配的信道就没有必要在频率上相邻。通过使小区 中的信道间隔尽可能的大，这样邻频干扰会减小。因此，实际工程中，不是在每 个特定的小区分配在频谱上连续的信道，而是使给定小区内分配的信道有最大的 频率间隔。通过顺序地将连续的信道分配给不同的小区，可以使得一个小区内的 邻频信道间隔为个信道带宽，其中是簇的大小。同时也可以用类似的方法避 免在相邻小区中使用邻频信道来阻止一些次要的邻频干扰。 2 2 移动网络规划的目标 移动网络规划中的一个重要目标就是使用尽量低的成本，获得较高的频带利 用率和相对较好的服务质量。换句话说，要尽可能地在单位面积的覆盖区域内容 纳更多的用户而同时使每个用户得到服务质量维持在一种可以接受的服务等级 ( q o s ，通常定义为呼叫阻塞的概率，或呼叫延迟时间大于特定排队时间的概率) 上。这一根本目标所涉及的主要方面主要有： 场强覆盖必须保证无线信号对目标区域的一定强度覆盖。即要求接收机 接收到的无线信号强度必须大于按照接收机灵敏度所设定的某一阈值。 业务覆盖对于每一个小区来说，必须保证足够的信道以满足呼叫建立和 切换的需求。而对于整个系统来说，必须保证在目标区域内的平均统计业务量覆 盖达到一定的系统设计要求。 信号传播质量在网络中无线信道的同频干扰和邻频干扰必须被控制在可 以保证可靠的信号传播的范围内。通常在设定的同频干扰和邻频干扰限制条件下 产生兼容矩阵，再针对此兼容矩阵进行信道分配。 建设成本一个网络的复杂性和关键性成本与网络中的基站密切相关。因 此基站的个数是减