分布式传感器数据库系统多查询架构体系及融合算法研究
|
摘要
集成了微电子技术、计算机技术和无线通信技术的新型网络——无线传感器网络提供了一种全新的信息获取和处理方式,它由大量的传感器节点以自组网的形式构成,这些节点通过无线通信方式协作地完成分布式查询任务。近年来,传感器网络在军事国防、生物医疗、环境监测、抢险救灾等许多重要领域的应用越来越广,已成为当前的研究和应用的热点。
从查询角度而言,无线传感器网络可以看作是一个以节点感知、存储数据为基础的分布式数据库系统。用户发出查询请求,传感器网络通过相应的查询处理技术,路由技术、数据融合技术,将用户感兴趣的数据经由网络发送给终端用户。由于无线传感器网络中能量和通信等方面存在着严格的资源限制,故不能将传统的分布式数据库查询技术直接应用于传感器网络。
在对现有无线传感器网络查询技术分析研究的基础上,本论文关注于目前的研究较少的多查询处理问题,并依据无线传感器网络多查询处理的要求,提出了一种以节能为首要目标的新的查询架构体系(Multi-Queries Framework:MQF)。主要由分布于用户终端的窗口模块,查询服务器,历史数据库,基站的查询管理器,和节点的查询过滤器5个功能模块构成,其中查询管理器是整个体系的核心部分。在该框架下,提出了多查询的分类算法和查询融合算法。实验表明,利用本文的算法,在同等条件下,可以有效节省传感器网络能量的消耗,进而延长网络的生命周期。
Wireless sensor networks (WSNs), a novel network, which integrated with micro-electronics technology, computer technology and wireless communication technology, provide a new approach to information acquisition and processing. It consists of a large number of small sensor nodes and accomplishes distributed query tasks through wireless communication collaboration among them. In recent years, it is extensively applied in military and national defense, biomedical, environmental monitoring, emergency relief, and many other important areas, and has become the hot spots of current research and application.
From the query point of view, wireless sensor networks could be regarded as a distributed database system, in which the sensor nodes sense and store data. Users propose the query requests, and then the interested data is send to the end user by the corresponding query processing, routing and data aggregation techniques via network nodes. Because the sensor nodes have strict resource constraints on the energy and communication, the traditional distributed database query techniques can not be directly applied in sensor networks.
After analyzing and studying on the existing query processing techniques, this thesis focuses on processing multi-queries problem which is important but without much attention paid to. So a new Multi-Queries Framework (MQF) is presented for query processing problems in this thesis with the primary purpose of energy-saving. The system is mainly composed of five function modules: Window, Query Server, History Database in User Terminals, Query Manager in base station, and Query Filters in sensors, and among the five modules, Query Manager is the core of the entire system. Under the proposed framework, the thesis discusses Multi-queries classification algorithm and Multi-queries aggregation algorithm and the simulation results show that our algorithms can effectively save the energy consumption and prolong the network lifetime on the same query conditions.
从查询角度而言,无线传感器网络可以看作是一个以节点感知、存储数据为基础的分布式数据库系统。用户发出查询请求,传感器网络通过相应的查询处理技术,路由技术、数据融合技术,将用户感兴趣的数据经由网络发送给终端用户。由于无线传感器网络中能量和通信等方面存在着严格的资源限制,故不能将传统的分布式数据库查询技术直接应用于传感器网络。
在对现有无线传感器网络查询技术分析研究的基础上,本论文关注于目前的研究较少的多查询处理问题,并依据无线传感器网络多查询处理的要求,提出了一种以节能为首要目标的新的查询架构体系(Multi-Queries Framework:MQF)。主要由分布于用户终端的窗口模块,查询服务器,历史数据库,基站的查询管理器,和节点的查询过滤器5个功能模块构成,其中查询管理器是整个体系的核心部分。在该框架下,提出了多查询的分类算法和查询融合算法。实验表明,利用本文的算法,在同等条件下,可以有效节省传感器网络能量的消耗,进而延长网络的生命周期。
Wireless sensor networks (WSNs), a novel network, which integrated with micro-electronics technology, computer technology and wireless communication technology, provide a new approach to information acquisition and processing. It consists of a large number of small sensor nodes and accomplishes distributed query tasks through wireless communication collaboration among them. In recent years, it is extensively applied in military and national defense, biomedical, environmental monitoring, emergency relief, and many other important areas, and has become the hot spots of current research and application.
From the query point of view, wireless sensor networks could be regarded as a distributed database system, in which the sensor nodes sense and store data. Users propose the query requests, and then the interested data is send to the end user by the corresponding query processing, routing and data aggregation techniques via network nodes. Because the sensor nodes have strict resource constraints on the energy and communication, the traditional distributed database query techniques can not be directly applied in sensor networks.
After analyzing and studying on the existing query processing techniques, this thesis focuses on processing multi-queries problem which is important but without much attention paid to. So a new Multi-Queries Framework (MQF) is presented for query processing problems in this thesis with the primary purpose of energy-saving. The system is mainly composed of five function modules: Window, Query Server, History Database in User Terminals, Query Manager in base station, and Query Filters in sensors, and among the five modules, Query Manager is the core of the entire system. Under the proposed framework, the thesis discusses Multi-queries classification algorithm and Multi-queries aggregation algorithm and the simulation results show that our algorithms can effectively save the energy consumption and prolong the network lifetime on the same query conditions.
引文
[1]崔莉、鞠海玲、苗勇等,无线传感器网络研究进展,计算机研究与发展,2005,42(1):163~174
[2]Estrin D,Govindan R., Heidemann J., Kumar S. ,Next century challenges: Scalable coordinate in sensor network, In Proc. of the 5th ACM/IEEE International Conference on Mobile Computing and Networking, 1999, 263~270
[3]C. Y Chong, S. Kumar, "Sensor networks evolution, opportunities, and challenge", Proceedings of the IEEE, 2003, vol. 91:1247~1256
[4]MIT Technology Review,“10 emerging areas of technology", Feb 2003, http://www.tech nologyreview.com
[5]Deployable Autonomous Distributed System, http://www.onr.navy.mil/sci tech/oc ean/ 321sensing/info _deploy.htm
[6]张晋,传感器网络的数据管理研究:[硕士学位论文],哈尔滨;哈尔滨工程大学,2006
[7]Pister K, Hohlt B, Jeong J et al., Ivy-A sensor network infrastructure, 2003, http://www-bsac.eecs.berkeley.edu/projects/ivy
[8]任丰原,黄海宁,林闯,无线传感器网络,软件学报,2003,14(7):1287~1291
[9]蒋鹏,基于无线传感器网络的湿地水环境远程实时监测系统关键技术研究,传感技术学报,2007,20(1):183~186
[10]孙利民,李建中,陈渝等,无线传感器网络,北京:清华大学出版社,2005,4~13
[11]J. Gao, L. J. Guibas, J. Hershberger, L. Zhang, Fractionally Cascaded Information in a Sensor Network, Proc. of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN'04), 2004,311~319
[12] S. Madden, W. I-long, TinyDB, http://telegraph.cs.berkeley.edu/tiny-db/.2003
[13]陈利虎,无线传感器网络实验平台的研究:[硕士学位论文],长沙;国防科学技术大学,2004
[14]Weisong Shi, Sellamuthu, S., Kewei Sha; Schwiebert, L., Query Agent: A General Query Processing Tool for Sensor Networks, Parallel Processing International Conference 2004, 15-18 :488~ 495
[15]Wei Yu, Thang Nam Le, Jangwon Lee and Dong Xuan, Effective Query Aggregation for Data Services in Sensor Networks, Computer Communications, November 2006, 29(18, 28): 3733~3744
[16]Sinha A, Chandrakasan A, Dynamic power management in wireless sensor network, IEEE Design and Test of Computer, 2001, 18(2): 62~74
[17]Ph. Bonnet, P.Seshadri, Device Database Systems, Proceedings of the International Conference on Data Engineering ICDE’99, San Diego, CA, 2000
[18]Ph.Bonnet, J.Gehrke, P.Seshadri, Querying the Physical World, IEEE personal Communications, Special Issue“Networking the Physical World”,2000
[19]Kyungseo Park, R. Elmasri, Query Classification and Storage Evaluation in Wireless Sensor Networks, Proceedings of 22nd International Conference on Data Engineering Workshops, 2006
[20]陈丹,郑增威,李际军,无线传感器网络研究综述,计算机测量与控制,2004,12(8):701~704
[21]Zhanyang Zhang, Guping Zheng, A Cluster Based Query Protocol for Wireless Sensor Networks, the 8th International Conference Advanced Communication Technology, 2006, 140~145
[22]N. Trigoni, Y. Yao, A. Demers, ec al., Hybrid push-pull query processing for sensor networks, In Workshop on Sensor Networks in GI, 2004
[23]马祖长,孙怡宁,梅涛,无线传感器网络综述,通信学报,2004,25(4):114~123
[24]Bonnet P, Gehrke JE, Seshadri P,Towards sensor database systems, In Tan K-L, Franklin MJ, Lui JCS, eds, Proceedings of the 2nd International Conference on Mobile Data Management. Hong Kong: Springer-Verlag, 2001, 3~14
[25]Minji Wu, Jianliang Xu, Xueyan Tang, et al,Top-k Monitoring in Wireless Sensor Networks, IEEE Trans.. Data Eng. 2007, 19 (7): 962~976
[26]Zhibin Zhao,Lan Yao, Binyang Li .et al, Filter-based Approach for Optimizing Top-k Queries in Wireless Sensor, International Conference of ITS Telecommunications Proceedings , 2006
[27]Qunhua Pan, Minglu Li, Min-You ,History-sensitive Based Approach to Optimize Top-k Queries in Wireless Sensor Network, Lecture Notes in Computer Science,2006, 43(25):674~684
[28]Adam Silberstein Silberstein, Rebecca Braynard, Carla Ellis,et al.,A Sampling-Based Approach to Optimizing Top-k Queries in Sensor Networks,22nd International Conference on Data Engineering, 2006,68
[29]M. Demirbas, H. Ferhatosmanoglu, Peer-to-peer spatial queries in sensor networks, In Proc. of the 3rd IEEE International Conference on Peer-to-Peer Computing, 2003
[30]B. Karp, H.T. Kung, GPSR: Greedy perimeter stateless routing for wireless networks, In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, 2000, 243~254
[31]Julian Winter,Wang-Chien Lee,KPT: A Dynamic KNN Query Processing Algorithm for Location-aware Sensor Networks , Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB, 2004, 119~124
[32]刘灿,张德贤,KNN查询处理算法性能研究,,苏州科技学院学报(自然科学版),2006.9,23(3):73~77
[33]B. Wu, K. T. Chuang, C. M. Chen,.et al., DIKNN: An Itinerary-based KNN Query Processing Algorithm for Mobile Sensor Networks,In ICDE, 2007
[34]Tao-Young Fu,Wen-Chih Peng,Wang-Chien Lee,Optimizing Parallel Itineraries for KNN Query Processing in Wireless Sensor Networks,Association for Computing Machinery, 2007
[35]Y. Xu,T. Y. Fu,W. C. Lee,et al., Itinerary-based Techniques for Processing K Nearest Neighbor Queries in Location-aware Sensor Networks,Signal Processing, 2007
[36]Z. Song ,N. Roussopoulos,K -Nearest Neighbor Search for Moving Query Point, In International Symposium on Spatial and Temporal Databases, 2001, 79~96
[37]J. Winter, Y. Xu, and W. C. Lee,Energy Efficient Processing of K Nearest Neighbor Queries in Location-aware Sensor Networks,In Mobiquitous, 2005, 281~292
[38]吴亚珺,传感器网络数据查询处理技术研究:[硕士学位论文],哈尔滨;黑龙江大学,2006
[39]A.Demers, J.Gehrke, R. Rajaraman, .et al, the cougar project: A work-in-progress report, SIGMOD Record, 2003, 32(4)
[40] S. Madden and M. Franklin, "Fjording the Stream: AnArchitecture for Queries over Streaming Sensor Data", the 18th International Conference on Data Engineering, 2002
[41]N. Trigoni, Y. Yao, J. Gehrke.et al, Multi-queries optimization for sensor networks, In Proc.of DCOSS, 2005
[42]Shili Xiang, Hock BengLim, Kian-Lee Tan, Impact of Multi-queries Optimization in Sensor Networks, Proceedings of the 3rd workshop on Data management for sensor networks, 2006, 1:7~12
[43]Guohua Liu, Shuzhi Zhang, Dongming Zhang, Research on Multiple Queries Processing Technology in Wide Area Sensor Databases, International Conference on Computational Intelligence for Modelling Control and Automation,2006
[44]Shili Xiang, Hock Beng Lim, Kian-Lee Tan, et al, Two-Tier Multiple Query Optimization for Sensor Networks, 27th International Conference on Distributed Computing Systems ,2007
[45]S. Madden, M. J. Franklin, Fjording the stream: architecture for queries over streaming sensor data, In Proc. of ICDE, 2002
[46]张明宇,传感器网络上的近似查询处理:[硕士学位论文],黑龙江大学,2005
[47]谢磊,陈力军,陈道蓄,谢立,无线传感器网络的查询处理机制研究综述,计算机科学,2006,33(9):45~49,68
[48]李建中,李金宝,石胜飞,传感器网络及其数据管理的概念、问题与进展,软件学报,2003, 14(10):1717~1727
[49]A.Silberstein, R. Braynard, and J. Yang,Constraint Chaining: On energy-efficient continuous monitoring in sensor networks,In Proc. Of SIGMOD,2006
[50]F.-C. F. Chen, M. H. Dunham, Common subexpression processing in multiple-query processing, IEEE TKDE, 1998, 10(3):493~499
[51]Deployable Autonomous Distributed System, http://www.onr.navy.mil/sci tech/ocean/ 321 sensing/info _deploy.htm
[52]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, .et al,A survey on sensor networks,IEEE Communications Magazine, 2002,40(8):102~114
[2]Estrin D,Govindan R., Heidemann J., Kumar S. ,Next century challenges: Scalable coordinate in sensor network, In Proc. of the 5th ACM/IEEE International Conference on Mobile Computing and Networking, 1999, 263~270
[3]C. Y Chong, S. Kumar, "Sensor networks evolution, opportunities, and challenge", Proceedings of the IEEE, 2003, vol. 91:1247~1256
[4]MIT Technology Review,“10 emerging areas of technology", Feb 2003, http://www.tech nologyreview.com
[5]Deployable Autonomous Distributed System, http://www.onr.navy.mil/sci tech/oc ean/ 321sensing/info _deploy.htm
[6]张晋,传感器网络的数据管理研究:[硕士学位论文],哈尔滨;哈尔滨工程大学,2006
[7]Pister K, Hohlt B, Jeong J et al., Ivy-A sensor network infrastructure, 2003, http://www-bsac.eecs.berkeley.edu/projects/ivy
[8]任丰原,黄海宁,林闯,无线传感器网络,软件学报,2003,14(7):1287~1291
[9]蒋鹏,基于无线传感器网络的湿地水环境远程实时监测系统关键技术研究,传感技术学报,2007,20(1):183~186
[10]孙利民,李建中,陈渝等,无线传感器网络,北京:清华大学出版社,2005,4~13
[11]J. Gao, L. J. Guibas, J. Hershberger, L. Zhang, Fractionally Cascaded Information in a Sensor Network, Proc. of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN'04), 2004,311~319
[12] S. Madden, W. I-long, TinyDB, http://telegraph.cs.berkeley.edu/tiny-db/.2003
[13]陈利虎,无线传感器网络实验平台的研究:[硕士学位论文],长沙;国防科学技术大学,2004
[14]Weisong Shi, Sellamuthu, S., Kewei Sha; Schwiebert, L., Query Agent: A General Query Processing Tool for Sensor Networks, Parallel Processing International Conference 2004, 15-18 :488~ 495
[15]Wei Yu, Thang Nam Le, Jangwon Lee and Dong Xuan, Effective Query Aggregation for Data Services in Sensor Networks, Computer Communications, November 2006, 29(18, 28): 3733~3744
[16]Sinha A, Chandrakasan A, Dynamic power management in wireless sensor network, IEEE Design and Test of Computer, 2001, 18(2): 62~74
[17]Ph. Bonnet, P.Seshadri, Device Database Systems, Proceedings of the International Conference on Data Engineering ICDE’99, San Diego, CA, 2000
[18]Ph.Bonnet, J.Gehrke, P.Seshadri, Querying the Physical World, IEEE personal Communications, Special Issue“Networking the Physical World”,2000
[19]Kyungseo Park, R. Elmasri, Query Classification and Storage Evaluation in Wireless Sensor Networks, Proceedings of 22nd International Conference on Data Engineering Workshops, 2006
[20]陈丹,郑增威,李际军,无线传感器网络研究综述,计算机测量与控制,2004,12(8):701~704
[21]Zhanyang Zhang, Guping Zheng, A Cluster Based Query Protocol for Wireless Sensor Networks, the 8th International Conference Advanced Communication Technology, 2006, 140~145
[22]N. Trigoni, Y. Yao, A. Demers, ec al., Hybrid push-pull query processing for sensor networks, In Workshop on Sensor Networks in GI, 2004
[23]马祖长,孙怡宁,梅涛,无线传感器网络综述,通信学报,2004,25(4):114~123
[24]Bonnet P, Gehrke JE, Seshadri P,Towards sensor database systems, In Tan K-L, Franklin MJ, Lui JCS, eds, Proceedings of the 2nd International Conference on Mobile Data Management. Hong Kong: Springer-Verlag, 2001, 3~14
[25]Minji Wu, Jianliang Xu, Xueyan Tang, et al,Top-k Monitoring in Wireless Sensor Networks, IEEE Trans.. Data Eng. 2007, 19 (7): 962~976
[26]Zhibin Zhao,Lan Yao, Binyang Li .et al, Filter-based Approach for Optimizing Top-k Queries in Wireless Sensor, International Conference of ITS Telecommunications Proceedings , 2006
[27]Qunhua Pan, Minglu Li, Min-You ,History-sensitive Based Approach to Optimize Top-k Queries in Wireless Sensor Network, Lecture Notes in Computer Science,2006, 43(25):674~684
[28]Adam Silberstein Silberstein, Rebecca Braynard, Carla Ellis,et al.,A Sampling-Based Approach to Optimizing Top-k Queries in Sensor Networks,22nd International Conference on Data Engineering, 2006,68
[29]M. Demirbas, H. Ferhatosmanoglu, Peer-to-peer spatial queries in sensor networks, In Proc. of the 3rd IEEE International Conference on Peer-to-Peer Computing, 2003
[30]B. Karp, H.T. Kung, GPSR: Greedy perimeter stateless routing for wireless networks, In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, 2000, 243~254
[31]Julian Winter,Wang-Chien Lee,KPT: A Dynamic KNN Query Processing Algorithm for Location-aware Sensor Networks , Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB, 2004, 119~124
[32]刘灿,张德贤,KNN查询处理算法性能研究,,苏州科技学院学报(自然科学版),2006.9,23(3):73~77
[33]B. Wu, K. T. Chuang, C. M. Chen,.et al., DIKNN: An Itinerary-based KNN Query Processing Algorithm for Mobile Sensor Networks,In ICDE, 2007
[34]Tao-Young Fu,Wen-Chih Peng,Wang-Chien Lee,Optimizing Parallel Itineraries for KNN Query Processing in Wireless Sensor Networks,Association for Computing Machinery, 2007
[35]Y. Xu,T. Y. Fu,W. C. Lee,et al., Itinerary-based Techniques for Processing K Nearest Neighbor Queries in Location-aware Sensor Networks,Signal Processing, 2007
[36]Z. Song ,N. Roussopoulos,K -Nearest Neighbor Search for Moving Query Point, In International Symposium on Spatial and Temporal Databases, 2001, 79~96
[37]J. Winter, Y. Xu, and W. C. Lee,Energy Efficient Processing of K Nearest Neighbor Queries in Location-aware Sensor Networks,In Mobiquitous, 2005, 281~292
[38]吴亚珺,传感器网络数据查询处理技术研究:[硕士学位论文],哈尔滨;黑龙江大学,2006
[39]A.Demers, J.Gehrke, R. Rajaraman, .et al, the cougar project: A work-in-progress report, SIGMOD Record, 2003, 32(4)
[40] S. Madden and M. Franklin, "Fjording the Stream: AnArchitecture for Queries over Streaming Sensor Data", the 18th International Conference on Data Engineering, 2002
[41]N. Trigoni, Y. Yao, J. Gehrke.et al, Multi-queries optimization for sensor networks, In Proc.of DCOSS, 2005
[42]Shili Xiang, Hock BengLim, Kian-Lee Tan, Impact of Multi-queries Optimization in Sensor Networks, Proceedings of the 3rd workshop on Data management for sensor networks, 2006, 1:7~12
[43]Guohua Liu, Shuzhi Zhang, Dongming Zhang, Research on Multiple Queries Processing Technology in Wide Area Sensor Databases, International Conference on Computational Intelligence for Modelling Control and Automation,2006
[44]Shili Xiang, Hock Beng Lim, Kian-Lee Tan, et al, Two-Tier Multiple Query Optimization for Sensor Networks, 27th International Conference on Distributed Computing Systems ,2007
[45]S. Madden, M. J. Franklin, Fjording the stream: architecture for queries over streaming sensor data, In Proc. of ICDE, 2002
[46]张明宇,传感器网络上的近似查询处理:[硕士学位论文],黑龙江大学,2005
[47]谢磊,陈力军,陈道蓄,谢立,无线传感器网络的查询处理机制研究综述,计算机科学,2006,33(9):45~49,68
[48]李建中,李金宝,石胜飞,传感器网络及其数据管理的概念、问题与进展,软件学报,2003, 14(10):1717~1727
[49]A.Silberstein, R. Braynard, and J. Yang,Constraint Chaining: On energy-efficient continuous monitoring in sensor networks,In Proc. Of SIGMOD,2006
[50]F.-C. F. Chen, M. H. Dunham, Common subexpression processing in multiple-query processing, IEEE TKDE, 1998, 10(3):493~499
[51]Deployable Autonomous Distributed System, http://www.onr.navy.mil/sci tech/ocean/ 321 sensing/info _deploy.htm
[52]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, .et al,A survey on sensor networks,IEEE Communications Magazine, 2002,40(8):102~114
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |