无线自组织网络路由协议及应用#
我们实现通过书上的内容系统了解什么是无限自组织网络协议。
无线自组织网络的定义和分类#
无线自组织网络由一组兼具终端及路由功能的设备通过无线链路形成的无中心、多跳、临时性自治系统。其目的是通过动态路由和移动管理技术传输满足一定服务质量要求的信息流。
特点：
- 无中心
- 自组织
- 多跳路由
- 动态网络拓扑结构
- 临时性
- 传输带宽有限
移动Ad Hoc网络 MANET#
在该网络模型中没有固定的基础设施，每个节点都是移动的。所有节点在网络控制、路由选择和流量管理上是平等的，它们不仅可作为普通节点，同时又可作为路由器，能够以任意方式动态地保持与其他节点的联系，实现发现及维持到其他节点路由的功能；源节点和目的节点之间一般存在多条路径，可以较好地实现负载均衡和选择最优的路由。
因此，虽然节点的无线覆盖取值范围具有局限性，但两个无法直接进行通信的节点可以借助其他节点进行分组转发。
机会网络#
机会网络的概念部分来源于延迟容忍网络 DTN[16]（Delay Tolerant Network）。目前对机会网络还没有一个统一的定义，本书在综合大量文献的基础上给出如下定义：机会网络（Opportunistic Networks）是一种具有间断或部分连接的网络拓扑、利用节点移动带来的相遇机会来实现通信的时延和断裂可容忍的无线移动自组织网络。从本质特征的角度看，机会网络和延迟容忍网络是相同的。
它具有以下特点：
- 由于节点运动性突出，网络拓扑动态变化相对较为剧烈，无线链路断开和重新连接非常频繁。
- 源、目的节点之间不能确保完整的端到端传输路径
- 节点之间通过节点移动获得的相遇机会进行信息互换来通信。
- 网络业务具有时延容忍的特点
无线自组织网络路由协议基础#
在无线自组织网络中，路由是指把信息从源穿过网络传递到目的地的行为。路由协议则是实现路由的一种规约，是路由器之间实现路由信息共享的一种机制，它允许路由器之间相互交换路由信息和维护各自的路由表。路由协议工作在网络层，负责收集关于网络当前状态的数据并寻找最优传输路径，根据这些数据，路由器就可以创建和维护路由表以便以后的数据分组转发。
早期路由协议继承固定网的基本思路，把路由查询建立在对全网路由信息精确掌握的基础上，并将控制平面和数据平面分离。。但由于无线自组织网络稳态持续时间很短，有时甚至在很长时间内无法进入稳态，因此早期的研究者不得不面对这样一种困境：提高拓扑信息更新的速度必然引起巨大的网络开销及频繁的路由震荡，而要克服这两个问题又必须以牺牲路由选择的准确性为代价。
目前无线自组织网络路由技术由两种主流设计思路：
- 控制平面与数据平面分离，单不保证路由表具备100%准确性和实时性。包括ZRP,FSR等
- 将控制平面与数据平面融合，以数据流触发路由查找过程，以提高路由查询开销为代价换取路由信息的实时性，如AODV，DSR等
无线自组织网络的典型特点是，每个节点既是主机，也是路由器。一般无线网络中采用的路由协议具有的共性是，路由更新会导致节点能量和网络带宽大量的周期性消耗。路由建立更新过程对拓扑变化的收敛比较慢，不能满足无线自组织网络的要求。同时，由于网络中的路由信息都是分布式地存储在网络中的各个节点上的，因此，无线自组织网络中的路由协议还要保证这种分布式存储的信息能够适应网络的动态变化。
针对不同业务需求，往往需要设置不同的路由协议。
无线自组织网络路由协议设计要求#
- 变化的网络拓扑的要求：路由协议必须具备对网络拓扑变化快速反应的能力，计算路由时收敛迅速，获取有效路由，尽量避免路由环路发生，提供简单的网络节点定位方法。
- 通信复杂度和节能要求，创建降低路由请求频率，分组等待延时和协议开销的路由机制，降低通信复杂度，有效利用带宽资源，降低控制管理开销，减少发生时间和发生数据量。
- 安全性要求，降低遭受攻击的可能性。
- 网络服务质量QOS支持要求，动态配置网络资源，获得较高的数据传输效率，保证多媒体业务传输质量，保证单跳及多跳路径上的QOS等。
- 收敛迅速。对拓扑变化具有快速反应能力，在计算路由时能够快速收敛，及时获得有效路由，避免出现节点不可达情况。
- 无环路由，拓扑结构变化会导致大量已有路由信息在短时间内作废，从而更容易产生路由环路。在无线自组织网络中提供无环路显得尤为重要。
- 避免无穷计算，经典距离矢量协议在某条链路失效时，可能出现无穷计算的情况。在无限自组织网络当中，链路失败是经常发生的。因此路由协议必须避免无穷计算。
- 控制管理开销小，无线传输带宽有限，传送管理控制分组会消耗掉一部分带宽资源，为了更有效利用带宽资源，因此需要尽可能减少控制管理开销。
- 对终端性能无过高要求，无线移动终端使用的可耗尽能源，CPU性能，内存大小，外部存储容量等都低于固定有线终端。因此不能对终端性能有过高要求。
- 支持单信道，无线自组织网络可能出现单信道。
- 实用简单
路由判据#
路由判据是路由协议的一个重要组成部分，是用来评价一条路径优劣的依据。路由判据是指路由参数、权重或与链路和路径相关的值，通过计算找到源节点和目的节点间开销最小或权值最小的路径，从而决定选用哪一条路径。
经典路由判据包括最小跳数，路径稳定性和链路质量等。
以跳数作为路由判据会使路由上某些节点负载过重，形成一些热点区域，在这些区域内节点特别繁忙，要为多个业务流转发数据包。因此最小跳数并不一定最优。
基于路径稳定性的路由协议具有较强网络鲁棒性，能够有效减少数据传输过程中链路中断次数，从而有效提高网络性能。可以根据GPS位置，节点接收信号强度和累计统计来判断。这种方法不适合于节点移动速度快，拓扑变化激烈的网络。
链路质量包括带宽，分组丢失率和端到端时延等。。现有的反映链路质量的参数主要有RTT（Round Trip Time）、ETX（Expected Transmission Count）、ETT（Expected Transmission Time）、mETX（modified ETX）等
综上所述，自组织网的路由协议设计需要综合考虑网络能力、自组织网的特点和运行环境、路由协议基本功能等诸多因素。
无线自组织网络路由协议类型#
1.根据接收业务数据目的节点个数不同分类：
- 单播：单个源节点对单个目的节点，单播路由协议。例如路由消息协议（Routing Information Protocol，RIP）、表驱动距离向量路由协议（Dynamic Source Routing Protocol，DSDV）、按需驱动距离矢量路由协议（Ad Hoc On-Demand Distance Vector Routing，AODV）等。
- 组播：源节点与目的节点一对多或者多对多。组播路由协议是实现组播的基础，其功能主要是形成一定的机制（如构造组播分发树或形成组播网络等）来完成组播路由任务。根据通往组成员的路由产生方法的不同，无线自组织网络组播路由协议又可分为基于树的组播路由协议、基于网格的组播路由协议、混合的组播路由协议、无状态组播路由协议、地理组播路由协议。
- 选播：在一个源客户端和用同一个选播地址标识的多个目的服务器中最近者之间的分组流。多个服务器用同一个选播地址表示，提供同样服务。
- 广播：发送给除本节点之外的所有其他节点。包括泛洪、基于概率的广播协议、基于区域的广播协议和基于邻居信息的广播协议。
- 根据信道数量不同进行分类
- 单信道
- 双信道
- 根据路由发现策略不同进行分类
- 主动式路由（表驱动式路由 Table Driven）。在主动式路由协议中，网络中每一个节点都要周期性地向其他节点交换路由信息，并且每一个节点都要保存路由表。当网络拓扑结构发生变化时，节点就在全网内广播路由更新信息，这样每一个节点就能连续不断地获得网络信息。
- 按需路由（被动式路由），按需路由协议仅在需要路由时才由源节点来创建，因而拓扑结构和路由表内容是按需建立的，通信过程中维护路由，通信完毕后便不再进行维护。通常按需路由包括3个过程：路由发现、路由维护和路由拆除。
- 混合路由，小范围内使用主动路由协议，局部区域之间采用按需路由协议。
- 根据是否使用GPS等提供的定位信息进行分类
- 根据网络采用的拓扑结构不同进行分类
- 平面路由协议：其网络拓扑结构是平面结构，源节点与目的节点间存在多条可用路由，所有节点地位对等，功能相同。节点之间通信由网络所有节点共同协作完成。完全分布式控制，可靠性高。包括所有主动路由协议和按需路由协议。
- 分级路由协议：网络的拓扑结构具有层次性，即把节点划分为不同的集群并对群内外节点指定不同功能。用于减少参与路由计算的节点数，减少节点路由表的尺寸。并且通过某种集群形成策略，产生一个较为稳定的子网。
- 根据单个源-目的节点对创建的路由数量不同进行分类
- 单路径路由协议
- 多路径路由协议
- 根据节点上装备的无线网络接口设备的数量不同进行分类
- 单接口方式
- 多接口方式
移动Ad Hoc网络路由协议及其应用#
什么是移动Ad Hoc网络#
移动Ad Hoc网络是一种不需要任何基站或固定基础设施的多跳无线网络，具有自组织，动态拓扑，资源受限，多跳路由等特点。 其所具有的特点对其路由协议设计提出以下要求：
- 适应动态拓扑，其网络拓扑结构动态变化，对路由协议收敛造成很大困难。必须对拓扑变化具有快速反应能力。
- 支持单向信道，在移动Ad Hoc环境中可能出现单向信道。
- 提供无环路由，提供无环路由是对路由协议的一项基本要求。
- 避免无穷计算，链路失效可能导致无穷计算出现
- 节约终端资源
- 简单实用
几种经典的移动Ad Hoc网络路由协议
DSDV 路由协议 目的序号距离矢量路由。它是传统Bellman-Ford路由协议改进，通过给每个路由设定序号避免路由环产生。
DSDV路由协议的基本原理是通过设定目的节点序列号解决距离向量DV中的循环和无限计数问题，通过相邻节点之间周期性交换路由表信息更新路由，每个节点维护一张包含到达目的节点信息的路由表。DSDV路由协议的路由表更新主要有两种：一种是全更新，即拓扑更新消息中将包括整个路由表，这种方式主要适合网络拓扑变化较快的情况；另一种是部分更新，即更新消息中仅包含变化的部分，通常适合网络拓扑变化较慢的情况。
其运作机制包括：路由表建立、路由维护以及链路中断检测
- 路由表建立：当网络建立或者网络中有新的节点加入时，节点便通过广播的方式通知其他节点本节点的加入，收到广播的节点便会把相应的路由信息添加到路由表中，完成对自己路由表的更新过程，然后发送新建立的路由表。一段时间后，网络中的每个节点便都建立了一个完整的路由表，表中包含了所有可达节点的路由。路由表中包含的信息包括目的节点地址、下一跳地址、路由跳数、目的节点序列号及路由建立时间等。每次发出信息时，每个节点会在信息中注明本节点的信息序号，以便于确定信息的新旧。这样就可以避免普通的Bellman Ford路由协议中的成环问题。
- 路由表维护：每个系欸但周期性将本地路由表信息发送给邻居节点，或者当其路由表发生变化时，立即将其路由信息发送给邻居节点。接收到该分组的节点，确认是新消息，将其路由跳数+1再发送出去。知道每个节点都收到该分组的拷贝。当邻居节点收到包含新路由信息表的广播信息后，先比较源节点、目的节点路由序列号的大小，具有更大序列号的路由信息总是优先接收，而目的节点路由序列号小的路由被淘汰。如果两个更新分组有相同的序列号，选择跳数（Metric）较小的分组，而使路由最优。
- 链路中断检测：链路中断可以通过两方面检测，一方面是通信硬件，数据链路层检测到中断后向路由层发送报告。另一方面是通过时间推断。
这个协议的优点是非常简单，采用序列号机制避免路由环路产生。主要适用于网络规模不大且拓扑变化缓慢的网络环境，且不支持单向信道。
AODV路由协议 Ad Hoc On-Demand Distance Vector Routing 按需距离矢量路由。它结合理论DSR和DSDV的优点，处理过程存储过程很小，可以对链路状态变化做出快速反应。
按需路由，仅当源节点需要向目的节点发送数据时，才在节点之间建立路由，源节点通过产生路由请求报文EERQ建立反向路由；；中间节点首次收到请求报文RREQ后进行广播转发，利用请求报文RREQ中节点序列号避免路由环的产生；目的节点在收到报文RREQ后产生路由应答报文RREP建立正向路由；断路节点产生路由错误报文RRER更新路由信息。
主要步骤包括路由发现和路由维护两个过程：
- 路由发现过程：当源节点S有数据需要发送时，首先查找自己的路由表，当路由表中存在到目的节点D的有效路由时则按照该路由发送数据。否则发送路由请求过程。广播的保温包括源节点地址，目的节点地址，目的节点序列号，跳数和生存时间。由于是广播的方式，如果中间节点重复收到自然要丢弃后面的报文。而目的节点收到之后按照已建立的反向路由发送给源节点。
- 路由维护过程：由于自组网的特性，已建立的网络拓扑结构会随着节点移动而改变。AODV通过多种手段进行路由维护，包括定期发送hello报文检测本地连接，链路本地修复及链路本地修复失败后向源节点发送报文通知链路断开。
AODV路由协议思路简单易懂，支持中间节点应答，能使源节点迅速获得路由，有效减少广播数量。节点只存储需要的路由，减少了内存要求和不要的复制。缺点是需要的建路时延比较长，不支持单向信道，中间节点可能出现过期路由。
OLSR路由协议 Optimized Link State Routing Protocol 最优化链路状态路由协议，对经典链路撞他协议进行优化而成。核心思想通过多点中继机制减少分组消息的发送。协议通过节点之间Hello分组的周期性交互，执行链路检测，邻居发现功能。通过拓扑控制分组的周期性交互执行MPR信息声明功能。最终以这些分组建立起来的拓扑结构为基础，进行基于MPR的路由计算。OLSR路由协议利用MPR系欸但转发达到减少控制分组的的目的。
所谓MPR时每个节点从自己的一跳邻居当中，选出的最小转发点集合——这些被选中的邻居负责代为转发该节点的控制消息。MPR是节点特定的，每个节点通过MPR selector set知道谁把本节点当MPR。MPR存在的目的就是为了让每个节点可以发出最少的消息从而覆盖全部两跳邻居。
主要步骤包括路由信息交互，路由计算与选择，数据分发三部分
- 路由信息交互：网络节点间周期性交互各种控制分组，通过分布式计算更新和建立自己的网络拓扑图。节点周期性交换的控制分组包括Hello分组和TC分组。Hello分组用于发布本链路状态信息，内容包括节点的1跳邻居节点信息，且连接信息不会被转发。TC分组用于发布本链路状态信息，会被广播到全网，其内容包括将发送TC分组的节点选为MPR的邻居节点的信息。OLSR中，每个节点在1跳邻居节点中选择部分节点作为MPR节点。只有MPR节点才会周期性地广播TC分组，也只有MPR节点才会转发TC分组。并且它对路由协议进行了以下改进： - MPR泛洪代替经典泛洪。只有MPR节点才会转发广播控制分组。也只有MPR节点才会转发控制分组。控制了泛洪的规模。 - 广播消息指包含部分链路状态信息。MPR泛洪广播不包括节点与全部邻居节点之间的链路信息，只包含与MPR Selector之间的链路状态信息。 - 用对称和不对称描述邻居节点状态。如果节点收到邻居发来的消息，又通过收到的消息知道邻居节点收到了自己发出的消息，该邻居节点状态就标为对称，否则是非对称。这样，对称邻居节点之间存在双向链路，否则可能存在单向链路，应该在选择路由时避开。
- 路由计算与维护：OLSR需要三张表：邻居表，拓扑表和路由表。OLSR根据收到的Hello分组和TC分组创建并更新邻居表和拓扑表，然后根据邻居表和拓扑表内容创建和更新路由表。在计算路由时只有MPR节点才会参与，根据最短路由路径优先原则，它采取了从目的节点倒推MPR节点的搜索方式。
- 数据分组转发：OLSR采用逐条转发的方式转发分组，每一个中间节点在转发数据分组时都要重新为其寻路。寻路的方法是在节点的路由表中查询目的节点对应的吓一跳节点，如果找到，则将数据分组转发出去，如果没有找到下一跳节点，那么就将其丢弃或者另作处理。
OLSR是一种主动式路由协议，节点在数据传输时已经存在到达目的节点的路径信息，具有路径选择等待时延小的优点。协议采用中继节点转发机制，减少由于链路状态信息泛洪带来的路由开销。缺点是OLSR不管链路状态是否变化，拓扑控制信息都采用周期性泛洪，开销大，不适用于节点稀疏的网络场景。
现在我对这个协议的TC消息，拓扑表的构建过程还不够了解
batman-adv#
为了充分研究移动自组网相关内容。我们首先从一个具体的自组网框架开始。我选择了batman-adv，这个框架是最常用的开源二层Mesh协议，在家庭/企业Mesh路由器和社区无线领域占据主流。但是在无人机，车载和工业移动机器人领域OSLR和Babel更为合适。
Anyway，我们需要先弄清楚所谓移动自组网究竟是怎么一回事。
什么是batman-adv#
batman-adv是BATMAN路由协议在二层（数据链路层）运行的Linux内核模块实现。其他的无线路由协议实现都在第三层工作，也就是说它们会通过发送UDP数据包来交换路由信息，并通过操纵内核路由表来使其路由决策生效。而batman-adv完全在第二层运行，不仅路由信息通过原始以太网帧传输，而且数据流量也由batman-adv处理。它封装并转发所有流量，直到到达目的地，从而模拟一个由所有参与节点组成的虚拟网络交换机。因此，所有节点都表现为链路本地节点，既不了解网络拓扑，也不受任何网络变化的影响。
理解它的最简单方式是将其想象成一个分布式交换机，每个运行batman-adv的系统都相当于一个交换机端口。每个节点都运行着一个 batman-adv 实例。这样的实例是一个虚拟网络接口（通常称为 “bat0”），在系统看来它就像是一个交换机端口，允许访问分布式交换机。节点之间（直接或间接）通信的实际细节则被隐藏在 “bat0” 网络接口背后。
首先，batman-adv工作在第二层，也就是数据链路层。第三层则是网络层。看来无线自组网也是遵循OSI 7层协议的。batman-adv工作在第二层，虚拟出了一个巨大的交换机，每一个设备都以为其他节点都连在同一个巨型交换机上，也就是所谓的“链路本地link local”。例如 A——B——C之间，A和C需要经过B中转，但是节点A会误以为可以直达C。
batman-adv具有一些有趣的特性：
- 网络层无关，可以在batman-adv上运行任何想要的协议
- 节点无需IP即可参与Mesh网络
- 轻松继承非Mesh（移动）客户端
- 支持非Mesh客户端漫游
- 优化流经Mesh的数据流
- 在Mesh和非Mesh客户端上与逆行依赖广播/组播的协议。
这里一直提到Mesh，所谓Mesh其字面意义就是像蜘蛛网一样，由许多节点互相连接形成的网络，没有严格的中心枢纽。 其技术定义是一种网络拓扑，其中每个节点都可以作为路由器为其他节点转发数据，支持多跳通信以扩展覆盖范围。
Ad-hoc是Mesh的哲学基础，Mesh是Ad-hoc的工程化实现。
Mesh具有四大特征：
- 多跳，数据通过中间节点接力传输
- 自组织，开机后自动发现邻居，协商拓扑
- 自愈，某个节点故障，网络自动绕路
- 去中心化，没有单点故障的网关
batman-adv 到底是用来做什么的？#
如何使用batman-adv呢？
配置端口#
首先需要高速batman-adv使用哪个端口来构建mesh网络。可以是Wifi wlanX，也可以是普通以太网设备ethX，甚至可以是蓝牙。
配置好之后就有一个bat0。bat0显然是一个虚拟的接口。需要给接口配置IP地址，也就是将接口和IP地址关联起来。以手动配置，也可以通过dhcpv4、avahi自动配置、dhcpv6或ipv6自动配置。任何进入此接口的数据包，都会被batman-adv内核模块根据其目标MAC地址进行检查，然后借助B.A.T.M.A.N.的路由“黑魔法”进行转发，最终神奇地从目标节点的bat0接口冒出来。
这里需要注意一下，batman-adv工作在第二层，配了IP的bat0仍然是第二层，是一个有IP的二层交换机。IP+接口。相当于mesh网络的身份证。如果不给bat0配置IP就只能作为网络中继。