无线传感器论文

zddyjs 贡献于2013-04-09

作者 ll  创建于2009-05-04 07:49:00   修改者番茄花园  修改于2009-06-01 01:37:00字数39524

文档摘要: 无线传感器网络是一个新兴的交叉学科,其综合了微机电系统(MEMS),传感器技术,嵌入式计算技术,现代网络及无线通信技术、分布式信息处理技术等多个学科,通过分布在监测区域内的大量节点实时监测、感知和采集网络的分布区域内的有用信息。目前,无线传感器网络在学术和应用方面都有了很大的发展,但仍然有许多问题需要解决。
关键词:

 原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研究所取得的成果。除文中已经注明引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体,均已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者: 日期: 年 月 日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品,知识产权归属郑州大学。根据郑州大学有关保留、使用学位论文的规定,同意学校保留或向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅;本人授权郑州大学可以将本学位论文的全部或部分编入有关数据库进行检索,可以采用影印、缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文或与该学位论文直接相关的学术论文或成果时,第一署名单位仍然为郑州大学。保密论文在解密后应遵守此规定。 学位论文作者: 日期: 年 月 日 中文摘要 中文摘要 无线传感器网络是一个新兴的交叉学科,其综合了微机电系统(MEMS),传感器技术,嵌入式计算技术,现代网络及无线通信技术、分布式信息处理技术等多个学科,通过分布在监测区域内的大量节点实时监测、感知和采集网络的分布区域内的有用信息。目前,无线传感器网络在学术和应用方面都有了很大的发展,但仍然有许多问题需要解决。 鉴于无线传感器网络自身的特点,其路由协议的要求也与现有网络的路由协议不同,因此使得设计符合无线传感器网络需求的路由成为一个研究热点。本文通过对现有的无线传感器网络路由算法的分析和比较,提出基于梯度的分簇算法ETBG(energy-aware topology control protocol based on gradient)。 ETBG算法通过基站把网络划分为以基站为中心的近似同心圆的梯度场,以建立网络中节点到达基站的最小跳数的簇树结构;通过分布式并行算法选择选取权值最大的节点成为各级簇头(树节点),能够有效地避免网络中能量少的节点过早死亡的情况;同时针对网络中能耗的分布不均的特点,利用每次簇头轮询时,更换基站节点位置的方法,使得网络中能量能够更加均匀的消耗,以延长网络的生存周期;最后,通过仿真验证算法的有效性。 第四章是通过一个路由算法在NS2上的实现,研究在NS2上添加新协议的过程,并研究NS2仿真无线传感器网络能量有效路由的方法。 关键词:无线传感器网络 NS2 分簇 梯度 基站移动 能量有效 路由协议 ABSTRACT ABSTRACT The wireless sensor network (WSN), which is integration of sensor techniques, MEMS techniques and network communication techniques, is a new interdisciplinary branch of science. It uses huge amounts of nodes ,that disseminate in the monitoring area ,to monitor , apperceive and gather useful information. Now, the wireless sensor network has made great development in academia and application area, but there are also a lot of problems in need of solution. Beacause of the features of the wireless sensor network,the requirements of WSN’s routing protocol are different with the traditional networks.So it needs to design some new routing protocol that accord the requirements of wireless sensor network, designing routing protocol has been a hotspot in the wireless sensor network.This paper analyses and compares the existing wireless sensor network routing protocol,at last introduces an energy-aware topology control protocol based on gradient(ETBG). The ETBG uses the Base-Station to make the network to be a concentric gradient ,builds a cluster-tree that has the least hops to the Base-station.It chooses the maximal weights value nodes to be the cluster heads in parallel,that can avoid the low energy node premature death.Because of the energy –consume is pockety in the nerwork.,the ETBG use Mobile-Base-Station to balance the energy load and prolong the network lifetime.At last,this paper uses simulation to validate the ETBG arithmetic. At last,this paper realizes a routing arithmetic in the NS2 to study how to add new protocol in the NS2 and how to simulate with NS2. KeyWords:Wireless-Sensor-Network NS2 clustering gradient Mobile-Base-Station energy-aware routing-protocol 目录 目 录 中文摘要 II ABSTRACT III 第一章 绪论 1 1.1 无线传感器网络体系结构 1 1.2 无线传感器网络的特征及应用 3 1.2.1 无线传感器网络的特点 3 1.2.2 无线传感器网络的应用范围 4 1.3 无线传感器网络关键技术 5 1.4 无线传感器网络协议栈 6 1.5 本文的主要内容 8 第二章 无线传感器网络现有路由协议分析 9 2.1 无线传感器网络路由协议特点 9 2.2 无线传感器网络路由协议设计要点 11 2.3 无线传感器网络路由协议分类 11 2.3.1 平面路由协议 11 2.3.2 分层路由协议 15 2.4 EAHC算法研究 19 2.5 本章小结 21 第三章 基于梯度的分级簇算法 23 3.1 模型和问题描述 23 3.1.1 网络模型 23 3.1.2 能量模型 24 3.1.3 网络能耗分布 25 3.2 算法描述 26 3.2.1 定义 26 3.2.2 符号声明 26 3.2.3 算法 27 3.2.4 算法特例说明 28 3.2.5 仿真分析 30 3.3 基于该分级簇的路由方案 33 目录 3.4 本章小结 35 第四章 EAMCT-G算法在NS2上的实现 36 4.1 NS2简介 36 4.1.1 NS2的分裂对象模型 37 4.1.2 NS2的模拟过程 37 4.1.3 NS2中无线节点的结构 38 4.2 EAMCT-G算法的NS2实现 39 4.2.1 EAMCT-G算法 39 4.2.2 NS2实现EAMCT-G算法的主要过程 39 4.2.3 仿真分析 45 4.3 本章小结 48 第五章 总结和展望 49 5.1 全文总结 49 5.2 研究展望 50 参考文献 51 发表论文与科研情况 55 致 谢 56 第一章 绪论 第一章 绪论 1.1 无线传感器网络体系结构 随着传感器技术、微机电系统技术、无线射频通信技术以及信号处理技术的飞速发展,出现了一种由大量廉价、低功耗、仅具备有限计算和通信能力的微小传感器节点组成的无线传感器网络(Wireless Sensor Networks,WSN),节点之间采用多跳、无线射频或光波等方式通信,相互协作共同完成诸如数据采集、目标跟踪和指定区域监控等任务[1][2][3][4]。它综合了传感器技术、嵌入式计算技术、通信技术、分布式信息处理技术、微电子制造技术和软件编程技术等。无线传感器网络在工业、农业、交通、军事、安全、医疗、空间探测、以及家庭和办公环境等众多领域都有着广泛的应用,其研究、开发和应用关系到国家安全、经济发展的众多领域。因无线传感器网络的广阔的应用前景和巨大的应用价值,近年来在国际上引起了广泛的重视。一些有实力的大公司如Intel、IBM 已经投入大量人力和物力进行相关产品的研发工作,且国内外已经出现了众多无线传感器网络相关实用产品。 图1-1 无线传感器网络体系结构 典型的无线传感器网络结构如图1-1所示,它由大量廉价的节点分布在监测区域组成。具有射频功能的传感器的节点分布在监测区域内,负责对区域内数据的感知和采集,数据通过 第一章 绪论 单跳或者多跳的方式把在区域内采集的信息传送给基站节点(BS),基站节点可以通过Internet网络发送给远处的用户,或者直接把信息传送给用户。反之,用户可以通过Internet网发送命令给BS(或直接发送命令给基站),而BS再将命令转发给网络内的各个传感器节点。 图1-2 传感器节点硬件结构 传感器节点兼作网络的终端和路由器双重功能,进行数据的收集,处理,对其他节点收集的数据进行存储、管理和融合。其典型结构如图1-2,一般由处理器模块、传感器模块、无线通信模块、存储器模块和电源模块组成。处理器模块负责对整个节点进行控制管理;传感器模块负责对兴趣数据进行采集;无线通信模块负责节点间的通信;存储器模块负责对数据进行缓存;电源模块负责为系统各个部分提供能量,通常无线传感器节点采用电池供电。此外,由于应用场合的要求,传感器节点还可能提供部分支持模块,如定位模块、移动管理模块等[5]。现在国内外已经研制出了众多传感器节点,如国外的有:CrossBow公司的MPR500,Moteiv公司的Tmote Sky,Intel的iMote等;国内的主要有中科院计算所宁波分所的GAINS系列节点。 第一章 绪论 1.2 无线传感器网络的特征及应用 1.2.1 无线传感器网络的特点 1) 节点数量众多,密度高 通常无线传感器网络是由成千上万甚至更多的节点分布在监测区域内,以准确的获得监控对象的信息。高密度的分布有利于用简单的节点获得复杂节点才能获得的高精确度,同时能够提高网络的健壮性和鲁棒性,使得网络在部分节点失效后依然能够继续工作。 2) 节点的能量、计算能力和存储容量有限 随着传感器节点的微型化,大部分节点采用电池供电,其能量有限,由于监测区域条件的限制,通常在使用过程中难以为节点更换电池,因此能量限制成为整个无线传感器网络的设计重点。同时节点大多采用单片机作为主控和管理单元,其计算能力及存储能力都较低,必须为其设计简单有效地协议等。 3) 网络的拓扑结构易变,具有自组织能力 无线传感器节点通常是通过飞机等工具随机的抛洒在监测区域,无法事先了解到网络的拓扑状态,这要求网络具有自组织等能力,能够有效地建立一个拓扑,及路由链路完成网络的组织和数据采集等功能。另外,无线传感器网络中的节点一般都能够在工作和睡眠状态之间切换,传感器节点随时可能发生故障或者能量消耗完等原因导致链路中断,或者由于添加新的传感器节点到网络中,这些原因都能导致网络拓扑的变换,网络拓扑的易变要求无线传感器网络的协议具有自组织,自管理,自配置等能力,保证网络拓扑发生变化时,网络能够继续工作。 4) 无线传感器网络是以数据为中心的,网络节点具有数据融合的能力 目前的互联网系统,网络终端脱离网络仍能够独立的工作。网络中的设备是通过ip这一唯一与之对应的地址标识进行通信的,是一个以地址为中心的网络。而传感器网络是任务型网络,脱离了传感器网络谈论传感器节点没有任何意义[6].传感器网络中的节点一般采用节点编号标识,构成的传感器网络与节点编号之间的关系是动态的,节点编号与节点位置没有必然的联系。用户使用网络查询感兴趣的事件时,直接把感兴趣的 第一章 绪论 事件通知网络,而不是通知给某个确定编号的节点。网络中可能同时有多个节点收集到用户感兴趣的事件,因此兴趣事件在网络中传送时要经过数据融合处理后在转发,以减少网络中不必要的能量开销。 1.2.2 无线传感器网络的应用范围 随着微电子技术的发展,无线传感器节点不断地微型化,成本也大大的降了下来。虽然无线传感器网络的部分理论还有待进一步研究,但无线传感器网络的优点使得其已经在部分领域中得到了应用: 1) 环境的监测和保护 近年来环境问题越来越引起人们的重视,需要采集的环境数据也越来越 多,而无线传感器网络能够用大量的节点分布在监测区域采集数据的特点,具有部署方便,无需人为维护的优点,为对环境问题的研究提供了便利的方法。 2) 医疗护理 传感器网络可以应用在监测人体的各种生理数据,跟踪和监控医院内医生和患者的行动,医院的药物管理等。微型节点组成的无线传感器可以监控护理病人的病情、收集人体的生理数据,发现异常及时处理,同时不会对监控的病人带来任何的不便。 3) 军事领域 无线传感器网络具有节点小,随机分布,部署方便,隐蔽性强,很好的 健壮性和鲁棒性的特点,适合于恶劣的战场环境,为侦查敌情,监控兵力、判断生物化学攻击等提供了方便。 4) 智能家居 在家电和家具中嵌入传感器节点,通过无线网络和Internet连接起来可以通过远程监控系统对家电进行远程控制等,为人们提供舒适、方便和更具人性化的智能家居环境。 5) 工、农业的应用 由于无线传感器节点采用无线通信的方式组网,节点放置方便,便于对工、 农业数据监测,以便对工业中故障及时发现,农业中病虫害防止、抗旱等做出及时的反应。 第一章 绪论 1.3 无线传感器网络关键技术[7] 1) MAC协议 由大量节点构成的无线传感器网络要求MAC介质访问控制层能够为节点有效地提供无线信道的使用方式及信道资源分配。其必须实现两个基本功能目标:建立一个基本网络基础设施所需的数据通信链路;协同共享介质的访问[8]。但无线传感器网络与现有网络有很大的区别,而且其是应用型网络,不同的应用网络有着不同的需求,传统的MAC协议不再适合无线传感器网络的应用,设计一个有效地MAC协议是无线传感器网络的一个关键问题。 2) 路由协议 无线传感器网络路由协议的目的是选择合适的、正确的优化路径把分组从源节点(采集数据的传感器节点)发送到目的节点(sink节点)。由于无线传感器网络节点具有能量限制,节点数目通常很大,节点只能获取局部信息来构建网络,因此传统有线网络,无线局域网以及移动自组织网络中的现有路由协议不能够很好应用在无线传感器网络中。同时由于无线传感器网络节点的分布呈随机状态,以及其应用需求的不同,要求建立的网络具有的性能也有所不同,所以很难设计一个适合无线传感器网络的通用路由协议。其路由协议的设计是具有针对性的。 3) 能量管理机制 由于无线传感器网络的能量限制,能量管理的功能是有效地管理电池供电的节点的能量的消耗,以延长网络的寿命。一个有效地能量管理机制对无线传感器来说是十分必要的。 4) 数据融合技术 大多数无线传感器网络应用都是由大量传感器节点构成的,共同完成数据采集的任务,因此,在信息采集过程中,会有许多节点采集到相同的数据,这些冗余数据不能全部的传送给sink节点,这样会浪费大量的通信能量在这些冗余信息中,对于能量有限的传感器节点来说,这是不合适的。因此要在数据收集过程中,去除冗余信息,以减少网络不必要的能耗,于是,数据融合的技术被提了出来。 5) 无线传感器网络安全机制 由于无线传感器网络采用无线传输信道,网络中存在窃听、恶意路由、消 息篡改等潜在的安全问题,在某些应用中这是致命的缺陷,需要设计对应的安全机制来保证网络消息的安全。同时,无线传感器网络的能量有限、计算能力有限、存储能力有限的特点使得安全机制的设计更加复杂化。 第一章 绪论 6) 无线传感器网络的定位技术 一般在无线传感器网络中,没有位置信息的监测信息往往是毫无意义的。用户一般关心事件发生的地点或者区域。常见的定位技术有全球定位系统GPS(Globe Position System),但其并不适用于无线传感器网络中的定位技术,无线传感器网络中节点具有低成本的特点,为每个节点配备GPS设备是不现实的,因此需要专门针对无线传感器节点的网络特点提出一种简单有效地无线定位技术。 1.4 无线传感器网络协议栈 图1-3 无线传感器网络的协议栈 如图1-3所示,无线传感器网络的协议栈主要分为两大部分:通信协议层和网络管理接口。通信协议层可划分为物理层,数据链路层,网络层,传输层和应用层;网络管理接口包括:能量管理,网络管理,拓扑管理等。网络管理接口主要是用于协调不同层次的功能以求在能耗管理、移动管理和任务管理方面获得综合考虑的最优化设计[9]。 1) 物理层 提供简单、健壮的信号调制。无线传感器网络通常以无线电作为主要的 传输方式,但也有使用光波等作为通信手段的,和无线电相比,光波传输具有不需要复杂的调制、解调机制,接收器电路简单,单位数据传输功耗小等优点。它比无线电通信更加高效,但只能在某些特殊的应用中使用,如SmartDust中就采用光束为通信介质 第一章 绪论 。 2) 数据链路层 负责数据流的多路复用,数据帧的检测,媒体介入和差错控制,以保证 无线传感器网络中节点之间的链接,主要涉及媒介访问控制(MAC)协议[10][11][12]。 3) 网络层 网络层包括拓扑控制(组网)和路由两个部分。拓扑控制把网络建立成 一个针对应用的优化网络,路由部分提供源节点到目的节点的通信路由。通过网络层,为无线传感器节点提供能量有效地传输路径,有效地减少能量不必要的消耗,延长网络生存周期。 4) 传输层 传输层为无线传感器网络提供有效、可靠地通信。传统传输层的主要目的是:(1)为应用层和网络层可靠地桥梁;(2)为源节点和汇聚节点提供带有误差控制的数据传输服务;(3)通过拥塞机制调整注入网络的消息量,使网络利用最大并尽量避免网络拥塞[13]。但由于无线传感器网络的特有的特点,对传输层的设计也有更多的约束。并且无线传感器网络的特定应用也对传输层的设计有着不同的要求。目前对WSN传输控制的研究还很少,现阶段对传输控制的研究主要集中于错误恢复机制。文献[14]分析了端到端错误恢复机制在无线多跳网络中的性能;文献[15]设计了一种快取慢存的数据流控制机制,通过在数据通路中的每个中间节点中都保持正确的数据包转发次序,来减少错序报文的盲目转发。如何在拓扑结构、信道质量动态变化的条件下,为上层应用提供节能、可靠、实时性高的数据传输服务是今后研究的重点。 5) 应用层 由于无线传感器网络是应用型网络,其应用层的功能随应用的不同而不同,必需针对不同的应用设计相应的应用层,但都有一个同有的功能即数据采集。以数据为中心和面向特定应用的特点要求无线传感器网络能够以自己独特的封装消息的方式,快速有效地把消息汇聚融合后传送给基站或者用户。同时,为了适应不同网络的需求,还要考虑加入时钟同步[16][17]、定位技术[18][19]等功能。 第一章 绪论 1.5 本文的主要内容 近年来,由于无线传感器网络引起了国内外的研究人员的广泛关注,已经取得初步的研究成果,并建立了部分实际的无线传感器网络用作环境 监测等方面的研究。但由于无线传感器网络是一种应用型网络,当前,还没有建立一套通用的适合无线传感器网络的标准。在一些关键理论和技术上,仍有很多问题需要解决,我国研究学者经过近几年在无线传感器网络方面的研究,在理论和应用方面都取得一定得成果。本文将结合国内外已有的研究成果,重点研究无线传感器网络的分层路由算法。本文的主要研究内容如下: 1) 搜集无线传感器方面的理论和应用资料,了解无线传感器网络特点及 关键技术,熟悉无线传感器网络的基础理论。 2) 了解无线传感器网络的路由协议与现有网络路由协议的区别及设计 特点,分析现有无线传感器的典型路由协议优缺点。通过特例详细说明一种基于能量的分级簇 (Energy-Aware Hierarchical Clustering,EAHC)算法。 3) 针对EAHC算法生成簇树级数较高,导致网络节点到基站的最大平均 跳数较大的不足提出一种基于梯度的分级簇算法,并对两种算法进行仿真对比。 4) 通过一种具体算法EAMCT-G (Energy- Aware Multilevel Clustering Tree with Gateway)在NS2上的实现来描述在NS2中添加新协议的具体过程,并对算法生成的trace文件进行分析。 第二章 无线传感器网络现有路由协议分析 第二章 无线传感器网络现有路由协议分析 无线传感器网络的路由协议主要为网络提供针对应用的优化路径,是WSN网络层的核心技术之一。由于无线传感器网络有其自身的特点,其路由协议也不同于现有的有线和无线路由协议,需要提出专有的路由协议。目前,路由协议是无线传感器网络的一个研究热点。 2.1 无线传感器网络路由协议特点 1) 无线传感器中具有一个或多个特殊节点——基站(sink节点或者汇聚 节点)。网络中节点感知和采集的数据通过单跳或者多跳的方式,最终都是送达基站节点的,而网络中的除了基站节点的其他任意节点不会最为数据流的最终目的节点,因此,无线传感器网络中数据流方向是多对一(many-to-one)和一对多(one-tomany)的特点,呈现的是一种收敛播[20],如图2-1所示。而现有的有线、无线网络以及与无线传感器网络最为接近的无线自组织网(Mobile Ad Hoc Networks,简称MANET)都是端到端的传输,网络中任一个节点都有可能成为数据的最终目的节点。 图2-1 收敛播 2) 无线传感器网络中节点一般都十分密集,邻节点采集的数据具有一定 的相似及关联性,存在冗余信息。有研究表明,在分布密度为 的随机区域,传感器间冗余数据量为 第二章 无线传感器网络现有路由协议分析 [21]。因此,信息需要经数据融(Data Fusion)合处理后再进行传输,以减少冗余数据的转发,降低网络中不必要的能量消耗。这在现有的网络中是极少存在的,现有网络的路由协议也就没有考虑这方面的设计,所以现有的路由协议不适合无线传感器网络。 3) 无线传感器网络大多是以数据为中心的网络,用户只关心网络中某个 方向上发生的事件,而不关心网络中的具体的某个节点采集的信息,因此网络中的节点不一定都需要唯一的地址,而传统的网络都是以地址为中心的网络。因此,多数的现有网络协议在以数据为中心应用的无线传感器网络中不能够很好地工作,无线传感器网络需要其独特的路由协议。图2-2说明了以地址为中心的路由和以数据为中心的路由的区别[22]。 (a)AD Routing (b)DC Routing 图2-2 以地址为中的路由和以数据为中心的路由 4) 无线传感器网络中节点多数情况下用的是电池供电,并且大多部署在 恶劣环境内,无法更换电池,能量不能够持久提供,所以为了使网络能够工作更长的时间,能量效率必须放在路由的设计首要地位,服务质量(QoS)放在次要考虑。而传统网络的路由协议均是以最求端到端延时最小,网络利用率最高以及避免通信拥塞和均衡网络流量的最优路径为目的的,其设计的出发点是不同,所以其不能很好的应用在无线传感器网络中。 第二章 无线传感器网络现有路由协议分析 2.2 无线传感器网络路由协议设计要点 基于上节中提到的无线传感器网络路由协议的特点,无线传感器网络路由协议的设计除了包含了部分传统网络路由协议的要点,如正确性,稳定性,公平性及最优性,也包含其独特的设计要求: 1) 能量高效。无线传感器网络的资源有限要求其路由协议能够简单、高 效的传输信息。而无线传感器网络的能量有限要求选择的路由路径能量消耗尽量小,并能够均衡网络的负载能耗。 2) 可扩展性。无线传感器网络的规模随应用的不同而不同,由于某些 原因要在原网络中添加节点,扩大网络规模,这就要求其路由协议能够适应网络规模的变化,具有很好的扩展性,保证网络在规模变化的情况下依然能够获得良好的连通性和能量有效性。 3) 容错性。在某些对监测恶劣环境及灾难性事件的应用中,无线通信链 路易受干扰往往不可靠,节点的下线也能导致通信链路的恶化,这要求无线传感器网络的路由协议具有一定的容错能力和路由修复能力,保证路由的连通和消息传递路径的准确性。 4) 快速收敛性。传感器网络拓扑结构动态变化,但节点的能量和通信带 宽等资源有限,因此要求路由机制能够快速收敛,以适应网络拓扑的动态变化,减少通信协议开销,提高消息传输效率。 2.3 无线传感器网络路由协议分类 目前无线传感器网络并没有一个标准的路由协议的分类,根据不同的角度,有着不同的分类。本文主要根据网络管理的逻辑结构来分类:平面路由协议和分层路由协议。 2.3.1 平面路由协议 平面路由协议是指网络路由的逻辑视图是平面结构,网络中各节点在路由功能上地位平等,都能够充当数据采集节点和数据转发节点。平面结构路由的优点是 第二章 无线传感器网络现有路由协议分析 网络结构简单,网络节点对等,不需要特殊的节点便能够维护网络,路由算法易于实现。缺点是可扩展性小,路由维护开销一般很大。下面介绍几种典型的平面路由协议。 1) 洪泛法(Flooding) 洪泛法[23]是一种经典、简单网络路由协议,网络 中节点如果有数据要发送,即发送一个广播消息给所有的邻居节点,邻居节点收到数据后,也发送一个广播消息给自己的所有邻居节点,直到数据发送到目的节点或者数据的包预设的最大跳数达到为止。如图2-1是洪泛协议的一个示意图,一节点A希望发送一块数据给节点D,节点A首先通过广播将数据副本传送给它的每一个邻居节点,每一个邻居节点收到数据包后,把预设的最大跳数减1,然后将其传输给各自的每一个邻居节点,除了刚刚给它们发送数据副本的节点A外。如此继续下去,直到将数据传输到目标节点D为止或者该数据包所设定最大跳数达到为止。 图 2-3 洪泛法 洪泛法所具有的优点是:实现简单;无需维护网络的拓扑控制信息,不需要为保持网络拓扑信息和实现复杂的路由发现算法而消耗计算资源;不足的地方主要有:(1)存在信息爆炸(implosion)问题,即出现一个节点可能得到一个数据多个副本的现象,如图2-3,E节点同时收到了节点B和C转发来自节点A的消息,使得E接收到多个来自节点A的数据副本;(2)数据出现部分重叠(overlap)现象,即同一节点收到两个或多个同类传感器节点发送的数据性质相同、数值相近的数据,如图2-3中,节点B和节点C同时监测到某个事件发生时,节点E会收到来自节点B和节点C采集的数据性质相同,数据相近的数据包(数据重叠)。 第二章 无线传感器网络现有路由协议分析 2) SPIN (Sensor Protocol for Information via Negotiation) SPIN[24]是一种 以数据为中心的自适应通信路由协议,该协议以抽象的元数据对数据进行命名。为了避免洪泛协议中的信息内爆和重叠现象,SPIN采用了节点间的协商制度和资源自适应机制。传感器节点在传送数据之前彼此进行协商,以确保仅传输有用数据。节点间通过发送元数据(即描述传感器节点采集的数据属性的数据)进行协商,由于元数据仅是采集数据的抽象,其大小远小于采集的数据,这就大大减少了网络的无用数据传输。 SPIN协议的通信过程如图2-4所示。运行SPIN协议,源节点A如果有数据要发送,则传感器节点A首先对外广播含有自己采集数据信息的元数据的ADV数据包给自己的邻居节点;如果它的邻居节点B在收到ADV后需要接收该DATA数据包,那么B就向该节点A发送一个REQ数据包,节点A收到B的REQ消息后,节点A向其邻居节点B发送DATA数据包。接下来B再重复这个过程,这样整个传感器网络中对此数据感兴趣的节点都会得到一份该数据的拷贝。 a)ADV扩散 b)数据请求 c)数据传送 d)ADV扩散 e)数据请求 f)数据传送 图2-4 SPIN协议的通信过程 SPIN的元数据协商机制解决了洪泛算法中的“内爆”、“重叠”和资源盲点的问题,因此能够高效的利用能源。SPIN的缺点是当产生数据的节点周围没有对其采集数据感兴趣时,将导致数据不能够转发,使得距离该节点更远的节点需要该数据时却没有获得该数据的链路。因此SPIN适用于网络中具有多个sink节点 第二章 无线传感器网络现有路由协议分析 的应用。 3) 定向扩散(Directed Diffusion) DD[25]路由协议是以数据为中心的路由 协议的一个重要里程碑,协议使用属性/值对数据进行命名。协议引入了:兴趣、数据消息、梯度和加强路径的概念。图2-5是定向扩散协议的路由建立过程,路由的建立需要4个步骤: (1) 兴趣的扩散:协议开始时首先基站选择一个命名机制来描述要感知的 任务。而命名机制描述的任务构成了一个兴趣,其通过基站按照一定得数据传输速率扩散到网络的每个节点。每个节点维护一个兴趣缓存,节点收到兴趣扩散时,查找自己兴趣缓存中是否有该兴趣,如果没有则在缓存中创建一个兴趣条目,记录该兴趣的数据传输速率及指向兴趣来源地梯度。然后转发该兴趣消息。 (2) 梯度的建立:当兴趣扩散到目标节点后,一个源节点到基站的临时梯 度就建立了起来。 (3) 数据传播:源节点收到兴趣消息后,采集数据,然后根据其所拥有的 所有梯度信息中选择数据传输速率最大值,并以这个速率把消息传递给相应的邻居节点。节点收到一个数据分组后根据自己缓存中是否有改兴趣的条目,决定是否转发以及以多大的速率转发数据。 (4) 加强路径:源节点先以低速率建立起‘探索’梯度,源节点把采集到 得数据沿‘探索’梯度从多条路径发给基站。基站从这多条路径中选择一条路径取回所需的数据,则此路径成为加强路径,然后源节点以更高的速率沿加强路径传输数据。 a)兴趣的扩散 b)‘探索’梯度的建立 c)传播数据 图2-5 定向扩散协议的路由建立 第二章 无线传感器网络现有路由协议分析 Directed Diffusion 采用周期性兴趣消息扩散,建立数据传输梯度和加强路径来维护网络的拓朴变化,采用数据融合的方法减少数据的传输量,是一种高能源有效性的协议。它的缺点是,不能够很好的应用在周期性传输数据的网络中,初始查询通过兴趣消息在网络中的扩散建立数据传输梯度,能耗过大。 2.3.2 分层路由协议 分层路由协议采用簇的概念对传感器网络进行层次划分,若干个节点构成一个簇,每个簇都有一个簇头。簇内通信是由簇头节点完成的,簇和簇之间的通信可以有各簇的簇头直接通信或者通过网关节点通信。数据采集过程中,簇头节点会把自己簇内所有节点收集的数据进行数据融合处理后转发,以减少冗余数据的传输。分层路由能够有效地较少冗余信息较多的无线传感器网络不必要数据的传输,并有较好的扩展性,适合大规模网络的应用。但其分层过程中需要额外的能量消耗。 典型的分层路由协议有: 1) LEACH(Low Energy Adaptive Clustering Hierarchy) LEACH [26]是第 一个提出数据融合的层次路由协议。协议分为簇的建立阶段和稳定的数据通信阶段两个阶段。为了平衡网络节点的能量消耗,LEACH协议中簇头是按轮随机选取的。在簇的建立阶段,网络中节点产生一个[0,1]的随机数,如果产生的随机数小于阈值T(n),该节点就担任本轮周期的簇头。阈值T(n)可以表示为: 其中,p是簇头在所有节点中所占的百分比,r是当前的轮数,G是在过去1/p轮中未充当过簇头的节点的集合。选定簇头节点后,簇头节点广播一个成为簇头的消息,其余非簇头节点根据接收到的簇头消息的强度大小决定加入的簇。然后簇头节点采用TDMA的方式为簇内的节点分配数据传送的时间片。 第二章 无线传感器网络现有路由协议分析 稳定的数据传输阶段,簇内节点按照自己的TDMA的时间片把数据传送到簇头节点,簇头节点对簇内所有节点采集的数据进行数据融合后直接传送给基站。LEACH协议生成的网络拓扑如图2-6所示。稳定阶段持续一段时间后,网络重新进入簇的建立阶段,使网络中的所有节点都有机会作为簇头节点来平衡网络的能量消耗。LEACH协议的优点有:(1)减少传送到基站的数据量,减少了网络的能量消耗;(2)采用CDMA/TMDA来减少簇内和簇间的冲突;(3)采用经过一定时间后网络重新分簇,使得网络中节点都能够做簇头,平衡了网络能耗。但LEACH也有其缺点:(1)簇头节点直接和基站通信,在远距离通信中节点的能耗和距离的平方甚至四次方成正比的关系,不利于簇头节点的节能;(2)簇头的选举时随机产生的,有可能使得簇头集中产生于某个区域;(3)协议没有考虑节点剩余能量的因素,有可能随机产生的簇头剩余能量较少,导致节点过早死亡。 图2-6 LEACH协议生成网络拓扑图 2) TEEN [27] (Threshold Sensitive Energy Efficient Sensor Network Protocol ) 。 在应用中,TEEN和LEACH的实现机制非常相似,只是前者是响应型的,而后者属于主动型。主动型网络是指节点持续的监测网络,并以恒定的速率传送数据;响应型网络指节点在监测到某些预设的事件时才发送数据,传送的数据具有突发的性质。响应型网络更适用于对特定事件敏感的应用。 第二章 无线传感器网络现有路由协议分析 TEEN中设置了硬、软两个门限值。硬门限是指监测事件不能超越的阈值。软门限是指监测事件的动态变化范围。节点持续的监测网络,当节点首次监测到事件超过节点的硬门限时,把监测值存入内部变量sv(state viable)中,并把采集到的数据发送出去。当节点再次监测到超过自己硬门限的事件后,首先比较最新事件与内部变量sv的差值是否大于软门限,如果大于则更新节点的sv,并发送数据,否则不处理该事件。硬门限根据用户感兴趣的事件设置,软门限根据用户对感兴趣事件的精度设置。 TEEN的优点是由于设置了硬、软两个门限值,数据传送量比主动型网络少,可以通过设置不同的硬、软门限来调整网络的数据传送阈值和数据传送频率取得网络能耗和监测精度之间的平衡,其适用于响应型(Reactive)应用。缺点是不适合应用在需要周期性采集的应用系统中,这是因为如果网络中的节点没有监测到大于硬门限的事件,那么节点就不会与汇聚节点进行通信,用户也就完全得不到网络的任何数据。 3) PEGASIS (Power Eifficient Gathering in Sensor Information Systems) PEGASIS[28]由LEACH发展而来的,采用确定顺序选择簇头的方法来避免LEACH协议频繁选举簇头的能量消耗。协议要求每个节点都知道网络中其他节点的位置,节点通过发送能量递减的测试信号,并监测应答来确定离自己最近的相邻节点。通过这种方式,网络中的所有节点能够了解彼此的位置关系。协议利用贪心算法选择最近的邻居节点作为链上的下一个节点,网络最终形成一个单链结构。链式结构形成后,每一轮通信只选链上的一个节点作为簇头与基站通信。选举簇头的方法很简单,不需要任何的通信消耗:假设网络中有N个节点并采用1~ N的自然数来编号,第j轮选取的簇头是第i个节点,i=j mod N(i为零时,选举节点N为簇头)。协议的实现可以分为两个阶段: (1) 成链阶段 从离基站最远的节点开始,各节点依次选择与其最近的节点作为链上的下一个节点,已经在链上的节点不再继续成链过程。遍历了网络的全部节点后,网络便建立成了一条链式结构。 第二章 无线传感器网络现有路由协议分析 图2-7 PEGASIS成链过程 (2) 数据传输阶段 成链后,每一轮中都通过无通信消耗的选举簇头的方法选取一个节点充当簇头。数据传输从链的两端开始,各节点接收邻居节点数据并和自己采集的数据进行融合后传送给链上的下一个节点。整个网络的数据最终由簇头节点统一融合后发给基站节点。 图2-8 PEGASIS的数据传送 PEGASIS算法的优点是采用确定选举簇头的方法减少了LEACH协议中频繁选举簇头带来的能量消耗,节点选择和自己最近的节点作为数据传输的下一跳节点,能够减小节点的发送功率,减小发送能耗。该算法的缺点是每轮数据传输仅通过一个簇头与基站通信,路由过度依赖于当前的单个簇头节点。随着网络的规模的扩大,网络节点要确定其他节点的位置的通信消耗也大大增大,并且形成的链路会大大的变长,导致数据传输延时过大,不适合实时的数据传输。 第二章 无线传感器网络现有路由协议分析 综上分析,平面路由协议中洪泛协议是最简单的路由协议,不需要维护路由信息,也不需要任何算法,但其能量利用效率很低,SPIN通过引入协商机制来改善洪泛协议的信息内爆现象,与洪泛协议相比能够延长网络的生存周期,但在某些情况下,其不能很好的建立源节点到目的节点的通信链路,定向扩散是一种基于查询和数据的路由协议,该协议采用多路径,健壮性好,但梯度建立的开销很大,数据融合采用时间同步的技术,会带来较大的开销和延时。分层路由协议通过簇头管理簇节点,能够减少网络中的数据传输量。LEACH协议是第一个典型的数据融合分层路由协议,并采用簇头轮询的策略均衡网络的负载,但其选举簇头方法过于简单,每轮采集数据后均重新分簇,分簇能量消耗过大。TEEN协议大大减少了网络中的数据量,但其不适用于主动型网络;PEGASIS有效的降低了LEACH协议选举簇头的能耗,但网络过于依赖一个簇头,在较大规模的应用中,数据延时较高。 2.4 EAHC算法研究 分层路由协议能够有效地减少网络中消息的转发,并具有很好的扩展性,能够很好的应用在大规模的无线传感器网络中。而LEACH协议是一种较好的分层路由协议,其利用簇头轮询的方法来平衡负载的能耗,尽量使网络中的节点能量同时消耗完,在一定程度上延长了网络的生存周期(网络中有一个节点死亡即网络死亡)。但由于其是在每传送一次数据后就重新分一次簇,这虽然有利于节点能耗更加均匀,但会是整个网络生存周期内,网络分簇次数过多,大量的能量消耗在组网上而不是有用的数据采集传输上。因此适当的减少分簇频率,采用采集一定轮数后再重新分簇组网,可以减少组网消耗,在一定程度上可以延长网络的生命期; LEACH协议采用单跳簇的网络拓扑,每个簇头直接与BS通信,而节点发送能耗与距离的指数(2次方以上)成正比。采用多跳簇的结构,即簇头通过多跳的方法与基站通信,能够有效地减少远距离节点的能量消耗,使得网络生存周期有一定得提高。 LEACH协议采用随机选取簇头的策略,没有对选择的簇头进行优化,获得的网络拓扑往往还有很大的优化空间。 第二章 无线传感器网络现有路由协议分析 文献[29]提出了一种基于能量的分级簇(energy-aware hierarchical clustering,EAHC)算法,该算法很好的很好的弥补了LEACH的不足之处。 EAHC算法利用图论中根树及极大权中继集的概念和理论,采用贪婪算法和深度优先算法逐个的搜索整个网络的所有节点,选取权值最大的,通信能耗最小的节点作为树节点,最终形成了以基站为根的簇树结构。为了平衡网络负载,EAHC算法利用定期簇头轮询的策略均衡每个节点的能耗,能够有效的延长网络的生存周期。EAHC算法生成簇树的过程仅需要知道一跳邻居节点的信息,具有较低的消息复杂度。 下面通过一个特例来描述EAHC算法的组网成簇过程:如图2-10是10个节点及一个基站的网络分布图,图(a)中后面括号中的为各个节点假设的第二权值W2(v),假设图中各个节点的剩余能量相同,即W1(v)都相同。算法初始化时,节点v广播自己的id并记录邻居节点。根据邻居节点计算节点v的第二权值W2(v)并和权值W1(v)一起发送给邻居节点,节点把收到的邻居按权值从大到小进行排列储存在自己的未确定邻集节点集合中:unexplored(BS):={7,4,2}、unexplored(0):={8,1,6,9}、unexplored(1):={5,0,8,6,9}、unexplored(2):={BS,7}、unexplored(3):={5}、unexplored(4):={BS,7,9}、unexplored(5):={7,8,1,3}、unexplored(6):={0,1,9}、unexplored(7):={BS,5,4,2}、unexplored(8):={5,0,1}、unexplored(9):={0,4,1,6}。 (a)网络分布 (b)EAHC算法生成的簇树 图2-10 EAHC算法特例描述图 第二章 无线传感器网络现有路由协议分析 首先从BS节点开始,BS节点设置l(BS):= 0(将基站的级数定为0);parent(BS):= Æ。并从其邻居节点中未确定节点集合中选取权值最大的节点7号节点作为下一个探索节点,发送state(BS, 0, Æ,7)消息。 由于state(BS, 0, Æ,7)消息把7号节点作为下一个探索节点,7号节点收到该消息后,设置l(7):=1,parent(7):= BS, unexplored(7):={BS,5,4,2}-{BS}= {5,4,2},并选择5号节点作为下一个探索节点,发送state(7,1,BS,5)。而2,4号节点收到state(BS, 0, Æ,7)消息后,把BS从自己的未确定集合中删除:unexplored(2):={BS,7}-{BS}={7},unexplored(4):={BS,7,9}-{BS}={7,9}。 邻居节点收到state(7,1,BS,5),BS节点把7号加入自己的孩子集:children(BS):={7},5号节点设置l(5):=2,parent(5):= 7, unexplored(5):={7,8,1,3} -{7}={8,1,3}, 选取未确定集合中8号节点作为下一个探索节点,发送state(5,2,7,8)。7号节点把5号节点加入自己的孩子集:children(7):={5}。2,4号节点把7号节点从自己的未确定集合中删除:unexplored(2):={7}-{7}={Æ},unexplored(4):={ 7,9}-{7 }={9}。 在上面的特例中,1号节点会收到state(6,4,8,1)的探索消息,由于1号节点的已确定邻居中5号节点具有更低的等级,1号节点加入5号节点的簇,把探索权移交给6号节点。类似的情况9号节点会加入1号的簇,4号节点加入BS的簇。4号节点确定后,由于邻居节点都以确定,会把搜索权按4->9->6->2->0->8->5的顺序交给5号节点,5号节点把探索权交给3号节点,3号节点邻居节点都以确定,探索权又会返回给5号节点,5号节点的邻居节点也都确定了,会按5->7->BS的顺序移交探索权给BS,BS探索4号节点后,会收到4号返回的探索权,至此BS邻居都已确定,即网络便组成了以BS为根的簇树。 2.5 本章小结 本章介绍了主要介绍了无线传感器网络的路由协议。由于无线传感器网络有其自身的特点,其路由协议有其自身的特点和要求,传统的路由协议并不适用于传感器网络。在这一章里首先 第二章 无线传感器网络现有路由协议分析 总结出了无线传感器网络的路由协议的特点和设计要求,然后对现有的路由协议进行了分析比较。重点通过特例对EAHC算法进行了介绍。 第三章 基于梯度的分级簇算法 第三章 基于梯度的分级簇算法 文献[29]提出了一种基于能量的分级簇(Energy-Aware Hierarchical Clustering,EAHC)算法,但由于EAHC算法采用的贪婪算法和邻域深度优先算法,其建立的网络的分级簇等级较高,延时较高,因此根据定向扩散协议的梯度思想,建立一种网络节点到基站的最小跳数的路由,同时为了兼顾网络中节点的能量平衡消耗,采用选取权值最大的节点作为下一跳节点,以及每次簇头轮询都改变基站的位置的方法,以使能量在更多的节点间平均消耗,延长网络的生存周期。 本章组织如下:第一部分介绍ETBG的模型和问题描述;第二部分介绍和分析ETBG算法的具体内容,并进行算法的仿真;第三部分给出基于ETBG算法的路由方案。 3.1 模型和问题描述 3.1.1 网络模型 可以用一个连通的无向加权图G = (G(V), G(E), G(w) ) 来表示无线传感器网络,其中:G(V)={ v1,…,vn}是一组节点的集合,分别对应每个无线传感器节点;G(E)=是边的集合,每条边表示两个传感器节点vi和vj彼此都在对方的通信范围之内,即两者之间存在一条双向通信链路;G(w)={ w(v1),…w(vi),…,w(vn)},其中w(vi)是节点vi的权值。 假设无线传感器节点随机分布在一个正方形区域内,区域内的节点具有以下性质: 1)节点静止的分布在区域内,只有上线和下线状态 2)无线链路是双向通路,节点a能收到节点b的消息,则节点b也能收到节点a的消息 第三章 基于梯度的分级簇算法 3)节点是同构的,即有相同的初始化能量,数据处理能力和通信能力 4)节点不具有能量续航能力,初始化能量用完,节点死亡(下线) 5)节点具有最大功率范围,且在最大功率范围内,节点功率可调 6)节点主动的,周期的向基站传送数据 7)监测区域边界可达,基站可移动(pda等可移动设备),基站能够在监测区域边界移动,并且基站具有覆盖整个监测区域的能力 3.1.2 能量模型 为了比较和分析不同算法和协议的能量消耗,必需设计一个科学的能量模型来准确的描述无线传感器节点发送接收数据的能耗。本章算法采用文献[30]给出的传感器节点的收发器能量模型,如图3-1所示。图中给出的是传送一个k-bit分组(packet)接收器和发射器的能耗模型。其中节点每发送k-bit分组数据的能量消耗分为两部分:一部分是信号发射电路所消耗的能量,一部分是信号放大电路所消耗的能量,写成公式为: 节点每接收k-bit分组数据消耗的能量为 图3-1能量模型 其中,和分别是发送电路和接收电路接收k-bit的能量消耗,模型中接收电路能量消耗和发送电路能量消耗相同都为,这里 第三章 基于梯度的分级簇算法 取=50nj/bit。d是信号传输距离,n为常数,其数值是由选择的无线信道决定的,是信号放大器的放大倍数。在自由空间衰减信道模型n=2,,而在多径衰减信道模型中n=4,。仿真中选择那个模型由两个通信节点的距离决定。临界距离为,如果通信距离小于等于,则选用自由空间衰减信道模型,如果通信距离大于临界距离,则选用多径衰减信道模型。本文中取k=128bit,di=87.7m。 3.1.3 网络能耗分布 (a)单跳网络能量消耗分布图 (b)多跳网络能量消耗分布图 图3-2 网络能耗分布图 图3-2中(a)和(b)分别描述的是在无线传感器网络中不同的路由思想导致的不同的网络能量消耗分布。其中图中的圆圈代表存活节点,实心点代表死亡节点(能量消耗完)。在单跳网络中,由于所有节点直接和基站通信,距离基站远的节点发送相同的数据所消耗的能量要远大于基站附近节点发送相同数据消耗的能量,因此在单跳网络中,距离基站远的节点要比基站附近的节点能量消耗的更快(更早死亡),即图3-2(a)中所示的现象。而在多跳网络中,远离基站的节点的数据通过多跳方式到达基站,因此在基站附近的节点要转发来自距离基站远处节点传送的数据,传送的数据量过大,导致基站附近节点的过早死亡, 第三章 基于梯度的分级簇算法 即图3-2(b)中所示的现象。因此,对于多跳网络,为了有效的延长网络的生存期,必须比较均匀消耗基站附近的节点的能量消耗。 3.2 算法描述 3.2.1 定义 定义1:同梯度等级集合Ui:对于一个网络G,有 Ui={v|v∈G(V),且node(v).level≡i} i为该集合的梯度等级。 定义2:梯度等级集合U:对于网络中的某个节点, U={Uk | k为该节点收到的所有梯度等级} 对U和Ui分别定义运算: Min(U)=Uj,j为集合U中元素集合的最小梯度等级(j值最小) Max(Ui)=m,m为集合Ui中权值最大的节点的id Level(Ui)=i,i为集合Ui的梯度等级 3.2.2 符号声明 ● struct Node { char level;char id;char;float w1;float w2;char par;} ――简化节点:其中level:节点的梯度等级;id:节点的id值;w1:节点的第一权值(剩余能量);w2:节点的第二权值(节点邻居节点个数的倒数);par:节点的父亲节点(节点到基站路由的下一跳节点) ●Gradient(R,level)——建立基本梯度等级消息(广播消息):R当前BS的通信半径,level:当前要建立的梯度等级。 ●Neighbor (level,w1,w2,id)——邻居节点交换参数消息(一跳广播消息),参数含义同简化节点中参数含义。 ●Add_cluster(level,cluster_id,id)——加入簇消息(一跳广播消息):cluster_id为要加入簇头的id ,id为发送消息的id值 ●Change_level(level,id)——节点梯度等级改变消息(一跳广播消息):level为节点改变梯度等级后的梯度等级,id为发送消息的id值 第三章 基于梯度的分级簇算法 3.2.3 算法 假设网络中节点的通信半径为R,监测区域距离基站的最大距离为D。初始化时,基站节点node(BS).level=0,node(BS).w2=0;其他节点node(i).level =L(i不等于BS,L足够大);node(i).w1=init_energy(初始化能量)。 第一次组网时,全网发送一跳广播信息,节点获得邻居节点的个数及id,并计算自己的第二权值w2 第一阶段基本梯度的建立: 1) 基站节点(BS)依次以nR(n=1,…,[D/R],其中[D/R]为整数,且D/R≤ [D/R]node(y).w1 2)node(x).w1==node(y).w1并且node(x).w2>node(y).w2 3)node(x).w1==node(y).w1同时node(x).w2==node(y).w2,xaccess(offset_); } }; struct hdr_eamct_mess{ u_int8_t mess_type; //区分同一类型的不同功能数据包 int id; //发送节点id值 double energy; //发送节点能量 double x; //发送节点x坐标 double y; //发送节点y坐标 x y坐标仅用作能量计算 inline int size(){ //该分组的大小 int sz=0; sz=17*sizeof(u_int8_t); return sz; } }; …… //添加更多的分组格式 union hdr_all_eamct{ hdr_eamct eamct_t; //定义操作该数据包的一些函数 hdr_eamct_mess node_mess; // 节点获得邻居节点的交互消息 hdr_send_ch send_ch; //簇头声明消息 第四章 EAMCT-G算法在NS2上的实现 hdr_send_mem send_mem; //加入簇消息 hdr_invite invite; //邀请加入簇树消息 hdr_child child; hdr_hello hello; //hello消息用于更新邻节点 hdr_has has; hdr_innet innet; //在簇树上消息 hdr_restart restart; //重新组网消息 hdr_miss miss; //发现某节点下线消息 hdr_notinnet notinnet; //不在簇树上消息 }; //创建一个共同体,使得发自同一协议的不同功能数据包具有一个共同的分组类型 为了在otcl中能够根据使用的协议配置相应的分组,以节省内存空间,要在otcl相应的文件中实现该功能,即在ns-packet.tcl中添加: foreach prot { …… EAMCT_G …… }{ add-packet-header $prot } add-packet-header方法会把允许出现在数据包中的分组值1,即激活该分组,最终由otcl类PacketHeaderManager的过程allochdr根据需要激活的分组计算数据包的长度,并传递给c++中的绑定变量Packet::hdrlen_。 要把c++中的分组和otcl接口绑定起来,需要定义一个静态类来实现(在EAMCT_G.cc中添加): static class EAMCT_GHeaderClass : public PacketHeaderClass { public: EAMCT_GHeaderClass() :PacketHeaderClass("PacketHeader/EAMCT_G", sizeof(hdr_all_eamct)) { bind_offset(&hdr_eamct::offset_); } } class_EAMCT_G_hdr; 至此协议与NS2紧密相关的部分已经完成,剩下的是根据EAMCT-G算法的具体过程编写相应的程序,建立路由表,网络的维护更新等,这部分程序和NS2体系联系不紧密,不在详细叙述。在编写过程中主要注意recv函数的实现,其主要完成与路由代理 相联系各层的数据包的处理;command函数,主要完成otcl脚本中未知命令的c++实现。 第四章 EAMCT-G算法在NS2上的实现 3)协议trace文件的跟踪 为了能够对算过程进行跟踪,需要在trace文件中显示出算法接收发送分组,这样便于查看算法在实际中出现的问题,能够更快的对算法进行分析并加以修正。首先要定义算法的分组类型及算法分组在trace文件中显示的名字,packet.h中定义的p_info类是一个包含所有分组类型的一个枚举类,用于标识分组的类型及名字,于是只要在p_info类中添加相应的类型及分组名称即可: enum packet_t { …… PT_EAMCT, PT_NTYPE // This MUST be the LAST one }; class p_info { public: p_info() { …… name_[PT_EAMCT]="EAMCT_G"; ……. } } 对于分组的记录是有cmu-trace.h中的CMUTrace类的函数实现的,需要在CMUTrace中添加一个处理EAMCT-G协议分组的函数: class CMUTrace : public Trace { …… void format_eamct(Packet *p, int offset); …… } 并在cmu-trace.cc中format函数中添加接收到PT_EAMCT类型的数据包后调用format_eamct函数: void CMUTrace::format(Packet* p, const char *why) { …… switch(ch->ptype()) { …… case PT_EAMCT: format_eamct(p, offset); break; 第四章 EAMCT-G算法在NS2上的实现 …… } } 同时实现format_eamct函数: void CMUTrace::format_eamct(Packet *p, int offset) { struct hdr_eamct *eamct = HDR_EAMCT(p); char op = (char) type_; switch (eamct->eamct_type) { case MESS_TYPE: op = 'M';break; case SEND_CH: op = 'C'; break; case SEND_MEM: op ='E';break; case INVITE: op = 'I';break; case CHILD: op = 'H';break; case ISINNET: op='N';break; case HAS: op='A';break; case HELLO: op='O';break; case MISS: op='S';break; case RESTART: op='R';break; default: break; } sprintf(pt_->buffer() + offset, "------- [%c] ",op ); return; } 在otcl仿真脚本中打开路由层的trace记录,在生成的trace中便会记录各个节点发送的组网等分组消息。 4.2.3 仿真分析 原EAMCT_G算法簇头轮询是网络节点采集一定轮数后才进行,这要求基站记录每个节点发送的数据轮数,且在某些情况下,如网络节点死亡,使得个别节点采集的数据轮数始终达不到簇头轮询的数目,不利于网络节点的能量平衡,故在NS2上实现时采用网络采集一定时间的数据后,便重新组网。原算法中网络维护更新没有具体的提到网络节点的上下线发现方法,在NS2上实现时,采用和aodv协议相同的方法即:定期发送hello消息来维护邻居节点,节点设置一个定时器,定时时间为两个hello消息的时间,当定时器超时后,检查邻居节点集合,删除未发送hello消息的节点,然后重置定时器。 第四章 EAMCT-G算法在NS2上的实现 模拟脚本的mac层采用802.11协议;发射功率(Pt_)为0.001W(此发射功率并不用来计算节点的能量消耗,仅配合RXThresh_及CSThresh_计算节点的通信距离及载波的覆盖范围),数据正确接收的功率门限(RXThresh_)为3.652x10-10W,载波功率门限(CSThresh_:能监听到载波,但不能正确接收分组)为1.559x11-10W,载波频率为914MHZ;节点的初始化能量为4J,接收功率(rxPower)为0.1W,发射功率(txPower)为0.2W;节点分布区域为100mx100m,节点个数为20(包含基站);应用层采用横速率数据流(cbr)来模拟节点的数据采集,节点每1s发送一个cbr数据包,数据包大小为128byte,簇头轮询时间为110s。 图4-3 网络的平均延时 图4-4 网络吞吐量 图4-3是对trace文件中的数据进行处理后得到的网络节点的平均延时,图中共有3处延时较大的时间点,分别在110s,220s,240s左右,延时大概为4s,110s和220s附近延时较高是由于簇头轮询时间到了,没有到达基站的有效路由,数据在等待组网完成后才能发送,其延时大概为组网时间4s,而在240s附近延时高的原因是网络中有簇头节点死亡导致网络重新组网,延时同样大致为组网的时间长度4s。 第四章 EAMCT-G算法在NS2上的实现 图4-4是对EAMCT-G算法生成的trace文件中数据处理后得到的网络的平均吞吐量(纵坐标单位为kbit/s,横坐标单位为s),在簇头轮询的110s和220s附近网络的吞吐量基本为零,在网络簇树生成后,组网前缓存的数据和当前节点应发送的cbr数据一起发送出去,会导致网络重新组网成功后,网络吞吐量的猛然增大,即图示在110s和220s附近的网络吞吐量的一个振荡。而在240s附近网络吞吐量的振荡最大值要小于前两个的最大值,这是由于网络中已经有节点死亡,网络吞吐量的最大值也随之下降。 (a)20个节点组网图 (b)14号节点下线 (c)14和4号节点下线 图4-5 网关节点下线维护更新 第四章 EAMCT-G算法在NS2上的实现 由于非网关簇节点下线,簇头仅删除该节点即可,而簇头节点下线要重新组网,所以上述两种情况都比较简单,而网关节点的下线则可以通过维护更新算法重新选择其他节点充当网关。图4-5是EAMCT-G算法的一个网关维护更新示例,数据由NS2生成,然后用matlab作图:图(a)是网络组成的簇树图,图(b)和图(c)分别是在仿真脚本中设置14号节点,14号节点和4号节点在30s时节点能量为零的维护更新图。图4-3,图4-4和图4-5也验证了算法在NS2上的成功实现。 4.3 本章小结 本章通过EAMCT-G算法在NS2上的实现介绍了在NS2中添加新协议的主要过程。并且通过EAMCT-G在NS2上的实现,看到EAMCT-G算法在实际应用中对网络的时间同步有较严格的要求,这样才能使得簇头轮询重新组网的第一阶段,节点能在同一时间发送组网消息,有效地发现所有未死亡邻居发送的组网消息。 从模拟算法生成的trace文件中发现,mac层采用802.11的情况下使用NS2自带的能量来计算网络的能量消耗,发现接收能量消耗要远远大于发送能量消耗。这是由于802.11协议中没有休眠机制,即使数据包不是发送给该节点的也会被该节点接收到,但不向上层提交该数据包,从而接收模式消耗了更多的能量。这种模型是基于实际网络的模型。但其和目前网络层能量路由仿真研究的一些假设(具有一个理想的mac层)有所不同,即节点仅计算发送自己的数据包的能耗,而邻居中有节点给其他节点发送数据包则不计算该数据包在本节点上的接收能耗,这种假设,简单,不依赖与其他层,而且能够更加清楚地比较不同路由协议的能量有效性。因此,NS2在仿真能量有效路由方面及目前能量有效路由研究的能量模型还有待进一步研究。 第五章 总结和展望 第五章 总结和展望 5.1 全文总结 无线传感器网络是一种全新的网络,其起源于军用,发展到现在已经在多个领域得到广泛应用,如智能家居、智能交通、工业监测等。由于其与现有网络有较大差别,现有网络的各种协议都不能很好的在无线传感器网络中应用。因此,无线传感器网络还有许多问题要解决。本文主要研究了无线传感器网络的基于梯度的分级簇路由及分级簇路由在NS2上的实现及仿真。 第一章介绍了无线传感器网络的网络体系结构、网络特点及其应用,描述了目前无线传感器网络的研究热点及关键技术,最后给出本论文的选题背景和研究的内容。 第二章总结了无线传感器网络路由层的特点和设计要求,根据路由层的分类,介绍了各种类型的典型路由协议,并对其优缺点进行分析。最后重点对EAHC算法进行了介绍及分析,并针对其不足之处,提出了一种改进算法—基于梯度的分级簇算法。 第三章提出了一种基于梯度的分级簇(ETBG)算法,该算法借鉴了定向扩散协议中梯度的思想,对EAHC算法中簇树的建立过程进行改进,使得网络节点到基站的最大平均跳数与EAHC算法生成的网络跳数相比有明显的减少,即降低了分级簇树的高度,从而降低了网络分组的延时;仍采用EAHC算法中选取最大权值的节点作为父亲节点的方法及簇头轮询的思想,并利用基站移动进一步平衡网络的能量消耗,延长了网络的生存周期;在本章最后给出了该算法的路由方案,网络中只有簇头节点需维护路由表,从而使整个网络的路由维护开销大大减少。 第四章通过一种具体的算法(EAMCT-G)在NS2上的实现介绍了在NS2中添加新协议的具体过程,并对EAMCT-G算法模拟后的trace文件进行了分析,验证了算法在NS2中实现的正确性。通过算法在NS2上了实现,描述算法在实际环境中应用对网络的要求及NS2在仿真 第五章 总结和展望 分析不同无线传感器网络路由能量有效性方面的不足。 5.2 研究展望 由于研究时间和力量有限,还有下面的工作有待进一步完善: 1) 对基于梯度的分级簇算法的网络维护更新方法需要进一步研究。 2) 基于梯度的分级簇算法虽然能够有效地减少分级簇树的等级,但在某些特定的网络分布下,算法的消息复杂度较高,如何在所有网络分布都能够以较低的消息复杂度生成分级簇树还需仔细考虑。 3) 在能量有效路由的仿真中,仿真模型与现实情况有着较大的偏差,建立一个简单有效、接近于现实的统一仿真模型,有利于协议之间的性能比较,这方面还需要更多的努力。 参考文献 参考文献 [1] F. Akyildiz, W.Su, Y.Sankarasubramaniam et al., Wireless sensor networks: a survey, Computer Networks, 2002, 38:393-422. [2] 盛敏,田野,李建东。无线传感器网络与自组织网络的研究现状。中兴通讯技术,2005(4),5-10. [3] 于海斌,曾鹏,王忠锋等, 分布式无线传感器网络通信协议研究, 通信学报,2004,25 (10):102-110. [4] 林瑞仲, 面向目标跟踪的无线传感器网络研究,浙江大学博士学位论文,2005年6月. [5] 崔莉,鞠海玲,苗勇等,无线传感器网络研究进展, 计算机研究与发展, 2005,42(1):163-174. [6] 孙利民,李建中,陈渝等。无线传感器网络。北京:清华大学出版社,2005. [7] 宋文 王兵 周应宾等 无线传感器网络技术与应用。北京:电子工业出版社。2007 [8] Mohammad Ilyas and Imad Mahgoub.Handbook of Sensor Networks:Compact Wireless and Wired Sensing Systems.Boca Raton London New York Washington,D.C.,CRC Press LLC,2005 [9] 李善仓 张克旺等。无线传感器网络原理与应用。北京:机械工业出版社。2008 [10] E.Shih, S.Cho, N.Ickes et al, Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks, Proceedings of the ACM MobiCom 2001. 272-286. [11] G.Pei and C.Chien, Low power TDMA in Large Wireless Sensor Networks, Military Communications Conference, Communications for Network-Centric Operations: Creating the Information Force, 2001, 1: 28-31. 参考文献 [12] A.Woo, D.Culler, A transmission control scheme for media access in sensor networks, Proceedings of the ACM MobiCom 2001, 221-235. [13] 王雪.无线传感器网络测量系统。北京:机械工业出版社,2008. [14] S.Capkun, J.P.Hubaux, and Levente Buttyan, Mobility Helps Security in Ad Hoc Networks, Proceedings of MobiHOC, 2003, 46-56. [15] Haowen chan, Adrian Perrig and Dawn Song, Random key predistribution Schemes for Sensor Networks, 2003 IEEE Symposium on Security and Privacy, Berkeley, CA, 2003, 197-205. [16] J.Elson, Time synchronization services for wireless sensor networks, Proceedings of the 15th International Parallel & Distributed Processing Symposium. 2001, 1965-1970. [17] J.Elson, D.Estrin, Wireless Sensor Networks: A New Regime for Time Synchronization. [18] Hairong Qi, Phani Teja Kuruganti, Yingyue Xu.The development of localized algorithms in wireless sensor network, Sensors Journal, 2002, 2(7): 286-293. [19] L.Girod, V.Bychkovskiy, J.Elson, D.Estrin, Locating tiny sensors in time and space: A case study, Proceedings of the International Conference on Computer Design. 2002, 195-204. [20] Estrin Deborah,Govindan Ramesh,Heidemann John.The Impact of Data Aggregation in Wireless Sensor Networks.Proceedings of Intemational Conference on Distributed Computing Systems,2002:457-458P [21] Ganesan Deepak,Govindan Ramesh,Shenker Scott,et al..Highly Resilient Energy Rfficient Multipath Routing in Wireless Sensor Networks.Proceedings of the 2001 ACM International Symposium on Mobile Ad Hoc Networking and Computing:MobiHoc 2001:251-254P [22] Bukerche Azzedine,Cheng Xiuzhen,Linus Joseph.Modeling Data-Centric Routing in Wireless Sensor Networks.Proceedings of the ACM International Workshop on Modeling,Analysis and Simulation of Wirelessand Mobile Systems,MSWIM 2003:42-49P 参考文献 [23] S. Hedetniemi and A. Liestman. A survey of gossiping and broadcasting in communication networks. Networks, Vol. 18, No. 4, pp.319-349. 1988. [24] J. Kulik, W. R. Heinzelman, and H. Balakrishnan, Negotiation-based protocols for disseminating information in wireless sensor networks, ACM Wireless Networks, vol. 8, no. 2-3, pp. 169–185, 2002. [25] Chalermek Intanagonwiwat, Ramesh Govinda, Deborah Estrin. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. in the Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking. 2000. [26] Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocols for wireless sensor networks[C]//IEEE proceedings of the Hawaii Intermational Conference System Sciences’00.Hawaii,U.S.A:[s.n.],2000:3005-3014 [27] Manjeshwar A, Agrawal D.P, TEEN: a routing protocol for enhanced efficiency in wireless sensor networks, International Proceedings of 15th Parallel and Distributed Processing Symposium, Pages 2009 -2015, 2001. [28] Lindsey S, Raghavendra C.S, PEGASIS: Power-Efficient Gathering in Sensor Information Systems. International Conference on Communications, 2001. [29] 阎新芳,孙雨耕,赵承利,无线传感器网络中基于能量的分级簇算法[J], 天津大学学报,2005,38(12): 1106-1110 [30] A. Wang, W. B. Heinzelmen, A. Sinha and A. P. Chanderkasan, Energy-scalable protocols for battery- operated microsensor networks, Journal of VLSI Signal Processing, 2001, 29: 223-237. [31] 徐雷鸣,庞博,赵耀。NS与网络模拟。北京:人民邮电出版社。 2003。 [32] 郑相全等。无线自组网技术使用教程。北京:清华大学出版社。2004 [33] NS MANUAL http://www.isi.edu/nsnam/ns/doc/node173.html [34] Na An, Xinfang Yan, Yufang Zhu, Lei Duan, A Virtual Backbone Network Algorithm Based on the Multilevel Cluster Tree with Gateway for Wireless Sensor Networks. In: Proceedings of CCWMSN'2007[C]. Shanghai,China: 2007 The IET International Communication Conference on Wireless 参考文献 Mobile and Sensor Networks, 2007. P: 462-465 发表论文与科研情况 发表论文与科研情况 [1] Na An, Xinfang Yan, Yufang Zhu, Lei Duan, A Virtual Backbone Network Algorithm Based on the Multilevel Cluster Tree with Gateway for Wireless Sensor Networks. In: Proceedings of CCWMSN'2007[C]. Shanghai,China: 2007 The IET International Communication Conference on Wireless Mobile and Sensor Networks, 2007. P: 462-465(EI收录). 参与的科研项目 无线Ad hoc网络分层路由问题研究(72300410430)——河南省科技厅基础与前沿技术研究基金项目. 致谢 致 谢 在攻读硕士研究生期间,我得到了师长、同学、朋友和家人的支持。在他们的帮助下,我才得以顺利完成学业。在此,我向他们表示最诚挚的感谢! 首先要感谢我的导师阎新芳教授!在三年的学习、生活和课题研究中,阎老师给了我许多的指导和帮助,感谢阎老师在课题研究过程中对我的信任、支持和指导,能够使我在一次次的失败中重新找到研究课题的动力,能够顺利的完成课题,也使我在生活中遇到挫折能够更加坚强。同时感谢阎老师在小论文和大论文的写作上提出的意见和建议,使我的论文写作水平和表达能力都有了很大的提高。也要感谢李良老师在实际工程项目上对我的指导和帮助,能够在三年的学习中接触到实际项目的机会,锻炼了我的动手能力。再次向阎新芳教授和李良老师表示深深地感谢。 感谢我的师弟师姐们:安娜、朱玉芳、张永琦、王志龙、李锡刚,有了他们的帮助,我的课题和论文才能顺利进行。 感谢我的朋友:王彦杰、李同鑫、刘军涛、王向前、翟卫松、王科、李晓等,在三年的学习和生活中大家互相帮助和关心,度过了一段美好的时光。 最后对我的父母和家人表示深深地感谢,在我三年的求学中默默地支持和理解,为我分忧解难,为我无私的奉献。 所有的感激之情不是寥寥几字所能表达的,在此衷心祝福三年来所有帮助、鼓励、支持和指导我的人们健康、幸福。

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档