1 引言

作为室外定位系统的补充,室内定位系统逐渐成为目前研究的热点之一。与到达时间(TOA)和到达角度(AOA)两种定位方法相比,由于读取接收信号强度(RSS)值简单、硬件成本低且收发之间无需保持时钟同步,基于RSS的定位方法备受研究人员的关注^[1]。近几年随着可见光通信(VLC)的发展,基于VLC的室内定位逐渐成为研究热点^[2]。与射频通信技术相比,基于发光二极管(LED)通信的室内定位具有3个优点^[3]:定位精度高,可以实现厘米级别的定位精度;频谱资源丰富,属于可见光频谱,无电磁波辐射,可直接在加油站、手术室等电磁波辐射禁止区域使用;多径干扰小,主要存在视距(LOS)通信。

室内可见光定位主要可以分为基于测距与无需测距两种定位方法^[2-3],基于测距的定位方法采用朗伯光源模型得到收发之间的距离,进而实现定位^[4-5]。无需测距的定位方法一般采用指纹匹配的方法实现定位^[6-7]。基于测距的定位方法虽然简单,但需要获得朗伯光源模型的相关参数,实现起来较难。基于位置指纹的定位方法在离线阶段会不可避免地需要采集位置指纹信息,但是定位时无需依赖朗伯光源模型,可以有效地解决获取朗伯光源模型参数难的问题,且定位精度高^[7]。机器学习是常用的指纹定位方法,如K最近邻(KNN)^[8]、极限学习机(ELM)^[9]、随机森林(RF)^[10]及人工神经网络(ANN)等^[11]。文献[ 12]采用加权K最近邻(WKNN)算法实现可见光定位,由于K个最近邻指纹采用不同的权重,取得较好的定位精度。基于机器学习的指纹定位通常将定位区域划分成不同类别的网格,通过训练与学习得到目标所属的类别,但为了提高定位精度,需要大量的样本学习,增加了实际应用的难度。WKNN虽然采用加权的方式实现定位,相比KNN,定位误差得到显著降低,然而权重的计算方法采用RSS向量之间距离的倒数^[12],该权重值计算方法依然不够准确。由于位置指纹满足压缩感知(CS)的稀疏性,因此CS为可见光定位提供了一种新的研究方案。经典的CS算法包括正交匹配追踪(OMP)^[13]、再加权l₁范数最小化(RWl₁M)^[14]及基追踪(BP)^[15]等。CS虽然在基于射频通信的指纹定位中被广泛使用^[16-17],然而在VLC中的研究依然较少,文献[ 13]利用OMP重构算法实现可见光定位,文献[ 14]利用RWl₁M重构算法实现可见光定位。

目前,基于CS的指纹定位存在2个问题:采用线性最小二乘法重构信号,容易陷入局部最优解,从而导致定位误差大;为了提高CS重构信号的准确性,需要较大的观测值,即需要高密度的LED布局,如基于OMP^[13]与RWl₁M^[14]的可见光定位。为了解决这些问题,本文结合粒子群优化(PSO)较强的全局搜索能力及较低的时间复杂度^[18-20],提出一种基于粒子群优化压缩感知的重构算法(PSO-CS算法),并将指纹定位的权重求解问题转换为稀疏矩阵的重构问题,旨在提供一种在低密度LED布局下实现高精度的定位方法。

2 基本理论

2.1 压缩感知

CS表明,当向量X∈ℝ^N是稀疏度为S的信号时,可以利用测量矩阵Φ∈ℝ^M×N和低维的观测向量Y∈ℝ^M,通过CS方法重构出高维的未知向量X∈ℝ^N,CS的基本表达式^[16]为

Y=ΦX,(1)

式中:M为LED的个数,N为指纹点的个数。当M≪N时,(1)式是一个欠定方程组。但当向量X满足稀疏性的情况下,在一定条件下,(1)式可以转换为^[16]

min‖X‖1,subjectto Y=ΦX+ε,(2)

式中:‖X‖₁为向量X的l₁范数;ε为测量噪声。可以利用线性最小二乘法求解出向量X_I∈ℝ^S,即

XI=(ΦITΦI)-1ΦITY,(3)

式中:索引集I∈ℝ^S;Φ_I∈ℝ^M×S表示依次提取测量矩阵Φ对应索引集I的S列,并重新构成矩阵。

2.2 粒子群优化

在经典的粒子群算法中,通过在解空间域内随机产生Q个粒子,每个粒子都有各自的位置与飞行速度,通过不断的迭代,粒子群快速收敛于最优解,其中第j个粒子的速度与位置更新^[18]分别为

vj,k(t+1)=ωvj,k(t)+c1r1[pj,k(t)-xj,k(t)]+c2r2[gk(t)-xj,k(t)],(4)xj,k(t+1)=xj,k(t)+vj,k(t+1)。(5)

式中:t为当前的迭代次数;k为搜索空间的维度,维度大小取决于稀疏度S的大小;r₁与r₂为[0,1]之间均匀产生的随机值;ω为惯性权重,其大小决定粒子的全局搜索能力;c₁与c₂分别为粒子的自我学习能力与社会学习能力;x_j,k(t)与v_j,k(t)分别为第j个粒子在第t次迭代后的位置与速度;p_j,k(t)和g_k(t)分别为第t次迭代后的个体最优解和全局最优解。

3 PSO-CS定位算法设计

3.1 指纹定位模型

基于LED通信的PSO-CS定位模型如图1所示,假设在天花板上均匀分布着M个LED。将定位区域均匀地划分为正方形网格结构,每个网格点称为指纹点,用θ_n表示第n个指纹点的坐标,n=1,2,…,N。网格间距,即最小正方形边长用L表示。从图1可以看出,随机出现的目标会以极大的概率落入由4个指纹点构成的最小正方形网格内,因此指纹定位的问题,即寻找与目标最近邻的4个指纹点,并求解目标与4个指纹点之间的权重值,并将权重求解问题转换为稀疏矩阵的重构问题。

图 1. 基于LED通信的PSO-CS定位模型

Fig. 1. PSO-CS positioning model based on LED communication

下载图片 查看所有图片

3.2 测量矩阵

离线阶段,由N个指纹点构成的RSS测量矩阵Φ∈ℝ^M×N为

Φ=[φ1φ2…φN]=φ1,1φ1,2…φ1,Nφ2,1φ2,2…φ2,N︙︙︙φM,1φM,2…φM,N,(6)

式中:第n个指纹点的RSS测量向量φ_n= [φ1,n,φ2,n,…,φM,n]T,φ_m,n为在第n个指纹点处由光电二极管(PD)读取到来自第m个LED的RSS值。

3.3 观测向量

在线阶段,第l个目标的RSS观测向量Y_l∈ℝ^M×1为

Yl=[φ1,l,φ2,l,…,φM,l]T,(7)

式中:φ_m,l为第l个目标读取到来自第m个LED的RSS值;l=1,2,…,C,C为目标的总数。

3.4 适应度函数

由于压缩感知重构的目的是寻找一个稀疏度为S的解向量X_I,使重构误差最小。而基于压缩感知的指纹定位实质是找到S个最近邻指纹点,并重构出S个指纹点的权重值,因此建立适应度函数,表达式为

F=(Yl-ΨXI)T(Yl-ΨXI),(8)

式中:I=max(Φ^TY_l,S),表示得到Φ^TY_l前S个能量最大的值,能量按照从高到低依次得到对应的索引集I∈ℝ^S;X_I∈ℝ^S表示按照索引集I∈ℝ^S得到对应指纹的权重值向量;Ψ=Φ_I,表示依次提取测量矩阵Φ对应索引集I的S列,并重新构成矩阵Ψ∈ℝ^M×S。因此定位的本质是找到一个解向量X_I=[g₁,g₂,…,g_S]^T,使目标函数F取得最小值,即

XI=argmin(F)I∈RS,subjectto0<gk<1and∑k=1Sgk=1,(9)

式中:g_k为粒子群迭代收敛时第k维输出的全局最优解。

3.5 算法描述

针对传统压缩感知,采用(3)式重构信号时容易陷入局部最优解,且需要高密度的LED布局,因此提出一种PSO-CS算法,其流程图如图2所示。为了使Φ^TY_l的能量值为(0,1],需要先对Φ与Y_l进行l₂范数归一化处理,即,使测量向量φ_n与观测向量Y_l分别满足 ‖φn‖2=1与 ‖Yl‖2=1。初始化参数包括索引集I、稀疏度S、种群规模Q、惯性权重ω、学习因子c₁与c₂、种群的初始位置与速度。T_max表示最大的迭代次数,F_min表示适应度函数的阈值。

图 2. PSO-CS算法流程图

Fig. 2. Flowchart of the PSO-CS algorithm

下载图片 查看所有图片

图2中,通过步骤1)可以得到S个与目标最近邻指纹的索引集I。通过步骤2)粒子群优化,重构出索引集I对应的S个指纹点权重值,虽然剩余的N-S个指纹点权重值为0,通过压缩感知重构后信息丢失,但因为剩余的N-S个指纹点不参与定位,因此对定位结果无影响。PSO-CS算法通过T_max与F_min来判断粒子群停止迭代的条件。

最后,根据步骤3)输出的索引集I和X_I=[g₁,g₂,…,g_S]^T,计算第l个目标的坐标(x_l,y_l),即

(xl,yl)=∑k=1SXI(k)θI(k)∑k=1SXI(k)。(10)

3.6 算法的时间复杂度

PSO-CS算法的时间复杂度如表1所示,步骤1)中求解索引集I的时间复杂度为O(MN)+O(SN),重新构建矩阵Ψ的时间复杂度为O(MS)。步骤2)中,粒子群优化的时间复杂度取决于粒子群规模Q与需要的迭代次数t,最坏情况需要迭代T_max次。步骤3)为输出变量值,时间复杂度忽略不计。根据最近邻指纹的强稀疏性和低密度的LED布局,即S≪N与M≪N,PSO-CS算法的时间复杂度主要取决于N、Q及T_max,近似为O(MN)+O(SN)+O(QT_max)。根据(9)式可知,粒子群需要搜索的维度为S,每个维度的取值范围为(0,1),粒子群需要搜索的维度和每个维度的取值范围都很小,所以总体时间复杂度较低。

4 仿真分析

为了验证所提PSO-CS算法的有效性,对其与如下10种算法进行比对分析。包括5种常用的机器学习,分别为KNN^[8]、ELM^[9]、RF^[10]、ANN^[11]、WKNN^[12];3种常用的压缩感知,分别为OMP^[13]、RWl₁M^[14]、BP^[15];2种被广泛使用的基于测量收发之间距离的定位方法,分别为牛顿迭代(NR)^[5,21]、线性最小二乘法(LLS)^[4,22]。其中ELM、ANN、RF三种机器学习分类的基本原理^[7]:首先,将定位区域划分为若干个相等的网格点,其中每个网格点代表一个类别;其次,利用机器学习算法对每个网格点所属的类别进行训练;最后,与推导的模型进行比较,预测目标的位置。

4.1 测量模型

由于LED是可见光光源,服从朗伯光源模型,在仿真过程中,位置指纹的测量矩阵Φ与目标的观测向量Y_l由朗伯光源模型产生。典型的室内可见光通信主要存在LOS通信,为了不失一般性,同样采用被广泛使用的LOS朗伯光源模型,如文献[ 4-7,12-14,19,23-28]均采用LOS朗伯光源模型。则接收到的光功率值为

Pr=PtrAPD(λ+1)2πd2cosλ(β)Tsgcosα,(11)

式中:P_tr为LED的发射功率;d为LED与PD之间的距离;λ为LED的调制阶数;A_PD为PD的有效面积;β和α分别为LED的辐射角和PD的接收角;T_s和g分别为接收端的光滤波器增益和聚光透镜增益。为了不失一般性,同样假设cos β=cos α=h/d^{[12,14,20,22-24,26]},h表示LED与PD之间的垂直距离。

4.2 参数设置

设置朗伯光源模型的参数为P_tr=5 W,T_s=g=1,PD的接收视角α_FOV=π/2,A_PD=1 cm²,λ=1。为了公平比对,目标总数C为200,且随机均匀地出现在面积为4 m×4 m、距离地面高度为1 m的区域中。KNN与WKNN算法的K值为4,RSS向量之间的距离度量方法采用欧氏距离。PSO-CS、OMP、RWl₁M、BP算法的稀疏度S为4。PSO的参数为ω=1,c₁=c₂=2,T_max=100,F_min=10^-9,Q=50,粒子群的初始位置与速度在(0,1)之间随机产生一个值。M=4,即4个LED均匀地被布置在面积为4 m×4 m、距离地面高度为3 m的天花板上,L为50 cm。ANN与ELM算法的输入层、隐层及输出层的神经元数目分别为4、100及81,激活函数为Sigmoid。在RF算法中,树的数目为30,其中隐层神经元数目与树的数目均为离线阶段进行训练与学习得到的最优值,即分类精度达到最高时对应的取值,且分类方法采用文献[ 7]中的方法。

4.3 结果分析

4.3.1 信噪比R_SN的影响

为了验证所提算法的有效性,分析了不同算法在不同信噪比R_SN下的平均定位误差,其结果如图3所示。从图3可以看出:OMP、RWl₁M、BP、PSO-CS 4种压缩感知算法的平均定位误差受到噪声的影响较小,然而由于LED密度低、观测值不够、采用线性最小二乘法重构的信号容易陷入局部最优解,OMP、RWl₁M、BP 3种算法的平均定位误差较大;ELM、ANN、RF 3种机器学习分类算法的平均定位误差受噪声的影响较大,在低信噪比下,分类的准确度明显下降,平均定位误差明显变大。在样本数量不足的情况下,机器学习分类算法的平均定位误差相对较大,适合粗定位,虽然可以通过提高样本的数量、降低网格的间距来提高机器学习分类算法的准确度,但复杂度会变高,加大了实际应用的难度。KNN算法取K个最近邻指纹点坐标的平均值作为定位结果,相比ELM、ANN、RF算法,平均定位误差较低;WKNN算法采用不同的权重,相比KNN算法,平均定位误差得到进一步的降低,然而即使在高信噪比下,WKNN算法的平均定位误差也无法得到进一步降低,主要由于WKNN算法采用RSS向量之间距离的倒数作为权重,不够准确;与基于位置指纹的定位不同,NR与LLS是通过测量收发之间的距离来实现定位的,算法复杂度虽然低,然而在低信噪比下,平均定位误差较大。虽然在高信噪比下,这两种算法的平均定位误差小,前提是需要准确获得朗伯光源模型的相关参数,实际应用时难度较大,且NR与LLS容易陷入局部最优解,从而会产生较大的定位误差。最后,从图3可以看出,PSO-CS算法的平均定位误差显著低于KNN、ELM、RF、ANN、WKNN、OMP、RWl₁M及BP 8种基于位置指纹的定位方法,即使网格间距为50 cm,在低信噪比下,依然显著优于NR与LLS 2种基于测距的定位算法。

图 3. R_SN对平均定位误差的影响

Fig. 3. Impact of R_SN on average positioning error

下载图片 查看所有图片

4.3.2 定位误差的累积分布函数(CDF)

11种不同算法的定位误差累积分布如图4所示,从图4可以看出,PSO-CS算法的定位误差累积分布明显优于另外10种算法。OMP、RWl₁M、BP 3种压缩感知算法因在低密度LED布局下观测值不够,且采用线性最小二乘法重构信号,容易陷入局部最优解,所以这3种算法的定位误差累积分布比较不理想。在网格间距较大、指纹采样数量较小的情况下,ELM、ANN、RF 3种机器学习分类算法的定位误差累积分布也同样不理想。WKNN算法的定位误差累积分布相对较好,然而因其权重的计算方法不够准确,相比PSO-CS算法,定位误差累积分布依然较差。从图4(b)可以看出,虽然在高信噪比下,NR与LLS 2种算法的定位误差累积分布相对较好,然而与另外9种基于位置指纹的方法不同,NR与LLS是基于测量收发之间距离的定位算法,需要事先获得准确的朗伯光源模型相关参数,实现起来相对较难。

图 4. 定位误差的累积分布。(a)信噪比为10 dB;(b)信噪比为20 dB

Fig. 4. Cumulative distributions of the positioning errors. (a) Signal-to-noise ratio is 10 dB; (b) signal-to-noise ratio is 20 dB

下载图片 查看所有图片

4.3.3 网格间距L对PSO-CS定位算法的影响

PSO-CS定位算法的平均定位误差随网格间距的变化情况如图5所示。从图5可以看出,随着L的降低,在5种不同的信噪比下,PSO-CS算法的平均定位误差都逐渐降低。然而随着指纹采样间距的降低,指纹库规模变大,这会加大离线阶段指纹库的构建难度及算法的时间复杂度,因此在实际的系统设计中,可以考虑在定位误差与算法复杂度之间进行折中处理。从图5也可以看出,即使网格间距达到80 cm,在5 dB的低信噪比下,PSO-CS算法的平均定位误差为9.24 cm,完全符合实际的大部分定位应用场景。

图 5. L对PSO-CS定位算法的影响

Fig. 5. Impact of L on the PSO-CS positioning algorithm

下载图片 查看所有图片

4.3.4 粒子群规模Q对PSO-CS定位算法的影响

PSO-CS定位算法的平均定位误差随粒子群规模的变化如图6所示。从图6可以看出,随着粒子群规模的增加,在6种不同情况下,PSO-CS算法的平均定位误差逐渐降低。粒子群算法的收敛速度快,复杂度相对较低,但当粒子群规模较小时,容易陷入局部最优解,当局部最优解偏离全局最优解时,重构得到的权重值偏离真实值,从而产生较大的定位误差。当粒子群规模为50时,6种不同情况下的平均定位误差都趋于收敛,因粒子群需要搜索的维度为4,每个维度的取值范围为(0,1),粒子群需要搜索的维度和每个维度的取值范围都很小,因此对粒子群规模的要求相对不高,时间复杂度相对较低。

图 6. Q对PSO-CS定位算法的影响

Fig. 6. Impact of Q on the PSO-CS positioning algorithm

下载图片 查看所有图片

4.3.5 稀疏度S对PSO-CS定位算法的影响

PSO-CS定位算法的平均定位误差随稀疏度的变化情况如图7所示。从图7可以看出,在6种不同情况下,PSO-CS算法的平均定位误差都先降低后增加。当S为4时出现波谷,即取4个最近邻值时,平均定位误差最小,所得结果与大部分文献一致,也验证了随机出现的目标会以极大的概率出现在由四个指纹点构成的最小正方形网格内。因此PSO-CS算法的最佳稀疏度为4,如果继续增加S值,不但平均定位误差变大,而且增加了粒子群搜索的维度与算法的时间复杂度。

图 7. S对PSO-CS定位算法的影响

Fig. 7. Impact of S on the PSO-CS positioning algorithm

下载图片 查看所有图片

4.3.6 LED个数M对PSO-CS定位算法的影响

PSO-CS定位算法的平均定位误差随LED个数的变化情况如图8所示。从图8可以看出,在6种不同情况下,随着M值变大,PSO-CS算法的平均定位误差都逐渐降低,但是当M取为4时,6种不同情况下的平均定位误差都趋于收敛,因此PSO-CS算法的指纹定位无需高密度的LED布局就可以实现较低的定位误差。

图 8. M对PSO-CS定位算法的影响

Fig. 8. Impact of M on the PSO-CS positioning algorithm

下载图片 查看所有图片

4.3.7 指纹采样率R_SR对PSO-CS定位算法的影响

为了验证PSO-CS算法具有较好的鲁棒性,即在非均匀的网格结构下依然具有较好的定位性能,引入指纹采样率R_SR,研究其对平均定位误差的影响。在给定的指纹采样率下,采用随机选取指纹的方法,采样率越低,指纹分布密度越低且越不均匀。为了更加准确地得到结果,在相同的采样率下,采用200个目标重复执行50次的平均值方法,结果如图9所示。从图9可以看出,在采样率只有50%、指纹分布密度低且极不均匀的情况下,所提算法的平均定位误差依然较小。为了进一步分析算法的鲁棒性,选取其中的两种情况分析PSO-CS定位算法在采样率只有50%的情况下,重复执行50次的定位结果。从图10可以看出,即使网格间距达到50 cm,在指纹采样率只有50%的情况下,重复执行50次的平均定位误差曲线波动依然较小,当信噪比为10 dB时,方差为2.54 cm,当信噪比为20 dB时,方差为1.38 cm,两种情况的方差都很小。因此,PSO-CS定位算法具有较好的鲁棒性,可以应用于不同指纹分布的定位场景中。

图 9. R_SR对PSO-CS定位算法的影响

Fig. 9. Impact of R_SR on the PSO-CS positioning algorithm

下载图片 查看所有图片

图 10. PSO-CS定位算法的平均定位误差随次数的变化曲线,R_SR=50%

Fig. 10. Variation curve of the average positioning error of the PSO-CS positioning algorithm with the number of times, R_SR=50%

下载图片 查看所有图片

4.3.8 算法的时间复杂度分析

当L=50 cm,R_SN=10 dB时,重复定位200次的平均计算时间如表2所示。从表2可以看出:相比于ELM、RF、ANN 3种分类算法,PSO-CS算法的时间复杂度明显比较低;相比OMP、RWl₁M、BP 3种压缩感知重构算法,PSO-CS算法的平均计算时间虽然相对较高,但依然可以满足实时的定位要求,且平均定位误差得到明显降低;KNN、WKNN、NR、LLS 4种算法的平均计算时间相对较低,但相比PSO-CS算法,4种算法的平均定位误差明显较大。从表2可以看出,相比于KNN、ELM、RF、ANN、WKNN、OMP、RWl₁M、BP、NR、LLS算法,PSO-CS算法的平均定位误差分别降低了75.88%、89.15%、85.44%、90.25%、58.05%、80.82%、86.29%、80.01%、73.57%、76.56%。由于WKNN算法的定位结果相对较好,因此分析WKNN算法与PSO-CS算法取得相近定位精度时的平均计算时间,当R_SN=10 dB时,其结果如表3所示。从表3可以看出,即使L值达70 cm,PSO-CS算法的平均定位误差为5.89 cm。因为WKNN算法采用RSS向量之间距离的倒数作为权重,权重的计算方法为粗略估计方法,即使L值降低到10 cm,平均定位误差依然达到6.18 cm,虽然此时的平均定位误差接近PSO-CS算法,但所需要的指纹数是PSO-CS算法的34.3倍,在实际定位过程中,会极大增加离线指纹库的构造复杂度,且在线指纹匹配的时间也增加了,此时的平均计算时间是PSO-CS算法的2.5倍。

5 结论

目前,基于压缩感知的可见光定位需要高密度的LED布局,采用线性最小二乘法重构信号时容易陷入局部最优解。为了解决这些问题,结合粒子群优化较强的全局搜索能力,提出一种基于粒子群优化压缩感知的可见光定位算法。由于求解权重的搜索维度与取值范围都很小,所提算法的时间复杂度较低,可以满足定位的实时要求。仿真结果表明,当网格间距为50 cm,信噪比为10 dB时,相比于KNN^[8]、ELM^[9]、RF^[10]、ANN^[11]、WKNN^[12]、OMP^[13]、RWl₁M^[14]、BP^[15]、NR^[5,21]、LLS^[4,22]算法,PSO-CS算法的平均定位误差分别降低了75.88%、89.15%、85.44%、90.25%、58.05%、80.82%、86.29%、80.01%、73.57%、76.56%。还详细分析了网格间距、粒子群规模、稀疏度、LED个数、指纹采样率对PSO-CS算法定位误差的影响,所得结果可为实际可见光定位系统的设计提供有益的参考。