现代通信技术课程9

1、4、 网络路由协议原理网络路由协议原理 4.1 有线路由协议有线路由协议 4.2 无线路由协议无线路由协议 4.3 机会路由协议机会路由协议 现代通信技术课程现代通信技术课程 主讲：宋梁，主讲：宋梁，LSONGIEEE.ORGLSONGIEEE.ORG QQQQ群：群：314945874 2015-20162015-2016 本堂内容本堂内容 无线自组网无线自组网 无线传感网无线传感网 什么是无线自组网？ 无线自组网（Wireless Adhoc Network）是一组以无 线链路进行通信、由移动节点动态形成的网络，它是 一个多跳的临时性自治系统。最早由美国DOD的PRNET 项目进行研究，主

2、要用于军事领域。但是由于无线自 组网构造时不需要预先存在的网络基础设施，如基站 等，因此在民用领域中也具有广阔的应用，如发生地 震、水灾后的营救等。随着无线通信技术和移动终端 技术的发展，Ad hoc网络在军用和民用等领域的应用 日益受到重视，各方面的研究不断展开。 无线自组网路由协议设计面临的问题 多播支持 QoS 支持 节能支持 位置支持 单向信道 支持 有限带宽 支持 当前主要无线分组网路由协议分析 无线分组网路由协议根据所采用的路由策略可分为 主动路由和按需路由两种。 主动路由 采用预先获取（Proactive）策略 按需路由 采用按需获取（Reactive）策略 当前主要无线分组网路

3、由协议分析 主动路由协议 DSDVDSDVOLSROLSRLANMARLANMAR 主动路由协议要求每个节点维护一张或几张路由表，其中包 含了网络中所有其他节点的路由信息。所有节点周期性地更 新这些路由表，以保证路由信息是一致和最新的，当网络拓 扑结构改变时，节点向整个网络传播路由变更消息。主动路 由的优点是当到目标节点的路由存在时，延时很小；缺点是 需要花费较大的开销保持路由更新。 DSDVDSDV（Distance Source Distance Distance Source Distance VectorVector） DSDV 协议是著名的Bellman-Ford 路由算法 的增强版

4、本,是在DVA 基础上进行改进设计的， 被认为是最早的自组网路由协议。在DSDV 协 议中，每个节点维护一个路由表，用于记录到 所有可达目标的“下次跳转”。DSDV 协议的特 点是采用了序列号机制来区别路由的新旧程度， 防止路由环的产生；其缺点是不适应快速变化 的自组网，不支持单向信道。 DSDVDSDV OLSROLSR（Optimized Link State RoutingOptimized Link State Routing） OLSR 是对链路状态协议的优化，以适应无线自组 网的需求。OLSR 的关键是使用了多点中继MPR （MultiPointRelay）。节点通常选择一组一次跳

5、 转邻居节点作为它的MPR集，在MPR 和MPR 选 择者之间必须存在双向链路，并且MPR 集能够与 MPR 选择者的所有二次跳转邻居通信。 在 OLSR 协议中，信息通过MPR 在网络中传递, 因为只有很少的MPR,所以控制包的数目和大小都 得到很大精简。 OLSR 协议比较适合于节点数目多且密集的网络。 OLSROLSR LANMARLANMAR（Landmark Routing Protocol for Landmark Routing Protocol for Large ScaleLarge Scale NetworksNetworks） 当网络尺度增大和节点的移动性增强时，过多的处

6、理开销 使得平面形式的主动路由模式变得不可行，LANMAR 使 用层次路由解决网络伸缩性和路由开销问题。 LANMAR 协议将网络划分为一些逻辑子网，这些子网中 的成员具有某种共性，因此子网节点很可能作为一个群体 整体性地移动。LANMAR在逻辑子网内使用FSR （Fisheye State Routing）无线自组网协议，一个节点 与距离较近的节点交换路由信息的频率要远大于与距离远 的节点交换路由信息的频率，因此可以减少路由开销。 LANMARLANMAR 当前主要无线分组网路由协议分析 按需路由协议 DSRDSRAODV层次路由层次路由 与表驱动的主动路由协议不同，按需路由协 议并不在每个

7、节点上维护最新的路由信息， 而是在某个路由信息需要时才去动态获取路 由信息。采用按需路由协议的优点是不需要 进行周期性的路由信息广播，节省了一定的 网络资源；缺点是发送数据分组时，如果没 有去往目标节点的路由，数据分组需要等待 因路由发现而带来的延时。 DSR 是最早采用按需路由思想的路由协议，它使用了源 路由机制进行分组转发，在每个包的包头携带一个完整 的节点序列，由于包本身已经包含了所有的路由判定， 因此中间节点不需要维护最新的路由信息就能完成包转 发。 DSRDSR（D DYNAMICYNAMIC S SOURCEOURCE R ROUTINGOUTING） DSR协议主要由两个机制构成

8、：路由发现和路由维护，这两 种机制都采用按需方式操作。当源节点不知道到达标节点的 路由时，源节点采用路由发现机制动态地获得这个路由，源 节点向网络广播路由请求（RREQ）包。每个接收到RREQ包的 节点将重传这个包，除非它本身是目标节点或者在该节点的 路由缓冲中保持了到达目标节点的路由，在后两种情况下， 该节点将向源节点发送路由应答（RREP）包。为了减少路由 发现过程的开销，每个节点维护一个源路由缓冲，这样可以 减少RREQ包的发送。如果源路由中的某条链路中断，源节点 会收到RERR通知，此时，源节点可以重新发起路由发现过程。 DSRDSR（D DYNAMICYNAMIC S SOURCEO

9、URCE R ROUTINGOUTING） DSR 路由协议的优点是中间节点不用维护去往全网所 有节点的路由信息，而且可以避免出现路由环路。它 的缺点是每个数据分组都携带了路径信息，造成协议 开销较大，而且也不适合于网络直径大的无线自组网 ,网络可扩展性不强。 DSRDSR（D DYNAMICYNAMIC S SOURCEOURCE R ROUTINGOUTING） AODV 协议是在DSDV 协议基础上结合类似DSR 中的按需路由 机制进行改进后提出的，不同之处在于AODV采用了逐跳转发 分组方式，而DSR 是源路由方式。 在 AODV 路由协议中，源节点向其邻居节点广播路由请 求（RREQ

10、），邻居节点记录一个反向路由，然后转发这个请 求，直到请求到达目标节点或拥有到达目标节点路由的某个 中间节点。如果中间节点拥有到达目标节点的路由，该节点 将构造一个路由应答（RREP）包，选择一个反向路由的最佳 链路将其发送；如果由于节点的移动，路由上的某个链路失 效，即某个中间节点不可达，此时该节点的邻居节点将检测 到这一情况，并且发送路由错误（RERR）消息给它的上游节 点，RERR 消息将最终到达源节点，源节点可以重新发起路 由发现过程。 AODVAODV（A AD D H HOCOC O ONN-D-DEMANDEMAND D DISTANCEISTANCE V VECTORECTOR

11、） AODV 路由协议的显著特点是加入了组播路由协议扩展， 支持QoS。它的缺点是不支持单向信道，因为AODV协议基 于双向信道的工作，路由回答分组直接沿着路由请求的 反方向回到源节点。 AODVAODV（A AD D H HOCOC O ONN-D-DEMANDEMAND D DISTANCEISTANCE V VECTORECTOR） 层次路由协议通过组合使用按需获取和预先获取等路由策 略，避免了主动路由协议中过量的控制消息流量问题和按需 路由协议中的长时延问题，常见的层次路由协议包括：DDR, CBRP, CEDAR, GSR,FSR, HARP, ZRP, HSR, BRP,IARP,

12、 IERP, LANMAR 等，其中最具代表性的就是区域路由协议 ZRP（Zone Routing Protocol）。 AODVAODV（A AD D H HOCOC O ONN-D-DEMANDEMAND D DISTANCEISTANCE V VECTORECTOR） ZRP 是第一个利用层次结构并混合使用按需路由策略和主动 路由策略的自组网路由协议。在ZRP 中，每个节点维护的区域 大小由区域半径指定，为了综合利用按需路由和主动路由的优 点，ZRP 协议规定每个节点采用DVA 主动路由协议维护去往区 域内其他节点的路由，采用类似DSR 协议中的按需路由机制寻 找去往区城外节点的路由。所

13、以ZRP协议的性能很大程度上由 区域半径决定。通常小区域半径适合于由移动速度较快的节点 组成的密集型网络；大区域半径适合于由移动速度较慢的节点 组成的稀疏网络。 当前主要无线分组网路由协议分析 分析对比分析对比 路由协议是实现无线自组网最关键的部分。为了适应 无线自组网带宽、能量有限等特性，认为无线自组网 的路由协议应满足以下几点需求： 分布式 操作 按需获 取路由 预先获 取路由 支持 “静默” 支持单 向链路 安全性 要好 避免路 由环 无线自组网路由协议实现技术探讨 无线自组网的路由功能可以在 OSI 参考模型的第二 层或者第三层实现。美军JTRS 系统早期的无线自组 网方案就是将节点移

14、动性隐藏于第二层的，这种方法 的不足是当网络的规模很大时，必须在各个域之间有 很多的桥接，导致过多的广播流量，拥塞整个网络。 在第二层实现无线自组网路由的好处是可以利用某些 链路层的信息和特征进行路由优化，但通过使用下面 介绍的自适应网络协议栈结构，这种优化带来的益处 同样可以在第三层中实现。 无线自组网路由协议实现技术探讨 在 第 三 层 实 现 无 线 自 组 网 路 由 的 例 子 有 美 军MIL-STD-188-220C 标准和MANET 路由协 议。第三层移动路由的好处是“为使用混合物理层介 质节点组成的多跳网络提供了网络级的一致性”，使 用无线技术A 和无线技术B 的装备分别形成

15、各自的无 线自组网络，当网络中存在同时具备A 和B 接口的装 备时，通过使用第三层路由，两个无线自组网的节点 之间可以透明地通信，实现不同技术体制装备间的“ 动中通”。 无线自组网链路代价和路由判定的准据(Metrics)， 如带宽、时延、应用特性、物理位置和电池电量等， 其信息的来源分布于网络协议栈的各个层次。 本堂内容本堂内容 无线自组网无线自组网 无线传感网无线传感网 概述概述 无线传感器网络中路由协议的主要任务是建立从源节点到汇聚节点的 路由，并可靠地传输数据。路由协议直接关系到无线传感器网络多跳 自组织功能的实现。作为无线传感器网络中数据传输的指挥者，路由 协议主要有以下两个方面的功

16、能： n建立源节点到目的节点的优化路径。 n将数据沿着优化路径进行传输。 与有线网络和蜂窝式无线网络不同，WSN中没有基础设施和全网统一 的控制中心。在这种无中心的环境下，路由可以看成分布式地获取网 络拓扑信息，以一定准则计算路径并对路径进行维护的过程。 概述概述 n网络特点是路由设计的主要依据，对网络特点的分析是进行协 议设计的前提。 n无线传感网络中，网络业务的最大特点是具有明显的方向性。 为了实现信息采集的目的，WSN的网络业务大都发生在数 据汇聚节点（sink）和普通的传感器节点之间，包括sink节点 到传感器节点的下行业务（如查询指令下达）和传感器节点到 sink的上行业务（如采集信

17、息的回传）。 传感器节点之间的横向业务所占比例较小，主要是网络的 控制信息和网内信息处理所需要的信息。 n无线传感器网络的一个基本理念是以大量低成本节点组网，通 过节点之间的协作节点之间的协作获得比单一的高精度、高可靠性和高成本的 传感器更好的信息采集效果。传感器节点的能量约束和无线通传感器节点的能量约束和无线通 信链路的不可靠是无线传感器网络固有的，将对协议设计产生信链路的不可靠是无线传感器网络固有的，将对协议设计产生 较大影响较大影响。 概述概述 路由路由协议的分类协议的分类 无线传感器网络路由协议有多种分类方法。根据网络拓扑组织 结构，可分为平面型路由协议平面型路由协议和层次（分簇）型路

18、由协议层次（分簇）型路由协议。 n平坦型路由协议 各个节点间的地位平等，节点通过局部信息来生成路由，其优点是结 构简单，鲁棒性较好，但对网络动态变化的反应较慢，且有可能存在 对资源盲目使用的情况。 概述概述 平面路由协议的典型代表有：定向扩散路由(Directed Diffusion，DD)、谣传路由(Rumor Routing)与闲聊路由 (Gossiping)、GBR、HREEMR 协议和SPIN 协议等。 概述概述 n层次（分簇）型路由 网络被划分为若干个簇，每个簇由一个簇头节点和若干个簇成员节点组成。 簇头节点负责簇内成员节点数据信息的收集和融合处理，以及簇间数据的转 发。分簇协议中设

19、计簇头的选举策略是一个重要议题。典型的分簇路由协议 有：LEACH、PEGASIS、TEEN、APTEEN、HEED和CHEF等。 平坦平坦型路由协议型路由协议 洪洪泛泛(Flooding)(Flooding)协议和闲聊协议和闲聊(Gossiping)(Gossiping)协议协议 洪泛协议：洪泛协议： 是一种传统的路由协议，它不要求维护网络的拓扑结构和计算路 由。收到数据的节点以广播形式向所有的邻居节点转发收到数据的节点以广播形式向所有的邻居节点转发，直到数据包 到达目的节点或者达到预先设定的最大跳数为止。 平坦平坦型路由协议型路由协议 协议机制： 源节点S希望发送数据给目的节点D。S发起数

20、据广播，然后任意 一个收到广播的节点都无条件将该数据副本广播出去，每一节点都重 复这样的过程直到数据遍历全网或者达到规定的最大跳数。 洪泛法具有实现简单、路径容错性好、时延短等优点，但存在消息消息 内爆内爆(Implosion) 、重叠重叠(Overlap)和盲目使用资源盲目使用资源的问题，数据传 输时能量消耗巨大、资源浪费严重。一般用于军事或与其它算法进行 性能上的比较。 消息内爆：节点几乎同时从邻居节点收到多份相同数据的现象。浪费 能量 重叠：节点先后收到监控同一区域的多个节点发送的几乎相同的数 据。浪费能量 盲目使用资源：即不考虑各节点能量可用状况，在任何情况下都转 发数据。 平坦平坦型

21、路由协议型路由协议 消息内爆 重叠 平坦平坦型路由协议型路由协议 闲聊协议（闲聊协议（ Gossiping Gossiping ）：）： 是对洪泛协议的改进，为了节省能量，节点收到数据后随 机选取一个相邻节点进行转发，而不采用广播形式，避免了消 息的内爆，但随机选取节点的机制导致了路径质量较差，增加 了端到端的传输时延，并且无法解决消息重叠和盲目使用资源 的问题。 优点：降低了数据转发重叠的可能性，避免了信息内爆现象的产 生。 缺点：点到点的时延增大。 由于随机转发某一个节点的方向并不一定在距离目的节点更近的 方向上，因此容易造成数据到达目的节点时间过长或者跳数己达 到最大，而数据还没有到达目

22、的节点，造成递送失败。 共同点：不需要维护路由信息，也不需要任何算法，简单但扩展性差。 4.2 4.2 平坦型路由协议平坦型路由协议 SPINSPIN协议（协议（sensor protocol for information via sensor protocol for information via negotiationnegotiation） nSPIN协议是第一个以数据为中心的自适应路由协议，通过协商机制协商机制来 解决洪泛算法中的“内爆”和“重叠”问题，节省了能量的消耗。 n节点在传输数据之前先进行协商，这种协商机制可确保数据传输的有 效性，避免了盲目传播（解决信息“内爆”和“重叠

23、”问题）。 n节点间通过发送元数据元数据(即描述传感器节点采集的数据属性的数据， meta-data)，而不是采集的整个数据进行协商。由于元数据小于采集 的实际数据，所以，传输元数据消耗的能量相对较少。为避免盲目使 用资源，所有传感器节点必须监控各自的能量变化情况，如果处于低 能量水平，则中断一些操作，例如数据转发。 平坦平坦型路由协议型路由协议 n协议提供了3种类型的消息：ADV、REQ和DATA。包含元数据的 ADV消息用于通知邻节点有数据要发送，REQ消息用于邻节点请 求数据，DATA用于发送原始数据到邻节点。 ADV：用于数据的广播，当某一个节点有数据可以发送时，可 以用ADV数据包通

24、知其邻居节点。 REQ：用于请求发送数据，当某一个收到ADV的节点希望接收 DATA数据包时，发送REQ数据包。 DATA：为原始感知数据包，里面装载了原始感知数据。 n工作机制：如下图所示，当传感器节点有数据要发送时，先广 播ADV消息（使用元数据），邻近节点收到ADV消息后，如果愿 意接收该数据，就向发送节点发出REQ请求消息，最后发送节 点向请求的邻居节点发送DATA数据包。 平坦平坦型路由协议型路由协议 SPINSPIN工作过程工作过程 平坦平坦型路由协议型路由协议 SPIN协议簇有4种不同的形式： SPIN-BC：适合于广播信道的SPIN协议 SPIN-PP：适合于点对点信道的SPI

25、N协议 SPIN-EC：在SPIN-PP基础上增加了能量限制 SPIN-RL：考虑信道上存在分组丢失的SPIN协议 SPIN协议的优点： 简单，不需要进行路由维护；通过数据协商机制保证了只向需要的节 点发送数据，提高了转发效率。小ADV消息解决了内爆问题；通过数 据命名减轻了重叠问题；节点根据自身资源和应用信息决定是否进行 ADV通告，避免了资源利用盲目问题。可用于移动WSN。 SPIN协议的缺点： ADV消息采用广播方式传输，开销比较大；每次发送数据包之前都要 进行协商，数据传输延迟较大。当产生或收到数据的节点的所有邻节 点都不需要该数据时，将导致数据不能继续转发，以致较远节点无法 得到数据

26、。 平坦平坦型路由协议型路由协议 基本基本概念概念 DD是无线传感器网络中以数据为中心（基于信息查询）的里程碑 式平面路由协议，得到了广泛的应用和研究。sink节点首先采用泛洪 (flooding)方式向全网广播Interest Interest (sink感兴趣的数据)；其次建 立相邻节点间的梯度梯度(反映沿该方向获得匹配数据的性能的矢量值)； 具有匹配Interest数据的节点接收到Interest后，依据梯度选择路径 并将数据送回sink。因此，DD协议包含兴趣（interest）扩散、梯度 （gradient）建立、数据（data message）传播（探测）以及路径加 固（routi

27、ng reinforcement）4个主要动态过程。 兴趣、数据、梯度兴趣、数据、梯度三个基本概念要透彻理解。 节点收到一个兴趣消息后该如何处理？ 节点收到一个数据消息后该如何处理？ 梯度如何建立？ 路径如何加强？ 平坦平坦型路由协议型路由协议 （1 1）命名机制）命名机制（如何描述兴趣？如何描述数据？） 无线传感器网络中的节点没有全局惟一的编号标识，每个传感器节点都只是每个传感器节点都只是 知道邻近节点的情况知道邻近节点的情况，而不知道全局所有传感器节点信息，所以为了保证源 节点产生的数据能够传输到监测者所在的任务管理节点，就需要把兴趣和采 集的数据以一种方式对应起来。 定向扩散协议是一种以

28、数据为中心的路由协议，所有的任务数据都是经过数 据命名的，而这种命名方式就是通过命名机制完成的。这种命名机制就是一 种简单的属性和值的配对（属性和值的配对（ Attribute-Value pairs ）的列表，这样就可以 对兴趣消息进行匹配。例如，对车辆的跟踪任务可能被描述为以下兴趣： type=wheeled vehicle /兴趣类型兴趣类型 interval=20ms /事件的传输时间间隔事件的传输时间间隔 duration=10s /兴趣的生存时间兴趣的生存时间 rect=-100, 100, 200, 400 /兴趣的传感区域兴趣的传感区域 平坦平坦型路由协议型路由协议 对兴趣的响

29、应也使用了类似的名字命名方案。所以，一个传感器节点检测到 轮式车辆后可能会以产生下面的数据回答： type=wheeled vehicle /类型类型 instance=truck /类型的实例类型的实例 location=127, 200 /节点位置节点位置 intensity=0.7 /信号强度信号强度 confidence=0.80 /匹配的确信度匹配的确信度 timestamp=00:24:40 /信号采集时间信号采集时间 在无线传感器网络中，针对定向扩散协议的第一步是设计一个命名方案（这 个命名方案并不固定）。通常而言，一个兴趣的属性组合描述要包括：监测 对象，监测区域，起始时间，有

30、效时间，发送速率等，不同的任务可以增加 各自的特殊的属性项。 平坦平坦型路由协议型路由协议 （2 2）兴趣和梯度）兴趣和梯度 兴趣用来表示查询的任务，例如监测区域内的温度、动物的运动轨迹等信息。 一个查询任务作为一个兴趣通过无线传感器网络传播，通过汇聚节点广播兴 趣消息。 梯度是一个宽泛的概念。一般梯度定义应包括一个数据的传输方向和传输速 率。在不同的设计中，设计者可以根据所关注的网络性能不同，采用不同的 梯度策略，例如，梯度列表项可包括如下几个字段：上一跳节点ID（方向， 记录着兴趣地直接来源）；事件传输速率（值，记录兴趣中要求的事件传输 间隔）；生存期（记录兴趣的生存期）。 总的来说，梯度

31、就是一个值和一个方向，方向指明事件可能会传向的邻居， 而值表明节点以何种传输速率将事件传给方向指向的邻居。 每个节点都维持一个兴趣列表，该兴趣列表中可有多个兴趣，每个兴趣 可能对应多个梯度，如图所示。 平坦平坦型路由协议型路由协议 定向扩散的路由机制定向扩散的路由机制 定向扩散的路由机制可以分为周期性的兴趣扩散兴趣扩散、梯度的建立梯度的建立、数据探测数据探测和 路径的加强路径的加强四个阶段，如图所示。 平坦平坦型路由协议型路由协议 （1）兴趣扩散 将任务通过命名机制构建成一个兴趣。例如： type=wheeled vehicle /兴趣类型兴趣类型 interval=1s /事件的传输时间间隔

32、事件的传输时间间隔 duration=60s /兴趣的生存时间兴趣的生存时间 rect=-100, 100, 200, 400 /兴趣的传感区域兴趣的传感区域 timestamp=01: 01: 22 /初始化时间初始化时间 expiresAt=01: 02: 22 /终止时间终止时间 平坦平坦型路由协议型路由协议 对于每个任务，为了动态适应节点失效、拓扑变化等情况，汇聚节点周期性周期性 的向网络中邻居节点广播兴趣消息。 在网络的初始阶段，由于处于探索的阶段，兴趣在网内扩散的目的仅仅是尝 试探测是否有事件源的存在，因此兴趣内所包含的匹配事件的传输间隔 （interval）比较长，这样可以避免过

33、多的通信量。 每个节点在本地都有一个兴趣列表。对于每一个兴趣，列表中都有一个梯度 表项记录发来该兴趣消息的来源（邻居节点）、数据发送速率和时间戳等任 务相关信息，以建立该节点向汇聚节点传递数据的梯度关系。每个表项还有 一个字段用来表示该表项的有效时间值，超过这个时间后，节点将删除这个 表项。 每个兴趣可能对应多个邻居节点，而每个邻居节点则只对应一个梯度信息。 当一个节点接收到一个兴趣消息时，节点要对该兴趣消息进行记录和转发， 按以下流程处理： 平坦平坦型路由协议型路由协议 注意：注意： 1.1.节点节点B B应该能够判断是否要将该兴趣转发，应该能够判断是否要将该兴趣转发， 如果发现已对该兴趣进

34、行了广播，就不如果发现已对该兴趣进行了广播，就不 再转发了。再转发了。 2.2.对于对于B B节点来说，这个兴趣仅仅来自节点来说，这个兴趣仅仅来自A A节节 点，而不管它来自哪个点，而不管它来自哪个SinkSink节点，兴趣节点，兴趣 表中也不包含表中也不包含SinkSink节点的信息。即只需节点的信息。即只需 记录局部信息，而不是全部。记录局部信息，而不是全部。 A B 平坦平坦型路由协议型路由协议 （2）梯度建立 定向扩散中，梯度的概念非常重要。梯度是在兴趣的发送过程中形成的，通 过梯度，源节点和目标节点就通过梯度作为路径联系起来了。 梯度包括邻居节点邻居节点、数据传送率数据传送率、有效期

35、有效期等信息。 当节点B从它的邻节点A收到某个 兴趣后，它判断将要转发该兴趣， 于是广播出去。这时A又会收到刚 转发的该兴趣，这样在A和B之间 就建立了双向梯度。这样的一个双 向梯度可以保证网络中的节点能够 被“兴趣”覆盖到。 A B 平坦平坦型路由协议型路由协议 （3）数据探测（传播） 当传感器节点采集到与兴趣匹配匹配的数据时，就把数据发送到梯度上的 邻居节点（组播或广播），并且按照梯度上的数据传输速率（例如每 秒传送一条数据）设定无线传感器模块采集数据的速率。由于可能从 多个邻居节点收到兴趣消息，节点向多个邻居节点发送数据，汇聚节 点可能收到经过多个路径的相同数据。 数据发送的形式如下：

36、type=wheeled vehicle /类型类型 instance=truck /类型的实例类型的实例 location=127, 200 /节点位置节点位置 intensity=0.7 /信号强度信号强度 confidence=0.80 /匹配的确信度匹配的确信度 timestamp=01:02:01 /信号采集时间信号采集时间 平坦平坦型路由协议型路由协议 中间节点接收数据的处理 流程如下： A B 平坦平坦型路由协议型路由协议 简单地说，传感器节点（源节点）收集到数据，与缓存中的兴 趣记录进行匹配，如果匹配程度达到要求，就认为该数据是 Sink节点需要的。然后，它把数据包往相邻节点转

37、发（广播）。 而相邻（中转）节点接受到新的数据包时，也会在它的缓存中 寻找是否有匹配的兴趣项，如果没有，则认为该数据包无效， 以丢弃的方式进行处理；要是有匹配的兴趣项，则看是否在过 去曾接收转发过同一数据，如果是，则也作丢弃的方式处理， 如果不是，则记录相关信息，再次转发给自己的邻居节点。如 此，数据包就可以由源节点逐步扩散传输到数据接收发送器。 平坦平坦型路由协议型路由协议 （4）路径的建立和加强 在上述描述的过程中，sink节点开始时不断的将一个兴趣注入到网络中进行 传播，兴趣传播时速率较低。兴趣的传播过程是为了寻找到合适的区域节点兴趣的传播过程是为了寻找到合适的区域节点 的通路的通路。兴

38、趣在传播的过程中建立了许多梯度（称之为探测梯度探测梯度），这些梯 度连通起来构成了sink节点和源节点之间的许多条数据通路。当源节点发现 了匹配的目标后，它会发送试探性的探测数据探测数据，这些数据沿着上述的若干条 通道返回给sink节点，发送的数据传输速率较低，因为这时初始化兴趣的间 隔值较高。在探测数据到达sink后，sinksink会根据从不同的数据通路接收数据会根据从不同的数据通路接收数据 的效果，选出一条或几条的效果，选出一条或几条“高效高效”的通路的通路，以后就在这些高效通路上传送的 数据。为了加强邻居，sink重新发送兴趣（点对点），但是发送兴趣时用较 高的数据传输速率。 type

39、=wheeled vehicle /兴趣类型兴趣类型 interval=10ms /事件的传输时间间隔事件的传输时间间隔 duration=60s /兴趣的生存时间兴趣的生存时间 rect=-100, 100, 200, 400 /兴趣的传感区域兴趣的传感区域 timestamp=01: 01: 22 /初始化时间初始化时间 expiresAt=01: 02: 22 /终止时间终止时间 平坦平坦型路由协议型路由协议 假设以数据传输延迟作为路由加强的标准以数据传输延迟作为路由加强的标准，汇节点选择首先发来最新数据的 邻居节点作为加强路径的下一跳节点，向该邻居节点发送路径加强消息。路 径加强消息中

40、包含新设定的较高发送数据速率值。邻居节点收到消息后，经 过分析确定该消息描述的是一个己有的兴趣，只是增加了数据发送速率，那 么该节点按照同样的规则选择加强路径的下一跳邻居节点。 路径加强的标准不是唯一的路径加强的标准不是唯一的，例如可以选择在一定时间内发送数据最多的节 点作为路径加强的下一跳节点，也可以选择数据传输最稳定的节点那作为路 径加强的下一条节点。在加强路径上的节点如果发现下一跳节点的发送数据 速率明显减少，或者收到来自其他节点的新位置估计，推断加强路径的下一 跳节点失效，就需要使用上述的路径加强机制重新确定下一跳节点。 平坦平坦型路由协议型路由协议 基于定向扩散路由的设计选择基于定向

41、扩散路由的设计选择 前面介绍了定向扩散协议的路由机制，对于不同的应用需求或者不同的网络 状况，可以对定向扩散协议的路由机制的各个过程进行不同的路由选择。 平坦平坦型路由协议型路由协议 定向扩散路由协议特点定向扩散路由协议特点 定向扩散的本质是一种框架性的协议，通过对梯度及路径加固策略的 改变可得到不同的具体协议，例如：GBR路由(Gradient-Based Routing)协议， EAR(Energy Aware Routing)路由协议，CADR路由 (Constrained Anisotropic Diffusion routing)协议等。 以数据为中心的路由算法，使得无线传感器网络的

42、通信不再依赖特定的节点， 而依赖于网络中的数据。 采用多路径，健壮性好； 使用数据融合能减少数据通信量； 节点遵循本地交互的原则。节点只需要知道局部(邻居)节点的情况，无需了 解整个网络的拓扑结构，也不需要特定的节点来计算路由。可以说，定向扩 散的寻路是自适应的； 兴趣传播及Gradient的建立开销很大； 对于大规模网络，会带来较大开销和时延。 资源盲目使用导致能耗不均匀，可能导致某些节点的过早死亡。 层次层次（分簇）型路由协议（分簇）型路由协议 分分簇路由协议概述簇路由协议概述 前面所讲的平面型路由协议具有以下特点： 所有节点功能一致、地位平等，不存在瓶颈节点，网络结构简单、健 壮性好。但

43、平面结构中所有节点都需要生成到达汇聚节点的路由，随 着网络规模的扩大，会带来大量的控制开销，因此，可扩展性差，对 网络动态变化的反应慢。 层次层次（分簇）型路由协议（分簇）型路由协议 在分簇路由协议中，网络通常被划分为簇(cluster)。所谓簇，就是 具有某种关联的网络节点集合。 每个簇由一个簇头(cluster head)和多个簇内成员(cluster member) 组成，低一级网络的簇头是高一级网络中的簇内成员，由最高层的簇 头与基站BS(base station)通信。如下图所示： 层次层次（分簇）型路由协议（分簇）型路由协议 分簇路由协议具有以下特点： 1)由簇首对整个网络进行集中

44、管理，能够动态适应网络拓扑结构的变化，可扩展性 好，非常适合于规模比较大的网络系统。 2)由簇首构成一个骨干网完成远距离的数据转发，簇成员可以按TDMA时隙轮流采集 数据，在空闲时可以关闭通信模块，节省了能量。 3)簇成员仅需要将数据传输到簇首，缩短了传输距离；簇首可以对簇内数据进行必 要的融合后再转发，减少了网络的通信量。 4)分簇路由只由簇首参与路径计算，极大地减少了路由节点的数目，降低了路由开 销。 5)分簇算法复杂，簇首选举过程中节点间需要交换大量的控制消息，带来一定的开 销。 6)簇首是网络中的关键节点，一旦簇首出现故障，容易造成较大面积的网络瘫痪。 7)簇首的能耗远大于其它成员节点

45、，如果没有较好的能量平衡措施，容易造成簇首 节点过早耗尽能量而死亡。 层次层次（分簇）型路由协议（分簇）型路由协议 分分簇算法的评价标准簇算法的评价标准 (1)簇首数量合适 簇首数量决定了分簇网络系统的结构和特性，不宜太多或太少，应根据应用 要求以尽量减少控制开销和降低能耗为原则来确定。另外，在每轮分簇过程 中，簇首数量应该相对稳定，以保证应用系统的数据采集精度。 (2)簇首位置分布均匀 簇首是网络的关键节点，要负责簇内数据的融合处理和成员节点的协调，实 现簇间数据转发。因此，簇首应均匀分布在整个监控区域。簇首的分布情况 可以用簇间重叠度来评价，其计算方法如下公式所示： 其中，n为簇首数，xi

46、为第i个簇内的节点数（总数），N为节点总数。K为簇 间重叠度，其值大于或等于1，其值越小，则簇首分布越均匀。 层次层次（分簇）型路由协议（分簇）型路由协议 (3)簇首负载均衡 簇首负载分为簇内负载和簇间转发负载两部分，簇间转发负载与节点 的位置有关，而簇内负载与簇内节点的数量有关。要实现簇内负载均 衡要求各个簇具有相近的节点数，其负载均衡程度的计算方法如公式 所示： 其中，n为簇首的个数，xi为第i个簇的成员节点数，B为负载均衡程度， 其值越小，负载均衡程度越好。 层次层次（分簇）型路由协议（分簇）型路由协议 (4)节点能量平衡 节约能量是无线传感器网络路由协议设计的首要目标，簇结构的生成 和

47、维护必须具有较小的通信开销，尽量减少节点的能量消耗。另外， 保持节点间的能量平衡也是设计路由协议时需要考虑的关键因素，它 直接影响网络的有效工作时间。节点能量平衡程度的计算方法如公式 所示： 其中，N为网络节点总数，Ei为第i个节点的剩余能量，EB表示能量平 衡程度，其值越小，意味着网络的能量消耗越能均匀地分配到各个传 感器节点上。 层次层次（分簇）型路由协议（分簇）型路由协议 分分簇算法的分类簇算法的分类 （1）按组织方式分：固定分簇和动态分簇 固定分簇：预先分配好节点是簇首或是簇成员，并且其身份始终保持不变， 适合于异构无线传感器网络。 动态分簇：簇首通过分簇算法选举产生，簇首和簇成员的身

48、份动态变化，适 合于同构无线传感器网络。 （2）按簇内跳数分：单跳分簇和多跳分簇 单跳分簇：簇成员采用一跳传输将数据发送到簇首。结构简单，但簇首数量 较多，簇内传输距离较远，能量消耗较大。 多跳分簇：簇成员采用多跳传输将数据发送到簇首。簇首数量少，簇覆盖范 围大，节点发送距离短，但簇生成算法复杂。 层次层次（分簇）型路由协议（分簇）型路由协议 （3）按分簇时机分：主动分簇和被动分簇 主动分簇：分簇算法中每隔固定的时间间隔对簇首进行轮换，有利于 保持节点间的能量平衡，避免簇首消耗过多的能量。 被动分簇：簇结构相对稳定，在异常情况（如簇首死亡或簇首能量小 于额定值）发生时才重新分簇。开销较小，但簇

49、结构变化慢，容易导 致部分节点能量消耗过度。 层次层次（分簇）型路由协议（分簇）型路由协议 LEACHLEACH协议协议 1. 1. 协议简介协议简介 LEACH（Low Energy Adaptive Clustering Hierarchy）是由MIT的Heinzelman W等人在2000年提出的第一个基于数据聚合的自适应分簇路由协议。 基本思想：将所有节点分成若干个簇，每个簇选取一个簇头，其余的节点为簇 内成员。簇内成员发送数据给簇头，簇头需要把数据进行融合后再发送给汇聚 节点。通过等概率地随机循环选择簇头，将整个网络的能量负载平均分配到每 个传感器节点，从而达到降低网络能量耗费、延长

50、网络生命周期的目的。 协议特征：采用自适应成簇技术和簇首节点轮换技术。簇首动态选举、簇结构 由本地协调产生、簇内实现数据融合等。 LEACH的执行过程是周期性的。LEACH将一个工作周期称为一“轮”（round）， 每轮分为簇形成阶段和数据传输阶段两部分。 层次层次（分簇）型路由协议（分簇）型路由协议 2. 2. 网络模型和拓扑结构网络模型和拓扑结构 LEACH协议的网络模型为：(1)网络中有固定基站(Sink节点)且远离传感器节 点，研究中不考虑基站的能量消耗，假定其具有充足的能量供应；(2)网络中 所有节点同构且具有有限的能源；(3)网络中所有节点具有相同的起始能量； (4)节点是静止的；

51、(5)节点总是有数据要发送；(6)节点可感知它的剩余能量， 并能改变发射功率。 层次层次（分簇）型路由协议（分簇）型路由协议 3. 3. 工作原理及过程工作原理及过程 LEACH中的操作是按“轮”(round)进行的。每一轮包含簇的建立阶段簇的建立阶段和 稳定的数据传输阶段数据传输阶段。簇的建立阶段主要形成簇，稳定的数据传输阶段是 进行数据传输。为了使能量消耗最小，通常第二个阶段持续时间要比第一 个阶段的时间长。 层次层次（分簇）型路由协议（分簇）型路由协议 层次层次（分簇）型路由协议（分簇）型路由协议 （1）簇建立阶段 簇首选举 在每一轮的开始，节点随机产生一个0，1之间的随机数，然后与系统

52、阈 值T(n)相比，决定自己能否成为簇首。若当前轮中这个值小于设定的阈值 T(n)，则该节点称为簇首， T(n) 按下式计算： 其中，P 是期望的期望的簇头节点与网络总节点数的比例（例如 p=0.05），r 是当前选举的轮数（第一轮，r=0），G 表示这一轮循环中未当选簇头的 节点集合。 使用这个阈值，可保证每个节点会在使用这个阈值，可保证每个节点会在1/p 1/p 轮操作内充当一次簇首。轮操作内充当一次簇首。 层次层次（分簇）型路由协议（分簇）型路由协议 分析： 在r=0时，T(n)=p，每个簇首节点的概率P是相同的。 r的值越大， T(n)的值越来越大，这样未当过簇首节点成为簇首的概率就越

53、 大。 当 r=l/p-1时， T(n)=1，网络中从未当过簇首的节点都可能成为簇首。 当 r=l/p 与 r=O 时T(n)的取值相同，r=l/p+l与 r=l时T(n)的取值相同，经 过1/p轮，所有节点又重新开始新一轮的循环。 层次层次（分簇）型路由协议（分簇）型路由协议 簇的形成 一旦簇首节点被随机选举出后，簇首节点需要告知其它节点自己已当选为簇簇首节点需要告知其它节点自己已当选为簇 首的消息首的消息。 该消息是非持续的一CSMA的ADV消息，ADV消息包含簇首节点标号和一个报头。 簇首节点需要在整个网络内用最大发射功率进行广播簇首节点需要在整个网络内用最大发射功率进行广播（由于ADV

54、消息较小，增 大簇首发射功率并不会造成额外大的能量消耗），以保证所有节点都能收到。 普通节点普通节点接收到簇首广播ADV消息后，选择信号最强的簇首作为此轮要加入的选择信号最强的簇首作为此轮要加入的 簇簇。接收到的广播信号最强则表示它与簇首距离最短。 普通节点普通节点确定了所要加入的簇后，需要向簇首节点发送一个请求加入消息需要向簇首节点发送一个请求加入消息。 该请求加入消息由节点自身ID、簇头ID及报头三部分组成。节点根据先前接 收到的簇首节点的广播ADV信号，调整向簇首节点发射的功率，使其和簇首节 点广播信号功率相同。 簇首节点收到节点的请求加入消息后，会为其建立一个簇首节点收到节点的请求加入

55、消息后，会为其建立一个TDMATDMA时隙表时隙表。最后根最后根 据成员节点的数目产生一个据成员节点的数目产生一个TDMATDMA时隙调度表，以广播的方式发送出去时隙调度表，以广播的方式发送出去，告诉 成员在什么时刻可以发送数据。 层次层次（分簇）型路由协议（分簇）型路由协议 工作流程： 层次层次（分簇）型路由协议（分簇）型路由协议 （2）稳定阶段（数据传输） 一旦簇形成，TDMA调度表确定，数据传输就开始了。簇头节点在收到 成员节点传来的数据后对数据进行数据融合和压缩，将融合处理后的 数据传输给Sink节点。在经历一段时间后，新的一轮重新开始，上述 过程又开始循环进行。具体过程如下： 簇内节点依据TDMA调度表所规定的时隙，将采集数据传输到簇首。在 非自已的时隙内