Clustering methods for radio-frequency-identifier networks

• US 20080136639A1
• Filed: 04/30/2007
• Published: 06/12/2008
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Pradhan, Salil, Mesarina, Malena, Recker, John, Deoalikar, Vinay
• Granted Patent: US 8,149,094 B2
• Time in Patent Office: Days
• US Class Current: 340/572.1
• CPC Class Codes: A01K 11/006 Automatic identification systems for animals, e.g. electronic devices, transponders for animals identification systems for access to feeding pens A01K1/0209; ear tags with electronic identification means A01K11/004
• CPC Class Codes: G06K 7/0008 General problems related to the reading of electronic memory record carriers, independent of its reading method, e.g. power transfer
• CPC Class Codes: G06K 7/10435 the interrogation device being positioned close to a conveyor belt or the like on which moving record carriers are passing conveying in accordance with bodily destination marks, see B65G47/46, sorting of objects carrying identity markings, see B07C5/34

Abstract

Methods and systems of the present invention are directed to clustering RFID-tag readers of a multi-RFID-tag-reader network in order to obtain a set of RFID-tag readers with high probability of detecting an event, but with low probability of collisions and with an acceptable cost. The cost may be determined by any of numerous cost functions of the RFID-tag readers in the set of RFID-tag readers, and may represent a cost in power, long-term reliability, and other such metrics that may be applied to an RFID-tag network.

Claims

1. A method for selecting a subset C of a set SC comprising all multi-RFID-tag-readers in a multi-RFID-tag-reader network, the method comprising:

receiving threshold parameters;

sorting the set SC in descending order of the correlation of each RFID-tag-reader in set SC with an event E;

initializing the set C to contain the RFID-tag-reader of set SC with index start; and

repeatedly

relaxing the threshold parameters,

identifying additional candidate RFID-tag-readers in SC that meet a criterion defined by the threshold parameters,

adding the identified additional candidate RFID-tag-readers to the subset C, and

removing the identified additional candidate RFID-tag-readers from the set SC until a cost computed for subset C exceeds a threshold cost.

2. The method of claim 1 wherein the threshold parameters include a threshold event correlation and a threshold cross correlation.

3. The method of claim 2 wherein the criterion defined by the threshold parameters is that the event correlation for a candidate RFID-tag-reader exceeds, in value, the threshold event correlation and that the cross correlation of the candidate RFID-tag-reader with respect to each RFID-tag-reader in the subset C is less that the cross-correlation threshold.

4. The method of claim 3 wherein the criterion defined by the threshold parameters further includes that the candidate RFID-tag-reader not be assigned to a collision-avoidance partition to which any RFID-tag-reader in the subset C is assigned.

5. The method of claim 4 wherein multiple clusters are obtained by multiple iterations of the method of claim 1, and a subset of these clusters are coalesced to produce a final subset C of RFID-tag readers.

6. The method of claim 1 wherein relaxing the threshold parameters further includes:

decreasing the event-correlation parameter and increasing the cross-correlation parameter.

7. A multi-RFID-tag-reader-network that employs the method of claim 1 to select subsets of the RFID-tag-readers in the multi-RFID-tag-reader-network for predicting or detecting an event.

8. A multi-RFID-tag-reader-network-analysis system that employs the method of claim 1 to select subsets of the RFID-tag-readers in the multi-RFID-tag-reader-network for predicting or detecting an event.

9. A method for selecting a subset C of a set S comprising all multi-RFID-tag-readers in a multi-RFID-tag-reader network with respect to an event E, the method comprising:

computing a cross-correlation matrix R for the RFID-tag-readers in set SC with respect to event E;

computing a diagonalized cross-correlation matrix R′

by;

R′

=TRT<sup>−

1</sup>;

computing a set of virtual scanners by matrix multiplication of T and S;

TS;

sorting the set of virtual scanners by corresponding eigenvalues in R<sup>−

1</sup>; and

truncating the sorted set of virtual scanners to form the subset C.

10. The method of claim 9 wherein each virtual scanner is a set of one or more RFID-tag-readers of the multi-RFID-tag-reader network.

11. The method of claim 10 wherein the sorted set of virtual scanners is truncated by removing those virtual scanners from the list of virtual scanners associated with eigenvalues less than a threshold eigenvalue K.

12. The method of claim 11 further including, following truncation of the sorted set of virtual scanners:

obtaining a set of partitioning constraints by adding to the set of partitioning constraints all pairs of RFID-tag-readers in each virtual scanner within the truncated list of virtual scanners; and

partitioning the set of all unique s RFID-tag-readers within the truncated list of virtual scanners.

13. The method of claim 12 further including selecting, as C, a subset of partitions produced by partitioning the set of all unique RFID-tag-readers within the truncated list of virtual scanners with a cumulative highest correlation with event E and with a cost less than a cost threshold.

14. A multi-RFID-tag-reader-network that employs the method of claim 9 to select subsets of the RFID-tag-readers in the multi-RFID-tag-reader-network for predicting or detecting an event.

15. A multi-RFID-tag-reader-network-analysis system that employs the method of claim 9 to select subsets of the RFID-tag-readers in the multi-RFID-tag-reader-network for predicting or detecting an event.