基于振荡器模型的多跳无线传感器网络时间同步问题研究论文

1、项目名称 基 于 振 荡 器 模 型 的 多 跳 无 线 传 感 器 网 络 时 间 同 步 问 题 研 究项目负责人（签名）_所在学校（盖章）_“研究类别”含义： 基础研究：指为获得关于现象和可观察事实的基本原理及新知识而进行的实验性和理论性工作，它不以任何专门或特定的应用或使用为目的。 应用研究：指为获得新知识而进行的创造性的研究，它主要是针对某一特定的实际目的或目标。 试验发展：指利用从科学研究和实际经验中所获得的现有知识、生产新材料、新产品、新装置、新流程和新方法，或对现有的材料、产品、装置、流程、方法进行本质性的改进而进行的系统性工作。 推广应用、科技服务：指与研究与发展活动相关并有

2、助于科学技术知识的产生、传播和应用的活动。研究项目项目名称基于振荡器模型的多跳无线传感器网络时间同步问题研究研究类别1.基础研究 2.应用研究 3.试验发展 4.推广应用 5.科技服务依托的一级学科 计算机科学技术成果形式专利、论文起止时间 2014 年 5 月到 2016 年 4 月经费申请总额 1 万元其他经费及其来源无项目负责人姓 名职 称工作单位电子邮箱项除目负组责主人要外成五员名姓名职称学位专业工作单位承担任务本人签名项目负责人近三年来承担的研究项目项目名称项目来源起止年月排名进展基于普适计算的物联网中间件的研究学科带头人学术攀登项目2013年9月-2016年6月3在研海运集装箱码头

3、调度方法的研究校科研基金2009年5月-2011年4月1结题程序设计类课程游戏化教学的深度实践-以数据结构课程为例校教改课题2013年12月-2015年12月1在研大宗商品供应链企业间知识共享博弈研究校科研基金2013年7月-2015年6月1在研一种无信标结点无线传感器网络定位算法研究宁波市自然科学基金2013年8月-2015年6月4在研基于PKI的Zigbee网络安全方案研究宁波市自然科学基金2013年7月-2015年4月4在研项目负责人为第一署名人的代表性成果成果名称成果来源获得时间排名等级基于耦合振荡器模型的WSN时间同步算法-以ZigBee网络以例论文2014年4月1鼓励奖Resear

4、ch on Application of Linkage Learning Mechanism of "Player-Learner" 论文2014年4月1鼓励奖Application on the partner selection of the concrete enterprise based on GAAA论文2012年4月1鼓励奖1 本项目研究意义及国内外同类研究工作现状（附主要参考文献及出处）：研究意义： 无线传感器网络是联系物理世界和计算机系统的桥梁，对物理世界的观测必须建立在统一的时间标度上，因此相对与通常的分布式系统，无线传感器网络对时间同步的需求尤为强烈

5、，可以说时间同步是无线传感器网络的一项支撑技术。其在无线传感器网络的数据融合、MAC协议、测距定位等研究领域有着非常重要的应用。 2002年8月，Jeremy Elson和Kay Römer提出和阐述无线传感器网络时间同步的研究课题后1。不断有新的时间同步协议被提出。这些时间同步协议基于节点间的包含时间信息的报文交换，力图提高时戳信息的准确性来提高时间同步的精度；力图利用无线广播特性来降低同步功耗。目前，单跳无线传感器网络的时间同步协议已经很成熟，同步误差在Mica2平台上已经达到几到十几微秒的量级，同步功耗也较低，能够满足大多数应用场合的需要。然而，当这些时间同步协议被扩展到多跳网

6、络时，经典的无线传感器网络时间同步算法通常是首先按照节点之间的通信连接关系建立起一定的网络拓扑结构，在该拓扑结构上，按照时间同步协议的约定，未同步节点和所选定的已同步节点之间通过交换含时间信息的同步报文，从而间接地实现与时间基准节点之间的同步。这种同步机制的特点在于：除时间基准节点的邻居节点外，其余点并不能直接和时间基准节点同步。传统时间同步协议在体系结构上的限制：节点不能直接和时间基准节点同步而只能和与时间基准节点存在同步误差的节点进行同步，因此必将出现节点的同步误差随着其离时间基准节点跳距(Hop Distance)的增加而增加的现象，即出现了同步误差的累积。理论分析和一些实际实验表明：在

7、这些传统的时间同步协议下，即使在最好的情况下，节点的同步误差至少与其跳距的平方根成正2。随着无线传感器网络的发展，同步误差累积问题将越来越严重。一方面由于传感器节点体积的不断减小使得节点的单跳传播距离可能减小，另一方面由于网络规模的不断扩大使得网络直径不断增加，这两个因素均会导致平均节点跳距的增加，使得同步误差的累积现象更加严重。这对大规模无线传感器网络的应用提出了挑战3。传统无线传感器网络时间同步协议还面临着可扩展性问题的挑战。它力图建立起网络拓扑结构从而把网络中的所有节点有机组织起来，当网络规模较小时，这是完全可行的，但当网络规模较大时，由于无线传输的不稳定性以及节点工作的动态性，只有频繁

8、地进行拓扑更新才能跟踪拓扑的变化，一方面这对于本已非常有限的网络带宽和节点电能供应来说是不可想象的，另一方面把网络拓扑维护的繁重工作交给时间同步协议来解决也并不合适。由于存在的上述问题，近些年来，研究者们开始寻找新的时间同步的思路和方法。而借鉴了萤火虫、心肌细胞等生物同步现象的基于线性振荡器模型的无线传感器网络时间同步方法逐渐引起了研究者们的注意。这种方法采用完全分布式的形式，节点之间仅通过简单的脉冲进行耦合，因此具有较高的健壮性和可扩展性。可以预见，该方法的研究将把无线传感器网络时间同步推入一个新的研究阶段。然而，传统的线性振荡器模型并不能直接应用在无线传感器网络中。例如，传统的线性振荡器模

9、型假设不存在传输和处理延迟，这显然在无线传感器网络中是不现实的；再如，传统的线性振荡器模型假设任何节点间都存在着一定程度的耦合，而在多跳的无线传感网络中，这也是不现实的。本项目在无线传感器网络的背景下，旨在解决延迟、多跳拓扑因素对线性振荡器模型所带来的关键理论挑战，以及相关的工程实现问题，推进线性振荡器模型在无线传感器网络中的实际应用，并为最终解决大规模无线传感器网络的时间同步问题打下坚实的理论和工程基础。通过本项目的实施，首先，可以从理论上解决线性振荡器模型在无线传感器网络时间同步应用上的理论缺陷问题，并为生物、物理等领域的同步问题的研究提供有益的理论借鉴；其次，项目研究中建立的仿真模型和实

10、验平台，可以为同领域在其他方向的研究提供有力的支持；最后，研制基于线性振荡器模型的轻量级无线传感器网络时间同步硬件设备，可以直接推进本项目研究成果的实用化。国内外同类研究工作现状：1、经典无线传感器网络时间同步算法 对于无线传感器网络时间同步的研究已经开展，研究者们提出了许多方法对该问题进行求解，这主要包括DMTS4，TPSN5，LTS6，RBS，FTSP7。等。下面对这些方法做简要的介绍。 无线网络同步最易于想到的方法为：发送者在同步报文中嵌入其本地时间，在接收到该报文后，接收者立即把自己的本地时间设置为嵌在该报文中的时间。但这种方法没有考虑到报文的传输延迟。而DMTS（Delay Meas

11、urement Time Synchronization）协议在此方法的基础上，进一步考虑了报文的传输延迟，接收者测量报文的传输延迟，并将本地时间设置为报文传输延迟与发送时刻之和。DMTS同步协议没有考虑传播延迟、编解码时间的影响，并且没有对时钟飘移进行补偿，同步精度不高。但通过单个的广播报文，一次就可以同步广播域内的所有节点，并且计算非常简单，是一种非常简单有效的同步协议。 DMTS同步协议简单，但同步精度不高，UCLA的NESL实验室的S.Ganeriwal认为：传统的发送者-接收者同步协议的同步精度较低的根源在于：基于单向报文所估算出的报文传播延迟不够精确。如果采用双向报文，基于报文传输

12、的对称性，有可能精确地计算出报文的传输延迟，因此能获得高的同步精度。为此，他引入了NTP协议中的双向报文交换协议，提出了TPSN（Timing-sync Protocol for Sensor Networks）协议。TPSN将NTP时间同步方法引入无线传感器网络，相对DMTS获得了较高的精度，但是其计算较为复杂，功耗较大。并且同步精度受到报文的传输延迟的影响，同时如果报文的双向传输不对称，同步精度也会受到影响。 LTS（Lightweight Tree-based Synchronization）同步算法是一种与TPSN非常类似的算法。无线传感器网络通常只具有非常有限的计算资源，但是其并不要

13、求非常高的时间同步精度。针对无线传感器网络的这一特点，LTS侧重于降低时间同步的复杂度，在有限的计算代价下获得合理的同步精度。LTS算法与TPSN协议的区别在于，LTS算法中节点只与自己的父节点进行同步，其同步次数是路径长度的线性函数，同时精度也随路径的长度线性降低，即在降低计算代价的同时降低了同步精度。 无线传感器网络的数据传播介质是无线信道，能否利用无线信道的广播特性设计相关的时间同步算法呢？RBS（Reference Broadcast Synchronization）算法就是利用无线信道广播特性进行同步的算法。与TPSN协议不同，RBS协议不是去同步报文的收发双方，而是去同步报文的多个

14、接收者，也即接收者-接收者同步机制。RBS算法认为：发送者-接收者同步机制的同步关键路径为从发送方到接收方。关键路径过长，导致传输延迟不确定性的增加，因此同步精度不可能很高。接收者-接收者同步机制的关键路径大为缩短，完全排除了发送时间和访问时间的影响。实验表明，RBS在Mica2上达到了31.7微秒的同步精度。 作为典型的发送者-接收者同步算法，TPSN认为：若能精确地估计出报文传输延迟，这种方法将能够取得很高的精度。然而仅根据单个报文的传输很难准确地估计出传输延迟，因此，TPSN采用了双向报文来估计传输延迟，在Mica2上达到了17.3微秒的同步精度。 FTSP（Flooding Time

15、Synchronization Protocol）属于发送者-接收者协议，因此发送者基于MAC层时间戳技术在报文中嵌入发送时刻，而接收者也在MAC层记录下接收时刻。和其它发送者-接收者同步协议不同，在FTSP协议中，发送者在发送一个报文时连续标记了多个时间戳。根据这多个时间戳，接收者可以估计出中断等待时间。接收者根据估计出的中断等待时间信息以及静态设定的编解码时间对接收时间戳进行补偿，从而得到更精确的同步点。如同RBS协议一样，FTSP协议基于速率恒定模型对节点间时钟飘移进行了补偿，补偿方法仍然采用了最小二乘法。FTSP协议具有同步精度高，协议非常健壮，工程实用性很强等优点。 国内研究者对时间

16、同步算法也进行了深入的研究。包括： 王汝传等8对RBS算法进行了改进，提出了一种改进的时间同步算法IRBS(Improved References Broadcast Synchronization)。该方法对每个接收节点的时间值利用最小平方线性回归方法进行估计，分析出同一节点的系统时钟误差并进行补偿。通过仿真表明该方法算法能够缩小时间误差，有效提高时间同步的精度。刘海涛等9提出将扩散机制引入FTSP算法，提出了一种基于扩散机制的无线传感器网络时间同步协议DTSP。该协议同时利用了容错、时分等策略，在保证同步精度前提下提高了协议的健壮性。 徐朝农等10针对TPSN的非同步期内由于节点间存在时钟

17、飘移所造成的失步情况，提出在非同步期内对时钟飘移进行估计和补偿。即估算出了直接相邻节点间的晶振频率偏差，然后通过迭代公式计算得到与时间基准节点间的晶振频率偏差，并进行补偿。应用此方法可设计的高精度、强可扩展性、低能耗的时间同步协议。实验表明，单跳平均同步误差在Mica2上小于10微秒。 王福豹等11-13提出一种嵌入路由报头的低功耗时间同步算法，该算法将时间同步集成到消息的路由报头中，通过在发送和接收端在路由消息上加盖精确的时间戳实现同步，从而消除了周期性时间同步消息的传输,减小了能量开销。 近些年提出的算法还包括，皇甫伟14等的网时间同步算法FTS，吴成伟等15的比对广播时间同步算法PBTS

18、，周新莲等16的基于簇型的多跳时间同步算法CBTS，齐望东等17的轻量级安全时间同步协议LiteST，屈玉贵等18的能量高效的时间同步算法EETS。2、基于耦合振荡器同步模型如前文所述，无线传感器网络经典时间同步算法，无法应对同步误差累积和可扩展性的问题。近些年来，研究者们开始寻找新的时间同步的思路和方法。而萤火虫同步这一古老的生物同步现象逐渐又被大家重视起来。互相临近的萤火虫能够调整为同步闪烁，这是一种非常奇妙的生物现象。早在上世纪初，很多学者就在Science上发文，对此现象进行了讨论。Smith 1935年的文章19对东南亚的萤火虫同步闪烁现象进行了生动详细的描述，文中描述了在泰国的湄公

19、河延绵十几英里的河岸边的树上，几乎每篇树叶上都栖息着近乎完美同步闪烁的萤火虫。这一现象引起了学者们的广泛关注，科学家们纷纷对此展开研究。早在1915年Blair就观察到了这一现象并试图对这一现象进行解释20，他把萤火虫类比为充电电池每次闪烁暂时性的将电池的电能耗光，而电池经过一段时间的充电之后又可以进行下一次的闪烁。同时，每次闪烁都会对其它电池的放电产生影响，最终使得所有的萤火虫同步的闪烁。Richmond提出了类似的假设，如果某个萤火虫将要闪烁的时候看到了其他萤火虫的闪烁，它将会提前闪烁21。Buck夫妇就是早期研究这一现象的著名学者，他们早期合著的一系列文章22-24对此现象以及其他学者对

20、此现象的解释进行了归纳总结，但这些解释和总结均只停留在文字描述的层面上，并没有建立数学模型。而在文22发表50年之后，John Buck又再次撰文25对50年中相关研究进行了总结，并给出了Phase-Advance和Phase-Delay两种同步模型。在Phase-Advance模型中，他定义了“late sensitivity window”，即接近萤火虫闪烁时刻的一个时间段，他认为如果萤火虫在“late sensitivity window”中受到光刺激（即其它萤火虫的闪烁），将立即闪烁。尽管Phase-Advance模型对萤火虫的同步闪烁现象给出了一个较好的解释，但是萤火虫之间的相互作用

21、（通常称为“耦合”）别限制在“late sensitivity window”中。Peskin将耦合作用拓展到萤火虫闪烁周期的任意时刻。在他1975出版的书中26，Peskin针对心肌细胞同步跳动提出了一种线性振荡器模型。他把互同步系统建模成许多互相耦合的相同的振荡器的集合，每个振荡器由一个状态变量描述，满足：其中和是振荡器的固有属性。当时，振荡器激发，并回到状态，同时会出现与其它振荡器之间的电耦合，从而把其它振荡器的状态提升一个很小的增量，称为耦合强度。而正是这种耦合的作用，使得振荡器的状态趋于相同，最终达到同时放电状态。根据上述模型，Peskin提出了两点假设：1)对任意初始状态，系统总能

22、达到同步状态；2)即使每个振荡器结构不同，系统最终也会达到同步。但是当他试图证明他的假设的时候，他发现当时并没有现成的数学工具可以求解这类系统。因此，他退而证明两个相同结构的振荡器具有同步收敛性这一最简单的情况，同时他还问题限制在很小的和，在此最简单的情况下，Peskin证明了两个相同结构的耦合振荡器具有同步收敛性。1990年，Mirollo和Strogatz在Peskin模型的基础上提出一种更加一般化的线性振荡器模型（后简称为M&S模型）27，在此模型中，振荡器也使用状态变量来描述，的变化服从函数，其中是一个0,1到0,1上的光滑单调递增上凸函数，是相位变量且满足(是同步周期)。Mi

23、rollo和Strogatz从理论上证明了此模型下多个耦合振荡器系统在几乎所有的初始情况下都能够达到同步。纵观线性振荡器同步模型的研究，研究的主体从生物学家到数学家、物流学家进而转移到计算机学家。今年来，将这一机制应用于计算机网络、神经网络的研究又使得该同步模型的研究成为热点。M&S模型虽然很好的解释了萤火虫同步现象，但是其很多理想的假设在实际应用中难以保证，因此将其直接用于无线网络的同步还存在不少问题。首先，这些模型都是基于即时耦合的，即脉冲的传播是即时的、没有延迟的，而无线通信传输延迟是无法避免的。Ernst等28, 29对具有延迟的两个振荡器之间的同步进行了数学分析，并对具有延迟

24、的多振荡器系统进行了仿真。他们得出的结论是，如果采用负耦合（inhibitory couping，即），系统仍然能够达到同步。其次，计算机网络，特别是无线网络通常是多跳网络，因此M&S模型的全互联的网络拓扑也限制了模型应用范围。Dennis和Wang30证明了M&S模型在只允许邻居通信的前提下仍然能够达到同步。相关工作的综述可以参考Simeome等的文章31。最后，无线传感器网络的节点通常采用廉价的单片机作为其处理器，因此无法处理M&S模型的非线性的状态函数。Werner-Allen等针对这一情况使用了一阶泰勒展开进行了近似。我们在该方向已经提出了一种采用线性状态函数的

25、非漏电线性振荡器模型，并证明了该模型在几乎所有的条件下都能达到同步。为进一步的深入研究打下了一定的先期研究基础。1Elson J, Romer K. Wireless Sensor Networks: A New Regime for Time Synchronization J. SIGCOMM Comput Commun Rev, 2003, 33(1): 149-154.2Elson J, Girod L, Estrin D. Fine-grained Network Time Synchronization Using Reference Broadcasts. J. ACM SIGO

26、PS Operating Systems Review, 2002, 36(SI): 147-163.3徐朝农, 徐勇军, 李晓维. 无线传感器网络时间同步新技术 J. 计算机研究与发展, 2008, 45(1): 138-145.4Ping S. Delay Measurement Time Synchronization for Wireless Sensor Networks. IRB-TR-03-013 R: Intel Research, 2003.5Saurabh G, Ram K, Mani B S. Timing-sync Protocol for Sensor Network

27、s. Proceedings of the 1st international conference on Embedded networked sensor systems, Los Angeles, California, USA C. ACM, 2003: 138-149.6Jana Van G, Jan R. Lightweight time synchronization for sensor networks. Proceedings of the 2nd ACM international conference on Wireless sensor networks and ap

28、plications, San Diego, CA, USA C. ACM, 2003: 11-19.7Mikl, S M, Ti, et al. The Flooding Time Synchronization Protocol. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, MD, USA C. ACM, 2004: 138-149.8李文锋, 王汝传, 孙力娟. 基于RBS的无线传感器网络时间同步算法 J. 通信学报, 2008, 29(6

29、): 82-86.9孙德云, 沈杰, 刘海涛. 基于扩散机制的无线传感器网络时间同步协议 J. 通信学报, 2008, 29(11): 41-49.10徐朝农, 赵磊, 徐勇军, et al. 无线传感器网络时间同步协议的改进策略 J. 计算机学报, 2007, 30(4): 514-523.11任丰原, 董思颖, 何滔, et al. 基于锁相环的时间同步机制与算法 J. 软件学报, 2007, 18(2): 372-380.12李连, 孙利民, 樊孝忠. 无线传感器网络基于概率分发的时间同步协议 J. 北京邮电大学学报, 2008, 31(5): 57-60.13王喆, 王福豹, 陈振华.

30、 嵌入路由报头的无线传感器网络时间同步算法 J. 计算机工程, 2009, 35(1): 132-134.14皇甫伟, 周新运, 陈灿峰. 基于多层抽样反馈的传感器网络时间同步算法 J. 通信学报, 2009, 30(3): 59-65.15吴成伟, 黄文君. 无线传感器网络比对广播时间同步算法 J. 传感技术学报, 2009, 22(12): 1789-1794.16周新莲, 黄力. 无线传感器网络中多跳时间同步算法的研究 J. 计算机工程与应用, 2009, 45(27): 102-104.17尹香兰, 齐望东. LiteST:一种无线传感器网络轻量级安全时间同步协议 J. 通信学报, 2

31、009, 30(4): 74-85.18杨春明, 屈玉贵. 无线传感器网络中能量高效的时间同步算法 J. 中国科学技术大学学报, 2009, 39(5): 532-539.19Smith H M. Synchronous Flashing of Fireflies J. Science, 1935, 82(2120): 151-152.20Blair K G. Luminous Insects J. Nature, 1915, 96(2406): 411-415.21Richmond C A. Fireflies Flashing in Unison J. Science, 1930, 71(

32、1847): 537-538.22Buck J B. Synchronous Rhythmic Flashing of Fireflies J. The Quarterly Review of Biology, 1938, 13(3): 301-314.23Buck J, Buck E. Biology of Synchronous Flashing of Fireflies J. Nature, 1966, 211(5049): 562-564.24Buck J, Buck E. Mechanism of Rhythmic Synchronous Flashing of Fireflies

33、J. Science, 1968, 159(3821): 1319-1327.25Buck J. Synchronous Rhythmic Flashing of Fireflies. II J. The Quarterly Review of Biology, 1988, 63(3): 265-289.26Peskin C S. Self-Synchronization of the Cardiac Pacemaker M. Mathematical Aspects of Heart Physiology. New York; New York University. 1975: 268-2

34、78.27Mirollo R E, Strogatz S H. Synchronization of Pulse-Coupled Biological Oscillators J. SIAM Journal on Applied Mathematics, 1990, 50(6): 1645-1662.28Ernst U, Pawelzik K, Geisel T. Synchronization Induced by Temporal Delays in Pulse-Coupled Oscillators J. Physical Review Letters, 1995, 74(9): 157

35、0-1573.29Ernst U, Pawelzik K, Geisel T. Delay-induced multistable synchronization of biological oscillators J. Physical Review E, 1998, 57(2): 2150-2162.30Dennis L, Wang I J. Decentralized Synchronization Protocols with Nearest Neighbor Communication. Proceedings of the 2nd international conference

36、on Embedded networked sensor systems, Baltimore, MD, USA C. ACM, 2004: 62-68.31Simeone O, Spagnolini U, Bar-Ness Y, et al. Distributed Synchronization in Wireless Networks J. IEEE Signal Processing Magazine, 2008, 25(5): 81-97.2 主要研究内容、目标、方案和进度及拟解决的关键问题：研究目标：本项目在真实的无线传感器网络环境下，分析传统振荡器模型存在的缺点，建立适合无线传感

37、器网络的基于脉冲耦合振荡器的时间同步算法，其特点为：充分考虑了无线传感器网络的计算能力弱、频率存在差异、通信延迟不确定、网络拓扑变动因素，具有计算量小、可扩展性好、鲁棒性强；将该算法在测试平台上进行实现，根据测试平台中各个参数对同步的影响程度的差异，对协议进行优化已获得最佳的精度。脉冲耦合振荡器是目前对自然界生物同步现象的最有效的模型，其算法存储量和计算量小，可扩展性好，非常适合于无线传感网络，可能是未来的发展方向。然而，无线传感网络存在的传输和处理延迟、多跳网络拓扑这两个因素在脉冲耦合振荡器模型中并没有被考虑，因此仍存在不足。该项目在已有的脉冲耦合振荡器模型的基础上，考虑上述两个因素，建立基

38、于线性振荡器的时间同步模型。本项目在真实的无线传感器网络环境下，分析传统振荡器模型存在的缺点，建立适合无线传感器网络的基于线性振荡器的时间同步算法。其特点为：充分考虑了无线传感器网络的计算能力弱、频率存在差异、通信延迟不确定、网络拓扑变动因素，具有计算量小、可扩展性好、鲁棒性强；将该算法在测试平台上进行实现，根据测试平台中各个参数对同步的影响程度的差异，对协议进行优化已获得最佳的精度。 研究内容： 1、建立一种基于线性振荡器模型的时间同步模型 基于线性振荡器模型的无线传感网络时间同步方法是无线传感器网络时间同步研究的新方法。其通信模型、通信方式与传统方法有着较大的差别，因此首先建立起一种基于线

39、性振荡器模型的无线传感器网络时间同步模型是本项目的首要研究内容，也是本项目后续研究的基础。2、在传统模型中引入传播和处理延迟因素，研究其对模型同步的影响传统的线性振荡器模型一个最重要的假设为不存在报文的传播和处理延迟。然而，传播和处理延迟普遍地存在于无线通信中，该因素不仅是影响时间同步精度的重要因素，而且可能会影响振荡器的同步收敛。因此，在线性振荡器模型中加入报文的传播和处理延迟因素，是基于线性振荡器模型的时间同步算法在无线传感器网络中得到应用的先决条件。 3、在传统模型中引入多跳网络拓扑因素，研究其对模型同步的影响传统的线性振荡器模型一个最重要的假设为单跳网络，换句话说，网络中的任一个节点都

40、可以和其他节点直接通信。现有的基于多跳网络的线性振荡器同步模型，也是在假设节点间耦合强度趋向于0的假设下，证明其收敛性的。显然，这个假设因素不仅是影响时间同步精度的重要因素，而且可能会影响在多跳网络条件下振荡器的收敛性。因此，在线性振荡器模型中多跳网络因素是基于线性振荡器模型的时间同步算法得到应用的重要条件。4、在传统模型中引入频率差异因素，研究其对模型同步的影响众所周知，无线传感器网络节点的计数器受晶体振荡器驱动，受到制造工艺和工作环境的影响 (温度, 电压等), 不同节点的晶振频率总存在偏差, 而晶体振荡频率偏差又使得节点间的计时速率不一致, 即使节点在某一时刻实现了同步, 也会出现时间偏

41、移。然而振荡器模型并没有考虑频率对模型同步的影响，本项目在传统振荡器的基础上，分析频率差异对模型同步的影响，建立一种频率互异的线性振荡器同步模型。5、设计基于线性振荡器模型的时间同步算法，并在测试平台上实现依据所研究出的线性振荡器模型，设计适用于传感器网络的基于线性振荡器的多跳时间同步算法，并且在测试平台上进行实现；根据模型中各个参数对同步的影响程度的差异，对协议进行优化以获得最佳的精度。关键问题： 1、分别考虑延迟和多跳网络拓扑条件下，线性振荡器模型的同步性证明提出一种适用于无线传感器网络的线性振荡器模型并证明其同步性是本项目的首要任务，也是设计同步算法的基础。然而，正如前文所述，现有的线性

42、振荡器模型并不适用于无线传感器网络，因此需要针对无线传感器网络的特性，分别考虑延迟和多跳网络拓扑两个因素，设计相应的振荡器动态特性函数，并讨论模型能够达到同步所需要满足的条件，再次基础上对其同步性进行证明。这是本项目要解决的首要问题。2、综合考虑延迟和多跳网络拓扑的条件下，线性振荡器模型的同步性证明延迟和多跳网络拓扑是影响传感器网络时间同步的两个重要因素，上一个研究点分别考虑延迟和多跳网络拓扑因素下，也即假设这两个条件不互相冲突，线性振荡器模型的同步性。然而，延迟和多跳网络拓扑这两个因素的联合作用，会对线性振荡器模型的同步性产生何种影响，这是本项目需要重点解决的问题。3、研究在频率差异情况下，

43、线性振荡器模型的同步性证明经典的Peskin模型26的第二个假设“即使每个振荡器并不相同，系统最终也会达到同步”也是针对频率的差异而进行的猜想。然而频率的差异对耦合振荡器模型却没有真正考虑过。正由于振荡器的频率之间存在差异，因此无法保证同步了的两个节点任意时刻相位相同。针对这一情况，需要研究在频率差异情况下，对线性振荡器模型的同步性证明。4、晶振频率模型和数据传输延迟模型的建立当前，对时间同步算法仿真的难度在于没有建立无线传感器网络节点上晶振以及节点间数据传输延迟的模型。由于无线传感器网络通常采用廉价的晶振，因此存在一定的时钟漂移，要建立准确的晶振频率模型就必须对其时钟漂移进行准确的测量，测量

44、方法以及误差处理方法都是要研究的重要问题。无线传感器网络节点之间的通信，存在着发送、接收、编码、解码、传播等一系列延迟，对这些延迟进行准确的测量和统计，是建立晶振频率模型和数据传输延迟模型的必要工作。5、探索硬件脉冲耦合的媒介和实现方式基于物理脉冲耦合来对传感器网络进行同步最大的困难在于寻找一种合适的脉冲耦合的媒介。光耦合方式在光线较强时（如白天）非常容易受到环境的干扰，而采用射频电波进行耦合，可能会受到正常通信电波的干扰。具体的媒质方式选择还需要进行大量的实验来确定。另外，研究如何将这种硬件装置与WSN节点连接，设计灵活可靠的接口，并且将这种周期性的耦合脉冲转化为节点的时钟值，也是本项目的难

45、度之一。研究方案：首先建立线性振荡器模型，基于此模型分别研究延迟和网络拓扑对模型的影响，并对模型的同步性进行证明。同时，设计和开发仿真程序，对模型进行验证和实验。在完成理论分析和仿真实验之后，在测试平台上进行实验，测量同步误差并进行分析。下面分别介绍每一部分拟采取的技术方案：1、建立线性振荡器模型1999年Peskin在M&S模型的基础上提出了耦合振荡器模型。即对M&S模型中的，令，且，可以得到。对此微分方程两边进行积分可得。令为周期，为相位变量，则可得Peskin模型 前期工作采用了正耦合即耦合强度，并在此前提下证明了系统的同步性。但是有研究发现，对于M&S模型，正耦

46、合在存在延迟的情况下系统无法达到稳定的同步状态，而在负耦合的情况下，某些初始条件可以达到同步状态。因此，考虑将负耦合引入模型，建立基于负耦合的非漏电线性振荡器模型。然后使用正耦合的同步证明方法，推导模型达到同步需要满足的条件。并证明两个振荡器组成的系统能够达到同步，具体利用M&S模型中所提出的“激发映射”和“回归映射”方法，证明回归映射函数总是趋向于0或者1。最后，在两个振荡器系统同步证明的基础上推导任意多个振荡器组成的系统的同步条件，并证明同步条件的可满足性。 2、 分析延迟对同步的影响研究延迟对线性振荡器模型同步的影响，首先要考虑延迟的线性振荡器模型，即加入传播延迟参数。假设耦合脉

47、冲经过时间后到达接收者，则对于两个振荡器的同步问题来说，的引入加大了分析的难度。这是由于在加入了后，使我们在分析回归映射（即连续两次某振荡器激发的时候另一个振荡器的相位）的时候必须考虑振荡器初始相位与的大小关系。我们的设想是：在、和这三个区间里分别讨论，而在每个区间内根据耦合强度和相位的大小再次划分出子区间。区间划分好之后，分别对其进行编号，然后分析每一种区间的回归映射函数，并根据回归映射函数判断其下一个状态将会转移到哪个子区间中去。在得到所有的子区间和转换关系之后，根据这种关系构建状态转换图，即有限状态自动机。如果这个有限状态机中每个状态都能转化到最终的同步状态，则系统的同步性得到了证明。对

48、于多个振荡器，由于状态太多，因此使用上述自动机的方法进行理论分析难度过高。拟采取仿真的方式对模型的同步性进行研究。即对振荡器的个数和周期、耦合强度、传输延迟等参数在一定范围内分别仿真，每次仿真随机产生振荡器的初始状态，然后按照模型的参数进行演化，同时绘制振荡器状态随时间变化的状态图，通过每轮所有节点时间值的均方差以及状态图来分析系统的同步情况。3、分析网络拓扑对同步的影响研究网络拓扑对同步的影响，首先需要在模型中体现网络拓扑关系，令为与节点相邻的节点组成的集合，则节点的耦合方式为：,其中，为振荡器和的连通性矩阵（如果振荡器和连通，否则），为耦合强度。即振荡器的相位为1时激发，同时振荡器的相位增

49、加一个增量，如果增加之后超过1，则其也被激发。增量为振荡器耦合强度与连通性矩阵对应元素的乘积。要证明上述情况下系统能够达到同步的一种思路是，构造相位的一个微分方程，将某节点与相邻节点的相位差作为参数，并证明耦合的过程将导致相位差趋向于某常量。4、在测试平台上实现基于上述模型的无线传感器网路时间同步算法由于时间同步的实时性要求高，因此必须建立起准确的时钟误差机制。由于测试平台的节点的主处理器Atmega128L的外部中断引脚具有“自中断”功能，即当外部中断输入引脚被配置为中断输入时，仍可以由软件强制在该引脚上输出任意电平，并且当输出电平满足中断触发条件时，还会触发该外部中断。因此，将所有节点的中

50、断输入引脚连接在一起，并让其中一个节点在需要测量时钟偏移时主动输出一个触发脉冲，则该触发脉冲将会同时触发这两个节点的外部中断。通过在外部中断服务程序中记录下节点此时的本地时刻并通过串口转以太网模块送入测试平台的数据库中保存，用作事后分析。通过这种机制，可以准确的获知节点间的相对时钟偏移。实现的主要工作是将理论模型中的各种参数映射到无线传感器网络的实际环境中去。首先是相位参数，由于无线传感器网络节点通常采用计数器作为时钟，因此必须将相位由区间离散化到整数区间上；其次是耦合参数，考虑使用节点间的射频信号或者数据包的传输作为模型中的耦合；最后还要考虑延迟和网络拓扑的表示。另外，由实际算法设计所引入的新参数也需要对原模型进行必要的修正以及同步性证明，以保证算法的可靠性。研究进度：1、2014.5.1-2014.7.31 全面调研国内WSN研究最新进展，深入调研现有国内外WSN环境下时间同步方法的研究情况，整理出国内外WSN时间同步方面的研究报告。2、2014.8.1-2014.10.31 研究基于线性振荡器模型的网络时间同步机制，构建耦合振荡器时钟同步模型。3、2014.11.1-2015.1.31 研究频率差异对同步的影响，构建基于频率互异的线性振