移动环境中自适应的XML广播索引

第13期 ol2009年7月

Jul

移动环境中自适应的XML广播索引 杨进才，龚 松，许沛华，胡金柱 (华中师范大学计算机科学系，武汉 430079) 摘 要：针对如何减少移动计算环境中XML数据广播的调谐时间和访问时间的问题，提出一种基于自适应索引的XML广播调度算法XAISA。它能根据系统负荷动态调整数据块的度，从而达到性能最优化。性能分析和实验比较表明，该算法能以极小的平均访问时间的代价大大减少平均调谐时间及接收XML广播数据的时间。 关键词：移动计算；XML传输；广播调度；自适应索引

Adaptive XML Broadcast Index in Mobile Environment

YANG Jin-cai, GONG Song, XU Pei-hua, HU Jin-zhu (Department of Computer Science, Huazhong Normal University, Wuhan 430079) 【Abstract】This paper focuses on how to minimize the access time and tuning time of the XML data broadcast in mobile computing environments, and proposes an XML data broadcast scheduling algorithm named XAISA(XML broadcast Scheduling Algorithm based on Adaptive Index) based on adaptive index. Its performance can be optimized by adjusting the degree of data blocks dynamically according to system workload, and it can significantly shorten the average tuning time at the cost of slight increment in average access time and the time of receiving XML broadcasting data, which is indicated by performance analysis and experimental results. 【Key words】mobile computing; XML transmission; broadcast scheduling; adaptive index

计 算 机 工 程 Computer Engineering第35卷

V.35 No.13 y 2009

术与数据库· 文章编号：1000—3428(2009)13—0046—03文献标识码：A

中图分类号：N945.12

·软件技

1 概述 在移动环境中，数据广播是一种有效的数据访问方式，能够以很小的代价支持大量移动客户机同时并发访问数据。衡量数据广播性能的主要参数有2个[1]，即访问时间(Access Time, AT)和调谐时间(Tuning Time, TT)。 XML是一种非常有效的半结构数据表示格式，并且是一种高效的传输及交换格式。XML的相关研究已有很多，比如

XML过滤、XML查询和索引技术。但如何在移动计算环境中高效地传输XML文档仍处于初步研究阶段。在大多数情况下，移动用户的查询结果只是XML文档很小一部分，如果广播整个XML文档，将会导致广播周期过长，从而延长访问时间，造成数据访问效率的急骤下降。文献[2]提出一种裁剪算法，用于对传输的XML文档进行预处理，可获得近50%的性能提升。另外，采用XML索引技术可以减小调谐时间。数据索引算法以较小的访问时间增量为代价来减小调谐时间。文献[3]提出了一种用于按需广播系统的索引方法。该方法的广播报文由一系列数据块组成，其中，每个数据块由一个索引片段和一个数据片段构成。数据块包含数据项的数目称为该数据块的度。每个数据片段由一些数据项组成，并且每个索引片段包含对应数据片段中数据项的索引项。 文献[3]通过引入索引预测机制，在广播报文中插入索引项，从而以很小的平均访问时间代价大大减少平均调谐时间，但该算法存在以下缺点[4]： (1)没有考虑启动和关闭WNI (Wireless Network Interface)的时间。

(2)不能适应系统负荷的动态变化。此外，在该索引结构中，数据块的度是固定不变的。本文提出一种新的XML自

适应索引，其中考虑了启动和关闭WNI时间，并通过

XAISA(XML broadcast Scheduling Algorithm based on Adaptive Index)算法调整XML广播数据块的度，以动态适应

系统负荷变化。 2 XML数据广播 定义XML数据广播问题如下：对于给定的XML数据集

D和查询集，服务器在无线通信上广播满足移动设备查询请求的XML文档，移动设备侦听广播通道并获取所需的数据。其中，XML数据集

Q

D以多个XML文档的形式存在；查询集为XPath查询集[5-6]。为了获得更好的性能，对待广播的XML文档进行多余分支数据节点的删除，并采用XAISA算法对待广播的XML数据生成相应的索引结构。因此，XML数据广播大致可以分为2个部分：XML数据的预处理和采用XAISA算法的XML数据广播调度。

Q

2.1 XML预处理 对XML数据的预处理采用文献[2]的裁剪算法。根据原

始的XML文档集D和用户查询集，输出经过裁剪后的XML文档结果集QPD。首先，初始化结果集，令PD=∅；根据构造一个NFA，然后对QD中每个元素的所有元素节点进行检查，若的元素节点与匹配成功，则标记对应的XML树状结构从根开始到该元素节点所经过路径上的所有节点及的子孙节点为“”。根据标记为“”的节点，去除多余的节点，这样结果集

ddnQd

nnRR

PD就产生了，其中包含

基金项目：湖北省科技攻关计划基金资助项目(2007AA101C49) 作者简介：杨进才(1967－)，男，教授，主研方向：移动数据库； 龚 松、许沛华，硕士研究生；胡金柱，教授、博士生导师 收稿日期：2008-11-05 E-mail：gongsong2024@126.com

—46— 了移动设备所需的XML数据。 2.2 相关定义和说明 为了方便XAISA算法的讨论，对本文中涉及的符号和名词作如下指定： (1)代价模型

OnT： WNI从激活状态转入休眠模式的时间；： WNI从休眠模式转入激活状态的时间。假定移动设备在内的能耗与成比例，即；相应地，内能耗为，其中，OffT

OnT

OnT1OnTβ×OffT2OffTβ×

1β,2β为常数。表示未考虑WNI启停时间的平均调谐时间。表示一次查询的有效调谐时间，=++，其中，,分别代表WNI的启停次数。为了便于讨论，下文令=、

TuningTTuningEffT

TuningEffT

TuningT

11OnnTβ××22OffnTβ××1n2n

TuningEffT

TuningT

1β=2β=1。 (2)客户端访问机制

对移动设备的访问请求进行分类后，客户端依照客户端访问机制获取所需的数据。每个数据块对应一个XML文档，

其中的数据项代表该XML文档中的部分节点。客户端访问机制采用文献[7]的方法，将访问分为3个阶段： (1)初始探测索引。提交数据请求后，移动设备监听广播信道直到索引片段到来。

(2)索引查找。移动设备获取索引片段后，判断后继数据片段是否包含所需数据项。若无，则转入休眠模式，直到后继索引片段到来时激活；否则，转入数据获取阶段。 (3)数据提取。若所需数据在当前广播的数据片段中，移动设备则估算从当前广播的索引片段直到获取所需数据的时间并进入休眠状态。当探测到所需数据时，重新转入活动状态并获取所需的XML数据。

在图1所示的数据请求的分类中，指移动设备监听广播信道的时刻；指移动设备获取到所需数据的时刻。根据上述的3个阶段，监听区间(~)内的数据块可分

3类：

StarttEndt

StarttEndt

(1)探测块：所依赖的数据块。图1中的StarttiB是探测块。 (2)查找块：移动设备只获取索引片段，而忽略数据片段的数据块。一次数据请求中，有0个或多个查找块。

(3)提取块：所依赖的数据块，即包含所需数据项的

数据块。由于查找块可能有0个或多个，因此探测块和提取块可能是相同或不同数据块。

Endt

图1 数据块的分类 2.3 XAISA算法 XAISA算法根据系统的负荷变化，采用自适应索引技术对数据块的度进行动态调整。该算法分为2个阶段：统计阶段和调整阶段，并在这2个阶段间交替。在统计阶段对所有

已完成的数据请求进行监测，获得相关的统计信息，作为调整阶段调整度的依据。 (1)数据请求类型 数据请求的2个分类依据为：

1)探测块和提取块是否相同； 2)和之间的关系。 StarttEndt

根据探测块和提取块的关系可以分为2类：I类：探测块和提取块是同一数据块；II类：探测块和提取块为不同的

数据块。 考虑和之间的关系，根据客户端访问机制，I类请求的必定位于索引片段中，否则，和不在同一数据块中，与类I的定义矛盾。II类请求需要根据的定位

进一步细分：II.I类：在索引片段中；II.II类：在数据片段中。

StarttEndtStarttStarttEndt

Startt

StarttStartt

(2)统计阶段 为了便于讨论，将所需XML数据已广播的请求称为已服务请求。在统计阶段，系统统计当前所有已服务请求的信息。Stat_I和Stat_II分别用于存储I类、II类请求的统计信

息，数据结构如下：

Struct Stat_I {ReqNo;// I类已服务请求个数

AggAT;// I类已服务请求的总访问时间 AggTT;// I类已服务请求的总调谐时间} Struct Stat_II {ReqNo;//II类已服务请求个数 AggATP/ AggTTP;// II类已服务请求的探测块的总访问时间或//总调谐时间 AggATS/ AggTTS;// II类已服务请求的查找块的总访问时间或//总调谐时间 AggATR/ AggTTR;// II类已服务请求的提取块的总访问时间或

//总调谐时间} 还有另一种结构，除了ReqNo，其他域以Avg为前缀，

表示相应值的平均值。访问请求可归为以下3个队列：

1)请求队列，所有提交的访问请求； 2)等待队列，已提交但未响应数据提取的请求； 3)就绪队列，提取到相应数据但等待广播的请求。定义一个Request结构，所有请求队列、等待队列、就绪队列中