Method and apparatus for efficiently querying and identifying multiple items on a communication channel

• US 6,727,803 B2
• Filed: 03/16/2001
• Issued: 04/27/2004
• Est. Priority Date: 03/16/2001
• Status: Active Grant

• Current Assignee: E-Tag Systems Incorporated
• Original Assignee: E-Tag Systems Incorporated
• Inventors: Hulvey, Robert
• Primary Examiner(s): Horabik, Michael
• Assistant Examiner(s): BANGACHON, WILLIAM L
• Application Number:
  US09/811,110
• Publication Number:
  US 20020130766A1
• Time in Patent Office: 1,138 Days
• Field of Search: 340/10.31, 340/10.32, 340/10.1, 340/10.2, 340/825.02, 340/825.56, 340/10.51, 340/10.52, 370/437, 370/458, 370/346, 370/312, 370/445, 370/449, 707/100, 707/101, 707/3, 711/128, 711/118
• US Class Current: 340/10.31
• CPC Class Codes: G06K 19/0723 the record carrier comprising an arrangement for non-contact communication, e.g. wireless communication circuits on transponder cards, non-contact smart cards or RFIDs
• 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/10049 binary tree

Abstract

Systems and methods for efficiently querying and identifying multiple items on a communication channel are disclosed. The invention is well suited to use with radio frequency identification with interrogation devices and systems that identify radio frequency identification transponders. A depth-first tree traversal protocol algorithm, including commands and symbols, is used to more efficiently interrogate a plurality of transponders in a short amount of time.

Claims

1. A method for identifying each of a plurality of objects using an interrogation process on a single communication channel, wherein an interrogating device capable of simultaneously communicating with a plurality of objects to be identified has access to the single communication channel, each object to be identified contains within it an identification number in the form of a plurality of digits enumerated in a predetermined sequence, each object contains a push-counter capable of counting from zero up to at least the number of digits contained within the identification number times N−

1, where N is the number of possible digit values, each object has the ability to communicate with the interrogating device and to provide predetermined responses to indicate the value of the digits contained in its respective identification number, wherein the responses for different values are such that they may be unambiguously discerned by the interrogating device even when two or more types of responses are returned simultaneously by the objects being interrogated, and wherein a response for a given value may be returned by two or more transponders and be distinguishable from the absence of any response, comprising the steps of;

activating said plurality of objects, to enable them to participate in the interrogation process,

interrogating a single digit within the predetermined sequence from all activated objects, to obtain a predetermined response from each of the plurality of objects indicative of the value of the digit being interrogated,

recording the value of each predetermined response obtained in the step of interrogating,

signaling each object with a non-zero push-counter value to add (N−

1) to its push-counter when two or more possible response values are detected,

signaling each object that responds with any but the highest valued currently available digit to add [(N−

1)−

digit value] to its push-counter when two or more possible response values are detected by the interrogating device,

recording an incomplete sequence of identification digits received by the interrogating device since the last step of activating,

signaling each object, which has a non-zero push-counter value to decrement its push-counter when one or more complete identification numbers are recorded and incomplete identification numbers remain to be completely identified,

terminating the method if none of the objects respond to the interrogating device,

recording complete identification numbers received,

allowing each object to no longer respond to the interrogating device when complete identification is obtained,

requiring each object with a zero push-counter value to respond to the interrogating device, and

continuing the step of interrogating until a complete identification number is obtained for each object.

2. The method of claim 1, comprising the alternate step of activating the plurality of objects to enable them to participate in the interrogation process when none of the objects respond to the interrogating device.

3. The method of claim 1, wherein two or more responses are received in response to the interrogation of the last digit in an identification number, wherein multiple complete identification numbers are identified by appending different possible digits to N different recorded incomplete sequences of identification digits.

4. The method of claim 1, wherein more than one identification number is identified when two or more possible response values are detected by the interrogating device and the response values represent the last digit interrogated in the identification number.

5. A method for identifying each of a plurality of objects using an interrogation process on a single communication channel, wherein an interrogating device capable of simultaneously communicating with objects to be identified has access to the communication channel, each object to be identified contains within it a representation of a complete identification number in the form of a plurality of binary digits enumerated in a predetermined sequence;

each digit having a binary value of zero or one, each object has the ability to communicate with the interrogating device, each object contains a push-counter capable of counting from zero up to at least the number of digits contained within the identification number, each object has the ability to communicate to the interrogating device predetermined responses that may be unambiguously discerned by the interrogating device to indicate the value of the digits contained in its respective identification number, all of said responses being distinguishable from an absence of response, the interrogation process comprising the steps;

(a) activating said plurality of objects, enabling them to participate in the interrogation process,

(b) interrogating a single bit, from all of said plurality of objects to obtain one of the predetermined responses indicative of ones of the plurality of binary bits in its respective identification number from each of said objects,

(c) recording each binary value received during the predetermined responses,

(d) signaling each of the objects that responded with any but one of the possible binary values and each object with a non-zero push-counter to increment its push-counter if both possible responses are received by the interrogating device in step (b),

(e) signaling each of the objects that incremented its push-counter to no longer respond until its push-counter is decremented to zero value if both possible responses are received by the interrogating device in step (b),

(f) recording an incomplete identification number sequence of identification digits received since the last step of activating,

(g) signaling each object having a non-zero value in its push-counter prior to step (d) to increment its push-counter if both possible responses are received by the interrogating device in step (b),

(h) appending the value received to the record of the incomplete identification number sequence received since the most recent step of activating if only one response value is detected,

(i) terminating the method when an absence of response is detected,

(j) repeating steps since the last step of activating until the complete identification number is obtained for at least one of said objects,

(k) recording the complete identification number received,

(l) signaling transponders that have a non-zero push-counter value to decrement their push counter values such that at least one transponder contains a zero-valued push-counter value, those transponders whose push-counters become zero becoming active and responding with the next digit, and

(m) repeating the foregoing steps following the step of activating until all of the recorded incomplete identification number sequences have been completed, and identification numbers are unambiguously obtained from each of the plurality of objects.

6. The method of claim 5, comprising the step of retrieving the last recorded incomplete identification number sequence recorded in step (f).

7. The method as in claim 5, wherein a response is not detected following the step of interrogating a single bit, the method further comprising the alternative step of starting the method anew.

8. The method as in claim 5, wherein the step of recording the complete identification number comprises the step of identifying more than one complete identification number when multiple digital response values are detected by the interrogation device upon interrogating the least significant digit in the complete identification number.

9. The method as in claim 5, wherein the signaling operation of step (l) also performs the interrogation operation of step (b).

10. The method as in claim 5, wherein steps (d) and (e) are combined into a single step.

11. The method as in claim 5, wherein steps (d) and (g) are combined into a single step.

12. The method as in claim 5, wherein steps (e) and (g) are combined into a single step.

13. The method as in claim 5, wherein steps (d), (e) and (g) are combined into a single step.

14. Identification apparatus within an object to be identified over a communication medium, wherein an interrogation device provides interrogation and reset signals, comprising:

means for communication with said interrogating device over the communication medium,

means for storing an identification number unique to said object,

bit-counter means for counting the current digit being interrogated by the interrogation device,

means for responding to interrogations with predetermined responses which represent the value of the current digit being interrogated,

push-counter means for accumulating “

push”

values in response to an increment signal,

means for detecting signals from the interrogation device to increment said push-counter means,

means for adding a value to said push-counter means in response to said increment signals wherein;

if the push-counter means value is 0, then (N−

1) minus the value of the current digit is added,

if the push-counter means value is non-zero, then (N-1) is added,

means for detecting said interrogation signals to decrement said push-counter means,

means for subtracting a value from the push-counter means in response to said decrement signals,

means for inhibiting response to interrogation when said push-counter means contains a non-zero value,

means for detecting said reset signal, and

means for resetting said bit-counter means and push-counter means values to zero in response to said reset signal.

15. Interrogation apparatus for interrogating objects to be identified over a communication medium, wherein the objects provide predetermined responses indicative of object identification numbers and further include push-counters, comprising:

first means for sending interrogation signals to and receiving responses from the objects over the communication medium, said interrogation signal operating to interrogate a single digit from the objects to be identified,

second means for recording incomplete identification numbers whenever two or more predetermined responses are received from the objects,

third means for retrieving incomplete identification numbers whenever two or more predetermined responses are received from the objects,

fourth means for sending a signal to the objects to cause the objects to add a number to their push-counters, wherein the number is determined by each object and is dependent upon the object'"'"'s previous responses to interrogation signals,

fifth means for sending a signal to the objects to cause objects to subtract a number from their push-counters, wherein the number is determined by each object and is dependent upon the object'"'"'s previous responses to the interrogation signals, and

sixth means for recording complete identification numbers as they are determined.

16. A method for identifying each of a plurality of objects using an interrogation process on a single communication channel, wherein

an interrogating device capable of simultaneously communicating with a plurality of objects to be identified has access to the signal communication channel,

each object to be identified contains within it a representation of a complete identification number in the form of a plurality digits, enumerated in an arbitrary predetermined sequence;

each digit having a value which may be mapped one-to-one to an integer value from 0 to N−

1, where N is the number of possible digit values, each object has the ability to communicate with the interrogating device, but not necessarily with other like objects, each object contains an internal counter capable of counting from zero up to at least the number of digits contained within the identification number times N−

1, where N is the number of possible digit values, said counter being hereafter referred to as the push—

counter, each object has the ability to communicate to the interrogating device predetermined responses to indicate the value of any of the digits contained in its respective identification number, said responses chosen such that all responses may be unambiguously discerned by the interrogating device even if two or more types of responses are returned simultaneously by the objects being interrogated, and all of said responses are distinguishable from the absence of any response, comprising the steps of

a) activating said plurality of objects, thereby enabling them to participate in the interrogation process,

b) interrogating a single digit from all currently activated objects, according to the predetermined sequence chosen for each object, from all of said plurality of objects to obtain one of the predetermined responses from each of said objects indicating the value of the digit being interrogated within the respective objects,

c) recording the value of said responses received in step (b),

d) signaling each of those objects which responded with any but the highest valued possible digit, if two or more possible responses are detected by the interrogating device in step (b), to add the difference between (N−

1) and its integer digit value to its push counter,

e) signaling each of said objects which was signaled to increase its push counter in step (d) to no longer respond until signaled to decrement its push-counter and its push-counter reaches zero,

f) recording the incomplete sequence of identification digits received thus far since the last execution of step (a) or retrieved in step (1) for those objects which were signaled to increase their push-counters in step (d),

g) signaling each of said objects, which had non-zero push-counter value prior to step (d), if two or more possible responses were detected by the interrogating device in step (b), to add N−

1 to its push-counter value,

h) appending the value received to the record of the sequence of digits received thus far since the most recent execution of step (a) or retrieved in step (1) if only one response was detected in step (b),

i) terminating the method if no object response was detected in step (b) whereby an error is presumed to have occurred,

j) repeating steps (b), (c), (d), (e), (1), (g), (h) and (i) until the complete identification number is obtained for at least one of said objects,

k) recording the complete identification number(s) received as having been successfully read, wherein more than one identification number may be identified if multiple responses are detected by the interrogation device upon interrogating the last digit of the identification number

l) retrieving the last incomplete identification sequence recorded in step (f), if any, otherwise proceeding to step (n),

m) signaling the plurality of transponders which have a non-zero push-counter value to decrease their push-counter values such that at least one transponder contains a non-zero push-counter value, those transponders whose push-counters become zero becoming active and responding with the next digit, and

n) repeating steps (b), (c), (d), (e), (f), (g), (h), (i), (j), (k), (l) and (m) until all of the incomplete identification sequences recorded in step (f) have been exhausted, and said identification numbers are unambiguously obtained from said plurality of objects over the single communication channel.

17. The method as in claim 16, wherein a response is not detected in step (b), comprising the alternative step of starting the method anew instead of terminating the method.

18. The method as in claim 16, wherein two or more responses are received in step (b) in response to the interrogation of the last digit, comprising the alternative step of obtaining multiple complete identification numbers, and skipping steps (d), (e), (f), (g), (h), (i) and (j) for the last digit.

19. The method as in claim 16, wherein two or more signaling operations of steps (d), (c), and (g) are combined into a single step.

20. A method for identifying each of a plurality of objects using an interrogation process on a single communication channel, wherein:

an interrogating device capable of simultaneously communicating with objects to be identified has access to the communication channel, each object to be identified contains within it a representation of an identification number in the form of a plurality of binary digits, hereafter bits, enumerated in an arbitrary predetermined sequence, each digit having a value of zero or one, each object has the ability to communicate with the interrogating device, but not necessarily with other like objects, each object contains a push-counter capable of counting from zero up to at least the number of digits contained within the identification number, each object has the ability to communicate to the interrogating device predetermined responses to indicate the value of any of the digits contained in its respective identification number, said responses chosen such that all responses may be unambiguously discerned by the interrogating device even if two responses are returned simultaneously by the objects being interrogated, and all of said responses are distinguishable from the absence of any response, comprising the steps of;

a) activating said plurality of objects, enabling them to participate in the interrogation process,

b) interrogating a single bit, according to the predetermined sequence chosen for each object, from all of said plurality of objects to obtain one of the predetermined responses from each of said objects indicating the value of the bit being interrogated within the respective objects,

c) recording the value of said responses upon receiving said predetermined responses,

d) signaling each of said objects, which responded with any, but one of the possible digit values to increment its push-counter if both, possible responses are detected by the interrogating device in step (b),

e) signaling each of said objects, which incremented its push-counter in step (d) to no longer respond until signaled to decrement its push-counter and its push-counter reaches zero if both possible responses were detected by the interrogating device in step (b),

f) recording the incomplete sequence of identification digits received thus far since the last execution of step (a) or retrieved in step (l) for those objects which were signaled to increase their push-counters in step (d),

g) signaling each of said objects which had a non-zero push-counter value prior to step (d) to increment its push-counter in response to said signal if both possible responses were detected by the interrogating device in step (b),

h) appending the value received to the record of the sequence of bits received thus far since the most recent execution of step (a) or retrieved in step (l) if only one response is detected in step (b),

i) terminating the method if no object response is detected whereby an error is presumed to have occurred,

j) repeating steps (b), (c), (d), (e), (f), (g), (h) and (i) until all of the plurality of binary digits are obtained for at least one of said objects,

k) recording the complete identification number received as having been successfully read, wherein more than one identification number may be identified if multiple responses are detected by the interrogation device upon interrogating the last digit in the identification number,

l) retrieving the last incomplete identification sequence recorded in step (f), if any, otherwise proceeding to step (n),

m) signaling the plurality of objects that have a non-zero push-counter value to decrement their push-counter values such that at least one transponder contains a non-zero push-counter value, those transponders whose push-counters become zero becoming active and responding with the next digit, and

n) repeating said steps (b), (c), (d), (e), (f), (g), (h), (i), (j) (k), (l), and (m) until all of the incomplete identification sequences recorded in step (f) have been exhausted and said identification numbers are unambiguously obtained from said plurality of objects over the communication channel.

21. The method as in claim 20, wherein a response is not detected in step (b), wherein alternative to step (i) the is started method anew.

22. The method as in claim 20, wherein two responses are received in step (b) in response to the interrogation of a last digit, wherein multiple complete identification numbers are recorded and steps (d), (e), (f), (g), (h), (i) and (j) may be skipped for the last digit.

23. The method as in claim 20, wherein the signaling operation of step (m) also performs the interrogation operation of step (b).

24. The method as in claim 20, comprising the step of combining the signaling operations of steps (d) and (e) into a single step.

25. The method as in claim 20, comprising the step of combining the signaling operations of steps (d) and (g) into a single step.

26. The method as in claim 20, comprising the step of combining the signaling operations of steps (e) and (g) into a single step.

27. The method as in claim 20, comprising the step of combining the signaling operations of steps (d), (e), and (g) into a single step.

28. Identification apparatus within an object to be identified over a communication medium wherein an interrogation device provides interrogation and reset signals, comprising:

first means for communication with the interrogating device over the communication medium

second means for storing an identification number unique to said object,

third means including at least a bit-counter for counting the current digit being interrogated by the interrogation device,

fourth means for responding to interrogations with predetermined responses which represent the value of the current digit being interrogated,

fifth mean including at least a push-counter for accumulating “

push”

values and for receiving an increment signal,

sixth means for detecting said increment signals to increment the means for accumulating,

seventh means for adding a value to said means for accumulating in response to said increment signals wherein;

if the means for accumulating value is 0, then (N−

1) minus the value of the current digit is added

if the means for accumulating value is non-zero, then (N−

1) is added

eighth means for detecting said interrogation signals from the interrogation device to decrement said means for accumulating,

ninth means for subtracting a value from the push-counter in response to said decrement signals,

tenth means for inhibiting response to interrogation when said push-counter contains a non-zero value,

eleventh means for detecting said reset signal from the interrogation device, and

twelfth means for resetting said bit-counter and push-counter values to zero in response to said reset signal.

29. Interrogation apparatus for interrogating objects to be identified over a communication medium, wherein the objects provide predetermined responses indicative of object identification numbers and further include push-counters, comprising:

first means for sending signals to and receiving signals from said objects over the communication medium,

second means for recording and later retrieving incomplete identification numbers whenever two or more predetermined responses are received from said objects,

third means for sending a signal to the objects to cause said objects to add a number to their push-counters, said number to be determined by each individual object and dependent upon said individual object'"'"'s previous responses to the interrogation,

fourth means for sending a signal to the objects to cause said objects to subtract a number from their push-counters, said number to be determined by each individual object and dependent upon said individual object'"'"'s previous responses to the interrogation,

fifth means for recording complete identification numbers as they are determined; and

sixth means for sending a signal to interrogate a single digit from the objects to be identified.