Dividing tagged items into subsets

• US 9,659,194 B2
• Filed: 12/17/2008
• Issued: 05/23/2017
• Est. Priority Date: 12/20/2007
• Status: Active Grant

• Current Assignee: Kyndryl Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Picon, Joaquin, Bauchot, Frederic, Clement, Jean-Yves, Marmigere, Gerard
• Primary Examiner(s): YANG, JAMES J
• Application Number:
  US12/336,594
• Publication Number:
  US 20090160622A1
• Time in Patent Office: 3,079 Days
• Field of Search: 340 11, 340 101- 106, 3405721-5729, 235375-385
• CPC Class Codes: G06K 17/0029 the arrangement being specially adapted for wireless interrogation of grouped or bundled articles tagged with wireless record carriers
• 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/10079 the collision being resolved in the spatial domain, e.g. temporary shields for blindfolding the interrogator in specific directions
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: H04Q 2213/13095 PIN / Access code, authentication
• CPC Class Codes: H04Q 2213/13098 Mobile subscriber

Abstract

A method and system for dividing a set of tagged items into subsets. Each tagged item is tagged with a passive RFID tag. A RFID reader is instructed to poll the RFID tags of all tagged items in a specified region having fixed boundaries to generate information including, for each tagged item, a spatial location of each tagged item and a list of all other tagged items in the region which are adjacent to each tagged item. The region is split into non-overlapping subregions. For each subregion, a central tagged item having more adjacent tagged items in each subregion than any other tagged item in each subregion is determined, utilizing the generated information. A virtual boundary is outlined around the central tagged item to enclose the central tagged item and a portion of the tagged items in each subregion which are adjacent to the central tagged item.

Claims

1. A method for dividing a set of tagged items into subsets, each tagged item being tagged with a passive Radio Frequency Identification (RFID) tag, said method comprising:

instructing, by a processor of a computer system, a RFID reader to poll the RFID tags of all tagged items in a specified region having fixed boundaries to generate information comprising, for each tagged item in the region, a spatial location of each tagged item and a list of all other tagged items in the region which are adjacent to each tagged item by being within a specified constant distance (Rlimit) from each tagged item, said region being entirely within a communication range (Rrange) of the RFID reader;

said processor splitting the region into a plurality of non-overlapping subregions such that the region consists of the non-overlapping subregions collectively;

said processor determining which tagged item in each subregion is a centered tagged item, said determining which tagged item in each subregion is the centered tagged item comprising utilizing the generated information to determine that the centered tagged item in each subregion has more adjacent tagged items in the subregion containing the centered tagged item than does each other tagged item in the subregion containing the centered tagged item, wherein said utilizing the generated information to determine each centered tagged item comprises utilizing the spatial location of each tagged item in the subregion containing the centered tagged item and the list of all other tagged items in the subregion containing the centered tagged item which are adjacent to each tagged item in the subregion containing the centered tagged item by being within the specified constant distance (Rlimit) from each tagged item in the subregion containing the centered tagged item;

said processor selecting the centered tagged item in each subregion as a central tagged item for each subregion; and

said processor outlining a virtual boundary around the central tagged item to enclose the central tagged item and a portion of the tagged items in each subregion which are adjacent to the central tagged item by being within the specified constant distance (Rlimit) of the central tagged item, said virtual boundary defining a subset of the set of tagged items for each subregion as comprising the central tagged item and all other tagged items within the virtual boundary, wherein the portion of the tagged items in each subregion consists of all, or less than all, tagged items which are adjacent to the central tagged item in each subregion.

2. The method of claim 1, wherein the portion of the tagged items in each subregion consist of all tagged items which are adjacent to the central tagged item in each subregion.

3. The method of claim 1, wherein the portion of the tagged items in a first subregion of the plurality of subregions consist of less than all tagged items which are adjacent to the central tagged item in the first subregion.

4. The method of claim 3, wherein the first subregion comprises an outer tagged item that is not within the virtual boundary and is not adjacent to the central tagged item in the first subregion, and wherein the method further comprises:

determining a first distance between the outer tagged item and the virtual boundary;

ascertaining that the first distance exceeds a specified threshold distance;

responsive to said ascertaining, creating a new subset of the set of tagged items and designating the outer tagged item a central tagged item of the new subset.

5. The method of claim 3, wherein the first subregion comprises an outer tagged item that is not within the virtual boundary and is not adjacent to the central tagged item in the first subregion, and wherein the method further comprises:

determining a first distance between the outer tagged item and the virtual boundary;

ascertaining that the first distance does not exceed a specified threshold distance;

responsive to said ascertaining, adding the outer tagged item to the subset defined by the virtual boundary in the first subregion.

6. The method of claim 1, wherein the method comprises:

said RFID reader polling the RFID tags of all tagged items in the region, wherein said polling comprises sending an identification request to the RFID tags of each tagged item in the region, and wherein the identification request comprises an identifier of the RFID tag to which each identification request is sent, a distance between the RFID reader and the RFID tag to which each identification request is sent, and the specified constant distance (Rlimit).

7. The method of claim 6, wherein the said polling comprises the RFID reader transmitting a polling command addressed to a passive RFID tag B in the region, and wherein the method further comprises:

a passive RFID tag A receiving the polling command previously transmitted from the RFID reader and addressed to the passive RFID tag B;

said RFID tag A determining that the polling command is not addressed to the RFID tag A;

in response to the RFID tag A determining that the polling command is not addressed to the RFID tag A, at a time t1 said RFID tag A switching the RFID tag A to a catching mode configured to catch echos from other tags;

said RFID tag A receiving at a time t3 an echo of a message sent by the RFID tag B to the RFID reader in response to the polling command received by the RFID tag B at a time t2, wherein the echo comprises an identification of the RFID tag B, and wherein t3>

t2>

t1;

said RFID tag A determining a distance (D.t2t) between the RFID tag A and the RFID tag B based on a total timing (TT) equal to t3 minus t1;

said RFID tag A ascertaining that the distance D.t2t does not exceed a radius limit consisting of the specified constant distance (Rlimit); and

responsive to said ascertaining, said RFID tag storing the identification of the RFID tag B and the distance D.t2t in a database within the RFID tag A.

8. The method of claim 7, wherein the method further comprises:

at a time later than the time t3, said RFID tag A sending an identification message to the RFID reader, wherein the identification message includes an identifier of the RFID tag A, a distance between the RFID tag A and the RFID reader, the radius limit, the identification of the RFID tag B, and the distance D.t2t.

9. The method of claim 7, wherein said determining the distance D.t2t comprises determining D.t2t according to:

D.t2t=(TT−

Ttrig−

TE.r2t.tagB−

TE.r2t.tagA)*C

wherein Ttrig is a specified delay that is not less than a sum of a tag access time for reading the polling command and a granted time for processing the polling command, wherein TE.r2t.tagA is a time for the polling command to be transmitted from the RFID reader to the RFID tag A, wherein TE.r2t.tagB is a time for the polling command to be transmitted from the RFID reader to the RFID tag B, wherein the polling command comprises TE.r2t.tagB, and wherein C is the speed of light.

10. A computer program product comprising a computer readable tangible storage device having a computer readable program code embodied in the device, said program code configured to be executed on a processor of a computer system to perform a method for dividing a set of tagged items into subsets, each tagged item being tagged with a passive Radio Frequency Identification (RFID) tag, said method comprising:

said processor instructing a RFID reader to poll the RFID tags of all tagged items in a specified region having fixed boundaries to generate information comprising, for each tagged item in the region, a spatial location of each tagged item and a list of all other tagged items in the region which are adjacent to each tagged item by being within a specified constant distance (Rlimit) from each tagged item, said region being entirely within a communication range (Rrange) of the RFID reader;

said processor splitting the region into a plurality of non-overlapping subregions such that the region consists of the non-overlapping subregions collectively;

said processor determining which tagged item in each subregion is a centered tagged item, said determining which tagged item in each subregion is the centered tagged item comprising utilizing the generated information to determine that the centered tagged item in each subregion has more adjacent tagged items in the subregion containing the centered tagged item than does each other tagged item in the subregion containing the centered tagged item, wherein said utilizing the generated information to determine each centered tagged item comprises utilizing the spatial location of each tagged item in the subregion containing the centered tagged item and the list of all other tagged items in the subregion containing the centered tagged item which are adjacent to each tagged item in the subregion containing the centered tagged item by being within the specified constant distance (Rlimit) from each tagged item in the subregion containing the centered tagged item;

said processor selecting the centered tagged item in each subregion as a central tagged item for each subregion; and

said processor outlining a virtual boundary around the central tagged item to enclose the central tagged item and a portion of the tagged items in each subregion which are adjacent to the central tagged item by being within the specified constant distance (Rlimit) of the central tagged item, said virtual boundary defining a subset of the set of tagged items for each subregion as comprising the central tagged item and all other tagged items within the virtual boundary, wherein the portion of the tagged items in each subregion consists of all, or less than all, tagged items which are adjacent to the central tagged item in each subregion.

11. The computer program product of claim 10, wherein the portion of the tagged items in each subregion consist of all tagged items which are adjacent to the central tagged item in each subregion.

12. The computer program product of claim 10, wherein the portion of the tagged items in a first subregion of the plurality of subregions consist of less than all tagged items which are adjacent to the central tagged item in the first subregion.

13. The computer program product of claim 12, wherein the first subregion comprises an outer tagged item that is not within the virtual boundary and is not adjacent to the central tagged item in the first subregion, and wherein the method further comprises:

determining a first distance between the outer tagged item and the virtual boundary;

ascertaining that the first distance exceeds a specified threshold distance;

responsive to said ascertaining, creating a new subset of the set of tagged items and designating the outer tagged item a central tagged item of the new subset.

14. The computer program product of claim 12, wherein the first subregion comprises an outer tagged item that is not within the virtual boundary and is not adjacent to the central tagged item in the first subregion, and wherein the method further comprises:

determining a first distance between the outer tagged item and the virtual boundary;

ascertaining that the first distance does not exceed a specified threshold distance;

responsive to said ascertaining, adding the outer tagged item to the subset defined by the virtual boundary in the first subregion.

15. The computer program product of claim 10, wherein the method comprises:

said RFID reader polling the RFID tags of all tagged items in the region, wherein said polling comprises sending an identification request to the RFID tags of each tagged item in the region, and wherein the identification request comprises an identifier of the RFID tag to which each identification request is sent, a distance between the RFID reader and the RFID tag to which each identification request is sent, and the specified constant distance (Rlimit).

16. A system for dividing a set of tagged items into subsets, each tagged item being tagged with a passive Radio Frequency Identification (RFID) tag, said system comprising:

means for instructing a RFID reader to poll the RFID tags of all tagged items in a specified region having fixed boundaries to generate information comprising, for each tagged item in the region, a spatial location of each tagged item and a list of all other tagged items in the region which are adjacent to each tagged item by being within a specified constant distance (Rlimit) from each tagged item, said region being entirely within a communication range (Rrange) of the RFID reader;

means for splitting the region into a plurality of non-overlapping subregions such that the region consists of the non-overlapping subregions collectively;

means for determining which tagged item in each subregion is a centered tagged item, said determining which tagged item in each subregion is the centered tagged item comprising utilizing the generated information to determine that the centered tagged item in each subregion has more adjacent tagged items in the subregion containing the centered tagged item than does each other tagged item in the subregion containing the centered tagged item, wherein said utilizing the generated information to determine each centered tagged item comprises utilizing the spatial location of each tagged item in the subregion containing the centered tagged item and the list of all other tagged items in the subregion containing the centered tagged item which are adjacent to each tagged item in the subregion containing the centered tagged item by being within the specified constant distance (Rlimit) from each tagged item in the subregion containing the centered tagged item;

means for selecting the centered tagged item in each subregion as a central tagged item for each subregion; and

means for outlining a virtual boundary around the central tagged item to enclose the central tagged item and a portion of the tagged items in each subregion which are adjacent to the central tagged item by being within the specified constant distance (Rlimit) of the central tagged item, said virtual boundary defining a subset of the set of tagged items for each subregion as comprising the central tagged item and all other tagged items within the virtual boundary, wherein the portion of the tagged items in each subregion consists of all, or less than all, tagged items which are adjacent to the central tagged item in each subregion.

17. The system of claim 16, wherein the portion of the tagged items in each subregion consist of all tagged items which are adjacent to the central tagged item in each subregion.

18. The system of claim 16, wherein the portion of the tagged items in a first subregion of the plurality of subregions consist of less than all tagged items which are adjacent to the central tagged item in the first subregion.

19. The system of claim 18, wherein the first subregion comprises an outer tagged item that is not within the virtual boundary and is not adjacent to the central tagged item in the first subregion, and wherein the method further comprises:

means for determining a first distance between the outer tagged item and the virtual boundary;

means for ascertaining that the first distance exceeds a specified threshold distance;

means for creating a new subset of the set of tagged items and designating the outer tagged item a central tagged item of the new subset, in response to said ascertaining.

20. The system of claim 18, wherein the first subregion comprises an outer tagged item that is not within the virtual boundary and is not adjacent to the central tagged item in the first subregion, and wherein the method further comprises:

means for determining a first distance between the outer tagged item and the virtual boundary;

means for ascertaining that the first distance does not exceed a specified threshold distance;

means for adding the outer tagged item to the subset defined by the virtual boundary in the first subregion, in response to said ascertaining.