CN102204374B - 管理用于基于网络的定位系统的位置数据库 - Google Patents

Abstract

描述了用于管理位置数据库的方法、程序产品和系统。服务器可以从位于无线通信网络的接入点的通信范围内的知道位置的移动设备(例如，能够使用GPS的设备)接收位置信息。服务器可以为每个接入点利用接收到的位置计算平均地理位置。基于平均地理位置，服务器可以将接入点分配给地理网格的单元。服务器可以基于接收的数据和接入点的流行度、稳定性、寿命和新鲜度，对每个单元中的接入点进行过滤。当第二移动设备连接到单元中的接入点时，可以基于该单元和邻近单元中的接入点的位置确定第二移动设备的位置。

Description

管理用于基于网络的定位系统的位置数据库

技术领域

本公开一般地涉及为移动设备确定地理位置。

背景技术

无线通信网络可以采用各种技术，以便设备无线地通信。例如，无线局域网(WLAN)可以包括使用无线电波而不是导线在网络的节点(例如，设备)之间进行通信的局域网(例如，覆盖相对小的物理区域的计算机网络，这样的物理区域例如家庭、办公室、或一小群建筑物，诸如学校)。WLAN技术的某些例子包括WiFi，其可以包括基于任何电气和电子工程师协会(IEEE)802.11标准的任何WLAN产品。

发送方和接收方之间的无线连接可以采用射频(RF)技术，即，采用与无线电波传播相关联的电磁频谱中的频率。WiFi中使用的某些示例性无线电频率是2.5吉赫兹(GHz)或5GHz。当RF电流被提供给天线时，可以产生电磁场。该电磁场可以在空中传播。一种无线通信网络的组件可以是接入点(AP)。接入点可以允许无线移动设备与有线网络通信。接入点的一种功能可以是广播可以由具有无线适配器的计算机或无线移动设备检测和“收听”到的无线信号。

WiFi网络的接入点可以覆盖某个地理区域，该地理区域由接入点发送和接收的信号的强度和该地理区域的物理特性确定。数量可变的移动设备可以位于接入点的通信范围内。一个移动设备可以同时位于多个接入点的通信范围内。如果接入点的位置是已知的，通过基于所接收的来自接入点的信号的强度对移动设备的位置进行三角测量，移动设备有时可以利用该移动设备能够与之通信的接入点的位置来确定该移动设备的位置。

发明内容

描述了用于管理基于网络的定位系统的位置数据库的方法、程序产品和系统。服务器计算机可以从位于无线通信网络的接入点的通信范围内的知道位置(location-aware)的移动设备(例如，能够使用GPS的设备)接收位置信息。服务器计算机可以为每个接入点利用接收到的位置来计算平均地理位置。基于所述平均地理位置，服务器计算机可以将接入点分配给地理网格的单元。服务器计算机可以基于接收的数据和接入点的流行度、稳定性、寿命和新鲜度，对每个单元中的接入点进行过滤。服务器计算机可以将接入点的标识符与所述平均地理位置相关联地存储在位置数据库中。

移动设备可以使用该移动设备可以与之连接的接入点的位置确定该移动设备的位置。在连接到地理网格上的单元中的接入点后，移动设备可以请求和接收该接入点的位置信息、该单元中的其它接入点的位置、以及与该单元邻近的单元中的接入点的位置。移动设备可以基于接收到的信息识别与该移动设备的通信范围内的接入点相关联的位置。移动设备可以使用识别出的位置计算平均地理位置。移动设备还可以计算每个位置与所计算出的平均值之间的距离。移动设备可以排除与平均值相距足够远的位置。移动设备可以重复所述计算和排除，直到为该平均地理位置实现了某个精度级别。移动设备可以在移动设备的地图显示上显示该信息。

可以实施用于管理基于网络的定位系统的位置数据库的技术，以实现下列示例性优点。当无线通信网络的某个接入点的实际位置未知时，一个地理区域可以与该接入点相关联。该地理区域可以对应于位于该接入点的通信范围内的实际移动设备可能位于的区域，而不是该接入点的实际位置。可以基于来自移动设备的实时数据估计该地理区域，该实时数据可被频繁更新，并且因此可以提供最新的位置信息。如果接入点已离开或被关闭，该接入点可从数据库中被去除，以避免无效的位置确定。可以基于在一天中的各个时间从移动设备接收的数据来计算地理区域，从而地理区域可以对应于各种使用模式，例如，路上时间(commutehour)、工作时间、或晚上。

与地理区域相关联的接入点可用于确定位于该接入点的通信范围内的不能使用GPS的移动设备的位置。接入点和移动设备之间的数据传输可以在移动设备空闲时进行，以避免干扰移动设备和接入点之间的正常通信。由于利用接入点的位置来确定移动设备的位置的系统可以传输直接位于移动设备的通信范围内的接入点的位置以及在邻近区域中的接入点的位置，因此，该系统可以自我限制对移动设备的带宽的消耗。因此，即使当移动设备移动时，频繁更新和重传也是不必要的。每个单元中的接入点的过滤机制可以进一步限制在每次传输中传输给移动设备的数据量。与例如使用信号强度来估计位置相比，移动设备可以更准确地估计其位置，这是由于信号强度可能由于各种干扰而改变。当例如GPS信号弱时(例如，在建筑物内)，能够使用GPS的移动设备可以利用无线接入点的位置。

在下面的附图和描述中提出了管理基于网络的定位系统的位置数据库的一种或多种实现方式的细节。从该描述、附图和权利要求书中，将明了管理位置数据库的其它特征、方面和优点。

附图说明

图1A是管理位置数据库的技术的概览。

图1B示出了管理三维空间中的位置数据库的技术。

图2A-2C示出了利用移动设备确定与WLAN中的接入点相关联的位置的示例性阶段。

图2D示出了在三维空间中利用移动设备确定与WLAN中的接入点相关联的位置的示例性阶段。

图3A和3B是示出了利用移动设备确定与WLAN中的接入点相关联的位置的示例性处理的流程图。

图3C是示出了实现管理位置数据库的技术的示例性系统的框图。

图4A示出了利用基于网络的定位系统中的位置数据库来确定移动设备的位置的技术。

图4B是示出了利用位置数据库来确定移动设备的位置的示例性处理的流程图。

图4C是示出了确定移动设备的位置的示例性自适应多遍处理的流程图。

图5示出了利用无线接入点的位置确定移动设备的位置的示例性用户界面。

图6是用于实现参考图1-5描述的特征和操作的示例性系统体系结构的框图。

图7是移动设备的示例性体系结构的框图。

在各个附图中，类似的附图标记表示类似的元件。

具体实施方式

管理位置数据库的概述

图1A是管理基于网络的定位系统的位置数据库的技术的概览。无线局域网(WLAN)可以是包括若干接入点105的无线通信网络。接入点105可以包括能够作为用于使无线设备连接到有线网络的通信集线器的硬件设备或计算机软件。多个接入点105可分布在一个区域中(例如，办公楼或机场)。

接入点105可以使用各种通信协议与无线设备(例如，移动设备108和110)通信。在某些实现中，接入点105可以是WiFi^TM网络的接入点，其执行基于电气和电子工程师协会(IEEE)802.11的协议(例如，IEEE802.11a)。在某些实现中，接入点105可以是全球微波接入互操作性(WiMAX)网络的接入点，其执行基于IEEE 802.16的协议(例如，IEEE802.16-2004或IEEE 802.16e-2005)。接入点105可以具有一定通信范围，取决于包括接入点105的配置和物理环境的因素，该通信范围可以从接入点105的位置到达从小于数十米到数百米的任何位置。当多个移动设备108和110位于接入点105的通信范围内时，移动设备108和110可以连接到接入点。相应地，单个移动设备108或110可以访问多个接入点105以便连接。移动设备108和110可以基于各种因素选择移动设备108和110可以连接到的特定接入点105。例如，该选择可以基于移动设备108是否被授权连接到接入点105a，或接入点105a是否可以为到移动设备108的无线连接提供最强的信号。

系统可以确定与接入点105相关联的位置区域115。可以这样计算位置区域115，使得它们指示位于接入点105通信范围内的移动设备108可能位于何处。系统可以基于来自位于接入点105通信范围内的移动设备108的已知位置来进行该确定。移动设备108可以是知道位置(location-aware)的移动设备，例如，能够使用GPS的移动设备，其内置有或连接到可以接收全球定位系统(GPS)信号并利用GPS信号确定位置的接收器。知道位置的移动设备108在图1A中被表示为黑三角。当知道位置的移动设备108位于特定接入点105(例如，接入点105a)的通信范围内时，知道位置的移动设备108可以将这些设备的位置传输给接入点105a。接入点105a可以将该传输以及接入点105a的标识符转发到系统。系统可以确定位于接入点105a的通信范围内的任何移动设备108或110最可能位于的估计位置区域115a。在本说明书中，估计的位置区域115被称为存在区域(presence area)，以表明，当位于特定接入点105的通信范围内时移动设备108或110可能存在。

为了计算存在区域115，系统可以应用迭代过程(例如，通过执行多遍分析)。该迭代过程可以以圆的形式确定与接入点(例如，接入点105)相关联的存在区域(例如，存在区域115)。该圆可以具有与基于位于接入点105通信范围内的知道位置的移动设备108的位置而计算的平均地理位置相对应的中心。该圆可以具有与误差幅度(error margin)相对应的半径，可以根据例如移动设备108的位置和平均地理位置之间的距离确定该误差幅度。下面将参考图2和3描述关于该迭代过程的进一步细节。可以周期性地执行该迭代过程(例如，每6个小时)，以便捕捉在一天的不同时间期间的不同的无线接入使用模式，以及捕捉接入点105的可能的移动。

该系统可将存在区域115的信息发送给位于接入点105通信范围内的移动设备，包括不能使用GPS的移动设备(例如移动设备110)，从而进行接收的移动设备可以确定使用存在区域115的设备的估计位置。例如，如果移动设备110位于接入点105b的通信范围内，则移动设备110的位置可被估计为与跟接入点105b相关联的存在区域115b相一致。

在给定区域中(例如，机场)，可能存在大量接入点105。另外，由于移动设备110可以移动，发送不直接位于移动设备110的通信范围内、但是与移动设备110足够靠近的接入点的位置可能是合乎常理的，从而移动设备110可以使用这些位置来跟踪其移动。为了避免向移动设备110发送大量位置数据，系统可以对接入点105和存在区域115进行过滤，从而仅有有限数目的接入点(例如，接入点105a)的位置数据而不是世界上存在的每个接入点的位置数据被传输。过滤可以基于各种因素，包括位置115和接入点105的流行度、稳定性、寿命和新鲜度。

为了过滤位置115和接入点105，系统可以创建包含单元102的地理网格100。单元102可以是形状大体为矩形的多边形，该多边形对应于地理网格100上可由地理区域的标识点(例如，中心或拐角)的纬度和经度、以及大小(例如，以经度度数衡量的长度和以维度度数衡量的宽度)来标识的地理区域。每个单元102可被用作可包含一定数量的位置的容器。例如，单元102可以是矩形，其长度是0.0005度子午线(近似为56米)，并且其宽度是0.0005度纬线(以米为单位的宽度可以根据纬度而改变)。单元102可被配置为拥有与接入点105相对应的若干(例如3个)存在区域115。在某些实现中，如果存在区域115的中心位于单元102的边界内，则单元102可以“拥有”存在区域115。可以基于一个或多个可靠性因素，从位于单元102中的所有存在区域115中选择存在区域115。该选择可以基于各种准则，诸如，流行度、稳定性、寿命和新鲜度。

特定接入点(例如，接入点105b)和与该接入点相关联的存在区域(例如，存在区域115)不必位于相同单元102中。例如当接入点105b位于单元102a中的一个建筑上，并且位于接入点105b的通信范围内的大部分移动设备108位于单元102b中的另一个建筑中时，这可能发生。在某些实现中，系统可以忽略接入点105b的实际位置。

当移动设备110连接到接入点(例如，接入点105a，其相关联的存在区域115a位于单元102c中)时，或以其它方式(例如，通过蜂窝网络)连接到系统时，移动设备110可以从系统接收位置更新。位置更新可以包括位于存在区域115a所位于的相同单元(例如，单元102c)中的所有存在区域115。位置更新还可以包括位于在地理网格100上与单元102c邻近的其它单元102(例如，单元102a和单元102b)中的存在区域115。

当移动设备110连接到接入点105a时，移动设备110可以检测可用的其它接入点105(例如，接入点105b)。移动设备110可以识别可用的接入点的存在区域(例如，存在区域115a和115b)。移动设备110可以使用各种算法计算移动设备110的当前位置。例如，当仅识别出一个存在区域115a时，移动设备110可以将存在区域115a指定为移动设备110的当前位置。当识别出两个或更多个存在区域115时，移动设备110可以使用迭代过程(例如，多遍分析)来计算其当前位置。该迭代过程可以计算这些存在区域的平均位置，计算这些存在区域与该平均位置之间的距离，并且排除与该平均位置相距最远的存在区域。移动设备110可以重复该迭代，直到满足用于确定移动设备110的位置的精度要求。移动设备110可以将该平均位置指定为移动设备110的当前位置，并且在地图显示设备上显示该平均位置。

在某些实现中，在移动设备110上从系统接收的位置更新可以包括许多邻近单元，从而可以覆盖围绕存在区域115a的足够大的区域(例如，1或2平方公里)。基于覆盖该大区域的位置更新，移动设备110可以避免在移动设备110移动时必须请求频繁的更新。当例如移动设备110空闲或具有可用通信带宽时，移动设备110可以有机会接收更新的存在区域信息。

图1B示出了管理三维空间中的位置数据库。某些知道位置的移动设备108(例如，能够使用GPS的设备)可以在三维空间中标识位置。这些位置可以以纬度、经度和高度表示。高度可被表示为例如从海平面以米测量的海拔。当需要移动设备的高度来定位该移动设备时，可能希望在三维空间中定位移动设备。例如，可以使用高度来确定移动设备处于高层建筑中的哪一层。移动设备108在三维空间中的位置可被显示在将海拔作为注释的二维地图上，或被显示在三维地图上。

移动设备108可以连接到接入点126。移动设备108可以是可将其位置传输给系统的知道位置的移动设备，所述位置包括纬度、经度和高度坐标。该系统可以基于从移动设备108接收的纬度、经度和高度坐标来计算平均位置。以平均位置为中心并且以误差幅度为半径的三维空间124可与接入点126相关联。空间124可以表示当移动设备位于接入点126的通信范围内时，该移动设备可能位于的空间。在本说明书中，空间124被称为存在空间。

系统向位于接入点126通信范围内的移动设备发送关于存在空间124的信息。接收到该信息的移动设备可以利用该信息来确定其地理位置。系统可以将三维地理空间划分为三维网格120。三维网格120可以由三维单元122组成。每个三维单元122可以具有与地理网格100的单元102相对应的基底。每个三维单元122可以具有作为一个维度的高度(例如，以米衡量)。如果存在空间124的中心在单元122中，则存在空间124可被称为位于单元122中。系统可以基于存在空间的流行度(例如，形成了多少从存在空间中的移动设备108到接入点126的连接)、存在空间124的稳定性(例如，存在空间124有多么稳定)、接入点126的寿命(例如，接入点126已经存在了多久)、和存在空间124的新鲜度(例如，来自位于接入点126通信范围内的移动设备108的最新位置传输是何时接收到的)，来限制单元122中的存在空间的数目。

系统可以基于三维网格120的三维单元122将关于存在空间124和邻近存在空间的信息传输给位于接入点126通信范围内的移动设备(例如，移动设备110)。移动设备110可以利用该信息估计移动设备110在三维空间中的当前位置，并且在三维地图上显示所估计的当前位置。

示例性的用于管理位置数据库的服务器端处理和系统

图2A-2C示出了管理位置数据库的示例性阶段。为了方便起见，将借助于包括实现这些技术的服务器的基于网络的定位系统来描述这些技术。

图2A示出了可用于确定与接入点105相关联的存在区域的多遍分析的示例性阶段。接入点105可以具有覆盖区域202，该覆盖区域202可以由接入点105的发射器的信号强度和其它因素(例如，接入点105周围的地理区域的物理特性)来确定。位于覆盖区域202内的移动设备108可以无线地连接到接入点105。接入点105可以允许移动设备108通过各种网关连接到有线网络。有线网络可以包括数据网络(例如，Internet)、公共交换电话网络(PSTN)、其它数字或模拟网络、或以上的组合。

移动设备108可以包括知道位置的移动设备(例如，能够使用GPS的移动设备)。每个知道位置的移动设备108(以图2A的黑三角表示)可以检测其当前地理位置。该当前地理位置可以用包括移动设备108的纬度和经度的地理坐标来表示。当移动设备108与接入点105通信时，移动设备108可以通过接入点105将位置信息传输给系统。该位置信息可以与接入点105的标识符(例如，接入点105的媒体访问控制(MAC)地址)相关联。系统可以利用从多个移动设备108接收的位置信息来确定可以与接入点105相关联的存在区域。该存在区域不一定围住了接入点100实际位于的位置。该存在区域也不一定与覆盖区域202的几何位置或形状相对应，尽管存在区域可以位于覆盖区域202内。

具有覆盖区域202的移动设备108的分布可以对应于移动设备108在特定时刻(例如，接入点105所位于的时区的本地时间上午8：30)的快照(snapshot)。每个移动设备108可以与单个位置相关联。具有覆盖区域202的移动设备108的分布也可以对应于移动设备108在一段时间(例如，从上午4点到上午10点的6个小时)上的位置。每个移动设备108可以与多个位置相关联(例如，当移动设备108移动时)。与多个位置相关联的单个移动设备108可以由系统中的多个位置表示，如图2A中的多个三角形所示的。

服务器可以确定从移动设备108接收的一组位置的平均地理位置。这一组位置可以包括在特定时刻或在特定时间段期间从移动设备108接收的位置。平均地理位置可被指定作为圆204a所包围的区域的中心205。圆204a的中心不必与接入点105的位置一致。服务器可以计算平均地理位置与这一组位置中的每个位置之间的距离，并且识别一个或多个离群点(outlier)。离群点可以是这一组位置中与平均地理位置相距最远的位置。到中心的距离超过某个阈值的离群点(例如，位置210)可以从该组位置中被排除。圆204a可以具有半径206，半径206对应于平均地理位置与排除离群点之后的当前一组位置中的位置之间的最长距离。

图2B示出了多遍分析中在图2A的阶段之后的示例性阶段。到图2A的平均地理位置(圆204a的中心205)的距离超过某个阈值的位置已从该组位置中被排除。所述阈值可被配置为使得排除某个百分比的位置(例如，图2A的位置中的5％)。可以基于该组位置中剩下的位置(例如，剩下的95％的位置)来计算新的平均地理位置。新的平均地理位置可以是例如圆204b的中心225。在各种实现中，计算新的平均地理位置可以包括对该组位置中的剩余位置进行平均，选择该组位置中的中间地理位置(例如，通过选择中间纬度或中间经度)，或应用其它算法。用于计算平均地理位置的算法在多遍分析的每一遍中可以是相同的，或可以在每遍中彼此不同。

当排除了离群点位置时，由圆204b包含的区域可以小于在前一遍中确定的由圆204a包含的区域。该较小的区域可以反映增加的计算精度。圆204b的中心225不一定与圆204a的中心205一致。在某些实现中，圆204b的半径216可以对应于与圆204b的中心225相距最远的移动设备108的剩余位置。半径216可以表示在当前这一遍中计算的存在区域的新的估计的误差幅度。

图2C示出了多遍分析的示例性的最终阶段。当满足一定的退出条件时，系统可以在最终阶段之后终止迭代过程。最终阶段可以产生与一群聚集的移动设备108的位置相对应的最终平均地理位置。最终平均地理位置可被表示为圆204c的中心235。圆204c可以具有与最终误差幅度相对应的半径，该半径基于最终平均地理位置与这一群聚集的位置中的位置之间的距离。通过接入点105的标识符(例如，MAC地址)，圆204c可被指定为与接入点105相关联的存在区域。

服务器可以基于各种因素确定是否要在位置数据库中包括接入点105的标识符和相关联的存在区域。例如，服务器可以对地理网格100的单元102中的存在区域的数目进行计数，并且基于流行度、稳定性和寿命来选择若干存在区域。服务器可以将位置数据库中的存在区域(包括存在区域204c，如果选择了存在区域204c的话)的信息发送给移动设备(例如，移动设备215)，不论移动设备215是否能够使用GPS。

图2D示出了管理三维空间中的位置数据库的示例性阶段。在图2D中，轴X、Y和Z可用于指示三维空间。例如，轴X、Y和Z可以分别表示经度、纬度和高度。为了方便，接入点126的位置被示出为与图2D中的X、Y和Z轴上的零点重合。在某些实现中，接入点126的实际位置(例如，纬度、经度和高度坐标)在计算中是可选的。

图2D的每个三角可以表示位于三维空间中的移动设备的位置。这些位置可以在三维空间的一个平面上具有投影(例如，投影226)。该平面可被定义在任意高度(例如，接入点126的高度)。例如，可由轴X和Y定义该平面。接入点126可以对应于覆盖区域222，覆盖区域222可以由接入点126的信号强度和其它限制因素(例如，信号路径中的地板、天花板、建筑)来确定。

一种多遍分析可以基于从位于单元空间202中的知道位置的移动设备108接收的一组位置，将地理空间与WLAN的接入点126相关联。在该多遍分析的一遍中，可以通过例如对该组位置中的位置的纬度、经度和高度坐标进行平均来确定平均地理位置(例如，空间224的中心)。可以计算平均地理位置与覆盖区域222中的位置之间的距离。位于覆盖区域222内但是与平均地理位置相距足够远的位置可从该组位置和进一步计算中被排除。空间224的半径可以由例如该组位置中的剩余位置与平均地理位置之间的最远距离来确定。

系统可以重复以下阶段：计算一组位置中的平均地理位置、计算该平均地理位置与该组位置中的位置之间的距离、以及基于计算的距离从这组位置中进行排除。可以继续该重复，直到满足退出条件为止。以平均地理位置为中心、其半径基于平均地理位置与该组位置中剩余位置之间的距离的空间可被指定为可以与接入点126相关联的存在空间。

图3A是示出了管理位置数据库的示例性处理300的流程图。可以使用处理300，以便例如确定与WLAN的接入点相关联的存在区域或存在空间。存在区域或存在空间可用于确定不能使用GPS的移动设备的位置。为了方便，将借助于执行处理300的系统来描述处理300。

系统可以从位于接入点105通信范围内的一个或多个第一移动设备108接收(302)一组位置。每个位置可以由一组地理坐标(例如，纬度、经度和高度)表示。该位置可被与接入点105的标识符(例如，MAC地址)相关联。当接入点105与系统通信时，接入点105可自动提供接入点的标识符。在各种实现中，这一组位置可以对应于一个时间段(例如，6个小时，或者从接入点105所位于的时区的上午6点到上午10点)。

在某些实现中，该时间段可被配置为反映一天中各个时间的特定使用模式的特性。位于接入点105通信范围内的移动设备最可能位于的区域可以在一天当中改变，从而指示在特定时间的各种使用模式。例如，该时间段可以对应于“路上时间”、“工作时间”、“夜晚时间”，等等。一天中的时间的特性可以对应于移动设备108的各种使用模式。例如，在路上时间期间，与接入点105相关联的存在区域可以处于或接近高速公路；在工作时间期间，与接入点105相关联的存在区域可以处于或接近办公大楼；在夜晚时间，与接入点105相关联的存在区域可以散开而没有特定的集中点。系统可以基于例如从上午4点到上午10点接收到的位置计算存在区域，并且基于从上午10点到下午4点接收到的位置重新计算，等等。在每个特征时间段中接收到的位置可以集合成系统中的一组位置。这些位置可以任何数据结构(例如，集合、列表、关系型数据库中的数据记录等)存储在耦接到服务器的存储设备上。

系统可以基于接收到的位置的平均值来确定(304)与接入点105相关联的地理位置。该地理位置可以包括上述的存在区域或存在空间。存在区域或存在空间可以通过例如接入点105的MAC地址与接入点105相关联。在某些实现中，确定地理位置可以包括对接收到的一组位置应用多遍算法，包括每一遍从该组位置中排除至少一个位置。确定地理位置可以包括周期性地应用多遍算法。

系统可以基于各种因素，包括接入点105的流行度、地理位置的稳定性和接入点105的寿命，将接入点105和与接入点105相关联的地理位置分配(306)给地理网格上的一个单元(例如，单元102)。在某些实现中，接入点105的流行度可以衡量有多少移动设备108位于接入点105的通信范围内。可以通过例如系统在一段时间内接收到位于接入点105通信范围内的多少移动设备108位置，来测量接入点的流行度。

与接入点105相关联的存在区域的稳定性可以反映，如果该存在区域被用于估计位于接入点105通信范围内的设备的位置，那么该存在区域的可靠性如何。可以通过例如比较由最后两次计算计算出的存在区域，并且确定这些存在区域之间的重叠程度，来测量与接入点105相关联的存在区域的稳定性。重叠程度越高，存在区域越稳定。

接入点105的寿命可以反映与接入点105相关联的数据的质量。例如，在数据库中存在了更长时间的接入点可能比最近添加的接入点更可靠。可以通过位置数据库中的数据的历史来测量接入点105的寿命。

在某些实现中，还可以使用数据的新鲜度来确定是否将与接入点105相关联的存在区域分配给地理网格100的单元102。可以通过系统在多久以前从移动设备108接收到最新位置，来测量数据的新鲜度。

系统可以基于流行度、稳定性、寿命和新鲜度，为位于地理网格100的单元102中的每个存在区域评分。位于单元102中的所有存在区域的至少一部分(例如，三个存在区域，包括与接入点105相关联的存在区域)可被分配给单元102。被分配的接入点和存在区域可用于定位位于接入点105通信范围内的移动设备(例如，移动设备110)。未被分配的存在区域可被存储在位置数据库中以供将来使用。

系统可以将与接入点105相关联的地理位置提供(308)给位于接入点105通信范围内的第二移动设备(例如，移动设备110)。系统还可以向第二移动设备提供位于相同单元中的其它地理位置，以及与分配给邻近单元的接入点相关联的地理位置。这些位置可以根据请求或使用各种推送或广播技术从接入点105被传输给第二移动设备。

在某些实现中，系统可以接收、处理和传输三维位置信息。存在空间(例如，存在空间124)可被分配给地理三维网格(例如，三维网格120)上的三维单元(例如，三维单元122)。这些位置可以根据请求或使用各种推送或广播技术，从接入点126被传输给位于接入点126通信范围内的第二移动设备。

图3B是示出了利用一组位置计算平均地理位置的示例性处理304的流程图。为了方便，将借助于执行处理304的系统来描述处理304。

系统可以利用这一组位置中的位置计算(324)平均地理位置。计算平均地理位置可以包括计算该组中的位置的纬度、经度和高度的平均，并且将位于所计算的平均纬度、经度和高度的位置指定为平均地理位置。在某些实现中，计算平均地理位置可以包括将位于该组中的位置的中间纬度、中间经度和中间高度处的位置指定为平均地理位置。

系统可以计算(326)这一组位置中的位置与平均地理位置之间的距离。在某些实现中，系统可以在欧几里得空间中计算该组中每个位置与平均地理位置之间的线性距离。在某些实现中，系统可以考虑地球的曲率，计算该组中每个位置与平均地理位置之间的测地距离。

在阶段326中计算出的距离可被指定为与一个中心相关联的半径。该中心可以是在阶段324中计算出的平均地理位置，其可以是圆(例如，圆204a)的中心。可以基于该组位置中的一个位置与平均地理位置之间的至少一个距离确定圆的半径。在某些实现中，该半径可以等于平均地理位置和该组中剩余的位置之间的最长距离。在某些实现中，该半径可以是这样的距离：当使用该半径并以该平均地理位置为中心画圆106d时，该圆可以包含该组中一定百分比(例如，80％)的剩余位置。该半径可以表示误差幅度，超出该误差幅度，对不能使用GPS的移动设备的位置估计不太可能在统计上有意义。

系统可以基于平均地理位置和至少一个位置之间的距离从该组中排除(328)该至少一个位置。在某些实现中，系统可以排除到平均地理位置的距离超过某个阈值距离的位置。在多遍分析的每一遍中，通过排除表现为远离位置集群(例如，一群聚集的位置)的位置，系统可以增加所估计的平均地理位置的精度。远离一群聚集位置的位置在估计与接入点105相关联的存在区域时不太有用，并且可被排除。在各种实现中，阈值距离可以从一遍到下一遍改变。在某些实现中，阈值距离可以是到平均地理位置的这样一个距离，其中这一组位置中某个百分比(例如，95％)的位置位于该距离以内。在某些实现中，阈值距离可以是与遍相对应的一组距离(例如，第一遍250米，第二遍150米，等等)。当平均地理位置和至少一个位置之间的距离超出该阈值距离时，系统可以从这一组位置中排除该至少一个位置。

系统可以重复处理304的阶段324、326和328，直到满足退出条件为止。系统可以确定(330)是否满足退出条件以便终止重复。在某些实现中，当重复次数达到某个阈值次数(例如，10次)时，退出条件被满足。该阈值次数以及用于排除位置的百分比可以是可配置的，以便精细调节在确定度(例如，较大的存在区域可以得到单元中的移动设备实际上位于该存在区域中的更大置信度)和精度(例如，较小的存在区域可以得到移动设备的更准确位置)之间的平衡。例如，当百分比被设置为95％并且遍数被设置为10时，最后一遍可以产生包含所有位置数据点的大约60％的圆。

在某些实现中，当存在区域或存在空间足够小时，阶段330的退出条件可被满足。在移动设备高度集中的单元中，存在区域可能足够小，以至于更多的遍将不一定会增加精度。当圆的半径达到低于阈值半径时，阶段324、326和328的重复可以终止。例如，阈值半径可以是8-10米。基于接收到的一组位置中的位置的分布模式(例如，接收到的位置数据点的数目、位置数据点的密度、以及单元中的集中区域)，阈值半径可以随着接入点的不同而不同。

系统可以将地理区域指定(332)为以平均地理位置为中心、其半径基于至少一个计算出的距离的圆。该地理区域可以与接入点(例如，接入点105)相关联。服务器可以将该地理区域(例如，中心和半径)提供给移动设备，以便计算该移动设备的当前位置。中心可以用纬度和经度表示。在某些在三维空间中计算距离的实现中，中心可以进一步用高度表示。

图3C是示出了实施管理位置数据库的技术的示例性系统的框图。该系统可以包括一个或多个处理器、一个或多个存储指令的存储器设备、和其它硬件或软件组件。该系统可以包括位置引擎350，其可被用于确定将与接入点(例如，接入点105)相关联的存在区域或存在空间。

位置引擎350可以包括数据收集模块352，其可以通过各个接入点从各个移动设备接收数据。该数据可以包括多个数据点，这些数据点可以指示一个或多个知道位置的移动设备(例如，移动设备108)的位置，以及表明移动设备108连接到哪个接入点的接入点标识符(例如，接入点105的MAC地址)。在某些实现中，数据点还可以包括关于移动设备108所在时区的信息。数据收集模块352可以包括数据接收模块354和数据索引模块356，数据接收模块354可以接收从移动设备108传输的数据。数据索引模块356可以对接收到的数据点执行各种处理。例如，数据索引模块356可以基于单元ID对纬度、经度和高度排序。数据索引模块356还可以基于时间段将数据分组。例如，可以为一个可配置的时间段(例如，6小时)创建新的一组接收位置。

各组接收到的移动设备108的位置可被存储在数据点数据库360中。数据点数据库360可以存储各个移动设备108的当前和历史位置。数据点数据库360可以包括ad-hoc数据库、关系数据库、面向对象数据库。数据点数据库360可相对于位置引擎350在本地或远程托管。

可以利用位置计算模块364计算数据点数据库中的各组数据点中的平均地理位置，计算平均地理位置和各个数据点的位置之间的距离，以及为进一步的计算从组中排除位置。位置计算模块364可以为特定组(例如，与一个单元ID相关联的一组数据点)执行计算，直到达到该特定组的退出条件为止。位置计算模块364可以为每个接入点(例如，接入点105)确定存在区域或存在空间。

在某些实现中，位置计算模块364可以使用有效性检查器366，基于各种准则和数据点中的各种数据，对存在区域或存在空间执行有效性检查。例如，从移动设备108接收的数据点可以包括移动国家代码(MCC)和时区信息。有效性检查器366可以将计算的存在区域或存在空间与对应于以MCC表示的国家的多边形和对应于时区的多边形进行比较。如果计算的存在区域或存在空间位于这些多边形之外，则有效性检查器366可以记录一个异常，并且去除该接入点。

位置过滤引擎368可以确定存在区域或存在空间是否可被用于估计当前位于接入点通信范围内的移动设备的位置。位置过滤引擎368可以将地理区域划分为地理网格100的单元102或三维网格120的三维单元122。位置过滤引擎368可以基于流行度、稳定性、寿命和新鲜度，给存在区域或存在空间评分。位置过滤引擎368可以将位于每个单元102或三维单元122中得分最高的存在区域或存在空间分配给单元102或三维单元。

存在区域或存在空间可以由具有一组位置的平均纬度、经度和高度坐标的中心来定义。存在区域或存在空间还可以由基于这一组位置中的位置到该中心的距离所确定的半径来定义。存在区域或存在空间的中心的纬度、经度和高度坐标以及存在区域或存在空间的半径可被存储在位置数据库372中。位置数据库372可以存储已分配和未分配的存在区域和存在空间。位置计算模块364可以在后续计算中分配未分配的存在区域或存在空间。位置数据库372可由位置计算模块364周期性地更新。

位置数据库372的数据可利用数据分发模块376被分发到移动设备。数据分发模块376可以根据请求、通过广播、或使用无需从移动设备接收请求的各种推送技术，将已分配的与接入点相关联的存在区域和存在空间的信息(例如，中心坐标和半径)发送给移动设备(例如，不能使用GPS的移动设备110)。

在某些实现中，数据分发模块376可以在一个传输会话中向移动设备发送多个存在区域和存在空间。为了减少可能消耗移动设备通信带宽的到移动设备的位置传输的数目，数据分发模块376可以使用邻居定位器378来定位移动设备110所处单元的邻居。邻近单元可以包括，例如，围绕移动设备110所处单元的若干单元，从而该单元和周围单元的总区域覆盖一定地理区域(例如，1或2平方公里)。向移动设备110发送关于与多个单元(例如，400个单元)相关联的存在区域和存在空间的信息可以减少当移动设备110跨单元移动时的传输数目。在某些实现中，当移动设备110移动到以前发送过的所有单元之外时，数据分发模块376仅需要向移动设备110发送更新。

利用无线接入点的位置确定移动设备的位置的示例性处理

图4A示出了用于利用无线接入点的位置确定移动设备的位置的技术。移动设备400可以是可以利用无线接入点的位置来确定其位置的示例性移动设备。示出了包括接入点404的通信网络的示例性部分。

移动设备400可以位于接入点404a的通信范围内。移动设备400可以从接入点404a接收包括关于邻近接入点的存在区域或存在空间(包括存在区域406)的信息的数据。移动设备400可以将接收到的数据存储在存储设备上。存储的数据可周期性地更新。

在示出的例子中，移动设备400位于接入点404a的通信范围内。此外，移动设备400在接入点404b、404c和404d的通信范围内。移动设备400可以在WLAN中使用的无线通信协议(例如，IEEE 802.11a)下识别接入点404a、404b、404c和404d。接入点404a、404b、404c和404d可以由接入点的MAC地址或其它标识符(例如，BluetoothTM标识符)来标识。

移动设备400可以识别分别与接入点404a-d相关联的存在区域406a、406b、406c和406d。识别存在区域406a-d可以包括从耦接到移动设备400的存储器设备中检索关于存在区域406a-d的信息。在某些实现中，移动设备400可以通过向服务器发送接入点404a-d的标识符，从服务器请求存在区域406a-d。

基于存在区域406a-d，移动设备400可以对存在区域406a-d执行迭代过程(例如，多遍分析)。该迭代过程可以产生地理区域402，其可以是对移动设备400的当前地理位置的估计。当使用三维位置信息时，地理区域402可以是地理空间。移动设备400可以在显示设备上(例如，在地图显示器上)显示估计的当前位置。

图4B是示出了使用位置数据库确定移动设备的位置的示例性处理410的流程图。为了方便，将借助于执行处理410的移动设备400来描述处理410。

移动设备400可以识别(412)移动设备400与之连接的当前接入点。移动设备400可以使用当前接入点来确定是否要请求位于移动设备400上的位置数据库的更新。位于移动设备400上的位置数据库可以包括以前下载到移动设备400的接入点的记录。位于移动设备400上的位置数据库中的记录可以包括接入点的标识符(例如，MAC地址)和相对应的位置(例如，纬度/经度坐标)。

在阶段412，移动设备400可以确定当前接入点是否被包括在位置数据库的记录中。移动设备可以使用移动设备400与之连接的当前接入点的标识符(例如，MAC地址)执行位置数据库查找。如果当前接入点被包括在位置数据库的记录中，则移动设备可以确定位置数据库是最新的。如果当前接入点未被包括在位置数据库的记录中，则移动设备400可以确定位置数据库需要更新。

移动设备400可以使用当前接入点的标识符从服务器请求(414)移动设备400的位置数据库的更新。位置数据库中的记录，包括接入点的标识符和位置，可利用新接入点的新标识符和位置被刷新。移动设备400可将当前接入点的标识符发送到服务器。服务器可以将某个单位识别为地理网格中的中心单元。中心单元可以是这样的单元，其包括与当前接入点的标识符相关联的位置，并且将该单元和邻近单元中的所有接入点位置发送给移动设备400。

移动设备400可以接收(416)与第二接入点相关联的一组第二位置。第二接入点可以分布在中心单元和在地理网格上与该中心单元邻近的单元中。与当前接入点相关联的位置(例如，圆区域的中心)可以位于中心单元中。邻近单元可以是在地理网格上位于中心单元旁边或与中心单元最近的单元。邻近单元的数目可以具有这样的值，即，使得中心单元和邻近单元可以覆盖预定的地理区域(例如，1.5平方公里)。当与接入点相关联的位置处于由中心单元和邻近单元覆盖的地理区域内时，这些接入点的标识符和与这些接入点相关联的位置可被包括在更新中。在当前接入点未被包括在位置数据库的记录中时更新移动设备400上的位置的一个示例性优点是，当移动设备400在单元之间移动时不需要更新，直到移动设备400移动到一个与单个接入点的覆盖区域相比的大区域之外为止。因此，可以避免频繁更新，为移动设备400和服务器两者节省了资源(例如，对移动设备而言，节省了带宽、CPU周期、电池电能；对服务器而言，当大量移动设备从一个街区移动到下一个街区时，服务器不需要向这些设备发送频繁的更新)。

移动设备400可以使用接收到的一组接入点位置和标识符来更新(418)位于移动设备400上的位置数据库。更新可以将移动设备400“定位”在由中心单元和邻近单元覆盖的地理区域的“中心”。移动设备400可以不需要请求另一个更新，直到移动设备400从该中心单元移动到未被邻近单元之一覆盖的单元。例如，如果每个单元大约为50米乘50米，并且该预定地理区域是1.5平方公里，则每次更新可以将大约600个单元注入移动设备400的位置数据库中。移动设备400不需要请求另一个更新，除非移动设备移动到该600个单元覆盖的区域之外。

移动设备400可以使用位于移动设备400上的位置数据库来计算(420)移动设备400的当前位置。可以使用由移动设备400执行的自适应多遍处理执行该计算。下面将参考图4C描述多遍处理的进一步细节。虽然其它因素(例如，来自各个接入点的信号强度)可以帮助对当前位置的计算，但是在该计算中不需要这些因素。

移动设备400可以可选地在移动设备400的地图显示设备上显示(422)移动设备400的当前位置。在下文会参考图5更详细地描述当前位置的示例性显示。

图4C是示出了确定移动设备的位置的示例性自适应多遍处理430的流程图。为了方便，将借助于执行处理430的移动设备400来描述处理430。

移动设备400可以接收(432)无线通信网络(例如，WLAN)的接入点(例如接入点404)的标识符。这些接入点可以位于移动设备400的通信范围内。所述标识符不必与移动设备400与之连接或可以连接的接入点相关联。例如，在特定位置，移动设备400可以处于3到20个接入点之间的通信范围内。移动设备400可能仅仅能够连接到两个接入点(由于例如接入点和移动设备400的安全设置)。移动设备400可能仅仅有效地连接到这两个接入点中的一个接入点。然而，在计算中可以使用移动设备400接收到的所有接入点标识符。

移动设备400可以从移动设备400的位置数据库中识别(433)与这些接入点相关联的一组位置。该组位置可以对应于与接入点相关联的存在区域406或存在空间。每个位置可以由地理坐标(例如，纬度、经度和高度)表示。每个位置可以与一个接入点404的标识符(例如，MAC地址)相关联。移动设备400可以使用数据库查找来识别这些位置。

移动设备400可以使用该组中的位置来计算(434)平均地理位置。计算平均地理位置可以包括计算该组中的位置的纬度、经度和高度的平均值，并且将位于计算出的平均纬度、经度和高度处的位置指定为平均地理位置。在某些实现中，计算平均地理位置可以包括将该组中的位置的中间纬度、中间经度和中间高度指定为平均地理位置。

移动设备400可以计算(436)该组中的位置与平均地理位置之间的距离。在某些实现中，系统可以在欧几里得空间中计算该组中的每个位置与平均地理位置之间的线性距离。在某些实现中，系统可以考虑地球的曲率，计算该组中的每个位置与平均地理位置之间的测地距离。

在阶段436中计算出的距离可被指定为与一个中心相关联的半径。该中心可以是在阶段434中计算出的平均地理位置，其可以是圆(例如，围绕地理区域402的圆)的中心。可以基于该组位置中的一个位置与平均地理位置之间的至少一个距离确定圆的半径。在某些实现中，该半径可以等于平均地理位置和该组中剩余的位置之间的最长距离。在某些实现中，该半径可以是这样的距离：当使用该半径并以该平均地理位置为中心画圆时，该圆可以包含该组中一定百分比(例如，80％)的剩余位置。该半径可以表示误差幅度，超出该误差幅度，对不能使用GPS的移动设备的位置估计不太可能在统计上有意义。

移动设备400可以基于平均地理位置和至少一个位置之间的距离从该组中排除(438)该至少一个位置。在某些实现中，系统可以排除到平均地理位置的距离超过某个阈值距离的位置。在多遍分析的每一遍中，通过排除表现为远离位置集群(例如，一群聚集的位置)的位置，系统可以增加所估计的平均地理位置的精度。远离一群聚集位置的位置在估计移动设备400的当前位置时不太有用，并且可被排除。在各种实现中，阈值距离可以从一遍到下一遍改变。例如，阈值距离可以是与遍相对应的一组距离(例如，第一遍50米，第二遍30米，等等)。当平均地理位置和至少一个位置之间的距离超过该阈值距离时，系统可以从这一组位置中排除该至少一个位置。

在某些实现中，移动设备400可以确定将被排除的位置的阈值百分比。该阈值百分比可以具有预先指定的值(例如，5％)。在每一遍中，移动设备400可以排除阈值百分比的与平均地理位置相距最远的位置。

移动设备400可以重复处理430的阶段434、436和438，直到满足退出条件为止。系统可以确定(440)是否满足退出条件以便终止重复。在某些实现中，当重复次数达到某个阈值次数(例如5次)时，退出条件被满足。该阈值次数可以与原始接收的组中的位置数目有关。该阈值数目以及排除位置的百分比可以是可配置的，以便精细调节在确定度(例如，较大的存在区域可以得到单元中的移动设备实际上位于该存在区域中的更大置信度)和精度(例如，较小的存在区域可以得到移动设备的更准确位置)之间的平衡。例如，当百分比被设置为95％并且遍数被设置为10时，最后一遍可以产生包含所有位置数据点的大约60％的圆。

在某些实现中，当存在区域或存在空间足够小时，阶段330的退出条件可被满足。在接入点404高度集中的区域中，估计的当前位置可能包括足够小的区域，以至于更多的遍将不一定会增加精度。当圆的半径达到低于阈值半径时，阶段434、436和438的重复可以终止。例如，阈值半径可以是8-10米。该阈值半径可以基于存在区域406的半径。在某些实现中，如果某些存在区域406的半径足够小，则阈值半径可以很小，以便反映估计的置信度。

移动设备400可以利用以平均地理位置为中心、其半径基于至少一个计算出的距离的圆，来指定(442)移动设备400的当前位置。该中心可以用纬度和经度表示。在某些在三维空间中计算距离的实现中，中心可以进一步用高度表示。在某些实现中，移动设备还可以在显示设备上在地图用户界面上显示当前位置。下面将参考图5描述示例性的地图用户界面。

用于确定移动设备的位置的示例性用户界面

图5示出了用于利用无线接入点的位置确定移动设备的位置的示例性用户界面。在图5中，在移动设备500上显示地理区域的示例地图502。在某些实现中，移动设备500可以在移动设备500的触敏显示器530上显示地图502。当用户选择地图对象以便观看基于地图和位置的服务时，可以显示地图502。在某些实现中，可以通过语音激活来选择诸如地图对象之类的对象。可以在地图502的顶部显示搜索栏504和书签列表对象506。可以在地图底部下面显示一个或多个显示对象，例如，搜索对象508、路线对象510、地图观看对象512和当前位置对象514。

搜索栏504可用于在地图上寻找地址或其它位置。例如，用户可以在搜索栏504中输入其家庭地址，从而包含该地址的区域将显示在地图502上。书签列表对象506可以例如给出包含频繁访问的地址(诸如，用户的家庭地址)的书签列表。书签列表还可以例如包含特别的书签，诸如当前位置(例如，移动设备500的当前位置)。

搜索对象508可用于显示搜索栏504和其它与地图有关的搜索菜单。路线对象510可以例如给出允许用户输入开始和结束位置的菜单界面。然后该界面可以显示信息(例如，从开始位置到结束位置的路线的方向和行进时间)。地图观看对象512可以给出允许用户选择地图502的显示选项的菜单。例如，可以将地图502从黑白变成彩色，可以改变地图的背景，或用户可以改变地图的亮度。

当前位置对象514可以允许用户在地图502上观看表明设备500当前处于何处的地理区域516。地理区域516可以对应于估计的地理区域(例如，地理区域402)，该估计的地理区域的中心是与处于移动设备500通信范围内的接入点相关联的数据点的平均地理位置。可以基于该平均地理位置和与这些接入点相关联的一个或多个位置之间的距离确定地理区域516的半径。当选择当前位置对象514时，特别的当前位置书签可被置于书签列表中。如果该特别的当前位置书签以前已被设置在书签列表中，则该旧的书签信息可以例如被新的当前位置信息所取代。在某些实现中，该特别的当前位置书签被绑定到地理区域516的形心。即，该特别的当前位置书签可以包括地理区域516的形心的坐标。地理区域516可以基于利用存储在移动设备500的存储器设备中的位置指令而确定或估计的位置数据。地理区域516可以例如由具有十字准线的圆、矩形、正方形、六边形或其它封闭区域，或者由某些其它区别元素来示出，以便区分地理区域516和地图502。

在某些实现中，地理区域516可以指示移动设备500被确定或被估计位于其中的区域，并且该地理区域可以不一定以移动设备500的实际当前位置为中心。在这个例子中，移动设备500可以处于该地理区域内偏离中心的位置。在另一个例子中，地理区域516可以以移动设备500的估计的当前位置为中心。

当轻击或选择当前位置对象514时，移动设备500可以使地图视图以地理区域516为中心。在某些实现中，可以基于位置数据或提供位置数据的技术、系统或服务的准确度或精度，调整地图的缩放级别。例如，当移动设备500不能接收GPS信号时，可以由于较低的准确度而缩小地图，并且使用接入点数据确定其位置。如果移动设备500能够使用GPS位置数据确定其当前位置，则可以由于较高的准确度而放大地图。在某些实现中，缩放级别可以基于移动设备500的速度(例如，可以在较高速度时缩小地图，在移动设备500不移动时放大地图)。还可以使用准确度或精度与速度的组合。

如果用于检索基于位置的数据的所有方法都失败了(例如，当移动设备500不在任何接入点的通信范围内时，或者当有效性检查器366确定没有存在区域能够与移动设备500可连接的任何接入点相关联时)，并且没有其它系统或服务可用于确定或估计移动设备500的当前位置，则可以向用户显示一个错误，并且不在地图502上显示地理区域。该错误可以例如包含将失败和可能的一个或多个失败原因通知给用户的消息。

可以选择当前位置对象514以便例如激活地图502上的地理区域516的估计和显示，从而获得去往或始于估计的当前位置(即，地理区域516的形心)的路线，将移动设备500的估计的当前位置发送给朋友(例如，使得该朋友可以到该相同位置)，或者为估计的当前位置创建书签。

示例性系统体系结构

图6是用于实现参考图1-5所描述的特征和操作的示例性系统体系结构600的框图。其它体系结构也是可能的，包括具有更多或更少组件的体系结构。在某些实现中，体系结构600包括一个或多个处理器602(例如，双核心

处理器)、一个或多个输出设备604(例如，LCD)、一个或多个网络接口606、一个或多个输入设备608(例如，鼠标、键盘、触敏显示器)、和一个或多个计算机可读介质612(例如，RAM、ROM、SDRAM、硬盘、光盘、闪存等)。这些组件可以通过一个或多个通信通道610(例如，总线)交换通信和数据，通信通道610可以使用各种硬件和软件，以帮助实现组件之间的数据和控制信号的传输。

术语“计算机可读介质”指参与向处理器602提供用于执行的指令的任何介质，包括但不限于，非易失介质(例如，光盘或磁盘)、易失介质(例如，存储器)和传输介质。传输介质包括但不限于同轴电缆、铜线和光纤。

如参考图1-5所述，计算机可读介质612还可以包括操作系统614(例如，Mac

server，

NT server)、网络通信模块616、数据库接口620、数据收集模块630、数据分发模块640和位置计算模块650。操作系统614可以是多用户的、多处理的、多任务的、多线程的、实时的，等等。操作系统614执行基本任务，包括但不限于：识别来自设备606、608的输入以及向设备606、608提供输出；在计算机可读介质612(例如，存储器或存储设备)上记录和管理文件和目录；控制外围设备；以及管理一个或多个通信通道610上的业务。网络通信模块616包括用于建立和保持网络连接的各种组件(例如，用于实现诸如TCP/IP、HTTP等通信协议的软件)。数据库接口620可以包括到文件系统上的一个或多个数据库(例如，数据点数据库360和位置数据库372)的接口。可以按照分层文件夹结构来组织数据库，所述文件夹映射到文件系统中的目录。数据收集模块630可以包括用于从通过接入点或通过其它通信通道(例如，蜂窝网络)无线连接到系统600的多个移动设备收集数据的组件。数据分发模块640可以执行用于向计算设备传输与无线通信网络的接入点相关联的位置数据的各种功能，所述计算设备包括移动设备108和110。位置计算模块650可以包括用于对从移动设备108接收的位置执行多遍分析的一个或多个组件。

体系结构600可被包括在能够持有(host)数据库应用程序的任何设备中。可以以并行处理或对等基础结构或者在具有一个或多个处理器的单个设备上实现体系结构600。软件可以包括多个软件组件，或者可以是单段代码。

描述的特征可被有利地以可在可编程系统上执行的一个或多个计算机程序实现，所述可编程系统包括至少一个可编程处理器、至少一个输入设备和至少一个输出设备，所述可编程处理器被耦接为从数据存储系统接收数据和指令，并且向数据存储系统传输数据和指令。计算机程序是可以在计算机中直接或间接使用以便执行某个活动或带来某个结果的指令集。计算机程序可被以任何形式的编程语言编写(例如，Objective-C、Java)，包括编译或解释语言，并且可被以任何形式部署，包括作为独立程序或作为模块、组件、子例程、基于浏览器的网络应用、或适合于在计算环境中使用的其它单元。

举例而言，用于执行指令程序的适当处理器包括通用和专用微处理器两者，以及任何类型计算机的单个处理器或者多个处理器或核之一。一般地，处理器将从只读存储器或随机访问存储器或这两者接收指令和数据。计算机的基本元件是用于执行指令的处理器和用于存储指令和数据的一个或多个存储器。一般地，计算机还将包括用于存储数据文件的一个或多个大容量存储设备，或计算机可操作地被耦接以与其通信；这些设备包括磁盘，诸如内部硬盘和可移动盘；磁光盘；和光盘。适用于有形地包含计算机程序指令和数据的存储设备包括所有形式的非易失存储器，作为例子，包括半导体存储器设备，诸如EPROM、EEPROM和闪存设备；磁盘，诸如内部硬盘和可移动盘；磁光盘；以及CD-ROM和DVD-ROM盘。处理器和存储器可被辅以ASIC(专用集成电路)或被结合在ASIC中。

为了提供与用户的交互，这些特征可被实现在具有用于向用户显示信息的显示设备(诸如，CRT(阴极射线管)或LCD(液晶显示器)监视器)和用户可以借以向计算机提供输入的键盘和指点设备(诸如，鼠标或轨迹球)的计算机上。

这些特征可被实现在包括后端组件(诸如数据服务器)，或包括中间件组件(诸如应用服务器或Internet服务器)，或包括前端组件(诸如具有图形用户界面或Internet浏览器的客户计算机)，或它们的任何组合的计算机系统中。系统的组件可以由数字数据通信的任何形式或介质(诸如，通信网络)来连接。通信网络的例子包括，例如，LAN、WAN、和形成Internet的计算机和网络。

该计算机系统可以包括客户端和服务器。客户端和服务器一般彼此远离，并且通常通过网络交互。通过在各自计算机上运行并且彼此具有客户端-服务器关系的计算机程序，产生了客户端和服务器的关系。

示例性移动设备体系结构

图7是移动设备的示例性体系结构700的框图。移动设备可以例如是手持计算机、个人数字助理、蜂窝电话、电子输入板、网络设备、照相机、智能电话、增强式通用分组无线业务(EGPRS)移动电话、网络基站、媒体播放器、导航设备、电子邮件设备、游戏控制台、或这些数据处理设备或其它数据处理设备中的任意两个或更多个的组合。

移动设备可以包括存储器接口702、一个或多个数据处理器、图像处理器和/或中央处理单元704、以及外围设备接口706。存储器接口702、一个或多个处理器704和/或外围设备接口706可以是分离的组件，或可被集成在一个或多个集成电路中。移动设备100中的各种组件可由一个或多个通信总线或信号线耦接。

传感器、设备和子系统可被耦接到外围设备接口706，以帮助实现多个功能。例如，运动传感器710、光传感器712和接近(proximity)传感器714可耦接到外围设备接口706，以帮助实现移动设备的定向、光照和接近功能。位置处理器715(例如，GPS接收器)可连接到外围设备接口706，以便提供地理定位。电子磁力计716(例如，一个集成电路芯片)也可连接到外围设备接口706，以便提供可用于确定磁北极方向的数据。

照相机子系统720和光学传感器722，例如，电荷耦合器件(CCD)或互补金属氧化物半导体(CMOS)光学传感器，可用于帮助实现照相机功能，诸如，记录照片和视频剪辑。

可以通过一个或多个无线通信子系统724来帮助实现通信功能，无线通信子系统724可以包括射频接收器和发射器和/或光学(例如，红外线)接收器和发射器。通信子系统724的具体设计和实现可取决于移动设备要在其上操作的一个或多个通信网络。例如，移动设备可以包括被设计为在GSM网络、GPRS网络、EDGE网络、Wi-Fi或WiMax网络、和Bluetooth网络上操作的通信子系统724。特别地，无线通信子系统724可以包括托管协议(hosting protocol)，从而设备可被配置作为其它无线设备的基站。

音频子系统726可耦接到扬声器728和麦克风730，以帮助实现能够使用语音的功能，诸如语音识别、语音复制、数字记录、以及电话功能。

I/O子系统740可以包括触摸屏控制器742和/或其它输入控制器(一个或多个)744。触摸屏控制器742可耦接到触摸屏746或触摸板。触摸屏746和触摸屏控制器742可以例如使用多种触敏技术中的任何一种来检测接触和移动或其中断，所述触敏技术包括但不限于电容、电阻、红外线和表面声波技术，以及用于确定与触摸屏746的一个或多个接触点的其它接近传感器阵列或其它元件。

其它输入控制器(一个或多个)744可耦接到其它输入/控制设备748，诸如一个或多个按钮、拨动开关、拇指轮、红外线端口、USB端口、和/或诸如触笔之类的指针设备。一个或多个按钮(未示出)可以包括用于扬声器728和/或麦克风730的音量控制的上/下按钮。

在一种实现中，将按钮按压第一持续时间可以解除触摸屏746的锁定；将按钮按压比第一持续时间长的第二持续时间可以接通或关闭移动设备的电源。用户可以定制一个或多个按钮的功能。触摸屏746还可以例如用于实现虚拟或软按钮和/或键盘。

在某些实现中，移动设备可以呈现记录的音频和/或视频文件，诸如，MP3、AAC和MPEG文件。在某些实现中，移动设备可以包括MP3播放器(诸如iPod^TM)的功能。因此移动设备可以包括与iPod兼容的针连接器。还可以使用其它输入/输出和控制设备。

存储器接口702可耦接到存储器750。存储器750可以包括高速随机访问存储器和/或非易失存储器，诸如一个或多个磁盘存储设备、一个或多个光学存储设备、和/或闪存(例如，NAND、NOR)。存储器750可以存储操作系统752，诸如，Darwin、RTXC、LINUX、UNIX、OS X、WINDOWS或嵌入式操作系统，诸如VxWorks。操作系统752可以包括用于处理基本系统服务和用于执行硬件相关任务的指令。在某些实现中，操作系统752可以包括内核(例如，UNIX内核)。

存储器750还可以存储通信指令754，以帮助实现与一个或多个附加设备、一个或多个计算机和/或一个或多个服务器的通信。存储器750可以包括：图形用户界面指令756，以帮助实现图形用户界面处理；传感器处理指令758，以帮助实现与传感器有关的处理和功能；电话指令760，以帮助实现与电话有关的处理和功能；电子消息收发指令762，以帮助实现与电子消息收发有关的处理和功能；网络浏览指令764，以帮助实现与网络浏览有关的处理和功能；媒体处理指令766，以帮助实现与媒体处理有关的处理和功能；GPS/导航指令768，以帮助实现与GPS和导航有关的处理和功能；照相机指令770，以帮助实现与照相机有关的处理和功能；磁力计数据772和校准指令774，以帮助实现磁力计校准。存储器750可以包括位置指令776，其可用于向接入点传输当前位置，以及基于与移动设备处于其通信范围内的接入点相关联的位置数据，确定估计的当前位置。存储器750还可以存储其它软件指令(未示出)，诸如，安全指令；网络视频指令，以帮助实现与网络视频有关的处理和功能；和/或网络购物指令，以帮助实现与网络购物有关的处理和功能。在某些实现中，媒体处理指令766被划分为音频处理指令和视频处理指令，以分别帮助实现与音频处理有关的处理和功能和与视频处理有关的处理和功能。激活记录和国际移动设备标识(IMEI)或类似的硬件标识符也可被存储在存储器750中。

上面列出的指令和应用中的每一个可以对应于用于执行上述一个或多个功能的一个指令集。这些指令不一定被实现为单独的软件程序、过程或模块。存储器750可以包括附加的指令或更少的指令。另外，移动设备的各种功能可以硬件和/或软件实现，包括以一个或多个信号处理和/或专用集成电路来实现。

已经描述了本发明的若干实现。然而，应当理解，可以做出各种修改，而不脱离本发明的精神和范围。例如，知道位置的设备被称为能够使用GPS。知道位置的移动设备也可以基于三角测量或其它技术。单元被在图中表示为大体是矩形形状。单元的实际形状可以改变。位置被描述为“圆”。本说明书中使用的术语“圆”可以包括不一定是完美的圆、但是是闭合的或具有封闭外观的任何几何形状(例如，椭圆、正方形、凸或凹多边形、或自由形状)。不是完美圆形的几何形状的半径可以包括在该几何形状边界上的各个点与几何形状中心之间的平均距离。使用WiFi和WiMax网络作为例子。也可以使用其它无线技术(例如，蜂窝网络)。因此，其它实现处于所附权利要求的范围中。

Claims (18)

1.一种由计算机实现的方法，包括：

从均位于无线通信网络的一接入点的通信范围内的多个第一移动设备接收多组位置，每组位置对应于一个不同的接入点；

基于接收到的对应于每个接入点的一组位置的平均值，确定与该接入点相关联的地理位置；

将与每个接入点相关联的地理位置分配给地理网格上的单元；

对于所述地理网格上的每个单元，基于接收到的对应接入点的一组位置中的位置的数目，对分配给该单元的各地理位置进行评分，其中，与数目较多的一组位置相关联的接入点所对应的地理位置得到较高的评分；

过滤分配给每个单元的各地理位置，包括保留该单元的具有最高评分的地理位置；和

将与所述接入点相关联的地理位置和分配给在所述地理网格上与所述单元邻近的单元的接入点的地理位置提供给连接到所述接入点的第二移动设备。

2.如权利要求1所述的方法，其中所述接入点由所述接入点的媒体访问控制(MAC)地址来标识，所述MAC地址与所述一组位置相关联。

3.如权利要求1所述的方法，其中所述无线通信网络是使用基于电气和电子工程师协会(IEEE)802.11的协议的无线局域网(WLAN)。

4.如权利要求1所述的方法，其中确定与所述接入点相关联的地理位置包括：

对接收到的所述一组位置应用多遍分析，其中包括在每遍分析中从所述一组位置中排除至少一个位置。

5.如权利要求1所述的方法，其中，对分配给每个单元的各地理位置进行评分进一步基于与每个地理位置相对应的每个接入点所关联的一组位置中的位置的稳定性、寿命或新鲜度中的至少一个。

6.如权利要求5所述的方法，其中接入点的稳定性对应于在不同时间确定的与该接入点相关联的地理位置的稳定性，接入点的寿命对应于该接入点已经存在的时间长度，并且接入点的新鲜度对应于从位于该接入点的通信范围内的第一设备接收到的最新位置。

7.如权利要求1所述的方法，其中第二移动设备具有包括下载到第二移动设备的接入点的记录的位置数据库，其中，响应于第二移动设备与之连接的当前接入点未被包括在位置数据库的记录中，当所述第二移动设备移动到一预定地理区域之外时，使用由所述提供步骤所提供的接入点的地理位置来更新所述位置数据库。

8.如权利要求1所述的方法，其中所述地理网格上的所述单元包括大体上为矩形的地理区域，所述地理区域在所述地理网格上能够用所述地理区域的标识点的纬度和经度来标识。

9.如权利要求1所述的方法，其中所述地理网格限定三维空间，并且所述单元包括三维封闭空间，所述三维封闭空间在所述地理网格中能够用所述封闭空间内的标识点的纬度、经度和高度来标识。

10.一种由计算机实现的系统，包括：

用于从均位于无线通信网络的一接入点的通信范围内的多个第一移动设备接收多组位置的装置，每组位置对应于一个不同的接入点；

用于基于接收到的对应于每个接入点的一组位置的平均值，确定与该接入点相关联的地理位置的装置；

用于将与每个接入点相关联的地理位置分配给地理网格上的单元的装置；

用于对于所述地理网格上的每个单元，基于接收到的对应接入点的一组位置中的位置的数目，对分配给该单元的各地理位置进行评分的装置，其中，与数目较多的一组位置相关联的接入点所对应的地理位置得到较高的评分；

用于过滤分配给每个单元的各地理位置的装置，所述过滤包括保留该单元的具有最高评分的地理位置；和

用于将与所述接入点相关联的地理位置和分配给在所述地理网格上与所述单元邻近的单元的接入点的地理位置提供给连接到所述接入点的第二移动设备的装置。

11.如权利要求10所述的系统，其中所述接入点由所述接入点的媒体访问控制地址(MAC)来标识，所述MAC地址与所述一组位置相关联。

12.如权利要求10所述的系统，其中所述无线通信网络是使用基于电气和电子工程师协会(IEEE)802.11的协议的无线局域网(WLAN)。

13.如权利要求10所述的系统，其中用于确定与所述接入点相关联的地理位置的装置包括：

用于对接收到的所述一组位置应用多遍分析的装置，其中包括用于在每遍分析中从所述一组位置中排除至少一个位置的装置。

14.如权利要求10所述的系统，其中，对分配给每个单元的各地理位置进行评分进一步基于与每个地理位置相对应的每个接入点所关联的一组位置中的位置的稳定性、寿命或新鲜度中的至少一个。

15.如权利要求14所述的系统，其中接入点的稳定性对应于在不同时间确定的与该接入点相关联的地理位置的稳定性，接入点的寿命对应于该接入点已经存在的时间长度，并且接入点的新鲜度对应于从位于该接入点的通信范围内的第一设备接收到的最新位置。

16.如权利要求10所述的系统，其中第二移动设备具有包括下载到第二移动设备的接入点的记录的位置数据库，其中，响应于第二移动设备与之连接的当前接入点未被包括在位置数据库的记录中，当所述第二移动设备移动到一预定地理区域之外时，使用由所述提供步骤所提供的接入点的地理位置来更新所述位置数据库。

17.如权利要求10所述的系统，其中所述地理网格上的所述单元包括大体上为矩形的地理区域，所述地理区域在所述地理网格上能够用所述地理区域的标识点的纬度和经度来标识。

18.如权利要求10所述的系统，其中所述地理网格限定三维空间，并且所述单元包括三维封闭空间，所述三维封闭空间在所述地理网格中能够用所述封闭空间内的标识点的纬度、经度和高度来标识。

Images