Advanced
Location Estimation Enhancement Using Space-time Signal Processing in Wireless Sensor Networks: Non-coherent Detection
Location Estimation Enhancement Using Space-time Signal Processing in Wireless Sensor Networks: Non-coherent Detection
Journal of Information and Communication Convergence Engineering. 2012. Sep, 10(3): 269-275
Copyright ©2012, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/li-censes/bync/ 3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : July 13, 2012
  • Accepted : July 30, 2012
  • Published : September 30, 2012
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Chang-Heon Oh
choh@koreatech.ac.kr

Abstract
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.
Keywords
I. INTRODUCTION
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 [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 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 [5] .
Many wireless location techniques have been investigated and can be divided into two approaches: geometric-based 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 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 [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 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 [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 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 [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 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 [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 space-time signal processing. We consider a complicated NLOS multipath propagation scenario.
PPT Slide
Lager Image
Elements of real-time locating system infrastructure. Tags are regularly spaced for illustration.
- B. Space-time Communication
We assume that Nr 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 far-field 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 (two-sided) 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 space-time 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. 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 K readers and Nr 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 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.
Step 2: location estimation process
  • A tag at an unknown location transmits a known waveform and the readers compute a signature
PPT Slide
Lager Image
  • ,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 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 Fig. 2 . A more detailed description of the generation of the signature vector is given in [3] .
PPT Slide
Lager Image
Computation of the signature vector: angle-delay matched filtering.
{ Zm,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 matched-filter outputs as Ψ i(k) ( Ml + m ) = Zm,l . This yields a database of NrK signatures for Nr 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
PPT Slide
Lager Image
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 Nr reference points, the detection of its location is equivalent to an Nr -ary hypothesis testing as [17] ,
PPT Slide
Lager Image
where
PPT Slide
Lager Image
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 zero-mean and σ 2 variance i.i.d. complex Gaussian random variables.
The probability density function (pdf) of
PPT Slide
Lager Image
given Hi is
PPT Slide
Lager Image
where ll·ll represents the Euclidean norm of a vector. Hence the maximum likelihood estimation of the tag location is made as follows:
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 ML × ML variance matrix Λ i(k) in the absence of noise for the i th reference point and the k th reader as
PPT Slide
Lager Image
where t is the measurement index and Nave is the number of measurements used in averaging. In the presence of noise, the estimated variance
PPT Slide
Lager Image
is the sum of error-free 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,
PPT Slide
Lager Image
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
PPT Slide
Lager Image
the pdf of a signature matrix when i is the true tag location becomes
PPT Slide
Lager Image
This leads to the maximum likelihood detection of
PPT Slide
Lager Image
We can obtain the upper-bound of the error probability for non-coherent detection as
PPT Slide
Lager Image
From (5) and (7), one can see that
PPT Slide
Lager Image
is completely determined by
PPT Slide
Lager Image
and
PPT Slide
Lager Image
, 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:
PPT Slide
Lager Image
where bn is the n th eigenvalue of
PPT Slide
Lager Image
I+ and I- are the index sets of positive and negative bn 's, respectively, and
PPT Slide
Lager Image
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 [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 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
PPT Slide
Lager Image
where ( xi, yi ) and
PPT Slide
Lager Image
, 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 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.
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 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 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, 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.
PPT Slide
Lager Image
Average error probability of location estimation; comparison between coherent detection and non-coherent 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 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.
PPT Slide
Lager Image
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 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.
References
Kanter T. G 2003 “ Attaching context-aware services to moving locations” IEEE Internet Computing 7 (2) 43 - 51
Schiller J. H , Voisard A 2004 Location-Based Services Morgan Kaufmann Publishers SanFrancisco, CA
Oh C. H 2011 “ Location estimation using space-time 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/fb0465f7-d047-4695-8165-d8bad31667a3/Presentation/PublicationAttachment/4d2c47b4-8dfd-4b38-89c3-5fd45b9b666b/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 24730-2: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 non-line-of-sight error mitigation algorithm in location estimation” Proceedings of IEEE Wireless Communications and Networking Conference New Orleans, LA 316 - 320
Cong L , Zhuang W 2001 “ Non-line-of-sight 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: real-time 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