Nosql Database Abstraction For Wireless Ad Hoc Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The main target of this NoSQL database abstraction is giving, NoSQL query interface to TikiriDB. Currently TikiriDB and other database abstractions used SQL query interface and those database abstractions are using relational database management system techniques. In problem section we mentioned that the problems relevant to the current database abstractions and we propose novel database abstraction call 'NoSQL database abstraction for Wireless Ad-Hoc and Sensor Networks'.\\

\newline

In this chapter we discuss about the background of the project and it catogorize to following sections.

\begin{itemize}

\item Operating Systems in Sensor Networks

\item Data Gathering Techniques in Sensor Networks

\item Database Abstraction in Wireless Ad-Hoc and Sensor Networks

\item NoSQL

\item Data Storing Techniques in NoSQL Databases

\end {itemize}

\subsection{Operating Systems in Sensor Networks}

\subsubsection{TinyOS}

TinyOS is the popular operating system which has been design for operate Wireless Sensor Networks. TinyOS has been implemented using NesC language which is the extended of C language. The design principles of TinyOS are motivated by basically four factors. Those are,

\begin{itemize}

\item Resource constrained

\item Reactive concurrency

\item Flexibility

\item Low power constrained

\end{itemize}

TinyOS has simulator called TOSSIM. Using this simulator programmer can easily develop sensor network applications and run in the simulated environment.

\subsubsection{Contiki}

Contiki is another well known sensor network operating system which is developed by Swedish Institute of Computer Systems in 2002. Contiki is light weight operating system written by using C language. Contiki providing abstraction that is rich enough for successful development environment for the developers while staying within the limitation of the Wireless Sensor Networks. Pre-emptive multithreading feature is an important factor in Contiki. Multithreading is also implemented as a library which can be optionally linked with the application program. Considering about Contiki operating system it has following features.

\begin{itemize}

\item Multitasking Kernel

\item Protothreads

\item TCP/IP networking, including IPv6

\item Windowing system and GUI

\item Networked remote display using Virtual Network Computing

\item Simple telnet client

\end{itemize}

\newpage

\subsection{Data Gathering Techniques in Sensor Networks}

\subsubsection{Directed Diffusion}

Directed Diffusion (DD) is on one of the energy efficient routing protocol that have been used to rout among the sensor nodes and gather data \cite{Kumar}. Directed Diffusion routing algorithm basically consists of four elements. Those are,

\begin{itemize}

\item Interest

\item Data message

\item Gradient

\item Reinforcements

\end{itemize}

An important feature of DD is that interest and data propagation and aggregation are determined by localized interactions. Basically the DD algorithm works by sending interest packets and find best route to receive data \cite{Dargahi}. Read HAD, GEAR and E3D are the main algorithms used when designing Directed Diffusion routing algorithm.

\subsubsection*{Directed Diffusion Basic Algorithm}

Sink node send out its query whenever it wants to obtain some information from sensor nodes. This query is carried by interest packet. When a node receives an interest packet, the packet is cached and broadcast to other neighbors to ensure every node in the network will receive it. Propagation of interest packets also setup the gradient in the network for delivering data to the sink. Gradient is a reply link to a neighbor form which the interest was received. When a node matches an interest, it generates a sample sensed data, which is called exploratory data and sends individually to the neighbors from which the gradient established before. As these exploratory data reach the sink from some neighbors, several paths are established between sink and source \cite{Dargahi}.\\

\newline

The sink reinforces one of these paths by increasing the data rate in the interest packet. Usually this path is the one which has the least delay. Eventually only one path remains while other paths are torn down. Finally the real data will send from the source, following the selected path.

\begin{figure}[h!]

\centering

\includegraphics[width=0.65\textwidth]{Img/DDAlgorithm}

\caption{Directed Diffusion a) Interest Propagation b) Initial Gradient Setup c) Data Delivery Reinforcement Path}

\end{figure}

\newpage

When considering about DD algorithm some of the naming conventions are used to gather data from the sensor networks.\\

\begin{tabbing}

Ex: \= Naming in Vehicle Tracking Sensor Network \\

\> type = wheeled vehicle /* detect vehicle location */ \\

\> interval = 20 ms /* send events every 20 ms */ \\

\> duration = 10 seconds /* for the next 10 seconds */ \\

\> rect = [-100, 100, 200, 400] /* from sensors within rectangle */

\end{tabbing}

\begin{tabbing}

All \= the coordinates are in GPS based. Above query generates following sensor data in the sensor network. \\

\> type = wheeled vehicle /* type of vehicle seen */ \\

\> instance = truck /* instance of this type */ \\

\> location = [125, 220] /* node location */ \\

\> intensity = 0.6 /* signal amplitude measure */ \\

\> confidence = 0.85 /* confidence in the match */ \\

\> timestamp = 01:20:40 /* event generation time */

\end{tabbing}

Considering about DD algorithm and DD techniques mainly it works using the four elements mentioned at beginning of this section. Finally we can conclude those four elements in Directed Diffusion algorithm as,

\begin{figure}[h!]

\centering

\includegraphics[width=0.75\textwidth]{Img/DesignSpace}

\caption{Partial Design Space for Diffusion}

\end{figure}

\subsubsection{Efficient Hybrid Data Gathering Scheme}

Data gathering from time sensitive sensor network application is somewhat crucial task. Efficient hybrid data gathering scheme gives solution for that problem. Efficient hybrid data gathering scheme is a combination of clustering and shortest hop pairing of the sensor nodes. The cluster heads and the super leader are rotated every round for ensuring an evenly distributed energy consumption among all the nodes \cite{chakraborty}. Comparing with other data gathering techniques such as PEGASIS, BINARY, LBEERA and SHORT Hybrid data gathering scheme has best performances.\\

\newline

The key idea of HDS algorithm is, it divide the whole network into number of clusters as in LBEERA. Then applied the SHORT scheme for each and every cluster and adopts centralized algorithms. Basically HDS algorithm operates in three phases.

\begin{itemize}

\item Cluster and group formation phase

\item Leader and super leader selection phase

\item Data transmission phase

\end{itemize}

HDS algorithm implemented using nesC language and tested by using TOSSIM simulator. HDS makes a good harmony among network lifetime, energy costs and network throughput. It not only reduces the network lifetime but also guarantees the best energy-delay product \cite{chakraborty}.

\begin{figure}[h!]

\centering

\includegraphics[width=0.75\textwidth]{Img/Graph}

\caption{Comparison of Network Lifetime and Energy-Delay product vs Number of Nodes \cite{chakraborty}}

\end{figure}

\subsubsection{Power Aware Chain Routing Protocol}

Power aware chain routing protocol is a distributed routing protocol for gather data in sensor networks. The chain construction algorithm calculates the transmission cost based on optimal transmission power \cite{Pham2005}. PAC takes remaining energy level and power consumptions of the sensor nodes in the network and electing the leader node. Then the nodes consume energy more uniformly. PACs' performances are better when comparing the performances of other routing protocols such as PEGASIS and MTE.

\subsubsection{Modified Adaptive Huffman Algorithm}

In this technique sensor data is first compressed by using the modified Huffman algorithm and the number of transmissions by the sensor node is limited by approximating the sensor data at the sink using prediction algorithms \cite{Tharini2010}. To compare the efficiency of this novel approach authors used different prediction algorithms for comparison. Those prediction algorithms are,

\begin{itemize}

\item Single Point Predictor (SPP)

\item Simple Linear Extrapolation (SLE)

\item Even Linear Extrapolation (ELE)

\item Linear Prediction (LP)

\item Newton-Gregory Backward Difference Interpolation

\item Least Mean Square Algorithm (LMS) and Normalized Least Mean Square

\item Normalized LMS (NLMS) Algorithm

\item Algorithm (NLMS)

\end{itemize}

By using this modified adaptive Huffman algorithm, authors able to implement spatial correlation based clustering which can be used to schedule the sensor nodes in each cluster to transfer the data \cite{Tharini2010}. By using that when sensor nodes are not transmitting data, it can be put it to sleeping mode and then it increases the life time of the sensor network.

\newpage

\subsection{Database Abstraction in Wireless Ad-Hoc and Sensor Networks}

Considering about database abstraction in WSNs, currently there are several database abstraction available. TinyDB, TikiriDB, Cougar and Vector programming database abstractions are some of those database abstractions. In this section we are going to discuss about those database abstractions in sensor networks.

\subsubsection{TinyDB Database Abstraction}

TinyDB is the declarative database abstraction under the TinyOS operating system. TinyDB provides a simple SQL-Like 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 resource aware algorithm to collect data \cite{Programming}.\\

\newline

TinyDB

has a distributed query processor which running on each and every node in the sensor network. Users can submit their queries from the base station. Then the queries are optimized in the base station, because TinyDB uses power aware routing. After that the optimized query will send through the network using the power aware routing tree.\\

\newline

Acquisitional Query Processing (ACQP) is adopted for TinyDB along with the traditional query features provided by SQL \cite{Programming}. It determines where and what order of data should be collected to minimize the power usage of the network. At the same time TinyDB will increases the data accuracy also.\\

\newline

In TinyDB user can specify the sample period of a query as a query parameter. Many queries, like, event-based, grouped aggregation and actuation queries, provides useful services to sensor network applications. TinyDB also supports data logging and network health monitoring through special queries. Queries can be prioritized in TinyDB.\\

\newline

Ex: - TinyDB Sample Query\\

\textbf{SELECT COUNT(*) FROM sensors AS s, recentLight AS rl WHERE rl.nodeid=s.nodeid AND s.light$<$rl.light SAMPLE PERIOD 10s;}\cite{Madden2005}

\begin{figure}[h!]

\centering

\includegraphics[width=0.65\textwidth]{Img/QueryResult}

\caption{A Query and the Result Propagating Through the Network \cite{Madden2005}}

\end{figure}

\newpage

\subsubsection{TikiriDB Database Abstraction}

TikiriDB is another well known database abstraction for Wireless Ad-Hoc and Sensor Networks. TikiriDB is the database abstraction layer for Contiki operating system. TikiriDB is developed by University of Colombo School of Computing. When comparing TikiriDB with TinyDB, TikiriDB support shared WSNs with respect to TinyDB.\\

\newline

TikiriDB also provide SQL-Like query interface called TikiriSQL to querying the sensor network\cite{Laxaman}. It is more similar to conventional query language with additional syntax to comply with sensor network environment.\\

\newline

Ex: - TikiriDB Query \\

\textbf{SELECT temp, humid FROM sensors SAMPLE PERIOD 2 FOR 10;}\\

\newline

This query returns node id, humidity level, and temperature level in every 2 seconds intervals for duration of 10 seconds from all the available sensors nodes in the sensor network. The result of this query has been illustrated in Figure 4. The resulting table is dynamically expanding according to the time and results will be appended to the end of the table as they are arrived to the user. That is, the result set is automatically sorted by time\cite{Laxaman}.

\begin{figure}[h!]

\centering

\includegraphics[width=0.75\textwidth]{Img/Results}

\caption{TikiriDB Query Result}

\end{figure}

\newpage

\subsubsection*{TikiriDB Internal Architecture}

TikiriDB architecture basically consists of three main elements. Those are,

\begin{itemize}

\item Client with TikiriSQL library

\item Serial Forwarder

\item Application in Motes

\end{itemize}

\subsubsection*{Client with TikiriSQL library}

The client side functionalities of the TikiriDB is included in the TikiriSQL library and used by a user program. It gives functions to issue SQL queries by the user program, parse the queries and send them to the Serial Forwarder (SF). TikiriSQL library returns data to the user program which is received from the SF. Its' main tasks are,

\begin{itemize}

\item Accept queries from the user program

\item Parse the query and put it to a manageable format

\item If there are any syntax and semantic errors, it returns warnings to the user

\end{itemize}

The possible semantic errors may be SELECT queries with undefined field names, EVENT queries with undefined event names, like wise. All the available field names and event names are kept in an XML configuration file.

\begin{itemize}

\item If no errors, send this new formatted query to the serial forwarder

\item Returns the query ID returned from the SF to the user program

\item This query ID can be used to issue a STOP query to stop executing a query identified by the query ID

\item Put the data received from the SF to some data structure and make it available to the user for manipulation

\end{itemize}

\subsubsection*{Serial Forwarder (SF)}

Serial Forwarder basically does the query and data exchanging job between the sensor motes and the clients who have sent the queries. It also keeps the track of which data should go to which client like ID mappings.

\begin{itemize}

\item Receives queries from clients who use TikiriSQL library

\item Send a unique query ID to the client

\item Store the query ID and the client ID mapping in a table or somewhere

\item Send the query to the sensor network with the query ID and ID for the SF

\item When data arrives from the sensor network, they are associated with query ID. So, SF searches for the client ID in the table who is the author of the query. When it finds the client ID, it sends data to that particular client

\end{itemize}

\subsubsection*{Application in Motes}

A particular scenario can be like this. A client which is identified by the client ID as CL1 is given a SELECT query by the user program to the TikiriSQL library (The user program is a program which calls the functions of TikiriSQL library). TikiriSQL library functions parse the query, returns errors if any to the calling program. Otherwise it sends the parsed query to the SF. Serial forwarder which is identified by SF1 receives the query and put the client's id which is CL1 in a table. It assigns a unique query id which is Q1 with the CL1 in the table.\\

\begin{center}

\begin{tabular}{|l|l|}

\hline client id & query id \\

\hline CL1 & Q1 \\

\hline

\end{tabular}

\end{center}

SF returns the Q1 to the client which sent the query. So, the client keeps the query id which is Q1 for further references like sending STOP queries. Then SF sends the query to the sensor network with CL1 and SF1. When some data returns to the SF from the sensor network, those data are coming with the associated query id. Therefore SF search in it is table for the owner of the query. If the data are received with the query id as Q1, it will find the owner as CL1. So, the serial forwarder sends the data results to the client who is identified by the client id CL1. The TikiriSQL library in the client program receives the data and makes them available to the client program for manipulation.

\subsubsection{Cougar Database Abstraction}

Cougar is another well known approach to In-Network query processing in sensor networks. It supports a platform for testing query processing techniques over ad-hoc sensor networks. Mainly Cougar has three-tier architecture. It consists of,

\begin{itemize}

\item The query proxy

\item The front-end components

\item A graphical user interface

\end{itemize}

Cougar database abstraction mainly designs for In-Network query processing. In-network processing can reduce energy consumption and improve sensor network lifetime significantly compared to traditional centralized data extraction and analysis. Thus one of the main roles of the query proxy when processing user queries is to perform in-network processing\cite{Yao2002}.

\subsubsection{Vector Programming Database Abstraction}

Vector Programming database abstraction is a novel database abstraction for wireless ad-hoc and sensor networks. It was designed by the Computer Science Department of University of Virginia. Vector Programming database abstraction was designed to support multiprocessor programming problem related to macro-programming in sensor networks.\\

\newline

In this Vector Programming approach they used special kind of a vector called a distributed vector. A distributed vector is a vector whose elements are unsorted. The elements of a distributed vector are called distributed elements and are composed of an index and a value\cite{Sookoor2011}.\\

\newline

This novel database abstraction make programming sensor networks much easier while retaining run time efficiency. This abstraction would help move sensor networks from the labs of sensor network researchers into the hands of application are a specialists such as environ-mentalists since many people are familiar with Matlab-like vector programming and thus would find it easy to program sensor network applications using the vector programming abstraction.

\newpage

\subsection{NoSQL}

NoSQL means Not Only SQL. The concept of NoSQL starts from 1998. NoSQL databases are differing from Relational Database Management Systems (RDBMS). Considering on RDBMS, those databases are design for guarantee ACID properties. But NoSQL databases did not guarantee ACID properties. They basically design for the performances and scalability. Normally NoSQL databases are suitable for large set of data.\\

\newline

When working with large set of data using a table based database systems, it needs lot of resources to store such massive data and the operations are time consuming. With regards to NoSQL databases handle massive amount of data is much easier, and the performances are very fast when comparing RDBMS. The only limitation of NoSQL is the memory and the processing speed. NoSQL database systems uses key, value pair to store data so, if you want to keep your data in a persistent state and have access to them, then this would be an ideal database system.\\

\newline

Currently there are several NoSQL database management systems available. Facebook's Cassandra, LinkedIn's Project Voldemort, Google's BigTable and Amazon's Dynamo are some of them. Chordless, CouchDB, Db4o, GT.M, Hbase, Hypertable, Memcachedb, Mnesia, MongoDB and Redis are some popular open source NoSQL projects as well. In this section we are going to talk about,

\begin{itemize}

\item Types of NoSQL databases

\item Features of RedisDB, Cassandra and CouchDB

\item Advantages of NoSQL

\end{itemize}

\begin{figure}[h!]

\centering

\includegraphics[width=1\textwidth]{Img/NoSQL}

\caption{NoSQL vs RDBMS}

\end{figure}

\newpage

\subsubsection{Types of NoSQL Database}

\subsubsection*{Key-Value Store}

A key-value store NoSQL databases maintains data as a pair consisting of an indexed key and a value. Generally, key-value store works with a single operation. It fetches a single value using its key. Following are some examples to key-value store databases.

\begin{itemize}

\item Redis

\item Cassandra

\item Project Voldemort

\item BerkeleyDB

\end{itemize}

\subsubsection*{Document-based Databases}

Document-based databases are also based on key-value store concept. But it has advanced feature set on top of the core KV storages. Document-based databases have following features,

\begin{itemize}

\item Semi structured data

\item Collections

\item Ad-hoc queries

\item Secondary indexes

\item Views and aggregation

\end{itemize}

\subsubsection*{Implementation Specific Features in Document-based Databases}

\begin{itemize}

\item In-place document editing

\item Persistent views

\item Multi-version concurrency control (MVCC)

\item Advanced conflict resolution

\item Configurable consistency/redundancy options

\item Simple references

\end{itemize}

\subsubsection*{Popular Document-based Databases}

\begin{itemize}

\item Software

\begin{itemize}

\item Apache Couch DB (Erlang)

\item Mongo DB (C++)

\item Fleet DB (Clojure)

\item Riak (C and Erlang)

\item Raven (.NET, Supports LINQ)

\end{itemize}

\item Database as a Service (DaaS)

\begin{itemize}

\item Amazon SimpleDB (Erlang)

\item Cloudant - Hosted Couch DB

\item Mongo HQ - Hosted Mongo DB

\end{itemize}

\end{itemize}

\subsubsection*{Column-oriented Databases}

The column-oriented databases stores data in column oriented way. This will optimizes the SQL databases by increasing disk performances and doing data aggregation easier. Google's Big Table, Hypertable, Facebook's Cassandra are some of example for column-oriented databases.

\begin{figure}[h!]

\centering

\includegraphics[width=0.75\textwidth]{Img/DataSize}

\caption{Data Size vs Data Complexity}

\end{figure}

\newpage

\subsubsection{RedisDB}

RedisDB is a light weight NoSQL database which is implemented by using C language. Redis stores data as a Key-Value pair and it provides richer API then something like Tokyo Cabinet\cite{Seeger2009}. Redis doing their operations in memory and periodically flushing results to disk. Redis values are always strings. Redis use lists, sets and ordered sets to store data. All this data types can be manipulated with atomic operations to push/pop elements, add/remove elements, perform server side union, intersection, difference between sets, and so forth. Also Redis support different kind of sorting capabilities.\\

\newline

When considering about the speed of Redis operations it is pretty fast. It can done 110,000 SETs of operations per second and 81,000 Gets operations per second in an entry level Linux box. Redis supports several languages such as Java, C, Ruby, Python, PHP and many other languages. Engine Yard, Github and Ruby Minds are some of the uses of Redis.

\subsubsection{Cassandra}

Facebook is the well known user of Cassandra. Cassandra system was designed to run on cheap commodity hardware and handle high write throughput while not sacrificing and efficiency\cite{Lakshman}. Instead of Key-Value pair Cassandra used distributed multidimensional map index by a key. Basically Cassandra use two kind of column families called Simple and Super column families. Super column families can be visualized as a column family within a column family.\\

\newline

Cassandra API consists with three simple methods. Those are,

\begin{itemize}

\item insert (table, key, rowMutation)

\item get (table, key, columnName)

\item delete (table, key, columnName)

\end{itemize}

Cassandra system architecture has characteristics such as scalable and robust solutions for load balancing, member ship and failure detection, failure recovery, replica synchronization, overload handling, state transfer, concurrency and job scheduling, request marshalling, request routing, system monitoring and alarming, and configuration management\cite{Lakshman}. Partitioning, replication, membership, failure handling and scaling are key design features of Cassandra.\\

\newline

When considering read/writes request arrives at any node in the Cassandra cluster the state machine morphs the following states.

\begin{itemize}

\item Identify the nodes that own the data for the key

\item Rout the request to the node and wait on the response to arrive

\item If the replies do not arrive within the configured timeout value fail the request and return to the client

\item Figure out the latest response based on timestamp

\item Schedule a repairs of the data at any replica if they do not have the latest piece of data

\end{itemize}

\subsubsection{CouchDB}

CouchDB is similar to Tokyo Cabinet\cite{Seeger2009} in that it essentially maps keys to data, but CouchDB's philosophy is completely different. CouchDB is coded using Erlang language. Not like Redis or Cassandra, CouchDB used a simple RESTful HTTP/JSON approach to interfacing with the outside world. Instead of query by key we can use upload function to that index of our data and then we can call those functions and retrieve data. Another interesting feature of CouchDB is the fact that developers can use 'views' to query the software for data\cite{Seeger2009}.

\subsubsection{Advantages of NoSQL}

\subsubsection*{Elastic Scaling}

When considering on RDBMS, database administrators should have increase the number of servers due to the growth of data. When the load gets increases they have to distributing the database across multiple hosts. They should have to done this thing because RDBMS might not scale out easily on commodity cluster. But NoSQL databases are design to reduce this problem. NoSQL databases have feature of expand transparently to take advantage of new nodes and those NoSQL database are designed with low cost commodity hardware.

\subsubsection*{Big Data}

In some enterprises RDBMS are intolerable to handle transactions with large amount of data. But NoSQL databases are capable of handle massive amount of data in transactions which cannot be done by using RDBMS such as Hadoop and Outstrip.

\subsubsection*{Ease of Use}

In theoretically NoSQL databases are design for,

\begin{itemize}

\item Less management

\item Automatic repair

\item Data distribution

\item Simple data model lead to lower administration

\item Tuning requirements

\end{itemize}

In practical scenario also we can achieve those features. So when comparing NoSQL with RDBMS, NoSQL databases are ahead in ease of use.

\subsubsection*{Economics}

NoSQL databases are typically use clusters of cheap commodity servers to manage data and transactions. But RDBMS are relay on expensive, proprietary servers and storage systems. So when comparing cost of transaction per second, NoSQL can be many times less that RDBMS.

\subsubsection*{Flexible Data Model}

Considering on RDBMS, even minor change to the data model causes a big headache to database administrators. But NoSQL database are more relax in that scenario. Even more complex NoSQL databases such as Cassandra and HBase typically allow new columns to be created without too much confuse.

\newpage

\subsection{Data Storing Techniques in NoSQL Databases}

Key-Value pair and Distributed hash tables are the main techniques which used as data storing techniques in NoSQL databases. In this section we are going to talk about key-value pairs and distributed hash tables.

\subsubsection{Key-Value Pair}

Most of NoSQL databases are key-value stores. That key-value pair allows users to store values by key in the database and it does not actually concerned about the contest of data. It just store in the database. Key-Value NoSQL databases users do not defined the scheme, but users have to define the semantic for understanding what are the values are. The benefit of using key-value pair approach for NoSQL databases are it is very simple and easy to scale it. And also it has great performances, because we can heavily optimize the access pattern of key-value store. RedisDB, Cassandra, CouchDB and Tokyo Cabinet are some NoSQL databases which use key-value pairs to store data \cite{Seeger2009}. And well known key-value data storage is Amazon. It is one of the largest e-commerce operations in the world. They used key-values storage because of the reliability at a massive scale of data \cite{Decandia2007}.

\subsubsection*{Features of Key-Value Pairs}

\begin{itemize}

\item Concurrency ' In key-value pair NoSQL databases concurrency is only applicable on a single key. These databases usually used optimized writes or eventually consistence for the concurrency. Highly scalable system normally used eventually consistence for control the concurrency of the databases

\item Quires ' All the queries contains with the key. Other that key there is not any way to perform the query. We cannot use rang queries on the key

\item Transaction ' Some key-value stores guarantee transactions and others are not

\item Scheme ' Key-value stores have a scheme key as a string

\item Scaling up ' Two major options for scaling

\begin{itemize}

\item Share the entire key space

\item Replication

\end{itemize}

\item Usage ' We need a key to access the data

\end{itemize}

\subsubsection{Distributed Hash Tables}

We can categorize wireless ad-hoc and sensor networks as distributed system. Basically sensor network consists with thousands of sensor motes in some particular area and those sensor motes establish the network using radio medium. Distributed Hash Tables (DHTs) are also turned out to be simple, elegant and powerful building block for distributed system \cite{CHR}. So we can use DHTs for store data in wireless ad-hoc and

sensor networks. Also DHTs are useful in wireless sensor networking because they can be used to implement scalable network service.\\

\newline

In sensor networking routing messages between two arbitrary nodes is an extremely cost operation. It may flood the entire network to find the corresponding path between the two nodes. Therefore, any DHT for wireless networks must be aware and adapted to the underlying routing strategy \cite{CHR}. Cell Hash Routing (CHR) is a DHT which was design to overcome the above problem in wireless ad-hoc and sensor networks. First, it creates a very structured and sparsely populated network of clusters, where we can apply a lightweight routing scheme. Second, the efficiency of the routing scheme is not affected by increasing node density \cite{CHR}. Current implementation of CHR has following limitations.

\begin{itemize}

\item Dynamic cell structure

\item General non-UDG model

\item Incorrect determination of position

\item Cluster induces disconnection

\item Fault tolerance requirements

\end{itemize}

\subsubsection*{DHTs of Approaches over WSN}

\begin{itemize}

\item Geographic hash tables (GHT) - In GHT there is a space of identifiers for nodes and keys. Unlike other DHTs, this space is not virtual, but physical. GHT hashes keys into geographic coordinates, and stores a (key, value) pair at the sensor node geographically nearest the hash of its key \cite{Thanh2009}. Also GHT provides similar interface as DHTs.

\begin{itemize}

\item Put(k; v) stores v (the observed data) according to the key k

\item Data dissemination and storages

\item GHT maps the data to coordination in the network

\item Data refreshment and release

\end{itemize}

\begin{figure}[h!]

\centering

\includegraphics[width=0.45\textwidth]{Img/GHT}

\caption{An Example GHT}

\end{figure}

\item Chord for sensor networks (CSN) ' runs on two modes

\begin{itemize}

\item Energy efficient mode

\item Robust mode

\end{itemize}

\item Virtual ring routing (VRR) ' gives relationship between the virtual ring and the physical network topology

\item Topology based distributed hash tables (T-DHT) ' Basically two steps

\begin{itemize}

\item The constriction of virtual coordinate space, which represent the network topology

\item On top of these coordinates we built two-dimensional has-table, where each node maintains the data close to its virtual position

\end{itemize}

\item Cell hash routing

\item Scatter pastry

\end{itemize}

\begin{figure}[h!]

\centering

\includegraphics[width=0.30\textwidth]{Img/Compare}

\caption{Comparison of Methods Used DHTs in WSNs With Three Main Parameters}

\end{figure}

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.