（计算机科学与技术专业论文）移动计算中的位置管理.pdf

国防科学技术大学研究生院学位论文 摘要 f 移动通信技术的飞速发展使得传统的固定网络应用环境变得更加灵活与不稳 定、用户可以通过各种无线连接方法访问数据库，获得查询结果，移动计算也 因此应运而生。与传统的分布式计算相比，移动计算面临着许多新的挑战。而 位置管理是移动计算中关系其移动断接特性的重要问题，也是移动数据库管理 必须面临的问题。 位置管理主要包括对移动用户位置的登记、更新与寻呼。随着网络中移动用 户的增加，移动通信向个人通信( p e r s o n a lc o m m u n i c a t i o n ) 的发展，位置管理 急待解决的问题有：第一，要具有可扩充性，解决未来p c n ( p e r s o n a l c o m m u n i c a t i o nn e t w o r k s ) 中，位置管理引起的网络流量激增，从而降低系统性 能的问题。第二，要具有适应性，解决未来移动用户的移动方式多样，移动与 呼叫模型多样的问题。 针对上述位置管理面临的问题，本文提出一种综合的位置管理方案。首先提 出了基于混合蜂窝系统的三层树型位置管理系统模型。在此基础上，提出了分 区的位置管理基本策略和按距离寻呼的寻呼方法本文针对移动的边界问题和 移动局部性利用问题提出两种改进策略，即分区覆盖和前向指针的改进应用。 其中前向指针的改进应用特别针对呼叫集移动与呼叫模型，提出了指针链的选 择消解和指针链环的断环处理。通过对模拟结果的分析比较，上述位置管理方 案可以有效减少由于位置管理引起的网络开销，同时保证位置管理本身的有效 性。 关键词：移动计算，位置管理， 量之前向指针，分区覆盖，指针消解 国防科学技术大学研究生院学位论文 a b s t r a c t t h e r a p i d l ye x p a n d i n gt e c h n o l o g y o fw i r e l e s sc o m m u n i c a t i o nw i l lm a k e t r a d i t i o n a r y n e t w o r k sm o r ef l e x i b l ea n du n s t e a d y u s e r sc a na c c e s sd a t a b a s e so r r e c e i v et h e i r q u e r y r e s u l t s t h r o u g h a l lk i n d so fw i r e l e s sc o n n e c t i o n a n da sa c o n s e q u e n c e ，m o b i l ec o m p u t i n gh a se m e r g e d c o m p a r e dw i t ht r a d i t i o n a r yd i s t r i b u t e d c o m p u t i n g ，m o b i l ec o m p u t i n g h a st of a c em a n yn e w c h a l l e n g e s l o c a t i o nm a n a g e m e m i so n eo ft h em o s ti m p o r t a n ti s s u e si nt h ef i e l do fm o b i l ec o m p u t i n gr e l a t i n gw i t h m o v i n ga n dd i s c o n n e c t i o n t h a ti sa l s oo n eo f t h em o s ti m p o r t a n ti s s u e st h a tm o b i l e d a t a b a s e sm u s td e a lw i t h l o c a t i o nm a n a g e m e n tm a i n l yi n c l u d e sr e g i s t e r , u p d a t i n ga n dp a g i n go fm o b i l e u s e r s l o c a t i o n s l o c a t i o nm a n a g e m e n th a si t so w n c h a l l e n g eb e c a u s eo f t h ef a c tt h a t t h en u m b e ro fm o b i l eu s e r si se x p a n d i n gd r a m a t i c a l l ya n dt h em o b i l ec o m m u n i c a t i o n i s d e v e l o p i n gt op e r s o n a lc o m m u n i c a t i o n f i r s t l y , l o c a t i o nm a n a g e m e n th a s t ob e s c a l e a b l et or e s o l v et h em a t t e rt h a tt h el a r g et r a f f i cr e s u l t i n gf r o ml o c a t i o nm a n a g e m e m i nt h ec o m m u n i c a t i o nn e t w o r km a yl o w e rt h ep e r f o r m a n c eo ft h ew h o l es y s t e m s e c o n d l y , l o c a t i o nm a n a g e m e n th a st om e e tt h ev a r i a n c eo f m o b i l eu s e r sa n dm o d e l s a b o u tm o v i n ga n dc a l l i n g t h i sp a p e r p r e s e n ta ni n t e g r a t e dl o c a t i o nm a n a g e m e n ts t r a t e g yt or e s o l v et h et w o i s s u e sm e n t i o n 酣a b o v e w ep r e s e n tat h r e e - t i e rt r e eb a s e dc o m b i n e dc e l l u l a ra so u r l o c a t i o nm a n a g e m e n ts y s t e mm o d e l a n dt h e nw ed i s c u s sb a s i cl o c a t i o nm a n a g e m e n t a l g o r i t h mo fp a r t i t i o na n dp a g i n gm e t h o d t h a ta c c o r d st od i s t a n c e t h e r ea r ea l s ot w o i m p r o v e da l g o r i t h m sc a l l e dp a r t i t i o nc o v e r i n ga n dm e n d e df o r w a r d i n gp o i n t e r t h e f o r m e ri sa b o u tt h eb o u n d a r yq u e s t i o na n dt h el a t c r , l o c a l i t yo f m o v i n g i n t h em e n d e d f o r w a r d i n gp o i n t e ra l g o r i t h m , w ec o v e y s e l e c t e dp u r g i n ga n dl o o pb r e a k i n ge s p e c i a l l y a b o u tt h em o d e lo fc a u e r - s e tm o v i n ga n dc a l l e r - s e tc a l l i n g a tl a s t ，w ec a nm a k ea c o n c l u s i o nt h a to u rs t r a t e g yc a nr e d u c et h e 倘ci nc o m m u n i c a t i o nn e t w o r kr e s u l t i n g f r o ml o c a t i o nm a n a g e m e n te f f i c i e n t l ya n dc a np e r f o r mi t sm a n a g e m e n tt a s ke f f i c i e n t l y k e y w o r d ：m o b i l ec o m p u t i n g , l o c a t i o nm a n a g e m e n t , p a r t i t i o n ，f o r w a r d i n g p o i n t e bp a r t i t i o nc o v e r i n g , p o i n t e rp u r g i n g i i 国防科学技术大学研究生院学位论文 第一章绪论 随着计算机技术、网络技术与通信技术的发展，世界进步趋势之一体 现为对信息占有的普遍化趋势，一是信息本身范围扩大，二是共享信息的 人群扩大。正是在此趋势的推动下，计算模式也有了相应变革，从集中式 计算到网络上的分布式计算，再到利用无线通信接入的更加灵活多变的移 动计算，这一直是计算机界的前沿研究方向。 1 1 什么是移动计算 计算模式的发展与作为其核心的数据库技术的发展是紧密相关的。数 据库技术由集中式数据库发展到分布式数据库。计算模式也相应从集中计 算过渡到分布计算。分布计算利用固定网络连接，使具有独立自治功能的 计算机互相协作，完成计算任务。比之集中计算，分布式计算具有更多的 优点，如可扩充性，可靠性，资源共享等。随着移动通信的发展，用户可 以通过无线电话，p d a ( 个人数字助理) 或便携式计算机与网络无线连接， 这就保证了用户的自由移动性与通信的灵活性。而无线寻呼、蜂窝电话、 无线局域网以及卫星通信技术的飞速发展又使得无线移动通信成为目前最 有发展前景的热点之一。世界各地的科研机构、标准化组织以及业界纷纷 对这一领域表示极大关注，相应地，移动数据库与移动计算必须以一种独 立的范式提出并加以讨论。一般地说，作为实现无线移动通信的计算范式 就叫做移动计算( m o b i l ec o m p u t i n g ) ，也叫漫游计算( n o m a d i cc o m p u t i n g ) 。 移动数据库是一种更加灵活，更加不稳定的分布式数据库，移动计算模式 是针对移动数据库的计算模式f 1 】。随着传统移动通信概念向个人通信 ( p e r s o n a lc o m m u n i c a t i o n ) 的飞跃，移动计算也相应面临着许多新问题。 1 2 移动通信的发展 个人通信是人类通信的最高目标，它使用各种可能的网络技术，实现 任何人在任何时间、任何地点与任何人进行任何种类的信息交换。表l 给 出了p c n ( p e r s o n a lc o m m u n i c a t i o nn e t w o r k s ) 的应用要求1 2 】。目前，以个人 通信为目标的移动通信系统按所采用的无线技术可以分为低功率系统、移 动卫星系统、无线l a n w a n 、专用移动通信系统、寻呼系统和数字蜂窝 系统。 低功率系统主要用来提供公用无绳电话业务，采用t d m a ( 时分多址) f d m a ( 频分多址) 的多址方式，话音编解码器的数据传输率为3 2 k b i t s ， 其中最流行的是欧洲的c t - 2 系统。 第1 页 国防科学技术大学研究生院学位论文 未来p c n 的典型应用要求 应用业务类型业务质量比特率范围 允许呼损 话音传输c o ，c b r 允许低中等程度的信元丢失 24 3 2 k b i t s 要求同步 允许呼损 数字音频c o ，c b r要求低的信元丢失1 2 8 5 1 2 k b i t s 低时延抖动 电话会议c o ，c b r 或统计复用( 对于v b r ) 6 4 3 8 4 k b i t s 多媒体通信 c o 僵r 允许呼损 ( 电话会议) 数字电视允许低伸等程度的信元丢失 1 - 6 m b i t s 低时延抖动 ( t v v c r 质 量) 允许呼损 数字h d t v c o c b r 允许低冲等程度的信元丢失 1 5 2 0 m b i t s 低时延抖动 一般计算机数 c l 无呼损 b e s te f f o r tp a c k e t 要求低信元丢失 0 1 - 1 m b i t s 据 可有中等时延和抖动 c l 低传输速率 b e s te f f o r tp a c k e t 无呼损 9 6 1 2 8 k b i t s 电子邮件 允许低的信元丢失 可有大的时延 高速数据( 文 c l 高传输率 件传输、多媒 突发模式的分组 要求很低的信元丢失 1 一1 0 m b i t s 体) 数据 可有中等时延和抖动 * c o 一- 面向连接；c l - 一无连接tc b r - 固定比特率；v b r - 一可变比特率 表l 移动卫星系统主要分为两大类，一类是同步轨道移动卫星系统，一类 是低轨道卫星移动通信系统。其中低轨道卫星移动通信系统轨道高度距地 约为5 0 0 2 0 0 0 公里，因此传播损耗小，时延小，频率复用有效，可多星互 为备用，能全球覆盖，应用前景比较广阔。目前低轨道移动卫星系统较成 熟的有铱( i r i d i u m ) 系统，全球星( g l o b a l s t a r ) 系统和t e l e d e s i c 系统。 无线l a n w a n 是移动通信中的一个重要领域，1 9 9 7 年6 月制定了无 线局域网标准i e e e 8 0 2 1 1 。提供一点对多点接入和点对点中继等工作模式， 为移动用户提供了可以代替有线的高速高效的联网解决方案。 专用移动通信系统中最主要的一种是集群无线通信系统。集群无线通 第2 页 国防科学技术大学研究生院学位论文 信系统是多个用户共用组无线电信道，动态分配使用这些信道的专用移 动通信系统，多用于交通、公安等部门的指挥调度。目前新一代的数字集 群系统的代表有爱立信公司的e d a c s 系统，摩托罗拉公司的m i r s 系统。 它们的主要特点是共同频率、共用设施、共享覆盖区、共享通信业务、共 同分担费用等。 目前的无线寻呼系统在现有的基础上推出加强型的系统并实现局部地 区的联网。欧洲制定了e i m m s 的标准，p h i l i p s 推出了a p o c 高速寻呼 编码方式，摩托罗拉推出了f l e x 高速寻呼方式。 蜂窝系统可以提供广阔的覆盖范围，支持无线语音双工通信，可以较 好地管理用户移动性。蜂窝系统的发展可划分为三代；第一代是以f d m a 技术为标志的模拟蜂窝系统，如美国的a m p s 系统，以及模拟无绳电话系 统。模拟蜂窝系统中，语音按电路交换的形式在窄带宽信道上以频率调制 的方法传输，系统对每个单元( c e l l ) 的控制放在m s s ( m o b i l es u p p o r t s t a t i o n ) 或者基站( b a s es t a t i o n ) 上，m s s 和基站作为固定网的一部分以 无线方式连接移动用户。模拟蜂窝系统以低效低速率提供模拟话音传输和 数据传输( 1 2 96 k b p s ) 。第二代是以t d m a 和c d m a ( 码分多址) 技术 为标志的数字蜂窝系统，如g s m ，以d e c t 、p a c s 、c t 2 为代表的数字无 绳电话系统以及通信工业协会制定的i s 5 4 和i s 9 5 标准。这也是当前应用 的主流移动通信系统，它采用数字调制信号，提供“类i s d n ”的服务。在 提供语音服务的同时也提供不同的数字服务如：寻呼、无线电传真和其他 高数据传输率的网络无线接入服务。移动设备本身具有了更多的控制功能， 包括控制越区切换、接受电源报告、扫描邻近基站、编码解码等。数字蜂 窝系统有较高的误码率和较低的有效数据传输率( 9 1 4 k b p s ) 。第三代是以 个人通信为目标的全球移动通信网p c n 。该网在i n j 中称为f p l m t s ( t h e f u t u r ep u b l i cl a n dm o b i l et e l e c o m m u n i c a t i o n ss y s t e m ，1 9 9 6 年更名为i m t 一 2 0 0 0 ) ，在欧洲称为u m t s ( u n i v e r s a lm o b i l et e l e c o m m u n i c a t i o n ss y s t e m ) 。 i m t 2 0 0 0 是供全球范围使用的移动通信系统，其特点有：第一，它是第一 个采用全球统一标准的移动通信系统，用户可以在全球范围内实现漫游； 第二，它是一个针对宽带数据通信设计的系统，工作在2 0 0 0 m h z 频段，提 供2 m b p s 的传输速率和5 m h z 以上的带宽，不仅进行话音通信，更可以进 行移动的多媒体通信；第三，它将把固定网、卫星网和地面移动网结合成 一个综合的整体网络。第三代移动通信标准的实施将使电信网和计算机网 络更加紧密的结合，消除传统话音通信和数据通信之间的界限。 关于第三代移动通信，目前提出的协议和主要技术标准主要有w a p ( 无 线应用协议) 、g p r s ( 通用分组业务) 、b l u e t o o t h ( 蓝牙) 技术等。 第3 页 国防科学技术大学研究生院学位论文 其中w a p 专为移动i n t e m e t 设计，解决手机上网问题。w a p 规范包括 无线应用环境和无线协议两大部分，无线应用环境独立于网络和设备，定 义了无线构造语言、无线电话应用接口及w a p 内容格式。无线协议包括无 线会话层、无线传输层安全机制、无线传输协议、无线网络接口定义等。 目前w a p 的标准化工作正在完善中。 w a p 解决了手机与i n t e m e t 协议互通的问题，但它的速率与传统话音 通信一样，为9 6 k b p s 。而g p r s 则可以解决这个问题。g p r s 在现有的电 路交换网上叠加一个基于分组的空中接口，分组交换仅当用户在发送或接 收数据时g p r s 无线资源才被使用，并可以同时在几个用户之间共享一个 信道。它的传输速率可达1 6 0 k b p s ，最高可达1 7 1 2 k b p s 。 蓝牙技术是公开的无线数据和话音通信标准，它将所有的技术和软件 集成于9 r a m 9 m m 的微芯片内，为无线和静态通信环境提供带保护的特殊 连接，以取代目前许多专用的电缆设备。其同步语音信道支持6 4 k b p s 的 数据传输率，非同步信道可支持非对称的最大速率为7 2 1 k b p s 的单向速率 ( 此时另一方向为5 7 6 k b p s ) 或者4 3 2 6 k b p s 的上下链路对称速率方式。 1 3 移动计算环境的网络结构 移动计算的网络结构研究如何经济高效地把具有无线接口的固定节点 连接起来，向用户提供个人通信以及移动数据库的服务业务。几种具有代 表性的固定网络结构如下： 一 图卜1 使用l a n 的分布式交换和控制结构 第4 页 国防科学技术大学研究生院学位论文 一、a t & tb e l ll a b 提出的利用电信网络的分布式交换和控制结构 如图1 1 所示 3 】，来自微蜂窝群的呼叫通过信道传到宏蜂窝基站，宏 蜂窝基站通过数字干线t s l c 与本地交换局相连，或者与i s d n 相连。图 中的l a n 主要服务于需要越区切换的移动用户，主站的作用是处理网络中 发起的呼叫，并为该呼叫选择合适的本地交换局或是基站。 二、w i n l a b 提出的蜂窝分组交换结构 如图1 2 所示，蜂窝分组交换利用光纤城域网将基站和控制器连接起 来，将网络的控制功能分散在城域网的接口单元中，采用虚电路分组交换 来建立无线终端和固定网络之间的链路。采用的主要协议1 e e e 8 0 2 6 、i s d n q 9 3 1 和p r m a 等。 b i u ： h i u ： v i u ： t i u ： c 工u ： g i u ： h d b ： v d b ： s s 7 ： 基站 归属 访问 干线 蜂窝 网关接口单元 归属数据库 由獭耋笔帮库图卜2 蜂窝分组交换 7 号信令 一一一、 三、n t t 提出的基于光纤的固定网络结构 如图1 - 3 所示【4 】，基于光纤的固定网络结构采用集中控制的方式将常 规基站中的调制解调器( m o d e m ) 和控制部分都集中到中心站，而基站中 仅有发射机部分，中心站到基站采用光纤传输。图中d s 的作用是根据业务 的需要，可将载波分配到任何蜂窝。这种结构的特点是布设容易。由于基 站仅是宽带收发信机。所以在需求增加时，可动态共享m o d e m 等设备，而 不需要增加新设备。 总的说来，移动计算的网络结构都是由固定网以某种形式的无线接口 第5 页 国防科学技术大学研究生院学位论文 连接上无线网络形成的，所以其结构可以由图1 - 4 统一表示。【l 】 图卜3 基于光纤的固定网络结构 图1 4 移动计算系统结构简图 如图卜4 所示，系统的固定节点分为两类，一类是传统意义上的固定 节点( f i x e dh o s t ) ，一类是具有无线接口的固定节点( m s s ) 。其中m s s 通过各种无线通信网与移动用户( m u ) 相连接，各移动用户以无线方式共 享网络资源。可以认为移动计算环境是传统固定网络在无线领域的个扩 充。 r a c e 计划中的r a c e 2 0 2 6m o n e t 工程提出和研究u m t s 的网络结 构问题，指出u m t s 作为现代固定电信业务网的无线延伸，提供与固定网 络用户享用的相同电信业务。通用的p c n 的构架如图1 5 所示【5 】，由通用 信息接入网络层( u n i v e r s a li n f o r m a t i o na c c e s sn e t w o r k ) 、宽带信息传输网 第6 页 国防科学技术大学研究生院学位论文 络层( b r o a d b a n di n f o r m a t i o nt r a n s p o r tn e t w o r k ) 、宽带信息传输网络层 ( p e r s o n a lc o m m u n i e a t i o ns e r v i c en e t w o r k ) 、智能信令控制( i n t e l l i g e n t s i g n a l i n gc o n t r 0 1 ) 和统一网管( u n i f i e dn e t w o r km a n a g e m e n t ) 组成。通用 信息接入网络层提供网络无线接入功能，包括空中接口的信道编解码、差 错控制、调制解调、同步、信道处理、信令和带宽管理、无线电资源管理、 移动性管理、安全、保密和认证等功能。宽带信息传输网络层支持话音、 数据、图象、视频和其他宽带业务和应用。未来的用户数量激增，高密度、 高移动性的用户要求的位置登记、跟踪和更新会产生大量非呼叫类业务负 荷，这就需要较高带宽的传输和交换系统。宽带信息传输网络层提供网络 业务的管理，包括配置、监测定制等接口的管理和控制。智能信令控制支 持最终用户与网络之间的虚电路通路信道连接、同步、智能路由和特 殊网络业务功能( 如寻呼和移动性管理) 。统一网管保证全局的q o s ，提供 整个网络的中心集成化智能控制。 图卜5 未来个人通信网的构架 u m t s 的结构与上述的通用结构相似，由三部分组成：u t m s 无线接 入系统，提供工作在1 8 8 5 2 0 2 5 m l - i z 和2 1 1 0 2 2 0 0 m h z 的高度灵活高效的 无线电接口。u t m s 核心( 交换) 网络，提供交换与传输功能，与b - i s d n 相集成，并与b i s d n 前的网络兼容f 7 】。u t m s ( 业务) 控制网络，将完全 支持个人移动性和终端移动性【6 】。 第7 页 国防科学技术大学研究生院学位论文 1 4 新的问题与挑战 随着移动通信向个人通信的发展，越来越多的用户使用移动电话、掌 上型电脑、膝上型电脑、p d a 等便携设备通过无线接e l 与固定网络相连， 和传统的固定用户一样共享网络资源，同时比固定用户更加灵活、方便。 这样的移动网络计算环境与传统固定网络的分布计算环境有很大不同。例 如，由于电池能源的限制，移动设备会经常处于断接状态( 分为主动断接 和被动断接) 。由于移动特性，用户也经常做越区切换( h a n d o f f ) 。由于无 线带宽的有限性、可变性以及无线网络不对称性( 数据向上传送的代价与 向下广播的代价比约为1 0 ：1 ) ，应用必须增加网络环境的移动参数。所有 这些对用户来说都应该是透明的，即p c n 的用户享受的服务应与固定网用 户没有大的区别。在新的移动计算环境下，数据如何分配，查询如何处理， 位置如何管理，电池的有限能源对数据访问有什么限制，如何处理断接， 如何恢复数据等等都是移动计算模式面临的新的挑战。这些新问题以及相 应的研究方向大致分为两类： 一、移动性、断接性与可扩展性 1 、位置管理( 包括位置相关查询) 2 、配置管理( 包括数据分布、复制与广播算法) 3 、断接前后c a c h e 一致性 4 、越区切换与错误恢复 5 、频繁断接条件下的事务处理 6 、安全问题 二、新的信息媒体和资源限制。 1 、无线信息服务 2 、省电数据管理与查询 3 、小型的非键盘输入用户界面 1 5 位置管理的重要性与意义 位置管理是针对移动性提出的课题，也是最能反映移动计算特点的技 术。 移动性的概念有两类【7 】，即终端移动性( t e r m i n a lm o b i l i t y ) 和个人移 动性( p e r s o n a lm o b i l i t y ) 。现在的p s t n 中，用户、终端及网络的关系是一 第8 页 国防科学技术大学研究生院学位论文 一对应的，用户与终端的关系也是一一对应的，终端通过网络接入点与网 络建立唯一的对应关系，网络仅通过接入点来识别不同的终端和用户。移 动通信中，支持终端移动性，即网络通过终端的唯标识识别终端，而不 再通过网络接入点来确定终端。它允许终端在网络覆盖范围内移动，终端 可通过任网络接入点接入网络。个人移动性是指用户和终端也不再有一 一对应的关系，网络仅对用户进行识别，每个用户都可以从任何一个终端 上收发网络呼叫。 个人通信的一个本质特点就是支持终端移动性和个人移动性，为了使 得用户可以在系统覆盖范围内任意移动的同时能够收到呼叫或者是查询结 果，就必须有一个高效的位置管理系统来跟踪移动用户的位置。一般地， 位置管理放在o s l 系统模型的数据链路层或网络层，当建立呼叫或是网络 接入发生变化时，应对上层透明。一些新的应用也需要移动用户的位置信 息，如回答移动用户包括位置在内的查询“离我们最近的旅馆”或是更新 网络参数如“对我们可用的打印机”等等。对于应用应该怎样要求和使用 位置信息并没有统一的标准，i l l i n o i s 大学就在应用层研究使用合适的数据 结构来保存位置的现状、历史信息和未来变化趋势【8 】。但大多数还是把位 置信息作为目录进行管理。 位置管理问题是所有移动网络系统( 蜂窝系统、无线l a n s 、卫星通信 系统等) 面临的问题，大致有两个基本的操作，即：移动用户本身的位置 更新( 可用m o v e 代表) 和其他用户对移动用户的呼叫建立( 可用c a l l 代 表) 。这两个基本操作反映为位置位置管理问题中的三个方面，即：位置登 记( r e g i s t e r ) 、位置更新( u p d a t i n g ) 和位置寻呼( p a g i n g ) 。位置登记解 决把移动用户的实时位置信息通知位置管理服务器的问题。位置更新解决 在移动用户的位置发生变化时，相应位置管理服务器的目录变化问题。位 置寻呼解决有效确定移动用户当前位置的问题。 位置管理问题涉及到网络响应和网络流量。网络响应关系到位置管理 服务器的处理能力，位置数据库的查询和响应。网络流量关系到位置的登 记、更新和寻呼给网络附加的通信量和延迟。位置管理所要达到的目标就 是尽可能减少与位置处理相关的业务量，同时尽可能快速确定移动用户位 置，尽可能提供可扩充性，在已有的带宽限制基础上容纳更多的用户。 i 6 本文的研究成果 本文针对移动计算的移动性、断接性和可扩展性的特点，对位置管理 的模型、位置管理基本策略、优化策略以及寻呼方法进行了研究。主要成 果有以下几点： 第9 页 国防科学技术大学研究生院学位论文 第一，提出了接入网、交换网、控制网的三层位置管理系统模型。 第二，针对接入网的混合蜂窝结构，提出了宏蜂窝基础上分区的位置 管理基本策略以及按距离寻呼方法。 第三，针对上述基本策略，提出了两种优化策略，即分区覆盖和前向 指针的改进应用。重点研究了对于移动边界问题的解决和指针 链的选择消解与断环处理方法。 第四，通过对任意移动任意呼叫、邻近经常移动任意呼叫和呼叫集移 动呼叫集呼叫的实验模拟，讨论了不同移动呼叫模型下各种位 置管理策略的优劣。 1 7 论文的结构 本文共分六章。第一章是绪论部分，主要介绍了移动计算的概念、移 动通信的发展和沿革、移动计算面临的新问题与新挑战，介绍了移动计算 中位置管理的重要性与意义，简要介绍了本文的研究内容和成果。 第二章是相关工作述评部分，主要介绍了当前各种不同的位置管理的 系统模型，位置管理策略以及它们的比较。 第三章提出了我们的一种综合的，针对未来p c n 发展的位置管理方 案。 第四章是性能评价部分，针对各种移动与呼叫建立模型，计算和推导 了不同位置管理策略的开销。 第五章是模拟结果及分析部分。通过实验模拟，对各种位置管理策略 的优劣和适用条件进行了讨论。 最后，第六章是结论与对未来工作的展望。 第l o 页 国防科学技术大学研究生院学位论文 第二章相关工作述评 2 1 当前位置管理概况 位置管理是所有移动网络系统( 蜂窝系统、无线l a n s 系统、卫星系统 等) 面临的问题，同时也是移动计算中，移动数据库必须解决的问题，首先数 据库本身存储的数据可能位置相关，其次信息返回的查询用户可能是移动用户。 迄今为止，绝大多数的位置管理策略都是基于两类模型，类是当前数字蜂窝 系统位置管理及其改进，一类是层次位置管理。 2 1 1 数字蜂窝系统位置管理及其改进 以g s m 的两层数据库结构为典型代表的数字蜂窝系统位置管理体系遵循 i s 4 1 标准，是个集中的位置管理解决方案 7 】。它由一个原籍位置寄存器h l r ( h o m el o c a t i o nr e g i s t e r ) 和若干个访问位置寄存器v l r ( v i s i t o rl o c a t i o n r e g i s t e r ) 组成。h l r 存储在其网络内注册的所有用户的文档，用户的位置信息 作为用户文档的一部分，用户以唯一的用户号与它的h l r 形成一一对应关系。 移动用户移动到新的蜂窝小区( c e l l ) ，礤瓜就做相应的更新，对移动用户的呼 叫也发往该用户的h l r 进行寻呼。不同的v l r 管理该网络中不同的位置区域 l a ( l o c a t i o na r e a ) ，每个位置区域由一定量的蜂窝小区组成。v l r 内存储这些 蜂窝小区内当前移动用户的位置信息。当小区a 中建立一个指向移动用户x 的 呼叫，则a 所在的位置区域的且首先响应，找不到x ，再与x 的h l r 建立 连接。移动用户移动到新的位置区域的小区，则旧的v l r 中的x 的目录被删除， 新的v l r 增加x 的目录。每个位置区域对应一个移动交换中心m s c ( m o b i l e s w i t c h i n gc e n t e r ) ，m s c 通过信令系统传输控制信息。这是基本的位置管理方法， 具体过程如图2 1 所示。 呼叫方 图2 - 1g s m 集中地址管理解决方案 第1 1 页 国防科学技术大学研究生院学位论文 改进方法一：缓存( p e ru s e rl o c a t i o nc a c h i n g ) 为了降低其他用户对移动用户的呼叫建立开销，r j a l n 9 等人提出了缓存思 想，即一旦移动用户x 被呼叫，x 的位置信息就被缓存在呼叫发起方的v l r 中， 这样，从该发起的对x 的后续呼叫首先检查本地v l r 的c a c h e ，如果命中，就 可以重用缓存的位置信息而不必远程访问h l r ，适用于c m r ( c a l lt om o v e r a t i o ，呼叫移动比，指移动用户的接收呼叫与本身移动频率的比值) 较大的用 户。为了降低c a c h e 的不命中率，有两种方法，一种是急性缓存，移动用户每 次到达个新位置，关于此用户的所有c a c h e 项都要更新，这样增加了m o v e 开 销。另一种是惰性缓存，即移动操作不引起c a c h e 更新，只有在呼叫建立时，c a c h e 不命中的情况下才引起c a c h e 更新，这样增加了c a l l 开销。对惰性缓存而言， 为了使其开销低于基本方法的开销，则在给定小区内，对任何用户的c a c h e 命 中率p 必须大于某个阈值p 产c n c 。c m 是c a c h e 命中条件下的呼叫建立开销t c 是基本方法的呼叫建立开销。c n 和c k 与h l r 和v l r 的查询开销有关。 例如，某个用户接收的呼叫服从p o i s s o n 分布，到达率为入，其移动的间隔时间 服从指数分布，其均值为u ，这样p = ( + u ) ，c m r 的最小值为p l ( 卜 p t ) 9 ，1 0 。缓存方法有与一般c a c h e 方法一样的共性，都要考虑3 c 不命中以及 c a c h e 替换策略。缓存利用了呼叫的时间局部性与空间局部性，其缺点是c a c h e 失效的附加开销较大，且对用户的移动性有限制。 改进方法二：复制( r e p l i c a t i o n ) 为了降低呼叫建立开销，在选定点复制特殊用户的位置是比较自然的想法。 如果从小区a 中发出的对移动用户x 的呼叫比较频繁，则在小区a 复制x 的位 置可以降低呼叫建立开销。同样，如果用户移动比较频繁，则复制内容的更新 又会带来额外开销。令n 为本地呼叫建立成功超过远程查询的开销差值，b 为 一次复制内容更新的开销，则移动用户x 的位置信息在小区a 中复制是有利的， 仅当下式成立：a c a ，。b u x 。其中c a 。是在给定时间段t 内从小 区a 发出的到x 的呼日q 数( 估计值) ，u x 是在t 内x 移动的次数，即改变位置 的次数。每个用户有哪些节点复制了它的位置，这些节点的信息就保存在它的 h l r 中。复制有两种思想，一种是集中的用户档案复制 1 1 ，一种是分布的工 作集复制 1 2 。 用户档案复制( p e ru s e rp r o f i l er e p l i c a t i o n ) ：它的目标是使得m o v e 和c a l l 的总开销最小，同时保持对每个用户p 。复僚4 信息的最大数量的控制，保持对小 区z 数据库中最大数量信息的控制。令m 为用户数，n 为小区数，r ( p 。) 为有 p 复制信息的节点集合，系统开销可以表示为： 第1 2 页 国防科学技术大学研究生院学位论文 工作集复制( w o r l d n gs e tr e p l i c a t i o n ) ：有这样一个事实，即对每个用户的 频繁呼叫一般都来自少数几个呼叫源，这些呼叫源的集合叫做该用户的工作集。 这样，只需在工作集中复制该移动用户的位置就可以满足大多数要求。这种思 想与用户档案复制的不同之处在于不提供对用户复制信息和对数据库的控制， 因此在小区z j 中提供关于用户p ，的位置信息可以独立于用户p j 来进行。 复制的方法仍然受限于用户的c m r ，只有在c m r 较高时才适用。 改进方法三：前向指针( f o r w a r d i n g p o i n t e r s ) 在这种改进里，当移动用户x 移动到一个新的位置时，x 的i - i l r 并不做更 新动作，而是在x 的旧的v l r 中建立一个指向新v l r 的指针。这样，对给定 用户的呼叫首先查询用户的i - i l r ，确定它的第一个v l r ( 也是用户真正注册的 求) ，然后再沿前向指针找到用户当前的v l r ，建立连接。 9 方法不同之处适用条件 缓存：y 呼叫 急性缓存 每次移动时有c a c h e 的更 x ，则在y 所新开销 在的l a 中缓 呼叫时c a c h e 不命中有更 大c m r 存x 的位置信 惰性缓存 新开销 息。 对每个节点的复制信息和 复制；在经常 用户档案复制每个用户的复制信息要附 呼叫x 的l a 加集中控制 大c m r 中复制x 的位 置信息 工作集复制 复制信息在各个节点以分 布的形式进行本地计算 前向指针；x 移动时，在它 的旧v l r 中必须限制指针链的长度小c m r 加一条指向新 v l r 的指针 表2 第1 3 页 c 口一u ，m 猁户 州 国防科学技术大学研究生院学位论文 与缓存和复制方法相反，前向指针适用于用户的c m r 较低的情况，可以降 低h l r 和v l r 的更新开销，所增加的是指针连接的开销和呼叫时的沿链寻找 开销。 表2 给出了基于数字蜂窝系统位置管理改进方法的比较。 2 1 2 树型层次结构位置管理 与集中式的两层数据库结构位置管理不同，层次结构位置管理采用分布的 方式，位置数据库按层次组织，般是树状结构。处在高层的位置数据库包括 它的下层位置数据库的信息，管理的覆盖范围随着层次的增高而拓广。处在叶 子节点的位置数据库仅覆盖一个蜂窝小区，管理所有在该小区中登记的用户目 录。中间节点包括它的所有子树的信息，存储方式是一个指向下层的指针。数 据库之间以智能信令网互连，例如，位置数据库可以捆绑在电话交换机上，两 个蜂窝小区之间只能通过该层次结构通信d 3 。 层次结构中，l c a ( i ，j ) ( t h e l e a s tc o m m o na n c e s t o ro f n o d eia n di ) 表示节 点i 和节点j 的最近的共同祖先节点。本地呼叫移动比( l c m r x ，) 的表达式也 l c m r t ，= 觚 t 有所不同。对某个中间节点i 而言，对特定的用户x ，有 其中k 是j 的孩子节点。也就是说，中间节点j 的关于用户x 的本地呼叫移动比 是来源于节点j 的所有子树的呼叫与用户x 本身移动次数的比值。 如图2 - 2 ，移动用户x 在节点1 8 ( 蜂窝小区) 处，节点0 有一个目录指针指 向节点2 ，节点2 的x 目录有一个指针指向节点6 ，节点6 再指向节点1 8 。当用 户x 从小区a 移动到小区b 时，从节点b 到节点l c a ( 气b ) ，以及从节点l c a ( a ， b ) 到节点a 的路径上的所有数据库都要更新。例如，用户x 从节点1 8 移动到节 点2 0 ，则节点2 0 、7 、2 、6 、1 8 的数据库都要更新，其中，节点1 8 和节点6 的 数据库要删去x 的目录，节点7 和节点2 0 要增加x 的目录，节点2 更改指针项。 当小区a 中的呼叫方呼叫位于小区b 的用户y 时，寻找过程要从a 出发沿树向 上查询数据库，直至发现含y 的信息的节点，即l c a ( a ，b ) ，再沿指针向下一 直找到节点b ，通过寻呼与y 建立连接。例如，节点2 1 有一个对用户x 的呼叫， 则查询节点2 l 、7 、2 ，直到在节点2 发现x 的信息，再沿节点2 的指针经节点 6 、1 8 ，最后在节点1 8 通过寻呼与x 建立连接。一种改进是保存用户x 的所有 数据库的目录，其指针项都填写x 的真实位置，而不是下层子树信息。如用户 在节点1 8 处则节点1 8 、6 、2 、0 的数据库的x 目录的指针项都填写节点1 8 。这 样在找到l c a ( a ，b ) 后，向下就不必沿链查询数据库。 第1 4 页 国防科学技术大学研究生院学位论文 层次结构使得移动用户不必绑定在h l r 上，可以通过查询层次结构的数据 库来确定用户的位置。考虑到移动用户的移动和呼叫事件的地理局部性，层次 结构减少了通信开销，能够很好解决两层数据库系统中的全局移动问题，即如 果呼叫方与被呼方处在邻近地域，呼叫方也必须首先访问被呼方的h l r 。层次 结构中，呼叫方不必远程访问中心数据库就可以根据附近的位置数据库与被呼 方建立连接。其不足之处在于数据库的更新与查找、查询开销变大，最坏情况 下，需要一直上溯到树根才能找到被呼方的目录。 e 匡1 8 玉1 8 1 lxl 图2 2 树型层次结构地址管理 改进方法一：数