傅予力;杨帅;陈培林;黄志建;唐杰
【摘 要】Since WiFi is widely used,it is selected as one of the popular technologies for indoor positioning.The positioning accuracy and speed have always been hot research issues.In this paper,an evidence K-nearest neighbor(EKNN) algorithm is proposed for the localization of the region of interest(ROI).In the algorithm,first,by taking a received signal strength indicator as the fingerprint,a wireless fingerprint database is established as a recognition class in each region.Then,based on the evidence theory,the neighbor evidences within each class are combined and the combined results among the classes are fused.Finally,the ROI class of the target is determined,and a precise positioning is performed within this class.As compared with other algorithms,the EKNN algorithm can achieve a recognition rate of 97％ at best and a maximum positioning error of about 2.2 meters as well as a great positioning efficiency improvement.%WiFi由于应用广泛而被作为室内定位的热门技术之一,而定位精度与速度向来是研究的焦点.文中针对室内感兴趣区域(RO
I)的定位问题,提出了一种证据理论K近邻(EKNN)算法.首先以接收信号强度指示作为指纹,在各区域分别建立无线指纹数据库作为识别的类;然后利用证据理论在各类别内进行近邻证据组合、类别间进行证据融合;最后确定目标所在ROI类,并在类中进行精定位.与其他算法相比,文中设计的EKNN算法的最佳区域类识别率可以达到97％,最大定位误差约为2.2m,定位效率也有较大提高. 【期刊名称】《华南理工大学学报（自然科学版）》
【年(卷),期】2017(045)010
泊松比【总页数】7页(P87-92,99)
【关键词】WiFi定位;感兴趣区域;证据理论K近邻算法;无线指纹类数据库;接收信号强度指示
【作 者】傅予力;杨帅;陈培林;黄志建;唐杰
【作者单位】华南理工大学电子与信息学院,广东广州510640;华南理工大学电子与信息学
林产化学与工业院,广东广州510640;华南理工大学电子与信息学院,广东广州510640;华南理工大学电子与信息学院,广东广州510640;华南理工大学电子与信息学院,广东广州510640
【正文语种】中 文
【中图分类】TN925+.93综合自动化
伴随着移动互联技术的快速发展，人们对定位的需求不再局限于户外，室内定位技术已成为一个研究热点.各种室内定位技术中，基于IEEE802.11的WiFi网络技术是室内定位研究领域较为重视的技术之一，它具有以下优势：①覆盖率高，WiFi技术应用广泛，基础设施部署较为完善；②成本低，与其它技术相比，利用现有设施及移动终端即可实现定位；③室内传输距离远，技术资料显示WiFi信号覆盖半径可以达到100 m左右.
WiFi定位常用的方法包括基于信号传播模型的方法和基于信号强度模型的方法，前者有：到达时间法(TOA)、到达时间差法(TDOA)和到达角度法(AOA)[1]；后者有：接收信号强度指示(RSSI)指纹法.由于室内环境比较复杂，干扰因素较多，这给基于信号传播模型的WiFi定位带来巨大挑战，故后者是目前普遍采用的方法，它将RSSI向量作为指纹信息，然后利
用指纹匹配算法实现定位，其前提假设是室内每一个位置的RSSI向量与其位置坐标一一对应[2].
随着WiFi室内定位方法标准的确立，在此基础上需要设计不同的定位算法以满足室内定位多元化应用的需求(例如在涉密场所，当监控目标越权进入机密区域时，需要对其位置进行报告以及跟踪监视；还有像监狱区域监控以及商场店铺指引等应用场景.这些往往都是对室内某些特定局部区域有定位需求，这些区域在文中被考虑为一种感兴趣区域(ROI)[3]).在利用RSSI向量作为指纹信息进行定位的算法中，由于K近邻算法(KNN)简单、易实现，故有关改进KNN算法的研究层出不穷[4]，例如加权K近邻算法(WKNN)，以及近两年提出的增强加权K近邻算法(EWKNN)，它们对KNN算法在定位精度上进行了很大改进.此外，基于概率的贝叶斯和支持向量机(SVM)等分类算法也被应用于WiFi室内定位.然而由于算法的局限性，存在不确定的指纹信息时常会造成误判.文中针对ROI定位，建立一种新模型，设计出基于证据理论的K近邻(EKNN)快速定位算法，其可以对ROI中不确定指纹信息进行准确的判决，通过将DS(Dempster-Shafer)证据组合规则与第5条比例冲突分配规则(PCR5)相结合，识别出目标归属于哪一ROI类；再从构建近邻证据的点中选择最优近邻点及对应的权重集，结合改进KNN的思路进行精定位.而其他精定位算法，如EWKNN，由于限制了近邻
点选择，从而与证据理论难以很好地结合.文中最后在定位平台上对EKNN算法进行了实验，通过将区域类识别率、定位精度及运行时间等指标与其它算法进行比较，验证EKNN的可行性和优越性.
1 基本证据理论
证据理论由美国哈佛大学的数学家Dempster提出，是利用上、下概率解决多值映射问题的一种理论研究[5]，DS证据理论和PCR5规则是对证据理论的发展和完善.
1.1 DS框架下的证据组合规则
DS证据组合规则是对贝叶斯推理方法的推广，无需知道先验概率就能表示不确定信息.以下是DS证据理论的相关概念定义.
(1)mass函数定义
设由基本命题θi组成的集合θ={θ1,θ2,…,θn}为一识别框架，由识别框架中所有子集构成的有限集合记为2θ={∅,{θ1},{θ2},…,{θ1,θ2},{θ1,θ3},…,{θ1,θ2,θ3},…,θ}，称为θ的幂集合，其中∅代表空集，若映射m:2θ→[0,1]满足以下条件：
(a)m(∅)=0;
则称m是2θ上的mass函数，也叫基本概率分配函数(BPA函数).对于框架中任意子集A，若满足m(A)>0，则称A为证据的焦元，m(A)为A的基本置信度指派值.
(2)DS组合规则
设在识别框架θ下，m1和m2分别是指派命题D和命题B的两个BPA，焦元分别为：D1，D2，…，Di和B1，B2，…，Bj.按DS组合规则将两证据组合为[6]
(1)
其中，冲突因子反映证据的冲突程度，是归一化因子，C是在框架θ下组合后的新命题，mDS是新的BPA函数，式(1)可以推广到多证据组合.
1.2 PCR5规则
江民通行证PCR5应用于DS模型框架下的静态或动态证据融合问题时，在识别框架θ下，PCR5规则[7]为
(2)
其中，∀X∈2θ\∅表示X为2θ中任意非空焦元，m12(X)对应两证据取一致的组合结果，即m12(X)=
规则可以将冲突证据按一定比例进行分配，使得高冲突的证据进行融合时不会得出有悖于常理的结论.
2 EKNN定位算法
2.1 定位原理概述
针对室内ROI定位问题，文中提出EKNN定位算法模型，工作原理分为离线和在线两个阶段，如图1所示.
图1 定位算法模型工作原理框图Fig.1 Principle diagram of positioning algorithm model
从武侠到玄幻
2.2 离线阶段
离线阶段根据实际室内环境建立全局RSSI指纹图(Radio Map)，并按室内ROI对指纹进行分类，把包含在某一需要定位区域内的指纹信息归为一类，为区域类识别和精定位提供数据支持.
2.2.1 构建指纹图
指纹图是用矩阵表示RSSI在室内空间上的特性.根据室内环境合理布置无线接入点(AP)，需保证定位区域每一个参考点(RP)能够接收到多个AP的信号，每一个AP都有唯一的MAC地址，也可以设置不同的服务集标识(SSID)对扫描到的指纹进行区分.假设室内区域分布了多个AP，设置了N个RP，可以根据采集的指纹数据建立一张全局指纹图，用矩阵ψ表示：
(3)
其中，xi,j(i=1,2,…,N;j=1,2,…,L)表示第i个RP接收到第j个AP的RSSI在时间上的平均值(单位：dBm)，L表示可扫描到的AP信号的总数.当定位面积很大时，需要布置更多的AP，这将会增加匹配指纹的计算量，文献[8]提供了3种AP选择机制.式(3)中每一个行向量称为RP的特征向量，表示一个RP的RSSI信息
Xi=(xi,1,xi,2,…,xi,L)
(4)
其中，Xi表示第i个RP接收到来自L个AP的RSSI在时间上的平均值(单位：dBm)，它可以作为位置识别特征，与其对应的位置坐标一起存入数据库.
2.2.2 构建区域分类指纹图
针对区域性定位需求，EKNN算法要求对室内全局指纹图在空间上按ROI进行划分，得到表示ROI的指纹图作为判别的类.如图2所示，C1、C2和C3这3块区域均属于ROI，不同的几何形状表示实际中常见的室内环境.
图2 室内感兴趣区域指纹分布示意图
湖南米仓门Fig.2 Schematic diagram of fingerprint distribution in indoor area of interest
以类别C1为例，构建ROI指纹图为
(5)
式(5)中N1(N1<N)表示C1中包含参考点的个数，即在指纹图ψ中选取C1区域中N1个指纹建立类C1.为降低算法复杂度，该阶段需要训练出类的中心点和类中心到边界点的最大距离E1：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议