In this paper, we proposed a novel location estimation algorithm based on the concept of spacetime signature matching in a moving target environment. In contrast to previous fingerprintbased 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.
I. INTRODUCTION
Recent growth of interest in pervasive computing with sensing and locationaware capabilities provides a strong motivation to develop new techniques for accurately estimating the location of devices in wireless sensor networks
[1

3]
. 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
[4]
. One of the representative standards of these applications is the realtime locating system (RTLS) that is intended to provide an approximate location (within 3 m in a lineofsight [LOS] environment) with frequent updates
[5]
.
Many wireless location techniques have been investigated and can be divided into two approaches: geometricbased techniques, such as angle of arrival (AOA)
[6]
, time of arrival (TOA)
[7]
, time difference of arrival (TDOA)
[8]
, and location fingerprinting approaches
[9
,
10]
. 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 nonlineofsight (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
[9
,
11
,
12]
. 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 premeasured 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 spacetime 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
[9

12]
, which rely on RSS information only to form a signature that is in turn utilized for location estimation. In
[3]
, we already proposed a location estimation algorithm based on spacetime 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
[3]
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 spacetime 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
[13]
. The RTLS infrastructure, as shown in
Fig. 1
, 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
M
antennas that can adopt spacetime signal processing. We consider a complicated NLOS multipath propagation scenario.
Elements of realtime locating system infrastructure. Tags are regularly spaced for illustration.
 B. Spacetime Communication
We assume that
N_{r}
tags are randomly distributed in a certain area and
K
readers are placed near the circumference of the area, for example, on the corners of the service area (
Fig. 1
). Each reader, equipped with an
M
 element antenna array, is assumed sufficiently far from most of the tags in the same plane so that farfield assumptions apply.
K
readers receive the signal from a tag to estimate its location. Each tag transmits a spread spectrum signaling waveform s(t) of duration
T
[s] and (twosided) bandwidth
W
[Hz]. Let
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 spacetime waveforms has the dimension
MN = MTW
. We make a practical assumption that the readers and tags are frequency (f
_{c}
) 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
T
. A tag transmits the spread of the spectrum signal to update its status.
III. LOCATION ESTIMATION ALGORITHM
 A. Spacetime 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 spacetime 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
K
readers and
N_{r}
reference locations.
Step 1: reference signature database generation

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 theith reference point is measured at thekth 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.
Step 2: location estimation process

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
[14

16]
. The angledelay virtual representation partitions the multipath responses into distinct angledelay 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
Fig. 2
. A more detailed description of the generation of the signature vector is given in
[3]
.
Computation of the signature vector: angledelay matched filtering.
{
Z_{m,i}
} is stacked to generate the
ML
x 1 dimensional signature vector
Ψ
_{i}^{(k)}
. The signature vector
Ψ
_{i}^{(k)}
for the
i
 th reference point at the
k
th reader is formed by placing those matchedfilter outputs as
Ψ
_{i}^{(k)}
(
Ml
+
m
) =
Z_{m,l}
. This yields a database of
N_{r}K
signatures for
N_{r}
reference locations and
K
readers.
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. Noncoherent Detection
When a tag of unknown location is placed at one of
N_{r}
reference points, the detection of its location is equivalent to an
N_{r}
ary hypothesis testing as
[17]
,
where
and
Ψ
_{i}
= [
Ψ
_{i}
^{(1)T}
, ... ,
Ψ
_{i}
^{(K)T}
]
^{T}
represent an observed signature and a reference signature at the
i
th reference point, respectively, and the noise vector
w
consists of a zeromean and σ
^{2}
variance i.i.d. complex Gaussian random variables.
The probability density function (pdf) of
given
H_{i}
is
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 phasesynchronized. 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 anglesofarrival, which appear as nonzero elements at different bins with different strengths in the signature matrices.
In the new method, which we term noncoherent 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
ML
×
ML
variance matrix
Λ
_{i}^{(k)}
in the absence of noise for the
i
th reference point and the
k
th reader as
where
t
is the measurement index and
N_{ave}
is the number of measurements used in averaging. In the presence of noise, the estimated variance
is the sum of errorfree variance
Λ
_{i}
^{(k)}
and noise variance σ
^{2}
I
. Using this, we model the distribution of a signature matrix at the
i
th reference point as,
and we assume that the variance matrix is diagonal, which follows from the path partitioning explained in Section IIIB. 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
i
is the true tag location becomes
This leads to the maximum likelihood detection of
We can obtain the upperbound of the error probability for noncoherent detection as
From (5) and (7), one can see that
is completely determined by
and
, respectively. This probability has exactly the same formulation as the error probability of a covariance matrixbased binary hypothesis test, and the closed form solution is as follows:
where
b_{n}
is the
n
th eigenvalue of
I^{+}
and
I^{}
are the index sets of positive and negative
b_{n}
'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 rectangularshaped 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 sitespecific channel simulator based on the deterministic 2D raytracing technique. A more detailed description of the multipath channel realizations is explained in
[3]
.
 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 signaltonoise 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
where (
x_{i}, y_{i}
) and
, respectively, represent the true and estimated coordinate of a tag and
d
(·,·) denotes the Euclidean distance.
Figs. 3
and
4
compare the estimation performance of coherent detection
[3]
and noncoherent detection algorithms for different tag mobility scenarios: fixed location and random movement. For the fixedlocation 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.
Fig. 3
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 noncoherent 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
_{1}
a
_{2}
] and [a
_{1}
e
^{jθ1}
a
_{2}
e
^{jθ2}
] are close, in terms of the norm, when θ
_{1}
≈ 0 and θ
_{2}
≈ 0, but far apart when θ
_{1}
≈ π or θ
_{2}
≈ π . Hence, noncoherent 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, noncoherent 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 threefold 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 noncoherent detection as a function of tag movement.
Fig. 4
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 noncoherent 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.
V. CONCLUSIONS
In this paper, we investigated location estimation algorithms for realtime location systems and proposed a novel location estimation algorithm based on the spacetime signature matching in a moving target environment. We derived the upperbound of the average error probability for noncoherent 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 noncoherent detection. However, when they are placed even a fraction of 0.1 m from the reference points, one should use the noncoherent 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
2003
“ Attaching contextaware services to moving locations”
IEEE Internet Computing
7
(2)
43 
51
Schiller J. H
,
Voisard A
2004
LocationBased Services
Morgan Kaufmann Publishers
SanFrancisco, CA
Oh C. H
2011
“ Location estimation using spacetime signal processing in RFID wireless sensor networks”
Proceedings of the 2011 FTRA World Convergence Conference
Jeju, Korea
57 
Campos L. M
,
Harris J. L
,
Rissetto C. L
2004
FCC provides access to better RFID technology to port security: federal funding for this new tool may be available [Internet]
ReedSmith
London
Available:http://m.reedsmith.com/files/Publication/fb0465f7d04746958165d8bad31667a3/Presentation/PublicationAttachment/4d2c47b48dfd4b3889c35fd45b9b666b/bull0420.pdf
2006
Information Technology ? Real Time Locating Systems (RTLS) ? Part 2: 2.4GHz air interface protocol
Available:http://www.iso.org/iso/catalogue_detail.htm?csnumber=40508
ISO/IEC 247302:2006
Krizman K. J
,
Biedka T. E
,
Rappaport T. S
1997
“ Wireless position location: fundamentals, implementation strategies, and sources of error”
Proceedings of IEEE 47th Vehicular Technology Conference
Phoenix, AZ
919 
923
Chen P. C
1999
“ A nonlineofsight error mitigation algorithm in location estimation”
Proceedings of IEEE Wireless Communications and Networking Conference
New Orleans, LA
316 
320
Cong L
,
Zhuang W
2001
“ Nonlineofsight error mitigation in TDOA mobile location”
Proceedings of IEEE Global Telecommunications Conference
San Antonio, TX
680 
684
Lin T. N
,
Lin P. C
2005
“ Performance comparison of indoor positioning techniques based on location fingerprinting in wireless networks”
Proceedings of International Conference on Wireless Networks, Communications and Mobile Computing
Maui, HI
1569 
1574
Kaemarungsi K
,
Krishnamurthy P
2004
“ Modeling of indoor positioning systems based on location fingerprinting”
Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies
Hong Kong
1012 
1022
Taheri A
,
Singh A
,
Agu E
2004
“ 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
Tampa, FL
676 
683
Kaemarungsi K
2006
“ Distribution of WLAN received signal strength indication for indoor location determination”
Proceedings of the 1st International Symposium on Wireless Pervasive Computing
Phuket, Thailand
Technology: realtime locating systems [Internet]
Association for Automatic Identification and Mobility
Available:http://www.aimglobal.org/technologies/rtls/
Sayeed A. M
2002
“ Deconstructing multiantenna fading channels”
IEEE Transactions on Signal Processing
50
(10)
2563 
2579
Sayeed A. M
2003
“ A virtual representation for time and frequencyselective correlated MIMO channels”
Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing
Hong Kong
648 
651
Sivanadyan T
,
Sayeed A. M
2006
“ Active wireless sensing: spacetime information retrieval from sensor ensembles”
Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing
Toulouse, France
Kay S. M
1998
Detection Theory
Upper Saddle River
NJ: Prentice Hall