PaperlayerView exact revision on arXiv

Source-linked AI summary

Nuzzer: A Large-Scale Device-Free Passive Localization System for Wireless Environments

Moustafa Seifeldin, Moustafa Youssef

arXiv:0908.0893v1cs.NIcs.PF

TL;DR

Device-free localization avoids attaching devices to tracked entities, while prior work focused on small or controlled environments. Nuzzer uses passive radio maps and probabilistic RSS-based inference in a large, multipath-rich office environment. It achieves a 1.82-meter median distance error using two laptops and three access points.

  • Problem

    Prior device-free localization studies focused on small areas with direct line of sight or controlled environments, leaving real multipath-rich settings to be addressed.

  • Method

    Nuzzer uses standard wireless networks to build a passive radio map and estimate the most probable location from received RSS using Bayesian-based inference.

  • Results

    1.82 meters median distance error was obtained in a 1500-square-meter multipath-rich office building using two laptops and three access points.

  • Takeaways & Limitations

    Nuzzer supports device-free location estimation in large real environments using standard wireless equipment and limited monitoring hardware.

Abstract

from arXiv · show

The widespread usage of wireless local area networks and mobile devices has fostered the interest in localization systems for wireless environments. The majority of research in the context of wireless-based localization systems has focused on device-based active localization, in which a device is attached to tracked entities. Recently, device-free passive localization (DfP) has been proposed where the tracked entity is neither required to carry devices nor participate actively in the localization process. DfP systems are based on the fact that RF signals are affected by the presence of people and objects in the environment. The DfP concept enables a wide range of applications including intrusion detection and tracking, border protection, and smart buildings automation. Previous studies have focused on small areas with direct line of sight and/or controlled environments. In this paper, we present the design, implementation and analysis of Nuzzer, a large-scale device-free passive localization system for real environments. Without any additional hardware, it makes use of the already installed wireless data networks to monitor and process changes in the received signal strength (RSS) transmitted from access points at one or more monitoring points. We present probabilistic techniques for DfP localization and evaluate their performance in a typical office building, rich in multipath, with an area of 1500 square meters. Our results show that the Nuzzer system gives device-free location estimates with less than 2 meters median distance error using only two monitoring laptops and three access points. This indicates the suitability of Nuzzer to a large number of application domains.

I. INTRODUCTION

Nuzzer addresses device-free localization in large, multipath-rich real environments, where indoor RF propagation and interference make localization challenging. It uses passive radio maps and probabilistic inference to estimate locations from RSS without requiring tracked entities to carry devices.

  • Device-free passive localization tracks entities without requiring them to carry devices or participate actively in localization.
  • Nuzzer presents a large-scale DfP system for real environments rich in multipath, extending prior work focused on small, direct-line-of-sight or controlled areas.
  • Indoor localization is difficult because walls, reflective materials, multipath fading, noise, and interference can unpredictably alter received signal strength.
  • Nuzzer targets high accuracy, ubiquitous coverage, scalability to large areas, and operation in real environments.
  • Nuzzer constructs a passive radio map to capture the complex relation between signal strength and distance in indoor environments.During online operation, it compares RSS samples received at monitoring points with the passive radio map to estimate the tracked entity’s location.
  • The system uses probabilistic techniques for single-intruder DfP localization and distinguishes them from device-based active localization techniques.

B. Contribution

The paper contributes probabilistic and post-processing algorithms for device-free localization, together with a large-scale evaluation and parameter study. Nuzzer operates through offline passive-radio-map construction and online RSS-based estimation using discrete and continuous estimators.

  • B. Contribution: The paper presents a probabilistic approach for device-free passive localization of a single intruder.
  • B. Contribution: It introduces post-processing techniques intended to enhance the accuracy of the basic probabilistic localization technique.
  • B. Contribution: The evaluation examines Nuzzer in a large-scale typical office environment rich in multipath and studies how system parameters affect localization performance.
  • A. Overview: Offline construction records a user’s effect on received data streams at radio-map locations without requiring the user to carry a device.
  • A. Overview: Online estimation uses RSS from each data stream and the passive radio map prepared during the offline phase.
  • A. Overview: The discrete estimator returns the calibrated radio-map location with maximum probability, while the continuous estimator post-processes it to estimate locations between calibrated points.

B. Mathematical Model

Nuzzer models device-free localization as finding the physical location most probable given a vector of received signal-strength readings. It builds per-location signal-strength histograms offline and evaluates candidate locations online, using multiple samples when available.

  • The model represents each user location x in a two-dimensional space and each observation as a q-dimensional vector s of stream readings.Each stream corresponds to an access-point and monitoring-point pair; samples from different streams are assumed independent.
  • Nuzzer constructs passive radio-map histograms for every stream at each calibrated location during the offline phase.These histograms describe signal strengths observed when a person stands at each radio-map location.
  • The online objective is to find the location x that maximizes the posterior probability P(x|s) for the received signal-strength vector.The system compares the observed vector with the probabilistic radio map to estimate the tracked entity’s location.
  • Assuming equally probable locations, Bayes’ theorem reduces the estimator’s objective to maximizing P(s|x).The prior P(x) is factored out under the equal-location-probability assumption.
  • The discrete estimator evaluates P(s|x) for each location using offline histograms and returns the location with maximum probability.Using m successive samples from each stream can improve performance.

D. Continuous Space Estimator

Nuzzer extends discrete localization into continuous space by averaging high-probability radio-map locations. The resulting estimate need not coincide with a calibrated radio-map location.

  • Nuzzer uses spatial and time averaging to produce continuous-space estimates when the entity is not standing at a radio-map location.These post-processing techniques are intended to increase localization accuracy.
  • Spatial averaging treats radio-map locations as probability-weighted physical objects and computes the center of mass of the k largest-probability locations.The parameter k controls how many locations contribute to the estimate.

1) Spatial averaging:

Spatial averaging converts the strongest discrete location probabilities into a continuous estimate, while time averaging smooths successive estimates. The time-window length trades latency against accuracy.

  • Spatial averaging: The radio map is ordered by normalized probability, and spatial averaging computes the center of mass of the top k locations.The estimate can therefore combine several high-probability locations rather than selecting only one.
  • Spatial averaging: The spatially averaged estimate need not be one of the original radio-map locations.This allows the estimator to represent positions between calibrated points.
  • Time averaging: Time averaging smooths estimates by averaging the last w outputs from either the discrete-space or spatial-averaging estimator.The window operates over a stream of successive location estimates.
  • Time averaging: The time-averaging window length affects both system latency and localization accuracy.

III. PERFORMANCE EVALUATION

Nuzzer was evaluated in a large, multipath-rich office environment using multiple estimators and a WiFi-based measurement setup. The experiment collected offline radio-map data and an independent online test set.

  • The evaluation compares Nuzzer’s discrete and continuous estimators with random and deterministic baseline estimators.The random estimator selects a location randomly, while the deterministic estimator uses nearest signal-strength matching against a radio map.
  • The testbed covered 1500 sq. m. of a typical office building containing furniture, plants, and substantial metal.The experiment took place in the main entrance and corridors.
  • The setup used three Cisco access points and two laptops acting as monitoring points in an 802.11b, 2.4 GHz environment.The access points were transmitting units, and the laptops were monitoring points.
  • RSSI values in dBm were collected from access points at five samples per second using active scanning.The system used RSSI rather than noise measurements.
  • The offline phase recorded 300 samples per stream at 53 locations, while an independent online test set covered 32 locations.There were six streams, one for each monitoring-point and access-point pair.
  • The experiment fixed the tracked person’s orientation throughout both offline and online phases.

C. System Parameters

Nuzzer tunes sample, stream, spatial, and temporal parameters to balance localization accuracy, latency, and available information. In the discrete estimator, probabilistic estimation achieves a 2.9m median distance error, while increasing samples improves accuracy at the cost of latency.

  • Default parameters: The default continuous-estimator parameters are n = 6, m = 26, k = 2, and w = 5, selected for the best combined performance.The continuous estimator adds spatial averaging over k locations and time averaging over a window w.
  • Discrete space estimator: 2.9m median distance error is achieved by the discrete space estimator, outperforming deterministic techniques by 2.9 times and the random estimator by 4.8 times.The comparison uses six data streams from three access points and two monitoring points.
  • Samples per stream: Increasing the samples per stream (m) decreases median distance error but increases latency because the estimator must wait for additional samples.A moving window can avoid waiting for m new samples by retaining m−1 older samples.
  • Number of streams: Increasing the number of streams (n) improves accuracy by providing more information about the environment.For each n, the figure reports the best result across stream combinations.

2) Impact of the number of streams:

More data streams improve Nuzzer’s accuracy, while continuous-space estimation further reduces error relative to discrete-space estimation. Spatial and temporal averaging also provide measurable improvements, with accuracy traded against latency for temporal averaging.

  • Number of streams: Increasing the number of streams improves accuracy because additional streams provide more information about the environment.The figure reports the best median error over possible stream combinations for each n.
  • Spatial averaging: Spatial averaging improves median distance error by 10% between k = 1 and k = 3.For larger k, the estimator becomes less sensitive because added locations receive substantially lower conditional probabilities.
  • Time averaging: A time-averaging window of w = 5 improves performance by 65% compared with w = 1, while larger windows increase latency.Temporal averaging therefore requires an accuracy–latency tradeoff.

2) Time averaging:

Nuzzer combines discrete estimation with continuous-space post-processing and spatial and temporal averaging. Using six data streams, it achieves high accuracy in large, multipath-rich areas while exposing tunable accuracy–latency tradeoffs.

  • Summary: 1.82 meters median distance error is achieved using six data streams in a non-LOS system covering large, multipath-rich areas.The six streams come from three access points and two monitoring points.
  • Averaging techniques: Spatial and temporal averaging are independent and can be combined to further enhance performance.The reported accuracy results from combining these techniques.
  • Accuracy–latency tradeoff: Parameters m and w can be tuned to balance accuracy and latency according to the deployment environment.m controls samples from each stream, while w controls the time-averaging window.
  • Limited hardware: Nuzzer maintains very good accuracy with as few as two available data streams, supporting deployments with limited hardware such as homes.This result concerns the number of raw data streams available to the system.

IV. RELATED WORK

Related localization systems commonly require attached devices, special hardware, line of sight, or controlled environments. Nuzzer instead targets large, typical environments using standard wireless networks without requiring the tracked entity to carry a device or maintain line of sight.

  • Nuzzer characteristics: Nuzzer tracks entities without attached devices or active participation, using standard wireless data networks and without requiring line of sight.RF signals penetrate walls, providing coverage beyond direct-LOS settings.
  • Computer vision systems: Video-camera localization is limited by darkness, smoke, occlusion, and out-of-sight entities, constraining range and scalability.These limitations are described for passive human localization using cameras.
  • Physical-contact systems: Physical-contact systems require special setup and hardware, limiting their scalability.Smart Floor is given as an example using pressure sensors in floor tiles.
  • Radar systems: Radar systems can provide accurate estimates but require special hardware, and their high complexity limits applications.UWB and MIMO radar systems use specialized waveforms or multiple transmit and receive elements.
  • Radio Tomographic Imaging: Radio Tomographic Imaging uses hundreds of raw data streams, measures attenuation, and loses accuracy as multipath increases because it is based on line of sight.Higher node density is used to overcome multipath effects.
  • Early DfP work: The initial DfP proof of feasibility achieved more than 86% tracking accuracy only in a small, highly controlled, one-dimensional environment.Nuzzer is presented as extending DfP to larger and less controlled settings.
  • Comparison with prior systems: Nuzzer’s distinguishing characteristics include high accuracy in typical large-scale environments, no special hardware, no LOS requirement, and operation with few raw data streams.These characteristics differentiate it from previous DfP systems.

V. CONCLUSIONS

Nuzzer combines passive radio mapping, Bayesian inference, and post-processing to localize device-free entities in real wireless environments. In a multipath office evaluation, it achieved a 1.82-meter median distance error while using standard wireless equipment.

  • System design: Nuzzer constructs a passive radio map offline and applies Bayesian inference to estimate the most probable entity location from received signal strengths.The system monitors and processes RSS from standard wireless networks without requiring tracked entities to carry devices.
  • Accuracy enhancement: Spatial and temporal averaging enhanced the basic Bayesian-based algorithm’s performance by 38%.These techniques are applied as post-processing methods to improve localization accuracy.
  • Evaluation: 1.82 meters was Nuzzer’s median distance error in a 1500-square-meter multipath office using two laptops and three access points.This error was 3.7 times better than deterministic techniques and 7.7 times better than a random estimator.
  • Evaluation: The presented techniques allowed Nuzzer to achieve its goals of high accuracy and operation in real environments.The conclusion ties the evaluated techniques to the system’s stated performance goals.
  • Deployment scope: Using standard wireless equipment, Nuzzer inherits the scalability and ubiquitous coverage of current wireless technologies.The conclusion attributes these properties to working with existing wireless equipment.
  • Future work: Future work includes multiple-entity tracking, automatic passive-radio-map generation, deployment optimization, and analysis of environmental and hardware changes.The authors also identify location clustering and further system expansion as ongoing directions.
Loading 0908.0893v1…