08-10-2012, 01:48 PM
DRINA: A Lightweight and Reliable Routing Approach for in-Network Aggregation in Wireless Sensor Networks
[attachment=35655]
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.
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.
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.
Cluster Formation
When an event is detected by one or more nodes, the leader
election algorithm starts and sensing nodes will be running
for leadership (group coordinator); this process is described in
Algorithm 2. For this election, all sensing nodes are eligible.
If this is the first event, the leader node will be the one that is
closest to the sink node. Otherwise, the leader will be the node
that is closest to an already established route (Algorithm 2,
Lines 7 to 9). In the case of a tie, i.e., two or more concurrent
nodes have the same distance in hops to the sink (or to an
established route), the node with the smallest ID maintains
eligibility, as shown in Lines 11 to 13 of Algorithm 2. Another
possibility is to use the energy level as a tiebreak criterion.
Routing Formation and Hop Tree Updates
The elected group leader, as described in Algorithm 2, starts
establishing the new route for the event dissemination. This
process is described in Algorithm 3, (Lines 2 to 10). For
that, the Coordinator sends a route establishment message
to its NextHop node. When the NextHop node receives a
route establishment message, it re-transmits the message to
its NextHop and starts the hop tree updating process. These
steps are repeated until either the sink is reached or a node
that is part of an already established route is found. The routes
are created by choosing the best neighbor at each hop. The
choices for the best neighbor are twofold: (i) when the first
event occurs, the node that leads to the shortest path to the
sink is chosen (Figure 2(a)); and (ii) after the occurrence of
subsequent events, the best neighbor is the one that leads to
the closest node that is already part of an established route
(Figure 2©). This process tends to increase the aggregation
points, ensuring that they occur as close as possible to the
events.
COMPLEXITY ANALYSIS
In this section we derive the communication cost bounds
for DRINA, InFRA, and SPT algorithms. More specifically,
we present the limits for the communication cost of these
algorithms to create the routing structure. We also present the
best and worst cases, while the average case will be shown in
the simulation results (see Section 5).
In the SPT algorithm, there is constant communication
cost to build the routing infrastructure. In a reactive fashion
operation, it is necessary one flooding started by the nodes that
sensed the first event in order to build the routing tree. One
more flooding, initiated by the sink node, is also necessary
for the other nodes to set up their ancestors in the tree
infrastructure. Hence, the constant communication cost for
SPT is 2n, where n is number of nodes.
Methodology
The performance evaluation is achieved through simulations
using the SinalGo version v.0.75.3 network simulator [35]. In
all results, curves represent average values, while error bars
represent confidence intervals for 95% of confidence from 33
different instances (seeds). The default simulation parameters
are presented in Table 3. For each simulation set, a parameter
shown in Table 3 will be varied as described in the evaluated
scenario. The first event starts at time 1000 s and all other
events start at a uniformly distributed random time between
the interval [1000, 3000] seconds. Also, these events occur
at random positions. The network density is considered as
the relation nπr2
c/A, where n is number of nodes, rc is the
communication radius, and A is the area of the sensor field.
For each simulation in which the number of nodes is varied,
the sensor field dimension is adjusted accordingly in order to
maintain the node density at the same value. Sensor nodes are
uniformly and randomly deployed.
Number of Steiner nodes
Since the ideal aggregation is achieved when the information
is routed through the minimal Steiner tree [17], in this section
we evaluate the number of Steiner tree nodes (i.e., relay nodes)
obtained after the construction of the routing tree structure for
each of the evaluated algorithms. In this analysis, the network
size is varied from 256 to 2048 sensor nodes; the density is
varied from 20 to 30; and the number of events were also
varied from 1 to 6.
The obtained results are presented in Figure 4. We can
clearly see that the number of Steiner nodes in the routing
tree built by DRINA algorithm is lower than the ones obtained
by the SPT and InFRA algorithms in all studied scenarios.
When compared to the MST algorithm, DRINA algorithm
results in a slightly larger number of Steiner nodes. However,
as mentioned before, the MST algorithm is not suitable for
WSNs due to its high overhead and large amount of required
memory. We are only comparing our proposed approach to
the MST algorithm because the number of Steiner nodes in
the routing tree built by the MST algorithm is proved to be at
most twice the optimum (i.e., minimum) Steiner tree [36].
The good results obtained by the DRINA algorithm are due
to its characteristic of prioritizing nodes that are closer to
already existing routes. The InFRA algorithm, on the other
hand, prioritizes the distance to the sink node, resulting in
lower and/or later aggregations, which increases the number
of Steiner nodes.
CONCLUSION AND FUTURE WORK
Aggregation aware routing algorithms play an important role
in event based WSNs. In this work we presented the DRINA
algorithm, a novel and reliable Data Aggregation Aware Routing
Protocol for WSNs. Our proposed DRINA algorithm was
extensively compared to two other known routing algorithms,
the InFRA and SPT, regarding scalability, communication
costs, delivery efficiency, aggregation rate and aggregated data
delivery rate. By maximizing the aggregation points and offering
a fault tolerant mechanism to improve delivery rate, the
obtained results clearly show that DRINA outperformed the
InFRA and SPT algorithms for all evaluated scenarios. Also,
we show that our proposed algorithm has some key aspects
required by WSNs aggregation aware routing algorithms 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.
[attachment=35655]
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.
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.
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.
Cluster Formation
When an event is detected by one or more nodes, the leader
election algorithm starts and sensing nodes will be running
for leadership (group coordinator); this process is described in
Algorithm 2. For this election, all sensing nodes are eligible.
If this is the first event, the leader node will be the one that is
closest to the sink node. Otherwise, the leader will be the node
that is closest to an already established route (Algorithm 2,
Lines 7 to 9). In the case of a tie, i.e., two or more concurrent
nodes have the same distance in hops to the sink (or to an
established route), the node with the smallest ID maintains
eligibility, as shown in Lines 11 to 13 of Algorithm 2. Another
possibility is to use the energy level as a tiebreak criterion.
Routing Formation and Hop Tree Updates
The elected group leader, as described in Algorithm 2, starts
establishing the new route for the event dissemination. This
process is described in Algorithm 3, (Lines 2 to 10). For
that, the Coordinator sends a route establishment message
to its NextHop node. When the NextHop node receives a
route establishment message, it re-transmits the message to
its NextHop and starts the hop tree updating process. These
steps are repeated until either the sink is reached or a node
that is part of an already established route is found. The routes
are created by choosing the best neighbor at each hop. The
choices for the best neighbor are twofold: (i) when the first
event occurs, the node that leads to the shortest path to the
sink is chosen (Figure 2(a)); and (ii) after the occurrence of
subsequent events, the best neighbor is the one that leads to
the closest node that is already part of an established route
(Figure 2©). This process tends to increase the aggregation
points, ensuring that they occur as close as possible to the
events.
COMPLEXITY ANALYSIS
In this section we derive the communication cost bounds
for DRINA, InFRA, and SPT algorithms. More specifically,
we present the limits for the communication cost of these
algorithms to create the routing structure. We also present the
best and worst cases, while the average case will be shown in
the simulation results (see Section 5).
In the SPT algorithm, there is constant communication
cost to build the routing infrastructure. In a reactive fashion
operation, it is necessary one flooding started by the nodes that
sensed the first event in order to build the routing tree. One
more flooding, initiated by the sink node, is also necessary
for the other nodes to set up their ancestors in the tree
infrastructure. Hence, the constant communication cost for
SPT is 2n, where n is number of nodes.
Methodology
The performance evaluation is achieved through simulations
using the SinalGo version v.0.75.3 network simulator [35]. In
all results, curves represent average values, while error bars
represent confidence intervals for 95% of confidence from 33
different instances (seeds). The default simulation parameters
are presented in Table 3. For each simulation set, a parameter
shown in Table 3 will be varied as described in the evaluated
scenario. The first event starts at time 1000 s and all other
events start at a uniformly distributed random time between
the interval [1000, 3000] seconds. Also, these events occur
at random positions. The network density is considered as
the relation nπr2
c/A, where n is number of nodes, rc is the
communication radius, and A is the area of the sensor field.
For each simulation in which the number of nodes is varied,
the sensor field dimension is adjusted accordingly in order to
maintain the node density at the same value. Sensor nodes are
uniformly and randomly deployed.
Number of Steiner nodes
Since the ideal aggregation is achieved when the information
is routed through the minimal Steiner tree [17], in this section
we evaluate the number of Steiner tree nodes (i.e., relay nodes)
obtained after the construction of the routing tree structure for
each of the evaluated algorithms. In this analysis, the network
size is varied from 256 to 2048 sensor nodes; the density is
varied from 20 to 30; and the number of events were also
varied from 1 to 6.
The obtained results are presented in Figure 4. We can
clearly see that the number of Steiner nodes in the routing
tree built by DRINA algorithm is lower than the ones obtained
by the SPT and InFRA algorithms in all studied scenarios.
When compared to the MST algorithm, DRINA algorithm
results in a slightly larger number of Steiner nodes. However,
as mentioned before, the MST algorithm is not suitable for
WSNs due to its high overhead and large amount of required
memory. We are only comparing our proposed approach to
the MST algorithm because the number of Steiner nodes in
the routing tree built by the MST algorithm is proved to be at
most twice the optimum (i.e., minimum) Steiner tree [36].
The good results obtained by the DRINA algorithm are due
to its characteristic of prioritizing nodes that are closer to
already existing routes. The InFRA algorithm, on the other
hand, prioritizes the distance to the sink node, resulting in
lower and/or later aggregations, which increases the number
of Steiner nodes.
CONCLUSION AND FUTURE WORK
Aggregation aware routing algorithms play an important role
in event based WSNs. In this work we presented the DRINA
algorithm, a novel and reliable Data Aggregation Aware Routing
Protocol for WSNs. Our proposed DRINA algorithm was
extensively compared to two other known routing algorithms,
the InFRA and SPT, regarding scalability, communication
costs, delivery efficiency, aggregation rate and aggregated data
delivery rate. By maximizing the aggregation points and offering
a fault tolerant mechanism to improve delivery rate, the
obtained results clearly show that DRINA outperformed the
InFRA and SPT algorithms for all evaluated scenarios. Also,
we show that our proposed algorithm has some key aspects
required by WSNs aggregation aware routing algorithms 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.