水下传感器网络时间同步和定位的联合实现方法

严长虹,马 静

(1.盐城工学院信息学院,江苏 盐城 224000;2.南京航天航空大学经济管理学院,南京 210016)



水下传感器网络时间同步和定位的联合实现方法

严长虹1,2*,马 静2

(1.盐城工学院信息学院,江苏 盐城 224000;2.南京航天航空大学经济管理学院,南京 210016)

水下传感器网络的信号传播速度受环境参数的影响而难以确定,增加了时间同步和定位的难度。当信号传播速度未知时,提出了一种水下传感器网络的时间同步和定位联合实现方案。通过建立该问题的优化函数和模型,设计了线性最小二乘(LLS)估计、最小二乘半定规划(LS-SDP)、平方最小二乘半定规划(SLS-SDP)及平方最小二乘二阶锥规划(SLS-SOCSDP)算法,分析了各算法的计算复杂度。仿真分析表明,线性代数LLS算法计算速度快,在低噪声条件下具有较高的估计精度。凸优化的LS-SDP、SLS-SDP及SLS-SOCSDP算法对未知参数估计的稳定性较好,但计算复杂度较高。

水下传感器网络;定位;时间同步;到达时间

水下传感器网络主要采用传感器节点监测水域内的各种环境参数,以实现资源监控、灾难预警与导航帮助等。水下传感器节点所采集的环境参数需要与地理位置坐标相捆绑才有意义,因此定位技术也是水下传感器网络的关键技术[1-3]。传统的GPS定位方法由于体积大、能耗高、需要固定的基础硬件设施并不适应于所有传感器节点定位。为此,传感器网络通常采用已知位置坐标的信标节点去推算未知节点的位置坐标,通过各种测距方法建立节点间距离约束优化方程以估算未知节点位置坐标。常用测距方法包括到达时间(TOA)[4]、到达时间差(TDOA)[5]及接收信号强度(RSS)及能量强度等。其中TOA测量方法实现原理简单,成本低,是一种较为常见的传感器网络定位实现方法。

建立于节点间距离约束优化方程基础上,已有各种算法估算位置坐标,常用的包括线性方程的代数估计[6-7]及凸优化的半正定(SDP)[8]和二阶锥规划(SOCP)[9]算法。线性代数估计法将未知结果直接表示为代数解,无须迭代计算过程,计算复杂度低,但在噪声较大时,估计结果不稳定。为此,也有算法将约束优化方程松弛为凸优化过程,SDP和SOCP也是当前传感器网络定位常采用的算法,但其计算复杂度较高。为减少凸优化变量及计算复杂度,凸优化模型的建立也是研究的重要内容,也有算法将模型松弛为混合的二阶锥规划(SOCSDP)过程。

时间测量以各节点的时钟为准,然而各节点的时钟存在漂移和偏离,导致直接的时间观测不准确,为此提出了时间同步和定位的联合实现方法[10-11]。文献[12]提出了采用多路信号来回传递推导了观测时间与实际时间的关系,从而实现时间同步和定位的联合。假设所有信标节点的时钟是同步的,而未知节点存在时钟漂移和偏离,文献[13]提出了非确定信标节点位置下多个未知节点的目标位置以及时间同步的联合代数计算方法。同样地,以节点时钟漂移和偏离模型为基础,文献[7]提出了一种时间同步和节点定位的多源目标联合线性估计方法,实现节点时钟漂移率、偏离量和位置坐标的同时估计。

节点间距离不但与时间有关,而且与信号传播速度相关,但水下信号传播速度与水深、盐度与温度等因素有关,因此水下传感器网络的时间同步和定位更加难以实现。文献[14]考虑信号传播速度的不确定性,提出了时间同步和定位的两步代数计算方法,即预先估计时间同步参数,再以估计出的时间同步参数确定节点位置坐标的两步估计方法。文献[15]将水下传播介质进行分层,采用对声波传播速度补偿的方法实现时间同步和定位的联合估计,并亦设计了代数计算方法,但代数计算方法在高噪声条件下估计误差较大。

当水下信号传播速度为未知参数时,本文提出了一种水下传感器网络的时间同步和定位联合实现方案,并设计了线性最小二乘(LLS)估计方法。为减少高噪声条件下的估计误差,本文又提出了凸优化的最小二乘半定规划(LS-SDP)、平方最小二乘半定规划(SLS-SDP)及平方最小二乘二阶锥规划(SLS-SOCSDP)算法。仿真实现了各算法,并验证了各算法的有效性,分析了各算法的计算复杂度和估计精度性能。本文第1部分首先介绍了问题描述;第2部分介绍了算法设计;第3部分详细推导了各算法的计算复杂度;第4部分为仿真与分析;最后部分为结论。

1 问题描述

考虑水下三维空间部署的传感器网络,存在着待确定位置坐标的未知节点,其位置坐标假设为x=[xyz]T。同时在该区域内分布着M个已知位置坐标的信标节点,假设信标节点位置坐标分别为xi=[xiyizi]T,i=1,2,…,M。为估计未知节点坐标,各信标节点与未知节点间进行到达时间(TOA)测量,如图1所示。信标节点i在Ti,1时刻(Ti,1为信标节点i上时钟的观测时间)向未知节点发送信号,未知节点在Ri,1时刻(Ri,1为未知节点上时钟的观测时间)收到信标节点i发出的信号。

图1 观测时间与实际真实时间关系

由于传感器节点所处环境参数、初始化及能量消耗等原因使得节点计时时钟失步,即引起节点上时钟的观测时间与实际真实时间不一致。由于Ti,1为信标节点i时钟的观测时间,根据文献[14-15]的节点计时时钟的漂移和偏离模型,有如下关系式

(1)

(2)

知节点上时钟的漂移率和偏移量。节点间收到信号的实际真实时间之差为节点间信号到达时间,记作ti,1,因此有关系式

(3)

(4)

当未知节点接收到信标节点i的信号后,未知节点又在Ti,2时刻(Ti,2为未知节点上时钟的观测时间)发送信号给信标节点i,信标节点i在Ri,2时刻(Ri,2为信标节点i上时钟的观测时间),同式(4)的类似推导过程,有方程式

(5)

当信号在水下区域进行传播时,信号传播速度随水下环境的压力、盐度和温度等参数变化而改变,为此在本模型中将信号传播速度假设为未知参数。式(4)及式(5)建立了节点的时钟同步参数ωx、ωi、θx、θi与节点间距离的约束关系,为节点时间同步和位置坐标的联合估计提供了可能。模型假设信标节点的时钟漂移率ωi、偏移量θi及位置坐标xi为已知参数,以估计未知节点的时钟漂移率ωx、偏移量θx、位置坐标x及水下信号的传播速度c。

2 算法设计

为估计时钟同步参数ωx、θx、位置坐标x及水下信号的传播速度c,下面分别介绍线性最小二乘(LLS)估计法及3种不同的凸优化实现方法。

2.1 线性最小二乘(LLS)估计法

对式(4)及式(5)相加,有关系式

(6)

(ai+bi)c+biδxc=di+0.5c(εi,1+εi,2)

(7)

式中:由于ai>0,ai+bi>bi,δx非常接近于零,故式(7)可以近似为

τic=di+εi

(8)

(9)

Aη=b+n

(10)

(11)

式中:权重矩阵Σn=E(nTn),其值表示为

(12)

式中:di为未知参数,可预先设置Σ为单位矩阵,以式(11)近似估计未知节点位置坐标。然后再以此近似估计值计算di,再以式(12)重新计算Σ及η,将此计算方法称之为线性最小二乘(LLS)估计法。根据向量η的定义,可从向量估计值η提取出未知节点位置坐标及信号传播速度平方值c2。

2.2 最小二乘半定规划(LS-SDP)算法

根据表示为式(8)的测量方程及极大似然估计法,联合估计问题可以表示为以下优化问题

(13)

式(13)所描述的优化问题为非线性非凸优化问题,为转化为凸优化问题,令d=[d1d2…dM]T,h=[dTc]T,可将式(13)中的目标优化函数重写为

(14)

(15)

(16)

所以将式(13)表示的优化函数可进一步表示为

(17)

为将式(17)表示的优化问题转化为凸优化问题,将H及Z作凸优化松弛,得到以下凸优化问题

(18)

式(18)表示的优化问题为最小二乘(LS)目标函数的半定规划(SDP)问题,故将上述算法称为LS-SDP算法。

2.3 平方最小二乘(SLS)凸优化方法

不同于式(13)表示的目标函数,亦可建立平方最小二乘的目标函数,以便于转化为凸优化问题。为此将式(8)两边平方,忽略高阶项,有关系式

(19)

对式(19)建立极大似然估计方程,表示为如下平方最小二乘(SLS)目标函数的优化问题

(20)

式中:μ=c2,μ为待确定的未知参数。对式(20)作进一步等效变换和凸优化松弛,可以转化为以下凸优化问题

(21)

式(21)表示的凸优化问题为目标函数为平方最小二乘(SLS)的半正定规划(SDP)问题,所以将此计算过程称之为SLS-SDP算法。SDP凸优化问题的变量较多,计算复杂度也较高,为此将式(21)进一步等效转化为如下形式

(22)

式中:u=[u1u2…uM]。式(22)表示的凸优化形式既包含了二次锥规划(SOCP),又包含了半定规划(SDP)优化,故将此计算过程称为SLS-SOCSDP算法。

2.4 时间同步参数的计算

考虑信号传播速度的变化量为Δc,未知节点坐标位置变化量为Δx=[ΔxΔyΔz]T,则式(7)可改写为

(23)

JΔθ=γ+ε

(24)

二乘法估计原理,未知向量Δθ的估计值为

(25)

(26)

并且将估计出的Δθ(1:3)及Δθ(4)作为Δx及Δc增加到LSS、LS-SDP、SLS-SDP及SLS-SOCSDP各算法的估计值中,对估计结果进行优化求精,将优化求精后的未知节点位置坐标及信号传播速度称为优化求精解。为估计时间偏移量θx。将式(5)减去式(4),有以下表达式

(27)

式中:i=1,2,…,M。考虑所有未知节点与信标节点的信号测量,有估计表达式

(28)

3 计算复杂度分析

凸优化算法的计算复杂度主要与凸优化方程中的变量和等式约束数量有关。为比较3种不同凸优化算法LS-SDP、SLS-SDP及SLS-SOCSDP算法的计算复杂度,将算法复杂度计算过程中的参数数量列出在表1中。表1中NSOCP表示了二次锥规划约束数量,NSDP表示了半定规划约束数量。LS-SDP算法包括了2个半定规划约束,其尺寸大小分别为M+1及4,故变量数量为(M+1)2+42,其等式约束数量为M+6。而SLS-SDP算法包括了M个尺寸大小为2及1个尺寸大小为4的半定规划约束,凸优化变量数量为4M+17,其等式约束数量为2M+6。SLS-SOCSDP算法包括了1个尺寸大小为M+1的二次锥规划约束及1个尺寸大小为4的半定规划约束,变量数量为M+18,其等式约束数量为M+6,故SLS-SOCSDP算法的变量与等式约束数量都比SLS-SDP算法有所减少。

[12]的凸优化算法的计算复杂度计算方法,考虑信标节点数量M≫4的情况下,3种凸优化算法的复杂度表示如下,

(29)

式中:log(1/ξ)表示了最小需要的迭代次数,ξ为凸优化算法的求解精度。由式(29)可知,3种算法中,LS-SDP算法的计算复杂度较高,而SLS-SOCSDP算法的计算复杂度较低。当然相比于3种凸优化算法,LLS算法不需要迭代计算,其计算过程较凸优化算法快了很多,具体复杂度计算在此不做介绍。

表1 凸优化算法复杂度计算中的参数数量

4 仿真分析

本文假设信号传播速度为未知参数,利用信标节点的时间同步参数和位置坐标,通过信标节点与未知节点间的TOA测量,实现了未知节点的时间同步参数和位置坐标的联合估计。在MATLAB软件上进行了LLS、LS-SDP、SLS-SDP及SLS-SOCSDP算法的仿真分析,3种凸优化算法采用CVX工具箱下的SeDuMi求解器计算。

4.1 算法的平均运行时间

在边长为100 m的三维区域平面上,预先将未知节点设置在(50,50,50)点,随机生成M个信标节点。分别假设信标节点数量M=6,7,8,9,10,表2列出了1 000次蒙特卡罗(MC)下LLS、LS-SDP、SLS-SDP和SLS-SOCSDP算法的单次平均运行时间。随着信标节点数量M的增加,未知节点与信标节点间的TOA测量连接数量增加,4种算法的平均运行时间都略有增加。比较3种凸优化LS-SDP、SLS-SDP和SLS-SOCSDP算法,SLS-SOCSDP的运行时间最短。如当M=6时,SLS-SOCSDP算法的平均运行时间为18.2 ms,而LS-SDP、SLS-SDP算法的平均运行时间为35.6 ms、27.7 ms。相比于3种凸优化算法,LLS算法的运行相当快,当M=6时,LLS算法的平均运行时间仅为0.22 ms。

表2 不同算法的单次平均运行时间比较 单位:ms

4.2 定位误差比较

所设计的算法在一定程度上进行了近似和松弛,所以定位结果非最优,仿真同时也验证了4种不同算法的估计误差精度。6个信标节点分别设置在(95,20,75),(16,95,5),(10,85,50),(70,75,90),(80,25,20),(65,30,60),并在该三维空间上随机产生20个未知节点。所有信标节点的时钟同步参数ωi=1,θi=0,且为已知值。假设未知节点与各信标节点间的传播时间噪声εi,1、εi,2以纳秒为单位,都服从均值为零,方差为δ2的高斯分布。仿真数据生成时,信号传播速度c预先设置为 3×108m/s。采用均方根误差(RMSE)评价4种不同算法的定位精度,取20个随机生成的未知节点位置的平均误差作为性能评价指标。选择RMSE定位误差的蒙特卡罗(MC)次数为1 000次,并采用1 000次平均值进行对比分析。

图2 误差随噪声大小变化关系

当传播时间噪声大小δ从0.5 ns增加到5 ns时,图2(a)绘出了4种算法的RMSE定位误差比较,该图中CRLB表示了该问题模型的克拉美罗下界值[14]。由图2(a)可见,4种算法的RMSE定位误差都随传播时间噪声的增加而增大。在低噪声条件δ<3.5 ns时,LLS算法的定位精度较高,但当δ>3.5 ns时,LLS算法的定位误差在4种算法中最大。3种凸优化的LS-SDP、SLS-SDP及SLS-SOCSDP算法的估计误差比较接近。相比较而言,LS-SDP算法的定位误差较小,但其复杂度较高。SLS-SOCSDP的RMSE定位误差较大,但SLS-SOCSDP算法的计算复杂度较低。

同样地,当传播时间噪声大小δ从0.5 ns增加到5 ns时,图2(b)绘出了4种算法的信号传播速度RMSE估计误差比较。有同样的结果发现,在噪声较小(δ<3.5 ns)时,LLS算法的估计误差更加接近于CRLB下界值,但当传播时间噪声δ>3.5 ns,LLS算法的信号传播速度估计误差较其他3种凸优化算法大。3种凸优化算法LS-SDP、SLS-SDP及SLS-SOCSDP的估计误差比较接近,相比于代数LLS方法,3种凸优化算法随噪声的变化关系更加平稳。

图3 时间同步参数的估计误差

4.3 时间同步参数估计误差

当所设计的4种算法估计出未知节点位置坐标及信号传播速度后,根据2.4所述的方法计算未知节点的时间同步参数,仿真同时也分析了时间同步参数的估计误差。未知节点及信标节点参数设置同4.2,当传播时间噪声大小δ从0.5 ns增加到5 ns时,图3绘出了4种算法的时间同步参数包括时钟漂移率和偏移量的RMSE估计误差比较。图3(a)所反映的时钟漂移率随噪声δ的变化曲线与图3(b)的时钟偏离量随噪声δ的变化曲线,有非常相似的变化关系。当δ<3.5 ns时,代数LLS算法的时钟漂移率及偏移量估计误差RMSE都较其他3种凸优化算法小;而当噪声δ>3.5 ns时,LLS算法的估计误差较大。相比于代数LLS方法,3种凸优化算法随信号传播噪声的变化较为平缓。如当噪声δ为0.5 ns时,LS-SDP算法的时钟漂移率RMSE为0.065,而代数LLS算法的时钟漂移率RMSE仅为0.03,代数LLS算法比LS-SDP算法的估计误差小;而当噪声δ等于5 ns时,LS-SDP算法的时钟漂移率RMSE增加到了0.12,而LLS算法的时钟漂移率RMSE增加到了0.175,代数LLS算法比LS-SDP算法的估计误差更大了。

4.4 优化求精估计误差比较

本文内容2.4所介绍的计算过程同时也对未知节点位置坐标进行了优化求精,仿真同时也对求精前的初始解与优化求精解进行了对比。同样地,未知节点及信标节点参数设置同4.2,当传播时间噪声大小δ从0.5 ns增加到5 ns时,图4对比了优化求精前后定位误差与信号传播速度的大小关系。由图4(a)可见,SLS-SOCSDP算法经过优化求精后,未知节点定位误差有较大的改善,更加接近于估计结果的CRLB下界值。如当δ=5 ns时,SLS-SOCSDP算法的初始解定位误差RMSE为4.7 m,而经过优化求精后,其定位误差RMSE减少到了3.9 m。从图4(b)可以发现,优化求精后的信号传播速度估计误差也有较好的改善。如当δ=5 ns时,LLS算法的信号传播速度初始解估计误差RMSE为1.22×107m/s,而经过优化求精后,其估计误差RMSE减少到了0.95×107m/s,估计误差较初始解有较大的改进。

图4 优化求精前后估计误差比较

5 结论

当无线信号在水下传播时,信号传播速度难以测量。本文针对水下传感器网络的时间同步和定位联合实现问题,提出了通过信标节点与未知节点间的双路来回时间测量方法。假设水下信号传播速度为未知参数,设计了时间同步和定位联合实现问题模型的LLS、LS-SDP、SLS-SDP及SLS-SOCSDP算法,验证了算法的有效性。与所设计的3种凸优化算法比较,代数LLS算法运算速度快,但在强噪声时估计误差较大。相比与LLS算法,LS-SDP、SLS-SDP及SLS-SOCSDP的凸优化算法随噪声的变化更为平缓。当然本文所提出了模型算法也有一定的局限性,只适用于单源节点的时间同步和定位联合实现问题,未将模型扩展到多源节点合作实现,有待于进一步探索与研究。

参考文献:

[1] Amin Y Teymorian,Wei Cheng,Liran Ma,et al. 3D Underwater Sensor Network Localization[J]. IEEE Transactions on Mobile Computing.2009,8(12):1610-1621.

[2] Xing Tan,Jian Li. Cooperative Positioning in Underwater Sensor Networks[J]. IEEE Transactions on Signal Processing,2010,58(11):5860-5891.

[3] 蔡绍滨,高振国,潘海为,等. 带有罚函数的无线传感器网络粒子群定位算法[J]. 计算机研究与发展,2012,49(6):1228-1234.

[4] Hong Shen,Zhi Ding,Soura Dasgupta,et al. Multiple Source Localization in Wireless Sensor Networks Based on Time of Arrival Measurement[J]. IEEE Transactions on Signal Processing,2014,62(8):1938-1949.

[5] Le Yang,C Ho. An Approximately Efficient TDOA Localization Algorithm in Closed-Form for Locating Multiple Disjoint Sources with Erroneous Sensor Positions[J]. IEEE Transactions on Signal Processing,2009,57(12):4598-4615.

[6] Huajie Shao,Xiaoping Zhang,Zhi Wang. Efficient Closed-Form Algorithms for AOA Based Self-Localization of Sensor Nodes Using Auxiliary Variables[J]. IEEE Transactions on Signal Processing,2014,62,(10):2580-2594.

[7] 顾治华,朱雪芬,吴晓平,等. 一种传感网时间同步和定位的联合线性估计方法[J]. 传感技术学报,2016,29(3):397-402.

[8] Pratik Biswas,Tzu-Chen Liang,Kim-Chuan Toh,et al. Semidefinite Programming Approaches for Sensor Network Localization with Noisy Distance Measurements[J]. IEEE Transactions on Automation Science and Engineering,2006,3(4):1-11.

[9] Ghasem Naddafzadeh-Shirazi,Michael Botros Shenouda,Lutz Lampe. Second Order Cone Programming for Sensor Network Localization with Anchor Position Uncertainty[J]. IEEE Transactions on Wireless Communication,2014,13(2):949-963.

[10] Aitzaz Ahmad,Erchin Serpedin,Hazem Nounou,et al. Joint Node Localization and Time-Varying Clock Synchronization in Wireless Sensor Networks[J]. IEEE Transactions on Wireless Communication,2013,12(10):5322-5333.

[11] Weijie Yuan,Nan Wu,Bernhard Etzlinger,et al. Cooperative Joint Localization and Clock Synchronization Based on Gaussian Message Passing in Asynchronous Wireless Networks[J]. IEEE Transactions on Vehicular Technology,2016,65(9):7257-7273.

[12] Reza Monir Vaghefi,R Michael Buehrer. Cooperative Joint Synchronization and Localization in Wireless Sensor Networks[J]. IEEE Transactions on Signal Processing,2015,63(14):4035-4040.

[13] Liyang Rui,K C Ho. Algebraic Solution for Joint Localization and Synchronization of Multiple Sensor Nodes in the Presence of Beacon Uncertainties[J]. IEEE Transactions on Wireless Communications,2014,13(9):5196-5210.

[14] Roee Diamant,Lutz Lampe. Underwater Localization with Time-Synchronization and Propagation Speed Uncertainties[J]. IEEE Transactions on Mobile Computing,2013,12(7):1257-1269.

[15] Jun Liu,Zhaohui Wang,Jun-Hong Cui,et al. A Joint Time Synchronization and Localization Design for Mobile Underwater Sensor Networks[J]. IEEE Transactions on Mobile Computing.2016,15(3):530-543.

Joint Implement Approach for Time Synchronization and Localization in Underwater Sensor Networks

YAN Changhong1,2*,MA Jing2

(1.School of Information Engineering,Yancheng Institute of Technology,Yancheng Jiangsu 224000,China; 2.College of Economics and Management,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

In underwater sensor networks,signal propagation speed is difficult to be determined due to the influence of environmental parameters,which increases the difficulty of time synchronization and localization. When the signal propagation speed is unknown,a joint implementation scheme for time synchronization and localization is put forward in underwater sensor networks. By building the optimization function and model of the problem,the linear least squares(LLS)estimation,least squares semidefinite programming(LS-SDP),squared least square semidefinite programming(SLS-SDP)and squared least square second order cone and semidefinite programming(SLS-SOCSDP)algorithms are designed,then the computational complexity of the proposed algorithms is analyzed. The simulation analysis shows that the linear algebra LLS algorithm runs fast and obtains high positioning accuracy in low noise conditions. The stability of LS-SDP,SLS-SDP and SLS-SOCSDP algorithm with convex optimization is better,but the computation complexity is higher.

underwater sensor networks;localization;time synchronization;time of arrival

严长虹(1980-),女,讲师,在读博士,主要研究方向为无线传感器网络、信号分析与处理、网络安全等。在国内外重要会议及期刊上发表论文十多篇;

马 静(1966-),女,教授,博士生导师,主要研究领域包括信息企业化、知识管理与知识管理系统、电子商务、国防科技情报、复杂网络与网络舆情、大数据分析等。

项目来源:国家自然科学基金项目(71373123);江苏高校哲学社会科学研究重点项目(2015ZDIXM007);南京航空航天大学基本科研业务费重大项目(NP201630X)

2016-11-02 修改日期:2017-02-12

TP393.0

A

1004-1699(2017)06-0922-07

C:6150;7110;5210

10.3969/j.issn.1004-1699.2017.06.020