Properly locating sensor nodes is an important building block for a large subset of wireless sensor networks (WSN) applications. As a result, the performance of the WSN degrades significantly when misbehaving nodes report false location and distance information in order to fake their actual location. In this paper we propose a general distributed deterministic protocol for accurate identification of faking sensors in a WSN. Our scheme does rely on a subset of nodes that are not allowed to misbehave and are known to every node in the network. Thus, any subset of nodes is allowed to try faking its position. As in previous approaches, our protocol is based on distance evaluation techniques developed for WSN. On the positive side, we show that when the received signal strength (RSS) technique is used, our protocol handles at most @math faking sensors. Also, when the time of flight (ToF) technique is used, our protocol manages at most @math misbehaving sensors. On the negative side, we prove that no deterministic protocol can identify faking sensors if their number is @math . Thus our scheme is almost optimal with respect to the number of faking sensors. We discuss application of our technique in the trusted sensor model. More precisely our results can be used to minimize the number of trusted sensors that are needed to defeat faking ones.
Relaxing the assumption of trusted nodes makes the problem more challenging, and to our knowledge, has only been investigated very recently @cite_19 . We call this model where no trusted node preexists the (or ) model. The approach of @cite_19 is randomized and consists of two phases: distance measurement and filtering. In the distance measurement phase, sensors measure their distances to their neighbors, faking sensors being allowed to corrupt the distance measure technique. In the filtering phase each correct sensor randomly picks up @math so-called sensors. Next each sensor @math uses trilateration with respect to the chosen pivot sensors to compute the location of its neighbor @math . If there is a match between the announced location and the computed location, the @math link is added to the network, otherwise it is discarded. Of course, the chosen pivot sensors could be faking and lying, so the protocol may only give probabilistic guarantee.
@cite_19
2131007986 2101191125 2128445255 2161249924
Wireless sensor networks are deployed for the purpose of monitoring an area of interest. Even when the sensors are properly calibrated at the time of deployment, they develop drift in their readings leading to erroneous network inferences. Based on the assumption that neighbouring sensors have correlated measurements and that the instantiations of drifts in sensors are uncorrelated, the authors present a novel algorithm for detecting and correcting sensor measurement errors. The authors use statistical modelling rather than physical relations to model the spatio-temporal cross-correlations among sensors. This in principle makes the framework presented applicable to most sensing problems. Each sensor in the network trains a support vector regression algorithm on its neighbours' corrected readings to obtain a predicted value for its future measurements. This phase is referred to here as the training phase. In the running phase, the predicted measurements are used by each node, in a recursive decentralised fashion, to self-assess its measurement and to detect and correct its drift and random error using an unscented Kalman filter. No assumptions regarding the linearity of drift or the density (closeness) of sensor deployment are made. The authors also demonstrate using real data obtained from the Intel Berkeley Research Laboratory that the proposed algorithm successfully suppresses drifts developed in sensors and thereby prolongs the effective lifetime of the network. This paper focuses on the principled study of distance reconstruction for distance-based node localization. We address an important issue in node localization by showing that a highly incomplete set of inter-node distance measurements obtained in ad-hoc node deployments carries sufficient information for the accurate reconstruction of the missing distances, even in the presence of noise and sensor node failures. We provide an efficient and provably accurate algorithm for this reconstruction, and we show that the resulting error is bounded, decreasing at a rate that is inversely proportional to radicn, the square root of the number of nodes in the region of deployment. Although this result is applicable to many localization schemes, in this paper we illustrate its use in conjunction with the popular multidimensional scaling algorithm. Our analysis reveals valuable insights and key factors to consider during the sensor network setup phase, to improve the quality of the position estimates We explore fundamental performance limits of tracking a target in a two-dimensional field of binary proximity sensors, and design algorithms that attain those limits. In particular, using geometric and probabilistic analysis of an idealized model, we prove that the achievable spatial resolution Δ in localizing a target's trajectory is of the order of 1overρ R, where R is the sensing radius and ρ is the sensor density per unit area. Using an Occam's razor approach, we then design a geometric algorithm for computing an economical (in descriptive complexity) piecewise linear path that approximates the trajectory within this fundamental limit of accuracy. We employ analogies between binary sensing and sampling theory to contend that only a "lowpass" approximation of the trajectory is attainable, and explore the implications of this obervation for estimating the target's velocity.We show through simulation the effectiveness of the geometric algorithm in tracking both the trajectory and the velocity of the target for idealized models. For non-ideal sensors exhibiting sensing errors, the geometric algorithm can yield poor performance. We show that non-idealities can be handled well using a particle filter based approach, and that geometric post-processing of the output of the Particle Filter algorithm yields an economical path description as in the idealized setting. Finally, we report on our lab-scale experiments using motes with acoustic sensors to validate our theoretical and simulation results. This paper describes a distributed, linear-time algorithm for localizing sensor network nodes in the presence of range measurement noise and demonstrates the algorithm on a physical network. We introduce the probabilistic notion of robust quadrilaterals as a way to avoid flip ambiguities that otherwise corrupt localization computations. We formulate the localization problem as a two-dimensional graph realization problem: given a planar graph with approximately known edge lengths, recover the Euclidean position of each vertex up to a global rotation and translation. This formulation is applicable to the localization of sensor networks in which each node can estimate the distance to each of its neighbors, but no absolute position reference such as GPS or fixed anchor nodes is available. We implemented the algorithm on a physical sensor network and empirically assessed its accuracy and performance. Also, in simulation, we demonstrate that the algorithm scales to large networks and handles real-world deployment geometries. Finally, we show how the algorithm supports localization of mobile nodes.