[0001] The present invention relates generally to Radio Frequency Identification (RFID) systems and more specifically to RFID systems utilizing phased array antennas.

BACKGROUND

[0002] RFID systems can be used to track, identify, and/or locate items. Such systems conventionally include RFID tags that are affixed to the items, an RFID reader that includes a transmit antenna to send activation signals to the RFID tags and a receive antenna to receive backscattered response signals from the activated tags. As a limitation, many RFID systems require that the RFID reader be within close proximity to the activated RFID tag in order to correctly receive the response signal. The backscattered response signal is more vulnerable to interferences as the distance between the RFID tag and the receive antenna increases. Further, the backscattered response signal may travel multiple paths to the receiver antenna creating multipath distortion.

[0003] The theory of compressive sampling, also known as compressed sensing or CS, is a novel sensing/sampling paradigm that allows one to recover signals from far fewer samples or measurements than once thought to be possible. The following overview of CS is largely drawn from Emmanuel J. Candes and Michael B. Wakin, An Introduction to Compressive Sampling, IEEE Signal Processing Magazine 21 (March 2008).

[0004] CS in practice allows for designing sampling protocols that allow for capturing less data while still maintaining the ability to reconstruct the signal of interest. The two fundamental requirements for CS protocols are that (1 ) the signals of interest must be "sparse" and (2) the sensing modality must have a sufficient degree of "incoherence". [0005] By way of background, sparsity expresses the idea that the "information rate" of a continuous time signal may be much smaller than suggested by its bandwidth, or that a discrete-time signal depends on a number of degrees of freedom, which is comparably much smaller than its (finite) length. More precisely, CS exploits the fact that many natural signals are sparse or compressible in the sense that they have concise representations when expressed in an appropriate basis.

[0006] Incoherence extends the duality between time and frequency and expresses the idea that objects have a sparse representation in one domain can be spread out in the domain in which they are acquired, just as a Dirac or spike in the time domain is spread out in the frequency domain. Put differently, incoherence says that unlike the signal of interest, the sampling/sensing waveforms are capable of having an extremely dense representation in an appropriate domain.

SPARSITY

[0007] Systems that perform CS typically are faced with the problem in which information about a signal f(t) is obtained by linear functionals recording the values:

Vk = (f> ⁽ Pk)

[0008] In a standard configuration, the objects that the system acquires are correlated with the waveform cpk {t). If the sensing waveforms are Dirac delta functions (spikes), for example, then y is a vector of sampled values of f in the time or space domain. If the sensing waveforms are sinusoids, then y is a vector of Fourier coefficients; this is the sensing modality used in magnetic resonance imaging MRI.

[0009] Systems can apply CS to recover information in undersampled situations. Undersampling refers to a circumstance in which the number M of available measurements is much smaller than the dimension N of the signal f. In such situations, a CS protocol is tasked with solving an underdetermined linear system of equations. Letting A denote the M χ N sensing or measurement matrix with the vectors φ , ... , φ ^* M as rows (a* is the complex transpose of a), the process of recovering f e M ^N from y=Afe]R ^M is ill-posed in general when M<N: there are infinitely many candidate signals for f. Shannon's theory indicates that, if f(t) has low bandwidth, then a small number of (uniform) samples will suffice for recovery. Using CS, signal recovery can actually be made possible using a broader class of signals. [0010] Many natural signals have concise representations when expressed convenient basis. Mathematically speaking, a vector feE ^N can be expanded orthonormal basis Ψ=[ψι ψ2 . . . ΨΝ] as follows:

where x is the coefficient sequence of f, x,= <f, ipk> .

[0011] It can be convenient to express f as Ψ (where Ψ is the N*N matrix with ψι , . . . , ijj _n as columns). The implication of sparsity is now clear: when a signal is a sparse expansion, the small coefficients can be discarded without much perceptual loss. Formally, consider f _s (t) obtained by keeping only the terms corresponding to the S largest values of (x,). By definition ί ₈ :=Ψχ ₈ , where x _s is the vector of coefficients (x,) with all but the largest S set to zero. This vector is sparse in a strict sense since all but a few of its entries are zero. Since Ψ is an orthonormal basis, Ilf-fsll=llx ^_ xsllt2, and if x is sparse or compressible in the sense that the sorted magnitudes of the (x,) decay quickly, then x is well approximated by x _s and, therefore, the error ||f-f _s || _t 2 is small. In plain terms, one can "throw away" a large fraction of the coefficients without much loss. As can be appreciated, sparsity is a fundamental modeling tool which permits efficient fundamental signal processing; e.g., accurate statistical estimation and classification, efficient data compression, etc. Sparsity has more surprising and far-reaching implications, however, which is that sparsity has significant bearing on the acquisition process itself. Sparsity determines how efficiently one can acquire signals nonadaptively.

INCOHERENT SAMPLING

[0012] Consider a pair (Φ, Ψ) of orthonormal bases or orthobases of M ^N . The first basis Φ is used for sensing the object f and the second Ψ is used to represent f. The coherence between the sensing basis Φ and the representation basis Ψ is [0013] In plain English, coherence measures the largest correlation between any two elements of Φ and Ψ. If Φ and Ψ contain correlated elements, the coherence is large. Otherwise, it is small. As for how large and how small, it follows from linear algebra that μ(Φ, Ψ)ε[1 , VN] .

[0014] Compressive sampling is mainly concerned with low coherence pairs of bases. Such bases include the time frequency pair where Φ is the canonical or spike basis and Ψ is the Fourier basis, and wavelet bases for Ψ and noiselet basis for Φ. Random matrices are largely incoherent with any fixed basis Ψ. Select an orthobasis Φ uniformly at random, then with high probability, the coherence between Φ and Ψ is about V(2 log N). In terms of hardware cost and complexity, it is desirable if the signal basis, Ψ, does not need to be known a priori in order to determine a viable sensing matrix Φ. Fortunately, random sensing matrices with sufficient sample size exhibit low coherence with any fixed basis. This means that a random sensing matrix can acquire sufficient measurements to enable signal reconstruction of a sparse signal without knowing a priori the proper basis Ψ for the signal.

UNDERSAMPLING AND SPARSE SIGNAL RECOVERY

[0015] Ideally, the N coefficients of f are observed, but in reality a CS system can only observe a subset of these and collect the data y _k = (f, <& _k ), keM where Me[1 , . . . , n] is a subset of cardinality M<N.

[0016] With this information, a conventional approach is to recover the signal by - norm minimization. Essentially, for all objects consistent with the data, find the object with the coefficient sequence that minimizes the h-norm. The use of the h-norm as a sparsity-promoting function traces back several decades. A leading early application was reflection seismology, in which a sparse reflection function (indicating meaningful changes between subsurface layers) was sought from bandlimited data. However h- norm minimization is not the only way to recover sparse solutions; other methods, such as greedy algorithms, or Orthogonal Matching Pursuit can also be utilized. [0017] In view of the above, CS suggests a very concrete acquisition protocol: sample nonadaptively in an incoherent domain and invoke linear programming after the acquisition step. Following this protocol enables the acquisition of a signal in a compressed form. A decoder can then "decompress" this data.

SUMMARY OF THE INVENTION

[0018] RFID systems for locating RFID tags utilizing phased array antennas and compressed sensing processing techniques in accordance with embodiments of the invention are disclosed. In one embodiment of the invention, an RFID system includes at least one exciter that includes at least one transmit antenna configured to transmit an activation signal to activate an RFID tag; a phased antenna array that includes a plurality of receive antennas configured to receive a backscattered response signal from the activated RFID tag; and an RFID receiver system configured to communicate with the at least one exciter and connected to the phased antenna array, where the RFID receiver system is configured to locate an RFID tag by performing reads of the RFD tag at multiple frequencies using the at least one exciter and the plurality of receive antennas of the phased antenna array, generating a measurement matrix for each of the plurality of receive antennas using the phase of the backscattered response signals from the activated RFID tag at each of the multiple frequencies, and determining a line of sight (LOS) distance between the activated RFID tag and each of the plurality of receive antennas by eliminating bases from the measurement matrix.

[0019] In a further embodiment, the RFID system of claim 1 , where performing reads of the RFID tag at multiple frequencies also includes selecting a new transmit carrier frequency for the activation signal and instructing the at least one exciter to send the activation signal at the new transmit carrier frequency.

[0020] In another embodiment, the RFID system of claim 2, where performing reads of the RFID tag at multiple frequencies also includes receiving the backscattered response signal from the activated RFID tag using each of the plurality of receive antennas of the phased antenna array and measuring at least a phase associated with the received backscattered response signal. [0021] In a still further embodiment, the RFID system of claim 3, where generating a measurement matrix also includes selecting a basis function representing the distance travelled from the exciter to the RFID tag to each of the plurality of receive antennas of the phased antenna array.

[0022] In still another embodiment, the RFID system of claim 1 , where eliminating bases from the measurement matrix also includes deconvolving the measurement matrix; sequentially eliminating a basis from the basis function corresponding to distance outward from the RFID receiver system; calculating and minimizing error after elimination of each successive basis; and determining if the calculated error is greater than a threshold value.

[0023] In a yet further embodiment, the RFID system of claim 5, where the threshold value can be determined using a stopping rule.

[0024] In yet another embodiment, the RFID system of claim 6, where sequentially eliminating a basis also includes eliminating the shortest remaining basis by a predetermined distance each time.

[0025] In a further embodiment again, the RFID system of claim 7, where calculating and minimizing error after elimination of each successive basis also includes forcing a convex optimization process to fit with the remaining basis.

[0026] In another embodiment again, the RFID system of claim 1 , where eliminating bases from the measurement matrix also includes placing an upper limit on the estimate of the line of sight distance.

[0027] In a further additional embodiment, the RFID system of claim 1 , where the RFID receiver system is also configured to locate an RFID tag by defining a plurality of elliptical representations using the at least one exciter, the RFID tag, and each of the plurality of receive antennas of the phased antenna array.

[0028] In another additional embodiment, the RFID system of claim 10, where the RFID receiver system is also configured to locate an RFID tag using the determined line of sight distance and the plurality of elliptical representations to locate the RFID tag as the intersection of a first ellipse and a second ellipse. BRIEF DESCRIPTION OF THE DRAWINGS

[0029] FIG. 1 is a schematic diagram of a distributed exciter architecture showing transmit and receive coverage areas and exciter interrogation spaces for an RFID system in accordance with an embodiment of the invention.

[0030] FIG. 2 illustrates an RFID system utilizing elliptical representations for determining the location of an RFID tag in accordance with the prior art.

[0031] FIG. 3 illustrates an exciter, RFID tag, and RFID receiver and a multipath propagation of a backscattered response signal from an activated RFID tag to the RFID receiver in accordance with an embodiment of the invention.

[0032] FIG. 4 is a flow chart illustrating a process for locating RFID tags utilizing CS techniques in accordance with an embodiment of the invention.

[0033] FIG. 5 is a flow chart illustrating a process for activating RFID tags using multiple transmit frequencies in accordance with an embodiment of the invention.

[0034] FIG. 6 is a flow chart illustrating a process for eliminating multipath distortion and locating the line of sight (LOS) distance between RFID receivers and RFID tags in accordance with an embodiment of the invention.

DETAILED DESCRIPTION

[0035] Referring now to the drawings, systems and methods for locating radio frequency identification (RFID) tags utilizing phased array antennas and compressed sensing (CS) processing techniques are described. The systems and methods utilize group delay measurements and CS techniques to reduce the effects of multipath distortion on backscattered response signals received at the RFID receiver. The systems include estimating the line of sight (LOS) distance between RFID tags and RFID receivers by creating a measurement matrix and selecting appropriate basis functions to eliminate multipath distortion. By successively eliminating a basis and observing the effects on error calculations, the system is able to accurately determine the LOS distance from the RFID receiver to the RFID tag. The LOS distance is determined for each receive antenna of a phased antenna array and the RFID tag is located using the system and method described in U.S. Patent No. 8,082,31 1 entitled "Radio Frequency Identification Tag Location Estimation and Tracking System and Method", issued December 6, 201 1 , the disclosure of which is incorporated by reference herein in its entirety.

[0036] A variety of RFID reader configurations can be used in accordance with embodiments of the invention including, but not limited to, configurations in which the transmit and receive functions of the reader are decoupled and can be performed by separate exciters and RFID receivers as described in U.S. Patent Application No. 12/054,331 , filed March 23, 2007 and allowed October 5, 2012, entitled "RFID Systems Using Distributed Exciter Network", the disclosure of which is incorporated by reference as if set forth in full herein.

DISTRIBUTED ARCHITECTURE

[0037] An RFID system including a distributed exciter architecture in accordance with an embodiment of the invention is shown in FIG. 1 . The RFID system (1 -1 ) includes an RFID receiver system (1 -2) connected to a phased antenna array (1 -4) and a plurality of exciters (1 -6, 1 -14, 1 -18, 1 -23, 1 -28) that are daisy chained to the RFID receiver system via cables (1 -10, 1 -9, 1 -16, 1 -22, 1 -26). The RFID receiver system (1 -2) is also connected to a LAN (1 -32) via connection (1 -34). An RFID application server (1 - 30) is connected to the LAN via connection (1 -36). Although the plurality of exciters are shown as wired, in many embodiments exciters communicate wirelessly with the RFID receiver system.

[0038] In operation, the RFID receiver system (1 -2) controls the activation of exciters. The cable segments (1 -10, 1 -9, 1 -16, 1 -22, 1 -26) carry both direct current (DC) power and control commands from the RFID receiver system (1 -2) to each exciter. The transmitted "backhaul signal" from the RFID receiver system (1 -2) to the exciters embeds signal characteristics and parameters that can be used to generate a desired waveform output from the exciter module to an RFID tag. In several embodiments, each exciter can be commanded and addressed by an N-bit address, N-ranging from 16-to- 32 bit. The exciters (1 -6, 1 -14, 1 -18, 1 -23, 1 -28) can be operated sequentially or concurrently, depending on the number of possible beams the RFID receiver system can support. In the illustrated embodiment, the RFID receiver system (1 -2) includes a single phased antenna array (1 -4) and is capable of generating a single beam. In other embodiments, the RFID receiver system includes multiple antenna arrays and is capable of generating multiple beams.

[0039] The interrogation space and transmitted power of each exciter can be managed and controlled by the RFID receiver system (1 -2). In the illustrated embodiment, the RFID receiver system (1 -2) controls the exciters to create interrogation space (1 -8, 1 -15, 1 -20, 1 -24, 1 -29) of different sizes. In addition, the received coverage area is configurable. The RFID receiver system can receive signals from the complete coverage area (1 -1 1 ). Alternatively, the RFID receiver system can adaptively beam-form to the specified exciter interrogation spaces (1 -12,1 -21 ).

[0040] The RFID application server (1 -30) schedules each exciter to operate harmoniously in multiple dimensions, which are time, frequency and space. In a number of embodiments, the RFID application server (1 -30) includes a scheduler for S/T/FDM (Space, Time and Frequency Division Multiplexing), which utilizes an optimization algorithm to maximize the probability of successful manipulation of all the RFID tags within a target interrogation space. In addition, the controller may utilize frequency hopping in scheduling the frequency channel for each exciter in order to satisfy various regulatory constraints. Although specific RFID systems including a distributed architecture are discussed above with respect to FIG. 2, any of a variety of RFID system architectures as appropriate to the requirements of a specific application can be utilized in accordance with embodiments of the invention. Processes for determining RFID tag locations using elliptical representation are discussed below.

RFID TAG LOCATION USING ELLIPTICAL REPRESENTATION

[0041] In several embodiments of the invention, the RFID system observes a backscattered response signal from activated RFID tags including the signal's phase information. Phase differences observed at various transmit frequencies can provide range information. The ratio of phase difference to frequency difference, referred to as group delay, can provide estimates of the path length between exciters, RFID tags and receive antennas. Using the path lengths and known relative distances between exciters and RFID receivers, an elliptical representation can be utilized to locate RFID tags.

[0042] An RFID system utilizing elliptical representations for determining the location of an RFID tag using a receiver antenna array in accordance with the prior art is shown in FIG. 2. The RFID system (200) includes an RFID receiver antenna array (1 -4) with a first receive antenna RXi (202) and N-1 additional antennas such that the last antenna is RX _N (204). The ellipse (210) is formed using exciter (206) and RXi (202) as the focus points. The ellipse (212) is formed using exciter (206) and RXN (204) as the focus points. Additional ellipses are formed using the exciter (206) and the additional N-1 receive antennas of the antenna array (1 -4).

[0043] The location of an RFID tag (208) is also shown. The exciter is configured to transmit interrogation signals and the receive antennas are configured to receive signals backscattered by the RFID tag. Each receive antenna is a known distance from the exciter, for example RXi (202) and RXN (204) are spaced a distance d1 and d'1 , respectively relative to the exciter (206). Path length from the exciter to tag to receiver, also known as the ETR distance, can be represented as the distance d2+d3 to receive antenna RXi (202) and d'2+d'3 to receive antennas RXN (204). The ETR distance can be determined using group delay observations and the systems and methods described in U.S. Patent No. 8,082,31 1 entitled "Radio Frequency Identification Tag Location Estimation and Tracking System and Method", issued December 6, 201 1 , incorporated by reference above. Accordingly, the ETR distances can be used with a priori known receive antenna and exciter locations to create elliptical representations such that the RFID system can locate RFID tags. In many embodiments of the invention, the RFID tag (208) is located as the intersection of a first ellipse (210) and a second ellipse (212). The method of locating RFID tags utilizing group delay observations and elliptical representation becomes more accurate with additional receive antennas utilized. However, interferences can negatively affect locating RFID tags as further discussed below. [0044] The backscattered response signal of an activated RFID tag can take multiple paths to reach the RFID receiver. The receive antenna cannot decipher how many paths, if any, a backscattered response signal has traveled and thus leads to so called multipath distortion. An illustration of multipath distortion in accordance with an embodiment of the invention is shown in FIG.3. The backscattered response signal bounces off obstacle (302) in route to the receive antenna RXi (202) and thus travels via two paths, d3 and d4+d5. As discussed above, the additional paths negatively impact correctly determining the LOS distance between RFID tag and RFID receiver. Although not illustrated in FIG.3, there can be more than one obstacle and thus increased multipath distortion.

[0045] Although specific process for determining the location of an RFID tag using elliptical representation utilizing a phased antenna array are discussed above with respect to FIG. 2, any of a variety RFID receiver antenna array configurations as appropriate for specific applications can be utilized in accordance with embodiments of the invention. Processes for locating RFID tags utilizing compressed sensing techniques in accordance with embodiments of the invention are discussed further below.

LOCATING RFID TAGS UTILIZING CS TECHNIQUES

[0046] In a compressed sensing approach, the signal received at each receive antenna is assumed to be a sum of the multipath with different distances and phases. In several embodiments of the invention, the received signal wave is deconvolved to express the received signal as the sum of n different distances that the backscattered signal travelled through such that: for each of the transmit frequencies. [0047] In several embodiments of the invention, the RFID system measures phase of a received signal at 50 frequency channels (the number of channels allowed in the United States that are open for RFID air communications), where more channels increase sparsity. The CS technique calls for selecting as few basis vectors as possible that still satisfy a given constraint. Knowing a priori that the signal of interest lies in the LOS path, many embodiments of the invention use a successive initial basis elimination (SIBE) approach to give an upper bound on the positive error. In various embodiments, error statistics can be computed via Monte-Carlo simulations and tabulated for the first and second moments for several noise figures.

[0048] A process for locating RFID tags utilizing CS techniques in accordance with an embodiment of the invention is shown in FIG. 4. The process (400) includes performing (404) reads of RFID tags at multiple frequencies as discussed further below. Using the backscattered response signals, a measurement matrix is generated (406). The process (400) includes reducing (408) multipath effects and locating (410) the LOS distance. In a number of embodiments, multipath effects are reduced by using a successive initial basis elimination (SIBE) approach, which is discussed further below. Although, in other embodiments any of a variety of processes can be used to eliminate bases from the bases used to construct the measurement matrix to determine the LOS distance as appropriate to the requirements of specific applications. Using the LOS distance, the RFID tag can be located (412). Although specific processes for locating RFID tags utilizing CS techniques are discussed above with respect to FIG. 4, any of a variety of processes for locating RFID tags utilizing CS techniques as appropriate to the requirements of a specific application can be utilized in accordance with embodiments of the invention. Processes for performing RFID tags reads using multiple transmit frequencies are discussed further below.

PERFORMING RFID TAG READS AT MULTIPLE TRANSMIT FREQUENCIES

[0049] In several embodiments of the invention, the exciter transmits activation signals to the RFID tag using multiple frequencies. A process for performing reads of RFID tags using multiple transmit frequencies in accordance with an embodiment of the invention is shown in FIG. 5. The process (500) includes selecting (504) a new transmit frequency and instructing (506) the exciter to send an activation signal to the RFID tag. The RFID receiver receives (508) the backscattered information signal from the activated RFID tag. The process further includes measuring (510) the phase of the received information signal. If an additional frequency is available then process (500) is repeated from step (504). If no additional frequency is available then process (500) is complete. Although specific processes for performing reads of RFID tags with multiple transmit frequencies are discussed above with respect to FIG. 5, any of a variety of processes for performing reads of RFID tags using multiple transmit frequencies as appropriate to the requirements of a specific application can be utilized in accordance with embodiments of the invention. Processes for eliminating multipath effects using a successive initial basis elimination approach are discussed further below.

ELIMINATING MULTIPATH DISTORTION

[0050] CS techniques can be utilized to eliminate multipath distortion and determine the LOS distance. A successive initial basis elimination (SIBE) approach is posed by minimizing the following expression:

(1 - γ) ||-4χ - Λ|| ₁ + γ||χ|| ₁ where A is a M_basis x N_frequency matrix consisting of the basis for each frequency, x is a M_basis by 1 complex weight vector, and b is a N_frequency x 1 complex vector of beamforming coefficients that are measured from each of the RFID tag reads. The vector b includes the observations from the response signal and L1 norm of Ax - b describes how well the Ax matches the observations. In several embodiments, a L2 norm of Ax - b can be utilized to describe how well the Ax matches the observations. Using a convex optimization process, the system determines the lowest coefficient that contributes the most to the observation and once that coefficient is removed from the observation vector, the error significantly increases. When no noise is present, the shortest (nearest to 0) component of the estimate often corresponds to the true LOS path. The choice of γ within 0.1 to 0.9 does not give significant difference in the simulated multipath. The SIBE approach exploits the LOS by successively eliminating the shortest basis by a predetermined distance away from the RFID receiver each time and hence forcing the convex optimization process to fit with the remaining basis. [0051] A process for eliminating the effects of multipath in determining the LOS distance in accordance with an embodiment of the invention is shown in FIG. 6. The process (600) includes deconvolving (604) the measurement matrix. A basis is sequentially eliminated (608) outward from the RFID receiver. After elimination of each successive basis, the process includes calculating and minimizing (610) error as described below. The change in error is compared (612) to a threshold value. In several embodiments, the threshold value can be determined by a stopping rule that can be predetermine or determined in real-time. If the change in error is not greater than a determined threshold, the process (600) is repeated from step (604). If the change in error is greater than threshold, the LOS is distance is determined (614) as described below. In several embodiments of the invention, the LOS distance is then used to locate the RFID tag utilizing elliptical representation.

[0052] Process (600) sequentially eliminates the shortest basis by a predetermined distance each time and generates a misalignment which increases the mean square error (MSE) fit if the true LOS path is eliminated. By detecting the pivot point where significant error occurs by comparing the error to a threshold value, the RFID system can estimate the true LOS distance. Process (600) also puts an upper limit on the estimate since the error significantly increases once the LOS path is removed from the basis. Although specific processes for locating RFID tags by eliminating multipath distortion using CS techniques are discussed above with respect to FIG. 6, any of a variety of processes for locating RFID tags by eliminating multipath distortion using CS techniques as appropriate to the requirements of a specific application can be utilized in accordance with embodiments of the invention.

[0053] While the above description contains many specific embodiments of the invention, these should not be construed as limitations on the scope of the invention, but rather as an example of one embodiment thereof. Accordingly, the scope of the invention should be determined not by the embodiments illustrated, but by the appended claims and their equivalents.