无线传感器网络定位跟踪与时间同步技术

1、无线传感器网络技术及其应用第四章 无线传感器网络定位、跟踪与时间同步技术课程目录4.14.2无线传感器网络定位技术无线传感器网络跟踪技术无线传感器网络时间同步技术4.3无线传感器网络的发展与安全趋势4.1无线传感器网络定位技术定位是无线传感器网络重要的支撑技术，定位就是确定位置。无线传感器网络的定位是指自组织的网络通过特定方法提供节点位置信息。这种自组织网络定位分为节点自身定位和目标定位。节点自身定位是确定网络中节点为坐标位置的过程。目标定位是确定网络覆盖范围内目标的坐标位置。14.1无线传感器网络定位技术在传感器网络中，没有统一的最优的定位算法，只有针对特定环境比较适合的定位算法。按照下面的

2、标准对定位算法进行分类：1基于测距的定位和无需测距的定位2绝对定位与相对定位3集中式计算、分布式计算与递增式计算24.1无线传感器网络定位技术1基于测距的定位和无需测距的定位前者需要测量相邻节点之间的绝对距离或者方位，并利用节点间的实际距离或者方位来计算未知节点的位置，常用的测距技术有RSSI（到达信号强度测量法）、TOA（到达时间测量法）、TDOA（到达时间差测量法）等。虽然在定位精度上有一定可取之处，但是并不适用于低功耗、低成本的领域。基于无需测距的定位算法无需测量节点之间的绝对距离或方位，而是利用节点间的估计距离计算节点的位置，如典型的DV-Hop定位、凸规划定位。虽然在精确度方面有待进

3、一步改进，但是具有可扩展性、规模性以及代价小等优点。34.1无线传感器网络定位技术2绝对定位与相对定位绝对定位的定位结果是一个标准的坐标位置，如经纬度；而相对定位通常是以网络中部分节点为参考，建立整个网络的相对坐标系统。绝对定位可为网络提供唯一的命名空间，受网络变动影响较小，有非常广泛的应用领域。大多数定位系统都可以实现绝对定位，只有部分定位系统和算法能实现相对定位。44.1无线传感器网络定位技术3集中式计算、分布式计算与递增式计算集中式计算是指把所需要的定位信息集中传送到某个中心节点（如汇聚节点），由该节点进行集中计算未知节点的位置。分布式计算是指由节点间进行信息交换，未知节点根据自身获取足

4、够的信息进行自身位置计算的计算方式。集中式计算的优点是可以从全局角度出发更好地进行规划，从而获得相对精确的定位。缺点是中心节点以及它周围的节点通信开销过大、能耗过快，易造成个别节点过早死亡，从而影响其它节点的定位。分布式计算可使网络中所有节点同时进行位置计算。递增式计算通常是从信标节点开始，信标节点周围的节点首先开始定位，依次向外延伸，逐步实现整个网络的定位。递增式算法的缺点是在定位过程中误差容易被积累和放大。5课程目录4.14.2无线传感器网络定位技术无线传感器网络跟踪技术无线传感器网络时间同步技术4.3无线传感器网络的发展与安全趋势课程目录4.1.14.1.2无线传感器网络测距技术无线传感

5、器网络定位机制与性能评价标准现有无线传感器网络定位方法4.1.3无线传感器网络定位技术4.14.1.1无线传感器网络测距技术测距即测量两个节点之间的距离，一般常采用物理信号测量方式，如无线电、声波和磁场等。根据各种物理信号的优缺点，常用的方法有到达时间测量法（TOA）、到达时间差测量法（TDOA）、到达信号强度测量法（RSS）等。1测距中用到的基本术语: 接收新信号强度指示（Received Signal Strength Indicator，RSSI）：节点接收到无线信号的强度的大小，称为接收信号的强度指示。 到达角度（Angle of Arrival，AOA）：节点接收到的信号相对于自身轴

6、线的角度，称为信号相对接收节点的到达角度。 视线关系（Line of Sight，LOS）：两个节点间没有障碍物间隔，能够直接通信，称为两个节点间存在视线关系。 非视线关系（NLOS，no LOS）：两个节点之间存在障碍物。24.1.1无线传感器网络测距技术一些测距方法:1到达时间测量法（Time of Arrival，TOA）2到达时间差测量法（Time Difference of Arrival，TDOA）3到达信号强度测量法（RSSI）34.1.1无线传感器网络测距技术1到达时间测量法（Time of Arrival，TOA）已知物理信号的传播速度v，根据信号的传播时间t来计算节点间的距

7、离，即距离d=vt。此方法要求进行通信的两个节点时间必须高度同步。44.1.1无线传感器网络测距技术2到达时间差测量法（Time Difference of Arrival，TDOA）发送节点同时发射两种不同速率的无线信号，接收节点根据两种信号的时间到达差和速率，计算这两个节点之间的距离。节点A在T0时刻同时发射无线射频信号和超声波信号，节点B分别记录这两种物理信号的到达时间T1和T2，已知无线射频信号和超声波的速率分别为v1，v2，设两节点之间的距离为d，由 可得：54.1.1无线传感器网络测距技术64.1.1无线传感器网络测距技术3到达信号强度测量法（RSSI）信号强度会随着其传播距离的增

8、加而衰减,表明信号强度变化与传播距离间存在着某种函数关系。无线信道的数学模型如式： d是发射机和接收机之间的距离，d0是参考距离；n是信道衰减指数，一般取值24；X是均值为零、方差的高斯随机变量；PL(d0)是距离发射机d0处的信号强度。它是一种低功率、廉价的测距技术，但是信号强度很容易受到周围环境的影响，通常将其看做一种粗糙的测距技术。74.1.1无线传感器网络测距技术课程目录4.14.2无线传感器网络定位技术无线传感器网络跟踪技术无线传感器网络时间同步技术4.3无线传感器网络的发展与安全趋势课程目录4.1.14.1.2无线传感器网络测距技术无线传感器网络定位机制与性能评价标准现有无线传感器

9、网络定位方法4.1.3无线传感器网络定位技术4.11定位机制解析几何中的任何可以确定某一点位置的几何学方法，只要传感器网络能够提供足够的信息，都可以成为定位的方法。比较常用的是三边定位法、多边极大似然估计法以及角度测量法。定义： 信标节点：已知节点坐标或者位置信息的节点，有的书籍也称为锚节点。 未知节点：坐标或者位置信息未知的节点。14.1.2无线传感器网络定位机制与性能评价标准（1）三边定位法已知3个信标节点的坐标和其中1个未知节点到3个信标节点的距离，求该未知节点的坐标。24.1.2无线传感器网络定位机制与性能评价标准设未知节点D的坐标为（x，y），信标节点的A、B、C的坐标分别为（xA，

10、yA）、（xB，yB）、（xA，yC），未知节点到3个信标节点的距离分别为dA、dB、dC，则从而可以推出未知节点的坐标为34.1.2无线传感器网络定位机制与性能评价标准（2）多边极大似然估计法多边极大似然估计法是指已知3个以上的信标节点的坐标和它们到未知节点的距离，求解该未知节点的坐标。设节点1，2，3，4，n个节点的坐标分别为 、 、 、 ，它们到节点D的距离分别为d1、d2、d3、dn，节点D的坐标为（x，y），则44.1.2无线传感器网络定位机制与性能评价标准54.1.2无线传感器网络定位机制与性能评价标准从第一个方程开始分别减去最后一个方程可得如下线性方程：64.1.2无线传感器网络

11、定位机制与性能评价标准简化为矩阵相乘的方式：AX=b使用标准的最小均方差估计方法可以得到节点D的坐标为：74.1.2无线传感器网络定位机制与性能评价标准（3）角度测量法原理如图4-4所示，已知信标节点A、B、C的坐标分别为 ， ， 和3个内角 、 、 。设未知节点D的坐标为 ，则对于节点A、C和角 ，如果弧段AC在 中，那么能够唯一确定一个圆，设圆心 ，半径为r1，则 ，并存在下列公式：能够确定圆心O1点的坐标和半径r1。同理对A、B，ADB和B、C，BDC分别能够确定相应的圆心 、半径r2、圆心 、半径r3。84.1.2无线传感器网络定位机制与性能评价标准最后，利用三边定位法，由点 ， ，

12、确定节点D的坐标。94.1.2无线传感器网络定位机制与性能评价标准2定位性能评价标准无线传感器网络自身定位系统和算法有很多，它们的性能直接影响其可用性。几个常用的评价标准：（1）定位精度定位精度是指定位系统提供的位置信息的精确程度，是评价指标中的首要标准。定位精度有相对精度和绝对精度。精度越高，技术要求越高，成本也相应越高。绝对精度是指以长度为量度的精度。相对精度通常以误差值与节点的无线射程的比例表示。104.1.2无线传感器网络定位机制与性能评价标准（2）覆盖范围覆盖范围是指节点的射程范围，覆盖范围越大，精度越高的定位机制是最佳的选择。覆盖范围和定位精度是一对矛盾。覆盖范围越大，提供的精度越

13、低。在实际应用中可以根据具体情况在覆盖范围和定位精度之间做出折中，以达到较好的定位效果。114.1.2无线传感器网络定位机制与性能评价标准（3）信标节点密度不同的定位方案对信标节点的数量要求不同，如三边定位算法要求3个信标节点、多边极大似然估计法需要至少3个信标节点。信标节点一般都是通过人工部署或者全球定位系统（GPS）获取其地址的。信标节点的密度越小越好。124.1.2无线传感器网络定位机制与性能评价标准（4）容错性和鲁棒性定位算法通常是在比较理想的通信环境和一些测量指标比较准确的情况下才能达到精确定位。在实际网络环境定位过程中，通常存在因为周围环境的影响而产生的测离和角度误差太大从而影响定

14、位精度，网络节点能量耗尽、物理损伤等自身原因而过早死亡，引起其他节点的定位过程中断或者不能实现等诸多情况。因此，定位系统要有一定的容错性和鲁棒性从而减小定位误差提高定位精度，以更好地适应周围环境。134.1.2无线传感器网络定位机制与性能评价标准课程目录4.14.2无线传感器网络定位技术无线传感器网络跟踪技术无线传感器网络时间同步技术4.3无线传感器网络的发展与安全趋势课程目录4.1.14.1.2无线传感器网络测距技术无线传感器网络定位机制与性能评价标准现有无线传感器网络定位方法4.1.3无线传感器网络定位技术4.11Cricket定位系统2质心定位算法3TOA和TDOA定位方法4AOA定位算

15、法5RSSI定位方法6DV-HOP定位方法7Amorphous定位方法8APIT定位方法14.1.3现有无线传感器网络定位方法1Cricket定位系统Cricket是一种基于TDOA测距技术的室内定位系统，与其他定位系统不同的是，它通过测量到未知节点最近的信标节点计算静止或者移动目标在大楼内具体房间的哪一区域，而不是绝对位置。Cricket系统没有中心管理或者控制系统，而是分布式管理，为了更好地通信，把信标节点和发射器布置在天花板上。24.1.3现有无线传感器网络定位方法2质心定位算法质心定位算法是一种与距离无关的估计定位算法，质心也即多边形的几何中心，多边形的顶点坐标的平均值为质心坐标。多边

16、形ABCD的顶点是 ， ， ， ，则质心坐标为 在质心算法中首先确定未知节点的所在区域，计算这个区域的质心坐标，并将该质心坐标作为此未知节点的坐标。它不需要信标节点和未知节点之间的协调，因此实现起来比较简单，算法复杂度比较低。34.1.3现有无线传感器网络定位方法3TOA和TDOA定位方法Girod L等利用TOA测距技术实现了网络定位。该系统中假设发送节点和接收节点时间同步并且每个节点均包含一个发射机和一个接收机，发射机发射一种命名为chirp的声波，并且同时在该声波中包含了发送时间。当接收机收到chirp声波后从中提取发送时间，利用声波在大气中的传播模型计算发送节点和接收节点之间的距离。节

17、点在计算出与多个临近信标节点之间的距离后，可以利用三边定位法或者极大似然估计法计算自身位置。基于TOA的定位实现简单，定位精度高，但是要求节点间保持精确的时间同步，这样对传感器网络的节点的硬件和功耗提出了较高的要求。44.1.3现有无线传感器网络定位方法基于TDOA测距定位的应用已经不再陌生，前面讲述的Cricket系统就是一个很好的应用，下面重点介绍另一个基于TDOA测距定位的应用AHLos（Ad-Hoc Localization System）系统。AHLos系统在初始阶段已经通过人工配置或者使用GPS定位技术使一小部分节点成为信标节点，它实现全网未知节点的定位是一个逐步迭代的过程。首先信

18、标节点向周围邻近节点广播自己的位置信息，未知节点通过TDOA方法测得与周围临近节点的距离和接收到的位置信息使用相应的定位算法计算自身的位置，转化成为信标节点并向周围邻近节点广播自己的位置信息，这样依次迭代直到网络中所有未知节点均计算出自己的位置。54.1.3现有无线传感器网络定位方法在具体迭代过程中，未知节点会根据周围信标节点的不同分布选择相应的多变定位算法计算自身位置。（1）原子多边算法（Atomic Multilateration）（2）迭代多边算法（Iterative Multilateration）（3）协作多边算法（Collaborative Multilateration）总体来讲

19、，AHLos算法在迭代过程中存在误差积累问题，对网络节点密度要求高，不适合大规模无线传感器网络。基于TDOA的测距技术对硬件要求高，具有测距误差小，精度高的优点。64.1.3现有无线传感器网络定位方法4AOA定位算法基于到达角度的AOA定位算法，未知节点通过天线阵列和多个超声波接收器感知信标节点的发送信号的方向，计算未知节点和信标节点之间的方位角等，再通过角度测量法计算未知节点的位置。每个节点配有两个超声波接收机为例，节点A为未知节点，节点B为信标节点，两个接收机R1和R2之间的距离为L，两个接收机的连线的中垂线为节点A的轴线，x1、x2分别为R1和R2到信标节点的距离，角为节点B相对于节点A

20、的方位角。当节点A的两个接收机收到节点B的信号后，利用TOA技术测出x1、x2，然后再根据几何关系可以推导出节点B相对于节点A的方位角。74.1.3现有无线传感器网络定位方法84.1.3现有无线传感器网络定位方法利用上面的方法，分别测得相邻3个节点的相对各自的方位角，如节点B相对节点A的方位角为ab，同样可以测得节点C相对于节点A的方位角ac，由此可得：CAB=acab。如果节点B是已知方向的节点，它的轴线相对于指南针方向角为b，则可以根据几何知识推导出节点A的轴线相对于指南针的方向角为 。由此可知，该算法还可以实现定向功能。由于基于AOA的定位算法需要额外硬件的支持，而且测距过程容易受到外界

21、环境的影响，因此不适合在大规模网络中使用。94.1.3现有无线传感器网络定位方法104.1.3现有无线传感器网络定位方法5RSSI定位方法在RSSI定位过程中，未知节点根据接收到的信号强度值计算信号的传播损耗，按照相应的传播损耗模型将传播损耗转化为距离，然后再根据三边定位法或者多边极大似然估计法计算未知节点的位置。SpotON项目，微软的RADAR系统都利用了RSSI测距技术。RADAR是一个基于RSSI测距的室内定位系统，用于确定用户所在楼层的具体位置。它一般使用信号传播经验模型和理论模型两种方法进行未知节点的定位。基于RSSI的定位受到周围环境的影响很大，定位精度不稳定，尤其是在室外，影响

22、因素会更多，该技术离实际应用还有一段距离。114.1.3现有无线传感器网络定位方法6DV-HOP定位方法DV-HOP（Distance Vector-HOP）定位机制包括3个不同的阶段，首先计算未知节点与每个信标节点的最小跳数，其次计算未知节点与信标节点之间的距离，最后计算未知节点的坐标。124.1.3现有无线传感器网络定位方法（1）第一阶段：计算未知节点与每个信标节点的最小跳数这个阶段使用经典的距离矢量交换协议，每个节点维护一个表 ，其中xi、yi、hi分别代表信标节点的坐标和到该信标节点的跳数。每个信标节点发送一个广播分组，该分组包含自身的位置信息和跳段个数，跳段个数初始化为0。节点收到信

23、标节点的广播分组后检验该分组跳段数是否小于本节点表内的存储值，如果是则更新该表，然后跳段数加1并广播该分组，否则丢弃该分组。最终所有的未知节点均能获得到所有信标节点的最小跳数。134.1.3现有无线传感器网络定位方法（2）第二阶段：计算未知节点与信标节点的距离每个信标节点根据自身表中记录的其他信标节点的坐标信息和跳数，按照式（4-12）计算平均跳段距离ci。然后把计算出来的平均跳段距离利用可控洪泛法进行广播，每个节点均接收第一个跳段距离，忽略后来到达的，这样确保了绝大多数节点可从最近的信标节点接收平均跳段距离。最后未知节点便可计算自己到达相应的信标节点的距离。其中 、 分别为信标节点i、j的坐

24、标，hi为节点i到节点j的跳段数。144.1.3现有无线传感器网络定位方法（3）第三阶段：计算未知节点的坐标 当未知节点收到3个或者更多信标节点的距离时，则可以根据三边定位或多边定位算法进行自身位置的计算。接下来举例说明具体计算过程，如图4-11所示，经过前两个阶段，现在已知信标节点L1、L2与L3之间的距离和跳数，假设L2计算得到平均跳段距离为（40+75）/（2+5）=16.42。假设节点A从节点L2获得平均跳段距离，则它与信标节点L1、L2、L3的距离为分别为316.42、216.42、316.42。DV-HOP定位算法使用平均跳段距离估算两点之间的实际距离，存在一定误差，同时在定位过程

25、中两次洪泛，能量开销大，但是该算法对硬件要求低，实现简单。154.1.3现有无线传感器网络定位方法164.1.3现有无线传感器网络定位方法7Amorphous定位方法假定传感器节点随机分布在一个二维面板上，传感器节点的物理通信半径为r，r远小于该面板的尺寸，在节点本身距离r以内的节点为通信邻居，每个节点都可以和通信邻居内的节点进行通信。同时，该算法首先假定每个节点拥有相同的通信距离，并且不使用RSS测距来确定未知节点的位置，因此Amorphous定位算法是无需测距的定位算法。174.1.3现有无线传感器网络定位方法Amorphous定位算法为以下面两个阶段：第一阶段：使用经典的距离矢量交换协议

26、计算未知节点和信标节点之间的最小跳数，该过程在DV-HOP定位算法中已经介绍，这里不再重复。第二阶段：使用节点的通信半径r作为节点间的平均每跳通信距离，从而估算未知节点和信标节点之间的距离，当未知节点得出至少到3个信标节点距离后，估算自己的坐标位置。直到该节点到信标节点的计算距离与估算距离之间的方差最小为止。Amorphous算法需要较高的节点密度，并且要求在网络部署前离线计算平均每跳距离，网络扩展性差。184.1.3现有无线传感器网络定位方法8APIT定位方法近似三角形内点测试法APIT（Approximate Point-in-triangulation Test）是一种无需测距的定位技术

27、，它包括四个步骤。1.收集信息。未知节点收集周围临近信标节点的位置、标识号、接收信号强度等信息，邻居节点之间交换并共享各自接收到的信标节点的信息。2.PIT测试。未知节点收集到的信标节点组合成不同的三角形，假设信标节点有n个，则可以组合成 个不同的三角形，测试该未知节点是否在三角形内部，直到穷尽所有三角形或者达到预定的定位精度为止。将所有的包含未知节点的三角形存储在Inside集合中。194.1.3现有无线传感器网络定位方法3.计算重叠区域。计算Inside集合中所有三角形的重叠区域，该区域为一个多边形。 4.计算未知节点的位置。计算重叠区域的质心坐标作为未知节点的坐标。204.1.3现有无线

28、传感器网络定位方法接下来重点介绍PIT测试原理，如图4-13所示，存在一个方向，当节点M沿着这个方向移动时，如果它同时远离或者接近节点A、B、C时，则节点M在三角形ABC的外部，否则节点M在三角形ABC的内部。214.1.3现有无线传感器网络定位方法但是无线传感器网络节点是静止的，如何辨别节点M是靠近还是远离某一信标节点。为了模拟节点的移动，利用节点的接收信号强度来进行测试，通常未知节点离信标节点越远，它的接收信号强度越弱，节点M通过与邻居节点交换信息并对比接收信号强度值，从而可以判断是靠近还是远离某一信标节点。为了穷尽所有可能的方向测试节点M会同时靠近或者远离了个信标节点，提出近似三角形内点

29、测试法，PIT测试的准确性与网络场景和网络节点密度有关。在网络无线信号传播模式不规则和传感器节点随机部署的情况下，APIT算法的定位精度高，性能稳定，但是APIT测试需要较高的网络连通性，通常连通度大于6。相对于质心算法而言，APIT定位算法对信标节点密度要求低，定位精度高。214.1.3现有无线传感器网络定位方法214.1.3现有无线传感器网络定位方法课程目录4.14.2无线传感器网络定位技术无线传感器网络跟踪技术无线传感器网络时间同步技术4.3无线传感器网络的发展与安全趋势课程目录4.2.14.2.2无线传感器网络跟踪技术概述无线传感器网络目标跟踪的基本过程无线传感器网络跟踪技术4.2在无

30、线传感器网络的许多实际应用中，跟踪运动目标是一项基本功能。由于传感器节点体积小、价格低廉、采用无线通信方式，以及传感器网络部署随机，具有自组织性、鲁棒性和隐藏性等特点，无线传感器网络非常适合于移动目标的定位和跟踪。传感器网络的跟踪算法必须能够尽可能利用局部信息进行目标位置和运动轨迹的计算，具备移动的鲁棒性以适应网络拓扑的动态变化，能够实时传输跟踪数据和计算结果，同时具备较低通信开销。14.2.1无线传感器网络跟踪技术概述在无线传感器网络跟踪过程中，首先需要节点进行监测，如果监测到目标出现，需要在一定时间内选择适合的算法判断出目标的运动轨迹，并对目标进行一些状态探测，这就要求传感器节点不仅具有一

31、定的数据处理能力，而且能够根据不同的任务和有限的资源选择适合的算法计算目标的状态。按照跟踪对象数量的不同，传感器网络的目标跟踪可以分为单目标跟踪和多目标跟踪；按照目标形状的不同，可以分为点目标跟踪和面目标跟踪；按照传感器节点运动方式的不同，可以分为静态目标的侦测和移动目标的跟踪。24.2.1无线传感器网络跟踪技术概述课程目录4.14.2无线传感器网络定位技术无线传感器网络跟踪技术无线传感器网络时间同步技术4.3无线传感器网络的发展与安全趋势课程目录4.2.14.2.2无线传感器网络跟踪技术概述无线传感器网络目标跟踪的基本过程无线传感器网络跟踪技术4.2跟踪与定位不同，主要目的不是追求定位的精度

32、，而是需要对移动的目标或者时间进行动态的监测。基于无线传感器网络的目标跟踪过程大致包括3个阶段：检测、定位和通告，每个阶段需要不同的技术来实现。14.2.2无线传感器网络目标跟踪的基本过程在检测阶段，主要任务是通过各种检测手段检测跟踪目标是否出现，常用的技术有超声波检测、震动技术检测、红外线技术检测以及多媒体基础检测等；定位阶段，定位是跟踪的技术基础，在前面部分叙述了多种无线传感器网络定位技术，可以根据不同的场景和用户需求来选择适合的定位技术来确定当前目标的位置和状态，比较常用的方法有双元检测、三角测量以及基于流行学习算法等，然后记录当前目标的轨迹和状态，用于以后目标跟踪查看或者预测；通告阶段

33、，是节点之间交互信息的过程，在这个过程中节点向周围其他节点发出协作定位求助或者通告其他节点自己对目标的监测状态。24.2.2无线传感器网络目标跟踪的基本过程1检测阶段无线传感器网络中的节点周期性地通过传感器模块检测是否有目标出现。节点通过一些技术测试目标的真实性，如果确实目标到达了本节点的监测区域，则节点首先计算自己到目标的距离，然后向整个网络广播目标侦测消息。邻居节点收到该目标侦测消息后保存到本地信息表中并加上时间戳。节点动态维护本地信息表，如果表中的信息表项在预定的时间内得不到更新将会被删除。34.2.2无线传感器网络目标跟踪的基本过程2定位阶段为了节省能量，只有距离跟踪目标比较近的节点才

34、会对目标进行定位，如果节点收到另外两个或者两个以上的节点到跟踪目标的距离，则可选用三边定位法或者多边极大似然估计法计算跟踪目标的位置。确定跟踪目标的位置后，还要进一步预测其运动趋势，以便通知目标将要达到区域的网络节点。44.2.2无线传感器网络目标跟踪的基本过程3通告阶段计算出跟踪目标的运动轨迹后，传感器网络要通知跟踪目标周围的节点启动进入跟踪状态。所有利用3个位置估算出的跟踪目标的轨迹节点均广播一个通告消息，该消息包含了本节点的位置信息和跟踪目标的轨迹。收到消息的节点计算本身到跟踪目标预测轨迹的距离，如果该距离小于预定的阈值d，则节点启动进入跟踪状态，同时转发该通告消息。否则节点保持原状态并

35、丢弃该消息。54.2.2无线传感器网络目标跟踪的基本过程课程目录4.14.2无线传感器网络定位技术无线传感器网络跟踪技术无线传感器网络时间同步技术4.3无线传感器网络的发展与安全趋势课程目录4.3.14.3.2时间同步模型时间同步协议无线传感器网络时间同步技术4.31时钟模型2通信模型3时钟同步的误差来源14.3.1时间同步模型1时钟模型传感器网络中节点的本地时钟依靠对自身晶振中断计数实现。晶振的频率误差和初始计时时刻不同，使得节点之间本地时钟不同步。如果能估算出本地时钟与物理时钟的关系或本地时钟之间的关系，就可以构造对应的逻辑时钟以达成同步。目前的逻辑时钟同步算法，如下文提到的有些同步算法同

36、步精度已达到1s，可以满足传感器网络中绝大部分应用的需求。如果要达到纳秒级精度，则要采用锁相环等硬件实现物理时钟同步。24.3.1时间同步模型（1）节点本地时钟模型在计算机系统中，时钟通常用晶体振荡器脉冲来度量:在工程实践中，因为温度、压力、电源电压等外界环境的变化，往往会导致晶振频率产生波动。因此，构造理想时钟比较困难。在一般情况下，晶振频率的波动幅度并是非任意的，而是局限在一定的范围之内，为了方便描述和分析，定义如下3种时钟模型:34.3.1时间同步模型 速率恒定模型。速率恒定模型假定时钟速率是恒定的，即晶振频率没有波动发生。当要求的时钟精度远低于频率波动导致的偏差时，该模型的假定应该是合

37、理的。 漂移有界模型。定义时钟速率 相对于理想速率1的偏差为时钟漂移(drift) ，即 。漂移有界模型在工程实践中非常有用，常用来确定时钟的精度或误差的上下界。 漂移变化有界模型。该模型假定时钟漂移的变化 是有界的时钟漂移的变化主要是温度和电源电压等因素发生变化所引起的，一般变化速率相对缓慢，可以通过适当的补偿算法加以修正。44.3.1时间同步模型（2）节点逻辑时钟模型任一节点i在物理时刻t的逻辑时钟读数可以表示为其中， 为当前本地时钟读数， 为频率修正系数， 为初相位修正系数。采用逻辑时钟的目的是对本地时钟进行一定的换算以达成同步。为了同步任意两个节点i和j，构造逻辑时钟有两种途径：一是根

38、据本地时钟与物理时钟等全局事件基准的关系进行变换,另一种是根据两个节点本地时钟的关系进行对应换算。两种方法都估计了频率修正系数和初相位修正系数，精度较高。对于低精度类应用，还可以简单地根据本地时钟和物理时钟的差值以及本地时钟两两之间的差值进行修正。54.3.1时间同步模型2通信模型节点时间校正技术是无线传感器网络时间同步的核心和基础。目前主要的时间校正技术有单向报文传递、双向报文交换、广播参考报文和参数拟合技术。64.3.1时间同步模型（1）单向报文传递节点i在本地时间 时刻向节点j发送一个报文，包含时间戳 。假设节点j在本地时间 时刻收到上述报文。节点j不知道报文的传递时延d，所以只能对d进

39、行估计，如果知道d的上界和下界，则可以得到进而估计节点i和节点j之间的时间偏差公式为这种时间校正技术的精度最低，因为它假设报文传递过程中只有传播延时，忽略了无线信道的许多不确定因素的影响。74.3.1时间同步模型（2）双向报文交换双向报文交换的时间校正技术要复杂很多。节点i在本地时钟 时刻向节点j发送同步报文，节点j在本地时钟时刻 接收到该报文，之后立即向节点i发送应答报文，节点i在本地时钟时刻 接收到该应答报文。则报文的往返时间为D，大小为 ，报文的传递时延d在0D之间。如果知道d的上界和下界，节点j可以确定d在 和 之间。由此可以确定节点i、j之间的时间偏差为 假设上行报文和下行报文的时间

40、延迟相等，即 双向报文交换是应用很广泛的一种时间校正技术，精度比较高。但是网络负载比较大，耗能较高，而且需要周期性地执行同步过程。84.3.1时间同步模型（3）广播参考报文它是利用第三个节点k作为参考节点，发送时间同步的参考广播报文给相邻的节点i和节点j。假设这个参考广播报文到达节点i和节点j的时间延迟相等 。节点j收到参考广播报文后，立即发送包含有 信息的报文给节点i，于是节点i就可以计算收到两条报文的时间间隔D为广播参考报文的方法只能使节点间的时钟保持相对同步。94.3.1时间同步模型（4）参数拟合技术参数拟合技术可以同时计算出节点时钟之间的频率偏移和相位偏移。假设两时钟的时间之间满足式其

41、中，和分别是两个时钟时间之间的相对频率偏移和相位偏移。采用上述3种方法测量节点间时间偏差，在测量得到多组数据样本后，就可以利用参数拟合技术计算时间的频偏和相偏。参数拟合技术有线性回归、锁相环两种实现方法。104.3.1时间同步模型3时钟同步的误差来源正确地估算本地时钟与物理时钟或本地时钟之间的频率偏差和相位偏差，是构造逻辑时钟的关键。节点通过交互同步信令估算相应的参数，然而同步信令在网络上传输会产生不确定的时延，该时延的不确定性是影响同步精度的关键因素。正确估计同步信息的时延对提高同步精度意义重大，同步信息的时延包括以下几部分：协议发送时延、接入时延、发送时延、传播时延、接收时延、接收处理时延

42、114.3.1时间同步模型124.3.1时间同步模型课程目录4.14.2无线传感器网络定位技术无线传感器网络跟踪技术无线传感器网络时间同步技术4.3无线传感器网络的发展与安全趋势课程目录4.3.14.3.2时间同步模型时间同步协议无线传感器网络时间同步技术4.31时间同步的类别时间同步一般理解为使许多节点的时钟显示相同的时间，实际上有很多种不同类型的同步。下面对各种同步方法进行整体的介绍。在为给定的应用选择同步算法时，要在最大程度满足应用的同时尽可能将计算、存储，尤其是能量开销降到最低。14.3.2时间同步协议（1）时钟速率同步与偏移同步速率同步是指各个传感器节点测量所得的时间间隔相等，如公式

43、（4-35）所示： 在目标跟踪、定位等应用中，节点时钟速率同步是最低的同步要求。偏移同步是指传感器节点在当前时刻t的时钟时间显示相等，即在时刻t传感器节点的时钟读出时间同为T，而不管时钟速率是否同步，如式（4-36）所示： 偏移同步对传感器网络中不同节点间的时戳结合是必须的。24.3.2时间同步协议（2）同步期限：长期同步与按需同步时间同步的同步期限是指同步要保持的时间长短。在长期同步的情况下，维持同步的代价是很大的，随着时间的推移，节点间误差逐渐增加，可能还需要周期性地再同步。按需同步是指传感器节点的时间在相关事件发生前后进行同步，它不需要大量的维护同步的通信开销，节省了通信带宽和节点能量。

44、对一些传感器网络的应用，按需同步效率更高。34.3.2时间同步协议（3）同步范围：全网同步与局部同步同步范围是定义网络中哪些节点式需要同步的。在有些情况下，范围可能纯粹是地理上的距离。而在其他情况下，逻辑距离更有用，如网络中的跳数。根据不同的应用，范围可能是网络中所有节点或者部分节点。44.3.2时间同步协议（4）内同步和外同步时间同步简单的意思就是得到正确的时间，一般这个正确时间就是UTC。然而，一些应用只需要记录事件发生的先后顺序以及时间间隔，并不需要事件发生的绝对时间。这种情况下，只需要内同步（相对同步），网络必须内部一致，不需要它们与外界标准时间保持一致性。另一类应用要求外同步（绝对同

45、步），即每个节点都要与外部时间标度（如UTC）保持同步。通常的环境监控或者需要数据存档的应用中，比较需要外同步，而且要求的同步期限比较长。54.3.2时间同步协议（5）发送者接收者同步与接收者接收者同步在进行发送者接收者同步时，发送者在报文中嵌入报文发送时间，而接收者在接收到报文后记录下接收时间，并利用这些时间信息计算出收发双方的时钟偏移，进而达到收发双方的时间同步。接收者接收者同步时，发送者发送一个同步报文到多个接收者，这些接收者通过对同一个报文时间的比较，计算出它们之间的时钟偏移，从而达到接收者一接收者同步。64.3.2时间同步协议2典型的时间同步协议（1）LTS协议（2）RBS协议（3）

46、TPSN协议（4）DMTS协议（5）FTSP协议（6）几种协议的比较74.3.2时间同步协议（1）LTS协议LTS（Lightweight Tree-based Synchronization）同步算法的设计目标就是适用于低成本、低复杂度的传感器节点时间同步，侧重最小化同步的能量开销，同时具有鲁棒性和自配置的特点。Anceaume和Puaut把时间同步模块划分为3个组成部件：重同步监测、远程时钟估计和时钟修正。重同步时间监测用来确定节点进行时间同步的时刻。两种方式确定重同步时刻：一种是基于初始同步的时间，以kR固定周期进行重同步，R是单个时间同步周期的长度，k是大于1的实数，用来防止两个同步周

47、期的重叠；另一种是一个特定节点在kR时间后发送初始同步消息给其他节点，节点在收到消息后启动时间同步。远程时钟估计部件用来决定网络中另一个节点的本地时钟。84.3.2时间同步协议（2）RBS协议2002年12月，Jeremy Elson等提出参考广播同步机制（Reference Broadcast Synchronization，RBS），该机制利用了无线数据链路层的广播信道特性，一个节点发送广播消息，接收到广播消息的一组节点通过比较各自接收到广播消息的同步时刻，来实现它们之间的时间同步。RBS算法通过接收节点对时抵消发送时间和访问时间，发送节点广播一个信标分组，广播域中两个节点都能接收到这个分组，交换接收时间，两个接收时间的差值相当于两个接收节点间的时间差值，其中一个节点可以根据这个时间差值更改它的本地时间，从而实现两个节点的时间同步。94.3.2时间同步协议104.3.2时间同步协议（3）TPSN协议2003年11月，Saurabh Ganer