Introduction
-
Aiming at the issue of edge server deployment, the HE-GA model is proposed to achieve the dual-objective optimization of communication delay and load balance under the premise of satisfying the optimal benefits quantity. The HE-GA model can be applied to edge server deployment in smart cities. As far as we know, few scholars have conducted in-depth research in this topic.
-
Based on the HE-GA model, with the optimal benefit quantity limitation, the genetic algorithm is exploited to solve the dual-objective issue under multiple constraints to balance the load and reduce the communication delay, to obtain an efficient and feasible edge server deployment solution.
-
On the basis of Mobile Communication Base Station Data Set of Shanghai Telecom, the comparative experiments and in-depth analysis are performed. The experimental results demonstrate that, under the premise of satisfying the optimal benefit quantity, the proposed approach comprehensively outperforms five typical deployment methods such as MIP, K-means, AK-means, Top-K, and Random according to reducing the communication delay and balancing the workload.
Related work
HE-GA method
Motivation
-
Cloud Service Center: it is still consistent with current cloud computing center. In mobile service computing system, it possesses the most powerful computing power and storage resources in the system. It provides all services for end users. The cloud service center communicates with all edge nodes. It is responsible for processing tasks with huge computing power demand and storing all results. At the same time, the cloud service center carries out distributed policy distribution management for the tasks of edge mobile service computing system.
-
Edge Node: it is mainly composed of edge server which has certain computing power and storage resources. It provides services to terminal users within its ability through reasonable deployment. Every edge server is liable for handling terminal user requests in a certain area through the base station. All edge servers unite to achieve the full coverage of the intelligent city at edge layer. Simultaneously, all edge servers are linked to cloud service center. They become the connection hub between the end users, mobile communication base stations, and the cloud service center. The number and manner of deployment of edge servers are also the core of this paper’s research.
-
Terminal Node: it mainly refers to mobile intelligent terminal. It has extremely limited computing power and storage resources. Its main task is to establish contact with the edge server through base stations, transmit the mobile intelligent terminal’s service requisition to edge nodes or cloud service center, and present the final result to the user.
Symbol | Implication |
---|---|
G | Mobile Service Computing network |
V | The node of Mobile Service Computing |
E | Connection during base station and edge server of Mobile Service Computing network |
B | The set of mobile correspondence base station |
n | Quantity of mobile communication base station |
S | Set of edge server |
K | Quantity of edge server |
\(E_s\)
| Set of base stations responsible for every edge server |
\(t_b\)
| The workload of base station b, where \(b\in B\)
|
\(t_s\)
| The workload successfully assigned to edge server |
\(t_c\)
| Edge servers deploy additional fixed load |
\(T_s\)
| The workload of the edge server s, where \(s\in S\)
|
\(T_s^{opt}\)
| Optimal number of cost-effective deployments of edge servers |
\(\rho\)
| The optimal benefits of edge servers |
\(l_b\)
| Situation of base station b |
\(l_s\)
| Situation of edge server s |
d | Communication delay among edge server and basestation |
\(K_s\)
| Optimal deployment amount of edge servers |
p | Probability of a base station choosing an edge server |
\(P_s\)
| Probability of successful allocation of all base stations |
Edge server deployment model
Setting of constraints and calculation of optimal benefit quantity
-
Constraint 1: Any two edge servers do not share any base station directly, and the total amount of base stations that all edge servers are responsible for justly is mobile communication base station set B.
-
Constraint 2: For the edge server, any service request of the mobile intelligent terminal that establishes contact with it through its responsible mobile communication base station must be processed.
-
Constraint 3: To ensure the highest input-output benefit of mobile edge servers, the amount of deployed edge servers is less than the optimal benefit quantity, and the total load on each edge server does not exceed a predefined maximum value.
Multi-objective optimization modeling
-
All edge servers will be deployed, and no base station is shared between every edge server, and total base stations will be allotted to edge servers, i.e.,$$\begin{aligned} E_i\cap Ej=\emptyset \end{aligned}$$(10)$$\begin{aligned} \bigcup _{s\in S}=B \end{aligned}$$(11)
-
The deployment location of the edge server will be opted from the deployment locations of the mobile communication base stations, and the location will be shared with the base stations. Through the mobile communication base station responsible for the area, any mobile intelligent terminal will correspond with edge servers responsible for base stations and request services. The edge server will process the service request from the user and return the result (as Formula (1) shows).
-
To ensure the highest input-output benefit of mobile edge servers, the number of deployed edge servers must be conformed to the limit of optimal benefit quantity of deployed edge servers, and the total load on each edge server does not exceed a predefined maximum value, i.e.,$$\begin{aligned} T_s\le T_{s}^{opt}, T_{s}\le arg max 2t_{s} \end{aligned}$$(12)
Genetic algorithm
Experiment and analysis
Data set and experimental settings
Base Station ID | Quantity of Terminals | Load /min |
---|---|---|
12 | 354 | 24958 |
400 | 1242 | 61972 |
40 | 1824 | 2571744 |
664 | 151 | 190730 |
328 | 108 | 140960 |
6023 | 261 | 14026 |
Evaluation metric
Load balancing
Communication delay
Deployment rate
Baseline methods
-
MIP [32]: The mixed integer programming (MIP) method utilizes binary decision variables to indicate whether to allocate mobile communication base stations to edge servers, and the location of each base station is a candidate for edge server deployment. For each candidate value, a tag is given to consider both distance and workload to determine whether it is suitable for deploying edge servers.
-
ESPHA [44]: Firstly, it combines the K-means algorithm and the ant colony algorithm to introduce a pheromone feedback mechanism in the deployment of the edge server. And then, it sets the taboo table in the ant colony algorithm to accelerate the algorithms’ convergence. At length, the ameliorated heuristic algorithm is utilized to gain the optimal deployment scheme of edge servers.
-
SA: It simulates the annealing process of solid materials in a physical scenario. Then, it takes a relatively high initial temperature as the starting state and undergoes a temperature parameter reduction process. At the same time, it employs the joint probability mutation characteristic to randomly search for the global optimal solution of the objective function.
-
K-means: First, it randomly assigns K cluster centers in the mobile communication base station cluster, and divides the base stations to be classified into each cluster according to the nearest neighbor principle. Then it calculates the centroid of each cluster iteratively according to average medium until the shift distance of the cluster core is less than the threshold. The determined centroid situation is the deployment position of the edge server.
-
Top-K: The top K mobile communication base stations having the top workload are picked as the deployment locations of the edge servers, and the base stations are allocated to the neighboring edge servers according to the principle of proximity.
-
Random: K edge servers are randomly placed in the mobile communication base station cluster, and the base stations are apportioned to adjacent edge servers according to the principle of proximity.
Results and analysis
-
The relationship between cost and benefit should be considered during the investment in infrastructure such as mobile communication base stations, edge servers, and cloud service centers. Although the more infrastructure investment, the better technical indicators, but the corresponding cost of investment is higher. If the investment is too high, the rationality of the investment is debatable compared to its return. So, we specifically design the calculation method of the optimal benefit quantity. This is one of the research motivations in this paper. And none of the baseline approaches in this paper, including ESPHA, considers the optimal benefit quantity of edge server deployment.
-
Optimal benefit, communication delay between edge server and mobile communication base station, load balancing value of edge server all need to compromise with each other, to gain the optimal deployment scheme, but difficult to achieve the optimum for all three simultaneously.
The number of base stations | 300 | 600 | 900 | 1200 | 1500 |
---|---|---|---|---|---|
HE-GA | 3.9502 | 5.9305 | 6.5572 | 6.6250 | 5.4217 |
MIP | 4.1954 | 7.4327 | 6.8487 | 6.8657 | 5.7346 |
ESPHA | 4.2046 | 7.3610 | 6.6979 | 6.7329 | 5.6321 |
SA | 6.3521 | 7.9482 | 6.9611 | 7.1527 | 6.2057 |
K-means | 4.2573 | 7.0673 | 6.4209 | 6.7311 | 5.8539 |
Top-K | 6.2476 | 7.7591 | 9.2102 | 12.7001 | 10.8571 |
Random | 6.4843 | 11.0005 | 10.4465 | 12.2637 | 9.6427 |
The number of base stations | 1800 | 2100 | 2400 | 2700 | 3000 |
---|---|---|---|---|---|
HE-GA | 5.5255 | 6.5455 | 5.4572 | 5.4357 | 5.3217 |
MIP | 5.7244 | 6.9515 | 5.6781 | 5.6014 | 5.5346 |
ESPHA | 5.6400 | 6.6672 | 5.5741 | 5.5120 | 5.4879 |
SA | 6.2470 | 7.3143 | 6.3521 | 6.4163 | 7.1763 |
K-means | 5.8417 | 6.6875 | 5.7186 | 5.6749 | 5.5741 |
Top-K | 9.0193 | 9.7727 | 9.0147 | 8.7964 | 8.4104 |
Random | 8.8271 | 11.5267 | 8.5687 | 8.2146 | 8.0973 |
The number of base stations | 300 | 600 | 900 | 1200 | 1500 |
---|---|---|---|---|---|
HE-GA | 1.8255 | 5.7435 | 7.0572 | 8.2374 | 7.5217 |
MIP | 1.9244 | 6.9741 | 7.4578 | 8.5471 | 8.4346 |
ESPHA | 2.2162 | 6.1678 | 7.5127 | 8.3439 | 7.7398 |
SA | 2.0086 | 7.1951 | 8.3902 | 9.9573 | 10.4094 |
K-means | 2.1568 | 8.4070 | 10.4571 | 13.2346 | 13.1050 |
Top-K | 1.1945 | 1.5696 | 1.4604 | 1.5138 | 1.4520 |
Random | 2.2442 | 2.4327 | 2.6711 | 2.5928 | 2.4019 |
The number of base stations | 1800 | 2100 | 2400 | 2700 | 3000 |
---|---|---|---|---|---|
HE-GA | 5.5255 | 6.5455 | 5.4572 | 5.4357 | 5.3217 |
MIP | 5.7244 | 6.9515 | 5.6781 | 5.6014 | 5.5346 |
ESPHA | 5.6400 | 6.6672 | 5.5741 | 5.5120 | 5.4879 |
SA | 6.2470 | 7.3143 | 6.3521 | 6.4163 | 7.1763 |
K-means | 5.8417 | 6.6875 | 5.7186 | 5.6749 | 5.5741 |
Top-K | 9.0193 | 9.7727 | 9.0147 | 8.7964 | 8.4104 |
Random | 8.8271 | 11.5267 | 8.5687 | 8.2146 | 8.0973 |
Number of Edge Servers | 100 | 200 | 300 | 400 | 500 |
---|---|---|---|---|---|
HE-GA | 8.9874 | 7.6874 | 5.3217 | 4.2174 | 3.4871 |
MIP | 10.2587 | 8.5471 | 5.5346 | 4.8574 | 4.1789 |
ESPHA | 9.8741 | 8.0665 | 5.4879 | 4.4674 | 3.8967 |
SA | 10.6269 | 9.3239 | 7.1763 | 5.4677 | 4.9711 |
K-means | 11.2413 | 7.5741 | 5.5864 | 5.0147 | 4.4893 |
Top-K | 14.2146 | 10.6082 | 8.4104 | 6.0736 | 5.6747 |
Random | 15.6712 | 13.8441 | 8.0973 | 6.4476 | 5.7410 |
Number of Edge Servers | 100 | 200 | 300 | 400 | 500 |
---|---|---|---|---|---|
HE-GA | 16.3853 | 13.2547 | 7.7698 | 6.6250 | 5.0214 |
MIP | 18.3746 | 15.3247 | 8.3210 | 6.8657 | 5.5698 |
ESPHA | 17.4789 | 14.4226 | 7.9874 | 6.7329 | 5.4593 |
SA | 19.3569 | 16.2525 | 9.5626 | 7.2916 | 6.5046 |
K-means | 25.7821 | 20.2214 | 16.8412 | 17.6984 | 14.2373 |
Top-K | 8.3698 | 4.2843 | 1.5782 | 1.2473 | 1.0247 |
Random | 2.8741 | 2.3659 | 1.9874 | 1.4789 | 1.2589 |
Analysis of the results of different quantity of base stations under the optimal benefit quantity limit
-
In terms of communication delay, the HE-GA is the best. When the number of base stations is 3000, the communication delay of HE-GA is respectively 3.12%, 4%, 34.85%, 4.74%, 52.16%, and 58.04%, which is lower than those of ESPHA, MIP, SA, K-means, Random, and Top-K. The result indicates that under the constraint of optimizing the benefits, HE-GA achieves better communication delay compared to the baselines. Both Random and Top-K have high communication delay with significant fluctuations, and their overall performance is similar. However, when the number of base stations is 3000, the communication delay of Top-K more than that of Random by 3.87%. It is because that Shanghai, as an international metropolis, has a high population density and uneven distribution. Using the Top-K algorithm will give priority to base stations with a higher load, but ignores the load balance, which leads to higher communication delay.
-
In terms of the standard deviation of edge server load, Random and Top-k perform best. When the number of base stations is 3000, the load standard deviation of HE-GA is respectively higher than those of Random and Top-K by 390.95%, 492.32%. At this point, the load standard deviation of Top-K is 25.93%, which is lower than that of Random. Because the two methods give priority to process base stations with a higher load, especially Top-K, so that the load gap of edge server is not large. In this case, the load standard deviation of HE-GA is respectively lower than those of ESPHA, MIP, SA, and K-means by 2.8%, 7.09%, 23.07%, and 116.75%. This result illustrates that under the constraints of optimal benefit, HE-GA achieves a better load standard deviation of edge server compared to the mainstream approach. Although Random and Top-K perform better in terms of load standard deviation, they do not consider optimal benefit and has poor communication delay performance. Therefore, their overall performance is average. K-means clusters the base stations with similar characteristics so that the base stations with similar load are more concentrated, that is to say, the base stations with the high load and low load are all more concentrated. However, the population density of Shanghai is too large and uneven, so the clustering effect is not ideal. Therefore, the K-means performs poorly in the comparative experiment of the load standard deviation of the edge server.
-
Overall, HE-GA achieves better performance under the constraint of optimal benefit. The baselines, such as ESPHA, MIP, SA, K-means, Random, and Top-K, do not consider the constraint of optimal benefit, thus failing to effectively balance the conflicting interests of network operators and end-users. HE-GA considers optimal benefit, communication delay between edge servers and mobile communication base stations, and balances loads of edge servers simultaneously, thereby obtaining the overall optimal deployment solution.
Analysis of the results of different edge server numbers under the same quantity of base stations
-
In the light of communication delay, the performance of the HE-GA is still the best on the whole. When the number of edge servers is 500, HE-GA achieves the reductions of communication latency by 11.75%, 19.84%, 42.56%, 28.74%, 64.64%, and 62.73% compared to ESPHA, MIP, SA, K-means, Random, and Top-K, respectively. This result indicates that even without the constraint of optimal benefits, HE-GA still achieves better performance in terms of communication latency compared to the baselines. Among all the methods, the communication delays of Random and Top-k decrease the fastest by the increasing quantity of edge servers deployed. Because newly added edge servers greatly improve the imbalance of edge server deployment caused by the above two methods, thus greatly reducing the communication delay, but its performance is still lower than the HE-GA method. It is worth mentioning that before the quantity of edge servers reaches 300, the communication delay of edge servers for all deployment methods decreases significantly, and the decrease is higher than that of the process while the quantity of edge servers increases from 300 to 500.
-
In the light of loads’ standard deviation of edge servers, Random and Top-K still perform the best. When the number of edge servers is 500, the load standard deviation of HE-GA more than those of Random and Top-K by 398.87%, 490.04%, respectively. At this time, the load standard deviation of HE-GA is lower than ESPHA, MIP, SA, and K-means by 8.72%, 10.92%, 29.54%, and 183.53%, respectively. This result indicates that without the constraint of optimal benefits, HE-GA also achieves better load standard deviation of edge server compared to mainstream methods. It is also worth that in process of raising the quantity of edge servers from 100 to 300, except for Random, the loads’ standard deviation of other deployment methods decreased significantly, and the decrease is higher than that of the process of raising the quantity of edge servers from 300 to 500.