06-02-2013, 04:22 PM
Cut Detection in Wireless Sensor Networks
Detection in Wireless.pdf (Size: 635.22 KB / Downloads: 80)
Abstract
A wireless sensor network can get separated into multiple connected components due to the failure of some of its nodes,
which is called a “cut”. In this article we consider the problem of detecting cuts by the remaining nodes of a wireless sensor network.
We propose an algorithm that allows (i) every node to detect when the connectivity to a specially designated node has been lost,
and (ii) one or more nodes (that are connected to the special node after the cut) to detect the occurrence of the cut. The algorithm is
distributed and asynchronous: every node needs to communicate with only those nodes that are within its communication range. The
algorithm is based on the iterative computation of a fictitious “electrical potential” of the nodes. The convergence rate of the underlying
iterative scheme is independent of the size and structure of the network. We demonstrate the effectiveness of the proposed algorithm
through simulations and a real hardware implementation
INTRODUCTION
WIRELESS sensor networks (WSNs) are a promising
technology for monitoring large regions at high
spatial and temporal resolution. However, the small size
and low cost of the nodes that makes them attractive
for widespread deployment also causes the disadvantage
of low operational reliability. A node may fail due to
various factors such as mechanical/electrical problems,
environmental degradation, battery depletion, or hostile
tampering. In fact, node failure is expected to be quite
common due to the typically limited energy budget of
the nodes that are powered by small batteries. Failure
of a set of nodes will reduce the number of multi-hop
paths in the network. Such failures can cause a subset of
nodes – that have not failed – to become disconnected
from the rest, resulting in a “cut”. Two nodes are said to
be disconnected if there is no path between them.
State update law and electrical analogy
The DCD algorithm is based on the following electrical
analogy. Imagine the wireless sensor network as an
electrical circuit where current is injected at the source
node and extracted out of a common fictitious node that
is connected to every node of the sensor network. Each
edge is replaced by a 1
resistor. When a cut separates
certain nodes from the source node, the potential
of each of those nodes becomes 0, since there is no
current injection into their component. The potentials
are computed by an iterative scheme (described in the
sequel) which only requires periodic communication
among neighboring nodes. The nodes use the computed
potentials to detect if DOS events have occurred (i.e., if
they are disconnected from the source node).
The Distributed Cut Detection (DCD) Algorithm
DOS detection
The approach here is to exploit the fact that if the state
is close to 0 then the node is disconnected from the
source, otherwise not (this is made precise in Theorem 1
of Section 2.4). In order to reduce sensitivity of the
algorithm to variations in network size and structure,
we use a normalized state. DOS detection part consists
of steady-state detection, normalized state computation,
and connection/separation detection. Every node
i maintains a binary variable dDOSi(k), which is set to 1
if the node believes it is disconnected from the source
and 0 otherwise. This variable, which is called the DOS
status, is initialized to 1 since there is no reason to believe
a node is connected to the source initially.
Performance analysis
The evolution of the node states with and without the
occurrence of cuts in the general asynchronous and timevarying
setting is stated in the next theorem. In the
statement of Theorem 1 and Assumption 2, ki is the
local iteration counter at node i, and k is a global time
counter. The global counter is used solely for the ease
of exposition; a node does not need to have access to it.
The following assumptions are used:
Assumption 2: i) Communication between nodes is
symmetric; ii) If a node fails permanently, each of its
neighbors can detect its failure within a fixed time
period; iii) The source node never fails; iv) Every node
takes part in the communication and state update infinitely
often, i.e., as k1 ! 1, ki ! 1 for 8i.
Theorem 1: Let the nodes of a sensor network G(k)
execute the state update law in an asynchronous manner,
subject to Assumption 2.
CONCLUSIONS
The DCD algorithm we propose here enables every node
of a wireless sensor network to detect DOS (Disconnected
frOm Source) events if they occur. Second, it
enables a subset of nodes that experience CCOS (Connected,
but Cut Occurred Somewhere) events to detect
them and estimate the approximate location of the cut
in the form of a list of active nodes that lie at the
boundary of the cut/hole. The DOS and CCOS events
are defined with respect to a specially designated source
node. The algorithm is based on ideas from electrical
network theory and parallel iterative solution of linear
equations.