# Distance-Based Resource Allocation for Vehicle-to-Pedestrian Safety Communication
## 6 One-to-Many Bipartite Matching
### Algorithm  
The algorithm takes a bipartite graph (W(C,V)) as input. The output is an array that maps a vehicle to the cellular users. For each V that is available, a C is connected to that V (if the vehicle has less than 5 connections). A group is complete once a V connects to five Cs at a given time. We decomposed the bipartite matching problem by converting it into maximum flow problem using the greedy Ford Fulkerson maximum flow method [31]. The pseudo code is shown in Algorithm 1.  
A vehicular user acts as a central controller with a W(C,V) matrix. This matrix has rows and columns showing a distance relationship between the cellular user and a vehicular user. The matching algorithm runs on each vehicle. For every cellular user (C), the assignVeh(C) function is called. A vehicle (V) is available (V\({}_{\text{available}}\)) if the W(C,V) matrix has an entry greater than zero and the vehicle has not been visited before. Each available vehicle is then put into three different groups based on the number of connections (Connv) it has with the cellular users. If number of connections is less than 1 (min_connection), available vehicle is directly assigned to Group 1. If the number of connections is more than 1 and less than 5 (max_connection), the available vehicle is assigned to Group 2. If number of connections is greater than equal to 5, than the available vehicle is assigned to Group 3. If a group is full but there is a cellular user (C') that is more vulnerable than any of the current members of the group, then it is assigned to that group with a replacement weight, replacing the least vulnerable user of that group. Once the vehicles are all assigned to the groups, the C is connected to the optimum vehicle (V\({}_{\text{optimum}}\)). Once each group is full (maximum connections), distance wise sorting is done. Maximum weight is assigned to the C closest in distance to the vehicle.  
Figure 3: One-to-many bipartite matching.  
```
Procedure:createConnections Inputs:W(C,V): distance relation between all V and C for each C unit do  CALL \"assignVeh(C)\" to connect C with optimum V unit Procedure: assignVeh(C) for each V do ifW(C,V) > 0 AND (NOT previously visited) \(\mathrm{V_{available}}\leftarrow\mathrm{V}\) for each V\(\mathrm{V_{available}}\)do \(\mathrm{Conn^{V}}\leftarrow\mathrm{Number\ of\ C\ connected\ to\ V_{available}}\) if\(\mathrm{Conn^{V}}<\mathrm{min\_connection}\) \(\mathrm{V_{group(1)}}\leftarrow\mathrm{V_{available}}\) elseif\(\mathrm{Conn^{V}}\geq\mathrm{min\_connection}\) AND \(\mathrm{Conn^{V}}<\mathrm{max\_connection}\) \(\mathrm{V_{group(2)}}\leftarrow\mathrm{V_{available}}\) else\(\mathrm{Conn^{V}}\geq\mathrm{max\_connection}\) \(\mathrm{V_{group(3)}}\leftarrow\mathrm{V_{available}}\) if\(\mathrm{V_{group(1)}}\) is NOT empty \(\mathrm{V_{optimum}}\leftarrow\mathrm{V_{group(1)}}\) with max weight (lowest distance from current C) \(\mathrm{Connect\ C}\) and \(\mathrm{V_{optimum}}\)  RETURN TRUE if\(\mathrm{V_{group(2)}}\) is NOT empty \(\mathrm{V_{optimum}}\leftarrow\mathrm{V_{group(2)}}\) with max weight (lowest distance from current C) \(\mathrm{Connect\ C}\) and \(\mathrm{V_{optimum}}\)  RETURN TRUE if\(\mathrm{V_{group(3)}}\) is NOT empty  Sort V\(\mathrm{group(3)}\) according to their distance cluster in ascending order for each V\(\mathrm{group(3)}\)do ifConn\(\mathrm{V^{(group\_3)}}\leq\mathrm{ replacement\ weight\ AND\ assignVeh(C^{\prime})}==\mathrm{TRUE}\) \(\mathrm{V_{optimum}}\leftarrow\mathrm{V_{group(3)}}\)  Connect C and \(\mathrm{V_{optimum}}\) RETURN TRUE  RETURN FALSE
```  
**Algorithm 1** One-to-Many Bipartite Matching