Portal de Periódicos da CAPES

Timer‐based greedy forwarding algorithm in vehicular ad hoc networks

2013; Institution of Engineering and Technology; Volume: 8; Issue: 4 Linguagem: Inglês

10.1049/iet-its.2013.0014

1751-9578

Chung‐Ming Huang, Shih‐Yang Lin,

Opportunistic and Delay-Tolerant Networks

IET Intelligent Transport SystemsVolume 8, Issue 4 p. 333-344 ArticleFree Access Timer-based greedy forwarding algorithm in vehicular ad hoc networks Chung-Ming Huang, Corresponding Author Chung-Ming Huang [email protected] Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan City, TaiwanSearch for more papers by this authorShih-Yang Lin, Shih-Yang Lin Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan City, TaiwanSearch for more papers by this author Chung-Ming Huang, Corresponding Author Chung-Ming Huang [email protected] Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan City, TaiwanSearch for more papers by this authorShih-Yang Lin, Shih-Yang Lin Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan City, TaiwanSearch for more papers by this author First published: 01 June 2014 https://doi.org/10.1049/iet-its.2013.0014Citations: 7AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Abstract Vehicular ad hoc networks bring new applications and services for wireless networks, such as information sharing among vehicles. These applications need data dissemination strategies or routing protocols to transmit data among vehicles efficiently. In order to reduce the transmission delay between the source vehicle and the destination vehicle, an efficient forwarding algorithm called timer-based greedy forwarding (TGF) is proposed in this study. TGF can find forwarding paths with fewer hop counts, lower transmission delay and fewer control packets. The proposed TGF chooses the farthest vehicle from a sender to be a packet forwarder, which is decided by receivers themselves. Although the concept of the TGF is similar to the greedy forwarding algorithm, the message exchanging for neighbouring information maintenance in the proposed TGF is unnecessary. To achieve this goal, three challenges that need to be tackled in the TGF are (i) the farthest node selection, (ii) timer error at an intersection and (iii) processing of redundant forwarded packets. Comparing with other methods, the simulation results show that the proposed TGF reduces the number of control packets, transmission delay and hop counts between a source vehicle and a destination vehicle significantly. 1 Introduction Emerging technique of telematics bring new applications for vehicular ad hoc networks (VANETs). In the past years, many kinds of VANET applications were developed, such as video data sharing [1], safety information sharing [2], event notification system [3] etc. Some of them need efficient data dissemination strategies or routing protocols. In the VANET environment, a routing protocol provides an algorithm, strategy or scheme for route discovery to find a suitable path from a source vehicle to a destination vehicle, for example, robust mobility adaptive clustering (RMAC) [4]. Depending on different requirements or purposes, various types of VANET routing protocols, such as proactive, reactive and hybrid approaches, were studied and researched. In proactive routing protocols, for example, destination-sequenced distance-vector [5], clusterhead gateway switch routing (CGSR) [6] and wireless routing protocol (WRP) [7], each vehicle maintains neighbouring vehicles' information for quick route discovery. In order to achieve the purpose of quick route discovery, periodical message exchanging between vehicles is required, which may lead to transmitting some extra packets. On the other hand, reactive routing protocols, such as ad hoc on-demand distance vector (AODV) [8], ad hoc on-demand multipath distance vector (AOMDV) [9] and dynamic source routing (DSR) [10], trigger the route discovery procedure only when it is needed. Using the reactive routing protocol, some unnecessary control packet exchanging between vehicles can be saved. In recent years, another routing strategy that uses the geographic information to assist the procedure of route discovery was proposed. One of them is the greedy forwarding strategy [11], which uses geographical information to select the farthest vehicle to be a packet forwarder. An illustration of the farthest vehicle selection strategy is depicted in Fig. 1a. When a sender vehicle broadcasts a packet, all vehicles that are located in the communication coverage can receive the packet. In order to save the transmission hop count to the destination vehicle, the sender chooses the farthest vehicle that is closest to the transmission boundary to be a packet forwarder. Although the greedy forwarding is a good idea for routing, some extra cost of message exchanging, which is used to obtain neighbouring vehicles' location information, may result in decreasing throughput. Fig. 1Open in figure viewerPowerPoint Illustration of the farthest vehicle selection strategy a Concept of the greedy forwarding strategy b Problem of redundant forwarded packets c Problem of timer error at an intersection Based on the greedy forwarding strategy, an efficient message dissemination technique called timer-based greedy forwarding (TGF) is proposed in this paper. The goal of TGF is to find dissemination paths between the source vehicle and the destination vehicle with fewer hop counts, lower transmission delay and fewer control packets. The key idea of the TGF is to choose the farthest vehicle to be a packet forwarder without any extra message exchanging. Referring to Fig. 1a, receivers 1, 2 and 3 can receive the packet that is broadcasted from the sender. Receiver 3 is the best choice because the distance between receiver 3 and sender is larger than others'. Let packet W, which was sent by the sender, be received by receivers 1, 2 and 3. Owing to (i) the characteristic of broadcasting in the wireless networks environment and (ii) receiver 1 and receiver 2 are in receiver 3's communication coverage, receiver 1 and receiver 2 can receive packet W that is forwarded by receiver 3 and know that receiver 3 is farther than themselves if receiver 3 forwards packet W earlier than receivers 1 and 2. In order to achieve the aforementioned purpose, three challenges should be overcome. First, how does the receiver know whether it itself is the farthest vehicle from the sender or not, and how does the receiver detect whether there are other further vehicles which will forward the packet or not? In the TGF, each receiver will wait for a specific time period, which depends on the distance between the sender and the receivers themself, before forwarding the received packet. When the timer expires, the farthest vehicle will first forward the packet. If the same packet is received again by a vehicle, which means that a further receiver vehicle does exist and has forwarded the packet during the waiting period, then forwarding the packet is no more needed. Second, some redundant packets that are forwarded on the closer roads are unnecessary. Fig. 1b gives an example. In Fig. 1b, since the TGF is designed to forward packets on each road for data dissemination, a packet will be forwarded on road 1 and road 2 by vehicle V1 and vehicle V2, respectively. The reason is that vehicle V1 and vehicle V2 are the farthest vehicles in their coursings. Hence, both vehicles forward the same packet. In this situation, only vehicle 1 needs to forward packets, because its communication coverage is farther than that of vehicle V2 in vehicle V2's direction. The third challenge is that the same distance between a source vehicle and receiving vehicles results in timer error at an intersection. For example, in Fig. 1c, both vehicles V2 and V3 receive the same packet from sender V1. Since the distance between vehicles V2 and V1 are the same with the distance between vehicles V3 and V1, both vehicles V2 and V3 become forwarders to forward the same packet, which is unnecessary. In this situation, only vehicle V3 needs to forward the packet because it is the farthest vehicle in its direction. The TGF is proposed to tackle the aforementioned three challenges. In the TGF, assuming all vehicles are equipped with the GPS device and the wireless communication device such as dedicated short-range communication (DSRC). Hence, the position of a vehicle can be obtained and communication between vehicles is feasible. In addition, time synchronisation can be achieved through the use of a GPS signal. When a sender vehicle wants to transmit a packet to a destination vehicle, it broadcasts the packet to its neighbouring vehicles. Any vehicle that is located in the communication coverage will receive the packet. Each vehicle will wait for a specific time period at first. The time period is calculated by the receiver itself, which is based on the distance between the sender and the receiver. In our design, the waiting time period of the further vehicle is always less than that of nearby vehicles. After the time period is expired, the receiver becomes a forwarder and forwards the packet if there is not any other forwarder forwarding the packet. Hence, the farthest vehicle can forward the packet before other nearby vehicles. In addition, since nearby vehicles are in the communication coverage of the farthest vehicle, nearby vehicles will not forward the packet because they can receive the forwarded packet sent from the farthest vehicle. In order to avoid unlimitedly packet forwarding, the TGF limits packets forwarding in a specific area. Furthermore, TGF is designed to overcome the challenges of redundant packets forwarding and timer error at an intersection. As a result, packets are transmitted to the destination vehicle through fewer hop counts, control packets and less transmission delay using the TGF. The rest of this paper is organised as follows: Section 2 presents related work of the corresponding VANET's routing protocols. Section 3 introduces the proposed TGF in detail. Section 4 presents the performance analysis of the TGF. Finally, Sections 5 and 6 present discussion and conclusion remarks, respectively. 2 Related works Generally speaking, data dissemination in the VANET can be classified into two types: V2I/I2V dissemination and V2V dissemination [12]. In V2I/I2V dissemination, push-based and pull-based dissemination approaches are adopted. In the V2V dissemination, flooding and relaying approaches are considered. The flooding approach provides high packet delivery rate in the VANET. However, the problem of the broadcasting storm, which leads to the huge number of transmitted packets in the network [13], occurs using the flooding approach. In order to limit packets' unlimited flooding, a suitable relay node selection strategy is needed. Selecting suitable relay nodes to forward packets become an important issue in VANETs. Several kinds of relay node selection strategies were proposed in recent years. The map-based/geographic forwarding approach is one of them, in which it uses some geographic information to choose relay nodes. In the geographic routing protocol, three categories of the geographic routing are (i) trajectory, (ii) opportunistic and (iii) greedy [14]. In the trajectory-based forwarding strategy [15], the source vehicle establishes a trajectory using the on-board digital map. When a vehicle is towards the destination and is close to the trajectory, it is selected as a next forwarder. In the opportunistic forwarding strategy [16], the forwarding vehicle buffered and carried packets temporarily when a route path is failed. When a route path from the forwarding vehicle to the destination vehicle is available, the buffered packets are forwarded. In the greedy forwarding strategy, the farthest vehicle from the sender is selected to be a next forwarder. Various greedy routing strategies were proposed in recent years, such as greedy perimeter stateless routing (GPSR) [11], geographical source routing (GSR) [17], greedy perimeter geographic routing protocol (GPCR) [18], improved greedy traffic-aware routing (GyTAR) [19] and connectivity-aware routing [20] etc. GPSR [11] uses positions of receivers and location information of the destination to make packet forwarding decisions. GPSR employs the following greedy concept: a next forwarder that is closest to the destination is a best choice. If no forwarder can be selected in the routing path from the sender to the destination, a recovery strategy called perimeter forwarding is used. In order to achieve this goal, every node has to maintain neighbouring information through periodical message exchanging, which results in extra cost of transmission. Data dissemination can be applied to the real implementation. For example, a vehicle broadcasts a call-for-help message when an accident occurs. The message should be efficiently disseminated among neighbouring vehicles to avoid some potential problems, for example, broadcast storm that may be caused using the flooding strategy. Although some approaches, for example, GPSR, GSR, GPCR and GyTAR, can be applied for these scenarios, an efficient forwarding algorithm called TGF is proposed in this paper to find dissemination paths with fewer hop counts, lower transmission delay and fewer control packets, because the costs of the aforementioned approaches for keeping neighbouring vehicles' information are huge. Even if our previous research [21] proposed a Farthest-first (FF) forwarding algorithm, the aforementioned second and third challenges that are mentioned in Section 1 have not been resolved. In the next section, TGF will be introduced in detail. 3 TGF algorithm The proposed TGF uses a specific time period to decide whether the receiver itself can become a forwarder or not. Fig. 2a depicts the basic concept of the TGF. In Fig. 2a, let sender send a packet and all vehicles in the transmission range such as receivers 1 and 2 receive the packet. Using the TGF, receiver 2 becomes the forwarder because it is the farthest vehicle. When receiver 2 forwards the packet, receivers 1, i and i + 1 can receive the forwarded packet. Since receiver 1 receives a duplicated packet, it does not have any action. The same TGF is operated in receivers i and i + 1. Thus, receiver i + 1 becomes the next forwarder. Finally, the forwarded packet reaches the boundary of the pre-defined requested zone. Any vehicle that is close to the boundary does not forward the packet. Hence, the forwarded packet is limited in a specific area, that is, the requested zone. Fig. 2Open in figure viewerPowerPoint Basic concept of the TGF a Concept of TGF strategy b Illustration of using the TGF algorithm An example is illustrated in Fig. 2b. When a packet is sent from the sender, vehicles R1 and R2 receive the packet. Each of them calculates its waiting time period which depends on the distance between the sender and itself. In this scenario, since vehicle R2 is farther than R1 from the sender, the waiting time period of vehicle R2 is less than that of vehicle R1. Vehicle R2 becomes a forwarder because it does not receive any forwarded packet during its waiting time period. On the other hand, vehicle R1 does not forward the packet because a duplicated packet, that is, the one that is forwarded by vehicle R1, is received during its waiting time period. The same situation happens for (i) vehicles Ri and Ri+1 and (ii) vehicles Rj and Rj+1. The packet can be delivered using the TGF forwarding algorithm till it reaches the boundary of the pre-defined requested zone. Before describing the TGF, the packet format has to be introduced. Some necessary information has to be encapsulated in the packet. The required information contains sender's ID, timestamp, location, for example, GPS coordinates etc. The packet format includes identification of the original source vehicle (source's ID) and the timestamp which is the sending time of a packet. In the TGF, geographical information of the sender is included in the location field. In the real environment, the location field can be longitude, latitude and altitude. For some simulated environment, the location field can be the x-, y- and z- axes. The other fields contain some related information, that is, requested zone definition, time to live and others. Before the packet is forwarded to other nearby vehicles, the forwarder will add its related information to the appended field. The information contains forwarder's ID, location information such as longitude, latitude, velocity and coursing of the vehicle etc. The control flowchart of the TGF is depicted in Fig. 3a. When a vehicle receives the packet, it will check whether it is located out of the pre-defined requested zone or not. The requested zone can be pre-defined by users, who define it depending on their purposes. For example, the requested zone can be defined as three hops, or the distance between the original sender and the last receiver. The purpose of defining the requested zone is to limit packet forwarding in a specific area, which is used to avoid the problem of unlimited flooding. If the receiver is located out of the requested zone, the packet is dropped; otherwise, the number of times of the received packet will be checked. Fig. 3Open in figure viewerPowerPoint Control flowchart of the TGF a Control flowchart of the TGF algorithm b Configuration for calculating round waiting time If the receiver receives the packet for the first time and the included angle between the sender and the receiver is smaller than a threshold, for example, 5°, the Furthest vehicle first (FVF) forwarding strategy is triggered because the receiver and the sender is on the same direction. The FVF strategy chooses the farthest vehicle from the sender to be a forwarder when the coursings of sender and receiver are the same. If the receiver receives the packet for the first time and the included angle between the sender and the receiver is bigger than a threshold, for example, 5°, the waiting timer correction (WTC) strategy is triggered. The WTC strategy is used to correct the timer error at an intersection. On the other hand, if a receiver receives the same packet twice and the included angle between the sender and the receiver is bigger than a threshold, the redundant packets decreasing (RPD) strategy is triggered. RPD is used to avoid some unnecessary packets' forwarding at two close roads. 3.1 FVF forwarding strategy Using the FVF forwarding strategy, a vehicle uses the round waiting time (RWT) to decide whether it can become a forwarder or not. In our design, RWT is calculated based on the distance between the sender and the receiver. The configuration of calculating RTW is illustrated in Fig. 3b. Let the communication range (CR) be set, for example, 1000 m, for DSRC communication and all vehicles be equipped with a GPS device. Hence, the time synchronism and location of vehicles can be obtained. When a sender broadcasts a packet, the transmission time to the boundary of the sender can be obtained using (1). In (1), 2.97 × 108 is the velocity of light per second, 'PacketLength' is the packet size and 'TransmissionSpeed' is equal to the velocity of radio wave in the wireless environment. The value of CR/2.97 × 108 is multiplied by a value of α in order to obtain reasonable time for waiting (1) Referring to Fig. 3b, let vehicle X, which is located at the boundary, receive the packet and then forward the packet. The time consumption can be obtained using (2), where 'TimeToPass' is the time to deliver packets from the physical layer to the network layer and 'TimeToProcess' is the time to handle one packet (2) When receiver 1 receives the forwarded packet that was sent by vehicle X, the time consumption can be obtained using (3) (3) Hence, let receiver 1 wait for the summation time period of (1)–(3). Equation (4) is the summation of (1)–(3) (4) Let there be receiver 1 and receiver 2 in Fig. 3b. When sender X broadcasts a packet, receiver 1 and receiver 2 can receive the packet. In our design, the RWT of receiver 1 is smaller than that of receiver 2 using (4). In this case, receiver 1 becomes the forwarder because receiver 1 does not receive the forwarded packet which is sent by others during its waiting time period, again. The waiting time is calculated using (4). Besides, the state of receiver 2 is changed to silence because receiver 2 receives the forwarded packet sent from receiver 1 during receiver 2's waiting time period, which is longer than that of receiver 1. Using the FVF forwarding strategy, a vehicle can determine whether it itself can become a forwarder or not by waiting for a specific time period. 3.2 WTC strategy The WTC strategy is used to correct timer error at an intersection in the TGF. Referring to Fig. 4a, RWT of V2 should be the time that the packet travels from vehicle V1 to point P2, and then reaches vehicle V2, where point P2 is located in front of the vehicle V2 and intersected with the communication boundary of vehicle V1. A packet's travelling time from vehicle V1 to point P2 can be obtained using (1). The calculation of the packet's travelling time from point P2 to vehicle V2 is as follows. Fig. 4Open in figure viewerPowerPoint WTC strategy a Illustration of using the WTC strategy b Illustration of using the RPD strategy At first, we introduce some symbols' definitions that are used in Fig. 4a. The location information of vehicles V1 and V2 is denoted as (x 1, y 1) and (x 2, y 2), respectively; the vehicle headings V1 and V2 are denoted as c1 and c2, respectively. 'Azimuth1' is a bearing indication from vehicle V1 and then is vertical with the heading of vehicle V2, and two bearings intersect at point P1. 'Azimuth2' is a bearing from vehicle V1 and passes vehicle V2. Segments 1, 2, 3 and 4 are denoted as the distances between vehicles and points. Fig. 5 shows the pseudo code of the procedure to obtain the value of 'segment4', which is depicted in Fig. 4a. At first, 'azimuth1' and 'azimuth2' should be calculated. Next, let included angle θ be equal to 'azimuth1' minus 'azimuth2'. After the included angle θ is obtained, 'segment1' and 'segment2' can be derived using the trigonometric function. Next, 'segment3' also can be derived using the trigonometric function. Finally, 'segment4' is equal to 'segment3' minus 'segment1'. Fig. 5Open in figure viewerPowerPoint Pseudo code of the segment4 calculation When 'segment4' is derived, RWT with the corrected timing can be obtained using (5). Using (5), vehicle V2 depicted in Fig. 4a can obtain the right RWT, and the problem of timer error at an intersection is resolved (5) 3.3 RPD strategy In order to resolve the problem of redundant packets that are forwarded on closer roads, the RPD strategy is proposed. Fig. 4b depicts the concept of the RPD strategy. In Fig. 4b, vehicle V2 unnecessarily forwards the packet that comes from vehicle V0, because vehicle V1 is farther than vehicle V2. In this situation, vehicle V2 receives the same packet again before its RWT is expired. Since the headings of vehicle V1 and V2 are different and the same packet is received twice at vehicle V2, the RPD strategy is triggered at vehicle V2. Equation (9) is used to determine whether the receiver V2 has to forward the packet or not (6) (7) (8) Assuming the included angle between vehicle V1 to V2 and V2's coursing is denoted as θ. In Fig. 4b, the distance between vehicle V2 and point P1, that is, 'segment1', can be obtained using (6), where point P1 is located in front of the vehicle V2 and intersects the vertical line that passes vehicle V1. Next, 'segment2' and 'segment3' can be calculated by (7) and (8), respectively. Finally, in (9), if 'segment1' plus 'segment3' is smaller than the communication radius r, vehicle V2 has to forward the packet because the communication coverage of vehicle V2 is farther than that of vehicle V1 in the V2's direction. Otherwise, vehicle V2 drops the packet because vehicle V1 can transmit the packet farther than vehicle V2 (9) Using the TGF, the aforementioned three problems depicted in Section 1 are resolved. Furthermore, any neighbouring vehicle information exchanging is unnecessary using the FVF forwarding strategy. The problem of local minimum in the greedy forwarding strategy does not exist using the FVF forwarding strategy, because the farthest vehicle is always chosen. 4 Performance analysis This section describes the performance analysis. First, simulation environment is introduced. Then, simulation results are described in detail. 'The Simulation environment': the networking simulator NS-2 is used in this paper. We utilised the simulator to obtain the performance evaluation for different routing protocols. In order to conveniently observe the comparison between various routing protocols, an effective simulation environment is used. In our simulation, we created a lane environment using NS-2. The transmission range of each vehicle is set to 250 m. 'Simulation results': three scenarios for the simulation are used, and four routing protocols, including TGF, AODV, AOMDV and GPSR, are compared in each scenario. In the first scenario, there are many vehicles located on a lane, in which each vehicle keeps the same distance to the front vehicle in the simulation; each simulation creates a procedure of route discovery for finding a routing path from the source vehicle to the destination vehicle. The distance between the source vehicle and the destination vehicle is about 5000 m. In the first scenario, we compared the hop counts, transmission delay and the number of packets used for the route discovery procedure. Fig. 6a depicts the hop counts comparison using different routing protocols. Since the routing protocol of AOMDV is similar to AODV, the hop counts of AODV and AOMDV in the simulation are similar. When a routing procedure is started, many routing paths may exist in the simulation if the routing protocol uses AOMDV. Although the simulation environment only has one lane, the AOMDV may find multi-routing paths from a source vehicle to a destination vehicle. For this reason, the number of packets used for route discovery using the AOMDV routing protocol is higher than that of the AODV routing protocol. On the other hand, hop counts used in TGF and GPSR are similar in the most. Since the main idea of both TGF and GPSR routing strategies is similar, which chooses the furthest vehicle to be a forwarding vehicle, the hop counts of both routing protocols are similar in the most. The transmission delay is the time spent for packet delivery from the source vehicle to the destination vehicle. Fig. 6b depicts the comparison of the transmission delay. Although the idea of the TGF is waiting for a time period to decide the next forwarder, the time period is actually very small. After the waiting time period, the farthest vehicle forwards the packets earliest. Therefore the transmission delay of the TGF is less than that of any of the other routing protocols. Besides, in order to have a reasonable value of the waiting time in the TGF, the α value is used to magnify the waiting time to meet the speed of computing in (5). Since the transmission speed of radio waves is very fast, we need to magnify the waiting time in the TGF for considering the real system implementation. Otherwise, the TGF may be failed because the waiting time (RWT) of receivers is always expired before the packet is forwarded, which results in each received vehicle forwarding the packet. Assuming a central processing unit (CPU) with the 3.0 GHz processing speed on a node is used. It spends 5 clock counts to finish an addition, 5 clock counts to finish a subtraction, 24 clock counts to finish a multiplication, 25 clock counts to finish a division and 89 clock counts are needed to process (5), which contains 3 additions, 2 divisions and 1 multiplication [22]. Hence the time for processing (5) is about 3.0 GHz/89 = 3.3708 × 10−7 s per time. Assuming the CR of the radio coverage is 250 m, the time for radio waves travelling 250 m is about 250/2.97 × 10−8 s = 8.4175 × 10−7 s. Hence, the time for radio waves travelling 250 m is faster than the CPU with the 3.0 GHz processing speed for about 2.51 times faster than the CPU speed. For this reason, the α value in our simulation is set to 1, 2.5 and 5, respectively, and the simulated results are depicted in Fig. 6b. Fig. 6Open in figure viewerPowerPoint Comparison of a Hop counts b Transmission delay c Number of used packets Referring to Fig. 6b, the transmission delay is almost the same when the distance between the vehicles is set to 10, 25 and 50 m using the TGF with different values. It is because farther vehicles are almost located at the transmission boundary to forward packets. Therefore the transmission delay are almost the same even if the α values are different using the TGF. On the other hand, the transmission delay becomes larger when forwarded vehicles are not close to the transmission boundary, for example, the distance between the vehicles is set to 65, 85 and 90 to 100 m, using the TGF. Since the distance between the farthest vehicle and the transmission boundary is large, it results in the farthest vehicle having to wait for more time. Furthermore, a larger α value, for example, 5, increases the transmission delay largely in these conditions because RWT of each forwarded vehicle is magnified. From the obser