使用多个选择的初始位置估计来确定位置的方法和系统

摘要

提供一种方法和系统，用于确定多个单元中每一个的位置，所述位置是从多组位置之一中选择的，这些位置的每一个都是根据不同的初始位置估计而估计的。所选择的一组位置包括具有最小误差值的那组，误差值是基于在从估计的位置确定的范围和测量的范围之间的差值的合计。通过使用不同组的初始位置估计，有更大的机会来使各组初始位置估计中的至少一组避免局部最小值，并产生更精确的单元位置估计。

说明书

技术领域

本发明总的来说涉及确定在包含多个单元的网络内操作的单元的位置，更具体而言，涉及根据对被定位的每个单元所建立的可能位置区域来使用多个初始位置估计。

背景技术

有几种情况，其中可能希望跟踪和/或估计网络内的各个单元的位置。在这些情况中的至少某些当中，一些更传统的方法，诸如全球定位系统(GPS)，可能会遇到困难。这样的例子包括当被跟踪的单元位于建筑物内部时。这是因为，GPS信号可能难以穿透建筑物的墙壁和/或穿过其他障碍。在同样的或其他情况中的一些当中，相对于位置已知或已被确定的一个或多个参考单元，范围测量的数目可能不足以实现对特定单元的方位进行三角测量。

在这些情况的至少一些当中，可能能够使用在至少一些单元之间测量的范围信息来确定对一个或多个单元的位置估计。在至少一种这样的情况中，通过迭代求最小值的方法来使与该估计相关联并与一组估计的位置相关联的误差值最小化，在至少一种情况中，所述误差值包括所测量的范围信息与对应于所计算的单元对之间的范围信息之间的差的平方和。至少一个这样的相应系统和方法的例子在Patwari等人的美国专利No.6,473,038中描述，该公开结合于此作为参考。然而，在某些情况下，根据如何选择初始位置估计来使误差值最小化的迭代方法可能限入局部最小当中，并难以收敛到更精确的解。因此，开发一种更可能识别解从而避免局部最小解的方法是有益的。

本发明人认识到，选择多个不同组的初始位置估计，它们中每一个用于对网络中的多个单元中的每一个的位置进行迭代估计，这样的方法在获得解方面是有益的，这样的方法更容易避免任何局部最小。在所确定的多个位置估计中，选择具有最小误差值的解集并用作多个单元的位置估计。本发明人还认识到，从对每个单元确定的可能位置区域中选择不同组的初始位置估计将是有益的。以这种方式，能够提供改进位置估计精度的系统和方法。

发明内容

本发明提供一种确定多个单元的位置的方法，每个单元通信耦合至其他多个单元中的至少一些，其中所述多个单元中的至少一些处于与一个或多个参考单元的通信范围中，所述参考单元的位置至少是确定的或已知的。该方法包括：测量所述单元中每一个和在彼此的通信范围内的任何参考单元之间的范围信息。然后为所述单元中每一个建立可能位置区域，包括多个可能初始位置估计。

然后从接近所述可能位置区域的区域中为所述各单元当中位置未知的每一个选择初始位置估计；并根据所测量的范围值与从估计的位置值计算的范围之间的差值，为所述单元中的每一个估计位置，其使误差值最小。然后，从所述多个可能的初始位置估计中使用不同组的初始位置估计为所述单元中的每一个选择初始位置估计，以及对所述单元中每一个做误差值最小的位置估计，重复上述动作至少一次。然后从重复的估计中选择具有最小的最小化误差值的那组位置估计。

在至少一个实施例中，为所述单元当中的每一个选择初始位置估计包括：从所建立的可能初始区域中从多个可能初始位置中随机选择位置。

在至少另一个实施例中，为所述单元中的每一个选择初始位置估计包括：从与所建立的可能位置区域相关联的多个可能初始位置的子集中顺序选择位置，所述多个可能初始位置在整个所述可能位置区域中按预设的模式间隔开。

在另一个实施例中，该方法还包括：对于与足够数量的参考单元有链接的单元进行确定，以通过三角测量来确定位置，然后对所标识的单元中的每一个的位置进行三角测量，并在三角测量保持有效的后续处理中将三角测量的单元标识为参考单元。

本发明还提供一种系统，用于确定多跳(multi-hop)网络中的多个单元中的每一个的位置，每个单元通信耦合至其他多个单元中的至少一些，其中所述多个单元中的至少一些处于与一个或多个参考单元的通信范围中，所述参考单元的位置至少是确定的或已知的。该系统包括：收发信机，其适于接收所述多个单元和和在彼此通信范围内的参考单元的连接性和范围信息；和处理器，其耦合到所述收发信机。

处理器包括存储区域，用于保存连接性、通信范围信息和多组位置估计以及相应的最小化误差值。处理器还包括计算模块，适于根据每一组初始位置估计为所述单元中的每一个确定可能位置区域，以及为所述单元中的每一个估计位置并其使误差值最小化。所述处理器还包括一个或多个选择模块，用于为所述单元中的每一个顺序选择与可能位置区域相关联的多组不同的初始位置估计，以及选择与最小的最小化误差值相关联的那组估计位置。

从下面本发明的一个或多个优选实施例的描述，并参考附图，本发明的这些和其他特征及优点是显而易见的。

附图说明

图1是示出根据本发明的至少一个实施例的通信网络的至少一部分的邻近成员之间的示范空间关系的部分空间概图；

图2是示出与一个或多个单元的不同位置估计相关联的误差值的部分示意图；

图3是部分空间概图，示出与公共单元通信的多个单元的重叠通信区域，以及基于包括一组在该多个单元和公共单元之间的范围的示范实施例的近似位置；

图4是部分空间概图，示出多个单元的重叠通信区域，其形成与该多个单元通信的单元的可能位置区域，并示出一组可能的初始位置估计；

图5是部分空间概图，示出多个单元的重叠通信区域，其形成与该多个单元通信的单元的可能位置区域，并示出一组可能的初始位置估计；

图6是部分空间概图，示出基于已知的先前位置、移动速率和自单元位于最后已知位置起所经过的时间的该单元的可能位置区域；

图7是部分空间概图，示出基于已知的先前位置和运动估计的单元的可能位置区域；

图8是示出根据本发明的至少一个实施例，确定多跳网络中多个单元中的每一个的位置的系统的框图；

图9是示出根据本发明的至少一个实施例，确定多个单元的位置的方法的流程图；

图10是示出根据图9的至少一个实施例，作为测量范围信息的步骤的一部分或除该步骤之外，对具有足够数量链接的单元进行确定和三角测量的更具体的流程图。

具体实施方式

尽管本发明可以有各种形式的实施例，但在附图中示出和在下文描述的是优选实施例，应该理解，本公开应认为是本发明的示例，并且不打算将本发明限制在所示出的具体实施例。

图1示出根据本发明的至少一个实施例，提供在通信网络10的至少一部分的邻近成员之间的示范空间关系的部分空间概图。网络10包括：参考单元12，其被表示为三角形，并且其位置是已知的或能够确定；多个盲单元14，其被表示为圆。盲单元14对应要被估计位置的单元。在至少所示出的实施例中，网络10是多跳网络，其对应这样的网络，其中某些单元对(pairs of units)不能直接通信和/或需要经由网络10内的另一个单元来通信。能够直接相互通信的单元利用在这些单元之间延伸的线16示出。所述线之一在图中与相应的参考数字相关联地示出。

通常，每个单元包括收发信机和相应的天线，其支持在通信范围内的其他单元之间的无线通信。通过相邻单元之间的通信，根据所接收信号的特性和/或时序来确定范围估计。在至少一个实施例中，接收信号强度指示、到达测量的时间、到达测量的时间差和/或到达测量的角度中的一个或多个用于确定测量的范围值。例如，在发射时，能够测量接收的信号强度并知道该信号的强度，根据预测作为距离函数的信号强度衰减的模型，能够计算范围估计。作为另一个例子，能够确定在单元对之间发射的信号的传播时间，并且基于信号的移动速率的近似以及确定的传播时间，近似得到单元之间的范围。在一些情况中，能够使用往返(round trip)通信来确定传播延迟。本领域技术人员容易理解，还存在另外的技术，用于根据与接收的信号相关联的特性和/或时序来近似得到单元之间的范围，并且能够不脱离本发明的教导而类似地使用该技术。

一旦建立了相邻单元(包括邻近的参考单元)之间的测距信息，就能够选择非参考单元中的每一个的初始位置。然后使用迭代处理来更新初始和随后的位置估计，直到与基于所选择坐标的确定的距离和基于测量的范围信息的距离之间的差值相关联的误差值不再减小，并且优选被最小化。然而，利用一些误差最小化技术，可能会陷入局部最小。在这些情况中的一些，局部最小值的偏移看来会增加误差值，并且结果会使这些值偏移回局部最小值。图2示出了一个这种局部最小的例子，其是二维显示的。

更具体地，图2示出了与一个或多个单元的不同位置估计相关联的示范误差值的部分图20。示出误差值的图时常是高于二维的。不管怎样，在具有更高维数的情况中，局部最小值可类似地出现。在示出的例子中，该图包括最小值22和局部最小值24。局部最小值可能由尖点26、隆起或高点产生，所述尖点26、隆起或高点位于局部最小值24和实际最小值22之间，并且根据在起始时你位于尖点26的哪一侧，可能使迭代解偏离实际最小值22。因为，关于你会收敛到局部最小值24还是收敛到实际最小值22，起始点可造成很大差异，对于正在确定的值选择初始值可能是重要的。

认识到初始估计能够影响到解是会收敛到局部最小值24还是会收敛到实际最小值22，所以开发了一种选择初始估计的方法，其试图提高识别收敛到实际最小值22的解的机会。通常，根据本发明的至少一个方面，使用多组不同的初始位置估计。

在至少一些情况中，通过能够确定的区域来限定单元的可能位置。图3示出待定位单元的可能位置区域30。更具体地，图3是基于多个单元和待定位单元32的一组预定传输范围，示出与待定位单元32通信的多个通信单元的重叠通信区域的部分空间概图。例如，如果待定位单元32能够接收来自三个不同单元的传输，那么该待定位单元32就可能位于区域30，在此，以弧线34A-C为界的传输区域对于三个不同单元中的每一个都重叠。然而，这不像三角测量，不是基于在这些单元中的每一个和待定位单元32之间的确定范围会收敛到近似位置。区域30由对每个单元估计的预定传输范围34来限定。如同可能通过三角测量确定的，更确切位置的例子示出为待定位单元32和其他单元之间的三个近似距离36A-C的会聚点。

在具有估计的预定传输范围(其被用于帮助限定可能的位置区域30)的单元中的一个的初始位置不确定的情况下，预定的传输范围34可以增加对应于不确定量的一个量，这可用于进一步扩展可能位置区域30。

一旦限定了单元可能位于的区域，就能够选择与该区域相关联的初始位置估计。不脱离本发明的教导，初始位置估计的这种选择可包括几个不同方法中的任意一个或多个，然而，在本申请的至少一个方面，选择多组不同的初始位置估计。在一些实施例中，可随机选择初始位置估计。在其他实施例中，通常初始位置估计可均匀地间隔开。在另一些实施例中，可基于预定的分布模式来选择初始位置估计。此外，在一些情况中，初始位置估计被限制在确定的可能位置区域，而在其他情况中，初始位置估计中的一些可偏离至可能位置区域之外。

图4示出了部分空间概图，突出显示由一对弧线42A和42B包围的可能位置区域40，其对应与待定位单元(未示出)通信的一对单元(未示出)的一对重叠的通信区域44A和44B。另外还对待定位单元示出一组示例性的可能初始位置估计，其示出为一组点，其中只有一些标记有相关的参考数字。在示出的实施例中，初始位置估计46通常在整个可能位置区域40中均匀间隔开。在至少两种情况中，初始位置估计46会落在可能位置区域40之外。在一些情况中，可能希望调整落在可能位置区域之外的任何位置，使其在该区域之内。实际间隔可取决于将使用的位置估计46的数量。

图5示出部分空间概图，其突出显示由三个弧线52A-C包围的可能位置区域50。类似于图4，图5还示出一组示例性的可能初始位置估计54。然而，与图4不同，该示范组的可能初始位置估计54按预定或预设的模式间隔开。在示出的实施例中，该预定模式以位置56为中心，位置56可对应于基于任何预定判据的最佳推测初始估计，该判据可与这里论述的概念相关或不相关。一个可能的实施例可以基于此前确定的位置来对该预定模式定位。在示出的特定模式中，初始位置估计54的位置密度较大，更接近最佳推测初始位置估计56。本领域技术人员容易认识到，作为替换，还可使用其他的预定模式，而不脱离本发明的教导。

在另一种替换方案中，可能位置区域可考虑环境特征，其可限制或排除单元位于某区域，和/或阻止单元穿过其他区域移动或进入其他区域。图6示出了基于已知的先前位置62，单元的可能位置区域60的部分空间概图。在示出的实施例中，可能位置还基于假定的或可能的移动速率，以及自单元位于最后已知的位置62以来所经过的时间。一对墙壁64和66限定了通道68并相应限制了单元的运动，它们用来更具体地限定可能位置区域60。

在另一种替换方案中，可类似地考虑此前确定的位置和从单元接收的惯性导航(inertial navigation)信息来确定可能位置区域。例如，单元可结合有计步器，其能够跟踪携带该单元的人的行进步数，或结合有里程表，其能够跟踪车轮行进的距离。此外，单元还可结合有指南针，其可相对于测量的行进距离提供行进的方向。作为替换，单元可包括一个或多个陀螺仪，其能够检测沿特定方向的运动和/或加速度。

在一些情况中，此前确定的位置可以是根据替换定位技术确定的位置，该替换技术可能在被跟踪单元所离开的区域中可用，而在被跟踪的单元正进入的区域中不可用。一个这样的例子可包括全球定位系统，其中相对于卫星或基站的网络对单元进行三角测量，而在单元进入建筑物后该定位技术不可用。相对于此前确定的位置可具有一定程度的确定性，由此能够确定和/或估计随后的可能位置区域。

图7示出基于已知的先前位置72和运动估计74的单元的可能位置区域70的部分空间概图，如上所述，其能够结合一些形式的惯性导航估计。运动估计74可以是单个距离和方向向量，并可以是平均值或集成的值。作为替换，运动估计74可包括多个不同的向量或分量74A-C，并对应多个相关联的方向。图7还示出惯性导航估计中不确定性的可能累积效果，以及它如何可产生可能位置区域70，从该区域可得出初始估计。

图8示出根据本发明的至少一个实施例确定多跳网络中多个单元的每一个的位置的系统100的框图。用于确定位置的系统100可结合到一个或多个待定位单元中，或者替代地，可位于另一个单元中，所述另一个单元经一个或多个跳跃(例如参考单元)至少可通信耦合至待定位单元。

系统100包括耦合到天线104的收发信机102，天线104用于促进与其他单元的通信，通过它可接收由单元中的每一个检测的测量范围信息以及用于确定可能位置区域的信息。收发信机102可以与许多形式的通信兼容，包括使用蜂窝电话无线电收发信机、无绳电话无线电收发信机、无线LAN连接、短程无线电收发信机(如蓝牙收发信机、红外通信收发信机)或其他类似通信设备的通信。本领域技术人员将认识到，其他形式的通信和/或它们的组合同样是可能的。

系统100还包括耦合到收发信机102的处理器106。处理器106包括存储区域108，用于接收和存储连接性和范围信息，并用于保持一个或多个位置估计及与位置估计110相关联的相应误差值。存储区域108还可包括一组或多组预存储的指令112。

处理器106还包括计算模块114，其适于确定单元中每一个的可能位置区域，以及基于一组初始位置估计来确定所述单元中每一个的位置估计并使得误差值最小化。处理器106还包括一个或多个选择模块116。在至少一个实施例中，处理器包括用于选择初始位置估计的选择模块118、用于选择最小化误差组的选择模块120。在一些实施例中，计算模块114和一个或多个选择模块116作为一组或多组预存储的指令112中的至少一些来实现。

在至少一个实施例中，处理器106可采用专用或通用计算机的形式，其包括一个或多个微处理器，用于执行一组或多组预存储的指令112。处理器还可包括一种或多种存储器和/或存储装置，其中一些可耦合到或结合在微处理器中，用于存储程序数据及所述一组或多组预存储的指令。不同类型存储器的例子包括一种或多种形式的易失性和/或非易失性存储器，包括常规ROM、EPROM、RAM或EEPROM。另外，不同类型的存储器可包括辅助存储器，如固定或可移动介质，包括磁盘或光盘驱动器。

图9示出根据本发明的至少一个实施例用于确定多个单元的位置的方法200的流程图。方法200通常包括测量各单元中的每一个和在通信范围之内的任何参考单元之间的范围信息(步骤202)。如上所述，这能够以至少几种不同的方式来实现。至少两个例子包括使用接收信号强度指示、到达测量的时间与到达测量的时间差。然后为各单元中的每一个建立可能位置区域(步骤204)。然后根据为各单元中的每一个建立的可能位置区域来为各单元中的每一个选择初始位置(步骤206)。然后对单元中的每一个进行位置估计并使误差值最小化(步骤208)。

在至少一些情况中，维持确定的位置估计以及对应的最小化误差值的记录。然后对是否已计算了期望数量的位置估计进行判定(步骤210)。在至少一些情况中，期望数量的位置估计可以是固定的预定数量。然而在其他情况中，期望数量的位置估计可以是其他因素的函数。例如，期望数量的位置估计可根据待定位各单元中每一个的一个或多个可能位置区域的大小而改变。

另外，已满足或超出的期望数量的位置估计可以根据已确定的最小误差值来确定。例如，如果已发现误差值低于预定阈值，则可以定义为已满足期望数量的位置估计。替代地，这可以表示为另一条件，可以替换地在达到所定义的预定数量的位置估计计算之前，中断循环并使方法流脱离该循环。此外，如果已超出减小的预定数量并且已发现小于预定阈值的误差值，则可以说已经计算的位置估计所期望数量已得到满足。本领域技术人员将认识到，在不脱离本领域技术人员的教导的情况下，其他替代方案是可能的。

在任何情况中，直到已经计算了期望数量的位置估计为止，才选择一组新的初始位置估计(步骤206)，并用来对各单元中的每一个确定位置估计(步骤208)，并且随后重复。在已经确定了期望数量的位置估计之后，和/或位置估计的计算已经在其他情况下中断，选择具有最小误差的这组位置估计(步骤212)。

在至少一个实施例中，误差估计是测量的范围信息和计算的估计位置之间的距离之间的差值的平方和的函数。在每个位置估计期间，使用迭代方法并试图使误差值最小化。

如前面至少结合图4至5所述，存在选择初始位置估计的至少几种可能性，包括接近确定的可能位置区域随机选择初始估计，相对于可能位置区域顺序选择间隔开的初始位置估计。在从间隔开的初始位置估计中顺序选择初始位置估计的情况下，位置估计通常可以是等间隔的，或替代地，它们可按相对于可能位置区域具有不同密度的预定模式排列。在一些情况中，初始位置估计在接近与最佳推测位置一致的区域处具有最大密度。

在另一实施例中，如图10所示，可通过借助于可能替代的位置确定手段来确定各单元中一些的位置而最小化需要确定位置的单元的数量。例如，如果在待定位各单元和足够数量的参考单元之间存在足够数量的范围估计，则可以通过三角测量来确定一个或多个单元的位置(步骤224)。另外，至少在三角测量保持有效的期间，通过三角测量来确定位置的任何单元又可以归类到或看作是参考单元(步骤226)。进而，这又可以允许通过替换的位置确定手段(如三角测量)来更确切地定位其他单元。可以重复该过程，直到没有其他单元能够以这种方式来定位(步骤228)。

另外可能的是，作为为了进行三角测量的定位过程的一部分，或与图9所提供的对多个单元进行定位的方法结合，通过增加功率并相应地增加单元之间的任何无线通信的范围，可以增强通信链路的数量和相应的范围测量(步骤222)。

通常，可在多种环境中与单元的定位结合来使用所述的方法200和系统100。至少一个这样的例子包括诸如蜂窝电话的设备或位于网络内的其他设备的定位。另外，系统100可用于跟踪存储在仓库中的物品的定位。

其他的例子包括结合待定位单元作为供在给定区域或环境中协同工作的一组或多组人使用的设备的一部分。一个这样的例子包括应急救险人员。在这种情况下，待定位单元可结合到或共同位于消防队员的头盔、护套或其他设备中。本领域技术人员将认识到，本发明用于对多个单元进行定位的方法和系统同样可适用于其他环境。

尽管示出并描述了本发明的优选实施例，但应该理解，本发明不限于此。本领域技术人员会作出大量的修改、改变、变型、替换和等效，而不脱离由所附权利要求限定的本发明的要旨和范围。