-基于三角形与位置指纹识别算法的WiFi定位比较

设计与实现72责任编辑：左永君[e-mail]2010年第10期【摘要】WiFi的定位实现主要基于三角形算法和位置指纹识别，文章首先分别对这两方面从理论上作了介绍，然后通过在校园和市内两种室外环境的现场实验，证实了基于WiFi无线定位的可能性，也表明了在室外环境下基于位置指纹识别的定位性能远优于基于三角形算法。【关键词】WiFi定位三角形算法位置指纹识别RSS基于三角形与位置指纹识别算法的WiFi定位比较收稿日期：2010-3-15卢恒惠刘兴川张超林孝康清华大学深圳研究生院1引言目标的位置信息在各种场合中发挥着重要作用，如车辆导航、矿井井下人员定位、医疗看护对象定位、建筑工地管理等。GPS作为全球最广泛使用的卫星导航定位技术，在许多领域得到了推广应用。然而，其信号却极易受障碍物的干扰和阻断，在密集的城市地带、隧道、室内等环境定位不可靠甚至于失效。因此，必须有其它的定位技术辅助GPS或者单独在无GPS可用的场合下提供定位服务。随着IEEE802.11技术的成熟，WiFi在世界各地普及，其覆盖面越来越广。虽然WiFi并不是为定位而设计，但接入点（AP）或基站定期发送的信标信号中所含的接收信号强度（RSS）信息为定位移动台提供了可能性，将其应用于定位场合受到了学术界与产业界的极大关注。较之现行定位技术如GPS、蜂窝定位、无迹推算等，基于WiFi的定位具有如下优势[1]：（1）可工作于室内、室外等不同场合，为实现无处不在的定位提供了可能性；（2）仅依赖于现有的WiFi网络，无需对其进行任何改动，使用成本低；（3）WiFi信号受非视距（NLOS）影响小，即使在有障碍物阻挡的情况下也能使用。当前，绝大多数基于WiFi的定位系统都利用RSS，其方法主要分成两类：三角形算法和位置指纹识别（fingerprinting）算法[2]。三角形算法利用待测目标到至少三个已知参考点之间的距离信息估计目标位置，而位置指纹识别则通过比较定位所需的信号特征指纹信息获取目标位置。本文对这两种方法进行了研究，并在不同的室外环设计与实现73责任编辑：左永君[e-mail]2010年第10期境下开展实验测试，对二者的性能进行了比较。2三角形算法基于三角形算法的WiFi定位可分成两个阶段：测距与定位。2.1测距阶段待测点首先接收来自三个不同已知位置AP的RSS，然后依照无线信号的传输损耗模型将其转换成待测目标到相应AP的距离。无线信号在传输过程中通常会受路径损耗、阴影衰落等的影响，接收信号功率随距离的变化关系可由信号传输损耗模型给出。在城市、郊区等环境，传输损耗模型通常采用如下简化模型[3]：Pr(d)=K-10εlg(d)（dBm）（1）其中，d代表接收机和发射机之间的距离，ε代表非自由空间的损耗系数，K是如下常数：()=10lg20lg()0.001r00PdKdW⎡⎤+⎢⎥⎣⎦（2）2.2定位阶段通过三角形算法计算待测点位置，即分别以已知位置的三个AP为圆心，以其各自到待测点的距离为半径做圆，所得三个圆的交点，如图1所示：图1三角形算法示意图设未知节点D的坐标为（x，y），已知A、B、C三个点的坐标分别为（x1，y1）、（x2，y2）、（x3，y3），它们到D的距离分别为d1、d2、d3，则D的位置可由下列方程中的任意两个求得[4]：222111()()xxyyd−+−=（3）222222()()xxyyd−+−=（4）222333()()xxyyd−+−=（5）然而，在实际应用中，由于测量误差的存在，三圆交于一点的情况未必出现，以致方程组（3）、（4）、（5）无解。在三圆两两相交的情况下，有图2、3两种典型的无解情况：图2方程组无解情况1图3方程组无解情况2在这两种情况下，D点的求解方法如下[4]：（1）根据方程（3）、（4）、（5）分别求解圆A与圆B的交点（Xab1，Yab1）、（Xab2，Yab2），圆A与圆C的交点（Xac1，Yac1）、（Xac2，Yac2），及圆B与圆C的交点（Xbc1，Ybc1）、（Xbc2，Ybc2）。（2）将圆A与圆C的交点代入[(x-x2)2+(y-y2)2]，找出距B圆圆心较近的点，设为（Xac，Yac）。同理，求解（Xab，Yab）、（Xbc，Ybc）。（3）近似计算待测点位置：(,),33abacbcabacbcXXXYYYxy++++⎛⎞=⎜⎟⎝⎠（6）设计与实现74责任编辑：左永君[e-mail]2010年第10期由上述介绍可知，基于三角形算法的WiFi定位很大程度上依赖于确知的AP位置信息及准确的信号传输损耗模型。然而，由于涉及个人隐私等原因，获知所有AP的位置信息并不现实。此外，由于影响信号传输的因素很多，不同环境下的信号传输损耗模型大不相同，建立一个准确的、适合实际应用的损耗模型存在着很大的困难。因此，基于三角形算法的无线定位在具体实施中困难重重。3位置指纹识别算法与通常意义上的指纹识别类似，位置指纹识别依靠表征目标特征的数据库进行识别。其定位过程主要分为训练与定位两个阶段[5]，如图4所示：图4基于位置指纹识别的WiFi定位3.1训练阶段其目标在于建立一个位置指纹识别数据库。首先，选择合理的参考点分布，确保能为定位阶段的准确位置估计提供足够的信息。接着依次在各个参考点上测量来自不同AP的RSS值，将相应的MAC地址与参考点的位置信息记录在数据库中，直至遍历关注区域内所有的参考点。由于受环境影响，无线信号强度并不稳定，为了克服RSS不稳定对定位的影响，通常在每个参考点上多次测量取平均。3.2定位阶段给定数据库后，依据一定的匹配算法将待测点上接收的APRSS与数据库中的已有数据进行比较，计算位置估计值。常用的匹配算法有最近邻法（NN）、KNN、神经网络等，本文采用简单的NN算法。假定待测点接收的RSS观测值为s=[ss1,ss2,…,ssn]，数据库中的已有记录为Si=[SS1,SS2,…,SSNi]，其中n代表待测点上检测到的不同AP数；i∈[1,NT]，NT为数据库中的记录数；Ni代表第i条记录中存储的不同AP数，则NN算法可以表示成下述形式[3]：L=argmini∈[1,NT]||s-Si||（7）其中，||s-Si||代表s和Si之间的欧式距离。4实测结果分析为考察三角形和位置指纹识别算法在WiFi定位中的应用，本文选取校园和市区两个测试点开展了现场实验：清华大学深圳研究生院及深圳市荔园大厦附近城区。参考点及待测点的选取如图5、6所示，其中红色代表参考点（位置已知），黑色代表待测点（位置未知）。在清华大学深圳研究生院选取的参考点和待测点数分别为307和145，在荔园大厦附近则选取了266个参考点和132个待测点。实测中采用配备了Intel(R)PRO/Wireless3945ABGNetworkConnection网卡的IBMX61笔记本电脑收集WiFi信息；选用TK-158-USB收集GPS信息，以其作为准确的位置信息，为WiFi定位结果提供比较基准。软件部分则采用WirelessMon3.0扫描AP信号，记录相应的MAC、RSS、GPS经纬度、时间等信息，选用SQLserver2000建立数据库，利用C++进行定位处理。图5清华深圳研究生院设计与实现75责任编辑：左永君[e-mail]2010年第10期图6深圳市荔园大厦周边城区4.1基于三角形算法的WiFi定位基于三角形的定位必须已知AP的位置，因此首先要获取AP的位置信息。由于每个AP发出的信号可能被不同的参考点接收，因此利用能检测到同一AP信号的三个参考点位置，依照三角形算法就能预先计算出AP位置。其中，信号的传输损耗模型依据实测信号随距离的变化拟合获得，变化曲线如图7所示。相应地，待测点的位置则可根据已知AP的位置，采用同样的三角形算法获得。实验结果如表1、2所示。图7接收信号强度随距离的变化曲线由表1可知，依照本文的方法并不能计算出所有AP的位置。然而在AP数量远远超过测试点时，即使不能知道所有AP的位置信息也依旧能够算出测试点位置。无法确定所有AP位置的可能原因如下：（1）接收信号强度除了和距离有关外，还受到天线高度、天线方向等的影响，本文拟合的信号传输损耗模型并没有考虑除距离外的其它因素，不能准确反映真实情况。（2）不同位置处的环境不同，相应的损耗模型也有所差别，用同一模型势必会引入误差。由表2可知，基于三角形算法的WiFi定位，其定位性能并不高，定位精度随着可用AP数的增加而提高。4.2基于位置指纹识别的WiFi定位依照前述的位置指纹识别方法，本文通过在参考点上多次测量取平均来建立数据库，每个参考点采样次数大于100。实验结果如表3：表3基于位置指纹识别的定位误差比较最小偏差平均偏差最大偏差清华X方向（m）06.8428.45清华Y方向（m）07.5629.78荔园X方向（m）02.2423.45荔园Y方向（m）01.9618.52由表3同样可以得到表2的分析结果，对比二者不难发现基于位置指纹识别的定位精度远远高于基于三角形算法的WiFi定位。由于基于位置指纹识别的无线定位并不需要知道AP的位置及准确的信道模型，因此不管在具体实施上还是定位性能上，其较之于基于三角形算法的定位都具有较大的优越性。表1基于三角形算法定位的可用性比较AP总数位置可算AP数TP总数位置可算TP数清华140101145113荔园20521302132132表2基于三角形算法的定位性能比较最小偏差平均偏差最大偏差清华X方向（m）0.177033.3933144.2904清华Y方向（m）0.934027.4355157.4788荔园X方向（m）0.547623.734379.8340荔园Y方向（m）0.139522.471087.0383RSS/dBmDistance/m设计与实现76责任编辑：左永君[e-mail]2010年第10期参考文献[1]DuvalletF,TewsAD.WiFipositionestimationinindustrialenvironmentsusingGaussianprocesses[C].ProcofIEEERSJ,2008:2216-2221.[2]SalvatoreCavalieri.WLAN-basedoutdoorlocalizationusingpatternmatchingalgorithm[J].InternationalJournalofWirelessInformationNetworks,2007,14(4):265-279.[3]SinanGezici1.ASurveyonWirelessPositionEstimation[J].WirelessPersonalCommunications,2008,44(3):263-282.[4]林玮,陈传峰.基于RSSI的无线传感器网络三角形质心定位算法[J].现代电子技术,2009(2):180-182.[5]BinghaoLi,IshratJQuader,AndrewGDempster.OnoutdoorpositioningwithWiFi[J].JournalofGlobalPositioningSystems,2008,7(1):18-26.★【作者简介】卢恒惠：清华大学深圳研究生院现代通信实验室在读博士研究生，主要研究方向包括无线定位、车辆组合定位及车载自组织网等。刘兴川：清华大学深圳研究生院现代通信实验室在读博士研究生，主要研究方向包括WiFi定位、汽车电子等。张超：清华大学深圳研究生院现代通信实验室在读硕士研究生，主要研究方向为汽车电子。5小结本文研究了基于三角形算法及位置指纹识别算法的WiFi无线定位问题，从基础理论和实际测试两个方面进行了探讨研究。理论分析与实验结果均表明，基于WiFi的无线室外定位是可能的；较之于三角形算法，使用位置指纹识别的WiFi定位系统在可用性与定位精度方面都具有较大优势。在本文的实验环境与简单建模