一种基于插值的室内指纹定位系统设计与实现*

章晓强,方 飞,应可珍,方 凯,陈庆章,毛科技*(.浙江广播电视大学萧山学院,杭州 30;.浙江工业大学计算机科学与技术学院,杭州 3003)



一种基于插值的室内指纹定位系统设计与实现*

章晓强1,方 飞2,应可珍2,方 凯2,陈庆章2,毛科技2*
(1.浙江广播电视大学萧山学院,杭州 311201;2.浙江工业大学计算机科学与技术学院,杭州 310023)

由于室内环境的复杂性,无线传感器网络WSN(Wireless Sensor Networks)室内定位的精度一直不够理想。本系统在测距定位算法和非测距定位算法的基础上,提出了基于信号强度RSSI(Received Signal Strength Indication)的指纹定位方法。该方法利用Cokriging插值算法建立定位区域的多维RSSI向量指纹,通过匹配目标节点的RSSI向量与指纹RSSI向量确定目标节点的位置范围,最后使用K-中心点聚类算法提取目标节点的实际位置。实际场景实验和仿真实验结果都表明此方法在复杂的室内环境中具有较高的定位精度。

无线传感器网络;室内定位;指纹定位;Cokriging算法;K-中心点

随着无线传感器网络的普及,用户对于传感器设备的实际位置信息重视程度越来越高。目前存在较多的无线定位技术,如GPS、AGPS等室外定位技术和外、WIFI、蓝牙等室内定位技术。其中GPS相对成熟,它采用基于信号传输时间差TDOA来定位[1],此定位技术在室外精度较高。在室内定位领域中,由于室内环境的复杂性和不可控性,因此很多室内定位技术都有特定的应用场景。

目前国内外无线传感器网络室内定位技术取得了显著的成果,指纹定位技术和基于RSSI的定位技术备受广泛关注。指纹定位技术在室内定位领域取得了的一定的进展,如Ma YW等人研发的新颖指纹机制(NFM)室内定位系统[2],该系统使用接收器和发射器获取定位数据,并采用6个定位机制来提高定位精度。Modamed等人使用陀螺仪与指纹匹配算法相结合的室内定位方法对定位结果加以改进,但单陀螺仪的定向方法具有较大的局限性[3-4]。李燕君等人提出利用众包更新指纹库的定位方法,但需定期对过期指纹进行筛减[5]。肖亚龙等人基于不同位置之间信号强度差异表征对应物理空间距离,提出了一种基于多维标度和区域细化的无线室内定位方法[6],该方法有效地减少了训练阶段指纹采集的开销并且提高了定位精度。同时基于RSSI的定位技术的发展也十分迅速,如Sorour S等人利用相邻位置节点的RSSI固有空间相关性提出了一种基于流形对齐的定位方法[7],该方法使用获取的具有RSSI空间相关性的数据集和一部分参考信息,通过半监督学习算法得到待测的位置;但此方法需要对异常值进行过滤而且计算复杂度较高。高仁强等人提出了一种结合模糊数学逻辑(Fuzzy Logic)理论的WiFi定位算法[8],但手持设备接收信号波动性较大影响定位精度。石柯等人针对室内定位中环境复杂、信道拥塞等问题,提出了一种基于支持向量回归的802.11无线室内定位方法[9],该方法有效地提高了最终的定位精度。徐琨等人针对未知发射功率会降低网络定位性能的问题提出了一种针对未知发射功率的室内定位优化算法,该算法很好地提升了定位性能[10]。基于传播损耗模型来提升定位精度也有一定的发展,如王跃等人针对室内定位接收功率干扰导致估计位置精度偏低的问题,提出了采用马儿可夫蒙特卡洛(MCMC)抽样来提高定位精度的室内定位算法[11]。陈文建等人结合地理编码原理和二维码技术提出了QR(Quick Response)标识导向的室内定位方法[12],提升了创新应用的新平台。现存较多室内定位方法的定位精度都有显著的提升,但指纹定位法的精度明显高于传播模型法[13];由于传统基于RSSI指纹定位算法在建立指纹过程中工作量较大,需要对测量点逐个进行RSSI值测量;本文针对此问题设计了一种基于Cokriging插值算法的多维RSSI指纹定位系统,该系统仅需测量定位区域内已知位置的少量样本节点的RSSI值就能对定位区域内的未知位置点RSSI值进行最优无偏估计,最后采用匹配算法计算出节点的实际位置。

1 系统模型

本系统采用无线传感器网络定位技术,适用于所有类型的室内网络下。首先将传感器节点部署到定位区域内,信标节点之间依次广播信号,然后传感器节点将接收数据包所获取的RSSI值发送至Sink节点,Sink节点再将收到的数据包通过串口发送至后台控制端,最后后台控制端进行数据处理之后返回定位节点的实际位置。本系统使用Tinyos操作系统开发传感器节点,后台控制端使用linux操作系统。

本系统采用Crossbow technology公司生产的Micaz传感器节点,该节点的精确度较高,主要分为以下几个模块:传感器模块、数据处理模块、无线通讯模块和供电模块,数据处理模块采用的是ATMega128L处理芯片;该节点可搭载温度、湿度、光照等传感器。

2 算法设计

本系统的定位方法分为以下几个步骤:Kalman滤波、Cokriging插值算法、多维向量指纹构建、向量匹配算法和K-中心点算法聚类提取定位结果。由于传感器节点的接收信号强度存在多径效应,本系统采用Kalman滤波进行异常值过滤;在少量已知位置样本节点的情况下,本系统采用Cokriging插值算法对定位区域内未知位置的RSSI值进行无偏最优估计;再根据Cokriging插值算法得到的RSSI值构建定位区域的多维向量指纹;最后使用K-中心点聚类算法提取定位结果作为定位节点的实际位置。以下小节分别介绍了算法设计中部分具体实现过程。

2.1 协同克里格插值算法

协同克里格(Cokriging)算法能够对有限区域内的区域化变量进行最优、无偏地估计,因此能够很好地适用于区域内的RSSI值预测。协同克里格算法是指除了主变量外,同时还引入了协同区域变量的一种多变量的克里格算法;协同区域化变量是指在同一空间域内既有空间相关性又有统计相关性特点的一组变量[14]。本系统采用的协同克里格算法以RSSI为主变量、LQI(链路通讯质量)为辅变量进行计算;因为RSSI和LQI在空间分布上呈正相关,因此符合此算法的变量要求。这两个变量除了进行自相关性预测外,还进行两变量间交叉相关性的预测,因此协同克里格算法在理论上具有更高的精确度。协同克里格算法具体的实现过程如下:

图1 样本配对关系图

2.1.1 建立依存关系

若使用Cokringing插值算法预测未知位置RSSI值,首先我们需要建立样本之间的依存规则。本系统使用采集的样本节点RSSI值和LQI值来进行对定位区域内未知位置RSSI值的预测;首先进行样本之间的配对,所有节点进行两两配对,配对后建立传感器节点之间距离d和RSSI之间的关系对Pairi=(di,RSSIi)和Pairj=(dj,LQIj)。配对过程如图1所示,利用关系对Pair进行自相关性和互相关性的空间建模。

具体步骤如下:

步骤1 根据测量的样本点在空间上的分布情况,分析自相关性的半变异函数,如式(1)所示。

(1)

式中:n表示关系对Pairi的数量,z(xa)和z(xa+h)分别表示配对的两个节点的RSSI值,h表示两节点间距离,γ(h)表示半变异函数。通过式(1)获得各个Pairi的半变异函数值。

步骤2 根据测量的样本点在空间上的分布情况,分析互相关性的半变异函数,如式(2)所示。

(2)式中:n表示Pairi的数量,zi(xa)和zi(xa+h)分别表示两个节点的RSSI值,zj(xa)和zj(xa+h)分别表示两个节点的LQI值,且距离均为h,γij(h)表示互半变异函数,通过式(2)获得各个Pairi的半变异函数值。

步骤3 经过式(1)和式(2)我们得到了关系对Pairi的自相关的半变异值γ(h)(包含RSSI和LQI的两个属性各自的半变异值)和互相关的半变异值γij(h)与对应两节点间距离h的关系,接着采用最小二乘法拟合,拟合建立相关的半变异模型。如图2中三角形代表Pairi关系对,曲线是互变异函数拟合模型的结果,根据拟合曲线匹配一个已有且误差最小的模型,然后根据统计模型生成预测表面,最后成功建立依存关系。

图2 互变异函数拟合图

2.1.2 预测估计

利用自相关的半变异模型和互相关的半变异模型对未知点位置的RSSI值进行最优无偏估计,如式(3)所示。

(3)

式中:Z0i表示待估计位置的RSSI值,Zi和Zj分别表示距离待估计位置最近的节点测量得到的RSSI和LQI值,m和n分别代表RSSI和LQI所对应样本数量(同位属性m=n)。为了满足Cokriging插值算法最优无偏方差估计的要求,本系统必须满足以下两个条件,如式(4)所示。本系统采用距离待预测点最近的4个样本点对

(4)

待估计位置进行RSSI值的预测,m=n=4,并且引入两个拉格朗日公式进行推导可得式(5)和(6)。

(5)

(6)

式(5)和式(6)中:γ11和γ22分别是Zi和Zj的自变异函数的理想模型,γ12和γ21代表的是两变量的互变异函数的理想模型,其中γ12=γ21。求解线性方程组式(4),(5)和(6)即可获得权重系数λi和λj以及两个拉格朗日乘数u1和u2的值,最后由式(3)可得到研究区域内任一点Z0i的插值估计,预测过程采用距离待预测点最近的4个已知样本点进行预测,如图3所示。

图3 预测过程图

2.2RSSI指纹建立

传统指纹构建是一个复杂和繁琐的过程,需要对定位区域内的测量点逐一地测量。本系统采用Cokriging插值算法构建定位区域的指纹,该方法仅需有限的样本点对定位区域内未知位置点RSSI值进行线性无偏的估计;一旦室内环境发生变化,RSSI指纹重构也很方便。

本系统采用25个已知位置的传感器节点组成传感器网络,其中5个用于定位的锚节点,剩余的20个普通节点用于辅助构建定位区域的RSSI指纹,如图4所示,图中5个锚节点依次广播信号,定位区域内建立5维指纹向量。

图4 传感器节点部署图

首先锚节点A向其他节点广播信号,剩余节点接收到锚节点A广播的信号并获取信号强度RSSI值;本系统中已知节点分布在定位区域内的位置是已知的,且节点均能获取到信号强度RSSI值和通讯链路质量LQI值,因此我们就可以建立2.1.1小节中的Pairi和Pairj关系对;再采用Cokriging插值算法对定位区域内未知点位置的RSSI值进行线性最优无偏估计;最后就成功建立锚节点A在定位区域内的单维RSSI向量指纹。剩余4个锚节点采用同样的方法构建向量指纹,那么定位区域内5维RSSI指纹向量就完成构建。定位区域的多维向量指纹构建具体实现过程如下:

步骤1 定位区域的长、宽分别为L 和W,并将它划分为m 行n 列,每个小格子的长和宽分别为Cl=l/m,Cw=w/n,如图5所示。

图5 定位区域划分

步骤2 上一步骤将定位区域划分后,在这一步骤中利用Node节点建立的Pairi(RSSI)和Pairj(LQI)与h的关系,通过Cokriging插值算法计算每个小格子对应的RSSI值。这样就建立了信标节点A 对应的单维度指纹fA,fA是一个m×n的指纹。

步骤3 通过上一步我们建立锚节点A的RSSI指纹向量,同样对B、C、D、E锚节点重复进行步骤2操作就可以分别建立单维度指纹fB、fC、fD和fE,最后对定位区域内的fA、fB、fC、fD和fE的5个RSSI指纹向量做并集,如式(7)所示。

Ffinger=fA∪fB∪fC∪fD∪fE

(7)

2.3 匹配定位算法

在2.2小节成功构建了定位区域内的多维RSSI向量指纹,用于此小节对目标节点实现定位。多维RSSI指纹向量构建成功之后,将定位区域内的普通节点全部撤离定位区域,目标节点进入定位区域内,5个锚节点依次向目标节点广播信号,如图6所示,红色三角形代表目标节点。目标节点先获取到一个有序的5维RSSI指纹向量T5,如式(8)所示,再进行基于向量相似度算法的匹配,具体的向量相似度匹配定位算法如表1所示,提取出向量相似度最高的Number个小格子,即可获得定位结果的定位范围。

(8)

图6 目标节点定位区域图

表1 向量相似度匹配定位算法

2.4K-中心点算法聚类提取定位结果

因为实验过程中可能存在误差,所以在2.3小节提取出向量相似度最高的Number个小格子中存在一些误差小格子。本系统采用文献[15]的K-中心聚类算法将误差范围剔除,2.3小节提取的Number个小格子分布如图7所示,斜线阴影部分表示误差较大的格子,这些格子的数量比较少,全阴影的格子表示精度较高的格子,这些格子数量比较多。我们使用K-中心点聚类算法对Number个结果进行聚类,将得到一个含有格子数最大的簇,此簇的簇首作为目标节点的实际位置。如果我们将m×n个格子分的足够细,那么节点的定位误差控制在接受范围之内。

图7 分簇定位图

3 实验

根据以上算法设计,我们设计并开发了一套定位系统,该系统的定位区域为室内一个长为5 m,宽为5 m的正方形,在定位区域内均匀部署25个传感器节点,传感器采用micaz节点,该节点的无线射频芯片为cc2440,其中部署区域4个顶点和部署区域中心部署的共5个节点是用于广播信号的信标节点,信标节点每隔100 ms依次发送广播信号,剩余20个是接收信号的普通节点,普通节点将接收到的信号发送到电脑端建立定位区域的信号强度指纹,定位目标是载着传感器节点的小车。系统将传感器网络信息发送到电脑端进行数据的处理,并定位出小车的位置。以下实验结果都是实物实验重复50次的平均结果。

3.1 插值效果分析

本次实验验证插值算法的准确性,我们选取定位区域内4个固定点,这4个点上放上传感器节点等待接收部署区域中心的信标节点A广播的信号并从数据包中获取RSSI值,然后利用插值算法预测出这4个位置对应的预测值,然后比较实际测量的结果和预测的结果。实验中4个固定点的坐标分别为a(0.75,0.75)、b(0.75,2.25)、c(2.25,0.75)、d(2.25,2.25),实验结果如图8所示,横坐标表示部署区域内普通节点的数量,纵坐标表示RSSI值,实验结果为4个点的RSSI平均值结果。

图8 插值效果图

实验结果表明随着定位区域内部署的节点越多,插值准确度越高,预测结果越接近真实值,并且插值算法预测的RSSI值与实际值比较接近,因此本系统利用插值算法建立定位区域的RSSI指纹是可靠的。

3.2 定位区域划分对定位精度的影响

本系统的方法将定位区域划分为m行n列,划分的精细度不同,定位的精度也不同。由于定位结果是通过计算格子的中心点获得的,因此划分的越粗,定位结果精度越差。实验结果如图9所示。横坐标表示定位区域划分的精细度,纵坐标表示定位的误差(cm)。

图9 定位区域划分精细度对定位精度影响图

实验表明当定位区域划分的精细度越高,定位的精度也越高,但是当划分的精细度高于90×90时,定位精度将不再提高,这是因为划分的精细度越高,每个小格子的面积小于节点实物的面积时定位精度不能再提高了。

3.3K-中心聚类算法提取定位结果分析

本系统利用K-中心聚类算法排除定位误差,实验随机的选取若干点进行定位实验。实验对比了没有利用K-中心点聚类算法和使用K-中心点聚类算法的定位结果,如图10所示。横坐标表示实验次数,纵坐标表示定位误差。

图10 K-中心点聚类提高精度图

实验结果表明使用K-中心点聚类算法提高了定位精度而且精度比较高,而且定位的精度比较稳定。

3.4 LANDMARC对比实验

本次实验采用文献[16]中的LANDMARC算法做对比,由于现存定位实物实验较少,而且LANDMARC算法实现定位精度较高,因此采用LANDMARC算法进行实验对比,我们采用micaz传感器节点实现该算法并开发了系统。该系统同样部署25个节点在长为5 m,宽为5 m的定位区域中,(节点的功能与文献[16]中的RFID标签相同)。实验中将本文提出的定位系统的部署区域划分为m×n个格子,实验结果如图11所示,横坐标表示定位区域划分的精细程度,纵坐标表示定位误差(cm)。

图11 实验结果对比

实验结果表明定位区域划分的精细程度低于50×50时,LANDMARC定位精度更高,因为精细程度不够导致本文提出的方法在匹配定位算法中找到最相似的前Number个小格子的误差相对较大,所以最终的定位结果误差也相对较大;当定位区域划分的精细程度在50×50与90×90之间时,本文提出的定位算法定位精度要高于LANDMARC算法,当精细程度达到一定的阈值时,本文提出的方法就能有效地匹配到最相似的前Number个格子,而随着精细程度的提高,所匹配到的前Number个格子也将离目标位置越接近,因此本文方法的定位结果误差要小于LANDMARC的误差且随着精细程度提高误差会越来越低;当定位区域划分的精细程度高于90×90时,本文的定位算法精度不能继续提高,因为每个小格子的面积小于节点实物的面积。

由于LANDMARC算法的定位精度主要受节点数量的影响,因此当节点数量固定不变时定位误差也维持在20 cm左右。本文提出的定位算法采用Cokriging算法建立了精细的定位指纹然后利用K-中心点聚类排除了误差成分,而LANDMARC算法采用加权的方式计算定位结果且该算法并不能很好的解决障碍物对定位的影响,因此本文的算法具有更高的精度,且本文提出的算法利用协同克里格插值能快速重建定位指纹。

3.5 位系统效果

本次实验验证定位系统的定位精度,在定位区域中随机确定一点,测量该点的实际位置,然后将目标节点放置在该位置,用定位算法计算目标节点的位置。测量得到该位置的坐标s(0.42 m,1.20 m)。实验定位结果如图12所示。一定障碍物环境下的定位如图13所示,红色圈出节点为目标节点。

图12 系统实物定位图

图13 复杂环境定位图

实验结果表明,图12情况下的定位误差在5 cm左右,图13情况下的定位误差在7 cm左右,因此在一定复杂环境下的定位结果的精度相对较高。定位误差主要是由环境因素造成,系统的RSSI值受环境中wifi、蓝牙等无线信号的干扰比较大,所以定位结果还存在误差。

4 总结

本系统提出了一种指纹定位算法,该算法利用协同克里格插值算法建立定位区域指纹,当定位区域环境发生变化时能快速重构定位区域指纹,从而大大减少了工作量。然后利用K-中心点聚类算法提高定位精度。但是系统和算法还存在不足之处,如没有研究传感器节点的天线角度对定位的影响等。因此在将来的工作中,希望将传感器节点的天线角度考虑到本文算法的定位中,从而进一步提高定位精度。

[1] Le T N,Kim J,Shin Y. TDoA Localization Based on Particle Swarm Optimization in UWB Systems[J]. Ieice Transactions on Communications,2011,94(7):2013-2021.

[2] Ma Y W,Chen J L,Chang F S,et al. Novel Fingerprinting Mechanisms for Indoor Positioning[J]. International Journal of Communication Systems,2015,29(3):638-656.

[3] Attia M,Moussa A,Elsheimy N. Map Aided Pedestrian Dead Reckoning Using Buildings Information for Indoor Navigation Applications[J]. Positioning,2013,4(4):227-239.

[4] 胡安冬,王坚,高井祥. 一种基于地图匹配辅助行人航位推算的室内定位方法[J]. 测绘科学技术学报,2014(5):529-532.

[5] 李燕君,徐凯锋,邵剑集. 利用众包更新Wi-Fi室内定位指纹库的方法研究[J]. 传感技术学报,2014,27(12):1692-1698.

[6] 肖亚龙,张士庚,王建新. 一种基于多维标度和区域细化的无线室内定位方法[J]. 计算机学报,2016,39:1-16.

[7] Sorour S,Lostanlen Y,Valaee S,et al. Joint Indoor Localization and Radio Map Construction with Limited Deployment Load[J]. IEEE Transactions on Mobile Computing,2013,14(5):1031-1043.

[8] 高仁强,张晓盼,熊艳,等. 结合模糊数学的WiFi室内定位算法[J]. 测绘科学,2016,10:1-8.

[9] 石柯,陈洪生,张仁同. 一种基于支持向量回归的802.11无线室内定位方法[J]. 软件学报,2014(11):2636-2651.

[10] 徐琨,刘宏立,马子骥,等. 一种针对未知发射功率的室内定位优化算法[J]. 传感技术学报,2016,28(6):961-965.

[11] 王跃,巴斌,崔维嘉,等. 马尔可夫蒙特卡罗的室内定位算法[J]. 西安电子科技大学学报,2016(2):153-158.

[12] 陈文建,王晓蒙,彭玲,等. 一种基于二维码的室内定位方法[J]. 测绘科学,2016(7):1-8.

[13] Hossain A K M M,Soh W S. A Survey of Calibration-Free Indoor Positioning Systems[J]. Computer Communications,2015,34:1-13.

[14] 章清,张海涛,郭龙,等. 基于主成分分析的协同克里格插值模型对土壤铜含量的空间分布预测[J]. 华中农业大学学报,2016(1):60-68.

[15] 王美,李晓峰,孟令军,等. 基于K-中心点算法的TOPO服务器算法的研究[J]. 计算机技术与发展,2014(4):122-125.

[16] Ni L M,Liu Y,Lau Y C,et al. LANDMARC:Indoor Location Sensing Using Active RFID[C]//IEEE International Conference on Pervasive Computing and Communications. IEEE,2003:407-415.

章晓强(1975-),男,汉族,浙江广播电视大学萧山学院教师,主要研究方向为物联网技术,无线传感器网络定位;

方 飞(1993-),男,汉族,硕士研究生,主要研究方向为无线传感器网络;

毛科技(1979-),男,汉族,浙江工业大学计算机科学与技术学院副教授,博士,主要研究方向为无线传感器网络,maokeji@zjut.edu.cn。

Design and Implement of an Interpolation Indoor Fingerprint-Based Localization System*

ZHANG Xiaoqing1,FANG Fei2,YING Kezhen2,FANG Kai2,CHEN Qingzhang2,MAO Keji2*
(1.College of Xiaoshan,Zhejiang Radio and Television University,Hangzhou 311201,China;2.College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)

Because of the complication of the indoor environment,the accuracy of indoor positioning has not been high in Wireless Sensor Networks(WSN). To improve the accuracy,we proposes a fingerprint positioning method based on Received Signal Strength Indication(RSSI)by using range and range-free localization algorithms. The method uses Cokriging interpolation algorithm to establish a multidimensional RSSI vector fingerprint of the target area,and locate the range of the target node by matching the RSSI vector between the target node and the fingerprint. Thenit extracts the actual location of the target node by usingK-medoids algorithm. The simulation and experiment results all show that the proposed method has high positioning accuracy under the complex indoor environment.

wireless sensor network;indoor location;fingerprint-based localization;cokriging interpolation;K-medoids

项目来源:国家自然科学基金项目(61379023);浙江省公益性技术应用研究计划项目(2015C31066)

2016-07-19 修改日期:2016-12-01

TP393

A

1004-1699(2017)04-0596-07

C:7230

10.3969/j.issn.1004-1699.2017.04.020