（通信与信息系统专业论文）无线传感器网络组播路由协议研究.pdf

摘要 中文摘要 近年来，无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 由于自身的特点及 其广泛的应用前景而受到越来越多研究人员的关注。但是，无线传感器网络的节点 资源受限，尤其是能量受限的特点也使其发展和应用面临严峻的挑战。因此，研究 和设计能量高效的路由协议成为了当前传感器网络研究领域的重要课题之一。 本文首先在绪论部分简要的介绍了无线传感器网络的概念和分类，比较全面地 分析和对比了无线传感器网络中的组播路由协议的研究现状和不足之处。在此基础 上，本文在第一章结合随机路由和f a c e - r o u t i n g 算法，提出了一种辅助信标的组播 路由算法，有效地延长了网络的生存周期。为了达到进一步优化传感器网络能量消 耗的目标，本文的第二章利用虚拟最小生成树将多播路由分解成父节点与子节点之 间的单播路由，同时引入修正因子以解决空洞问题，提出了能量高效的路由算法。 本文在第三章将研究范围扩展到整个无线网络，通过在组播路径的构建中引入基于 b e t a 分布的声誉机制，提出在具有自私节点的无线网络中提高组播效率的策略。论 文在第四章对全文的工作进行了总结，在此基础上提出了若干未来值得进一步研究 的问题和方向。 关键词：无线传感器网络，组播，节能，声誉机制 福建师范大学蒋佳铭硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，m a n yr e s e a r c hi n t e r e s t sh a v eb e e nf o c u s e do nw i r e l e s ss e n s o r n e t w o r k sd u et oi t so w nd i s t i n g u i s hf e a t u r e sa n dt h ew i d ea p p l i c a t i o np r o s p e c t b u tt h e l i m i t a t i o n si nr e s o u r c e s ，e s p e c i a l l yi np o w e ro fw i r e l e s ss e l l s o rn e t w o r kn o d e sc h a l l e n g e i t s d e v e l o p m e n t t h e r e f o r e ，s t u d y i n ga n dd e s i g n i n gr o u t ep r o t o c o l s e x c e l l e n ti n p o w e r - e f f i c i e n c yb e c o m ea l li m p o r t a mi s s u ei nw i r e l e s ss e n s o rn e t w o r k s i nt h i sp a p e r , w ef i r s ti n t r o d u c ew i r e l e s ss e n s o rn e t w o r k s c o n c e p ta n dc l a s s i f i c a t i o n i ne x o r d i u m ；a l s ow ea n a l y s i st h er e s e a r c hs i t u a t i o na n di n e f f i c i e n c yo fm u l t i c a s tr o u t e p r o t o c o l o fw i r e l e s ss e n s o rn e t w o r k s a f t e rt h a t , i nf i r s t c h a p t e r , w ep r o p o s ea b e a c o n i n g - a i d e dm u l f i c a s tp r o t o c o lb a s e do nt h ec o m b i n a t i o no fs t o c h a s t i cr o u t i n ga n d f a c e r o u t i n g t h i sp r o t o c o lc a ne f f e c t i v e l yp r o l o n gt h el i f et i m eo fn e t w o r k i no r d e rt o a c h i e v et h eg o a lo fm a k i n gaf u r t h e ro p t i m i z a t i o ni ne n e r g yc o n s u m p t i o n , i nt h es e c o n d c h a p t e r , w ep r o p o s ea ne n e r g ye f f i c i e n tm u l t i c a s tp r o t o c o lb yd i v i d i n gt h em u l t i c a s t r o u t i n gi n t o s e v e r a lu n i c a s tr o u t i n gb e t w e e np a r e n tn o d e sa n dc h i l dn o d e so fv i r t u a l m i n i m u ms p a n n i n gt r e ec o n s t r u c t e di na d v a n c e a l s ow ei n t r o d u c em o d i f yf a c t o rt o r e s o l v et h ev o i dp r o b l e m i nt h i r dc h a p t e r , w ee x t e n do u rr e s e a r c hf i e l dt ot h ew h o l e w i r e l e s sn e t w o r k w ep r o p o s ean e ws t r a t e g yt oi m p r o v et h em u l t i c a s te f f i c i e n c yo f w i r e l e s sn e t w o r kc o n t a i n i n gs e l f i s hn o d e sb yi n t r o d u c i n gr e p u t a t i o nm e c h a n i s mb a s e do n b e t ad i s t r i b u t i o ni nt h ep r o c e s so fc o n s t r u c t i n gm u l t i c a s tp a t h w ec o n c l u d eo u rw o r k si n t h ef o u r t hc h a p t e r , a n dp r o p o s es o m ev a l u a b l ei s s u e sf o rf u r t h e rr e s e a r c h k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k s ，m u l t i c a s t , e n e r g yc o n s e r v a t i o n , r e p u t a t i o n m e c h a n i s m h i 吣4 川148 99川1眦y 福建师范大学蒋佳铭硕士学位论文 i v 中文文摘 中文文摘 近几年微电子机械系统和低功耗、高集成度的数字电子技术的进步促进了微传 感器的发展。这类传感器一般都具有数据处理及通信能力。无线传感器网络正是由 数量庞大的这种传感器节点以自组织的方式构成的一种新型网络。这种网络将在各 种应用领域中起着重要作用：如从军事监测领域到森林火灾监测领域，再到建筑物 监测领域。 组播是一个众所周知的节省通信量的概念，是诸如重发布命令、数据中心型存 储以及目标追踪等应用场合的基础。组播的目的在于通过仅在连接目的节点的链路 出现分支的情况下创建数据拷贝，从而在网络中的路径上仅传输一次数据包的方式 来实现高效路由信息。其优点在于节约网络资源。而传感器网络中的节点通常受带 宽、计算能力和能量限制，因此节约网络资源、延长网络生存周期对传感器网络来 说是极其重要的。因此组播路由成为了近几年的一个研究热点。 本文的绪论部分对无线传感器网络作了全面的介绍，主要包括传感器网络的组 成，传感器网络的分类和传感器网络应用领域，同时对无线传感器网络的组播路由 协议的研究现状作了深入的分析。 第一章以组播区域与s i n k 节点距离比较远的传感器网络模型为研究对象，将组 播路由划分成两个阶段。第一阶段为s i n k 节点到a p 节点之间的数据包路由阶段。 在该阶段中，当前节点的前向转发区域内的节点采用定时器超时的方式竞争转发数 据包，并引入f a c e r o u t i n g 策略进行空洞修复。第二阶段为组播区域内的数据分发 阶段。此时构建一棵以a p 节点为根节点的组播树，树中的节点根据父层节点的能量 信息不断更新自己的父节点。该方案可以有效的延长网络的生命周期。 在多播路由中，一个算法的质量取决于两个方面的因素：其一、数据包的拷贝 策略；该策略应该沿着代价高效的主干网转发数据包。其二、下一跳转发节点的选 择；该选择方法应该在主干网上高效地转发数据包。因此，本文第二章利用虚拟最 小生成树作为主干网，将多播路由分解成父节点与子节点之间的单播路由，在父节 点与子节点之间的数据包路由过程中，根据候选转发节点与子节点之间的距离、角 度以及候选转发节点的能量信息选择下一跳转发节点，同时引入修正因子以解决空 洞问题，提出了能量高效的路由算法。仿真结果表明该方案能够很好的均衡网络节 v 福建师范大学蒋佳铭硕士学位论文 点之间的能量消耗。 第三章将问题扩展到整个无线多跳网络背景下，在网络中引入基于b e t a 分布的 声誉机制。该部分内容首先分析了该声誉机制模型并阐述了该模型在网络中的应用 价值；接着提出了基于该机制的组播路由协议。采用该协议的网络在运作过程中， 通过观察并记录节点的历史动作来更新节点的声誉值，从而将不合作节点排除在组 播树之外，以此来促进节点之间的合作性，达到提高组播路由效率的目的；最后用 实验证明了该方案的有效性。 最后，第四章对本文的研究成果进行了系统的总结，并在此基础上展望该领域 的研究方向。 v i 绪论 绪论 第一节无线传感器网络简介 近些年微电子技术的进步促进了智能传感器的发展，无线传感器网络也因此在 世界范围内越来越受到关注。无线传感器网络是由数百乃至数千个传感器节点组成 的网络。这些节点可以通过无线媒体进行通信。在一地理区域部署数量众多的传感 器节点可以对该区域进行更加精确的监测 1 。组成网络的传感器节点一般由以下几 个部分构成：定位系统、移动装置、感知单元、处理单元、收发单元和能量单元， 如图o l 所示 1 。这些传感器节点具有体积小、计算处理能力有限、能量少和价 格低廉等特点。无线传感器网络由许许多多的传感器节点组成，但一般极少有或完 全没有基础设施。传感器网络中的节点以自组织的方式工作。图o - 1 还显示了无线 传感器网络的通信体系结构。传感器节点通常散布在被监测区域。传感器节点之间 进行协作以产生与物理环境相关的高质量的信息。每一个节点根据自己的任务、当 前所持有的信息和自己当前的计算、通信以及能源资源来决定自己的行为。每一个 节点都有采集和路由信息的能力。传感器网络中常常有一个移动的或者是固定的基 站。基站将传感器网络连接到已有的通信基础设施或英特网，这样，用户可以对采 集的数据进行处理。 定位系统移动装置 处理单元1 发单芜 收发 感知电弓一 l 处理器匕 器1 9器 传感 器 转换 t tt 能量单元 h 鐾鋈茎 图0 - 1 无线传感器网络示意图 f i g u r eo - 1t h ev i e wo f w s n 福建师范大学蒋佳铭硕士学位论文 一、无线传感器网络分类 无线传感器网络可以部署在地面上，地下以及水中。无线传感器网络所处的物 理环境不同，设计网络技术时所受到的约束和挑战也不尽相同。目前可将传感器网 络归为五类 5 ：地面无线传感器网络，地下无线传感器网络，水下无线传感器网络， 多媒体无线传感器网络和可移动的传感器网络。 地面无线传感器网络 6 ：成百上千的、造价比较便宜的部署在一个指定的区域， 并以自组织或预先部署的方式工作的传感器节点集就构成了地面无线传感器网络。 在这类网络中，节点之间的可靠通信功能是很重要的。地面传感器节点必须能够将 数据有效的传送到基站。由于地面传感器节点的电源能量有限，又难以对其进行充 电。在任何情况下，节点的节能问题都是非常重要的。对于地面无线传感器网络来 说，可能通过多种方式进行节能，如多跳最佳路由，以较短的发送半径通信，网内 数据融合等。 地下无线传感器网络 7 8 ：这种网络的节点通常埋藏于地下或放置于洞穴或 矿井中，以便探测地表下的情况。此外，还有其它的s i n k 节点布置于地表，用于将 传感器节点收集到的信息中继到基站。与地面无线传感器网络相比，地下无线传感 器网络在配置的设备、网络部署和维护等方面的花费都更高。地下传感器节点之所 以更昂贵，是因为必须挑选合适的装置，以便可以顺利穿透土壤、岩石、水和其它 矿物进行可靠的通信。由于在地下环境下，信号损耗和衰减比较大，所以在地下环 境进行无线通信是一个难点。相较地面传感器网络而言，布置地下传感器网络需要 周密的计划和充分考虑能量与价格因素。和地面传感器网络一样，地下传感器节点 也配备能量有限的电池，而且节点一旦部署到地下，就难以对其进行充电或更换电 池。因此，电源是设计地下传感器网络时需要考虑的一个重点因素。 水下无线传感器网络 9 1 0 ：这类传感器网络由一些部署在水下的传感器节点 和移动装置组成。与地面传感器网络相比，水下传感器网络的节点更加的昂贵，节 点数量也较少。具有自治能力的水下移动装置用于探测信息或从传感器节点收集信 息。与密集部署的地面传感器网络相比较，水下传感器网络部署得比较稀疏。水下 无线通信通常采用声波技术实现。但声波的带宽窄、传输延时长和信号衰落等特点 给水下通信造成一定的困难。另一个困难是由于环境因素造成的节点失效问题。水 下传感器节点必须能够进行自我配置和适应恶劣的海洋环境。水下传感器节点同样 只配备了能量有限的电源，也难于进行更换电池或对电池进行充电。 绪论 多媒体无线传感器网络 1 1 ：这类传感器网络被用于以视频、声音和图片等多 媒体方式监测和追踪事件。多媒体传感器网络由一些装备有摄像头和麦克风的价格 低廉的传感器节点组成。多媒体传感器以事先部署的方式放置于监测环境中，以此 保证网络的覆盖面。多媒体无线传感器网络设计中的难点包括高带宽要求、高能耗、 服务质量、数据处理和压缩技术以及跨层设计。多媒体信息需要较大的带宽来传输。 因此，高数据率就导致了高能耗。开发支持高带宽和低能耗的传输技术势在必行。 变化的延时和变化的信道容量使在多媒体无线传感器网络中提供的q o s 服务变得极 具挑战。 可移动的无线传感器网络：这类无线网线由可自主移动并且可以和外界环境互 相交互的传感器节点组成。移动节点和静态节点一样，具有感知、计算和通信功能。 不同之处在于，移动节点可以在网络中变更位置及自由活动。可移动无线传感器网 络一经部署，他们可以相互交换各自收集到的信息。可移动传感器网络与静态传感 器网络的一个关键区别在于数据的分发方式。在一个静态的网络中，数据的分发是 以固定的路由方式或洪泛方式进行的。然而，在可移动网络中采用的却是动态路由。 可移动传感器网络的设计难点包括部署、定位、导航和控制、覆盖率、能耗、维护 和数据处理。部署后就可以进行工作，移动节点可以扩散出去收集信息。 二、无线传感器网络的应用 无线传感器网络的应用方案可以归为两大类 5 ：监测与追踪( 如图0 - 2 所示) 。 监测应用包括户内户外环境监测、医疗和健康监测、能量监测、库位监测、工业控 制自动化和地震监测。追踪应用包括追踪物体、动物、人类和交通工具。当前已有 许多这方面的研究，现举几个例子。p i n p t r 2 是一个用于检测和定位射击者的实验 系统。该系统使用分布密集的传感器网络来检测和测量一次射击中产生的声波的到 达时间。传感器节点将所测量得到的结果传输到基站，让基站计算出射击者的位置。 m a c r o s c o p eo fr e d w o o d 3 是一个研究无线传感器网络的案例。该案例用于监测和 记录红杉树林。在该系统中，传感器节点被部署在树上不同高度位置并让每一个传 感器节点对树林中的温度、相对湿度等环境变量进行测量。专家对红杉树林周围的 气候空间梯度变化进行跟踪并对他们的生物理论进行验证。半导体工厂和油箱应用 案例 4 对设备预防性维护进行了研究。该案例通过传感器节点采集的振动特征来预 测设备的运行状态。 福建师范大学蒋佳铭硕士学位论文 军事领域 敌人追踪 商业领域 人物追踪 传感器网络 追踪 栖息地 动物追踪 公共- l - 业领域 汽车追踪 军事领域 安全监测 商业领域 库存监测 医疗卫生领域 病人监测 监测 图0 - 2 传感器应用分类 f i g u r e0 - 2c l a s s i f i c a t i o no fa p p l i c a t i o no f w s n 第二节组播协议的研究现状 栖息地 动物监测 公共工业领域 基础设施监测 化学物品监测 环保领域 环境监测 ( 天气，气温，气 压) 部署在某一监测区域内、用于记录和收集环境参数的大量传感器节点组成传感 器网络。由于这类网络往往对某一区域内的传感器节点集的数据感兴趣，而不是对 某一特定节点感兴趣，所以高效的组播是一项很有吸引力的网络服务。用组播方式 传送这类信息比使用单播传送同样的信息更加高效、低损耗、灵活。而组播协议的 设计是解决这类问题的有效方法之一。当前，针对无线传感器网络而设计的组播协 议可以进行如下分类 1 2 ： ( 1 ) 基于树型结构的组播路由协议 ( 2 ) 基于能量的组播路由协议 ( 3 ) 基于组群区域的组播路由协议 下面，分别针对这三类协议进行简要的介绍。 一、基于树型结构的组播路由协议 这类协议的中心思想是先构建一棵组播树，然后数据包从源节点开始沿着组播 树被转发到所有其它组成员节点。为了构建组播树，源节点广播请求信息包，以期 绪论 发现子节点；同时，子节点也以相同的方式发现它的子节点，最终构建出以源节点 为树根节点的组播树。这类协议的典型代表包括 4 7 4 8 4 9 5 0 1 4 1 3 1 9 。 s i g m 4 7 的提出主要是为了解决由于s i n k 节点的位置变化而引起的一系列维护 组播树所产生的问题。为此，s i g i 让每个s i n k 节点自己构建连接源节点的路径。 s i g m 以源节点所在位置为圆心，以1q ( 1 = 0 ，l ，2 ) 为半径将监测区域划分成1 个环域，每个环域划分成4 ( 2 1 + 1 ) 个相同的子区域。如图0 3 所示，当处于某一子 区域内的s i n k 节点移出原来的子区域时，该s i n k 节点就向源节点发起一次位置改 变通告。当通告到达边界节点时，该通告将被以l i n ep a t h - b a s e d ( 或c i r c l e p a t h - b a s e d ) 的方式转发，直到该通告到达源节点或m e r g i n gn o d e 。这样就构建起 一条由源节点到达该s i n k 节点或先由源节点到达m e r g i n gn o d e ，再到s i n k 节点的 路径。所有s i n k 节点对应的这样的路径就构成了一棵以源节点为根节点的组播树。 数据包沿着该组播树转发到各个s i n k 组成员中。 m e 睁骘 t - 一一 l 峨l m 2 ： m c r 嘲l i t 4 图0 3 路径构建示意图 f i g u r eo 一3s c h e m a t i cd i a g r a mo fp a t hc o n s t r u c t i o n 在g m r 4 8 中，组树中的每一个节点试图以广播次数据包的方式将该数据包分 发到组播树中的所有分支。在每一次广播中，该节点都在数据包中指定一些邻居节 福建师范大学蒋佳铭硕士学位论文 点作为中继节点以及每个中继节点所必须负责转发数据包的目的节点集。中继节点 的选择按如下标准进行：选择使c o s to v e rp r o g r e s sr a t i o 最优化的节点集。该标 准试图做到选择最少中继节点的同时让数据包前进的距离最大化。当中继节点接收 到数据包时，根据数据包中为自己指定负责的目的节点集时行相同的操作，直到所 有目的节点接收到数据包。 h r p m 4 9 的主要目的在于解决数据包报头随网络规模增长而增长过快的问题。 为了达到这个目的，h r p m 将监控区域划分成大小适合的子区域。每一个子区域选择 出一个a p ( a c c e s sp o i n t ) 。而整个监控区域选择出一个r p ( r e n d e z v o u sp o i n t ) 。落 在各个区域内的组成员节点通过各自的a p 与r p 联系。而r p 再与源节点联系。这样 就构成了一个以r p 为根节点、各个a p 为非叶子节点及各个区域内的组播组成员为 叶子节点的树型结构。当某一源节点有数据包要发给组成员时，它首先根据组标识 计算出r p 的位置，然后从该r p 处获取组成员向量。再根据该向量将含有组成员的 子区域的a p 构建成一棵s o u r c e - a p s 树。而各个子区域内的组成员与对应的a p 构 建成一棵a p & m e m b e r s 树。这样，源节点的数据包就通过r p 到达各个a p ，再通过 a p 到达所有的组成员。 h g m r 5 0 则结合了g m r 与h r p m 的优点，提出了一个具有g m r 的发送数据包的高 效性和具有h r p m 的报头的简洁性的路由协议。h g m r 在r p 专a p s 之间采用h r p m 的方 式转发数据包，而在a p - ) m e m b e r s 之间采用g m r 的方式转发数据包。 e m r s 1 4 是一种基于树型结构的组播路由协议。该协议用于将数据包从基站分 发到所有其它的节点。基站为了构建这棵组播树，首先广播一请求包以期发现自己 的子节点，而其子节点也以同样的方式发现自己的子节点。 v l m 2 1 3 为资源受限且具有层次结构和一定移动性的无线传感器网络提供了轻 量级的组播服务。该服务直接建立在链路层之上。采用这种模式设计的多播协议不 但可以减少路由状态数和代码规模，还能够适应由于节点加入离开组播树，或节点 位置发生变化引起的网络拓扑变化。协议的核心思想是：在基站到节点的下行方向 上提供多播、单播和广播三种不可靠的数据报服务，而在节点到基站的上行方向上 提供单播和广播两种服务。 许多研究都致力于数据分发策略的研究，如文献 2 0 2 1 。在这些方案中，源 节点和s i n k 节点一起形成一棵以源节点为根节点的组播树，源节点将数据沿着树的 分支推送到s i n k 节点。但是，传感器节点的通信半径小以及源节点和s i n k 节点的 绪论 频繁移动可能导致某个s i n k 节点由于路径的损坏而无法接收到数据包，而且树型结 构也必须频繁的重新配置以重新建立源节点与s i n k 节点之间的连接。为了解决这类 问题，d p t b 1 9 提出了自己的方案。在该方案中，每一个源( s i n k ) 节点都和一个被 称为源( s i n k ) 代理的静态的传感器节点相关联。所有相关联的源节点相同的代理构 成一棵代理树。有了这棵代理树，源节点可将数据推送到代理，代理再进一步将数 据推送到多个s i n k 代理，而s i n k 可以以查询的方式从自己的代理那就获取数据。 二、基于能量的组播路由协议 传感器网络的基本功能为收集和传输感知数据。能量被认为是最珍贵的资源之 一。因为对数以千计的远程节点或部署于对敌对环境下的节点进行能量补给是很困 难的，所以通过节约能量的使用以延长电池生命周期显得十分重要，而如何高效的 使用能量也就成为设计传感器网络路由协议时需要考虑的重点因素之一。这类协议 的中心思想为以尽可能高效的方法转发数据，从而达到延长网络的生存周期的目的。 这类协议的典型代表包括 1 5 1 6 5 1 3 2 。 b a m 1 5 的主要贡献在于减少了无线通信负载传感器节点的主要能量因素。 b a m 不使用像j o i n l e a v e 这类控制包，也不管理多播组。b a m 由两种数据聚合技术 构成：一跳聚合( s - b a m ) 和多路径聚合( m b a m ) 。s - b a m 用于减少每一分支上的冗余 通信负载，m - b a m 的作用在于减少分支的数量。s - b a m 与m - b a m 的结合，可以有效地 降低无线通信量，从而节约能量使用。 d p a m 1 6 以监测区域范围比较大、具有多个观察者的自组织密集型传感器网络 为模型，设计了一种分布式体系结构。该结构通过应用层感知数据缓冲技术和异步 更新多播技术来节省能量。该体系结构的目标是降低网络基本功能数据收集和 数据传输一的能量消耗，从而延长网络生命周期。 e b m r p 5 1 的目的在于通过变更路由的方式达到均衡网络能耗。为了实现这个目 的，源节点以自己为中心将监测区域划分成四个象限，并根据目的节点的位置将同 一个象限内的目的节点归成一组。然后源节点为每一个象限( 如果该象限内有目的节 点) 创建一个路由发现包，并将各个象限内的目的节点置于路由发现包内。路由发现 包创建好后，源节点为每一个包在其各自对应的象限内选择一个中继节点，然后将 该包发送给中继节点。中继节点接收到路由发现包后，将自己当作新的源节点，以 进行上述相同的操作，直到所有目的节点都接收到该包。至此，路径也就构建完成。 数据包便沿着上述所建立的路径转发到各个组成员节点。经过若干次数据包的传输 福建师范大学蒋佳铭硕士学位论文 后，源节点将原来的象限任意旋转一个角度，再重新进行路径发现操作以建立新的 数据包转发路径。 为了达到高效使用能量的目的，m s t e a m 3 2 采用了贪心算法。源节点s 首先计 算出一棵仅包含s 和所有目的节点的最小生成树。再根据源节点s 处的分支数n 将 目的节点集划分成n 个分别由各个分支负责数据包转发的子节点集。然后，s 在自 己的邻居节点集中为每个子目的节点集选择一个最优转发节点。将子目的节点集嵌 入数据包中发给转发节点。转发节点接收到数据包后，判断自己是不是目的节点? 如是，则从目的节点中将自己删除，然后进行和源节点相同的操作。直到所有的目 的节点接收到数据。 三、基于组群区域的组播路由协议 基于组群模式的组播协议的中心思想为把节点划分成不同的区域，各个区域按 照选定的方式移动，组内节点之间及组与组之间可以采用不同的通信方式。这类路 由协议的典型代表包括 5 2 1 7 e l s 等。 5 2 将组播区域定义为一个闭合多边形，并提出了两种多播策略。在第一种策 略中，定义了转发区域。当某节点接收到数据包时，根据数据包中的转发区域信息 决定是否转发数据包。如果该节点处于转发区域内，则向其邻居节点转发该数据包。 否则将数据包丢弃。在第二种策略中，文献并没有定义转发区域，而是将组播区域 说明、区域中心坐标和发送节点坐标置于数据包头中。当某一节点接收到数据包时， 根据自己到组播区域中心的距离与发送节点到组播区域中心的距离关系及发送节点 是否处于组播区域内决定自己是否转发数据包。该文还对算法进行了优化。 在t e a mm u l t i c a s t 1 7 中，研究对象为由装备有各种各样传感器的无人机器组 成的队。这些队要求有高效的通信方式来反馈感知数据、与其它队交互信息、执行 复杂的任务。在每一个队里的节点具有相同的运动模式，这一运动模式称为“共联 队模型 。整个系统由孤立的地面传感器网络、群和连接群的骨干节点所组成。地面 传感器网络由多种不同的传感器( 如环境监控传感器，化学探测传感器，运动探测传 感器等) 组成。此外，队具有如下性质：( a ) 相同的移动模式：相同的移动模型即为 “共联队模型”。( b ) 执行的任务相同。( c ) d 跳可达性：队内的任意两个节点 在d 跳内相互可达。t e a mm u l t i c a s t 中的m l a n m a r 协议是对l a n m a r 的改进。 m - l a n m a r 在源节点与每个队的代理节点之间建立了一条通道。有数据需要发送时， 源节点向每个l a n d m a r k 都发送一份数据拷贝。当数据拷贝到达l a n d m a r k 时， 绪论 l a n d m a r k 将其在队内进行广播。t e a mm u l t i c a s t 非常符合由装备有多种不同传感器 的移动实体组成的队之间的通信要求。 m o b i c a s t 1 8 3 协议的特点在于在特定的时间向某一特定区域的节点分发组播信 息。该协议通过两类技术将空间约束条件和时间约束条件结合在一起考虑：其一为 请求向某一特定区域内的所有节点转发信息；其二为将时间约束表示为一个时间函 数。 为了更好的比较上述几种协议，将这些协议的消息域、缓存、数据汇集、节点 定位、鲁棒性和扩展性等几个方向的指标列在表0 - 1 中。 表o 1 组播协议比较 器 e 麟v l n l 2d r u t e a mm o b i c a s t 比较尺度 m u l t i c a s t 消息域l 跳l 跳1 跳1 跳1 跳 缓存无有有无 无 数据汇集无无有有无 节点定位无无无有有 鲁棒性 扩展性 第三节课题来源及内容安排 本文的课题来源于如下基金项目：国家自然科学基金项目( n o 6 1 0 7 2 0 8 0 ) ：跨层 协作的可编程无线m e s h 网络案例关键技术研究；福建省自然科学基金项目 ( n o 2 0 0 8 3 0 0 1 4 ) ：基于容错分簇和跨层协作的传感器网络安全匿名路由技术。本文 以无线传感器网络为研究对象，针对不同的应用方案提出了相应的组播算法，以求 达到延长网络周期或提高组播可靠性的目的。论文的主要工作和内容安排如下： 第一章以锚节点与监测区域相距很远的无线传感器网络为研究对象，提出了一 种能量均衡的组播路由算法。该算法分成两个阶段：在第一阶段，前向转发区域内 的候选节点通过依据自己的剩余能量及到接入点的距离设定定时器来竞争转发数据 包；在第二阶段，算法在多播区构建一棵以接入节点为根节点的组播树，树中的节 点根据当前父节点及候选节点的剩余能量更新父节点。该章最后用仿真实验验证了 福建师范大学蒋佳铭硕士学位论文 该算法在延长网络生命周期上的有效性。 第二章为了均衡无线传感器网络中节点的能量消耗，进而达到延长网络生命周 期的目的，提出一种以最小生成树形成虚拟主干树的能量均衡的组播路由算法。该 算法在选择转发节点的过程中，综合考虑前向转发区域内的节点的位置及能量信息， 并引入修正因子及路径封锁技术。仿真实验表明，该算法能够有效的均衡传感器节 点的能量消耗，延长网络的生命周期。 第三章出于提高组播树的可靠性，进而达到提高组播效率的目的，提出了一种 基于声誉机制的组播协议。该协议在构建组播树时考虑节点的声誉值，从而将自私 性节点排除在组播树之外，使得构建的路径比较可靠。仿真实验表明该协议可以有 效的提高组播效率。 第四章在总结本文研究成果的基础上，对论文的下一步研究工作做了展望。 第一章无线传感器网络中能量均衡的组播路由协议 第一章无线传感器网络中能量均衡的组播路由协议 资源受限是无线传感器网络的一大显著特征，故能量问题也就成为设计无线传 感器网络协议时所要考虑的主要问题之一。本章以节点具有位置信息的传感器网络 为研究对象，讨论了基于位置信息的组播路由协议。 第一节问题的提出与网络模型 多播是一个源节点将数据包发送到一组目的节点的通信方式 2 2 。多播路由就 是寻找一棵以源节点为根节点，以所有目的节点为树成员节点的多播树。2 0 0 3 年， 文献v l m 2 1 3 首次讨论了在w s n s 中的多播问题。该文构建了一棵多播树，源节点 用这棵树向所有传感器节点发送查询和控制信息。与v l m 2 不同的是m o b i c a s t 1 8 利用一种网络拓扑感知技术，通过构造一个动态的转发区域来将实时信息发送到网 络中某个投递区域内的所有节点。s a r f 2 2 将路由分为两个阶段，第一阶段使用 d i j k s t r a 算法在s i n k 节点和接入节点之间建立一条最短路径；第二阶段将数据包 在多播区域内进行洪泛。s a m 2 2 的第一阶段和s a r f 一样，第二阶段则是在多播区 域内构建一棵多播树。e e m r a 6 也将路由分成两个阶段，第一阶段使用了动态规划 模型寻找从s i n k 到接入节点的路由；第二阶段也在多播区域建立一棵多播树。在上 述的协议中，v l m 2 和m o b i c a s t 只适用于特定应用，缺乏普遍性；而s a r f 容易使最 短路径上的节点能量消耗过快，从而导致网络过早死亡；e e m r a 使用的动态规划模 型计算较为繁复，并且它构建多播树的方法会导致多播区域中的一些节点成为孤立 节点。本章以延长网络的生命周期为目的，提出了一种能够有效地均衡网络中节点 的能量消耗的多播路由协议( e n e r g yb a l a n c i n gp r o t o c o l ，e b p ) 。 考虑由n 个随机部署的传感器节点组成的多跳无线传感器网络，如图1 - 1 所示， 节点集合为s = 瓴，。：， ，isi = n 用图g = ( 矿，d 来表示该无线传感器网络的拓扑结构， 其中v 表示传感器节点集；e e v 2 表示边集( 巧，一) ，其中k ，_ e v 且两者均在对方的通 信范围内。 假定网络中的节点已知地理坐标信息，基于地理位置的多播不同于因特网上的 传统多播。在传统的多播中，一个节点要想成为某一个组播组的成员，它必须显示 的申请加入该组播组，故组成员有可能散布在整个网络。而在基于地理位置的组播 福建师范大学蒋佳铭硕士学位论文 1 1 一置l s i n k 曩：0 簿t ， 一 一 ；o ：f 。 - - 。 一； 二1 二乙： 三t 己 i 。 - 。 ? - - - - - ； = 砒( | ) + 一( 七，d ) ( 1 - 1 ) 距离为d 的节点对收发k 比特数据的总能耗为： e 。= e + e h = 砒( 七) + 一( t d ) + k 撕( 七) ( 卜3 ) = 2 七+ 七d 2 在( 卜1 ) 式、( 卜2 ) 式能量消耗模型公式中，屯表示无线收发电路所消耗的能量， 依据 6 ，假定= 5 0 n j i b i t 。为此模型中功率放大器所消耗的能量，假定 s a m p = l o o p j b i t m 2 。 第一章无线传感器网络中能量均衡的组播路由协议 第二节算法描述 算法包括两个阶段：第一个阶段为s i n k 节点到a p 之间路由数据包阶段。该阶 段中，当前转发节点将数据包发送出去并监听是否有节点中继该数据包，是则不做 其它动作；否则算法转入“空洞修复策略。第二个阶段在多播区域中构建一棵以 a p 为根节点的多播树，数据包沿着多播树进行分发：树中的节点根据信标提供的信 息，实时地更新自己的父节点，以实现均衡能量消耗。 一、s i n k 节点和a p 之间数据包的路由算法 步骤l ：当前转发节点( 起中继数据包作用的节点，包括刚开始时的s i n k 节点和 之后每跳中被选中以转发数据包的节点) 将数据包发送出去，前向转发区域( 图1 - 2 中所示的小圆) 内的节点根据自己到a p 节点( 即为图1 - 2 中的d 节点) 的距离和自己 的剩余能量设置定时器来竞争转发数据包。定时时间长度计算如下： k _ ( 1 量e oy 怒幸死 ( 1 _ 4 ) d u ，a 即 公式( 卜4 ) 中巨表示前向转发区域中候选节点i 的剩余能量，反表示节点的初始 能量，a ( i ，胛) 表示前向转发区域中候选节点i 与a p 之间的距离，d u ，a p ) 表示当前 转发节点j 与a p 之间的距离，瓦表示定时器的可设定的最大时间。节点i 根据公 式( 卜4 ) 计算得到的实际定时时间大小k 设定自己的定时器。前向转发区域内的候 选节点根据定时器超时时是否已经有其它候选节点发送数据来决定自己是否要转发 数据。 步骤2 ：前向转发区域内的节点在自己的定时器超时前，如果监听到已经有其它 节点转发该数据包，就将自己的定时器取消，放弃转发数据包；否则，定时器超时 后，将包转发出去。 福建师范大学蒋佳铭硕士学位论文 图1 2 前向转发区域及“空洞现象” f i g u r e1 - 2f o r w a r d i n ga r e aa n dv o i d 修复策略：在转发过程中，可能出现这么一种情况：前向转发区域内不存节点， 即“空洞现象( v o i d ) 。在图1 - 2 中，如果小圆内不存在任何节点，那么小圆覆盖 的范围就是一个“空洞 ，而此时的当前转发节点s 称为“凹节点”。 我们采用如下算法来解决这个问题： 1 ) 当前转发节点将数据发送出去后，设定一个定时器。若在定时器超时前监听 到有邻居节点转发数据包( 说明还没有出现空洞) ，不做任何动作：否则发送一个信 标( q u e r y n e i g h b o r s ) 向周围一跳邻居节点收集位置信息( 图卜3 ) 。 2 ) 周围邻居节点收到该请求后，将自己的位置信息发送给当前转发节点。 图1 3 发送信标、按“左手定则 转发及按“右手定则”转发 f i g u r e1 3s e n d i n gb e a c o na c c o r d i n gt o “l e f th a n dp r i n c i p l e o r r i g h th a n d p r i n c i p l e 3 ) 当前转发节点收集到信息后，首先判断是否存在比自己到a p 近的邻居节点， 如果有就采用单播的形式将数据包发送给该邻居节点；否则，让当前转发节点构造 一个“平坦子图 6 ，然后将数据包中的状态标志设置为修复状态( 图卜4 ) ，且将 自己的位置信息放入数据包包头，并按照“f a c er o u t i n g 中的“左手定则”或“右 第一章无线传感器网络中能量均衡的组播路由协议 手定则 发送数据。如图1 - 3 所示，如果图中的b 节点不存在，那么当前转发节点 s 将按照“左手定则”把数据包发送给节点h ：否则，s 将按照“右手定则”把数据 包发送给节点b 。 4 ) 下一跳节点接收到数据包后，首先检查状态标志位是否为修复状态，如果为 正常状态，则按正常方式发送数据；如果为修复状态，判断自己是否比“凹节点 到接入节点的距离近，如果是则将数据包的状态设置为正常状态( 图i - 4 ) ，按正常 方式发送数据；否则继续以“f a c er o u t i n g ”方式发送数据。 该采用基r f a c er o u t i n g 基础演化出的修复策略具有保证数据包的可达性( 在 网络连通的前提下，可以保证将数据包送达目的节点) 的特性，由于篇幅限制，具体 证明过程参见 2 5 。当数据包到达a p 时，a p 发送一个信号，通知它的邻居节点不 用再向其转发数据包。于是该转发过程结束。 根据上述的算法，数据包从s i n k 节点路由到a p 的过程是一个随机选择转下一 跳节点的过程，该选择过程在候选节点的剩余能量与候选节点到a p 的距离之间进行 一个综合考虑，在每一次多播都选择出当前比较恰当的候选下一跳节点作为下一跳， 这样每一次多播过程中选择的路径都有可能不一样，从而将能耗在所有的候选节点 之间进行均衡。 b 一一一jd j、c，? j ：i 、，。 。、， j i i 、 、， - 一、 图1 - 4 状态转换图。 f i g u r e1 - 4s t a t ec o n v e r t i n g 当数据包由节点a 发送给节点c 时，由于节点c 的前向转发区域内没有候选节 点，即节点c 为“凹节点 ，于是节点c 将数据包的状态设置成“修复状态并按修 复策略将数据包发送给节点e ；节点e 接收到数据包后，发现数据包被标记成“修 复状态”，于是将自己到目的节点d 的距离和“凹节点”到目的节点d 的距离作比较， 福建师范大学蒋佳铭硕士学位论文 发现自己到d 的距离更近，于是将数据包标记为“正常状态 并将数据包发送给前 向转发区域内的节点b 。 二、多播区域中多播树的建立与数据传输算法 ( 1 ) 多播树建立与更新 多播区域内的所有节点拥