Computers, Materials & Continua DOI:10.32604/cmc.2021.015730 | ![]() |
Article |
Hybrid Metamodeling/Metaheuristic Assisted Multi-Transmitters Placement Planning
1Wireless Communication Ecosystem Research Unit, Chulalongkorn University, Bangkok, 10330, Thailand
2Department of Electrical Engineering, University of Central Punjab, Lahore, Pakistan
3School of Engineering, University of Glasgow, Glasgow, G12 8QQ, UK
4Head-of-Innovation-and-Entrepreneurship-Center, College of Engineering, Taif University, Taif, KSA
5Department of Electrical and Computer Engineering, King Mongkut University of Technology North Bangkok, Bangkok, Thailand
6Department of Electrical Engineering, Siam University, Bangkok, Thailand
*Corresponding Author: Lunchakorn Wuttisittikulkij. Email: lunchakorn.w@chula.ac.th
Received: 04 December 2020; Accepted: 13 January 2021
Abstract: With every passing day, the demand for data traffic is increasing, and this urges the research community not only to look for an alternating spectrum for communication but also urges radio frequency planners to use the existing spectrum efficiently. Cell sizes are shrinking with every upcoming communication generation, which makes base station placement planning even more complex and cumbersome. In order to make the next-generation cost-effective, it is important to design a network in such a way that it utilizes the minimum number of base stations while ensuring seamless coverage and quality of service. This paper aims at the development of a new simulation-based optimization approach using a hybrid metaheuristic and metamodel applied in a novel mathematical formulation of the multi-transmitter placement planning (MTPP) problem. We first develop a new mathematical programming model for MTPP that is flexible to design the locations for any number of transmitters. To solve this constrained optimization problem, we propose a hybrid approach using the radial basis function (RBF) metamodel to assist the particle swarm optimizer (PSO) by mitigating the associated computational burden of the optimization procedure. We evaluate the effectiveness and applicability of the proposed algorithm by simulating the MTPP model with two, three, four and five transmitters and estimating the Pareto front for optimal locations of transmitters. The quantitative results show that almost maximum signal coverage can be obtained with four transmitters; thus, it is not a wise idea to use higher number of transmitters in the model. Furthermore, the limitations and future works are discussed.
Keywords: Simulation–optimization; radial basis function; particle swarm optimization; multi-transmitter placement
The demands for data traffic have been increasing at an exponential rate over the last decade, and this trend is expected to continue in the future. Billions of humans and devices require seamless wireless communication in indoor and outdoor environments supporting higher data rates, and this demand has resulted in the evolution of heterogeneous networks (HetNets) with small cell size [1]. The solution to this is the deployment of more stationary or mobile base stations (BS) to meet the ever-increasing traffic demand [2]. With the rapid advancement in solid-state lighting (SSL) and microelectromechanical systems, the research community can develop sensors that have the capability of sensing, computation and/or decision-making [3].
Legacy networks have a huge cell size; however, in next-generation networks, the cell size is dramatically reduced, which creates a major challenge for telecommunication network operators to scrupulously plan their complex networks. Networks of the fifth-generation (5G) and beyond necessitate the massive deployment of BS. If these deployments are unplanned, this can result in a huge cost, higher interference levels, and overall straitened network performance. It is therefore important to perform BS placement planning in such a manner that requires the least number of transmitters to accomplish the desired coverage ratio while maximizing the average received power in conjunction with the quality of service (QoS) [4]. Therefore, BS placement in a mobile network is crucial to effectively use the resources in next-generation networks, thus reducing the infrastructure cost. One of the challenges associated with the optimal placement of BS is the computational complexity of transmitter location optimization in contrast with the manual transmitter placement through site surveying [5].
In various applications of WSNs, the coverage rate is always considered to be an essential indicator because it determines the monitoring capability for the target area [6]. Maximizing the coverage of the monitoring area has received a great deal of attention in the literature. Searching for the optimal node deployment scheme is a difficult task, especially for large-scale sensor networks [7]. The multi-transmitter placement planning problem (MTPP) of guaranteeing coverage while meeting some application requirements quite often gives rise to NP-hard optimization problems [6,8]. In much of the literature, most of the proposed algorithms for the optimal placement problem have used metaheuristics. Some studies have applied an ant colony algorithm (ACO) for WSN problems [9–12]. This algorithm follows the behavior of a real ant colony; the more ants follow a trail, the more attractive the trail is. The powerful global search capability of particle swarm optimization (PSO) has been attractive for WSN problems in the literature [13–16]. The grey wolf optimizer (GWO) is another favorable metaheuristic that has recently been used in WSN coverage optimization and beyond [6,7,17].
Metamodeling techniques have been used to avoid intensive computational and numerical simulation models, which might squander time and resources when estimating the model’s parameters. The general overview of a metamodel is illustrated in Fig. 1. Different metamodels have been developed in engineering practice, such as the radial basis function (RBF), support vector regression (SVM), Kriging (also known as the Gaussian process), polynomial regression, and multivariate adaptive regression splines [18–20]. Today, the Kriging surrogate has been used as a widespread global approximation technique that is applied widely in engineering design problems [21–28]. However, to the best of our knowledge, there is a lack of studies using the application of approximation methods (e.g., metamodels) in WSNs and MTPP particularly combined with metaheuristics. In, the Kriging metamodel was used as a localized method to interpolate a spatial phenomenon inside a coverage hole using available nodal data; the authors claimed that it is not always possible to maintain exhaustive coverage in large-scale WSNs, and hence coverage strategies based solely on the deployment of new nodes may fail. The problem of distributed estimation in a WSN with an unknown observation noise distribution was investigated in [29] by the application of a Kriging metamodel, where each sensor only sends quantized data to a fusion center. The authors in [29] applied the Kriging interpolation technique to accurately predict the temperature at uncovered areas and estimate positions of heat sources in WSNs. The RBF neural network was accurately used in [30] for localization with noisy distance measurements in WSNs. A data fusion method for WSNs based on RBF neural networks was presented in [31]. In [32], RBF neural networks were used as a new application of neurocomputing for data approximation and classification to process data in WSNs. A new multilayer neural network model, called the artificial synaptic network, was designed and implemented for single sensor localization with time-of-arrival measurements in [33]. In [34], the authors analyzed an RBF network for the development of a localization framework in WSNs; they claimed that an RBF-based localization framework can be analyzed with a faster speed of convergence and low cost of computation.
Figure 1: The viewpoint of metamodel and relationship with a simulation model
In this study, we develop a new mathematical programming model for the MTPP problem. To solve this mathematical optimization model, we propose a new approach combining the PSO metaheuristic and RBF metamodel applied in the practice of simulation–optimization for wireless signal coverage in the MTPP problem. Among metaheuristic techniques, PSO has attracted wide attention in engineering design problems due to its algorithmic simplicity and powerful search performance [35,36]. Here, we assist the PSO metaheuristic using a radial basis function (RBF) metamodel in an optimization procedure to alleviate the associated computational burden. RBF has become a widely accepted metamodel for deterministic and stochastic simulation metamodeling due to its promising results, particularly in solving complex simulation-based optimization problems [37–40].
The major contributions of our research can be summarized as follows:
i) A new mathematical programming model is developed in this paper for coverage optimization in a multi-transmitter placement planning problem. This model has flexibility in the design of optimal placements for any number of transmitters (not limited to an exact number of transmitters in the optimization model).
ii) To solve this new optimization model, this paper also proposes a new hybrid technique using a combination of an RBF metamodel and PSO optimizer. The proposed algorithm can search the whole design space continuously with no need to run a simulation model for all investigated locations (thus incurring a low computational cost).
The rest of this paper is organized as follows. Section 2 provides the preliminaries and follows the algorithmic framework of the proposed algorithm which has been developed for the MTPP problem in Section 3. In Section 4, a numerical case study is presented to show the applicability and effectiveness of the proposed algorithm in the simulation–optimization of the MTPP problem. Finally, this paper is concluded in Section 5.
The RBF is a kind of neural network that employs RBF as a transfer function (see Fig. 2) and consists of an input layer, a hidden radial basis layer, and an output linear layer [41]. The RBF employs a linear combination of independent symmetric functions based on Euclidean distances to compute the approximation function of response.
Figure 2: Radial basis function neural network
The simple mathematical forms of RBF can be expressed as
where wi,
where
where f(xi) is the exact output from the original model for the ith sample points and
2.2 Particle Swarm Optimization
The canonical PSO algorithm, which simulates the swarm behaviors of social animals, such as bird flocking or fish schooling, was proposed in [43]. The PSO algorithm begins by initializing the population. The second step is the calculation of the fitness values of each particle, followed by updating individual and global bests; later, the velocities and positions of the particles are updated. The second to fourth steps are repeated until the termination condition is satisfied [44,45]. The PSO algorithm is formulated as follows [43–45]:
where w is inertia weight factor,
Here, we explain the algorithmic framework of the proposed simulation-based optimization technique based on a hybrid RBF metamodel and PSO metaheuristic. Fig. 3 represents the procedure of the proposed hybrid optimization algorithm in this study along with the construction of the simulation model and analysis of data. Furthermore, the proposed hybrid optimization algorithm is implemented with the following steps:
Input: Simulation of the input/output (I/O) set of data. Here, for the transmitter localization problem, the input data set includes (X, Y) locations, and the output data set includes the average signal coverage (ASC) regarding each location.
Output: Estimation of Pareto frontier including a set of optimal locations for multiple transmitters.
Step 1: Fit RBF metamodel over the I/O data set.
Step 2: Construct the objective function of the optimization model.
Note: In the current paper, in the MTPP problem, we consider the maximization of ASC as an objective function of the model. However, to smooth the amount of signal overlap by transmitters, we control the Euclidean distances between every pair of transmitters in a set of constraints. Let
Subject to:
where
Step 3: Run the PSO optimizer for the constructed optimization model in the previous step and obtain the optimal result.
Step 4: Repeat the three previous steps for different values of
Figure 3: The simulation-based optimization method in the current study including the procedure of proposed hybrid RBF/PSO algorithm in conjunction with simulation model and data analyzing
4 Simulation-Based Optimization of MTPP: Case Study
In this section, the applicability of the proposed algorithm in the MTPP problem is studied to obtain the optimal locations of each transmitter to maximize the amount of signal coverage. To continue, first, the application of the proposed algorithm using the hybrid RBF metamodel and PSO metaheuristic integrated by mathematical programming in the current MTPP optimization problem is explained; then, the obtained results are discussed in detail.
In this work, we used a ray-tracing simulator developed in Python. We created a simulation model that simulated the environment of an office room to implement the MTPP problem. The obstacles in the room were modeled according to the layout of the office equipment by creating a polygon of each object and placing it in various positions in the room. The calculations of the coverage area assumed that the signal propagation was omnidirectional, and the transmitter could transmit the signal in two dimensions. To evaluate the coverage rate in a two-dimensional area, we divided the entire monitoring region into
To reduce the number of simulation runs and produced images, we decussated odd locations (odd X and Y positions) in the two-dimension design area to set the transmitter; thus, only coverage images were produced for even pixels, meaning that we produced 12,544 images. Then, we analyzed the set of images gained from the simulation model to obtain the ASC for each relevant X and Y location (i.e., in the following, this computed dataset is used as the set of I/O data for the optimization procedure). We used the Matlab
Figure 4: Three-dimensions scatter plot for different (X, Y) transmitter locations and relevant average signal coverage
Figure 5: Contour plot for average coverage using one transmitter in all locations of design space. Obstacles areas show in dark blue color with zero signal coverage
Figure 6: Maximum signal coverage in the model with one transmitter is obtained in X = 26, Y = 0 with ASC = 0.4355. Black areas include obstacles and not covered by transmitter
This work aimed to develop a new method to investigate the optimal locations of multiple transmitters. However, in the current instance, we applied the proposed algorithm. Note that the proposed algorithm is flexible for any number of transmitters, and we are not limited to the number of transmitters in a model. Here, to show the applicability and effectiveness of the proposed algorithm, the MTPP problem was investigated for two, three, four, and five transmitters, respectively. For this purpose, we first constructed the RBF metamodel over the set of I/O data obtained from the simulation model. We used the “newrbe” Matlab
Figure 7: Surface plot of fitted RBF metamodel (a) and scatter plot for mean square error of constructed RBF prediction (b)
We constructed the mathematical programming model for the MTPP problem (see Eq. (5) till Eq. (7)) with two, three, four, and five transmitters (K = 2, 3, 4, 5) in a model, respectively. The design ranges for both the X axis and Y axis were
Objective function:
Constraints:
where di, j shows the Euclidean distance between transmitters (e.g.,
In the model with two transmitters (K = 2), we applied the proposed algorithm by integrating the RBF metamodel constructed over a set of I/O data (i.e., I/O data obtained from the simulation model) and PSO optimizer. The optimization results in the model with two transmitters for three different values of
Table 1: The optimal locations and relevant overall signal coverage for two-transmitters localization model
Figure 8: Optimal locations (i.e., are shown by triangle marker) and overall signal coverage of two transmitters in MTL problem for
Next, we constructed the optimization procedure based on the proposed hybrid RBF and PSO algorithm for a case with three transmitters in the model. The obtained optimization results are shown in Tab. 2 for three different
Table 2: The optimal locations and relevant overall signal coverage for three-transmitters localization model
Figure 9: Optimal locations (i.e., are shown by triangle marker) and overall signal coverage of three transmitters in MTL problem for
Table 3: The optimal locations and relevant overall signal coverage for four-transmitters localization model
Figure 10: Optimal locations (i.e., are shown by triangle marker) and overall signal coverage of four transmitters in MTL problem for
Besides, the application of the proposed algorithm was used for the MTPP problem with five transmitters. Optimal locations and relevant obtained results are provided in Tab. 4 and schematically are shown in Fig. 11. The obtained results for the optimization of a model with five transmitters revealed that the highest signal coverage was obtained in
Table 4: The optimal locations and relevant overall signal coverage for five-transmitters localization model
Figure 11: Optimal locations (i.e., are shown by triangle marker) and overall signal coverage of five transmitters in MTL problem for
Finally, we compared all obtained results based on
Figure 12: Average signal coverage for different number of transmitters in the model based on three different
Here, we developed a new mathematical programming model for the MTPP problem. This model has flexibility in terms of the design of optimal placements for any number of transmitters (not limited to an exact number of transmitters in the optimization model). To solve this new optimization model, we also propose a new hybrid technique using a combination of the RBF metamodel and PSO optimizer. In comparison with common model-based optimization techniques, two main advantages of the proposed hybrid algorithm are as follows:
i) The proposed algorithm can search in the whole design space continuously. In other words, in the current instance in this paper, we are not restricted to investigating optimal locations only by discrete areas when searching among the 12,544 locations (as aforementioned, the signal coverage for 12,544 locations in the two-dimensional design space is modeled and computed through the simulation model); thus, any area within these 12,544 locations can be investigated as well because we APPLY the interpolation method (the well-known RBF metamodel) that can be trained on the whole design space. In contrast, the model-based optimization techniques are limited to searching only within a limited number of locations.
ii) In the current paper, for the MTPP problem, one way to tackle the previous shortcomings in the case of using model-based techniques for coverage optimization is that the number of locations modeled in the simulation can be increased. However, the simulation model needs to run with a larger number of locations (more than 12,544 locations in the current study) and compute the signal coverage for locations with smaller distances. However, this procedure can increase the computational cost of optimization significantly.
There are two main limitations in the current study, as stated below:
i) The proposed method employs the RBF metamodel to train the black-box simulation model. Therefore, the approximate errors cannot be ignored when solving inequality-constrained simulation-based optimization problems. A challenge for optimization under restricted budgets (limited number of sample points) will be to find the right degree of approximation (smoothing factor) from only a relatively few samples [52]. Other metamodels, such as Kriging, polynomial regression, and neural networks, can be used and compared with the RBF metamodel used in the current study for the MTPP problem.
ii) In this study, we use the common death penalty method to deal with inequality constraints in the optimization model. However, other constraint handling methods [50] can be used and compared with the results of this study.
Simulation-based optimization is a viable solution for solving complex real-world problems, such as the base station placement problem in wireless sensor networks. The multi-transmitter placement planning problem of guaranteeing coverage while meeting some application requirements quite often gives rise to NP-hard optimization problems. In this paper, we developed a new mathematical programming model to handle the design of optimal locations for any number of transmitters in a two-dimensional design space. To solve the mentioned MTPP model, we proposed a new hybrid method combining the PSO metaheuristic and RBF metamodel. The applicability of the proposed method was shown using a simulation-based MTPP optimization problem with two, three, four, and five transmitters. The results showed the effectiveness of the proposed algorithm for solving a mathematical model of the MTPP optimization problem with a computationally less expensive method. The results also showed that, in the current case study, cost-effective signal coverage concerning considered obstacles could be obtained with four transmitters (with an average signal coverage equal to 82% of the area in the model), and more transmitters did not provide a significant change in the amount of average signal coverage. This approach can continuously search the whole of the design space to obtain optimal locations for any number of transmitters in the model without requiring the simulation of signal coverage for all locations via a simulation model. The RBF metamodel can train the model using a black-box simulation model and a limited amount of input-output data to approximate all locations in the design space. Finally, the limitations of the current study were discussed. Regarding the mentioned limitations of the current study, future research can be addressed.
Funding Statement: This research project is funded by TSRI Fund (CU_FRB640001_01_21_6). Amir Parnianifard would like to acknowledge the financial support by Second Century Fund (C2F), Chulalongkorn University, Bangkok. Sattam Al Otaibi would like to thank Taif University Researchers Supporting Project number (TURSP-2020/228), Taif University, Taif, Saudi Arabia for the financial support.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
![]() | This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |