09-02-2013, 04:33 PM
Fast Data Collection in Tree-Based Wireless Sensor Networks
Fast Data Collection in Tree.pdf (Size: 1.13 MB / Downloads: 30)
Abstract
We investigate the following fundamental question—how fast can information be collected from a wireless sensor network
organized as tree? To address this, we explore and evaluate a number of different techniques using realistic simulation models under
the many-to-one communication paradigm known as convergecast. We first consider time scheduling on a single frequency channel
with the aim of minimizing the number of time slots required (schedule length) to complete a convergecast. Next, we combine
scheduling with transmission power control to mitigate the effects of interference, and show that while power control helps in reducing
the schedule length under a single frequency, scheduling transmissions using multiple frequencies is more efficient. We give lower
bounds on the schedule length when interference is completely eliminated, and propose algorithms that achieve these bounds. We
also evaluate the performance of various channel assignment methods and find empirically that for moderate size networks of about
100 nodes, the use of multifrequency scheduling can suffice to eliminate most of the interference. Then, the data collection rate no
longer remains limited by interference but by the topology of the routing tree. To this end, we construct degree-constrained spanning
trees and capacitated minimal spanning trees, and show significant improvement in scheduling performance over different deployment
densities. Lastly, we evaluate the impact of different interference and channel models on the schedule length.
INTRODUCTION
CONVERGECAST, namely, the collection of data from a set of
sensors toward a common sink over a tree-based
routing topology, is a fundamental operation in wireless
sensor networks (WSNs) [1]. In many applications, it is
crucial to provide a guarantee on the delivery time as well as
increase the rate of such data collection. For instance, in
safety and mission-critical applications where sensor nodes
are deployed to detect oil/gas leak or structural damage, the
actuators and controllers need to receive data from all the
sensors within a specific deadline [2], failure of which might
lead to unpredictable and catastrophic events. This falls
under the category of one-shot data collection. On the other
hand, applications such as permafrost monitoring [3] require
periodic and fast data delivery over long periods of time,
which falls under the category of continuous data collection.
RELATED WORK
Fast data collection with the goal to minimize the schedule
length for aggregated convergecast has been studied by us
INCEL ET AL.: FAST DATA COLLECTION IN TREE-BASED WIRELESS SENSOR NETWORKS 87
in [7] and [9], and also by others in [5], [10], and [11]. In [7],
we experimentally investigated the impact of transmission
power control and multiple frequency channels on the
schedule length, while the theoretical aspects were discussed
in [9], where we proposed constant factor and
logarithmic approximation algorithms on geometric networks
(disk graphs). Raw-data convergecast has been
studied in [1], [12], [13], and [14], where a distributed time
slot assignment scheme is proposed by Gandham et al. [1]
to minimize the TDMA schedule length for a single channel.
The problem of joint scheduling and transmission power
control is studied by Moscibroda [5] for constant and
uniform traffic demands. Our present work is different
from the above in that we evaluate transmission power
control under realistic settings and compute lower bounds
on the schedule length for tree networks with algorithms to
achieve these bounds. We also compare the efficiency of
different channel assignment methods and interference
models, and propose schemes for constructing specific
routing tree topologies that enhance the data collection rate
for both aggregated and raw-data convergecast.
MODELING AND PROBLEM FORMULATION
We model the multihop WSN as a graph G ¼ ðV ;EÞ, where
V is the set of nodes, and E ¼ fði; jÞ j i; j 2 V g is the set of
edges representing the wireless links. A designated node
s 2 V denotes the sink. The euclidean distance between two
nodes i and j is denoted by dij. All the nodes except s are
sources, which generate packets and transmit them over a
routing tree to s. We denote the spanning tree on G rooted
at s by T ¼ ðV ;ET Þ, where ET E represents the tree
edges. Each node is assumed to be equipped with a single
half-duplex transceiver, which prevents it from sending and
receiving packets simultaneously. We consider a TDMA
protocol where time is divided into slots, and consecutive
slots are grouped into equal-sized nonoverlapping frames.
We use two types of interference models for our
evaluation: the graph-based protocol model and the SINRbased
physical model. In the protocol model, we assume
that the interference range of a node is equal to its
transmission range, i.e., two links cannot be scheduled
simultaneously if the receiver of at least one link is within
the range of the transmitter of the other link. In the physical
model, the successful reception of a packet from i to j
depends on the ratio between the received signal strength at
j and the cumulative interference caused by all other
concurrently transmitting nodes and the ambient noise
level. Thus, a packet is received successfully at j if the
signal-to-interference-plus-noise ratio, SINRij, is greater
than a certain threshold , i.e.,