An Analysis of Performance in a Hierarchical Structured Vehicular Ad Hoc Network

Abstract

With the rapid development of vehicle technology and wireless communication technology, a vehicular ad hoc network (VANET) has come into sight as a vehicular application of the well-known mobile ad hoc networks (MANETs). In this paper, we consider the performance issue of a large-scale VANET and extend the technology of Mobile IP used in a MANET into the VANET. In our considered hierarchical structured VANET, each roadside gateway deployed on the roadside is responsible for forming a small-scale local VANET by clustering a number of vehicles nearby. We apply the destination-sequenced distance-vector (DSDV) routing protocol and the Mobile IP to support intra- and intercommunications of local VANETs. Our studies focus on the feasibility of the proposed architecture and evaluate its network performance through an analysis of connectivity. Moreover, we investigate the influence of main network configuration parameters on performance measures such as the mobility of node, the network density, and the number of gateways and demonstrate that the architecture we proposed can achieve good performance with proper configuration parameters.

1. Introduction

As the rapid development of wireless communication technology, wireless networks have deeply penetrated into every aspect of people's work, lives, and relationships and even have been quietly changing people's way of life. Furthermore, promoted by the popularity of the vehicle and advances in vehicle technology, vehicular ad hoc networks (VANETs) arise at the historic moment. Not only the Internet companies but also the automobile manufacturers have begun to get involved in the field of VANET. Toyota, GM, Ford, and BMW have launched G-BOOK [1], OnStar [2], and other digital intelligent vehicle electronic systems. One of the world's largest automotive companies, Ford Motor Company, has advertised itself as a technology company, not just the car manufacturers. Users can connect to some of the smartphone applications through voice commands in their Ford vehicles using SYNC AppLink [3].

As an emerging wireless communication technology, mobile ad hoc network (MANET) has gained more and more attention because of low cost and rapid deployment. It is a self-organizing network that connects mobile routers and terminal hosts by wireless links. Due to the random mobility of each node, this network has an arbitrary topology. Hence centralized administration and specific infrastructures are unnecessary in this kind of network. Depending on the routing protocol adopted in MANETs, mobile nodes are not merely the hosts running applications. Generally, they also play the roles of routers and are responsible for forwarding packets.

With the increased number of vehicles in urban road, frequent traffic accidents, traffic congestion, parking problem, and a series of social problems gradually emerged. Intelligent transportation systems are considered to be an important way to solve these problems. Vehicular ad hoc network (VANET) is proposed to achieve intelligent transportation system applications. It can be used to ensure road safety and improve traffic efficiency. The VANETs usually have smart devices mounted on mobile vehicles with the capability of wireless communication and roadside gateways to constitute a communication mode in two forms: one is the communication between the vehicle and the vehicle and the other is the communication between vehicles and roadside gateways. For the VANETs, the possibility of accessing other networks, such as the Internet, has received growing attention.

A technique was described in [4] which integrates Mobile IP [5] with MANETs to achieve a ubiquitous broadband wireless access. The authors proposed architecture with IEEE 802.11-based access points. This integrated environment can support the micro- and macro-IP mobility. And this facilitates the gradual trend towards all-IP wireless environment. However, there are several different aspects between VANETs and MANETs, especially the high mobility of nodes and the restricted moving pattern. Furthermore, the VANET should have the capability of providing multimedia streaming, game services, information push services, and so on.

In this paper, we consider a large-scale two-tier hierarchical structured VANET and the technique that integrates Mobile IP with MANETs is extended into VANETs. In this architecture, the roadside gateways are deployed to form the backbone and each roadside gateway is responsible for establishing a small-scale local VANET by clustering the vehicles nearby. Moreover, the destination-sequenced distance-vector (DSDV) protocol [6] is applied to support the communications of intralocal VANETs, and the Mobile IP technology is used to support the communications of interlocal VANETs. Our works focus on the feasibility of the proposed architecture and evaluate its network performance through an analysis of connectivity. We investigate the influence of main configuration parameters on the network performance such as the mobility of node, the network density, and the number of gateways and demonstrate that the architecture we proposed can achieve good performance with proper configuration parameters. We aim to determine the feasibility of this architecture and predict the performance of the configuration parameters under a given specific scenario.

The rest of the paper is structured as follows. Section 2 introduces existing work about system architecture in VANET and how our study relates to them. Then we present our two-tier hierarchical structured architecture in Section 3. Section 4 studies the performance analysis methods in VANET. In Section 5, we study the performance of a hierarchical structured VANET through the investigation on the routing path connectivity, the network connectivity, and the k-connectivity. And finally, we give a conclusion of this paper in Section 6.

2. Related Work

Vehicular ad hoc network architecture has attracted much attention. One of these works is National ITS Architecture [7] defined by US DOT. It aims to provide a common framework and the members of the intelligent transportation system (ITS) community can use it for planning, defining, and integrating intelligent transportation systems. This architecture defines the functions required for ITS, such as gathering traffic information or requesting a route. Besides, it also defines the physical entities or subsystems like the field or the vehicle and the information flows and data flows connecting the functions and physical subsystems. The National ITS Architecture is a guideline of future transportation systems in the US. Inevitably, it is comprehensive, but not in depth.

In the Smartway project [8], another ITS architecture has been used. The Smartway is the next generation transportation system using advanced technologies to combine the existing services, such as vehicle information and communication systems (VICS) and electronic toll collection system (ETC). It proposes that the key of platform deployment strategy is common on-board unit (OBU). Particularly, OBU has the capability of processing and communication and is mounted on each vehicle. It is able to provide an application runtime environment, location information, security, interfaces, and so on.

Luo et al. [9] proposed two-tier architecture called mobile infrastructure based VANET (MI-VANET). It utilized the buses to play the role of mobile backbone for data delivery and the ordinary cars and passengers constitute the low tier. By doing so, they achieved some improvement in delivery ratio when compared to GPSR in traditional VANET. However, this method is limited by the type of vehicle, and the bus line information should be informed in advance.

In [10], the authors proposed a collaboration-based hybrid system framework consisting of road side sensors and mobile sensors, and the main concern is to provide effective and efficient architecture for data collection, storage, and exchange. However, an important feature of urban VANET was not considering that vehicles move as clusters because of the influence of road topology, surrounding environment, or traffic lights.

In [11], the peer-to-peer (P2P) network technology was extended to VANET and clustering based architecture was proposed for traffic information sharing. Under this architecture, the scalability problem can be addressed by introducing proxy mechanism. Tseng et al. [4] discussed some issues that are related to integrating the Mobile IP with MANETs. As previously mentioned, VANET differs from MANET in several aspects, especially because of the restricted network topology. Therefore, this technology cannot be simply applied to the VANET.

Considering a large-scale VANET, we provide scalable two-tier hierarchical communication architecture and study the feasibility. The Mobile IP and DSDV protocol are integrated in our hierarchical structured VANET. Moreover, we investigate the performance of the proposed architecture given a specific scenario of configuration parameters.

3. System Architecture

3.1. Two-Tier Hierarchical Structured VANETs

In a vehicular ad hoc network, the special wireless communication devices are mounted on the vehicles to provide the network connectivity. With these devices, each vehicle can transmit and receive messages as well as relay the messages to nearby mobile nodes or gateways by the wireless communication. The gateways deployed at the roadside can connect directly to the Internet. By doing so, the passengers in the vehicles are allowed to enjoy a variety of Internet services.

The two-tier hierarchical structured VANET architecture proposed by us is shown in Figure 1. As the backbone, the roadside gateways are deployed to provide direct Internet connections. Among these, each gateway has the responsibility to establish a small-scale local VANET by clustering several nearby vehicles. All small-scale local VANETs further constitute a large-scale VANET. Vehicles are allowed to move freely from one small-scale local VANET to another.

Figure 1

Two-tier hierarchical structured VANETs.

We aim to propose a hierarchical structured VANET that has the scalability to accommodate large-scale deployment. In this study, we consider the network that includes two or more small-scale local VANETs to be a large-scale VANET. And the scale of small-scale subnet is related to the communication range of gateway and vehicle density. There is only one roadside gateway in a small-scale local VANET. And this gateway clusters the surrounding vehicles to establish a local VANET. In the same local network, vehicles can communicate with each other directly without relying on the roadside gateway. The intra-VANET communications comply with IEEE 802.11p standards. In addition, the communications of inter- and intralocal VANETs are supported in this architecture through Mobile IP and DSDV protocol, respectively.

Each vehicle is responsible for data collection through the devices installed in the vehicle. It sends these data to the roadside gateway in the same cluster with it and accesses Internet services through this gateway. In addition, the vehicle can exchange and share the information with another vehicle in the same cluster with it. If a vehicle requires to send messages to other vehicles in different clusters, it needs to transmit them through the gateway. Moreover, the initial gateway of a vehicle plays the same role of the home agent in Mobile IP. Therefore, this design enjoys all the benefits of Mobile IP.

The large-scale deployment of VANETs in the real world is facing many difficulties in the policy, economy, technology, and so forth. In the aspect of technology, the two-tier hierarchical structured VANET architecture as one solution has good scalability. Furthermore, the mode that the large-scale network is divided into many subnets can control the flow and reduce congestion. The data transmission within a small-scale network does not need to cross the roadside gateways and, therefore, does not place an extra burden on the transmission lines of the entire network. However, if the network is divided into more detailed three or more tiers, it will undoubtedly add more control and maintenance overhead and is unnecessary.

3.2. DSDV

In VANETs, the design of routing is a challenging problem due to the frequent changes of network topology. And these changes are not usually noticed in advance. Typically, the routing protocols of ad hoc network can be divided into two categories: proactive and reactive approaches. As a proactive protocol, DSDV periodically distribute available routing information throughout the network to maintain the freshness of the routing table. On the contrary, a reactive protocol maintains the current routes on demand such as the ad hoc on-demand distance-vector routing (AODV) [12] and the dynamic source routing (DSR) [13].

DSDV is a table-driven routing protocol for ad hoc networks. This protocol is designed based on Bellman-Ford algorithm and to avoid the routing loop problem by giving each route entry a sequence number. The even sequence number generated by the corresponding destination node indicates that this link exists and, on the other hand, the odd sequence number indicates that the link has been broken. Each node periodically distributes updates of routing tables to maintain the consistency. When a mobile node receives routing information, it will compare this information with the previous information and the route with the latest sequence number is retained. If the two routes have the same sequence number, the route will be chosen according to the routing cost. The routing table records that expired will be deleted.

We employ DSDV to support intra-VANET communications in our hierarchical structured VANET. And the DSDV protocol is used to arrange the forwarding path when the communications between two nodes happen in the same local VANET. The small-scale VANET usually contains one roadside gateway and several vehicles around it. In such a local network, any proper routing protocol can be used to complete the data transmission between the vehicles and the vehicle to gateway communication. In this paper, we assume that all corresponding routings in the small-scale VANETs can be supported by using DSDV protocol.

3.3. Mobile IP

Mobile IP is a well-known network transmission protocol standard developed by the Internet engineering task force (IETF). It is the purpose of the design that allows the mobile devices to move from one network system to another, but the IP address of the device remains unchanged [5]. This enables the mobile node to maintain its connectivity on the move and to achieve roaming function within the Internet.

Mobile IP defines three functional entities: mobile node, home agent, and foreign agent. The home agent and the foreign agent are also referred to as mobile agents. When a remote communication entity sends an IP packet to the mobile node, the home agent intercepts the packet and compares the destination address of the packet with the home address existing in its own list. If there is the same address, the home agent encapsulates the packet and transmits it to the care-of address of the mobile node using the technology of the tunnel. Then the current foreign agent for this mobile node receives the packet and decapsulates it and then transmits it to the node. Therefore, the mobile node receives the data without changing its home address. When mobile nodes move across different foreign subnets, the care-of addresses will change.

We employ Mobile IP to support inter-VANET communications in our hierarchical structured VANET. The hierarchical VANET is presented in the form of two-tier structure, including the backbone composed of roadside gateways as the upper layer network and the small-scale local networks composed of each roadside gateway and its surrounding vehicles as the underlying networks. Each roadside gateway also acts as the roles of the home agent and the foreign agent. Each vehicle is equivalent to a mobile node and moves in different small-scale local VANET. When a vehicle moves from the home network (a small-scale subnet) which contains its registered home agent (typically a roadside gateway in the home network) to the foreign networks (other small-scale subnets), in order to ensure that IP addresses are not lost, the vehicle needs to obtain its care-of address and to register at its own home agent. When a mobile vehicle leaves its home network, the packets destined to it will be sent directly to the gateway of its current foreign network. Thereafter, DSDV forwards the messages to the mobile vehicle.

In our proposed hierarchical VANET, in order to optimize the data transmission and improve scalability in a large network, the roadside gateways divide the small-scale local subnets from the large-scale network; that is to say, the large-scale VANET is composed of some small-scale local VANETs. And, taking into account the vehicle mobility that the vehicles move frequently among various subnets, all of these make the unchanged IP addresses necessary. Therefore, in order to ensure that the moving vehicles remain ongoing communication when the links are switching, using Mobile IP technology in inter-VANET communication is one of the important solutions.

3.4. Network Configuration Parameters

Given our VANET structure, we investigate the influence of network configuration parameters such as node density, mobility, and number of gateways on the network performance.

In the large-scale VANET, node density can be expressed as the number of vehicles within the unit area. In each local VANET, with the growth in the average number of vehicles, the average number of neighbors correspondingly increases for each vehicle. Consequently, the probability of successful communication between a vehicle and a roadside gateway through several nearby vehicles will increase. Therefore, the performance measures such as the average transmission delay and the delivery ratio will be improved.

The mobility of node is considered one of the important factors for network performance in a VANET. With the speed of vehicles increasing, more rapid changes of the network topology will happen and so does the shorter connectivity period of the paths. Thus, the average transmission delay and packet loss will increase due to the frequent breakage of link and new path discovery.

We consider the number of gateways corresponding to the number of small-scale local VANETs in our proposed VANET structure. In a large-scale VANET, increasing the number of gateways distributed uniformly can improve the probability that vehicles communicate with gateways through a small number of hops. Moreover, the burden of each gateway will be reduced. As a result, the average transmission delay and packet loss ratio will decrease.

A detailed analysis on the influence of these configuration parameters on network performance will be given in the following sections.

4. Performance Analysis Method in VANET

4.1. Performance Analysis on Routing Protocols

There are many researches [14, 15] focusing on the routing protocols in VANETs to increase communication reliability. Most of them evaluated their relative performance from two aspects: the packet delivery ratio and the average end-to-end delay [16].

4.2. Performance Analysis on Connectivity

In [17], the performance of multihop connectivity was investigated. The authors provided the outage connectivity probability and the successful probability of message hopping in their proposed multihop VANET. Many existing works [18, 19] study the influence of key parameters, including vehicle density, speed of vehicles, radio communication range, and roadside units, and evaluate the feasibility and performance of some applications.

4.3. Performance Analysis on DSRC

Dedicated short-range communication (DSRC) is a standard to support wireless access in VANET environment. Compared with the traditional cellular or WiMax communication, it is more adaptable to the vehicle communication environment with the characteristic of low cost, short range, and high data rate (6–27 Mbps) [20]. The concepts of communication reliability (CR) and application-level reliability (AR) were proposed in [21]. And two metrics are used to achieve better communication reliability: packet delivery ratio and distribution of consecutive packet drops. In [22], the researchers defined the communication density in order to measure the channel load and utilize it to reflect the scalability.

The main goal of our work focuses on analyzing the performance of proposed hierarchical structured VANETs. We assess the feasibility of this architecture and evaluate the network performance. Furthermore, we study the influence of key network parameters so that we can give some suggestions on configuration parameters such as network density and the number of gateways.

5. Performance Analysis

In our earlier study, the performance issue of a large-scale VANET has been briefly discussed. Here we provide a more detailed description. We consider a freeway scenario with a number of gateways deploying along the roadside to provide direct communications to the Internet. A larger scale of the VANET results in a higher average number of hops between a destination node and source node.

The relationship between the number of hops and the end-to-end period was studied in [23]. A higher number of hops and a higher mobility of nodes would result in a shorter connectivity period of the routing path. In this study, a freeway scenario was considered. With a probability of $90\%$ , a five-hop routing path will be established in 3.5 s when the speed is set to 72 km/h. In addition, the duration will be reduced further with the higher mobility of the vehicles or the higher number of hops.

In [24], considering a freeway scenario, the relationship between the network density and the network connectivity was discussed. When the particular distances between vehicles and roadside gateways are given, the probability of network connectivity that the vehicle can successfully communicate with the roadside gateway can be calculated. Furthermore, a high number of the vehicles that are described by network density ensure high network connectivity. Particularly, when the vehicles are not uniformly distributed, a more stringent requirement is desired [25].

In the following section, we will investigate the connectivity issues including the routing path connectivity by calculating the probability that an end-to-end routing path will become invalid and the network connectivity and k-connectivity analysis of a hierarchical structured VANET by calculating the probability that a vehicle can communicate with the roadside gateway via intermediate vehicles. Table 1 summarizes the parameters used in this section.

Table 1

Performance analysis parameters.

Parameter	Value
Mobility model	Highway
Length (L)	1000 m
Transmission range (R)	200 m
Average vehicle density (λ)	5,10,15,20 (Vehicles/km)
The speeds of vehicles	30,20,10,2 (m/s)
Normalized speed (m)	0.15,0.1,0.05,0.01
Normalized distance between a vehicle and its roadside gateway (d)	$\mathrm{2,3},\mathrm{4,5}$
Intervehicle communication standard	IEEE 802.11p

5.1. Routing Path Connectivity Issue

In a practical large-scale VANET, the network structure should follow a hierarchical form. In our consideration, all roadside gateways that serve their respective local VANETs are connected to establish a large-scale network. The roadside gateways form a backbone network, and an amount of vehicles near the roadside gateway will be clustered to form a small-scale local VANET. In view of the above, it is full of significance to do such a research work on the scale of the small-scale local VANET.

We first study the influence of the mobility on the routing path. According to the characteristics of vehicle movement, the vehicles can move in two directions, the opposite direction and the same direction, in the same road segment. Therefore, we need to consider two aspects. Given by [23], $T_{od}$ indicates the random variable that is used to describe the link connectivity period of two communication peers. In this scenario, the vehicles move in the opposite direction with a normalized speed m. Then we have

$$\begin{array}{l}\text{Pr}\{T_{od}\le t\}\\ \hspace{1em}=\{\begin{array}{ll}1-\frac{1}{30m^2{t}^2},\hfill & t>\frac{1}{m}\hfill \\ 1-\frac{1-2{\left(1-mt\right)}^6}{30m^2{t}^2},\hfill & \frac{1}{2m}<t\le \frac{1}{m}\hfill \\ 1-\frac{{\left(1-2mt\right)}^6-2{\left(1-mt\right)}^6+1}{30m^2{t}^2},\hfill & 0<t\le \frac{1}{2m}\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(1)

Let the quantity $T_{sd}$ describe the link connectivity period of two communication peers. In this scenario, the vehicles move in the same direction with a normalized speed m, and we have

$$\begin{array}{l}\text{Pr}\left\{T_{sd}\le t\right\}\\ \hspace{1em}=\{\begin{array}{ll}1-\left(\frac{2}{5mt}-\frac{1}{15m^2{t}^2}\right),\hfill & t>\frac{1}{m}\hfill \\ 1-\frac{2}{30m^2{t}^2}\left[6mt+{\left(1-mt\right)}^6-1\right],\hfill & 0<t\le \frac{1}{m}\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(2)

Furthermore, let $T_s$ describe the link connectivity period in the scenario that a stationary roadside gateway communicates with the vehicle moving away from it, and then we have

$$\begin{array}{cc}& \text{Pr}\left\{T_s\le t\right\}=\{\begin{array}{cc}1-\frac{1}{3mt},\hfill & t>\frac{1}{m}\hfill \\ 1-\frac{1}{3}\left(m^2{t}^2-3mt+3\right),\hfill & 0<t\le \frac{1}{m}\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(3)

In this study, we investigate the end-to-end connectivity period between two communication peers. One of the nodes is a mobile vehicle and the other is a roadside gateway. In VANET, the links are unstable and suffer from frequent breakages due to the high mobility of vehicles and obstructions. According to the approach given in [23], we make an appropriate modification to plot the numerical results as shown in Figure 2. This figure shows the cumulative distribution of the connectivity probability that the routing path becomes invalid where the numbers of hops h are varied with 2, 3, 4, and 5, and the m is set to 0.1 (or 72 km/h). For a reactive routing protocol, a new routing path should be established, when the existing routing path becomes invalid. For a proactive routing protocol, updating the routing information among all relevant nodes must occur in order to restore the correct route. The ongoing packet routing may be temporarily interrupted during the path reestablishment period. And it will result in a long delay to the end user. Furthermore, the probability also reflects the robustness of the communications.

Figure 2

CDF of connectivity period for the h-hop routing path.

We can see that the high number of hops leads to the high probability that an existing routing path breaks due to the mobility of the vehicle. Obviously, the routing path breaks more frequently in the 5-hop scenario compared with a 2-hop scenario. To achieve a certain level of robustness in end-to-end communications, the probability of path breakage should be kept low. Based on our numerical study, reducing the number of hops represents one effective approach. In a large-scale VANET, this can be achieved through the design of a hierarchical structure. Vehicles can communicate with roadside gateways via a certain number of hops by deploying the roadside gateways properly. We can intuitively know that determining an appropriate gateway density is significant to reduce the probabilities of routing path breakage and improve the performance of network communications.

5.2. Network Connectivity Issue

We discuss the network connectivity probability in this section. According to [24], let $P_n(d)$ be the physical network connectivity probability between two nodes. The variable d indicates a given distance between them, and n indicates the number of additional nodes within a one-dimensional setup. Then we have

$$\begin{array}{cc}& P_n\left(d\right)=\{\begin{array}{cc}0,\hfill & n<d-1\hfill \\ {\left(1-{\left(1-\frac{1}{d}\right)}^n\right)}^{n+1},\hfill & n\ge d-1.\hfill \end{array}\end{array}$$

(4)

Likewise, we consider setting an appropriate freeway scenario. In (4), the value of d is normalized to the transmission range and let $b=n/d$ indicate the density of the network. Here we study the probability of network connectivity with various values of b and d.

For a fully connected local VANET, we evaluate the basic requirement of the network density in Figure 3. In other words, we study the probability that a roadside gateway can communicate with the vehicle located at d distance away from it via intermediate vehicles. As can be seen from the results, to maintain a certain probability, the demand for network density is lower for a shorter distance. When the distance variable d between a vehicle and its roadside gateway is 2, the network connectivity probability is approximately 0.9 where the network density is 3, while the network connectivity probability is approximately 0.5 in the case of $d=5$ . With a smaller distance between the roadside gateway and the vehicle, a lower number of hops can be obtained which contributes to the establishment of the robust end-to-end communications.

Figure 3

The probability of network connectivity versus network density.

5.3. k-Connectivity Analysis

The link outages appear frequently in VANET due to the characteristics of application environment, such as the high mobility of vehicles, fading, and shadowing. Moreover, some vehicles running on the road may suddenly leave the network, for example, at intersections, parking lots, highway exits, and others. All of these factors may cause the network to disconnect. It is well-known that the connectivity of the network is always associated with network performance. Thus, the remainder of connectivity is an important issue, when some nodes and links fail. That is to say, a high connectivity level of VANET is desired. Any two remaining vehicles should communicate even if some vehicles depart. The notion of k-connectivity can be used to measure this.

A graph is called k-connected only if there does not exist a situation that the graph is splitted into some disjoint connected set after a set of ( $k-1$ ) vertices removal. A network can be modeled by a graph, imagining that the vertices correspond to the vehicles or gateways on the roadside and edges to the links between them. A VANET is said to be k-connected if departure of any ( $k-1$ ) vehicles does not disconnect the network. In other words, a sufficient and necessary condition for the VANET to be k-connected is that there exist at least k disjoint paths between every two nodes in the network.

In most cases, we can achieve the reliability of communication and the QoS requirements by satisfying the conditions of k-connectivity ( $k\ge 1$ ). In addition, k-connectivity is helpful to balance the network load and node energy level. In this way, the fault tolerance and robustness can be enhanced in a k-connected vehicular ad hoc network. In many scenarios, connectivity enables any node to communicate with others to achieve proper functioning of a network. The analysis of k-connectivity will benefit the design and investigation of large-scale VANETs.

There exist many research efforts on the factors which impact the probability of k-connectivity in the fields of associated geometric graphs, wireless sensor networks, and so forth. The k-connectivity has shown remarkable differences with distinct network conditions. In VANET, we consider the impacts of the value of k, different node densities, and mobility. In addition, the k-connectivity property is also impacted by diverse conditions such as nonuniform node distribution, distinct channel conditions, path loss, fading, and shadowing characteristics.

According to the theorem in [26], we know the property that the probability of a geometric random graph being k-connected approximates to 1 when the number of neighbors for a node is not less than k. Let $P_{\ge }(k)$ denote the probability of k-connectivity. We refer to this property and express the relationship as the following:

$$\begin{array}{cc}& P_{\ge }\left(k\right)\approx P\left(n_d\ge k\right),\end{array}$$

(5)

where $n_d$ is the minimum degree of a node; then the probability that the number of neighbors per node is at least k is denoted as $P(n_d\ge k)$ . The expression of $P(n_d\ge k)$ is given as

$$\begin{array}{cc}& P\left(n_d\ge k\right)={\displaystyle \sum }_{i=k}^{\infty }{\displaystyle \sum }_{j=k}^{i}P(i,\lambda )\left(\begin{array}{c}i\\ j\end{array}\right)P_c^j{\left(1-P_c\right)}^{i-j}.\end{array}$$

(6)

Here, $P_c$ denotes the probability of successful link connectivity. We consider that nodes are randomly distributed with average density λ using a Poisson process. The probability that there are i nodes in the region of road with a finite length L is expressed as $P(i,\lambda )$ . Then, we have

$$\begin{array}{cc}& P\left(i,\lambda \right)=e^{-\lambda L}\frac{{\left(\lambda L\right)}^i}{i!},\hspace{1em}i\ge 0.\end{array}$$

(7)

In addition, we assume a uniform placement of these i nodes over the plane region, and each node has the same communication range.

As described previously, we still consider the link reliability of three possible motions between two adjacent nodes: (a) the nodes move in the opposite direction and far away from each other, (b) the nodes move in the same direction and the faster node is in front, and (c) one node is stationary and the other node moves away from it. These movement trends have led to the increasing of the distance between the two nodes and the interruption of link will happen with a higher probability. In this section, we still evaluate the network connectivity by the period of time that a link remains connected. Our works focus on the scenario (b) and are easily modified to apply to more complex situations. In this scenario, $P_c$ is given by $1-\text{Pr}\{T_{sd}\le t\}$ . Thereafter, substituting $P_c=1-\text{Pr}\{T_{sd}\le t\}$ into (6), we can calculate the probability of k-connectivity.

In VANET, we evaluate the interaction between the probability of  k-connectivity with the node mobility, the node density, and the value of k. The vehicles have been uniformly placed over a region of L  =  1000 m. And average node density λ is varied with $5\times 10^{-3}$ , $10\times 10^{-3}$ , $15\times 10^{-3}$ , and $20\times 10^{-3}$ . As previously mentioned, we assumed the same communication radius R  =  200 m for each node. In addition, the speed of node, m, is normalized to the transmission range [23]. Figure 4 shows the probability of k-connectivity in terms of the different speeds when the value of k is 3 and the node density λ is 10/km. The normalized m values used are 0.15, 0.1, 0.05, and 0.01, which, respectively, correspond to the speed of 30 m/s, 20 m/s, 10 m/s, and 2 m/s. We can see that, from overall trend, the higher probability of k-connectivity will be obtained at lower speeds. For m of 0.15 (30 m/s or 108 km/h), the probability that the network is 3-connectivity is less than 10% before 40 s. In contrast with m of 0.01 (2 m/s) like the scenario of traffic jams, the probability of 3-connectivity stays high over time. According to the analysis, movement of the vehicle largely affects the network connectivity.

Figure 4

The probability of 3-connectivity for the different speeds when λ  =  10/km.

In Figure 5, the relationship between the node density and the probability of k-connectivity is shown with k  =  3 and m  =  0.1 (20 m/s or 72 km/h) as the most general case. $P_{\ge }(3)$ is 0.065, 0.278, 0.519, and 0.709 at 20 s, when the average density λ is 5/km, 10/km, 15/km, and 20/km, respectively. We observe that, as the node density increases, the probability $P_{\ge }(3)$ increases at a given speed of the nodes. When the density of the node is very low, the fall in the k-connectivity probability is quite rapid. In other words, a higher probability of 3-connectivity can be obtained by increasing the node density even in a high mobility condition. The link between two vehicles breaks with a higher probability due to the higher mobility of node, as mentioned earlier. To achieve a high network connectivity probability, it is often desirable to reduce the distances between the sender and recipient to increase the network density.

Figure 5

The probability of 3-connectivity for the different node densities when $m=0.1$ .

Thereafter, we calculated the k-connectivity of the network at k = 1, 2,…,15, for λ = 5/km, λ = 10/km, λ = 15/km, and λ = 20/km, respectively, as illustrated in Figure 6. The value of m is also given as 0.1 and Figure 6 is captured at the time instant that is 20th second. For the increasing values of k, the k-connectivity probability decreases badly. Meanwhile, we can increase the number of nodes to improve this situation. When λ = 5/km, the probability of 4-connectivity is almost zero. Even in the case where λ = 20/km, the probability of 9-connectivity also approximates to zero and the probabilities $P_{\ge }(k)$ equal 0 at higher values of k (k = 9,10,…,15). Furthermore, as shown in the figure, under the same conditions of node density, the VANET has the higher probabilities of k-connectivity when the values of k are lower. Therefore, a shorter distance and lesser number of hops between the roadside gateway and the moving vehicles can help to improve the performance of network connectivity. As the design of our hierarchical VANETs, we can achieve a lower number of hops and a higher connectivity probability by deploying the roadside gateways reasonably.

Figure 6

The probability of 3-connectivity for the different values of k.

6. Conclusions

The researches on the vehicular ad hoc network have caught public attention due to the popularity of the vehicle and the development of wireless communication technology and vehicle technology. Considering the performance issue of a large-scale VANET, we integrate the DSDV protocol and Mobile IP with the VANETs to form a hierarchical structured large-scale VANET. A collection of roadside gateways play the role of backbone directly connecting to the Internet, while each roadside gateway clusters a number of vehicles nearby to form a small-scale local VANET. We apply the DSDV protocol to support intra-VANET communications and the Mobile IP was used to support inter-VANET communications. In this paper, we analyzed the performance of our proposed design in terms of the routing path connectivity and network connectivity. We are able to suggest some key parameters of network configuration for a specific scenario, such as the network density and the number of gateways. We confirm that the proposed design is feasible with proper configuration parameters.