P2) 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.