（通信与信息系统专业论文）无线传感网中基于能量的多信道接入分簇成链算法的研究与设计.pdf

摘要 摘要 无线传感器网络是由大量随机撒布在监测区域内的传感器节点协作感知、采 集、处理和传输监测信息的无线网络。现如今其已在军事国防、环境监测、生物 医疗、抢险救灾等各个领域中广泛应用。 传感器网络特别适合部署在恶劣环境或人类不宜到达的区域，然而这给其节 点能量的补给带来了很大的困难，因此，低功耗技术一直是无线传感器网络研究 的重点。 分簇算法被认为是目前为止传感网中最有效的协议，因此本文以节能为前 提，对基于能量的无线传感网分簇算法的研究现状展开分析：在路由层，一般分 簇算法能耗在簇首处过分集中，且需要频繁的簇重构；链式算法易形成局部长链， 同时存在传输时延大的缺陷。在m a c 层，现有分簇算法大多采用单信道接入，冲 突严重，降低了网络吞吐量的同时带来了能量浪费；一般分簇算法采用的t d m a 时隙分配的方式加重了簇首的负担：链式算法采用令牌机制不利于有效休眠机制 的引入，同时令牌的传递增加了额外开销。另外，如今大多数无线传感网算法研 究中都忽略了电池复杂的充放电特性，本文对此进行了详尽的分析，并确定了最 终采用的电池能耗模型。 鉴于无线传感网( w s n ) 很强的应用相关性，本文针对小规模周期性报告的应 用场景，提出一种新的算法m c l c 一既e d 。该算法以旺e d 为基础，在路由层簇内 引入贪婪算法形成链式拓扑结构，各链上剩余能量最大的节点担任簇首，负责收 集汇聚由链两端逐跳传递而来的数据。该方式缩短了节点间的通信距离，减小发 送功率，改善一般分簇算法中能耗在簇首过分集中的问题，使全网能量更加均衡。 另外结合m a c 层f d m a 多信道接入机制，各簇同时进行数据收集而不发生碰撞冲 突，节能并降低时延，同时本文针对m c l c 肛e d 算法特殊的拓扑结构设计了一 种簇内固定t d 姒时隙自动计算分配的方式，无需每次簇首轮换时为各节点重新 分配接入时隙，发送分配消息。此外，算法还综合考虑了电池的充放电特性，避 免节点过度放电，给予电池充分休息以恢复其表面活性物质浓度差。 本文的最后，通过n s 一3 仿真平台对m c 一腿e d 、m c b a i 卜脏e d 以及m c l c 一砸e d 摘要 算法的性能指标进行对比验证。仿真结果表明，m c l c 一肛e d 在以下几个方面都 表现出更为出色的效果：在网络生存时间方面，m c l c 一髓e d 算法比m c _ 皿e d 和 m c b a r _ 髓e d 分别提高了约7 0 和2 0 ；能量均衡方面，m c 一肛功及m c b a r 一腿e d 算法在全网4 0 节点死亡时，其余存活节点仍拥有不同程度的较高剩余能量，而 此时m c l c 一肛e d 算法的其余节点几乎同时频临死亡的边缘；另外，m c b a r _ 肛e d 算法的死亡节点极为集中，造成区域信息采集空洞，而m c 一旺e d 和m c l c 一脏e d 算法的死亡节点分布则较为平均，更有利于全网信息的全面采集。 关键词：分簇；链式；电池能量特性 a b s t r a c t w l r e l e s ss e n s o rn e t 、0 r k ( w s n ) i sak i n do f 谢r e l e s sn e 咖r kt 1 1 r o u 曲w i l i c ha l a r g em h n b e ro fs e n s o r sr 卸融o m l ys p r e a d i i lt l l em o n i t o r e dr e g i o ns e 璐e ，c o l l e c t p r o c e s sa n d 仃柚s m i tt h em o n i t o r i n gi n f b 册a t i o nc 0 0 p e r a t i v e l yn o w a d a y s ，w s nh 硒 b e e nw i d e l ya p p “e di nv a r i o u sf i e l d so fm i l i t a d ，d e f e n s e ，b i o l o g i c a la n dm e d i c a l 仃e 砌e n t ，e n v i r o 姗e n t a lm o n i t o r i n g ，d i s a s t e rr e l i e e e t c s e n s o rn e t w o r ki ss u i t a b l et od e p l o yi i lah a r s he n v i r o n m e n t0 r 曲屺a r e ah u m a n s h o u l dn o tr e a c he s p e c i a l l y h o w e v e r ，i tb r o u g h t 伊e a td i 伍c u i t i e st 0t h es e n s o rn o d e s f o re n e r g ys u p p l i e s ，s ol o 、- p o w e rt e c h n o l o g yh a sb e e nm ef o c u so ft h es t u d yf o r 、i r e l e s ss e n s o rn e 咖r l 【s c l u s t e r i n g 越g o r i t h mi sc o n s i d e r e d 舔t l l em o s te 饪i e c t i v ep r o t o c o li i ls e l l s o r n e t w o r k s t h e r e f o r c ，t h er e s e a r c hs i t u a t i o no fe n e r g y - b a s e dc l u s t e r i n ga l g o r i t h mi n w i r e l e s ss e n s o rn e t w o r ki s 锄a i v z e di nd e t a i l i nm i sa r t i c l e ：f o rr o u t i n gl a y e r ，t h e o v e r c o n c e n 仃a t i o no fe i l e r 鼢，c o n s u 】m p t i o na n df k q u e n tc l u s t e rr e c o n s t m c t i o ni s n e i e d e di ng e n e r a lc l u s t e r i n ga l g o r i t l l i i l s ；i ti se a $ t 0 疗0 mt i l e1 0 c a ll o n gc h a i l la n d i n c r e a l s et h e 仃a n s m i s s i o nd e l a yi nl i n l ( a 1 9 0 r i t h m s f o rm a cl a y e r ，s i n g l e - c h 锄e l a c c e s si sa d o p t e di nm o s to ft h ee x i s t i n gc l u s t e r i n ga 1 9 0 r i t 胁st 0b r i n gs e r i o u s c o n f l i c t s ，r e d u c e 龇n e t w o r kt l l r o u g h p u ta i l dr e s u l ti l le n e 聊w a l s t e t l l et d m as 1 0 t a l l o c a t i o nu s e di ng e n e r a lc l u s t e r i n ga 1 9 0 “m m sa g 伊a v a t e st l l eb u r d e no fc l u s t c r h e a d ；t h ct o k e nm e c h a n i s mu s e d i nl i n l ( a 1 9 0 r i t si sn o tc o n d u c i v et 0t h e i n 仃o d u c t i o n0 fa ne 虢c t i v em e c h a n i s mo fd o m 锄c y 锄dt h et o k c np a s s i n ga i s o i n c 陀弱e sm ee ) ( t r ac h 鹕e a d d i t i o m l l y ，t h i sp a p e r 锄a l y z e st 1 1 ec o m p l e xc h a 唱ea n d d i s c h a 唱ec t e r i s t i c so fb a t t e 巧i i ld e t a i l ，w h i c hi si g n o r e di i lm o s to fw i r e l e s s s e n s o rn e t 、o r ka l g o r i m m t h e nw ed e t e 咖i n et h ee v e n t u 甜a d o p t i o no fm eb a t t e 巧 e n e r g yc o n s u m p t i o nm o d e i b e c a u s es e n s o rn e r ki sah i 曲l yt 鹕e t e dn e t 、) v d r k ，t 1 1 i sp a p e rp r e s e n t e dan e w a l g o r i t h mm c l c h e e db 嬲e d 0 ns m a l l s c a l e 埘r e l e s s n s o rn e t w o r kw 量i i c h r e p o n e dm e s s a g ep e “o d i c a l l y n ea 1 9 0 r i t h mi s b a s e do nh e e d ，i 曲o d u c i n gm e g r e e d ya 1 9 0 r i t h f i li nt h er o u t i n gl a y e rt 0f 0 】强ac h a i nt o p o l o g ) ，i f lt h ec l u s t e r r n l e c l u s t e rh e a do ne v e 叮c h a i nw 汕t 1 1 em o s tr e s i d u a le n e r 斟i sr e s p o n s i b l ef o rc o l l e c t i n g d a t a g a t i l e r e dh o p - b y - h o p 丘o mm ec h a i l le n d s n i sm e t i l o ds h o n e nt 1 1 e c o m m u i l i c a t i o nd i s t a l l c eb e t 、) 旧e nn o d e s ，r e d u c et t l et r a n s m i s s i o np o w e r ，i m p r 0 et h e p r o b l e mt h a tt h ee n e f g yc o n s m n p t i o nj st 0 1 0c o n c e n 仃a t e di i lt h ec l u s t e rh e a da n ds o t h a tt h ee n e r g yo ft h ew h o l en 咖r kg e tm o r eb a i a n c e d i na d d i t i o n ，t h ea l g o r i t h l t l c o m b i n e sf d m am u l t i c h a n n e la c c e s sm e c h a l l i s m ，a n dc o l l e c t sd a t a 证e a c hc l u s t e ra t t t l es 锄et i i n ew i m o u tc o l l i s i o na n dc o n n i c tt os a v et l l ee n e r g y 觚dr c d u c et l l ed e la y m e a n w h i l e ， w e d e s i g n e d am e t h o d a c c o r d i n g t ot h e s p e c i a lt o p o l o 斟 0 f m c l c - h e e da l g o r i t h mt 0c a l c u l a t ea n da l l o ca _ t et h et d m af i x e dt i m es 1 0 t i l i a b s t r a c t a u t o m a t i c a l l v s 0t i l a ti td i dn o tn e e dt 0r e d i s t r i b u t et i l i l es 1 0 ta 1 1 ds e n d 邪s i 鲷m e n t m e s s a g et oe a c hn o d ew h e nt 1 1 ec l u s t e rh e a d sr ( 协t e i na d d i t i o n ，t h ec h a r g ea l l d d i s c h a r g ec h a r a c t e r i s t i c so fb a t t e r yw e r ec o n s i d e r e dm 廿l i sa l g o r i t l l mt 0a v o i d e x c e s s i v ed i s c h 唱ef o rn o d e sa n dg i v et i l eb a ：t t e 巧e n o u 曲r e s tt 0r e s t o r ei t sd i s c h a 唱e l o s s f i n a l l y ，w ed r e wac o m p a r i s o nw i t l lm ep e 墒r m a n c eo ft l l em c h e e d 、 m c b a r - 脏e da n dm c l c 旺e da l g o r i t h mt h r o u g i ln s 3c o m p u t e rs i m u l a t i o n p l a t f o m s i m u l a t i o nr e s u l t ss h o w e dt l a tt h em c l c h e e dp e 响m sm u c hm o r e e x c e l l e n tt 1 1 a nt h eo t h e rt v 旧a l g o r i t h m sa t t 1 1 ef o l l o w i n gf a c t o r s ：m c l c - h e e d p r o l o n g e dt h en e 似o r kl i f e t i m em o r et l a n7 0 锄d2 0 t i l a l lt 1 1 ea l g o r i t l l m so f m c h e e da n dm c b a r h e e ds e p a r a t e l v ：、矾1 e nt i l en u m b e ro fd e a mn o d e sw 觞u p t 04 0 o ft h et o t a ln o d e s ，t i l er e s to fs u n r i v a ln o d e ss t i l lh a dv e r yh i g hr e s i d u a le n e r g y i nt h em c h e e d锄dm c b a r - h e e d ，w h i i et h er e m a i n i n gn o d e si nt h e m c l c - h e e da l g o r i t h mw e r ea l m o s tn e a rt h ed y i i l gp o i n ta tt 1 1 es 锄et i m e ：i i l a d d i t i 0 1 1 t i l ed e a t hn o d e s 盯ed i s t r i b u t e de v e n l yi nm c h e e da n dm c l c 艇e d ， w h i l e 也ed e a ：c hn o d e sa r ee x = i r e m e l yc o n c e n t r a t e di nt h em c b a r - h e e da l g o r 甜蚰t 0 f o r mt l l eh o l l o wo ft 1 1 ei n f o m a t i o nc o l l e c t i o na r e ae a s i l v w h i c hi sn o tc o n d u c i v et 0a c o m p r e h e n s i v ec o l l e c t i o no fn e 咖r ki o n n a t i o n k e yw o r d s ：c i u s t e r i n g ；l i n l ( ；b a 位e 叮e n e e 斟c h a r a c t e r i s t i c s 第l 章绪论 第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 ，w s n ) 作为“物联网” ( i n t e r n e to ft h i n g s ，i o t ) 中最基础的关键环节，获得了社会各界的广泛关注。 早在1 9 9 9 年美国召开的移动计算和网络国际会议上，就提出“传感网是下 个世纪人类面临的又一个发展机遇”；2 0 0 3 年，美国技术评论杂志提出“传 感网络技术将是未来改变人们生活的十大技术之首”；2 0 0 5 年，突尼斯举行的信 息社会世界峰会( w s i s ) 上，国际电信联盟( i t u ) 发布i t u 互联网报告2 0 0 5 ： 物联网，正式提出了“物联网”的概念。 美国总统奥巴马就职后，在和工商领袖举行的圆桌会议上，提出了被美国人 认为是振兴经济、确立全球竞争优势关键战略的“智慧地球”的概念；2 0 0 9 年8 月中国国务院总理温家宝视察中科院无锡微纳传感网工程技术研发中心，提出尽 快建立中国的传感信息中心，并形象地称之为“感知中国”中心；2 0 0 9 年9 月 1 1 日，“传感器网络标准工作组成立大会暨感知中国高峰论坛”在北京举行， 标志着传感网标准工作组的正式成立n 3 。 中国在2 0 1 0 年远景规划和“十五”计划中，将传感器列为重点发展的产业 之一；与此同时，中国下一代互联网项目、国家自然基金项目都十分支持w s n 的研究，国家发改委在下一代互联网( c n g i ) 示范工程中，也部署了w s n 的相关课 题羽。 此外，日本、韩国等也分别提出了“u - j a p a n ”、“u - k o r e a ”战略口1 。 现如今，全球对传感网这项新兴技术倾注的热情与关注，预示着“传感网” 必将是未来信息革命的发展方向，是继计算机、互联网与移动通信网后的又一次 信息产业浪潮。它可以使人们在任何时间、地点以及任何环境条件下，获取大量 详实可靠的物理世界信息，这种具有智能获取、传输和处理信息能力的无线传感 网，正在逐步形成i t 领域的新兴产业h 3 。 无线传感网中基于能量的多信道接入分簇成链算法的研究与设计 1 1 2 无线传感器网络体系结构及特点 1 无线传感器网络的体系结构 ( 1 ) 网络拓扑结构 如图卜l 所示，w s n 由大量随机部署在监测区域内的集成有传感器、数据处 理单元和通信模块的微小传感器节点通过自组织的方式构成网络，借助于节点中 内置的形式多样的传感器，协作地实时感知、采集、处理网络覆盖区域内人们感 兴趣的物质对象信息，并通过多跳的无线通信方式，将收集处理后的信息传输到 网关( 汇聚节点) ，网关通过这个传输网络将感测数据从传感区域发送到提供远 程连接和数据处理的基站，基站再通过i n t e r n e t 连接到远程数据库，最后将采 集到的数据经分析、处理后通过一个界面提供给终端用户暗m m 。过去的几年中， 作为一种新的信息获取方式和处理模式，无线传感器网已经引起了研究界的广泛 关注，促使大量新应用的诞生。 图1 1 无线传感器网络通信结构 ( 2 ) 通信协议栈 无线传感器网络典型的通信协议栈既参考了t c p i p 和o s i 模型架构，同时 又包含了传感网络特有的电源管理、移动管理及任务管理，如图卜2 。应用层为 不同应用提供一个相对统一的高层接口；如若需要，传输层可为传感网络保持数 据流及保证与i n t e r n e t 的连接；网络层主要关心数据的路由方式；数据链路层 协调无线媒质的访问，尽量减少相邻节点信息传输时的冲突碰撞；物理层为系统 2 第l 章绪论 提供了一个简单稳定的调制、传输和接收系统；此外，电源、移动和任务管理负 责传感节点能量、移动和任务分配的监测，帮助传感节点协调感测任务，尽量减 少整个系统的功耗等等墙钔。 图卜2 无线传感器网络通信协议栈 2 无线传感器网络的特点 与传统的无线网络相比，无线传感网主要具有如下特点n 帅 ： 1 、硬件资源受限。传感器节点体积小，成本低，其计算能力、程序空间和 内存大小都受到很大限制，这就要求其协议层次必须简单。 2 、电源容量受限。受到应用环境的限制，节点能量补给困难，有时传感器 节点甚至不可回收，电池能量即成为网络寿命的关键。 3 、节点数量多、分布密集。为了对一个区域执行监测任务，往往有成千上 ：+ 万的传感器节点。 4 、多跳路由。节点的通信半径小，带宽低，一般采用多跳路由转发的方式 进行数据收集。 5 、动态拓扑。节点可随时按需布设，工作过程中一个节点可能因为电池能 量耗尽或故障退出网络，另一节点也可能由于工作需要随时添加进网络。 6 、无中心、自组织。网络中没有严格控制的中心，各节点地位平等。网络 的布设和展开无需依赖任何预设网络设施，节点开机后就可快速自动组成一个独 立网络。 7 、以数据为中心。传感网系统中，人们只关心某个区域的某个观测指标， 无线传感网中基于能量的多信道接入分簇成链算法的研究与设计 不必关心某个具体节点的监测数据，因此，w s n 能快速有效组织起各节点信息， 从中融合并提取有用信息直接传送给终端用户。 1 1 3 面临的主要问题及当前研究热点 如今，无线传感器网络在军事侦察、环境监测、医疗监护、农业养殖、建筑 物监测以及空间探索和灾难抢险等领域都有着广泛的应用前景n 羽。从环境恶劣无 人值守的森林火险监测，到农田地表环境信息采集，再到智能医疗体感网( b o d y a r e an e t w o r k ，b a n ) 应用中对人体组织器官的温度监测，定位原发病灶点等等。 无线传感器网络重要的科研价值已经引起了全世界的广泛关注，该技术以其重要 性被公认为是2 1 世纪最具影响的技术之一。然而，目前无线传感技术仍处于初 步研发阶段，许多关键技术还面临着许多问题与挑战，主要有以下几个方面： 1 节点成本。无线传感器网络中往往撒布着大量的节点，因而节点的成本问 题将会成为制约其发展的因素之一。 2 能量供给。传感器节点分布众多、覆盖范围大、工作环境复杂，能量补给 困难，网络寿命的长短主要取决于节点的电池总能量以及消耗情况。 3 系统安全。无线传感网实际多应用于军事商业领域，安全问题应引起重视， 且传感节点多位于边远、环境恶劣的区域，自身难以进行保护或者维修。 4 网络内通信。无线传感网的正常通信信号容易受到一些障碍物或其他信号 干扰，安全有效的通信保障是无线传感网系统正常运行的基础。 无线传感器网络是一种特殊a dh o c ，然而它又具有许多有别于传统无线自 组织网络的一些鲜明独特的特点和需求。因此，现今许多已相当成熟的用于传统 无线网络的协议并不能很好地适用于传感网，而针对传感网自身特征的算法的研 究和设计就显得尤为重要。目前针对无线传感网的研究热点主要集中于两个关键 技术上2 3 删： 网络通信协议 1 路由层 针对传感网自身特征的路由算法设计一直是无线传感网长期的研 究重点。为节能起见，路由算法应设计的尽可能简单，节点上不应保存 太多的状态信息，节点间不应进行太多的路由信息交换，尽量避免发送 4 第l 章绪论 冗余信息，减少能量浪费。 2 m a c 层 m a c 层直接控制射频模块，对节点能耗有重要影响。目前为止，能 源效率是无线传感器网络m a c 层协议的主要设计目标，利用节点在没有 数据收发时关闭射频模块，转入休眠态，降低工作占空比，减少串扰和 空闲侦听带来的能量浪费。 网络管理技术 1 能量管理 主要是数据采集的管理、节能问题，控制节点对能量的使用，包括 操作系统、物理层、链路层、路由协议等方面的内容。 2 安全管理问题 无线传感网多用于军事、商业领域，安全性是重要研究内容。研究 中借鉴扩频通信、节点接入认证鉴权、数据加密、数据水印等技术提高 网络的安全性。 1 1 4 论文选题的目的及意义 无线传感网具有很强的应用相关性，没有一个通用的协议可以针对其众多不 同应用都发挥出最佳效果，算法的好坏将直接影响着无线传感器网络的整体性 能。 在无线传感器网络中，各节点通常由电池供电。然而作为微电子设备的传感 器节点，只能装载有限能量，许多应用场合能量的补给又是不可能实现的。因此， 节点的生存时间对电池寿命显示出很强的依赖。影响网络能耗的因素很多，首先， 通过功率放大器在无线介质中传递信号将消耗大量的能量；其次，各节点不仅自 身使用用户接口、存储设备进行运算时会耗能，而且作为中继节点转发数据时也 会耗能；路由选择及m a c 层控制，也将对耗能造成影响n 引。受到能源限制的无线 传感网络，其服务质量并不是首要的考虑因素，反而会因为节约能量而牺牲服务 质量口3 。因此，在无线传感器网络的设计过程中，任何技术和协议的使用都需以 节能为前提。 另外，从目前的研究来看，对电池能量特性的研究没有深入到无线传感网领 无线传感网中基于能量的多信道接入分簇成链算法的研究与设计 域，对于传感器节点能量来源电池的定量分析与研究少之又少口钔。目前大多 研究者都把研究重点放在网络特性上，提出各种算法以减少节点能耗的方式延长 网络寿命n 2 儿1 5 儿1 酊。然而，对电池特性的不了解，导致过度放电造成相当一部分放 电损耗由于节点死亡而无法得到恢复，从而割裂了电池特性与节能机制之间的有 机联系，使电池未能得到有效的利用和恢复，电池的实际电量无法达到其理论容 量n 力。倘若能将目前已掌握的电池特性很好地与算法相结合，过度放电的节点可 以得到及时休息和电量恢复，势必产生更佳的效果。 因此，本文将针对周期性事件报告模型的小规模w s n 网络应用，主要从能量 管理的角度出发，从以下几个方面对现有基于能量的路由层和m a c 层算法进行相 关的研究分析： ( 1 ) 降低能耗。在算法形成的拓扑结构中，节点间通信距离的减小可降低通 信发射功率进而减小能量消耗。 ( 2 ) 减少冗余。采用数据融合机制，尽量利用其处理能力在本地进行简单融 合，再传输处理后的部分必要数据，在数据传输到汇聚节点前就完成可能的数据 计算，大为减少网络中的数据量口1 。 ( 3 ) 负载能耗均衡。各节点分担全网的通信负载，平衡节点剩余能量，从而 能有效延长全网的工作寿命。 之后，本文在已有的算法基础上，对路由层和m a c 层协议进行捆绑设计，利 用跨层优化技术从降低功耗、均衡全网能量、延长网络生存周期等方面对网络性 能进一步综合改善，同时设计过程中将节点的电池特性与其节能机制有机结合。 本论文研究受教育部博士点基金“无线传感器时间同步新技术研究及其收 敛性分析”( 2 0 1 0 0 1 2 1 1 2 0 0 2 0 ) ，福建省重点科技计划项目“面向农业的无线传 感网开发平台及其应用”( 2 0 0 8 h 0 3 7 ) ，福建省自然科学资金项目“基于电池能量 特性的传感器网能量控制算法研究”( 2 0 0 7 j 0 0 3 5 ) 的资助。 1 2 研究现状及存在的问题 1 2 1 路由层 1 研究现状 对于w s n 路由协议的设计，能耗问题是首要考虑任务，除此之外，更要从整 6 第l 章绪论 个网络系统的角度，根据具体的应用背景，考虑网络能量的均衡使用，最终延长 整个网络的寿命n 明。从网络结构的角度，无线传感器网络的路由协议大致分为平 面路由和层次路由h 们。现有数据表明层次路由比平面路由节省更多能量，因此分 簇已成为当前路由算法中的研究热点。 ( 1 ) 基于能量的分簇路由 l e a c h 啪3 协议是w s n 中最早提出的分簇路由协议。该协议采用随机选举簇首 的方式避免簇首过分消耗能量，提高网络生存时间，且簇内仅一个簇首负责与 s i n k 通信及簇内数据收集，同时采用数据融合技术，能有效减少节点间交换数 据的通信量达到节能效果。但l e a c h 协议的簇首是随机选取的，这不能保证簇首 均匀地分布在整个网络区域中晗。 针对l e a c h 不能提供位置和簇首数量的保证，l e a c h _ c 陇3 在簇结构建立时考 虑了节点的能量因素，使用中心控制算法形成更好效果的簇群，然而该算法假定 所有节点都对网络拥有全局认识，这往往是不可行或是将消耗大量能量的。 r b l e a c h 采用随机时间间隔，并设置计数器以确保每轮簇首数量恒定，但 是其并未考虑到剩余能量因素且额外的计数器值维护信息将浪费大量无谓开销。 文献 2 4 根据簇首分布及节点能耗不均提出的能量负载均衡的分组成簇算 法，该算法根据各节点能量进行分组，并随着网络的运行进度动态调整分组个数， 组内再由能量重心进行簇首选举，有效实现负载均衡。然而该算法要求网内所有 节点能直接向s i i l k 返回节点能量信息，不适合大规模网络。 t e e n ( t h r e s h 0 1 ds e n s i t i v ee n e r g ye f f i c i e n ts e n s o rn e t w o r kp r o t o c 0 1 ) 2 5 1 在l e a c h 基础上，针对监测突发事件的场景，在簇建立过程中引入了绝对门限和 相对门限，前者指被监测事件属性符合查询要求，可以激活传感节点的门限值， 后者表示时间属性超过绝对门限后其变化幅度是否超过相对门限，以确定是否需 要发送监测数据。但是该算法对于周期性事件报告模型的应用并不适合。 a p t e e n 3 改进了t e e n ，增加了一个技术时间参数，同时提供了对周期性事件 报告的支持。但a p t e e n 同t e e n 协议一样，其主要缺点在于，构建多层簇以及设 置阈值在实现上较为复杂，基于属性的查询机制也会带来额外的开销。 脏e d 3 协议也是在l e a c h 算法簇首分布不均匀这一问题基础之上而作出的改 进，以节点剩余能量和簇内通信代价的主从关系引入多个约束条件作用于簇首的 7 无线传感网中基于能量的多信道接入分簇成链算法的研究与设计 选择过程，各节点采用从一跳范围内迭代选举簇首的方式使得选举出来的簇首在 邻居簇范围内的概率很小。该算法收敛速度快，簇首分布更均匀，形成的网络拓 扑也更趋于合理。 然而，包括髓e d 晗 协议在内的大多数的分簇协议周期性进行簇首重选时不可 避免地要进行簇重构，簇重构操作由于在全网运行期间的频繁进行，其造成的能 耗不容忽视。 文献 2 8 针对分簇算法的频繁簇重构缺陷，并引入簇间多信道接入方式以避 免各簇同时传输时的信道争用冲突，提出了m c 皿算法。该算法仅在网络初始化 时采用髓e d 算法形成簇结构，之后采用基于权值的簇首委任制在本簇内进行簇 首轮换，簇内采用多级结构的t d m a 接入，各簇使用不同频率的f d 姒多信道接入， 最后由簇首融合全簇数据后以逐级多跳的方式传递给s i n k 。该算法虽避免了频 繁簇重构带来的额外开销，然而每次簇首轮换时簇内多级树结构的建立，同样需 要不小的开销。 ( 2 ) 基于能量的链式路由 针对一般分簇路由频繁簇重构的问题，p e g a s i s 3 协议对此提出改进。它是 最早提出的链式路由，被认为是一种特殊的分簇算法。从距离s i n k 最远的节点 开始以贪婪算法在全网形成一条链式，每轮传输由链上的一个节点作为簇首，数 据从链端向簇首逐跳传递，再由簇首向s i n k 汇报。它的优点是数据传递总在相 邻节点间进行，传输距离短，并且簇首重选并不需要频繁进行簇结构的重组，然 而全网单链的结构，造成其传输时延过大的缺陷，无法满足实时应用的要求。 c o s e n 算法针对此问题提出改进，同样采用贪婪算法，但当链上节点数达 到全网2 0 ，从下跳节点开始新链的建立，直至遍历全网。该算法最终在全网形 成多条链式。每条链上剩余能量最大的节点被选举为链簇首。多链同时传输的方 式大为缩短单链算法传输时延大的弊端。 然而，由于p e g a s i s 和c o s e n 算法都是在全网范围内寻找下跳邻居节点，成 链后半阶段，由于链端附近大多节点均已入网，为寻找下一跳未入网节点，很容 易形成超长链，增大了局部的通信距离。 针对c o s e n 的不足，出现了一种改进的p e g a s i s 分层链路路由协议口，该协 议依据节点与s i n k 的距离，把网络划分为环状层次区域，构建由外到内的节点 第l 章绪论 到s i i l k 的链状路由树。该算法一定程度上抑制了簇内长链的形成，减小通信能 耗，然而各链簇首始终由离基站最近节点担任，将导致距基站最近的层节点快速 死亡，形成监测空洞。 文献 3 2 中引入了距离门限来避免链式算法有可能出现的相邻节点间的长 链，超过距离门限的下跳节点将就近接入一个已入网的节点。该算法杜绝了长链 的形成，然而该方法构建了分支链式的拓扑，在数据传输时需要更多的调度信 息开销，并且对于硬件资源受限的传感器节点来说，其增加了算法的复杂度。 ( 3 ) 结合电池充放电特性的路由 大多数的传感网算法设计一味追求降低能耗以延长网络寿命，却都忽略了对 能量供给源电池的充放电特性考虑。事实上，电池的充放电行为远比我们想 象的复杂，传感网节能算法的设计更应充分结合已掌握的电池充放电特性，以达 到对电池能量利用的最大化。 文献 3 3 中提出的b a r 盯r 、b a r _ n f p 、b a r _ d i r 、b a r _ g e d i r 等分别是基于 皿r 川、n f p 汹3 、d ir 蚓、g e d i r 等算法结合电池特性作出的改进。b a r 协议的宗 旨是选择电量恢复最完全的节点作为下跳节点。首先由发送节点在一跳范围内发 送r t s 广播包，收集邻居节点当前的能量恢复情况，收到r t s 的节点回复包含其 充放电信息的c t s 包。发送节点收集了所有邻居节点的充放电信息，选择电量恢 复情况最好的节点作为下跳候选节点，而后再根据肝r 、n f p 、d i r 、g e d i r 等协 议各自的选择方式在下跳候选节点中确定最终下跳节点。结果表明，在网络生存 时间方面，b a r 协议下的各算法都比原算法有显著延长。 b a r - b i d s 算法口刀加入对节点剩余能量和当前电池状态的考虑，在网络中优先 选取拥有更多能量且更少放电损耗的节点用作路由节点，从而减少节点的放电损 耗，均衡全网能耗，延长网络存活期等等。 文献 3 8 提出了结合电池充放电特性的分簇路由算法b 肿皿e d 。该算法将簇 首轮换方式改为簇内进行，改善了肛e d 中簇首轮换时频繁进行全网簇重构的缺 点。同时，b a r 一旺e d 考虑了电池放电时表面活性物质浓度差带来的放电损耗。 由于镍镉电池和锂离子电池的研究实验结果表明，当一个电池处于过度使用时， 其放电损耗会占到电池总容量的3 0 以上。因此，b a r - 脏e d 改变原肛e d 算法 中通过时间驱动全网重组的方式，而是采用当簇首节点放电损耗达到初始电池容 9 无线传感网中基于能量的多信道接入分簇成链算法的研究与设计 量3 0 的时候，即触发本簇内的簇首轮换机制，避免频繁全网簇重组带来的额外 消耗，同时电池充放电机制的结合，使得电池的电量尽可能地得到充分发挥。然 而该算法并没有改变分簇算法在簇首处能量消耗过分集中的问题。另外，其本簇 内簇首轮换的方式，将导致部分节点到簇首的通信功率增大，造成全网通信能耗 的增加。 2 存在的主要问题 基于对现有的无线传感网络中的路由协议的分析比较，当前对路由协议的研 究还存在以下问题： ( 1 ) 能耗不均。当前大多数分簇算法存在着簇首处能耗过分集中的问题，导 致全网能量分布不均衡，簇首节点过早死亡，缩短网络寿命。 ( 2 ) 频繁簇重构。大多分簇算法在簇首轮换时都要进行全网的簇结构重组， 这部分能耗不容小觑。 ( 3 ) 通信距离大。链式算法成链后期存在着可能的长链问题，增加能量开销。 ( 4 ) 时延大。单链结构算法存在着传输时延大的问题，不利于实时数据采集。 ( 5 ) 忽略电池充放电特性。现有研究表明，电池的充放电行为远比我们想象 的复杂。当前大多数基于能量的路由算法，独立于电池设计，架空了电池特性与 节能机制的有机联系。 1 2 2 _ a c 层 1 研究现状 w s n 中，数据通信是节能的主要着手点，而m a c 协议直接控制着节点收发器， 因此m a c 协议的设计是实现无线传感器网络节能的重要方面m 3 。w s n 的m a c 协议 设计主要目标是在保证传输时延和数据吞吐量的基础上，减少由于冲突和空闲侦 听带来的能量消耗h 。m a c 协议按节点接入方式分为竞争式和调度式。 调度式t d m a 机制没有竞争机制中的碰撞重传问题，并且数据传输时不需要 过多的控制信息，节点在空闲时隙可以及时进入睡眠而节省能量。由于传感网的 能量受限，过分复杂的网络协议会导致其能耗开销过大，t d m a 作为实现信道分 配的简单成熟的机制，其一些特点非常适合传感网络节能的需求m 1 。 ( 1 ) 调度式m a c 协议 l o 第l 章绪论 d 勘撇h 3 3 协议将时间帧分为周期性的调度访问阶段和随机访问阶段，随机访 问阶段由多个连续信令交换时隙组成，用于处理节点的添加、删除及时间同步。 周期性调度访问阶段由多个连续的数据传输时隙组成，某个时隙分配给特定节点 发送数据，每个时隙又分为控制时隙和数据时隙，发送节点在控制时隙内发出控 制消息，指出接收节点，而此时所有节点处于接收状态，如果发现自己非接收节 点，则进入休眠。只有发送节点和接收节点在数据时隙进行数据传递。在一定程 度上，d 队n a 减少了节点接收不必要的数据，部分解决串音问题。但是其对时间 同步精度要求高，控制时隙的控制消息收发增加了额外的开销。 t r a m a “町协议将时间划分为连续时隙，根据局部两跳内的邻居节点信息，采 用分布式选举机制确定每个时隙的无冲突发送者。同时让非发送和接收节点处于 睡眠态，避免把时隙分配给无流量节点以达到节省能量的目的。然而该协议要求 节点有较大存储空间来保存拓扑信息和邻居调度信息，需要计算两跳内邻居的所 有节点优先级，运行a e a 算法，这对于计算和存储能力有限的传感器节点而言是 一个严峻的考验。 ( 2 ) 针对分簇传感网络的t d m a 调度机制m a c 协议 文献 4 5 中分析了针对分簇结构的传感器网络的几种基于t d m a 机制的m a c 协议。a r i s h aka 提出了由簇首负责为簇内所有传感器节点分配时隙，收集和 处理簇内传感器节点发来的数据，并将数据发送给汇聚节点的分簇传感网姒c 协议。采用c d 姒来区分不同簇间的干扰。 单跳s l m a c 模型是针对簇首直接与s i i l l 【进行单跳通信的路由而设计的。由 簇首分配簇内节点时隙s l o t ，在每一帧的末端设置簇首至s i i l l 【的s s l o t 发送 时隙。c h b s 间采用c s m a 的方式，不同簇首与基站通信时，可能出现冲突。但 在网络规模不大，全网簇首数不多的情况下，冲突情况还是可以接受的。然而对 于网络规模大，某些远处节点无法直接与s i i l l 【通信的情况就不适用了。同时， 在网络中簇首数目较多的情况下，冲突将变得十分严重。另外，远处的簇首与 s i i l l 【通信时的高能耗容易造成远离s i i l l 【的节点早死亡的现象，不利于全网能量 的均衡。 由此出现了m - l i a c 模型，簇首间多跳转发的通信方式，c h _ c h - b s 。其在簇 内时隙结束后，给各簇首添加不同长度的空闲时隙，用于不同簇首间的帧同步， 无线传感网中基于能量的多信道接入分簇成链算法的研究与设计 之后簇首间进行逐跳转发直至s i i l l 【。然而此种方式由于空闲时隙的增加，导致 其时隙利用率低，传输时延大。 改进式的m l 姒c 模型同样存在着网络规模限制的缺陷，并且c h - c h 间数据 不再融合处理，无形中增加了冗余信息以及中间转发簇首的发送次数，造成靠近 s i i l k 的节点由于能耗分布不均而早死亡。 ( 3 ) 针对链式传感网络的令牌机制m a c