低能耗无线传感器网络时间同步方法

摘要

本发明公开一种低能耗无线传感器网络时间同步方法，包括网络预同步、主动节点选择、再选择三个过程，所述网络预同步过程要完成节点分级、时间同步和统计下级节点度；所述主动节点选择是利用下级节点度选取网络中的特定节点，将网络中的节点分为主动节点和被动节点；所述再选择过程是在时间同步过程中出现主动节点失效或所有的主动节点的能量不能再满足广播时间同步消息或根节点失效时，重新选出主动节点。采用本发明的时间同步方法，可以有效的减少网络中发送时间消息的节点的数量，降低了同步过程中的网络通信量，时间同步中的冗余消息大大减少，网络冲突也随之降低，延长了传感器网络的工作周期；具有较高的稳定性。

说明书

技术领域

本发明属于无线传感器网络技术领域，涉及无线传感器网络时间同步消息的传输方法，具体是一种低能耗无线传感器网络时间同步方法。

背景技术

无线传感器网络就是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感知和采集网络覆盖区域中某些特定的物理量，并对所采集的信息进行处理，然后发送给观测者。

对于大多数无线传感器网络的应用来说，统一的时间扮演着一个至关重要的角色。依赖于时间同步的应用和协议存在于无线传感器网络的方方面面。时间同步协议的实现既依赖于无线传感器网络的传输特点，同时又支持了无线传感器网络的通信和上层应用，是无线传感器网络中至关重要的一部分。

传感器网络的时间同步可以采用两种方法，一.给每个节点配备GPS模块，以获得精确的时间，使节点时间和标准时间一致，达到同步；二.利用网络通信方式，交换时间信息，使得全网保持统一的时间，达到同步。由于GPS设备的成本高、能耗大，不能为每个节点都配备GPS模块，因此只有少量的节点能够配备GPS模块，其它的节点则采用交换时间同步消息的办法来达到全网时间同步。

节点间利用网络通信交换时间同步消息的方法有很多种，其中洪泛广播时间同步协议是比较简单的一种方法。这个方法的原理是：网络中的每个已同步节点将其本地时间打包，然后采用广播的方式发送出去。对消息传递中各个阶段的时间延迟进行细致的分析并建立分布模型，接收到消息的节点按照所建立的分布模型对时间延迟造成的影响进行消除，采用线性回归的方法估计节点相对于全局时间的时间偏移和时间漂移，利用估计值校正本地时间。

该方法假设传感器网络中的每个节点具有唯一的身份标识号，也就是ID号。整个网络中有一个根节点，根节点是ID号最小的节点，也是选中的同步源。洪泛广播时间同步协议采用层次结构，根节点属于0级，根节点广播域内的节点属于1级节点，以此类推，级别i的节点同步到级别为i-1的节点。所有节点周期性的广播时间消息，当i级节点收到i-1级节点的时间消息，达到同步后，生成新的时间消息，然后广播出去。依次，时间同步从级别高的节点扩散的级别低的节点，最后达到全网的时间同步。

图1示出了洪泛广播时间同步的时间消息包的结构。包括前导码Preamble、同步字节SYNC、数据段Data和CRC校验码四部分，其中的数据段又包括时间信标timeStamp、根节点标识号rootID和序列号seqNum三个部分。图1中，洪泛广播时间同步协议利用时间同步消息包中的根节点标识号rootID进行根节点选择，可以确保在根节点失效的情况下重新选出根节点；接收到时间同步消息的节点使用消息包中的序列号seqNum判断接收到的时间同步消息是否是最新的。

洪泛广播时间同步协议中，所有的已同步节点都会广播时间同步消息。无线传感器网络的一个特点是节点密度大，应此，一个节点就会收到周围很多节点广播的时间消息，这些消息中只有一个会被用到，而其它的消息则是冗余消息，这些冗余消息不但会浪费节点的能量，而且还会造成网络通信碰撞，降低网络通信质量。

发明内容

本发明的目的在于避免现有技术的不足，而提出一种低能耗无线传感器网络时间同步方法，可以有效地降低时间同步中冗余消息的发送量，达到减小时间同步能耗的目的。

为实现上述目的，本发明提出了下级节点度的概念，并提供了统计各个节点的下级节点度的方法。利用下级节点度选取网络中的部分节点发送时间同步消息，其它的节点只是被动的接收消息，并不发送时间同步消息。

本发明的具体方法包括网络预同步、主动节点选择、再选择三个过程，所述网络预同步过程要完成节点分级、时间同步和统计下级节点度；所述主动节点选择是利用下级节点度选取网络中的特定节点，将网络中的节点分为主动节点和被动节点；所述再选择过程是在时间同步过程中出现主动节点失效或所有的主动节点的能量不能再满足广播时间同步消息或根节点失效时，重新选出主动节点。

根据本发明的方法，所述节点分级是在时间同步过程中，将传感器节点分为不同的级别并记录节点的级别号；在此基础上统计下级节点度：令一个节点的下级节点度的初始值为0，在一个同步周期中，处于第i级的节点收到第i+1级某个节点发送的时间同步消息，就将其下级节点度加1。

根据本发明的方法，所述主动节点选择遵循如下两个规则：

(1)下级节点度为0的节点不发送时间同步消息，则此节点为被动节点；

(2)如果节点的下级节点度小于接收到的其它同级节点的下级节点度，节点不发送时间同步消息，则此节点为被动节点。

根据本发明的方法，主动节点的再选择过程按如下三种方式处理：

(1)某个主动节点失效，经同级的被动节点确认后，由被动节点发送时间同步消息包，经过几个同步周期，重新选出主动节点；

(2)所有的主动节点的能量不能再满足广播时间同步消息，由根节点进行确认，并发起全网的再选择；

(3)根节点失效，由新的根节点发起再选择，需要重新进行网络预同步和主动节点选择。

本发明所采用的传递时间同步消息的消息包，其数据段Data中增加级别号levelNum和下级节点度NLND，其中级别号用于传递节点的等级信息，此levelNum是必须的，NLND为可选的。

相对于传统的洪泛广播时间同步协议，本发明主要有下面几个优点：

(1)本发明利用下级节点度选取主动节点和被动节点。在时间同步过程中，由于只有主动节点发送时间同步消息，被动节点只需要接收时间同步消息包。相比于传统洪泛广播时间同步协议中每个节点都要发送时间同步消息，本发明可以有效的减少网络中发送时间消息的节点的数量，降低了同步过程中的网络通信量，时间同步中的冗余消息大大减少，网络冲突也随之降低，延长了传感器网络的工作周期；

(2)本发明的网络预同步过程中，节点分级和统计下级节点度是伴随时间同步进行的。主动节点再选择过程确保在主动节点失效或不能承担时间同步消息发送的情况下，重新选出主动节点。这样可以大大提高低能耗无线传感器网络时间同步方法运行的稳定性。

附图说明

附图1是洪泛广播时间同步消息包的结构示意图

附图2是本发明低能耗无线传感器网络时间同步消息包的结构示意图

附图3是本发明一级节点在主动节点选择前后的状态示意图

具体实施方式

图2显示的是低能耗时间同步方法的时间同步消息包的结构，包括前导码Preamble、同步字节SYNC、数据段Data和CRC校验码四部分，其中的数据段又包括时间信标timeStamp、根节点标识号rootID、序列号seqNum、节点级别号levelNum和节点下级节点度NLND五个部分。比图1所示的洪泛广播时间同步数据包多出两个数据，其中levelNum携带的是节点的等级信息，这个数据是必须的，伴随时间同步始终。NLND携带的数据是节点的下级节点度，这个数据是可选的，只有在时间同步处于主动节点选择过程或再选择过程时，时间同步消息包中才会携带这个数据。

低能耗无线传感器网络时间同步方法分为三部分：网络预同步过程、主动节点选择过程、再选择过程。

(一)网络预同步过程

这个过程中时间同步主要完成了3个任务：节点分级、时间同步和统计下级节点度。传感器网络进行时间同步的同时也伴随着分级和统计下级节点度这两个过程。

假设，在整个传感器网络生命周期内，节点的通信距离是固定不变的，每个节点的发射半径相同。分级和统计下级节点度是和时间同步同时进行的，不会对时间同步的收敛性有任何影响。当根节点确定后，开始分级过程，规定根节点为0级节点，同步由根节点开始。根节点广播时间同步消息包，这个消息包中包含根节点的级别号(levelNum＝0)和时间信标等重要数据。根节点周围的节点接收到这个消息包后，估算时间偏移，根据时间偏移调整本地时间，然后将消息包中提取的级别号加1，作为自己的级别号。这样在根节点周围，能够直接接收到根节点发送的时间消息包的节点，其级别号为1。这些节点与根节点同步后，且经过T＝0.5T+T_rand后，产生新的时间信标，与级别号一同打包广播出去。T_rand值为(0，0.5T)之间的一个均匀分布的随机数，T的取值根据节点的传输速率决定，目的是为了减少网络碰撞。对于后续节点继续同步和分级，其过程是，当某个节点收到所处级别为i的一个节点发送的时间消息包后，若这个节点还没有设置级别号或级别号大于i+1，那么将这个节点的级别号设置为i+1；否则保持原有的级别号不变。随着时间同步，分级也从根节点扩散到整个网络。

经过几个时间同步周期后，网络中的每个节点都具有了一个级别号。网络中节点的级别号确定以后，如果根节点没有变化，就不会再进行传感器网络的分级过程。根节点重新选择后，节点的等级也要重新划分。

时间同步进行一段时间后，网络的节点的时间趋于同步，节点的级别已经确定，就开始统计下级节点度NLND，这个过程是随时间同步一起进行的，某个节点的下级节点度的定义为：与该节点有直接联系的下级节点的个数。

下级节点度的统计方法是：令网络中节点的下级节点度的初始值为0，在一个同步周期中，如果处于第i级的节点收到第i+1级某个节点发送的时间同步消息，那么就将其下级节点度加1(NLND＝NLND+1)，这样，在一个时间同步周期后，网络中的每个节点都可以统计出自己广播覆盖范围内下级节点的数量，也就是下级节点度。

(二)主动节点选择过程

本发明利用图2所示消息包中的节点级别号levelNum和节点的下级节点度NLND两个数据进行主动节点选择。这个过程的目的是选取网络中的某些节点发送时间同步消息包，而其它节点只是被动接收消息，不主动发送消息。为此，有下面定义：

主动节点——传感器网络中，一个节点与全局时间达到同步后，能够产生时间同步消息包并广播出去，这样的节点称为主动节点；

被动节点——传感器网络中，一个节点只能接收时间同步消息，而不能广播时间同步消息包，这样的节点称为被动节点。

在全网达到时间同步，每个节点都获得自己的下级节点度后，在下一个时间同步周期，进行节点选择。节点选择的方法是利用下级节点度进行判断：当下级节点度为0时，表示该节点没有下级节点，这样的节点向外广播时间同步消息包，也不会有节点利用这个时间同步消息包，因此，该节点只需要被动接收时间同步消息包，不需要主动发送消息，这样的节点就被设置为被动节点；当节点达到同步且下级节点度不为0时，节点将时间信标、节点级别号和下级节点度一起打包发送。其它同级节点接收到这个时间同步消息包后，将自己的下级节点度与消息包中的下级节点度进行比较，如果节点的下级节点度小于消息包中的下级节点度，那么该节点就被设置成为被动节点，停止发送时间同步消息包。这样，经过几个时间同步周期后，在一定范围内，只有下级节点度最大的节点才能够发送同步消息，这些节点就是主动节点。

图3所示的是一级节点在主动节点选择前后的状态，其中同心圆表示的是节点所处的层级，黑色的点表示根节点。左图表示的是预同步过程中节点的通信状态，这个过程中，每个节点都需要发送时间同步消息，并且统计下级节点度。图中深色点旁边的数字代表该节点所统计的下级节点度；右图表示的是第一级节点经过节点选择后的状态，其中深色点表示选出的第一级中的主动节点，空心点表示被动节点。而第二级还没有进行主动节点选择，其所有的节点依然发送时间同步消息。

在图2中，虽然低能耗时间同步方法的消息包多出两个数据，但是，经过主动节点选择后，发送时间同步消息包的节点数量减少，从总体考虑，全网通信量也减少了。这样可以有效的降低时间同步的通信量、通信冲突和网络开销，节省了能量。

(三)再选择过程

在传感器网络的运行中，会出现下面三种情况而影响网络的时间同步：第一、在网络的运行过程中某个主动节点失效，将会影响到传感器网络某一部分的时间同步；第二、主动节点的能量耗费相对较大，在运行一段时间后，主动节点将不能再维持时间同步消息包的传输，这种情况会影响到整个网络的时间同步。第三、根节点失效，这种情况也会影响到整个网络的时间同步。

对于第一种情况，可以在网络的局部重新进行主动节点的选择，选择过程由失效节点的同级节点发起。当同级的某个被动节点接收不到任何与自己相同级别的节点广播的时间消息时，该被动节点就认为某个主动节点已经失效，这时被动节点变为主动节点，发送时间同步消息包，经过几个同步周期，重新选出主动节点。

对于第二种情况，主动节点再选择由根节点发起，这个过程和上述“主动节点选择过程”的方法相同，其不同之处在于，以前已选出的主动节点将不再作为主动节点。

对于第三种情况，主动节点再选择同样由根节点发起，但这个过程需要重新进行“网络预同步”和“主动节点选择”过程。