Location Estimation Using Space-Time Signal Processing in RFID Wireless Sensor Networks

Abstract

We consider real-time locating systems (RTLS) consisting of radio frequency identification (RFID) tags and multiantenna readers to propose a novel location estimation algorithm based on the concept of space-time signature matching for multipath environments. 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 evaluate the performance of the proposed algorithm in terms of the average error probability. Simulations and analytic results confirm the effectiveness of the proposed algorithm for location estimation even in non-line-of-sight (NLOS) environments.

1. Introduction

RFID technology has greatly extended our ability to monitor and control the physical world and has been proposed for various applications including search, rescue, disaster relief, and target tracking. The inherent characteristics of these applications make an object's location an important element [1, 2].

Wireless localization, the location estimation of an object in wireless networks, has been extensively investigated. The Federal Communications Commission (FCC) has recently amended its rules to permit the use of improved RFID systems to facilitate seaport security efforts [3]. The rules will permit the use of more powerful RFID devices with commercial shipping containers, which, in turn, will offer improved security at the nation's ports, rail yards, and warehouses. One of the representative standards of these applications is the RTLS. It is a real-time location estimation system based on RFID technology at a 2.45 GHz band that is intended to provide an approximate location (within 3 m in line-of-sight (LOS) environment) with frequent updates. It operates in conformance with the International Committee for Information Technology Standards (INCITS) 371 RTLS standard [4].

Many wireless location techniques have been investigated and can be divided into two approaches: geometric-based techniques, such as angle of arrival (AOA) [5], time of arrival (TOA) [6], time difference of arrival (TDOA) [7], and location fingerprinting approaches [8, 9]. 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 time and angle of arrival signal is affected by multipaths, and the estimation accuracy is generally considerably reduced in 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 RSS for a target environment. Although frequent and extensive site measurements are often required, location fingerprinting performs well in NLOS conditions [8]. Thus, In this paper, we focus on location fingerprinting approaches since they are more suitable for NLOS applications. Many fingerprinting-based techniques have been proposed for location estimation in wireless networks, with a special emphasis on wireless local area network (WLAN) applications [8, 10, 11]. Unfortunately, most existing research related to location fingerprinting only uses the RSS information. The location is estimated by comparing the current measured data with the “radio map” of the premeasured database. This approach is simple to implement and gives reasonable accuracy in small area applications. However, it 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 case, unfortunately, the RSS information is not enough for accurate location estimation. To estimate a location more precisely, we need more information to characterize the received signal's features.

In this paper, we investigate a location estimation algorithm for RTLS consisting of RFID tags and multiantenna readers to propose novel location estimation algorithms 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 fingerprint-based approaches [8–10], which rely on RSS information only to form a signature that is in turn utilized for location estimation. We evaluate the performance of the proposed algorithm in terms of the average error probability. The organization of this paper is as follows. Section 2 provides a description of the system model, an overview of RTLS and the basic space-time communication model in the proposed approach. Section 3 describes the proposed location estimation algorithm based on the space-time signature matching technique and presents the detection method. Section 4 describes multipath channel generation based on the ray-tracing technique, and simulation results are presented to verify the effectiveness of the proposed algorithm. Conclusions are given in Section 5.

2. System Model

2.1. Overview of RTLS

A real-time locating system 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. In typical applications, systems are required to track thousands of tags simultaneously, and the average tag battery must last for five or more years [12]. The RTLS infrastructure, as shown in Figure 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. Each DSSS transmission from a transmitter contains a “blink” packet containing subblinks. All subblinks within a blink are identical to provide time diversity.

Figure 1

Elements of RTLS infrastructure: tags are regularly spaced for illustration.

Each subblink includes the RTLS transmitter's 32-bit identification (ID), 4 bits of status data, cyclical redundancy check (CRC) data, and optional telemetry data. The number of subblinks per blink, $N_s$ , and the blink interval are configurable. The RTLS transmitters transmit at a power level that can ensure successful reception at readers located at least 300 meters away [4]. In this paper, we assume that each reader is equipped with an array of M antennas that can adapt space-time signal processing. We consider not only LOS propagation but also the more complicated NLOS multipath propagation scenario.

2.2. Space-Time 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 (see Figure 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\gg \mathrm{1}$ denote the time-bandwidth 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 the practical assumption that the readers and tags are frequency $(f_c)$ but not phase synchronized. Furthermore, we assume that the phase offset between each tag and the reader stays constant for at least the packet duration T. A tag transmits the spread spectrum signal to update its status. Denoting the ith tag's data by $c_i$ , the transmitted signal $s_i(t)$ , $i=\mathrm{1,2},\dots ,N_r$ is expressed as

$$\begin{array}{cc}& s_i\left(t\right)=c_{i}q\left(t\right),\end{array}$$

(1)

where $q(t)$ is the spreading signal, that is, a pseudorandom noise (PN) sequence of N rectangular pulses or chips of duration $T_c$ each. In most applications, $T=N{T}_c$ for some integer N. The spreading signal can be expressed as [13]

$$\begin{array}{cc}& q\left(t\right)={{\displaystyle \sum }}_{j=\mathrm{0}}^{N-\mathrm{1}}{x}_j{p}_{T_c}(t-j{T}_c),\hspace{1em}\mathrm{0}<t\le T,\end{array}$$

(2)

where $\{x_j\}$ is a binary $(\pm \mathrm{1})$ spreading sequence and $p_{T_c}(t)$ is a rectangular pulse of duration $T_c$ ; that is, $p_{T_c}(t)=\mathrm{1}/\sqrt{T_c}$ when $\mathrm{0}\le t\le T_c$ and $p_{T_c}(t)=\mathrm{0}$ otherwise.

The transmitted signal $s_i(t)$ undergoes multipath propagation due to scattering off of objects, for example, densely stacked containers that are randomly distributed. Thus, each reader receives a superposition of multiple waveforms from the tag. In this paper, we assume for the sake of simplicity that only one tag transmits a signal at a certain instance; this is reasonable because each tag is active for only short periods of time, and in many applications they do not have to update the central server very often. Thus, the received signal at each reader can be expressed as

$$\begin{array}{cc}& \mathbf{r}\left(t\right)={{\displaystyle \sum }}_{n=\mathrm{1}}^{N_p}{\beta }_n{e}^{-j{\varphi }_n}a\left({\theta }_n\right)c_{n}q(t-{\tau }_n)+w\left(t\right),\end{array}$$

(3)

where ${\beta }_n$ and ${\varphi }_n$ denote the magnitude and phase, respectively, of the complex path gain corresponding to nth path with a normalized AOA ${\theta }_n$ and delay ${\tau }_n$ . $N_p$ denotes the number of paths, and $w(t)$ denotes an additive white Gaussian noise (AWGN) vector process representing the noise at different antenna elements of variance ${\sigma }^{\mathrm{2}}$ . In (3), $a({\theta }_n)$ is the steering/response vector of the antenna array toward angle ${\theta }_n$ ; this is explained in further detail later. For simplicity, we consider a one-dimensional uniform linear array (ULA) with spacing d and assumed M to be odd without loss of generality; we then define $\tilde{M}=(M-\mathrm{1})/\mathrm{2}$ . The array steering/response vector for a ULA is given by

$$\begin{array}{cc}& a\left(\theta \right)={\left[e^{j\mathrm{2}\pi \tilde{M}\theta },\dots ,\mathrm{1},\dots ,e^{-j\mathrm{2}\pi \tilde{M}\theta }\right]}^T,\end{array}$$

(4)

where the normalized angle θ is related to the physical angle of arrival φ measured w.r.t. broadside as $\theta =d\sin (\phi )/\lambda$ with $\lambda =\mathrm{1}/f_c$ . The steering/response vector represents the relative phases across antenna for the receiver from angle θ. We assume that a $d=\lambda /\sqrt{\mathrm{2}}$ spacing, which corresponds to the maximum angular spread (90°) at the antenna array; larger spacing can be used for smaller angular spreads ( $d=\lambda /(\mathrm{2}\sin ({\phi }_{\max }))$ spacing results is a one-to-one mapping between $\theta \in [-\mathrm{0.5},\mathrm{0.5}]$ and $\phi \in [-{\phi }_{\max },{\phi }_{\max }]\subset [-\pi /\mathrm{4},\pi /\mathrm{4}]$ ).

From (3), the physical channel can be expressed as

$$\begin{array}{cc}& h\left(t\right)={{\displaystyle \sum }}_{n=\mathrm{1}}^{N_p}{\alpha }_n\delta (t-{\tau }_n)a\left({\theta }_n\right),\end{array}$$

(5)

where ${\alpha }_n={\beta }_n{e}^{-j{\varphi }_n}$ and the $M\times \mathrm{1}$ vector $\mathbf{h}(t)$ represent the impulse response for the space-time multipath channel. Let ${\min }_n{\tau }_n=\mathrm{0}$ and ${\max }_n{\tau }_n\mathrm{\hspace{0.17em}\hspace{0.17em}}={\tau }_{\max }$ ; the delay spread of the channel is then ${\tau }_{\max }$ , and we assume that the packet signaling duration $T\gg {\tau }_{\max }$ .

3. Proposed Location Estimation Algorithm

This section begins with an overview of conventional fingerprint-based algorithms and our algorithm, followed by the spatiotemporal partitioning technique. This technique serves as a key role in our algorithm because the angle and delay associated with each scatterer can be obtained through this. The details of our algorithm are then presented.

3.1. Fingerprint-Based Location Estimation

Conventional fingerprint-based location estimation algorithms rely solely on the received RSS measured at multiple single-antenna receivers. First, an RSS database is formed by transmitting signals from a large number of locations called reference points and storing the RSS measured at all receivers. Once the database is ready, the system is able to estimate the location of an object at an unknown location by finding the location in the database whose RSS values most closely match the current RSS values.

However, the estimation accuracy of the fingerprint technique is limited by the fact that it relies only on RSS. Although RSS is an important characteristic for a location, RSS-based algorithms cannot distinguish two locations if their RSSs' are similar, even if they induce different angles of arrivals and delays. This is especially true in the presence of multipaths. Thus, in this paper, we propose a novel method based on space-time signature matching to accurately estimate the location by utilizing not only the RSS but also the angle and delay information of the received signal. Two key differences are that our algorithm can (1) utilize angular information captured through multiple antennas at readers and (2) resolve powers contributed by each ray or path in contrast to RSS, which is the aggregate of the path contributions.

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 reference signatures. This is explained in more details later. We assume that there are K readers and $N_r$ reference locations.

Step 1.

Reference signature database generation

• (i)

Place a transmitter at one of the reference positions and let it transmit a known spread spectrum waveform.

(ii)

Readers receive the waveform and generate a signature vector of this location. Denoted by ${\psi }_i^{(k)}$ , the signature vector of the ith reference point is measured at the kth reader. Details on generating it are explained in Section 3.3.

(iii)

These signatures ${\psi }_i^{(k)}$ , $k=\mathrm{1},\mathrm{2},\dots ,K$ along with the corresponding reference coordinates $(x_i,y_i)$ are saved in the database located in the server.

(iv)

Move to the next reference point until all reference points, $i=\mathrm{1},\mathrm{2},\dots ,N_r$ , are visited.

(v)

Thus, for $N_r$ reference points, the database consists of $N_{r}K$ signature vectors, ${\psi }_i^{(k)}$ , $i=\mathrm{1},\mathrm{2},\dots ,N_r$ , $k=\mathrm{1},\mathrm{2},\dots ,K$ .

(vi)

Once the reference signatures are obtained, we can locate a tag at unknown position as follows.

Step 2.

Location estimation process.

• (i)

A tag at unknown location transmits a known waveform, and readers compute a signature ${\tilde{\psi }}^{(k)}$ , $k=\mathrm{1},\mathrm{2},\dots ,K$ based on the received signal.

(ii)

Compare the currently computed signature with the reference signatures in the database.

(iii)

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.

3.2. Path Partitioning in Angle and Delay

The main concept behind our algorithm is that the estimation accuracy can be greatly improved by working with a detailed map or signature of a 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 RSS-based methods. Such information buried in the regular channel vector or matrix clearly shows up in the virtual channel vector, which is explained next.

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, 15]. The virtual representation in the angle corresponds to beam forming in M fixed virtual directions: ${\tilde{\theta }}_m=m/M$ , $m=-\tilde{M},\dots ,\tilde{M}$ . The $M\times M$ unitary (DFT) matrix is defined as

$$\begin{array}{cc}& A=\frac{\mathrm{1}}{\sqrt{M}}\left[a\left(-\frac{\tilde{M}}{M}\right),\dots ,\mathrm{1},\dots ,a\left(\frac{\tilde{M}}{M}\right)\right].\end{array}$$

(6)

Its columns are the normalized steering vectors for the virtual angles, and they form an orthonormal basis for the spatial signal space. Using this, a virtual spatial vector $h_V(t)$ can be defined as

$$\begin{array}{cc}& h_V\left(t\right)=A^{H}h\left(t\right)⟷h\left(t\right)=A{h}_V\left(t\right),\end{array}$$

(7)

and its coefficients are related to the physical paths in

$$\begin{array}{cc}& h_V(m;t)\approx M{{\displaystyle \sum }}_{n\in S_{\theta ,m}}{\alpha }_{n}g\left({\theta }_n-\frac{m}{M}\right)\delta (t-{\tau }_n),\end{array}$$

(8)

where $g(\theta )=(\mathrm{1}/M)(\sin (\pi M\theta )/\sin (\pi \theta ))$ is the Dirichlet sinc function that captures the interaction between the fixed virtual beams and true signal directions, $\delta (·)$ denotes the Dirac delta function, and $S_{\theta ,m}=\{n\in \{\mathrm{1},\dots ,N_p\}:-\mathrm{1}/\mathrm{2}M<{\theta }_n-m/M\le \mathrm{1}/\mathrm{2}M\}$ represents the set of all paths whose angles lie in the mth spatial resolution bin of width $\mathrm{\Delta }\theta =1/M$ , centered around the mth beam. Thus, the virtual spatial representation partitions the multipath signals in the angle.

The multipath responses within each spatial beam can be further partitioned by resolving their delays with resolution $\mathrm{\Delta }\tau =\mathrm{1}/W$ . Let $L=\lceil {\tau }_{\max }W\rceil$ be the normalized delay spread of the channel. The impulse response $h_V(m;t)$ of the channel corresponding to the mth direction can be further processed to yield entries $h_V(m,l)$ corresponding to the mth direction and lth uniformly spaced delays as [16]

$$\begin{array}{cc}& h_V(m;t)\approx {{\displaystyle \sum }}_{l=\mathrm{0}}^{L-\mathrm{1}}{h}_V\left(m,l\right)\delta \left(t-\frac{l}{W}\right),\\ h_V\left(m,l\right)=M{{\displaystyle \sum }}_{n=\mathrm{1}}^{N_p}{\alpha }_{n}g({\theta }_n-\frac{m}{M})\text{sinc}(W{\tau }_n-l)\\ \approx M{{\displaystyle \sum }}_{n\in S_{\theta ,m}\cap S_{\tau ,l}}{\alpha }_{n}g({\theta }_n-\frac{m}{M})\text{sinc}(W{\tau }_n-l),\end{array}$$

(9)

where $\text{sinc}(x)=\sin (\pi x)/\pi x$ captures the interaction between the fixed virtual and true signal delays and $S_{\tau ,l}=\{n:-\mathrm{1}/\mathrm{2}W<{\tau }_n-l/W\le \mathrm{1}/\mathrm{2}W\}$ is the set of paths whose relative delays lie within the lth delay resolution bin of width $\mathrm{\Delta }\tau =\mathrm{1}/W$ centered around the lth fixed virtual delay ${\tilde{\tau }}_l=l/W$ .

Thus, the angle-delay virtual representation partitions the multipath responses into distinct angle-delay resolution bins: the virtual coefficient $h_V(m,l)$ is a superposition of all multipath responses whose angles and delays lie in the intersection of the mth angle and lth delay bin (see Figure 2). The generation of a signature vector based on virtual representation and the location estimation algorithm using signature matrices are presented next.

Figure 2

Angle-delay resolution bins.

3.3. 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 Figure 3.

Figure 3

Computation of the signature vector: angle-delay matched filtering.

Let $r(t)$ be the $M\times \mathrm{1}$ vector of the received signal from the antenna array of reader as in (3). For a given reference tag location, we ignore the dependency on reader $(k)$ and reference location (i). After a unitary spatial transform, we obtain $r_V(t)=A^{H}r(t)$ , which represents the signal in the virtual angle domain, that is, each row corresponds to a virtual angle. Using (5) and (7), $r_V(t)$ can be expressed as

$$\begin{array}{cc}& r_V\left(t\right)={{\displaystyle \sum }}_{l=\mathrm{0}}^{L-\mathrm{1}}{h}_V\left(l\right)s\left(t-\frac{l}{W}\right)+w_V\left(t\right),\end{array}$$

(10)

where $w_V(t)=A^{H}w(t)$ is the noise in the virtual angle domain.

Note that $s(t-l/W)=c_{i}q(t-l/W)$ is nothing but a delayed and BPSK-modulated version of a pseudorandom waveform $q(t)$ . Hence, we have the following property

$$\begin{array}{cc}& 〈s\left(t-\frac{l}{W}\right),s\left(t-\frac{l^{\prime }}{W}\right)〉\approx {\delta }_{l-l^{\prime }}.\end{array}$$

(11)

Thus, correlating each $r_V(m;t)$ with delayed versions of $s(t)$ yields a signature $\{z_{m,l}:m=\mathrm{1},\dots ,M;l=\mathrm{0},\dots ,L-\mathrm{1}\}$ . Consider

$$\begin{array}{cc}& z_{m,l}=〈{\mathbf{r}}_V(m;t),s\left(t-\frac{l}{W}\right)〉\\ ={{\displaystyle \int }}_{\mathrm{0}}^{T+{\tau }_{\max }}{\mathbf{r}}_V\left(m,t\right)s^{*}(t-\frac{l}{W})dt.\end{array}$$

(12)

$\{z_{m,l}\}$ are stacked to generate the $ML\times \mathrm{1}$ dimensional signature vector ${\psi }_i^{(k)}$ . The signature vector ${\psi }_i^{(k)}$ for the ith reference point at the kth reader is formed by placing those matched-filter outputs as ${\psi }_i^{(k)}(Ml+m)=z_{m,l}$ . This yields a database of $N_{r}K$ signatures for $N_r$ reference locations and K readers. Figure 4 shows an example of the tag signature at four readers.

Figure 4

Example of the signature at each reader for a tag position.

After obtaining signature vectors from all reference points, readers constantly monitor the field. When a strong signal is detected, each reader forms a signature vector ${\tilde{\psi }}^{(k)}$ from the received signal. The maximum likelihood decision for the location is then made. We consider coherent detection as the detection method.

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

$$\begin{array}{cc}& H_i:\tilde{\psi }={\psi }_i+w,\hspace{1em}i=\mathrm{1,2},\dots ,N_r,\end{array}$$

(13)

where $\tilde{\psi }={[{\tilde{\psi }}^{(\mathrm{1}{)}^T},\dots ,{\tilde{\psi }}^{(K{)}^T}]}^T$ and ${\psi }_i={[{\psi }_i^{(\mathrm{1}{)}^T},\dots ,{\psi }_i^{(K{)}^T}]}^T$ represent an observed signature and reference signature at the ith reference point, respectively, and noise vector w consists of zero mean and ${\sigma }^{\mathrm{2}}$ variance i.i.d. complex Gaussian random variables.

The probability density function (pdf) of ${\tilde{\psi }}^{(k)}$ given $H_i$ is

$$\begin{array}{cc}& f_i\left(\tilde{\psi }\right)=\frac{\mathrm{1}}{{\left(\pi {\sigma }^{\mathrm{2}}\right)}^{MLK}}\exp \left(-\frac{{\parallel \tilde{\psi }-{\psi }_i\parallel }^{\mathrm{2}}}{{\sigma }^{\mathrm{2}}}\right),\end{array}$$

(14)

where $\parallel ·\parallel$ represents the Euclidean norm of a vector. Hence, the maximum likelihood estimation of the tag location is made as follows:

$$\begin{array}{cc}& {\widehat{i}}_{ML}\left(\tilde{\psi }\right)=\underset{i\in \left\{\mathrm{1},\dots ,N_r\right\}}{\arg \max }{f}_i\left(\tilde{\psi }\right)=\underset{i}{\arg \min }{\parallel \tilde{\psi }-{\psi }_i\parallel }^{\mathrm{2}},\end{array}$$

(15)

which implies that the maximum likelihood decision is equivalent to simply finding a reference signature that is closest to the observed signature.

We now analyze the error probabilities of this algorithm. When the true tag location is i, the error probability can be upper bounded using the union bound technique as

$$\begin{array}{cc}& P\left(e\mid i\right)\le {{\displaystyle \sum }}_{j=\mathrm{1},j\ne i}^{N_r}P(\widehat{i}=j\mid i),\end{array}$$

(16)

where i and $\widehat{i}$ denote the true and estimated tag positions, respectively. The pairwise error probability can be easily derived to be

$$\begin{array}{cc}& P(\widehat{i}=j\mid i)=Q\left(\frac{\sqrt{{{\displaystyle \sum }}_{k=\mathrm{1}}^K{\parallel {\psi }_i^{\left(k\right)}-{\psi }_j^{\left(k\right)}\parallel }^{\mathrm{2}}}}{\sqrt{\mathrm{2}}\sigma }\right),\end{array}$$

(17)

where $Q(x)=(\mathrm{1}/\sqrt{\mathrm{2}\pi }){\int }_x^{\infty }{e}^{-t^{\mathrm{2}}/\mathrm{2}}dt$ is the Gaussian tail function. Since $Q(x)$ is monotonically decreasing, the error probability improves with increasing k, decreasing σ, and the norm of the difference vector. Assuming each location has an equal chance of being chosen, the average error probability can be upper bounded as

$$\begin{array}{cc}& P_e=\frac{\mathrm{1}}{N_r}{{\displaystyle \sum }}_{i=\mathrm{1}}^{N_r}P\left(e\mid i\right)\\ \le \frac{\mathrm{1}}{N_r}{{\displaystyle \sum }}_{i=\mathrm{1}}^{N_r}{{\displaystyle \sum }}_{j=\mathrm{1},j\ne i}^{N_r}Q(\frac{\sqrt{{{\displaystyle \sum }}_{k=\mathrm{1}}^K{\parallel {\psi }_i^{\left(k\right)}-{\psi }_j^{\left(k\right)}\parallel }^{\mathrm{2}}}}{\sqrt{\mathrm{2}}\sigma }).\end{array}$$

(18)

We show the above upper bound with the Monte-Carlo simulation in Section 4 to confirm the validity of the simulation.

4. Simulation and Discussions

The performance of the proposed algorithm is evaluated through simulations and theoretical analysis. This section first describes how we generate multipath channel realizations and then presents the simulation and analytic results with discussions.

4.1. Generation of Multipath Channel Realizations

We consider a field of a 300 m × 300 m square region. We assume that reference tags are randomly distributed over the region, and four readers equipped with five antennas each are placed in the corners of the region. Twenty rectangular-shaped scatterers are placed inside the region in a random manner. We measure signature vectors at reference tag positions separated by 3 m (see Figure 5).

Figure 5

Sample snapshot of ray tracing at each reader.

In order to generate realistic multipath channel realizations that are suitable for seaport wireless environments, we develop a site-specific channel simulator based on the deterministic two-dimensional ray tracing technique. The ray-tracing technique has been used for accurately predicting site-specific radio propagation characteristics [17]. For each transmitter and receiver pair, ray-tracing simulates all paths arriving at the receiver to produce necessary information such as the RSS, multipath delay, AOA, and number of paths. In the ray-tracing algorithm, most rays arrive at the reader via multiple reflections due to the objects in the environment. We only consider reflections of the surface of scatterers, not diffraction. The angle of arrival, distance of travel (or delay), and number of reflections are recorded for every path and for every pair of a reference position and reader. To find a path, a reference point draws a line from itself along a certain angle. There can be three cases. (1) If the line does not intersect a reader or scatterer, we examine the next angle, which is the previous angle incremented by a small amount (e.g., 1°) until all 360° have been examined. (2) If it intersects a reader, we are done with this angle, so we store all the information and examine the next angle. (3) If it intersects a scatterer, a new line is drawn according to the law of reflection, and the search continues until (1) or (2) is encountered. Figure 5 shows a sample snapshot of the ray-tracing results. In Figure 5, dark lines represent paths that eventually arrive at a reader, and light lines are those that initially intersect a scatterer but do not finally arrive at a reader. In this paper, we assume there is no signal fluctuation for at least the packet duration T because there is seldom movement of a tag in an RTLS environment.

4.2. Performance Evaluation

The effectiveness of the proposed algorithm for enhancing the accuracy of location estimation in NLOS environments is validated through computer simulation and theoretical analysis. In the simulation, 1,135 tags are considered as reference positions, and the transmit signal-to-noise ratio (TXSNR) was used as an SNR criterion. The estimation performance of the proposed algorithm is evaluated in terms of the average error probability. Figures 6 and 7 show the results of the proposed algorithm when there is no movement, that is, tag locations are fixed. In this case, we consider coherent detection as a detection method.

Figure 6

Average error probability of location estimation; comparison between simulation results and analytical results.

Figure 7

Average error probability of location estimation for different number of collaborating reader.

Figure 6 illustrates the estimation performance of the proposed algorithm in terms of average error probability for $M=\mathrm{5}$ and $K=\mathrm{4}$ . For verification purposes, the analytical results obtained in Section 3 are also compared with the simulation results in Figure 6. As shown in Figure 6, the simulation results closely match the analytic upper bound, especially at high TXSNR. As expected, the estimation performance improves as the TXSNR increases. The estimation error probability is about $\mathrm{1}{\mathrm{0}}^{-\mathrm{3}}$ at TXSNR = 8 dB. This indicates that the proposed algorithm can reliably estimate the tag location even in NLOS environments.

Figure 7 shows the effect of collaborative processing (combing) of the multiple readers on the average error probability for $M=\mathrm{5}$ . As predicted, the estimation performance improves as the number of collaborating readers increases for a given TXSNR. This indicates that the more readers that collaborate, the more accurate estimation of the location that can be obtained; furthermore, the improvement is huge, on the order of a magnitude. These improvements are as expected from (17) since increasing k also increases the argument of the Q function.

5. Conclusions

In this paper, we investigated location estimation algorithms for real-time location systems and proposed novel location estimation algorithms based on the space-time signature matching in NLOS environments. Unlike existing works, we incorporated all available information (angle, delay and RSS) into a signature vector via spatiotemporal processing, and we did not require line-of-sight environment for successful operation. We derived the upper bound of the average error probability for coherent detection and carried out simulations. The two-dimensional ray-tracing technique was used to generate multipath channel realizations. From the results, we confirmed that in a fixed tag location the proposed algorithm could reliably estimate the target tag location even in the NLOS environments and the estimation accuracy greatly improved as the number of collaborating readers increased.