RF Sensor Networks for Device-Free Localization_ Measurements, Models, and Algorithms

INV ITED P A P E R RF Sensor Networks for Device-Free Localization: Measurements, Models, and Algorithms This paper considers situations where a person or an object can be examinedVeven in buildings and through wallsVbecause a wireless network uses RF signals as a probe. By Neal Patwari and Joey Wilson ABSTRACT | In this paper, we discuss the emerging applica- tion of device-free localization (DFL) using wireless sensor networks, which find people and objects in the environment in which the network is deployed, even in buildings and through walls. These networks are termed ‘‘RF sensor networks’’ because the wireless network itself is the sensor, using radio- frequency (RF) signals to probe the deployment area. DFL in cluttered multipath environments has been shown to be feasible, and in fact benefits from rich multipath channels. We describe modalities of measurements made by RF sensors, the statistical models which relate a person’s position to channel measurements, and describe research progress in this area. KEYWORDS | Fading; multistatic radar; radiowave propagation; sensor systems and applications; signal processing; wireless sensor networks I . INTRODUCTION Wireless networks are ubiquitous. Wherever we are, we are interacting with radio-frequency (RF) electromagnetic (EM) waves. In this paper, we review efforts to use the changes caused by people’s interaction with the RF EM wave field to infer their position. We call the static wireless devices used for this purpose ‘‘RF sensors,’’ because they are used to measure the signal on each link between devices. Such a network we call an RF sensor network, as opposed to the term ‘‘wireless sensor network,’’ which refers to a general-purpose network of sensors. This area of research is also called ‘‘device-free’’ localization (DFL) [1] to emphasize that a person1 does not need to be carrying a wireless device to be detected and located, or ‘‘sensorless sensing’’ because sensor network researchers typically do not consider the radio to be a sensor [2]. With or without a radio transmitter (TX) or receiver (RX) on them, a person’s presence at a location affects the radio waves nearby. This area is related to radar, including ultrawide- band (UWB) and multiple-input–multiple-output (MIMO) radar systems, but is not limited to these frameworks. There is an advantage to sensing RF energy as opposed to light, infrared, or thermal energy when attempting to infer people’s movements. Visible light cameras largely depend on daylight; light and infrared do not penetrate smoke. RF waves can penetrate nonmetal walls and smoke [3], unlike light, thermal, or millimeter-wave energy. Thus, RF-based DFL is a complementary security technology which does not require floodlights to work at night, and can locate people in a smoke-filled building, or from the exterior of the building. Other radio-based localization technologies exist, sometimes labeled as real-time location Manuscript received December 7, 2009; revised March 26, 2010; accepted May 23, 2010. Date of publication July 26, 2010; date of current version October 20, 2010. This work was supported by the National Science Foundation under Grant #0748206. The authors are with the Department of Electrical and Computer Engineering, University of Utah, Salt Lake City, UT 84112 USA (e-mail: npatwari@ece.utah.edu; joey@xandem.com). Digital Object Identifier: 10.1109/JPROC.2010.2052010 1In this paper, we use ‘‘person’’ to refer generically either to a person or a mobile object. Vol. 98, No. 11, November 2010 | Proceedings of the IEEE 19610018-9219/$26.00 �2010 IEEE systems (RTLSs), which require each person or object to be attached to a radio transmitter tag, which is then located based on the signals received from that tag at multiple other sensors [4]. However, in security or emergency applica- tions, one cannot expect all people of interest to be wearing a radio tag. With these advantages, DFL has several applications. DFL technologies may complement existing localization systems which use tags to locate and identify people by combining RF sensor measurements from two sources: 1) from signals received from the transmitter tag, and 2) measurements between the static RF sensors. As such, DFL may improve existing RTLSs. As another example, DFL techniques may be useful for police or emergency responders approaching a dangerous building. Prior to entering, they may wish to deploy an RF sensor network around the building, either independently from, or in concert with, an existing wireless network in the building. Then, they can use DFL techniques to locate and track people moving within the building. As another example, RF sensor networks may be deployed within large buildings and facilities, as an alternative to more invasive video camera networks, in order to ensure compliance with safety and security rules. These networks may work in concert with context-aware computing and control systems to prevent accidents, and protect confidential information. An RF sensor network effectively measures many sections of the environment because many links between pairs of radios exist in an area, and each link measures a different section of space. Thus, the word tomography, defined as imaging by sections, applies to estimation in RF sensor networks. However, RF radio wave propagation is not solely by line-of-sight (LOS) propagation [5]. In fact, we typically expect the power in non-line-of-sight (NLOS) paths to dominate, except in unobstructed short-range links [6]. Thus, computed tomography (CT) techniques developed for X-ray scanners, which assume that each measurement is along a straight line through the medium [7], do not directly applyVwe cannot simply scale up the size of an area, scale down the frequency of emission, and achieve proportional results. Yet, as we describe in this paper, a significant quantity of research has shown results that locate people in build- ings using RF sensor measurements [1], [2], [8]–[17]. Results have been presented which count the number of people moving [9], estimate a person’s location [13], [14], [17], [18], and image the movements in an area of interest [11]–[13], [15], all in real-world multipath environments. Both location estimation (estimating a person’s coordinate at one time) and tracking (estimating a person’s velocity and sequence of positions over a duration of time) have been reported, with accuracy of less than 1 m of average error [8], [13], [14] or less than 2 m median error over a 1500-m2 area [17]; these results are at least as good as reported location error when locating radio tagged objects [4], [19], so the accuracy is surprising. How are these systems able to counteract the effects of multipath in an effort to track movement? The answer to this question is that successful DFL systems have been designed to take advantage of the effects of multipath propagation, rather than try to counteract them. Multipath fading becomes the signal, not the noise. We show in this review paper how multipath fading is used for the benefit of DFL systems. We present the results of the growing literature for DFL in three parts, first discussing the RF sensor measurement modalities in Section II, then pre- senting models for the measurements in Section III, and then presenting the algorithms and results in Section IV. Finally, we conclude in Section VI. II . MEASUREMENTS DFL employs networks which measure properties of the radio channel between many pairs of RF sensors. Changes in channel properties provide information about the position of objects in the environment. What types of radio channel measurements are most appropriate for DFL? In this section, we introduce several modalities of measurements of radio channel characteristics which can be used to infer the location of people and objects in a building. We discuss the advantages and disadvantages of these modalities. A. Ultrawideband First, we discuss the use of UWB measurements for purposes of DFL. UWB receivers measure the amplitudes, time delays, and phases of the multipath signals which exist in the radio channel. Measured at multiple probing times t, UWB measurements and the changes between them can be used to infer both the properties of the static propagation environment, and the changes in the envi- ronment which might indicate a moving person or object. UWB transceivers are certainly more cost-prohibitive than narrowband transceivers, but the ability to distinguish time delay is a key benefit. Transmitting and receiving a UWB pulse (or for that matter, high bandwidth signal) allows one to measure the channel impulse response (CIR). Assume at time t, NðtÞ multipath components arrive at the RX, with the ith component having complex amplitude gain of �iðtÞ and time delay �iðtÞ. As a complex value, �iðtÞ can be written as j�iðtÞj exp½jff�iðtÞ�. The CIR is [5] hðt; �Þ ¼ XNðtÞ i¼1 �iðtÞ� � � �iðtÞð Þ (1) where �ð�Þ is the Dirac impulse function. The knowledge of time delay provides important information about position. Comparing the delay �iðtÞ to the LOS time delay (assuming it is known) indicates the excess delay, which gives some knowledge of the spatial Patwari and Wilson: RF Sensor Networks for Device-Free Localization: Measurements, Models, and Algorithms 1962 Proceedings of the IEEE | Vol. 98, No. 11, November 2010 incidence of the ith multipath. For example, if the path was assumed to result from a single ‘‘bounce,’’ i.e., change in direction, then that object that caused the bounce is located somewhere on an ellipse of a certain size, with the TX and RX as foci [20]. When time delay is measured on multiple links, the intersection between ellipses is an estimate of the object location. B. Narrowband Next, we discuss narrowband channel measurements for purposes of DFL. Narrowband receivers cannot provide information about individual multipath, only the signal magnitude and phase as a whole. However, narrowband transceivers are produced in high quantity for commercial applications, thus their low cost is a key part of enabling large-scale RF sensor networks. Narrowband wireless devices simply measure the sum of the contributions of all multipath. We consider a continuous-wave (CW) signal, which results in a received complex baseband voltage ~V of ~V ¼ VT XNðtÞ i¼1 �iðtÞ ¼ XNðtÞ i¼1 ViðtÞ (2) where VT is the complex baseband voltage at the TX, and ViðtÞ ¼ VT�iðtÞ is the complex baseband voltage of com- ponent i at the RX [5]. There is information about position contained in ~V. First, the information in the magnitude of ~V will be discussed below. Second, ~V, when compared to the ~V measured at other RX locations or at multiple antennas, provides information about the azimuth or elevation angles-of-arrival of the multipath signals [21], and can be used in multiple wave field reconstruction techniques as discussed in Section IV-B. Typical distributed wireless sensors have difficulty with accurate timing synchronization [22], and for coherent phase measurements, phase synchronization is required. Phase synchronization means that the carrier used by two different transceivers must have the same phase. Since the carrier phase changes from 0 to 2� each carrier cycle, timing synchronization errors must be much less than 1=fc, where fc is the carrier frequency. For example, at 900 MHz, timing errors must be much smaller than 1 ns. A future challenge in DFL is to either provide practical means for phase-coherent measurements of ~V at disparate sensors, such as interferometric methods [23], or to achieve some of the benefits of phase-coherent measurements using noncoherent measurements. C. Received Signal Strength (RSS) In this section, we consider measurements of RSS for purposes of DFL. Compared to the narrowband measure- ments presented above, RSS is a magnitude-only measure- ment. Measurements of RSS are ubiquitous in nearly all wireless devices. The received power is the squared magnitude of the complex baseband voltage ~V. What we typically call the RSS is a measurement of the received power in decibel terms. For a narrowband receiver, this power is RdB ¼ 20 log10 j~Vj ¼ PT þ 20 log10 XNðtÞ i¼1 �iðtÞ ����� ����� (3) where PT ¼ 20 log10 jVTj. One source of information in RdB is its magnitude. For links with a strong LOS component, when that strong component is blocked, RdB tends to decrease. This is called shadowing, and a sharp decrease in RdB can be used to infer that a person or object is located along the LOS path [11]. Further, multipath fading is a source of location information. Depending on the phases of each ViðtÞ, the sum in (2) may be destructive (with opposite phases) or constructive (with similar phases). Measurements of fading are one source of information about the location or number of moving people in the environment, as discussed in Section IV. Fading can be quantified, for example, with the variance of RdB [9], [13], by the absolute value of differences [8], [24], or even the link quality indicator (LQI) [9]. The variance of RdB has been shown to be approxi- mately linearly related to the total power in multipath components affected by the movement in the environ- ment [25]. We will discuss what is meant by ‘‘affected’’ and provide models for the effect in Section III-D. Although individual RSS measurements are less informative about person location than UWB measure- ments, for example, the low cost of RSS-only narrowband radios will allow more nodes for a given price. Since measurements are made between pairs of RF sensors, the number of measurements increases as OðN2Þ, and the overall capability of the RF sensor network can be very significant. D. Polarization Finally, we consider the DFL information contained in the polarization of the EM wave at the RX. The polar- ization is useful to detect movement in the environment [26]. The polarization of an EM wave at the RX will change due to environmental changes just as the phase of the signal will change. Using two orthogonally polarized antennas, an RX can measure both relative amplitudes and the phase between the two signals. Just like in (2), each polarized received signal has multipath component amplitudes and phases. These two measurements deter- mine a point on a Poincare´ sphere. The ‘‘differential polarization’’ can be determined by finding the angular Patwari and Wilson: RF Sensor Networks for Device-Free Localization: Measurements, Models, and Algorithms Vol. 98, No. 11, November 2010 | Proceedings of the IEEE 1963 change from an original polarization state to the current state. This differential can be calculated either with a time average, or a frequency-domain subband average. The latter is shown in [26] to provide a higher signal-to-noise ratio for detection of human-caused changes. III . MODELS All of the measurements described in Section II map changes in multipath components in order to locate and count the number of moving people (or objects) in the environment. Consider a person located at coordinate xo, and a link with TX location xt and RX location xr, as depicted in Figs. 1 and 2. In this section, we consider models for the relationship between changes caused to the multipath components by the person, and coordinate of the person xo. Certainly, if changes are not a function of xo, we have no ability to locate the person. It is thus critical to have models to describe the changes in measurements as a function of position xo. There are generally two views on the formulation of this position dependence. 1) Relative position dependence: The channel param- eters are only a function of the relative position of xo to TX and RX positions xt and xr. For example, the parameters may only be a function of the dis- tances kxo � xtk and kxo � xrk. These assump- tions are used in the algorithms presented in Sections IV-B–H. 2) Absolute position dependence: The channel param- eter dependence cannot be simplified using the relative positions of xo, xt, and xr [1], [10], [17], [18]. In the latter case, the dependence of the measurement on xo must be determined for every link (and thus xt and xr), and for the entire range of xo, for each environment. Channel measurements are very sensitive to the place- ment and EM properties of all objects in the environ- ment, and these positions and properties are highly likely to be unknown. Thus, measurements are required, at a high density of positions xo. For multiple people, the channel will have to be measured for all combinations of human locations. Algorithms which have this perspective are called fingerprint-based DFL, and are discussed in Section IV-A. From the relative position dependence perspective, a statistical model describes the relationship between the channel changes experienced on a given link and xo, relative to xt and xr. If knowledge about environmental objects is available (e.g., wall locations) their relative positions with respect to (w.r.t.) xt and xr can also be used in the propagation model [27]. While not every link will experience the same changes given identical relative position information, if measured for many links, the distribution of changes should be characterized by the model. Such a statistical model could be generated from theory, or from many sets of measurements. We do not suppose that a statistical model is accurate for all environments. True EM simulation or ray tracing might be used if the properties, size, and position of objects in the environment were known. Or, perhaps these parameters can be considered ‘‘clutter’’ and measured so that a scatterer’s position can be determined regardless [28], [29]. Statistical models are required when the complexity of typical static environments cannot be accurately determined. Algorithms which do not make multipath propagation assumptions are discussed further in Section IV-B. To formulate multipath channel models which provide position dependence, we primarily need to consider their spatial impact, rather than time delay and amplitude [25].We denote SiðtÞ as the spatial filter of path i at time t. Generally, we model SiðtÞ as series of connected line segments, rep- resenting a plane wave changing direction at discrete points. Finally, to simplify the language, we simply refer to all objects which interact with a wave via transmission, diffraction, reflection, or scattering, as ‘‘scatterers,’’ regardless of the actual propagation mechanism. A. Related Research Fading models for static links dependent on the position of moving people are less prevalent than those for frequency- dependent fading or for space-dependent (small-scale) fading models. However, the reported literature has observations relevant to DFL, which we relate in this section. Fig. 1. (a) Example multipath components between TX at xt and RX at xr . (b) When a person appears at xo, there are additional paths ð����Þ and alterations to existing multipath ð� � �Þ. Fig. 2. TX, RX, plane containing scatterers, and the new person. Patwari and Wilson: RF Sensor Networks for Device-Free Localization: Measurements, Models, and Algorithms 1964 Proceedings of the IEEE | Vol. 98, No. 11, November 2010 In past studies, fading due to human motion was quan- tified to aid in the design of static communications systems which operate among moving people, e.g., indoor wireless local area networks (WLANs) [30]–[33]. For indoor communications links, fading on a static link typically follows a Ricean mixture distribution, with a high variance when people are moving in and around the area of the link, and a low variance when they are not [30]. The Ricean K-factor depends on the power in ‘‘stationary’’ paths versus power in ‘‘time-