# Improving Roadside Unit Deployment in Vehicular Networks by Exploiting Genetic Algorithms
## 3 GARSU: Automatic RSU Deployment
### Fitness Function  
The target function to be maximized, also known as the fitness function, summarizes in a single numerical figure how close to meeting the overall specification requirements the given designed solution is. It is one of the most important parameters to determine since it acts as a guide for the search process. In this paper, the RSU deployment problem tackled focuses on low notification time for warning messages to the emergency authorities. In particular, our RSU deployment approach should reduce warning notification delays close to zero by achieving a fitness function close to one hundred.  
Since the RSU deployment is fixed, the fitness function should reflect the results obtained for the different traffic flows that could be found during a single day in a given city. The approach we followed calculates the average warning notification time for each scenario tested, in order to assign a uniform importance to every possible vehicle density. The fitness function that guides GARSUD is indicated in (1), where \(wnt(i)\) represents the average warning notification time measured in scenario \(i\) and \(N\) is the number of tested scenarios.  
\[GARSUD\_Fitness=\frac{100}{\frac{\sum_{i=1}^{N}wnt(i)}{N}+1.0} \tag{1}\]  
Notice that the GARSUD fitness function returns values between zero and 100, where zero represents the worst possible result when the warning notification time is maximum and 100 when the warning notification time is low.  
We assign the same importance (i.e., the same weight) to each scenario since this approach provides in practice good results, and it ensures that no scenario is completely ignored or considered irrelevant. Nevertheless, the calculated mean value could be tuned to assign different weights to each density (i.e., representing how often that scenario would be found in a real environment).  
Figure 2: One-point crossover operator example.  
GARSUD uses of evolutionary computation, specifically genetic algorithms, to test different configurations and guide the search process to maximize the value of the objective function. Testing all the possible configurations is computationally unfeasible, due to the high amount of possible combinations of locations for the RSUs, even when considering small map layouts. For example, deploying only five RSUs in a map with 200 possible locations for each RSU could produce \(\binom{200}{5}=2.53565\)e + 9 different possible deployments. Considering, for example, that our computational power allows us to evaluate 1000 deployments per second (which requires a high computing performance), it would require more than 29 days of computing time to determine the optimal deployment for only one small specific scenario.  
GARSUD requires a map of the target area including the street and junction layout, the possible obstacles interfering with the wireless radio signal, mobility traces representing the behavior of the traffic using realistic vehicle densities and the number of RSUs to be deployed in the area. Using this information as input, GARSUD computes a location for every RSU, thus increasing the coverage provided and reducing the notification time of warning messages in the given scenario.  
Figure 3 illustrates the steps followed by GARSUD. As a first step, it makes an initial random RSU deployment; secondly, it simulates this specific scenario by using a modified version of the ns-2 simulator, which allows us to calculate the solution fitness. After that, it performs the parent selection, the crossover and the mutation operations. Finally, it evaluates the fitness of the new solution, makes the partial replacement and checks whether the termination condition is fulfilled (in our case, a maximum number of completed generations). If not, it performs the parent selection process again and repeats the subsequent operations.  
Efficient use of genetic algorithms requires defining several parameters to guide the search process. Table 1 summarizes the parameters defined in GARSUD.  
Figure 3: GARSUD algorithm.