（控制理论与控制工程专业论文）嵌入式移动数据库的初步研究.pdf

摘要 摘要 计算机技术和无线通讯技术的发展与结合使得一种全新的计算环境移动计算 成为现实。移动数据库的概念应运而生。目前移动数据库的研究己经成为一个热点。本 文对嵌入式移动数据库进行了初步研究，着重解决了基于z i p f 法则的多盘调度算法中倾 斜因子的确定和同步技术中使用互斥量。z i p f 函数中口是倾斜因子，0 越大分布越倾斜。 访问概率的0 由实际中移动客户对数据的请求情况决定，而磁盘的臼并没有统一的取 值，且0 的不同取值对分盘结果有比较大的影响，也势必影响平均访问时间，而访问时 间决定了移动用户响应速度的快慢，从而影响到数据库的性能。互斥量是w i n d o w 系统 的线程同步对象，在同步中使用互斥量，可以简化同步过程，减少系统丌销，这在对于 数据处理要求不高的工业应用中是可行的。 在移动计算环境中，数据广播是一种发布数据的重要途径，能有效支持对具有公共 访问兴趣的热点数据的访问。数据广播的一个首要问题是如何调度待广播的数据，优化 数据广播的访问时间和调谐时间。在减少访问时间方面，人们提出了许多广播调度的算 法，也有大量相关的研究。通过比较数据广播的平坦调度与非平坦调度，说明多盘调度 的优越性。分析了定长数据下数据平均访问时间的最小值的公式和实现条件。 接着介绍了基于z i p f 法则的多盘调度算法，在很多文献都提出基于z i p f 分布的分 盘策略，但对倾斜因子口的取值则没有进步的探讨，而0 的墩值对分盘结果的影口向还 是比较大的，因此提出确定0 取值的方法还是比较有意义的。然后讨论了基于z i p f 法则 的多盘调度算法中的访问概率倾斜因子和磁盘倾斜因子如何确定，最后用c 语言模拟实 验，求出0 和最小平均访问时间。 然后详细研究和分析移动数据库的同步机制各个方面关键技术问题，其中重点分析 了数据分发问题，数据一致性问题，故障恢复问题等。最后提出了在同步过程中使用互 斥量，互斥量是一个数据结构，它能够保证它在任何一个时刻只会被同一个使用者使用， 这个使用者可以是进程、线程或者其他任何使用它的主体。最后编写了读写控制程序和 读写同步演示程序，给出了这两个程序的流程图。 关键词：嵌入式移动数据库，多盘调度算法，倾斜因子，同步技术； ：奎三些查兰兰璺土耋堡丝圣 a b s t r a c t t h ed e v e l o p m e n ta n di n t e g r a t i o no fc o m p u t e rt e c h n o l o g ya n dw ir e l e s s c o m m u n i c a t i o nt e c h n o l o g yh a v er e a l i z e dab r a n dn e wc o m p u t i n ge n v i r o n m e n t 1 n o b i l ec o m p u t i n g m a n yc o n c e p t so nm o b i l ed a t a b a s e sh a v eb e e np r o p o s e d t h es t u d yo fm o b i l ed a t a b a s eh a sb e c o m eah o ts p o t t h isp a p e rp r e l i m i n a r y r e s e a r c ho i le m b e d d e dm o b i1ed a t a b a s e ，a n de m p h a t i c a l l ys o l v ed e t e r m i n i n gs k e w f a c t o rw h i c hi st h ev a l u eo fz i p f m d s a ，a n du s i n gm u t e x i n s y n c h r o n o u s p r o c e s s e s t h et h e t ai nz t p jf u n c t i o ni ss k e wf a c t o r t h eg r e a t e rt h et h e t ai s ， i t sd i s t r i b u t i o ni sm o r eg r a d i e n t t h ea c c e s s p r o b a b i l i t y0i sd e p e n d e do n t h er e q u e s to fa c t u a lm o b i l ec u s t o m e r ，a n dd i s ks k e wf a c t o rd o e s n th a v et h e u n i q u ev a l u e d i f f e r e n tv a l u eo ft h e t ah a sg r e a ti m p a c to n t h er e s u l to f d i s s e m i n a t i n gp l a t ea sw e l la st h em e a na c c e s st i m e t h er e s p o n s es p e e do f t h em o b i l eu s e r si sa l s od e p e n d e do nt h ea c c e s st i m e ，w h i c hi sg o i n gt oa f f e c t t h ed a t a b a s ep e r f o r m a n c e t h em u t e xi ss y n c h r o n o u so b j e c to fw i n d o w s s y s t e m u s i n gm u t e xi ns y n c h r o n o u sp r o c e s s e sc a ns i m p li f yt h es y n c h r o n o u s p r o c e s s e sa n dr e d u c et h es p e n d i n go fs y s t e m d a t ab r o a d c a s t i n gisa ni m p o r t a n tw a yf o rd a t ad i s s e m i n a t i o ni nm o b i l e e n v i r o n m e n t i tc a ne f f i c i e n t l ys u p p o r ta c c e s st oh o td a t a w i t hc o m m o n i n t e r e s t o n eo ft h ep r i n c i p a lp r o b l e m so fd a t ab r o a d c a s ti sh o wt os c h e d u l e t h eb r o a d c a s td a t a ，s oa st oo p t i m i z et h ea c c e s st i m ea n dt u n i n gt i m eo ft h e b r o a d c a s t al o to fb r o a d c a s tt u n i n gr e s e a r c ha n dm e t h o d sh a v eb e e np a i do n r e d u c i n gt h ea c c e s s i n gt i m e t h ep a p e ri l l u s t r a t e sa d v a n t a g e so fm u l t i d i s k s c h e d u l eb yc o m p a r i n gt h eu n i f o r ms c h e d u l ew i t hn o n u n i f o r mo fd a t ab r o a d c a s t i th a sa n a l y z e dt h ef o r m u l ao fm e a nm i n i m u ma c c e s st i m ei ni n v a r i a b l el e n g t h i t e m s ，a n dt h er e a l i z a t i o ne o n d i t i o n t h e nt h ep a p e ri n t r o d u c e sam u l t i d i s kb r o a d c a s ts c h e d u l i n ga l g o r i t h m b a s eo n z i p fr u l e t h o u g hp r o p o s e dt h ed i s t r i b u t e dp l a t es t r a t e g yb a s e do n i i z i p f - m d s ah a db e e nm e n t i o n e di nm a n yd o c u m e n t s ，p e o p l ed i d n td i s c u s s et h e v a l u eo fs k e wf a c t o rf u r t h e r a l s ot h ei n f l u e n c eo f ft h er e s u l to fd i s t r i b u t i n g p l a t ei sq u i t el a r g e t h e r e f o r et h ep r o p o s e dm e t h o do fd e t e r m i n a t i n gt h e t a i s q u i t es i g n i f i c a n t l a t e ri td i s c u s s e sh o wt od e t e r m i n a t et h ev a l u eo f a c c e s s p r o b a b i l i t ya n dd i s ks k e wf a c t o rb a s e dz i p f m d s a f i n a l l yt h ep a p e r s s i m u l a t e st h er e a l i z a t i o nb ycl a n g u a g ea n dc a l c u l a t e dt h ea v e r a g em i n m u m a c c e s st i m e t h e r ei sm o r ed e t a i l e d s t u d y a n da n a l y s i so ft h em o b i l ed a t a b a s e s y n c h r o n i z e dm e c h a n i s mf o ra 1 1k e yt e c h n i c a li s s u e s ，f o c u s i n go nt h ea n a l y s i s o fd a t ad i s t r i b u t i o n ，d a t ac o n s i s t e n c y ，r e c o v e r y ，a n ds oo n f i n a l l yi t p r o p o s e su s i n gm u t e xi nt h es y n c h r o n o u sp r o c e s s m u t e xi sad a t as t r u c t u r e ， w h i c hc a ng u a r a n t e et h a ti tc a nb eu s e da ta n y t i m eb yt h ei d e n t i c a lu s e rw h i c h m a yb et h ep r o c e s s ，t h r e a do ro t h e ra n ym a i nb o d y f i h a l l yt h ep a p e r i f l t r o d u c e sh o wt od e s i g np r o g r a mo fr e a d w r i t ec o n t r o la n dr e a d w r i t e s y n c h r o n i z a t i o nd e m o n s t r a t i o n ，f l o wc h a r t so ft w op r o g r a m s k e y w o r d s ：e m b e d d e dm o b i l ed a t a b a s e ，m u l t i d is k s c h e d u l e s k e wf a c t o r ， s y s c h r o n i z a t i o n ； 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在导 师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注 和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包含本人 或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论文 成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 一：尔凶l j 论文作者签字：才l j 复斤材、 2 一一年钿岁j 日 第一章绪论 第一章绪论 随着互联网的不断延伸与渗透，信息系统正逐渐走出传统的机房与桌面，使用 户能够随时随地获取相关信息，作出j 下确决策，并使企业事务一旦发生便可及时获 得反馈信息。这就是所谓的移动计算模式( c o m p u t i n ga n y w h e r e ) 。在移动计算模式 中，由移动终端( 如笔记本、手机、p d a 等) 构成的计算结点可以在自移动的过程中 保持网络连接，使得人们希望能在任何时候、任何地点访问任何数据的需求成为可 能。而原来基于有线网络和固定主机的分布式数据库不再适应这种应用环境，于是 一种更加灵活、复杂的数据库技术便应运而生，并迅速成为一个新的研究热点，这 就是移动数据库。 移动计算环境的与传统计算环境不同，有如下特点： 1 用户的移动性。用户可以在移动过程中进行各种操作。 2 网络带宽的不对称性。下行( 服务器到移动端) 带宽大于上行( 移动端到服务 器) 带宽。移动端甚至可以在不能发送信息的情况下仍可以接收到服务器发送给它的 信息。但即便如此，下行带宽一般也只有1 0 2 0 k b s ，无线局域网可能可以达到l o m b s 。 3 频繁断接。移动端可能因为用户主动关机或网络不稳定而间歇性的入网、断 接。 由于移动计算有以上的特点，因而在移动数据库的设计中，需要考虑诸多传统 计算环境下不需要考虑的问题，如对断接操作的支持、对跨区长事务的支持、对位 置相关查询的支持、对查询优化的特殊考虑以及对提高有限资源的利用率和对系统 效率的考虑等等为了有效地解决上述问题，诸如数据复制与缓存技术、移动事务 处理、数据广播技术、移动查询处理与查询优化、位置相关的数据处理及查询技术、 移动信息、发布技术、移动a g e n t 等技术在移动数据库中具有特别的意义它们都 是实现和完善移动数据库的关键性技术，还有待于人们的进一步探索移动数据库 系统的目的是有效的支持移动计算环境中的数据应用，能够使移动计算机或其他信 息设备在移动过程中，通过无线网络自由地交换数据，从而实现人们在任何时候、 任何地点访问所需数据的愿望m 广东i ：业大学i ：学硕+ 学位论文 1 1 本论文的研究背景、意义 1 1 1 研究背景 在移动计算环境中，数据广播是一种发布数据的重要途径，能有效支持对具有 公共访问兴趣的热点数据的访问。数据广播就是把各种数据按照一定的组织和顺序 定期的传送出去，在数据广播中涉及到两个方面：发送方和接收方，在本文中发送 方就是指服务器，接收方就是指移动计算机m c ，数据广播中的核心问题是服务器如 何对数据进行组织和调度，使得客户机的访问时间和调谐时白j 均达到最优值。在减 少访问时问方面，人们提出了许多广播调度的算法，也有大量相关的研究。 访问时日j ( a c c e s st i m e ) 是指从移动计算机提出数据请求开始到从广播中得到 结果为止所花费的时白j 1 2 1 。它决定了移动用户响应速度的快慢，是衡量移动数据库性 能的一个重要参数，因此缩短访问时问是数据广播的一个重要研究方向。 减小平均访问时间可以采用合理的广播调度实现。广播技术所采用的调度策略 有m ：平坦调度和非平坦调度，其中非平坦调度包括倾斜调度和多盘调度等。在概率 分布比较倾斜的情况下，多盘调度的性能是最优的。在文献 3 中胡虚怀提出基于 z i p f 规则的多盘调度算法，该方法比较适用于实际情况，可操作性强，在实际中实 现起来很方便。 很多文献都提出基于z i p f 分布的分盘策略，但对。的取值则没有进一步的探讨， 而目的取值对分盘结果的影响还是比较大的，因此本论文分析了基于z i p f 规则的多 盘调度中的倾斜因子口与最优访问时白j 0 的关系，然后提出确定口方法并求得0 ， 这些研究还是比较有理论意义的。 同步机制是保持数据库内容更新的最好方法。信息汇总是企业信息系统的核心 功能之一自己断开连接的移动数据库使用不多。一方面，必须汇总来自移动用户 的字段数据并将其集成到企业信息系统中另一方面，移动用户必须依赖后端来跟 踪数据库的最新更新。移动数据库供应商都提供自己数据库专用的同步解决方案i 呻 如何实现数据库同步复制，保持多个数据副本的一致性，则是移动数据库应用必须 解决的一个关键性问题：数据库的同步复制也是移动数据库相对于传统数据库的一 个重要特点 第一_ 章绪论 1 1 2 研究意义 1 1 2 1 移动数据库研究的学术价值和应用前景 移动数据库技术有着很高的学术起点并涉及到多个学科领域，在数据的存贮、 组织和管理等方面要借助和继承传统数据库技术，但又不等同l 。在数据库的传播方 面又要涉及无线通讯技术和计算机网络技术移动数据库对这三个方面的技术既有 继承，又提出了新的挑战。 移动数据库的研究具有极其重要的应用价值，覆盖了军民用的各个方面，因此， 移动数掘库已经成为当今数据库领域热门的新兴研究方向之一。移动数据库技术的 研究和实现，对未来移动计算环境中的许多重要应用，诸如移动商务系统、移动办 公系统，公共信息发稚系统等，都将具有重要的意义和巨大的实用价值，其应用前 景也是非常广阔的【s 6 1 1 1 2 2 研究倾斜因子的意义 z i p f 函数中口是倾斜因子，口越大分布越倾斜。访问概率的p 由实际中移动客 户对数据的请求情况决定，而磁盘的口并没有统一的取值，且口的不同取值对分盘结 果有比较大的影响，也势必影响平均访问时间，而访问时间决定了移动用户响应速 度的快慢，从而影响到数据库的性能。 1 1 2 3 互斥量在同步技术研究的意义 在目前的移动数据库系统中，由于受到诸如网络条件、无线通讯费用，移动设 备本身资源等多方面因素的限制，移动设备通常不能采用和网络保持持续连接的应 用方式，因此大部分时间移动设备是和固定网络断开连接的因而同步机制显得特 别重要互斥量是w i n d o w 系统的线程同步对象，是一个数据结构，能够保证它在任 何一个时刻只会被同一个使用者使用在同步中使用互斥量，可以简化同步过程， 减少系统开销，这在对数据处理要求不复杂的工业应用中是可行的 1 2 相关研究现状 广播技术所采用的调度策略有脚：平坦调度和非平坦调度其中非平坦调度包括 广东1 ：业大学丁学硕士学位论文 倾斜调度和多盘调度等，并且从实验数据可得如下结论f f ( 1 ) 在访问概率分布比较 均匀或均匀分布时，平坦调度的平均访问时间是最小的；( 2 ) 访问概率分布越倾斜， 非平坦调度( 倾斜，多盘) 的平均访问时间越小，当分布比较倾斜时优于平坦调度； ( 3 ) 多盘调度的平均访问时间总是优于倾斜调度。胡虚怀提出了基于z i p f 规则的多 盘调度算法，很多文献也都提出基于z i p f 分布的分盘策略，但是都没有对倾斜因子 作进一步的研究。 从目前国际、国内移动数据库的应用情况来看，移动数据库的应用正处于一个 “百花齐放、百家争鸣”的状态。 在国外，当移动计算环境初现端倪时，为了抢占商机和市场，世界上几家著名 的大型数据库软件公司相继推出了各自的移动计算解决方案和产品f 2 j 。移动数据库供 应商都提供自己数据库专用的同步解决方案，一般是提供同步引擎，使他们的移动 数据库可以和他们自己的或者第三方的后端数据库同步。o r a c l e 公司及时地推出了 支持移动计算机访问数据库的产品m o b i l ea g e n t m 。i n f o r m i x 公司的移动计算解决 方案也是基于一种三层的体系结构：移动计算机、应用a g e n t 服务器、数据库服务 器 9 1 。s y b a s e 公司推出了s y b a s es q la n y w h e r e 和s q lr e m o t e 两种产品，采用数据 复制技术来支持移动计算ij o 。m i c r o s o f t 的s h i l o h t j ，i n f o r m i x 旗下公司推出的 c l o u d s c a p e 系列，以及p o i n tb a s e , n 等产品。 在国内，在上个世纪九十年代对移动数据库就丌始了研究，并取得了许多成果。 中国人民大学成功研制出“小会灵”嵌入式移动数据库管理系统聊、华中科技大学开 发的m d m 2 n 、东南大学自主开发的s w i f t d b t ，并在很多行业进行应用。国防科技大 学周兴铭院士主持的研究组对这方面作了大量的工作【i ，l 周兴铭教授等提出了移动 数据库系统的三级复制体系结构。中国人民大学王珊教授，东北大学张霞教授等 在嵌入式移动数据库系统方面的工作也具有代表性。王珊和张霞教授等都分别研究 基于同步服务器的嵌入式移动数据库系统陋1 。 数据广播是解决移动数据库系统用户规模庞大及网络通讯非对称性等问题的一 个有效方法嗍服务器将大多数用户频繁访问的热点数据以一定的方式组织起来， 主动周期性地广播出去，这样可以以较小的代价解决大量用户访问的问题。m a r y l a n d 大学和m i t l 实验室的m f r a n k l i n 和s a c h a r y a 等人应用“广播磁盘”进行数据广 播研究1 1 4 ，还对广播协议和更新策略进行了研究m s t a t h a t o s 等人采用了。空中 c a c h e ”的方法李霖等对数据广播进行了较深入的研究，提出了启发式多盘调度算 法o s l 。 1 3 本论组织结构 本课题主要是研究基于z i p f 法则多盘调度算法中对访问时间有影响的倾斜因子 以及使用互斥量达到数掘同步的目的，为了保证文章的完整性和连续性，我们也对 一些概念作了介绍。 本课题主要研究内容有以下三个方面： 1 分析了定长数据下数据平均访问时间的最小值的公式和实现条件。 2 完成基于z i p f 规则多盘调度的访问概率的倾斜因子0 和磁盘倾斜因子口的确 定。根据0 的特性，提出两种求0 值的算法，并进行分析比较，所求得的p 与实际 值很接近。根据0 和乞的关系，提出两种求口算法，用w i n t c 在w i n d o w s 环境下编 写程序进行了模拟实验。 3 分析了移动数据库同步机制中数据分发问题，数据一致性问题，故障恢复问 题等。在实现移动数据库的同步技术中，提出了使用互斥量，并编写了读写控制程 序和读写同步演示程序。互斥量是一个数据结构，它能够保证它在任何一个时刻只 会被同一个使用者使用，这个使用者可以是进程、线程或者其他任何使用它的主体。 本论文章节的安排如下： 第一章从移动数据库系统应用背景出发，探讨了移动数据库系统研究的学术价 值和应用前景，国内外研究现状，为移动数据库技术的进一步研究打下基础。并介 绍本文的组织结构。 第二章介绍了了广播技术两个重要性能指标、分析了三种调度策略，通过比较 数据广播的平坦调度与非平坦调度，说明多盘调度的优越性。分析了定长数据下数 据平均访问时问的最小值的公式和实现条件 第三章讨论基于z i p f 法则多盘调度算法中对访问时间有很大影响的倾斜因子， 这里做了两项工作，一个是根据数据访问概率确定访问概率分布的倾斜情况即确定 ：另一个是确定使得平均访问时间最小的磁盘的倾斜因子p ，并用w i n - t c 编写程 序进行了模拟实验。 第四章对移动数据库系统中涉及数据同步的各个方面的关键技术问题作了较 为洋细的研究和分析，其中重点分析了数据分发问题，数据一致性问题，故障恢复 5 广东1 = 业大学工学硕士学位论文 问题等。 第五章提出了在数据同步中使用互斥量，并对互斥量进行了详细的介绍，还详 细介绍了读写控制程序和读写同步演示程序的设计，给出了这两个程序的流程图。 最后，我们对全文作了简单的总结，讨论了有待进一步研究的问题。 1 4 本章小结 本章是本文的总起部分，从移动数据库系统应用背景出发，论述本论文研究背 景和意义以及相关研究现状，并介绍本文的章节安排。 第二章倾斜网子确定的理论基础 第二章倾斜因子确定的理论基础 移动计算环境下的无线网络通讯不对称性特点，从服务器到移动客户机的下行 通信带宽往往要远大于从移动客户机到服务器的上行通信带宽，而且移动客户机接 收数据的丌销也远小于发送开销，即使是在客户机处于断接状态无法向服务器发送 消息的情况下，移动客户机也可以选择接收从服务器发送的下行信息。于是数据库 服务器可以利用这种网络的非对称性，把大多数移动客户机用户频繁访问的热点数 据以一定的方式组织起来以周期性的广播形式主动提供给移动用户 2 1 访问时间与调谐时间 广播技术研究的主要问题是，一方面在服务器端要研究如何组织广播调度，即 数据项在广播中的先后顺序，在一个广播周期中出现的次数等，以便使得移动端访 问所需数据花的时问最少。另一方面，在移动端，因其移动性要求，采用电池供电， 而电池的电量是有限的，要考虑节电问题移动计算机有两种工作模式，一个是工 作状态，一个是体眠状态。休眠状态能最大限度节约电能。为得到自己所需数据时， 移动计算机必须处于工作状态，侦听广播数据，看所需数据是否到达。所以广播技 术还要研究应该怎样使移动端侦听时间最小与以上两方面对应有两个性能指标， 即访问时间和调谐时间，这是衡量广播调度算法好坏的两个参数 2 0 1 。 访问时间a t ( a c c e s st i m e ) ，是指移动端向服务器发出数据请求开始，到从广 播队列中获得自己所需的数据所花费的时间。它决定了移动用户响应速度的快慢， 因此缩短访问时问是数据广播的一个重要研究方向 调谐时间t t ( t u n i n gt i m e ) ，移动端发出请求后，并不一定要一直保持侦听以 获得所需数据，可以采取某种方法使移动端知道所需数据什么时候到来，计算机发 出请求后就进入休眠状态，数据到来时才触发其进入工作状态接收所需数据所以 调谐时间的大小直接影响电能的消耗大小移动计算机处于活动模式所消耗的电量 远大于睡眠模式( d o z em o d e ) 如何节省电能是移动计算机研究的又一个重要问题， 因此减少调谐时间也是数据广播的一个重要研究方向 7 广东工业大学工学硕士学位论文 实际研究中，两者往往会有矛盾。为减小调谐时间要在广播队列中加入一些信 息数据，这无疑也会使访问时间也增大。减小平均访问时间采用合理的广播调度可 以实现，减小调谐时间可以在广播调度中引入索引技术来实现【2 1 1 。 2 2 广播调度 数据广播的一个主要研究课题是：如何组织数据广播信道中的数据，使之适合 于移动计算机访问。我们把这个问题称为数据广播的调度问题。 2 2 1 广播技术研究中的基本假设 为了便于理论分析需要根据实际情况对数据广播环境做一些限制以作为数据广 播技术研究中的基本假设。这些假设包括矧： 周期广播：假设数据广播采用周期性的广播形式即服务器生成一个广播调度序 列之后循环地广播相同的调度序列。 移动客户机对广播数据访问的独立性：服务器向移动客户机广播时所基于的通 信网络具有固定的广播能力，即被广播的数据对所有的移动客户机都是可同时访问 的，各个移动客户机之间互不干扰。并且移动客户机在访问数据广播时，每次访问一 个数据项，相邻两次访问的数据项之间也是相互独立的。 广播数据格式的一致性：广播数据的最小单位是数据项。且所有被广播的数据 项都是等长度的。在实际应用中，这些数据项可以是关系数据库中的记录，面向对象 数据库中的对象，或者是数据库中的一个存储页面。 数据项访问概率已知：即服务器知道移动客户机对广播数据项的访问概率分布 情况。可以假定移动客户机通过某种手段将自己的访问兴趣汇集到服务器，服务器可 以利用这些已知情况生成广播调度。 广播数据项的自我识别性：即移动客户机通过接收任意一个数据项可以知道它 是不是自己所要访问的数据项。这可以通过在每个广播数据项之前插入适当的头数 据来实现。 广播数据项以主键标识其唯一性：即每个广播数据项拥有一个主键。它能够唯一 地标识一个数据项。并且移动客户机总是根据主键来访闯数据广播中的数据项 i 第二章倾斜因子确定的理论基础 广播数据项地址的确定：定义一个数据项在数据广播中的地址为该数据项在广 播信道中到达的偏移时间。假定数据广播信道具有固定的网络带宽，且广播一个数据 项的时间为单位时间1 ，则当移动客户机从一个广播周期起始处开始接听时，后续每 个广播数据项的地址依次为l ，2 ，3 。 数据库的一致性假设：数据库的一致性以一个广播周期为单位，即：如果在一个 广播周期内发生了数据库的更新，则更新结果将在下一个广播周期内反映出来。 2 2 2 广播调度策略 广播技术所采用的调度策略有嘲：平坦调度和非平坦调度。其中非平坦调度包 括倾斜调度和多盘调度等。 服务器必须根据所有移动客户机的需要来组织广播程序，即数据广播的调度。 数据广播的调度可以看作一个带宽分配问题。给定所有客户机访问数据项的概率分 布，服务器试图确定每个数据项在广播带宽中所占的最佳比例，然后根据这个比例 产生广播程序。一种最简单的调度方法是将所有待广播的数据项简单地并在一起， 在每个广播周期里任意数据项都出现一次且只有一次，这种调度称为平坦调度。如 果在一个广播调度中，各个数据项出现的次数不一定为1 ，即所占的带宽比例不一 定相同，则将该调度称作非平坦调度。把数据项在广播中的一次出现称做该数据项 的一个实例，如果在一个广播调度中每个数据项前一个实例与下一个实例的时日j 隔 都是各自相等的，则称其为多盘调度，反之无论数据项在广播调度中有几个实例， 总是先广播完一个数据项的所有实例，再广播下一个数据项这种调度就是倾斜调度。 图2 - 1 是个三种调度的图示。 平坦调度倾斜调度多盘调度 图2 - 1 三种调度方式 f i g 2 lt h r e es c h e d u l i n gw a y s 数据广播可以看作是一个数据缓存，存放着一个无线单元里大家比较经常访闯 的数据，是供无线单元里所有移动用户所共享的移动用户首先在本地缓存查询所 9 广东工业大学工学硕士学位论文 需数据，如果没有再到广播缓存里查询。多盘调度可看作一系列不同转速的“磁盘”， 不同访问概率的数据存放在不同转速的“磁盘”。访问概率较高的数据被广播的次数 较高，就像存放在转速较高的“磁盘”里一样。 表2 - 1 和表2 - 2 是对图2 一l 三种调度在三种访问概率分布下的平均访问时间的 实验数据。 表2 - 1 各个数据的平均访问时间( 表示对4 的平均访问时间) t a b 2 - 1a v e r a g ea c c e s st i m eo fe a c hd a t a 调度 r 2f 3 平坦 3 23 23 2 倾斜 3 4 木3 2 + 1 4 木l 2 = 1 0 84 2 = 24 2 = 2 多盘 2 4 木2 2 + 2 4 术2 2 = l4 2 = 24 2 = 2 表2 2 对所有数据的平均访问时白j ( 只为对4 的访问概率) t a b 2 - 2a v e r a g ea c c e s st i m eo fa lld a t a 访问概率分布 平均访问时，= 片t i + 昱，2 + b + 如 只 最只 平坦 倾斜多盘 3 3 3 3 3 3 3 3 3 1 51 7 4 91 6 7 5 0 3 0 2 0 1 51 6 2 51 5 7 0 2 0 10 9 61 51 4 7 51 3 从表2 - 2 可以得出如下结论： ( 1 ) 在访问概率分布比较均匀或均匀分布时，平坦调度的平均访问时间是最小 的； ( 2 ) 访问概率分布越倾斜，非平坦调度( 倾斜，多盘) 的平均访问时间越小， 当分布比较倾斜时优于平坦调度； ( 3 ) 多盘调度的平均访问时间总是优于倾斜调度 由于实际中对数据库数据的访问概率分布一般都是比较倾斜的，所以广播调度 第二章倾斜因子确定的理论基础 算法的研究都是基于多盘调度的，即总是设法使得各个数据在广播中的实例是等间 距的 2 3 数据平均访问时间的理论最优值 由于下章倾斜因子的确定方法是假设在定长数据情况下，因此本节将说明定长 数据项最小平均访问时自j 理论值及其实现条件。定长数据项是假定广播中的所有数 据项占的带宽比例都是相同的，即数据是等长的。反之则是不定长数据。在几乎所 有有关移动数据库广播技术研究的文献都有对广播调度访问时间的分析及理论最优 值的推导。文献 2 4 只对定长数据理想情况下的平均访问时间理论最优值进行了推 导，而且最后的表达式也有错。文献 2 5 则只对变长数据的理想情况进行了分析。 有的文献指出了定长数据实际情况下最优值的取得条件但没给出理论最优值的表达 式。因此本小节将对定长数据情况下的最优值进行推导及说明实现条件。 这里所说的理想情况是指在广播中每个数据项的广播次数与其被访问的概率有 关，被访问的概率越高，广播的次数就越高，这样几乎每个数据项都有唯一的广播 次数，理论最优值的研究就是要确定其广播次数与访问概率的关系及理论最优值的 表达式。而实际情况下如果按每个数据项的访问概率确定其广播次数，在数据项很 多的情况下无疑工作量将是很大的，而且每个数据项几乎都有一个独立的广播次数， 即在广播中各自都有不同的实例个数，这样子有两个不好，一方面在产生广播调度 时将很复杂，开销很大；另一方面，产生的广播调度的长度将长得不可思议。所以 理想情况在实际中是不可操作的。因此操作中往往是先确定k 不同转速的“磁盘”， 再将数据分成k 部分放入“磁盘”，再求每个盘的平均访问概率。根据平均访问概率 来确定该盘的转速，即广播次数。 2 3 1 术语和符号规定 为讨论方便，我们约定如下术语和符号 定长数据理想情况嘲： l ，广播数据：由m 个数据项组成，即4 ，吐，以丸；所有数据项的长度相同： 2 、对任意一个数据项访问请求，它访问的概率为p ，所有数据项按访问概率递 广东t 业大学1 ：学硕十学位论文 减的次序排列，即日 最 己； 3 、设在广播信道中发送一个数据项的时间为单位时间，即广播一个数据项的广 播带宽为l ； 4 、实例：一个数据项在广播周期中的一次出现称为它的一个实例。在一个广播 周期中，可以包含一个数据项的多个实例； 5 、调度( s c h e d u l e ) ：在广播周期中所有数据项实例的排列，称为一个广播调 度； 6 、数据项的频率：在一个广播周期中，数据项z 的实例个数称为z 的频率，记 为，； 7 、广播周期假设一个广播周期由n 个单位时问( 数据项) 组成，即广播周期为 r ；广播周期 r 可以表示为： = ， ( 2 1 ) i f f i l 8 、间隔：一个数据项两个实例之间的间隔是指从开始广播第一个实例到丌始广 播第二个实例所花费的时间，瓯表示数据项4 的第j 个实例与下一个实例问的间隔。 注意，在z 的第f 个实例之后，下一个实例是下一广播周期中的第一个实例： 9 、单个数据项的平均访问时间：即淝在请求数据项d 时的平均等待时白j ，记 为。假设该请求的到来按均匀分布落在广播周期中的任意时刻，即落在瓯中的概 率为瓯，此时该请求得到的平均等待时间为瓯2 ，因此： ， = & 2 + 岛 ( 2 2 ) j - i 多盘调度情况下，每个数据项的实例是等自j 距的，瓯是一个常数墨，则： 最= n i x ( 2 3 ) 于是公式( 2 2 ) 式简化为： t 。= s 。2 l o 、综合平均访问时间( 数据广播的平均访问时间) ： 平均访问时问，记为t ； t - - p s 2 ，l i 实际情况下，作如下修改和补充： ( 2 4 ) 即客户访问任意数据项的 ( 2 5 ) 第二章倾斜因子确定的理论基础 1 、假设有k 个盘，即垦，垦，马皿 2 、每个盘里的数据广播频率都相同，置盘的广播频率为z 3 、b i 盘包含的数据个数为c f ，墨盘的平均访问概率为q ： q = ；1 。p ， ( 2 6 ) o ，e 岛 2 3 2 定长数据情况下的理论分析 2 3 2 1定长数据理想情况下的理论分析 由式( 2 5 ) 和( 2 3 ) 可得： m ，= 竽= 等 j - i，l i ( 2 7 ) 令舅= , n ，又= z 所以g ，= 1 ，即蜀中只存在肼一1 个自由变量，所 t - i，l 以可把式( 2 7 ) 写成： ，= 砉 首先将上式对蜀进行求导，并令其为0 ，g z g ，当作常数： 。：毒：掣唁+ 毒 吼寺2 南 髓：k 2 。2 z 南 综合上两式得：詈= 岳，同理詈= 号 将g = z 代入上式得：丢= 号 广东t 业大学r 学硕七学位论文 概率的平方根，令，= 口耳并代入式( 2 1 ) 求得口： 弘索引。券属厉 将式( 2 8 ) 代入( 2 7 ) 得平均访问时间的理论最优值： o ： ( 兰打) ： ( 2 8 ) ( 2 9 ) 其实现条件是： ， ( 1 ) 在广播调度中每个数据项的实例是等l 日j 距的； ( 2 ) 任意数据项的广播频率应- q 其访问概率的平方根成正比。 2 3 2 2 定长数据实际情况下的理论分析 在实际情况下，有七个盘蜀，岛，马毋，置盘包含c 个数据项且广播频率 为，其平均访问时为： ，= 妻筹= 雏等 = 妻等 亿 实际情况下广播周期变为：= e + z ( 2 i i ) 令g i = e + f i n ，从式( 2 1 1 ) 可知g ，= l ，即g ，中只存在t 1 个自由变量， 所以可把加1 0 ) 虢，= 妻譬 仿照上面的求导过程可证明当满足下面条件时t 取得最小值： 将蜀= g + z 代入上式得：五h 一- 善 仿照上面证明求得比例系数，并把，代入式( 2 1 0 ) 求得时问最优值： 。= 将厄h 妻再 定长数据实际情况下取得理论最优值的条件是： ( 1 ) 在广播调度中每个数据项的实例是等间距的； 1 4 ( 2 1 2 ) 兰三耋堡箜垦主塑塞箜墨至董翌 ( 2 ) 任意盘垦的广播频率z 正比于该盘的平均访问概率的平方根虿 2 4 多盘调度算法 多盘调度的思想最先由美国b r o w n 大学的a c h a r y a 等人提出1 2 7 划。多盘调度即 广播队列每个数据项的实例都是等间距的，那怎么产生这样的一个广播调度呢? 多 调度的产生过程一般包含以下步骤： ( 1 ) 确定k 个磁盘旦，垦，马毋； ( 2 ) 将所有广播数据按一定方法分入k 个盘中，每个盘包含c j 个数据； ( 3 ) 根据每个盘的平均访问概率q 确定广播频率，旦盘的广播频率为z ，z 根 据上一节理论分析得出的广播平均访问时间取得理论最优值的条件来确定，例如定 长数据实际情况下z * q ，让五= l ( 第k 个盘是最后一个盘，平均访问概率最小， 广播频率最4 , - - 般取为1 ) ，求得比例系数口= 1 q ，所以，= q q 。 ( 4 ) 求所有z 的最小公倍数l c m ，将每个盘分为p 块，口= l c m f , ，每 块记为见( j = l ，2 ) ，如果数据数目不能整分则取整，取整的方法是数值舍去小 数再加l ，例如若求得口的值为1 5 最后应取为2 。多盘调度由如下算法产生： f o r ( 芦l ：i = l c m ；i + + ) f o r ( 产l ；j _ | k ；j + + ) 广播数据块q 肼岛) ( 是取模运算) ； 即一个广播周期包括l c m 个子周期，第一个子周期分别取出每个盘的第一块数 据块组成、第二个子周期分别取出每个盘的第二块数据块组成，以此类推。当一个 盘取完最后一块数据块时，下一个子周期又从第一块开始。 图2 - 2 说明多盘调度的产生过程，假设有8 个数据项珥西，已经根据一定方 法分好盘，盘的数量为3 ，每个盘的广播频率分别为：4 、2 、1 则l c m = 4 ；各个 盘的分块数为：l 、2 、4 盘厉三个数据项分成两块，前两个数据项分为一块，第 三个数据项单独成一块，空格只是示意，实际中不应该被当做一个空数据项进行广 播，去掉空格后，数据项4 的实例并不是等问距的，所以实际上广播的多盘调度并 不是严格的多盘调度。 广东工业大