《5G Enabled MEC: A Distributed Traffic Steering for Seamless Service Migration of Internet of Vehicles》

作者：Muhammad Rizwan Anwar；Shangguang Wang； Muhammad Faisal Akram；Salman Raza；Shahid Mahmood
发表时间：2021-05-31
发表刊物：IEEE Internet of Things Journal

本文提出了两种路径选择算法，主要应用于车联网场景，即在车辆行驶过程中，从起点O到终点D这一过程中，在MEC网络中任务卸载路径的选择算法。

所提出问题

1. 如何平衡高带宽和低时延两个优化目标的关系，如何在多条路径之间以最小的时间周期查找到最优路径，从而保证QoS。
2. MEC部署到大型网络时存在一定问题，如路径选择成本变大、众多节点信息收集时间变长等等

解决方法

1. 首先作者提出一种“自主网络边界发现”算法（ANBD），使得当前边缘服务器只能看到与其相邻的服务器，该算法运用的是广度优先搜索思想；同时作者还提出了一种“必须连接节点块”算法（MCNB），即创建必须相连接的节点的不可变列表。

2. 作者为了解决问题2，从大型MEC网络中划分子网，同时定义必须连接的节点进行路径搜索。为了平衡好带宽和时延两个影响因子，提出了一个目标函数如下，即两服务器之间某一路径的时延成本等于各部分的传输时延、服务器上任务处理时延以及可用带宽的倒数之和。
   目标函数

3. ANBD算法：首先将节点入栈，然后使用广度优先搜索，从栈中取出节点来判断其是否在子网中，如果不在子网中且该节点是服务器则将其纳入子网；反之如果节点是路由器，则将该节点的所有相邻未访问节点入栈，并以该节点作为其相邻节点的前置节点。以此可以构建出子网矩阵。
   ANBD算法

4. MCNB算法：该算法利用递归构造一个ALLPath函数实现通过相邻节点来找目标节点的功能，然后将查找范围限定在之前得到的子网内，利用ALLPath函数得到初始节点和目标节点之间所有的节点集。
   MCNB算法

5. 之后作者提出基于ANBD算法和MCNB算法的最短路径选择算法（MDSPS）和多路径选择算法（MDMPS）。
   

   其中MDSPS算法是从必须连接节点（MCN）中得到一个缩减矩阵，然后在Dijkstra算法基础上找出最短路径。该算法中利用缩减矩阵来减小搜索时间。
   MDSPS
   
   当同时要处理多个服务时，很明显MDSPS算法效率不高，故作者又提出MDMPS算法来得到两个服务器之间的多个最佳路径。MDMPS算法是从ALL_Path路径字典中获取可走的路径，然后对每条路径计算时延成本并记录可用带宽，然后选出最低时延的路径进行传输任务。
   MDMPS

数据集

本文数据都是模拟随机产生，其中链路时延进行归一化后范围在0~1，链路通信容量范围设置在0.5~1Gb/s，同时实验所计算的结果都取平均值。

评价指标

本文中提出了四种情况：Bounded、Mapped、Bounded & Mapped、No Filter。其中Bounded是指当前服务器只能看到其相邻服务器的情况；Mapped是指引入必须连接块（MCNB）的情况；Bounded & Mapped是指在前两种情况都有时；No Filter则是指MEC网络视为一个整体，未应用前两种条件的情况。
本文中从平均计算时延、传输不同大小数据所需时延、节点距离对时延影响、子网中节点数对时延影响四个方面来进行评价。

总结

1. 文中一些数据处理技巧可以学习：比如将带宽的倒数加入成本函数，能有效将带宽和时延的影响都考虑进来；比如原MEC网络太大了，可以将网络矩阵缩减，利用必须连接节点等思想来减小计算时间。
2. 本文中作者在对带宽和时延进行多目标优化的那一块没怎么看懂，即作者提出Pareto解并进行论证处。
3. 对评价标准中的四种条件有一些疑惑，作者提出的两种路径选择算法自身其实就运用了必须连接块或者是限定边界思想，这与No Filter或者是单一的Bounded或者Mapped条件有冲突，所以不知道为什么要分这四种情况来进行评价。