# A New Hybrid Hierarchical Roadside Unit Deployment Scheme Combined with Parking Cars
## 4 Scenario Description and Basic Definition
### Optimize RSUs Deployment with Already-Existing t-RSUs
\(Ed\) refers to the Euclidean distance; \(Vel\) means vehicle. After modeling the robustness of the intra-cluster and inter-cluster, the next step is to establish the RSU deployment strategy. Within a given cost \(C\), the number of the RSUs is set. Since the maintenance cost and the installation cost are relatively certain, here we assume them as constant. The total number of the RSUs to be deployed is calculated in Equation (5):  
\[N=\left[\frac{C}{C_{m}+C_{i}}\right] \tag{5}\]  
where \(N\) is the maximum number of RSUs that can be deployed within the given cost. The notation \([\cdot]\) denotes rounding down the value to the nearest integer. \(C_{m}\) and \(C_{i}\) refer to the maintenance cost and installation cost, respectively. RSU deployment strategy is now based on how to find the strongest connectivity robustness path and covering the most vehicles for an observation time among those given N number of RSUs to be deployed. First, still starting from the simplest and most fundamental circumstance, the connectivity robustness between two RSUs is considered. For the specific RSU and another RSU, the path with the strongest robustness is calculated according to the formula in Equation (6):  
\[Path_{-}R=\sum_{k\in R_{\rm s}}\min\{Intra_{-}R_{i},Inter_{-}R_{i,i+1}\}_{k} \tag{6}\]  
where \(Path_{-}R\) means the robustness of the path from one RSU to another with the strongest robustness. \(R_{\rm s}\) is the set of the path with the strongest robustness. \(i\) and \(k\) refer to the ID of the cluster and road, respectively. \(\min\{Intra_{-}R_{i},Inter_{-}R_{i,i+1}\}\) represents a single road's robustness since a road's robustness is determined by its minimum intra-cluster and inter-cluster robustness. For an observation time T, the average number of vehicles on a specific road or the path from one RSU to another with the strongest connectivity robustness can be obtained. Therefore, finally, the RSU deployment strategy is given by the following formula in Equation (7):  
\[\left\{ \begin{matrix}\max\sum_{road=1}^{m}Num(road)\cdot\mathit{Bool_{road}} \\ \max\sum_{rsu=1}^{m}C(rsu)\cdot\mathit{Bool_{rsu}}\\ \sum_{rsu=1}^{m}\mathit{Bool_{rsu}}\leq N\end{matrix} \right. \tag{7}\]  
where \(Num(road)\) means the average number of vehicles during the observation time on the given road. \(\mathit{Bool_{rsu}}\) and \(\mathit{Bool_{road}}\) determine whether the RSU or road is selected with their values being either 0 or 1. \(C(rsu)\) refers to the average connectivity robustness of an RSU with other RSUs. \(\sum_{rsu=1}^{m}Bool_{rsu}\) refers to the total number of RSUs to be deployed. It should be noted that to achieve the maximum average connectivity robustness and the highest average number of vehicles on the road for a given observation duration, it can be concluded that the sum \(\sum_{rsu=1}^{m}Bool_{rsu}\) should be set to \(N\). The above problem is a multi-objective optimization problem. The proposed multi-objective problem can be transformed into a single-objective optimization problem and then solved by the branch and bound algorithm [24; 25]. The algorithm flow is shown in Figure 6:  
Figure 6: Branch and bound algorithm flow chart. Figure 6 describes the flow of the branch and bound algorithm. The algorithm uses block calculation to exhaustively block the feasible solution of the problem until the algorithm obtains the optimal solution. A detailed description of the branch and bound method is shown in Table 1.  
As shown in Table 1, the detailed process of the branch and bound algorithm is divided into five steps. After obtaining the optimal solution of the model, the simulation software OpenStreetMap and SUMO (version 1.11.0) [26] are used to verify the above calculation results.