CN110012039A - 一种车联网中基于admm的任务分配与功率控制方案 - Google Patents

Abstract

本发明涉及一种车联网场景中的移动边缘计算方案，该方法在满足时延要求的前提下，对车内用户设备的计算任务分配和传输功率控制问题进行了优化。把设备在计算任务分配率加权下的能源损耗作为目标函数，使用排队论方法获得用户设备和边缘计算节点的数据传输模型，通过非线性分式优化和交替方向乘子法的迭代来解决该优化问题。在每一轮循环中，外层循环解决非线性分式规划问题，内层循环更新初始值和变量，直到迭代的结果满足设定的阈值，确定各用户设备的任务量分配比率并得到最小化的能耗。本发明提供的技术方案可以有效降低用户设备的能耗并满足时延的要求，提高整个网络的计算能力。

Description

一种车联网中基于ADMM的任务分配与功率控制方案

技术领域

本发明涉及无线通信领域的移动边缘计算方案，具体涉及一种应用于车联网的通过调节用户设备计算任务分配与传输功率而提高用户设备能耗的方法与系统。

背景技术

作为物联网在交通运输领域的典型应用，车联网实现了在很少或没有人为干预的车辆中进行无所不在的信息共享，这对于实现未来智能交通系统至关重要。一方面，车联网会刺激道路安全、旅行援助和自动驾驶等领域的一系列具有严格时效性要求的应用程序快速发展；另一方面，增强现实、流媒体视频和在线游戏等丰富的多媒体物联网应用迅速发展，导致极大的工作负载数据需要被缓存和处理，这需求大量的计算、通信和存储资源。在传统的云计算模型中，云服务器的位置远离需求边，而且回传路径和主干网络能力有限，这就造成了不可预测的延迟，无法保证物联网提供可靠的服务质量和体验质量。

而作为物联网中快速的任务处理方法，车辆的边缘计算（VEC）将计算模式从远端的中心分布构架扩展到了分布式边缘服务器。在车联网中，计算、通信和存储资源被分配到接近用户的地方，并且分散在网络边缘。车联网可以被视为传统云计算的一种有益补充。在网络边缘处理较低计算需求和有严格时效性限制的任务可以消除过多的网络越点，这不仅减少了计算响应时间，也缓解了能力有限的回程链路的信号拥挤问题。进一步来说，车联网通过将耗能过多的工作负载转移到具有更高计算能力和持续能量供应的VEC节点上，大大提高了电池容量有限的智能手机和可穿戴设备等车内用户设备的续航时间。通过适宜的任务分配策略，本地计算的能量损耗以增加数据传输的能量消耗，以及由数据传输、边缘服务器上的工作负载处理及跨区引起的延迟为代价而被减少。

因此，实现VEC场景下的计算任务分配和功率控制是重要的问题。首先，由于车辆的快速移动造成信道状况和网络拓扑快速改变，在不同延迟约束下决定最优的任务分配比率是很困难的。而车辆也可能在数据传输或者任务处理期间离开路边单元的服务范围。其次，不同问题的任务分配变量由于VEC节点计算能力有限而相互耦合，从能量效率的角度出发，任务分配比率必须与功率控制进行联合优化。最后，由于在用户设备和VEC节点上的工作任务随机变化，无法得到确定的计算和通信资源的最佳利用方案。

发明内容

为解决上述现有技术中的不足，本发明的目的是提供一种适用于车联网场景下的移动边缘计算中计算任务分配比率和传输功率控制的联合优化算法。通过使用本发明的算法，可以在保证时延限制的前提下，合理分配待计算任务和传输功率，有效降低用户移动设备的能量消耗。

与最接近的现有技术相比，本发明提供的技术方案具有的优异效果是：

本发明介绍了怎样去实现有较高能效的车联网边缘计算方法，通过交替方向乘子法和非线性分式优化解决该能量消耗最小化问题，并考虑到包括本地计算和数据传输在内的能量消耗及由本地计算、数据传输、在VEC节点和路边单元的等待时间以及跨区造成的延迟。在VEC节点计算能力的约束条件下，提出分数形式的目标函数和耦合的优化变量，形成NP难问题

为了更好的搭建多任务多服务器计算模式，引入排队论。在考虑队列异质性的情况下，推导出在用户设备和VEC节点处的动态传输模型。并假设每个用户设备产生的工作量服从泊松分布，且任何一个用户设备和VEC节点的服务时间遵循指数分布，由此在用户设备和VEC节点的任务传输模型可以分别被视为M/M/1队列和M/M/c队列。

附图说明

图1是本发明提供的车联网边缘计算系统图；

图2是本发明提供的不同功率下归一化能量消耗随任务分配比率变化图；

图3是本发明提供的不同任务分配比率下归一化能量消耗随传输功率变化图；

图4是本发明提供的不同算法中能量消耗与用户设备数量关系图；

图5是本发明提供的不同功率下归一化能量消耗随路边单元服务半径变化图；

图6是本发明提供的算法收敛性与迭代次数关系图；

图7是本发明提供的不同用户设备数量下归一化能量消耗随任务分配比率变化图。

具体实施方式

下面结合附图对本发明的具体实施方式作进一步的详细说明。

以下描述和附图充分地示出本发明的具体实施方案，以使本领域的技术人员能够实践它们。其他实施方案可以包括结构的、逻辑的、电气的、过程的以及其他的改变。实施例仅代表可能的变化。除非明确要求，否则单独的组件和功能是可选的，并且操作的顺序可以变化。一些实施方案的部分和特征可以被包括在或替换其他实施方案的部分和特征。本发明的实施方案的范围包括权利要求书的整个范围，以及权利要求书的所有可获得的等同物。在本文中，本发明的这些实施方案可以被单独地或总地用术语“发明”来表示，这仅仅是为了方便，并且如果事实上公开了超过一个的发明，不是要自动地限制该应用的范围为任何单个发明或发明构思。

实施例一、

本发明模拟在车联网场景下多任务多服务器的场景，考虑到车辆较快的移动速度，待计算任务可能无法在一个路边单元的服务范围传输完毕，而接收计算结果时也会存在跨区问题。通过判断能否将任务分派到路边单元进行计算，以及协调任务分配的比率及传输功率，可以在保证时延要求的条件下降低用户设备能耗。通过中心控制器的调控，确定车辆所在位置属于的路边单元，完成计算结果的回传。同时需要考虑到由于多用户产生多任务，而路边单元的计算能力及存储能力有限而造成的等待时间。其系统模型图如图1所示，整个过程包括以下内容：

1、判断能否在路边单元的服务范围内完成数据传输。用户设备分配到路边单元的任务分配比率服从平均到达率为的泊松过程，车辆以速度运动，距路边单元边缘的距离为时，数据传输时间需不大于。且整个边缘计算过程的执行总时间不大于车辆离开该路段的时间。满足上述条件时，以任务分配比率将计算任务发送至路边单元。

2、算数执行执行过程中的时延主要由传输时间、等待时间和计算时间构成。

1）计算任务从车内用户设备发送到路边单元为两跳传输。其中从车内移动设备到车内转发器的信噪比为，从车内转发器大到路边单元的信噪比为，故而总信噪比为。在所传输数据包的大小为、信道带宽为时，传输时间通过下式得到：

2）有比例为的任务在本地计算，其对计算资源的需求为，对CPU资源的占有率，用户设备的本地计算能力，则得到本地计算时间：

3）有比例为的任务被分配到路边单元计算。路边单元配备有个等同的计算能力为的服务器。由于一个路边单元的服务范围内会有多个用户设备传输计算任务，其总的到达率为。在M/M/c队列模型和Erlang公式的基础上，得到待计算任务在路边单元的平均计算时间:

其中，，，

4）由于路边单元的处理能力有限，待计算任务必须在队列中等待。路边单元的传输处理速度为，则每一个计算结果在路边单元处的平均等待时间为：

5）当准备发送计算结果时，如果车辆已经运动到路边单元的服务范围之外了，计算结果将首先被发送到中心控制器，然后被转发至车辆所在的路边单元。此过程中的传输延时、在中心控制器的平均等待时间和在路边单元的等待时间可以认为是常量，由于计算结果的数据长度远小于计算任务，计算结果从路边单元到用户设备的时延可以忽略。因此跨区的延时可以表达为：

6）移动边缘计算过程的全部执行时间可以表达为：

3、计算过程中，用户设备的能量损耗主要包括本地计算的能量消耗和数据传输的能量消耗。

1）本地计算功率由CPU的固有特性和工作负载的复杂性决定，在任务计算期间可以视作常量，则本地计算的能量消耗为：

2）用户设备的数据传输功率为，则用户设备向车内转发器发送数据的能量损耗为：

3）在边缘计算执行过程中，用户设备的总能量损耗为：

实施例二、

本发明的优化算法分为两层迭代过程，外层迭代过程解决非线性分式优化问题，内层迭代过程对变量进行更新。其目标为最小化路边单元服务范围内辆车的整体能耗。该问题被表达为：

s.t.

由于不同的用户设备的任务分配变量是耦合的，因此优化目标不可分离。为了解决该问题，引入最优资源分配策略的本地副本并定义局部优化变量，使目标函数是可分离的：

s.t.

因此目标函数可以被分解为能并行解决的子问题，该问题为非凸问题。通过进一步数学变换，并定义目标函数值为，可以将该问题转化为凸优化问题，进而可以在迭代过程中被优化。加入限制条件后在每一次迭代时，下面的问题被解决：

当限制条件被满足时，所得结果即为该优化问题的最优解。通过解决下面的增广拉格朗日问题获得每一次内层迭代更新的变量及此次外层循环过程的最优解：

对变量进行初始化之后，在对偶变量的迭代过程中，满足目标函数收敛，残差收敛和对偶变量收敛条件后可以得到此次外层循环的最优解，并在满足设定的循环终止条件后，获得所求目标函数的最优解及最佳任务分配比率和最佳传输功率。

对于本发明，我们进行了大量仿真实验。如图2，随着的增长，即更多的任务被分配到边缘计算节点进行计算，能量损耗先降低后增加。这是由于在较小时，数据传输的能量要少于本地计算的能量，而后随着数据传输消耗的能量多于本地计算的能量。图3显示了随着传输功率的增加，传输速率在增大，然而数据传输所消耗能量的增长速度要快于传输速率的增加，因此表现为传输能量损耗的单调增加。图4反映了用户设备数量对三种不同优化方案下的能量损耗的影响。图5显示出随着随着路边单元覆盖范围的增加，能量损耗逐渐减少并趋于稳定。在图6所示的过程中，表明该算法的迭代可以在6~7次迭代中迅速收敛，即可以快速获得最优解。图7为不同用户设备数量下，能量损耗与任务分配比率的关系。该结果与图2、图4的结论一致。

以上实施例仅用以说明本发明的技术方案而非对其限制，尽管参照上述实施例对本发明进行了详细的说明，所属领域的普通技术人员依然可以对本发明的具体实施方式进行修改或者等同替换，这些未脱离本发明精神和范围的任何修改或者等同替换，均在申请待批的本发明的权利要求保护范围之内。

Claims (4)

1.一种车联网边缘计算场景下，基于交替方向乘子法（ADMM）的计算任务分配和功率控制方案，其特征在于，所述方法有以下步骤：

1）确定能否在车辆离开路边单元服务范围之前完成数据传输；

2）通过非线性分式优化和交替方向乘子法的迭代过程进行优化，获得使能量损耗最小的计算任务分配比率和传输功率；

3）路边单元的服务器对分配的任务进行计算，并在中心控制器的控制下，将计算的结果通过路边单元发送给车内移动设备。

2.如权利要求1步骤1）所述的判断过程，其特征在于，从用户设备到路边单元的任务量分配比率服从平均到达率为的泊松过程，在所述确定能否于车辆离开路边单元的服务范围之前完成数据传输的过程中，进一步包括：

1）在车辆进入路边单元的服务范围时，由车速和车辆与路边单元边缘的距离确定最大容忍时间，当数据传输时间小于该值时，可以进行数据传输；

2）在数据传输时间满足要求后，若整个边缘计算过程的执行时间不大于车辆离开该路段的时间，则按一定任务分配比率将计算任务发送至路边单元；

上述的判断过程，其特征在于，依据任务量分配比率，时延和能耗由本地计算过程和数据传输及边缘计算过程两部分构成，进一步包括：

1）分配的任务首先从车内移动设备转发至车内转发器，然后车内转发器用最大传输功率将此任务发送到路边单元，全过程为两跳传输；两跳的信噪比分别表示为：

其中，和分别代表了移动设备和转发器的传输功率，和表示从移动设备到转发器和从转发器到路边单元的信道增益，用表示高斯白噪声的单边功率谱密度，并得到两跳总信噪比：

进而对于所传输的大小为的数据包，当信道带宽为时，传输时间通过下式得到：

2）对于所述的在本地计算的任务，本地计算时间由待计算任务对计算资源的需求，移动设备的本地计算能力，待计算任务对CPU资源的占有率，平均到达率为和任务量分配比率导出：

3）对于被分配到路边单元的服务器进行计算的任务，等待被服务器计算的来自于不同移动设备的任务量有总到达率；路边单元具有个等同的服务器，每个服务器的计算能力为，在M/M/c队列模型和Erlang公式的基础上，得到计算任务在路边单元的平均处理时间：

其中，，

，

由于路边单元的处理能力有限，待计算任务在必须队列中等待，然后被路边单元处理并将结果发送给用户设备，因此每一个计算结果在路边单元处的平均等待时间为：

其中为路边单元的传输处理速度，由于计算结果的数据长度远小于计算任务，计算结果从路边单元到用户设备的时延可以忽略；当准备发送计算结果时，如果车辆已经运动到路边单元的覆盖范围之外了，计算结果将首先被发送到中心控制器，然后被转发至车辆所在的路边单元；此过程中的传输延时、在中心控制器的平均等待时间和在路边单元的等待时间可以认为是常量，因此跨区的延时可以表达为：

4）对所述的整个移动边缘计算过程的执行时间，有

。

3.如权利要求1步骤2）所述的优化方案，其特征在于，用户设备的能量损耗应包括本地计算的能量消耗和传输数据的能量消耗；定义为本地计算功率，它取决于CPU的固有特性和工作负载的复杂性，在任务执行期间可以被视为常量；

通过下得到用户设备的本地计算能量消耗：

通过下式得到用户设备向车内转发器发送数据的能量损耗：

通过下式得到用户设备的总能量损耗：

能耗优化方案为基于ADMM的计算任务分配和功率控制方案，其目标为最小化路边单元服务范围内辆车的整体能耗，定义优化变量集合，其中，，则所述的优化问题为：

s.t.

和为限制了工作负载的到达率和分别不能超过用户设备和路边单元的处理速率，确保了传输功率不超过用户设备的最大传输功率，和分别为数据传输和任务计算过程的延迟限制，为任务分配比率的边界限制；

在P1中，因为不同的用户设备的任务分配变量是耦合的，因此优化目标是不可分离的；为了解决该问题，进一步包括以下步骤：

1）引入最优资源分配策略的本地副本；使用一组新的变量来表示局部优化变量，定义和分别作为和的本地变量，则本地优化变量的集合被定义为，其中，,

则P1的次优问题可以表达为：

s.t.

2）P2通过引入局部变量使目标函数可分离，将目标函数分解为个可以被并行解决的子问题，这些分散的联合优化问题可以被表达为：

s.t.

目标函数P3依然是一个非凸问题，将P3的分子和分母分别定义为：

并定义作为P3的最优目标函数值：

其中和分别代表了最优本地计算任务分配比率和功率控制策略；

3）根据非线性分式优化问题，获得最优目标值的充分必要条件是：当且仅当方程

成立，即通过解决下面的问题得到最优的本地优化变量和：

s.t.

4）为每个用户设备定义本地变量集合，并定义函数：

由此，关于P2的凸优化问题可以表达为：

s.t.

5）定义关联于P5的最优变量集合，

在权利要求1步骤2）所述的迭代算法的每一次迭代过程中，下面的问题被解决：

s.t.

其中最优解在前一步迭代中获得，当限制条件被满足时，是所求优化问题P1的一组最优解。

4.如权利要求1步骤2）所述的优化方案，其特征在于，对于所述的迭代过程，定义对应于方程P6的拉格朗日乘子集合，定义正常数调整收敛速度，则P6 的增广拉格朗日公式可以被表达为：

该迭代过程包含两层循环，外循环为非线性分式优化问题，用n来指示迭代次数；内循环为原始变量和对偶变量的更新，用t来指示迭代次数，

进一步包括：

1）对工作任务分配比率、传输功率和最优解初始化，设置终止条件；

2）更新优化变量集合，给定第n次外循环的最优解，进而获得每个用户设备的传输功率；本地变量和的更新可以被分解为能够并行解决的个子问题；根据下式计算用户设备在第t次内循环时的获得的最优任务分配比率和传输功率：

3）更新；根据下式获得第次内循环时的全局最优任务分配比率：

根据下式获得第次内循环时的拉格朗日乘子：

4）更新最优解；在ADMM的初始变量和对偶变量的迭代过程中，当t趋于下确界时，满足目标函数收敛，残差收敛和对偶变量收敛条件；第n次迭代的内循环终止时得到和，则第次迭代的最优解按下式得到：

5）循环终止；当第n次外层循环满足时，通过下式获得最优任务分配比率、最优传输功率和最优解：

。