Location measurement process for radio-frequency badges

• US 7,293,104 B2
• Filed: 11/04/2005
• Issued: 11/06/2007
• Est. Priority Date: 05/01/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Gregory, Krumm, John, Brumitt, Barrett, Harris, Stephen
• Primary Examiner(s): Cardone; Jason
• Assistant Examiner(s): Bhatia; Ajay M
• Application Number:
  US11/267,751
• Publication Number:
  US 20060265447A1
• Time in Patent Office: 732 Days
• Field of Search: 709/236, 342/450
• US Class Current: 709/236
• 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:

for each computer associated with a RX performing, a badge hit message generating step for 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;

a badge hit table generating step for 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;

a location determining step for determining the location of each TX transmitting a TX ID message using the badge hit data, said determining step comprising,

a screening step 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, said screening step comprising performing, for each entry of the badge hit table,

a signal strength determining step for 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, performing,

a first deeming step for deeming the entry to have passed a thresholding test,

a time table establishing step for 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,

a logging step for logging the hit time of the entry under consideration in the time table assigned to the TX associated with the entry under consideration,

an ascertaining step for 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, performing a second deeming step for 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, performing a selecting step for 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, and

a determining step for 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; and

an updating step for 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 selecting step comprises selecting one of the entries randomly.

3. The process of claim 1, wherein the selecting step comprises 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.

4. The process of claim 1, wherein the selecting step comprises 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.

5. A computer-readable storage medium having computer-executable instructions for performing the process steps recited in claim 1.

6. 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:

for each computer associated with a RX performing a badge hit message generating step for 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;

a badge hit table generating step for 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;

a location determining step for determining the location of each TX transmitting a TX ID message using the badge hit data, said determining step comprising,

a screening step 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

a first determining step for 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; and

an updating step for 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, and wherein said updating step comprises 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,

a second determining step for 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, performing an assigning step for 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, performing a third determining step for 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, performing a replacing step for replacing the location currently assigned to the entity with the location of the RX.

7. A computer-readable storage medium having computer-executable instructions for performing the process steps recited in claim 6.

8. 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:

each computer associated with a RX performing, a badge hit message generating step for 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;

a badge hit table generating step for 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;

a location determining step for determining the location of each TX transmitting a TX ID message using the badge hit data, said determining step comprising,

a screening step 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

a first determining step for 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; and

an updating step for 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, and wherein said updating step comprises performing 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,

a second determining step for 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, performing an assigning step for 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, performing a third determining step for 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, performing a replacing step for 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.

9. The process of claim 8, wherein the screening step comprises, for each entry of the badge hit table, performing:

a fourth determining step for 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, performing a deeming step for 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.

10. A computer-readable storage medium having computer-executable instructions for performing the process steps recited in claim 8.