无线系统中目标装置定位的新取样点决定方法

摘要

本发明公开一种在无线系统中目标装置定位的新取样点决定方法。在训练时期，当获知目标装置所在位置无线信号的观察值分布后，本发明分析该位置无线信号观察值的概率分布的不确定度，以及与其邻近观察位置的无线信号观察值概率分布之间的差异度，以决定该位置是否为新取样点或为重新校准点的候选者。本发明与判定规则全然无关，也不存在因判定规则选择不当而衍生的问题；并且，本发明提供从一个位置到另一个位置的错误预测代价机制，从而可以解决边界在线的取样点具备双重角色属性所衍生的问题。

说明书

技术领域

本发明涉及无线环境下的定位系统，尤其涉及无线系统(wirelesssystem)中目标装置定位(location determination)的新取样点(new samplepoints)决定方法。

背景技术

为了估计目标装置(target device)的位置，一个定位系统需要测量一个量值(quantity)，该量值至少是距离的函数(function of distance)。而该量值可以是无线接入点(access point，AP)所发射的信号强度(signalstrength)，在开放空间(free space)会随距离以log函数形式衰减(logarithmically decay)。定位技术以所接收到的无线信号(received radiosignal)在所述目标装置上的观察值(observation)为基础。通常，在某位置的观察值形成一个概率模型(probabilistic model)，且该概率模型描述了所接收到无线信号的分布情形。

在每个取样点(sample point，SP)观察信号的分布基本上与其邻近点的无线信号接近。为了建立每个取样点的概率模型，一般需要从每个取样点去收集无线数据(radio data)。然而，大多数环境里取样点的总数目很大，使得从每个取样点去执行无线数据收集就变得很难。所以，通常会仅选取一些取样点去执行实际测量(physical measurement)，然后再由模拟(simulation)或理论计算(theoretical calculation)来得到其它取样点的概率分布。例如，以所述实际测量值为基础，然后通过内插(interpolation)或外插(extrapolation)来得到其它取样点的概率分布。这样，所产生的概率模型会与无线数据被收集的多少(how many)和地点(where)相关。

无线定位系统通常以两阶段来处理，一为训练阶段(training phase)，另一为追踪定位阶段(location determining phase)。训练阶段是一离线(offline)阶段，系统在此阶段会撷取无线接入点在各所属区域里某些点(certain cells)的签署凭证(signature)，去收集并分析信号样式(pattern)，以少量取样点来推测整个空间的对应图(map)，也就是熟知的无线地图(radio map)。

在追踪定位阶段，目标装置利用所收到无线接入点的信号强度向量与该无线地图对照，然后找出最佳匹配(match)，例如距离最近的候选者(nearest candidate)，作为目标装置的估计位置。

世界专利申请公开案WO03/102620的文献，公开了一种目标装置预测位置(predicted location)的误差估计(error estimate)决定方法。该方法根据一个概率模型和收集(collecting)信号观察值来决定目标装置的位置。图1为该误差估计决定方法的流程图。参照图1，首先，决定目标装置在某特定观察值的后验概率分布(posterior location probabilitydistribution)，如标记101所示；然后，决定目标装置在该观察值下，真实位置与预测位置之间的误差距离函数(error distance function)，如标记103所示；接着，将该后验概率分布乘以该距离函数，并将该乘积(product)累加至误差估计，如标记105所示；并且，在该定位系统运行的实际区域(physical area where the positioning system is operating)重复上述步骤，如标记107所示。

上述误差距离估计是以定位系统在其实际运行区域中目标装置所在的取样点与预测位置之间错误距离的期望值来决定。该误差距离估计可用来决定是否增加新取样点(new sample point)，或决定是否重新校准(recalibrated)现有取样点(existing sample point)。而该错误距离期望值最大的点就是需要被取样的取样点。

对于该估计位置每个不同的观察值，所述错误距离期望值会有所不同。因此，该误差距离估计很难给予新取样点良好(good)、客观(objective)、或有效(effective)的建议，除非将其对应的最佳化判定规则(optimal decision rule)一同纳入考虑。然而，如果采用随机数对应(random mapping)的判定规则，则要从接收到的信号去分辨不同位置的能力，则将不适合采用该错误距离期望值，因为该期望值与应用观测到的无线信号来选取取样点无关。

甚至，在位置估测中，当同时(concurrently)考虑多种不同环境下的定位模型时，采用不同模型的取样点间距大小(grid size)可能不一致(inconsistent)。所以，当用该误差距离估计来推荐潜在的位置(potentiallocation)时，错误距离期望值的判定规则会偏向选择取样点间距大的取样点，而忽略取样点间距小的取样点。

如果选择候选者是限定在单一定位模型时，在边界线(border line)上的取样点若属于取样点间距大的区域则始终会被忽略，但若该取样点归属于取样点间距小的区域则始终会被选上。这是因为边界在线的取样点具备双重角色(double-role)的属性(attribute)。

降低实际测量取样点的数目已成为无线定位系统中各中技术的差异重点之一。然而，如果训练完后，发现系统定位效果不好，就必须增加或校准(calibrate)取样点。

发明内容

有鉴于此，本发明目的在于提供一种无线系统中目标装置定位的新取样点决定方法，其不存在因判定规则选择不当而衍生的问题，同时还可解决边界在线的取样点具备双重角色属性所衍生的问题。

为了达到上述目的，本发明提供一种无线系统中目标装置定位的新取样点决定方法。该方法原理简述如下：当获知目标装置的无线信号的位置观察值后，在训练期间，以该观察值分布的本质为基础，计算出该位置的无线信号本身的稳定度(stability)，并计算其与其它观察位置的无线信号观察值概率分布之间的差异度(difference)，以决定该位置是否为新取样点、或为重新校准点的候选者。

当收到某观察位置的无线信号后，该无线信号的稳定度可以用该信号所形成的概率分布的不确定度(uncertainty)来描述。而两个位置间无线信号概率分布的差异度可以用各观察值的概率代入差异函数后所有差异的平均(average of a difference function)来求得，且该差异函数可以是两数值相减后的绝对值、或两数值的对数值差(logarithmic difference)、或其它相似的函数。当考虑不同位置错误预测(error prediction)的代价(penalty)时，可以将权重(weight)或代价函数与两位置间的信号分布的差异度组合在一起考虑。

对于上述本发明所提供一种无线系统中目标装置定位的新取样点决定方法，其可包括下列几个主要的步骤。首先，计算出在某位置所接收到无线信号本身的稳定度。然后，计算出该位置与其它邻近观察位置无线信号概率分布的差异度(distribution difference)，并决定该位置与其它邻近观察位置的无线信号概率分布之间的代价。接着，计算出该位置的校准指标(calibration index)。重复上述过程于该无线系统运行的实际区域内所有位置。

对于上述无线系统中目标装置定位的新取样点决定方法，优选地，该方法根据所述多个位置计算出的多个指标，决定出新取样点的一个或多个候选者。

对于上述无线系统中目标装置定位的新取样点决定方法，优选地，所述位置q的稳定度以所述无线信号在所述位置q形成的概率分布P(O|q)不确定度来描述，其中O代表在该位置q所接收到无线信号所有可能的被观察输出值。

对于上述无线系统中目标装置定位的新取样点决定方法，优选地，所述位置q的无线信号的概率分布的差异度为该位置q的概率分布函数P(O|q)与不同于q的位置的概率分布函数之间的长度函数。

对于上述无线系统中目标装置定位的新取样点决定方法，优选地，所述长度函数为距离函数。

对于上述无线系统中目标装置定位的新取样点决定方法，优选地，所述位置q的稳定度以资熵来测量。

对于上述无线系统中目标装置定位的新取样点决定方法，优选地，所述位置q的校准指标I(q)为下列三者的函数，在该位置q接收到无线信号的稳定度、该位置q无线信号观察值概率分布与其邻近观察位置无线信号观察值概率分布之间的差异度、以及从该位置q到另一位置的错误预测代价。

对于上述无线系统中目标装置定位的新取样点决定方法，优选地，该方法还包括下列步骤：提供一种从该位置q到另一个位置的错误预测的代价机制。

对于上述无线系统中目标装置定位的新取样点决定方法，优选地，所述错误预测的代价机制由所述位置q与之间的差异度函数和参数λ来决定。

对于上述无线系统中目标装置定位的新取样点决定方法，优选地，所述参数λ的值是可变的。

本发明具有如下有益效果：首先，本发明与判定规则全然无关，也不存在因判定规则选择不当而衍生的问题。其次，本发明提供了从一个位置到另一个位置的错误预测代价机制，可以解决边界在线的取样点具备双重角色属性所衍生的问题。

下面将参照附图并结合具体实施例详细介绍本发明，以进一步揭示上述及其它本发明的目的和优点。

附图说明

图1为现有技术中目标装置预测位置的误差估计决定方法流程图；

图2为四个不同位置所接收到无线信号分别对应的概率分布函数；

图3为本发明无线系统中目标装置定位的新取样点决定方法流程图；

图4为本发明如何应用不同的λ值于边界在线不同区域的示例图；

图5A为本发明在训练阶段中四个样本点SP1-SP4的概率分布；

图5B为本发明中四个样本点SP1-SP4之间相互距离的示例；

图5C为本发明中四个样本点SP1-SP4的熵值的示例；

图5D为本发明中以Kullback-Leibler距离为例计算出四个样本点SP1-SP4的概率分布两两之间的差异度；

图5E为本发明中四个样本点SP1-SP4的校准指标的示例。

并且，上述附图中主要的各附图标记说明如下：

101表示步骤以决定目标装置在某特定信号下位置的后验概率分布；

103表示步骤以决定目标装置真实位置与预测位置之间的误差距离函数；

105表示步骤以将该后验概率分布乘以该误差距离函数，并将该乘积累加至误差估计；

107表示步骤以在该定位系统运行的实际区域重复上述步骤；

SP1-SP4表示四个样本点；

PDF1-PDF4表示四个样本点SP1-SP4所接收到无线信号对应的概率分布函数；

o_t表示目标装置在时间t的观察值变量，且P(o_t＝m_t|q_t＝s_t)表示目标装置在位置s_t的观察值为m_t的概率；

301表示步骤以计算出在某位置所接收的无线信号本身的稳定度；

302表示步骤以计算出该位置与它邻近区域内其它位置的无线信号的概率分布的差异度，并决定该位置与它邻近区域内其它位置的无线信号的概率分布之间的代价；

303表示步骤以计算出该位置的校准指标；

304表示步骤以重复上述过程于该无线系统运行的实际区域内所有位置；

401表示禁止区。

具体实施方式

本发明是在无线定位系统中训练阶段期间来决定目标装置定位的新取样点，并且是以目标装置所接收到无线信号的观察值(observation atlocation)为基础。目标装置在某位置所报告的观察值形成了一种概率分布(probability distribution)，并且是一种条件概率的形式。换句话说，条件概率P(o_t＝m_t|q_t＝s_t)是指目标装置在位置s_t的观察值为m_t的概率，而o_t表示目标装置在时间t的观察值变量(observation variable)。

在不同位置所接收到的无线信号，其相对应的概率分布是彼此无关的(independent)。如图2所示，在四个不同位置(例如，四个样本点SP1-SP4)所接收到无线信号，其相对应的四个概率分布函数PDF1-PDF4是彼此无关的。通常，还存在着需要大幅校准取样点的情形，不稳定的区域(例如存在大障碍物的地区)可以用精确概率分布的取样点来遮盖。

为了找出新取样点的潜在候选者(potential candidate)，本发明决定新取样点的方法是在训练阶段期间，以观察值分布(observationdistribution)的本质(intrinsic property)为基础来选取新取样点。因此其与判定规则全然无关，也不存在因判定规则选择不当而衍生的问题。

在收到某观察位置在时间t的无线信号o_t分布后，本发明计算该位置无线信号的稳定度，以及与其它观察位置的无线信号观察值概率分布之间的差异度，来决定该位置是否为新取样点。图3示出了本发明无线系统中目标装置定位的新取样点决定方法的主要流程。

参照图3，首先，计算出在某位置所接收到无线信号本身的稳定度，如步骤301所示。然后，计算出该位置与它邻近区域内其它观测位置的无线信号的概率分布的差异度，并决定该位置与它邻近区域内其它位置无线信号的概率分布之间的代价，如步骤302所示。接着，计算出该位置的校准指标，如步骤303所示。并且，重复上述过程于该无线系统运行的实际区域内所有位置，如步骤304所示。

有了所有位置的校准指标后，根据该无线系统运行的实际区域的环境状况，就可推荐新的校准点(calibration point)。以下进一步说明该四个步骤301-304的具体运行。

在步骤301中，无线信号本身在位置q的稳定度可以用此信号在此位置q所形成的概率分布P(O|q)的不确定度来描述，其中O表示在该位置接收到的无线信号所有可能的被观察输出值(observed output)。测量该不确定度的方法有多种，例如可使用Shannon的资熵(information entropy)，且该资熵定义如下：

当概率分布P(O|q)为离散(discrete)概率分布时，

$H(O/q)=-\underset{o_i\in O}{\Sigma }p\left(o_i\right|q){\log }_{2}p\left(o_i\right|q)---\left(1\right)$

而当概率分布P(O|q)为连续(continuous)概率分布时，

$H\left(O\right|q)=-\underset{O}{\int }p\left(o\right|q){\log }_{2}p\left(o\right|q)\mathrm{do}---\left(2\right)$

在步骤302中，无线信号的两个概率分布P(O|q)与之间的差异度可以由两个函数的长度(norm)得到。该长度可采用L_p-norm、或采用sup norm、或采用每个可能观察值的差异度函数(difference function)的平均(average)。而差异度函数可为对数差异度(logarithmic difference)、或为每个共同观察值(common observation)的两个概率分布之差的绝对值、或为雷同者。其中，优选实施例可使用Kullback-Leibler距离，该距离定义如下：

当概率分布的型态为一离散概率分布时，

$D_{\mathrm{KL}}\left(P\left(O\right|q)\right|\left|P\left(O\right|\tilde{q})\right)=\underset{o_i\in O}{\Sigma }p\left(o_i\right|q){\log }_2\left(\frac{p\left(o_i\right|q)}{p\left(o_i\right|\tilde{q})}\right)---\left(3\right)$

而当概率分布的型态为一连续概率分布时，

$D_{\mathrm{KL}}\left(P\left(O\right|q)\right|\left|P\left(O\right|\tilde{q})\right)=\underset{O}{\int }p\left(o\right|q){\log }_2\left(\frac{p\left(o\right|q)}{p\left(o\right|\tilde{q})}\right)\mathrm{do}---\left(4\right)$

该Kullback-Leibler距离不是负值，且不是可交换的(commutative)；也就是说，概率分布P(O|q)与之间的Kullback-Leibler距离不等于概率分布与P(O|q)之间的Kullback-Leibler距离。并且，当且仅当$P\left(O\right|q)=P\left(O\right|\tilde{q})$时，两个概率分布P(O|q)与之间的Kullback-Leibler距离为0。值得注意的是，在某特定位置的所有可能观察值都具有正值的概率(strictly positive probability)，因此在计算两个概率分布P(O|q)与之间的差异度时，不会有零概率的情形。

在步骤303中，值得一提的是，本发明提供一种从一个位置q到另一个位置的错误预测的代价(penalty of error prediction)机制。该错误预测的代价机制可以由两位置q与之间的差异度函数和一个权重参数λ来决定，且该参数λ可由服务供应商(service provider)视实际环境的需求而设定。

上述错误预测的代价机制的计算方法示例之一如下：

$w(q,\tilde{q})=1-e^{-\mathrm{\lambda d}(q,\tilde{q})},$

其中，是两位置q与之间的距离函数，且根据不同区域或精确度的实际需求可采用不同的λ值。

在边界在线不同的区域采用不同的λ值，如此可轻易解决在边界在线的不同区域具有双重角色属性的问题。

在某些区域有不同的错误代价(different error penalties)的例子有多种。例如，某些区域是小孩的禁止区(restricted area)。所以，如果将目标装置错估为在禁止区之外，而实际上应该是在禁止区之内的话，那么就必须给予重的(heavy)错误预测代价。在位置q的邻近区域们给予不同的λ值，可以适应实际环境的需求。图4为本发明中如何应用不同的λ值于边界在先不同区域的示例图。

如图4所示，在禁止区401中，假设目标装置的位置为SP，则其邻近取样点有SP1至SP6，其中SP1在禁止区401的外部。所以，如果该目标装置是禁止进入401之内的话，那么如果将目标装置错估为在SP1而实际上应该是在SP的话，则必须给予较重的(heavier)错误预测代价。换句话说，从SP至SP1的错误预测代价采用的权重参数λ₁的值重于从SP至SP2或SP3或SP4或SP5或SP6的错误预测代价采用的权重参数λ的值。

在步骤303中，位置q的校准指标I(q)为下列三者的函数：在待测位置接收到无线信号的稳定度、待测位置的无线信号观察值概率分布与其邻近观察位置的无线信号观察值概率分布之间的差异度、以及从位置q到另一个位置的错误预测的代价。该位置q的校准指标I(q)的计算方法示例之一如下：

$I\left(q\right)=\frac{1}{H_{\max }-H\left(O\right|q)+ϵ}+\underset{\tilde{q}}{\Sigma }\frac{w(q,\tilde{q})}{(D_{\mathrm{KL}}\left(P\left(O\right|q)\right|\left|P\left(O\right|\tilde{q})\right)+D_{\mathrm{KL}}\left(P\left(O\right|\tilde{q})\right|\left|P\left(O\right|q)\right))/2+ϵ}---\left(5\right)$

其中，H_max是接收到无线信号在位置q的最大资熵，该最大资熵可利用均匀分配来获得；而ε是防止分母为0的一个常数且其值很小。

在步骤304中，对于该无线系统运行的实际区域内所有位置，重复上述步骤301至303。如此，就可得到目标装置在所有位置的校准指标。根据这些校准指标，就可决定出新取样点的一个或多个候选者。并且，候选者的多少可根据实际环境的需求来选取。

值得一提的是，由于本发明以观察值分布的本质为基础，所以与判定规则全然无关，也不存在因判定规则选择不当而衍生的问题。

以下以图5A至图5E所示的工作示例，详细说明本发明如何来决定新取样点。图5A是在训练阶段期间四个样本点SP1-SP4的观测信号概率分布。图5B是在该四个样本点SP1-SP4之间的相互距离(mutualdistance)，其中单位设定为1公尺。图5C是在该四个样本点SP1-SP4位置，利用公式(1)计算所得的熵值(entropy value)。

图5D是以Kullback-Leibler距离为例，利用公式(4)计算所得该四个样本点SP1-SP4概率分布两两之间的差异度。如前所述，在图5D中，概率分布P(O|SP1)与P(O|SP2)之间差异度D_KL(P(O|SP1)||P(O|SP2))＝2.2189不等于P(O|SP2)与P(O|SP1)之间差异度D_KL(P(O|SP2)||P(O|SP1))＝1.5361。并且，图5D中的错误预测代价机制的λ值被假设为1。

图5E是以公式(5)为例，计算所得在四个样本点SP1-SP4的校准指标，其中ε值设定为10^-5。从图5E的结果可以看出：SP3的校准指标值为7.2237，是四个样本点SP1-SP4中最高的；其次为SP2，其校准指标值为7.0251；且两者都远高于样本点SP1与SP4。换句话说，被推荐的新校准点是SP3、或SP3与SP2，具体推荐需视环境需求状况而定。

综上所述，本发明在训练阶段，当获知目标装置的无线信号后，计算该位置的无线信号的稳定度，以及与其它观察点的无线信号观察值概率分布之间的差异度，进而计算出在所有可能位置的校准指标，以决定该位置是否为新取样点或新校准点。本发明以观察值分布的本质为基础，因此与判定规则全然无关，也没有因判定规则选择不当而衍生的问题。并且，本发明提供从一个位置到另一个位置的错误预测代价机制，还可以解决边界在线的取样点具备双重角色属性所衍生的问题。

需要声明的是，上述介绍仅为本发明最佳实施例而已，并不能据此限定本发明的实施范围。也即，凡在本发明权利要求书范围内所作的等同变化与修饰，均涵盖于本发明专利保护范围之内