Power-efficient technique for multiple tag discrimination

• US 5,521,601 A
• Filed: 04/21/1995
• Issued: 05/28/1996
• Est. Priority Date: 04/21/1995
• Status: Expired due to Term

• Current Assignee: Intermec IP Corporation (Honeywell International Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Krishna, Arvind, Kandlur, Dilip D.
• Primary Examiner(s): Sotomayor, John B.
• Application Number:
  US08/426,507
• Time in Patent Office: 403 Days
• Field of Search: 342/42, 342/44, 342/51
• US Class Current: 342/44
• 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/10069 the collision being resolved in the frequency domain, e.g. by hopping from one frequency to the other frequency hopping or spread spectrum techniques H04B7/00

Abstract

This invention provides a tag identification system and method for identifying tags in the range of a reader station where the tags are divided into smaller groups, where the tags are identified one group at a time so as to save power by powering off the tags that are not in the group currently being identified. Each tag puts itself in a group by performing calculations from parameters stored in itself and from parameters received from the reader station. In another variation of this invention, only tags which configure themselves to be activated at a final frequency are identified. The set of tags which configure themselves to be activated at the final frequency changes with each identification round until all tags in the range of the reader have been identified.

Claims

1. In a tag identification system having only a single two-way communications channel between a reader and a plurality of tags in the range of the reader, where the identification of the tags is not initially known to the reader, where the tags can be activated by the reader in response to signals on a single frequency, and where each tag can deactivate itself, a method of identifying all of the tags in the range of the reader, the method comprising:

a. broadcasting a first signal and a first query message from the reader, the first signal being used to activate all of the tags, and the first query message containing a first indication of the number of the tags in the range of the reader station;

b. each of the tags storing an IDENTIFIED indication that it is not yet identified by the reader in its non-volatile memory, in response to the first query message;

c. each of the tags performing a corresponding computation based upon the first indication, random bits at each tag, and the stored IDENTIFIED indication in response to the first query message received, with each of the tags deactivating itself if its corresponding computation yields a corresponding, predetermined result, thereby forming a first set of remaining, activated tags;

d. identifying each tag of the first set of the activated tags, with each tag of the first set changing its stored IDENTIFIED indication to indicate its successful identification by the reader in said each tag'"'"'s non-volatile memory, with each tag deactivating itself after said successful identification;

e. broadcasting a second signal and a second query message from the reader, the second signal activating all tags in the range of the reader, and the second query message containing a second indication of the number of unidentified tags in the range of the reader;

f. repeating steps c) and d) using the second indication instead of the first indication, thereby creating a second set of remaining activated tags for step d), and thereby increasing the number of tags which have been identified; and

g. repeating steps e) and f) using subsequent signals and query messages with subsequent indications until all of the tags in the range of the reader have been identified.

2. A tag identification system having only a single two-way communications channel between a reader and a plurality of tags in the range of the reader, where the identification of the tags is not initially known to the reader, where the tags can be activated by the reader in response to signals on a single frequency, and where each tag can deactivate itself, a method of identifying all of the tags in the range of the reader, said system comprising:

a. means for broadcasting a first signal and a first query message from the reader, the first signal being used to activate all of the tags, and the first query message containing a first indication of the number of the tags in the range of the reader station;

b. means for each of the tags to store an IDENTIFIED indication that it is not yet identified by the reader in its non-volatile memory, in response to the first query message;

c. means for each of the tags to perform a corresponding computation based upon the first indication, random bits at each tag, and the stored IDENTIFIED indication in response to the first query message received, with each of the tags deactivating itself if its corresponding computation yields a corresponding, predetermined result, thereby forming a first set of remaining, activated tags;

d. means for identifying each tag of the first set of the activated tags, with each tag of the first set changing its stored IDENTIFIED indication to indicate its successful identification by the reader in said each tag'"'"'s non-volatile memory, with each tag deactivating itself after said successful identification;

e. means for broadcasting a second signal and a second query message from the reader, the second signal activating all tags in the range of the reader, and the second query message containing a second indication of the number of unidentified tags in the range of the reader;

f. means for repeating steps c) and d) using the second indication instead of the first indication, thereby creating a second set of remaining activated tags for step d), and thereby increasing the number of tags which have been identified; and

g. means for repeating steps e) and f) using subsequent signals and query messages with subsequent indications until all of the tags in the range of the reader lave been identified.

3. In a tag identification system having only a single two-way communications channel between a reader and a plurality of tags in the range of the reader, where the identification of the tags is not initially known to the reader, where the tags can be activated by the reader in response to signals on a single frequency and where each tag can deactivate itself, a method of identifying all of the tags in the range of the reader, the method comprising:

a. broadcasting a first signal and a first query message from the reader, the first signal being used to activate all of the tags, and the first query message containing a first indication of the number of the tags in the range, and a QUERY-ROUND indication that it is the first query message;

b. each of the tags performing a corresponding computation based upon the first indication and random bits at each tag, and storing the corresponding result, referred to as a ROUND indication, in said each tags own non-volatile memory in response to the first query message received;

c. each of the tags deactivating itself if its ROUND indication does not match the QUERY-ROUND indication, thereby forming a first set of remaining activated tags;

d. identifying each tag of the first set of the activated tags, with each tag of the first set deactivating itself after it has been identified by the reader;

e. broadcasting a second signal and a second query message from the reader, the second signal activating all tags in the range of the reader, and the second query message containing a second QUERY-ROUND indication;

f. repeating steps c) and d) using the second QUERY-ROUND indication instead of the QUERY-ROUND indication, thereby creating a second set of tags for step d; and

g. repeating steps e) and f) using subsequent signals and query messages with subsequent QUERY-ROUND indications until all of the tags in the range of the reader have been identified.

4. In a tag identification system having only a single two-way communications channel between a reader and a plurality of tags in the range of the reader, where the identification of the tags is not initially known to the reader, where the tags can be activated by the reader in response to signals on a single frequency and where each tag can deactivate itself, a method of identifying all of the tags in the range of the reader, the method comprising:

a. means for broadcasting a first signal and a first query message from the reader, the first signal being used to activate all of the tags, and the first query message containing a first indication of the number of the tags in the range, and a QUERY-ROUND indication that it is the first query message;

b. means for each of the tags to perform a corresponding computation based upon the first indication and random bits at each tag, and storing the corresponding result, referred to as a ROUND indication, in said each tags own non-volatile memory in response to the first query message received;

c. means for each of the tags to deactivate itself if its ROUND indication does not match the QUERY-ROUND indication, thereby forming a first set of remaining activated tags;

d. means for identifying each tag of the first set of the activated tags, with each tag of the first set deactivating itself after it has been identified by the reader;

e. means for broadcasting a second signal and a second query message from the reader, the second signal activating all tags in the range of the reader, and the second query message containing a second QUERY-ROUND indication;

f. means for repeating steps c) and d) using the second QUERY-ROUND indication instead of the QUERY-ROUND indication, thereby creating a second set of tags for step d; and

g. means for repeating steps e) and f) using subsequent signals and query messages with subsequent QUERY-ROUND indications until all of the tags in the range of the reader have been identified.

5. In a tag identification system having only a single two-way communications channel between a reader and a plurality of tags in the range of the reader, where the identification of the tags is not initially known to the reader, where the reader can send signals on a plurality of frequencies indexed as 1, 2, . . . , c, where tags have the capability of being activated only in response to a signal on a predetermined one of the plurality of frequencies with the tags remaining deactivated in the presence of signals from the reader station on frequencies other than the predetermined one frequency, each active tag further having the capability of selecting the frequency on which it will next be activated, and where each tag can deactivate itself, a method of identifying all of the tags in the range of the reader, the method comprising:

a. initializing a reading process by setting all the tags to respond to signals of frequency 1 only, by setting each of the tags to indicate that they haven'"'"'t been identified, and by setting a CURRENT_-- FREQUENCY indicator in the reader to frequency 1;

b. broadcasting from the reader a first signal on one of said frequencies indicated by the CURRENT_-- FREQUENCY and broadcasting a first query message, the first signal being used to activate all of the tags which respond to signals on the frequency indicated by the CURRENT_-- FREQUENCY indicator, and the first query message containing a tag estimate indication of the number of the tags in the range of the reader that will be activated in response to the first signal;

c. the reader station decrementing its CURRENT_-- FREQUENCY indicator if it estimates that no tags will be activated in response to the first signal on the frequency indicated by the CURRENT_-- FREQUENCY indicator;

d. identifying all active tags if the CURRENT_-- FREQUENCY indicator is set to the final frequency c, with signals on only the final frequency c being used to identify the active tags, with each of the latter active tags changing its stored IDENTIFIED indication to reflect its successful identification by the reader in said each tags non-volatile memory, and the identified tags configuring themselves to be activated only in response to signals on the first frequency, and each tag deactivating itself after said successful identification, the reader station decrementing its CURRENT_-- FREQUENCY indicator at the end of the identification of all the latter active tags;

e. if the CURRENT_-- FREQUENCY was not the final frequency c, each of the active tags performing a corresponding computation based upon the tag estimate indication, random bits at each tag, and the stored IDENTIFIED indication in response to the first query message received, with each of the tags deactivating itself if its corresponding computation yields a corresponding predetermined result, and said deactivated tags configuring themselves to be activated only in response to signals on the same frequency on which they were activated, the remaining tags other than said deactivated tags configuring themselves to be activated in response to signals on a subsequent frequency instead of the frequency on which they were last activated, the reader station incrementing its CURRENT_-- FREQUENCY indicator, and

f. repeating steps b) through e) until the CURRENT_-- FREQUENCY indicator is set to zero, at which time all of the tags have been identified.

6. In a tag identification system having only a single two-way communications channel between a reader and a plurality of tags in the range of the reader, where the identification of the tags is not initially known to the reader, where the reader can send signals on a plurality of frequencies indexed as 1, 2, . . . , c, where tags have the capability of being activated only in response to a signal on a predetermined one of the plurality of frequencies with the tags remaining deactivated in the presence of signals from the reader station on frequencies other than the predetermined one frequency, each active tag further having the capability of selecting the frequency on which it will next be activated, and where each tag can deactivate itself, a method of identifying all of the tags in the range of the reader, the method comprising:

a. means for initializing a reading process by setting all the tags to respond to signals of frequency 1 only, by setting each of the tags to indicate that they haven'"'"'t been identified, and by setting a CURRENT_-- FREQUENCY indicator in the reader to frequency 1;

b. means for broadcasting from the reader a first signal on one of said frequencies indicated by the CURRENT_-- FREQUENCY and broadcasting a first query message, the first signal being used to activate all of the tags which respond to signals on the frequency indicated by the CURRENT_-- FREQUENCY indicator, and the first query message containing a tag estimate indication of the number of the tags in the range of the reader that will be activated in response to the first signal;

c. means for the reader station to decrement its CURRENT_-- FREQUENCY indicator if it estimates that no tags will be activated in response to the first signal on the frequency indicated by the CURRENT_-- FREQUENCY indicator;

d. means for identifying all active tags if the CURRENT_-- FREQUENCY indicator is set to the final frequency c, with signals on only the final frequency c being used to identify the active tags, with each of the latter active tags changing its stored IDENTIFIED indication to reflect its successful identification by the reader in said each tags non-volatile memory, and the identified tags configuring themselves to be activated only in response to signals on the first frequency, and each tag deactivating itself after said successful identification, the reader station decrementing its CURRENT_-- FREQUENCY indicator at the end of the identification of all the latter active tags;

e. means for, if the CURRENT_-- FREQUENCY was not the final frequency c, each of the active tags to perform a corresponding computation based upon the tag estimate indication, random bits at each tag, and the stored IDENTIFIED indication in response to the first query message received, with each of the tags deactivating itself if its corresponding computation yields a corresponding predetermined result, and said deactivated tags configuring themselves to be activated only in response to signals on the same frequency on which they were activated, the remaining tags other than said deactivated tags configuring themselves to be activated in response to signals on a subsequent frequency instead of the frequency on which they were last activated, the reader station incrementing its CURRENT_-- FREQUENCY indicator; and

f. means for repeating steps b) through e) until the CURRENT_-- FREQUENCY indicator is set to zero, at which time all of the tags have been identified.

7. In a tag identification system having only a single two-way communications channel between a reader and a plurality of tags in the range of the reader, where the identification of the tags is not initially known to the reader, where the reader can send signals on a plurality of frequencies indexed as 1, 2, . . . , c, where tags have the capability of being activated only in response to a signal on a predetermined one of the plurality of frequencies with the tags remaining deactivated in the presence of signals from the reader station on frequencies other than the predetermined one frequency, each active tag further having the capability of selecting the frequency on which it will next be activated, and where each tag can deactivate itself, a method of identifying all of the tags in the range of the reader, the method comprising:

a. broadcasting a first signal and a first query message, the first signal being used to activate all of the tags, and setting a CURRENT_-- FREQUENCY indicator in the reader to frequency 1;

b. each of the tags performing a corresponding computation based upon the first query message and random bits at each tag, and each tag configuring itself to respond to only one of said plurality of frequencies based upon said computation, and then each tag deactivating itself;

c. broadcasting a wake up signal on a frequency indicated by the CURRENT_-- FREQUENCY indicator at the reader, where said wake up signal activates all tags configured to be activated in response to signals on said frequency;

d. identifying all active tags of step c) using signals on only said frequency, with each tag deactivating itself after successful identification, the reader station incrementing its CURRENT_-- FREQUENCY indicator at the end of the identification of all latter active tags; and

e. repeating steps c) and d) for each frequency indicated by the CURRENT_-- FREQUENCY indicator until the current frequency indicator is set to frequency c+1.

8. In a tag identification system having only a single two-way communications channel between a reader and a plurality of tags in the range of the reader, where the identification of the tags is not initially known to the reader, where the reader can send signals on a plurality of frequencies indexed as 1, 2, . . . , c, where tags have the capability of being activated only in response to a signal on a predetermined one of the plurality of frequencies with the tags remaining deactivated in the presence of signals from the reader station on frequencies other than the predetermined one frequency, each active tag further having the capability of selecting the frequency on which it will next be activated, and where each tag can deactivate itself, a method of identifying all of the tags in the range of the reader, the method comprising:

a. means for broadcasting a first signal and a first query message, the first signal being used to activate all of the tags, and setting a CURRENT_-- FREQUENCY indicator in the reader to frequency 1;

b. means for each of the tags to perform a corresponding computation based upon the first query message and random bits at each tag, and each tag configuring itself to respond to only one of said plurality of frequencies based upon said computation, and then each tag deactivating itself;

c. means for broadcasting a wake up signal on a frequency indicated by the CURRENT_-- FREQUENCY indicator at the reader, where said wake up signal activates all tags configured to be activated in response to signals on said frequency;

d. means for identifying all active tags of step c) using signals on only said frequency, with each tag deactivating itself after successful identification, the reader station incrementing its CURRENT_-- FREQUENCY indicator at the end of the identification of all latter active tags; and

e. means for repeating steps c) and d) for each frequency indicated by the CURRENT_-- FREQUENCY indicator until the current frequency indicator is set to frequency c+1.