HK1159925A - Managing a location database for network-based positioning system - Google Patents

Description

Managing location databases for network-based positioning systems

Technical Field

The present disclosure relates generally to determining a geographic location for a mobile device.

Background

Wireless communication networks may employ various techniques for devices to communicate wirelessly. For example, a Wireless Local Area Network (WLAN) may include a local area network (e.g., a computer network covering a relatively small physical area, such as a home, office, or a small group of buildings, such as a school) that uses radio waves instead of wires to communicate between nodes (e.g., devices) of the network. Some examples of WLAN technologies include WiFi, which may include any WLAN product based on any Institute of Electrical and Electronics Engineers (IEEE)802.11 standard.

The wireless connection between the sender and the receiver may employ Radio Frequency (RF) technology, i.e., employing frequencies in the electromagnetic spectrum associated with radio wave propagation. Some exemplary radio frequencies used in WiFi are 2.5 gigahertz (GHz) or 5 GHz. When an RF current is supplied to the antenna, an electromagnetic field may be generated. The electromagnetic field may propagate in air. A component of a wireless communication network may be an Access Point (AP). The access point may allow the wireless mobile device to communicate with a wired network. One function of an access point may be to broadcast a wireless signal that may be detected and "listened to" by a computer or wireless mobile device having a wireless adapter.

An access point of a WiFi network may cover a geographic area determined by the strength of signals transmitted and received by the access point and the physical characteristics of the geographic area. A variable number of mobile devices can be located within a communication range of an access point. A mobile device may be simultaneously within communication range of multiple access points. If the location of an access point is known, the mobile device can sometimes determine the location of the mobile device using the locations of access points with which the mobile device can communicate by triangulating the location of the mobile device based on the strength of the signals received from the access points.

Disclosure of Invention

Methods, program products, and systems for managing a location database of a network-based positioning system are described. The server computer may receive location information from a location-aware mobile device (e.g., a GPS-enabled device) located within a communication range of an access point of the wireless communication network. The server computer may calculate an average geographic location using the received locations for each access point. Based on the average geographic location, the server computer may assign an access point to a cell of a geographic grid. The server computer may filter the access points in each cell based on the received data and the popularity, stability, longevity, and freshness of the access points. The server computer may store an identifier of the access point in association with the average geographic location in a location database.

A mobile device can determine the location of the mobile device using the locations of access points to which the mobile device can connect. Upon connecting to an access point in a cell on the geographic grid, the mobile device can request and receive location information for the access point, the locations of other access points in the cell, and the locations of access points in cells proximate to the cell. The mobile device can identify, based on the received information, a location associated with an access point within communication range of the mobile device. The mobile device may calculate an average geographic location using the identified locations. The mobile device may also calculate the distance between each location and the calculated average. The mobile device may exclude locations that are sufficiently far from the average. The mobile device may repeat the calculating and excluding until a certain level of accuracy is achieved for the average geographic location. The mobile device may display the information on a map display of the mobile device.

Techniques for managing a location database of a network-based positioning system may be implemented to achieve the following exemplary advantages. A geographic area may be associated with an access point of a wireless communication network when the actual location of the access point is unknown. The geographic region may correspond to an area within a communication range of the access point where an actual mobile device may be located, rather than an actual location of the access point. The geographic area may be estimated based on real-time data from the mobile device, which may be updated frequently and thus may provide up-to-date location information. If an access point has left or is turned off, the access point may be removed from the database to avoid invalid location determinations. The geographic area may be calculated based on data received from the mobile device at various times of the day, such that the geographic area may correspond to various usage patterns, such as, for example, time on road (communethours), hours of operation, or nights.

An access point associated with a geographic area can be used to determine a location of a GPS-enabled mobile device located within a communication range of the access point. Data transmission between the access point and the mobile device can occur while the mobile device is idle to avoid interfering with normal communications between the mobile device and the access point. Since a system for determining the location of a mobile device using the locations of access points can transmit the locations of access points that are directly within the communication range of the mobile device as well as the locations of access points in the vicinity, the system can self-limit the consumption of bandwidth by the mobile device. Therefore, even when the mobile device moves, frequent updates and retransmissions are unnecessary. The filtering mechanism of the access points in each cell may further limit the amount of data transmitted to the mobile device in each transmission. A mobile device may estimate its location more accurately than, for example, using signal strength to estimate the location, since signal strength may change due to various interferences. A mobile device that is capable of using GPS may take advantage of the location of a wireless access point when, for example, the GPS signal is weak (e.g., within a building).

The details of one or more implementations of managing a location database of a network-based positioning system are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of managing a location database will become apparent from the description, the drawings, and the claims.

Drawings

FIG. 1A is an overview of a technique to manage a location database.

FIG. 1B illustrates a technique for managing a location database in a three-dimensional space.

Figures 2A-2C illustrate exemplary stages for determining a location associated with an access point in a WLAN with a mobile device.

Fig. 2D illustrates exemplary stages for determining a location associated with an access point in a WLAN with a mobile device in three-dimensional space.

Fig. 3A and 3B are flow diagrams illustrating an exemplary process for determining a location associated with an access point in a WLAN with a mobile device.

FIG. 3C is a block diagram illustrating an exemplary system implementing techniques for managing a location database.

Fig. 4A illustrates a technique for determining the location of a mobile device using a location database in a network-based positioning system.

FIG. 4B is a flow chart illustrating an exemplary process for determining a location of a mobile device using a location database.

FIG. 4C is a flow diagram illustrating an exemplary adaptive multi-pass process for determining a location of a mobile device.

Fig. 5 illustrates an exemplary user interface for determining a location of a mobile device using locations of wireless access points.

Fig. 6 is a block diagram of an exemplary system architecture for implementing the features and operations described with reference to fig. 1-5.

FIG. 7 is a block diagram of an exemplary architecture of a mobile device.

Like reference symbols in the various drawings indicate like elements.

Detailed Description

Overview of managing a location database

Fig. 1A is an overview of a technique for managing a location database of a network-based positioning system. A Wireless Local Area Network (WLAN) may be a wireless communication network that includes several access points 105. The access point 105 may include a hardware device or computer software capable of acting as a communications hub for wireless devices to connect to a wired network. Multiple access points 105 may be distributed in a region (e.g., an office building or airport).

Access point 105 may communicate with wireless devices (e.g., mobile devices 108 and 110) using various communication protocols. In some implementations, the access point 105 may be WiFi^TMAn access point of a network that implements an Institute of Electrical and Electronics Engineers (IEEE)802.11 based protocol (e.g., IEEE802.11 a). In some implementations, the access point 105 may be an access point of a Worldwide Interoperability for Microwave Access (WiMAX) network that implements an IEEE802.16 based protocol (e.g., IEEE802.16-2004 or IEEE802.16 e-2005). The access point 105 may have a range of communication depending on the access involvedThe communication range may range anywhere from less than tens of meters to hundreds of meters from the location of the access point 105, depending on the configuration of the point 105 and the physical environment. When multiple mobile devices 108 and 110 are within communication range of access point 105, mobile devices 108 and 110 can connect to the access point. Accordingly, a single mobile device 108 or 110 may access multiple access points 105 for connection. The mobile devices 108 and 110 can select a particular access point 105 to which the mobile devices 108 and 110 can connect based on various factors. For example, the selection can be based on whether the mobile device 108 is authorized to connect to the access point 105a, or whether the access point 105a can provide the strongest signal for a wireless connection to the mobile device 108.

The system may determine a location area 115 associated with the access point 105. The location areas 115 can be calculated such that they indicate where mobile devices 108 located within communication range of the access point 105 are likely to be located. The system can make this determination based on known locations from mobile devices 108 located within communication range of access point 105. Mobile device 108 can be a location-aware mobile device, such as a GPS-enabled mobile device that has built in or connected to a receiver that can receive Global Positioning System (GPS) signals and determine location using the GPS signals. Location aware mobile device 108 is represented in fig. 1A as a black triangle. When location-aware mobile devices 108 are within communication range of a particular access point 105 (e.g., access point 105a), location-aware mobile devices 108 can transmit the locations of these devices to access point 105 a. The access point 105a may forward the transmission to the system along with an identifier for the access point 105 a. The system may determine an estimated location area 115a in which any mobile device 108 or 110 located within communication range of access point 105a is most likely located. In this description, the estimated location area 115 is referred to as a presence area (presence area) to indicate that the mobile device 108 or 110 may be present when located within communication range of a particular access point 105.

To calculate the presence area 115, the system may apply an iterative process (e.g., by performing a multi-pass analysis). The iterative process may determine a presence area (e.g., presence area 115) associated with an access point (e.g., access point 105) in the form of a circle. The circle may have a center corresponding to an average geographic location calculated based on the location of location-aware mobile devices 108 located within communication range of access point 105. The circle may have a radius corresponding to an error magnitude (error margin), which may be determined based on, for example, a distance between the location of mobile device 108 and the average geographic location. Further details regarding this iterative process will be described below with reference to fig. 2 and 3. This iterative process may be performed periodically (e.g., every 6 hours) in order to capture different wireless access usage patterns during different times of the day, as well as to capture possible movements of the access point 105.

The system may transmit the presence area 115 information to mobile devices within communication range of the access point 105, including mobile devices that are not capable of using GPS (e.g., mobile device 110), so that the receiving mobile device may determine an estimated location of the device using the presence area 115. For example, if the mobile device 110 is within a communication range of the access point 105b, the location of the mobile device 110 may be estimated to coincide with the presence area 115b associated with the access point 105 b.

In a given area (e.g., an airport), there may be a large number of access points 105. Additionally, since mobile device 110 may be mobile, it may be desirable to transmit locations of access points that are not directly within communication range of mobile device 110, but that are sufficiently close to mobile device 110 so that mobile device 110 may use these locations to track its movement. To avoid sending large amounts of location data to the mobile device 110, the system may filter the access points 105 and the presence areas 115 so that only location data for a limited number of access points (e.g., access point 105a) is transmitted instead of location data for each access point present in the world. The filtering may be based on various factors including popularity, stability, longevity, and freshness of the location 115 and access points 105.

To filter locations 115 and access points 105, the system may create a geographic grid 100 containing cells 102. The cells 102 may be polygons that are generally rectangular in shape, corresponding to geographic areas on the geographic grid 100 that may be identified by the latitude and longitude of an identified point (e.g., center or corner) of the geographic area, as well as the size (e.g., length in degrees longitude and width in degrees latitude). Each cell 102 may be used as a container that may contain a number of locations. For example, the cell 102 may be rectangular, with a length of 0.0005 degrees meridian (approximately 56 meters), and a width of 0.0005 degrees latitude (the width in meters may vary depending on latitude). Unit 102 may be configured to own several (e.g., 3) presence areas 115 corresponding to access points 105. In some implementations, a cell 102 may "own" a presence area 115 if the center of the presence area 115 is located within the boundaries of the cell 102. Presence areas 115 may be selected from all presence areas 115 located in cell 102 based on one or more reliability factors. The selection may be based on various criteria, such as popularity, stability, longevity, and freshness.

A particular access point (e.g., access point 105b) and a presence area (e.g., presence area 115) associated with the access point need not be located in the same cell 102. This may occur, for example, when access point 105b is located on one building in cell 102a and most of mobile devices 108 located within communication range of access point 105b are located in another building in cell 102 b. In some implementations, the system may ignore the actual location of access point 105 b.

When mobile device 110 connects to an access point (e.g., access point 105a, whose associated presence area 115a is located in cell 102c), or otherwise connects to the system (e.g., through a cellular network), mobile device 110 may receive a location update from the system. The location update may include all presence areas 115 located in the same cell (e.g., cell 102c) in which presence area 115a is located. The location update may also include presence areas 115 located in other cells 102 (e.g., cell 102a and cell 102b) that are adjacent to cell 102c on geographic grid 100.

When mobile device 110 connects to access point 105a, mobile device 110 may detect other access points 105 (e.g., access point 105b) that are available. The mobile device 110 may identify the presence areas (e.g., presence areas 115a and 115b) of the available access points. The mobile device 110 may calculate the current location of the mobile device 110 using various algorithms. For example, when only one presence area 115a is identified, the mobile device 110 may designate the presence area 115a as the current location of the mobile device 110. When two or more presence areas 115 are identified, the mobile device 110 may calculate its current location using an iterative process (e.g., a multi-pass analysis). The iterative process may calculate an average position of the presence areas, calculate a distance between the presence areas and the average position, and exclude presence areas that are farthest from the average position. The mobile device 110 may repeat this iteration until the accuracy requirements for determining the location of the mobile device 110 are met. The mobile device 110 may designate the average location as the current location of the mobile device 110 and display the average location on a map display device.

In some implementations, the location updates received from the system on the mobile device 110 can include many neighboring cells, and thus can cover a sufficiently large area (e.g., 1 or 2 square kilometers) surrounding the presence area 115 a. Based on the location updates covering the large area, the mobile device 110 may avoid having to request frequent updates as the mobile device 110 moves. The mobile device 110 may have an opportunity to receive updated presence area information when, for example, the mobile device 110 is idle or has available communication bandwidth.

FIG. 1B illustrates managing a location database in three-dimensional space. Some location aware mobile devices 108 (e.g., GPS-enabled devices) may identify a location in three-dimensional space. These locations may be represented in latitude, longitude and altitude. The altitude may be expressed as an altitude measured in meters, for example, from sea level. When the height of a mobile device is needed to locate the mobile device, it may be desirable to locate the mobile device in three-dimensional space. For example, the altitude may be used to determine which floor of a high-rise building the mobile device is at. The location of the mobile device 108 in three-dimensional space may be displayed on a two-dimensional map with altitude as an annotation, or on a three-dimensional map.

Mobile device 108 can connect to access point 126. Mobile device 108 may be a location-aware mobile device that may transmit its location to the system, including latitude, longitude, and altitude coordinates. The system may calculate an average location based on latitude, longitude, and altitude coordinates received from mobile device 108. A three-dimensional space 124 centered at the average position and having a radius of error magnitude may be associated with an access point 126. Space 124 may represent the space in which a mobile device may be located when the mobile device is within communication range of access point 126. In this specification, the space 124 is referred to as a presence space.

The system sends information about the presence space 124 to mobile devices located within communication range of the access point 126. The mobile device that receives the information can utilize the information to determine its geographic location. The system may divide the three-dimensional geographic space into a three-dimensional grid 120. The three-dimensional grid 120 may be composed of three-dimensional cells 122. Each three-dimensional cell 122 may have a base corresponding to a cell 102 of geographic grid 100. Each three-dimensional cell 122 may have a height as one dimension (e.g., measured in meters). If the center of presence space 124 is in cell 122, presence space 124 may be said to be located in cell 122. The system may limit the number of presence spaces in cell 122 based on the popularity of the presence spaces (e.g., how many connections from mobile devices 108 in the presence spaces to access points 126 are formed), the stability of presence spaces 124 (e.g., how stable presence spaces 124 are), the age of access points 126 (e.g., how long access points 126 have existed), and the freshness of presence spaces 124 (e.g., when the latest location transmissions from mobile devices 108 located within communication range of access points 126 were received).

The system may transmit information about presence space 124 and neighboring presence spaces to mobile devices (e.g., mobile device 110) located within communication range of access point 126 based on three-dimensional cells 122 of three-dimensional grid 120. The mobile device 110 may utilize this information to estimate the current location of the mobile device 110 in three-dimensional space and display the estimated current location on a three-dimensional map.

Exemplary Server-side Process and System for managing location databases

Fig. 2A-2C illustrate exemplary stages of managing a location database. For convenience, these techniques will be described with the aid of a network-based positioning system that includes a server implementing these techniques.

Fig. 2A illustrates exemplary stages of a multi-pass analysis that may be used to determine a presence area associated with an access point 105. Access point 105 may have a coverage area 202, which coverage area 202 may be determined by the signal strength of the transmitters of access point 105 and other factors (e.g., physical characteristics of the geographic area surrounding access point 105). Mobile devices 108 located within coverage area 202 can wirelessly connect to access point 105. Access point 105 may allow mobile device 108 to connect to a wired network through various gateways. The wired network may include a data network (e.g., the Internet), a Public Switched Telephone Network (PSTN), other digital or analog networks, or a combination thereof.

Mobile device 108 may comprise a location-aware mobile device (e.g., a GPS-enabled mobile device). Each location-aware mobile device 108 (represented by the black triangle of fig. 2A) can detect its current geographic location. The current geographic location may be represented by geographic coordinates including a latitude and longitude of mobile device 108. When mobile device 108 is in communication with access point 105, mobile device 108 may transmit location information to the system through access point 105. The location information may be associated with an identifier of the access point 105 (e.g., a Media Access Control (MAC) address of the access point 105). The system may utilize location information received from multiple mobile devices 108 to determine presence areas that may be associated with access points 105. The presence area does not necessarily enclose the location where the access point 100 is actually located. The presence area also does not necessarily correspond to the geometric location or shape of the coverage area 202, although the presence area may be located within the coverage area 202.

The distribution of mobile devices 108 with coverage area 202 may correspond to a snapshot (snapshot) of mobile device 108 at a particular time (e.g., 8: 30 am, local time of the time zone in which access point 105 is located). Each mobile device 108 may be associated with a single location. The distribution of mobile devices 108 with coverage areas 202 may also correspond to locations of mobile devices 108 over a period of time (e.g., 6 hours from 4 am to 10 am). Each mobile device 108 may be associated with multiple locations (e.g., as the mobile device 108 moves). A single mobile device 108 associated with multiple locations may be represented by multiple locations in the system, as illustrated by the multiple triangles in fig. 2A.

The server may determine an average geographic location of the set of locations received from the mobile device 108. The set of locations may include locations received from mobile device 108 at a particular time or during a particular time period. The average geographic location may be designated as the center 205 of the area enclosed by circle 204 a. The center of circle 204a does not necessarily coincide with the location of access point 105. The server may calculate a distance between the average geographic location and each location in the set of locations and identify one or more outliers (outliers). The outliers may be the locations of the set of locations that are farthest from the average geographic location. Outliers that are more than some threshold distance from the center (e.g., location 210) may be excluded from the set of locations. Circle 204a may have a radius 206, radius 206 corresponding to the longest distance between the average geographic location and the location in the current set of locations after the outlier is excluded.

FIG. 2B illustrates an exemplary stage in a multi-pass analysis that follows the stage of FIG. 2A. Locations whose distance to the average geographic location of fig. 2A (center 205 of circle 204a) exceeds some threshold have been excluded from the set of locations. The threshold may be configured such that a certain percentage of locations (e.g., 5% of the locations of fig. 2A) are excluded. A new average geographic location may be calculated based on the remaining locations in the set of locations (e.g., the remaining 95% locations). The new average geographic location may be, for example, the center 225 of the circle 204 b. In various implementations, calculating the new average geographic location may include averaging the remaining locations in the set of locations, selecting an intermediate geographic location in the set of locations (e.g., by selecting an intermediate latitude or an intermediate longitude), or applying other algorithms. The algorithms used to calculate the average geographic location may be the same in each of the multiple passes of the analysis, or may be different from each other in each pass.

When outlier locations are excluded, the area encompassed by circle 204b may be smaller than the area encompassed by circle 204a determined in the previous pass. This smaller area may reflect increased computational accuracy. The center 225 of circle 204b does not necessarily coincide with the center 205 of circle 204 a. In some implementations, the radius 216 of the circle 204b can correspond to the remaining location of the mobile device 108 furthest from the center 225 of the circle 204 b. Radius 216 may represent the error magnitude of the new estimate of the presence area calculated in the current pass.

Fig. 2C shows an exemplary final stage of the multi-pass analysis. The system may terminate the iterative process after the final stage when certain exit conditions are met. The final stage may produce a final average geographic location corresponding to the locations of a cluster of aggregated mobile devices 108. The final average geographic location may be represented as the center 235 of the circle 204 c. Circle 204c may have a radius corresponding to the final error magnitude that is based on the distance between the final average geographic location and the location in the cluster of locations. Circle 204c may be designated as a presence area associated with access point 105 by an identifier (e.g., a MAC address) of access point 105.

The server may determine whether to include the identifier of the access point 105 and the associated presence area in the location database based on various factors. For example, the server may count the number of presence areas in the cells 102 of the geographic grid 100 and select a number of presence areas based on popularity, stability, and longevity. The server may send information of the presence areas (including presence area 204c, if presence area 204c is selected) in the location database to the mobile device (e.g., mobile device 215) regardless of whether mobile device 215 is capable of using GPS.

FIG. 2D illustrates an exemplary stage of managing a location database in three-dimensional space. In fig. 2D, axes X, Y and Z may be used to indicate three-dimensional space. For example, axes X, Y and Z may represent longitude, latitude, and altitude, respectively. For convenience, the location of the access point 126 is shown as coinciding with X, Y in fig. 2D and a zero point on the Z-axis. In some implementations, the actual location (e.g., latitude, longitude, and altitude coordinates) of the access point 126 is optional in the calculation.

Each triangle of fig. 2D may represent a location of a mobile device located in three-dimensional space. These locations may have projections (e.g., projection 226) on one plane of the three-dimensional space. The plane may be defined at any height (e.g., the height of the access point 126). For example, the plane may be defined by axes X and Y. Access point 126 may correspond to a coverage area 222, and the coverage area 222 may be determined by the signal strength of the access point 126 and other limiting factors (e.g., floor, ceiling, buildings in the signal path).

A multi-pass analysis can associate a geographic space with an access point 126 of a WLAN based on a set of locations received from location-aware mobile devices 108 located in cellular space 202. In one pass of the multi-pass analysis, an average geographic location (e.g., the center of space 224) may be determined by, for example, averaging the latitude, longitude, and altitude coordinates of the locations in the set of locations. The distance between the average geographic location and the location in the coverage area 222 may be calculated. Locations that are within the coverage area 222 but sufficiently far from the average geographic location may be excluded from the set of locations and further calculations. The radius of the space 224 may be determined by, for example, the farthest distance between the remaining locations in the set of locations and the average geographic location.

The system may repeat the following stages: the method includes calculating an average geographic location in a set of locations, calculating a distance between the average geographic location and a location in the set of locations, and excluding from the set of locations based on the calculated distance. This repetition may continue until an exit condition is satisfied. A space centered at the average geographic location and having a radius based on the distance between the average geographic location and the remaining locations in the set of locations may be designated as a presence space that may be associated with the access point 126.

Fig. 3A is a flow diagram illustrating an exemplary process 300 for managing a location database. Process 300 may be used, for example, to determine a presence area or presence space associated with an access point of a WLAN. The presence area or presence space may be used to determine the location of a mobile device that is not capable of using GPS. For convenience, process 300 will be described with reference to a system that performs process 300.

The system can receive (302) a set of locations from one or more first mobile devices 108 located within a communication range of access point 105. Each location may be represented by a set of geographic coordinates (e.g., latitude, longitude, and altitude). The location may be associated with an identifier (e.g., a MAC address) of the access point 105. When the access point 105 communicates with the system, the access point 105 may automatically provide an identifier of the access point. In various implementations, the set of locations may correspond to a period of time (e.g., 6 hours, or from 6 am to 10 am of the time zone in which access point 105 is located).

In some implementations, the time period may be configured to reflect characteristics of a particular usage pattern at various times of the day. The area in which mobile devices located within communication range of access point 105 are most likely to be located may change during the course of a day, indicating various usage patterns at particular times. For example, the time period may correspond to "on-road time," "work time," "night time," and so forth. The characteristics of the time of day may correspond to various usage patterns of the mobile device 108. For example, during on-road times, the presence area associated with access point 105 may be at or near a highway; during operational hours, the presence area associated with access point 105 may be at or near an office building; during the night time, the presence areas associated with access points 105 may spread out without a particular point of concentration. The system may calculate the presence area based on the location received, for example, from 4 am to 10 am, and recalculate based on the location received from 10 am to 4 pm, and so on. The locations received in each characteristic time period may be grouped into a set of locations in the system. These locations may be stored in any data structure (e.g., collection, list, data records in a relational database, etc.) on a storage device coupled to the server.

The system may determine (304) a geographic location associated with the access point 105 based on the average of the received locations. The geographic location may include a presence area or a presence space as described above. The presence area or presence space may be associated with access point 105 by, for example, the MAC address of access point 105. In some implementations, determining the geographic location may include applying a multi-pass algorithm to the received set of locations, including excluding at least one location from the set of locations on each pass. Determining the geographic location may include periodically applying a multi-pass algorithm.

The system may assign 306 an access point 105 and a geographic location associated with the access point 105 to a cell (e.g., cell 102) on a geographic grid based on various factors including popularity of the access point 105, stability of the geographic location, and longevity of the access point 105. In some implementations, the popularity of an access point 105 can measure how many mobile devices 108 are within communication range of the access point 105. The popularity of an access point may be measured, for example, by how many mobile device 108 locations are received by the system within communication range of the access point 105 over a period of time.

The stability of the presence area associated with access point 105 may reflect how reliable the presence area is if the presence area is used to estimate the location of devices located within communication range of access point 105. The stability of the presence areas associated with access point 105 may be measured, for example, by comparing the presence areas calculated by the last two calculations and determining the degree of overlap between these presence areas. The higher the degree of overlap, the more stable the presence area.

The lifetime of the access point 105 may reflect the quality of data associated with the access point 105. For example, an access point that exists in the database for a longer time may be more reliable than a recently added access point. The lifetime of the access point 105 may be measured by a history of data in the location database.

In some implementations, the freshness of the data can also be used to determine whether to assign a presence area associated with an access point 105 to a cell 102 of the geographic grid 100. The freshness of the data can be measured by how long ago the system received the latest location from the mobile device 108.

The system may score each presence area located in a cell 102 of the geographic grid 100 based on popularity, stability, longevity, and freshness. At least a portion of all presence areas located in cell 102 (e.g., three presence areas, including the presence area associated with access point 105) may be assigned to cell 102. The assigned access point and presence area may be used to locate mobile devices (e.g., mobile device 110) that are within communication range of access point 105. Unallocated presence areas may be stored in a location database for future use.

The system can provide (308) the geographic location associated with access point 105 to a second mobile device (e.g., mobile device 110) located within communication range of access point 105. The system may also provide the second mobile device with other geographic locations located in the same cell, as well as geographic locations associated with access points assigned to neighboring cells. These locations may be transmitted from the access point 105 to the second mobile device upon request or using various push or broadcast techniques.

In some implementations, the system may receive, process, and transmit three-dimensional location information. A presence space (e.g., presence space 124) may be assigned to a three-dimensional cell (e.g., three-dimensional cell 122) on a geographic three-dimensional grid (e.g., three-dimensional grid 120). These locations may be transmitted from access point 126 to a second mobile device located within communication range of access point 126 upon request or using various push or broadcast techniques.

FIG. 3B is a flow diagram illustrating an exemplary process 304 for calculating an average geographic location using a set of locations. For convenience, process 304 will be described with reference to a system that performs process 304.

The system may calculate (324) an average geographic location using the locations in the set of locations. Calculating the average geographic location may include calculating an average of the latitude, longitude, and altitude of the locations in the group, and designating the locations at the calculated average latitude, longitude, and altitude as the average geographic location. In some implementations, calculating the average geographic location may include designating a location located at a middle latitude, a middle longitude, and a middle altitude of the locations in the group as the average geographic location.

The system may calculate (326) a distance between a location in the set of locations and the average geographic location. In some implementations, the system may calculate the linear distance between each location in the group and the average geographic location in euclidean space. In some implementations, the system may calculate geodesic distances between each location in the set and the average geographic location, taking into account the curvature of the earth.

The distance calculated in stage 326 may be specified as a radius associated with one center. The center may be the average geographic location calculated in stage 324, which may be the center of a circle (e.g., circle 204 a). The radius of the circle may be determined based on at least one distance between one of the set of locations and the average geographic location. In some implementations, the radius may be equal to the longest distance between the average geographic location and the remaining locations in the group. In some implementations, the radius may be a distance: when circle 106d is drawn using the radius and centered on the average geographic location, the circle may contain a percentage (e.g., 80%) of the remaining locations in the group. The radius may represent a margin of error beyond which a location estimate for a mobile device that is not capable of using GPS is unlikely to be statistically significant.

The system may exclude (328) the at least one location from the group based on a distance between the average geographic location and the at least one location. In some implementations, the system may exclude locations that are more than a certain threshold distance from the average geographic location. In each pass of the multi-pass analysis, the system may increase the accuracy of the estimated average geographic location by excluding locations that appear to be far away from a cluster of locations (e.g., a cluster of aggregated locations). Locations that are far from a cluster of aggregate locations are less useful in estimating presence areas associated with access points 105 and may be excluded. In various implementations, the threshold distance may vary from one pass to the next. In some implementations, the threshold distance may be a distance to an average geographic location within which a percentage (e.g., 95%) of the locations in the set of locations are located. In some implementations, the threshold distance may be a set of distances corresponding to passes (e.g., 250 meters for the first pass, 150 meters for the second pass, etc.). When the distance between the average geographic location and the at least one location exceeds the threshold distance, the system may exclude the at least one location from the set of locations.

The system may repeat stages 324, 326, and 328 of process 304 until an exit condition is satisfied. The system may determine (330) whether an exit condition is satisfied in order to terminate the repetition. In some implementations, the exit condition is satisfied when the number of repetitions reaches a certain threshold number (e.g., 10). The threshold number of times and the percentage used to exclude locations may be configurable to fine tune the balance between certainty (e.g., a larger presence area may result in more confidence that the mobile device in the cell is actually located in the presence area) and accuracy (e.g., a smaller presence area may result in a more accurate location of the mobile device). For example, when the percentage is set to 95% and the number of passes is set to 10, the last pass may produce a circle containing approximately 60% of all the location data points.

In some implementations, the exit condition of stage 330 may be satisfied when the presence area or presence space is sufficiently small. In cells where the mobile device is highly concentrated, the presence area may be small enough that more passes will not necessarily increase accuracy. The repetition of stages 324, 326, and 328 may terminate when the radius of the circle reaches below the threshold radius. For example, the threshold radius may be 8-10 meters. The threshold radius may vary from access point to access point based on a distribution pattern of locations in the received set of locations (e.g., a number of received location data points, a density of location data points, and a concentration area in a cell).

The system may assign (332) a geographic area as a circle centered at the average geographic location with a radius based on the at least one calculated distance. The geographic region may be associated with an access point (e.g., access point 105). The server may provide the geographic area (e.g., center and radius) to the mobile device in order to calculate the current location of the mobile device. The center may be represented by latitude and longitude. In some implementations where distances are calculated in three-dimensional space, the center may be further represented by a height.

Fig. 3C is a block diagram illustrating an exemplary system implementing techniques for managing a location database. The system may include one or more processors, one or more memory devices storing instructions, and other hardware or software components. The system may include a location engine 350 that may be used to determine a presence area or presence space to be associated with an access point (e.g., access point 105).

The location engine 350 can include a data collection module 352 that can receive data from various mobile devices through various access points. The data can include a plurality of data points that can indicate a location of one or more location-aware mobile devices (e.g., mobile device 108) and an access point identifier (e.g., MAC address of access point 105) that indicates to which access point mobile device 108 is connected. In some implementations, the data point can also include information about the time zone in which the mobile device 108 is located. Data collection module 352 may include a data reception module 354 and a data indexing module 356, data reception module 354 may receive data transmitted from mobile device 108. Data indexing module 356 can perform various processing on the received data points. For example, the data indexing module 356 may order latitude, longitude, and altitude based on the cell ID. The data indexing module 356 may also group data based on time periods. For example, a new set of receive positions may be created for a configurable period of time (e.g., 6 hours).

The location of each set of received mobile devices 108 may be stored in the data point database 360. The data point database 360 can store current and historical locations of various mobile devices 108. The data point database 360 may include an ad-hoc database, a relational database, an object-oriented database. The data point database 360 may be hosted locally or remotely with respect to the location engine 350.

The location calculation module 364 can be utilized to calculate an average geographic location in each set of data points in the data point database, calculate a distance between the average geographic location and the location of each data point, and exclude locations from the set for further calculations. The location calculation module 364 can perform calculations for a particular set (e.g., a set of data points associated with a cell ID) until an exit condition for the particular set is reached. The location calculation module 364 may determine a presence area or presence space for each access point (e.g., access point 105).

In some implementations, the location calculation module 364 can perform a validity check on the presence area or presence space based on various criteria and various data in the data points using the validity checker 366. For example, the data points received from the mobile device 108 can include a Mobile Country Code (MCC) and time zone information. Validity checker 366 can compare the calculated presence area or presence space with polygons corresponding to countries represented by MCCs and polygons corresponding to time zones. If the calculated presence area or presence space is outside of these polygons, validity checker 366 can record an exception and remove the access point.

Location filtering engine 368 can determine whether a presence area or presence space can be used to estimate a location of a mobile device currently located within communication range of an access point. Location filtering engine 368 may divide the geographic area into cells 102 of geographic grid 100 or three-dimensional cells 122 of three-dimensional grid 120. The location filtering engine 368 can score presence areas or presence spaces based on popularity, stability, longevity, and freshness. Location filtering engine 368 can assign a highest scoring presence area or presence space located in each cell 102 or three-dimensional cell 122 to a cell 102 or three-dimensional cell.

A presence area or presence space may be defined by a center having an average latitude, longitude, and altitude coordinate of a set of locations. The presence area or presence space may also be defined by a radius determined based on the distance of the location from the center in the set of locations. The latitude, longitude, and altitude coordinates of the center of the presence area or presence space and the radius of the presence area or presence space may be stored in location database 372. Location database 372 may store allocated and unallocated presence areas and presence space. The location calculation module 364 may allocate unallocated presence areas or presence spaces in subsequent calculations. Location database 372 may be periodically updated by location calculation module 364.

Data of location database 372 may be distributed to mobile devices using data distribution module 376. Data distribution module 376 can send the assigned information (e.g., center coordinates and radius) of the presence area and presence space associated with the access point to a mobile device (e.g., mobile device 110 that is not capable of using GPS) upon request, by broadcast, or using various push techniques that do not require receiving a request from the mobile device.

In some implementations, the data distribution module 376 can send multiple presence areas and presence spaces to the mobile device in one transmission session. To reduce the number of location transmissions to the mobile device that may consume mobile device communication bandwidth, the data distribution module 376 can use the neighbor locator 378 to locate the neighbors of the cell in which the mobile device 110 is located. The neighboring cells may include, for example, several cells surrounding a cell in which the mobile device 110 is located, such that the total area of the cell and surrounding cells covers a geographic area (e.g., 1 or 2 square kilometers). Sending information to mobile device 110 regarding presence areas and presence spaces associated with multiple cells (e.g., 400 cells) may reduce the number of transmissions when mobile device 110 moves across cells. In some implementations, the data distribution module 376 need only send updates to the mobile device 110 when the mobile device 110 moves outside of all units that have been previously sent.

Exemplary Process for determining the location of a Mobile device Using the location of a Wireless Access Point

Fig. 4A illustrates a technique for determining the location of a mobile device using the locations of wireless access points. Mobile device 400 can be an exemplary mobile device that can utilize the locations of wireless access points to determine its location. An exemplary portion of a communication network is shown including an access point 404.

Mobile device 400 can be within communication range of access point 404 a. Mobile device 400 can receive data from access point 404a that includes information regarding presence areas or presence spaces (including presence area 406) of neighboring access points. Mobile device 400 can store the received data on a storage device. The stored data may be updated periodically.

In the illustrated example, the mobile device 400 is located within a communication range of an access point 404 a. Further, mobile device 400 is within communication range of access points 404b, 404c, and 404 d. The mobile device 400 can identify the access points 404a, 404b, 404c, and 404d under a wireless communication protocol (e.g., IEEE802.11a) used in the WLAN. The access points 404a, 404b, 404c, and 404d may be identified by the MAC address or other identifier (e.g., a bluetooth identifier) of the access point.

Mobile device 400 can identify presence areas 406a, 406b, 406c, and 406d associated with access points 404a-d, respectively. Identifying the presence areas 406a-d may include retrieving information about the presence areas 406a-d from a memory device coupled to the mobile device 400. In some implementations, the mobile device 400 can request the presence areas 406a-d from a server by sending an identifier of the access points 404a-d to the server.

Based on the presence areas 406a-d, the mobile device 400 can perform an iterative process (e.g., a multi-pass analysis) on the presence areas 406 a-d. The iterative process may produce a geographic area 402, which may be an estimate of the current geographic location of the mobile device 400. When three-dimensional location information is used, the geographic region 402 may be a geospatial space. The mobile device 400 can display the estimated current location on a display device (e.g., on a map display).

Fig. 4B is a flow diagram illustrating an exemplary process 410 for determining a location of a mobile device using a location database. For convenience, process 410 will be described with the aid of mobile device 400 performing process 410.

Mobile device 400 can identify (412) a current access point to which mobile device 400 is connected. The mobile device 400 can use the current access point to determine whether to request an update of a location database located on the mobile device 400. The location database located on mobile device 400 can include records of access points previously downloaded to mobile device 400. A record in a location database located on mobile device 400 can include an identifier of an access point (e.g., a MAC address) and a corresponding location (e.g., latitude/longitude coordinates).

At stage 412, mobile device 400 can determine whether the current access point is included in a record of the location database. The mobile device may perform a location database lookup using an identifier (e.g., MAC address) of the current access point to which the mobile device 400 is connected. The mobile device may determine that the location database is up-to-date if the current access point is included in the record of the location database. If the current access point is not included in the records of the location database, the mobile device 400 can determine that the location database needs to be updated.

Mobile device 400 can request (414) an update of the location database of mobile device 400 from a server using the identifier of the current access point. The records in the location database, including the identifiers and locations of the access points, may be refreshed with new identifiers and locations of new access points. The mobile device 400 can send an identifier of the current access point to the server. The server may identify a unit as a center cell in the geographic grid. The central unit may be a unit that includes a location associated with an identifier of the current access point and transmits all access point locations in the unit and the neighboring units to the mobile device 400.

Mobile device 400 can receive (416) a set of second locations associated with a second access point. The second access points may be distributed among a central cell and cells adjacent to the central cell on the geographic grid. The location associated with the current access point (e.g., the center of the circular area) may be located in the center cell. The neighboring cells may be cells that are located beside or closest to the central cell on the geographic grid. The number of neighboring cells may have a value such that the central cell and neighboring cells may cover a predetermined geographic area (e.g., 1.5 square kilometers). Identifiers of access points and locations associated with the access points may be included in the update when the locations associated with the access points are within a geographic area covered by the central cell and the neighboring cells. One exemplary advantage of updating the location on mobile device 400 when the current access point is not included in the records of the location database is that no update is required as mobile device 400 moves between cells until mobile device 400 moves outside a large area compared to the coverage area of a single access point. Thus, frequent updates can be avoided, saving resources for both the mobile device 400 and the server (e.g., bandwidth, CPU cycles, battery power for mobile devices; for servers, the server need not send frequent updates to a large number of mobile devices as they move from one street zone to the next).

The mobile device 400 may update (418) a location database located on the mobile device 400 using the received set of access point locations and identifiers. The update may "locate" the mobile device 400 at the "center" of the geographic area covered by the central cell and the neighboring cells. The mobile device 400 may not need to request another update until the mobile device 400 moves from the central cell to a cell that is not covered by one of the neighboring cells. For example, if each cell is approximately 50 meters by 50 meters and the predetermined geographic area is 1.5 square kilometers, approximately 600 cells may be injected into the location database of mobile device 400 per update. The mobile device 400 need not request another update unless the mobile device moves outside the 600 cell coverage area.

Mobile device 400 can calculate (420) the current location of mobile device 400 using a location database located on mobile device 400. The calculation may be performed using an adaptive multi-pass process performed by the mobile device 400. Further details of the multi-pass process will be described below with reference to fig. 4C. These factors are not required in the calculation, although other factors (e.g., signal strength from various access points) may aid in the calculation of the current location.

Mobile device 400 may optionally display (422) the current location of mobile device 400 on a map display device of mobile device 400. An exemplary display of the current location is described in more detail below with reference to fig. 5.

Fig. 4C is a flow diagram illustrating an exemplary adaptive multi-pass process 430 for determining a location of a mobile device. For convenience, process 430 will be described with the mobile device 400 performing process 430.

Mobile device 400 can receive (432) an identifier of an access point (e.g., access point 404) of a wireless communication network (e.g., WLAN). These access points can be within communication range of mobile device 400. The identifier need not be associated with the access point to which the mobile device 400 is connected or can be connected. For example, at a particular location, mobile device 400 may be within communication range between 3 and 20 access points. Mobile device 400 may only be able to connect to two access points (due to, for example, the security settings of the access points and mobile device 400). The mobile device 400 may only be actively connected to one of the two access points. However, all access point identifiers received by the mobile device 400 can be used in the calculation.

Mobile device 400 can identify (433) a set of locations associated with the access points from a location database of mobile device 400. The set of locations may correspond to a presence area 406 or presence space associated with the access point. Each location may be represented by geographic coordinates (e.g., latitude, longitude, and altitude). Each location may be associated with an identifier (e.g., MAC address) of one access point 404. The mobile device 400 can identify these locations using a database lookup.

The mobile device 400 can calculate (434) an average geographic location using the locations in the group. Calculating the average geographic location may include calculating an average of the latitude, longitude, and altitude of the locations in the group, and designating a location at the calculated average latitude, longitude, and altitude as the average geographic location. In some implementations, calculating the average geographic location may include designating a median latitude, a median longitude, and a median altitude of the locations in the group as the average geographic location.

Mobile device 400 can calculate (436) a distance between the locations in the group and the average geographic location. In some implementations, the system may calculate the linear distance between each location in the group and the average geographic location in euclidean space. In some implementations, the system may calculate geodesic distances between each location in the set and the average geographic location, taking into account the curvature of the earth.

The distance calculated in stage 436 may be specified as a radius associated with one center. The center may be the average geographic location calculated in stage 434, which may be the center of a circle (e.g., a circle surrounding geographic area 402). The radius of the circle may be determined based on at least one distance between one of the set of locations and the average geographic location. In some implementations, the radius may be equal to the longest distance between the average geographic location and the remaining locations in the group. In some implementations, the radius may be a distance: when a circle is drawn using the radius and centered on the average geographic location, the circle may contain a percentage (e.g., 80%) of the remaining locations in the group. The radius may represent a margin of error beyond which a location estimate for a mobile device that is not capable of using GPS is unlikely to be statistically significant.

The mobile device 400 may exclude (438) the at least one location from the group based on a distance between the average geographic location and the at least one location. In some implementations, the system may exclude locations that are more than a certain threshold distance from the average geographic location. In each pass of the multi-pass analysis, the system may increase the accuracy of the estimated average geographic location by excluding locations that appear to be far away from a cluster of locations (e.g., a cluster of aggregated locations). Locations that are far from a cluster of aggregate locations are less useful in estimating the current location of the mobile device 400 and may be excluded. In various implementations, the threshold distance may vary from one pass to the next. For example, the threshold distance may be a set of distances corresponding to passes (e.g., a first pass of 50 meters, a second pass of 30 meters, etc.). When the distance between the average geographic location and the at least one location exceeds the threshold distance, the system may exclude the at least one location from the set of locations.

In some implementations, the mobile device 400 can determine a threshold percentage of locations to be excluded. The threshold percentage may have a pre-specified value (e.g., 5%). In each pass, the mobile device 400 can exclude a threshold percentage of locations that are farthest from the average geographic location.

Mobile device 400 can repeat stages 434, 436, and 438 of process 430 until an exit condition is satisfied. The system may determine 440 whether an exit condition is satisfied in order to terminate the iteration. In some implementations, the exit condition is satisfied when the number of repetitions reaches a certain threshold number (e.g., 5). The threshold number of times may be related to the number of locations in the group originally received. The threshold number and percentage of excluded locations may be configurable to fine tune the balance between certainty (e.g., a larger presence area may result in greater confidence that the mobile device in the cell is actually located in the presence area) and accuracy (e.g., a smaller presence area may result in a more accurate location of the mobile device). For example, when the percentage is set to 95% and the number of passes is set to 10, the last pass may produce a circle containing approximately 60% of all the location data points.

In some implementations, the exit condition of stage 330 may be satisfied when the presence area or presence space is sufficiently small. In areas where the access point 404 is highly concentrated, the estimated current position may comprise an area small enough that more passes will not necessarily increase accuracy. The repetition of stages 434, 436 and 438 may terminate when the radius of the circle reaches below the threshold radius. For example, the threshold radius may be 8-10 meters. The threshold radius may be based on the radius of presence area 406. In some implementations, if the radius of some presence areas 406 is small enough, the threshold radius may be small to reflect the confidence of the estimate.

Mobile device 400 can specify (442) a current location of mobile device 400 using a circle centered at the average geographic location and having a radius based on the at least one calculated distance. The center may be represented by a latitude and a longitude. In some implementations where distances are calculated in three-dimensional space, the center may be further represented by a height. In some implementations, the mobile device can also display the current location on the display device on a map user interface. An exemplary map user interface will be described below with reference to fig. 5.

Exemplary user interface for determining a location of a mobile device

Fig. 5 illustrates an exemplary user interface for determining a location of a mobile device using locations of wireless access points. In fig. 5, an example map 502 of a geographic area is displayed on a mobile device 500. In some implementations, the mobile device 500 can display the map 502 on a touch-sensitive display 530 of the mobile device 500. When a user selects a map object for viewing a map and location based service, a map 502 may be displayed. In some implementations, objects such as map objects may be selected through voice activation. A search bar 504 and a bookmark list object 506 may be displayed at the top of the map 502. One or more display objects, such as search object 508, route object 510, map view object 512, and current location object 514, may be displayed below the bottom of the map.

The search bar 504 may be used to find an address or other location on a map. For example, the user may enter his home address in the search bar 504, so that the area containing the address will be displayed on the map 502. The bookmark list object 506 may, for example, present a bookmark list containing frequently accessed addresses, such as the home address of the user. The bookmark list may also, for example, contain special bookmarks, such as a current location (e.g., a current location of the mobile device 500).

Search object 508 can be used to display search bar 504 and other map related search menus. The route object 510 may, for example, present a menu interface that allows the user to enter start and end positions. The interface may then display information (e.g., directions and travel times for a route from the start location to the end location). The map view object 512 may present a menu that allows the user to select display options for the map 502. For example, the map 502 may be changed from black and white to color, the background of the map may be changed, or the user may change the brightness of the map.

The current location object 514 may allow the user to view a geographic area 516 on the map 502 that indicates where the device 500 is currently located. Geographic area 516 can correspond to an estimated geographic area (e.g., geographic area 402) centered at an average geographic location of data points associated with access points within communication range of mobile device 500. The radius of the geographic area 516 may be determined based on a distance between the average geographic location and one or more locations associated with the access points. When the current location object 514 is selected, a particular current location bookmark can be placed in the bookmark list. If the particular current location bookmark has been previously set in the bookmark list, the old bookmark information may be replaced, for example, by new current location information. In some implementations, the particular current location bookmark is tied to the centroid of the geographic area 516. That is, the particular current location bookmark may include coordinates of the centroid of the geographic area 516. The geographic area 516 may be based on location data determined or estimated using location instructions stored in a memory device of the mobile device 500. The geographic area 516 may be illustrated, for example, by a circle, rectangle, square, hexagon, or other enclosed area with crosshairs, or by some other distinguishing element, to distinguish the geographic area 516 from the map 502.

In some implementations, the geographic area 516 can indicate an area in which the mobile device 500 is determined or estimated to be located, and the geographic area may not necessarily be centered around the actual current location of the mobile device 500. In this example, the mobile device 500 may be located off-center within the geographic area. In another example, the geographic area 516 can be centered around the estimated current location of the mobile device 500.

When the current location object 514 is tapped or selected, the mobile device 500 can center the map view on the geographic area 516. In some implementations, the zoom level of the map may be adjusted based on the accuracy or precision of the location data or the technology, system, or service providing the location data. For example, when the mobile device 500 is unable to receive GPS signals, the map may be zoomed out due to lower accuracy and its location determined using the access point data. If the mobile device 500 is able to determine its current location using GPS location data, the map may be magnified for greater accuracy. In some implementations, the zoom level can be based on the speed of the mobile device 500 (e.g., the map can be zoomed out at higher speeds and zoomed in when the mobile device 500 is not moving). A combination of accuracy or precision and speed may also be used.

If all of the methods for retrieving location-based data fail (e.g., when the mobile device 500 is not within communication range of any access point, or when the validity checker 366 determines that no areas exist that can be associated with any access points to which the mobile device 500 can connect), and no other systems or services are available to determine or estimate the current location of the mobile device 500, then an error may be displayed to the user and no geographic area is displayed on the map 502. The error may for example comprise a message informing the user about the failure and possibly one or more reasons for the failure.

The current location object 514 can be selected to, for example, activate the estimation and display of the geographic area 516 on the map 502 to obtain a route to or from the estimated current location (i.e., the centroid of the geographic area 516), to send the estimated current location of the mobile device 500 to a friend (e.g., so that the friend can go to the same location), or to create a bookmark for the estimated current location.

Exemplary System architecture

Fig. 6 is a block diagram of an exemplary system architecture 600 for implementing the features and operations described with reference to fig. 1-5. Other architectures are possible, including architectures with more or fewer components. In some implementations, the architecture 600 includes one or more processors 602 (e.g., dual cores)A processor), one or more output devices 604 (e.g., an LCD), one or more network interfaces 606, one or more input devices 608 (e.g., a mouse, a keyboard, a touch-sensitive display), and one or more computer-readable media 612 (e.g., RAM, ROM, SDRAM, a hard disk, a compact disk, flash memory, etc.). These components may exchange communications and data via one or more communication channels 610 (e.g., a bus), and the communication channels 610 may use various hardware and software to facilitate the transfer of data and control signals between the components.

The term "computer-readable medium" refers to any medium that participates in providing instructions to processor 602 for execution, including without limitation, non-volatile media (e.g., optical or magnetic disks), volatile media (e.g., memory), and transmission media. Transmission media includes, but is not limited to, coaxial cables, copper wire and fiber optics.

As described with reference to fig. 1-5, the computer-readable medium 612 may also include an operating system 614 (e.g., Macserver，NT server), a network communication module 616, a database interface 620, a data collection module 630, a data distribution module 640, and a location calculation module 650. The operating system 614 may be multi-user, multi-processing, multi-tasking, multi-threaded, real-time, and the like. The operating system 614 performs basic tasks including, but not limited to: identify inputs from devices 606, 608 and provide outputs to devices 606, 608; recording and managing files and directories on a computer-readable medium 612 (e.g., a memory or a storage device); controlling the peripheral device; and manages traffic on one or more communication channels 610. The network communication module 616 includes various components for establishing and maintaining network connections (e.g., software for implementing communication protocols such as TCP/IP, HTTP, etc.). Database interface 620 may include an interface to one or more databases (e.g., data point database 360 and location database 372) on the file system. The database may be organized in a hierarchical folder structure, with the folders mapping to directories in the file system. Data collection module 630 can include components for collecting data from a plurality of mobile devices wirelessly connected to system 600 through access points or through other communication channels (e.g., a cellular network). Data distribution module 640 can perform various functions for transmitting location data associated with access points of a wireless communication network to computing devices, including mobile devices 108 and 110. The location calculation module 650 can include one or more components for performing a multi-pass analysis of locations received from the mobile device 108.

Architecture 600 can be included in any device capable of holding (host) a database application. Architecture 600 may be implemented in a parallel processing or peer-to-peer infrastructure or on a single device having one or more processors. The software may include multiple software components or may be a single piece of code.

The described features can be implemented advantageously in one or more computer programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. A computer program is a set of instructions that can be used, directly or indirectly, in a computer to perform a certain activity or bring about a certain result. A computer program can be written in any form of programming language (e.g., Objective-C, Java), including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, browser-based web application, or other unit suitable for use in a computing environment.

Suitable processors for the execution of a program of instructions include, by way of example, both general and special purpose microprocessors, and the sole processor or one of multiple processors or cores of any kind of computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for executing instructions and one or more memories for storing instructions and data. Generally, a computer will also include, or be operatively coupled to communicate with, one or more mass storage devices for storing data files; these devices include magnetic disks, such as internal hard disks and removable disks; magneto-optical disks; and an optical disc. Storage devices suitable for tangibly embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and memory may be supplemented by, or incorporated in, ASICs (application-specific integrated circuits).

To provide for interaction with a user, the features can be implemented on a computer having a display device, such as a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, such as a mouse or a trackball, by which the user can provide input to the computer.

The features can be implemented in a computer system that includes a back-end component, such as a data server, or that includes a middleware component, such as an application server or an Internet server, or that includes a front-end component, such as a client computer having a graphical user interface or an Internet browser, or any combination of them. The components of the system can be connected by any form or medium of digital data communication, such as a communication network. Examples of communication networks include, for example, a LAN, a WAN, and the computers and networks forming the Internet.

The computer system may include a client and a server. A client and server are generally remote from each other and typically interact through a network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

Exemplary Mobile device architecture

Fig. 7 is a block diagram of an exemplary architecture 700 of a mobile device. The mobile device may be, for example, a handheld computer, a personal digital assistant, a cellular telephone, an electronic tablet, a network device, a camera, a smartphone, an Enhanced General Packet Radio Service (EGPRS) mobile telephone, a network base station, a media player, a navigation device, an email device, a game console, or a combination of any two or more of these data processing devices or other data processing devices.

The mobile device may include a memory interface 702, one or more data processors, image processors and/or central processing units 704, and a peripheral interface 706. The memory interface 702, the one or more processors 704, and/or the peripherals interface 706 can be separate components or can be integrated in one or more integrated circuits. The various components in the mobile device 100 may be coupled by one or more communication buses or signal lines.

The sensors, devices, and subsystems can be coupled to the peripheral interface 706 to facilitate a number of functions. For example, a motion sensor 710, a light sensor 712, and a proximity sensor 714 may be coupled to the peripheral interface 706 to facilitate orientation, lighting, and proximity functions of the mobile device. A location processor 715 (e.g., a GPS receiver) may be connected to the peripheral interface 706 in order to provide geolocation. An electronic magnetometer 716 (e.g., an integrated circuit chip) can also be connected to peripherals interface 706 to provide data that can be used to determine the direction of magnetic north.

A camera subsystem 720 and an optical sensor 722, for example, a Charge Coupled Device (CCD) or Complementary Metal Oxide Semiconductor (CMOS) optical sensor, may be used to facilitate camera functions, such as recording photographs and video clips.

Communication functions may be facilitated by one or more wireless communication subsystems 724, and wireless communication subsystems 724 may include radio frequency receivers and transmitters and/or optical (e.g., infrared) receivers and transmitters. The specific design and implementation of the communication subsystem 724 may be dependent upon one or more communication networks over which the mobile device is intended to operate. For example, the mobile device may include communication subsystem 724 designed to operate over a GSM network, a GPRS network, an EDGE network, a Wi-Fi or WiMax network, and a Bluetooth network. In particular, wireless communication subsystem 724 may include a hosting protocol (HOTING PROTOCOL) whereby devices may be configured as base stations for other wireless devices.

The audio subsystem 726 may be coupled to a speaker 728 and a microphone 730 to facilitate voice-enabled functions, such as voice recognition, voice replication, digital recording, and telephony functions.

The I/O subsystem 740 may include a touchscreen controller 742 and/or other input controller(s) 744. The touch screen controller 742 may be coupled to a touch screen 746 or a touchpad. Touch screen 746 and touch screen controller 742 can detect contact and movement or break thereof, for example, using any of a variety of touch sensitive technologies, including but not limited to capacitive, resistive, infrared, and surface acoustic wave technologies, as well as other proximity sensor arrays or other elements for determining one or more points of contact with touch screen 746.

Other input controller(s) 744 may be coupled to other input/control devices 748, such as one or more buttons, toggle switches, a thumb wheel, an infrared port, a USB port, and/or a pointer device such as a stylus. The one or more buttons (not shown) may include up/down buttons for volume control of the speaker 728 and/or the microphone 730.

In one implementation, pressing the button for a first duration may unlock the touch screen 746; pressing the button for a second duration that is longer than the first duration may turn power to the mobile device on or off. The user may customize the functionality of one or more buttons. The touch screen 746 may also be used, for example, to implement virtual or soft buttons and/or a keyboard.

In some implementations, the mobile device can present recorded audio and/or video files, such as MP3, AAC, and MPEG files. In some implementations, the mobile device may include an MP3 player (such as an iPod)^TM) The function of (c). The mobile device may therefore include a pin connector that is compatible with the iPod. Other input/output and control devices may also be used.

Memory interface 702 can be coupled to memory 750. Memory 750 may include high-speed random access memory and/or non-volatile memory, such as one or more magnetic disk storage devices, one or more optical storage devices, and/or flash memory (e.g., NAND, NOR). The memory 750 may store an operating system 752, such as Darwin, RTXC, LINUX, UNIX, OS X, WINDOWS, or an embedded operating system, such as VxWorks. Operating system 752 may include instructions for handling basic system services and for performing hardware dependent tasks. In some implementations, the operating system 752 can include a kernel (e.g., UNIX kernel).

Memory 750 may also store communication instructions 754 to facilitate communication with one or more additional devices, one or more computers, and/or one or more servers. The memory 750 may include: graphical user interface instructions 756 to facilitate graphical user interface processing; sensor processing instructions 758 to help implement sensor-related processing and functions; phone instructions 760 to facilitate phone-related processes and functions; electronic messaging instructions 762 to help implement processes and functions related to electronic messaging; web browsing instructions 764 to facilitate web browsing-related processes and functions; media processing instructions 766 to facilitate processing and functions related to media processing; GPS/navigation instructions 768 to facilitate GPS and navigation-related processes and functions; camera instructions 770 to facilitate camera-related processes and functions; magnetometer data 772 and calibration instructions 774 to help implement magnetometer calibration. Memory 750 can include location instructions 776 that can be used to transmit a current location to an access point and determine an estimated current location based on location data associated with access points that the mobile device is within its communication range. Memory 750 may also store other software instructions (not shown), such as security instructions; network video instructions to facilitate network video related processing and functions; and/or online shopping instructions to facilitate processes and functions related to online shopping. In some implementations, the media processing instructions 766 are divided into audio processing instructions and video processing instructions to facilitate audio processing-related processes and functions and video processing-related processes and functions, respectively. An activation record and an International Mobile Equipment Identity (IMEI) or similar hardware identifier may also be stored in the memory 750.

Each of the instructions and applications listed above may correspond to a set of instructions for performing one or more of the functions described above. The instructions need not be implemented as separate software programs, procedures or modules. Memory 750 may include additional instructions or fewer instructions. In addition, various functions of the mobile device may be implemented in hardware and/or software, including in one or more signal processing and/or application specific integrated circuits.

Several implementations of the present invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. For example, a device that knows location is said to be capable of using GPS. Location aware mobile devices may also be based on triangulation or other techniques. The cells are shown in the figures as being generally rectangular in shape. The actual shape of the cell may vary. The position is described as a "circle". The term "circle" as used in this specification may include any geometric shape (e.g., oval, square, convex or concave polygon, or free shape) that is not necessarily a perfect circle, but is closed or has a closed appearance. The radius of a geometric shape that is not perfectly circular may include the average distance between various points on the boundary of the geometric shape and the center of the geometric shape. WiFi and WiMax networks are used as examples. Other wireless technologies (e.g., cellular networks) may also be used. Accordingly, other implementations are within the scope of the following claims.

Claims (27)

1. A method performed by a computer, comprising:

receiving a set of locations from a first mobile device located within a communication range of an access point of a wireless communication network;

determining a geographic location associated with the access point based on the received average of the set of locations;

assigning the access point and the geographic location associated with the access point to a cell on a geographic grid based on the number of locations in the received set of locations and the age of the locations in the received set of locations; and

providing a geographic location associated with the access point and a geographic location of an access point assigned to a cell neighboring the cell on the geographic grid to a second mobile device.

2. The method of claim 1, wherein the access point is identified by a Media Access Control (MAC) address of the access point, the MAC address associated with the set of locations.

3. The method of claim 1, wherein the wireless communication network is a Wireless Local Area Network (WLAN) using Institute of Electrical and Electronics Engineers (IEEE)802.11 based protocols.

4. The method of claim 1, wherein determining the geographic location associated with the access point comprises:

applying a multi-pass analysis to the received set of locations, including excluding at least one location from the set of locations in each pass of the analysis.

5. The method of claim 4, wherein applying the multi-pass analysis comprises:

(a) calculating an average geographic location using the set of locations;

(b) calculating a distance between the average geographic location and a location in the set of locations;

(c) excluding at least one location from the set of locations based on a distance between the average geographic location and the at least one location;

(d) repeating (a), (b), and (c) until an exit condition is satisfied; and

(e) specifying a geographic location associated with the access point using a circle centered at the average geographic location and having a radius based on at least one calculated distance.

6. The method of claim 5, wherein the exit condition is satisfied when a number of repetitions reaches a threshold number.

7. The method of claim 5, wherein the exit condition is satisfied when a radius of the circle is below a threshold radius.

8. The method of claim 1, wherein the cell on the geographic grid comprises a generally rectangular geographic area identifiable on the geographic grid by a latitude and longitude of an identification point of the geographic area.

9. The method of claim 1, wherein the geographic grid defines a three-dimensional space, and the cell comprises a three-dimensional enclosure identifiable on the geographic grid by a latitude, a longitude, and an altitude of an identifying point within the enclosure.

10. A system, comprising:

one or more computers configured to perform operations comprising:

receiving a set of locations from a first mobile device located within a communication range of an access point of a wireless communication network;

determining a geographic location associated with the access point based on the received average of the set of locations;

assigning the access point and the geographic location associated with the access point to a cell on a geographic grid based on the number of locations in the received set of locations and the age of the locations in the received set of locations; and

providing a geographic location associated with the access point and a geographic location of an access point assigned to a cell neighboring the cell on the geographic grid to a second mobile device.

11. The system of claim 10, wherein the access point is identified by a Media Access Control (MAC) address of the access point, the MAC address associated with the set of locations.

12. The system of claim 10, wherein the wireless communication network is a Wireless Local Area Network (WLAN) using Institute of Electrical and Electronics Engineers (IEEE)802.11 based protocols.

13. The system of claim 10, wherein determining the geographic location associated with the access point comprises:

applying a multi-pass analysis to the received set of locations, including excluding at least one location from the set of locations in each pass of the analysis.

14. The system of claim 13, wherein applying the multi-pass analysis comprises:

(a) calculating an average geographic location using the set of locations;

(b) calculating a distance between the average geographic location and a location in the set of locations;

(c) excluding at least one location from the set of locations based on a distance between the average geographic location and the at least one location;

(d) repeating (a), (b), and (c) until an exit condition is satisfied; and

(e) specifying a geographic location associated with the access point using a circle centered at the average geographic location and having a radius based on at least one calculated distance.

15. The system of claim 14, wherein the exit condition is satisfied when a number of repetitions reaches a threshold number.

16. The system of claim 14, wherein the exit condition is satisfied when a radius of the circle is below a threshold radius.

17. The system of claim 10, wherein the cells on the geographic grid include a generally rectangular geographic area identifiable on the geographic grid by a latitude and longitude of an identification point of the geographic area.

18. The system of claim 10, wherein the geographic grid defines a three-dimensional space, and the cells comprise a three-dimensional enclosure identifiable on the geographic grid by a latitude, a longitude, and an altitude of an identified point within the enclosure.

19. A computer program product tangibly stored on a storage device, the computer program product operable to cause data processing apparatus to perform operations comprising:

receiving a set of locations from a first mobile device located within a communication range of an access point of a wireless communication network;

determining a geographic location associated with the access point based on the received average of the set of locations;

assigning the access point and the geographic location associated with the access point to a cell on a geographic grid based on the number of locations in the received set of locations and the age of the locations in the received set of locations; and

providing a geographic location associated with the access point and a geographic location of an access point assigned to a cell neighboring the cell on the geographic grid to a second mobile device.

20. The product of claim 19, wherein the access point is identified by a Media Access Control (MAC) address of the access point, the MAC address associated with the set of locations.

21. The product of claim 19, wherein the wireless communication network is a Wireless Local Area Network (WLAN) using Institute of Electrical and Electronics Engineers (IEEE)802.11 based protocols.

22. The product of claim 19, wherein determining the geographic location associated with the access point comprises:

applying a multi-pass analysis to the received set of locations, including excluding at least one location from the set of locations in each pass of the analysis.

23. The article of manufacture of claim 22, wherein applying the multi-pass analysis comprises:

(a) calculating an average geographic location using the set of locations;

(b) calculating a distance between the average geographic location and a location in the set of locations;

(c) excluding at least one location from the set of locations based on a distance between the average geographic location and the at least one location;

(d) repeating (a), (b), and (c) until an exit condition is satisfied; and

(e) specifying a geographic location associated with the access point using a circle centered at the average geographic location and having a radius based on at least one calculated distance.

24. The product of claim 23, wherein the exit condition is satisfied when a number of repetitions reaches a threshold number.

25. The product of claim 23, wherein the exit condition is satisfied when a radius of the circle is below a threshold radius.

26. The product of claim 19, wherein the cells on the geographic grid include a generally rectangular geographic area identifiable on the geographic grid by a latitude and longitude of an identification point of the geographic area.

27. The product of claim 19, wherein the geographic grid defines a three-dimensional space, and the cells comprise a three-dimensional enclosure identifiable on the geographic grid by a latitude, a longitude, and an altitude of an identifying point within the enclosure.