Locality sensitive hashing-aware fruit fly optimization algorithm and its application in edge server placement – Journal of Cloud Computing

LSHFOA

In order to comprehensively analyze the experimental performance of the algorithm LSHFOA in this paper, comparison tests with IFFO and CFOA on the basis of Fig. 6 are performed, and the experimental results are shown in the following figures.

Performance of the algorithm under F1 function

Performance of the algorithm under F2 function

Performance of the algorithm under F3 function

Performance of the algorithm under F4 function

Performance of the algorithm under F5 function

Performance of the algorithm under F6 function

Performance of the algorithm under F7 function

Performance of the algorithm under F8 function

Figure 7 represents the experimental results of the single-dimensional single-peak function F1. Since the single-dimensional single-peak function is relatively simple, a set of classical functions was used randomly to test the performance of the algorithm. As can be seen from the figure, the algorithm in this paper is significantly better than IFFO in both the optimization accuracy and optimization efficiency. Compared to CFOA, the optimization efficiency is slightly lower while the final experimental results are similar. The experimental results of this group show that the algorithm of this paper also has good experimental results under the one-dimensional single-peak function test.

Figures 8 and 9 represent benchmark functions F2 and F3, i.e., single-dimensional multi-peak function tests. The experimental accuracy and efficiency of LSHFOA are much better than CFOA and slightly better than IFFO. While the experimental accuracy and efficiency of this algorithm are significantly better than CFOA and IFFO. Meanwhile, it can be seen from the changing trend of each algorithm in Figs. 7 and 8 that the fruit fly optimization algorithm has a strong dependence on the initial position of the population, i.e., after the initial position is determined, the algorithm’s optimization results are limited. However, it can be slightly seen from Fig. 9 that the algorithm in this paper can reduce the influence of the initial position on the FOA optimization results, i.e., the optimization results will fluctuate slightly which will suitable to find better results. Such fluctuations are more obvious in Figs. 11 and 12, and the impact of such fluctuations on the experimental accuracy is similar.

Figures 10 and 11 represent the multidimensional multi-peak test functions (F4 and F5). from Fig. 10, it can be seen that with the increase of iterations, the algorithm in this paper can rapidly reduce the experimental search accuracy. The benchmark function value rapidly decreases and the results are significantly smaller than CFOA and IFFO. Therefore, for the benchmark function F4, the algorithm in this paper has better experimental results with convergence speed. From Fig. 10, it can be seen that in the multi-dimensional multi-peak test function, although the initial Fitness value is larger than LSHFOA, the algorithm in this paper can quickly approach the optimal solution through the local sensitive hashing mechanism, so as to achieve similar optimization-seeking accuracy and optimization-seeking efficiency comparing to algorithms IFFO and CFOA. In summary, it can be seen from Figs. 10 and 11 that with the increase of iterations, the algorithm in this paper has excellent optimization-seeking accuracy and convergence speed in the multidimensional single-peak function test.

Figures 12 and 13 represent the multi-dimensional multi-peak test functions (test functions F6 and F7). Overall, it can be seen from the experimental results in Figs. 12 and 13 that the proposed algorithm in this paper can achieve significant advantages in the multi-dimensional multi-peak situation compared with the CFOA and IFFO. For example, as can be seen from Fig. 11, even though the initial population position LSHFOA is slightly worse than that of CFOA and IFFO, with the increase in the number of iterations, the optimization accuracy of this algorithm is gradually improved. After 50 iterations, the experimental results of this algorithm significantly outperform the comparative algorithms CFOA and IFFO. Therefore, for the benchmark function F5, the accuracy and efficiency of the experimental results are significantly better than the classical algorithms CFOA and IFFO, although the initial position of the algorithm is slightly worse. As can be seen from Fig. 13, for benchmark function F7, the algorithm in this paper outperforms CFOA and IFFO in terms of optimization results close to 0 (the most value of the function in the domain). In terms of the optimization efficiency, the accuracy of the feasible solution of this paper is higher than that of the comparison algorithm in about 20 iterations, which indicates that LSHFOA can achieve excellent optimization results and efficiency in high-dimensional multi-peak functions. In summary, for the multi-dimensional multi-peak problem, the algorithm in this paper can get better results. It can be seen that LSHFOA is more suitable for solving the high-dimensional multi-peak optimization problem.

Figure 13 represents the combination function of two- dimensional variables, and it can be seen from the figure that although the algorithm in this paper has a slightly worse optimization accuracy than IFFO, it significantly outperforms CFOA, that is LSHFOA can be applied in such problems. Combining the above several test functions, it can be seen that the algorithm in this paper can achieve significantly better experimental results than CFOA and IFFO in multi-peak situations, especially in high-dimensional multi-peak situations.

LSHFOA-ESP

To extensively evaluate LSHFOA-ESP’s performance, we simulate a set of ESP scenarios in the experiments. We employ a Windows machine equipped with an Intel Core i7-7500 processor, and 16G RAM to perform the experiments. At the same time, a real-world dataset is applied to conduct the experiments. It has been widely used in edge computing environments [2, 6, 22, 26, 27]. Overall, this dataset includes a large number of real-world users and base stations in Melbourne Metropolis, Australia, including the geographical information of users and base stations, and the coverage of base stations.

Performance Metrics. Two metrics are employed to measure the effectiveness and efficiency of LSHFOA-ESP, including 1) the number of served users, and 2) the time consumption.

Comparison Approaches. In this paper, to evaluate the performance comprehensively, two state-of-the-art approaches and one baseline approach are employed as comparison approaches in this paper.

RESP [6]: This is a representative approach proposed very recently. It makes the first attempt to solve the robustness-oriented edge server placement problem, with the aim to maximize the overall robustness.

CRESP [7]: This approach is an extension of, which focuses on the tradeoff between robustness and coverage. This is because maximizing the overall robustness only usually leads to a decrease in user coverage.

FOA-ESP: This is a baseline approach that tries to solve the edge server placement problem by using the classical FOA only [12, 14].

Parameter Settings. Similar to many studies in edge computing environment [2, 6, 7, 22, 26,27,28,29], in each experiment, n base stations are randomly selected from the dataset and c users are selected from the data set [2, 22, 27] randomly as well, where base stations include the geographical locations and the coverage radiuses, users include the geographical locations. Then, based on those geographical locations of base stations and users and the radiuses of base stations, the user-base station accessibilities matrix can be built. Next, to test the performance of LSHFOA-ESP comprehensively, three parameters are varied, including 1) number of base stations (n); 2) number of edge servers (m) and 3) number of users (c). Accordingly, the experimental settings of those parameters are summarized in Table 3. LSHFOA-ESP iterates 300 times before giving out the solution. The number of fruit flies in each iteration is 50. Each time we vary one parameter and repeat the experiment 100 times, then the results are averaged.

Number of Served Users (Set 1)

Number of Served Users (Set 2)

Number of Served Users (Set 3)

Effectiveness Generally, Figs. 15, 16 and 17 show the effectiveness, measured by the number of served users, of all the approaches in Set 1, Set 2 and Set 3, respectively. From those figures, it is easy to see that the proposed approach, LSHFOA-ESP can serve the most users compared to other approaches. First, LSHFOA-ESP can find a solution to cover the most users, which is significantly greater than the classic FOA and its application to the ESP problem. This is because, as stated above, LSHFOA, as an extension of FOA, is designed to overcome the difficulties of FOA and aims to find the optimal solution. Thus, LSHFOA-ESP’s performance is better than FOA-ESP’s, by 15.32%. Second, RESP serves the least number of users. The background reason is straightforward. That is, RESP is designed to maximize the overall robustness of edge servers, i.e., maximizing the overall served times of users instead of serving more users. Thus, edge servers are usually driven to be placed on a small group of base stations that have covered the greatest number of users. In this way, the overall robustness will be maximized. Obviously, LSHFOA-ESP outperforms RESP significantly, by 25.48%. Lastly, as an extension of RESP, CRESP is designed to balance the overall robustness and the number of served users. As a result, its number of served users achieves the second-highest performance. But it is still lower than LSHFOA-ESP by 8.32%.

Specifically, Fig. 15 shows that when the number of base stations increases in Set 1, the number of served users achieved by all the four approaches decreases. The background reason is analyzed as follows. As shown in Table 3, when the number of base stations varies, the number of edge servers and the number of users are fixed. In this case, a larger number of base stations will lead to a decrease in the number of users covered by each base station on averagely. As a consequence, selecting the same number of base stations, i.e., placing a fixed number of edge servers, usually results in a lower number of served users. But the results, as shown in Fig. 14, are gradually stabilized. This is because, the locations of base stations and users come from a real-world, and they are fixed. In this case, when nearly all the base stations have been selected, the geographical distributions of users are unchanged. Thus, the number of served users decreases first and then becomes stabilized. Figure 16 demonstrates that LSHFOA-ESP is capable of serving the most edge users when the number of edge servers varies. Compared to FOA-ESP, RESP and CRESP, LSHFOA-ESP outperforms them with significant advantages. Especially, when more and more edge servers are placed in a specific edge computing environment, the performance gaps between LSHFOA-ESP and FOA-ESP, RESP and CRESP increase gradually. This is because, given a fixed number of base stations, placing more edge servers will cover more base stations to serve more users. When the number of users increases in Set 3, the number of served users increases in all approaches, as shown in Fig. 17 The underlay reason is similar to that in Set 2. That is, more users are extracted from the real-world data, and each base station will cover more users in general. Thus, placing a fixed number of edge servers usually leads to an increase in the overall number of served users, as shown in Fig. 16. As shown in Fig. 16, our approach, LSHFOA-ESP can still find a solution to serve the maximum number of users. Therefore, as demonstrated in Figs. 15, 16 and 17, the proposed approach, LSHFOA-ESP can be used to solve the edge server placement effectively.

Efficiency Figures 18, 19 and 20 demonstrate the time consumption of all approaches in Set 1, Set 2 and Set 3. In general, we can find that LSHFOA-ESP takes much less time than RESP and CRESP to find the solutions, and is slightly higher than FOA-ESP. Those phenomena are acceptable. First, as an improved FOA approach, LSHFOA-ESP takes a slightly higher time to find a solution. It is straightforward. But as shown in Figs. 15, 16 and 17, LSHFOA-ESP can serve much more users than FOA-ESP. Second, LSHFOA-ESP takes a smaller time to find a better solution than RESP and CRESP, as shown in Figs. 15, 16 and 17 and Figs. 18, 19 and 20. This shows that LSHFOA-ESP can be used to solve the edge server placement problem efficiently. Last, in terms of the time consumption of RESP and CRESP, CRESP is an extension of RESP by considering more metrics, such as robustness and user coverage. Thus, CRESP takes more time than RESP, obviously, and achieves a better result than RESP, as well, as shown in Figs. 15, 16 and 17.

Specifically, as shown in Figs. 18, 19 and 20, we can find that LSHFOA-ESP’s time consumption increases as long as the number of edge servers or the number of users increases. The reason is straightforward – a larger number of edge servers means a longer coding of each fruit fly, as shown in Fig. 5, and a larger number of users means the more complicated fitness function calculations of each fruit fly. However, in Set 1, the increase in the number of base stations does not significantly affect LSHFOA-ESP’s time consumption, as shown in Fig. 18. This is because, for the coding of each fruit fly, i.e., Fig. 5, each code element will select one of the base stations only without traversing the entire base stations. Thus, the time consumption of Set 1 fluctuate as the number of base stations varies. As shown in Figs. 18, 19 and 20, the increase in time consumption usually follows a linear trend when the number of edge servers and the number of users increase. This indicates the LSHFOA-ESP can handle the large-scale ESP problem efficiently, i.e., LSHFOA-ESP can converge quickly in large-scale ESP scenarios.

Overall Time Consumption (Set 1)

Overall Time Consumption (Set 2)

Overall Time Consumption (Set 3)