In this paper, we proposed a novel location estimation algorithm based on the concept of space-time signature matching in a moving target environment. In contrast to previous fingerprint-based approaches that rely on received signal strength (RSS) information only, the proposed algorithm uses angle, delay, and RSS information from the received signal to form a signature, which in turn is utilized for location estimation. We evaluated the performance of the proposed algorithm in terms of the average probability of error and the average error distance as a function of target movement. Simulation results confirmed the effectiveness of the proposed algorithm for location estimation even in moving target environment.
Recent growth of interest in pervasive computing with sensing and location-aware capabilities provides a strong motivation to develop new techniques for accurately estimating the location of devices in wireless sensor networks
. The Federal Communications Commission (FCC) has amended its rules to permit the use of improved radio frequency identification (RFID) systems to facilitate seaport security efforts
. One of the representative standards of these applications is the real-time locating system (RTLS) that is intended to provide an approximate location (within 3 m in a line-of-sight [LOS] environment) with frequent updates
Many wireless location techniques have been investigated and can be divided into two approaches: geometric-based techniques, such as angle of arrival (AOA)
, time of arrival (TOA)
, time difference of arrival (TDOA)
, and location fingerprinting approaches
. In the case of AOA, TOA, and TDOA, location estimation is based on triangulation techniques that require LOS between the transmitter and the receiver. However, in practical wireless environments, it is difficult to guarantee a LOS path between the transmitter and the receiver. Therefore, the estimation accuracy is considerably reduced in non-line-of-sight (NLOS) environments. On the other hand, location fingerprinting techniques solve the problems related to NLOS and multipath propagation by using a “ radio map” of the received signal strength (RSS) for a target environment. Thus, in this study, we focused on location fingerprinting approaches since they are more suitable for NLOS applications
. Unfortunately, most existing research has only used RSS information. The location is estimated by comparing the current measured data with the “ radio map” of the pre-measured database. However, this has limited value for some applications, such as outdoor scattering environments where radio signal propagation is very complicated because of severe multipath effects.
In this paper, we investigated a location estimation algorithm for RTLS consisting of RFID tags and multiantenna readers and propose a novel location estimation algorithm based on the concept of space-time signature matching in NLOS multipath environments. The proposed algorithm uses angle, delay, and RSS information from the received signal; this is in contrast to previous fingerprintbased approaches
, which rely on RSS information only to form a signature that is in turn utilized for location estimation. In
, we already proposed a location estimation algorithm based on space-time signature matching in NLOS environments. In this case we assumed there was no target movement, i.e., the target location was fixed. However, in real wireless environments, one cannot expect that a target location is fixed. Hence the target mobility scenario is a practical assumption. Therefore, this paper can be regarded as an extension of the previous study
to the more complicated scenario when there is a target random movement. We evaluated the performance of the proposed algorithm in terms of the average probability of error and the average error distance as a function of target movement. The organization of the paper is as follows. Section II provides a description of the system model. Section III describes the proposed location estimation algorithm based on the space-time signature matching technique and presents a detection method. In Section IV, simulation results are presented to verify the effectiveness of the proposed algorithm. Conclusions are given in Section V.
II. SYSTEM MODEL
- A. Overview of RTLS
RTLS is an automatic system that continually monitors the locations of objects. The system continually updates the database with current tag locations as frequently as every several seconds or as infrequently as every few hours depending on the mobility of the target tags
. The RTLS infrastructure, as shown in
, typically consists of RTLS transmitters (radio tags), RTLS receivers (readers), and the RTLS server. RTLS transmitters blink (or transmit) a direct sequence spread spectrum (DSSS) signal, and RTLS readers, whose locations are fixed, receive signals from the tags. The RTLS server aggregates data from the RTLS readers and determines the tag’s current location.
In this paper, we assume that each reader is equipped with an array of
antennas that can adopt space-time signal processing. We consider a complicated NLOS multipath propagation scenario.
Elements of real-time locating system infrastructure. Tags are regularly spaced for illustration.
- B. Space-time Communication
We assume that
tags are randomly distributed in a certain area and
readers are placed near the circumference of the area, for example, on the corners of the service area (
). Each reader, equipped with an
- element antenna array, is assumed sufficiently far from most of the tags in the same plane so that far-field assumptions apply.
readers receive the signal from a tag to estimate its location. Each tag transmits a spread spectrum signaling waveform s(t) of duration
[s] and (two-sided) bandwidth
N = TW
>> 1 denote the timebandwidth product of the signaling waveforms representing the approximate dimension of the spatiotemporal signal space. Thus, the signal space of the space-time waveforms has the dimension
MN = MTW
. We make a practical assumption that the readers and tags are frequency (f
) synchronized but not phase synchronized. Furthermore, we assumed that the phase offset between each tag and the reader stays constant for at least the packet duration
. A tag transmits the spread of the spectrum signal to update its status.
III. LOCATION ESTIMATION ALGORITHM
- A. Space-time Signature Matching
In this paper, we propose a novel method based on spacetime signature matching to accurately estimate the location by utilizing not only the RSS but also the angle and delay information of the received signal.
The proposed space-time signature matching algorithm is carried out in two steps. In the first step, reference signatures are generated for every reference point. A tag at an unknown location can then be estimated by comparing the signature generated from the received signal with the reference signatures. We assume that there are
Step 1: reference signature database generation
Step 2: location estimation process
Place a transmitter at one of the reference positions and let it transmit a known spread spectrum waveform.
Readers receive the waveform and generate a signature vector of this location. Denoted byΨi(k), the signature vector of thei-th reference point is measured at thek-th reader.
These signaturesΨi(k),k= 1,2, … . ,Kalong with the corresponding reference coordinates (xi, yi) are saved in the database located in the server.
Move to the next reference point until all reference points,i= 1,2, … . ,Nrare visited.
Thus, forNrreference points, the database consists ofNrKsignature vectors,Ψi(k),i= 1,2. … ,Nr,k= 1,2, … . ,K.
Once the reference signatures are obtained, we can locate a tag at an unknown position as follows.
A tag at an unknown location transmits a known waveform and the readers compute a signature
,k= 1,2, … . ,Kbased on the received signal.
Compare the currently computed signature with the reference signatures in the database.
Estimate the unknown tag’s location by finding the location in the database whose signatures are closest to the currently obtained signature. All information (i.e., angle, delay, and RSS information at each reader) is used or combined to estimate the tag location.
- B. Path Partitioning in Angle and Delay
The main concept of our algorithm is that the estimation accuracy can be greatly improved by working with a detailed signature of the scattering environment. The detailed signature consists of the angle, delay, and path gain associated with each scatterer, which provides more information to the estimator than the conventional RSSbased methods. Such information buried in the regular channel vector or matrix clearly shows up in the virtual channel vector.
A key property of the virtual channel representation is that its coefficients represent a resolution for the multipath in angle and delay commensurate with the signal space parameters M and W , respectively
. The angledelay virtual representation partitions the multipath responses into distinct angle-delay resolution bins.
- C. Generation of Signature Vector
The signature vector is what we eventually use to estimate the location. It is computed from the received signal at each reader, as illustrated in
. A more detailed description of the generation of the signature vector is given in
Computation of the signature vector: angle-delay matched filtering.
} is stacked to generate the
x 1 dimensional signature vector
. The signature vector
- th reference point at the
-th reader is formed by placing those matched-filter outputs as
. This yields a database of
reference locations and
After obtaining signature vectors from all reference points, the readers constantly monitor the field. When a strong signal is detected, each reader forms a signature vector
from the received signal. The maximum likelihood decision for the location is then made. We considered noncoherent detection to be a detection method.
- D. Non-coherent Detection
When a tag of unknown location is placed at one of
reference points, the detection of its location is equivalent to an
-ary hypothesis testing as
, ... ,
represent an observed signature and a reference signature at the
-th reference point, respectively, and the noise vector
consists of a zero-mean and σ
variance i.i.d. complex Gaussian random variables.
The probability density function (pdf) of
where ll·ll represents the Euclidean norm of a vector. Hence the maximum likelihood estimation of the tag location is made as follows:
which implies that the maximum likelihood decision is equivalent to simply finding a reference signature that is closest to the observed signature.
The coherent detection method in (3) is optimal only in ideal settings. That is, in order for the method to produce a good estimate of the location, two conditions should be satisfied. First, the transmitter and receiver should be phase-synchronized. A mismatch in the phase of the carrier causes a phase shift in the entries of a signature matrix. The phase shift of entries of
can induce a large error in the Euclidean norm of the difference between the observed and reference signatures in (3). Second, a tag should be placed exactly at one of the reference points. Otherwise, even a short distance may induce a significant phase shift and deteriorate the estimate accuracy. For example, if a tag is placed 10 cm from a reference location, it corresponds to
radians of phase shift when a 2 GHz carrier frequency is used. However, both conditions are difficult to satisfy in practical situations. This motivates the development of a new location estimation method that is resilient both to the carrier phase mismatch and to the location offset.
For the reasons discussed above, we cannot rely on the phase part of the entries of the signature matrices, but should base our decision on their magnitude. Although we discard the phase part, we still can distinguish locations because different locations induce different delays and angles-of-arrival, which appear as nonzero elements at different bins with different strengths in the signature matrices.
In the new method, which we term non-coherent detection, we form a database of variance matrices at reference points instead of that of signature matrices. Variance matrices can be estimated by transmitting a known signal a number of times in the vicinity of each reference point. We estimate the
in the absence of noise for the
th reference point and the
th reader as
is the measurement index and
is the number of measurements used in averaging. In the presence of noise, the estimated variance
is the sum of error-free variance
and noise variance σ
. Using this, we model the distribution of a signature matrix at the
th reference point as,
and we assume that the variance matrix is diagonal, which follows from the path partitioning explained in Section III-B. We further assume the mean to be zero because of the randomness of the phase part of a signature matrix. Denoting by
the pdf of a signature matrix when
is the true tag location becomes
This leads to the maximum likelihood detection of
We can obtain the upper-bound of the error probability for non-coherent detection as
From (5) and (7), one can see that
is completely determined by
, respectively. This probability has exactly the same formulation as the error probability of a covariance matrix-based binary hypothesis test, and the closed form solution is as follows:
th eigenvalue of
are the index sets of positive and negative
's, respectively, and
IV. SIMULATION AND DISCUSSIONS
- A. Generation of Multipath Channel
We considered a field of a 300 × 300 m square region. We assumed that reference tags were randomly distributed over the region, and four readers equipped with five antennas each were placed in the corners of the region. Twenty rectangular-shaped scatterers were placed inside the region in a random manner. We measured the signature vectors at the reference tag positions separated by 3 m. In order to generate realistic multipath channel realizations that are suitable for wireless environments, we developed a site-specific channel simulator based on the deterministic 2D ray-tracing technique. A more detailed description of the multipath channel realizations is explained in
- B. Performance Evaluation
The effectiveness of this approach for enhancing the accuracy of location estimation in NLOS environments was validated through computer simulation. In the simulation, 1,135 tags were considered to be reference positions and the transmit signal-to-noise ratio (TXSNR) was used as a SNR criterion. The estimation performance of the proposed algorithms was evaluated in terms of the average probability of error and the average error distance
, respectively, represent the true and estimated coordinate of a tag and
(·,·) denotes the Euclidean distance.
compare the estimation performance of coherent detection
and non-coherent detection algorithms for different tag mobility scenarios: fixed location and random movement. For the fixed-location scenario, tags of unknown location were placed exactly at one of the reference points and the location was estimated. In the random movement scenario, they were placed on the circle of a certain radius centered at one of reference points, and the estimation was carried out. In real settings, one cannot expect tags attached to containers, for example, to be placed exactly (i.e., within 0.01 m) at the reference points. Hence the random movement scenario is a practical assumption.
illustrates the effect of random movement of a tag on the average error probability for M = 5 and K = 4. It can be observed that the estimation performance of coherent detection is superior to that of non-coherent detection if there is no or negligible movement (i.e., 0.01 m). However, the performance of coherent detection drastically degrades with meaningful movement (i.e., 0.05 m or more) regardless of the system bandwidth (i.e., delay resolution) and TXSNR. This is due to the sensitivity of the Euclidean norm on the phase part of a vector. For example, two complex vectors [a
] and [a
] are close, in terms of the norm, when θ
≈ 0 and θ
≈ 0, but far apart when θ
≈ π or θ
≈ π . Hence, non-coherent detection, which does not rely on the phase, is expected to perform better than coherent detection. The figure clearly shows that coherent detection performs extremely well when the tags are placed less than 0.05 m from the reference points but becomes useless beyond this range. On the other hand, non-coherent detection shows a reasonably good error probability of 0.04 even when placed 0.4 m from the reference points. The figure also reveals the dependence of the performance on delay resolution and TXSNR. As expected, the performance is better with finer delay resolution (10 ns) and about a three-fold increase in the delay resolution affords much greater improvement than the 10 dB TXSNR increase.
Average error probability of location estimation; comparison between coherent detection and non-coherent detection as a function of tag movement.
shows the effect of random movement of a tag on the average error distance for M = 5 and K = 4. We investigate the error distance because it is important whether the erroneous location estimation is the close neighbor of the true location or not. The RTLS specification also describes the requirement in terms of error distance. This figure shows that the average error distance behaves similarly to the average error probability. An interesting observation is that non-coherent detection performs much better than the average error probability graph implies. The error probability was about 10 to 20% with a 32 ns delay resolution and 15 or 25 dB TXSNR at 0.4 m from the reference points. However, the average error distance is only about 1 or 2 m. This implies that the errors mostly occur at the immediate neighbors of the true location.
Average error distance of location estimation; comparison between coherent detection and noncoherent detection as a function of tag movement.
In this paper, we investigated location estimation algorithms for real-time location systems and proposed a novel location estimation algorithm based on the space-time signature matching in a moving target environment. We derived the upper-bound of the average error probability for non-coherent detection and carried out simulations. A 2D ray tracing technique was used in generating multipath channel realizations. Simulation results show that when tags are placed exactly at the reference points, coherent detection works much better than non-coherent detection. However, when they are placed even a fraction of 0.1 m from the reference points, one should use the non-coherent detection algorithm, which provides an accuracy of less than 2 m with most practical system parameters when reference point spacing is 3 m.
Kanter T. G
“ Attaching context-aware services to moving locations”
IEEE Internet Computing
Schiller J. H
Morgan Kaufmann Publishers
Oh C. H
“ Location estimation using space-time signal processing in RFID wireless sensor networks”
Proceedings of the 2011 FTRA World Convergence Conference
Campos L. M
Harris J. L
Rissetto C. L
FCC provides access to better RFID technology to port security: federal funding for this new tool may be available [Internet]
Information Technology ? Real Time Locating Systems (RTLS) ? Part 2: 2.4GHz air interface protocol
Krizman K. J
Biedka T. E
Rappaport T. S
“ Wireless position location: fundamentals, implementation strategies, and sources of error”
Proceedings of IEEE 47th Vehicular Technology Conference
Chen P. C
“ A non-line-of-sight error mitigation algorithm in location estimation”
Proceedings of IEEE Wireless Communications and Networking Conference
New Orleans, LA
“ Non-line-of-sight error mitigation in TDOA mobile location”
Proceedings of IEEE Global Telecommunications Conference
San Antonio, TX
Lin T. N
Lin P. C
“ Performance comparison of indoor positioning techniques based on location fingerprinting in wireless networks”
Proceedings of International Conference on Wireless Networks, Communications and Mobile Computing
“ Modeling of indoor positioning systems based on location fingerprinting”
Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies
“ Location fingerprinting on infrastructure 802.11 wireless local area networks location fingerprinting on infrastructure 802.11 wireless local area networks”
Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks
“ Distribution of WLAN received signal strength indication for indoor location determination”
Proceedings of the 1st International Symposium on Wireless Pervasive Computing
Technology: real-time locating systems [Internet]
Association for Automatic Identification and Mobility
Sayeed A. M
“ Deconstructing multiantenna fading channels”
IEEE Transactions on Signal Processing
Sayeed A. M
“ A virtual representation for time- and frequencyselective correlated MIMO channels”
Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing
Sayeed A. M
“ Active wireless sensing: spacetime information retrieval from sensor ensembles”
Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing
Kay S. M
Upper Saddle River
NJ: Prentice Hall