基于移动模型的水下传感器网络时间同步算法

王慧强，温秀秀，林俊宇，冯光升，吕宏武



基于移动模型的水下传感器网络时间同步算法

王慧强，温秀秀，林俊宇，冯光升，吕宏武

（哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨 150001）

水下传感器网络具有高时延、移动性的特点。现有时间同步算法在网络移动性方面考虑不足，时间同步参数计算精度不高。针对该问题，首先分析网络移动性对时间同步参数计算的影响，建立节点移动模型，并在此基础上推导出时间同步参数计算方程；进而提出一种能够应用于水下高时延网络的时间同步算法MM-sync。实验结果表明，与现有算法相比，MM-sync能够在通信量较小的基础上达到较高的精确度，适用于高密度快速运动的水下传感器网络。

传感器网络；水下环境；高时延网络；时间同步；移动模型

1 引言

水下传感器网络是指将具有能耗低、较短通信距离的水下传感器节点部署到指定海域中，采用水声通信，利用节点的自组织能力自动建立的网络[1]，具有网络传播时延大、移动性和能量有限的特点，是一种新型传感器网络。时间同步是网络节点调度和网络安全认证等算法的基础[2~4]，是水下传感器网络的重要问题[5,6]。对于采用无线电波通信的传感器网络，已经出现了一些成熟的时间同步算法。例如，Tiny-sync算法、Mini-sync算法和LS(light weight tree-based synchronization)算法。这些算法往往忽略网络传播时延，不能适应水下的高时延环境[7]，尤其是水下传感器网络的移动特性会导致传播时延始终处于动态变化状态，进一步增加了时间同步算法的设计难度。

针对水下网络的高时延特性，Affan等[8]首先提出了TSHL(time synchronization for high latency acoustic networks)算法，该算法通过2个阶段的消息交换来估计节点时钟间的相对漂移和相对偏移，算法过程简单易行，但忽略了节点在通信过程中的移动性，不能适用于节点运动剧烈的环境。Nitthita等[9]在分析了影响时间同步精度的因素后，提出了MU-sync(time synchronization protocol for underwater mobile networks)算法，该算法通过增加双向通信次数实现节点对时间同步，能够达到较高精度，但需要消耗大量能量。Bong等[10]考虑了节点不能和时间参考节点直接通信的情况，提出了针对时延容忍网络的分布式时间同步算法DCS(distributed asynchronous clock synchronization in delay tolerant networks)，该方法通过相邻节点间歇性通信的方法提高时间同步的准确性，并使用加权系数衡量时间同步信息的精度以解决网络时延对计算结果的影响。刘军等[11]提出了Mobi-sync算法，该算法借鉴了洋流模型，节点首先估计自身运动趋势，然后进行时间同步。该算法与具体环境结合紧密，为解决时间同步问题提供了新思路，但也限制了其应用范围。

现有水下传感器网络时间同步算法以双向通信为基础，能够适应水下网络的高时延特性，却忽略了网络的移动特征，导致计算精度不足（移动特性会导致传播时延始终处于动态变化状态）；Mobi-sync等算法虽然考虑了水下网络移动性的特点，提高了算法的计算精度，却需要节点感知自身运动速度，限制了算法的应用范围。针对这些问题，本文综合考虑了水下网络高时延和移动性特点，建立节点移动模型，并在此基础上分析网络传播时延与节点位置的动态变化，得出时间同步参数方程，进而提出算法MM-sync，仅通过节点之间的单向通信和时间同步参数方程求解，即可得到时间同步所需的参数，实现节点间时间同步。与其他时间同步算法相比，MM-sync无需双向通信，节点无需对自身的运动速度进行感知，能够适应水下网络高时延和移动特性，具有适用性强、计算精度较高、网络能量消耗较小的特点，适用于近海区域的高密度水下传感器网络。

2 水下传感器网络时间同步模型

传感器网络中节点的本地时钟是依靠对自身晶体振动中断计数实现的[12]。每个晶体由于制作工艺等因素，震荡频率存在微小偏差。此外，不同节点的时钟初始化时间也有可能不同。这些因素造成不同节点时钟会存在差异。节点的时钟与标准时间存在以下关系

时钟频偏和时钟漂移的范围是确定的。其中，传感器节点时钟频偏的范围由传感器生产工艺确定，可以从传感器的性能参数中得出。同时，时钟初始化时间的不同是引起时钟漂移不为0的主要原因，应小于相邻节点传输信号的最大时延。

MM-sync算法的目标是计算普通传感器节点的时钟频偏和时钟漂移，完成普通传感器节点和浮标节点的时间同步。下面首先介绍MM-sync算法的基础——节点移动模型。

3 节点移动模型

节点移动模型是MM-sync算法的基础。本节首先分析洋流对节点运动的影响；然后描述时间同步过程中信号传输时间与节点位置的动态变化关系，建立节点移动模型。

3.1 洋流对节点运动的影响

节点的运动受洋流影响。Brower在20世纪70年代提出了洋流模型

3.2 时间同步节点移动模型

网络中有普通传感器节点和浮标节点，的时钟频偏为，时钟漂移为。网络布置好后，发送时间同步数据分组。依次接收到数据分组。形成记录列表。中记录表示第个数据分组由在时刻发送，在其时钟显示时接收。这里浮标节点时间为参考时间，因此为标准时间，而对应的标准时间即修正时间为。

(4)

4 MM-sync原理

本节主要介绍MM-sync计算时间同步参数的原理。首先以节点移动模型(式(4))为基础，建立时间同步参数方程组；然后分析时间同步参数方程组在具体应用过程中可能产生的误差，以及其控制方法。MM-sync算法的具体流程将在第5节给出。

4.1 时间同步参数方程组

式(4)是一个二次方程，且包含了一些时间同步不关心的变量、、，可以采用变量替换的方法简化运算，变量替换规则如下

(6)

(7)

将式(5)~式(7)代入式(4)，可得关于、、、、的五元一次方程

(9)

4.2 误差控制

算法的误差来源主要有2个：1) 极端天气下水下节点的剧烈运动；2) 时间同步数据分组的处理和发送时延。可以采用线性拟合、多浮标节点时间同步的方法降低第一种误差；采用物理层加时间戳的方法降低第二种误差，下面分别介绍各个误差控制方法的原理。

4.2.1 线性拟合

降低假设节点做匀速直线运动的时间，进而结合线性拟合可以降低第一种误差。具体来说，首先对方程组(9)进行变换，将、、作为中间变量，对参数计算方程组(9)中的任意4个方程进行变换，消去、、，得到和的线性关系如下

其中，系数、、的计算方法如下

(12)

(14)

(15)

4.2.2 多浮标节点同步

当网络中存在多个浮标节点时，普通传感器节点可以充分利用从多个浮标节点接收的时间同步数据分组来提高MM-sync算法的计算精度。然而，并不是所有浮标节点发送的数据都可靠，因此需要对每个浮标节点发送的数据进行筛选。

首先根据时钟频偏和时钟漂移的大概范围进行数据初步筛选。令、分别表示时钟频偏和时钟漂移的最大可能偏差。4.2.1节提到将收集到的来自的数据每4个划分为一组，并对每组数据应用式(12)~式(15)，得到关于和线性关系的系数。令、、表示第组系数，表示系数的组数。根据式(11)可以得到，进而得到不等式。由于，，因此可以得到、、应满足的约束关系为

4.2.3 物理层加时间戳

针对第二种误差来源，可以采用在物理层加时间戳的方法降低误差。水声网络中数据分组延时主要由3部分组成：数据分组处理时延、信道接入时延、传播时延[9]。水声信号的传输速度大约为无线电波的传输速度的百万分之一，传播时延在秒级，因此传播时延占数据分组时延的主要部分。其余2种时延可以使用在物理层加时间戳的方法降低其对时间同步的影响[9]。下面对MM-sync算法进行详细介绍。

5 MM-sync算法

结合上面MM-sync计算时间同步参数的原理，提出一种能够应用于水下高时延网络的时间同步算法。首先给出MM-sync算法的具体流程；然后介绍时间同步数据分组的结构；最后分析算法的时间复杂度。

5.1 算法流程

MM-sync采用单向通信。浮标节点作为时间同步参考节点，开启网络时间同步，开始周期性地发送时间同步数据分组；普通传感器节点收集时间同步数据分组，首先进行数据分组，然后建立线性方程组，并在此基础上进行数据筛选，最后结合线性拟合方法计算时间同步所需的参数。MM-sync算法伪代码如下。

算法：MM-sync

输入：、、、、

输出：、

开始

/*数据收集*/

2) 接收时间同步数据分组;

5) end while

6) for 每一个时间同步参考节点

8) while {lengh([])<4}

/*数据分组*/

/*线性方程建立*/

/*数据筛选*/

17) end if

19) end while

/*数据深度筛选*/

25) end for

26) end if

27) end for

28) 删除、、中值为null的元素;

/*对标准型进行线性拟合*/

结束

对于存在不能和浮标节点直接通信节点的网络，可以与网络分簇机制相结合，采用逐步同步的方法。水下无线传感器网络为了便于管理，通常需要建立分簇结构[1]，每个簇里包含一个簇头节点和若干成员节点，簇头节点与其成员节点一跳可达，负责收集成员节点数据，并通过其他簇头节点将数据发送到浮标节点。这里假设网络已经采用文献[14]所述的簇构建算法，为普通传感器节点建立了簇结构。浮标节点作为初始时间同步参考节点开启网络时间同步，此时能够与浮标节点直接通信的节点通过MM-sync完成时间同步；完成时间同步的簇头节点进而成为临时时间同步参考节点，周期性地发送时间同步数据分组个，进而使其成员节点和与其相邻的簇头节点能够通过MM-sync完成时间同步；此过程一直继续，直到所有簇头节点都成为临时时间同步参考节点，全网时间同步完毕。

5.2 时间同步数据分组格式

时间同步数据分组由发送节点序号、发送时间、接收时间3部分组成。

时间同步数据分组由时间同步参考节点发送。节点在应用层产生数据分组，并在数据分组上标记自身节点序号；在物理层标记数据分组发送时间。

时间同步数据分组由未完成时间同步的普通传感器节点接收。节点在接收到时间同步数据分组后，在物理层将接收时间标记在数据分组上，并在应用层执行上面的时间同步算法。

5.3 时间复杂度分析

时间复杂度是衡量算法计算量的标准，本部分主要分析MM-sync算法的时间复杂度。MM-sync算法核心部分是第6）行~29）行，是一个二层循环结构。外层循环变量为时间同步参考节点的数量；对于每一个时间同步参考节点，内层循环次数为从该时间同步参考节点处接收数据分组的数量。因此总循环次数为数据分组的总数量，计算时间复杂度为，是一种简单算法，能够适用于计算能力低、电池能量有限的水下传感器网络节点设备。

6 实验与分析

实验环境为NS-2 (network simulator-2)，本文对NS-2进行了修改，添加了水下仿真模块和时间同步算法，并在此基础上从数据分组消耗量、时间同步精度两方面对MM-sync算法、TSHL算法和MU-Sync算法进行比较。

6.1 实验设置

表1 实验参数设置

6.2 实验分析

图4所示为数据分组消耗量随节点数量的变化情况。横轴表示网络中普通传感器节点的数量，纵轴表示网络完成同步所消耗数据分组的数量。从图中可以看出，随着节点数目增加，MM-sync算法的数据分组消耗量不变，TSHL算法与MU-sync算法数据分组消耗量增加，其中，MU-sync算法数据分组消耗量增加最为明显。这是由于TSHL算法在第2阶段需要时间同步参考节点与传感器节点进行一次双向通信，以计算节点时钟漂移，因而数据分组消耗量曲线随节点数量增加而缓慢上升。算法MU-sync为了达到更高的计算精度，增加了双向通信的次数，当网络节点较多时，消耗数据分组的数量迅速增加，远远超过了MM-sync算法和TSHL算法。而MM-sync算法无需双向通信，原理与TSHL算法和MU-sync算法不同，普通传感器节点不需要对时间同步数据分组进行应答。因而无论节点数目增加或减少，消耗数据分组的数量始终为常量。

图11和图12分别显示多浮标节点条件下时钟同步计算偏差随洋流流过频率的变化情况(可靠度门限，置信度，图中MM-sync后面括号中的数字表示浮标节点的数量)。由图可知，MM-sync(4)的计算精度优于其他算法。当洋流流过频率较小时，网络节点运动较为稳定，此时浮标节点数量(即时间参考节点的数量)对MM-sync算法计算精度的影响较小，MM-sync算法和MU-sync算法的计算精度相差不大；随着洋流流过频率的增加，网络节点运动的不稳定性增强，各个算法的计算精度逐渐降低，由图11和图12可知，此时增加浮标节点的数量能够保持MM-sync的计算精度，使MM-sync(4)和MM-sync(2)的计算精度优于MU- sync，因此增加浮标节点的数量能够增强MM-sync应对洋流频繁波动的能力。

7 结束语

水下传感器网络高时延、移动性和能量有限的特点增加了时间同步算法设计的难度。针对水下网络的特性，本文首先建立节点移动模型，并以此为基础，提出了一种时间同步算法MM-sync。MM-sync通过单向通信和时间同步参数方程求解的方法，完成时间同步所需参数的计算，并结合线性拟合的方法降低算法误差。与已有时间同步算法相比，MM-sync算法避免了双向通信，能够有效地降低网络负载，降低网络能量消耗；节点无需感知自身速度，增加了算法的适用范围。同时，由于在建模过程重点考虑了节点移动导致的网络时延动态变化问题，因此在节点高速运动的环境下，仍能够保证所需的计算精度。实验结果表明，MM-sync算法在高密度运动稳定的水下环境中具有良好性能，且能够适应各种盐度与温度的水域环境。但算法目前采用的移动模型仅适用于水流较为平稳的近海区域。在接下来的工作中将对移动模型进行改进，以扩大本算法的适用范围。

[1] GUO Z W, LUO H J, HONG F, et al. Current progress and research issues in underwater sensor networks [J]. Journal of Computer Research and Development, 2010,47(3):377-389.

[2] SEUNGKU K, HUA B L, DOO S E. An independent sleep scheduling protocol for increasing energy efficiency in wireless body area networks[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2013, E96-A(5): 908- 915.

[3] QASIM M C. Simple and robust clock synchronization scheme[J]. IEEE Transactions on Communications, 2012,60(2):328 -332.

[4] JULIEN R, DARRY V, TIMOTHY B. The case for feed-forward clock synchronization[J]. IEEE/ACM Transactions on Networking, 2012, 20(1):231-242.

[5] FIKRET S, BULENT Y. Time synchronization in sensor networks: a survey[J]. IEEE Network,2004,18(4):45-50.

[6] SAURABH G, RAM K, MANI B S. Timing-sync protocol for sensor networks[C]//The 1st International Conference on Embedded Networked Sensor Systems. New York, c2003: 138-149.

[7] GUO Y, LIU Y T. Mobile counteracted time synchronization for underwater sensor networks[J]. Information Computing and Applications, 2012,307(1): 515-522.

[8] AFFAN A S, JOHN H. Time synchronization for high latency acoustic networks[C]//The 25th IEEE International Conference on Computer Communications. Barcelona, Spain, c2006: 1-12.

[9] NITTHITA C, WEE-SENG S, KEE C C. MU-sync: a time synchronization protocol for underwater mobile networks[C]//The Third ACM International Workshop on Underwater Networks. New York, c2008:35-42.

[10] CHOI B J, SHEN X M. DCS: distributed asynchronous clock synchronization in delay tolerant networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2012,23(3):491-504.

[11] LIU J, ZHOU Z, ZHENG P, et al. Mobi-Sync: efficient time synchronization for mobile underwater sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013,24(2): 406-416.

[12] ZHOU X W, WEI W, QIN B P. Research on time synchronization in wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2006,19(1):20-29.

[13] CARUSO A, PAPARELLA F, VIEIRA L F M, et al. The meandering current mobility model and its impact on underwater mobile sensor networks[C]//The 27th Conference on Computer Communications. San Francisco, CA, USA, c2008: 771-779.

[14] SUNDARAMEENA V, PRIYATHARISINI D. Acquaint based grid clustering algorithm for Underwater wireless sensor network[C]//2014 International Conference on Information Communication and Embedded Systems. Chennai, India, c2014: 1-4.

Time synchronization algorithm based on mobility model for underwater sensor networks

WANG Hui-qiang, WEN Xiu-xiu, LIN Jun-yu, FENG Guang-sheng, LYU Hong-wu

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

With the characteristics of high transmission delay and mobility, distributed time synchronization of underwater sensor networks can be very challenging. The existing works cannot get high accuracy, because most of them ignore the long transmission latency, or dynamic changing transmission delay caused by the mobility. A mobility model was built considering the effect of mobility and long transmission latency on time synchronization, and a time synchronization parameters equation was formed according to the mobility model. Thus, based on the equation, a time synchronization algorithm (MM-sync) was proposed. The experiment results show that MM-sync can reduce the consumption of energy, and can get higher accuracy than state-of-art solutions in high density underwater sensor networks with rapid movement.

sensor networks, underwater environment, high latency propagation networks, time synchronization, mobility model

TP393

A

10.11959/j.issn.1000-436x.2016001

2014-11-11；

2015-02-06

国家自然科学基金资助项目(No.61370212)；博士点基金优先发展领域基金资助项目（No.20122304130002）；教育部高等学校博士点基金资助项目（No.20102304120012）；黑龙江省自然科学重点基金资助项目（No.ZD201102）；中央高校基本科研业务费专项基金资助项目（No.HEUCF100601, No.HEUCFZ1213）

The National Natural Science Foundation of China (No.61370212), The Research Fund for the Doctoral Program of Higher Education of China (Priority Development Area) (No.20122304130002), The Research Fund for the Doctoral Program of Higher Education of China (No.20102304120012), The Natural Science Foundation of Heilongjiang Province (No.ZD201102), The Fundamental Research Fund for the Central Universities (No.HEUCF100601, No.HEUCFZ1213)

王慧强（1960-），男, 河南周口人，哈尔滨工程大学教授、博士生导师，主要研究方向为云计算、信息安全、自律计算与可信计算、认知网络。

温秀秀（1989-），女，黑龙江牡丹江人，哈尔滨工程大学博士生，主要研究方向为传感器网络、未来网络和认知网络等。

林俊宇（1981-），男，广西博白人，哈尔滨工程大学助理研究员，主要研究方向为自律计算、未来网络和 QoS保障。

冯光升（1980-），男，山东德州人，哈尔滨工程大学讲师，主要研究方向为认知网络和QoS保障。

吕宏武（1983-），男，山东日照人，哈尔滨工程大学讲师，主要研究方向为未来网络、性能评价和进程代数。