无线生理传感器网络TPSN算法的改进与分析＊

何晓梅，蒋邦英，齐华

（1.国家安全生产监督管理总局通信信息中心，北京100013；2.西安工业大学）

引 言

无线生理传感器网络（Wireless Body Sensor Networks，WBSN）是基于无线传感器网络（Wireless Sensor Network，WSN）的。通过生理传感器网络节点采集生理信息，通过互联网或无线电传输到医院、用户或家属等检测终端，以便用户或医生随时监测用户的病情，做到早发现、早治疗［1－2］。但是由于网络传送时延的不确定性，不能以数据包到达的时间作为传感器节点数据的时间，因此必须在传感器节点集中维持一个与中心节点同步的时钟，即时间同步［3］。无线生理传感器网络具有传感器节点较少、网络结构固定和能量有限的特点，TPSN（Timing－sync Protocol for Sensor Networks）算法较其他时间同步算法在同步误差和同步精度上更适合于无线生理传感器网络的要求。

1 TPSN算法描述

TPSN算法［4］采用Client／Server时间同步的模式，与传统的网络时间协议NTP类似，其要达到的目的是在全网络范围内提供节点时间同步。该算法具有精度高的优点，比较适合于对同步精度要求较高的环境。TPSN协议采用层次型网络结构［5］，首先将所有节点按照层次结构进行分层，通过下层节点与其上层节点的时间同步，最终实现所有节点与根节点的时间同步。假定每个传感器都有唯一的标识号ID，节点间的无线通信链路是双向的，通过双向的消息交换实现节点间的时间同步。其同步过程包括两个阶段:

①层次发现与建立阶段。在网络部署后，根节点通过广播“级别发现”分组，启动层次发现阶段，级别发现分组包含发送节点的ID和级别。每个节点赋予一个级别，根节点被赋予最高级别，设为第0级，根节点的邻居节点收到根节点发送的分组后，将自己的级别设置为分组中的级别加1（即第1级），然后广播新的级别发现分组。节点收到第i级节点的广播分组后，记录发送这个广播分组的节点ID，设置自己的级别为（i＋1），广播级别设置为（i＋1）的分组。这个过程持续下去，直到网络内的每个节点都赋予一个级别。

②同步阶段。即实现所有节点的时间同步，第1级节点同步到根节点，第i级节点同步到第（i－1）级的一个节点，最终所有节点都同步到根节点，实现整个网络的同步。TPSN算法示意图如图1所示。

节点1属于（i－1）级节点，节点2属于i级节点；T1和T4表示节点2本地时钟在不同时刻测量的时间，T2和T3表示节点1本地时钟在不同时刻测量的时间；σ表示两个节点之间的时间偏差，d表示消息的传播延迟，假设来回消息的延迟是相同的。节点2为待同步节点，节点1为参照节点，节点2在T1时间向节点1发送同步请求分组，分组中包含节点2的级别和T1时间。节点1在T2时间收到分组，T2＝T1＋d＋σ，然后在T3时刻发送应答分组给节点2，分组中包含节点1的级别和T1、T2、T3信息。节点在T4时刻收到应答，T4＝T3＋d－σ，因此可以推导出下面公式:

图1 TPSN算法示意图

节点2利用公式（1）和（2）估算往返时延d和时间偏差σ，根据d和σ的值调整自己的时钟为t2＝t1＋d＋σ（t1为节点1的本地时钟，t2为节点2的时间），从而达到与参考节点1同步的目的。

2 TPSN算法改进

在TPSN算法中，节点的同步是通过逐级消息交换实现的，而消息的交换必然会引起消息传递延迟，这样就会引起同步误差。并且在多跳网络中，误差随着跳数的增加而增大。算法优化是通过减小消息交换延迟带来的误差来提高时间同步的精度。由TPSN算法的描述可知:误差由传输延迟和时间偏差两部分组成［6］，传输延迟为确定性部分，时间偏差为不确定性部分，而且若时钟频率的不一致还会导致时间漂移；所以非确定性部分由时间偏差和时间漂移组成。为了减小不确定部分引起的同步误差，提高同步精度，下面采用最小二乘法对TPSN算法进行优化。为了表达方便，将优化后的TPSN算法称为TPSN－LS（Time－sync for Senor Network with Least Square Method）。

若每个节点的时钟频率一样，那么只需考虑时间偏差，但是实际上每个节点的时钟频率并不一样，所以必须考虑时间漂移。设传输延迟为d，时间偏差为σ，若实际接收时间为T2，令T2在节点2上对应的时间为T′2，那么:

由式（1）得:

为了求时间偏差和时间漂移，我们建立数学模型:

其中，α表示两节点相应的时间漂移；σ表示时间偏差。令i为第i次同步，那么式（5）可整理为:可以看到这个方程有两个参数α和σ。这里用最小二乘法来求相关参数。

令yi＝Ti2，xi＝利用最小二乘法［7－9］求未知参数α和σ的估计值和得与所有的（xi，yi）（i＝1，2，…，n）拟合程度最好，即同步效果最好。

估计值与实际值的离差:

简化后得:

节点2可以利用计算出来的时间偏差值α和时间漂移σ来修正自身的本地时间，达到时间同步。这样计算出来的时间偏差在较长一段时间可以保持不变，为使用周期同步降低能耗提供了一种可行方法。

3 仿真结果

为了检验改进后的TPSN算法即TPSN－LS的性能，通过网络仿真工具NS－2［10］对算法进行了仿真实验。根据无线生理传感器网络的拓扑结构特点，选择了100个节点，节点的距离最大1.5m，最小0.1m，出于节约能量考虑，根节点选择在人体的中间部位，其余节点根据人体生理参数测量位置随机分布。主要从累积误差和同步精度两方面进行了实验，并从TPSN－LS算法的节点数目和层次数目对算法进行了性能分析，实验结果如图2、图3所示。

图2为时间同步的累积误差。节点跳数最大为10，是同步一次的累积误差。可以看出，TPSN算法的累积误差随节点跳数的增加而增加得较快，TPSN－LS算法的累积误差随节点跳数的增加而增加得较缓慢；相同节点跳数时，TPSN－LS算法的累积误差比TPSN算法要小得多，且节点跳数越大，两算法的累积误差的差值就越大。所以，TPSN－LS能够很好地减小时间同步的累积误差，从而显著提高了时间同步的精度。

图2 时间同步的累积误差

改进前后算法的时间偏差比较如图3所示。采用TPSN－LS算法进行时间同步时，多次同步的时间偏差波动较小，且在同步次数为20以后，其时间偏差比较接近10μs，几乎没有波动；然而TPSN算法的波动一直都比较大，且相邻同步次数的时间偏差的差值较大。在周期同步中，同步周期越长，能量损耗越少，而同步误差的波动直接影响同步周期的长短。由于TPSN－LS算法在同步次数达到20以后就几乎保持不变，而TPSN算法始终大幅度波动，所以TPSN－LS算法的同步周期要远大于TPSN算法。因此，在周期同步中，无论是考虑精度还是能耗问题，TPSN－LS算法都比TPSN算法更适合无线生理传感器网络。

图3 改进前后算法的时间偏差比较

结 语

与TPSN算法相比，改进后的算法更适用于周期同步。TPSN－LS算法不仅减小了时间误差，提高了同步精度，且在周期同步中有利于减少能耗，延长网络寿命。

［1］孔佳薇.体域网BSN的研究进展及应用前景［J］.上海市浦东科技信息中心，2010（7）:737－753.

［2］Eirik Næss－Ulseth，Novelda AS，Dag Ausen.Biomedical Wireless Sensor Network–phase II，2010.

［3］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005:185－266.

［4］Ganeriwal S，Kumar R，Srivastava M B.Timing－sync protocol for sensor networks［C］／／Proceedings of first ACM Conference on Embedded Networks Sensor System，Los Angeles，CA，USA，2003.

［5］Dai Hui，Han R.TSync:A Lightweight Bidirectional Time Synchronization Service for Wireless Sensor Networks［J］.Mobile Computing and Communications Review，2004，8（1）:125－139.

［6］刘俊.无线传感器网络TPSN协议的改进［EB／OL］.［2012－02－16］.http:／／www.paper.edu.cn／index.php／default／releasepaper／content／201101－355.

［7］Gao Q，Blow K J，Holding D J.Simple algorithm for improving time synchronization in wire less sensor networks［J］.Electronics Letters，2004，40（14）:889－891.

［8］邹乐强.最小二乘法原理及其简单应用［J］.河南工程技术学校，2010（23）:282－283.

［9］Tomas Schonhoff，Arthur Giondano.Detection and Estimation Theory and Its Applications［M］.Beijing:publishing house of electorica industry，2007:182－255.

［10］方路平，刘世华，陈盼，等.NS－2网路模拟基础与应用［M］.北京:国防工业出版社，2008（5）:42－104.