Wireless Sensor Network Queries Processor A survey

Wireless Sensor Network Queries Processor A survey Karim FATHALLAH and Ali FRIHIDA Cognition and Ontology of GeoSpatial Systems (CONTOS²) National Engineering School of Tunis, Tunis El Manar University – TUNISIA [email protected],[email protected]

Nejib BEN HADJ-ALOUANE National Engineering School of Tunis, Tunis El Manar University – TUNISIA [email protected]

of sensor networks to greatly simplify the development of applications over such networks. Abstract— Recently, wireless sensor network (WSN) research community has proposed to model WSN as a distributed database. This enables users to interrogate the WSNs through simple SQL like queries. First, this approach significantly reduces the development and implementation cost of the system. Furthermore, various demonstrations have been quickly reported, showed that this approach performs substantial energy saving. These particular database systems are frequently referred as sensor network query processing systems (SNQP). During the last years, various flavors of SNQPs have been introduced and investigated. However, none of them completely answers to the capital performance requirements including spatial and temporal data management. In this paper, we present a survey of key state of art of SNQP systems existing in the literature, analyze their key characteristics and discuss their drawbacks and challenges. Open related issues of research are also summarized. KEYWORDS-wireless sensor network, sensorDB, sensor network query processor.

I.

INTRODUCTION

The purpose of this paper is to explore different projects relevant for WSN SNQP then provide a list of actives and challenging research axis.The rest of the paper is structured as follows: Section 2 gives an overview of the architecture of SNQP. Section 3 is dedicated to the description of SNQP current projects and approaches and the most representative undertaken from this perspective, section 4 is devoted to propose a list of the challenging research thematic. Then end with the conclusion of the paper. II.

OVERVIEW OF SENSOR NETWORK QUERY PROCESSOR (SNQP)

A. Problems raised by an SNQP Sensor networks provide an environment requiring computer programming: the devices are small and vulnerable, debugging applications is via some diodes, are excessively distributed programs and must carefully manage energy while sharing bandwidth between information and processing.

The advancement of computer technology and electronics has enabled the emergence of wireless sensor networks (WSN), offering an unprecedented opportunity for a wide range of realtime applications. These tiny sensor nodes are low cost, low power and easy deployable. When they are combined together, they offer many advantages over traditional networks. Due to their tight integration with the physical world and their unique characteristics, sensor networks typically pose significant constraints and make application development a difficult task. A sensor node must detect process and communicate data whenever it is used with minimal resources. This implies the need for a new programming paradigm and new operating systems that perform all tasks efficiently.

Because of these limitations, the data collection systems in WSN should take into account a series of unusual software requirements. For example:

A Sensor Network Query Processor (SNQP)[1], also so called sensorDB, is a user-friendly interface for programming and running applications translates instructions from declarative programming language with high-level instructions to low-level instructions understood by the operating system. Indeed, the basic idea of SNQP is the addition of a layer modeling the WSN as a distributed database searchable by a query language similar to SQL. These systems fully meet the various challenges of designing and implementing technology

Optimized interface to make its use significantly simpler than the direct use of the operating system.

Optimal management of resources including energy. Communications and sensing tend to dominate consumption. Management of the transitory nature of sensor networks, the signal strength varies depending on the battery charge, but the data collection must be uninterrupted. Display and storage of the data collected.

Provide the user with the tools necessary to manage and understand the status of the sensor network deployed.

B.

General architecture of an SNQP A general architecture [2] for executing the queries in sensor networks is showed in Figure 1. The architecture consists of two main parts: The server side software: running on the user pc (base station). In its most basic form, the software interprets queries, delivers them in the network, and collects the results posted on the network. Node-side: The software behaves like a distributed query processing. This software consists of several modules built on top of the nodes operating system.

Figure2. User Query interface[7]

Figure 1. Structure of an SNQP

C. Users queries in SNQP In this architecture, the user enters queries at the server in the form of a variant of SQL commands that refers to the data to be collected, how they will be combined and presented (Figure 2). This variant is SQL profoundly different from the SQL standard that the execution of these queries is continuous in time. In practice, the user requests more information on some reports by writing predefined conditions (e.g. temperature in the greenhouse # 3 every 10 seconds for 1 hour) and the system returns the result in accordance with those conditions. Each time when the result is produced is called an epoch. The duration of a time period or sampling a query, denotes the time between two successive samples (10 seconds).

D. Query optimization in SNQP As in traditional DBMS, queries describe a logical set of data which the user is interested, but do not describe the algorithm that will be executed to retrieve the data [3]. Typically, the system can choose between different execution plans for any query. For example, to find the average temperature in the fifth greenhouse, the system will collect data from all the sensors, then filtering the sensed data of the greenhouse number 5 in order to calculate the desired average. Alternatively, one can retrieve the temperatures of the nodes of the 5th greenhouse. It is therefore quite clear that the plan will be more optimized. The process of selecting the best plan is called query optimization. E. Query languages in SNQP As in SQL, the query in SNQP is a select-from-wheregroup by blocks support for join operations, selection, aggregation and grouping (see Table 1). SNQP generally allow the modeling of sensor data as a single virtual table. The system continuously added to this table tuples with each sample transmitted by the network. For example, the query (select nodeid, light, temp from sensors sample period 1s for 10s) specifies that each node must return its own parameters: identifier (nodeid), brightness (light), temperature (temp) read once per second, for 10 seconds. The virtual table "sensors" combines a column for each attribute and one line for every possible instance in time.

Operator

Description Acquire a reading (field) from a sensor or an internal device attribute, such as a light sensor reading or free RAM in the dynamic heap.

Data acquisition

Select

Reject readings that don’t satisfy a particular Boolean predicate. For example, the predicate temp > 80°F rejects readings under 80°F.

Aggregate

Combine readings according to an aggregation function. For example, AVG(light) computes the average light value over each mote.

Join

Concatenate two readings when some join predicate is satisfied.

TABLE I.

III.

SENSOR NETWORK QUERY-PROCESSING OPERATORS.

DIFERENT SENSOR NETWORK QUERY PROCESSOR

A. Cougar In early 2000, a research group at Cornell University Introduced a new dimension in middleware research by adopting a database approach where sensor data are considered like a “virtual” relational database and WSN management operations are implemented in forms of queries using an SQL like language. Cougar [4] defines a sensor data base system composed of sensor database and sensor queries. The sensor database in its turn contains stored data and sensor data. The stored data are represented as relations and they include the set of sensors that participate in the sensor database together with characteristics of the sensors or the physical environment. The sensor data are represented as time series to facilitate the formulation of sensor queries. Cougar then, uses Abstract Data Types (ADT) with virtual relations to model sequences. All sensors of the same type are represented by the same ADT. With algebra operators, the sensor queries are formulated in form of SQL likely language. The long running queries are supported by using incremental results to maintain a persistent view of such queries. The cougar database approach is very suitable for large sensor collections, and offers a simple implementation for different network operations. However, it uses valuable resources to transfer large amount of raw data from devices to the database server and there is a potential risk for communication links failure in case of a large scale sensor network. Also the dynamic nature of large-scale sensor networks poses a problem for the centralized optimizer that Cougar uses to maintain a global knowledge of the network.

B. SINA SINA, System Information Networking Architecture [5], developed at the University of Delaware. For the purpose of achieving adaptive sensor network organization SINA models the network as massively distributed objects. Its kernel provides efficient mechanisms enabling scalability, and energy efficiency. Its architecture backbone is based on a spreadsheet database for querying and monitoring. A logical datasheet composed of cells, where each cell represents an attribute of a sensor node (e.g. in the form of a single value such as power level and location or multiple values such as temperature changes history). Each cell is namely unique and the whole datasheet is maintained by each sensor node. The sensor network as a whole is viewed as a collection of datasheets. The spreadsheet approach is the abstraction that allows information management to meet application changes and needs. SINA then incorporates two robust mechanisms: hierarchical clustering allowing scalability and an attribute – based naming scheme based on an associative broadcast to manage the spreadsheets. The cells are initiated in a node by a request from other nodes (e.g. user or cluster head). The requests are made in a form of SQL like statement. The cells are maintained and updated by four possible approaches namely, on demand content retrieval, content coaching, periodic content update and triggered content update. SINA offers an advantage over Cougar by incorporating low-level mechanisms such as hierarchical clustering of sensors for efficient data aggregation. However as cougar it does not address the distributed systems heterogeneity. C. DsWare DsWare, Data service Middleware [6] is another database like abstraction approach that is tailored to sensor networks based on event detection. It provides more flexibility by supporting group – based decision, reliable data-centric storage, and implementing a mix of approaches to improve real-time execution performance, reliability of aggregated results and reduce network communication (overhead). DsWare provides application with services supported by its architecture modules such as data storage, data caching, group management, event detection, data subscription, and scheduling. DsWare uses SQL like language for the registration and cancellation of events. DsWare supplies applications with a very rich and convenient interface so that applications do not have to implement their own application data-service. It allows sensor data to be represented using interfaces as conventional databases. It handles the dynamic nature of sensor network data and provides more reliability since services could be provided by a group of geographically close sensor nodes; hence it can easily tackle failures as long as enough sensors remain in the area to provide valid measurements. In the other hand, DsWare, in its present form does not provide solutions for heterogeneity and mobility. D. TinyDB In the early of 2003, TinyDB [7] was created by TelegraphCQ database laboratory at the Berkley University.

TinyDB is the declarative database abstraction for TinyOS [8] operating system. TinyDB provides a simple SQL query interface. TinyDB architecture provides the sensor network user with a database file called 'sensor' which stores the sensor data values collected from the sensor network. TinyDB uses a resources dedicated algorithm to collect data [1]. TinyDB monitors a query processor running on each network node. Queries may be submitted to the nodes from the base station where they are optimized for power economy reasons. Along with the traditional query features provided by SQL, TinyDB adopts Acquisitional Query Processing (ACQP). The ACOP system determines where and in what order the data should be collected to minimize the energy consumption and to improve data accuracy. Finally, user can specify the sample period of a query as a query parameter and submit queries like eventbased, grouped aggregation and actuation queries. E. SwissQM SwissQM[8], is an acronym for Scalable Wireless Sensor Query Machine. It was developed at the Department of Computer Science at ETH Zurich. It offers an enhanced functionality at the sensor network level, an adjustable interface, data and query language independence, optimized performance with a rich set of modifiable settings. and seamless integration with data processing functions. SwissQM uses a dedicated virtual machine that runs optimized byte code queries rather than SQL scripts and integrates TinyOS library. SwissQM supplies an remarkable multi-user support, a generic high-level, declarative programming model and it deals efficiently with different data models (relational, XML etc.). It admits user defined functions, window queries, complex event generation at the sensor level, an flexible instruction set, and a sophisticated optimizations routines. This makes SwissQM highly customizable without reducing its overall performance. F. SNEE The Sensor Network Engine (SNEE) [9], was developed in Manchester University. It presents a novel sensor network query processing architecture that has breakthroughs in three main respects: 1) coverage of the query optimization phases that transform declarative query into executable code, 2) usage a more expressive programming language and 3) acccess to nodes and data even over heterogeneous sensor networks. SNEE architecture is based on the view that a sensor network is a distributed computing infrastructure, in a very constrained one. It also employs an optimizer that receives metadata information about the available resources (e.g., memory, energy), the WSN topology and also predictive cost models. Thus optimizer extended the two-phase optimization approach from Distributed Query Processing, which comprises a single site phase, and a subsequent multi-site phase (figure 3).

Figure3. SNEE optimizer[9]

SNEE combines a rich, expressive query language, named SNEEQL, which provides extensive support for JOIN operators incorporating techniques found on classical Distributed queries processing architectures. Furthermore, SNEE reduces power consumption by supporting workload balancing by scheduling different workloads to different sites. To achieve this goal, the underlying network infrastructure should employ an optimized protocol for topology selforganization. G. TikiriDB TikiriDB [10] is a sensor network query processor for Contiki operating system. TikiriDB provides an SQL query interface called TikiriSQL to query the sensor network [3]. It is much more similar to conventional query language apart from additional syntax to comply with sensor network environment. As example of TikiriSQL query: SELECT temp, humid FROM sensors SAMPLE PERIOD 2 FOR 10; This query returns node id, humidity level, and temperature level in every 2 second intervals for duration of 10 seconds from all the available sensors nodes in the sensor network. The results appended to the table as they are arriving to the user. Thus, the resulting table dynamically expands according to time. The client side functionalities of the TikiriDB is included in the TikiriSQL library and used by a user program. It provides functions to issue SQL queries by the user program, parses the queries and sends them to the Serial Forwarder (SF). TikiriSQL library returns data to the user program which is received from the SF. Their main tasks are: Accept queries from the user program, Parse the query and put it to a manageable format, If there are any syntactic and semantic errors, it returns warnings to the user,

If no errors, send this new formatted query to the serial forwarder, Returns the query 10 returned from the SF to the user program, Put the data received from the SF to data structures and make it available to the user for manipulation. H. Corona Corona [11] is a distributed query processor for the SunSPOT Wireless Sensor Network platform, developed at the School of IT at the University of Sydney, Australia. It has been conceived with energy conservation issues in mind. It offers the following features: Tree topology query arrangement: This permits innetwork results aggregation at the tree levels and discarding of irrelevant data thus minimizing transmission costs. Time-synchronized network nodes : if a query is supposed to run multiple time, it is sent to the node only once along with its estimated run time and run count. A Remote Method Invocation (RMI) interface: this is a rapid application development environment permits the use of the Corona query engine over a network or the web. A persistence facility: query results can be stored and retrieved on request. A GUI is provided in order to interact with the query engine. This includes a visual query builder and a results visual display tool. IV.

CHALLENGE AND ACTIVE RESEARCH AREA

A. Bridging the gap with the web of things The web of things [12] is vision were everyday embedded device and computers are connected by fully integrating them to the web. In other word, the web of thing is about reusing the web standard to connect smart devices like sensor nodes. To enable this connection the Open Geospatial Consortium proposed several services, models and standrads called sensor web enablement (SWE)[13]. In SWE standards, the sensor data must be encoded in XML format in conformity with O&M schema[13] . This representation enables an easy integration of sensor data with other OGC services like WMS (Web Map Service) and WFS (Web Feature Service) [13]. In fact, the main goals of SWE standards is to insure the interoperability between heterogeneous sensors networks and to permit an easy publication of sensor data in a spatial data infrastructure like a WebGIS. Although many sensor WSN projects has implemented the SWE standards., none of the sensor network queries processor offers compatibility with SWE model and services. We believe that providing support to the SWE standards will be one of the most interesting research areas in the nearly future.

B. Power consumption optimization: As we mentioned in the beginning of this paper minimizing the power consumption is one of the early objective of developing sensor network query processor. Firstly, it is important to note that many researches have demonstrated that communication is the principle source of power consumption in wireless sensor network. So the guideline of the different approach presented below is based in minimizing the number of message transmission in the network. Ross Rosemark et al [14] presented a new query optimizer. Central to the working of this query optimizer is a cost-based analysis to estimate the overall energy consumption associated with a given query plan over the lifetime of a query. By utilizing this estimation technique, this query optimizer compares the desirability of several candidate plans for a given query and chooses a plan that is likely to utilize the least energy for execution. Mohamed Watfa et al [15] presented another approach based on building an index tree that enabling to query the data with the minimum of exchanged packet. Although the multitude of projects in this domain, we believe that this thematic continuous to be one the interesting research subjects. C. Heterogeneity One problematic question with the SNQP is to deal with heterogeneous WSN. In fact, most sensor query processor proposed as yet lack the support of application that simultaneous connects to heterogeneous sensor network. Actually very little advancement in the domain has been released. Minsoo kim et al [16] propose a specific query types that may support multiple and heterogeneous sensor network simultaneously. Then they developed a new SNQP called SIMC (sensor information management component) to support such query type. Although the authors reclamations of efficiency of the SIMC systems none indications about the supported motes and WSN operating systems. D. Historical and temporal queries Most existing applications just process real-time data generated by sensor networks. However, historical data of sensor networks are also important for us. For example, by capturing rush hours and the bottleneck of transportation traffic data according to time axis, useful information can be provided to improve traffic conditions. By applying knowledge discovery and data mining routines to historical data, some hidden principles, properties and spatio-temporal patterns can be unveiled. But, storing large volume of data raises the memory issues. In order to deal with this problem, Libellium Corporation [18] has proposed new nodes (waspmotes) equipped with 2Go of flash memory. Although the importance of the information that can be retrieved from historical query over sensor network we found only one paper that discussed this issue. Chunyu Ai et al [17] proposed an Index based Historical Data Query Processing schemata. This schemata stores time series data locally and runs energy-efficiency queries using a distributed index tree. The simulation study shows that this approach achieves good performance on both query responding delay and network traffic.

E. Spatial queries Wireless Sensor network can be embedded in a variety of environments, such as high-rise building, airport, highway stretches, or even the ocean. Unlike traditional database application where spatial considerations are often irrelevant (expect as expressed by traditional attributes such as address or zip code),most applications of sensor network, in such diverse fields as security, civil engineering, environmental engineering, or precision agriculture will involve queries over spatial data. Spatial queries are used to answer question such:

REFERENCES [1] [2] [3] [4]

Find the average temperature in a given area

[5]

Count the number of sensors within five miles of a point of interest

[6]

Find the maximum vehicle speed on road x

[7]

Find average humidity within 5 miles of lake y Identify parcel where irrigation is required As demonstrated by previous examples the ability to run spatial queries is extremely useful for wireless sensor networks. Spatial query execution has been extensively studied in the context of centralized spatial databases; however very few projects dealing with spatial issues over sensor network. Dina Godin et al [19] discussed the challenge of spatial querying over sensors networks, focusing on three issues: dynamic spatial data, centralized vs localized evaluation, and spatial data redundancy. Mehdi Sharifzadeh et Al [20] introduce “spatial aggregation” that takes into consideration the distribution of the value generated by sensor node. They propose the using of spatial interpolation methods derived from fields of spatial statistics and computational geometry to answer spatial aggregation. In particular, they studied spatial moving average (sma), vornoï diagram and triangulated irregular network (TIN). As contribution they introduced an incremental algorithm to compute and maintain the vornoï cell at sensor node. Palino Di Felice et Al [21] developed a spatial extension to tinyDB sensor network query processor system. This extension are suitable to manage the location of sensors nodes and, hence able to process besides standard queries, spatial queries as well. Latter extension supports three spatial operators (DISTANCE, INBOX and BEYONDBOUNDARY). We believe that spatial querying will be one of the most active areas in the research about sensor network queries systems.

[8]

[9]

[10]

[11]

[12]

[13] [14]

[15] [16]

[17]

V.

CONCLUSION

The paper focuses sensor networks queries processor systems also so called sensorDB. The approach is very promising given the facilities it offers in the use of sensor networks. We presented the typical architecture of an SNQP. A sensorDB selection was discussed by evaluating the positive and negative points of each system. This led us point out research questions still open as support for spatial and temporal queries, management of heterogeneity and interoperability. ACKNOWLEDGMENT This research is funded by the Canadian International Development Research Center (IDRC/Enda Lead Africa).

[18] [19] [20]

[21]

L. AL-Jadir, “Sensor Network Databases - An Introduction,” Advanced Research Topics in Databases Summer 2004-2005. J. Gehrke, S. Madden, Query processing in sensor networks, pervasive computing, January, 2004 R. Govindan, J. Hellerstein, W. Hong, S. Madden, M. Franklin, S. Shenker, The Sensor Network as a Database , 2002 Y Yao, J E Gehrke, The cougar approach to in-network query processing in sensor networks, Proceedings of ACM SIGMOD, 2002. C. Srisathapornphat, C. Jaikaeo and C. Shen “Sensor Information Networking Architecture”. International Workshop on Parallel Processing, September 2000. X. Yu, K. Niyogi, S. Mehrotra and N.Venkatasubramanian, Adaptive Middleware for Distributed Sensor Environments. IEEE Computer Society, 2003. S. Madden, Michael J. Franklin, Joseph M. Hellerstein, Wei Hong , The Design of an Acquisitional Query Processor for Sensor Networks, Proceedings of ACM SIGMOD , 2002 R. Müller, Gustavo Alonso, Donald Kossmann, SwissQM: Next Generation Data Processing in Sensor Networks, Proceedings of the Third Biennial Conference on Innovative Data Systems Research (CIDR 2007) X. Galpin , Christian Y. A. Brenninkmeijer , Alvaro A. A. Fern , Es Norman W. Paton, SNEE: A Query Processor for Wireless Sensor Networks, Distributed and Parallel Databases manuscript, 2010. A. P. Sayakkara, W. S. N. Prabath Senanayake, Kasun Hewage , Nayanajith M. Laxaman , Kasun De Zoysa, The deployment of TikiriDB for monitoring palm sap production, Proceedings of the 4th international conference on Real-world wireless sensor networks,2010 R. Khoury, Tim Dawborn, Bulat Gafurov, Glen Pink, Edmund Tse, Quincy Tse, K. Almi’Ani, Mohamed Gaber, Uwe R¨ohm, and Bernhard Scholz, Corona: Energy-Efficient Multi-query Processing in Wireless Sensor Networks, International Conference on Database Systems for Advanced Applications, 2010 Alexandra Moraru, Dunja Mladenic, Matevz Vucnik, Maria Porcius, Carolina Fortuna, Mihael Mohorcic, Exposing Real World Information for the Web of Things, Proceedings of the 8th International Workshop on Information Integration on the Web,2011 Open Geospatial Consortium, www.opengeospatial.org/ , 2012 Ross Rosemark , Wang-Chien Lee, Bhuvan Urgaonkar, Optimizing energy-efficient query processing in wireless sensor networks, Proceedings of Mobile Data Management, 2007 Watfa, M., Daher, W. & Al Azar, An energy aware sensor network query processing system, Info Comp, 2009 Minsoo Kim, Chungho lee, youngjun lee, towards query processor over heterogeneous wireless sensor networks, international conference on convergence information technology,2007 Chunyu Ai, Ruiying Du, Minghong Zhang, Yingshu Li, Innetwork Historical Data Storage and QueryProcessing Based on Distributed Indexing Techniques in Wireless Sensor Networks , Wireless Algorithms, Systems, and Applications Lecture Notes in Computer Science ,2009 Libelium corporation,http://www.libelium.com/,2012 Dina Goldin, Spatial Queries over Sensor Networks, University of Connecticut, 2003 Mehdi Sharifzadeh and Cyrus Shahabi, Supporting spatial aggregation in sensor network databases, Proceedings of the 12th annual ACM international workshop on Geographic information systems,2004 Paolino Di Felice, Massimo Ianni, Luigi Pomante, A spatial extension of TinyDB for wireless sensor networks, IEEE Symposium on Computers and Communications, 2008.