Understanding Path Reconstruction Algorithms in WSN

Abstract

Low-power and multihop wireless networking is envisioned as a promising technology to achieve both energy efficiency and easy deployment for many Internet of Things (IoT) applications. Measuring packet-level path is crucial for managing large-scale multihop wireless networks. Packet-level path information encodes the routing path, a packet that takes through a network. The availability of packet-level path information can greatly facilitate many network management tasks. It is challenging to reconstruct packet-level paths using a small overhead, especially for large-scale networks. While there is a long list of existing path reconstruction algorithms, these algorithms focus on specific network scenarios, e.g., periodic monitoring networks or event detection networks. There lacks a unified model for systematically understanding and comparing the performance of these algorithms in different network scenarios. In this Project, we fill this gap by proposing an abstract model. Using this model, it is possible to derive a decision space for selecting the best algorithm for different networks. Furthermore, this model also guides us to devise better path reconstruction algorithms (cPathT, cPathS, and cPathST ) with respect to path reconstruction ratio. Extensive experiments demonstrate the prediction power of our model as well as the advantages of our proposed algorithms. The results show that our algorithm (cPathST ) improves a path reconstruction ratio from 94.4%, 34.3%, and 30.8% to 98.9%, 99.9%, and 60.1% on average in three network scenarios, respectively, compared with the best state-of-the-art algorithms.

Existing System

The per packet routing path serves as the meta-information for understanding detailed wireless networks behaviours in many network maintenance and Diagnosis situations, e.g., routing dynamics detection on Routing holes or wormholes or even per-hop per-packet, Transmission delay, network diagnosis etc. In the existing system, a Compressive-Sensing-based Path Reconstruction method was proposed, CSPR, which formalizes the sparse path representation and leverages compressive sensing to recover routing paths. CSPR lets intermediate nodes briefly annotate the transmitted packets and classifies packets traveling along different paths into different groups. For a particular path, the forwarded packets encode independent observations and CSPR performs compressive sensing to recover the path when a certain amount of packets (and the annotations) is collected. The path reconstruction by CSPR requires no interpacket correlations and utilizes only a small number of received packets. CSPR is thus invulnerable to topology dynamics and lossy links. On the protocol level, CSPR introduces only small and fixed overhead in annotating each packet, which could be optimized accordingly for practical WSNs. In addition to the basic design, it further propose a set of optimization techniques to gradually shrink the representation space and reduce the sparsity of unrecovered path vectors. The numbers of packets needed for remaining path reconstructions are lowered, and processing is thus accelerated. In the existing system, a compressive sensing based approach for path reconstruction (CSPR) technique is developed. It formalizes the sparse path representation and leverages compressive sensing to recover routing paths. It annotates the transmitted packets and classifies packets traveling along different paths into different groups. In the particular path the forwarded packet encoded and CSPR perform the compressive sensing to recover path when certain number of packets are collected. CSPR extracts 3-tuple key as sAddr, pLen, bFlt from the packet and classifies into a path group. At the sink CSPR manage all the path groups with database. If the keys in the database are matched with the received keys, the packet transmit to the sink. If the keys are not matched, then the entry for new path will generated and the packets are stored in the buffer. It utilizes only a small number of received packets.

Proposed System

Low-power and multihop wireless networking is envisioned as a promising technology to achieve both energy efficiency and easy deployment for many Internet of Things (IoT) applications. This project mainly ains to provide answers to three questions such as Key information source for path reconstruction, the proposed model can generate the relationship between the information sources, can easily design better algorithm. In the proposed system three different kinds of information source are used for path reconstruction. They are as follows, Path information only in p. Path information in multiple packets generated from the same original node. Multiple packets generated from the same original node are likely to follow the same path towards the sink. Such correlation is called as “temporal correlation”. Path information in multiple packets generated from different nodes. Multiple packets generated from a node and its forwarders are likely to follow the same subpath towards the sink. Such correlation is called as “spatial correlation”. In the proposed system, the source node send the packet to the destination node. The packet contains the path level information which facilitate many network management task. The routing path for the packet is obtained by the information encoded in the packets. For the better forwarding of the packets three better algorithms are proposed. cPathST provide the better performance compared with the other algorithms. cPathT exploits the temporal correlation and cPaths exploits the spatial correlation. cPathST is the combination of both the spatial and temporal correlation. It contains the following fields for encoding the information such as origin, pLen, aMsr, pathhash and parent.

Architecture

Architecture Diagram