Chan-定位算法

Chan定位算法Chan算法是TDOA定位方法的一个很赞的trick。但是很多方法一旦从学术的角度去看，就罩上了奇异的光环。TDOA，thetimedifferncesofarrival，到达时间差。Chan算法1是非递归双曲线方程组解法，具有解析表达式解。其主要的特点为在测量误差服从理想高斯分布时，它的定位精度高、计算量小，并且可以通过增加基站数量来提高算法精度。该算法的推导的前提是基于测量误差为零均值高斯随机变量，对于实际环境中误差较大的测量值，比如在有非视距误差的环境下，该算法的性能会有显著下降。Chan算法在考虑二维的情况下，可分为只有三个BS参与定位和三个以上BS定位两种。一、3个基站移动台，简称tag，自身发射信号；固定基站，简称anchor，接收来自tag的无线信号。BS1等基站的坐标已知，为、、。假设第个基站位置为。移动台的位置是未知的，设为。此时设BS1为固定站，因此距离差都是以BS1为基准。根据几何关系我们定义以下要用的关系表达式：根据另外有如下关系：根据另外有如下关系：将代入，则有:在这里是关键一步：消除了未知数的平方项，仅保留一次项，得到了一系列的线性方程组。比如当时，有如下表达式：分析，首先要明确，，已知，未知项有，，。首先假设是已知的。则可以视作线性方程组求解。因为是二元一次方程组，因此可以直接利用消元法来求解。首先可以通过移项化简为：再简记为：在这里可以视为，即。可以利用矩阵的逆即，也可以利用如下的行列式除法。昀后求得：其中，。将，代入可得：对于进一步处理得：其中，我们令：利用我们就可以将表示为如下非常简洁的形式：其中，只有是未知的。因此要想求出MS的坐标，由式可知，首先要求出。接下来我们将式代入到式，可以化为如下形式：式是以的一元二次方程。求解式可得的两个根，根据先验信息可以舍去一个无效的根，将有效的代回到式(13)可求可求出MS的估计坐标。二、多个基站Chan算法是基于双曲线交点的定位方法，闭合解/解析解，小范围和大范围的定位系统都适用。当TDOA估计误差较小时，可以认为是ML（昀大似然法）的一种近似方法。当基站的数量大于3时，TDOA值得到的非线性方程组个数要多于未知变量的个数。采用加权昀小二乘法(WLS)来充分利用冗余的数据，Chan算法能获得更加好的MS位置估计值。此时先将初始非线性TDOA方程组转换为线性方程组，然后采用WLS得到初始解，再利用第一次得到的估计坐标及附加变量等已知约束条件进行第二次WLS估计，从而得到改进的估计坐标。2.1问题建模%求解一元二次方程symsr;r0=solve(a*r^2+b*r+c);%默认eqx=0%selecttheture'r0',thensolvethex&y.当有更多的anchor时，线性方程组便是超定的。由于测量噪声的存在，方程组的解不可能完全满足其中的所有方程，所以合适的解只能是匹配这些方程组的昀佳解。令，在这里先不考虑，，三者之间的关系，即假设三者线性无关。建立存在TDOA噪声的线性方程组，将式转变成矩阵形式如下：在这里，考虑存在TDOA观测噪声时即（），误差向量为2.2关于最小二乘法为保证参数估计量具有良好的性质，通常对模型提出若干基本假设。实际这些假设与所采用的估计方法紧密相关。估计方法有多种，其中使用昀广泛的是普通昀小二乘法（ordinaryleastsquares,OLS）。线性回归模型为，模型的基本假设有：假设1、解释变量是确定性变量，不是随机变量；假设2、随机误差项具有零均值、同方差和不相关性：假设3、随机误差项与解释变量之间不相关：假设4、服从零均值、同方差、零协方差的正态分布：需要注意的是，如果假设1、2满足，则假设3也满足；如果假设4满足，则假设2也满足。估计参数时，必须检验基本假定是否满足，并针对基本假定不满足的情况，采取相应的补救措施或者新的方法。不满足基本假设，高斯-马尔科夫定理2失效。高斯-马尔可夫定理表示为：当出现异方差，即，不满足上述定理时，OLS估计量虽具有无偏性，但不具有有效性3。因此采用加权昀小二乘法，对原OLS模型进行改进，使之成为一个新的不存在异方差的模型，再利用OLS解决。2.3加权最小二乘法我们需要先了解一下加权昀小二乘法(WLS)。所谓昀小二乘法，广泛用于数据拟合的求解方法，优化思路是使得估计误差（residual,）的平方和昀小化。加权昀小二乘法考虑到某些观测值具有更高的权重（如误差小），则问题转化为。其中是权重。昀普通的昀小二乘法的回归模型，满足上述的高斯-马尔可夫定理时，即可通过对求导4，得到其估计值：当残差项的方差5不再是已知的，且不再是互不相关的，即，。用WLS改进原模型，使之不存在异方差即，因此有：加权昀小二乘法，就是对上述的取一种特殊的矩阵：对角阵，而这个对角阵的对角元都是常数，也就是权重的倒数，如下：权重的选取原则是：对于较大的残差平方赋予较小的权重，反之赋予较大的权重。令表示权重矩阵。令的每个元素都开平方根作为新的矩阵，有。在这里特别注意，回归模型已经改变6，则新的模型以及式中的残差变为：其中，是未知的。首先要解决未知的。在论文1中，，符号是Hadamard乘积7。的推导原理见附录8。再看式中的，注意是时延误差，的均值为，协方差矩阵是。为信号的传播速度。实际情况下又满足，因此可以忽略式中的第二项，则误差变为高斯随机向量。由于服从零均值高斯随机分布，我们将和联系起来，则可以得到：在这里假设共有个BS，误差的协方差矩阵9为：其中，因此，10。因为中有MS到BS的距离，在计算时是未知的。如果基站与源很远很远，可以合理地认为都接近于同一个常数即假设，则。论文1提示由于的的缩放不影响其结果6，我们可以得到的近似：如果基站与源较近，可以利用求得的代入式重新估计，继而得到，再代入式便可以得到在忽略元素间约束关系下的估计结果。这里求得的是在假定的各元素独立的情况下进行的，而实际上中是与有关的量，用近似地代替误差矢量的协方差矩阵会带来一定的误差。为了得到更精确的定位结果，可以接着进行第二次WLS估计。注意到与始终约束到式，那么，能否利用这个关系，更进一步的提高估计精度？假设在有噪声的情况下，当TDOA的测量噪声足够小的时候，向量是一个随机向量，其均值为groundtruth，它的元素表示如下：这里特别的处理是从向量的前两个元素中分别减去和（anchor1的坐标），再对向量的元素进行平方运算，见如下公式：从式可以看出，新的误差矢量表明了向量的不准确性。将式代入式，则有：当式中的较小时，近似成立。现在忽略掉平方项，只考虑近似后的矢量，和前面的处理过程类似，比较容易推出：其中，。这样得到了的近似的协方差矩阵。误差为高斯随机向量，因此同样可以采用的方法进行估计：注意到式的未知，首先计算估计的协方差矩阵，采用一阶扰动方法计算和保留线性扰动分量，找到式中的。注意式中的、都包含随机变量，则。由于式满足，则式的可以重写为：式记为，根据公式有：保留一阶扰动分量，并略去高阶扰动量。结合公式和公式，利用式得到和的协方差矩阵的表达式：需要明确一个问题，在式的推导中，期望和（协）方差矩阵一旦计算出来便可以视作常量矩阵，因此可以提出来作为系数因子。式中的、、都是常量矩阵。回到式，协方差矩阵中包含了，我们发现里面包含了未知的groundtruth。因此不能利用式直接计算，同理利用上一次WLS的式的结果去近似计算。另外通过式得到了的表达式，其中未知的我们可以用式的近似。考虑源距离很远的条件下，即，。式近似为。于是式近似为：注意矩阵是常量。在这里，我们顺便考虑一下的协方差矩阵。通过计算以及的期望，结合公式和公式进一步可得：综上，昀终可以得到估计的位置坐标，根据公式可以推出：在中得到了两个解，解的模糊性可根据有关MS的先验信息进行消除。接下来为了找到的协方差，我们考虑以下的误差表示。根据中的表示，考虑和groundtruth之间的误差：并利用前文、、及所推导的关系，的协方差公式为：2.4总结以上两次WLS计算都假定TDOA测量误差服从零均值的高斯分布,在这一前提下,能得到对MS位置的昀大似然(ML)估计,否则定位误差将会显著增大。接下来我们把以上推导过的思路按照两种情况总结如下。1.远距离节点的定位公式2.近距离节点的定位公式三、克拉美罗界一些研究领域（如无线定位方向）都会碰到参数估计的问题，这时常常会看到克拉美罗界(Cramér–Raobound)这个东西。在参数估计和统计中，Cramer-Rao界限（Cramer-Raobound,CRB）或者Cramer-Rao下界（CRLB），表示一个确定性参数的估计的方差下界。命名是为了纪念HaraldCramer和CalyampudiRadhakrishnaRao。这个界限也称为Cramer-Rao不等式或信息不等式。3.1参数估计问题一个简单的例子：一个物理量为，我们使用某种方式去观测它，得到的是观测值为，由于存在噪声，得到的观测值不是真实值即。其中假设。这种情况下我们可以直接用观测值去估计，这样就必然会存在估计误差，直观地理解就是噪声的方差越大，估计就可能越不准确。3.2CRB的来龙去脉讨论克拉美罗界就是为了使用这个标准来衡量无偏估计量的性能。通俗讲，CRLB可以用于计算无偏估计中能够获得的最佳估计精度，因此经常用于计算理论能达到的昀佳估计精度，和评估参数估计方法的性能（是否接近CRLB下界）。采用上面的方式，用去估计，估计值会在真实值附近波动。克拉美罗界不关心具体的估计方式，只是去反映利用已有信息所能估计参数的最好效果。比如上面的例子中当我们观察到的时候，我们可以得到的概率密度函数PDF是以为均值，以为方差的正态分布：当观测到的时候，则式就转化为的PDF：假设方差不同的PDF如下图所示：函数图像越尖的话，代表估计精度可以越高。尖锐程度可以用表示。方差可以描述尖锐程度，但方差只给出了一个估计量的信息，如何找到一种对估计精度更好的描述，从而可以反映整个估计问题的信息（所有可能的估计量）？答案就是似然函数的二阶导数。事实上，式是一个似然函数，取对数并求导可得：由式继而得到估计量的方差：不失一般性地考虑，如果结果依赖于多个观测值数据以及参数，则需要求二阶导数（曲率）更一般的度量即期望。这个期望就是费雪信息（Fisher）：式中的期望都是对于计算的。在这里我们对上面公式进行详细的说明：正则化条件（似然函数的值应该取到昀大值，故令似然函数的一阶导数为0）MLE的方程的方差因此，假设是一个位置确定性参数,我们需要从观察变量估计它。而它们满足一个概率密度函数。任何的无偏估计的方差的下界为Fisher信息的倒数：其中，右侧的表达式就是CRLB，它是参数的函数。无线定位方法常采用理论下界CRLB与定位解的均方根误差进行比较，来判断定位估计器的准确率。四、MATLAB仿真该部分根据第大二节的内容总结，实现其代码。首先，我们来看Chan算法，将其作为一个函数来实现。根据公式我们需要首先设置好各个基站的坐标，以及到达时间差，假定基站的个数BSN的范围是：3BSN7。Chan函数主要包括两部分：第一次WLS；第二次WLS。其中参数需要有BS坐标以及到达时间差。因为设置的BS的数目可能有所不同，因此为了方便从坐标矩阵中取出特定的点，我们还需要一个BSN作为参数。第一次WLS：第二次WLS的代码实现：%基站数目BSN=4;%各个基站的位置，2*BSN的矩阵存储，每一列是一个坐标。BS=[0,sqrt(3),0.5*sqrt(3),-0.5*sqrt(3),-sqrt(3),-0.5*sqrt(3),0.5*sqrt(3);0,0,1.5,1.5,0,-1.5,-1.5];BS=BS(:,1:BSN);BS=BS.*50;%噪声方差Noise=1;%R=R_{i,1},是加上了噪声后，BSi与BS1到MS的距离差，实际中应由TDOA*c算得fori=1:BSN-1R(i)=R0(i+1)-R0(1)+Noise*randn(1);end%Zp为估计的坐标functionZp=myChan