关键字：嵌入式系统; 体系结构; 移动数据库
1 引言
随着嵌入式系统和无线通信网络技术的飞速发展，出现了移动办公、移动通信等崭新的移动服务理念，人们对获取信息和使用信息的场合、时间、方式及方法提出了越来越多的需求。在这种应用需求推动的背景下，嵌入式移动数据库应运而生，成了近年来数据库发展的一个重要分支。本文对嵌入式移动数据库系统进行了深入的研究，完善和解决了嵌入式移动数据库系统的关键技术。
2 嵌入式移动数据库的系统模型
在传统的分布式计算系统中，各个计算节点是通过固定网络连接并保持网络的技术连接性的，而移动计算系统改变了这种假设条件。移动计算系统是固定节点和移动节点构成的分布式计算系统。移动计算的网络环境具有鲜明的特点：移动性、断接性、带宽多样性、可伸缩性、弱可靠性、网络通信的非对称性、电源能力的局限性等。移动环境中的分布式数据库就是移动数据库。它是传统分布式数据库系统的扩展，可以看作客户与固定服务器节点动态连接的分布式系统。移动数据库系统的模型[2][6]如图1所示。
其中，移动客户机MC（Mobile Client）包括便携式电脑、PDA等;MSS（Mobile Support Station）支持移动计算的固定节点，具有无线通信接口;FH（Fixed Host）没有无线通信接口，安装有数据库和数据库管理系统。
3 嵌入式移动数据库的关键技术
移动数据库涉及的理论和技术涵盖了当今通信和计算机发展的最新的成果，其中，在移动环境下如何进行数据管理是实现移动数据库的关键。在移动数据库系统设计中，需要考虑诸多在传统分布式数据库系统中不需要考虑的问题，如客户端的移动、客户端与网络的频繁断接、网络条件多样性、网络通信非对称、移动计算部件电源容量有限、可靠性低、伸缩性高、客户端与服务器数据的不一致性、移动数据查询等问题。为了解决上述问题，关于数据复制/缓存技术、数据广播技术、位置相关的查询优化等技术的研究，在移动数据库中具有特别重要的意义。这些技术都是解决由于客户端移动而带来的一系列问题的关键性技术。下面对移动数据库所涉及的几个关键性技术进行详细的阐述。
3.1 数据复制/缓存技术
该技术是解决移动数据库断接性的关键技术。传统的复制/缓存技术都是假设客户机和服务器之间是经常保持连接的，并基于这个前提来维护一致性。这在移动计算中是不适用的。目前，人们已经提出了多种移动复制算法，最典型的一个算法是:三层复制体系结构（Three-Tier Replication Architecture，简称TTR结构），下面我们就以TTR为例来介绍复制。三层复制体系结构[3]，如图2所示。
第一层复制是指服务器之间利用传统的复制技术在固定高速网络中所进行的复制，称之为“服务器级复制”。为了支持移动计算环境，一般采用一种弱一致性服务器级复制机制（ Weakly Consistent Server Replication，简称WCSR）。这种策略让每个复制服务器都支持查询与更新操作，并且允许各个复制之间存在暂时的不一致。因此，一个用户在访问数据库时，只需要访问一个复制服务器即可，而且不仅可以执行查询事务，还支持更新事务。为了降低通信开销，提高可靠性，WCSR采用了一种周期成对同步的方式，即每个服务器周期地选择另一个服务器，两个服务器之间交换各自的暂时事务日志，经过有限次的成对同步过程，最终使所有数据库状态达成一致。
第二层复制是指服务器利用无线网络固有的广播能力将数据库中经常被大部分用户访问的公共热点数据组织起来，经由MSS向无线网络单元内的所有MC广播，这实际上是在无线广播信道上做数据复制，称之为“空中复制”，空中复制充分利用了无线网络非对称性的特点。首先，因为无线网络特有的广播能力与普通网络中的广播显著不同，它可以支持大量MC同时接收，而且不管接收的客户数有多少，MSS的广播代价并不改变，这就允许大规模的移动用户同时访问被广播的热点数据，极大地提高系统的可伸缩性;其次，由于MC可以从空中复制取得常用的热点数据，使得其向服务器发送访问请求的频率也大幅减少，甚至没有必要再与服务器联机，这不仅可以使MC更有效地使用上行链路或避免代价较高的无线通信，而且减少了服务器处理每个联机MC的开销，进而使服务器可以同时接收更多联机MC的访问。可见，空中复制是一项开销不大，但却很有实际应用意义的技术。
第三层复制是为了支持移动用户的断接操作，MC利用本身的处理和存储能力缓存数据库中部分数据，称之为“客户机缓存”。由于MC的存储容量无法与数据库服务器相比，而且普通用户也不需要在断接期间访问整个数据库系统，因此在TTR体系中一般采用一种支持数据库的子集缓存的MC缓存机制，称作MCC（Mobile Client Caching）机制。MCC缓存机制的核心是缓存管理器，它在不同的网络连接条件下具有三种不同的工作状态，即联机状态、脱机状态、集成状态。在联机状态下，缓存管理器将MC用户的事务转交给服务器执行，并负责建立与维护MC的缓存:在脱机状态下，缓存管理器仿真服务器的功能，并将用户更新事务记录在本地的脱机事务日志中:在集成状态下，缓存管理器与服务器合并，并回到联机状态。
3.2 数据广播
通俗地讲，数据广播[4]是指在移动计算环境中，利用客户机与服务器通信的不对称性，以周期性广播的形式向客户机发送数据。其最大的优点是，广播开销不依赖移动用户数量的变化而变化，借助数据广播，可以在一定程度上解决移动数据库系统的断接问题。
数据广播技术研究的关键问题是:数据广播调度问题。而数据广播调度的关键是采用什么样的调度算法，如何确定广播的周期。日前，有关数据广播调度的研究主要集中在访问时间和调谐时间的优化问题上，但存在较大的局限性，如只考虑访问时间的优化或调谐时间的优化，不能较好地将两者结合起来，且现有的数据广播的调度机制大都缺乏可操作性，不支持移动数据库系统的实际应用。针对这些不足，数据广播技术研究中有必要从理论上分析访问时间和调谐时间的最优值，并以理论分析为指导，提出一种能在优化调谐时间的同时仍保持较低访问时间的数据广播调度算法。
数据广播的调度可以看作一个带宽分配问题:给定所有客户机访问数据项的概率分布，服务器试图确定每个数据项在广播带宽中所占的最佳比例，然后根据这个比例产生广播程序。一种最简单的调度方法是将所有待广播的数据项简单地并在一起，在每个广播周期里任意数据项都出现一次且只有一次，且每个数据项的平均访问时间都是相同的（即广播周期的一半），这种调度称为平坦调度。如果在一个广播调度中，各个数据项出现的次数不一定为1，即所占的带宽比例不一定相同，则将该调度称作非平坦调度。但是，仅仅确定各数据项的带宽比例是不够的，如果在一个广播周期中数据项的间距（即两次出现之间的时间差）不均匀，那么非平坦调度并不能产生好的效果。这里可以通过一个简单的例子说明这一点。如图3所示，包含3个数据项的数据广播可以有3种不同的调度方式:程序a是平坦调度;而程序b和程序c是非平坦调度，其中数据项d1在一个广播周期中出现两次，而数据项d2和d3只出现一次。程序b是一种偏斜调度，因为在一个周期里，数据项d1的两次出现连在一起，使得d1的广播间隔时间不均匀。程序a则是一种均匀调度，其广播周期中每个数据项在广播带宽中所占的间隔时间都是均匀的，这样，数据项dl好像存在一个速度比d2和d3快一倍的磁盘上，这种调度称为多盘调度（Multi-Disk schedule）。假设移动客户机数据项访问请求的到达是完全随机的，即可能落在数据广播周期内的任意时刻.表1列出了在不同的数据项访问概率分布下三种调度程序的平均访问时间。
表1说明了三个问题：首先，当数据项访问概率均匀分布时（即为1/3）平坦调度的平均访问时间最低。这说明多盘调度技术不能随意使用，在某些场合下可能得不偿失。其次，当数据项访问概率分布趋向偏斜时，非平坦调度的性能将优于平坦调度。最后，在两种非平坦调度中，多盘调度的性能都将优于偏斜调度，这说明均匀的非平坦调度可以获得更好的性能。
多盘调度算法构造一个广播调度程序的过程为：
（1）将所有数据对象按照访问概率递减次序排序。
（2）将这些数据对象依次分割到K个相邻的租，称为“磁盘”。定义磁盘Bi的容量Ci为磁盘对象的个数。
（3）确定各盘的相对广播频率fi，即各盘对象在广播中所占的带宽之比。fi必须是互质的整数，i=1，2，……, k。
（4）产生广播调度程序。
● 将每个盘分割成若干块。首先，求得所有盘的广播频率的最小公倍数LCM;然后,将每个盘Bi分割为num_chunks（i）=LCM/fi个相同大小的块,记为Cij ，j=1，……，num_chunks（i）。若Bi不能整分，则在不满的块中填充空闲数据。
● 按如下程序交错广播各盘的块，生成广播调度。
For（i=0; i
For（j=1; j=k; j++）
广播块 Cj（i mod num_chunks（j））;
3.3 位置相关查询优化
在移动数据库中，存在着与位置相关信息的查询及更新。查询通常是与位置相关的，即使是同一个问题，在不同的地方，所得查询结果是不同的，如“最近的医院在哪里?”。移动查询优化技术是指在传统分布式数据库查询优化技术的基础上，利用多种方法，消除带宽多样性、断接等因素造成的影响，使查询引擎能够根据当前可用网络条件采取恰当的优化策略;同时，针对移动计算机有限电源能力，合理地组织本地数据库管理、远程数据库访问等耗电能较多的操作，达到节能目的，延长关键数据的可用时间。
采用基于分割的地址更新策略时，由位置服务器维护的移动用户对象包含以下数据成员和方法：
分割集合——记录MSS的分割情况，例如｛Cell1,Cell2｝,｛Cell3,Cell4,Cell5｝;
LOC——记录移动用户最近报告的地址（无线单元的ID），例如Cell1;
ERR——移动用户当前所在的分割，例如，若LOC=Cell1,则ERR=｛Cell1,Cell2｝;
loc（）——一个方法，用于返回该用户的实际地址，即上面介绍的地址查询过程。
在移动查询的应用中，有各种各样涉及地址的查询，例如“请寻找一名校园附近的医生”，“查找X，Y，Z，这三人都在同一条公路上，且Y在X与Z之间”，等等。一般地，可以把这一类地址相关查询表示为：
SELECT x1,x2,…，xn
FROM Users
WHERE（x1.loc=11∧…∧xn.loc=1n）∧C（11,…，1n）∧W（x1,…,xn）
其中C（11,…，1n）是关于地址11，…，1n的n元约束条件，而W（x1,…,xn）是关于对象x1,x2,…，xn非地址属性的n元约束条件，Users是所有移动用户的集合。
这种位置相关查询需要检查各个对象的实际地址是否满足约束条件而这些实际地址必须进行地址查询才能得到,因为位置服务器只提供分到一级不精确的地址。因此，要求得位置相关查询的最终答案，必须先查询足够的精确地址信息。若对这一类查询进行适当的优化，可以大大减少查询地址信息所需的通信开销。
4 结束语
嵌入式移动数据库将随着各种移动设备、智能计算设备、嵌入式设备的发展而迅速发展。它将在未来的军事、航空、国土资源管理、移动医疗等领域中扮演越来越重要的角色。嵌入式移动数据库是一个崭新的研究课题，至今还有许多问题有待解决，在移动数据库技术逐步走向成熟的时候，必将产生巨大的商业和社会价值。
本文作者创新点：
鉴于移动计算环境中客户机与服务器通信的不对称性和数据传输的断接性问题，笔者提出了三层复制体系结构和多盘调度算法，并对部分问题探讨了其初步的解决方式。
参考文献：
[1]D Barara. Mobile computing and database — A survey. IEEE Trans on Knowledge and Data Engineering. 1999,11（1）:108～117.
[2]王珊 ,丁治明. 移动计算中的移动数据库[N]. 微电脑世界, 2001,8.25
[3]胡虚怀，郑若忠.移动数据库及其关键技术[J]. 计算机系统应用，2000,5（1）:29～32.
[4]王磊，邵时.移动数据库中广播技术的研究：[硕士学位论文][D]. 上海：华东师范大学计算机科学技术系，2004. 13～15.
[5]李东，曹忠升. 移动数据库技术研究综述[J]. 计算机应用研究， 2000,（10）:4～7
[6]牛立新，关永，刘旭敏. 嵌入式移动数据库研究[J], 微计算机信息， 2006，第22卷第1-2期，85-87页转251页.
