APP下载

基于GA-BP神经网络的超宽带室内定位

2021-11-13薛阳阳

关键词:适应度交叉遗传算法

薛阳阳,沈 重

(海南大学信息与通信工程学院,海南海口 570228)

与主要应用于室外场景的全球定位系统不同,超宽带(Ultra Wide Band,UWB)定位主要用于复杂的室内环境,在商场、机场、生产车间等大型建筑内应用广泛.与传统信号相比,UWB信号具有时域较窄、工作频率极高、占空比极低、频谱宽、能量密度低等特性,使其具有时间分辨率增强、功耗极低和隐蔽性好等优点,故被广泛应用于室内定位[1].由于室内环境存在人员流动、建筑、障碍物等,在定位时会产生非视距(Not Line Of Sight,NLOS)误差以及多径干扰[2].如何降低或消除NLOS误差成为了研究的重点.

目前,UWB室内定位的主要技术有:基于到达角度(Angle Of Arrival,AOA)方法[3]、基于到达时间(Time Of Arrival,TOA)方法[4]、基于接收信号强度(Receive Signal Strength,RSS)方法[5]和基于到达时间差(Time Difference Of Arrival,TDOA)方法[6].由于信道环境的复杂性,受NLOS影响,通常会产生较大的误差.在此基础上许多学者进行了研究,陈小斯[7]等使用差分技术对TDOA算法进行改进,提高了定位系统的稳定性;Shen C[8]等人综合了TDOA和AOA算法的优点,结合最陡下降算法,消除了非视距误差;Li N[9]等使用将布谷鸟搜索算法与BP神经网络进行结合,对TDOA进行校正;Niitsoo A[10]等将深度学习与定位结合起来降低多径干扰对位置估计的影响.虽然传统BP神经网络可以对通信过程中NLOS误差进行修正,但由于BP神经网络是沿误差函数反向传播时梯度下降的方向搜寻,寻找到的阈值和权值有可能是局部最优值.为避免此情况发生,笔者采用遗传算法(Genetic Algorithm,GA)进行优化.自然界种群的进化过程就是对个体基因的择优选取,在个体繁殖的过程中,基因可能发生突变、交叉从而诞生更优秀的基因,具有优秀基因的个体更容易存活下来.在多代繁殖后,种群中存活下的都是优良个体.遗传算法模仿上述过程,对BP神经网络中的参数编码形成种群并进行种群进化.进化结束后,对种群中最优良个体进行解码获取最优参数并用其构建BP神经网络定位模型.使用模型获取校正过后的TOA值并代入TDOA定位中的Chan算法进行位置估计.

1 算法描述

1.1 BP神经网络BP神经网络通过计算输出值与期望值的误差优化系统的参数.网络一般有一个输入层、一个输出层、一个或多个隐含层,参数为层与层之间的权值和阈值[11].其拓扑结构如图1所示.

图1中X i为神经网络的M个输入,ωij为输入层到隐含层的权值,输入到达隐含层时需经阈值t j判断是否能够激活神经元,若输入大于阈值t j则使用激活函数S(x)获取Y j,同理得隐含层到输出层的权值γjk,输出层阈值k k,隐含层到输出层输出Z k.其中激活函数为便于后续计算,选用Sigmoid函数,其公式为

图1 BP神经网络的拓扑结构

BP神经网络首先通过正向传播过程获取输出,将输出和期望输出之间的误差反向传播,沿误差函数梯度下降的方向求解最小值,此时神经网络的参数为梯度下降算法搜寻到的最小解.假设期望输出为r=[r1,r2,…,r O],则其误差函数为

1.2 遗传算法遗传算法通过模拟大自然生物的自然选择和遗传学机理搜寻最优解.该算法属于全局搜索算法[12],其对模型整体的优化性能十分优秀,其算法流程如图2所示.

图2 遗传算法流程图

遗传算法的主要过程为:1)对算法中的参数设置初值,生成一代群体;2)为评价个体的优劣,选用合适的适应度函数计算每个个体的适应度;3)对群体进行选择操作,按照设置概率进行交叉操作和变异操作,在满足设置的终止判断条件后结束训练.

1.3 TDOA定位算法TDOA使用基站之间的时间差信息进行定位.该算法需要基站之间严格地时钟同步[8],假设基站A,B,C的坐标为(x1,y1),(x2,y2),(x3,y3),标签的坐标为(x,y),则其TDOA非线性方程

其中,t0表示标签发送信号的时刻,t1,t2,t3表示基站收到标签信号的时刻,c表示电磁波传播速度.

式(3)可直接使用最小二乘法进行位置估计,但定位精度较差,故需采用其他位置估计算法.采用Chan算法进行位置估计,其优势在于无初始值要求且位置估计精度很高[13].其计算过程为

首先对方程(4)两边平方得

设标签到达A基站和到达其他基站的距离差为d i,1,可知

联立方程(5)和(6)可得

可简化为

其中,

联立式(3)和(5)且取i=1可得

求解该方程可获取d1,再将d1代入方程(8)中即可求出标签的估计坐标(x,y).

为评估TDOA定位性能,选用均方根误差(Root Mean Square Error,RMSE)为评价指标,其计算过程为

其中,(x',y')为标签的真实位置,由该式可知其统计的估计坐标相对于真实位置的偏差.通过对不同定位算法的RMSE分析,可获得其定位过程的平均精度,即可评估出算法的优劣.在TDOA定位过程,对NLOS和LOS环境的区分的依据是TDOA标准差的不同,NLOS环境的TDOA标准差较大,故可以通过提高TDOA标准差来提升NLOS对定位算的影响.

2 GA-BP神经网络算法模型

该模型的算法流程如图3所示,具体说明:

图3 GA-BP算法流程

1)首先确定网络结构,结构如图1所示.采用三基站来对标签进行定位,网络的输入为标签到3个基站的TOA值,输出层为校正后的TOA值.则M=3,O=3.隐含层的数目由经验公式N≥log2M确定,式中N为隐含层神经元个数,设为8.

2)确定需要通过网络优化的参数,该网络需要优化的参数有:w i=[w i,1,wi,2,…,wi,8]T,t i=[t1,t2,…,t8],γj,k=[g j,1,g j,2,g j,3]T,k k=[k1,k2,k2].选取[-1,1]之间的随机数进行参数初始化.

3)遗传算法无法对上述的参数直接进行运算,需要对上述参数进行编码.采用浮点数编码,主要有2点优势:①上述参数为类型浮点数,利于编码计算;②在交叉、变异操作后,依然在选定浮点数的范围,提高了精度.本文中的参数个数可用式(9)计算,计算可得浮点数编码的染色体长度为59.

4)对获取的训练样本数据进行归一化处理并训练网络,计算输出误差,将误差代入适应度函数计算适应度f.适应度函数的选择对遗传算法有着很大的影响,在式(2)中已经获取误差函数,为方便后续获取最大适应度,使用误差函数的倒数作为适应度,公式

5)进行选择操作:常用的选择算子有轮盘赌选择算子、随机竞争选择算子和最佳保留选择算子等[14],在实际测试中轮盘赌选择的误差较大,随机竞争选择周期较长,最佳保留选择性能相对均衡.选取最佳保留选择进行选择操作.在轮盘赌选择的基础上增加对一次选择,降低了误差.选择概率公式为

其中,f i为第i个个体的适应度;L为该种群个体数目.

6)进行交叉操作:常用的交叉算子有高概率下的单点交叉和低概率下的多点交叉,在实验进行过程发现多点交叉产生的优良染色体较少,故采用高概率下的单点交叉.假设需要进行交叉操作的基因为第i个染色体的第k个基因g ik和第j个染色体的第k个基因g jk,则其交换过程

其中,e是一个[0,1]之间的随机数.

7)进行变异操作:浮点数编码要求变异后的基因仍在域内,故需考虑变异操作的边界问题.将基因设为2个方向变异,假设基因的最大值为gmax,最小值为gmin,当向最大值方向变异时,变异幅度不超过gmax-g,当向最小值方向变异时,变异幅度不超过g-gmin,故可得

其中,I是加速后期变异的函数,I c为当前迭代次数,Imax最大迭代次数.

8)判断性能是否满足要求,若不满足要求则解码后进行4)~7)操作,若达到最大迭代次数也结束训练,对适应度最高个体进行解码,得到BP神经网络的最优权值和阈值.使用最优参数构建网络模型,对输入的TOA值校正并使用Chan算法进行位置估计.

3 仿真实验及结果

3.1 实验环境本文实验工具为Matlab2018a.为了进行对比实验,选取了Chan算法、BP-Chan算法和GA-BP-Chan算法进行TDOA定位,分别建立Chan算法定位模型、BP-Chan算法定位模型和GA-BP-Chan算法定位模型.在进行实验前首先测试了基站半径对4种定位模型RMSE的影响,如图4所示.

从图4可知,基站半径对3种算法的影响趋势比较相似,当基站半径为10 m时,3种算法的R M S E均取得较小值.故本文采用的基站半径为10 m.

图4 基站半径对不同算法的影响

在10×10的区域设置3个位置为(0,0),(10,0),(5,5 5)的UWB定位基站构建定位场景.BP神经网络设置3个输入、3个输出,输入的是待测位置与基站的有误差TOA值,输出为校正后的TOA值.有误差的TOA值由UWB信号经过与信道冲击响应卷积之后加入高斯白噪声获取.BP神经网络的最大训练次数设置为4 000,学习效率设为0.02.GA-BP网络中的交叉概率设置为0.60,变异概率设置为0.01,进化的迭代次数为100.

3.2 仿真试验结果将标签以1 m·s-1的速度做匀速直线运动,每隔0.1 s获取一次数据.将获取到的数据分别输入Chan算法定位模型、BP-Chan算法定位模型和GA-BP-Chan算法定位模型,得到如图5所示的不同算法的运动轨迹预测图.

由图5可知,Chan算法和BP-Chan算法运动轨迹与真实轨迹之间偏离较远,而GA-BP-Chan算法的轨迹与真实轨迹比较接近.即在相同环境下,GA-BP-Chan算法的优化效果最优.测试3种算法的抗NLOS能力,在上文提到可以提升TDOA标准差模拟NLOS对定位的影响越来越大,依旧使用RMSE作为评价指标,仿真如图6所示.

图5 算法数据轨迹预测图

由图6可知,当TDOA标准差较小时,3种算法的定位精度都比较理想.当TDOA标准差开始增大时,Chan算法的RMSE快速上升,BP-Chan算法的R M S E也出现了明显的上升,但波动幅度较小,GABP-Chan算法基本是在一个值范围来回波动.由此可知,Chan算法的抗NLOS能力最差,BP神经网络算法的抗NLOS能力其次,且其定位精度在Chan算法上提高了12.82%,GA-BP-Chan算法的抗NLOS能力最强,定位精度相比于BP-Chan提高了16.12%.

图6 不同环境下3种算法的R M S E

在对模型分析后可知,Chan算法的定位误差急剧下降是由于Chan算法在计算过程中将噪声的分布近似于理想高斯分布,而随着TDOA标准差的提升,Chan算法还是将其作为理想高斯分布处理,但此时其方差和期望都与理想高斯分布偏差较大,故R M S E开始急剧上升.BP-Chan算法中,由于BP神经网络对非线性方程的强大处理能力,其对偏差的校正能力极强,但由于BP神经网络中搜寻的参数可能是局部最优解,其对误差的校正能力有限.GA-BP-Chan算法中,使用遗传算法优化了对BP神经网络参数的搜寻,搜寻BP神经网络的全局最优解,提升了其对误差的校正能力,故其定位性能最好.

4 结束语

为了提高复杂室内环境下UWB定位的抗NLOS能力,将GA-BP神经网络应用于UWB室内定位中,使用BP神经网络提升UWB定位系统的抗NLOS能力,利用遗传算法可以将全体解搜索出来的特性,对局部最优解问题进行优化,从而提高了算法的定位精度.实验表明,使用GA-BP-Chan算法进行定位时,算法预测轨迹和实际轨迹基本吻合.对3种算法不在同环境下的RMSE进行分析可知,GA-BP-Chan算法的抗NLOS能力最强,且相比于BP-Chan算法,定位精度提升16.12%.将该方法在三维空间的定位是下一步研究重点.

猜你喜欢

适应度交叉遗传算法
改进的自适应复制、交叉和突变遗传算法
基于改进遗传算法的航空集装箱装载优化
菌类蔬菜交叉种植一地双收
基于改进遗传算法的航空集装箱装载问题研究
基于遗传算法的高精度事故重建与损伤分析
“六法”巧解分式方程
物流配送车辆路径的免疫遗传算法探讨
启发式搜索算法进行乐曲编辑的基本原理分析
连数
连一连