传感器网络中的多查询优化技术研究

郑州航空工业管理学院 程文静

传感器网络中的多查询优化技术研究

郑州航空工业管理学院 程文静

对查询技术的研究是传感器网络中的一个重要方面，而查询优化又是提高查询效率的重要途径之一。当前对查询优化的研究主要集中在单个查询应用上，对多查询优化的研究并不太多。本文介绍并对比了三种不同的多查询优化技术CACQ、TTMQO，它们各有特点，并适用于不同的应用情境。

传感器网络；多查询；优化

1.研究背景

对传感器网络中的数据处理技术来说，TinyDB和Cougar是最有代表性的两个系统。然而，它们都只能对单个查询提供优化处理，而针对多个查询同时发出请求的状况时，它们的处理方法是先在基站对每个查询进行优化处理，然后在查询进入网络的同时对相同的传感器集进行一些批处理。此方法的弊端在于，这两个系统无法通过共享不同的查询产生的结果来分摊数据获取、计算和通信的耗能。另外，运行多查询会导致带宽负荷，严重的话可能出现通信冲突的话而导致数据丢失。因此，对能量受限的传感器网络来说，在查询处理中引入多查询优化技术是很必要的。然而，当前这方面的研究还比较少。在本文中，将讨论并比较三种典型的多查询优化算法。

2.两种多查询优化方法

2.1 持续的自适应连续查询（C A C Q）

CACQ[1]是一个用于本地查询处理器的方案，适用于环境监测的传感器网络中。它改进了传统的连续查询设计，在为查询工作量的变化提供自适应特性时执行流处理方式。当一个连续查询进入网络时，首先在基站由全局查询操作符对其进行分解，成为一系列子查询。然后这些子查询分别被在网内广播，到达相关的传感器。在此，流数据的扫描、选择和连接等操作依次被执行，产生的部分结果返回全局查询处理器。因为连续查询方案的基本思想是使单个传感器上多个相似的查询共享本地的查询操作符，所以查询处理计划中的常见部分将只被执行一次。

CACQ的自适应特性体现在当有新查询产生时，传感器会改变现有查询的数据传输率，另外查询操作符的执行顺序也可能改变。自适应是通过整合Eddy操作符实现的，Eddy对正在运行的查询计划中的查询操作符进行重新排序，从而实现持续的自适应的查询处理过程[2]。对于不含连接操作的多查询，使用单个Eddy来路由所有当前运行的查询包含的元组。根据关系表中对应的属性，多个选择谓词被分成若干组，然后对每一个属性应用分组过滤器得到经过过滤的元组。考虑如下的三个查询，它们基于Eddy的查询结构如图1所示：

图1 基于E d d y的持续查询结构[1]

三个查询Q1，Q2和Q3被提交到源节点S。它们一共包括了在属性a和b上的六个选择谓词s1到s6。Eddy模型对每一个谓词运用一个过滤操作，即产生了两个组{s1,s2,s3}和{s4,s5,s6}，当有一个带有属性a和b的元组s到达时，Eddy先把a传给过滤组{s1,s2,s3}，把b传给过滤组{s4,s5,s6}。在两个组中分别执行相应的选择操作，产生的中间结果会被传递给全局查询处理器。由于在这种框架中，每个元组只被查看一次，因此，多查询的执行效率显著提高。

当需要向系统中加入新的查询Q4时，如果Q4是针对一个新的数据源的查询，Eddy就会实例化一个新的查看器和一组针对Q4的新的过滤器。如果Q4查询的数据仍然是来源于S，那么只需要在已分组的过滤器中的s.a和s.b上加上基于属性a和b的新的选择谓词，或者为其他属性实例化一个新的分组过滤器。

2.2 对聚集查询的多查询优化

Trigoni 等人提出的多查询优化技术是第一个正式考虑传感器网络中的多查询优化的工作[3]。它主要针对空间聚集查询，发展了结果共享和结果编码两项技术。结果共享用于多聚集查询的处理，结果编码用于减少查询更新过程中产生的需要计算的数据量。这两项技术都能显著地降低求和、计数和求平均值这三类查询的通信消耗。另外，还可以使用一种线性减少算法来降低不规律的数据更新的规模，使用一种接近最优算法来最大程度地减少计算量。

整体来说，为了优化聚集查询，具有相同聚集操作符的查询被分在一组，通过共享查询处理过程来降低通信消耗。对长时间运行的查询来说，每一个时间段被分为两个步骤：查询预处理和结果传输。在此方法中，查询传播的成本忽略不计，因为这和持续查询过程中用来传输结果的能耗相比是微不足道的。

基于以上思想，此项多查询优化技术针对的是具有相同聚集操作符的多查询。这些查询将一个长方形区域中的传感器读数进行聚集处理，因此用它们在空间中所处的位置来自我标识。每一查询被表示成一个含有k个属性的矢量，其中k是网络中的传感器节点数量。为了使用这样的表示，用户需要了解网络拓扑图。地理位置上靠近又涉及相似查询的传感器被划进同一类，组成一部分路由树的分支，由此查询结果的消息数量可以被更好的压缩，从而有效地降低能耗。

2.3 两层多查询优化

Xiang等人在[4]中提出了一个两层多查询优化方案TTMQO。它支持数据聚集和数据获取两类查询。TTMQO的第一层称为基站优化，它使用基于代价的方法，通过发掘源查询中的相似性和减少冗余进行查询重写，优化后的查询被投入网络；第二层称为网内优化，利用无线信道的传播特性传输结果，并通过恰当地对数据获取和通信安排时间进度来接受相关查询的共性分享。

对于基站优化，运用了一个代价模型来评估查询重写的效益，该模型把传输成本作为性能指标。在这个方案里，无线传输成本被认为是查询结果传输的成本，因为它在持续查询的成本中占据主体地位。因此，查询成本可通过以下公式计算：

对于网内查询优化，重点在于对多个查询在时间或空间指标上的结果共享。首先介绍基于时间的结果共享方法。对于两个查询q1和q2，它们唯一的区别在于取样周期不同，它们的优化步骤如下：如果q1的取样周期长度能被q2的整除（4096ms和2048ms），那么q1和q2可以被整合成一个查询，方式如前文所述，其中结果的共同部分能被共享。如果q1的取样周期长度不能被q2的整除（如6144ms和4096ms），那么就无法构造有效的合成查询。然而，q1请求的数据中有一半也是q2请求的。

因此研究人员提出了一项对数据获取和传输安排时间表的技术，以此提高两个查询的效率。每当一个新的查询进入网络，节点的时钟被设置为所有查询的时间周期的最大公约数。另外，一个新查询的开始时间被设置为可被时间周期整除的数。虽然重置开始时间可能导致第一个周期的些许延迟，但是对于长时间持续查询来说，没有太大影响。这样做的好处在于，能够大量地节省能量和带宽，因为具有相同周期的查询会在每一周期中的同一时间点开始取样。

除了基于时间的查询优化，还有基于空间的查询优化方法，其基本思想是使多个查询共享传输。对于聚集查询来说，一个节点会优先选择一个和它属于同一查询并具有许多满足条件的数据的邻居节点作为它的传输路径上的父节点。由此，一条结果消息就能由多个不同查询产生的相同的部分聚集结果产生。对于采集查询来说，一个传感节点能够产生一条包含不同查询所请求的所有属性的消息。由于传递多个小消息比传递一个大消息的成本要高，因此消息共享是一个减少网络通信量的有效办法。

实验结果表明在多查询优化中，两层优化明显比单一运用基站优化或者网内优化有效。在两层结构中，传输时间减少了18%，说明网络带宽和能量都被大量地减少了。

结论

虽然当前对多查询优化的研究并不多，但是这将是未来一个新的研究方向。本文介绍了三种多查询优化技术，CACQ方法适用于数据流形式的查询，在每个数据流上应用一个本地查询处理器；TTMQO结构是一个两层查询优化器，既适用于获取型查询，也适用于聚合查询；最后一种多查询优化技术运用了一个线性缩减算法有效地觉少了结果消息的数量，适用于基于区域的聚合查询。

[1]S．Madden．Continuously adaptive continuous queries over streams． In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp． 49-60, June 2012．

[2]R．Avnur．Eddies：Continuously adaptive query processing．In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp． 261-272, May 2010．

[3]N．Trigoni．Multi-query optimization for sensor networks． In Proceedings of DCOSS,vol． 3560 of Lecture Notes in Computer Science, pp．307-321, 2015．

[4]S．Xiang．Two-tier multiple query optimization for sensor networks．In Proceedings of IEEE International Conference on Distributed Computing Systems, pp．39-47,June 2012．

程文静（1983-），女，河南新乡人，硕士，郑州航空工业管理学院讲师，研究方向：数据知识工程。