## 4 Extending Delta Network to Global Solutions: Using Scores to Customize the Coverage
3:covered_cells \(\leftarrow\)\(\mathcal{O}\); \(\triangleright\) Clear vector holding deployed RSUs
4:while\(|\)covered_cells\(|<\)\(\alpha\)do\(\triangleright\) Loop until covering \(\alpha\) cells
5:for each uncovered cell \([x][y]\) in the grid do\(\triangleright\) Loop for all cells without roadside units
6:add_cell\([x][y]\) to set covered_cells; \(\triangleright\) Temporarily cover the cell
7:score\([x][y]\)\(\leftarrow\)compute_score after adding cell \([x][y]\); \(\triangleright\) Compute score
8:remove_cell\([x][y]\) from covered_cells; \(\triangleright\) uncover the cell
9:endfor
10:\([x^{\prime}][y^{\prime}]\)\(\leftarrow\)get_max_score(score[[]]); \(\triangleright\) Get the coordinates of the cell returning the highest score
11:add_cell\([x^{\prime}][y^{\prime}]\) to set covered_cells; \(\triangleright\) Cover the cell definitely
12:endwhile
13:return covered_cells;
```  
**Algorithm 1** General greedy heuristic  
The strategy _balanced_ considers an uniform distribution of weights for all ranges of \"percentage trip duration under coverage\" (\(\rho\)1). The strategy computes the _score_ of each cell by estimating the area underneath the Delta curve (since we rely on a greedy heuristic, the obtained area may not be optimal). Let us assume that cells {\(c_{1},c_{2},\ldots,c_{n-1}\)} are covered. Then, the score of cell \(c_{n}\) is given by Equation (1):  
\[\text{score of cell}[c_{n}]\text{ in }\textit{balanced}=\int_{0}^{1}f(x)dx \tag{1}\]  
where \(f(x)\) indicates the Delta curve after covering cells {\(c_{1},c_{2},\ldots,c_{n}\)}. On the other hand, the strategy _direct_ assigns weight to cells directly proportional to the \"percentage trip duration under coverage\", as indicated in Figure 3(b). Hence, cells receive high reward when increasing the coverage of highly connected vehicles. The _score_ is computed as the sum of the coverage received by each vehicle in terms of the percentage trip duration. Let us assume that cells {\(c_{1},c_{2},\ldots,c_{n-1}\)} are covered. Then, the score of cell \(c_{n}\) is given by Equation (2):  
\[\text{score of cell}[c_{n}]\text{ in }\textit{direct}=\sum_{i=1}^{\forall \ v\ \in\ \text{vehicles}}\rho_{1}(v) \tag{2}\]  
where \(\rho_{1}(v)\) indicates the percentage of the trip duration that vehicle \(v\) is traveling under the coverage of roadside units after covering cells {\(c_{1},c_{2},\ldots,c_{n}\)}. Thus, the strategy _direct_ represents an elitism: Vehicles experiencing high coverage tend to receive more coverage after each iteration (i.e., the strategy tries to extend the coverage of already covered vehicles). Complimentally, strategy _inverse_ assigns weight to cells inversely proportional to the \"percentage trip duration under coverage\" (\(\rho_{1}\)). In other words, cells providing coverage to vehicles with low coverage (or no coverage at all) receive high reward. \[\text{score of cell}[c_{n}]\text{ in }\textit{inverse}=\sum_{ \begin{subarray}{c} \forall\ v\in\text{ vehicles}\\ \end{subarray} }^{\forall\ v\in\text{ vehicles}}(1-\rho_{1}(v)) \tag{3}\]  
where \(\rho_{1}(v)\) indicates the percentage of the trip duration that vehicle \(v\) is traveling under the coverage of roadside units after covering cells \(\{c_{1},c_{2},\dots,c_{n}\}\). Figure 4 shows the distribution of weights used for computing the _score_. The _score_ indicates the next cell to be covered by Algorithm 1. Figure 4a shows the distribution used by the strategy _balanced_. In this distribution, all ranges of \"percentage trip duration under coverage\" (\(\rho_{1}\)) receive the same weight (shown in the \(x\)-axis), and the strategy tries to maximize the area under the Delta curve. Figure 4b shows the distribution used by the strategy _direct_, where weights are directly proportional to \(\rho_{1}\). By using such distribution, we intend to increase the share of highly connected vehicles. Figure 4c shows the distribution used by the strategy _inverse_, where weights are inversely proportional to \(\rho_{1}\).