PCAR: A Packet-delivery Conditions Aware Routing Algorithm for Vanet Networks

INTRODUCTION

As the applied range becomes increasingly wide and specific based on inter-vehicle and vehicle to roadside communication in transportation systems, Vehicular Ad Hoc Networks (VANETs) have emerged as a new and promising field of research from Mobile Ad Hoc Networks (MANETs) (Corson and Macker, 1999). In comparison with MANETs, the main characteristic of VANETs is that vehicles moving along the traffic road constitute the mobile nodes in the network (Zhou et al., 2009). Considering each node being a vehicle, some limitations of mobile nodes in traditional MANETs such as power efficiency are no longer primary importance (Dan-Yang et al., 2009; Manickam and Shanmugavel, 2007). What is more, VANETs can make use of GPS and digital map which is helpful in choosing optimal forwarding route. Apart from the advantages above, VANETs have some challenges, for example, VANETs have high and constrained mobility of nodes and more frequent changes of network topology; in addition, the signal reception in VANETs is susceptible to interferences of environment of road and streets with intersections.

As one of the most prominent technologies in Intelligent Transportation Systems (ITS), VANETs mostly are considered to be used in applications such as improving the safety, traffic flow and comfort of passengers inside vehicles. Besides, the user of VANETs can easily obtain some public transportation services, such as the schedule of subways, the entrance to highway, current opening hours of an agency and packing information in some places, through communicating with roadside equipments. All applications above are based on the reliable inter-vehicular communications and road-vehicular communications. Therefore, finding and maintaining a high quality communication route has been a hot research topic in this field for years.

Since VANET networks are characterized by rapid topology changes and frequent network disconnections, some existing topology-based routing algorithm, such as DSR (Johnson and Maltz, 1996; Lakshmi and Sankaranarayanan, 2006) and AODV (Perkins and Royer, 1999; Hussain et al., 2007) are not suitable for VANETs. Recent years, position-based routing algorithms have been proposed as a promising routing scheme for VANETs which commonly require the auxiliary information about the geographic position of the participating nodes and do not need the establishment or maintenance of routes.

GPSR (Karp and Kung, 2000) is an earlier proposed position-based routing algorithm. It is considered as the most promising routing schemes for VANET due to its better packet delivery ratio and low packet delay. However, there exist several issues in this routing algorithm: (1) In GPSR, a sender’s neighbor might have gone out of the sender’s communication range during a HELLO message broadcast period owing to the high mobility of both nodes. So packet loss will happen if the invalid neighbors are selected as the next hop by the sender. (2) GPSR does not deal with the issue that signal reception can be easily interfered by radio obstacles such as high buildings. (3) In the perimeter mode, packets may be forwarded farther away from the destination which is likely to increase the packet delay time on the one hand and may cause packet loss due to packet’s TTL (Time To Live) in the network being run out of on the other. GPSR-L (Rao et al., 2008) addresses the issue in (1) from introducing the concept of lifetime which is calculated between the node and each of its neighbors according to the velocity of the both nodes. A lifetime timer which is set to the lifetime value helps in determining the quality of link and duration of the neighbor’s existence. During the next hop selection process, the node selects the neighbor which is closest to the destination with good link quality and non-zero lifetime timer value in contrast to GPSR. In GPCR (Lochert et al., 2005), data packets should always be forwarded to a node on the junction (known as coordinator) rather than being forwarded across the junction which can solve the issue described in (2) effectively. However, for the issue in 3), GPSR-L does not refer to, while GPCR just forwards packet to the coordinator at which right-hand rule is used to select the next forwarding node when local optimum occurs which does not really cope with the issues caused by perimeter forwarding. GyTAR (Jerbi et al., 2007) is another position-based routing algorithm for VANET which tries to deal with the drawbacks of perimeter forwarding in GPSR by delivering packets to road intersections. It uses the metrics of vehicle density between two adjacent intersections and the distance to destination to compute the next hop intersection but it still remains in the hypothetical stage that high vehicle density can represent good quality of link because vehicle nodes may be uneven deployed between the two adjacent intersections.

GSR (Lochert et al., 2003) and A-STAR (Seet et al., 2004) are two routing schemes for VANET which use Dijkstra algorithm to calculate the optimal forwarding route. The former takes the shortest distance computed according to the digital map between the source and the destination as the optimal forwarding route, while the latter assigns weight to each street based on the number of bus lines by which it is served and then computes the optimal forwarding route using Dijkstra algorithm with the in-car digital map. In VANET, however, the shortest distance between the source and the destination cannot correctly indicate the optimal forwarding route owing to high nodes mobility and A-STAR always chooses the streets that have more bus lines as the forwarding route which can cause severe bandwidth congestion on the one hand.

GVGrid (Sun et al., 2006) and HarpiaGrid (Chen et al., 2008) are two grid-based routing algorithms which partition the geographic region into squares of equal-size called grids. GVGrid selects a grid sequence in which nodes are likely to move at similar speeds and toward similar directions as the network route with the best stability. In the route maintenance process, GVGrid does not reconstruct the previous grid sequence but recover route from waiting for nodes moving to the proper positions in the broken grid sequence. This increases the packet delay time severely. In contrast with GVGrid, in cases of low vehicle density, HarpiaGrid will trace back to the grid which is closest to the destination and is not on the same road with the fault grid, then remove all grids after the current grid and generate a new grid forwarding route.

Unlike other approaches, CAR (Naumo and Gross, 2007) integrates locating destinations with finding connected paths between source and destination instead of using the popular location service like RLS. Moreover, the guard node is introduced to inform neighbors when the destination moves out of a fixed range, with the purpose of tracking the latest destination location. However, according to the selection rule of anchor points, some needless nodes may be added into path, resulting in increment of the hops. ACAR (Lim et al., 2008) is an adaptively connectively aware routing protocol which selects the optimal route with the best transmission quality based on the metrics of the packet error rate and the connectivity probability represented by vehicles density and traffic light periods.

However, these current proposed position-based routing algorithms share one common characteristics, that is, the majority of them utilize indirect metrics (such as the distance or density of vehicles between source node and destination node) to produce optimal routing path but it is still not sure that these indirect metrics can represent the real road conditions, so most of present algorithms remain at the stage of hypothesis. Therefore, this study has presented a new packet-delivery conditions aware routing algorithm called PCAR for VANETs, with the purpose to use direct metrics to build a high quality route. PCAR takes packet delay time and packet delivery ratio as the metrics for selecting optimal forwarding route.

PCAR ROUTING ALGORITHM

Here, the proposed PCAR routing algorithm is described. Preliminaries and assumptions will be presented first, next hop selection algorithm as well as adaptive route selection and maintenance scheme will also be specified.

Fig. 1:	Scene of node deployment

Preliminaries and assumptions: In vehicular ad hoc networks, vehicles are referred to as mobile nodes for generality. In addition, we assume PCAR equips every road junction with a static node which can be integrated with traffic lights. We also assume that each node is equipped with a short range wireless device and has the same communication range R (Fig. 1).

Every static node stores its location, the junction radius and location of its neighbor static nodes, in which the location of static node is the centre position of the junction, the junction radius represents the distance between the static node and its neighbor roads. In Fig. 1, r represents the junction radius; A, B, C, D and S indicate static nodes in corresponding junctions and A, B, C, D are the neighbor static nodes of S. On the other hand, to be location aware, each mobile node is equipped with an in-car GPS navigator from which it can read its current location. Mobile node periodically broadcasts mobile HELLO (mHELLO) message including the current location and velocity of the node to its direct neighbor nodes, while static node periodically broadcasts static HELLO (sHELLO) message, the sHELLO message contains all the information stored in that node.

When a source node needs to send data packets, it uses proposed location services strategy (Li et al., 2000) to get the ID of the destination node and the locations of the two static nodes that designate the road segment the destination node is moving on. The source node sets the static node to which the destination node is moving as destination static node and the static node to which the source node is moving as source static node. All the road segments between destination static node and source static node are dependent forwarding routes. The static node sending packet in each road segment is called road sender static node, while the static node receiving packet is road receiver static node. All source static node, destination static node, road sender static node and road receiver static node belong to routing static node.

Fig. 2:	Format of routing packet

Fig. 3:	Scene of node movement

The packet format for the routing protocol is shown in Fig. 2. sID indicates the ID of the source node. dID indicates the ID of the destination node. lSend contains the location of the current road sender static node, while lRecv contains the location of the current road receiver static node. lSource contains the location of the source static node and lDest contains the location of the destination static node. The time field indicates when the packet was generated by the source node. sNo is the sequence number of the current packet. DATA contains the content to be sent.

Next hop selection algorithm: In our PCAR routing algorithm, the process that packets are forwarding within each road segment is an independent process. Between every two static nodes in the adjacent, PCAR selects one of the static nodes as the current destination node (that is, as described above, the road receiver static node). So in this section, we first introduce the calculation of mobile node moving to a new road segment before detail the next hop selection algorithm.

Mobile node can get the location of static nodes at both ends of the road segment which the mobile node is moving on through the HELLO message exchange with the passing static node. Figure 3 shows a mobile node is moving from BS road segment to SC road segment (B, S and C are the static nodes in the road junctions). We assume the coordinates of static nodes S, A, B, C and D is (X_s, Y_s), (X_a, Y_a), (X_b, Y_b), (X_c, Y_c) and (X_d, Y_d) respectively.

When the mobile node is moving to the road junction, it will receive the mHELLO message from the static node in that road junction and then extract the radius of the junction and the location of the static node and all its neighbor static nodes. We judge the mobile node has moved to a new road segment when it moves to position P (X_p, Y_p) where exceeding the radius of the junction. Through calculating the angles between vector SP and SA, SB, SC respectively, we select the road segment which makes the smallest angle with vector SP as the new road segment the mobile node has moved in.

From the definition of scalar product, we get Eq. 2 from Eq. 1 where a and b are two vectors. Based on Eq. 2, we can calculate the angles between vector SP and SA, SB, SC using Eq. 3.

(1)

(2)

(3)

For this example, we compute that the road segment SC designates is the new road segment to which the mobile node has moved. So according to the above approach, when a mobile node moves to a new road segment, the two static nodes at both ends of that road segment can be calculated.

After knowing the road segment on which mobile node is moving, the mobile node can deliver routing packets to road receiver static node at that road segment using greedy forwarding strategy where the road receiver static node computes the next forwarding road segments based on the location of destination static node. In the following sections, we present the forwarding strategy of mobile node and static node respectively.

Every node can get the information of its neighbor nodes from periodical HELLO message exchange. So if the mobile node needs to deliver packets, it checks its neighbor table. If there is road receiver static node that packets indicate in the neighbor table of the sender, the mobile node sends packets to the road receiver static node directly, or it recalculates the location of its neighbor nodes, chooses the node that is nearest to road receiver static node and is still in the range of the sender as the next hop. Finally, if all neighbor nodes of the sender are further away from the road receiver static node than the sender, the sender stores the packet temporally.

To get the next hop, we refer to checking neighbor table and recalculating the location of the neighbor nodes in above section.

Fig. 4:	M0 and M1 approaching each other in opposite direction

The following describes the process of its implementation.

We know, every node periodically broadcasts HELLO message, so the location information of a neighbor node can not be changed in the interval of one broadcast cycle. Due to high mobility, however, the mobile node might have gone out of range in this broadcast cycle. Consider the node movement situation shown in Fig. 4, the broadcast cycle of node M₁ and M₀ is assumed to be t_m and node communication range is R. On reception of the HELLO message from M₁, the position of node M₀ is located at point P₀, while M₁ at the point of P₁. Over the next t (t<t_m) time, the following scenario may occur. M₀ moves to point P₀', while M₁ moves to point P₁. Thus, at moment t, M₁ might have gone out of range of M₀, that is, |P₀ P₁|< R <|P₀' P₁' |, M₀ selects M₁ as a next hop resulting in packet loss.

Now we give the process of calculating the distance between P₀' and P₁'.

At moment t, M₀ knows the velocity of M₁ at point P₁, represented by vector , where the coordinator of P and P₁ is (XP, YP) and (XP₁, YP₁) respectively. According to definite proportionate inserted point theorem, the coordinator of point P₁' (XP₁’, YP₁’) is obtained as:

(4)

(5)

Then we compute λ value. As we know, λ is the ratio that point P1 partitions directed line segment . So λ can be computed as:

(6)

The distance between point P and P₁ can be got easily because M₀ stores the velocity of M₁ when exchanging HELLO message. So M₀ can predict the distance between point P₁ and P₁' as:

(7)

Fig. 5:	Packet generated by S0 forwarding along the road segments to D0

Till now, the coordinator of point P₁' (XP₁', YP₁') has been calculated. In addition, M₀ can get its own coordinator at point P₀' (XP₀', YP₀') using in-car GPS navigator, then the distance between P₀' and P₁' is computed as:

(8)

Knowing the latest neighbor location information, mobile node can efficiently deliver the packets to road receiver static node as we discuss above. The next hop selection policy of static node is given below. a) In the neighbor table of static node, if there are static nodes that are closer to destination static node than the sender, the sender chooses the one that is closest to destination as the next hop, if no node is selected in this policy, then we follow the policy b); b) The sender chooses the road segments that are closer to the destination as the next road segments other than the receiver road segment, if no road segment is selected, the receiver static node sends the packets back to the sender static node along to the receiver road segment.

Figure 5 illustrates how our algorithm selects next hop road segment. We assume each static node stores the location of its adjacent static nodes. In Fig. 5, the coordinator of static R is (X_R, Y_R), is the source node, is the destination node, S indicates the source static node, D indicates the destination static node, S(X_S, Y_S), R1(X_R1, Y_R1), R2(X_R2, Y_R2) and R3(X_R3, Y_R3) are the adjacent static nodes of R. We compute the angles between vector and ,, respectively and then choose the angles of less than 90 degrees as the next hop road segments. For this example, the road segments RR₂, RR₃ is selected. R then replaces the lRecv field of the packets by R₂, R₃ respectively.

Adaptive route selection and maintenance: In our PCAR algorithm, the packets in each road segment should be delivered to the road receiver static node. Thus, optimal route selection is mainly influenced by static node. As we proved above, static node may choose more than one next hop road segments in its next hop selection algorithm. For example, in Fig. 5, road segments RR₂, RR₃ is selected at one time as the next hop road segments. So the road sender static node can send packets along different road segments simultaneously and the same packet can also be received by the road receiver static node from different road segments. This process is called redundant forwarding process.

Redundant forwarding process execution for a certain time (e.g., when ten redundant packets were received.), it will automatically enter the routing convergence process which is the optimal route selection process. In routing convergence process, the road segment provided with the best packets delivery ratio and packet delay time is selected as the optimal packet receiver road segment by road receiver static node. Meanwhile, the road receiver static node sends STOP message (contains the location of the road sender static node, the type of this message and flag of the road receiver static node) to the road sender static nodes on those road receiver segments which are not be chosen. On reception of the STOP message, the road sender static node stops forwarding packets along this road segment. Utilizing this strategy, the PCAR algorithm can choose one optimal packet forwarding route between the source static node and the destination static node based on the metrics of packet delivery ratio and packet delay time.

However, duo to the high mobility of nodes, rapidly changing topology and frequent network disconnections, the chosen optimal forwarding route might be degenerating to non-optimal route, causing the packet deliver ratio slower or/and the packet delay time longer than the statistical value which will be discussed below. At this moment, the maintenance process is activated. The basic idea is that when a road segment degenerates to non-optimal route, the receiver static node on this road sends RESTART message (contains the location of the road sender static node, the type of this message and flag of the road receiver static node) to the road sender static nodes on those road segments which were stopped in routing convergence process. Then the local region around the degenerating road segment reverts to the redundant forwarding process.

In order to achieve adaptive route selection and maintenance, we let each routing static node maintain a road forwarding table.

Table 1:	Road forwarding table of R2 in Fig. 5

The first row of the table stores the adjacent static nodes indicating the corresponding road segments; the second row is the forwarding state for each adjacent road segment which can take the following values: 1(Input, indicating road receiver segment), -2, -3, -4…(indicating the order of stop receiving packets from that road segment, bigger the value is, earlier the road segment is stopped), 0 (Output, representing the next hop road segment), 2, 3, 4…(representing the order of forwarding packets to that road segment, bigger the value is, later the static node stops forwarding packets to this road segment), -1(default value, indication the road segment has not been used); No.3 row to No.3+N-1 row are used to record the corresponding packet delay time on different road receiver segments from which the packets are received, these rows are initialized to 0. Theoretically, the value of N should not be too big or too small. If the value is too big, it will not only cause larger storage space but also lead to slower for the optimal forwarding route selection. On the other hand, the smaller N may result in frequent routing convergence and instability in network transmission. Table 1 shows the road forwarding table of static node R₂ in Fig. 5. t_R(1)…t_R(N), t_R4(1)…t_R4(N) indicate the delay time of the last N packets from RR₂, R₄R₂ road segments respectively. R₅R₂, R₆R₂ road segments are the next hop road segments of static node R₂.

(9)

(10)

On receiving of the first N packets generated by the same source node and directed to the same destination node, the road forwarding table automatically starts calculating the average packet delay time(, expressed as Eq. 9) and the variance of the packet delay time(S, expressed as Eq. 10) on road receiver segments respectively. According to Eq. 9 and 10, we choose the receiver road segment which provide with the smallest average packet delay time and the smallest variance as the best road receiver segment. Then we also need to record the smallest average packet delay time and the smallest variance and send STOP message to the receiver segment which is not selected. Finally the road forwarding table must be updated, e.g., the forwarding state for certain road receiver segment is reset to -2.

On the other hand, if the average packet delay time of the next N packets is greater than the last average packet delay time plus the variance which we recorded last time, PCAR automatically activates its route maintenance process.

In the end, our PCAR algorithm also takes into account the mobility of the source node and the destination node. As we described above, every routing packet contains the location of the source static node and the location of the destination static node. When a packet arrives at the destination static node and is still not received by the destination node, then we consider that the destination node has moved to another road segment. Similarly, the source node may move to new road segment too when delivering packets.

In order to record the motion tracks of the source node and the destination node, we let each static node maintain a tracking queue at length of M which is used to record the passing source node or destination node. When the source node or destination node passes the static node, it will send a RECORD (contains the flag of the sender and message type) message to the static node for being recorded. If all data has been send over between the source node and the destination node, the source node and the destination node revert to general node and do not send RECORD message.

According the strategy presented above, if the packet generated by the source node can not be directed to the destination node when it reaches the destination static node, the destination static node checks its tracking queue and finds the road segment which the destination node enters, then sends the packet to the new road segment until reaching the destination node.

If the destination node has move to another road segment when it receives the packet generated by the source node, it will send its new location information to the source node using redundant forwarding strategy. On reception of the new location information of the destination node, the source static node also checks its tracking queue and forwards the message along the new road segment which the source node passing by. Using the new location information of the destination node, the source node resets the lDest field of the packets.

EXPERIMENT RESULTS

Here, the performance of PCAR is evaluated and compared with GPSR and GPSR-L. Because GPSR and GPSR-L may fail due to frequent network disconnections in VANET, we add the carry-and-forward mechanism in both.

Fig. 6:	Simulation map (near Hangzhou West Lake)

Simulation setup: Our experiment is based on a 4000x4100 m rectangle street area which is normalized from a snapshot of a section of Hangzhou City from Google Earth[http://www.google.com/earth/index.html] as shown in Fig. 6. The map has 25 intersections and 40 road segments. Since modeling of complex vehicle movement is important for accurately evaluating routing algorithm, we generate the movement of nodes using MOVE (Karnadi et al., 2007).

The 250 nodes are generated in our simulation, including 225 mobile nodes with a maximum speed of 40 m sec^-1 and 25 static nodes located at intersections in our map. Each node transmits according to IEEE 802.11 wireless LAN standard and transmission range was set to 500 m. The simulation time is 1000 seconds.

The experiment is carried out in NS-2.33 [http://www.isi.edu/nsnam/ns/] simulator. The packet loss ratio, average packet delay time and packet delivery rate are used as metrics for the analysis of results.

SIMULATION RESULTS AND ANALYSIS

Packet loss ratio: As shown in Fig. 7, PCAR achieves the lowest packet loss ratio compared with the others. There are two main reasons that PCAR outperforms GPSR and GPSR-L. First, the adaptive redundant forwarding strategy of PCAR guarantees the maximum packet forwarding, i.e., a packet can be forwarded along different road segments at the same time. What is more, once the optimal route is selected, it must be the truly best route between the source and destination due to that we directly use packet deliver ratio and packet delay time as the metrics for choosing optimal route.

Fig. 7:	Packet loss ratio comparison

Fig. 8:	Packet delay comparison

Second, the static nodes located at both ends of road segments provide a better packet delivery ratio when packet forwarding along the road segments because PCAR only needs send packet to road receiver static node, that is, the road receiver static node is the destination of the current packet which addresses the local optimum problem in greedy forwarding strategy (i.e., the only path requires that packet be forwarded farther away from the destination).

Average packet delay time: Average packet delay time comparison is shown in Fig. 8 which shows that PCAR produced a shorter delay than GPSR and GPSR-L. This is due to that, PCAR does not choose the geographic shortest route as the optimal forwarding route but directly use the metric of average packet delay time to select the optimal forwarding route. On the other hand, PCAR sends packet along all the next hop road segments computed by the road sender static node to the destination from the very beginning. For GPSR and GPSR-L, since the geographic shortest path between source node and destination node might be broken owing to the high mobility of nodes and uneven deployment of nodes in VANET, the packet delay time is increased.

Packet delivery rate: In present simulation, Packet delivery rate is defined as the number of packets which are successfully received by the destination node. Figure 9 shows the comparison of packet delivery rate represented by number of packets that are successfully delivered to destination.

Fig. 9:	Packet delivery rate comparison

As we can see, PCAR achieves higher packet delivery rate than GPSR and GPSR-L, especially when in higher density. This is because GPSR and GPSR-L will route packets away from the destination when runs into the problem of local optimum in greedy forwarding mode. Therefore, the packet may be dropped due to that the lifetime of the packet in network can easily run out under the above circumstance. However, in our PCAR algorithm, since introducing the static nodes at both ends of each road segment and always sending packet to neighbor static node, it thoroughly solves the problem of local optimum appeared in GPSR and GPSR-L.

CONCLUSION AND FUTURE WORK

In this study, we have presented a packet-delivery conditions aware routing algorithm for VANET. Our goal is to maintain a truly optimal route which provides better quality of communication and data transmission. For this purpose, we use packet delivery ratio and average packet delay time as the metrics for calculating optimal route which is in contrast to most current VANET routing algorithms using indirect metrics, such as the distance or density of vehicles between source node and destination node, to evaluate optimal route. In addition, by take advantage of the static node located at intersections, we solve the drawback of local optimum appeared in GPSR and GPSR-L when forwarding packets. Also, the adaptive route selection and maintenance strategy including redundant forwarding process and routing convergence process is designed which makes data transmission more efficient. Finally, we deal with the problem about the mobility of source node and destination node, providing superior fault-tolerance capability. The experimental results have shown that PCAR could offer truly optimal route with greater packet delivery and lower packet delay compared to GPSR and GPSR-L.

As future enhancements, we are trying to combine the route selection and the discovery process of destination nodes. We also need to purse more accuracy in simulation; simulations with different vehicle density shall be carried out. Moreover, verifying the most appropriate size of road forwarding table referred to in section 3.3 is another part of our ongoing work.