Step 1. The vehicle layer submits the request task for the vehicle.
Step 2. The FLI algorithm of the edge layer determines the compute node of the task.
Step 3. If the compute node is a cloud node, the task is sent to the cloud node for processing and then return the result.
Step 4. If the compute node is an edge node, the edge node applies the KDMSSA algorithm to the task queue after a certain interval. It allocates specific virtual machine computing resources. The tasks are executed on the specified virtual machine. Finally, return the result.
3.1 FLI algorithm
Typically, any number of input variables are used in fuzzy logic. This paper selects variables that have a significant impact on task execution performance. Bandwidth of cloud nodes and virtual machine utilization of edge servers are important factors. The characteristics of the vehicle's mission also have a certain impact. Therefore, this paper selects task length, bandwidth of cloud node, and virtual machine utilization of edge node as the input of fuzzy inference system. Because the vehicle is in constant motion. The location is constantly changing. The location of the vehicle affects the choice of the computing node for the task. Therefore, this paper presents two different scenarios (with overlap/without overlap). The method of task node selection based on fuzzy logic inference. Fuzzy logic system consists of four parts, input, fuzzification, rule base, and defuzzification. The details are as follows.
(1) Case1
(2) There is no overlap.
The case 1 of Fig. 3, the areas of responsibility of adjacent edge servers do not overlap with each other. The vehicle is in the area where a single edge server is responsible. In fuzzy inference, it will determine how to process the requests from vehicles. Specifically, it is to decide whether these requests should be processed by cloud nodes or edge servers.
Input. In Fig. 3, in order to select the best compute node, this paper selects the task length, the bandwidth of the cloud node, and the virtual machine utilization of the edge node as the input of the fuzzy inference system. Mathematically, it can be defined as the formula (1). Where \(\epsilon\) represents the length of the task, \(\eta\) represents the virtual machine utilization of the edge server, and \(\theta\) represents the cloud node bandwidth. In general, fuzzy logic reasoning uses linguistic variables (non-numbers) from natural language in the case of numerical values. Therefore, this paper uses low (L), medium (M) and high (H) as language variables.
$$\begin{array}{c}\varGamma =\left(\epsilon ,\eta ,\theta \right)\#\left(1\right)\end{array}$$
Fuzzification. Membership functions can be in different forms, such as triangular, trapezoidal, piecewise linear, or Gaussian [33]. This article selects the triangular. Membership function is shown in Fig. 4. Figure 4(a) is a function of task length. Figure 4(b) is a function of virtual machine utilization. Also, Fig. 4(c) is a function of cloud node bandwidth. Fuzzification is the process of converting clear values to fuzzy values by using membership functions. In this paper, the membership function shown in Fig. 4 is used to calculate the membership degrees of the three variables respectively to obtain the fuzzy set. Formula (2) is a set of membership function 1 in mathematical form.
$${\varGamma }_{\epsilon }\left(x\right)=\left[{w}_{\epsilon }^{L}\right(x), {w}_{\epsilon }^{M}(x), {w}_{\epsilon }^{H}(x\left)\right]{\varGamma }_{\eta }\left(x\right)=\left[{w}_{\eta }^{L}\right(x), {w}_{\eta }^{M}(x), {w}_{\eta }^{H}(x\left)\right]{\varGamma }_{\theta }\left(x\right)=\left[{w}_{\theta }^{L}\right(x), {w}_{\theta }^{M}(x), {w}_{\theta }^{H}(x\left)\right]$$
2
Fuzzy rule base. Defining fuzzy rules is critical, because the performance of the system depends on these rules. This paper finds a relatively good fuzzy rule set from experience. In case 1, there are 3 membership functions and 3 language terms. And the number of fuzzy rules is 27. Some example rules are shown in Table 1. Fuzzy rule base 1 is used to get the node selection result.
Table 1
Examples of fuzzy rule base 1.
Rule Index | \(\epsilon\) | \(\eta\) | \(\theta\) | \(\varGamma\) |
R1 | L | L | L | edge |
R2 | H | M | L | edge |
R3 | M | H | M | cloud |
R4 | H | H | H | cloud |
Defuzzification. In fuzzy logic, the output result of fuzzy rules is usually a fuzzy set. It needs to be de-fuzzized. It is converted into a specific numerical value. Common defuzzification methods include maximum membership degree method, weighted average method, and area method. The maximum membership degree method is chosen in this paper, as shown in formula (3).
$$\delta =max\left\{{\varGamma }_{\epsilon }\right(x), {\varGamma }_{\eta }(x), {\varGamma }_{\theta }(x\left)\right\}$$
3
(3) Case2
(4) There is some overlap.
In the case 2 of Fig. 5, there is overlap in the areas of responsibility of adjacent edge servers. When vehicle V is in the overlapping area, fuzzy inference is necessary to judge the request of vehicle C3. The request is processed by the cloud node, edge server 1, or edge server 2.
Input. In Fig. 5, task length, bandwidth of cloud node, virtual machine utilization of edge server 1, and virtual machine utilization of edge server 2 are selected as the input of fuzzy inference system. Its input can be defined as the formula (4). Where \(\epsilon\) represents the length of the task, \({\eta }_{1}\) represents the virtual machine utilization of edge server 1, \({\eta }_{2}\) represents the virtual machine utilization of edge server 2, and \(\theta\) represents the bandwidth of the cloud node. In this paper, low (L), medium (M), and high (H) are used as language variables.
$$\varGamma =(\epsilon , {\eta }_{1}, {\eta }_{2}, \theta )$$
4
Fuzzification. In this paper, the triangular membership function is selected, as shown in Fig. 6. Figure 6(a) is a function of task length. Figure 6(b) is a function of edge server 1 virtual machine utilization. Figure 6(c) is a function of edge server 2 virtual machine utilization. Also, Fig. 6(d) is a function of cloud node bandwidth. In this paper, the membership function shown in Fig. 6 is used to calculate the membership degrees of the four variables respectively to obtain the fuzzy set. Formula (5) is a set of membership function 2 in mathematical form.
$${\varGamma }_{\epsilon }\left(x\right)=\left[{w}_{\epsilon }^{L}\right(x), {w}_{\epsilon }^{M}(x), {w}_{\epsilon }^{H}(x\left)\right]{\varGamma }_{{\eta }_{1}}\left(x\right)=\left[{w}_{{\eta }_{1}}^{L}\right(x), {w}_{{\eta }_{1}}^{M}(x), {w}_{{\eta }_{1}}^{H}(x\left)\right]{\varGamma }_{{\eta }_{2}}\left(x\right)=\left[{w}_{{\eta }_{2}}^{L}\right(x), {w}_{{\eta }_{2}}^{M}(x), {w}_{{\eta }_{2}}^{H}(x\left)\right]{\varGamma }_{\theta }\left(x\right)=\left[{w}_{\theta }^{L}\right(x), {w}_{\theta }^{M}(x), {w}_{\theta }^{H}(x\left)\right]$$
5
Fuzzy rule base. In case 2, since there are four membership functions and three language terms, the number of fuzzy rules is 81. Some example rules are shown in Table 2. Fuzzy rule base 2 is used to get the node selection result.
Defuzzification. In case 2, this paper uses the maximum membership method to blur, as shown in formula (6).
$$\delta =max\left\{{\varGamma }_{\epsilon }\right(x), {\varGamma }_{{\eta }_{1}}(x), {\varGamma }_{{\eta }_{2}}(x), {\varGamma }_{\theta }(x\left)\right\}$$
6
Table 2
Examples of fuzzy rule base 2.
Rule Index | \(\epsilon\) | \({\eta }_{1}\) | \({\eta }_{2}\) | \(\theta\) | \(\varGamma\) |
R1 | L | H | L | H | Edge2 |
R2 | L | L | H | M | Edge1 |
R3 | H | H | M | L | Edge2 |
R4 | H | L | H | L | Edge1 |
R5 | H | H | H | L | cloud |
R6 | H | H | H | H | cloud |
-
Algorithm Description
As shown in algorithm 1, this paper sets the membership function and fuzzy rule base respectively in two cases. First, the task belongs to case 1 or case 2 based on the geographical location of the vehicle task. Then, it needs to input the relevant information about the task. The information of cloud nodes and edge nodes is also necessary to be input. Then the fuzzy and defuzzy operations are carried out in turn. Finally, output the processor node of the task.
Algorithm 1: FLI Algorithm |
Input: membership function set 1, membership function set 2; Fuzzy rule base 1, fuzzy rule base 2 |
Output: Processor node of the task |
1 | Determine the location of the vehicle sending the task |
2 | In case 1 |
3 | Input tuple \(\varGamma =(\epsilon , \eta , \theta )\) |
4 | Fuzzy using membership function set 1 |
5 | Fuzzy set is obtained by using fuzzy rule base 1 |
6 | Use formula (1) to deblur |
7 | Return result |
8 | In case 2 |
9 | Input tuple \(\varGamma =(\epsilon , {\eta }_{1}, {\eta }_{2}, \theta )\) |
10 | Fuzzy using membership function set 2 |
11 | Fuzzy set is obtained by using fuzzy rule base 2 |
12 | Use formula (2) to deblur |
13 | Return result |
14 | End |
3.2 KDMSSA
Sparrow Search algorithm (SSA) is a swarm intelligence optimization algorithm. This algorithm is designed to simulate the behavior of a sparrow. The sparrow avoids predators in its environment. At the same time, it constantly approaches the location of food for survival. SSA not only provides low computational complexity, but also is easy to implement and operate. The SSA algorithm can also find the optimal solution in a short time. This is very beneficial for the reasonable allocation of computing resources in the networked vehicle environment.
● In updating the forager's behavioral strategy, these adhere to specific logical rules embodied in Formula (7). Specifically, when the perceived risk level \(\mathcal{R}\) is less than the preset safety threshold \(\mathcal{S}\mathcal{T}\), it indicates that the current environment is deemed safe. Consequently, the forager continues to play its leading role, guiding the entire swarm towards foraging areas in search of resources. However, once the risk level \(\mathcal{R}\) reaches or exceeds the safety threshold \(\mathcal{S}\mathcal{T}\), it poses an immediate threat to the swarm's safety. In this scenario, the forager's role shifts. It ceases to focus solely on foraging and promptly identifies the potential threat, swiftly taking action to lead the entire swarm towards a relatively safe area. This ensures the survival and reproduction of the swarm remain unaffected.
$${x}_{i,d}^{t+1}=\left\{\begin{array}{c}{x}_{i,d}^{t}\times exp\left(-\frac{i}{\alpha }\times {iter}_{max}\right) R<ST\\ {x}_{i,d}^{t}+Q R\ge ST\end{array}\right.$$
7
\({x}_{i,d}^{t}\) represents the d-dimensional position of the i-th individual in the t-generation of the population. \({\alpha }\in [0, 1]\)denotes a uniformly distributed random number, serving as a factor in the optimization process. \({iter}_{max}\) signifies the maximum number of iterations allowed for the algorithm to converge towards an optimal solution.\(\mathcal{ }\mathcal{R}\in \left[\text{0,1}\right]\) is an alarm value, utilized to trigger specific behaviors or responses in the algorithm based on the perceived level of danger or change in the environment. \(\mathcal{S}\mathcal{T}\in \left[\text{0.5,1.0}\right]\) represents a safety threshold, defining a range within which individuals are considered to be relatively secure from potential threats or adverse conditions. Q stands for a random number drawn from a standard normal distribution, introducing stochasticity into the algorithm to enable exploration of the search space and avoid premature convergence.
● When adjusting the position of followers, these follows the rules defined in formula (8). Specifically, when the follower's index \(i\) satisfies the condition \(i\le \raisebox{1ex}{$\mathcal{N}$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\), it indicates that they belong to the core group of followers within the swarm. These followers closely follow and supervise the forager's actions, collaborating with it in food scavenging to ensure the swarm's foraging efficiency and success rate. However, if the follower's index \(i\) is greater than \(\raisebox{1ex}{$\mathcal{N}$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\), it means they belong to the periphery or independent action units of the swarm. These followers will no longer strictly rely on the guidance of the forager but instead exhibit greater autonomy, choosing to forage for food resources independently.
\({x}_{i,d}^{t+1}=\left\{\begin{array}{c}Q\times exp\left(\frac{{xw}_{i,d}^{t}-{x}_{i,d}^{t}}{{i}^{2}}\right) i>\raisebox{1ex}{$\mathcal{N}$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\\ {xb}_{i,d}^{t}+\frac{1}{d}\sum _{d=1}^{d}\left(rand\left\{-\text{1,1}\right\}\times \left(\left|{xb}_{i,d}^{t}-{x}_{i,d}^{t}\right|\right)\right) i\le \raisebox{1ex}{$\mathcal{N}$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\end{array}\right.\) | (8) |
\({xw}_{i,d}^{t}\) signifies the worst position of the i-th sparrow in the d-dimension within the population at the t-generation. \({xb}_{i,d}^{t}\) represents the best position of the i-th sparrow in the d-dimension within the population at the t-generation. \(\mathcal{N}\) denotes the population size, specifying the total number of sparrows participating in the optimization process.
● When adjusting the position of defenders, it is done based on specific conditions to optimize their layout and enhance the defensive capabilities of the swarm. As shown in formula (10), when \({\mathcal{F}}_{\mathcal{i}}\ne {\mathcal{F}}_{\mathcal{g}}\), it typically indicates that the defenders currently situated at the edge of the swarm have perceived potential danger. To mitigate the risk of predation, these defenders will adopt strategies to gradually move closer to the center of the swarm, thereby facilitating better coordination and protection of the entire swarm. On the other hand, if \({\mathcal{F}}_{\mathcal{i}}={\mathcal{F}}_{\mathcal{g}}\), it signifies that the defenders located at the center of the swarm have also detected the proximity of a threat. In such situations, to avoid becoming the primary target of predators, these defenders need to promptly and strategically adjust their positions, shedding their current, potentially exposed locations. This ensures their own safety while maintaining a defensive coverage over the entire swarm.
$${x}_{i,d}^{t+1}=\left\{\begin{array}{c}{xb}_{i,d}^{t}+\beta \left({x}_{i,d}^{t}-{xb}_{i,d}^{t}\right) {\mathcal{F}}_{\mathcal{i}}\ne {\mathcal{F}}_{\mathcal{g}}\\ {x}_{i,d}^{t}+k\times \left(\frac{{x}_{i,d}^{t}-{xw}_{i,d}^{t}}{\left|{\mathcal{F}}_{\mathcal{i}}-{\mathcal{F}}_{\mathcal{w}}\right|+\epsilon }\right) {\mathcal{F}}_{\mathcal{i}}={\mathcal{F}}_{\mathcal{g}}\end{array}\right.$$
9
\(\beta\) represents a random number drawn from a standard normal distribution.\({\mathcal{F}}_{\mathcal{g}}\) represents the fitness value of the sparrow occupying the best position within the population. \(\text{k}\in [-\text{1,1}]\) is a uniformly distributed random number. \({\mathcal{F}}_{\mathcal{w}}\)denotes the fitness value of the sparrow(s) occupying the worst position(s) within the population. \(\epsilon\) is a small positive number, used primarily to avoid division by zero in calculations.
● In addressing the limitation of SSA, which inherently tackles single-objective optimization problems, this study confronts the challenge of solving a multi-objective mathematical model. To bridge this gap, we transform the multiple objectives into a single objective for solution. This is achieved by assigning a weight \({w}_{i}\)to each objective and summing them up to derive a composite fitness value. As depicted in Eq. (10), \({w}_{i}\) represents the weight corresponding to each objective, while \({f}_{i}\) denotes the individual objective function. By this method, we effectively integrate the multiple objectives into a unified optimization framework.
$$\mathbf{£}={w}_{1}*{f}_{1}+{w}_{2}*{f}_{2}+{w}_{3}*{f}_{3}+{w}_{4}*{f}_{4}$$
10
Due to the constant change of vehicle location, the traditional static resource allocation method may no longer be suitable. The Sparrow Search algorithm uses its dynamic location update mechanism. It can adapt to changes in the vehicle's position in real time. The allocation of compute nodes is adjusted accordingly. When the vehicle moves to a new location, the algorithm can quickly reevaluate the surrounding compute nodes. The algorithm can make the optimal allocation decision according to the new situation.
Therefore, in order to solve the problem of allocation of computing resources within nodes, this paper aims to minimize the completion time and load balancing. A Discrete multi-objective Sparrow Search algorithm based on K-means (KDMSSA) is proposed. Table 3 shows the symbol table.
Table 3
symbol | Meaning |
\({r}_{id}\) | Number of task i |
\({r}_{len}\) | The task i need to deal with the amount of data |
\({r}_{cpu}\) | The task i complete the required CPU resources |
\({r}_{ram}\) | Memory resources required for task i to complete |
\({r}_{bw}\) | Bandwidth resources required for task i to complete |
\({v}_{id}\) | The number of the virtual machine j |
\({v}_{f}\) | The computing power of virtual machine j |
\({v}_{cpu}\) | The CPU resources of virtual machine j |
\({v}_{ram}\) | The memory resources of virtual machine j |
\({v}_{bw}\) | The bandwidth resource of virtual machine j |
Suppose there are n tasks in the task queue of edge node i. The edge node contains m VMS. Allocate n tasks to m VMS. Formulas (11) and (12) represent the task assignment of edge node i.
$$\overrightarrow{p}=\left[{p}_{i,j}\right]=\left[\begin{array}{cc}\begin{array}{cc}{p}_{\text{1,1}}& {p}_{\text{1,2}}\\ {p}_{\text{2,1}}& {p}_{\text{2,2}}\end{array}& \begin{array}{cc}\cdots & {p}_{1,m}\\ \cdots & {p}_{2,m}\end{array}\\ \begin{array}{cc}⋮& ⋮\\ {p}_{n,1}& {p}_{n,2}\end{array}& \begin{array}{cc}\ddots & ⋮\\ \cdots & {p}_{n,m}\end{array}\end{array}\right]$$
11
$${p}_{i,j}=\left\{\begin{array}{c}1 task i is assigned to VM j\\ 0 unallotment \end{array}\right.$$
12
The completion delays of task i includes the processing delay and the waiting delay. Formula (13) is the processing delay of task i. Formula (14) is the waiting delay of task i. Formula (15) is the completion delay of task i. Formula (16) is the maximum completion delay of n tasks.
$${t}_{pro}^{i}=\frac{{r}_{len}^{i}}{{v}_{f}^{i}}$$
13
$${t}_{wait}^{i}=\left\{\begin{array}{c} 0 i=1\\ {t}_{wait}^{i-1}+{t}_{pro}^{i-1} i>1\end{array}\right.$$
14
$${t}_{total}^{i}={t}_{pro}^{i}+{t}_{wait}^{i}$$
15
$$\mathcal{T}=\text{m}\text{a}\text{x}\{\sum _{i=1}^{n}{p}_{i,1}\times {t}_{total}^{i},\sum _{i=1}^{n}{p}_{i,2}\times {t}_{total}^{i},\dots ,\sum _{i=1}^{n}{p}_{i,m}\times {t}_{total}^{i}\}$$
16
Load balancing involves the allocation of requests when multiple virtual machines are deployed on edge servers. By employing specific algorithms and strategies, the load on each virtual machine can be balanced. The objective of this approach is to enhance system performance and reliability. The lower the comprehensive load value of the edge node, the more balanced the request distribution. Formula (17) indicates the usage of a resource for a single VM. Formula (18) is the combined load of a single virtual machine j. Formula (19) is the comprehensive load of the edge node.
$$\mu =\frac{{R}_{i, index}}{{v}_{j, index}}$$
17
$${L}_{j}=\sum _{k=1}^{sum}{\lambda }_{k}{\mu }_{k}$$
18
Constraint \({\sum }_{k=1}^{sum}{\lambda }_{k}=1\)(\({\lambda }_{k}\) is the weight of a resource)
$$LEN=\sqrt{\frac{1}{m}\sum _{j=1}^{m}{({L}_{j}-\frac{1}{m}\sum _{j=1}^{m}{L}_{j})}^{2}}$$
19
In the internal computing resource allocation of nodes, this paper takes minimizing the completion delay of tasks and the load balancing of nodes as optimization objectives. It seeks to find the optimal computing resource allocation scheme within the node. The objective function is shown in formula (20).
$$\varGamma =\{\text{min}\left(\mathcal{T}\right),\text{m}\text{i}\text{n}(LEN\left)\right\}$$
20
In this paper, each sparrow's position vector represents a solution to the computational resource allocation problem. The dimension of each sparrow's position vector is equal to the number of tasks n in the task queue. The position of each sparrow is represented by n dimensional coordinates. Each coordinate is limited to a range between (1, m + 1). m is the number of VMS. The integer part of the sparrow position vector coordinates is taken as the mapping result between the task and the virtual machine. Table 4 assumes that an edge node has 6 tasks and 4 virtual machines. The position of a sparrow is (1.1,2.3,1.5,3.4,2.7,4.2).
In formula (21), task \(\{{R}_{1}, {R}_{3}\}\) is assigned to virtual machine \({V}_{1}\). Task \(\{{R}_{2}, {R}_{5}\}\) is assigned to virtual machine \({V}_{2}\). Task \(\left\{{R}_{4}\right\}\) is assigned to virtual machine \({V}_{3}\). Task \(\left\{{R}_{6}\right\}\) is assigned to virtual machine \({V}_{4}\).
Table 4
shows the mapping between tasks and VMS in the example.
Task number | Sparrow position | Virtual machine number |
1 | 1.1 | 1 |
2 | 2.3 | 2 |
3 | 1.5 | 1 |
4 | 3.4 | 3 |
5 | 2.7 | 2 |
6 | 4.2 | 4 |
\(\{{R}_{1}, {R}_{3}\}\underset{allocation}{\to }{V}_{1}\) \(\{{R}_{2}, {R}_{5}\}\underset{allocation}{\to }{V}_{2}\) \(\left\{{R}_{4}\right\}\underset{allocation}{\to }{V}_{3}\) \(\left\{{R}_{6}\right\}\underset{allocation}{\to }{V}_{4}\) (21)
Therefore, the KDMSSA algorithm flowchart is shown in Fig. 7. It builds a conversion mechanism in the form of integer encoding. This corresponds the sparrow individual positions in SSA to integer encodings. This enables it to solve discrete problems. It can solve discrete problems. First, the K-means algorithm [34] is used to cluster the sparrow population. And K subpopulations were obtained. Then, the positions of sparrows in each subpopulation are encoded, sequenced, and decoded. Thus the k optimal solutions are obtained. Finally, the fast non-dominated sorting algorithm [35] is used to sort the k optimal solutions. So that SSA can not only solve the problem of local optimal solution, but also solve the discrete multi-objective optimization problem. The details are shown in algorithm 2.