移动计算技术读书笔记

1、题目 题目作者名 孙杰, 作 者 张传楷, 作者1(软件学院 (系)全名,省 市(或直辖市) 邮政编码) 单位2(软件学园(系)全名,省 市(或直辖市) 邮政编码)7.移动数据管理及移动数据库 一、 移动数据库概述什么是移动数据库？移动数据库：移动着的分布式数据库，支持移动计算的分布式数据库。 即：（1）、人在移动是，可以访问数据库；（2）、人可以带着数据库移动。一般认为，移动数据是分布式数据库的推广，是支持移动计算的分布式数据库，由于移动终端是诸如掌上电脑、PDA、车载设备、移动电话等嵌入式设备，因此，又被成为嵌入式移动数据库系统。二、移动数据库应用移动数据库将在移动据算平台、家庭信息环境、

2、通讯计算平台、电子商务平台、车载计算平台等领域得到广泛的应用。移动数据库主要应用领域： 公共信息发布 实时数据采集 位置相关查询 配合GPS等技术电子商务D移动商务7.1移动数据库的特性 标题21、计算平台的移动性2、网络短接频繁性3、网络条件的多样性4、网络通信非对称性5、移动计算平台电源能力的有限性6、低可靠性7、系统的高伸展性等一、理想的移动数据库系统应实现以下四个目标：（1） 克用性和伸缩性（2） 移动性（3） 可串行性（4） 收敛性二、什么是分布式数据库？ 数据物理上被存放在网络的多个节点上，逻辑上是一个整体。三、移动数据库与分布式数据库的差别具体表现 （1）位置特性 分布式数据库：

3、处理的对象位置是透明的，事务所在位置清楚且不变化（2）不同的代价/性能观 分布式数据库中的最佳解决方案因移动性、机损跨区、通信的不对称性等因素，在移动计算环境中有可能不在使用。（3）事务处理的负载型 由于移动计算环境的特性：移动事务处理比分布数据库系统中的事务处理更复杂。由于用户常常要求在间断期间进行数据操作；所以对于本地数据库的自治性要求比较高。在移动事务处理模型的设计中必须考虑无线网络的有限带宽和通信的不对称性等移动计算环境特征，必须提供对移动终端断接操作的支持。还必须保持数据库系统ACID要求的基础上支持移动的事务处理。四、移动数据库的基本特点 （1） 移动性 （2） 移动事务处理 （3

4、） 故障修复 （4） 数据复制 （5） 查询处理 （6） 名字解析 （7） 异构性 （8） 易错性7.2 移动数据查询移动环境的特点：1、 查询模型和查询支持环境2、 查询优化标准的变化3、 个性化查询的变化4、 脱机查询的支持5、 查询语言和查询表达方式6、 查询的不确定性和不精度性7.2.1 移动查询模型一、移动查询模型大体上可分为两类：一类是基于客户缓存和复制的模型，另一类是基于代理的模型。基于客户端缓存管理技术：利用复制、缓存技术来支持间断条件下的查询，即采用数据缓存技术，分析用户访问数据的历史信息，并结合用户提出的简档文件决定缓存那种数据。基于代理的移动查询模式二、两类移动模型的对比

5、 基于缓存和复制技术的模型具有独特的优点，可以有效的支持断接的查询，但此类模型应用上具有局限性：要求移动设备端具有存储管理数据、数据同步等能力，承担处理任务比例大；不适合于高度动态的数据库查询。 基于代理的移动模型有着不可替代的作用，适用于受客户机，适合搞查询高度动态数据。7.2.2 移动查询语言1、 位置相关查询1）、位置敏感查询2）、位置相关查询2、与时空相关查询语言-FTL FTL主要使用了两个关于未来状态的算子UNTIL和NEXTTIME。形如 f UNTIL g 的语句表示当且仅当以下两个情形之一发生时满足：g在这时满足或将来未来某个状态下满足并且知道g满足前f是持续满足的；形如NE

6、XTTIME f 的语句表示当且仅当f在下一次满足的时候满足。在DOMINO系统中，一个查询由如下语法来定义： RETRIEVE<targets-list>WHERE <condition>此处condition由FTL语句给出如果一个不断移动的用户连续发出位置相关查询，则按照位置条件将以前查询结果进行缓存，可以使用花奴才能内部分数据满足部分查询要求，从而加快响应速度，减少通信开销，提高查询处理效率。7.2.3 弱连接下的移动查询技术弱连接：具有易中断、低带宽、高延迟或高费用等特性的通信链路。强连接：典型固定计算机网络，带宽高，费用低。无线移动通信网络的一个基本特性是弱

7、连接性在应用层的查询处理中如何适应这话总网络环境特性的变化构成了移动查询的关键技术之一。两种方法：最直接的做法：利用复制、缓存技术来支持断接条件下的查询，即采用数据缓存技术，分析用户访问数据的历史信息，并结合用户提出的简档文件决定缓存那种数据。另一种做法：采用代理技术，亦称适应性中间件技术。实际上就是一种根据数据流类型进行的有损压缩，目的是使应用能适应多变的网络环境。7.2.4 支持移动查询的人机交互技术易操作的人机界面 由于移动计算机的体积越来越小，键盘输入会代之以笔输入、图形或语言输入、传统的数据库人机界面必须加以改进。可视化查询语言表达 支持以单机图标的方式构造查询7.2.5 省电查询与

8、查询优化查询优化的主要目标:提高间断状态下移动数据库的可用性和查询效率，减少查询引起的通信开销，减少功耗，提高查询的可伸展性。移动通信在很多场合无法不保证始终具有可用的链路，未来保证提供用户可用的、正常的服务，必须支持断接查询。断接查询主要通过预存与缓存技术来实现广播查询: 广播数据组织方法、索引方法； 数据广播调度算法、三层复制体系结构间断查询： 卡内基梅隆大学CODA系统 缓存与同步算法7.3 移动数据管理7.3.1 数据广播一、 定义所谓数据广播是指数据库服务器把大多数移动用户频繁访问的数据组织起来，周期性地广播给移动终端，是移动用户以最小的代价有选择性地接收数据。二、 广播的局限性广播

9、是顺序进行的，用户需要持续保持接收听状态知道所需数据出现。数据访问时被动的，访问延迟与广播数据量成正比。利用数据广播访问数据库仅仅适用于查询输入数据集与结果数据集相差不大的情况。具有“拉”服务特征的从移动终端发出的查询能有更多自主性和针对性。“推”、“拉”服务的结合可以获得更好的综合性能。三、 数据广播的所研究的主要问题如何组织数据广播信道中的数据，如何在广播信道总分配数据和索引，即数据调度问题。衡量数据广播调动算法的参数有两个，即访问时间与调度时间。四、 数据广播的若干概念访问时间：也称访问时延指从移动终端提出数据请求开始，到用户从数据广播中得到结果为止所需的时间。访问时延决定了移动终端查询

10、的响应时间。访问时延由两个部分组成：探测等待和广播等待。调度时间：咋完成一个访问请求期间，移动终端保持侦听广播的总时间。移动终端必须保持在活跃才能监听广播信道的信息，因此调度时间的长短决定了移动终端的电能消耗。五、访问时延与调度时间的优化可以降电能消耗，这也是广播数据组织与调度的主要依据。 （1）访问时延优化 平坦调度：将所有及诶听数据广播的客户机所需的数据对象简单地并在一起，由服务器周期地广播，每个周期内每个对象都出现一次且只有一次。多盘广播调度 将数据重新组织，根据数据对象的访问概率，服务器确定每个对象在广播中所占的最佳比例。（2）调度时间的优化 在完成一个访问请求期间，移动客户机保持接听

11、广播的总时间 1）调度时间最优 简单索引平坦调度（SIFS） 是最简单的索引方法，在每个平坦调度的广播周期的其实处插入索引信息，每个广播数据单元都有附带的一个地址指针，这个指针指向下一个广播周期中的索引段的开始地址，移动终端在访问广播数据时，首先接听当前的一个数据单元，确定广播中下一个索引段的地址并等待索引的到来，并转入休眠状态，知道所需的数据项开始广播时重新激活，最后接受数据项。 2）簇集索引 高度索引方式包括（1，m）索引与分布式索引，它们均被称作簇集索引，所谓簇集索引是指具有ixangtong属性值的数据在队列中连续出现。 （1，m）索引是指在一个文件的广播周期中索引会被播出m次，整个索

12、引被放在数据队列的每个片段（1/m）之前。 4）访问时延 探测等待时间为（index+L/m）/2,找到索引段 广播等待时间为（m*index）+L）/2+C，找到记录并下载完成 访问时延=探测等待时间+广播等待时间=(m+1)*index+(1/m+1)*L/2+C 5)调谐时间 第一次探测是得到下一索引段的指针，然后，根据索引树的指针K次探测，找到第一个记录，最后还需要C次用以下载所有的记录。调谐时间=1+K+C通过上面的公式，可以计算出最优m值，读值使得访问延迟到达最小。7.3.2 移动数据复制与同步复制的主要目的： 提高移动计算系统的可用性，可靠性以及访问性能。传统的复制策略： 静态的

13、，由于系统管理员统一安排好复制结构就固定不变了。一、 两级复制机制针对移动客户机频繁断接的特点而提出构成移动数据库的节点类型。 数据库服务节点直接连串到固定网络上，维护数据库的第一级复制。移动节点通过无线网络与基节点连接，维护数据库第二级复制。在多个服务器上建立副本可保证移动终端移动到任何位置都能就近访问服务器得到所需信息。二、 两级复制移动节点的每个复制数据对象都维护两个版本 主版本从服务器节点得到的最新值 暂态版本断接对于由本地暂态事务更新的对象值两类事务 基事务只在对象主节点上执行，并更新版本 暂态事务间接时对本地暂态数据操作，产生新的暂态版本，以后将产生一个基事务，以更新数据只能访问主

14、节点是基节点或是本身的数据对象不能访问其他移动节点的数据。三、 两级复制的原理移动节点处于联机状态 从主节点复制数据移动节点处于断接状态 能够继续使用节点上的数据库 由暂态事务来处理数据对象移动界定啊结束断接，重新与基节点相连 丢弃基数据对象的暂态版本 将移动节点所有的暂态事务及其输入参数传送给基节点，由基接待你按照暂态事务在移动节点上的提交顺序依次执行对应的基事务。四、 断接情况下的复制有2种方法1、乐观复制 2、动态复制五、 三级复制为增强系统的灵活性与可伸缩性，提出了一种基于客户缓存、空中复制、服务器级复制的三级复制移动数据库系统结构TTR 启发式多盘调度算法 针对于空中复制，设计了一种

15、数据广播的启发式多盘调度算法。 该算法将待广播数据项分配到K个具有不同广播频率的盘中，并根据各盘的平均访问概率的平方根之比确定其相对广播频率，最终生成一种多盘数据广播调度序列。六、 三级复制的特点在TRR体系结构中，服务器纸复制通过在告诉网络中复制数据，不仅提高了整个数据库系统的可用性，而且使以哦对那个终端在任何一个无限网络单元都可以就近访问数据，从而分组了服务器的开销。服务器纸复制于移动终端缓存具有交互作用的特性，在保证系统收敛性的基础上，针对弱一致性与可变一致性情形获得事务执行可串行性。七、 复本的一致性维护策略从不同的角度，一致性维护策略可以有若干种分类： 由服务器方发起的更新传送策略，

16、由客户方发起的请求维护策略。服务器可以分为有状态服务器、无状态服务器与混合状态服务器。八、 移动终端与服务器的3种同步策略1）、回调策略2）、按需请求策略3）、定期广播更新策略7.3.3 数据缓冲与预存对于频繁访问的数据在本地进行缓存可以减少访问延迟，降低网络开销。缓存技术的目的：通过在客户机上缓存部分数据，达到减少访问数据库服务器，提高性能。传统的缓存技术要求客户机经常与服务器保持连接一、缓存失效报告广播技术客户机缓存的原因:减少通信量，避免网络堵塞缓存失效报告：由服务器发出的，通过移动客户机内缓存的数据变为失效的报告。缓存失效报告广播技术的目的：使客户机的缓存与服务器保持同步，服务器定期或

17、异步地广播缓存失效报告。二、缓存失效报告广播技术 时间戳广播算法 服务器定期地广播失效报告，失效报告由最近w个时间单位内被更新的数据对象标志id及其最新时间戳ts参数对（id，ts）组成。 若在失效报告中，某个对象的时间戳逼缓存中对应数据对象的时间戳新，则从缓存中清楚该对象。 如果失效报告中没有该对象的时间戳，则将缓存中该对象的时间戳更新为此次失效报告的时间戳。 失效终端算法三、移动环境下缓存替换策略五、 预取技术根据移动用户的行为，猜测用户将要用到的数据，在数据使用前预先取到移动终端的缓存中。CMU提出了TIP预取策略。7.4 移动事务及事务处理 事务概述 数据库事务的概念：所谓一个事务是由

18、一系列的读写操作组成的操作，以begin操作开始，以一个夭折操作或提交操作中止，它是数据库的逻辑工作单位。移动事务是由移动端提交的事务，它是分布事务的一种，其中部分计算在移动终端上执行，而其他部分在固定主机上执行。一、 数据库事务数据库事务：工作的一个逻辑单元一个事务由一系列操作组成，从一个begin操作开始，以一个提交活或者中止结束。二、 数据库事务ACID原子性：要么全都执行，要么全都不执行一致性：事务在完成时，必须所有的数据都保持一致隔离性：并发执行的各个事务之间不能相互干扰持久性：事务完成之后，它对于系统的影响是永久的。可能使食物ACID特新遭到破坏的因素有以下两种情况：（1）、多个事

19、务并发执行时，不同事务的操作交叉执行。（2）、事务在运行过程中被强行中止。7.4.2 移动事务特征移动事务：在移动终端上发起执行的事务。它实际上是一种分布事务，其中一部分计算放在移动终端上完成，而其他部分则交给固定节点完成。移动客户发出移动事务的方式有两种：（1）、在一个请求消息中发送事务全部操作，移动客户与协调器的交互以整个事务为基本单元，在发出事务请求后，将执行控制权交给协调器，直到该事务执行完毕。（2）、一个事务操作分多次发送。一、 移动事务处理的特点（1）、移动性（2）长事务（3）、易错性（4）、异构型7.4.3 关键问题及技术1、移动事务的一致性2、移动事务的持久性3、移动事务的过区切换4、移动事务的断接与恢复一般的处理一致性问题存在以下3种方法： （1）、可任意读/任意写的弱一致性复制 （2）、延迟的收敛性控制 （3）、每次写操作都进行依赖关系的检查7.4.4 移动事务处理模型理想的移动事务处理模型特点1 较低的事务夭折率2 正确性3 低通信代价和高并行性4 自