专利名称：根据周围信号确定装置的近似位置的方法
技术领域：
本发明通常涉及位置确定，尤其涉及利用周围的信号强度提供装置的近似位置的系统。
背景技术：
研发计算机的目的是帮助人们处理被认为是非常耗时的重复性任务。大部分早期的计算机用于解决复杂的数学问题。与今天使用的计算机相比较而言，第一个计算机器非常大。尽管它们具有庞大的尺寸，但是早期机器的计算能力远比今天的机器小。一般而言，该计算装置的尺寸由该时代的现有电子器件的尺寸驱动。这就意味着只有大科研所或大企业可以使用计算机器。随着适于更小电子器件的新技术的发展，计算装置的尺寸也在变小。尽管按照今天的标准仍然缺乏功效，但是计算装置的尺寸被充分地缩小，以便其可被放置在标准书桌上。从而，诞生了″台式计算机″。这使得用户在中心计算建筑物以外的位置中还能够获得可用计算技术。人们发现具有在他们的办公桌上利用计算技术而不是向中央位置提交计算问题的能力，这使得他们的工作更加有成果。最终，将台式计算机搬移到家庭环境中以更加方便地工作的想法成为现实。
当计算机进入家庭时，其工作以外的其他用途变得明显。这使得人们不只将计算机视为是一种工作工具，而且还是一种有用的设备，例如其可以用于玩游戏，辅助学习、处理家庭的远程通信，甚至控制家用器具和灯光。然而，一般而言，用户只限于计算该计算机上可获得的信息。可以在台式计算机上安装并玩游戏，却不能和其它位置处具有计算机的人共玩游戏。运用电话调制解调器技术连接这些计算机的第一次尝试给出了这种技术。这允许单独的用户通过拨号电话联接来进行连接。这对于市内电话来说是昂贵的，但是对于长途电话更是庞大的花费。然而，随着因特网的出现，改变了一切。它提供了一个连接全世界计算机的廉价方式。其允许用户快速并轻易地发送和接收全球范围内的信息。商业充分地利用了这个新技术，建立“电子商务”。现在用户可以在线发送并接收信息，甚至在线购买产品和服务。这种在线访问大量信息并轻易地进行交易的方式成为我们社会的主要组成部分。
理所当然的是，人们一旦享受到类似因特网这样工具的好处，则无论他们到哪都希望能使用这种工具。膝上型计算机的发展已有助于提供一个更机动的访问因特网的接入点。然而，膝上计算机仍然需要某些类型的连接，通过有线或无线的连接方式连接到因特网。这对于总是处于″运动中″的具体用户来说极大地制约了他们的机动性。技术已延续到通过发展计算机来适应，该计算机需要将一种设备连同大电池和提供显示荧光屏的观察窗置于主体上。尽管更加轻便，但是这些设备的笨重限制了它们的实用性，而且设备尺寸(在典型的台式计算机的基础上)的减小，一般也限制了它的计算能力。另外，因为它的复杂性，所以其是一种这样的设备，即用户必须选择使用、了解它的局限性和限制，并且要小心不损害精密设备。
随着社会利用新技术，开始对其提出了更高的要求。计算装置的最初的用户对其能够减轻他们的工作的重复性任务的能力感到高兴。他们更高兴迈入安装有计算装置的办公楼，使其不必作重复性的任务。由于社会已习惯于在工作中和家中具有易用的计算机，因此现在要求到处可用的计算信息。在一些地方，信息站已出现在机场和大型购物中心，以致人们可以轻易地访问信息。但是这对于某些试图获得最小最轻并能够在可以携带它们去的任何地方都能进行访问的计算装置的用户来说还不够。像个人数字助理(PDA)和超小型膝上计算机这样的产品常试图当用户移动时向其提供信息。
尽管现在可用的计算装置的尺寸小，但是它们的运作原理通常与发明的第一个计算装置类似。用户″接近″设备并问它问题。然后该设备试图向用户提供信息。进程已经发展到″推入技术″(push technology)，其中用户预编程设备以检索所需的信息。然而，这既耗时，又一般假定用户是固定的进行编程。尽管用户在家时，想要知道其所在城市的时间和温度，但当他们在另一个城市旅行时，在那时那些信息变得与用户不相干。为了克服这个问题，技术已开始集中于解决得到用户位置这样的问题。最明显的选择是利用全球定位系统或GPS。这是一种军用卫星定位系统，其用来协助处于移动中的军队和装备的位置。政府从他们的卫星向公众提供跟踪的较少的决定版本。尽管不如军用型的准确，但与传统方法相比还是非常准确的。最初使用卫星跟踪的民用设备庞大且难于使用。最后，GPS部件在尺寸上缩小了很多，从而易于运输。甚至该部件发展到能够直接塞入像膝上计算机这样的便携式电脑中。这个结合允许用户跟踪他们的进程，诸如当他们驾驶时在他们的膝上计算机显示街道图像。令人遗憾的是，拖着膝上计算机、连接所有连接到GPS天线上的连接物以及找到所有设备的电力使得这个技术过于繁重。另外，由于该技术的性质，当GPS可以直接访问最少数量的卫星时其才工作，这限制了它在人口稠密区，诸如在具有摩天大楼的较大城市中以及当人在室内时的使用。
用户逐渐要求在不需要烦累的设备的情况下能够拥有他们可用的相关信息。例如，经常旅行的旅客想要无论他们位于何处都能够拥有他们可用的气象信息、机场信息或出租汽车公司信息。加油站、饭店及其他企业想要得到旅客并让他们在适当的时刻了解他们所处的位置。尽管对一个地方缺乏预先的了解，但这样的信息流通允许用户更加有效地使用他们的时间和资源。商人还可以得益于能够快速确定新客户的地方资源。提供有关基于所需基础的信息是增加交易的最有效方式。

发明内容
为了提供本发明某些方面的基本知识，以下提供简化的发明综述。这个摘要并不是本发明的详尽概述。其不用于确定本发明的关键/重要元件或描写本发明的范围。其的基本目的是以简化形式，如稍候提供更详细说明的前序的方式提供本发明的一些基本原理。
本发明一般涉及位置确定，尤其涉及利用发射器的多个周围信号来提供设备的近似位置的系统，发射器例如为基站、天线塔、活动平台、建筑物天线等等。由诸如微软智能个人对象技术(SPOT)此类技术提供的实际信号强度和信号强度指示符之间的单调增长属性被平衡以确定设备位置。这提供了不需要校准单独的设备和/或定义确定位置的计量单位的定位方式。通过利用施加于周围信号频率的观测上的推理，获得对设备定位的方式。在本发明的一个方面，使用等级矢量从测量信号强度矢量的单调递增函数中隔离出结果。这使本发明减低对为了确定位置而需要获得绝对信号强度的敏感性。本发明通过提供一种系统还使得便于设备定位的近似定位，该系统不需要获得基本数量的可用信号但仍然提供确定位置方面的基本准确度，减少了计算及数据存储要求。
为了实现上述和有关目的，在此将结合以下描述和附图来描述本发明的某些例证性的方面。但是，除了其中可应用本发明原理的各种方式的少数几个，这些方面是象征性的，并且本发明试图包括所有这类方面及它们的等价物。当结合附图来考虑时，根据发明的详细说明可以清楚本发明的其他优点和新颖特征。
附图简述

图1是根据本发明一个方面的信息系统的结构图。
图2是根据本发明一个方面的定位系统的结构图。
图3说明根据本发明一个方面的使用定位系统的设备。
图4是说明根据本发明一个方面的信号强度的准确度的图表。
图5是说明根据本发明一个方面的信号强度的单调性的图表。
图6是说明根据本发明一个方面的散列码置换的三维空间图。
图7说明根据本发明一个方面所使用的地图。
图8是说明根据本发明一个方面的无线电信号强度指示值的图表。
图9是根据本发明的一个方面的分级准确度的实例。
图10是根据本发明一个方面的在测量信号强度和模拟信号强度之间的斯皮尔曼相关性直方图。
图11是根据本发明一个方面的西雅图区中的无线电台的模拟信号强度表。
图12是根据本发明一个方面的在七个选择站的测量信号强度和模拟信号强度之间的斯皮尔曼相关性直方图。
图13是说明根据本发明一个方面的试验区的地图。
图14是说明根据本发明一个方面的单元宽度和中间误差之间关系的图表。
图15是说明根据本发明一个方面的一个给定单元宽度的概率密度函数和累积密度函数错误的图标。
图16是说明根据本发明一个方面的相关阈值和中间误差之间的关系的图表。
图17是说明根据本发明一个方面的窗口大小和中间误差之间的关系的图表。
图18是根据本发明一个方面的一种对设备定位的方法的流程图。
图19是根据本发明一个方面的对设备定位的方法的另一流程图。
图20是根据本发明一个方面的一种训练定位设备的方法的流程图。
图21是根据本发明一个方面的一种为定位设备所使用的修正修正直方图方法的流程图。
图22是根据本发明一个方面的一种修正修正位置推理的方法的流程图。
图23是根据本发明一个方面的一种最优化为定位设备所使用的周围信号组的方法的流程图。
图24说明其中本发明可以运行的实例运行环境。
图25说明其中本发明可以运行的另一实例运行环境。
发明的详细说明现在将参照附图来描述本发明，其中相同的参考数字自始至终指示相同的组分。在以下描述中，由于说明的目的，为了彻底了解本发明而阐明了很多特定细节。然而，很明显的是没有这些特定细节也可以实施本发明。在其他情况中，为了便于描述本发明，公知的结构和装置以结构图的形式示出。
正如本申请所用的，术语″部件″意指与计算机相关实体，或者硬件、硬件和软件的结合、软件或执行中的软件。例如，部件可以是，但不局限于处理器上运行的进程、处理器、对象、可执行部件、执行的线程、程序和/或计算机。举例来说，运行在服务器上的应用程序和该服务器都可以是一种计算机部件。在进程和/或执行的线程之内可以存在一个或多个部件，并且一种部件可以位于一个计算机和/或分布在两个或更多计算机之间。″线程″是操作系统核心预定执行的进程之内的实体。众所周知，在本领域中每个线程都具有一个关联的″上下文″，该上下文是一种与执行的线程有关的易失数据。线程的上下文包括系统寄存器和属于该线程的进程的虚拟地址。因此，有效数据包括随着线程而变化的线程的上下文。
如在此所使用的，术语″推理″一般涉及通过事件和/或数据从一组观测结果中推出进程或推断系统状态、环境和/或用户。例如，可以利用推理确定特定的上下文或行为，或者可以得出状态的概率分布。该推理可以随机的，也就是说根据对数据和事件的考虑来计算所关心的状态的概率分布。推理还可能涉及从一组事件和/或数据中组成高级事件所应用的技术。根据一组观测的事件和/或存储的事件数据，这种推理构成新的事件或行为。
本发明公开了一种通过分析多重信号发射器发送的周围信号来确定粗略位置，如在室内和/或户外信息的方法，发射器诸如商业无线电台等等。在本发明的一个实例中，由于它的运行使用极少的电力，使得其成为小型的低功率设备的位置信息的可行信号源，该小型设备提供一种形式的信号强度指示，例如像微软的SPOT此类。SPOT集中于开发手表大小的设备，该设备具有通过编码在有规则的FM无线电广播中的数字数据接收通知的能力。在一个实例中，利用本发明的设备和/或方法能够利用SPOT设备的先有能力接收FM并测量信号强度来建立具体位置通知服务。在一个实例中，本发明利用名为″RightSPOT″算法的算法。本发明还不易受利用本发明的设备的结构制造差异所引起的变化影响。
便携式设备中的位置认识允许新机制的销售和交易。例如，用户可以希望预订相应于他们所处位置或附近的提供折扣和促销的服务。零售商，诸如餐馆老板可能希望利用这种关于时间限制报价的敏感定位来上客平衡，以便填补慢夜晚之间的空饭店。当在短时期期间通过只替换那些可以相应的人来限制通知的数量，敏感位置的过滤可以限制只对离营业所足够近到提供这种响应的上客平衡的客户的促销。
在图1中，示出了根据本发明一个方面的信息系统100的结构图。信息系统100包括具有信息部件104的信息系统部件102，定位系统106和信号部件108。信号110由信号部件108接收并被处理成信号强度指示符。这个处理一般需要模数的处理。信号部件108可以处理各种信号，诸如周围无线电波等等，其包括但不限于，调频(FM)信号。一旦将信号变为信号指示符，就将其传递到定位系统106。定位系统106处理信号指示符并向信息部件104提供位置。信息部件104利用该位置导出一组相关数据。数据关联可以严格地以位置和/或位置和用户偏爱性的组合(通过用户输入端，未显示)为基础。该数据还可以与那些从便于处理的可下载查找表格的信息有关。一旦选择了该数据，那么就通过用户接口将其作为“所需信息”提供给用户，该接口诸如为图形用户界面(GUI)和/或基于文本的用户接口等等。
在本发明的另一实例中，定位系统106存储该位置。这允许在较迟的时间点利用定位数据，例如由于设备方向而导致的降低了定位的敏感性(例如，平均前″X″次位置推理)。跟踪系统(例如，车辆、包裹、人员、设备跟踪等等)还可以利用这类历史定位数据。因此，例如可以利用本发明帮助警察确定被偷窃对象(诸如汽车)位于何处，或者可以帮助包裹货运局在发现交货延迟之后确定如何传送特定的包裹。父母还可以利用本发明的一个实例获悉他们的孩子在前一段时间内位于何处。同样，老板可以跟踪雇员和设备以提高工作实绩。还可以利用本发明跟踪动物，诸如宠物等等。利用本发明，计算机还可以自动地报告它们的位置。这允许计算机基于它的位置自动地配置其自身，像时区、国家和语言等等这类东西。
在本发明的另一实例中，提供一种基于位置管理有限资源的装置。该有限资源可以包括，但不限于存储器、电力和处理能力等等。例如，如果数据存储能力受到限制，定位可用于丢弃已存储的数据，诸如不在临近设备的当前位置的区域的地图。这提供了存储有关不能另外存储的当前位置的附加信息的存储空间。在本发明的又一实例中，可以利用位置信息帮助其他实体，诸如硬件设备和软件程序等等。这些可以包括，但不限于导航系统、绘图软件、跟踪软件和定位软件等等。同样，可以在基于突然事件的设备中利用本发明的一个实例来在危险环境中，诸如在医疗事故、火灾、洪水和基础结构修理中提供援助。可以提供诸如用于火灾控制的水源、房屋建筑布局、医疗服务位置、地下管线和气象报告等等这类信息。还可以利用本发明来根据位置发布对时间敏感的信息、广告、天气预报、实体的邻近信息等等。实体的邻近信息可以包括，但不局限于当朋友或同伴靠近设备的位置时进行通知的同伴名单型服务。同样，当其他车辆到达该地区时还可以通知设备。可以当作积极效果利用这些信息来聚集对象，也可以当作副作用来利用这些信息通知对象以允许该等对象远离或分离。
在本发明的又一实例中，提供一种根据事件位置而非事件的时间来组项的装置。例如，如果一个人在他们去大峡谷然后到拉斯帕尔马斯，然后再回到大峡谷的休假时进行摄影，那么他们可以具有他们的相片，该等相片被自动地根据位置(例如，所有大峡谷拍摄在一起)而非根据他们所拍摄的实际顺序存储。由于还可以在室内利用本发明，所以其还可以根据室内事件以及户外事件组项。对于这些应用，经常不需要具有详细的纬度和纵坐标，而只须知道在那个城市或城市的一部份拍摄了相片。这些应用甚至可以保持不明显的粗略位置，并使用这些性质将项目聚集和/或组合到视图和/或分类的不同组中的。
请参考图2，说明了根据本发明一个方面的定位系统200的结构图。定位系统200包括定位部件202。定位部件202接收被用来训练定位部件202的训练数据204。训练数据204可以包括用于各种位置指定信号等的散列码置换等。可以根据通过实地旅行到一个位置和/或通过提供所需信号特性的模拟软件所获得的信息来计算该数据204，以便获得信号特性。在本发明的其他实例中，不使用训练数据。信号强度指示符输入206允许定位部件根据信号强度指示符确定它的位置。该指示符不要求其实际信号强度的绝对值。定位部件202以关于绝对值的脱敏方式处理信号强度输入206，以提供定位208。该定位部件202一般包括计算等级矢量的分析部件(未显示)，该等级矢量提供一种与绝对值无关地把信号强度指示符分等的方式。
转到图3，示出了SPOT设备300的示例。SPOT设备300包括可佩带设备302、天气预报显示器304、交通显示器306、饭店显示器308和文娱显示器310。无所不在的计算的一个保证是将用户同他们在世界上来回运动的重要信息相连。本发明的一个实例补充SPOT设备的小型低功率设备平台。如图3所示，SPOT向用户提供了一种在手表大小的设备上接收关键通知的方式。SPOT设备被设计成能在频宽(特别是从主无线电台租借的)上倾听标准FM无线电台载波频率上的数字编码数据，诸如新闻故事、气象预测、个人信息、交通更新和零售目录等等。该设备具有将数百万的人同重要的通知和警报相连的潜力。
除小尺寸构成因素以外，SPOT设备的一个特征是数字式电子表此类的长电池寿命，使充电的间隔时间最大化。从而，使尺寸和功耗最小地设计SPOT设备。在一个实例中，利用本发明来提供一种非常低功率地识别设备的位置的方法，所述设备如SPOT设备。由于利用本发明，SPOT设备可以确定位置信息，因此其支持新型的实践，诸如允许设备只倾听与特定位置有关的警报。以前用于将定位数据传输到特定设备的基本方法依赖于FM无线电信号的有限范围。因此，只有在特定广播塔的范围内的设备才能接收与该广播塔覆盖区域有关的数据。但是，对于某些信息，这个定位分辩率太不精确。交通更新，有限现金折扣报价和附近吸引人的事物的名单需要比FM广播电台覆盖区所提供的更精确的定位过滤。尽管GPS是用于提供更精确的位置信息的候选对象，但是GPS接收器将耗费宝贵的电池电力，并且增大了已经密集压缩的设备的体积和费用。另外，GPS只限于其中可以建立与卫星的直接连接的外部使用。
在本发明一个实例中，提供一种根据对存在的信号频率发射器的周围信号强度所做的分析来定位设备的装置，该信号频率发射器例如为FM广播电台。利用诸如″RightSPOT″此类算法的本发明的系统和方法可以依赖已研发的用于接收通知的SPOT技术，该技术包括用于测量FM频带中的适当频率上的信号强度的硬件和软件。
在一个实例中，本发明利用取自不同频率的无线电信号强度矢量来确定位置。每当要推断位置时，该设备就扫描一组FM频率并记录每个的信号强度。标准SPOT设备扫描多个FM广播电台并测量信号强度，以便发现发送SPOT数据中具有充足能量的一个。在本发明一个实例中，通过本发明的设备中的模数转换器(ADC)，提供一个接收信号强度指示符(RSSI)。对每个频率的未处理数字测量值进行换算并平均，例如在13毫秒读取20次上。一般不为测量任何某单元中的RSSI或使设备到设备一致而校准ADC和有关电路。本领域熟练的技术人员可以理解到尽管上述实例利用了SPOT技术，诸如RSSI，但是其它用于获得信号强度指示符的装置也适合于本发明。本发明可以利用任何信号强度指示符，无论是否具有提供相对信号强度的单元。
在图4中，图表400示出了一个说明根据本发明一个方面的信号强度的图标。垂直轴表示输入信号强度，而横轴是来自一个设备的测量信号强度(RSSI)，例如像提供RSSI的SPOT设备。曲线402表示由小三角形404表示的测量数据点的适当数学函数。用于RSSI测量设备之间的意料之内的不一致提供了一个障碍，这样的变化使得难于概括出重复使用信号强度和位置之间的单一映射。解决这个问题的一个可能方法是使用一个已知FM传输强度来具体地为每个设备标定一个预验值。这些测试的一个结果如图4所示，其示出了特定设备的RSSI读取如何随已知传输信号强度的变化而变化。这个测试的数据将被拿到法拉第笼(Faraday cage)中，但是该程序对于大批量地生产来说被认为是太昂贵的。另一个解决方法是训练处于不同位置的每个设备，随后聚集要使用在相同的设备中的已知地方的信号强度矢量。普通的消费者可能不会认同这种训练方式。
除了制造变化之外，信号强度还受设备方向、它的环境和附加装置的调整的影响，诸如还可以作为信号接收天线的腕带等。几乎不可能预测所有的这些影响绝对信号强度的可变因素。如果可以预测绝对信号强度，那么随机结构，像位置判断的统计模型化方法中(IEEE Transactions on Mobile Computing，2002；l(1)p.59-69)的T.，P.Myllymaki和H.Tirri是适当的。但是，对于给出的发现每个设备的反应特性的不切实际性来说，需要一个比较信号强度的替换方法。
不依赖于作为位置指示符的绝对信号强度，本发明利用提供更实用的推理的信号强度变换。在通常测试中，利用本发明，诸如RightSPOT算法的设备通过一组广播电台的测量RSSI提供它们的等级，如以下所述。最后，设备可以不依赖于给出一致的绝对信号强度。由于该事实，根据相对信号强度相对一致的的事实来利用代替的假定(即，对于一个给定位置，按信号强度排序的广播电台的顺序表变化不是很大)。更确切地说，假定输入信号强度和测量RSSI之间的关系不是单调升高的。在图5中，示出了一个说明根据本发明一个方面的信号强度的单调性的图表。图表500表明如果移动装置的测量RSSI是一个输入信号强度的单调递增函数，则同时还保存了输入信号强度顺序。例如，如果A＜B＜C，那么通过相异RSSI测量函数来变换的这些值被以实质类似的信号强度顺序保持。这允许本发明可以与多种设备来一起运行，不管在它们如何测量信号强度中的设备到设备的变化。
在一个实例中，本发明利用通过扫描一列n个无线电频率(诸如FM无线电频率等等)来推断设备位置的算法，f＝(f1，f2，...，fn)产生相应得测量信号强度的矢量s＝(s1，s2，...，sn)。然后利用一个排序程序来计算信号强度的等级矢量，上升排序的v＝(r1，r2...，rn)，其中每个ri给出s中的相应si的等级。例如，如果信号强度矢量为s＝(12，40，38，10)，那么相应等级矢量为v＝(2，4，3，1)。应注意，等级矢量对s成分的任何单调递增函数不敏感，这使得算法实用于不同的设备如何测量信号强度的变化。从而，本发明不需要绝对信号强度来确定设备位置。
作为另一个例子，无线电频率可以表示能通过索引[1...n]识别的不同广播电台。对每个站台的RSSI的测量产生一组有序对，其给出了每个广播电台的站台索引[1，……n]和信号强度{(1，s1)，(2，s2)，(n，sn}。然后通过信号强度对这组广播电台强度多元组进行排序，以得到等级矢量。例如，假定n＝3，从而扫描结果是{(1，40)，(2，30)，(3，35)}。对这组有关信号强度的有序对进行分类，得出{(2，30)，(3，3)，(1，40)}。等级矢量是以信号强度排序的广播电台索引，即表示s2＜s3＜s1的v＝(2，3，l)。可以分解相等的信号强度，例如通过任意排序，第一检测排序，多数常用的检测排序等。
对于n个广播电台来说，有n！个可能的等级矢量，其是整数1，2，...，n的排列。每个等级矢量可使用由Knuth，D描述的1981年，麻萨诸塞州读物中Addison-Wesley的《计算机程序语言技术的半数算法》中64页所述的整数混合基表达式(算法P)映射至整数集r∈{0，1...n！-1}。从而，为每个信号强度的排列产生唯一的散列码。
本发明的分类计划通过假定不同的位置将显示出不同的相对信号强度来激发。理论上，每个位置将映射到r的单个的唯一值。实际上，由于来源于诸如接收单元，如SPOT天线的局部倾斜和位置此类因素的噪音，根据不同的结构和与建筑物和地形有关的几何结构在周围信号发射器的相对路径上变化，因此每个位置产生不同的r分布。
应理解的是，根据本发明各个方面的分类可以利用基于随机的和/或基于统计的分析(例如，分解为分析效用和成本)，以便预测或推断用户想自动完成的行为。分类器可以是将输入属性矢量的一个函数，即x＝(x1，x2，x3，...，xn)映射到输入属于一类的可靠度，也就是说，f(x)＝可靠度(类)。例如，可以利用支持向量机(SVM)分类器，SVM一般通过发现可能输入的空间中的动态变化超曲面操作。其它直接的和间接的模型分类方法例如包括naiveBayes、贝叶斯网络(Bayesian networks)、决策树，并且可以利用提供不同的独立模式的随机分类模式。在此说用的分类还是统计回归的表现，应用该统计回归来研发优先的模型。
转到图6，描述了说明根据本发明一个方面的散列码排列的三维空间图600。图600包括规格化的柱状图轴602，位置轴604和导出的排列散列码轴606。例如，在本发明的一个实例中，为了训练一个系统，接收设备，诸如SPOT设备被带入每个L位置处，聚集散列码ri(l)，其中l＝1，2...，L在位置上索引，而i＝1，2，...，Nl在位置l处所观测到的散列码上索引。对于每个位置，构成散列码的规格化柱状图以估计从该点所看到的散列码的离散概率分布，p(r|l)。图6示出了六个位置三个频率的规格化柱状图的实例。
给定观测似然性p(r|l)和观测R*，由贝叶斯法则计算任一L位置的概率
p(l|r*)=p(r*|l)p(l)Σl′=1Lp(r*|l′)p(l′)---(1)]]>这里，p(l)是当前所在位置的先验概率。由于不存在设备位置的特定在先认识，因此假定了一个均匀分布，设定p(l)＝l/L。与其计算似然性，还不如直接比较非规格化的后验。分类器，例如像贝叶斯分类器这样的分类器识别具有最大后验概率的类，即l*=argmaxp(l|r*)l=1...L=argmaxp(r*|l)l=1...L---(2)]]>算法上，这意味着为了观测r*，参照规格化的柱状图(图6)，在位置l∈{1，2，...L}的整个范围内查找p(r*|l)的值，并采用具有最大p(r*|l)值的位置l。
作为使用本发明的一个实例，描述了以下测试。从实验室所存储的测试设备中选择了三个SPOT手表。没有尝试选择那些能够发出一致的信号强度的手表，并且也没有相对于绝对信号源或相对于彼此来尝试校准这些手表。考虑到执行校准设备的测试的经济可行性，这模拟了这种设备的标准生产运行。
请参考图7，示出了根据本发明一个方面所使用的地图700。地图700包括6个表示西雅图郊区的六个位置702-712。对每个设备进行编程，以测量32个不同地方的FM广播电台的信号强度。然后将设备运到西雅图地区的6个不同的郊区内，记录所有的32个信号强度，每秒对每个广播站进行一次测量。在每个郊区，当绕郊区的传播核心运动时，平均进行720次(大约10分钟)读取。选择传播核心作为本发明的一个令人信服的应用，其例如包括传播发送对时间敏感的报价的商行，以及列举当地吸引人的事物。
在图8中，描述了说明根据本发明一个方面的无线电信号强度指示值的图表800。图表800由原始数据802和中值过滤数据804组成。如图8所示，发现来自设备的原始RSSI数据有噪音，所以将窗口中值滤波器应用于该数据，使用它本身和在前的29个未过滤值的中值替换每个RSSI。本领域熟练的技术人员可以理解，其他过滤装置也可以代替该窗口中值滤波器来完成。
通过交替地从三个作为规格化直方图基础的设备的一个中拾取数据来进行测试，并且使用来自其他两个设备的数据进行测试。与只对每个设备本身测试相比而言，这是一个更现实的测试，因为在本发明的一个实例中，该设备最终依赖于确定它们位置的一个既定程序组的直方图。
转到图9，说明根据本发明一个方面的分类准确度的实例900。实例900由周围信号发射器数量902、周围信号发射器904的子集和分类准确度结果906所构成。这示出了将该设备正确地分类到用于进行测试的六个郊区的一个中的频率。努力使位置确定的存储和计算负担最小，诸如利用32个已记录的广播电台的缩小很多的子集。对于n个广播电台的每个测试，检查要用于分类位置的一组 不同的站台的组合。依据分类准确度，结果如图9所示。因此，可以同更少的周围信号发射器来利用本发明，而且仍然被用于定位设备。
所报告的准确度是在全部测试上进行正确推理的一小部分，在全部测试中，拿出一个设备来制出柱状图而其他两个设备用于测试。对于n 5，可以测试全部可能的组合。对于n＞5来说，测试10000个组合的随机子集。这用于解释为什么当从n＝5移动到n＝6站台时记下分类准确度；很可能没有发现通过基于模拟所选择的n＝6的随机子集的最好组合。使用n＝8个广播电台时，最佳分类准确度为81.7％。应注意，定位准确度采掘程度是以利用周围信号发射器(例如，无线电发报机等等)和利用不倾向于提供位置信息的接收器的有机方式处理的。
这个实例证明利用本发明的一个实例使用现有的周围信号发射器将设备定位于郊区的可行性，周围信号例如像FM无线电信号。在本发明的一个实例中，通过使用同本发明一起使用的现有技术，例如像SPOT设备，只需要向现有的结构中添加少量软件就可使现有硬件平衡以测量信号强度，如FM无线电信号请读，使得定位能力，从而能够定位。不同的设备有差别地测量的信号强度，并且信号强度也受其他许多变量影响。例如，使用贝叶斯分类算法的本发明不利用绝对信号强度，而是利用信号强度的等级，以便保证交叉设备和其他变量的稳定性。
显然，为了从排列散列码中推断出位置，需要位置和散列码之间的关系。如上文所描述的那样，确定这个关系的一种方式是在地上实际观察位置并记录信号强度。然而，对于一般的应用来说，如果广播电台改变了它的发送器的功率与/和位置，那么其将是令人厌烦的并且还需要维护。因此，还可以使用该本发明在没有事实上参观不同位置来预料不同位置的信号强度特征，以便获得信号特征或″训练数据″。与其进行大量的物理测量，还不如利用RadioSoft的ComStudy软件(通常访问，因特网网点http://www.radiosoft.com/)及其类似软件被用来产生模拟的FM无线电信号强度地图。这种模拟还可以便于为最佳的位置确定要聆听的广播电台的有效子集。使用无线电强度地图的最理想方法包括利用概率方法来研究模拟的可靠性和可能性偏差如何随着基于拓扑、拓扑与/和发送器之间的几何关系，以及建筑物和其他人造构造物存在而变化。例如，我们可以根据搜集的有关模拟无线电强度和实际检测的无线电强度的差异为可靠性与/和偏差训练统计分类器，并利用这种分类器研发置信度与/和校正无线电映射表和无线电强度排序函数。
同样，可以使用位置持续概念来填充可披露的置信度中的缺口。例如，如果不确信设备在一个具体位置，那么如果时间没有长到能够远行时，假定设备接近于最后有把握检测到的位置上。
该ComStudy软件支持许多可以用来预知FM无线电地图的无线电传播模型。根据其公知的准确度，在本发明的一个实例中选择Longley-Rice模型(参看，P.L.Rice，A.G.longley K.A. Norton和Barsis A.P.；Transmission LossPredictions for Tropospheric Communication Circuits；National Bureau ofStandards Technical Note 101，1月，1967)。由于其结合了反射、折射(当无线电波上升穿过大气时，射线被弯曲)和几种类型的衍射(信号在斜坡上的溢漫)，所以其通常很准确。该模型利用地面地图来模拟斜坡和山谷的影响。
ComStudy通过每个广播电台发送器的频率、发射功率和位置(纬度，经度)使每个广播电台发送器参数化。对于每个发送器，产生一个场强度矩阵。该矩阵是在所选择的地上区域上延伸的矩形单元的格网，每个单元格包括议论中的发送器发送的信号功率信息。该单元格的宽度选择为6弧秒(大约南北向185米及东西向124米)。这相当于每平方公里具有40点(单元格)。然后ComStudy应用选择的传播模型来计算每个单元格中心的场强度。在此实例中，为华盛顿区西雅图的28个当地FM无线电台生成地图。
在为位置推理而利用模拟信号强度地图之前，要确定精确地映射预知排列矢量的置信级。为了完成这项工作，对SPOT手表进行编程来测量相同28个FM无线电台的信号强度，以生成地图。然后，将SPOT手表带到该区域，记录所有28个站台的信号强度，每秒对28个站台中的一个进行扫描，结果对每个站台要进行大约3920次的读取。同样从GPS接收器中记录纬度和经度。为了确定模拟的准确度，在分等级的广播电台之间从测量的信号强度和从模拟的信号强度推算出枪兵等级相关性(参看，William H.Press，Saul A.Teukolsky，WilliamT.Vetterling，和Brian P.Flannery；C语言中的数字技巧；1992，剑桥大学出版)，利用GPS读取以从映射中确定要使用哪个模拟强度。不使用Kendall的方法而使用枪兵等级相关性的原因是因为数据值等级之间的差异还更分别地给予更多的加权。相关性范围为[-1...1]，″1″表示相等的等级，而″-1″表明相对等级。
在图10中，描述根据本发明一个方面的在测量信号强度和模拟信号强度之间的斯皮尔曼相关性柱状图1000。柱状图1000示出超过95％的测量的等级使用在[-1...1]上的至少0.6的因数校正。这指出该模拟结果足够准确地确定SPOT手表的位置。如以下详述的那样减少站台的数量，那么将获得更好的相关性。
对于28个可用的广播电台来说，提供了28！3.05×1029个不同等级矢量，其需要庞大的计算和存储的开销。然而，这些站台中的多数从具有相似发射功率相同的塔进行广播。来自同一定位的测量信号强度，相同的发电厂是多余的。为了消除这些冗余，将28个站台分成近似相同站台的组。以下标准用于确定类似性1、根据在模拟信号强度映射上空间对应的点计算所有成对电台之间皮尔森(Pearson)相关系数(参看，id)。(请注意皮尔森相关系数是标准的线性相关系数，并不是等级关系。)2、找到彼此相关地大于某一阈值的电台组。对于本发明的一个实例来说，所使用的＝0.95。
3、从每个相关分组中选择具有最高平均信号强度的电台以表示组。
将上述标准应用于西雅图地区的模拟的信号强度(同样将该标准应用于SPOT手表的实际测量，并导致近似相同的结果＝0.9)，找到具有至少0.95的相关皮尔森系数的七个相关电台的组。在图11中，描述了根据本发明一个方面的西雅图区中的无线电台的模拟信号强度表1100。表1100示出七个电台分组以及每个分组内部的频率、平均值和相关电台的偏离值。从每个分组中选出的电台用黑体字示出。
应用上述标准，电台的数量从28个减少到7个。这个平均数代替具有28！个不同等级矢量，也就是仅仅7！＝5040个等级矢量，减少了25个数量级。这对于用于位置确定的技术来说，在计算和存储性能上具有相当的积极效果。这对于资源受限的设备来说尤其重要。在图12中，描述了根据本发明一个方面的在七个选择站的测量信号强度和模拟信号强度之间的斯皮尔曼相关性柱状图1200。柱状图1200示出了在具有28个电台的(图10)类似柱状图1100之上的显著改善，其在测量和模拟信号强度之间具有更高的相关性。超过95％的测量信号强度等级矢量与具有0.8或更大系数的模拟信号强度有关。这进一步地强调要使用的模拟结果对于确定SPOT手表和类似装置等的位置是有效的。
模拟信号强度映射的每个单元格将被转换为等级散列码，最后利用该等级散列码从测量的等级散列码推断出位置。模拟信号强度映射在大约124米宽(东西向)和185米高(南北向)的网格上产生。这接近于ComStudy的最大模拟分辩率的限制，并且本发明的这个实例所需要更优良。而且，该高分辨率提供表示环绕西雅图的测试区域的442806个单元格(东西811个，南北546个)。等级散列码分布在
上，这意味着每个精细单元需要13位整数以表示它的散列码。无线电映射于是将需要811×546×13/8 0.7MB以表示该测试区域的散列码的精细网格。
为了减轻这个存储问题并且以合理的分辩率表示散列码，在优良网格上建立粗网格，并且根据它下层的精细单元格将每个粗单元格表示为等级散列码的柱状图。粗单元格的大小是变化的，但是标准大小是3公里×3公里，其覆盖了16×24＝384个精细单元格。对于单元格，将每个粗表格的柱状图规格化为给定的等级散列码概率分布的估算。数学上，这个类似性估算为P′(r|ci)，其中r∈
表示n个无线电台的等级散列码和ci，i∈
表示m个粗单元格的一个。
实际上，因为大量可能的等级散列码，所以柱状图被稀少地填充。由于噪音，设备的方向以及未模拟的无线电传播的影响，为单元格中的等级散列码所测量的模拟类似性p′(r|ci)为零。从而，为了填充间隙使类似性估算修正修正。
令人遗憾的是，简单修正修正的等级散列码比率不是合理的，这是由于邻近的散列码未必表示类似的等级矢量。作为替代，通过使用所有正被讨论的具有面元的斯皮尔曼(Spearman)相关系数为以上选择的阈值ρs的面元上的最大值来替换每个柱状图面元中的值来完成修正修正。在构成的等式中，(未规格化)修正修正的类似性按照以下被计算
Pu(r|c)=maxP′(r′|c)r′:s(r,r′)≥ρs---(3)]]>这里，S(r，r′)，是由散列码r和r和r′表示的等级矢量之间的斯皮尔曼(Spearman)相关系数。然后在r上将Pu(r|ci)规格化为P(r|ci)，以给出给定粗单元的等级散列码的修正类似性函数。直观地，ρs作为修正参数，具有给出更修正的较高值。
给定一个测量的等级散列码r，单元格中ck的概率由贝叶斯法则给出P(ck|r)=P(r|ck)P(ck)Σi=1mP(r|ci)P(ci)---(4)]]>给定r，这个分母是常数，并且没有预先假定装置在m单元中的哪一个单元中，平均数P(ck)＝1/m。因此，最大类似性估算按照设备的位置予以选定c=argmaxP(r|ck)ck:k∈[1...m]---(5)]]>在实际操作中，通过在最后K个信号强度扫描(临时窗口大小)上采取更经常的推理单元来使这些结果修正。这帮助防止位置推理不合理地从一处跳到另一处，尽管K的极端值可以使推理太″稠″。
以上实例是使用被编程以测量7个本地FM无线电台的减缩组的信号强度的SPOT手表，在更大的西雅图地区内完成。在该区域附近传送SPOT手表，记录所有7个电台的信号强度，每秒扫描一次7个电台，对于每个站大约产生3920次读取以及GPS位置读取。其间，产生7个电台的模拟无线电地图。在图13中，描述了说明根据本发明一个方面的测试区的地图1300。地图1300示出驾驶路径1302以及具有用于推断位置的单元格宽度为7公里的粗网格1304。驾驶路径1302包括高速公路和本地公路。
利用建立在模拟无线电地图的顶部的简单柱状图，该实例说明可以使用本发明在小于10英里(～16公里)的准确度下确定设备的位置。随后讨论相关阈值ρs、临时窗口大小K和网格单元宽度w对估算位置的准确度的影响。
该实例示出了粗网格单元格宽度w是影响位置推理准确度的，一个重要参数。增加粗单元格宽度具有在P′(r|c)的柱状图中有更多优良网格单元格的优点，从而具有更多的有关等级概率分布的信息。同样，增加单元格宽度减少了网格中的总体单元格的数量，从而减少了计算开销。但是，由于单元格宽度增大，位置分辨率也自然地减少了。在图14中，示出了根据本发明一个方面的说明单元格宽度和中间值误差之间的关系，其中ρs＝0.9并且K＝5。从图表1400可以看到在方圆10英里(～16公里)范围内存在导致低中间误差的三个值(1，7，11公里)。在图15中，图表1500、1502说明根据本发明一个方面的给定单元格宽度的概率密度函数和累积密度函数误差。误差概率密度函数(PDF)图表1500和累积密度函数(CDF)图表1502相应于单元格宽度w＝1公里、ρs＝0.9和K＝5。
影响推理算法的准确度的第二个因素是相关修正阈值ρs。如以上所述，在修正类似性估算中引入相关阈值。因此，增加ρs，将导致填充基于柱状图的P′(r|ci)估算中的更多间隙。但是，使ρs增加到某一值之上，将导致太过修正，从而减少了不同位置的分辨率。在图16中，描述了说明根据本发明一个方面的相关阈值和中间值误差之间的关系的图表1600。图表1600示出当ρs＝0.9时存在中间误差的全局极小值，其中w＝1公里和K＝5(图表不规则内插导致ρs＝0.95左右的假倾角)。
影响准确度的另一个因素是临时窗口大小K。因为广播电台是以1赫兹被扫描，因此K相应于被利用来推断位置的大量第二数据。明显地，增加K将提高准确度；但是，它也同样增加了存储和计算能力的需求。在图17中，说明了说明根据本发明一个方面的窗口大小和中间值误差之间的关系的图表1700。从图表1700中可以清楚当窗口大小k≥10时获得小于10英里(～16公里)的中间误差，其中w＝1公里和ρs＝0.9。
本发明提供一种根据周围信号强度来推断设备位置的装置，周围信号强度诸如为无线电信号强度等。它的优点包括FM无线电的宽覆盖率，覆盖室内和室外位置，并且诸如SPOT设备等用于测量无线电信号强度的目标设备的备用，提供几个英里的准确度。本发明实用于测量设备之间的误差，依靠根据周围信号而非它们的绝对信号强度的推理。当使用模拟信号强度时，不需要将信号强度的人工勘测作为位置的函数。通过利用等级散列码的修正柱状图，可以将设备的位置推理到小于10英里(～16公里)的准确度。通过本发明允许向资源受限的设备，诸如小型的、可佩戴的设备提供功能，应用本发明使用极少的资源。
在本发明的另一实例中，应用识别哪一个广播电台柱状图将传输给设备的方法，某些设备被给予了有限存储容量。仍在本发明的另一实例中，可以通过使时间上的位置推理修正来提高分类精确性，利用有关位置邻接的知识，并遵循约束设备在位置之间的可料到的多么快的移动。仍是本发明的另一实例，其使用决策理论方法以使位置上的给定概率分布的误诊最小化。同样，仍为本发明另一实例中，其使用其他捕获等级排序之上的相对信号强度的属性的基本表示，包括捕获强度比和通过强度分组的信号发射器的分组之间的关系。
鉴于如上所述和示出的典型系统，根据本发明可以实现的方法将通过参考图18-23的流程图来得到更好的理解。虽然，为了简化说明的目的，是以块的形式描述和示出了该方法，但是应理解本发明并不受块的顺序限制，根据本发明某些块可以不同的顺序发生和/或在此示出和描述的其他块一起发生。
此外，根据本发明，不需要所有块来实现所述方法。
本发明可以计算机可执行指令的一般上下文的形式描述，诸如通过一个或多个部件执行的程序模块形式。一般而言，程序模块包括执行特定任务或实现特定抽象数据类型的例行程序、程序、对象、数据结构等等。一般地，程序模块的功能可以组合或分布在本发明所需要的各种情况中。
转到图18，描述了根据本发明一个方面的定位设备的方法1800的流程图。方法1800开始于1802，提供信号强度指示器1804。指示器一般由诸如来自于广播塔、建筑物天线和移动单元(包括地面和航空单元等等)等等信号源的周围信号的信号表示。信号可以包括但不限于，调频信号，调幅信号，极高的频率信号，超高的频率信号等等，甚至更多的方向信号，诸如向上的等等。本发明还可以使于与能够指示红外线、X射线和宇宙线等等信号强度的高频率接收设备操作。类似地，本发明同样可与提供对超声波、次声波等接收的较低频率接收设备操作。本发明还可以解决随时间变化的信号和从移动平台发出的信号。还可以利用地面灵敏传播模型来对信号由于地形障碍的而发生的变化。同样，可以利用其他的传播模型来对从大型结构，诸如建筑物、纪念碑和人造物体等反射的情况做出说明。通过利用速度推算模型，还可以利用本发明来确定设备的速度和它的位置。
信号强度指示符并不限于那些以绝对比例提供准确强度的指示符。本发明可以在没有任何与该指示符有关的任何单元的情况下接受信号强度指示符。一旦提供了信号强度指示符，根据所提供的信号强度指示符1806确定位置，然后结束流程1808。该确定一般是基于允许调整分布以通过推理来提供位置的算法。在本发明一个方面中，利用了不依赖于绝对信号强度的贝叶斯分类算法。作为代替，应用信号强度的等级以便于保证诸如信号检测误差、校准误差和未知信号强度指示符源等的变化不会影响位置确定。
在图19中，示出了根据本发明另一个方面的定位设备的方法1900的流程图。方法1900开始于1902，获得周围信号，例如来自像商业FM无线电天线塔和或电台这样的信号源的射频信号1904。扫描一列无线电频率1906，并确定测量的信号强度矢量1908。然后对相对强度排序，并且计算频率的等级向量1910。然后根据信号强度排列1912的置换生成散列码1912。然后从每个所需位置获得训练定位系统的散列码1914。然后根据散列码构造规格化的柱状图1916。通过如贝叶斯法则1918来计算概率。然后利用例如为贝斯分类器的分类器来识别最大后验概率，其指出具体位置上最有可能的设备1920，然后结束流程1922。
参考图20，说明了根据本发明一个方面的训练定位设备的方法2000的流程图。方法2000开始于2002，定位在具体位置接收周围信号的设备2004。多次扫描周围信号，诸如射频信号等，以便获得它们的信号强度2006。然后对每个扫描计算等级信息，诸如等级散列码等等2008。对于具体位置，产生并存储等级信息诸如等级散列码的规格化柱状图2010。然后确定是否想从另一个位置获得数据2012。如果是，那么将该设备迁移到另一个位置2004，并且方法2000重新开始。如果不再需要更多的位置，那么流程结束2014。
在图21中，示出了根据本发明另一个方面，用于定位设备的柱状图修正的方法2100的流程图。方法2100开始于2102，根据下层的精细网格单元格计算粗网格单元格柱状图2104。通过利用粗网格而不是模拟软件，诸如ComStudy等提供的精细网格，可以在下层设备上不导致沉重存储和处理负担的情况下获得合理的分辨率。然后规格化粗网格单元格柱状图2106。这位单元格提供了一种等级散列码的概率分布的估算。然后选择相关阈值2108。这通过高值给出的更光滑，允许稀疏填充的柱状图的修正控制。修正。然后确定在相关阈值上具有斯皮尔曼相关系数的柱状图箱2110。在所有关于阈值的柱状图箱之上确定的极大值2112。在相关阈值之上的每个柱状图箱都使其值被最大值所代替2114，结束流程2116。在等式构成中，修正的类似性按照以下被计算
Pu(r|c)=maxP′(r′|c)r′:s(r,r′)≥ρs---(3)]]>其中，S(r，r｀)是由散烈码r和r｀表示的等级矢量之间的斯皮尔曼相关系数。然后在r基础上将Pu(r|ci)规格化成P(r|ci)以给出给定粗单元格的等级散烈码的类似性函数。
参考图22，描述了根据本发明一个方面的修正位置推理的方法2200的流程图。方法2200开始于2202，获得信号强度扫描的历史记录2204。然后选择位置推理修正值″K″(临时窗口大小)2206。然后确定在上″K″次信号强度扫描之上的最时常推断的位置2208，结束流程2210。最时常推断的位置成为被下层设备利用的位置。为了防止设备由于设备的定向运动和其他环境的影响而从一个位置″跳″到另一位置，这要经常地进行。通过修正推理的位置，通过设备示出一个基本上稳定的值。
转到图23中，示出了根据本发明另一个方面，用于定位设备的最佳化周围信号组的方法2300的流程图。方法2300开始于2302，获得一组周围信号以及它们各自的信号强度2304。然后在该组中所有成对信号源之间计算皮尔森相关系数2306。在本发明的一个实例中，一对信号源是基于在模拟信号强度地图等等之上空间对应的点。皮尔森相关系数表示一种标准线性相关系数，并非是一种等级相关系数。然后选择相关阈值2308。在本发明的一个情况下，这个相关阈值的典型值大约为0.95。将与大于选择的相关阈值相关的信号源被分组集合2310。然后选择具有每个组的最高平均信号强度的信号以指出组2312，结束流程2314。这个方法2300使被利用在定位设备中的等级矢量的数量减少了几个数量级。当周围信号来自单一源时，2300还特别有助于消除源冗余在本发明的情况下可以包括在编程设备上和/或终端设备本身上从用户接收输入和/或反馈的方式。这种输入可以包括用户希望从推理中排除的范围，例如，″仅仅考虑在较大城市范围中区域的这个特定子集；我不将在其他区域中旅行″。这种约束可以通过缩小位置的范围而提高系统的推理的准确度。在本发明的另一个情况下，用户可以如通过简单的安压按钮输入有关系统准确度的反馈，例如，″这个不正确；这个正确″，。这种反馈可用于提高将来推理的准确度。
为了提供实现本发明各个方面的附加的上下文，图24及随后的讨论试图提供简短的、一般说明其中可以实现本发明各个方面的一种适当的计算环境2400。虽然以上以运行在本地计算机和/或远程计算机上的计算机程序的计算机可执行指令的一般上下文的形式描述了本发明，但是本领域熟练的技术人员应该认识到本发明还可以与其他程序模块结合地实现。通常，程序模块包括执行特定任务和/或实现特定抽象数据类型的例行程序、程序、对象、部件、数据结构，等等。此外，本领域熟练的技术人员将理解本发明方法可以与其他计算机系统结构一起实施，包括单处理器或多处理器计算机系统，小型计算机主计算机，以及个人计算机、手持式计算机、基于微处理器的和/或可编程消费电子设备等等，它们中的每一个都可以和一个或多个相关的设备可行地相连通。本发明的已说明方面还可以在其中通过连接通信网络的远程处理设备来执行任务的分布计算环境中实施。但是，本发明的一些但不是全部方面可以在单计算机上实施。在分布计算环境中，程序模块可以位于本地和/或远程存储器存储设备中。
正如在本申请中所用的那样，术语″部件″意图是指与计算机有关的实体，硬件、硬件和软件的结合或执行的软件。例如，部件可以是但不限于运行在处理器上的进程、处理器、对象、可执行部件、执行的线程、程序和计算机。作为说明，运行在服务器上的应用程序和/或服务器可以是一个部件。另外，部件可以包括一个或多个子部件。
参考图24，用于实现发明各个方面的示例性系统环境2400包括通用计算机2402，其包括处理单元2404、系统存储器2406和将包括系统存储器的各个系统组成部分耦合到处理单元2404的系统总线2408。处理单元2404可以是任何市场上可买到的或专有的处理器。另外，处理单元可作为由一个以上的处理器构成的多处理器，诸如可以并行连接。
系统总线2408可以是几种类型总线结构中的任一类型，其包括，仅举几个例子，存储器总线或存储控制器，外围总线，和使用各种诸如PCI、VESA、微通道、ISA和EISA此类通用总线体系结构的本地总线。系统存储器2406包括只读存储器(ROM)2410和随机存取存储器(RAM)2412。包含诸如在启动期间有助于在计算机2402内的元件之间传输信息的基本例行程序的基本输入/输出系统(BIOS)2414，被存储在ROM 2410中。
计算机2402还可以包括例如硬盘驱动器2416、例如在活动磁盘2420上进行读或写的磁盘驱动器2418、和例如在CD-ROM盘2424或其他介质上进行读或写的光盘驱动器2422。硬盘驱动器2416、磁盘驱动器2418和光盘驱动器2422分别通过硬盘驱动器接口2426、磁盘驱动器接口2428和光驱动器接口2430连接到系统总线2408上。驱动2416-2422以及它们的相关计算机可读介质提供用于计算机2402的数据、数据结构、计算机可执行指令等的非易失性存储。虽然以上描述的计算机可读介质指的是硬盘、可移动磁盘和CD，但是本领域熟练的技术人员应理解，其他的计算机可读的介质的类型，诸如磁带盒、闪存储卡数字视频光盘、Bernoulli盒式磁带机等也可用在典型运行环境2400中，并且这样的介质可以包含执行本发明的方法的计算机可执行指令。
大量程序模块可以存储在驱动器2416-2422和RAM2412中，其包括操作系统2432、一个或多个应用程序2434、其他程序模块2436和和程序数据2438。操作系统2432可以是任何适当的操作系统或操作系统的组合。举例来说，应用程序2434和程序模块2436可以包括根据本发明一个方面的推断设备的位置。
用户可以通过一个或多个用户输入装置，诸如键盘2440和指示设备(例如，鼠标2442)将命令和信息输入到计算机2402中。其他输入装置(未显示)可以包括麦克风、控制杆、游戏板、卫星碟、无线远程输入装置、扫描器等等。这些及其他输入装置通常通过串行接口2444连接到处理单元2404，该串行接口2444耦合于系统总线2408，但是也可以通过其他接口，并行端口，游戏端口或通用串行总线(USB)连接。监视器2446或其他类型的显示设备同样通过诸如视频适配器2448连接到系统总线2408。除了监视器2446之外，计算机2402还包括其他外围输出设备(未显示)，诸如扬声器、打印机等。
应当理解，计算机2402可以在使用逻辑连接到一个或多个远程计算机2460的网络环境中进行。远程计算机2460可以是工作站、服务器计算机、路由器、对等设备或其他公用网络节点，虽然为了简短起见，只在图24中示出了存储器设备2462，但是其一般包括关于计算机2402所述一些或所有元件。图24所描述的逻辑连接可以包括局域网(LAN)2464和广域网(WAN)2466。这种连网环境在办公室、企业计算机网络、内部网和因特网中是常见的。
当用于局域网连网环境中时，例如计算机2402通过网络接口或适配器2468连接于局域网2464。当用于WAN连网环境中时，计算机2402一般包括调制解调器(例如，电话、DSL、电缆等)2470或者连接于局域网上的通信服务器，或者具有其他在诸如因特网此类的WAN 2466上建立通信的方式。调制解调器2470相对于计算机2402来说可以是内部调制解调器也可以是外部调制解调器，其通过串口接口2444连接于系统总线2408。在网络环境中，程序模块(包括应用程序2434)和/或程序数据2438可以存储在远程存储器存储装置2462中。应当理解，所示出的网络连接是示例性的，在计算机2402和2460之间建立通信链路的其他方式(例如，有线或无线)可以在执行本发明一个方面时使用。
根据计算机编程的本领域熟练人员的实践，已经参考操作的行为和符号表示描述了本发明，该操作通过诸如计算机2402或远程计算机2460执行，除非另有陈述。这种行为和操作有时成为被计算机执行的行为或操作。应当理解，行为和符号表示的操作包括通过处理单元2404操作表示导致电信号表现的结果变换或减少的数据位的电信号和在存储系统(包括系统存储器2406、硬盘2416、软盘2420、光盘2424和远程存储器2462)中的存储单元保持数据位，以藉此重新配置或相反交互计算机系统的操作，以及其他信号的处理。其中保持数据位的存储器位置是具有相应于数据位的特定的电、磁或光性质的实际位置。
图25是另一个可以与本发明进行交互的采样计算环境2500的结构图。系统2500进一步说明了包括一个或多个客户端2502的系统。该(多个)客户端2502可以是硬件和/或软件(例如，线程，进程，计算设备)。系统2500还包括一个或多个服务器2504。该服务器2504还可以是硬件和/或软件(例如，线程，进程，计算设备)。例如，服务器2504可以驻留通过应用本发明执行变换的线程。客户端2502和服务器2504之间的一个可能的通信可以是适于在两个或更多的计算机进程之间传输的数据包形式。系统2500包括通信结构2508，其可用于促进客户端2502和服务器2504之间的通信。客户端2502可操作地连接于一个或多个客户数据存储器2510中，使用其可将本地信息存储到客户端2502中。类似地，服务器2504可操作地连接到一个或多个服务器数据存储器2506中，利用其可以将本地信息存储到服务器2504中。
在本发明的一个实例中，在两个或更多的计算机元件之间传输的数据包便于定位设备，该数据包至少部分地包括，关于基于至少一个周围频率信号指示符确定设备位置的近似值的定位系统的信息。
在本发明的另一个实例中，一种存储了便于定位设备的系统的计算机可执行部件的计算机可读介质，至少部分地包括，关于基于至少另一个周围频率信号指示符确定设备位置的近似值的定位系统的信息。
在本发明的另一情况下，基于以移动和/或稳定信号发射极为基础的信号强度指示符来确定位置。利用移动单元发送的数据来提供确定位置的稳定性。
在本发明的另一情况下，利用信号发射器的辐射模式确定位置。
应当理解，可以用于在便于计算机元件和非计算机相关元件的定位系统中使用本发明的系统和/或方法。此外，本领域熟练的技术人员应认识到本发明的系统和/或方法可应用在涉及这样的技术的电子系列中，即但不限于，计算机、服务器和/或手持电子设备、可附加电子设备(例如，磁性附加、钩和套附加、钩附加、粘合附加等)，可佩带的电子设备(例如，手表、眼镜、衣服、助听器、项链、手镯、皮带、脚镯、领带装饰针、戒指等)，等等。
以上已经描述了几个本发明实例。当然，为了描述本发明，不可能描述所有想到的部件或方法的组合，但是本领域普通的技术人员可以认识到，本发明的进一步组合和置换是可能的。因此，本发明意图包括所有落于附加权利要求的精神和范围内的变化、修改和改变。此外，对于词义的范围，用于详细说明或权利要求中的术语″包括″意图以类似于术语″包含″的方式在作为权利要求中的过渡词时被解释为″包括″。
权利要求
1.一种便于确定装置位置的系统，包括接收至少一个周围信号的元件；和一种推断装置的至少一个近似位置的分析元件，所述装置部分地基于周围信号的至少一个子集的相对信号强度。
2.根据权利要求1所述的系统，所述近似位置由实时实体所使用的分析元件予以推断出。
3.根据权利要求1所述的系统，所述分析元件提供所述装置的至少一个已推断的近似位置的修正。
4.根据权利要求3所述的系统，所述修正包括在之前的信号强度扫描的变数上获得一个最频繁推断出的位置。
5.根据权利要求4所述的系统，所述变数包括一种暂时窗口，K，其表示一个时段中的多个信号扫描。
6.根据权利要求1所述的系统，所述分析元件提供周围信号子集的优化以充分地减少它们的数量。
7.根据权利要求6所述的系统，所述优化使用相关度以有助于数量的降低。
8.根据权利要求7所述的系统，所述相关度包括一对基于至少一个空间对应的信号源位置的周围信号之间的Pearson相关系数。
9.根据权利要求7所述的系统，所述优化使用至少一个相关阈值，ρ。
10.根据权利要求9所述的系统，所述相关阈值近似等于0.95。
11.根据权利要求1所述的系统，所述周围信号包括至少一个无线电频率(RF)信号。
12.根据权利要求11所述的系统，所述设备仅能接收RF信号。
13.根据权利要求11所述的系统，所述RF信号包括由802.11信号、调幅(AM)无线电信号、调频(FM)无线电信号、电视广播信号、商品收音机信号和军用无线电信号所构成的组中选出的至少一个信号。
14.根据权利要求1所述的系统，所述周围信号包括由红外信号、X-射线信号、次声波信号、音频信号和超声波信号所构成的组中选出的至少一个信号。
15.根据权利要求1所述的系统，进一步包括一个计算至少周围信号子集的等级矢量的分级元件。
16.根据权利要求15所述的系统，所述分级元件为每个信号强度的置换(permutation)分别生成唯一的等级散列码。
17.根据权利要求16所述的系统，所述分析元件使用至少一行散列码的至少一个直方图，以促进所述设备的近似位置的分类。
18.根据权利要求17所述的系统，所述分析元件使用关于至少一个直方图的修正技术。
19.根据权利要求18所述的系统，所述修正技术包括关于至少一个直方图的至少一个斯皮尔曼相关系数的过程运用。
20.根据权利要求18所述的系统，所述修正技术使用相关阈值，ρs。
21.根据权利要求20所述的系统，所述相关阈值近似等于0.9。
22.根据权利要求1所述的系统，所述分析元件估算特定位置处所获得的散列码的离散概率分布。
23.根据权利要求1所述的系统，所述分析元件在统计分析中使用由来自一个或多个信号发射器的时变信号强度和来自一个或多个信号发射器的静态信号强度所构成的组中选出的至少一个信号强度。
24.根据权利要求1所述的系统，所述分析元件使用至少一个传播模型。
25.根据权利要求24所述的系统，所述传播模型至少部分地包括地形灵敏的无线电波传播模型。
26.根据权利要求1所述的系统，进一步包括一个全球定位系统元件(GPS)。
27.根据权利要求1所述的系统，进一步包括一个速度元件，其确定或推断部分基于周围信号子集的相对信号强度的设备的速率。
28.根据权利要求1所述的系统，进一步包括适配的可下载的查阅表。
29.根据权利要求1所述的系统，进一步包括信号强度模拟元件。
30.根据权利要求29所述的系统，所述信号强度模拟元件为分析元件提供关于至少一个所需区域的信号强度数据。
31.根据权利要求30所述的系统，所述信号强度数据包括基于覆盖所述要求区域的方格系统的数据。
32.根据权利要求1所述的系统，所述分析元件进一步使用至少一个时间坐标的信息源，以促进所述设备近似位置的确定。
33.一种有助于确定设备位置的系统，包括用于接收装置信号的设备；和多个设备，其用于推断部分基于至少一个周围信号的相对信号强度的设备的近似位置。
34.根据权利要求33所述的系统，所述周围信号包括一种无线电频率(RF)信号。
35.一种在两个或更多个便于定位装置的计算机元件之间传送的数据包，所述数据包至少部分地由与定位系统相关的信息构成，所述系统基于至少一个周围频率信号指示器确定所述设备的位置近似值。
36.一种电脑可读介质，在所述介质上存储有权利要求1所述系统的电脑可运行的元件。
37.一种使用权利要求1所述系统的设备，其包括至少从电脑、服务器、耐磨的电子器件、附加的电子器件和手持电子器件所构成的组中选出的一个。
全文摘要
所述本发明平衡(leverages)不同位置处已感知的无线电信号的强度变化以确定设备的位置。在本发明的一个实例中，推断过程用于处理周围商品无线电信号，以估算设备位置或设备位置的概率分布。在本发明的另一个实例中，系统使用适于信号强度矢量的等级矢量的学习(learning)和推理方法。这样等级顺序的移动使得系统忽视位置计算中绝对信号强度的因素。本发明通过提供一种不需要可获得的周围信号强度的实际数量的系统，并仍提供确定位置中的有用的位置推断，促进定位设备的估算。
文档编号G01C21/28GK1607400SQ20041008514
公开日2005年4月20日 申请日期2004年7月9日 优先权日2003年7月22日
发明者J·C·克伦姆, G·F·瑟麦克, E·J·霍维茨, E·C·米勒, A·A·A·约瑟夫 申请人:微软公司