时钟非同步网络的高精度网络拓扑定位算法

摘要

本发明属于网络的拓扑定位技术领域，具体为一种时钟非同步网络的高精度网络拓扑定位算法。本发明分为两大部分：一是基于一种时分多址(TDMA)的协议，各节点收集、发送信息，并将其扩散到整个网络；二是基于这些信息，得出不需要时钟同步的高精度网络拓扑定位。对于一个单跳网络，本发明提供一种中心化算法，对于一个大规模多跳网络，本发明提供一种分布式定位算法。进一步，还可得出网络中各离散节点本地时钟的时延估计。本发明考虑到了锚点信息的不正确性，使得该算法更贴近实际，定位更加精确，且能够达到克拉美劳限。

说明书

技术领域

本发明属于网络的拓扑定位技术领域，具体涉及一种时钟非同步网络的高精度网络拓扑定位算法。

背景技术

网络的拓扑定位是无线传感网络、无人机网络、无线自组织网络中的关键技术。特别是对于无人机网络，要避免机群节点的碰撞和高精度定位控制，对网络的各个节点实现分米级的高精度的定位。因此，我们不能仅依赖于GPS/北斗的定位信息。而是要不但基于锚点的定位信息(GPS/北斗定位或其他定位信息)，而且通过节点间的自聚集与信息交换，协同获得精度高于米级的网络拓扑信息。

针对上述问题，已经有大量的研究工作发表。

传统的高精度网络拓扑定位假设各分布式节点的时钟同步，而实际中网络节点的时钟由于晶振频偏，很难做到时钟同步。同时，如何将各离散节点关于节点间的距离测量的信息高效汇聚，并实现最优的拓扑定位，也是一个难题。

发明内容

本发明的目的在于提供一种对时钟非同步网络实现高精度定位的网络拓扑定位算法。

本发明提供的网络拓扑定位算法，分为两大部分，一是基于一种时分多址(TDMA)的协议，各节点收集、发送信息，并将其扩散到整个网络；二是基于这些信息，得出不需要时钟同步的高精度网络拓扑定位。而且作为本定位算法的副产品，能够得出网络中各离散节点本地时钟的时延估计。

本发明提供的网络拓扑定位算法(也称中心化算法)，具体步骤如下：

第一步，对于一个N个节点的单跳网络。该网络采用一种基于时分多址(TDMA)的信息交换协议，如图1所示。

网络中每个节点轮替广播导引信号(beacon)；假设此时第n个节点在广播导引信号，该导引信号包含下列内容：

(1)1个同步序列，它用于精确估计导引信号到达时接收节点的本地时间；

(2)1个时间戳T_n，即第n个节点发送该导引信号时的本地时间；

(3)N-1个时间戳{R_nm,m＝1,…,n-1,n+1,…,N}，即第n个节点收到其他N-1个节点导引信号时的本地时间。

从节点1到节点N轮流发送上述信息。经过N个回合，所有这些单跳区域内的节点都将收集到{T_n,n＝1,2,…,N}(即网络中N个节点各自发送导引信号时的本地时间)和{R_nm,n,m＝1,2,…,N}(即网络中N个节点收到其他N-1个节点发送的导引信号时的本地时间)。

基于这些信息，可以获得如下关系：

其中，Δ_n是节点n相对于节点1的时钟漂移，显然Δ₁＝0，d_mn是节点m,n之间的距离。C是信号传播的速度，∈_mn是由于测量R_mn和T_n带来的误差，∈_mn·C即为节点间距的测量误差，假设其服从高斯分布C·∈_mn～N(0,σ²)，其中，σ为标准差；

第二步，假定在N个节点中，有K≤N个节点装备了GPS/北斗定位，这些节点首先开始自定位，并将定位信息广播给其他节点。至此，网络中所有节点获得了这K个锚点的GPS/北斗定位信息，但有误差。也就是：

其中，p_k是第k个节点的真实位置坐标矢量，是节点k的GPS/北斗定位，Q_k是第k个节点GPS/北斗测量误差的3x3协方差矩阵(这里我们考虑三维定位，如果是二维定位，则Q_k是个2x2的矩阵)，是所有带GPS/北斗的节点的集合；

第三步，至此，网络中的所有节点都已经获得了如下信息：{T_n,n＝1,2,…,N}，{R_nm,n,m＝1,2,…,N}，根据这些信息，网络中的各节点再运行本发明提供的定位算法，可以得出网络中的各个节点的定位(也可以只让网络中某个电池剩余电量较高的节点运行该算法，再把定位结果广播出去)。

第三步中，所使用的定位算法为高性能定位算法，具体如下：

根据表达式(14)，定义：

据此计算最优定位：

其中，是所有彼此直接互联的节点对的集合，σ如前文定义，p_m,p_n表示第m,n个节点的位置坐标矢量，p是N个节点的位置矢量横向拼接形成的3×N矩阵(这里我们考虑三维定位，如果是二维定位则N个节点的位置矢量横向拼接形成的2×N的矩阵)，代表运用本算法产生的对p的估计。

首先，以K个有GPS/北斗的节点的定位为锚点，采用传统的三角定位法获得所有N个节点的定位。如果网络是多跳的，也就是有些节点可能不能和有GPS/北斗的节点直接相连。为解决这一问题，将已被三角定位的节点加入扩大的锚点集。由此确保所有N个节点都能被定位。

为方便我们讨论，定义：

其中，

基于上述方法获得的对各节点位置的初步估计，我们用如下算法贯序凸规划法(SCP)求解式(17)：

(1)计算函数f(p)的一阶导和二阶导

(2)计算的特征值分解其中Λ是以特征值为对角线元素的对角矩阵，U是的特征向量组成的矩阵，U^H是U的共轭转置矩阵。

(3)如果Λ的对角线元素全为正数，进入第(4)步，否则跳转第(5)步。

(4)计算跳转第(6)步。

(5)计算其中Λ^-是将Λ^-1中非正的对角线元素替换为0得到的新的对角矩阵。

(6)用回溯直线搜索法或者任何其他的线性搜索法，计算能最小化f(p+su_nt)的那个s，其中，s是步长，f(p+su_nt)是将网络中所有节点的位置坐标p更新为p+su_nt后，式(5)代价函数值。

(7)判断是否满足停止准则(如：|f(p+su_nt)-f(p)|≤η，其中η是一个自行设置的小正数)，将p更新为p+su_nt，p←p+su_nt。如果满足停止准则，则算法结束，得到网内节点的位置坐标估计p；否则回到第(1)步。

上述算法过程中，一阶导为：

其中，是节点n的一跳邻居节点的集合，而是所有带GPS/北斗的节点的集合。

二阶导为

其中：

进一步，本发明还推导出定位算法的理论最优性能限--克拉美劳限(CRB)为：

其中，Q＝diag{Q₁,Q₂,…,Q_K}是一个3K×3K的块对角矩阵，而T的对角子块是：

其中，是节点n的邻居节点集。而T的非对角子块为

本发明还提供一种分布式定位算法，是从中心化算法演化而来，基本上是把一个大网络分割为若干小的子网，在每一个子网内执行第三步；但相邻子网之间需要一些信息交换。具体介绍如下：

上述网络拓扑定位算法中，假定网络是一个单跳网络，网络规模较小，对网络中所有节点收集到的全部信息采用的是一种中心化处理方式，即将整个网络的所有节点收集到的信息一次性全部集中到一起处理(即中心化算法)。如果是多跳网络，网络规模较大，可以采用由中心化的定位算法演变而来的分布式定位算法，具体是在网络的各个局部，先利用局部信息分别进行定位，然后各个局部相互反馈定位结果，相互校准。以此避免了一次性对整个网络的全部信息进行处理，从而避免了超高的计算复杂度，并且还能保持中心化定位算法的定位精度。

分布式定位算法的基本思想如图3所示。假定一个大规模多跳网络通过某种自聚集方法(self-clustering)分簇为若干个个子网，其中任意相邻的两个子网，簇A和簇B中含有若干个公共节点，称为网桥节点。分布式定位算法具体步骤如下：

(1)在簇A和簇B中分别进行前述的中心化定位算法过程中的第一步和第二步，收集到簇内信息：这些符号含义与上文相同，A、B分别标识从属于簇A和簇B中的簇内信息。

(2)在簇A中，使用前文描述的定位算法处理簇A中收集到的信息进行簇内节点定位。取出其中的网桥节点的定位结果(网桥节点定位的位置矢量首尾拼接形成的列向量)。计算簇内节点定位CRB矩阵，取出网桥节点对应的CRB矩阵子块C_A。将C_A传递给簇B。

(3)在簇B中，将网桥节点当作锚点(如同装备了GPS/北斗的节点)，并将当作他们的锚点定位(如同GPS/北斗定位结果)，其中是网桥节点的真实位置矢量首尾拼接形成的列向量。使用前文描述的定位算法处理簇B中收集到的信息进行簇内节点定位。取出其中的网桥节点的定位结果计算簇内节点定位CRB矩阵，取出网桥节点对应的CRB矩阵子块C_B。将C_B传递给簇A。

(4)在簇A中，同样，将网桥节点当作锚点，并将当作他们的锚点定位。使用前文描述的定位算法处理簇A中收集到的信息进行簇内节点定位。如果簇A中的定位结果与上一轮结果比较没有重要变化，即更新的定位估计和原估计相比较，其变化小于某个自选门限，通常设为0.05米，则进入(5)步。进入第(5)步；否则，取出其中的网桥节点的定位结果并计算簇内节点定位CRB矩阵，取出网桥节点对应的子块C_A，将C_A传递给簇B。回到第(3)步。

(5)将簇A和簇B的定位结果合并得出整个网络的节点定位：p←p_A,p_B。其中p_A,p_B分别是簇A和簇B中的最终定位结果。

在子网个数大于等于3的情况下，在任意一对相邻簇之间执行上述步骤，如三个子网的情况，在AB,AC，BC之间；或者四个子网的情况在AB,AC,AD,BC,BD,CD之间，等等。执行上述分布协同算法，最终获得整个大网络的最优定位。

进一步，本发明可以获得各节点的时钟相对于第一个节点(参考节点)时钟漂移的最优估计：

其中，y是将y_mn(见式(16)摞起来的一个的矢量:

y＝(y₂₁,y₃₁，…,y_N1,y₁₂,y₃₂，…,y_N2,……,y_1N,y_2N,…,y_(N-1)N)^T

是A去掉第一列得到的矩阵；

其中，A₁,A₂,A₃,…,A_N都是(N-1)×N维矩阵：

以此类推，

由此，也推导了理论最优性能限--克拉美劳限(CRB)为：

此算法得出的估计亦可达到克拉美劳限。

本发明方法的优点

(1)考虑到了锚点信息的不正确性，使得该算法更贴近实际，定位更加精确，且能够达到克拉美劳限。

(2)易于演化成为分布式定位算法，并且保持它的定位精度，可适应大规模网络中的定位。

(3)可以进一步得出网络中各个节点本地时钟的时延估计，该估计亦可达到克拉美劳限。

附图说明

图1为节点轮替广播图示。

图2为中心化定位算法的性能。本算法性能达到最优限-克拉美劳限(CRB)

图3为在两个子网内分别进行中心化的定位算法，然后通过网桥节点往复迭代的图示。

图4为分布式和中心化处理式的性能比较。

图5为时延估计的性能。

具体实施方式

下面进一步通过具体实施例，进一步介绍本发明。

作为实施例，本发明用计算机仿真了一个20节点的单跳网络。各节点随机分布在一个200m*200m*200m的区域，其中，5个节点是有GPS/北斗的，其三维测量误差为高斯分布单位是米。节点间距的测量误差为N(0,σ²)。以三角定位法为初始点，利用本发明提出的SCP算法迭代，进行了200次蒙特卡洛实验。最终定位误差的性能如图2所示。其中x-轴是测量节点间距离误差的方差σ²；y-轴是节点定位的平均误差。平均误差计算如下：在每一次蒙特卡洛实验中，先计算所有节点定位平方误差的平均值其中(x_i,y_i,z_i)代表第i个节点的真实位置矢量，是对其的估计；然后将200次蒙特卡洛实验中计算结果取平均后开根号，得到y-轴表示的节点定位的平均误差。对于图中克拉美劳限曲线上的数值计算：先计算式(9)的CRB矩阵，取其对角线元素计算均值并乘以可以看出，本发明提出的算法性能远超三角定位法，也显著优于经典的MDS算法[1]，可以达到理论最优性能限--克拉美劳限(CRB)。

本发明对采用分布式算法也进行仿真，考虑一个35-节点的网络。该网络被分成两个20-节点的子网，其中有5个节点是网桥，被两子网共有。采用上述分布式定位算法，进行了200次蒙特卡洛实验，节点的定位误差如图4所示，其中x-轴是测量节点间距离误差的标准差σ，y-轴是节点定位的平均误差，计算方式与上一个仿真中的相同。可以看到，分布式算法的性能(上侧带小圆点的线)非常接近于中心化算法(中间带方点的线)，两者都接近克拉美劳限(CRB，下侧带大圆点的线)。

对于时延估计，本发明用计算机仿真了一个单跳网络。各节点随机分布在一个200m*200m*200m的区域。节点间距的测量误差为N(0,σ²)。对于网络中分别含有5,10,20个节点的情况，分别进行了200次蒙特卡洛实验，最终时延估计结果如图5所示，其中x-轴是测量节点间距离误差的方差σ²，y-轴是节点时延估计的均方误差(已将时延误估计误差乘以信号传播速度C从而转换成距离误差)。节点时延估计的均方误差计算如下：在每一次蒙特卡洛实验中，先计算除节点1以外的所有节点时延估计平方误差的平均值其中δ_i代表第i个节点真实时延乘以C，是对其的估计；然后对200次蒙特卡洛实验中计算结果取平均，得到y-轴表示的节点时延估计的均方误差。对于图中克拉美劳限曲线上的数值计算：先计算式(13)的CRB矩阵，然后取其对角线元素计算均值。可以看出，本发明提供的时延估计亦能够达到理论最优性能限--克拉美劳限(CRB)，并且随着网络中节点的数目增加，估计效果越好，反映了其中的网络协作效应。

参考文献

[1]I.Dokmanic,R.Parhizkar,J.Ranieri and M.Vetterli,"Euclidean Distance Matrices:Essential theory,algorithms,and applications,"in IEEE Signal Processing Magazine,vol.32,no.6,pp.12-30,Nov.2015。