每周文章分享

2023.05.29-2023.06.04

标题: An enhanced geographical routing protocol based on multi-criteria decision making method in mobile ad-hoc networks

期刊: Ad Hoc Networks, Volume 103, 1 June 2020, 102157

作者: Beom-Su Kima, Sana Ullahb, Kyong Hoon Kimc, BongSoo Rohd, Jae-Hyun Hamd and Ki-Il Kim.

分享人: 河海大学——董奕伶

研究背景

无线自组织网络是一种分散类型的无线网络。由于自组织网络不需要诸如路由器或接入点之类的预先存在的基础设施，因此基于网络环境和路由算法动态地确定哪些节点转发分组。由于传统的地理路由协议及其变体在路由过程中只使用单一的度量，因此它们不能处理拥塞、网络空洞和链路丢失等问题。为了解决这些问题，人们提出了多度量地理路由协议，但它们大多不能根据网络条件自适应地改变转发策略，因为它们没有定义多个度量之间的关系或优先级。针对这一局限性，本文将多准则决策(MCDM)方法应用到地理路由协议中，以合理地适应多个度量。此外还提出了一种新的动态优先级方案，通过根据网络环境区分优先级来选择最合适的下一跳。

关键技术

本文应用多准则决策(MCDM)方法来确定多个度量之间的权重因子。MCDM是运筹学的一个分支学科，明确地在包括各种指标、相互冲突的目标和度量在内的复杂情况下找到最佳结果。MCDM方法通过同时考虑各种因素，提供了一个灵活的决策过程。为了识别网络环境和选择最合适的下一跳，本文采用了连通性、缓冲区占用率和链路变化率三个路由指标，并使用AHP和SAW方法确定了这些指标之间的相对权重。基于使用提出的度量计算得出的单个代价，每个节点可以选择最佳的下一跳。

该方法的创新和贡献如下：

1）为了克服多度量GRP的问题，本文引入了多度量的MCDM方法，包括连通性、缓冲区占用率和链路变化率。在网络层选择每个度量作为良好的指标，以解决网络空洞、拥塞和链路丢失三个问题。

2）与已有的基于静态优先级的AHP方法不同，本文提出了一种新的根据网络条件区分优先级的动态优先级方案，以提高地理路由协议中选择最合适的下一跳的性能。

3）本文对原有的GRP进行了扩展，协议扩展是通过在报头中添加新的度量并根据MCDM方法计算的单个代价选择下一跳来完成的。

算法介绍

1. 路由度量

为了解决网络空洞、拥塞和链路丢失这三个问题，本文提出了以下三个度量。

A. 连通性

图1  网络空洞

网络空洞的一个特点是相邻节点不多。由于中间节点数量不足，从而造成了网络空洞。在图1中可以看到构成网络空洞的节点的数量是有限的。这意味着如果在下一跳选择中考虑相邻节点的数量，就可以提前避免网络空洞。本文将节点通信范围内的节点数定义为连通性，并将节点i的连通性表示为Ci。连通性计算为

B.  缓冲区占用率

图2  拥塞

缓冲区占用率表示在每个节点处接收到多少分组。如果节点负载过重，就有可能发生缓冲区溢出。在图2中，所有相邻节点将分组转发到节点A，因为节点A是距离目的地D最近的节点。在这种情况下，如果节点A接收的分组比其能够处理的多得多，则可能发生缓冲区溢出。本文将节点的剩余缓冲区大小定义为缓冲区占用率，并将节点i的缓冲区占用率表示为Bi。缓冲区占用率计算为

C. 链路变化率

图3  链路丢失

当节点S将分组转发到节点A时，如果节点A不再在节点S的通信范围内，则发生链路丢失。因此，当邻居节点在更新邻居节点的新位置之前移动到源节点的通信范围外时，就会发生链路丢失。在图3中，由节点S转发的所有分组在时间t处丢失，因为节点A不再在其通信范围内。为了防止链路丢失造成的丢包，每个节点都需要使用稳定的链路，为了确定稳定的链路，本文使用了链路变化率。链路变化率计算为

LCR表示在控制分组传输间隔Dt=t2−t1期间改变了多少链路。因此，这意味着链路变化率越高，由于节点的移动可能发生的链路丢失越多。

2. 描述适应变化的环境的动态优先级方案

如前所述，LCR：B：C的相对重要性应根据网络条件动态确定。否则，当前网络状况不需要的指标可能会反映在决策制定中。为此，本文提出了一种新的动态优先级方案，通过根据网络条件区分优先级来选择最合适的下一跳。

最好的方法是动态调整成对比较矩阵X的比例值，如下所示

这种方法的优点是矩阵单元格中的值(nij)不是固定值。相反，它们取决于早先做出的决定。这种对历史数据的依赖最终会产生对时间的依赖。然而，除非比例值是固定值，否则很难保持标准之间的优先顺序的一致性。此外，由于每当比例值根据历史数据发生变化时都会重新计算权重系数，因此会产生额外的开销。

为了克服这些限制，本文预定义了适合每个网络环境的首选项。每个偏好以两两比较矩阵的形式定义，并根据网络的可靠性和及时性等要求确定比例值。该偏好将被动态地应用于基于网络条件的决策。然而，每个偏好都必须通过AHP的一致性检查程序。本研究中使用的偏好如下。

显然，预定义偏好的数量越多，决策就越灵活。然而，为了集中验证该方法的适用性，只需预先创建三个成对比较矩阵，并动态调整每个矩阵以适应基于LCR的决策过程。

3. 扩展的GRP

GPS使得每个节点知道自己在GRP中的位置信息。每个节点洪泛信标消息以传播其位置。本文中使用的GRP的主要特点是数据包转发具有区域和分层策略。区域象限策略有助于减少洪泛开销。然后，每个节点维护三个信息表：目的地表、邻居表和回溯表。如果一个节点仍然无法转发分组，则回溯机制使用回溯表将分组返回到前一个节点。如果至少有一条路由到达目的地，则回溯机制可确保GRP将数据包转发到目的地。

本文假设构成网络的所有节点都具有相同的传输范围并配备了GPS。每个节点可以通过传播控制分组来知道目的节点和邻居节点的位置。所有节点在每个时间间隔Dt向其相邻节点发送HELLO数据包。HELLO数据包包括其自己的路由信息：id、距离、度量1、度量2、度量3、时间戳。当节点收到HELLO数据包时，如果HELLO数据包中已有条目，且HELLO数据包的时间戳字段高于邻居表的时间戳字段，则在其邻居表中创建新的条目或使用该条目中的信息更新其邻居表。度量1、度量2和度量3被定义为链路变化率(LCR)、缓冲区占用率(B)和连通性(C)。本文使用MCDM方法修改GRP的下一跳选择算法。

每个节点基于使用成本函数的每个度量的加权和来选择最佳下一跳。每个节点从目的表中查找目的地信息。如果目的地表中不存在目的信息，则返回传输失败消息。然后，将执行回溯过程。位置信息用于查找比其自身更接近目的地的邻居列表。例如，在图4中，源节点在其通信范围内具有六个相邻节点。其中，选择距离目的地比自身距离更近的邻居节点作为转发候选节点。因此，即使源节点选择转发候选之一作为下一跳，分组也将被传递，因为候选比其自身更接近目的地。此约束可确保在不进行额外修改的情况下将数据包传递到目的地。

图4  邻居列表示例

实验结果分析

1.  实验设置

本文使用网络模拟器OPNET Modeler版本18.7来评估所提出的协议的性能。使用五个版本的高级GRP：拥塞感知GRP、网络空洞感知GRP、链路丢失感知GRP、基于模糊的GRP和基于MCDM的GRP。为了准确比较基于模糊的GRP和建议的GRP的性能，假设在模拟中使用相同的度量。表1显示了仿真中使用的基本参数的详细配置。本文在95%的可信区间内进行了100次模拟。

表1  基本仿真参数

为了比较每个多度量GRP的性能，本文使用了三个性能度量：分组传输率、端到端延迟和路由开销并在动态网络场景下对这些协议进行了评估，以分析不同参数的影响：流量比特率的影响和节点速度的影响。

2. 分组传输率的性能分析

不同速度的分组传输率如图5(a)所示。在图中，链路丢失感知GRP、网络空洞感知GRP和拥塞感知GRP表现出类似的性能。网络空洞感知GRP将数据包转发到最短路径，并在数据包进入禁区时绕过它们。也就是说，具有稳定链路的邻居节点不太可能被选为下一跳，因此当重试计数达到阈值时，分组丢失率增加。链路丢失感知GRP可以减少链路丢失引起的丢包。然而，由于不能识别网络空洞，目的地未知经常出现在局部最大值区域。另一方面，拥塞感知GRP使用多条路径来利用移动性和拥塞度量来减少丢包。因此，在使用单一度量的三种协议中，性能最佳。然而，由于它们的转发策略不能根据网络条件自适应地改变，因此分组传输率随着节点速度的增加而迅速下降。由于类似的原因，基于模糊的GRP也会随着节点速度的增加而迅速增加丢包率。随着网络条件的变化，模糊推理规则需要自适应地改变。此外，还有一个限制，即其他指标的相对优先级不能一起更改。

相比之下，基于MCDM的GRP基于LCR级别识别本地网络状况，并选择一个预定义的首选项。每个偏好表示一个由AHP规则逻辑确定的成对比较矩阵，并用于用SAW方法计算指标的加权和。因此，随着节点速度的增加，LCR的权重相对增加，以选择链路稳定的相邻节点。结果，可以有效地减少由重发失败引起的分组丢失。这意味着基于MCDM的GRP可以比基于模糊的GRP更能根据网络条件自适应地改变转发策略。

图5  (a)不同速度对PDR的影响 (b)不同流量比特率对PDR的影响

不同流量比特率的分组传输率如图 8（b）所示。在使用单一度量的 GRP 中，使用拥塞度量的拥塞感知 GRP 表现出最好的性能。随着流量比特率的增加，使用单个度量的其余协议无法正确地进行负载平衡，从而导致由于缓冲区溢出而导致分组丢失增加。基于模糊的 GRP 也显示出较差的性能，因为它使用了多种指标，但拥塞指标的权重没有适当调整。另一方面，基于 MCDM 的 GRP 可以随着流量比特率的增加灵活地进行决策。例如，当距离目的地最近的邻居节点的缓冲区占用率增加时，该节点不再是合适的下一跳。这样一来，除了填充了一定数量的节点外，每个节点都选择离目的地最近的节点作为下一跳。这个过程导致负载分配。除了缓冲区占用率指标外，本文还使用连通性指标来选择合适的下一跳。很明显，随着相邻节点数量的增加，避免网络空洞的概率以及负载分配的机会也会增加。

3. 端到端延迟的性能分析

从图6可以看出，与其他GRP相比，网络空洞感知GRP表现出较差的性能，而与流量比特率和节点速度无关。该协议不是一种提前阻止网络空洞进入的机制，所以当数据包进入禁区时，就会绕道到达目的地。此过程会增加延迟，因为随着节点速度的提高，经常会产生网络空洞。另外，随着流量增加，不进行负载均衡，处理时延和排队时延都会随之增加。链路丢失感知GRP可以减少重传延迟，但随着节点速度的提高，数据包更有可能绕道到达其目的地。此外，随着流量比特率的增加，处理延迟和排队延迟也会增加，因为无法执行负载均衡。拥塞感知GRP可以减少由于拥塞引起的端到端延迟。但是，由于使用多条路径，重复数据包会增加排队延迟和处理延迟。另一方面，基于模糊的GRP利用了多个度量，因此可以容忍由于网络状况变化而导致的性能下降。然而，由于转发策略不能根据网络状态的变化而灵活地改变，因此性能低于基于MCDM的GRP。

图6  (a)不同速度对端到端延迟的影响 (b)不同流量比特率对端到端延迟的影响

可以看到，与其他GRP相比无论流比特率和节点速度如何，基于MCDM的GRP表现出了一致的性能。原因在于当网络稳定(低LCR水平)时，即使流量比特率增加，也可以实现负载均衡，因为缓冲区占用率的权重被设置得很大。因此，在转发候选中，具有一定缓存量的节点不太可能被选为下一跳。此外，连通性度量的相对重要性也增加了，因此更有可能将数据包转发到高密度区域。这提供了更多的负载平衡机会。当网络条件不稳定(高LCR水平)时，由于LCR度量的相对重要性被设置为大，所以在转发候选中具有稳定链路的相邻节点被选择为下一跳。因此可以自适应地减小重传延迟。

4. 路由开销的性能分析

从图 7(a) 中可以看到基于 MCDM 的 GRP 具有最低的控制开销。在基于 MCDM 的 GRP 中，整个网络被划分为象限以优化洪泛。当一个节点离开它所属的最高层的象限时，信标消息被泛洪到整个网络。相比之下，其他 GRP 使用信标计时器定期将其位置洪泛到整个网络。特别地可以看到网络空洞感知 GRP 具有最高的控制开销。原因是网络空洞感知 GRP 识别网络空洞边界并将此信息传播到空洞周围的节点。换句话说，网络漏洞感知 GRP 增加了控制开销，因为它将额外的数据包传播到网络以进行无效处理。另一方面，其他采用回溯机制的 GRP 不会传播额外的控制数据包。

除了控制开销之外，还有两个因素会增加 GRP 中的路由开销。第一个因素是所有节点由于没有到目的地的路由而执行的回溯总数。从图 7（b）可以看出，链路丢失感知 GRP 和拥塞感知 GRP 具有多个回溯轨道。为了减少回溯次数，要么将数据包转发到网络空洞区域之外，要么将数据包转发到本地网络稳定的区域。然而，回溯也可能发生在网络空洞感知 GRP 中，因为在绕过空洞区域时，下一跳不是基于链路稳定性或节点密度来选择的。结果，当分组被传递到没有转发候选者的空白区域时，可能发生回溯。另一方面，当节点速度较低时，基于 MCDM 的 GRP 选择连通性权重较高的偏好。结果，数据包更有可能被转发到它们的目的地，因为它们将被传递到高密度区域。这意味着到达目的地的路线很多，因此回溯的次数会减少。相反，如果节点速度高，则基于 MCDM 的 GRP 选择具有高 LCR 权重的偏好。结果，数据包被转发到一个稳定的本地区域，这减少了由于链路中断而导致的回溯数量。

第二个因素是网络中所有 WLAN MAC 的重传尝试总次数，直到数据包成功传输或由于达到短重试或长重试限制而被丢弃。如上所述，传输失败经常由缓冲区溢出和链路中断引起。为了评估重传尝试的次数，本文将节点速度固定为 20 m/s，并随着流量比特率的增加测量性能。图 7(c) 表明基于 MCDM 的 GRP 可以随着网络环境的变化自适应地改变其转发策略。尽管基于模糊的 GRP 也同时使用移动性和拥塞度量，但重传次数高于基于 MCDM 的 GRP，因为无法确定度量之间的相对优先级。

图7  (a)不同速度对平均控制开销的影响 (b) 不同速度对平均回溯次数的影响(c) 不同流量比特率对平均重传尝试次数的影响

总结