[高等教育]10-自组织移动网络.ppt

中科院计算所 授课教师：鲁士文 2006.3.1,1,中科院计算所网络课程 10-自组织移动网络,中科院计算所 授课教师：鲁士文 2006.3.1,2,第十单元 自组织移动网络,10.1 什么是ad hoc无线网络？ 10.2 Ad hoc移动网络面临的挑战 10.3 Ad hoc无线介质访问协议 10.3.1 MACA-BI协议 10.3.2 PAMAS协议 10.3.3 DBTMA协议 10.3.4 MARCH协议 10.4 Ad hoc按需距离向量路由选择 10.5 基于关联的长活路由选择,中科院计算所 授课教师：鲁士文 2006.3.1,3,10.1 什么是ad hoc无线网络？,Ad hoc无线网络是一个有两个或更多个具有无线通信和网络连接能力的设备的集合。这些设备都可以跟在它们的无线范围内的另一个节点直接通信，或者也可以跟它们的无线范围之外的节点通信。在后者的情况下使用一个中间节点把分组从源向着目的地中继或转发。 Ad hoc网络是自组织的和自适应的。这就意味着所形成的网络可以动态地重构而不需要任何系统管理。术语“Ad hoc”意味着“可以取不同的形式”，并且“可以是移动的、独立的或连网的”。Ad hoc节点或设备应该能够检测到其它同类设备的存在，并执行必要的握手过程，以便允许通信和共享信息和服务。,中科院计算所 授课教师：鲁士文 2006.3.1,4,10.1 什么是ad hoc无线网络？,由于Ad hoc无线设备可以取不同的形式，例如掌上电脑、笔记本和因特网电话等，设备的计算、存储和通信能力可能差别很大。Ad hoc设备应该不但能够发现跟邻接设备或节点的连接性的存在，而且能够识别这些设备的类型以及它们对应的属性。由于一个Ad hoc无线网络不依赖任何固定的网络实体，它本身基本上就是一个无基础的网络。不必有固定的基站，没有导线，也没有固定的路由器。然而，由于存在移动性，必须交换路由信息以反映链路连接性的变化。 Ad hoc移动设备的多样性还意味着它们的电池容量的差别。由于Ad hoc网络的节点需要对由其它节点发送的数据分组进行转发，功耗就成了关键的问题。,中科院计算所 授课教师：鲁士文 2006.3.1,5,10.1 什么是ad hoc无线网络？,一个Ad hoc移动设备作为服务器或服务提供者的能力跟它的计算能力、内存和外存容量以及电池寿命有关。这就意味着在网络中的一些设备比其它设备功能强；一些设备可以是服务器，其它设备只能是客户机。此外，为其它节点中继分组会消耗自己的能量，因此，一个移动节点在承诺为其它节点转发分组之前应该考虑自己的生存条件。 无线传感器网络是一种形式的Ad hoc无线网络。传感器通过无线连接，它们在适当的时候把信息中继到某些选定的节点。这些选定的节点再执行一些基于所收集的数据的计算（通过一个通常称作数据融合的进程），从而得到最终的统计数据（它们反映出对环境和战术条件的评估），允许做出关键的决策。,中科院计算所 授课教师：鲁士文 2006.3.1,6,10.1 什么是ad hoc无线网络？,有多种多样的传感器，包括声的、地震的、图像的、热能的、方位的和温度传感器。这些传感器的建立需要高度集成的电子学，比如微电子机械系统MEMS。这些无线传感器网络的实现面临着一系列的挑战，主要包括： (a)设备制造； (b)电源生命保持； (c)能量高效利用的协议； (d)分布式计算； (e)规模可伸展性； (f)数据传播通路的产生； (g)安全性。,中科院计算所 授课教师：鲁士文 2006.3.1,7,10.1 什么是ad hoc无线网络？,无线传感器网络的设计面向低的数据吞吐率（一般不超过512位/秒，可以低到1位/秒或更低）、大的报文延迟（数秒甚至数分钟的延迟都是可以接受的，通常禁止传送视频和音频数据）、低成本、低功耗和自组织的拓扑结构。它的许多应用都不需要移动性。为了降低网络设备的成本，安全特征必须能够用廉价的硬件实现。低的逻辑门数量、受限的存储器容量和少的可执行指令的条数限制了可以采用的安全算法的类型。无线传感器网络还有一些其他方面的需求，包括网络规模可扩展性（设备轻小，但数量可能很大，如仓库或超市的物品传感部件）、标准化引导的规模生产、容错以及对各种恶劣环境的适应性。 一个无线ad hoc传感器网络用较低的数据吞吐率和较大的报文延迟换取较低的成本和较少的电源功耗。主要目标是设计满足需求的物理层、数据链路层和网络层的通信协议。,中科院计算所 授课教师：鲁士文 2006.3.1,8,10.1 什么是ad hoc无线网络？,无线ad hoc传感器网络的设备可以是固定的、可携带的和移动的，网络提供低数据速率的无线连接。位置感知性被认为是它的颇具特色的能力。 无线ad hoc传感器网络的典型应用有库存管理、工业监控、保安系统、智能农业以及家庭消费电子产品。无线传感器节点将被放置在天花板上、工矿企业的设备里、农场中、战场上以及家用电器内等地方。它们以最少的人工干预执行物体定位、危险感知和环境监控等功能。成功的关键是提供轻小的低成本的节点，更重要地，节点必须只消耗超低的功率，以避免频繁的电池更换。 我们在本单元中重点讨论无线移动ad hoc 网络。,中科院计算所 授课教师：鲁士文 2006.3.1,9,10.1 什么是ad hoc无线网络？,在一个Ad hoc移动网络中的移动主机可以跟它的直接对等方通信，即仅限于单个无线跳段。然而如果有3个或更多个节点都在可通信的范围内（但互相不必是单个跳段的路程），那么就是远程到远程的移动节点通信。在典型的情况下，远程到远程通信跟成组迁移有关。不同类型的Ad hoc通信产生不同的交通特征。 一个Ad hoc路由包含源（SRC）、目的地（DEST）和可能的若干个中间节点（IN）。这些节点中任意一个的移动都可能影响路由的有效性。路由中的源节点有一个下行链路，当它移动出下行邻居的无线覆盖范围的时候，现有的路由会立即变得无效。因此，所有的下游节点必须得到通知，它们才可能删除它们的无效路由表项。同样地，当一个目的地节点移动出它的上游邻居的无线覆盖范围的时候，该路由也将变得无效。在这里，上游节点必须得到通知，它们才能够删除它们的无效路由表项。最后，一个支持现有路由的中间节点的移动也可能使得该路由变得无效。,中科院计算所 授课教师：鲁士文 2006.3.1,10,10.1 什么是ad hoc无线网络？,所有这些移动都使得许多常规的分布式路由协议对链路变化做出响应，其结果是更新网络内所有的其余节点，以保持路由信息的一致性。然而，更新过程涉及在无线介质上的广播，引起带宽浪费和总的网络控制交通的增加。因此，Ad hoc网络需要新的路由协议。 除了上述移动类型之外，在两个移动子网之间的执行子网-桥接功能的节点的移动可能把移动子网分割成更小的子网。一个移动子网的性质说明，如果源和目的节点都是该子网的成分，那么应该存在一条或多条路由，除非该子网被某个子网-桥接移动节点分区了。另一方面，某些节点的移动可能引起子网的合并，形成更大的子网。,中科院计算所 授课教师：鲁士文 2006.3.1,11,10.1 什么是ad hoc无线网络？,当移动子网合并形成更大的子网时，路由算法可以通过更新所有节点的路由表来接受新的子网。然而，这是非常低效的。有效的路由机制应该放弃这一过程，并且选择只更新受到影响的节点的相关路由表，这已是移动节点的无线数据链路层功能的一个固有的部分。 从应用的角度看问题，可以使用移动子网支持漫游合作计算。当两个合作组聚和，或者当新的用户通过进入无线范围加入时，合作成员在规模上可能增大。 在现实中，可能存在源、目的地和中间节点的并发移动，因此在调用多重的路由重构或修正过程时，需要有一些规则来保证一致性。如果所执行的路由重构是适当的，这些过程最终应该收敛。,中科院计算所 授课教师：鲁士文 2006.3.1,12,10.2 Ad hoc移动网络面临的挑战,大多数的实验Ad hoc网络是基于ISM频段。为了防止干扰，Ad hoc网络必须在某些允许的或指定的频谱范围上运行。大多数微波炉运行在2.4GHz频带，因此可能会干扰无线LAN系统。频谱不仅被严格地控制和分配，而且也需要购买。可以动态建立和拆除的Ad hoc网络，还不清楚谁应该为这个频谱付费。 跟蜂窝网络不同，在Ad hoc无线网络中没有中心控制和全局同步。因此，TDMA和FDMA机制在这里不适用。此外，现有的许多MAC协议都不处理主机移动性。这样，为了支持QoS，对于帧的调度和即时发送是困难的。,中科院计算所 授课教师：鲁士文 2006.3.1,13,10.2 Ad hoc移动网络面临的挑战,在一个Ad hoc无线网络中，由于同一个介质被多个移动Ad hoc节点共享，对于该共享通道的访问必须通过一种MAC协议以分布式的方式进行。在没有静态节点的情况下，各个节点不能够依赖一个中心的协调进程。MAC协议必须竞争对共享通道的访问，同时要避免跟邻居节点的可能的冲突。在为Ad hoc无线网络设计MAC协议的时候，必须考虑移动性、隐藏终端和暴露终端的问题。 在微电子学方面的进展使得制造小的可携带的高度集成的移动设备成为可能，因此Ad hoc网络的节点可以比较自由地移动，产生动态的拓扑改变。现有的距离向量和链路状态路由协议不能够适应在Ad hoc无线网络中频繁的链路改变，使用它们会导致差的路由收敛和非常低的通信吞吐量。显然我们需要为Ad hoc移动网络设计新的路由协议。,中科院计算所 授课教师：鲁士文 2006.3.1,14,10.2 Ad hoc移动网络面临的挑战,Internet用户数目爆炸性增长的部分原因是视频和声频会议一类应用的引入。这类多方参与的通信通过采用组播路由协议而成为可能。组播主干试验网络（MBone）互连多个能够把组播分组隧道通过非组播路由器传送的组播路由器。一些组播协议使用广播和剪枝的方法建立以源为根的组播树。其它的组播协议使用公用的核心节点作为组播树的根。所有这些方法都基于这样的事实，即路由器是静态的；一旦形成了组播树，树节点不会移动。然而，Ad hoc移动网络不是这样的情况。 大多数现有的网络协议不太考虑功率消耗的问题，因为它们假定存在着静态的主机和路由器，可以由有线电网供电。然而，今天的移动设备主要由电池供电。电池技术依然落后于微处理器技术。锂离子电池仅能维持2-3小时。这样的设备运行时间限制意味着需要节约使用电能。特别地，对于一个Ad hoc移动网络，移动设备必须同时执行端点系统（执行用户交互操作和运行应用程序）和中间系统（执行分组转发）的功能。为其它节点转发分组需要消耗功率，这在Ad hoc无线网中可能是相当显著的。,中科院计算所 授课教师：鲁士文 2006.3.1,15,10.2 Ad hoc移动网络面临的挑战,在当前的Internet上，TCP依赖对来回路程时间（RTT）和分组丢失的测量得出网络中是否发生了拥塞的判断。不幸的是，TCP不能够对移动性的存在和网络拥塞加以区别。在一条连接上的节点移动可能引起分组丢失和长的RTT。因此，需要对TCP做一些增强或改进，保证传输协议能够执行适当，不影响端到端的通信吞吐量。 传统的客户/服务器RPC（远地过程调用）过程是否适用于Ad hoc网络？Ad hoc网络包含异种设备和机器，并非每一个节点都能担当服务器的角色。由客户机发起、请求服务器执行，然后等待返回结果的概念在带宽和功率都受限的条件下是没有吸引力的。也许在移动代理中做远地编程的概念更为可取，因为这样可以减少在无线介质上于客户和服务器之间交换的信息量。另外，在Ad hoc网络中移动设备如何访问一个远程的服务？一个设备如何向网络中的其它成员通告它愿意提供的服务？所有这些问题都需要认真研究。,中科院计算所 授课教师：鲁士文 2006.3.1,16,10.2 Ad hoc移动网络面临的挑战,Ad hoc网络是内部网，除非它们连到了Internet。不在本地区的黑客攻击不了这样的网络。但当Ad hoc网络跟有线网络连接的时候情况就不同了。通过对邻接节点的身份验证，用户可以知道邻居用户是友善的，还是敌意的。在一条Ad hoc路径上传送的信息可以用某种方式进行保护，但是可能有许多个节点参与传输或转发，必须通过对分组源发方的识别使用流ID或标记对分组中继进行身份验证。,中科院计算所 授课教师：鲁士文 2006.3.1,17,10.2 Ad hoc移动网络面临的挑战,综上所述，Ad hoc网络需要具有自我组织的特征，它们必须执行路由和分组转发功能。Ad hoc无线网络的拓扑是动态改变的，因为随着时间变化，设备并不固定在特定的位置。节点非静止的事实意味着不宜采用中心的介质访问控制机制。在Ad hoc网络中的路由协议需要处理节点的移动性和电源及带宽的限制条件。在Ad hoc无线网络中的组播需要是高效率的，使用洪泛则会引起对可用带宽的大量消耗，并降低电池的使用寿命。Ad hoc设备依靠电池运行，通信协议的低效率会显著地缩短这些设备的运行时间。现在的传输协议不是为无线Ad hoc网络设计的，特别地，TCP是一个端到端的协议，它不能够区分移动性和拥塞。最后，需要有新的方法来设计Ad hoc无线网络中的服务定位、服务提供和服务访问。总之，有许多具有挑战性的问题需要我们去解决。,中科院计算所 授课教师：鲁士文 2006.3.1,18,10.3 Ad hoc无线介质访问协议,无线MAC协议是一套规则或过程，它允许对无线共享介质的有效利用。我们把节点定义成试图访问介质的主机。发送方是一个试图在介质上发送的节点，接收方是当前传输的接收者。MAC协议涉及每条链路的通信，但不是端到端的。 在同步的MAC协议中，所有节点都同步到同一时钟。这是通过由一个时间主站定期广播信标实现的。所有的节点都倾听这个信标，并把它们的时钟同步到主站的时间，因此需要有中心的协调机制来同步时间事件。,中科院计算所 授课教师：鲁士文 2006.3.1,19,10.3 Ad hoc无线介质访问协议,在异步的MAC协议中，节点不必跟从同样的时钟，而是使用分布式控制机制协调对通道的访问。因此，对通道的访问倾向于采用基于竞争的机制。 按照通信起始者的不同，无线MAC协议还可以分为接收方起始的MAC协议和发送方起始的MAC协议。在接收方起始的MAC协议中，接收方必须首先联系发送方，通知发送方它已经准备好接收数据。实际上，这是一种形式的轮询。因为接收方不知道发送方是否确实有数据要发送。这也是一种被动形式的通信起始，因为发送方不必发起一个请求。此外，该通信方式只需要使用一个控制报文，而在RTS-CTS方式中则需要使用两个控制报文。,中科院计算所 授课教师：鲁士文 2006.3.1,20,10.3 Ad hoc无线介质访问协议,在发送方起始的MAC协议中，首先由发送方通知接收方它有数据要发送。MACA（带冲突避免的多路访问）就是一个由发送方起始的MAC协议。发送方节点给接收方节点发送一个明确的RTS报文，表示它通信的意愿。随后接收方节点对该报文予以应答，说明它是否愿意接收来自发送节点的数据。如果愿意，它就给发送节点返回一个CTS报文。接着，发送方就开始发送数据。下面介绍现有的主要的Ad hoc MAC协议。,中科院计算所 授课教师：鲁士文 2006.3.1,21,10.3.1 MACA-BI协议,带邀请的MACA协议（MACA By Invitation）是对经典的三次握手MAC协议的一种改变。如图10-1所示，MACA-BI仅使用两次握手。没有RTS，取而代之的是RTR(准备好接收)。在MACA-BI中，一个节点在收到邀请后才能够发送数据。值得注意的是，接收节点不必知道源是否有数据要发送。因此接收方需要预测该源节点是否有数据要给它发送。邀请的时机会影响通信的性能。,中科院计算所 授课教师：鲁士文 2006.3.1,22,10.3.1 MACA-BI协议,中科院计算所 授课教师：鲁士文 2006.3.1,23,10.3.1 MACA-BI协议,一般说来，可以使用在源节点的分组队列长度和到达速率作为调整邀请发送的依据。实现这一方法的一种可能的途径是通过捎带在源发给接收方每个分组中的信息，让接收方知道发送方的上述状态。因此，对于恒定位速率（CBR）交通，MACA-BI的效率比较高，因为预测机制可以工作得很好。然而，对于突发性交通，MACA-BI的性能可能不会比MACA好。 在非稳定交通的条件下，为了增强MACA-BI的通信性能，一个节点在其队列长度或分组延迟超过某个可以接受的门槛值时，在RTR(准备好接收)被传输之前，该发送方仍然可以发送一个RTS。这就意味着MACA-BI现在又返回到了MACA。图10-2示出了在MACA和MACA-BI之间的差别。,中科院计算所 授课教师：鲁士文 2006.3.1,24,10.3.1 MACA-BI协议,中科院计算所 授课教师：鲁士文 2006.3.1,25,10.3.1 MACA-BI协议,总之，MACA-BI减少了发送/接收轮换的时间。在MACA中，每一次传送应该延迟一个从发送到接收的轮换时间（最高达25微秒），以允许先前的发送方转变为接收方式。因为MACA-BI仅使用单个控制报文，所以减少了轮换限制。此外，MACA-BI中保留了MACA的功能，包括MACA的无冲突特征。事实上，MACA-BI发生控制分组冲突的可能性是比较小的，因为跟MACA相比，它只使用了一半的控制分组数量。,中科院计算所 授课教师：鲁士文 2006.3.1,26,10.3.2 PAMAS协议,用于Ad hoc网络的感知功率的带信令的多路访问协议（Power-Aware Multi-Access Protocol with Signaling）是基于MACA协议，但增加了分立的信令通道。RTS-CTS对话就发生在这个通道上。PAMAS通过有选择地关闭不在发送或接收分组的设备的电源来节约使用电池能量。 当节点A要给节点B发送数据时，它首先发送一个RTS报文，并且进入等待CTS状态。如果CTS报文没有到达，节点A就进入二进制指数后退状态，并在随后尝试再发送RTS。如果CTS报文到达了，节点A就进入数据传输状态。对于接收节点B说来，在发送CTS报文的时候，它就进入了等待数据状态。如果数据确实开始到达了，节点B就开始在信令通道上发送忙音，进入接收数据状态。（共有两个通道：数据和信令，后者包括控制和忙音）。,中科院计算所 授课教师：鲁士文 2006.3.1,27,10.3.2 PAMAS协议,在PAMAS中，如果节点听到不是指向它们的传输，就把自己关闭。每个节点独立地决定是否关闭自己的发射器。迫使一个节点关电的条件包括： （a）如果一个节点没有分组要发送，那么在它的一个邻接节点正在发送的情况下，它应该关电； （b）如果一个节点有分组要发送，但当至少有一个邻接节点在发送、另一个节点在接收的情况下，它应该关闭自己的收发器。,中科院计算所 授课教师：鲁士文 2006.3.1,28,10.3.2 PAMAS协议,注意，当一个节点的收发器关电时，它既不能接收，也不能发送。应该使用探测装置来发现什么时候一个节点应该开电。关电时间长度是很关键的，因为它影响延迟和吞吐量性能指标。此外，一个节点仅可以有选择地关闭它的数据接口，并且让信令接口继续加电工作。,中科院计算所 授课教师：鲁士文 2006.3.1,29,10.3.3 DBTMA协议,双忙音多路访问（DBTMA）协议是把忙音多路访问（BTMA）的概念用于Ad hoc无线网络。忙音多路访问（BTMA）可以解决隐藏终端的问题。然而BTMA依赖于无线最后一跳的网络结构，在这里有一个中心基站服务于多个移动主机。当基站从一个特定的移动主机接收分组的时候，它给无线单元内的所有其它节点发送一个忙音信号。因此，隐藏终端感知到忙音，并且抑制其发射。 在双忙音多路访问（DBTMA）协议中使用两个带外忙音通知邻接节点将要进行的传输。此外，单个共享通道被划分（时分）成数据通道和控制通道。数据分组在数据通道上发送，控制分组（例如RTS和CTS）在控制通道上发送。特别地，一个忙音标示发送忙，另一个忙音标示接收忙。这两个忙音在频率上是分隔的，因此可以避免干扰。(共有三个通道：数据和控制共享一个通道、两个忙音信道)。,中科院计算所 授课教师：鲁士文 2006.3.1,30,10.3.3 DBTMA协议,中科院计算所 授课教师：鲁士文 2006.3.1,31,10.3.3 DBTMA协议,双忙音多路访问（DBTMA）的操作原理相对简单。要发送的Ad hoc节点首先发出一个RTS报文。当接收节点接收到这个报文，确定它已经准备好并且愿意接受数据时，它发出一个接收忙音报文，后随一个CTS报文。所有听到接收忙音的邻接节点都被禁止发送。在接收到CTS报文时，源节点给周围节点发出一个忙音报文后再发送数据。听到发送忙音的邻接节点被禁止发送，并且忽略接收到的任何传输。分析和试验表明，DBTMA在性能方面要优于RTS-CTS MAC机制。,中科院计算所 授课教师：鲁士文 2006.3.1,32,10.3.4 MARCH协议,在PAMAS(感知功率的带信令的多路访问)中我们看到，监听可能导致不必要的功率消耗。此外，今天的大多数无线站点都使用全向天线。有一个新的MAC协议，它在采用全向天线的Ad hoc移动网络中利用了监听特征。这就是采用简化握手过程的介质访问协议MARCH(Media Access with Reduced Handshake)。 如图10-4所示，MARCH通过减少控制开销量改善了无线多跳Ad hoc网络的通信吞吐量。跟其它接收方启动的协议不同，MARCH的运行不采用交通预测机制。事实上，MARCH是利用全向天线的广播特征来减少所需要的握手次数。在MARCH中，一个节点从收到的另一个节点发出的CTS分组得知在其邻接节点数据分组的到达。然后它可以使用自己的CTS发起一个中继数据的邀请。,中科院计算所 授课教师：鲁士文 2006.3.1,33,10.3.4 MARCH协议,中科院计算所 授课教师：鲁士文 2006.3.1,34,10.3.4 MARCH协议,图10-4示出了全向天线的广播特征。节点C收到节点B发送的CTS1报文。这个特征意味着，听到的CTS1分组也可以用来向节点C传达数据分组到达节点B的信息。接着，在数据分组被节点B接收以后，节点C可以通过CTS2分组邀请节点B转发那个数据。 图10-4还说明，在第一跳之后RTS-CTS握手过程现在被简化成单个CTS(CTS Only)，控制开销的减少量是路由长度的函数。对于一个L跳的Ad hoc路由，从源发送一个数据分组到目的地所需要的握手次数，在MACA中是2L，在MACA-BI中是L，在MARCH中是（L+1）。因此，当L比较大时，MARCH将有跟MACA-BI类似的握手次数。,中科院计算所 授课教师：鲁士文 2006.3.1,35,10.3.4 MARCH协议,MARCH可以看成是一种先请求后拖拉的协议，因为在通路中的后随节点只需发送邀请，就可以把数据拉向目的节点。在MARCH中的RTS-CTS报文包含： *发送方和接收方的MAC地址； *路由标识号（RTID）。 图10-5进一步地示出了MARCH的操作。有两条在公共节点C交叉的路由，路由1由节点A、B、C和D构成，而路由2由节点Y、C和Z构成。这些路由可以通过适当的路由协议建立。在基于关联的路由选择中，通过在路径上的各个节点中建立路由登记项发现和激活所需要的路由。在路由发现阶段广播分组。当进入数据通信阶段时，在路径上的节点使用诸如MARCH这样的基础协议。,中科院计算所 授课教师：鲁士文 2006.3.1,36,10.3.4 MARCH协议,中科院计算所 授课教师：鲁士文 2006.3.1,37,10.3.4 MARCH协议,为了开始在路径1上的数据传输，先从节点A往节点B发送一个RTS1。如果这个分组被节点B成功接收，节点B将用一个CTS1分组应答，以准许数据传输。同时，节点C也听到了CTS1。根据MAC地址和RTID，节点C知道由它的上游节点B发送的分组在路径1上。然后节点C调用一个定时器Tw, Tw的值设置成足够B接收和处理新的数据分组，在超时的时候如果通道空闲，节点C给节点B发送一个CTS2分组来获得该数据分组。类似地，节点D听到由节点C发送的CTS2，并且随后通过CTS3在D设置的Tw超时的时候邀请节点C中继这个数据分组。值得注意的是，作为路径2上的节点C的下游节点，节点Z也听到CTS2分组。为了避免节点Z误解而启动不必要的CTS-Only握手，应用了RTID的方法。,中科院计算所 授课教师：鲁士文 2006.3.1,38,10.3.4 MARCH协议,在MARCH中，MAC层可以访问路由表，该路由表维持该节点所参与的路径信息以及在这些路由中它的上游和下游邻居。然而，这并不意味着MARCH执行第2层路由选择。事实上，它只是查询这些表，以确定它是否应该对一个特别地用于某条路经的控制报文（RTS/CTS）做出响应。如果一个节点要启动路径1上的仅仅CTS握手，它在CTS分组中包括它用于那条路径的RTID。因此，通过检查在CTS2中的RTID，仅仅节点D会对该控制分组做出适当的反应，可以在它的Tw定时器期满后发起一次仅仅CTS握手。,中科院计算所 授课教师：鲁士文 2006.3.1,39,10.3.4 MARCH协议,简言之，MARCH（采用简化握手过程的介质访问）不参与路由选择，也不做数据分组交换的决定。然而，它对MAC帧提供高速快捷的中继，并且在由源到目的地的路径上用不着每一跳段都执行RTS-CTS握手过程，从而提高了网络性能。,中科院计算所 授课教师：鲁士文 2006.3.1,40,10.4 Ad hoc按需距离向量路由选择,已经为Ad hoc网络提出了多种路由算法，其中比较引人注目的是Ad hoc按需距离向量（AODV）。AODV（Ad hoc On-Demand Distance Vector）算法不是像常规的距离向量算法那样维持整个路由表，而是在按需的基础上建立路由，从而减少所需要的广播数目。AODV是一个按需获得路由的系统，因为不在所选通路上的节点不用维持相关的路由信息，不参与相关的路由表交换。 如图10-6所示，当一个源节点要发送一个报文给某个目的节点并且尚未得到前往那个目的地的有效路径时，它启动一个通路发现过程，确定另一节点的位置。它给它的邻居广播一个路由请求（RREQ）分组，邻居再把该请求转发给它们的邻居，直到请求抵达目的地或一个有到达目的地足够新的路由的中间节点。,中科院计算所 授课教师：鲁士文 2006.3.1,41,10.4 Ad hoc按需距离向量路由选择,中科院计算所 授课教师：鲁士文 2006.3.1,42,10.4 Ad hoc按需距离向量路由选择,AODV使用路由的目的地顺序号来保证所有的路由都是无回路的，并且包含最近的路由信息。每个节点维持它自己的顺序号，每发出一个分组（请求或应答），该顺序号都加1，起着类似于时钟的作用。每个节点还维持一个广播ID，该ID随着该节点启动的每个RREQ递增，跟该节点的IP地址结合在一起唯一地标识一个RREQ。随同自己的序列号和广播ID，源节点在其RREQ中还包括它具有的关于那个目的地的最近的序列号。中间节点仅当它们具有到达目的地的路由，并且该路由对应的目的地序列号大于或等于在RREQ中的序列号时才可以应答。,中科院计算所 授课教师：鲁士文 2006.3.1,43,10.4 Ad hoc按需距离向量路由选择,在转发RREQ的过程中，中间节点在它们的路由表中记录从其收到广播分组的第一个邻居的地址，从而建立一条反向通路。如果随后又收到同一RREQ的拷贝，这些分组会被静静地丢弃。一旦RREQ抵达目的地或抵达一个具有足够新鲜路径的中间节点，那么目的地或中间节点就要给首先从其收到RREQ的邻居单播往回发送一个路由应答（RREP）分组，作为响应（参见前面的图10-6）。当RREP沿着反向通路向后传输时，沿着这个通路的节点都在它们的路由表中建立转发路径登记项，指向从其接收RREP的节点。这些转发路径登记项表示活动的转发路径。跟每个路径登记项相关联的是路径定时器，如果该登记项在指定的生命期内不被使用，就会被删除。由于RREP是沿着由RREQ建立的通路转发，因此AODV仅支持使用对称链路的情况。,中科院计算所 授课教师：鲁士文 2006.3.1,44,10.4 Ad hoc按需距离向量路由选择,在AODV中，如果源节点移动了，它必须重新启动路由发现协议，寻找到达目的地的新路由。如果沿着路径的一个节点移动了，它的上游节点注意到了该移动，并且给它的每个上游活动邻居传播一个链路失效通知报文（一个带有大距离参数的RREP），通知它们删除该路径的那个部分。这些节点再把链路失效通告传播到它们的上游邻居，如此进行下去，直到抵达源节点。如果还需要使用这条路由，源节点可以选择为那个目的地重新启动路由发现过程。 AODV的另一个附加成分是hello报文，该报文由一个节点定期地在本地广播，通知它的邻居自己的活动性以及关于自己的邻居中的其它节点。可以使用hello报文来维持一个节点的本地连接性。然而对hello报文的使用不是必须的，节点可以倾听再次发射的数据分组，确信下一跳段依然可达。如果没有听到再次发射，节点也可以使用其它技术，包括对hello报文的接收。hello报文可以列出移动节点所听到的其它节点，使得对网络连接性有较好的感知。,中科院计算所 授课教师：鲁士文 2006.3.1,45,10.5 基于关联的长活路由选择,基于最短通路的路由选择不适合无线ad hoc网络。在时间T计算的最短ad hoc路由在时间T+1可能不再有效，因为在路径上的任何节点都可能已经移动了，或者在路径上的链路特征可能已经改变。因此需要有一个新的路由选择方法。 关联涉及移动主机的空间、时序和连接的稳定性。特别地，关联是用一个节点跟它的邻接节点的连接性来测量的。当一个节点迁移时，它跟邻居的关联改变，它的过渡期可以用关联时标或计数来标识。就迁移而言，在一个不稳定的时期之后，存在着一个稳定期，也就是说，在一个时期内一个节点跟某些邻居保持连接性，恒定地跟它们相关联。在稳定期间，移动节点在开始打破它跟周围邻居的连接性关系并移动出当前无线单元边界之前，会在当前的无线单元内度过某个长度的休眠时间。,中科院计算所 授课教师：鲁士文 2006.3.1,46,10.5 基于关联的长活路由选择,图10-7示出了一个移动节点跟它的邻居的空间和时序关系。当移动节点在空间上从一点移动到另一点时，它听到来自它的邻居的信标。它跟邻居节点的结盟也随着时间和空间改变。特别地，移动节点从邻接节点C收集到更多的信标，因为它的移动框架是继续跟节点C维持好的连接性；尽管它在时间和空间上都一直在移动，但有着高的关联时标。,中科院计算所 授课教师：鲁士文 2006.3.1,47,10.5 基于关联的长活路由选择,中科院计算所 授课教师：鲁士文 2006.3.1,48,10.5 基于关联的长活路由选择,在基于关联的长活路由选择（ABR）中，每个移动主机定期地发送标识它自己的短的信标（类似于hello报文），并且不断地更新根据它在周围环境中听到的其它信标而产生的关联/计数。例如，在一个无线ad hoc网络中，每个无线单元直径为10米（r=5），每个移动主机每秒钟发出一个信标。因此，如果一个移动节点以2米/秒的步行速度迁移，穿过一个无线单元，有一个或多个邻接移动主机，那么，该移动主机将会纪录不大于5的关联时标。假定这是一个门槛值，记作Athreshold,大于这个门槛值的任何关联时标意味着关联稳定。给过渡邻居发送分组是无用的，因为跟这个邻居的链路连接性不久将被打破。在本质上，为了得到ad hoc移动网络中的稳定路由，具有稳定的链路是关键的。,中科院计算所 授课教师：鲁士文 2006.3.1,49,10.5 基于关联的长活路由选择,在ABR（Associativity-Based Long-lived Routing）中，当移动主机对它的邻接节点具有低的关联时标时，它呈现高度的移动状态。然而，如果观察到高的关联时标（大于Athreshold），移动主机将被看成是处于稳定状态，这是执行ad hoc路由选择的理想时间点。因为在关联性上的互相依赖关系，如果在一条路径上的所有移动主机都具有高的关联时标，那么就产生互锁现象，在这里，对于一台主机而言，如果其它主机都没有离开可达范围，并且进入移动状态，那么该主机的关联度是高的。,中科院计算所 授课教师：鲁士文 2006.3.1,50,10.5 基于关联的长活路由选择,上述讨论集中在对关联时标的解释上。然而，在ABR中的稳定性指的不仅仅是关联时标。如表10-1所示，它还包括信号强度和电池生命期。信号强度定义信号传播通道的质量，而电池生命期描述设备的当前电池生命期。在无线收发器技术方面的进展使得监视信号强度随时间变化并把这一信息存储到存储器成为可能。类似地，在智能电池技术方面的进展使得我们能够监视采用电池供电的设备的剩余功率生命期。我们可能使用这类信息来考虑路由的稳定性。,中科院计算所 授课教师：鲁士文 2006.3.1,51,10.5 基于关联的长活路由选择,中科院计算所 授课教师：鲁士文 2006.3.1,52,10.5 基于关联的长活路由选择,传统的路由度量关注的特征是： *对于链路变化的快速自适应（指路由恢复时间）； *到目的地的最小跳段数通路； *传播延迟(介质延迟，跟传播距离有关)； *避免回路； *链路容量（影响发送或转发延迟）。 然而，在无线ad hoc网络中，以频繁的广播和过量的无线带宽消耗为代价的快速自适应是不可取的。好的路由质量不应该包括跳段数目和往返路程传播的时延。,中科院计算所 授课教师：鲁士文 2006.3.1,53,10.5 基于关联的长活路由选择,由于具有较小跳段数值但有效期短的路由因频繁的数据流中断和需要做频繁的路由重构而效果很差，在ad hoc移动网络中路由长活性是最重要的。这种新的度量理念表明，经典的最短通路度量既不必用于也不可用于ad hoc无线网络。从另一个角度看问题，公平路由中继负载也是重要的，因为没有一个特别的移动节点应该不公平地承担支持许多条路由和执行许多分组中继功能的任务。这是一个公平性的问题，均匀路由中继负载可以减少在ad hoc移动网络中发生拥塞的可能性。 从源到目的地有多条可能的路由的情况下，如果一条路由由若干具有高的关联时标的移动节点组成，那么该路由将被该目的地选用，而不管是否存在其它较少跳段数的短路由。然而，如果有两个或更多个路径的总体关联稳定度相同，那么将选择具有最少跳段数的路由。如果多条路由具有同样的最小跳段计数，那么将任意地选择其中的一条路由。这种ABR路由选择算法在目的地节点上运行。,中科院计算所 授课教师：鲁士文 2006.3.1,54,10.5 基于关联的长活路由选择,ABR协议是由源起始的按需路由协议，它由三个阶段构成： *路由发现阶段； *路由重构阶段； *路由删除阶段。 开始，当源节点需要一条路由时，调用路由发现阶段。当由于源/目的地/中间节点或子网-桥接移动主机迁移引起所建立的路径的链路改变时，调用路由重构阶段。当源节点不再需要该路由时，它发起路由删除阶段。,中科院计算所 授课教师：鲁士文 2006.3.1,55,10.5.1 路由发现阶段,路由发现阶段由一个广播查询（BQ）和一个等待应答（REPLY）构成。起初，除了目的地节点的邻居之外的所有节点都没有到达该目的地的路由。要得到到达目的地的一条路由的一个节点广播一个广播查询（BQ）报文，该报文通过ad hoc移动网络传播，寻找到达目的地有一条路由的移动主机。在这里需要使用序列号唯一地标识每个BQ，没有一个BQ分组会被多于1次地广播。 一旦BQ分组被源广播了，所有收到该查询的中间节点都需要检查它们是否已经处理过这个分组。如果已经处理过，就把该查询分组丢弃。否则每个节点就检查它是否是目的地。如果不是目的地，它就把自己的移动主机地址/标识符附加在查询分组的IN标识符域，并把分组广播到它的邻居（如果有的话）。随同它的路由中继负载、链路传播延迟、剩余电池生命期和路由跳段计数，它还附加上跟其邻居的关联时标。图10-8示出了关联时标捎带信息是如何加进BQ查询分组的。,中科院计算所 授课教师：鲁士文 2006.3.1,56,10.5.1 路由发现阶段,中科院计算所 授课教师：鲁士文 2006.3.1,57,10.5.1 路由发现阶段,下一个后继中间节点将删除它的上游邻居的跟路径无关的时标，仅保留跟它自己及其上游邻居相关的时标。以这种方式，到达目的地的查询分组将仅含有中间移动主机地址（因此记录了所经过的通路）以及它们的关联时标（因此记录了支持该路由的中间节点的稳定状态）和中继负载，同时还含有路由转发延迟和跳段计数信息。因此，如图10-9所示，结果产生的BQ分组是可变长的。,中科院计算所 授课教师：鲁士文 2006.3.1,58,10.5.1 路由发现阶段,中科院计算所 授课教师：鲁士文 2006.3.1,59,10.5.1 路由发现阶段,在接收到第一个BQ分组之后的适当时间，目的地将知道所有可能的路由和它们的质量。然后它可以基于前述选择的标准选择最好的路径，并且如图10-10所示，通过选择的路径往源回送一个REPLY分组。这就引起在路径上的中间节点把它们通往目的地的路径表记成有效，这就意味者所有其它可能的路径都将是不活动的，不为那个目的地中继分组，即使它们听到了传输。因此，这样就避免重复分组到达目的地。类似于BQ，REPLY分组也是可变长的。,中科院计算所 授课教师：鲁士文 2006.3.1,60,10.5.1 路由发现阶段,中科院计算所 授课教师：鲁士文 2006.3.1,61,10.5.2 路由重构阶段,虽然使用基于关联的长活路由算法选择的路由倾向于是长活的，但仍然有违犯关联稳定性的时候，例如，移动设备用户可能决定要去休息室或者离开所在场点做其它的事先未预料到的处理。在这种情况下就要用到路由重构过程来处理移动性问题(当由于源/目的地/中间节点或子网-桥接移动主机迁移引起所建立的路径的链路改变时，调用路由重构阶段) 基于关联的长活路由算法（ABR）把路由修复操作本地化，智能地避免过量的控制开销和打扰不相关的节点。ABR路由恢复使用部分路由恢复原则，因此恢复过程是快速的。它在运行过程中实时地修复断开的路径。,中科院计算所 授课教师：鲁士文 2006.3.1,62,10.5.2 路由重构阶段,ABR路由维护阶段包括下列操作： *部分路由恢复； *无效路由删除； *有效路由更新； *新的路由发现。 ABR通过尝试快速定位一条有效替代路由来处理不可预料的移动，除非必需，一般不采用广播查询（BQ）。以下的讨论分别参照图10-11(a)、(b)和(c)。,中科院计算所 授课教师：鲁士文 2006.3.1,63,10.5.2 路由重构阶段,中科院计算所 授课教师：鲁士文 2006.3.1,64,10.5.2 路由重构阶段,由于该路由协议是由源起始的，SRC的移动将引入等效于路由初始化的路由重构过程，即通过BQ-REPLY过程。这样做可以避免由并发节点移动引起的多重路由重构冲突。 当DEST移动时，DEST的直接上游邻居将删除它的路由。然后执行一个LQ(H)过程，这里的H表示跳段数。LQ(H)是一个本地查询过程，探知DEST是否仍然可达。如果DEST接收到该LQ，它将选择最好的部分路由（再次基于关联稳定性标准），并发送REPLY；否则LQ_TIMEOUT期满，该上游节点将反向跟踪下一个上游节点。在反向跟踪期间，新的上游节点将删除通过那条链路的路由，并执行一个LQ(H)过程，直到新的上游节点离开DEST的距离大于从源到目的地跳段数的一半，或者发现了一个新的部分路由。如果没有找到部分路由，相关的上游节点将发送一个路由通告分组RNDIR=1给源节点，以初始化一个广播查询BQ过程。图10-12示出了本地查询LQ控制分组的格式，跟BQ相似，LQ分组也是可变长的。,中科院计算所 授课教师：鲁士文 2006.3.1,65,10.5.2 路由重构阶段,中科院计算所 授课教师：鲁士文 2006.3.1,66,10.5.2 路由重构阶段,如图10-13所示，路由通告分组RN包含一个ORG ID域，该域存储上游节点地址以及表明要执行的路由通告的类型的STEP标志。当STEP=0时，反向跟踪过程一次一跳地执行（在往上游的方向上）；当STEP=1时，就意味着路由通告控制分组将往回直接传到源节点，以引入BQ-REPLY周期，或者传给目的节点以删除无效路由。路由通告控制分组RN还包含一个DIR标志，表示RN1传播的方向。,中科院计算所 授课教师：鲁士文 2006.3.1,67,10.5.2 路由重构阶段,中科院计算所 授课教师：鲁士文 2006.3.1,68,10.5.2 路由重构阶段,如果在路径上的任一中间节点移动了，并破坏了关联稳定度，就需要执行路由重构过程。直接上游节点将引入LQ(H)过程，快速定位一个替代的稳定的部分路由。LQ(H)过程的执行是基于一个适当的H值。如果该上游节点经过先前的活动路由离目的地节点的距离是x跳段，那么