Cut Detection in Wireless Sensor Networks – projects 2012
ABSTRACT:Cut Detection in Wireless Sensor Networks – projects 2012
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 paper, we consider the problem of detecting cuts by the remaining nodes of a wireless sensor network. We propose an algorithm that allows 1) every node to detect when the connectivity to a specially designated node has been lost, and 2) 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.
Under cut detection mechanism, every node to detect when the connectivity to a specially designated node has been lost, and one or more nodes (that are connected to the special node after the cut) to detect the occurrence of the cut.
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.” To make the network error prone, we need to identify the cut occurrence.
Cut detection must perform
- Detection by each node of a DOS event when it occurs
- Detection of Connected, but a Cut Occurred Somewhere (CCOS) event by the nodes close to a cut, and the approximate location of the cut.
- By approximate location of a cut, the location of one or more active nodes that lie at the boundary of the cut and that are connected to the source can be identified.
- Nodes that detect the occurrence and approximate locations of the cuts can then alert the source node or the base station.
When sensor wants to send data to the source node has been disconnected from the source node. Without the knowledge of the network’s disconnected state, it may simply forward the data to the next node in the routing tree, which will do the same to its next node, and so on. However, this message passing merely wastes precious energy of the nodes; the cut prevents the data from reaching the destination. Therefore, on one hand, if a node were able to detect the occurrence of a cut, it could simply wait for the network to be repaired and eventually reconnected, which saves on-board energy of multiple nodes and prolongs their lives. On the other hand, the ability of the source node to detect the occurrence and location of a cut will allow it to undertake network repair. Thus, the ability to detect cuts by both the disconnected nodes and the source node will lead to the increase in the operational lifetime of the network as a whole.
Distributed algorithm to detect cuts, named the Distributed Cut Detection (DCD) algorithm can serve as useful tools for such network repairing methods. The algorithm allows each node to detect DOS events and a subset of nodes to detect CCOS events. The algorithm proposed is distributed and asynchronous: it involves only local communication between neighboring nodes, and is robust to temporary communication failure between node pairs. A key component of the DCD algorithm is a distributed iterative computational step through which the nodes compute their (fictitious) electrical potentials. The convergence rate of the computation is independent of the size and structure of the network.
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 multihop 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.
We assume that there is a specially designated node in the network, which we call the source node. The source node may be a base station that serves as an interface between the network and its users. We can create a topology which consists of ‘n’ number of nodes. The number of nodes created can be done user preferences.
v E-linear cut detection
- Cut detection in wireless networks has been proposed, an algorithm that can be employed by a base station to detect an e-linear cut in a network. An e- linear cut is a separation of the network across a straight line so that at least en of the nodes (n is the total number of nodes in the network) are separated from the base station. The base station detects cuts when they occur based on whether it is able to receive messages from specially placed sentinel nodes.
v Flooding based scheme
- A flooding based scheme may also be used for detecting separations. Under node to- base flooding approach, every node periodically sends a time-stamped message to the base station. If the base station does not receive a new message from node i for a certain time interval, it can declare that i is disconnected from it. Base station floods the network with time-stamped beacon packets periodically. A node detects that it is disconnected from the base if the length of time during which it hasn’t received a new packet from the base exceeds a threshold value.
v Critical node detection
- A critical node is one whose removal renders the network disconnected.
v Algorithm proposed only for detecting linear cuts in the network
v In flooding based technique, routes from the nodes to the base station and back have to be recomputed when node failures occur.
v Critical node detection uses relatively lower communication overhead come at the cost of high rate of incorrect detection
- High false positives
- It should be emphasized that a cut can occur even if there are no critical nodes in network, when multiple non-critical nodes fail.
- Critical node detection algorithms mentioned above are designed to detect critical nodes before any node failure occurs; while the problem we address is detecting a cut after it occurs.
v DCD algorithm is applicable even when the network gets separated into multiple components of arbitrary shapes, and not limited to straight line cuts.
v DCD algorithm enables not just a base station to detect cuts, but also every node to detect if it is disconnected from the base station.
v CCOS event detection part of the algorithm is designed for networks deployed in 2D regions, the DOS event detection part is applicable to networks deployed in arbitrary spaces.
v Comes with provable characterization on the DOS detection accuracy
v CCOS events detection can be identified
v DCD algorithm enables base station and also every node to detect if it is disconnected from the base station.