（通信与信息系统专业论文）无线通信网络位置区规划和优化算法.pdf

摘要 摘要 在移动通信系统中，由于用户的移动性，网络须时刻识别移动台所处位置，它 是移动性管理( m o b i l i t ym a n a g e m e n t ) 的重要组成部分，位置区就是基于此发展起来的 概念。许多小区被划分在不同的位置区内，当移动台跨越位置区边界时就要进行一 次位置更新( l o c a t i o nu p d a t e ) ，待机状态下也要周期性的向网络进行位置更新请求， 以便告知系统其最新的位置信息；当网络发起对某个移动台的被叫时，将对其所在 位置区内的所有小区发起寻呼( p a g i n g ) 以建立通信。可见位置更新和寻呼都是以位置 区为单位进行的。无论是位置更新还是寻呼都要消耗网络资源，而且两者均与位置 区大小形状有关，位置区过大会导致更多的寻呼成本，位置区过小又会产生频繁的 位置更新，但在现实中我们期望两者都达到最小，可见两者是一对矛盾，因此，如 何合理的对通信网络区域进行位置区划分，以达到最优的位置管理成本，成为我们 研究的重点。 对于不同的网络问题，针对相应的模型进行了位置区规划，在算法的选取上， 分别采用常用的模拟退火以及进化算法来实现。首先，提出了一种基于模拟退火的 新方法来划分位置区，采取了一种自适应策略来调节位置区数目，并结合有效设计 的模拟退火算子，克服了通常算法易于陷入局部最优解的弊端同时避免了无效的搜 索，通过在三组网络环境下进行位置区规划，实验取得了更优的结果，表明了算法 的有效性。 重点从实际出发，在基于道路统计以及切换统计的基础上建立了位置区优化模 型。在通常的位置区规划数学模型中，基本上只是考虑理论的蜂窝小区的数据模型， 而忽略了实际环境的地理因素，如山体河流道路等对位置区目标函数的影响，与仅 仅使用用户流动性数据来表述小区间的相关性相比，基于地理因素基础上建立的模 型更具有真实性。文中通过道路归类统计为基础建立移动管理模型，以位置更新为 目标，在寻呼容量约束下求解最大位置区边界，寻求位置更新成本和寻呼成本之间 的平衡，以达到系统最优的位置管理成本。位置区规划通常被看作是复杂的优化问 题，在算法实现上，解空间十分庞大，为了有效的压缩搜索空间，添加了相邻但不连 通小区属于不同位置区的约束，并利用进化算法的群体搜索优势采用了进化算法和 广东工业大学硕士学住论文 新的编码方式来求解l a p 问题。同时，为了得到有效的初始解和较小的位置区切换， 在结合小区之间的连通性上借鉴模糊聚类的方法来初始化l a 。最后，模拟实际的 道路分布进行了计算机仿真实验，实验结果表明了算法的有效性。 关键词：无线网络；位置区；位置管理；寻呼；位置更新；优化算法 a b s t r a c t a b s t r a c t m o b i l i t ym a n a g e m e n ti sc r u c i a lf o rt h em o b i l ec o m m u n i c a t i o nn e t w o r k ，t h es y s t e m m u s ta l w a y si d e n t i f yt h em o b i l et e r m i n a l sl o c a t i o nt om e e ti t sm o b i l i t y f r o mw h i c h l o c a t i o na r e a ( l a ) i sd e v e l o p e d t h ew h o l es e r v i c ea r e ai s p a r t i t i o n e di n t os e v e r a l l o c a t i o na r e a sa n dal o c a t i o na r e ac o n t a i n sm a n yd i f f e r e n tc e l l s w h e nt h em o b i l e t e r m i n a lc r o s s e sal o c a t i o na r e ab o u n d a r y ，t h a t st os a y ，i te n t e ran e wl o c a t i o na r e a , i t w i l lr e p o r tt h es y s t e ma n dr e g i s t e rt h en e wl o c m i o nt os t a r tal o c a t i o nu p d a t e ( l u ) ，a n di t s h o u l da l s op e r i o d i c a l l yp e r f o r ml u st oi n f o r mt h es y s t e ma b o u ti t sn e w e s tl o c a t i o ni n s t a n d b ys t a t e w h e nac a l la r r i v e s ，t h en e t w o r kw i l ls e a r c ht h et a r g e tm s i na l lt h ec e l l s u n d e rt h es 锄el at os e tu pc o m m u n i c a t i o n ，w h i c hi sc a l l e dp a g i n g s ol o c a t i o na n d p a g i n gp r o c e s sa r eb a s e do nl a w h e t h e rl o c a t i o nu p d a t eo rp a g i n gc o n s u m e st h e n e t w o r kr e s o u r c e s ，a n dt h e yb o t hr e l a t et ot h es i z eo fa nl a t o ol a r g et h es i z eo fa nl a w i l lc a u h i g h e rp a g i n gc o s t ，s i n c et h e r ea r em o r ec e l l st ob ep a g e d ，b u tt h er e g i s t r a t i o n c o s tw i l lb el o w e r c o n v e r s e l y ，i tw i l lc a u s em o r ef r e q u e n tl o c a t i o nu p d a t e sa n dl o w e r p a g i n gc o s t t h e r e f o r e ，r e g i s t r a t i o na n dp a g i n gi sa na n t i n o m y ，a n dt h en u m b e ro fc e l l s i na nl ai si m p o r t a n t b u ti na c t u a la p p l i c a t i o n ，w ee x p e c tb o t hm i n i m u m h o wt of i n d t h er e a s o n a b l el o c a t i o na r e a p a r t i t i o n i n g a n dm a k et h e o p t i m a lm o b i l e l o c m i o n m a n a g e m e n tc o s ti nw i r e l e s ss y s t e mb e c o m e st h ek e yt oo u rs t u d y t h i sp a p e rp r o p o s e sd i f f e r e n tl o c a t i o na r e ap l a n n i n g ( l a p ) w i t l lc o r r e s p o n d i n g m o d e l sf o rd i f f e r e n tn e t w o r kp r o b l e m s ，u s i n gs i m u l a t e da n n e a l i n ga l g o r i t h ma n dg e n e t i c a l g o r i t h m f i r s t ，w ep r o p o s ea na l g o r i t h mb a s e do ns i m u l a t e da n n e a l i n g ( s a ) ，t or e g u l a t e t h en u m b e ro fl o c a t i o na r e a sf o rl a p ，u s i n ga na d a p t i v es t r a t e g ya n dw i t hd e s i g n i n g e f f e c t i v es i m u l a t e da n n e a l i n go p e r a t o r ，o v e r c o m et h el o c a lo p t i m u m ，a v o i di n v a l i d s e a r c ho ft h eu s u a la l g o r i t h m sa n di m p r o v et h es e a r c h i n ge f f i c i e n c yo fa l g o r i t h m t h e n w em i n i m i z e st h el o c a t i o nm a n a g e m e n tc o s ti nt h r e ed i f f e r e n tn e t w o r kc o n d i t i o n s ，t h e e x p e r i m e n t a lr e s u l t ss h o wt h ee f f e c t i v e n e s so ft h ea l g o r i t h m m 广东工业大学硕士学位论文 t h i sa r t i c l ea t t e m p t st oc r e a t el o c a t i o nr r e ao p t i m i z a t i o nm o d e lb a s e d0 nr o a d s t a t i s t i c sa n dh a n d o v e rs t a t i s t i c sc o r r e l a t i o nr e a l i s t i c a l l y t h eu s u a lm a t h e m a t i c a lm o d e l s o fl o c a t i o na r e ap l a n n i n gj u s ta l w a y sc o n s i d e rt h ec e l l s d a t am o d e li nt h e o r y ，w h i l e i g n o r i n gt h ei n f l u e n c eo f t h ea c t u a lg e o g r a p h i c a le n v i r o n m e n tf a c t o r s ，s u c ha sm o u n t a i n s ， r i v e r s ，r o a d sa n ds oo n t h el a pm o d e lc o n s i d e r i n ga c t u a lg e o g r a p h i c a le n v i r o n m e n t f a c t o r sh a sm o r ea u t h e n t i c i t y ，c o m p a r e dw i t hd e s c r i p t i o no fc e l l sc o r r e l a t i o nw i t hs i n g l e m o b i l i t yd a t e t h ep a p e re s t a b l i s h e sm o b i l em a n a g e m e n tm o d e lt h r o u g ht h ec l a s s i f i e d s t a t i s t i c so fr o a d s ，a n dt h eo b j e c t i v ei st om i n i m i z et h el u su n d e rt h ep a g i n gc a p a c i t y c o n s t r a i n t s ，a i m i n gt of i n dab a l a n c eb e t w e e nr e g i s t r a t i o na n dp a g i n ga n da c h i e v et h e o p t i m u ml o c a t i o nm a n a g e m e n tc o s t sf o rt h eg i v e ns y s t e m l o c a t i o na r e ap l a n n i n gi s u s u a l l yr e g a r d e da sac o m p l e xo p t i m i z a t i o np r o b l e m ，a n dt h es o l u t i o ns p a c eo ft h e a l g o r i t h mi sv e r yh u g e ，i no r d e rt oe f f e c t i v e l yc o m p r e s st h es e a r c hs p a c e ，t h ep a p e ra d d s t h ec o n s t r a i n tt h a tt h ea d j a c e n tb u tn o tc o n n e c t e dc e l l sb e l o n gt od i f f e r e n tl a s ，p r o p o s e s e v o l u t i o n a r ya l g o r i t h m ( e a ) a n dt a k e sn e wc o d i n gm e t h o df o ri t ss o l u t i o n e v o l u t i o n a r y a l g o r i t h mh a st h eg r o u ps e a r c ha d v a n t a g et os o l v et h el a pa n df o re f f e c t i v ei n i t i a l s o l u t i o na n dl o w e rl o c a t i o nu p d a t ec o s t ，t h ef u z z yc l u s t e r i n gm e t h o di su s e dt oi n i t i a l i z e t h el a sc o m b i n e dw i t ht h ec o n n e c t i v i t yb e t w e e nc e l l s f i n a l l y ，c o m p u t e rs i m u l a t i o n b a s e do np r a c t i c a lr o a dd i s t r i b u t i o ns h o w st h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m k e y w o r d s ：w i r e l e s sn e t w o r k ；l o c a t i o na r e a ；l o c a t i o nm a n a g e m e n t ；p a g i n g ；l o c a t i o n u p d a t e ；o p t i m i z a t i o na l g o r i t h m i v c o n t e n t s c o n t e n t s c h i n e s ea b s t r a c t i e n g l i a s ha b s t r a c t i i i c h i n e s ec o n t e n t s v c h i n e s ec o n t e n t s v i i c h a p t e rle x o r d i u m 1 1 1b a s i cc o n c e p t sa n dr e s e a r c hb a c k g r o u n d 1 1 2 i h em e a n i n g so f l a pr e s e a r c h 3 1 2 1d e s c r i p t i o na n dt h ei m p o r t e n c eo fl a p 3 1 2 2t h ep r i n c i p l eo fl a p 4 1 3o p t i m i z a t i o na l g o r i t h ms e l e c t e d 4 1 4o u t l i n eo ft h ed i s s e r t a t i o n 7 c h a p t e r2a na d a p t i v es t r a t e g yb a s e do ns i m u l a t e da n n e a l i n gf o rl o c a t i o na r e a p l a n n i n g 8 2 1i n t r o d u c t i o n 8 2 2 】：a 】，p r o b l e m 9 2 3a d a p t i v el a p d e s i g n 10 2 3 1a d a p t i v es t r a t e g yd e s i g n e dt or e g u l a t et h en u m b e ro fl o c a t i o na r e a s f o rl a p 1 ( ) 2 3 2d e s i g no fs aa l g o r i t h mo p e r a t o r 1l 2 3 3s t e p so fs aa l g o r i t h m 1l 2 3 4i n i t i a l i z a t i o nd e s i g no f t h el a s 1 2 2 ：；5t h es o l u t i o no fs c a t t e r e dl a 1 2 2 4c o m p u t e rs i m u l a t i o na n dt h er e s u l t s 13 2 5s u m m a r y o ft h ec h a p t e r 1 4 c h a p t e r3l o c a t i o na r e ap l a n n i n gm o d e l i n ga n do p t i m i z a t i o na l g o r i t h mb a s e do n m o b i l i t ys t a t i s t i c sf r o mr o a d s 15 v l i 广东工业大学硕士学位论文 ：；1i n t r o d u c t i o n 15 3 2p r o b l e md e s c r i p t i o na n do b j e c t i v ef u n c t i o no fl a p 16 3 2 1p r o b l e md e s c r i p t i o n 16 3 2 2l a pm o d e l 1 6 3 2 3l a po b j e c t i v ef u n c t i o n 17 3 3f o r m u l a t i o no fl a p 18 3 3 1a d j u s t m e n ts t r a t e g yf o rc o n s t r a i n t sv i o l a t i o n 18 3 3 2i n i t i a l i z a t i o ns t r a t e g y ”1 9 3 3 3c o d ed e s i g n 2 0 3 3 4u p d a t es t r a t e g y 2 1 3 4a l g o r i t h ms t e p sa n ds i m u l a t i o n 2 2 3 4 1e x p e r i m e n t a ls t e p so fe v o l u t i o n a r ya l g o r i t h m 2 2 3 4 2p a r a m e t e r ss e t t i n g 2 2 3 4 3e x p e r i m e n t a lr e s u l t s 2 4 3 5s u m m a r yo f t h ec h a p t e r - 2 5 c o n c l u s i o n s 2 6 r e f e r e n c e s 2 8 t h e p u b l i s h e dp a p e r sd u r i n gm a s t e r ss t u d i e s 3 2 o r i g i n a la n n o u n c e m e n t j 3 3 a c k n o w l e d g e m e n t 。3 4 v i 第一章绪论 1 1 基本概念与研究背景 第一章绪论 位置区的概念出现在移动通信网络系统中，在介绍位置区之前我们首先引出位 置管理的内容。与固定的电信网络不同，在移动通信网络系统中，移动用户( 或者 移动终端、移动台) 可以自由的移动，而不受固定的点到点的约束，并且移动用户 可以随时随地的接入到系统中，网络也可以时时刻刻的与移动终端建立链接。移动 通信网络系统的优越性为移动性用户提供了动态服务，系统如何识别移动终端的位 置信息，并且为其保证正常的通信，成为移动通信的重要特征，这主要是通过位置 管理来实现的。位置管理主要负责跟踪、存储、查找和更新移动节点的位置信息， 主要包括两个重要功能：位置更新( 或称位置注册，r e g i s t r a t i o n ) 和位置查找( 或称 寻呼，p a g i n g ) ，其中，位置更新( l u ，l o c a t i o nu p d a t e ) 由移动终端向系统报告其 位置的改变；位置查找是系统查找移动终端的过程【1 1 。为方便起见，本文一律将位 置查找称为寻呼，当网络中的移动终端被叫时，系统将通过广播的方式对所有的小 区进行寻呼。由于系统寻呼信道容量的限制，寻呼信息不可能整网下发【2 j ，因此引 入了位置区的概念，蜂窝移动通信网络将服务区划分成不同的位置区，寻呼和位置 更新都是以位置区为单位进行的。 由上面可知，系统时刻保持移动终端的位置信息十分重要。在g s m 网络中， 网络对移动终端进行位置登记，并将其位置信息存储在两个寄存器中，归属位置寄 存器h l r 以及访问位置寄存器v l r 。移动通信系统区域按照等级可以分为g s m 服 务区，p l m n ，m s c v l r 业务区，位置区，基站区，小区【3 】。m s c v l r 业务区指 m s c 所覆盖的区域，通常有一个v l r 为一个m s c 控制区服务，到达该区的移动台 须在此v l r 登记，一个或者几个m s c 对应一个h l r 。一个m s c v l r 覆盖区域由 几个位置区组成，位置区是移动台可以自由的移动不需要进行位置更新的区域，一 个位置区包含若干个小区，不同的位置区由位置区识别码( l a i ) 区别，对应不同 的通信业务区，见下图1 1 。 广东工业大学硕士学位论文 图1 1 业务区划分图 f i g u r e1 - ls e r v i c ea r e ap a r t i t i o n i n g 位置更新：当移动台( m s ) 从一个位置区移动到另一个位置区时，需进行登记。 此过程由移动台发起，当其发现收到的位置区识别码( l a i ) 与其所存储的不一样时 候，便通知移动交换中心( m s c ) 更新其l a i 。文献 1 】和【3 】中分别陈述了位置更新 的三种类型的以及其基本流程： l 、正常位置更新即移动台选择新的位置区内的小区作为服务小区；2 、由小区 参数i 3 2 1 2 定义的周期性位置更新：3 、在附着分离( a t t a c h d e t a c h ) 功能打开的条 件下，移动台重新开机( 或插入s i m 卡后) ，发现当前位置登记区与其存储的l a i 不一致，移动台开始位置更新过程。 位置更新基本流程：m s 开始位置更新过程，在r a c h ( r a n d o ma c c e s sc h a n n e l ， 随机接入信道) 上向基站子系统发送信道请求，然后去占用系统分配的 s d c c h ( s t a n d a l o n ed e d i c a t e dc o n t r o lc h a n n e l ，独立专用控制信道) 发起位置更新请 求信息。经过鉴权和加密过程，v l r 向移动台发送位置更新接受消息，其中包含 t m s i 和l a i 信息。移动台将t m s i ( t e m p o r a r ym o b i l es u b s c r i b e ri d e n t i t y ，临时移 动用户识别码) 和l a i 存储在s i m 卡( s u b s c r i b e ri d e n t i t ym o d e l 用户身份识别卡) 中，回送t m s i 应答消息，移动台释放s d c c h ，位置更新过程完成。 寻呼：当移动台被叫时，m s c 就会向m s 发起寻呼，此消息将以广播的形式在 被叫m s 所在的位置区下发，该位置区内的所有b t s ( 基站) 将通过p c h ( p a g i n g c h a n n e l ，寻呼信道) 向m s 发出寻呼消息，其中包括m s 的i m s i t m s i 信息，m s 在其服务小区的c c c h ( c o m m o nc o n t r o lc h a n n e l s ，公共控制信道) 上监听自己的 寻呼信息，被叫m s 收到后立即响应，可见位置区是寻呼区域的基本单位。 2 第一章绪论 1 2l a p 研究意义 1 2 1 问题产生以及解决的必要性 由上可知，在移动通信网络中，位置管理有两个主要功能：位置更新以及寻呼， 为了更好的进行位置管理，整个通信覆盖区被划分成不同的位置区，一个位置区包 含了若干个小区。在位置区内，m s 可以自由移动不用受位置更新的约束，当m s 跨越位置区边界时就需要进行位置重新登记：当有来电时，网络以广播的形式下发 p a g i n g 命令，被叫m s 所在的位置区内的所有小区都要被寻呼。可见，位置更新和 寻呼在位置管理中是相互矛盾的。位置区范围越大，m s 穿越位置区边界的次数越 少，网络处理位置更新的过程就越少，而此时寻呼的范围就会越大，每次寻呼占有 的网络资源开销就会增大，同时增大了单个基站的寻呼负荷，而且容易造成寻呼失 败，寻呼成功率下降。当位置区范围规划的越小，m s 穿越位置区边界越频繁，位 置更新的次数就会越多，占用更多的s d c c h 信道以及网络开销，同时增加m s c 、 h l r 的负担，手机耗电增加，并且位置更新需要一定的时间，此期间移动台不能打 进或打出电话，然而此时寻呼成本却大大降低。对于整个无线通信系统而言，无疑 要求网络的位置管理成本越小越好，我们希望寻呼和位置更新成本都达到最小，这 显然是不能同时实现的。因此，如何正确合理的划分位置区，对于网络的位置管理 的而言显得十分重要。 位置区规划优化( l a p ) 就是在满足一定的条件( 寻呼容量、带宽等) 下，如何 合理的划分位置区大小，使得系统的位置管理成本最优的问题。位置划分有两个极 端情况：一是整个服务区只含一个l a ，这时候l a 的范围等同于整个服务区，m s 自由移动无需进行位置更新，位置更新成本为零，然而寻呼成本却最大，另外一种 是单个小区作为一个l a ，这时l a 的范围等同于单个小区，寻呼成本最小，m s 只 要穿过小区( 位置区) 边界就要进行一次位置更新，位置更新成本达到最大。l a p 就是在这两个极端之间找到一个折中，使得位置更新和寻呼成本都能达到最优，达 到最小的位置管理成本。 广东工业大学硕士学位论文 1 2 2 位置区边界划分原则 一般情况下，一个m s c 覆盖区域可分成若干个位置区。从减少位置更新次数 节省系统信道资源而讲，位置区划分的越大越好，但是若位置区设置过大，造成系 统寻呼负荷过载，降低寻呼率产生二次呼叫，进一步增加系统负担，严重时导致系 统瘫痪。因此，位置区也不可划分得过大，在无线网络规划优化时候要全面考虑位 置区容量，信道资源以及寻呼负荷之间的关系4 1 。位置区划分一般有以下原则【2 】： 1 位置区划分大小要合理，不能过大过小，以在位置更新成本以及寻呼成本之 间找到一个平衡，一个l a 可以包含单个或者多个b s c ，一个b s c 也可以划分成多 个位置区，但l a 只能属于唯一的m s c ，也即一个位置区内的小区只能属于同一个 m s c 。 2 尽量利用移动用户的地理分布和行为进行l a c 划分，达到位置区边界l u 次 数较少的目的。 3 位置区的边界应该尽量避开话务密集闹市，以减少乒乓位置登记以及二次寻 呼的机率。大城市可以利用市区中山体、河流等地形因素作为位置区的边界。 4 l a 划分尽量不以街道为界，一般要求边界与街道斜交，尽量不与之平行或垂 直，避免乒乓切换以及乒乓位置更新。 1 3 优化算法选择 位置区优化机制包括动态和静态的，前者复杂性较高，往往根据每个用户的行 为及地理分布来设计合理的位置区，位置区的边界是不固定的，位置更新取决于一 些特殊的准则，动态位置更新有基于状态( s t a t e b a s e d ) ，基于距离，基于运动以及 基于时间等几种机制：基于距离的位置更新以移动台所处的小区和它最近一次位置 更新小区的距离为基础，与设定的距离阀值d 相比，超过d 即进行一次位置更新， 若动态的进行距离阀值的优化，位置区大小也动态地变化；基于用户运动模式的位 置更新指移动台根据自己的运动状况，每跨越预先设定的运动阀值相等次数的小区 边界就要进行一次位置更新；基于时间的位置更新中，移动台经过固定的时间间隔 便执行一次位置更新，与所在网络区域位置无关。基于状态机制在综合了以上情况 的基础上，移动台根据自己的当前状态来决定是否执行l u ，这种机制具备了上述 4 第一章绪论 三种的优缺点。 后者对所有的用户设计相同的位置区划分，在实际应用中可行性比较高，因此 静态的位置区划分被广泛的研究，静态机制中位置区的边界是固定不变的，有基于 区域( z o n e b a s e d ) 或者基于用户简表( p r o f i l e b a s e d ) 等。本文之前介绍的g s m 位 置更新采用的就是静态位置更新机制，在某个地区l a 的界限固定不变，由移动用 户的话务量、用户密度数以及寻呼量决定。当移动台跨越位置区边界时便会进行位 置更新。现网用户数的增加以及更高的通信质量要求都需要更合理的进行l a p 。现 在移动通信已经逐渐进入3 g 时代，3 g 通信网络为更多的用户提供更优质的服务， 由于网络频谱资源和处理负荷的有限性，寻求一个消耗更小的位置管理系统就显非 常重要【5 】。2 g 与3 g 网络共存使得各种相关研究也积极推进，但鉴于u m t s 和g s m 中移动性管理的相似性【6 】在此我们依然根据g s m 移动通信网络系统标准进行，它 的准则同样适用于我们的新局入网规划。 划分问题一般看作是n p 难问题【7 】，l a p 位置区规划优化问题属于划分问题，许 多优化算法如进化算法【6 ，8 - 1 5 】( e v o l u t i o n a r ya l g o r i t h m s ，e a ) 以及模拟退火算法 ( s i m u l a t e da n n e a l i n g ，简称s a ) 【1 7 - 2 0 ，禁忌搜索( t a b u - s e a r c h ，t s ) 【2 1 ，2 2 ，8 】等都 被用来解决l a p 。 文献【6 】运用基于并行岛屿模型的遗传算法解决l a p 。文献【8 】分别用遗传算法， 模拟退火算法和禁忌搜索解决。a l m e i d a - l u zs 等在【ll 】以及s 6 n i aa l m e i d a - l u e 等 在【1 2 】和 1 3 1 中运用差分进化算法( d i f f e r e n t i a le v o l u t i o na l g o r i t h m ，d ea l g o r i t h m ) 求解位置区最优问题，在 1 3 q b s 6 n i aa l m e i d a - l u e 设置相应d e 方案的最佳参数，在 1 2 种不同的测试网络下进行结果比较，取得了好的结果。b k a r a o g l u 运用【1 7 】中模 型以小区m s c 分配( c e l l t o s w i t c ha s s i g n m e n t s ，c s a ) 和小区l a 分配( c e l l t o l a a s s i g n m e n t s ) 为目标，用三种不同进化算法：遗传算法g a ，多种群遗传算法 ( m u l t i p o p u l a t i o ng e n e t i ca l g o r i t h m s ) 以及m e m e t i c 算法( m e m e t i ca l g o r i t h m s ，m a ) 来测量它们解决c s a 问题的适用性l l 引。 文献【1 7 】提出了基于模拟退火( s a ) 算法求解l a p 以及c s a ( c e l l - t o s w i t c h a s s i g n m e n t ) d , i r 分配的方法。文献【1 8 】将在模拟退火算法中使用文献 2 2 1 q 了六种不同 的退火策略来解决 1 7 q b l a p 的问题。t a h e r i 分别运用遗传算法( g e n e t i ca l g o r i t h m ， g a ) 【1 5 l 和模拟退火( s a ) 1 1 9 1 以及c o m b i n e dg e n e t i c n e u r a la l g o r i t h m l 2 3 】解决移动 性管理问题，对不同个数小区的网络环境进行了位置区划分。文献【2 4 】中l a 划分问 5 广东工业大学硕士学位论文 题被看作是图优化问题( g r a p ho p t i m i z a t i o np r o b l e m ) 。在文献【2 5 】中使用了深度优 先搜索( b d f s ) 的启发式搜索，在规定执行时间的情况下，该算法能取得比s a g a t s 更优的最优解。l i 等在完全均匀话务量以及相邻小区之间的用户流动性为常数的情 况下，用一种多项式时间近似方案求解小的位置管理成本【7 1 。此外，s 6 n i a a l m e i d a - l u e 运用一种新的算法，分散搜索算法【2 6 】解决l a p 问题；m e m e t i c 算法 ( m e m e t i ca l g o r i t h m s ，m a ) 1 5 , 2 7 也被用来求解l a p 。 本文将分别用s a 和e a 解决不同模型的位置区规划问题。 模拟退火算法简介：模拟退火算法起源于固体退火过程，先将固体加温至充分 高，再将其缓缓降温。加温过程，固体粒子随升温变成无序状，内能增大，降温过 程，粒子逐渐趋于有序，在每个温度都可达到平衡态，内能降低，并在常温时达到 最小圆。模拟退火算法降温过程能量接受概率服从m e t r o p o l i s 准则( 粒子在温度r 时 趋于平衡的概率是e - a e ( 灯) ，其中e 为温度丁时的内能，丝为其能量改变量，k 为 b o l t z m a n n 常数) ，即概率接受新状态，是m e t r o p o l i s 在1 9 5 3 年提出的重要性采样法， 1 9 8 3 年k i r k p a t r i c k 等提出模拟退火算法，并将其应用于组合优化问题的求解。模拟 退火算法与初始值无关，其求得的解与算法迭代的起点无关，它以一定的概率接受 新能量的方式使其成为一种全局最优算法，具有渐近收敛性和并行性，另外还具有 描述简单、使用灵活、运行效率高等优点。文献【2 9 】对模拟退火算法进行了详细全 面的研究。 进化算法简介：进化算法又称进化计算( e v o l u t i o n a r ya l g o r i t h m ，e a ) ，起源 于2 0 世纪5 0 年代末，它是一种模拟生物适者生存，优胜劣汰机制的遗传和进化过程 的随机搜索方法，通过一组初始解不断复制、交换、变异等遗传操作产生和选择新 个体逐渐逼近最优解，它包含遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、进化策略( e v o l u t i o n s t r a t e g y ，e s ) 和进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 等三大主流方法。这三 种方法分别利用不同的进化手段来模拟生物的进化规律。遗传算法( g e n e t i c a l g o r i t h m ) 最先i 由b a g l e y 在1 9 6 7 年发表的关于遗传算法应用方面的论文中第一次使 用了遗传算法这个名称【3 0 】，直至u 1 9 7 5 年，美i 虱m i c h i g a n 大学的j h o n h h o l l a n d 发表 了著作( a d a p t a t i o ni nn a t u r a la n