Search

CN-115529633-B - Service migration and task rerouting balance and resource management online optimization method oriented to mobile edge computing

CN115529633BCN 115529633 BCN115529633 BCN 115529633BCN-115529633-B

Abstract

The invention discloses a service migration and task rerouting balance and resource management online optimization method for mobile edge computing, which realizes balance between service migration and task rerouting when edge server access switching occurs to mobile equipment and provides seamless, economical and efficient computing service. In consideration of network dynamics and possible asynchronism of management decisions, including random task generation and time-varying channel conditions, the invention constructs a double-time-scale online optimization problem to jointly determine a large-time-scale decision and a small-time-scale decision, and then based on an improved Lyapunov algorithm, the long-term average service delay of the system is asymptotically optimal by combining an iterative algorithm of a random rounding and Lagrangian dual technique.

Inventors

  • SHI YOU
  • YI CHANGYAN
  • WANG RAN
  • WU QIANG
  • CHEN BING

Assignees

  • 南京航空航天大学

Dates

Publication Date
20260512
Application Date
20220909

Claims (8)

  1. 1. A service migration and task rerouting balance and resource management online optimization method facing mobile edge computing is characterized by comprising the following steps: (1) Construction of the member Individual distributed edge servers A mobile edge computing system composed of heterogeneous mobile devices, wherein each mobile device in the system has a computation-intensive task flow to be executed, and random movement of the mobile device triggers dynamic access connection switching; (2) The mobile equipment selects local calculation or calculation unloading according to the self available resource capacity, and the calculation comprises calculation of system overhead, wherein the system overhead comprises local calculation energy consumption, transmission energy consumption from the mobile equipment to an edge server and calculation energy consumption for unloading a calculation task to the edge server; (3) The edge server distributes transmission bandwidth resources and CPU computing resources for potential access equipment, wherein the transmission bandwidth resources and the CPU computing resources comprise service migration energy consumption and computation task rerouting energy consumption computation, and the mobile equipment adaptively selects a service mode according to dynamic channel conditions, random task generation and self-caching capacity, wherein the service mode comprises service migration or task rerouting; (4) A dual time scale mobility management model is built to balance the overhead of service migration and task rerouting, where, For the large time scale index, each large time frame contains A small number of time frames of time, For small time scale indexes, the access selection, service migration and task rerouting are operated under a large time scale, and the task unloading and the transmission and calculation resource allocation are operated under a small time scale; (5) The method aims at minimizing the long-term average service delay, and determines the long-term optimization problem and constraint conditions of edge calculation, including bandwidth allocation upper limit constraint, long-term stability constraint of a local task queue and server The cache capacity constraint of the system, the long-term stability constraint of the energy consumption of the mobile edge computing system, the computing resource allocation constraint of the edge server, the selection constraint of service migration and task rerouting and the consideration of decision variables thereof; (6) Equivalent problem reconstruction, based on the modified Lyapunov online algorithm, decomposes long-term problems into a series of deterministic problems, including the decomposition of each large slot Is evenly distributed to the migration delay and the energy consumption of All small time slots in In accordance with each minislot The total service delay and the total energy consumption in the system are used for problem transformation, and an energy consumption loss queue is defined To describe the device Is in a small time slot In combination with a local task buffer queue, wherein a quadratic Lyapunov function is defined as follows: Wherein, the Queue for energy consumption deficit Buffering queues with local tasks And deriving a conditional Lyapunov drift function: (7) Decoupling decisions into two sub-questions of different time scales, based on instantaneous values of the energy consumption deficit queues and the local task backlog queues of all mobile devices, for each large time slot The optimization problem of joint access selection, service migration and task rerouting is converted into an overall planning problem according to each obtained big time slot Is an optimal decision for access selection, service migration and task rerouting in each minislot Optimizing task offloading decisions, transmission and computing resource allocation decisions.
  2. 2. The method for online optimization of mobile edge computing-oriented service migration and task rerouting balance and resource management of claim 1, wherein the mobile edge computing system comprises one computationally intensive task flow to be performed by each mobile device.
  3. 3. The mobile edge computing-oriented service migration and task rerouting balance and resource management online optimization method as set forth in claim 1, wherein the overhead computing process in step (2) comprises the following steps: (2-1) definition Representing mobile devices The CPU computation rate of (2) and the computation delay of local computation are expressed as follows: , Wherein, the For mobile devices Is used for the task size of (1), Representing the number of CPU cycles required to complete a 1bit computing task; according to an energy model in the CMOS circuit, determining the local calculation energy consumption to calculate as follows: Wherein, the For mobile devices Is determined by the chip architecture of the mobile device; (2-2) definition Indicated in a small time slot Mobile device To edge servers The mathematical expression of the instantaneous receiving signal-to-noise ratio of (a) is: , Wherein, the For mobile devices Is used for the transmission power of the (c), In order to be a path loss index, For the bandwidth of the communication to be available, For mobile devices And edge server The distance between the two plates is set to be equal, As the spectral density of the channel noise power, Is the fading amplitude; Obtaining mobile equipment according to a fragrant-Hartley formula And edge server The mathematical expression of the transmission rate between the two is as follows: Wherein, the Representation device Selective access server Is used for the decision variables of (a), Representing a transmission bandwidth allocation decision variable; (2-3) according to the Mobile device And edge server The transmission rate between the two transmission rates is used for acquiring the transmission delay of task unloading: , the corresponding transmission energy consumption is as follows: ; (2-4) definition Is an edge server Is a mobile device Is at the edge server The calculation time delay of the calculation is as follows: , Wherein, the Representing a CPU resource allocation decision, and correspondingly calculating the energy consumption as follows: , Wherein, the Is an edge server Is determined by the chip architecture of the edge server.
  4. 4. The mobile edge computing-oriented service migration and task rerouting balance and resource management online optimization method of claim 3, wherein step (3) comprises the following computing process: (3-1) defining state variables To describe the device The required application instance is at time Is initially installed on a server The mathematical expression is as follows: , Wherein, the Representing service migration decisions, Representing task rerouting decisions; (3-2) when the service migration mode is adopted, the service migration delay is generated only once in a time slot with a large time scale, and the expression is: ; when the task rerouting mode is adopted, the routing delay of the calculation task is generated in each small time scale time slot, and the expression is as follows: ; considering all mode selections in aggregate, in each large time scale, the mobile device is executed The total service delay of the computing tasks of (1) can be expressed as: Wherein, the Representing an offloading decision; (3-3) when the service migration mode is adopted, the expression of service migration energy consumption is: , Wherein the method comprises the steps of Representing the transmission power of the edge server, the value of which can be predetermined; When adopting the task rerouting mode, the expression of the routing energy consumption of the calculation task is as follows: ; considering all mode selections in aggregate, in each large time scale, the mobile device is executed The total energy consumption of the computing task of (a) is expressed as: (3-4) for any edge server In large time slots In this, the buffer space occupied by the application instance migrated from the other edge server is expressed as: ; For any edge server In large time slots Application instance selection reservation has been previously installed for handling the task of rerouting back, which takes up a buffer space expressed as: 。
  5. 5. The mobile edge computing oriented service migration and task rerouting balance and resource management online optimization method of claim 4, wherein the long term optimization problem and constraint conditions in step (5) are specifically expressed as follows: s.t. (C6) , wherein C1 represents a bandwidth allocation upper limit constraint, C2 represents a long-term stability constraint of the local task queue, wherein Representing local task queue backlog, C3 represents a server Wherein Representation server Wherein C4 represents a long-term stability constraint for system energy consumption, wherein Representing the total energy consumption of the system, Representing a long term stable upper bound on system energy consumption, C5 represents a computational resource allocation constraint, wherein Representation device The application instance cache location of (1), C6 representing the selection constraints of service migration and task rerouting, C7 representing that service migration, task rerouting and offloading are binary decision variables.
  6. 6. The mobile edge computing-oriented service migration and task rerouting balance and resource management online optimization method of claim 5, wherein the problem reconstruction of the equivalence in step (6) comprises the following computing process: this step will be every large slot Is evenly distributed to the migration delay and the energy consumption of All small time slots in In (b), then each minislot The total service delay and total energy consumption of (a) are expressed as: Wherein, sum up Representing each minislot separately Service migration delay and migration energy consumption; Thus, the original optimization problem is converted into: S.t. (C2) (C3) (C4) (C5) (6) (7) Defining energy consumption deficit queues To describe the device Is in a small time slot Deviation between the energy consumption of (c) and the long-term energy consumption budget, The expression of (2) is as follows: Defining a secondary Lyapunov function by combining a local task buffer queue: , Wherein, the A collection of energy consumption loss queues and local task buffer queues; next, a conditional Lyapunov drift function is derived: , Based on this, a Lyapunov drift-penalty function is constructed: , Wherein, the Is Lyapunov control parameter; meanwhile, the Lyapunov drift-penalty function satisfies the following theorem: Wherein, the , The slot length is the slot length of the small slot; The original optimization problem is converted into a minimum value of a right expression for solving the Lyapunov drift-penalty function, and decision variables and constraint conditions of the double time scales are kept unchanged.
  7. 7. The mobile edge computing oriented service migration and task rerouting balancing and resource management online optimization method of claim 6, wherein in step (7), the optimization problem of joint transmission and computing resource allocation is transformed into the following sub-problem: S.t. Wherein, the ; The problem is a linear programming problem, and an optimal solution of transmission and calculation resource allocation is obtained by adopting a Lagrange dual method; determining equipment by comparing optimal strategy with locally calculated service delay Task offloading decisions for (a) I.e. if the service delay of the local computation is small No calculation unloading is performed for =0 and conversely, Calculation unloading was performed with =1.
  8. 8. The mobile edge computing oriented service migration and task rerouting balancing and resource management online optimization method of claim 6, wherein in step (7), decoupling the decision into two different time scale sub-questions further comprises the following process: Definition of binary variables As a selection indicator of both, the expression is: Service migration decision And task reroute decisions Satisfies the condition + =1; Given the instantaneous values of the energy consumption deficit queue and the local task backlog queue of all the current mobile devices, at each large time slot The joint access selection, service migration and task rerouting optimization problem of (c) is translated into the following sub-problems: S.t. The problem is integer programming, the optimal solution of access selection, service migration and task rerouting is obtained by adopting random rounding, and each large time slot is obtained Is an optimal decision for access selection, service migration and task rerouting in each minislot Optimizing task offloading decisions, transmission and computing resource allocation decisions.

Description

Service migration and task rerouting balance and resource management online optimization method oriented to mobile edge computing Technical Field The invention belongs to the technical field of communication of mobile Internet of things, and particularly relates to a mobile edge computing-oriented service migration and task rerouting balance and resource management online optimization method. Background The mobile internet has evolved rapidly driven by the rapid evolution of 6G, web 3.0.0 and its enabled intelligent mobile devices. With the development of technologies such as autopilot, smart glasses and haptic apparel, various computationally intensive, time-delay sensitive high-tech applications have grown, such as V2X communication, immersive augmented reality (XR) and Human Digital Twinning (HDT). However, it is difficult for the mobile device itself to meet the stringent service requirements of the cloud computing system-applications for which these resources are scarce due to their infrastructure limitations. Mobile edge computing (also known as multi-access edge computing) provides high processing power with relatively low response delay by enabling mobile devices to offload heavy loads (i.e., computing tasks) to migrate to edge servers deployed on wireless access points. Because of the great potential in improving computing and communication efficiency, mobile edge computing has gained a great deal of research attention, including access selection and handoff, service migration and application placement, and joint allocation of computing and communication resources. However, there are still some key issues, particularly how to implement seamless and low cost edge computing services for heterogeneous mobile devices, which are not yet adequately addressed. Intuitively, a radio access handoff may be triggered when a mobile device leaves the radio coverage of the current edge server. If edge computing services are to continue to be provided to the device, one common approach is to migrate its required application instances from the once accessed edge server to a new edge server. However, as noted by the european telecommunications standards, service migration itself may lead to potential service disruption, and thus, task rerouting should be appreciated in addition to service migration in order to reroute computing tasks of a mobile device back to its previously hosted server. Obviously, task rerouting, while avoiding the overhead of large-scale application migration, inevitably introduces delays and power consumption, so it is very challenging to balance service migration and task rerouting in the optimal management of a mobile edge computing system: 1) In order to improve the quality of service (QoS) of a mobile edge computing system, it is desirable to jointly optimize access selection, service migration, task rerouting, and transmission resource allocation for all devices to maximize the overall system performance. However, these decisions are highly dependent on the cache state (i.e., application instance in the cache) of each edge server, are typically nonlinear, and the access selection, service migration, and task rerouting decisions are discrete, while the computation and communication resource allocation may be continuous, which makes the optimization problem a mixed integer nonlinear programming problem, i.e., NP-hard. 2) In a mobile edge computing system, all optimization decisions (access selection, service migration, task rerouting and resource allocation) need to be dynamically adjusted due to time-varying channel conditions, mobility of the device, and randomness of task generation. This requires on-line optimization and long-term performance guarantees, which however requires statistics of future network dynamics, but this information is difficult to obtain. 3) For each mobile device, its access selection, service migration, and task rerouting may not be changing in real time, as frequent access handoffs may produce severe doppler shifts, while frequent service migration or task rerouting changes may result in significant configuration overhead. In contrast, to better cope with time-varying task generation and channel conditions, higher update frequencies are required for computation and communication resource allocation. This suggests that decision variables in the online optimization problem should be optimized asynchronously on different time scales, rather than on only one time scale as in conventional studies. Disclosure of Invention The invention aims to provide a service migration and task rerouting balance and resource management online optimization method for mobile edge computing, which aims to minimize long-term average service delay of all mobile devices, ensure stability of a system and limited energy consumption and sufficient caching capacity, and provide seamless, economical and efficient edge computing service for the mobile devices. A service migration and task rerouti