Method for simultaneous detection of a plurality of RFID tags using multiuser detection

Abstract

A method and apparatus are disclosed that apply multiuser detection (MUD) analysis to an aggregated RF response from a plurality of simultaneously queried RFID tags, so as to distinguish the individual tag responses. The claimed method thereby significantly reduces RFID detection latency when multiple tags are simultaneously queried. Some embodiments transmit carrier waves at more than one frequency, such as a plurality of equally-spaced frequencies, so as to enhance the MUD analysis by incorporating a multi-frequency dimension. Other embodiments incorporate additional spatial dimensions by deploying multiple RF detection antennae at separated locations. The number of colliding tag responses must be estimated before MUD analysis can be applied. In some embodiments other signal parameters must be estimated, such as signal bias and an impulse function for each responding tag that characterizes alterations of the RF signal while in transit due to propagation distance, passage through intervening objects, and reflections.

Claims

1. A method for distinguishing responses received by an RFID detector from a plurality of simultaneously queried RFID tags, the method comprising: querying the plurality of RFID tags; receiving an aggregated RF response from the plurality of RFID tags; characterizing the aggregated RF response according to a plurality of characteristics, the plurality of characteristics including at least RF amplitude and RF phase; according to the characterization of the aggregated RF response, estimating at least one parameter, the at least one parameter including a number of RFID tag responses included in the aggregated RF response; and applying multiuser detection including jointly demodulating a plurality of colliding RFID tag responses included in the aggregated RF response according to the at least one estimated parameter so as to distinguish each of the RFID tag responses included in the aggregated RF response.

2. The method of claim 1, further comprising repeating the steps of querying, receiving, characterizing, estimating, and applying until the responses of all of the plurality of simultaneously queried RFID tags have been distinguished.

3. The method of claim 1, wherein the at least one parameter includes a signal bias.

4. The method of claim 3, wherein the signal bias is estimated by averaging a bias of the aggregated RF response over a plurality of symbol intervals.

5. The method of claim 3, wherein the estimated signal bias is subtracted from the aggregated RF response preceding further analysis of the aggregated RF response.

6. The method of claim 1, wherein estimating the number of RFID tag responses included in the aggregated RF response includes applying a statistical analysis method so as to detect clustering of the aggregated RF response, as characterized according to the plurality of characteristics.

7. The method of claim 6, wherein the statistical analysis method comprises one of: a K-Means algorithm; a Maximum likelihood solution; and a T test.

8. The method of claim 1, wherein: the aggregated RF response includes a plurality of unique identifying sequences transmitted simultaneously by each of the responding RFID tags, the identifying sequences being statically independent of each other, and estimating the number of RFID tag responses included in the aggregated RF response includes counting a number of unique eigenvalues in a covariance matrix derived from a portion of the aggregate RF signal that includes the simultaneously transmitted identifying sequences.

9. The method of claim 1, wherein for each of the RFID tags that contributed to the aggregated RF response, the at least one parameter includes a corresponding channel impulse response function that characterizes an alteration of an RF response from the corresponding RFID tag during transit of the RF response from the RFID tag to the RFID detector.

10. The method of claim 1, wherein: receiving the aggregated RF response from the plurality of RFID tags includes simultaneously transmitting to the plurality of RFID tags a plurality of RF carrier waves at a plurality of RF frequencies; and characterizing the aggregated RF response according to a plurality of characteristics includes characterizing the aggregated RF response according to frequency.

11. The method of claim 10, wherein the plurality of RF carrier waves is a plurality of equal amplitude RF carrier waves, and the plurality of RF frequencies is a plurality of equally spaced RF frequencies.

12. The method of claim 1, wherein: receiving the aggregated RF response from the plurality of RFID tags includes obtaining a plurality of spatially separated responses received using a plurality of spatially separated RF receiving antennae; and characterizing the aggregated RF response according to a plurality of characteristics includes characterizing the aggregated RF response according to the plurality of spatially separated responses.

13. An apparatus for distinguishing responses received from a plurality of simultaneously queried RFID tags, the apparatus comprising: an RF transmitter configured to transmit a querying RF signal to the plurality of RFID tags; an RF receiver configured to receive an aggregated RF response from the plurality of RFID tags; an RF characterizer configured to characterize the aggregated RF response according to a plurality of characteristics, the plurality of characteristics including at least RF amplitude and RF phase; and a computer controlled by software configured to direct the computer to estimate at least one parameter pertaining to the characterized aggregated RF response, the at least one parameter including a number of RFID tag responses included in the aggregated RF response, the software being further configured to direct the computer to apply multiuser detection including jointly demodulating a plurality of colliding RFID tag responses included in the aggregated RF response according to the at least one estimated parameter, so as to distinguish each of the RFID tag responses included in the aggregated RF response.

14. The apparatus of claim 13, wherein the at least one parameter includes a signal bias.

15. The apparatus of claim 14, wherein the signal bias is estimated by averaging a bias of the aggregated RF response over a plurality of symbol intervals.

16. The apparatus of claim 14, wherein the estimated signal bias is subtracted from the aggregated RF response preceding further analysis of the aggregated RF response.

17. The apparatus of claim 13, wherein estimating the number of RFID tag responses included in the aggregated RF response includes applying a statistical analysis method so as to detect clustering of the aggregated RF, as characterized according to the plurality of characteristics.

18. The apparatus of claim 17, wherein the statistical analysis method comprises one of: a K-Means algorithm; a Maximum likelihood solution; and a T test.

19. The apparatus of claim 13, wherein: the aggregated RF response includes a plurality of unique identifying sequences transmitted simultaneously by each of the responding RFID tags, the identifying sequences being statically independent of each other; and estimating the number of RFID tag responses included in the aggregated RF response includes counting a number of unique eigenvalues in a covariance matrix derived from a portion of the aggregate RF signal that includes the simultaneously transmitted identifying sequences.

20. The apparatus of claim 13, wherein for each of the RFID tags that contributed to the aggregated RF response, the at least one parameter includes a corresponding channel impulse response function that characterizes an alteration of an RF response from the corresponding RFID tag during transit of the RF response from the RFID tag to the RFID detector.

21. The apparatus of claim 13, wherein: the RF transmitter is able to simultaneously transmit to the plurality of RFID tags a plurality of RF carrier waves at a plurality of RF frequencies; and the software is able to direct the computer to characterize the aggregated RF response according to the plurality of RF frequencies.

22. The apparatus of claim 13, further comprising a plurality of spatially separated RF receiving antennae that are able to receive the aggregated RF response as a plurality of spatially separated responses, the software being able to direct the computer to characterize the aggregated RF response according to the plurality of spatially separated responses.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1A is a functional diagram illustrating an RFID detector transmitting a query signal to an RFID tag in a typical prior art configuration;

(2) FIG. 1B is a functional diagram illustrating an RFID detector transmitting a carrier wave to a passive RFID tag, while the RFID tag simultaneously transmits a response signal to the RFID detector in a typical prior art configuration;

(3) FIG. 1C is a functional diagram illustrating an RFID detector transmitting a carrier wave to a plurality of RFID tags while the RFID tags simultaneously transmit response signals to the RFID detector;

(4) FIG. 2 is a table illustrating a simplified ALOHA protocol of the prior art for distinguishing the responses of a plurality of simultaneously queried RFID tags;

(5) FIG. 3 is a block diagram illustrating a mathematical model describing communication between an RFID detector and a single RFID tag;

(6) FIG. 4 is a block diagram illustrating an embodiment of the present invention in which estimated parameters used for MUD detection include signal bias, number of collisions, and channel impulse response functions;

(7) FIG. 5 is a pair of graphs that illustrate estimation of the number of collisions present in an aggregated signal by applying a statistical analysis clustering technique in an embodiment of the present invention;

(8) FIG. 6 is a diagram that illustrates a maximum likelihood decision tree used in an embodiment of the present invention for MUD analysis;

(9) FIG. 7 is a graph illustrating application of a multi-frequency carrier wave to a group of RFID tags in an embodiment of the present invention so as to provide additional frequency dimensionality for enhanced discrimination of individual signal responses included in an aggregated RF signal.

(10) FIG. 8A is a graph that presents the magnitude as a function of frequency for a typical RFID tag complex channel response gain; and

(11) FIG. 8B is a graph that presents the phase as a function of frequency for a typical RFID tag complex channel response gain.

DETAILED DESCRIPTION

(12) Based on current RFID designs, a problem occurs when a plurality of RFID tags is simultaneously queried by an RFID detector, for example a plurality of RFID tags that are attached to each product carried by a shipping pallet. In such a case the detector will receive a nearly simultaneous response from every tag that is located within its detection range, resulting in collisions of the data packets transmitted by the tags. Prior art approaches have implemented protocols that cause packets to transmit their information at random times, and to re-transmit until a collision-free transmission is achieved. The present invention applies Multi-User Detection (“MUD”) to distinguish overlapping packets, thereby reducing or eliminating the need for random delays and/or re-transmissions.

(13) Signal Model

(14) So as to understand how the present invention solves this problem, it is helpful first to understand the physics and define a representative signal model that incorporates collisions from multiple tag responses. To start we define the signal model for a single tag scenario and then we extend it to the case where multiple tag responses collide. FIG. 1A and FIG. 1B illustrate the basic query and response for a single RFID tag. This interaction can be mathematically modeled as shown in FIG. 3. An RF carrier wave 300 e.sup.jωt is generated by the RFID detector 102 and is then amplified in the RF transmitter 106 by a factor β so as to be strong enough to transmit a signal to the RFID tag 100 and, in the case of a passive tag, to power the RFID tag 100.

(15) The RF signal is initially transmitted as a query signal 104 to the RFID tag 100. This “forward” signal is modified in transit according to a forward impulse response function 302 h.sub.f.sup.BP(t) due to the distance traveled by the RF query signal 104, and possibly also due to passage through and/or reflection from intervening objects, and such like. After transmission of the RF query 104, the RFID detector 102 continues to transmit an unmodulated carrier wave 112.

(16) As shown in FIG. 3, the RFID tag modulates the carrier wave 112 by passing it through a variable impedance 304. The modulated carrier wave 110 is then re-transmitted to the RFID detector 102. The retransmitted signal is modified in transit according to a response impulse function 306 h.sub.r.sup.BP (t), due to the distance traveled and also due to any passage through and/or reflections from intervening objects and such like. Along the way, noise 308 is inevitably added to the signal 110. The signal 110 is then phase detected 310, so as to extract both the phase and amplitude of the modulated RF signal 110. Note that, in general, both the RF amplitude and the RF phase can be set by the RF transmitter 106 and the RFID tag 100 to any of several possible values. This enables the RF transmitter 106 and the RFID tag 100 to encode several binary bits into each modulation. For this reason, the transmissions 104, 110 are said to consist of a series of transmitted “symbols,” wherein each symbol represents one or more bits.

(17) This process can be mathematically modeled according to the following equations. The complex baseband received signal y(t) is defined as

(18) $\begin{array}{cc}y\left(t\right)=\left[\left(\underset{m=1}{\overset{M}{.Math.}}d\left(m\right)p\left(t-\mathrm{mT}\right)\left[\beta e^{j\omega t}*h_j^{\mathrm{BP}}\left(t\right)\right]\right)*h_T^{\mathrm{BP}}\left(t\right)\right]e^{-j\omega t}+\left[\beta e^{j\omega t}+w^{\mathrm{BP}}\left(t\right)\right]e^{-j\omega t}& \left(1\right)\end{array}$
which can be reduced with no loss of generality to

(19) $\begin{array}{cc}y\left(t\right)=\underset{m=1}{\overset{M}{.Math.}}d\left(m\right)h\left(t-\mathrm{mT}\right)+\beta +w\left(t\right)& \left(2\right)\end{array}$
where m denotes the symbol index and M denotes the total number of symbols. In equations 1 and 2, ω(t) denotes the complex baseband white Gaussian noise process defined as
ω(t)=ω.sup.BP(t)e.sup.−jωt  (3)
and h(t) denotes the complex baseband composite channel impulse response defined as
h(t)=p(t)*(γh.sub.r.sup.BP(t)e.sup.−jωt),  (4)
where γ=(βe.sup.jωt*h.sub.f.sup.BP(t))e.sup.−jωt is a complex gain. For the purpose of this discussion we assume the return channel h.sub.r.sup.BP(t) is multipath free and is therefore represented as a single tap FIR filter. This allows us to represent the baseband equivalent propagation channel as (γh.sub.r.sup.BP(t)e.sup.−jωt)=αδ(t), which allows h(t) to be rewritten as
h(t)=αp(t).  (5)

(20) This assumption holds when the distance between the RFID detector and the tag is less than a few wavelengths which is the case for many RFID tag applications. Though this description assumes a single tap channel, this model can easily be extended to assume a multipath channel. We also assume the symbols transmitted by the retro-reflective tags are spread with a zero mean spreading sequence {s.sub.n}.sub.n=1.sup.N like a Manchester code. In ASK modulation, this enables accurate estimation and removal of the bias term on the received signal as will be discussed in a later section. This spreading sequence can be modeled as part of the symbol waveform defined in FIG. 3 and allows us to rewrite h(t) as

(21) $\begin{array}{cc}h\left(t\right)=\alpha \underset{n=1}{\overset{N}{.Math.}}{s}_{n}g\left(t-{\mathrm{nT}}_c\right)& \left(6\right)\end{array}$
where N is the length of the spreading sequence, T.sub.c is the chip period, and g(t) is the chip waveform. Because the modulation scheme is ASK, the elements of the transmitted symbol sequence d(m) are constrained to the set {±1+ψ} where ψ is an arbitrary but fixed complex offset that is based on the reflection coefficient of the tag when sending binary symbols b.sub.m ε{±1}. It is assumed that the complex gain due to the reflection coefficient of the tag is already incorporated in the reverse channel model h.sub.r.sup.BP(t). From this definition, equation (2) can be rewritten as

(22) $\begin{array}{cc}y\left(t\right)=\underset{m=1}{\overset{M}{.Math.}}\left[b_m+\psi \right]h\left(t-\mathrm{mT}\right)+\beta +w\left(t\right).& \left(7\right)\end{array}$
Substituting (6) into (7) yields

(23) $\begin{array}{cc}\begin{array}{c}y\left(t\right)=a\underset{m=1}{\overset{M}{.Math.}}\underset{n=1}{\overset{N}{.Math.}}{b}_m{s}_{n}g\left(t-\mathrm{mT}-{\mathrm{nT}}_c\right)+\\ a\psi \underset{m=1}{\overset{M}{.Math.}}\underset{n=1}{\overset{N}{.Math.}}{s}_{n}g\left(t-\mathrm{mT}-{\mathrm{nT}}_c\right)+\beta +w\left(t\right)\end{array}& \left(8\right)\end{array}$

(24) On sampling the complex baseband received signal y(t) at the chip rate T.sub.c during the reception of a single symbol b.sub.m and assuming g(t) is a unit energy Nyquist pulse, (8) can be written as follows with no loss in generality
y=sαb.sub.m+1α.sub.o+w  (9)
where y is the N×1 received signal vector sampled at the output of the chip matched filter, s is the N×1 spreading sequence, 1 is an N×1 all ones vector, α.sub.o=αψ+β and w is the complex Gaussian white noise process with covariance σ.sup.2I.

(25) This single tag model can now be easily expanded to the situation where K tag responses collide. Because the time base for every tag is obtained through the RFID detector reference signal, and because the propagation delay is short relative to a symbol duration, all the colliding tag responses are assumed to be symbol and packet synchronous. This allows us to represent the signal model as the sum of K received vectors.

(26) $\begin{array}{cc}\begin{array}{c}r=\underset{k=1}{\overset{K}{.Math.}}{s}_k{\alpha }_k{b}_{m_k}+1{\alpha }_{a_k}+w\\ =\mathrm{SAb}+\Phi a_o+w\end{array}& \left(10\right)\end{array}$
where k denotes the user index, S is the N×K spreading matrix whose k.sup.th column is S.sub.k, A=diag{α.sub.1, . . . , α.sub.K}, b=[b.sub.m1 . . . , b.sub.mK].sup.T, Φ is an N×K all ones matrix and a.sub.o=[α.sub.o1 . . . , α.sub.oK].sup.T.

(27) Conventional Demodulation

(28) RFID tag systems today employ conventional demodulators to estimate the symbols transmitted from a single tag. This is accomplished by first estimating and removing the bias on the received signal defined in (9) as follows

(29) $\begin{array}{cc}\begin{array}{c}y=y-E\left\{y\right\}\\ ={\mathrm{sab}}_m+1a_o+w-E\left\{{\mathrm{sab}}_m\right\}-E\left\{1a_o\right\}-E\left\{w\right\}\\ ={\mathrm{sab}}_m+1a_o+w-0-1a_o-0\\ ={\mathrm{sab}}_m+w\end{array}& \left(11\right)\end{array}$

(30) We note that E{sαb.sub.m}=0 because, as described above, the spreading sequence s is assumed to be zero mean. From here the complex amplitude α must be estimated. This can be performed using data-aided or non-data-aided maximum likelihood techniques as described in H. Meyr, M. Moenclaey, and S. Fechtel. Digital Communication Receivers. Wiley, New York, N.Y., 1998, herein incorporated by reference.

(31) Once signal parameters have been estimated, a matched filter is used to estimates the bits as follows:

(32) $\begin{array}{cc}{\hat{b}}_m=\mathrm{sgn}\left\{\frac{1}{\alpha }{s}^H\tilde{y}\right\}& \left(12\right)\end{array}$

(33) This approach yields the optimal solution for the reception of a single tag response. However, as soon as there are collisions, as modeled in (10), this solution no longer holds. In fact, in most cases this solution will fail. This failure is due to the large amount of interference from colliding tags caused by a high correlation between the spreading sequences {s.sub.k}.sub.k=1.sup.K, as described in S. Verdu. Multiuser Detection. Cambridge University Press, 1998, incorporated herein by reference.

(34) Multi-User Detection

(35) The present invention uses multiuser detection (“MUD”) analysis to extract and differentiate the transmitted symbols from each of a plurality of colliding packets transmitted simultaneously by a plurality of RFID tags. The details of various multiuser detection analysis methods are presented in references cited below and incorporated herein by reference. Fundamentally, these MUD analysis methods capitalize on differences in signal parameters that apply to the plurality of RFID tags, and exploit these differences so as to differentiate the RFID tag signals from each other. For example, differences in the relative distances and orientations of the RFID tags, as well as differences regarding the number and types of intervening objects, will cause signals from otherwise identical RFID tags to arrive at the RFID detector at slightly different times and with differing amplitudes and phases. There may even be more complicated time-dependent behavior that differentiates the RFID tags, for example if some of the signals are reflected from various objects. In general, the various signal parameters are used as analytical “dimensions” into which the signals from the different RFID tags are separated and thereby distinguished.

(36) Based on this general approach, and on the signal model defined in equation (10), it is therefore clear that in order to estimate the transmitted symbols from each colliding packet, one must first estimate the signal's parameters. FIG. 4 is a functional diagram that illustrates an embodiment in which the parameters include a received signal bias a.sub.o 400, the number of colliding packets K 402, and the channel response 404 for each tag {α.sub.k}.sub.k=1.sup.K as seen at the interrogator. Once these parameters are estimated, each tag's transmitted symbols are estimated jointly across all tags using a multiuser detector algorithm 406.

(37) Signal Bias Estimator

(38) In the multiuser scenario modeled in equation (10), the bias term can be estimated 400 and removed 408 by subtracting the expected value from the received signal vector r. This is the same approach used in the conventional demodulation approach applied to the single tag scenario described above.

(39) $\begin{array}{cc}\begin{array}{c}\tilde{r}=r-E\left\{r\right\}\\ =\mathrm{SAb}+\Phi a_o+w-E\left\{\mathrm{SAb}\right\}-E\left\{\Phi a_o\right\}-E\left\{w\right\}\\ =\mathrm{SAb}+\Phi a_o+w-0-\Phi a_o-0\\ =\mathrm{SAb}+w\end{array}& \left(13\right)\end{array}$

(40) We note that E{SAb}=0 because, as described according to the basic signal model above, each tag's spreading sequence {s.sub.k}.sub.k=1.sup.K is assumed to be zero mean. In practice the expected value of E{r} is estimated by averaging r over several symbol intervals.

(41) Number of Collisions Estimator

(42) With multiple colliding packets the usual method for identifying the number of transmitting sources, namely to count the number of unique eigenvalues of the received signal covariance matrix, will not work. Since the number of symbols being transmitted is relatively small, and since the signals themselves come from a finite alphabet, there is a non negligible probability that some of the signal eigenvalues will be indistinguishable from the noise eigenvalues. As such, this limitation also precludes the use of noise subspace identification methods like MUSIC when the channel is not assumed known and must be estimated.

(43) From equation (10) and the assumptions on the channel, it is assumed that our received signals will arrive in somewhat well defined paired clusters. Since each of these clusters will represent a unique interference pattern for the signal, we can find the number of transmitting tags by using a Number of Collisions Estimator 402 to take log.sub.2 of the number of clusters and to count and identify the centroids of these clusters by employing statistical analysis clustering techniques. While other and various techniques are within the scope of the invention, three examples of these clustering techniques are:

(44) K-Means algorithm

(45) Maximum likelihood solution

(46) T test

(47) For each approach it is assumed that the spreading sequence on each symbol for each user is differentially encoded, for example Manchester encoded, where {s.sub.k}.sub.k=1.sup.K=[1, −1].sup.T. This follows the ISO 18000-6 standard (see International Organization for Standardization, Information Technology, Radio Frequency Identification for Item Management—Part 6: parameters for Air Interface Communications at 860 MHz to 960 MHz, 1st edition, 2004, incorporated herein by reference). These solutions also hold for any other differential encoding scheme, such as FMO coding, that is used in the EPC Global standard (see EPCglobal Inc. Specification for RFID Air Interface, EPC Radio-Frequency Identity Protocols Class-l Generation-2 UHF RFID Protocols for Communications at 860 MHz-960 MHz, Version 1.0.9, 20, incorporated herein by reference).

(48) We begin by defining r.sup.(0) and r.sup.(1) to be the elements of r, which, as described above, correspond to the chip match filter outputs. We also define b.sup.(0) and b.sup.(1) to be the equivalent input bits for r.sup.(0) and r.sup.(1) respectively (b.sup.(0)=b and b.sup.(1)=−b). In the absence of destructive interference, we can assume that r.sup.(i) is monotonically increasing with respect to the amplitudes of A. Now, we define the following received cloud classes:
C.sub.j={r.sup.(i)|b.sup.(i) contains j 1's and (κ−j)−1's}

(49) If we sort the received clouds by their power, then, using our assumption, we find the first received cloud belongs to C.sub.o and the next κ ordered power clouds belong to C.sub.j.

(50) K-Means Algorithm

(51) Briefly stated, the K-Means algorithm tries to minimize the objective function given by

(52) 0$\begin{array}{cc}J\left(\kappa \right)=\underset{j=1}{\overset{\kappa }{.Math.}}\underset{i=1}{\overset{N}{.Math.}}{.Math.x_i^{\left(j\right)}-C_j.Math.}^2& \left(14\right)\end{array}$
where the summand is the distance between the point x.sub.i with prior classification j and the j.sup.th centroid. Here κ is specified as input. The algorithm works by positing a guess for the initial values of C.sub.J and then iterating between the two steps below until convergence:

(53) assign each point x.sub.i to the cluster with the nearest centroids; and

(54) recompute the centroid of each cluster;

(55) The K-Means algorithm itself is not intended to find the number of clusters in a data set. However, there are certain optimality criteria (Schwarz Criterion etc) which can identify κ using the values for J in (14). These criteria work relatively well for large data sets, as shown in FIG. 5, which illustrates that clusters can be well resolved when displayed in complex space 500, and that the cluster resolution or “error distance” decreases as the number of centroids increases 502.

(56) Maximum Likelihood Solution

(57) The maximum likelihood solution takes advantage of the features specific to the RFID clustering problem. These features are:

(58) the variance of each cluster is known and constant throughout all clusters (Noise Power);

(59) there is a 1-1 correspondence between each cluster and its ASK equivalent inverse cluster (From Manchester encoding); and

(60) for large data sets, each cluster will have roughly the same number of elements (Uncorrelated source signals).

(61) For current RFID protocol standards such as EPC Global or ISO 18000-6 the length of the RFID serial number field may not be long enough to satisfy the last condition. However, for new standards this can be fixed by increasing the length of the serial number field. To make use of all the known information given above we compare the likelihood that each block and its Manchester dual came from the Gaussian distribution of its nearest neighbors against the likelihood that the new blocks and the prior clusters came from a mixture density. Mathematically, we choose the null hypothesis if

(62) $\begin{array}{cc}\lambda =\frac{\underset{m=1}{\overset{M}{.Math.}}\underset{n=1}{\overset{2}{.Math.}}{e}^{\frac{-{\left(r_m^H-{\rho }_0^n\right)}^2}{2{\sigma }^2}}}{\underset{m=1}{\overset{M}{.Math.}}\underset{n=1}{\overset{2}{.Math.}}\underset{i=1}{\overset{2}{.Math.}}{\omega }_i{e}^{\frac{-{\left(r_m^n-{\rho }_i^n\right)}^2}{2{\sigma }^2}}}>1& \left(15\right)\end{array}$
where:

(63) n, m, I are indices of the Manchester encoding, received symbol and mixture respectively;

(64) r.sub.m.sup.n is the m.sup.th observation of r which either belongs to or is hypothesized as belonging to the cluster centered around μ.sup.m;

(65) ω.sub.i is the weighting factor for mixture densities (assumed to be 0.5 for two-mixtures);

(66) μ.sub.0.sup.n is the recomputed sample mean of the received block of data together with its nearest cluster;

(67) μ.sub.1.sup.n is the sample mean of the received data block; and

(68) μ.sub.2.sup.n is the sample mean of the closest existing cluster to the received data block.

(69) T Test

(70) A slightly modified T test may be employed to check whether a received block belongs to a previously received cluster. Recall that the test statistic used to determine if two sample sets, A and B, arose from the same distribution is given by

(71) $\begin{array}{cc}t=\frac{.Math.\widehat{{\mu }_A}-\widehat{{\mu }_B}.Math.}{{\sigma }_{\hat{A}B}\sqrt{\frac{1}{n_A}+\frac{1}{n_B}}}& \left(16\right)\end{array}$
where σÂB is the empirical pooled standard deviation. t is distributed according to the t distribution and the probability of type I error is given by the incomplete beta function

(72) $\begin{array}{cc}P\left(H_1|H_0\right)=\frac{1}{\beta \left(0.5v,0.5\right)}{\int }_0^{\frac{v}{\left(v+t^2\right)}}{t^{0.5v}\left(1-t\right)}^{-0.5}dt& \left(17\right)\end{array}$
where ν=n.sub.A+n.sub.B−2 is the degrees of freedom, β is the β function and H.sub.1 is the hypothesis that the samples came from two distributions. Thus, if the type I error falls below a certain predefined threshold, we choose H.sub.1.

(73) A clustering algorithm, then, proceeds as follows.

(74) Upon receiving a new symbol block, find all the existing clusters within 2σ of the sample mean of the new block.

(75) Perform a T test against each of the existing clusters.

(76) If H.sub.1 is returned, verify by checking whether the pooled variance of the block with each existing cluster comes closer to the known noise power with the addition of the new block.

(77) For clusters returning H.sub.0,t test their Manchester inverse clusters with the next received block of symbols, which is the Manchester inverse of the prior block.

(78) Choose to merge the blocks into the clusters that yield the smallest average type I error, where the average is taken across the Manchester clouds. If this error is above the threshold, define two new clusters with the Manchester blocks as their elements.

(79) An alternate approach to estimating the number of collisions is to add a unique training sequence or serial number to each tag that is statically independent from each other sequence. This will increase the overhead per packet reducing overall data rate but will enable the use of subspace techniques such as the MUSIC algorithm or other techniques that count the number of unique eigenvalues of the received signal covariance matrix over measured over only the period of each packet where the training sequences or serial number fields overlap.

(80) Multiuser Channel Estimator

(81) Based on the received signal model defined in equation (10) the channel for each tag is modeled by the Multiuser Channel Estimator 404 as a complex gain α.sub.k incorporated into the diagonal matrix A. To estimate the diagonal elements of A, we only need know which clouds belong to the classes C.sub.0 and C.sub.1. The process is straightforward. Let r.sub.j be a member of C.sub.j. Then
E(r.sub.1−r.sub.0)=SA.Math.2e.sub.k  (18)
where e.sub.k is the unit vector on the k.sup.th basis. Thus, we can derive the K diagonal elements of the diagonal matrix A from taking the sample mean of the κ cloud differences.

(82) Multiuser Detector

(83) Once the signal bias is removed and the number of colliding packets is estimated and each packets channel response is computed, a multiuser detection receiver 406 is employed to jointly demodulate the bits from each users packet.

(84) As illustrated in FIG. 4, once all the signal parameters for each tag response are estimated, they are passed to the multiuser detector along with the unbiased received signal vector r. The maximum likelihood (ML) multiuser detector in this case can be defined as

(85) $\begin{array}{cc}{\hat{b}}_{\mathrm{ML}}=\arg \underset{b\in {\psi }^K}{\min }{\left(r-\mathrm{SAb}\right)}^H\left(r-\mathrm{SAb}\right)& \left(19\right)\end{array}$
where ψ.sup.K is the K dimensional set of all possible symbol hypotheses.

(86) FIG. 6 shows an example of the ML decision tree 600 for an ASK system where K=4. In this case, obtaining the ML solution requires testing 16 hypotheses 602, a manageable complexity to implement in real time based on today's processor capabilities. However because complexity is exponential in the number of users K, this can quickly become much too computationally complex to implement in real time. Low complexity solutions are preferable. Applicant incorporates the following documents in their entirety for all purposes: patent application U.S. Ser. No. 11/035,311 and patents U.S. Pat. No. 6,999,498, U.S. Pat. No. 6,981,203, U.S. Pat. No. 6,967,598, U.S. Pat. No. 6,947,506, U.S. Pat. No. 6,839,390, U.S. Pat. No. 6,831,574, U.S. Pat. No. 6,704,376, U.S. Pat. No. 7,218,690, and U.S. Pat. No. 7,245,673.

(87) Methodfor Incorporating Frequency and Spatial Diversity

(88) It was mentioned previously that in general, the various signal parameters are used as analytical “dimensions” into which the signals from the different RFID tags are separated and thereby distinguished. In some embodiments of the present invention, additional diversity is incorporated into the received RFID tag signals 110 by transmitting the carrier wave 112 on more than one frequency and/or by using a plurality of spatially separated antennae to receive the signals 110.

(89) In particular, with reference to FIG. 7, adding additional frequency diversity adds dimensionality to the problem and makes cluster identification, channel estimation and multiuser detection easier by effectively reducing the cross-correlation between colliding tag responses. Cross-correlation is reduced because for each tag there is a unique channel response, modeled as a complex gain α.sub.k(f), at each frequency that is dependent on the distance l.sub.k between the tag and the interrogator, and on the mean reflection coefficient Φ.sub.k(f) of the tag. Based on free space electromagnetic wave propagation theory described (see W. Hayt, Engineering Electromagnetics, McGraw-Hall, 1989, incorporated herein by reference), the mathematical model of the complex gain at each frequency f for each tag k can be explicitly defined as

(90) $\begin{array}{cc}{\alpha }_k\left(f\right)={\varphi }_k\left(f\right)\exp \left\{-2l_k\zeta \sqrt{f}-j2\pi f\frac{2l_k}{c}\right\}& \left(20\right)\end{array}$
where ζ is the free space attenuation constant and c is the speed of light.

(91) A typical complex gain α.sub.k(f) is presented as a function of frequency for three separate RFID tags in FIGS. 8A and 8B, where FIG. 8A presents the complex amplitudes and FIG. 8B presents the corresponding complex phases. It can be seen in FIGS. 8A and 8B that the magnitudes and phases of the complex gains for the three tags 800, 802, 804, are different from each other at almost all frequencies, and that the magnitude and phase for each tag 800, 802, 804 varies significantly across the frequency range. The five transmitting frequencies of FIG. 7 are indicated as vertical, dashed lines 806 in FIGS. 8A and 8B. If the carrier wave is transmitted on all of these frequencies 806 simultaneously, the fact that each magnitude and phase response from each example tag will not be identical means that the response from the tag reflections will also not be identical for each tag across each measured frequency. This will serve to further separates clusters of responses in a higher dimensional space. With one frequency the clustering is measured in two dimensions (amplitude and phase). With multiple frequencies the clustering is measured in amplitude and phase for each frequency, resulting in 2×N dimensions where N is the number of frequencies and 2 refers to the amplitude and phase dimension measured at each frequency. In FIGS. 8A and 8B, N=5.

(92) To impart this frequency diversity an interrogator may be used that transmits at several distinct frequencies 700 all Δf Hz apart 702. In a realizable system the number of frequencies P and the difference between frequencies Δf should be selected based on the assumed range distribution of the tags relative to the interrogator. P should be selected relative to the mean of the set {l.sub.k}.sub.k=1.sup.K because P is directly proportional to the maximum resolvable distance l.sub.max. To provide more optimal diversity gain it is desired to increase the total frequency range Δf as much as possible because Δf is inversely proportional to the resolvable distance resolution Δl. To understand how this frequency diversity is incorporated into the parameter estimation and multiuser detection algorithms we rewrite equation (10) to incorporate the added frequency diversity as follows:
{hacek over (r)}={hacek over (S)}{hacek over (A)}b+{hacek over (Φ)}{hacek over (a)}.sub.o+{hacek over (w)}  (21)
where {hacek over (r)} is the NP×1 received signal vector, {hacek over (S)} is the NP×KP block diagonal matrix where each block diagonal component is S, {hacek over (A)}=[A(1).sup.T, . . . , A(P).sup.T].sup.T, A(f)=diag{α.sub.1(f), . . . , α.sub.K(f)}, {hacek over (Φ)} is an NP×KP block diagonal matrix with block diagonal elements φ, {hacek over (α)}.sub.0 is a KP×1 vector of complex offsets α.sub.okf, and {hacek over (w)} the NP×1 white Gaussian noise vector.

(93) From this model neither the bias estimator nor the multiuser channel response estimator will change. However, there will be a unique estimate for each at each frequency. This can be obtained by passing the elements of r into each one frequency at a time. The number of collisions estimator will not change but now the clustering will be performed in a 2P dimensional space instead of the 2-dimensional complex plane. The multiuser detector algorithm will remain unchanged but its performance will greatly increase due to the reduced cross correlation between colliding packets.

(94) It is important to note that similar gains can be obtained by incorporating spatial diversity into the RFID detector by adding multiple antenna elements to the receiver chain in different physical locations. In this case, the array spacing affects diversity. The system model for this approach also reduces to the same model defined above for adding frequency diversity. In this case the algorithms will perform just as described above.

(95) By employing frequency or spatial diversity techniques described above the correlation between each colliding tag is reduced. This increased the performance of any algorithms used to estimate the number of collisions and the channel response. It also improves the performance of any multiuser detector.

(96) The foregoing description of the embodiments of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of this disclosure. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.