Hybrid Metamodeling/Metaheuristic Assisted Multi-Transmitters Placement Planning

Amir Parnianifard,Muhammad Saadi,Manus Pengnoo,Muhammad Ali Imran,Sattam Al Otaibi,Pruk Sasithong,Pisit Vanichchanunt,Tuchsanai Polysuwan and Lunchakorn Wuttisittikulkij,＊

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

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

1 Introduction

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 solidstate 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].

1.1 Related Works

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

1.2 Research Contributions

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.

2 Preliminaries

2.1 Radial Basis Function

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

wherewi,(i=1+2+···+m)represents the weight coefficients that need to be estimated,mis the number of sample points andhi(x)is theith radial function.There are different types of RBF, such as linear, cubic, Gaussian, multi-quadratic, and so on [41].For instance, the common Gaussian form of the radial function is

whereri=‖x?xci‖ is thel2norm andxciis the center vector of sample pointi[42].The value of the weight parameterswican be estimated by minimizing the sum square error of model:

wheref(xi)is the exact output from the original model for theith sample points andis related to the predicted output from RBF.As the RBF interpolates the sample points, the SSE is expected to beSSE≈0.

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]:

3 Proposed Algorithm

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:

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

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.Letk=1,2,...,Kbe the number of transmitters in a model; therefore, the proposed optimization model based on a mathematical programming framework is constructed as below:

Subject to:

whereCk(X,Y)is the RBF estimation of ASC in location(X,Y)for thekth transmitter.The termsuXanduYindicate the length and width of the design space.The expressionshows the Euclidean distance (norm) between two locations of theith andjth transmitters.The expression ‖h‖ shows the maximum Euclidean distance between two locations in the design space.The weight scaleβis defined by the decision-maker and indicates the emphasis of the model over the distances between transmitters to smooth the overall signal coverage.From Eq.(5) the optimal result depends on the value ofβ, which can be chosen by the decision-maker.Varyingβallows the capture of the Pareto frontier (also called Pareto optimal efficiency).The set of optimal solutions obtained by fluctuatingβin the model provides an estimate of the Pareto frontier [49].As the aforementioned mathematical model is constrained(see Eq.(6)), a constraint handling method should be integrated into the optimization algorithm.There are several methods for handling constraints in the literature, such as penalty functions,special operators, repair algorithms, the separation of objectives and constraints, and hybrid methods [50].In this study, we use the simplest method, called the death penalty.In this method,search agents that violate any of the constraints at any level are treated as the same and penalized by assigning a large fitness value (small objective value in case of maximization).This method is very cheap and readily applicable to the PSO algorithm without algorithm modifications [50,51].

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 β in Eq.(6)to obtain the estimation of the Pareto frontier.

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.

4.1 Simulation Setup

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 222×222 pixels.We applied the binary model in this study, meaning set 0 for the area that the transmitter did not cover and 1 for the area that the transmitter successfully covered.

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

To reduce the number of simulation runs and produced images, we decussated odd locations(oddXandYpositions) 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 relevantXandYlocation (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? environment to analyze the data set.However, 12,544 sets of input (XandYlocations) and output data (ASC regarding each location)were produced.We used the Matlab?“Deep learning” toolbox to construct the RBF metamodel and applied the “particle swarm optimization” toolbox to perform PSO global optimization.We defined both theXaxis andYaxis in the same range of [0,222].Fig.4 shows the scatter plot for 12,544 different(X,Y)locations and the relevant average coverages for one transmitter.Notably,in the current simulation model, we assumed zero coverage for areas with obstacles in the design space.Fig.5 illustrates the contour plot of signal coverage in two-dimensions of the design space including the obstacle areas with zero coverage (areas with dark blue color).From the initial simulation model, by locating one transmitter, the maximum ASC was obtained in a location ofX=26 andY=0 withASC=0.4355 (see Fig.6).

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?function to construct the RBF metamodel.Fig.7 shows the surface plot of the constructed RBF metamodel and scatter plot of the relevant mean square error of prediction.

Figure 7:Surface plot of fitted RBF metamodel (a) and scatter plot for mean square error of constructed RBF prediction (b)

4.2 Mathematical Formulations

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 theXaxis andYaxis were 0 ≤Xk≤222 and 0 ≤Yk≤222,respectively.‖h‖ is the maximum distance between two locations, which here is the square diameter in the design space and equal to= 313.956.We repeated the optimization model forK=2,3,4,5 three times forβ=0.5,β=1, andβ=1.5 (see Eq.(6)).However, we ran the PSO optimizer for each optimization model, respectively.As we used the RBF metamodel instead of the original simulation model, we did not consider the number of function evaluations (iterations) required by the PSO global optimizer.In the following, we first sketch the mathematical programming model for each MTPP problem with two, three, four, and five transmitters (K=2,3,4,5), respectively.

Objective function:

Constraints:

wheredi,jshows the Euclidean distance between transmitters (e.g.,d1,2= {(X1?X2)2+(Y1?Y2)2}12), indicating the distance between the first and second transmitters in the design space.Besides,rbf (X.,Y.)shows the RBF metamodel that previously was fitted over 12,544 I/O data sets obtained from the simulation model (XandYlocations as a two-dimensional input set and the ASC for each location as an output set).Below, the obtained results for the MTPP optimization problems are discussed.

4.3 Results

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β(see Eq.(6)) are shown in Tab.1.Fig.8 provides the schematic signal coverage in the design space when two transmitters are located on their computed optimal locations.This figure shows the schematic image for signal coverage in the design space (222×222 pixels) for problems with two transmitters for three different values ofβ, respectively when the transmitters are located optimally on their computed optimal locations using the proposed algorithm.White zones in these images show the area covered by the signal, while black zones (mostly obstacles)show areas that were not covered by the signal of the transmitters.The optimal locations of transmitters are also shown in each image.The proposed algorithm aims to maximize the average signal coverage for each problem.As can be seen, the highestASCwas obtained by aβ=0.5 equal to 0.733.The optimization procedures for bothβ=1 andβ=1.5 provided the same results(the same locations for two transmitters) withASC=0.713.

Figure 8:Optimal locations (i.e., are shown by triangle marker) and overall signal coverage of two transmitters in MTL problem for β=0.5, β=1, and β=1.5.Black areas include obstacles and not covered by transmitters

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βvalues, and schematic coverages for the optimal locations of transmitters are illustrated in Fig.9.The optimal locations of transmitters and areas covered by the signal from the transmitters are shown in each image.The black zones (mostly obstacles)show areas that were not covered by the signal from the transmitters.As can be seen from Tab.2,the highest signal coverage was obtained forβ= 0.5 andβ= 1 byASC= 0.746 when three transmitters were optimally located in the design space.With the same procedure, the proposed optimization algorithm was used for the model with four transmitters, and the obtained results are depicted in Tab.3 and Fig.10.For a case with four transmitters, the highest signal coverage in the model was obtained byASC=0.802 inβ=1, followed closely byβ=0.5 withASC=0.794.

Figure 9:Optimal locations (i.e., are shown by triangle marker) and overall signal coverage of three transmitters in MTL problem for β=0.5, β=1, and β=1.5.Black areas include obstacles and not covered by transmitters

Figure 10:Optimal locations (i.e., are shown by triangle marker) and overall signal coverage of four transmitters in MTL problem for β=0.5, β=1, and β=1.5.Black areas include obstacles and not covered by transmitters

Table 1:The optimal locations and relevant overall signal coverage for two-transmitters localization model

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β=1 byASC=0.802,which was the same as the model with four transmitters.

Figure 11:Optimal locations (i.e., are shown by triangle marker) and overall signal coverage of five transmitters in MTL problem for β =0.5, β =1, and β=1.5.Black areas include obstacles and not covered by transmitters

Finally, we compared all obtained results based onβ=0.5,β=1, andβ=1.5, as shown in Fig.12.β=0.5 shows good results for the models with two, three, and four transmitters but not for the model with five transmitters.However, due to the considered obstacle areas in the original simulation model, the model with five transmitters exhibited very similar behavior in terms of the covering design space with the model using four transmitters.Thus, it is not cost-effective to use a higher number of transmitters when almost maximum signal coverage can be obtained with four transmitters.

Figure 12:Average signal coverage for different number of transmitters in the model based on three different β values

Table 2:The optimal locations and relevant overall signal coverage for three-transmitters localization model

Table 3:The optimal locations and relevant overall signal coverage for four-transmitters localization model

Table 4:The optimal locations and relevant overall signal coverage for five-transmitters localization model

4.4 Discussion

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 inequalityconstrained 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.

5 Conclusions

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.

Conficts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.