21-09-2016, 10:12 AM
1455514927-Routing.pdf (Size: 1.27 MB / Downloads: 7)
Abstract
One of the major challenges in wireless sensor networks (WSNs) research is to prevent traffic congestion without
compromising with the energy of the sensor nodes. Network congestion leads to packet loss, throughput
impairment, and energy waste. To address this issue in this paper, a distributed traffic-aware routing scheme
with a capacity of adjusting the data transmission rate of nodes is proposed for multi-sink wireless sensor networks
that effectively distribute traffic from the source to sink nodes. Our algorithm is designed through constructing a
hybrid virtual gradient field using depth and normalized traffic loading to routing and providing a balance between
optimal paths and possible congestion on routes toward those sinks. The simulation results indicate that the
proposed solution can improve the utilization of network resources, reduce unnecessary packet retransmission,
and significantly improve the performance of WSNs.
1 Introduction
Wireless sensor network (WSN) refers to a group of
spatially dispersed and dedicated sensors for monitoring
and recording the physical conditions of the environment
and organizing the collected data at a central
location. In large-scale applications of wireless sensor
networks (WSNs), such as environment monitoring or
agricultural scenarios, several hundreds of sensor nodes
are deployed over a large covered-area [1,2]. Large numbers
of nodes become active and transmit data traffic,
leading to congested areas.
Congestion in wireless sensor networks has a negative
impact on the performance, decreases throughput, increases
packet retransmission, and wastes energy. In
wireless sensor networks, traffic has the centralized
pattern, so bypassing the hot spots is not effective in
removing the congestion, because it will reappear near
the sink.
Additionally, the traditional centralized approach, in
which data traffic from sensor nodes accumulate near
one sink [3,4], is not efficient in terms of energy consumption
or packet delays and may yet be unacceptable
due to limited network capacity. Therefore, using multiple sinks is proposed as a more feasible scheme
for such networks [5-8].
In this paper, we propose a traffic-aware routing algorithm
to route packets around congested areas by using
the idle or under loaded nodes. The key concept of our
algorithm is to construct two independent gradient fields
using depth and traffic loading, respectively.
The depth (distance cost) is built conventionally as
in other gradient-based routing protocols that find
the shortest paths for packets. The second factor addresses
the traffic loading of neighboring nodes that
may become the next forwarder. Once the traffic
loading exceeds a threshold, it means that there is
congestion at a node in the path toward a specific
sink; the packets would flow along other suboptimal
paths.
Thus, the traffic gradient field endows our trafficaware
solution, and the depth field provides the basic
routing backbone to direct the packets to the sink.
These two fields will be combined into a hybrid potential
field to dynamically make routing decisions. In
other words, this method leads to a trade-off between
the shortest paths and traffic at overloaded node. Additionally,
our algorithm presents a hop-by-hop congestion
control scheme, in which congestion is controlled by dynamically adjusting data transmission rate of the
nodes.
The rest of this paper is organized as follows: in
Section 2, we introduce the related work about congestion
control in WSN and summarize the studies related
to gradient-based routing. In Section 3, the basic idea is
presented, in which the total gradient is built and some
properties are analyzed. In Section 4, detailed implementation
of the proposed algorithm is described. Simulation
settings and numerical results are presented in Section
5. The final section concludes the paper and discusses
the scope for future work.
2 Related works
Since wireless sensor networks work on a limited network
bandwidth, traffic congestion frequently occurs
during the relay process of sensing data. To solve this
problem, several studies have been proposed based on
the reduction of data sensing rates in terminal sensor
nodes [9,10].
Congestion detection and avoidance (CODA) [10]
presents the first detailed investigation on congestion
detection and avoidance in wireless sensor networks.
CODA includes three elements - congestion detection
based on receiving, open loop hop-by-hop back pressure,
and closed loop multi-source rate adjustment. As
with open loop hop-by hop back pressure, the source
gets the back pressure signals depending on the local
congestion state. For closed loop multi-source rate adjustment,
the source gets an acknowledgement (ACK)
from the sink and when the congestion occurs, the sink
stops sending ACKs to the source. CODA controls the
rate of flow of packets based on the additive-increase/
multiplicative-decrease (AIMD) algorithm. This technique
is energy-efficient, but the reliability of the successful delivery
of the packets to the destination is not guaranteed,
for on receiving back pressure signals (meaning, the signals
received by the source node from the intermediate
nodes), the nodes drop their packets based on the congestion
parameters.
The event-to-sink reliable transport (ESRT) protocol
improved the reliability of event data transmission in
wireless sensor networks [11]. In this method, all sensor
nodes monitor their internal buffers to find traffic congestion.
When traffic congestion is detected, the result
is sent to the sink node. The sink node periodically configures
the source sending rate with broadcasts the congestion
state to all sensor nodes. After receiving the
broadcast message, each sensor node tries to reduce the
data transmission rate. Due to the reduced data traffic,
the traffic congestion problem could be alleviated gradually.
Similarly, interference-aware fair rate control
(IFRC) [12] uses static queue thresholds to determine
congestion level and operates congestion control by adjusting outgoing rates on each link based on AIMD
scheme. It employs a tree rooted at each sink to route
all data. When congestion occurs, the flow rates of the
interfering trees are throttled.
When traffic congestion occurs, the above methods
lead to the reduction of data sensing rates in the terminal
sensor nodes. There have been some attempts to
explore mechanisms for congestion avoidance in WSNs
but not for the schemes based on reduction of data sensing
rates.
SPEED [13] manages congestion by rerouting the incoming
traffic around the hot spot. The rerouted path,
however, may not have a larger end-to-end channel capacity
to accommodate the incoming traffic, leading to
congestion. In congestion-aware routing (CAR) [14],
authors represent a differentiated routing approach to
discover the congested area of the network that exists
between high-priority data sources and the data sink and
to dedicate this portion of the network to forward primarily
high-priority traffic data.
Another scheme is proposed to split the traffic from
the source into multiple paths to achieve load balance
and increase throughput [15].
To avoid additional costs of multi-path routing when
the network is not congested, biased geographical routing
(BGR) protocol [16] is presented to reactively split traffic,
when congestion is detected. BGR employs the dynamic
routing technique to alleviate congestion so as to decrease
the additional cost of static multi-path routing. If its drawbacks,
such as the blindness during scattering packets and
the restrictions on coordinate systems, can be properly
overcome, a more effective and practicable congestion
control mechanism would be achieved for WSNs. Based
on this understanding, many studies have been conducted
with the aim of using gradient search to solve the routing
problem in WSNs [17-21].
In gradient search, a node builds its own gradient field
in response to neighbor nodes in the direction of a specific
sink. Data traffic flows along the direction with the
steepest gradient in order to reach the sink. The cost
model can be designed in terms of hop count from sink
to node, physical distance, energy consumption, or cumulative
delay, depending on the objectives of routing
such as energy consumption, packet delay, or packet delivery
ratio [22].
One of the first researches mentioning the concept of
gradient for routing protocols in WSNs conducted diffusion
technique [18] leading to energy savings by storing
and processing data in a network. The gradient field
contains a data rate and duration information field from
a node to its neighbors toward the sink.
Many research works have been devoted to solve the
energy-aware routing in wireless sensor networks.
Gradient-based routing protocol for load-balancing (GLOBAL) [22] focuses on energy improvement in
large-scale multi-sink wireless sensor networks. It allows a
source node to choose the least loaded path in order to
avoid overloaded nodes by constructing its gradient field
utilizing the weighted factor of the cumulative path load
and traffic load of the overloaded nodes over the path.
However, the approach based on global information cannot
guarantee the correctness of the updated information
over the long path because of the network dynamics in
high traffic scenarios.
Also, SGF [23] is a gradient-based routing protocol to
reach significant energy savings. The authors suggest a
new gradient field for nodes without using routing tables.
The values are updated on demand by data transmission
with little overhead. A cost-aware multi-hop is
represented in [24] routing protocol. The cost metrics
used to build gradient fields are energy, traffic load,
delay, and link reliability. This algorithm leads to a significant
improvement in energy consumption. Another
scheme to solve energy efficiency and computational
complexity in industrial WSN is proposed in [25]. The
authors present a new method with two-hop information
routing algorithm that takes velocity and remaining
energy at each node into account. Gao et al. [26] form
clusters via nodes with the same number of hops away
from the sink. Each node then takes turns to become
the cluster head to balance the energy consumption and
the lifetime of sensor nodes in a cluster.
In addition to energy-aware, traffic control is also an important
issue in WSNs. Traffic-aware routing to achieve
network balancing and congestion avoidance, has received
extensive attention in the area of WSNs. The routing algorithm
in [21] designs a potential field for traffic-aware
routing based on steepest gradient search method in
order to create a trade-off between traffic metrics and
link costs. It means that the routing algorithm in [21]
finds optimal routes by balancing congested areas and
the shortest path. It is proved that this algorithm obtains
significant improvement in end-to-end delay and
jitter over many kinds of networks and traffic conditions
with a few overheads. The method, however, is hardly
applied to WSNs, because it requires extensive communication
and computation, and it is originally designed
for the Internet. Park and Jung [27] propose a trafficaware
routing protocol (TARP) to increase the data
transmission efficiency and improve energy consumption
for WSNs. TARP uses a lightweight genetic algorithm
to distribute the data traffic away from congested
areas. TARP also takes two-hop information of surrounding
nodes in route calculation; however, this
algorithm focuses on packet loss due to queue overflow
and power efficiency and therefore leads to single sink
scheme, which is different from our model. Gradientbased
traffic-aware (GRATA) routing [28] utilizes the expected packet delay at one-hop neighbor and the
number of hops to make routing decisions. However,
the routing scheme based on packet delay can be lack of
information about traffic condition, which may lead a
packet to a new congestion area.
In this paper, we will follow gradient-based search
model to solve the traffic-aware routing issues. Compared
with the recent researches, our contributions are
as follows:
Leading to multi-sink WSN applications with heavy
traffic scenarios, in which a large amount of traffic
may cause black spot on the paths to the sink.
Using the number of hops from the local node to
the sink, while current traffic information contains
the queue length, the congestion degree and the
average cumulative queue length construct the
gradient field at each node.
Adjusting the congestion window and data
transmission rate of sender nodes in order to
improve overall throughput.
3 System model
In this section, we will distinguish how to make the
gradient-base routing model using depth and traffic
loading, respectively, and then how to integrate them together
to make dynamic routing decision. First, depth
field for a gradient field, which is based on the shortest
cost path model, is described. Next, we insert an additional
metric into the gradient field to reflect traffic
information in each of the neighboring nodes. By monitoring
the number of packets in queue, the congestion
degree and the average cumulative queue length, a node
informs its neighbors about both the distance cost from
itself to a sink and possible congestion.
On a multi-sink network, multiple gradients are built
corresponding to each sink. The height value in each node
implies the minimum cost to reach the final destination.
3.1 Depth field
To provide the basic routing function, namely, to make
each packet flow toward sink i, we define the depth
potential field Vi
d ð Þv as:
Vi
d ðÞ ¼ v Depth ðÞ ð v 1Þ
where depth (v) is the depth of node v with respect to sink i.
Depth (v) is quite similar to the length of the shortest
path, since they both represent the distance from the
destination. If the shortest path algorithm chooses the
hop count as its routing metric, Depth (v) will actually
become the length. Due to the centralized traffic pattern
in WSNs, Depth (v) has some special properties. The
depth difference between node v and its neighboring node wє nbr(v), namely Vi
d ð Þ v; w , can only be either −1,
0, or 1, since the neighbors nodes are defined to be one
hop away. As a result, the depth field encourages packet
to flow directly to the sink via the shortest path.
We will now show that a system based on the shortest
path paradigm is loop-free [29], following Theorem 1.
Theorem 1: If field Vd (v1) is independent of time,
shortest path routing is loop free.
Proof: This theorem is proved by contradiction. Assume
that the field Vd (v1) monotonically decreases from source
to sink and the steepest gradient searches for a neighbor
with lowest gradient index. If there is a loop, then packets
go in a circle of v1 → v2 → … → vn → v1. However, this
closed loop cannot work, due to not meeting the condition
Vd (v1) < Vd (v1), because the number of hops from a
node to sinks is unchanged or time-invariant.
In a special case, if there are two or more next neighbors
with the same lowest gradient values, the node
chooses the next forwarder randomly in a stochastic
scheme, similar to tossing a die [30]. With hop count,
each node discovers a list of parents, siblings, and children
with respect to each sink from its neighbors, whose
hop count is respectively one hop lower, equal, or one
hop greater on the path toward a specific sink. The node
maintains a table with the relative nodes of each sink. In
light traffic, the node should choose routes with the lowest
distance to the sink in order to ensure low energy
consumption. However, since a large number of nodes
become active and send data to the sinks simultaneously,
this causes areas of congestion, leading to packet delays
or loss. Our target is to consider all candidates and to
find possible routes that can be used to avoid heavy traffic
regions by incorporating traffic conditions into our
calculation.