Friday, August 16, 2013

Abstract - NoSQL Query Processing System for Wireless ad-hoc and Sensor Networks By Manula Thantriwatte & Chamath Keppetiyagama

Wireless Sensor Networks (WSN) are distributed systems typically composed of embedded devices, each equipped with a processing unit, a wireless communication interface, as well as sensors and/or actuators. Many applications have been implemented on sensor networks demonstrating the versatility of this technology, and some are already finding their way into the mainstream. Often, sensor nodes are tiny battery powered devices. Usually, these devices are capable of forming ad hoc wireless networks and communicate with each other.

Two main abstractions are available for developing applications for WSNs; message passing and SQL query interfaces. First exposes the network to the programmers and the second hides the complexity of the network with a database abstraction.  There are two popular query processing systems for wireless sensor network, namely TinyDB (for TinyOS) and TikiriDB (for Contiki). These query processing systems represent the sensors on the sensor network as a table. Users can insert queries at the base station, and it converts those queries into sensor node understandable format, and they are sent to sensor network to get the results.

Database abstractions currently used in WSN are based on Relational Database Management Systems (RDBMS). These relational models use ACID properties (atomicity, consistency, isolation, durability). TinyDB and TikiriDB use SQL queries.  However, a relational database model that guarantees ACID properties is not a good match for a wireless sensor network since consistent connectivity or the uninterrupted operation of the sensor nodes cannot be expected.

We noted that the NoSQL approach which does not rely on the ACID properties is a better match for a query processing systems for WASNs.  We developed a NoSQL based database abstraction on the Contiki operating system that is popular among the WSN community.

We designed NoSQL query syntaxes for querying sensor networks that are similar to the RedisDB NoSQL queries and we also adopted the RedisDB architecture for our implementation. We implemented the following NoSQL queries on Contiki.

  • Select Query: Appropriate keyword followed by relevant key
  • Join Query: Appropriate keyword followed by relevant key followed by valid set condition for key
  • Range Query: Appropriate keyword followed by relevant key followed by valid range condition
  • Ranking Data: Appropriate keyword followed by key and relevant member name
  • Get the key of members: Appropriate keyword followed by relevant key

We have implemented the Redis back-end in iterative manner. RedisDB supports different data structures such as Strings, Hashes, Lists, Sets and Sorted-sets. We prototyped the back-end using each of the above mentioned data structures and evaluated the performance.  Based on the experience gained through these prototypes, we decided to use Sorted-sets for the final implementation.

Sorted-set implementation of our NoSQL database abstraction works with two values called the key and the member. In this implementation we mapped sensing field of a query to a key and sensing values to members. According to these key and member values we can use following NoSQL queries in our database abstraction.

  • ZADD key score member: Add a member to a Sorted-set, or update its score if it already exists.
  • ZCARD key: Get the number of members in a Sorted-set.
  • ZCOUNT key min max: Count the members in a Sorted-set with scores within the given values.
  • ZINCRBY key increment member: Increment the score of a member in a Sorted-set. 
  • ZINTERSTORE destination numkeys key [key ...]: Intersect multiple Sorted-sets and store the resulting Sorted-set in a new key.

In performance analysis we analyzed the query execution time of TikiriDB database abstraction and our newly designed NoSQL database abstraction. We collected the execution times of queries by changing the sample period of both SQL and NoSQL queries. Then we observed that for a shorter time periods, both database abstractions show the same performances, but when the time period increases, performances of NoSQL database abstraction get better. The reason for that performance bottleneck in SQL database abstraction is the processing time of SQL queries. According to above results we can conclude that processing NoSQL queries are much more efficient than processing SQL queries in sensor networks. 

Also we measured the power required to process the NoSQL queries as well as the SQL queries. Our implementation consumes less power than the SQL based query processing system on Contiki. This is important since sensor nodes are usually energy constrained and an efficient query processing system helps to conserve energy.


No comments:

Post a Comment