Source: http://www.google.com/patents/US20060065731?dq=5,241,671
Timestamp: 2014-07-12 11:49:57
Document Index: 569648396

Matched Legal Cases: ['art 500', 'art 500', 'art 900', 'art 900', 'art 900', 'art 1000', 'art 1000', 'art 1000']

Patent US20060065731 - Methods and systems for the negotiation of a population of RFID tags with ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsMethods and systems for the negotiation of a population of RFID tags with improved security is provided. In one aspect, tags are singulated without using information that directly identifies the tags in the tag population. A key is generated to identify each RFID tag of the population of RFID tags. The...http://www.google.com/patents/US20060065731?utm_source=gb-gplus-sharePatent US20060065731 - Methods and systems for the negotiation of a population of RFID tags with improved securityAdvanced Patent SearchPublication numberUS20060065731 A1Publication typeApplicationApplication numberUS 11/270,778Publication dateMar 30, 2006Filing dateNov 10, 2005Priority dateOct 25, 2002Also published asCA2508861A1, CN1726500A, CN100354874C, EP1559056A2, EP1559056A4, US7195173, US7497384, US20040134984, WO2004038644A2, WO2004038644A3Publication number11270778, 270778, US 2006/0065731 A1, US 2006/065731 A1, US 20060065731 A1, US 20060065731A1, US 2006065731 A1, US 2006065731A1, US-A1-20060065731, US-A1-2006065731, US2006/0065731A1, US2006/065731A1, US20060065731 A1, US20060065731A1, US2006065731 A1, US2006065731A1InventorsKevin Powell, Wayne Shanks, William BandyOriginal AssigneeSymbol Technologies, Inc.Export CitationBiBTeX, EndNote, RefManReferenced by (9), Classifications (9), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetMethods and systems for the negotiation of a population of RFID tags with improved securityUS 20060065731 A1Abstract Methods and systems for the negotiation of a population of RFID tags with improved security is provided. In one aspect, tags are singulated without using information that directly identifies the tags in the tag population. A key is generated to identify each RFID tag of the population of RFID tags. The generated key does not include bits identifying an item with which the particular RFID tag is associated. An algorithm is operated to identify one or more tags in the population of RFIDs tags using the generated keys. In another aspect, frequency hopping and/or spread spectrum techniques are used to provide improved security while negotiating tags. In another aspect, the reader causes the tags to scroll series of bits back to the reader for each bit sent to the tags to provide improved security. Images(10) Claims(50)
In an embodiment, the binary tree traversal process eliminates tags from communication until only one tag with a unique number is isolated and verified. As described above, each level in the binary tree represents a bit position in the tag identification number. As the reader proceeds through nodes (and levels) in the binary tree, it directs a subset of the population of tags to remain active and a subset of the population of tags to go inactive. The reader may send out a bit or combination of bits in a signal to cause the tags to begin a binary traversal, as described above. The tags then respond with the first bit of their identification number. The reader then determines which branch of the binary tree to follow. For example, the reader may select a �0� bit as the first bit of interest. The reader transmits the �0� bit. Tags that last sent a �0� bit remain active; those that did not will go inactive. This process continues, where the reader selects one of the �0� and �1� branches of the binary tree. Statistically, on each bit exchange, one half of the tag population will go inactive. This process continues until the reader reaches a node in the last level of the binary tree and results in a unique tag isolation and elimination. This process can be repeated until each tag in the population of tags is isolated. For more information concerning binary tree traversal methodology, and, more generally, communication between an RFID reader and a population of RFID tags in accordance with an embodiment of the present invention, see U.S. Pat. No. 6,002,544, entitled �System and Method for Electronic Inventory� which is incorporated herein by reference in its entirety, and the following co-pending U.S. Patent Applications, each of which is incorporated by reference herein in its entirety: application Ser. No. 09/323,206, filed Jun. 1, 1999, entitled �System and Method for Electronic Inventory,� Attorney Docket No. 1689.0010001; 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. Example Embodiments of the Present Invention The present invention provides for secure communications (i.e., negotiations) between readers and tags. According to the present invention, a reader can communicate with tags on an open-air communication channel, while keeping tag data, such as tag identification numbers, secure. According to embodiments of the present invention, binary traversal algorithms, such as described above, can be modified to provide for secure communications between readers and tags. For example, a conventional binary tree traversal algorithm can be modified to provide for the secure negotiations. Embodiments of the present invention for communications between readers and tags with improved security are described in detail in the subsections below. Implied Scroll Embodiments According to an embodiment of the present invention, an �implied scroll� is used to provide for improved security during communications between readers and tags. According to this embodiment, a tag �scrolls� by transmitting multiple response bits during a single response interval provided by the reader, instead of the normal single bit response. The reader transmits a substantially constant output signal during which each participating tag scrolls multiple response bits in series to the reader. The reader monitors the scrolling series of response bits from the tag(s), and determines when to terminate the response of the tag(s). The reader can terminate the response of the tag(s) by ending the substantially constant output signal. After ending the response of the tag(s), the reader can transmit one or more subsequent substantially constant output signals to cause further bit scrolling, and/or can commence the interchange of single bits with the tag(s) through a binary traversal operation. In an embodiment, tags can �scroll� or transmit serial streams of bits to the reader in response to an explicit command received from the reader, such as a command bit string. In an alternative embodiment, tags can be caused to scroll bits to the reader by an implied command of the reader. For example, in an embodiment, after the tag transmits a first response bit, the tag waits for a next bit (i.e., a forward link symbol) from the reader. If the tag continues to receive substantially constant/continuous power from the reader for longer than a specific interval, the tag can recognize this as an implicit command to modulate its next response bit back to the reader. The tag can continue to modulate further response bits back to the reader as long as the tag keeps receiving the continuous power signal from the reader. In this manner, a tag can scroll multiple bits to a reader without further intervention from the reader. Scrolling can be used to enhance security in various ways. For example, scrolling allows for multiple bits to be transmitted from a tag to the reader for every reader transmitted bit. Because tag bits are transmitted at a lower power, these bits are harder for unwanted third parties to detect. Because fewer reader bits are transmitted during scrolls, there are fewer higher powered bits transmitted that are easier to detect. FIG. 5 shows a flowchart 500 providing example steps for a reader to communicate with a population of RFID tags with improved security, using bit scrolling, according to an example embodiment of the present invention. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion. The steps of FIG. 5 are described in detail below, with reference to FIG. 6. FIG. 6 shows a signal diagram 600 representing an example communication between a reader and tag, according to an example embodiment of the present invention. Flowchart 500 begins with step 502. In step 502, a first bit is transmitted to the population of tags. For example, the first bit can be transmitted by the reader to begin a binary traversal, or can be any bit within a binary traversal tree. For example, FIG. 6 shows an example first reader bit 602 transmitted by a reader. In the example of FIG. 6, first reader bit 602 is represented by a low signal transmitted by the reader for specific period of time. For illustrative purposes, the signal shown transmitted by the reader in FIG. 6 is shown in logical form, without a carrier frequency, etc. In step 504, a substantially constant signal is transmitted to the population of tags. For example, as shown in FIG. 6, a substantially constant RF output is provided by the reader, shown as substantially constant signal portion 604. In step 506, a plurality of bits are received from a first tag during transmission of the substantially constant signal. For example, as shown in FIG. 6, a first tag response is shown as first tag response 606 a (shown in FIG. 6 as modulating substantially constant signal portion 604 with three cycles of a response backscatter frequency). For instance, first tag response 606 a is a normal response of a tag during a binary traversal after receiving a reader bit, first reader bit 602. As shown in FIG. 6, the tag waits a specific time interval 608 a from responding with first tag response 606 a (or from any other reference point). After specific time interval 608 a expires, the tag responds (i.e., scrolls) with a next bit, second tag response 606 b. The tag makes this response due to the implied command from the reader, which merely maintains substantially constant signal portion 604. In a likewise manner, after expiration of a second specific time interval 608 b, the tag responds (i.e., scrolls) with still another bit, third tag response 606 c. Once again, the tag makes this response due to the implied command from the reader, which merely maintains substantially constant signal portion 604. In step 508, transmission of the substantially constant signal to the population of tags is terminated to end transmission of the plurality of bits from the first tag. For example, as shown in FIG. 6, substantially constant signal portion 604 is terminated at point 610. Thus, since another specific time interval 608 did not expire between third tag response 606 and point 610, the tag understands this as the implied command to stop scrolling out response bits. After point 610, the reader can transmit a next reader bit 602 to direct the population of tags down another branch of the binary tree, issue a command, or do any other reader function. In an embodiment, the length of an interval 608 that a tag waits before modulating a next response bit back to the reader can be set in various ways. For example, the length of the interval 608 can be preprogrammed into the tag. Alternatively, an interval 608 can be defined in a training/synchronization sequence transmitted from the reader to the tag during operation. Such an implied scroll procedure can be useful to enhance binary traversals of tag populations. For example, a length of time required to perform a binary traversal can be reduced. For instance, in an embodiment, during a binary traversal, a reader can transmit bits at nodes in a binary tree where the reader knows that both the �0� and �1� branches of the tree from the node are populated with tags. At other nodes, the reader can allow the tag(s) to scroll bits. If the reader receives both �0� and �1� responses simultaneously from tags, then the reader can terminate the scroll by transmitting a bit that directs which branch the binary traversal at this binary tree �fork� will take. Because binary trees are frequently sparsely populated, an ID number having a large number of bits (e.g., such as 80 bits) can be isolated by the reader only having to transmit much fewer bits (e.g., 3 or 4 bits) to resolve bit collisions/forks in the binary tree, and scrolling through the remaining nodes of the binary tree. Note that in an embodiment, a reader may have a limit on how many bits it will allow to scroll continuously before terminating the current bit scroll. For example, the number of scroll bits may be limited in order to keep the reader and tags synchronized. In another example, the number of scroll bits may be limited so tags do not confuse the continuous signal from the reader with other signals that can be sent by a reader, such as a master reset signal, etc. Thus, for example, scrolls may not be allowed to proceed through more than 10 or 12 bits at a time. For an example 80 bit ID number, scrolling 10 bits at a time will still only require that around 12 percent of the ID number be broadcast from the reader, thus speeding up a binary traversal operation (where all 80 bits are broadcast). Furthermore, in this manner, the tag ID numbers are kept more secret from an undesired third party. Frequency Hopping and Spread Spectrum Embodiments As described above, it is possible for an unwanted third party to fool or �spoof� a reader into revealing complete tag ID numbers. The unwanted third party can transmit a false tag response to cause bit collisions and thus force the reader to transmit bits to resolve the collision. The unwanted third party receives the bits from the reader, and sends out false response signals multiple times to piece together one or more ID numbers of the tag population. Given enough time, the unwanted third party could potentially �spoof out� the entire tag population binary tree. Readers that transmit at ultra high frequencies (UHF) can use a frequency hopping spread spectrum approach to mitigate multi path nulls and interference from other readers. Thus, an unwanted third party attempting to spoof a RFID system will have to follow along with the reader frequency hops. If the reader uses a pseudo-random hop sequence, it may be relatively easy for the unwanted third party to follow the reader frequency hops. If the reader uses a true random frequency hop sequence, it is difficult, if not impossible for the unwanted third party to follow the frequency hops. If there are many readers operating simultaneously to negotiate populations of tags, then any one channel, or any sequence of channels that the unwanted third party may select, will contain a random interleaving of incomplete tree data. Thus, the unwanted third party will be unable to extract meaningful information in a reasonable amount of time. For RFID systems that desire improved security but use only one or a few readers, the random frequency hop technique will not be as robust. In an embodiment, to provide an improved system, a reader can transmit a direct sequence spread spectrum signal. In a preferred embodiment, the direct spreading sequence is random. Similarly to the tags, an unwanted third party could listen in on the reader transmission (i.e., the forward link) with a wide band receiver. To spoof a tag, the exact spreading sequence must be known by the unwanted third party before the transmission of the reader is received. The unwanted third party will most likely be receiving and transmitting at a relatively great distance. Thus, even if the unwanted third party can receive the reader transmissions and quickly transmit a modulated replica, the phase shift caused by the propagation delay will likely prevent the reader from despreading the unwanted third party's spoofing signal properly. As a result, the spoofing signal will be spread over a wider band than a true tag response, and will be ignored. In embodiments, depending on the particular situation, random frequency hopping, random direct sequence spread spectrum, or a hybrid approach can be used to provide robust data protection. Binary Traversal Embodiments without Application Data In another embodiment of the present invention, a binary tree traversal provides for improved security. According to the present embodiment, a binary number of a tag, other than the tag identification number, is used for negotiating a binary traversal. Furthermore, this binary number, or �second key,� contains no application data. In other words, the binary number returned to the reader by the tag does not contain information that can be correlated with, or can be used to identify the object to which the tag is associated. By not transmitting application data to the reader, a tag singulation (i.e., isolation of a single tag) by the reader can occur with security maintained over any information about the item to which the tag is attached. In embodiments, several types of binary numbers can be used in tags to provide varying degrees of security, with different performance tradeoffs. Typically, tag ID numbers (i.e., the first key) that are to be negotiated in a binary traversal are required to be unique for all possible tagged items over a period of time. This can entail a lengthy bit sequence to cover uniqueness for large numbers of items, including even trillions of items worldwide. Negotiating such a large number of bits required for tag uniqueness can take a relatively long period of time. Typically, however, a particular reader is not capable of powering and/or reading more than a particular number of passive tags. The number of tags that can be powered by a particular reader depends on a tag broadcast power, a distance from the reader to the tags, and other factors. In an example situation, a reader can power about 2000 passive tags, which can be covered by an 11 bit binary string (i.e., 2048 unique values). Hence, in such a situation, it would not be efficient to attempt to always read a complete ID number, such as a 112 bit identification number, for example (e.g., 96 bits ePC plus 16 bits CRC) every time. Statistically, in the present example, there is only a need for 11 bits to accommodate tag uniqueness within the reader field. In embodiments, however, further bits than the minimum may be used for various reasons, such as for error correction, etc. According to the present invention, a reader singulates a tag using the bit pattern of a second key. Subsequently, the tag can transmit to the reader its relatively lengthy identification number or item key (e.g., ePC or similar) (i.e., first key), which often contains information about the item the tag is attached to. However, this transmission only has to be done once, as the two keys can be associated in the reader or the host system for future identification. Thus, in such an embodiment, the second key is shorter than the first key. Note, however, in alternative embodiments, as described below, the second key can be the same length as or longer than the first key. FIG. 7 shows an example tag 700 that includes a second storage element 702 for storing the bit pattern of the second key, according to an embodiment of the present invention. The second key can include a single bit pattern, or plurality of combined bit patterns. According to an example embodiment of the present invention, encoding of the second key is broken up into several portions or sections. Each section provides additional uniqueness. For example, a first portion is used as a minimum level of statistical uniqueness in the expected population of tags. For instance, in an expected population of 1024 tags, 10 bits for a first portion is an absolute minimum. Furthermore, additional bits can be added for probability and error detection schemes. Hence, for an example population of 1024 tags, 16-24 bits may be used in the first portion. In many cases, a broadcast of this many bits in such a tag population would result in isolation of a single tag. If it is determined that transmission of this many bits does not isolate a tag, then a second portion of the second key can be negotiated, and so on until isolation of a tag is obtained. In further example embodiments, the second key can be implemented as follows: (A) A simple sequence number: A first tag is assigned a binary number 1 as the second key, a second tag is assigned a binary number 2 as the second key, and so on. These numbers could be assigned when the tags are manufactured, or at any time later. Such a number could be stored in storage 702, such as shown in FIG. 7, for example. However, second keys assigned in the manner may yield information about the tags if detected by an unwanted third party. This is because a range of numbers assigned to a particular population of tags may be known (e.g., by the unwanted third party) to have been produced in a certain date range, or sold for a specific purpose. Thus, knowing such information about the tags, and having determined the numbers assigned to the tags by eavesdropping, an unwanted third party may be able to deduce information about the objects to which the tags are associated. Thus, although this is a relatively simple solution, some information about the items to which the tags are attached may be undesirably gained through eavesdropping measures. (B) Randomly generated static numbers: A random, fixed number may be stored in a tag as the second key. Such a number could be stored in storage 702, such as shown in FIG. 7, for example. The use of such a randomly generated static number avoids the type of eavesdropping described in (A) above. However, an overall number of tagged items in the locality may be obtained by an eavesdropping third party. For example, the unwanted third party could eavesdrop, and record all of the random, fixed numbers assigned to the tags in the local population that are broadcast. The unwanted third party could then compare the recorded values with previous entries obtained by the eavesdropper to determine an estimate, or exact count, of the number of tagged objects present. Thus, this solution is better at keeping the identity of items secure, while possibly allowing an unwanted third party to determine the number of items present. Note that the second key can be assigned to be a fixed pseudo-random number. Preferably, the second key is assigned a bit pattern that is non-correlated with the bit pattern of the first key. For example, the second key can be assigned a bit pattern that includes bits corresponding to a location on the wafer in which the integrated circuit chip of the RFID tag was formed. For example, the bit pattern could include bits indicating an X-Y location of the chip on the wafer, or a number of the chip in the wafer. The bit pattern could further include a unique number corresponding to the particular wafer from the chip was removed, to further correlate the second key with the wafer. In another example, the bit pattern of the second key can include bits corresponding to a time stamp, such as a time that the tag was manufactured, a time that the chip was produced, or other relevant time stamp. In another example, the bit pattern of the second key could include a portion of the bit pattern of the first key. For example, the second key could include bits of the identification number of the tag. In another example, the bit pattern of the second key could include cyclic redundancy check (CRC) processed bits related to the tag, and/or bits processed according to any other error checking algorithm. In another example, bits of the second key could be hashed according to a hashing code. In further embodiments, any combination of these bit patterns can be used in the second key, along with any other bit pattern(s), as desired. (C) Dynamically generated numbers: The use of dynamically generated numbers for each tag is relatively even more secure against eavesdropping and spoofing. In this embodiment, the second key can be changed each time the population of tags is negotiated or addressed in a binary traversal operation. Because of this, an outside eavesdropping system could not tell whether a new second key transmitted by a tag applies to a new item, or to an existing item that is being read again with a new second key. Thus, in this embodiment, the number of items present cannot be readily determined, as in the embodiment of (B) described above. FIG. 8 shows an example tag 800 that includes a random number generator or random bit pattern generator 802, according to an example embodiment of the present invention. In an embodiment, random bit pattern generator 802 can generate a random number or bit pattern for the second key having a known fixed length, or alternatively, can generate a random number of any length, as dictated by the reader. Thus, in some embodiments, tags can have a flexible bit length second key, as determined by the reader. In this manner, the reader can cause the tag to respond with any numbers of bits, including bits the 1s, 10s, 100s, 1000s, and any other length ranges, until the reader decides to request no further bits. Furthermore, in an embodiment, the second key generated by random bit pattern generator 802 can be stored in a second storage element 804, when present. Alternatively, in an embodiment, the second key is not stored, and is transmitted by the tag bit-by-bit as it is generated by random bit pattern generator 802. Thus, in such an embodiment, second storage element 804 is not present. Such an embodiment is useful when a tag transmits a different second key each time it is negotiated, and/or transmits a second key with variable length. Any type of random bit pattern generator can be used for random bit pattern generator 802, including an oscillator, a combination of logic gates, or other type of random bit pattern generator known to persons skilled in the relevant art(s). A tradeoff with using a dynamically generated number is that in order for the reader to know what item a tag is attached to, after reading the second key, the first key of the tag must be read. However, because the tag was already isolated using the secure second key, the reader can transmit a command to the tag to transmit the first key (e.g., identification number) to the reader, rather than the reader transmitting the first key to the tag, as during a normal binary traversal. Thus, only the response of the tag, such as a backscatter type response, will contain the first key. The approach of (C) above solves several problems. For example, when negotiating using a bit to bit approach, such as in a binary tree traversal, information in the first key is essentially broadcast on the reader transmit channel (i.e., forward link), which is a relatively high powered channel (i.e., high power is required to activate the passive tag). Such a signal may be easily eavesdropped upon from a fairly long distance (hundreds of feet). After repeated scans of a tag population by readers, random noise, or inserted noise (spoofing), can eventually cause all or a significant portion of the first keys of the tags to be transmitted on the forward link. However, in an embodiment, the present invention provides that the first key is not transmitted by the reader in the forward link. Instead, the second key, which can be much shorter than the first key, and can be devoid of item related information (i.e., is non-correlated to the attached object), is transmitted by the reader in the forward link. If desired, the reader can then have the singulated tag transmit its first key in the �backward� link (i.e., tag to reader). Because the responses of a tag are much lower power than transmissions of a reader, the responses are much more difficult for an unwanted third party to eavesdrop in on. Thus, even though the tag transmits the first key to the reader, this backward link transmission is much more difficult to detect, allowing for improved security over having the reader transmit the first key in the forward link. Another problem solved by the present invention is related to the number of bits required to be communicated between readers and tags. According to the present invention, the number of bits negotiated between tag and reader (i.e., the second key) can be substantially less than the item identification number (i.e., first key). Once the reader has obtained the first key from the tag, the reader can address the tag using the second, shorter, key, until a new second key is generated by the tag. In embodiments, the reader can send a command to the tag to respond with a new second key. Alternatively, the tag can always respond with a newly generated second key, or can respond with a newly generated second key after every N interrogations, where N is greater than or equal to 1. By addressing a tag with a second key that is shorter than the first key, communications can occur much faster. As described above, typically a tag only needs to be unique within the field of a reader, so really only needs a key much shorter than the first key. The first key can provide uniqueness worldwide and can be over 100 bits. Uniqueness in the field of the reader likely requires fewer bits. By resolving tag reads based on minimal number of bits according to the present invention, the speed of performance is increased on tags that need continued monitoring, such as in an automated inventory system. Higher system performance can result in faster overall inventory scans, which can detect inventory changes faster. Item level information that is of security concern (i.e., first key information) is not transmitted as part of the tag negotiation process of the present invention because a non-correlated second key is instead used. Thus, advantages of the present invention include providing the capability to read item identification numbers securely, from a reader transmit/broadcast perspective. Additionally, in static applications (such as inventory), much better efficiency can be obtained using the shorter second key, while keeping item identification numbers (i.e., first keys) private from competitors or other unwanted third parties. FIG. 9A shows a flowchart 900 providing example steps for a tag to communicate with a RFID reader with improved security, according to an example embodiment of the present invention. In the example of flowchart 900, the example tag stores an identification number (i.e., a first key) which is defined by a first bit pattern. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion. The steps of FIG. 9A are described in detail below. Flowchart 900 begins with step 902. In step 902, a first at least one bit is received from the reader. The first at least one bit causes the tag to respond to a binary traversal operation with a second bit pattern. The first at least one bit can be any bit or combination of bits to cause tags to respond with the second key. This can amount to a state transition by the tag, or other tag algorithm change. In step 904, a binary traversal operation is engaged with the reader, wherein the tag responds during the binary traversal operation with the second bit pattern. Thus, as described above, the tag communicates with the reader, responding to the reader with bits of the second key. The tag can be singulated in this manner. Steps 906, 908, 910, and 912 are optional, according to further example embodiments of the present invention. In step 906, at least one bit is received from the reader to cause the first tag to transmit its identification number. For example, as described above, once the tag is singulated, the reader may desire to read the identification number, first key, of the tag, in order to identify the object to which the tag is attached. Thus, the reader can use any mechanism to cause the tag to respond with bits of the first key. In step 908, the identification number is transmitted. In step 910, a command is received from the reader. For example, as described above, once the tag is singulated, the reader may desire to command the tag to execute any operation that the tag is capable of, such any command/operation as described elsewhere herein, or otherwise known. In step 912, the command is executed. FIG. 9B shows example steps for step 904. As shown in the embodiment of FIG. 9B, step 904 can include steps 914 and 916. In step 914, a series of bits is received from the reader. For example, as described above, the reader transmits bits to the tag. In step 916, each bit of the series of bits is responded to with a corresponding bit of the second bit pattern. For example, the tag compares each received bit with the previous transmitted bit of the tag's second key (or in alternative embodiments, compares each received bit with the next bit of the tag's second key). If they match, the tag transmits the next bit of the second key. In an embodiment, step 904 can include the step where the next bit of the second bit pattern is read from storage in the tag. For example, the storage can be second storage element 702 or 804, which stores the second key. In another embodiment, step 904 can include the step where the next bit of the second bit pattern is randomly generated. For example, the bit values can be generated by a random bit pattern generator, such as random bit pattern generator 802 shown in FIG. 8. The generated bit values can be stored in storage 804, or alternatively, are not stored, but are immediately transmitted by the tag to the reader in response to the binary traversal operation. Thus, in a subsequent binary traversal operation, the tag would newly generate each bit of the second bit pattern. FIG. 10A shows a flowchart 1000 providing example steps for a reader to communicate with a population of RFID tags with improved security, according to an example embodiment of the present invention. In the example of flowchart 1000, each tag of the population of tags stores a corresponding identification number (i.e., a first key) which is defined by a first bit pattern. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion. The steps of FIG. 10A are described in detail below. Flowchart 1000 begins with step 1002. In step 1002, a first at least one bit is transmitted to the population of tags to cause tags to respond to a binary traversal operation with a second bit pattern. The first at least one bit can be any bit or combination of bits to cause tags to respond with the second key. In step 1004, a binary traversal operation is performed to singulate a first tag of the population of tags. Steps 1006, 1008, and 1010 are optional, according to further example embodiments of the present invention. In step 1006, the first tag is caused to transmit its identification number. In step 1008, the identification number of the first tag is received. In step 1010, a command is transmitted for execution by the first tag. FIG. 10B shows example steps for step 904, according to an example embodiment of the present invention. As shown in the embodiment of FIG. 10B, step 1004 can include steps 1012 and 1014. In step 1012, a series of bits is transmitted to the population of tags. In step 1014, a corresponding bit of the second bit pattern is received from the first tag in response to each bit of the series of bits. Note that many tags of the population of tags may be responding to bits of the series of bits transmitted by the reader. However, eventually, only a single tag will respond, becoming the singulated tag. In an embodiment, in step 1010, the reader transmits a predetermined number of bits. For example, the number of bits may be predetermined to be sufficient to identify tags within a communication range of the reader. For example, as described above, to negotiate 1024 tags, 10 bits are required for uniqueness. Thus, the reader may transmit 10 or more bits in the series of bits. Note that in embodiments, however, there is no limit on the number of bits a reader may transmit in the series of bits, including in the 1s, 10s, 100s, and 1000s of bits, to singulate a tag. For example, in the example where the tag population includes 1024 tags, 16 bits may be chosen as the length of the second key for the tags. Thus, in this example, the reader could transmit 16 bits to likely singulate a tag. However, in this example, the reader could transmit fewer than 16 bits if it is predetermined that fewer than 16 bits will identify a single tag within communication range. Alternatively, the reader may desire to transmit bits additional to 16 bits to singulate a tag, in embodiments where tags are configured to have flexible bit lengths for the second key. Further Embodiments The systems and methods described above for improved security during RFID negotiations can be combined in any manner, as desired for a particular application. For example, in an embodiment, a reader may negotiate a population of tags. The tags may be instructed by the reader to respond with a second bit pattern during the negotiation that is not correlated with their identification number (e.g., their EPC number). The reader may negotiate the population of tags using a binary traversal. Once the reader singulates a tag, the reader can use the implied scroll function to cause the tag to send its identification number to the reader. Thus, this embodiment provides enhanced security because a non-correlated number is negotiated, and because the tag identification number is sent to the reader on the �backward� link, which is lower power. Furthermore, such a singulation of a tag, and receipt of the tag's identification number can occur very rapidly. Because during the implied scroll, a reader does not transmit edges, and therefore the tag does not have to wait for edges, the identification number of the tag can be scrolled to the reader very rapidly. For instance, in an example embodiment, the tag can transmit its identification number (or other information) during an implied scroll three times faster than communications can occur during a binary traversal. Further combinations of the embodiments described herein are also within the scope and spirit of the present invention, as would be understood by persons skilled in the relevant art(s) from the teachings herein. CONCLUSION While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. It will be apparent to persons skilled in the relevant art that various changes in form and detail can be made therein without departing from the spirit and scope of the invention. Thus, the breadth and scope of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents. Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7826938 *Dec 22, 2005Nov 2, 2010Mitsubishi Electric Research Laboratories, Inc.System for tracking railcars in a railroad environmentUS8113435Jun 11, 2009Feb 14, 2012Cubic CorporationCard readerUS8315391 *Apr 27, 2007Nov 20, 2012Fujitsu LimitedInformation access system, reader/writer device and contactless information storage deviceUS8350668Jul 15, 2009Jan 8, 2013Cubic CorporationSmartcard protocol transmitterUS8581706 *Jun 12, 2007Nov 12, 2013Giesecke & Devrient GmbhData storage medium and method for contactless communication between the data storage medium and a readerUS8680970Feb 1, 2013Mar 25, 2014Mojix, Inc.RFID systems using distributed exciter networkUS20090199206 *Jun 12, 2007Aug 6, 2009Klaus FinkenzellerData storage medium and method for contactless communication between the data storage medium and a readerUS20120127976 *Nov 23, 2010May 24, 2012Symbol Technologies, Inc.Radio frequency identification system and related operating methodsWO2008118875A1 *Mar 24, 2008Oct 2, 2008Mojix IncRfid systems using distributed exciter network* Cited by examinerClassifications U.S. Classification235/451, 235/492International ClassificationG06K19/06, G06K7/00, G06K7/08Cooperative ClassificationG06K7/0008, G06K7/10049European ClassificationG06K7/10A1A1A, G06K7/00ELegal EventsDateCodeEventDescriptionApr 23, 2013FPExpired due to failure to pay maintenance feeEffective date: 20130303Mar 3, 2013LAPSLapse for failure to pay maintenance feesOct 15, 2012REMIMaintenance fee reminder mailedAug 24, 2010CCCertificate of correctionNov 10, 2005ASAssignmentOwner name: MATRICS, INC., MARYLANDFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:POWELL, KEVIN J.;SHANKS, WAYNE E.;BANDY, WILLIAM R.;REEL/FRAME:017221/0743;SIGNING DATES FROM 20040316 TO 20040402Owner name: SYMBOL TECHNOLOGIES, INC., NEW YORKFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:MATRICS, INC.;REEL/FRAME:017221/0752Effective date: 20041221RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google