基于多目标自适应DE算法在UWB中的应用研究

尤谍, 陈勇, 张修伟, 段刚鹏

(重庆师范大学,计算机与信息科学学院,重庆 401331)

0 引言

室外定位依赖于GNSS,提供载体姿态和位置信息[1-2],具有足够的精度,但它的工作能力仅限于能够实现无遮蔽卫星跟踪的室外环境。环境超出GPS的覆盖范围,室内定位技术不断涌现,比如ZigBee、UWB、Wi-Fi、RFID等定位技术[3-4]。UWB技术被称之为“超宽带”,又称之为脉冲无线电技术,利用纳秒至微秒级的非正弦波窄脉冲传输数据,UWB发射功率很小,应用范围很广[5-6]。UWB具有高时间分辨率和良好的过障能力,能在室内区域实现高精度测距。UWB定位被视为高精度需求的最佳解决方案之一,在室内通信、高速无线LAN、家庭网络、安全检测、位置测定、雷达、医疗及军事领域都有广泛应用。室内复杂环境下超宽带信号传播存在非线性视距(NLOS)误差问题[7]。室内超宽带定位技术关键在于测距,测距主要取决于到达时间(TOA)的估计。TOA存在一些关键挑战,如电子干扰、NLOS条件等。UWB信号在传播过程中不可避免地产生多径效应,从而导致明显的NLOS定位误差。

1 UWB定位技术原理

UWB的定位技术有多种方法,通常采用距离信息定位算法。本文采用飞行时间(TOF)的测距。TOF测距技术是UWB定位法中最常见的定位方法。

1.1 TOF测距技术

双边双向测距原理如图1所示。双边双向测距分2次进行。设备A先发起第一次测距并记录发送的时间戳,设备B收到数据,记录接收时间戳;设备B响应,发送信号给A并记录发送时间戳,当设备A收到数据之后,再返回数据。这样可以得到4个时间差:Tro1、Tro2、Tre1、Tre2。

图1 双边双向测距原理图

由设备A的时间差Tro1、Tro2,设备B的时间差Tre1、Tre2,得到无线信号飞行时间Tp:

(1)

(2)

如Tp1=Tp2=Tp,则进一步计算可得:

(3)

可得到飞行时间TP计算式:

(4)

若响应时间对称,设Tre1=Tre2,则

(5)

2 差分进化算法

2.1 种群初始化

在目标空间中随机产生均匀M个个体,每个个体由n维向量组成,当前世代种群的第i个个体表示方法如下:

(6)

第i个个体的第j维取值方式:

xi,j,0=xj,min+rand(0,1)×(xj,max-xj,min)

(7)

其中,rand(0,1)是介于0到1之间的随机数,xj,min和xj,max分别为xi在第j维的最小值和最大值。

2.2 变异操作

在第G次迭代中,从种群中随机选择3个个体Xp1,G、Xp2,G、Xp3,G且p1≠p2≠p3,则生成的变异向量为

Vi,G=Xp1,G+F(Xp2,G-Xp3,G)

(8)

2.3 自适应交叉

(9)

CR是交叉算子,自适应调整,CRl、CRu是CR的下限和上限。fi是个体Xi的适应度,fmax、fmin分别是当前种群中最差和最优个体适应度。

CR是交叉算子,当rand(0,1)<=CR时,第i个向量的后代ui向量的第j维等于变异向量vi的第j维;否则ui,j等于xi,j;从[1,2,…,D]中随机选择一个数作为jrand,以保证Ui,G至少有一个维度来自Vi,G。

2.4 环境选择

(10)

环境选择过程会根据适应度值作出判断,若子代优于父代则选择子代,反之则选择父代。

2.5 变异策略

为了防止陷入局部搜索,采用3种不同的变异策略:

Vi,G=Xbest,G-F(Xp1,G-Xp2,G)

(11)

Vi,G=Xi,G+F(Xbest,G-Xi,G)+F(Xp1,G-Xp2,G)

(12)

Vi,G=Xp1,G+F(Xp2,G-Xp3,G)+F(Xp4,G-Xp5,G)

(13)

3 多目标差分进化算法

3.1 传统多目标差分进化算法

算法1给出了传统的多目标差分进化算法[8-9]的总体框架。

算法1 传统多目标差分进化算法1 Initialize the population P2 Evaluation(P)3 while gen<=Max_gen4 for each individual p in P5 select individuals to generate difference vector6 v=mutation(p)7 o=crossover(v,p)8 Evaluation(o)9 end for10 C=[P,O]11 nondominated_sorting(C)12 Calculate_crowding_distance(C)13 P=Environmental selection(C)14 end while15 Output the final population P

3.2 改进的多目标差分进化算法

传统的多目标差分进化算法存在2个问题:

(1) 种群中的个体共用相同的参数。比如所有个体使用相同的变异策略以及交叉算子CR等参数。种群中的每个个体所处的环境是不同的,有些个体所处的环境比较拥挤,而有些个体则处于稀疏的环境中,因此对它们使用相同的参数是不合理的。

(2) 参数全局固定。进化算法在初期更侧重于全局搜索、扩大搜索范围,在后期则更侧重于局部搜索。固定的变异策略、交叉算子等参数显然会影响算法的性能。

针对上述问题,提出自适应多目标差分进化算法:

Step 1:根据种群中每个个体所处的环境为其分配参数,且所分配的参数会动态地调整以适应环境的变化。

Step 2:根据拥挤距离的大小,将个体所处的环境划分为3个等级,每个等级使用一套参数。

Step 3:权重系数w会随着迭代的进行逐渐降低算法的搜索能力,在不影响算法前期搜索能力的情况下增大算法后期的局部开发能力。

(14)

(15)

(16)

CD1=CDmin+(CDmax-CDmin)/3

(17)

CD2=CDmax-(CDmax-CDmin)/3

(18)

(19)

其中,gen和Max_gen分别表示当前迭代次数和最大迭代次数,CDmin和CDmax分别为种群中个体拥挤距离的最小值和最大值,CDi为种群中第i个个体的拥挤距离。

3.3 多目标差分进化精确定位模型建立

DE群体中突变和交叉操作被用于探索空间,而选择用来确保有希望的个体可以进一步利用,通过种群不断的迭代变异,估计出Tag的精确位置。根据估计的Tag到锚点的距离和Tag到锚点的真实距离差设置目标函数,提出UWB方法结合多目标差分进化精确定位目标函数为

(20)

(21)

(22)

(23)

其中,(xi,yi,zi)是第i个Anchor坐标,i的范围为[1,4],(x,y,z)是使用此定位模型定位出的Tag坐标,Ri是到Anchor的真实值。目标函数f值越小,(x,y,z)越逼近Tag的精确定位。由此,定位问题可转化为优化问题:

(24)

4 差分进化精确定位模型实验结果

本次实验在室内的测试环境中,分别在测试环境的4个角落A0、A1、A2、A3放置UWB锚点(Anchor),并向所有方向发送信号。Tag是需要定位的目标。其实验场景示意图如图2所示。利用TOF技术,测算飞行时间,按照信号是否有遮挡分为场景1和场景2。

图2 实验测试环境示意图

4.1 已知信号有无干扰定位实验

场景1测得无干扰的正常数据与场景2测得有干扰的异常数据比较,明显异常数据分散,如图3所示。

(a) 场景1

利用多目标差分进化算法定位,结果如图4所示。图中心位置为定位出的Tag位置,四角为Anchor。

(a) 场景1无干扰

为证明此算法定位的精确性,进行误差计算,误差结果如表1、表2所示。表1中,场景1在无信号干扰条件下,计算出Tag坐标为(521.18,520.83,1076.2),单位为mm。

表1 无干扰下定位精度

表2 有干扰下定位精度

表2中,场景2在有信号干扰条件下,计算出Tag坐标为(516.74,525.83,1120.3),单位为mm。

4.2 未知信号有无干扰定位实验

此定位模型可以应用于不同场景,在未知是否存在干扰时,也有良好表现。设置场景3随机施加扰动,将测得的数据进行精确定位实验,结果如图5所示。

图5 未知有无信号干扰定位效果图

场景3在未知是否有干扰条件下,计算出Tag坐标为(518.94,526.12,1100),单位为mm。定位精确度如表3所示。

表3 未知是否有干扰下定位精度

5 总结

实验表明,通过多目标差分算法与UWB定位技术结合,在未知干扰情况的室内环境定位实验中,该方案有优秀表现,具有较强的环境适应性,精度可达毫米级。本算法也存在一定的改进空间,其在室外环境恶劣的条件下精度有待提高,这也将是未来继续研究的重点。