自组织网络（Ad Hoc Network）——TOPIC 5 MANET Routing

MANET Routing

为什么不用有线MANET Routing？
  • 寻找到可靠的链接需要花费很多能量
  • 收敛慢 slow convergence
  • 吞吐量低
  • 管理中的挑战——移动性 / 带宽限制 / 资源限制，用电
MANET的组成分类

在这里插入图片描述

Table Driven(例如DSDV)
  • 保持routing table的实时性，周期性的路由更新
  • 每个路由的路有信息都会被记录
  • 大量的通信和电力消耗（Substantial signalling traffic and power consumption.）
On-Demanded Driven(例如ABR/AODV)
  • source只有为了传输才会创建route
  • 当节点需要到目的地的路由时，它将在网络中启动路由发现过程
  • 没有周期性的route更新
  • power使用相对高效
  • 带宽使用相对高效

Destination Sequenced Distance Vector（DSDV）

总体来讲，DSDV协议是对传统的DV协议的一种拓展。

  • 每个节点都保持着一张路由表，路由表中的每一项记录了它到目的节点的距离和序列号，也就是 （S，D）
  • 给每条路径增加了一个序列号码
  • 每个目的节点会定期广播一个单调递增的偶数序列号号码
  • 当一个节点到某个目的节点的路径断开时，把到这个节点的距离设为∞，并且将这条路径的序列号加1（此时为奇数），然后向网络中广播这个更新包。
    当这条路径修复时，它又将序列号加1然后广播出去（整体+2）。

我们假设节点A向节点B发送了一个信息（Sa，Da），B在更新前的状态是（Sb，Db）。在收到信息后，B将按照如下方式进行更新：
当Sa>Sb
序列号的更新以序列号较大的为准，距离也变成Db = Da + d(A, B)。
当Sa=Sb
比较Db 和 Da + d(A, B) ，选择较小的值作为新的Db。如果需要经过A到达目的节点，将设置A为下一跳。
在这里插入图片描述

DBF算法在这里插入图片描述

路由更新的一种比较好的解决方案：
1）full dump（完全转储）： 它包含所有可用的路由信息。当本地拓扑发生重大变化(许多节点正在移动)时，就会发生这种情况。
2）? Incremental Updates（增量更新）： 只包含自上一次full dump以后的路由信息。当路由没有观察到重大变化的时候，就会发生这种情况。

DSDV的优点/缺点：

advantages：
1）可以随时读取route->destinations，没有延迟
2）序列号的增量更新使现有的有线网络协议适应于无线网络

disadvantages：
1）在高移动性期间，由于链路中断而导致的更新会导致沉重的控制开销
2）要获取关于特定目标节点的信息，节点必须等待由相同目标节点发起的表更新消息。这种延迟可能导致节点上的路由信息陈旧。

AODV

  • 是基于On-Demand的路由协议。

  • 当source源节点需要给网络中其他节点发送信息时，首先广播RREQ
    （RREQ报文中记录着发起节点和目标节点的网络层地址）

  • 邻近节点收到RREQ，首先判断目标节点是否为自己：
    -如果是，则向发起节点发送RREP(路由回应);
    -如果不是，则首先在路由表中查找是否有到达目标节点的路由
    ----如果有，则向源节点单播RREP
    ----否则继续转发RREQ进行查找

  • 按需路由协议，只有当到达某目的节点的路由不存在时，才会激起该协议发起路由请求

  • 传输层使用的是UDP协议
    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在这里插入图片描述在这里插入图片描述

  • 维护反向路径的路由表项将在超时间隔后清除

  • 如果没有使用active_route_timeout间隔，则清除维护转发路径的路由表条目

RERR：

  • 只有当某节点位于某活跃路径之上时，他才能发送Hello消息帧。
  • 活跃路径节点以HELLO_INTERVAL为周期发送Hello消息。
  • 在DELETE_PERIOD的时间内没有收到来自邻居节点的Hello消息，则认为该链路失效；发起一次指向该邻居节点的局部修复，路由修复超时以后，路由错误信息RERR向源节点和目的节点发送，RERR在传播过程中，各中间节点删除该失效路径上相应的路由信息。

两个Timer

route_request_expiration_timer： 设置这个参数是为了让不在路径上的节点，丢弃这个路由数据。
route_caching_timeout ： 用来判断什么时候路由已经无效。此外，活跃节点的地址也会被保留，如果某路由断了，就会找到其他活跃的邻居节点。

ABR

  • 是一种On-Demand路由协议
  • 给予稳定性的原则选择路由
  • Stability in ABR refers to ：
    1）associativity ticks
    2）signal strength
    3）power life
    在这里插入图片描述
  • 如何识别neighbours ？
    -发送Hello message，查看是否有回复
  • 如何判断neighbours的稳定性？
    -比较Hello message的接受频率（一定时间从某个点接收到很多hello message，则它是稳定的）

Associativity Ticks：在这里插入图片描述

  • 迁移过程中，迁移方与邻居的关系发生变化。在这个不稳定的时期之后，存在一个稳定的时期，在此期间，移动主机将在一个无线单元中花费更多的休眠时间，然后再移动。
  • 一个移动电话表示，当它与相邻的移动电话的结合度较低（associativity tick）时，其移动状态处于高水平。如果观察到高结合性标记，这意味着主机处于稳定状态，是执行ad hoc路由的理想点。
    在这里插入图片描述
路由选择的原则 ？在这里插入图片描述
路由发掘步骤（Route Discovery Phase）

在这里插入图片描述

  • source有data要传输了，先进行BQ广播发现邻居都不是destination。
  • BQ先把经过的点的associativity ticks记下来，一直携带着往下一位传输。
  • 如果有多种情况，BQ会都记下来，最后遇到dest以后用算法比较最稳定、最佳的路径。
【Reference原文】
1）数字被用来唯一地识别每一个BQ包并且没有BQ包将被广播超过一次。
2）一旦SRC广播了BQ查询，所有接收该查询的INs将检查它之前是否处理过该包。如果肯定,查询包将被丢弃,否则该节点将检查如果是服务台。如果它不是桌子,在附加MH地址/标识符在IDs中字段的查询数据包广播到邻国(如果有的话)。与它的邻居的结合性蜱也将被追加，连同它的中继负载，链路传播延迟和跳数。
3）下一个成功的IN将擦除它的上游节点的邻居的结合度标记条目，只保留那些与它自己和它的上游节点有关的条目。此外，由于节点之间的关联标记对称，可以检查从上游节点接收到的关联标记的有效性。通过这种方式,查询数据包到达桌子将只包含中间肉类的地址(因此记录路线)和他们的结合性蜱虫(因此录音的稳定状态INs支持路线)和路由转发负载,一起传播延迟和路由跳数信息。产生的BQ包的长度是可变的。
4）DEST将在收到第一个BQ数据包后的适当时间知道所有可能的路由及其质量。然后，它可以选择最佳路由(基于前面提到的选择条件)，并通过选择的路由将应答包发送回SRC。这将导致路由中的INs将其路由标记为有效的DEST，这意味着所有其他可能的路由都将是不活动的，不会中继发送给DEST的数据包，即使它们听到了传输。因此，这避免了重复的数据包到达DEST。

在这里插入图片描述

ABR–IN moves在这里插入图片描述
  • 当被删除的IN节点位于不到一半的位置时，也就是“上臂”的时候，可以返回RN[1]给SRC直接删除没有用的路由条目，重新找到一条新的通向DEST的路由。
  • 然后，由旋转节点调用LQ[H]进程来定位备用部分路由。DEST可能会收到多个LQ，因此它需要选择最佳的部分路由，并向旋转节点返回一个应答。这将导致DEST和旋转节点之间的所有in更新它们的RTs。收到回复后，旋转节点更新其RT条目，并将下一跳(传出)节点ID添加到数据包中。这确保只选择一个部分路由。
  • 当被删除的IN节点位于一半以后的位置时，和以前一样，LQ[H]过程是基于合适的H值来执行的。如果通过之前的主动路由，旋转节点距离DEST X跳，则使用H=X，希望DEST仍然在X跳范围内(通过其他路径可达)或更短。因此，这将尝试重建长度相等或较短的部分路径(即在RRCs期间的路径优化)。
  • 然而,如果不存在部分路线,LQ超时将到期和RN[0]旋转节点发送的数据包将上游到下一个节点,并在这样的循环,直到下一个旋转节点跳数大于一半hopsrc桌子或当一个新的部分路线发现不在座位上。
ABR–Dest Remove在这里插入图片描述
  • 当DEST移动时，DEST的直接上游邻居(即旋转节点)将擦除它的路线。然后它执行一个LQ[H]过程来确定是否仍然可以到达DEST，同时，在到达中间节点之前，一直发送RN[0]。如果DEST收到LQs，它将选择最佳的部分路由并发送回复，否则将达到LQ超时时间，旋转节点将回退到下一个上游节点。
  • 在回溯过程中，新的枢轴节点将擦除通过该链路的路由并执行LQ[H]过程，直到新的枢轴节点距离dest超过一半的hopsrc dest，或者找到新的部分路由。如果没有发现部分路由，则旋转节点将发送一个RN[1]包回SRC以启动BQ进程。虽然RN包的长度是固定的，但LQ包则不是。RN和LQ包的格式如表5和表6所示。
  • ORG ID是枢轴节点ID，而SRC和DEST ID标识路由。步骤=0在RN控制包中（RN[0]）意味着回溯过程是一次一跳地执行(在上游方向)，而步骤=1意味着RN包（RN[1]）将是基于关联的自组网路由直接传播回SRC以调用BQ进程，或传播到DEST以删除无效的数据路线。
ABR–SRC Remove

直接按照Route Discovery Phase中的路由建立过程来重新建立路由。唤醒RRC。

路由重建 ：RRC
BQ ：SRC会发送BQ用来删除没有用的重建
只会有一条路由创建成功
ABR–SRC Remove

当发现的路由不再需要时，SRC将启动路由删除(RD)广播【是一个定向广播direct broadcast】，以便所有INs将更新它们的路由表条目。与BQ类似，RD控制包也可以实现全波形广播。

在这里插入图片描述

版权声明：本文为weixin_43525427原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。