30-04-2012, 12:25 PM
Mitigating Performance Degradation in Congested Sensor Networks
Mitigating Performance Degradation in Congested Sensor Networks.pdf (Size: 4 MB / Downloads: 41)
1 INTRODUCTION
SENSOR network deployments may include hundreds or
thousands of nodes. Since deploying such large-scale
networks has a high cost, it is increasingly likely that
sensors will be shared by multiple applications and gather
various types of data: temperature, the presence of lethal
chemical gases, audio and/or video feeds, etc. Therefore,
data generated in a sensor network may not all be equally
important.
With large deployment sizes, congestion becomes an
important problem. Congestion may lead to indiscriminate
dropping of data (i.e., high-priority (HP) packets may be
dropped while low-priority (LP) packets are delivered). It
also results in an increase in energy consumption to route
packets that will be dropped downstream as links become
saturated. As nodes along optimal routes are depleted
of energy, only nonoptimal routes remain, further
compounding the problem. To ensure that data with
higher priority is received in the presence of congestion
due to LP packets, differentiated service must be provided.
In this work, we are interested in congestion that results
from excessive competition for the wireless medium.
Existing schemes detect congestion while considering all
data to be equally important. We characterize congestion
as the degradation of service to HP data due to competing
LP traffic. In this case, congestion detection is reduced to
identifying competition for medium access between HP
and LP traffic.
Congestion becomes worse when a particular area is
generating data at a high rate. This mayoccur in deployments
in which sensors in one area of interest are requested to gather
and transmit data at a higher rate than others (similar to
bursty convergecast [25]). In this case, routing dynamics can
lead to congestion on specific paths. These paths are usually
close to each other, which leads to an entire zone in the
network facing congestion. We refer to this zone, essentially
an extended hotspot, as the congestion zone (conzone).
In this paper, we examine data delivery issues in
the presence of congestion. We propose the use of data
prioritization and a differentiated routing protocol and/or a
prioritized medium access scheme to mitigate its effects on
HP traffic. We strive for a solution that accommodates
both LP and HP traffic when the network is static or near
static and enables fast recovery of LP traffic in networks
with mobile HP data sources. Our solution uses a
differentiated routing approach to effectively separate
HP traffic from LP traffic in the sensor network. HP traffic
has exclusive use of nodes along its shortest path to the
sink, whereas LP traffic is routed over uncongested nodes
in the network but may traverse longer paths.
Our contributions in this work are listed as follows:
. Design of Congestion-Aware Routing (CAR). CAR
is a network-layer solution to provide differentiated
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 7, NO. 7, JULY 2008 1
. R. Kumar, H. Rowaihy, G. Cao, and T.F. La Porta are with the Department
of Computer Science and Engineering, The Pennsylvania State University,
State College, PA 16802.
E-mail: {rajukuma, rowaihy, gcao, tlp}[at]cse.psu.edu.
. R. Crepaldi is with the Department of Computer Science, University of
Illinois, Urbana-Champaign, IL 61801-2302. E-mail: rcrepal2[at]uiuc.edu.
. A.F. Harris III is with the Center for Remote Sensing of Ice Sheets
(CReSIS), University of Kansas, Lawrence, KS 66045-7612.
E-mail: afh[at]cresis.ku.edu.
. M. Zorzi is with Department of Information Engineering, University of
Padova, 35131 Padova, Italy. E-mail: zorzi[at]dei.unipd.it.
Manuscript received 6 Aug. 2007; revised 16 Nov. 2007; accepted 10 Jan.
2008; published online 28 Jan. 2008.
For information on obtaining reprints of this article, please send e-mail to:
tmc[at]computer.org, and reference IEEECS Log Number TMC-2007-08-0232.
Digital Object Identifier no. 10.1109/TMC.2008.20.
1536-1233/08/$25.00 2008 IEEE Published by the IEEE CS, CASS, ComSoc, IES, & SPS
service in congested sensor networks. CAR also
prevents severe degradation of service to LP data by
utilizing uncongested parts of the network.
. Design of MAC-Enhanced CAR (MCAR). MCAR
is primarily a MAC-layer mechanism used in
conjunction with routing to provide mobile and
lightweight conzones to address sensor networks
with mobile HP data sources and/or bursty
HP traffic. Compared to CAR, MCAR has a
smaller overhead but degrades the performance of
LP data more aggressively.
We compare CAR and MCAR to an AODV scheme
enhanced with priority queues (AODVþPQ). Both CAR and
MCAR lead to a significant increase in the successful packet
delivery ratio of HP data and a clear decrease in the average
delivery delay compared to AODVþPQ. CAR and MCAR
also provide low jitter. Moreover, they use energy more
uniformly in the deployment and reduce the energy
consumed in the nodes that lie on the conzone, which
leads to an increase in connectivity lifetime. In the presence
of sufficient congestion, CAR also allows an appreciable
amount of LP data to be delivered. We further show that, in
the presence of mobile HP data sources, MCAR provides
mobile conzones, which follow the HP traffic.
We also present the implementation of MCAR on our
sensor network testbed. The implementation shows the
feasibility of MAC-layer enhancements and differentiated
routing on current hardware. We demonstrate that using an
actual implementation, HP delivery rates similar to those
seen in simulation can be achieved in a practical system.
The rest of this paper is organized as follows: Section 2
presents related work. Details of CAR and MCAR are
presented in Section 3. Simulation details and results are
presented in Section 4. Section 5 discusses our testbed
implementation and results. Finally, Section 6 presents
conclusions and future directions.
2 RELATED WORK
An obvious solution to enhance service to HP data is to use
priority queues to provide differentiated services (see [4],
[15], and [25]). However, in such schemes, though
HP packets get precedence over LP packets within a node,
at the MAC layer, they still compete for a shared channel
with LP traffic sent by surrounding nodes. As a result,
without a routing scheme to address the impact of
congestion and hotspots in the network, local solutions like
priority queuing are not sufficient to provide adequate
priority service to important data.
QoS in sensor networks has been the focus of current
research (e.g., [4], [8], and [26]). SPEED [8] provides soft
real-time guarantees for end-to-end traffic using feedback
control and location awareness. It also concludes that local
adaptation at the MAC layer alone is insufficient to address
the problem of hotspots and that routing is essential to the
solution. Akkaya and Younis [4] propose an energy-aware
QoS routing protocol to support the delivery of real-time
data in the presence of interfering non-real-time data by
using multiple queues in each node in a cluster-based
network; they do not consider the impact of congestion in
the network and the interference that non-real-time traffic
can cause to real-time data. Zhang et al. [26] propose a
generic model for achieving multiple QoS objectives.
Degrading service to one type of data to provide better
service to another has been used in schemes like RAP [15]
and SWAN [3]. Similar to these works, we segregate data;
however, instead of real-time delivery demands, we use
data priority as the basis for our segregation.
Approaches like 802.11e [1] and other differentiated
MAC schemes that assign higher priority to important data
(e.g., VoIP for 802.11e) via MAC-layer mechanisms succeed
at providing better service to HP data by assigning them
preferential medium access. Funneling-MAC [2], proposed
by Ahn et al., addresses the issue of increased traffic
intensity in the proximity of a sink by using a schedulebased
and contention-based MAC hybrid. As with data
aggregation schemes like [16] and [21], it serves to delay the
occurrence of congestion. Back pressure and rate limiting
(also used in SPEED [8] and Fusion [10]) are essential to
avoid situations where the network capacity is less than the
amount of traffic being injected into the medium.
Rangwala et al. [20] propose Interference-Aware Fair Rate
Control (IFRC), which employs schemes to achieve fair and
efficient rate limiting. It uses a tree rooted at each sink to
route all data. When congestion occurs, the rates of the flows
on the interfering trees are throttled. But, these schemes do
not adopt differentiated routing. Also, in a large network
that is under congestion in a constrained area, our approach
leverages the large uncongested parts of the network that is
often underutilized to deliver LP traffic.
RAP [15], SPEED [8], and MMSPEED [7] use velocitymonotonic
scheduling. Applications assign an expected speed
to each data packet, which is then ensured by these
schemes. The speed that the application should assign to
a packet if the network is congested is unclear. These
schemes spread traffic around hotspots, but they do not
give preference to HP data. In fact, if LP data has led to a
hotspot in an area, routes for HP data that later enter the
network will circumvent this hotspot. This will increase the
number of hops over which this data has to be routed and
increase the energy consumed in the network. In the worst
case, no path for HP data may be found, and these packets
will be dropped. Additionally, MMSPEED [7] achieves
reliability by duplicating packets and routing them over
different paths to the destination. Duplication of packets in
congested networks may further precipitate congestion.
Also, these schemes do not explicitly separate LP and
HP traffic generated in the same area.
Our schemes are different from these schemes, because
we use differentiated routing to provide the best possible
service to HP data while trying to decrease the energy
consumption in the conzone.
Congestion in sensor networks has been addressed
in works like CODA [22], Fusion [10], and by Ee and
Bajcsy [6]. Though these schemes take important steps to
mitigate congestion in sensor networks, they treat all data
equally. These schemes are complementary to the capability
provided by CAR and MCAR. Similarly, our solutions do
not preclude the use of priority queues, which can be added
as a simple extension.
Existing work on congestion in sensor networks has
two aspects: detection and mitigation. As mentioned earlier,
we do not concern ourselves with congestion detection
2 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 7, NO. 7, JULY 2008
schemes in this work. Most mitigation schemes differ in how
they invoke back pressure and rate limiting. Fusion’s [10]
mitigation scheme (other than back pressure and rate limiting)
is assigning preferential medium access to parents in
the routing tree. This assumes that all data in a network is
destined to a single sink, which might not always be the case.
In contrast, in our scenario, LP data can be sent from any
node to any other node. As a result, Fusion’s preferential
MAC scheme is not applicable. Also, congestion in Fusion
occurs due to the accumulation of packets close to the sink.
In contrast, we address the degradation of performance of
HP data delivery due to an extended hotspot in the network
resulting from competition for medium access between LP
and HP data. Also, Fusion does not do data differentiation
based on priorities or provide differentiated routing.