Method for estimating number of tags in slotted alohabased RFID system

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
39Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method for estimating the number of tags in a slotted Alohabased RFID system, the method comprising the steps of:
 a) setting the number (N) of slots, the measured number (c_{0}) of empty slots, and the measured number (c_{1}) of ID slots as parameters; and
b) estimating the number (n) of the tags by substituting the set values into n=(N−1)/(c_{0}/c_{1}).
1 Assignment
0 Petitions
Accused Products
Abstract
Provided is a method for estimating the number of tags in a slotted Alohabased RFID system, which can estimate the number of tags through a new statistical average scheme using the number of slots, the measured number of empty slots, and the measured number of ID slots. The estimating method includes the steps of: a) setting the number (N) of slots, the measured number (c0) of empty slots, and the measured number (c1) of ID slots as parameters; and estimating the number (n) of the tags by substituting the set values into n=(N−1)/(c0/c1).
44 Citations
View as Search Results
Coding methods of communicating identifiers in peer discovery in a peertopeer network  
Patent #
US 7,961,708 B2
Filed 07/10/2007

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

WIRELESS POWER TRANSFER FOR FURNISHINGS AND BUILDING ELEMENTS  
Patent #
US 20100201202A1
Filed 10/02/2009

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

CONVEYING DEVICE INFORMATION RELATING TO WIRELESS CHARGING  
Patent #
US 20100201533A1
Filed 10/02/2009

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

WIRELESS POWER TRANSFER FOR VEHICLES  
Patent #
US 20100201189A1
Filed 10/02/2009

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

CODING METHODS OF COMMUNICATING IDENTIFIERS IN PEER DISCOVERY IN A PEERTOPEER NETWORK  
Patent #
US 20090016353A1
Filed 07/10/2007

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

CODING METHODS OF COMMUNICATING IDENTIFIERS IN PEER DISCOVERY IN A PEERTOPEER NETWORK  
Patent #
US 20090016249A1
Filed 07/10/2007

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

CODING METHODS OF COMMUNICATING IDENTIFIERS IN PEER DISCOVERY IN A PEERTOPEER NETWORK  
Patent #
US 20090016248A1
Filed 07/10/2007

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

CODING METHODS OF COMMUNICATING IDENTIFIERS IN PEER DISCOVERY IN A PEERTOPEER NETWORK  
Patent #
US 20090016250A1
Filed 07/10/2007

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

REVERSE LINK SIGNALING VIA RECEIVE ANTENNA IMPEDANCE MODULATION  
Patent #
US 20090286476A1
Filed 10/10/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

SIGNALING CHARGING IN WIRELESS POWER ENVIRONMENT  
Patent #
US 20090286475A1
Filed 10/10/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

METHOD AND APPARATUS FOR AN ENLARGED WIRELESS CHARGING AREA  
Patent #
US 20090284218A1
Filed 10/10/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

WIRELESS POWER TRANSFER FOR APPLIANCES AND EQUIPMENTS  
Patent #
US 20090284245A1
Filed 11/07/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

TRANSMIT POWER CONTROL FOR A WIRELESS CHARGING SYSTEM  
Patent #
US 20090284369A1
Filed 10/10/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

METHOD AND APPARATUS FOR ADAPTIVE TUNING OF WIRELESS POWER TRANSFER  
Patent #
US 20090284220A1
Filed 11/06/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

RECEIVE ANTENNA FOR WIRELESS POWER TRANSFER  
Patent #
US 20090284227A1
Filed 10/10/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

METHOD AND APPARATUS WITH NEGATIVE RESISTANCE IN WIRELESS POWER TRANSFERS  
Patent #
US 20090284082A1
Filed 11/06/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

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

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

Wireless power transfer for appliances and equipments  
Patent #
US 8,487,478 B2
Filed 11/07/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Coding methods of communicating identifiers in peer discovery in a peertopeer network  
Patent #
US 8,494,007 B2
Filed 07/10/2007

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Coding methods of communicating identifiers in peer discovery in a peertopeer network  
Patent #
US 8,520,704 B2
Filed 07/10/2007

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Repeaters for enhancement of wireless power transfer  
Patent #
US 8,611,815 B2
Filed 11/06/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Wireless power transfer using multiple transmit antennas  
Patent #
US 8,629,650 B2
Filed 10/10/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Coding methods of communicating identifiers in peer discovery in a peertopeer network  
Patent #
US 8,630,281 B2
Filed 07/10/2007

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Conveying device information relating to wireless charging  
Patent #
US 8,854,224 B2
Filed 10/02/2009

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Wireless power transfer for vehicles  
Patent #
US 8,878,393 B2
Filed 10/02/2009

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Repeaters for enhancement of wireless power transfer  
Patent #
US 8,892,035 B2
Filed 12/16/2013

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Reverse link signaling via receive antenna impedance modulation  
Patent #
US 8,965,461 B2
Filed 10/10/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Signaling charging in wireless power environment  
Patent #
US 9,130,407 B2
Filed 10/10/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Receive antenna for wireless power transfer  
Patent #
US 9,178,387 B2
Filed 10/10/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Wireless power transfer for furnishings and building elements  
Patent #
US 9,184,632 B2
Filed 10/02/2009

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Method and apparatus with negative resistance in wireless power transfers  
Patent #
US 9,190,875 B2
Filed 11/06/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Coding methods of communicating identifiers in peer discovery in a peertopeer network  
Patent #
US 9,198,148 B2
Filed 12/16/2013

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Method and apparatus for adaptive tuning of wireless power transfer  
Patent #
US 9,236,771 B2
Filed 11/06/2008

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Systems and methods relating to multidimensional wireless charging  
Patent #
US 9,312,924 B2
Filed 09/25/2009

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Wireless power transfer for portable enclosures  
Patent #
US 9,583,953 B2
Filed 02/12/2013

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Coding Methods of communicating identifiers in peer discovery in a peertopeer network  
Patent #
US 9,848,372 B2
Filed 07/29/2013

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Reverse link signaling via receive antenna impedance modulation  
Patent #
US 9,954,399 B2
Filed 02/23/2015

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Signaling charging in wireless power environment  
Patent #
US 9,991,747 B2
Filed 08/27/2015

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Method and system for distance determination of RF tags  
Patent #
US 7,511,604 B2
Filed 05/04/2003

Current Assignee
Zebra Enterprise Solutions Corp.

Sponsoring Entity
SANDLINKS SYSTEMS LTD.

Lowcomplexity cryptographic techniques for use with radio frequency identification devices  
Patent #
US 7,532,104 B2
Filed 02/19/2004

Current Assignee
Emc IP Holding Company LLC

Sponsoring Entity
RSA Security LLC

Distributed ethernet hub  
Patent #
US 7,356,042 B2
Filed 06/21/2002

Current Assignee
Tellabs Bedford Inc.

Sponsoring Entity
Tellabs Bedford Inc.

Collision mitigation methods used in a communication system  
Patent #
US 20030072288A1
Filed 10/17/2001

Current Assignee
Motorola Solutions Inc.

Sponsoring Entity
Motorola Solutions Inc.

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.

2 Claims
 1. A method for estimating the number of tags in a slotted Alohabased RFID system, the method comprising the steps of:
 a) setting the number (N) of slots, the measured number (c_{0}) of empty slots, and the measured number (c_{1}) of ID slots as parameters; and
b) estimating the number (n) of the tags by substituting the set values into n=(N−1)/(c_{0}/c_{1}).  View Dependent Claims (2)
 a) setting the number (N) of slots, the measured number (c_{0}) of empty slots, and the measured number (c_{1}) of ID slots as parameters; and
1 Specification
The present invention relates to a method for estimating the number of tags in a slotted Alohabased RFID system; and, more particularly, to a method for estimating the number of tags in a slotted Alohabased RFID system, which can estimate the number of tags through a new statistical average scheme using the number of slots, the measured number of empty slots, and the measured number of ID slots.
DESCRIPTION OF RELATED ARTRadio Frequency IDentification (hereinafter, referred to as RFID) is a wireless data collection technology that can identify, track and manage a product, animal, or person, to which a tag is attached, by reading or writing data from/to the tag having unique identification information by using radio frequency. The RFID system includes a plurality of electronic tags or transponders (hereinafter, referred to as tags) attached to a product or animal having unique identification information, and an RFID reader or interrogator for reading or writing the information contained in the tags. The RFID systems are classified into a mutual induction scheme and an electromagnetic scheme, depending on communication schemes between the reader and the tag. Also, the RFID systems are classified into a passive RFID system and an active RFID system, depending on whether the tag has its own power source. In addition, the RFID systems are classified into a long wave RFID system, a medium wave RFID system, a short wave RFID system, an ultra short wave RFID system, and a microwave RFID system, depending on use frequencies. According to these classifications, various standards have been established and is now preparing.
Accordingly, the RFID technology is a ubiquitous IT based technology that acquires, processes and uses information in real time using the RFID tag attached to the product, thereby realizing high living standard. The RFID technology is considered as a core technology that can expand the information society by distribution innovation and synchronization of real product and product information using barcode. Thus, various researches on the RFID technology are conducted around the world.
In such an RFID system, when the reader queries the tag attached to the product, the tag sends its own identifier in response to the query, thus achieving tag identification. At this point, when only one tag exists in an identification zone of the reader, the tag identification can be simply processed. On the other hand, when a plurality of tags exist, collision occurs because the respective tags respond to the reader at the same time. Largescaled RFID system environment such as distribution has to identify a large quantity of products in real time. Therefore, an anticollision algorithm is essentially required to efficiently identify a plurality of tags. The anticollision algorithm can be classified into a tree based decision algorithm and a slotted Alohabased statistical algorithm.
In recent years, the UHF band is recognized as the most suitable band in the distribution fields. To meet the strong demand of the RFID markets, the standardization for the use of the UHF band is in rapid progress, compared with other bands. “ISO/IEC 180006 type B” that has been already approved as the international standard in August 2004 and “EPCglobal UHF Gen2” that is preparing for adoption of “ISO/IEC 180006 type C” also use the slotted Alohabased anticollision algorithm. In addition, “ISO/IEC 180007” for the band of 433 MHz and “EPC C1” for the band of 13.56 MHz use the slotted Alohabased anticollision algorithm.
A general Aloha scheme transfers data at every transmission request. On the contrary, in the slotted Alohabased anticollision algorithm, a transmission time is divided into several time slots, and the respective tags select arbitrary slots and transfer data. In the RFID system, when the reader transmits information on the number of slots to the tag existing in the zone, the respective tags generate random number and select slots and then respond to the reader by loading information to be transmitted on the slots. At this point, the information on the number of the slots is contained as parameter in the query command. The ID slots having only one information can be identified by the reader. However, the slots having a plurality of information, that is, the slots where collision occurs cannot be identified, and the tags that load information on these slots have to retransmit information at next round or frame. Also, among the slots responding to the reader, the empty slots where any information is not loaded are included. For the efficient tag identification, the number of slots is set such that a ratio occupied by system efficiency, that is, the ID slots of all slots becomes highest. If the number of the slots is excessively large, it results in waste of the slots. If the number of the slots is excessively small, the collision rate between the tags increases. Thus, the number of tags and the set number of slots in the zone determine the system efficiency.
However, unlike the existing wireless communication, the RFID system has a problem that cannot know the number of tags in the zone. Therefore, the estimation of the number of tags in the zone has to take precedence. Also, based on the estimated number of tags, the number of slots has to be set to obtain the highest system efficiency.
SUMMARY OF THE INVENTIONIt is, therefore, an object of the present invention to provide a method for estimating the number of tags in a slotted Alohabased RFID system, which can estimate the number of tags through a new statistical average scheme using the number of slots, the measured number of empty slots, and the measured number of ID slots.
In accordance with an aspect of the present invention, there is provided a method for estimating number of tags in a slotted Alohabased RFID system, the method comprising the steps of: a) setting the number (N) of slots, the measured number (c<sub>0</sub>) of empty slots, and the measured number (c<sub>1</sub>) of ID slots as parameters; and b) estimating the number (n) of the tags by substituting the set values into n=(N−1)/(c<sub>0</sub>/c<sub>1</sub>).
BRIEF DESCRIPTION OF THE DRAWINGSThe above and other objects and features of the present invention will become apparent from the following description of the preferred embodiments given in conjunction with the accompanying drawings, in which:
FIG. 1 is a view of an RFID system in accordance with an embodiment of the present invention;
FIG. 2 is a flowchart illustrating a method for estimating the number of tags in a slotted Alohabased RFID system in accordance with an embodiment of the present invention;
FIG. 3 is a graph illustrating comparison result of the prior art and the present invention in the estimation of the number of tags;
FIG. 4 is a graph illustrating comparison of the set number of slots that can optimize the system efficiency based on the estimated number of tags in FIG. 3;
FIG. 5 is a graph of simulation result of the method for estimating the number of tags in the slotted Alohabased RFID system in accordance with the embodiment of the present invention; and
FIGS. 6A and 6B are graphs simulation results obtained by the method for estimating the number of tags in the slotted Alohabased RFID system in accordance with the embodiment of the present invention.
DETAILED DESCRIPTION OF THE INVENTIONOther objects and aspects of the invention will become apparent from the following description of the embodiments with reference to the accompanying drawings, which is set forth hereinafter.
FIG. 1 is a view of an RFID system in accordance with an embodiment of the present invention.
Referring to FIG. 1, the RFID system includes a tag 120 having unique ID information, and a reader 110 for recognizing the tag and reading the ID information from the recognized tag.
Hereinafter, a method for estimating the number of tags in a slotted Alohabased RFID system in accordance with the preferred embodiments of the present invention will be described in detail. The existing studies on the estimation of the number of tags within a predetermined region will be first described and a new statistical average method will be then described. Moreover, the comparison and simulation results of the present invention and the prior art will be described.
Regarding the existing RFID system, standard and specification, such as “180006 type A”, “EPCglobal Gen 2”, “180007” and “EPC C1”, was proposed. All of them use the slotted Alohabased anticollision algorithm, Icode algorithm, Bitslot algorithm, and so on.
In order to explain a basic concept about the estimation of the number of tags, a general algorithm will be first described.
A reader begins a tag identification process by querying a tag using parameter of “p=<N, R, I>” where “N”, “R” and “I” represent the number of slots, a seed value required for generating random values, and a tag identifier range or an information on whether to participate in tag identification, respectively. At this point, the selected tags within the region generate random values using the value of R. An arbitrary slot is selected within the range of the number of the slots, based on the random value. Then, the tag identifier information of the selected slot is loaded and transferred to the reader. The slot received by the reader may be the empty slot, the ID slot, or the collided slot.
States of the slots in one frame or one round are represented by “c=<c<sub>0</sub>, c<sub>1</sub>, c<sub>k</sub>>”, where c<sub>0</sub>, c<sub>1 </sub>and c<sub>k </sub>represent the number of empty slots, the number of ID slots, and the number of collided slots, respectively. Accordingly, the number of slots within a zone is estimated using the values c.
When “c<sub>0</sub>” occupies most of the slots, the number of the slots must decrease. When “c<sub>k</sub>” occupies most of the slots, the number of the slots must increase. If the number of the tags can be exactly estimated, the number of slots having the highest system efficiency must be newly set, and next frame or next round is started.
Regarding the estimation of the number of tags, an error minimization method is based on Cherbyshev's inequality. That is, all random values are generally distributed around an average expected value. Thus, the estimated value of the number of tags can be calculated using Eq. 1 below.
<maths id="MATHUS00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>e</mi><mi>vd</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mi>N</mi><mo>,</mo><msub><mi>c</mi><mn>0</mn></msub><mo>,</mo><msub><mi>c</mi><mn>1</mn></msub><mo>,</mo><msub><mi>c</mi><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munder><mi>min</mi><mi>n</mi></munder><mo></mo><mrow><mo>(</mo><mtable><mtr><mtd><msubsup><mi>a</mi><mn>0</mn><mrow><mi>N</mi><mo>,</mo><mi>n</mi></mrow></msubsup></mtd></mtr><mtr><mtd><msubsup><mi>a</mi><mn>1</mn><mrow><mi>N</mi><mo>,</mo><mi>n</mi></mrow></msubsup></mtd></mtr><mtr><mtd><msubsup><mi>a</mi><mi>k</mi><mrow><mi>N</mi><mo>,</mo><mi>n</mi></mrow></msubsup></mtd></mtr></mtable><mo>)</mo></mrow></mrow><mo></mo><mrow><mo>(</mo><mtable><mtr><mtd><msub><mi>c</mi><mn>0</mn></msub></mtd></mtr><mtr><mtd><msub><mi>c</mi><mn>1</mn></msub></mtd></mtr><mtr><mtd><msub><mi>c</mi><mi>k</mi></msub></mtd></mtr></mtable><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>Eq</mi><mo>.</mo><mstyle><mspace width="0.8em" height="0.8ex"/></mstyle><mo></mo><mn>1</mn></mrow></mtd></mtr></mtable></math></maths>
In Eq. 1, “N”, “n”, “a<sub>0</sub><sup>N,n</sup>”, “a<sub>1</sub><sup>N,n</sup>”, and “a<sub>k</sub><sup>N,n</sup>” represent the number of slots, the number of tags, the average expected value of c<sub>0</sub>, the average expected value of c<sub>1</sub>, and the average expected value of c<sub>k</sub>. The number of tags is estimated as the value of “n” that minimizes an error between the measured value and the expected value of the slot state.
However, the implementation of this error minimization method is complicated, and the error of the estimated value is determined by how much the measured value is close to the average expected value. Also, the error of the expected value is associated with the range of “n”.
Most of algorithms use a method of estimating a minimum value, which is implemented more simply than the error minimization method. The estimated value of the number of tags can be calculated using Eq. 2 below.<FORM>e<sub>min</sub>(N,c<sub>0</sub>,c<sub>1</sub>,c<sub>k</sub>)=c<sub>1</sub>+2c<sub>k</sub> Eq. 2</FORM>
The collided slots are generated because at least two tags are allocated at the same time. Thus, the estimated number of the tags in Eq. 2 means the minimum value. The method of estimating the minimum value is advantageous to estimate the number of the tags within two times range of the set number of the slots because a very large error occurs when the number of the tags exceeds two times the number of the slots, which is set with the maximum value that can be estimated as shown in Eq. 3 below.<FORM>e<sub>min</sub>(N,c<sub>0</sub>,c<sub>1</sub>,c<sub>k</sub>)=c<sub>1</sub>+2c<sub>k</sub>=2N−2c<sub>0</sub>−c<sub>1</sub>≦2N Eq. 3</FORM>
In the algorithm to which the abovedescribed method is applied, the number of the tags is estimated through multisteps. Also, the tags are efficiently identified by adjusting the number of the slots using a fixed slot increase/decrease method, a proportional slot increase/decrease method, or a log slot increase/decrease method, based on the ratio that “c<sub>0</sub>” or “c<sub>k</sub>” occupies among the entire “c”.
FIG. 2 is a flowchart illustrating a method for estimating the number of tags in the slotted Alohabased RFID system in accordance with an embodiment of the present invention.
Referring to FIG. 2, the number (N) of slots, the measured number (c<sub>0</sub>) of empty slots, and the measured number (c<sub>1</sub>) of ID slots are set in step 201. The number (n) of tags is estimated by inserting the set value into n=(N−1)/(c<sub>0</sub>/c<sub>1</sub>) in step 202.
Hereinafter, the basic mathematic background about the slotted Alohabased anticollision algorithm will be described.
When n number of tags communicates with the reader by using N number of slots, a probability that r number of tags will exist within a single slot follows a binomial distribution and can be expressed as Eq. 4 below.
<maths id="MATHUS00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>B</mi><mrow><mi>n</mi><mo>.</mo><mstyle><mspace width="0.3em" height="0.3ex"/></mstyle><mo></mo><mfrac><mn>1</mn><mi>N</mi></mfrac></mrow></msub><mo></mo><mrow><mo>(</mo><mi>r</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mo>(</mo><mtable><mtr><mtd><mi>n</mi></mtd></mtr><mtr><mtd><mi>r</mi></mtd></mtr></mtable><mo>)</mo></mrow><mo></mo><msup><mrow><mo>(</mo><mfrac><mn>1</mn><mi>N</mi></mfrac><mo>)</mo></mrow><mi>r</mi></msup><mo></mo><msup><mrow><mo>(</mo><mrow><mn>1</mn><mo></mo><mfrac><mn>1</mn><mi>N</mi></mfrac></mrow><mo>)</mo></mrow><mrow><mi>n</mi><mo></mo><mi>r</mi></mrow></msup></mrow></mrow></mtd><mtd><mrow><mi>Eq</mi><mo>.</mo><mstyle><mspace width="0.8em" height="0.8ex"/></mstyle><mo></mo><mn>4</mn></mrow></mtd></mtr></mtable></math></maths>
Therefore, the average number of tags that can be read during one frame or round can be expressed as Eq. 5 below and the average number of empty slots can be expressed as Eq. 6 below.
<maths id="MATHUS00003" num="00003"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>a</mi><mn>1</mn><mrow><mi>N</mi><mo>,</mo><mi>n</mi></mrow></msubsup><mo>=</mo><mrow><mrow><mi>N</mi><mo>·</mo><mrow><msub><mi>B</mi><mrow><mi>n</mi><mo>.</mo><mfrac><mn>1</mn><mi>N</mi></mfrac></mrow></msub><mo></mo><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mrow></mrow><mo>=</mo><msup><mrow><mi>n</mi><mo></mo><mrow><mo>(</mo><mrow><mn>1</mn><mo></mo><mfrac><mn>1</mn><mi>N</mi></mfrac></mrow><mo>)</mo></mrow></mrow><mrow><mi>n</mi><mo></mo><mn>1</mn></mrow></msup></mrow></mrow></mtd><mtd><mrow><mi>Eq</mi><mo>.</mo><mstyle><mspace width="0.8em" height="0.8ex"/></mstyle><mo></mo><mn>5</mn></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>a</mi><mn>0</mn><mrow><mi>N</mi><mo>,</mo><mi>n</mi></mrow></msubsup><mo>=</mo><mrow><mrow><mi>N</mi><mo>·</mo><mrow><msub><mi>B</mi><mrow><mi>n</mi><mo>.</mo><mfrac><mn>1</mn><mi>N</mi></mfrac></mrow></msub><mo></mo><mrow><mo>(</mo><mn>0</mn><mo>)</mo></mrow></mrow></mrow><mo>=</mo><msup><mrow><mi>N</mi><mo></mo><mrow><mo>(</mo><mrow><mn>1</mn><mo></mo><mfrac><mn>1</mn><mi>N</mi></mfrac></mrow><mo>)</mo></mrow></mrow><mi>n</mi></msup></mrow></mrow></mtd><mtd><mrow><mi>Eq</mi><mo>.</mo><mstyle><mspace width="0.8em" height="0.8ex"/></mstyle><mo></mo><mn>6</mn></mrow></mtd></mtr></mtable></math></maths>
If Eq. 6 is divided by Eq. 5, the result is given by Eq. 7 below.
<maths id="MATHUS00004" num="00004"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msubsup><mi>a</mi><mn>0</mn><mrow><mi>N</mi><mo>,</mo><mi>n</mi></mrow></msubsup><mo>/</mo><msubsup><mi>a</mi><mn>1</mn><mrow><mi>N</mi><mo>,</mo><mi>n</mi></mrow></msubsup></mrow><mo>=</mo><mrow><mrow><msup><mrow><mi>N</mi><mo></mo><mrow><mo>(</mo><mrow><mn>1</mn><mo></mo><mfrac><mn>1</mn><mi>N</mi></mfrac></mrow><mo>)</mo></mrow></mrow><mi>n</mi></msup><mo>/</mo><msup><mrow><mi>n</mi><mo></mo><mrow><mo>(</mo><mrow><mn>1</mn><mo></mo><mfrac><mn>1</mn><mi>N</mi></mfrac></mrow><mo>)</mo></mrow></mrow><mrow><mi>n</mi><mo></mo><mn>1</mn></mrow></msup></mrow><mo>=</mo><mrow><mi>n</mi><mo></mo><mrow><mo>(</mo><mrow><mi>N</mi><mo></mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>Eq</mi><mo>.</mo><mstyle><mspace width="0.8em" height="0.8ex"/></mstyle><mo></mo><mn>7</mn></mrow></mtd></mtr></mtable></math></maths>
Eq. 7 can be rewritten as follows.<FORM>n=(N−1)/(a<sub>0</sub><sup>N,n</sup>/a<sub>1</sub><sup>N,n</sup>) Eq. 8</FORM>
Therefore, the number of the tags is estimated by substituting the measured values “c<sub>0</sub>” and “c<sub>1</sub>” into Eq. 8, instead of “a<sub>0</sub><sup>N,n</sup>” and “a<sub>1</sub><sup>N,n</sup>”. That is, the number of the tags is estimated using Eq. 9 below.<FORM>n=(N−1)/(c<sub>0</sub>/c<sub>1</sub>) Eq. 9</FORM>
As described in the error minimization method, the error of the estimated value in the proposed statistical average method is determined by how much the measured value is closed to the average expected value. On the other hand, the statistical average method of the present invention has the simple calculation process and can be applied more widely than the method of estimating the minimum value.
In order to verify the performance of the method for estimating the number of tags in the slotted Alohabased RFID system in accordance with the present invention, the comparison and simulation result between the prior art and the present invention will be described below. Specifically, the estimated number of tags, the optimal number of slots calculated using the estimated number of the tags, the states of the slots whose number is four times and eight times the number of the tags with respect to the set number of the slots, and the distribution of the estimated number of the tags will be compared and analyzed through the simulation in comparison with the method of estimating the minimum value.
Parameters set for the simulation are as follows.
The number of tags is 16256 and the number of slots is maximum 256. For example, the number of the slots may be 16, 32, 64, or 128.
FIG. 3 is a graph illustrating the comparison result of the prior art and the present invention in the estimation of the number of tags. In FIG. 3, a reference numeral 301 represents the estimated number (Npe) of the tags 301, which is estimated using the statistical average method of the present invention when the number of the slots is 64, a reference numeral 303 represents the number (Nmin) of the tags, which is estimated using the method of estimating the minimum value, and a reference numeral 302 represents the real number (Nr) of the tags with respect to the increase in the number of the tags.
Referring to FIG. 3, although the error of the estimated value somewhat increases according to the increase in the number of the tags, the estimating method of the present invention obtains the result close to the real number of the tags, compared with the method of estimating the minimum value. Also, according to the method of estimating the minimum value, the error is very large when estimating more than 128 tags, which correspond to two times the set number of the slots.
FIG. 4 is a graph illustrating the comparison of the set number of the slots that can optimize the system efficiency based on the estimated number of the tags in FIG. 3.
It can be seen from FIG. 4 that the estimated number (Npe) of the slots calculated using the estimated number of the tags estimated by the estimating method of the present invention is very close to the number (opt) calculated using the real number of the tags. On the contrary, the number (Nmin) calculated using the number of the tags estimated by the method of estimating the minimum value is set to be smaller than the optimal number (opt) during the period where the number of the tags is 6484 and the period where the number of the tags is more than 142. This means that the estimating method of the present invention improves the system efficiency much more than the method of estimating the minimum value.
FIG. 5 is a graph illustrating the simulation result of the method for estimating the number of tags in the slotted Alohabased RFID system in accordance with the embodiment of the present invention. Specifically, FIG. 5 illustrates the comparison of the number of the empty slots and the number of the ID slots in one frame or round when the number of the tags is four times and eight times the number of the set number of the slots.
It can be seen from FIG. 5 that the average expected value of the empty slot or the ID slot is not “1” when the number of the tags are eight times the number of the slots. That is, when the set number of the slots is ⅛ time the number of the tags, “c<sub>0</sub>” and “c<sub>1</sub>” are “0”.
When the number of the tags is four times the number of the slots, “c<sub>0</sub>” is not “1” until the number of the tags is 128, that is, the number of the slots is 32.). “c<sub>0</sub>” is “1” when the number of the tags is 256, that is, the number of the slots is 64. In this case, the number of the tags cannot be estimated using Eq. 9.
In the statistical average measuring method based on the slot's triple state information “c=<c<sub>0</sub>, c<sub>1</sub>, c<sub>k</sub>>”, when either or both of “c<sub>0</sub>” and “c<sub>1</sub>” becomes close to “0”, the error of the estimated value becomes large or the number of the tags cannot be estimated. On the contrary, when the number of the slots is very larger than the number of the tags, when the number (c<sub>k</sub>) of the collided slots becomes close to “0”. However, because “c<sub>0</sub>” or “c<sub>1</sub>” contains much more information, the estimated number of the tags becomes more correct.
In order to merely estimate the number of the tags while ignoring the system efficiency, more correct result can be obtained by setting the number of the slots to be large. In estimating 16256 tags, the proposed method can correctly estimate the number of the tags in almost all periods when the initial number of the slots is set to 128.
The above results were based on the average expected values, and the measured values have to be used in the real algorithm. Therefore, the error of the estimated value is determined by how much the measured value is close to the average expected value. Moreover, the system efficiency is determined.
FIGS. 6A and 6B are graphs illustrating the simulation results obtained by the method for estimating the number of tags in the slotted Alohabased RFID system in accordance with the present invention. When the number of the tags is 128, the number of the slots is set to 64, 128 and 256. At this point, the number of the tags estimated using the measured values is illustrated in FIGS. 6A and 6B.
As illustrated in FIG. 6A, most of the measured values are distributed around the average expected value of 128, but some of the measured values have a very large error. In addition, when a large number of the slots are selected, the measured values are distributed much more around the average expected value. Some of the measured values having large error can reduce the error with respect to the average expected value very easily by using the method of estimating the minimum value and the states of the slots, as illustrated in FIG. 6B.
As described above, the method for estimating the number of tags in the slotted Alohabased RFID system can improve the system efficiency by efficiently estimating the number of the tags through the anticollision algorithm of the slotted Alohabased RFID system.
The abovedescribed methods in accordance with the present invention can be stored in computerreadable recording media. The computerreadable recording media may include CDROM, RAM, ROM, floppy disk, hard disk, optical magnetic disk, and so on. Since these procedures can be easily carried out by those skilled in the art, a detailed description thereof will be omitted.
The present application contains subject matter related to Korean patent application No. 20050105074, filed in the Korean Intellectual Property Office on Nov. 3, 2005, the entire contents of which is incorporated herein by reference.
While the present invention has been described with respect to certain preferred embodiments, it will be apparent to those skilled in the art that various changes and modifications may be made without departing from the scope of the invention as defined in the following claims.