移动ad hoc网络
•移动Ad hoc网络/多跳无线网络
▫由一组带有无线通信收发装置的移动终端节点（只有移动终端，承担中转）组成
▫网络中每个终端可以自由移动、地位相等
▫是一个多跳、临时、无中心网络
▫不需要现有信息基础网络设施的支持
▫可以在任何时候、任何地点快速构建起来的移动通信网络
没有专门承担中转的设备
移动ad hoc网络的特点
•具备移动通信网络和计算机网络的特点
▫移动通信和计算机网络相结合
▫报文交换采用分组交换机制
▫用户终端是配有无线收发设备的移动便携式终端
▫作为主机要运行面向用户的应用程序
▫作为路由器要运行相应的路由协议（距离矢量：RIP，链路状态：OSPF）
▫终端之间的路由通常通过多个中间节点的转发来完成
移动ad hoc网络的特点
•网络拓扑动态变化
▫用户终端随意移动
▫节点的开机/关机
▫无线电发送功率变化
▫无线信道间互相干扰
▫地形等综合因素影响
•多跳组网方式
▫接收端和发送端可使用比两者直接通信小得多的功率进行通信，因此大大节约电池能量的消耗。
▫中间节点参与分组转发，能有效降低对无线传输设备的设计难度和成本，同时扩大了自组网络的覆盖范围。
•有限的无线传输带宽
▫无线信道能提供的网络带宽比有线信道要低很多
▫竞争共享无线信道产生的碰撞
▫信号衰落、噪声干扰以及信道之间干扰等
•移动终端的自主性
▫自组网络的移动终端之间存在某种协同工作关系
▫每个终端都将承担为其它终端进行分组转发的义务
•安全性差
▫无线链路使ad
hoc网络容易受到链路层的攻击
▫节点漫游时缺乏物理保护
▫移动性使得节点之间的信任关系经常变化
•网络的可扩展性不强
▫节点之间的相互干扰造成网络容量下降
▫各节点吞吐量随网络节点总数的增加而下降
•存在单向的无线信道
▫无线终端发射功率的不同以及地形环境的影响
•生存时间短
移动ad hoc网络与其他网络比较
•与分组无线网、无线局域网、红外网络比较
▫单跳与多跳
�WLAN、红外网络都是单跳网络，不存在路由问题
▫研究重点不同
�Ad
hoc网络的研究内容主要以路由协议为核心的网络层设计
▫通信模式不同
�ad
hoc移动终端的通信是对等的
ad hoc网络面临的问题
•特殊的信道共享方式
▫共享信道（MAC层问题）
▫“隐藏终端”/“暴露终端”（无线信号一定有的问题）
•动态变化网络拓扑
▫常规路由协议花较高代价（带宽、能源、CPU等）获得的路由信息可能已经陈旧
•有限的无线传输带宽
▫减少节点之间交换的信息量
▫减少控制信息带来的附加开销
实现ad hoc网络的关键技术
•路由协议
▫感知网络拓扑结构的变化
▫维护网络拓扑的连接
▫高度自适应的路由
▫广播和多播
•服务质量
•功率控制
▫信道接入技术
▫能耗节约机制
•安全问题
•Ad hoc网络的互联
▫多个ad hoc网络互联
▫内部节点访问Internet功能
•Ad hoc网络的资源管理
•传输层服务的性能
Ad hoc路由面临的困难
•路由信息不易获得
▫定期交换路由信息或者按需搜索路由的开销大
▫网络资源有限，并且必须被所有节点共享
▫节点资源（电池、CPU等）也是有限
▫也许不可能收集齐所有的路由信息
•路由信息不完整
▫由于移动和分区很难将信息分发到一个没有固定成员
•网络的所有节点路由信息可能过期
▫不可能连续地或者立即地交换信息
▫节点随时移动
▫无线传播变化很大
常规路由协议是否可用？
•常规路由协议不是为高移动性和低带宽网络设计的
•DV算法（距离矢量）存在“无穷计算”问题和慢收敛
•采用泛洪技术的（链路状态）协议造成额外的通信和控制开销
•常规路由协议周期性地路由更新消耗大量的网络带宽和节点能源
•当网络节点失效和网络分区时形成路由回路（解决：设定一个限制，超过限制丢弃）
•无线终端功率的差异以及无线信道的干扰导致单向信道的存在
Ad hoc路由协议分类
•平面路由
▫无需建立具有特殊cluster头功能节点的层次结构；
▫不划分区域以及所谓的区内/外不同路由
▫所有的节点在路由机制中地位平等
▫寻址方式是平面的
•层次路由
▫节点功能不同
▫寻址方式是分层进行的
•地理信息辅助路由
▫利用地理信息进行路由选择
按需（on-demand）路由协议
•反应式（reactive）路由
▫在源端需要时候通过路由发现过程来确定路由
�控制信息采用泛洪（flooding）方式
�路由请求延迟高
�路由开销低
•两种实现技术
▫源路由（使数据包沿源路由中路传递）（报文头携带完整的路由信息）
▫hop-hop路由
•DSR、AODV
表驱动（table driven）路由（主动路由 距离矢量，链路状态）
•先应式（proactive）路由
▫传统的分布式最短路径路由协议
�链路状态或者距离向量
�所有节点连续更新“可达”信息
•每个节点维护到网络中所有节点的路由
•所有路由都已经存在并且随时可用
•路由请求的延迟低
•路由开销高（维持路由表的最新状态）
•OLSR、TBRPF
OSPF：
1、洪泛更新
2、最优即为最优
3、延迟大
4、开销大
距离矢量（Distance-Vector）
（优点：开销小）
（缺点：最优路径未必是最优，通知速度不够快，无穷计算环路问题）
•基于分布式的Bellman-Ford算法
•每个节点维持一张路由表
▫所有可达目的地（目的网络）
▫到目的地的下一跳
▫到达目的地的跳计数（指明最优）
•定期把路由表发给所有的邻居一边
DV协议能否适应MANET？
•DV的固有缺点
▫无法发现路由回路
▫“无穷计算”问题
•可选方法：DSDV协议
▫没有全局拓扑视图
▫主动先应式路由
▫每个节点维护到所有已知目的地的路由信息
▫路由信息必须定期更新
▫即使网络拓扑没有变化也有通信开销
▫维护的路由可能从来不用
DSDV协议特点
•保持了DV算法的简单性
•确保无路由回路（不存在无穷计算）
▫新的路由表带有目的地序列号
•对于拓扑变化能快速反应
▫当路由表发生重大变化时立即启动route
advertisement
▫但是等待不稳定路由的通告(减缓路由波动)？
路由通告（route advertisement）（环路问题：归根结底是由于周期性更新）
•向每个邻居通告自己的路由信息
▫目的地地址
▫metric
= 到目的地的跳计数
▫目的地的序号
•设置序号的规则
▫每次通告递增自己的目的地序号（只用偶数值）
▫如果一个节点不再可达(timeout)，则将该节点的序号递增1(奇数值)并置metric
路由选择(Route Selection)
•将收到的路由更新信息与自己的路由表比较
▫选择目的地序号大的路由(这样能确保使用的总是来自目的地的最新路由信息)
▫如果目的地序号相同，则选择具有较小metric值的路由。
DSDV总结
•优点
▫非常简单（几乎与DV算法一致）
▫通过目的地赋予的序号值来防止出现路由回环
▫不存在路由发现带来的延迟
•缺点
▫没有节点睡眠
▫开销：多数路由信息从不使用
动态源路由协议（DSR）
•Dynamic Source Routing protocol
▫基于源路由概念的按需自适应路由协议
▫允许节点动态发现到任何目的地source route
▫中间节点不必存储转发分组所需的路由信息
▫采用Cache存放路由信息
▫允许网络完全自我组织和自我配置
▫因其简单而有效成为首选协议
▫网络开销较小
▫存在陈旧路由
DSR协议假设（网卡，工作在混杂模式下，所有包都交给上层处理）
•所有节点都愿意参与协议工作
•节点收到损坏分组时能检测出来并丢弃
•节点的移动速度相对于分组的传输延迟以及底层网络硬件的无限传输范围来说相对温和
•节点的无线网络接口硬件可以promiscuous方式工作
▫接口将收到的每个帧都上交给驱动器软件而不会针对目的地址进行过滤
•任何一对节点之间的无线通信能力可不同
•每个节点只能宣称一个IP地址
DSR协议描述
•DSR协议由两个相互协同的机制组成
▫Route discovery（路由发现）
�由需要发送数据给节点D的节点S使用；
�该过程只在S需要发送数据并且不知道到D的路由时才启动；
▫Route maintenance（路由维护）
�节点S在给D发送数据时要能检测出由于网络拓扑动态变化导致源路由中断的情况；
�当前的源路由不能用时S切换到另一条已知的路由或者重新发起route discovery寻找新路由
按需操作的优点
•路由发现和维护都是按需进行的
▫不需要周期性地通告路由
▫不需要感测链路状态
▫不需要邻居检测
▫不依赖于任何底层协议
•按需操作没有周期性通告的优点（路由最大的开销是通告）
▫DSR的开销在网络中多数节点相对位置近似不变的情况下接近0
▫随着节点的移动通信模式的变化DSR的路由包开销能自动扩展成当前使用的路由情况
DSR的多路径思想
•多路径获得的途径
▫作为route discovery的响应
▫其他路由控制包和数据包中的路由信息
▫为任何目的地缓存多条路由
•多路径的作用（主要开销来自discovery）
▫如果正在使用的一条路径中断，节点可立即切换到另一条缓存的路由
▫多条路由的缓存可避免每次路由中断后执行route discovery
基本route discovery
•S源节点A将路由请求（Route Request）消息作为局部广播分组发送
▫Route discovery的发起者A
▫Route discovery的目标E
▫Request id
▫List(初始为空)：用来记录路由发现包经过的节点
•所有位于A无线传输范围内的节点都将收到该路由请求包
•如果目标节点E收到该请求包，给请求源A回答一个ROUTE REPLY消息
▫List：拷贝自ROUTE REQUEST
•路由发现源收到ROUTE REPLY消息后在本地Route Cache中缓存路由信息
•无穷迭代的路由发现过程
▫如果目标端在route
cache中没有找到去往路由发起端的路由信息，并且网络存在单向链路
▫则需要发起新一轮route discovery过程（若在C中断，则在C发起discovery）
•DSR规定目标端（E）可使用ROUTE REQUEST消息中记录的路由作为返回的ROUTE REPLY的源路由；
▫首选逆向路由可避免有可能的第二次路由发现过程带来的开销
•DSR规定目标端在发起逆向返回到源端的新一轮routediscovery时，在ROUTE REQUEST中“捎带”ROUTE REPLY消息；
基本route maintenance
•路由的维护
▫每个节点确保使用源路由发送/转发的数据分组被路由中的下一跳接收；
▫如果没有收到下一跳的确认则不断重发（至最大重试次数）
•如何确保数据报被逐跳转发？
▫链路级的确认（IEEE802.11）
▫被动确认（B侦听C向D转发）
▫要求DSR软件返回确认
•如果数据分组被重发了最大次数仍然没有收到下一跳的确认，则节点（C）要向分组的源端发送ROUTE ERROR消息，并指明中断的链路；
•分组的源端（A）将该路由从路由缓存中删除；
•如果源端路由缓存中存在另一条到目标的路由则重发此分组；
•否则，重新开始route discovery过程；
路由发现的其他特点
•缓存转发获得的路由信息
▫ROUTE REQUEST
�记录了一条从路由发现发起端到本节点的路由
▫ROUTE REPLY
�给出一条从目标端到路由发现发起端的反向路由
▫数据分组
�给出一条从数据报源端到目标端的正向路由
•使用缓存的路由响应ROUTE REQUEST
▫收到路由请求包的中间节点可用自己route
cache 缓存的到目标节点的路由信息应答路由请求；
▫ROUTE REPLY中的路由记录=ROUTE REQUEST中的list
+ 缓存的路由
▫在返回ROUTE REPLY之前要检查是否存在路由环路
•ROUTE REPLY风暴
▫节点广播一个针对某目标端的路由请求，当其邻居的cache中都有该目标端的路由时，每个邻居都试图以自己的缓存路由响应，由此造成应答风暴；
•风暴将浪费网络带宽
•风暴将加剧局部网络冲突
•预防ROUTE REPLY风暴
▫节点将网络接口置于promiscuous接收方式；（在混杂模式下通过监测）
▫延迟发送ROUTE REPLY；
▫同时侦听路由请求端是否在用更短的路径发送；
•ROUTE REQUEST的跳数限制（太长的不传）
▫ROUTE REQUEST消息中的hop limit字段限制了转发该路由请求消息的中间节点数量；
•非传播ROUTE REQUEST消息
▫Hop limit = 0可用来确定目标节点是否在路由发现发起端的邻居；
▫Hop limit = 0可用来确定路由发现发起端的邻居是否有缓存的路由；
▫如果在一定的时间间隔内没有收到ROUTE REPLY消息，则采用广播ROUTE REQUEST消息；
•扩展环搜索(expanding ring)
▫逐步递增hop limit的值（limit递加：防止不停的传播，减少discovery在网络的传播，减少开销）
•营救(salvaging)分组
▫如果节点在自己的缓存路由中发现有到目标的路由，则在报告ROUTE ERROR之后努力营救分组；
▫两种方式
�将分组的源路由替换成缓存的路径；
�保留分组源路由的前缀，用缓存的路由替换分组源路由的后缀；
•路由最短自动化
▫数据分组使用的源路由在一个或多个中间节点不需要时能自动实行路由最短化
▫节点给数据分组的源端发回一个免费的ROUTE REPLY消息（不用request，直接reply）
•增加ROUTE ERROR消息的扩展范围
▫当一个节点收到ROUTE ERROR而本地cache内没有第二条路由时，要发起新一轮的ROUTE REQUEST；
▫新ROUTE REQUEST消息“捎带”ROUTE ERROR消息内容以便通告所有邻居特定链路中断情况；
▫由此保证之后收到的ROUTE REPLY不是原来的过时路由
•缓存否定信息
▫节点收到ROUTE ERROR后不是简单地删除该路由，而是将特定链路中断信息缓存一段时间；
▫随后收到的所有包含该中断链路的路由都很容易判断为不可用；
▫缓存的链路中断信息必须超时删除，以便在该链路恢复工作时可用；
DSR协议优点（类似洪泛，但耗带宽）
•节点不需要周期性地发送路由广播分组
•无须维持到全网所有节点的路由信息
▫节省了电池能量和网络带宽，尤其是当没有节点要发送数据时，网络中没有通信开销。
•仅需要维护路径上节点之间的路由
•能完全地消除路由环路
•能同时提供多条路由
•可用于单向信道
•中间节点的应答使源节点快速获得路由（list写入了源路由，成为最大开销）
cluster （分簇）
zone（分区）
分区路由协议（ZRP）
•Zone Routing Protocol
•zone的划分
▫整个网络被分成若干个以节点为中心、一定跳数为半径的zone；
▫zone内节点数与设定的区半径有关
•路由策略
▫混合使用了主动和按需源路由策略
▫域内的节点通信使用域内路由协议
▫跨域节点通信使用域间路由协议
AS：是管理层的分区
域半径和路由域
•域半径(zone radius)
▫指定每个节点维护的域，以跳计数；
•路由域(routing zone)
▫所有包含在域半径内的节点
•边界节点(peripheral/border)
▫最小距离正好等于域半径的节点
域路由架构
•区内路由协议（IARP,IntrAzoneRouting Protocol）
▫采用传统的主动路由法
▫支持距离向量和链路状态两种路由策略
▫节点之间通过周期性地交互路由表获得到zone内各节点的最新路由
•区间路由协议（IERP,IntErzoneRouting Protocol）
▫采用按需路由协议
▫负责寻找区外节点的路由
•边界传播（BRP, BordercastResolution Protocol
▫BRP协议使得路由查询分组只在边界节点之间广播（减少开销）
•BRP
(BordercastResolution Protocol)
▫使用IARP提供的拓扑信息组播路由查询包到外围节点
▫Bordercast接收者在边界广播查询包到自己的外围节点，直至发现一条到目标的路由。
•IARP
采用主动策略维护本地路由信息；
•构造路由域的前提是了解自己的邻居
▫通过MAC协议
▫通过邻居发现协议(NDP)
•每个节点给域内一些节点发送“zone building packets”
▫使得节点了解自己的发送域
•每个节点将路由更新包的TTL设置为域内最远节点的距离
域间路由协议（IERP）
•Interzone Routing Protocol
▫域间路由发现基于BRP（边界前一个节点广播，边界再按需传）
▫按需发现全局路由
▫当本地没有数据报的目的地路由时进行路由发现过程
�数据报源产生一个路由查询包
�该查询包被边界广播算法确定一组节点中继
�收到查询包的节点检查目标节点是否在自己的路由域中，或者本地路由cache中是否存有目标路由信息
�有则返回一个路由响应包给源端
�没有则边界广播查询包
ZRP路由实例
•如果目的节点不属于Z(S)（M不属于Z，则S发请求给C，E再建立自己的区），则源节点S发路由请求给本域的边界节点；
•这些节点在各自的路由域中查找是否有到目的地的路由
“隐藏”节点问题（有线网络无隐藏节点）
•假设：A正在向B传输数据，C也要向B发送数据。
•隐藏节点不能侦听到发送端但能干扰接收端。
MAC解决冲突问题
移动Ad Hoc网络的MAC层
•在移动Ad Hoc网络中，节点移动、无线信道脆弱、缺乏中心协调机制是在设计MAC协议时必须仔细考虑的问题。
目前有以下三类：
▫竞争协议(Contention Protocol)；
▫分配协议(Allocation Protocol )；
▫混合协议(Hybrid Protocol)(竞争协议和分配协议的组合协议)。
mac以太网：载波监听加碰撞监测协议
•竞争协议(ContentionProtocol)：
使用直接竞争来决定信道访问权，通过重传机制解决碰撞问题；目前有以下四种协议：（最传统的）
▫1．ALOHA协议；
▫2．载波侦听多址访问协议(CSMA)；
▫3．基于控制分组握手的访问控制协议；
▫4. 忙音类多址访问协议。
•ALOHA协议（随机）：以强制性的争夺方式共享信道带宽，碰撞问题严重，需要反馈机制保证分组交付；
▫当传输点有数据需要传送的时候，立即向通讯频道传送。
▫接收点在收到数据后，ACK传输点。
▫如果接收的数据有错误，接收点会向传输点发送NACK。
▫当两个传输点同时向
频道传输数据时，
发生冲突，各自等待
一段随机长度时间后
，再次尝试传送。（随机窗口，发随机数，谁短谁发）
•时隙化ALOHA协议：将信道分为若干个时隙，强迫每个节点一直等到一个时隙开头的时候才开始发送其分组；
•时隙化ALOHA协议的一个改进版，即持续参数p的时隙化ALOHA协议，使用持续参数p(0<p<1)来确定一个节点在一个时隙内发送一个分组的概率。减小持续参数p，可以减少碰撞次数，但同时却增大了时延。（效率降低，时延增大）
•载波侦听多址访问协议(CSMA) ：
▫持续载波侦听多址访问：连续不断地侦听信道，信道空闲后立刻发送分组，若有冲突则等待随机时间后再侦听，
▫优点：减少了信道空闲时间；
▫缺点：增加了发生冲突的概率；
▫非持续载波侦听多址访问：随机地侦听信道，信道空闲后立刻发送分组，当检测信道忙时，随机时间后重新检测信道，直到发现信道空闲；
▫优点：减少了冲突的概率；
▫缺点：增加了信道空闲时间，数据发送延迟增大；
•载波侦听多址访问协议(CSMA)：对以上两种方式的改进
•持续参数p的载波侦听多址访问：适用于分时隙信道，连续不断地侦听信道，若介质空闲，便以概率p发送数据，以概率1-p把数据发送推迟到下一个时间片；如果下一个时间片介质仍然空闲，便再次以概率p发送数据，以概率1-p将其推迟到下下一个时间片。若介质忙，那么它就等到下一个时间片继续侦听介质；
•载波侦听通过测试发射机附近的信号强度来努力避免碰撞。但碰撞的发生不是在发送方一侧，而是在接收方一侧。易导致 “隐含终端”问题。
•基于控制分组握手的访问控制协议:
•(1)多址访问与碰撞回避(MACA)协议:
▫发送数据前先向接收者发送RTS帧，帧中包含将要发送的分组的长度；
▫接收者收到RTS后，回送CTS帧，并将长度消息捎回；收到CTS后，发送者开始发送数据。
▫收到RTS/CTS的其它节点在传输时间内不发送任何消息。
▫冲突后遵循，指数退避。
（2）MACAW协议：
在MACA上，增加确认数据包，用RTS-CTS-DS-Data-ACK 实现媒质的冲突检测。缺点：手续过于复杂
•多址访问与碰撞回避(MACA)协议:
▫优点：
▫提高了无线信道的利用率：仅会发生长度比数据帧小得多的RTS/CTS帧的冲突，冲突几率降低；
▫部分解决了隐终端问题；
▫缺点：
▫不能解决控制分组之间(RTS-CTS)的冲突问题；
▫无链路层确认机制（无 ACK），发生冲突时需上 层超时重发，效率低；
▫错误阻塞。
•基于控制分组握手的访问控制协议:
•(4)IEEE 802.11（WIFI） MAC协议：不同时隙结合CSMA/CA；
•(5)MACA-BI协议（准许式多址访问与碰撞回避协议）基于MACA的收方主动的信道接入协议，接收方轮询其他节点是否有数据要发送，只有接到RTR(ready to receive)邀请的节点才能发送数据。
▫MACA-BI减少了握手次数，从而在高速、短距离的AD HOC网络中提高了吞吐量；
▫为了防止冲突需要共享相邻节点的传输特征表。
•忙音类多址访问协议（数据链路层）
•(1)忙音多址访问协议(BTMA):带宽划分为两个独立的信道
▫数据信道：传输数据分组，占大半带宽，
▫控制信道：传输特殊的忙音信号，忙音信号用于表示数据信道上出现数据发送；
▫节点发送数据前先收听控制信道上的忙音信号，若无忙音信号，则发送数据，同时其他节点检测到数据信道上的数据发送后，立即开始往控制信道上发送忙音信号，直到数据信道上的发送停止；
▫若有忙音信号，则随机时间后再发送；
▫优点：防止了隐藏接点的干扰，和RTS/CTS碰撞率；
▫缺点：暴露节点问题增加，信道利用率不足；
（2）双忙音多址访问协议（DBTMA）
收一个发一个
•分配类协议：
▫静态分配协议：集中式传输时间安排算法，事先为每个节点静态地分配一个固定的传输时间安排。
▫动态分配协议：使用分布式传输时间安排算法，按需计算传输时间安排。
•时分多址访问协议(TDMA)
•五步预留协议(FPRP)
•跳频预留多址访问协议(HRMA)
