Scheduling in an RFID system having a coordinated RFID tag reader array

• US 7,817,014 B2
• Filed: 07/29/2005
• Issued: 10/19/2010
• Est. Priority Date: 07/30/2004
• Status: Active Grant

• Current Assignee: Quake Global, Inc.
• Original Assignee: Reva Systems Corp. (Quake Global, Inc.)
• Inventors: Fischer, Jeffrey H., Husak, David J., Stephenson, Robert A., Krishna, Pattabhiraman
• Primary Examiner(s): Brown; Vernal U
• Application Number:
  US11/194,127
• Publication Number:
  US 20060022800A1
• Time in Patent Office: 1,908 Days
• Field of Search: 340/10.2, 340/10.1, 340/825.69, 340/825.72, 340/10.5, 340/10.3, 340/825.58
• US Class Current: 340/10.4
• CPC Class Codes: G01S 5/02525 Gathering the radio frequency fingerprints
• CPC Class Codes: G01S 5/06 Position of source determined by co-ordinating a plurality of position lines defined by path-difference measurements G01S5/12 takes precedence
• CPC Class Codes: G06K 17/0029 the arrangement being specially adapted for wireless interrogation of grouped or bundled articles tagged with wireless record carriers
• CPC Class Codes: G06K 7/0008 General problems related to the reading of electronic memory record carriers, independent of its reading method, e.g. power transfer
• CPC Class Codes: G06K 7/10356 using a plurality of antennas, e.g. configurations including means to resolve interference between the plurality of antennas

Abstract

A system and method of scheduling RFID tag interrogations by a plurality of RFID readers so as to mitigate the effects of interference within an RFID environment in which the readers are deployed, and to enhance the efficiency and reliability of the overall RFID system. The system includes a plurality of RFID receivers for receiving RFID tag data, a plurality of RFID tag interrogators for transmitting RF interrogation signals for interrogating RFID tags, and a controller for providing to at least one interrogator, at least one receiver, and at least one tag, a parameter associated with operational characteristics of the interrogator, the receiver, and the tag, respectively. The interrogator, the receiver, and the tag are operative, in response to receipt of the respective parameter, to modify its operational characteristics in accordance with the respective parameter, thereby avoiding interference at the receivers and the tags.

Claims

1. Apparatus for use in a radio frequency identification (RFID) tag data acquisition system including at least one RFID tag, at least one RFID tag interrogator for transmitting at least one RF interrogation signal for interrogating said at least one RFID tag, and at least one RFID receiver for receiving RFID tag data from said at least one RFID tag, said apparatus comprising:

at least one controller operative to generate at least one parameter associated with operational characteristics of at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag, and to forward the respective at least one parameter to said at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag,

wherein the respective at least one parameter is generated by said at least one controller to avoid interference at least one RFID tag during the transmission of said at least one RF interrogation signal by said at least one RFID tag interrogator, and to avoid interference at least one RFID receiver during the reception of said RFID tag data from said at least one RFID tag,

wherein the respective at least one parameter comprises at least one scheduling parameter,

wherein said at least one RFID tag interrogator is operative to transmit said at least one RF interrogation signal for interrogating said at least one RFID tag using a plurality of carrier frequencies in a specified frequency hop sequence, and

wherein said at least one controller is further operative to generate said at least one scheduling parameter based at least in part upon information relating to said specified frequency hop sequence, and to forward said at least one scheduling parameter to said at least one RFID tag interrogator to schedule in time the transmission of said at least one RF interrogation signal, thereby avoiding at least one collision in frequency involving said at least one RF interrogation signal.

2. The apparatus of claim 1:

wherein said at least one RFID tag interrogator has at least one frequency table associated therewith, said at least one frequency table including the information relating to said specified frequency hop sequence; and

wherein said at least one controller is operative to access the information relating to said specified frequency hop sequence included in said at least one frequency table.

3. Apparatus for use in a radio frequency identification (RFID) tag data acquisition system including at least one RFID tag, at least one RFID tag interrogator for transmitting at least one RF interrogation signal for interrogating said at least one RFID tag, and at least one RFID receiver for receiving RFID tag data from said at least one RFID tag, said apparatus comprising:

at least one controller operative to generate at least one parameter associated with operational characteristics of at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag, and to forward the respective at least one parameter to said at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag,

wherein the respective at least one parameter is generated by said at least one controller to avoid interference at least one RFID tag during the transmission of said at least one RF interrogation signal by said at least one RFID tag interrogator, and to avoid interference at least one RFID receiver during the reception of said RFID tag data from said at least one RFID tag,

wherein said system further includes a plurality of RFID tag interrogators,

wherein said at least one controller is further operative to select at least one of said plurality of RFID tag interrogators for subsequent control thereof, and to assign, based upon an RFID tag interrogator selection algorithm, at least one associated frequency channel and at least one associated time slot to the respective at least one of said plurality of RFID tag interrogators for subsequent use in scheduling at least one RF signal transmission by the respective at least one of said plurality of RFID tag interrogators,

wherein said RFID tag interrogator selection algorithm is operative to determine a set of unassigned frequency channels {F_free}, a first subset of inactive RFID tag interrogators U, and a second subset of inactive RFID tag interrogators U′

,

wherein

U={i|S_i(t)≦

T,1≦

i≦

R},

i being an index corresponding to a respective one of the plurality of RFID tag interrogators, S_i(t) being an earliest time that the respective one of the plurality of RFID tag interrogators having index i can be active during time slot t without violating duty cycle requirements of the respective RFID tag interrogators, T being a current time value, and R being a set of inactive RFID tag interrogators, wherein each of the first subset of inactive RFID tag interrogators U and the second subset of inactive RFID tag interrogators U′

is a subset of the set of inactive RFID tag interrogators R, and

wherein the second subset of inactive RFID tag interrogators U′

includes at least one inactive RFID tag interrogator for which

E_i(t)=E_min and i∈

U,

E_i(t) being a latest time that the respective one of the plurality of RFID tag interrogators having index i can be active during time slot t without violating duty cycle requirements of the respective RFID tag interrogators, and E_min being a minimum value of E_i(t) for the inactive RFID tag interrogators having index i contained within the first subset of inactive RFID tag interrogators U.

4. The apparatus of claim 3 wherein said at least one controller is operative to allocate frequency channels for use by said plurality of RFID tag interrogators in transmitting respective RF interrogation signals based upon a frequency channel selection algorithm.

5. The apparatus of claim 4 wherein said frequency channel selection algorithm comprises an iterative maximal matching algorithm operative to match at least one RFID tag interrogator contained within the second subset of inactive RFID tag interrogators U′

with at least one frequency channel contained within the set of unassigned frequency channels {F_free}.

6. The apparatus of claim 4 wherein said at least one controller is operative to generate at least one schedule comprising a sequence of matches between respective ones of said plurality of RFID tag interrogators and the respective at least one associated frequency channel over a predetermined time based upon said allocation of frequency channels.

7. The apparatus of claim 4 wherein said at least one controller is operative to assign said at least one associated frequency channel to the respective at least one selected RFID tag interrogator within the respective associated time slot based upon priority assignment criteria.

8. Apparatus for use in a radio frequency identification (RFID) tag data acquisition system including at least one RFID tag, at least one RFID tag interrogator for transmitting at least one RF interrogation signal for interrogating said at least one RFID tag, and at least one RFID receiver for receiving RFID tag data from said at least one RFID tag, said apparatus comprising:

at least one controller operative to generate at least one parameter associated with operational characteristics of at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag, and to forward the respective at least one parameter to said at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag,

wherein the respective at least one parameter is generated by said at least one controller to avoid interference at least one RFID tag during the transmission of said at least one RF interrogation signal by said at least one RFID tag interrogator, and to avoid interference at least one RFID receiver during the reception of said RFID tag data from said at least one RFID tag,

wherein said system further includes a plurality of RFID receivers,

wherein said at least one controller is further operative to select at least one of said plurality of RFID receivers for subsequent control thereof, and to assign, based upon an RFID receiver selection algorithm, at least one associated frequency channel and at least one associated time slot to the respective at least one selected RFID receiver for subsequent use in scheduling at least one RF signal reception of said at least one RFID receiver,

wherein said RFID receiver selection algorithm is operative to determine a set of unassigned frequency channels {F_free}, a first subset of inactive RFID receivers U, and a second subset of inactive RFID receivers U′

,

wherein

U={i|S_i(t)≦

T,1≦

i≦

R},

being an index corresponding to a respective one of the plurality of RFID receivers, S_i(t) being an earliest time that the respective one of the plurality of RFID receivers having index i can be active during time slot t without violating duty cycle requirements of the respective RFID receivers, T being a current time value, and R being a set of inactive RFID receivers, wherein each of the first subset of inactive RFID receivers U and the second subset of inactive RFID receivers U′

is a subset of the set of inactive RFID receivers R, and

wherein the second subset of inactive RFID receivers U′

includes at least one inactive RFID receiver for which

E_i(t)=E_min and i∈

U,

E_i(t) being a latest time that the respective one of the plurality of RFID receivers having index i can be active during time slot t without violating duty cycle requirements of the respective RFID receivers, and E_min being a minimum value of E_i(t) for the inactive RFID receivers having index i contained within the first subset of inactive RFID receivers U.

9. The apparatus of claim 8 wherein said at least one controller is operative to allocate frequency channels for use by said plurality of RFID receivers in receiving respective RF signals based upon a frequency channel selection algorithm.

10. The apparatus of claim 9 wherein said frequency channel selection algorithm comprises an iterative maximal matching algorithm operative to match at least one RFID receiver contained within the second subset of inactive RFID receivers U′

with at least one frequency channel contained within the set of unassigned frequency channels {F_free}.

11. The apparatus of claim 9 wherein said at least one controller is operative to generate at least one schedule comprising a sequence of matches between respective ones of said plurality of RFID receivers and the respective at least one associated frequency channel over a predetermined time based upon said allocation of frequency channels.

12. The apparatus of claim 9 wherein said at least one controller is operative to assign said at least one associated frequency channel to the respective at least one selected RFID receiver within the respective associated time slot based upon priority assignment criteria.

13. The apparatus of claim 9 wherein said frequency channel selection algorithm is operative to match each of said plurality of RFID receivers with a respective one of the frequency channels, and to generate co-interference information for each matching of the RFID receivers with the respective frequency channels, said co-interference information including information relating to interference at the respective RFID receivers taking into account spatial separations between the respective RFID receivers.

14. The apparatus of claim 13 wherein said frequency channel selection algorithm is operative to represent said co-interference information in a matrix format.

15. The apparatus of claim 13 wherein said co-interference information includes information relating to a number of non-interfering RFID receiver and frequency channel matches that can co-exist with each matching of the RFID receivers with the respective frequency channels.

16. A method of operating a radio frequency identification (RFID) tag data acquisition system, said system including at least one RFID tag, at least one RFID tag interrogator, and at least one RFID receiver, said method comprising the steps of:

in a transmitting step, transmitting, by said at least one RFID tag interrogator, at least one RF interrogation signal for interrogating said at least one RFID tag;

receiving, by said at least one RFID receiver, RFID tag data from said at least one RFID tag, said RFID tag data being provided by said at least one RFID tag in response to being interrogated by said at least one RFID tag interrogator;

in a generating step, generating, by at least one controller, at least one parameter associated with operational characteristics of at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag,

wherein the respective at least one parameter is generated by said at least one controller to avoid interference at least one of said at least one RFID tag during the transmission of said at least one RF interrogation signal by said at least one RFID tag interrogator, and said at least one RFID receiver during the reception of said RFID tag data from said at least one RFID tag;

in a forwarding step, forwarding, by said at least one controller, the respective at least one parameter to said at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag,

wherein said transmitting step includes transmitting, by said at least one RFID tag interrogator, said at least one RF interrogation signal for interrogating said at least one RFID tag using at least one selected carrier frequency,

wherein the respective at least one parameter corresponds to said at least one selected transmit carrier frequency, and

wherein said at least one RFID tag interrogator has at least one frequency table associated therewith, said at least one frequency table including information relating to a plurality of carrier frequencies;

accessing, by said at least one controller, the information relating to said plurality of carrier frequencies included in said at least one frequency table;

in a first selecting step, selecting, by said at least one controller, said at least one transmit carrier frequency from said plurality of carrier frequencies included in said at least one frequency table,

wherein said system further comprises a plurality of RFID tag interrogators;

in a second selecting step, selecting at least one of said plurality of RFID tag interrogators for subsequent control thereof by said at least one controller;

in an assigning step, assigning at least one associated frequency channel and at least one associated time slot to the respective at least one of said plurality of RFID tag interrogators by said at least one controller;

scheduling at least one RF signal transmission by the respective at least one of said plurality of RFID tag interrogators based upon the at least one frequency channel and the at least one time slot associated with the respective at least one of said plurality of RFID tag interrogators by the at least one controller,

wherein said second selecting step and said assigning step are performed according to an RFID tag interrogator selection algorithm,

wherein said RFID tag interrogator selection algorithm comprises the steps of determining a set of unassigned frequency channels {F_free}, determining a first subset of inactive RFID tag interrogators U, and determining a second subset of inactive RFID tag interrogators U′

,

wherein

U={i|S_i(t)≦

T,1≦

i≦

R},

i being an index corresponding to a respective one of the plurality of RFID tag interrogators, S_i(t) being an earliest time that the respective one of the plurality of RFID tag interrogators having index i can be active during time slot t without violating duty cycle requirements of the respective RFID tag interrogators, T being a current time value, and R being a set of inactive RFID tag interrogators, wherein each of the first subset of inactive RFID tag interrogators U and the second subset of inactive RFID tag interrogators U′

is a subset of the set of inactive RFID tag interrogators R, and

wherein the second subset of inactive RFID tag interrogators U′

includes at least one inactive RFID tag interrogator for which

E_i(t)=E_min, and i∈

U,

E_i(t) being a latest time that the respective one of the plurality of RFID tag interrogators having index i can be active during time slot t without violating duty cycle requirements of the respective RFID tag interrogators, and E_min being a minimum value of E_i(t) for the inactive RFID tag interrogators having index i contained within the first subset of inactive RFID tag interrogators U.

17. The method of claim 16 including the step of allocating frequency channels for use by said plurality of RFID tag interrogators in transmitting respective RF interrogation signals by said at least one controller.

18. The method of claim 17 wherein said allocating step is performed according to a frequency channel selection algorithm.

19. The method of claim 18 wherein said frequency channel selection algorithm comprises the step of employing an iterative maximal matching technique to match at least one RFID tag interrogator contained within the second subset of inactive RFID tag interrogators U′

with at least one frequency channel contained within the set of unassigned frequency channels {F_free}.

20. The method of claim 18 including the step of generating at least one schedule comprising a sequence of matches between respective ones of said plurality of RFID tag interrogators and the respective at least one associated frequency channel over a predetermined time based upon said allocation of frequency channels by said at least one controller.

21. The method of claim 18 including the step of assigning said at least one associated frequency channel to the respective at least one selected RFID tag interrogator within the respective associated time slot based upon priority assignment criteria.

22. The method of claim 17 wherein said assigning step includes assigning said at least one associated frequency channel to the respective at least one selected RFID receiver within the respective associated time slot based upon priority assignment criteria.

23. The method of claim 17 wherein said frequency channel selection algorithm comprises the steps of matching each of said plurality of RFID receivers with a respective one of the frequency channels, and generating co-interference information for each matching of the RFID receivers with the respective frequency channels, said co-interference information including information relating to interference at the respective RFID receivers taking into account spatial separations between the respective RFID receivers.

24. The method of claim 23 wherein said frequency channel selection algorithm comprises the step of representing said co-interference information in a matrix format.

25. A method of operating a radio frequency identification (RFID) tag data acquisition system, said system including at least one RFID tag, at least one RFID tag interrogator, and at least one RFID receiver, said method comprising the steps of:

in a transmitting step, transmitting, by said at least one RFID tag interrogator, at least one RF interrogation signal for interrogating said at least one RFID tag;

receiving, by said at least one RFID receiver, RFID tag data from said at least one RFID tag, said RFID tag data being provided by said at least one RFID tag in response to being interrogated by said at least one RFID tag interrogator;

in a generating step, generating, by at least one controller, at least one parameter associated with operational characteristics of at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag,

wherein the respective at least one parameter is generated by said at least one controller to avoid interference at least one of said at least one RFID tag during the transmission of said at least one RF interrogation signal by said at least one RFID tag interrogator, and said at least one RFID receiver during the reception of said RFID tag data from said at least one RFID tag;

in a forwarding step, forwarding, by said at least one controller, the respective at least one parameter to said at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag,

wherein said transmitting step includes transmitting, by said at least one RFID tag interrogator, said at least one RF interrogation signal for interrogating said at least one RFID tag using at least one selected carrier frequency,

wherein the respective at least one parameter corresponds to said at least one selected transmit carrier frequency, and

wherein said at least one RFID tag interrogator has at least one frequency table associated therewith, said at least one frequency table including information relating to a plurality of carrier frequencies;

accessing, by said at least one controller, the information relating to said plurality of carrier frequencies included in said at least one frequency table;

in a first selecting step, selecting, by said at least one controller, said at least one transmit carrier frequency from said plurality of carrier frequencies included in said at least one frequency table,

wherein said system further comprises a plurality of RFID receivers;

in a second selecting step, selecting at least one of said plurality of RFID receivers for subsequent control thereof by said at least one controller;

in an assigning step, assigning at least one associated frequency channel and at least one associated time slot to the respective at least one selected RFID receiver by said at least one controller; and

scheduling at least one RF signal reception of said at least one RFID receiver by said at least one controller,

wherein said second selecting step and said assigning step are performed according to an RFID receiver selection algorithm,

wherein said RFID receiver selection algorithm comprises the steps of determining a set of unassigned frequency channels {F_free}, determining a first subset of inactive RFID receivers U, and determining a second subset of inactive RFID receivers U′

,

wherein

U={i|S_i(t)≦

T,1≦

i≦

R},

i being an index corresponding to a respective one of the plurality of RFID receivers, S_i(t) being an earliest time that the respective one of the plurality of RFID receivers having index i can be active during time slot t without violating duty cycle requirements of the respective RFID receivers, T being a current time value, and R being a set of inactive RFID receivers, wherein each of the first subset of inactive RFID receivers U and the second subset of inactive RFID receivers U′

is a subset of the set of inactive RFID receivers R, and

wherein the second subset of inactive RFID receivers U′

includes at least one inactive RFID receiver for which

E_i(t)=E_min and i∈

U,

E_i(t) being a latest time that the respective one of the plurality of RFID receivers having index i can be active during time slot t without violating duty cycle requirements of the respective RFID receivers, and E_min being a minimum value of E_i(t) for the inactive RFID receivers having index i contained within the first subset of inactive RFID receivers U.

26. The method of claim 25 including the step of allocating frequency channels for use by said plurality of RFID receivers in receiving respective RF signals by said at least one controller.

27. The method of claim 26 wherein said allocating step is performed according to a frequency channel selection algorithm.

28. The method of claim 27 wherein said frequency channel selection algorithm comprises the step of employing an iterative maximal matching technique to match at least one RFID receiver contained within the second subset of inactive RFID receivers U′

with at least one frequency channel contained within the set of unassigned frequency channels {F_free}.

29. A method of operating a radio frequency identification (RFID) tag data acquisition system, said system including at least one RFID tag, at least one RFID tag interrogator, and at least one RFID receiver, said method comprising the steps of:

transmitting, by said at least one RFID tag interrogator, at least one RF interrogation signal for interrogating said at least one RFID tag;

receiving, by said at least one RFID receiver, RFID tag data from said at least one RFID tag, said RFID tag data being provided by said at least one RFID tag in response to being interrogated by said at least one RFID tag interrogator;

generating, by at least one controller, at least one parameter associated with operational characteristics of at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag,

wherein the respective at least one parameter is generated by said at least one controller to avoid interference at least one of said at least one RFID tag during the transmission of said at least one RF interrogation signal by said at least one RFID tag interrogator, and said at least one RFID receiver during the reception of said RFID tag data from said at least one RFID tag; and

forwarding, by said at least one controller, the respective at least one parameter to said at least one of said at least one RFID tag interrogator, said at least one RFID receiver, and said at least one RFID tag,

wherein said system further includes a plurality of RFID tag interrogators,

wherein said method further includes;

in a selecting step, selecting at least one of said plurality of RFID tag interrogators for subsequent control thereof by said at least one controller;

in an assigning step, assigning at least one associated frequency channel and at least one associated time slot to the respective at least one of said plurality of RFID tag interrogators by said at least one controller; and

scheduling at least one RF signal transmission by the respective at least one of said plurality of RFID tag interrogators based upon the at least one frequency channel and the at least one time slot associated with the respective at least one of said plurality of RFID tag interrogators by the at least one controller,

wherein said selecting step and said assigning step are performed according to an RFID tag interrogator selection algorithm,

wherein said RFID tag interrogator selection algorithm comprises;

determining a set of unassigned frequency channels {F_free};

determining a first subset of inactive RFID tag interrogators U; and

determining a second subset of inactive RFID tag interrogators U′

,

wherein

U={i|S_i(t)≦

T,1≦

i≦

R},

i being an index corresponding to a respective one of the plurality of RFID tag interrogators, S_i(t) being an earliest time that the respective one of the plurality of RFID tag interrogators having index i can be active during time slot t without violating duty cycle requirements of the respective RFID tag interrogators, T being a current time value, and R being a set of inactive RFID tag interrogators,

wherein each of the first subset of inactive RFID tag interrogators U and the second subset of inactive RFID tag interrogators U′

is a subset of the set of inactive RFID tag interrogators R, and

wherein the second subset of inactive RFID tag interrogators U′

includes at least one inactive RFID tag interrogator for which

E_i(t)=E_min and i∈

U,

E_i(t) being a latest time that the respective one of the plurality of RFID tag interrogators having index i can be active during time slot t without violating duty cycle requirements of the respective RFID tag interrogators, and E_min being a minimum value of E_i(t) for the inactive RFID tag interrogators having index i contained within the first subset of inactive RFID tag interrogators U, and

wherein said method further includes;

allocating frequency channels for use by said plurality of RFID tag interrogators in transmitting respective RF interrogation signals by said at least one controller; and

generating at least one schedule comprising a sequence of matches between respective ones of said plurality of RFID receivers and the respective at least one associated frequency channel over a predetermined time based upon said allocation of frequency channels by said at least one controller.