RoadGate : Mobility-Centric Roadside Units Deployment for Vehicular Networks

Abstract

With the increase of the storage capacity, computing, and wireless networking of the vehicular embedded devices, the vehicular networks bring a potential to enable new applications for drivers and passengers in the vehicles. Due to the prohibitive cost of deployment and management of a roadside unit (RSU), it is difficult to cover roads with a large number of RSUs so that every vehicle can always keep a connection with the nearby RSU. In this paper, we study the problem of deploying the RSUs to provide the desired connectivity performance while minimizing the number of the deployed RSUs. The key idea of our solution is to exploit the time-stable mobility pattern to find the optimal deployment places. We analyze a realistic vehicle trace, observe the mobility pattern, and propose a graph model to characterize it. Based on the graph model, we transform the gateway deployment problem into a vertex selection problem in a graph. By reducing it into the minimum vertex coverage problem, we show that the RSU deployment problem is NP-complete. Then, a heuristic algorithm RoadGate is proposed to search greedily the optimal positions. Extensive simulations based on the synthetic and realistic scenarios are carried out to evaluate the performance. The results show that RoadGate outperforms other approaches in terms of the number of required RSUs and the actual achieved coverage performance.

1. Introduction

Today, a growing number of vehicles are equipped with the embedded communication devices that can facilitate vehicle-to-vehicle and vehicle-to-infrastructure communication. Increased storage capacity, computing, and communications power, coupled with the advanced wireless networking technology, bring a potential to enable new applications for drivers and passengers in the vehicles. Therefore, vehicular ad hoc networks (VANETs) recently have started to attract attention from many researchers in both industry and academia. The Federal Communications Commission (FCC) in the United States has allocated specifically 5.850–5.925 GHz band and enacted the dedicated short range communications (DSRCs) standard using that band [1]. DSRC is designed to support an intelligent transportation system (ITS) with public safety and private operations for vehicle-to-roadside units (RSUs) and intervehicle communications.

In the typical vehicular networks applications, the vehicles can be equipped with various sensors to collect the traffic and environmental data such as air pollution level, pavement condition, driving habits, and road congestion. The data are reported to the backend servers via the wireless interface embedded in the vehicles. Besides, those Internet services including email, news, entertainment, and location-based services such as ads and navigation are also be provided by the vehicle-to-RSU communication paradigm.

However, a number of technical challenges should be solved before vehicular networks become a reality. In vehicle-roadside communication, RSUs act as RSUs to the Internet and to the infrastructure of other systems such as an ITS, vehicles transmit their gathered data and Internet access requests to RSUs. RSUs send responses to the Internet queries and road information to vehicles. Due to the prohibitive cost of deployment and management of an RSU (typical cost is 3000$/node [2]), it is difficult to cover roads with a large number of RSUs so that every vehicle on road can always be connected to at least one nearby RSU. The solution that can leverage intermittent connectivity provided by RSUs is more scalable and competitive. The experiments in various controlled environments have confirmed the feasibility of RSU-based vehicular Internet access for noninteractive applications. However, solutions based on intermittent connectivity of RSUs can provide opportunistic services without any worst case service guarantees, which poses great difficulty to its application.

In this paper, we study the problem of RSUs placement that required the minimum number of RSUs, with the vehicle-to-RSU contact probability guarantee given that an intermittent single-hop connectivity exists between vehicles and RSUs in a road region. We firstly analyze a realistic vehicles trace and observed that there is time-stable statistical mobility pattern in the realistic trace. Then, we propose a graph model to characterize this pattern and show that the RSUs deployment problem is NP-complete by reducing it into the minimum vertex coverage problem. Finally, we propose a heuristic greedy algorithm RoadGate to find the optimal locations. Extensive experiments in the synthetic and realistic scenarios are carried out to evaluate the performance of our solution. The results show that our solution achieves the desired coverage performance and minimize the number of the required RSUs.

We make the following contributions in this paper. (1)

We disclose the time-stable statistical mobility pattern existing in the realistic vehicles and develop a graph model to characterize it.

(2)

We show that the RSU deployment problem is NP-complete and propose a heuristic algorithm to find the optimal places.

The rest of this paper is organized as follows. In Section 2, we briefly review the related works. We firstly describe the system model in Section 3, then analyze a realistic vehicle trace to verify its time-stable mobility pattern, and propose a graph model to characterize it in Section 4. We formulate the RSU deployment problem and prove it is NP-complete, then develop a heuristic algorithm in Section 5. In Section 6, we evaluate the solution performance in two scenarios. Finally, we make conclusions in Section 7.

2. Related Works

Wireless AP or Base Station placement is a well-known research topic in the cellular, wireless sensor networks, and mesh networks; however, most of the works that have addressed this problem so far consider a continuous infrastructure radio coverage. Here, we just describe those most relevant RSUs deployment works in vehicular networks.

There are some works studying the feasibility of leveraging the RSUs in the vehicular networks. Drive-thru Internet [3] was first introduced in the paper, which shows that a vehicle moving with the velocity of 180 km/h can access internet data via a roadside AP. Refrences [4, 5] confirm the feasibility of WiFi-based vehicular Internet access for noninteractive applications. Cabernet [6] aims to deliver data to and from moving vehicles by using WiFi access points. It only provides the intermittent network connectivity with the current deployed APs. Cartel [7] is a mobile sensor computing system which collect, process, and deliver data from vehicular sensors to the server located in Internet by opportunistically using the roadside APs. All these works are assumed to utilize the unplanned deployment APs without the service guarantee. The feasibility of information dissemination using stationary supporting units (SSUs) is investigated in [8] mainly based on computer simulations. However, the deployment issues have not been carefully studied in these works.

Thus, the dedicated RSUs are proposed to be integrated into the vehicular networks to achieve the system scalability, and various RSUs deployment strategies are developed. Banerjee et al. [2] consider a simple nonuniform strategy that places more stationary nodes in the network core. However, it was completely based on intuition without providing any performance guarantees. Alpha coverage [9] provides the intermittent coverage and guarantees the number of contact between vehicles and RSUs. The authors further present an efficient deployment method that maximizes the worst case contact opportunity under a budget constraint [10]. Li et al. [11] consider the optimal placement of RSUs to minimize the average number of hops from APs to RSUs. Lee and Kim [12] seek optimal placement of RSUs by analyzing the number of the reported locations per minute by taxis to telematics system. Lochert et al. [13] use genetic algorithm for optimal placement of RSUs for a VANET traffic information system. The optimal placement is aimed at minimizing the travel time based on aggregated sharing of traffic information. A centrality-based AP deployment scheme was proposed to optimize the end-to-end delay in [14]. Trullols et al. [15] consider that a given number of RSUs have to be deployed for disseminating information to vehicles in an urban area. They formulate it as a maximum coverage problem (MCP) and seek to maximize the number of vehicles that get in contact with the RSUs over the considered area. The deployment scheme proposed in [16] can guarantee that vehicles at any place could communicate with RSUs in certain driving time by proving it equivalent to the set-covering problem. In [17], the deployment optimization objective guarantees a required maximum vehicle-to-RSU data packet delivery delay with a certain predetermined delay violation probability. Besides, [18] uses the game theory to model the RSUs deployment when multiple operators perform their deployment decisions concurrently.

3. System Model

In this section, we firstly present the system model and then give the problem description.

As depicted in Figure 1, a typical VANET consists of three entities in city scenarios: the top server, the fixed RSUs or gateway along the roadside, and the mobile OBUs (on-board units) equipped on the running vehicles. The servers depend on the specific application, and we will not give detailed description. All RSUs are planned to provide communication services. The RSUs and OBUs are equipped with short-range radio interfaces such as 802.11 b/g/p, and they can exchange data when entering into their mutual transmission ranges. The RSUs have the powerful storage space to cache the data reported by vehicle or the disseminated data from the server. Moreover, RSUs may connect to the server in the Internet to download or upload data.

Figure 1

System model for vehicle-to-roadside communication.

Considering a limited geographical region, vehicles enter and leave, autonomously and continuously, the region. All RSUs can be installed at any place in the region. When a vehicle moves into the radio range of any RSU, it may use the opportunity to establish connectivity with the RSU and then send or receive data from it. The capacity of the communication system gets fairly important when the amount of transferred data becomes large. The capacity of the intermittently connected network relies on a few factors such as the vehicle speed, the radio range, and the data rate. For example, the higher the data rate is, the larger the throughput is. However, in this paper, we focus on the impact of meeting probability which indicates the possibility that a vehicle can access the deployed RSU when it goes through the area.

Our goal is to guarantee the meeting probability specified by users while minimizing the deployment cost, say, the number of the required RSUs. Specifically, the meeting probability is the probability with which any vehicle can enter the communication range of at least on installed RSU after it moves within a given distance from entering the region. This enables our solution work at the situation that the vehicles sojourn or stay within the area. Note that we do not take the possible available open access points into account, but our work provides a lower bound of system performance when that way is allowed.

4. Mobility Graph

In this section, we firstly analyze a realistic vehicle trace and observe the time-stable statistical mobility pattern. Then, we give the definition of the graph model to characterize the mobility pattern.

4.1. Analysis on Realistic Vehicle Trace

Some existing works also study the performance enhancement in mobile networks by deploying stationary nodes. But these works basically assume the nodes move according to the simplistic random models. These models are usually easy to implement in simulations and allow statistical analysis of large-scale protocols and systems. However, they do not capture the characteristic of people move in realistic environment.

Recent that studies [19] on some realistic traces of moving users show that nodes within a social environment do not move completely randomly. Instead, they usually move around a set of landmarks such as home, office, and park. Specifically, nodes show preference for a small number of landmarks and would move less often to the neighborhood of other landmarks. The second observation is that in some social environments the node trajectory in time is almost deterministic [20]. This means a node has its own mobility schedule and it generally moves between landmarks according to that schedule, subject to few random deviations.

Above observations disclose the long-term mobility pattern of people in reality. Inspired by above observations from the study on the realistic people traces, Piorkowski also [21] analyzed a realistic GPS-based mobility traces of taxi in San Francisco, USA. This dataset contains the GPS coordinates of 665 taxis collected over 30 days in the Bay Area. His work verifies that the spatially heterogeneous mobility pattern appears to be stable in time.

As the taxi trace is only a sample of the urban mobility pattern, we use a realistic vehicle trace containing different type mobile nodes (buses, taxis, pedestrians, etc.). This trace is generated by MMTS (multiagent microscopic traffic simulator) [22] which accurately models the public and private traffic over real regional road maps of Switzerland with a high level of realism [23]. Figure 2 shows the simulation involving around 260000 vehicles in an area of around 250 km × 260 km in the canton of Zurich, the largest city in Switzerland.

Figure 2

Road network and traffic in MMTS.

For the purpose of our analysis, we extract the traffic data over around 18 hours in an area of around 3000 m × 3000 m in the central city of Zurich. The whole area is divided into a set of nonoverlapped uniform zones. Each zone has an area of 200 m × 200 m, 300 m × 300 m, and 600 m × 600 m, respectively, in three experiments. With the time unit of 20 minutes, we count the number $N_{i}$ of vehicles passing zone i and the number $N_{i j}$ of vehicles entering zone j after leaving zone i for each time unit. Then, we use $N_{i j} / N_{i}$ as the estimation of transition probability. In each experiment, we record and plot the transition probability of five pairs of zones shown in Figure 3.

Figure 3

Transition probability for zone of different area.

Some key characteristics are observed from the above statistical results. (1) The transition probabilities between two zones stay approximately stable which fluctuate around a mean value within two traffic peak time. (2) The transition probability between two same zones is different in two peak time, as depicted by blue lines in Figures 3(b) and 3(c). The possible reason is the regular mobility behaviors of people. For example, people usually move from their home to office in the morning and return along the inverse routine in the evening. (3) There is no obvious impact of the size of zone on the time stability of transition probability. However, the transition probability may vary with time when the zone is very small. We do not consider the case because our zone division is big enough.

4.2. Definition

Based on the above observations, we define a mobility graph to characterize the time-stable statistical mobility pattern in a region.

Let us consider a connected and bounded geographical area A, we divide it into s nonoverlapped uniform zones. A Mobility Graph is a directed graph G, whose vertex set $𝒱 (G)$ corresponds to the set of zones. Its edge set $ℒ (G)$ corresponds to the set of mobility links between zones on which vehicles travel. There exists a mobility link between two neighboring zones i and j only if a vehicle leaves zone i and then enters zone j immediately. Each edge is associated with a transition probability which indicates the probability that a random node moves from i to j. We use the similar approach used in Section 4.1 to compute the transition probability. Let T denote the time unit, the transition probability is computed as follows:

\begin{matrix} P^{T} (i, j) = \frac{| {𝒩_{i} (T) \cap 𝒩_{j} (T)} |}{| 𝒩_{i} (T) |}, \end{matrix}

(1)

where

𝒩_{i} (T)

and

𝒩_{j} (T)

are, respectively, the set of vehicles located in zones i and j within a time unit T. As stated in Section 4.1, transition probability between two zones is basically time stable for a long period of time and changes for another duration in a day. Then, the average of all time units in the total statistical time is computed as the final weight of the corresponding edge.

We also explore the mobility process of all vehicles passing the boundary of the area A. We introduce a virtual vertex U to represent the exterior zone beyond A. If there are the vehicles entering A from the bounding zone i, then an edge exists between vertex U and vertex i. The corresponding transition probability is computed in the similar way to the ordinary edges. An example is shown in Figure 4. Its left part shows that the geographical area is divided into 6 zones, say, zone from $1$ to $6$ , and the corresponding mobility graph is depicted in right side. Here, we find that all the vehicles only move into the area from $1$ and $4$ zones with the probability of 0.8 and 0.2, respectively. Meanwhile, they only leave the area from zones $2$ and $6$ with the probability of 0.3 and 0.6, respectively. The red curves represent, respectively, the physical path 1-3-4-6 in the geographical area and that on the Mobility Graph.

Figure 4

A geographical area and the corresponding mobility graph.

Now, we discuss some methods to optimize the constructed mobility graph. First, we delete those vertices corresponding to the zones which do not contain roads because all vehicles cannot move into them. Additionally, we also delete those vertices that contain only a road segment because they have no chance of moving to other zones but the two fixed neighbors. Finally, those edges associated with the transition probability smaller than a given threshold should be removed because they nearly have no impact on the final computation.

5. RSU Deployment Problem

In this section, we firstly present the several definitions and assumptions, then formally define the Minimum RSUs deployment problem (MRDP). Finally, we prove it is NP-hard and develop a greedy heuristic algorithm to find the optimal deployment solution.

5.1. Assumptions and Definitions

For the sake of convenience to make our idea clear, we make the following assumptions. We assume that each zone can be covered by the communication range of an RSU. That is to say, the vehicles can exchange data with the installed RSU once they enter the zone. We assume that the transmission ranges of all RSUs are fixed, so we have to adjust the size of zones to meet that assumption. Let us take the RSU integrating the 802.11 g interface as an example. The outdoor standard transmission distance of 802.11 g is around 300 m. Thus, the area of a zone may be selected as 400 × 400 m² if the RSU is placed at the center of the zone. The size of a zone should be set smaller while considering the signal decay caused by the buildings. In the following, we introduce several key definitions. The symbols and notations used in the paper are summarized in Table 1.

Table 1

Summary of major notations.

A	Target geographical area
G	Mobility graph
$𝒱 (G)$	Vertex set
$ℒ (G)$	Edge set
$ℳ (G)$	Transition matrix of graph
$P (i, j)$	Transition probability from vertex i to j
$π_{i j}^{δ}$	Transition probability from i to j in at most $δ$ hops
$λ_{i ℛ}$	Visiting probability from vertex i to group ℛ
$\hat{𝒱}$	Optimal vertex set being searching
$δ$	Maximum hops
$P_{u}$	Meeting probability threshold specified by users

Definition 1 (transition matrix).

Since there are the time-stable transition probabilities between all zones, the statistical mobility pattern can be represented by a time homogeneous Markov chain. Its state space is exactly corresponding to the vertex set, say, all zones. Therefore, the transition probability distribution between the state space can be represented by the transition matrix $ℳ (G)$ . A journey of a vehicle passing the area A can be denoted as a path in the Markov chain.

Definition 2 (vertex visiting probability (VVP)).

$π_{i j}$ is the probability of a node that moves from vertex i to j within a given maximal length δ. It is computed as

\begin{matrix} π_{i j}^{δ} = \sum_{h = 1}^{δ} π_{i j} (h), \end{matrix}

(2)

where

π_{i j} (h)

is the probability of a node move from vertex i to j within the exact length h. Let ℳ denote the transition matrix of mobility graph, then we have

\begin{matrix} π_{i j} (h) = ℳ^{h} [i] [j], \end{matrix}

(3)

where

ℳ^{h}

is the h-step transition probability, which can be computed as the hth power of the transition matrix ℳ.

Definition 3 (set visiting probability (SVP)).

$λ_{i ℛ}$ is defined as the probability with which a node moves from vertex i to at least one vertex $j \in ℛ$ . It is derived as follows:

\begin{matrix} λ_{i ℛ} = 1 - \prod_{j \in ℛ} ‍ (1 - π_{i j}^{δ}) . \end{matrix}

(4)

5.2. MRDP and Its Complexity

Based on the above definitions, we transform the minimum RSU deployment problem to a problem of selecting vertex subset. The formulation of MRDP is formulated as follows. Given a mobility graph G modeling the statistical mobility pattern over the area A and the meeting probability threshold $P_{u}$ specified by users, the objective of MRDP is to find the smallest subset $\hat{𝒱} \subseteq 𝒱 (G)$ such that the SVP from any vertex to $\hat{𝒱}$ is not smaller than the probability specified by user, say,

\begin{array}{l} minimize | \hat{𝒱} | \\ s . t . \hat{𝒱} \subseteq 𝒱 (G), \forall i \in 𝒱 (G), λ_{i \hat{𝒱}} \geq P_{u} . \end{array}

(5)

We have the following theorem regarding the complexity of the MRDP.

Theorem 4.

The MRDP problem is NP-complete.

Proof.

The MRDP problem can be reduced to the classical minimum vertex cover problem which is a well-known NP-complete problem. First, for each vertex $i \in 𝒱 (G)$ , we compute its VVS to all vertex j, $π_{i j}^{δ}$ according to (2). Then, we find a vertex subset $𝒳_{i} = {j ∣ j \in 𝒱 (G)$ and $π_{i j}^{δ} \geq P_{u}}$ . It contains all reachable vertices from vertex i within the constraint of given path length and the visiting probability specified by user. By repeating the process, we can compute the above set for each starting vertex i, say, $𝒳_{i} ∣ i \in 𝒱 (G)$ . Then, we construct a set for each vertex i, $Y_{i} = {j ∣ i \in 𝒳_{j}}$ , containing those starting vertices from which a node can visit the vertex i within the constraint of the given path length and meeting probability threshold. Finally, the MRDP is equivalent to the problem of finding a subset $\hat{𝒱}$ ,

\begin{array}{l} minimize | \hat{𝒱} | \\ s . t . ⋃_{i \in \hat{𝒱}} ‍ Y_{i} \supseteq 𝒱 (G) . \end{array}

(6)

Obviously, the formulation is the classical minimum vertex cover problem, which has been shown as NP-complete. Note that we just consider the visiting probability from all vertices to a single vertex in the $\hat{𝒱}$ instead of the SVP, which usually is greater than the former. However, this point cannot affect the correctness of the proving procedure because it just equivalent to that the meeting probability specified by user $P_{u}$ is set to a smaller value. Consequently, MRDP is still an NP-complete problem.

5.3. RoadGate Algorithm

In order to solve the MRDP problem, we develop a heuristic algorithm RoadGate which uses the greedy strategy to search optimal RSU deployment. The details of the algorithm are shown in Algorithm 1.

Algorithm 1: RoadGate deployment algorithm.

Input: G—Mobility Graph; $δ$ —maximal path length; $P_{u}$ —meeting probability specified by user

Output: $\hat{𝒱}$ —result set being searched

(1) $ℳ \leftarrow$ transition matrix of G

(2) compute the 1-step, 2-step $, \dots, δ$ -step transition matrix of ℳ

(3) compute the VVP $π_{i j}^{δ}$ between all nodes according to (2)

(4) $\hat{𝒱} \leftarrow \emptyset$

(5) $𝒮 \leftarrow \emptyset$

(6) while $| 𝒮 | < | 𝒱 (G) |$ do

(7) $j \leftarrow \arg \max_{x \in 𝒱 - \hat{𝒱}} (| {k ∣ k \in 𝒱 - 𝒮, λ_{k (\hat{𝒱} ⋃_{} ‍ {x})} \geq P_{u}} |)$

(8) $\hat{𝒱} \leftarrow \hat{𝒱} ⋃_{} ‍ {j}$

(9) $𝒮 \leftarrow 𝒮 ⋃_{} ‍ {k ∣ λ_{k \hat{𝒱}}} \geq P_{u}}$

(10) end while

In this algorithm, the first 3 lines are responsible for computing the VVP $π_{i j}^{δ}$ from any vertex i to other vertex j. The vertex set being searched is initialized in line 4. In line 5, the algorithm initializes a set 𝒮 from which the SVP to the set being searched $\hat{𝒱}$ is not smaller than the probability specified by user. Line 6 shows the following procedure terminates until all SVP from all vertices to the result set $\hat{𝒱}$ are not smaller than predefined probability. Line 7, the key idea of RoadGate, searches greedily the vertex which can maximize the number of vertices whose SVP to the result set is not smaller than the predefined threshold. The found vertex is added the result vertex set in line 8. Finally the set 𝒮 is updated after the new vertex is added. Clearly, the time complexity of this algorithm is $O ({| 𝒱 |}^{3})$ .

6. Performance Evaluation

6.1. Methodology

In this section, we evaluate the performance of RoadGate algorithm in two different scenarios. The first is a synthetic scenario shown in the left side of Figure 5. A $1600 * 2000$ m² area is divided into 20 zones, each with $400 * 400$ m². Thus, the corresponding mobility graph contains 21 vertices. The largest degree of each vertex is 4 because the vehicles only move from current zone to 4 neighboring zones. The average path length is $δ = 5$ zones when a vehicle passes the whole area. The experiment is conducted for 200 runs. Each of those generates randomly the mobility graph with different random seeds.

Figure 5

Two scenarios for performance evaluation.

Another experiment scenario is the realistic vehicle trace used in Section 4.1. We choose a central city area of $2000 \times 1500 m^{2}$ in Zurich. It is divided into 50 zones each with $200 \times 300 m^{2}$ . Then, we use the approach proposed in Section 4.1 to compute the statistical transition probability and then construct the corresponding mobility graph. Moreover, we also choose a larger area including both two scenarios to simulate the vehicles that enter and leave the scenarios.

We compare RoadGate with other two baseline algorithms. The first is the Random Deployment (RandDeploy), which selects randomly a vertex to be added the result set until the SVP of all vertices to the result set is not smaller than the predefined threshold. The second is the Degree First Deployment (DegFDeploy). Contrary to the RandDeploy, it chooses greedily the vertex with the largest degree to be added to the result set. The higher the degree of a vertex is, the more popular the corresponding zone is. Thus, DegFDeploy captures the stationary statistical pattern of the mobility in the target area in contrast to the RoadGate.

The following performance metrics are evaluated. (1) The number of required RSUs indicates the deployment cost which is the key metric of our system. (2) Actual meeting probability. It represents the achieved coverage performance when the vehicles go through the above scenarios. We implement the deployment solution in the simulator ONE (opportunistic network environment) [24] and drive the nodes to move to count the realistic meeting probability.

6.2. The Number of Required RSUs

We firstly compute the number of required RSUs when the meeting probability specified by user is 70% and 90% in the synthetic scenario. Figure 6 shows the cumulative distribution of 200 experiment results. It can be seen that RoadGate requires much less RSUs than other algorithms. When the expected meeting probability of users is 70%, 5 RSUs are needed for RoadGate, but RandDeploy and DegFDeploy need nearly 8 RSUs in most cases. Similarly, RoadGate also outperforms the other two algorithms when the meeting probability specified by user is 90%. It can be explained as follows. RandDeploy blindly chooses the placement zones thus achieves and the worst performance. DegFDeploy only uses the coarse statistical information of the mobility pattern in the area. Thus, it has the poor performance in the random mobility graph. RoadGate utilizes the fine-grained statistical characteristic of mobility and can select the optimal places to install RSUs.

Figure 6

The cumulative distribution of required RSUs.

Only one deterministic mobility graph can be generated from the realistic vehicle traces. Therefore, we vary the meeting probability specified by user to observe its impact on the required number of RSUs in the three algorithms. As shown in Figure 7, the higher the meeting probability specified by users, the larger the number of the required RSUs. Moreover, our algorithm RoadGate always outperforms the two baseline algorithms. Since RoadGate can take full advantage of the coverage capability of each added RSU, it needs to add a few RSUs to fulfil the increase of users' expected meeting probability.

Figure 7

Number of required RSUs in the realistic scenario.

6.3. Actual Meeting Probability

We also evaluate the achieved meeting probability when vehicles go through the experiment scenarios. In the synthetic scenario, we compute the RSU deployment solution, respectively, by using, three algorithms for the meeting probability specified by users, which is 70% and 90%. In the 200 experiments in the synthetic scenario, we place 1000 vehicles in the experiment area and let them move according to the generated mobility graph. The RSUs are deployed according to the result computed by the three algorithms. When a vehicle moves into the zone with RSU, it succeeds in communication with the RSU. The actual meeting probability is computed as the ratio of the number of the vehicles meeting RSUs to total vehicle number. The cumulative distribution of 200 experiment results is shown in Figure 8.

Figure 8

The cumulative distribution of actual meeting probability in synthetic scenario.

As can be seen, all three algorithms succeed in meeting the meeting probability requirement of users. However, in contrast to RandDeploy and DegFDeploy, the real meeting probability achieved by our RoadGate fairly matches the expected probability. Most of its results fall in the interval of 70%–80% when the specified probability is 70%. It shows that RoadGate is capable of selecting accurately the deployment places to meet the coverage requirement.

We measure the actual meeting probability in the realistic scenario. Similarly, we compute the deployment solution by using the three algorithms for the user's specified probability, which is 70% and 90%. Then, we make use of the solution to place the RSU in the scenario in the ONE simulator. These RSUs broadcast a beacon packet periodically. The experiments are carried out for 24 runs. Each run uses the extracted realistic vehicles trace lasting for 20 minutes from the total 8 hours peak time. These traces are fed into the simulator to drive the vehicles move. The actual meeting probability is calculated as the ratio of the number of the vehicles receiving the beacon to the total vehicle number in current run. The cumulative distributions of actual meeting probability are shown in Figure 9.

Figure 9

The cumulative distribution of actual meeting probability in realistic scenario.

It can be observed from the above figures that the actual meeting probability achieved by the three algorithms basically varies in a large range and failes to meet the users' specified performance threshold. For example, when the expected meeting probability is 90%, around 40% probability achieved by RoadGate is smaller than the threshold. However, our RoadGate still outperforms RandDeploy and DegFDeploy. The reasons are described as follows. The analysis result of Section 4.1 shows that the transition probability between a same pair of zones is probably different for different time periods in a day. However, the mobility graph is constructed by using the average transition probability, causing probably a considerable deviation. Thus, the three algorithms running on the graph are hard to fulfill accurately the users' performance requirement. We also consider some possible strategies to relieve the problem. For example, we build an individual mobility graph for each possible transition probability of an edge. Then, we run the algorithm in each graph to get a deployment solution and then combine them as the final solution. Its essence is to meet the expected coverage performance by adding more RSUs.

7. Conclusions

In this paper, we study the problem of deploying RSUs for mobile vehicles in the vehicle-to-roadside communication system. Due to the limited transmission range and high deployment and maintenance cost, it is difficult to decide how many and where the RSUs should be placed. The objective of our study is to satisfy the connectivity requirement for all vehicles passing the coverage region. At the same times, the deployment cost such as the number of RSUs must be minimized. Our solution RoadGate uses the time-stable statistical mobility pattern observed in the realistic vehicle traces to find the optimal installation places. We propose a graph model to characterize this pattern and show that the RSU deployment problem is NP-complete by reducing it the minimum vertex coverage problem. Finally, we propose a heuristic greedy algorithm RoadGate to find the optimal installation places. Extensive experiments in the synthetic and realistic scenarios are carried out to evaluate the performance of our solution. The results show that our solution achieves the desired coverage performance and minimizes the number of the required RSUs.

Footnotes

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (Grants no. 61202436 and 61271041) and the National Basic Research Program of China (973Program) (Grant no. 2009CB320504).

References

Zhu

Roy

MAC for dedicated short range communications in intelligent transport system

IEEE Communications Magazine 2003 41 12 60 67

2-s2.0-0346752334

10.1109/MCOM.2003.1252800

Banerjee

Corner

M. D.

Towsley

Levine

B. N.

Relays, base stations, and meshes: enhancing mobile networks with infrastructure

14th Annual International Conference on Mobile Computing and Networking (MobiCom ′08)

September 2008

81 91

2-s2.0-78650759659

10.1145/1409944.1409955

Ott

Kutscher

Drive-thru internet: IEEE 802.lib for “automobile” users

Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′04)

March 2004

362 373

2-s2.0-8344283536

Navda

Subramanian

A. P.

Dhanasekaran

Timm-Giel

Das

MobiSteer: using steerable beam directional antenna for vehicular network access

Proceedings of the 5th International Conference on Mobile Systems, Applications and Services (MobiSys ′07)

June 2007

192 205

2-s2.0-35448962081

10.1145/1247660.1247684

Balasubramanian

Mahajan

Venkataramani

Levine

B. N.

Zahorjan

Interactive wifi connectivity for moving vehicles

ACM SIGCOMM Computer Communication Review 2008 38 4 427 438

2-s2.0-65249095217

10.1145/1402946.1403006

Eriksson

Balakrishnan

Madden

Cabernet: Vehicular content delivery using WiFi

Proceedings of the 14th Annual International Conference on Mobile Computing and Networking (MobiCom ′08)

September 2008

199 210

2-s2.0-60149104098

10.1145/1409944.1409968

Hull

Bychkovsky

Zhang

Chen

Goraczko

Miu

Shih

Balakrishnan

Madden

CarTel: a distributed mobile sensor computing system

Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SenSys ′06)

November 2006

125 138

2-s2.0-34247356882

10.1145/1182807.1182821

Lochert

Scheuermann

Caliskan

Mauve

The feasibility of information dissemination in vehicular ad-hoc networks

Proceedings of the 4th Annual Conference on Wireless on Demand Network Systems and Services (WONS ′07)

January 2007

92 99

2-s2.0-34547553225

10.1109/WONS.2007.340478

Zheng

Sinha

Kumar

Alpha coverage: Bounding the interconnection gap for vehicular internet access

Proceedings of the 28th Conference on Computer Communications (INFOCOM ′09)

April 2009

2831 2835

2-s2.0-70349660165

10.1109/INFCOM.2009.5062241

10.

Zheng

Sinha

Kumar

Maximizing the contact opportunity for vehicular internet access

Proceedings of IEEE Conference on Computer Communications (INFOCOM ′10)

March 2010

1 9

2-s2.0-77953312420

10.1109/INFCOM.2010.5461937

11.

Huang

Fang

Lin

Optimal placement of gateways in vehicular networks

IEEE Transactions on Vehicular Technology 2007 56 6 I 3421 3430

2-s2.0-36749068893

10.1109/TVT.2007.907230

12.

Lee

Kim

C. M.

A roadside unit placement scheme for vehicular telematics networks

Advances in Computer Science and Information Technology 2010 6059

Springer

196 202 Lecture Notes in Computer Science

2-s2.0-77954608033

10.1007/978-3-642-13577-4_17

13.

Lochert

Scheuermann

Wewetzer

Luebke

Mauve

Data aggregation and roadside unit placement for a vanet traffic information system

Proceedings of the 5th ACM International Workshop on VehiculAr Inter-NETworking (VANET ′08)

September 2008

58 65

2-s2.0-59249090296

10.1145/1410043.1410054

14.

Kchiche

Kamoun

Centrality-based Access-Points deployment for vehicular networks

Proceedings of the 17th International Conference on Telecommunications (ICT ′10)

April 2010

700 706

2-s2.0-77954561267

10.1109/ICTEL.2010.5478800

15.

Trullols

Fiore

Casetti

Chiasserini

C. F.

Barcelo Ordinas

J. M.

Planning roadside infrastructure for information dissemination in intelligent transportation systems

Computer Communications 2010 33 4 432 442

2-s2.0-74149086091

10.1016/j.comcom.2009.11.021

16.

Sun

Lin

Shen

Roadside units deployment for efficient short-time certificate updating in VANETs

Proceedings of IEEE International Conference on Communications (ICC ′10)

May 2010

1 5

2-s2.0-77955385286

10.1109/ICC.2010.5502183

17.

Abdrabou

Zhuang

Probabilistic delay control and road side unit placement for vehicular ad hoc networks with disrupted connectivity

IEEE Journal on Selected Areas in Communications 2011 29 1 129 139

2-s2.0-78651227986

10.1109/JSAC.2011.110113

18.

Filippini

Malandrino

Dan

Cesana

Casetti

Marsh

Non-cooperative RSU deployment in vehicular networks

Proceedings of the 9th Annual Conference on Wireless On-Demand Network Systems and Services (WONS ′12)

January 2012

79 82

10.1109/WONS.2012.6152243

19.

Ghosh

Philip

S. J.

Qiao

Sociological orbit aware location approximation and routing in MANET

Proceedings of the 2nd International Conference on Broadband Networks (BROADNETS ′05)

October 2005

688 697

2-s2.0-33847035562

10.1109/ICBN.2005.1589669

20.

Liu

Routing in a cyclic mobispace

Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′08)

May 2008

351 360

10.1145/1374618.1374665

21.

Piorkowski

Mobility-centric geocasting for mobile partitioned networks

Proceedings of the 16th IEEE International Conference on Network Protocols (ICNP ′08)

October 2008

228 237

2-s2.0-67249150047

10.1109/ICNP.2008.4697041

22.

Naumov

Baumann

Gross

An evaluation of inter-vehicle ad hoc networks based on realistic vehicular traces

Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC ′06)

May 2006

108 119

2-s2.0-33748041133

23.

Raney

Voellmy

Cetin

Vrtic

Nagel

Towards a microscopic traffic simulation of all of switzerland

Proceedings of the International Conference on Computational Science (ICCS ′02) 2002 2329

London, UK

Springer

371 380 Lecture Notes in Computer Science

24.

Keranen

Ott

Karkkainen

The ONE simulator for DTN protocol evaluation

Proceedings of the 2nd International Conference on Simulation Tools and Techniques (ICST ′09)

May, 2009

1 10

10.4108/ICST.SIMUTOOLS2009.5674