A Greedy Traきc Light and Queue Aware Routing Protocol for Urban VANETs

Yangyang Xia, Xiaoqi Qin, Baoling Liu, Ping Zhang

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Abstract: Vehicular Ad-hoc Networks(VANETs) require reliable data dissemination for time-sensitive public safety applications.An efficcient routing protocol plays a vital role to achieve satisfactory network performance.It is well known that routing is a challenging problem in VANETs due to the fast-changing network typology caused by high mobility at both ends of transmission. Moreover, under urban environment, there are two non-negligible factors in routing protocol design,the non-uniform vehicle distribution caused by traffic lights, and the network congestion due to high traffic demand in rush hours. In this paper, we propose a greedy traffic light and queue aware routing protocol (GTLQR)which jointly considers the street connectivity,channel quality, relative distance, and queuing delay to alleviate the packet loss caused by vehicle clustering at the intersection and balance the trafficc load among vehicles. Through performance evaluation, we show that our proposed protocol outperforms both TLRC and GLSR-L in terms of packet delivery ratio and end-to-end delay.

Keywords: VANETs; 5G; trafficc light; queuing delay; vehicular communications

I. INTRODUCTION

Vehicular Ad-Hoc Network (VANET) is considered as an important application scenario of Ultra-Reliable and Low-Latency Communication (uRLLC) in 5G networks to enhance the efficiency, safety and sustainability of future intelligent transportation systems [1]. VANET is an infrastructure-less type of network formed by vehicles and roadside units. Efficient data dissemination is considered as one of the most signi ficant problems in VANETs,because the majority of VANET applications require the propagation of messages in a very short time to all other vehicles within a range of a few kilometers from the source. However,due to the fast-changing topology, it is critical to design a reliable routing protocol for efficient information dissemination among vehicles [2]. Compared with highway VANETs,there are more challenges in routing design for urban VANETs due to complex road conditions (crisscrossing road, speed limit, trafficc light, etc.) and traffic congestion during rush hours. What’s more, the vehicles are uneven distributed, which is caused by traffic lights and social spots [3]. Therefore, mobility management considering lane usage and congestion control are two important issues for intelligent routing solutions.

The routing algorithm of VANETs has been extensive researched in recent years [4]. The proposed routing protocols can be divided into two categories, topology-based routing protocols and position-based routing protocols. The former employs a proactive or reactive scheme to establish complete route from source to destination, while the latter only makes next-hop forwarding decisions. Due to the high mobility of vehicles and complex road conditions, position-based routing protocols are more suitable for urban VANETs. A classical position-based routing protocol is called greedy perimeter stateless routing (GPSR) [5]. In this protocol,each packet is marked with its destination location, and the next-hop selection among neighbouring vehicles is based on the relative distance to the destination. Although the position-based routing protocols is adaptive to high mobility, without careful consideration of city scenarios, they may lead the packets to topology holes in urban VANETs. Several works have been proposed to overcome this problem. To simulate the realistic world, various parameters are considered for reliable routing solutions including map information [6] [7],effect of traffic light on vehicle distribution[8], moving direction prediction [9] - [11],inter-vehicle link lifetime [12], speed prediction [13] [14], density of vehicles [15] [16],interference [17], heterogeneous transmission powers among vehicles [18], and data deliver frequency [19].

Fig. 1. System architecture.

In this paper, we propose a greedy traffic light and queue aware routing protocol(GTLQR) for urban VANETs. To achieve efficient data dissemination, we consider several parameters including vehicle speed,street connectivity, channel quality, relative distance among vehicles, and queueing delay.We present the system architecture in figure 1. As shown in figure 1, we assume that data transmission among vehicles employs V2V mode using IEEE 802.11p, while control messages are broadcasted by base station(BS). The BS could provide important road information including trafficc light information,vehicle position, and street connectivity. The street connectivity is used to select a suitable street in the case of intersections. We calculate the street connectivity by considering the clustering effect caused by traffic lights and uneven distribution of vehicles moving in different directions. After the street with highest connectivity is selected, the relay vehicle is selected locally based on the queuing delay,channel quality and relative distance. Our goal is to minimize the end-to-end delay of multihop routing among vehicles while ensuring the successful delivery of data packets.

The remainder of this paper is organized as follows. In section II, we introduce the related works. In section III, we provide the details of our proposed routing protocol. In section IV,we present the performance evaluation results.Section V concludes the paper.

II. RELATED WORKS

There have been existing works on position-based routing protocol design for VANET. In position-based routing protocol,the packets are forwarded hop-by-hop without a pre-determined complete route. A drawback of this method is that it may lead the packet to topology hole where no suitable relay nodes exist. To overcome this problem, various factors are considered in the protocol design. In[15], Tripp-Barba et al. considered four factors for next-hop selection, including distance to destination, vehicle density, trajectory and available bandwidth resource. In [19], Jia Li et al. introduced a performance indicator called Coefficient of Dependence (CoD), which is calculated based on neighbours’ number, data deliver frequency, driving direction and positions. Then the authors dynamically set the beacon interval by evaluating CoD. In [20],Dahmane et al. proposed a weighted trustaware routing protocol which considers the relative distance, link quality, communication link stability, successful reception probability and trust value to select relay.

The most related works are those which address the complicated street conditions for routing protocol design in urban scenarios. In[16], Mezher et al leveraged information of city map for next-hop selection, which considered that the buildings will block the signal.In [21], Jerbi et al. proposed a greedy traffic aware routing (GyTAR) protocol which considers the length of street and the number of vehicles to estimate the street connectivity. It assumes the vehicles on the street are uniformly distributed. However, in urban scenario,vehicles will gather at the intersection during the time of red light and thus it will lead to topology hole along the street. In [22], Chang et al. proposed a shortest-path based routing protocol which considers the effect of traffic light. Upon arriving at the intersection, STAR first checks whether the red light segment which is closer to the destination is connected.If it is connected, the packets will be delivered toward this segment. Otherwise, the packets are relayed toward the vehicles on the green light segment that is closer to the destination.However, the vehicle density changes rapidly,and the green light segment may not always be connected. In [8], Qing Ding et al. considered the effect of trafficc lights on vehicle distribution. However, it assumes that the numbers of vehicles moving towards different directions along the two-way street are the same, which may not be true in urban scenario during rush hours.

Other than the performance metrics mentioned in most existing work, queueing delay at each vehicle along the route is also critical for delay-sensitive message dissemination in VANET, especially under urban scenario with complicated street condition and high traffic demand during rush hours. Only if the information is not out-dated as it arrives the destination vehicle, it is counted as a successful delivery. Therefore, in this paper, we propose a trafficc light and queue aware routing protocol for urban VANETs which jointly considers channel quality, street connectivity, relative distance, and queueing delay.

III. PROTOCOL DESIGN

In this section, we provide the details of our proposed routing protocol. As for each vehicle, it collects information of its one-hop neighbours by exchanging HELLO packets periodically. We first present the design of packet structure, and propose a speed adaptive packet transmission scheme to reduce traffic load in network. Then we propose to exploit three performance metrics for relay selection,including street connectivity, channel quality,and queueing delay. Finally, we describe the routing algorithm in detail.

3.1 Hello packet

In this paper, we assume that each vehicle obtains the geolocation and queue state information of its neighboring vehicles by exchanging HELLO packets. Each vehicle maintains an information set about its neighbors and updates the set as a new HELLO packet arrives.The frame structure design is shown in table 1. The node ID is used to identify the neighbor vehicle. The node position, node direction, and node speed can be used to predict the position of this neighbor vehicle. The time stamp,queue length and packet number are used to calculate the queueing delay.

Traditionally, HELLO packet should be sent according to a fixed period. However, in urban environment, the speed of vehicles varies according to street conditions and trafficc light. In case of trafficc jam and red light, the vehicles cluster together with little movement. The frequent exchanging of packets does not provide much valuable information while causinghigher collision probability. For example, if the vehicle speed is 0m/sfor a certain period of time, there is no need to resend the HELLO packets. Therefore, we propose a speed adaptive transmission scheme of HELLO packets.The transmission period is computed as the following:

Table I. HELLO packet.

whereVrepresents the speed of vehicle,aandbare parameters determining the maximum and minimum periods, respectively. Note that the period of HELLO packet is updated only when the last Hello packet is sent completely.

In figure 2, we plot the resulting HELLO packet period relative to speed of vehicle. The velocity of vehicles changes from 0m/stoVmax m/s. With an decreasing of vehicle’s velocity,the period of HELLO packet increases. In this way, we can reduce the network load and the possibility of communication collision.

Fig. 2. Transmission period of HELLO packet relative to vehicle speed.

Fig. 3. An example of VANET communication.

3.2 Street connectivity

In urban scenario, the mobility pattern of vehicles is restricted by city planning. The vehicles can only move along designed streets and change its direction at intersections. Therefore,it is essential to consider map information for more reliable relay selection. In figure 3,we use a simple example to demonstrate the importance of map information. As shown in figure 3, the source vehiclesintends to send messages to destination vehicled. In traditional GPSR based protocols which simply selects relay depending on the distance, both vehicleaand vehiclebare not qualified to relay the message. However, the vehicleais suitable to relay the message actually when considering the map information. Therefore, before selecting a speci fic relay vehicle, we propose to first leverage the city map information to select the street with highest connectivity for more reliable packet relay. Then select a relay vehicle along the chosen street.

As for street connectivity calculation, it is critical to consider the effect of traffic light.Trafficc signal controls the trafficc pattern along different streets. As we all know, during red light, the vehicles tend to cluster together at intersections. Therefore, it is unfair to simply count the total amount of vehicles when calculating street density. Instead, it is critical to consider the clustering effect caused by trafficc light and use street connectivity as the performance metric. Therefore, we propose to estimate the street connectivity by jointly considering the number of vehicles and the signal timing at intersections.

Moreover, due to trafficc jam at rush hours,it is common that the trafficc is not symmetric along different directions for a two-way street.As shown in figure 4, the vehicles gathers at intersections along both directions in case of red light. However, since the number of vehicles moving along different directions are distinct, the street connectivity is different.Therefore, the street connectivity along different directions of a two-way street is independent, and should be treated differently.

Taking figure 4 as an example, we divide the street into two parts based on moving direction, and estimate the street connectivity as follows. As for either part, we first calculate the number of clustered vehicles at intersection.Tianddenote the total time and the remaining time of red light, respectively, wherei={1,2}. Then, we can represent the time that red light has continued as

Then the number of vehicles gathering at the intersection can be calculated as follows.

In this paper, we assume that the number of vehicles and the signal timing can be obtained by RSU deployed along the street or traffic light at each intersection based on historical information. The communication units with computing capability can perform the street connectivity calculation and broadcast the results periodically to vehicles or upon requests.

3.3 Channel prediction

Fig. 4. An example of vehicle distribution on two-way street under effect of (1)trafficc lights, (2) different directions.

Due to high mobility and complicated city environment, the small-scale fading in VANET changes rapidly with coherence time less than 1ms[23] [24]. It is impractical to obtain the real-time CSI of vehicles for relay selection.However, compared with the random human mobility pattern, the moving pattern of vehicles is relatively stable and easy to predict.Therefore, the large-scale fading of channels between vehicles can be predicted based on the geo-location information. To achieve reliable data dissemination, we define a SNR utility function which jointly considers the channel condition and the relative distance to the destination node for relay selection.

3.3.1 Distance prediction

We assume that each vehicle collects the motion information of its neighbor vehicles by listening to the HELLO packets described in Sec. 3.1. Then it can perform a simple relative distance estimation based on Euclidean distance formula. Letnpdenote the vehicle,which carries packets. The set of neighbors ofnpis denoted bySnp. Based on the position,direction, speed, and time stamp information extracted from the HELLO packet sent by vehiclej(j∈Snp), vehiclenpcan predict the position of vehiclejat timetas follows:

wheretsrepresents the time stamp of the HELLO packet;andrepresent the velocity components of vehiclejin thexdirection andydirection, respectively;is the position of vehiclejat timeTs. Then the distance between the vehicles are approximated by:

3.3.2 SNR computation

In this paper, we approximately calculate the SNR of the link (from vehiclenpto vehiclej)as follows:

whereBis the bandwidth, andN0is the Gaussian noise power spectral density.PrandPtrepresent the signal power of receiver and transmitter, respectively. What’s more,represents the path loss of large-scale fading,which is de fined as

whereGiandhiare the gain and the height of antenna respectively.

3.3.3 Utility Computation

To increase the probability of forwarding packages successfully, we set a threshold of SNR, which is denoted byrth.rthis the minimum SNR to decode the packets successfully at the receiver. Letnmindicate the destination vehicle or the temporary destination. To minimize the number of hop, we select the nearest vehicle tonmas relay from the candidate vehicles, which satisfy the conditionThus, the utility of selecting vehiclejas the relay can be computed by

3.4 Queuing delay

As for VANETs, store-and-forward mechanism is employed to compensate the coverage hole problem, where each vehicle stores and carries the message until it finds a suitable relay to forward the message. Therefore, the queue length at each vehicle is different. If a vehicle is chosen to carry trafficc for multiple flows, then the messages may be backlogged at the vehicle and results in large queuing delay. Therefore, it is critical to consider the queue state for relay selection to achieve low end-to-end delay and avoid packet loss caused by queue over flowing.

We propose to exchange and estimate the queue-length information among vehicles in a distributed manner. For vehicledenotes the total number of packets obtained between two HELLO packets, anddenotes the average length of queue during this period. Then vehiclejpacksin the HELLO packet, and broadcasts to its neighbours. At the same time, vehiclenprecords the total number of packets (denotedwhich are sent fromnptojduring this period. What’s more,rdenotes the packets processing rate. Each time whennpreceives a HELLO packet from vehiclej, it will recalculate the queueing delay of vehiclejas

Then we propose to define the neighbor priority index for relay selection, which jointly considers channel condition, distance to destination and queueing delay. The priority of vehiclejto be selected is de fined as

3.5 Routing algorithm

In this section, we present the details of the proposed routing algorithm. Table 2 presents the notation table of the related parameters.The specific process of the proposed routing algorithm is showed in table 3 in detail. Ifnswill greedily forward packets according to the position ofnd. Otherwisenpwill select a street and one intersection of this street as the temporary destination to forward packets. Ifnpis in streetstr, the intersection ofstrcloser tondwill be selected. Ifnpis at the intersectionninsec, it will create a candidate set of intersections. The candidate set consists of the adjacent intersections ofninsec, which are closer tondthanninsec. Then the best intersec-tion will be selected according to the street connectivity calculated by the Eqs.(2)-(5).Once the temporary destination is determined,npselects a neighbor as relay which has the maximum priority according to Eq.(12).

As shown in figure 5, the source node selects intersectionBas the temporary destination from its two adjacent intersectionsAandB. Then the source node greedily sends packets toB. When the packets are about to arrive atB, the node need to select a new temporary destination. The intersectionBhas three adjacent intersectionsA,CandE.CandEare closer to the destination thanB, whileAis farther. So it creates a candidate set consists ofCandEfirstly. ThenCwill be selected as the next intersection according to the street connectivity.

Although we select the street with the highest connectivity, it may happen that there is no suitable relay. When this situation arises,the vehicle will keep the packets until finding an appropriate node, which is called carry-and-forward strategy. Note that,dthis longer than the communication radius of vehicles.npmay not find a suitable relay, when it greedily forwards packets to vehiclend. When a suitable relay appears,may become longer thandth. Thennpshould select an intersection as temporary destination again.

IV. PERFORMANCE EVALUATION

In this section, we present the simulation results to protocol (GTLQR). For comparison,we also simulate two commonly cited routing protocols GPSR-L [12] and TLRC [8]. For fairness, we add the carry-and-forward function for both protocols. That is, each vehicle stores and carries and message until it finds a suitable relay vehicle.

4.1 Simulation setting

Fig. 5. An illustrative example of route selection strategy .

Table II. Notation Table

Table III. Simulation parameters.

Fig. 6. Simulation map.

We evaluate the performance of proposed protocol using NS-2 simulator. We use the Simulation of Urban Mobility (SUMO) engine[25] to generate an urban environment, which contains 16 intersections and 24 two-way streets, as shown in figure 6. Table 4 lists the simulation parameters. To demonstrate the robustness of our proposed routing protocol, we present the performance comparison of packet delivery ratio and end-to-end delay under various velocities, vehicle densities and trafficc loads. The details are described as follows.

4.2 Eあ ect of velocity

We compare the performance of the three routing protocols under different velocity. We consider a network with 150 vehicles and increase the max velocity of vehicles from 10m/sto 40m/s. The number of traffic flows is set as 1. Figure 7(a) and figure 7(b) show the trend of packet delivery ratio and end-to-end delay as the velocity increases from 10 to 40, respectively. As shown in the figures, the packet delivery ratio of all three protocols decreases as the velocity increases, while the end-toend delay increases as the velocity increases.This is because the network topology varies more rapidly as the increasing velocity, which makes it harder for relay selection. Therefore,the vehicle tends to store and carry the packets, which results in lower packet delivery ratio and larger end-to-end delay as increasing velocity. Compared to TLRC and GPSR-L,our protocol decreases the end-to-end delay by 75.60% and 54.68% on average, respectively.What’s more, our protocol increases the packet delivery ratio by 73.19% when compared to TLRC, and more than 4 times compared to GPSR-L.

4.3 Eあ ect of vehicle density

We compare the performance of the three routing protocols under different vehicle density.We set the max velocity of vehicles as 20 m/s and increase the number of vehicles from 50 to 350. The number of traffic flows is set as 1. Figure 8(a) and figure 8(b) show the trend of packet delivery ratio and end-to-end delay as the number of vehicles increases from 50 to 350, respectively. As shown in the figures,the packet delivery ratio of all three protocols increases as the number of vehicles increases,while the end-to-end delay decreases as the number of vehicles increases. This is because the number of candidate vehicles increases,and the network connectivity is higher. Compared to TLRC and GPSR-L, our protocol decreases the end-to-end delay by 91.31% and 20.42% on average, respectively. Our protocol increases the packet delivery ratio by 28.15%when compared to TLRC, and more than 2 times compared to GPSR-L.

4.4 Eあ ect of traき c load

Fig. 7. Effect of velocity on packet delivery ratio and end-to-end delay.

Fig. 8. Effect of vehicle density on packet delivery ratio and end-to-end delay.

Fig. 9. Effect of trafficc load on packet delivery ratio and end-to-end delay.

We compare the performance of the three routing protocols under different traffic load.We set the max velocity of vehicles as 20 m/s and increase the number of trafficc flows from 1 to 6. The number of vehicles is set as 150.Figure9(a) and figure9(b) show the trend of packet delivery ratio and end-to-end delay as the number of traffic flows increases from 1 to 6, respectively. As shown in the figures, the packet delivery ratio of all three protocols decreases as the number of trafficc flows increases, while the end-to-end delay increases as the number of trafficc flows increases. This is because both the probability of collision and the queuing delay increase as the number of traffic flows increases. Compared to TLRC and GPSR-L, our protocol decreases the end-toend delay by 80.24% and 90.24% on average,respectively. The packet delivery ratio of our protocol is more than 2 times compared to that of TLRC, and is more than 4 times compared to that of GPSR-L.

V. CONCLUSIONS

In this paper, we studied the important routing problem in urban VANET. We proposed a greedy GPSR-based routing protocol called GTLQR. To model the real-world conditions,we consider the uneven vehicle distribution caused by trafficc light, and the queuing delay due to congestion during morning-evening rush hours. Simulation results show that the performance of our proposed protocol is competitive when compared to other position-based routing algorithms in terms of packet delivery ratio and end-to-end delay under various scenarios.

ACKNOWLEDGEMENTS

This paper is supported by the Beijing University of Posts and Telecommunications project No. 500418759, and the State Key Laboratory of Networking and Switching Technology project No. 600118124.