王朝炜，王天宇，刘 婷，王卫东

(1.北京邮电大学 电子工程学院，北京 100876；2.泛网无线通信教育部重点实验室，北京 100876)

0 引言

6G移动网络有望成为一个内生智能、高动态、超密集的异构网络，以极低延迟和高速数据传输实现万物互联。6G关键技术进一步推进车联网应用于大规模车路协同业务场景，进一步提升交通系统效率。车联网使用车辆对基础设施(V2I)通信,为导航、游戏、XR视频流、网络缓存和移动群感知等交通安全外的应用提供互联网服务[1]。信息娱乐应用依赖蜂窝基础设施与互联网交互，此类数据密集型应用程序为车辆用户提供额外的信息和娱乐，并收集城市传感数据用于各种用途。车辆和车载应用数量的增加将产生巨大的数据流量并导致蜂窝网络拥塞和授权频谱紧缺[2-3]。网络运营商可以将这些高吞吐量数据流量卸载到其他基础设施[4]。

部署在交通路口的路侧设备(Road Side Unit,RSU)是用于机会式数据卸载的理想基础设施。RSU的作用类似于无线接入点(Access Point,AP)，利用IEEE 802.11ad/ay等Wi-Gig技术以60 GHz的中心频率为多个客户端同时提供速率超过4 Gb/s的点对点宽带链路，帮助车辆卸载娱乐信息应用程序的数据流量[5-6]。6G D2D技术的演进使得Wi-Gig和基于蜂窝网的车用无线通信技术(C-V2X)的集成成为可能，可将大量数据流量从授权频谱卸载到免费频谱，有望支持比5G显著提高的数据速率[7]，使利用Wi-Gig技术的RSU数据卸载成为可行的解决方案。车辆停留在红绿灯或停车场等区域并进入RSU服务范围内时，移动网络运营商通过RSU进行数据卸载[7]。在通信和计算能力有限的情况下，有效地调度网络中资源的使用以达到最佳利用率，支持边缘计算的RSU沿道路部署，以向车辆提供数据带宽和计算卸载，该方案缓解了频谱受限蜂窝系统中的资源占用[8]。部署和维护RSU的成本很高，RSU的规划和使用至关重要。

目前,针对RSU部署方法的研究包括：Ni等[9]提出的RSU服务区概念，将邻近街道的车联网数据流量任务划分给相应的RSU，考虑了RSU的服务能力和车间传输时延，利用基于线性规划的聚类算法，协同解决RSU在城市环境中的部署和任务分配；Kim等[10]考虑了3种不同类型的RSU部署方法(静态、移动和可控)，分别采用RSU、私人车辆和可控公共交通车辆部署车联网通信设备，最大化它们的时空覆盖(Space-Time Conservation,STC)。以上研究并未全面考虑车联网中车辆的移动状态。通过对城市车辆数据集的分析发现：车辆并非时刻处于运动状态中，而时常处于等红绿灯、靠边停车、低速行驶状态中。本文重点利用车辆在路口等运动速度较低的情况，利用RSU进行数据卸载的可行性，分析了将RSU布置在路口时，数据卸载的效率。

另一方面，车联网中的数据卸载机制的研究包括：Raja等[1]设计了一种基于下一代车联网的智能车联网架构，设计了基于SDN控制器的流量分类方法和基于反馈的智能数据卸载机制，将非车辆安全相关的数据流量分类并卸载到合适的RSU；Si等[11]提出了DAVE,考虑到车联网数据卸载延迟容限的路由机制，将延迟容忍数据流量卸载到邻近车载网络；Wang等[12]提出了一种基于云/边缘/雾计算的车联网架构的新分类方法；Fan等[13]研究了 C-V2X网络的流量卸载问题，提出了一种智能软件定义的 C-V2X 网络框架，通过将网络数据平面与控制平面解耦来实现灵活且低复杂度的流量卸载，在数据平面上，蜂窝流量卸载和车辆辅助流量卸载是联合进行的。在控制平面，部署深度学习，降低软件定义网络(Software Defined Network,SDN)控制复杂度，提高流量的分流效率；Huang等[14]设计了一种基于移动边缘计算的k-hop远程卸载代理机制，当有k-hop V2V路径可以连接车辆和前方的RSU时，可以启用V2I卸载，当车辆已经离开对应RSU的信号覆盖范围时，如果有k-hop V2V路径可以将车辆与后方的RSU连接进行V2I卸载；Gao等[15]设计了一种考虑到时延限制的基于概率的移动数据卸载机制。以上研究较少考虑车联网应用的延迟容忍特点，并非所有车联网应用都需要实时的数据传输，一些传感数据与云存储数据实时性要求较低。本文分析了车联网中车辆接入RSU的平均时间，研究了车联网应用的传输延迟时限的容忍程度。依据数据卸载的效率、传输时延的容忍度等参数对RSU的部署位置或设备的启用进行动态调整，是本文的研究重点。

本文首先将上述场景建模，针对V2I数据业务面临的问题，分析了车联网中RSU的利用率和接入等待时间，对RSU的部署位置进行选择。将RSU部署问题证明为一个NP-hard问题，然后设计了一种改进的贪婪算法得出RSU部署方法，利用真实GPS 数据集仿真验证，最后对实验结果进行分析，总结全文并展望未来工作趋势。

1 系统模型

城市交通干线路口是RSU部署的理想位置,最能适应车载数据卸载的高吞吐量和延迟容忍特性。由于道路中车辆速度过快，分布不均匀，车辆遵循的机会式传输模式被称为“存储-转发”模式，利用车辆移动带来的相遇机会实现通信的自组织网络，具有一般DTN网络传输特征，利用RSU的机会式通信可以为车辆提供Internet访问和商业应用等[16]。车联网数据卸载场景示意如图1所示，RSU可以覆盖并为相对静止的车辆提供无线接入。当车辆在红绿灯处短暂停车时，车载信息娱乐应用程序会通过最近的RSU执行点对点数据传输。

图1 车联网数据卸载场景示意

网络模型：城市场景可以被建模为一张图G= {V,E},图的节点代表城市道路的交叉路口，图的边代表连接各个路口的道路。V={vi:i= 1,2,…,I}表示节点的集合，E= {ei:i= 1,2,…,J}表示边的集合。图中的节点和边的总数分别是I和J。

U= {ui:i= 1,2,…,M}表示M辆车的集合，T={ti:i= 1,2,…,N}表示N个时间段。L(U)是一个由M辆车在N个时间点上的地理坐标组成的矩阵。例如,lij表示车辆ui在j时刻的地理坐标:

(1)

在所有路口都布放RSU不现实也不经济，RSU部署算法应从所有路口的集合中选出一部分用于部署RSU。集合R= {ri:i= 1,2,…,K}表示部署算法选中的RSU的坐标。集合R中的元素会随着部署算法的迭代而改变，R⊆V，K≤I。

(2)

例如，车辆ui的网络访问状态将被其驾驶路径中遇到的RSU影响。车辆ui的网络访问状态将被记录为一个0-1序列，如LR(ui)=[0 1 1 … 0]。

时间线示意如图2所示，以进一步阐明网络状态阶段。灰色和空白线框分别代表服务时间和等待时间。箭头线代表该服务期间卸载的数据包。等待超出容限的数据包将被丢弃。

图2 车辆网络状态时间线示意

传输模型：考虑到车联网场景的延迟容忍特征，研究了等待时延，将TL作为数据卸载等待时间的限制[15]。车载应用的平均数据生成率为d0，通过RSU的数据卸载率为σ。

(3)

部署算法通过调整场景中RSU的位置来改变λ与μ的比例。当λ增加时，车辆更有可能遇到RSU。当μ减小时，车辆在RSU通信范围内停留的时间更长。

(4)

当式(4)中的2个项目大小相似时，数据卸载的质量最好。在这种情况下，车辆每个阶段的数据量刚好等于该阶段可以卸载的数据量，数据丢失或延迟的概率最小，成本会在合理范围内。

UR的期望值为：

(5)

P= {pi:i= 1,2,…,I}表示在每个路口部署RSU的成本。成本受很多方面的影响，包括基本成本、维护成本和交叉口的拥堵程度。成本集P与路口集V之间存在一一对应关系，主要从路口的交通量和道路拓扑结构估计。

归一化目标函数反映了部署算法对RSU利用率和数据卸载延迟的影响。通过适当部署RSU来改变车辆的通信状态，该函数的值将会增加。

F(R)=UR/Tw。

(6)

定义2(RSU部署问题)：从给定的一组路口中选择其中一组子集来部署RSU，以最大化目标函数并服从预算约束B。

给定：I个候选路口，V={vi:i= 1,2,…,I}和对应的开销P= {pi:i= 1,2,…,I}，N个时间点T= {ti:i= 1,2,…,N}。

目标：选出集合R= {ri:i= 1,2,…,K}用于部署RSU，R⊆V，K≤I，使得F(R)最大。

限制条件：P(R)≤B。

2 RSU部署算法

理论证明：本文提出的问题是在有限的成本范围内选择一组合适的位置来部署RSU，以实现更好的数据卸载效率，可以证明这是一个NP-hard问题。首先证明它属于NP问题，假设该问题不能在多项式时间内找到答案，但存在可能的解Ω′，可以在多项式时间内验证Ω′是问题的解，且验证的时间复杂度为O(n)，此时该问题是一个NP问题。MCP问题：对于给定的集合S= {si:i= 1,2,…,n}，每个si都有对应的收益Fi和成本Ci，并且目标是找到S′⊆S以满足相应的预算成本限制Cmax并获得较高的收益。为了进一步证明该问题NP-hard，可将MCP问题的条件与本问题进行一一映射，以将MCP问题规约为本文问题：

Fi→Ei,si→ri，

Ci→pi,Cmax→B。

MCP问题的任何实例都可从本文问题中找到对应的实例。在文献[17-18]中，MCP问题已被详细证明是NP-hard，因而本文问题为NP-hard。由于在多项式时间内很难找到NP-hard问题的精确解，本文设计了一种改进的贪婪算法，在缩短求解问题的时间复杂度的同时得到逼近精确解的近似解。

边际效应：边际效应源自与此RSU的开销相比通过添加一个RSU后目标函数减少的量。贪婪的策略总是选择本轮迭代中边际效应最大的RSU。

(7)

RSU部署算法如下。

输入:路口集合 V={vi:i=1,2,…,I},部署成本集合 P= {pi:i = 1,2,…,I},预算限制 B,当前成本 P输出:选出最优路口集合 Ω Initialize:Ω=ϕ,S=ϕ,P=0;1.forS′⊆V,P(S′)≤Bdo2. S←S′,max=0;3. forvi∈V-Sdo4. S′←{S∪vi},5. ΔF(S)=F(S′)-F(S);6. Ei=-ΔF(S)pi7. ifEi>max and P(S′) ≤ B8. S←S′9. max←Ei10. end if11. ifF(S)

本文设计了改进的贪婪算法解决用于数据卸载的RSU部署问题，通过在预算约束内放置更多RSU来最大化目标函数。改进的贪婪算法总是预先选择一组最有效的路口进行放置，然后执行其余的贪婪迭代。改进的贪婪算法考虑了添加RSU部署位置时的边际效应，大大降低了算法的时间复杂度。当预算用完，或者边际效应趋于零时，算法会自动停止并提出当前的最佳部署位置集合。在最差情况下总共有m次选择迭代，每轮会遍历n个RSU侯选位置，算法的时间复杂度为O(mn)。

3 仿真结果与分析

模拟采用由上海市4 000多条出租车轨迹组成的真实交通数据集[19-20]。本文首先对交通数据集进行了初步处理，剔除不适当的轨迹。对不同数据文件的采样周期进行了缩放，以保证模拟的可靠性。部署成本P= {pi:i= 1,2,…,I}服从均值为1的高斯分布，总成本预算以20为间隔从30增加到250。仿真实验假设毫米波点对点传输信道能够获取较为稳定的传输速率；数据生成速率d0和数据卸载速率σ分别设置为500 MB/s和4 GB/s。本节分析了RSU利用率、服务等待时间和等待容忍度，将3种算法：均匀布放、贪心算法和RSU部署算法用于比较它们的效率。均匀布放算法将RSU放置在固定间隔距离处，普通贪心算法总是选择当前轮次成本最低的位置来放置RSU。

目标F(R)与不同预算的关系如图3所示。RSU部署算法对目标函数及其边际效应遵循贪婪策略，使得目标函数随着预算的增加而增加。当RSU部署算法放置大约150个RSU时，目标函数已降至理想的小值。RSU部署算法不仅考虑了部署成本，还考虑了对整个系统的边际影响，算法的效率和最终效果优于均匀算法和贪心算法，最终可以多部署15%的RSU，其最终效果优于均匀和贪婪的部署。

图3 不同部署成本下算法的F(R)对比

图4和图5显示了服务等待时间和RSU利用率与不同预算的关系。

图4 不同部署成本下算法的车辆平均接入间隔对比

图5 不同部署成本下算法的RSU利用率对比

当预算增加时，算法会在网络中部署更多的RSU，以提高遇到RSU的几率。同时，算法增加了车辆在路口停留的期望时间。当预算达到150个单位时，Tw显著下降到大约1个GPS采样周期(13 s)。

随着总预算的增加，车辆与RSU之间的有效通信时间随之增加。算法不仅减少了Tw，而且使RSU能够为车辆提供更长时间的数据卸载。因此，UR随着预算的增长而增加。同时，由于Tw的下降，数据几乎不可能等待超过时间限制TL，这进一步增加了UR。

图6显示了具有不同延迟容忍度车辆应用的 RSU利用率。在前3组仿真中，TL固定为10 min。但是，不同的TL，数据卸载的效果会有明显差异。仿真实验中，TL参与了F(R)，Tw，和UR的计算。TL根据车辆应用的延迟容忍度而变化。对于短TL的应用，只有大约80%的数据有机会通过RSU卸载，因为有限的RSU密度不足以支持延迟容忍时间内的机会式数据卸载。具有长TL的应用程序的机会式卸载RSU利用率较高，RSU密度足以支持车辆延迟容忍时间内机会式地接入RSU并进行数据卸载。

图6 不同延迟容忍下算法的RSU利用率

4 结束语

本文研究了6G车联网中机会式数据卸载的RSU部署问题，减轻车联网的拥塞和延迟问题。综合考虑卸载效果和部署成本的同时，将RSU部署问题转化为一个NP-hard问题。引入了一个目标函数来衡量数据卸载的效果，并设计了一种改进的贪婪算法部署RSU，以最大化目标函数。使用真实出租车GPS数据集初始化场景并进行仿真，结果表明RSU部署算法在预算限制内有效增加了车联网机会式卸载的RSU利用率，并且优于其他算法。