严翰致，许小龙,+，代 飞，齐连永，窦万春，李 彤
(1.南京信息工程大学 计算机与软件学院，江苏 南京 210044；
2.西南林业大学 大数据与智能工程学院，云南 昆明 650224；
3.曲阜师范大学 信息科学与工程学院，山东 日照 276825；
4.南京大学 计算机软件新技术国家重点实验室，江苏 南京 210023；
5.云南农业大学 大数据学院，云南 昆明 650201)
边缘计算利用分布在网络边缘的计算资源为用户提供服务环境和云数据中心[1]。将边缘计算引入车联网协同云计算处理服务请求(即边云协同的车联网边缘计算)，改变了以往通过云数据中心向车载用户反馈结果的方式，而以边缘设备作为服务处理节点，充分利用边缘侧资源，显著缓解了大规模数据传输导致的网络负担[2-4]。然而边缘服务器资源有限，随着车辆终端数的增多，车联网服务与应用更加广泛，边缘服务器部署问题变得更加复杂[5]。现有边缘服务器部署策略主要用于改善5G、无线城域网等场景下的服务性能，相关技术很难直接用于车联网服务部署。并且由于交通流量分布不同以及车载用户请求具有分散性，不同路段的路边单元需要处理的数据量存在明显差异[6-7]。因此，车联网环境下科学合理的边缘服务器数量与位置部署是支持车联网服务部署的关键，而边缘服务器间的负载均衡问题则是边缘服务器部署的关键。
基于强化学习的边缘服务器部署策略将强化学习机制应用于划分路边单元的归属与决策边缘服务器位置，以实现边缘服务器之间的负载均衡，同时兼顾车联网服务请求响应时延与能耗，满足车载用户对车联网服务“低延时、高带宽、高可靠”的性能需求[8]。
目前，边缘计算技术的核心在于解决边缘服务器部署、计算卸载、服务迁移、群智协同4个关键问题，其中科学合理的边缘服务器部署是其他技术研究与部署应用的前提。XIAO等[9]设计了一种基于资源需求预测的预测映射优化启发式算法，并构建了跨区域资源优化模型，能够有效应对不同区域服务请求量差异的问题；
CHEN等[10]提出一种采用免疫优化算法的边缘服务器部署策略，并通过仿真实验验证了该策略在减少访问延迟与优化负载平衡方面的有效性和可行性；
CAO等[11]进行了异构边缘服务器部署策略研究，提出一种由离线阶段和在线阶段组成的方法，离线阶段采用整数线性规划技术生成异构边缘服务器的最佳部署策略，在线阶段则采用一种基于移动感知游戏理论的算法来应对用户移动的动态特征。
另一方面，将车联网与强化学习技术结合来提高车联网服务质量，进而改善车载用户的出行体验，也是车联网领域具有前景的研究方向之一。由于传统的车联网缺乏感知环境和学习最佳策略的能力，针对其在面对动态环境时无法选择最佳的路由策略，WANG等[12]提出一种基于强化学习，适用于车联网软件定义的认知网络，与几种典型协议相比，该协议具有有效性，而且性能更加优良;JIANG等[13]将单代理强化学习中的Markov决策过程扩展到多代理系统，提出一种基于分布式多代理强化学习的边缘缓存算法来解决边缘缓存优化问题，该方法能有效减轻车联网中的冗余流量和内容访问延迟；
WU等[14]提出一种动态无线接入网切片框架，用以动态分配无线电频谱和计算资源，并为切片分配计算工作量，其将无线接入网切片问题分解为资源分配子问题和工作负载分配子问题，用双层约束的强化学习算法解决这两个子问题，即在外层用强化学习算法决定资源分配，在内层用优化子程序分配工作量。
综上所述，目前采用强化学习对车联网环境下的边缘服务器进行部署的工作较少，而且致力于车联网环境下边缘服务器部署策略的设计缺乏对负载、时延、能耗等的综合考量。因此，需要兼顾边缘服务器之间的负载均衡、车联网服务请求响应时延与能耗，设计科学合理的边缘服务器部署策略支持车联网服务器部署，进而改善用户的出行体验。
2.1 边云协同的5G车联网边缘计算系统架构
边云协同的5G车联网边缘计算系统架构如图1所示。车载终端是环境感知、车辆行为决策和车辆控制的主体，为了向车载终端提供道路、行人和其他车辆的信息，路边单元被分布在道路边缘收集数据，路边单元用集合U={u1,u2,…,uZ}表示。ui是一个三元组，有纬度、经度和数据量3个参数，表示为ui(lati,loti,di),ui∈U，其中di表示路边单元ui收集的数据，所有路边单元收集的数据一一对应，表示为D={d1,d2,…,dZ}。因为依靠各种高分辨率传感器(如激光雷达传感器和视觉传感器)的车辆会产生大量数据，所以边缘服务器被安排在交通密集区域，以协助存储数据和处理车联网服务请求，边缘服务器用集合S={s1,s2,…,sN}表示。在此架构中，假定边缘服务器的服务范围相同，用Re表示服务范围的半径;le表示边缘服务器的工作负载，lem则是边缘服务器的负载上限;sj可被表示为一个四元组sj(latj,lotj,Re,le),sj∈S，其有纬度、经度、服务范围半径和负载4个参数。与路边单元相比，边缘服务器的覆盖区域更广，具有更强的存储和计算能力。边云协同模式下功能最强大的服务器为云数据中心s0，除去服务器的基本计算和存储能力，云数据中心还负责管理边缘服务器并为其分配虚拟资源。
在该架构中，计算节点由路边单元、边缘服务器和云数据中心组成，表示为C={U,S,s0}。两个节点ci,cj之间的距离可根据经纬度，用大圆距离公式表示为dist(ci,cj)。
2.2 负载均衡分析
服务器过载会降低用户的服务体验质量，因此应合理分配每个边缘服务器的工作负载，尽可能使负载均衡。假设部署的边缘服务器数量为N，则划分至边缘服务器si(1≤i≤N)服务范围内的路边单元可表示为集合PSi={ui1,ui2,…,uiG}(1≤G (1) 式中σj为路边单元uj收集后卸载到云数据中心的计算任务的数据量，每个边缘服务器的工作负载应小于负载上限lem。 边缘服务器的合理工作负载预期为τ， (2) 负载均衡模型旨在最小化边缘服务器之间的负载差距，以实现基于数据量的初步负载均衡，未考虑特定的任务调度策略。为了量化负载均衡的程度，采用离散系数定义负载均衡指标，离散系数 (3) 当CV=0时，达到理想的负载均衡，然而考虑实际应用中的其他限制因素，CV无法等于零，即边缘服务器之间难以达到理想的负载均衡。因此在实际应用中，当CV取得最小值时，负载分配策略最佳。 边缘云协作系统在边缘服务器或云数据中心处理服务请求，为了减少服务请求的响应时延，仅将一些对时间不敏感的计算任务卸载到云数据中心执行。服务请求的响应耗时由传输时延、传播时延和任务执行时延3部分组成，而且执行传输、传播和任务都会产生能耗，每个阶段的能耗则取决于其相应的时延和单位时间能量损耗。 (4) 式中γi和γj分别为路边单元和目标边缘服务器两个节点的信道带宽。 数据传输阶段的总能耗 (5) 式中φtm为传输过程中的单位时间能量损耗。 传播时延由信号传输引起，仅与传输距离和传输速率有关。该时延包括任务卸载阶段的传播时延和结果反馈阶段的传播时延两部分。因为大多数车联网服务请求的处理速度非常快，所以服务处理期间的车辆移动距离可以忽略不计，而且车辆位置可近似由路边单元的位置表示。传播时延 (6) 式中：dist为两个节点之间的距离； 信号传播阶段的总能耗 (7) 式中φpg为传播过程中的单位时间能量损耗。 服务器的任务执行能力由其拥有的计算资源决定，这里采用计算单元的数量δ衡量计算资源，每个计算单元的计算能力记为θ，则任务执行时延 (8) 式中dsi为服务器需要处理的数据量。 任务执行阶段的总能耗 (9) 式中φec为任务执行过程中的单位时间能量损耗。 路边单元收集数据的处理耗时是传输时延、传播时延和任务执行时延的总和，因此处理完所有服务请求所需的总时长 (10) 整个数据处理过程中的能耗是传输、传播和任务执行3个阶段所产生能耗的总和，因此处理问完所有服务请求的总能耗 ECtotal=ECtm+ECpg+ECec。 (11) 本文旨在解决以边缘服务器间负载均衡为核心目标，兼顾车联网服务请求的响应时延和能耗的多目标优化问题，找到用于车联网环境下边缘服务器部署的高效策略。根据以上模型，该问题可形式化表述为： minCV,minTtotal,minECtotal。 (12) s.t. ωq≤le,∀q∈[1,N]； (13) (14) 式中Fc为云数据中心工作负载与总工作负载的最大比率。为了能够充分利用边缘服务器，减轻云数据中心的负担，减少网络拥塞，云数据中心的工作负载率应小于或等于Fc。 基于强化学习的边缘服务器部署策略(deployment Strategy of edge servers based on Reinforcement Learning, SRL)流程如图2所示。首先用粗聚类算法Canopy获取初始聚类中心，然后根据Canopy结果的聚类数进行模糊C均值聚类，由于模糊C均值聚类的结果易受噪音影响，在进行聚类前需滤除噪声簇。因为模糊C均值聚类算法最终输出的隶属度矩阵只保留最高隶属度，所以在聚类过程中引入路边单元相对于边缘服务器的归属程度，通过输出路边单元的归属优先级矩阵指明其在各个簇的优先级，以便优化选择路边单元的归属。最后根据累计奖励值采用强化学习方法确定边缘服务器位置，获取最终的边缘服务器部署策略。 路边单元划分方法中采用模糊C均值聚类算法获取聚类中心即为最小化目标函数的过程，目标函数本质上是各路边单元与各边缘服务器距离的平方和。经过反复迭代运算，目标函数收敛则完成聚类。通过循环计算累计奖励并比较各轮奖励值的大小，确定最优服务器的位置，在达到循环终止条件或最大循环轮数时停止循环。 路边单元被放置在智能交通系统中，其位置信息可被用于划分聚类。聚类算法常用于划分聚类，通过对噪声健壮的聚类操作可以获得路边单元的簇数和质心，从而初步估计边缘服务器的数量和位置。基于质心的聚类算法通常会生成相似大小的簇，而且该算法倾向于将点与最近的质心关联，簇生成规模相似性和质心关联性使基于质心的聚类算法在设施选址问题上具有良好的性能。K-means，K-median，K-medoids为3种具有代表性的基于质心的聚类算法，这些聚类算法将数据点硬性划分至各个确定的簇，而本文采用的模糊C均值聚类的聚类结果比K-means等硬聚类更加灵活。因为不考虑服务器负载等影响因素，仅以一个分类标准，即路边单元位置信息划分聚类，将导致大多数路边单元被直接划分至确定的簇，所以引入路边单元相对于边缘服务器的归属程度，根据归属程度确定路边单元归属的优先级，以便后续进一步对路边单元的归属情况进行优化。 算法1基于模糊C均值聚类的路边单元划分。 输入：路边单元集合U、隶属度因子m。 输出：Pm，Ccur。 1：Cnum=K 2：for i=0 to K-1 do 3：if point_numi 4：Cnum=Cnum-1 5：end for 6：while true do 7：for j=0 to Cnum-1 do 8：根据式(17)和式(18)计算聚类中心 9：end for 10：for i=0 to M do 11：根据式(16)更新隶属度矩阵 12：end for 13：根据式(15)计算目标函数值 14：end while 15：end if 16：根据隶属度矩阵冒泡排序计算Pm 17：for i=0 to M do 18：for j=0 to Cnum-1 do 19：if Pm[i][j]=1 then 20：ui归入Ccur[j] 21：end if 22：end for 23：end for 24：return Pm，Ccur 模糊C均值聚类的主要参数有固定簇数、各簇质心、每个路边单元最接近的质心对应的簇。为确定模糊C均值聚类算法所需的固定簇数，采用Canopy获得初始聚类中心集合C{c1,c1,…,cK}，簇数为K。Canopy可以获取簇的数量以及准确性较低的聚簇中心，是一种粗略的聚类算法，由于其结果易受噪音影响，在进行模糊C均值聚类之前需滤除噪声簇。 模糊C均值聚类通过最小化目标函数得到聚类中心，如算法1所示。目标函数为 (15) (16) 聚类中心的位置计算如下： (17) (18) 当输出的隶属度矩阵趋向稳定，即目标函数收敛时停止迭代，得到最终解。终止条件为 (19) 式中：t为迭代步数； 根据最后输出的隶属度矩阵，排列每个路边单元相对于各聚类中心的隶属度，给出当前的聚类划分结果Ccur，并输出路边单元的归属优先级矩阵Pm，Pm[i][j]表示路边单元ui在sj上的优先级，优先级最高为1，最低为N-1。 通过算法1获得的初始路边单元划分结果和边缘服务器位置仅以路边单元位置信息作为分类标准，而设施选址问题，包括边缘服务器部署问题，不只受位置信息单一因素制约，该类选址问题通常被认为是NP难的多目标优化问题，针对该类问题，目前已经提出几种多目标优化算法，如粒子群优化算法和遗传算法。粒子群优化算法在求解连续性问题中具有优势，遗传算法则在解决设施选址类离散性问题上性能优越。遗传算法中，由于优秀个体对种群影响大，降低了种群多样性，算法很难收敛至全局最优。若种群多样性过大，则遗传算法的收敛速度将像随机算法一样明显降低。而强化学习方法能够根据智能体与环境交互获得的反馈，通过持续迭代更新进行特征学习，更易找到合适的策略。因此，本文采用强化学习方法划分路边单元并确定边缘服务器的位置。 算法2基于强化学习确定边缘服务器位置。 输入：Pm，Ccur，路边单元集合U。 1：初始化累计奖励Reward 2：for i=0 to Z-1 do 3：for j=0 to G-1 do 4：for each st∈ST do 5：for h=0 to H-1 do 6：根据式(21)计算该步奖励 7：end for 8：根据式(22)计算累计奖励 9：end for 10：Radi=max (V,V′) #计算该轮最大累计奖励 11：end for 12：if Radi>Reward then 13：Reward=Radi 14：end if 15：更新环境状态(修改RSU归属、服务器负载) 16：根据新的质心位置更新聚类中心 17：if|Reward′-Reward|<ε then 18：停止该层循环 19：end if 20：end for 算法2的环境状态由路边单元的划分情况决定，选定的状态包括路边单元的归属情况Rs、各边缘服务器的负载情况Es、当前时延Ts与当前能耗Ps，当前状态可以表示为 st={Rs,Es,Ts,Ps}。 (20) 各状态的执行动作为move，即改变当前路边单元的归属。根据算法1输出的路边单元归属优先级矩阵的归属优先级选择动作，目标是获取最大的累计奖励值，累计奖励通过状态转变产生的单步奖励计算。单步奖励为一次动作执行期间，CV，Ttotal，ECtotal3个指标的变化率按比例求和后的负值，即 (21) 式中：r(St,move)为在状态St执行动作move的奖励值； 累计奖励 (22) 式中ST表示状态集合，该式计算从初始状态至最终状态整个过程的累计奖励。 基于强化学习的边缘服务器位置确定过程如图3所示。可见，基于模糊C均值聚类的路边单元划分给出了初步的路边单元划分、边缘服务器位置和路边单元归属优先级矩阵。根据优先级矩阵为每个路边单元选择所归属的边缘服务器，将每次选择作为一个动作，计算执行每个动作的单步奖励，然后对所有单步奖励求和，获得一次路边单元归属整体更新的累计奖励。经过多轮更新获取最大累计奖励，用该次归属结果更新边缘服务器的位置，用更新后的边缘服务器位置替换模糊C均值聚类的结果。循环以上步骤，直至最大累计奖励不再变化，输出最终的路边单元归属和边缘服务器部署位置的优化结果。 本章通过实验验证本文提出的边缘服务器部署策略的有效性。首先从边缘服务器负载均衡、车联网服务处理请求响应时延和能耗3个层面详细介绍实验配置，并与Random Selection[15]、K-medoids[16]及边缘服务器量化和放置协作方法(Collaborative method for Quantification and Placement of edge servers, CQP)[17]3种策略进行对比分析。 实验采用南京市路边单元数据集，主要数据包括分布在南京市各个路段436个已激活的路边单元位置信息，以及这些路边单元不同时段收集的车联网服务请求数据。为了对比验证部署策略的性能，获取如下3种边缘服务器部署策略： (1)Random Selection[15]该策略随机选择彼此距离尽可能远的K个点作为聚簇中心，获得未经优化的边缘服务器位置。 (2)K-medoids[16]该策略可以从具有噪声的真实数据点中找到每个聚类的中心。该策略的执行前提是确定的聚类数，当聚类数给定时，例如采用Canopy算法的处理结果作为初始的聚类划分，K-medoids在设施选址问题中具有良好的性能。 (3)CQP[17]该策略结合聚类算法与遗传算法，采用基于参考点的非支配排序遗传算法优化K-medoids算法的聚类结果。 SRL策略获取的边缘服务器部署位置如图4所示，图中半径较大的圆实心点为边缘服务器的部署位置。下面分别从负载均衡指数、时延、能耗3方面详细对比分析Random Selection，K-medoids，CQP，SRL 4种策略的性能。 4.2.1 负载均衡指数对比分析 本节对Random Selection，K-medoids，CQP，SRL 4种边缘服务器部署策略进行负载均衡效果评估，对比监测日3种边缘服务器部署策略的负载均衡指数。边缘服务器的负载均衡指数与其自身负载、服务器平均负载有关，该指数越低，各服务器的负载越趋于平均负载，负载均衡程度越高。 图5所示为4种策略在28日的负载均衡指数。可知，在边缘服务器部署数量相同的情况下，SRL策略的负载均衡指数为0.7～0.8，均显著低于其他策略，其在负载均衡的优化目标上有较大优势； 4.2.2 服务请求响应时延对比分析 本节对Random Selection，K-medoids，CQP，SRL 4种边缘服务器部署策略的服务请求响应时延进行评估，对比监测日3种边缘服务器部署策略的日平均服务请求响应时延。由上述分析可知，服务请求响应时延由传输时延、传播时延和任务执行时延3部分组成，服务请求得到处理的时间间隔越短，车载用户的出行体验越佳。由于假设采用相同规格的边缘服务器和硬件配置，实验主要考虑传输和传播时延。 图6所示为4种策略监测28日的每日平均服务请求响应时延。可知，在边缘服务器部署数量相同的情况下，Random Selection策略由于聚类中心的选择具有随机性，其服务器部署策略的时延优化效益较低； 图6中各策略的每日平均服务请求响应时延均高于3.2 ms，因此将3.2 ms作为低时延处理标准，3.2 ms内处理完成的服务请求视为低时延处理。图7所示为4种策略监测28日的每日服务请求低时延处理率。可知，在边缘服务器部署数量相同的情况下，Random Selection策略由于聚类中心选择具有随机性，其在某些监测日有较高的低时延处理率，但也存在19日仅90.3%较低低延时处理率的情况，而且对比图6的每日平均时延可推断出该策略存在部分服务请求高时延的问题。基于K-medoids的CQP策略采用遗传算法对K-medoids策略的结果进行进一步多目标优化，相比K-medoids策略有更高的服务请求低时延处理率。在4种方法中，SRL策略的服务请求低时延处理率在多数检测日最高。根据图6和图7的结果，CQP策略对服务请求响应时延的优化更加明显，SRL策略能够保证更多服务请求在低时延内处理，因此SRL策略在降低车联网服务请求的响应时延方面具有有效性。 4.2.3 服务请求响应能耗对比分析 本节对Random Selection，K-medoids，CQP，SRL 4种边缘服务器部署策略的服务请求处理能耗进行评估，对比一定天数内3种边缘服务器部署策略的日总服务请求处理能耗。由上述分析可知，服务请求的处理过程包括传输、传播和任务执行，每个阶段的能耗则取决于其相应的时延和单位时间能量损耗，由于假设采用相同规格的边缘服务器和硬件配置，实验主要考虑传输和传播产生的能耗。 图8所示为4种策略下28日的每日平均请求处理能耗，由于处理能耗由响应时延与每秒能耗决定，对比图6中4种策略的平均时延发现两图折线走势相同。在边缘服务器部署数量相同的情况下，聚类中心选择的随机性使Random Selection的能耗优化效益较低； 针对车联网边缘计算面临的边缘服务器部署问题，在车联网环境下非定量边缘服务器部署策略研究中，本文设计了边云协同的5G车联网边缘计算系统架构，同时将边缘服务器部署问题形式化为多目标优化问题，通过模糊C均值聚类算法和强化学习方法对负载均衡、服务请求响应时延和能耗3个目标进行优化。最后与Random Selection，K-medoids，CQP 3个方法对比表明，本文所提SRL策略在重点优化边缘服务器间负载均衡的同时，能有效降低服务请求的响应时延和能耗。 为了简化模型，本文假设边缘服务器的计算能力相同。实际上，智能交通系统中部署的边缘服务器的规格可以不同，而且可随城市建设边缘服务器布局的需要变更适应性。例如，在交通繁忙区域采用具有更强计算能力的边缘服务器，在车流稀少的地区采用计算能力一般的边缘服务器来降低能耗。未来将设计新型的边缘服务器量化和部署策略，以适应不同地区车流量以及城市建设导致的车流量变化。2.3 时延与能耗分析
ρ为服务请求车辆与目标服务器之间的距离(ρ的值与dist近似)；
μ为两个节点之间的信号传输速率。2.4 问题定义
3.1 SRL概览
3.2 基于模糊C均值聚类的路边单元划分
ε为误差阈值，当连续两次迭代结果的误差不超过该阈值时，认为达到最优，该过程最终收敛于Fm的局部极小值点或鞍点。3.3 基于强化学习的边缘服务器位置的确定
ΔCV是动作执行后的负载均衡指标变化量；
ΔTtotal为动作执行后的总时延变化量；
ΔECtotal为动作执行后的总能耗变化量；
z为常数，表示负载均衡指标的权重，其使负载均衡优化更加有效。
4.1 实验配置
4.2 实验对比分析
CQP策略基于K-medoids策略的结果，采用遗传算法进行进一步多目标综合优化，其负载均衡指数为1.1～1.2，优于K-medoids和Random Selection策略；
K-medoids和Random Selection策略的负载均衡指数均为1.4～1.5，其中Random Selection策略因聚类中心的选择存在随机性，其服务器部署策略的负载均衡效果不稳定，相比K-medoids策略存在部分时段更优或更差的情况。因此，SRL策略能有效优化车联网环境下边缘服务器间的负载均衡。
基于K-medoids的CQP策略采用遗传算法对K-medoids策略的结果进行进一步多目标优化，因此时延优化程度较高。在4种方法中，SRL策略的日服务请求响应平均时延在28日比Random Selection平均时延降低0.66%，比K-medoids平均时延降低0.32%，因为本文重点优化边缘服务器间的负载均衡，负载均衡优化所占权重较高，所以SRL策略对服务请求的响应时延优化效果略逊于CQP策略。
基于K-medoids的CQP策略，采用遗传算法对K-medoids策略的结果进行进一步多目标优化，因此能耗优化程度较高。4种策略中，相比Random Selection和K-medoids策略，SRL策略的日服务请求处理能耗在28日整体较优，因为本文重点优化边缘服务器间的负载均衡，负载均衡优化所占权重更高，所以SRL策略的服务请求处理能耗优化效果略逊于CQP策略。根据图示对比结果，SRL策略在降低车联网服务请求处理能耗方面具有有效性，CQP策略对能耗的优化更加明显。