基站轨迹定位算法

winston

前言

我在哪？是LBS领域首先要解决的问题。因为技术限制，传统的GPS卫星定位只有室外的空旷地区才能够准确定位，对于室内环境来说，GPS定位往往会因“搜星”失败而无法定位。正因为GPS定位的天然缺陷，基于手机基站的定位技术正在蓬勃发展。然而因为基站的覆盖范围大，很难以取得高精度的效果，本文利用基站轨迹，提出了一个提高基站定位精度的方法。

关键字：基站定位，轨迹定位，Viterbi算法

绪论

对于单基站定位，如果仅根据用户当前的基站ID进行定位，精度必定有限。用户可能出现在基站覆盖范围内的任意一个地方，基站的覆盖范围越大，推测出来的用户位置就越不准。
如果我们还知道用户之前一段时间内经过的基站ID序列（称为基站轨迹），此时即可大致判定用户行动轨迹，可借此提高精度。
例举一个简单例子:

如上图所示，假设用户在一瞬间，基站ID从A切换到了B，此时用户属于B基站，单单从B这一个基站考虑的话，很难从其巨大的覆盖圆内取出精准位置。
但是从假设条件我们知道，用户之前一直是在A基站范围内，切换到B基站只是刚刚发生的事情，通过这个条件，人很容易就想到用户很大可能在两圆相交的位置（图中手机的位置）。当然，对于这种特殊情况来说，不光是人，程序也很容易去模拟，但是如果用户继续行走呢？比如一直走到B基站的右侧，还有算法可以继续推算吗？
本算法便是提出一种模型，用以解决此问题。

隐马尔可夫链模型(HMM)与Viterbi算法介绍

隐马尔可夫链作为一个常见的序列预测模型，其具体定义在这里就不细细展开了，有兴趣的用户可以到wiki上搜索相关资料。此模型已经在多个计算机场景中得到了成功的应用，比如拼音输入法中，我们输入”wo zai bai du da sha”，实际想输入的是“我在百度大厦”，也就是说其中有两个序列、一个是拼音字母序列（明序列），一个是汉字序列（隐序列）。两个序列之间有一定的相互关系，如何通过一个已知的“明序列”来推测另一个未知的“隐序列”便是隐马尔可夫链模型要解决的问题。本文的重点也是如何用隐马尔可夫链模型解决轨迹基站定位。

解决隐马尔可夫链问题中的一个著名算法是Viterbi算法。建议读者先去阅读wiki中的Viterbi算法介绍，里面有一个简单的天气的例子详细说明了该算法的大体过程。：

http://en.wikipedia.org/wiki/Viterbi_algorithm

算法细节隐马尔可夫链模型

我们知道隐马尔可夫链中有两个序列，一个是明序列（A1、A2、A3……），一个是隐序列（B1、B2、B3……）。在本模型之中，明序列（A1、A2、A3……）代表了用户经过的基站序列，隐序列是用户的实际位置序列。我们要做的是通过基站序列，来推测用户的实际位置序列。

首先，我们做如下假设：

● 用户行使在道路上。

●用户在匀速的行驶。

有了这两个假设，再把道路分解成一个一个的路段，我们便可以用路段序列来代替用户的位置序列。也就是说，我们需要通过观察到的用户基站序列，来推测用户的路段序列。如下图所示，我们观察到的是用户所经过的基站覆盖圆情况，需要求得的是用户的路段行驶轨迹。假设观察到基站轨迹是图中的绿色基站，那很明显用户最大可能是沿着红色箭头在行走。

Viterbi算法

如果要用Viterbi算法来解决本应用，只要知道如下几个问题即可。

路段的定义：将路网数据每隔10m抽象成一个有向线段，并且假设用户在这些路段之间离散的跳跃，每一个有向线段，即为一个路段。并且在这里假设用户将要跳跃到的路段只和当前路段相关，与过去的路段无关。

基站序列的定义：每秒钟检测其所处的基站，并且做记录。比如记录信息为（基站A、基站B、基站B、基站C），则表示用户在四秒钟的时间内分别属于基站ABBC三个基站，并且在B基站待了2秒。

路段序列定义：如果用户能够每秒钟记录其所属的路段，这个序列便是路段序列，这是用户的真实位置序列。

路段从属于基站的概率：Viterbi算法中需要知道隐状态从属于明状态的概率，拿到本应用中来看，便是要知道路段从属于基站的概率。解决此问题有如下两个方法：

1.根据路段在基站覆盖圆的具体位置来调整概率，比如，距离基站覆盖圆中心越近，则从属于此基站的概率越大。

2.根据真实的用户数据来推算概率。此方法最准确，其原理也简单，根据用户的真实位置（GPS点）变可以知道用户处于的哪个路段，也就知道了这个路段曾经属于过哪些基站，以及其概率。

如果有用户的真实数据，那么采用方案2无疑是最好的，但是没有数据的情况下，用方案1也可以最大可能的模拟。

路段之间的转移概率：路段之间的转移概率是本算法的重点，在这里做如下定义：假设路段A指向了路段B和C，那么从路段A转移到B和C的概率分别是33%，也就是概率等分，请注意路段A能转移到自身，其到自身的概率也是33%。

Viterbi算法大体过程

Viterbi算法过程是在各个路段之间进行概率转移。如下图所示，用户的基站序列为ABBC,则需要进行三(n-1)次概率转移过程。

对于基站序列ABBC来说，需要分成以下几步：

1.求得每一个路段的初始概率，即各个路段属于基站A的概率。

2.进行第一次转移，从基站A到基站B。比如路段A转移到路段B的概率为：路段A的概率×两个路段的转移概率×路段B属于基站的概率。

3.重复过程2，再转移两次，分别为 基站Bà基站B  基站Bà基站C。

4.最后取出概率最大的路段即为用户位置。

有心的读者可能已经看到，路段之间转移概率的定义是一个路段只能转移与其相连接的路段，这样有一个问题便是，按照上述算法可能所有路段的最终概率均为0。这是因为我们假设在时间间隔内，用户只能从一个路段行驶到相邻的路段，然而实际情况下，用户的速度可能较快，在我们扫描基站的间隔内，用户能跨越多个路段。对于这个问题，我们需要根据用户的速度来对用户扫描到的基站序列进行修复，比如速度是我们假定速度两倍的用户可以将基站序列ABBC变换成AABBBBCC。用户的速度可以通过速度传感器或者基站轨迹进行大概的推算，比如用户经过了10个基站，将这10个基站的覆盖圆中心连接起来，用总长除以时间，即为大概的速度。

算法效果

作者在实现本算法之后，对于匀速运动的定位用户的定位精度提升了一倍之多。对于一些特定用户，更是能明显的起到优化作用，比如高速公路上的用户，基站覆盖半径大，没有用本算法的话，只能返回巨大基站覆盖圆的中心给用户，定位精度极差。采用本算法之后定位精度会得到极大的提高，甚至用户的定位点丝毫不差的跟随用户的真实走动而走动，这也是因为在高速公路上路网比较简单，此算法效果会更突出。

by gaoyunxiang