移动时空数据库中一些技术的探讨*

吴春辉，徐万和

（1.湖北科技学院 计算机科学与技术学院，湖北 咸宁 437100；

2.通城县地方税务局，湖北 通城 437400）

随着移动通信技术的迅速发展和使用，许多计算结点已经可以在自由移动的过程中保持与网络的连接.于是人们迫切需求能在任何时候、任何地点访问任何数据，这使得原来基于有线网络和固定主机的分布式数据库不再适应，因而移动数据库技术便应运而生.新的应用对移动环境下的事务处理提出了新的需求，如实时交通信息管理系统、海上导航系统及股票交易系统等，该类应用普遍要求在移动环境下实现实时事务处理.移动实时数据库系统（MRTDBS）正开始受到越来越多的研究人员的关注.一般认为移动实时数据库系统就是移动环境（如GSM网络和无线局域网）所支持的实时数据库系统［1］.

以计算机网络为中心的移动计算技术得到广泛应用，随着智能移动终端的普及，人们对移动数据的实时处理和管理要求不断提高，同时在对无线网络和时空要求也越来越迫切，因此在分布式计算、实时处理、移动通信、无线实时查询等各个方面都有着非常广泛的应用.

1 移动数据库

移动数据库是伴随着移动计算诞生的.移动计算是一种新型的技术，它使得计算机或其它信息设备，在没有与固定的物理连接设备相连的情况下，能够传输数据.移动计算的作用在于，将有用准确及时的信息与中央信息系统相互作用，分担中央信息系统的计算压力，使有用准确及时的信息能提供给在任何时间任何地点需要它的任何用户.移动计算环境比传统的计算环境更为复杂和灵活.凡是有数据的地方，就要用到数据库来协助管理数据移动计算也是对数据的处理，离开对数据的管理处理，计算机就毫无意义移动计算同时又强调其移动性，传统的 PC机要做到移动，同时在苛刻的环境下作到良好的运作也是不可能的，当然，嵌入式很好的满足了移动计算对移动客户端计算的要求三者从这一点上结合就产生了当今数据库的一个新的发展空间：嵌入式数据库技术移动数据库是指支持移动计算环境的分布式数据库［2］.

纵观数据库技术发展过程，计算环境和数据库技术基本保持着一种同步发展的态势，它们互相影响，互相促进.计算环境先后经历了集中式、分布式、网络以及目前受到广泛关注的移动计算环境MCE（Mobile Computing Environment）等多种计算模式.相应地，数据库系统的发展也经历了集中式数据库系统、分布式数据库系统、B/A/S多层结构的数据库系统、嵌入式数据库系统和移动数据库系统等多个阶段［3］.

与基于固定网络的传统分布计算环境相比，移动计算环境具有移动性、频繁断接性、网络条件多样性、网络通信的非对称性、不可靠性、规模易变性及电源能力有限等特点［1］.这些特点都要求移动实时数据库系统必须具有比传统客户/服务器及分布式数据库系统高得多的可伸缩性.同时，那些传统分布式计算和分布式数据库的研究基于有线网络和固定主机的默认隐含假设，如固定网络连接、对等通讯代价、主机节点固定不变等在此也已不再成立.

移动实时数据库系统可以定义为：事务和数据可以具有定特性或显示定时限制，并运行在移动计算环境的数据库系统.移动实时数据库是在移动计算环境下的分布式、实时数库，其本质特征是实时处理、分布式计算和移动服务.一个移实时数据库系统包括移动客户机（MHS）、固定主机（Fhs）、位置服务器（LS）、移动支持基站（MSSs）、固定网络和移动网络［3］.

2 移动时空数据库中的关键技术

2.1 同步机制：在移动数据库的实际应用中，如何在错综复杂的移动环境下高效地实现数据的最终收敛：即保持数据的一致性是关键问题，而这数据的最终一致性是整个系统的根本所在，也是同步过程所要达到的目标，数据的一致性有紧密一致性和松散一致性两种类型，传统的分布式数据库系统属于紧密一致性，也就是说在传统的分布式数据库系统中，数据可以在任何时候都保持一致性，在固定征稽系统中即是如此，而在移动征稽系统中由于移动环境与网络的断连接，资源有限，要实现数据的紧密一致性往往是不现实的.因此，数据的收敛通常是采用松散一致性来完成的，即不能保持数据的时刻一致，但是可以允许暂时不一致，进而可以采用同步技术来保证数据的一致性［4］.

2.2 数据广播技术：无线通信网络的迅猛发展使得移动计算成为现实.移动支持站点把被频繁请求的数据组织起来，以广播的形式传送给移动客户.移动实时环境里数据广播的首要问题是广播内容的选择.被频繁请求的热点数据能够及时广播，将会满足大量客户的需求，提高系统效率.传统的频繁元素获取通常采用计数、概要、分位数和散列等技术，时间性能最好的是散列类算法.在伯努利大数定理和马尔科夫不等式的基础上，通过统计散列冲突估算频繁元素出现的次数，利用多个散列函数和散列表可以使得误差被控制到精度许可的范围内.多散列计算可以充分利用现在主流多核微型处理器的计算能力.只需要增加散列函数的.

数量就可以提高统计精度，而增加的计算时间却很少.以最少的时间和能源消耗获得最多有用的数据是移动客户在数据广播中获取的最大效益.数据广播调度从客户效益出发，采用基于优先权的调度策略.优先权综合考虑了数据截止期，数据的被请求频率和数据请求的到达时间.通过参数来调整它们的权重，使得调度策略能够在满足数据请求成功率的基础上，权衡平均访问时间和调谐时间.在调度策略的实施过程中将同一客户请求的数据尽可能地放在一起调度播出.数据组织结构里增加了热点数据指示器，移动客户在侦听信道的时候，可以根据自己设备的电源情况，有选择地下载各级热点数据，提高缓存命中率，降低上行信道负荷和平均访问时间，提高系统的处理能力.实时系统中数据访问偏斜时，数据广播的索引技术鲜有研究.建立索引一方面要考虑数据的访问概率，另一方面要考虑数据的时间限制；同时构建索引的算法本身的时间复杂度要低.近似最优二叉索引树参考静态最优查找树的构造思想，在处理节点概率权重时引入实时加权，快速构造出查找效果近似最优的二叉索引树.其查找过程类似于折半查找，平均查找长度和logN成正比，即调谐时间至多logN个时间单位.因为考虑数据访问概率，被频繁访问的数据放在广播序列的前端，缩短了平均调谐时间；因为考虑了实时加权，时限较短的数据也放在了广播序列的前端，提高了实时系统中数据请求的成功率［5］.

2.3 路网下的最近邻动态查询：对于快速发展的无线技术，基于位置的服务（LBSs）成为可能，其中基于位置的查询（LBQs）技术是一个非常热门的研究课题，而在基于位置的查询（LBQs）中最近邻查询（NN）又是最多最实用的一种查询.当然这其中涉及了很多方面的问题，比如：

（1）居住在某小区的人想要找到离家最近的超市，这个问题可以抽像为这个问题，把其周边可以设置一个范围如100公里之内的超市，把超市作为一个一个的节点，构造一个图，然后此人就可以通过查找离他家最近的那个节点即可，这类问题是最简单的一个问题，因为查找者和查找对象都是静态不变的.

（2）行驶在公路上的汽车查找最近的加油站，这个问题实际上就是最近邻查询问题，可以把加油站想成一个一个的节点，汽车查找最近的那个节点即可.当然在此类问题中在路上行驶的汽车是运动的，查找对象时静态的，此类问题就要复杂，因为在查找过程中，汽车是移动的如果查询结果延迟过高，那么查询的准确性就不高，所以其中存在很多问题值得研究.

（3）路上的行人搭乘出租车，这个问题也是最近邻查询问题，但是比上个问题还要复杂些，因为行人是在行走的，是动态的，而出租车是在行驶的，也是动态的，所以查询者和查询对象都是动态的，在查找过程及查找准确度上都要负责的多.

基于位置的查询（LBQs）的返回结果是基于某些位置信息.在无线技术中有两种基本的方法访问位置信息：请求访问和周期广播［7］.请求访问使用的是一个基本的客户－服务器模型，移动客户（MC）提交一个查询给服务器，服务器就会处理这个查询并且通过点对点的专用信道返回一个结果给客户.这种访问请求数据方法适用于负载竞争信道小的系统.然而，当没有上行信道时，移动客户（MC）就不能发送查询给服务器，更不能实时的获得结果.还有，所有的查询请求都是在中心服务器处理，这将导致很多问题：服务器将变成系统的瓶颈，所以系统性能会很低；服务器必须同时处理大量的查询请求这将影响结果的实时性.为了克服以上缺点，周期广播方法被提出，在周期广播中数据项通过无线信道被周期广播，移动客户（MC）负责查询处理.无需发送任何信息给服务器，客户只需简单的侦听广播信息来查找与自己查询相关的数据，然后处理查找到的数据并自动的返回查询结果即可.这种周期广播方法相对来说非常适用于高负载系统，并且移动客户可以分布式的自动处理.

当然，有很多基于点对点方式进行基于位置查询的研究，但是性能不是很好，最近有很多研究者开始瞄准适用周期广播方式进行基于位置查询的研究.很多研究结果已经出现在以下文献中［8～14］.并且所有存在的基于周期广播位置查询方法都是用的欧氏空间，没有人用在网络空间.实际上移动客户经常会在某系网络中移动，如路网、铁路网、飞行网等.

在文献［6］中，作者提出一种数据广播环境下路网中最近邻查询处理的方法（NBNN），其中最主要的问题是如何分割基本的网络和将网络和其中的对象组织在一个序列包集合中，从而信息能够在网络中广播.作者使用了网络维诺图（NVD），维诺图包含很多多边形，多边形中的任何点的最近邻都是多边形的节点对象.作者就是通过维诺图来构建路网模型，然后作者又提出一种有效的方法叫NVD方格分割，把NVD分割成很多网格从而形成一个网格树，叫NVD网格树，从而保持每个单元的NVD结构.同时给出了GC－code编码为树中每个节点，只要给定一个空间的点，即可计算出其对应的网格的GC－code编码，然后以后序遍历方式线性化树中各叶子节点即格子编码即可得到一个广播序列.

当然在无线广播中，调谐时间和访问时间是能量消耗和访问延迟的两个重要指标.因此使用索引结构以使得移动客户有选择的侦听广播信息将有助于节省能量.在文献［6］中作者提出一种基于NVD的分布式索引结构，叫NVD－ID.这种索引允许最近邻查询可以在任意的时间开始执行，并且每个查询操作可以在一个广播周期内完成.同时，这种索引结构也大大减少了能量消耗和访问时间延迟.

文献［6］中提出的NBNN方法主要有以下几步完成：

（1）通过使用一个对象属性标记路网中每条边，这些边属于维诺多边形中的一个特定对象，即需要根据实际需要，根据实际对象构建相应的维诺图.

（2）NVD方格分割，即将1）中建好的NVD图分割成很多格子单元，把这些划分的单元构建一方格树，即NVD方格树，保持NVD结构，特别是，NVD树很好的平衡了大小和很好的位置保护行为.

（3）然后对NVD树提出了一种数字编码技术，即用二进制对NVD图中的每个格子单元即树中所有节点进行二进制编码，并且米格查询客户都可以通过自己的位置坐标计算出其所在的格子单元，从而转换为相应的GC编码.

（4）针对于移动客户的能量消耗和访问延迟，提出了一种比较好的索引方法，基于NVD分布式索引，这种索引方式不但使得每个客户都可以随时执行自己的查询并且都可以在一个广播周期内就可以得到相应，同时大大减少了能量消耗和时间延迟.

但是尽管文献［6］提出的方法新颖并且效率也很好，但是本人认为很存在一些问题，首先存在以下一些局限性：

（1）查询对象只考虑了一种类型对象，对多种类型对象并存时如何有效查询，并且若对象很密集，此时若为每一对象分配一区域，将会使区域很小，从而会导致区域个数很大，那每个对象对应的编码就会越长，生成的树也会越深，在转换成一个广播帧时，帧长会很大，也会导致广播及接收能耗增大.

（2）移动客户提出请求后有可能继续移动，要判断在等待延迟时间内是否已经运动出了所在区域，若出了所在区域，则查询将不准确.同时只考虑了对静态对象的查询，未考虑对动态对象的查询.

解决方法：

a.能否针对密集对象时不是为每个对象分配一区域，而是为一组相邻的对象分配一个区域，从中选择一个中心节点，负责其他信息的收集接收等工作.

b.针对编码变长，能否对编码进行优化，使编码更短些，从而缩短帧长.

c.对移动客户上安装的传感设备，能够适量增加一些存储空间用来存储部分数据，实现主动的通过邻居节点信息进行实时动态查询.

d.在进行划分区域时，只考虑静态情况，如何在动态增加某些对象时加快实时更新也是个问题.

e.能否进行分布式的定位查找，以提高速率和实时性.

f.是否考虑传感器也可以接收交通网中的任意一个移动客户信息，从传感器网络的角度进行查询搜索信息，主动的发送和接收包.

2.4 无线广播下连续近邻查询：此问题是本人针对上述文献［6］中局限性2中的移动客户提出请求后有可能继续移动提出的，在基于位置查询中连续近邻查询（CNNQ），此类查询是在客户从开始位置到目的地移动中连续查找离查询位置最近的对象.与快照查寻只需评估一次相比，连续近邻查询（CNNQ）需要连续评估查询结果直到满足要求为止.连续近邻（CNNQ）可以分为两类：一类是静态查询移动对象，另一类是移动查询移动对象.在文献［11］中就针对第二类查询即移动查询移动对象进行了研究，作者假设存在的移动对象集合和一个中心服务器用来检测它们的位置信息并通过周期广播它们的位置信息给分布在各个不同位置上的客户.在移动连续近邻查询（MCNNQ）过程实际是，在客户和查找对象都移动的情况下移动客户连续的查找距离查询位置最近的对象.在文献［11］中，作者提出一种新的基于位置的三维查询处理算法来支持无限网络广播环境下（MCNNQ）服务使用者和目标对象都能移动.并且研究了同时执行的性能问题、在移动对象和查询增加情况下连续查询问题.并且使用对象位置和移动速度定义了一保证区域（GR）.客户在保证区域（GR）能确保最近邻对象而不需等待和调谐广播信道.此种方法是 Exponential Sequence Scheme with Guaranteed Region（ESS_GR），此方法适用于静态和移动两类查询，具体步骤如下：

1）定义了保证区域（GR），实际是将查询线分割成了一些分离的线，从而使得在每个保证区域（GR）中的点的最近邻对象相同.保证区域（GR）使得移动客户查找移动对象中找到准确的答案.并且精心选择调谐来节省移动客户的能量资源.

2）ESS_GR算法支持无线广播环境下动态连续的最近邻查询，并且对于很多客户同时请求同一数据的查询是非常适用.

文献［11］确实是对文献［6］中的局限性有了有力的补充，但文献［11］在广播建立索引及客户能量消耗上没有精心考虑，当然如果能结合两者优点效果应该会更好.同时对文献［11］中尽管通过几何方式得到保证区域（GR），但是在查询线上仍存在一些盲区，当然这也是不可避免的，能否寻求一种更好的方法使得盲区尽量小，是一个值得研究的问题；在已有的文献中只考虑二维空间下的查询，而三维空间下的查询，研究甚少，事实上三维空间下的查询将会更加有用如：飞行航线即为一三维空间下的查询、海底潜艇的查询等.

2.5 易错无线数据广播下分布式空间索引查询的创建：此问题是本人针对上述文献［6］中局限性1中对多种对象及容错性方面进行了探讨，当信息可用时，不仅仅是在正确的时间，而在正确的位置时，对于使用者来说也是非常重要的，当然在基于位置数据访问中，分布式索引（DSI）起着非常重要的作用，因为这种索引方式使得很多查询路径共享，从而使得查询的容错性大大提高，并且支持经典的基于位置的快照和连续模型查询，窗口查询和kNN查询等.窗口查询是指查询所有以一查询点为中心的查询窗口中的所有查询对象，kNN查询是指查询查询点最近的k个对象.在两种情况下，查询点可以是最近的用户位置或者是预先的用户移动轨迹.在文献［14］中提出的DSI，考虑了三个方面因素：

1）性能需求上考虑了能量耗费和访问效率

2）本身的不可靠性和无线通信的易错性

3）一般基于位置查询的支持

考虑到客户的移动性，不仅仅考虑了典型的查询点固定的快照查询，还考虑了查询点按照预定轨迹移动的连续查询.连续查询用于客户将来的移动是计划好的情形下，DSI方法有很多的优势如下：

①它组织对象数据是以一定的线性顺序.这样自然的适合无线广播数据媒介以提高索引效率和广播任务.

②它有一完全的分布式结构允许查询处理立即开始因而最小化了不必要的等待时间.这个性质大大缩短了查询数据的访问延迟.

③它提供了对同一对象的多路径查询并且共享一般查询路径从而最小化了索引信息的带宽负载.

④它在无线数据广播本身易错性通信环境下非常可靠，客户可以恢复，而不用重新开始，在错误发生时查询处理操作大大减少.

⑤它支持很多类型的基于位置的查询，包括窗口查询和kNN查询.

在文献［14］中，还有考虑多方向的扩展DSI，DSI只考虑了同性质类型的数据对象查询，而未考虑多类型数据对象的查询，并且在三维环境下查询的处理会涉及到多类型数据.并且要考虑复杂查询下索引效率的提高及基本系统框架的构建.并且可以把一些相关信息放在各个移动客户上，因为现在内存越来便宜，这样就可以实现分布式的快速的高响应的实时查询.

3 结论

本文对移动时空数据库中的一些技术及前沿方法进行了简要的介绍，主要从同步技术、数据广播技术、基于位置的最近邻查询技术进行了阐述，重点以文献［6，11，14］介绍了基于位置的最近邻查询技术，并且提出了一些自己想法和有待于研究的问题，主要是能否将二维空间的查询扩展到三维空间中去，如何提高查询的准确度和实时性等都有待于研究者进一步研究解决，并且三维空间的查询应用将会越来越广泛，越来越迫切，总之，在移动时空数据库中最近邻查询这个领域还有很多问题值得人们去思考，研究和实践.

［1］E Kayan，O Ulusoy.An Evaluation of Real－ Time Transaction Management Issues in Mobile Database systems［J］.The Computer Journal，1999，42（6）：501 －510

［2］钱希志，陈志泊.移动数据库关键技术及其研究应用［J］.微计算机信息，2010，26，（102）.

［3］肖迎元，刘云生，廖国琼.移动实时数据库系统综述［J］.计算机工程与应用，2004.35：173～177.

［4］黎娜，张庆吉.移动数据库同步技术及应用［J］.现代计算机，2011，05：76 ～78.

［5］吴海.移动数据库同步技术及应用［D］.博士论文，2010，11.

［6］Yanhong Li，Guohui Li.Searching Nearest Neighbors in Road Networks on the Air［J］.The Elsevier Jairnal，2011，12.

［7］S.Berchtold，D.A.Keim，H.P.Kriegel，and T.Seidl，“Indexing thesolution space：A new technique for nearest neighbor search in high － dimensional space”［J］.IEEE TKDE 2000，12（1），pp.45～57.

［8］S.E.Hambrusch，E.Liu，W.G.Aref，and S.Prabhakar，“Query process － ing in broadcasted spatial index trees”，in SSTD（2001），pp.502～521.

［9］Chuan－Ming Liu and Shu－Yu Fu，“Effective protocols for knn search onbroadcast multi－dimensional index trees”［J］.Information Systems，2008，33（1），pp.18 ～35.

［10］K.Park，M.Song，and C.－S.Hwang，“Adaptive data dissemination schemes for location－awaremobile services”［J］.Journal of Systems and Software，2006，79（5），pp.674 ～688.

［11］ Kwangjin Park，Hyunseung Choo，and Patrick Valduriez，“A scalable energy － efficient continuous nearest neighbor search in wireless broadcast systems”［J］.in Wireless Netw ，2010：16，pp.1011～1031.

［12］B.Zheng，W.－C.Lee，and D.L.Lee，“Search continuous nearest neighbors on the air”，in Proc.MobiQ-uitous，2004，pp.236 ～245.

［13］B.Zheng，W.－C.Lee，and D.L.Lee，“On searching continuous k nearest neighbors in wireless data broadcast systems”［J］.in IEEE Transactions on Mobible Computing，2007，6（7），pp.748 ～761.

［14］B.Zheng，W.－ C.Lee，D.L.Lee，C.K.Lee，and M.Shao，“A distributedspatial index for error－ prone wireless data broadcast”［J］.in The VLDB Journal ，2009，18，pp.959～986.