Proximity detection using wireless signal strengths

• US 7,509,131 B2
• Filed: 06/29/2004
• Issued: 03/24/2009
• Est. Priority Date: 06/29/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Krumm, John C., Hinckley, Kenneth P.
• Primary Examiner(s): Pan; Yuwen
• Application Number:
  US10/880,051
• Publication Number:
  US 20060046709A1
• Time in Patent Office: 1,729 Days
• Field of Search: 4554561- 6, 455517-520, 342/451
• US Class Current: 455/456.1
• CPC Class Codes: H04N 21/4126 The peripheral being portable, e.g. PDAs or mobile phones
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Described is a system and method in a wireless (Wi-Fi) network comprising a server, clients and various mechanisms that compute lists of other clients and resources that are physically nearby. Clients report Wi-Fi access points'"'"' signal strengths to a server, which uses that data to compute the proximity of resources to one another, including an estimate the distance between resources. The data may be returned to the client as a list of resources within short range proximity, or resources within long-range proximity, with an approximate time to that resource based on previous clients'"'"' reporting. Because proximity is used rather than absolute location, only minimal setup is needed. As the number of clients and resources that use the system increases, the server knowledge also increases with respect to the number of resources that can be found and in the physical range over which other people and places can be found.

Claims

1. At a proximity management computer system in a wireless network environment in which signal strengths data can be detected, a method for returning a sorted list of nearby resources of a specified type to a client, the method comprising:

receiving registration data from a user'"'"'s client device in the wireless network environment, the registration data including registration data identifying the user'"'"'s client device and identifying at least one non-networked resource, wherein the non-networked resource includes at least one of a room, a non-electronic device and an electronic device without wireless networking capabilities, the registration data for the non-networked resource being sent on behalf of the non-networked resource, the registration data being configured to include a client device wireless network environment signature for identifying the non-networked device'"'"'s location in relation to the user'"'"'s client device;

generating a globally unique identifier based on the user'"'"'s registration data, such that transmissions from the user are associated with the user, regardless of which client device the user uses;

returning a globally unique identifier to the client device in response to receiving the registration data;

receiving a client device wireless network environment signature from and for the user, the client device wireless network environment signature including a data structure that associates the returned globally unique identifier with a MAC address and a corresponding determined received signal strength indicator for each base station the client device detected within the wireless network environment;

receiving a non-networked resource wireless network environment signature from the user, the non-networked resource wireless network environment signature including a data structure that associates the user'"'"'s globally unique identifier with the corresponding determined received signal strength indicator for each base station the client device detected within the wireless network environment, such that the user'"'"'s client device can report on the non-networked resource'"'"'s behalf;

storing the client device wireless network environment signature and the non-networked resource wireless network environment signature in a database;

receiving a query from the user for a specified type of resource subsequent to storing the client device wireless network environment signature and the non-networked resource wireless network environment signature in the database;

accessing resource wireless network environment signatures and non-networked resource wireless network environment signatures for resources of the specified type from the database, each resource wireless network environment signature associating a globally unique identifier for a resource with a corresponding determined received signal strength indicator for each detected base station associated with the resource;

determining the similarity of each accessed resource wireless network environment signature to both the client device wireless network environment signature and the non-networked resource wireless network environment signature;

generating a list of resources of the specified type of resource in response to the received query, the list of resources sorted by physical distance from the client device, wherein resources having wireless network environment signatures with increased similarity to at least one of the client device wireless network environment signature and the non-networking resource wireless network environment signature are indicated as physically closer to the client device and wherein resources having a wireless network environment signature with reduced similarity to at least one of the client device wireless network environment signature and the non-networking resource wireless network environment signature are indicated as physically further from the client device; and

returning the generated list of resources to the client device to indicate resources of the specified type that are available for use by the client device.

2. The method of claim 1 further comprising, building a database of signal strength data.

3. The method of claim 2 further comprising, determining from the database which base stations can be detected simultaneously with one another.

4. The method of claim 3 further comprising, maintaining a data structure that contains information as to which base stations are adjacent to which other base stations.

5. The method of claim 4 further comprising, providing data to the client device corresponding to how many base stations away the client device is to a resource.

6. The method of claim 2 wherein building the database includes discarding inconsistent information as to at least one base station that has not been previously detected.

7. The method of claim 2 wherein building the database includes discarding inconsistent information as to base stations that are reported as having overlapping coverage but have not been previously detected as having overlapping coverage.

8. The method of claim 1 wherein determining the similarity of each accessed resource wireless network environment signature to the client device wireless network environment signature comprises comparing how many base stations the client device has in common-with each resource.

9. The method of claim 1 wherein determining the similarity of each accessed resource wireless network environment signature to the client device wireless network comprises for each resource ordering base stations seen in common by signal strength values into a first ordering for the client device and a second ordering for the resource, and determining similarity between the first ordering and the second ordering.

10. The method of claim 1 further comprising, selecting numeric features for computing distance, and testing combinations of those features to determine a function that gives the best results with respect to actual distances.

11. The method of claim 1 wherein at least one resource is not connected to the network, and further comprising, using another network device to determine signal strength indicators for the at least one resource.

12. The method of claim 1 wherein the resource comprises a mobile computing device, and further comprising, obtaining a plurality of readings from the resource and returning information corresponding to the approximate distance to the resource based on a latest reading of the plurality.

13. The method of claim 1 wherein the generated list of resources includes short range proximity data for the client device, the short range proximity data corresponding to at least one resource that the client device can communicate with without the communication having to hop between access points.

14. The method of claim 13 further comprising using the short range proximity data to establish that a mobile device is closely associated with another mobile device.

15. The method of claim 13 wherein the short range proximity data is used to present a list of nearby people and things to a user of the client device.

16. The method of claim 1, further comprising tagging a wireless resource with a user-defined tag that includes the wireless resource'"'"'s wireless signature.

17. The method of claim 16, wherein the tag further includes the user'"'"'s GUID.

18. The method of claim 1, further comprising notifying the user when a resource of the specified type is found.

19. The method of claim 1, further comprising:

receiving subsequent registration data from a different client device used by the user; and

assigning the same globally unique identifier to the different client device based on the received subsequent registration data from the user.

20. The method of claim 1, wherein the proximity management computer system generates two lists of resources of the specified type of resource in response to the received query:

a short range proximity list showing those resources of the desired type that have at least one detectable access point in common with the querying client and a long range proximity list showing those resources of the desired type that are reachable by hopping through access points with overlapping coverage.

21. The method of claim 20, wherein the resources found within hopping distance are reported with an estimate indicating the amount of time it would take to travel to the resource.

22. The method of claim 20, wherein determining the similarity of each accessed resource wireless network environment signature comprises determining the physical distance between at least one of the accessed resource and the client device and the accessed resource and the non-networked resource.

23. The method of claim 22, further comprising determining the physical distance by determining at least one of the following:

the number of access points in common between the resources, the Spearman rank-order correlation coefficient which represents how closely the two resources ranked their common access points by signal strength, the sum of squared differences of signal strengths, and the number of access points unaccounted for in each list.

24. At a computer system operating in a wireless network environment, a method for the computer system to obtain a list of nearby resources of a specified resource type, the method comprising:

transmitting registration data to register a user'"'"'s client device with a proximity management computer system, the registration data including registration data identifying the user'"'"'s client device and identifying at least one non-networked resource, wherein the non-networked resource includes at least one of a room, a non-electronic device and an electronic device without wireless networking capabilities, the registration data for the non-networked resource being sent on behalf of the non-networked resource, the registration data being configured to include a client device wireless network environment signature for identifying the non-networked device'"'"'s location in relation to the user'"'"'s client device;

receiving a generated globally unique identifier from the proximity management computer system in response to registering with the proximity management computer system, the globally unique identifier being generated based on the user'"'"'s registration data, such that transmissions from the user are associated with the user, regardless of which client device the user uses;

detecting one or more base stations within the wireless network environment;

for each detected base station included in the one or more base stations;

obtaining a MAC address for the detected base station;

determining a corresponding signal strength indicator for signals received from the detected base station;

creating a wireless network environment signature for the client device from the obtained MAC addresses and corresponding determined signal strength indicators of the detected base stations, the wireless network environment signature including a data structure that associates the generated globally unique identifier with each obtained MAC address and corresponding determined signal strength indicator;

transmitting a non-networked resource wireless network environment signature from the user, the non-networked resource wireless network environment signature including a data structure that associates the user'"'"'s globally unique identifier with the corresponding determined received signal strength indicator for each base station the client device detected within the wireless network environment, such that the user'"'"'s client device can report on the non-networked resource'"'"'s behalf;

reporting the wireless network environment signature and the non-networked resource wireless network environment signature to the proximity management computer system;

submitting a query from the user for a specified type of resource to the proximity management computer system subsequent to reporting the wireless network environment signature; and

receiving a list of resources of the specified type of resource in response to the submitted query, the list of resources sorted by physical distance from the client device, wherein resources having wireless network environment signatures with increased similarity to at least one of the client device wireless network environment signature and the non-networking resource wireless network environment signature are indicated as physically closer to the client device and wherein resources having a wireless network environment signature with reduced similarity to at least one of the client device wireless network environment signature and the non-networking resource wireless network environment signature are indicated as physically further from the client device.

25. A computer system for implementing a method for returning a sorted list of nearby resources of a specified type to a client, the computer system comprising one or more computer-readable storage media having thereon computer-executable instructions that, when executed by one or more processors of the computing system, cause the computing system to perform the method, the method comprising:

receiving registration data from a user'"'"'s client device in the wireless network environment, the registration data including registration data identifying the user'"'"'s client device and identifying at least one non-networked resource, wherein the non-networked resource includes at least one of a room, a non-electronic device and an electronic device without wireless networking capabilities, the registration data for the non-networked resource being sent on behalf of the non-networked resource, the registration data being configured to include a client device wireless network environment signature for identifying the non-networked device'"'"'s location in relation to the user'"'"'s client device;

generating a globally unique identifier based on the user'"'"'s registration data, such that transmissions from the user are associated with the user, regardless of which client device the user uses;

returning a globally unique identifier to the client device in response to receiving the registration data;

receiving a client device wireless network environment signature from and for the user, the client device wireless network environment signature including a data structure that associates the returned globally unique identifier with a MAC address and a corresponding determined received signal strength indicator for each base station the client device detected within the wireless network environment;

receiving a non-networked resource wireless network environment signature from the user, the non-networked resource wireless network environment signature including a data structure that associates the user'"'"'s globally unique identifier with the corresponding determined received signal strength indicator for each base station the client device detected within the wireless network environment, such that the user'"'"'s client device can report on the non-networked resource'"'"'s behalf;

storing the client device wireless network environment signature and the non-networked resource wireless network environment signature in a database;

receiving a query from the user for a specified type of resource subsequent to storing the client device wireless network environment signature and the non-networked resource wireless network environment signature in the database;

accessing resource wireless network environment signatures and non-networked resource wireless network environment signatures for resources of the specified type from the database, each resource wireless network environment signature associating a globally unique identifier for a resource with a corresponding determined received signal strength indicator for each detected base station associated with the resource;

determining the similarity of each accessed resource wireless network environment signature to both the client device wireless network environment signature and the non-networked resource wireless network environment signature;

generating a list of resources of the specified type of resource in response to the received query, the list of resources sorted by physical distance from the client device, wherein resources having wireless network environment signatures with increased similarity to at least one of the client device wireless network environment signature and the non-networking resource wireless network environment signature are indicated as physically closer to the client device and wherein resources having a wireless network environment signature with reduced similarity to at least one of the client device wireless network environment signature and the non-networking resource wireless network environment signature are indicated as physically further from the client device; and

returning the generated list of resources to the client device to indicate resources of the specified type that are available for use by the client device.