（计算机软件与理论专业论文）个人通信网络中的移动位置管理策略研究.pdf

硕士学位论文 m a s t e r st h e s i s 中文摘要 未来的无线个人通信服务p c n ( p e r s o n a lc o m m u l l i c a t i n e 咐o r k ) 将支持更高密 度，更高移动性的用户，并支持采用不同接入网与核心网的用户进行网间漫游。这 将会产生巨量的系统资源消耗。设计合理、高效、优化的移动终端的移动性管理策 略，并给出行之有效的算法及严密的理论证明，在移动计算中是十分重要的。为此 要对现有的位置管理策略进行改进以提高效率。 现有的基于h i r ，瓜两级数据库结构的位置管理策略在移动用户穿过位置区 时，需要频繁的更新移动用户的h u t ，系统效率受到了极大的限制，资源消耗很大。 本文提出了一种基于阈值的两级指针推进策略，该策略将部分v l 且中的移动用户 选为移动代理m a ( m o b i l ea g e n t ) 。m a 之间建立第一级指针链，在m a 与v l r 之 间建立第二级指针链，两级指针链均设定长度阚值。将该策略与基本位置管理策略 及“通行用户指针推进策略”和“带门槛的指针推进策略”的开销进行比较得出： 选择适当的阈值，提出策略的开销优于上述策略。同时，基于阈值的两级指针推进 策略的一个最大特点是在存在一个较长的指针链的情况下，不增加呼入查找时延。 利用基于缓存( c a c h c ) 的位置管理策略的优点，本文提出了一种将指针推进策略 与c a c h e 策略结合的位置管理策略，通过利用移动用户移动的移动和接受呼入的局 部性，在c a c h e 信息失效的情况下，可通过遍历起始于c a c h e 中的推进指针链来获 得移动用户的位置信息，从而避免直接访问h u l 数据库。有效的减少对h l r 的访 问和位置管理中的通信流量。 由于未来的p c n 将提供更小的蜂窝来适应不断增长的移动用户，这一举措使 得移动终端尽管只是在一个小的区域内移动或在两个邻近的蜂窝之间来回移动时， 由于其高跨区率将导致频繁的位置更新和较高的网络信号流量。为克服由于移动用 户的这种局部性运动而导致的不必要的频繁位置更新，从而给基于移动的策略性能 带来的影响，本文最后又提出了一种基于移动的去环位置更新策略r r m b 策略， 该策略通过去除移动终端在移动轨迹中形成的环，可减少移动用户移动过程中的位 置更新的次数。 本文最后总结全文，并提出未来的展望。 关键词：移动计算；位置管理；位置更新；寻呼；无线网络：个人通信网络 a b s t r a c t f u t l l r ew j r e l e s sp e r s o n a l 删1 】l l i c a t i o nn e 研o r k ( p c n ) 弼us u p p o ni i l t e r - n e 脚o r k m 扰l i i l gb e t 、v e e nd i 肺r e ma c c sn e 咐o r k s 锄dc o f en e 撕o r kf o rh i g h c fd e n s i t ya i l d m o b i m yu s e f st h a tw n 王l e a dt ol a r g eq u a l l t 协e so fs y s l e mr c s o u r c e sc o n “m 如g i ti s s i 鲥丘c 姐t i nm o b i l e c o m p u t i n g t l l a t r a t i o n a l ，e 踟c t i v c 粕d 叩t i l i z c dm o b m t y m a n a g 锄e n ts c h e m e sa r ec o n c e i v e d 姐dm e i ra l g o r i 岫sa r ep v e dt ob ef e a s i b l e a c 删i n gt 0 m es 仃i c tt h 吲e s s oi ti sv e r yi m p o n a n tt oo p t i 刀1 i z et h cc u 玎e n tl o c a t i 咖 m a 越g c m e n ts c h e m e st 0a c h i e v ee m c i e n c y n e e x i s t i n gl o c a t i o nm 卸a g e m e n ts t r a t e g i e ss u c ha sh 球，v l rh a v et ou p d a t et l i e h l ro f m o b i l eu s e r sf r e q u c n n yw h e nt h e yc m s st l l eb o u n d 村yo fal t 1 1 c r e f o ，s y s t e m p e r f o m 柚c ei sr e d u c e d 柚ds y s 胁r c s o u r c ei s0 v e r 咖s u m c d s oam o - l e v e lp o i n t c r f b 邢a r d j n gs t r a t e g yw i t l lt h f e s h o l d si sp r o p o s e d h tt l l i ss c l l e m e ，ap a n 0 fm o b i l eu s e r si i i 露s 盯cs e l e d e da st h em a s ( m o b j l ea g e n t s ) a 丘r s tl e v dp o i n t e ri sb u n tb e t w e e n m 触，孤das e c o n dl e v e lp o j n t e ri sb u i l tb e 柳e e nm a s a n dv u t s n r e s h o l d sa r es e tf o r t h ct w o l e v e lp o i n t e r s ( b m p a r i n gt l l cc o s t0 ft b es c h e m cp f o p o s e dw i t i it l l a t0 ft h c p e 卜u s e rf b r w a r d i n gs c h e m e ，r c s u l ts h o w s t h es c h e m cp r o p o s e do u t p e r f o n n st h eo t l i e r sb y c h o o s i n g 晰os u i t a b l et l l r e s h o l d s a tm es 锄et i m e ，o n eo ft h ca d v 卸t a g e so fo u rs c h e m e j st l l a tt l l o u g hi tm a yh a v eal 咖gp o i i l t e rc h a i l lw i t h o u ti n c r e a s i n gt l l ec a l lf i n d i gd e l a y u s i l l gt h ea d v a n t a g eo ft h cc a c h es c h e m e ，ak i n do fc a c h c m b i n e sf b 聊盯d i n g p o i n t e 娼m o b i l i t ym a n a g e m e n ts c h e m e ( c a l l e dc c fs c h 啪c ) i sp r o p o s e di n 也i sp a p c r ， w h i c he x p l 蕊t sau s e r sm o v e m e n ta 】1 dc a l ll o c a l i t y e v e ni ft h ec a c h ei n f o n a t i o ni sn o t u p - t o d a t e ，t t l ec a l l e dm o b i l eu s e rc a nb ef o u n db yt r a d n gf o r w a r d i n gp o i n t e r ss t a r t j i l g 丘o mt l l a tv l r p o i n t e di nt h ec a c h ei n s t e a do fq u c r y i n gt h eh u l t h e r e f o r e ，t h i ss d l e m e c a i le 脏c t i v e l yr e d u c et h ea c c e s sl ot h eh u ta i l dt h es j 肛a l i n gt r a f f i cj nt l i el o c a t i o n m a i l a g e m e t a 川d y t i cr e s u l t ss h o wt h a t ，t 1 1 ep r o p o s e ds c h e m eo u t p e r f o 珊so t h e r s c h e m e sw 血e nau s e r sc m ri sh j g l lo rt h es i 印a l i n gt m 位ct ot h eh u ti sh e a v y f b rt h ef l l t u r ep c sn e 押o r ka d o p t ss m a l l e rc e l l st oa c c o m m o d a t ec o n t i n u o u s l y 铲。诵n gp o p u l a t i o n o fs u b s 州b e r s ，w h i c hr e s u l t si n 丘e q u 髓t1 0 c a t i o n u p d a t e姐d c o n s e q u e n t l yh i g h e rs j g n a l i n g s t i nt h i sp a p e r ，ar i n g r e m o v a lm o v e m e n t - b 硒e d l o c a t i o nu p d a t es c h e m ew i t l las e l e c t i v ep a 百n gi sp r o p o s e d t h i sl o c a t i o nu p d a t es 6 h e m e 硕士学位论文 m a s t e r st h e s i s r e d u c e st h el o c a t i o nu p d a t e sb yr e m o v i n gt h er i gf o 衄e di nt c 珊i i l a l sm o v e m e n tp a t h n u m e r i c a lr e s u l t ss h o wt h a tt h ep m p o s e dm o v e m e n t - b 鹤e du p d a t es c h e m ep r o v i d e sa b e n c rp e r f o 锄a n c et h a nt h ei m p r o v e d 硼o v e m e n t - b 髂e dr c 百s t r a l i o n ( i m b r ) s c h e m e w h e nt h et e 瑚i n a l sc a l l t o m o b i t ym t i oi ss m a l l a t l a s t ，t h et l l e s i si sc o n c l u d e da l l df t l t u r ew o r ki sp m p o s e d k e yw o r d s ：m o b i l ec o m p u “n g ；l o c a t i o nm a n a g e m e n t ；l o c a t i o nu p d a l i n g ；p a g i i l g ； w i r e l e s sn e 铆o r k s ：p e r s o n a lc o m m u n i c a t i o nn e 柳o f l 【s i i l 顾士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名： 日期：p 垮 7 日 导师签名： 日期：年月 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。回童鲨塞堡变压进厦! 旦坐笙；旦二生；旦三生筮查： 作者签名：揪 日期：加6 年6 月- 7 日 导师签名 日年多月7 日 | 1 1 课题背景及意义 第一章绪论 随着信息技术的发展，无线通信得到了巨大的发展，个人通信是2 l 世纪通信 发展的重要方向，个人通信服务网络用户呈指数速度增长并将在今后的几年中继续 增长。下一代个人无线通信网络p c n 被规定为i m ：2 0 0 0 系统的标准，其目的就是 把现今存在的各种系统( 包括p c s ，晰o - w a 丫呼叫，移动人造卫星，等等) 统一成一 个能提供大范围服务的无缝的无线通信设施。因此，对终端用户移动性的描述成为 重要研究领域之一。在获得用户移动性的基础上，我们可以进一步研究移动用户的 位置管理。 在移动计算中，移动终端m t ( m o b n ct c n i l i m l ) 时常从一个网络位置移动到另 一个网络位置。为了能够有效的跟踪m t ，它们的当前位置信息必须存储在网络的 特定位置，并对它们的位置信息进行管理。位置管理涉及到两个基本操作：位置更 薪( l o c a t i o nu p d a t e ) 和寻呼0 a g i l l 曲。当m t 从一个网络位置移动到另一个网络位置 时，就触发了位置更新操作，位置更新操作涉及m t 的移动率；当需要联系m t 时， 就需要对其进行寻呼查找。寻呼操作涉及m ，r 的呼入频率，就是呼入到达率。这两 个操作都消耗资源，包括m t 和基站之间通信链路的信令交换，空中接口带宽，无 线网络带宽，网络数据库资源和其他系统资源。 位置管理使网络能够在连续的两次呼入之间跟踪m t 的位置，因为m t 可在覆 盖的区域内自由移动，网络只能维护每个m t 的大致位置。当网络必须为某个特定 的用户建立呼入连接时，网络必须决定该m t 在一个蜂窝尺寸大小的区域内的精确 位置。 由于在移动计算中，需要存储、更新和查找m r 的位置信息，围绕着这一问题 产生了各种各样的方法。从资源消耗的角度看，如果一旦m t 越过蜂窝边界即对其 位置进行更新，则定位花费高( 知道m t 的确切位置) ，寻呼的花费低( 寻呼信息只 需发送到较小的区域) ；如果m t 不常进行位置更新。当呼入到达时为查找到m t 的当前位置需寻呼一个大的覆盖区域，则定位花费低( 知道m t 的大致位置) ，寻 呼的花费高( 寻呼信息需要发送到较大的区域) 。因此，这两个过程在占用系统资 源方面是对立的，一般需要在两者之间取一个折衷的方案。因此，位置管理的核心 问题就是设计一个算法以最小化位置更新和寻呼的总费用。 各种位置管理策略都是在上述两个极端之间即在位置更新与寻呼查找之间寻 找一个平衡点，一般地，是在可用性( a v a i l a b i l i t y ) 、精确性( p r e c i s i o n ) 和流通性 ( c u f r e n c y ) 三者之间选择一个折衷的方案。可用性的选择范围是介予以下两个极端之 间：从网络的所有节点存储m t 的位置信息，到不在任何一个网络的节点存储其位 置信息。精确性有许多形式，如存储一些m t 的可能位置，而不存储其精确位置。 流通性主要是关于何时更新位置信息，如对于高移动性低呼入的m t ，当它每次移 动时不必立即更新其位置信息，位置更新操作可以稍作延迟。 由于m t 的移动性，使得人们与移动用户的通信费用伴随着寻找它们当前位置 的费用而增大。因此，设计一个合理、高效、优化的跟踪m t 的系统模型，并给出 行之有效的算法及严密的理论或实验证明，在移动计算领域是举足轻重的。值得一 提的是，移动性管理策略的研究成果具有广阔的应用前景，尤其适用于移动电子商 务、卫星导航与定位等等。因此，本文致力于移动计算方面的移动性位置管理策略 的研究。 1 ：2 位置管理策略研究现状 目前对位置管理的研究主要放在系统数据库结构的优化和缩短信令在网内的 传输等方面，考虑的因素主要是在激增的移动用户数量下如何减少数据库更新，缩 短对m t 的寻呼步骤，减少寻呼延迟等等，而不降低系统的可靠性。其策略从系统 网络结构上可分为两类。 1 2 1 集中式位置管理 目前2 g 系统所采用的g s m 和i s 4 1 【1 2 】就是一种集中式位置管理方式。它们采 用归属位置寄存器h l r ( h o m el 0 c a t i o nr e g i s t e r ) 和访问位置寄存器v 】且( v i s i t io c a t i o nr e g i s t e r ) 组成的两级数据库1 3 叫处理网络中的信令交换和传输。h l r 保存本 地注册用户的永久信息( 如注册数据、鉴权数据、位置信息等) ，而每个v u t 则存 储漫游到它所覆盖区域内的部分访问用户的信息( 从h l r 拷贝而来) 。集中式位置管 理的研究就是在保持基本的数据库网络结构不变的前提下( 即为h l r 和v l r 组成 的两级数据库结构) 来对i s - 4 1 位置管理策略进行改进，采用优化策略达到减小位置 管理开销的目的。这种方式的优点是无需做重大的修正即可用于当前的移动通信网 络。目前的大部分研究就是采用这种方式。 2 1 2 2 分布式位置管理 分布式位置管理【7 删其主要思想是：建立一个层次型全分布式的位置数据库槲坤坷， 取代i s 4 1 标准中的h u v v l r 两级数据库结构进行位置管理。如图1 1 所示，网络 数据库分多层，每个上层数据库统辖多个下层数据库所在的地区。每一层的数据库 都是h l r 和v u t 的结合。m t 与位于最低层次的位置信息数据库( 叶数据库) 相对 应，每一个位置信息数据库保存位于其“子树”内的m t 的位置信息。级别越高其 所容纳的m t 位置信息越多，呈指数增长。这种方式降低了信令消息的传输距离。 然而，该方案增加了数据库更新的次数，由此增加了位置更新和呼叫传递的时延。 由于蹦t - 2 0 0 0 要组成一个全国乃至全球性网络，网络由采用不同核心网、不 同接入网的予网组成，因此数据库在本质上是分布式的。3 g 系统的位置管理可以 看作是由大量的超大容量数据库组成的分布式位置管理方式。而各国在各自的 2 g 2 5 g 系统设计时未考虑移动用户在各系统间的漫游，导致移动用户只能在各自 的通信系统网络内漫游，这些系统网络实际上只是一些物理上相互隔绝的集中式两 级数据库网络。 图1 1 分布式数据库结构方式 其实，理想的位置管理方案应该是结合了动态化的介于集中式和全分布式之间 的方案。实际上，大多数正在进行的研究集中在：1 ) 提高集中式数据库结构下位置 信息的分布。2 ) 在分布式数据库结构中减小位置信息的分布性。 硕士学位论文 m a s t e r st h e s i s 1 3 现有的位置管理策略 1 3 i 当前普遍使用的2 g 系统的位置管理 在第一代和第二代蜂窝移动通信网( g s m ，i s 4 l 等) 中，使用得最为广泛的是采 用两级数据库结构，通过位置区l 吣l 0 c a t i o n 加e a ) 进行位置管理【。l a 由一定数 量的蜂窝小区组成，使系统得以追踪在网络中漫游的用户。当系统知道某用户所在 l a 时，若需要与该用户建立连接，只需在该l a 内的蜂窝区中发送寻呼信号。实 现基于l a 的位置管理方式需要使用数据库。其位置管理方法是基于一个双层的数 据库结构，也就是用两种网络位置数据库h l r 和v l 且来跟踪m t 。如图1 。2 所示， 通常，一个网络有一个h i r ，用户和所注册网络的h l r 永久地联系在一起。用户 的有关信息，如所购买的服务和位置信息都存储在h u t 的用户文件中。不同网络 中且的数量和位置各不相同，每个v u t 存储访问它所覆盖区域的非本地注册的 m t 的信息( 从h u t 拷贝而来) 。 图1 2 现有位置管理采用的网络架构 目前常用的位置管理，有两个通用的标准：e i a 门r i a 的a n i s 4 1 和g s m 的m a p ， 前者用于北美的i s 9 5 系统，也是c d m a 2 0 0 0 1 x 、c d m a - e v 等2 5 g 和3 g 系统 位置管理的基础，后者用于欧洲提出的g s m 系统，在2 5 g 的g p r s 、e d g e 和3 g 的w c d m a 和t d s c d m a 等系统大面积普及应用之前，这些已应用的移动通信系 统之间还是孤立的，不能进行相互通信，自然也不涉及位置管理的问题。 现有位置更新的方式有周期性位置更新和越区位置更新。前者要求用户定时向 4 硕士学位论文 m a s t e r st h e s i s 网络报告其身份，有时会造成不必要的资源浪费( 如用户数小时都在某l a 内) ，因 此常和后一方法结合使用。在越区位置更新方法中，各基站周期性地在本区广播其 l a 识别码。当m t 接收到的l a 识别码与所广播的l a 不同时，自动进行位置更新。 以君前世界上覆盖面积最广、用户最多、技术最成熟的移动通信系统g s m 为 例，在g s m 移动通信系统中，使用了h l i v v u t 机制来进行用户的移动性管理， 整个服务区被分成许多个位置区l a ，用h l r 来永久登记那些临时移动到它管辖的 网络内的用户，而每个v i 且则存储它所辖位置区内的部分访问用户数据。当用户 进入到一个新的位置区时，如果新位置区和原位置区都由同一个v l r 服务，那么 就不向h u t 产生任何更新请求，如果新位置区与原位置区不是由同一个v i 且服务， 瑚m 就进行位置更新操作。如果网络和移动终端之间在一段固定的时间内( 比如几 个小时) 都没有通信( 即移动终端处于空闲模式) ，移动终端也应产生位置更新，以便 在系统数据库记录失败的情况下恢复用户位置数据。这里用户的位置信息存储在 h u t 和t 中。 1 3 22 5 g 系统中位置管理应用 2 5 g ( 第2 5 代移动通信系统) 是在现有2 g 蜂窝网络基础上，主要由“个人通信 业务( p c s ) ”运营商而非系统供应商提出的，借以转化到由i m ：2 0 0 0 规范参考规定 的下一代无线通信技术的一组方法。可以使无线网络运营商在3 g 平台可用之前就 能够部署数字分组业务，并尽量使2 g 系统平滑过渡到3 g 系统。目前的2 5 g 技术 平台主要有通用分组无线业务( g p r s ) 、g s m 演进增强数据率g e ) 、码分多址 ( c d m a 2 0 0 0 1 ) ( ) 。 从技术上看，2 5 g 主要是在2 g 系统核心网的基础上增加了基本上独立于标准 系统交换和传输网络的一种分组数据交换和传输网络。其位置管理基本沿用2 g 系 统的两级数据库结构，没有改变。只是在进行位置管理操作时要增加分组数据交换 业务端的信令交换量。因此可以认为2 5 g 的位置管理策略与2 g 相同。 1 0 3 第三代移动通信系统o g ) 及其位置管理应用 目前蜂窝移动通信以直接传输和处理数字信息为主要特征的第二代数字移动 通信系统已投入商业运营1 3 年了( 以1 9 9 1 年芬兰建成的第一个g s m 网络为准) 。 第三代蜂窝移动电话系统( 简称3 g ) 在国外已经开始投入商用，其固有的i p 核心 网络可望推动多媒体个人业务及移动互联接入业务的发展。3 g 移动通信系统将移 动和固定，语音和数据等服务融合在一起，提供一个综合服务平台。它的主要特征 是无缝的在全球漫游，至少2 m b i t s 的传输速率和无缝的提供服务【1 7 】。 硕士举住论文 m a s t e r st h e s i s 国际电信联盟( r r u ) 把第三代移动通信系统称为i m ，r - 2 0 0 0 ，而欧洲则把第三 代移动通信系统称为u m t s ( 通用移动通信系统) 。其移动通信网络主要包括无线 接入网和支持无线接入的核心网。空中接口的选择是3 g 面临的一个重要且必须及 早解决的问题。3 g p p ( 3 gp a n n c r s l l i pp r o j e c t ) 和3 g p p 2 第三代合作项目是为加速 开放的全球认可的3 g 技术规范而设立的项目。3 g p p 的宗旨是制定以g s m 为核心 网，w c d m a 为主要无线接口标准。3 g p p 2 的宗旨是制定以a n s s 4 1 为核心网， c d m a ：! o o o 为主要无线接口的标准。 在位置管理上，为降低信令业务量和优化网络规程，3 g 系统基于现有两级数 据库体系作了部分改进。例如3 g p p 2 3 1 9 规范提出了在v l r 与h l r 间引入网关位 置寄存器( g l r ) 来限制国际漫游信令在被访问移动网络和归属移动网络间的业务 量。此方案适用于不同类的无线接入网在g s m 核心网络的综合。 虽然第三代移动通信可以比第二代移动通信系统的传输速率快上千倍。但是仍 无法满足未来多媒体通信的要求，未来各种不同技术的综合和互相作用以及真正的 宽带无线变革和以用户为导向的智能业务将引领新一代异类无线网络，即通常所说 的4 g 系统。 1 3 4 目前所采用位置管理策略的不足 目前采用的两级数据库+ 固定位置区的位置管理策略主要有以下缺点： 1 信令分布不均匀性，尤其是无线信令分布的不均匀性：移动终端穿越位置 区边界触发的位置更新所产生的信令负载集中在位置区边界的蜂窝上，以致无线信 令在不同蜂窝及蜂窝内不同位置的分布不均匀； 2 当用户容量扩大引起事务处理增多时，将大大增加h u t 信令处理负荷和数 据库查询时延，h u t 将成为数据处理的瓶颈，并使系统可靠性降低； 3 固定不重叠配最的位置区可能导致移动终端在相邻位置区间来回的局部性 运动，形成多次不必要的位置更新； 4 移动性管理过程不能根据用户在不同时间的不同移动一呼入特征作自适应 的动态调整； 5 如果一个移动用户漫游到距离归属地较远的位置区，这种机制将增加位置 更新和呼入请求的时延，同时会大量增加中继网络的信令负荷。 6 硕士学位论文 m a s t e r st h e s i s 1 4 研究工作介绍 位置管理的研究目标就是对个人通信网络中已有位置管理策略的基础上，为适 应移动用户数的增加以及随着通信网络的发展而引起的这一领域的一系列变化，提 出一些新的位置管理策略，以适应这些变化，从而满足最小化移动用户位置管理开 销的要求。 在此，可以提出量化的位置管理总开销的公式： 丁c 如缸f = i 缸把+ c 品肼r 增( 1 1 ) 其中前者包括进行位置更新所产生的信令开销，后者包括进行寻呼操作产生的信令 开销。 对个人通信网络中的位置管理策略进行改进或提出新的策略，并通过仿真实 验，验证提出策略的可行性及优越性。文中提出的几种新的位置管理策略，包括基 于阈值的两级指针推进策略、将缓存和指针推进的结合位置管理策略以及基于移动 次数的去环的位置管理策略，对原有位置管理策略，包括基本位置管理策略、指针 推进的等静态位置管理策略和基于移动次数策略的动态位置管理策略进行改进。并 通过理论分析和仿真实验，对新的位置管理策略的优越性进行证明。 1 5 论文的章节安排 本文的结构安排如下： 第一章，介绍论文课题研究的背景和意义，概述当前国内外位置管理的研究进 展，以及目前所采用的位置管理的不足，最后对本文的研究工作和章节安排作了简 要介绍。 第二章，本章对移动通信网络的基础知识做出概述，介绍如移动计算中的位置 管理使用到的网络拓扑模型、呼入到达概率、以及用来刻画聚合或单个用户移动行 为的移动性模型。并着重介绍了目前国内外学者在移动性管理策略的研究方面己取 得的巨大成果，本文在阅读了了大量参考文献的基础上列举出了目前人们探讨的一 些主要的位置更新和寻呼策略。 第三章，本章主要对移动性管理策略进行研究，在分析了现行个人通信网络中 现有的一些位置管理策略的缺陷后，提出了一种基于阈值的两级指针推进策略，利 用计算出的移动用户在两次呼入之间的平均越区次数公式对上述策略进行了对比 分析。 硕士学位论文 m a s t e r st h e s i s 第四章，在研究了缓存策略和指针推进策略后，提出了一种将缓存和指针推进 结合的位置更新策略，通过该策略可减少缓存失效率，从而减少对m 且的访问次 数，节约系统资源和减少网络信号流量。 第五章，为适应未来p c s 网络的一些特性提出了一种基于移动次数的去环的位 置更新策略，并且对该策略的性能和开销与其它的基于移动的策略进行了对比研 究。 第六章，总结本文的研究工作，并对需要进行进一步研究的方向做了展望。 第二章位置管理概述 当前的p c s 网络使用一个蜂窝状的结构，其物理覆盖区域划分成许多蜂窝 ( c c l l ) ，一个机站b s ( b a s es t a t i o n ) 服务于一个c e l l ，m t 通过b s 与网络连接。c e l l 可 以有不同的大小：在室内环境中通常使用p i c o c e l l ；大的城市中使用m j c r o - c e l l ； m a c r o c c l l 通常被用在乡村地区或高速公路。小c c l l 通信电力消耗少并且允许更大 的频率复用。几个b s 连接到一个机站控制器b s c 衄s es t a t i o nc 0 m m l l e r ) 上，多个 b s c 再连接到一个移动交换中心m s c ( m o b i l es 稍t c h i l l gc 0 n 咖1 l c r ) 。多个m s c 再 连接到公共电话交换网络p s l ：n ( p u b l i cs w i t c ht e l 印h en e t w 砒k ) 。 p c s 网络使用基于l a 的位置更新算法以及覆盖选举( b l 趾k c tp o l l i n g ) 寻呼策略。 由一个h u t 所服务的区域成为一个服务区s 刖s e i c c 心e a ) ，其覆盖区域被划分成 大量的l a ，每个l a 包含一群c d l 。如图2 1 所示，是一个典型的p c s 网络结构图 1 3 ，埔，1 9 1 。同一个l a 内的所有b s 周期性的广播该l a 的标识符( i d ) 。每个m t 将它 所注册l a 的i d 与其当前所接收到的广播的m 进行比较，如果这两个d 不同， 则触发m t 进行位置更新。当有呼入时，对该m t 所在l a 的所有c e l l 同时进行选 举，确保一次寻呼成功。 服务区( s a ) 图2 1 典型的p c s 网络结构 9 硕士学位论文 m a s t e r st h e s i s 2 1 网络拓扑 网络拓扑可以是1 维的或2 维的。如图2 2 所示，在1 维拓于卜中，每个c e n 有 两个邻居( 如果存在的话) 。如果使用环形拓扑，则第一个和最后一个蜂窝是邻居【加j 。 1 维拓扑用来模拟移动终端仅限于向前或向后移动的那些服务区，比如高速公路和 铁路。 2 维拓扑用来模拟那些移动终端可向任何方向移动的一般的服务区域，有两种 可能的蜂窝格局覆盖服务区，即正六边形格局和网状格局。如图2 3 所示的正六边 形格局中，每个c d l 有六个邻居【2 1 ，2 2 l 。而图2 4 显示了蜂窝的网状格局，尽管每个 c c l l 表面上有8 个邻居，但大多数研究者认为m t 实际上几乎不会移动到角上的4 邻居中去，所以一般认为只有4 个邻居i 凸吲，即分别位于水平方向和垂直方向的2 个邻居( 第五章中将会涉及到这种网状格局的具体应用) 。尽管为简便起见假设了蜂 窝的网状格局，但还不知道网状格局是否是一个符合实际的模型，尤其是假设只有 四个邻居的情形。 图2 2 1 d 网络模型 图2 32 维网络拓扑的正六边形格局 1 0 硕士学位论文 m a s t e r st h e s i s 2 2 呼入到达概率 22222 211 12 2l012 2l112 22222 图2 42 维网络拓扑的网状格局 呼入到达概率在评价位置管理策略的性能中起着非常熏要的作用。如果m t 事 先知道寻呼到达的时间，则其可在呼入刚刚到达前更新其位置。采用这种方式，更 新开销和寻呼开销都可以最小化。然而，现实总是比理想中的要差，许多研究者认 为m t 的呼入是一个p 0 i s s o n 分布。因此，两次连续的呼入间隔时间服从独立的指 数分布，其密度函数，o ) 一 e “【掉2 6 1 ，这里a 表示呼入到达率。一些学者还假设了 离散的情况，因此，呼入间隔时间服从具有概率分布函数为f o ) 一1 一( 1 一a y 的几何 分布。 2 3 移动性模型 移动模型在检验无线网络可能存在的各种不同问题中起着重要的作用，包括资 源分配，过区切换和位置管理。一般而言，移动模型取决于移动用户的速度、方向 或移动历史。位置管理中常用的几种移动性模型包括：属于聚合移动模型的流体流 动( f l u i df l o w ) 模型和重力( g r a v i t y ) 模型，属于个体移动模型的对称随机行走 ( r a i l d o mw a l k ) 模型、马尔可夫行走( m a r k o vw o r k ) 模型、基于蜂窝驻留时间和高斯 马尔可夫( g a u s s m a r k o n 模型，各种移动模型的分类如图2 5 所示。 1 1 硕士学位论文 m a s t e r st h e s i s 2 4 位置更新与寻呼 图2 5 不同移动性模型的分类 位置管理包括两个基本操作，即位置更新和寻呼查找。位置管理结构本质上是 基于m t 的移动性和叫入特性的，位置更新处理过程使系统知道m t 的位置，以便 为到达的呼入确定路由；寻呼处理过程是向m r 注册区内的所有小区发送寻呼信息。 位置更新就是m t 周期性地向网络报告其所在的接入蜂窝，以便移动网络对其 进行鉴权并更新位置记录，作用是m t 用一些触发器通告网络关于它的当前位置信 息，这样可以避免通过全部可能的b s 穷举查找该m t ，节约有限的信道资源。位 置更新操作主要包括身份验证和数据库更新。 寻呼查找就是向移动通信网络查询用户的位置记录，以此来得知m t 的位置信 息，其基本过程是网络寻找确定的访问端口以到达该m t 。如果寻呼成功，m t 将 发送一个寻呼响应到网络，通过寻呼可以建立网络与m t 的连接。寻呼主要操作包 括数据库查询和终端寻呼。 2 4 1 位置更新 为了减少位置的不确定性，每个m t 必须不时的报告它的位置。位置更新过程 始于m r 通过上行链路发送更新消息，接着是一些更新位置数据库的信号传输过程。 位置更新算法可归类为全局和局部两个方面。如果在同一组蜂窝中的所有用户都更 新它们的位置，则更新算法是全局的；如果允许单个的用户决定何时何地执行位置 更新，则更新算法是局部的。 如果当用户移动到一组事先定义好的蜂窝必须执行位置更新而不管移动终端 的移动性，则更新是静态的。在静态算法中，是基于网络拓扑结构而触发位嚣更新 的；如果移动终端位置更新在何蜂窝中执行取决于它的移动性，则更新是动态的。 在动态的算法中，是基于用户的呼入移动模式来进行位置更新的。 近年来的研究中学者们所提出的一些常见的位置更新策略【2 ”q 包括：选择性的 l a ( s e l e 鲥v el a ) 更捌3 、基于侧信息p m f i l e b a s e d ) 【3 2 l 、基于移动次数( m 0 v 鼬e n t b a s e d ) 【刎、基于计时器m e r _ b a s e d ) 1 2 0 l 、基于距离i s t a n c c - b 鹳e d ) 【捌、基于预测性 的距离( p r e d j c 【i v ed i s t a n c c - b a s e d ) p 习、基于状态( s t a t e b a s e d ) 【3 4 】的更新策略等等。 2 4 2 寻呼查找 终端寻呼是网络用来决定一个特定m t 糖确位置的处理操作，寻呼操作由网络 来执行的。当m t 有呼入时，网络将在m t 所有可能驻留的蜂窝中去查找，定位其 所在的蜂窝，然后将呼叫路由到相应的b s 。所寻呼的蜂窝的个数取决于位置更新 操作的执行策略。 因为寻呼过程是要消耗带宽的，寻呼开销与选举周期是成比例的，也与每个周 期中的蜂窝数有关。考虑到寻呼的开销，有些策略对寻呼时延( 周期) 予以了限制。 在寻呼开销和寻呼时延之间存在折衷。如果不限制时延，寻呼操作将会对m t 所有 可能驻留的蜂窝按概率递减的顺序依次进行寻呼，这会带来最小的寻呼开销。如果 同时对所有的蜂窝进行选举，则导致寻呼时延最小化而寻呼开销最大化。现在许多 研究者都朝着限制寻呼时延且最小化寻呼开销的方向进行研究瓯3 ”9 】。目前学者们 提出的一些主要的寻呼策略包括：覆盖寻呼l a n k c tp o l l i n g ) 、最短距离优先寻呼、 基于用户所在位置区概率大小依次进行的寻呼、速度寻呼( v c l o c i t yp a 峦n d 4 0 i 、线性 寻呼( u n e p a 百n g ) 【4 1 】等几种寻呼策略。 2 5 研究小结 目前提出的位置更新算法大多还是基于l a 的执行方案，依靠相同的位置更新 机制。如果m t 在它当前的l a 中，一个位置更新过程将被执行。寻呼在l a 内的 p a 中进行。p a 的范围根据不同的策略等于或小于l a ，或动态变化。另外一些位 置更新的触发不需要把网络覆盖区域分割成l a 。网络中唯一有用的位置信息是和 m t 最后联系的位置点。这些非源于l a 的位置更新方法是基于单个用户的，可以 使参数对每个独立用户达到最优化。另一个优点是位置更新实际上可以被分配给网 络中全部的蜂窝，比源于l a 的方法更能达到均匀分布信令负担。它的一个重要问 题是数据库系统和整个网络架构的容量。不同于基于l a 的概念，非源于l a 的方 法常常没考虑到建立连接产生的信令开销和在骨干网络中的路由以及现在的固定 基站设备中没有储存这些信息的数据库。要采用这种方法得对现有系统的软硬件进 行重大调整，耗资也是十分巨大的。 根据研究，在网络中执行h u t 和v l r 位置更新通常比寻呼操作消耗更多的无 线和有线带宽设备和计算机资源，更新操作产生的开销大约是寻呼操作产生开销的 1 0 倍。因此，大部分的位置管理研究着眼于减少位置更新产生的信令消耗和网络数 据库资源。本文也建立在h i r ，恳两级数据库结构的基础上分别在接下来的两章 中探讨了两种新的位置更新策略。 1 4 硕士学位论文 m a s t e r st h e s i s 第三章指针推进位置管理策略 p c s 网络为移动用户提供了无线通信服务，使得它们在任何时间、任何地点都 能提供任何形式的服务。为了有效的服务这些移动用户，系统就需要跟踪它们的当 前位置。位置管理成为个人通信服务网络中的一个重要研究课题。目前盛行的位置 管理策略中一类是以两级数据库结构h i 取，r 为基础。两级结构简单且易于实现， 但是由于存在不可扩展性和移动用户位置管理开销太大等问题，使它不适合于许多 新的移动计算应用。为提高系统的性能，目前很多学者已提出一类用多级层次结构 来组织数据库的位置管理策略。多级层次结构能够提高定位移动用户的能力，但为 了维护移动用户的位置而进行位置更新的代价还是非常大的。 本章将通过对现有的几种位置管理策略的分析，针对其不足之处，以两级数据 库结构为基础，提出一种基于阈值的两级指针推进移动性位置管理策略，以降低系 统位置管理的总开销，提高通信效率与效益。 3 1 基本位置管理策略 目前，一些国家( 包括我国) 正在使用的移动通信系统( 如i s 4 0 ，i s 5 4 ，i s 9 5 ， g s m ) 均使用两层数据库：归属位置寄存器m 且和访问位置寄存器v 1 且进行位置 管理，其基本结构如图3 1 所示。 链接 基站 。蜂窝w s o 一 图3 1 移动通信网络基本结构 硕士学位论文 m a s t e r st h e s i s 在使用两级数据库结构的位置管理策略中，h l r 记录了移动用户永久的位置及 相关信息，v l r 包含当前位于其服务区内的移动用户的位置及相关信息。为了便 于跟踪移动用户，个人通信网络被