移动实时数据库的移动对象位置管理与位置相关查询策略（可编辑）

移动实时数据库的移动对象位置管理与位置相关查询策略（可编辑） 移动实时数据库的移动对象位置管理与位置相关查询 策略 华中科技大学 硕士学位论文 移动实时数据库的移动对象位置管理与位置相关查询策略 姓名:胡卫星 申请学位级别:硕士 专业:计算机软件与理论 指导教师:徐丽萍 20090520 华 中 科 技 大 学 硕 士 学 位 论 文 摘要摘要 摘要摘要 随着计算机技术的飞速发展，人们的需求开始对数据处理环境有了许多全新的变 化，最显著的特点是对数据处理环境提出移动性要求。传统的数据库技术已经无法 满足这种移动环境下的新兴需求，因此对移动计算技术的需求也应运而生。在移动 计算技术的推动下，数据库技术也逐步地向移动数据库技术发展。目前，对移动实 时数据库的研究成为一个热点，它使在任何时候任何地点访问任何数据的需求逐渐 成为现实。 位置管理是作为移动环境诸多应用中不可缺少的重要组成部分，是系统具备移动 性特点的前提。在位置管理策略中，通过一个六元组来描述系统的移动对象位置信 息，并采用两层组织模式来存储位置信息。此外，了一种高效的基于因子平衡 的位置更新策略与过区切换方式，并通过一种两级判别模式实现了移动对象透明的 过区切换，为系统的移动特性提供了有效的支撑。 在位置相关查询策略中，通过一种基于格栅合并的两级索引方法系统有效地实现 位置信息到数据区域的快速映射，从而解决了位置相关查询中最为关键的技术问题， 同时，通过对移动实时环境下位置相关查询的分析,在查询策略中引入了主动订阅机 制，来支持移动终端的本地执行。 关键词关键词:移动实时数据库: ，位置管理，位 置相关查询，格栅合并 关键词关键词:: I 华 中 科 技 大 学 硕 士 学 位 论 文 Abstract Abstract AbstractAbstract With the rapid development of computer technology, People's demand has changed a lot in the environment of data-processing, the most prominent feature of which is that mobility has been proposed in the environment of data-processing Traditional database technology has been unable to meet the emerging demand for this mobile environment, so the demand for mobile computing technology has emerged. In the impulse of mobile computing technology, Database technology is gradually developing towards Mobile Database technology. At present, the research of mobile real-time database has become a hotspot, which gradually makes the demand for accessing any data at any place and any time become a reality. Location Management as a number of applications in the mobile environment is an important and indispensable component, also is the premise of mobility for system. In the Location Management Strategy, use a six-tuple to describe location information of mobile objects in the system, and a two-tier model to store location information. In addition, design an efficient location update strategy based on the balance of factors and a way to Area-Switching, and through a two-tier judgments Model come true transparent Area-Switching of mobile objects, which provides an effective support for the Mobile feature of system . In the Location Dependent Query strategy, system effectively achieve the rapid mapping between Location information and Data Region by a method based on grid combination and two level of index, so that resolve the most critical issue of the Location Dependent Query, at the same time, by analyzing the Location Dependent Query of mobile real-time environment, introduce an initiative Subscribe mechanism in the query strategy to support the local implementation of mobile terminal. Key words: Mobile Real-Time Database, Location Management, Location Dependent Query, grid combination II 独创性声明独创性声明 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到，本声明的法律结果由本 人承担。 学位论文作者签名: 日期: 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即:学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密?，在_____年解密后适用本授权书。 本论文属于 ? 不保密?。 (请在以上方框内打“?” ) 学位论文作者签名: 指导教师签名: 日期: 年 月 日 日期: 年 月 日 华 中 科 技 大 学 硕 士 学 位 论 文 1 1 引言引言 1 1 引言引言 1.1 课题背景及意义 随着计算机技术的飞速发展，人们的需求开始对数据处理环境有了许多全新的变 化，最显著的特点是对数据处理环境提出移动性要求。传统的数据库技术已经无法 满足这种移动环境下的新兴需要，因此对移动计算技术的需求也应运而生。在移动 计算技术的推动下，数据库技术也逐步地向移动数据库技术[1-2]发展。目前，对移动 实时数据库的研究成为一个热点，它使得新的数据处理需求逐渐成为现实。 当前，作为移动数据库技术中的一个重要组成部分，移动环 境下的位置管理技 术在许多移动应用领域内都起着重要的作用。它是系统具有移动性特征的前提，同 时在许多基于移动对象的位置信息服务中，系统都需要知道移动对象的具体位置。 因此，为了使移动对象在系统服务的范围内可以自由的移动、通信和发出呼叫以及 各种查询请求，则需要一种位置管理策略来提供有效地支撑。位置管理策略主要内 容包括移动对象位置信息的表示、位置数据库的组织模式、位置更新策略、过区切 换处理。 在位置管理策略的基础上，可以开发位置相关的服务，移动查询可以分为位置相 [3] 关查询、位置持续查询、位置感知查询 。位置相关查询使得用户从任何地点访问位 置相关数据成为现实。通过对位置相关查询的扩展，例如进行周期性位置相关查询 或基于事件的位置相关查询等，这样可以催生很多新的应用需求。最简单的一个应 用就是旅游景点电子导游功能，到时每个游客只需手持一个电子导游终端，走到那 一个景区终端设备就显示那个景点的相关信息介绍。可见，基于位置相关的查询服 务有着广阔的应用前景。 1.2 国内外研究现状 近年来， 随着硬件技术、通讯技术、相应的软件技术的发 展，为移动计算技术 提供了可靠的技术保障，在任何时候任何地点访问任何数据的需求已逐渐成为现实。 在移动计算技术的推动下，数据库技术也逐步地向移动数据库技术发展。 在移动数据库中，由于移动计算环境，给数据库带来了很多新的明显特征:移 1 华 中 科 技 大 学 硕 士 学 位 论 文 [5] 动性、断连性、可伸缩性、网络通信的不对称性、低可靠性 。正是由于这些特点， 在移动数据库中主要关键技术有事务处理、数据广播 解决网络 通信不对称性 、数 据复制与同步 (解决频繁断连性)、基于位置的查询服务 [5] 。在基于位置的查询服务 系统中，主要研究的内容体现在如下几个方面: 1 位置建模方法。移动数据库是对传统的分布式数据库的一种扩展。在移动数 据库中，由于在移动环境中，引起移动对象的当前位置信息不断地变化。为了满足 移动性，则必须对移动对象的位置进行有效的管理，这样才能克服移动环境下带来 的移动对象与中心服务器的通信问题。有了位置管理，服务器通过位置管理提供的 信息来为移动对象提供服务，而移动对象则在位置管理策略中，能够及时的与中心 服务器建立起 (间接)连接。所以，位置管理首先面临的问题就是位置建模方法。 位置建模方法是一种用来表示移动对象信息，通过该信息可以为移动对象的移动 性提供有效的支撑。 根据应用的不同，对位置信息的表示粒度也可以不同，大致可分为两类:一种是 通过无线通信系统中位置管理设施所提供的信息，可以达到无线通信单元一级的位 置精度，如移动的蜂窝网络，就是把应用区域划分成一个个紧密相连的无线通信单 元;另一种是精确位置表示，通过点坐标 (x，y)分别来表示对象的经度与纬度以 [6] 达到来确定移动对象的位置的目的 。目前移动对象的精确位置可以通过全球定位系 统(GPS)来获得。 由于移动对象的位置会随着移动对象的运动而不断的变化，所以在位置建模过程 [6] 中，必须有一种有效的位置更新策略 来及时地更新移动对象的当前位置信息。传统 方式是通过周期性刷新位置信息，但移动对象频繁的位置更新会给服务器带来严重 的更新开销,同时位置更新也会占用上行通信带宽,降低了网络带宽的利用率,增加 了网络负担。目前,在移动对象数据库技术中主要采用的位置建模方法是将移动对象 的位置信息表示为时间的函数,系统通过该时间函数预测移动对象将来的位置信息, 只有在预测位置与实际位置的偏差超过了某一阈值时,才发起位置更新.该方法极大 地避免了不必要的位置更新请求,从而有效地降低了系统位置更新的开销。在移动对 象的位置模型中具有代表性的成果有移动对象离散数据模型和移动对象时间模型。 2 华 中 科 技 大 学 硕 士 学 位 论 文 2 位置数据库的组织模式。目前位置数据库的组织模式有如下几种: 集中式。集中的位置管理模式较为简单，该模式将所有移动对象的位置信息 都存放在一个集中式的位置数据库中。所有位置信息的查询和更改操作都直 接在该集中式数据库中进行。这种模式主要应用于军事领域，在商业应用方 面由于所有的操作都集中在一个数据库里完成，容易造成系统应用瓶颈，从 而导致查询效率低下。 两层模式。两层模式是通过两级位置数据库来共同管理移动对象的一种组织 形式。两层模式的位置数据库组织模式在移动蜂窝网络中得到了广泛的应 用，在移动蜂窝网络中，每个移动对象由一个归属位置寄存器和一个访问位 置寄存器两层共同管理。 层次树状模式。层次树状模式是对两层模式的一个扩展，它将位置数据库组 织成树状层次结构。其叶子节点位置数据库对应一个移动位置区域，管理该 移动位置区域内所有移动对象的位置信息。上层节点位置数据库包含了它所 有下层节点位置数据库中移动对象的位置。对于每个移动对象而言，其 在上层节点中的位置记录可以是移动对象的实际位置信息，也可以是指向下 层节点的一个指针 [7-8] 。 3 位置更新策略。移动对象的移动特性，引发移动对象的位置不断地改变，在 这种情况下，要保证服务器与移动对象的双向逻辑通信和位置信息的有效性，必须 有一种有效的位置更新策略来不断地刷新系统登记的位置信息。 目前，当前的位置更新策略主要可以分为以下三类:基于时间、基于运动和基于 距离的位置更新策略[9-12]。基于时间的位置更新策略是最简单的一种更新策略，根据 一个预先定义的时间阈值来判断移动对象是否需要向服务器发出更新请求。然而这 种策略容易产生很多不必要的更新消息，浪费无线带宽和其他网络资源，从而降低 网络利用率，更新代价很大;基于距离的位置更新策略提供了一个距离阈值，移动 对象根据目前位置与服务器维护的自身位置之间的偏移量是否超过该距离阈值来确 定是否向服务器发出位置更新信息;基于运动的位置更新策略根 据移动对象穿越划 分的无线通信单元的次数来确定移动对象发起位置更新操作的时机。该策略的缺点 3 华 中 科 技 大 学 硕 士 学 位 论 文 是:当移动对象在划分的无线通信单元之间来回不停的运动时，就会产生很多不必 要的位置更新，边界 “乒乓效应”严重。 4 移动对象索引技术。在移动数据库中，移动对象是通过一定的位置管理策略 来进行统一管理，对移动对象的检索代价会随着移动对象的规模的不断增加而增加， 一旦移动对象的规模达到一定的程度时，对移动对象的检索就会成为制约系统性能 的一个瓶颈。为了提高移动对象检索效率，就必须对移动对象进行索引。 对于移动对象的索引方法，像B树及其变形树等传统关系数据库的索引方法，可 能有点力不从心，通常借鉴于空间数据索引技术。目前，在空间数据索引方法中主 要研究成果有Quad树、X树、LSD树、R树、R+树、R*树等。由于空间数据具有静态 特征，所以在空间数据索引方法中更多的是考虑查询效率。而在移动数据库系统中， 由于移动性的特征，导致移动对象的位置信息会不断的变化，这种变化会引起移动 对象索引结构动态变化[13-17]，导致索引的维护代价很大,从而制约了检索的性能。所 以在移动对象索引方法中，要达到提高效率的目的，必须综合考虑两个主要影响因 素:移动对象查询效率和位置更新引起索引结构动态变化的代价。 目前，在移动对象索引方法中，马里兰大学的Z.Song等人提出了一种 hash方法。 该方法是通过设计合理的 Hash 函数，从而实现了对移动对象的快速检索。此外， Aalborg 大学的 DieterPfoser 等人提出了一种基于 R 树的移动对象索引方法[18]; Bilkent大学的 JamelTayeb等人提出了一种 Quad变形树的移动对象索引方法;还有 不少基于空间变换的移动对象索引方法。 5 位置信息到数据区域的映射。位置相关查询[19,20]的关键技术之一就是位置信 息与数据区域的映射，通过这种映射，把位置相关查询条件转化成传统关系数据库 的查询条件[21]。主要的解决是把空间计算、对象分解技术和数据区域索引相结 合。在空间计算方面,主要体现上点在多边形内的判断方法;在对象分解技术和数据 区域索引方面，它是通过对象分解技术把复杂的数据区域分解成为形状简单且规则 的区域，再对分解后形成的区域进行索引。目前主要理论成果有基于关系数据库的 可变粒度格栅索引[21]、Trian-Tree、Trap-Tree [22-26]等。 4 华 中 科 技 大 学 硕 士 学 位 论 文 [27] 6 移动对象的不确定表示与处理 。移动对象是通过位置管理策略中提供的位 置更新策略来及时地进行位置信息的更新。不管采用哪种位置更新策略，在相邻两 次位置更新期间，客观地存在一个时间差，由于移动对象具有移动性，使得在下一 次发生位置更新前，真实的位置信息可能已经与当前系统记录的位置信息产生了一 定的偏差。特别是在位置相关的精确查询时，从移动对象发起查询请求到结果返回 的这个时间差中，返回的结果可能就与真实结果有偏差，为了保证结果的有效性， 这也是为什么有的移动事务必须在实时条件下完成的一个原因之一[27]。可见，移动 对象的位置管理方式本质上就具有不确定性，而且在某种程度上，位置更新代价与 位置的不确定性是矛盾的。例如系统采用基于阈值的位置更新策略来减少位置更新 的代价，却无形中增加了位置的不确定性。 移动对象位置的不确定性[28]是位置管理中客观存在的事实，无法消除它的存在, 而是要根据系统应用需求，对它进行正确的处理，在消弱不确定性所带来影响的同 时，也要充分地考虑位置更新的代价对系统性能所带来的影响，尽可能在两者之间 找到一个平衡点。 目前，在移动对象的不确定处理方面，研究成果有:基于样本统计的位置预测模 型 由于充分地考虑运动对象运动随机性的特点，从而有效地提高了位置预测的准确 性[28][29] 和满足误差限制的偏差优化技术[30]。 1.3 论文内容与组织结构 本论文的组织结构安排如下: 第一章介绍课题的研究背景及意义，对位置管理和位置相关查询的研究现状进 行了评述，分析了现阶段存在的问题并对未来研究的趋势进行了预测。 第二章根据课题组的具体应用提出一种基于三层体系结构的位置管理策略，并 且从位置信息的表示、位置数据库的组织模式、位置更新策略和切区切换机制四个 方面来详细地介绍了位置管理策略。 第三章分析了位置相关查询总代价的构成因素，并结合了第二章的位置管理策 略，设计了一种基于代价的位置相关查询策略。在该位置更新策略中，通过一种基 于格栅合并的两级索引方法，有效地实现了位置信息到数据区域的映射，并引入了 5 华 中 科 技 大 学 硕 士 学 位 论 文 主动订阅机制，来支持移动终端查询的本地执行。 第四章根据第二、三章的基本理论与方法，开发出一个适合移动实时环境下位 置管理与位置相关查询的原型系统，并对原型系统进行测试与性能评价。 第五章是对全文工作进行总结，并指出以后的研究工作方向。 6 华 中 科 技 大 学 硕 士 学 位 论 文 2 2 基于三层体系结构的位置管理基于三层体系结构的位置管理策略策略 22 基于三层体系结构的位置管理基于三层体系结构的位置管理策略策略 系统采用了 Server-Agent-MC 三层体系结构[31]，如图 2-1 所示。该体系结构中 Server 与 Agent 是通过固定网络相连，该连接是一种具有高可靠性，高传输速率、 高安全性的强连接。Agent 通过自身的无线通信接口与 MC 的进行通信，两者之间是 通过无线网络进行连接，此网络环境以及移动对象自身的一些特点决定了该连接是 一种弱连接，它具有频繁的断连性，上下行通信不对称性，低可靠性等特点。在这 三层体系结构中，MC与Server之间不能直接进行通信，而是通过Agent这个中间层 来进行间接通信。 图 2-1 系统三层体系结构图 在三层体系结构中，为了满足移动对象的移动性特点，需要一种位置管理策略 [32]来为移动性提供支撑。在位置管理策略中主要考虑:移动对象位置的表示与存储、 位置信息的更新、过区切换的处理。 2.1 位置的表示模型 位置的表示模型是一种用来表示移动对象信息，通过该信息可以为移动对象的移 动性提供有效的支撑。 7 华 中 科 技 大 学 硕 士 学 位 论 文 在三层体系结构中，为了丰富系统位置服务功能，移动对象同时提供两种表示粒 度的位置信息——无线通信单元级与精确点级。无线通信单元级可以通过无线通信 系统中位置管理设施所提供的信息，如移动的蜂窝网络，就是把应用区域划分成一 个个紧密相连的无线通信单元[33];精确点级，是通过点坐标 (经度，纬度)来描述 移动对象的地理位置，点坐标可以通过定位系统 (GPS)来获取。 定义 2.1:移动对象位置的表示模型为:M (Mid,Aid,T,(X,Y)， Vx,Vy ,TYPE)， 其中 Mid为移动对象的标识符，Aid为代理层 (无线通信单元)的标识符，T为最新 更新时间，(X,Y)分别为移动对象的经度与纬度, Vx,Vy 表示移动对象的速度，TYPE 为移动对象的类型，具体如表2-1所示。 表 2-1 移动对象位置的表示模型描述 Mid 移动对象的标识符 Aid 代理层 (无线通信单元)的标识符 T 最新更新时间 X,Y) 分别为移动对象的经度与纬度 Vx,Vy) 表示移动对象的运动速度 TYPE 移动对象的类型 由于系统 Server 与 MC 端不能直接进行通信，所以 Aid 的引入具有两层含义:对 于移动对象而言，只有知道自己当前所在的无线通信单元，才能通过该无线单元建 立起到服务器的逻辑通信;对于服务器而言，只有知道移动对象所在的无线通信单 元，才能与移动对象建立起逻辑通信。 点坐标是描述了移动对象的物理位置，通过点描述，可以忽略移动对象形状及大 小，同时为按距离进行的位置相关查询方式提供了有效的支撑。 例如在军事应用上， 可以 “查询周围1 公里范围内的友军移动单位”;在日常生活应用中，可以 “查询 离我最近的出租车”等。 (Vx,Vy)的引入为将来查询提供了可能，结合点坐标，移动对象的位置信息可 以表示成时间的函数。 定义 2.2:对于任意移动对象 M，当前位置信息 M (Mid,Aid,T ,(X ,Y )， 0 0 0 V ,V ,TYPE)，根据实际的精度要求设定 M 有效的一个最大时间范围 T ，对于 x0 y0 8 华 中 科 技 大 学 硕 士 学 位 论 文 ?t ? T ,T + T ，M的点坐标 X ,Y 可以近似的表 示为: 0 0 t t X X +V * t ?T ? ? t 0 x 0 0 ? 。 Y Y + V * t ? T ? t 0 y 0 0 ? 例如:在公交站台查询未来 3分钟可能内经过该站的公交车。 TYPE 描述移动对象的类型，其作用有两点:提供对移动对象的分类查询;为移 动对象提供了索引关键字。 2.2 位置的组织模式 在位置管理模块，有了移动对象的位置表示，面临的问题直接问题就是位置信息 的管理，即采用哪种组织模式来存放位置信息。位置的组织模式的好坏会直接影响 到系统的整体性能，特别是在实时系统中，在性能方面的要求就更高。 目前在位置数据库的组织模式方面，研究成果有:集中式、 两层模式、层次树状 模式。在实际应用中，具体采用那种组织模式比较合适，应该结合系统的体系结构 来综合考量。集中式是采用一个集中式的位置数据库来管理所有的移动对象的位置 信息，实现比较简单，但是对位置信息的所有操作都直接在集中式数据库中进行， 使得集中式数据库负荷重。 结合系统三层体系结构的特点，系统对位置的组织模式是采用的两层模式。在 Agent层，动态地保存进入其所辖区域的 MC的实时位置信息,内容主要包括 MCID、T、 x,y 、(Vx,Vy);在 Server 层管理的位置信息没有地理依赖性，主要记录 MCID 与 Agent的对应关系以及MC的具体位置无关信息 如第三章中提到的订阅表信息 。 这种组织模式的一个优点是:移动对象的更新主要是在 Agent上完成，对Server 端的影响较小;只有在发生了过区切换或移动对象订阅发生变化时，才会去触发 Server 更新位置管理信息,大大降低了 Server 负担;但是两层结构增加了移动对象 的寻呼时间，从而也限制了移动对象查询移动对象的性能。 2.3 位置更新策略 移动对象的移动特性，引发移动对象的位置不断地改变，在这种情况下，要保 证服务器与移动对象的双向逻辑通信和位置信息的有效性，必须有一种有效的位置 更新策略来不断地刷新系统登记的位置信息。 9 华 中 科 技 大 学 硕 士 学 位 论 文 位置更新过程是通过移动对象向所在 Agent 发送其新的位置信息，Agent 收到 位置更新信息后会替换本地的位置信息，同时 Server维护相应的位置信息。 通过上述过程可知，位置更新会占用MC到Agent的无线上行带宽，同时也会给 Agent和Server带来维护的代价，特别是在MC对象达到一定的规模时，给Agent与 Server 带来的代价尤为明显，同时位置更新对移动对象的索引性能也会产生很大的 影响，特别是在采用树形 (如R，B树等)作为索引结构时，移 动对象的位置频繁地 + 更新会带来移动对象索引结构的不断地变化，增加了索引结构的维护代价。 在移动实时数据库中，位置更新频率太高，会降低系统的整体性能;位置更新 频率太低，会增加移动对象的位置不确定，从而影响查询服务的结果，降低系统的 正确性。所以，迫切需要一种高效的位置更新策略来折衷处理系统性能与系统正确 性之间的矛盾。 传统的基于阈值的位置更新策略，包括基于时间阈值、距离阈值、运动阈值。 基于时间的位置更新策略是通过一个事先设置好的时间阈值T 来周期性的进行位 置更新，这种位置更新策略的缺陷是对于运动速度变化快的移动对象来说，并不能 及时的反映运动速度的变化，可能导致系统产生无法容忍的误差，同时，时间阈值?T 没有一个统一的定义其大小，例如对于慢速运动的对象，?T 定义大一些，会提 高系统的性能;对于快速运动的移动对象，?T 定义小一些，可以减少系统的误差。 基于距离的位置更新策略是通过一个事先设置好的距离阈值?L ，当移动对象与最近 一次位置更新时的距离超过?L 时，触发位置更新，这种更新策略的缺陷是移动对象 在发起下一次更新前需要不断地获取当前时刻的移动对象点坐标，并计算移动距离， 而移动对象的处理能力比较弱，这种情况会降低移动对象自身的处理能力。传统的 基于阈值的位置更新策略由于在触发位置更新条件太过单一，缺乏对系统各种因素 (例如时间，运动等)的综合考虑，只能应用在符合其特性的 移动系统中，应用范 围相对比较窄。为此，提出一种基于因子平衡的位置更新策略。 10 华 中 科 技 大 学 硕 士 学 位 论 文 ?时间因素τ ? 距离因素? ? ? 影响因素ε ?速度因素υ ? ?边界"乒乓效应"ρ ? 移动对象应用环境 η ? 基于因子平衡的位置更新策略的位置更新策略是一种周期 性更新与事件驱动相 结合的位置更新方式，按触发方式分类可分为:基于事件驱动的 触发更新策略和基 于时间阈值的更新策略。 ? 基于事件驱动的触发更新策略按事件的不同，又可分为:过区切换触发、距离阈 值触发、速度阈值触发。 1 过区切换触发，是指移动对象收到新的Agent 广播的地址信息时，在等待若 干个地址信息广播周期 T后，如果期间没有收到旧 Agent的广播地址信息时,发起的 位置更新方式。在这种触发方式中，等待若干个地址信息广播周期 T 是为了防止在 两个 Agent管理的无线单元区的重叠部分时，移动对象触发了不必要的位置更新,同 时，在某种程度上也可以减弱移动对象边界运动所产生“乒乓效应”。这种触发方式， 与其他的触发方式的一个不同点，就是这种更新会改变位置信息 中的Aid。 2 距离阈值触发是指移动对象根据自身的特点设置预先 设定一个距离阈值?L, 假设最近一次更新时刻 T 的位置为 x , y ,同时假设时刻 T 通过基于因子平衡的位 0 0 0 0 置更新得到的时间阈值为?T ，?T t T + ?T ，时刻 t对应的位置为 x , y ，如 0 0 t t 2 2 果?L x ? x 2 + y ? y ，则不触发更新;如果?L ? x ? x 2 + y ? y ，立 t 0 t 0 t 0 t 0 即触发更新。 3 速度阈值触发可以根据速度的大小和速度的方向进行 更新。设最近一次更新 时刻T 的速度为 Vx ,Vy ,同时假设时刻 T 通过基于因子平 衡的位置更新得到的时 0 0 0 0 间阈值为?T ，?T t T + ?T ，时刻 t对应的 位置为 Vx ,Vy ，不妨设速度大小 0 0 t t 阈值为?v ，如果?v Vxt 2 + Vyt 2 ? Vx02 + Vy02 ，则不触发更新;如果 ?v ? Vxt 2 + Vyt 2 ? Vx0 2 + Vy0 2 ，立即触发更新。 不妨设速度方向阈值为?θ ，如果 Vx *Vx + Vy *Vy ?θ arccos t 0 t 0 ,则不触发更新;如果 Vx 2 + Vy 2 Vx 2 + Vy 2 t t t t 11 华 中 科 技 大 学 硕 士 学 位 论 文 Vx *Vx + Vy *Vy ?θ ? arccos t 0 t 0 ，立即触发更新。 Vx 2 + Vy 2 Vx 2 + Vy 2 t t t t ? 基于时间阈值的更新策略。通过为系统设置一个固定的周期 ，作为整个系统中 所有移动对象位置更新周期的策略。 定义 2.3:设二维平面区域G X × Y 内，存在一个这样的Agent管理的无线通信 n 单元区域集合A LA ,LA ,...,LA ，同时满足条件G ULA 和LAi ? LAj i ? j ，则 1 2 n i i 1 称区域集合 A为区域 G的一个极小全覆盖。所谓全覆盖是指? x, y ?G ，总?LA ? A i 使得 x , y ? LA 。 i Agent所管理的无线通信单元区域是指 Agent 广播的信号所能达到的范围。根据 无线信号传播的特点，可以清楚地知道Agent 所管理的无线通信单元区域 LA是一个 以Agent所在地为圆心，无线信号传播的最大距离为半径的圆域。根据这个特点， 给出如下几种区域 G的极小覆盖的结构实例 图2-2、图2-3和图2-4 。 图 2-2 区域G 的极小覆盖的结构实例 按图2-2所示结构来构造区域 G的极小全覆盖，可以减少Agent之间的重叠区域 的大小 (即可减小Agent 的数量)，但是圆域的两两相切处点，同时属于四个 Agent 所有，围绕该边界点周围运动的移动对象可能产生频繁的位置更新，“乒乓效应” 影响比较大。 按图2-3所示结构来构造区域 G的极小全覆盖，与图 2-2 相比不但增加单位面积 下的重叠区的面部，还增加区域与区域之间的边界，“乒乓效应”影响比较大。 12 华 中 科 技 大 学 硕 士 学 位 论 文 图 2-3 区域G 的极小覆盖的结构实例 图 2-4 区域G 的极小覆盖的结构实例 无论采用那种结构来构造区域 G的极小全覆盖，要充分地考虑其结构带来的 “乒 [34] 乓效应” ，同时尽可能减少Agent的数量，以达到降低成本的效果。 在基于因子平衡的位置更新策略中, 对过区切换触发的处理方式对于两个Agent 可以消除在无线通信单元重叠区的 “乒乓效应”，同时在某种程度上减弱了边界来回 运动所产生的“乒乓效应”。 2.4 过区切换机制 对于采用了 Server-Agent-MC三层体系结构实现的移动实时数据库中，Agent一 个主要的功能是负责 Server 与 MC 的间接通信。当移动对象从一个 Agent 移动到另 一个 Agent时, Server 与MC之间的间接通信就发生了变化。 定义 2.4:假设系统通过 N 个Agent来负责 Server与MC的双向通信，N 个Agent 管理的无线通信单元位置区域构成集合 A LA ,LA „,LA ，系 统的可用范围为二维 1 2, N 平面 G X×Y，区域集合 A 是G的一个极小覆盖。用点 (x,y) 代表移动对象M的位置， , ? x y ?G ，总?LA ? A 1 ? i ? N 满足 x , y ? LA 。在没有发生过区切换的情况下， i i MC执行一个事务 T1过程如下: 13 华 中 科 技 大 学 硕 士 学 位 论 文 第一步、MC向其所在的Agent发送 T1执行请求。 第二步、Agent收到T1请求时，先通过一定的优先级算法，计算出T1的优先级， 再将该T1放入相应的事务上传队列，最后通过Agent提供的上传事务进程来上传 T1。 第三步、Server 收到 T1 请求时，通过事务调度算法，把事务 T1 放入事务执行 队列，等待 Server的执行。 第四步、Server执行完T1后，产生结果 R1，Server会通过 Agent 将R1返回给 MC。 然而，在移动环境下，移动对象具有随机自由的特点，可能导致它从一个Agent 切换到另外一个 Agent 所管区域,对事务结果的返回也有了新 的要求,同时对于旧 Agent上维护的 MC相关信息也需要转移到新的 Agent上,以支持 MC的透明切换。 2.4.1 过区切换的实现方式 当过区切换发生时，其过程如下 如图2-6所示 。 图 2-6 过区切换过程图 1 MC向新的Agent发起注册请求。 2 Agent收到注册请求后，在其上记录其位置相关信息，并通过 Server发生了 14 华 中 科 技 大 学 硕 士 学 位 论 文 过区切换。 3 Server 更新其上的登记信息，同时把与 MC 相关的信息 (如订阅表信息)传 送新的 Agent，并通知旧的 Agent删除其该 MC 的位置相关信息。 4 Agent删除其中该MC的相关信息，并对过区切换进行登记，为过区切换的透 明化提供保障。 2.4.2 过区切换的透明性 过区切换的透明性是相对于移动对象而言透明的，当移动对象从一个Agent运动 到另一个 Agent 时，不需要人为的进行干预，系统自动进行无缝信息转移，即用户 本身感知不到过区切换的存在，对用户的使用不会产生任何限制和影响。然而，如 果不做特殊处理，可能造成在过区切换时很大的事务夭折率。例如移动对象通过无 线通信单元 A向Server发起查询请求，但当结果返回到A时，该移动对象已发生了 过区切换到了无线通信单元 B，如果继续通过 A把结果发送移动对象，可能因为无法 与该移动对象建立通信而导致结果丢失，造成事务夭折，从而影响用户的使用。为 了不让这种情况发生时，希望 A 能自动把返回结果传到 B，再由 B 向该移动对象传 送。 为了实现这个要求，系统在Agent层采用了两级判别模式(如图 2-7所示)来向 MC转发结果。该方法的实现过程如下: 1 通过在Agent 上引入过区切换登记列表，用来记录移动对象发生过区切换的 信息，登记列表信息主要包括:MCID、新的AgentID、未完成事务数量和过区切换发 生时间。当发生过区切换时，通过 Agent 上维护的 MC 相关信息，可以得到 MC 未完 成事务数量，如果该值为零，则不在过区切换登记列表中登记过区切换;否则,把 MCID、新的 AgentID和未完成事务数量登记到过区切换登记列表中。 2 当 Agent 收到一个事务结果时，先查找 MC 是否还在其所管理的移动对象中 ——一级判别。如果在 Agent 所管理的移动对象中，则根据 Agent 上记录移动对象 信息的最新更新时间与当前时间进行比较，如果两者之差小于某 一阈值，则直接将 结果发送给 MC;否则与MC之间测试连接，如果连接正常，就立刻把结果发送给MC。 如果 MC 不在 Agent 所管理的移动对象中,则去查找过区切换登记列表，找到其相应 15 华 中 科 技 大 学 硕 士 学 位 论 文 的过区切换记录——二级判别。根据过区切换记录，把结果信息向新的 Agent 进行 转发。当新的Agent收到转发结果时，重复步骤 2 。 显然，通过这种方式，在结果返回过程中，即使发生了多次过区切换，只要事务 不超期，都是可以有效地保证结果传递给移动对象。 图 2-7 Agent 结果返回的两级判别模式 2.5 小结 本章通过对移动实时数据库三层体系结构的分析，结合三层结构体系的特点，提 出了一种满足该体系结构的位置管理模型，并对位置管理模型中的位置的表示、位 置的组织模式、位置更新策略以及过区切换机制作了详细的描述。 16 华 中 科 技 大 学 硕 士 学 位 论 文 3 3 一种一种移动实时数据库移动实时数据库的位置相关查询策略的位置相关查询策略 33 一种一种移动实时数据库移动实时数据库的 位置相关查询策略的位置相关查询策略 位置相关查询是指查询结果依赖于移动用户当前位置的查询，对于同一查询请 求，其提交的地点不同，返回的结果也将不同。例如 “请告诉我当前所在的地方”， 对于这类查询，其结果是随着用户提交查询请求的地点而不断变化的。由此可见， 提供位置相关查询功能的系统，必须满足如下三个基本前提条件: 移动对象位置的不确定性。只有在这种前提下，用户才能在不同的地点发起 查询服务请求。 移动对象位置的精确性。由于位置相关查询的查询结果严重依赖于移动用户 的当前位置，所以在这类查询中，系统响应查询请求前，必须同时获得移动 用户的当前位置，才能提供依赖于移动用户当前位置的结果。 位置相关的数据。位置相关的数据是指具有地理位置依赖性的数据，例如“天 气预报”。 位置相关查询的查询条件按位置相关性进行分类可分为:位置相关查询条件 (Location Dependent Query Condition 即 LDQC)和非位置相关查询条件 (Non-Location Dependent Query Condition 即 N-LDQC)，则位置相关查询的结构 可表示为:SELECT A FROM B WHERE LDQC && N-LDQC，其中A表示查询的属性集， B表示查询表集合，如果N-LDQC为NULL，则用 1 1代替。可见，实现位置相关查询 的关键技术之一就是实现 LDQC 向 N-LDQC 的转换，即实现从移动查询用户具体地理 位置到数据区域的映射。为了实现 LDQC 向 N-LDQC 的转换，位置相关数据的表示与 存储是基础。 3.1 位置相关数据的表示模型 位置相关数据的典型特征是在不同位置它可能具有不同的值。例如 “地名”是一 个位置相关的数据对象，它的名称与实际地理位置存在一对一的对应关系，在不同 位置地名的取值当然不同。不妨以 “地名”这个位置相关数据为例，考虑位置相关 数据如何表示。为了表示 “地名”这个位置相关数据，根据在不同位置地名的取值 不同的特点，对整个应用区域按地名进行划分，从而形成相应的地理区域。该地理 区域的特点是: 17 华 中 科 技 大 学 硕 士 学 位 论 文 地理区域与地名一一对应。 任意相邻的两个地理区域之间，地名的值均不相同。 对“地名”这个位置相关数据的表示，可以让系统支持 “请告诉我当前所在的地 方”此类的位置相关查询。 3.1.1 位置相关数据的表示 设整个应用区域为 G X×Y，通过 L (x,y)表示移动对象任意时刻的位置，其中 x?X，y?Y。 定义 3.1:位置相关数据[21]。位置相关数据是指其值由具体地理位置决定的数据， 该数据具有地理位置依赖性。比如说天气预报，不同的地方有不能的取值。不妨设D 为任意一个位置相关数据，且D在位置 L处的值记为δ D, L 。 定义 3.2:数据区域[21]。不妨设任意一个位置相关数据 D，且在整个应用区域 G 中有n个地理区域分别记为 R D,1 ，R D,2 ，„，R D,n 。如果满足如下条件: (1)n 个地理区域之和为整个应用区域 G,且任意两个地 理区域之间没有重叠的 n 部分。即UR D,i G,且对于?i, j i ? j ,有R D,i IR D, j ? 。 i 1 (2)对于同一地理区域中任意两个不同的位置，其对应的位置相关数据的取值 一定相同。即对于?L , L ? R D,i 1 ? i ? n ,有δ D, L δ D, L 。 1 2 1 2 (3)对于任意两个不同地理区域的两个位置，其对应的位置相关数据的取值一 定不同。即对于?L ? R D,i ,?L ? R D, j 1 ? i ? n,1 ? j ? n, i? j,且R D,i 与R D, j 1 2 相邻 ,有δ D, L ? δ D, L 。 1 2 则称? D R D,1 , R D, 2 ,..., R D,n 为位 置相关数据 D 的一个数据区域划 分，其中R D,i 1 ? i ? n 称为 D的一个数据区域。具体 实例如图 3-1所示。 18 华 中 科 技 大 学 硕 士 学 位 论 文 (0 ，100) (100，100) 江汉区 青山区 武昌区 汉阳区 洪山区 (0 ，0 ) (100，0 ) 图 3-1 数据区域 3.1.2 位置信息与数据区域的映射机制 位置相关查询[35]的关键技术之一就是位置信息与数据区域的映射，通过这种映 射，把位置相关查询条件转化成传统关系数据库的查询条件。例如 “查找我当前所 在的地方”，对于这类型位置相关查询来说，首先通过位置相关数据的表示对地名 这个位置相关的数据对象实现地名到数据区域一一对应的划分，并通过多边开的表 示方法把数据区域以及与地名的一一对应关系存入数据库，当进行查询时，首先得 到移动对象的当前位置，把通过某种空间计算方式，得到当前位置信息所在的数据 区域。以图3-1为例，对“查找我当前所在的地方”进行说明。 定义 3.3:数据区域的表示。对于任意数据区域，都可以通过一个多边形来近似 的表示，所以数据区域的表示可以抽象为对多边形的表示。对于任意一个 N 边形， 先随机选择一个顶点作为起始点，并将其记为 V ，再沿着 N 边形的边按顺时针方向 1 依次把这个 N 个顶点记为 V 、V 、„、V ，得到一个顶点序列 V,V ,„,V ，即该 N 2 3 N 1 2 N 边形可以用顶点序列 V,V ,„,V 表示，并记为P V ,V ,„,V 。 对于 P V ,V ,„,V 1 2 N 1 2 N 1 2 N 具有如下特点: (1)?V ? V ,V ,...,V 0 ? i ? N ,V 用 X , Y 表示 。 i 1 2 N i i i 量 (2)?i 1 ? i ? N ,V 与V 的有向线段,记为 VV ,并且VV 的方向由向 i i+1 i i+1 i i+1 uv v r X ? X + Y ? Y j表示 注:当i N时,i+1取值为 1,即V 表示V 。 i i+1 i i+ 1 i N+1 1 (3)由顶点序列相邻点构成的有向线段共N条，且与 N 边形的 N条边一一对应。 19 华 中 科 技 大 学 硕 士 学 位 论 文 根据数据区域的表示方法，可以把图3-1所示的数据区域 表示成表3-1所示的数 据区域定义表。 表 3-1 数据区域定义表 地名 DataRegion 数据区域 Vertex 汉阳区 0,0 0,50 16,22 36,36 43,0 武昌区 43,0 36,36 44,68 71,63 85,43 63,24 78,0 洪山区 78,0 63,24 83,44 100,48 100,0 青山区 50,100 100,100 100,48 83,44 71,63 44,68 37,90 江汉区 0,50 0,100 50,100 37,90 44,68 36,36, 16,22 定义 3.4:点在有向线段右侧的判断方法。? 点 x,y 和 有向线段 VV ，且满足 i j uuv v X ? x ? X 或X ? x ? X ，同时VV 的方向矢量为r X ? X + Y ? Y j ，有向线 i j j i i j i j j i j i Y ? Y 段可以表示为函数 y ? j i x ? X ?Y ? 0 X ? X ? X 或X ? X ? X 。判断点 X ? X i i i j j i j i x,y 在有向线段VV 右侧的方法如下: i j uuv v 1 当 r X ? X + Y ? Y j 指向第 一象限时，即X -X 0且Y -Y 0，当且仅当 i j j i j i j i j i Y ? Y j i y ? x ? X ?Y ? 0 ，点 x,y 在有向线段 VV 右侧。 X ? X i i i j j i uuv v 2 当r X ? X + Y ? Y j 指 向第二象限时，即X -X 0且Y -Y 0,，当且仅 i j j i j i j i j i Y ? Y j i 当y ? x ? X ?Y ? 0 ，点 x,y 在有 向线段VV 右侧。 X ? X i i i j j i uuv v 3 当r X ? X + Y ? Y j 指 向第三象限时，即X -X 0且Y -Y 0,，当且仅 i j j i j i j i j i Y ? Y j i 当y ? x ? X ?Y ? 0 ，点 x,y 在有 向线段VV 右侧。 X ? X i i i j j i uuv v 4 当r X ? X + Y ? Y j 指 向第四象限时，即X -X 0且Y -Y 0,，当且仅 i j j i j i j i j i Y ? Y 当 j i y ? x ? X ?Y ? 0 ，点 x,y 在有向 线段VV 右侧。 X ? X i i i j j i 20 华 中 科 技 大 学 硕 士 学 位 论 文 uuv v 5 当r X ? X + Y ? Y j 指向坐标 轴时，如果 X -X 0 且 Y -Y 0，即方向 i j j i j i j i j i 矢量指向 y轴的正方向，当且仅当x-X 0，点 x,y 在有向线段 VV 右侧;如果X -X 0 i i j j i 且Y -Y 0，即方向矢量指向 y轴的负方向，当且仅当x-X 0， 点 x,y 在有向线段VV j i i i j 右侧;如果X -X 0且Y -Y 0，即方向矢量指向 x轴的正方向， 当且仅当 y-Y 0，点 j i j i