# Adaptive Virtual RSU Scheduling for Scalable Coverage under Bidirectional Vehicle Traffic Flow
## 4 RSU Allocation
### RSU Allocation Strategy for Bidirectional Link Capacity  
In this section, we will present our RSU allocation strategy design for the service capacity in the bidirectional traffic flow. The traditional Max-Flow-Min-Cut problem with single-source and single-destination can be solved with a polynomial-time algorithm. For example, the Edmonds-Karp algorithm, push-relabel algorithm, and relabel-to-front algorithm are proposed to calculate the maximal flow. The Store-Wagner algorithm is usually utilized to calculate the minimal cut. As the urban traffic can be divided into multiple road segments, we can simplify the problem for each road segment, and analyze the relationship between the distributed RSUs and link capacity between them. Given a road segment with bidirectional traffic flow in Figure 3, we can construct an abstract ladder graph in Figure 4, including the bidirectional traffic flows of eastbound link and westbound link in each region. In Figure 4, the road segment can be divided into seven regions, as \(A\), \(B\),..., and \(G\), respectively. The set of regions with eastbound traffic can be denoted as \(V^{e}(G)=\{A^{e},B^{e},...,G^{e}\}\), and the set of regions with west bound traffic can be denoted as \(V^{w}(G)=\{A^{w},B^{w},...,G^{w}\}\) accordingly. The link capacity (e.g., \(|\widehat{AG}|\)) is determined by the communication connectivity of passing-by regions. The communication connectivity in each region can be inferred from the communication time and vehicle density for V2V communication in the same direction, V2V communication in the opposite direction, and V2I communication. For node \(v\in V(G)\), we denote \(f^{+}(v)\) as the joining flow capacity, which presents the connectivity between the source node and node \(v\). For example, we can have \(f^{+}(C^{e})=min\big{\{}f^{+}(B^{e}),|\widehat{B^{e}C^{e}}|\big{\}}+min\big{\{} f^{+}(C^{w}),|\widehat{C^{w}C^{e}}|\big{\}}\). In addition, we can denote \(V^{+}(v)\) as the node regions before \(v\) along the traffic direction, and \(V^{-}(v)\) as the node regions after \(v\) in the following traffic direction. For example, \(V^{+}(D^{e})\) denotes the node regions \(\{A,B,C\}\), and \(V^{-}(D^{e})\) denotes the node regions \(\{E,F,G\}\). In order to allocate RSUs \(\{1,...,k\}\), we present the bidirectional allocation algorithm for RSUs in Algorithm 1. As the connectivity bottleneck in the upstream will reduce the whole link capacity, the main idea in Algorithm 1 is to arrange the connectivity bottleneck in the downstream of the communication link through RSU allocation. The details of implementation issues will be illustrated through an example in Figure 4. Given a bidirectional traffic flow, the RSUs are allocated in region \(A\) and \(G\). In the link \(\widehat{AG}\), there exist four connectivity bottleneck nodes denoted as black nodes with \(f^{+}(C^{e})<f^{+}(F^{w})<f^{+}(E^{w})<f^{+}(D^{e})\). We are motivated to maximize the link capacity \(|\widehat{AG}|\) through RSU allocation. Initially, the set of regions \(B,C,D,E,F\) are available for RSU allocation. In step 1, \(f^{+}(C^{e})\) is selected as the link bottleneck, and the link is updated as \(\widehat{CG}\); in step 2, \(f^{+}(F^{w})\) is selected as the link bottleneck,and the link is updated as \(\widehat{CF}\); in step 3, \(f^{+}(E^{w})\) is selected as the link bottleneck, and the link is updated as \(\widehat{CE}\); in step 4, \(f^{+}(D^{e})\) is selected as the link bottleneck, and the link is updated as \(\widehat{CD}\). Finally, as \(f^{+}(D^{e})<f^{+}(C^{w})\), the RSU is allocated in region \(D\). As a result, \(\widehat{AG}\) can be divided into \(\widehat{AD}\) and \(\widehat{DG}\) with increasing link capacity \(|\widehat{D^{w}A^{w}}|\) and \(|\widehat{D^{e}G^{e}}|\), respectively.