06-02-2013, 02:35 PM
DRINA: A Lightweight and Reliable Routing Approach for in-Network Aggregation in Wireless Sensor Networks
[attachment=49842]
Abstract
Large scale dense wireless sensor networks (WSNs) will be
increasingly deployed in different classes of applications for accurate
monitoring. Due to the high density of nodes in these networks, it is likely
that redundant data will be detected by nearby nodes when sensing an
event. Since energy conservation is a key issue in WSNs, data fusion
and aggregation should be exploited in order to save energy. In this
case, redundant data can be aggregated at intermediate nodes reducing
the size and number of exchanged messages and, thus, decreasing
communication costs and energy consumption. In this work we propose
a novel Data Routing for In-Network Aggregation, called DRINA, that
has some key aspects such as a reduced number of messages for
setting up a routing tree, maximized number of overlapping routes,
high aggregation rate, and reliable data aggregation and transmission.
The proposed DRINA algorithm was extensively compared to two other
known solutions: the InFRA and SPT algorithms. Our results indicate
clearly that the routing tree built by DRINA provides the best aggregation
quality when compared to these other algorithms. The obtained results
show that our proposed solution outperforms these solutions in different
scenarios and in different key aspects required by WSNs.
INTRODUCTION
A Wireless Sensor Network (WSN) consists of spatially distributed
autonomous devices that cooperatively sense physical
or environmental conditions, such as temperature, sound,
vibration, pressure, motion or pollutants at different locations
[1], [2]. WSNs have been used in applications such as
environmental monitoring, homeland security, critical infrastructure
systems, communications, manufacturing and many
other applications that can be critical to save lives and assets
[3], [4], [5].
Sensor nodes are energy-constrained devices and the energy
consumption is generally associated with the amount of gathered
data, since communication is often the most expensive
activity in terms of energy. For that reason, algorithms and
protocols designed for WSNs should consider the energy
consumption in their conception [6], [7], [8], [9]. Moreover,
WSNs are data-driven networks that usually produce a large
amount of information that needs to be routed, often in a multihop
fashion, toward a sink node, which works as a gateway
to a monitoring center (Figure 1). Given this scenario, routing
plays an important role in the data gathering process.
A possible strategy to optimize the routing task is to use
the available processing capacity provided by the intermediate
sensor nodes along the routing paths. This is known as datacentric
routing or in-network data aggregation. For more
efficient and effective data gathering with a minimum use
of the limited resources, sensor nodes should be configured
to smartly report data by making local decisions [10], [11],
[12], [13]. For this, data aggregation is an effective technique
for saving energy in WSNs. Due to the inherent redundancy
in raw data gathered by the sensor nodes, in-networking
aggregation can often be used to decrease the communication
cost by eliminating redundancy and forwarding only smaller
aggregated information. Since minimal communication leads
directly to energy savings, which extends the network lifetime,
in-network data aggregation is a key technology to be
supported byWSNs. In this work, the terms information fusion
and data aggregation are used as synonyms. In this context, the
use of information fusion is twofold [14]: (i) to take advantage
of data redundancy and increase data accuracy, and (ii) to
reduce communication load and save energy.
IN-NETWORK DATA AGGREGATION
In the context of WSNs, in-network data aggregation refers
to the different ways intermediate nodes forward data packets
toward the sink node while combining the data gathered from
different source nodes. A key component for in-network data
aggregation is the design of a data aggregation aware routing
protocol. Data aggregation requires a forwarding paradigm that
is different from the classic routing, which typically involves
the shortest path “in relation to some specific metric” to
forward data toward the sink node. Differently from the classic
approach in data aggregation aware routing algorithms, nodes
route packets based on their content and choose the next hop
that maximizes the overlap of routes in order to promote innetwork
data aggregation.
A key aspect of in-network data aggregation is the synchronization
of data transmission among the nodes. In these
algorithms, a node usually does not send data as soon as it is
available since waiting for data from neighboring nodes may
lead to better data aggregation opportunities. This in turn, will
improve the performance of the algorithm and save energy.
Three main timing strategies are found in the literature [15],
[16]:
Cluster-Based Approaches
Similarly to the tree-based approaches, cluster-based
schemes [27], [30], [31] also consist of a hierarchical
organization of the network. However, in these approaches,
nodes are divided into clusters. Moreover, special nodes,
referred to as cluster-heads, are elected to aggregate data
locally and forward the result of such aggregation to the sink
node.
In the Low-Energy Adaptive Clustering Hierarchy (LEACH)
algorithm [30], clustered structures are exploited to perform
data aggregation. In this algorithm, cluster-heads can act as
aggregation points and they communicate directly to the sink
node. In order to evenly distribute energy consumption among
all nodes, cluster-heads are randomly elected in each round.
LEACH-based algorithms assume that the sink can be reached
by any node in only one hop, which limits the size of the
network for which such protocols can be used.
The Information Fusion-based Role Assignment (InFRA)
algorithm [27] builds a cluster for each event including only
those nodes that were able to detect it. Then, cluster-heads
merge the data within the cluster and send the result toward
the sink node. The InFRA algorithm aims at building the
shortest path tree that maximizes information fusion. Thus,
once clusters are formed, cluster-heads choose the shortest
path to the sink node that also maximizes information fusion
by using the aggregated coordinators-distance [27]. A disadvantage
of the InFRA algorithm is that for each new event that
arises in the network, the information about the event must be
flooded throughout the network to inform other nodes about
its occurrence and to update the aggregated coordinatorsdistance.
This procedure increases the communication cost of
the algorithm and, thus, limits its scalability.
[attachment=49842]
Abstract
Large scale dense wireless sensor networks (WSNs) will be
increasingly deployed in different classes of applications for accurate
monitoring. Due to the high density of nodes in these networks, it is likely
that redundant data will be detected by nearby nodes when sensing an
event. Since energy conservation is a key issue in WSNs, data fusion
and aggregation should be exploited in order to save energy. In this
case, redundant data can be aggregated at intermediate nodes reducing
the size and number of exchanged messages and, thus, decreasing
communication costs and energy consumption. In this work we propose
a novel Data Routing for In-Network Aggregation, called DRINA, that
has some key aspects such as a reduced number of messages for
setting up a routing tree, maximized number of overlapping routes,
high aggregation rate, and reliable data aggregation and transmission.
The proposed DRINA algorithm was extensively compared to two other
known solutions: the InFRA and SPT algorithms. Our results indicate
clearly that the routing tree built by DRINA provides the best aggregation
quality when compared to these other algorithms. The obtained results
show that our proposed solution outperforms these solutions in different
scenarios and in different key aspects required by WSNs.
INTRODUCTION
A Wireless Sensor Network (WSN) consists of spatially distributed
autonomous devices that cooperatively sense physical
or environmental conditions, such as temperature, sound,
vibration, pressure, motion or pollutants at different locations
[1], [2]. WSNs have been used in applications such as
environmental monitoring, homeland security, critical infrastructure
systems, communications, manufacturing and many
other applications that can be critical to save lives and assets
[3], [4], [5].
Sensor nodes are energy-constrained devices and the energy
consumption is generally associated with the amount of gathered
data, since communication is often the most expensive
activity in terms of energy. For that reason, algorithms and
protocols designed for WSNs should consider the energy
consumption in their conception [6], [7], [8], [9]. Moreover,
WSNs are data-driven networks that usually produce a large
amount of information that needs to be routed, often in a multihop
fashion, toward a sink node, which works as a gateway
to a monitoring center (Figure 1). Given this scenario, routing
plays an important role in the data gathering process.
A possible strategy to optimize the routing task is to use
the available processing capacity provided by the intermediate
sensor nodes along the routing paths. This is known as datacentric
routing or in-network data aggregation. For more
efficient and effective data gathering with a minimum use
of the limited resources, sensor nodes should be configured
to smartly report data by making local decisions [10], [11],
[12], [13]. For this, data aggregation is an effective technique
for saving energy in WSNs. Due to the inherent redundancy
in raw data gathered by the sensor nodes, in-networking
aggregation can often be used to decrease the communication
cost by eliminating redundancy and forwarding only smaller
aggregated information. Since minimal communication leads
directly to energy savings, which extends the network lifetime,
in-network data aggregation is a key technology to be
supported byWSNs. In this work, the terms information fusion
and data aggregation are used as synonyms. In this context, the
use of information fusion is twofold [14]: (i) to take advantage
of data redundancy and increase data accuracy, and (ii) to
reduce communication load and save energy.
IN-NETWORK DATA AGGREGATION
In the context of WSNs, in-network data aggregation refers
to the different ways intermediate nodes forward data packets
toward the sink node while combining the data gathered from
different source nodes. A key component for in-network data
aggregation is the design of a data aggregation aware routing
protocol. Data aggregation requires a forwarding paradigm that
is different from the classic routing, which typically involves
the shortest path “in relation to some specific metric” to
forward data toward the sink node. Differently from the classic
approach in data aggregation aware routing algorithms, nodes
route packets based on their content and choose the next hop
that maximizes the overlap of routes in order to promote innetwork
data aggregation.
A key aspect of in-network data aggregation is the synchronization
of data transmission among the nodes. In these
algorithms, a node usually does not send data as soon as it is
available since waiting for data from neighboring nodes may
lead to better data aggregation opportunities. This in turn, will
improve the performance of the algorithm and save energy.
Three main timing strategies are found in the literature [15],
[16]:
Cluster-Based Approaches
Similarly to the tree-based approaches, cluster-based
schemes [27], [30], [31] also consist of a hierarchical
organization of the network. However, in these approaches,
nodes are divided into clusters. Moreover, special nodes,
referred to as cluster-heads, are elected to aggregate data
locally and forward the result of such aggregation to the sink
node.
In the Low-Energy Adaptive Clustering Hierarchy (LEACH)
algorithm [30], clustered structures are exploited to perform
data aggregation. In this algorithm, cluster-heads can act as
aggregation points and they communicate directly to the sink
node. In order to evenly distribute energy consumption among
all nodes, cluster-heads are randomly elected in each round.
LEACH-based algorithms assume that the sink can be reached
by any node in only one hop, which limits the size of the
network for which such protocols can be used.
The Information Fusion-based Role Assignment (InFRA)
algorithm [27] builds a cluster for each event including only
those nodes that were able to detect it. Then, cluster-heads
merge the data within the cluster and send the result toward
the sink node. The InFRA algorithm aims at building the
shortest path tree that maximizes information fusion. Thus,
once clusters are formed, cluster-heads choose the shortest
path to the sink node that also maximizes information fusion
by using the aggregated coordinators-distance [27]. A disadvantage
of the InFRA algorithm is that for each new event that
arises in the network, the information about the event must be
flooded throughout the network to inform other nodes about
its occurrence and to update the aggregated coordinatorsdistance.
This procedure increases the communication cost of
the algorithm and, thus, limits its scalability.