（信号与信息处理专业论文）基于图着色的无线传感器网络高能效传输调度协议研究.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名： 叁遂垂目 日 期艺! 垄：兰：17 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在 论文作者签名： 山东大学硕士学位论文 目录 摘要i a b s t r a c t i i 第l 章绪论1 1 1 无线传感器网络概述1 1 1 1 无线传感器网络组成及功能1 1 1 2 无线传感器网络的关键问题j 3 1 2 无线传感器网络节能技术二4 1 2 1 无线传感器网络能耗来源4 1 2 2 节能技术分类5 1 3 本文研究目标：8 第2 章无线传感器网络的高能效传输协议1 0 2 1 中心式控制与分布式控制一1 0 2 2 基于竞争机制的休眠唤醒协议1 0 2 3 基于分配机制的传输调度协议1 2 2 4 传输协议评价1 4 第3 章改进的休h 民唤醒协议l6 3 1 双射频休眠唤醒协议1 6 3 2s t e m t d m 基本原理18 3 3 性能分析2 0 第4 章基于图着色的链路调度协议2 3 4 1 系统模型与假设2 3 4 1 1 网络模型2 3 4 1 2 冲突模型2 4 4 2 中心式图着色链路调度协议一2 5 4 2 1 冲突图的生成2 5 山东人学硕士学位论文 4 2 2 中心式调度协议2 6 4 3 分布式图着色链路调度协议2 8 4 4 性能分析3 0 第5 章总结与展望3 4 参考文献3 5 致谢3 8 山东大学硕士学位论文 c o n t e n t s a b s t r a c t i i c h a p t e r1i n t r o d u c t i o n 1 i io v e r v i e wo f w i r e l e s ss e n s o rn e t w o r k s 1 1 1 1c o n s t r u c t i o na n df u n c t i o no fw i r e l e s ss e n s o rn e t w o r k s 1 1 i 2k e yi s s u e so f w i r e l e s ss e n s o rn e t w o r k s 3 1 2e n e r g y s a v i n gt e c h n o l o g i e so f w s n 4 1 2 1e n e r g yc o n s u m p t i o n so f w s n 4 1 2 2c l a s s i f i c a t i o no f e n e r g y s a v i n gt e c h n o l o g i e s 5 1 3o b j e c t i v eo f t h i sp a p e r 8 c h a p t e r2e n e r g y e f f i c i e n tt r a n s m i s s i o np r o t o c o l so fw s n 10 2 1c e n t r i l i z a e dc o n t r o la n dd i s t r i b u t e dc o n t r o l 10 2 2s l e e p w a k e u pp r o t o c o l sb a s e do nc o m p e t i t i o nm e c h a n i s m 10 2 3s c h e d u l i n gp r o t o c o l sb a s e do na l l o c a t i o nm e c h a n i s m 12 2 4e v a l u a t i o no f t r a n s m i s s i o np r o t o c o l s 1 4 c h a n p t e r3i m p r o v e ds l e e p w a k e u pp r o t o c o l 16 3 1d o u b l e r a d i os l e e p w a k e u pp r o t o c o l s 16 3 2b a s i cp r i n c i p l eo fs t e m t d m 18 3 3p e f o r m a n c ee v a l u a t i o n 2 2 0 c h a p t e r 4l i n ks c h e d u l i n gp r o t o c o lb a s e do ng r a p h c o l o r i n g 2 3 4 1s y s t e mm o d e l sa n da s s u m p t i o n s 2 3 4 1 1n e t w o r km o d e l 2 3 4 1 2c o n f l i c tm o d e l 2 4 4 2c e n t r i l i z e dl i n ks c h e d u l i n gb a s e do nv e r t e xc o l o r i n g 2 5 4 2 1f o r m u l a t i o no f c o n f l i c tg r a p h 2 5 4 2 2c e n t r a l i z e ds c h e d u l i n gp r o t o c o l 2 6 山东大学硕士学位论文 4 3d i s t r i b u t e dl i n ks c h e d u l i n gp r o t o c o lb a s e do nv e r t e xc o l o r i n g 2 8 4 4p e f o r m e n c ee v a l u a t i o n 3 0 c h a n p t e r5c o n c l u s i o n s 3 4 r e f e r e n c e s 3 5 a c k n n o w l e d g e m e n t s 3 8 山东大学硕士学位论文 摘要 能耗控制是无线传感器网络应用中需要解决的首要问题。本文针对无线传感 器网络中数据传输能耗显著的问题，提出了一种改进的休眠唤醒协议和一种基于 图着色方法的链路调度传输协议。休眠唤醒协议通过降低空闲侦听频率达到降低 传输能耗的目的，s t e m ( s p a r s et o p o l o g ya n de n e r g ym a n a g e m e n t ) 是一种典型的 分布式、按需休眠唤醒协议，但其双射频传输方案使其适用范围受到限制。本文 采用时分复用方法对s t e m 进行了改进，提出使用单射频天线的s t e m t d v ( s t e m t i m ed i v i s i o nv a r i a t i o n ) 协议，扩大了分布式按需休眠唤醒协议的应用范 围。由于休眠唤醒协议并不能彻底解决无线传输冲突，本文进一步提出了一种链 路传输调度协议v c l s ( v e r t e xc o l o r i n gb a s e dl i n ks c h e d u l i n g ) 。v c l s 协议将图 顶点着色方法应用于无线网络的链路调度，可实现无冲突的链路时隙分配，避免 了传输冲突引起的分组重传及高能耗问题。为避免中心式调度协议中的长距离多 跳分组转发引起的延迟及丢包问题，文中给出了v c l s 协议的分布式算法，并引 入了两种保障机制用于提高染色成功率。网络仿真结果表明，改进的休眠唤醒协 议s t e m t d v 的节点能耗比原有的双射频休眠唤醒协议更低；提出的基于图着 色方法的链路调度协议v c l s 在能耗、空间重用率和丢包率等方面效果优于传统 链路调度协议i h l s 和d r a n d 。 关键词：高能效传输，休眠唤醒协议，链路调度，图着色，无线传感器网络 山东大学硕士学位论文 a b s t r a c t e n e r g yc o n t r o li so n eo ft h ek e yi s s u e sn e e dt ob es o l v e di nt h ea p p l i c a t i o n so f w i r e l e s ss e n s o rn e t w o r k s t h i sp a p e ra i m sa tc o n t r o l l i n go fd a t at r a n s m i s s i o ne n e r g y w h i c hi sr e m a r k a b l ei ne n e r g yc o n s u m p t i o no fw i r e l e s ss e n s o rn e t w o r k s a ni m p r o v e d s l e e p w a k e u pp r o t o c o la n dav e r t e xc o l o r i n gb a s e dl i n ks c h e d u l i n gp r o t o c o la r e p r o p o s e di nt h i sp a p e r t h es l e e p w a k e u pp r o t o c o l sr e d u c et r a n s m i s s i o ne n e r g yc o s t b y d e c r e a s ei d l e l i s t e n i n gf r e q u e n c y s t e m ( s p a r s et o p o l o g y a n de n e r g y m a n a g e m e n t ) p r o t o c o li sat y p i c a ld i s t r i b u t e d ，o n - d e m a n ds l e e p w a k e u pp r o t o c o l w h i c hu s e st w or a d i o si ni t sa p p l i c a t i o n s t h ep a p e ri m p r o v e st h es t e mp r o t o c o l u s i n gt i m ed i v i s i o nm e t h o da n dp r o p o s e ds t e m - - t d v ( s t e m t i m ed i v i s i o n v a r i a t i o n ) p r o t o c o l ，w h i c hm a k e st h eo r i g i n a ls t e mp r o t o c o ls u i t a b l ef o rs i n g l er a d i o n e t w o r k s t oa v o i dt r a n s m i s s i o nc o n f l i c ti nw i r e l e s ss e n s o rn e t w o r k s ，t h ep a p e r f u r t h e rp r o p o s e sah i g he n e r g y e f f i c i e n tl i n ks c h e d u l i n gp r o t o c o lv c l s ( v e r t e x c o l o r i n gb a s e dl i n ks c h e d u l i n g ) t h ev c l sp r o t o c o la d o p t sv e r t e xc o l o r i n gm e t h o d i nl i n ks c h e d u l i n go fw i r e l e s sn e t w o r k s ，a n dc a no b t a i nc o n f l i c t - f r e et i m e s l o t a l l o c a t i o nf o rw i r e l e s sl i n k s ad i s t r i b u t e di m p l e m e n t a t i o no ft h ev c l sp r o t o c o li s s h o wi n t h i sp a p e r , w h i c hc a na v o i dd e l a ya n dp a c k e tl o s sp r o b l e m sc a u s e db y l o n g - d i s t a n c em u l t i h o pf o r w a r d i n gi nc e n t r a l i z e di m p l e m e n t a t i o n s i m u l a t i o nr e s u l t s s h o wt h a tt h ei m p r o v e ds l e e p w a k e u pp r o t o c o ls t e m - t d vh a sal o we n e r g yc o s t t h a nt h eo r i g i n a ld o u b l e r a d i os c h e m e ，a n dt h ep r o p o s e dv c l sp r o t o c o lh a sb e t t e r p e r f o r m a n c et h a nc o n v e n t i o n a ls c h e d u l i n gp r o t o c o l ss u c ha si h l sa n dd r a n di n e n e r g yc o n s u m p t i o n ，s p a c er e u s er a t ea n dp a c k e tl o s sr a t e k e yw o r d s ：e n e r g y - e f f i c i e n tt r a n s m i s s i o n ，s l e e p w a k e u pp r o t o c o l ，l i n ks c h e d u l i n g ， v e r t e xc o l o r i n g ，w i r e l e s ss e n s o rn e t w o r k s 第1 章绪论 1 1 无线传感器网络概述 1 1 1 无线传感器网络组成及功能 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 是由多个通过无线通信系 统连接的感知节点构成的用于信息感知、环境监测和数据采集等功能的网络系 统。因其成本低廉、易于架设、分布范围广、可无人值守等特点，无线传感器网 络在军事国防、工业控制和检测、智能家居和消费电子、物资跟踪和供应链管理、 智能农业和环境感知、灾害预警等诸多领域的应用价值同趋显著【i 】。 无线传感器网络通常由数十个至数百个不等的无线节点形成自组织网络，节 点之间通过无线方式通信。通常网络中有感知节点( s e n s o rn o d e ) 和汇聚节点( s i n k ) 两类无线节点，在分层传感器网络中还有用作簇内控制的簇首节点。装备有传感 器的感知节点用于采集环境信息，并将采集的数据以无线传输方式发送给汇聚节 点；汇聚节点和远端服务器相连，用于进行环境信息的处理或节点的任务调度等 1 2 】。一般的传感器网络中有一个或有限的几个汇聚节点，感知节点的数量由几十 个至几百个不等。图1 为一个典型的无线传感器网络的示意图。 图l 无线传感器网络体系结构示意图 无线节点是无线传感器网络的重要组成部分，一个典型的无线节点通常由感 知单元、中央处理单元、无线传输单元以及供电系统等几部分功能单元构成【3 1 。 图2 显示了一个无线节点的功能结构，其中感知单元用于从环境获取信息及数 据，将外部的模拟信号转换为微控制器町处理的数字信号；中央处理单元用于节 点行为控制以及x c n 采集数据的处理，如数捌融合；无线传输单元通过射频传输 山东大学硕上学位论文 线 图2 一个典型无线节点的功能结构 将环境信息或采集的数据传递给远端的汇聚节点；供电系统为无线节点提供正常 工作所需电源：此外，无线节点根据应用需要还可能具备定位系统单元和用于移 动节点的传动装置单元等。 不同应用对无线传感器网络的要求也不尽相同。从网络规模看，可能从十几 个节点到几百甚至几千个节点；从网络寿命看，可能从几个月至几年甚至几十年； 从网络传输的数据量看，可从比特级到几千比特级甚至兆比特级f 4 1 。为满足应用 需求，无线传感器网络通常具备以下几个特点1 1 ： ( 1 ) 低功耗 w s n 通常在部署之后需要长期运行，不便于进行电池更换或充电，因此， 网络必须尽可能地节省能量。w s n 通常要求比现有无线通信系统( 如蓝牙、w i f i 等) 具有更低的功耗，以保证较长的网络寿命。 ( 2 ) 低成本 w s n 应用中通常需要部署大量无线节点( 如军事目标追踪、森林环境检测 等) ，且节点不易回收，高成本的无线节点将阻碍w s n 的应用推广。 ( 3 ) 便于定位 因在应用中节点数量多、部署环境不便人工介入( 如高压电站、远洋运输等) ， 部署后的无线节点应能够进行自身定位，实际应用中，可借助全球定位系统 ( g l o b a lp o s i t i o n i n gs y s t e m ，g p s ) 等现有定位系统实现节点定位，但某些情况下 g p s 定位精度不够高，通常需要更符合w s n 应用要求的定位算法。 ( 4 ) 低吞吐量 为最大程度降低传输功耗，现有w s nm 议( 如z i g b e e ) 不支持太高的数据 传输速率，冈此要求无线节点对采集的数掘进行分析处理后传送，并尽可能降低 山东人学硕士学位论文 传输开销。无线节点需借助特定的数据融合算法减少待传数据量。 此外，根据某些特殊应用的要求，w s n 还需考虑安全性、移动性和低传输 延迟等方面的问题。如在军事应用中，要求无线数据传输有较高的安全保证；在 物资跟踪应用中，无线节点会因物资运输而产生地理位置变化，要求网络能够适 应节点移动变化；在部分实时监测应用中，要求无线传输的延迟尽可能地小，防 止因高延迟引起的数据误判等操作。 1 1 2 无线传感器网络的关键问题 针对以上提出的应用特点以及无线传感器网路的自身构成特点，在无线传感 器网络中，有以下关键技术问题需要考虑。 ( 1 ) 能耗控制 无线节点电池电量的耗尽预示着无线网络寿命的终止，因此，w s n 的能耗 控制是最为关键的问题。为降低节点能耗、延长网络寿命，研究人员已提出了一 系列高能效控制协议，如网络拓扑控制、启发式的节点唤醒和休眠机制、网络传 输调度机制等【2 ，5 一。为延长网络寿命，一方面，可采用高能效的网络控制协议。 另一方面，可通过电池电量的持续补给到达维持网络长期运转的目的，相关学者 已经开展了通过从周边环境收集能量( 如太阳能) 来维持无线节点电量供给的研 究【7 】。 ( 2 ) 路由算法 w s n 由于能量受限及节点数目较多，其路出算法不同于普通无线网络，应 尽可能地降低路由开销，最大程度地节省能量，并着力解决无线节点问的数据汇 聚及转发问题，保证普通节点和汇聚节点之问及时有效的数据传输。路由算法还 应考虑能量均衡问题，尽可能地降低树形拓扑网络中漏斗效应( f u n n e l i n ge f f e c t ) r 8 】 对网络寿命的影响。此外，在移动传感器网络中，还要求路由算法能够根据节点 位置实时更新路由。 ( 3 ) 节点定位 通常，无线节点的位置信息是所采集数据的组成部分。在某螳应用中，如目 标实时跟踪、辅助路由、目标轨迹预测等，均需要收集每个铬点的位置信息f 9 1 。 冈此，w s n 要求无线符点自身能够进行i f 确的定位。 3 山东大学硕：t 学位论文 ( 4 ) 数据融合 减少传输的数据量可以有效降低能耗，且通常无线节点采集的数据中存在较 多冗余信息，因此，无线节点在从环境收集数据后，需要借助数据融合算法去除 冗余信息，压缩待传数据量，从而减少传输负担，达到节能目的。 ( 5 ) 时间同步 w s n 中各无线节点之间以及普通节点与汇聚节点之间需要协同工作，需要 统一的时钟节奏。时间同步技术重点解决无线节点的时钟漂移以及频率偏移问 题，避免或降低时钟误差引起的网络时间失调。 此外，无线传感器网络还需要综合考虑网络连通性、信道分配、网络安全， 无线传输技术等许多其它方面的技术问趔1 0 ，1 。 1 2 无线传感器网络节能技术 能耗控制是无线传感器网络需要解决的首要问题，本文围绕网络能耗展开研 究，本节重点介绍无线传感器网络的能量消耗来源以及现有的几类能耗控制协 议。 1 2 1 无线传感器网络能耗来源 无线传感器网络的能量消耗主要来自数据传输、数据处理和数据感知，其中， 传输能耗是传感器网络的最主要能耗，是指无线数据收发过程中的射频天线的能 量消耗。实验结果显示数掘传输耗能较大，而数据处理与感知耗能较小，发送 l b i t 信息消耗的能量大概是处理1 0 0 0 条操作所需的能量【2 1 。 网络运行过程中，无线节点的传输单元有发送、接收、空闲及休眠四种可能 的运行状态。表1 给出了两种不同的无线网络中无线节点在各状态下的能耗，第 一列为运行8 0 2 1 1 协议的无线网卡功耗【1 3 l ，第二列为w i n s 无线节点功耗1 1 羽。 数据表明，无线节点在传输单元睡h 民状念的能耗比重较小，与数据处理及感知能 耗相当，而发送、接收及空闲状态能耗比重较大，传输单元空闲状念的能耗接近 于节点在收发状念的能耗。无线节点在无线数据的收发阶段需丌启射频天线，该 阶段的能量消耗不可避免。由于节点在空闲状态需要丌启射频天线侦听信道，空 - 闲状态也将产q t 大量能耗。冈此，在节点的空闲状念降低侦听频率，尽可能地关 4 山东大学硕十学位论文 闭天线可以有效地降低无线传输能耗。 表l 无线节点不同运行状态功耗 功率值( m w ) 节点状态 8 0 2 1 1 无线网卡w i n s 无线节点 发送 1 3 0 09 8 6 接收 9 0 07 5 l 空闲7 4 07 2 7 睡眠4 76 4 1 2 2 节能技术分类 无线传感器网络的能量优化涉及硬件平台、应用软件、网络协议等多个方面， 不仅要考虑单个节点上的能量消耗，还要设法使整个网络的生存时间最大化。这 会牵扯到网络设计和运行的每个阶段，需要在能量消耗、系统性能和运行稳定性 之间做出合理取舍【1 2 】。无线传感器网络节能技术按照应用范围可分为节点级能 量优化和网络级能量优化；按照应用阶段可分为针对数据处理和针对数据传输的 节能技术。 节点级能量优化主要针对无线节点的硬件平台，目的在于降低单个节点的功 率消耗。当前，节点级能量优化主要有以下几种技术。动态电源管t - 里( d y n a m i c p o w e rm a n a g e m e n t ，d p m ) 技术旨在关闭空闲状态组件以节省能量f 1 。动态电压 调节( d y n a m i cv o l t a g es c a l i n g ，d v s ) 技术通过优化活动状态组件的能量消耗、动 态调节电源电压和运行频率来适应即时处理需要，避免器件一直工作于最优性能 而耗费过多能型”】。典型的无线节点对每个收到的分组，不管其最终目的地， 都要进入计算子系统处理，而实际上6 5 的分组要转发出去，针对数据处理能耗 的智能射频硬f l ：( i n t e l l i g e mr a d i oh a r d w a r e ) 允许在通信子系统内部标定和重定向 分组，而不用打扰计算予系统的睡h 民，从而节省能量f l 们。无线传输使用不同调 制方式消耗的能量也不相同，调制级别高时，能耗也高，针对数据传输能耗的调 制调节( m o d u i a t i o ns c a l i n g ，m s ) 技术通过自适应地改变调制级别以降低能耗m 。 单独节点级能量优化技术如d v s 和m s 技术，以传输延迟的增加为代价换 取功耗的降低。数据处理和数据传输折中的协同功率管理技术将算法计算量分布 到多个无线常点中实现爻：行计算，可减小数据处理带来的传输延迟，进一步降低 能耗，彳日分布式的计算义增加了节点的通信量。所以能量优化算法的设计需要在 气 山东大学硕士学位论文 数据处理和数据传输之间获得较好取舍，进行节点级的协同能量管理，即进行网 络级的能量优化。 。 网络级的能量优化技术可分为三大类，即网络拓扑控制、休眠唤醒协议以及 传输调度协议。 ( 1 ) 网络拓扑控制 通常无线传感器网络的节点是随机部署的，为防止节点失效，一般会部署比 实际需要更多的无线节点，因此网络含有很大冗余度。高密度的无线传感器网络 中，并非所有节点需要作为数据从源节点到汇聚节点传输的路由【1 8 】。网络拓扑 控制的目的是根据应用需要，动态调节网络拓扑，使网络在数量最少的激活节点 下正常运行。拓扑控制协议通过选择保证连接的最优节点子集，去除网络的冗余 节点或链路，达到降低网络能耗，延长网络寿命的目的。 拓扑控制协议有基于地理位置和基于节点连接的两类协议。基于地理位置的 拓扑控制协议根据已知的节点位置计算能够保证网络连通或数据传输路由完整 性的网络拓扑，以此得到每个节点在特定时间的激活和休眠状态1 6 】。基于节点连 接的拓扑控制将一部分初始节点置为激活状态，而后根据网络流量情况动态地调 整其它无线节点的激活睡眠状态，以随时满足网络连通性或完整的网络覆盖1 1 9 1 。 使用拓扑控制协议的网络生存时间与节点密度有关，一般来讲，使用拓扑控 制的无线传感器网络寿命通常比所有节点都激活的无控制协议网络的寿命长2 3 倍。但单纯的拓扑控制仍不能满足实际应用需要，拓扑控制协议还须与其它节能 技术结合，但多种节能方案的结合又有可能导致未知结果【2 1 。 ( 2 ) 休眠唤醒协议 休眠唤醒协议可与拓扑控制相互补充，用于更改激活节点的休眠唤醒状态， 使得通过拓扑控制协议选出的激活节点不必一直丌启射频天线，在没有网络活动 时可将激活节点也置为睡眠状态。休h 民唤醒协议对节点工作占空比进行调节，工 作占空i ：i , ( d u t yc y c l e ) 是指节点生命周期中活跃时问的比值，无线节点根据网络流 量情况在激活和睡眠周期问转换。该类协议的休u e 唤醒调度使节点运行在较低 的工作占空比时也能保证分组的顺利转发。 现有的休眠唤醒协议根据其实施的网络层次可分为完全集成剑媒体接入控 制层( m e d i aa c c e s sc o n t r o l ，m a c ) 的休眠唤醒协议和在m a c 层之上( 通常是网络 6 山东大学硕：t 学位论文 层或应用层) 运行的独立休眠唤醒协议。独立的休眠唤醒协议不考虑网络拓扑和 连接，更加灵活，可在不同m a c 层之上使用。独立的休眠唤醒协议有按需唤醒 协议、约定调度唤醒协议和异步唤醒协议三类。 按需唤醒协议中，无线节点仅当其它节点想要与其通信时才唤醒。该类协议 通常要求无线节点装备具有不同能耗性能比的两根射频天线，低速率、低功率 天线用于信号指示，高速率、高功率天线用于数据通信。信号指示天线检测到通 信需求时便开启数据通信天线1 2 0 】。约定调度协议中，无线节点和其邻居在某个 约定时间同时唤醒，并保持一段活动时问用于和邻居交换信息，然后再次进入睡 眠状态，直到下次约定调度到来【2 1 ，2 2 1 。异步唤醒协议保证无线节点与其邻居节 点有交叠的激活周期，允许节点可在其需要时独立于其它节点并仍能与其邻居通 信的时候唤醒，数据在邻居交叠的唤醒周期内进行传送f 2 3 1 。 按需唤醒协议中，无线节点拥有最短的激活时间，使得节能最大化。但该协 议要求无线节点具备双射频天线，限制了其应用范围。约定调度协议最方便，适 合数据聚合并支持网络广播，但需要节点间的时间同步，防止节点问约定时间产 生误差。异步唤醒协议对时间同步的要求较宽松，且比同步的约定协议更能适应 频繁的拓扑变化，但节能效果不如约定调度协议，且异步协议不支持网络广播。 ( 3 ) 传输调度协议 传输调度协议采用时分复用多址访问( t i m ed i v i s i o nm u l t i p l ea c c e s s ，t d m a ) 的方式对网络数据流进行时隙划分，无线节点或者无线链路只在安排的特定的时 隙内进行数据传输，在无数据传输动作的空闲时隙可关闭射频天线以降低能耗。 传输调度协议可分为针对节点和针对链路的两类调度协议。文献 2 4 ，2 5 便 是典型的针对节点的传输调度。在针对节点的传输调度中，无线节点的数据流量 大小决定其获得的时隙数的多少，各节点在自己获得的可利用时隙内自行安排自 己各条链路的收发，且要处理好与邻居节点的传输冲突。无线节点在自行安排链 路传输时隙过程中，必须和邻居节点通信以保证链路首尾节点动作一致。而针对 链路的传输调度直接将每条无线链路作为调度对象，协议的算法执行完后产生的 时隙划分方案可以直接用于数据传输，无线节点不必再自行为本地链路安排收 发。文献1 2 6 ，2 7 1 采用了针对链路的传输调度方案。 传输调度协议针对无线传感器例络最丰要的空闲侦听能耗进行优化，时隙划 7 山东大学硕_ ：学位论文 分方案可以显著降低无线传输能耗，并能最大程度地降低传输冲突，避免因冲突 产生的分组重传，提高数据正确率。相比于针对节点的调度方案，针对链路的传 输调度目标更加具体，通过算法直接为链路安排时隙可避免邻居无线节点之间过 多的数据交换，从而降低传输能耗。 ( 4 ) 其它网络优化技术 除上述网络级的能量优化技术，还有专注于数据感知能耗以及利用移动无线 节点的网络节能技术f 2 1 。传感器节点采集的样本数据一般会有很强的空时相关 性，没必要将所有数据发送给汇聚节点。数据感知能耗包括冗余数据的传输能耗 和感知子系统的能耗两方面，虽然对冗余样本数据的感知能耗可忽略，但冗余数 据的传输仍会产生较大能耗。基于数据预测方法的感知能耗优化技术用于减少样 本数据量，去除冗余数据，同时在应用可接受的范围内保证数据准确度。 树形拓扑传感器网络中存在传输漏斗效应，一部分路由为数据汇聚必经之 地，导致该路由上节点负载过重，靠近汇聚节点的无线节点过早耗尽电量，从而 影响整体网络寿命。若将网内一部分节点( 多为汇聚节点) 作为移动节点，负责直 接从静止节点收集数据，静止节点等待移动节点的经过并与其进行数据传输，则 无线通信距离会大幅缩短( 单跳或者跳数较少的多跳) 。无线节点会因为通信距离 的缩短、通信竞争强度的降低和数据转发开销的减少而大幅降低能量消耗。此外， 利用移动无线节点的节能技术可以均匀网络范围内的路由负载，避免传输漏斗效 应的影响，整体延长网络寿命 2 8 】 1 3 本文研究目标 如前文所述，无线传感器网络的无线传输能耗为最主要能耗，而降低无线节 点的空闲状态侦听频率可显著减少传输能耗。降低空闲侦听频率的最直接方式是 采用休眠唤醒协议，即无线节点根据网络数据流情况在激活和休眠状态问转换， 休眠期间关闭射频天线、不进行空闲侦听。由于休眠唤醒协议需要在激活周期进 行基于竞争的数据收发，可应用于存在移动节点的无线传感器网络，但竞争机制 将导致数据传输产生冲突和碰撞，无法避免数据重传。且在固定周期的休眠唤醒 协议中，节点不能最大程度地自适应网络信息流，存在分组传输延迟长的缺点。 而基于时隙分配机制的传输调度协议，由于为网络数据流规定了动作时隙，传输 8 山东大学硕。 二学位论文 过程中不会出现冲突、碰撞，因此避免了数据重传，即降低了能耗又提高了数据 传输正确率。传输调度协议中，无线节点在无传输动作的空闲时隙也将关闭射频 天线，不进行空闲侦听。相比于休眠唤醒协议，传输调度协议能够更大程度地降 低能耗，但仅适用于无移动节点的静态传感器网络。 本文针对无线传感器网络的传输能耗，研究适用于多跳可拓展无线传感器网 络的网络级能量优化技术，根据数据采集型传感器网络的树形拓扑、后向数据流 等自身特点，设计两种分布式、低能耗的传输方案。所设计传输方案运行在m a c 层之上的网络层或应用层，以便于在具有不同m a c 层的无线网络中使用。由于 网络拓扑控制协议旨在降低网络冗余，其单独运行的节能效果有限，本文主要研 究基于竞争机制的休眠唤醒协议和基于分配机制的传输调度协议。双射频的按需 休眠唤醒协议是一种分布式、低延迟的能耗优化技术。本文提出使用单射频天线 的同步传输按需唤醒协议，使原有的双射频传输协议在能耗不增加的前提下可用 于单射频无线传感器网络，扩大了其应用范围。但休眠唤醒协议依赖m a c 的竞 争机制，仍存在传输冲突。为避免传输冲突，最大程度地降低网络能耗，本文设 计一种针对链路的传输调度协议。链路调度协议通过分布式的邻居消息交换获得 调度需求信息，借助图着色方法为每条无线链路进行无冲突的时隙分配。无线链 路仅在动作时隙进行传输，从而避免传输碰撞及数据重传能耗，无传输动作的空 闲时隙节点将关闭天线以降低能耗。 9 山东人学硕士学位论文 第2 章无线传感器网络的高能效传输协议 国内外学者已经针对无线传感器网络的低能耗传输做了大量研究，并提出了 许多不同的低能耗方案。在无线传感器网络现有的网络级能量优化技术中，基于 竞争机制的休眠唤醒协议和基于分配机制的传输调度协议是两类有效的节能传 输方案。前者为节点划分固定或自适应变化的激活、睡眠周期，激活周期用来进 行基于竞争的数据传输，睡眠周期关闭天线以节省能量，典型协议有s m a c l 2 9 ， a s l e e p r l l ，s t e m 2 0 】等。后者按照时分复用方式为节点或链路划分调度时隙， 节点在特定时隙内执行相应的调度动作( 发送、接收或睡眠) ，这类协议有f p s l 2 2 1 ， d r a n d t 2 5 1 ，i h l s 2 7 】等。 2 1 中心式控制与分布式控制 无线传感器网络中的传输控制协议一般有中心式和分布式两种实现方案。 在中心式的实现方案中，每个无线感知节点均需要将其自身信息发送给多跳 以外的汇聚节点，汇聚节点收集到整个网络的信息后，运行特定的协议控制算法， 并得到控制结果。为使全网节点按照既定控制结果传输，汇聚节点还需把控制结 果发送给各无线感知节点。在网络的整个运行过程中，若需根据网络结构或流量 的实时变化调整控制结果，则每次均需要感知节点和汇聚节点进行来往通信。 分布式的实现方案允许无线节点根据局部网络信息在本地运行控制算法。无 线节点通过与其邻居节点的信息交换获取局部网络信息，根据局部信息以及与邻 居节点的协调执行控制算法，节点可直接执行本地得到的控制结果。分布式的实 现方案中不存在感知节点与汇聚节点间的长距离多跳转发，其控制结果送达率高 于中心式实现方案，适合在大规模网络中应用。 2 2 基于竞争机制的休眠唤醒协议 休h 民唤醒协议在无线网络的m a c 层采用载波监听多路访问碰撞避免 ( c a r r i e rs e n s em u l t i p l ea c c e s s c o l l i s i o na v o i d ，c s m a c a ) 机制，以供无线节点在 激活周期通过竞争方式争抢信道进行数据传输。 s m a c ( s e n s o r - m a c ) 协议足较早提 n 的针对多跳无线传感器网络的休眠唤 l o 山东大学硕士学位论文 醒协议。s m a c 将无线节点的运行时间划分为监听区、传送区和睡h 民区，分别用 于监听发送请求信息、传送感知数据和进入休眠状态。节点若有数据待传，会先 向邻居节点发送数据传送请求，传输过程中各节点通过m a c 层的竞争协议抢占 无线信道。接收数据的节点在监听区保持清醒，等待其它节点的发送请求，若收 到请求则在传送区进行数据收发；若在监听区未接收到其它节点发送请求，则在 接下来的传送区进入休眠状态1 2 9 1 。s m a c 可在一定程度上降低空闲侦听频率， 但存在网络延迟大、灵活性差、不能避免传输冲突等诸多不足。 d m a c ( d a t ag a t h e r i n gm a c ) 协议是基于s m a c 的改进协议。d m a c 加入了 数据预测和多数据待发机制，用于解决s m a c 中的睡h 民区延迟问题和树形拓扑 中的分支干扰问题；使用父、子级节点间交错的休眠唤醒周期代替s m a c 中固 定的工作周期划分，以降低分组转发延迟1 3 0 1 。d m a c 大大降低了s m a c 中的分 组传输延迟，但其交错唤醒机制要求网络时间同步；d m a c 中的周期长度仍是 固定的，无法适应网络流量变化；由于依赖m a c 层的竞争协议，d m a c 也无法 避免传输冲突。 a s l e e p ( a d a p t i v es t a g g e r e ds l e e pp r o t o c l ) 也采用了交错休眠唤醒机制，并 能根据数据流量和网络结构自适应调节工作区间和睡眠区问长度。a s l e e p 引入 睡眠预测算法估算下个周期的通信区间长度，以满足网络流量需求，引入睡眠协 调机制以提高通信成功概率1 2 。a s l e e p 的自适应区问长度调整保证激活区间长 度和实时数据流量所需的传输时间最小值一致，这种动态调整能够使无线节点更 大程度地进入休眠状态，比s m a c 和d m a c 显著降低了网络能耗；自适应的交 错唤醒机制缩短了分组传输的平均延迟；树型拓扑中同级别但不同父节点的子节 点的激活区问起始和结束时间不同，比区间长度固定的d m a c 协议更进一步减 少了传输冲突。但由于数据发送仍然依赖竞争机制，a s l e e p 仍不能完全避免传 输冲突。 s t e m ( s p a r s et o p o l o g ya n de n e r g ym a n a g e m e n t ) 是一种使用双射频天线的按 需休l i 比唤醒协议，其将s m a c 、d m a c 等单射频休眠唤醒协议中的发送请求空 闲侦听功能和数据传输功能分拆到两个独立的信道实现。无线节点具有唤醒信道 和数据信道两个信道，分别用于发送请求信号收发和感知数据传输。s t e m 在唤 醒信道上二采用异步工作周期，使