17-04-2013, 04:42 PM
Detecting Cuts in Sensor Networks
Detecting Cuts.pdf (Size: 392.15 KB / Downloads: 29)
INTRODUCTION
Wireless sensor networks (WSN) have emerged as an important
new technology for instrumenting and observing the physical world.
The basic building block of these networks is a tiny microprocessor
integrated with one or more MEMS (micro-electromechanical system)
sensors, actuators, and a wireless transceiver. These devices can
be embedded or scattered in large quantities in a physical space,
where they self-organize into an ad hoc multi-hop wireless network,
allowing us to observe and monitor the world at an unprecedented
spatial and temporal resolution. A rich variety of scientific, commercial,
and military applications [7], [11], [25], [32] has been proposed
for sensor networks, and many experimental prototypes are under
development in academia and industry. Realizing the full potential of
the sensor networks, however, requires solving several challenging
research problems. Many of these challenges stem from two major
limitations of the sensor nodes: low power and low bandwidth.
Consequently, a number of proposals have been made for improving
the data collection and information processing in sensor networks,
including power-aware routing and scheduling [16], [24], [27], innetwork
aggregation [15], [23], [28], query processing [13], data
storage management [12], etc.
Cuts in Sensor Networks
Consider a set S of n sensors, which are modeled as points in
the two-dimensional plane. (More generally, we can assume that the
sensors lie on a surface or terrain that is topologically equivalent to
the plane.) An adversary can make a linear cut through the sensor
network, disabling all the sensors on one side of the line; the base
station is assumed to lie on the other (safe) side. Formally, given a
line L, let L− and L+ denote the two half-planes defined by L, and
let L−(S) and L+(S) denote the subset of sensors that lie in these
half-planes. We will adopt the convention that the linear cut induced
by L disables all the sensors in L−(S). Alternatively, the adversary
can disrupt the communication so that sensors on one side of the line
cannot communicate with sensors on the other side, including the base
station. These two formulations are equivalent for our purpose. There
are other natural forms of cuts, such as circular cuts, rectangular cuts,
polygonal cuts. We will briefly discuss them in Section VI.
Related Work
The problem of network partition in sensor networks has been
raised in several papers, but it appears not to have been investigated
formally. In their survey paper [6], Chong and Kumar raise this
problem with a security focus: sensor networks may operate in
hostile environments and schemes to detect tampering should be
built into the design. In [5], Cerpa and Estrin propose schemes for
self-configuring sensor network topologies. They mention network
partition as an important problem for which “complementary system
mechanisms will be needed,” but leave that as a future research
direction. In [19], Lifton, Broxton and Paradiso consider a network
disconnection problem, but with a very different focus: the nodes
are cooperative. For instance, sensor nodes with low battery power
communicate with the network to determine whether the network will
be partitioned if they failed. This is also an experimental paper, with
no formal algorithm analysis.
GEOMETRIC PRELIMINARIES
The network topology and the communication protocol are not
directly relevant to our result. We simply assume that the sensor
network is connected and that every sensor is able to communicate
with a base station through multi-hop routing, as long as a valid
communication path exists. We also assume that the location of every
sensor is available to the base station. A set S of n sensors scattered
in a terrain is modeled as a set of n points in the plane (ignoring the
altitude of each sensor). Our problem of monitoring the integrity of
the sensor field is best studied in a geometric setting.
EXPERIMENTAL EVALUATION
In this section, we describe our simulations results that are intended
to evaluate the scalability of our sentinel based scheme. We also
performed experiments comparing our scheme with some simple
sampling-based methods.
The geometric distribution of sensors is likely to vary widely from
application to application. We, therefore, generated several random
and non-random distributions of points in the plane to model a variety
of sensor networks. We used three main data sets in our simulation:
(1) uniform, (2) non-uniform, and (3) US census data. Figure 5 shows
example distributions of these three sets. The uniform set contains n
random points uniformly distributed in a square. The non-uniform set
contains n points, equally divided among k clusters. Each cluster is
centered at a random point, and the points in the cluster are generated
using a Gaussian distribution. The last set is a US Tiger Census map,
which includes locations of 14, 000 geographical features in the USA.
We chose these locations as positions for the sensors.