摘 要：室内定位技术对于室内物品的实时监管具有重要的实际应用价值。为了进行室内物品的精确定位，文中建立了一种基于距离的最优估计定位模型，并引入变尺度（DFP）算法对模型进行求解，从而达到提高坐标精度的目的。本设计首先对原始距离信息利用最小二乘估计、三次样条插值法来提高测距精度；其次通过三圆公共弦交点法确定出初始坐标值；然后把空间几何关系转换为无约束极小值问题，再采用DFP法对初始坐标进一步精化，以得出更为精确的坐标值。最后通过两种模拟实验对算法进行验证，结果表明：引入最优估计理论的室内定位算法，具有更高的定位精度。
关键词：室内定位算法；最优估计；DFP法；无约束极小值；三次样条插值
中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2014）02-0019-03
0 引 言
室内定位技术是物联网感知层的基础支撑技术，因其可以提供室内物品的与位置相关的信息，赢得了广大学者的关注和研究。同时随着物联网相关概念的推广，室内物品的联网与定位开始提出了新的需求与挑战，即更加便捷的部署方式、更高精度的定位信息。采用室内定位系统，可以实现室内物品的实时在线、远程监管，使得物联网从理论概念走到现实世界中。
完整的室内定位系统一般包括室内定位技术、室内定位算法、数据管理软件和硬件设备等。其中定位算法是核心，定位算法的精度是决定系统实施与应用的关键。根据定位过程中是否测量实际节点间的距离，把算法分为：基于距离的（Range-Based）算法和距离无关的（Range-Free）算法[1-3]。距离无关的定位机制只利用节点间的连通性来估测自身的位置，用最优化方法来提高定位精度，比较经典的算法如凸规划算法和MDS-MAP算法[4-7]，但整体的精度没有基于距离的定位算法高，虽然有些算法利用了循环方式来提高精度[8]，然而应用的范围远不及前者。因而基于距离的定位机制，因具有高精度、部署方便和组网灵活的特点[9]，备受研究者们的关注。
本文研究重点是基于距离的室内定位算法。根据定位算法原理，定位精度主要受两个因素影响：距离测算与坐标计算。本工作建立基于距离的坐标估计、计算模型，采用数值分析理论对距离进行误差补偿，利用运筹学方法对初步定位结果做进一步的求精，并通过模拟实验验证算法精度。
1 模型建立与求解
提高基于距离的室内定位算法精度存在两个难点：距离数据的处理和坐标值的推导，本节所述模型将通过以下4个步骤完成对原始距离值的统计、还原，初始坐标的预测与进一步精化：
（1）利用最小二乘估计准则求解距离的统计优化值；
（2） 通过三次样条插值优化距离值，提高测距精度；
（3） 根据弦交点法预测初始坐标值；
（4） 用变尺度法对初始值进行迭代精化，提高定位精度。
1.1 最小二乘求解距离的统计值
从终端获取某个点的n次待测节点到4个参考节点的距离信息：
dij（i=1，2，3，4；j=1，2，…，n）
把dij进行最小二乘估计[10]，即以dij的测量残差=di-dij（i=1，2，3，4）的平方和最小作为最优估计准则来估计出最优的dij（i=1，2，3，4），如（1）式：
（1）
然后求使（1）式取最小值的di作为此刻的最优估计值。
1.2 三次样条插值优化距离值
三次样条插值基于样条曲线，样条曲线实际上是由分段三次曲线并接而成，在连接点即样点上要求二阶导数连续，从概念上概括就得到数学中的三次样条函数这一概念[11]。把（1）式得出的最优值di通过三次样条插值拟合运算，使之更加接近真实值，即对距离进行“求真运算”。该方法主要设计以下关键步骤：
（1）确定边界条件：边界条件设置为y"1=1，y"n=1，即假定测量值和真实值是相一致的；
（2） 计算：构造满足步骤1边界条件的三次样条插值函数；
（2）
式（2）中，αj（x），βj（x）是插值基函数。
（3） 构造三弯矩方程。
（3）
（4）把结果代入步骤2内即可。
实验时，在范围50 m以内选取了10个点进行实际的测量，以此10点数据进行插值求解关系表达式，然后，选取额外的15点进行插值计算，求插值后的距离值。得出实际距离、测试距离和插值距离的关系如图1所示。
图1 三次样条插值对比图
由图1可以看出，经过插值之后得出距离非常接近真实值，误差的绝对值│espline┃<0.6 m，可为下一步的坐标计算提供较精确的数值输入。
1.3 弦交点法初步定位
由三次样条插值得出待测节点与各个参考节点的距离dspline，i（i=1，2，3，4）之后，以参考节点为圆心、待测节点到参考节点的距离为半径作圆，初步判定待测点在4个圆所交的公共区域U内，即X0∈U，并有不等式方程组式（4）成立，其中（x，y）为第i个参考节点的坐标。
（4）
为在不影响精度的情况下简化计算，可以选择其中三个不等式组成方程组式（5），选择的标准就是提出距离值最大的一个。原因是：若参考节点组成的区域为矩形区域，待测节点与某一参考节点距离最大，则必定在另外三个参考节点组成的三角形中。
（5）
为了在待选区域U选择合适的迭代初始值，该算法思路是：两圆相交必有公共弦，三圆相交则有三条公共弦，此三条公共弦L1，L2，L3必相交于一点O（x，y），可由三条公共弦的直线方程联立方程组进行证明，就以此交点作为迭代初始值X0（x0，y0）。
1.4 变尺度法（DFP）精化
分析不等式方程组式（4），在该方程组的解空间中找出在一定准则下的理论最优值，可以把此方程组转换为无约束最优化问题。
于是，设有以下求极小值问题：
（6）
由最优估计理论分析可知，该无约束极小值问题的最优解满足不等式方程组式（4），把该解作为初始点求精后的最优值。对无约束极小值问题式（6） 的求解，可采用变尺度法（DFP法），该方法是求解无约束极值问题的一种有效方法[12]。由于它避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著优越性，因此可以对该问题进行有效求解。
DFP法主要涉及两个主要的算法，分别是利用黄金分割法进行一维搜索和利用DFP法计算最小点对应的自变量的值。其中，DFP算法流程如图2所示：其中ε为控制误差，X0为输入的初始值，E0是与X0同维的单位矩阵。黄金分割法流程如图3所示。
图2 DFP算法流程图
图3 黄金分割法流程图
2 算法验证与结果分析
2.1 实验环境
为验证本算法的定位精度，选取并设计了两个实验场景来模拟不同环境。理想环境：验证定位算法在无信号折射反射、视距传播的环境中的定位精度；复杂环境：验证定位算法在室内（封闭环境）受多径影响下的定位精度。
理想环境：室外较宽阔空间，在50×50 m2的空旷场地上选取4.8×10.8 m2的一个矩形区域作为测试范围，周围除了自然辐射以外没有额外影响射频信号发射、传播、接收的电磁波。参考节点和待测节点放在离地面约3 m的位置。
复杂环境：封闭的仓库环境，在10×8 m2的仓库内对选取4.8×10.8 m2的一个矩形区域作为测试范围，除了室内的信号传播造成的多径现象，无其他额外信号干扰，参考节点同样放置在离地面3 m的地方。
2.2 定位结果
理想环境中，计算出的实验数据如表1所列。
表 1环境实验结目标序号实际坐标预估坐标最终坐标预估误差最终误差
1（0.50，0.50）（0.76，0.86）（0.71，0.31）0.197 20.080 2
2（2.40，1.20）（2.48，1.36）（2.47，1.23）0.0320.019 3
3（1.20，3.60）（1.02，4.31）（1.08，3.99）0.536 50.166 5
4（3.60，4.80）（3.75，4.72）（3.34，4.74）0.028 90.071 2
5（0.50，6.00）（0.66，5.83）（0.93，5.83）0.054 50.213 8
6（3.60，7.20）（3.44，7.06）（3.43，7.21）0.045 20.029
7（2.40，9.60）（2.47，9.35）（2.52，9.57）0.067 40.015 3
8（4.00，10.00）（3.73，9.64）（3.84，9.80）0.202 50.065 6
注：误差是指两点间的距离
由表1可发现，该算法在理想环境中能实现对待定目标位置的估计，弦交点法初步定位的误差在0.68 m以内，而经过DFP法精化后，误差缩小到在0.22 m以内，达到了提高精度的目的。同时经过实验，由弦交点预估出的初始坐标，可以明显缩短DFP迭代次数并节约算法整体运行时间。
复杂环境中，测出的距离数据经过DFP求精计算后的坐标比初始坐标也有更好的精度，最优情况能达到0.22 m，而在矩形区域的边缘部分精度有所下降，控制在0.8 m以内，如图4所示。
图4 仓库环境中实验结果对比图
4 结 语
本文把三次样条插值算法和DFP迭代算法引入到室内定位算法的距离补偿和坐标的精化运算，并通过模拟实验对本算法进行了实现与验证。从算法研究和实验数据分析可以看出，DFP精化算法确实提高了定位精度。基于本算法模型的精确室内定位技术结合计量检测技术、GIS技术、网络传输技术和云计算技术等技术，可以搭建一个集实时监控和信息管理于一体的管理平台，一改传统人工操作规程，保障物资安全，真正达到室内物品实时、有效监控和管理的目的。
参 考 文 献
[1] 王光辉， 刘洪霞， 胡浩舒， 等. 室内定位算法综述[C]. 第十八届全国网络与数据通信学术会议论文集. 南京： [出版者不详]， 2011.
[2] KIM Hakyong. A ranging scheme for asynchronous location positioning systems [C]// Proceedings of 2009 6th Workshop on Positioning， Navigation and Communication. Hannover， Germany： WPNC， 2009： 89-94.
[3] DENG Zhong-liang， YU Yan-pei， YUAN Xie， et al. Situation and development tendency of indoor positioning [J]. China Communications， 2013， 10（3）： 42-55.
[4] 陈智勇， 王健， 季晓勇. 无线传感网络定位算法的研究进展[J]. 电子检测技术， 2010， 33（10）： 40-43.
[5] 张松涛. 无线传感器网络定位问题研究[D]. 武汉： 华中科技大学， 2010.
[6] 倪海燕， 应祥岳， 简家文， 等. 无线传感器网络的自身定位算法研究[J]. 宁波大学学报：理工版， 2009， 22（1）： 7-11.
[7] 于宁， 万江文， 吴银峰. 无线传感器网络定位算法研究[J]. 传感技术学报， 2007， 20（1）： 187-192.
[8] 彭立， 张炜. 基于循环求精的APIT无线传感器网络定位算法[C]. 第二十九届中国控制会议论文集. 北京： [出版者不详]， 2010.
[9] 施蕾.无线传感器网络自定位算法研究[OL].中国科技论文在线， [2007-04-20]. http：//.cn/qkpdf/wlwj/wlwj201402/wlwj20140210-1.pdf" style="color:red" target="_blank">原版全文