没有合适的资源?快使用搜索试试~ 我知道了~
0 AASRI会议论文集 5 ( 2013 ) 2 – 802212-6716 © 2013作者。由ElsevierB.V.出版。由美国应用科学研究学会负责选择和/或同行评审。doi: 10.1016/j.aasri.2013.10.0510ScienceDirect02013年并行和分布式计算系统AASRI会议0使用列-并行处理传感器网络数据0面向数据库的0金敬昌 a*,金钟锡 b0a 韩国首尔弘益大学计算机工程系, b 韩国釜山新罗大学信息技术系0摘要0许多无线传感器网络(WSN)应用需要连接属于不同传感器节点的传感器数据。对于连接处理,最重要的是要最小化通信成本,因为通信成本是电池能量的主要消耗者。在本文中,我们介绍了一种用于传感器网络的并行连接技术。WSN由许多独立的传感器节点组成,并提供了一个自然的平台来进行无共享架构的并行处理。所提出的并行连接算法基于存储在列式数据库中的传感器数据。列式数据库以列而不是以传统关系型数据库中的行的方式存储表数据。所提出的算法在能量上是高效的,有两个明显的原因。首先,与关系型数据库不同,只有相关的列被传送到连接区域进行最终的连接处理。其次,传感器数据的并行连接处理也提高了性能。性能分析表明,所提出的算法优于基于关系型数据库的传感器数据连接算法。© 2013由ElsevierB.V.出版。由美国应用科学研究学会负责选择和/或同行评审。关键词:无线传感器网络;并行连接;列式数据库;无共享架构;通信成本0* 通讯作者。电话:+811-712-1606; 传真:+822-320-1606.电子邮件地址:kckim@hongik.ac.kr.0在线访问www.sciencedirect.com0© 2013作者。由Elsevier B.V.出版。由美国应用科0在CC BY-NC-ND许可下开放访问。0在CC BY-NC-ND许可下开放访问。 03 金敬昌和金钟锡 / AASRI会议论文集 5 ( 2013 ) 2 – 801. 引言0许多传感器网络应用需要对散布在传感器节点之间的传感器读数进行相关性分析。例如,在物体跟踪系统中,人们可能对从一个指定区域到另一个指定区域行进的物体感兴趣,以监测特定物体的交通量和速度。传感器网络可以被建模为分布式数据库,并使用查询收集和处理传感器读数。为了更好地处理传感器读数,可以将传感器读数以数据的形式存储在关系型数据库中。连接是在发现传感器读数的相关性时的重要操作之一。在处理传感器网络的连接操作时,最重要的性能指标之一是最小化总通信成本。总通信成本是相邻传感器节点之间的数据传输总量。最小化通信成本很重要,因为每个传感器节点都有有限的电池能量,数据通信是电池能量的主要消耗者。对于应用程序(如物体跟踪)的即席连接查询,一个简单的方法是将传感器读数移回基站,并在基站上执行连接。这种方法可能会产生高昂的通信成本,因为所有传感器数据都必须传输到基站。更好的方法是在传感器网络内部执行连接。在这种内部网络方法中,多个传感器节点协同执行连接,即分布式连接。由于资源限制,没有单个传感器节点可以执行连接。连接的结果然后传输到基站。在本文中,我们提出了一种用于无线传感器网络的新型连接技术,以最小化总通信成本并提高性能。我们的方法基于两种技术:首先,我们使用列式数据库而不是关系型数据库来存储传感器数据;其次,我们使用并行连接技术。最近几年,人们对列式数据库进行了越来越多的关注和研究工作。列式数据库按列顺序(即按列排列)存储数据,而不是如传统的关系型数据库那样按行顺序存储。对于只读查询而言,它们在I/O效率上更高效,因为它们只访问查询所需的那些列(或属性)。只读查询在数据分析、语义Web和传感器网络中的工作负载和应用程序中很常见。由于传感器网络可以被建模为分布式数据库且传感器节点是独立的,因此它提供了一个自然的无共享架构平台。使用无共享架构,我们可以分布传输要连接的传感器数据,并执行并行连接以提高性能。为了测试我们提出的连接技术的效率,进行了性能分析。通过性能实验,我们证明我们的技术在基于关系型数据库和基于列式数据库的传感器网络上的连接算法方面优于当前的连接算法。本文的其余部分组织如下。我们在第2节讨论相关工作。在第3节中,我们提出了一种基于列式数据库和并行性的新型连接算法。在第4节中,我们将所提出的算法的查询性能与传感器网络的传统连接算法进行了比较。第5节给出了结论。02. 相关工作0文献中提出了几种处理传感器网络中简单连接的技术[1,2]。传感器网络中的一般连接策略可以分为简单连接、顺序连接和质心连接,具体取决于连接区域在传感器网络中的位置[2]。这些常规方法的主要问题是与低选择性连接相关的通信成本开销。不是连接候选的元组可能会被不必要地传输到连接区域。更好的方法是仅将参与连接的那些记录传输到连接区域。已经提出了几种过滤技术,其中只有与连接结果相关的传感器数据被传输到接近基站的连接区域。一种方法是利用传感器读数的概要信息来修剪与连接结果无关的读数的概要连接(SNJ)算法[3]。另一种技术是使用位向量进行记录过滤(RFB)算法[4]。在执行半连接后,RFB算法使用位向量来修剪在从每个节点向连接区域传输数据之前的不必要数据。对于列式数据库存在重要的优化技术。在查询重构过程中,早期和晚期的物质化策略都是重要的[5]。隐式连接[6]扩展了使用列式布局改进星型模式查询的先前工作。提出了一种基于列式数据库的连接算法来执行传感器网络中的数据连接处理[7]。我们将该算法称为EM,它基于列式数据库中的早期物质化策略。 04 金敬昌和金钟锡 / AASRI会议论文集 5 ( 2013 ) 2 – 803. 提出的算法0考虑一个覆盖道路网络的传感器网络。每个传感器节点检测到车辆的ID,记录检测到车辆的时间戳,并将时间戳记录保留固定的持续时间。假设区域R和区域S表示两组进行车辆检测的传感器节点。用于确定两个区域之间车辆行驶速度的连接查询如下所示:选择 R.vehicle_id, R.time, S.time From R, S Where R.loc in R_region AND S.loc in S_region AND R.vehicle_id =S.vehicle_id..为了评估上述查询,从区域R和区域S收集并联接传感器读数。这个例子的联接查询选自[3]。在本文中,我们假设传感器数据存储在列存数据库中,而不是关系型数据库。列存数据库以列的形式存储数据(按列存储),而不像关系型数据库那样以行的形式存储数据(按行存储)。对于只读查询,列存数据库比较高效,因为它们只读取查询所访问的属性(或列)的磁盘数据。列存数据库有两种材料化策略,即早期材料化和延迟材料化。材料化是将单列投影组合成更宽的元组的过程,需要输出支持符合标准的关系型数据库接口(如ODBC和JDBC)的行样式元组。在早期材料化策略中,如果需要某个列,则将该列添加到中间查询结果中以形成元组。在延迟材料化策略中,只有在处理查询计划的某个部分之后,才形成元组。我们在本文中考虑的一个通用查询如下所示:SELECT R.A1, R.A2, S.A2 FROM R, S WHERE R.loc in R-region AND S.loc in S-region AND R.A1 =S.A1.R和S是关联表,R-region(S-region)是传感器网络中进行传感器读数的R区域(S区域)。R.A1和S.A1分别是R和S中的连接属性。查询在称为查询汇聚点(即汇聚节点)的传感器节点上启动,并且查询结果也在查询汇聚点收集。由于每个节点的内存大小有限,汇聚节点无法在本地执行联接。联接必须通过几个节点的协作来执行。所提出的算法是涉及R区域、S区域、联接区域和汇聚节点的分布式算法。R(S)区域包含多个传感器节点,每个节点存储R(S)关系的一部分。此外,联接区域F还包含多个传感器节点,它们协作执行分布式联接。该联接算法采用延迟材料化策略,分为三个阶段,即选择阶段、联接阶段和结果阶段。在选择阶段,联接列的值最初发送到联接区域F。在联接阶段,对R和S的联接列执行半联接,以仅将符合条件的列值从R区域和S区域发送到联接节点F。在结果阶段,将R和S的符合条件的列值进行合并以构建元组,并将其发送到汇聚节点。所提出的算法的选择阶段由两个步骤组成。在第一步中,汇聚节点启动查询并将其发送到R区域和S区域中的一个节点。接收节点将查询广播到R(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中每个节点的构建的元组作为查询结果发送到汇聚节点。由于传感器网络中的传感器节点是独立的,因此它为执行并行处理提供了自然的平台。如果我们假设传感器网络使用共享无存储体系结构,则可以将刚刚描述的分布式算法转换为并行算法。基于哈希的分发方案确保具有相同连接属性值的元组始终在相同的联接节点上发送和联接。这确保联接和元组合并都可以在每个指定节点上并行执行。 05 金庆昌和金宗锡 / AASRI Procedia 5 ( 2013 ) 2 – 80为了测试本文提出的联接算法的成本效益,进行了与现有的SNJ、RFB和EM算法的性能分析。SNJ和RFB算法基于关系型数据库,而EM算法使用列存数据库的早期材料化策略。不同的算法在通信成本方面进行了比较,通信成本是传输到各个节点以获取联接结果的字节数。04. 性能分析04.1 实验环境0将联接算法与不同表大小(2,000个元组和5,000个元组)的R和S进行比较,以确定表R和S中元组数量增加对通信成本的影响。我们还测试了不同联接选择性(0.01、0.05、0.1、0.5)下不同联接算法的通信成本。联接选择性是满足联接条件的表元组的比例。联接选择性为0.05表示只有5%的元组符合查询条件。 06 金庆昌和金宗锡 / AASRI Procedia 5 ( 2013 ) 2 – 80为了简化网络流量分析,我们假设在消息传输过程中不会发生故障。消息和元组的大小均假设为40字节。对于给定的查询,假设联接元组(即查询结果)的大小为30字节。对于列存数据库,假设每个列的大小为10字节。04.2 实验结果0在执行查询时,总通信成本是选择阶段、连接阶段和结果阶段的通信成本之和。每个阶段的通信成本是将数据发送到其他节点的成本。通信成本的单位是从一个节点传输到其他节点的字节数。图1显示了不同连接选择性的连接算法的通信成本,当表R和表S的基数分别为2000元组和5000元组时。实验中使用的连接选择性范围为0.01、0.05、0.1和0.5。连接选择性为0.1意味着只有10%的元组满足连接条件。我们提出的算法中位图的大小是每个位对应一个列位置的位数。实验表明,所提出的算法在所有不同的连接选择性测试中优于SNJ和RFB算法。它还优于基于列式数据库的EM算法。可以看出,所提出的算法的性能随着连接选择性的降低而提高。换句话说,随着越来越多的元组在连接结果中被连接和输出,所提出的算法的通信成本进一步降低。0图1. 连接选择性上的通信成本0图1显示了不同表连接的不同算法的通信成本。使用的连接选择性为0.1,基数从2000个元组(R和S各1000个元组)变化到5000个元组(R和S各2500个元组)和8000个元组(R和S各4000个元组)。我们提出的算法在所有不同的基数测试中优于SNJ和RFB算法。与SNJ算法相比,通信成本在所有基数上减少约18%。与RFB算法相比,通信成本在所有基数上减少约13%。可以看出,我们提出的算法的性能更好,但通信成本对于不同的基数保持不变。性能结果表明,连接选择性决定了通信成本,而不是要连接的表的大小。0数据传输(千字节)0连接选择性(左:2000个元组,右:5000个元组)0SNJ0RFB0EM0提出的 07 金光章和金宗锡 / AASRI Procedia 5 ( 2013 ) 2 – 80我们没有对传感器网络中不同连接技术的查询响应时间进行实验。原因是我们认为传感器网络最重要的性能指标是总通信成本。然而,很容易观察到,使用我们提出的并行计算算法的查询响应时间比不基于并行计算的其他算法更快。使用我们的算法,参与查询处理的传感器节点越多,查询响应时间越快,因为连接和数据传输可以并行完成。05. 结论0本文提出了一种用于处理传感器网络中数据的分布式算法。所提出的算法基于列式数据库中的延迟材料化策略,其中数据表以列的形式存储。如果我们假设传感器网络采用共享无关架构,那么将分布式算法转换为并行版本是很直接的。所提出的算法是能效高的,因为只有与查询相关的列和列值才会被传送到连接区域中的传感器节点。在运用基于关系数据库的过滤技术来裁剪不必要的元组之前,已经有一些结果(例如SNJ、RFB)报告了使用关系数据库的情况下的情况。还提出了一种基于列式数据库的类似方法(例如EM)。实验结果表明,我们提出的算法在通信成本方面优于SNJ、RFB和EM算法。SNJ和RFB算法基于关系数据库,EM算法基于列式数据库。为了验证我们的实验,我们使用了不同的连接选择性值和不同的表大小。在性能分析中,我们表明所提出的算法的性能随着连接选择性的降低而提高。换句话说,如果更多的元组被连接和输出到连接结果中,所提出的算法的通信成本将降低。此外,使用我们的算法,参与查询处理的传感器节点越多,查询响应时间越快,因为连接和数据传输都可以并行完成。0致谢0这项研究得到了韩国国家研究基金会(NRF)教育、科学和技术部的基础科学研究计划的支持(资助编号2012-0007012)。0参考文献0[1] Madden, S. 传感器网络查询处理架构的设计与评估。加利福尼亚大学伯克利分校博士论文,2003年。[2] Coman, A.;Nascimento, M.; Sander, J.传感器网络中连接位置的研究。移动数据管理(MDM)会议论文集,德国曼海姆,2007年5月1日。[3] Yu, H., Lim, E.,Zhang, J. 传感器网络的网络简介连接处理研究。移动数据管理会议论文集,日本奈良,2006年。[4] Kim, K.C, Oh B. J.传感器网络数据库中处理网络连接的节能过滤方法。多媒体、计算机图形学和广播会议论文集,韩国济州,2011年。[5]Abadi, D.J., Myers, D.S., DeWitt, D.J., Madden, S.R.列式数据库管理系统中的材料化策略。国际数据工程会议论文集,土耳其伊斯坦布尔,2007年。[6] Abadi, D.J., Madden,S.R., Hachem, N. 列式存储与行式存储:它们到底有多大不同?在ACM SIGMOD会议论文集,加拿大温哥华,2008年。[7]Kim, K.C, Kim C. S.无线传感器网络中处理传感器数据的一种节能技术。普适计算和多媒体应用会议论文集,印度尼西亚巴厘岛,2012年。 08 金光章和金宗锡 / AASRI Procedia 5 ( 2013 ) 2 – 80
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 李兴华Java基础教程:从入门到精通
- U盘与硬盘启动安装教程:从菜鸟到专家
- C++面试宝典:动态内存管理与继承解析
- C++ STL源码深度解析:专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手:数据管理与企业增值的战略
- Eclipse IDE基础教程:从入门到精通
- Shell脚本专家宝典:全面学习与资源指南
- Tomcat安装指南:附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华:必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功