基于TSMS的同步协议优化方法

摘要

本发明提供了一种基于TSMS的同步协议优化方法，包括：每个节点都与根节点进行直接同步，根节点与普通节点进行5次数据交换，获取5组时间数据，通过该5种时间数据建立一个5*5的矩阵方程，并分别针对接收时间与发送时间进行2次求解，得到的线性解系构成的方程即是两点之间的时间关系。解出两个不等式之后，每个变量的值取区间中点，即可得到一个特殊解。这个解包括5个变量，这5个变量组成了根节点和普通节点的时间关系。通过这个时间关系，本发明可以很方便的调节普通节点的时间以达到与根节点同步的功能。

说明书

技术领域

本发明涉及无线传感网络同步算法(TS/MS)，具体地，涉及基于TSMS的同步 协议优化方法。

背景技术

传感器网络各个节点之间的时间同步是近年来传感器网络范畴内的重要内容。为了 在网络中完成时间精确度更高的协同操作，传感器网络内各个节点必须拥有统一的时间 信息。但是，在正常的工作环境中，不同节点的工作状态、工作内容、环境变量、方位 信息等参数不同，常常导致时间信息不同；进一步来说，预先设置好统一的时间信息后， 由于不同节点长时间工作在不同状态，时间信息也会出现很大程度的偏移。这样的时间 误差是无法忍受的。因此，如何在一个无线传感网络下保证时间信息的统一是大型传感 器网络领域的首要解决问题。然而，目前国际上提出的时间同步算法多为针对多终端有 线网络模式设计，此类方法虽然精度高，但功耗非常大，在无线传感网络中，由于电能 是稀缺资源，该类算法的功耗无法适应无线传感网络的实际应用场合，综上所述，无线 传感网络领域亟需一种既能节省功耗，又能达到一定精度的时间同步算法。

目前无线传感网络领域的时间同步算法多是基于有线网络时间同步算法 (TSS，RBS，TPSN，FTSP等)改进而来。如LTS，Tsync，ETSP等，都是简化有线网络同步时间 算法，通过降低网络中传递数据包的帧长度和数量降低该算法的精度达到降低功耗的目 的。Sichitiu和Veeraritthphan提出了一种TS/MS(Tiny Sync/Mini Sync)的同步方 法，此方法建立在任意两点的时间信息互为线性函数这个前提下。假设

t_A＝a_ABt_B+b_AB   (1)

则只需计算出a_AB和b_AB就可得知A点时间t_A与B点时间t_B之间的关系，而实际应用 中，由于数据包发送之间会有未知延迟，所以在A、B节点进行一次数据包往返发送时 (A点发送数据后，B点接收数据后，立即发送数据给A点)，A点记录下发送时间t₀以及 接收时间t_r，B点接收到A点的消息后立刻记下当前B点的时间t_b并回发给A点。因此， 当本次数据交互完成之后，A点己知了3个时间信息t₀，t_r和t_b。又由于公式(1)，可以 将t_b化为t_a的线性函数，因此可以得到两个不等式：

t₀＜a_ABt_a+b_AB

t_r＞a_ABt_a+b_AB

这样的一组时间信息称为<t₀，t_b，t_r>发送两次数据，可得到两组时间信息 <t₀₁，t_b1，t_r1><t₀₂，t_b2，t_r2>。

该两组不等式组的结果可由图1两条黑线之间的范围表示。

通过上图的线性范围，可确定一条直线来确定两点的时间关系(往往选取角平分线 或两次收发的时间中点连线)，该直线的斜率为a_AB，截距为b_AB。通过本式来修改B点 的时间，达到时间同步的目的。根节点同步好其一跳节点后，一跳节点再与子节点以相 同的方法同步，直到网络中所有节点全部同步完成。该同步方式的优点是功耗非常小、 算法简单，但其精度不高，一跳节点下的测试结果时间误差为±945μs，5跳下结果为 ±3.232ms，并且，该算法仅适用于分级网络，因此该协议的应用具有很大的局限性。

发明内容

针对现有技术中的缺陷，本发明针对网络中存在多个节点(节点总数n>4)的 情况，提出了一种优化同步时间且不需要对网络节点进行分级的同步协议，该协议 稍微增加了同步的功耗，通过数值分析的方法求解矩阵的线性解系，以此获得节点 之间的时间关系，进而同步整个网络。

根据本发明提供的一种基于TSMS的同步协议优化方法，包括如下步骤：

步骤1：同步节点n₀先发送广播，通知其他节点开始时间同步，一切准备就绪后， 同步节点n₀将自己的信息发送给节点n_k并记录下当前时间t₀；

节点n_k接收到同步节点n₀的信息后，能够获得总跳数m的具体值，然后节点n_k记 录下接收到同步节点n₀的信息的时间t_r，并将时间信息t_r和总跳数m作为回发消息回发 给同步节点n₀；

步骤2：同步节点n₀接收节点n_k发出的回发消息，并记录下接收到回发消息的时间 t₂；

步骤3：以上步骤1和步骤2的收发过程，再重复N-1次，得到N组数据；根据该 N组数据列出矩阵并根据矩阵调整节点n_k的时间值以达到时间同步；

同步节点n₀与其他节点仍通过步骤1至步骤3中的方式进行同步，直到全网节点都 完成同步。

优选地，所述步骤2包括如下步骤：

n₀接收到回发消息，并记录下接收到消息的时间t₂，通过本次数据交互，无论节 点经过具体哪一条链路，均能够在最后收到数据包后知道途径的节点，通过下式求 解节点n₀与节点n_k的时间关系常数a_0k、b_0k：

t₂＞a_0kt₁+b_0k+t_mr+t_ms...+t_nr+t_ns+t_kr+t_0s

t₀＜a_0kt₁+b_0k+t_mr+t_ms...+t_nr+t_ns+t_kr+t_0s

其中，t_mr、t_ms分别是数据转发过程中经过节点m后的接收时间与转发时间， t_nr、t_ns分别是数据转发过程中经过节点n的接收时间、转发时间；t₁为节点n_k收到 消息的时间，t_kr为节点n_k收到消息的接收时间，t_0s为节点n₀的发送时间；

由于在一次转发过程中，除同步节点n₀外，其他节点均处于同步状态，因此其 他节点的接收时间、转发时间的差距仅在于路由表遍历时某几条语句的执行时间， 可忽略不计，因此认为：

t_mr＝t_nr，n，m∈{1，2，3...}

t_ms＝t_ns，n，m∈{1，2，3...}

故得：

t₂＞a_0kt₁+b_0k+(m+1)t_kr+mt_ks+t_0s

t₀＜a_0kt₁+b_0k+(m+1)t_kr+mt_ks+t_0s

其中，t_ks为节点n_k的发送时间。

优选地，所述步骤3包括如下步骤：

以上步骤1和步骤2的收发过程，再重复4次，得到5组数据；根据该5组数 据列出矩阵：

$\left(\begin{array}{ccccc}{t}_{11}& 1& m_1+1& m_1& 1\\ t_{12}& 1& m_2+1& m_2& 1\\ t_{13}& 1& m_3+1& m_3& 1\\ t_{14}& 1& m_4+1& m_4& 1\\ t_{15}& 1& m_5+1& m_5& 1\end{array}\right)\left(\begin{array}{c}{a}_{0k}\\ b_{0k}\\ t_{\mathrm{kr}}\\ t_{\mathrm{ks}}\\ t_{0s}\end{array}\right)<\left(\begin{array}{c}{t}_{21}\\ t_{22}\\ t_{23}\\ t_{24}\\ t_{25}\end{array}\right)$

$\left(\begin{array}{ccccc}{t}_{11}& 1& m_1+1& m_1& 1\\ t_{12}& 1& m_2+1& m_2& 1\\ t_{13}& 1& m_3+1& m_3& 1\\ t_{14}& 1& m_4+1& m_4& 1\\ t_{15}& 1& m_5+1& m_5& 1\end{array}\right)\left(\begin{array}{c}{a}_{0k}\\ b_{0k}\\ t_{\mathrm{kr}}\\ t_{\mathrm{ks}}\\ t_{0s}\end{array}\right)>\left(\begin{array}{c}{t}_{01}\\ t_{02}\\ t_{03}\\ t_{04}\\ t_{05}\end{array}\right)$

其中，t_1i，i＝1，2，3，4，5，表示第i次收发过程中n_k收到信息的时间，m_i，i＝1，2，3，4，5， 表示第i次收发过程中经过的节点跳数，t_2i，i＝1，2，3，4，5，表示第i次收发过程 中n₀收到回传信息的时间，t_0i，i＝1，2，3，4，5，表示第i次收发过程中n₀开始传送信 息的时间；

由于矩阵的第二列和第五列都是1，能够得到该矩阵的秩小于5，因此两组矩 阵必有解；利用简单的QR分解，节点n₀能够通过固定算法算出两个矩阵的解，由两 组解能够知道a_0k、b_0k、t_kr、t_ks、t_0s5个变量的变化区间，取其中值即能够得到该 参数的估计值；

节点n₀再发送一次数据给节点n_k，数据中包含a_0k、b_0k、t_kr、t_ks、t_0s这5个变 量的估计值，节点n_k收到数据后，列出以下等式：

t_k＝a_0kt₀+b_0k

根据该等式，调整节点n_k的时间值以达到时间同步。

与现有技术相比，本发明具有如下的有益效果：

本发明适用于分级网络，不再要求同步节点与被同步节点必须在一跳范围内， 使被同步节点均与根节点同步，增加了同步精度。

附图说明

通过阅读参照以下附图对非限制性实施例所作的详细描述，本发明的其它特征、 目的和优点将会变得更明显：

图1为TS/MS时间同步协议的不等式结果图示；

图2为同步节点发送数据给某节点n_k时的一种可能链路；

图3为数据包随着时间在不同节点处转发直到目标节点n_k。

具体实施方式

下面结合具体实施例对本发明进行详细说明。以下实施例将有助于本领域的技术人 员进一步理解本发明，但不以任何形式限制本发明。应当指出的是，对本领域的普通技 术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进。这些都属于 本发明的保护范围。

TS/MS的主要局限在于该协议仅适用于分级网络，而且该算法同步精度较低， 优势在于具有极小的功耗。因此，本发明提出一种TS/MS方法的改进算法，该方法 可以适用于非分级网络，并且能极大提高同步精度，仅在TS/MS协议的基础上略微 增加了根节点需要收发的数据包及计算量。本同步算法中每个节点都与根节点进行 直接同步，根节点与普通节点进行5次数据交换，获取5组时间数据，通过该5组 时间数据建立一个5*5的矩阵方程，并分别针对接收时间与发送时间进行2次求解， 得到的线性解系构成的方程即是两点之间的时间关系。由于该矩阵的系数均大于0， 且要求解的2个增广矩阵系数也都大于0，通过简单的矩阵等价变换，我们可知该 矩阵的秩小于阶数，故必有解。解出两个不等式之后，每个变量的值取区间中点， 即可得到一个特殊解。这个解包括5个变量，这5个变量组成了根节点和普通节点 的时间关系。通过这个时间关系，我们可以很方便的调节普通节点的时间以达到与 根节点同步的功能。

本发明的具体实施方案如下：

在一个多节点无线传感网络中，至少有一个时间同步节点，该节点拥有准确的 时间轴，并为其他节点提供时间信息，我们称之为同步节点n₀。该同步节点n₀不需 要是根节点，但必须能够与所有节点进行多跳通信。

首先，当需要进行同步时，该同步节点n₀先发送广播，通知节点开始时间同步， 唤醒某些节点、暂停某些节点的数据交换。

第二，网络中的节点准备好进行时间同步后，向n₀发送一个消息，表示可以开 始同步。当n₀确认收到所有节点的准备完成消息之后，开始进行时间同步。

第三，n₀将自己的信息发送给某节点k(下面用n_k表示)并记录下当前时间t₀， n₀发送消息给n_k时，每转发一次，转发节点将数据帧内记录转发次数的变量加1。

第四，n_k接收到信息后，可知总跳数m具体值，然后n_k记录下接收到n₀数据的 时间t_r，并将时间信息t_r和跳数m回发给n₀。具体数据帧流动过程如图2所示。

第五，n₀接收到回发消息，并记录下接收到消息的时间t₂，通过本次数据交互， 无论节点经过具体哪一条链路，我们均可在最后收到数据包后知道途径的节点，因 此可以得知数据包抵达的节点与时间关系如图3所示。

可以列出下式：

t₂＞a_0kt₁+b_0k+t_mr+t_ms...+t_nr+t_ns+t_kr+t_0s

t₀＜a_0kt₁+b_0k+t_mr+t_ms...+t_nr+t_ns+t_kr+t_0s

其中，a_0k、b_0k是节点0与节点k的时间关系常数，是我们要求解的量。t_mr、t_ms是数据转发过程中经过节点m后的接收时间与转发时间，t_nr、t_ns是节点n的接收、 转发时间。由于在一次转发过程中，除同步节点n₀外，其他节点均处于同步状态， 因此其他节点的接收时间、转发时间的差距仅在于路由表遍历时某几条语句的执行 时间，可忽略不计，因此可认为：

t_mr＝t_nr，n，m∈{1，2，3...}

t_ms＝t_ns，n，m∈{1，2，3...}

故可得：

t₂＞a_0kt₁+b_0k+(m+1)t_kr+mt_ks+t_0s

t₀＜a_0kt₁+b_0k+(m+1)t_kr+mt_ks+t_0s

其中a_0k、b_0k、t_kr、t_ks、t_0s是5个未知量。

第六，以上收发过程，再重复4次，可得到5组数据。根据该数据可列出矩阵：

$\left(\begin{array}{ccccc}{t}_{11}& 1& m_1+1& m_1& 1\\ t_{12}& 1& m_2+1& m_2& 1\\ t_{13}& 1& m_3+1& m_3& 1\\ t_{14}& 1& m_4+1& m_4& 1\\ t_{15}& 1& m_5+1& m_5& 1\end{array}\right)\left(\begin{array}{c}{a}_{0k}\\ b_{0k}\\ t_{\mathrm{kr}}\\ t_{\mathrm{ks}}\\ t_{0s}\end{array}\right)<\left(\begin{array}{c}{t}_{21}\\ t_{22}\\ t_{23}\\ t_{24}\\ t_{25}\end{array}\right)$

$\left(\begin{array}{ccccc}{t}_{11}& 1& m_1+1& m_1& 1\\ t_{12}& 1& m_2+1& m_2& 1\\ t_{13}& 1& m_3+1& m_3& 1\\ t_{14}& 1& m_4+1& m_4& 1\\ t_{15}& 1& m_5+1& m_5& 1\end{array}\right)\left(\begin{array}{c}{a}_{0k}\\ b_{0k}\\ t_{\mathrm{kr}}\\ t_{\mathrm{ks}}\\ t_{0s}\end{array}\right)>\left(\begin{array}{c}{t}_{01}\\ t_{02}\\ t_{03}\\ t_{04}\\ t_{05}\end{array}\right)$

由于矩阵的第二列和第五列都是1，可知该矩阵的秩小于5，因此两组矩阵必 有解。利用简单的QR分解，n₀节点可通过固定算法算出两个矩阵的解，由两组解可 知a_0k、b_0k、t_kr、t_ks、t_0s5个变量的变化区间，取其中值即可得到该参数的估计值。

第七，n₀再发送一次数据给n_k，数据中包含该5个变量的估计值，n_k收到数据 后，列出以下等式：

t_k＝a_0kt₀+b_0k

通过该等式，可知如何调整节点k的时间值以达到时间同步。

第八，节点n₀与其他节点仍通过这种方式进行同步，与每个节点都进行第三、 第四、第五、第六、第七步，直到全网节点都完成同步。该方式可以大大降低TS/MS 同步协议的误差，并且该方法适用于非分级网络。

以上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上 述特定实施方式，本领域技术人员可以在权利要求的范围内做出各种变形或修改， 这并不影响本发明的实质内容。