Location measurement process for radio-frequency badges

• US 20030206115A1
• Filed: 05/01/2002
• Published: 11/06/2003
• Est. Priority Date: 05/01/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Gregory, Krumm, John, Brumitt, Barrett L., Harris, Stephen C.
• Granted Patent: US 6,993,592 B2
• Time in Patent Office: Days
• US Class Current: 340/825.49
• 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: H04L 2012/2841 Wireless
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A process for determining the location of entities carrying transmitters (TXs) that transmit TX ID messages to at least one receiver (RX) connected to a computer, in a network of computers. Each RX sends data messages to its associated computer which includes an identifier identifying the TX transmitting the TX ID message, the signal strength of the received TX ID message, and a RX identifier. Each RX computer generates badge hit messages from each data message, and provides them to a centralized computer of the network. The centralized computer generates a badge hit table having a separate entry for each badge hit message, which has fields including the information received in the badge hit message and a hit time indicating the time the entry was added to the table. The badge hit table data is used to determining the location of the TXs, and so the entities.

Claims

1. A computer-implemented process for determining the location of people and objects carrying radio frequency (RF) transmitters (TXs) that transmit TX ID messages to at least one RF receiver (RX) which is in communication with a computer in a computer network, wherein each RX forwards data received from the TXs to the network, along with a value indicating the signal strength of the received TX message, the process comprising using a computer to perform the following process actions:

each computer associated with a RX generating badge hit messages upon receipt of a data message from the RX and providing the badge hit messages to a centralized computer of the network, wherein each badge hit message includes information received in the data message comprising a transmitter identifier, the signal strength indicator associated with the TX ID message and a receiver identifier that uniquely identifies the particular RX sending the data message;

generating a badge hit table in a badge hit database residing on the centralized computer, wherein the badge hit table has a separate entry derived from each badge hit message received whose fields comprise the information received in the badge hit message and a hit time assigned to the entry indicating the time the entry was added to the badge hit table;

determining the location of each TX transmitting a TX ID message using the badge hit data; and

updating an entity location table of a geometric model database with the location of entities included therein, wherein the entity location table comprises a list of entities and the TX identifier of a TX that is associated with each entity, as well as the location of the entity if known, and wherein said entity is a person, object or a collection of persons and objects and the location of the entity is the location determined for the TX associated with the entity.

2. The process of claim 1, wherein the process action of determining the location of each TX is performed by the badge hit database.

3. The process of claim 1, wherein the geometric model database resides in the centralized computer.

4. The process of claim 1, wherein the geometric model database runs on a computer other than the centralized computer, and wherein entries from the badge hit table are transferred to the computer hosting the geometric model database and the process action of determining the location of each TX is performed by the geometric model database.

5. The process action of claim 1, wherein the process action of determining the location of each TX, comprises the actions of:

screening the entries of the badge hit table to ensure that only entries having a signal strength value equaling or exceeding a prescribed level, and that only one entry per TX transmission, are used to determine the location of a TX whose transmission resulted in the entry; and

determining the location of the TX associated with each of the screened entries having a signal strength value equaling or exceeding the prescribed level and representing the only entry attributable to a TX transmission that is used to determine the TX'"'"'s location, based on a known location of the RX identified in the entry, wherein the known location of a RX is obtained from the geometric model data base which maintains a list of each RX and its location within an environment modeled by the geometric model database.

6. The process action of claim 5, wherein RX is identified in the geometric model data base by said RX identifier.

7. The process action of claim 5, wherein each badge hit message further comprises an identifier identifying the computer sending the badge hit message, and wherein RX is identified in the geometric model database by said computer identifier.

8. The process of claim 5, wherein the process action of screening the entries of the badge hit table, comprises the actions of, for each entry of the badge hit table:

determining whether the signal strength value of the entry exceeds a signal strength threshold; and

whenever the signal strength of the entry equals or exceeds the signal strength threshold, deeming the entry to have passed a thresholding test.

9. The process of claim 8, wherein the signal strength threshold is chosen to correspond to approximately a level that would be expected if the TX associated with an entry was transmitting from about 1 to 2 meters away from the RX that originally measured the signal strength.

10. The process of claim 8, wherein the process action of screening the entries of the badge hit table, comprises the actions of, for each entry passing the thresholding test:

determining if a time table has been established for the TX associated with the entry and if not creating one, wherein said time table logs the hit time of each entry associated with the TX that passes the thresholding test; and

logging the hit time of the entry under consideration in the time table assigned to the TX associated with the entry under consideration.

11. The process of claim 10 wherein the process action of screening the entries of the badge hit table, further comprises the actions of, for each entry passing the thresholding test:

ascertaining whether the respective differences in the hit time of the entry under consideration and each previously logged hit time of the time table assigned to the TX associated with the entry under consideration fall within a prescribed time period;

whenever the differences between the hit time of the entry under consideration and the hit times of all the previous entries in the time table assigned to the TX associated with the entry under consideration fall outside the prescribed time period, deeming the entry under consideration to have cleared a time conflict resolution procedure and ready for further processing to determine the location of the TX; and

whenever the difference between the hit time of the entry under consideration and the hit time of one or more of the previous entries in the time table assigned to the TX associated with the entry under consideration fall within the prescribed time period, assuming these entries are attributable to the same or a redundant TX transmission and selecting just one of them for further processing to determine the location of the TX, wherein the entry selected for further processing is deemed to have cleared the time conflict resolution procedure.

12. The process of claim 11, wherein the prescribed time period is set based on the latency of said network and the rate at which the entries in the badge hit table processed.

13. The process of claim 12, wherein the prescribed period of time is approximately 1 second.

14. The process of claim 11, wherein the process action of selecting just one of the entries for further processing to determine the location of the TX, comprises an action of selecting one of the entries randomly.

15. The process of claim 11, wherein the process action of selecting just one of the entries for further processing to determine the location of the TX, comprises an action of selecting the entry of the group of entries assumed to be attributable to the same or redundant TX transmission that has the earliest hit time.

16. The process of claim 11, wherein the process action of selecting just one of the entries for further processing to determine the location of the TX, comprises an action of using the entry of the set of entries assumed to be attributable to the same or redundant TX transmission that has the most recent hit time for further processing to determine the location of the TX.

17. The process of claim 10, wherein the location determined for each entity is assigned to that entity in an entity location table of a geometric model database, and wherein the process further comprises a process action of screening the entity location table to remove stale location designations.

18. The process of claim 17, wherein the process action of screening the entity location table to remove stale location designations, comprises the actions of, for each time table associated with a TX:

examining the time table to determine if the most recent hit time of the badge hit entries referenced in the table is earlier than a time defined by the time of examination less a prescribed timeout period; and

whenever it is determined that the most recent hit time of the badge hit entries referenced in the table is earlier than the time defined by the time of examination less the prescribed timeout period, deleting any location designation assigned to the entity associated with the TX whose time table is under consideration from said entity location table.

19. The process of claim 5, wherein the process actions of determining the location of the TX associated with each of the screened entries and updating the entity location table of the geometric model database with the location of entities included therein, comprises the actions of, for every screened entry having a signal strength value equaling or exceeding the prescribed level and representing the only entry attributable to a TX transmission that is used to determine the TX'"'"'s location:

determining whether the entity associated with the TX identified in the entry has a location assigned to it in the entity location table of the geometric model database;

whenever a location has not been previously assigned to the entity in the entity location table, assigning a location to the entity corresponding to the known location of the RX identified in the entry and entering the location in the entity location table, wherein the location of the RX is defined in semantic terms in that the location refers to a predefined space in which the RX is located;

whenever a location has been previously assigned to the entity in the entity location table, determining whether the location is the same as the location of the RX; and

whenever it is determined that the location assigned to the entity in the entity location table is not the same as the location of the RX, replacing the location currently assigned to the entity with the location of the RX.

20. The process of claim 5, wherein the process actions of determining the location of the TX associated with each of the screened entries and updating the entity location table of the geometric model database with the location of entities included therein, comprises the actions of, for every screened entry having a signal strength value equaling or exceeding the prescribed level and representing the only entry attributable to a TX transmission that is used to determine the TX'"'"'s location:

determining whether the entity associated with the TX identified in the entry has a location assigned to it in the entity location table of the geometric model database;

whenever a location has not been previously assigned to the entity in the entity location table, assigning a location to the entity defined as being within a prescribed distance from the known location of the RX identified in the entry and entering the location in the entity location table, wherein the location of the RX is characterized in metric terms in that the location is the coordinates at which the RX is located relative to a prescribed coordinate frame;

whenever a location has been previously assigned to the entity in the entity location table, determining whether the entity'"'"'s currently assigned location is within the prescribed distance from the known location of the RX identified in the entry; and

whenever it is determined that the location currently assigned to the entity in the entity location table is not within the prescribed distance from the known location of the RX, replacing the location currently assigned to the entity with a location specifying that the entity is within the prescribed distance from the location of the RX.

21. The process of claim 20, wherein the process action of screening the entries of the badge hit table, comprises the actions of, for each entry of the badge hit table:

determining whether the signal strength value of the entry exceeds a signal strength threshold; and

whenever the signal strength of the entry equals or exceeds the signal strength threshold, deeming the entry to have passed a thresholding test; and

wherein

the signal strength threshold is chosen to correspond to approximately a level that would be expected if the TX associated with an entry was transmitting from a prescribed transmitting distance away from the RX that originally measured the signal strength; and

wherein

the prescribed distance from the known location of the RX that defines the location of the entity corresponds to the prescribed transmitting distance.

22. The process of claim 1, wherein the TX ID messages transmitted by each TX comprise error detection data which is included in the data messages sent by each RX to its associated computer and in the badge hit message sent from each RX-associated computer to the centralized computer, and wherein the error detection data comprises a message count which is incremented each time a TX transmits a TX ID message, and wherein the centralized computer determines whether the message count is one increment above the last previously transmitted TX ID message from that TX, thereby indication whether a previous TX ID message has been lost.

23. The process of claim 1, wherein the TX ID messages transmitted by each TX comprise error detection data which is included in the data messages sent by each RX to its associated computer, and wherein the error detection data comprises a message count which is incremented each time a TX transmits a TX ID message, and wherein the RX-associated computer determines whether the message count is one increment above the last previously transmitted TX ID message from that TX, thereby indication whether a previous TX ID message has been lost.

24. The process of claim 1, wherein the TX ID messages transmitted by each TX comprise error detection data which is included in the data messages sent by each RX to its associated computer, and wherein the error detection data comprises a checksum, and wherein the RX-associated computer determines whether the TX ID message was complete using the checksum.

25. A location tracking system for determining the location of persons and objects using transmitters that transmit TX ID messages to at least one receiver connected to a computing device in a network of computing devices, comprising:

a plurality of radio frequency (RF) transmitters (TXs), each of which is carried by the person, or attached to the object, whose location is to be determined;

at least one RF receiver (RX), each of which receives TX ID messages transmitted by TXs within signal range of the RX, said TX ID messages comprising a transmitter identifier which uniquely identifies the particular TX transmitting the TX ID message, and wherein each RX measures the strength of the signal carrying a TX ID message received from a TX;

at least one computing device, each of which is in communication with a different RX and which receives data messages from the RX which are generated upon receipt of a TX ID message from a TX, wherein the data message comprises the transmitter identifier, a signal strength indicator associated with the TX ID message and a receiver identifier that uniquely identifies the particular RX sending the data message;

a centralized computing device which is in communication with each of the computing devices associated with a RX via said network and which receives badge hit messages each of which represents a version of the forwarded RX data messages with an identifier identifying the computing device forwarding the message appended thereto; and

a computer program comprising program modules executable by the centralized computing device, wherein the computing device is directed by the program modules of the computer program to determine the location of each TX using the data forwarded to it from each computing device associated with a RX.

26. The system of claim 25, wherein the centralized computing device generates a badge hit table in a badge hit database, each entry of which comprises fields for the information received in the badge hit message and a hit time assigned to the entry indicating the time the entry was added to the badge hit table, and updates an entity location table of a geometric model database with the location of entities included therein, wherein the entity location table comprises a list of entities and the TX identifier of a TX that is associated with each entity, as well as the location of the entity if known, said entity being a person, object or a collection of persons and objects, and the location of the entity being the location determined for the TX associated with the entity, and wherein the program module for determining the location of each TX, comprises the sub-modules for:

screening the entries of the badge hit table to ensure that only entries having a signal strength value equaling or exceeding a prescribed level, and that only one entry per TX transmission, are used to determine the location of a TX whose transmission resulted in the entry; and

determining the location of the TX associated with each of the screened entries having a signal strength value equaling or exceeding the prescribed level and representing the only entry attributable to a TX transmission that is used to determine the TX'"'"'s location, based on a known location of the RX identified in the entry, wherein the known location of a RX is obtained from the geometric model data base which maintains a list of each RX and its location within an environment modeled by the geometric model database.

27. The system of claim 26, wherein entries are added to the badge hit table each time a TX transmission is received by a RX, and wherein the sub-module for screening the entries of the badge hit table, comprises sub-modules for:

(a) selecting a previously unselected entry of the badge hit table;

(b) determining whether the signal strength value of the selected entry exceeds a signal strength threshold;

(c) whenever the signal strength of the entry equals or exceeds the signal strength threshold, deeming the entry to have passed a thresholding test; and

(d) for each selected entry passing the thresholding test,

(i) determining if a time table has been established for the TX associated with the entry and if not creating one, wherein said time table logs the hit time of each entry associated with the TX that passes the thresholding test,

(ii) logging the hit time of the entry under consideration in the time table assigned to the TX associated with the entry under consideration,

(iii) determining if a prescribed waiting period has elapsed since the hit time of the selected entry,

(iv) whenever the prescribed waiting period has not yet elapsed, repeating actions (a) through (d)(iii), as appropriate,

(e) whenever it is determined that the prescribed waiting period has elapsed, selecting a previously unselected entry of the badge hit table that passed the thresholding test;

(f) ascertaining whether the respective differences in the hit time of the selected entry and each of the other logged hit times of the time table assigned to the TX associated with the selected entry, fall within a prescribed time period;

(g) whenever the differences between the hit time of the selected entry and the hit times of all the other entries in the time table assigned to the TX associated with the selected entry fall outside the prescribed time period, using the selected entry for further processing to determine the location of the TX, and

(vii) whenever the difference between the hit time of the selected entry and the hit time of any other entry in the time table assigned to the TX associated with the selected entry fall within the prescribed time period, assuming these entries are attributable to the same or a redundant TX transmission and using just the entry having the most recent hit time for further processing to determine the location of the TX.

28. The system of claim 27, wherein the prescribed time period is set based on the latency of said network and the rate at which the entries in the badge hit table processed.

29. The system of claim 28, wherein the prescribed waiting period is made approximately equal to, but not less than, said prescribed time period.

30. The system of claim 26, wherein the data derived from TX transmissions is collected for a prescribed collection period at which time an entry associated with each of said TX transmissions is added to the badge hit table to create a set of entries in the table, and wherein the sub-modules for screening the entries of the badge hit table, comprises sub-modules for:

(a) selecting a previously unselected entry in the set of entries of the badge hit table;

(b) determining whether the signal strength value of the selected entry exceeds a signal strength threshold;

(c) whenever the signal strength of the entry equals or exceeds the signal strength threshold, deeming the entry to have passed a thresholding test; and

(d) for each entry passing the thresholding test,

(i) determining if a time table has been established for the TX associated with the entry and if not creating one, wherein said time table logs the hit time of each entry associated with the TX that passes the thresholding test,

(ii) logging the hit time of the entry under consideration in the time table assigned to the TX associated with the entry under consideration,

(iii) repeating actions (a) through (d)(ii), as appropriate, until all the entries in said set of entries have been selected,

(e) selecting a previously unselected entry of the badge hit table that passed the thresholding test;

(f) ascertaining whether the respective differences in the hit time of the selected entry and each of the any other logged hit times of the time table assigned to the TX associated with the selected entry fall within a prescribed time period,

(g) whenever the differences between the hit time of the selected entry and the hit times of all the other entries in the time table assigned to the TX associated with the selected entry fall outside the prescribed time period, using the selected entry for further processing to determine the location of the TX, and

(h) whenever the difference between the hit time of the selected entry and the hit time of any other entry in the time table assigned to the TX associated with the selected entry fall within the prescribed time period, assuming these entries are attributable to the same or a redundant TX transmission and using just the entry having the most recent hit time for further processing to determine the location of the TX.

31. The system of claim 30, wherein the prescribed time period is set based on the latency of said network and the rate at which the entries in the badge hit table processed.

32. The system of claim 30, wherein the prescribed collection period is begins when a set of entries is added to the badge hit table and lasts for a predetermined period of time.

33. The system of claim 30, wherein the prescribed collection period begins when a set of entries is added to the badge hit table and ends when a predetermined number of TX transmissions are received by the centralized computing device.

34. The system of claim 26, wherein the centralized computer forwards the location of each entity to a separate entity location database each time the entity location table of the geometric model database is updated, said entity location database listing each entity by the name of the person, object or collection thereof, that the entity represents, and the last known location of the entity.

35. A computer-readable medium having computer-executable instructions for determining the location of entities carrying RF transmitters that transmit TX ID messages to at least one receiver connected to a computing device in a network of computing devices from a data table having entries for each TX ID message received comprising fields for a PIN identifying an entity associated with the transmitter responsible for the TX ID message, the signal strength indicator indication the strength of the RF signal carrying the TX ID message, a receiver identifier that identifies the receiver receiving the TX ID message, and a hit time indicating the time the entry was added to the data table, said computer-executable instructions comprising:

screening the entries of the data table to ensure that only entries having a signal strength value equaling or exceeding a prescribed level, and that only one entry per transmission, are used to determine the location of a transmitter whose transmission resulted in the entry; and

determining the location of the transmitter associated with each of the screened entries having a signal strength value equaling or exceeding the prescribed level and representing the only entry attributable to a transmission that is used to determine an entities location, based on a known location of the receiver identified in the entry; and

equating the transmitter'"'"'s location to the entity whose PIN is listed in the entry under consideration.

36. The computer-readable medium of claim 35, wherein the instruction for equating the transmitter'"'"'s location to the entity whose PIN is listed in the entry under consideration, comprises a sub-instruction for updating an entity location table with the location of transmitter that is associated with each entity, wherein the entity location table comprises a list of entities and the PIN that is associated with each entity, as well as the location of the entity if known.

37. The computer-readable medium of claim 36, wherein the instruction for determining the location of the transmitter associated with the entries, comprises sub-instructions for:

determining whether the entity associated with the PIN identified in the entry has a location assigned to it in the entity location table;

whenever a location has not been previously assigned to the entity in the entity location table, assigning a location to the entity corresponding to the known location of the receiver identified in the entry, wherein the location of the receiver is defined in semantic terms in that the location refers to a predefined space in which the receiver is located;

whenever a location has been previously assigned to the entity in the entity location table, determining whether the location is the same as the location of the receiver; and

whenever it is determined that the location assigned to the entity in the entity location table is not the same as the location of the receiver, replacing the location currently assigned to the entity with the location of the receiver.

38. The computer-readable medium of claim 36, wherein the instruction for determining the location of the transmitter associated with the entries, comprises sub-instructions for:

determining whether the entity associated with the PIN identified in the entry has a location assigned to it in the entity location table;

whenever a location has not been previously assigned to the entity in the entity location table, assigning a location to the entity defined as being within a prescribed distance from the known location of the receiver identified in the entry, wherein the location of the receiver is characterized in metric terms in that the location is the coordinates at which the receiver is located relative to a prescribed coordinate frame;

whenever a location has been previously assigned to the entity in the entity location table, determining whether the entity'"'"'s currently assigned location is within the prescribed distance from the known location of the receiver identified in the entry; and

whenever it is determined that the location currently assigned to the entity in the entity location table is not within the prescribed distance from the known location of the receiver, replacing the location currently assigned to the entity with a location specifying that the entity is within the prescribed distance from the location of the receiver.