基于分簇的时间同步算法

宋协栋

摘要：由于无线传感器网络中的节点能量有限，能量有效是拓扑设计的一个重要问题，它能在很大程度上影响着网络的寿命。分簇是提高网络寿命和可扩展性的一种基本机制。在本文中，提出了一种能量有效的分簇机制CTSA来最小化无线传感器网络中的能量消耗。

关键词：无线传感器网络 分簇 时间同步 能量有效

1.引言

时间同步问题是支持无线传感器网络广泛应用的基础支撑技术，实时保证网络的同步精度是目前研究时间同步问题关注的焦点所在。无线传感器网络的独特性为时间同步问题的研究增加了难度，如传感器节点采用电池供电，能量有限，因此设计时间同步算法时应该综合考虑同步精度和能量消耗，尽量取到平衡点；传感器节点资源有限，无论是信息存储还是数据计算都不能太复杂[1]。

针对现有时间同步机制的不足，本文以TPSN同步算法和RBS同步算法为基础，综合考虑了分簇对时间同步算法的影响，设计了一种基于分簇的时间同步算法。算法首先以DEEC分簇算法为基础进行网络拓扑结构的构建，均衡网络中节点的能量消耗，之后，簇间采用双向成对同步的同步方式使得簇头与BS节点进行同步，簇内以簇头节点为基准节点，按照单向广播同步的同步方式，并采用在MAC层增加时间戳的方式，去掉访问时间和发送时间对时间同步的影响，提高算法同步精度。

2.相关工作

2.1 网络模型

有N个传感器节点随机部署在M*M的检测区域内，为了简化网络模型，采用如下合理的假设：

1） 基站BS远离监测区域，是静止的，有供电设施，提供标准全局时间。普通传感器节点电池供电，能量受限。

2） 所有传感器节点一旦部署完毕就不再移动或者是微移动的。

3） 簇内成员节点都在彼此通信范围内。

2.2 DEEC分簇算法

DEEC（Distributed energy-efficient clustering algorithm，分布式能量有效成簇算法）[2]规定每个节点根据其初始能量和剩余能量来决定其成为簇头的概率，即簇头轮转周期适应节点的能量变化。算法实现了具有较高的初始能量和剩余能量的传感器节点比低能量的传感器节点有更多机会成为簇头，即能量高的节点成为簇头的次数会更多，从而实现能量的均衡消耗，延长网络寿命。

算法过程同Leach算法，簇头的选举周期性按照“轮（round）”来随机选取，各个节点产生一个0到1之间的随机数，如果该数小于Ti（将Pi带入Ti就可以得到不同节点的Ti）则相应的节点即作为簇头，然后确定的簇头节点发送一个短消息，其它节点按照收到簇头信息信号的强度决定加入哪一个簇。

3.算法设计

分析已有无线传感器网络时间同步算法可知，节点的同步误差随着距离和跳数的增加而增大，因此利用簇的形式来减少同步路径上的同步跳数，降低同步误差，提高同步精度。

根据网络规模的不同，本文考虑这样一种情况，无线传感器网络规模不大，簇头节点可以与BS节点一跳通信，部分簇成员节点无法与BS直接通信，设计基于分簇的单跳时间同步算法CTSA，簇头节点与BS以TPSN算法双向成对同步方式进行双向同步。

3.1 CTSA同步算法

在单跳分簇情形下，簇头节点可以与BS节点一跳通信，以BS节点为根节点，所有簇头节点作为上层节点，簇成员节点作为下层节点。

算法首先按照DEEC分簇算法构建网络，BS节点作为基准节点连通外部互连网与内部传感器网络，有基础供电设施，即能量不受限制，并且能够提供全局的标准时间。BS节点向其通信范围内所有簇的簇头节点发送同步信息，簇头节点以一跳的方式进行回复，以双向成对同步方式进行时间同步，以此来保证初级节点的同步精度。

将网络的整个过程划分为轮（round）），每一轮又有多个期（epoch）组成，每一轮由建立拓扑结构和时间同步两个阶段构成。在建立拓扑结构阶段网络中的传感器节点按照自组织的方式以DEEC分簇方法建立全网的拓扑结构，选取网络中能量较高的节点作为簇头节点。网络中节点的状态分别为：簇头节点和簇成员节点，簇头节点保持活动状态，而其它簇成员节点进入睡眠状态，减少能量消耗，直到簇头节点将其唤醒。进入时间同步阶段，BS节点按照双向成对同步的方式同步所有簇头节点，保证簇头节点同步的精度，之后每个簇内部分布式的进行内部时间同步，按照单向广播同步算法的方式。为了提高簇内节点的时间同步精度，簇头节点通过多次广播时间同步信息，接收者节点之间多次记录到达的时间信息，采用4.1中的线性回归的方式来减少时间同步误差。一个同步周期即一个epoch。网络定时重构，重复以上过程。

簇内同步过程算法具体过程：

1） 簇头节点O于t1时刻广播同步信息，簇内成员节点记录到达时间，此处以节点A和节点B为例，收到同步信息时间分别为t2和t5。随即选择成员节点回复，此处假设为节点A，在时间t3回复信息，信息包含t2和t3，簇头节点O在时间t4收到，按双向成对同步的方式可以得到时间偏差为 。

2） 簇头节点O再次广播同步信息，信息中包含t2和时间偏差Δ。簇成员节点收到后可以计算达到同步。

3.2 CTSA能耗分析

同步开销，即发送的时间同步信息数包括两部分：BS节点与簇头节点同步时交换的同步信息数和簇内节点同步时交换的同步信息数。设节点总数为N=n+1，n表示普通传感器节点的数目，“”表示1个BS节点。

同步信息数目计算公式为：

能量的消耗按照同步算法过程分三部分：建立分簇的网络拓扑结构消耗的能量E1，簇头与节点BS同步消耗的能量E2，簇内节点同步消耗的能量E3。各部分能量消耗公式如下：

消耗总能量为：

dtoBS表示簇头节点距离BS节点的平均距离，按照网络模型可以得到dtoBS>d0，因此采用多路径衰减模型。

4.总结

本文设计了特定情况下的基于分簇的时间同步算法，基于单跳的分簇时间同步算法CTSA，算法将分簇的思想引入时间同步算法中，可以均衡网络中节点的能量消耗，而且减少跳数，减少能量消耗。并通过理论验证证明了该算法的正确性和优越性。

参考文献：

[1]李善仓，张克旺.无线传感器网络原理与应用[M].机械工业出版社，2008.

[2]卿利，朱清新，王明文.异构传感器网络的分布式能量有效成簇算法[N].软件学报，2006，17（3）：481-489.