11-10-2012, 05:31 PM
Capacity of Data Collection in Arbitrary Wireless Sensor Networks
Capacity of Data Collection.pdf (Size: 475.88 KB / Downloads: 24)
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. The union of
all sensing values from n sensors at a particular time is called
a snapshot. The task of data collection is to deliver these
snapshots to a single sink. Due to spatial separation, several
sensors can successfully transmit at the same time if these
transmissions do not cause any destructive wireless interference.
As in the literature, we first adopt the protocol
interference model in our analysis and assume that a successful
transmission over a link has a fixed data rateW bits/second.
Later, we relax these assumptions to more realistic models:
physical interference model and Gaussian channel model.
RELATED WORK
Gupta and Kumar initiated the research on capacity of
random wireless networks by studying the unicast capacity
in the seminal paper [9]. A number of following papers
studied capacity under different communication scenarios
in random networks: unicast [10], [11], [12], multicast [13],
[14], [15], and broadcast [16], [17]. In this paper, we focus on
the capacity of data collection in a many-to-one communication
scenario.
Capacity of data collection in random wireless sensor
networks has been investigated in [1], [2], [3], [4], [5], and
[6]. Duarte-Melo et al. [1], [2] first studied the many-to-one
transport capacity in random sensor networks under a
protocol interference model. They showed that the overall
capacity of data collection is ðWÞ. El Gamal [3] studied
data collection capacity subject to a total average transmitting
power constraint. They relaxed the assumption that
every node can only receive from one source node at a time.
It was shown that the capacity of random networks scales as
ðlognWÞ when n goes to infinity and the total average
power remains fixed. Their method uses antenna sharing
and channel coding. Barton and Zheng [4] also investigated
data collection capacity under more complex physical layer
models (noncooperative SINR (Signal to Interference plus
Noise Ratio) model and cooperative time reversal communication
(CTR) model).
Branch Scheduling Algorithm
We now illustrate how to collect one snapshot from all
sensors. Given the collection tree T, our scheduling algorithm
basically collects data from each path Pi in T one by one.
First, we explain how to schedule collection on a single
path. For a given path Pi, we can use i slots to collect one
data in the snapshot at the sink. See Fig. 2 for illustration. In
this figure, we assume that R ¼ r, i.e., only adjacent nodes
interfere with each other. Thus, i ¼ 3. Then, we color the
path using three colors as in Fig. 2a. Notice that each node
on the path has unit data to transfer. Links with the same
color are active in the same slot. After three slots (Fig. 2d),
the leaf node has no data in this snapshot and the sink got
one data from its child. Therefore, to receive all data on the
path, at most i jPij time slots are needed. We call this
scheduling method Path 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.
CONCLUSION
In this paper, we study the theoretical limits of data
collection in terms of capacity for arbitrary wireless sensor
networks. We first propose a simple data collection method
based on the BFS tree to achieve capacity of ðWÞ, which is
order optimal under protocol interference and disk graph
models. However, when the underlying network is a
general graph, we show that ðWÞ may not be achievable.
We prove that a new BFS-based method using greedy
scheduling .