DATA GATHERING IN WIRELESS SENSOR NETWORKS - Mini Project

[Kalyan]

DATA GATHERING IN WIRELESS SENSOR NETWORKS

Abstract

Sensor networks have recently emerged as an important platform. Sensor nodes are typically less mobile and more densely deployed than mobile ad-hoc networks. Networking together hundreds or thousands of micro sensor nodes allows users to accurately monitor a remote environment by intelligently combining the data from the individual nodes. These networks require robust wireless communication protocols that are energy efficient and provide low latency.

One of the main design aspects for sensor network architectures is energy efficiency to keep the network operational as long as possible. Therefore data gathering technique are essential building blocks, as they aim to reduce the number of transmissions required for data collection which in turn reduces energy consumption. When sequence of data gathering query arrives one by one, to respond each query the system builds a spanning tree.

The objective when building a tree is to maximize the number of data gathering queries answered until the first node in the network fails. The algorithm proposed for maximizing the network lifetime takes the residual energy and the volume of the data at each sensor nodes for performance measure.

1. INTRODUCTION

Wireless Sensor network is a collection of sensor nodes deployed in an ad hoc fashion. Being battery powered and deployed in remote areas they have limited energy resource and hence limited lifetime. Other constraints are limited memory, processing power, bandwidth and large latencies. Due to these limitations data aggregation is an important consideration for sensor networks. The idea is to combine the data coming from different sources and route it further after eliminating redundancy. Data gathering can be used for a wide variety of monitoring and research applications like inventory maintenance, healthcare, military, object recognition and tracking, research and study of biological and environmental phenomenon. The performance of the application depends on the ability to extract data from the network. The main constraint of sensor nodes is their low battery energies which limits the network lifetime and has an impact on the quality of the network. Thus, the network lifetime of a wireless sensor network is defined as the time of the first node failure in the network. Therefore, energy efficiency in the design of routing protocols for sensor networks is important. Hence there is a need for data gathering mechanism which improves the network lifetime by minimizing the communication thus consuming less energy.

2. QUERY PROCESSING

Sensor networks generate a large amount of data. For extracting information, we need to collect and query the data from sensor networks. The primary focus is on aggregate summarized data. A Query can be a request for information or orders to collect more data. When a user requests a query at the sink node to the sensor network the query is disseminated across the network. In response to the query the system builds a routing tree rooted at the sink. The probable queries for the sensor networks can be categorized into:

1) Simple Queries:
These are non aggregate queries. E.g. "SELECT temperature FROM sensor WHERE node = z". These are generally mapped into broadcast or point to point queries.

2) Complex Queries:
They may contain sub queries. E.g. "SELECT temperature FROM sensor WHERE room = (SELECT room WHERE floor = '3')"

3) Event Driven Queries:
These are the continuous queries that return values periodically at specified time intervals. E.g. "SELECT AVG (temperature) FROM sensor where node = z". The query is similar to SQL, supporting the SQL clauses like SELECT, FROM, WHERE, GROUP BY, HAVING and aggregate clauses like MAX, AVG, MIN, COUNT and SUM. The difference is they support continuous monitoring queries by adding the clauses like DURATION and EVERY representing the lifetime of the query and the rate of answering the query.

3. DATA AGGREGATION

To support queries over sensor networks, the distributed data over sensor nodes need to be processed. This poses up an implicit requirement for aggregating the data. There are two approaches for data aggregation.

1) Centralized approach
2) In-Network Aggregation

3.1 Centralized Approach

This is an address centric approach where each node sends data to a central node via the shortest possible route using a multi-hop wireless protocol. The sensor nodes simply send the data packets to a leader, which is a powerful node. The leader aggregates the data which can be queried. The underlying routing protocols need minimal changes. Wireless protocol like AODV can be used. Each intermediate node has to send the data packets addressed to leader from the child nodes. So a large number of messages have to be transmitted for a query- in the best case equal to the sum of external path lengths for each node. The major drawback is the sensor networks are energy constrained and hence the approach is costly as requires a lot of messages to be exchanged for each query.

3.2 In-Network Aggregation

This is a data centric approach where the intermediate nodes can look at the content and perform aggregation on multiple packets it receives. The transmitting and receiving cost is greater than the computing cost. This has been the motivation for in-network aggregation. It implies the shifting of a part of the computation from clients to the sensor nodes- aggregating the results or filtering the irrelevant data records with an aim of reducing the message transfer and efficient use of bandwidth, thereby increasing the life time of the system.

4. RELATED WORKS

To prolong the network lifetime, Energy efficient routing protocols for wireless ad hoc networks have been addressed in literature [3].

The energy efficient broadcast or multicast routing in ad hoc networks which aims to minimize the total transmission energy consumption, has been extensively studied [10]. To solve this problem an energy efficient broadcast or multicast tree rooted at the source is built and the same message is broadcast from the tree root to every other node in the tree. The data gathering problem in sensor networks is to build a routing tree rooted at a sink node too. The data gathering problem aiming at the minimization of the total energy consumption has been studied in the literature [11].

They have initialized the study of this problem by proposing clustering protocol called LEACH. The nodes in LEACH are grouped into a number of clusters in a self-organizing manner, and a cluster head serves as a local "base station" to aggregate the gathered messages from its members and forward the result to the sink directly.

Lindsey and Raghavendra in [4] studied the problem by providing an improved protocol called PEGASIS in which all the nodes in the network form a chain and one of the nodes in the chain is chosen as the head that will be responsible for reporting the aggregated result to the base station.

Kalpakis in [2] considered this problem by proposing an integer program solution and a heuristic solution. It should be mentioned that although each of the above approaches for data gathering does consider the energy consumption issue none of them provides energy consumption metric explicitly as the optimization objective.

The existing data gathering approaches based on routing trees assume that the length of the message transmitted by each relay node is independent of the lengths of its children messages, i.e., each node transmits the same volume of data no matter how much data it received from its children. Such queries in databases include AVG, MIN, MAX, COUNT, etc. However, there are a number of data gathering applications in which the length of the message transmitted by a relay node depends on not only the length of its sensed message, but also the lengths of the messages received from its children.

There are several studies that deal with data gathering problem [5] with different optimization metrics of energy consumption. They also proposed a hierarchical matching algorithm for the problem, which delivers an approximate solution that is up to a logarithmic factor of the optimum. Cristescu in [5] studied a variant of the problem the data correlation problem with an objective to minimize the total transmission energy consumption. In [9] they proposed a data dissemination schema called directed diffusion with opportunistic aggregation, where data is opportunistically aggregated at intermediate nodes on a low latency tree. In this paper, the proposed algorithm takes the energy optimization metrics to prolong the network lifetime.

5. PROBLEM DEFINITION

Given a wireless sensor network M = (N, A) with a sink node, we assume that there is an unknown sequence of data gathering queries which arrive one by one. As a query arrives, the response by the system to the query is to build a routing tree rooted at the sink and spanning the other nodes for it. We further assume that the length of the message transmitted by each relay node in the routing tree is the sum of the lengths of its children messages and its own sensed message. The data gathering problem is to maximize the network lifetime without knowledge of future query arrivals and generation rates. In other words, the problem is to maximize the number of queries answered until the first node in the network fails. For a given query, the length of the sensed message by each sensor node is identical, it is various for different queries.

To prolong the network lifetime when dealing with data gathering by using different energy optimization metrics, there are two types of energy optimization metrics that have been widely used, One is to find a routing tree T such that the total transmission energy consumption in tree is minimized, which aims to prolong the network lifetime through minimizing the total energy consumption per data gathering query.

However, this optimization does not take into account the energy consumption at each individual node. Thus, a relay node near the tree root may run out of energy and fail very quickly, which leads to the network being partitioned. Another is to find a routing tree T such that the minimum residual energy among the nodes is maximized. Residual energy is defined as the current battery level of the node at time t. This optimization aims to prolong the network lifetime through extending the lifetime of individual nodes by maximizing the minimum residual energy among the nodes.


6. ENERGY MODEL

The Residual Energy for a node is the current battery level of the node at time t. When node i send data to node j then the residual energy of the node i is calculated as,

Min { r(i) – TXi,j , r(j) – RXj }
Where,
r(i) is residual energy of node, r(j) is residual energy of node j. TXi,j is energy consumed in transmitting data packets from i to sensor j.

TXi,j = Elec * K + E amp * d i,j 2 * K

Where,
Elec is the energy consumed by sensor to run the transmitter or receiver circuitry. Eamp is energy consumed by transmitter amplifier and d i,j is the distance between node i and j and k refers to the data packet.

7. ALGORITHM FOR DATA GATHERING


In the following, we propose an algorithm for the data gathering problem. Consider the wireless sensor network M (N, A) as a directed graph G (V, E) where the set of nodes V consisting of sensors and (u, v) € E if and only if u and v are within the transmission ranges of each other.

The basic idea behind the proposed algorithm is that once a data gathering query arrives, a data gathering tree for the query is constructed using a greedy policy that maximizes the minimum residual energy among the nodes. Specifically, the nodes are included into the tree one by one. Initially, only the sink node is included. Each time a node v is included into the tree, either the network lifetime derived from the current tree is at least as long as that without the inclusion of v to the tree or the amount of reduction of the network lifetime is minimized. That is, a node v is chosen to be included into the tree if it leads to maximizing the minimum residual energy among the tree nodes including it.

The proposed algorithm is that once a data gathering query arrives, a data gathering tree for the query is constructed with the root at sink such that it maximizes the minimum residual energy among the nodes. A node v is included into the tree if it leads to maximizing the minimum residual energy. Thus the node is included into the tree one by one.

.

Maximum_Network_Lifetime(G; re; k)
/* G is the current sensor network and re is an array of the
residual energy at each node */
begin
1. VT? {s}; terminate "false";
/* VT is the set of nodes in the tree, terminate is a boolean variable, */
/* and k is the size of the sensed data by node added node. */
2. Q? V- VT;
/* the set of nodes that are not in the tree*/
3.re(s) ? 8;
/* the sink node has unlimited energy supply */
4. repeat

5. gmax? 0;
/* the maximal minimum residual energy at nodes in the tree */
6. for each v € Q do
7. compute gmax (v) and temp_parent (v)
8. if gmax (v) > gmax then
9. gmax ? gmax (v)
10. added node? v;
/* the node that will be added to the tree */
endif;
endfor;
11. if gmax > 0 then
12. p (added node) ?temp_parent( added_node)
13. for each node u € Padded_node,s do
14. re(u) ? re(u)- kda u, p(u)

endfor;
15. VT ? VT U {added_node};
16. Q? Q _ {added_node};
17. else terminate 'true';
18. endif;
19. until (Q = null) or terminate;
end.

8. OUTPUT

The performance of the proposed algorithm is evaluated through experimental simulations. The node is distributed in a 100 * 100 m 2 region and one of the nodes is the sink node, which has unlimited energy supply. The initial energy assigned to each sensor node except the sink node is identical. The data gathering queries are assumed to arrive one by one. The length k of the sensed message by each sensor node for a data gathering query is identical. The network lifetime, which is the time of the first node failure due to expiration of its energy, is used as the metric to evaluate the performance of the algorithm.

9. CONCLUSION

This paper introduces an energy-efficient
data gathering scheme for maximizing the network lifetime by taking the energy consumed by each node rather than considering the energy consumed by the entire network. Thus the algorithm outperforms the other existing algorithms while we consider the energy as an optimizing metric.

[rajvb]

hi there can u plz tell me in which environment the simulations were carried out?

[dhoni]

this is really amazing project
data gathering wireless sensor n/w
this should be easily send data to other network with wireless sensor this can send