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
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
v Flooding based scheme
v Critical node detection
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
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.