Delay Bounded Roadside Unit Placement in Vehicular Ad Hoc Networks

Abstract

The placement of roadside units (RSUs) is a difficult and yet important issue in vehicular networks. If too few RSUs are placed, the system performance would be very poor. However, with too many RSUs, it would incur high installation cost and maintenance cost of these RSUs. In this paper, we study the problem of delay bounded roadside unit placement (DRP) in vehicular networks. For a given delay bound, our objective is to place the minimal number of RSUs in the system such that a message from any of RSUs in the region can be disseminated to all vehicles within the given delay bound. We consider two cases of RSUs, the case that all RSUs are interconnected through wired lines (called DRP-L problem) and the case that RSUs connect to other RSUs through wireless link (called DRP-W problem). We first prove that both DRP-L and DRP-W problems are NP-hard. Then, we propose several heuristic algorithms to solve DRP-L and DRP-W problems, respectively. Extensive simulations have been conducted to show that the performance of our proposed methods is superior to the other methods.

1. Introduction

Vehicular networks (VANETs) have recently attracted great interest in the research community and intervehicle communication is becoming a promising field of research [1]. A vehicular network consists of two types of nodes, the nodes of vehicular on-board units (OBUs) that are installed on the vehicles and the nodes of roadside units (RSUs) that are installed at roadside to form the backbone (or infrastructure) network. A vehicle can communicate with other vehicles either directly by using OBUs, if they are within each other's transmission range, or otherwise through the RSUs. RSUs can be interconnected through wired lines or wireless communications. They allow passing vehicles to collect data from or deposit data into them. The primary use of vehicular networks is for information dissemination, routing, geocasting, and data delivery [2–5]. That is, whenever a node (event source) has some information such as road accidents and traffic congestion, it can use the vehicular network to broadcast the information to all vehicles in a region efficiently. Meanwhile, the proper placement of RSUs is crucial for the new generation ITS applications, such as content downloading [6–8] and content distribution [9–11]. In a word, the overall performance can be improved by placing additional RSUs in the vehicular networks.

The performance of the vehicular network highly relies on the placement of RSUs. On one extreme case, if there is no RSU installed in the system, then, the information propagation would only rely on one vehicle passing to another nearby vehicle. It would take a long time for all vehicles in a region to receive the information (some of them could never receive it) in this case. On the other extreme case, if a sufficient number of RSUs are installed in a region such that anywhere in the region is covered by the signal of at least one RSU, then, a message can be broadcasted to all RSUs via either the backbone network of RSUs or passing by vehicles and it is further broadcasted to all vehicles by RSUs in one hop. The information dissemination can be done in a very efficient way in this case. Thus, the placement of RSUs is a difficult issue. With the placement of too few RSUs, the system performance would be poor. However, with too many RSUs, it would incur high installation cost and maintenance cost of these RSUs. It is important to find the optimal solution that places the minimal number of RSUs and meets the performance requirements.

In this paper, we study the problem of delay bounded roadside unit placement (DRP) in vehicular networks. We are given a delay bound. The objective is to place the minimal number of RSUs in the system such that a message from any of RSUs in the region can be disseminated to all vehicles within the given delay bound. We consider two cases of RSUs, the case that all RSUs are interconnected through wired lines (called DRP-L problem) and the case that RSUs connect to other RSUs through wireless link (called DRP-W problem). We first prove that both DRP-L and DRP-W problems are NP-hard. Then, we propose several algorithms to solve DRP-L and DRP-W problems, respectively.

Our problem is different from the previous works of RSUs placement in two aspects: (1) we consider both wired connection of RSUs and wireless connection of RSUs; (2) we consider delay bounded information dissemination, which is desired by many real-time applications in vehicular networks.

The rest of this paper is organized as follows. Previous studies are summarized in Section 2. We present the system model and the problem in Section 3. The detailed description of our DRP-L problem and DRP-W problem are in Sections 4 and 5, respectively. In Section 6, we evaluate our proposed approach by comparing it with different environment. We conclude this paper in Section 7.

2. Related Work

Nowadays, there are many studies of the capacity, delay, and coverage of the wireless hybrid infrastructure (i.e., the base stations and mobile nodes) [12–14], data multicast, and message dissemination [15–18] in wireless networks. In particular, there are some published work about the node and AP placement problem in wireless sensor networks [19–28]. Liu et al. [20] investigated the relay node placement in two-tiered wireless sensor networks and proposed several approximation algorithms to solve the minimum relay-node placement problem. Lloyd and Xue [21] studied two versions of relay node placement problems. One is the single-tiered relay node placement problem and the other is the two-tiered relay node placement problem. Zhang et al. [22] investigated four versions of relay node placement problems, which were single-tiered placement with base stations, single-tiered placement without base stations, two-tiered placement with base stations, and two-tiered placement without base stations. Then, they proposed several polynomial time algorithms to solve the problems. In [23], the authors addressed the full fault-tolerant relay node placement problem and partial fault-tolerant relay node placement. In [24, 25], the authors considered a heterogeneous wireless sensor network consisting of three kinds of nodes: base stations, sensor nodes, and relay nodes. They studied the scenario where relay nodes can be placed only at certain candidate locations. In [26], the authors addressed a new problem in which the network cost is minimized while the resulting lifetime is at least equal to a given value. Then, they proved that this problem was NP-hard and derived a lower bound on the minimum number of sensors required. In [27, 28], the authors proposed two optimal node deployment patterns to minimize the number of nodes for completely covering a long belt. Also, there are some published work about the node problem in wireless networks [29, 30]. Zhang et al. [29] studied the optimal placement of APs such that the total cost of all APs is minimized, subject to the constraint that the traffic demand for each client can be fulfilled. Zhou et al. [30] investigated the minimal number of APs placement problem, so that both fault tolerance and QoS constraints can be satisfied. All above node placement studies are most related to our problem.

Moreover, there is some published work related to the problem of increasing the performance of vehicular opportunistic networks with the deployment of RSUs or stationary relay nodes [31–36]. In [31], authors addressed the problem of optimally placing gateways in vehicular networks to minimize the average number of hops from access points (APs) to gateways, so that the communication delay can be minimized and the average capacity of each AP can be maximized. Therefore, they found the optimal placement of gateways to minimize the average number of hops from APs to gateways in 1D vehicular networks and 2D vehicular networks, respectively. This previous work was extended in [32], where the authors showed that the problem of optimal relay node placement is a NP-hard problem and proposes an integer linear programming (ILP) formulation for this problem. Two heuristic algorithms were also presented. One of the algorithms aimed at minimizing the number of hop counts between source-destination terminal nodes, while the other aimed at minimizing the average message delivery time to the destination. Nevertheless, both algorithms also attempted to minimize the number of required relay nodes in the network. Lochert et al. [33] presented their solution of RSU placement for a VANET traffic information system using a genetic algorithm. In order to cope with the highly partitioned nature of a VANET in an early deployment stage, they identified good spots for RSUs from a set of possible positions that are initially given. Barrachina et al. [34] proposed a density-based road side unit deployment policy (D-RSU), specially designed to obtain an efficient system with the lowest possible cost to alert emergency services in case of an accident. In [35], the authors considered capacity cost tradeoffs for vehicular access networks with three cases of wireless access infrastructure, such as cellular BSs, wireless mesh backbones (WMBs), and roadside access points (RAPs). Reis et al. [36] studied the benefits of deploying RSUs to improve communications in highway scenarios. All the RSUs or stationary relay nodes placement problems in vehicular ad hoc networks are helpful for us to solve our RSUs placement problem.

The works in [14, 37–39] are most related to our problem. In [37], the authors solved the optimal schedule problem of turning RSUs on and off within a given time period so that the overall energy consumption in the system was minimized while the network connectivity was still maintained. They also divided the problem into two subproblems called the snapshot scheduling problem and the snapshot selection problem. However, they only considered all the RSUs connected through wired lines. In [14, 38], the authors studied the problem of optimal wireless relay placement (RPP) for sensory data collection from the vehicles. They also proposed heuristic algorithms to get the near-optimal results in a reasonable computing time. They proposed an approximate algorithm for the RPP with given vehicle traces (D-RPP) and proposed an algorithm for solving the RPP without a priori knowledge about future vehicle traces (N-RPP), which exploited regularity extracted from historical traces. The work of [39] studied two AP deployment problems and proved both problems are NP-complete. Then, they developed several optimal and approximation algorithms for different topologies of mobility graphs. However, delay bounded placement is not considered in prior research.

The difference between their works and ours is that our objective is minimizing number of RSUs rather than maximizing data collection in vehicular networks. Meanwhile, we consider two cases of placement of wired and wireless RSUs. In a word, our objective is to design an optimal placement scheme for both wired and wireless RSUs; the information disseminates to all the vehicles in the network within the given delay bound and the number of RSUs is minimized. To the best of our knowledge, our work is the first to study this problem in the literature.

3. System Model and Problem Formulation

In this section, we give the system model used in our analysis to solve the DRP problem; then, we formally formulate the problem.

3.1. System Model

A VANET system consists of a set of vehicles equipped with OBUs and a set of RSUs that are installed at the road side. Since, in this paper, we are only concerned about the placement of RSUs, we do not consider the nodes of vehicles. Whenever there is an emergency or road accident, a user or traffic policeman would report the emergency to an information center, and the information center would broadcast an emergency message to all vehicles on road through RSUs. For the vehicles that are not currently within the direct communication range of RSUs, the message will be forwarded to them via other vehicles. A vehicle can only forward a message to another vehicle if they are within each other's transmission range. We assume that the transmission time of a message between two vehicles is negligible, compared with time that a vehicle carries the message on the road and forwards it to another vehicle when it comes to the range of the other vehicle (i.e., the carry-and-forward model).

We consider the DRP problem in two cases: (1) RSUs are interconnected by wired lines and (2) RSUs are interconnected by wireless link. We assume all RSUs have the same transmission range. In the case that RSUs are interconnected by wired lines, we assume the communication between RSUs takes no time (the delay is 0). In the case of DRP-W problem, we further assume that a wireless RSU only receives the message from a nearby RSU but never gets the message from a passing vehicle. Once it receives a message, an RSU would broadcast the message immediately. When two RSUs are within each other's transmission range, they can communicate directly via wireless link.

Given the road map of a region, it has to decide the possible candidate sites for installing RSUs. The candidate sites are the locations where the RSUs may be installed but are not yet. The RSUs are usually installed at intersections of roads, and, sometimes, they are installed along a highway or bridge for relay purpose if the highway or bridge is too long. Suppose we are given a set of candidate sites, denoted by $V=\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_n\}$ . With the road map and the set of candidate sites, we could find the optimal subset of candidate sites to install the RSUs. Before we give our research problem, we first define the neighboring relationship between two candidate sites as follows.

Definition 1.

Two candidate sites $v_i$ and $v_j$ , $v_i$ and $v_j$ in V, are neighbors if and only if there is no other candidate site lying between $v_i$ and $v_j$ along the road from $v_i$ to $v_j$ .

The road map can be represented by a undirected weighted graph $G(V,E)$ , where V is the set of candidate sites for placing RSUs. There is an edge $e(v_i,v_j)$ in E if and only if $v_i$ and $v_j$ are neighbors. Each edge is associated with an expected link delay, which is the expected delay from $v_i$ to its adjacent vertex $v_j$ .

Now we consider the link delay between two candidate sites along the road without the help of RSUs infrastructure. We need to estimate the delay of message propagation done by vehicles passing from one to another under the normal situation of road traffic. In the vehicular networks, there are many forwarding methods. In this paper, we only consider the epidemic forwarding method where if vehicles fall into each other's transmission range, they can forward messages successfully. Let $d_{ij}$ denote the expected link delay between two neighboring candidate sites $v_i$ and $v_j$ . Different from link delay model proposed by [40], we focus on the normal, not light, traffic layout, where each road has one- or two-way traffic. Based on the model proposed in [2, 41], our link delay estimation is composed of transmission delay and propagation delay. Let $d_{ij}^t$ and $d_{ij}^p$ denote the expected transmission delay and propagation delay between two neighboring candidate sites $v_i$ and $v_j$ , respectively; we have

$$\begin{array}{cc}& d_{ij}^t=\left(\mathrm{1}-e^{-R·{\rho }_{ij}}\right)·\frac{d\left(i,j\right)·c}{R_v},\\ d_{ij}^p=e^{-R·{\rho }_{ij}}·\frac{d\left(i,j\right)}{{\bar{v}}_{ij}},\end{array}$$

(1)

where $R_v$ is the wireless transmission range of vehicles, ${\rho }_{ij}$ is the density of vehicles on road segment $e(v_i,v_j)$ , c is the average one-hop packet transmission delay, $d(i,j)$ is the Euclidean distance of road segment $e(v_i,v_j)$ , and $\bar{v}$ is the average vehicle speed on road segment $e(v_i,v_j)$ . Thus, the link delay $d_{ij}$ is

$$\begin{array}{cc}& d_{ij}=d_{ij}^t+d_{ij}^p.\end{array}$$

(2)

Due to propagation delay several orders of magnitude longer than the transmission delay, we assume that the link delay approximately equals the propagation delay. The assumption is acceptable as the unit of propagation delay is a second and the unit of transmission delay is a millisecond.

After computing the link delay of edges of graph $G(V,E)$ , we define $D_{ij}$ , the expect information dissemination delay between any two candidate sites $v_i$ and $v_j$ . Note that $D_{ij}$ is the delay estimated under the condition that no RSU infrastructure is used. It will help us to determine, for a given delay bound, how far a message can be propagated from a point without the help of RSUs. Let $N(i)$ denote the neighbor of node i; we calculate $D_{ij}$ as follows:

$$\begin{array}{cc}& D_{ij}=\left\{\begin{array}{cc}\mathrm{0},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}j=i;\hfill \\ d_{ij},\hfill & \text{else}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}j\in N\left(i\right);\hfill \\ \underset{k\in N\left(i\right)}{\min }\{D_{ik}+D_{kj}\},\hfill & \text{otherwise}.\hfill \end{array}\right.\end{array}$$

(3)

3.2. Problem Formulation

The delay bounded RSUs placement problem (DRP for short) is formally defined as follows. Given a delay bound Δ, DRP problem is to find the minimum number of candidate sites to install RSUs such that a message originating from any of RSUs can be propagated to all vehicles in the region within delay Δ through the help of RSUs.

The DRP problem under the case that RSUs are interconnected by wired lines is called DRP-L problem, and the problem under the case that there is no infrastructure for RSUs is called DRP-W problem.

Let $X_i$ denote whether site $v_i$ will be installed an RSU or not. Consider $X_i=\mathrm{1}$ if site $v_i$ is selected to install an RSU and $X_i=\mathrm{0}$ otherwise. Our objective is to minimize the total number of RSUs installed in the region; that is,

$$\begin{array}{cc}& \min {\displaystyle \sum }_{i\in V}‍X_i\end{array}$$

(4)

subject to

$$\begin{array}{cc}& X_i\in \left\{\mathrm{0,1}\right\},\hspace{1em}\forall i\in V,\end{array}$$

(5)

$$\begin{array}{cc}& D_{ij}*X_i*X_j\le T,\hspace{1em}\forall i,j\in V.\end{array}$$

(6)

Constraint 5 indicates that there is at most one RSU in each candidate site. Constraint 6 says that if any two candidate sites $v_i$ and $v_j$ place an RSU, the best case information dissemination delay between $v_i$ and $v_j$ is not more than the delay bound Δ.

4. DRP-L Problem

In this section, we first give some definitions for solving DRP-L problem. Then, we reduce reduction from constrained minimum vertex cover problem on bipartite graphs (MIN-CVCB) to DRP-L problem and prove it is NP-hard. Finally, we give our solution for DRP-L problem.

4.1. Definition

In the case of DRP-L problem, we assume that the communication delay between RSUs is zero because all RSUs are interconnected through wired lines. Then, we model the system as the delay bounded graph and transform the DRP-L problem to the vertex cover problem. Before we study the DRP-L problem, we first give some definitions as follows.

Definition 2.

Delay bounded vertex cover set of a candidate site $v_x$ , denoted by $\Delta \text{-}VC(v_x)$ , is a set of candidate sites where the expected $\text{end-end}$ propagation delay from $v_x$ to any node in $\Delta \text{-}VC(v_x)$ is within delay bound Δ.

The expected end-end propagation delay between two candidate sites $v_x$ and $v_i$ includes the expected information dissemination delay from $v_x$ to $v_i$ and the expected end delay from $v_i$ to all vehicles on the roads that $v_i$ covers. As the expected information dissemination delay from $v_x$ to $v_i$ is several orders of magnitude longer than the expected end delay from $v_i$ to all vehicles, we assume that the expected end delay from $v_i$ to all vehicles that $v_i$ covers approximately equals $\mathrm{0}$ . Therefore, $\Delta \text{-}VC(v_x)$ can be represented as

$$\begin{array}{cc}& \Delta \text{-}VC\left(v_x\right)=\{v_i\hspace{0.17em}|\hspace{0.17em}{D}_{xi}\le \Delta ;\hspace{0.17em}\hspace{0.17em}\forall v_i\in V\left(G\right)\}.\end{array}$$

(7)

Definition 3.

Delay bounded edge cover set of a candidate site $v_x$ , denoted by $\Delta \text{-}EC(v_x)$ , is a set of edges where the $\text{end-end}$ propagation delay from $v_x$ to any part of the edge $e(v_i,v_j)$ in $\Delta \text{-}EC(v_x)$ is within delay Δ.

The expected $\text{end-end}$ propagation delay from $v_x$ to any part of edge $e(v_i,v_j)$ includes the expected information dissemination delay from $v_x$ to the end of edge $v_i$ or $v_j$ and the expected information dissemination delay on the roads $e(v_i,v_j)$ . Therefore, $\Delta \text{-}EC(v_x)$ can be represented as

$$\begin{array}{l}\Delta \text{-}EC\left(v_x\right)=\left\{e(v_i,v_j)\hspace{0.17em}|\hspace{0.17em}{v}_i\in \Delta \text{-}VC\left(v_x\right)\wedge v_j\in \Delta \text{-}VC\left(v_x\right)\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\phantom{e(v_i,v_j\text{idd})\hspace{0.17em}|\hspace{0.17em}}\wedge (D_{xi}+d_{ij}\le \Delta \vee D_{xj}+d_{ji}\le \Delta )\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\phantom{e\left(v_i,v_j\text{did}\right)\hspace{0.17em}|\hspace{0.17em}}\wedge e\left.\left(v_i,v_j\right)\in E\left(G\right);\forall v_i,v_j\in V\left(G\right)\right\}.\end{array}$$

(8)

As shown in Figure 1, when given a delay bound Δ, a message is sent from the RSU A to the vertexes A, B, and C, so that delay bounded vertex cover set of the RSU A is $\Delta \text{-}VC(A)=\{A,B,C\}$ and delay bounded edge cover set of the RSU A is $\Delta \text{-}EC(A)=\{e(A,B),e(B,C)\}$ .

Figure 1

An example of delay bounded vertex cover set and edge cover set.

Now, we introduce a delay bounded graph $G_{\Delta }(V_{\Delta }=V\cup V_E,E_{\Delta })$ , where one side of nodes in this bipartite graph is $V=\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_n\}$ and the other side of nodes is $V_E=\{v_{e_{\mathrm{1}}},v_{e_{\mathrm{2}}},\dots ,v_{e_m}\}$ . An edge $e(v_i,v_{e_j})$ in $E_{\Delta }$ if and only if the $\text{end-end}$ propagation delay from $v_i$ to any part of the road of $e_j$ is within delay Δ. That is,

$$\begin{array}{cc}& G_{\Delta }=\{e(v_i,v_{e_j})\hspace{0.17em}|\hspace{0.17em}{e}_j\in \Delta \text{-}EC\left(i\right);\hspace{0.17em}\hspace{0.17em}\forall v_i\in V,\hspace{0.17em}{v}_{e_j}\in V_E\}.\end{array}$$

(9)

Figure 2 presents an illustrative example of the delay bounded graph. In Figure 2(a), the system has four candidate nodes $A,B,C$ , and D. We model the system as a road graph G. When delay bound $\Delta =\infty$ , we get the delay bounded graph $G_{\infty }$ . As shown in Figure 2(b), it means there is no limit to delay bound, so each vertex in $V_{\mathrm{1}}$ covers each vertex in $V_{\mathrm{2}}$ . When delay bound $\Delta =\mathrm{4}$ is given, we should cut off the edge $e(v_A,v_{e(C,D)})$ , as the vertex $v_A$ does not cover the edge $e(C,D)$ within the delay bound $\Delta =\mathrm{4}$ . Similarly, we cut off the edges which $v_B$ , $v_C$ , and $v_D$ do not cover. Then, we get the delay bounded graph $G_{\mathrm{4}}$ as shown in Figure 2(c). While delay bound $\Delta =\mathrm{2}$ , we get $G_{\mathrm{2}}$ in the same way as shown in Figure 2(d). Notice that we have some isolate vertex, $v_D$ , $v_{e(C,D)}$ , and $v_{e(D,A)}$ . That means when given a minimal delay bound $\Delta =\mathrm{2}$ , we cannot cover the road $e(C,D)$ even if all candidate sites are placed RSUs.

Figure 2

An example of the delay bounded graph.

Obviously, if there are no isolate vertex, $G_{\Delta }=(V_{\Delta },E_{\Delta })$ is a bipartite graph.

Lemma 4.

Delay bounded graph $G_{\Delta }=(V_{\Delta },E_{\Delta })$ is a bipartite graph when delay bound $\Delta \ge \max \{d_{ij}\hspace{0.17em}|\hspace{0.17em}\forall e(i,j)\in E(G)\}$ , while the number of vertexes is $\left|V_{\Delta }\right|=+n$ and the number of edges is $\left|E_{\Delta }\right|={\sum }_{i=\mathrm{0}}^{m-\mathrm{1}}‍|\Delta \text{-}EC(v_i)|$ .

Proof.

According to definition of bipartite graph [42], the bipartite graph is a graph whose vertices can be divided into two disjoint sets $V\mathrm{1}$ and $V\mathrm{2}$ such that every edge connects a vertex in $V\mathrm{1}$ to one in $V\mathrm{2}$ . Therefore, we should conduct these two disjoint sets $V\mathrm{1}$ and $V\mathrm{2}$ .

According to definition of $G_{\Delta }$ , we let $V\mathrm{1}$ be the vertex set and let $V\mathrm{2}$ be the edge set of the road graph, respectively. Thus, the number of $V\mathrm{1}$ is m and the number of $V\mathrm{2}$ is n. When delay bound $\Delta \ge \max \{d_{ij}\hspace{0.17em}|\hspace{0.17em}\forall e(i,j)\in E(G)\}$ , it means there is no isolate node in vertex sets $V\mathrm{1}$ and $V\mathrm{2}$ . So delay bounded graph $G_{\Delta }=(V_{\Delta },E_{\Delta })$ is a bipartite graph, and the number of vertexes is $\left|V_{\Delta }\right|=m+n$ . Meanwhile, we have the set of edges

$$\begin{array}{cc}& E_{\Delta }={\displaystyle \bigcup }_{i=\mathrm{0}}^{m-\mathrm{1}}‍\Delta \text{-}EC\left(v_i\right).\end{array}$$

(10)

Thus, the number of edges is $\left|E_{\Delta }\right|={\sum }_{i=\mathrm{0}}^{m-\mathrm{1}}‍|\Delta \text{-}EC(v_i)|$ .

Our problem is transformed into the minimal vertex set cover problem in $G_{\Delta }=(V_{\Delta },E_{\Delta })$ , that is, to choose a minimal subvertex set V that can cover all edge set in $V_E$ . Then, we can install RSUs at the vertices in minimal cover set. By doing so, any message propagated from an RSU to other candidate sites shall not exceed the given delay bound Δ, because the delay between any pair of candidate sites is within Δ if there exists an edge between them in $G_{\Delta }$ . We use Figure 2(a) for example to explain the problem transform. Suppose the delay bound is $\mathrm{3}$ units. The transmission range of an RSU is set to part of one road segment. According to Definition 3, vertex $v_A$ covers the edge set $\{e(v_A,v_B),e(v_B,v_C)\}$ within the delay bound. Similarly, vertex $v_B$ covers the edge set $\{e(v_A,v_B),e(v_B,v_C)\}$ , vertex $v_C$ covers the edge set $\{e(v_A,v_B),e(v_B,v_C),e(v_C,v_D)\}$ , and vertex $v_D$ covers the edge set $\{e(v_C,v_D)\}$ within the delay bound. Therefore, our problem is transformed into the minimal vertex set cover problem which chooses a minimal subvertex set that can cover the edge set.

The DRP-L problem is difficult to solve, as shown in the following theorem.

Theorem 5.

The DRP-L problem is NP-hard.

Proof.

To provide the evidence of NP-hardness, we provide a polynomial reduction from constrained minimum vertex cover problem on bipartite graphs (MIN-CVCB) [43] to DRP-L.

Considering the MIN-CVCB problem, the inputs of MIN-CVCB are a graph $G=(V,E)$ with vertex bipartition $V=U\cup L$ and two integers $k_u$ and $k_l$ . The objective is to find a minimum vertex cover in G with at most $k_u$ vertices in U and at most $k_l$ vertices in L.

If we input delay bounded graph $G_{\Delta }=(V_{\Delta },E_{\Delta })$ with vertex bipartition $V_{\Delta }=V\cup V_E$ and two integers $k_u=n$ and $k_l=\mathrm{0}$ , obviously, the DRP-L equals the MIN-CVCB problem.

4.2. DRP-L Algorithm

As proven in Theorem 5, the DRP-L problem is NP-hard. So there is not a deterministic polynomial time algorithm to solve it. Therefore, we focus on designing an efficient approximation algorithm to solve the DRP-L problem. Due to the monotonicity of minimum vertex set function, greedy algorithm is a competitive candidate. As our greedy algorithm, we can select the candidate sites that maximize the delay bounded coverage gain in each iteration. Let W be the set of all covered road segments. When we consider installing an RSU at site $v_i$ , $\Delta \text{-}EC(v_i)$ may include some road segments that are already delay bounded covered by the existing RSUs. Therefore, only the new delay bounded covered road segments are regarded as the gain of this considered candidate site. We define the $g(i)$ as the delay bounded coverage gain of installing an RSU at site $v_i$ . Then, we have

$$\begin{array}{cc}& g\left(i\right)=\left|\Delta \text{-}EC\left(v_i\right)\cap \left(E\setminus W\right)\right|.\end{array}$$

(11)

Our algorithm for DRP-L is presented as Algorithm 1. The major steps of Algorithm 1 are as follows. First, we compute the expected information dissemination delay $D_{ij}$ between any two candidate sites in line $\mathrm{2}$ ; then, we calculate the delay bounded vertex cover set and delay bounded edge cover set of all candidate sites. This is accomplished in lines 3–5. After that, we compute delay bounded coverage gain of all unselected candidate sites iteratively in lines 7–9. Next, we find the best node which has the maximal delay bounded coverage gain. This is accomplished in line $\mathrm{10}$ . In lines 11-12, we add the best node to the set of placement RSUs and remove all the delay bounded edge cover set from the set of road segments. Finally, when all the road segments are covered within the given delay bound, we identify the placement RSUs set of our solution in line $\mathrm{14}$ .

Algorithm 1: DRP-L algorithm.

Input:

  $$G=(V,E)$$ : The road map;

  $$\mathrm{\Delta }$$ : The delay bounded;

  $$D_{ij}$$ : The information dissemination delay from RSU i to other nodes j

Output:

    $$\mathcal{R}$$ : The placement set of installing RSUs

(1) $$\mathcal{R}=\varnothing$$ ; $$U=E$$ ;

(2) For all $$i,j\in V$$ , initial $$D_{ij}$$ according to 3;

(3) for all $$v_i\in V$$   do

(4)  Compute $$\mathrm{\Delta }\mathrm{\hspace{0.17em}\hspace{0.17em}}-\mathrm{\hspace{0.17em}\hspace{0.17em}}VC(v_i)$$ and $$\mathrm{\Delta }\mathrm{\hspace{0.17em}\hspace{0.17em}}-\mathrm{\hspace{0.17em}\hspace{0.17em}}EC(v_i)$$ ;

(5) end for

(6) while   $$U\ne \mathrm{\varnothing }$$   do

(7)  for  all unselected $$v_i\in V$$   do

(8)   Calc delay bounded coverage gain $$g(i)$$ according to 11;

(9)  end  for

(10)  $$v^{\mathrm{*}}=\{v_i\hspace{0.17em}|\hspace{0.17em}\max \left\{g\left(i\right)\right\},\forall v_i\in V\}$$ ;

(11)  $${\mathcal{R}}_L={\mathcal{R}}_L\bigcup \left\{v^{\mathrm{*}}\right\}$$ ;

(12)  $$U=U\setminus \mathrm{\Delta }\mathrm{\hspace{0.17em}\hspace{0.17em}}-\mathrm{\hspace{0.17em}\hspace{0.17em}}EC\left(v^{\mathrm{*}}\right)$$ ;

(13) end while

(14) return   $$\mathcal{R}$$

Figure 3 shows an illustrative example of the DPR-L algorithm. As shown in Figure 3(a), the graph G has $\mathrm{4}*\mathrm{4}$ candidate sites ( $v_{\mathrm{0}}~v_{\mathrm{15}}$ ), which are numbered from the left to the right and from the top to the bottom. Graph G includes $\mathrm{24}$ road segments. The transmission range of an RSU is set to one road segment. We further assume that the expected link delay of each road segment is 1 min, and the delay bound Δ is also set to 1 min. Figure 3(b) shows that, in the first iteration, $v_{\mathrm{5}}$ is selected to install an RSU, since the corresponding delay bounded coverage gain $g(\mathrm{5})=\mathrm{14}$ is the maximum one. The $\mathrm{14}$ black thick lines are the newly delay bounded coverage gain. Figure 3(c) shows that in the second iteration $v_{\mathrm{10}}$ is chosen to install an RSU, where the gray thick lines are the newly delay bounded coverage gain; that is, $g(\mathrm{10})=\mathrm{6}$ . Figure 3(d) shows the result of our DRP-L algorithm, which installs four RSUs at candidate sites $v_{\mathrm{2}}$ , $v_{\mathrm{5}}$ , $v_{\mathrm{8}}$ , and $v_{\mathrm{10}}$ .

Figure 3

An example of the DRP-L algorithm. (a) The undirected weighted graph $G(V,E)$ . (b) In the first iteration, choose $v_{\mathrm{5}}$ to instal an RSU greedily. The black thick lines are the newly delay bounded coverage gain. (c) In the second iteration, choose $v_{\mathrm{10}}$ to install an RSU greedily. The gray thick lines are the newly delay bounded coverage gain. (d) The result of the DRP-L algorithm.

4.3. Analysis

We analyze the time complexity of Algorithm 1 as follows.

Theorem 6.

The time complexity of Algorithm 1 is $O(|V{|}^{\mathrm{3}}+\left|V\right|*(|V|+|E|)*L)$ , where $\left|V\right|$ is the number of candidate sites, $\left|E\right|$ is the number of road segments, and L is running rounds of Algorithm 1.

Proof.

Line $\mathrm{2}$ of Algorithm 1 computes $D_{ij}$ . The time complexity of $D_{ij}$ is $O(|V{|}^{\mathrm{3}})$ as we use Floyd-Warshall algorithm to compute the shortest path between any two candidate sites. In line $\mathrm{4}$ , the complexity of computing the delay bounded vertex cover set and edge cover set for each RSU placement is not more than V and E, respectively. Therefore, the complexity of line 3–5 is $|V{|}^{\mathrm{2}}+|V\left|*\right|E|$ . Then, it iteratively computes the delay bounded coverage gain for unselected candidate sites. The size of all unselected candidate sites is not more than $\left|V\right|$ , the calculation of delay bounded coverage gain is not more than $\left|E\right|$ and it will run L rounds. Thus, the time complexity of lines 7–9 is $O(|V\left|*\right|E|*L)$ . Next, it iteratively chooses the site which has the maximum delay bounded gain in line $\mathrm{10}$ and the time complexity is $O(|V{|}^{\mathrm{2}}*L)$ . Thus, the time complexity of lines 6–13 is $O(|V|*(\left|V\right|+\left|E\right|)*L)$ . Therefore, the total time complexity is $O(|V{|}^{\mathrm{3}}+\left|V\right|*(|V|+|E|)*L)$ .

Next, we analyse the approximation ratio of Algorithm 1. We denote the road segments of $G(V,E)$ in order in which they are covered by Algorithm 1. Let $l_{\mathrm{1}},\dots ,l_n$ be this numbering. For each road segment $l_k$ which is added to E, we define $e(l_k)=\mathrm{1}/g(i)$ , which equals the effectiveness of the newly installed RSUs in each iteration. Before we derive the approximation ratio, we have following lemma first.

Lemma 7.

Let ${\mathcal{R}}^{OPT}$ be the optimal solution to DRP-L. For each $k\in \{\mathrm{1},\dots ,n\}$ , one has $e(l_k)\le \left|{\mathcal{R}}^{OPT}\right|/(n-k+\mathrm{1})$ .

Proof.

Assume the optimal placement set ${\mathcal{R}}^{\text{OPT}}=o_{\mathrm{1}},o_{\mathrm{2}},\dots ,o_p$ . Now, we assume that the greedy algorithm has covered the road segments in W so far. Then, we know the that uncovered road segments, or $|E\setminus W|$ , are, at most, the intersection of all of the optimal sets intersected with the uncovered road segments:

$$\begin{array}{cc}& \left|E\setminus W\right|\le {\displaystyle \sum }_i^p\left|\Delta \text{-}EC\left(o_i\right)\cap \left(E\setminus W\right)\right|.\end{array}$$

(12)

In the greedy algorithm, we always choose the set with the maximal coverage gain, that is, the smallest effectiveness, so that we should have

$$\begin{array}{cc}& e\left(l_k\right)\le \frac{\mathrm{1}}{|\Delta \text{-}EC\left(o_i\right)\cap (E\setminus W)|},\end{array}$$

(13)

where $i=\mathrm{1,2},\dots ,p$ .

We substitute 12 and 13 in the following equation; then, we have

$$\begin{array}{l}\left|{\mathcal{R}}^{\text{OPT}}\right|={\displaystyle \sum }_{i=\mathrm{1}}^p\mathrm{1}\ge {\displaystyle \sum }_i^{p}e\left(l_k\right)\left|\Delta \text{-}EC\left(o_i\right)\cap \left(E\setminus W\right)\right|\\ \hspace{1em}\hspace{1em}\hspace{0.17em}\ge e\left(l_k\right)\left|E\setminus W\right|.\end{array}$$

(14)

In the iteration in which element $l_k$ was covered, $|E-W|$ contains at least $n-k+\mathrm{1}$ elements. Therefore, we have

$$\begin{array}{cc}& e\left(l_k\right)\le \frac{\left|{\mathcal{R}}^{\text{OPT}}\right|}{n-k+\mathrm{1}}.\end{array}$$

(15)

Theorem 8.

Let $\mathcal{R}$ be one's solution to DRP-L and let ${\mathcal{R}}^{OPT}$ be the optimal solution to DRP-L; then, $\left|\mathcal{R}\right|/\left|{\mathcal{R}}^{OPT}\right|\le \ln (n)$ .

Proof.

The theorem can be founded in a similar way as in [44]. We have

$$\begin{array}{l}\left|\mathcal{R}\right|={\displaystyle \sum }_{k=\mathrm{1}}^{n}e\left(l_k\right)\le {\displaystyle \sum }_{k=\mathrm{1}}^n\frac{\left|{\mathcal{R}}^{\text{OPT}}\right|}{n-k+\mathrm{1}}=\left|{\mathcal{R}}^{\text{OPT}}\right|*\left(\mathrm{1}+\frac{\mathrm{1}}{\mathrm{2}}+\cdots +\frac{\mathrm{1}}{n}\right)\\ \hspace{1em}\hspace{0.17em}\hspace{0.17em}=\left|{\mathcal{R}}^{\text{OPT}}\right|*\ln \left(n\right).\end{array}$$

(16)

5. DRP-W Problem

In this section, we investigate the DRP-W problem. We first prove that DRP-W problem is also NP-hard. Then, we propose our greedy and MST-based algorithm to solve the DRP-W problem.

5.1. DRP-W Greedy Algorithm

In the DRP-L problem, RSUs are interconnected to each other by wired line, and a wired RSU can be installed at any candidate site in the DRP-L algorithm. Compared with the DPR-L problem, each wireless RSU is interconnected by wireless link in the DRP-W problem. In this case, we should consider that each wireless RSU should be within the transmission range of an existing RSU. That is, DRP-W problem requires not only covering all the road segments within the delay bound but also connection of each wireless RSU. Therefore, if a candidate site falls outside the transmission area of any existing RSU, a wireless RSU cannot be placed at this candidate site. We use $d(x,y)$ to denote the Euclidean distance between two points x and y in the plane. We assume that all wireless RSUs have the same communication range $R>\mathrm{0}$ , where R are given constants. Following the above discussions, two placed wireless RSUs $r_x$ and $r_y$ can communicate directly with each other if and only if $d(r_x,r_y)$ is less than or equal to the communication range R.

The DRP-W problem is also difficult to solve, as shown in the following theorem.

Theorem 9.

The DRP-W problem is NP-hard.

Proof.

Let an instance ${\mathcal{L}}_{\mathrm{1}}$ of DRP-L be given by $G(V,E)$ . We construct an instance ${\mathcal{L}}_{\mathrm{2}}$ of DRP-W by $G(V,E)$ , where each RSU is within the transmission range of any other RSU. It is easy to see that a subset ${\mathcal{R}}^{\prime }\subseteq \mathcal{R}$ is an optimal solution to ${\mathcal{L}}_{\mathrm{1}}$ if and only if it is an optimal solution to ${\mathcal{L}}_{\mathrm{2}}$ . After that, we reduce the DRP-W problem to a DRP-L problem in a polynomial time.

The DRP-W problem is a complicated combinatorial optimization problem, and we first proposed a greedy algorithm to solve the DRP-W problem. The strategy of DRP-W greedy algorithm is the same as the DRP-L algorithm. In each iteration, we can select the candidate sites that maximize the delay bounded coverage gain. The major difference between DRP-L cases and ORP-W case is the interconnected way of RSUs. Note that a wired RSU can be installed at any candidate site in V. However, since a wireless RSU only communicate with other RSUs, it should be within the transmission range of an RSU. This difference is shown in line $\mathrm{3}$ . Therefore, if a candidate site falls outside of the transmission area of any existing RSU, it cannot be placed a wireless RSU. The details of our greedy algorithm are presented in Algorithm 2.

Algorithm 2: DRP-W greedy algorithm.

Input:

  $$G=(V,E)$$ : The road map;

  $$\mathrm{\Delta }$$ : The delay bounded;

  $$D_{ij}$$ : The information dissemination delay from RSU i to other nodes j

Output:

    $$\mathcal{R}$$ : The placement set of installing RSUs

(1) $$\mathcal{R}=\varnothing$$ ; $$U=E$$ ;

(2) while   $$U\ne \mathrm{\varnothing }$$   do

(3)  for all unselected $$v_i\in U$$ and $$v_i$$ is with the transmission range of an existing RSU  do

(4)   Compute $$\mathrm{\Delta }\mathrm{\hspace{0.17em}\hspace{0.17em}}-\mathrm{\hspace{0.17em}\hspace{0.17em}}VC(v_i)$$ and $$\mathrm{\Delta }\mathrm{\hspace{0.17em}\hspace{0.17em}}-\mathrm{\hspace{0.17em}\hspace{0.17em}}EC(v_i)$$ ;

(5)   Calc delay bounded coverage gain $$g(i)$$ according to 11;

(6)  end for

(7)   $$v^{\mathrm{*}}=\{v_i\hspace{0.17em}|\hspace{0.17em}\max \{g(i)\},\forall v_i\in V\}$$ ;

(8)   $${\mathcal{R}}_L={\mathcal{R}}_L\bigcup \{v^{\mathrm{*}}\}$$ ;

(9)   $$U=U\setminus \mathrm{\Delta }\mathrm{\hspace{0.17em}\hspace{0.17em}}-\mathrm{\hspace{0.17em}\hspace{0.17em}}VC(v^{\mathrm{*}})$$ ;

(10) end  while

(11) return   $$\mathcal{R}$$

5.2. DRP-W MST-Based Algorithm

In the previous section, we proposed the greedy algorithm. Each time we add a new RSU, we need to evaluate all candidate sites for the RSUs and select the best combination. The greedy algorithm can lead to good placement of RSUs; however, its time complexity is a bit high. Therefore, we propose a more efficient algorithm in this section. Our solution for DRP-W is composed of two steps. In step one, we apply Algorithm 1 for DRP-W to compute a placement set ${\mathcal{R}}_a$ of installing RSUs. As in the DRP-L problem, each placed RSUs ${\mathcal{R}}_a$ is interconnected by wired line, so the road segments are covered by these RSUs within the delay bound. However, in the DRP-W problem, these RSUs are wireless RSUs and each RSU may not be connected if distance between them is larger than transmission range. In order to connect these wireless RSUs, more wireless RSUs are needed. In step two, we apply another algorithm for minimal Steiner tree (MST) problem [45] to augment ${\mathcal{R}}_a$ by some other wireless RSUs ${\mathcal{R}}_b$ so that the network is connected. The union of ${\mathcal{R}}_a$ and ${\mathcal{R}}_b$ is output as our solution for DRP-W problem. We call this MST-based algorithm.

Before we use MST-based algorithm to solve DRP-W problem, we define the communication set of placed RSUs and weighted communication graph (WCG) in the following.

Definition 10.

Communication set of placed RSUs $\mathcal{R}$ , denoted by ${\mathcal{C}}_{\mathcal{R}}$ , is a set of candidate sites where each candidate site is at least within an RSU transmission range.

Definition 11.

Weighted communication graph (WCG) is an undirected weighted graph $G_{\text{wcg}}=\text{WCG}(V_{\text{wcg}},E_{\text{wcg}})$ , while the vertex set as $V_{\text{wcg}}={\mathcal{R}}_a\cup {\mathcal{C}}_{{\mathcal{R}}_a}$ consists of the RSUs placement set ${\mathcal{R}}_a$ union, the set of communication set ${\mathcal{C}}_{{\mathcal{R}}_a}$ , and the edge set $E_{\text{wcg}}$ defined as follows. For any two RSUs $r_i,r_j\in {\mathcal{R}}_a$ , $E_{\text{wcg}}$ contains the undirected edge $e(r_i,r_j)$ if and only if $d(r_i,r_j)\le R$ , and the weight of $e(r_i,r_j)$ is $\mathrm{2}$ . For an RSU $r_x\in {\mathcal{R}}_a$ and a candidate site $v_y\in {\mathcal{C}}_{{\mathcal{R}}_a}$ , $E_{\text{wcg}}$ contains the undirected edge $e(r_x,v_y)$ if and only if $d(r_i,r_j)\le R$ , and the weight of $e(r_x,v_j)$ is $\mathrm{1}$ .

The WCG characterizes all possible communications between the placed RSUs and the unselected candidate sites. The weight of each edge is defined as the number of placed RSUs. As shown in Algorithm 3, we first apply Algorithm 1 to obtain an installing RSUs set ${\mathcal{R}}_a$ in line $\mathrm{1}$ . Then, we construct weighted communication graph $G_{\text{wcg}}$ based on the placed RSUs in line $\mathrm{2}$ . In line $\mathrm{3}$ , we consider computing a low weight Steiner tree ${\mathcal{T}}_b$ , spanning the node set ${\mathcal{R}}_a\cup {\mathcal{C}}_{{\mathcal{R}}_a}$ of WCG. Let the set of Steiner points in the tree be ${\mathcal{R}}_b$ so that the network is connected. Finally, we obtain the placement set $\mathcal{R}={\mathcal{R}}_a\cup {\mathcal{R}}_b$ of installing wireless RSUs in line $\mathrm{4}$ .

Algorithm 3: DRP-W MST-based algorithm.

Input:

  $$G=(V,E)$$ : The road map;

  $$\mathrm{\Delta }$$ : The delay bounded;

  $$D_{ij}$$ : The information dissemination delay from RSU i to other nodes j

Output:

  $$\mathcal{R}$$ : The placement set of installing wireless RSUs

(1) Apply Algorithm 1 to obtain a installing RSUs set $${\mathcal{R}}_a$$ ;

(2) Construct the weighted communication graph $$G_{\text{wcg}}$$ based on the placed RSUs;

(3) Apply an approximation algorithm for MST to obtain additional wireless RSUs set $${\mathcal{R}}_b$$ by using $${\mathcal{R}}_a$$ as an input of MST,

   such that G is connected;

(4) return   $$\mathcal{R}={\mathcal{R}}_a\bigcup {\mathcal{R}}_b$$

We illustrate the major steps of Algorithm 3 via the example shown in Figure 4. The graph G also has $\mathrm{4}*\mathrm{4}$ candidate sites ( $v_{\mathrm{0}}~v_{\mathrm{15}}$ ), which are numbered from the left to the right and from the top to the bottom. The parameter of graph G is the same as Figure 3. Figure 4(a) shows that, by applying Algorithm 3, we obtain an installing RSUs set ${\mathcal{R}}_a=\{v_{\mathrm{2}},v_{\mathrm{5}},v_{\mathrm{8}},v_{\mathrm{10}}\}$ . Figure 4(b) shows the weighted communication graph based on the placed RSUs. The graph $G_{\text{wcg}}$ has $\mathrm{4}$ RSUs and $\mathrm{6}$ candidate sites. In Figure 4(c), we obtain a Steiner tree spanning the node set ${\mathcal{R}}_a\cup {\mathcal{C}}_{{\mathcal{R}}_a}$ . Here we used the MST-based approximation algorithm [46] to obtain the Steiner tree. The Steiner tree has two Steiner nodes $v_{\mathrm{1}}$ and $v_{\mathrm{9}}$ , leading to the use of two more wireless RSUs. Figure 4(d) shows our solution for DRP-W MST-based algorithm, which uses $\mathrm{6}$ wireless RSUs. Figure 4(e) shows the optimal solution, which uses $\mathrm{4}$ wireless RSUs.

Figure 4

(a) Apply Algorithm 1 and obtain an installing RSUs set ${\mathcal{R}}_a=\{v_{\mathrm{2}},v_{\mathrm{5}},v_{\mathrm{8}},v_{\mathrm{10}}\}$ for $\mathrm{4}*\mathrm{4}$ candidate sites. (b) Construct the weighted communication graph based on the placed RSUs. (c) A Steiner tree based on the WCG. (d) The result of our DRP-W MST-based algorithm, which places $\mathrm{6}$ RSUs. (e) The optimal solution, which places $\mathrm{4}$ RSUs.

Next, we analyse the complexity and approximation ratio of Algorithm 3 as follows.

Theorem 12.

The time complexity of Algorithm 3 is $O(T_a+T_b+|{\mathcal{R}}_a\cup {\mathcal{C}}_{{\mathcal{R}}_a}{|}^{\mathrm{2}})$ , while $T_a$ and $T_b$ are the time complexities of the approximation algorithms for DRP-L and MST problem, and $|{\mathcal{R}}_a\cup {\mathcal{C}}_{{\mathcal{R}}_a}|$ is the number of union set $|{\mathcal{R}}_a\cup {\mathcal{C}}_{{\mathcal{R}}_a}|$ .

Proof.

Line $\mathrm{1}$ of Algorithm 3 applies Algorithm 1 in $T_a$ time. Line $\mathrm{2}$ constructs the WCG and assigns the weights to the edges in $O(|{\mathcal{R}}_a\cup {\mathcal{C}}_{{\mathcal{R}}_a}|)$ time. Line $\mathrm{3}$ requires $T_b$ time to obtain the minimal Steiner tree. This proves the time complexity of the algorithm.

Theorem 13.

Let $\mathcal{R}$ be one's solution to DRP-W and let ${\mathcal{R}}^{OPT}$ be the optimal solution to DRP-W; then, $\left|\mathcal{R}\right|/\left|{\mathcal{R}}^{OPT}\right|\le \ln (n)+\mathrm{3}$ .

Proof.

The theorem can be founded in a similar way as in [20]. Let ${\mathcal{R}}_{\mathrm{1}}^{\text{OPT}}$ be the minimum set of wireless RSUs that cover road segments within the delay bound. Obviously, we have

$$\begin{array}{cc}& \left|{\mathcal{R}}_{\mathrm{1}}^{\text{OPT}}\right|\le \left|{\mathcal{R}}^{\text{OPT}}\right|.\end{array}$$

(17)

According to Theorem 5, we have

$$\begin{array}{cc}& \left|{\mathcal{R}}_{\mathrm{1}}\right|\le \ln n\left|{\mathcal{R}}_{\mathrm{1}}^{\text{OPT}}\right|.\end{array}$$

(18)

Let ${\mathcal{R}}_{\mathrm{2}}^{\text{OPT}}$ be the minimum set of wireless RSUs that make ${\mathcal{R}}_{\mathrm{1}}$ connected. We apply a 2-approximation algorithm for the MST which Kou et al. proposed in [46]. Then, we have

$$\begin{array}{cc}& \left|{\mathcal{R}}_{\mathrm{2}}\right|\le \mathrm{2}\left|{\mathcal{R}}_{\mathrm{2}}^{\text{OPT}}\right|.\end{array}$$

(19)

According to [20], we have

$$\begin{array}{cc}& \left|{\mathcal{R}}_{\mathrm{2}}\right|\le \left|{\mathcal{R}}^{\text{OPT}}\right|+\left|{\mathcal{R}}_{\mathrm{1}}\right|.\end{array}$$

(20)

According to 17, 18, 19, and 20, the total number of wireless RSUs placed by the Algorithm 3 is

$$\begin{array}{l}\left|\mathcal{R}\right|=\left|{\mathcal{R}}_{\mathrm{1}}\right|+\left|{\mathcal{R}}_{\mathrm{2}}\right|\\ \hspace{1em}\hspace{0.17em}\le \ln n\left|{\mathcal{R}}_{\mathrm{1}}^{\text{OPT}}\right|+\mathrm{2}\left|{\mathcal{R}}_{\mathrm{2}}^{\text{OPT}}\right|\\ \hspace{1em}\hspace{0.17em}\le \ln n\left|{\mathcal{R}}_{\mathrm{1}}^{\text{OPT}}\right|+\mathrm{2}\left(\left|{\mathcal{R}}^{\text{OPT}}\right|+\left|{\mathcal{R}}_{\mathrm{1}}\right|\right)\\ \hspace{1em}\hspace{0.17em}\le \left(\ln n+\mathrm{3}\right)\left|{\mathcal{R}}^{\text{OPT}}\right|.\end{array}$$

(21)

6. Performance Evaluation

In this section, we evaluate the performance of our proposed methods and present the simulation results of our algorithms in different cases.

6.1. Simulation Model

In the simulation, we model the street layout of urban areas by a grid graph $G(V,E)$ . The candidate sites number is $\left|V\right|$ , and the number of road segments is $\left|E\right|$ . The length of road segment is set to 500 m, which is regarded as the length unit in the simulation. Therefore, a $\mathrm{10}\times \mathrm{10}$ network means the region has $\mathrm{10}\times \mathrm{10}$ evenly distributed candidate sites, with all sides $\mathrm{500}\hspace{0.17em}\text{m}\times \mathrm{10}=\mathrm{5000}\hspace{0.17em}\text{m}$ long. The expected link delay of each road segment is set to 5 mins. Since we consider the epidemic forwarding messages, we assume that there is no transmission conflict and both vehicles and RSUs have infinite buffer to store packets. We define the $\Delta \text{-}$ coverage ratio as the percentage of road segments that can be covered within the delay bound by the placed RSUs. We investigate the number of RSUs and the Δ-coverage ratio under different candidate sites, different delay bounds, and different transmission range. We consider several algorithms as follows.

• (i)

Random algorithm for RSU-L problem (Random-L): in this algorithm, we randomly install wired line RSUs.

(ii)

Our DRP-L algorithm (DRP-L): it is our proposed algorithm for DRP-L problem.

(iii)

Random algorithm for RSU-W problem (Random-W): in this algorithm, we randomly install wireless RSUs.

(iv)

Our DRP-W greedy algorithm (Greedy-W): it is our proposed greedy algorithm for DRP-W problem.

(v)

Our DRP-W MST-based algorithm (MST-W): it is our proposed MST-based algorithm for DRP-W problem.

6.2. Impact of Candidate Sites

We investigate how the changes of candidate sites impact the performance of the different algorithms. Figure 5 shows the number of RSUs, the $\Delta \text{-}$ coverage ratio of DRP-L algorithm, and the DRP-W greedy algorithm under different candidate sites of $\mathrm{5}\times \mathrm{5}$ , $\mathrm{6}\times \mathrm{6}$ , $\mathrm{7}\times \mathrm{7}$ , $\mathrm{8}\times \mathrm{8}$ , $\mathrm{9}\times \mathrm{9}$ , and $\mathrm{10}\times \mathrm{10}$ . The delay bound is $\mathrm{5}$ minutes, the transmission range of RSUs is set to 500 m. Compared with other algorithms, our DRP-L and DRP-W algorithms always obtain the lower number in Figure 5(a). Meanwhile, we could see that the larger candidate sites yield more RSUs. This is because the larger candidate sites yield more road segments, leading to placing the larger number of RSUs. In Figure 5(b), we plot the Δ-coverage ratio of DRP-L algorithm under different candidate sites. We could see that the Δ-coverage ratio increases as the candidate sites increase that is because the more the RSUs installed, the more the road segments covered. In Figure 5(c), we plot the Δ-coverage ratio of DRP-W greedy algorithm under different candidate sites. We could also see that the Δ-coverage ratio increases as the candidate sites increase in the DRP-W greedy algorithm. Meanwhile, we could see that, with the same Δ-coverage ratio, we should install more wireless RSUs to cover the road segments in DRP-W greedy algorithm, compared with the DRP-L algorithm.

Figure 5

Impact of candidate sites (transmission range of RSUs = 500 m, delay bound = 5 mins).

6.3. Impact of Delay Bounds

We investigate how the changes of delay bounds impact the number of RSUs and Δ-coverage ratio in Figure 6. The delay bounds are from 5 mins to 30 mins, the candidate sites are $\mathrm{10}\times \mathrm{10}$ , and the transmission range of RSUs is 500 m. As shown in Figure 6(a), for all algorithms, the shorter delay bound leads to more RSUs number. This is because the shorter delay bound requests communication in a short time, leading to the larger number of RSUs. Moreover, our DRP-L and DRP-W greedy algorithms have better performance than other algorithms under different value of delay bounds. The performance of DRP-W MST-based algorithm is nearly the same as the DRP-W greedy algorithm. As shown in Figure 6(b), as the delay bound increases, the Δ-coverage ratio also increases. As the delay bound increases, we could choose to install less RSUs to meet the delay bound. In this case, each RSUs could cover more segments within the delay bound. In Figure 6(c), as the delay bound increases, the Δ-coverage ratio also increases in DRP-W greedy algorithm. Meanwhile, we find that when delay bound is above 20 mins, the Δ-coverage ratio of DRP-W greedy algorithm nearly equals the DRP-L algorithm.

Figure 6

Impact of delay bound (candidate sites = $\mathrm{10}\times \mathrm{10}$ , transmission range of RSUs = 500 m).

6.4. Impact of Transmission Range

Figure 7 shows the different performance under different transmission range. The transmission of RSUs is from $\mathrm{0.5}$  km to $\mathrm{3}$  km. The candidate sites are $\mathrm{10}\times \mathrm{10}$ and the delay bound is $\mathrm{5}$ minutes. As shown in Figure 7(a), even when the transmission is low, our DRP-L, DRP-W greedy, and MST-based algorithms still achieve a good performance (e.g., when the transmission range of RSUs is above 1.5 km). As the transmission range increases, the number of RSUs drops smoothly as shown in Figure 7(a). This is because the more the transmission range increases, the more the RSUs are connected with others especially wireless RSUs by wireless link in no time and the more the covered road segments we could obtain, so the number of RSUs decreases. In Figures 7(b) and 7(c), we could see that when the number of RSUs is less, the Δ-coverage ratio of DRP-L algorithm and DRP-W greedy algorithm both increase quickly. However, when the number of RSUs increases, their curves become stable gradually, which suggests that as the number of RSUs increases, the newly placed RSUs contribute less and less in serving the uncovered roads.

Figure 7

Impact of transmission range (candidate sites = $\mathrm{10}\times \mathrm{10}$ , delay bound = 5 mins).

7. Conclusion

In this paper, we investigate the problem of delay bounded roadside unit placement (DRP) problem in vehicular networks, which enables all vehicles to receive the messages in a given delay bound. First, we divide the DRP problem into two subproblems called delay bounded roadside unit placement for wired line RSUs (DRP-L) problem and delay bounded roadside unit placement for wireless RSUs (DRP-W) problem. Next, we theoretically prove that both DRP-L and DRP-W are NP-hard. Finally, we propose several heuristic algorithms to solve the DRP-L problem and DRP-W problem, respectively. Simulation results show that the performance of our methods is superior to the other methods under different environment.