CN108919182B - 一种wifi环境下基于支撑集及期望最大化的目标定位方法 - Google Patents

Abstract

本发明公开了一种WiFi环境下基于支撑集及期望最大化的目标定位方法，涉及WiFi定位领域，包括如下步骤：步骤1：建立离线指纹库；步骤2：根据线上获取的目标信号和离线指纹库构建支撑集，通过对支撑集进行真值发现估计正确位置完成目标定位；本发明提出利用支撑集克服最优匹配准则的弊端，并通过期望最大化算法从支撑集中进行目标位置的精确估计，能有效克服环境变化和异构设备造成的RSS波动问题，从而提高了定位的精度和稳健性。

Description

一种WIFI环境下基于支撑集及期望最大化的目标定位方法

技术领域

本发明涉及WIFI定位领域，尤其是一种WIFI环境下基于支撑集及期望最大化的目标定位方法。

背景技术

近年来，室内定位技术展现出广阔的发展前景和商业价值，譬如大型超市对货物的跟踪管理，医院对病人的位置实时监控，博物馆内对馆藏物品的导航以及智能家居等各种应用。室内定位系统需要在固定位置安装发射设备用来发送定位信号，常见的发射设备有WIFI、蓝牙、RFID和UWB等，但是安装大量的发射设备需要大量的人力和物力，因此大多数定位系统倾向于使用已有的被广泛部署的无线设备去实现室内定位，其中WIFI已广泛使用在家庭、商场、机场等各类大型或小型建筑内，使得WIFI成为定位领域中一个最引人注目的无线技术。

基于WIFI的定位方法包括两类：基于参数化估计的方法和基于指纹的方法，其中基于指纹的方法由于不需要参数估计以及较好的定位性能而受到广泛关注。但是现有的指纹定位方法使用最优匹配准则来对实测样本进行定位，这种方式易受接收信号强度RSS(Received Signal Strength)波动的影响，使得利用最优匹配准则进行定位通常会匹配到错误的位置，造成较大的定位误差。其中RSS波动的一个主要原因是室内环境的动态特性，其中包括人员走动、门窗的开关、AP的发射功率的变化以及室内环境的温度和湿度改变等因素。另一个主要原因是异构设备，线上定位时，不同用户可能使用不同的设备，由于不同厂商的硬件规格不同，使得不同设备即使在同一位置，同一环境下也会产生很大的RSS波动。目前环境变化和异构设备造成的RSS波动是制约指纹定位方法性能的最大瓶颈，如何寻找一种能够克服复杂室内环境中RSS波动的高精度实时定位系统，已经成为业界的研究重点。

现有技术中一种基于最优匹配准则的传统指纹定位方法，该方法包括以下几个步骤：一、在划分好的格点采集RSS建立线下指纹库；二、在线上定位阶段，利用实测数据的RSS和线下RSS指纹库进行欧氏距离匹配，选取匹配相似度最高的线下指纹对应的格点作为最终位置估计。这种定位方法虽能在简单的室内环境下能取得不错的定位精度，但其仍然面临着室内环境的动态特性和异构设备的挑战：当室内环境多径传播效应强、环境变化较大时，RSS波动会很明显；对于异构设备，线上定位时同一环境下也会产生很大的RSS波动；两中情况导致传统的最优匹配方法失配，使得定位误差较大；因此，需要一种WIFI定位方法能完成在复杂的室内环境中很难形成准确、稳定的目标位置估计。

发明内容

本发明的目的在于：本发明提供了一种WIFI环境下基于支撑集及期望最大化的目标定位方法，解决了现有通过相似度计算实现位置估计无法解决异构设备和环境动态特性的技术问题。

本发明采用的技术方案如下：

一种WIFI环境下基于支撑集及期望最大化的目标定位方法，包括如下步骤：

步骤1：建立离线指纹库；

步骤2：根据线上获取的目标信号和离线指纹库构建支撑集，通过对支撑集进行真值发现估计正确位置完成目标定位。

优选地，所述真值发现包括期望最大化即EM算法。

优选地，所述步骤1包括如下步骤：

步骤1.1：在定位环境中固定AP位置，并将定位环境划分为若干格点；

步骤1.2：搭建WIFI网络，将信号源放置于各格点并记录此时信号源位置坐标；

步骤1.3：已放置的信号源发射信号，记录并存储各AP接收到的信号源的RSS值完成离线指纹库建立。

优选地，所述步骤2包括如下步骤：

步骤2.1：获取实时定位阶段即线上的目标信号，根据目标信号和离线指纹库的相似性构建支撑集；

步骤2.2：使用最优支撑集选择算法确定支撑集的大小；

步骤2.3：使用期望最大化从支撑集中估计目标位置。

优选地，所述步骤2.1包括如下步骤：

步骤2.1.1：获取目标信号

通过欧氏距离d_kn计算目标信号

和离线指纹库r_k(n)的相似度得到距离向量d，计算公式如下：

d＝[d₁₁，d₁₂，…，d_GM]^T

其中，G代表格点个数，M代表离线阶段每个格点的RSS采样个数，k代表格点序号；

步骤2.1.2：选取距离向量d中距离最小的K个距离对应的标签构建支撑集x，计算公式如下：

X＝[x₁，x₂，…，x_K]T

其中，x_i表示距离第i小的线下样本对应的标签。

优选地，所述步骤2.2包括如下步骤：

步骤2.2.1：获取目标信号，通过贝叶斯信息准则BIC进行最优支撑集选择，计算公式如下：

BIC(K)＝ln(K)-2lnL(θ^(t))

其中，θ^(t)为期望最大化收敛后估计的指纹质量，K为假设估计的支撑集的大小；

步骤2.2.2：选择最小BIC对应的K值作为支撑集的大小

计算公式如下：

优选地，所述步骤2.3包括如下步骤：

步骤2.3.1：通过假设定义指纹质量θ，计算公式如下：

其中，N_t表示x中正确位置出现的次数，N_f表示x中错误位置出现的次数，y表示目标位置的标签即格点的序号，y_l表示目标位置标签的估计，x_i表示距离第i小的线下样本对应的标签；

步骤2.3.2：使用贝塔分布和似然函数定义目标函数从而估计指纹质量θ，计算公式如下：

L(θ)＝P(θ|β)P(x|θ)

其中，P(x|θ)是似然函数，P(θ|β)是贝塔分布的概率密度函数；

步骤2.3.3：计算在给定距离第i小的线下样本对应的标签x_i和指纹质量θ下目标位置的标签y的后验概率分布，计算公式如下：

其中，t表示第t次迭代；

步骤2.3.4：最大化目标函数式获得新的指纹质量，计算公式如下：

步骤2.3.5：重复步骤2.3.3和步骤2.3.4直至收敛，收敛条件为L(θ^(t))-L(θ^(t-1))＜ε，即第t次和第t-1次的目标函数之间的误差小于给定门限ε，ε取10^-6，收敛后即得到目标位置的标签y的最终概率分布，计算公式如下：

其中，N为x出现过的不同位置的个数；

步骤2.3.6：基于目标位置的标签y的最终概率分布得到其最大的概率对应的下标

通过如下公式得到目标的标签估计：

将目标的标签估计通过

函数转换为目标的二维坐标完成目标位置的估计。

综上所述，由于采用了上述技术方案，本发明的有益效果是：

1.本发明提出利用支撑集克服最优匹配准则的弊端，并通过期望最大化算法从支撑集中进行目标位置的精确估计，能有效克服环境变化和异构设备造成的RSS波动问题，从而提高了定位的精度和稳健性；

2.本发明使用期望最大化进行真值发现，支撑集的大小可根据线上定位数据动态构建，具有很强自适应性；利用期望最大化对支撑集进行真值发现，能够在正确评价支撑集指纹质量的基础上对目标位置进行精确估计。

附图说明

本发明将通过例子并参照附图的方式说明，其中：

图1是本发明的方法流程示意图；

图2是本发明在环境变化情况下的定位误差图；

图3是本发明在异构设备情况下的定位误差图。

具体实施方式

本说明书中公开的所有特征，或公开的所有方法或过程中的步骤，除了互相排斥的特征和/或步骤以外，均可以以任何方式组合。

下面结合图1-3对本发明作详细说明。

实施例1

真值发现采用期望最大化：

步骤1.1在定位环境中固定好AP的位置并将定位环境划分为若干格点；

步骤1.2.搭建好WIFI网络，依次将信号源置于定位环境中的各个格点并记录下此时的信号源位置坐标；

步骤1.3.已放置的信号源发射信号，记录并存储各AP接收到的信号源的RSS值完成离线指纹库建立；

步骤2.1.获得待定位的目标信号；

步骤2.2.使用最优支撑集选择算法选取合适的支撑集大小；根据目标信号和离线指纹库的相似性构建支撑集；

步骤2.3.使用期望最大化从支撑集中估计正确位置。

实验场地布置

实验环境为73m×20m的办公室环境，位于电子科技大学创新大厦21楼，环境包含10个办公室和一个走廊，九个AP即无线网络接入点均匀的部署在整个环境中，场地划分为175个格点，相邻格点间距0.8m。

获取数据并形成离线指纹库

步骤1.2中.搭建好WIFI定位环境，将信号源即手机置于环境中的任意格点，记录下此时的格点序号和二维坐标，然后发射信号，记录各AP接收到的手机的信号强度，设n时刻第q个AP接收到来自k格点的手机发射的RSS测量值为

假设有L个AP，采集了M个RSS样本，得到在格点k的指纹库D_k：

步骤1.3中.将步骤1.2中的得到的不同格点的指纹库存储下来，得到整个环境的指纹库D：

D＝[D₁,D₂,…,D_G] (2)

其中，G是环境的格点数。

构建支撑集

2.1.1.接收到线上RSS测试样本

再使用欧氏距离d_kn衡量测试样本

和线下RSS样本r_k(n)的相似度：

得到距离向量d＝[d₁₁，d₁₂，…，d_GM]^T。

2.1.2.构建支撑集x，即选取d中距离最小的K个样本对应的标签：

X＝[x₁，x₂，…，x_K]^T (4)

其中，x_i是距离第i小的线下样本对应的标签；为了顺序的获得x_i，先获得最小的距离值和它的索引：

[value，index]＝min(d) (5)

其中，value是最小的距离，index是对应的索引，通过以下公式获取支撑集中第一个标签：

x₁＝ceil(index/M) (6)

其中，ceil(·)的作用是朝正无穷方向取整；

获得x₁之后，更新距离向量d：

d＝d→value (7)

其中→代表从d中删除元素，因此，支撑集x可以通过重复式(5)-(7)获得。

令

为x中出现过的不同的位置，其中N为不同位置的个数，记n＝[n₁，n₂，…，n_N]^T，其中n_l是y_l在x中出现的次数；

最优支撑集选择

2.2.1.为了自适应的对支撑集大小进行选择，采用最优支撑集选择算法，它通过利用贝叶斯信息准则BIC来估计K，贝叶斯信息准则定义为：

BIC(K)＝ln(K)-2lnL(θ^(t)) (21)

其中，θ^(t)是期望最大化收敛后估计的指纹质量，K为假设估计的支撑集的大小；

2.2.2.给定一个线上测试样本

选择最小的BIC对应的K值作为支撑集大小

计算公式如下：

其中，θ^(t)是期望最大化收敛后估计的指纹质量；

最优支撑集选择具体实施如下：EM算法需要给定一个支撑集，支撑集的大小即K采用最优支撑集选择算法确定，一般而言，K的大小可能的取值范围为1到每个格点最大的采样数M之间，首先假设K＝1，进行EM算法得到此时的指纹质量θ^(t)，代入公式(21)计算BIC(1)，再次假设K＝2，计算期望最大化得到此时的指纹质量θ^(t)，并代入公式(21)计算BIC(2)，以此类推，可得到M个BIC(K)值，通过选择最小的BIC值对应的K值来确定最优支撑集大小。

期望最大化

2.3.1.假设支撑集x中的正确位置为y_l即目标位置标签的估计，令N_t表示x中正确位置出现的次数，N_f表示x中错误位置出现的次数，则指纹质量θ可以定义为：

其中，x_i表示距离第i小的线下样本对应的标签；

在实际情况中，θ是未知的，因此使用极大似然估计θ，使用贝塔分布来控制θ的先验，贝塔分布有两个参数β₁和β₂，它们分别代表了x中正确位置和错误位置的伪计数，在本发明中，我们设置指纹质量θ的初值为贝塔分布概率取最大时的值：

令y的概率分布为p＝[p₁，p₂，…，p_N]^T，其中p_l＝P(y＝y_l)(l＝1，2，…，N)代表正确位置为y_l的概率；本发明提出了基于频率和概率联合初始化的策略，对出现次数越多，越靠近几何中心的位置赋予更大的先验概率，因此p_l的先验概率可以定义为：

其中，g(y_l)为目标位置的标签y_l的二维坐标，g(·)是将目标位置的标签映射为二维坐标的函数；

2.3.2.定义目标函数为似然函数和贝塔分布的乘积：

L(θ)＝P(θ|β)P(x|θ) (11)

其中，P(x|θ)是似然函数：

P(θ|β)是贝塔分布的概率密度函数：

最大化目标函数：期望最大化包括两步：期望步(E步)和极大步(M步)，其中E步计算在给定x_i和指纹质量θ下y的后验概率分布，M步更新指纹质量。具体流程如下：

2.3.3.E步：假设现在迭代到第t步，在给定x_i和指纹质量θ^(t-1)后，y_l的后验概率可以表示为：

其中，t表示第t次迭代；

其中式(14)中的第二项由伯努利分布产生：

其中|x_i＝y_l|在x_i＝y_l时为1，反之为0；

正确标签为y_l的概率更新为：

2.3.4.M步：最大化目标函数式(11)来获得新的指纹质量，即

求解方法为对L(θ)关于θ求导，并使其为0来得到θ的估计：

其中，a为支撑集x中正确标签数量的伪计数：

2.3.5-2.3.6.期望最大化将重复E步和M步直至收敛，收敛条件为：

L(θ^(t))-L(θ^t-1))＜ε (20)

选择L(θ^(t))-L(θ^(t-1))＜ε，即第t次和第t-1次的目标函数之间的误差小于给定门限ε作为收敛条件，ε设为10^-6；

假设给定一个实测样本，基于已选择的支撑集大小，通过期望最大化迭代，假设期望最大化在第t轮迭代收敛，y的最终概率分布可以表示为

其中，N为x出现过的不同位置的个数；p^(t)中最大的概率对应的下标为：

目标的标签估计可以通过如下公式获得：

将目标的标签估计通过

函数转换为目标的二维坐标完成目标位置的估计。

现针对正确位置为格点3的测试样本进行算法实测验证，假设通过最优支撑集选择算法得到最优的大小

为10，则根据测试样本和离线指纹库的相似性构建支撑集，得到：

x＝[1，1，11，13，3，1，1，3，9，11]^T

其中y＝[1，3，9，11，13]^T，可以看到，如果根据传统指纹方法中的最优匹配准则，将会得到错误的定位结果1，而本发明提出的支撑集是一个包含正确位置的集合，可以有效克服最优匹配准则在RSS波动大情况下的弊端，然后通过期望最大化在支撑集中进行位置估计，其中贝塔分布的参数设置为

原因是β₁和β₂代表了支撑集中正确位置和错误位置的伪计数，在这种设置下指纹质量的初值θ⁽⁰⁾约为0.25，即代表支撑集中出现次数多的位置可能是错误的，这种现象在RSS波动明显的复杂室内环境中是合理的，同时，y的概率分布初值根据基于频率和概率联合初始化的策略可以得到：

p⁽⁰⁾＝[0.26，0.22，0.19，0.17，0.16]^T

期望最大化进行E步和M步的迭代，最终可以得到期望最大化在迭代t轮收敛后的y的概率分布为：

p^(t)＝[0.16，0.58，0.12，0.09，0.05]^T

得到

最终的位置估计

本发明能从复杂的室内环境中估计出正确的位置，而基于最优匹配准则的传统方法会因为RSS波动而匹配到错误的位置。

本发明设计了两组实验来验证提出算法的优越性，第一组实验是在离线指纹库建立后的一段时间随机采集了975个测试样本进行实测定位，平均定位误差为2.51米，图2为背景技术方法和本发明方法在环境变化情况下的定位误差性能比较图；第二组实验是在离线指纹库建立后使用不同的接收设备随机采集了975个测试样本进行实测定位，图3为背景技术方法和本发明方法在异构设备情况下的定位误差性能比较图；不论是在环境变化还是异构设备情况下，本发明提出的算法都明显好于传统的指纹定位方法，本发明提出利用支撑集克服最优匹配准则的弊端，并通过期望最大化算法从支撑集中进行目标位置的精确估计，能有效克服环境变化和异构设备造成的RSS波动问题，实验结果证明其提高了定位的精度和稳健性。

实施例2

真值发现还可以采用投票法。

Claims (4)

1.一种WiFi环境下基于支撑集及期望最大化的目标定位方法，其特征在于：包括如下步骤：

步骤1：建立离线指纹库；

步骤2：根据线上获取的目标信号和离线指纹库构建支撑集，通过对支撑集进行真值发现估计正确位置完成目标定位；

所述真值发现包括期望最大化即EM算法；

所述步骤2包括如下步骤：

步骤2.1：获取实时定位阶段即线上的目标信号，根据目标信号和离线指纹库的相似性构建支撑集；

步骤2.2：使用最优支撑集选择算法确定支撑集的大小；

步骤2.3：使用期望最大化从支撑集中估计目标位置；

所述步骤2.3包括如下步骤：

步骤2.3.1：通过假设定义指纹质量θ，计算公式如下：

其中，N_t表示x中正确位置出现的次数，N_f表示x中错误位置出现的次数，y表示目标位置的标签即格点的序号，y_l表示目标位置标签的估计，x_i表示距离第i小的线下样本对应的标签；

步骤2.3.2：使用贝塔分布和似然函数定义目标函数从而估计指纹质量θ，计算公式如下：

L(θ)＝P(θ|β)P(x|θ)

其中，P(x|θ)是似然函数，P(θ|β)是贝塔分布的概率密度函数；

步骤2.3.3：计算在给定距离第i小的线下样本对应的标签x_i和指纹质量θ下目标位置的标签y的后验概率分布，计算公式如下：

其中，t表示第t次迭代；

步骤2.3.4：最大化目标函数式获得新的指纹质量，计算公式如下：

步骤2.3.5：重复步骤2.3.3和步骤2.3.4直至收敛，收敛条件为L(θ^(t))-L(θ^(t-1))＜ε，即第t次和第t-1次的目标函数之间的误差小于给定门限ε，ε取10^-6，收敛后即得到目标位置的标签y的最终概率分布，计算公式如下：

其中，N为x出现过的不同位置的个数；

步骤2.3.6：基于目标位置的标签y的最终概率分布得到其最大的概率对应的下标

通过如下公式得到目标的标签估计：

将目标的标签估计通过

函数转换为目标的二维坐标完成目标位置的估计。

2.根据权利要求1所述的一种WiFi环境下基于支撑集及期望最大化的目标定位方法，其特征在于：所述步骤1包括如下步骤：

步骤1.1：在定位环境中固定AP位置，并将定位环境划分为若干格点；

步骤1.2：搭建WIFI网络，将信号源放置于各格点并记录此时信号源位置坐标；

步骤1.3：已放置的信号源发射信号，记录并存储各AP接收到的信号源的RSS值完成离线指纹库建立。

3.根据权利要求1所述的一种WiFi环境下基于支撑集及期望最大化的目标定位方法，其特征在于：所述步骤2.1包括如下步骤：

步骤2.1.1：获取目标信号

通过欧氏距离d_kn计算目标信号

和离线指纹库r_k(n)的相似度得到距离向量d，计算公式如下：

d＝[d₁₁，d₁₂，…，d_GM]^T

其中，G代表格点个数，M代表离线阶段每个格点的RSS采样个数，k代表格点序号；

步骤2.1.2：选取距离向量d中距离最小的K个距离对应的标签构建支撑集x，计算公式如下：

x＝[x₁，x₂，…，x_K]^T

其中，x_i表示距离第i小的线下样本对应的标签。

4.根据权利要求1所述的一种WiFi环境下基于支撑集及期望最大化的目标定位方法，其特征在于：所述步骤2.2包括如下步骤：

步骤2.2.1：获取目标信号，通过贝叶斯信息准则BIC进行最优支撑集选择，计算公式如下：

BIC(K)＝ln(K)-2lnL(θ^(t))

其中，θ^(t)为期望最大化收敛后估计的指纹质量，K为假设估计的支撑集的大小；

步骤2.2.2：选择最小BIC对应的K值作为支撑集的大小

计算公式如下：

Images