面向煤矿井下WSN低功耗双向时间同步算法研究与实现*

崔丽珍,员曼曼,李 璋,赫佳星

(内蒙古科技大学信息工程学院,内蒙古 包头 014010)



面向煤矿井下WSN低功耗双向时间同步算法研究与实现*

崔丽珍*,员曼曼,李 璋,赫佳星

(内蒙古科技大学信息工程学院,内蒙古 包头 014010)

针对传统时间同步算法通过交换较多数据包来获取同步精度而导致能耗过大的现象,结合煤矿井下网络结构的特殊性,在分析双向成对同步机制和单向广播同步机制基础上,利用广播传输特性将2种机制有效结合起来,提出一种基于簇状结构的主被动式低功耗双向时间同步算法。实验表明,基于簇状结构的主被动式同步方式可有效解决传统双向报文交互频繁的问题,在误差允许范围内达到减少消息开销和平衡整个网络能量损耗的目的。

煤矿井下;时间同步;无线传感器网络;低功耗;分簇

我国是产煤大国,煤炭工业是关系国家经济命脉的重要基础产业,但由于煤矿井下环境恶劣,地质条件复杂多样,随着煤矿开采的不断延深和开采强度的增大,矿难等灾害还是屡屡发生[1],因此作为煤矿安全生产最重要保障之一的煤矿监控系统日益受到重视。

无线传感器网络WSN(Wireless Sensor Network)作为一种新兴低功耗、低数据、低成本、短距离无线技术已成为物联网应用中的关键。时间同步技术作为WSN支撑技术之一在煤矿井下的应用日益广泛[2]。在WSN分布式系统中要完成数据融合、功率管理、传输调度、TDMA定时、测距定位等应用时,都需要保证网络中节点时钟同步。而煤矿巷道一般深处地下几百米到几十千米,导致无法收到地面上广为应用的GPS(Global Positioning System)以及其他基础时间服务信号,从而需要网络本身可提供一定精度的时间同步服务。因此WSN时间同步技术在煤矿井下的应用受到较大关注。

目前,WSN时间同步技术已成为国内外学者研究的热点之一[3],将现有WSN时间同步协议划分为集中式算法和分布式算法两类。

集中式同步算法包括:基于发送者的同步机制,典型算法有DMTS(Delay Measurement Time Synchronization)算法和FTSP(The Flooding Time Synchronization Protocol)算法;基于发送者-接受者的同步机制,典型算法有TPSN(Timing-sync Procol for Sensor Networks)算法;基于接受者-接受者的同步机制,典型算法有RBS(Referenced Broadcast Synchronization)算法。

分布式同步算法包括:利用观察脉冲信号,通过调整脉冲信号发射间隔以达到与周围节点保持同步的萤火虫同步算法[4];利用随机矩阵方程来解决同步问题的ATS(Average Time Sync)算法[5];通过利用邻居节点信息的交互,使整个网络达到同一状态的一致性同步算法[6]。

集中式算法虽然不能够适应网络拓扑的变化,但算法收敛性强,同步精度高。因此本文采用集中式算法。通过对集中式算法协议的分析和研究得出:①利用无线传输广播特性来降低同步能耗;②利用双向报文交换来提高同步精度。

煤矿井下通信环境有巷道和工作面等区域划分。巷道环境较为狭长而工作面环境面积较大且环境复杂多变[7],因此研究井下节点在不同环境中的部署情况,提出一种面向煤矿井下的低功耗双向时间同步算法,使节点在保持较低能耗的同时保证同步精度,具有一定的科研意义和使用价值。

1 双向时间同步算法

双向时间同步算法TPSN[7](Timing-sync Protocol for Sensor Networks)是由加州大学网络和嵌入式实验室Saurabh Ganeriwal等人提出的。TPSN算法采用发送端-接收端同步SRS(Sender-Receiver Synchronization)模型,利用双向报文交换实现两节点间时间同步。

图1 SRS时钟同步模型

(1)

(2)

Ui

(3)

Vi

(4)

(5)

(6)

由式(5)、式(6)可知,当只进行一次信息交换时,TPSN时钟相偏估计也是指数模型和高斯模型下的最大似然估计式,如式(7)、式(8)所示:

(7)

(8)

2 低功耗双向时间同步CRTS算法

TPSN算法采用发送者-接受者同步机制,通过MAC层时间戳技术消除访问时间带来的同步误差从而提高同步精度,但为保证两节点间时钟相偏小于某个门限值,需频繁运用TPSN算法来进行报文的双向交互[8]。在WSN中,数据通信是系统最重要的操作之一,但所需能量远大于数据处理所需能量[9]。

因此本文针对煤矿井下WSN中节点在巷道和工作面的特殊分布情况,研究一种可适用于井下节点分布的时间同步算法CRTS。针对煤矿井下节点分布在巷道且需进行持续循环多跳时间同步的情况,构建基于TPSN算法的新型主动式时间同步多跳模型;针对煤矿井下工作面环境的节点,由于工作面是属于较大范围空间,人和机器等设备在工作面环境中进行作业,因此在井下工作面环境布设传感器网络是属于密集型大范围的传感器网络。针对分布在工作面的节点,算法分为网络成簇阶段和同步阶段。在网络成簇阶段中,利用自适应分簇拓扑算法选举簇头以均衡网络中节点所消耗的能量;在同步阶段中,根据簇状结构分为簇间同步和簇内同步。簇间同步采用本文提出的新型多跳模型进行主动式时间同步;簇内同步采用单向广播机制与双向报文交换相结合的算法进行被动式时间同步,在误差允许范围内对能耗方面进行进一步的研究与改进。

2.1 网络成簇阶段

针对井下工作面环境的特点,采用一种自适应的分簇拓扑算法。LEACH协议是比较成熟且常用的分簇路由协议[10],以选举形式产生簇首,可均衡网络中的能耗,是一种为无线传感器网络设计的低功耗路由协议。

①簇头选举。设置阈值T(n),每个节点产生一个0～1的随机数,如果该数值小于阈值T(n),则该节点在本轮循环中成为簇头。在本轮循环中当选过簇头的节点会把阈值T(n)设置为0以避免该节点再次成为簇头,而未当选簇头的节点将以T(n)为概率当选。T(n)随着当选过簇头节点数目的增加而增大,同时节点产生小于T(n)随机数的概率也增大,使节点当选簇头的概率增加[11]。T(n)可表示为:

(9)

其中,P为一轮中簇头在所有节点中所占百分比;r为所完成循环次数;rmod(1/P)为本轮循环中成为簇头节点的个数;Gr为本轮循环中未成为簇头节点的集合;n为网络中节点数目。

节点当选簇头以后,发布消息告知其他节点自己成为簇头节点。

②子节点收集。簇头节点确定后,需建立以时间基准节点为根的广度优先生成树拓扑结构。根据节点自身获得级别与周围同级别邻居节点之间报文交互情况进行拓扑建立。

选取时间基准节点并设置其层次号为0,其余节点均为无穷大并由根节点广播拓扑建立报文。若簇头节点接到该报文,则设置自己层次号为1并由该簇头节点继续广播拓扑建立报文,其他节点收到报文后将报文中的层次号提取出来加1作为自己的层次号;如果已有层次号且层次号比消息包中的层次号小,则将该节点的节点号加入到自己的下层邻居节点列表中。重复这个过程直到所有节点都被赋予层次号,完成网络拓扑结构的建立。

2.2 同步阶段

2.2.1 主被动时间同步算法

①主动式同步。煤矿井下巷道部分狭长,节点采用链状拓扑结构进行布放,在此基础上建立新型多跳时间同步模型进行双向报文交互。簇间时间同步过程采用如图2所示的主动式时间同步算法。

节点N-1称为节点N的时间源邻居节点,节点N称为节点N-1的时间目标邻居节点。算法具体实现过程如图3所示。

节点首先发送同步请求报文,被其所在簇的簇头节点接收并回复同步应答报文,目标邻居节点收到同步应答后计算它和时间源邻居节点之间的时钟偏差(注意:节点之前发送的同步请求报文和当前收到的同步应答报文构成一对双向报文)并返回给时间源邻居节点,此时的时钟偏差如式(10)所示:

(10)

时间源邻居节点收到时钟偏差后,据此修改自己的时间以达到与目标邻居节点之间的直接同步,并同时触发向其时间源邻居节点发送同步请求,最终使得在同步路径上的所有节点均达到同步。

②被动式同步。对于煤矿井下工作面环境的节点,针对节点众多且分布具有随机性的特点,将广播传输特性与双向报文交换算法结合达到利用较低功耗同步较多节点的目的。在该阶段,根节点从自己的下层邻居节点列表中随机选取一个子节点作为响应节点并广播同步消息。单个节点广播范围内只有一个簇首节点执行双向报文交互过程,其他节点通过监听簇头节点同步过程来进行被动同步。图4为被动式时间同步算法模型的单跳示例。整个单跳网络同步机制可看作是发送者-接受者和接受者-接受者的混合机制[12]。从能耗角度看,被动式时间同步算法在一个单跳网络中传输的报文数为仅为3个。

图3 主动式时间同步算法流程

图4 被动式时间同步算法模型

节点O为时间基准节点,节点A,B,和C处于节点O的一跳范围内并可与其进行同步,这里假设各节点之间都可进行直接通信。具体过程如下:

①同步请求

②同步应答

③同步数据收集

④同步校正

(11)

(12)

图5 分簇网络拓扑结构

将算法扩展至多跳,通过网络成簇阶段对网络进行分簇,构建一个如图5所示的分级分簇树形拓扑结构[13]。每个节点及其子节点形成一个可直接进行单跳算法的连通区域。在该拓扑结构中,对于簇头节点和应答节点之间进行主动式时间同步算法达到瞬时簇间同步;簇成员节点间利用被动式时间同步算法达到簇内同步,完成整个网络节点的时间同步校正。

在实际应用中可根据网络需求对节点进行部署,将大功率节点作为簇首进行分布从而覆盖更大的通信范围并减少簇首个数,对网络中其他节点可实现更为有效的低功耗运行。

选用簇头节点间进行主动式时间同步,其他簇内节点采用被动式监听同步的方式,相对于传统双向报文算法可大大降低通信开销,尤其是子节点数目越多时通信开销越明显[14],解决了对于大规模节点分布,逐个进行双向报文交互耗能巨大的问题。

2.2.2 计算复杂度分析

主要从算法的低通信开销来定性分析算法的计算复杂度。首先算法采用主被动式同步方式,根据井下环境来设定选取不同的同步算法。这相对于传统的TPSN算法,减少通信开销。其次,CRTS算法利用广播传输特性,使得处于工作面的一些簇成员节点,只需通过报文监听来获取偏差达到与簇头节点同步,而不必通过报文交换来计算偏差,这样,就不需要全网每个节点通过计算偏差来保持同步,以此来减少某些节点不必要的能量开销。因此,同步阶段中CRTS算法相对于TPSN算法,在计算复杂度上具有优势,在同步误差允许的范围内,减少了节点的通信开销。

2.2.3 同步开销分析

通过对算法的复杂度分析,CRTS算法在保持了双向同步算法特征的基础上大大减少了通信开销,在每个同步周期中只需2n个同步报文交互,n为拓扑结构中非子节点数目。CRTS算法与其他同步算法在每个同步周期所需要的报文交互数如表1所示。m为除去参考节点外所需要同步节点的个数。

表1 不同算法同步报文开销对比

由表1可知,以上算法在网路中报文交互数目随节点数目的增加而增加,而CRTS算法由于采用被动监听方式获取偏差信息,因此通信开销和计算复杂度要小于其他算法,在保证同步精度的前提下有效的降低了通信开销。

3 算法实现及结果分析

3.1 实验环境

为了真实地反映客观物理环境,本文对时间同步能耗和精度的测试通过实验完成。实验采用实验室自主研制的传感器节点。该节点处理器芯片采用以AVR为核心的微处理器ATmega128L;RF射频芯片采用CC2420射频芯片,支持MAC层时间戳技术;采用TinyOS操作系统。

实验平台由9个节点组成,每个节点均采用频率为7.3728MHz晶振。对于涉及计数器的精确操作,本实验未使用TinyOS提供的通用计数器TimerMilliC,而采用ATmega128L的3号计数器HplAtm128Timer3C并对其晶振进行1024分频作为时钟源,从而获得分辨率为2.5μs的时钟源。

为验证CRTS算法的性能,实验基于本文提出的层次拓扑结构,在实验平台上实现了TPSN和CRTS算法,并对这2种算法获得的测试数据进行处理和分析比对。在模拟井下工作面环境进行了实验,选取8 m×2.4 m的区域布放9个节点,如图6所示。根节点布放在测试区域的中央,其余节点随机分布。为获取算法的测试数据具有可比性,实验均在相同的环境和平台中获得。

图6 模拟井下实验设置

网络中使用可覆盖全网的查询节点和监听节点,查询节点以固定周期向全网广播同步查询报文,网络中的同步节点收到查询报文后,用本地时间记录下接收到查询报文的时刻并立刻发送响应报文,此时监听节点监听到各节点的响应报文并把这些报文上传到上位机,上位机对数据进行处理和分析。

3.2 实验结果分析

使用如图6所示的拓扑结构进行同步精度测试。实验中同步报文周期为5 s,分别对一跳、两跳节点与时间源节点的同步误差进行统计分析,每隔一个同步周期进行一次统计,测试所得误差以同步周期个数为单位进行计算,获得如图7所示的同步误差曲线图。

为查看子节点与时间源节点的同步情况,实验选取拓扑结构中的子节点进行同步实验。从实验结果可以看出:各跳节点同步误差基本一致,同步误差随同步周期的增加变化不明显,各跳平均误差均在40 μs以内,误差呈交错波动形式,在与全网节点同步后同步误差波动减小且稳定,可见该算法具有较好的收敛性,子节点可与时间源节点较好的保持同步。

对比CRTS算法与传统TPSN算法的精度差异,分别给出了2种算法在相同实验条件下的同步误差分布对比曲线图,如图8所示。由实验结果可看出:2种算法的同步精度相差不大,平均误差在30 μs～50 μs之间。相对于TPSN算法,CRTS算法在满足一定精度的前提下,大大减少了消息交换开销,节约了能量,表现在数值上如表1所示。

图7 不同跳数同步误差曲线图

图8 不同算法同步误差分布

在建立网络拓扑后,不同算法在每个同步周期需发送同步报文个数随网络中节点数目的增加而增加[15]。由表2可知,TPSN算法的精度略高于CRTS算法,但根据同步开销分析可知CRTS算法在通信开销上要明显低于TPSN算法。

表2 不同算法同步精度对比 单位:ms

4 结论

时间同步作为WSN应用的一项关键技术,对其算法的设计、实现和应用都非常重要[16]。对于煤矿井下WSN的应用,研究同步误差范围内如何降低通信开销更为重要。本文针对这种情况并结合煤矿井下环境的特殊性提出一种面向煤矿井下的主被动式时间同步算法CRTS。对于分布在巷道的节点,构建新型多跳模型并进行主动式同步。对于分布在工作面环境的节点,通过建立分级分簇树形拓扑网络结构,对簇头节点采用主动式同步实现簇间同步;簇内节点通过监听簇头节点的时间同步信息来进行被动式同步实现簇内同步,最终实现全网节点同步。与TPSN算法相比,该算法在满足一定精度的前提下大大降低了通信开销。通过WSN实验平台测试,结果表明与传统TPSN算法相比该算法更适用于煤矿井下,且利用较少能耗达到所需同步精度。本文的研究对于煤矿井下时间同步具有一定的理论指导意义和实际应用价值。

[1] 崔丽珍,于洤. 基于ZigBee自适应通信在矿井瓦斯监控系统中的设计与实现[J]. 矿业安全与环保,2012,39(2):19-21.

[2]崔丽珍,李蕾,员曼曼,等. 基于核函数法及粒子滤波的煤矿井下定位算法研究[J]. 传感技术学报,2013,26(12):1728-1733.

[3]Akyildiz I F,Su W,Sankarasubramaniam Y,et al. A Survey on Sensor Networks[J]. Communications Magazine,IEEE,2002,40(8):102-114.

[4]Werner-Allen G,Tewari G,Patel A,et al. Firefly-Inspired Sensor Network Synchronicity with Realistic Radio Effects[C]//Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems. New York,NY,USA:ACM,2005:142-153.

[5]Schenato L,Gamba G. A Distributed Consensus Protocol for Clock Synchronization in Wireless Sensor Network[C]//Decision and Control,2007 46th IEEE Conference on. IEEE. New Orleans,LA,USA:IEEE,2007:2289-2294.

[6]Maggs M K,O’Keefe S G,Thiel D V. Consensus Clock Synchroni-zation for Wireless Sensor Networks[J]. Sensors Journal,IEEE,2012,12(6):2269-2277.

[7]王玉秀,黄剑,石欣,等. 基于分簇的低功耗多跳无线传感器网络层次时间同步算法[J]. 计算机应用,2013,33(2):369-373.

[8]Jeske D R. On Maximum-Likelihood Estimation of Clock Offset[J]. IEEE Transactions on Communications,2005,53(1):53-54.

[9]王越,万洪. 一种节能的无线传感器网络多跳自适应时间同步算法[J]. 传感技术学报,2013,26(11):1557-1563.

[10]吴宝明,李声飞. 基于最优线性拟合的WSN时间同步算法研究[J]. 传感技术学报,2010,23(12):1787-1791.

[11]张伟华,李腊元,张留敏,等. 无线传感器网络LEACH协议能耗均衡改进[J]. 传感技术学报,2009,22(11):1918-1922.

[12]关新平,张晓静,刘志新. 基于分簇的低功耗多跳WSN时间同步机制[J]. 计算机工程,2010,36(9):111-113.

[13]江禹生,樊宇. 无线传感器网络双向成对时间同步优化方法[J]. 计算机工程,2013,123(5):126-131.

[14]吴成伟,黄文君. 无线传感器网络比对广播时间同步算法[J]. 传感技术学报,2009,22(12):1789-1794.

[15]汪付强,曾鹏,于海斌. 一种低开销的双向时间同步算法[J]. 仪器仪表学报,2011,32(6):1357-1363.

[16]孙德云,沈杰,刘海涛. 基于扩散机制的无线传感器网络时间同步协议[J]. 通信学报,2009,29(11):40-49.

崔丽珍(1968-),女,1990年毕业于北京交通大学通信工程专业。内蒙古科技大学信息工程学院副院长,硕士生导师,教授。研究方向为宽带无线通信、无线传感器网络。承担科研课题7项,发表科研论文30余篇。近年来专注于煤矿井下通信及监测系统的研究与开发,lizhencui@163.com;

员曼曼(1988-),女,内蒙古包头人,硕士,研究方向为煤矿井下无线传感器网络时间同步算法研究与实现。

ResearchandImplementationofLowPowerTwo-WayWSNTimeSynchronizationAlgorithmforCoalMine*

CUILizhen*,YUANManman,LIZhang,HEJiaxing

(School of Information Engineering,Inner Mongolia University of Science and Technology,Baotou Inner Mongolia 014010,China)

The energy consumption problem that exists in traditional time synchronization algorithm because of exchanging more packets to obtain synchronization accuracy. According to the special network structure in underground coal mine,on the basis of the analysis of bidirectional pair and one-way broadcast synchronization mechanism,combine both synchronization mechanisms with the transmission characteristics of radio effectively,and a two-way synchronization algorithm based on clusters structure which at the characteristics of the passive and low power is proposed. Experiments show that,synchronization algorithm which been proposed can solve the problems of exchanging packets frequently effectively,in the range of allowable error can reduce message consumption and balance the network energy.

coal mine;time synchronization;wireless sensor network(WSN);Low power consumption;clustering

项目来源:包头市科技发展项目(2012Z1006-5)

2014-04-16修改日期:2014-07-15

10.3969/j.issn.1004-1699.2014.09.018

TD76

:A

:1004-1699(2014)09-1253-07