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 AHP_{k}_{−}_{1}] or [AHP_{k}_{−}_{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 AHP_{2}]. It has two paths to the RSU:

(1) i → g → RSU

(2) i → h → AHP_{2} → AHP_{1} → 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. AHP_{1} is higher than AHP_{2}). 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 → AHP_{2} → AHP_{1} → RSU

(3) j → k → AHP_{1} → RSU

The path 2 and 3 have the same hop number. Because the first AHP (AHP_{1}) in path 3 is higher than that path 2 (AHP_{2}), vehicle j will choose path 3 as the transmitting path. This selection can also relieve the stress of AHP_{2} 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 AHP_{k}_{−}_{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 AHP_{1} (such as vehicle c and b) whose distance to the RSU is marked as x_{1}, whose transmission radius is marked as R_{1}. There is a constraint,

(1)

which ensure the AHP_{1}’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 AHP_{1} as AHP_{2} (such as vehicle a and d ). x_{2 }means the distance between the AHP_{1} and the AHP_{2}. 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,

(2)

and

, (3)

where N_{RSU} 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 AHP_{1}], its packets will be transmitted to the RSU through the multi-hop without the help of AHPs. If the vehicle is located in [AHP_{m}_{−}_{1} AHP_{m}] or [AHP_{k}_{−}_{1} BPC], (), its packets will be transmit to the AHP_{m}_{−}_{1} through multi-hop. BPC means the boundary point of coverage which RSU need to cover. Then AHP_{m}_{−}_{1} will relay the packets to its own up layer AHP (AHP_{m}_{−}_{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 → AHP_{3} → AHP_{2} → AHP_{1} → 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),

(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. T_{0} 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

(5)

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. H_{AN} 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,

(6)

where.

(2) When k = 2, There is two-hierarchy network. Due to the uniform distribution, we can get the maximum of d_{2}(i) according to R and r. So we can get,

(7)

where.

(3) When k = m, There is m-hierarchy network. When we extend the hierarchy to m, we can get,

(8)

where.

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

(9)

as a function about variable k. Then we can get the first derivation of expressed by,

(10)

When, we can get the extreme value k_{e} as the optimal k shown in Equation (11)

(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 AHP_{1}s, two AHP_{2}s until two AHP_{m}_{−}_{1}s in our system. mean distance of each neighboring AHP positions. x_{1} means the distances between AHP_{1} 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 AHP_{1}] H_{1} can be calculates by

(12)

(2) The total hop number of vehicles in [AHP_{1} AHP_{2}] H_{2} can be given by

. (13)

(3) Similarly, the total hop number of vehicles in [AHP_{m}_{−}_{2} AHP_{m}_{−}_{1}] H_{m}_{−}_{1} is

(14)

(4) The total hop number of vehicles in [AHP_{m}_{−1} BPC] H_{m }is calculated by

(15)

Then we can get the average up-link delay as the objective function

(16)

There are some restrictions

(17)

To simplify the restrictions, we have R_{j} = x_{j}. So there are

(18)

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), V_{1}, V_{2}, V_{3}, V_{4} in one hop range, so they share their own positions with each other. For instance, the V_{1} have a table such as Table 1 to save its neighbors’ positions. V_{2}, V_{3}, V_{4} in Figure 4(a) and V_{12}, V_{13}, V_{14} 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 P_{ij} means the jth position of AHP_{i }

(and), P_{0} 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 AHP_{i}. If one vehicle’s position is in one interval of, it becomes the candidate of AHP_{i}. Because of the position sharing of neighbors’ position, the one who is closest to the P_{ij} among these candidates becomes the jth AHP_{i} 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 AHP_{i}_{ }as shown in Algorithm 1. P_{Vx} means the position of vehicle x. P_{VNx} 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 AHP_{k}_{−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/N_{RSU} > 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 AHP_{i} has similar process.

Algorithm 1. The process of confirming AHP_{i} when the whole road is covered by the RSU.

Algorithm 2. Confirming i value of remotest AHP_{i} when the whole road is not covered by the RSU completely.

Algorithm 3. The process of confirming AHP_{i} when the whole road is not covered by the RSU completely.

6. Simulation

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 [9] 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) [10] 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 [11] . Other conventional parameters in NS-2 are set as Table 2.

Table 2. Parameter setting in simulations.

6.2. Analyses

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 [5] . We proposed method can suitable for multi-hop. So we compare the average end-to-end delay for different vehicle numbers in paper [5] 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 AHP_{k}_{−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 [5] and the two hierarchical link schemes for different vehicle numbers. In paper [5] , 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 [5] . 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

(a)(b)

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 [5] 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 [5] 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.

7. Conclusion

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.

Acknowledgements

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.

NOTES

^{*}Corresponding author.

Cite this paper

Yu, Y. , Li, D. , Zhang, G. and Zhang, X. (2016) A Hierarchical Link Scheme in Multi-Hop VANETs with Delay Analysis for Congestion Scenario.*Journal of Computer and Communications*, **4**, 10-22. doi: 10.4236/jcc.2016.48002.

Yu, Y. , Li, D. , Zhang, G. and Zhang, X. (2016) A Hierarchical Link Scheme in Multi-Hop VANETs with Delay Analysis for Congestion Scenario.

References

[1] Shahidi, R. and Ahmed, M.H. (2014) Probability Distribution of End-to-End Delay in a Highway VANET. IEEECommunications Letters, 18, C443-C446.

http://dx.doi.org/10.1109/LCOMM.2014.011214.132606

[2] 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.

http://dx.doi.org/10.1109/iccoins.2014.6868395

[3] 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.

http://dx.doi.org/10.1007/s11277-014-1622-5

[4] 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.

[5] 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.

http://dx.doi.org/10.1109/tmc.2015.2480062

[6] 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.

[7] Liu, Q.Z., Wu, Q.W. and Yong, L. (2013) A Hierarchical Security Architecture of VANET. International Conference on Cyberspace Technology (CCT 2013), Beijing, 6-10 November 2013, 6-10.

[8] 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.

http://dx.doi.org/10.1109/ICC.2015.7248893

[9] 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.

http://dx.doi.org/10.1109/wicom.2012.6478416

[10] 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.

[11] 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.

http://dx.doi.org/10.1016/j.jpdc.2013.10.004