《AdHoc的初步理解》PPT课件.ppt

1、浙江工商大学,Ad Hoc网络,Ad Hoc 基本介绍研究的主要问题 体系结构 信道接入协议 路由协议 分簇结构和算法（略） 节能问题,Ad Hoc 网络,10:04,2,“Ad Hoc” 一词源于拉丁语，意为“For the specific purpose only”, 即:特别的，临时的。 Ad Hoc网络是由一组带有无线收发装置的移动终端组成的一个多跳的临时性自治系统。 -移动终端：兼备路由器和主机两种功能，可以通过无线连接构成 任意的网络拓扑 -多跳：由于节点发射功率有限，故无线传输范围受限，无法直接 通信的节点通过中间节点转发实现通信 -临时：战地通信、灾后营救、野外作业、临时集会

2、等 -自治：没有严格的控制中心，所有节点通过分层的网络协议和分 布式算法协调各自的行为 Ad Hoc网络可独立工作，也可以末端子网的形式接入现有网络，不适于作为中间承载网络。,Ad Hoc 基本介绍,10:04,3,典型的Ad Hoc网络结构,10:04,4,自愈式雷场系统 系统采用智能化的移动反坦克地雷阵来挫败敌人对地雷防线的突破。 具体：1、将地雷配备无线通信与自组织联网单元，通过某种方式布撒（飞机、 地对地导弹等） 2、地雷迅速构成移动Ad Hoc网络 3、遭到敌方坦克突破后，地雷通过对拓扑结构的自适应判断和自身兼 备的自动弹跳功能迅速“自愈”，重新构建网络，对敌方坦克实施 阻拦。 4、

3、如此多次反复，直到网络无法重构，系统自行引爆 作用：限制敌军机动能力，延缓敌军进攻或撤退速度，在一定时间内 封锁特定区域。,Ad Hoc 的一个应用例子：,10:04,5,由移动性引起的：无中心、自组织、 生存时间短 由终端引起的：多跳路由、拓扑动态变化、携带方便、能源受限 由信道引起的：带宽较窄、无线信道质量差 广播信道是多跳共享的，一个节点的发送，只有 其一跳相邻节点可以听到 总体：无基础设施支持、自动配置、健壮、安全性 差、路由选择维护困难,Ad Hoc的特点,10:04,6,信道接入技术：决定网络的性能，隐终端、暴露终端 路由协议： 网络体系结构：提供多种业务及支持一定QoS的需要 服

4、务质量保证：不同层都要提供相应的机制， 基于特定的网络和应用环境进行研究 广播和多播：Ad Hoc的特殊性导致问题复杂 安全问题： 网络互联技术：不同路由协议和传输层服务的转换工作 能耗节省机制：核心，功率控制 网络公平性：实现公平性的算法,Ad Hoc 网络研究的主要问题,10:04,7,Ad Hoc 基本介绍及研究的主要问题 体系结构 信道接入协议 路由协议 分簇结构和算法（略） 节能问题 QoS保障（略）,Ad Hoc 网络,10:04,8,Ad Hoc网络的节点分为主机、路由器和电台三部分。 -主机：普通移动终端的功能 -路由器：维护网络拓扑结构和路由信息，完成报文转发的功能 -电台：

5、为信息传输提供无线信道支持,节点结构,10:04,9,Ad Hoc网络的节点结构,从物理结构分：,10:04,10,拓扑可变的网络包含四种基本结构： 1、中心式控制结构 2、分层中心式控制结构 （普通节点设备简单，中心控制节点设备复杂， 有较强的处理能力，负责路由和实施流量控制） 3、完全分布式控制结构（平面结构） 4、分层分布式控制结构（分级结构）,Ad Hoc的网络结构,10:04,11,Ad Hoc的网络结构,平面结构的Ad Hoc网络 （只适用于中小规模的Ad Hoc网络）,10:04,12,平面结构的Ad Hoc网络 优点：1、简单，所有节点在网络控制、路由选择和流量管理上 都是平等

6、的，又称对等式结构。 2、原则上不存在瓶颈，源与目的节点间存在多条路径， 可以较好的实现负载平衡和选择最优化的路由。 3、节点覆盖范围小，相对较安全。,Ad Hoc的网络结构,10:04,13,平面结构的Ad Hoc网络 缺点：1、在节点数目很多，特别是在节点大量移动的情况下，控 制开销大，路由经常中断，很难实施集中式的网络管理 和控制。 2、扩充性差，每一个节点都需要知道到达其他所有节点的 路由，所以网络规模受限。,Ad Hoc的网络结构,10:04,14,分级结构的Ad Hoc网络 1、网络划分为一到多个簇(cluster)，每个簇由一个簇头和多个簇成员组成。 2、簇头形成高一级的网络，又

7、可以再分簇，再组成更高一级的网络。 3、簇头可以指定，也可以由节点使用算法选举产生。 4、为了实现簇头间的通信，要有网关节点支持。网关节点指同时位于两个簇头通信范围内的节点。 5、簇头和网关节点形成高一级的网络，称为虚拟骨干网(VBN),Ad Hoc的网络结构,10:04,15,分级结构的Ad Hoc网络 簇头：1、维护到达其他簇的路由信息，负责簇间数据的转发。 2、知道网络中所有节点与簇的所属关系，知道所属簇成员 的位置。 簇成员：不需要维护复杂的路由信息,Ad Hoc的网络结构,10:04,16,分级结构的Ad Hoc网络 优点：1、良好的可扩充性，网络规模不受限制。可以简单的通 过增加簇

8、的个数和网络的级数来增大规模。 2、很强的抗毁性，因为簇头节点可以随时选举产生。 3、使路由信息局部化，减少路由协议的开销，提高系统 吞吐量，容易实现全网的局部同步。 4、节点定位比平面结构简单。 5、结合了无中心和有中心模式。,Ad Hoc的网络结构,10:04,17,分级结构的Ad Hoc网络 缺点：1、要有簇头选举算法，增加计算复杂性。 2、不一定能使用最佳路由，因为簇间信息都要经过簇头 寻路。 3、簇头作为集中转发点可能会成为新的网络瓶颈。,Ad Hoc的网络结构,10:04,18,分级结构的Ad Hoc网络 单频分级结构（所有节点使用同一频率通信） （根据硬件配置不同分类，还有多频分

9、级结构）,Ad Hoc的网络结构,10:04,19,分级结构的Ad Hoc网络 多频分级结构 1、不同级使用不同的频率通信 2、高级节点同时处于多个级中，使用 多个频率，以实现不同级的通信。,Ad Hoc的网络结构,10:04,20,Ad Hoc网络的协议栈,由于TCP/IP已成为事实上的网络互联标准，Ad Hoc网络的体系结构应基于TCP/IP体系结构，并根据自身特点进行必要的简化、修改和补充。 为了获得较高的系统性能，即适应Ad Hoc网络动态变化，节能，满足QoS保证，需要采用基于应用和网络特征的跨层体系结构。,10:04,21,Ad Hoc 基本介绍及研究的主要问题 体系结构 信道接入

10、协议 路由协议 分簇结构和算法（略） 节能问题 QoS保障（略）,Ad Hoc 网络,10:04,22,运行在物理层上，是所有报文在无线信道上发送和接收的直接控制者，它的性能好坏直接关系着信道的利用效率和整个网络的性能。 面临的问题：不同的信道共享方式 隐终端 暴露终端,Ad Hoc网络的信道接入协议,10:04,23,点对点共享（最简单） 多点共享（以太网） 点对多点 共享（蜂窝） 多跳共享（Ad Hoc）,Ad Hoc网络的信道共享方式,10:04,24,多跳共享：当一个节点发送报文时，只有在它的邻居节点才 能够收到。其他节点感知不到，故不受影响，可 以同时发送报文，提高了频率的空间复用度

11、。 即：在使用一个通信频率的情况下，Ad Hoc网络 中可以有多对节点同时进行通信。 多跳共享广播信道的直接影响： 报文冲突与节点所处的地理位置有关。即报文冲突是局 部事件，发送节点和接收节点感知到的信道状况不一定相 同，带来隐终端、暴露终端问题。,Ad Hoc网络的信道共享方式,10:04,25,隐终端位于准备接收的站点范围内，但在发送站点的范围之外。如图：当 A 和 C 检测不到无线信号时，都以为 B 是空闲的，因而都向 B 发送数据，结果发生碰撞。,隐终端(Hidden Terminal)问题,10:04,26,隐终端问题会引起报文冲突，从而影响信道利用率 在单信道条件下，隐发送终端问题

12、（不能发送任何消息）可以用握手机制部分解决；但隐接收终端问题（通知发送者自己是隐终端）无法解决，即无法告诉发送者自己是隐终端，而发送终端无法收到目标接收者的CTS，不能确定其是隐终端或者是没有开机，只能重新发送RTS。,隐终端(Hidden Terminal)问题,10:04,27,与隐终端相对的现象：它在发送站的范围内但在接收站的范围外。如图： B 向 A 发送数据，而 C 又想和 D 通信。 C 检测到媒体上有信号，于是就不敢向 D 发送数据。,暴露终端(Exposed Terminal)问题,10:04,28,如图：单信道条件下，B向A发送数据时，C知道自己是暴露终端，认为自己可以发送数

13、据。C向D发送RTS，D发送回C的CTS会与B发送的数据报文在C处冲突，C永远听不到D的CTS。C不但没向D成功发送数据，反而重发了许多无用的RTS。,暴露发送终端问题,10:04,29,如图：单信道条件下，B向A发送数据时，D要向暴露终端C发送数据。D的RTS会与B的数据在C处冲突，C收不到来自D的RTS，所以D也就收不到C的CTS，D就超时重发RTS。,暴露接收终端问题,10:04,30,暴露终端(Exposed Terminal)问题,事实上B 向 A 发送数据并不影响 C 向 D 发送数据。 而当C 检测到媒体上有信号，就不敢向 D 发送数据，所以就引入了不必要延迟。 暴露发送和接收终

14、端问题在单信道条件下使用握手机制都无法解决。,10:04,31,高空间复用度 避免报文间的冲突 提供冲突解决的方法 硬件无关性 Tip:可以将信道与公路联系：公路要容纳很多的车（空间复用），防止相撞，撞车了要可以进行处理，对上路的车无特殊要求。,信道接入协议应具备的特性,10:04,32,基于单信道的接入协议 基于双信道的接入协议 基于多信道的接入协议,信道接入协议的分类,10:04,33,用于只有一个共享信道的Ad Hoc网络。所有的控制报文和数据报文都在同一个信道上发送和接收。 目标：通过使用控制报文，尽量减少甚至消除数据报文的冲突， 即设计合适的冲突避免策略 典型的Ad Hoc单信道接入

15、协议：MACA MACAW IEEE802.11DCF FAMA系列 MACA-BI,基于单信道的接入协议,10:04,34,采用RTS-CTS握手机制 -隐终端：听到CTS没有听到RTS -暴露终端：听到RTS没有听到CTS 冲突解决采用BEB(Binary Exponential Backoff) 没有解决隐接收终端和暴露终端问题。,MACA(Multiple Acess Collision Avoidence),10:04,35,采用RTS-CTS-DS-DATA-ACK握手机制 -DS报文用于暴露终端确认自己身份。 -如果节点听到RTS但没有听到DS，说明RTS或CTS发生了 冲突，就

16、没有必要延迟发送。 -ACK用于LLC的确认，没有得到ACK确认的数据报文将会 被重发。 冲突解决采用MILD(Multiplicative Increase Linear Decrease)退避算法和退避计数器拷贝等技术取代BEB，实现公平接入。 也没能很好的解决隐终端和暴露终端问题。,MACAW(MACA for Wireless LAN),10:04,36,采用RTS-CTS-DATA-ACK报文交互机制。 -当数据报文较短时，可以直接采用DATA-ACK的简单报文交互以提高效率；当报文较长时为减少冲突使用RTS-CTS来预约信道。 -源于CSMA/CA，故节点发送前先监听信道，如果空闲

17、，等待一个DIFS，如果在此期间信道持续空闲，就开始发送报文；如果在此期间信道变忙，则执行退避算法。 -在下一次信道空闲持续DIFS时，节点开始以时隙为单位递减退避时间。递减到0，即发送报文；若在递减过程中信道又变忙，则冻结退避时间，待下次信道空闲持续DIFS后继续递减。,IEEE802.11DCF,10:04,37,一个描述一类无线信道接入协议的框架，这类协议在发送数据之前要先使用控制报文预约信道。 该协议允许一次RTS-CTS成功握手后连续发送多个数据报文，以提高信道利用率。 采用载波监听机制，并通过增加CTS控制报文的长度来消除隐发送终端的影响。,FAMA(Floor Acquisiti

18、on Multiple Acess),10:04,38,用于有两个共享信道的Ad Hoc网络。两个信道分别为控制信道和数据信道。 采用两个信道使控制报文和数据报文不会发生冲突。 在解决隐终端和暴露终端方面具有独特优势，通过适当的控制机制，可完全消除隐终端和暴露终端的影响，避免数据报文的冲突 典型的Ad Hoc双信道接入协议：BAPU DBTMA DCMA系列,双信道接入协议,10:04,39,1、解决隐接收终端问题，即告知发送者自己是隐终端，可以接收数据。A在给B发送数据时，D要向C发送报文。则D和C在控制信道上交换RTS和CTS，D然后用数据信道向C发送数据报文，不影响A向B的发送。,双信道

19、的优势,10:04,40,2、解决暴露发送终端的问题，暴露终端是可发送报文的。B向A发送数据时，C是暴露终端。C要向D 发送报文，则用控制信道与D进行RTS-CTS握手，然后C用数据信道向D发送数据报文而不影响B向A 的发送。,双信道的优势,10:04,41,3、解决暴露接收终端的问题：暴露终端是不可以接收数据的，所以要通知发送者自己是暴露终端，请延迟发送数据。B向A发送数据时，C是暴露终端。D要向C发送数据，C通过控制信道告知D自己是暴露终端，不可接受数据，D转而去处理其他任务，延迟发送，而不是像在单信道中因为得不到C的回应就不断的重发RTS。,双信道的优势,10:04,42,多信道接入协议

20、,用于具有多个信道的Ad Hoc网络，相邻节点可以使用不同的信道同时进行通信，接入控制更加灵活。 关注两个问题：信道分配和接入控制。 -信道分配：为不同的通信节点分配相应的信道，消除数据报文的 冲突，使尽量多的节点可以同时进行通信。 -接入控制：确定节点接入信道的时机、冲突的避免和解决。 典型的Ad Hoc多信道接入协议：多信道CSMA DCA-PC,10:04,43,设计目标：通过使用多信道减少隐终端问题的影响，减少数据报文的冲突。 采用准信道预留技术。 通过CDMA或FDMA将可用信道划分为N个子信道(N节点数)。 根据信号的强度和自己的载波监听门限判断信道的忙闲情况。 信道空闲的情况下，

21、优先选用上次使用的信道。,多信道CSMA,10:04,44,多信道的划分为什么不采用TDMA方式？ -在Ad Hoc网络中，全网范围内的同步问题比较难解决。,多信道CSMA,10:04,45,使用动态信道分配技术和功率控制技术。 目的：通过多信道尽量解决数据报文冲突问题，通过功率控制 减少报文冲突的概率并节省能量。 控制信道：RTS、CTS、RES 数据信道：数据报文、ACK 每个节点都保存三个数组：功率控制列表POWERI 信道使用状况列表CULI 空闲信道列表FCL,DCA-PC(Dynamic Channel Assignment with Power Control),10:04,46

22、,1、A要向B发送数据时，A检查CUL列表，用CUL列表和POWER列表构建FCL。如果B无法接受数据报文或无可用信道，A退避重发。 2、A向B发送RTS，其中包含FCL和将要发送的数据报文长度L。 3、B收到RTS，检查A发的FCL和自己的CUL和POWER列表，找到满足此次通信需要的信道Ro,计算向A发送需要的功率PA。构建CTS报文，将Ro和PA发送给A。并将接收机调整到信道Ro。 4、A收到CTS，将B和信道Ro添加入CUL，表明B在使用信道Ro。计算向B发送需要的功率PB。 5、A在控制信道上广播一个RES，其中包括信道Ro、退避时间、PB。 6、A在信道Ro上用功率PB将数据报文发

23、送给B。 7、B收到数据报文后，在信道Ro上用功率PA向A回送ACK。 8、其他节点收到A的RTS后退避一段时间，以防止与CTS冲突；收到B的CTS要更新自己的CUL列表，记录B在使用信道Ro和释放时间；收到A的RES，也更新自己的CUL列表 ，记录A在使用信道Ro和释放时间.,DCA-PC工作过程,10:04,47,二进制指数退避算法BEB 倍数增线性减算法MILD 退避计数器广播 计数值扩散的对策,信道接入协议的退避算法,10:04,48,BEB(Binary Exponential Backoff),10:04,49,MILD(Multiplicative Increase Linear

24、 Decrease),10:04,50,Ad Hoc 基本介绍及研究的主要问题 体系结构 信道接入协议 路由协议 分簇结构和算法（略） 节能问题 QoS保障（略）,Ad Hoc 网络,10:04,51,WLAN研究内容主要集中在物理层和数据链路层，为什么Ad Hoc网络要研究网络层？ -WLAN从网络层角度看是一个单跳的网络，分组处理不用通 过网络层。而Ad Hoc网络中，终端兼有主机和路由器功能， 作为路由器，终端需要运行相应的路由协议，根据路由协议 和路由表参与分组转发工作和路由维护工作。,路由协议,10:04,52,1、传统的路由协议都是基于固定网络设计的，都需要周期性的交换信息来维护正

25、确的路由表。周期性的交互开销大，而Ad Hoc网络的带宽较窄，能量有限。 2、传统的路由协议认为节点间的链路是对称的双向链路。而在Ad Hoc网络中，由于无线收/发设备的不同或周围环境对无线信道的影响，会造成单向的无线传输信道，即A和B能通信，B和C能通信，A和C不能直接通信，但也不一定能通过B的转发进行通信。,传统路由协议不适用于Ad Hoc网络的原因：,10:04,53,收敛迅速 提供无环路由 避免无穷计算 控制管理开销小 对终端要求小 支持单向信道 简单实用 支持节点休眠以节电 提供安全保护机制,Ad Hoc对路由协议的要求,10:04,54,端到端的数据吞吐量和时延 路由请求时间 路由

26、协议的效率 注意：不同的路由协议在不同的环境中，其性能的好坏有很大差异。 Ad Hoc组网环境主要涉及：网络规模大小(即节点个数的多少)、拓扑变化速度、节点移动速度、信道传输带宽、单向信道的比率和休眠节点的比率。,评价Ad Hoc网络路由协议的指标,10:04,55,按路由的驱动模式的不同，分为表驱动路由协议和按需驱动路由协议。 按网络拓扑结构的差异，分为平面结构路由协议和分簇路由协议,Ad Hoc路由协议的分类,10:04,56,又称为主动式的路由协议。每个节点实时维护一张或几张到网络中其他节点的路由信息表。在大规模和拓扑变化较快的环境中会占用过多的资源。 典型的表驱动路由协议：DSDVCG

27、SR WRP,表驱动路由协议(Table Driven Protocols),10:04,57,最大优点：解决了传统距离矢量路由协议中的无穷环路问题。 每个节点维护一张路由表，表项包括：目的节点、跳数、下一跳节点和目的节点序号。 只使用序列号最高的路由，如果序列号相同，选择最优的路由（如跳数最少）。 只能在给定的源和目的节点间提供单条路径。 协议中的参数：定时更新的周期、最大的“沉淀时间”和路由失效间隔时间。,DSDV(Destination-Sequenced Distance-Vector Routing),10:04,58,由目的节点分配，用于判别路由是否过时，并可防止路由环路的产生-每

28、次当目的节点的链路发生改变时，目的节点便会把自己的序列号加1。 当某一节点与其他节点建立新连接时，产生的新路由将采用新的序列号值，说明此路由比原来的路由新。 相邻节点间相互交换路由信息，首先检查序列号的大小，如果收到的路由记录的序列号比本节点保存的路由记录的序列号大，则更新。如果序列号大小相同，则比较路由的距离。如果小于本节点保存的路由记录的序列号，则不需更新。,DSDV目的序列号,10:04,59,路由表更新的两种方式： 1、全部更新(Full dump)：拓扑更新消息中将包括整个路 由表，主要应用于网络变化较快的情况。 2、部分更新(Incremental update)：更新消息中仅包含

29、 变化的路由部分，适用于网络变化较慢的情况。,DSDV(Destination-Sequenced Distance-Vector Routing),10:04,60,向每个邻居节点通告自己的路由信息 包括：目标地址 metric = 到目标的跳计数 目的地的序号 设置序列号的规则： 每次通告递增自己的目标序号（只用偶数值） 如果一个节点不再可达(timeout)，则将该节点的序号递增1(奇数值)并置metric = ,DSDV(Destination-Sequenced Distance-Vector Routing),10:04,61,一个实例：,DSDV(Destination-Sequ

30、enced Distance-Vector Routing),10:04,62,一个实例：,DSDV(Destination-Sequenced Distance-Vector Routing),10:04,63,DSDV(Destination-Sequenced Distance-Vector Routing),10:04,64,DSDV(Destination-Sequenced Distance-Vector Routing),10:04,65,存在的问题：1、节点维护准确的路由信息代价高； 2、有时候可能刚得到的路由马上就失效了。 主要用于网络规模不是很大，网络拓扑变化不频繁的环境。

31、 洪泛：节点在发送的报文头部携带目的节点地址，向其邻节点广播，中间节点收到报文后根据目的节点地址判断是转发报文还是接收报文。 洪泛的特点：简单。在网络拓扑变化频繁或路由发现维护的代价高时，洪泛可能比其他路由协议的效率更高。 洪泛的问题：网络中很多非目的节点参与了报文的转发， 网络耗费高。 在大多数Ad Hoc网络路由协议中，仅对控制报文采用洪泛方式，用于路由的发现过程。,DSDV(Destination-Sequenced Distance-Vector Routing),10:04,66,优点：-通过目的地赋予的序号值来防止出现路由回路 -不存在路由发现带来的延迟 缺点： -路由信息必须定期

32、更新 -即使网络拓扑没有变化也有通信开销 -维护的路由可能从来不用 -不能有节点睡眠,总结DSDV(Destination-Sequenced Distance-Vector Routing),10:04,67,又称为反应式路由协议。节点平时不实时维护网络路由，只在有数据要发送时，才进行寻路。 典型的按需路由驱动协议：AODV DSR LMR TORA ABR SSR 按需路由是Ad Hoc网络路由协议区别于常规路由协议的一个重要特征。,按需驱动路由协议(Source-Iniciated On-Demand Protocols),10:04,68,按需路由协议路由发现过程,当节点1有数据要向节

33、点8发送且无路由时，节点1启动路由发现过程： 节点1向其邻节点（2、3、4）发送路由请求消息； 中间节点转发路由请求消息至目的节点8； 目的节点选择合适的路由返回路由响应消息，该消息中携带了从节点1到节点8的完整路由。,10:04,69,主要由路由发现和路由维护两部分组成。 -路由发现：用于帮助源节点获得到达目的节点的路由。 -路由维护：检测当前路由的可用情况，当检测到路由故障 时，将调用新一轮的路由发现过程。 DSR要解决的核心问题： 如何能够知道到达目的节点的路由？,DSR(Dynamic Source Routing),10:04,70,1、源节点首先向其邻节点广播路由请求报文，即RRE

34、Q报文。报文中包括：目的节点地址、路由记录、请求ID等字段。 -路由记录：用来记录从源节点到目的节点路由中的中间节点地 址，该字段中的所有节点地址即构成了从源到目的的路由。 -请求ID：由源节点管理。 2、中间节点维护 序列对列表，该序列对用于唯一标识一个路由请求报文，以防止收到重复的路由请求。,DSR路由发现,10:04,71,1、如果路由请求报文的 存在于本节点的序列对列表中，表明该请求报文已经收到过，节点不用处理该请求；否则转至步骤2; 2、如果本节点的地址已经在路由记录字段中存在，节点不用处理该请求；否则转至步骤3; 3、如果请求报文的目的节点就是本节点，则路由记录节点中的节点地址序列

35、构成了从源节点到目的节点的路由。本节点向源节点发送“路由响应（Route Reply）”报文，即RREP报文，同时将该路由拷贝到RREP报文中；否则转至步骤4; 4、该节点是普通的中间节点，将该节点地址附加在报文的“路由记录”字段后，同时向邻节点广播该路由请求。 通过上述处理，路由请求报文将最终达到目的节点。,DSR路由发现中间节点的处理：,10:04,72,假若节点a已经收到节点S的路由请求，则不再处理节点b的路由请求。 节点D可能会同时收到节点c和d的路由请求消息，造成消息碰撞，反而收不到正确的路由请求。可采用节点随机延时发送来避免上述情况。 目的节点D根据收到的源节点 RREQ 报文回送

36、 RREP 报文。,DSR路由发现,10:04,73,DSR路由响应,目的节点在将 RREP 报文转发到源节点时，需考虑下述几种情况： 1、 目的节点有到达源节点的路由。此时目的节点可直接用该路由回送 RREP。,10:04,74,DSR路由响应,2、如果目的节点没有到源节点的路由，此时需要考虑节点通信信道问题： (a) 如果网络中所有节点间的通信信道是对称的，此时目的节点到源节点的路由即为源节点到目的节点的反向路由；(b) 如果信道是非对称的，目的节点就需要发起到源节点的路由请求过程，同时将路由 RREP 报文携带在新的 RREQ中,10:04,75,传统的路由协议中通过周期性广播路由更新消

37、息将路由发现和路由维护过程合二为一。而在DSR协议中，由于没有这种周期性的广播，节点必须通过路由维护过程来检测路由的可用性. 按照路由检测方法的不同，可以将路由维护分为以下两种：点到点证实机制和端到端证实机制。,DSR路由维护,10:04,76,又称逐跳证实机制。 相邻节点通过数据链路层的消息证实或者高层应用层之间的消息证实机制，来检测路由中各邻节点的可达性。 当发现节点间的传输故障，即路由不再有效时，向上级节点发送“路由差错”报文（RERR），收到路由差错报文的节点根据此信息将该路由从本节点的路由缓冲区中删除。,DSR路由维护点到点证实机制,10:04,77,通过端到端的证实机制可以检测整个

38、路由的有效性。 但是，当路由发生故障时，该机制无法确定故障发生的位置，即究竟是在哪个节点处发生了故障。,DSR路由维护端到端证实机制,10:04,78,由于各节点能够听到相邻节点发出的所有报文，包括路由请求，路由响应等。这些报文中携带了一些路由信息，节点通过缓存这些路由信息，可以尽量减少每次每次发送新报文时启动的路由发现过程，提高系统的效率。,DSR路由缓冲,10:04,79,节点S通过发起目的节点为D的路由请求过程，获得路由S-a-c-D，同时节点S也获得了到达该路由中其他节点的路由。 同时，中间节点在收到源节点的路由请求时，如果本节点路由缓冲区中有到目的节点的路由，可以直接回复路由响应消息

39、。如节点b在发起到D的路由请求时，当报文到达节点a时，若a中有缓冲路由a-c-D，a可以直接回复路由响应b-a-c-D。,DSR路由缓冲,10:04,80,DSR路由协议的优点,仅在需要通信的节点间维护路由，减少了路由维护的代价。 采用路由缓冲技术可进一步降低路由发现的代价。 由于采用了路由缓冲技术，因此在一次路由的发现过程中，会产生多种达到目的节点的路径。 支持非对称传输信道模式。,10:04,81,1、由于采用源节点路由，每个数据报文的头部都要携带路由信息，增加了报文长度。 2、用于路由发现的控制信息可能会波及全网各节点，造成一定的耗费。 解决方案：通过控制路由发现报文的传输距离减少耗费。

40、若本轮路由发现失败，则在后续的路由发现过程中再加大传输距离。,DSR路由协议的问题与不足,10:04,82,3、“路由响应风暴”问题。由于采用路由缓冲技术，中间节点根据自己的缓冲路由，对路由请求直接回答，源节点会同时收到多个路由响应，造成路由响应信息之间的竞争。 解决方案：中间节点同时监听邻节点的路由响应报文，发现该路由比自己的路由更短时，就不再发送本节点的路由响应报文。,DSR路由协议的问题与不足,10:04,83,4、 “脏”缓冲路由对其他节点的影响。如果中间节点的路由缓冲记录已经过时，当该节点根据缓冲路由回复路由请求时，其他监听到此“脏”路由的节点会更改自己的缓冲路由记录，造成“脏”缓冲

41、路由的污染传播。 解决方案：为缓冲路由设定有效期，超过有效期的路由将被认为无效，将其从缓冲区中删除。,DSR路由协议的问题与不足,10:04,84,表驱动和按需驱动路由协议比较,10:04,85,群首信关切换路由协议（Clusterhead Gateway Switch Routing） 无线路由协议（The Wireless Routing Protocol） 自组织网按需距离矢量路由协议（Ad Hoc On-Demand Distance Vector Routing） 临时排序路由算法（Temporally-Ordered Routing Algorithm） 基于联合的路由协议（Ass

42、ociativity-Based Routing） 信号稳定性路由协议（Signal Stability Routing）,其他路由协议简介,10:04,86,CSGR是有几种路由选择方式的分群的多跳移动无线网络。 通过群首控制网络节点，信关隔离群，信道接入可以分配路由和带宽。 -群首选择算法：选择一个节点作为群首并在群内应用分布式算法。 -信关：那些在两个或多个群首的通信半径之内的节点。 节点发送数据包首先把它传送到群首，通过信关到另一个群首，一直重复此过程直到目的节点所在群的群首收到此数据包。然后，数据被传送到目的节点。 每个节点必须保存一个群成员表和路由选择表。 群首方式的缺陷在于当群首

43、频繁的变换时，节点忙于选择群首而不是数据转发，这样反而会影响路由协议的实行。因此，当群内成员发生变化时，产生了最小群变化协议（Least Cluster Change）。利用LCC，只有当一个群内有两个群首或一个节点在所有的群首通信范围之外时，群首才发生变换。 TIPS: 类似于簇！,群首信关切换路由协议（CGSR）,10:04,87,WRP是以维护网络中所有节点间的路由信息为目的的基于表的协议。 每一个节点都需保存距离表、路由表、链路开销表以及信息转发表。 节点通过更新分组告知其它节点链路的变化状况，通过接收相邻节点的确认分组以及其它信息来获知其它节点的情况。在WRP中，节点为网络中的每一个

44、目的节点交流距离和下一跳到最后一跳的路由信息。 WRP属于有特殊例外的路径搜寻算法。它通过强迫每一节点检查所有相邻节点发送的信息记录来避免无穷计（count-to-infinity）问题。这最终会消除环路现象和当链路断开时提供更快的路由收敛。,无线路由协议（The Wireless Routing Protocol）,10:04,88,AODV实质上就是DSR和DSDV的综合，它借用了DSR中路由发现和路由维护的基础程序以及DSDV中跳到跳的路由选择、序列号码及周期性的更新信息的用法。 和DSDV保存完整的路由表不同的是，AODV通过建立基于按需的路由来减少路由广播的次数，这是AODV对DSD

45、V的重要改进。 和DSR相比，AODV的好处在于源路由并不需包括在每一个数据包中，这样会使路由协议的开销有所降低。 AODV是一个纯粹的按需路由系统，那些不在路径内的节点不保存路由信息也不参与路由表的交换。,自组织网按需距离矢量路由协议(AODV),10:04,89,TORA是基于逆向连接概念的高度自适应、环路开放、分布式路由算法。 主要应用在动态移动网络环境内。 它是源始发的路由协议，能向每一对源-目的节点提供多条路由。 关键思想：把路由信息的传送限制在网络拓扑结构变化处附近 较小的范围内。 为了实现这一点，节点必需保留一跳之远的节点的路由信息。 TORA主要实现三个基本功能：路由建立、路由

46、维护、路由删除。 在路由建立和路由维护的过程中，节点应用高度、 跳数来建立一个以目的节点为根部的指导性的非循环的图表。这样链路根据相邻两个节点的高度值来确定向上或向下的方向。,临时排序路由算法（TORA）,10:04,90,ABR协议是环路开放的、分组复用的，它为自组织网定义一个新的度量（metric）。 -metric：联合稳定性程度。 路由的选择基于节点的联合稳定性程度。节点周期性地发送信标来表明自身的情况。一旦相邻节点收到信标，它们的联合路由表就会被更新。每接收一个信标，节点就增加一个关于发送信标的节点的联合条目。 联合稳定性通过节点和其它节点在时间和空间的连接稳定性来定义。高联合稳定性

47、也许意味着节点的低移动率，而低稳定性意味着高移动率。当节点的相邻节点或节点本身移动出相邻的范围时，联合条目会被刷新。 ABR的基本目标是为自组织网找出生命时间更长的路由。,基于联合的路由协议（Associativity-Based Routing）,10:04,91,SSR是基于自适应路由协议的按需路由协议。SSR选择路由是基于节点间信号的强度以及节点位置的稳定性。 这种路由选择标准有选择强连接性路由的作用。 SSR可分成两部分:DRP动态路由协议和SRP静态路由协议。 DRP(Dynamic Routing Protocol)主要负责路由表和信号稳定程度表的维护。所有的传送过程及接收都在DRP进行。 SRP (Static Routing Protocol)负责处理节点接收的数据。,信号稳定性路由协议（Signal Stability Routing）,10:04,92,Ad Hoc 基本介绍及研究的主要问题 体系结构 信道接入协议 路由协议 分簇结构和算法（略） 节能问题 QoS保障（略）,Ad Hoc 网络,10:04,93,这里主要针对节点通信子系统的无线收发部分，探讨如何通过设计不同的软件协议达到节能。 当然，也可以从硬件实现，如提高电池容量、低功耗CMOS器件的设计、低功耗显示技术、磁盘驱动器的节能算法、低功耗I/O设备、低功耗CPU