Source: http://www.google.com/patents/US20040135674?dq=6721967
Timestamp: 2017-12-12 12:36:38
Document Index: 168219285

Matched Legal Cases: ['Application No. 60', 'art 400', 'art 400', 'art 400', 'art 530', 'art 530', 'art 530', 'art 530', 'art 700', 'art 700', 'art 700']

Patent US20040135674 - Method for the efficient reading of a population of radio frequency ... - Google Patents
A method for reading and tracking radio frequency identification (RFID) tags in the presence of a noisy air channel is provided. In accordance with the method, a binary tree data structure is used to characterize a plurality of RFID tags, each of which is associated with a unique identification (ID)...http://www.google.com/patents/US20040135674?utm_source=gb-gplus-sharePatent US20040135674 - Method for the efficient reading of a population of radio frequency identification tags with unique identification numbers over a noisy air channel
Publication number US20040135674 A1
Application number US 10/687,690
Also published as CN1706206A, EP1552710A2, EP1552710A4, US7068148, WO2004036771A2, WO2004036771A3
Publication number 10687690, 687690, US 2004/0135674 A1, US 2004/135674 A1, US 20040135674 A1, US 20040135674A1, US 2004135674 A1, US 2004135674A1, US-A1-20040135674, US-A1-2004135674, US2004/0135674A1, US2004/135674A1, US20040135674 A1, US20040135674A1, US2004135674 A1, US2004135674A1
Inventors Wayne Shanks, Jens Arnold
Original Assignee Wayne Shanks, Jens Arnold
Patent Citations (8), Referenced by (27), Classifications (6), Legal Events (8)
US 20040135674 A1
(a) receiving a series of bits from the plurality of RFID tags and storing said series of bits in corresponding nodes in a binary tree, wherein each node in said binary tree is associated with a counter;
(b) incrementing a counter associated with a node in said binary tree when a bit received from said plurality of RFID tags matches a bit stored in said node;
(c) decrementing a counter associated with a node in said binary tree when a bit received from said plurality of RFID tags does not match a bit stored in said node; and
(d) assigning a value to a bit received from said plurality of RFID tags based on a value of a counter associated with a node in said binary tree.
if it is determined in step (l) that the tag bit pattern is complete, determining whether the stored bit pattern contains a valid tag identification number.
16. The method of claim 2 wherein the first logical value is a data “0” and the second logical value is a data “1.”
17. A method in a radio frequency identification (RFID) reader for interrogating a population of tags using binary tree traversal protocol, comprising the steps of:
(d) if it is determined in step (c) that at least one symbol has been received, adjusting information stored for the logical node;
18. The method of claim 17 wherein step (d) comprises the steps of:
if it is determined in step (c) that at least one symbol has been received, determining whether one symbol received from the population of tags corresponds to a first logical value;
if it is determined in step that one symbol received corresponds to a first logical value, incrementing a node counter value associated with the first logical value;
if it is determined in step that one symbol received does not correspond to a first logical value, decrementing the node counter value associated with the first logical value;
if it is determined in step (c) that at least one symbol has been received, determining whether one symbol received from the population of tags corresponds to a second logical value;
if it is determined in step that one symbol received corresponds to a second logical value, incrementing a node counter value associated with the second logical value; and
if it is determined in step that one symbol received does not correspond to a first logical value, decrementing the node counter value associated with the second logical value.
19. The method of claim 18 wherein step (d) further comprises the step of:
20. A method in a radio frequency identification (RFID) reader for interrogating a population of tags using a binary tree traversal protocol, comprising the steps of:
21. The method of claim 14 wherein the error detection code value is a cyclic redundancy code value.
22. A method in a radio frequency identification (RFID) reader for interrogating a population of tags using binary tree traversal protocol, comprising the steps of:
storing data related to the tag population, wherein the tag population data includes information associated with each populated node in a binary tree;
23. The method of claim 22 wherein the information associated with each populated node in the binary tree includes node weighting information, wherein the storing step comprises
(1) storing the node weighting information for each populated node.
24. The method of claim 23 wherein the node weighting information includes:
a first stored counter value associated with a first logical bit value; and
a second stored counter value associated with a second logical bit value;
wherein step (1) comprises storing the first stored counter value and the second stored counter value for each populated node.
obtaining at least some of the tag population data from external to the reader.
26. The method of claim 25 wherein the at least some of the tag population data is obtained from a second reader.
27. The method of claim 26 wherein the at least some of the tag population data is obtained from a database.
This application claims priority to U.S. Provisional Application No. 60/419,091, entitled “Method for the Efficient Reading of a Population of Radio Frequency Identification Tags with Unique Identification Numbers Over a Noisy Air Channel,” filed Oct. 18, 2002, which is hereby incorporated by reference in its entirety.
The present invention is directed to a system and method for the efficient reading of a population of radio frequency identification (RFID) tags with unique identification numbers over a noisy channel. In accordance with aspects of the present invention, the RFID system includes one or more readers, each reader having a processing module and a memory. The memory stores a set of information about each node in a binary tree data structure (binary tree). The set of information includes an activity register, a “0” bit counter, and a “1” bit counter. Other characteristics of the node, such as path length at the node, may also be stored.
In a further aspect, the processing module includes logic. The logic permits an RFID reader to efficiently read a binary tree characterizing a collection of RFID tags having unique identification numbers within communication range of the reader. In an aspect of the present invention, when the reader receives one or more response signals from a population of tags, the reader adjusts the information stored for the current node being traversed. If only a “0” was received, the reader increments the activity register value, increments the “0” counter, and decrements the “1” counter. If only a “1” was received, the reader increments the activity register value, increments the “1” counter, and decrements the “0” counter. If both were received, the reader increments both counters and the activity register. In addition, the reader also evaluates the stored node information to determine which branch in the binary tree to traverse to optimize the efficiency of the read cycle.
[0014]FIG. 1 is a block diagram of an environment where one or more tag readers communicate with one or more tags, according to an embodiment of the present invention.
[0015]FIG. 2A is a block diagram illustrating an architectural overview of communication between one ore more readers and one or more tags, according to an embodiment of the present invention.
[0016]FIG. 2B is a block diagram of an illustrative reader according to an embodiment of the present invention.
[0017]FIG. 3 is a diagram of an exemplary binary tree having information associated with each node in accordance according to embodiments of the present invention.
[0018]FIG. 4 is a flowchart of a read interrogation operation using traversal path weighting from the perspective of the reader, according to embodiments of the present invention.
[0019]FIG. 5A is a flowchart illustrating a method for determining the next reader bit in accordance with embodiments of the present invention.
[0020]FIG. 5B is a flowchart illustrating an alternative method for determining the next reader bit in accordance with embodiments of the present invention.
[0021]FIG. 6 is a diagram of an exemplary tag having bit positions corrupted by noise.
[0022]FIG. 7 is a flowchart depicting a method of using error detection code processing to identify a tag according to an embodiments of the present invention.
[0023]FIG. 8 is a flowchart depicting a method of using multiple error detection code processes to identify a tag according to an illustrative embodiment of the present invention.
Before describing the present invention in detail, it is helpful to describe an example environment in which the invention may be implemented. The present invention is particularly useful in radio frequency identification (RFID) applications operating in noisy environments. FIG. 1 illustrates an environment 100 where one or more RFID tag readers 104 communicate with an exemplary population of RFID tags 120, according to the present invention. As shown in FIG. 1, the population of tags 120 includes seven tags 102 a-102 g. According to embodiments of the present invention, a population of tags 120 may include any number of tags 102. In some embodiments, a very large number of tags 102 may be included in a population of tags 120, including hundreds, thousands, or even more.
[0030]FIG. 2A is a block diagram of an example RFID system 200 providing communications between one or more readers 104 and tags 102, according to an embodiment of the present invention. RFID system 200 includes a user application domain 250, a network of readers 104 a-n, and one or more tags 102. Note that the invention is applicable to a single reader, as well as to a plurality of readers coupled in a network, as shown in FIG. 2. Hence, although “reader” is often referred to herein, it should be understood that the present invention is applicable to any number of readers in any configuration as required by a particular application.
Each of the readers 104 a-n includes a processing module 240 and a memory 250. FIG. 2B is a block diagram of an illustrative RFID reader 104 according to an embodiment of the present invention. As shown in the example embodiment of FIG. 2B, processing module 240 may include logic 270 to determine a traversal path based on node information stored in memory 250. Logic 270 permits an RFID reader to efficiently read a binary tree characterizing a collection of RFID tags having unique identification numbers within communication range of the reader. Reading all the tags within the tag population during a read cycle results in the repeated passage through bit sequences that are common to multiple tags. Furthermore, a reader generally performs multiple read cycles on a tag population. Therefore, even the unique identification number of a tag is read multiple times. The processing logic of the present invention does not discard information gathered during these repeated passages through the binary tree. Instead, the reader compiles information representing the occupation of each node in the binary tree. Because random noise at a particular node over many samples will average to zero and systematic signals will not, the signal-to-noise ratio for any bit in the binary tree is improved by averaging over many trials. This reader logic can improve the read rate for tags by as much as an order of magnitude at very high bit rates.
Memory 250 stores data associated with tag population 120. In an embodiment, memory 250 is configured to store two registers/counters for every node in the binary traversal tree. A first counter 260 stores the weight of the “1” symbol and a second counter 265 stores the weight of the “0” symbol at the node. In addition, memory 250 is configured to store an activity register 230 for each node in the binary traversal tree.
Furthermore, note that the use of the terminology “counter” is not intended to imply a specific implementation. Each counter can be implemented as a register or in another manner including hardware, software, firmware, or any combination thereof.
[0040]FIG. 3 illustrates a logical representation of an example set of node data stored in memory 250. FIG. 3 shows a binary traversal tree 300 having three levels below the root level, where each level corresponds to a bit position in the tag identification number. Note that three levels are shown for illustrative purposes, and that the present invention is applicable to any size set of node data. The binary tree has 14 nodes 310 a-o. Each node may have an associated “0” counter 265 and “1” counter 260, as described above. Each node may also contain an activity register. In addition, other parameters characterizing the node, such as length of traversal path at that node, may be stored. Two branches extend from each node except the nodes at the lowest level of the tree (nodes 310 h-310 o). For each branch pair, the “0” branch descends towards the left, and the “1” branch descends towards the right.
In an embodiment, the value of the “0” counter 265 at a node is incremented each time the reader receives a “0” symbol while traversing the node. The value of the “0” counter 265 at a node is decremented each time the reader does not receive a “0” symbol while traversing the node. Similarly, the value of the “1” counter 260 at a node is incremented each time the reader receives a “1” symbol while traversing the node. The value of the “1” counter 260 at a node is decremented each time the reader does not receive a “1” symbol while traversing the node. In alternate embodiments, the counters may be incremented or decremented in other ways to track received symbols, as would be understood to persons skilled in the relevant art(s).
tag identification number error detection code
In an embodiment, contention between the tags 102 is avoided by requiring transmissions from each tag 102 to the reader 104 to be unique in a separation of frequency, but can be avoided in other ways. Contention may be defined as communications by multiple transmissions in the same frequency, time, and/or phase that thereby destructively interfere with each other's attempted transmission. Thus, in an example binary traversal algorithm, one bit of information is negotiated at a time between the reader 104 and the current population of tags 102 that the reader is addressing. Each tag response is defined by two frequencies, one frequency for 0, and the other frequency for 1. In such a manner, many tags can simultaneously and non-destructively communicate a data 0. It is not important that the reader cannot differentiate a single data 0 from multiple data 0's, just that there exists a data 0. Alternatively, for example, a tag response may be defined by two time periods, one time period for “0”, and the other for “1.”
For more information concerning binary tree traversal methodology, see the following co-pending U.S. patent applications, each of which is incorporated by reference in its entirety: application Ser. No. 10/072,885, filed Feb. 12, 2002, entitled “Method, System and Apparatus for Binary Traversal of a Tag Population,” Attorney Docket No. 1689.0210001; and application Ser. No. 10/073,000, filed Feb. 12, 2002, entitled “Method, System and Apparatus for Communicating with a RFID Tag Population,” Attorney Docket No. 1689.0260000. For more information concerning communication between an RFID reader and a population of RFID tags, see U.S. Pat. No. 6,002,344, entitled “System and Method for Electronic Inventory” which is incorporated herein by reference in its entirety and application Ser. No. 09/323,206, filed Jun. 1, 1999, entitled “System and Method for Electronic Inventory,” Attorney Docket No. 1689.0010001 which is incorporated herein by reference in its entirety.
[0050]2. Binary Tree Traversal Using Traversal Path Weighting
[0051]FIG. 4 is a flowchart 400 depicting the operation of the present invention according to an example embodiment. The flowchart illustrates the present invention's use of traversal path weighting to increase the efficiency of an interrogation of a population of tags. The present invention works conjointly with the binary tree traversal protocol used by the reader. Examples of binary tree traversal protocols are described above. Flowchart 400 will be described with continued reference to the example environment in FIG. 2, above. However, the invention is not limited to that environment. Note that some steps shown in flowchart 400 do not necessarily have to occur in the order shown.
After a binary tree traversal is started, in step 415, the reader enters a node of the binary tree (e.g., shown in FIG. 3 as one of the nodes 310 a-o). As part of binary traversal protocol, at each node in the binary tree, the reader transmits a signal to initiate a response from the population of tags. In a typical binary tree traversal protocol, the response contains a symbol representing a bit in the identification number of at least one tag.
In step 541, the reader determines whether the current node is a branching node. A branching node is a node at which both a “0” response value and a “1” response value have been received and the reader must decide which branch to traverse. If the node is not a branching node (i.e., only one response value was received), operation proceeds to step 542. If the node is a branching node (i.e., both response values were received), operation proceeds to step 545.
In step 543, the reader determines whether it is probable or likely that one or both of the received signals were caused by noise or some other problem. The reader bases this determination on an evaluation of the node information stored in memory 250. For example, because the reader may pass through a particular node many times during a read cycle, counters 260 and 265 associated with branches in a tag populated path will have high values over time, while unpopulated branches will have counters 260 and 265 with relatively low values over time. Consequently, counters 260 and 265 can be used as a weighting factor during the determination step. For example, if “1” counter 260 is highly positive while “0” counter 265 is highly negative or zero, then reader 104 determines that it is probable that the “0” symbol was caused by noise and therefore selects the positive weighted “1” branch to traverse. The reader may also consider the length of the traversal path (i.e., the number of nodes traversed prior to this node) at the node as a possible indication of a false path.
In step 549, if the reader determines the probability or likelihood is that neither signal was caused by noise in step 543, the reader applies a default preference technique to select a branch to traverse. For example, the reader may have a default preference for the strongest signal. Alternatively, the reader may have a default preference for a particular bit value, such as a bit “0” or a bit “1.”
If the reader determines the probability or likelihood is that both received symbols were likely caused by noise, the reader may elect to terminate traversal of the path and start traversal of another path. Alternatively, the reader could select a branch to traverse (similar to step 544) and control passes to step 452. If both signals were noise, tag response will “drop out” at the next node.
[0062]FIG. 5B depicts a flowchart 530B for determining the next reader bit value, in an alternate embodiment of the present invention for step 430. A reader may use the method of flowchart 530B when a determination is made that the probability that the read process is subject to noise is low or non-existent, for example. Flowchart 530B uses traversal path weighting to isolate and read weak or unread tags. A weak tag may be a tag whose signal is difficult to read.
In step 547, the reader determines whether it is probable or likely that one or both of the received signals were from weak or unread tags. The reader bases this determination on an evaluation of the node information stored in memory 250. For example, if the “1” counter 260 is highly positive while the “0” counter is highly negative or zero, then the reader determines that it is probable that the received “0” signal is from a weak tag and selects the “0” branch to traverse.
In step 549, the reader applies a default preference technique to select a branch to traverse. For example, the reader may have a default preference for the strongest signal. Alternatively, the reader may have a default preference for a particular bit value, such as a bit “0” or a bit “1.”
After completion of flowchart 530A or 530B, operation proceeds to step 452. In step 452, the reader increments the activity register (if either a “0” or a “1” symbol was received in step 420).
In step 453, if a received bit equals 0, operation proceeds to step 454. In step 454, the reader network increments “0” counter 265 for the node and operation proceeds to step 456. In step 453, if a received bit does not equal 0, operation proceeds to step 455. In step 455 the reader network decrements “0” counter 265 and operation proceed to step 456.
In step 456, if a received bit equals 1, operation proceeds to step 457. In step 457, the reader network increments “1” counter 260 for the node and operation proceeds to step 460. In step 456, if a received bit does not equal 1, operation proceeds to step 458. In step 458, the reader network decrements “1” counter 260 for the node and operation proceeds to step 460.
In an embodiment of the present invention, “1” counter 260 and “0” counter 265 can reflect negative values. In an alternate embodiment, “1” counter 260 and “0” counter 265 are held at 0 when a decrementing step would cause the counter to have a negative value. Note that while steps 452-458 depict the reader first checking for a 0 bit then checking for a 1 bit, the reader can perform these steps in the any order or in parallel without departing from the spirit or scope of the present invention. In an alternative embodiment of the present invention, the adjustment of the node information (steps 450-458) can occur before the reader determines which branch to traverse (step 430).
If the reader determines that tag identification bits have been accumulated in step 490, the reader assumes that the reader proceeded down an incorrect path in the binary tree. This “drop out” of tag response due to an incorrect path will most likely occur directly after the node where the first incorrect branch was taken. Therefore, in an embodiment of the present invention, in step 495, the reader decrements the weight of the counter corresponding to the incorrect path at the node immediately preceding the drop out. In alternate embodiments, the reader may decrement counters at additional nodes in the traversal path such as nodes prior to where the incorrect branch was taken. After the counter is adjusted, operation proceeds to step 498.
Another technique for the efficient reading of tags identifies and stores bit sequences that are common among the identification numbers of the tags onto a stack, which are sequentially pulled off the stack and read out. For example, reader 104 may accumulate the first n bits of a tag identification number. While negotiating the next bit position, the reader may receive two symbols from the tag population. The reader will select a branch associated with one symbol to traverse. The reader will then store the bit sequence associated with the other symbol on the stack. This stacking is performed each time a branching node is reached by the reader. Because a bit sequence pulled off the stack is forced out, those bits are less susceptible to bit errors. This technique is complex but is robust to noise. However, this “stack” technique does not optimally utilize all the information gained by an RFID reader during the process of reading a population of RFID tags.
Another technique for efficient reading of tags uses a stored traversal path after a “drop out” of tag responses occurs during a binary tree traversal. In this technique, after the “drop out” of responses, the reader retrieves the stored traversal path accumulated during the binary tree traversal. The reader then communicates each bit of the stored traversal path to the readers during a new “modified” binary tree traversal. While negotiating the bits in the stored traversal path, the reader ignores responses from the tags and proceeds through the stored traversal path. This continues until the reader has traversed the nodes associated with all the bits in the stored path or has traversed the nodes associated with a subset of bits. The reader then resumes standard binary tree traversal for the remaining bits to be accumulated.
In the present invention, the reader can determine which bit or bits have been potentially corrupted by noise. The reader can use this knowledge to correctly identify an individual tag without performing another read process. FIG. 6 illustrates an exemplary tag having a 10-bit identification number 692 and an error detection code value 693. During the read process, the reader has identified two bit positions 695 and 696 that have been potentially corrupted by noise (as indicated in FIG. 6 as having both 0 and 1 values). Thus, the reader can determine that the valid tag has one of four potential 10-bit identification numbers 677 a-d due to the four possible combinations of the two unknown bits. Each of the four potential 10-bit identification numbers 677 a-d has an associated error detection code value 678 a-d. The error detection code values 678 a-d are calculated by the reader 104. The valid tag identification number can then be identified by matching the error detection code value 693 received from the tag as part of the read process to an error detection code value 678 a-d. The identification number 677 a-d associated with the matched error detection code value is indicated by the reader as the valid identification number.
[0088]FIG. 7 illustrates a flowchart 700 for using error detection code processing to identify a tag in the presence of errors introduced during communications between tag 102 and reader 104 according to an embodiment of the present invention. In an embodiment of the present invention, the error detection code processing is cyclic redundancy check (CRC) processing. As will be appreciated by persons skilled in the relevant art(s), flowchart 700 can be used in conjunction with tag population interrogation using traversal path weighting as described herein.
Flowchart 700 begins at step 710 when the reader begins communications with a tag 102 or a population of tags 120. In an embodiment, the communications can include a read process or another process where a tag 102 or multiple tags are not placed in a mute state during tag-reader communications. In step 720, the reader identifies bit positions potentially corrupted by noise. For example, when the reader receives both a “0” and a “1” symbol, the reader may identify the associated bit position as potentially corrupted. The reader may also use other available information such as length of the traversal path at the node or values of bit counters and activity node register to determine whether the bit position was corrupted by noise.
In step 825, the reader determines whether both a “0” symbol and a “1” symbol have been received. If both have been received, the reader assumes that the current bit position has been potentially corrupted by noise. In an alternate embodiment of the invention, the reader may also use additional node information stored in memory to determine whether bit position corrupted. In either embodiment, operation proceeds to step 840 when the reader determines that the bit position is potentially corrupted by noise.
US8319641 * Sep 25, 2007 Nov 27, 2012 Semiconductor Energy Laboratory Co., Ltd. Article management method including shared memory and reader/writers
US20070126554 * Dec 6, 2006 Jun 7, 2007 Choi Sung W Multiple RFID reader system and method for controlling multiple RFID readers in the same
US20080252426 * Jan 6, 2006 Oct 16, 2008 C & S Microwave Co., Ltd. Intelligent Rfid System For Low Powered Reader-Tag Communication and Method Thereof
WO2007037595A1 * Sep 8, 2006 Apr 5, 2007 Sk Telecom Co., Ltd. Method for identifying tags using adafitve binary tree splitting technique in rfid system and rfid system therefor
Cooperative Classification G06K7/10049, G06K7/0008
European Classification G06K7/10A1A1A, G06K7/00E
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SHANKS, WAYNE;ARNOLD, JENS;REEL/FRAME:014444/0437;SIGNING DATES FROM 20040316 TO 20040318
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:MATRICS, INC.;REEL/FRAME:015618/0597