CN111314889B - Task unloading and resource allocation method based on mobile edge calculation in Internet of vehicles - Google Patents

Abstract

The invention discloses a task unloading and resource allocation method based on mobile edge calculation in the Internet of vehicles, which comprises the following specific steps: establishing a vehicle networking communication scene comprising vehicle-to-vehicle V2V and vehicle-to-infrastructure V2I communication; clustering vehicle nodes in a scene, and dividing the vehicle nodes into a V2I user cluster and a V2V user cluster; aiming at a V2V user cluster in a scene, dividing, pairing and optimizing a V2V request node and a service node in the V2V user cluster; calculating the total delay of task processing of all nodes in a scene; and establishing an optimization problem model by taking the minimization of the total delay of vehicle task processing in the vehicle networking system as a target and combining constraint conditions, and solving the optimization problem model by using a quantum particle group algorithm to obtain a channel and calculation resource allocation and each vehicle node power allocation strategy of the vehicle networking system. The invention solves the problem of task unloading and resource allocation based on MEC in the car networking environment with lower complexity.

Description

Translated fromChinese

车联网中基于移动边缘计算的任务卸载与资源分配方法Task offloading and resource allocation method based on mobile edge computing in Internet of Vehicles

技术领域Technical Field

本发明涉及车联网移动边缘计算的任务卸载与资源分配问题技术领域，具体涉及一种车联网中基于移动边缘计算的任务卸载与资源分配方法。The present invention relates to the technical field of task offloading and resource allocation problems of mobile edge computing in an Internet of Vehicles, and in particular to a task offloading and resource allocation method based on mobile edge computing in an Internet of Vehicles.

背景技术Background Art

随着移动网络技术的不断发展，人们对车载通信的研究不断深入。利用车联网(V2X)提供的高可靠、低延迟的无线通信服务，可以改善道路安全状况并提升驾驶体验。常见的车联网系统中，包含车-设施(V2I)、车-车(V2V)等信息交换路径。车辆请求任务可分为商娱类和安全类。商娱类请求涉及大量数据交换；安全类请求则对延迟有很高的要求。车载单元计算资源和计算能力有限，多接入边缘计算(MEC)作为一种新的计算范例，在网络边缘处提供计算服务，更接近终端用户，有助于降低设备成本，提高服务质量。通过将任务卸载到其他资源节点上进行处理，实现周围空闲计算资源共享，这样可以充分利用网络中的资源，同时可以降低车辆节点的开销。此外，由于大量设备对计算密集型任务进行迁移卸载，因此迫切需要大量的连接，蜂窝网络中的V2V用户可以通过复用V2I用户的上行信道直接相互通信，而不需要经过基站，提高了整个网络的频谱效率，从而允许网络接纳更多的用户，在一定程度上解决了频谱资源有限的问题。With the continuous development of mobile network technology, people's research on vehicle-to-vehicle communications has continued to deepen. The high-reliability, low-latency wireless communication services provided by the vehicle-to-everything (V2X) can improve road safety and enhance the driving experience. Common vehicle-to-everything systems include vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) information exchange paths. Vehicle request tasks can be divided into business and entertainment and safety categories. Business and entertainment requests involve a large amount of data exchange; safety requests have high requirements for latency. The computing resources and computing power of the vehicle-mounted unit are limited. Multi-access edge computing (MEC) is a new computing paradigm that provides computing services at the edge of the network, closer to end users, which helps reduce equipment costs and improve service quality. By offloading tasks to other resource nodes for processing, the surrounding idle computing resources can be shared, which can fully utilize the resources in the network and reduce the overhead of vehicle nodes. In addition, since a large number of devices migrate and offload computationally intensive tasks, a large number of connections are urgently needed. V2V users in cellular networks can communicate directly with each other by reusing the uplink channels of V2I users without going through base stations, which improves the spectrum efficiency of the entire network, allowing the network to accommodate more users and, to a certain extent, solves the problem of limited spectrum resources.

对车联网系统进行合理地规划，将任务卸载到其他资源节点上进行处理，并对车联网系统中的频带资源和计算资源进行合理的分配，可以在保证任务服务质量的前提下，使得车联网系统任务处理的总延迟最小。Reasonable planning of the Internet of Vehicles system, offloading tasks to other resource nodes for processing, and reasonable allocation of frequency band resources and computing resources in the Internet of Vehicles system can minimize the total delay of task processing in the Internet of Vehicles system while ensuring the quality of task service.

在现有的技术中，结合MEC的D2D通信增强蜂窝网络的计算能力，通过节点参数计算各种通信模式下传输延迟和计算延迟，然后根据资源限制建立任务卸载和功率分配的联合优化问题，获得最优的资源分配方案。在本发明技术方案的研究过程中至少发现，现有技术的缺点在于没有考虑D2D通信中D2D用户如何建立配对这一关键问题，而是默认D2D配对已确定。In the existing technology, the D2D communication of MEC is combined to enhance the computing power of the cellular network, and the transmission delay and computing delay in various communication modes are calculated through node parameters, and then the joint optimization problem of task offloading and power allocation is established according to resource constraints to obtain the optimal resource allocation solution. In the process of studying the technical solution of the present invention, it is at least found that the disadvantage of the existing technology is that it does not consider the key issue of how D2D users establish pairing in D2D communication, but assumes that the D2D pairing has been determined.

发明内容Summary of the invention

本发明的目的是为了解决现有技术中的上述缺陷，提供一种车联网中基于移动边缘计算的任务卸载与资源分配方法。具体地，根据车辆节点处理自身任务所需要的时间以及车辆节点与基站通信的信道容量，利用高斯聚类对场景中的车辆节点进行聚类；针对V2V用户，利用二分图法进行V2V请求用户与服务用户的配对；并在此基础上，建立优化问题对用户发送功率以及频谱、计算资源进行联合优化分配，从而使系统总延迟最小。The purpose of the present invention is to solve the above defects in the prior art and provide a method for task offloading and resource allocation based on mobile edge computing in the Internet of Vehicles. Specifically, according to the time required for the vehicle node to process its own task and the channel capacity for the vehicle node to communicate with the base station, Gaussian clustering is used to cluster the vehicle nodes in the scene; for V2V users, the bipartite graph method is used to pair the V2V requesting user with the service user; and on this basis, an optimization problem is established to jointly optimize the allocation of user transmission power, spectrum, and computing resources, so as to minimize the total delay of the system.

本发明的目的可以通过采取如下技术方案达到：The purpose of the present invention can be achieved by adopting the following technical solutions:

一种车联网中基于移动边缘计算的任务卸载与资源分配方法，所述的任务卸载与资源分配方法包括以下步骤：A method for task offloading and resource allocation based on mobile edge computing in an Internet of Vehicles, the method comprising the following steps:

S1、构建一个部署有基站、边缘计算服务器和车辆的车联网系统应用场景，车辆具备V2V和V2I通信能力，其中，V2V表示车辆对车辆，V2I表示车辆到基础设施，请求节点可以通过卸载将任务卸载到附近的服务节点进行处理，其中部分车辆和边缘计算服务器配备有限的信道和计算资源，可以为其他车辆提供计算服务，称为服务节点，提出任务计算请求的车辆，称为请求节点；S1. Build an application scenario of an Internet of Vehicles system with base stations, edge computing servers and vehicles. The vehicles have V2V and V2I communication capabilities, where V2V means vehicle-to-vehicle and V2I means vehicle-to-infrastructure. The requesting node can offload the task to a nearby service node for processing. Some vehicles and edge computing servers are equipped with limited channels and computing resources and can provide computing services to other vehicles, which are called service nodes. The vehicle that makes a task computing request is called a requesting node.

S2、根据车联网系统应用场景中车辆节点处理自身任务所需要的时间以及车辆节点与基站通信的信道容量，对车联网系统应用场景中的车辆节点运用高斯混合模型进行聚类，将车辆节点划分为V2V用户簇和V2I用户簇；S2. Based on the time required for vehicle nodes to process their own tasks in the application scenario of the Internet of Vehicles system and the channel capacity for communication between the vehicle nodes and the base station, the vehicle nodes in the application scenario of the Internet of Vehicles system are clustered using a Gaussian mixture model, and the vehicle nodes are divided into V2V user clusters and V2I user clusters;

S3、针对场景中的V2V用户簇，对其中的V2V请求节点与服务节点进行划分、配对并优化；S3: for the V2V user clusters in the scene, the V2V request nodes and service nodes therein are divided, paired and optimized;

S4、针对完成配对的V2V对以及V2I节点，计算整个车联网系统任务处理的总延迟D_total；S4. Calculate the total delay D_total of the entire Internet of Vehicles system task processing for the paired V2V pairs and V2I nodes;

S5、以最小化车联网系统任务处理总延迟D_total为目标，结合约束条件，建立最优化问题模型，采用量子粒子群(QPSO)算法进行求解，得到车联网系统频带、计算资源分配以及各个车辆节点功率分配的最优解，以保证车联网系统任务处理总延迟最小。S5. With the goal of minimizing the total delay D_total of task processing in the Internet of Vehicles system, combined with constraints, an optimization problem model is established, and the quantum particle swarm optimization (QPSO) algorithm is used to solve it. The optimal solution for the frequency band of the Internet of Vehicles system, computing resource allocation, and power allocation of each vehicle node is obtained to ensure that the total delay of task processing in the Internet of Vehicles system is minimized.

进一步地，所述的步骤S2包括：Furthermore, the step S2 comprises:

S2.1、根据车联网系统应用场景中车辆节点与基站通信的信道容量，对车辆节点的延迟与容量进行量化，过程如下：S2.1. According to the channel capacity of the communication between the vehicle node and the base station in the application scenario of the Internet of Vehicles system, the delay and capacity of the vehicle node are quantified. The process is as follows:

计算车辆节点处理自身任务所需要的时间组成一个集合T＝{t_m|m∈M}，M表示车辆节点的集合，第m个车辆节点的任务数据量用V_m表示，单位任务计算量用C_m表示，自身计算能力用f_m表示，那么第m个车辆节点处理自身任务所需要的时间t_m，表达式为：The time required for the vehicle node to process its own task is calculated to form a set T = {t_m | m∈M}, where M represents the set of vehicle nodes, the task data volume of the mth vehicle node is represented by V_m , the unit task calculation volume is represented by C_m , and the own computing power is represented by f_m . Then the time t_m required for the mth vehicle node to process its own task is expressed as:

计算车辆节点与基站通信的信道容量组成一个集合Γ＝{η_m|m∈M}，第m个车辆节点与基站通信的信道容量η_m，表达式为：The channel capacity between the vehicle node and the base station is calculated to form a set Γ＝{η_m |m∈M}. The channel capacity η_m between the mth vehicle node and the base station is expressed as:

其中，

是第m个车辆节点与基站通信时的信干噪比，其表达式为：in,

is the signal-to-interference-noise ratio when the mth vehicle node communicates with the base station, and its expression is:

上式中，

为第m个车辆节点的发送功率；LP(d)是第m个车辆节点与基站之间信道的路径损耗，LP(d)单位为dB，与第m个车辆节点与基站之间的距离d有关，

表示噪声的平均功率；In the above formula,

is the transmission power of the mth vehicle node; LP(d) is the path loss of the channel between the mth vehicle node and the base station. The unit of LP(d) is dB and is related to the distance d between the mth vehicle node and the base station.

represents the average power of the noise;

S2.2、对车联网系统应用场景中的车辆节点运用高斯混合模型进行聚类，将车辆节点划分为V2I用户簇和V2V用户簇。S2.2. The Gaussian mixture model is used to cluster the vehicle nodes in the application scenario of the Internet of Vehicles system, and the vehicle nodes are divided into V2I user clusters and V2V user clusters.

进一步地，所述的步骤S2.2包括：Furthermore, the step S2.2 comprises:

S2.2.1、根据步骤S2.1中的计算结果，建立一个新的M×2的矩阵B，矩阵B的第一列元素由M辆车处理自身任务所需时间集合T组成，矩阵B的第二列元素由M辆车与基站通信的信道容量集合Γ组成，新建一个由矩阵B的行向量为元素的集合X；S2.2.1. According to the calculation results in step S2.1, a new M×2 matrix B is established, wherein the first column of the matrix B is composed of the time set T required for the M vehicles to process their own tasks, and the second column of the matrix B is composed of the channel capacity set Γ for the M vehicles to communicate with the base station. A new set X is established, wherein the elements are the row vectors of the matrix B.

S2.2.2、将集合X中所有数据元素看做两个模型的高斯混合分布：S2.2.2. Consider all data elements in set X as Gaussian mixture distributions of two models:

其中，

表示第k个高斯分布的概率密度，

x_m表示集合X中的第m个元素，待求解参数为：两个高斯函数的均值和方差

以及π₁，π₂；in,

represents the probability density of the kth Gaussian distribution,

x_m represents the mth element in the set X. The parameters to be solved are: the mean and variance of the two Gaussian functions

and π₁ ,π₂ ;

S2.2.3、采用最大期望算法(Expectation-Maximization algorithm，EM算法)求解参数值：定义分量数目k＝2，对每个分量k设置参数π_k，

∑_k的初始值，对集合X中的数据元素求均值和协方差得到

和∑的初始值；S2.2.3. Use the Expectation-Maximization algorithm (EM algorithm) to solve the parameter value: define the number of components k = 2, set the parameter π_k for each component k,

∑_k is the initial value, and the mean and covariance of the data elements in the set X are obtained

and the initial values of ∑;

S2.2.4、根据当前的参数值，计算第k个混合的后验概率：S2.2.4. Calculate the posterior probability of the kth mixture based on the current parameter values:

上式中，t表示当前迭代次数；In the above formula, t represents the current number of iterations;

S2.2.5、使用步骤S2.2.4中的值最大化似然函数：S2.2.5. Maximize the likelihood function using the value in step S2.2.4:

根据第k个混合的后验概率p(z_mk)，求新一轮迭代的模型参数

According to the posterior probability p(z_mk ) of the kth mixture, find the model parameters for the new round of iteration

得到高斯混合模型的对数似然函数为：The log-likelihood function of the Gaussian mixture model is obtained as:

S2.2.6、判断似然函数是否收敛：若收敛，则输出参数

以及π₁、π₂；若不收敛，则返回步骤S2.2.3继续执行直至满足收敛条件；S2.2.6. Determine whether the likelihood function converges: If it converges, output the parameter

and π₁ , π₂ ; if not converged, return to step S2.2.3 and continue to execute until the convergence condition is met;

S2.2.7、利用基于最小错误概率的贝叶斯判别准则，获得每个节点所属类别，根据贝叶斯公式，第m个节点关于第k个高斯混合分布模型的后验概率公式为：S2.2.7. Using the Bayesian discriminant criterion based on the minimum error probability, the category to which each node belongs is obtained. According to the Bayesian formula, the posterior probability formula of the mth node with respect to the kth Gaussian mixture distribution model is:

其中，所述的基基于最小错误率的贝叶斯判别准则如下：The Bayesian discriminant criterion based on the minimum error rate is as follows:

a)若p(μ₁,∑₁|x_m)>p(μ₂,∑₂|x_m)，则判定节点x_m应选择第一种卸载方案；a) If p(μ₁ ,∑₁ |x_m )>p(μ₂ ,∑₂ |x_m ), then node x_m should choose the first offloading scheme;

b)若p(μ₁,∑₁|x_m)≤p(μ₂,∑₂|x_m)，则判定节点x_m应选择第二种卸载方案。b) If p(μ₁ ,∑₁ |x_m )≤p(μ₂ ,∑₂ |x_m ), then node x_m should choose the second offloading scheme.

进一步地，所述的步骤S3过程如下：Furthermore, the process of step S3 is as follows:

对步骤S2中聚类得到的V2V用户建立一个集合，记作

记集合中共有

个元素；用户y的任务数据量用V_y表示，单位任务计算量用C_y表示，自身计算能力用f_y表示。对V2V用户自身的计算能力进行排序，用车辆节点计算自身任务所需要的时间

作为对车辆自身计算能力的衡量，选择t_y值最大的

个节点划入V2V请求节点集J，集合中余下的

个节点划入V2V服务节点集K；建立成一个带权二分图，

个V2V请求节点作为二分图的一个顶点集，

个V2V服务节点作为二分图的另一个顶点集，两个顶点集之间的边的权重代表V2V请求节点与服务节点之间建立连接所获得的收益，该边的权重与V2V请求节点的任务数据量V_j、V2V服务节点的计算能力f_k以及通信节点间的链路质量有关，链路质量考虑节点之间距离d_jk的影响，因此定义ξ_jk表示带权二分图中边的权重：A set of V2V users clustered in step S2 is established, denoted as

There are a total of

elements; the task data volume of user y is represented by V_y , the unit task calculation volume is represented by_Cy , and the computing power itself is represented by f_y . The computing power of V2V users is sorted, and the time required for calculating their own tasks is calculated by vehicle nodes.

As a measure of the vehicle's own computing power, select the vehicle with the largest t_y value.

nodes are included in the V2V request node set J, and the remaining

nodes are included in the V2V service node set K; a weighted bipartite graph is established.

V2V request nodes are regarded as a vertex set of a bipartite graph.

The V2V service nodes are used as another vertex set of the bipartite graph. The weight of the edge between the two vertex sets represents the benefit obtained by establishing a connection between the V2V request node and the service node. The weight of the edge is related to the task data volume_Vj of the V2V request node, the computing power_fk of the V2V service node, and the link quality between the communication nodes. The link quality considers the influence of the distance_djk between the nodes. Therefore,_ξjk is defined to represent the weight of the edge in the weighted bipartite graph:

利用Kuhn-Munkres算法求解带权二分图的最大匹配方案作为V2V通信车辆节点与服务节点的配对方案，记作μ＝{μ_jk}，j∈J,k∈K。The Kuhn-Munkres algorithm is used to solve the maximum matching scheme of the weighted bipartite graph as the pairing scheme of the V2V communication vehicle node and the service node, denoted as μ={μ_jk }, j∈J, k∈K.

进一步地，所述的步骤S4中，定义V2I请求节点集合为I＝{1,…,i,..,I}，V2V请求用户集合为J＝{1,…,j,…,J}，V2V服务用户集合为K＝{1,…,k,…,K}，假设基站可以获得所有的信道状态信息，该步骤包括：Furthermore, in step S4, the V2I requesting node set is defined as I = {1, ..., i, ..., I}, the V2V requesting user set is defined as J = {1, ..., j, ..., J}, and the V2V service user set is defined as K = {1, ..., k, ..., K}. Assuming that the base station can obtain all channel state information, this step includes:

S4.1、计算V2I节点与基站通信的信干噪比

S4.1. Calculate the signal-to-interference-to-noise ratio of the communication between the V2I node and the base station

其中，β_ij∈{0,1}，β_ij＝1表示V2V请求节点j复用V2I节点i的上行信道，β_ij＝0表示V2V请求节点j没有复用V2I节点i的上行信道，每个V2V请求节点至多复用一个信道，即

p_i和p_j分别表示V2I请求节点i和V2V请求节点j的发送功率，满足车辆节点的功率峰值限制，即p_i，p_j<p^max，

表示V2I请求节点i在子信道n上的信道增益，∑_j∈Jβ_ijp_j|h_j|²表示V2V通信用户对V2I用户i的干扰，其中|h_j|表示V2V用户j通信时在子信道上的信道增益，N₀W是加性高斯白噪声的功率，W是子信道的带宽；Among them, β_ij ∈{0,1}, β_ij =1 means that the V2V request node j reuses the uplink channel of the V2I node i, and β_ij =0 means that the V2V request node j does not reuse the uplink channel of the V2I node i. Each V2V request node reuses at most one channel, that is,

p_i and p_j represent the transmission power of V2I request node i and V2V request node j, respectively, satisfying the peak power limit of vehicle nodes, that is, p_i , p_j < p^max ,

represents the channel gain of V2I requesting node i on subchannel n, ∑_j∈J β_ij p_j |h_j |² represents the interference of V2V communication user to V2I user i, where |h_j | represents the channel gain of V2V user j on the subchannel when communicating, N₀ W is the power of additive white Gaussian noise, and W is the bandwidth of the subchannel;

S4.2、计算V2V请求用户j与服务用户K通信时的信干噪比

S4.2. Calculate the signal-to-interference-noise ratio when the V2V requesting user j communicates with the serving user K

其中，

表示V2V通信时，V2I用户对V2V接收端用户的干扰，∑_{j′∈J,j′≠j}β_ij′p_j′|h_j′|²表示V2V通信时，其他V2V用户对V2V接收端用户的干扰；in,

represents the interference of V2I users to V2V receiving users during V2V communication, ∑_{j′∈J,j′≠j} β_ij′ p_j′ |h_j′ |² represents the interference of other V2V users to V2V receiving users during V2V communication;

S4.3、计算整个车联网系统任务处理的总延迟D_total，由V2I用户的卸载延迟和V2V用户的处理延迟组成，计算公式如下：S4.3. Calculate the total delay D_total of the entire vehicle networking system task processing, which is composed of the unloading delay of the V2I user and the processing delay of the V2V user. The calculation formula is as follows:

上式中，

表示所有V2I用户的任务处理总延迟，包括传输延迟和计算延迟，其中V_i表示V2I用户i的任务数据量，C_i表示计算1bit数据所需要的CPU周期数，f_i^e表示边缘服务器分配给每个V2I用户的计算资源；

表示所有V2V配对用户的任务处理总延迟，包括V2V请求用户的传输延迟以及V2V服务用户对自身任务和请求任务进行计算的延迟；

表示未能成功配对的V2V用户进行本地任务计算的延迟，其中，V_j表示V2V请求用户j的任务数据量，C_j、C_k分别表示计算1bit来自V2V请求用户和服务用户的任务所需要的CPU周期数，f_j、f_k分别表示V2V请求用户和服务用户的计算能力，μ_jk表示V2V配对策略。In the above formula,

represents the total task processing delay of all V2I users, including transmission delay and calculation delay, where_Vi represents the task data volume of V2I user i,_Ci represents the number of CPU cycles required to calculate 1 bit of data,^and_fie represents the computing resources allocated to each V2I user by the edge server;

It represents the total task processing delay of all V2V paired users, including the transmission delay of the V2V requesting user and the delay of the V2V service user to calculate its own task and the requested task;

represents the delay of the V2V user who failed to pair successfully to perform local task calculation, where_Vj represents the task data volume of V2V requesting user j,_Cj and_Ck represent the number of CPU cycles required to calculate 1 bit of task from V2V requesting user and serving user respectively,_fj and_fk represent the computing power of V2V requesting user and serving user respectively, and_μjk represents the V2V pairing strategy.

进一步地，所述的步骤S5中，以最小化车联网系统任务处理的总延迟D_total为目标，建立最优化问题模型如下：Furthermore, in step S5, with the goal of minimizing the total delay D_total of the task processing of the Internet of Vehicles system, an optimization problem model is established as follows:

C1:β_ij∈{0,1}，

C1:β_ij ∈{0,1},

C2:

C2:

C3:

C3:

C4:

C4:

C5:γ_i^c≥γ_i^th，

C5:γ_i^c ≥γ_i^th ,

C6:

C6:

上述约束条件中，C1表示β_ij，μ_jk的取值只能为0或1，

指示子信道的复用情况，μ_jk表示V2V请求节点与服务节点的配对情况，C2表示每个V2V请求节点至多复用一个信道，C3表示每个V2I节点和V2V配对用户发送节点的功率限制，C4表示边缘服务器分配给所有V2I车辆的计算资源总和应小于边缘服务器的总计算资源，C5表示每个V2I节点与基站进行通信的信干噪比应大于门限值γ_i^th，C6表示每个V2V用户进行通信的信干噪比应大于门限值

In the above constraints, C1 represents β_ij , and the value of μ_jk can only be 0 or 1.

indicates the multiplexing of subchannels, μ_jk indicates the pairing of V2V requesting nodes and service nodes, C2 indicates that each V2V requesting node can reuse at most one channel, C3 indicates the power limit of each V2I node and V2V paired user sending node, C4 indicates that the sum of computing resources allocated by the edge server to all V2I vehicles should be less than the total computing resources of the edge server, C5 indicates that the signal-to-noise ratio of each V2I node communicating with the base station should be greater than the threshold value γ_i^th , and C6 indicates that the signal-to-noise ratio of each V2V user communicating should be greater than the threshold value

本发明相对于现有技术具有如下的优点及效果：Compared with the prior art, the present invention has the following advantages and effects:

1)本发明公开的一种车联网中基于移动边缘计算的任务卸载与资源分配方法中，V2V用户复用V2I用户的上行信道，提高了车联网系统的频谱利用率；1) In a method for task offloading and resource allocation based on mobile edge computing in a vehicle networking system disclosed by the present invention, a V2V user reuses the uplink channel of a V2I user, thereby improving the spectrum utilization rate of the vehicle networking system;

2)本发明公开的一种车联网中基于移动边缘计算的任务卸载与资源分配方法，考虑了V2V通信中V2V用户如何建立配对这一关键问题；2) The present invention discloses a method for task offloading and resource allocation based on mobile edge computing in a connected vehicle network, which takes into account the key issue of how V2V users establish pairing in V2V communication;

3)本发明公开的一种车联网中基于移动边缘计算的任务卸载与资源分配方法，将任务卸载与资源分配方法分为三步进行，即聚类、配对和求解，在较低的计算难度和复杂度下获得了车联网系统的次优解。3) The present invention discloses a method for task offloading and resource allocation based on mobile edge computing in the Internet of Vehicles. The method is divided into three steps, namely clustering, pairing and solving, and a suboptimal solution for the Internet of Vehicles system is obtained with lower computational difficulty and complexity.

附图说明BRIEF DESCRIPTION OF THE DRAWINGS

图1是本发明实施例中公开的车联网任务卸载与资源分配方法流程图；FIG1 is a flow chart of a method for task offloading and resource allocation for Internet of Vehicles disclosed in an embodiment of the present invention;

图2是本发明实施例中公开的场景示意图；FIG2 is a schematic diagram of a scenario disclosed in an embodiment of the present invention;

图3是本发明实施例中对V2V通信车辆节点与服务节点进行配对方法流程图。FIG3 is a flow chart of a method for pairing a V2V communication vehicle node with a service node in an embodiment of the present invention.

具体实施方式DETAILED DESCRIPTION

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。In order to make the purpose, technical solution and advantages of the embodiments of the present invention clearer, the technical solution in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments are part of the embodiments of the present invention, not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without creative work are within the scope of protection of the present invention.

实施例Example

如图1所示，本发明的基本实施例公开了一种车联网中基于移动边缘计算的任务卸载与资源分配方法，本发明将基于移动边缘计算的车联网系统中的任务卸载与资源分配方法分为聚类、配对和求解三个主要步骤。其中利用配对和聚类两个步骤，通过综合考虑基于移动边缘计算的车联网系统中各车辆自身的任务数据量、计算能力以及车-基础设施(V2I)和车-车(V2V)的距离等因素，确定了使得卸载总延迟最小的各车辆任务卸载方式。具体步骤如下：As shown in Figure 1, the basic embodiment of the present invention discloses a method for task offloading and resource allocation based on mobile edge computing in an Internet of Vehicles system. The present invention divides the method for task offloading and resource allocation in an Internet of Vehicles system based on mobile edge computing into three main steps: clustering, pairing, and solving. Among them, by using the two steps of pairing and clustering, by comprehensively considering factors such as the amount of task data of each vehicle itself in the Internet of Vehicles system based on mobile edge computing, computing power, and the distance between vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V), the task offloading method for each vehicle is determined to minimize the total unloading delay. The specific steps are as follows:

S1、构建一个部署有基站、边缘计算服务器和车辆的车联网系统应用场景，车辆具备V2V和V2I通信能力，其中，V2V表示车辆对车辆，V2I表示车辆到基础设施，请求节点可以通过卸载将任务卸载到附近的服务节点进行处理，其中部分车辆和边缘计算服务器配备有限的信道和计算资源，可以为其他车辆提供计算服务，称为服务节点，提出任务计算请求的车辆，称为请求节点；S1. Build an application scenario of an Internet of Vehicles system with base stations, edge computing servers and vehicles. The vehicles have V2V and V2I communication capabilities, where V2V means vehicle-to-vehicle and V2I means vehicle-to-infrastructure. The requesting node can offload the task to a nearby service node for processing. Some vehicles and edge computing servers are equipped with limited channels and computing resources and can provide computing services to other vehicles, which are called service nodes. The vehicle that makes a task computing request is called a requesting node.

考虑一个有基站和车辆节点的V2X网络场景，MEC服务器部署于基站侧，车联网系统模型如图2所示。场景中有1个基站和密集部署的M个车辆节点，每个车辆节点带有一个计算任务，第m个节点的计算任务的属性用V_m，C_m，T_m表示，其中V_m(单位为：bits)表示计算任务的大小，C_m(单位为：cycles/bit)表示计算1bit数据所需要的CPU周期数，T_m表示第m个车辆节点的计算任务的最大处理时延。所有车辆配备有单个天线，因此车辆可以选择通过V2I通信将计算任务卸载到MEC服务器，或者通过V2V通信将计算任务卸载到空闲车辆。所以，场景中的车辆节点被分成三类：其中将计算任务卸载到MEC服务器的节点是V2I请求节点；将计算任务卸载到其他车辆节点的是V2V请求节点；接受来自其他节点的计算任务并处理的是空闲V2V服务节点。Consider a V2X network scenario with a base station and vehicle nodes. The MEC server is deployed on the base station side. The vehicle network system model is shown in Figure 2. There is one base station and M densely deployed vehicle nodes in the scenario. Each vehicle node has a computing task. The properties of the computing task of the mth node are represented by_Vm ,_Cm , and_Tm , where_Vm (in units of bits) represents the size of the computing task,_Cm (in units of cycles/bit) represents the number of CPU cycles required to calculate 1 bit of data, and_Tm represents the maximum processing delay of the computing task of the mth vehicle node. All vehicles are equipped with a single antenna, so the vehicle can choose to offload the computing task to the MEC server through V2I communication, or to offload the computing task to an idle vehicle through V2V communication. Therefore, the vehicle nodes in the scenario are divided into three categories: the node that offloads the computing task to the MEC server is the V2I request node; the node that offloads the computing task to other vehicle nodes is the V2V request node; and the node that accepts and processes the computing tasks from other nodes is the idle V2V service node.

S2、根据车联网系统应用场景中车辆节点处理自身任务所需要的时间以及车辆节点与基站通信的信道容量，对车联网系统应用场景中的车辆节点运用高斯混合模型进行聚类，将车辆节点划分为V2V用户簇和V2I用户簇，具体步骤如下：S2. Based on the time required for vehicle nodes to process their own tasks in the application scenario of the Internet of Vehicles system and the channel capacity for communication between the vehicle nodes and the base station, the vehicle nodes in the application scenario of the Internet of Vehicles system are clustered using a Gaussian mixture model, and the vehicle nodes are divided into V2V user clusters and V2I user clusters. The specific steps are as follows:

S2.1、根据场景中车辆节点与基站通信的信道容量，对车辆节点的延迟与容量进行量化。S2.1. According to the channel capacity of the vehicle node and the base station in the scenario, the delay and capacity of the vehicle node are quantified.

计算车辆节点处理自身任务所需要的时间组成一个集合T＝{t_m|m∈M}，M表示车辆节点的集合。假设第m个车辆节点自身的计算能力为f_m(单位为：cycle/s)，那么第m个车辆节点处理自身任务所需要的时间t_m，表达式为：The time required for the vehicle node to process its own task is calculated to form a set T = {t_m | m∈M}, where M represents the set of vehicle nodes. Assuming that the computing power of the mth vehicle node itself is f_m (unit: cycle/s), then the time t_m required for the mth vehicle node to process its own task is expressed as:

计算车辆节点与基站通信的信道容量组成一个集合Γ＝{η_m|m∈M}。第m个车辆节点与基站通信的信道容量η_m，表达式为：The channel capacity between the vehicle node and the base station is calculated to form a set Γ＝{η_m |m∈M}. The channel capacity η_m between the mth vehicle node and the base station is expressed as:

其中，

是第m个车辆节点与基站通信时的信干噪比，其表达式为：in,

is the signal-to-interference-noise ratio when the mth vehicle node communicates with the base station, and its expression is:

上式中，

为第m个车辆节点的发送功率；LP(d)(单位为：dB)是第m个车辆节点与基站之间信道的路径损耗，与第m个车辆节点与基站之间的距离d有关；

表示噪声的平均功率。In the above formula,

is the transmission power of the mth vehicle node; LP(d) (unit: dB) is the path loss of the channel between the mth vehicle node and the base station, which is related to the distance d between the mth vehicle node and the base station;

Represents the average power of the noise.

S2.2、对车联网系统应用场景中的车辆节点运用高斯混合模型进行聚类，将车辆节点划分为V2I用户簇和V2V用户簇。具体步骤如下：S2.2. Use the Gaussian mixture model to cluster the vehicle nodes in the application scenario of the Internet of Vehicles system and divide the vehicle nodes into V2I user clusters and V2V user clusters. The specific steps are as follows:

S2.2.1、根据步骤S2.1中的计算结果，建立一个新的M×2的矩阵B，矩阵B的第一列元素由M辆车处理自身任务所需时间集合T组成，矩阵B的第二列元素由M辆车与基站通信的信道容量集合Γ组成，新建一个由矩阵B的行向量为元素的集合X；S2.2.1. According to the calculation results in step S2.1, a new M×2 matrix B is established, wherein the first column of the matrix B is composed of the time set T required for the M vehicles to process their own tasks, and the second column of the matrix B is composed of the channel capacity set Γ for the M vehicles to communicate with the base station. A new set X is established, wherein the elements are the row vectors of the matrix B.

S2.2.2、将集合X中所有数据元素看做两个模型的高斯混合分布：S2.2.2. Consider all data elements in set X as Gaussian mixture distributions of two models:

其中，

x_m表示集合X中的第m个元素。待求解参数为：两个高斯函数的均值和方差

以及π₁，π₂；in,

x_m represents the mth element in the set X. The parameters to be solved are: the mean and variance of the two Gaussian functions

and π₁ ,π₂ ;

S2.2.3、采用最大期望算法(Expectation-Maximization algorithm，EM算法)求解参数值：定义分量数目k＝2，对每个分量k设置参数π_k，

∑_k的初始值，对集合X中的数据元素求均值和协方差得到

和∑的初始值；S2.2.3. Use the Expectation-Maximization algorithm (EM algorithm) to solve the parameter value: define the number of components k = 2, set the parameter π_k for each component k,

∑_k is the initial value, and the mean and covariance of the data elements in the set X are obtained

and the initial values of ∑;

S2.2.4、根据当前的参数值，计算第k个混合的后验概率：S2.2.4. Calculate the posterior probability of the kth mixture based on the current parameter values:

上式中，t表示当前迭代次数；In the above formula, t represents the current number of iterations;

S2.2.5、使用步骤S2.2.4中的值最大化似然函数：S2.2.5. Maximize the likelihood function using the value in step S2.2.4:

根据第k个混合的后验概率p(z_mk)，求新一轮迭代的模型参数

According to the posterior probability p(z_mk ) of the kth mixture, find the model parameters for the new round of iteration

得到高斯混合模型的对数似然函数为：The log-likelihood function of the Gaussian mixture model is obtained as:

S2.2.6、判断似然函数是否收敛：若收敛，则输出参数

以及π₁、π₂；若不收敛，则返回步骤S2.2.3继续执行直至满足收敛条件；S2.2.6. Determine whether the likelihood function converges: If it converges, output the parameter

and π₁ , π₂ ; if not converged, return to step S2.2.3 and continue to execute until the convergence condition is met;

S2.2.7、利用基于最小错误概率的贝叶斯判别准则，获得每个节点所属类别。根据贝叶斯公式，后验概率公式为：S2.2.7. Use the Bayesian discriminant criterion based on the minimum error probability to obtain the category to which each node belongs. According to the Bayesian formula, the posterior probability formula is:

其中，所述的基基于最小错误率的贝叶斯判别准则如下：The Bayesian discriminant criterion based on the minimum error rate is as follows:

a)若p(μ₁,∑₁|x_m)>p(μ₂,∑₂|x_m)，则判定节点x_m应选择第一种卸载方案；a) If p(μ₁ ,∑₁ |x_m )>p(μ₂ ,∑₂ |x_m ), then node x_m should choose the first unloading scheme;

b)若p(μ₁,∑₁|x_m)≤p(μ₂,∑₂|x_m)，则判定节点x_m应选择第二种卸载方案。b) If p(μ₁ ,∑₁ |x_m )≤p(μ₂ ,∑₂ |x_m ), then node x_m should choose the second offloading scheme.

S3、针对场景中的V2V用户簇，对其中的V2V请求节点与服务节点进行划分、配对并优化；S3: for the V2V user clusters in the scene, the V2V request nodes and service nodes therein are divided, paired and optimized;

如图3所示，具体步骤如下：As shown in Figure 3, the specific steps are as follows:

对步骤S2中聚类得到的V2V用户建立一个集合，记作

即集合中共有

个元素；对V2V用户自身的计算能力进行排序，用车辆节点计算自身任务所需要的时间

作为对车辆自身计算能力的衡量，选择t_y值最大的

个节点划入V2V请求节点集J，集合中余下的

个节点划入V2V服务节点集K；建立成一个带权二分图，

个V2V请求节点作为二分图的一个顶点集，

个V2V服务节点作为二分图的另一个顶点集，两个顶点集之间的边的权重代表V2V请求节点与服务节点之间建立连接所获得的收益，该边的权重与V2V请求节点的任务数据量V_j、V2V服务节点的计算能力f_k以及通信节点间的链路质量有关，链路质量主要考虑节点之间距离d_jk的影响，因此定义ξ_jk来表示带权二分图中边的权重：A set of V2V users clustered in step S2 is established, denoted as

That is, there are

elements; sort the computing power of V2V users themselves, and use vehicle nodes to calculate the time required for their own tasks

As a measure of the vehicle's own computing power, select the vehicle with the largest t_y value.

nodes are included in the V2V request node set J, and the remaining

nodes are included in the V2V service node set K; a weighted bipartite graph is established.

V2V request nodes are regarded as a vertex set of a bipartite graph.

The V2V service nodes are used as another vertex set of the bipartite graph. The weight of the edge between the two vertex sets represents the benefit obtained by establishing a connection between the V2V request node and the service node. The weight of the edge is related to the task data volume_Vj of the V2V request node, the computing power_fk of the V2V service node, and the link quality between the communication nodes. The link quality mainly considers the influence of the distance_djk between the nodes. Therefore,_ξjk is defined to represent the weight of the edge in the weighted bipartite graph:

利用二分图最大权匹配算法——KM算法(Kuhn-Munkres Algorithm)求解带权二分图的最大匹配方案作为V2V通信车辆节点与服务节点的配对方案，记作μ＝{μ_jk}，j∈J,k∈K。The Kuhn-Munkres Algorithm (KM Algorithm), a maximum weighted matching algorithm for bipartite graphs, is used to solve the maximum matching scheme of the weighted bipartite graph as the pairing scheme of the V2V communication vehicle nodes and service nodes, denoted as μ={μ_jk }, j∈J, k∈K.

S4、针对完成配对的V2V对以及V2I节点，计算整个车联网系统任务处理的总延迟D_total。S4. For the paired V2V pairs and V2I nodes, calculate the total delay D_total of the entire Internet of Vehicles system task processing.

V2I请求节点集合为I＝{1,…,i,..,I}；V2V请求用户集合为J＝{1,…,j,…,J}；V2V服务用户集合为K＝{1,…,k,…,K}。基站可以获得所有的信道状态信息。The V2I requesting node set is I = {1, ..., i, ..., I}; the V2V requesting user set is J = {1, ..., j, ..., J}; the V2V service user set is K = {1, ..., k, ..., K}. The base station can obtain all channel state information.

具体步骤如下：The specific steps are as follows:

S4.1、计算V2I节点与基站通信的信干噪比

S4.1. Calculate the signal-to-interference-to-noise ratio of the communication between the V2I node and the base station

其中，β_ij∈{0,1}，β_ij＝1表示V2V请求节点j复用V2I节点i的上行信道，β_ij＝0表示V2V请求节点j没有复用V2I节点i的上行信道，每个V2V请求节点至多复用一个信道，即

p_i和p_j分别表示V2I请求节点i和V2V请求节点j的发送功率，它们都应该满足车辆节点的功率峰值限制，即p_i，p_j<p^max，

表示V2I请求节点i在子信道n上的信道增益，∑_j∈Jβ_ijp_j|h_j|²表示V2V通信用户对V2I用户i的干扰，其中|h_j|表示V2V用户j通信时在子信道上的信道增益，N₀W是加性高斯白噪声的功率，其中W是子信道的带宽；Among them, β_ij ∈{0,1}, β_ij =1 means that the V2V request node j reuses the uplink channel of the V2I node i, and β_ij =0 means that the V2V request node j does not reuse the uplink channel of the V2I node i. Each V2V request node reuses at most one channel, that is,

p_i and p_j represent the transmission power of V2I request node i and V2V request node j respectively, and they should both meet the power peak limit of vehicle nodes, that is, p_i , p_j < p^max ,

represents the channel gain of V2I requesting node i on subchannel n, ∑_j∈J β_ij p_j |h_j |² represents the interference of V2V communication user to V2I user i, where |h_j | represents the channel gain of V2V user j on the subchannel when communicating, N₀ W is the power of additive white Gaussian noise, where W is the bandwidth of the subchannel;

S4.2、计算V2V请求用户j与服务用户K通信时的信干噪比

S4.2. Calculate the signal-to-interference-noise ratio when the V2V requesting user j communicates with the serving user K

其中，

表示V2V通信时，V2I用户对V2V接收端用户的干扰，∑_{j′∈J,j′≠j}β_ij′p_j′|h_j′|²表示V2V通信时，其他V2V用户对V2V接收端用户的干扰；in,

represents the interference of V2I users to V2V receiving users during V2V communication, ∑_{j′∈J,j′≠j} β_ij′ p_j′ |h_j′ |² represents the interference of other V2V users to V2V receiving users during V2V communication;

S4.3、计算整个车联网系统任务处理的总延迟D_total，由V2I用户的卸载延迟和V2V用户的处理延迟组成，计算公式如下：S4.3. Calculate the total delay D_total of the entire vehicle networking system task processing, which is composed of the unloading delay of the V2I user and the processing delay of the V2V user. The calculation formula is as follows:

上式中，

表示所有V2I用户的任务处理总延迟，包括传输延迟和计算延迟，其中V_i表示V2I用户i的任务数据量，C_i表示计算1bit数据所需要的CPU周期数，f_i^e表示边缘服务器分配给每个V2I用户的计算资源；

表示所有V2V配对用户的任务处理总延迟，包括V2V请求用户的传输延迟以及V2V服务用户对自身任务和请求任务进行计算的延迟；

表示未能成功配对的V2V用户进行本地任务计算的延迟，其中，V_j表示V2V请求用户j的任务数据量，C_j、C_k分别表示计算1bit来自V2V请求用户和服务用户的任务所需要的CPU周期数，f_j、f_k分别表示V2V请求用户和服务用户的计算能力，μ_jk表示V2V配对策略。特别地，V2V服务用户只有在自身任务处理完之后才能处理来自V2V请求用户的任务。In the above formula,

represents the total task processing delay of all V2I users, including transmission delay and calculation delay, where_Vi represents the task data volume of V2I user i,_Ci represents the number of CPU cycles required to calculate 1 bit of data,^and_fie represents the computing resources allocated to each V2I user by the edge server;

It represents the total task processing delay of all V2V paired users, including the transmission delay of the V2V requesting user and the delay of the V2V service user to calculate its own task and the requested task;

represents the delay of the V2V user that failed to pair successfully to perform local task calculation, where_Vj represents the task data volume of V2V requesting user j,_Cj and_Ck represent the number of CPU cycles required to calculate 1 bit of tasks from V2V requesting user and service user, respectively,_fj and_fk represent the computing power of V2V requesting user and service user, respectively, and_μjk represents the V2V pairing strategy. In particular, the V2V service user can only process the tasks from the V2V requesting user after processing its own tasks.

S5、以最小化车联网系统任务处理的总延迟D_total为目标，结合约束条件，建立最优化问题模型，采用量子粒子群(QPSO)算法进行求解，得到车联网系统频带、计算资源分配以及各个车辆节点功率分配的最优解，以保证车联网系统任务处理的总延迟最小。S5. With the goal of minimizing the total delay D_total of the task processing of the Internet of Vehicles system, combined with the constraints, an optimization problem model is established, and the quantum particle swarm optimization (QPSO) algorithm is used to solve it. The optimal solution for the frequency band of the Internet of Vehicles system, computing resource allocation, and power allocation of each vehicle node is obtained to ensure that the total delay of the task processing of the Internet of Vehicles system is minimized.

之前步骤中已经对车辆节点进行分类和配对，得到V2I用户集合I、V2V请求用户集合J和V2V服务用户集合K，以及V2V配对策略μ_jk，在此基础上，通过信道、计算资源分配以及功率控制，以最小化车联网系统任务处理的总延迟D_total为目标，建立最优化问题模型如下：In the previous steps, the vehicle nodes have been classified and paired to obtain the V2I user set I, V2V request user set J, V2V service user set K, and V2V pairing strategy μ_jk . On this basis, through channel and computing resource allocation and power control, with the goal of minimizing the total delay D_total of the task processing of the Internet of Vehicles system, the optimization problem model is established as follows:

C1:β_ij∈{0,1}，

C1:β_ij ∈{0,1},

C2:

C2:

C3:

C3:

C4:

C4:

C5:γ_i^c≥γ_i^th，

C5:γ_i^c ≥γ_i^th ,

C6:

C6:

上述约束条件中，C1表示β_ij，μ_jk的取值只能为0或1，

指示子信道的复用情况，μ_jk表示V2V请求节点与服务节点的配对情况，C2表示每个V2V请求节点至多复用一个信道，C3表示每个V2I节点和V2V配对用户发送节点的功率限制，C4表示边缘服务器分配给所有V2I车辆的计算资源总和应小于边缘服务器的总计算资源，C5表示每个V2I节点与基站进行通信的信干噪比应大于门限值γ_i^th，C6表示每个V2V用户进行通信的信干噪比应大于门限值

In the above constraints, C1 represents β_ij , and the value of μ_jk can only be 0 or 1.

indicates the multiplexing of subchannels, μ_jk indicates the pairing of V2V requesting nodes and service nodes, C2 indicates that each V2V requesting node can reuse at most one channel, C3 indicates the power limit of each V2I node and V2V paired user sending node, C4 indicates that the sum of computing resources allocated by the edge server to all V2I vehicles should be less than the total computing resources of the edge server, C5 indicates that the signal-to-noise ratio of each V2I node communicating with the base station should be greater than the threshold value γ_i^th , and C6 indicates that the signal-to-noise ratio of each V2V user communicating should be greater than the threshold value

上述优化问题是一个混合整数规划问题，本实施例采用量子粒子群(QPSO)算法对其进行求解，用较低的复杂度获得全局次优解。具体求解过程如下：The above optimization problem is a mixed integer programming problem. This embodiment uses the quantum particle swarm (QPSO) algorithm to solve it and obtain a global suboptimal solution with lower complexity. The specific solution process is as follows:

首先，优化问题要将N个子信道分配给所有用户，假设有Q个粒子，每个粒子的位置向量由四个部分组成，第q个粒子的位置向量表示为：First, the optimization problem is to allocate N sub-channels to all users. Assuming there are Q particles, the position vector of each particle consists of four parts. The position vector of the qth particle is expressed as:

X_q＝(β₁₁,…,β_IJ，f₁^e,…,f_I^e,p₁,…,p_I，p₁,…,p_J) (16)X_q = (β₁₁ ,…,β_IJ ,f₁^e ,…,f_I^e ,p₁ ,…,p_I ,p₁ ,…,p_J ) (16)

其中，第一部分β₁₁,…,β_IJ是V2V通信用户的信道资源复用情况指示，第二部分f₁^e,…,f_I^e是边缘服务器分配给每个V2I用户的计算资源，第三部分p₁,…,p_I是每个V2I通信用户的发射功率；第四部分p₁,…,p_J是V2V通信发送方的发射功率。引入惩罚函数，将原始带约束的最优化问题转化为一个无约束优化问题，转换后的新目标函数如下：Among them, the first part β₁₁ ,…,β_IJ is the indication of the channel resource reuse of the V2V communication user, the second part f₁^e ,…,f_I^e is the computing resource allocated by the edge server to each V2I user, the third part p₁ ,…,p_I is the transmission power of each V2I communication user; the fourth part p₁ ,…,p_J is the transmission power of the V2V communication sender. The penalty function is introduced to transform the original constrained optimization problem into an unconstrained optimization problem. The new objective function after the transformation is as follows:

其中，f(β_ij,f_i^e,p_i,p_j)表示原问题中的目标函数，

是惩罚因子，P_f(β_ij,f_i^e,p_i,p_j)是惩罚函数，包含原问题中的所有约束条件：Among them, f(β_ij ,_fi^e ,_pi ,p_j ) represents the objective function in the original problem,

is the penalty factor, P_f (β_ij ,f_i^e ,_pi ,p_j ) is the penalty function, which contains all the constraints in the original problem:

利用QPSO算法求解上式(15)。首先，计算粒子的平均最好位置C(s)，它等于所有粒子的最佳位置的平均值：The QPSO algorithm is used to solve the above equation (15). First, the average best position of the particle C(s) is calculated, which is equal to the average of the best positions of all particles:

其中，s表示迭代次数；Q是粒子数；

表示当前迭代中第q个粒子的最佳位置。Where s represents the number of iterations; Q is the number of particles;

represents the best position of the qth particle in the current iteration.

然后，进行粒子的位置更新，过程如下：Then, the particle position is updated, and the process is as follows:

其中，P_q(s)用于第q个粒子的位置更新；

可通过以下公式获得：Among them, P_q (s) is used to update the position of the qth particle;

It can be obtained by the following formula:

G_best(s)表示当前迭代中所有粒子的全局最优位置，通过比较所有粒子的最佳位置

的适应度函数获得：G_best (s) represents the global optimal position of all particles in the current iteration.

The fitness function is obtained:

粒子位置的更新公式为：The update formula of particle position is:

其中，s是迭代次数，X_q(s)表示第q个粒子在第s次迭代中的位置，ε代表收缩扩张系数，一般不大于1，u和r为在(0,1)上均匀分布的随机数。Where s is the number of iterations,_Xq (s) represents the position of the qth particle in the sth iteration, ε represents the contraction and expansion coefficient, which is generally not greater than 1, and u and r are random numbers uniformly distributed on (0,1).

QPSO算法具体步骤如下：The specific steps of the QPSO algorithm are as follows:

初始化每个粒子的位置X_q(0)、最大迭代次数S，此时

根据上式(20)，全局最佳位置G(0)取

中的最佳位置。Initialize the position of each particle_Xq (0) and the maximum number of iterations S.

According to the above formula (20), the global optimal position G(0) is

The best location in.

迭代次数s从0开始，对于从1到Q的每个粒子，按照以下步骤执行，直到s＝S-1，即迭代次数达到最大迭代次数S；The number of iterations s starts from 0. For each particle from 1 to Q, the following steps are performed until s = S-1, that is, the number of iterations reaches the maximum number of iterations S;

根据公式(19)和(20)，计算C(s)和P_q(s)；According to formulas (19) and (20), calculate C(s) and_Pq (s);

根据公式(24)，更新粒子的位置X_q(s)；According to formula (24), update the particle position_Xq (s);

根据公式(17)中的适应度函数，更新

判断F[X_q(s)]与

的大小，如果

则

否则

According to the fitness function in formula (17), update

Determine whether F[X_q (s)] and

If the size

but

otherwise

根据公式(17)，更新G(s)：如果

则G(s)＝G(s-1)，否则

According to formula (17), update G(s): if

Then G(s)＝G(s-1), otherwise

根据公式(17)，计算在全局最佳的位置处对应的值，得到的结果就是所求的全局次优解。According to formula (17), the corresponding value at the global optimal position is calculated, and the result obtained is the desired global suboptimal solution.

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。The above embodiments are preferred implementation modes of the present invention, but the implementation modes of the present invention are not limited to the above embodiments. Any other changes, modifications, substitutions, combinations, and simplifications that do not deviate from the spirit and principles of the present invention should be equivalent replacement methods and are included in the protection scope of the present invention.

Claims (3)

Translated fromChinese

1.一种车联网中基于移动边缘计算的任务卸载与资源分配方法，其特征在于，所述的任务卸载与资源分配方法包括以下步骤：1. A method for task offloading and resource allocation based on mobile edge computing in an Internet of Vehicles, characterized in that the method for task offloading and resource allocation comprises the following steps:S1、构建一个部署有基站、边缘计算服务器和车辆的车联网系统应用场景，车辆具备V2V和V2I通信能力，其中，V2V表示车辆对车辆，V2I表示车辆到基础设施，请求节点可以通过卸载将任务卸载到附近的服务节点进行处理，其中部分车辆和边缘计算服务器配备有限的信道和计算资源，可以为其他车辆提供计算服务，称为服务节点，提出任务计算请求的车辆，称为请求节点；S1. Build an application scenario of an Internet of Vehicles system with base stations, edge computing servers and vehicles. The vehicles have V2V and V2I communication capabilities, where V2V means vehicle-to-vehicle and V2I means vehicle-to-infrastructure. The requesting node can offload the task to a nearby service node for processing. Some vehicles and edge computing servers are equipped with limited channels and computing resources and can provide computing services to other vehicles, which are called service nodes. The vehicle that makes a task computing request is called a requesting node.S2、根据车联网系统应用场景中车辆节点处理自身任务所需要的时间以及车辆节点与基站通信的信道容量，对车联网系统应用场景中的车辆节点运用高斯混合模型进行聚类，将车辆节点划分为V2V用户簇和V2I用户簇；S2. Based on the time required for vehicle nodes to process their own tasks in the application scenario of the Internet of Vehicles system and the channel capacity for communication between the vehicle nodes and the base station, the vehicle nodes in the application scenario of the Internet of Vehicles system are clustered using a Gaussian mixture model, and the vehicle nodes are divided into V2V user clusters and V2I user clusters;S3、针对场景中的V2V用户簇，对其中的V2V请求节点与服务节点进行划分、配对并优化；S3: for the V2V user clusters in the scene, the V2V request nodes and service nodes therein are divided, paired and optimized;S4、针对完成配对的V2V对以及V2I节点，计算整个车联网系统任务处理的总延迟D_total；S4. Calculate the total delay D_total of the entire Internet of Vehicles system task processing for the paired V2V pairs and V2I nodes;S5、以最小化车联网系统任务处理总延迟D_total为目标，结合约束条件，建立最优化问题模型，采用量子粒子群算法进行求解，得到车联网系统频带、计算资源分配以及各个车辆节点功率分配的最优解，以保证车联网系统任务处理总延迟最小；S5. With the goal of minimizing the total delay D_total of the task processing of the Internet of Vehicles system, combined with the constraints, an optimization problem model is established, and the quantum particle swarm algorithm is used to solve it, and the optimal solution of the frequency band of the Internet of Vehicles system, the allocation of computing resources, and the power allocation of each vehicle node is obtained to ensure that the total delay of the task processing of the Internet of Vehicles system is minimized;其中，所述的步骤S2包括：Wherein, the step S2 comprises:S2.1、根据车联网系统应用场景中车辆节点与基站通信的信道容量，对车辆节点的延迟与容量进行量化，过程如下：S2.1. According to the channel capacity of the communication between the vehicle node and the base station in the application scenario of the Internet of Vehicles system, the delay and capacity of the vehicle node are quantified. The process is as follows:计算车辆节点处理自身任务所需要的时间组成一个集合T＝{t_m|m∈M}，M表示车辆节点的集合，第m个车辆节点的任务数据量用V_m表示，单位任务计算量用C_m表示，自身计算能力用f_m表示，那么第m个车辆节点处理自身任务所需要的时间t_m，表达式为：The time required for the vehicle node to process its own task is calculated to form a set T = {t_m | m∈M}, where M represents the set of vehicle nodes, the task data volume of the mth vehicle node is represented by V_m , the unit task calculation volume is represented by C_m , and the own computing power is represented by f_m . Then the time t_m required for the mth vehicle node to process its own task is expressed as:

计算车辆节点与基站通信的信道容量组成一个集合Γ＝{η_m|m∈M}，第m个车辆节点与基站通信的信道容量η_m，表达式为：The channel capacity between the vehicle node and the base station is calculated to form a set Γ＝{η_m |m∈M}. The channel capacity η_m between the mth vehicle node and the base station is expressed as:

其中，

是第m个车辆节点与基站通信时的信干噪比，其表达式为：in,

is the signal-to-interference-noise ratio when the mth vehicle node communicates with the base station, and its expression is:

上式中，

为第m个车辆节点的发送功率；LP(d)是第m个车辆节点与基站之间信道的路径损耗，LP(d)单位为dB，与第m个车辆节点与基站之间的距离d有关，

表示噪声的平均功率；In the above formula,

is the transmission power of the mth vehicle node; LP(d) is the path loss of the channel between the mth vehicle node and the base station. The unit of LP(d) is dB and is related to the distance d between the mth vehicle node and the base station.

represents the average power of the noise;S2.2、对车联网系统应用场景中的车辆节点运用高斯混合模型进行聚类，将车辆节点划分为V2I用户簇和V2V用户簇；S2.2. Use the Gaussian mixture model to cluster the vehicle nodes in the application scenario of the Internet of Vehicles system, and divide the vehicle nodes into V2I user clusters and V2V user clusters;其中，所述的步骤S2.2包括：Wherein, the step S2.2 comprises:S2.2.1、根据步骤S2.1中的计算结果，建立一个新的M×2的矩阵B，矩阵B的第一列元素由M辆车处理自身任务所需时间集合T组成，矩阵B的第二列元素由M辆车与基站通信的信道容量集合Γ组成，新建一个由矩阵B的行向量为元素的集合X；S2.2.1. According to the calculation results in step S2.1, a new M×2 matrix B is established, wherein the first column of the matrix B is composed of the time set T required for the M vehicles to process their own tasks, and the second column of the matrix B is composed of the channel capacity set Γ for the M vehicles to communicate with the base station. A new set X is established, wherein the elements are the row vectors of the matrix B.S2.2.2、将集合X中所有数据元素看做两个模型的高斯混合分布：S2.2.2. Consider all data elements in set X as Gaussian mixture distributions of two models:

其中，

表示第k个高斯分布的概率密度，

x_m表示集合X中的第m个元素，待求解参数为：两个高斯函数的均值和方差

以及π₁，π₂；in,

represents the probability density of the kth Gaussian distribution,

x_m represents the mth element in the set X. The parameters to be solved are: the mean and variance of the two Gaussian functions

and π₁ ,π₂ ;S2.2.3、采用最大期望算法求解参数值：定义分量数目k＝2，对每个分量k设置参数π_k，

∑_k的初始值，对集合X中的数据元素求均值和协方差得到

和∑的初始值；S2.2.3. Use the maximum expectation algorithm to solve the parameter value: define the number of components k = 2, set the parameter π_k for each component k,

∑_k is the initial value, and the mean and covariance of the data elements in the set X are obtained

and the initial values of ∑;S2.2.4、根据当前的参数值，计算第k个混合的后验概率：S2.2.4. Calculate the posterior probability of the kth mixture based on the current parameter values:

上式中，t表示当前迭代次数；In the above formula, t represents the current number of iterations;S2.2.5、使用步骤S2.2.4中的值最大化似然函数：S2.2.5. Maximize the likelihood function using the value in step S2.2.4:根据第k个混合的后验概率p(z_mk)，求新一轮迭代的模型参数

According to the posterior probability p(z_mk ) of the kth mixture, find the model parameters for the new round of iteration

得到高斯混合模型的对数似然函数为：The log-likelihood function of the Gaussian mixture model is obtained as:

S2.2.6、判断似然函数是否收敛：若收敛，则输出参数

以及π₁、π₂；若不收敛，则返回步骤S2.2.3继续执行直至满足收敛条件；S2.2.6. Determine whether the likelihood function converges: If it converges, output the parameter

and π₁ , π₂ ; if not converged, return to step S2.2.3 and continue to execute until the convergence condition is met;S2.2.7、利用基于最小错误概率的贝叶斯判别准则，获得每个节点所属类别，根据贝叶斯公式，第m个节点关于第k个高斯混合分布模型的后验概率公式为：S2.2.7. Using the Bayesian discriminant criterion based on the minimum error probability, the category to which each node belongs is obtained. According to the Bayesian formula, the posterior probability formula of the mth node with respect to the kth Gaussian mixture distribution model is:

其中，所述的基于最小错误概 率的贝叶斯判别准则如下：Wherein, the Bayesian discriminant criterion based on the minimum error probability is as follows:a)若p(μ₁，∑₁|x_m)＞p(μ₂，∑₂|x_m)，则判定节点x_m应选择第一种卸载方案；a) If p(μ₁ ,∑₁ |x_m )＞p(μ₂ ,∑₂ |x_m ), then node x_m should choose the first unloading scheme;b)若p(μ₁，∑₁|x_m)≤p(μ₂，∑₂|x_m)，则判定节点x_m应选择第二种卸载方案；b) If p(μ₁ ,∑₁ |x_m )≤p(μ₂ ,∑₂ |x_m ), then node x_m should choose the second unloading solution;其中，所述的步骤S3过程如下：The process of step S3 is as follows:对步骤S2中聚类得到的V2V用户建立一个集合，记作

记集合中共有

个元素；用户y的任务数据量用V_y表示，单位任务计算量用C_y表示，自身计算能力用f_y表示，对V2V用户自身的计算能力进行排序，用车辆节点计算自身任务所需要的时间

作为对车辆自身计算能力的衡量，选择t_y值最大的

个节点划入V2V请求节点集J，集合中余下的

个节点划入V2V服务节点集K；建立成一个带权二分图，

个V2V请求节点作为二分图的一个顶点集，

个V2V服务节点作为二分图的另一个顶点集，两个顶点集之间的边的权重代表V2V请求节点与服务节点之间建立连接所获得的收益，该边的权重与V2V请求节点的任务数据量V_j、V2V服务节点的计算能力f_k以及通信节点间的链路质量有关，链路质量考虑节点之间距离d_jk的影响，因此定义ξ_jk表示带权二分图中边的权重：A set of V2V users clustered in step S2 is established, denoted as

There are a total of

elements; the task data volume of user y is represented by V_y , the unit task calculation volume is represented by_Cy , and the computing power itself is represented by f_y . The computing power of V2V users is ranked, and the time required for calculating their own tasks is calculated by vehicle nodes.

As a measure of the vehicle's own computing power, select the vehicle with the largest t_y value.

nodes are included in the V2V request node set J, and the remaining

nodes are included in the V2V service node set K; a weighted bipartite graph is established.

V2V request nodes are regarded as a vertex set of a bipartite graph.

The V2V service nodes are used as another vertex set of the bipartite graph. The weight of the edge between the two vertex sets represents the benefit obtained by establishing a connection between the V2V request node and the service node. The weight of the edge is related to the task data volume_Vj of the V2V request node, the computing power_fk of the V2V service node, and the link quality between the communication nodes. The link quality considers the influence of the distance_djk between the nodes. Therefore,_ξjk is defined to represent the weight of the edge in the weighted bipartite graph:

利用Kuhn-Munkres算法求解带权二分图的最大匹配方案作为V2V通信车辆节点与服务节点的配对方案，记作μ＝{μ_jk}，j∈J，k∈K。The Kuhn-Munkres algorithm is used to solve the maximum matching scheme of the weighted bipartite graph as the pairing scheme of the V2V communication vehicle node and the service node, denoted as μ={μ_jk }, j∈J, k∈K.2.根据权利要求1所述的车联网中基于移动边缘计算的任务卸载与资源分配方法，其特征在于，所述的步骤S4中，定义V2I请求节点集合为I＝{1，...，i，..，I}，V2V请求用户集合为J＝{1，...，j，...，J}，V2V服务用户集合为K＝{1，...，k，...，K}，假设基站可以获得所有的信道状态信息，该步骤包括：2. The method for task offloading and resource allocation based on mobile edge computing in the Internet of Vehicles according to claim 1 is characterized in that, in the step S4, the V2I request node set is defined as I = {1, ..., i, .., I}, the V2V request user set is defined as J = {1, ..., j, ..., J}, and the V2V service user set is defined as K = {1, ..., k, ..., K}. Assuming that the base station can obtain all channel state information, the step includes:S4.1、计算V2I节点与基站通信的信干噪比

S4.1. Calculate the signal-to-interference-to-noise ratio of the communication between the V2I node and the base station

其中，β_ij∈{0，1}，β_ij＝1表示V2V请求节点j复用V2I节点i的上行信道，β_ij＝0表示V2V请求节点j没有复用V2I节点i的上行信道，每个V2V请求节点至多复用一个信道，即

p_i和p_j分别表示V2I请求节点i和V2V请求节点j的发送功率，满足车辆节点的功率峰值限制，即p_i，p_j＜p^max，

表示V2I请求节点i在子信道n上的信道增益，∑_j∈Jβ_ijp_j|h_j|²表示V2V通信用户对V2I用户i的干扰，其中|h_j|表示V2V用户j通信时在子信道上的信道增益，N₀W是加性高斯白噪声的功率，W是子信道的带宽；Wherein, β_ij ∈ {0, 1}, β_ij = 1 indicates that the V2V request node j reuses the uplink channel of the V2I node i, and β_ij = 0 indicates that the V2V request node j does not reuse the uplink channel of the V2I node i. Each V2V request node reuses at most one channel, that is,

p_i and p_j represent the transmission power of V2I request node i and V2V request node j respectively, satisfying the power peak limit of vehicle nodes, that is, p_i , p_j ＜p^max ,

represents the channel gain of V2I requesting node i on subchannel n, ∑_j∈J β_ij p_j |h_j |² represents the interference of V2V communication user to V2I user i, where |h_j | represents the channel gain of V2V user j on the subchannel when communicating, N₀ W is the power of additive white Gaussian noise, and W is the bandwidth of the subchannel;S4.2、计算V2V请求用户j与服务用户K通信时的信干噪比

S4.2. Calculate the signal-to-interference-noise ratio when the V2V requesting user j communicates with the serving user K

其中，

表示V2V通信时，V2I用户对V2V接收端用户的干扰，∑_{j，∈J，j′≠j}β_ij′p_j′|h_j′|²表示V2V通信时，其他V2V用户对V2V接收端用户的干扰；in,

represents the interference of V2I users to V2V receiving users during V2V communication, ∑_{j,∈J,j′≠j} β_ij′ p_j′ |h_j′ |² represents the interference of other V2V users to V2V receiving users during V2V communication;S4.3、计算整个车联网系统任务处理的总延迟D_total，由V2I用户的卸载延迟和V2V用户的处理延迟组成，计算公式如下：S4.3. Calculate the total delay D_total of the entire vehicle networking system task processing, which is composed of the unloading delay of the V2I user and the processing delay of the V2V user. The calculation formula is as follows:

上式中，

表示所有V2I用户的任务处理总延迟，包括传输延迟和计算延迟，其中V_i表示V2I用户i的任务数据量，C_i表示计算1bit数据所需要的CPU周期数，f_i^e表示边缘服务器分配给每个V2I用户的计算资源；

表示所有V2V配对用户的任务处理总延迟，包括V2V请求用户的传输延迟以及V2V服务用户对自身任务和请求任务进行计算的延迟；

表示未能成功配对的V2V用户进行本地任务计算的延迟，其中，V_j表示V2V请求用户j的任务数据量，C_j、C_k分别表示计算1bit来自V2V请求用户和服务用户的任务所需要的CPU周期数，f_j、f_k分别表示V2V请求用户和服务用户的计算能力，μ_jk表示V2V配对策略。In the above formula,

represents the total task processing delay of all V2I users, including transmission delay and calculation delay, where_Vi represents the task data volume of V2I user i,_Ci represents the number of CPU cycles required to calculate 1 bit of data,^and_fie represents the computing resources allocated to each V2I user by the edge server;

It represents the total task processing delay of all V2V paired users, including the transmission delay of the V2V requesting user and the delay of the V2V service user to calculate its own task and the requested task;

represents the delay of the V2V user who failed to pair successfully to perform local task calculation, where_Vj represents the task data volume of V2V requesting user j,_Cj and_Ck represent the number of CPU cycles required to calculate 1 bit of task from V2V requesting user and serving user respectively,_fj and_fk represent the computing power of V2V requesting user and serving user respectively, and_μjk represents the V2V pairing strategy.3.根据权利要求1所述的车联网中基于移动边缘计算的任务卸载与资源分配方法，其特征在于，所述的步骤S5中，以最小化车联网系统任务处理的总延迟D_total为目标，建立最优化问题模型如下：3. The method for task offloading and resource allocation based on mobile edge computing in the Internet of Vehicles according to claim 1 is characterized in that, in the step S5, the optimization problem model is established with the goal of minimizing the total delay D_{total of} task processing in the Internet of Vehicles system as follows:

C1：

C1:

C2：

C2:

C3：

C3:

C4：

C4:

C5：

C5:

C6：

C6:

上述约束条件中，C1表示β_ij，μ_jk的取值只能为0或1，

指示子信道的复用情况，μ_jk表示V2V请求节点与服务节点的配对情况，C2表示每个V2V请求节点至多复用一个信道，C3表示每个V2I节点和V2V配对用户发送节点的功率限制，C4表示边缘服务器分配给所有V2I车辆的计算资源总和应小于边缘服务器的总计算资源，C5表示每个V2I节点与基站进行通信的信干噪比应大于门限值

C6表示每个V2V用户进行通信的信干噪比应大于门限值

In the above constraints, C1 represents β_ij , and the value of μ_jk can only be 0 or 1.

Indicates the multiplexing of sub-channels, μ_jk indicates the pairing of V2V request nodes and service nodes, C2 indicates that each V2V request node can reuse at most one channel, C3 indicates the power limit of each V2I node and V2V paired user sending node, C4 indicates that the sum of computing resources allocated by the edge server to all V2I vehicles should be less than the total computing resources of the edge server, and C5 indicates that the signal-to-noise ratio of each V2I node communicating with the base station should be greater than the threshold value.

C6 indicates that the signal-to-interference-to-noise ratio of each V2V user's communication should be greater than the threshold value

Images