Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
SYSTEMS AND METHODS FOR ESTIMATION OF A POPULATION OF PASSIVE RFID SENSORS
Document Type and Number:
WIPO Patent Application WO/2014/164919
Kind Code:
A1
Abstract:
Systems and methods for providing an estimate of a population of passive Radio Frequency Identification (RFID) sensors in a coverage area of an RFID reader system are disclosed. In accordance with embodiments of this invention, the contention resolutions or results of each slot in an interrogation receive frame are determined. The contention resolutions are then used to determine the probabilities of different population estimates. A population estimate is then selected as the population based on the probability of the estimate meeting predetermined criteria.

Inventors:
SADR RAMIN (US)
Application Number:
PCT/US2014/023797
Publication Date:
October 09, 2014
Filing Date:
March 11, 2014
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
MOJIX INC (US)
International Classes:
H04Q5/22
Foreign References:
US20070126555A12007-06-07
US20080150674A12008-06-26
US20070096877A12007-05-03
US20080074238A12008-03-27
US20090134975A12009-05-28
US20060170534A12006-08-03
Other References:
CABUNAR ET AL.: "Efficient tag detection in RFID systems", J. PARALLEL DISTRIB.COMPUT., vol. 69, 2009, pages 180 - 196, Retrieved from the Internet [retrieved on 20140616]
Attorney, Agent or Firm:
BAILEY, David, J. (2400 E. KatellaSuite 105, Anaheim CA, US)
Download PDF:
Claims:
WHAT IS CLAIMED IS:

1 . A method for estimating a population of Radio Frequency Identification (RFID) sensors in an area based upon responses during an interrogation frame processed by a processing system in a transceiver system receiving the responses comprising:

receiving responses from RFID sensors during a plurality of time slots of a receiving frame;

determining a contention resolution of each of the plurality of time slots; determining a probability state for each of a plurality of population estimates based upon the contention resolution for each of the plurality of time slots;

estimating a probability for each of the plurality of population estimates based on the probability state;

selecting one of the plurality of population estimates as a population based upon the estimated probability of the selected population estimate meeting a predetermined criteria.

2. The method of claim 1 wherein the determining of the probability state comprises:

traversing a state machine using the contention resolutions of the plurality of time slots to determine the probability state wherein the estimating of the probability for each of the plurality probability estimates is calculated based upon the determined state.

3. The method of claim 1 wherein the determining of the probability state is performed by determining an address in a lookup table based upon the contention resolutions of the time slots and the probabilities of each population is read from the determined address in the lookup table.

4. The method of claim 3 further comprising populating the lookup table by determining a probability for each possible state for each of the plurality of slots and storing the probabilities of each possible state for each of the plurality of slots at an address in the lookup table corresponding to a particular state of a slot.

5. The method claim 1 wherein the contention resolution of each of the plurality of slots is selected from one of a singleton response, an empty response, a captured response, and a deleted response wherein a singleton response and a captured response advance the probability state to a next probability state; and the empty response and deleted response cause the probability state to remain in the same state.

6. The method of claim 1 further comprising transmitting an interrogation signal prior to the response frame.

7. The method claim 1 further comprising transmitting an acknowledgement sachet to an RFID sensor in response to a proper decoding of the RFID sensor information from the RFID sensor to prevent transmission in subsequent time slots.

8. The method of claim 1 further comprising determining all the sensors in an area have been interrogated based upon the population estimate.

9. A device for providing an estimate of a population of passive Radio Frequency Identification (RFID) sensors in a coverage area of a RFID reader system comprising:

a memory; and

a processor configured via one or more applications stored in the memory to:

receive responses from RFID sensors during a plurality of time slots of a receiving frame,

determine a contention resolution of each of the plurality of time slots,

determine a probability state for each of a plurality of population estimates based upon the contention resolutions of the plurality of time slots,

estimate a probability for each of the plurality of population estimates based on the probability state for each of the plurality of population estimates, and

select one of the plurality of population estimates as a population based upon the estimated probability of the selected population estimate meeting a predetermined criteria.

10. The device of claim 9 wherein the configuration of the processor to determine the probability state of each of the plurality of population estimates includes configuring the processor to traverse a state machine using the contention resolutions of the plurality of time slots to determine the probability state wherein the estimating of the probabilities for each of the plurality of population estimates is calculated based upon the determined state.

1 1 . The device of claim 9 wherein the configuration of the processor to determine of the probability state is performed by configuring the processor to determine an address in a lookup table based upon the contention resolutions of the time slots and the probabilities of each of the plurality of population estimates is read from the determined address in the lookup table.

12. The device of claim 1 1 wherein the processor is further configured to populate the lookup table by determining a probability for each possible state for each of the plurality of slots and storing the probabilities of each possible state for each slot at an address in the lookup table corresponding to a particular state of a slot.

13. The device of claim 1 wherein the contention resolution of each of the plurality of slots is selected from one of a singleton response, an empty response, a captured response, and a deleted response wherein a singleton response and a captured response advance the probability state to a next probability state; and the empty response and deleted response cause the probability state to remain in the same state.

14. The device of claim 9 wherein the processor is further configured to direct the RFID reader system to transmit an interrogation signal prior to the response frame.

15. The device of claim 9 wherein the processor is further configured to generate an acknowledgement sachet and direct the RFID reader system to transmit the acknowledgement sachet to an RFID sensor in response to a proper decoding of the RFID sensor information from the RFID sensor to prevent transmission in subsequent time slots.

16. The device of claim 9 wherein the processor is further configured to determine that all the sensors in the coverage area of the RFID reader system have been interrogated based upon the population estimate.

17. A machine readable medium containing processor instructions, where execution of the instructions by a processor causes the processor to perform a process for estimating a population of Radio Frequency Identification (RFID) sensors in an area based upon responses during an interrogation frame processed by a processing system in a transceiver system receiving the responses comprising:

receiving responses from RFID sensors during a plurality of time slots of a receiving frame;

determining a contention resolution of each of the plurality of time slots; determining a probability state for each of a plurality of population estimates based upon the contention resolution for each of the plurality of time slots;

estimating a probability for each of the plurality of population estimates based on the probability state;

selecting one of the plurality of population estimates as a population based upon the estimated probability of the selected population estimate meeting a predetermined criteria.

Description:
SYSTEMS AND METHODS FOR ESTIMATION OF A POPULATION OF PASSIVE

RFID SENSORS

FIELD OF THE INVENTION

[0001] This invention relates to the interrogation of Radio Frequency Identification (RFID) sensors in a particular area. More particularly, this invention relates to systems and methods for estimating a number of RFID sensors in an area to be interrogated.

BACKGROUND OF THE INVENTION

[0002] RFID sensors are used for many purposes. One of the most common types of RFID sensors is a passive RFID sensor. A passive RFID sensor includes circuitry that stores a particular encoding; a transceiver module that receives an RF signal from a reader; and circuitry that uses the energy from the received RF signal to power circuitry in the sensor that generates and transmits an RF signal that includes the stored encoding. Passive RFID sensors are popular because of the low cost of the sensor and their durability. In particular, passive RFID sensors do not require replaceable or chargeable batteries since they operate on the energy from the received RF signals.

[0003] One of the most common uses of passive RFID sensors is inventory control. To track items in a store or warehouse, passive RFID sensors with unique encodings are attached to the items in the store or warehouse. RFID readers are then placed throughout the store or warehouse. Each RFID reader periodically interrogates the RFID sensors within the coverage area of the reader to obtain the unique encodings to identify the items in the area. The interrogation is performed by transmitting an interrogation signal and reading the signals from the RFID sensors that are received by the RFID reader in predetermined time slots of a particular interrogation frame. The process is repeated for several frames until information is received from all of the RFID sensors in the coverage area of the reader.

[0004] As items tend to move within the area, it is often difficult to determine whether an RFID reader has captured the information from all of the RFID sensors in its coverage area. Currently, this is often solved by having the RFID reader perform the interrogation for a predetermined number of interrogation frames that assures that a predetermined number of RFID sensors can be interrogated. The predetermined number is often set much higher than the average number of RFID sensors that are commonly in an area to assure information from all of the RFID sensors in the area are received. However, this does not assure that all of the RFID sensors in an area have been identified. Thus, a way of estimating the number of RFID sensors in a particular area is needed to ensure that all of the items in a particular area are identified.

SUMMARY OF THE INVENTION

[0005] The above and other problems are solved and an advance in the art is made by systems and methods of estimating a population of passive RFID sensors in accordance with embodiments of this invention. Embodiments of this invention use the determination of contention resolutions in slots of an interrogation response frame to estimate the population of RFID sensors in the area and provide a certain degree of confidence in the population estimate. For purposes of this discussion, a contention resolution is the result of the signals read from a slot in the interrogation frame. The estimate may then be used to determine whether a predetermined amount of RFID sensors in the area have been identified.

[0006] In accordance with embodiments of this invention, the system receives signals from the RFID sensors during the allotted time slots in an interrogation frame. A contention resolution is then determined for each of the time slots. The contention resolutions of the time slots are then used to determine a probability state. Probabilities for different estimated populations or numbers of RFID sensors in the area are determined based upon the probability state. One of the estimated populations is selected as the population based on the determined probabilities of the estimated populations.

[0007] In accordance with some of these embodiments of the invention, a state machine is traversed using the contention resolutions of the time slots to determine the probability state and the probabilities for each population estimate are calculated based upon the determined probability state. [0008] In accordance with other embodiments of this invention, the determining of the probability state is performed by determining an address in a lookup table based upon the contention resolutions of the time slots. The probability of each estimated population is read from the determined address in the lookup table. In accordance with some of these embodiments, the lookup table is populated by determining a probability for each possible state for the time slots and storing the probabilities of each possible state of each slot at an address in the lookup table corresponding to the particular state of the particular slot.

[0009] In accordance with embodiments of this invention, the contention resolution of each of the slots is a singleton response, an empty response, a captured response, or a deleted response. In accordance with these embodiments, a singleton response and a captured response advance the probability state to a next probability state; and the empty response and deleted response cause the probability state to remain in the same probability state.

[0010] In accordance with some embodiments of this invention, the system transmits an interrogation signal prior to the response frame. In accordance with further embodiments, an acknowledgement sachet is transmitted to an RFID sensor in response to a proper decoding of the RFID sensor information received from the RFID sensor to prevent transmission by the RFID sensor in subsequent time slots. In accordance with some embodiments, the population is then used to determine whether a predetermined threshold of RFID sensors in the area have been interrogated.

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] Figure 1 illustrates a set of RFID passive sensors deployed in an area covered by an RFID reader system having two antennas in accordance with an embodiment of this invention.

[0012] Figure 2 illustrates an RFID reader system such as the RFID reader system show in Figure 1 in accordance with an embodiment of this invention.

[0013] Figure 3 illustrates a state diagram of probability states based upon the contention resolutions of slots in an interrogation frame in accordance with embodiments of this invention. [0014] Figure 4 illustrates a trellis showing the possible probability states for the various slots in an interrogation based on the contention resolutions in accordance with embodiments of this invention.

[0015] Figure 5 illustrates a pruned trellis of the possible probability states for slots in an interrogation frame based upon the possible contention resolutions for each slot in accordance with embodiments of this invention.

[0016] Figure 6 illustrates a conceptual diagram of a system for estimating the population of passive RFID readers in accordance with an embodiment of this invention.

[0017] Figure 7 illustrates a conceptual diagram of an alternative system for estimating the population of passive RFID readers in accordance with an embodiment of this invention.

[0018] Figure 8 illustrating a flow diagram of a process for estimating the population of passive RFID sensors in an area in accordance with embodiments of this invention.

DETAILED DISCLOSURE OF THE INVENTION RFID SYSTEM

[0019] Turning now to the drawings, passive RFID sensors 101 -109 in an area covered by an RFID reader system in accordance with an embodiment of this invention is illustrated in Figure 1 . The RFID reader includes a controller 1 15. The controller 1 15 is a processing system such as a computer system connected to one or more transceivers for communicating with passive RFID sensors to gather data. In the shown embodiment, the controller 1 15 is connected to two RFID transceivers 1 1 1 and 1 12. RFID transceivers 1 1 1 and 1 12 include the necessary circuitry to transmit and receive RF signals for communication with passive RFID sensors. Each RFID transceiver transmits RF signals that illuminate passive RFID sensors in a particular area of coverage to allow the RFID sensors to generate and transmit response RF signals. One skilled in the art will recognize that the area covered by each RFID transceiver is determined by the energy and frequency of the RF signals that can be transmitted. The energy and frequency of the RF signals is constrained by limits imposed by regulatory bodies; and sensor sensitivity thresholds for harvesting energy and transmitting state information to the reader. [0020] As shown in Figure 1 , RFID reader 1 1 1 covers an area that includes RFID sensors 101 , 102, 104, 106 and 109. RFID reader 1 12 covers an area that includes RFID sensors 103, 105, 107, and 108. One skilled in the art will recognize that although two RFID transceivers and nine passive RFID sensors are shown in this embodiment, any number of RFID transceivers and passive RFID sensors may be included in a system without departing from this invention. In order to assure that information from all of the RFID sensors in a coverage area is received during an interrogation process, the RFID reader system needs to ascertain the population of RFID sensors in an area covered by a particular RFID transceiver. Although a system including RFID transceivers is illustrated in FIG. 1 , many embodiments of the invention can utilize a distributed exciter architecture similar to the architectures disclosed in U.S. Patent 8,395,482 entitled "RFID Systems Using Distributed Exciter Network", issued March 12, 2013, the disclosure of which is hereby incorporated by reference in its entirety, including one or more RFID receivers and a network of exciters distributed throughout the read range of the RFID receivers to create discrete interrogation zones.

[0021] A more detailed description of the components of controller 1 15 in accordance with embodiments of this invention is given with reference to Figure 2. The controller 1 15 includes a processor 205, a non-volatile memory 215, and a volatile memory 210. The processor 205 is a processor, microprocessor, controller, or a combination of processors, microprocessor, and/or controllers that performs instructions stored in the volatile memory 210 or non-volatile memory 215 to manipulate data stored in the memory. The non-volatile memory 215 and/or volatile memory 210 can store the processor instructions utilized to configure the device 200 to perform processes including processes in accordance with embodiments of the invention and/or data for the processes being utilized. In other embodiments, the software and/or firmware for providing systems and methods in accordance with this invention can be stored in any of a variety of computer readable media in controller 1 15 that are appropriate to a specific application. [0022] Processor 205 is then connected to RFID transceiver 1 1 1 and 1 12 either directly through an Input/Output (I/O) bus or wireless via transponders connected to the I/O bus. In operation, the processor executes applications that control RFID transceivers to operate at different times to prevent interference between signals and to prevent an RFID sensor from being interrogated by different RFID readers.

OVERVIEW OF SYSTEM AND METHOD FOR ESTIMATING AN RFID POPULATION

[0023] In order to determine the amount of time that a particular RFID transceiver needs to perform the interrogation process to gather data from all of the RFID sensors in the coverage area of the transceivers, controller 1 15 ideally would need to know the exact number of passive RFID sensors in the coverage area or alternatively, needs an estimate the population of passive RFID sensors in the coverage area of each of the transceivers that is accurate to within a certain degree of confidence. In an environment where the RFID sensor may move between coverage areas of various transceivers, it is impossible to know the exact number of sensors in the coverage area at any particular time. This is particularly true in an environment, such as a store or warehouse, where there may be 100s or 1000s of RFID sensors moving about the area at any given time. Thus, a system is needed to estimate the population of the passive RFID sensors with a reasonable degree of certainty so that the controller can determine when data has been collected from substantially all of the passive RFID sensors in an area covered by a transceiver. Systems and methods of estimating the population in an area in accordance with embodiments of this invention provide estimates of populations of passive RFID sensors in coverage areas of the RFID reader system that can be used in determining when an RFID receiver has collected data from substantially all of the RFID sensors in the coverage area of the transceiver. [0024] In accordance with many embodiments of this invention, RFID sensor population estimation is based on the following premises. The first premise is that when a population of RFID sensors respond to an interrogation by a RF transceiver the following contention scenarios or results occur in the time slots of an interrogation receive frame of the transceiver:

1 . Singleton (A s ): a single RFID sensor responds in the slot and information of the sensor is properly decoded;

2. Empty (A e ): an empty slot in which no signal from the RFID sensors is received in the slot;

3. Capture (A c ): multiple RFID sensors respond in a single slot and data from a single sensor is properly decoded; and

4. Deletion (A d ): Multiple sensors respond and data from none of the responding sensors may be decoded.

[0025] In the above contention resolutions, the capture and deletion events result from collisions of signals from transmitting RFID sensors in a time slot. The observation of these contention resolutions over a number of slots, L, during an interrogation receive frame may be used to provide an estimate of the number of sensors in the area.

[0026] In accordance with embodiments of this invention, the contention resolutions of the time slots in the interrogation receiving frame define a set of integers that represent the value of a state of a slot. Each integer, X n , is determined as follows: X n =

Xn-1 + 5, n

where

Ac ~ capture event, As ~ singleton event, Ae ~ empty slot event, Ad ~ deletion event.

[0027] Let N denote the total number of RFID sensors and L is the number of slots in an interrogation frame. Based on the maximum a posteriori probability (MAP) estimation approach which is optimal in "strict sense" for estimating parameter N, an estimate of N, N, may be represented in the following manner:

N = Max N≡{1 Nmax) P L {N \ X 1 ... X L ) where Max N E {1 Νγηαχ is a maximum value of N that is between 1 and some predetermined maximum value;

P L (N I X 1 ... X L ) is confidence in the probability that N is correct based upon the set of integers representing the slots, Xi through X L . The values of each X n being the state value of the X n for each slot based on the contention resolutions observed.

[0028] One skilled in the art will note that in a real-world deployment scenario N is typically bounded by an N M AX in a particular area of coverage for an RFID receiver. A/max in a passive RFID application is typically in a range of about 1 -10 for large assets and may be in a range of 1 -1000 for small tagged items, such as pieces of merchandise in a store. Based on Bayes Rule, the estimate of N, N, can be rewritten as follows: j f _ _ P n (¾ ...¾ | N)P n («)

i — i ri xNs[l....Nmax] D tv v where a discrete stochastic process {X n , n = 1, ... , L ) forms a Markov Chain.

[0029] Hence, the probability of X n based on the chain may be rewritten as follows: [0030] It should be noted that in a general setting that when a RFID sensor responds in a slot and the RFID receiver successfully decodes the data from the sensor, the RFID reader system sends an acknowledgement packet to the RFID sensor to prevent the RFID sensor from transmitting in the remaining time slots of the interrogation receive frame. Thus, the population of active RFID sensors in an area exhibits a time varying behavior from slot to slot depending on the contention resolutions observed in each slot.

[0031] Furthermore, each RFID reader system has a different capture capability. Capture capability may be defined as the ability of a RFID reader system to decode the strongest signal received during a slot despite interference that may be cause the transmission of signals from other sensors and/or other environmental factors. The capture capability of a particular RFID reader system is set as a variable threshold denoted as a.

[0032] To compute each term for P n (Xi ... X2 | N), a theoretical graph denoted (G + R) may be used when the only non-zero probability for traversing from one node in state Si to state S, are P n (S,→SM) and P n (S,→Sj), i.e. P n (S,→S,j=0 except / ' =). There is one-to-one isomorphism between each state S and X n - The probabilities of empty, deletion, singleton and capture contention resolutions for slot n are P e n , P%, P s n , P c n respectively. Hence, the Markov Chain, of Xs can be represented by the state diagram illustrated Figure 3 in accordance with embodiments of this invention.

[0033] In Figure 3, state change 302 shows P n (Si → S i+1 ) which is the probability of changing from state 301 to state 303 and state change 305, P n (5 £ → 5 £ ), shows the probability of remaining in state 303. State changes 302, 304 and 305 are expanded by (P e n , P , P s n , P c n ) to show the probabilities of these state changes. The probabilities of change to another state, such as state changes 302 and 304, are denoted as P n (Si→ S i+1 ) or P n and the probability of a state change remaining in the same state are denoted as P n (5 f → 5 f ) or Q n . One skilled in the art will note that P n = P e n + P% and Q n = P c n + P s n , or = 1 - P n , with P n (X 0 = 0) =1 . [0034] Based on the state diagram shown in Figure 3, a trellis 400, illustrated in Figure 4, generated to show each state that corresponds to a slot / ' of the interrogation receive frame showing a possible state S 1 of slot / ' at times n corresponding to a value of X n defined in the state diagram shown in Figure 3. One skilled in the art will note that any probability for a path in the trellis 400 is given by the following equations:

Prob ( ) = Π[ =1 Π Ρ Λ-

and

0, Otherwise

[0035] The probabilities of each of the contentions resolutions causing a change state are then as follows. The probability of an empty contention resolution pn = (1 _ i .

The probability of a singleton contention resolution is: pn =

The probability of a capture contention resolution is:

Probability of a deletion contention resolution is: [0036] As stated above, each interrogation response frame has L slots. In each of the L slots in the frame, the RFID reader system can detect one of the four contention resolutions namely Ac, As, Ae, or Ad. Each contention resolution corresponds to a transition for traversing the trellis illustrated Figure 4. Ac and As represent a state change of 5 £ →5 £ + 1 ; and Ae, and Ad represent the state change 5 £ → 5 £ . The probability of the state P n (5 £ ) is computed by multiplying P n (Si - i ) with Q n and P n via equations given above.

[0037] This operation is repeated for each value of NE {0, N MAX } in the first frame and NE {0, ... ,Np} where Np denotes the estimate of N from the previous frame. The maximum probability path is then selected. Subsequently, N is found in the equation,

N = ma½ E[1 Nmax Ρη(¾ "'¾ | N)P " (W) , by imposing an additional constraint of P 2 (N)

(which may be chosen if one does not assume uniformly probable distribution of N) that may be a typical choice to provide a binomial distribution. This assumes apriori knowledge of mean and variance of distribution of N. For example μ=Ν τηαχ , σ 2 ρ (1 _ p) may be assumed where p can be chosen by the user as desired for the particular use case. Otherwise, one can assume a uniform distribution and simply use the equation N= Max n P n (X 1 ... X 2 I N) whereby the maximization is taken over the trellis for N=Max ~1 P n (S L ). Based on the above, a fully pruned trellis 400 for the case of 16-slots in accordance with embodiments of this invention is shown in Figure 4. The portion of feasible solutions of the trellis 400 in accordance with embodiments of this invention is shown in Figure 5. One skilled in the art will note that the upper half portion of a node in the trellis 400 are unfeasible, as shown in Figure 5, by definition in by the equation:

Xn= Xn-1 + 5 n where

SYSTEMS FOR ESTIMATING POPULATION OF PASSIVE RFID SENSORS

[0038] Based on the above, a first system in accordance with some embodiments of this invention is provided in the following manner. All realizable paths in a trellis of possible nodes based upon the number of slots are pre-computed. The paths of the trellis are then stored in memory. During runtime, a vector including the contention resolutions of the slots (A c , A s , A d , A e ) is used by an address generator to output the terminal node of the path corresponding to N. The probability of N may be determined for the node based upon the determined path. A conceptual diagram of a system in accordance with these embodiments is shown in Figure 6.

[0039] System 600 includes module 605 that pre-computes all of the possible paths of a trellis of the nodes for the number of slots, L, in the each interrogation receive frame. These paths are stored in a memory, such as, but not limited to Random Access Memory 610. Address generator 615 then receives the string of contention resolutions observed during the L slots of an interrogation receive frame and uses the contention resolutions to determine the proper address of the node in the trellis for the probability determination for each N from 1 to A or N.

[0040] In accordance with these embodiments, a process performed by a processing system in either the controller or the transceiver based upon instructions stored in the system estimates the population in accordance with the flow diagram illustrated in Figure 7.

[0041] Process 700 includes transmitting an interrogation signal from the RFID reader system to illuminate RFID sensors in the coverage area of the transceiver (705). The RFID reader system then receives RF signals from the RFID sensors during an interrogation receive frame (710). The frame is divided into L time slots. The contention resolution for each time slot is determined from the signals received in each time slot (715). The contention resolutions are then used to determine the probability node for each of the possible population estimates (1 to N max †or the first frame or 1 to N of the last frame for subsequent frames) (720). Based upon the determined probability nodes for each of the possible population estimates, the probability of each of the population estimates is calculated (730). The population estimate that has a probability that meets a predetermined criterion is then selected as the population of the sensors (735). The predetermined criterion may include any number of parameters including, but not limited to, the population estimate having the highest probability. One skilled in the art will note that the selected population and probability associated with the selected probability may then be used for any number of functions including as criteria in determining when to the interrogation process with a RFID reader system is complete.

[0042] As one skilled in the art will appreciate, N may be bounded by a maximum number such as, a thousand tags, and therefore it is feasible to compute the ensemble trellis for all N in the subspace of the sample space of size L N . This approach alleviates the need to compute probabilities for each path in the trellis bank at runtime if computational bandwidth is limited in the reader architecture. A conceptual drawing of a system in accordance with embodiments using this approach is illustrated in Figure 8. In system 800, a number of trellises 801 -802, L, or one trellis for each of the slots in the interrogation frame are stored in a memory. The contention resolutions are then used to traverse each trellis to find the probability of the estimated population. This may be performed by storing the probabilities of each node in each trellis at an address in a lookup table and then using the contention resolutions of the slots in the interrogation frame to determine the proper node and find the address in the lookup table for the node. The probability of the node is then read from the lookup table. The estimated population with the greatest probability is then selected by module 805.

[0043] While the above description contains many specific embodiments of the invention, these should not be construed as limitations on the scope of the invention, but rather as an example of embodiments thereof. Accordingly, the scope of the invention should be determined not by the embodiments illustrated, but by the appended claims and their equivalents.