采用确定性信号传播模型的普适寻优定位方法

刘 影，李国庆，钱志鸿,刘 丹

(1.辽宁工程技术大学 电子与信息工程学院,辽宁 葫芦岛 125105; 2.吉林大学 通信工程学院,长春 130022;3.大连海洋大学 信息工程学院,辽宁 大连 116000)

0 引 言

随着智能移动终端设备的发展以及人们室内活动时间变长，精确的室内定位逐渐成为刚需。由于Wi-Fi基础设施的广泛部署和可用性，基于Wi-Fi指纹定位方法[1-2]成为室内定位中最具有吸引力的解决方案之一，该方法已被纳入苹果、思科、华为、百度等大公司的定位服务中。

无线Wi-Fi信号可以有多种方式实现定位，一种是利用接收信号强度(received signal strength, RSS)来实现测距；另一种方式是通过“指纹”的方式实现定位。基于指纹的定位方法是利用在不同位置上获取RSS信号具有一定的空间差异，将特定位置上的RSS信号特征作为该位置指纹，从而建立节点位置和指纹关系数据库，将待定位节点获取的指纹与数据库中存储的指纹进行匹配的方式实现对待定位节点位置估计。基于Wi-Fi指纹架构的定位方法[3-4]，其定位精度主要受RSS的波动性[5]影响，使得同一位置点在线阶段采集的指纹和离线阶段采集的指纹不一致，导致指纹定位匹配错误。为了保证指纹库的有效性需要重新获取指纹库，又会消耗大量的人力，因此，出现了指纹地图自动构建方法[6]。该方法大部分都是利用各种现有移动设备作为指纹参考点，自动收集这些设备的信号强度及移动轨迹，再利用这些信息实现指纹参考点的定位[7-9]。其中，移动设备的移动轨迹是利用设备上的惯性传感器(例如，加速度传感器、陀螺仪等)不断采集携带者的运动信息，从而得到位置和指纹的关系。该类方案可以解决由于指纹数据库长时间不更新造成的指纹错误匹配问题，且易于实现，但是目前移动设备上的惯性传感器精度较低，所以自动构建的指纹地图数据具有很大的提升空间，限制了Wi-Fi指纹定位系统的实用性。

直接利用RSS信号进行测距是最普适、简单和易于实现的定位方法。然而，在复杂的室内环境中，由于RSS容易受到移动或固定障碍物遮挡、以及各种信号的干扰、甚至温湿度变化的影响，使得RSS传播过程中产生的损耗程度也不尽相同。为了获得更高的定位精度，贺磊南等[10]根据Wi-Fi信号的多信道，利用多载波相位进行测距，可实现分米级的定位，但该方法需要获取物理层信道状态信息(channel state information, CSI)，CSI 信号难以获取，只能在特定的Wi-Fi 设备上使用。此外还出现对传播模型进行修正的定位方法，例如，李腾非等[11]将定位分为2个阶段：第1阶段采用非测距方法；第2阶段采用测距定位。在测距阶段给出了室内和室外环境下有无遮挡时的信号传播模型，设置了信号穿墙的衰减因子、衰减因子可分辨的最大墙面数等参数来提高路径损耗模型的精准性。陈岭等[12]为了简化信号衰减模型复杂性以及参数难确定的问题，提出使用较少参数来刻画无线信号传播模型，该模型通过距离或信号强度的3次样条插值函数来调整对数-距离损耗模型中的路径损耗因子，计算简单。刘万寿[13]利用BP神经网络方法来拟合RSS与传播距离之间的关系模型，该种方法需要大量迭代，适用于样本特征较多时。基于测距的定位方法受限于参考点的数目以及传播模型的精准性，主要适用于一些对定位精度要求不高或者与其他高精度定位方法相结合的位置服务中。

基于以上分析，本文提出一种确定性信号传播模型的普适寻优定位方法。该算法首先研究RSS信号的统计分布特性，揭示数据内在性质及规律，利用快速搜索和发现密度峰值[14](clustering by fast search and find of density peaks, CFSFDP) 的聚类算法对收集到的RSS信号进行去噪和分类；然后在此基础上建立确定性的信号传播模型，待定位节点根据确定性信号传播模型估计出与无线接入点(access point, AP)之间的距离；最后，通过天牛须搜索方法(beetle antennae search，BAS )[15]进行定位。

1 RSSI测距定位模型

基于接收信号强度指示 (received signal strength indication, RSSI)的Wi-Fi室内定位方法，其核心思想在于将用户终端接收信号强度映射为AP与用户终端之间的距离。在自由空间中，AP和用户终端之间没有障碍物遮挡情况下，用户终端接收信号强度与传播距离的平方线性负相关，表示为

(1)

(1)式中：Pr[W]为用户终端接收信号功率；Pt为AP的传输功率；Gt为AP发送信号的增益；Gr为终端接收信号的增益；L为自由空间损耗因子，计算方法为

(2)

(2)式中：λ为波长，计算方法：如果AP带宽为2.4 GHz，λ=300×106/(24 000×106)=0.125 m;如果AP带宽为5 GHz，λ=300×106/(50 000×106)=0.06 m；d表示距离。

然而，在室内环境中，由于受到各种障碍物的遮挡使信号发生反射、散射或者遮蔽等现象，导致接收端所采集到的信号值携带一定的干扰，使信号分布呈现出不确定性。目前大多研究者通常假设信号的传播满足对数-距离路径损耗模型，采用(3)式所示的路径损耗模型进行距离计算[13]。

(3)

(3) 式中：Pr(d)表示从AP端发射的信号经过一段传输距离d到达用户终端后出现的损耗(单位为dB)；P0(d0)表示距离AP发送端为d0时的路径损耗；n为路径损耗系数；Xσ表示均值为0，标准差σ∈[4,10]高斯分布随机变量。

当待定位节点收到3个AP的信息，进而可建立待定位节点到3个AP节点的距离公式为

(4)

(4)式中：(x,y)表示待定位节点的坐标；(x1,y1)，(x2,y2)和(x3,y3)表示接入点的坐标，接入点为参考点。

2 CB-DSPM寻优的普适室内定位方法

2.1 原始RSS信号的CFSFDP的变换

在复杂的室内环境下，在同一个位置上一段时间内收集到同一个AP的n个信号强度具有一定的时间波动性，如图1。其中，图1a为无干扰环境下，RSS波动为-35～-40 dB；图1b为有干扰环境下，RSS波动为-35～-45 dB，从图1a可以看出，没有干扰环境下RSS波动值达到5 dB。因此，本文在定位前先对收集到的集合F={f1,f2,…，fi，…,fn}利用CFSFDP方法进行预处理，将集合F划分为若干不相交的子集，每个子集称为“簇”，其中，fi表示信号强度RSS。

图1 RSS波动性示意图Fig.1 RSS bias over time

CFSFDP聚类方法主要通过局部密度和距离来刻画聚类中心，具体聚类过程如下。

步骤1将收集到的Wi-Fi指纹信号数据集F映射到二维空间，横坐标为指纹的个数Iη={1,2,…,n}，η为待聚类的指纹数，纵坐标为|F|；计算出任意2个指纹的距离dij=dist(fi,fj)，dist(·)表示指纹fi和指纹fj之间的距离，令dij=dji，i

步骤2采用局部密度ρi来刻画聚类中心的邻居节点个数，局部密度计算方式有2种：①基于Cut-off kernel；②基于Gaussian kernel。前者得到的局部密度为离散值，后者为连续值，根据本文数的特点采用后者方法，因为使用高斯核函数计算局部密度产生冲突的概率更小，如果采用前者方法计算可能会有很多数据点具有相同的局部密度值。ρi表达式为

(5)

(5)式中，dc为截断距离。dc的确定方法：由于dmn=dnm，故聚类中距离dmn总数为K=(1/2)M(M-1),将K个距离进行升序排列，表示为

d1≤d2≤…≤dK

(6)

并取dc=df(Kt)，其中，f(Kt)表示对Kt进行四舍五入运算，t取经验值0.02[14]。

ρq1≥ρq2≥…≥ρqn

(7)

根据距离的含义，则任一个聚类中心与其他聚类中心的距离表示为

(8)

(8)式中，dqwqz为局部密度ρqw和ρqz的欧氏距离。

步骤4在局部密度ρi和任一个聚类中心与其他聚类中心的距离σi确定后，可确定其指纹数据集的聚类中心。当某个指纹点的ρ值较大，同时σ值较大，那么该指纹点成为聚类中心的可能性较大。

(9)

(10)

然后聚类中心点根据ηqw确定该簇内的其他节点cj′，即非聚类中心数据点。

步骤7最后保留簇内数据点最多的簇，并将簇内数据求均值，作为下一步定位使用。

2.2 室内无线信号传播模型的建立

在室内环境下直接利用经验对数-距离路径损耗模型进行距离估计存在较大误差。因此，为了更准确地描述室内环境，本文对实际环境中的测试数据进行拟合，在室内定位空间设置N个采样点，在每个采样点处收集AP的RSS值，则采样点数据集表示为F=[f1,f2,…,fj,…,fN]M×N，其中，F为N个采样点所接收到的信号强度；每个信号向量fj的维数为M，M为数据包的个数，j=1,2,…,N。对这些采样点拟合得到的曲线如图2，建立确定性的信号传播模型(deterministic signal propagation model，DSPM)[15]，表示为

图2 信号强度与距离的拟合曲线Fig.2 Fitting curve of signal strength and distance

d=α1×RSS3+α2×RSS2+α3×RSS+α4

(11)

(11)式中：d表示采样点(接收端)与AP之间的距离，单位m；RSS表示AP发射信号经过距离d到达采样点后出现的损耗，单位为dBm；α1，α2；α3以及α4为拟合所获参数。

图2纵坐标表示采样点距AP的距离，横坐标表示AP发射信号经过距离d到达各采样点后出现的损耗。此确定性模型相比于自由空间的对数-路径损耗模型可以更真实地反映当前环境下信号的传播情况。当环境变化较大时，可通过实际测量数据拟合参数来校准信号传播模型。

待定位节点进入定位区域收集到≥3个AP信号时，首先对采集的原始RSS信号使用2.1节方法进行预处理，利用(11)式可计算出与每个AP的距离，最后由(4)式求解待定位节点的位置。但是待定位节点设备一般在同一时间内只能与1个AP建立关联，所以即使存在3个AP也无法同时计算出待定位节点与各个AP之间的距离，只能以串行的方式进行测距，从而限制了基于测距的定位技术应用。因此，本文提出基于BAS的测距定位算法，是一种搜索逼近的方法。BAS方法原理是根据气味强度来觅食，如果左边收到的气味比右边收到的气味强大，天牛下一步就往左走，否则就往右走。该方法不需要梯度信息、不需要知道函数的具体形式即可实现高效寻优，且运算量大大降低。弥补了测距定位算法误差较大的缺陷以及在Wi-Fi环境下没有足够多AP的实际可应用性。

2.3 CB-DSPM定位算法流程

BAS算法中气味相当于目标函数，CB(CFSFDPB AS)-DSPM的目标函数为待定位节点与AP之间的距离，假设待定位节点收到n个AP的RSS值，建立待定位节点到AP的目标函数为

(12)

利用天牛须方法求解目标函数Gi中的待定位节点的位置坐标(x,y)值，完成对待定位节点的定位，CB-DSPM定位算法具体执行过程如下。

1)待定位节点进入定位区域内收集到AP的信号后，利用CFSFDP方法对数据进行分类处理；

2)将分类后得到的结果利用(11)式计算出待定位节点与AP的距离di，把di代入到(12)式；

3)假设待定位节点的位置初始值随机选取u；

4)在k维空间中，待定位节点移动方向表示为

(13)

(13)式中：rand(k,1)为随机向量；k表示维度；

(14)

(14)式中：u表示待定位节点的位置坐标；d0表示两须之间的距离；ul表示在搜寻区域内左须的位置；ur表示在搜寻区域内右须的位置；

6)根据目标函数Gi，求取待定位节点左右两须的气味强度，确定下一步待定位节点的位置，表示为

(15)

(15)式中：f(ul)表示向左走；f(ur)表示向右走；step表示为步长；sign为符号函数；

7)通过第6)步计算得出的u代入函数Gi中，直至找到Gi的最优值；

8)当有多个AP参与定位时，将有多个AP限定待定位节点的走向，AP数量对定位结果的影响通过仿真结果进行分析。

3 仿真分析

3.1 实验设置

为了验证分类方法、DSPM模型以及BAS优化方法的性能，使用matlab2016a编程工具对本文提出的方法进行仿真验证。

本文所使用的原始数据都来源于实际测试，具体测试位置于辽宁工程技术大学葫芦岛校区实验大楼一楼公共大厅1 980 cm×1 560 cm和静远楼4楼2 000 cm×1 000 cm的公共大厅，测试场景如图3。图3a中，这些区域人员走动频繁，干扰复杂，这个环境下采集的RSS数据具有很强代表性，平面图见图3b。无线网络使用的是华为荣耀路由器，总共部署4个AP的位置为AP1(5,5)，AP2(5,-5)，AP3(-5,5)，AP4(-5,-5) ，随机选取若干个测试点来验证算法的定位性能，测试点A作为坐标轴的中心。

图3 测试场景Fig.3 Testbed

3.2 RSS信号聚类结果

为了使RSS信号适合聚类，本文在每个采样点处连续收集100个RSS数据包，将收集到的RSS数据映射到二维平面，为了接近原始数据分布，将100个数据点的x轴坐标除以10 000，如图4，纵坐标为RSS的绝对值。

图4 节点分布图Fig.4 Distribution of nodes

以图4中节点为例，计算出局部密度ρi和距离σi。决策图如图5，横轴表示局部密度，纵坐标表示任一个聚类中心与其他聚类中心的距离。将局部密度ρ最小、距离σ值最大的点在原始数据包中定义为“离群点”，将此值直接滤除。

图5 决策图Fig.5 Decision graph

滤除“离群点”后，根据决策图5选出ρ较大和σ值较大的2个点作为聚类中心，将剩余的数据分成2类，聚类结果如图6。

图6 聚类结果图Fig.6 Clustering result

3.3 DSPM测距模型性能分析

为了验证DSPM测距模型的性能，在距离AP分别为2，4，6 m的圆周上等间隔选取10个采样点，在每个采样点处收集10个RSS信号，利用DSPM模型计算出采样点到达AP的距离，该测距模型的误差累计分布概率如图7。从图7中可以看出，距离AP 4 m以内的采样点85%误差小于1 m。但该模型参数需要根据实际环境测试获得。

自由空间路径损耗模型(3)式误差的累计分布概率如图8。从图7和图8中可以看出，距AP越远，误差越大，但本文提出的DSPM测距模型要优于自由空间路径损耗模型。

图7 DSPM误差的累计分布概率Fig.7 Cumulative distribution probability of DSPM error

3.4 CB-DSPM定位算法性能分析

3.4.1 收敛速度

BAS方法不需要梯度信息、不需要知道函数的具体形式即可实现高效寻优，且运算量大大降低，目标函数Gi通常在迭代10～20次之后基本可以收敛到最优位置，如图9。

图9 收敛速度Fig.9 Convergence rate

3.4.2 定位效果图

定位区域内随机选取A点坐标为(0,0)和B点坐标为(4,4)，在不同数量的AP下分别定位100次，定位结果如图10。其中，圈表示节点实际位置，*号和+号表示估计出的位置，所有的数据均为实际测量值。当只有1个AP时，从图10a中可以看出，A点经过100次的定位结果分散在(0,0)点的周围，优化误差为2.661 2 m，B点经过100次的定位结果分散在(4,4)点的周围， B点优化误差为1.638 9 m；当只有2个AP时，从图10b中可以看出，A点和B点的定位结果相对于图10a更加集中，A点优化误差为1.897 7 m， B点优化误差为1.286 1 m；当只有3个AP时，从图10c中可以看出，A点定位结果优于图10a和图10b，A点优化误差为1.631 2 m，但是B点结果较为分散，B点优化误差为2.825 5 m，由于B点定位时选取较远的参考点导致定位精度降低；当只有4个AP时，A点优化误差为1.905 5 m，B点优化误差为3.916 5 m。从这个结果可以看出，并不是AP数量越多越好，需要选出较好的参考点才能达到较好的定位结果。从图10a—图10d可以看出，该方法的整体误差一般在2～3 m左右。

图10 不同AP数目的定位结果Fig.10 Location results of different AP numbers

为了进一步测试CB-DSPM定位算法的有效性，与PSO(particle swarm optimization)-DSPM优化方法、PSO-经典测距模型方法以及基于RSS测距室内定位方法[16]进行对比，结果如表1。其中，CB-DSPM方法、PAO-DSPM方法和PSO-经典测距模型方法每个测试点选择距离最近的2个AP参与定位。从表1可知， BSA与PSO方法相比，收敛速度大大降低，是一种高效的智能优化方法，较适用于移动终端的定位。在3.3节仿真分析中得出DSPM测距模型优于经典的测距模型，因此，CB-DSPM和PSO-DSPM方法误差小于PSO-经典测距模型的误差。基于RSS测距的定位方法与前3种优化方法相比，至少需要3个AP才能实现定位，本文选择4个AP，该方法的定位结果与PSO-DSPM方法结果接近。

表1 算法对比Tab.1 Comparison of several algorithms

3.5 算法时间复杂度

CB-DSPM算法的时间复杂度由2部分组成:CFSFDP的时间复杂度和BAS优化的时间复杂度。假设每个待定位节点采集的RSS数据为n个，对于每一个待定位节点的计算时间复杂度为o(n2)。

聚类算法时间复杂度，计算参数ρi，dij，σi时间复杂度均为o(n2)；任意指纹点需要计算其作为聚类中心rc时的时间复杂度为o(n)；计算簇内节点hqw数量时的时间复杂度为o(n)。因此，CFSFDP的时间复杂度为

o(n2+n2+n2+n+n)=o(n2)

(16)

定位过程中利用BAS算法进行优化，首先计算函数Gi的最优值，假设迭代l次，无论几个AP参与定位的时间复杂度均为o(l)；其次，为了提高定位结果的稳定性，定位节点需要定位m次取平均值，时间复杂度为o(l×m)。因此，BAS的时间复杂度为

o(l×m+l)≈o(l2)

(17)

根据以上分析，由于BAS收敛速度极快，一般10～20次，n的取值为100，因此，整个算法的时间复杂度为

o(n2+l2)≈o(n2)

(18)

4 结 论

本文提供一种基于测距的普适室内定位方法，使用快速数据聚类方法确保RSS数据的稳定性和有效性，为后续自适应信号模型的建立和位置求解奠定基础；建立的DSPM信号传播模型达到对环境表现出一定的适应性；位置求解方法实现简单且收敛速度快，对AP的数量没有限制，多AP或者单个AP都可实现高效寻优，突破了传统基于测距精度受限的问题，定位精度达到了与指纹定位相媲美。并且该方法基于普通的移动终端设备利用已部署的商用Wi-Fi网络完成复杂的定位任务，实现简单且收敛速度极快。