基于列数据库的无线传感器网络并行连接算法研究

© 2013由Elsevier B.V.发布。由美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 5（2013）2 - 82013年AASRI并行和分布式计算系统基于列数据库Kyung-Chang Kima *，Choung-Seok Kimba部。韩国首尔弘益大学计算机工程系b部韩国釜山新罗大学信息技术系摘要许多无线传感器网络（WSN）应用需要属于不同传感器节点的传感器数据的连接。对于连接处理，重要的是最小化通信成本，因为它是电池功率的主要消耗者。在本文中，我们介绍了传感器网络的并行加入技术。无线传感器网络由许多独立的传感器节点组成，并为无共享架构提供了一个自然的平台来进行并行处理。所提出的并行连接算法是基于传感器数据，存储在面向列的数据库。面向列的数据库按列存储表数据，而不是像传统关系数据库那样按行存储。所提出的算法是节能的，原因有两个。首先，与关系数据库不同，只有相关的列才被运送到连接区域进行最终的连接处理。其次，传感器数据的并行连接处理也提高了性能。性能分析表明，该算法优于基于关系数据库的传感器数据连接算法。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。由美国应用科学研究所负责选择和/或同行评审关键词：无线传感器网络;并行连接;面向列的数据库;无共享结构;通信开销* 通讯作者。联系电话：+811-712-1606;传真：+822-320-1606。电子邮件地址：kckim@hongik.ac.kr。2212-6716 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。美国应用科学研究所负责的选择和/或同行评审doi：10.1016/j.aasri.2013.10.051Kyung-Chang Kim和Choung-Seok Kim / AASRI Procedia 5（2013）231. 介绍许多传感器网络应用需要分散在传感器节点之间的传感器读数的相关性。例如，在对象跟踪系统中，人们可能对从一个指定区域行进到另一指定区域的对象感兴趣，以监视特定对象的交通量和速度。传感器网络可以被建模为分布式数据库，传感器读数使用查询来收集和处理。为了更好地处理传感器读数，可以使用关系数据库将传感器读数存储为数据。连接是查找传感器读数相关性的重要操作。在传感器网络中，最重要的性能指标之一是最小化总的通信开销。总通信成本是相邻传感器节点之间的总数据传输。最小化通信成本是重要的，因为每个传感器节点具有有限的电池功率，并且数据通信是电池能量的主要消耗者。回答应用程序（如对象跟踪）的ad-hoc join查询的一种简单方法是将传感器读数移回基站，并在基站执行join。由于所有传感器数据都必须发送到基站，因此这种方法可能导致高通信成本。更好的方法是在传感器网络内执行加入。在这种网络内的方法中，多个传感器节点协作来执行连接，即分布式连接。由于资源的限制，没有一个传感器节点可以执行加入。然后将加入的结果发送到基站。在本文中，我们提出了一种新的加入技术，无线传感器网络，以最大限度地减少总的通信成本，提高性能。我们的方法是基于两种技术，第一，我们使用一个面向列的数据库，而不是关系数据库来存储传感器数据，第二，我们使用一个并行连接技术。近年来，面向列的数据库受到越来越多的关注和研究工作。面向列的数据库以列顺序（即列方式）存储数据，而不是像传统关系数据库那样以行顺序存储数据。对于只读查询，它们的I/O效率更高，因为它们只访问查询所需的那些列（或属性）。只读查询在数据分析、语义Web和传感器网络中的工作负载和应用中很常见。由于传感器网络可以被建模为分布式数据库，并且传感器节点是独立的，因此它为无共享架构提供了一个自然的平台。使用无共享架构，我们可以分布传感器数据连接和并行连接，以提高性能。为了测试我们提出的连接技术的效率进行性能分析。通过性能实验，我们表明，我们的技术优于目前的传感器网络连接算法的基础上，关系数据库和列导向数据库。本文的其余部分组织如下。我们将在第2节讨论相关的工作。在第三节中，我们提出了一个新的连接算法的基础上面向列的数据库和并行。在第4节中，将该算法的查询性能与传统的传感器网络连接算法进行了比较。结论见第5节。2. 相关作品在文献[1，2]中提出了几种处理传感器网络中简单连接的技术。传感器网络中的一般连接策略可以根据连接区域在传感器网络中的位置分为朴素连接、顺序连接和质心连接[2]。这些通用方法的主要问题是与低连接选择性相关的通信开销。不是用于连接的候选的元组可能不必要地被传输到连接区域。更好的方法是只将连接中涉及的那些记录传输到连接区域。提出了几种过滤技术，其中仅将连接结果中涉及的那些传感器数据传输到4Kyung-Chang Kim和Choung-Seok Kim / AASRI Procedia 5（2013）2靠近基站的连接区域。一种方法是概要连接（SNJ）算法[3]。关键思想是使用传感器读数的概要来修剪那些与连接结果无关的读数。另一种技术是使用位向量（RFB）算法的记录过滤[4]。RFB算法使用在执行半连接之后产生的位向量来在将数据从每个节点运送到连接区域之前修剪不必要的数据。对于面向列的数据库，存在重要的优化技术。物化策略，无论是早期还是晚期，在查询重建过程中都很重要[5]。不可见连接[6]扩展了以前使用面向列的布局改进星型模式查询的工作。提出了一种基于面向列数据库的连接算法，用于传感器网络中数据的连接处理[7]。该算法，我们称之为EM，是基于一个早期的物化策略在面向列的数据库。3. 该算法考虑覆盖道路网络的传感器网络。每个传感器节点检测车辆的id，记录检测到车辆的时间戳，并将时间戳记录保存固定的持续时间。假设区域R和区域S表示进行车辆检测的两组传感器节点。确定在两个区域之间行驶的车辆的速度的连接查询如下：选择R.vehicle_id，R.time，S.time From R，S其中R.locin R_region AND S.loc in S_region AND R.vehicle_id = S.vehicle_id.。为了评估上述查询，收集来自区域R和区域S的传感器读数并将其连接到vehicle_id属性上。示例连接查询取自[3]。在本文中，我们假设传感器数据存储在一个面向列的数据库，而不是一个关系数据库。面向列的数据库按列存储数据（在列中），而不是像关系数据库那样按行存储数据（在行中）。面向列的数据库对于只读查询更有效，因为它们只从磁盘读取查询访问的那些属性（或列）。在面向列的数据库中，有两种物化策略，早物化和晚物化。物化（Materialization），也称为元组拼接（tuple stitching）或元组构造（tuple construction），是将单列投影组合成更宽元组的过程，需要输出行样式元组以支持符合标准的关系数据库接口，如ODBC和JDBC。在早期物化策略中，如果需要列，则将每个列添加到中间查询结果中以形成元组。在后期物化策略中，被访问的列直到查询计划的某个部分被处理之后才形成元组。我们在本文中考虑的一个一般查询如下：SELECT R.A1，R.A2，S.A2 FROM R，S其中R.loc在R区域中并且S.loc在S区域中并且R.A1 = S.A1。R和S是相关性表，R区域（S区域）是传感器网络中的R区域（S区域），其中传感器读数被获取。R.A1和S.A1分别是R和S中的连接属性。查询在称为查询汇（即汇节点）的传感器节点处发起，并且查询结果也在查询汇处收集。由于每个节点的内存大小是有限的，因此汇聚节点无法在本地执行连接。连接必须通过称为连接区域的多个节点的协作来执行。该算法是一种分布式算法，涉及R区域、S区域、连接区域和汇聚节点。R（S）区域包含多个传感器节点，每个传感器节点存储关系R（S）的一部分。此外，连接区域F还包含协作以执行分布式连接的若干传感器节点。连接算法是一种后期实现的策略，分三个阶段执行，即选择阶段、连接阶段和结果阶段。在选择阶段，连接列值最初被发送到连接区域F。在连接阶段，在R和S的连接列之间执行半连接，以仅将合格的列值从R区域和S区域运送到连接节点F。在结果阶段，R和S的合格列值被缝合在一起以构造元组并发送到sink节点。该算法的选择阶段由两个步骤组成。在第一步中，汇聚节点发起查询并将其发送到R区域和S区域中的节点。接收节点将查询广播到Kyung-Chang Kim和Choung-Seok Kim / AASRI Procedia 5（2013）25R（S）区域中的其他节点。关系R和S都被划分成若干不相交的子表，每个子表具有连接属性值范围。R（S）区域中的每个节点存储子表。在第二步中，关系R和S的连接列值被运送到连接节点F。使用基于散列的分布方案，F中的每个节点以相同的连接值范围连接R和S的两个子集。R和S的相同连接属性值始终在F中的同一节点处连接。该算法的连接阶段由三个步骤组成。在第一步中，在每个节点处执行半连接。连接的结果产生两个数据结构。一个是位置列表，另一个是位图（对于R和S）。我们假设存在元数据以在分布式情况下计算正确的位置列表和位图。半连接的结果是一个包含两列的位置列表，一列用于R的连接列，另一列用于S的连接列。位置列表中的每个条目对包含具有相同联接属性值的R和S的联接列的位置。位图包含满足联接条件的联接列的位置。在第二步中，将位图发送回R（S）区域中的节点。接收节点将位图广播到R（S）区域中的其他节点。在第三步中，在每个节点处，位图用于从位被设置为1的相应位置处的合格列中提取值。所选列值被传送到联接区域F中的指定节点。我们假设存在元数据以将表位图映射到子表。在选择阶段的第二步中，基于散列的方案用于将所选列值运送到F区域中与具有相同位置的联接值相同的节点。该算法的结果阶段由两个步骤组成。在第一步中，在F中的每个节点处，连接阶段的第一步中的位置列表和位图用于将R和S的列值缝合在一起以构造元组。元组拼接在F中的每个节点处并行执行。我们假设存在元数据以在给定位置列表和位图的情况下映射R和S的列值。在第二步中，从F中的每个节点构造的元组作为查询结果被运送到sink节点。由于传感器网络中的传感器节点是独立的，它为无共享架构提供了一个自然的平台来执行并行处理。如果我们假设传感器网络是一个无共享的体系结构，那么将刚才描述的分布式算法转换为并行算法是很简单的。基于散列的分发方案确保具有相同联接属性值的元组总是在相同联接节点处被发送和联接。这确保了连接和元组拼接可以在每个指定节点上并行执行。4. 性能分析为了测试本文提出的连接算法的成本效益，与现有的SNJ，RFB和EM算法的性能分析。SNJ和RFB算法是基于关系数据库的，而EM算法在面向列的数据库中使用早期物化策略。从通信代价的角度对不同算法进行了比较，通信代价是为了得到连接结果而向各个节点发送的字节数。4.1实验环境针对R和S的不同表大小（2，000元组和5，000元组）比较连接算法，以确定表R和S中的元组数量的增加对通信成本的影响。我们还测试了几个连接选择性（0.01，0.05，0.1，0.5）的不同连接算法的通信成本。连接选择性是表中满足连接条件的元组的比例。联接选择性0.05意味着只有5%的元组符合查询条件。6Kyung-Chang Kim和Choung-Seok Kim / AASRI Procedia 5（2013）2450400350300250200150100500SNJRFBEM提出0.010.05 0.1 0.5 0.01 0.05 0.1连接选择性（左：2000个元组，右：5000个元组）为了简化网络流量分析，我们假设在消息传输过程中不发生故障。消息和元组的大小被假定为各为40个字节。对于给定的查询，得到的连接元组（即查询结果）的大小被假定为30字节。对于面向列的数据库，假设每列的大小为10字节。4.2实验结果在执行查询时，总通信成本是选择阶段、连接阶段和结果阶段的通信成本之和。每个阶段的通信成本是将数据发送到该阶段的其他节点的成本。通信成本的单位是从一个节点传输到其他节点的字节数。图1显示了不同连接选择性的连接算法的通信成本，当表R和表S的基数分别为2000元组和5,000元组时。实验中使用的连接选择性范围为0.01、0.05、0.1至0.5。连接选择性为0.1意味着只有10%的元组满足连接条件。在我们提出的算法中，位图的大小是位数，其中每个位对应于一个列位置。实验表明，该算法优于SNJ和RFB算法的所有不同的连接选择性测试。它也优于EM算法，这也是基于列面向数据库。可以看出，所提出的算法的性能得到更好的连接选择性变得更低。换句话说，随着更多的元组被连接并在连接结果中输出，所提出的算法的通信成本进一步降低。Fig. 1.连接选择性图1示出了用于要被联接的表的不同基数的不同算法的通信成本。所使用的连接选择性是0.1，基数从R和S的每个2000元组变化到每个5000元组和每个8000元组。我们提出的算法优于SNJ和RFB算法的所有不同的基数测试。与SNJ算法相比，通信成本降低了约18%的所有基数。与RFB算法相比，通信成本降低了约13%的所有基数。可以看出，我们提出的算法的性能更好，但通信成本保持不变，不同的基数。性能测试结果表明，连接选择性对通信开销的影响大于连接表的大小数据传输（KNOW）Kyung-Chang Kim和Choung-Seok Kim / AASRI Procedia 5（2013）27我们没有对传感器网络的不同连接技术的查询响应时间进行实验。原因是因为我们认为传感器网络最重要的性能标准是总通信成本。然而，很容易观察到，使用我们提出的算法的并行版本的查询响应时间比其他算法，不基于并行计算更快。使用我们的算法，更多的传感器节点参与查询处理，更快的查询响应时间，因为连接和数据装运都可以并行完成。5. 结论提出了一种传感器网络数据处理的分布式算法。该算法是基于一个后期物化的战略，在面向列的数据库中的数据表存储在列。如果我们假设传感器网络是一个无共享的体系结构，那么将分布式算法转换为并行版本是很简单的。所提出的算法是节能的，因为只有那些列和列值中涉及的查询被运送到传感器节点的连接区域。在使用基于关系数据库的过滤技术来在将候选元组运送到连接区域之前修剪不必要的元组方面，报告了几个结果（例如SNJ，RFB）。也有人提出了一种类似的方法，基于面向列的数据库（例如，EM）。实验结果表明，我们提出的算法优于SNJ，RFB和EM算法的通信成本。SNJ和RFB算法基于关系数据库，EM算法基于面向列的数据库。为了验证我们的实验，我们使用了不同的连接选择性值以及不同的表大小。在性能分析中，我们发现，该算法的性能得到更好的连接选择性降低。换句话说，如果连接更多的元组并在连接结果中输出，则所提出的算法的通信成本降低。此外，使用我们的算法，更多的传感器节点参与查询处理，更快的查询响应时间，因为加入和数据运输到加入节点可以并行完成。确认本研究由韩国教育科学技术部资助的韩国国家研究基金会（NRF）的基础科学研究计划支持（资助号2012-0007012）引用[1] 马登，S。传感器网路查询处理架构之设计与评估。博士论文，加州大学伯克利分校，2003[2] Coman，A.; Nascimento，M.; Sander，J.，传感器网络中的加入位置。在Proceedings of MobileData Management（MDM）中，Mannheim，德国，2007[3] 余，H.，Lim，E.，Zhang，J. On In-network Synopsis Join Processing for Sensor Networks. In：Proceedings of Mobile Data Management，Nara，Japan，2006[4] Kim，K.C.，Oh B. J.传感器网络数据库中网络内连接处理的节能过滤方法。《多媒体、计算机图形学和广播学报》，韩国济州，2011年[5] 阿巴迪，D.J.，迈尔斯，D.S.，DeWitt，D.J.，Madden，S.R.面向列的数据库管理系统中的物化策略。数据工程国际会议（ICDE），伊斯坦布尔，土耳其，2007年。[6] 阿巴迪，D.J.，Madden，S.R.，Hachem，N.列存储与排店：他们真的有什么不同8Kyung-Chang Kim和Choung-Seok Kim / AASRI Procedia 5（2013）2在ACM SIGMOD会议记录中，加拿大温哥华，2008年。[7] Kim，K. C，Kim C. S.无线传感器网络中传感器数据处理的节能技术。在：普适计算和多媒体应用程序（UCMA），巴厘岛，印度尼西亚2012