浙江工业大学硕士学位论文 无线传感器网络洪泛时间同步的研究和改进 作者姓名：范波杰 指导教师：胡同森教授 左伍衡副教授 浙江工业大学计算机科学与技术学院 20 1O 年4 月 7g 3639 D i s s e l r t a t i o nS u b m i “e dt oZ h e j i a n gU n i V e r s i 坶o f 1 k c h n o l o g y f o rt h eD e g r e eo fM a s t e r AR E S E A R C HA N DI M P R o V E 剐咂N To FF L o o D I N G T ES Y N C H R o N I Z A T I o NP R o T o C o L F o R W I R E L ES SS E N S o RN E T W o R K S C a n d i d a t e ：F a nB o j i e A d 啊s o r ：P r 0 H uT 0 n g - s e n A s s o c i a t eP r o Z u oW u h e n g C o l l e g eo fC o m p u t e r S c i e n c ea n d r e c h n o l o g y Z h e j i a n gU n i V e r s i 坶o f1 e c h n o l o g y A p r i l2 0 1 0 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名髓浪勘 日期：劢埠期矽日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囱。 ( 请在以上相应方框内打“ ) 作者签名珑浓丧，) 导师签名：匍蚺1 武亭 日日 矽7 月月年年 勿O 弦 溉 期期j 日 浙江工业大学硕士学位论文 无线传感器网络洪泛时间同步的研究和改进 摘要 无线传感器网络是集信息采集、信息传输、信息处理于一体的综合智能信息系统，具 有广阔的应用前景，是目前非常活跃的一个领域。时间同步作为无线传感器网络的基础构 件之一，不仅是无线传感器网络各种应用正常运行的必要条件，并且同步精度直接决定了 其他服务的质量。但由于无线自组网特有的属性和设计要求，传统的时间同步技术如N T P ( N e t w o r kT i m eP r o t o c 0 1 ) 和G P S ( G l o b a lP o s i t i o nS y s t e m ) 授时因复杂度、能量及尺寸等 因素无法应用在传感器网络中，这使无线传感器网络时间同步的研究工作遇到了很多新的 挑战，于是无线传感器网络中的时间同步技术就成为一个新的研究热点。 本文是围绕无线传感器网络时间同步算法展开研究的。我们通过分析几种具有代表性 的时间同步协议，发现现存的协议在单跳网络中已经具有很强的工程实用性，能够满足大 多数场合的需要。但是，在多跳的环境中，由于要构建一定的拓扑结构，所以导致报文开 销过大，网络的健壮性和扩展性不好。因此我们通过对洪泛时间同步协议( F l o o d i n gT i m e S y n c h r o n i z a t i o nP r o t o c o l ，F T S P ) 的分析提出了自己的改进算法：优化的洪泛时间同步协议 ( o p t i m i z e d F T S P ) 。在这个协议中我们主要做了两方面工作： 1 通过分析时间同步数据包的洪泛过程，我们把多点中继集引入了洪泛时间同步协 议，大大减少了洪泛节点的数目，消除了大量冗余数据包。 2 我们发现时间同步阶段和路由阶段有很多重复的报文发送现象，通过把时间同步 与路由过程结合起来，利用路由阶段的信息来进一步减少了报文发送量。 最后，我们通过仿真验证了这种改进算法的可行性：有效减少洪泛节点的数量和整个 时间同步过程中的报文发送量，当进行多次时间同步周期时，这种算法的性能表现更好。 在本文的最后，对全文做了总结。 关键字：无线传感器网络，时间同步，洪泛，多点中继 浙江工业大学硕士学位论文 AR E S E A R C HA N D 姗R o V E T 讧E N To F F L o o D 矾G T 玎ES Y N C H R o N I Z A T I o NP R o T o C o LF o R 嘲L E S SS E N S o RN E T W o R K S A B S T R A C T W i r e l e s ss e n s o rn e t w o r ki sas y n t h e t i c i n t e l l i g e n ti n f o r m a t i o ns y s t e mw h i c hi n c l u d e s i m o m a t i o n c o l l e c t i o n ，i n f o m a t i o nt 啪s m i s s i o na I l di b r m a t i o n p r o c e s s i n g I t h a sw i l d 印p l i c a t i o np r o s p e c ta I l di ti sah o tf i e l d T i m es y n c h r o l l i z a t i o ni sa 如n ( 1 锄e n t a lc o m p o n e n to f 、i r e l e s ss e n s o rn e 铆o r k sa 1 1 di ti si m p o r t a n tf o ro t h e ra p p l i c a t i o n sa 1 1 ds e r v i c e s H o w e v e r ，t h e c o m p l e x i t y ，e n e r g yc o s ta n ds i z ec o n n i c t sb e t 、v e e nt r a d i t i o n a la l g o r i t I l I l ls u c ha SN T Pa 1 1 dG P S p r o h i b i t t h e i ru s ei nW S N T h i si n t r o d u c e m a n yn e wc h a l l e n g e s，s od e v e l o p i n gt i m e s y l l c h r o n i z a t i o nm e t h o d ss u i 讪l ef o rw i r e l e s ss e n s o rn 咖o r k sh a V ea t t r a c t e d 谢d ea t t e m i o n T h i sa n i c l eb a S e so nt h es t u d yo ft i m es y n c l l r o n i z a t i o n a l g o r i t l l l T lf o r 谢r e l e s ss e n s o r n e 铆o r k B ya n a l y z i n gs e V e r a l 锣p i c a lt i m es y n c l l r o n i z a t i o np r o t o c o l s ，、ef m dt h e s ep r o t o c o l sc a J l s a t i s 黟m o s tn e e d si ns i n g l e h o pn e t w o r k B u tt l l e yc a u s et o om u c ho v e r h e a di nm u l t i - h o p s n e t w o r kf o rc o n s t m c t i n gt o p 0 1 0 9 i c a ls t m c t u r ea n dt h en e 撕o r k se x p a I l s i b i l 时i sn o tg o o d ，s oi s t 1 1 er o b u s t n e s s S ow ep r o p o s e dan e wa l g o r i t h I l l ：t h eo p t i m i z e dn 0 0 d i n gt i m eS y n c h r o n i z a t i o n p r o t o c o l ，i t b a S e so nt h e s t u d y i n go ft h en o o d i n gt i m eS y n c h r o n i z a t i o np r o t o c 0 1 I nt K s p r o t o c o l ，em a i n l yt w 0a S p e c t s ： 1 B y a 1 1 a l y z i n gt h et i m es y n c m o I l i z a t i o np a c k e t si l ln o o d i n gp r o c e s s ，w ei n t r o d u c ea m u l t i p o i mr e l a ys e t I tg r e a t l yr e d u c e st ：h em l m b e ro fn o o d i l l gn o d e s ，e l i m i n a t i n gal a r g e 肌m b e r o fr e d u n d a n td a t ap a c k e t s 2 W 色f 0 u n dt h a tm e r ea r eal o to fd u p l i c a t ep a c k e t si nt i n l es y n c h r o 血z a t i o np h a S ea n dt 1 1 e r o u t i n gp h a s e ，s ow ec o m b i n et h et 、阳p h a S e st o 如n h e rr e d u c et h e 锄o u n to fp a c k e t st os e n d F i n a l l y ，w ec o n f i n n e dt h a tt 1 1 ea l g o r i t h mc a ne 行e c t i V e l yr e d u c e 。t h em l m b e ro fn o o d i n g n o d e sa 1 1 dt h et i m es y I l c h r o n i z a t i o np a c k e t st 1 1 r o u 曲as i m u l a t i o n A n d 、他e nw ed om 觚yt i m e