基于WIFI BSSID相似度和RSSI概率分布的定位算法

王丽园，吴沐阳，吴家皋,2

(1.南京邮电大学 计算机学院，江苏 南京 210003；2.东南大学 计算机网络和信息集成教育部重点实验室，江苏 南京 211189)

基于WIFI BSSID相似度和RSSI概率分布的定位算法

王丽园1，吴沐阳1，吴家皋1,2

(1.南京邮电大学 计算机学院，江苏 南京 210003；2.东南大学 计算机网络和信息集成教育部重点实验室，江苏 南京 211189)

随着高校的扩大，教室的增多，以及无线网络覆盖率的增大，能够精确定位在校人员所在的教室位置具有重大意义。基于信号强度的定位算法是现今无线网络定位的主要方法。在已有算法的基础上，针对校园环境，提出了基于WIFI BSSID相似度和RSSI概率分布的定位算法。该算法先将当前扫描的BSSID集合与事先采集的数据库中的BSSID集合进行相似度计算，相似度高的位置可判定为定位位置。若存在多个位置相似度基本相同，则进一步根据信号强度的概率分布进行概率加权运算，权值最大的教室位置即为定位位置。实验结果表明，该定位算法在校园室内定位中可以提高定位精确度。因此，基于该校园室内定位算法，可以有助于精确定位在校人员所在教室位置，给在校人员的学习与工作带来便捷。

基本服务集标识符；信号强度；相似性；概率；室内定位

1 概 述

随着无线网络的发展及移动终端处理能力的提高，越来越多的用户希望通过移动终端享受各种便捷服务。移动用户希望在不同地点、不同时间有不同的服务体验。移动终端中自带的全球定位系统模块(Global Positioning System,GPS)、无线局域网(Wireless Fidelity,WIFI)给定位带来了便捷。在室外环境中，用户的密度较低，GPS是一个较好的选择。然而，在复杂的室内环境中，GPS受其自身限制和环境影响，并不能在室内使用[1]。而校园中的WLAN由一个或多个无线接入点构成，更易确定位置[2]。因此，WIFI在室内定位中更具优势。

现有的无线定位技术主要有基于到达时间(Time of Arrival,TOA)、到达时间差(Time Difference of Arrival,TDOA)、信号到达角度(Angle of Arrival,AOA)和信号强度(Received Signal Strength Indicator,RSSI)四种方式。TOA[3]是基于信号到达时间测距的算法，TDOA[4]是利用发送的两种不同信号间的到达时间差进行测距。这两种方法要求系统精确同步，而校园环境访问接入点AP(Access Point)分布有限，传输时延可以忽略不计，因此不宜采用。AOA[5]是基于信号到达角度进行测距，需要增加额外的硬件设施。基于RSSI[6-7]的算法不需要额外的硬件，成本低，适用范围广。文献[8]提出一种基于RSSI的贝叶斯室内定位算法，该算法通过RSSI预处理得到初始坐标，对其进行贝叶斯处理得到准确坐标，该算法降低了定位误差。

基于RSSI定位的算法中，根据数据库中信号指纹表示方式的不同可分为两类：基于概率的定位方法和确定性的定位算法。使用确定性的定位算法是通过求每个节点的信号强度的平均值来估计移动点位置。如K邻近算法(K-NearestNeighborhood,KNN)[9-10]，通过在位置指纹库中寻找与未知节点最接近的多个参考点的平均值，作为未知节点的位置。尽管KNN在算法复杂度与定位精度上具有一定的优势，但是由于K值的固定，最终会影响某些位置的定位精确度。基于概率的定位算法也称贝叶斯概率算法[11]，通过条件概率为位置指纹建立模型，采用贝叶斯推理机制来推断用户所在位置。RoosT等提出了直方图法[12]，该方法将信号强度划分为若干区间，统计每个区间里信号强度出现的次数，将一个待定位的空间分为若干区域，每个区域对应一个强度区间。尽管简单可行，但定位精确度受信号干扰影响较大。文献[13]提出了一种区域投票算法，该算法根据采样点信号强度数据库，求出每个区域对应各个AP信号强度的最大值与最小值，存于数据库，在实时定位阶段根据所采集的信号信息给对应区域投一票，取最多票数的区域为定位定点。该算法利用信号强度的变化特征，定位结果准确。然而，实验测试表明，在校园环境中，由于不同教室的AP信号强度范围比较相似，因此算法定位精确度较小。

文中采用基于概率的RSSI定位算法。在文献[13]的基础上，结合信号强度概率分布的特点，提出了基于WIFI基本服务集标识符(BasicServiceSetIDentifier，BSSID)相似度和RSSI概率分布的室内定位算法。该算法在第一阶段将当前位置的BSSID集合与数据库中的BSSID集合进行相似度计算，排除不可识别位置。如果当前位置存于数据库，且数据相似度较大，则进入第二阶段，将信号强度分为若干段，根据每段的信号强度的概率分布，赋予权值。实验结果表明，在校园环境中，该算法较区域投票算法，定位精度有所提高。

2 系统框架

基于信号强度的无线网络定位系统主要分为离线训练与在线定位两个阶段，如图1所示。

图1 基于WIFI BSSID相似度和RSSI概率分布算法定位过程

在离线训练阶段，通过手机采集大量地理位置的无线网络信号信息，对这些数据进行分析。根据数据规律，建立合适的位置信息数据库—BSSID位置数据库和信号强度概率分布数据库。其中，BSSID位置数据库记录不同位置的BSSID集合，信号强度概率分布数据库记录不同BSSID的信号强度信息。

在在线定位阶段，根据实时收集的BSSID及其信号强度调用定位算法，与数据库进行匹配计算，最终确定定位位置。

3 离线采样阶段

为了实现校园教室的精确定位，需要建立一个精确的校园地理信息指纹库。通过每日不同时段的地理信息采集，将数据进行汇总分析，建立合适的地理信息指纹库。通过对数据表进行汇总分析，进行如下研究。

3.1 教室AP的BSSID相似度的研究

相邻的教室AP的BSSID相似度较高，距离较远的教室BSSID相似度较低，对不同教室的BSSID集合进行相似度分析。

文中通过Jaccard[14]相似系数来衡量两个教室的BSSID集合的相似度。两个教室Ti和Tj的BSSID相似度定义为：

(1)

例如：

S(Ti)={“00:15:70:7e:7f:8c”,“00:15:70:91:99:8c”,“5c:0e:8b:da:10:80”}

S(Tj)={“00:15:70:7e:7f:8c”,“00:15:70:91:66:50”,“00:15:70:91:99:8c”,“5c:0e:8b:da:10:80”}

J(Ti,Tj)=75%,，表示Ti和Tj两个教室的BSSID相似度为75%。

部分测试结果如下所示(其中对应的教室平面图如图2所示):

图2 教室平面图

J(2-104,2-103)=90.0%

J(2-104,2-107)=33.3%

J(2-106,2-107)=91.7%

J(2-107,2-103)=13.3%

通过数据分析，发现相距较远的教室BSSID相似度较低，而相邻教室BSSID相似度较高。所以，BSSID相似度可以判别相距较远的教室。

基于以上分析，通过测量可获得不同教室的BSSID集合。令T为所有教室的集合，并将其保存到数据库中。定位时，将扫描热点得到的BSSID集合与数据库中的BSSID集合进行匹配，根据计算得到的相似度确定位置。

3.2 同一BSSID信号强度的研究

针对特定的BSSID，通过先行的热点扫描软件进行信号强度扫描，获得同一BSSID在不同教室的信号强度概率分布。

通过大量数据分析可知，不同教室的同一BSSID信号强度概率分布不同。由于不同教室同一BSSID的信号强度范围基本相似，如果单取最大值与最小值，则信号强度特征不能得到充分体现，因此不能进行准确定位。基于以上分析，文中对信号强度进行如下处理。

令P(Bi,Tj,x)表示BSSIDBi在教室Tj信号强度为x的概率。其中，信号强度x为整数，x∈[minRSSI,maxRSSI]，minRSSI,maxRSSI为信号强度的最小、最大值。概率归一化条件要求：

(2)

将信号强度范围[minRSSI,maxRSSI]从小到大以每段信号强度的范围为h均匀分段，则M(k)=[minRSSI+kh,minRSSI+(k+1)h-1]，表示第k段的强度范围。其中，k∈[0,L]，L为段数，L=「(maxRSSI-minRSSI+1⎤/h。

则BSSIDBi在教室Tj的第k段信号强度权重定义为：

(3)

通过采集数据得到信号强度概率分布P(Bi,Tj,x),将信号强度进行分段处理，得到k段信号强度M(k)。将两者结合运算得到信号强度权重W(Bi,Tj,k)，存于数据库。

例如，教室分别为2-105、2-204、2-205，minRSSI=-92，maxRSSI=-73，若取h=6,则L=4，各段信号强度范围：M(0)=[-92,-87],M(1)=[-86,-81],M(2)=[-80,-75],M(3)=[-74,-69]。经过计算权重为：W(“5c:0e:8b:d7:40:90”,“2-105”,0)=12%,W(“5c:0e:8b:d7:40:90”,“2-204”,0)=78%,W(“5c:0e:8b:d7:40:90”,“2-205”,0)=62%,W(“5c:0e:8b:d7:40:90”,“2-105”,1)=27%,W(“5c:0e:8b:d7:40:90”,“2-204”,1)=2%,W(“5c:0e:8b:d7:40:90”,“2-205”,1)=14%,W(“5c:0e:8b:d7:40:90”,“2-105”,2)=23%,W(“5c:0e:8b:d7:40:90”,“2-204”,2)=16%,W(“5c:0e:8b:d7:40:90”,“2-205”,2)=18%,W(“5c:0e:8b:d7:40:90”,“2-105”,3)=38%,W(“5c:0e:8b:d7:40:90”,“2-204”,3)=14%,W(“5c:0e:8b:d7:40:90”,“2-205”,3)=6%。

将这些数据存于数据库。实时定位时，如果多次扫描到“5c:0e:8b:d7:40:90”的BSSID，且信号强度为-91，范围在[-92,-87]之内，则给2-105教室权重加12，2-204教室权重加78，2-205权重加62。对实时扫描的每个BSSID的每段RSSI进行权重处理，最终权重最大的教室即为定位教室。

4 实时定位阶段

实时定位过程分为两个阶段，如图3所示。

4.1 第一阶段

扫描用户所在区域N次，得到BSSID集合，通过一级数据库，与数据库中对应BSSID集合匹配，进行相似度计算。如果所有相似度都小于60%，则数据库中不存在当前定位位置，归为不可识别的位置，结束定位。否则，当前位置为可识别的位置，在此基础上，如果相似度大于60%，且数据库中只存在一个与之匹配的位置，则该位置为当前定位位置。否则，扫描二级数据库。

图3 算法流程图

4.2 第二阶段

根据第一阶段扫描得到的BSSID集合及对应强度集合，针对每个BSSID，根据其信号强度，查找该强度在数据库中位于哪段范围，给对应强度段中的位置增加对应的权重。权重最大者即为定位位置。

基于WIFI BSSID相似度和RSSI概率分布的定位算法的伪代码实现如下：

输入：无；

输出：Location,即定位位置。

Begin

扫描N次，得到BSSID的集合S1，对于Bi∈S1，记录其信号强度RSSI的列表R(Bi)

ForeachTi∈T

计算S1和S(Ti)的相似度；

Endfor

If相似度都小于60%Then

Location:=Null，该位置不可识别；

ElseIf有且一个相似度大于60%Then

Location:=Ti,其中,J(Ti,T)>60%；

Else

将J(Ti,T)<60%过滤，得到T'

W(Tj)=0，∀Tj∈T'

ForeachBi∈S

Foreachx∈R(Bi)

Ifx∈R(k)

W(Tj)=W(Tj)+W(Bi,Tj,k);

Endfor

Endfor

Location:=Tj使得W(Tj)取最大值；

EndIf

End

该算法复杂度分为两部分：基于相似度算法与基于信号强度概率分布算法。相似度计算的平均时间复杂度为O(p)，信号强度概率分布算法平均时间复杂度为O(n×m×l)，总的平均时间复杂度为O(n×m×l)+O(p)。其中，p为教室—BSSID数据库中数据记录的条数；n为扫描得到的BSSID个数；m为不同BSSID对应的强度个数；l为BSSID数据库中数据记录的条数。

5 算法测试

算法是在开发环境Eclipse下基于Android4.0实现的。测试设备是HUAWEIC8812，实验地点是南京邮电大学教学楼。

5.1 室内定位测试

由于定位一个教室时，可能会出现定位到周围其他教室的错误结果。结合扫描信息和文中算法计算权值，将权重最大教室与实际所在教室进行对比，验证该定位算法的准确性。

测试使用HUAWEI手机，对20个不同教室进行定位准确度测试，每隔30 s扫描一次教室热点，共扫描4次，数据库中每个BSSID信号强度以h=3为分段值。

实验结果表明，基于WIFIBSSID相似度和RSSI概率分布算法定位精确度较高。

5.2 热点扫描次数对精确度的影响

手机扫描热点，干扰因素较多且耗电量较大。因此在实时定位阶段选择合适的扫描次数，不仅有助于提高定位精确度，同时能减少手机耗能。

图4是扫描次数与定位精确度关系的折线图。实验结果表明，当定位次数达到4次以上，可以在一定程度上避免干扰因素对定位结果的影响。因此，系统实时定位阶段选择每隔30 s进行一次定位，共4次定位。

5.3 分段值h对定位精确度的影响

随着定位数据库的扩充，实时定位数据与数据库的匹配速度会变慢，寻找合适的h值，可以降低算法的复杂度，从而完成快速准确的定位。

图4 扫描次数与精确度关系图

实验通过HUAWEIC8812，于南京邮电大学教二20个教室进行测试，每个目标地址共进行10次测试，其中定位目标教室时每隔30s扫描一次，共扫描4次。实验结果如图5所示。结果表明，当h=3时，定位效果最好。

图5 分段值h与定位精确度关系图

5.4 投票区域选定算法与信号强度加权算法的对比

本次测试通过HUAWEI C8812，于南京邮电大学教二20个教室进行测试，每个目标地址共进行10次测试，其中定位目标教室时每隔30 s扫描一次，共扫描4次。其中数据库中每个BSSID信号强度以h=3为分段值。实验结果见图6。

图6 不同定位算法的对比

由图可知，基于WIFIBSSID相似度和RSSI概率分布算法相比投票区域选定方法，在校园室内定位中定位精确度更高。

6 结束语

基于对WIFI信号特征的分析，在已有算法的基础上提出一种改进的室内定位算法—基于WIFIBSSID相似度和RSSI概率分布的算法。实验结果表明，该算法较大提高了室内定位精确度，但仍存在许多不足：指纹库的建立耗时长且需不断更新；同时，对于不同设备，指纹库适用度低。

该算法可以运用于校园室内定位，通过不同教室的定位，可以给在校人员的工作学习带来便捷，具有很大的实用价值。

[1] 万 群，郭贤生，陈章鑫.室内定位理论、方法和应用[M].北京：电子工业出版社，2012.

[2] 余 涛,黄书宝,葛昭攀,等.无线局域网环境下的位置服务研究[J].计算机工程,2005,31(14):122-124.

[3]LeeWCY.Mobilecommunicationengineering[M].NewYork:McGraw-Hill,1982:20-30.

[4] 史小红.基于TDOA的无线定位方法及其性能分析[J].东南大学学报:自然科学版,2013,43(2):252-257.

[5]DengP,FanPZ.Anefficientposition-baseddynamiclocationalgorithm[C]//Internationalworkshoponautonomousdecentralizedsystems.[s.l.]:[s.n.],2000:36-39.

[6]HataM.Empiricalformulaforpropagationlossinlandmobileradioservices[J].IEEETransactionsonVehicularTechnology,1980,29(3):317-325.

[7] 朱明辉,张会清.基于RSSI的室内测距模型的研究[J].传感器与微系统,2010,29(8):19-22.

[8] 彭玉旭，杨艳红.一种基于RSSI的贝叶斯室内定位算法[J].计算机工程，2012，38(10):238-240.

[9]OutemzabetS,NerguizianC.AccuracyenhancementofanindoorANN-basedfingerprintinglocationsystemusingKalmanfiltering[C]//IEEE19thinternationalsymposiumonpersonal,indoorandmobileradiocommunications.[s.l.]:IEEE,2008:1-5.

[10]RodriguesML,VieiraLFM,CamposMFM.Fingerprinting-basedradiolocalizationinindoorenvironmentsusingmultiplewirelesstechnologies[C]//IEEE22ndinternationalsymposiumonpersonal,indoorandmobileradiocommunications.Toronto,ON,Canada:IEEE,2011:1203-1207.

[11] 王洪春.贝叶斯公式与贝叶斯统计[J].重庆科技学院学报:自然科学版,2010,12(3):203-205.

[12]RoosT,MyllymakiP,TirriH,etal.AprobabilisticapproachtoWLANuserlocationestimation[J].InternationalJournalofWirelessInformationNetworks,2002,9(3):155-164.

[13] 储海兵.基于无线局域网的定位追踪技术研究[D].杭州:浙江大学,2011.

[14]Jaccard.index[EB/OL].[2015-04-05].https://en.Wikipedia.org/wiki/Jaccard_index.

A Positioning Algorithm Based on WIFI BSSID Similarity and RSSI Probability Distribution

WANG Li-yuan1,WU Mu-yang1,WU Jia-gao1,2

(1.College of Computer，Nanjing University of Posts and Telecommunications，Nanjing 210003，China;2.Key Laboratory of Computer Network and Information Integration of Ministry of Education,Southeast University,Nanjing 211189,China)

With the expansion of universities,the increase of classroom as well as the wireless network coverage,to locate accurately the classroom of school personnel is of great significance.Positioning algorithm based on signal strength is popular for wireless network location.On the basis of the existing algorithms,a positioning algorithm based on WIFI Basic Service Set Identifier (BSSID) similarity and Received Signal Strength Indicator (RSSI) probability distribution is proposed for the campus environment.The similarity is calculated between the current scanned BSSID set and that collected beforehand in database,and the position with highest similarity can be determined to be current position.If there are many positions with approximate similarity,weight is calculated according to the probability distribution of the RSSI,and the position with the maximum weight is located.Experimental results show that the positioning algorithm can improve accuracy in campus indoor positioning.Thus,based on that,it can help locate the classroom of personnel and bring convenience to study and life of school personnel.

BSSID;RSSI;similarity;probability;indoor positioning

2015-11-22

2016-03-17

时间：2016-11-21

国家自然科学基金资助项目(61373139)；计算机网络和信息集成教育部重点实验室(东南大学)开放基金(K93-9-2014-05B)；南京邮电大学科研基金(NY214063)

王丽园(1993-)，女，研究方向为移动计算；吴家皋，博士，副教授，CCF会员，研究方向为计算机网络、GIS应用等。

http://www.cnki.net/kcms/detail/61.1450.TP.20161121.1633.016.html

TP301.6

A

1673-629X(2016)12-0200-05

10.3969/j.issn.1673-629X.2016.12.043