CN112749010A - Edge calculation task allocation method for fusion recommendation system - Google Patents

Abstract

The present invention provides an edge computing task allocation method for a fusion recommendation system, comprising: step 1, establishing a connection between a cloud module, an edge server module and a mobile terminal to construct a cloud-edge-terminal fusion recommendation system; step 2, a task sender Send a task request to the cloud-edge-terminal fusion recommendation system; step 3, the cloud-edge-terminal fusion recommendation system receives the task request sent by the task sender, and the edge server module performs the tasks according to the needs of the multiple devices deployed on the roadside facilities. The location information and computing capacity of the edge server that starts the task are used to construct an edge server database. The invention combines the cached edge server and the recommended edge server to design, the recommendation hit rate is high, and it is proved that the recommended hit rate problem is a monotone submodular function and NP-hard problem, which improves the utilization rate of computer resources and reduces the time. consume.

Description

Edge computing task assignment method for fusion recommender system

technical field

The invention relates to the technical field of computer task assignment, in particular to an edge computing task assignment method of a fusion recommendation system.

Background technique

According to a Cisco report, mobile data traffic will grow sevenfold over the next 5 years, reaching 49 exabytes (EB) (1EB-106TB) per month by 2021, while the global number of IoT devices will increase from the current 8 billion to 12 billion. This will make it difficult for it to access the network to obtain the computing resources of the mobile edge server.

In addition, in the 5G network era, large-scale task processing requirements have also begun to appear, such as multimedia special effects tasks and big data processing tasks. In these task scenarios, the most common user requirement is the real-time requirement, that is, the task is required to be quickly responded to, executed quickly, and the execution result can be quickly returned to the user. In order to cope with the rapid development of the mobile Internet and the Internet of Things, 5G needs to meet the new business requirements of ultra-low latency, ultra-low power consumption, ultra-high reliability, and ultra-high-density connections. Therefore, minimizing task completion time is the most common goal in task offloading problems.

The current unloading problems in mobile edge computing mainly include: page unloading, that is, edge caching. The page provider caches frequently used pages on the edge cloud to reduce the delay and energy consumption when users request pages. There have been cache strategies considering page distribution and user mobility in related research. Task offloading, the problem of deciding when, where, and how many tasks should be offloaded from mobile devices to the edge to reduce computational latency and save energy. This kind of research mainly focuses on the problem of uninstall decision in multi-user environment and multi-server environment. Page unloading mainly concerns the storage capacity of the edge cloud, and does not consider the computing power synchronously. In the related research on task offloading, the normal assumption is that the edge cloud has sufficient hardware and software resources to support task computing, which is contrary to the limited resources of the edge cloud and the inability to support all types of tasks.

For the task offloading problem of MEC, many scholars have done related research. Considering the capacity constraints of fronthaul and backhaul links and the maximum delay constraints of users, an effective offloading scheme is proposed by minimizing the total energy consumption of the network. Under the trade-off between energy consumption and delay, an energy-aware computing offloading scheme is proposed, and the remaining energy of the smart device battery is introduced into the definition of the weighting factor of energy consumption and delay, which effectively reduces the total consumption of the system. Considering the trade-off between the latency and reliability of task offloading, the task of user equipment is divided into subtasks and offloaded to nearby edge nodes in turn. However, the above literatures do not reasonably allocate the limited wireless and computing resources. Under the multi-user MEC system, an online task offloading algorithm is proposed to minimize the average energy consumption of users and MEC servers. Considering the minimization of the total energy consumption of the system, the joint optimization problem of offloading decision, radio resource and computing resource allocation is studied. Nevertheless, the existing task scheduling algorithms only perform task offloading and allocation by optimizing energy consumption and delay, but never select edge servers to process tasks from the task itself.

SUMMARY OF THE INVENTION

The present invention provides an edge computing task assignment method for a fusion recommendation system, the purpose of which is to solve the problem that the traditional task assignment method does not select an edge server to process the task from the task itself.

In order to achieve the above object, an embodiment of the present invention provides an edge computing task allocation method for a fusion recommendation system, including:

Step 1: Connect the cloud module, the edge server module and the mobile terminal to each other to construct a cloud-edge-terminal fusion recommendation system;

Step 2, the task sender sends a task request to the cloud-edge-device fusion recommendation system;

Step 3: The cloud-edge-device fusion recommendation system receives the task request sent by the task sender, and the edge server module constructs the location information and computing power of a plurality of edge servers deployed on the roadside facilities that start executing tasks according to requirements. Edge server database;

Step 4, the cloud-edge-device fusion recommendation system selects the edge server information that can process the current task from the edge server database;

Step 5, filter the screened edge server information through a filtering algorithm according to the location information of the current task sender;

Step 6: Clustering the filtered edge server information according to the computing capability of the edge server, obtaining the location information and computing capability information of the edge server capable of executing the task request, and starting the edge server capable of executing the task request;

Step 7: According to the edge server table established in the edge server module according to the location information and computing capability information of the edge server that can complete the task execution, the edge server module recommends the edge server table to the cloud module;

Step 8, the cloud-edge-device fusion recommendation system combines the edge server table recommended by the edge server module to the cloud module with the edge server cached in the cloud module but not participating in the task execution of the previous stage;

Step 9, the cloud-edge-device fusion recommendation system selects both the edge server recommended to the cloud module for the edge server module and the edge server cached by the cloud module, and constructs a final recommended edge server information table according to the selected edge servers;

Step 10: The cloud-edge-device fusion recommendation system analyzes the task characteristics of the task request, selects the edge server that can execute the current task request in the final recommended edge server information table, and recommends it to the task sender, as the task sender. When receiving the edge server recommended by the cloud-edge-device fusion recommendation system, the edge server executes the current task request of the task sender;

Step 11: Optimize the recommendation hit rate of the cloud-edge-terminal fusion recommendation system to the task sender by designing a recommendation optimization algorithm, and obtain the optimal recommendation hit rate.

Wherein, the step 3 specifically includes:

Step 31, extracting and summarizing the deployment positions of each edge server, and screening the deployment position information of the edge servers;

Step 32, summarizing the deployment area of the edge server, and determining the deployment location of the edge server;

Step 33, extracting the position of the task sender, screening the edge server deployment positions within the communication range of the task sender, and obtaining a set of edge server deployment positions within the communication range of the task sender;

Step 34, analyze the computing capability of each edge server according to the set of edge server deployment locations;

Step 35, sorting and summarizing the location information of each edge server within the communication range of the task sender, determining the deployment location of each edge server, and establishing a deployment location database of the edge server;

Step 36: Summarize the computing capabilities of each edge server within the communication range of the task sender, and establish a database of edge servers participating in task processing.

Wherein, the step 5 specifically includes:

Step 51 , according to the location information of the current task sender transmitted from the edge server module, filter the edge server information within a certain communication range of the current task sender through a filtering algorithm.

Wherein, the step 6 specifically includes:

Step 61, separating the edge server information that needs to be recommended from the edge server information after the secondary filtering;

Step 62 , when the information of the separated edge servers is too much, the edge servers with sufficient computing capabilities are clustered to obtain the location information of the edge servers with sufficient computing capabilities and start.

Wherein, the step 7 specifically includes:

Step 71, establishing an edge server table according to the obtained location information of the edge server of the edge server with sufficient computing capability;

Step 72, the edge server module recommends the edge server table to the cloud module.

Wherein, the step 8 specifically includes:

Step 81, the cloud-edge-device fusion recommendation system records the edge server table of the cloud module recommended by the edge server module;

Step 82, combine the edge server recommended by the edge server module with the edge server cached by the cloud module.

Wherein, the step 9 and the step 10 specifically include:

Filter out the edge servers that are cached in the cloud module and recommended for the edge server module to construct the final recommended edge server information table. The cloud-edge-device fusion recommendation system uses breadth-first search to select the final recommended edge server information table that can process the current task request. The edge servers of m are added to the end of the edge server table, and the cloud-edge-device fusion recommendation system recommends m edge servers that can complete the current task request to the task sender.

Wherein, the step 11 specifically includes:

Since the task sender is in a mobile state and the edge server is in a flexible state, the tasks that need to be processed between the task sender and the edge server change with time, and the edge server selected to process the task request is in the task sending state in the current network state. within the communication range of:

q _ij =prob{ED j in the range of TS i}∈{0,1} (1)

Among them, q _ij represents the communication range of the task sender, i represents the task sender, j represents the edge server, and TS represents the task sender.

Wherein, the step 11 further includes:

When the task request of the task sender is recommended to hit, express the recommended hit rate of the task request as a function of an integer variable, as follows:

表示任务发送者i发送的任务请求，当任务k不合理时，任务发送者发送任务请求n的概率，满足

M表示边缘服务器数，K表示任务数，x_nj表示在任务发送者通信范围内被用于处理任务n的边缘服务器数目。Among them, n represents the task request, n∈K,

Represents the task request sent by the task sender i. When the task k is unreasonable, the probability of the task sender sending the task request n is satisfied.

M represents the number of edge servers, K represents the number of tasks, and x _nj represents the number of edge servers used to process task n within the communication range of the task sender.

Wherein, the step 11 further includes:

The problem of optimizing the recommendation strategy is formulated as:

Among them, N represents the task sender, p _ik represents the probability that the task sender i requests to process the task k, x _nj represents the number of edge servers used to process the task n within the communication range of the task sender, and C represents the required amount of processing tasks. Maximum number of edge servers.

The above-mentioned scheme of the present invention has the following beneficial effects:

The edge computing task allocation method of the fusion recommendation system according to the above-mentioned embodiment of the present invention adopts the cloud-edge-terminal fusion recommendation system to analyze the task characteristics of the task request of the task sender and select an appropriate edge server, and then assign the task to the task request. It is allocated to the appropriate edge server for execution; the cached edge server is combined with the recommended edge server, and the recommendation hit rate is high, and it is proved that the recommendation hit rate problem is an NP-hard problem of a monotonic submodular function, which improves the utilization of computer resources. rate, reducing time consumption.

Description of drawings

Fig. 1 is the flow chart of the present invention;

Fig. 2 is the structural representation of the present invention;

FIG. 3 is a schematic diagram of a recommendation flow of the present invention;

4 is a schematic diagram of the recommendation rate of the present invention under different BFS parameters;

FIG. 5 is a schematic diagram of the recommendation rate of the present invention in different recommendation modes after optimization;

6 is a schematic diagram of the time consumption of the present invention under different vehicles;

FIG. 7 is a schematic diagram of the time consumption of the present invention under different task sizes.

Detailed ways

In order to make the technical problems, technical solutions and advantages to be solved by the present invention more clear, the following will be described in detail with reference to the accompanying drawings and specific embodiments.

Aiming at the problem that the existing task assignment method does not select the edge server to process the task from the task itself, the present invention provides an edge computing task assignment method integrating a recommendation system.

As shown in FIG. 1 to FIG. 7 , an embodiment of the present invention provides an edge computing task allocation method for a fusion recommendation system, including: Step 1: Connect the cloud module, the edge server module and the mobile terminal to each other to construct a cloud-edge - Terminal fusion recommendation system; Step 2, the task sender sends a task request to the cloud-edge-terminal fusion recommendation system; Step 3, the cloud-edge-terminal fusion recommendation system receives the task request sent by the task sender, and the edge server module according to the The location information and computing capabilities of multiple edge servers deployed on roadside facilities that start executing tasks according to requirements build an edge server database. The edge server information of the task; step 5, filter the filtered edge server information through a filtering algorithm according to the location information of the current task sender; step 6, cluster the filtered edge server information according to the computing capability of the edge server, Obtain the location information and computing capability information of the edge server that can execute the task request, and start the edge server that can execute the task request; Step 7, according to the location information and computing capability information of the edge server that can complete the task execution, build the edge server module on the edge server module. In the server table, the edge server module recommends the edge server table to the cloud module; step 8, the cloud-edge-device fusion recommendation system recommends the edge server module to the edge server table of the cloud module and caches it in the cloud module but did not participate in the previous stage task The executed edge server combination; step 9, the cloud-edge-device fusion recommendation system will screen out both the edge server recommended for the edge server module to the cloud module and the edge server cached by the cloud module, and build the final recommendation according to the edge server selected Edge server information table; Step 10, the cloud-edge-device fusion recommendation system analyzes the task characteristics of the task request, selects the edge server that can execute the current task request in the final recommended edge server information table, and recommends it to the task sender , when the task sender receives the edge server recommended by the cloud-edge-device fusion recommendation system, the edge server executes the task sender's current task request; step 11, by designing a recommendation optimization algorithm, the cloud-edge-device fusion recommendation system is recommended to The recommended hit rate of the task sender is optimized to obtain the optimal recommended hit rate.

In the edge computing task allocation method of the fusion recommendation system described in the above-mentioned embodiment of the present invention, it is assumed that the edge server information record is regarded as a series of data points, then each edge server ID-computing capability-location data point is: S =(id,computing power,position); all edge server information can be recorded as: Q=(S ₁ , S ₂ ,...,S _n ); since in practice, the deployment position of edge servers is fixed and only when needed It is necessary to roughly delineate the edge servers within a certain communication range of the task sender based on the location of the task sender, and filter out the location information of the edge servers. Obtaining edge server location information within a specified range is divided into: extracting edge server deployment locations, summarizing edge server deployment areas, and analyzing edge server computing capabilities. 1. Extracting the deployment location of the edge server includes extracting and summarizing the deployment location of each edge server, and filtering the deployment location information of the edge server. 2. Summarizing edge server deployment areas includes determining, filtering, and merging edge server deployment locations, and summarizing edge server deployment areas. 3. Analysis of edge server computing capabilities includes sorting edge server deployment areas, screening edge server deployment areas, and analyzing edge server computing capabilities. Each deployment location indicates that the edge server has a specific behavior at a certain location. By extracting and summarizing the deployment locations, the set of edge server deployment locations within the communication range of the task sender is obtained, and then the computing capability of each edge server is analyzed. Establish an edge server location database, and then summarize the edge server computing capabilities in the fixed location area to establish an edge server database.

Wherein, the step 3 specifically includes: step 31, extracting and summarizing the deployment positions of each edge server, and screening the deployment position information of the edge server; step 32, summarizing the deployment area of the edge server, and determining the deployment position of the edge server; step 33, extracting the task Sender location, filter the edge server deployment locations that meet the communication range of the task sender, and obtain a set of edge server deployment locations within the communication range of the task sender; Step 34: According to the edge server deployment location set, the computing capability of each edge server Analyze; Step 35, sort and summarize the position information of each edge server within the communication range of the task sender, determine the deployment position of each edge server, and establish a deployment position database of the edge server; Step 36, communicate with the task sender The computing power of each edge server within the scope is summarized, and a database of edge servers participating in task processing is established.

The step 5 specifically includes: step 51, filtering edge server information within a certain communication range of the current task sender through a filtering algorithm according to the location information of the current task sender transmitted by the edge server module.

The step 6 specifically includes: step 61, separating the edge server information that needs to be recommended from the edge server information after the secondary filtering; step 62, when the separated edge server information is too much, separate the edge server information with sufficient computing power The servers are clustered to obtain the location information of edge servers with sufficient computing power and start them.

The step 7 specifically includes: step 71, establishing an edge server table according to the obtained location information of the edge server of the edge server with sufficient computing capability; step 72, the edge server module recommending the edge server table to the cloud module.

The step 8 specifically includes: step 81, the cloud-edge-device fusion recommendation system records the edge server table of the cloud module recommended by the edge server module; step 82, the edge server recommended by the edge server module and the cloud module cached Edge server integration.

Wherein, the steps 9 and 10 specifically include: screening out the edge servers that are both cached in the cloud module and recommended for the edge server module to construct a final recommended edge server information table, and the cloud-edge-terminal fusion recommendation system uses breadth priority The search adds the edge servers that can process the current task request in the final recommended edge server information table to the end of the edge server table, and the cloud-edge-device fusion recommendation system recommends m edge servers that can complete the current task request to the task sender.

In the edge computing task allocation method of the fusion recommendation system according to the above-mentioned embodiment of the present invention, the edge server information table includes the recommended edge server information and the edge server information that has been cached in the cloud, and the cloud-edge-terminal fusion recommendation system is based on the task request. Select the appropriate edge server from the edge server information table and recommend it to the task sender.

The step 11 specifically includes: since the task sender is in a mobile state and the edge server is in a flexible state, the tasks to be processed between the task sender and the edge server change with time, and the edge server is selected as the edge for processing task requests. The server is within the communication range of the task sender in the current network state:

q _ij =prob{ED j in the range of TS i}∈{0,1} (1)

Among them, q _ij represents the communication range of the task sender, i represents the task sender, j represents the edge server, and TS represents the task sender.

Wherein, the step 11 further includes: when the task request of the task sender is recommended to hit, expressing the recommended hit rate of the task request as a function of an integer variable, as shown below:

表示任务发送者i发送的任务请求，当任务k不合理时，任务发送者发送任务请求n的概率，满足

M表示边缘服务器数，K表示任务数，x_nj表示在任务发送者通信范围内被用于处理任务n的边缘服务器数目。Among them, n represents the task request, n∈K,

Represents the task request sent by the task sender i. When the task k is unreasonable, the probability of the task sender sending the task request n is satisfied.

M represents the number of edge servers, K represents the number of tasks, and x _nj represents the number of edge servers used to process task n within the communication range of the task sender.

Wherein, the step 11 further includes: expressing the problem of optimizing the recommendation strategy as:

Among them, N represents the task sender, p _ik represents the probability that the task sender i requests to process the task k, x _nj represents the number of edge servers used to process the task n within the communication range of the task sender, and C represents the required amount of processing tasks. Maximum number of edge servers.

In the edge computing task allocation method for the fusion recommendation system described in the above-mentioned embodiments of the present invention, the task sender sends a task request to the cloud-edge-terminal fusion recommendation system, and searches for information on edge servers that can complete the task in the following BFS manner. , request edge server information related to the task content from the cloud-edge-device fusion recommendation system, and add the requested edge server information to the list M in the order returned by the cloud-edge-device fusion recommendation system. For the edge server information in the list M, further recommend the edge server information related to it and capable of task processing, and add them to the end of the list M. Add other related edge server information by analogy until the retrieval depth is reached, search the list M for edge server information that is also included in the cloud cache through the TORS algorithm, and add it to the output list G until the list M is browsed and the output list G contains N edge server information, whichever comes first (line 5-10). After the above steps are performed, the number of edge servers in the output list G is less than N, then the N-|G| edge server information is added to the output list G (line 11-16).

The edge computing task allocation method of the fusion recommendation system described in the above-mentioned embodiment of the present invention, the optimization problem of formula (3) is proved as follows:

表示和当前处理任务k相关的边缘服务器集合，如下所示：The objective function of the optimization problem is an NP-hard problem, using

Represents the set of edge servers related to the current processing task k, as follows:

Among them, t represents an edge server different from edge server j for processing the current task k, and M represents the number of edge servers;

假设只有边缘服务器j被推荐处理任务(x_j＝1and

)，因此推荐率将会等于

(

是边缘服务器t处理任务i的概率)。当不只有边缘服务器j被推荐处理任务，用S'表示所有被当前任务所覆盖的边缘服务器并集

因此推荐率等于

因此目标函数相当于：The subset of edge servers is represented as

Suppose that only edge server j is recommended to process the task (x _j = 1 and

), so the referral rate will be equal to

(

is the probability that edge server t processes task i). When more than one edge server j is recommended to process the task, let S' denote the union of all edge servers covered by the current task

So the recommendation rate is equal to

So the objective function is equivalent to:

表示边缘服务器t处理任务i的概率，q_it表示边缘服务器t在任务i的发送者通信范围。in,

represents the probability that edge server t processes task i, and q _it represents the communication range of edge server t in the sender of task i.

The above is equivalent to the maximum coverage problem of weighted elements, where elements correspond to edge servers, weights correspond to probability values, and the number of selected subsets must be less than the maximum number of edge servers required to process the task, and the union of covered elements is S '. This is a known NP-hard problem. Therefore, the problem of having many recommended edge servers within the scope covered by each task is also an NP-hard problem.

等同于集合函数

其中K×M是边缘服务器推荐集合(k,j)，k表示任务，j表示边缘服务器，S＝{k∈K,i∈M:x_kj＝1}，如下所示：The objective function is a monotonic submodular function and is constrained by the cardinality: objective function

Equivalent to aggregate function

where K×M is the recommended set of edge servers (k, j), k represents the task, j represents the edge server, and S={k∈K,i∈M:x _kj =1}, as follows:

表示任务发送者i发送的任务请求，当任务k不合理时，任务发送者发送任务请求n的概率，满足

q_ij表示任务发送者的通信范围，i表示任务发送者，j表示边缘服务器。where p _ik represents the probability that task sender i requests to process task k,

Represents the task request sent by the task sender i. When the task k is unreasonable, the probability of the task sender sending the task request n is satisfied.

q _ij represents the communication range of the task sender, i represents the task sender, and j represents the edge server.

和ε∈V\B认为：An aggregate function is characterized as a submodular aggregate function if and only if for each

and ε∈V\B that:

[f(A∪{ε})-f(A)]-[f(E∪{ε})-f(E)]≥0 (7)

ε表示属于V不属于E的元素；Among them, A and E represent sets, satisfying for all A and E sets

ε represents an element that belongs to V but not to E;

首先计算：According to the formula

First calculate:

表示任务发送者i发送的任务请求，当任务k不合理时，任务发送者发送任务请求n的概率，满足

q_ij和q_im表示任务发送者的通信范围，i表示任务发送者，j，m表示边缘服务器。Among them, l, ε represent elements that do not belong to A, p _ik represents the probability that task sender i requests to process task k,

Represents the task request sent by the task sender i. When the task k is unreasonable, the probability of the task sender sending the task request n is satisfied.

q _ij and q _im represent the communication range of the task sender, i represents the task sender, and j and m represent the edge server.

The value of formula (9) is always greater than 0, which proves the sub-modularity;

Since equation (10) is always in a non-negative state, the monotonicity is proved;

To prove that the constraint is a matrod, consider the set ν = K × M (i.e., all possible tuples {tasks, edge servers}) and the set of subsets thereof do not violate the maximum number of edge servers required to process a task, as follows shown:

Among them, S represents the subset of edge servers, ^2ν represents the power set of the set v, C represents the maximum number of edge servers required to process the task, and M represents the number of edge servers.

其认为，如果

集合E推荐的边缘服务器个数不会超过任务处理所需的最大边缘服务器数目，然后，对于

因为在集合A中每个边缘服务器都必须与集合E中边缘服务器相同或者少于集合E，因此不违反边缘服务器数目问题。其次，对于所有集合A,E∈Γ，满足推荐条件的边缘服务器，|E|>|A|，在集合E中，更多边缘服务器被推荐，在集合A中，边缘服务器数目未达最大值，否则集合E将违反边缘服务器数目约束，即

这意味着集合A可以继续推荐至少一个以上的边缘服务器，并且可以从集合E中选择该边缘服务器；First, for all sets A and E,

It believes that if

The number of edge servers recommended by set E will not exceed the maximum number of edge servers required for task processing. Then, for

Since each edge server in set A must be the same as or less than the edge server in set E, the edge server number problem is not violated. Secondly, for all sets A, E∈Γ, edge servers that satisfy the recommendation condition, |E|>|A|, in set E, more edge servers are recommended, in set A, the number of edge servers does not reach the maximum value , otherwise set E will violate the constraint on the number of edge servers, i.e.

This means that set A can continue to recommend at least one more edge server, and this edge server can be selected from set E;

For any monotone submodular function f, it is considered that:

F(x)≥(1-1/e)f*(x) (12)

Among them, f ^* (x) represents the optimal value of the monotone submodular function.

To maximize monotone submodular functions constrained by matroids, Khuller S proposed a stochastic algorithm that gives (1-1/e) approximation, which is divided into two parts. In the first part, the combinatorial problem is replaced by a continuous problem, and approximate solutions to the continuous problem are found. In the second part, fractional solutions to continuous problems are rounded using a technique called Pipage rounding. Although this algorithm provides better performance guarantees, when the size of the recommended set of edge servers in the problem is equal to K × M, it is too computationally expensive to implement. Of course, minimizing algorithmic complexity or best approximation algorithms is beyond the scope of what needs to be dealt with. Greedy, a fast and effective greedy algorithm, is used to process large tasks efficiently in cloud-edge collaboration scenarios.

In the edge computing task allocation method of the fusion recommendation system described in the above-mentioned embodiment of the present invention, Fig. 4 shows the recommendation rate of recommendation+cache through two cases of direct recommendation and recommendation+cache, with the increase of parameters B and D higher than the direct recommendation. Figure 5 shows the recommendation rate of the TORS algorithm, the recommendation rate performance of the greedy algorithm Greedy and the Top recommendation algorithm under different BFS parameters. For the same situation, the greedy algorithm Greedy always outperforms the TORS algorithm, and the recommendation rate performance of the Top recommendation algorithm is 2 times higher than that of the greedy algorithm Greedy. Figure 5 clearly shows the benefits of combining recommendation and caching.

In the edge computing task allocation method for the fusion recommendation system described in the above-mentioned embodiments of the present invention, the total time cost of the system when the number of edge nodes increases is shown in FIG. 6 and FIG. 7 . In general, the total cost of the three methods decreases as the number of edge nodes increases. In Figure 6, the top recommendation algorithm is the best, the greedy algorithm Greedy has a small difference, and both the TORS algorithm and the greedy algorithm Greedy are relatively stable. At the same time, the optimal recommendation curve of the Top recommendation algorithm is higher than that of the Greedy algorithm, and it is greedy for unilateral nodes. But when there are more edge nodes, the faster it declines. This is because the execution time decreases as the number of edge nodes increases. Figure 7 shows the impact of the offload task data size on the total cost of the system, where the number of edge nodes is set to 4, as the offload task data size increases, the total cost of the three methods also increases. This is because the larger the amount of data, the greater the time and energy consumption for offloading. Compared with other methods, the TORS algorithm has a slower growth trend and better effect. As the amount of data increases, the top recommendation algorithm curve grows much faster than the TORS algorithm and the greedy algorithm Greedy, indicating that the larger the amount of data required for offloading, the greater the delay and energy consumption of offloading computation.

The edge computing task allocation method of the fusion recommendation system according to the above-mentioned embodiment of the present invention adopts the cloud-edge-terminal fusion recommendation system to analyze the task characteristics of the task request of the task sender and select an appropriate edge server, and then assign the task to the task request. Assign to the appropriate edge server for execution. The cloud-edge-device fusion recommendation system mainly includes three modules: cloud module, edge server module and mobile terminal (task sender). The edge server module mainly recommends edge servers that are in a flexible state (non-cached), and recommends edge servers that meet this condition to the cloud module according to whether the edge server communicates with the task sender and has sufficient computing power. The cloud module combines the edge server information obtained from the edge server module with the edge server cached in the cloud, and recommends it to the task sender. The cloud-edge-device fusion recommendation system is designed by combining the cached edge server with the recommended edge server, and has a high recommendation hit rate, and it is proved that the recommendation hit rate problem is a monotone submodular function and NP-hard problem , improve the computer resource utilization rate of the whole system and reduce the time consumption.

The above are the preferred embodiments of the present invention. It should be pointed out that for those skilled in the art, without departing from the principles of the present invention, several improvements and modifications can be made. It should be regarded as the protection scope of the present invention.

Claims (10)

1. An edge computing task allocation method for a fusion recommendation system is characterized by comprising the following steps:

step 1, a cloud module, an edge server module and a mobile terminal are mutually connected to construct a cloud-edge-terminal fusion recommendation system;

step 2, a task sender sends a task request to a cloud-edge-end fusion recommendation system;

step 3, the cloud-edge-end fusion recommendation system receives a task request sent by a task sender, and an edge server module builds an edge server database according to the position information and the computing capacity of a plurality of edge servers which are deployed on road side facilities and start to execute tasks according to requirements;

step 4, screening edge server information capable of processing the current task from an edge server database by the cloud-edge-end fusion recommendation system;

step 5, filtering the screened edge server information through a filtering algorithm according to the position information of the current task sender;

step 6, clustering the filtered edge server information according to the computing capability of the edge server to obtain the position information and the computing capability information of the edge server capable of executing the task request and starting the edge server capable of executing the task request;

step 7, recommending the edge server table to the cloud module by the edge server module according to the edge server table established in the edge server module according to the position information and the computing capacity information of the edge server capable of completing task execution;

step 8, the cloud-edge-end fusion recommendation system recommends the edge server module to the edge server table of the cloud end module and combines the edge server which is cached in the cloud end module but does not participate in the task execution of the previous stage;

step 9, screening the edge servers which are recommended to the cloud end module for the edge server module and cached in the cloud end module by the cloud-edge-end fusion recommendation system, and constructing a final recommendation edge server information table according to the screened edge servers;

step 10, the cloud-edge-end fusion recommendation system analyzes task characteristics of the task request, selects an edge server capable of executing the current task request in the final recommendation edge server information table, and recommends the edge server to a task sender, and when the task sender receives the edge server recommended by the cloud-edge-end fusion recommendation system, the edge server executes the current task request of the task sender;

and 11, optimizing the recommendation hit rate of the cloud-edge-end fusion recommendation system to the task sender by designing a recommendation optimization algorithm to obtain the optimal recommendation hit rate.

2. The method for distributing the edge calculation tasks of the fusion recommendation system according to claim 1, wherein the step 3 specifically comprises:

step 31, extracting and summarizing the deployment position of each edge server, and screening the deployment position information of the edge server;

step 32, summarizing an edge server deployment area, and determining an edge server deployment position;

step 33, extracting the position of the task sender, and screening edge server deployment positions meeting the requirement in the communication range of the task sender to obtain an edge server deployment position set in the communication range of the task sender;

step 34, analyzing the computing power of each edge server according to the edge server deployment position set;

step 35, sequencing and summarizing the position information of each edge server in the communication range of the task sender, determining the deployment position of each edge server, and establishing a deployment position database of the edge servers;

and step 36, summarizing the computing power of each edge server in the communication range of the task sender, and establishing an edge server database participating in task processing.

3. The method for distributing the edge calculation tasks of the fusion recommendation system according to claim 1, wherein the step 5 specifically comprises:

and step 51, filtering the edge server information within a certain communication range of the current task sender through a filtering algorithm according to the position information of the current task sender transmitted by the edge server module.

4. The method for distributing the edge calculation tasks of the fusion recommendation system according to claim 1, wherein the step 6 specifically comprises:

step 61, separating the edge server information needing to be recommended from the edge server information after secondary filtering;

and step 62, clustering the edge servers with sufficient computing power when the separated edge servers have excessive information, obtaining the position information of the edge servers with sufficient computing power, and starting.

5. The method for distributing the edge calculation tasks of the fusion recommendation system according to claim 1, wherein the step 7 specifically comprises:

step 71, establishing an edge server table according to the obtained position information of the edge server with sufficient computing capacity;

step 72, the edge server module recommends the edge server table to the cloud module.

6. The method for distributing the edge calculation tasks of the fusion recommendation system according to claim 1, wherein the step 8 specifically comprises:

step 81, recording an edge server table of an edge server module recommendation cloud end module by the cloud-edge-end fusion recommendation system;

and step 82, combining the edge server recommended by the edge server module with the edge server cached by the cloud end module.

7. The method for distributing the edge calculation tasks of the fusion recommendation system according to claim 1, wherein the steps 9 and 10 specifically include:

the method comprises the steps that edge servers which are cached in a cloud module and recommended for an edge server module are screened out to construct a final recommended edge server information table, a cloud-edge-end fusion recommendation system adds edge servers which can process current task requests in the final recommended edge server information table to the tail of the edge server table by means of breadth-first search, and the cloud-edge-end fusion recommendation system recommends m edge servers which can complete current task requests to a task sender.

8. The method for distributing the edge calculation tasks of the fusion recommendation system according to claim 1, wherein the step 11 specifically comprises:

because the task sender is in a mobile state, the edge server is in a flexible state, tasks needing to be processed between the task sender and the edge server change along with time, and the edge server selected as the edge server for processing the task request is in the communication range of the task sender under the current network state:

q_ij＝prob{ED j in the range of TSi}∈{0,1} (1)

wherein q is_ijIndicating the communication range of the task sender, i indicating the task sender, j indicating the edgeEdge server, TS, represents task sender.

9. The method for distributing the edge computing task of the fusion recommendation system according to claim 8, wherein the step 11 further comprises:

when the task request recommendation of the task sender is hit, the recommendation hit rate of the task request is expressed as a function of an integer variable, as follows:

where n represents a task request, n is equal to K,

the probability that the task sender sends the task request n is satisfied when the task k is unreasonable and the task sender i sends the task request n

M denotes the number of edge servers, K denotes the number of tasks, x_njIndicating the number of edge servers used to process task n within the communication range of the task sender.

10. The method for distributing the edge computing task of the fusion recommendation system according to claim 9, wherein the step 11 further comprises:

the problem of optimizing the recommendation strategy is represented as:

where N denotes the task sender, p_ikRepresenting the probability, x, that a task sender i requests to process a task k_njIndicating the number of edge servers used to process task n within the communication range of the task sender, C indicating the maximum number of edge servers required to process the taskTo achieve the purpose.

Images