《高级计算机网络》之移动自组网——大连理工大学研究生课程整理笔记（非常详细，通俗易懂）

注&＃xff1a;本文根据大连理工大学《高级计算机网络》课程整理&＃xff0c;这部分是移动自组网专题。整理不易&＃xff0c;对你有用的话点个赞吧&＃xff01;

• 《高级计算机网络》之移动自组网——大连理工大学研究生课程整理笔记&＃xff08;非常详细&＃xff0c;通俗易懂&＃xff09;
• 《高级计算机网络》之无线传感网——大连理工大学研究生课程整理笔记&＃xff08;非常详细&＃xff0c;通俗易懂&＃xff09;
• 《高级计算机网络》之物联网——大连理工大学研究生课程整理笔记&＃xff08;非常详细&＃xff0c;通俗易懂&＃xff09;

mobile ad hoc network 移动自组网

名词汇总

• MANET mobile ad hoc network 移动自组网
• DSR dynamic source routing 动态源路由
• RREQ route request 路由请求
• RREP route reply 路由回复
• RERR route error 路由错误信息
• hello message 用来检测连通性的
• LAR Location Aided Routing 位置辅助路由
• bi-directional 半双工&＃xff1a;可发可收&＃xff0c;但是不能同时发和收

introduction 介绍

• fromed by wireless hosts which may be mobile 由移动终端组成
• without using a pre-existing infrastructure 不用预先存在的基础设施
• routes between nodes may potentially contain multiple hops 多路跳转
• may need to traverse multiple links to reach a destination 可能需要遍历多条链路来到达目标节点
• mobility causes route changes 移动性导致的路由变换

why mobile ad hoc network?

• easy of deployment 部署便捷
• speed of deployment 部署速度快
• decrease dependence on infrastructure 减少对基础设施的依赖

many applications 应用

• 个人应用
  • 手机&＃xff0c;笔记本&＃xff0c;耳机&＃xff0c;手环
• 军事应用
  • 士兵&＃xff0c;坦克&＃xff0c;飞机
• 城市环境
  • 出租车网络&＃xff0c;会议室&＃xff0c;运动场&＃xff0c;小船&＃xff0c;小型飞行器
• 突发事件场景
  • 搜救&＃xff0c;警用设施&＃xff0c;消防救援

许多变化many variations

• 完全对称的环境
  • 所有的节点都有相同的能力和责任
• 非对称环境
  • 传输范围和雷达不同 transmission ranges and radios may differ
  • 不同节点的电池寿命不同
  • 不同节点的处理能力不同
  • 移动速度的不同&＃xff08;不同节点&＃xff09;
• 非对称环境下各节点的责任
  • 只有一些节点发送报文 route packets
  • 一些节点负责领导附近的节点&＃xff08;节点集群&＃xff09;
• 不同的移动自组网中交通设备的特性
  • 比特率
  • 时效性约束 timeliness constraints
  • 可靠性要求 reliability requirements
  • 单播&＃xff0c;多播&＃xff0c;位置辅助多播
• 可能基于相同的基础设施进行合作&＃xff0c;共存。
• 移动模式不同
  • 人在飞机的候机室
  • 纽约的出租车
  • 孩子玩耍
  • 军事移动
  • 个人领域的网络 personal area network
• 移动特性
  • 速度
  • 预测
    • 移动方向
    • 移动模式
  • 不同节点之间的移动缺乏一致性

*挑战 challenges

• 无线传输范围有限
• 无线终端的广播特性&＃xff1a;隐藏终端问题 hidden terminal problem
• 传输错误导致丢包
• 移动导致路由变化
• 移动导致丢包
• 能量限制 batter constraints
• 潜在的大量网络介入 potentially frequent network partitions
• 安全问题&＃xff1a;无线网络容易被监听 ease of snooping on wireless transmissions(security hazard)

hidden terminal problem 隐藏终端问题

A 和 C 无法感知到对方。

解决方案 the holy grail

圣杯&＃xff1a;极难得到的东西

• 一劳永逸的解决方案 a one-size-fits-all solution
  • 可能使用一个自适应的/混合的方案
• 许多方案提出尝试解决一个子问题

假设&＃xff1a;所有的环境都是对称的

除非特别声明 unless stated otherwise, fully symmetric environment is assumed implicitly

unicast routing 单播路由

没有任何协议能在所有环境里都表现良好。

路由协议的分类

• 主动路由协议
  • 根据移动模式主动探测
  • 传统的link-state和distance-vector 路由协议是主动的
• 被动路由协议
• 混合路由协议

折中方案 trade off

• 路由发现的延迟
  • 主动式路由协议低延迟&＃xff1a;因为路由一直保持连接
  • 被动式高延迟&＃xff1a;因为X到Y的路由只有在X尝试发送到Y的时候才开始建立
• 路由发现或保持的开销
  • 主动式开销大&＃xff1a;因为要保持路由的更新
  • 被动式开销小&＃xff1a;只有必要的时候才进行路由探索
• 哪一个方法达到更好的折中取决于流量和移动模式

路由协议一览

重点关注&＃xff1a;

洪范式路由发现过程&＃xff0c;

动态源路由发现过程&＃xff08;路由缓存&＃xff09;&＃xff0c;

位置辅助路由发现过程&＃xff0c;

以及DREAM算法&＃xff08;实际上也是基于地理位置的&＃xff0c;圆锥区域发送&＃xff09;&＃xff0c;

查询本地化&＃xff08;在旧的路径的基础上最多加入K个新节点&＃xff09;&＃xff0c;

还有对于广播风暴的应对算法&＃xff08;距离&＃xff0c;计数&＃xff0c;延迟转发&＃xff0c;dropout)&＃xff0c;以及查询本地化&＃xff08;最多K个节点&＃xff0c;减少洪泛范围&＃xff09;

按需距离矢量路由AODV&＃xff08;路由信息保存在节点上&＃xff0c;单一路径路由&＃xff0c;需要的时候才连接&＃xff09;

链路反转算法&＃xff08;部分反转&＃xff0c;全反转&＃xff0c;可能会有多条路径&＃xff09;

洪泛式数据传输 flooding for data delivery

• 发送节点S发送数据包P给所有的邻接结点
• 每个收到P的节点也转发给各自的邻接节点
• 序列号码用来防止传输相同的包两次
• 目标节点D不用转发package

洪泛式数据传输的优点

• 简单
• 可能的高效性&＃xff08;低开销&＃xff09;&＃xff1a;当信息传输率足够低的时候&＃xff0c;可能会比其他协议有效&＃xff0c;因为路由发现和保持的开销增加。
  • 例如&＃xff1a;当传输的数据包比较小的时候&＃xff0c;而此时两次连续传输之间的路由结构发生了变化
• 潜在的数据传输的高可靠性
  • 因为传输到目标节点有多条路径

洪泛式数据传输的缺点

• 高开销
  • 数据传输给许多不必要的节点
• 可能的低可靠性
  • 洪泛使用广播&＃xff0c;而广播在不明确增加开销的前提下是很难保证可靠性的。 IEEE802.11 MAC是不可靠的
  • 例如&＃xff0c;节点J和K同时发送数据包给D导致数据包丢失&＃xff0c;导致冲突。

改进&＃xff1a;洪泛式控制包传输 flooding of control packets

• 许多协议只是洪泛控制包&＃xff0c;而非数据包
• 控制包用来进行路由发现
• 被发现的路由可能用来发送数据包
• 洪泛控制包的开销被分摊了 &＃xff1f; 如何分摊&＃xff1a;理解&＃xff0c;可能是和之前的洪泛数据包作比较&＃xff1f;

动态源路由 dynamic source routing(DSR)

初始节点S 通过洪泛 发送 RREQ&＃xff08;route request 路由请求包&＃xff09;

每个经过的节点都将自己的标识加入到控制包中&＃xff08;慢慢的形成一条路径&＃xff09;

目标节点D收到第一个RREQ之后&＃xff0c;根据RREQ中的路由反转&＃xff0c;发送RREP&＃xff08;route reply 路由回复包&＃xff09;&＃xff0c;RREP包含了S到D的路由信息。

• RREP 只能在半双工传输链路中传送&＃xff0c;因此发送RREQ的时候应该只发送给满足半双工传输路径的节点&＃xff08;即发给他&＃xff0c;他也能发给我&＃xff0c;全双工是能同时收发&＃xff0c;半双工是双向收发&＃xff0c;但不能同时&＃xff09;
• 如果路径中的节点允许非全双工&＃xff08;非对称&＃xff09;那么可能目标节点还需要发现到S的路由。&＃xff08;即不能反转S到D的路由&＃xff0c;还得重新寻找回去的路&＃xff09;
  • 如果路由D已经知道了到S的路由&＃xff0c;那么RREP会经过这个路由发送

源节点S收到目标节点D的RREP之后

• S将会捕获S到D的路由信息
• S发送给D的数据包中&＃xff0c;在头部将会包含整条路由信息&＃xff08;hence the name source routing)
• 中间负责转发的节点根据数据包头部的souce route来决定转发给哪个节点

什么时候执行路由发现&＃xff1a;当节点S要发送数据包给D但是不知道S到D的路径的时候。&＃xff08;废话&＃xff09;

改进DSR优化&＃xff1a;路由缓存 route caching

在路由发现过程中可以充分利用所有涉及的节点已知的信息。

路由缓存的使用

情景一&＃xff1a;当节点S获知到节点D的路由中断的时候&＃xff0c;它会从路由缓存中找到一条可行的路由。否则就发送RREQ进行路由发现。

情景二&＃xff1a;中间节点X如果收到了一个路由请求并且知道从X到目标节点的路由&＃xff0c;那么X可以直接发送RREP给S。

• 可以加速路由发现
• 可以减少路由请求的传输

路由缓存需要注意的

• 过期的路由缓存会影响性能stale caches
• 随着时间流逝和终端的移动&＃xff0c;已经获知的路由信息可能会无效/过期。
• 发送者可能需要多次尝试才能找到一条好的路由

DSR优点

• 只有必要的节点之间才进行路由保持连接
• 路由缓存能够进一步减少路由发现的开销
• 一个路由发现过程可能会产生许多到目标节点的路由。因为中间节点从本地缓存中进行回复。

DSR缺点

• 路由长度过长&＃xff0c;包的头部过大&＃xff08;可能会导致负载降低&＃xff0c;即包头比数据还大&＃xff09;
• 路由请求信息洪泛可能会到达所有的节点
• 需要避免相邻节点之间的路由请求冲突&＃xff1a;在转发RREQ之前设置随机延迟&＃xff08;即&＃xff0c;隐藏终端问题&＃xff09;
• 冲突加剧&＃xff1a;如果大量的节点用本地缓存路由信息进行回复
  • 路由回复风暴问题 route reply storm problem&＃xff08;后面有风暴问题的解决方案&＃xff09;
  • 当一个节点获知别的节点有更短的路由RREP已经发送的时候就不用再发RREP了&＃xff0c;这样可以缓解路由回复风暴问题。
• 一个中间节点的本地缓存路由信息可能是过时的&＃xff0c;而它用这个信息进行回复会**污染其他的缓存。**polluteing other caches
• 这个问题可以通过引入某种净化机制来缓解。
• 一些可行的净化方案
  • 静态超时 static timeouts设置超时时间&＃xff08;时间到了就清除路由缓存信息&＃xff0c;或者使用一个队列&＃xff0c;将比较久的信息清除&＃xff09;
  • adaptive timeouts based on link stability 根据链接稳定性设置动态的超时时间&＃xff0c;例如链接不稳定的时候超时时间短&＃xff08;链路不稳定的状态下&＃xff0c;路由信息失效更快&＃xff09;

洪泛控制包的时候

• 如何减少路由请求洪泛的范围
  • LAR 位置辅助路由
  • Query localization 查询本地化
• 如何减少冗余的广播
  • 广播风暴问题

位置辅助路由LAR

Location Aided Routing

位置可以通过GPS获得&＃xff0c;或者其他什么方式。

期望区域Expected Zone&＃xff1a;即目标节点可能的区域范围&＃xff0c;基于之前的目标节点的位置信息以及目标节点移动的速度

请求区域Request Zone&＃xff1a;包含目标节点期望域和发送节点的区域

LAR算法&＃xff1a;

• 只有在请求域内的节点才转发请求&＃xff08;请求域外内的节点收到请求即丢弃&＃xff0c;不转发&＃xff0c;这样能缩小洪泛范围&＃xff09;
• 在请求头中显式地包含了路由请求的请求域&＃xff08;即物理划定的范围&＃xff0c;节点知道自己的物理信息&＃xff0c;能判断自己是否在该范围内&＃xff09;
• 每个节点都必须知道自己的位置以决定是否转发收到的请求
• 如果Sender初始化的请求域太小以至于没找到目标节点&＃xff0c;那么一段时间后重新初始化一个较大的请求域&＃xff08;请求范围&＃xff09;&＃xff0c;最大的范围可能包含整个网络&＃xff08;相当于完全洪泛&＃xff09;
• 其余的部分同DSR&＃xff08;动态源路由协议&＃xff09;

LAR优化&＃xff1a;动态请求域 adaptive request zone

• 每个节点可以根据自己掌握的信息更改请求域&＃xff08;请求域逐渐缩小&＃xff09;
• 更新后的请求域使用的是最新的、较为准确的位置信息&＃xff0c;可能比原始的请求域小

LAR优化&＃xff1a;模糊请求域implicit request zone

• 之前的模式中&＃xff0c;路由请求显式地包含了请求域&＃xff0c;这次不包含而是由节点决定是否转发
• 如果节点X相对于节点Y更接近目标节点&＃xff0c;那么节点X就转发节点Y的请求
• 动机是&＃xff1a;尽可能地让路由请求在每一次转发之后更接近目标节点
• 基于这样一个假设&＃xff1a;在路由发现过程中&＃xff0c;节点X的位置Y是知道的

LAR优点

• 减少了路由请求洪泛的范围
• 减少了路由发现的开销

LAR缺点

• 每个节点都必须知道自己的物理位置
• 没有考虑在信号传输过程中可能存在的障碍物 obstructions for radio transmissions

Distance Routing Effect Algorithm for Mobility(DREAM)

移动的距离路由效应算法

注意&＃xff1a;LAR洪泛的是控制包&＃xff0c;而DREAM洪泛的是数据包&＃xff0c;不需要事先知道路由&＃xff08;不需要发起路由发现的过程&＃xff09;

• 利用位置信息和速度&＃xff08;同LAR&＃xff09;
• 直接洪泛数据包&＃xff08;不同于LAR&＃xff09;
  

如上图所示&＃xff0c;S发送数据包给在圆锥区域内的所有邻接节点&＃xff08;它知道目标节点的大概方位&＃xff0c;但是不知道路径&＃xff09;

• 收到数据包的节点A在一个更小的圆锥区域内转发请求&＃xff08;它也知道目标节点大概的方位&＃xff0c;但是不知道路径&＃xff09;
• 所有收到数据包的节点都如同A一样操作直到找到目标节点

前提是&＃xff0c;所有的节点都要知道自己的位置以及邻接节点的位置

• 节点需要周期性地广播自己的物理位置
• 广播的范围应该也是圆锥区域&＃xff08;而不是全网&＃xff09;&＃xff0c;所以距离自己近的节点更新频繁&＃xff0c;距离远的节点更新就慢。
• Distance Effect&＃xff1a;距离远的节点相对于距离近的节点以较慢的角速度移动
• 使用TTL来控制广播信息/数据包发送的距离。如果TTL短&＃xff0c;发送的距离也短&＃xff0c;TTL&＃xff08;time to live存活时间)到了就认为失败。

Relative Distance Micro-Discovery Routing&＃xff08;RDMAR&＃xff09;

相对距离微发现路由

• 发送节点先评估到目标节点的跳数
• 根据以上的评估来设置TTL
• 评估依据是&＃xff1a;之前的目标节点到发送节点之间的物理距离以及传输范围

Gerographic Distance Routing&＃xff08;GEDIR&＃xff09;

地理距离的路由

• 假设目标节点的位置是已知的
• 每个节点都知道自己的邻接节点的位置
• 每个节点转发包给距离自己最近的邻接节点
• 但是可能会存在不可达的情况&＃xff0c;因为局部最短路径全局不一定是最短的&＃xff0c;甚至是不可达的
• 如果相同的边遍历了两次&＃xff0c;认为路由发现失败&＃xff08;不可达&＃xff09;&＃xff0c;即C发给G&＃xff0c;G又发给C。

Routing with Guaranteed Delivery

保证交付的路由

• 基于GEDIR改进&＃xff1a;保证转发&＃xff0c;即提供一条确定存在的源到目标的路径
• Guarantees delivery(using location information) provided that a path exists from source to destination
• 必要的时候路由可以绕道&＃xff0c;回溯。routes around obstacles if necessary

Query Localization查询本地化

• limits route request flood without using physical information 在不需要物理信息的前提下限制洪泛范围
• route requests are propagated only alone paths that are close to the previously known route 路由请求的转发只基于之前已知的路由路径
• the closeness property is defined without using physical location information 所谓的最近定义不基于物理位置信息
• path locality heuristic(启发式的&＃xff0c;探索式的)&＃xff1a;look for a new path that contains at most K nodes that were not present in the previously known route 寻找一条新的路径包含最多K个新节点&＃xff0c;这K个节点并不包含在最近已知的路径中。
• route request is forwarded only if the accumulated route in the route request contains at most k new nodes that were absent in the old route,this limits propagation of the route request.
• 只有当路由请求头中的节点包含至多K个新的节点&＃xff08;之前的路由中没有出现过的节点&＃xff09;时&＃xff0c;本次路由才会转发&＃xff0c;这大大限制了路由转发的数量。

查询本地化的优势

• 在不用物理位置信息的前提下减少了路由转发的开销
• 可以在旧路由的邻近区域搜索新路由&＃xff0c;在有障碍物的情况下表现更好

查询本地化的缺点

可能会产生比LAR更长的路由&＃xff0c;最短的路由可能包含了超过K个新节点&＃xff0c;所以找到的路由不一定是最短的。

看这个例子&＃xff0c;之前已知道的路由SAD&＃xff08;旧的路由&＃xff09;&＃xff0c;现在D移动了位置变成了右边的样子。

这样只需要在旧的路由的基础上&＃xff0c;最多再洪泛两个节点&＃xff0c;即SABE&＃xff0c;或者SABC.失败了就增大K。

而F节点不会转发请求&＃xff0c;因为加上F节点就是新增三个节点了&＃xff0c;这样能够控制洪泛的范围。

广播风暴问题 Broadcast Storm Problem

• 冗余:一个节点可能会收到许多节点的相同信息
• 概率模式&＃xff1a;一个节点第一次收到请求的时候&＃xff0c;它以概率P来决定是否转发
• 或者&＃xff1a;不同节点延迟转发&＃xff0c;采取碰撞避免机制。如果同时转发到一个节点&＃xff0c;很容易会导致碰撞。wait a random delay when channel is idle(无事可做的)
• 计数模式&＃xff1a;如果一个节点E接收到超过K个邻居的路由请求&＃xff0c;不进行转发。&＃xff08;这意味着这个节点E周围已经有很多洪泛数据了&＃xff09;
  • 直觉上认为这K个邻居已经转发给这个节点E的所有邻居了。
• **基于距离模式&＃xff1a;**如果E接收到节点Z的请求转发&＃xff0c;而节点E和Z的距离小于d,则E不进行转发。
  • 直觉上认为&＃xff1a;E和Z太近了&＃xff0c;E和Z覆盖的区域相差不大&＃xff0c;即便E进行了转发&＃xff0c;所能通知到的新节点也寥寥无几。

广播风暴问题总结

• 概率转发&＃xff0c;延迟转发&＃xff0c;计数模式&＃xff0c;距离模式
• 洪泛会导致&＃xff1a;碰撞&＃xff0c;冗余
• 碰撞问题&＃xff1a;通过延迟转发解决&＃xff0c;waiting for a random interval before propagating the flood
• 冗余问题&＃xff1a;通过选择性的转发来解决

Ad Hoc On-Demand Distance Vector Routing (AODV) 按需距离矢量路由协议

总结&＃xff1a;只有需要的时候才发起路由请求&＃xff0c;路由信息保存在每个节点上&＃xff0c;每个节点只保存到下一跳的信息。

• 动态源路由头部包含了路由信息&＃xff0c;这导致头部越来越大&＃xff0c;可能会让负载有效率降低&＃xff0c;即头部比负载信息还大。
• AODV将路由表保存在节点&＃xff0c;这样数据包就不用包含路由信息了
• AODV和DSR一样只有节点之间需要通信的时候才保持连接。
• RREQ发送的过程同DSR
• 当一个节点转发请求的时候&＃xff0c;它反转路径指向源节点&＃xff0c;AODV假设是全双工的
• 当目标节点接收到请求的时候&＃xff0c;它根据反转的路径发送RREP
• 一个中间节点可能会发送RREP提供一个最新的到目标节点的路径。
• 但是这个中间节点发送RREP的概率比DSR低&＃xff0c;因为节点S发起的RREQ设置了一个更大的序列号&＃xff0c;而中间节点的序列号较小无法发送RREP。&＃xff08;当序列号足够大时才认为它掌握的信息是最新的&＃xff09;

timeouts

• 一个路由表维护的逆向路径在一段时间后&＃xff08;timeout 超时时间&＃xff09;将会被清除
  • timeout的设置应该能保障RREP回到发送节点
• 一个路由表维护的逆向路径在一段时间内&＃xff08;active_route_timeout 活动路由时间)没有使用&＃xff0c;将会被清除。
  • 即便这个路劲信息依然是有效的

Link Failure Reporting 连接失败报告

Route Error

• 当节点X无法转发数据包P的时候&＃xff0c;它就生成一个RERR消息
• 节点X加大目标节点的序列号&＃xff0c;序列号将被包含在RERR中
• 节点S收到RERR之后&＃xff0c;重新开始路由发现过程&＃xff0c;这时对目标节点设置的序列号至少比N大&＃xff08;每一跳之后序列号就增加&＃xff09;

AODV总结

• routes need not be inclued in packet headers包头不用包含路由
• nodes maintain routing tables containing entries only for routes that are in active use节点只需要维护需要使用的路由表实体
• at most one next-hop per destination maintained at each node 最多只需要维护一跳的信息就行&＃xff08;一个节点只需要维护到邻居的路径即可&＃xff09;
  • dsr may maintain serveral routes for a single destination&＃xff08;DSR需要维护很多&＃xff0c;可能是整条完整的路径&＃xff09;
• unuserd routes expire enve if topology dose not change 即便网络拓扑结构没有发生改变&＃xff0c;那些长期未使用的路由也会被清除

Link Reversal Algorithm 链路反转算法

• 首先要求链路是bi-directional 半双工的&＃xff08;可发可收&＃xff0c;但是不能同时发和接收&＃xff09;
• 为每一个目标节点维护一个有向无环图&＃xff08;Directed acyclic graph DAG)
• 除了目标节点&＃xff0c;任何没有出路的节点都将入的链路反向
• 注意到之前反向过得邻居还会再次被反向&＃xff1a;每次都是整个网络满足条件的节点反向。 full reversal method 全链路反向方法
• partial reversal method 局部链路反向算法&＃xff1a;之前反向过得不用再反向

链路反向算法的优点

• link reversal methods attempt to limit updates to routing tables at nodes in the vicinity of a broken link
  • partial reversal method tends to be better than full reversal method
• each node may potentially have multiple routes to a destination 可能会有多条路径到目标节点

缺点

• need a mechanism to detect link failure&＃xff08;需要引入检测链路失败的机制&＃xff09;
  • hello messages may be used 发送hello message来检测连通性
  • but hello message can add to contention
• if network is partitioned&＃xff08;分割&＃xff09;&＃xff0c;link reversal continue indefinitely (陷入死循环)