1.3.4　路由协议

1. 基本概念

在自组网中，数据需要通过多跳通信方式传输，因此路径选择算法是网络层设计的一个主要任务。路由协议是自组网的关键技术之一，主要负责寻找一条从源节点到目的节点的最优路径以满足不同服务质量。数据分组将沿该路径进行转发和传输。

2. 主要分类

当前自组网路由协议主要分为基于网络拓扑路由协议、基于地理位置信息路由协议和基于机器学习路由协议。

（1）基于网络拓扑路由协议

基于网络拓扑路由又可分为静态路由、主动路由、按需路由和混合式路由四类。

静态路由基于固定的路由表路由，仅适用于网络拓扑不变的业务环境，对网络拓扑变化的业务环境是不适用的。常见的静态路由包括负载携带和传递路由（Load Carry and Deliver Routing，LCAD）[16]与数据中心路由（Data Centric Routing，DCR）。LCAD是自组网发展初期使用的静态路由算法，其优点是可同时增强网络安全和提高网络吞吐量；缺点是平均端对端时延随网络成员之间通信视距的扩大而迅速上升。DCR可满足小规模自组网中多对一的分组传递要求，但不适用于大规模组网。

主动路由可定期更新路由表，因网络中的每个节点都有现成的路由表可供即时选择路径，平均端对端时延会很低；缺点是网络收敛所需时间长、控制开销大。典型的主动路由协议有目标序列距离矢量路由协议（Destination-Sequenced Distance-Vector，DSDV）[17]，该协议把路由的序列号作为第一属性、跳数作为第二属性进行优先选择，但是当网络拓扑高速变化时，无论节点是否发送数据都必须进行周期性更新，网络控制开销会增大；此外，各个节点都必须保留到达全部节点的路由，严重占用内存。

按需路由协议在传输数据前才查询传输路径，优点是能够降低控制开销，缺点是没有现成的路由表供即时传输路径选择，导致端对端时延高。常用于自组网的按需路由协议有基于时隙请求的按需距离矢量路由（Ad hoc On-demand Distance Vector，AODV）[18]，AODV为每个网络成员单独分配转发时隙，可有效提高数据转发的成功率，但控制开销较大。

混合路由是由主动路由和按需路由融合而成的路由，集合了主动路由低时延和按需路由网络控制开销低的优点，主要适用于网络拓扑结构稳定的网络。区域路由（Zone Routing，ZR）[19]是这类路由的典型代表；ZR在小尺度范围采用主动路由，在大尺度范围采用按需路由，以提升网络的扩展能力。

由于自组网具有动态变化的网络拓扑结构特征，基于网络拓扑路由协议会带来较大的路由开销，因而基于地理位置信息的路由成为提升路由性能的主要选项。

（2）基于地理位置信息路由协议

GPSR[20]是由Harvard University的著名学者Brad Karp领导的研究小组提出的以地理信息为基础的路由协议，近年来被广泛地用于自组网领域。该协议以网络节点的地理信息为依据来制定数据包传送策略和传输路径。Shirani R. 等人通过仿真实验验证了GPSR协议在节点密度较大的自组网中具有良好的性能。然而由于在GPSR中路由转发采用右手定则绕过空洞区域，当传递路径上高频率遇到空洞时，其决策的下一跳存在随机性，导致跳数增加。近年来，有很多学者对GPSR进行改进，如引入多点定向传送数据包的GPSR-EZ路由协议[21]。

（3）基于机器学习方法的路由协议

近年来，已开展基于机器学习算法的路由协议的研究工作。这类路由协议利用机器学习算法的学习能力，基于对网络拓扑、信道状态、用户行为、流量移动性等更准确的感知来进行最优路由路径选择。这些算法桥接物联网和人工智能两个研究领域，以实现智联网。以下是一些典型的基于机器学习方法的路由协议。

Boyan等人[22]首次将强化学习引入静态网络的路由问题中，提出了一种自适应算法Q-routing。随后，一些研究者基于Q-routing提出了适用于自组网的基于强化学习路由协议。Jung等人[23]提出基于Q-learning的地理临时路由协议（QGeo）。这是一种基于强化学习的地理路由方案，用于减少高移动性场景中的网络开销。Liu等人[24]改进了QGeo路由协议，并提出了一种基于Q-learning的多目标优化路由协议（QMR）。与QGeo相比，QMR具有更低的端到端时延、更低的能耗和更高的数据包到达率。

为了改善路由协议对网络拓扑变化的自适应能力，一些学者将深度学习与强化学习结合，提出了基于深度强化学习的路由协议。Liu等人[25]提出一种基于深度强化学习的自适应和可靠路由协议（ARdeep）。这是一种基于深度强化学习的自适应和可靠路由协议，它使用马尔可夫决策过程模型制定路由决策，以适应网络环境的变化。它在路由决策中综合考虑链路状态、包的错误率、链路的预期连接时间、节点剩余能量、节点到目的地的距离等，来精确推断网络环境，做出更合适的转发决策。仿真结果表明，ARdeep优于现有QGeo路由协议。

近年来，网络编码技术被引入路由协议设计中，以改善数据传输速率和可靠性。随机线性网络编码（RLNC）[26]是一种经典的网络编码方法，其中所有网络节点将到目前为止收到的所有数据包保存在其缓冲区中，并使用来自某个无限域的随机系数转发这些数据包的线性组合。由于其随机选择线性组合系数的特性，RLNC不能根据网络环境的变化（如变化的链路质量和变化的中间节点数量）来自适应地调整编码系数。Wang等人[27]提出了一种基于深度强化学习的智能网络编码算法，可用于路由协议设计，优化端到端时延和能耗。该方法将编码系数优化问题表示为一个马尔可夫决策过程，并采用深度强化学习算法来优化编码系数。不同于RLNC算法随机选择编码系数，该方法根据当前网络状况自学习和动态调整源节点和每个中继节点的编码系数。实验结果表明，该方法具有良好的泛化能力，能够很好地适应链路质量快速变化的动态场景。