18-10-2012, 04:55 PM
Capacity of Data Collection in Arbitrary Wireless Sensor Networks
Capacity of Data Collection.pdf (Size: 475.88 KB / Downloads: 28)
Abstract—
Data collection is a fundamental function provided by wireless sensor networks. How to efficiently collect sensing data from
all sensor nodes is critical to the performance of sensor networks. In this paper, we aim to understand the theoretical limits of data
collection in a TDMA-based sensor network in terms of possible and achievable maximum capacity. Previously, the study of data
collection capacity [1], [2], [3], [4], [5], [6] has concentrated on large-scale random networks. However, in most of the practical sensor
applications, the sensor network is not uniformly deployed and the number of sensors may not be as huge as in theory. Therefore, it is
necessary to study the capacity of data collection in an arbitrary network. In this paper, we first derive the upper and lower bounds for
data collection capacity in arbitrary networks under protocol interference and disk graph models. We show that a simple BFS treebased
method can lead to order-optimal performance for any arbitrary sensor networks. We then study the capacity bounds of data
collection under a general graph model, where two nearby nodes may be unable to communicate due to barriers or path fading, and
discuss performance implications. Finally, we provide discussions on the design of data collection under a physical interference model
or a Gaussian channel model.
INTRODUCTION
DUE to their wide-range potential applications in various
scenarios such as battlefield, emergency relief, and
environment monitoring, wireless sensor networks have
recently emerged as a premier research topic. The ultimate
goal of a sensor network is often to deliver the sensing data
from all sensors to a sink node and then conduct further
analysis at the sink node. Thus, data collection is one of the
most common services used in sensor network applications.
In this paper, we study some fundamental capacity problems
arising from the data collection in wireless sensor networks.
We consider a wireless sensor network where n sensors
are arbitrarily deployed in a finite geographical region. Each
sensor measures independent field values at regular time
intervals and sends these values to a sink node.
CAPACITY FOR A DISK GRAPH MODEL
Upper bound of collection capacity. It has been proved that
the upper bound of capacity of data collection for random
networks isW [1], [2]. It is obvious that this upper bound also
holds for any arbitrary network. The sink v0 cannot receive at
rate faster than W since W is the fixed transmission rate of
individual link. Therefore, we are interested in the design of a
data collection algorithm to achieve capacity in the same
order of the upper bound, i.e., ðWÞ.
In this section, we propose a simple BFS-based data
collection method and demonstrate that it can achieve the
capacity of ðWÞ under our network model: disk graph
model. Our data collection method includes two steps: data
collection tree formation and data collection scheduling.
CAPACITY FOR A GENERAL GRAPH MODEL
So far, we assume that the communication graph is a disk
graph where two nodes can communicate if and only if
their distance is less than or equal to transmission range r.
However, a disk graph model is idealistic since in practice
two nearby nodes may be unable to communicate due to
various reasons such as barriers and path fading. Therefore,
in this section, we consider a more general graph model
G ¼ ðV ;EÞ where V is the set of sensors and E is the set of
possible communication links. Every sensor still has a fixed
transmission range r such that the necessary condition for vj
to receive correctly the signal from vi is kvi vjk r.
However, kvi vjk r is not the sufficient condition for an
edge vivj 2 E. Some links do not belong to G because of
physical barriers or the selection of routing protocols. Thus,
G is a subgraph of a disk graph. Under this model, the
network topology G can be any general graph (for example,
setting r¼1and putting a barrier between any two nodes
vi and vj if vivj 62 G). Notice that even though we still
consider the protocol interference model, our analysis still
holds for an arbitrary interference graph.