相关申请案交叉申请
本申请要求2018年5月23日递交的第15/987,319号美国专利申请案的在先申请优先权，该在先申请的主题以引入的方式并入本文。
技术领域
本发明通常涉及基于位置的服务，尤其涉及地理防护。
背景技术
众多应用可以使用来自移动设备或电话等计算设备的位置信息。诸多应用使用位置数据定位朋友、玩游戏及帮助用户确认方向。当用户在如企业、机构、地标、公园或用户感兴趣的其它位置等兴趣点附近时，还可以使用所述位置信息向用户的移动设备发出提示。例如，用户可以选择每次在特定商店或餐馆附近时收到提醒。
基于位置的服务属于移动应用领域，这些移动应用利用许多移动设备的能力确定其当前位置并基于该位置执行操作。在一些实例中，基于位置的服务使用地理围栏。地理围栏是可围绕现实地理面积创建的虚拟周界。根据特定的应用，进入或穿过地理围栏可以引起服务提供、导致服务暂停或触发某些其它类型的操作。但是，当前在许多移动设备上实现地理围栏存在缺陷。其中一种缺陷会限制移动设备可监控的地理围栏的形状和/或大小。
发明内容
根据本发明一方面，提供一种计算机实现的地理防护方法，包括：计算设备生成多个圆形地理围栏，以覆盖多边形地理围栏定义的地理区域；所述计算设备对所述多个圆形地理围栏进行监控，以检测进入任一所述圆形地理围栏的边界的用户设备的当前位置；所述计算设备基于所述检测，确定所述用户设备的当前位置在所述多边形地理围栏中；通知基于位置的服务所述用户设备已经进入所述多边形地理围栏。
可选地，在上述任一方面中，所述方法还包括：所述计算设备将所述多边形地理围栏分割为一个或多个子区域，其中，每个所述子区域由所述多个圆形地理围栏中的一个对应圆形地理围栏覆盖。
可选地，在上述任一方面中，所述生成多个圆形地理围栏还包括：所述计算设备通过计算所述多边形地理围栏覆盖的地理区域的面积与所述多个圆形地理围栏覆盖的地理区域的面积的差值，测量所述多个圆形地理围栏的质量阈值。
可选地，在上述任一方面中，所述方法还包括：所述计算设备定义基线阈值；所述计算设备生成内插点，其中，每个内插点位于所述多边形地理围栏内部；所述计算设备计算所述多个圆形地理围栏的最小数量，以基于生成的内插点生成所述多个圆形地理围栏；所述计算设备对所计算出的所述多个圆形地理围栏的最小数量进行求值，以确定是否满足所述基线阈值；如果所述质量阈值大于所述基线阈值，所述计算设备调整所述最小数量并基于调整后的最小数量生成所述多个圆形地理围栏；如果所述质量阈值小于或等于所述基线阈值，所述计算设备生成所述最小数量的多个圆形地理围栏，以覆盖所述多边形地理围栏。
可选地，在上述任一方面中，生成所述内插点包括：所述计算设备在所述地理区域中填充独立点；所述计算设备将所述独立点内插于定义所述地理区域的所述多边形地理围栏之中。
可选地，在上述任一方面中，所述方法还包括：所述计算设备将所述内插的独立点分割为子区域，其中，每个子区域由所述多个圆形地理围栏中的一个所覆盖。
可选地，在上述任一方面中，所述计算所述多个圆形地理围栏的最小数量包括：所述计算设备计算所述多个圆形地理围栏的初始中心点，作为将所述多边形地理围栏在一个方向上划分为所述最小数量的等分的点；所述计算设备将所述内插点分割为最小数量的集群，并围绕每个所述集群中的点创建单个圆形地理围栏；由于所述多个圆形地理围栏中不只一个位于所述多边形地理围栏内部，所述计算设备对所述多个圆形地理围栏进行合并，以减少所述多个圆形地理围栏的总数。
可选地，在上述任一方面中，所述确定所述用户设备的当前位置在所述多边形地理围栏中还包括：所述计算设备检索方位及准确度信息，所述方位及准确度信息定义围绕所述用户设备的位置的圆形区域；所述计算设备计算所述位置与所述多边形地理围栏的每个边之间的距离；根据所述距离大于还是等于所述准确度，所述计算设备确定所述方位是在所述多边形地理围栏的内部还是外部；如果所述距离中的至少一个距离小于所述准确度，所述计算设备确定所述圆形区域与所述多边形地理围栏之间存在重叠。
可选地，在上述任一方面中，如果所述距离小于所述准确度：所述计算设备生成内插于所述圆形区域的M个点；所述计算设备确认位于所述圆形区域及所述多边形地理围栏内部的N个点；所述计算设备计算出所述用户设备位于所述多边形地理围栏内部的概率为N/M，其中，N近似于所述圆形区域与所述多边形地理围栏之间的重叠面积大小，M近似于所述圆形区域的面积大小。
可选地，在上述任一方面中，所述基于位置的服务是基于所述用户设备的当前位置提供信息的应用、导航系统或系统。
根据本发明的另一方面，提供一种设备，包括：包含指令的非瞬时性存储器；与所述存储器通信的一个或多个处理器，其中，所述一个或多个处理器执行所述指令以：生成多个圆形地理围栏，以覆盖多边形地理围栏定义的地理区域；对所述多个圆形地理围栏进行监控，以检测进入任一所述圆形地理围栏的边界的用户设备的当前位置；基于所述检测，确定所述用户设备的当前位置在所述多边形地理围栏中；通知基于位置的服务所述用户设备已经进入所述多边形地理围栏。
根据本发明的又一方面，提供一种非瞬时性计算机可读介质，存储用于地理防护的计算机指令，当所述计算机指令被一个或多个处理器执行时，使得所述一个或多个处理器执行以下操作：计算设备生成多个圆形地理围栏，以覆盖多边形地理围栏定义的地理区域；所述计算设备对所述多个圆形地理围栏进行监控，以检测进入任一所述圆形地理围栏的边界的用户设备的当前位置；所述计算设备基于所述检测，确定所述用户设备的当前位置在所述多边形地理围栏中；通知基于位置的服务所述用户设备已经进入所述多边形地理围栏。
发明内容简单介绍了一些概念，在具体实施方式中会进一步描述这些概念。发明内容不旨在提供专利申请所要求保护的主题的关键特征或基本特征，也不旨在确定专利申请所要求保护的主题范围。专利申请所要求保护的主题不限于解决背景技术中提到的任何或所有问题的实现方式。
附图说明
通过示例对本发明各方面进行描述，附图不对本发明的各方面造成限制。在附图中，相同的编号指示元件。
图1示出了一种用于生成地理围栏的示例性系统；
图2示出了一种可用于图1的系统中的示例性计算设备；
图3示出了一种用于对计算设备的位置进行求值的示例性流程；
图4A与图4B示出了一种将圆形地理围栏应用于多边形地理围栏的示例性流程；
图4C示出了一种围绕多边形地理围栏的圆形地理围栏的示例；
图5A至图5E示出了一种用于确定计算设备与地理围栏的相对位置的示例性流程；
图6示出了图4A中的流程的执行示例；
图7A与图7B示出了使用不同基线阈值生成圆形地理围栏时的性能数据；
图8示出了一种可用于实施各种实施例的网络系统的方框图。
具体实施方式
下文结合附图对本发明进行描述，附图通常涉及基于位置的服务及地理防护。
地理防护是一种用于监控手机等计算设备在地理区域中的移动，并在所述设备进入或离开所述地理区域时通知或提醒所述设备的用户的技术。地理围栏定义了所述地理区域的边界，这样就可以将手机的位置数据与地理围栏边界或周界的坐标(如维度和经度)进行比较。本发明解决手机进入或离开地理围栏时的准确度问题，更具体地，提供一种机制，用于确定手机何时进入或离开多边形地理围栏。在一实施例中，本文中公开的技术使用多个圆形地理围栏近似得到多边形地理围栏。通过这种方式近似得到多边形地理围栏可以减少处理并降低功耗。
可以理解的是，本发明实施例可以通过众多不同形式实现，并且所要求保护的范围不应理解为限于本文所描述的实施例。准确地说，提供这些实施例是为了使本发明更详尽更完整，并向本领域技术人员充分传达本发明实施例构思。事实上，本发明旨在覆盖包括在由所附权利要求书限定的本发明公开的精神和范围内的这些实施例的替代物、修改和等同物。此外，在本发明实施例的以下具体描述中，提供了众多具体细节以供全面了解。但是本领域的普通技术人员清楚了解，可以在没有这些具体细节的情况下实践本发明实施例
图1示出了一种用于生成地理围栏的示例性系统。所述系统包括计算设备102(例如用户设备或移动设备)以及远程服务器114。所述计算设备102与所述远程服务器114通过网络110(例如互联网)，进行通信。
本文中的术语“计算设备”指的是包括存储器、可编程处理器及全球定位系统(Global Positioning System，GPS)接收器或用于确定当前位置的其它构件的蜂窝电话、智能手机、个人或移动多媒体播放器、个人数字助理(personal data assistant,PDA)、笔记本电脑、平板电脑、智能本、车辆计算系统、陆海空导航系统、超级本、掌上电脑、无线电子邮件接收器、多媒体互联网蜂窝电话、无线游戏控制器及类似的个人电子计算设备中的任一种或全部。术语“计算设备”还包括具有处理器及用于确定当前位置的构件的嵌入式计算设备，所述嵌入式计算设备包含在更大的计算设备或车辆中，如集成在自行车、汽车、摩托车、飞机、舟船等中的计算系统和/或导航系统。
在公开的非限制性实施例中，所述移动设备102包括位置检测引擎102A、地理防护引擎102B及通知引擎102C。在一实施例中，所述移动设备102可以使用所述位置检测引擎102A检测其位置。所述位置检测引擎102A可以使用Wi-Fi热点、蜂窝塔信号和/或GPS信号等检测所述移动设备的当前位置。所述位置检测引擎102A还可以访问远程服务器114(其可位于“云”中)请求位置信息。例如，所述远程服务器114可以从所述移动设备接收Wi-Fi热点列表并且可以基于所述列表提供位置，或所述远程服务器114可以从蜂窝服务请求位置。
在一实施例中，所述移动设备102(或所述设备的用户)可以使用防护技术生成地理边界或周界，以使用所述地理防护引擎102B生成地理围栏118A(如图解118所示)。在另一实施例中，所述移动设备102可以从所述远程服务器114等服务器接收地理围栏118A。如下文详述，在一实施例中，所述地理围栏118A围成包括一位置的区域，所述位置可以是位于或靠近所述区域的中心。在其它实施例中，所述地理围栏118A围成包括一位置的圆形或椭圆形区域。还可以理解的是，所述移动设备102(或所述设备的用户)可以选择所述移动设备102或位置数据库112等数据库中存储的预定义地理围栏。
如上所述，所述地理围栏118A的边界及服务可以由远程服务器，如所述远程服务器114，提供。在本实施例中，所述移动设备102中的任意开启地理围栏的应用(如图2中的应用240)从所述远程服务器114接收附近的地理围栏的地理位置。当在计算设备(如所述移动设备102)中执行时，所述开启地理围栏的应用，例如通过所述计算设备的GPS接收器和/或通过Wi-Fi(如预先映射的Wi-Fi接入点位置)和/或蜂窝连接(如预先映射的蜂窝塔位置)，持续确定其位置并将其位置与已知地理围栏的位置相比较，以确定是否满足阈值或条件(例如，进入地理围栏、离开地理围栏、穿过地理围栏边界或周界等)。当所述开启地理围栏的应用确定满足地理围栏阈值或条件时，所述应用可以发起与存储地理围栏信息的服务器的通信，将该地理围栏事件通知所述服务器。或者，所述应用可以在本地使用该地理围栏。
在另一实施例中，所述移动设备102可以存储与地理围栏118A相关联的Wi-Fi标识(或其它已知网络)。所述移动设备102向Wi-Fi检测器116发送请求。所述请求可包括应围绕其生成地理围栏118A的位置等，还可以包括所述地理围栏118A的中心延伸的距离。例如，在图示中的多边形地理围栏118A中，可以从所述地理围栏118A的中心向定义所述地理围栏118A的每个边界(或周界)延伸多个半径或距离。所述位置本身可以由所述位置检测引擎102A创建或从位置数据库112接收。相应地，所述Wi-Fi检测器116可以提供定义所述地理围栏118A的半径内的Wi-Fi标识，或可以回复所述Wi-Fi标识的经纬度坐标。该回复可以存储在所述移动设备102中并与所述地理围栏118A相关联。
所述地理围栏引擎102A可以检测所述移动设备102是位于所述多边形地理围栏118A等生成的地理围栏内部还是外部。在一实施例中，所述地理围栏118A的内部定义为包括所述地理围栏的边，如边界或周界。在另一实施例中，所述地理围栏引擎102B还可以检测所述移动设备102进入或离开所述地理围栏118A的时间。可以在所述移动设备102正在主动穿过所述地理围栏118A的边界或周界时或所述移动设备102已经穿过所述地理围栏118A的边界或周界时检测所述移动设备102是进入还是离开所述地理围栏。在一实施例中，所述移动设备102可以通过GPS信号或蜂窝塔三角法检测所述移动设备的当前位置。例如，所述地理围栏引擎102B可以使用GPS信号或蜂窝塔三角法获取所述移动设备102当前位置的经纬度坐标。所述地理围栏引擎102B可以将所述GPS信号或蜂窝塔三角法中的经纬度坐标与所述地理围栏118A的经纬度坐标进行比较，以确定所述移动设备是否位于所述地理围栏118A中。
检测到所述移动设备位于所述地理围栏118A中时，所述地理围栏引擎102B向所述通知引擎102C发出指示。所述通知引擎102C可以向在所述移动设备102中运行的操作系统或应用发出通知。例如，所述通知可以使应用执行操作，例如，将所述通知发送给基于位置的服务器。在另一示例中，将所述通知发送给与商户相关联的应用，向用户指示该用户在所述商户的地理位置附近。
所移动设备102还可以通过所述网络110与位置数据库112通信。所述位置数据库112可以提供与兴趣点相关联的位置。例如，所述移动设备102的用户可能对某餐厅的位置感兴趣。此时，当所述位置数据库112接收到所述移动设备102的请求时，其中，所请求包括所述移动设备102的位置，所述位置数据库112可以回复所述移动设备102附近的一个或多个餐厅位置。在一实施例中，可以使用经纬度表示所述位置。接收到所述位置数据库112的回复后，所述移动设备102可以将所述餐厅位置提供给所述地理防护引擎102B。然后所述地理防护引擎102B可以对所述餐厅位置进行处理并生成围绕所述位置的地理围栏118A。
图2示出了一种可用于图1的系统中的示例性计算设备。所述计算设备，即本示例中的移动设备102，可包括处理器210，以及所述处理器210可以访问的存储器220，如随机存取存储器(Random Access Memory，RAM)、闪存存储器或其它类型的存储器。所述存储器220可用于存储操作系统(operating system，OS)230及应用240，如开启地理围栏的应用，其中，所述应用可以向所述移动设备102的用户提供基于位置的服务。
开启地理围栏的应用240可以运行在所述OS 230上并由所述处理器210执行。所述开启地理围栏的应用240可以使用不同的技术确定所述计算设备的当前位置。例如，所述开启地理围栏的应用240可以从可选的GPS接收器280接收所述计算设备的当前位置。在另一实施例中，所述开启地理围栏的应用240可以使用不同的本地定位系统确定所述计算设备的当前位置，例如，通过使用射频收发器270及一个或多个天线290从多个Wi-Fi接入点、蓝牙基站、蜂窝塔、基站等接收信号。在另一实施例中，所述开启地理围栏的应用同时使用GPS及不同的本地定位系统。
所述处理器210可耦合至显示器250及一个或多个输入/输出(input/output(I/O)设备260，如键盘、触摸板感应器、麦克风等。所述处理器210还可以耦合至连接天线290的收发器270。所述收发器270可用于通过所述天线290发送及接收蜂窝网络信号、无线数据信号及其它类型的信号。
在一实施例中，GPS接收器280还可以使用所述天线290接收可通过通信卫星292(如GPS卫星)传输的GPS信号。在另一实施例中，所述天线290从附近的基站296接收信息或向其发送信息。
所述收发器270可通过所述天线290与所述基站296进行无线通信，例如，使用用于语音电话及报文数据转发的蜂窝通信协议及标准，如GSM、CDMA、GPRS、EDGE、UMTS、LTE、5G等，通过蜂窝无线网络进行通信。在另一实施例中，所述天线290从无线路由器294(或接入点)接收信息或向其发送信息。
图3示出了一种用于对计算设备的位置进行求值的示例性流程。现有各种技术用于生成并监控多边形地理围栏118A等地理围栏。在一示例中，可以使用启动位置功能的移动设备102定义空间边界，以标识或包围兴趣点304(如企业、机构、地标、公园或用户会感兴趣的其它位置)，并检测开启GPS的移动设备102何时进入和/或离开所述地理围栏118A的边界(如边界301)。用户可以，例如使用图形用户界面(user interface，UI)工具，定义这些边界，以创建多边形“框”和/或进入或穿过其中即发起或触发事件的边界(或周界)。在另一技术中，选择兴趣点304，如经纬度，并定义所述兴趣点304的半径或主/次轴，以围绕所述兴趣点304创建边界。
虽然所述移动设备102可对地理围栏的边界或周界进行定义，使所述地理围栏呈多边形，但是GPS接收器(或具有GPS功能的软件服务或应用编程接口(applicationprogramming interface，API))支持圆形或矩形地理围栏而不支持多边形地理围栏。因此，应用传统地理防护技术时，使用单个圆形或矩形地理围栏，如圆形地理围栏305，对由边界或周界定义为多边形地理围栏的面积或区域进行分析。
使用单个圆形或矩形地理围栏对多边形地理围栏进行分析会降低基于位置的信息的准确度，因为原先由多边形地理围栏覆盖的面积或区域现在是由改变了原先面积或区域(即覆盖更大的面积或区域)的单个圆形(或单个其它形状的)地理围栏覆盖。例如，所述圆形地理围栏305由所述兴趣点304及半径R定义，其中，所述兴趣点304通常表示所需地理位置的中心，所述半径R是确立所述兴趣点304为中心的圆圈的半径。可以预先确定所述半径定义所需的地理面积，以覆盖所述多边形地理围栏118A。创建所述圆形地理围栏305之后，可以对所述移动设备102进行监控，以确定所述移动设备102是否出现在所述圆形地理围栏305中及其在所述圆形地理围栏305中的位置，其中，所述圆形地理围栏305近似于所述多边形地理围栏118A。
为了提高基于位置的准确度并降低所述多边形地理围栏118A外部的面积或区域大小，所述计算设备(即移动设备102)生成多个圆形地理围栏区域308，以覆盖所述多边形地理围栏118A。如图中306所示，所述多边形地理围栏118A中“挤满”了所述多个圆形地理围栏308。在一实施例中，设置所述多个圆形地理围栏区域308以将所述多边形地理围栏118A外的空间(面积)大小降到最低。在一实施例中，单独的圆形地理围栏308或圆形地理围栏308的集合(组)可以有不同大小。例如，如图所示，最外层的圆形地理围栏308小于最内层的圆形地理围栏308。但是，应当理解的是，在任意数量的不同配置中，所述圆形地理围栏308可以是不同大小中的任一大小，并设置为覆盖所述多边形地理围栏118A。
在一实施例中，使用K均值聚类算法对所述多个圆形地理围栏308进行聚集，以将所述多边形地理围栏118A分割为子区域，并创建多个圆形地理围栏308覆盖每个所述子区域。详情如下文结合图4A、图4B及图4C所述。在创建所述多个圆形地理围栏308后，可以在步骤310中将其加载到地理防护引擎102B中，所述地理防护引擎102B可以对每个圆形地理围栏308进行处理。在一实施例中，在步骤310中，将所述圆形地理围栏308输入到GPS接收器280或开启GPS的软件服务或API中。
所述地理防护引擎102B对所述圆形地理围栏308进行监控，并且在所述移动设备102的当前位置在任一所述圆形地理围栏308中时发送通知。例如，可以将所述移动设备102的位置(可由位置检测引擎102A或GPS接收器280确定)与每个圆形地理围栏308的边界或周界进行比较，以确定所述移动设备102是否在任一所述圆形地理围栏308中。在一实施例中，所述移动设备102可包括应用240(开启地理围栏的应用)，用于管理与所定义的所述多边形地理围栏118A的子区域中的一个子区域相关联的圆形地理围栏308。所述应用240可以使用所述移动设备102的基于位置的服务(定位功能)确定所述移动设备102是否已经穿过所述圆形地理围栏308中的一个圆形地理围栏308的边界或周界。当确定所述移动设备102已经进入或穿过所述圆形地理围栏308中的一个圆形地理围栏308的边界或周界时，可以发送通知或指示，通报所述移动设备102已经进入或穿过所述圆形地理围栏308中的一个特定圆形地理围栏308。
接收到所述通知之后，在步骤312中，所述地理防护引擎102B确定所述移动设备102的当前位置是位于所述多边形地理围栏118A内部还是外部还是与所述多边形地理围栏118A重叠(穿过其边界或周界)。如下文结合图5B、图5C及图5D所述，使用围绕所述移动设备102的位置(中心点)的圆形区域与所述多边形地理围栏118A的相对位置表示所述移动设备102的当前位置。
图4A示出了一种将圆形地理围栏应用于多边形地理围栏的示例性流程。在一实施例中，由移动设备102执行所述流程。在另一实施例中，在移动设备102的远程服务器114等远程服务器中执行所述流程。但是，可以理解的是，图1、图2及图8中的任意设备或部件可以执行所述流程。为便于描述，在以下示例中，由所述移动设备102的处理器210执行所述流程。
为支持使用地理围栏，所述移动设备102重复确定其当前位置。然后可以将所述当前位置与定义边界或周界的位置进行比较，其中，所述边界或周界定义了特定地理围栏(如围绕兴趣点的地理围栏)。但是，所述移动设备102不停地轮询当前位置以进行比较会消耗资源，包括处理资源及能耗。地理围栏(如多边形地理围栏)的形状越复杂，消耗越多的处理资源及能耗。同理，形状(如圆形地理围栏)越简单，所述移动设备102需要越少的处理资源及能耗。因此，虽然理论上所述移动设备102可以支持任意形状及大小的地理围栏，但是这受限于处理资源的数量及实际设备的能耗。
为降低所述移动设备102中的处理器210的整体处理消耗及能耗，在公开的技术中，使用多个圆形地理围栏308近似得到更复杂的地理围栏形状，如多边形地理围栏118A。例如，可以生成并分配多个圆形地理围栏308以覆盖所述多边形地理围栏118A(如图3中306所示)。可以均匀、随机或随意地分配所述圆形地理围栏308。通过这种方式分配所述多个圆形地理围栏308，有效地将该形状更复杂的多边形地理围栏118A“变换”或“转换”成更简单的圆形地理围栏308。所述更简单的圆形地理围栏308可以由GPS接收器280进行处理(否则GPS接收器280无法处理多边形)，并且所述GPS接收器280消耗的处理资源及能源要比处理器210少得多。
将多边形地理围栏118A转换为多个圆形地理围栏308之后，所述GPS接收器280可以持续监控所述移动设备102的当前位置，并确定所述当前位置何时穿过或进入任一所述多个圆形地理围栏308。
在步骤402中，设置基线阈值(B1)。所述基线阈值(B1)定义尽管所述移动设备102的当前位置实际位于所述多边形地理围栏118A内部时，所述移动设备102的当前位置可位于所述多边形地理围栏118A外部的最大距离或面积。当近似于所述多边形地理围栏118A的多个圆形地理围栏308中的一个圆形地理围栏308的一区域延伸至所述多边形地理围栏118A的边界或周界外且所述移动设备102进入该“延伸”区域时，可能发生这种情况例如，结合图4B，区域R1是圆形地理围栏308的一部分且位于所述多边形地理围栏118A的外部(即延伸出所述边界或周界)。在此示例中，由于所述包括区域R1的圆形地理围栏近似于所述多边形地理围栏118A，并且确定所述移动设备102在所述包括区域R1的圆形地理围栏308中，则尽管所述移动设备102位于所述多边形地理围栏118A内部，仍将所述移动设备102确定为位于所述多边形地理围栏118A外部。在一实施例中，为尽量减少这种情况的发生，可以对所述基线阈值(B1)进行调整，以考虑到各种因素，如精确确定位置的准确度及可用处理能源数量。详情将在下文中描述。
在步骤404中，所述处理器210生成应当位于所述多边形地理围栏118A内部(或边上—即边界或周界上)的内插点(用点表示)。
在步骤406中，计算初始圆圈数量(k)(其中，每个圆圈代表一圆形地理围栏308)。在一实施例中，所述初始圆圈数量(k)是可以覆盖所述多边形地理围栏118A的圆圈的最小数量。
所述初始圆圈数量(k)的确定(或计算)可取决于设置的基线阈值(B1)的等级，即，结果质量需要满足的等级。例如，如果所述基线阈值(B1)设为高，则所述初始圆圈数量(k)可以为低；相反，如果所述基线阈值(B1)设为低，则所述初始圆圈数量(k)可以为更高。因此，所述初始圆圈数量(k)与所述基线阈值(B1)直接相关。
例如，参考图4C，图4C示出了一种围绕多边形地理围栏的圆形地理围栏的实例。(当单个圆形地理围栏足以满足所述基线阈值(B1)时)可通过生成单个圆圈450覆盖多边形452，初始化所述初始圆圈数量(k)。为便于描述，示出了单个圆圈450及形状简单(边界最少)的多边形452。但是可以理解的是，可以使用多个圆圈及更复杂的多边形，类似于前述附图中所示。
在一实施例中，所述单个圆圈450是能够覆盖整个所述多边形452的直径D最小的圆圈，如图所示。创建之后，确定多边形顶点间的地理中点(MidPoint)，并计算每个MidPoint与每个顶点间的距离。然后使用最大距离(maxD)及最小距离(minD)计算所述初始圆圈数量(k)：maxD/minD。(按需将计算出的初始圆圈数量(k)四舍五入为最接近的整数)。
继续参考图4C，确定所述圆圈450的质量阈值(Q1)。可以使用所述多边形452覆盖的面积与所述圆圈450覆盖的面积的差值度量所述质量阈值(Q1)。确定所述质量阈值(Q1)为差值(M)/直径(D)，其中，所述差值(M)为所述圆圈450的外边与所述多边形452的最近的边之间的最大距离，所述直径(D)为可以覆盖整个多边形452的最小圆圈450的直径。可以将所述质量阈值(Q1)与所述基线阈值(B1)进行比较，以确定质量是否合格。详情如下文所述。
生成的圆圈数量越多(因此尺寸越小)，能够越准确地近似得到多边形地理围栏(下文图7A与7B示出不同的圆圈大小)。但是圆圈数量(k)越多也需要更多的处理资源及更高的能耗，GPS接收器280的负载越大。因此，需要将圆圈数量最小化，以降低对处理资源、能耗及GPS接收器的负载的影响，同时保持满足所述基线阈值(B1)的所述质量阈值(Q1)。
Q1越低，(确定位置的)准确度越高，但是需要更多的圆圈及资源。Q1越高，准确度越低，但是需要更少的圆圈及资源。以下表1示出了这种差异性的一个示例。
表I
在一实施例中，可能存在一个被所述多边形452覆盖但是不被所述圆圈450覆盖的面积或区域(未示出)。由于对所述圆圈450进行求值以近似得到所述多边形，这可能导致所述面积或区域形成一个间隙(即，在所述多边形452中但在任意圆圈450外部)。为确定是否存在所述间隙，可以使用C/P度量第二阈值(M2)，其中，C是被所述多边形452覆盖但不被所述圆形450覆盖的面积，P是所述多边形452覆盖的面积。
在步骤408中，创建覆盖所述多边形的最小数量(k)的圆圈。如图4B所示，可以使用生成的内插点，通过K均值聚类算法等聚类算法将所述多边形地理围栏118A分割为子区域118B。可以理解的是，聚类可以使用任意聚类算法，而非限于K均值聚类算法。分割为子区域118B后，可以生成所述多个圆形地理围栏308(圆圈)，并设置为覆盖每个所述子区域118B。结合子流程408A、408B及408C对该流程进行详细描述。
在步骤408A中，将‘k’个中心点初始化为将所述多边形118A划分为分区的点。在一实施例中，所述分区是一个方向上的等分。在一实施例中，在维度(lat_span)或经度(lon_span)(以较大者为准)上进行所述划分。这使得聚类函数能够快速收敛。可以使用最大维度–最小维度计算所述维度(lat_span)，并使用最大经度–最小经度计算所述经度(lon_span)。
例如，假设lon_span大于lat_span，创建包括k个元素的经度阵列(tempArray[k])。对每个元素tempArray[i]进行如下初始化：tempArray[i]＝最小经度+(i+1)*(Lon_Span/(k+1)).然后可以生成中心点阵列(PreCenterPoint[k])。对每个元素PreCenterPoint[i]进行如下初始化：PreCenterPoint[i]＝内插点集合中的点，其中，经度等于(或最接近于)tempAarray[i].可以有不只一个点。此时，可以选择其中任意点作为中心点。可以理解的是，还可以使用该计算结果确定维度阵列的中心点。
在步骤408B中，(例如，使用所述k均值聚类算法)将所述内插点分割为k个集群，并围绕每个所述集群中的点创建圆圈308(图4B)。更具体地，分配一个包括k个元素的阵列ClusterArray，其中，每个元素具有以下子元素：(1)CenterPoint：集群的中心点；以及(2)PointArray[]：点阵列，包括集群中的所有点。然后对ClusterArray进行如下初始化：ClusterArray[i].CenterPoint＝PreCenterPoint[i]，并对内插点集合中的每个点进行循环，并在ClusterArray找到其CenterPoint最接近该点的集群，并在对应的PointArray[]中使用所述点。然后对ClusterArray[]中的每个集群进行循环，并重新计算使用的PointArray[]的CenterPoint。例如，如果PointArray[]中有n个点：
重新计算所述CenterPoint之后，对每个集群进行循环，以计算ClusterArray[i].CenterPoint与PreCenterPoint[i]之间的距离。如果每个计算的距离都足够小，创建一个包围PointArray[]中的点的圆圈。否则，对每个集群进行循环，以使PreCenterPoint[i]＝ClusterArray[i].CenterPoint，然后创建一个圆圈包围PointArray[]中的点。
在步骤408C中，当存在不只一个完全位于所述多边形118A中的圆圈308时，可选地，可以对所述圆圈308进行合并，以减少圆圈总数(k)。对于完全位于所述多边形中的每个圆圈308，将所述圆圈308置于阵列SubClusterArray[]中。然后可以使用SubClusterArray[]中的CenterPoints创建虚拟多边形，并计算初始圆圈数量(k)以及生成(重新生成)新的圆圈306。
在步骤410中，对所生成的圆圈308的质量阈值(Q1)进行求值，以确定质量是否满足所述基线阈值(B1)。当所述质量阈值(Q1)小于或等于所述基线阈值(B1)(即Q1≤B1)时，所生成的圆圈满足准确度要求(即，满足所述基线阈值(B1)，并实现了所需的计算设备位置准确度)。相应地，在步骤412中，确定质量合格；并且在步骤416中，使用所生成的圆圈(308)近似得到所述多边形地理围栏118A。
当所述质量阈值(Q1)大于所述基线阈值(B1)(即Q1>B1)时，所生成的圆圈不满足准确度要求(即，不满足所述基线阈值(B1)，且未实现所需的计算设备位置准确度)。相应地，在步骤412中，确定质量不合格，并且可以丢弃所生成的圆圈(308)。返回步骤408调整圆圈308的最小数量，即重新计算圆圈的最小数量(k)。
图5A示出了一种用于确定计算设备与地理围栏的相对位置的示例性流程。在一实施例中，由移动设备102执行所述流程。在另一实施例中，在移动设备102的远程服务器114等远程服务器中执行所述流程。但是，可以理解的是，图1、图2及图8中的任意设备或部件可以执行所述流程。为便于描述，在以下示例中，由所述移动设备102的处理器210执行所述流程。
如上文所述，所述移动设备102能够通过蜂窝塔或Wi-Fi三角法(例如，使用基站296或接入点294)检测并上报其位置(如经纬度)及准确度(如与所述位置的距离)，还能够使用GPS(例如GPS接收器280)检测并上报其位置。所述移动设备102还可以在后台运行应用(如应用240)，当发生某些预定义事件或条件时，所述设备的操作系统(如OS 230)可以触发所述应用。并且当发生某些预定义位置事件时，所述移动设备102还能够通知后台进程。在一实施例中，所述移动设备102通过网络110与远程服务器114通信，以从所述移动设备102接收地理围栏进入或离开事件。
当所述GPS接收器280或地理围栏引擎102B上报所述移动设备102的位置是在多个圆形地理围栏308中的一个或多个圆形地理围栏中时，则所述移动设备102可以对其与多边形地理围栏118A的相对位置进行求值(图3中步骤312)。通过求值可以确定所述移动设备102是在所述多边形地理围栏118A的内部还是外部还是正在穿过所述多边形地理围栏118A边界或周界(与所述多边形地理围栏118A重叠)。
位置的准确度通常是与所述移动设备102上报的经纬度(位置)的距离。因此，认为所述准确度是以所述移动设备102的当前经纬度为的中心点的圆圈524(圆形区域)的半径。假设所述位置大概率地在所述圆圈524内部，其中，所述概率为“LocP”，所述圆圈524为“LocCircle”，所述移动设备102的位置在所述多边形地理围栏118A的内部的概率定义如下：S2＝πAccuracy
为了求S1/S2的近似值，将M个点内插于LocCircle中。在一实施例中，对所述点进行均匀内插。然后确定同时位于所述多边形地理围栏118A与LocCircle中点的数量(N)，并通过N/M求S1/S2的近似值(图5E)。
返回图5A，对用于确定计算设备与地理围栏的相对位置的流程进行进一步描述。在步骤502中，检索所述移动设备102的位置及准确度。然后可以使用所述位置及准确度构建所述移动设备102的圆圈524。例如，所述经纬度(位置)可以作为所述圆圈524的中心点，所述准确度(与所述位置的距离)可以是所述圆圈524的半径。
在步骤504中，计算所述位置(经纬度)与所述多边形地理围栏118A的每个边之间的距离。在步骤506中，将每个计算出的距离与所述准确度进行比较，确定所述距离是否大于等于所述准确度(距离≥准确度)。
在步骤518中，如果所述圆圈524的中心点在所述多边形地理围栏118A的外部，确定所述移动设备102的位置在所述多边形地理围栏118A的外部(图5B)。在这种情况下，在步骤520中返回通知，指示所述移动设备102在所述多边形地理围栏118A的外部。否则，在步骤518中，如果所述圆圈524的中心点在所述多边形地理围栏118A的内部，确定所述移动设备102的位置在所述多边形地理围栏118A的内部(图5C)。在这种情况下，在步骤522中返回通知，指示所述移动设备102在所述多边形地理围栏118A的内部。
在一实施例中，如果在步骤506中确定每个计算出的距离并不大于等于所述准确度，则所述圆圈524与所述多边形地理围栏118A之间存在重叠(即，所述移动设备102正在穿过边界或周界)，流程进入步骤508，确定所述移动设备102在所述多边形地理围栏118A内部的概率。
在步骤508中，结合图5E，将M个点内插在所述圆圈524中。在步骤510中，检查每个内插点，确定其是否在所述多边形地理围栏118A内部。对于在步骤512中确定为在所述多边形地理围栏118A外部的每个内插点，流程返回步骤510。如果在步骤512中确定一内插点在所述多边形地理围栏118A内部，流程进入步骤514，确认在所述多边形地理围栏118A内部的每个点(N)，然后返回步骤510。
确定每个内插点是否位于所述多边形地理围栏118A内部之后，近似求得S1/S2为N/M，其中，N为所述多边形地理围栏118A内部的内插点的数量。
图6示出了图4A中的流程的执行示例；如上文所述，图4A中描述的将圆形地理围栏聚集在多边形地理围栏中的流程可以在不同平台上执行。如图4A所示的实施例中所述，在所述移动设备102中执行所述流程。在另一实施例中，如图所示，可以在与网络110通信的远程服务器114(即云端服务器)中执行所述流程。为避免在具有更少处理资源的所述移动设备102上进行处理，可以在所述远程服务器114上生成圆形地理围栏308。例如，满足更低质量阈值(Q1)(获得更高准确度)的圆形地理围栏308需要额外的计算资源。可以在所述远程服务器114上执行所述处理，而不消耗所述移动设备102的大量资源。所述流程完成之后，所述远程服务器114可以将计算结果分配给所述移动设备102。
图7A与7B示出了使用不同基线阈值生成圆形地理围栏时的性能数据。如图所示，根据以上流程生成圆形地理围栏308(实线)，并根据传统技术生成覆盖整个多边形的圆形地理围栏702(虚线)。以下表II(对应图7A)提供Q1及M2结果，其中，Q1设为0.20。表III(对应图7B)提供Q1及M2结果，其中，Q1设为0.10。CPU执行时间指示执行时间(单线程)。
表II
表III
基于上文所述的图5A中的流程的实施，CPU执行时间<1ms，总内存使用率<6.1KB。表IV示出了性能详情。
表IV
图8为可用于实施各种实施例的网络设备800的方框图。特定网络设备可利用所有所示的组件或仅使用所述组件的子集，且设备之间的集成程度可能不同。此外，网络设备800可包含部件的多个实例，例如多个处理单元、处理器、存储器、发射器、接收器等等。网络设备800可包括配备一个或多个输入/输出设备(如网络接口、存储接口等)的处理单元801。处理单元801可以包括中央处理器(CPU)810、存储器820、大容量存储器设备830、以及连接至总线870的I/O接口860。所述总线870可以是任意类型的若干总线架构中的一种或多种，包括内存总线或内存控制器、外设总线等。
所述CPU 800可包括任何类型的电子数据处理器。存储器820可包括任意类型的系统存储器，例如静态随机存取存储器(static random access memory，SRAM)、动态随机存取存储器(dynamic random access memory，DRAM)、同步DRAM(synchronous DRAM，SDRAM)、只读存储器(read-only memory，ROM)或其组合等等。在实施例中，存储器820可包含在开机时使用的ROM以及在执行程序时使用的存储程序和数据的DRAM。在实施例中，存储器820是非瞬时的。在一实施例中，所述存储器820包括：生成模块820A，用于生成多个圆形地理围栏，以覆盖多边形地理围栏定义的地理区域；监控模块820B，用于对所述多个圆形地理围栏进行监控，以检测进入任一所述圆形地理围栏的边界的用户设备的当前位置；确定模块820C，用于基于所述检测，确定所述用户设备的当前位置在所述多边形地理围栏中；通知模块820D，用于通知基于位置的服务所述用户设备已经进入所述多边形地理围栏；以及分割模块820E，用于将所述多边形地理围栏分割为一个或多个子区域，其中，每个所述子区域由所述多个圆形地理围栏中的一个对应圆形地理围栏覆盖。
所述大容量存储器设备830可包括任意类型的存储器设备，用于存储数据、程序及其它信息，并使所述数据、程序及其它信息可以通过总线870访问。所述大容量存储器设备830可包括，例如，固态硬盘、硬盘驱动器、磁盘驱动器、光盘驱动器等中的一个或多个。
所述处理单元801还包括一个或多个网络接口850。所述网络接口850可包括用于访问节点或一个或多个网络880的以太网线等有线链路和/或无线链路。所述网络接口850使所述处理单元801能够通过所述网络880与远程单元通信。举例来说，所述网络接口850可以经由一个或多个发射器/发射天线以及一个或多个接收器/接收天线提供无线通信。在一个实施例中，所述处理单元801耦合到局域网或广域网以进行数据处理以及与远程装置通信，其中，所述远程装置例如是其它处理单元、因特网、远程存储设施等等。
应理解，本发明可以具体体现为许多不同的形式且不应被解释为仅限于本文所阐述的实施例。准确地说，提供这些实施例是为了使本发明的主题更详尽更完整，并向本领域技术人员充分传达本发明。事实上，本主题旨在涵盖包括在由所附权利要求书限定的本主题公开的精神和范围内的这些实施例的替代物、修改和等同物。另外，在以下本主题细描述中，阐述了许多特定细节以便提供对本主题的透彻理解。然而，所属领域的普通技术人员清楚了解，可以在没有这样具体细节的情况下实践本发明的主题。
本文结合根据本发明实施例的方法、装置(系统)和计算机程序产品的流程图和/或方框图来描述本发明的各方面。应理解，流程图和/或方框图的每个方框以及流程图说明和/或方框图中的方框的组合可以由计算机可读程序指令实现。可以将这些计算机程序指令提供给通用计算机、专用计算机或其它可编程数据处理装置的处理器，以生成机器，使所述通过计算机或其它可编程指令执行装置的处理器执行的指令创建一种机制，用于实现流程图和/或方框图中指定的功能/操作。
计算机可读非瞬时性介质包括各种类型的计算机可读介质，包括磁存储介质、光存储介质、固态存储介质，但具体不包括信号。应当理解的是，可以在设备中安装软件一并出售。或者，可以获取软件并将软件加载到设备中，包括通过磁盘介质或从网络或分发系统的的任意方式，例如包括从软件创建者拥有的服务器或从所述软件创建者所用但非其所有的服务器，获取所述软件。所述软件可以存储在服务器上以通过因特网等进行分发。
计算机可读存储介质不包括传输信号本身，可以被计算机和/或处理器访问，并包括可移动的和/或固定的易失性及非易失性内部和/或外部介质。对于计算机来说，不同类型的存储介质以任意合适的数字格式存储数据。本领域技术人员应当理解的是，可以使用Zip驱动器、固态硬盘、磁带、闪存卡、磁带盒等其它类型的计算机可读介质存储计算机可执行指令，以执行所公开架构中的新方法(操作)。
本文中所用的术语仅仅是出于描述特定方面的目的，而不用于限制本发明。除非上下文清楚说明，否则本文所用的单数形式“一”和“所述”包括其复数形式。应进一步了解，本说明书中所用的术语“包括”用于说明存在所述特征、整数、步骤、操作、元件和/或部件，但并不排除存在或添加一个或多个其他特征、整数、步骤、操作、元件、部件和/或它们的组合。
对本发明的描述仅仅是为了说明及阐述，而非对本发明的穷举或将其限于所公开的形式。在不偏离本发明的范围和精神的前提下，多种修改和改变对本领域技术人员而言是显而易见的。选择本发明各个方面进行描述以便更好地解释本发明的原理和实际应用，并且使本领域技术人员能够理解本发明的适合预期特定用途的各种修改。
为施行本发明，可以由一个或多个计算设备连续执行与所公开的技术相关联的每个流程。流程中的每个步骤可以由与其它步骤中所用的计算设备相同或不同的计算设备执行，且每个步骤不一定由单个计算设备执行。
虽然已经以结构特征和/或方法动作特定的语言描述了所述主题，但是应该理解的是，权利要求书定义的主题不必局限于上面描述的具体特征或动作。相反地，上文所述的特定特征及动作作为实现权利要求书的示例性形式公开。
机译： 在移动设备上启用多边形地理围栏服务的系统和方法
机译： 在移动设备上启用多边形地理围栏服务的系统和方法
机译： 在移动设备上实现地理围栏
