一种基于概率模型的改进Scout无线定位算法

吴小军，赵东明，徐 进

（武汉理工大学 自动化学院 自动化系，武汉 430070）

当前，无线定位算法已经成为一个重要的研究方向和热点问题.典型的定位算法可分为两大类：基于距离的（Range－based）定位算法［1］和与距离无关的（Range－free）定位算法［2］.Range－based定位使用三边测量法、三角测量法或最大似然估计法，即通过测量节点间的距离或角度信息来计算未知节点的位置；Range－Free定位则无需距离和角度信息，仅根据网络连通性等信息即可实现，常用的Range－Free定位算法有DV－Hop算法、APIT算法［3］、质心算法等.与距离无关的定位算法对节点的硬件结构要求较低，但是其定位精度不高，很难满足室内定位精度的要求.常用的测距技术有RSSI、TOA、TDOA 和AOA［4］等，其中由于RSSI测距借助的硬件设备少，而且许多无线通信模块都可以直接提供RSSI值，因此，基于RSSI的测距方法被广泛应用.

反射、多径传播、非视距、天线增益等问题都会对相同距离产生显著的传播损耗.通常将RSSI测距看作为一种粗略的测距技术，如何能够提高基于RSSI的定位精度是一个比较有意义的问题.目前，应用于室内无线定位的算法有很多，比如：基于RSSI差分修正的加权质心定位算法［5］，基于RSSI测距的差分修正定位算法［6］，基于RSSI的三角形质心定位算法［7］，基于RSSI的无线传感器网络距离修正定位算法［8］等，文献［9］提出了一种基于概率模型的Scout定位算法，该算法借助于参考标签对其相应的读卡器进行参数修正，利用一个概率模型来描述标签与读卡器之间的距离和标签接收到的信号强度的关系，最后通过贝叶斯推理［10］确定目标的定位区域，该算法定位精度较高，但是由于需要一定数量的参考标签，硬件成本较高，为了解决这一问题，本文在Scout定位算法的基础上进行改进，提出了一种基于概率模型的改进Scout算法.

1 算法模型描述

1.1 Scout定位算法

Scout算法基于RSSI对跟踪目标进行定位.在算法执行过程中，借助分布于现场的参考标签对各传输参数进行实时修正，利用一个概率模型来描述标签与读卡器之间的距离和标签接收到的信号强度的关系，最后通过贝叶斯推理确定目标的定位区域.

Scout算法定位需要n（n≥4）个信号读取设备（读卡器），与之对应n（n≥4）个已知位置的参考标签，至少一个服务器，以及要追踪的目标节点标签若干个.读卡器用于判断各个标签的RSSI值并传送给服务器进行处理，参考标签用于校正参数.

该算法是通过利用已知的参考标签参与校正，在每次定位算法执行的过程中，通过更新传输损耗和路径损耗进行校正.在算法执行的过程中RSSI与各个参数的关系如下.

其中，a为传输损耗，n为路径损耗，每次测算之前需要进行重新计算以防止在不同测试情况下产生误差.所以该算法的核心部分在于参考标签的参数修正部分，需要准确求出每个读卡器相应的传输损耗a和路径损耗n.

1.2 Scout定位算法的改进

本文提出的定位算法在Scout算法的基础上作出了改进，该算法定位需要n（n≥4）个读卡器，不需要在读卡器附近设置参考标签，经过算法修正后，读卡器可以当参考标签使用，这样一来，该定位系统设备（n＝4时）只需要4个读卡器就够了，传统的Scout算法需要8个节点，对于整个定位系统而言，本文提出的定位算法大大降低了硬件成本.改进前与改进后的定位节点布局如图1所示.

如图1（b）所示，在求算读卡器1 相对应的a和n时，根据公式（1）可知，我们只需联立不同距离得到的信号RSSI值便可以解得a和n，如下公式（2）.由（d1，d2）求得a1、n1；由（d1，d3）求得a2、n2；由（d2，d3）求得a3、n3；然后求a1、a2、a3的平均值得a；求n1、n2、n3的平均值得n.得到信号RSSI值的时候，可以代入概率公式（3）求概率的大小.以上公式可以把信号的强弱看做一个概率事件，即无论两点间的距离是多少，其某一次产生的信号可大可小，只是概率大小的区别.对于一个有限的区域，遍历各个位置到读卡器的距离d发出RSSI的概率，取最大的概率对应的d.

图1 Scout算法改进前与改进后的定位节点布局图Fig.1 Node layout of Scout positioning algorithm and improred Scout positioning algorithm

各个点的概率归一化后取P＞0.999 9后得到的最大概率点分布图如图2所示.

最后把对某一点上到各个读卡器的概率相乘得到目标位于该点的最终概率，从中选取最大的概率，通过计算得到目标点的位置.

图2 最大概率点分图布Fig.2 Point of maximum probability distribution

2 算法的执行步骤

图3 算法流程图Fig.3 Algorithm flowchart

（1）初始化可信度向量Bel（x0）

其中，x0表示跟踪目标的初始状态，即目标在探测区域中的初始位置；算法将整个探测区域划分为N个子区域，Bel（x0）表示在初始时刻目标位于各子区域的可能性.

（2）决定基本的探测范围

图4 观测一个目标点Fig.4 Observing a target point

（3）修正传输参数

（4）重新计算可信度向量Bel（xt）

（5）如果迭代次数小于预定的迭代次数，则移动到下一个网络，并且返回到第2步.否则结束步骤4中的迭代过程，确定定位区域.

Bel＇（xt）称为相对可信度向量，将向量中数值大于或等于阀值概率的元素所对应的子区域列入最终的定位区域；C（gxk，gyk）表示整个探测区域中的第k个子区域；子区域又被称为网格，一个网格由位于网格中心的一个点来表示，gxk，gyk表示第k个网格的中心点的横纵坐标，Bel（xt＝C（gxk，gyk）表示目标在t时刻位于第k个网格的概率.

（6）确定定位点

每一次迭代都确定了相应的定位区域，所有的迭代结束后，求取以上列出的各定位区域所对应的概率的平均值，概率的平均值所对应的点即是最终的定位点.

3 仿真结果

在Matlab平台上分别对Scout算法和改进后的算法进行仿真，仿真条件是在一个10m×10m的正方形区域内，传播路径损耗模型选择经典的自由空间模型和对数－常态模型.在该区域放置4个读卡器，其坐标自己设定，对Scout算法仿真时，在各读卡器附近固定位置增加参考标签节点，对改进后的算法仿真时不需要参考标签.未知目标节点的坐标由Matlab随机生成函数来生成，在该区域内随机分布，一共生成10 个未知目标节点.然后根据RSSI与距离的关系生成RSSI数据，并在数据中添加均值为0、标准差σ为3 的高斯噪声作为RSSI的随机分量，以模拟实际环境中的反射、多径、物体遮挡、气候等带来的影响.路径损耗系数n取4，通过自由空间传播模型和对数－常态分布模型，按照上述的算法步骤来对上述两种算法进行仿真定位.对于这两种算法，列出了迭代次数r＝10时的仿真图.图5和图6是算法的Matlab仿真结果图.

图5 Scout算法仿真图Fig.5 Simulation diagram of Scout algorithm

图6 Scout算法改进后仿真图Fig.6 Simulation diagram of improved Scout algorithm

从图6可以看出，两种算法定位的精度都很高，Scout算法定位需要八个定位节点，而改进后的算法只需要四个定位节点就能达到Scout算法的定位精度.

4 结论

基于概率模型的改进Scout无线定位算法，通过改进算法将定位节点减少一半，降低了定位系统的硬件成本，而由于改进后的算法的定位核心思想仍同于Scout定位算法，因此，基于概率模型的改进Scout无线定位算法在减少参考节点数量的情况下定位精度相比Scout定位算法并没有降低.

5 展望

基于概率模型的改进Scout无线定位算法也存在不足，定位节点数的减少是通过改进算法来实现的，如果定位区域较大，需要的读卡器数量较多时，各个读卡器之间的关系变得复杂了，通过改进算法来减少定位节点的难度将很大，要解决这一问题还需要进一步优化算法或者更新定位算法的思路.

［1］王 琦.基于RSSI测距的室内定位技术［J］.电子科技，2012，25（6）：64－66.

［2］李建中，高 宏.无线传感器网络的研究进展［J］.计算机研究与发展，2008，45（1）：1－15.

［3］Sayed A，Tarighat A，Khajehnouri N.Networkbased wireless location［J］.IEEE Signal Processing Mag，2005，22（4）：24－40.

［4］Ni L M，Liu Y，Cho Y，ea al.LANDMARC：indoor loca－tion sensing using active RFID［C］／／Proceedings of the First IEEE International Conference on Pervasive Computing and Communications（PerCom 2003），2003（3）：23－26.

［5］花 超，吉小军，蔡 萍.基于RSSI差分修正的加权质心定位算法［J］.传感器与微系统，2012，31（5）：139－144.

［6］任维政，徐连明，邓中亮.基于RSSI测距的差分修正定位算法［J］.传感技术学报，2008，21（7）：1247－1250.

［7］林 玮，陈传峰.基于RSSI的无线传感器网络三角形质心定位算法［J］.现代电子技术，2009，289：180－182.

［8］陈昌祥，达 维，周 洁.基于RSSI的无线传感器网络距离修正定位算法［J］.通信技术，2011，44（2）：65－69.

［9］Girod L，Estrin D.Robust range estimation using acoustic and muhimodal sensing［EB／OL］.http：／／www.rfcode.com／data＿sheets／mantis.pdf.

［10］Roos T，Myllymaki P，Tirri H，et al.A probabilistic approach to WLAN user location estimation［J］.International Journal of Wireless Information Networks，2002，9（3）：17－18.