嵌入式数据流检索系统的研究与实现

2013-12-23杜红

机械工程与自动化 2013年3期

杜红

（山西职业技术学院，山西太原 030006）

0 引言

目前，学术界将具有“实时、连续、潜在无界、有序（隐含的通过到达时间或者明确的时间戳）”这些特征的数据项的序列称为“数据流（Data Stream）”，数据流同时具备了时效性、实时性、无限性和瞬间性等特点。而对于嵌入式系统，IEEE（国际电气和电子工程师协会）给出的定义为：嵌入式系统是“用于控制、监视或者辅助操作机器和设备的装置”。嵌入式系统具有“嵌入”、“专业性”、“计算机”的基本要素和特征。

本文的研究目标是：设计一个可以应用于嵌入式系统的数据流查询系统架构。这个系统被部署在无线网络环境中，系统中所需要处理的数据流对象主要由传感器数据流构成，而且这些数据流都是数值型的数据。该系统在实现对用户感兴趣的敏感数据实时提取的同时，实现对数据的过滤与筛选，以有效减少在网络中传输的数据流量，使用户终端能够得到更加优质的数据。

1 系统硬件平台

嵌入式系统可以使用的硬件资源非常少，通常内存在几kB到几十MB 范围内；同时对实时性的要求很高，该特点与数据流的实时性特点是完全一致的。这一点对该系统设计工作提出了很高的要求，既要尽最大可能地减少内存的资源占用，又要提高效率、缩短处理时间。

本系统的嵌入式硬件平台为基于S3C44B0X 的实验板，这款实验板的CPU 为Samsung S3C44B0X（ARM7 内核，主频为66 MHz），8MB SDRAM ，2MB FLASH。嵌入式软件开发环境为UCLinux（2.4版本的内核），软件开发工具为GNU，交叉编译工具采用了Arm－elf－tools。

2 系统设计

2.1 存储模块设计

面对海量的数据，将这些数据全部保存下来是无法实现的，并且运行在嵌入式设备上的系统所能够调用的内存资源也非常有限。但为了能对数据流进行处理，依然需要实现保存部分数据功能。目前在数据流处理中存储数据用得最多的是滑动窗口（sliding window）模型。基于容量的滑动窗口模型如图1所示，其滑动窗口的大小是固定的。当一个数据到来时如果滑动窗口没有满，则将它添加到滑动窗口中；如果此时滑动窗口已满，则将滑动窗口中最旧的数据删除后再插入新数据，滑动窗口用队列实现。

图1 基于容量的滑动窗口模型

2.2 聚合函数设计

聚合函数包括 SUM、AVG、MAX、MIN、COUNT。对于聚合函数，本文采用增量式计算方法与普通的遍历式计算方法相结合的方式来实现。增量式计算方法为：每当数据进入滑动窗口时做一次计算，每次计算值都依赖于前一个值，只需要将要进入和退出滑动窗口的数据和保存值做计算就可以得出结果，查询结果始终保存在内存中，需要使用时只需要读出这个结果。对于一些增量式计算方法不适用的特殊情况，则通过结合遍历式计算方法来实现。

2.3 查询指令的解析

查询指令的结构和语法类似于SQL 语句，如：Select＊from sl where tmp ＞10。解析时的主要工作由以下4个步骤组成：解析数据流对象、解析输出列和聚合函数、解析查询条件、对解析结果排序。当用户输入的查询语句不符合正确的语法要求时，需要给出错误提示信息。在这个方面，系统被设计为每当遇到一个解析错误就返回一个错误信息提示用户。系统在其解析式中会得到的信息主要包括数据流对象信息、输出信息、聚合函数信息、查询条件信息。其中查询条件包括产生条件判断的列、操作符、条件比较数、多重表达式逻辑关系信息。系统针对所采集到的数据，专门设计了特殊数据结构来保存这些解析结果。

3 查询引擎设计

查询引擎的工作就是根据解析出的结果来进行查询，以得到最终的处理结果。下面对该体系中的两个主要模块的设计过程进行介绍。

3.1 单数据流选择和投影模块

单数据流选择和投影操作，就是通过遍历当前滑动窗口中存储的数据来检索出满足条件的数据，之后再进行一次投影操作，并将数据保存。对单数据流做选择和投影操作时的大致算法如下：

（1）解析出Ifmask（条件掩码）和Getmask（投影完成后的输出掩码），并在解析过程中得出输出列的数量。在解析的过程中需要注意的是：如果用于等值连接的列未出现在最后的输出列中，为了等值连接运算的完成仍需要对这一列进行保存，这时，则需要修改Getmask，使得这一列能够得到正常的输出。

（2）选择操作，即从滑动窗口中取出一个单元的数据流，根据逻辑表达式条件，来判断这个数据是否满足提取条件。

（3）投影操作，即将满足条件的查询结果保存到存储查询结果的Query＿res中，并在保存结果的同时对关键列进行投影操作。

（4）判断当前指针是否已经达到滑动窗口的末尾，若是则算法结束，否则返回到步骤（2）继续。

3.2 多数据流连接模块

多数据流连接，就是在对单数据流做了选择和投影后将具有相同属性的列中值相同的数据单元提取出来。连接操作通过链表实现，每当有数据流参与连接，就将连接的结果加入到链表中。对多数据流做等值连接的大致算法如下：

（1）设置两个指针Dtqrpt和Srcqrpt，Dtqrpt指向保存最后结果的Query＿res，Srcqrpt指向保存新连入数据流选择和投影后结果的Query＿res。设置指针Dstqrdpt用来指向查询结果中的数据流表（数据流表以二级链表的结构来实现），即Dstqrdpt＝Dtqrpt→Srcqrpt。

（2）找到Dstqrdpt指向Query＿res中的查询结果信息头部链表的尾部，将Srcqrpt指向的Query＿res中所保存的查询结果信息的头部插入到所找到节点的尾部。

（3）找到Dstqrdpt中的数据单元链表（二级链表Sdpt）尾部节点后，将尾部数据单元中用于等值连接的数据列与Srcqrpt指针所指向的数据链表中的对应列做比较，若相等则将这部分数据单元添加到Srcqrpt所指数据的尾部；反之则将Dstqrdpt 做后移操作（Dstqrdpt＝Dstqrdpt→next），最后删除Dstqrdpt所指向的节点。

（4）若Dstqrdpt！＝NULL，则继续执行步骤（3）；否则，算法结束。

3.3 连续查询机制的实现

连续查询是数据流处理工作的主要特征，也是该系统不可缺少的重要组成部分。连续查询用两个参数来控制：时间间隔和重复的次数。时间间隔参数用来控制连续查询的间隔，即在间隔一定的次数之后执行一次查询；重复的次数参数用来指定重复查询的执行次数。连续查询采用定时器实现，即每到设置的定时时间触发一次查询。本文中采用了CCS算法来处理滑动窗口中数据的连续查询操作，CCS算法主要针对滑动窗口以元组为单位进行滑动的情况，这种细粒度的算法非常适合大量连续数据流。在有新的数据元组到达需要查询时，CCS及时更新滑动窗口和数据缓存队列，该处理算法的测试结果如图2所示。