（计算机应用技术专业论文）无线传感器网络中若干问题的研究和实现.pdf

中国科学技术大学硕士论文无线传感器网络中若干问题的研究和实现 摘要 无线传感器网络作为当今信息领域新的研究热点，涉及多学科交叉的研究领 域，有非常多的关键技术有待发现，本文仅研究时间同步和二层架构，并实现 个选路协议。 在无线传感器网络中，时间同步是十分必要的。有限的电池能量，存储以及 带宽限制等传感器固有的特性的存在，导致传统的时间同步算法不适合无线传感 器网络。本文阐述了时间同步问题和时间同步的必要性，介绍了一些传感器网络 的时间同步算法，并深入研究了在考虑节点移动的情况下，利用节点的移动来传 递时间信息的思想，模拟证明我们的算法性能良好。 在基于二层架构的无线传感器网络中，有效的簇头选举算法非常重要。一些 现有的算法随机性很大，而另外一些只考虑了同构的情况，实用价值不大。因此， 本文提出了一种基于负载平衡的算法。该算法中簇头计算每个簇内成员预期做簇 头后的生命期，然后把生命期最大的两个簇员选作新的簇头和新的候选簇头。通 过模拟，我们将该算法与随机选取算法的实现效果进行比较，发现此算法延长了 网络生命期。 当前的传感器网络的组建绝大多数都是采取类似蜂窝网、带有基站( 或类似 设备) 的方式，但在一些比较特殊的场合，比如战场上，这样的组网方式会很受 限制，因为建立基站设备会耗费相当的时间和人力物力，而基站一旦被毁网络就 会瘫痪。因此，在中科院方向性课题、移动自组网路由协议项目的支持下，本文 将尝试着以移动自组网( m o b i l ea dh o cn e t w o r k ) 的方式组建一个无线传感器 网络。 本文最后描述了在带有传感器的军用端机的硬件平台上一个移动自组网选 路协议的实现，以及如何以此路由协议为组网软件主体建立一个无线移动自组 网。在实验测试中，我们建立了以四个端机作为结点的传感器移动自组网，用串 口发送数据来模拟传感器采集数据。实验结果表明，各结点之间可以实现多跳通 信，网络拓扑变化时路由协议会迅速重新选择可用路由，并且路由协议能够满足 军用环境下无数据传输时保持安静的要求。 关键词：无线传感器网络，时间同步，簇头选举，移动自组网，路由协议 中国科学技术大学硕士论文 无线传感器网络中若干问题的研究和实现 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 k s ，a san e wa n dp o p u l a ra r e ao fr e s e a r c hi n i n f o r m a t i o nt e c h n o l o g y ，i n v o l v i n gi n t e r d i s c i p l i n a r yf i e l do fs t u d y ，a l a r g en u m b e ro fk e yt e c h n o l o g ie sn e e dt ob ef o u n da tt h i sti m e a n dt h e p a p e ro n l ym a k e sr e s e a r c ho nt i m es y n c h r o n i z a t i o n ，t w o t i e r e ds t r u c t u r e a n di m p l e m e n t sar o u t i n gp r o t o c o l 。 i nw i r e l e s s s e n s o rn e t w o r k s ，t i m es y n c h r o n i z a t i o ni sn e c e s s a r y s o m ei n t r i n s i cp r o p e r t i e so fs e n s o rn e t w o r k s ，s u c ha s1 i m i t e dr e s o u r c e s o fe n e r g y ，s t o r a g e ，c o m p u t a t i o n ，a n db a n d w i d t h ，m a k et r a d i t i o n a lt i m e s y n c h r o n i z a t i o nm e t h o d su n s u i t a b l ef o rw s n t h i sa r t i c l ef o r m u l a t e st h e t i m es y n c h r o n i z a t i o np r o b l e ma n dt h en e e df o rs y n c h r o n i z a t i o ni ns e n s o r n e t w o r k s ，a n da l s oi n t r o d u c e ss o m et i m es y n c h r o n i z a t i o na l g o r i t h m s ，a n d m a k ef u r t h e rr e s e a r c ho nt h ei d e a so f “c a r r yt i m ei n f o r m a t i o nw i t h m o b i l i t yo ft h en o d e s ”w h e nt a k i n gm o b i l i t yi n t oa c c o u n t w h i c hi sp r o v e d t ob eg o o db ys i m u l a t i o n i nt h et w o t i e r e dw i r e l e s ss e n s o rn e t w o r k s ，h o wt od e s i g nam o r e e f f i c i e n td i s t r i b u t e dc l u s t e rh e a de l e c t i o na l g o r i t h mi sac r u c i a l p r o b l e m i na 1 1a l g o r i t h m sp r o p o s e db e f o r e ，s o m ed e p e n do nr a n d o mg r e a t l y ， a n do t h e r so n l yt a k eh o m o g e n e o u si n t oa c c o u n t o nt h eb a s iso ft h e m ，w e p r o p o s ean e wp r a c t i c a la p p r o a c h ，i nw h i c ht h eo l dc l u s t e rh e a d ，a st o t h ep o w e ri n f o r m a t i o n ，c h o o s e st h et w on o d e sw h i c hs u p p l yt h ec l u s t e rw i t h t h em a x i m u ml i f e t i m ei ft h e ya r ee l e c t e da st h en e wc l u s t e rh e a da n dt h e n e wo n e sa s s i s t a n t t h es i m u l a t i o np e r f o r m a n c er e s u l t sd e m o n s t r a t et h e e f f i c i e n c yo ft h em e t h o dc o m p a r i n gw i t ht h er a n d o mc h o o s i n ga l g o r i t h mi n m u c hl o n g e rn e t w o r kl i f e t i m e r e c e n ti f ，m o s ts e n s o rn e t w o r kw a sc o n s t r u c t e di nc e ll u l a rf o r m ，t h a t i s ，t h e r ea r es o m eb a s es t a t i o n s ( o ro t h e rd e v i c e sp l a y i n gt h es a m er o l e ) i nt h en e t w o r k b u ti ns o m es i t u a t i o n s ，s u c ha st h ew a r ，c e ll u l a rn e t w o r k i i 中国科学技术大学硕士论文 无线传感器网络中若干问题的研究和实现 w i l lb ev e r yr e s t r i c t e d b e c a u s eb a s es t a t i o nd e v i c e sc o n s u m em u c ht i m e a n dm o n e y ，a n do n c et h eb a s es t a ti o nh a db e e nd e s t r o y e d ，t h ew h o len e t w o r k c a n tw o r ka n ym o r e t h i sp a p e rw i l lt r yt oe s t a b l i s has e n s o rn e t w o r k i nt h em o b i l ea d h o cm o d e a tl a s t ，t h i sp a p e rr e a l i z e dam a n e tr o u t i n gp r o t o c o l ，a n db a s e do n t h ep r o t o c o la n dt h eh a r d w a r ep l a t f o r mo fak i n do fm i l i t a r ys i n g l e b o a r d m a c h i n ew i t hs e n s o r ，w ee s t a b l i s h e dam o b i l ea d h o cn e t w o r k w et e s t e d o u rr o u t i n gp r o t o c o lo nan e t w o r ko ff o u rn o d e s t h et e s t i n gr e s u l tt u r n e d o u tt h a tn o d e sc a nc o m m u n i c a t ew i t he a c ho t h e rt h r o u g hm u l t i h o p s ，a n d w h e nt h en e t w o r kt o p o l o g yc h a n g e d ，o u rr o u t i n gp r o t o c o lc a nf i n dan e w r o u t eq u i c k l y ( a sl o n ga sav a li dr o u t ee x is t s ) t h ep r o t o c o lk e e p ss i l e n t w h e nn od a t an e e dt r a n s l a ti n g k e y w o r d ：w i r e l e s ss e n s o r sn e t w o r k ，t i m es y n c h r o n i z a t i o n ，c l u s t e rh e a d e l e c t i o n ，m a n e t ，r o u t i n gp r o t o c o l i i i 中国科学技术大学硕士论文无线传感器网络中若干问题的研究和实现 第一章引言 1 1 无线传感器网络概述 微电子技术、计算技术和无线通讯等技术的进步，推动了低功耗多功能传感 器的快速发展，使其在微小体积内能够集成信息采集、数据处理和无线通讯等多 种功能。无线传感器网络就是由部署在监测区域内大量的廉价微型传感器节点 组成，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发 送给观察者。如果说i n t e r n e t 构成了逻辑上的信息世界，改变了人与人之间的 沟通方式，那么无线传感器网络就是将逻辑上的信息世界与客观上的物理世界融 合在一起，改变了人类与自然界的交互方式。人们可以通过传感器网络直接感知 客观世界，从而极大地扩展现有网络的功能和人类认识世界的能力。 传感器网络的应用前景非常广阔，能够广泛应用于军事、环境监测和预报、 健康护理、智能家居、建筑物状态监控、复杂机械监控、城市交通、空间探索、 大型车间和仓库管理，以及机场、大型工业园区的安全监测等领域。随着传感器 网络的深入研究和广泛应用，传感器网络将逐渐深入人类生活的各个领域。 1 2 无线传感器网络特点 无线自组网( m o b i l ea d h o cn e t w o r k ) 是一个由几十到上百个节点组成的、 采用无线通信方式的、动态组网的多跳的移动性对等网络。其目的是通过动态路 由和移动管理技术传输具有服务质量要求的多媒体信息流。通常节点具有持续的 能量供给。 传感器网络虽然与无线自组网有相似之处，但同时也存在如下差别： 第一，传感器网络是集成了监测、控制以及无线通信的网络系统，节点数目 更为庞大( 上千甚至上万) ，节点分布更为密集。 第二，传感器节点由电池供电，节点能量有限。由于节点数量多，而且无线 传感器网络往往应用于人烟荒芜的地方或人们难以直接操作的地方，因此更换传 感器节点电池是不现实的。这决定了传感器节点生命和网络寿命的有限性。 中国科学技术大学硕士论文无线传感器网络中若干问题的研究和实现 第三，网络拓扑易变化。由于节点能量有限，节点易出故障，导致无线传感 器网络拓扑信息变化快速。 第四，节点体积限制、能量有限决定了节点只能具备有限的计算存储能力和 短距离通信能力。 无线传感器网络与传统的无线自组网有着不同的设计目标，后者在高度移动 的环境中通过优化路由和资源管理策略最大化带宽的利用率，同时为用户提供一 定的服务质量保证在无线传感器网络中，除了少数节点需要移动以外，大部分节 点都是静止的因为它们通常运行在人无法接近的恶劣甚至危险的远程环境中， 能源无法替代，设计有效的策略延长网络的生命周期成为无线传感器网络的核心 问题当然，从理论上讲，太阳能电池能持久地补给能源，但工程实践中生产这种 微型化的电池还有相当的难度在无线传感器网络的研究初期，人们一度认为成 熟的i n t e r n e t 技术加上a d h o c 路由机制对传感器网络的设计是足够充分的，但 深入的研究表明：传感器网络有着与传统网络明显不同的技术要求前者以数据 为中心，后者以传输数据为目的为了适应广泛的应用程序，传统网络的设计遵循 着“端到端”的边缘论思想，强调将一切与功能相关的处理都放在网络的端系统 上，中间节点仅仅负责数据分组的转发，对于传感器网络，这未必是一种合理的选 择一些为自组织的a d - h o c 网络设计的协议和算法未必适合传感器网络的特点 和应用的要求节点标识( 如地址等) 的作用在传感器网络中就显得不是十分重要， 因为应用程序不怎么关心单节点上的信息：中间节点上与具体应用相关的数据处 理、融合和缓存也显得很有必要在密集性的传感器网络中，相邻节点间的距离非 常短，低功耗的多跳通信模式节省功耗，同时增加了通信的隐蔽性，也避免了长距 离的无线通信易受外界噪声干扰的影响这些独特的要求和制约因素为传感器网 络的研究提出了新的技术问题 1 3 本文的工作和目标 本文以当前的无线传感器网络的研究为背景，深入研究了如何利用节点的移 动来传递时间信息。接着提出了一种在二层架构下的能量有效和负载平衡的簇头 选举算法，目的是为了尽可能的延长网络的生命期。最后，我t r i l l 以一种连接有 传感器的端机结点为硬件平台，通过在其上实现一个自适应的选路协议，建立一 2 中国科学技术大学硕士论文 无线传感器网络中若干问题的研究和实现 个无需基站、结点相互之间可以进行多跳通信的移动自组网。在这个网络中，负 责采集数据的网络结点与控制中心( 可以看作一个特殊的端机结点) 之间的通信 可以经由其它结点转发，二者不一定直接相连。当某个结点移动或者宕机时，路 由协议在必要的时候会重新选择路由以在新的拓扑结构满足通信的需要。路由协 议将有一定的可扩展性，其性能不受网络结点个数的限制。 中国科学技术大学硕士论文无线传感器网络中若干问题的研究和实现 第二章背景知识和相关技术介绍 2 1 时间同步技术 2 1 1 问题简介 在分布式系统中，不同的节点都有自己的本地时间。由于不同的节点的晶体 振荡器频率存在偏差，以及温度变化和电磁波干扰等，即使在某个时刻所有节点 都达到时间同步，它们的时间也会逐渐出现偏差，而分布式系统的系统工作需要 节点间的时间同步，因此时间同步机制是分布式系统基础框架的个关键机制。 分布式时间同步涉及物理时间和逻辑时间两个不同的概念。物理时钟用来表示人 类社会使用的绝对时间：逻辑时钟表达事件发生的顺序关系，是一个相对概念。 分布式系统通常需要一个表示整个系统时间的全局时间，全局时间根据需要可以 是物理时间或逻辑时间。 时间同步机制在传统网络中已经得到广泛应用，如网络时间协议n t p ( n e t w o r kt i m ep r o t o c 0 1 ) 是i n t e m e t 采用的时间同步协议，g p s 、无线测距等技 术也用来提供网络的全局时间同步。在传感器网络应用中同样需要时间同步机 制，例如时间同步能够用于形成分布式波束系统、构成t d m a 调度机制和多传 感器节点的数据融合，在节点间时间同步的基础上，用时间序列的目标位置检测 可以估计目标的运行速度和方向，通过测量声音的传播时间能够确定节点到声源 的距离或声源的位置。 我们都可以用下面的公式来估计一个时钟的值： c i ( t ) 2 a i ( t ) 书t + b i ( t ) ( 其中a i ( t ) 表示时间频偏，b i ( t ) 表示时间相偏) 同样我们可以用下面的公式来表示两个时钟的相对关系： c ( t ) 2 a 1 2 ( f ) 木c 2 ( f ) + 6 l z ( f ) ( 其中a 1 2 表示相对时间频偏，6 l z 表示相对时 间相偏) 时间同步算法的目的就是求出两个时钟之间的相对漂移和相对偏移，这样就 可以将一个时钟调整到另外一个时钟的步调( p a c e ) 上，而且通过重复的同步训 练，使它们在一段时间内保持一致。 4 中国科学技术大学硕士论文无线传感器网络中若干问题的研究和实现 2 1 2 必要性 n t p ( n e t w o r kt i m ep r o t o c 0 1 ) 协议在i n t e m e t 上已经广泛使用，具有精度高、 鲁棒性好和易扩展等优点，但是它主要依赖的条件在传感器网络中难以满足，例 如n t p 协议应用在已有的有线网络中，假定网络链路失败的概率很小，而传感 器网络中无线链路通信质量受环境影响往往较大，甚至时常失败：n t p 协议的 网络结构相对稳定，便于为不同位置的节点手工配置时间服务器列表，而传感器 网络的拓扑结构动态变化，简单的静态手工配置无法适应这种变化；n t p 协议 中时间基准服务器间的同步无法通过网络自身来实现，需要其他基础设施的协 助，如g p s 系统或无线电广播报时系统，而在传感器网络的有些应用中，无法 取得相应基础设施的支持；n t p 协议需要通过频繁交换消息来不断校准时间频 率偏差带来的误差，并通过复杂的修正算法消除时间同步消息在传输和处理过程 中的非确定因素干扰，c p u 使用、信道监听和占用都不受任何约束，而传感器 网络中节点造价不能太高，节点的微小体积不能安装除本地振荡器和无线通信模 块外更多的用于同步的器件，因此，价格和体积成为传感器网络时间同步的重要 约束。传感器网络中多数节点是无人值守的，仅携带少量有限的能量，即使是进 行侦听通信也会消耗能量，时间同步机制必须考虑能量因素。 现有的时间同步算法往往关注于最小化同步误差来达到最太的同步精 度方面，而较少考虑计算和通信的开销，没有考虑计算机消耗的能量，相应的计 算机性能对传感器节点而言高很多，能量也能够不断得到供给。由于传感器网络 的特点，以及能量、价格和体积方面的约束，使得n t p 、g p s 等现有时间同步 机制不适用于传感器网络，需要修改或重新设计时间同步机制来满足传感器网络 的要求。 2 1 3 考虑因素 设计一种传感器网络的时间同步算法，需要认真考虑如下因素： 1 ) 能量感知：为了减少能量消耗，保持网络时间同步的交换消息数尽量 少，必需的网络通讯和计算负载应该可预知，时间同步机制应该根据网络节点的 能量分布，均匀使用网络节点的能量来达到能量的高效使用。 2 ) 可扩展性：在传感器网络应用中，网络部署的地理范围大小不同，网 中国科学技术大学硕士论文无线传感器网络中若干问题的研究和实现 络内节点密度不同，时间同步机制要能够适应这种网络范围或节点密度的变化。 3 ) 精度：对于一些应用，它们要求较高的精度( 比如微妙级) 。 4 ) 鲁棒性：由于各种原因可能造成传感器节点失效，另外现场环境随时 可能影响无线链路的通信质量，因此要求时间同步机制具有良好的鲁棒性。 5 ) 稳定性：传感器网络在保持连通性的同时，因环境影响以及节点本身 的变化，网络拓扑结构将动态变化，时间同步机制要能够在拓扑结构的动态变化 中保持时间同步的连续性和精度稳定性。 6 ) 收敛性：传感器网络具有动态拓扑结构变化的特点，同时传感器节点 又存在能量约束，这些都要求建立时间同步的时间很短，使节点能够及时知道它 们的时间是否达到同步。 7 ) 成本：g p s 系统能够以纳秒级精度与世界标准时间u t c 保持同步，但 需要配置高成本的接收机，同时在室内、森林或水下等有障碍的环境中无法使 g p s 系统。如果用于军事目的，没有主控权的g p s 系统也是不可依赖的。在传 感器网络中只可能为极少数节点配置g p s 接收机，这些节点为传感器网络提供 基准时间。 2 1 4 主要性能参数 1 ) 最大误差：一组传感器节点之间的最大时间差量，或相对外部标准时间 的最大差量。通常情况下，最大误差随着需要同步的传感器网络范围的增大而增 加。 2 ) 同步期限：节点之间需要一直保持时间同步的时间长度，传感器网络需 要在各种时间长度内保持时间同步，从瞬间同步到伴随网络存在的永久同步。 3 ) 同步范围：需要节点之间时间同步的区域范围，这个范围可以是地理范 围，如以米度量的距离；也可以是逻辑距离，如网络的跳数。 4 ) 可用性：指在范围内的覆盖完整性，有些时间同步机制能够同步区域内 的每个节点，基于网络的机制通常能够同步每个节点，而有些机制对硬件要求高， 仅能同步部分节点，如g p s 系统。 5 ) 效率：达到同步精度所经历的时间以及消耗的能量。需要交换的同步消 息越多，经历的时间越长，消耗的能量越大，同步的效率相对就越低。 6 中国科学技术大学硕士论文无线传感器网络中若干问题的研究和实现 6 ) 代价和体积：时间同步可能需要特定硬件，在传感器网络中需要考虑部 件的价格和体积，这对传感器网络非常重要。 2 1 5 遇到的挑战 节点之间为了达到同步需要交换各种各样的消息，因此节点处理消息时间和 消息传送延迟的不确定性，是对w s n 时间同步问题的最大的挑战。我们可以将 不确定性时间分解为以下几部分： 传送时间：发送节点用来构造和发送时间同步消息所用的时间，包括时间同 步应用程序的系统调用时间、操作系统的上下文切换和内核协议处理时间以及把 消息从主机发送到网络接口的时间。 访问时间：发送节点等待访问网络传输信道的时间，这与底层m a c 协议密 切相关。在基于竞争的m a c 协议如以太网中，发送节点必须得到信道空闲后才 能传输数据，发送过程中产生冲突需要重传。无线局域网8 0 2 1 1 协议r t s c t s 机制要求发送节点在数据传输前交换控制消息，获得对无线传输信道的使用权； t d m a 协议要求发送节点必须得到分配给它的时槽，才能发送数据。 传输延迟：消息离开发送节点后，从发送节点传输到接收节点所经历的时间 间隔。当发送节点和接收节点共享物理介质时，如l a n 或a d - - h o c 无线网络中 的邻居节点，消息传播延迟非常小，仅仅是消息通过介质的物理传播时间。相反， 在广域网中传播延迟往往比较大，包括在路由转发过程中的排队和交换延迟，以 及在各段链路上的传输延迟。 接收时间：从接收节点的网络接口接收到消息到通知主机消息到达事件所用 的时间，这通常是网络接口产生消息接收信号需要的时间。如果接收消息在接收 主机操作系统内核的底层打上时标，如在网络驱动中断程序中处理，接收时间就 不包括系统调用、上下文切换，甚至从网络接口到主机传送所需要的时间。 在消息延迟的四个部分中，对于不同的应用网络，访问延迟往往变化比较大， 广域网的传输延迟抖动也比较大，发送延迟和接收延迟的变化相对较小。如何准 确的估计消息延迟是提高时间同步精度的关键技术。 中国科学技术大学硕士论文 无线传感器网络中若干问题的研究和实现 2 1 6 主要同步算法 2 1 6 1r b s 同步机制 j e l s o n 等人提出的参考广播同步( r b s ) 机$ l j 1 l n 用了无线数据链路层 的广播信道特性，一个节点发送广播消息，接收到广播消息的一组节点通过比较 各自接收到消息的本地时刻，实现它们之间的时间同步。消息延迟中，发送时间 和访问时间依赖于发送节点c p u 和网络的瞬间负荷，所以随时间变化比较大且 难于估计，是时间同步误差非确定因素的最主要部分。而广播消息相对所有接收 节点而言，它的发送时间和访问时间都是相同的。通过比较接收节点之间的时间， 就能够从消息延迟中抵消发送时间和访问时间，从而显著提高局部网络内节点之 间的时间同步精度。 r b s 同步机制通过接收节点对时抵消发送时间和访问时间。发送节点广播 一个信标( b e a c o n ) 分组，广播域中两个节点都能够接收到这个分组。每个接收 几点分别根据自己的本地时间记录接收到信标( b e a c o n ) 分组接收时间。两个接 收时间的差值相当于两个接收节点间的时间差值，其中一个接收节点可以根据这 个时间差值更改它的本地时间，从而达到两个接收节点的时间同步。 r b s 机制中不是通告发送节点的时间值，而是通过广播同步指示分组实现 接收节点间的相对时间同步。b e a c o n 分组本身并不需要携带时标，何时准确地发 送出去也不是非常重要。正式由于无线信道的广播特性，b e a c o n 分组相对所有接 收节点而言同时发送到物理信道上，才能够去除发送时间和访问时间引入的时间 同步误差。r b s 机制通过去这两个主要误差源来提高时间同步的精度。 对于传播时间，r b s 机制只关心各个接收节点之间消息传播时间的差值。 对于r f 信号来说，这种传播时间差值非常小，所以r b s 机制忽略了传播时间带 来的时间偏差。不过，如果使用声音作为信息传输手段，因为声音的传播速度比 较慢，这种传播时间偏差将不能忽略。 分组的接收时间主要由接收节点底层硬件决定。系统时钟能够在分组接收中 断时间时读取，这就去除了接收节点的接收协议处理、上下文切换和网络接口想 主机传送等时间。同样，两个节点的接收时间差值对r b s 机制才具有意义，接 收时间差值相对很小，r b s 机制也忽略了接收时间差值。 影响r b s 机制性能的主要因素包括接收节点间的时钟偏差、接收节点非确 中国科学技术大学硕士论文无线传感器网络中若干问题的研究和实现 定因素和接收节点的个数。为了提高时间同步精度，r b s 机制采用了统计技术， 通过发送节点发送多个消息，获得接收节点之间时间差异的平均值。对于时钟偏 差问题，采用了最小平方的线性回归( 1 e a s ts q u a r e sl i n e a rr e g r e s s i o n ) 方法进行线 性拟合，直线斜率就是两个节点的时钟偏差，直线上的点表示节点间的时间差异。 r b s 机制可以用来构造局部时间，对于需要时间同步但不需要绝对时间同 步的传感器网络应用非常有用。对于两个接收节点，r b s 机制需要3 个发送消 息和4 个接收消息。对于单个广播域内的n 个节点和m 个广播消息，r b s 机制的 复杂度是o ( m n ) 。在实际传感器网络中，发送节点往往也需要时间同步，需要 另外一个节点成为发送节点。用于多跳网络的r b s 机制需要依赖有效的分簇方 法，保证簇之间具有共同节点以便簇间进行时间同步。r b s 机制在多跳网络中 的误差随跳数增加而增加。 传感器网络存在能量约束，为了节省传感器节点的能量，最好尽可能长得 让它们保持在低功耗睡眠状态。基于这种考虑，j e l s o n 提出后同步地思想，就 是通常情况下节点的时间不必同步，只有监测到一个事件发送时，节点才首先用 它的本地时间记录事件发生的时间，然后采用r b s 机制，个“第三方”节点 广播b e a c o n 消息给区域内的所有节点，接收节点利用这个同步消息作为一个瞬 间的时间参考点，同步它们监测到的事件发生时间。 2 1 6 2t p s n 同步机帛0 传感器网络时间同步协议t p s n ( t i m i n g s y n cp r o t o c o lf o rs e n s o rn e t w o r k s ) 2 】类似于传统网络的n t p 时间同步协议，目的是提供传感器网络全网范围内节 点间的时间同步。在网络中有一个于外界通信获取外界时间的节点称为根节点， 根节点可装配如g p s 接收机的复杂硬件部件，并作为整个网络系统的时钟源。 t p s n 协议采用层次型网络结构，首先将所有节点按照层次结构进行分级，然后 每个节点与上一级的一个节点进行时间同步，最终所有节点都与根节点时间同 步。节点对之间的时间同步是基于发送者一接收者的同步机制。 t p s n 协议假设每个传感器节点都有唯一的标志号i d ，节点间的无线通信 链路是双向的，通过双向的消息交换实现节点间的时间同步。t p s n 协议将整个 网络内的所有节点按照层次型结构，如t i n y d b 需要数据融合树，这样整个网络 只需要生成和维护共享的层次结构。t p s n 协议包括两个阶段，第一个阶段生成 9 中国科学技术大学硕士论文 无线传感器网络中若干问题的研究和实现 层次结构，每个节点赋予一个级别，根结点赋予最高级别第0 级，第i 级的节点 至少能够与个第( i 一1 ) 级的节点通信；第二个阶段实现所有树节点的时间同 步，第一级节点同步到根节点，第i 级的节点同步到第( i 1 ) 级的一个节点，最终 所有都同步到根节点，实现整个网络的时间同步。 第一阶段称为层次发现阶段( 1 e v e ld i s c o v e r yp h a s e ) ：在网络部署后，根节点 通过广播级别发现( 1 e v e ld i s c o v e r y ) 分组启动层次发现阶段，级别发现分组包含 发送节点的i d 和级别。根节点的邻居节点收到根结点发送的分组后，将自己的 级别设置为分组中的级别加l ，即为第1 级，建立它们自己的级别，然后广播新 的级别发现分组，其中包含的级别为1 。节点收到第i 级节点的广播分组后，记 录发送这个广播分组的节点i d ，设置自己的级别为( i + 1 ) ，广播级别设置为( i + 1 ) 的分组。这个过程持续下去，直到网络内的每个节点都赋予一个级别。节 点一旦建立自己的级别，就忽略任何其他级别发送的分组。 第二阶段称为同步阶段( s y n c h r o n i z a t i o np h a s e ) ：层次结构建立以后，根节 点通过广播时间同步( t i m es y n c ) 分组启动同步阶段。第一级节点收到这个分组 后，各自分别随机等待一段随机时间，通过与根节点交换消息同步到根节点。第 2 级节点侦听到第l 级节点交换消息进行同步。等待一段时间的目的是保证第2 级节点在第1 级节点时间同步完成后才启动消息交换。这样，每个节点与层次结 构中最靠近的上一级节点进行同步，最终所有节点都同步到根节点。 2 1 6 3 其他同步机制 t i n y s y n ca n dm i n i s y n c 3 同步算法是两个轻量的时间同步算法，通过交 换少量消息能量提供具有确定误差上界的频偏和相偏估计，同时仅需要提供非常 有限的网络通信带宽、存储容量和处理能力等资源，这正是传感器网络最需要的 特性。这两个算法的前提假设是节点的时间是“真实时间”的线性变化，它的时 钟频偏和相偏是不变的，对于需要长期监测的传感器网络应用，传感器节点低成 本的晶体振荡器很难保证时钟频偏和相片的长时间稳定性。 延迟测量时间同步( d e l a ym e a s u r e m e n tt i m es y n c h r o n i z a t i o n ，d m t s ) 机制基 于同步消息在传输路径上所有延迟的估计，实现节点间的时间同步。r b s 机制 需要交换的同步消息个数多，从而消耗较多的网络能量并降低时间同步收敛的速 度。d m t s 避免往返消息的r r t 估计，并且减少交换消息的发送个数，同时兼 1 0 中国科学技术大学硕士论文无线传感器网络中若干问题的研究和实现 顾可扩展性、能量消耗、计算代价等因素。 文献 4 认为利用消息往返双向传输的时间同步技术不适合传感器网络，因 为这种时间同步技术假设消息在往返双向路径上的传输时间相当。而这种假设在 传感器网络中往往不成立。为说明原因，将两个节点间的分组传输延迟细分为发 送端的处理延迟、介质访问延迟、发送延迟、无线传输延迟和接收端的处理延迟 等五部分，除了发送延迟和无线传播延迟外，其他部分的延迟在两个方向上都不 是对称的。另外，分组可能会损失和丢失。如果m a c 协议重传分组，往返时间 也会显著增加。 在d m t s 机制中，选择一个节点作为时间主节点广播同步时间。所有接收 节点的测量这个时间广播分组的延迟，设置它的时间为接收到分组携带的时间加 上这个广播分组的传输延迟，设置它的时间为接收到分组携带的时间加上这个广 播分组的传输延迟，这样所有接收到广播分组的节点都与主节点进行时间同步。 时间同步的精度主要由延迟测量的精度所决定。 l t s ( 1 i g h t w e i g h tt r e e - b a s e ds y n c h r o n i z a t i o n ) 匾 步算法 5 的设计目标是适用于 低成本、低复杂度的传感器节点时间同步，侧重最小化同步的能量开销，同时具 有鲁棒性和自配置的特点。有两类l t s 多跳时间同步算法：集中式和分布式。 集中式同步算法基本思想是构造低深度的生成树，然后以树根为参考节点， 依次向叶节点进行逐级同步，最终达到全网同步。 在分布式深度优先搜索算法中，任何节点在需要同步时都可以发起同步请 求，从参考节点到该节点路径上的所有节点采用节点对的同步方式，逐跳实现与 参考节点的时间同步。为减少开销，可以进行同步请求消息的合并，以及节点以 不同概率沿着不同路径发送同步请求消息，这可使得更多节点被动地与参考节点 同步。 2 2a o d v 按需路由协议介绍 a o d v 1 2 是一种按需路由协议。结点内部不维护路由表，当有数据需要发 送时查看路由缓存，如果没有可用路由就发起路由发现过程，将找到的路由记录 到路由缓存中，并用它发送数据。路由发起的过程分两步：源结点广播路由请求， 中间结点通过广播转发路由请求；目的结点单播发回路由应答。路由请求消息包 中国科学技术大学硕士论文无线传感器网络中若干问题的研究和实现 含请求的目的结点地址、自己的地址、用以控制重复发送的i d 和避免路由回环 的序列号信息。路由应答消息包含请求者地址、请求目的地址、i d 和序列号信 息等。在路由请求和路由应答经过的路径上，中间结点可以向自己的路由缓存中 记录通往上下游结点的路由。这样，当路由发现的发起者收到一个有效的路由应 答消息后，就可以建立通往请求目的的路由。当某一结点发现自己通向某邻居的 链路断开，并且自己的路由缓存中记录有若干有效路由，它需要向受到断开链路 影响的路由的上游结点发送出错消息。出错消息被逆向传播( 单播或广播) 到路 由的端点，如果有必要端点可以重新发起路由发现过程。 如果某结点缓存有若干有效路由，它可以在一定时间内周期性发送h e l l o 消息以维持链路的连接性。当一条路由一段时间没有被使用后，应该将它从路由 缓存中删除。这样做是因为在移动自组网的环境中不能保证任一条路由在任一段 时间后仍然有效。 a o d v 协议只需要很少的网络带宽开销。其缺点是实时性不是太好。 2 3 本实验的软件环境 本文的内容涉及到两个实验，一个是用仿真实验验证我们提出的关于时间同 步和二层架构下的簇头选举的方案。另一个是用连接有传感器、相互之间可以进 行无线通信的端机组建一个移动自组网，下面介绍一下实验的软、硬件环境。 2 3 1n s 2 仿真 对于时间同步和二层架构下的簇头选举方案的实验将在n s 2 1 3 平台上进 行。n s 2 ( n e t w o r ks i m u l a t o r ) 是众多网络仿真工具中的一种，是由美国d a r p a 资助的v 烈t 项目中的一项成果。作为一个事件驱动的虚拟实验平台，它可以提 供有线、无线网络中链路层及其上层、精确到数据包的一系列行为的仿真，对 t c p 、路由、多播( 组播) 协议的模拟提供了有力的支持。 2 3 2 传感器网络的拓扑结构和工作方式 传感器网络的基本工作模式是：控制中心向包含传感器的端机结点发送控制 消息，设定或查询端机的运行参数和工作状态：端机结点上的传感器负责监测周 中国科学技术大学硕士论文 无线传感器网络中若干问题的研究和实现 围环境，采集感兴趣的信息交由端机发回控制中心。整个网络的拓扑结构原理图 如图2 1 。图中的虚线表示无线通信链路。 上图只画出了一个控制中心，实际上控制中心可以有多个，分布在网络各处。 从图中可以看出，端机结点和控制中心之间的路径可以有多跳，控制中心的信号 覆盖范围没有必要将所有端机都包括在内。不能直接接收到控制中心信号的端机 可以通过其它端机做中介和控制中心交换信息。因此，控制中心不必像蜂窝网络 中的基站一样具有很高的发射功率，信号覆盖很广的范围。通过将转发功能分布 到每个端机上，并在网络中运行合适的多跳选路协议，我们可以在一个功率不大 的控制中心周围组建延伸范围相当广阔的传感器网络。 2 3 3 端机介绍 一一一一一一乜 传感器 传感器 图2 1 无线传感器网络的拓扑结构 我们将在以a r m 7 t d m i 为微控制器的端机结点上组建移动自组网，实现端 机结点之间和端机结点到控制中心的多跳通信。图2 2 是简化的端机结点结构的 原理图，其中省略了定时器、中断控制器等控制部件和一些外部接口单元。 图中a r m 7 t d m i 是传感器的中央控制部件。a r m 7 t d m i 1 6 是a r m 7 处理 器系列成员之一，是目前应用很广的3 2 位高性能嵌入式r i s c 处理器。它具有 中国科学技术大学硕士论文 无线传感器网络中若干问题的研究和实现 三级指令流水线( 取指令，译码，执行) ，使用单一的3 2 位数据总线传送指令和 数据，可以读写8 位、1 6 位和3 2 位的数据。它的存储接口控制信号是流水作业 的，允许在标准低功耗逻辑下实现系统控制功能。3 2 位地址总线允许访问最多 4 g 物理内存。a r m 7 t d m i 具有3 2 位和1 6 位两种指令集。3 2 位指令集是通常 使用的a r m 指令集；1 6 位指令集称为t h u m b 指令集，是3 2 指令集的子集，可 以提供较高的代码密度，使代码长度大大缩减，适用于有存储器宽度限制和对代 码密度要求较严格的嵌入式应用场合。1 6 位t h u m b 指令在执行时被透明地实时 解压为3 2 位a r m 指令，且性能没有损失。a r m 7 t d m i 内部含有嵌入式i c e r t 逻辑，其中包含了调试通信通道( d c c ，d e b u gc o m m u n i c a t i o n sc h a n n e l ) ，用于 在目标和宿主调试器之间传送信息。嵌入式i c e r t 逻辑通过j t a g ( j o i n tt e s t a c t i o ng r o u p ) 测试访问口进行控制，所以，可以通过b d i 等具有j t a g 接口的 调试工具方便地进行调试。 传感器用于采集数据。本实验使用的传感器用于军方，因此这里的传感器负 责搜集的信息包括人员、车辆的移动、震动、声响、热源等各个方面。采集到的 信息是模拟信号，需要经过模数转换器转换为数字信号传给a r m 7 t d m i 微处理 器。如果采集的信息需要发送，a r m 7 t d m i 会将转换来的数字信号组帧，交给 数组信号处理器d s p ，使用数模转换器把d s p 处理过的帧转换为模拟信号发送 出去。当从控制中心或其它端机结点收到消息后，d s p 将模数转换器转换来的信 号做接收后处理形成接收帧，交给a r m 7 t d m i 。 存储模块包括6 4 k 的f l a s h 和1 2 8 k 的s r a m 。f l a s h 充当了计算机中硬盘的 角色，s r a m 相当于内存。二进制可执行文件烧写在f l a s h 上，上电启动后，f l a s h 上位于r e s e t 中断处理程序入口处的引导程序把全部代码拷贝到s r a m 中，然后 跳转到s r a m 上程