内容发布更新时间 : 2024/5/22 8:43:17星期一 下面是文章的全部内容请认真阅读。
龙源期刊网 http://www.qikan.com.cn
基于质心的改良Wi—Fi三边定位算法设计与分析
作者：蓝茂俊 陈正铭 戴经国 张楠 来源：《软件工程》2016年第11期
摘 要：针对节点不均匀导致的Wi-Fi三边定位算法精度较低的问题，提出了基于质心的改良Wi-Fi三边定位算法。该算法通过计算相交圆的公共区域所组成的质心来提高对待测点位置估算的精确度，然后通过数据图表分析，证明基于质心改良后的Wi-Fi三边定位算法的确比原三边定位算法定位精确度更高。
关键词：WI-FI；定位；三边定位算法；质心定位算法 中图分类号：TP393.1 文献标识码：A 1 引言（Introduction）
Wi-Fi全称Wireless Fidelity，又可称为无线保真网络，是一种可以将个人电脑、手机等终端设备以无线连接的方式进行数据传输的技术，相比蓝牙和红外线技术，具备传送范围更广、速率更快、和多设备连接等特点。现如今随着无线网络的迅速发展，许多新兴应用的通信设备大量涌现[1]并运用于许多公共场所和商业服务，包括搜索救援、灾难抢险和基于位置的服务，这导致对无线连接用户的位置信息需求逐步增多[2]。因此需要比较成熟的定位技术去监测信息，而监测信息必须和位置相结合才有意义[3]，如三边定位算法，虽然它能快速和较为精确地定位，但是存在节点不均匀导致的精度较低的问题。为了提高三边定位算法的精确度，本文将通过质心算法的思想提出基于质心的改良Wi-Fi三边定位算法的实现过程与实验分析。 2 三边定位算法简述（The sketch of trilateral localization algorithm）
三边定位算法是依靠三个坐标点的位置，通过三边定位的公式求需定位点的坐标值[4]。根据此算法分成两个步骤：测量距离以及进行定位。 2.1 测量距离
待测点首先需要接收来自三个RSS点，前提是这三个RSS点的位置AP已知并且不重复。假设这三个RSS点分别为P1（X1，Y1）、P2（X2，Y2）和P3（X3，Y3）。由于无线信号在传输过程当中一般会受路径损耗、阴影衰落等因素影响，其接收信号的功率随距离的变化关系可由信号传输损耗模型体现[5]。信号传输损耗模型如式（1）所示。
式（1）中，d是某一个已知位置的RSS点与待测点的距离，而ε代表非自由空间的损耗系数，K是一个常数[6]，可由式（2）体现。
龙源期刊网 http://www.qikan.com.cn
2.2 定位
假设待测点为S（X，Y），在上一步测量距离过程当中，可用三个已知位置的RSS点作为圆心，以RSS点与待测点的距离d作为半径做圆，得到三个圆的共同交点，如图1所示。 如果存在三个圆相交能得出唯一交点时，可以利用式（3）—式（5）[7]，解出点S的坐标。
但是，这只是其中一种情况，还有以下两种情况，如图2所示。
这受限于测量距离的精度不够，虽然也是可以通过特定的公式计算出待测点的坐标，但是计算方式比较复杂，且算出的是一个近似范围解，不能精确定位。
三边定位算法由于存在许多的能够影响信号传输的因素，例如环境的变化，其他的信号波的干扰等，这些都会造成传输损耗模型有所不同，导致测量距离d受到影响，致使待测点的位置误差较大。
3 基于质心的改良Wi-Fi三边定位算法的思路（The thought of the Wi-Fi trilateral positioning algorithm based on centroid）
针对三边定位算法的缺陷，提出将质心算法[8]的思想融入到三边定位算法里面，通过多次计算相交圆的公共区域所组成的质心来估算出待测点的位置，以提高计算出待测点的坐标位置的精确度的思路，而该算法需要满足网络环境中已知的RSS点位于待测点的外侧且这些RSS不少于三个。
第一步，假设三个RSS点分别为A（X0，Y0）、B（X1，Y1）、C（X2，Y2），以及假设待测点为S（X，Y）。三个RSS点作为相交圆的圆心，以圆心到待测点的距离作为半径形成三个圆，假设三个RSS点到待测点的距离分别为d1、d2、d3。
第二步，计算出点与点之间的距离，假设点A到点B的距离为D1，点A到点C的距离为D2，点B到点C的距离为D3。将三个RSS点连接形成三角形ABC，其中包含进去了三个RSS点到待测点的距离边。因此可以通过三角形定理得出结论，如式（6）—式（10）所示。 通过这五个结论，可分两种情况来判断，第一种情况是当不满足后三个结论的任意一个时，将对d1、d2、d3对应的三条边都增加其对应外边减去当前大三角形内部对应外边所形成的三角形的最小边的差的一定倍数。另外一种情况是当不满足前两个结论时，将对d1、d2、d3对应的三条边都减少当前大三角形内部对应外边所形成的三角形的最大边减去对应外边的差的一定倍数。直至满足这五个结论才进入到下一步。
第三步假设求出圆A与圆B的交点分别为（Xab1，Yab1）、（Xab2，Yab2），圆A与圆C的交点分别为（Xac1，Yac1）、（Xac2，Yac2），以及圆B与圆C的交点分别为（Xbc1，
龙源期刊网 http://www.qikan.com.cn
Ybc1）、（Xbc2，Ybc2）。之后通过公式（X-X1）2+（Y-Y1）2求出圆A和圆B的两个交点中离圆C最近的点，假设为（Xab1，Yab1）。同理可以求出圆A和圆C的两个交点中离圆B最近的点假设为（Xac1，Yac1），以及圆B和圆C的两个交点中离圆A近的点，假设为（Xbc1，Ybc1）。如果这三个点完全一致的话，那么这个交点即为待测点，否则将以这三个交点为圆心，再进行上述流程。一般此过程重复三次左右即可较大程度地提高对待测点的精确度。若重复十次之后三个点仍然不一致的话，可用质心定位算法的思想去估算待测点的坐标，求法如式（11）所示。
4 实验与分析（The experiment and analysis）
待测点定位算法优劣性主要从待测点的定位准确度、网络中RSS的密度、待测点的密度、网络规模等方面进行评估[8]。本文只针对算法本身所估算出来的待测点的定位精度进行分析。
通过Java代码分别对三边定位算法以及本文所提出的改良算法的优劣性进行分析比较，仿真过程如下：
（1）在10*10的平面直角坐标中随机生成至少三个RSS点，这里为了方便就设定随机生成三个RSS点，分别为A点（X1，Y1）、B点（X2，Y2）和C点（X3，Y3）。（实际中如果出现超过三个RSS点的话则可以通过Wi-Fi覆盖等级寻找出一个RSS分布较为均匀的网络环境，在此环境寻找出满足本算法条件的三个RSS点。
（2）寻找出三个RSS点之后将其形成三角形ABC，在其内部的随机位置生成D点，假设为（X，Y）。
（3）计算AD、BD、CD的距离假设分别为d1、d2、d3，以及计算AB、AC、BC的距离假设分别为D1、D2、D3。
（4）为d1、d2、d3分别加上人为误差后假设为D1、D2、D3，以确保实验的真实性。 （5）根据式（6）—式（10）让三角形ABC满足五个结论。
（6）根据A、B、C三点的坐标值，以及D1、D2、D3，通过三边定位算法和本文所提出的改良算法估算出待测点的坐标点，假设求出的待测点分别为（Xthr，Ythr）、（Xcen，Ycen）。
（7）分别根据上述两种算法估算出坐标值（Xthr，Ythr）、（Xcen，Ycen）与点D的真实值（X，Y）根据公式（X-X1）2+（Y-Y1）2=d12求出两点直接的距离并作为其误差。 （8）在同一设定误差值下重复以上过程50次，求出平均误差并记录数据。通过数据表格来进行比较分析，如表1和图3所示。