（计算机软件与理论专业论文）移动客户机位置管理技术研究.pdf

华中科技大学硕士学位论文 ! = ! = = = = ! ! = = = = 2 1 = = = = = = = = ! ! = ! = ! = ! ! ! = = ! ! ! ! ! ! ! = ! ! 摘要 移动客户机位置管理是移动数据库中的一项关键技术，其设计的优劣直接影响 了整个系统的效率。论文在分析了现有的各种位置管理方法的优缺点基础上，设计 并实现了国产移动数据库m d m 2 中的位置管理。 在分析了影响位置管理开销的各种因素基础上，提出了一套位置管理开销评价 体系。该体系充分考虑了客户机的移动行为，涵盖了客户机位置管理过程中所涉及 到的数据库和网络操作的各个方面，为位置代理法的提出奠定了理论基础。针对该 评价体系，设计了移动客户机位置管理系统m c l m 的体系结构。 m c l m 用位置代理法有效地实现了m d m 2 中客户机的位置管理。该系统既满 足了位置管理的要求，又能够与其他子系统协同工作。m c l m 借鉴了移动m 网络 模式，修改了其位置注册过程，吸收了复制法和前向指针法的优点，很好地平衡了 位置管理的两个方面即位置更新和位置查询代价，克服了这些方法所存在的问题， 并着重解决了位置代理法的关键技术：客户机工作集、指针链管理、位置代理的安 全性。对于客户机的三种移动方式，m c l m 均提供了位置更新的详细算法，并给 出了简单位置查询的操作流程，设计了所用到的主要数据结构。为了说明并比较位 置代理法的优势，选取复制法和前向指针法作为参考，将三者从理论和实验两个方 面来进行了讨论和验证，并测试了c m r 、工作集大小等因素对位置管理性能的影 响，为以后继续深入研究指明了方向。 关键词：移动薮：位置者垣_ 位置更新；位置主葡7 位置枉：7 工宿羹j 移；r 行为 - 华中科技大学硕士学位论叉 a b s t r a c t l o c a t i o nm a n a g e m e n to f m o b i l ec l i e n ti so n eo f k e yt e c h n o l o g i e si nm o b i l ed a t a b a s e t h ed e s i g no fl o c a t i o nm a n a g e m e n tc a r l _ d i r e c t l ya f f e c tt h ep e r f o r m a n c eo fs y s t e m t h i s p a p e ra n a l y z e da d v a n t a g e sa n dd i s a d v a n t a g e s o f “ik i n d so fl o c a t i o nm a n a g e m e n t s t r a t e g i e se x i s t e d ，d e s i g n e d a n d i m p l e m e n t e d t h el o c a t i o nn a a n a g e m e n ti nm d m 2 w e p r o p o s e das u i to fe v a l u a t i o ns y s t e mo fl o c a t i o nm a n a g e m e n te x p e n s eo nt h e b a s eo fa l lk i n d so ff a c t o r sa f f e c t e dl o c a t i o nm a n a g e m e n tc o s t t h i ss y s t e mc o n s i d e r e d e f f e c t i v e l yb e h a v i o r so fm o b i l ec s e n t ，c o v e r e de v e r yp a r to fd a t a b a s ea n dn e t w o r k o p e r a t i o nd u r i n gm a n a g i n gl o c a t i o n ，w h i c he s t a b l i s h e dt h eb a s eo fp r o p o s i n gl o c a t i o n a g e n tm e t h o d a i m i n ga tt h i se v a l u a t i o ns y s t e m ，w ed e s i g n e dt h es y s t e ms t r u c t u r eo f m c l m ( l o c a t i o nm a n a g e m e n to f m o b i l ec l i e n t ) m c l m e f f e c t i v e l yr e a l i z e dt h el o c a t i o nm a n a g e m e n to fm o b i l ec l i e n ti nm d m 2 b y a d o p t i n gl o c a t i o na g e n tm e t h o d m c l mc a nn o to n l ys a t i s f yt h en e e do fl o c a t i o n m a n a g e m e n t ，b u ta l s oc o o p e r a t ew i t ho t h e rs u b s y s t e m m c l mu s e dt h em o b i l ei pf o r r e f e r e n c e ，m o d i f i e dt h e p r o c e s s o fl o c a t i o n r e g i s t e r ，a b s o r b e dt h ea d v a n t a g e so f r e p l i c a t i o na n df o r w a r d i n gp o i n t e r ， b a l a n c e dt h ec o s to ft w o p a r t s ：l o c a t i o nu p d a t ea n d l o c a t i o n l o o k u p i nl o c a t i o n m a n a g e m e n t m c l mg o t o v e rt h e d i s a d v a n t a g e s o f r e p l i c a t i o na n df o r w a r d i n gp o i n t e r ，s o l v e ds e v e r a lk e yt e c h n o l o g i e s ：c l i e n t sw o r k s h e e t s 、 m a n a g e m e n to f p o i n t l i n ka n ds e c u r i t yo f l o c a t i o na g e n t w e p r o p o s e d d e t a i l e da l g o f i t h r n o fl o c a t i o nu p d a t ea b o u tt h r e em o v i n gb e h a v i o r sa n ds i m p l el o o k u p b e s i d e st h e s e ，w e d e s i g n e dm a i nd a t as t r u c t u r e h io r d e rt oe x p l a i na n dc o m p a r el o c a t i o na g e n tm e t h o d w i t hr e p l i c a t i o na n d f o r w a r d i a gp o i n tm e t h o d ，w ed i s c u s s e da n dv a l i d a t e df r o mt h e o r y a n a l y s i sa n de x p e r i m e n t ，w h a t sm o r e ，w et e s t e df a c t o r sl i k ec m r 、w o r k s h e e th o wt o a f f e c t e dl o c a t i o nm a n a g e m e n tc o s t ，w h i c hd i r e c t e du st or e s e a r c h d e e p l y k e yw o r d s ：m o b i l ed a t a b a s e ；l o c a t i o n m a n a g e m e n t ；l o c a t i o nu p d a t e ；l o c a t i o nl o o k u p l o c a t i o na g e n t ；w o r k s h e c t ；m o v i n gb e h a v i o r i i 华中科技大学硕士学位论文 1 1 课题研究目的及意义 i 绪论 随着计算机网络的日益发展，人们对通过网络获取信息的要求越来越高，这不 仅体现在获取和提交的大信息量，更体现在对获取信息的实时性和便易性的迫切需 求上，人们希望能在任何时候、任何地点访问任何所需要的数据。为此，人们从终 端、网络和软件平台各个方面做了不懈努力。未来的绝大部分移动计算机都将配备 以无线网络为主的移动联网设备，以支持移动用户访问网络中数据的需要。利用移 动终端通过无线和固定网络与远程服务器交换数据的分布计算环境称为移动计算 ( m o b i l ec o m p u t i n g ) t 1 2 o 目前，移动计算已成为包括w e b 计算、数据仓库和挖掘 在内的“以客户为中心”应用的三大技术手段之一。 在传统的分布计算系统中，各个计算结点之问都是通过固定网络连接，并且保 持网络的持续连接。而移动计算系统是由固定结点和移动结点构成的分布计算系 统，系统中的用户不再停留在固定的位置不变，而是可以携带着移动计算机自由移 动，并在移动的同时通过移动通信网络保持与固定结点或其他移动结点的连接。这 种移动性将创造一类全新的应用，使得人们能够更加方便地访问各种信息，如移动 办公、公共信息发布、数字战场和位置相关查询等。 移动数据库即支持移动计算环境的数据库。它是一个新兴的研究领域，涉及数 据库技术、分布式计算技术以及移动通讯技术等多个学科领鸟妒捌。移动数据库技 术的许多特性都与信息时代的需求特点相吻合，在许多领域获得了成功的应用，并 涌现出了许多令人耳目一新的实用系统，如警察及社会保障系统、人寿保险移动业 务系统、食品卫生检疫系统、零售业等等。此外，移动数据库技术还在制造业、金 融业、医疗卫生、机顶盒、手机等领域展现了广阔的应用前景。 在移动计算环境中，客户机可能会从一个网络区域移动到另一个网络区域。移 动计算系统必须提供有效的客户机位置管理f 。并且随着网络规模的扩大和用户 数量的增加，在移动环境中定位客户机的位童将囊舞麓为穰客户机的位一管理 华中科技大学硕士学位论文 包括两个方面：位置更新和位置查询。前者发生在客户机移动后，发送更新它的位 置信息；后者发生在当需要访问或呼叫该客户机时，定位它当前的位置。衡量位置 更新和位置查询代价的体系应包括以下因素：发送消息的数量、大小、消息需要传 输的距离、消耗的网络带宽、处理消息的费用和位置数据库查询的延迟。一种好的 位置管理方案应该优化这些因素。 位置管理应在网络层和数据链路层对用户透明地加以管理。除了在低层处理移 动性，也需要在高层获得有关移动对象的位置信息。获取移动客户机当前的位置信 息，不仅是网络路由的要求，更是高层应用的要求，特别是一些基于位置的查询眺 1 0 1 。这些查询主要是基于位置的高级查询。目前大部分的研究和应用都是基于集中 式数据库展开的。许多问题，对传统数据库提出了新的挑战。比如： 1 代表客户机位置的数据是经常变化的； 2 除了空间维，查询位置数据还有一个时间维问题； 3 。查询涉及到未来的时间，如客户想知道在未来一小时里，将进入某一特定 区域的移动客户机的情况。对于这一类的应用，我们只能在现有信息的基础上加以 推测。 除此之外，另一类应用涉及到更新环境参数，合理调配本地化的资源。如在城 市车辆调度系统中，交管人员需要在交通路况紧张时刻，充分调配可利用车辆，提 高运行效率，其中获取当前车辆、路况的信息在这里变得尤为重要。 以上应用都涉及到客户机的位置管理，而且在未来的通信系统中，用户越来越 多，网络覆盖的地理范围越来越大。在这样的系统中，为了定位客户机的位置而产 生的信号数量( s i g n a l 乜a 伍c ) 和处理开销将会急剧增长，而且随着移动数据库技术的 发展和广泛使用，与客户机位置有关的应用也将越来越广泛，所以研究并设计出有 效的客户机位置管理方法具有重要意义。 1 2 国内外研究概况 与传统分布式数据库系统【1 2 t1 3 l 相比，移动数据库系统具有下面的特点【1 4 - 1 7 ： 1 移动性及位置相关性 移动客户机可以在无线通讯单元内及单元间自由移动，在移动的同时仍然能够 华中科技大学硕士学位论文 保持通讯连接，但应用程序及数据查询可能是位置相关的。这就要求移动数据库系 统支持这种移动性，解决过区切换问题，并实现位置相关的处理。 2 频繁的断接性 移动数据库与固定网络之间经常处于主动或被动的断接状态，但事务在断接情 况下仍能继续运行，或者自动进入休眠状态，而不会因网络断接而撤消。 3 系统的安全性及可靠性较差 。 由于移动计算平台可以远程访问系统资源，从而带来新的不安全因素。 4 资源的有限性 移动设备的电源通常只能维持几个小时，还受通讯带宽、存储容量、处理能力 的限制。移动数据库系统必须充分考虑这些限制，在查询优化、事务处理、存储管 理等诸环节提高资源的利用效率。 5 网络通讯的非对称性 上行链路的通讯代价与下行链路有很大的差异。这要求在移动数据库的实现中 充分考虑这种差异，采用合适的方式( 如数据广播) 传递数据。 上述特点使得传统的分布式数据库技术不能有效地支持移动数据库，而必须对 之进行扩充和改造。o r a c l e 公司是数据库产商的巨头，为了支持移动计算机访问数 据库，它推出了m o b i l ea g e n t | 【嘲。m o b i l ea g e n t 将传统的客户，服务器结构扩展为客 户a g e n f f 服务器结构，用于支持移动用户对信息的高效、安全访问。这种结构是一 个三层的无连接结构，移动客户机与服务器之间的通信全部交给位于固定网络中的 a g e n t 来完成。a g e n t 代表客户机完成所需的事务处理，并将结果返回给客户机。 客户机与a g e n t 之间的连接是面向消息的，这种机制很好的支持了客户机的断接， 大大减少了无线网络上的通信量。与o r a c l e 的m o b i l e a g e n t 类似，i n f o r m i x 公司的 移动计算解决方案也是基于三层的体系结构：移动客户机、应用a g e n t 和数据库服 务器刚。在移动计算机和a g e n t 之间多了一个基于消息的移动中间件( m i d d l e w a r e ) ， 它负责建立各种有线或无线数据传输通道和网络协议。i n f o r m i x 采用多种优化技术 如动态数据压缩、客户端消息存储转发技术等来提供一个具有更高性价比的移动网 络基础设施。s y b a s e 采用了数据复制的方法来支持移动应用推出了s y b a s es 掣 a n y w l a c a 暗和s y b a a er d n o w 匕述数据库产晶对移动计算环境的支持很育限。o n i g l e 华中科技大学硕士学位论文 和i n f o r m i x 都只是侧重于解决移动客户机与数据库服务器之间因为无线网络的低 带宽、高延迟、易中断等特点带来的网络连接问题，而对于移动客户机的缓存与断 接操作、数据复制、客户机的移动性都未考虑。s y b a s e 支持了复制，但没有涉及到 客户机的移动性。达梦数据库系统( d m 2 ) 是我国自行研制的分布式多媒体数据库系 统，本身不支持客户机的移动。随着移动计算广泛使用，研制和实现基于d m 2 的 移动数据库系统m d m 2 变得极为重要。 客户机位置管理的体系结构目前主要有两种；两级结构( t w o - t i e r a r c h i t e c t u r e ) 1 和层次结构( h i e r a r c h i c a la r c h i t e c t u r e ) 2 2 】。在两级结构模式下，客户机的当前位置 保存在网络中的两处：h l r ( h o m el o c a t i o nr e g i s t e o 和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 ) 。层次结构扩展了两级结构，通过使用层次位置数据库，它通常是一棵树 结构，位于叶节点的位置数据库服务一个小区，它保存了该小区中客户机的所有入 口。在高一层的位置数据库中，保存了低层的客户机位置信息。当客户机i 从小区 i 移动到小区j ，要更新i 的位黄，j 发送一注册信息给它的父节点，然后这个过程 逐步向上传播，直到找到i 的入口。这个入口一般位于i ，j 的最近共同祖先( l e a s t c o m m o n a n c e s t o r ) ，记为：l c a ( i ，j ) 。然后一条取消注册消息从l c a ( i ，j ) 向下传播 到节点i ，取消沿路上位置数据库中保存的该客户机信息。当需要从位置i 处查找 某个用户i ，而且前i 位于j 处，从i 所在叶结点出发，向上查找，直到有一个节点 上的位置数据库保存了该客户机的入口，显然这个节点应该是l c a ( i ，j ) 。消息从 l c a ( i ，j ) 向下传播到j ，直到客户机i 被准确的定位。当客户机的呼叫和移动操作 都在本地或临近区域进行时，层次结构减少了通信开销，因为不需要将一客户与 h l r 绑定起来。反之，如果当客户机的访问和移动操作在物理上相距很远，相比 两级结构，层次结构中的更新和查询代价将大大增加，因为涉及到的位置数据库数 量较多，更新和在位置数据库中的查询代价将显著增加。 客户机位置管理技术存在两种极端团j ：一种是无论什么时候，当需要访问一用 户i 时，进行全网络搜索，这就演变成了完全的广播技术。这种方法大大减少了更 新代价，因为客户机发生移动后不需要位置更新，但是，随之而产生的网络中的信 号量急剧增长。另外一种极端是，每当客户机发生移动后，网络中的所有位置服务 器都更新客户机的位置信息，这种方法大大减少了查询代价，因为查询操作演变成 4 华中科技大学硕士学位论文 了简单的本地数据库查询。但是，它使得更新代价急剧增长。在两种极端之间，目 前提出了许多方法来权衡位置更新和位置查询的代价。这些方法可以分为两类：集 中减少更新代价和集中减少查询代价。目的不一样，采用的方法也就有所区别。我 们将各种方法归纳如图1 1 所示。 位置管理技术 减少查询代价减少更新代价 复丽一冲面选择前向名针基b 学妄于预测 图i i 位置管理方法汇总 位置管理在移动计算环境和移动数据库中都占据着相当重要的位置。特别是随 着网络的发展，移动用户数量急剧增加，客户机位置管理策略将严重影响系统的开 销。如何实现有效的位置管理，成为许多公司和研究机构的研究热点。目前已经提 出并实现的位置管理方案有： 1 i t l r v l r 现己广泛用于i s _ 4 1 2 4 g s m z s e f t l 约h l r v l r 法采用了两级结构，将客户机 位置信息保存在h l r 和v l r 中。h l r 中保存的是客户机永久的位置信息，v l r 保留客户机临时的位置。当客户机移动到新的小区时，它向本地的v l r 报告新的 位置，由v l r 将位置更新消息发送给h l r 。当需要访问该客户，呼叫者首先查询 本地的v l r ，如果能够找到客户机的位置，则连接建立。否则，需查询全局的h l r 。 这种方法实现起来比较简单，存在的缺陷是： ( 1 ) 不适合本地化操作。在此本地化指物理上相距很近但属于不同的小区。如 果位于这两个小区中的客户机需要通信时，假如他们所在的v l r 没有保留对方的 地址信息，那么必须要经过h l r 才能建立连接，这样通信距离变长，使得定位客 户机的开销变得十分庞大。 ( 2 ) h l r v l r 法与客户机的移动模式无关。不管客户机是否规则移动，该方法 都统一对待，不具有灵活性。 ( 3 ) 当通过v l r 无法获得客户机位置信息时，都需要查询h l r ，增加了查询 开销，同时导致i - - i l r 负担较重 华中科技大学硕士学位论文 2 复制法 为了减少查询代价，可将一些客户机的位置信息在选择的站点进行复制l l “”1 。 当需要同该客户机进行通信时，可直接在本地数据库中查询，而不必每次都去查询 中央数据库。查询中央数据库由于网络带宽、通信距离和网络资源紧缺等原因而导 致较大的查询延迟。但另一方面，由于客户枧位置的时常改变，为了维持复制版本 的一致性与有效性，系统必须为位置更新付出更大的代价。 总的来讲，如果由于复制而带来的开销节省大于由此而产生新的更新代价，那 么认为这种复制方法是有效的。像缓存( c a c h i l l 曲口7 】方法一样，这种效益很大程度上 取决于客户机的c m r 。从直观上来说，如果该值很大，也就是说，大量的对客户 机i 的访问都来源于同一区域j ，那么在区域j 复制i 的位置信息是有效的。然而， 如果客户机i 移动频繁，更新代价将大大增加。设矾表本地查询相对于中央数据 库的查询代价的节省，b 代表由复制引起增加的更新代价，可以根据以下公式来判 断将客户机i 的位置信息复制在区域j 是合理的： q + c u 2b + u i c u 代表在某一时间段t 内从区域j 呼叫客户机i 的可能数目，u i 代表在这段时 间内客户机i 的移动次数。 除了代价因素，对复制区域的选择，还必须考虑其他因素，比如每个数据库的 服务能力和用来保存复制信息的最大存储能力。对每个用户的复制站点信息必须保 存在中央数据库中。当然，除了复制客户机的位置信息，还可以复制客户机的服务 信息、服务质量要求、可提供的传输带宽等等。该选择那些站点去复制客户机的位 置信息呢? 在文献田l 牛- 提到了一种工作集复制法。该方法基于这样一个观察事实： 每个移动用户总是问某一类资源进行通信。这一类资源就叫该客户机的工作集。因 此，对于移动较少的客户机来说，当客户机发生移动后，该客户机只需要通知工作 集中的有关站点来更新该客户机的位置，这种方法减少了一定的更新代价。但工作 集合的大小该如何确定? 一般认为，工作集合越大，客户机移动后产生的位置更新 代价成倍数增长；集合越小，查询客户机位置时，产生查询丢失的可能性也变大， 这时就不得不访问中央数据库，这样也导致系统开销交大。 华中科技大学硕士学位论文 i l l i l l 3 前向指针法 v 越d y a ，p r a d l l a n 和k d s h i l a 对于移动设备的位置管理提出了前向指针法 f f o r w a r d i i l g p o m t c r s ) 2 6 1 。在位置管理中引入前向指针法的目的是为了减少位置更新 的代价。基本思想是：在客户机移动到新的小区时，在客户机上一次所在小区建立 指针指向当前区域。在客户机的m r 中保存着客户机第一次所在的小区，即链头。 这种方法可以形象地用图1 2 来表示。 图1 2 前向指针法位置更新 先设定卸二r 中保留的关于甘广机m u 2 当前存储位置是在小区1 ，而目前它实 际上已经移动到小区n 中。这时若客户机m u l 欲同客户机m u 2 通信。前向”“ 法位置查询过程可形象地用图1 3 表示。它需要经过下面几个过程： ( 1 ) 首先查询且，得知m u 2 在小区1 中； ( 2 ) 查询小区1 ，这时在小区1 中有一指针指向2 ，则证明m u 2 在小区2 中， 查询顺着指针继续向前进行； ( 3 ) 查询2 ，若结果与( 2 ) 同，查询继续进行，直到在小区n 中找到客户机m u 2 。 前向指针法提高了系统在位置更新时的效率，但是对于位置查询需要可能经过 很长的指针搜索，造成开销较大。除此以外，前向指针法还可能存在以下问题： ( 1 ) 指针管理问题在客户机移动的过程中，可能会导致指针过长，或者形成 指针环。 ( 2 ) 追赶问题假设客户机位置移动后发送位置更新消息，查询客户机位置传 送查询消息。如果客户机移动的速度大于传送查询消息的速度，这样将永远无法获 得客户机的位置信息。 7 华q - 科技大学硕士学位论文 ( 3 ) 颠簸问题如果客户机在小区边界来回移动，将导致指针更新频繁a 引起 系统巨大的资源开销 图1 3 前向指针法位置查询 4 缓存法 t l j a i n , y b l i n 和s m o h a n 提出了对每个客户机建立缓存来管理客户机的位置 跚。将上一次与客户机通信获取的位置信息保存在本地数据库中，下一次需要与该 客户机通信时，直接从本地查询。这种方法大大减少了通信代价。存在问题是要求 客户机具有一定的存储能力，如何保证缓存信息的合法性是缓存法必须解决的个 大问题。文献雎8 1 引入了种时间门槛机制，动态的决定缓存信息何时无效。 1 3 课题的研究内容 研究并实现基于d m 2 的移动数据库系统( m d m 2 ) 属于信息产业部下达的项目。 位置管理是其中的一个子系统，主要用来提供有效的客户机位置管理。传统的数据 库体系结构已不再适用m d m 2 ，我们将c l i e n t s e r v e r 结构扩展为c l i e n t a g e n t s e r v e r 结构，中间层a g e n t 用来支持事务断接、管理客户机位置等。在现有位置管理方法 中，每种都有自身的优缺点，适合某些方面的应用，但这些方法对于客户机的移动 行为和网络的实际运行情况考虑很少或基本上不予考虑，而这些因素在移动数据库 中对位置管理的开销影响很大。为了设计一种比较通用的位置管理方法，必须全面 考虑影响位置管理开销的各种因素，以减小位置管理代价为目标。本文将参照移动 i p 模式，利用复雠法和前向指针法的优点，挖掘客户机的移动规律，解决他们存在 的问题，设计并实现适合m d m 2 的位置管理方法位置代理法。我们期望系统能 8 华中科技大学硕士学位论文 够达到的目标是：实现客户机的位置管理；比起现有方法，在性能上具有一定的优 势；充分考虑客户机具体的移动行为和网络状况，体现出一定的灵活性和可扩展性。 本课题主要工作将包括以下几个方面： ( 1 ) 研究当前现有的位置管理策略：h l r v l r 法、复制法、前向指针法等，分 析优缺点，为位置代理法的提出作铺垫。 ( 2 ) 客户机位置管理理论分析。由于目前移动数据库尚处在研发阶段，而且在 客户机移动性方面支持不够。我们将借鉴移动通信环境中位置管理的实现方法，在 m d m 2 的结构基础上，设计m c l m 的体系结构。并且还将分析影响位置管理开销 的各种因素，提出位置管理开销评价体系及最终将要实现的目标。 ( 3 ) 客户机位置管理的具体设计与实现。将首先介绍位置代理法的思想来源， 讨论位置代理法中的关键技术，并将针对客户机的移动行为给出位置更新和位置查 询详细算法，设计所用到的主要数据结构。 ( 4 ) 通过实验评测，比较位置代理法、复制法和前向指针法性能差异，并讨论 c m r 、工作集大小等因素对位置管理开销的影响，为以后继续深入研究指明方向。 9 华中科技大学硕士学位论文 2 移动客户机位置管理理论分析 本章将主要讨论客户机位置管理的理论基础。首先介绍在移动计算环境中位置 管理的实现方法，接着分析了影响位置管理开销的各种因素，然后提出了位置管理 代价的评澳4 体系及实现目标，最后讨论了移动数据库系统m d m 2 和位置管理子系 统m c l m 的体系结构。 2 1引言 在一个移动计算环境中，移动设备( m o b il eu n i t ，简称m u ) 通常通过移动服务 支持结点( m o b i l es u p p o r ts t a t i o n ，简称m s s ) 与固定网络连接的。图2 1 展示了 一种移动计算环境的典型体系结构。在这个移动计算环境中，高速固定网络部分构 成连接固定结点的主干。固定网络中拥有若干固定主机( f i x e dh o s t ，简称f h ) 和移 动服务支持结点 l s s ，每个m s s 负责建立一个无线网络单元( 如图中所示的无线广 播单元或无线局域网单元) ，单元内的移动计算机与m s s 之间通过无线网络连接。 这些无线网络单元的覆盖范围取决于它们所采用的无线通信技术，例如无线l a n 单 元覆盖直径约为几百米，而采用卫星通信的无线网络单元只需几个即可覆盖整个地 球。移动计算机可以从任何一个无线网络单元经由m s s 联接到固定网络中，从而实 现了自由的移动。 在移动计算环境中，位置相关信息的更新及查询是一个重要的应用。为了有效 地支持这种移动查询，人们在图2 1 体系结构的固定网络中间设立了一些位置服务 器。这些位置服务器彼此互联，并通过固定网络与若干移动服务支持结点m s s 联接。 目前一个位置服务器通常下接6 0 个到1 0 0 个m s s 不等。我们把一个位置服务器下 面联接的所有m s s 及其支持的无线网络单元称为该服务器的覆盖范围。每个位置服 务器负责跟踪并管理位于自己覆盖范围内的移动计算机的地址。这些地址信息可能 是精确的，如某个无线单元的标识符；也可能是模糊的，如某个区域是一组无线单 元的集合。为了支持大规模的移动计算环境，位置服务器可以组织成层次形式，即 高层的位置服务器之下可以设立一些低层的位置服务器，直到最终的m s s 为止。 t o 华中科技大学颁士学位论文 图2 i 移动计算典型体系结构 每个移动计算机都在某一个位置服务器上作永久性注册，该服务器称为它的宿 主服务器( h o m el o c a t i o ns e r v e r ) ：此外，当它移动到其他位置服务器范围内时， 以访问者的身份向当地的位置服务器注册，并通报给宿主服务器。每一个m s s 总是 知道有哪些移动计算机活动在它的无线网络单元内，而位置服务器却不一定准确的 知道某个移动计算机位于哪个单元内，但是可以通过寻呼来找到它：由宿主服务器 可知移动计算机当前处在哪个位置服务器覆盖的范围内，然后由该位置服务器向所 有m s s 发送广播信息，这样就可得知移动计算机究竟在哪一个m s s 的无线单元内。 由于这种广播是在固定网络中完成的，因此每次寻呼的开销正比于m s s 的数目。由 此可见，移动计算机的地址信息数据库是分布在许多位置服务器上的。未来的移动 计算环境中将拥有大量的移动用户，如果地址数据库想维护每个移动用户的精确地 址，这就要求移动用户在跨越一个无线单元时都必须向宿主位置服务器报告，这样 会给网络及位置服务器带来过多的开销。相反，如果移动用户不报告地址，只是在 进入另一个位置服务器的覆盖范围时才注册，那么又会使查询该用户当前地址的开 销增大，因为这个时候必须对该位置服务器的每一个m s s 发送寻呼广播。这时，更 适合的方法是采用一种折衷的方法，将每个位置服务器下的m s s 划分为若干互不交 叉的组，每个组称为一个分区。移动用户只有在从一个分区移动到另一个分区内时， 才向位置服务器报告地址的变动。这时，若需要查询一个移动用户的基本步骤为： 首先查询其宿主服务器，找到当前所在的位置服务器；然后。从该位置服务器查 华中科技大学硕士学位论文 出移动用户在哪个分区内；最后，从这个分区内的各个m s s 中找到移动用户。从分 区中查找移动用户的策略有三种： 1 广播：向分区内所有m s s 发送寻呼信息，其代价正比于分区内m s s 的数目。 2 优先表：每个分区的m s s 被组织成一个优先列表，根据移动用户所在的可 能性排序。查询用户地址时，按照这个列表依次查找各个m s s ，直到找到为止。这 种方法的最坏情况是查遍所有m s s 才找到移动用户。 3 指针：每当移动用户在分区内从一个m s s 移动到另一个m s s 时，在上一个 m s s 建立一个前向指针，指向本次的m s s 。查询用户地址时，只需从该用户到达本 分区内的第一个m s s 开始，沿着指针链路，就可找到该用户。如果用户回到一个已 到过的m s s ，只需断掉产生的指针回路即可。这种方法的代价取决于指针链的长度， 最大不会超过分区内m s s 的数目。 查询一个移动用户的地址是一种最简单的地址相关查询，除此之外，还有大量 的涉及到地址的查询，如查询结果与提出该查询的移动用户的实际地址相关、查询 结果与移动用户的移动方向有关、聚集度查询和实时数据的查询等等。位置管理策 略是移动查询方法的前提。 2 2 位置管理的影响因素和目标 在移动计算和移动数据库环境下，客户机的物理位置不再决定于它的网络地 址。客户机可以根据需要，在网络上随意移动。并且客户机可在任意时刻访问任意 需要的资源。由于客户机的移动，导致网络上被访问的资源也相对移动。为了正确 有效地完成客户机的请求，位置代理必须提供一套有效的位置管理策略，以实现网 络路由的需要和一些高层应用的迫切需求。位置管理主要应解决下面这些问题： 1 系统或网络采取什么方法获得客户机的当前位置： 2 移动客户机当前位置信息保存的地点； 3 负责更新移动客户机位置信息的处理部件。 t m l 。+ ，”_ + 华中科技大学硕士学位论文 2 2 1 影响位置管理的因素 在移动数据库中，客户机移动的随意性给系统的位置管理带来了极大的困难。 为了实现一种有效的位置管理，我们首先必须分析客户机的移动模式和实际运行环 境，主要应该考虑下面几项： ( 1 ) 稳定性( s t a b i l i t y ) 客户机的访问源是否来自于固定的集合，比如说。某个 客户的电话总是来自亲戚、家人和朋友。还有一点，客户机的移动是否仅限于某一 些特定区域的集合。比如某个人的活动地点总限于公司、食堂、家庭。 ( 2 ) 本地化( l o c a l i t y ) 涉及到客户机位置信息的操作大部分是否都在本地或临 近地点完成。 ( 3 ) 访问移动频率( c m r ) ：描述客户机被呼叫和移动的相对比较。用c i 代表某 一时间间隔t 内访问客户机i 的次数，m i 代表在这段时间内i 移动的次数。那么客 户机i 的c m r 定义为：c m r i = c i m i 。 另外位置管理还与实际的网络情况有关，比如网络拓扑结构、网络资源分布、 网络流量等。可以预见，未来的位置管理方案应该是在综合考虑了上面各种因素而 提出来的。正如在图2 2 中看到的，未来的位置管理应具有很大的灵活性。 位置管理 时间 空间 f 动态可适应 静态每个用户用户组每个小区 图2 2 未来的位置管理方案 衡量位置管理的开销，主要从两个方面考虑：数据库开销和网络开销。 从数据库方面来看，在此数据库包括两方面：中央数据库和本地数据库。评价 数据库开销的主要指标为：( 1 ) 数据库更新和查询的次数；( 2 ) 数据库数据的装载 和规模；( 3 ) 数据库操作的延迟。 衡量网络开销的评价指标：( 1 ) 通信消息的数量；( 2 ) 操作是否跨区；消息 通信的距离；( 4 ) 通信消息的大小；( 5 ) 链路上的通信量 华中科技大学硕士学位论文 评价一种位置管理方案是否可行和高效，除了满足位置管理方面的基本要求， 还应该综合考虑以上影响位置管理开销的各种因素，使得系统在客户机位置管理方 面付出的代价最小。 2 2 2 位置管理目标 不论在移动计算环境下，还是在移动数据库中，位置管理都是一个重要的方面。 我们期望实现位置管理的目标是： ( 1 ) 灵活性：由于网络环境的多样性，加上客户机移动的不确定性，我们应该 从实际情况分析入手，针对各种情况，采取相应的位置管理策略。 ( 2 ) 高效性：从影响位置管理的各种因素出发，权衡位置更新和位置查询代价， 使系统在位置管理方面付出的开销达到最小； ( 3 ) 便利性：从客户机方面来说，要真正满足客户机随时随地访问信息的需求， 并且保证客户机对系统的位置管理有一定的透明度，即客户机很少参与位置管理。 2 3 基于m d m 2 的位置管理子系统 m c l m 是m d m 2 系统中的一个子系统，目的在于有效管理客户机的位置信息 它是实现移动查询的前提。在详细讨论m c l m 之前先简要描述一下m d m 2 。 2 3 1 移动数据库l v i d m 2 移动数据库系统作为传统分布式数据库系统的推广，具有传统分布式数据库系 统所不具有的特点，如移动性、断接性等。传统的二级客户朋匣务器结构中客户机 和服务器要保持持久连接，不支持断接性。移动客户机的移动可能跨越多个数据库 服务器平台，显然直接在数据库服务器这一层管理移动客户机跨平台移动及相关信 息是不合理的，至少应该抽象出一层来管理移动性。也就是说，必须扩展传统的二 级客户朋匣务器结构为多级客户朋艮务器结构。 1 ) 1 t , t 2 是我们自主研制的主动型、分布式多媒体数据库管理系统1 ，它以成熟的 关系数据库理论为基础，采用层次一关系模型，吸收面向对象的思想，集先进的分 华中科技大学硕士学位论文 布式处理技术、主动数据库技术、多媒体技术、多线索技术于一体。随着移动计算 的广泛应用，研制基于d m 2 的移动数据库系统具有十分重要的意义。为了使之支持 移动数据库的管理，我们在此基础上进行了扩展，改造成三层客户服务器结构， 中间层是代理服务器集合，包括：缓存代理、事务代理、位置代理和移动查询代理 等。经改造后的移动数据库系统m d m 2 体系结构3 3 】如图2 3 所示。 固定网络 图2 3m d m 2 系统结构 其中：l d b m si 表示第i 个场地的数据库管理系统：a g e n ti 表示第i 个场 地的代理服务器；删表示移动用户。l d b m s 提供基本的数据库管理系统功能。代理 服务器是一组代理的集合，每个代理完成一定的功能。内部结构如图2 4 所示。 图2 4 位置代理服务器体系结构 其中各个模块功能如下： ( 1 ) 移动事务代理 移动事务代理要解决在移动计算环境中“移动的、频繁的、可预见的拆连”情 况下的事务处理。移动事务的移动性、长事务、易错性和异构性等特点使得传统的 事务管理策略和算法已经不完全适合移动事务处理。为了保证活动事务的顺利完 华中科技大学硕士学位论文 成，必须设计和实现新的事务管理策略和算法。在佃舵中，对移动事务的处理原则 如下： 出现过区切换( 也称跨区切换) 时，要切换移动事务代理服务器； 根据应用需要来确定事务处理场地，即是在移动计算机上执行事务还是在 固定计算机上执行事务； 日志记录须在固定计算上保留备份，两者的一致性要进行维护； 移动计算机进行断接处理时，向服务器主动声明。 ( 2 ) 数据缓存代理 采用复制缓存技术解决移动数据库断接操作。数据缓存不仅存在于代理服务 器上，而且存在于客户端，其中移动子集洲是主要的数据缓存机制。移动数据库系 统的特点决定了移动客户机上的缓存数据和中央数据库数据之间具备弱一致性，一 致性维护算法是一个关键技术。另外，由于不可能将全部数据库装载到移动计算机 上，合理选择需要移动的数据库子集就是关键。合适的数据库子集不仅可以减少网 络上数据传送量，提高系统响应时间，而且可以提高移动数据库系统的可用性。由 于移动计算机上数据库的容量是有限的，并且在实际运行时会发生变化。当库容满 而不能提供数据存储空间时，就需要替换失效的或不再需要或使用频率较低的数 据。缓存代理负责进行这种维护，这对提高移动数据库的整体性能是有意义的，并 且可以减少许多不必要的数据或信息传送。 ( 3 ) 位置代理 在移动数据库系统中，为了支持客户机的移动，必须跟踪客户机的位置状态， 以便让相应的服务器为客户机提供服务。位置代理主要用来满足客户机的位置更新 和简单位置查询请求，为客户机访问固定网络提供接入点。它是实现移动查询处理 的前提，也是本文讨论重点。 ( 4 ) 移动查询代理 主要用来处理与位置有关的高级查询。客户机在移动过程中，查询的结果往往 与位置是相关的。比如，有一个查询q 1 = “查询在移动客户机周围半径为5 公里 范围内所有的加油站”。显然，随着客户机的移动，查询结果是不同的。也就是说， 对一个查询的回答不仅依据数据库的内容，而且要依据查询发生的位置。为此在客 华中科技大学硕士学位论文 户机和服务器端要提供一种机制完成客户机的逻辑位置的跟踪。移动查询处理由客 户机上的移动子集和代理服务器共同完成。 ( 5 ) 翻译处理 中央服务器对移动设备发送的请求可能无法直接执行，受自身条件所限，服务 器返回的结果也许不能很好地在客户端显示，为了解决这一类问题，在代理服务器 上引入了翻译处理模块。基本工作过程是：分析客户机发送的消息，判断是否合法， 然后处理成标准形式发送到中央服务器执行，最后将执行结果组合处理以可见形式 发给客户机。 2 3 2 位置管理系统体系结构 在移动计算环境中，通过彼此互连的位置服务器将整个网络环境中移动设备的 位置管理起来。在i v l d i v l 2 环境下，我们也借鉴这种思想，每个位置代理管辖一部 分客户机，提供位置更新和位置查询服务。这样减少了中央数据库的负担，也可以 实现多数据库访问。图2 5 描述了位置代理的基本组成。 圈2 5m c l m 系统结构 在上面描述的位置管理系统体系结构中，虚线表示无线连接，实线表示固定连 接。整个结构涉及到三类实体：客户机、位置