03-05-2012, 01:01 PM
Dynamic Conflict-Free Transmission Scheduling for Sensor Network Queries
Dynamic_Conflict-Free_Transmission_Scheduling_for_Sensor_Network_Queries.pdf (Size: 1.09 MB / Downloads: 32)
Abstract
With the emergence of high data rate sensor network applications, there is an increasing demand for high-performance
query services. To meet this challenge, we propose Dynamic Conflict-free Query Scheduling (DCQS), a novel scheduling technique for
queries in wireless sensor networks. In contrast to earlier TDMA protocols designed for general-purpose workloads, DCQS is
specifically designed for query services in wireless sensor networks. DCQS has several unique features. First, it optimizes the query
performance through conflict-free transmission scheduling based on the temporal properties of queries in wireless sensor networks.
Second, it can adapt to workload changes without explicitly reconstructing the transmission schedule. Furthermore, DCQS also
provides predictable performance in terms of the maximum achievable query rate. We provide an analytical capacity bound for DCQS
that enables DCQS to handle overload through rate control. NS2 simulations demonstrate that DCQS significantly outperforms a
representative TDMA protocol (DRAND) and 802.11b in terms of query latency and throughput.
Index Terms—Query scheduling, TDMA, sensor networks.
Ç
1 INTRODUCTION
EARLY research on wireless sensor networks (WSNs) has
focused on low data rate applications, such as habitat
monitoring [1]. In contrast, recent years have seen the
emergence of high data rate applications, such as real-time
structural health monitoring [2] and preventive equipment
maintenance [3]. For instance, a structural health monitoring
system may need to sample the acceleration of each
sensor at rates as high as 500 Hz, resulting in high network
load when a large number of sensors are deployed for finegrained
monitoring. Moreover, the system may have highly
variable workload in response to environmental changes.
For example, an earthquake may trigger a large number of
new queries in order to assess any potential damage to the
structure. Therefore, a key challenge is to provide a highthroughput
query service that can collect data from large
networks and adapt to workload changes.
To meet this challenge, we propose Dynamic Conflict-free
Query Scheduling (DCQS), an integrated framework for
transmission scheduling designed to meet the communication
needs of high data rate applications. A data collection
application may express its collection interests as queries
over subsets of nodes which may involve data aggregation
[4]. Instances of these queries are executed periodically to
collect data at the base station. The use of routing trees in
executing query instances introduces precedence constraints
among packet transmissions. For example, when data
aggregation is used, a node must wait for its children’s
data reports before computing an aggregated data report
and relaying it to its parent. Intuitively, integrating
application layer information (the periodicity of queries)
and routing layer information (the precedence constraints)
into the transmission scheduling process may lead to
significant performance improvements. By incorporating
this cross-layer information into the scheduling process,
DCQS provides not only better performance than traditional
transmission scheduling techniques designed for
general workloads and networks, but also has the following
salient features: 1) DCQS can adapt its transmission
schedule in response to the addition/removal of queries
and changes in query rates without having to recompute
its transmission schedule. 2) DCQS dynamically determines
the transmissions to be executed in each slot and, as
a result, it may adapt to workload changes more effectively
than traditional TDMA protocols with fixed transmissions
schedules. 3) DCQS has low runtime overhead and limited
memory requirements making it suitable for resourceconstrained
devices.
The remainder of the paper is organized as follows:
Section 2 describes the query and network models we adopt.
Section 3 details the design and analysis of DCQS. Section 4
describes how DCQS handles dynamic networks and workloads.
Section 5 provides simulation results using NS2.
DCQS is compared with existing transmission scheduling
approaches in Section 6. Section 7 concludes the paper.
2 SYSTEM MODELS
In the following, we describe the query and networks
models that DCQS builds upon.
734 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 5, MAY 2011
. O. Chipara is with the Department of Computer Science and Engineering,
University of California, San Diego, 9500 Gilman Drive, Mail Code 0404,
La Jolla, CA 92093-0404. E-mail: ochipara[at]gmail.com.
. C. Lu and C.-G. Roman are with the Department of Computer Science and
Engineering, Washington University in St. Louis, Bryan Hall, Campus
Box 1045, One Brookings Drive, St. Louis, MO 63130.
E-mail: lu[at]cse.wustl.edu, roman[at]wustl.edu.
. J.A. Stankovic is with the Department of Computer Science, School of
Engineering and Applied Science, University of Virginia, 151 Engineer’s
Way, PO Box 400740, Charlottesville, VA 22904-4740.
E-mail: stankovic[at]cs.virginia.edu.
Manuscript received 1 Oct. 2008; revised 8 Oct. 2009; accepted 12 July 2010;
published online 25 Oct. 2010.
For information on obtaining reprints of this article, please send e-mail to:
tmc[at]computer.org, and reference IEEECS Log Number TMC-2008-10-0391.
Digital Object Identifier no. 10.1109/TMC.2010.209.
1536-1233/11/$26.00 2011 IEEE Published by the IEEE CS, CASS, ComSoc, IES, & SPS
2.1 Query Model
DCQS assumes a common query model in which source
nodes produce data reports periodically. This model fits
many applications that gather data from the environment at
user-specified rates. Such applications generally rely on
existing query services [5]. A query is characterized by the
following parameters: a set of sources that respond to a
query, the query period Pq, and the start time of the query
q, and an optional function for in-network aggregation [4].
Query instances are released periodically to gather data from
the WSN. We use Iq;k to denote the kth instance of query q.
The query instance Iq;k is released at time Rq;k ¼ q þ k Pq
which we call the release time of Iq;k. For each query
instance, a node i needs Wq½i slots to transmit its
(aggregated) data report to its parent. DCQS can support
queries with in-network data aggregation, such as average
and histogram [4], as well as more common forms of
aggregation such as packet merging [6] and data compression
[7]. While DCQS can optimize the performance of
queries with aggregation, it also supports queries that do
not perform aggregation.
Aquery service works as follows: a user issues a query to a
sensor network through a base station, which disseminates
the query description to all nodes. To facilitate data
aggregation, each nonleaf node waits to receive the data
reports from its children, produces a new data report by
aggregating its data with the children’s data reports, and then
sends it to its parent. We assume that there is a single routing
tree that spans all nodes and it is used to execute all query
instances. This assumption is consistent with the approach
adopted by existing query services [4]. During the lifetime of
the application, the user may issue new queries, delete
queries, or change the period of existing queries. DCQS is
designed to support such workload dynamics efficiently.
2.2 Network Model
DCQS works by scheduling conflict-free transmissions in a
time slot. To determine whether two transmissions are in
conflict, we introduce the Interference-Communication (IC)
graph. The IC graph, ICðE; V Þ, has all nodes as vertices and
has two types of directed edges: communication and
interference edges. A communication edge ab
!
indicates that
the packets transmitted by a may be received by b. A subset
of the communication edges forms the routing tree that is
used for data collection. An interference edge ab
!
indicates
that a’s transmission interferes with any transmission
intended for b even though a’s transmission may not be
correctly received by b. An example of an IC graph is shown
in Fig. 2.
The IC graph is used to determine if two transmissions
may be scheduled concurrently. We say that two transmissions,
ab
!
and cd
!
are conflict-free (ab
!
k cd
!
)andmaybe scheduled
concurrently if 1) a, b, c, and d are distinct and 2) ad!
and cb
!
are
not edges in E. Referring to Fig. 2, the transmissions ea!and
fb !
conflict due to the interference edge eb
!
. In contrast,
transmissions ne ! and po ! are conflict-free, since edges no !
and pe !are not part of the graph.
RID, a realistic method for constructing IC graphs based
on Receive Signal Strength (RSS) measurements, is proposed
in [8]. To gather RSS measurements, nodes transmit
sequences of two packets. The first packet is broadcast at
maximum power and is used to identify the sender and
prepare the potential interfering nodes to measure the RSS
during the subsequent packet transmission. The second
packet is transmitted at the default power. Based on the
collected RSS values, interference edges are added to the IC
graph as follows: Consider a node p which receives packets
from one of its children c. Node p knows c’s RSS as well as
the RSS of all other senders which may interfere with c’s
transmission. RID generates all sets of interferes IðpÞ such
that jIðpÞj Nr, where Nr is a bound on the number of
senders that may be active in a time slot. Given the
transmission !cp, RID computes Signal to Noise Plus
Interference Ratio (SNIR) for each IðpÞ. If the SNIR for the
set IðpÞ is below a threshold, then incoming edges from the
nodes in IðpÞ to p are added to the graph. RID’s
communication cost is linear in the number of nodes.
The IC graph is based on the SNIR model. Empirical
studies validating the accuracy of the SNIR model on
802.15.4 [9], [10], [8] and 802.11 [11] radios have already
been performed. Moreover, MAC protocols which take
advantage of the SNIR model have already been proposed
and their performance validated empirically [12]. These
previous studies on real hardware indicate that the IC
graph is a realistic assumption. The IC graph was studied in
[9], which presented a realistic approach for constructing IC
graphs based on the SNIR model and RSS measurements. It
should also be noted that the IC graph model adopted by
our algorithm is more realistic than models often adopted
by earlier scheduling algorithms (e.g., unit disk models and
ignore interference).
Interference is inherently probabilistic and time-variant.
It is important to note that the SNIR threshold controls the
temporal stability of the IC graph. A conservative SNIR
threshold would lead to a more stable IC graph at the cost
of reduced throughput. We recognize that even when using
conservative SNIR threshold, packets may be still corrupted
as a result of intermittent interference. We address these
issues through retransmissions and multipath routing (see
Section 4).
While the IC graph is built conservatively to improve
temporal stability, over time the interference relations may
change significantly. We may detect changes in IC graph by
monitoring the reliability of data collection over time. If the
reliability falls below a user-set threshold then the IC graph
is rebuilt. The IC graph also needs to be updated when
nodes are added or removed.