基于WiFi的室内定位算法的研究

肖静，薛楠，高员

（1.工业和信息化部电子第五研究所，广东广州510610曰2.工业和信息化部电子第五研究所华东分所，江苏苏州215000）

基于WiFi的室内定位算法的研究

肖静1，薛楠2，高员1

（1.工业和信息化部电子第五研究所，广东广州510610曰2.工业和信息化部电子第五研究所华东分所，江苏苏州215000）

院随着现代社会科技水平的不断提高和通信技术的愈加完善，定位技术受到了用户越来越多的关注遥WiFi定位技术具有在室内获取便利尧覆盖范围广尧信息传输速度快和搭建成本低廉等优点而得到了广泛的应用遥提出了一种基于WiFi技术的位置指纹定位算法，称为快速定位算法，极大地提高了计算效率，并且仍然能够保持室内定位的精确性遥基于此，设计并实现了应用于Android终端的室内定位系统遥

院无线保真曰位置指纹定位技术曰匹配算法

0 引言

人们在日常生活中迫切地需求具体的位置信息，当置身于陌生的环境中时更是如此，定位技术正是为了满足人们的这种需求而逐渐地发展起来的一种技术遥定位技术分为室外定位技术和室内定位技术遥在室外定位领域，一般采用GPS技术进行定位，EPS定位系统得到了广泛的应用曰而在室内定位领域，由于GPS信号受到建筑物尧室内物品的干扰，信号会出现衰减，定位精度低，因而使用GPS无法满足室内定位的要求遥而WiFi网络具有通信快速尧部署方便的特点，因此，其在室内场所广受欢迎，将WiFi技术应用于室内定位成为了目前的一个研究热点遥

利用WiFi的信号强度进行定位的技术主要分为两种，即传输损耗定位法和位置指纹定位法遥前者将信号强度计算折耗后转化为距离测量值并建立数学模型，但是，信号在传输的过程中由于受到距离尧障碍物等因素的影响而产生的折耗并不能被准确地估量，所以利用传输损耗法难以建立准确的模型并保持稳定的精度曰采用位置指纹法进行定位的精度高，但事先需要建立一个完整尧科学的数据库幷进行维护遥

1 位置指纹定位技术

一个终端发射的无线信号经过反射和折射产生的多径信号在稳定的环境中的任一位置处表现的特征性质都是唯一的，这种特征性质便可以被用做指纹遥一个指纹信息关联一个位置信息即可将采集到的无线信号转变为输出的位置信息，从而实现定位的功能遥

位置指纹定位一般分为离线阶段和在线阶段遥离线阶段需要在待定位的区域中采集无线信号信息，将在参考点采集的无线信号的信息和参考点的空间位置存入数据库中曰在线阶段需要在待定位区域中的一个位置处采集无线信号信息，通过匹配算法输出所在的空间位置遥

采用位置指纹定位技术，可以利用现有的AP热点，不需要增加其他设备，而且定位的精度高，但是需要在离线阶段建立数据库，而且对数据库的更新维护需要花费大量的时间遥

2 匹配算法

根据测量结果可知，WiFi信号的强度一般分布在-30～120 dBm之间，负号后面的数值越小则信号的强度越大遥即使在日常生活中我们也能发现WiFi信号时好时坏，事实上，WiFi信号的强度具有时变的特性，所以采用位置指纹定位的方法进行定位时在在线阶段不能直接地使用WiFi信号强度进行匹配，本文采用将WiFi信号强度的大小转化为信号热点之间的关系记录并进行匹配遥

图1为用户和信号热点的示例图，该环境由ROOM1和ROOM2两个房间组成，两个房间中分布了USERA尧USERB和USERC 3个用户，房间外部存在AP1尧AP2尧AP3尧AP4尧AP5和AP66个信号热点遥首先，在离线阶段采集USERB和USERC处的信号强度，所得到的结果如表1所示遥

图1 用户和信号热点示例图

表1USERB和USERC处采集到的信号热点的信息

表1为在同一地点多次采集的信号信息取平均值后的结果，按照信号强度的值由大到小进行排序遥考虑到信号热点-信号强度这组值在在线阶段难以进行匹配，所以将其转化为信号热点-信号热点的形式遥具体的操作是将比信号热点的信号强度小X dBm的信号热点作为该信号热点的值遥

表2为根据信号热点-信号强度形式的数据转化形成的信号热点-信号热点数据遥考虑到WiFi信号的时变特性，此处X取的值为10遥此时离线阶段的工作完成遥

在线阶段采用的匹配算法如下所述:

表2 信号热点-信号热点形式的信号热点信息

即在待定位的位置以信号热点-信号强度的形式采集此处的WiFi信号信息，随后将其转化为信号热点-信号热点的形式遥然后，与在离线阶段采集到的每一处信息进行匹配，匹配规则如下:AP热点都相同的情况下，存在相同的AP热点的信号热点的值最大的即为待定位点最可能所在的地点遥为了进一步地提高匹配效率，可以先将采集到的待定位数据转化成信号热点-信号热点数据，然后将待定位点的前两个信号热点与离线阶段采集的数据库中的数据的前两个信号热点进行比较，当两个信号热点都不相同时则放弃与此数据进行进一步的匹配，这样一来便可以大幅度地提高匹配效率遥

离线阶段采集的待定位点USERA的信息如表3所示遥

表3 待定位点USERA信息

根据所采集到的待定位点USERA的信息，按照匹配规则，USERB的得分为9，USERC的得分为0，则USERA点更可能存在于USERB处遥

3 匹配算法的优势

目前在室内定位领域普遍使用的是KNN定位算法遥运用K近邻法首先需要知道在线阶段测量得到信号强度均值[s1，s2，噎，sn]和在离线阶段采集得到的信号均值[S1，S2，噎，Sn]之间的距离遥假定待定位区域存在m个参考点，n个AP热点，Sij为待定位区域中第i个参考点处的第j个AP热点的信号强度均值，sj为在线阶段测量得到的第j个AP热点的信号强度均值，i=1，2，噎，m，j=1，2，噎，n遥AP热点的距离可以采用如下公式表示:

3.1 较低的时间复杂度

KNN是一种懒惰算法，离线阶段没有对样本进行分类，在线阶段才去找k个近邻遥这样导致了KNN算法的构造模型很简单，但在对测试样本分类的系统开销大，因为要扫描全部训练样本并计算距离遥而匹配算法在离线阶段采集测量数据时已经对样本进行分类，只需要在在线阶段与待定位的点进行匹配即可，尤其在需要进行连续定位的时候，匹配算法的效率会远远高于KNN算法遥

待定位区域中存在N个AP热点，在在线阶段对一个在离线阶段采集的点判断是否为待定位点所需要进行比较的次数如表4所示遥

表4 算法比较一

在离线阶段采集得到的点是M个的情况下，在线阶段进行匹配所需要进行的总的比较次数如表5所示遥

表5 算法比较二

引入匹配算法中的优化，根据排列组合的规律，在N个AP热点的情况下，某两个AP至少一个排在前两位的情况有4（N-1）浴-2种，而总的排列组合情况为N浴种，则某两个AP至少一个排在前两位的概率约为4/N遥引入优化后在线阶段进行匹配所需要进行的总的比较次数如表6所示遥

表6 算法比较三

因此，AP热点的数量越多，匹配算法的效率就越突出遥

3.2 较小受到错误数据的影响

K近邻算法采用了多次方运算，错误的数据会在进行多次方运算后被放大，直至对最终的结果造成不可忽视的影响遥而匹配算法首先会对采集得到的数据进行两个不同AP热点信号强度的比较，将大小相差超过10 dB的AP取出，这一步骤会使错误的数据有极大的几率被缩小，即使错误的数据经过该步骤处理后未被过滤，在匹配阶段其对最后的得分的影响也是非常微小的遥

4 结束语

本文提出了一种匹配算法，并将其应用到了安卓平台上，实现了一款利用WiFi信号进行室内定位功能的应用程序遥该算法不仅摆脱了传统定位所需要明确的信号发送端的位置的局限性，保证了在不窃取AP热点位置等敏感信息的前提下实现定位的功能，而且比一般的位置指纹定位算法运算量更小，保障了系统的灵活性，可以应用于智能手机等新兴移动终端遥如何进一步地提高匹配算法的计算效率，进一步地提高室内定位的精度是值得研究的问题遥

院

[1]王小平.无线传感器网络定位技术研究[D].长沙:国防科学技术大学，2010.

[2]URNETTE E.Hello，Android:introducing Google爷s mobile development platform[M].London:Pragmatic Bookshelf，2010.

[3]吴彬，李俊娥.无线传感器网络在室内定位中的应用研究[J].计算机科学，2013，40（5）:115-117.

[4]王春东.基于802.11的室内定位算法研究[J].计算机工程，2007，33（7）:94-95.

[5]李昊.位置指纹定技术[J].山西电子技术，2007，36（5）:84-87.

[6]杨清.基于指纹的无线室内精确定位方法研究[D].杭州:浙江大学，2011.

Research on Indoor Positioning Algorithm Based on WiFi

XIAO Jing1，XUE Nan2，GAO Yuan1
（1.CEPREI，Guangzhou 510610，China曰2.CEPREI-EAST，Suzhou 215000，China）

With the continuous improvement of the level of science and technology in modern society and the increasing perfection of communication technology，positioning technology has been paid more and more attention.WiFi positioning technology has the advantages of convenient access in the room，wide coverage，high information transmission speed and low building cost，so it has been widely used.A location fingerprint positioning algorithm based on WiFi technology，namely fast positioning algorithm，is proposed，which greatly improves the computational efficiency，and can still maintain the accuracy of indoor positioning.Based on this，the indoor positioning system applied to the Android terminal is designed and implemented.

WiFi曰location fingerprint positioning technology曰matching algorithm

院TN 926+.24

院A

院1672-5468（2017）03-0044-04

10.3969/j.issn.1672-5468.2017.03.009

院2016-10-09

院肖静（1982-），女，湖北襄阳人，工业和信息化部电子第五研究所软件质量工程研究中心工程师，硕士，主要从事软件测试工作。