（信息与通信工程专业论文）无线传感器网络的定位算法和超帧调度机制的研究.pdf

浙江大学硕士学位论文 摘要 基于i e e e 8 0 2 1 5 4 标准的z i g b e e 技术是一种新兴的低成本、低功耗、低速 率的短距离无线通信技术。随着z i g b e e 技术越来越多地被应用与环境监测、家 庭自动化和医疗护理等领域，无线传感器网络的定位技术和同步技术也收到越来 越多的关注。 本文的主要的工作有三个部分：首先，系统地介绍了无线传感器网络中的定 位算法，并对a p i t 、e c o l o c a t i o n 分布式定位算法进行了仿真和比较；然后，分 析了z i g b e e 树簇型网络的超帧调度算法中存在的问题，并给出了改进的方法； 最后，设计并实现了一个z i g b e e 网络平台。 无线传感器网络的节点定位是目标定位、监控等一系列应用的前提，也是无 线传感器网络的支撑技术。本文系统地介绍了目前存在的定位算法，重点介绍了 与距离无关的定位算法，并对经典的分布式定位算法a p i t 、e c o l o c a t i o n 进行了 仿真和比较，为进一步研究基于z i g b e e 的定位算法打下了基础。 时间同步对于无线传感器网络至关重要，且由于无线传感器网络与应用相关 的特性，在众多不同的应用中很难采用同一的时间同步机制。本文主要介绍了 z i g b e e 树簇型网络中，如何通过对信标帧的调度，实现整个网络的同步。并分析 了调度算法中存在的一系列问题，着重研究了使用调度算法引起的网络容量大小 的问题，提出通过对网络中协调器进行分组( 同一分组中的协调器可以同时发送 信标帧) ，可以在一定程度上改进网络的容量。 为了进行进一步的研究，结合符合i e e e 8 0 2 1 5 4 的无线微控器j n 5 1 2 1 ，自 行设计了具有温湿度采集能力的z i g b e e 节点，并开发了一个具有可视化界面的 z i g b e e 网络。 最后，本文总结了所作的工作，并对将来的工作进行了展望。 关键词：无线传感器网络，z i g b e e ，无线定位，超帧，时间同步 浙江人学硕士学位论文 a b s t r a c t z i g b e et e c h n o l o g y , b a s e do nt h ei e e e8 0 2 15 4p r o t o c o l ，i san e w l yd e v e l o p e d s h o r tr a n g ew i r e l e s sc o m m u n i c a t i o nt e c h n o l o g yw i t ht h em e r i t so fl o wc o s t ，l o w p o w e rc o n s u m p t i o na tc o m p a r a b l el o w e rd a t ar a t e w h i l et h ez i g b e et e c h n o l o g yi s m o r ea n dm o r ef r e q u e n t l ya d o p t e di na p p l i c a t i o na r e a sl i k ee n v i r o n m e n t a lm o n i t o r i n g ， h o m ea u t o m a t i o n ，m e d i c a lt r e a t m e n ta n ds oo n ，w i r e l e s ss e n s o rn e t w o r kp o s i t i o n i n g t e c h n o l o g ya n ds y n c h r o n i z a t i o nt e c h n o l o g yh a sa l s or e c e i v e di n c r e a s i n ga t t e n t i o n t h em a i nw o r ko ft h ea r t i c l eh a st h r e ep a r t s ：f i s t ，g i v e sas y s t e m a t i ci n t r o d u c t i o n o ft h el o c a l i z a t i o na l g o r i t h mi nw i r e l e s ss e n s o rn e t w o r k s a n ds i m u l a t e st h ea p i ta n d e c o l o c a t i o na l g o r i t h m ；t h e n ，a n a l y z e st h ep r o b l e m si nt h es u p e r f r a m ed u r a t i o n s c h e d u l ea l g o r i t h m ，a n dg i v e st h ei m p r o v e dm e t h o d ；f i n a l l y , d e s i g n sa n dr e a l i z e sa z i g b e en e t w o r kp l a t f o r m t h en o d el o c a l i z a t i o no fw i r e l e s ss e n s o rn e t w o r ki st h ep r e m i s eo faw i d er a n g e o fa p p l i c a t i o n ss u c ha s t a r g e t i n ga n dm o n i t o r i n g ，b u ta l s ot h es u p p o r to fw i r e l e s s s e n s o rn e t w o r k t h i sa r t i c l eg i v e sas u m m a r yo ft h ec u r r e n tl o c a l i z a t i o na l g o r i t h m ， e m p h a s i so nt h er a n g e f r e ea l g o r i t h m ，a n dg i v e sas i m u l a t i o na n dc o m p a r i s o no ft h e c l a s s i cd i s t r i b u t e dl o c a l i z a t i o na l g o r i t h m ，p r o v i d e sab a s i sf o rt h ef u r t h e rs t u d yo ft h e l o c a l i z a t i o na l g o r i t h mb a s e do nz i g b e e t i m es y n c h r o n i z a t i o ni se s s e n t i a lf o rw i r e l e s ss e n s o rn e t w o r k s ，a n db e c a u s e w i r e l e s ss e n s o rn e t w o r k si sh i g h l yr e l a t e dt oa p p l i c a t i o n s ，i ti sv e r yd i f f i c u l tt ou s et h e s a m et i m es y n c h r o n i z a t i o nm e c h a n i s ma m o n gt h e m t h i sa r t i c l em a i n l yi n t r o d u c e s h o wt os y n c h r o n i z et h ew h o l en e t w o r kb ys c h e d u l et h eb e a c o nf r a m ei nz i g b e ec l u s t e r t r e en e t w o r k a n dp o i n t so u tt h ep r o b l e mi nt h es d sa l g o r i t h m ，g i v e sas o l u t i o nt o h o wt oe n l a r g et h en e t w o r kc a p a c i t y f o rf u r t h e rs t u d yo nz i g b e e ，w ed e v e l o paz i g b e en e t w o r kp l a t f o r mb a s e do nt h e ai e e e 8 0 2 15 4w i r e l e s sm i c r o c o n t r o l l e ra n dt e m p e r a t u r eh u m i d i t ys e n s o r ，w h i c h a l s oap c g r a p h i cu s e ri n t e r f a c e i nt h ee n d ，w ec o n c l u d eo u rw o r k ，a n dg i v eap r o s p e c to ft h ef u t u r ew o r k k e y w o r d s ：w s n ，z i g b e e ，l o c a l i z a t i o n ，s u p e r f r a m e ，t i m es y n c h r i n i z a t i o n i i 浙江大学硕士学位论文 第一章绪论帚一早瑁化 1 1 无线传感器网络概述 无线传感器网络是由空间上分布在不同位置，用传感器对现实世界的参量例 如温度，湿度，光强，气体浓度等进行采集和监测的器件组成的无线网络。它综 合了传感器技术、嵌入式计算技术、现代网络和无线电通信技术，被认为是对 2 l 世纪产生巨大影响力的技术之一。 无线传感器网络与传统的无线网络( 如w l a n 和蜂窝移动电话网络) 有着 不同的设计目标，后者在高度移动的环境中通过优化路由和资源管理策略最大化 带宽的利用率，同时为用户提供一定的服务质量保证。在无线传感器网络中，除 了少数节点需要移动外，大部分节点都是静止的。设计有效的策略延长网络的生 命周期成为传感器网络的核心问题，深入的研究表明：传感器网络有着与传统网 络明显不同的技术要求。前者以数据为中心，后者以传输数据为目的。 2 0 0 0 年1 2 月i e e e 成立了i e e e 8 0 2 1 5 4 工作组，致力于定义一种供廉价的 固定、便携或移动设备使用的极低复杂度、成本和功耗的低速率无线连接技术。 产品的方便灵活、易于连接、实用可靠及可继承延续是市场的驱动力。一般认为 短距离的无线低功率通信技术最适合传感器网络实用，传感器网络是 i e e e 8 0 2 1 5 4 标准的主要市场对象。将传感器和i e e e 8 0 2 1 5 4 设备组合，进行数 据收集、处理和分析，就可以决定是否需要何时需要用户操作。 i e e e 8 0 2 1 5 4 标准受到m o t o r o l a ，h o n e y w e l l ，p h i l i p s 这些国际通信和工业 控制巨头的极力推崇，他们在i e e e 8 0 2 1 5 4 的基础上在2 0 0 2 年成立了z i g b e e 联 盟，负责制定网络层，应用支持子层和一些应用相关的框架。 1 2 无线传感器网络的体系结构 1 2 1 无线传感器网络结构 无线传感器网络系统通常包括传感器节点( s e n s o rn o d e ) 、汇聚节点( s i n k n o d e ) ，如图1 1 所示。大量传感器节点部署在监测区域内，能够通过自组织方 式构成网络。传感器节点监测的数据沿着其它传感器节点逐跳地进行传输，在传 输过程中监测数据可能被多个节点处理，经过多跳后路由到汇聚节点，最后通过 互联网、g p r s 或者卫星到达管理节点。用户通过管理节点对传感器网络进行配 浙江大学硕士学位论文 置和管理，发布监测任务以及收集监测数据 1 4 。 传感器节点通常是一个微型的嵌入式系统，它的处理能力、存储能力和通信 能力相对较弱，通过携带能量有限的电池供电。从网络功能上看，每个传感器节 点兼顾传统网络节点的终端和路由器双重功能。除了进行本地信息收集和数据处 理外，还要对其它节点转发来的数据进行存储、管理和融合等处理，同时与其它 节点协作完成一些特定任务。目前传感器节点的软硬件技术是传感器网络研究的 重点。 汇聚节点的处理能力、存储能力和通信能力相对比较强，它连接传感器网络 与i n t e r n e t 等外部网络，实现两种协议栈之间的通信协议栈转换，同时发布管理 节点的监测任务，并把收集的数据转发到外部网络上。汇聚节点既可以是一个具 有增强功能的传感器节点，有足够的能量供给和更多的内存与计算资源，也可以 是没有监测功能仅带有无线通信模块的特殊网关设备。 图1 1 无线传感器网络体系结构 1 2 2 传感器节点结构 节点的典型硬件结构如图1 2 所示，主要包括电池及电源管理电路、传感器、 信号调理电路、a d 转换器件、存储器、微处理器和射频模块等。传感器节点的 处理器模块操作，存储和处理本事采集的数据以及其他节点发来的数据；无线通 信模块负责和其他传感器节点进行无线通信，交换控制消息和收发采集数据；能 2 浙江大学硕上学位论文 量供应模块为传感器节点提供运行所需的能量，通常采用微型电池。根据不同的 应用需求，还可能会有定位系统用来确定传感器节点的位置，有移动单元使得传 感器节点可以在待监测地域中移动【4 2 。 传感模块 处理模块无线通信模块 图1 2 传感器节点结构 1 2 3 传感器网络协议栈 随着传感器网络的深入研究，研究人员提出了多个传感器节点的协议栈。图 1 3 所示是一种典型的协议栈，这个协议栈包括物理层、网络层、传输层和应用 层，与互联网协议栈的5 层协议相对应。另外，协议栈还包括能量管理平台、移 动管理平台和任务管理平台。这些管理平台使得传感器节点能够按照能源高效的 方式协同工作，在节点移动的传感器网络中转发数据，并支持多任务和资源共享， 个层协议和平台的功能如下： 物理层：提供简单但健壮的信号调制和无线收发技术； 数据链路层：负责数据成帧、帧监测、媒体访问和差错控制； 网络层：主要负责路由生成与路由选择； 图1 3 无线传感器网络协议栈 浙江大学硕士学位论文 传输层：负责数据流的传输控制，是保证通信服务质量的重要部分； 应用层：包括一系列基于监测任务的应用层软件； 能量管理平台：管理传感器节点如何使用能源，在各个协议层都需要考虑节 省能量： 移动管理平台：监测并注册传感器节点的移动，维护到汇聚节点的路由； 任务管理平台：在一个给定的区域内平衡和调度监测任务。 1 3 无线传感器网络的特征 1 3 1 与现有无线网络的区别 无线自组网是一个由几十到上百个节点组成的，采用无线通信方式的、动态 组网的多跳的移动对等网络。其目的是通过动态路由和移动管理技术传输具有服 务质量要求的多媒体信息流。通常节点具有持续的能量供给。 传感器网络虽然与无线自组网有相似之处，但同时也存在很大的差别。传感 器网络是集成了监测、控制以及无线通信的网络系统，节点数目更为庞大( 上千 甚至上万) ，节点分布更为密集；由于环境影响和能量耗尽，节点更容易出现故 障；环境干扰和节点故障造成网络拓扑结构的变化；通常情况下，大多数传感器 节点是固定不动的。另外，传感器节点具有的能量、处理能力、存储能力和通信 能力等都十分有限。传统无线网络的首要设计目标是提供高服务质量和高效带宽 利用，其次才考虑节约能源；而传感器网络的首要设计目标是能量的高效使用， 这也是传感器网络的和传统网络最重要的区别之一。 1 3 1 无线传感器网络的特点 l 、以数据为中心：无线传感器网络中节点数目巨大，而且由于网络拓扑的 动念特性和节点放置的随机性，节点并不需要也不可能以全局唯一的i p 地址来 标识，只需使用局部可以区分的标号标识。用户对所需数据的收集，是以数据为 中心进行，并不依靠节点的标号。 2 、资源受限：无线传感器网络中，节点只具有有限的硬件资源，其计算能 力和对数据的处理能力相当受限。此外，节点只能携带有限的电池能量，且在应 用过程中不可能更换电池，因此能量也相当受限。 4 浙江人学硕士学位论文 3 、部署方式：无线传感器网络具有可快速部署的特点。节点一旦被抛撒即 以自组织方式构成网络，无需任何预设的网络设施。 4 、自动维护：在通信过程中，节点会随时因为能源耗尽而离开网络，也可 能因为某种需要而随时进入网络，从而引起网络拓扑的频繁变化，影响通信质量。 无线传感器网络不仅可实现自动组网，还具有网络自动配置和自动维护功能，保 证了网络的通信质量。 5 、多跳路由：网络中节点的电池能源非常有限，因此其通信覆盖范围一般 只有几十米，即每个节点都只能与其邻居节点进行通信。若需要与通信覆盖范围 外的节点通信，则需要通过中间节点进行多跳路由。 1 4i e e e 8 0 2 1 5 4 协议 i e e e 8 0 2 1 5 4 1 的全功能节点有三种不同的工作模式： ( 1 ) p a n 协调器：整个网络的主控器。协调器用唯一的i d 标识整个网络， 并对整个网络进行配置。在z i g b e e 中，它被称为z i g b e e 协调器。 ( 2 ) 协调器：通过发送信标帧来同步子节点，其父节点是p a n 协调器，且 不会组织自己的网络，在z i g b e e 中，它被称为z i g b e e 路由器。 ( 3 ) 终端设备：不具备以上功能的节点是终端节点。终端节点成为z c 或 z r 的子节点后，可以和网络中的节点进行通信。在z i g b e e 中，它被称为z i g b e e 终端节点。 消减功能节点只实现了整个协议栈的部分，在应用中，它适合那些只需要很 简单功能的场合，例如灯光控制系统中的开关。 1 4 1 物理层 物理层主要负责数据的发送和接收。i e e e 8 0 2 1 5 4 提供三种不同的工作频段 2 4 g h z ，915 m h z ，8 6 8 m h z 。8 6 8 m h z 和8 6 8 6 m h z 之间只有一条信道，9 0 2 m h z 和9 2 8 m h z 之间有1 0 条信道，2 4 g h z 和2 4 8 3 5 之间有1 6 条信道。 浙江大学硕十学位论文 8 6 8 9 1 5 m h z 物理层 2 ，4 g 物理层 信道1 一l o 2 m h z “ 2 瑚z 图1 - 4i e e e 8 0 2 1 5 4 的工作频段 所有的频段都采用直接序列扩频的方式对信号进行调制。 物理层数据服务包括以下五方面的功能： ( 1 ) 激活和休眠射频收发器； ( 2 ) 信道能量检测( e n e r g yd e t e c t ) ； ( 3 ) 检测接收数据包的链路质量指示( 1 i n kq u a l i t yi n d i c a t i o n ，l q i ) ； ( 4 ) 空闲信道评估( c l e a rc h a n n e la s s e s s m e n t ，c c a ) ； ( 5 ) 收发数据。 信道能量检测为网络层提供信道选择依据。它主要测量目标信道中接收信号 的功率强度，由于这个检测本身不进行解码操作，所以检测结果是有效信号功率 和噪声信号功率之和。 链路质量指示为网络层或应用层提供接收数据帧时无线信号的强度和质量 信息，与信道能量检测不同的是，它要对信号进行解码，生成的是一个信噪比指 标。这个信噪比指标和物理层数据单元一道提交给上层处理。 空闲信道评估判断信道是否空闲。i e e e8 0 2 1 5 4 定义了三种空闲信道评估模式： 第一种简单判断信道的信号能量，当信号能量低于某一门限值就认为信道空闲； 第二种是通过判断无线信号的特征，这个特征主要包括两方面，即扩频信号特征 和载波频率；第三种模式是前两种模式的综合，同时检测信号强度和信号特征， 给出信道空闲判断。 1 物理层的载波调制 在8 6 8 m h z 和9 1 5 m h z 这两个频段上，信号处理过程相同，只是数据速率不 同。处理过程，首先将物理层协议数据单元( p h yp r o t o c o ld a t au n i t ，p p d u ) 的 6 o 一 耥n一 浙江大学硕士学位论文 - - n 数据差分编码，然后再将差分编码后的每一个位转换为长度为1 5 的片序列 ( c h i ps e q u e n c e ) ，最后b p s k 调制到信道上。 差分编码是将数据的每一个原始比特与前一个差分编码生成的比特进行异 或运算：e n = r noe n 1 ，其中e n 是差分编码的结果，r n 为要编码的原始比特， e n 1 是上一次差分编码的结果。对于每个发送的数据包，r 1 是第一个原始比特， 计算e 1 时假定e 0 = 0 。差分解码过程与编码过程类似： r n = e noe n 1 ，对于每 个接收到的数据包，e 1 是第一个需要解码的比特，计算r 1 时假定e 0 = 0 。 差分编码以后，接下来就是直接序列扩频。每一个比特被转换为长度为1 5 的片 序列。扩频过程按下表进行，扩频后的序列使用b p s k 调制方式调制到载波上。 2 4 g h z 频段的处理过程，首先将p p d u 的二进制数据中每4 位转换为一 个符号( s y m b 0 1 ) ，然后将每个符号转换成长度为3 2 的片序列。在把符号转换片 序列时，用符号在1 6 个近似正交的伪随便噪声序列的映射表，这是一个直接序 列扩频。 1 4 2 媒体接入控制层( m a c ) 层 m e e 8 0 2 15 4 支持两种工作模式： ( 1 ) 信标使能模式：当网络工作在信标使能模式时，协调器和路由器 通过周期性地发送信标帧来同步和它们关联的节点。信标帧中超 帧描述字段规定了这个超帧的持续时间，活跃部分持续时间以及 竞争访问时段持续时间等信息。g t s 分配字段交无竞争时段划分 为若干个g t s ，并把每个g t s 具体分配给了某个设备。 ( 2 ) 信标非使能模式：协调器和路由器将不会发送信标帧，网络中也 不存在超帧的概念。媒体接入控制由不带时槽的c s m a c a 来实 现。 1 4 3 超帧结构 每个超帧都以网络协调器发出信标帧( b e a c o n ) 为始，在这个信标帧中包含 了超帧将持续的时间以及对这段时间的分配等信息。网络中普通设备接收到超帧 开始时的信标帧后，就可以根据其中的内容安排自己的任务，例如进入休眠状态 直到这个超帧结束。 7 浙江人学硕士学位论文 l 一j 图l 一5i e e e 8 0 2 1 5 4 的一l 作模式 超帧的活跃部分有3 部分组成：信标帧、竞争访问时段和非竞争访问时段。 ( 1 ) 信标帧：超帧描述字段、g t s 分配字段、待转发数据目标地址字 段和信标帧负载数据。 ( 2 ) 竞争访问时段( c a p ) ：c a p 的最短长度为4 4 0 个符号。在竞争 访问时段，数据传输采用带时槽的c s m a c a 机制。如果数据包 不可发送信标 r j ( ：t s i g t s 2 c氏p 黧鞠豳阕躐 i n a c t i v e p e r i o d r | b l = a b a s e s u p e r f r a m e d u r a t i o n 2 ”s y m b o l s 幽l 一6 超帧结构 不能在c a p 传输完毕，必须在延迟到下一个超帧才能传输。 ( 3 ) 非竞争访问时段：在非竞争时段，协调器根据上一个超帧p a n 网 络中设备申请g t s 的情况，将非竞争时段划分成若干个g t s 。每 个g t s 由若干个时槽组成，时槽数目在设备申请g t s 时指定。如 果申请成功，申请设备就拥有了它指定的时槽数目。每个g t s 中 的时槽都指定分配给了时槽申请设备，因而不需要竞争信道。i e e e 浙江大学硕士学位论文 8 0 2 1 5 4 标准要求任何通信都必须在自己分配的g t s 内完成。 超帧中有两个重要的参数，如图2 6 所示： ( 1 ) 信标帧的间隔( b hb e a c o ni n t e r v a l ) ：两个信标帧之间的时间间隔。 ( 2 ) 超帧持续时间( s d ：s u p e r f r a m ed u r a t i o n ) ：b i 中的活跃部分，被划分 成1 6 个等长的时槽。 如果b i s d ，将存在着一个非活跃时期。在非活跃期，节点可以进入睡眠以 节省能量。b i 和s d 分别由b o 和s o 两个参数决定，如式2 1 2 所示： b i ：a b a s e s u p e r f r a m e d “r a t i o 玎2 肋 肋：础傩易佣扣材m f 面刀2 f o 加舳b d 9 4 ( 2 1 2 ) a b a s e s u p e r f r a m e d u r a t i o n = 1 5 3 6 m s ( 2 4 g h z ，比特率为2 5 0 k b p s ) ，即当s o = 0 时超帧的最短长度。 如图2 - 6 所示，s o b o 的值越小，非活跃部分就越长，节点的能耗就越少。 1 5z i g b e e 协议 1 5 1 简介 z i g b e e 2 定义了o s i 模型的两层：应用层( a p l ) 和网络层( n w l ) ，如图 1 7 所示。每一层都为上一层提供一定的服务。不同的通过s a p ( s e r v i c ea c c e s s p o i n t ) 进行通信。s a p 包括两种实体：( 1 ) 数据实体( n l d e s a p ) 用来提供数 据传输服务( 2 ) 管理实体( n l m e s a p ) 用来提供层次间的管理服务。 应用层( a p l ) 是最上层，包括应用支持子层( a p s ) ，z i g b e e 器件对象( z d o ) 和包含与应用相关的执行对象的应用框架( a f ) 。a p l 和a p s 通过所谓的 e n d p o i m s 来进行交流，每一个e n d p o i n t s 包含一组接口( a p s d e s a p ) 来支持 层次间的数据传输。应用支持子层( a p s ) 提供两组服务：( 1 ) a p s m e s a p ， 即应用支持子层管理实体s a p ，协调器的z d o 通过它来取得a p s 层的信息，用 来执行保证网络安全的一些操作，( 2 ) a p s d e s a p ，即应用支持子层数据实体 s a p ，a f 和z d o 用来和a p s 交换数据。z d o 提供给a f 接口，用以发现另外 的器件和它们提供的服务。z d o 位于e n d p o i n t0 。应用对象是在z i g b e e 协议栈 上运行的制造商的具体的应用，位于e n d p o i n t0 2 4 0 ，执行一个具体的服务， 可以是z i g b e e 联盟制订的公共的，也可以是用户自己定义的( 私有的) 。 9 浙江人学硕二l 学位论文 阂辫 o s a _ 】p e 蛾? 虢 图1 7z i g b e e 协议栈结构 z i g b e e 网络层负责整个网络的管理( 节点加入和离开网络) ，安全和路由。 当然，也维护网络的邻居列表和一些相关的信息。网络层提供了一组接1 3 ， n l d e s a p 用来和a p s 层进行数据交换。 图1 8z i g b e e 网络拓扑结构 i e e e 8 0 2 1 5 4 z i g b e e 器件可以通过它们的功能进行分类：全功能器件( f f d ) 1 0 浙江大学硕士学位论文 具有i e e e 8 0 2 1 5 4 z i g b e e 协议栈的所有功能；精简功能器件( r f d ) 只有协议 栈的部分功能。 考虑器件在网络中的功能，z i g b e e 定义了3 中类型的器件： z i g b e e 协调器( z c ) ：一个z i g b e e 网络只有一个；负责初始化和配置网络； 是i e e e 8 0 2 1 5 4 个域网的协调器；当网络建立完毕后，是网络的一个路由器 ( z i g b e er o u t e r ) ；是一个全功能器件( f f d ) 具有协议栈的所有功能；如果网 络运行在信标使能的模式中，z c 将要周期性地发送信标帧来同步网络中的其它 节点。在树簇型网络中，所有的z r 会接收到它们的父节点发送来的信标，也会 自己发送信标来同步它们簇中的节点。 z i g b e e 路由器( z r ) ：在网状网和树簇型网络中参与数据包的多跳路由； 参与节点加入网络的验证过程；是i e e e 8 0 2 1 5 4 个域网的协调器；是一个全功 能的器件。 z i g b e e 端器件( z e d ) ：不允许其它节点以它为父节点加入网络；不参与 数据包的路由过程；只是一个传感器节点；可以是一个z e d 。 i e e e 8 0 2 1 5 4 z i g b e e 有三种类型的网络拓扑一星形、网状、树形。如图2 2 所示。 在树形网络中( 图1 - 8 a ) ，只有一个节点作为z c 。z c 选择一个p a ni d ，i d 必须和周围的z i g b e e 网络的i d 不同。星形网络的通信是以z c 为中心的，一个 器件( f f d 或者r f d ) 加入了网络，如果想要和另一个节点进行通信，必须先 将数据包发送至z c ，然后z c 在将此数据包发送到目的节点。星形网络不适合 无线传感器网络，原因有两方面：( 1 ) z c 节点将很快将电量耗尽；( 2 ) 网络覆 盖范围有限，不适合大规模的传感器网络。 网状拓扑( 图1 8 b ) 也包括一个标识整个网络的z c 。但是，网状网络的通 信模式是分布式的，例如一个节点可以和在它通信范围内节点直接通信。网状网 在加强了网络的健壮性的同时也使整个网络更加复杂。本质上，网状网是一个 a d h o c 网络，允许数据包通过多跳路由从一个节点到达另一个节点。相对于星 形网络而言，网状网能量利用率更高，也更公平，因为通信不依赖与某一个特定 的节点。 树簇型( 图1 - 8 c ) 网络拓扑是网状网络的一个特例，任何两个节点间只有一 条路由，并且存在一个同步机制( i e e e 8 0 2 1 5 4 信标使能模式) 。和网状网络一 个，整个网络只有一个标识全网的z c 。每一个簇只有一个z r 。任何一个全功能 节点都可以作为z r ，提供同步服务给其它节点。 1 5 2z i g b e e 网络层 浙江人学硕士学位论文 网络层负责网络管理( 例如，加入和离开网络，开始网络，分配地址，器件 配置和n m f n w ki n f o r m a t i o nb a s e ) 的维护) 、数据路由和安全相关的一些服务。 z i g b e e 网络层支持两种服务实体。网络层数据实体( n l m e ) 提供数据帧的 传输和一定网络拓扑下的路由的服务。图1 - 9 描述了网络层的参考模型。 所有的z i g b e e 器件都支持别的器件加入和离开网络。协调器和路由器还必 须具备如下的功能： 图l - 9 网络层参考模型 ( 1 )当m a c 层有请求或应用层有命令时，允许器件加入网络。 ( 2 )当收到网络层的离开命令帧或者应用层的离开请求时，允许器件离开 网络。 ( 3 ) 分配网络的1 6 位短地址。 ( 4 ) 维持一个邻居列表。 z i g b e e 协调器定义了一些重要的网络参数，下面一一来说明。c m ，一个节 点所能拥有的最大孩子数，在c m 中，r m 代表这些孩子中具有路由能力的器件的 上限，剩下的就是z e d 。每一个节点都有一个深度，即发送一个数据包到z c ， 只用p a r e n t c h i l d 链路，需要的跳数。z c 的深度为0 ，它的孩子的深度为1 z c 也定义了网络的最大深度，用l m 表示。z i g b e e 使用c m ，r m ，l m 和分布式地址 策略来计算每个节点的地址。 1 6 本文的主要工作与篇章结构 随着低成本、低功耗、低速率的z i g b e e 技术越来越多地应用到家庭自动化、 1 2 浙江人学硕士学位论文 环境监测和医疗护理等领域，作为无线传感器网络支撑技术的定位技术和时间同 步也受到人们的关注。本文主要研究基于z i g b e e 的定位算法、z i g b e e 树簇型网 络的超帧调度算法以及z i g b e e 网络平台的搭建。 论文在内容组织上分为七章，具体安排如下： 第一章绪论 主要介绍了无线传感器网络的概念、体系结构、特点，并对 i e e e 8 0 2 1 5 4 z i g b e e 协议做了简要介绍。最后阐述了本文的主要工作和篇章结 构。 第二章无线传感器网络中的定位技术 主要介绍了无线传感器网络中与距离无关的经典算法，并进行了仿真和分 析，总结了它们的优缺点。 第三章超帧调度算法 详细讨论了z i g b e e 协议中树簇型网络中同步信息易于丢失的问题，详细讨 论了如何使用超帧调度算法解决此问题。同时，也总结了超帧调度算法中存在的 一系列问题。 第四章s d s 算法的改进和分析 针对超帧调度算法中存在的网络容量过小的问题，提出通过对协调器进行分 组以提高网络容量，并指导性给出如何在实际场景中实现。 第五章z i g b e e 网络平台的设计和实现 组建了一个z i g b e e 网络平台。采用j e n n i c 公司的无线微控器j n 5 1 2 1 搭载温 湿度传感器自行设计了硬件平台，协调器和p c 通过串口通信，p c 端程序采用 开源的脚本语言p y t h o n 进行编写，实现了网络拓扑显示、温湿度数据显示和对 网络中节点的简单控制。 第六章总结和展望 总结了全文的工作，提出了下一步的工作计划。 浙江大学硕上学位论文 第二章无线传感器网络中的定位技术 2 1 无线传感器定位简介 在无线传感器网络中，位置信息对传感器网络的监测活动至关重要，事件发 生的位置或获取信息的节点位置是传感器节点监测消息中所包含的重要信息，没 有位置信息的监测消息往往毫无意义。因此，确定事件发生的位置或获取消息的 节点位置是传感器网络最基本的功能之一，对传感器网络应用的有效性起着关键 作用。 在传感器网络的各种应用中，检测到事件之后关心的一个重要问题就是该事 件发生的位置。如环境监测应用中需要知道采集的环境信息所对应的具体区域位 置，比如需要知道森林火灾现场位置，战场上敌方车辆运动区域，天然气管道泄 露具体地点等。对于这些问题，传感器节点必须知道自身的地理位置信息，这是 进一步采取措施和做出决策的基础。 定位信息除用来报告事件发生的地点外，还具有下列用途：目标跟踪 2 3 ， 实时监测目标的行动路线，预测目标的前进轨迹；协助路由 2 4 1 1 2 5 】，为网络提 供命名空间 2 6 2 7 2 8 ，如直接利用节点位置信息进行数据传递的地理路由协 议，避免信息在整个网络中扩散，并可以实现定向的信息查询；进行网络管理， 利用传感器节点传回的位置信息构建网络拓扑图，并实时统计网络覆盖情况 3 5 3 6 ，对节点密度低的区域及时采取必要的措施，实现网络均衡负载以及网 络拓扑的自配置，等等。因此在传感器网络中，传感器节点的精确定位对各种精 确定位对各种应用有着重要作用。 在传感器网络中，传感器节点能量有限、可靠性差、节点规模大且随机布放、 无线模块的通信距离有限，对定位算法和定位技术提出了很高的要求。传感器网 络的定位算法通常需要具备以下特点： 自组织性：传感器网络的节点随机分布，不能依靠全局的基础设 施协助定位。 健壮性：传感器节点的硬件配置低、能量少、可靠性差，测量距 离时会产生误差，算法必须具有较好的容错性。 能量高效：尽可能地减少算法中计算的复杂性，减少节点间的通 信开销，以尽量延长网络的生存周期。通信开销是传感器网络的 主要能量开销。 分布式计算：每个节点计算自身位置，不能将所有信息传送给某 1 4 ) ) ) ) 1 2 3 4，ll，l，k 浙江大学硕士学位论文 个节点进行集中计算。 传感器网络节点定位技术中，根据节点是否己知自身的位置，把传感器节点 分为信标节点( b e a c o nn o d e ) 和( u n k n o w nn o d e ) 。信标节点在网络节点中所占 的比例很小，可以通过携带g p s 定位设备等手段获得自身的精确位置。信标节 点是未知节点定位的参考点。除了信标节点外，其他传感器节点就是未知节点， 它们通过信标节点的位置信息来确定自身位置。在如图2 1 所示的传感器网络中， 节点( 1 ，7 ，9 ，1 4 ) 代表信标节点，其余节点为未知节点。未知节点通过一定 的定位算法计算出自身的位置。 图2 一l传感器【网络中信标i 了点利未知1 ，点 无线传感器网络的定位算法大致分为两类：基于距离的定位和与距离无关的 定位。 基于距离的定位机制( r a n g e b a s e d ) 是通过测量相邻节点间的实际距离或方 位进行定位。具体过程通常分为3 个阶段：第一个阶段是测距阶段，未知节点首 先测量到邻居节点的距离或角度，然后进一步计算到邻近信标节点的距离或方 位，在计算到邻近信标节点的距离时，可以计算未知节点到信标节点的直线距离， 也可以用两者之i n j 的跳段距离作为直线距离的近似；第二个阶段是定位阶段，未 知节点在计算出到达三个或三个以上信标节点的距离或角度后，利用三边测量 法、三角测量法或极大似然估计法计算未知节点的坐标；第三个阶段是修正阶段， 对求得的节点的坐标进行求精，提高定位精度，减少误差。 虽然基于距离的定位能够实现精确定位，但往往对无线传感器节点的硬件要 求高，处于硬件成本、能耗等的考虑，人们提出了距离无关的定位技术。距离无 关的定位技术无需测量节点间的绝对距离或方位，降低了对节点硬件的要求，但 定位的误差也相应有所增加。 浙江大学硕士学位论文 2 2 计算节点位置的基本方法 传感器节点定位过程中，未知节点在获得邻近信标节点的距离，或获得邻近 的信标节点与位置节点之间的相对角度后，通常使用下列方法计算自身的位置。 2 2 1 三边测量法 三边测量法如图2 - 2 所示，已知a ，b ，c 三个节点的坐标分别为( ，虼) 、 ( ，y b ) 、( t ，见) ，以及它们到未知节点d 的距离分别为d a ，d b ，d c ，假设节点d 的坐标为( x ，y ) 。 图2 - 2 三边测量法图示 那么存在下列公式： i 一) 2 + ( y - y o ) 2 = 吃 一) 2 + ( y - y b ) 2 = 巩 i ( x t ) 2 + ( 少一咒) 2 = 以 由式( 2 1 ) 可以得到节点d 的坐标为： 1 6 ( 2 1 ) ； = 主 乏二乏；主 芰二芰； 。1 薹二萎：要二妻：墨二凄 c 2 2 ， 2 2 2 三角测量法 三角测量法( t r i a n g u l a t i o n ) 原理如图2 - 3 所示，已知a ，b ，c 三个节点的 坐标分别为( 工。，儿) 、( ，虼) 、( t ，虬) ，节点d 相对于a ，b ，c 的角度分别为： z a d b ，z a d c ，_ b d c ，假设节点d 的坐标为( x ，y ) 。对于节点a ，c 和角z a d c ， 如果弧段a c 在鲋口c 内，那么能够惟一确定一个圆，设圆心为o ，( x o 。，y d l ) ，半 径为，i ，那么c t = z a o , c = ( 2 z - 2 z a d c ) ，并存在下列公式： 4。(。x。o。l。-。x。,。,。)。：。+。(。y。o。l-。y。,。,。)。2。=r。 厄i 万百而= 巧 ( 2 3 ) ( 一t ) 2 + ( 儿一儿) 2 = 2 2 2 巧2 c o s b ( ，吮) 图2 - 3 三角测量法图示 由式( 2 3 ) 能够确定圆心q 点的坐标和半径巧。同理对a ，b ，z a d b 和b ，c ， 么叻c 分别确定相应的圆心q ( ：，y o ：) 、半径眨、圆心q ( 勤3 ，y o ，) 和半径。 1 7 浙江大学硕士学位论文 最后利用三边测量法，由点d ( x ，y ) ，o , ( x o 。，y o 。) ，0 2 ( x 0 2 ，2 ) ， q ( ，3 ) 确 定d 点的坐标。 2 2 3 极大似然估计法 极大似然估计法( m a x i m u ml i k e l i h o o de s t i m a t i o n ) 如图2 _ 4 所示，己知1 ，2 ， 3 等n 个节点的坐标分别为( 五，乃) ，( 吃，儿) ，( 恐，乃) ，( ，儿) ，它们到节点d 的距 离分别为4 ，吐，喀，吃，假设节点d 的坐标为( x ，y ) 。 3 图2 _ 4 极大似然估计法图不 那么，存在下列公式： i ( 五- x ) 2 + ( 乃- y ) 2 = 彳 i i ( - x ) 2 + ( 只一y ) 2 = 刃 从第一个方程开始分别减去最后一个方程，得： f 彳一x