wsn路由协议.ppt

1、,Wireless Sensor Networks,无线传感器网络技术,第二章 WSN路由协议,Wireless Sensor Networks,基础知识, 1978年国际标准化组织 ISO（ International Standard Organize）公布了网络互连及网络体 系结构的框架, OSI/RM（ Open Systems Interconnection,Reference Model），简称为 OSI模型, OSI 模型是一个用于开发这些标准的框架，其自,身并不是一个标准。, 网络的任务是非常复杂的，并不是仅仅一个标准,就能处理的。,主机层，保证主机之间 数据的无差错传输,表示

2、层（6） 会话层（5）,传输层（4） 网络层（3）,链路层（2） 物理层（1）,高层,中间层,低层，又称介质层，控制网络中 信息的物理传输,Wireless Sensor Networks 网络逻辑结构 OSI (Open Systems Interconnection) 模型 应用层（7）,Wireless Sensor Networks,网络的逻辑结构, 可以在物理设备或节点间建立连接并控制这些点,间路由和数据传输的标准和协议。, 逻辑连接是建立在物理连接之上的 ，所以逻辑结 构和物理结构相互依赖，但是两者同时具有 高度 的独立性, 可以在不改变逻辑结构的情况下改变网络的物理,结构；, 同

3、样，同一物理网络在很多情况下可以支持不同,的标准和协议。,表示层（6） 会话层（5） 传输层（4） 网络层（3） 链路层（2） 物理层（1）,处理资 源设计 带宽资 源设计,存储资源 设计,Wireless Sensor Networks 各类资源与OSI模型层次之间的关系 应用层（7）,Wireless Sensor Networks,实际的OSI模型：一个电子邮件例子,Wireless Sensor Networks,网络层（NL：Network Layer）, 网络层的数据传输单元为“分组”(packet)，它 是一种数据的结构化形式。网络层功能以数据链 路层的无差错传输为基础，为网络内

4、任意两设备 间的数据交换提供服务。, 网络 层 主 要 解 决 通 信 子 网 的 运 行 控 制 ， 这 就 需 要,在通信子网中进行路由（routing）选择。, 如果 同 时 在 通 信 子 网 中 出 现 过 多 的 分 组 ， 会 造 成 阻塞（Congestion），当然还要 解决网际互连 的问题,Wireless Sensor Networks,网络层, 负责对在传输层协议控制下建立的连接或者会,话中的 每个数据包进行寻址和路由, 在网络层，消息将被分解为多个数据包，每个,数据包都带有源端和目的端的 地址。, 网络层用于在一个站点与另一站点之间传输块,（称为数据包）, 传输可以在

5、几个网络之间进行 网络层提供的服务,包括寻址、网络互连、错误处理、网络管理,（包括拥挤控制和数据包排队）等等,Wireless Sensor Networks,数据链路层（DL：Data Link Layer）, 数据链路层分为两个子层：, 逻辑链路控制（LLC）和媒体访问控制 (MAC） 逻辑链路控制是数据链路层中的第一个子层，通 常由IEEE 802.2标准定义,为网络层能够与任意类 型的媒体访问控制层工作提供接口。, 由LLC产生并传输到MAC层的帧称为LLC协议数,据单元（LLC Protocol Data Unit, LDPU), LLC层定义了无连接的和面向连接的通信服务。,Wir

6、eless Sensor Networks,数据链路层, 数据链路层的第二个子层: 媒体访问控制(MAC)层 控制设备允许访问物理层传输数据的方式和时间, 设备需要能够识别这些在网络媒体中传输的数据包，这是通过MAC,地址实现的, 从数据链路层往下，数据包采用MAC地址寻址来确定包的源和目的,地的物理设备 主要作用：,是通过校验、确认和反馈重发等手段将该原始的物理连结改造成无,差错的数据链路, 主要任务：, 加强物理层传输原始比特的功能，使之对网络层显现为一条无错线路,Wireless Sensor Networks MAC层的主要任务：,将该原始的物理连结改造成无差错的数据链路, 使之对网络

7、层显现为一条无错线路, ,如果两个设备同时在网络的共享媒体上传输 无论是有线还是无线，两个信号都会相互干扰，导致两 个设备的传输都无效 因此对共享媒体的访问需要有效的管理,确保在这种不断,产生冲突的情况下不浪费可用带宽 有线：载波监听多路访问/ 冲突检测：CSMA/CD 无线：载波监听多路访问/ 冲突避免： CSMA/CA，CA：Collision Avoidance,Wireless Sensor Networks,物理层技术, 当MPDU(MAC Protocol Data Unit)向下传至物理层 后，被物理层会聚协议（PHY Layer convergence Procedure，PL

8、CP)处理并被加上与所使用的物理层类型 有关的前导码和报头,前导码包含的一组比特可以让接收 机用来同步解调器和收到的信号时序, 物理层技术决定了网络可以达到的最大数据速率，因为,该层定义了数据流被编码至物理传输媒体的方式。, 由于MAC和PLCP报头、前导码和错误检测以及与冲突避,免或者退避有关的空闲周期，都意味着效率的降低, 有线：以太网802.3,ISDN,IEEE1394,SATA,USB. 无线： ,Wireless Sensor Networks OSI模型的物理层定义 为物理信道实体之间的比特序列传送 而进行的物理连接的激活、保持和解除 激活，提供机械、电气及过程上的手 段。物理层

9、应保证数据按位传送的正确 性。物理层涉及到机械、电气和过程性的接口问题，如： （1）信号“1“和“0”的表示电压数。 （2）一个比特信息占用的时间（位宽） （3）传输方式，包括半工、半双工和全双工。 （4）初始连接的建立。 （5）通信完毕后连接的断开。 （6）网络插头和插座的管脚数及其定义等。,Receive r,Communication channel,Transmitter,Wireless Sensor Networks,无线通信方式,Wireless Sensor Networks,无线PHY层功能, 信道选择；, 信道能量检测； 空闲信道评估；, 无线信道收发数据;, 接收包链路质

10、量的检测；,Wireless Sensor Networks 网络的逻辑结构,络 层,网,数据链路层,物,理 层,数据链路层,物,理 层,应,用 层,表 会,示 层 话 层,传,输 层,络 层,网,数据链路层,物,理 层,应,用 层,表 会,示 层 话 层,传,输 层,网,络 层,数据链路层,物,理 层,传输介质,传输介质,传输介质,络 层,网,OSI环境,主机B 应用进程B,主机A 应用进程A,CCP A,CCP B,Wireless Sensor Networks,OSI参考模型数据单元及各层主要功能总结,Wireless Sensor Networks,WSN体系结构,Wireless

11、Sensor Networks,蜂窝移动通信（B3G）,Wireless Sensor Networks,无线传感器网络是一种信息采集网络, 自组织通信是其中实现多跳的信息回传和进行网络,控制的手段。, 为了实现信息采集，无线传感器网络的业务大都发 生在数据汇聚节点（Sink）和普通传感器节点之间 下行业务：包括Sink节点到传感器节点的下行业,务（如查询指令下达）, 上行业务：传感器节点到Sink的上行业务（如采,集信息的回传)；, 传感器节点之间的横向业务所占比例较小，主要是,网络的控制信息和网内信息处理所需要的信息,Wireless Sensor Networks,无线传感器网络拓扑结构

12、, 因为网络的拓扑结构严重制约无线传感器 网络通信协议（如MAC协议和路由协议） 设计的复杂度和性能的发挥。, 根据节点功能及结构层次可分为：,平面网络结构 分级网络结构 混合网络结构 mesh网络结构,Wireless Sensor Networks,平面网络结构, 所有节点为对等结构，具有完全一致的功能,特性，也就是说每个节点均包含相同的 MAC 、路由、管理和安全等协议。, 这种网络拓扑结构简单，易维护，具有较好 的健壮性，事实上就是一种 Ad hoc 网络结 构形式。, 由于没有中心管理节点，故采用自组织协同,算法形成网络，其组网算法比较复杂,Wireless Sensor Netwo

13、rks,分级网络结构, 分级网络结构（也叫层次网络结构）是无线传感 器网络中平面网络结构的一种扩展拓扑结构，网 络分为上层和下层两个部分：,上层：中心骨干节点,下层：一般传感器节点。, 骨干节点之间或一般传感器节点之间采用的是平,面网络结构。, 具有汇聚功能的骨干节点和一般传感器节点之间,采用的是分层网络结构。,Wireless Sensor Networks,分级网络结构, 所有骨干节点为对等结构，骨干节点和一般传感器节点有不同,的功能,每个骨干节点均包含相同的MAC 、路由、管理和安全等功,能协议,一般传感器节点可能没有路由、管理及汇聚处理等功能。, 分级网络通常以簇的形式存在，按功能分为

14、： 簇首（具有汇聚功能的骨干节点：Cluster head） 成员节点（一般传感器节点：members）。, 网络拓扑结构扩展性好，便于集中管理, 可降低系统建设成本，提高网络覆盖率和可靠性 集中管理开销大，硬件成本高,Wireless Sensor Networks,一种分级网络结构,Wireless Sensor Networks,混合网络结构, 平面网络结构和分级网络结构的一种混合拓扑结构 网络骨干节点之间、一般传感器节点之间采用平面,网络结构, 网络骨干节点与一般传感器节点之间采用分级网络,结构。, 这种网络拓扑结构和分级网络结构不同的是一般传 感器节点之间可以直接通信，可不需要通过汇

15、聚骨 干节点来转发数据。, 这种结构同分级网络结构相比较，支持的功能更加,强大，但所需成本更高。,Wireless Sensor Networks mesh网络结构,WMN- Wireless Mesh Network, ,多跳（multi-hop）网络 网格网络 基于 802.11技术 与传统无线网络完全不同的新型无线网络, mesh网络是规则分布的网络 网络内部的节点一般都是相同的，mesh网络也称为对 等网,Wireless Sensor Networks,mesh网络结构的优点, mesh网络是构建大规模无线传感器网络的一个很 好的结构模型，特别是那些分布在一个地理区域 的传感器网络，

16、如人员或车辆安全监控系统, 尽管所有节点都是对等的地位，且具有相同的计 算和通信传输功能，但某个节点可被指定为簇首 节点，而且可执行额外的功能。, 一旦簇首节点失效，另外一个节点可以立刻补充,并接管原簇首那些额外执行的功能。,Wireless Sensor Networks,mesh网络结构,Wireless Sensor Networks,无线传感器网络的主要特点 传感器网络中的传感器节点数量多 传感器的节点分布稠密, 传感器的网络拓扑经常变化, 传感器节点通信主要 采用广播（broadcast）或,组播（ multicast）两种方式, 传感器节点的能量、计算能力和存储空间有限 传感器节点

17、的标识不规范,Wireless Sensor Networks 组播和广播的区别, ,广播： 当有多台主机想要接收相同的报文，广播采用 的方式是把报文传送到局域网内每个主机上，不管这 个主机是否对报文感兴趣。这样做就会造成了带宽的 浪费和主机的资源浪费 。 组播： 有一套对组员和组之间关系维护的机制，可以 明确的知道在某个子网中，是否有主机对这类组播报 文感兴趣，如果没有就不会把报文进行转发，并会通 知上游路由器不要再转发这类报文到下游路由器上。 当有多台主机同时成为一个数据包的接受者时，出于 对 带宽和CPU负担的考虑，组播成为了一种最佳选 择。,Wireless Sensor Networ

18、ks,无线传感器网络的协议栈1,2002年提出了WSN的五层模型：,Wireless Sensor Networks,无线传感器网络的协议栈2,Wireless Sensor Networks,无线传感器网络的协议栈3,Wireless Sensor Networks,无线传感器网络的网络层协议 无线传感器网络的网络层主要负责路由 的发现和维护,其路由协议包括了两个方 面的基本功能：,路径选择，即寻找源节点和目的节点,间的优化路径；,数据转发，即要将数据沿优化路径正,确转发。,Wireless Sensor Networks,无线传感器网络的协议栈4,Wireless Sensor Netwo

19、rks,WSN数据链路层研究的重点是MAC, 在WSN中，差错控制通常采用自动重发请求（ARQ）,和前向纠错（FEC）两种方式。, ARQ和FEC等纠错方式已有非常成熟的理论，主要需要,研究的是差错控制方案的比较和选择问题, 由于传感器节点密集、传输距离短，即使采用无线传,输，受信道衰落等特性的影响也比较小, 为了节省传感器节点的处理开销，广泛使用 ARQ方式 WSN数据链路层研究的重点是介质访问控制（media,Access control，MAC）协议,Wireless Sensor Networks,无线传感器网络的协议栈5,Wireless Sensor Networks,物理（PHY

20、）层协议, 信道选择；, 信道能量检测（energy detect, ED）； 空闲信道评估（clear channel,assessment ,CCA）；, 无线信道收发数据（PHY Protocol Data,Unit）；, 接收包链路质量（link quality indication,LQI）的检测；,Wireless Sensor Networks,WSN体系结构,？,Wireless Sensor Networks,无线传感器网络的数据分发,Wireless Sensor Networks,WSN的网络层需考虑两个相互关联的问题, 网络自身的结构（拓扑）和消息在网络中的路由算法是,

21、互相关联的, 无线传感器网络的定义中已经明确它是一个自组织的无,中心网络，无需人工管理, 看起来似乎没有必要讨论网络的拓扑结构问题： 网络节点间的物理通信链路可以使用任何拓扑结构。 实际情况并非如此，对网络逻辑结构的讨论是非常有意,义的，其中一个重要的原因是解决可扩展性问题 。,？,Wireless Sensor Networks,WSN的网络层, 网络层控制网络的运作，负责路由选择、数据包转发 ，,还完成流量控制 功能, 无线传感器网络中一般 很少考虑流量控制问题，因为传 感器网络的数据吞吐量很低，并且在服务质量（Quality of service，QoS）方面的要求较低。, 但网络的运作

22、及路由问题对无线传感器网络的设计人员 来说却是一个巨大的挑战，因为必须 尽 量 降 低 无 线 传 感 器网络节点的占空比 。, 低占空比的要求限制了用于同步、磋商、协调以及其他,网络层行为的允许开销,Wireless Sensor Networks,无线传感器网络的网络层, 在无线传感器网络中,由于受能量限制，节点之间往 往无法直接通信，通常需要借助中间节点以多跳路 由的方式将源数据传送至目的节点, 无线传感器网络的网络层主要负责 路由的发现和维,护, 其路由协议包括了两个方面的基本功能：,路径选择，即寻找源节点和目的节点间的优化路径 数据转发，即要将数据沿优化路径正确转发,Wireless

23、 Sensor Networks 内容提要 一WSN路由协议概述 二WSN路由协议分类,1. 2. 3. 4.,以数据为中心路由协议 集群结构路由协议 地理信息路由协议 QOS 路由协议,三WSN路由协议最新研究成果,Wireless Sensor Networks,1、WSN路由协议功能, 定义,WSN路由协议是 一套将数据从源节点传输到目的,节点的机制 。,设计目标,满足应用需求 低网络开销,资源利用的整体有效性 网络高吞吐率,Wireless Sensor Networks,2、WSN路由协议特点,特点,自组织的网络（随机部署）,数据的冗余性（多节点监测同一事件） 基于局部拓扑信息（硬件

24、限制） 网络功能（数据收集） 数据为中心,Wireless Sensor Networks,WSN路由协议要求,要求,能量高效（协议简单、节省能量、均,衡消耗）,可扩展性（网络范围、节点密度） 鲁棒性（节点变化、拓扑变化） 快速收敛性,Wireless Sensor Networks,3、WSN路由协议关键技术,考虑网络和节点能量优化（硬件限制） 具有高可扩展性 （网络规模、自组织）,适应强网络拓扑变化（节点移动、无线信道） 传感器网络路由中使用数据融合技术（数据为中,心）,传感器网络中流量分布不对称 （数据收集网,络、多源单 Sink),Wireless Sensor Networks,WS

25、N网络层的研究现状-1, 根据传输过程中采用路径的多少,可分为单路径路由协议,和多路径路由协议, 根据节点在路由过程中是否有层次结构、作用是否有差,异，可分为平面路由协议和层次路由协议, 根据路由建立时机与数据发送的关系，可分为主动路由协,议、按需路由协议和混合路由协议, 根据是否以地理位置来标识目的地、路由计算中是否利用 地理位置信息，可分为基于位置的路由协议和非基于位置 的路由协议。, 根据节点是否编址、是否以地址标识目的地，可分为基于,地址的路由协议和非基于地址的路由协,Wireless Sensor Networks,WSN网络层的研究现状-2, 根据路由选择是否考虑QoS约束，可分为

26、保证QoS的,路由协议和不保证QoS的路由协议, 根据数据在传输过程中是否进行融合处理， 可分为数,据融合的路由协议和非数据融合的路由协议。, 根据是否以节点的可用能量或传输路径上的能量需求 作为选择路由的依据，可分为能量感知路由协议和非 能量感知路由协议。, 根据路由建立是否与查询有关，可分为查询驱动和非,查询驱动的路由协议,Wireless Sensor Networks,4、传感器网络路由协议的挑战, 减小通信量, 构建能量有效的全局最优路由策略 保持通信量负载平衡 应具有容错性, 应具有安全机制,Wireless Sensor Networks,传感器网络路由协议的挑战,自组织布署（A

27、d hoc deployment） 能量消耗（Energy consumption ） 路由精度（Routing accuracy）,计算能力（Computation capabilities） 通信能力（Communication tolerance） 容错能力（Fault tolerance） 可扩展性（Scalability）,控制负载（Control overhead）,Wireless Sensor Networks 内容提要 一WSN路由协议概述 二WSN路由协议分类,1. 2. 3. 4.,以数据为中心路由协议 集群结构路由协议 地理信息路由协议 QOS 路由协议,三WSN路由协

28、议最新研究成果,Wireless Sensor Networks,WSN路由协议分类, 以数据为中心的平面路由协议, SPIN ( Sensor Protocols for Information,via Negotiation ), Directed Diffusion, 集群结构的路由协议, LEACH TTDD, 地理信息路由协议, GPSR GEAR, QoS路由协议, QoS路由协议,Wireless Sensor Networks 内容提要 一WSN路由协议概述 二WSN路由协议分类,1. 2. 3. 4.,以数据为中心路由协议 集群结构路由协议 地理信息路由协议 QOS 路由协议

29、,三WSN路由协议最新研究成果,Wireless Sensor Networks,1. 以数据为中心的平面路由, 传统网络作为以通信为目的的对等网络，所使用的 路由协议通常以地址作为节点的标识和路由依据 ， 完成任意两个节点间的通信任务。, 而无线传感器网络作为以数据收集为目的的数据汇 聚型网络，所关注的是节点监测区域的感知数据 ， 而不是具体哪个节点获取的信息。, 一般传感器网络将大量节点的随机部署，网络中通 常包含多个传感器节点与少数汇聚节点的数据流， 按照对感知数据的要求，数据通信模式和流向等， 以数据为中心形成消息的转发路径,DC，Data-centric,AC，Address-cen

30、tric,Wireless Sensor Networks 数据中心网络和地址中心网络 DC网络可 进行数据 融合，减 少网络中 的数据量,Wireless Sensor Networks 以数据为中心的平面路由 平面路由中所有节点具有相同的地位和功能，节点间协同 工作完成感知任务。 由于节点数量庞大，分布密度高，相邻节点间的数据采集 又大多面向同一监测点，因此在传输数据时会经常出现冗 余现象。 需要构建以数据为中心的平面路由协议，即汇聚节点向某 些区域发送查询并等待来自于这些区域内的节点所采集的 相关数据。 平面路由的特点:, ,结构简单,鲁棒性较好 缺乏对通信资源的优化管理，对网络动态变化

31、的反应速 度较慢,Wireless Sensor Networks,平面结构的优缺点,Wireless Sensor Networks,层次结构的优缺点,Wireless Sensor Networks,（1) SPIN：Sensor Protocol for,Information via Negotiation, SPIN协议是一种以数据为中心的自适应路由协议，其目的： 为了避免由于节点间重复地收发大量的冗余信息所造成,的能源浪费；,网络中的节点必须实时监控本地的能源消耗，并根据能 量等级改变工作模式来延长节点自身和整个网络的运行 时间, 考虑到WSN中的数据冗余问题： 邻近的节点所感知的

32、数据具 有相似性，通过节点间协商（Negotiation）的方式减少网 络中数据的传输的数据量。, 节点只广播其他节点所没有的数据以减少冗余数据，从而有,效减少能量消耗。,Flooding: 广播方式，节点向邻 居节点转发数据包， 不管其是否收到过相 同的,Gossiping: 不广播，随机选一个 相邻节点转发，感知 节点感知区域有重 叠，导致数据冗余,Wireless Sensor Networks Flooding协议 和 Gossiping协议 Gossiping是对 Flooding的改进,Wireless Sensor Networks,Flooding 的Implosion (内爆

33、） Gossiping 的overlap（重叠）,Flooding 的Implosion (内爆）,Wireless Sensor Networks,Gossiping 的overlap（重叠）, Flooding协议中，节点产生或收到数据后向所有邻节 点广播，数据包直到 过期或到达目的地才停止传播。 该协议具有严重缺陷：, 内爆。节点同时从邻节点收到多份相同数据。, 重叠。节点先后收到同一区域的多个节点发送的相同数据。 资 源利用盲目 。 节 点 不 考 虑 自 身 资 源 限 制 ， 在 任 何 情 况 下 都 转,发数据。, Gossiping 协议是对Flooding 协议的改进，节点

34、在发 送数据时不再采用广播的形式，而是随机选取一个相邻 节点转发它所接收到的数据，有效避免了内爆现象； 但 仍然无法解决部分重夏和盲目使用资源所引起的传输时 延长、传输速度慢等问题。, Flooding和Gossiping这两个协议不需要维护路由信,息，简单易行，但扩展性很差。,Wireless Sensor Networks SPIN（Sensor Protocol for Information via Negotiation）协议是对Flooding协议的改进 通过和邻居节点的协商来减少Flooding带来的内爆和重叠的 影响 通过元数据来完成协商过程, 元数据 (meta-,data)

35、：一种对源数据的映射，比源数据短, 避免传输冗余数据 3步握手协议(ADV-REQ-DATA) PIN协议采用三次握手协议来实现数据的交互 SPIN-2在SPIN-1的基础上加入了能量阈值 当一个节点的剩余能量低于能量阈值后，减少其在协议中参与的活 动。,Wireless Sensor Networks,SPIN,（Sensor Protocol for Information via Negotiation） 协商通过元数据进行 元数据描述实数据(数据压缩） 元数据与原始感知数据一一对应 协议消息 消息广播包：Advertise (ADV) 数据请求包：Request (REQ) 数据包：D

36、ata transfer (DATA),A A A,A A A,Wireless Sensor Networks SPIN：3步握手协议 节点A有新数据，通过ADV,发布新数据信息，使用元 数据 B节点收到ADV后，发现自 己没有该数据，通过REQ向 A请求新数据 A节点向B节点传送源数据 B节点融合新数据，并通 过ADV发布新数据消息 如果某节点有ADV中描述 的数据的副本就忽略该消 息,Wireless Sensor Networks,SPIN协议评价, 优点,部分解决了内爆和重叠问题 不需要进行路由维护,对网络拓扑变化不敏感，可用于移动WSN, 缺点,本质上SPIN还是向全网扩散新消息，

37、开销比较大 当产生或收到数据的节点的所有邻节点都不需要数据 时，将导致数据不能继续转发，以致对该数据感兴趣 的较远节点无法得到数据。这使得SPIN协议无法保证 数据的可靠传递。,Wireless Sensor Networks,SPIN协议族（Protocol Family） SPIN-PP:适合点对点信道的SPIN协议, For networks using point-to-point transmission,media, Ideal conditions assumed with no packet loss, SPIN-EC：SPIN-PP的基础上增加了能量限制, SPIN-PP w

38、ith low energy threshold, SPIN-BC： 适合于广播信道的SPIN协议, 3-stage handshake protocol for broadcast media, SPIN-RL： 考虑信道上存在分组丢失的SPIN协议, SPIN-BC for Lossy networks,Wireless Sensor Networks,（2） DD路由算法（Directed Diffusion）-,基于查询的路由, 基于查询的路由, 在诸如环境监测、战场评估等应用中，汇聚节点（Sink) 发出任务查询命令，传感器节点向汇聚节点报告采集的 数据。, 通信流量主要是汇聚节点和

39、传感器节点之间的命令和数 据传输 ，同时 传感器节点要在传输路径上进行数据融 合 ，通过减小通信流量来节能。, DD中采用了 以数据为中心的查询机制，增加了路径与,数据的匹配程度。, 查询是通过定期全网广播兴趣包来实现的，如果查询频 率过高，会引起广播风暴问题，造成能量的快速消耗。,Wireless Sensor Networks,定向扩散模型DD, 定向扩散模型DD是一种以数据为中心的信息传播协,议，是专门为无线传感器网络设计的路由策略, 主要思想:,将来自于不同源节点所发送的数据聚合起来, 目的：,减少数据冗余,缩减数据被传递的大小和次数,保存网络能量和延长网络生命周期, 运行DD的传感器

40、节点使用基于属性的命名机制来描述,数据,Wireless Sensor Networks,DD路由算法（Directed Diffusion）,:基于查询的路由, Sink节点查询兴趣消息, 兴趣消息采用泛洪的方法传播到网络 有和兴趣匹配数据的节点发送数据 兴趣扩散阶段建立节点到Sink的路径, 兴趣消息，由属性值对组成 ：, 查询内容（温度、湿度等）, 查询要求（如上报间隔、持续时间等）,type = four-legged animal / detect animal location interval = 20 ms / send back events every 20 ms dura

41、tion = 10 seconds / . for the next 10 seconds,rect = -100, i00, 200, 400 / from sensors within rectangle,Wireless Sensor Networks,定向扩散（Directed Diffusion）,Wireless Sensor Networks,Directed Diffusion特性,Wireless Sensor Networks,Directed Diffusion的元素,Wireless Sensor Networks,兴趣包、网络梯度, 汇聚节点（Sink)将查询任务封装

42、成兴趣消息,（interest）的形式 ，采用洪泛方式传播兴趣消息到其 他节点。, 兴趣消息用来表达用户对监测区域内感兴趣的信息， 例如监测区域内的温度、湿度和光照等环境信息。 Sink节点向所有传感器节发送兴趣包信息，即通过分 配不同属性值来表示不同任务的描述符。每个传感器 节点收到兴趣包后保存在各自的缓存中。, 兴趣包中包含时间标签域和若干个梯度(gradient) 域， 按成本最小化原则引导数据扩散的方向 。节点发 出的查询业务也用属性的组合表示，逐级扩散最终遍 历全网。,Wireless Sensor Networks,网络梯度, 在兴趣消息的传播过程中，协议逐跳地在每个 节点上建立反

43、向的从数据源到汇聚节点的数据 传输梯度。, 节点保存一个称为“梯度”的变量与整个业务 请求的扩散过程相联系，反映网络中间节点对 匹配请求条件的数据源的近似判断。, 节点用一组标量值表示它的选择，值越大意味 着向该方向继续搜索获得匹配数据的可能性越 大，这样的处理最终将会在整个网络中为Sink 节点的请求建立一个临时的“梯度”场 ，匹配 数据可以沿“梯度”最大的方向中继回Sink节 点。,Wireless Sensor Networks,网络（信息）梯度, 信息梯度类似于反向路由条目（从当前节点到Sink的 路由），它既包含了下一跳节点（发来查询的相邻节 点）和时间戳，也包含了信息采集相关的内容

44、（如数 据采集内容、采集速率等）, 兴趣包中包含时间标签域和若干个梯度域，按成本最,小化原则引导数据扩散的方向。, Sink节点发出的查询业务也用属性的组合表示,逐级扩,散,最终遍历全网,找到所有匹配的原始数据., “梯度”变量与整个业务请求的扩散过程相联系,反映 了网络中间节点对匹配请求条件的数据源的近似判断,Wireless Sensor Networks,兴趣和梯度, Sink节点向全网查询兴趣M,建立源节点和Sink间路径 兴趣在全网中扩散,对每一个活动任务，Sink周期进行查询, 邻居更新自己的兴趣cache，并且转发 兴趣cache中的条目,时间戳：指示接收到相关兴趣消息的最近时间

45、 若干梯度域：每个梯度和其邻居节点相关联,每个梯,度中含有一个指定的数据传输率 持续时间：该兴趣消息的有效期,Wireless Sensor Networks,Directed Diffusion, 查询消息的传播: 建立数据的传输梯度,汇聚节点发送查询消息, 兴趣消息：任务性质、数据采集/发送数率、时间戳等 中间节点：记录,转发, 梯度：表示了数据的传输方向,Wireless Sensor Networks,兴趣（Interests）表述,A A A,A A A,Wireless Sensor Networks SPIN：3步握手协议 节点A有新数据，通过ADV,发布新数据信息，使用元 数据

46、 B节点收到ADV后，发现自 己没有该数据，通过REQ向 A请求新数据 A节点向B节点传送源数据 B节点融合新数据，并通 过ADV发布新数据消息 如果某节点有ADV中描述 的数据的副本就忽略该消 息,Wireless Sensor Networks,SPIN协议评价, 优点,部分解决了内爆和重叠问题 不需要进行路由维护,对网络拓扑变化不敏感，可用于移动WSN, 缺点,本质上SPIN还是向全网扩散新消息，开销比较大 当产生或收到数据的节点的所有邻节点都不需要数据 时，将导致数据不能继续转发，以致对该数据感兴趣 的较远节点无法得到数据。这使得SPIN协议无法保证 数据的可靠传递。,Wireless

47、 Sensor Networks,DD（Directed Diffusion）路由,Wireless Sensor Networks,Interest的传播,Wireless Sensor Networks,路径梯度（Gradient）,Wireless Sensor Networks,“兴趣查询”及“信息梯度”创建, 查询在网络中洪泛，节点收到后为其创建,“信息梯度”，并转发。, “信息梯度”类似于反向路由条目（从当前 节点到sink的路由），它既包含了下一跳节点 （发来查询的相邻节点）和时间戳，也包含 了信息采集相关的内容（如数据采集内容、 采集速率）。, 查询可能沿多条路径到达被查询的传

48、感器节 点。节点根据要求启动查询任务，并把采集 到的信息回传给sink。,Wireless Sensor Networks,“路径加强”, 查询发出一段时间后，sink开始从多条路径收,到回传的信息。, 此时，它从中选择最优路径（如回传信息的 时延最小），向相应的相邻节点发送“路径 加强”消息。, “路径加强”消息也是一个查询命令，与前,一个不同的是它包含了更大的信息采集速 率。“路径加强”消息沿最优路径逐跳传输 到被查询的传感器节点，这条路径成为“主 路径”，而其他路径相应的成为备用路径。 传感器节点接收到“路径加强”消息后，根,据要求提高信息采集速率。,Wireless Sensor Ne

49、tworks,加强（reinforced）路径,Wireless Sensor Networks,Interest的任务命名（naming）,Wireless Sensor Networks,Interests的区分和汇聚,Wireless Sensor Networks,Interests缓存,Wireless Sensor Networks,Interests的传播,Wireless Sensor Networks,数据搜集（data gathering）,Wireless Sensor Networks,数据传播（1/3）,Wireless Sensor Networks,数据传播（2/

50、3）,Wireless Sensor Networks,数据传播（3/3）,Wireless Sensor Networks,路径加强（reinforcement）,Wireless Sensor Networks,路径加强（2/6）,Wireless Sensor Networks,路径加强（3/6）,Wireless Sensor Networks,路径加强（4/6）,Wireless Sensor Networks,路径加强（5/6）,Wireless Sensor Networks,路径加强（6/6）,新路径,Wireless Sensor Networks 路径修复问题 加强路径上的

51、节点可以触发和启动路径 的加强过程 C和源节点 之间路径,断裂,Wireless Sensor Networks,定向扩散方法的设计选择,Wireless Sensor Networks,DD协议评价,优点,数据中心路由，定义不同任务类型/目标区域消,息；,路径加强机制可显著提高数据传输的速率； 周期性路由：能量的均衡消耗；,缺点,周期性的洪泛机制: 能量和时间开销都比较大； 节点需要维护一个兴趣消息列表，代价较大；,Wireless Sensor Networks,WSN信息传播, SPIN DD,Wireless Sensor Networks,DD 和 SPIN协议有以下两点不同, （1

52、）当汇聚点通过 flooding任务的方式向传 感器节点发送查询请求时，DD协议讨论的是按 需数据查询 。而在 SPIN协议内，传感器节点通 过广告机制 通知数据的可用性 并允许感兴趣的 节点来查询该数据。, （2）DD协议要求所有的通信过程都遵循邻居 到邻居的传输方式，并且 每个节 点都有执行数 据融合和缓存的能力 。,Wireless Sensor Networks （3）谣传（Rumor Routing）路由, ,有些无线传感器网络的数据传输量较少，如果采用定向 扩散路由，需要经过查询消息 的洪泛传播和路径增强机 制才能确定一条优化的数据传输路径，开销相对过大。 如果有sink节点的一次

53、查询只需一次上报，则DD（定向 扩散）协议开销就太大了，Rumor协议正是为解决此问 题而设计的。 谣传路由机制引入了查询消息的单播随机转发，克服了 使用洪泛方式建立转发路径带来的开销过大问题。 为此，提出了适用于数据传输量较小的无线传感器网络 的谣传路由。,Wireless Sensor Networks,Rumor 的基本思想, 借鉴欧氏平面上任意两条曲线交叉几率很大的思想。 当节点监测到事件后将其保存 创建称为Agent的数据包：,生命周期较长,包括事件和源节点信息,将其按一条或多条随机路径在网络中转发。, 收到Agent的节点根据事件和源节点信息建立反向路径，并 将Agent再次随机发

54、送到相邻节点，并可在再次发送前在 Agent 中增加其已知的事件信息。, sink节点的查询请求也沿着一条随机路径转发，当两路径交 叉时则路由建立；如不交叉，Sink节点可flooding查询请 求。, 在多Sink节点、查询请求目很大、网络事件很少的情况下， Rumor协议较为有效。但如果事件非常多，维护事件表和收 发Agent 带来的开销会很大。,Wireless Sensor Networks,谣传路由基本思想, 事件区域中的传感器节点产生代理（agent）消息 ，代 理消息沿随机路径向外扩散传播，同时汇聚节点发送的 查询消息也沿随机路径在网络中传播。, 当代理消息和查询消息的传输路径相

55、遇的时候,就会形成 一条从汇聚节点到事件区域的完整路径，于是交叉节点 会沿查询消息的反向路径将事件信息传送到查询节点。,Wireless Sensor Networks,谣传路由, 谣传路由以“事件查询者”和“查询命令事件区 域”的双向（random walk）的方式解决把用户命令发 送到被查询事件的发生区域的路由问题。, 用户可以通过任何一个节点接人网络并发送命令。 接收到用户命令的节点，如果没有到达被查询事件区域,的路由，就将其随机转给一个邻居。, 为了加快用户命令到事件发生区域的传输过程，检测到,一个事件的传感器节点应该把事件通告出去。, 在Rumor 中，当节点检测到某一事件时，记录到

56、事件的,距离为0，并以一定概率产生代理。,Wireless Sensor Networks,代理（agent）消息, 代理是一个包含对事件的简单描述的分组。, 代理在网络中转发，目的是把事件发生的消息通告 给更多的节点，以便在这些节点收到用户的命令 时，能够指引命令传送到事件区域。, 代理传播过程中，如果遇到自己此前没有看到的事,件，也会把该事件添加到自己的事件列表中。,Wireless Sensor Networks,Rumor算法代理的传播, 节点收到代理即获得了到达事件发生区域的路由。 如果代理的TTL不为0，则继续被转发。, 代理中记录着其最近经过的节点和这些节点的相邻节 点，当节点转

57、发代理时，为了让事件传播的范围更大， 应优先选择不在列表中的节点。, Rumor把用户命令和事件同时以随机走动的方式在网络 中传播，当两个传播路径出现交叉，则建立了用户命令 到事件发生地点的路径。, 用户命令如果在生存期内无法到达事件区域，则可以增,大TTL或者以洪泛方式发送命令。,Wireless Sensor Networks Rumor算法代理的传播, ,利用代理提供的信息，可能优化节点到某个事件的路 径。 如：代理 1存有一条到事件 1 的路径，其长度是 3；当 节点A 收到代理 1 时，节点A发现代理提供的路径比自 己原来记录的更短，则更新自己的路径。,Wireless Sensor

58、 Networks Rumor的工作过程, ,以 “事件查询者”和 “查询命令事件区域 ”的双向（ random walk）的方式解决把用户命令发送到被查询事件的发生区域的路 由问题。 Rumor把用户命令和事件同时以随机走动的方式在网络中传播 ， 当两个传播路径出现交叉，则建立了用户命令到事件发生地点的 路径。 用户命令如果在生存期内无法到达事件区域，则可以增大 TTL或 者以洪泛方式发送命令。,Wireless Sensor Networks,Rumor Routing,与DD路由相比，Rumor可有效地减少路由建立的开销。 Rumor路由数据传输路径不是最优路径，可能存在路由环 路问题。,Wireless Sensor Networks,Directed Diffusion Family, GBR路由(Gradient-Based Routing)协议：,梯度域扩展（传感器节点