无线传感器网络时间同步CS-TPSN算法研究与仿真

董甲东，吴顺风，黄昌文

（1.安庆师范大学 电子工程与智能制造学院，安徽 安庆 246133；2.安徽安簧机械股份有限公司，安徽 安庆 246005）

近年来，随着多功能传感器技术和现代网络技术的快速发展，无线传感器网络（WSN）得到广泛应用。WSN是基于无线通信方式的分布式、多节点、多跳、自组织系统，其节点传感器属微型嵌入式设备，主要实现监测对象数据采集、处理、发送以及请求信息的控制等功能，通过多节点协同，组成无线传感器网络，最终将获取信息送达至用户[1]。

各节点传感器的时间同步是WSN的关键技术，也是近年来研究的热点领域。传感器节点在采集对象信息、信息处理、信息传输时，需要多个传感器节点协同工作[2]。在同一系统中，各节点信息的采集和传输需要有统一的时间标准，这也是多个节点进行信息交换的关键。在WSN中，传感器节点时间信息由各节点的本地时钟提供。每个传感器内含有一个晶体振荡器，其构成了本地计时器。晶体振荡器的生产工艺不同，或工作环境的温度、压力、工作时长不同，均可能导致传感器节点的晶振速率产生偏差，最终造成网络节点间的时间不同步。对于WSN，传感器节点时间保持同步是实现传感器运行、通信和节点定位的技术基础[3]。在综合分析、研究WSN的时间同步传统算法基础上，本文提出了CS-TPSN算法，通过层内和层间的优化设计[4]，改进拓扑结构，减少报文数量，降低算法开销，实现基于OPNET的建模和仿真分析。

1 无线传感器网络时间同步算法

Internet时间同步主要采用网络时间协议（NTP）实现系统各节点的时间同步，结合本地时间和时间误差，可对系统各节点进行时间统一，其精度可达毫秒级，时间同步机制已得到深入研究和广泛应用。基于NTP协议基础，WSN时间同步协议的算法主要有以下三类。

（1）接收者-接收者（Receiver-Receiver）的时间同步算法。其代表算法为2002年Jeremy Elson等提出的参考广播同步算法（RBS）[5]。该算法具有较低的同步误差，明显的缺点就是节点之间进行同步需要交换包含时间信息的数据包[6]，数据包交换次数太多使得算法复杂且能量消耗大[7]。

（2）发送者-接收者（Sender-Receiver）的单向时间同步算法。其代表算法为2004年Miklós Maróti等提出的泛洪时间同步协议（FTSP）[8]。该算法采用单向消息处理方式，通过将通信延迟进行详细划分并分别进行处理来减小延迟对同步精度的影响，虽然提高了同步精度、减少了数据包交换量，但由于采用泛洪的方式，通信距离受中心节点能量制约，对于范围较大的网络能量消耗严重。

（3）发送者-接收者（Sender-Receiver）的双向时间同步算法。其代表算法为2003年Saurabh Ganeri‐wal等提出的传感器网络的时间同步协议（TPSN）[9]。该算法采用中心节点与子节点的双向通信，交换时间信息计算偏差值达到网络时间同步，虽然具有较高的时钟同步精度，但当网络中节点密度较大时，节点同步跳数明显增加，这影响了同步精度并增加了节点能量消耗。

此外，Kyoung-lae Noh等将RBS和TPSN进行结合，提出了PBS（Pairwise Broadcast Synchronization）时钟同步算法[10]。该算法采用仅接收者（ROS）同步机制，减少了网络通信能耗，但其采用两个超级节点覆盖网络中其他所有节点，存在通信范围有限的问题。当WSN规模增大时，网络的同步精度会随着节点的同步跳数增加而降低，同时会增加能耗[11]。经典时钟同步算法无法有效适应大规模多跳WSN。为此，结合TPSN与RBS算法的优点，本文提出一种应用于多跳WSN的时间同步算法，即CS-TPSN（Clock Synchronization Node-TPSN）。在TPSN算法基础上首先引入时钟节点。同步节点和普通节点的概念，然后以分层的方式划分节点，采用发送者-接收者双向时间同步协议并结合广播时间同步协议方式完成WSN时间同步，该算法可以确保同步精度，降低节点能量消耗，能够应用于多跳WSN。

2 CS-TPSN改进算法

2.1 TPSN算法

TPSN时间同步算法是基于发送者-接收者双向时间同步算法的代表协议，通过发送者与接收者间相互交换时间信息实现同步。该算法类似于NTP时间同步协议，需要一个提供绝对时间的时钟源来负责对全网进行时间同步。采用网络分层，将节点按层次划分，下层节点只与对应上层节点通信以完成时间同步。算法执行步骤分为两个阶段：层次发现阶段和时间同步阶段。

层次发现阶段，该阶段主要工作是将网络分层。TPSN构建了一个生成树，其中给每个节点设定唯一ID号，通过记录节点ID号以维持分层过程中父子节点关系，每个节点都知道自己和父节点的层次。设定时钟源节点为0层的根节点，负责网络层次划分开始。根节点发送分层数据包，其中包含自己所在0层的层次信息和节点ID。当所有一跳邻居节点接收到数据包时，一跳节点将自己层次设为1，父节点层次设为0，并记录父节点ID信息。一跳节点完成后再发送分层数据包，此时接收到1层数据包且未分层的节点将自己层次设为2，父节点层次设为1，并记录父节点ID信息。以此类推来完成全网层次划分。二跳TPSN网络拓扑如图1所示。

图1 TPSN网络拓扑结构

时间同步阶段，该阶段主要工作是将网络节点时间同步。当网络层次发现阶段完成后，由参考节点发送时间同步开始包，开始网络时间同步，时间开始同步包发送至全网。1层节点接收到开始同步数据包后向根节点发送时间同步请求，根节点接收后发送同步应答包，1层节点依次完成时间同步。待一层节点全部完成同步后，2层节点向1层节点发送时间同步请求，1层节点接收后发送同步应答包，2层节点依次完成时间同步。以此类推完成全网节点时间同步。节点双向交换信息过程如图2所示。

图2 TPSN协议节点双向交换信息过程

假设两个节点i、j，将节点i同步到节点j，节点同步过程具体如下：

（1）节点i准备一个时间同步包，发送给节点j开始时间同步，并记录发送时刻T1；

（2）节点j接收到节点i的时间同步包后，立刻记录接收时刻，记录为T2；

（3）节点j等待一段时间后发送时间同步应答包给节点i，并记录发送时刻T3；

（4）节点i接收到节点j的时间同步应答包，记录接收时刻为T4，并通过记录的时间戳信息计算时间偏差。

令节点时间偏差为θ，传输延迟为d，根据时间同步过程可得计算出偏差和延迟后，节点i和j的时钟差异可以修正，使用偏差校正本地时钟，提高同步精确度。

2.2 CS-TPSN改进算法

如何降低TPSN协议的数据包交换次数，降低协议开销，是研究优化算法的主要方向。TPSN算法的节点间相互通信次数较多，在一次时间同步过程中，每一个节点都需要与父节点交换最少4次数据包。为解决数据包交换次数多的问题，通过网络拓扑简化对时间同步算法进行优化。简化后拓扑结构如下页图3所示。

图3 CS-TPSN网络拓扑结构

TPSN协议在多跳情况下，下层节点需向每个上层节点发送时间同步请求，下层节点需与多个上层节点计算偏差，这种同步方式并不能保证同步精度的提高。因此，设计下层节点选取一个上层节点作为父节点，一个下层节点对应一个父节点，父节点对应一个或多个子节点，父节点在整个网络中被称为同步节点。具体工作流程如下页图4所示。

图4 CS-TPSN算法工作流程

（1）网络拓扑初始化。全网时钟源的参考节点主动发起周期性拓扑更新。数据中包含参考节点ID信息、自身层次和父节点等信息。接收到广播消息的节点保存接收信息，将发送数据节点设置为父节点，并继续发送包含相同信息的数据包，以此完成全网初始化。

（2）计算二跳节点。网络初始化完成后，每个节点将保存自己的子节点信息，然后节点将子节点信息发送到父节点，此时父节点与自己保存的子节点信息进行对比可获得二跳节点信息。

（3）计算同步节点。对于每个同步节点的计算，采用的是贪婪启发式算法[12]。算法优先覆盖独立节点，二跳节点与根节点之间如果只有一个节点进行数据转发，则此中间节点被选为同步节点。在独立节点覆盖完成后，根据子节点覆盖的二跳节点数量判断是否被选择为同步节点，二跳节点覆盖数量多的优先选中，完成全部覆盖和同步节点选择。

（4）同步方式名单。上层节点计算完同步节点并广播发布信息，下层节点将根据此信息生成同步方式名单。当下层节点接收到上层节点发送的同步信息名单后，与自己ID进行对比，如果在名单中则将上层节点记录在自己的同步节点名单中，并采用时间同步协议同步；如果不在同步名单中则将自己的同步名单记录为空，采用广播方式同步。

3 CS-TPSN算法建模与仿真

OPNET是一款用于网络环境建模与仿真的专业软件包，能精准仿真和分析各类复杂网络性能，在网络设备制造和通信运营领域有广泛的应用。下面基于OPNET进行建模和仿真分析。

3.1 CS-TPSN算法建模

CS-TPSN算法建模主要包括进程层次设计、节点模型和包结构设计、网络结构设计等，进程层次设计是建模仿真工作的核心。CS-TPSN算法具体功能将在进程模型设计中实现，设计完成后即可设计节点和网络结构，最终完成仿真设计。

CS-TPSN算法节点分为TIME和COMMON节点，TIME节点负责提供基准时钟，定义为0层根节点，其他除TIME节点外均为COMMON节点。TIME节点与COMMON节点均采用相同进程模型，但通过进程函数模块设计并判断节点类型后，执行不同功能。进程模型如图5所示。

图5 TIME和COMMON节点进程模型

判断TIME节点和COMMON节点关键代码如下。

//获取节点类型

op_ima_obj_attr_get(own_node_id,"Node Type",&node_type);

if(node_type==0)

{

initial_offset=0.0;

initial_skew=0.0;

//调度基准节点并发起拓扑初始化过程

op_intrpt_schedule_self

(op_sim_time(),TOPO_CODE);

own_parent=-1;

own_level=0;

}

else

{

//非核心节点存在时钟偏差

initial_offset = op_dist_uniform

(0.1);

initial_skew=op_dist_uniform(0.000001);

own_parent=-1;

own_level=MAX_NODE_NUM;

}

TIME节点作为全网核心节点，有独立时钟源，负责提供全网基准时间。根据算法描述，核心节点主要承担以下工作：（1）启动网络拓扑，对网络进行分层和拓扑更新；（2）作为网络节点参与网络结构划分；（3）与下层节点相互交换数据包，完成时间同步。TIME节点功能实现关键代码如下。

if(op_intrpt_code()==TOPO_CODE)

{

//创建拓扑初始化报文

pkptr=op_pk_create_fmt("topo_init_pkt2");

//设置报文字段内容

op_pk_nfd_set(pkptr,"Type",0x00);

op_pk_nfd_set(pkptr,"Node ID",own_address);

op_pk_nfd_set(pkptr,"Level",0);

op_pk_nfd_set(pkptr,"Parent ID",-1);

//统计网络开销

op_stat_write(ovhd_gstathandle,1.0);

op_stat_write(ovhd_gstathandle,0.0);

//发送报文

op_pk_send(pkptr,OUTSTRM);

}

COMMON节点作为网络内的普通节点，需要将时间与TIME节点同步。根据算法描述，COMMON节点主要承担以下工作：（1）作为网络节点，响应核心节点发起的网络初始化，完成网络分层和拓扑更新；（2）网络分层完成后，主动向上层节点发起时间同步请求，与上层节点进行信息交互，完成时间同步工作；（3）如果COMMON节点被选择为同步节点，则负责与下层节点进行信息交互完成时间同步工作。COMMON节点功能实现关键代码如下。

//时间同步应答报文

static void time_synrpy_handle(Packet*pkptr)

{

int temp_node_id;

double temp_date;

FIN(time_synrpy_handle(pkptr));

//从报文中提取有效字段

op_pk_nfd_get(pkptr,"Child ID",&temp_node_id);

//判断是否应答给本节点的报文

if(temp_node_id==own_address)

{

//提取上层节点反馈的时间信息

op_pk_nfd_get(pkptr,"T O 2",&syn_to2);

op_pk_nfd_get(pkptr,"T O 3",&syn_to3);

//记录当前接收反馈时间

syn_ta4=current_time;

//计算时间偏差

temp_date=((syn_ta4-syn_to2)-(syn_to3-syn_ta1))/2;

time_date-=temp_date;

printf("node:%d current:%f time:%f date:%f-- % f ",own_address,current_time,op_sim_time(),temp_date,current_time-temp_date);

}

3.2 仿真分析

采用OPNET仿真软件，对CS-TPSN算法与传统RBS、TPSN算法的时间同步误差和网络开销进行仿真，结果如图6、图7所示。由图6可知：RBS算法的同步误差较高，随着节点数增加其误差随之加大；TPSN算法的同步误差在节点数较少和跳数低的情况下表现优异，但随着跳数增加，同步误差逐渐增加；在跳数较少时，CS-TPSN算法与TPSN算法时间同步误差相差不大，但随着跳数增加，CS-TPSN算法同步误差逐渐优于TPSN。由图7可知：节点数量较少时，CS-TPSN算法无法选择最佳邻居节点，其性能应与TPSN相同，但由于CS-TPSN算法可以减少节点数据包交换次数，其他节点采用广播监听的方式完成时间同步；而TPSN算法采用一对一时间同步，每个节点通过直接与上层节点交换数据包完成同步，随着网络节点数增加，跳数增多，CS-TPSN算法同步误差将明显小于TPSN算法，当节点数目为150时，误差结果降低约20%，由其趋势可知，伴随节点数目增加误差降低效果增强，如图6所示。随着节点数增加，RBS、TPSN算法协议开销均高于CS-TPSN算法。

图6 CS-TPSN算法与传统算法的误差仿真分析

图7 CS-TPSN算法与传统算法的网络开销仿真分析

4 结束语

综上所述，本文在综合分析传统TPSN、RBS时间同步算法的基础上，提出了改进算法CS-TPSN。本算法主要通过减少TPSN数据包交换次数减低能耗，提高节点生存寿命；采用周期性更新拓扑结构，提高算法的可扩展性，效果较好。但是，不足在于算法设计没有充分考虑移动节点，这是未来研究和改进的方向。