无线传感器网络的路由协议.ppt

《无线传感器网络的路由协议.ppt》由会员分享，可在线阅读，更多相关《无线传感器网络的路由协议.ppt（43页珍藏版）》请在三一文库上搜索。

1、,WSN中的路由协议和拓扑控制,主要内容,1.WSN的体系结构 2.路由协议的定义 3.WSN的特点及对路由设计的影响 4.路由协议的关键问题分析 5.路由协议的分类 6.典型路由协议及其比较 7.拓扑控制,WSN的体系结构,Node有四个基本组件构成 sensing unit processing unit Transceiver unit power unit 可能有的取决于应用程序需要的组件 location finding system：许多路由技术和传感任务需要精确获悉节点位置 power generator：在特定状况下需要提供长时间的电源支持 Mobilizer：需要移动节点到另

2、一个地方执行指定的任务,The sensor networks protocol stack,hysical layer 实现简单、强壮的数据调制，发送、接收 MAC层 考虑节点的通信环境噪声和节点的移动，且需要降低 能量消耗，最小化和邻居节点的广播冲突.负责数据成 帧，帧检测，媒体访问控制和差错控制 network layer 路由生成和路由选择 transport layer 数据流传输控制，是保证通信服务质量的重要部分 application layer 根据传感任务的不同，可以建立不同的application power management plane 管理传感器节点如何使用能源，各

3、个协议层都要考虑 节省 mobility management plane 监测并注册传感器节点的移动，维护到汇聚节点的路 由，使node能动态跟踪其邻居节点的位置 task management plane 在一个给定的区域内平衡和调度监测任务,路由协议是WSN的关键技术之一，它负责将数据分组从源 节点通过网络转发到目的节点 主要包括两个方面的功能： 寻找源节点和目的节点的优化路径 将数据分组沿着优化路径正确转发,路由协议,与有线网络和蜂窝式无线网络不同，WSN中没有基础设施和 全网统一的控制中心，在这种无中心的环境下，路由可以看成 分布式地获取网络拓扑信息，以一定准则计算路径并对路径 进行

4、维护的过程。,网络特点是路由设计的主要依据，对网络特点的分析是进 行协议设计的前提,WSN的特点及对路由设计的影响,无线传感网络中，网络业务的最大特点是具有明显的方向 性。为了实现信息采集的目的，WSN的网络业务大都发生在 数据汇聚节点（sink）和普通的传感器节点之间，包括sink节 点到传感器节点的下行业务（如查询指令下达）和传感器节 点到sink的上行业务（如采集信息的回传） 传感器节点之间的横向业务所占比例较小，主要是网络的 控制信息和网内信息处理所需要的信息。,从对路由协议设计影响的角度，归纳WSN的特点,1.形式多样的信息报告模式 WSN中信息报告模式分四类： a.事件触发：节点采

5、集信息后判断，若超过一定的阈值，则认 为发生了某种事件，需要立即上报，如用于预警的WSN b.周期的：节点定期把采集到的信息报告给sink。如野生动植 物和环境监测WSN c.基于查询：node不主动向sink上报采集到的信息，而是等待 用户查询，根据用户需要反馈信息。 d.混合模式：前三种的综合。如智能交通的WSN,2.多对一和一对多为主的业务模式 WSN的主要业务是传感器节点把采集到的信息传给sink和sink向WSN 下达查询命令，这是典型的多对一和一对多的模式。 为了支持这种通信模式，WSN中很多路由协议建立具有树状结构的 路由,此外还有“地域多播（geocast）”的业务模式 WSN

6、中，用户可能对一个地理信息区域内的信息感兴趣，因此需要把查询 和命令发送到该区域内的所有节点。针对这种模式设计了以下一些路由协 议： LBM：基于位置的多播协议 Voronoi diagram and convex hull based geocasting and routing：基 于Voronoi图和基于凸包的地域多播协议 GEAR: geographical and energy aware routing,3.数据为中心的设计理念 把WSN看成是一个大型的数据库，用户关心的是从这里得到什么信息， 而不关心数据库中的哪个元素（node）提供了该信息,该理念对网络层的一个重要影响是节点的

7、地址分配 一般情况下没必要为每个node分配全局唯一地址，node描述信息产 生时间，地点和内容即可，统一编址，对大规模WSN开销过大,该理念还影响分组转发的过程 WSN中，原始数据可能存在一定的冗余，在满足信息采集的要求前 提下，可以在数据转发过程中对其进行修改，甚至把多个分组合并成一个 分组，从而降低能耗,4.动态变化的网络拓扑,大部分的WSN中节点并不移动，造成网络拓扑变化的主要原因是节点的失效和 存在不可靠性、非对称链路。为了节能和延长网络寿命，需要对网络进行休眠调度， 会在一定程度上增加网络拓扑的动态性。在有些WSN中为了弥补节点失效造成的 性能损失，进行再布设（re-deploym

8、ent），也会使网络拓扑发生变化。 有些WSN中的节点是可移动的，如医疗监测WSN，候鸟迁徙WSN，网络拓扑 变化比较快,5.能量受限、结构简单的节 点 Node大都由电池供电，电池 体积小，能量有限且难以更 换，许多场合需要WSN连续 工作数年甚至更长。 Node结构简单，存储、处理、通信 能力低，单个节点可靠性差。要求协 议尽可能简单，具有容错性,1.能量有效性 提高能量有效性是WSN从硬件设计到软件开发都必须考虑的 问题。 从路由协议设计的角度有两种思路提高能量有效性： a.节能：寻找节能路由，减少路由建立和维护的控制开销，提 高路由可靠性 b.能耗均衡：从空间上调度能量资源，使网络中节

9、点能量均衡 消耗,路由协议的关键问题分析,2.可扩展性 可扩展性是指网络的性能不随着网络中节点的数量增加而有 明显的下降,3.数据传输可靠性 数据传输的可靠性直接关系到WSN是否能给用户提供准确、全 面和可靠的信息，而WSN中节点无线通信能力弱，应用环境复 杂，实际的链路质量比较低。如何保证数据传输的可靠性是 WSN路由设计中的一个关键问题 影响WSN数据传输可靠性原因： a.无线信道上的碰撞导致分组无法正确接收 b.节点故障使路由不可用，导致分组丢失 c.链路不可靠，导致分组传输出错或丢失,几十种WSN路由协议，未统一分类标准 一种分类方法（5类）：,路由协议的分类,1.基于聚簇的路由协议

10、LEACH, PEGASIS, TEEN等,2.基于地理位置的路由协议 GEM,MAP, LCR等,3.以数据为中心的路由协议 DD，Rumor-routing，TTDD，支持查询的近似路由算法等,4.能量感知路由协议 Energy aware routing，GEAR,等,5.容错路由协议 建立多条路径，重复传输数据包，基于编码的机会路由协议（MORE）等,泛洪路由(Flooding) 扩散法(Flooding)是一种传统的网络 路由协议，不需要知道网络拓扑结构 和使用任何路由算法,典型的路由协议分析,协议内容： 一节点S希望发送一块数据给节点D，节点S首先通过网络将数据副本传送 给它的每一

11、个邻居节点，每一个邻居节点又将其传输给各自的每一个邻居 节点，除了刚刚给它们发送数据副本的节点S外。如此继续下去，直到将 数据传输到目标节点D为止或者为该数据所设定的生命期限（在传感器网 络里面通常定义为最大跳数）变为零为止或者所有节点拥有此数据副本 为止。,洪泛路由（Flooding）的优点： 实现简单 不需要为保持网络拓扑信息和实现复杂的路由发现算法而消 耗计算资源 适用于健壮性要求高的场合。,洪泛路由（Flooding）的不足： 存在信息爆炸(Implosion)问题，即出现一个节点可能得到 一个数据多个副本的现象 盲目使用资源，即扩散法不考虑各节点能量可用状况因而 无法作出相应的自适应

12、路由选择。,洪泛路由（Flooding）的应用情况： 网络资源过于浪费，实际很少直接采用 具有极好的健壮性，可用于军事应用 作为衡量标准评价其它路由算法,SPIN协议（sensor protocol for information via negotiation） SPIN是最早的以数据为中心的自适应路由协议，通过协商机 制来解决洪泛算法中的“内爆”和“重叠”问题，节省了能量的消耗 a.为了避免出现扩散法的信息爆炸问题和部分重叠现象，传感 器节点在传送数据之前彼此进行协商，协商制度可确保传输有 用数据 b.节点间通过发送元数据(即描述传感器节点采集的数据属性的 数据，meta-data)，而不

13、是采集的整个数据进行协商。由于元 数据大小小于采集的数据，所以，传输元数据消耗的能量相对 较少。为避免盲目使用资源，所有传感器节点必须监控各自的 能量变化情况。,SPIN-PP采用点到点的通信模式，并假定两节点间的通信不受其他节点的干扰， 分组不会丢失，功率没有任何限制,1.在发送一个DATA数据包之前，一个传感器节点首先对向邻居节点广播ADV数据包； 2.如果一个邻居节点在收到ADV后有意愿接收该DATA数据包，那么它向该节点发送 一个REQ数据包，接着节点向该邻居节点发送DATA数据包。 3.类似地进行下去，DATA数据包可被传输到远方汇节点或基站。,SPIN协议的优点： 1.ADV消息减

14、轻了内爆问题; 2.节点根据自身资源和应用信息决定是否进行ADV通告，避免 了资源利用盲目问题，有效地节约了能量。,SPIN协议的不足： 在传输新数据的过程中，直接向邻居节点广播ADV数据包，而 没有考虑其所有邻居节点由于自身能量的原因，不愿承担起 转发新数据的功能，则新数据无法传输，将会出现“数据盲点”， 进而影响整个网络信息的收集,MTE(Minimum Transmission Energy)路由协议： 在MTE协议中，节点选择离自己 平面距离最近的节点进行路由中 转 当且仅当如下公式满足时，节点A将会选择 B转发自己的数据到节点C,右图为MTE协议示意图 MTE路由协议的优点： 简单、

15、开销小，每个节点只需要找到 通往Sink节点的下一跳节点，然后把 数据发给它 MTE路由协议的不足： 靠近Sink节点的传感器节点会一直承担路由器的 角色，节点之间负载不平衡，靠近Sink节点的传 感器节点可能很快就耗尽自己的能源而死亡，缩 短整个网络的生命周期,LEACH（Low-Energy Adaptive Clustering Hierarchy）路由协议： LEACH是一种基于聚类路由协议，在WSN路由协议占有重要地位，其 他基于聚类的路由协议如TEEN、APTEEN、PEGASIS等大都由LEACH发展而来,LEACH路由协议的核心思想： 1.LEACH协议分为两个阶段操作，即类准

16、备阶段(set-up phase)和就绪阶段(ready phase)。为了使能耗最小化，就绪阶段持续的时间比类准备阶段长。类准备阶段 和就绪阶段所持续的时间总和称为一轮(round) 2.在类准备阶段，LEACH协议随机选择一个传感器节点作为类头节点(cluster head node)，随机性确保类头与基站之间数据传输的高能耗成本均匀地分摊到所有传感 器节点。 3.具体的选择办法是：一个传感器节点随机选择 0和1之间的一个值，如果选定的值小于某一个 阈值T(n)，那么这个节点成为类头节点。 T(n)值按右边公式计算：,N：网络中传感器节点的总数； p：一轮中网络的类头节点数； r：己完成的

17、轮数； Gr：在剩余的N/k-r个回合中未成为类头节点的传感器节点组成的集合；,4.在类头节点选定后，该类头节点对网络中所有节点进行广播，广播数据包含有该节 点成为类头节点的信息。一旦传感器节点收到广播数据包，根据接收到的各个类头 节点广播信号强度，该节点选择信号强度最大的类头节点加入，向其发送成为其成 员的数据包。类形成后，类头节点采用TDMA策略分配通道使用权给类内节点。 5.一旦处于就绪阶段，类头节点开始接收类内各节点采集的数据，然后采用数据融合 和数据压缩等技术进行汇聚，将整合后的数据传输给Sink节点。在就绪阶段持续了 一段时间后，网络又进入了另一次的类准备阶段。,LEACH路由 协

18、议模型,LEACH缺点,1、簇头选举随机性很强，可能会出现簇头集中在某一个区域的现象，造成簇头分布不均匀。,2、信息的融合和传输都是通过簇头节点来进行，造成了簇头节点能量消耗过快的问题； 3、发射机和接收机必须严格遵守时隙的要求，避免在时间上互相重叠，然而，维持时间同步又增加了一些额外的信令通信量。节点的时间表可能会需要较大的存储器。 4、LEACH要求节点之间和节点与Sink点之间都能进行直接通信，网络的扩展性差，对于大规模网络而言，节点直接进行通信需要消耗大量的能量。并且采用单跳路由方式，增加了交换数据的能量。,TTDD（two-tier data dissemination ）路由协议：

19、 TTDD协议是一个层次路由协议,主要是解决网络中存在多sink点及sink点 移动问题,TTDD协议的基本原理： 1.当多个节点探测到事件发生时,选择一个节点作为发送数据的源节点,源 节点以自身作为格状网(grid)的一个交叉点构造一个格状网. 2.其过程是:源节点先计算出相邻交叉点位置,利用贪心算法请求最接近该 位置的节点成为新交叉点； 3.新交叉点继续该过程直至请求过期或到达网络边缘. 4.交叉点保存了事件和源节点信息.进行数据查询时,sink点本地flooding查 询请求到最近的交叉节点,此后查询请求在交叉点间传播,最终源节点收到 查询请求,数据反向传送到sink点.,下图为TTDD

20、格状网建立与数据查询 源节点B发起建立格状网 Sink点向源节点B查询数据,TTDD协议的优点： 与Directed Diffusion协议相比,该协议采用单路径,能够提高网络生存时间,TTDD协议的不足： 1.计算与维护格状网的开销较大; 2.节点必须知道自身位置; 3.非sink点位置不能移动; 4.要求节点密度较大,路由协议的分类比较,路由协议的特点比较,路由协议的应用范围比较,贪心算法： 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛

21、的许多问 题他能产生整体最优解或者是整体最优解的近似解。 贪心算法的基本思路如下： 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解；,附录：,拓扑控制的概念与意义,概念 拓扑控制（topology control）是一种协调节点间各自传输范围的技术，可以减少节点的能耗或增加网络的传输能力。 意义 (1)影响整个网络的生存时间。 (

22、2)减小节点间通信干扰，提高网络通信效率。 (3)为路由协议提供基础。 (4)影响数据融合。 (5)弥补节点失效的影响。,拓扑控制的研究方向,WSN中拓扑控制可以分为两个研究方向：功率控制和层次拓扑结构控制。 功率控制机制调整网络中每个节点的发射功率，保证网络连通，在均衡节点中直接邻居数目(单跳可达邻居数目)的同时，降低节点之间的通信干扰。 层次拓扑控制是利用分簇思想，使网络中的部分节点处于激活状态，成为簇头节点。由这些簇头节点构建一个连通的网络来处理和传输网络中的数据，并定期或不定期地重新选择簇头节点，以均衡网络中节点的能量消耗。,拓扑控制的评价指标,连通性 在没有拓扑算法前，两个节点之间存

23、在k条路径，那么使用拓扑算法后，这两个节点中也应该存在k条路径。 覆盖性 覆盖问题中，最重要的因素是网络对物理世界的感知能力。 吞吐量 化简后的网络拓扑结构应该能够支持与原始网络相似的通信量。 扩展性（网络容量） 减少数据传输节点所能影响的邻居节点的数量,减少节点通信的传输范围,可以有效减小网络中的冲突域,从而降低通信冲突的概率。,拓扑控制的应用效果,实现拓扑控制的手段,1、在保证网络的连通性与覆盖性的情况下，控制节点的发射距离，减少发射功耗，同时减少分组冲突的可能性，减少不必要的开销； 2、尽可能让多的节点进行休眠，降低功耗； 3、数据融合，减少分组的冗余。,拓扑控制的表现,1、网络寿命：尽

24、量降低网络能耗，延长网络生存周期； 2、减小节点通信负载，提高通信效率：传感器节点分布密度一般比较大，通过拓扑控制技术中的功率控制技术可以通过选择节点的发射功率合理调整节点的通信范围，使得节点在连通性与覆盖性得到一个平衡点。 3、辅助路由协议：只有活动的节点才能进行数据转发，而拓扑控制可以确定由哪些节点作为转发节点，同时确定节点之间的邻居关系。 4、数据融合策略的选择； 5、节点冗余：由于传感器节点本身固有的脆弱性不能保证节点一直持续正常工作。,拓扑控制的分类,基于位置的拓扑控制算法-邻近图,基本思想 设所有节点都使用最大发射功率发射时形成的拓扑图G，按照一定的邻居判别条件q求出该图的邻近图G

25、，最后G中的每个节点以自己所邻近的最远通信节点来确定发射功率。 经典的邻近图算法 RNG、GG、DG、YG、MST、DRNG、DLMST、DLSS,DRNG与DLSS算法,第一步: 每个节点以最大的发射功率广播HELLO信息，该信息至少包括：节点ID号、最大的发射功率、自身的位置。节点在收到HELLO信息后，确定了自己可以达到的邻居集合。 第二步： DRNG与DLSS以各自的邻居算法确定邻居集合，DRNG以与它节点最近的邻居节点选择优先；而DLSS最小化了图中所有边的最大能量消耗, 并取单跳距离的节点作为其邻居节点。 第三步 确定邻居节点后，将发射半径调整到最远邻居节点的距离，进一步通过对拓扑图的边进行增删，使网络达到双向连通。,邻近图算法仿真结果对比,本文欣赏结束,红藕香残玉簟秋，轻解罗裳，独上兰舟。 云中谁寄锦书来？雁字回时，月满西楼。 谢谢欣赏！,