Method and apparatus for constructing a user-generated geographical system

• US 9,198,154 B2
• Filed: 12/10/2010
• Issued: 11/24/2015
• Est. Priority Date: 12/10/2009
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology, Nokia Corporation
• Original Assignee: Massachusetts Institute of Technology, Nokia Corporation
• Inventors: Ledlie, Jonathan, Hicks, Jamey, Minkov, Einat, Park, Jun-geun, Curtis, Dorothy W., Charrow, Benjamin, Teller, Seth J., Battat, Jonathan
• Primary Examiner(s): Mitchell, Nathan
• Assistant Examiner(s): DONADO, FRANK E
• Application Number:
  US12/965,762
• Publication Number:
  US 20110306354A1
• Time in Patent Office: 1,810 Days
• US Class Current: 1/1
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A method and apparatus are provided to permit location discovery, including location discovery in indoor settings. The method may identify a wireless fingerprint present at a geographical location and determine whether the wireless fingerprint corresponds to a previously observed wireless fingerprint associated with the predefined geographical location. A new wireless fingerprint and a geographical location, or bind, may be received by the system and the system may evaluate whether or not the new bind is erroneous or not, or if the new bind is an improvement over existing binds in determining whether or not to accept the new bind.

Claims

1. A method comprising:

receiving a new bound space that comprises an observed wireless fingerprint at a mobile apparatus and a corresponding geographical location for a given bound space;

determining whether to at least one of accept and decline the new bound space based upon the observed wireless fingerprint compared to previously measured wireless fingerprints and locations;

analyzing an average signal distance between the geographical location and a plurality of nearest neighbors that comprise existing bound spaces stored in a database wherein, when accepting the new bound space to a fingerprint of a current bound space for the mobile apparatus, an increase in the average signal distance improves the accuracy of the existing bound spaces stored in the database;

accepting the new bound space to the fingerprint of the current bound space for the mobile apparatus in an instance in which adding the new bind to the database increases the current average signal distance between the geographical location and the plurality of nearest neighbors that comprise existing bound spaces stored in the database;

declining the new bound space from the fingerprint of the current bound space for the mobile apparatus in an instance in which adding the new bind to the database decreases the current average signal distance between the geographical location and the plurality of nearest neighbors that comprise existing bound spaces stored in the database;

and failing to associate the new bind with the geographic location in response to declining the new bound space.

2. A method according to claim 1, wherein determining whether to at least one of accept and decline the new bound space comprises:

accepting the new bind in an instance in which the new bound space is the only bound space corresponding to the geographic location.

3. A method according to claim 1, wherein determining whether to at least one of accept and decline the new bind comprises:

hierarchical clustering to group the new bound space with existing bound spaces that correspond to the geographical location; and

accepting the new bound space if it is in the cluster whose sum of signal distance to neighbor locations is shortest in response to more than one cluster resulting from the hierarchical clustering.

4. A method according to claim 1, wherein determining whether to at least one of accept and decline the new bound space comprises:

determining wireless fingerprints from a plurality of spaces that neighbor the geographical location;

determining if the wireless fingerprints from the majority of the plurality of spaces that neighbor the geographical location match the wireless fingerprint of the new bound space; and

accepting the new bound space in response to the wireless fingerprints from the majority of the plurality of spaces that neighbor the geographical location matching the wireless fingerprint of the new bound space.

5. A method according to claim 1, wherein associating the new bound space with the geographic location comprises updating a Voronoi diagram such that any geographical locations that do not have an associated wireless fingerprint that are closer to the new bound space than to any existing bind are associated with the new bound space.

6. An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to:

receive a new bound space that comprises an observed wireless fingerprint at a mobile apparatus and a corresponding geographical location for a given bound space;

determine whether to at least one of accept and decline the new bound space based upon the observed wireless fingerprint compared to previously measured wireless fingerprints and locations;

analyze an average signal distance between the geographical location and a plurality of nearest neighbors that comprise existing bound spaces stored in a database wherein, when accepting the new bound space to a fingerprint of a current bound space for the mobile apparatus, an increase in the average signal distance improves the accuracy of the existing bound spaces stored in the database;

accept the new bound space to the fingerprint of the current bound space for the mobile apparatus in an instance in which adding the new bind to the database increases the current average signal distance between the geographical location and the plurality of nearest neighbors that comprise existing bound spaces stored in the database;

decline the new bound space from the fingerprint of the current bound space for the mobile apparatus in an instance in which adding the new bind to the database decreases the current average signal distance between the geographical location and the plurality of nearest neighbors that comprise existing bound spaces stored in the database; and

fail to associate the new bind with the geographic location in response to declining the new bound space.

7. An apparatus according to claim 6, wherein determining whether to at least one of accept and decline the new bound space comprises accepting the new bound space in an instance in which the new bind is the only bound space corresponding to the geographic location.

8. An apparatus according to claim 6, wherein determining whether to at least one of accept and decline the new bound space comprises:

hierarchical clustering to group the new bound space with existing bound spaces that correspond to the geographical location; and

accepting the new bound space if it is in the cluster whose sum of signal distance to neighbor locations is shortest in response to more than one cluster resulting from the hierarchical clustering.

9. An apparatus according to claim 6, wherein determining whether to at least one of accept and decline the new bound space comprises:

determining wireless fingerprints from a plurality of spaces that neighbor the geographical location;

determining if the wireless fingerprints from the majority of the plurality of spaces that neighbor the geographical location match the wireless fingerprint of the new bound space; and

accepting the new bound space in response to the wireless fingerprints from the majority of the plurality of spaces that neighbor the geographical location matching the wireless fingerprint of the new bound space.

10. The method of claim 6, comprising:

receiving a request for a user device to provide a user-defined location;

providing for display of a representation of an estimated geographic location of the user device;

receiving a user-defined location;

providing for transmission of the user defined location;

wherein the representation of the estimated geographic location of the user device is at least a portion of a Voronoi diagram.

11. A method according to claim 10, wherein the Voronoi diagram includes a plurality of spaces.

12. A method according to claim 11, wherein the user-defined location is a space on the Voronoi diagram.

13. A method according to claim 12, wherein the Voronoi diagram is updated to include the user-defined location as a new bound space in a new bound region.

14. A method according to claim 13, wherein the new bound region includes spaces proximate the new bound space that are closer to the new bound space than they are to an existing bound space.

15. A method according to claim 10, wherein the request is generated by the user device.