一种提高室内定位精度的算法

引言

室内定位技术是物联网感知层的基础支撑技术，因其可以提供室内物品的与位置相关的信息，赢得了广大学者的关注和研究。同时随着物联网相关概念的推广，室内物品的联网与定位开始提出了新的需求与挑战，即更加便捷的部署方式、更高精度的定位信息。采用室内定位系统，可以实现室内物品的实时在线、远程监管，使得物联网从理论概念走到现实世界中。

完整的室内定位系统一般包括室内定位技术、室内定位算法、数据管理软件和硬件设备等。其中定位算法是核心,定位算法的精度是决定系统实施与应用的关键。根据定位过程中是否测量实际节点间的距离，把算法分为：基于距离的(Range-Based)算法和距离无关的(Range-Free)算法。距离无关的定位机制只利用节点间的连通性来估测自身的位置，用最优化方法来提高定位精度，比较经典的算法如凸规划算法和MDS-MAP算法，但整体的精度没有基于距离的定位算法高，虽然有些算法利用了循环方式来提高精度，然而应用的范围远不及前者。因而基于距离的定位机制，因具有高精度、部署方便和组网灵活的特点，备受研究者们的关注。

本文研究重点是基于距离的室内定位算法。根据定位算法原理，定位精度主要受两个因素影响:距离测算与坐标计算。本工作建立基于距离的坐标估计、计算模型，采用数值分析理论对距离进行误差补偿，利用运筹学方法对初步定位结果做进一步的求精，并通过模拟实验验证算法精度。

1模型建立与求解

提高基于距离的室内定位算法精度存在两个难点：距离数据的处理和坐标值的推导，本节所述模型将通过以下4个步骤完成对原始距离值的统计、还原，初始坐标的预测与进一步精化：

利用最小二乘估计准则求解距离的统计优化值；

通过三次样条插值优化距离值，提高测距精度；

根据弦交点法预测初始坐标值；

用变尺度法对初始值进行迭代精化，提高定位精度。

1.1最小二乘求解距离的统计值

从终端获取某个点的n次待测节点到4个参考节点的距离信息：

然后求使(1)式取最小值的di作为此刻的最优估计值。

1.2三次样条插值优化距离值

三次样条插值基于样条曲线，样条曲线实际上是由分段三次曲线并接而成，在连接点即样点上要求二阶导数连续，从概念上概括就得到数学中的三次样条函数这一概念。把(1)式得出的最优值dt通过三次样条插值拟合运算，使之更加接近真实值，即对距离进行“求真运算”该方法主要设计以下关键步骤：

（1）确定边界条件：边界条件设置为y'1=1，y'n=1，即假定测量值和真实值是相一致的；

（2）计算：构造满足步骤1边界条件的三次样条插值函数；

（4）把结果代入步骤2内即可。实验时，在范围50m以内选取了10个点进行实际的测量，以此10点数据进行插值求解关系表达式，然后，选取额外的15点进行插值计算，求插值后的距离值。得出实际距离、测试距离和插值距离的关系如图1所示。

由图1可以看出,经过插值之后得出距离非常接近真实值,误差的绝对值丨知哄1<0.6m，可为下一步的坐标计算提供较精确的数值输入。

1.3弦交点法初步定位

由三次样条插值得出待测节点与各个参考节点的距离dge，(i=1,2,3,4)之后，以参考节点为圆心、待测节点到参考节点的距离为半径作圆，初步判定待测点在4个圆所交的公共区域U内，即X。eU,并有不等式方程组式(4)成立,其中(x,y)为第i个参考节点的坐标。

为在不影响精度的情况下简化计算，可以选择其中三个不等式组成方程组式(5),选择的标准就是提出距离值最大的一个。原因是：若参考节点组成的区域为矩形区域，待测节点与某一参考节点距离最大，则必定在另外三个参考节点组成的三角形中。

(5)为了在待选区域U选择合适的迭代初始值，该算法思路是：两圆相交必有公共弦，三圆相交则有三条公共弦，此三条公共弦L1，L2,L3必相交于一点。(x,y),可由三条公共弦的直线方程联立方程组进行证明，就以此交点作为迭代初始值X0(x0,y0)°

1.4变尺度法(DFP)精化

分析不等式方程组式(4),在该方程组的解空间中找出在一定准则下的理论最优值，可以把此方程组转换为无约束最优化问题。

于是，设有以下求极小值问题：

由最优估计理论分析可知，该无约束极小值问题的最优解满足不等式方程组式(4),把该解作为初始点求精后的最优值。对无约束极小值问题式(6)的求解，可采用变尺度法(DFP法)，该方法是求解无约束极值问题的一种有效方法[12]。由于它避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著优越性，因此可以对该问题进行有效求解。

DFP法主要涉及两个主要的算法，分别是利用黄金分割法进行一维捜索和利用DFP法计算最小点对应的自变量的值。其中，DFP算法流程如图2所示：其中s为控制误差,X。为输入的初始值,E是与X。同维的单位矩阵。黄金分割法流程如图3所示。

2算法验证与结果分析

2.1实验环境

为验证本算法的定位精度，选取并设计了两个实验场景来模拟不同环境。理想环境:验证定位算法在无信号折射反射、视距传播的环境中的定位精度；复杂环境：验证定位算法在室内(封闭环境)受多径影响下的定位精度。

理想环境：室外较宽阔空间，在50X50m2的空旷场地上选取4.8X10.8m2的一个矩形区域作为测试范围，周围除了自然辐射以外没有额外影响射频信号发射、传播、接收的电磁波。参考节点和待测节点放在离地面约3m的位置。

复杂环境：封闭的仓库环境，在10X8m2的仓库内对选取4.8X10.8m2的一个矩形区域作为测试范围，除了室内的信号传播造成的多径现象，无其他额外信号干扰，参考节点同样放置在离地面3m的地方。

2.2定位结果

理想环境中，计算出的实验数据如表1所列。

表1环境实验结

注:误差是指两点冋的距离

由表1可发现，该算法在理想环境中能实现对待定目标位置的估计，弦交点法初步定位的误差在0.68m以内，而经过DFP法精化后，误差缩小到在0.22m以内，达到了提高精度的目的。同时经过实验，由弦交点预估出的初始坐标，可以明显缩短DFP迭代次数并节约算法整体运行时间。

复杂环境中，测出的距离数据经过DFP求精计算后的坐标比初始坐标也有更好的精度，最优情况能达到0.22m，而在矩形区域的边缘部分精度有所下降，控制在0.8m以内，如图4所示。

图4仓库环境中实验结果对比图

4结语

本文把三次样条插值算法和DFP迭代算法引入到室内定位算法的距离补偿和坐标的精化运算，并通过模拟实验对本算法进行了实现与验证。从算法研究和实验数据分析可以看出，DFP精化算法确实提高了定位精度。基于本算法模型的精确室内定位技术结合计量检测技术、GIS技术、网络传输技术和云计算技术等技术，可以搭建一个集实时监控和信息管理于一体的管理平台，一改传统人工操作规程，保障物资安全，真正达到室内物品实时、有效监控和管理的目的。

20211118_619644fd9f0bf__一种提咼室内定位精度的算法