Received 20 April 2016; accepted 14 June 2016; published 17 June 2016
With the development of wireless communication network, Vehicular Ad-Hoc Networks (VANETs)  have received more and more considerable attention. In VANETs, some road-side units (RSUs), which can serve for vehicles to access the Internet, are placed along the road. Common vehicles access a RSU to get service base on multi-hop. So VANETs can realize various different applications to share the entertainment information, optimize the route and enhance the safe level of driving  . Especially, in some emergency circumstances, VANETs have an irreplaceable role such as transferring accident message, getting a free lane for ambulance and so on. Although VANETs can change our life in many hands, it also meets some challenges. Getting methods to make transmission delay satisfy some emergency scenarios such as congestion scenario is one of challenge problems.
In actual situation, on one hand, RSU’s number is finite because of RSU’s high cost. On the other hand, the coverage of RSU is limited. Too many requests from mobile vehicles to one RSU may bring about long communication delay and lots of collisions  . Many researchers commit themselves to decreasing delay and ensuring the delay within a certain acceptable range. Liu et al.  analysed the message delivery delay in a bidirectional traffic model and got that the message delivery delay had a linear relationship with the message forwarding distance. It gave the relationship between delivery delay and the relay distance but didn’t give efficient decreasing strategy  . He et al.  proposed an optimal link strategy and an optimal touting strategy to minimize the expected path delay based on the store-and-forward framework in large-scale VANETs with buses and taxis. Ju et al.  provided an efficient and adaptive location-aided gateway discovery mechanism in 3G-VANETs integrated network. In this mechanism, some vehicles, which have both UTRAN (Universal Mobile Telecommunication Systems Terrestrial Radio Access Network Interface) and IEEE 802.11p interface, were selected as gateways. The all vehicles in one hop range of a gateway will access this gateway. And the one hop coverage of one gateway is adaptive about the delay limitation. This mechanism can guarantee the average delay of packets within an allowable range  . But in actual situation, there are not so many vehicles having both UTRAN and 802.11p interface. Besides its model is only suitable for one-hop accessing gateway and doesn’t consider the situation of unable connecting the gateway by one-hop. Assuming we can solve these two points, the effect will be better. When we attempt to find some methods, the hierarchical perspective wins our confidence. There are some researchers paying attention to it. Zhu et al.  extended the technique of integrating Mobile IP with MANET into VANETs. Transmission delay and delivery ratio were analysed in a two-tier hierarchical structured VANETs including gateways and mobile vehicles. Liu et al.  provided an overall mastery of security system architecture in hierarchical analysis that set the brief direction for future researches. De Castro et al.  proposed a hierarchical architecture for content distribution in VANETs. This architecture consisted of two layers for the vehicular environment and the network infrastructure, didn’t discuss how to apply the hierarchical thought to the link scheme. So in this paper, we apply the hierarchy viewpoint into link scheme for a better delay guarantee.
In this paper, some vehicles will be selected as the accessing help points (AHPs) and classified into different hierarchies. AHPs deployed in different hierarchies have different transmission radius. These AHPs can not only communicate with RSUs or its prior hierarchical AHPs, but also serve for the common vehicles. We choose the moving AHPs in VANETs, which can make all vehicles uncovered by RSUs access the Internet with less delay. We propose an optimal hierarchy algorithm, which can get the most reasonable hierarchy number based on the link delay and the vehicle distribution. Besides, the hierarchical link scheme in VANETs contributes to decreasing communication delay, which gives a new perspective for the VANETs. The simulation results illustrate the affectivity of our hierarchical link scheme.
The remainder of this paper is organized as follows. In Section 2, we give the system model. In Section 3, we present two different hierarchical methods. Section 4 gives the optimal hierarchical number algorithm based on the link delay analysis. The initialization and update process in our hierarchical link scheme is proposed in Section 5. Section 6 presents the related simulations and we conclude this paper in Section 7.
2. System Model
We introduce the hierarchical link scheme in this paper to help vehicle accessing more efficiently and more rapidly than the pure multi-hop VANETs in congestion scenario. We suppose that vehicles move on a one-dim- ension road because any scenario can be established by the straight road. Some RSUs are deployed along the road and vehicles are uniformly distributed in the network because of congestion. Due to the limitation of the vehicle’s transmitting radius, the data transmission from a source vehicle to a RSU can be interrupted. Thus the remote source vehicle needs the help of the relay vehicles when it sends packets to the RSU. With no doubt, the larger hop numbers cause the longer delay, as shown in Figure 1. Based on the relay strategy, we select some moving vehicles as the AHPs to help the communication. Different AHPs which have different communication radius are deployed in different hierarchies. Let L denote the length of the one-dimension road. Let k denote the number of hierarchy (k is an integer over 0). According to whether the whole road is covered or not, we have different hierarchical methods, inward progressive hierarchical method when the whole road is fully covered by RSUs and outward extend hierarchical method when the whole road is not fully covered.
In our system model, we analyse the uplink delay when a source vehicle sends request for service. When the RSU number is enough to cover the whole road, we will analyse the maximal link delay of a resource vehicle uplink request in k-hierarchy link scheme with inward progressive hierarchical method. When can satisfy our demand, the other vehicles will have delay guarantee. At the same time, we need to get the optimal k and the corresponding positions of AHPs in various hierarchies to minimize the delay. When the road is not fully covered, we hope all vehicles can access rapidly with less delay. Thus we will evaluate the average link delay in k-hierarchy link scheme with outward extend hierarchical method. At the same time, we need to get the optimal k and the corresponding positions of AHPs in various hierarchies to minimize the delay.
In this hierarchical link scheme, the link delay is changeable with the hierarchy k. To get the optimal hierarchical number in our model, some assumptions are listed as follows:
(1) Because of road congestion the vehicle positions obey uniform distribution U (0, L). L is the length of one road. The moving status of vehicle is relatively stable, which means the vehicle positions are relatively changeless. RSUs are deployed along the road uniformly. The coverage radius of every RSU is R (R ≤ L).
(2) Because the vehicle speed is far less than the transmission speed. So we assume that the one-hop delay is the same marked by T0 whether the vehicle is a moving AHP or not. In view of this assumption, the link delay can be calculated by computing the number of relay hops.
(3) Because the distance between two vehicles is small in congestion scenario. There is at least one vehicle in every vehicular communication radius r (r < R < L), which ensure all packets have successful paths to a RSU.
3. The Hierarchical Link Scheme in VANETs
According to the RSU number, we will give two hierarchical methods. One is inward progressive hierarchical method and uplink scheme when RSUs cover the whole road. Another is outward extended hierarchical method and uplink scheme when RSUs don’t cover the whole road.
3.1. Inward Progressive Hierarchical Method and Uplink Scheme When RSUs Cover the Whole Road
When all vehicles are covered by RSUs, we select some vehicles as the moving AHPs, which are classified as k different hierarchies as shown in Figure 2. We choose two vehicles positioned in R/2 as the first hierarchical moving AHPs (marked as AHP1), such as vehicle a and d. Then we select some vehicles as the second hierarchical moving AHPs (marked as AHP2) beside AHP1 with the similar method, such as vehicle b, c, f, e. The distance between AHP1 and AHP2 is R/4. We define that when i < j, the hierarchy of AHPi is higher than AHPj. The transmission radius of AHP1 is equal to or little greater than R/2 to ensure that AHP1 own packets can be received by RSU. Similarity, transmission radius of AHPi is equal to or little greater than R/2i to ensure that AHPi own packets can be received by its up layer AHP.
Figure 1. The VANET based on multi-hop.
Figure 2. The hierarchical link scheme when RSUs cover the whole road.
When a source vehicle would like to access Internet for service, it firstly judge its position interval according to its own position. If the vehicle is positioned in interval [RSU AHPk−1] or [AHPk−1 BPR], it have two paths to transmit its packets. BPR means the boundary point of RSU radius. One path means transmitting straightly to the RSU through multi-hop without the help of AHPs. Another path means transmitting to the closest AHP which will relay the packets to its up layer AHP until the packets received by the RSU. The vehicle will choose the path with fewer hops for transmitting packets. If the two values of hop are the same, the vehicle will choose the path through multi-hop, because this way can relieve the stress of AHPs. For example, in Figure 2, we assume the optimal k is 3 and vehicle i is in the interval [RSU AHP2]. It has two paths to the RSU:
(1) i → g → RSU
(2) i → h → AHP2 → AHP1 → RSU
Because the hop number of each path is different, so vehicle i will choose the path with fewer hop number to transmit its packets.
If the vehicle is positioned in interval of two AHPs, it will have three paths for selection. One path still means transmitting straightly to the RSU through multi-hop without the help of AHPs. The rest two paths mean transmitting to AHPs on its own both sides and then the two AHPs relay the packets to its up layer AHP until the packets received by the RSU. The vehicle will choose the path which has the fewest hop number to transmit. If there are two or three paths having the same hop number, it will choose the path without AHP firstly, and then choose the path whose first AHPs hierarchy is higher (e.g. AHP1 is higher than AHP2). For instance in Figure 2, vehicle j need send the requesting data. It has three paths for selection,
(1) j → c → h → i → g → RSU
(2) j → AHP2 → AHP1 → RSU
(3) j → k → AHP1 → RSU
The path 2 and 3 have the same hop number. Because the first AHP (AHP1) in path 3 is higher than that path 2 (AHP2), vehicle j will choose path 3 as the transmitting path. This selection can also relieve the stress of AHP2 to some extent.
With this hierarchical and uplink scheme, the vehicle which is furthest from RSU has the maximal hop number. Although the link hierarchical number k can be quite large theoretically until the radius of AHPk−1 is equal to the common vehicle radius, we find that when k is larger than a threshold, the hop number to the RSU increase with the increase of k. The increase of hop number means the larger delay. So the hierarchy k is not the larger the better and we need to research the optimal k based on maximal delay limitation.
3.2. Outward Extend Hierarchical Method and Uplink Scheme When RSUs Uncover the Whole Road.
When all vehicles are not fully covered by RSUs, we hope all vehicles can access Internet by one RSU under the delay limitation. As shown in Figure 3, we choose two vehicles as AHP1 (such as vehicle c and b) whose distance to the RSU is marked as x1, whose transmission radius is marked as R1. There is a constraint,
which ensure the AHP1’s packets can transmit to RSU successfully. Similarity, we also select another two
Figure 3. The hierarchical link scheme when RSUs don’t cover the whole road.
vehicles which are remoter to the RSU than AHP1 as AHP2 (such as vehicle a and d ). x2 means the distance between the AHP1 and the AHP2. So there is a restriction set,. We just select AHPs with the optimal sets, properly, which can make all vehicles access available with less delay. As shown in Figure 3, there are 4 hierarchies (k = 4). We have the restrictions,
where NRSU means the number of RSUs along the road.
When a source vehicle wants to send request to a RSU, the vehicle will also judge its position interval according to its own position similar to Section 3.1. If the vehicle is posited in [RSU AHP1], its packets will be transmitted to the RSU through the multi-hop without the help of AHPs. If the vehicle is located in [AHPm−1 AHPm] or [AHPk−1 BPC], (), its packets will be transmit to the AHPm−1 through multi-hop. BPC means the boundary point of coverage which RSU need to cover. Then AHPm−1 will relay the packets to its own up layer AHP (AHPm−2) until packets are received by RSU.
For instance, in Figure 3, vehicle h wants to send packets to RSU, its packets will have the same path h → i → g → RSU as the situation which has no AHPs. But when vehicle j wants to transmit information, its request will received by RSU through the path: j → h → AHP3 → AHP2 → AHP1 → RSU.
4. The Optimal Hierarchical Number with the Delay Analysis
In order to get the optimal hierarchical number, we give the following definitions.
(1) The maximal link delay means the longest time from a packet being sent to being received by the RSU. Link delay can be express by Equation (4),
where N denotes the number of vehicles which send packets to one RSU. means every vehicle’s delay. means every vehicle’s hop number when it sends packets to RSU. T0 means the delay of one single hop.
(2) The hop number from common vehicle to RSU is related to not only common vehicle transmission radius r but also distance between the common vehicle and the AHPs beside itself. So the maximal hop number must happen to the remotest one in the inward progressive hierarchical method. So the max link delay can be calculated by
where means the distance between the vehicle i and its closest AHP. And if the vehicle is playing the moving AHP role, its distance is 0. means the min integer larger than. HAN means the hop number of vehicle N’s up layer AHP. In this paper, we choose stand for the to simplify the compute.
4.1. The Optimal Hierarchical Number Based on Delay Analysis When RSUs Cover the Whole Road
(1) When k = 1, There is a single hierarchy network without AHPs. All vehicles on the whole road are common vehicle, as the traditional VANETs shown in Figure 1. The radius of the RSU is denoted by R, and r means the radius of the common vehicle. We can get,
(2) When k = 2, There is two-hierarchy network. Due to the uniform distribution, we can get the maximum of d2(i) according to R and r. So we can get,
(3) When k = m, There is m-hierarchy network. When we extend the hierarchy to m, we can get,
According to Equation (8), the is changing with the various m. To make the delay least possible we need get the optimal k. So we introduce
as a function about variable k. Then we can get the first derivation of expressed by,
When, we can get the extreme value ke as the optimal k shown in Equation (11)
4.2. The Optimal Hierarchical Number Based on Delay Analysis When RSUs Uncover the Whole Road
When the whole road is not fully covered by RSUs, we analyse the average delay of uplink. When k = m, the system is an m-hierarchy network. There are two AHP1s, two AHP2s until two AHPm−1s in our system. mean distance of each neighboring AHP positions. x1 means the distances between AHP1 and RSU. mean AHPs’ radius accordingly. σ means the density of vehicle distribution in one-dim- ension.
(1) The total hop number of vehicles in [RSU AHP1] H1 can be calculates by
(2) The total hop number of vehicles in [AHP1 AHP2] H2 can be given by
(3) Similarly, the total hop number of vehicles in [AHPm−2 AHPm−1] Hm−1 is
(4) The total hop number of vehicles in [AHPm−1 BPC] Hm is calculated by
Then we can get the average up-link delay as the objective function
There are some restrictions
To simplify the restrictions, we have Rj = xj. So there are
According to the formula of, the square term is much larger than one degree term. So when the numerator gets the smallest and gets the smallest. So we can get the optimal k and set to make get the least value.
5. The Initialization and Update of AHPs in the Hierarchical Link Scheme
In our hierarchical link scheme, all vehicles get their own positions by GPS technology and exchange positions with their neighbors in transmission range every fixed time. As shown in Figure 4(a), V1, V2, V3, V4 in one hop range, so they share their own positions with each other. For instance, the V1 have a table such as Table 1 to save its neighbors’ positions. V2, V3, V4 in Figure 4(a) and V12, V13, V14 in Figure 4(b) also have the similar tables. All vehicles will update their own position every fixed time. Our system will update the AHPs every ∆T time. Because the vehicle speed is low and relative position is stable in congestion scenario, so the influence caused by different ∆T to delay can be ignored.
When the number of RSUs is enough to cover the whole road, there are some steps to realize the initialization and updating process.
Step 1. After RSU confirm the optimal hierarchical number k, RSUs will broadcast a message packet including
Figure 4. The initialization and update of AHP.
Table 1. Neighbors’ positions of V1.
, where Pij means the jth position of AHPi
(and), P0 means the RSU’s position.
Step 2. All vehicles on the road will receive the message from RSU and save this message, then each vehicle will compare its own position and the position of AHPi. If one vehicle’s position is in one interval of, it becomes the candidate of AHPi. Because of the position sharing of neighbors’ position, the one who is closest to the Pij among these candidates becomes the jth AHPi and changes its own transmission range.
Step 3. After ∆t time, all vehicles update their own position information and renew the AHPs.
We assume the k = 4 in Figure 4(a) and there are a segment of pseudo-code to identify how to confirm AHPi as shown in Algorithm 1. PVx means the position of vehicle x. PVNx mean the all positions of vehicle x’s neighbors.
When the number of RSUs is not enough to cover the whole road, there are also some steps to realize the initialization and updating process.
Step 1. After RSU confirm the optimal hierarchical number k and the corresponding position, RSUs will broadcast a message packet including all AHPs position information.
Step 2. Because of the existence of uncovered vehicle by RSU, some vehicles can’t receive the message. So vehicles not only need to judge whether themselves are AHPs, but also judge whether they are AHPs out of the RSU coverage. If the vehicle is the AHP which is out of the RSU coverage, after the AHP change its own transmission radius, the AHP will relay the packet to the vehicles in its transmission range until the packet can be received by candidates of AHPk−1.
Step 3. After ∆t time, all vehicles update their own position information and renew the AHPs.
We assume the hierarchy number is k, and l=L/NRSU > R. There are only a part of vehicles receiving the packet from the RSU. So Algorithm 2 and Algorithm 3 express the initialization and updating process. The other AHPi has similar process.
Algorithm 1. The process of confirming AHPi when the whole road is covered by the RSU.
Algorithm 2. Confirming i value of remotest AHPi when the whole road is not covered by the RSU completely.
Algorithm 3. The process of confirming AHPi when the whole road is not covered by the RSU completely.
In this section we give some simulations. It comprises simulation scenario setup and performance analysis.
6.1. Simulation Scenario Setup
The simulations are performed by the VanetMobilsim and the NS-2  simulator 2.33 version. VanetMobilsim generates the simulation scenario file used in NS-2 simulator. In our simulation, the transmission range of common vehicle is 100 m. Because the vehicle density and speed can influence the result, so they are set different. The number of node in the road is varied from 50 to 250 in step of 50. The vehicle speed maximums are set as 2, 6, 10 (m/s). We applied our hierarchical link scheme into the Greedy Perimeter Stateless Routing (GPSR)  which is one of geographic routing protocols. The reason of selecting GPSR as routing protocol is that the initialization and update process in our hierarchical link scheme is based on location information. Also, GPSR is based on geographic location and used in many research works  . Other conventional parameters in NS-2 are set as Table 2.
Table 2. Parameter setting in simulations.
We compare the average end-to-end delay for different hierarchical number k in each of our proposed two hierarchical link methods as shown in Figure 5. Because only vehicle in one hop can access Internet by method in paper  . We proposed method can suitable for multi-hop. So we compare the average end-to-end delay for different vehicle numbers in paper  method and proposed two hierarchical link methods as shown in Figure 6.
When the inward progressive hierarchical method is used, Figure 5(a) reflects the delay trends with different hierarchical number k at different vehicle velocities. When the vehicle maximal speeds are fixed respectively, the average end-to-end delay all have a decrease stage with the increase of k firstly. However when k increases to a threshold, the average end-to-end delay increases oppositely. This trend is consistent with aforementioned theoretical analysis. When we select the moving AHPs with different transmission radius located in different hierarchies, AHPs can relay the packets to a remoter vehicle with one hop. So at first the delay decrease sharply. But when number of hierarchy increases to a threshold, the transmission radiuses of AHPk−1 decrease accordingly. So the effect of decreasing delay is not so obvious but present a rising trend. In Figure 5(a), we get that the optimal k is 7, which minimizes the average end-to-end delay.
When the outward extend hierarchical method is used, the delay trends with different hierarchical number k is shown in Figure 5(b). Analysing the simulation result, the average end-to-end delay trends firstly descend and then rise similarly to the trends using inward progressive hierarchical method. Comparing Figure 5(a) and Figure 5(b), we find that the average end-to-end delay presented in Figure 5(b) is higher than Figure 5(a). It is because that the outward extend hierarchical method need to make the vehicles uncovered by RSU have less delay. So the effect of decreasing delay is inferior to the inward progressive hierarchical method. The character is shown in Figure 6. We also get that the optimal k is 8, which minimizes the average end-to-end delay, in Figure 5(b).
In Figure 6, we compare the average end-to-end delay in paper  and the two hierarchical link schemes for different vehicle numbers. In paper  , some vehicles will be selected as gateways and other common vehicles access to the gateway in one-hop for getting service. The maximal velocity is the 4 m/s and the hierarchical number is the optimal value in Figure 5(a) and Figure 5(b). With the increase of vehicles, the average delay increases when using the method in paper  . It is because the number of vehicle in one hop increases, which make the waiting time for accessing longer. By the inward progressive hierarchical method and the outward extend hierarchical method, the average delay decreases with the increase of vehicle number. It is because the two
Figure 5. (a) The average link delay when RSUs cover the whole road (left figure), (b) The average link delay when RSUs don’t cover the whole road (right figure).
hierarchical methods both make the common vehicles distribute in different layers, which can relay packets to a remoter vehicle by the help of AHPs. When the vehicle number is small, the average delay in paper  is smaller than our proposed two hierarchical methods. But when the vehicle number increases to a certain extent, the average end-to-end delay in paper  is larger than our proposed two hierarchical link methods. So our proposed hierarchical link scheme can decrease the transmission delay in a higher vehicle density.
In this paper, we propose a hierarchical link scheme in VANETs. We discuss two different hierarchical methods
Figure 6. The average link delay with different vehicle number.
and deduce the maximal up-link delay and average up-link delay. Through the optimization we can get the optimal hierarchy value k. Our scheme can be used for some service in congestion scenario, e.g. getting an empty lane for ambulances. Our simulations illustrate that our hierarchical link scheme can decrease the transmission delay. In the future, we intend to investigate the combination of our hierarchical link scheme and bus system to make our hierarchical link scheme more useful.
This work is supported by the NSF of China under Grant No. 61301118; the Innovation Program of Shanghai Municipal Education Commission under Grant No. 14YZ130; the International S & T Cooperation Program of Shanghai Science and Technology Commission under Grant No. 15220710600; and the Fundamental Research Funds for the Central Universities under Grant No. 16D210403.
 Shahidi, R. and Ahmed, M.H. (2014) Probability Distribution of End-to-End Delay in a Highway VANET. IEEECommunications Letters, 18, C443-C446.
 Wagan, A.A. and Jung, L.T. (2014) Security Framework for Low Latency Vanet Applications. 2014 International Conference on Computer and Information Sciences (ICCOINS), Kuala Lumpur, 1-6 June 2014, 1-6.
 Ju, K., Chen, L.J., Wei, H.Y. and Chen, K.L. (2014) An Efficient Gateway Discovery Algorithm with Delay Guarantee for VANET-3G Heterogeneous Networks. Wireless Personal Communications, 77, 2019-2036.
 Liu, Y.Z., Niu, J.W., Qu, G.Z., Cai, Q.S. and Ma, J. (2011) Message Delivery Delay Analysis in VANETs with a Bidirectional Traffic Model. 2011 7th International Wireless Communications and Mobile Computing Conference, Istanbul, July 2011, 1754-1759.
 He, J.P., Cai, L., Cheng, P. and Pan, J.P. (2015) Delay Minimization for Data Dissemination in Large-Scale VANETs with Buses and Taxis. IEEE Transactions on Mobile Computing, 99, 1-14.
 Zhu, W.T., Zhang, Q. and Fong, A.C.M. (2013) On Testing for a Constant Hazard against a Change-Point Alternative. Green Computing and Communications (GreenCom), 2013 IEEE and Internet of Things (iThings/CPSCom), IEEE International Conference on IEEE Cyber, Physical and Social Computing, Beijing, August 2013, 1352-1356.
 De Castro, C., Raffaelli, C. and Andrisano, O. (2015) A Dynamic Hierarchical VANET Architecture for Named Data Networking Applications. 2015 IEEE International Conference on Communications (ICC), London, June 2015, 3659- 3665.
 Hu, L.L., Ding, Z.Z. and Shi, H.J. (2012) An Improved GPSR Routing Strategy in VANET. 2012 8th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), Shanghai, 21-23 September 2012, 1-4.
 Karp, B. and Kung, H.T. (2000) Boston, Massachusetts, USA GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, New York, 6-11 August 2000, 243-254.
 Ayaida, M., Barhoumi, M., Fouchal, H., Doudane, Y.G. and Afilal, L. (2014) Joint Routing and Location-Based Service in VANETs. Journal of Parallel and Distributed Computing, 74, 2077-2087.