用于增量式确定位置情境的方法和装置

摘要

用于为移动设备的用户导出或预测位置情境的技术，其包括：接收信号数据，该信号数据指示了具有一个或多个不同信号源的集合，对于多个不同时间中的每个时间，在所述移动设备处从所述具有一个或多个不同信号源的集合接收信号。该方法进一步包括：基于所述信号数据，在当前时间确定所述移动设备是否在指定区域的外部移动。该方法进一步包括：如果确定所述移动设备未在所述指定区域的外部移动，则在所述当前时间处，对于与所述具有一个或多个不同信号源的集合相关联的固定状态增加计数。该方法还包括：基于所述固定状态，将服务递送给所述移动设备。

说明书

背景技术

服务提供商(例如无线、蜂窝等)以及设备制造商一直努力通过例如 提供引人注目的网络服务来向消费者递送价值和便利性。一种普遍的应用 是基于无线设备的位置来向无线设备的用户递送服务，并且许多移动设备 包括全球定位系统(GPS)接收机，该接收机提供达到约30米精度的设备 地理位置。尽管适于多种用途，基于GPS数据来递送服务仍然存在问题。 一个问题是：就进行连续监控的设备上的GPS而言，功耗是高的。对于大 部分移动电话来说，仍然不可能连续追踪用户超过一段相对短的时间(例 如3小时)而不充电。第二个问题是：用于存储GPS踪迹(trace)的存 储成本也是高的。第三个问题是：仍然不是有效且高效地基于确定出不同 GPS踪迹的相似性而导出例如在常见地点(诸如咖啡厅、健身房、办公室 或家里)或其附近的用户情境。值得期望的是：导出诸如“工作”或“午 餐”或“娱乐”这样的情境，以便用于定制网络服务。然而，用于从地理 位置数据导出位置情境的现有技术在计算上是密集的，并且没有被良好地 调适用于成千上万的服务用户。

发明内容

因此，需要一种为移动设备的用户导出和/或预测位置情境的方法，其 被良好地调适用于多个用户，诸如增量式(incrementally)确定位置情境。

根据一个实施例，一种方法包括：接收信号数据，该信号数据指示了 具有一个或多个不同信号源的集合(a set of one or more dictinct singal  sources)，对于多个不同时间中的每个时间，在移动设备处从所述具有一 个或多个不同信号源的集合接收信号。该方法进一步包括：基于所述信号 数据，在所述多个不同时间中的当前时间确定所述移动设备是否在指定区 域的外部移动。该方法进一步包括：如果确定所述移动设备未在所述指定 区域的外部移动，则在所述当前时间处，对于与所述具有一个或多个不同 信号源的集合相关联的固定状态(stationary state)增加计数。该方法还包 括：基于所述固定状态，将服务递送给所述移动设备。

根据另一实施例，一种携带了一个或多个序列的一个或多个指令的计 算机可读存储介质，当由一个或多个处理器执行时，所述一个或多个序列 的一个或多个指令使得装置接收信号数据，该信号数据指示了具有一个或 多个不同信号源的集合，对于多个不同时间中的每个时间，在移动设备处 从所述具有一个或多个不同信号源的集合接收信号。还使得所述装置：基 于所述信号数据，在所述多个不同时间中的当前时间确定所述移动设备是 否在指定区域的外部移动。进一步使得所述装置：如果确定所述移动设备 未在所述指定区域的外部移动，则在所述当前时间，对于与所述具有一个 或多个不同信号源的集合相关联的固定状态增加计数。还使得所述装置： 基于所述固定状态，将服务递送给所述移动设备。

根据另一实施例，一种装备包括：用于接收信号数据的装置，该信号 数据指示了具有一个或多个不同信号源的集合，对于多个不同时间中的每 个时间，在移动设备处从所述具有一个或多个不同信号源的集合接收信号。 该装备进一步包括：用于基于所述信号数据，在所述多个不同时间中的当 前时间确定所述移动设备是否在指定区域的外部移动的装置。该装备进一 步包括：用于如果确定所述移动设备未在所述指定区域的外部移动，则在 所述当前时间，对于与所述具有一个或多个不同信号源的集合相关联的固 定状态增加计数的装置。该装备进一步包括：用于基于所述固定状态，将 服务递送给所述移动设备的装置。

根据另一实施例，一种装置包括：至少一个处理器，以及包括计算机 程序代码的至少一个存储器，所述至少一个存储器和计算机程序代码被配 置以便与所述至少一个处理器一起使得所述装置：接收信号数据，该信号 数据指示了具有一个或多个不同信号源的集合，对于多个不同时间中的每 个时间，在移动设备处从所述具有一个或多个不同信号源的集合接收信号。 还使得所述装置：基于所述信号数据，在所述多个不同时间中的当前时间 确定所述移动设备是否在指定区域的外部移动。还使得所述装置：如果确 定所述移动设备未在所述指定区域的外部移动，则在所述当前时间，对于 与所述具有一个或多个不同信号源的集合相关联的固定状态增加计数器。 还使得所述装置：基于所述固定状态，启动将服务递送给所述移动设备。

根据另一实施例，一种方法包括：促进对用户接口的访问(包括授权 对用户接口的访问权限)，所述用户接口被配置以便接收信号数据，该信 号数据指示了具有一个或多个不同信号源的集合，对于多个不同时间中的 每个时间，在移动设备处从所述具有一个或多个不同信号源的集合接收信 号。该方法进一步包括：促进对用户接口的访问(包括授权对用户接口的 访问权限)，在基于所述信号数据确定出所述移动设备未在指定区域的外 部移动的时间处，基于与具有一个或多个不同信号源的集合相关联的固定 状态，所述用户接口将服务递送给所述移动设备。

通过下面的具体描述，仅通过说明多个特定实施例和实施方式(包括 所设想的用于实现本发明的最佳模式)，本发明的其它方面、特征和优点 将变得显而易见。本发明还可以包括其它和不同的实施例，并且在不偏离 本发明的精神和范围的情况下，可以在各个明显的方面修改本发明的若干 细节。相应地，认为附图和说明书在本质上是说明性的而不是限制性的。

附图说明

在所附附图中，示例性地而不是限制性地示出了本发明的实施例：

图1A是根据一个实施例的能够增量式确定位置情境的系统的示图；

图1B是根据一个实施例的不同信号源的示图，其中在移动终端处从 所述不同信号源接收信号；

图2A是根据一个实施例的信号数据流的示图；

图2B是根据一个实施例的位置情境服务模块的组件的示图；

图2C是根据一个实施例的固定状态记录的示图；

图2D是根据一个实施例的转移状态记录(transition state record)的 示图；

图3是根据一个实施例的用于增量式确定位置情境的进程的流程图；

图4是根据一个实施例的用于针对图3的进程来检测移动的进程的流 程图；

图5是根据一个实施例的用于针对图3的进程来增量式更新固定状态 的进程的流程图；

图6A是根据一个实施例的用于针对图3的进程来增量式更新转移状 态的进程的流程图；

图6B是根据一个实施例的多个时间特征的优先性(precedence)的示 图；

图7A是根据一个实施例的用于针对图3的进程来预测下一转移状态 的进程的流程图；

图7B是根据一个实施例的在最可能的转移状态当中的Viterbi路径的 示图；

图8A是根据一个实施例的在客户端进程处的位置情境数据的示图；

图8B是根据一个实施例的在服务器进程处的位置情境接口的示图；

图9A和图9B是根据一些实施例的分别针对GSM蜂窝和WiFi接入 点的发射机覆盖区的地图；

图10A是根据一个实施例的移动终端的移动周期与非移动周期的比的 示图；

图10B是根据一个实施例的在时间上增量式积累的移动终端的固定状 态数目的示图；

图11A和图11B是根据一些实施例的分别针对GSM蜂窝和WiFi接 入点的在时间上增量式积累的移动终端的最频繁的固定状态的累积分布函 数的示图；

图12A和图12B是根据一些实施例的分别针对GSM蜂窝和WiFi接 入点的相比于其它方法来说用于构建转移状态的概率模型的时间的示图；

图13A至图13D是根据一些实施例的分别针对GSM蜂窝和WiFi接 入点的对移动和非移动转移状态的预测精度的示图；

图14A和图14B是根据一些实施例的对固定状态的出现概率的不同最 小门限(所谓的最小支持)所进行的预测数目的示图；

图15是根据一些实施例的对于GSM蜂窝和WiFi接入点的移动和非 移动的移动终端进行预测的平均时间的示图；

图16是可用于实现本发明实施例的硬件的示图；

图17是可用于实现本发明实施例的芯片集的示图；以及

图18是可用于实现本发明实施例的移动终端(例如手机)的示图。

具体实施方式

公开了一种用于增量式确定位置情境的方法和装置。在下面的描述中， 出于解释的目的，阐述了多个具体细节以便提供对本发明实施例的全面理 解。然而，显然本领域技术人员可以理解，可以在不需要这些具体细节的 情况下或者在等同布置的情况下实施本发明的实施例。在其它实例中，已 知的结构和设备以框图形式示出，以避免不必要地使本发明实施例不清楚。

图1A是根据一个实施例的能够增量式确定位置情境的系统100的示 图。该实施例不要求现有技术方法中的过量的功耗、存储装置、计算源或 用户牵连。为解决该问题，并不预测用户将去往的地方的精确地理坐标， 图1A的系统100而是引入了以下能力：预测用户可能转移到或者从其转 移出的位置状态。如这里所使用的，用户的每个位置状态指代了在空间中 具有一个或多个锚点/区域的集合，并且根据那些锚点或者用户评论或通信 (当其与那些锚点相关联时)搜集情境。在进行查询之后，预测任务产生 出针对给定时间窗口的所预测位置状态的序列。通过精确且高效地解决该 问题，启用了一组新的基于位置的服务(LBS)，其可以基于用户的当前 和未来位置状态来向他/她智能地推荐信息。

在特定实施例中，提供了增量式位置状态获取和预测(iLoc)构架， 用于通过利用用户的移动设备上的传感器信息来解决预测问题。ILoc通过 恒定地监控移动设备的信号环境来增量式学习位置状态。学习和预测模块 被紧密地集成到一个单框架中。从而，iLoc能够连续更新位置状态，并且 同时预测未来的位置状态。

如图1A所示，系统100包括移动用户设备(UE)101，移动用户设 备(UE)101经由通信网络105而连接到服务器主机130和服务器主机140。 举例来说，系统100的通信网络105包括一个或多个网络，诸如数据网络 (未示出)、无线网络(未示出)、电话网络(未示出)或其任何组合。 可以设想到，数据网络可以是任何局域网(LAN)、城域网(MAN)、广 域网(WAN)、公共数据网(例如因特网)或任何其它合适的分组交换网 络，诸如商业拥有的、专有的分组交换网络，例如，专有电缆或光纤网络。 另外，无线网络可以例如是蜂窝网络，并且可以采用各种技术，包括增强 型数据速率全球演进(EDGE)、通用分组无线电服务(GPRS)、全球移 动通信系统(GSM)、因特网协议多媒体子系统(IMS)、通用移动电信 系统(UMTS)等，以及任何其它合适的无线介质，例如微波接入(WiMAX)、 长期演进(LTE)网络、码分多址(CDMA)、宽带码分多址(WCDMA)、 无线保真(WiFi)、卫星、移动ad-hoc(特定)网络(MANET)等。

UE 101是任何类型的移动终端或便携式终端，包括移动手机、站台、 单元、设备、多媒体输入板、因特网节点、通信器、桌上型计算机、膝上 型计算机、个人数字助理(PDA)或其任何组合。还可以设想到UE 101 可以支持针对用户的任何类型的接口(诸如“可佩戴式”电路等)。UE 101 使用一个或多个无线链路107来与网络105通信。下面参考图18更详细地 描述了示例移动终端。服务器主机130或服务器主机140是任何的移动或 固定终端；并且分别通过可以是有线的或无线的网络链路103来与网络105 通信。

移动UE 101包括位置情境客户端进程103，而服务器主机130包括位 置情境服务进程132，以便确定UE 101的位置情境。该位置情境然后被提 供给其它网络应用，诸如在服务器主机140上的基于位置的服务进程142。 如以下更详细的描述，位置情境服务132采用具有一个或多个用户状态记 录136的数据库134。

举例来说，UE 101和主机130或主机140使用已知的、新的或仍在开 发的协议来彼此通信以及与通信网络105的其它组件进行通信。在该情境 中，协议包括定义了通信网络105中的网络节点如何基于在通信链路上发 送的信息来彼此交互的一组规则。这些协议在每个节点内的不同操作层是 有效的，从生成和接收各种类型的物理信号，到选择用于传输那些信号的 链路，再到由那些信号所指示的信息格式，以及到标识在计算机系统上执 行的哪个软件应用发送或接收了该信息。在开放系统互连(OSI)参考模 型中描述了用于在网络上交换信息的在概念上不同的协议层。

在网络节点之间的通信通常通过交换离散数据分组来实现。每个分组 通常包括(1)与特定协议相关联的头部信息，以及(2)有效载荷信息， 其在头部信息之后并且含有可独立于该特定协议而被处理的信息。经常， 用于特定协议的有效载荷中的数据包括：用于所谓被封装在较低层协议中 的一个不同协议的有效载荷和头部。

在各个设备(诸如UE 101和服务器主机130或服务器主机140)上执 行的进程经常使用网络通信的客户端-服务器模型来进行通信。计算机进 程交互的客户端-服务器模型广为人知并且广为应用。根据客户端-服务 器模型，客户端进程向服务器进程发送包括请求的消息，并且服务器进程 通过提供服务来进行响应。服务器进程还可以返回具有对客户端进程的响 应的消息。通常，客户端进程和服务器进程在不同的计算机设备(所谓的 主机)上执行，并使用用于网络通信的一个或多个协议经由网络来进行通 信。术语“服务器”常规上用来指代提供服务的进程，或者在其上操作进 程的主机。类似地，术语“客户端”常规上用来指代进行请求的进程，或 者在其上操作进程的主机。如这里所使用的，术语“客户端”和“服务器” 指代进程，而不是主机，除非在上下文中另有明示。另外，由于包括可靠 性、可扩缩性和冗余度等在内的原因，通过服务器来实施的进程可以作为 在多个主机(有时称为层级(tiers))上的多个进程分开运行。在与通信 网络相连的大部分节点上可用的熟知的客户端进程是万维网客户端(称为 “Web浏览器”或简称为“浏览器”)，其通过根据超文本传输协议(HTTP) 而格式化的消息来与提供了Web页面的大量服务器(称为万维网(WWW) 服务器)中的任何服务器进行交互。

根据所述实施例，至少部分地根据从不同信号源接收的信号(诸如形 成无线链路107的信号)来导出UE 101的位置情境。如这里所使用的， 术语“固定无线发射机”指代用于无线通信的任何无线发射机，其在延续 的时间段上(该时间段相比于用来确定移动终端的位置情境的时间来说是 长的)保持在一个位置，例如，在超过约一周的时间上保持在一个位置。 尽管关于无线保真(WiFi)接入点和全球移动通信系统(GSM)基站描述 了各个实施例，但是可以想到，这里所描述的方法可用于其它无线通信发 射机，诸如用于参考通信网络105所述的网络通信的发射机中的任何一个。

图1B是根据一个实施例的固定无线发射机的示图，在移动终端处同 时接收来自所述固定无线发射机的信号。移动终端150是移动台UE 101 的示例。为了说明的目的，假设移动终端150是与GSM基站通信的蜂窝 电话，并且包括与处于范围内的任何WiFi接入点通信的WiFi网络卡。如 图1B所示，移动终端处于蜂窝电话网络的三个GSM基站160a、160b、 160c(下文中统称为GSM基站160)的范围内，从而与所述三个GSM基 站160a、160b、160c交换数据分组。移动终端也处在与因特网相连的两个 WiFi接入点162a、162b(下文中统称为WiFi接入点162)的范围内，从 而可与所述两个WiFi接入点162a、162b交换数据分组。

根据所述实施例，位置情境客户端103连续地对来自用户移动终端101 的信号指纹(signal fringerprint)进行采样。在每个固定采样时间间隔(例 如30秒)处，其对从处于范围中的所有无线发射机接收的信号进行采样， 并将指示了那些信号的发射机的数据发送到位置情境服务132。例如，采 样了两个信号指纹/向量：GSM蜂窝标识符；以及WiFi接入点标识符，(例 如，服务集合标识符(SSID)，其是无线局域网(WLAN)的名称)。在 一个或多个数据分组的信号数据流中将信号指纹发送给位置情境服务 132。

图2A是根据一个实施例的信号数据流200的示图。信号数据流200 包括第一时间字段201a和第一信号数据字段203a，之后是第二时间字段 201b和第二信号数据字段203，之后是由省略号209指示的随后的字段。 在一些实施例中，根据数据被接收的时间来推断出在时间字段201a、201b 和由省略号209指示的其它字段(下文中统称为时间字段201)中的信息； 并且从信号数据流200中省略时间字段201。每个信号数据字段203a、203b 以及由省略号209指示的其它字段(下文中统称为信号数据字段203)持 有指示了以下内容的数据：用于处在一种或多种(例如WiFi或GSM)无 线通信范围内的一个或多个不同信号源的标识符。例如，信号数据字段203 持有用于GSM基站160和WiFi接入点的数据，在移动终端150处同时接 收来自所述GSM基站160和WiFi接入点的信号。

可以使用任何方法来在信号数据字段203中指示无线发射机标识符 (ID)。例如，在一些实施例中，明确地包括了用于每个ID的字母和数 字的代码。在一些实施例中，标识符具有可变的长度且被散列成固定长度 数目的比特。在一些实施例中，以用于所遇到的每个无线发射机的向量位 置来定义二进制向量，其中向量尺寸随着时间而增加。向量位置中的“0” 指示了对应的发射机在特定时间并未处于UE 101的范围中，而“1”指示 了其处于范围中。在一些实施例中，向量被包括在信号数据字段203中。 在一些实施例中，在信号数据字段203中指示了向量的非零位置的列表。 可以在发射前在位置情境客户端103处形成向量，或者在收到时由位置情 境服务132来形成向量。通常，在时间间隔i处单个信号数据字段的内容 是由一个或多个无线发射机标识符α的向量vi所表示的集合，例如：

vi＝αik其中k＝1，Ki

其中，Ki是在时间间隔i处在移动终端处所接收到的无线发射机ID的数 目。

当移动终端150基本没有移动(例如没有在限定的或另外指定的区域 外部移动)时，由连续的信号数据字段203所指示的标识符是相似的(轻 微地发生改变，例如，如果一个或多个WiFi接入点接通或断开，或者用 户移动到公寓内的不同位置)。然而，当移动终端150显著地在移动时， 由连续的信号数据字段203所指示的标识符较为明显地发生改变并且因此 不那么相似。当移动终端并不频繁移动从而具有发射机ID的相似集合时， 那些相似集合定义了固定状态，例如限定的区域，在该区域中，移动终端 的用户趋于停留。通过固定转移时间间隔(计时单元(tick))、初始固 定状态(起始地状态(From State))和最终固定状态(目的地状态(To  State))来定义转移状态，并且转移状态包括其中初始和最终状态都是相 同的固定状态的那些状态。因而，对于计时单元来说保持不变的固定状态 (大部分固定状态都如此)是所有可能的转移状态的集合的成员。在一些 实施例中，转移时间间隔(计时单元)与用于确定移动终端是否在移动的 采样时间间隔相同。然而，通常计时单元(例如大约10分钟)长于采样时 间间隔(例如30秒至2分钟)。

图2B是根据一个实施例的位置情境服务模块220的组件的示图。模 块220是位置情境服务进程132的一个实施例。可以想到，这些组件的功 能可被组合到一个或多个组件中，或者通过相同或不同设备、计算机或芯 片集上(包括在主机130、主机140或UE 101上)的等同功能性的其它组 件来实现。在该实施例中，位置情境服务模块220包括注释模块221、学 习模块222和预测模块228，以及用于其它应用的应用编程接口API 240， 以便请求和接收移动设备的当前和预测的位置状态。来自学习模块222的 输出是具有移动分类225的信号数据流以及固定和转移状态的数据库230。 来自学习模块222的输出由状态预测模块228用来向外部应用API 240提 供当前和/或预测的状态229。因而，位置情境服务模块220接受用户输入 210和信号数据流200，并将当前和未来的位置状态229提供给一个或多个 外部应用242。例如，位置情境服务模块220确定出用户当前在工作但是 将要离开去吃午餐；并将该信息传递给外部应用242，像基于位置的服务 142，诸如向将在预订餐馆附近吃午饭的用户提供餐馆优惠券的行销服务。

用户输入是被传递到位置情境服务器的由用户输入的任何内容，包括 对用于标识用户当前位置的提示的任何响应、对用户在移动设备上所做或 所说的任何事情(包括打开和关闭应用)的任何响应。例如，在一些实施 例中，当标识出主要固定状态(primary stationary state)时，如在下文中 更详细描述的，用户被提示以便利用可用于标记相关联的固定状态的单词 或短语来标注用户的当前位置。在一些实施例中，当用户处在主要固定状 态之一中时，用户的消息或语音呼叫被监控，并且单词被挖掘(mined) 以便导出用于该固定状态的情境。例如，如果用户重复地说着或写着指示 了“运动(working out)”、“增氧健身法(aerobics)”、“锻炼(exercise)” 等的文本，则推断该固定状态与健身房相关联。

注释模块221取得由位置情境客户端103转发的用户输入数据210， 并确定记号、标签或标记或者某种组合以便依附于由学习模块222所确定 的固定或转移状态。注释组件负责将用户标记的状态连接到所学习的状态。 因而，输出的状态信息可具有所依附的更多语义信息(例如“在家中”或 “在工作”)。在使用被动模式的实施例中，服务器可以监听从移动设备 (例如微薄)推送出的内容。基于该内容，可以导出位置标记信息。在使 用主动模式的实施例中，针对信息而向用户进行提示或询问。例如，当系 统认为用户处在特定重要的固定状态时，这些实施例提示用户以便确定不 同的位置标记。系统仅需要对用户提出非常少的问题，这使得询问方法非 常可行并且较少地骚扰用户。在一些实施例中，省略了注释模块221。

在一些实施例中，信号数据流200包括临时(occasional)GPS地理位 置，其可以用于确定哪个特定位置与固定状态相关联并进一步提供情境。 例如，可以在与用健身房标签来标记的固定状态相关联的GPS位置处或附 近为该健身房确定街道地址。在一些实施例中，例如当确定移动终端处在 固定状态中时，位置情境服务模块向位置情境客户端103发送请求，以便 捕获GPS位置并将其包括在信号数据流中。通过仅使用临时GPS地理位 置，移动终端的功率、存储器和计算资源不会像依赖于用于预测未来用户 位置的GPS的现有方法那样承受严重负担。

学习模块222包括移动检测模块224、增量式状态学习模块226和数 据库230，所述数据库230具有用于每个用户的固定状态数据结构232以 及用于每个用户的转移状态数据结构234。因而，数据库230是数据库134 的实施例，而用户状态记录136被实现为固定状态数据结构232和转移状 态数据结构234。在下面的示图和流程图中更详细地描述了由这些模块和 数据结构中的每一个所提供的功能。

图2C是根据一个实施例的固定状态记录250的示图。固定状态记录 250是在固定状态数据结构232中的一个记录。固定状态记录220包括用 户ID/标记/情境字段251、状态ID字段252、概率字段258，以及持有发 射机ID集合(例如发射机ID第一集合字段254a、发射机ID第二集合字 段254b以及由省略号259所指示的其它字段(下文统称为发射机集合字段 254))的一个或多个字段，以及一个或多个计数字段，例如第一计数字段 256a、第二计数字段256b以及由省略号259所指示的其它字段(下文统称 为计数字段256)。

用户ID/标记/情境字段251持有指示了用户的数据(预计每个用户具 有不同的固定和转移状态以及改变模式)。在一些实施例中，用户ID/标 记/文本字段251包括指示了用户所提供的标记的数据，例如“工作”，或 者通过其它方式所确定的情境，例如通过分析消息或GPS地理位置。

状态ID字段252持有为固定状态提供了唯一标识符z的数据，例如针 对固定状态数据结构的索引，或者针对每个用户或移动设备重新开始的序 列号。

每个发射机集合字段254(例如发射机集合字段254a)持有指示了一 个或多个不同信号源(诸如在用户的移动终端处同时接收到的无线发射机 ID)的数据，例如当服务确定移动终端为“否”时所接收到的一个向量vi 的值。每个计数字段256(例如计数字段256a)持有指示了采样间隔的数 目的数据，其中对于所述采样间隔同时接收到了发射机ID的该特定集合。 被确定与同一固定状态相对应的不同但相似的发射机ID集合被包括在不 同的发射机集合字段254中，例如发射机集合字段254b，其具有对应的计 数字段，例如256b。

所指示的无线发射机可以是固定的或非固定的发射机。使用非固定的 发射机(例如蓝牙)涉及用于本地化(localize)这些发射机的步骤。在一 些实施例中，使用从固定发射机(例如GSM、WiFi)挖掘的固定状态来 划分非固定发射机(例如蓝牙或其它ad-hoc网络)。根据这些划分，可以 标识非固定发射机，其具有良好的位置感知(例如当用户在办公状态时总 会出现)或情境(例如，在特定车辆中)。在该步骤之后，为了确定固定 状态或转移状态或相关联的情境或者某种组合，在一些实施例中使用本地 化的非固定发射机。

如在下文更详细描述的，确定具有不同信号源(例如发射机ID)的两 个不同的集合是否相似；以及，在一些实施例中，基于在给定了特定的固 定状态的情况下发现特定发射机ID的后验概率(基于过去历史的概率) 来进行该确定。该概率由符号P(ID/z)来表示。通过以下方式可以确定 该值：对字段254中的发射机ID进行分类，对于其中出现了该ID的每个 集合增加计数，以及除以计数字段256中的计数的总和。因而，出现在每 个集合中的ID将具有100％的概率，而出现在少量集合中的ID将具有较 小的概率。在一些实施例中，当更新固定状态记录250时更新固定状态中 的每个发射机ID的概率，并将经更新的值存储在概率字段258中。

图2D是根据一个实施例的转移状态记录260的示图。转移状态记录 260是转移状态数据结构234中的一个记录。转移状态记录260包括用户 ID字段261、起始地状态ID字段262、目的地状态ID字段264，以及在 先状态和计数字段270。记录260还包括一个或多个时间情境字段，例如 时间情境字段266a、字段266b以及由省略号269所指示的其它字段(下 文统称为时间情境字段266)。记录260还包括一个或多个平均持续时间 字段，例如平均持续时间字段267a、字段266b以及由省略号269所指示 的其它字段(下文统称为平均持续时间字段267)，以及一个或多个持续 时间标准偏差(STD)字段，例如STD持续时间字段268a、字段268b以 及由省略号269所指示的其它字段(下文统称为STD持续时间字段268)。

用户ID字段261持有指示了用户(预计每个用户具有不同的固定和 转移状态以及改变模式)的数据。起始地状态ID字段262持有指示了以 下内容的数据：用于在时间计时单元(time tick)的开始处的固定状态的 唯一标识符z1。目的地状态ID字段264持有指示了以下内容的数据：用 于在时间计时单元的结尾处的固定状态的唯一标识符z2。

每个时间情境字段266(例如时间情境字段266a)持有指示了诸如周 末或工作日，上午或下午或夜晚，与时间计时单元的开始相关联的时间特 征的数据。可以定义若干时间特征。时间特征具有固定数目的域值，其表 示时间的一些语义概念。例如，特征可具有{上午、下午、夜晚}作为其域 值。在表1中，列出了在示例实施例中使用的示例时间特征的集合。每个 时间特征具有唯一的ID；特征的每个值也具有唯一的ID(其起到积累数 据的bin(容器)的作用)。在所述实施例中，出于说明的目的，定义了 非常一般的特征。可以想到，可以在其它实施例中容易地增加更多的特定 于域的特征。

表1.示例时间特征

每个平均持续时间字段267(例如平均持续时间字段267a)持有指示 了在转移状态中的平均持续时间的数据。可使用任何方法来指示平均持续 时间。在一些实施例中，平均持续时间字段包括对于在当前时间情境中观 察到多少转移发生的计数，从而使得可通过以下方式来更新持续时间：对 于最后观察到的转移持续时间扣除其对总体计数的相对贡献。每个STD持 续时间字段268(例如STD持续时间字段268a)持有指示了以下内容的数 据：用于完成转移状态的持续时间的标准偏差。可使用任何方法来指示STD 持续时间。在一些保存了平均持续时间字段267中的持续时间观察量的数 目的实施例中，STD持续时间字段268指示了自乘的(squared)持续时 间的总和，其可以用每个新的自乘的持续时间来进行更新。可以根据自乘 的持续时间的总和连同观察量的数目和平均值一起来计算标准偏差，在平 均持续时间字段267中指示了所述观察量的数目和平均值。

可以在不同时间观察到特定的转移状态，并且所述特定的转移状态因 而可以与不止一个时间情境相关联。因而，在一些实施例中，不同的时间 特征值被包括在不同的时间情境字段(例如字段266b)中，其具有对应的 平均持续时间字段(例如267b)以及STD持续时间字段268b。

如下文更详细描述的，给定当前转移状态以及在转移状态当中的变化 的先前分布，确定不同的转移状态的概率。因而，在一些实施例中，转移 状态记录260包括在先状态和计数字段270。在先状态和计数字段270持 有指示了以下内容的数据：刚好在由字段262和264指示的转移状态(z1 至z2)之前观察到的转移状态(例如za至zb)。在先状态和计数字段270 还包括指示了以下内容的数据：刚好在当前转移状态之前观察到多少次先 前状态(例如za至zb)。来自每个转移状态记录的该数据可用于确定在 不同转移状态当中的分布的后验概率。在一些实施例中可以通过数学模型 拟和所述数据，诸如本领域熟知的多项式拟和。

尽管上文出于说明的目的将记录示为具有按照特定顺序的特定字段的 数据的邻接块(contiguous blocks)，然而在其它实施例中，一个或多个字 段或记录或其部分可以按照相同或不同的顺序被安排在一个或多个网络节 点上的数据库的相同或不同部分上。

图3是根据一个实施例的用于增量式确定位置情境的进程的流程图。 在一个实施例中，位置情境服务模块220实施进程300，并且其实现于例 如芯片集中，所述芯片集包括如图17所示的处理器和存储器、如图18所 示的移动终端或者如图16所示的通用计算机。尽管出于说明的目的而按照 特定的顺序在图3中示出了特定步骤以及后续的流程图(图4、图5、图 6A和图7A)，但是在其它实施例中，一个或多个步骤被省略或者实施成 不同的顺序或者在时间上重叠、顺序或者并行，或者增加额外的步骤，或 者按照某种组合方式来改变所述进程。

在步骤301，接收信号数据流中的当前数据。例如，从特定用户的移 动终端150接收信号数据流200中的信号数据203b。在步骤303，将用户 的移动终端分类为在当前时间移动或不移动。在所述实施例中，如下面参 考图4的更详细的描述，基于确定了在当前和先前时间处的发射机ID的 相似性来实施步骤303。在一些实施例中，通过学习模块222的移动检测 模块224来实施步骤301和303。

在步骤305，基于在步骤303中实施的分类来确定移动终端当前是否 在移动。如果不是，那么在步骤307中，更新固定状态记录。在所述实施 例中，如下面参考图5的更详细的描述，基于找到特定状态中的发射机ID 的后验概率来实施步骤307。在更新了固定状态之后，或者如果在步骤305 中确定用户的移动终端当前在移动，那么在步骤309中，更新用户的转移 状态的数据。在所述实施例中，如下面参考图6A的更详细的描述，基于 对于给定时间特征来说的转移状态持续时间的后验概率来实施步骤309。 在一些实施例中，通过增量式状态学习模块226来实施步骤305和步骤307 和步骤309。

在步骤311，确定是否收集了足够的历史数据来进行对未来转移状态 的预测。例如，在一些实施例中，在一周的不同日子，或者至少在周末和 非周末之间，预计有不同的移动，从而认为在一周的重要部分(诸如大约 三天至大约五天)上的数据足以用来进行预测。在其它实施例中，其它持 续时间是足够的。例如，对于应急或军事工人，可认为一天足以进行预测。 步骤311包括确定是否存在对预测未来状态的任何期望，例如，因为外部 应用242已经请求了针对特定查询时间的预测。如果没有来自任何外部应 用的对于预测未来状态的请求，那么在一些实施例中，步骤311确定没有 用于预测的足够的数据。

如果数据不足以进行预测，那么在步骤313中，基于当前或最新近的 (most recent)转移状态或固定状态，将服务递送给用户。例如，外部应 用242通过应用API 240来向位置情境服务220查询最新近的固定状态或 者基于最新近的固定状态的转移状态，并且基于该状态来向用户移动终端 递送优惠券。

如果存在用于进行预测的足够的数据，那么在步骤315中，进行对未 来转移状态的零次或更多次预测，包括维持有同一固定状态的任何转移状 态。在所述实施例中，如下面参考图7A的更详细的描述，通过以下方式 来实施步骤315：基于在计时单元期间一个或多个转移状态变成不同的转 移状态的后验概率，确定在未来时间处的最可能的转移状态。在一些实施 例中，通过状态预测模块228来实施步骤311和步骤315。

如果在步骤317中确定满足了条件来结束对当前和未来状态的确定， 则进程300结束。否则，在步骤301中继续进程。

图4是根据一个实施例的用于为图3的进程300的步骤303检测移动 的进程的流程图。进程400用于检测移动终端是否表现为在移动，同时说 明了以下概率：即使在移动终端是固定的时候，发射机的群体也可能有一 些改变。基本构思为：如果终端没有移动太多，则对应的信号指纹应彼此 保持相对地相似。将信号数据流划分成在当前时间处结束的固定长度时间 窗口(例如10分钟)的滑动集合。确定用于输入信号数据流的两个最新近 的(most recent)时间窗口。在这两个窗口上评估在间隔[0到1]上定义的 相似性函数M。然后通过在该相似性函数的结果上施加移动门限值τ_M来 构建分类器。

在步骤401，当前窗口被定义具有来自在当前时间处结束的信号数据 流200的一个或多个邻接信号数据字段203。在步骤403中，前一窗口被 定义具有相同数目的邻接信号数据字段，但是在比当前时间要早的时间处 结束。每个窗口因此具有w个信号数据字段。在一些实施例中，这两个窗 口交叠并且在两个窗口中都包括一些信号数据字段。在所述实施例中，在 步骤403所定义的前一窗口结束在步骤401所定义的当前窗口的第一信号 数据字段之前的最后的信号数据字段上。在一些实施例中，每个窗口仅包 括一个信号数据字段。

在步骤405中，对于两个窗口中的信号数据字段203确定出相似性测 量。可以使用任何相似性测量。在使用GSM和WiFi流的所述实施例中， 使用(许多信息检索系统常用的)余弦相似性来定义相似性函数。对于这 两个时间窗口，将观察量分别分组到2个向量v1和v2中。其中i是当前 采样时间的索引，当前窗口信号v1＝vi，vi-1，...，vi-w；并且前一窗口信号 v2＝vi-w-1，vi-w-2，...，vi-2w。然后可以由公式1来定义余弦相似性。

M＝v1·v2/(|v1|×|v2|)        (1)

在步骤407中，将这两个窗口的相似性与移动门限τ_M进行比较。如果 相似性大于门限，那么在步骤411中，分类器确定移动终端没有在移动。 否则，在步骤409中，分类器确定移动终端在移动。在分类之后，该进程 结束；并且控制前进到进程300的步骤305。

图5是根据一个实施例的用于为图3的进程增量式更新步骤307中的 固定状态的进程500的流程图。在进程500的开始处，提供了无线发射机 ID的当前向量vi用于更新固定状态。当接收到无线发射机ID的第一向量 时，不存在固定状态；也就是说，固定状态的集合Z为空。当随时间增量 地学习了固定状态时，所述集合在成长。

在步骤501中，确定是否存在与当前向量vi相比较的另一固定状态。 如果没有，那么在步骤503中，将基于向量vi的新的固定状态添加到固定 状态数据结构，例如作为新的固定状态记录250。例如，当移动终端不在 移动时，将最初的向量vi添加为第一固定状态记录250中的第一字段。在 字段252中形成和存储固定状态ID z，在字段254a内存储vi中的无线发 射机ID，以及在字段256a中存储作为1的计数。给定固定状态z，对于在 vi中找到每个发射机ID的100％的概率，更新概率字段258。然后更新进 程结束；并且控制前进到图3中的步骤309以便更新转移状态。

如果存在另一固定状态，那么在步骤505，检索用于该固定状态z的 固定状态记录。在步骤507中，确定概率P(z|vi)：下一固定状态是在 给定发射机ID的当前向量vi下的固定状态。

在步骤509中，确定概率P(z|vi)是否大于群集门限(cluster  threshold)τ_C。如果是的话，那么在步骤511中，更新固定状态记录，即， 将当前向量添加到与该固定状态相关联的发射机ID集合的群集中。在示 例实施例中，群集门限是10％的概率。因而在该实施例中，给定当前向量 vi下的当前状态z的概率大于10％使得当前状态被更新以便包括向量vi 中的发射机ID的集合。

在步骤511中更新固定状态记录。例如，将向量vi与发射机集合字段 254中的发射机ID的集合之一进行匹配。如果找到精确的匹配，则增加相 关联的计数。如果没有，那么将新的发射机集合字段254添加到具有向量 vi中的发射机ID的精确集合的记录，并且其关联的计数字段被设置成指 示1。在一些实施例中，还更新概率字段258以便指示P(ID|z)的新值。 更新进程然后结束，并且控制前进到步骤307。

如果在步骤509中确定概率P(z|vi)不大于门限τ_C，则控制返回到 步骤501，如上所述，以便确定在数据库中是否已经存在另一固定状态记 录。

在所述实施例中，在步骤507中，基于在给定固定状态(如在固定状 态记录的字段258中找到的那样)下vi的每个发射机ID的各个概率来估 计概率P(z|vi)。实质上，在步骤507中，增量式状态学习模块226计 算P(z|vi)的后验分布。每个输入可被分解成特征值对(也称为属性值 对)的集合。例如，在时间ti处输入的WiFi信号可具有被表示为IDk(k ＝1到Ki)的具有Ki个WiFi ID的集合，并且可以作为二进制特征来处 理。可以将所述后验分布估计为如公式2所示。

P(z|vi)＝P(z)×∏_k＝1toKi P(IDk|z)/(∑_j＝1toZ P(zj)×∏_k＝1toKi P(IDk|zj) (2)

其中Z是集合Z中的固定状态的数目。条件独立假设，即P(vi|z)＝∏_k＝1，KiP(IDk|z)，类似于Naive Bayes(NB)条件。这是合理的假设，因为传感 器特征(例如WiFi SSID)经常被独立地建立。该假设在每个P(IDk |z) 不等于零时成立；否则的话，输入向量的似然概率Pr(vi|z)变为0。这 通过使用两个不同的考虑来进行处理。在第一情况中，如果输入向量vi中 的大部分(例如70％)发射机ID不在群集z中，则对于该群集的似然概 率P(z|vi)变为零。在第二情况中，给定固定状态z，输入向量中的仅一 小部分项目不在。向每个不在的项目IDk指派小的概率。这样，整体似然 性将保持为非零。在实验中，如下面更详细的描述，向每个不在的IDk指 派一值，该值等于目前为止所观察到的流输入的大小的倒数。

因而，在所述实施例中，为了评估公式2，在步骤521，获得vi中的 下一个IDk。在步骤523，确定是否P(IDk|z)＝0，例如，因为在当前状 态z中先前还未观察到该特定的无线发射机ID。如果是这样的话，那么在 步骤525中，将小的非零值指派给P(IDk|z)，例如直到当前时间的信 号数据流的大小的倒数。在步骤527中，确定vi是否包括70％以下的在固 定状态z中已检测到的发射机ID。如果是的话，则控制前进到步骤531以 便设置值P(z|vi)＝0，从而确保用于当前固定状态z的记录不被更新。 如果在步骤523中确定P(IDk|z)不等于零，或者确定vi包括70％或以 上的z中的发射机ID，则控制前进到步骤529，以便确定在vi中是否存在 另一IDk。如果是的话，则控制返回到步骤521以便获得vi中的下一IDk。 否则的话，对于全部的k＝1到Ki，P(IDk |z)是非零的，并且可以评估 公式2。在步骤533中，使用公式2(其作为P(IDk|z)的函数，其中k ＝1到Ki)来确定P(z|vi)。

图6A是根据一个实施例的为图3的进程的步骤309增量式更新转移 状态的进程600的流程图。转移状态提供了实施时间预测的能力，从而使 得在给定对转移状态的过去观察量的情况下，可以预测未来的转移状态。 存在两种转移：自转移；以及从两个不同固定状态的转移。在转移模型中， 转移状态空间S包括所有可能的固定状态对(即，S＝{(za-zb)，其中 a，b＝1，Z})。该进程开始于评估最后获知的固定状态z的重要性。还将概 率P(z)认为是对固定状态的支持(support)。如果对固定状态的支持大于 预定的最小支持，则认为是重要的。在所述实施例中评估了不同的最小支 持设定。出于说明的目的，假设最小支持是1％。如果固定状态是重要的 (例如具有大于最小支持的概率)，并且如果主体在移动，那么在记录点， 目的地仍是未知的。对起始地状态的信息以及时间情境信息进行缓存。一 旦主体到达固定状态，如果缓存的起始地状态不为空，则对涉及不同固定 状态的转移进行更新。否则，更新自转移。

给定时间和转移信息，根据公式3，使用时间特征和过去的观察量来 更新在给定前一转移状态下的下一转移状态的概率P(si+1|si)。

P(si+1|si)＝P(si+1|si，γ，β1...βB)        (3)

其中γ表示在si中停留的时间段。获得B个时间特征的集合(β1...βB)。 如下文参考优先性图形的更详细的描述，不允许时间特征值对相互包括； 并且因而可以假设时间特征值对是条件独立的。

为了允许假设条件独立，使用优先性图形来移除依赖性。给定时间实 例ti，可能具有多个匹配的时间特征值对。所期望的是，仅选择有区别的 或重要的那些时间特征值对。优先性图形对重要的关系进行编码。该图形 为全部时间特征值对定义了偏序(partial-order)。图6B是根据一个实施 例的针对多个时间特征的优先性的示图。优先性图形600具有用于每个特 征的每个值的节点。用于第一特征的值的节点是：表示表1中的B1的上 午节点651a、表示B2的下午节点651b，以及表示B3的夜晚节点651c。 用于第二特征的值的节点是：表示B4的周末节点652a，以及表示B5的非 周末节点652b。用于第三特征的值的节点是：表示B6的周末上午节点 653a、表示B7的周末下午节点653b，以及表示B8的周末夜晚节点653c。 用于第四特征的值的节点是：表示B9的假期节点654a，以及表示B10的 非假期节点654b。上面的节点比下面的连接节点占有优势(dominate)， 例如具有更有用的描述(其包括并替换不那么有用的描述)。

通过优先性图形，可以更好地表征时间实例ti。表2示出了提取时间 特征的进程。

表2.时间特征提取

首先将时间实例与所有可能的时间特征值对进行匹配。检查优先性图 形以便消除那些已被占优(dominated)的值。例如，1月9日上午8点是 正常工作日的上午，其匹配于两个特征值对(TF1B1：上午，以及TF4B10： 非假期)。由于“上午”比“非假期”更具有区别性，因此“上午”具有 更高的优先性并被用作最终提取的时间特征bin值。在提取进程的末尾， 仅剩下一个或多个重要的特征值的集合来表示从离开固定起始地状态(z1) 至到达固定目的地状态(z2)的时间间隔。

假设时间特征独立性，可使用公式3来扩展公式2。

P(si+1|si，γ，β1...βB)＝∏_b＝1toB P(s|si，γ，βb)/(∑_q＝1toS∏_b＝1toB P(sq|si，γ，βb)(3)

为了估计P(s|si，γ，βb)的值，首先估计也称为残存概率的概率 P(si|si，γ，βb)。残存概率表示主体在下一时间计时单元处停留在同一转移状 态si中的概率。如公式4所示，使用具有均值μ和标准偏差σ的正态分布 来根据γ对持续时间值的给定观察分布进行建模。

P(si|si，γ，βb)＝1-∫_-∞toγN(μ.σ)dx    (4)

示例示出了该进程。出于说明的目的，假设主体在时间ti处于转移状 态s1。根据过去的数据，对于βj(例如TF1B1：上午)的时间特征值，已 知主体在5分钟的标准偏差(即σ＝5)下按照平均20分钟(即μ＝20) 转移到另一状态s2、s3等。如果主体已经在s1中停留达25分钟，则保持 在s1中的概率降低至16％，这也意味着变到另一转移状态的概率是84％。 已知残存概率，则前往其它转移状态的总概率P(s≠si|si，γ，βb)称为剩余概率 ＝1-残存概率。根据si的含义，有区别地计算转移至其它转移状态的概 率。在第一情况下，si表示从一个固定状态z1移动到不同的固定状态z2。 由于目的地是指定的，因此P(s≠si|si，γ，βb)表示到达z2的概率(即，s＝ (z2-z2))。在第二情况中，如果si表示停留在固定状态中，则P(s≠si|si，γ，βb) 表示变到其它转移状态的总概率，由公式5给出。

P(s≠si|si，γ，βb)＝∑_{q＝1toS，≠i} P(s＝sq |si，γ，βb)     (5)

如果已知si将转移到sq，则停留在si处的持续时间变为不相关的，从 而P(s＝sq|si，γ，βb))等于P(s＝sq|si，βb)，这可以通过对历史数据的多项式 分布拟和来进行建模。当新的观察量到达时，可以在数据库230(例如一 个或多个转移状态记录260)中保存分布的参数。

因而在进程600中，如图6A所示，在步骤601中确定最新近的固定 状态z。在步骤603中，确定P(z)是否大于最小支持(S-min)。如果不 是，则来自该固定状态的转移状态并不足够重要，并且该进程在不更新转 移状态的情况下结束。否则，按照计时单元时间(例如10分钟)来增加持 续时间γ。在步骤607，基于从移动检测器接收到的移动分类，确定移动终 端是否在移动。如果是的话，则将起始地状态(z1)设置成等于最后的固 定状态z。精确的转移状态是未知的，因为移动终端仍未到达目的地状态， 并且该进程结束。

如果在步骤607中确定移动终端不在移动，则在步骤611中，目的地 状态(z2)被认为是当前固定状态z并被设置成等于该值。在步骤613中， 确定起始地状态是否已被设置。如果不是，则z1为空，并且控制前进到步 骤615以便将当前转移状态si设置成自转移，其中起始地状态与目的地状 态z2相同(都等于z)。如果已经设置了起始地状态，则z1不为空，并且 在步骤617中，将转移状态si设置成是从状态z1转移到z2＝z。起始地状 态z1被设置成空。在任一情况中，控制前进到步骤619，以便在持续时间 γ、当前时间特征β的情况下更新转移状态si。在一些实施例中，重新开始 持续时间，例如将其设置为零；因而，自转移总是具有等于计时单元时间 的持续时间。在一些实施例中，自转移持续时间未被重置为零，直到移动 终端再次被归类为是移动的。

在步骤621中，确定在给定当前转移状态下的下一转移状态的概率 P(s|si)以便支持预测。然后进程结束，并且控制前进到图3的进程300的 步骤311。

在所述实施例中，步骤621包括步骤623至步骤631。在步骤623中， 确定对于时间特征β在转移状态si中的持续时间的均值μ和标准偏差σ， 例如从转移状态记录260中的字段267和字段268中提取。在步骤625中， 例如使用公式4，基于μ和σ来确定残存概率P(si|si)。在步骤627中，确 定当前状态si是否是其中z1＝z2的自转移状态。如果不是，则在步骤629 中，将返回到最新近的固定状态(非转移)的概率确定为剩余概率1- P(si|si)，并且该进程结束。

如果在步骤627中确定当前状态si是其中z1＝z2的自转移状态，则持 续时间无关紧要，并且控制前进到步骤631，以便基于转移状态变化的历 史分布来确定到达不同固定状态的可能的转移。例如，将多项式分布拟和 成基于在先状态的历史数据，并在每个转移状态记录260的字段270中进 行计数。使用该分布来在其它可能的转移状态sq(其中q≠i)当中分摊 (apportion)剩余概率1-P(si|si)，并且该进程结束。

图7A是根据一个实施例的为图3的进程300的步骤315预测下一转 移状态的进程700的流程图。给定预测时间窗口，其包括在当前计时单元 ti之后数目为x的时间计时单元，可将预测任务公式化为P(si+1... si+x|s0...si)，其表示过去的转移状态观察量s0...si和未来的观察量si+ 1...si+x。直接估计该概率分布是不可行的，因为用于存储联合分布的空间 会过于难以负担。在所述实施例中，进行一阶Markov链假设，从而使得 在时间计时单元ti+1处观察到转移状态si+1的概率仅有条件地依赖于在 ti处的转移状态si。然后可以简化并有效地实施预测任务，如公式6所示。

P(si+1...si+x|s0...si)＝∏j＝i to i+x P(sj+1|sj)     (6)

一阶Markov假设是合理的，因为在实际情况中，移动终端将要前往 的位置与当前位置高度相关，而与先前的位置关联较少。因为在步骤621 中已经描述了用于计算Pr(si+1|si)的高效进程，因此预测任务变得可 行。进程700中的预测任务被分为两个子任务。步骤701中的第一任务是 预测在当前时间ti处最可能的转移状态si。步骤703中的第二任务是对于 未来时间窗口x预测最可能的状态序列。

在步骤701，存在所考虑的两个可能的情况。在第一情况中，在预测 点ti处，移动检测模块224未检测到任何移动；而增量式状态学习模块226 指示固定状态之一zi。因此，转移状态表示自转移si＝(zi-zi)。在第二情 况中，移动检测模块224在查询时间ti处报告移动终端在移动，并且最终 固定目的地状态z2是未知的，因此si也是未知的。最后的自转移状态已 知为处于前一时间t0，并被表示为s0。在该情况下，预测从最后的自转移 状态开始。来自最后的固定状态的时间间隔被分离成时间计时单元的集合 (例如每个10分钟)。基于一阶Markov假设，在每个步骤中假设最可能 的转移，这是对熟知的Viterbi算法的实现，用于计算在查询时间ti处的 最可能的转移状态。Viterbi算法是用于计算Viterbi路径的动态编程算法， 其对应于具有最大概率的转移状态序列的序列。在查询时间ti，存在来自 最后的固定状态的m个时间计时单元。在时间ti处的最佳转移状态具有概 率：P＝max(P(sm))。在每个较早时间计时单元j处的状态可被定义为：P(sj ＝max(P(sj|sj-1))。对于开始状态s0，随后的那些被设置为：P(s0＝(z0-z0)) ＝1和P(s0≠(z0-z0))＝0，因为其从已知的固定状态z0中的自转移开始。 在图7A中，将当前时间ti简化为当前时间t；并且将si表示为St。

因而，在步骤705中，确定最新近的固定状态z0和相关联的时间t0。 在步骤707，确定移动检测器是否已将移动终端分类为在移动的。如果不 是，则si＝(z0-z0)，并且步骤701完成。

如果在步骤707确定移动检测器已将移动终端分类为在移动的，则在 步骤711，使用公式7来确定自从最后的固定状态以来的时间计时单元的 数目。

m＝(ti-t0)/tick                (7)

在步骤713，在每个时间计时单元(例如j＝1至m)，根据公式8来 确定最可能的转移状态。

P(sj)＝max(P(sk|sj-1，γ，β)for k＝1to S)(8)

其中max是返回在自变量中指示的一组值中的最大值的算子。对于持续时 间γ和时间特征β的给定转移状态sj-1，存在保持在同一转移状态的有限 概率以及改变到一个或多个不同转移状态中的每个转移状态的有限或零概 率。在公式8中将这些状态表示为sk，k＝1至S(转移状态的总数)。max 算子比较所有的这些概率(其中很多为零)，并且选择最可能的一个为sj。 在最后的时间步骤，计算最可能的当前转移状态si＝St，并且步骤701完 成。

在步骤703，返回通往未来的整个Viterbi路径，而不仅仅是在结束时 间tX处的转移状态。给定查询结束时间tX，再次从最后已知的固定状态 z0(或者当前转移状态si)将时间分割为离散数目(由数目X来表示)的 时间计时单元(例如10分钟)，并且输出具有最大概率的转移状态序列。 因而在步骤721，使用公式9来确定计时单元的数目X。

X＝(tX-t0)/tick          (9)

并且在步骤723中，在每个时间计时单元处(例如j＝1至X)，根据上面 的公式8来确定转移状态的最可能的序列。

图7B是根据一个实施例的在最可能的转移状态当中的Viterbi路径的 图形750。时间如时间轴752所示向右增加。特定时间由在离散时间t0 760、 时间t1 761、时间t2762和时间tX 763处的垂直线段来表示。在每个时间 处的转移状态的分布由节点来表示，例如在时间t0处的节点770、在时间 t1处的节点771a、771b、771c、在时间t2处的节点772a、772b、772c， 以及在时间tX处的节点773a、773b和773c，在下文将其统称为转移状态 节点777。从一个转移状态改变到另一转移状态的概率被呈现为：在将初 始转移状态连接到下一转移状态的实线箭头783或虚线箭头781旁边的数。 由实线箭头783来指示在每个时间步骤处的最可能的路径。每个转移状态 节点777在顶行中指示了固定起始地状态和固定目的地状态。每个转移状 态节点777还指示了处于该转移状态和最有可能变到该节点的前一转移状 态的概率。例如，根据转移状态记录260中的在先状态和计数字段270中 的数据，可以确定最有可能的前一转移状态。

图7B示出了时间范围查询。在该例中，存在X＝3个时间计时单元。 在该图中的每个节点表示转移状态sx，其被指示为一对固定状态。因此， 在查询时间计时单元的结尾处，得到最可能(48％)的转移状态(z2-z1)。 如果使用前一最佳节点由原路返回，则获得从时间t0到时间tX的最佳序 列为：{(z0)，(z0-z2)，(z2)，(z2-z1)}，其意味着移动终端被预测成向固定状态 z2转移，并且然后开始向固定状态z1转移。

这里估计了在图3至图7A中所示的进程表示的系统的复杂性。如在 下文更详细描述的实验中所确定的，复杂性是非常容易管理的，并且针对 大数目的用户进行了良好的调适。因而，合理数目的服务器和主机可以服 务于大数目的位置情境用户。

在存储复杂性方面，由于转移状态的集合S包括所有可能的固定状态 对，因此在|Z|²的量级上的空间(表示为O(|Z|²))是有用的。为了维护转 移状态，从所有转移状态直到所有的成对转移行为(P(sk|si，γ，βj))将是有用 的。其涉及O(|S|²)空间。如果存在B个时间特征值对，则整体存储要求由 O(B×|S|²)来约束。例如，如果存在10个固定状态，则可能存在100个可能 的转移状态和10,000个可能的成对转移。幸运的是，实际上许多转移状态 是不可能的(例如从“办公室”直接到“假期旅馆”)，这大大减少了成 对转移的数目。因此，可以高效地存储该模型。

关于计算复杂性，对于经过增量式状态学习模块222的每个传感器输 入v来说，移动检测模块224将O(|v|)时间用于相似性计算。在状态挖掘 进程期间，根据转移状态S及其中可能的成对改变来建立散列表。平均需 要O(log(B×|S|²))来更新模型。因此，对于每个输入来说，成本为O(|v|)+ O(log(B×|S²))。如果每个输入的大小是小的，则移动检测具有近似恒定的 成本。因此，处理n个流输入的成本为O(n log(B×|S|²))。对于大数目的输 入和小数目的转移状态，整体复杂性随输入数而言几乎是线性的。

预测模块的整体复杂性依赖于在两个时间计时单元之间涉及多少对转 移状态。在最差的情况中，其可以达到|S|2。因此最差情况的复杂性是 O(m|S|²)。在实际中，由于时间约束，并不是两个时间计时单元之间的所 有转移状态都是可能的，这在时间计时单元的数目X较小的情况下尤其如 此。因此，预计当预测时间窗口较小的时候(例如1小时)，预测进程非 常高效，而当预测时间窗口较大的时候(例如1天或1周)，预测进程不 那么高效。

实验：

在特定实施例情况下的大量实验显示：通过iLoc学习的位置-状态的 质量优于其它已知方法的质量。还证实：当其它方法的学习进程未能产生 合理预测时，iLoc仍提供了良好的预见。关于效率，iLoc仅传递数据一次， 而其它方法的学习进程需要多个迭代。实际上，iLoc不需要在移动设备上 缓存任何数据记录，其通过多个数据流处理模型进行了良好的拟和。

在实验中，使用Python来实现特定实施例。在这些实施例中报告的运 行时间是测量自具有Linux操作系统(OS)的P4-2GigaHerts(GHz，1GHz ＝109Hz，1Hz＝每秒1个周期)PC。为了比较，还实现了Latent Dirichlet Allocation(LDA)模型和隐式Markov模型(HMM)。通过利用来自Natick， Massachusetts的MATHWORKSTM的MATLABTM的多种统计工具而 生成LDA和HMM模型。

尽管LDA在文本挖掘域中表现出非常好的性能，但是当施加到位置 情境中时仍然存在几个问题。第一个问题是：LDA不考虑时间依赖性。每 个记录/文档都被假设是独立的或可互换的。因此，LDA不能直接用于预 测未来的位置状态。第二个问题是：LDA不具有表示用户停留的位置的固 定状态的语义概念。在LDA模型中，在移动时所遇到的WiFi源将出现在 开始的和最终的固定状态，这导致差的聚类(clustering)性能。而且，尤 其在判定群集的数目和估计参数时，难以递增式更新LDA模型。尽管还 可以应用其它基于非模型的聚类算法(诸如K-means或者分层合并聚类 (hierarchical agglomerative clustering，HAC))，但是已经显示它们不 如基于模型的方法精确；并且，这些基于非模型的方法也存在与LDA类 似的问题。

HMM也是生成式模型(generative model)，从而使得通过潜在状态 变量来生成每个观察量。在时间点处的潜在状态还依赖于其前一潜在状态。 可通过使用Baum-Welch算法来估计HMM中的参数，所述Baum-Welch 算法是广义期望最大化(GEM)算法。尽管建模状态转移是HMM的一部 分，但是这些状态在物理上并不对应于位置状态。这导致在预测未来移动 时的差的性能。对于HMM，观察序列在预测点处不可用。例如，仅给定 最初2个记录，所期望的是预测在两个位置状态之间的转移。在不提供未 来观察量的情况下，HMM很难预测转移。

实验使用GSM和WiFi传感器数据，因为这两种数据具有清楚的位置 感知，并且可以广泛地获得。通过在66天的时间段上连续监控3个用户而 获得实验数据。

通过使用用于S60的Python来实现用作位置情境客户端103的数据 收集客户端，并且该数据收集客户端在来自Espoo，Finland的NOKIA的 S60系列移动电话上运行。客户端周期性地上传数据到服务器。整体服务 也被称为NOKIA简单情境服务。图8A是根据一个实施例的在客户端进 程处的位置情境数据800的示图。在所述实施例中，图8A示出了在NOKIA 的N95移动电话上运行的客户端的屏幕捕获。客户端是高度可定制的，其 具有在相同时间监控多个传感器(GSM、WiFi、GPS、蓝牙等)的能力。

客户端的一个关注特征是自适应GPS，其使用相同的上述移动检测模 块来控制GPS感测。其在设备移动时可以智能地打开GPS，并在其它情 况下关闭GPS。尽管在实验所涉及的特定实施例中使用GPS数据来对WiFi 和GSM信号源进行地理标记，但可以预期的是，其它实施例进一步在增 量式状态学习模块226中利用GPS数据。

图8B是根据一个实施例的在服务器进程处的位置情境接口850的示 图。接口850在面板852、854、856和858中显示了用户的最后几个记录。 面板852显示了指示用户标识符(ID)和其它情境信息(诸如应用运行或 被发送的消息)的数据。面板854显示了指示WiFi和GSM发射机标识符 (ID)的列表的数据。面板856显示了基于最后的GPS位置的用户环境的 地图。面板858显示了指示移动终端上的计算机可读存储装置的分配的数 据。

一旦在服务器上存储了从客户端发送的数据，便可以使用各种API(例 如API 240)来检索/下载数据。尽管在实验中使用的实施例是构建在PC 上的，但是代码也可以按照实时模式在移动客户端上直接运行。使用标准 PC来相对于诸如LDA和HMM的现有技术方法或其它替换方法而使得性 能基准化。

在实验时间段期间，已经观察了数以千计的不同的WiFi接入点和 GSM蜂窝ID。图9A和图9B分别是根据各个实施例的用于GSM蜂窝和 WiFi接入点的发射机覆盖区的地图。基于一个用户的数据来对这些蜂窝进 行地理标记，并且在实验区域的地图图像901上绘制这些蜂窝。GSM信号 源位置903和WiFi信号源位置905覆盖了非常大的地理区域。应注意， 仅使用单独的信号源(例如单个GSM蜂窝ID)来表示固定状态是不够的。 这些信号源中的很多信号源并不对应于固定状态(例如，它们是在通勤期 间被发现的)；并且它们中的许多表示相同的固定状态(例如，在一次扫 描中的多个WiFi接入点)。

在表3中，概括了在2个月的时间段期间用于用户的数据集合。表3 为每个用户示出了记录的总数以及不同信号源(例如发射机ID)的数目。 注意到，与GSM相比，用于WiFi的记录的数目要少。这是因为相比于 GSM扫描，WiFi扫描的功耗更多，并且因此WiFi扫描相比GSM扫描而 言以较低的速率进行。对于这些用户，WiFi扫描速率被设置在2分钟与5 分钟之间，并且GSM扫描速率被设置在30秒与2分钟之间。注意在该章 节中，关注的是用户1的数据以便理解每个组件如何良好地工作。所有用 户的数据都被包括以便概括整体性能。

表3.实验数据设置(seta)

表4示出了iLoc所使用的缺省参数设置。对于不同的组件，所述参数 具有不同的敏感度。例如，相比于在增量式状态学习模块226的转移状态 部件中使用的参数，在增量式状态学习模块226的固定状态部件以及移动 检测模块中的门限设置不那么敏感。因此，在该章节的后面部分中，评估 了在改变参数值时的性能含义。

表4.缺省参数设置

图10A是根据一个实施例的针对用户1的移动终端的移动时间段与非 移动时间段的比值的图形1000。水平轴1002是以天计的时间。垂直轴1004 是在那天移动终端处于移动的时间除以移动终端处于固定的时间的比值。 迹线1010示出了基于WiFi数据流的对移动的检测；而迹线1020示出了 基于GSM数据流的对移动的检测。针对用户1的日常移动比值示出了移 动检测模块224的有效性。可见，移动并不仅限于周末，而是也包括工作 日。用户1确认：移动检测模块224可以正确地捕获大的移动，尤其对于 到达不同位置的通勤。在表5中，对所有的用户计算了每天的平均移动比 值。注意到，相比于GSM数据流，WiFi数据流可以捕获更多的移动。这 是因为WiFi接入点通常具有比GSM蜂窝要小的空间覆盖，并且因此该数 据对于移动更加敏感。然而，该差别不是很大，这表明GSM蜂窝也可用 于移动检测。

表5.每天的移动比值

  数据流类型   用户1   用户2   用户3   GSM   9.2％   16.2％   10.1％   WiFi   12.4％   24.9％   14.2％

图10B是根据一个实施例的在时间上增量式积累的移动终端的固定状 态的数目的图形1050。如图10A中那样，水平轴1002是以天计的时间。 垂直轴1054是固定状态的数目Z。迹线1060示出了用户1的基于WiFi 数据流的固定状态的增长；而迹线1070示出了用户1的基于GSM数据流 的固定状态的增长。图形1050清楚地说明：增量式状态学习模块226的固 定状态更新进程在数据到达时可以递增地发现新的固定状态。注意到， WiFi固定状态的数目大于GSM固定状态的数目。这也是预期的，因为现 在许多场所具有免费的WiFi接入，但是这些接入点中的许多接入点可能 处在同一GSM蜂窝下。在表6中，概括了由全部3个用户发现的固定状 态的总数。

表6.固定状态的总数

  数据流类型   用户1   用户2   用户3   GSM   46   95   58   WiFi   86   109   83

图11A和图11B分别是根据一些实施例的用于GSM蜂窝和WiFi接 入点的在时间上增量式积累的移动终端的最频繁固定状态的累积分布函数 的图形1100和1150。水平轴1102是以天计的时间。垂直轴1104是总观 察量(其可归属于(attributable to)给定固定状态的总和)与所有较频繁 状态的分数。在针对用户1GSM数据流的图形1100中，迹线1111示出了 归属于第一状态的观察量的分数，迹线1112针对第一和第二最频繁的固定 状态，迹线1113针对第一到第三最频繁的固定状态，迹线1114针对第一 到第四最频繁的固定状态，迹线1115针对第一到第五最频繁的固定状态， 以及迹线1116针对第一到第六最频繁的固定状态。迹线之间的差别给出了 可归属于附加固定状态的分数。在针对用户1WiFi数据流的图形1150中， 迹线1151示出了归属于第一状态的观察量的分数，迹线1152针对第一和 第二最频繁的固定状态，迹线1153针对第一到第三最频繁的固定状态，迹 线1154针对第一到第四最频繁的固定状态，以及迹线1155针对第一到第 五最频繁的固定状态。这些图形示出了固定状态如何按照出现频率来分布。 GSM和WiFi图形分别示出了一致地具有超过50％的概率的大的固定状 态。在人工地检查了这些状态之后，该状态清楚地对应于“家里”状态。 WiFi的前5位和GSM的前6位一致地占用了每天95％以上的时间。这些 状态清楚地对应于“办公室”以及其它频繁访问的场所。

HMM和LDA学习器不是增量式学习器。为了对这些备选方法提供有 利的比较，以完整两个月的数据来训练HMM和LDA，即使这些结果可能 不可用于66天。另一个困难的问题是如何判定用于HMM和LDA方法的 群集的数目。存在在文献中提出的不同启发方法。这里，通过使用来自iLoc 的结果来提供非常好的估计。HMM和LDA的群集的数目是基于覆盖了用 户95％的固定时间的前几位固定状态(top stationary states)。假设：如 果HMM或者LDA优胜于iLoc，则优胜模型应当发现固定状态的相似集 合。表7示出了来自iLoc的对不同用户的95％的固定时间进行了说明 (account for)的群集的数目。另外，为了有效地应用HMM和LDA，还 确定了迭代的数目。对于HMM，迭代的最大数目被设置成100。对于LDA， 使用了用于训练LDA模型的Gibbs采样器方法。用于Gibbs采样器的迭 代的数目被设置成500。

表7.对95％的固定时间进行了说明的固定状态的数目。

  数据流类型   用户1   用户2   用户3   GSM   6   23   10   WiFi   5   24   12

图12A和图12B分别是根据一些实施例的用于GSM蜂窝和WiFi接 入点的相比于其它方法的用于构建转移状态的概率模型的时间的图形 1200和1250。水平轴1202指示了用于用户和建模方法的bin。垂直轴1204 和1254指示了单位为秒的时间。在图形1200中示出了用于GSM数据流 的模型构建时间，对于HMM方法，针对三个用户中的每个用户，将模型 构建时间示为条1210a、1210b和1210c，在下文中将其统称为条1210；对 于LDA方法，将模型构建时间示为条1220a、1220b和1220c，在下文中 将其统称为条1220；对于iLoc实施例，将模型构建时间示为条1230a、1230b 和1230c，在下文中将其统称为条1230。在图形1250中示出了用于WiFi 数据流的模型构建时间，对于HMM方法，针对三个用户中的每个用户， 将模型构建时间示为条1260a、1260b和1260c，在下文中将其统称为条 1260；对于LDA方法，将模型构建时间示为条1270a、1270b和1270c， 在下文中将其统称为条1270；对于iLoc实施例，将模型构建时间示为条 1280a、1280b和1280c，在下文中将其统称为条1280。即使仅通过100个 迭代，HMM也花费最长的时间(条1210和1260)来进行训练。这还示 出：iLoc(条1230和1280)比具有Gibbs采样的LDA(条1220和1270) 快大约2倍到10倍。性能增益主要是因为iLoc是一次通过算法，而其它 算法要求在数据上进行多次迭代。

另外对来自不同方法的群集的质量进行了检查。对于用户1，在表8 中将前5位群集(WiFi数据流)与来自HMM和LDA的群集进行比较， 表8示出了来自每个学习方法的前3位WiFi接入点ID。对于该用户，这 些接入点ID可以容易地与一些语义含义相关联。在表9中，用户基于前 10位WiFi ID来标记这些群集。对于iLoc，用户能够表示和区分若干关注 的场所，包括家、办公室以及朋友的家。另外，iLoc对用户的日常午餐和 健身房位置附近的WiFi接入点ID进行正确的聚类。表9还示出了每个群 集的先验概率(支持)，其表示每个群集的重要性程度。用户对于与固定 状态相关联的iLoc群集表示同意。然而，HMM和LDA不能清楚地分开 这些固定状态。例如，WiFi ID“家(Home)”出现在了几个群集中。如 果这些HMM和LDA群集被选择为固定状态，则转移模型受到严重的影 响，导致差的预测性能。对于其他两个用户也观察到类似的聚类行为。

表8.通过各种方法的用于固定状态的前3位WiFi ID(SSID)。

表9.通过各种方法的用于固定状态的位置情境。

为了完全测试出转移模型和预测框架，自动形成预测查询的连续集合。 在该设置中，顺序地重播来自数据流的输入。在每个采样点，调用移动检 测进程，并形成两种类型的查询。第一种查询被称为非移动查询(并被标 记为Qt1)，从而使得如果用户不在移动，则进行具有60分钟时间范围的 查询。预测模块每10分钟输出最可能的转移状态，直到用户开始再次移动 或者60分钟的预测窗口已经过去。通过比较所预测的转移状态s与固定状 态z0，在每个时间计时单元处计算出精度。如果s表示自转移s＝(z0-z0)， 则认为预测是正确的。第二种查询被称为移动查询(并被标记为Qt2)， 从而使得如果用户从最新近的固定状态z0开始而在移动，则形成一时间范 围，其持续到用户到达另一固定状态z1。在该时间范围期间，每10分钟 对s进行预测。通过比较所预测的转移状态s与在两个固定状态之间的正 确转移z0-z1，在每个时间计时单元处测量精度。表10示出了用于这两 种查询的查询负载。

表10.在实验期间的预测请求(查询)负载。

这两种查询类型涵盖了很多使用情况。非移动查询基本上提问用户将 在相同的固定状态中停留多长时间，而移动查询提问用户是否将要转移以 及去往那个固定状态。如果iLoc能够对两种查询一致地提供精确的预测， 则其可以用于多个实际生活应用(例如Ad-服务)。尽管所述实施例是完 全增量式模型，但是统计量是在若干天上聚集的以便提供(populate)后 验概率。在正好两个月的数据上连续实施预测。对于所述预测，如果预测 器拒绝进行预测，则认为预测器没有足够的信息来进行预测，并且其不是 查询负载的一部分。这是合理的，因为目标是具有非常精确的预测而不是 非常宽泛的预测。为了获得对预测进程的一些理解，检查对用户1的日常 预测。如果不存在对一天所进行的预测，则认为其是正确的选择(即，对 于该天100％正确)。

图13A至图13D分别是根据一些实施例的用于GSM蜂窝和WiFi接 入点的针对移动和非移动转移状态的预测精度的图形1300、1320、1340 和1360。水平轴1302是以天计的时间。垂直轴1304指示了在每计时单元 10分钟的三个不同时间范围(1个计时单元(10分钟)、3个计时单元(30 分钟)和6个计时单元(60分钟))上对于每天的正确预测率(1＝100％ 正确预测)。基于GSM数据流，针对用户1的Qt1查询，图形1300将计 时单元1预测示为迹线1310a、将计时单元2预测示为迹线1310b，以及将 计时单元6预测示为迹线1310c。基于WiFi数据流，针对用户1的Qt1查 询，图形1320将计时单元1预测示为迹线1330a、将计时单元2预测示为 迹线1330b，以及将计时单元6预测示为迹线1330c。基于GSM数据流， 针对用户1的Qt2查询，图形1340将计时单元1预测示为迹线1350a、将 计时单元2预测示为迹线1350b，以及将计时单元6预测示为迹线1350c。 基于WiFi数据流，针对用户1的Qt2查询，图形1360将计时单元1预测 示为迹线1370a、将计时单元2预测示为迹线1370b，以及将计时单元6 预测示为迹线1370c。

基于GSM数据流的预测没有基于WiFi数据流的预测好。主要的原因 是：GSM蜂窝覆盖较大的空间区域。Qt1预测主要测试了用于不同固定状 态的自转移。来自GSM数据流的固定状态有时会混杂不同的固定状态(如 果它们在附近的话)。从而，用于GSM的自转移模型没有用于WiFi的好。 然而，即使对于GSM，iLoc仍然能够获得62％的整体精度。对于WiFi 数据流，iLoc表现非常好，并且获得73％的整体精度。

在一些天中，图形1340和1360中示出的对于Qt2查询的预测精度不 是非常好(例如接近0)。在咨询了用户之后，得出这些天大部分是周末 和假期。由于不规则的移动，预测这些天是有挑战性的。然而，能够将这 些天与正常的工作日区分开来可以改善对这些天的预测精度。GSM预测再 次比WiFi预测要差。因此，对于增量式状态学习模块固定状态更新进程 有用的是：精确地发现固定状态。

与下一组实验中的HMM和LDA相比，更明显的是：iLoc具有更好 的性能。整体上，基于WiFi数据流的iLoc预测能够获得84％的预测精度， 而GSM流获得25％的预测精度。基于GSM和基于WiFi的预测模块均在 达到一小时的查询时间范围内进行合理的预测。这对于很多应用情况是足 够的，在所述应用情况中，预测下一小时的用户行为对于满足用户的信息 需求来说极为有用。

表11示出了在不同的方法下和不同的参数设置下对于所有用户的整 体精度测量。第一行示出了具有缺省参数(来自表4)的iLoc的精度。表 11易于比较不同方法和不同参数设置的性能。表11具有三个部分。在第 一部分，将iLoc的性能与HMM和LDA相比。HMM和LDA都示出了 不适于该预测任务的低精度。LDA仅提供了可用作固定状态的群集信息。 HMM需要观察量以便推断隐藏状态，而在查询时间实例中，未来的观察 量还不可用。尽管HMM提供了针对不同状态的转移概率分布，然而这些 转移大部分针对自转移。Viterbi算法总是会以相同的状态结束。为说明这 点，表12示出了来自HMM模型的转移矩阵。根据矩阵本身，可以观察 到除了自转移之外的一些转移。例如，状态1能够以63％的概率转移到状 态3。然而，给定表9中所示出的状态的语义含义，它们本质上是相同的 状态。对于其它转移也可以得出类似的结论。因此，为了具有公平的比较， 仅包括来自LDA和HMM的群集/固定状态。如从结果可以观察到的，尤 其是对于查询类型Qt2，存在对于HMM和LDA的一些预测。然而，精 度仍然远落后于具有缺省参数的iLoc(iLoc-default)。这也可以从在方法 名称下列出的对应方法的平均精度观察到。对于这组实验，由于整组数据 被用于训练HMM和LDA，因此用于HMM和LDA的任何增量式学习方 法都不能优胜于对iLoc示出的结果。此外，由于能够容易地插入不同的群 集方法，iLoc是更为灵活和开放的。

表11.用于不同方法和设置的预测精度。

表12.基于WiFi数据流的HMM状态转移矩阵

  状态1   状态2   状态3   状态4   状态5   状态1   37％   0％   63％   0％   0％   状态2   0％   99％   0.90％   0.10％   0％   状态3   82％   10％   1％   7％   0％   状态4   0％   0.50％   0.50％   36％   63％   状态5   0％   0％   0％   56％   44％

表11的第二部分示出了当最小支持参数值变化时iLoc的精度。测试 了四个设置(0％、1％缺省、2％和5％)，其被标记为iLoc-0、iLoc-default、 iLoc-2以及iLoc-5。最小支持越高，在转移状态中考虑越少的固定状态， 并且通常预测精度越大。用于较大精度的代价是不能预测一些不频繁的移 动。

图14A和图14B是根据一些实施例的针对用于固定状态的出现概率的 不同最小门限(被称为最小支持)所进行的预测数目的图形1400和1450。 水平轴1402是最小支持百分数(％)。垂直轴1402是允许的Qt1查询的 数目；以及垂直轴1454是允许的Qt2查询的数目。基于GSM数据流，图 形1400将Qt1查询对于用户1示为迹线1410a、对于用户2示为迹线1410b， 以及对于用户3示为迹线1410c。基于WiFi数据流，图形1400同样将Qt1 查询对于用户1示为迹线1420a、对于用户2示为迹线1420b，以及对于用 户3示为迹线1420c。基于GSM数据流，图形1450将Qt2询问对于用户 1示为迹线1460a、对于用户2示为迹线1460b，以及对于用户3示为迹线 1460c。基于WiFi数据流，图形1450同样将Qt2查询对于用户1示为迹 线1470a、对于用户2示为迹线1470b，以及对于用户3示为迹线1470c。

如图14A和图14B所示，随着最小支持增加，可被答复的查询的数目 单调地减小。在0％的最小支持处，iLoc可以针对Qt1和Qt2这二者答复 最大数目的查询；然而却具有最差的精度。对于Qt1，在1％的最小支持 的情况下，iLoc仍然能够以好的精度增益来答复大部分查询。对于Qt2， 在1％的最小支持处，下降的查询数目对于一些设置可能是大的。然而， 精度增益是显著的。当最小支持保持增加时(例如，iLoc-2和iLoc-5)， 下降的查询数目也增加。精度增益仅是适中的(6％至9％的整体改善)。 因此，为了达到适当的平衡，选择1％的最小支持值作为缺省值。

表11的第三部分示出了时间特征的效果。iLoc-none实施例不使用时 间特征。iLoc-none对于Qt2查询表现较差。这是预期的，因为iLoc-none 并不区分在不同时间情境中的移动。当添加上午、下午和夜晚时间特征时 (被标记为iLoc-man)，性能显著改善。在全特征集合(被标记为 iLoc-default)情况下进一步增强了性能。

图15是根据一些实施例的用于GSM蜂窝和WiFi接入点的对移动和 非移动的移动终端进行预测的平均执行时间的图形1500。水平轴1502指 示了用于查询和信号数据流的bin。垂直轴1504指示了单位为秒的执行时 间。条1510指示了基于GSM数据流的用于Qt1查询的执行时间。条1520 指示了基于GSM数据流的用于Qt2查询的执行时间。条1530指示了基于 WiFi数据流的用于Qt1查询的执行时间。条1540指示了基于WiFi数据 流的用于Qt2查询的执行时间。大部分查询在5毫秒内完成。通过该速度， iLoc可以很好地调适作为用于数以千计的用户的Web服务。

iLoc框架是开放框架。所述实施例良好地工作于移动信号环境。在其 它实施例中，合并了更多的传感器输入，诸如加速计传感器数据，以便区 分更细粒度的移动。在一些实施例中，合并了信号强度来帮助标识较小的 固定状态。

iLoc学习框架捕获空间和时间维度，并且能够以全自动和增量式的方 式来精确预测用户的未来位置。基于iLoc的推荐系统可以基于所预测的位 置信息来精确地推送相关信息。例如，当用户将要转移到另一固定状态(例 如从办公室到家里)时，系统可以自动取得相关的交通信息并准备路由信 息，而不需要来自用户的任何命令。可选地，系统可以智能地推送与不同 固定状态相关的广告(例如当用户将要去吃午餐时推送午餐优惠券)。为 了对数百万的用户产生价值，系统应该能够随着所接收到的信息量而进行 线性的调适。已经示出，iLoc由于其增量式信号数据流处理模块而能够满 足该要求。已通过经验而示出了构建和存储不同用户状态的效率。

硬件描述：

这里所述的用于增量式确定位置情境的进程可以有利地通过以下内容 来实现：软件、硬件(例如，通用处理器、数字信号处理(DSP)芯片、 专用集成电路(ASIC)、现场可编程门阵列(FPGA)等)、固件或其组 合。下面详细描述实施所述功能的这种示例硬件。

图16图示了在其上可以实现本发明的实施例的计算机系统1600。尽 管针对特定设备或装置描绘了计算机系统1600，然而可以想到，图16内 的其它设备或装置(例如网络元件、服务器等)可以部署所说明的系统1600 的硬件和组件。计算机系统1600被编程(例如通过计算机程序代码或指令) 以便如本文所述那样增量式确定位置情境，并且计算机系统1600包括用于 在计算机系统1600的其它内部和外部组件之间递送信息的通信机构，诸如 总线1610。信息(也称为数据)被表示为可测量的现象的物理表达，通常 是电压，但在其它实施例中也包括诸如磁、电磁、压力、化学、生物、分 子、原子、亚原子和量子交互这样的现象。例如，北极和南极磁场或者零 和非零电压表示二进制数位(比特)的两个状态(0，1)。其它现象可以 表示更高基底的数位。测量之前的多个同时的量子状态的叠合 (superposition)表示量子比特(qubit)。一个或多个数位的序列构成了 用于表示字符的数目或代码的数字数据。在一些实施例中，被称为模拟数 据的信息通过特定范围内的可测量值的近连续体来表示。计算机系统1600 或其一部分构成了用于实施增量式确定位置情境的一个或多个步骤的装 置。

总线1610包括一个或多个并行的信息导体，从而使得在耦合于总线 1610的设备之间快速地传递信息。用于处理信息的一个或多个处理器1602 与总线1610相耦合。

处理器1602按照与增量式确定位置情境相关的计算机程序代码所指 定的来对信息执行操作集合。计算机程序代码是为处理器和/或计算机系统 的操作提供指令来实施指定功能的一组指令或声明。例如，可以按照被编 译到处理器的本地指令集的计算机编程语言来书写代码。还可以直接使用 本地指令集(例如机器语言)来书写代码。操作集合包括：从总线1610 带入信息以及将信息置于总线1610上。操作集合通常还包括：比较两个或 更多信息单元，将信息单元的位置移位，以及诸如通过相加或相乘或者逻 辑运算(比如或(OR)、异或(XOR)和与(AND))来组合两个或更多 信息单元。可以由处理器实施的操作集合中的每个操作由被称为指令的信 息(诸如一个或多个数位的操作代码)来表示给处理器。要由处理器1602 执行的操作序列(诸如操作代码序列)构成了处理器指令，也被称为计算 机系统指令或简单地称为计算机指令。处理器可以单独地或组合地被实现 为机械、电、磁、光、化学或量子组件等。

计算机系统1600还包括耦合到总线1610的存储器1604。诸如随机访 问存储器(RAM)或其它动态存储设备的存储器1604存储了信息，包括 用于增量式确定位置情境的处理器指令。动态存储器允许计算机系统1600 改变存储在其中的信息。RAM允许独立于在相邻地址处的信息而存储和 检索被存储在称为存储器地址的位置处的信息单元。存储器1604还被处理 器1602用于存储在处理器指令的执行期间的临时值。计算机系统1600还 包括只读存储器(ROM)1606或耦合到总线1610的其它静态存储设备， 用于存储计算机系统1600不会改变的静态信息(包括指令)。某个存储器 包括易失性储存器，当断电时，易失性储存器会丢失在其上存储的信息。 也耦合到总线1610的是非易失性(永久)存储设备1608，诸如磁盘、光 盘或闪卡，用于存储包括指令的信息，非易失性(持久)存储设备1608 即使当计算机系统1600关闭或以其它方式断电时也进行留存。

将包括用于增量式确定位置情境的指令的信息从外部输入设备1612 (诸如含有由人类用户操作的字母数字键的键盘)或传感器提供给总线 1610，用于由处理器使用。传感器检测其附近的状况，并且将那些检测结 果转换成与用于表示计算机系统1600中的信息的可测量现象相兼容的物 理表达。耦合到总线1610的主要用于与人类交互的其它外部设备包括显示 设备1614，诸如阴极射线管(CRT)或液晶显示器(LCD)，或者用于呈 现文本或图像的等离子屏幕或打印机，以及指点设备1616，诸如鼠标或轨 迹球或光标方向键，或者运动传感器，用于控制在显示器1614上呈现的小 光标图像的位置以及发布与在显示器1614上呈现的图形元素相关联的命 令。在一些实施例中，例如，在计算机系统1600自动地执行所有功能而无 需人类输入的实施例中，省略了外部输入设备1612、显示设备1614和指 点设备1616中的一个或多个。

在所图示的实施例中，诸如专用集成电路(ASIC)1620的专用硬件 耦合到总线1610。专用硬件被配置以便为专用目的足够快地执行处理器 1602不执行的操作。专用IC的例子包括：用于为显示器1614生成图像的 图形加速器卡、用于加密和解密在网络上发送的消息的密码板、语音识别， 以及针对专门外部设备的接口，诸如重复地执行一些在硬件中更为有效实 现的复杂操作序列的机器臂和机械扫描设备。

计算机系统1600还包括耦合到总线1610的通信接口1670的一个或多 个实例。通信接口1670提供了耦合到与其自己的处理器一起操作的各种外 部设备(诸如打印机、扫描仪和外部盘)的单向或双向通信。通常，耦合 是针对网络链路1678，网络链路1678被连接到本地网络1680，具有其自 己的处理器的各种外部设备被连接到本地网络1680。例如，通信接口1670 可以是个人计算机上的并行端口或串行端口或通用串行总线(USB)端口。 在一些实施例中，通信接口1670是综合服务数字网络(ISDN)卡或数字 订户线路(DSL)卡或向相应类型的电话线路提供信息通信连接的电话调 制解调器。在一些实施例中，通信接口1670是电缆调制解调器，其将总线 1610上的信号转换成用于在同轴电缆上的通信连接的信号，或者转换成用 于在光纤线缆上的通信连接的光信号。又例如，通信接口1670可以是局域 网(LAN)卡，用于提供针对兼容的LAN(诸如以太网)的数据通信连接。 还可以实现无线链路。对于无线链路，通信接口1670发送或接收或者既发 送又接收携带了信息流(诸如数字数据)的电、声或电磁信号，包括红外 信号和光信号。例如，在无线手持设备(诸如像蜂窝电话这样的移动电话) 中，通信接口1670包括被称为无线电收发器的无线电频带电磁发射机和接 收机。在特定实施例中，通信接口1670启用与通信网络105的连接以便获 得来自UE 101的信号数据流。

术语“计算机可读介质”在此用于指代参与向处理器1602提供信息(包 括用于执行的指令)的任何介质。这样的介质可以采用很多形式，包括但 不限于非易失性介质、易失性介质和传输介质。非易失性介质包括例如光 盘或磁盘，诸如存储设备1608。易失性介质包括例如动态存储器1604。传 输介质包括例如同轴电缆、铜导线、光纤线缆以及在没有导线或电缆的情 况下通过空间行进的载波，诸如声波和电磁波，包括无线电波、光波和红 外波。信号包括通过传输介质而被传送的在幅度、频率、相位、极化或其 它物理属性方面的人为瞬时变化。计算机可读介质的常见形式包括例如： 软盘、柔性盘、硬盘、磁带或任何其它磁介质、CD-ROM、CDRW、DVD、 任何其它光介质、穿孔卡、纸带、光标记单或者具有孔图案或其它光可识 别的标记的任何其它物理介质、RAM、PROM、EPROM、FLASH-EPROM 或任何其它存储器芯片或卡式盒、载波或者计算机可以从其进行读取的任 何其它介质。这里使用术语“计算机可读存储介质”来指代除了传输介质 之外的任何计算机可读介质。

在一个或多个有形介质中编码的逻辑包括以下之一或两者：在计算机 可读存储介质和在诸如ASIC 1620的专用硬件上的处理器指令。

网络链路1678通常使用传输介质通过一个或多个网络向使用或处理 信息的其它设备提供信息通信。例如，网络链路1678可以通过本地网络 1680向主机计算机1682或向由因特网服务提供商(ISP)运营的设备1684 提供连接。ISP设备1684进而通过现在常被称为因特网1690的网络的公 共全球分组交换通信网络来提供数据通信服务。

连接到因特网的被称为服务器主机1692的计算机托管了以下处理：响 应于在因特网上接收到的信息而提供服务。例如，服务器主机1692托管了 以下处理：提供表示用于在显示器1614处呈现的视频数据的信息。可以想 到，可在其它计算机系统(例如主机1682和服务器1692)内的各种配置 中部署系统1600的组件。

本发明的至少一些实施例涉及使用计算机系统1600来实现在此描述 的一些或所有技术。根据本发明的一个实施例，响应于处理器1602执行在 存储器1604中所含的一个或多个处理器指令的一个或多个序列，由计算机 系统1600来实现那些技术。这样的指令(也被称为计算机指令、软件和程 序代码)可以从诸如存储设备1608或网络链路1678的另一计算机可读介 质被读入到存储器1604中。对存储器1604中所含的指令序列的执行使得 处理器1602实施在此描述的一个或多个方法步骤。在替代实施例中，可以 取代用于实现本发明的软件或与其组合地来使用诸如ASIC 1620的硬件。 因而，本发明的实施例不限于硬件和软件的任何特定组合，除非在此另外 明确声明。

通过通信接口1670在网络链路1678和其它网络上传送的信号携带了 去往和来自计算机系统1600的信息。计算机系统1600可以经由网络链路 1678和通信接口1670，通过网络1680、1690等来发送和接收信息，包括 程序代码。在使用因特网1690的例子中，服务器主机1692通过因特网 1690、ISP设备1684、本地网络1680和通信接口1670来传送由从计算机 1600发送的消息所请求的用于特定应用的程序代码。所接收到的代码可以 在其被接收到时由处理器1602来执行，或者可以存储在存储器1604中或 存储在存储设备1608或其它非易失性储存器中用于以后执行，或者二者兼 有。如此，计算机系统1600可以在载波上获得信号形式的应用程序代码。

在将一个或多个指令序列或数据或者这二者携带到处理器1602用于 执行时，可以涉及各种形式的计算机可读介质。例如，初始地，可以在诸 如主机1682的远程计算机的磁盘上携带指令和数据。远程计算机将指令和 数据加载到其动态存储器中，并且使用调制解调器在电话线路上发送指令 和数据。计算机系统1600的本地调制解调器在电话线路上接收指令和数 据，并且使用红外发射机来将指令和数据转换成在用作网络链路1678的红 外载波上的信号。充当通信接口1670的红外检测器接收在红外信号中携带 的指令和数据，并且将表示该指令和数据的信息放置到总线1610上。总线 1610将信息携带到存储器1604，处理器1602对存储器1604进行检索，并 使用随指令一起发送的一些数据来执行指令。可选地，在存储器1604中接 收到的指令和数据可以在处理器1602进行执行之前或之后被存储在存储 设备1608上。

图17图示了可以在其上实现本发明的实施例的芯片集1700。芯片集 1700被编程以便如在此所描述的那样增量式确定位置情境，并且包括例如 相对于图16所描述的被合并在一个或多个物理封装(例如芯片)中的处理 器和存储器组件。举例来说，物理封装包括在结构配件(例如，基板)上 的一个或多个材料、组件和/或导线的布置，以便提供一个或多个特性，诸 如物理强度、尺寸的保持和/或电交互的限制。可以想到，在特定实施例中， 可以在单个芯片上实现芯片集。芯片集1700或其一部分构成了用于实施增 量式确定位置情境的一个或多个步骤的装置。

在一个实施例中，芯片集1700包括通信机构，诸如用于在芯片集1700 的组件当中递送信息的总线1701。处理器1703具有到总线1701的连接， 以便执行指令并处理在例如存储器1705中存储的信息。处理器1703可以 包括一个或多个处理核心，每个核心被配置成独立地实施。多核处理器使 得能够在单个物理封装中进行多处理。多核处理器的例子包括两个、四个、 八个或更多数目的处理核心。替代地或附加地，处理器1703可以包括经由 总线1701联合配置的一个或多个微处理器，以便使得能够独立执行指令、 流水线操作和多线程。处理器1703还可以附有一个或多个专用组件以便执 行特定处理功能和任务，诸如一个或多个数字信号处理器(DSP)1707， 或者一个或多个专用集成电路(ASIC)1709。DSP 1707通常被配置成独 立于处理器1703而实时地处理真实信号(例如，声音)。类似地，ASIC 1709 可以被配置以便实现通用处理器不容易实现的专用功能。在此描述的有助 于实现本发明功能的其它专用组件包括：一个或多个现场可编程门阵列 (FPGA)(未示出)、一个或多个控制器(未示出)，或者一个或多个其它 专用计算机芯片。

处理器1703和所附组件具有经由总线1701而到存储器1705的连接。 存储器1705包括动态存储器(例如，RAM、磁盘、可写光盘等)和静态 存储器(例如，ROM、CD-ROM等)这二者，用于存储可执行指令，当 执行所述可执行指令时，实现在此描述的本发明步骤，以便增量式确定位 置情境。存储器1705还存储与本发明步骤的执行相关联的数据或通过本发 明步骤的执行而生成的数据。

图18是根据一个实施例的能够在图1的系统中操作的用于通信的移动 终端(例如，手机)的示例组件的示图。在一些实施例中，移动终端1800 或其一部分构成了用于实施增量式确定位置情境的一个或多个步骤的装 置。一般而言，常常关于前端和后端特性来定义无线电接收机。接收机的 前端包括所有的射频(RF)电路，而后端包括所有的基带处理电路。如在 本申请中所使用的，术语“电路”指代以下二者：(1)仅硬件实现(诸如 仅在模拟和/或数字电路中的实现)，以及(2)电路与软件(和/或固件) 的组合(诸如一个或多个处理器(包括数字信号处理器)、软件以及一个 或多个存储器的组合，它们一起工作使得诸如移动电话或服务器这样的装 置实施各种功能)。“电路”的该定义应用于本申请(包括任何权利要求) 中对该术语的所有使用。作为另一示例，如在本申请中所使用的，术语“电 路”还将涵盖仅一个处理器(或多个处理器)与其附带软件/或固件的实现。 术语“电路”还将涵盖例如在移动电话中的基带集成电路或应用处理器集 成电路，或者在蜂窝网络设备或其它网络设备中的类似集成电路。

电话的相关内部组件包括主控制单元(MCU)1803、数字信号处理器 (DSP)1805，以及包括扩音器增益控制单元和扬声器增益控制单元在内 的接收机/发射机单元。主显示单元1807向用户提供支持各种应用和移动 终端功能的显示，这些功能实施或支持增量式确定位置情境的步骤。显示 单元1807包括显示器电路，其被配置以便显示移动终端(例如移动电话) 的用户接口的至少一部分。另外，显示单元1807和显示器电路被配置以便 促进对移动终端的至少一些功能的用户控制。音频功能电路1809包括扩音 器1811和扩音器放大器，扩音器放大器放大了从扩音器1811输出的语音 信号。从扩音器1811输出的经放大的语音信号被馈送到编码器/解码器(编 解码器)1813。

无线电部件1815放大功率并转换频率，以便经由天线1817与包括在 移动通信系统中的基站进行通信。如本领域中已知的，功率放大器(PA) 1819和发射机/调制电路在操作上利用来自PA 1819(其被耦合到双工器 1821或循环器或天线开关)的输出来对MCU 1803进行响应。PA 1819还 耦合到电池接口和功率控制单元1820。

在使用中，移动终端1801的用户向扩音器1811讲话，并且他或她的 话音连同任何所检测到的背景噪声被转换成模拟电压。然后，该模拟电压 通过模数转换器(ADC)1823被转换成数字信号。控制单元1803将数字 信号路由到DSP 1805中用于在其中进行处理，诸如语音编码、信道编码、 加密和交织。在一个实施例中，使用蜂窝传输协议(诸如全球演进(EDGE)、 通用分组无线电服务(GPRS)、全球移动通信系统(GSM)、因特网协 议多媒体子系统(IMS)、通用移动电信网络(UMTS)等)以及任何其 它合适的无线介质(例如，微波接入(WiMAX)、长期演进(LTE)网 络、码分多址(CDMA)、宽带码分多址(WCDMA)、无线保真(WiFi)、 卫星等)，通过未单独示出的单元来对经处理的语音信号进行编码。

然后，编码信号被路由到均衡器1825，用于补偿在通过空气传输期间 发生的诸如相位和幅度失真这样的任何频率相关的损伤。在均衡了比特流 之后，调制器1827将该信号与在RF接口1829中生成的RF信号进行组 合。调制器1827通过频率或相位调制来生成正弦波。为了准备用于传输的 信号，上变频器1831将从调制器1827输出的正弦波与由合成器1833生成 的另一正弦波进行组合，以便获得所期望的传输频率。然后，通过PA 1819 来发送该信号，以便将信号增加到适合的功率水平。在实际系统中，PA 1819 充当可变增益放大器，其增益根据从网络基站接收到的信息而受到DSP 1805的控制。然后，该信号在双工器1821中被过滤，并且可选地被发送 到天线耦合器1835以便匹配阻抗，从而提供最大功率传输。最后，该信号 经由天线1817被传送到本地基站。可以提供自动增益控制(AGC)来控 制接收机的最后阶段的增益。可以从那里将信号转发到远程电话(其可以 是另一蜂窝电话)、其它移动电话或连接到公共交换电话网络(PSTN)的 陆线，或者其它电话网络。

被传送到移动终端1801的语音信号是经由天线1817来接收的，并且 立即由低噪声放大器(LNA)1837进行放大。下变频器1839降低载波频 率，而解调器1841去掉RF仅留下数字比特流。然后，该信号经过均衡器 1825并由DSP 1805进行处理。数模转换器(DAC)1843转换该信号并且 将所得到的输出通过扬声器1845传送给用户，所有这些都在主控制单元 (MCU)1803(其可以被实现为中央处理单元(CPU)(未示出))的控制 之下。

MCU 1803从键盘1847接收包括输入信号的各种信号。键盘1847和/ 或MCU 1803结合其它用户输入组件(例如扩音器1811)包括用于管理用 户输入的用户接口电路。MCU 1803运行用户接口软件以便促进对移动终 端1801的至少一些功能的用户控制，从而发送用户输入或信号数据流来增 量式确定位置情境。MCU 1803还向显示器1807和语音输出切换控制器分 别递送显示命令和切换命令。此外，MCU 1803与DSP 1805交换信息，并 且可以访问可选而被合并的SIM卡1849和存储器1851。另外，MCU 1803 执行终端所需要的各种控制功能。DSP 1805可以根据实现方式来对语音信 号实施各种常规数字处理功能中的任何功能。另外，DSP 1805根据由扩音 器1811所检测到的信号来确定本地环境的背景噪声级别，并且将扩音器 1811的增益设置成被选择用于补偿移动终端1801的用户的自然倾向的水 平。

编解码器1813包括ADC 1823和DAC 1843。存储器1851存储了包括 呼入音调数据在内的各种数据，并且能够存储包括经由例如全球因特网所 接收到的音乐数据在内的其它数据。软件模块可以驻留在RAM存储器、 闪速存储器、寄存器或本领域已知的任何其它形式的可写存储介质中。存 储设备1851可以是但不限于：单个存储器、CD、DVD、ROM、RAM、 EEPROM、光储存器，或者能够存储数字数据的任何其它非易失性存储介 质。

可选而被合并的SIM卡1849携带了例如重要信息，诸如蜂窝电话号 码、供应服务的载波、预订细节和安全信息。SIM卡1849主要用来标识 无线电网络上的移动终端1801。卡1849还含有用于存储个人电话号码登 记簿、文本消息和特定于用户的移动终端设置的存储器。

尽管已经结合多个实施例和实现方式描述了本发明，但是本发明并不 限制于此，而是涵盖了落入所附权利要求的范围之内的各种明显的修改和 等同布置。尽管在权利要求当中按照特定组合表达了本发明的特征，但是 可以预想到，可以以任何组合和顺序来布置这些特征。