基于半定规划的移动辅助定位算法*

陈德全

(1.重庆大学计算机学院,重庆 400044;2.重庆幼儿师范高等专科学校通识教育部,重庆 404047)

尽管全球定位系统(Global Positioning System,GPS)能够为无线设备提供位置信息,但GPS增加了额外成本[1-2],也提高了设备的功耗。因此,多数物联网应用中并不适合安装GPS模块。

为此,研究人员采用基于射频RF定位算法估计设备位置[3]。这些算法先测量信息,如到达角度(Angle of Arrival,AoA)[4],到达时间(Time of Arrival,ToA)[5]、到达时间差(Time Difference of Arrival,TDoA)[6]以及接收信号强度(Received Signal Strength Indicator,RSSI)[7-8],再利用这些测量信息估计未知节点位置。相比于AoA、ToA,RSSI测量无需额外硬件设备,几乎所有无线设备均能够测量RSSI值。因此,基于RSSI的定位算法得到广泛应用。

依据网络模式,基于RF定位算法可粗略地划分为两类:基于节点间通信定位和移动辅助定位。前者也称为静态定位算法。在基于节点间通信定位算法中,先依据节点间RF测量估计通信节点间的欧式距离,再利用多边定位[9]或者协作定位算法[10]估计节点位置。而移动辅助定位是通过无线移动单元估计节点位置,这些移动单元能够感知自己位置。

为了区分,本文将位置固定的节点称为传感节点。而能够移动、且能感知位置的节点称为移动单元,如无人车(Unmanned Aerial Vehicle,UAV)。与传感节点不同,移动单元一般不受能量限制。相比于静态定位,移动辅助定位算法具有一定的优势。静态定位常因障碍物遭受非视距问题,而移动辅助定位由于移动单元可以移动,能缓解或避免非视距问题。此外,在稀疏环境,节点间无法构成通信链路,这就无法实现静态定位。而移动辅助定位就不存在此问题。随着基于UAV辅助的无线传感网络的快速发展[11],移动辅助定位得到广泛关注[12]。

文献[12]对移动辅助定位算法进行综述。但是传统的移动辅助定位算法是假定环境参数是已知的。文献[13]将UAV与GPS系统相结合,实现对机器人的定位。目前,基于RSSI测距的移动辅助定位仍存在一些问题:1)路径损耗指数的估计不准。而路径损耗指数对测距精度有重要影响。估计不准的路径损耗指数导致测距误差;2)移动单元位置的不确定性。特定应用的部署区域或者环境条件对准确估计移动单元位置设置了阻力[13]。

为了解决上述问题,提出半定规划的移动辅助定位(Semi-Definite Programming based Mobility-Assisted Localization,SMAL)算法。SMAL算法引用移动单元,并周期地向传感节点广播beacon包。与传统的移动辅助定位算法不同,SMAL算法将传播模型的路径损耗参数看作未知参数,并不再将移动单元的位置作为已知条件。

先部署一些锚节点,再通过锚节点获取环境参数,并建立简易的传播模型进行测距,最终,通过半定规划(Semi-Definite Programming,SDP)算法估计节点位置。仿真结果表明,提出的SMAL算法有效地估计节点位置。

1 系统模型

在区域Π内部署N个传感节点和一个移动单元。N个传感节点分别标识为s1,s2,…,sN。移动单元在区域Θ内沿着任意轨迹移动,并周期向所有传感节点广播beacon包,且每个beacon包具有唯一序列号。例如,第k个beacon的序列号为k,且k∈{1,2,3,…,K},其中K为beacon包数。

假定移动单元发射的功率足够大,能够传输至所有传感节点。传感节点si接收到beacon包,就估计它的RSSI值,进而构建矢量ri∈RK:

ri=(ri,1,ri,2,…,ri,k,…,ri,K)

(1)

式中:ri,k表示传感节点si从接收的第k个beacon中所提取的RSSI值。

RSSI值ri,k与距离di,k相关。依据对数-距离传播模型[14],可建立ri,k与di,k间函数关系。该模型也称高斯模型。

ri,k=Pi-10αlgdi,k+Xi,k[dBm]

(2)

式中:di,k表示传感节点si离第k个beacon的距离。α为路径损耗。若是自由空间,α一般取值为2;若是都市环境,α一般取值3～5。由于传感节点可以部署任何环境,将α看作未知数。

因此,定位问题可表述如下:网络已部署已知位置的m个节点(锚节点),且m

2 SMAL算法

2.1 测距

为此,先建立si,j与距离di,j的单调函数,如式(3)所示:

si,j=α+βdi,j+Y

(3)

式中:α、β为常数。Y表示用于线性误差,即α+βdi,j与si,j间误差变量。噪声是产生误差的重要原因。因此,Y是噪声函数。

2.2 基于SDP的定位

2.2.1 定位形式化表述

(4)

(5)

(6)

2.2.2 基于SDP求解

令矩阵X=[x1,x2,…,xN]。用矩阵形式表述定位问题:

(7)

式中:I表示单位矩阵。而ei为一个向量,除了第i个元素不为零[16],其他元素均为零。

再将式(7)转化为半定规划:将Y=XTX转化为Y>XTX。并定义不等式矩阵Z:

(8)

因此,定位问题可表示为标准SDP形式:

(9)

式中:0表示零矩阵。最后,通过求解式(9)求解,进而估计传感节点位置。表1显示了SMAL算法的整个过程。

表1 SMAL算法流程

3 性能仿真

3.1 仿真场景

利用Python建立仿真平台。将N个传感节点和m个锚节点随机分布于Π区域。移动单元周期地发送beacon包。同时,考虑两个传播模型:高斯模型(Gaussian)和瑞利模型(Rayleigh)。

同时,选择基于RSSI的静态协作定位(Static)作为参照。为了考虑各种参数对SMAL算法的性能,考虑三个场景,场景参数如表2所示。

3.2 场景一

场景一的仿真参数如表2所示。场景一反映了室外场景环境。本次实验分析定位误差随K变化情况,如图1所示。表3给出各点的定位误差。

图1显示了Gaussian和Rayleigh两个传播模型下的定位算法误差。从图1可知,定位误差随K变化有一定波动。当K从100升至400时,定位误差随之下降。但当K从400升至1 000时,定位误差不再随之变化。相比于Static算法,提出的SMAL算法的定位误差得到有效控制。不论是Gaussian还是Rayleigh,SMAL算法的性能优于Static算法。

3.3 场景二

设置场景二的目的在于分析噪声σX对定位误差的影响,如图2所示。表4给出各点的定位误差。

图2分析了K=200、K=800两个环境对定位误差的影响。从图2可知,σX的增加,提高了定位误差,原因在于:σX越大,测距误差越大。大的测距误差必然降低定位精度。此外,相比于Static算法,SMAL算法有效地控制了定位误差。这主要是因为:Static算法直接利用RSSI值测距。此外,K=200时的SMAL算法的定位误差大于K=800时定位误差。原因在于:K=800时,移动单元发送的beacon更多,传感节点获取的RSSI值越多,越有利于测距精度的提高。

3.4 场景三

最后,通过场景三分析传感节点数N对定位误差的影响,如图3所示。表5给出各点的定位误差。

从图3可知,传感节点数N对定位误差的影响并不大。而锚节点数的增加,可以微略地增加定位精度。

此外,相比于Static算法,当锚节点数较小(例如A=5),SMAL算法的定位精度得到有效提升。这也说明,SMAL算法能在少数锚节点环境时,获取较高的定位精度,在室内定位环境中,定位误差约1.5 m。

表2 三个场景的仿真参数

表3 beacon数对定位误差的影响 单位:m

表4 σX对定位误差的影响 单位:m

表5 节点数N的定位误差的影响 单位:m

图1 定位误差(场景一)

图2 定位误差(场景二)

图3 定位误差(场景三)

4 总结

针对无线网络的定位问题,提出基于半定规划的移动辅助定位SMAL算法。SMAL算法利用未知位置的移动单元辅助估计节点位置。相比于传统的定位算法,SMAL算法具有以下几点优势。首先,由于无需移动单元位置,SMAL算法既能适用于室内也能适用于室外环境。其次,SMAL算法不依赖于硬件,无需复杂硬件设备,能在广泛的物联网场景中使用。第三,SMAL算法能便捷地估计无线环境参数。