Clustering methods for radio-frequency-identifier networks

• US 8,149,094 B2
• Filed: 04/30/2007
• Issued: 04/03/2012
• 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: Deoalikar, Vinay, Recker, John, Mesarina, Malena, Pradhan, Salil
• Primary Examiner(s): Lee, Benjamin C
• Assistant Examiner(s): MEHRAVAR, PETER CYRUS
• Application Number:
  US11/799,146
• Publication Number:
  US 20080136639A1
• Time in Patent Office: 1,800 Days
• Field of Search: 340/10.1, 340/10.2, 340/10.3, 340/10.6, 340/572.1, 340/572.4, 370/370, 238/385
• US Class Current: 340/10.2
• 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 predicting a subset C from a set SC, comprising all multi-RFID-tag-readers in a multi-RFID-tag-reader network, wherein the subset C detects an event E with an increased accuracy in comparison to the set SC, the method comprising:

partitioning the RFID-tag-readers in the set SC for collision avoidance;

receiving threshold parameters including an index start;

sorting the set SC in descending order based on the correlation of each RFID-tag-reader in the set SC with the event E, where the index start is set to one of the multi-RFID-tag-readers of the set SC with a highest correlation with event E;

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

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

repeatedly relaxing the threshold parameters,

adding an identified candidate RFID-tag-reader to the subset C; and

removing the identified candidate RFID-tag-reader 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 identified 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 identified candidate RFID-tag-reader not be assigned to a collision-avoidance partition to which the RFID-tag-readers in the subset C are 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 2 wherein relaxing the threshold parameters further includes:

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

7. The method of claim 1, further comprising successively increasing a numerical value of the start index to create a number of sets of RFID-tag reader clusters, wherein each cluster has a different index start.

13. The method of claim 7, further comprising selecting a cluster from the number of sets of RFID-tag reader clusters that has a highest cumulative correlation coefficient with respect to the event E.

8. A method for predicting a subset C from a set SC, comprising all multi-RFID-tag-readers in a multi-RFID-tag-reader network, wherein the subset C detects the event E with an increased accuracy in comparison to the set SC, the method comprising:

partitioning the RFID-tag-readers in the set SC for collision avoidance;

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

computing a diagonalized cross-correlation matrix R′

by;

R′

=TRT<sup>−

1</sup>, wherein T is a diagonalizing matrix for R;

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

TS, wherein S is a vector of scanners;

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.

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

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

11. The method of claim 10 further including:

producing a set of partitioning constraints by adding pairwise constraints of the RFID-tag-readers in the subset C; and

partitioning the set of RFID-tag-readers within the subset C.

12. The method of claim 11 further including selecting a subset of RFID-tag-readers with a cumulative highest correlation with event E and with a cost less than a cost threshold.