Location Estimation Enhancement Using Space-time Signal Processing in Wireless Sensor Networks: Non-coherent Detection

  • cc icon

    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.


    Location estimation , Space-time signature matching , NLOS , RTLS , Target mobility


    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.


      >  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.

      >  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 (fc) 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.


      >  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 the i -th reference point is measured at the k-th reader.

    These signatures Ψi(k), k = 1,2, … . , K along 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, … . , Nr are visited.

    Thus, for Nr reference points, the database consists of NrK signature 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, … . , K based 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].

    {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


    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],





    Ψ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


    given Hi 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 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 ML × ML variance matrix Λi(k) in the absence of noise for the ith reference point and the kth reader as


    where t is the measurement index and Nave is the number of measurements used in averaging. In the presence of noise, the estimated variance


    is the sum of error-free variance Λi(k) and noise variance σ2I. Using this, we model the distribution of a signature matrix at the ith 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 i 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:


    where bn is the nth eigenvalue of


    I+ and I- are the index sets of positive and negative bn's, respectively, and



      >  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


    where (xi, yi) 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 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 [a1 a2] and [a1ejθ1 a2ejθ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.

    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.


    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.

  • 1. Kanter T. G 2003 “ Attaching context-aware services to moving locations” [IEEE Internet Computing] Vol.7 P.43-51 google
  • 2. Schiller J. H, Voisard A 2004 Location-Based Services google
  • 3. Oh C. H 2011 “ Location estimation using space-time signal processing in RFID wireless sensor networks” [Proceedings of the 2011 FTRA World Convergence Conference] P.57 google
  • 4. 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] google
  • 5. 2006 Information Technology ? Real Time Locating Systems (RTLS) ? Part 2: 2.4GHz air interface protocol google
  • 6. 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] P.919-923 google
  • 7. Chen P. C 1999 “ A non-line-of-sight error mitigation algorithm in location estimation” [Proceedings of IEEE Wireless Communications and Networking Conference] P.316-320 google
  • 8. Cong L, Zhuang W 2001 “ Non-line-of-sight error mitigation in TDOA mobile location” [Proceedings of IEEE Global Telecommunications Conference] P.680-684 google
  • 9. 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] P.1569-1574 google
  • 10. 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] P.1012-1022 google
  • 11. 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] P.676-683 google
  • 12. Kaemarungsi K 2006 “ Distribution of WLAN received signal strength indication for indoor location determination” [Proceedings of the 1st International Symposium on Wireless Pervasive Computing] google
  • 13. Technology: real-time locating systems [Internet] google
  • 14. Sayeed A. M 2002 “ Deconstructing multiantenna fading channels” [IEEE Transactions on Signal Processing] Vol.50 P.2563-2579 google
  • 15. 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] P.648-651 google
  • 16. 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] google
  • 17. Kay S. M 1998 Detection Theory google
  • [Fig. 1.] Elements of real-time locating system infrastructure. Tags are regularly spaced for illustration.
    Elements of real-time locating system infrastructure. Tags are regularly spaced for illustration.
  • [Fig. 2.] Computation of the signature vector: angle-delay matched filtering.
    Computation of the signature vector: angle-delay matched filtering.
  • [Fig. 3.] Average error probability of location estimation; comparison between coherent detection and non-coherent detection as a function of tag movement.
    Average error probability of location estimation; comparison between coherent detection and non-coherent detection as a function of tag movement.
  • [Fig. 4.] Average error distance of location estimation; comparison between coherent detection and noncoherent detection as a function of tag movement.
    Average error distance of location estimation; comparison between coherent detection and noncoherent detection as a function of tag movement.