（计算机应用技术专业论文）无线传感网分布式多跳分层路由协议msrp的研究与设计.pdf

无线传感网分布式多跳分层路由协议m s r p 的研究与设计摘要 无线传感网分布式多跳分层路由协议m s r p 的研究与设计 中文摘要 由于受成本的制约，传感器节点的能量、处理能力、存储能力都十分受限。因此， 无线传感网路由算法的首要目标是节能，算法也不能有太高的运算复杂度和空间复杂 度，运行在传感网上的路由协议必定是一个轻量级的节能路由协议。本论文主要进行 层次型路由协议的研究和设计，在分析l e a c h 协议及其现有改进算法的基础上， 提出了分布式、簇间多跳的传感网分层路由协议，并对其进行了仿真、分析和改进， 论文的具体研究和实现工作如下： 研究了现有传感网路由协议，分析了其机制、特点和存在的问题。以簇类协 议为研究切入点，重点研究l e a c h 等几种分簇路由协议，并指出各分簇协议的特 点和不足。论文研究了现有l e a c h 协议的改进算法，并指出了这些改进存在的问 题：有的引入集中控制；有的需要复杂的计算；有的需要全局信息，需要占用大量的 辅助存储空间；对“通信热区”问题、路由安全问题没有给出有效的解决方案。 提出了一个分布式、簇间多跳的传感网分层路由协议m s r p 。算法通过簇间 多跳机制提高协议的扩展性；协议提出了基于邻接度、剩余能量等信息的随机数加权 簇头选举机制使簇头的分布更加合理；协议提出“虚拟s i n k 层技术”缓解“通信热 区问题，抵御w o r m h o l e 攻击；协议优化了簇间通信机制，提出了新的防止路由 环路方法。算法复杂度小、只需要很小的辅助存储空间。 还研究了o m n e t + + 的原理和实现机制，并对协议进行了仿真和分析。通过 仿真证明了改进算法的可行性，给出了协议的使用建议。 提出了m s r p 协议一个基于蚁群算法的改进方案a c m s r p 。协议采用多汇 聚点的网络模型以增加网络的健壮性、实用性；协议提出“蚂蚁轨迹本地化”技术减 少网络中的数据传输量；协议的信息素更新规则考虑了包的传输延时和剩余能量； a c m s r p 协议根据邻接度和信息素进行簇头选择和路径选取，不需要节点的位置信 息，可以有效的抵御h e l l o 洪泛攻击、s y b i l 攻击、w o r m h o l e 攻击和选择性转发攻 击。 关键词：路由，扩展性，虚拟s i l l l 【层，随机数加权，轨迹本地化 作者：刘春涛 指导老师：陆建德 a b s t r a c tr e s e a r c ha n d d e s i g no fd i s t r i b u t e dm u l t i - h o ph i e r a r c h i c a lr o u t i n gp r o t o c o lm s r pi nw s n r e s e a r c ha n dd e s i g no fd i s t r i b u t e dm u l t i h o ph i e r a r c h i c a l r o u t i n gp r o t o c o lm s r p i nw s n a bs t r a c t d u et ot h ec o s tc o n s t r a i n t s ，t h es e n s o rn o d eh a sl i m i t e de n e r g y , c o m p u t i n gc a p a c i t y a n ds t o r a g ec a p a c i t y t h e r e f o r e ，t h ep r i m a r yo b j e c t i v eo faw i r e l e s ss e n s o rn e t w o r kr o u t i n g a l g o r i t h mi se n e r g yc o n s e r v a t i o n ，a n dt h ea l g o r i t h mc a n n o tt a k eah i g hc o m p u t a t i o n a l c o m p l e x i t ya n ds p a c ec o m p l e x i t y t h er o u t i n gp r o t o c o lr u n n i n go ns e n s o rn e t w o r km u s tb e l i g h t w e i g h ta n de n e r g y e f f i c i e n t t h i sp a p e rf o c u s e so nt h er e s e a r c ha n dd e s i g no fw s n h i e r a r c h i c a lr o u t i n gp r o t o c 0 1 b a s e do nt h ea n a l y s i so fe x i s t i n gr o u t i n gp r o t o c o l sa n dt h e i m p r o v e da l g o r i t h m sf o rl e a c h ，a ni n t e r - c l u s t e rm u l t i h o ph i e r a r c h i c a ls e n s o rn e t w o r k r o u t i n gp r o t o c o l i s p r o p o s e d as i m u l a t i o na n da n a l y s i so ft h ep r o t o c o la n da n i m p r o v e m e n tf o rt h ep r o t o c o lh a sb e e nm a d e t h em a i nc o n t e n t so ft h i st h e s i sa r e a s f o l l o w s ： r e s e a r c h e x i s t i n gr o u t i n gp r o t o c o l s o fw s n ，a n a l y z et h e i rm e c h a n i s m s ， c h a r a c t e r i s t i c sa sw e l la sd r a w b a c k s t a k et h ec l u s t e rr o u t i n gp r o t o c o la st h es t a r t i n gp o i n t f o rt h er e s e a r c h ，s t u d yw i t he m p a s h i so ns e v e r a lc l a s s i c a lc l u s t e r b a s e dr o u t i n gp r o t o c o l s i n c l u d i n gl e a c h a n dp o i n to u tt h e i rc h a r a c t e r i s t i c sa n dd e f e c t s s t u d y t h e e x i s t i n gi m p r o v e da l g o r i t h m s f o r l e a c h ，s u m m a r i z e t h e i r c h a r a c t e r i s t i c sr e s p e c t i v e l ya n dp o i n to u tt h ep r o b l e m se x i s t i n gi nt h e s ei m p r o v e m e n t s i n c l u d i n gc e n t r a l i z e dc o n t r o l ，o rc o m p l e xc a l c u l a t i o n s ，o rg l o b a li n f o r m a t i o nw h i c hw i l l t a k el a r g ea m o u n to fa u x i l i a r ys t o r a g es p a c e ，o ri n e f f e c t i v es o l u t i o n st oc o m m u n i c a t i o nh o t z o n ei s s u ea n d r o u t i n gs e c u r i t y p r o p o s ead i s t r i b u t e di n t e r - c l u s t e rm u l t i - h o ps e n s o rn e t w o r kc l u s t e rr o u t i n g p r o t o c o lm s r p t h es c a l a b i l i t yo ft h ep r o t o c o li si m p r o v e dt h r o u g ht h ei n t e r - c l u s t e r m u l t i h o pm e c h a n i s m t h ec l u s t e rh e a de l e c t i o nm e c h a n i s mw i t hr a n d o mw e i g h t e dr u m b e r b a s e do ni n f o r m a t i o ni n c l u d i n ga d j a c e n c yd e g r e e ，t h er e m a i n i n ge n e r g ya n de t c i sg i v e nt o m a k et h ed i s t r i b u t i o no fc l u s t e rh e a d sm o r er e a s o n a b l e av i r t u a ls i n kl a y e rt e c h n i q u ei s p r o p o s e dt om i t i g a t ec o m m u n i c a t i o nh o tz o n ep r o b l e ma n dd e f e n da g a i n s tw o r m h o l e a t t a c k an e wm e t h o di sp u tf o r w a r dt op r e v e n tr o u t i n gl o o p s t h ec o m p l e x i t yo ft h e i l r e s e a r c ha n dd e s i g no fd i s t r i b u t e dm u l t i - h o ph i e r a r c h i c a lr o u t i n gp r o t o c o lm s r pi nw s n a b s t r a c t a l g o r i t h mb e c o m e sl o w a n d n e e d sal e s sa u x i l i a r ys t o r a g es p a c e r e l e a i z et h es i m u l a t i o no ft h ep r o t o c o lo nap l a t f o r mo m n 卅t h ea n a l y z e d r e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mi sf e a s i b l e ，a n dt h es u g g e s t i o n st od e p l o ys c e n e s o ft h ep r o t o c o la r eg i v e n i n t r o d u c ea n tc o l o n ya l g o r i t h mt oi m p r o v et h ei n t e r - c l u s t e rm e c h a n i s mo fm s r p a n dd e v e l o pan e wp r o t o c o la c - m s r p m u l t i s i n kn e t w o r km o d e li se m p l o y e dt oi n c r e a s e n e t w o r kr o b u s t n e s sa n dp r a c t i c a l a b i l i t y a n tt r a c kl o c a l i z a t i o nt e c h n i q u ei sp r o p o s e dt o r e d u c en e t w o r kt r a f f i c t h ep a c k e tt r a n s m i s s i o nd e l a ya n dt h en o d e sr e m a i n i n ge n e r g ya r e c o n s i d e r e dw i t ht h eu p d a t i n gr u l eo ft h ep h e r o m o n e t h ec l u s t e rh e a d sa n dr o u t e sa r e s e l e c t e di na c m s r pa c c o r d i n gt ot h ea d j a c e n td e g r e ea n dt h ep h e r o m o n ew i t h o u t p o s i t i o ni n f o r m a t i o no fn o d e s t h ea c m s r pc a nd e f e n da g a i n s tt h eh e l l of l o o da t t a c k , s y b i la t t a c k ，w o r m h o l ea t t a c ka n ds e l e c t i v ef o r w a r d i n ga t t a c ke f f e c t i v e l y k e y w o r d s ：r o u t i n g ，s c a l a b i l i t y , v i r t u a ls i n kl a y e r , w e i g h t e dr a n d o mn u m b e r , t r a c k l o c a l i z a t i o n i i i w r i t t e nb yl i uc h u n t a o s u p e r v i s e db yl uj i a n d e 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：，勃绍虿融日期：互。多。垆 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 导师签名： 日期w 吖0 6 哗日期：矽吖叻旷7 日期：五彳嘶 无线传感网分布式多跳分层路由协议m s r p 的研究与设计第一章绪论 第一章绪论 无线网络可分为两类：一类为有基础设施的网络，需要有固定基站对网络中的节 点进行组织协调；另一类为无基础设施网无线a dh o e ，节点采用分布式运行并具有 相对独立的路由维护功能。根据网络中节点移动的特点，无线a dh o e 网络又可分为 两类：一类为移动a dh o e 网络( m o b i l ea dh o cn e t w o r k ，简称m a n e t l l l ) ，网络中节 点移动较频繁；一类为无线传感器网络( 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 m e t 改变了 人与人之间的沟通方式，那么无线传感器网络将改变人类感知世界的方式。如果说 i p v 6 让每一个沙子都有一个i p 地址，那么传感器网络研究的问题就是“每一粒沙 子都应该是一台计算机”。 1 1 无线传感器网络概述 无线传感器网络4 】是由部署在监测区域内大量价格低廉的微型传感器节点以无 线通信的方式形成的自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖 区域中感知对象的信息，并发送给观察者。传感器节点、感知对象和观察者构成了传 感器网络的三要素。 1 1 1 传感器节点 传感器节点通常是具有监测、数据处理、通信等功能的微型嵌入式系统，节点采 集本地的监测数据( 如温度、湿度、加速度等信息) 并将其传送到被称为汇聚节点 ( s i n k ) 的命令中心。数据的传送方式可能是主动连续的，也可能是基于事件的，也可 能是基于查询的。 典型的传感器节点主要由传感器模块、处理器模块、无线通信模块和能量供应模 块四部分组成，如图1 1 所示。传感器模块负责监测区域内信息的采集和数据转换； 第一章绪论无线传感网分布式多跳分层路由协议m s r p 的研究与设计 处理器模块负责控制整个传感器节点的操作，存储和处理本身采集的数据以及其它节 点发来的数据；无线通信模块负责与其它传感器节点进行无线通信，交换控制消息和 收发采集数据；能量供应模块为传感器节点提供运行所需的能量，节点通常采用微型 电池供电。复杂的节点还有定位、移动支持、能量再生等模块。 l 互匹二 ：一传感器模块 | | 回悃； il 移动支持模块 i 一广一 ：处理器模块i ? 无线通信模块j 。 癣一| 图l l 传感器节点的结构 由于在无线传感器网络中需要大量配置传感器节点，为了降低网络成本，单个传 感器节点的资源一般都是十分受限的。节点的处理能力、存储能力和通信能力相对较 弱。典型的传感器节点通常只有数兆赫兹c p u 处理能力、几十k 的f l a s h 存储空 间。表1 1 列举了典型的传感器节点s m a r td u s t 的性能参数【5 1 。 表1 1 传感器节点性能参数 c p u 8 - b i t ，4 m h z s t o r a g e 8k b y t e si n s t r u c t i o nf l a s h 5 1 2b y t e sr a m 5 1 2b y t e se e p r o m b a n d w i d t h9 1 6m h zr a d i o 1 0 k b p s 1 1 2 传感器网络的网络架构 一个典型的传感器网络的架构如图1 2 所示，网络中的节点大致可分为三类： 一般节点( s e n s o rn o d e ) 负责采集监测数据；汇聚节点( s i n k ) 收集一般节点中的数 据并进行存储、处理、上传；网关节点实现s i n k 节点与处理中心或其它外部网络的 连接。通常s i n k 节点兼有了网关节点功能。汇聚节点可以是一个增强功能的传感器 节点( 有足够的能量供给和更大的存储空间、功能更强的处理器) ，或者是一个没有 监测功能只带有无线通信设备的特殊网关。 传感器网络通常由大量的传感器节点和数个汇聚节点组成。汇聚节点通常处理能 2 无线传感网分布式多跳分层路由协议m s l 冲的研究与设计第一章绪论 力、存储能力和通信能力相对比较强，一般有能量补充。传感器网络通过汇聚节点与 外部i n t e m e t 相连，实现通信协议的转换和监测任务的发布。传感器节点首先将监测 数据发送给汇聚节点，再由汇聚节点转发到外部网络。 ? 、 ? 。互联| 蠕卫星 ，。矽 ， 用户节点 监测区域传感器节点 图1 2 传感器网络的网络架构 1 1 3 传感器网络的特点 传感器网络是一个新兴网络，由于节点的处理能力、存储能力和能量都非常有限， 使传感器网络在协议设计、资源管理、应用开发等方面有很多不同于传统网络的特点。 总的来说，传感器网络具有以下几个典型特点： ( 1 ) 大规模传感器节点通常分布在很大的监测区域中，往往通过节点的大量密 集部署来减少路由空洞和监测盲区、提高监测的精确度和系统的容错性能。节点的密 集部署要求传感器网络的协议设计和系统控制策略有良好的扩展性。 ( 2 ) 自组织传感器节点被部署在没有基础设施的区域中，通常采用随机部署； 传感器网络的拓扑结构因节点出现故障、新节点的加入而改变；网络中的传感器、感 知对象和观察者这三要素都可能移动，传感器节点必须能够自动配置、管理和修复， 通过拓扑控制和网络协议自主形成具有监测功能的网络系统。 ( 3 ) 应用相关无线传感器网络用来感知客观世界，不同的应用背景对无线传感 器网络有不同的要求，其硬件平台、软件系统、通信协议和安全要求都可能不同。针 对不同的应用来研究传感器网络，是传感器网络研究的一大特点。传感器网络的应用 可以分为以下几种类型：基于查询型( s i n k 发起) 、周期发送型、事件驱动型等。 ( 4 ) 以数据为中心如果说i n t e m e t 是一个以地址为中心的网络，那么传感器网 络是一种以数据为中心的网络。用户感兴趣的是传感器监测的数据，而不是节点本身。 用户直接将查询通告给整个网络，而不是某个特定节点，网络在获得指定事件的信息 后将其汇报给用户，其主要思想是以数据本身作为查询或传输线索。 ( 5 ) 节点资源受限节点不仅能量、处理能力、存储能力有限，而且通信链路也 第一章绪论无线传感网分布式多跳分层路由协议m s r p 的研究与设计 受限。由于无线信道本身的物理特性以及其本质上是一个广播式的竞争共享信道，因 而将产生碰撞、信号衰减、噪音干扰、信道间干扰等多种情况，网络的有效带宽远小 于理论值。 1 1 4 传感器网络研究的关键技术 无线传感器网络是一个多学科交叉的研究领域，有众多问题需要研究和突破。研 究中的关键技术包括两个方面：一是硬件平台的研究；二是无线传感器网络的通信协 议和模式研究，主要包括：物理层研究、m a c 层协议研究以及路由层协议研究。下 面介绍部分关键技术： ( 1 ) 拓扑控制传感器网络通过拓扑控制生成网络的拓扑结构，良好的拓扑结构 能够提高路由协议和m a c 协议的效率，可为数据融合、时间同步和目标定位等多 方面奠定基础，可以有效节省节点的能量。 拓扑控制的主要研究问题是在满足网络覆盖度和连通度的前提下，通过功率控制 和骨干网节点选择，剔除节点之间不必要的通信链路，生成一个高效的、数据转发的 网络拓扑结构。拓扑控制可以分为节点功率控制和层次型拓扑结构形成两个方面。功 率控制机制调节网络中每个节点的发射功率，在满足连通度的前提下，减小节点的发 射功率，控制节点单跳可达的邻居数目；层次型拓扑结构形成利用分簇机制，让一部 分节点成为簇头节点，由簇头形成一个处理并进行数据转发的骨干网络，其它非簇头 节点在没有数据发送的情况下可以进行睡眠，有效节省网络能量。需要特别说明的是 本课题提出的路由算法本质上既是一个拓扑控制算法，又是一个路由协议。 ( 2 ) 网络协议传感器网络协议的功能是使各个节点形成一个多跳的数据传输网 络，当前协议研究的重点是网络层协议和m a c 层协议。由于计算能力、存储能力 有限，节点只能获取局部的拓扑信息，其上运行的协议也不能太复杂，只能是一个轻 量级协议；传感器节点拓扑结构、网络资源的不断变化都对传感器协议的设计提出很 高的要求。同时，由于传感器网络是一个应用相关的网络，应用需求不同时，网络协 议需要根据不同的应用类型或者应用目标环境而定制，没有任何一个协议可以适用所 有不同的应用。 。 传感器网络路由协议设计的首要目标是节能。路由协议不仅关心单个节点的能量 消耗，更关心整个网络的能量消耗，以免局部节点能量耗尽而无法工作，形成路由空 洞和监测盲区，影响整个网络的生存期。同时，由于传感器网络是一个以数据为中心 的网络，传感网路由协议不要求节点有唯一地址。 4 无线传感网分布式多跳分层路由协议m s r p 的研究与设计第一章绪论 传感器网络的m a c 协议的首要目标仍然是节省能源，其次才考虑扩展性、公 平性、利用率和实时性等。在m a c 层的能量浪费主要表现在空闲侦听、接收不必 要的数据、碰撞重传等。为了节省能源，传感器节点通常采用“侦听睡眠”机制， 节点在需要收发数据时才侦听无线信道，其它时间进入睡眠。 ( 3 ) 网络安全为了保证任务的机密布置、任务结果的安全传递和数据融合，无 线传感器网络需要实现基本的安全机制。主要安全问题包括机密性、点到点的消息认 证、完整性鉴别、新鲜性、认证广播和安全管理。为了保证数据融合后数据源信息的 保留，数字水印也成为安全研究的内容。 由于传感器节点的限制，传感器网络安全研究不同于传统的i n t e m e t 的安全。由 于节点的处理能力有限，必须在算法的计算强度和安全强度之间进行权衡；另外，有 限的计算资源和能量资源要求系统的各种技术综合考虑，以减少系统的复杂度，安全 路由技术的提出正是出于这样的考虑。 ( 4 ) 定位技术位置信息是传感器节点数据采集不可缺少的部分，没有位置信息 的监测有时毫无意义。确定事件发生的位置是传感器网络常用的功能之一。为了能够 提供有效的位置信息，节点必须能够确定自身的位置。由于节点的资源有限、随机部 署、通信易受干扰、节点失效等影响，定位技术必须有自组织性、健壮性、能量高效、 分布式计算等要求。 ( 5 ) 数据融合由于传感器网络能量有限，减少数据量的传输能够有效节省能量。 因此，传感器节点在存储、转发数据的过程中，需要利用节点的本地计算能力和存诸 能力去除冗余数据信息，从而达到节省能量的目的。由于节点不稳定，传感器网络也 需要数据融合技术对多份数据进行综合，提高信息的准确度。但是，数据融合技术是 有代价的，为了融合必须等待其它数据的到来、融合路由的发现和数据的融合处理也 需要时间，必然导致网络传输延迟的增加；此外，数据融合必然导致数据的损失，降 低了网络的鲁棒性。 由于传感器网络的良好应用前景，国内外许多著名的大学和公司纷纷从不同的层 次、不同的角度对传感器网络进行了研究和开发。国外无线传感器网络研究开始于上 个世纪末，研究重点主要集中在网络层和数据链路层以及物理层。现在，国外研究重 点已从研究传感器硬件转向相关协议的研究。国内对于无线传感器网络的研究起步较 晚，主要以改进、应用软硬件技术为主。随着国内研究机构对传感器网络研究的重视， 软硬件的研究与设计将有较大的发展空间。未来传感器网络的研究将以微型节能硬件 研究、软件协议研究并行发展，重点突出软件协议的研究为主要发展趋势。 第一章绪论无线传感网分布式多跳分层路由协议m s r p 的研究与设计 由于节点尺寸小、无人维护、应用场景不适合人工更换电源等特点，传感器网络 研究的首要问题是节省能量。能量高效的路由协议是设计一个可用的传感器网络最重 要的工作【6 】，路由协议研究是当前无线传感器网络研究的热点，但是仍处在起步阶段， 很少能与实际相结合。由于传感器网络的应用相关性，单一的路由协议不能满足各种 应用需求，因而人们提出了许多路由协议。由于平面路由对通信资源的优化管理能力 差、自组织协同工作算法复杂、对网络动态变化的反应速度较慢，因此在大规模无线 传感器网络中的应用受到较大制约【7 】。当节点密度较大时，平面传感器网络中的s i i l l ( 节点将不堪重负，网络中的传输延迟将增大，并产生大量的能量消耗。而分层结构允 许增加网络的节点密度和网络规模而不至于对网络性能产生大的影响。层次路由具有 拓扑管理方便、能量利用高效、数据融合简单等优点，而层次分簇结构协议在数据融 合和多跳机制中更有先天的优势，成为当前重点研究的路由技术和今后无线传感器网 络路由应用的方向【s l 。本文以传感网层次型路由协议的研究和设计为研究课题。 1 2 层次路由协议的研究现状和存在的挑战 由于层次型路由协议的良好性能，国内外研究人员对其进行了大量的研究。层次 型路由协议起源于手工对节点进行部署使其形成簇，其中能量供应比较充足、计算能 力较强、通信能力较强的节点担任簇头，然后由簇头组成骨干网进行簇间通信。与此 同时，功能较弱的节点放置在簇头周围，它们通过骨干网把监测数据传送到s i n k 节 点。但是随着网络规模的扩大，手工放置节点是不现实的。 h e i n z e l m a n 等于2 0 0 0 年提出的l e a c h ( l o w e n e r g ya d a p t i v ec l u s t e r i n g h i e r a r c h y ) t 9 】协议，是无线传感器网络中最早提出的层次路由协议。它的成簇思想贯穿 于其后出现的很多层次路由协议中，如t e e n t l 0 】，h e e d l 1 。l e a c h 协议的目的是 为了在非层次型网络中通过节点随机成为簇头而把传感器网络逻辑分簇。簇头采用集 中式方式对簇内成员进行调度和数据融合，数据传输采用单跳方式以减少网络中的能 耗。簇内使用t d m a 机制、簇间使用c d m a 机制来减少网络中的无线信号冲突。 l e a c h 的缺点是单跳的通信机制限制了网络的扩展性，簇头选举的随机性使簇头分 布很不合理，簇的维护也带来额外的能量开销。p e g a s i s t l 2 】是一个链式分层协议， 协议把网络内所有节点组成一个链，节点只需要和邻居节点进行通信，每一轮随机选 取一个节点和s i n k 进行通信。c 2 e 2 s 协议【1 3 】综合利用l e a c h 和p e g a s i s 的优 点来延长大规模网络的生存期。m o c a 算法1 使网络成为k 个簇头的统治域。节 点由根据网络规模大小生成的概率确定是否成为簇头。簇头在k 跳范围内广播簇的 6 无线传感网分布式多跳分层路由协议m s r p 的研究与设计第章绪论 信息，在k 跳内的节点接到此信息后不管以前是否加入到别的簇，仍然选择加入到 这个簇。同属于多个簇的节点称为边界节点，簇间通信可以通过边界节点进行。 b a n d y o p a d h y a y 和c o y l e 等提出一个多层路由协谢15 1 。算法使用不同的簇头生成概 率选择从1 层到n 层的簇头。每一层都是多个簇头的统治域，每一层也都有边界节 点。e e m c t l 6 】仍然是一个多层的成簇机制，簇内节点发送自己的位置、能量等信息到 s i n k 节点，s i n k 节点根据这两项数据生成每一层簇头的生成概率。b c d c p 协议【1 7 1 利用分簇的扩展性、能效、便于管理的优点的同时，加入了对真实网络流量下q o s 的 支持。2 0 0 4 年，m h a t r e 等比较了同构网络和异构网络中单跳簇类协议的能效，并给 出了优化的簇头数1 1 8 j 。2 0 0 5 年，s o r o 和h e i n z e l m a n 等提出了不均衡簇模型1 1 9 1 ，主 要思想在于簇类协议中，簇头承担了较多的负载，因此网络生存期受簇头的寿命界定， 通过限制网络中每个簇的成员的个数来均衡簇头的负载，通过延长簇头的寿命来延长 网络的生存期。2 0 0 6 年，a r b o l e d a 和n a s s e r 等比较了主动型和被动型簇类路由协 议【2 0 1 。d u a r t e m e l o 和l i u 等给出了给定监测区域中优化的簇的数目的推导t 2 。 c h i a s s e r i n i 等提出一个通过优化簇的大小和簇内节点的分配来延长网络的生存期的 算法【2 2 】，算法假定簇头的数目和位置固定、簇头知道全局拓扑信息，这在实际应用中 是不现实的。刘明等提出了一种分布式的高效、节能的无线传感器网络数据收集和聚 合协议【2 3 1 ，为了减小簇首节点的能量开销，簇首之间以多跳方式将收集到的数据发送 到指定的簇首节点，然后通过该节点将整个网络收集的数据发送到基站。 经典的分簇路由是基于跳数的路由，路由算法总是选取跳数最小的路径【2 4 1 ，s i n g h 等提出通过考虑每一个包的能量消耗、网络丢失连通性、节点的能量等方面进行路由。 被动式路由算法1 2 5 】选择根据最先声明胜的原则进行路由，这项原则规定节点选择最先 发出簇头信息的簇头节点成为自己的簇头。文献 2 6 】把优化路由算法延长网络的生存 期规范化为线性编程问题，并提出启发式算法进行路由选取。文献 2 7 】提出一个使用 双分解的分布式路由算法。p a s c h a l i d i s 等于2 0 0 7 年在文献 2 8 】中探讨了大规模网络 场景下的不同任务的资源公平分配问题。a c e t 2 9 1 算法根据时间和权重两种标准选择 簇头。权重表示节点的忠诚跟随者( 也就是没有加入其它簇的节点) 数，当非簇头节 点获取最小跟随者门限规定数量的跟随者时可以成为簇头，最小跟随者门限是一个从 协议为该节点初始化开始到当前时间的一个函数。l e a c h 是根据随机生成的概率选 择簇头。h e e d 协议根据节点的剩余能量、最小簇头能量门限、网络的簇头比例等 来选择簇头。b o u b a f s 等提出一个根据语义信息形成簇头的协议【3 0 1 ，在协议中一个用 户的查询被转换为查找满足特定条件的节点，网络中满足此条件的节点成为簇头，簇 第一章绪论 无线传感网分布式多跳分层路由协议m s r p 的研究与设计 头和其所在的区域内的节点形成簇。w a n g 等【3 1 1 提出了一个根据语义和权重两项信 息进行成簇的协议。协议语义信息代表本地属性，成簇过程开始于一个节点洪泛一个 消息到网络，网络中节点根据自己的能量级别等待一定的时间，然后开始宣称自己成 为簇头，还没有发出宣称为簇头的候选节点在收到别的簇头的簇头广播后取消自己的 竞选，然后转发此广播。林亚平等提出了分布式数据汇聚层次路由算法| 3 2 1 ，该算法利 用能量核的思想汇聚数据以减少传输到目的节点的信息量。 尽管层次算法在传感器网络拓扑管理、数据融合和传输等方面有很多优势，但也 存在许多不足，归纳起来集中体现在： ( 1 ) 扩展性当前的层次路由协议有的需要集中式控制，有的需要全局的节点信 息，限制了网络的扩展性，不适合在大规模网络中使用。 ( 2 ) 网络热区在多跳网络中，簇内数据的传输必须依赖中间节点转发，靠近s i n k 节点的簇头承担了更多的转发任务，能量耗费较快，容易形成路由空洞和监测盲区。 实验结果显示，当一个传感器网络生命结束后，总的节点能量剩余超过9 0 t 3 3 1 。 ( 3 ) 算法健壮性的考虑由于传感器节点易出现故障，簇头一旦不能工作，整个 簇内的成员都将无法发送数据。 ( 4 ) 算法复杂度高现在的层次算法，要么需要集中式控制、要么需要全局信息 进行复杂的路由计算，而节点的存储、计算能力有限，必定要求传感器网络中的路由 协议是运算强度低、辅助存储空间小的一个轻量级路由。 1 3 论文内容和主要贡献 本文主要研究传感器网络的路由协议，重点研究簇类路由协议的改进与设计。首 先提出了一种改进了的分布式、高扩展性的轻量级分簇路由协议m s r p ( m u l t i h o p s h o r t e s t p a t hb a s e dr o u t i n gp r o t o c o l ，多跳基于最短路径的路由协议) ，接着引入群集 智能算法以增强协议的实用性、健壮性和安全性，最后在o m n e t + + 平台上进行了 模拟实现。笔者所做的主要工作总结如下： 论文首先论述了无线传感器网络的研究背景，介绍了节点组成、网络体系结构、 无线传感器网络的特点和研究的主要问题，指出了传统网络的路由协议不适合传感器 网络。由于簇类协议的良好性能，我们重点总结了传感器网络层次路由协议的研究现 状和面临的挑战。然后分析了传感器网络路由协议的特点和设计要求，着重探讨了几 种有代表性的传感器网络路由协议，并对其做了对比分析。接着指出了传感网路由协 议的发展方向。 8 无线传感网分布式多跳分层路由协议m s r p 的研究与设计 第章绪论 论文其次提出了种分布式、簇问多跳的无线传感网路由协议m s r p 。协议提 出了基于邻接度、剩余能量等信息的随机数加权簇头选举机制使簇头的分布更加合 理；协议提出了“虚拟s i i l l ( 层 技术不但缓解了“通信热区 对网络生存期的影响， 而且削弱了w o r m h o l e 攻击；协议优化了簇间通信机制，提出了新的防止路由环路 的方法；协议算法复杂度小、只需要很小的辅助存储空间，适合传感器节点计算能力 较弱、存储空间小的特点；协议有较低的能耗、良好的扩展性和健壮性，适合在大规 模网络场景中使用。 为了提高协议的安全性、健壮性和实用性，论文还提出了一种基于蚁群算法的 m s r p 协议的改进协议a c m s r p ( a n t c o l o n yb a s e dm s r pr o u t i n gp r o t o c o l ，基于蚁 群的m s r p 路由协议) 。协议采用群集智能解决大规模无线传感网的分布式路由问 题，通过引入信息素改进了m s r p 协议的成簇机制和簇间通信算法。协议优化了蚁 群算法，利用“蚂蚁轨迹本地化技术”减少了网络的负载。协议完全根据信息素进行 路由，不需要节点的位置信息，协议采用多汇聚点的网络模型以增加网络的健壮性和 扩展性。a c m s r p 协议不但根据邻接度而且还根据信息素进行簇头选择和路径选 取，使h e l l o 洪泛攻击无从下手，而且a c m s r p 协议根据信息素进行路由可以有 效的抵御s y b i l 攻击、选择性转发攻击。a c 。m s r p 协议有较低的能耗、良好的扩展 性、较好健壮性、不需要节点的位置信息、满足多汇聚点部署时的健壮性需求，适合 在大规模网络场景中使用。 论文还研究了o m n e t + + 仿真平台的原理和实现机制，并对l e a c h 协议、 m s r p 协议、a c m s r p 协议进行了仿真实现和性能分析。并结合m s r p 协议对路 由协议的安全问题进行了探讨，分析了本文提出的协议的安全性。 本文主要贡献：论文提出了基于邻接度、剩余能量等信息的随机数加权簇头竞争 机制；论文还提出了“虚拟s i n k 层”技术概念以缓解“通信热区”对网络生存期的 影响，并提出了一个基于虚拟s i n k 层的路由协议m s r p ；论文对m s r p 协议进行 了基于蚁群的优化，并对蚁群算法的通信机制进行了改进；结合m s r p 协议的特点， 提出了新的防止路由环路的解决办法；对所提出的协议进行了仿真实现和分析。 1 4 论文的结构安排 第一章绪论：论述了无线传感器网络的研究背景和课题要研究的问题，总结了 论文的内容和相关工作。 第二章无线传感网路由协议相关研究：首先阐述了传感网路由协议的功能、特 9 第一章绪论无线传感网分布式多跳分层路由协议m s r p 的研究与设计 点和挑战等路由协议相关问题，然后分析了典型的无线传感网路由协议，并对平面路 由协议和层次路由协议进行了对比分析，最后总结了传感网路由协议研究的发展趋 势。 第三章基于虚拟s i n k 层的路由协议m s r p 的设计：分析了l e a c h 协议的 优缺点及其改进算法，提出了一种分布式、簇间多跳的轻量级分层路由协议m s r p 。 对协议的设计思想、需求分析、详细设计进行了阐述。 第四章m s r p 协议的模拟实现和仿真评测：介绍0 m n e t 卜 仿真平台，给出 了协议各个模块的实现，对l e a c h 协议和m s r p 协议进行了详细的评测分析。 第五章m s r p 协议基于蚁群的改进与仿真分析：首先对蚁群算法进行了阐述， 然后详细介绍了协议的成簇算法、簇间通信机制、“轨迹本地化技术”等设计思想并 对协议进行了设计和实现。最后对路由协议的安全问题进行了探讨，并分析了本文提 出的协议的安全性。 第六章总结与展望：总结全文，对下一步研究工作提出展望。 1 5 本章小结 本章首先简要介绍了无线传感器网络的节点结构与网络特点，以及它们对无线传 感网路由协议设计产生的影响：节点的结构决定了传感网路由协议设计的首要目标是 节能，网络特点决定了传统的网络协议不适合传感器网络，这也是无线传感器网络协 议研究的意义；接着总结了传感器网络研究的主要问题，指出了传感网路由协议研究 是当前无线传感器网络研究的关键问题，也是本课题的研究方向；然后介绍了无线传 感网层次类路由协议的研究现状和面临的挑战，以及本课题的相关工作；最后介绍了 论文的