CN103648164A - 一种基于到达时间差和Gossip算法的无线传感器网络分布式定位方法 - Google Patents

Abstract

一种基于到达时间差和Gossip算法的无线传感器网络分布式定位方法，本发明涉及无线传感器网络分布式定位方法。本发明是要解决无线传感器网络中单纯到达时间差定位方法定位精度低问题。一、锚节点获取自身位置坐标；二、实现分布式时间同步；三、锚节点随机唤醒监测未知节点；四、唤醒锚节点保存接收信号时刻和本地坐标；五、所有锚节点是否全部完成信号监测和数据保存；六、锚节点j收到其所有M个相邻锚节点的数据；七、获取锚节点j对于未知节点位置的初始估计值；八、所有锚节点获取未知节点位置初始估计值；九、运行Gossip算法随机选择相邻锚节点交换定位数据；十、算法终止。本发明应用于无线传感器网络典型工作领域。

Description

一种基于到达时间差和Gossip算法的无线传感器网络分布式定位方法

技术领域

本发明涉及无线传感器网络分布式定位方法。

背景技术

无线传感器网络，作为物联网的核心技术之一，被赞誉为未来改变人类生活的十大支撑技术之一。自从无线传感器网络被广泛关注开始，其定位技术一直是理论研究的焦点问题。近年来，国内外学者提出多种无线传感器网络中心式或分布式定位算法，但其基本上是针对未知节点（网络中待测其位置的节点）主动定位的情况设计的。

无线传感器网络是由大量具有数据采集、数据处理和无线数据收发等功能的节点所组成的通信网络。典型的无线传感器网络工作方式是将大量的无线传感器节点布置或抛洒在感兴趣的区域，无线传感器节点通过自组织的方式快速形成一个无线网络。每个传感器节点都有自己通信区域并且通过感知设备来检测周围环境的温度、湿度抑或频谱等信息，同时也可以配备通信设备与相邻节点进行短距离通信。

基于上述无线传感器网络的自身特点，传感器节点的工作区域通常为诸如军事侦察、路况检测等人类不易进入的区域，而且对于像灾后重建、气候监测等传感器网络的典型应用环境，传感器节点通常通过飞机抛洒等手段被置于工作区域，因而它们的位置都是随机而未知的。然而在许多应用中，节点所采集的数据必须结合它所处的坐标位置才有意义，因而对于无线传感器网络未知节点的定位技术的研究具有重要的意义。

通过基于两个信号到达节点的时间差而完成测量从而进行定位的方法叫做到达时间差定位(Time Difference of Arrival,TDOA)。TDOA是一种被广泛采用的定位方法，目前被多种定位硬件平台确定为首选定位方法。TDOA定位技术在蜂窝定位系统、WCDMA技术、无线测距雷达、路基多点定位等无线定位系统中有着非常广泛的应用，并且已有研究人员开始尝试将其扩展到无线传感器网络的定位应用中。但是目前在无线传感器网络定位应用之中，TDOA算法存在着定位精度较低，定位性能较差的问题。而且，目前TDOA算法一般都被用来实现未知节点的自身主动定位，尚未将其扩展应用于类似军事精确打击或非法接入频谱电台监测等无线传感器网络典型工作环境所需的分布式被动定位领域。

由于无线传感器节点有限的通信能力、数据处理能力和设备可靠性，无线传感器网络中的节点通常都采用密集放置的方式。由于节点密度较高，因此地理位置上临近的节点所采集的数据通常具有较大的冗余。如果能在数据传输过程中将这些数据进行融合、压缩，就可以显著减小后续传输过程中的分组数量和分组尺寸，从而提高网络容量并降低节点的能量消耗。因此关于无线传感器网络中的数据压缩和有效传输手段的研究就成为了一个研究热点。在这种背景下，诞生了可应用于无线传感器网络分布式共识的Gossip算法。该算法中的每个节点随机地和它选定的某个（或某组）相邻节点交换数据，然后这两个（或该组）节点分别利用凸合并算法合并这些数据，并用新的数据替换掉自己原有的数据。

Gossip算法最早在1984年由Tsitsiklis等人首次提出，该算法仅利用网络节点的本地信息与它的邻居节点的信息进行数据交换，解决了分布条件下的平均共识问题。在无线传感器网络中研究最早、研究成果最成熟并且应用最普遍的是成对Gossip算法。目前，基于Gossip算法的平均共识问题在无线传感器网络中的应用更是研究的热点。与传统的路由算法不同，Gossip路由算法强调通过节点的本地信息与邻居节点进行数据交换的方式来进行数据更新，我们把一次数据更新过程称为一次迭代过程。由于在迭代过程中，只涉及到一跳邻居节点信息和本地信息的交换，所以基于Gossip的网络并不需要传统路由算法的路由建立过程和维护过程，也没有数据的转发过程，这就大大降低了网络的能量消耗、延长了网络节点的生存期。同时Gossip算法是一种随机路由算法，避免了网络中因信道竞争造成的“丢包”和网络阻塞等问题。并且，整个网络中所有的节点地位对等，没有所谓的“中心节点”，也避免了瓶颈效应的存在。所以Gossip算法是对无线传感器网络中分布式平均共识问题的良好解决方案，因而可以想象Gossip算法也一定同样适用于无线传感器网络分布式定位这一典型的分布式问题。

综上所述，目前广泛使用的单纯TDOA定位方法虽然在无线移动通信网络中性能十分优良，但是在无线传感器网络中的应用依然存在定位精度较低、定位性能有限等问题。而且对于如何在由无线传感器网络的特点所决定的分布式被动定位问题中使用，目前也是一个研究盲点，特别是如何完成类似军事上对于入侵未知节点进行高精度打击，或是对于非法接入频谱的未知无线电台进行精确定位等特殊工程应用问题，也急需研究人员提出切实方案。

发明内容

本发明是要解决无线传感器网络中单纯TDOA定位方法定位精度低，定位性能有限并且无法适用于分布式被动定位这一典型应用场景等问题，而提供了一种将到达时间差算法和Gossip算法有机结合并且适用于无线传感器网络分布式被动定位的全新定位方法。

基于到达时间差和Gossip算法的无线传感器网络分布式定位方法按以下步骤实现：

步骤一：在无线传感器网络覆盖范围内随机或人为布置N个锚节点，每个锚节点借助GPS或人为布置的方式获取自身未知坐标(x_k,y_k,)；

步骤二：整个无线传感器网络中所有锚节点通过广播Gossip算法实现分布式时间同步；

步骤三：每个锚节点在各个时隙随机唤醒，监测未知节点是否出现；

步骤四：如若未知节点出现，则唤醒锚节点k将收到未知节点发射的无线电信号，锚节点k记录收到信号的时刻t_k，连同本地坐标保存在一起(x_k,y_k,t_k)；

步骤五：每个锚节点依次唤醒，重复步骤四，直至所有锚节点均完成未知节点的信号监测和数据保存；

步骤六：无线传感器网络中的锚节点随机唤醒，假设锚节点j处于唤醒状态，该锚节点向通信半径范围内的所有相邻锚节点广播请求，要求其返还节点坐标和接收信号时刻，该锚节点开始接收数据并实时判断是否收到全部相邻锚节点的数据，如若未收到全部相邻锚节点数据，则继续接收，如若收到全部相邻锚节点数据，则完成数据的接收并将锚节点j收到其所有M个相邻锚节点的数据保存在本地，得到本地数据如下

$\left[\begin{array}{ccc}{x}_0^j& y_0^j& t_0^j\end{array}\right]=\left[\begin{array}{ccc}{x}_1& y_1& t_1\\ x_1& y_2& t_2\\ \·& \·& \·\\ \·& \·& \·\\ \·& \·& \·\\ x_i& y_i& t_i\\ \·& \·& \·\\ \·& \·& \·\\ \·& \·& \·\\ x_M& y_M& t_M\end{array}\right];$

步骤七：锚节点j根据步骤六获取的本地数据，根据基于TDOA定位的Taylor算法初始迭代位置公式获取未知节点位置初始迭代值((x_j(0),y_j(0))，根据预先设置的门限运行Taylor算法的迭代过程，直至获取锚节点j对于未知节点位置的初始估计值((x_j(0),y_j(0))；

步骤八：无线传感器网络中的其余锚节点随机唤醒，按照锚节点j的工作方式重复步骤六和步骤七获取本锚节点对于未知节点位置的初始估计值，直至所有锚节点完成对于未知节点位置的初始估计，无线传感器网络中所有锚节点的未知节点位置初始估计值坐标为

$\left[\begin{array}{cc}{x}^{\′}\left(0\right)& y^{\′}\left(0\right)\end{array}\right]=\left[\begin{array}{cc}{x}_1^{\′}\left(0\right)& y_1^{\′}\left(0\right)\\ x_2^{\′}\left(0\right)& y_2^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}\left(0\right)& y_j^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}\left(0\right)& y_N^{\′}\left(0\right)\end{array}\right];$

步骤九：在无线传感器网络中所有锚节点获取本节点对于未知节点位置的初始估计值的基础上，全网所有N个锚节点运行成对Gossip算法，成对Gossip算法具体运行过程如下：假设在时隙t锚节点j被唤醒，该锚节点随机选择一个相邻锚节点i交换初始估计值数据

$x_j^{\′}(t+1)=x_i^{\′}(t+1)=\frac{1}{2}(x_i^{\′}\left(t\right)+x_j^{\′}\left(t\right))$

$y_j^{\′}(t+1)=y_i^{\′}(t+1)=\frac{1}{2}(y_i^{\′}\left(t\right)+y_j^{\′}\left(t\right))$

全网N个锚节点所运行的成对Gossip算法整个迭代过程可以表示如下

$z^{\′}(t+1)=W\left(t\right)z^{\′}\left(t\right)=\underset{n=1}{\overset{t}{\mathrm{\Σ}}}W\left(n\right)z^{\′}\left(0\right)$

其中

$z^{\′}\left(t\right)=\left[\begin{array}{cc}{x}^{\′}\left(t\right)& y^{\′}\left(t\right)\end{array}\right]=\left[\begin{array}{cc}{x}_1^{\′}\left(t\right)& y_1^{\′}\left(t\right)\\ x_2^{\′}\left(t\right)& y_2^{\′}\left(t\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}\left(t\right)& y_j^{\′}\left(t\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}\left(t\right)& y_N^{\′}\left(t\right)\end{array}\right];$

步骤十：判断Gossip算法是否达到预先设定的迭代次数，如若达到预先设定的迭代次数则整个算法完成，无线传感器网络中所有锚节点完成分布式共识定位，各个锚节点获得完全相同的未知节点位置估计值，该方法所获得的最终未知节点位置估计值为

$z^{\′}=\left[\begin{array}{cc}{x}^{\′}& y^{\′}\end{array}\right]=\left[\begin{array}{cc}{x}_1^{\′}& y_1^{\′}\\ x_2^{\′}& y_2^{\′}\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}& y_j^{\′}\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}& y_N^{\′}\end{array}\right]=\frac{1}{N}\stackrel{\→}{1}{\stackrel{\→}{1}}^T\left[\begin{array}{cc}{x}_1^{\′}\left(0\right)& y_1^{\′}\left(0\right)\\ x_2^{\′}\left(0\right)& y_2^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}\left(0\right)& y_j^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}\left(0\right)& y_N^{\′}\left(0\right)\end{array}\right]$

即完成了一种基于到达时间差和Gossip算法的无线传感器网络分布式定位方法。

发明效果：通过对于本发明所提出的基于到达时间差和Gossip算法的无线传感器网络分布式定位方法的仿真分析，可以得到如下结论：(1)在仿真过程中锚节点数目分别设置为5,10,20,30,40,50时，定位精度分别提升了23.37%，58.63%，75.88%，77.84%，83.53%，84.81%，从而证实本发明所提出的算法确实能够有效提高原算法的定位精度，而且根据仿真分析数据可以看出，随着锚节点数目的增多，定位精度也随之增大，但是增加幅度随之减小；(2)在仿真过程中测量时间误差标准差分别设置为3.3ns，6.7ns，10.0ns，13.3ns，16.7ns，也就是换算成对应的测距误差标准差分别为1m，2m，3m，4m，5m时，定位精度分别提升了78.38%，77.61%，76.80%，76.06%，76.68%，同样可以证实本发明所提出的算法确实可以有效提高定位精度，并且定位精度基本满足随着测时误差增大而减小的规律；(3)本发明所提出的算法可以完成分布式共识定位，也就是说网络中每个锚节点借助于成对Gossip算法的帮助获取完全相同的对于未知节点位置的估计值，从而为军事精确打击入侵未知节点或是实时监测接入频谱的非法未知电台等无线传感器网络典型工作领域奠定良好基础。

本发明准备将目光转移到以无线传感器网络为背景的未知节点分布式被动定位领域。发明采用TDOA定位算法作为基本定位技术，同时借助于Gossip算法可以随机选择相邻节点进行信息交换并且最终达到分布式平均共识的特点，全新设计出基于Gossip机制的无线传感器网络分布式到达时间差定位算法。与传统的定位算法相比，该算法不仅具备精确定位精度、优良定位性能等优点，而且完全可以适用于例如通信频谱稀缺环境对于非法使用频谱的无线电台快速精确定位等特殊工程应用背景，通过该全新设计的算法可以使各个锚节点借助Gossip算法获得完全相同的未知节点的位置估计值坐标，从而完成分布式共识定位。

本发明主要针对于以无线传感器网络为背景的工程应用。例如，其典型应用场景可以是对于某通信频谱资源稀缺的区域，随机或人为布置一定数量的监测锚节点，以预防非法未知无线电台接入频谱。当有未知无线电台非法接入频谱时，我方监测锚节点接收未知无线电台发射的无线电信号，并记录收到信号的时间。之后我方监测锚节点使用Gossip算法随机交换坐标和时间数据，在每个监测锚节点上运行TDOA定位算法，获得一个对于未知无线电台的估计位置。此后我方所有监测锚节点参与一个Gossip过程，在运行完Gossip迭代更新后，各个监测锚节点达到分布式平均共识，也就是说每个监测锚节点都获得一个较为精准并且完全相同的未知无线电台位置估计坐标，从而完成分布式共识精确定位，为进一步施行抓获接入频谱的非法未知无线电台奠定良好的基础。

另外在此要特别强调的是，定位精度是定位算法所关心的一个重要指标，一般衡量定位精度的常用度量指标为定位解的均方误差(MSE)或者根均方误差(RMSE)，本算法的仿真便是针对根均方误差展开的。下面给出均方误差和根均方误差在二维空间定位估计中的计算方法：

$\mathrm{MSE}=\frac{1}{\mathrm{MC}}\underset{h=1}{\overset{\mathrm{MC}}{\mathrm{\Σ}}}{(x-x_h)}^2+{(y-y_h)}^2---\left(1\right)$

$\mathrm{RMSE}=\sqrt{\frac{1}{\mathrm{MC}}\underset{h=1}{\overset{\mathrm{MC}}{\mathrm{\Σ}}}{(x-x_h)}^2+{(y-y_h)}^2}---\left(2\right)$

其中，MC为所进行的蒙特卡洛仿真次数，(x,y)为未知节点真实位置，(x_h,y_h)为第h次仿真试验得到的对于未知节点位置的估计值。

通过本发明所做的仿真结果及分析，可以看出发明所提出的基于Gossip的Taylor定位算法(PGA-Taylor)能够取得最优的定位精度。因而本发明所提出的基于Gossip的Taylor定位算法确实是一种可以获得更小定位精度，并且能够实现无线传感器网络的分布式共识定位的一种优秀定位算法。通过仿真验证已经证实其有效性和优异性，可以说该算法是一种在无线传感器网络定位领域值得推广的定位算法。

附图说明

图1是本发明提出的PGA-Taylor算法的流程图；

图2是具体实施方式一中的根均方误差随锚节点数目增加时的变化曲线；其中

表示Taylor，

表示PGA-Taylor；

图3是根均方误差随所测时间误差标准差增加时的变化曲线；其中

表示Taylor，

表示PGA-Taylor。

具体实施方式

具体实施方式一：本实施方式的基于到达时间差和Gossip算法的无线传感器网络分布式定位方法按以下步骤实现：

步骤一：在无线传感器网络覆盖范围内随机或人为布置N个锚节点，每个锚节点借助GPS或人为布置的方式获取自身未知坐标(x_k,y_k,)；

步骤二：整个无线传感器网络中所有锚节点通过广播Gossip算法实现分布式时间同步；

步骤三：每个锚节点在各个时隙随机唤醒，监测未知节点是否出现；

步骤四：如若未知节点出现，则唤醒锚节点k将收到未知节点发射的无线电信号，锚节点k记录收到信号的时刻t_k，连同本地坐标保存在一起(x_k,y_k,t_k)；

步骤五：每个锚节点依次唤醒，重复步骤四，直至所有锚节点均完成未知节点的信号监测和数据保存；

步骤六：无线传感器网络中的锚节点随机唤醒，假设锚节点j处于唤醒状态，该锚节点向通信半径范围内的所有相邻锚节点广播请求，要求其返还节点坐标和接收信号时刻，该锚节点开始接收数据并实时判断是否收到全部相邻锚节点的数据，如若未收到全部相邻锚节点数据，则继续接收，如若收到全部相邻锚节点数据，则完成数据的接收并将锚节点j收到其所有M个相邻锚节点的数据保存在本地，得到本地数据如下

$\left[\begin{array}{ccc}{x}_0^j& y_0^j& t_0^j\end{array}\right]=\left[\begin{array}{ccc}{x}_1& y_1& t_1\\ x_1& y_2& t_2\\ \·& \·& \·\\ \·& \·& \·\\ \·& \·& \·\\ x_i& y_i& t_i\\ \·& \·& \·\\ \·& \·& \·\\ \·& \·& \·\\ x_M& y_M& t_M\end{array}\right];$

步骤七：锚节点j根据步骤六获取的本地数据，根据基于TDOA定位的Taylor算法初始迭代位置公式获取未知节点位置初始迭代值((x_j(0),y_j(0))，根据预先设置的门限运行Taylor算法的迭代过程，直至获取锚节点j对于未知节点位置的初始估计值((x_j(0),y_j(0))；

步骤八：无线传感器网络中的其余锚节点随机唤醒，按照锚节点j的工作方式重复步骤六和步骤七获取本锚节点对于未知节点位置的初始估计值，直至所有锚节点完成对于未知节点位置的初始估计，无线传感器网络中所有锚节点的未知节点位置初始估计值坐标为

$\left[\begin{array}{cc}{x}^{\′}\left(0\right)& y^{\′}\left(0\right)\end{array}\right]=\left[\begin{array}{cc}{x}_1^{\′}\left(0\right)& y_1^{\′}\left(0\right)\\ x_2^{\′}\left(0\right)& y_2^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}\left(0\right)& y_j^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}\left(0\right)& y_N^{\′}\left(0\right)\end{array}\right];$

步骤九：在无线传感器网络中所有锚节点获取本节点对于未知节点位置的初始估计值的基础上，全网所有N个锚节点运行成对Gossip算法，成对Gossip算法具体运行过程如下：假设在时隙t锚节点j被唤醒，该锚节点随机选择一个相邻锚节点i交换初始估计值数据

$x_j^{\′}(t+1)=x_i^{\′}(t+1)=\frac{1}{2}(x_i^{\′}\left(t\right)+x_j^{\′}\left(t\right))$

$y_j^{\′}(t+1)=y_i^{\′}(t+1)=\frac{1}{2}(y_i^{\′}\left(t\right)+y_j^{\′}\left(t\right))$

全网N个锚节点所运行的成对Gossip算法整个迭代过程可以表示如下

$z^{\′}(t+1)=W\left(t\right)z^{\′}\left(t\right)=\underset{n=1}{\overset{t}{\mathrm{\Σ}}}W\left(n\right)z^{\′}\left(0\right)$

其中

$z^{\′}\left(t\right)=\left[\begin{array}{cc}{x}^{\′}\left(t\right)& y^{\′}\left(t\right)\end{array}\right]=\left[\begin{array}{cc}{x}_1^{\′}\left(t\right)& y_1^{\′}\left(t\right)\\ x_2^{\′}\left(t\right)& y_2^{\′}\left(t\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}\left(t\right)& y_j^{\′}\left(t\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}\left(t\right)& y_N^{\′}\left(t\right)\end{array}\right];$

步骤十：判断Gossip算法是否达到预先设定的迭代次数，如若达到预先设定的迭代次数则整个算法完成，无线传感器网络中所有锚节点完成分布式共识定位，各个锚节点获得完全相同的未知节点位置估计值，该方法所获得的最终未知节点位置估计值为

$z^{\′}=\left[\begin{array}{cc}{x}^{\′}& y^{\′}\end{array}\right]=\left[\begin{array}{cc}{x}_1^{\′}& y_1^{\′}\\ x_2^{\′}& y_2^{\′}\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}& y_j^{\′}\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}& y_N^{\′}\end{array}\right]=\frac{1}{N}\stackrel{\→}{1}{\stackrel{\→}{1}}^T\left[\begin{array}{cc}{x}_1^{\′}\left(0\right)& y_1^{\′}\left(0\right)\\ x_2^{\′}\left(0\right)& y_2^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}\left(0\right)& y_j^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}\left(0\right)& y_N^{\′}\left(0\right)\end{array}\right]$

即完成了一种基于到达时间差和Gossip算法的无线传感器网络分布式定位方法。

本实施方式，步骤二中，广播Gossip算法是Gossip算法中的一种，不同于成对Gossip算法，无法保证最终收敛于所有初始值的均值，其典型应用就是完成分布式时钟同步；

步骤十中，迭代次数的选择根据具体网络拓扑结构和需求的精度选择Gossip算法的迭代次数，保证算法能够收敛于初始均值。

具体实施方式二：本实施方式与具体实施方式一不同的是：步骤二中所述的广播Gossip算法具体为：

网络中的节点随机唤醒并且广播其状态值，该状态值被其通信半径内的所有节点接收，所有接收节点按照算法设计更新其本地状态值，其他节点状态值保持不变。其它步骤及参数与具体实施方式一相同。

具体实施方式三：本实施方式与具体实施方式一或二不同的是：

一、TDOA定位

首先假设所有锚节点已通过广播Gossip算法达到分布式时间同步，锚节点的通信半径受网络中TDOA定位硬件模块的限制，N点无线传感器网络的拓扑结构G(N,R)由邻接矩阵Φ_ij表示，当i≠j时，如果锚节点i和锚节点j相邻，则Φ_ij=1；否则，Φ_ij=0；对于锚节点j，定义M={i∈{1,2,...,N}:Φ_ij≠0}；

TDOA定位算法又叫做双曲线定位算法，其数学机理是求取双曲线的交点从而获得未知节点的估计位置；对于唤醒锚节点j，其双曲线方程为

$R_{i,j}=R_i-R_j=\sqrt{{(x_i-x)}^2+{(y_i-y)}^2}-\sqrt{{(x_j-x)}^2+{(y_j-y)}^2}---\left(3\right)$

其中R_i为未知节点到第i个锚节点的距离，R_j为信号源到达唤醒锚节点(定义锚节点j为服务唤醒锚节点)的距离，R_i,j为未知节点到第i个锚节点和唤醒锚节点j的距离差，R_i,j=c(t_i-t_j)，其中c为光速，t_i和t_j分别为节点i和节点j接收到未知节点发射信号的时刻；在其中令i=1,2,…,M，(x,y)为未知节点的坐标，(x_i,y_i)为第i个锚节点的位置坐标，(x_j,y_j)为唤醒锚节点位置坐标；

二、Taylor算法

对双曲线方程(3)进行线性化，采用Taylor级数展开算法，Taylor级数展开算法是一种需要信号源初始估计位置的递归算法，在每一次递归中通过求解TDOA测量误差的局部最小二乘解来改进对信号源的估计位置。在实际应用中，Taylor级数展开法通常具有较好的定位性能。

Taylor序列展开式需要初始估计位置，在每一次递归中通过求解TDOA测量误差的局部最小二乘解来改进估计位置。对于一组TDOA测量值，该算法首先选取初始迭代位置，具体按如下方式选取

$p={\left(G_a^T{Q}^{-1}{G}_a\right)}^{-1}{G}_a^T{Q}^{-1}h---\left(4\right)$

其中，Q为TDOA的协方差矩阵

$h=\frac{1}{2}\left[\begin{array}{c}{R}_{1,j}^2-x_1^2-y_1^2+x_j^2+y_j^2\\ R_{2,j}^2-x_2^2-y_2^2+x_j^2+y_j^2\\ \·\\ \·\\ \·\\ R_{M,j}^2-x_M^2-y_M^2+x_j^2+y_j^2\end{array}\right],G_a=-\left[\begin{array}{ccc}{x}_{1,j}& y_{1,j}& R_{1,j}\\ x_{2,j}& y_{2,j}& R_{2,j}\\ \·& \·& \·\\ \·& \·& \·\\ \·& \·& \·\\ x_{M,j}& y_{M,j}& R_{M,j}\end{array}\right]$

公式中(x_i,j,y_i,j)为第i个锚节点与唤醒锚节点j之间的坐标差值。

Taylor级数展开算法对于未知节点位置的初始迭代值按如下公式选取

$\left\{\begin{array}{c}{x}_j\left(0\right)=p\left(1\right)\\ y_j\left(0\right)=p\left(2\right)\end{array}\right.---\left(5\right)$

下一次递归中令：

x′_j(0)=x_j(0)+△x,y′_j(0)=y_j(0)+△y           (6)

△x、△y按如下方式选取

$\mathrm{\δ}=\left[\begin{array}{c}\mathrm{\Δx}\\ \mathrm{\Δy}\end{array}\right]={\left(G_t^T{Q}^{-1}{G}_t\right)}^{-1}{G}_t^T{Q}^{-1}{h}_t---\left(7\right)$

其中

$h_t=\left[\begin{array}{c}{R}_{1,j}-R_1+R_j\\ R_{2,j}-R_2+R_j\\ \·\\ \·\\ \·\\ R_{M,j}-R_M+R_j\end{array}\right],G_t=\left[\begin{array}{cc}(x_j-x)/R_j-(x_1-x)/R_1& (y_j-y)/R_j-(y_1-y)/R_1\\ (x_j-x)/R_j-(x_2-x)/R_2& (y_j-y)/R_j-(y_2-y)/R_2\\ \·& \·\\ \·& \·\\ \·& \·\\ (x_j-x)/R_j-(x_M-x)/R_M& (y_j-y)/R_j-(y_M-y)/R_M\end{array}\right]$

重复以上过程，直到△x、△y足够小，满足一定门限：

其中ε是一个很小的正数，此时的((x′_j(0),y′_j(0))即为锚节点j对于未知节点位置的初始估计值。

其它步骤及参数与具体实施方式一或二相同。

具体实施方式四：本实施方式与具体实施方式一至三之一不同的是：

假设无线传感器网络有N个传感器节点，每个传感器节点j在t时刻有一个状态值a_j(t)，t=1,2,…；

在Gossip算法开始阶段即t=0，每个传感器节点j依据任务需要获取自己的状态值a_j(0)，该值可以是任意欲监测的信息值；随后，无线传感器网络中任意传感器节点j可以在时刻t被随机激活并和它随机选定的具备状态值a_i(t)的相邻传感器节点i交换状态值，典型公式为

$a_j(t+1)=a_i(t+1)=\frac{1}{2}(a_i\left(t\right)+a_j\left(t\right))---\left(9\right)$

把无线传感器网络中所有传感器节点的状态用一个N维向量a(t)来表示，为了便于研究，把(9)式改写成向量的形式：

a(t+1)=W(t)a(t)               (10)其中W(t)是一个随机矩阵，它主要取决于时隙t内被唤醒的传感器节点，这样就得到了经典成对Gossip算法的一般数学模型。从算法模型可以看出，经典成对单播Gossip算法的实现十分简单，而且关键问题是其收敛性也已经得到了理论证明。，Gossip算法的目的就是通过尽量少的迭代次数，使网络中每个节点j的状态值均收敛于所有传感器节点初始状态值的均值 $(1/N){\mathrm{\Σ}}_{m=1}^N{a}_m\left(0\right).$

其它步骤及参数与具体实施方式一至三之一相同。

仿真实验：

本仿真在100m×100m的二维平面内进行定位算法仿真，假设未知节点位置坐标为(20m,20m)。TDOA测时误差满足零均值的高斯分布，Taylor算法迭代门限设置为ε=10^-8。说明书附图2为分别对锚节点数目N=5,10,20,30,40,50的情况进行仿真，本仿真锚节点位置在100m×100m范围内随机布置。本发明分别画出原始Taylor算法和基于Gossip的Taylor定位算法(PGA-Taylor)随着锚节点数目增加时的均方根误差曲线，整个仿真中的数据是进行1000次独立实验取平均值后获得的结果。本仿真实验在仿真过程中锚节点数目分别设置为5,10,20,30,40,50时，定位精度分别提升了23.37%，58.63%，75.88%，77.84%，83.53%，84.81%，从而证实本发明所提出的PGA-Taylor算法确实能够有效提高原算法的定位精度，而且根据仿真分析数据可以看出，随着锚节点数目的增多，定位精度也随之增大，但是增加幅度随之减小。说明书附图3为固定锚节点数目N=20且锚节点位置亦在100m×100m范围内随机分布时，对于均方根误差随测时误差标准差变化的情况所进行的仿真。依然分别为Taylor算法和PGA-Taylor算法随着测时误差变大时的均方根误差曲线，整个仿真实验也是进行1000次独立实验平均后的结果。在本次仿真过程中，测量时间误差标准差分别设置为3.3ns，6.7ns，10.0ns，13.3ns，16.7ns，也就是换算成对应的测距误差标准差分别为1m，2m，3m，4m，5m时，定位精度分别提升了78.38%，77.61%，76.80%，76.06%，76.68%，同样可以证实本发明所提出的算法确实可以有效提高定位精度，并且定位精度基本满足随着测时误差增大而减小的规律。

Claims (4)

1.一种基于到达时间差和Gossip算法的无线传感器网络分布式定位方法，其特征在于基于到达时间差和Gossip算法的无线传感器网络分布式定位方法按以下步骤实现：

步骤一：在无线传感器网络覆盖范围内随机或人为布置N个锚节点，每个锚节点借助GPS或人为布置的方式获取自身未知坐标(x_k,y_k,)；

步骤二：整个无线传感器网络中所有锚节点通过广播Gossip算法实现分布式时间同步；

步骤三：每个锚节点在各个时隙随机唤醒，监测未知节点是否出现；

步骤四：如若未知节点出现，则唤醒锚节点k将收到未知节点发射的无线电信号，锚节点k记录收到信号的时刻t_k，连同本地坐标保存在一起(x_k,y_k,t_k)；

步骤五：每个锚节点依次唤醒，重复步骤四，直至所有锚节点均完成未知节点的信号监测和数据保存；

步骤六：无线传感器网络中的锚节点随机唤醒，假设锚节点j处于唤醒状态，该锚节点向通信半径范围内的所有相邻锚节点广播请求，要求其返还节点坐标和接收信号时刻，该锚节点开始接收数据并实时判断是否收到全部相邻锚节点的数据，如若未收到全部相邻锚节点数据，则继续接收，如若收到全部相邻锚节点数据，则完成数据的接收并将锚节点j收到其所有M个相邻锚节点的数据保存在本地，得到本地数据如下

$\left[\begin{array}{ccc}{x}_0^j& y_0^j& t_0^j\end{array}\right]=\left[\begin{array}{ccc}{x}_1& y_1& t_1\\ x_1& y_2& t_2\\ \·& \·& \·\\ \·& \·& \·\\ \·& \·& \·\\ x_i& y_i& t_i\\ \·& \·& \·\\ \·& \·& \·\\ \·& \·& \·\\ x_M& y_M& t_M\end{array}\right];$

步骤七：锚节点j根据步骤六获取的本地数据，根据基于TDOA定位的Taylor算法初始迭代位置公式获取未知节点位置初始迭代值((x_j(0),y_j(0))，根据预先设置的门限运行Taylor算法的迭代过程，直至获取锚节点j对于未知节点位置的初始估计值((x_j(0),y_j(0))；

步骤八：无线传感器网络中的其余锚节点随机唤醒，按照锚节点j的工作方式重复步骤六和步骤七获取本锚节点对于未知节点位置的初始估计值，直至所有锚节点完成对于未知节点位置的初始估计，无线传感器网络中所有锚节点的未知节点位置初始估计值坐标为

$\left[\begin{array}{cc}{x}^{\′}\left(0\right)& y^{\′}\left(0\right)\end{array}\right]=\left[\begin{array}{cc}{x}_1^{\′}\left(0\right)& y_1^{\′}\left(0\right)\\ x_2^{\′}\left(0\right)& y_2^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}\left(0\right)& y_j^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}\left(0\right)& y_N^{\′}\left(0\right)\end{array}\right];$

步骤九：在无线传感器网络中所有锚节点获取本节点对于未知节点位置的初始估计值的基础上，全网所有N个锚节点运行成对Gossip算法，成对Gossip算法具体运行过程如下：假设在时隙t锚节点j被唤醒，该锚节点随机选择一个相邻锚节点i交换初始估计值数据

$x_j^{\′}(t+1)=x_i^{\′}(t+1)=\frac{1}{2}(x_i^{\′}\left(t\right)+x_j^{\′}\left(t\right))$

$y_j^{\′}(t+1)=y_i^{\′}(t+1)=\frac{1}{2}(y_i^{\′}\left(t\right)+y_j^{\′}\left(t\right))$

全网N个锚节点所运行的成对Gossip算法整个迭代过程可以表示如下

$z^{\′}(t+1)=W\left(t\right)z^{\′}\left(t\right)=\underset{n=1}{\overset{t}{\mathrm{\Σ}}}W\left(n\right)z^{\′}\left(0\right)$

其中

$z^{\′}\left(t\right)=\left[\begin{array}{cc}{x}^{\′}\left(t\right)& y^{\′}\left(t\right)\end{array}\right]=\left[\begin{array}{cc}{x}_1^{\′}\left(t\right)& y_1^{\′}\left(t\right)\\ x_2^{\′}\left(t\right)& y_2^{\′}\left(t\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}\left(t\right)& y_j^{\′}\left(t\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}\left(t\right)& y_N^{\′}\left(t\right)\end{array}\right];$

步骤十：判断Gossip算法是否达到预先设定的迭代次数，如若达到预先设定的迭代次数则整个算法完成，无线传感器网络中所有锚节点完成分布式共识定位，各个锚节点获得完全相同的未知节点位置估计值，该方法所获得的最终未知节点位置估计值为

$z^{\′}=\left[\begin{array}{cc}{x}^{\′}& y^{\′}\end{array}\right]=\left[\begin{array}{cc}{x}_1^{\′}& y_1^{\′}\\ x_2^{\′}& y_2^{\′}\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}& y_j^{\′}\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}& y_N^{\′}\end{array}\right]=\frac{1}{N}\stackrel{\→}{1}{\stackrel{\→}{1}}^T\left[\begin{array}{cc}{x}_1^{\′}\left(0\right)& y_1^{\′}\left(0\right)\\ x_2^{\′}\left(0\right)& y_2^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_j^{\′}\left(0\right)& y_j^{\′}\left(0\right)\\ \·& \·\\ \·& \·\\ \·& \·\\ x_N^{\′}\left(0\right)& y_N^{\′}\left(0\right)\end{array}\right]$

即完成了一种基于到达时间差和Gossip算法的无线传感器网络分布式定位方法。

2.根据权利要求1所述的一种基于到达时间差和Gossip算法的无线传感器网络分布式定位方法，其特征在于步骤二中所述的广播Gossip算法具体为：

网络中的节点随机唤醒并且广播其状态值，该状态值被其通信半径内的所有节点接收，所有接收节点按照算法设计更新其本地状态值，其他节点状态值保持不变。

3.根据权利要求1或2所述的一种基于到达时间差和Gossip算法的无线传感器网络分布式定位方法，其特征在于步骤七中所述的基于TDOA定位的Taylor算法具体为：

一、TDOA定位

首先假设所有锚节点已通过广播Gossip算法达到分布式时间同步，锚节点的通信半径受网络中TDOA定位硬件模块的限制，N点无线传感器网络的拓扑结构G(N,R)由邻接矩阵Φ_ij表示，当i≠j时，如果锚节点i和锚节点j相邻，则Φ_ij=1；否则，Φ_ij=0；对于锚节点j，定义M={i∈{1,2,...,N}:Φ_ij≠0}；

对于唤醒锚节点j，其双曲线方程为

$R_{i,j}=R_i-R_j=\sqrt{{(x_i-x)}^2+{(y_i-y)}^2}-\sqrt{{(x_j-x)}^2+{(y_j-y)}^2}---\left(1\right)$

其中R_i为未知节点到第i个锚节点的距离，R_j为信号源到达唤醒锚节点的距离，R_i,j为未知节点到第i个锚节点和唤醒锚节点j的距离差，R_i,j=c(t_i-t_j)，其中c为光速，t_i和t_j分别为节点i和节点j接收到未知节点发射信号的时刻；在其中令i=1,2,…,M，(x,y)为未知节点的坐标，(x_i,y_i)为第i个锚节点的位置坐标，(x_j,y_j)为唤醒锚节点位置坐标；

二、Taylor算法

采用Taylor算法对双曲线方程(1)进行线性化，Taylor序列展开式需要初始估计位置，在每一次递归中通过求解TDOA测量误差的局部最小二乘解来改进估计位置，对于一组TDOA测量值，该算法首先选取初始迭代位置，具体按如下方式选取

$p={\left(G_a^T{Q}^{-1}{G}_a\right)}^{-1}{G}_a^T{Q}^{-1}h---\left(2\right)$

其中，Q为TDOA的协方差矩阵

$h=\frac{1}{2}\left[\begin{array}{c}{R}_{1,j}^2-x_1^2-y_1^2+x_j^2+y_j^2\\ R_{2,j}^2-x_2^2-y_2^2+x_j^2+y_j^2\\ \·\\ \·\\ \·\\ R_{M,j}^2-x_M^2-y_M^2+x_j^2+y_j^2\end{array}\right],G_a=-\left[\begin{array}{ccc}{x}_{1,j}& y_{1,j}& R_{1,j}\\ x_{2,j}& y_{2,j}& R_{2,j}\\ \·& \·& \·\\ \·& \·& \·\\ \·& \·& \·\\ x_{M,j}& y_{M,j}& R_{M,j}\end{array}\right]$

公式中(x_i,j,y_i,j)为第i个锚节点与唤醒锚节点j之间的坐标差值；

Taylor算法对于未知节点位置的初始迭代值按如下公式选取

$\left\{\begin{array}{c}{x}_j\left(0\right)=p\left(1\right)\\ y_j\left(0\right)=p\left(2\right)\end{array}\right.---\left(3\right)$

下一次递归中令：

x′_j(0)=x_j(0)+△x,y′_j(0)=y_j(0)+△y          (4)

△x、△y按如下方式选取

$\mathrm{\δ}=\left[\begin{array}{c}\mathrm{\Δx}\\ \mathrm{\Δy}\end{array}\right]={\left(G_t^T{Q}^{-1}{G}_t\right)}^{-1}{G}_t^T{Q}^{-1}{h}_t---\left(5\right)$

其中

$h_t=\left[\begin{array}{c}{R}_{1,j}-R_1+R_j\\ R_{2,j}-R_2+R_j\\ \·\\ \·\\ \·\\ R_{M,j}-R_M+R_j\end{array}\right],G_t=\left[\begin{array}{cc}(x_j-x)/R_j-(x_1-x)/R_1& (y_j-y)/R_j-(y_1-y)/R_1\\ (x_j-x)/R_j-(x_2-x)/R_2& (y_j-y)/R_j-(y_2-y)/R_2\\ \·& \·\\ \·& \·\\ \·& \·\\ (x_j-x)/R_j-(x_M-x)/R_M& (y_j-y)/R_j-(y_M-y)/R_M\end{array}\right]$

重复以上过程，直到△x、△y足够小，满足设定门限：

其中ε是一个很小的正数，此时的((x′_j(0),y′_j(0))即为锚节点j对于未知节点位置的初始估计值。

4.根据权利要求1或2所述的一种基于到达时间差和Gossip算法的无线传感器网络分布式定位方法，其特征在于步骤九中所述成对Gossip算法具体为：

假设无线传感器网络有N个传感器节点，每个传感器节点j在t时刻有一个状态值a_j(t)，t=1,2,…；

在Gossip算法开始阶段即t=0，每个传感器节点j依据任务需要获取自己的状态值a_j(0)；随后，无线传感器网络中任意传感器节点j可以在时刻t被随机激活并和它随机选定的具备状态值a_i(t)的相邻传感器节点i交换状态值，典型公式为

$a_j(t+1)=a_i(t+1)=\frac{1}{2}(a_i\left(t\right)+a_j\left(t\right))---\left(7\right)$

把无线传感器网络中所有传感器节点的状态用一个N维向量a(t)来表示，把(7)式改写成向量的形式：

a(t+1)=W(t)a(t)              (8)

其中W(t)是一个随机矩阵，它主要取决于时隙t内被唤醒的传感器节点，得到经典成对Gossip算法的一般数学模型，Gossip算法通过尽量少的迭代次数，使网络中每个节点的状态值均收敛于所有传感器节点初始状态值的均值

Images