Minimizing transmission delays in vehicular ad hoc networks by optimized placement of road-side unit

Abstract

In a vehicular ad hoc network (VANET), a road side unit (RSU) is a network traffic transmitter statically placed along the route to facilitate communication between vehicles and network infrastructure. The transmission and propagation delays, and the capacity of a VANET greatly depend upon the relative positions of RSUs along the road. In this paper, we investigate the problem of RSU placement on a highway-like roadway and propose a scheme that reduces network latency while ensuring good network capacity. In this regard, an integer linear programming model with the objective of minimizing network latency has been developed that depicts the network under consideration. Optimization techniques have then been applied to determine the RSU deployment that provides the minimum network latency. The proposed scheme was validated by generating traffic mobility patterns by using VanetMobiSim and performing simulations in NS2. In-depth comparative analyses of the proposed scheme with uniform distribution scheme and cost-effective strategy showed a reduction of 25% and 10% in network latency, respectively and thus established the superiority of the proposed solution.

1 Introduction

Vehicular Ad Hoc Network (VANET) is an emerging ad hoc network technology that enables the concept of Intelligent Transportation System (ITS). ITS helps in efficient utilization and management of road infrastructure by gathering and disseminating information via VANETs. A VANET allows vehicles to communicate with each other and outside network, and to access the Internet on the move. VANET is a sub-branch of Mobile Ad-hoc Networks (MANET). The nodes in MANET and VANET are self-composed, self-guided and decentralized in a distributed manner with a self-observed authority [1]. VANET provides a wireless communication link between moving vehicles, using Dedicated Short Range Communication (DSRC) [2], which is essentially IEEE 802.11a modified for low overhead operation [3].

Due to high mobility the topology of a VANET changes continuously. Furthermore, in long range communication, one of the major problems is unavailability of RSU in some areas which results in disconnection and unwanted delays. The capacity and efficiency of VANET strongly depends upon placement of RSU along the route. A well-designed RSU placement strategy can greatly enhance the capacity and efficiency of the network, and at the same time reduces implementation cost. The RSU allocation strategy must be devised such that it is able to collect all the traffic data and disseminate it in real-time over the entire network.

VANET has a wide range of applications ranging from entertainment to road safety [4]. Safety applications heavily rely on near real-time transmission of emergency messages [5]. These types of applications require both vehicle-to-vehicle and vehicle-to-infrastructure communication for reliable operation. The main purpose is to avoid mishaps, save peoples’ lives and provide obstacle less environment to emergency response team. On highways, VANET could transmit alert messages using RSUs to help expedite the emergency response in case of an incident. There is a time period, called the golden period [6], between the happening of an accident and arrival of medical assistance. When an accident happens, alert messages should be propagated to the concerned authorities within half of the golden period [7]. It is evident that minimizing transmission delay is the key to provide emergency response in time.

This work deals with placement of RSUs on a highway-like roadway. Each vehicle can access RSUs in two different ways; first is the direct delivery, which takes place when the vehicle enters the transmission range of the RSU, and other is multi-hop relaying, that occurs when the vehicle is out of the transmission range of any RSU. We propose an RSU placement strategy, called Delay Minimization Problem (DMP), by formulating the problem as an Integer Linear Programming (ILP) model. The objective of the model is to minimize overall system latency, while respecting the total budget available for the deployment. For developing the model we consider both vehicle-to-vehicle and vehicle-to-RSU communications. Vehicle distribution and mobility patterns are generated by using VanetMobiSim [8], while the proposed model is validated by network simulations performed in NS2.

The rest of the paper is organized as follows. Some background and related work is presented in Sect. 2. Section 3 provides the system model. Then, the RSU placement problem is formulated in Sect. 4. The simulation experiments are presented in Sect. 5, while results and discussions are presented in Sect. 6. Finally, Sect. 7 concludes the paper.

2 Background and related work

The problem of optimal placement of RSU has been addressed by several researchers. Liu et al. [7] analyzed the total delay of broadcasting alerts in VANET along highways. The researchers also developed a relationship between the optimal number of RSUs and the distance covered by vehicles. However, they did not propose any RSU deployment strategy. Ahmed and Bouk [9] considered the RSU placement problem and devised a scheme that minimizes handover duration from source RSU to target RSU. The scheme calculates a parameter called Coverage/Service Time, which is used to determine the time during which a subscriber station can receive service from the target RSU. Minimizing handover delay can be beneficial in reducing network delay, but it cannot provide any bound on the overall network latency.

In another scheme [10], proposed by Cheng et al. a geometry based sparse coverage protocol for RSU placement is used which considers many attributes such as geometry of road networks, traffic patterns and resource limitations. By analyzing historical data, the protocol is able to discover the most suitable coverage areas. Both genetic and greedy algorithms are used to resolve the coverage problem. However, that scheme does not address the problem of minimizing network delay.

Chi et al. [11] proposed an RSU placement strategy based on the traffic flow. The scheme minimizes the number of RSU by placing RSUs at road intersections and places with highest vehicle frequency. The idea is to cluster road intersections and find potential RSU locations by using Markov clustering algorithm. On the other hand, T. J. Wu provided a comparative study that showed that the scheme proposed by Chi et al. [12] is not efficient. They proposed a cost-effective strategy (CES) of RSU placement that aims to maximize system capacity. The scheme provides good throughput but the network delay achieved by it is not optimal. We have compared CES with our strategy and presented the results in Sect. 6.

Cavalcante et al. [13] modeled a maximum coverage with time threshold problem (MCTTP) by using a genetic algorithm for solving the problem. Four real-world datasets were tested and compared with a greedy approach. Aslam et al. [14] proposed two different optimization methods for the deployment of a limited number of RSUs in an urban area. One is called Balloon Expansion Heuristic (BEH) method, the other is an analytical BIP method. BIP utilizes branch and bound approach for finding an optimal analytical solution, while BEH method uses balloon expansion analogy for finding an optimal or near optimal solution. Both methods were used to solve the optimization problem of minimizing the average reporting time. The proposed scheme showed that BEH method performs better than BIP method in terms of computational cost and scalability. Patil et al. [15] proposed a novel Voronoi network-based algorithm for effective allocation of RSU’s that forms a Voronoi network in terms of the amount of delay incurred by data packets sent over the RSUs. Similarly, Jalooli et al. [16] proposed an algorithm for visualizing the performance of message propagation in VANET, called Safety-Based Disconnected RSU Placement algorithm (S-BRP) through which message propagation delay can be minimized in urban areas. These urban scenarios cannot be applied to highways due to difference in traffic density, mobility patterns, vehicle speeds, traffic signals, obstacles, more severe interference and resource contention.

Rui et al. [17] proposed an algorithm for modifying the impact of MRC under WAVE multichannel environment called Success Probability based Relay Contention Algorithm (SPRCA). The stochastic properties of vehicular distribution and real time location information of vehicles were explored by SPRCA. To analyze the SPRCA performance with stochastic geometry-based approach and derive their properties, a theoretical model was constructed. No strategy for minimizing network delay was proposed by the authors. In an another work [18], to evaluate the quality of service (QoS) in VANET, the delay bounds and end-to-end backlog were considered as the significant metrics by Hu, Yun et al. Two kinds of data applications were considered, one was the delay tolerant application and other was the delay sensitive application. For analyzing the access performance in the MAC sub-layer EDCA mechanism was adopted. By assuming the double Nakagami-m fading channel model between vehicles, the proposed algorithm was verified with three kinds of real wireless data traces that are UDP, VoIP and gaming. However, they did not provide any RSU placement strategy.

Most of the research work done on RSU placement has focused on maximizing system performance in terms of throughput [11, 12, 14] or overall system capacity [10, 13, 15]. Few researchers have considered the problem of minimizing latency. Ahmed et al. [9] mainly focused on minimizing handover latency and associated network overhead. In [17] researchers studied the problem of how to mitigate the impact of multichannel relay conflict and maintain high information propagation speed and proposed a relay contention algorithm. Liu et al. [7] and Hu et al. [18] modeled and analyzed the delay of broadcasting an alert message in VANET. These works focused on finding the optimal number of RSUs for a given distance, however they did not consider the problem of optimal RSU placement. The problem of minimizing transmission delay by optimally placing RSU was studied in [16]. However, the proposed solution was focused on minimizing delays in urban environment. Our research work mainly focuses on optimal RSU placement for minimizing transmission delays along highways.

We propose an RSU placement strategy for minimizing network delay by formulating the problem as an Integer Linear Programming (ILP) model. Minimizing transmission delay is very important for life saving because there is a delay constraint, so called golden period, between the happening of the accident and the arrival of the medical assistance. The objective of the model is to minimize overall network latency, while respecting the total budget available for the deployment. For developing the model we consider both vehicle-to-vehicle and vehicle-to-RSU communications. Vehicle distribution and mobility patterns are generated by using VanetMobiSim [8], while the proposed model is validated by network simulations performed in NS2.

3 Proposed approach

The Capacity and efficiency of VANET strongly depends upon the placement of RSU along the route. A well-designed RSU placement strategy can greatly enhance the capacity and efficiency of the network, while at the same time reduces implementation cost. This work deals with placement of RSUs on a highway-like roadway. There can be at most one RSU placed in a segment. Each vehicle can access RSUs in two different ways one is Direct delivery, which takes place when the vehicle enters the transmission range of the RSU. Other is Multi-Hop Relaying, which occurs when the vehicle is out of the transmission range of any RSU. Our methodology for the efficient deployment of RSU is as follows:

• 1. Vehicle mobility patterns are generated under different scenarios by using VanetMobiSim to emulate realistic vehicular environment.

• 2. An Integer Linear Programming model is formulated that minimizes the overall latency of the network and reduces RSU deployment cost as well.

• 3. The proposed optimization model is solved to get optimal RSU placement.

• 4. The proposed model is then validated by simulations performed on the optimized model in NS2 simulator.

• 5. Comparative analysis are done between the proposed RSU placement strategy (DMP) and well-known Uniform Distribution scheme.

The initial step of this work is to generate a vehicular mobility pattern by using VanetMobiSim. VanetMobiSim is a realistic vehicular movement trace generator that is used for simulating large-scale telecommunication networks [19]. In VanetMobiSim, different scenarios were generated by choosing a highway map with 5, 10, 15, 20, 30, 40 and 50 vehicles, respectively. The road consists of multiple lanes, upper road is for the vehicular movement from left to right, whereas on the lower road traffic is moving from right to left. The road is partitioned into 5 segments; each segmental distance is set equal to the transmission range of an RSU. All vehicles are moving with speed between 60 to 120 km/h. Random Trip Generator is used for random generation of vehicular patterns. After generating mobility pattern VanetMobiSim produce an output file that can be used as an input for NS2 simulation. Problem formulation is discussed in detail in the next section.

4 Problem formulation

In this section, the RSU deployment problem is formulated as an Integer Linear Programming (ILP) model. The objective of this problem is to devise a minimum latency cost-efficient RSU deployment scheme, i.e. the model determines how many RSUs to deploy and where to place them so that the overall network latency be minimized at the minimum possible deployment cost.

Consider that each vehicle can access the RSU in two different ways on a highway, i.e. direct access and multi-hop relaying. The following decision variables are defined to facilitate ILP model formulation:

$Y_i^j=1$::

there are vehicles in segment j being served by the RSU in segment i. While, $Y_i^j=0$ if there is no vehicle in segment j being served by the RSU in segment i

$R_i$::

Whether or not an RSU is present in segment i. $R_i\in \{0,1\}$

$D_i$::

The average delay over the link via direct access to an RSU located in segment i

$D_i^{j^{m-}}$::

The average delay for a link from a vehicle in segment i to an RSU in segment j via multi-hop relaying in backward direction. In this case $i > j$.

$D_i^{j^{m+}}$::

The average delay for a link from a vehicle in segment i to an RSU in segment j via multi-hop relaying in forward direction. In this case $i < j$.

$T_{th}$::

A positive integer indicating the hop count limit for multi-hop relaying

$C_R$::

Deployment cost of one RSU

$C_T$::

Total deployment budget for this placement

Mathematically, the problem can be formulated as follows.

$$\begin{aligned} Min~\left( \sum _{i=1}^{k} R_i D_i + \sum _{j=1}^{i-1} Y_i^j D_i^{j^{m-} } + \sum _{j=i+1}^{k} Y_i^j D_i^{j^{m+} }\right) \end{aligned}$$

subject to:

$$\begin{aligned}&R_i \in \{0,1\}, \quad \forall i \in \{1,2,3,\ldots ,k\} \end{aligned}$$

(1)

$$\begin{aligned}&Y_i^j=0 if\; |i-j| > T_{th}\quad else\; Y_i^j\in \{0,1\} \end{aligned}$$

(2)

$$\begin{aligned}&\sum _{i=1}^k Y_i^j \le 1, \quad j \in \{1,2,3,\ldots ,k\} \end{aligned}$$

(3)

$$\begin{aligned}&R_i=1, if\; \Pi _j (1-Y_i^j )=0 , \quad \forall i \in \{1,2,3,\ldots ,k\} \end{aligned}$$

(4)

$$\begin{aligned}&\sum _{i=1}^k R_i C_R \le C_T \end{aligned}$$

(5)

Where the objective is to minimize the sum of delays resulting due to both direct connections and multi-hop connections. The first term ($\sum _{i=1}^{k} R_i D_i$) accounts for the overall delays due to direct connections only. The second and third terms of the objective represent the total delays in backward multi-hop connections and forward multi-hop connections, respectively. Constraint (1) indicates that at most one RSU can be deployed in a segment. Constraint (2) enforces the hop count limit (i.e. $T_{th}$) for vehicle to vehicle communication. This is required to ensure satisfactory performance in multi-hop relaying connections. According to constraint (3), each multi-hop connection can be served by at most one RSU at a given instant. Constraint (4) indicates that there must be an RSU deployed in segment i if there are vehicles in any other segment being served by the RSU in that segment. However, this does not restrict the placement of RSU in any other segment for which the condition is not true. Constraint (5) specifies the total budget for this RSU deployment.

4.1 Maximum achievable data rate

According to the Shannon Capacity theorem, the maximum achievable data rate ($\tau$) for a link of bandwidth W is given by

$$\begin{aligned} \tau = W \log _2(1 + SNR) \end{aligned}$$

(6)

where SNR is the signal to noise ratio at the receiver.

We have two scenarios to consider: direct link transmission and multihop transmission. In direct link transmission, a vehicle is in transmission range of an RSU, and therefore a direct communication link can be established between them. For the Free Space model with negligible backgroud noise, the signal power at the receiver is given by

$$\begin{aligned} P_r = \frac{P_t}{d^2} \end{aligned}$$

(7)

where $P_t$ and $P_r$ are the transmission power and the power received, respectively, and d is the direct link distance between the transmitter and the receiver.

If there is a vehicle in the interference range of the receiver, the strength of noise signal at the receiver due to the single interference source can be given as follows:

$$\begin{aligned} P_r^\prime = \frac{P_t^\prime }{d^{\prime 2}} \end{aligned}$$

(8)

where $P_t^\prime$ and $P_r^\prime$ are the transmission power of interference source and the interference signal power at the receiver respectively, and $d^\prime$ is the shortest distance between the interfering vehicle and the receiver.

If there are N interfering vehicles within the interference range of the receiver, the total interference experienced by the receiver is the combined effect of all the interference signals. In the worst case, all these signals will combine constructively at the receiver and the total interference can be given as follows:

$$\begin{aligned} P_{tot}^\prime = \displaystyle \sum _{i=1}^{N} \frac{P_{t_i}^\prime }{d_i^{\prime 2}} \end{aligned}$$

(9)

and the SINR at the receiver can be expressed by

$$\begin{aligned} SINR = \frac{P_r}{P_{tot}^\prime } \end{aligned}$$

$$\begin{aligned} SINR = \frac{P_t}{d^2} \times \displaystyle \sum _{i=1}^{N} \frac{d_i^{\prime 2}}{P^\prime _{t_i}} \end{aligned}$$

(10)

The maximum achievable rate can be determined by combining Eqs. 6 and 10:

$$\begin{aligned} \tau = W \log _2 \left( 1 + \frac{P_t}{d^2} \times \displaystyle \sum _{i=1}^{N} \frac{d_i^{\prime 2}}{P^\prime _{t_i}} \right) \end{aligned}$$

(11)

For a successful communication link, it is necessary that SINR is greater than a threshold value ($\varsigma$). Let $\beta (x)$ be the probability density function of the vehicle location distribution and $\phi$ be the interference range of the receiver, then the probability of exactly one vehicle in the interference range is given by

$$\begin{aligned} P_{\phi } = \int _{\phi } \beta (x) dx \end{aligned}$$

(12)

and the average number of vehicles in $\phi$ is given by

$$\begin{aligned} N_{\phi } = N P_{\phi } \end{aligned}$$

(13)

where N is the total number of vehicles in the system.

Let $\varTheta _{t,r}$ be the probability of a successful transmission between the transmitter t and the receiver r, then $\varTheta _{t,r}$ can be determined by the following mathematical relation [20].

$$\begin{aligned} \varTheta _{t,r}(\phi ) = r \cdot (1 -r )^{N_{\phi }-1} \end{aligned}$$

(14)

where r is the successful channel access probability.

In case of a multi-hop IEEE 802.11p network, r can be expressed as follows [21].

$$\begin{aligned} r \approx 2 q \frac{\omega _{min}}{(\omega _{min}+1)^2} \end{aligned}$$

(15)

where $\omega _{min}$ is the minimum contention window size of CSMA/CA and q is a constant that represents the probability of a successful handshake.

For a multi-hop relay, the transfer rate depends upon successful establishment of the connection. Therefore, $\tau$ depends upon the probability of successful transmission. The expected value of $\tau$ can be determined by combining Eqs. 11 and 14.

$$\begin{aligned} \tau& \approx \varTheta _{t,r}(\phi ) W \log _2 \left( 1 + \frac{P_t}{d^2} \times \displaystyle \sum _{i=1}^{N} \frac{d_i^{\prime 2}}{P^\prime _{t_i}} \right) \nonumber \\&= r \cdot (1-r)^{N_{\phi }-1} W \log _2 \left( 1 + \frac{P_t}{d^2} \times \displaystyle \sum _{i=1}^{N} \frac{d_i^{\prime 2}}{P^\prime _{t_i}} \right) \end{aligned}$$

(16)

4.2 Average propagation delay

The average achievable delay is easy to calculate if there is no restriction on budget, i.e. we can deploy any number of RSUs such that each active vehicle has a direct link with an RSU. In this scenario, all links are direct and there is no multi-hop connection, and therefore the total network propagation delay is the minimum. For N connections it can be given by the following equation:

$$\begin{aligned} D_{min} = \displaystyle \sum _{i=1}^N R_i D_i \end{aligned}$$

(17)

However, this idealistic scenario is not always possible. The average propagation delay of a multi-hop link depends upon the average number of relays and the average distance between adjacent relaying vehicles. Let’s first consider the case of a single hop link. In this case, the propagation delay depends only upon the average distance between communicating vehicles in adjacent segments. Inter-vehicle spacing on a highway can be modeled by an exponential distribution with average propagation distance between two vehicles equal to $\frac{1}{\lambda }$. In our model, we have assumed the transmission range of a vehicle (L) to be equal to the segment length. Since L is much smaller than the signal propagation speed (c), therefore the average distance between two vehicles in adjacent segments can be approximated to segment length $\frac{1}{\lambda }=L$. The propagation delay can be expressed by the following equation.

$$\begin{aligned} D = \frac{L}{c} \varTheta _{t,r}(\phi ) \end{aligned}$$

(18)

where $\varTheta _{t,r}$ is the probability of successful communication.

In the general case, the interest is to determine the expected number of hops in a relay process. Vehicles follow an independent homogenous Poisson process with a constant vehicle intensity $\mu$ along the road [20]. The expected number of hops (y(k)) for such a distribution can be expressed by the following mathematical relation [20].

$$\begin{aligned} \begin{aligned} y(k)&= \displaystyle \sum _{i=0}^{L-k-1} \mu (1-\mu )^i \left[ 1+y(i)\right] \quad \forall \; 0 \le k \le L-1 \\&\quad and\; y(L)=0 \end{aligned} \end{aligned}$$

(19)

where L is the transmission range of the vehicle and k is the distance between communication vehicles. Therefore, the total propagation delay for a multi-hop link can be determined by combining Eqs. 14, 18 and 19.

$$\begin{aligned} \begin{aligned} D_{tot}&= r \cdot (1 -r )^{N_{\phi }-1} \frac{L}{c} \displaystyle \sum _{i=0}^{L-k-1} \mu (1-\mu )^i \left[ 1+y(i)\right] \\&\quad \forall\; 0 \le k \le L-1 \end{aligned} \end{aligned}$$

(20)

5 Computational experiments

To evaluate the performance of our proposed RSU deployment strategy via simulation, we consider the road topologies similar to one shown in Fig. 1, where the road consists of multiple lanes and the dimensions of road are 1250 m (length) by 150 m (width). The road is partitioned into 5 segments. The length of each segment is set equal to the transmission range of an RSU. Multiple simulation scenarios were created with a vehicle distribution of 5–50 vehicles moving along the highway with the speed in the range of 60–120 km per hour on a highway like roadway. Vehicles are moving in two different directions: On one side of the road they are moving from left to the right, whereas on the other side they move from right to left. VanetMobiSim [19] is used to generate mobility model to emulate realistic vehicular distribution. The vehicle population is not uniformly distributed, and the population density is relatively high at road junctions. The average transmission delay between vehicle and RSU is found through simulations in NS2 by considering the fact that a vehicle can make both direct and multi-hop connections. The transmission range of each RSU and vehicle is 250 m and the interference range is 550 m, resulting in 5 segments. Each vehicle can make a connection to the nearest RSU in either forward or backward directions. The important simulation parameters are shown in Table 1.

Fig. 1

Example of an RSU deployment: five RSUs deployed in five segments along a road

For each of the simulation scenario, we performed 50 runs with DMP, Uniform Distribution and CES schemes, and the average results are reported here. For example Fig. 2 shows DMP deployment, while Fig. 3 shows Uniform deployment for the scenario involving 2 RSU and 10 vehicles.

Fig. 2

Two RSUs deployed according to DMP RSU placement strategy

Fig. 3

Two RSUs deployed according to Uniform Distribution

Table 1 Simulation parameters

6 Result and discussion

We compare our proposed solution with Uniform Distribution and CES , and evaluate the average network latency and average throughput in the network for each placement strategy. The objective of CES is to maximize network capacity. The total number of RSUs that can be deployed is controlled by the budget constraint. In Figs. 4 and 5, DMP 1 means DMP scheme with one RSU, similarly DMP 2 means DMP scheme using 2 RSUs and so on. Similarly, in Figs. 6 and 7, DMP 10 implies DMP applied to 10 vehicles scenario. Other data labels should be interpreted in a similar manner.

Fig. 4

Average latency for different number of connections

Fig. 5

Average throughput for different number of connections

Fig. 6

Average latency for different number of RSUs

Fig. 7

Average throughput for different number of RSUs

To perform more rigorous analysis, we generate different scenarios having 5, 10, 15, 20, 30, 40, and 50 vehicles. In all the scenarios, the vehicles are moving at speeds between 60 and 120 km per hour, while the average speed is set to 80 km per hour, and each vehicle establishes at most one connection with an RSU. The results reveal that DMP tends to place RSU in segments near to areas of higher vehicle density. Figure 4 plots the average observed latency for DMP, Uniform Distribution, and CES for different traffic population. It can be seen that DMP provides superior performance in all the cases. The corresponding average throughput for all the cases is shown in Fig. 5. The results show that DMP provides an average reduction of 25% and 10% in latency over Uniform RSU placement and CES, respectively. Latency is highest for Uniform distribution because it does not consider vehicles’ mobility patterns when deploying RSUs. CES tends to deploy RSUs in segments where vehicles stay the most, while DMP tends to deploy RSUs in segments with highest vehicle influx. Therefore, DMP provides connection opportunities to more vehicles per unit time and thus it is able to achieve the lowest delay for all scenarios.

We plot average latency as function of number of RSU units for scenarios of 5, 10, 15, 20, 30, 40, and 50 vehicles in Fig. 6. The average delay is maximum in case of 1 RSU and 5 vehicles, because with only 1 RSU for direct connection and very few vehicles to establish multi-hop connections, each vehicle has to wait considerable amount of time before it can establish a connection and send its data packets. The situation improves by increasing the number of RSUs and the number of vehicles, both of these factors increase the opportunity to establish either direct or multi-hop connections. The corresponding average throughput is presented in Fig. 7. As expected, the minimum throughput is obtained for the case of 1 RSU and 5 vehicles. The performance improves considerably with increasing number of RSUs. It is evident, DMP outperforms Uniform Distribution in all these cases with an improvement of up to 33%. However, the throughput provided by CES is on average 2% more then the throughput provided by DMP. It is expected since Uniform distribution does not consider vehicles’ mobility patterns when deploying RSUs. CES tends to deploy RSUs in segments where vehicles stay the most, while DMP tends to deploy RSUs in segments with highest vehicle influx. Therefore, CES allows vehicles to transmit more data due to greater connection lifetime and thus it is able to provide the best throughput.

7 Conclusion

In this work, we have studied the RSU deployment strategy for vehicular ad hoc networks under a highway-like scenario, where each vehicle can access an RSU in two different ways: direct access and multi-hop relaying. Two types of RSU distribution schemes have been compared. One is our optimized Delay Minimization Problem (DMP model) and other is Uniform Distribution. Simulation results show that our proposed model outperforms Uniform Distribution in almost all cases. DMP model suggests us the best RSU deployment strategy by keeping in view the total deployment budget such that the overall latency of the network is minimized. This can be very beneficial in the timely delivery of alerts in case of an incident, and also provides improvements in the aggregate throughput of the network.