Efficient memoryless protocol for tag identification

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
31Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method of identifying a plurality of tags, said method comprising:
 (a) maintaining a set of query strings;
(b) selecting a string from the set of query strings;
(c) removing the selected string from the set of query strings;
(d) broadcasting to the plurality of tags a query message containing at least a portion of the selected string;
(e) receiving a response from the plurality of tags; and
(f) if the plurality of tags includes any unidentified tags, repeating steps (b) through (f).
1 Assignment
0 Petitions
Accused Products
Abstract
The invention features a method and system for identifying a plurality of tags using an efficient memoryless protocol. The system includes a reader and a plurality of tags. The reader is adapted to maintain an ordered set of query strings; select a string from the set of query strings; broadcast a query message containing the selected string or a portion of the selected string to the tags; and receive a response from one of the tags. The tags operate without batteries and are adapted to respond to the selected string broadcast by the reader. Accordingly, the tag identification methods are efficient in terms of both time and communication complexities.
41 Citations
View as Search Results
Tag anticollision RFID system and method for tag identification  
Patent #
US 8,028,910 B2
Filed 12/14/2005

Current Assignee
SK Telecom Co. Ltd.

Sponsoring Entity
SK Telecom Co. Ltd.

IDENTIFYING RFID CATEGORIES  
Patent #
US 20100295659A1
Filed 05/21/2009

Current Assignee
AlcatelLucent SA

Sponsoring Entity
AlcatelLucent SA

TAG IDENTIFICATION METHOD, TAG ANTICOLLISION METHOD, RFID TAG  
Patent #
US 20100182128A1
Filed 10/16/2008

Current Assignee
Chungang University Industry Academic Cooperation Foundation

Sponsoring Entity
Chungang University Industry Academic Cooperation Foundation

METHOD FOR SIMULTANEOUS DETECTION OF A PLURALITY OF RFID TAGS USING MULTIUSER DETECTION  
Patent #
US 20100039233A1
Filed 08/12/2009

Current Assignee
Collision Communications Inc.

Sponsoring Entity
Collision Communications Inc.

Estimation of the cardinality of a set of wireless devices  
Patent #
US 7,688,180 B2
Filed 09/22/2006

Current Assignee
WSOU Investments LLC

Sponsoring Entity
AlcatelLucent USA Inc.

METHODS AND APPARATUSES TO IDENTIFY DEVICES  
Patent #
US 20100207739A1
Filed 05/03/2010

Current Assignee
RUIZHANG TECHNOLOGY LIMITED COMPANY

Sponsoring Entity
RUIZHANG TECHNOLOGY LIMITED COMPANY

Method for Adaptively Modifying the Observed Collective Behavior of Individual Sensor Nodes Based on Broadcasting of Parameters  
Patent #
US 20100293131A1
Filed 08/05/2010

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Method For Identifying Tags Using Adaptive Binary Tree Splitting Technique In RFID System and RFID System Therefore  
Patent #
US 20090040021A1
Filed 09/08/2006

Current Assignee
SK Telecom Co. Ltd., SK Planet Co. Ltd.

Sponsoring Entity


TRACKING RFID OBJECTS WITH INTEGRATED COMMUNICATION LINK  
Patent #
US 20090315717A1
Filed 06/16/2005

Current Assignee
Koninklijke Philips N.V.

Sponsoring Entity
Koninklijke Philips N.V.

Anonymous tracking using a set of wireless devices  
Patent #
US 20080074238A1
Filed 06/29/2007

Current Assignee
WSOU Investments LLC

Sponsoring Entity
WSOU Investments LLC

Estimation of the cardinality of a set of wireless devices  
Patent #
US 20080079544A1
Filed 09/22/2006

Current Assignee
WSOU Investments LLC

Sponsoring Entity
WSOU Investments LLC

Tag AntiCollision Rfid System and Method for Tag Identification  
Patent #
US 20080283600A1
Filed 12/14/2005

Current Assignee
SK Telecom Co. Ltd.

Sponsoring Entity
SK Telecom Co. Ltd.

METHODS AND APPARATUSES TO IDENTIFY DEVICES  
Patent #
US 20070262851A1
Filed 07/20/2007

Current Assignee
RUIZHANG TECHNOLOGY LIMITED COMPANY

Sponsoring Entity
RUIZHANG TECHNOLOGY LIMITED COMPANY

Methods and apparatus for anticollision for radio frequency communication  
Patent #
US 20070279194A1
Filed 08/10/2007

Current Assignee
RUIZHANG TECHNOLOGY LIMITED COMPANY

Sponsoring Entity
RUIZHANG TECHNOLOGY LIMITED COMPANY

Interactive system using electronic tags  
Patent #
US 20050289247A1
Filed 06/25/2003

Current Assignee
Koninklijke Philips N.V.

Sponsoring Entity
Koninklijke Philips N.V.

Methods and apparatus for anticollision for radio frequency communication  
Patent #
US 8,279,047 B2
Filed 08/10/2007

Current Assignee
RUIZHANG TECHNOLOGY LIMITED COMPANY

Sponsoring Entity
Alien Technology Corporation

Methods and apparatuses to identify devices  
Patent #
US 8,284,034 B2
Filed 07/20/2007

Current Assignee
RUIZHANG TECHNOLOGY LIMITED COMPANY

Sponsoring Entity
Alien Technology Corporation

Anonymous tracking using a set of wireless devices  
Patent #
US 8,299,900 B2
Filed 06/29/2007

Current Assignee
WSOU Investments LLC

Sponsoring Entity
AlcatelLucent SA

Method for identifying tags using adaptive binary tree splitting technique in RFID system and RFID system therefore  
Patent #
US 8,477,016 B2
Filed 09/08/2006

Current Assignee
SK Telecom Co. Ltd., SK Planet Co. Ltd.

Sponsoring Entity
SK Planet Co. Ltd.

Methods and apparatuses to identify devices  
Patent #
US 8,742,899 B2
Filed 12/19/2011

Current Assignee
RUIZHANG TECHNOLOGY LIMITED COMPANY

Sponsoring Entity
Align Technology Incorporated

Methods and apparatuses to identify devices  
Patent #
US 8,768,952 B2
Filed 05/03/2010

Current Assignee
RUIZHANG TECHNOLOGY LIMITED COMPANY

Sponsoring Entity
Align Technology Incorporated

Adaptively modifying the observed collective behavior of individual sensor nodes based on broadcasting of parameters  
Patent #
US 8,898,284 B2
Filed 08/05/2010

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Tracking RFID objects with integrated communication link  
Patent #
US 9,035,772 B2
Filed 06/15/2006

Current Assignee
Koninklijke Philips N.V.

Sponsoring Entity
Koninklijke Philips N.V.

UTILIZATION OF MOTION AND SPATIAL IDENTIFICATION IN RFID SYSTEMS  
Patent #
US 20150186700A1
Filed 03/06/2015

Current Assignee
Intermec IP Corporation

Sponsoring Entity
Intermec IP Corporation

Identifying RFID categories  
Patent #
US 9,081,996 B2
Filed 05/21/2009

Current Assignee
AlcatelLucent SA

Sponsoring Entity
AlcatelLucent SA

Methods and apparatuses to identify devices  
Patent #
US 9,483,671 B2
Filed 06/12/2014

Current Assignee
RUIZHANG TECHNOLOGY LIMITED COMPANY

Sponsoring Entity
RUIZHANG TECHNOLOGY LIMITED COMPANY

Utilization of motion and spatial identification in RFID systems  
Patent #
US 9,704,002 B2
Filed 03/06/2015

Current Assignee
Intermec IP Corporation

Sponsoring Entity
Intermec IP Corporation

Method for simultaneous detection of a plurality of RFID tags using multiuser detection  
Patent #
US 9,769,547 B2
Filed 08/12/2009

Current Assignee
Collision Communications Inc.

Sponsoring Entity
Collision Communications Inc.

Tracking RFID objects with integrated communication link  
Patent #
US 9,801,011 B2
Filed 05/18/2015

Current Assignee
Koninklijke Philips N.V.

Sponsoring Entity
Koninklijke Philips N.V.

Method For Simultaneously Detecting A Plurality Of RFID Tags Using Multiuser Detection  
Patent #
US 20170374438A1
Filed 09/10/2017

Current Assignee
Collision Communications Inc.

Sponsoring Entity
Collision Communications Inc.

Method for simultaneously detecting a plurality of RFID tags using multiuser detection  
Patent #
US 10,117,004 B2
Filed 09/10/2017

Current Assignee
Collision Communications Inc.

Sponsoring Entity
Collision Communications Inc.

Object Identification system with adaptive transceivers and methods of operation  
Patent #
US 6,362,737 B1
Filed 08/11/1999

Current Assignee
RF Code Incorporated

Sponsoring Entity
RF Code Incorporated

Radio tag system and method with improved tag interference avoidance  
Patent #
US 6,034,603 A
Filed 01/24/1997

Current Assignee
Axcess International Inc.

Sponsoring Entity
Axcess Inc.

Anticollision protocol for reading multiple RFID tags  
Patent #
US 5,883,582 A
Filed 02/07/1997

Current Assignee
CHECKPOINT SYSTEMS INC., Mitsubishi Materials Corporation

Sponsoring Entity
CHECKPOINT SYSTEMS INC.

Method and system for remote monitoring and tracking of inventory  
Patent #
US 5,887,176 A
Filed 06/28/1996

Current Assignee
RANDTEC INC.

Sponsoring Entity
RANDTEC INC.

Radio location system for precisely tracking objects by RF transceiver tags which randomly and repetitively emit wideband identification signals  
Patent #
US 5,920,287 A
Filed 01/21/1997

Current Assignee
Zebra Technologies Corporation

Sponsoring Entity


System and method for electronic inventory  
Patent #
US 6,002,344 A
Filed 11/21/1997

Current Assignee
Symbol Technologies LLC

Sponsoring Entity
William R. Bandy, Michael R. Arneson, Robert A. Williams

Powerefficient technique for multiple tag discrimination  
Patent #
US 5,521,601 A
Filed 04/21/1995

Current Assignee
Intermec IP Corporation

Sponsoring Entity
International Business Machines Corporation

Transponder system with variable frequency transmission  
Patent #
US 5,450,492 A
Filed 10/30/1992

Current Assignee
IPC UNIPOST SC

Sponsoring Entity
DISYS CORPORATION

Audible tag for magnetic electronic article surveillance systems  
Patent #
US 5,012,224 A
Filed 08/03/1990

Current Assignee
Sensormatic Electronics Corporation

Sponsoring Entity
Sensormatic Electronics Corporation

Object identification system  
Patent #
US 4,209,783 A
Filed 03/22/1978

Current Assignee
Tokyo Shibaura Electric Co. Ltd.

Sponsoring Entity
Tokyo Shibaura Electric Co. Ltd.

30 Claims
 1. A method of identifying a plurality of tags, said method comprising:
(a) maintaining a set of query strings;
(b) selecting a string from the set of query strings;
(c) removing the selected string from the set of query strings;
(d) broadcasting to the plurality of tags a query message containing at least a portion of the selected string;
(e) receiving a response from the plurality of tags; and
(f) if the plurality of tags includes any unidentified tags, repeating steps (b) through (f).  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 28)
 17. A system for identifying a plurality of tags, said system comprising:
a transceiver;
storage; and
a controller, said controller programmed to perform the functions of;
(a) maintaining a set of query strings;
(b) selecting a string from the set of query strings;
(c) removing the selected string from the set of query strings;
(d) causing the transmitter to broadcast to the plurality of tags a query message containing at least a portion of the selected string;
(e) receiving through the transceiver a response from the plurality of tags; and
(f) if the plurality of tags includes any unidentified tags, repeating steps (b) through (f).  View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 29, 30)
1 Specification
This application claims priority from U.S. Provisional Application Ser. No. 60/210,634, filed Jun. 9, 2000.
This invention relates generally to electromagnetic tag identification.
The emergence of lowpower and lowcost sensing technologies enables the development of electromagnetic tags. A tag has a unique ID that is remotely readable via an electromagnetic channel by a tag reader. When attached to consumer goods, the tags can be used as identifiers that may replace Uniform Product Codes (Bar Codes) in the near future. It is because the tags, unlike the bar codes, can be read without direct line of sight. The tags can also be implemented on smart automated systems that exhibit intelligent, collaborative behavior, which may bring drastic improvements on human productivity and efficiency. Example applications of the tags include automatic object tracking, inventory and supply chain management, and Web appliances.
A tag system is similar to a multiaccess communication system in that tags and the tag reader share a bandwidthlimited channel. To resolve conflicts in accessing the channel, the tag system uses a collision resolution protocol that requires no prior scheduling or central control, in a similar manner as in a multiaccess system. However, additional challenging issues exist in a tag system. Because of severe cost constraint in a tag system, the tags are very limited in memory, power, and computations capabilities. Because of the limited resources available in the tags, it is not desirable for the tags to communicate with each other directly or to maintain dynamic states in their circuitry.
In a general aspect of the invention, a method of identifying a plurality of tags uses an efficient memoryless protocol. The method includes maintaining an ordered set of query strings; selecting a string from the set of query strings; removing the selected string from the set of query strings; broadcasting to the plurality of tags a query message containing at least a portion of the selected string; and receiving a response from the plurality of tags. If the plurality of tags includes any unidentified tags, the method repeats the selecting step through the receiving step.
Embodiments of the above aspects of the invention may include one or more of the following features.
The query message includes the entire selected string. If the received response identifies one of said plurality of tags, the method includes storing the identity of the identified tag.
If the received response indicates a collision has occurred, a first extension is appended to the selected string to generate a first new query string, and the first new query string is added to the set of query strings. If a collision has occurred, a second extension is appended to the selected string to generate a second new query string, and the second new query string is added to the set of query strings. Appending the first extension to the selected string involves appending the first extension to the end of the selected string as a suffix to generate the first new query string. Appending the second extension to the selected string involves appending the second extension to the end of the selected string as a suffix to generate the second new query string. The first extension and the second extension are binary numbers. For example, the first extension is a one, and the second extension is a zero.
If the received response indicates a collision has occurred, the method further includes appending a 00 to the selected string to generate a first new query string, appending a 01 to the selected string to generate a second new query string, appending a 10 to the selected string to generate a third new query string, appending a 11 to the selected string to generate a fourth new query string, and adding the first second, third, and fourth new query strings to the set of query strings.
The method further includes initializing the set of query strings with a 0 and a 1.
If no collision is detected in the response, the method includes repeating broadcasting the same query message and receiving a response for a predetermined number of times.
The method further includes estimating the number of tags in the response when receiving the response from the plurality of tags. If the response is from more than one tag, the method skips a string in the set of query strings.
The broadcasting step includes broadcasting a short command in the query message to induce a onebit response from the plurality of the tags.
In another aspect of the invention, a system for identifying a plurality of tags includes a transceiver; storage; and a controller, the controller programmed to perform the functions of: maintaining an ordered set of query strings in the storage; selecting a string from the set of query strings; removing the selected string from the set of query strings; causing the transmitter to broadcast to the plurality of tags a query message containing at least a portion of the selected string; and receiving through the transceiver a response from the plurality of tags. If the plurality of tags includes any unidentified tags, the controller is programmed to repeat the selecting step through the receiving step.
Embodiments of the above aspects of the invention may include one or more of the following features.
The query message includes the entire selected string. If the received response identifies one of said plurality of tags, the controller is programmed to store the identity of the identified tag.
If the received response indicates a collision has occurred, the controller is programmed to append a first extension to the selected string to generate a first new query string, and add the first new query string to the set of query strings. If a collision has occurred, the controller is programmed to append a second extension to the selected string to generate a second new query string, and add the second new query string to the set of query strings. Appending the first extension to the selected string involves appending the first extension to the end of the selected string as a suffix to generate the first new query string. Appending the second extension to the selected string involves appending the second extension to the end of the selected string as a suffix to generate the second new query string. The first extension and the second extension are binary numbers. For example, the first extension is a one, and the second extension is a zero.
If the received response indicates a collision has occurred, the controller is further programmed to append a 00 to the selected string to generate a first new query string, append a 01 to the selected string to generate a second new query string, append a 10 to the selected string to generate a third new query string, append a 11 to the selected string to generate a fourth new query string, and add the first second, third, and fourth new query strings to the set of query strings.
The controller is further programmed to initialize the set of query strings with a 0 and a 1.
Embodiments may have one or more of the following advantages. The method and system advantageously devise a number of techniques for tag identification, where a tag reader attempts to obtain the unique tag ID of each tag within a readable range. Each tag employs a memoryless protocol that requires minimal computations, memory, and power. The protocol specifies that the current response of each tag depends only on the current query of the tag reader but not on the past query history. Moreover, the only computation required for each tag is to match its ID against the binary string in the query. The tag identification methods are efficient in terms of both time and communication complexities.
The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.
Referring to
Tag reader 30 includes a transceiver 40, a storage device 60 and a controller 50. Under control of controller 50, tag reader 30 broadcasts query signals stored in storage device 6Q through transceiver 40 to tags 10 via communication channel 70. For the purpose of identifying the tags, each query signal contains a query string that may be a tag ID or a prefix of a tag ID.
Tags 10 have minimal computing circuitry. Tags 10 do not have batteries or any independent power sources, and therefore are passive. Except for an incremental matching technique that will be described below, tags 10 do not maintain dynamic states of the communication process in their circuitry. In other words, tags 10 employ a memoryless protocol, which specifies that the current response of each tag only depends on the current query of tag reader 30, but not on the past history of the reader'"'"'s queries.
Tag 10 includes an electromagnetic front end 41, which converts electromagnetic energy in the query signal into DC voltage. Powered by the DC voltage, tag logic 43 compares the query string in the query signal against its tag ID stored in memory 20, and transmits results back to tag reader 30 when appropriate. The comparison of tag ID with the query string is the only computation performed by tag logic 43.
To identify the tags, tag reader 30 broadcast a query signal to tag 10s. Each tag 10 uses its electromagnetic front end 41 to detect and receive the query signal, and sends a response back to tag reader 30 if the query signal matches a prefix of its ID. If only one tag 10 responds, tag reader 30 receives the tag ID from the tag and will identify the tag successfully. If more than one tag 10 responds, their responses will collide in communication channel 70, and tag reader 30 will detect a collision as a result.
A tag identification method, as described below, specifies a communication process between tag reader 30 and tags 10, so that the tag reader can collect all the tag IDs at the end of the process. According to the method, tag reader 30 initially does not know anything about the tags. The method requires minimal computations and memory for each tag 10.
Referring to
A rigorous description of the method, known as the QueryTree (QT) protocol, is provided in the following. A theoretical discussion on the Query Tree is presented in Appendix A. An algorithmic description of the QT protocol is given below.
Let A=U^{i=0}^{k }{0, 1}^{i }be the set of strings in {0, 1} with length at most k. The state of tag reader 30 is a pair of queue and memory (Q, M) located in storage device 60, where queue Q is an ordered set of strings in A; and memory M is a set of strings in A. A query string transmitted from tag reader 30 is a string q in A. A reply from a tag 10 is a string w in {0, 1}^{k}.
At tag reader 30, the queue Q is defined as {ε} initially for convenience, where E is the empty string, and memory M is empty. Let (q, x) represent a string formed by appending x to string q, where x is 1 or 0.
 1. Let Q={q_{1}, q_{2}, . . . , m}.
 2. Update Q to be {q_{2}, . . . , q_{m}} and broadcast query q, to tags 10.
 3. On receiving a response from tags 10:
 If the reply is the string w, tag reader 30 insert the string w into memory M of storage device 60.
 If tag reader 30 detects a collision at communication channel 70, then tag reader 30 updates Q to be {q_{2}, . . . , q_{m}, (q_{1},0), (q_{1},1)}.
 If there is no reply, do nothing.
 4. Repeat the above procedures until Q is empty.
At tag 10, let w=(w_{1}, w_{2}, . . . , w_{k}) be its tag ID. Let q be the query string received from the reader. If q=ε or q=(w_{1}, w_{2}, . . . , w_{q}), then it sends string w to tag reader 30. When more than one tag responds at the same time, tag reader 30 detects a collision instead of receiving the messages.
Referring to
In reality, it is not possible for tag reader 30 to send the empty string F. Thus, in practice, the method generally starts with Q {0, 1}.
A fault tolerant version of the tag identification method is useful when the communication between tags 10 and tag reader 30 is unreliable. As a result, some tags might not be identified and be considered as missing. The fault tolerant method is designed to trade running time for the probability of missing tags. In particular, a fault tolerant method (QT^{l}) requires repeating a query string q until no collision occurs for l times, where 0 is a positive integer greater than one. The choice of 0 can be made to minimize the probability of a missing tag with query string q. Two theorems (Theorems 3 and 4) of the fault tolerant method are presented in Appendix I.
Further techniques can be used to reduce time complexity, i.e., the running time, of the tag identification process. Theoretical discussions on time complexity are presented in Appendix I. Three techniques, e.g., shortcutting, aggressive advancement and categorization, are introduced in the following description.
Shortcutting. Assume that tag reader 30 detects a collision for a query string q. To continue the identification process, tag reader 30 appends a 1 or a 0 to the current query string q to form a next query string; the order of appending a 1 or a 0 can be randomly chosen. Suppose x and y are complementary binary numbers, i.e., x=1 if y=0, and x=0 if y=1. Assume that tag reader 30 chooses to transmit (q, x) as the next query string. If there are no tags with prefix (q, x), then tag reader 30 knows that there are at least two tags with prefix (q, y). Therefore, the reader skips transmitting the query string (q, y).
The shortcutting technique gives an improved expected running time bound of 2.655n−1.
Aggressive Advancement. Assume that tag reader 30 knows that at least n unrecognized tags exist with prefix q. For example, tag reader 30 may have an a priori knowledge of tagged items in a warehouse, or the tag reader can detect the strength of responses from tags to estimate the number of the tags.
In this situation, it is very likely that that queries containing (q, 1) and (q, 0) will collide. On the other hand, the probability that no collision occurs is ½^{n−1}, which is negligible if the number of tags n is large. Aggressive advancement method updates the set of query string Q by appending two bits to the query string q, and inserting the four appended—query strings to the set Q. In other words, tag reader 30 will transmit query strings (q, 00), (q, 01), (q, 10), and (q, 11) instead of (q, 0) and (q, 1). With this technique, the probability of saving two queries (q, 0) and (q, 1) is 1−½^{n−1}. Accordingly, the number of queries sent by tag reader 30 is reduced.
Categorization. A categorization technique is used when tag reader 30 has a priori knowledge of the types of tags 10, and therefore knows how to categorize tag IDs. For example, assume that tag reader 30 knows that a set of tag IDs G can be partitioned into G_{1}, . . . G_{m}, such that all the tag IDs in G_{i }have a prefix q_{i}. Under such circumstances, tag reader 30 can identify each set G_{i }independently, thus reducing the running time. In particular, if the tags are partitioned into m groups, then the upper bound on the expected running time is improved to 2.887n−m.
Two other techniques, i.e., shortlong queries (QTsl) and incremental matching (QTim), are designed to improve communication complexity of tag reader 30 and tags 10, which is the number of bits sent by the tag reader and the number of bits transmitted by the tags, respectively. It is particularly desirable to reduce the communication complexity of the tags because power consumption of the tags is reduced as a result. Theoretical discussions on communication complexity are presented in Appendix II.
ShortLong Queries. In the QT protocol, as illustrated in the example of
An algorithmic description of the shortlong query method is provided below. Let A=U_{i=0}^{k }{0, 1}^{i }be the set of strings in {0, 1} with length at most k. The state of tag reader 30 is a pair (Q, M) stored in storage device 60, where the queue Q is an ordered set of strings in A; and memory M is a set of strings in A.
A query transmitted from tag reader 30 is a pair (c, w), where cε{short, long} and w is a string in A. A reply from a tag is a string “1” or a string in {0, 1}^{k}.
At tag reader 30, the queue Q is defined as {F} initially for convenience, where ε is the empty string, and memory M is empty.
 1. Let Q={q_{1}, q_{2}, . . . , q_{m}}.
 2. Broadcast short query (short, q_{m}) to tags 10.
 3. Update Q to be {q_{1}, . . . , q_{m−1}. }
 4. On receiving a response from tags 10:
 If the reply is “1”, then
 i. broadcast long query (long, q_{m}) to tags 10;
 ii. insert the response string w into memory M of storage device 60.
 If a collision is detected at communication channel 70, then update Q to be {q_{1}, . . . , q_{m−1}, (q_{m},0), (q_{m},1)}.
 If there is no reply, do nothing.
 If the reply is “1”, then
 5. Repeat the above procedures until Q is empty.
At tag 10, let w=(w_{1}, w_{2}, . . . , w_{k}) be the tag ID. Let (c, q) be the query string received from tag reader 30. If q=ε or q=(w_{1}, w_{2}, . . . , w_{q}), then
 If command c is short, it sends string “1” to tag reader 30.
 If command c is long, it sends string w to tag reader 30.
An example of the shortlong query method is shown in FIG. 4. At blocks 310, 330, 360, and 380, tag reader 30 sends a long query after it receives a “1” in the reply from one of tags 10. In contrast to the “firstinfirstout” approach described in the QT protocol, the shortlong query method adopts a “lastinfirstout” approach. Although either approach can be used for the QT protocol and the shortlong query method, the “lastinfirstout” is best used in an incremental matching method as will be discussed below.
Incremental Matching. Incremental matching is another technique designed for reducing the communication complexity. However, the technique requires tag 10 to remember the bit position of the prefix it has matched so far. Therefore, the protocol specified by the method is no longer memoryless.
The incremental matching is very similar to shortlong query. Thus, we will only describe the differences between the two techniques.
Referring to
A transient tag will become inactive (block 440) if the next query is neither a long query nor a reactivate command. If the next query is a long query, the transient tag will become active and reset bit marker b to 1 (block 410). An inactive tag remains inactive (block 440) even when a reactivate command is received.
All tags 10 reset their respective bit markers to 1 and become active again upon receiving a long query (block 410). When a long query is received, each of the tags 10 in active state responds with its full tag ID.
With these extra tag functionalities, tag reader 30 can send query strings incrementally, which would not be possible for shortlong queries. For example, if tag reader 30 sent q in the previous query and the tag reader is about to send (q, 1) as in the example of
The communication complexity of the incremental matching for tags is the same as that of shortlong query. However, the communication complexity of tag reader 30 is reduced.
A number of embodiments of the invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. Accordingly, other embodiments are within the scope of the following claims.
5 Time Complexity
In this section, we analyze the time complexity of the QT protocol. Assuming that each queryresponse step takes a fixed amount of time, we count the number of queries sent by the reader in a complete execution of the protocol. We define the identification time of the QT protocol, denoted by T_{S}, as the number of queries sent by the reader in order to identify a set of tags S. As we discussed in the preceding section the underlying algorithm of QT is similar to the confilct resolution algorithms studied in some previous work. Using similar analysis from [7], we can also show that for n=S≧4,
2.881n−1≦E[T_{S}]≦2.887n−1
for a uniformly distributed random set S, where E[T_{S}] is the expected identification time. This gives us the average time complexity of the QT protocol. In Section 5.2, we discuss the worstcase time complexity of the protocol. We show that in the worst case, it takes n·(k+2−log n) steps to identify all the n tags. In Section 5.3, we argue that with high probability, the running time of the protocol is O(n).
To help our analysis in the current section and subsequent sections, we introduce the notion of a query tree, which describes the complete dialogue between the reader and the tags in an execution of the QT protocol. Knowing the size of the query tree, we can find out the identification time of the QT protocol.
5.1 Query Tree
A query tree is a full binary tree (a binary tree in which each node has either two children or no children) capturing the complete readertags dialogue of the QT protocol. For a given execution of the protocol, there is a onetoone correspondence between every node in the query tree and every query sent by the reader. Therefore, the size, i.e. number of nodes, in the query tree is equal to the number of queries sent by the reader.
For any node x in the query tree, let f(x) be the query string in the corresponding query. Also, for a query tree node x, let l(x) and r(x) be the left child and right child of x respectively. If x is a leaf node, then l(x) and r(x) are defined to be NIL.
Definition of a Query Tree
Suppose the QT protocol is executed, and the reader has sent the set of query strings Q. The query tree of the QT protocol is defined recursively by Q.
 1. The root of the query tree corresponds to the query string ε.
 2. If the query tree node x corresponds to the query string q, and both q0, q1 ∈ Q, the l(x) and r(x) are query tree nodes that correspond to the query strings q0 and q1 respectively. Otherwise, both l(x) and r(x) equal NIL.
See
The above definition implies that an internal node of a query tree corresponds to a query string that results in a collision in the communication channel. On the other hand, a leaf corresponds to a query string that results in either no reply or a response from exactly one tag. To facilitate our discussion, we shall call a leaf white if the corresponding query string results in no reply, and black otherwise.
Structure of a Query Tree
From the definition of query tree, we have the following observation:
 1. The height of a query tree is at most k, since the query string sent out by the reader is at most k bits long.
 2. If x is an internal node, then x has at least two black leaf descendants. This follows from the fact that each black leaf corresponds to a unique tag ID and each internal node corresponds to a query that results in a collision.
5.2 WorstCase Time Complexity
The number of queries sent by the reader equals the size of the query tree. Given a set S of n tags, let Y_{S }be the query tree for S. Also, let R_{S }be number of internal nodes of the tree Y_{S}. Since a query tree is a full binary tree, the size of the tree is simply 2R_{S}+1.
A simple argument can give a bound on the size of Y_{S}. In a query tree, any internal node is an ancestor of some black leaf. For each black leaf, it has at most k ancestors, which are internal nodes. This gives us R_{S}≦kn. Therefore, it follows that the size of the tree equals 2R_{S}+1, which is no more than 2nk+1.
An improved result is stated in the following:
Theorem 1 The number of queries sent by the reader to identify n tags is at most n·(k+2−log n).
Proof. The number of queries sent by the reader to identify n tags equals the size of the corresponding query tree, which has exactly n black leaves. In Appendix A, it is shown that the size of any query tree with exactly n black leaves is no more than n·(k+2−log n).
5.3 Probabilistic Analysis
Here we show that with high probability, the running time of the QT protocol is O(n).
Mathys and Flajolet [8] claimed that the variance of the running time can be shown to be linear in n, as n→∞. And this would be sufficient to show that the running time is linear in n with high probability. However, the derivation was omitted in [8] because it is “rather lengthy and complicated”.
In the following we will present a proof that QT has linear running time with high probability. We note that by bounding the number of white leaves (as introduced in Section 5), we essentially bound the total size of the tree.
Let W_{n }be the random variable of the number of white leaves in a query tree with n black leaves. We will apply the Chernoff bound on the upper tail of the distribution of W_{n}. We first need the following technical lemmas.
Lemma 1 For n≧2,
E[e^{0.4W}^{n}]≦e^{0.4n}.
Proof. See Appendix B.
Lemma 2
Pr{W_{n}≧α}≦e^{0.4(n−α)}.
Proof. See Appendix B.
We now show that the running time of QT is O(n) with high probability. In particular, the probability that QT takes at least cn steps decreases exponentially with size n.
Theorem 2 The probability the QT protocol takes at least cn steps to identify n tags is at most e^{−0.4n(c/2−2)}.
Proof. When the size of the query tree is larger than cn−1, the number of white leaves is at least cn/2−n. By Lemma 2,
Pr{W_{n}≧α}≦e^{−0.4(α−n) }
for all α>0. Let α=cn/2−n, then,
Pr{W_{n}≧cn/2−n}≦e^{−0.4((cn/2−n)−n)}=e^{−0.4n(c/2−2)}.
Theorem 3 With failure probability p≦1/2, the running time of the QT^{l }protocol is at most
Proof. See Appendix C
Theorem 4 With failure probability p, the probability that the QT^{(C+1)log}^{1/p}^{n }protocol does not identify all tags is at most 1/n^{c}.
Proof. The probability that a certain tag is not identified is at most p^{(C+1)log}^{1/p}^{n}. Therefore, the probability that any tag is unidentified is np^{(c+1)log}^{1/p}^{n}=1/n^{c}.
7. Communication Complexity
In this section we turn our attention to the communication complexity of the protocol. The reader communication complexity is the number of bits sent by the reader; and the tag communication complexity is the number of bits sent by a tag. The tag communication complexity is especially important because it is desirable to minimize the power consumption of the tags.
We will first derive the communication complexities of out QT protocol and then introduce several variants that improve upon the performance of QT.
7.1 Basic QueryTree
In the followings, we will first find the expected number of collisions experienced by a tag. We assume that the bit length k of each tag ID is infinite. This will give us an upper bound for cases where k is finite. We show that in the QT protocol, the expected number of responses a tag makes is no more than 2.21 log n+3.19, where n is the total number of tags.
In the algorithm QT, each tag responds to query strings that match its prefix. It will experience a collision only if there is some other tag having the same prefix, which is the query string sent by the reader.
We consider a system with n tags. Let w be the ID of an arbitrary tag, Let C_{w }be the number of collisions the tag has experienced. In addition, let I_{w}^{i}, j=1, . . . be an indicator variable such that:
Then we have the following equation:
By linearity of expectation,
For each J ε {0, 1, 2, . . . },
Therefore, the expected number of conflicting responses the tag experiences is given by:
A bound on EC_{w} is derived in Theorem 5, which depends on the follwoing technical lemma.
Lemma 3 for all n≧2,
Proof. See Appendix D.
Now we are ready to state the theorem and prove it.
Theorem 5 For a system with n tags, a tag is expected to experience no more than 2.21 long n+3.19 conflicts before it successfully transmits its ID.
Proof. See appendix D.
Theorem 6 Let there be n tags to be identified. The expected reader communication complexity for QT is 2.89 kn. The expected tag communication complexity is 2.21 k log_{2 }n+4.19 k.
Proof. See Appendix E.
Theroem 7 Let there be n tags to be identified. The expected reader communication complexity of QTsl is at most 3.89 kn+3.89 n. The expected tag communication complexity of QTsl is at most 2.21 ln n+k+4.19.
Proof. See Appendix E.
Theorem 8 The expected reader communication complexity of QTim protocol is at most 2.21 n log_{n }n+6.10 n.
Proof. See Appendix E.
A. Bounding the Query Tree Size
Our objective in this section is to give an upper bound on the size of a query tree with n black leaves. Let T be a query tree with n black leaves. Since it is a complete binary tree, the number of nodes in T is simply 2l−1, where l is the number of leaves in T. Therefore, our goal in this section is to bound the number of leaves l in T. The result will be stated in Theorem 9, which depends on the following Lemmas.
Lemma 4 For any query tree with height k and two black leaves, the number of leaves in the tree is at most k+1.
Proof. Suppose there are m≧k+2 leaves in the query tree. Then the tree has at least k+1 internal nodes. Since the height of the query tree is at most k, there exist two internal nodes in the tree whose depth is the same. Therefore, these two nodes do not have any common decendants. As a result, one of them must have fewer than two black leaf decendants, since there are totally two black leaves in the query tree. This contradicts with the fact that every internal node must have at least two black leaf descendants.
Lemma 5 Suppose T is the largest query tree with exactly n black leaves. If n is even, then the sibling of any black leaf in T is also a black leaf. In n is odd, the same is true except for one black leaf, whose sibling is an internal node.
Proof. First note that the sibling of a black leaf cannot be a white leaf, since otherwise the parent of the black leaf will have only one black leaf descendant. Now suppose there are two black leaves in T whose siblings are internal nodes. Then
Lemma 6 If T is the largest query tree with exactly n black leaves, where n is odd, then there exists a query tree T′ that has exactly n−1 black leaves and has the same size as T.
Proof. By Lemma 5 there is a black leaf in T whose sibling is an internal node. By replacing the black leaf by a white leaf, the modified tree T′ is still a valid query tree. In addition, it has n−1 black leaves and has the same size as T.
See
FIG. 3: (a): Two subtrees of a query tree with an upaired black leaf. (b): The modified subtrees. Note that there is one more white leaf in the modified query tree.
See
FIG. 4: Modifying a query tree with the structure in (a) into a larger query tree in (b). The tree in (b) has one more white leaf than (a).
Because of Lemma 6, we only consider the case where n is even. Suppose T is the largest query tree with exactly n black leaves. By Lemma 5, we can pair up all the sibling black leaves in T.
To count the number of leaves in T, we first “cut away” subtrees from T to form a set of subtrees Q, so that any leaf in T belongs to some subtree in Q, as stated in Lemma 7. As a result, the number of leaves in T is simply the total number of leaves in the subtrees in Q. The set Q is defined as follows:
Q={S_{i}S_{i }is the largest subtree of T that contains exactly one pair of sibling black leaves}. (4)
Lemma 7 Suppose T is the largest query tree with exactly n black leaves, where n is even and positive, then any leaf in T will appear in some subtree in Q.
Proof. By definition of Q, every black leaf must appear in some subtree in Q. Suppose there is a white leaf x that does not appear in any subtree in Q. Let y denote the parent of x and S denote the subtree rooted at y. Then at least two pairs of black leaves must appear in S. Suppose only one pair of black leaves appear in S. The fact that S∉Q implies there is a different subtree S_{i }ε Q of T such that S_{i }contains the same pair of black leaves and it is larger than S. This implies S is a subtree of S_{i}. Since S_{i }ε Q, the white leaf x does not appear in S_{i}. As a result, the fact that x appears in S contradicts that S is a subtree of S_{i}.
Given that at least two pairs of black leaves appear in S,
As a result, we can count of total number of leaves in Q to give an upper bound of the number of leaves in T. Since every subtree in Q has exactly two black leaves, we can apply Lemma 4 to count the number of leaves in each subtree in Q.
Theorem 9 The total number of leaves in a query tree with height k and n black leaves is at most
Proof. Suppose T is the largest query tree with n black leaves. We construct the set of subtrees Q as in (4). For each subtree S_{i }in Q, let root(S_{i}) denote the root of the tree S_{i }and let depth(S_{i}) denote the depth of the node root(S_{i}) in T. Then the height of each subtree S_{i }in Q is at most k−depth(S_{i}), since the height of the T is at most k. By Lemma 4, the number of leaves in S_{i }is therefore at most k−depth(S_{i})+1. Summing over all the subtrees in Q, the total number of leaves, denoted by L(Q), is given by:
Lemma 8 gives a bound on the last term in the above equation.
Proof. For each subtree S_{i }δ Q, its root root(S_{i}) has depth depth(S_{i}) in the original tree T. Since T is a binary tree, and all the trees in Q are disjoint, if we set h(S_{i})=2^{−depth(S}^{i}^{)}, we have:
By the fact that the geometric mean of a set of nonnegative numbers is at most their arithmetic mean, we have:
Therefore, by Equation 8,
Dividing both sides by n/2, taking the logarithm and then multiplying by n/2 on both sides, we have:
Finally, we continue from Equation (7) to prove Theorem 9:
B Proof of Lemmas 1 and 2
Lemma 2 for n≧2,
E[e^{0.4Wn}]≦e^{0.4n } (18)
Proof. Since W_{0}=1 and W_{1}=0, we have
E[e^{0.4W}^{0}]=e^{0.4},
E[e^{0.4W}^{1}]=1.
For n≧2, we have the following recurrence:
where W_{i }and W_{n−i }are the number of white leaves in the two subtrees. Since W_{i }and W_{n−i }are independent, we can write Equation (19) as
First, for the base case n=2, we have
Therefore,
It remains to show that E[e^{0.4W}^{n}]≦e^{0.4n }for n>2.
Multiplying both sides of Equation (20) by 2^{n}, we have
Now, after subtracting both sides of Equation (21) by 2e^{0.4}E[e^{0.4W}^{n}], we apply our inductive assumption that E[e^{0.4W}^{i}]≦e^{0.4i }for i=2, . . . , n−1,
For n>2,
n(1−e^{−0.4})>e^{0.4}−1.
Thus, we conclude that
(2^{n}−2e^{0.4})E[e^{0.4W}^{n}]<e^{0.4n}(2^{n}−2e^{0.4}) (22)
And dividing Equation (22) by 2^{n}−2e^{0.4 }yields
E[e^{0.4W}^{n}]<e^{0.4n }
Lemma 2 Let W_{n }be the random variable of the number of white leaves in a query tree with n black leaves, then
Pr{W_{n}≧α}≦e^{0.4(n−α)}.
Proof. The Chernoff Bounds[10, p.39] state that for any random variable X and α>0,
Pr{X≧α}≦e^{−tα}E[e^{tX}] (23)
for all t>0.
Setting t=0.4 and X=W_{n}, we can rewrite Equation (23) as
PR{W_{n}≧α}≦e^{−0.4α}E[e^{0.4W}^{n}].
And by Lemma 1, we have
C Proof of Theorem 3
Theorem 3 With failure probability p≦½, the funning time of the QT^{l }protocol is at most
Proof. There is a probability of p^{n }that all tags fail to respond. And for n>1, there is a probability of np^{n−1}(1−p) that exactly one tag responses.
Let T(n) be the expected running time of the QT^{l }algorithm when there are n tags to be identified.
First, for the base cases,
T(0)=l
T(1)=l
For n≧2, let
p_{n}=p^{n}+np^{n−1}(1−p)
We can rewrite Equation (24) as
thus,
First, we consider the case when there are two tags to be identified. Since p^{2}+2p(1−p)=2p−p^{2},
Solving Equation (26) for T(2) yields
Since p_{2 }is a decreasing function on p, thus 2/(1−p_{2}) is a decreasing function on p. Then, 2/(2−p_{2})=8 when p=½, thus
T(2)≦3l+8
Thus, since n=2,
Therefore, the upper bound
on running time is valid for n=2.
Now we will prove the upper bound for n>2 inductively. We have from Equation (25),
Multiplying both sides by 2^{n−1},
Subtract T(n) from both sides and assume that T(i)≦ki−1 for i=2, . . . , n−1, where
It is straightforward to verify that
for n≧3. Thus
(2^{n−1}−1)T(n)≦kn(2^{n−1}−1)−(2^{n−1}−1)−kn+(1+n)(l+1)+2n+1
Since for n≧3, (1+n)(l+1)+2n+1−kn<0, we conclude that
T(n)≦kn−1.
D Expected Number of Conflicts Experienced by a Tag
We first prove Theorem 5, assuming Lemma 3 is true. Then we will prove Lemma 3.
D.1 Proof of Theroem 5
Therorem 5 For a system with n tags, a tag is expected to experience no more than 2.21 log n+3.19 conflicts before it successfully transmits its ID.
Proof. From Equation (3), the expected number of conflicting responses a tag experiences, E[C_{w}], is given by
We first prove by induction on n that,
Base Case: The statement is true for n=1, 2 and 3.
Inductive Case: Assume the statement is true for n−1, where n≧4. In other words,
Then we proove the statement is true for n:
Because of the following fact:
the expected number of collisions experienced by a tag is at most:
C(1+ln(n−1)),
which is less than 2.21 log n+3.19.
D.2 Proof of Lemma 3
We organize the proof as follows. We split the series
into 8 parts:
where p_{1}=└log(n+1)┘−1 and p_{2}=└log(n+1)┘+2. We give an upper bound on each part, as stated in Lemmas 11, 12, and 13. From the lemmas we can give an upper bound on the series as a whole.
We first prove the following two lemmas, which will be used in the proofs of Lemmas 11 and 12.
Lemma 9 Let f(x)=2^{−x}(1−2^{−x})^{n}. For nonnegative x, f′(x)>0 if and only if x<log(n+1).
Proof.
Since 2^{−x }is strictly decreasing,
Also, (1−2^{−x})^{n−1}>0 for x>0. Therefore f′(x)>0 if and only if:
1−(n+1)2^{−x}<0.
Solving the inequality gives us:
x<log(n+1)
Proof. Let y=2^{−x}. Then we have:
Therefore,
Proof. By Lemma 9, f(x)=2^{−x}(1−2^{−x})^{n }is strictly increasing for 0≦x<log(n+1). Therefore, for any j=1, 2, . . . , p_{1}, f(x)≧f(j) for j<x≦j+1. It follows that:
Summing up the inequalities for j=1, . . . , p_{1}, we have:
Therefore, we have:
Proof. The proof is similar to the proof of Lemma 11. By Lemma 9, f(x)=2^{−x}(1−2^{−x})^{n }is nonincreasing for x≧log(n+1). Therefore, for any j=p_{2}, p_{2}+1, . . . , we have f(x)≧f(j) for j−1≦x≦j. It follows that
Summing up the inequalities for j=p_{2}, p_{2}+1, . . . , we have:
Therefore, it follows that:
Now, we are ready to prove Lemma 3.
Lemma 3 For n≧2,
Proof. Let p_{1}=└log(n+1)┘−1, p_{2}=└log(n+1)┘+2.
E Proofs of Theorems 6, 7, and 8
Theorem 6 Let there be n tags to be identified. The expected reader communication complexity for QT is 2.89kn. The expected tag communication complexity is 2.21k log_{2 }n+4.19k.
Proof. Since the expected running time is at most 2.887n−1, and the length of each query is at most K. Therefore the expected total number of bits sent by thereader is at most 2.89kn.
The expected depth of a black node is 3.19+2.21 log_{2}n. On each step, the tag sends a kbit ID, then the expected tag communication complexity is at most
2.21k log_{2 }n+4.19k.
Theorem 7 Let there be n tags to be identified. The expected reader communication complexity of QTsl is at most 3.89kn+3.89n. The expected tag communication complexity of QTsl is at most 2.21 ln n+k+4.19.
Proof. Note that with QTsl protocol, we need one extra bit to specify whether the query is short or long.
The expected total number of short and long queries is at most 3.887n−1. Each query is at most k+1bit long, thus the expected reader communication complexity is at most
(3.887n−1)(k+1)<3.89kn+3.89n.
The expected depth of a black node is 3.19+2.21 log_{2 }n. For each short query, the tag sends a 1 response. For the long query, the tag sends a kbit ID. Therefore, the expected tag communication complexity is at most
2.21 log_{2 }n+k+4.19.
Theorem 8 The expected reader communication complexity of QTim protocol is at most 2.21n log_{2 }n+6.10n.
Proof. We can partition the queries in the groups such that each group ends with a long query. We can find the number of bits transmitted in each group. The total bits of short queries transmitted is just the one plus the expected prefix when a tag is identified:
3.19+2.21 log_{2 }n+1=2.21 log_{2 }n+4.19
We need 2 bits for each long query, thus 2n in total. Each white node will need 1 extra bit for the reactivate command. Since there are at most 0.444n white nodes in expectation, the expected reactivate overhead is at most 0.89n.
The expected reader communication complexity is at most
2.21n log_{2 }n+7.08n.