GreeAODV: An Energy Efficient Routing Protocol for Vehicular Ad Hoc Networks

Depósito de Investigación de la Universidad de Sevilla https://idus.us.es/ This is an Accepted Manuscript of an article published by Springer Nature in Intelligent Computing Methodologies, on July 2018, available at: https://doi.org/10.1007/978-3-319-95957-3_69 © 2018 Springer International Publishing AG, part of Springer Nature. GreeAODV: An Energy Efficient Routing Protocol for Vehicular Ad Hoc Networks Thar Baker1, Jose M. García-Campos2, Daniel Gutiérrez Reina3, Sergio Toral2, Hissam Tawfik4, Dhiya Al-Jumeily1, and Abir Hussain1 1Department of Computer Science, Liverpool John Moores University, Liverpool, UK [email protected], [email protected], [email protected] 2Electronic Engineering Department, University of Seville, Seville, Spain [email protected], [email protected] 3Engineering Department, Loyola Andalucía University, Seville, Spain [email protected] 4School of Computing, Creative Technologies & Engineering, Leeds Beckett University, Leeds, UK [email protected] Abstract. VANETs allow communications among vehicles, and vehicles with the roadside infrastructure, namely Vehicle-to-Vehicle (V2V) and Vehicle-to- Infrastructure (V2I) respectively, in smart cities. Due to the number of vehicles, the infrastructure elements, the size of scenarios and mobility of nodes, the energy consumed to discover routes between source and destination nodes and to transmit applications packets can be high. In this paper, we propose a GreeDi based reactive routing protocol aimed at selecting the most efficient route in terms of energy consumption between two nodes in VANETs. The route selection is based on the power consumed by the intermediate nodes between the source and destination nodes. The proposed algorithm has been evaluated in city map-based VANET scenarios. The simulation results confirm that the proposed algorithm outperforms the original AODV in terms of power consumption. Furthermore, a computational Intelligence driven approach to address the challenge of energy efficient routing optimisation, is discussed. Keywords: VANETs, energy consumption, AODV, Routing Protocols, Computational Intelligence. 1 Introduction An ad hoc network is an autonomous system of wireless mobile nodes that cooperatively form a network without a specific administration. Each node in an ad hoc network is in charge of routing information between its neighbors. We refer to nodes that are free to move randomly and organize themselves arbitrarily as Mobile Ad Hoc NETworks (MANETs) [1]. As an evolution of traditional MANETs, VANETs (Vehicular Ad hoc NETworks) [2] include communications between moving vehicles on the roads and with the roadside infrastructure. The main objective of a VANET is to 2 provide safety and comfort to vehicle passengers. Each vehicle is integrated with wireless devices that can receive and relay messages such as traffic information, roadblock, parking, location tracking, fuel stations and weather information among others. Such massive exchange of information causes a high power consumption that leads to high fuel consumption, and consequently, CO2 emissions. Routing protocols for VANETs are not normally designed to take power consumption into consideration [3]. In general, they are intended for considering the high mobility of nodes and unpredictability of the wireless medium. However, saving energy is also an important matter in the design of green smart cities where VANETs are envisioned to play an important role. Therefore, it is important to propose new energy efficient routing protocols for VANETs. In this paper, we proposed GreeAODV a reactive routing protocol based on the GreeDi algorithm proposed in [4], and discussed in [5]-[7]. In this case, the rationale proposed in [4] is used to select energy efficient routing paths in VANETs. GreeDi [4] is based on the idea that each communication device has different power consumption when transmitting and receiving information. Using such rationale, the shortest path between two communication nodes would not always be the most efficient in terms of power consumption. In multi-hop networks like VANETs, the energy consumed by the communication routes should be calculated by using the energy information about all the participating nodes in the multi-hop communication path. Although GreeDi is designed for static networks such as the ones found in the communications between Internet nodes and data center presented in [4], we believe that its rationale for selecting routes of communications will be also valid for highly dynamic scenarios like VANETs. Consequently, in this paper we evaluate the GreeDi algorithm in dynamic networks such as VANETs. As such, the main contributions of this paper are: • The design of GreeAODV a novel reactive routing protocol for vehicle communications based on GreeDi [4] that selects the most efficient routes in terms of power consumption. • The evaluation of the proposed GreeAODV in realistic urban scenarios, and its comparison with Ad Hoc On-Demand Distance Vector (AODV) routing protocol. • A proposal of a computational Intelligence approach to the challenge under consideration This paper continues as follows; Section 2 reviews existing work on energy efficiency-based routing protocols intended for VANETs. Section 3 presents the proposed GreeAODV. Section 4 contains the simulation results obtained in realistic VANET urban scenarios. Finally, this paper ends with some conclusions in Section 5. 2 Related Work Energy consumption is an important designing parameter in wireless multi-hop network routing protocols in general and in VANET scenarios in particular. Several approaches have been proposed in the last few years [8]-[15]. Energy consumption in 3 multi-hop ad hoc networks gets its importance since communications are normally carried out by devices, which employ batteries and solar cells as energy sources [8][9]. An energy efficient routing algorithm is proposed in [10], which tries to find minimum energy paths. To select them, the authors propose using two different metrics such as network lifetime and energy consumed by packets. The combination of both metrics is the criteria to select the most energy efficient path. In [11], the authors propose ERBA, an energy efficient routing protocol for VANETs. It uses parameters such as driving patterns, vehicle category and intersection information to obtain the best routes in terms of energy. The idea behind ERBA is to select the most stable routes so as to reduce the energy consumption. Another approach based on routing stability is proposed in [12], where the authors propose Velocity Based Routing Protocol (VHRP). The authors state that route breakages impact significantly on the power consumption VHRP. Consequently, by selecting stable routes the global energy consumption of the network can be improved. VHRP considers that vehicles are grouped into different groups and also makes mobility predictions to anticipate route breakages. In [13], the authors proposed DE-OLSR. It is a modification of the well-known proactive routing protocol OLSR. DE-OLSR improves the performance of OLSR in terms of energy consumption. For that, the network interfaces are modeled in one of the four following states: receiving, transmitting, idle or sleeping. The total energy consumption by a packet transmission is the sum of the costs incurred by the sending node and all receivers. It does not take into consideration the idle and sleeping states. Unlike some of the previous works, which are focused on factors such as network lifetime, route stability, the way of driving, mobility predictions, and developing applications that control the traffic signals [14][15], we focus our attention on the routing layer. We modify the well-known reactive routing protocol AODV based on the GreeDi approach proposed in [4]. The objective is to find and use the most energy efficient routes to transmit applications packets. 3 The Proposed GreeAODV The proposed GreeAODV is based on one of the most used routing protocols for ad hoc networks like ADOV Error! Reference source not found., and the routing selection algorithm proposed in GreeDi [4]. In its original version, AODV is hop count based. It means that AODV seeks to find the shortest route in terms of number hops between two nodes in the network. AODV Error! Reference source not found. is a reactive protocol, so it only maintains routes if they are active. Otherwise, AODV will remove the routing information of obsoleted routes from its routing tables. AODV relies on flooding to discover routes between two nodes. Whenever AODV Error! Reference source not found. needs a new communication route between a source and a destination node, the source floods the network with request packets (RREQ. Such request packets are forwarded once by intermediate nodes, until one of the copies reaches the destination node. Each intermediate node updates the route request packet (RREQ) packets by including the last hop followed by the packet and increas- 4 ing the hop count. On receiving the request packet, the destination node replies the received request by sending back a route reply packet (RREP), which will follow the same communication path followed by the received RREQ. When the RREP reaches the source node, then, it updates its routing table and can start sending application packets to the destination using the established communication path. It is important to note that the destination node only replies once the RREQ packets. Only if the received RREQ contains a lower hop count, the destination will generate another RREP. In the proposed GreeAODV, we modify the policy of route formation of the original AODV as proposed in GreeDi [4]. We consider the total power consumed by nodes in the found communication route as the selecting metric. The main argument is that in many occasions the shortest route is not the most energy efficient one. The primary reason is that the power consumed by each node in the network can be very different. Consequently, there can be longer routes but more efficient in terms of power consumption. The total power consumed to discover a route between source and destination nodes 𝑃"($%&)((is( defined as: 𝑃"($%&) = 𝑃 ,- + ∑ (𝑃01 + 𝑃,1) 2 134 + 𝑃05 (1) Where Pts is the power consumed by the source node to transmit a packet, Prd is the power consumed by the destination node to receive a packet, and 𝑃01(and(𝑃,1 are the powers consumed by an intermediate node receiving and transmitting an incoming packet, respectively. It is important to highlight that we only consider the power consumed by the wireless transceivers included in the nodes and used for sending and receiving packets. We do not take into account the energy consumed by the nodes for processing the received information. We make such simplification since the energy consumed by the communication operations is in general higher than the energy consumed by the nodes for processing the received information. Notice that in (1) we do not distinguish among the type of packet transmitted or received since we consider that the power consumed is independent of the type of packet (routing or application packets). As mentioned, the proposed GreeAODV selects routes based on the total power consumed. In order to calculate the total power consumed by a route, the RREQ packets should include the cumulative power consumption from the source node until that point in the route. As in Fig. 1, the fields of the request packets are depicted. With respect to the original AODV RREQ packets, we add the power count. This field represents the energy consumed to receive and transmit the request packet and it is updated in every intermediate node. It is important to indicate that we have not modified the rest of the features of AODV Error! Reference source not found.. Therefore, when the RREQ packet reaches the destination node, the power count field will contain the total energy consumed from the source to the destination node. For every found route the destination node will receive a different RREQ packet that contains different power consumption. The destination node will only generate a new RREP if the power count in the received RREQ is lower than the one used in current active route between the source and the destination node. Therefore, we guarantee that the most efficient route between the source and the destination nodes is used. 5 In order to illustrate how the retransmission of packets is carried out in GreeAODV, we depict an example in Fig. 2. In Fig. 2, we represent the discovery procedure of a route between a source node (S) and a destination node (D). The power consumed by the found route can be calculated using (1) as: 𝑃"($%&) = 𝑃 ,- + ( 𝑃 09 + 𝑃 ,9 ) + ( 𝑃0: + 𝑃,: ) + 𝑃05 (( (2) ( In the example represented in Fig. 2, we show two intermediate nodes a and b that forward the RREQ packet generated by the source node S and targeted at the destination node D. In this example we only show a possible route between the source and destination nodes. However, in a real situation there can be multiple routes between the source and destination nodes. Therefore, each RREQ packet received by the destination node will contain a different power count value. Notice that the same calculation can be done for the RREP packets and also for the application packets delivered from S to D. Fig. 1. RREQ packet of GreeAODV Fig. 2. Example of RREQ retransmission in GreeAODV It is important to highlight that the proposed GreeAODV selects the most efficient route between the source and destination nodes at the moment in which the source needs a route to communicate with the destination. This route is used until a route breakage is detected. However, since VANETs are dynamic networks, another more efficient route between both nodes may appear due to the mobility of nodes. For example, if source and destination nodes get closer each other. In the current version of GreeAODV, there is not a mechanism to detect such possibility, but we will consider it as future work. 6 4 Simulation Results This section includes the simulation results obtained by the proposed GreeAODV routing protocol. First, we present the simulation environment used to conduct the simulations, followed by simulation results. 4.1 Simulation Environment Settings The main simulation parameters used are included in Table 1. We use the Network Simulator 2 (NS-2), which is one of the most popular event driven network simulators for multi-hop ad hoc networks. We implement the proposed GreeAODV using the code of the original AODV in NS-2. Regarding the mobility of vehicles, we use C4R application [19] in order to generate the mobility of vehicles in an urban VANET scenario. It is important to highlight some specific aspects of VANET simulations such as the MAC protocol used, which is the IEEE 802.15.4, which is widely used in wireless sensor networks. Regarding the propagation model, we use the two-ray ground reflection model 1 because it gives more accurate prediction for long distances than the free space model. Table 1. Simulation Parameters Parameter Value Network Simulator NS-2.34 Mobility Model IDM Size of scenario (m x m) 1000x1000 Average speed of nodes (Km/h) 30 Nº Nodes 100 MAC layer IEE 802.15.4 Routing layer AODV, GreeAODV Transport layer UDP Application layer CBR Nº Communication flows 5,10,15,20 and 25 Transmission rate (packet/s) 1 Size of application packets (bytes) 512 Transmission range (m) 250 Propagation model Two-ray ground Simulation time (s) 300 Fig. 3 shows the urban VANET scenario considered for the simulation study. It represents a part of the city of Seville in Spain. The type of traffic is Constant Bit Rate (CBR), which is typically used in multi-hop scenarios with UDP transport layer. CBR traffic is suitable for real time applications. The maximum speed of nodes is 30 km/h. This maximum value is approperaite for urban scenarios, where the limited speed is about 50 km/h. 1 Available at https://pdfs.semanticscholar.org/a86f/90f1238ccb90181c26335684fd762247408e.pdf 7 In addition, Fig. 3 also shows the movements of the vehicles in the considered scenario. Each color in Fig. 3 represents a different vehicle. To highlight the movement of the vehicles we depict the movements of some of them in terms of the begin (car picture) and the end (flag) of their trajectories. To evaluate the performance of GreeAODV, we consider the following performance metrics: Total Power Consumption (TPC) [mW]: It is the total power consumption consumed by the routing protocol during the simulation time. This metric considers both the routing (RREQ and RREP), and the application packets (CBR). The objective is that TPC value can be as low as possible. Fig. 3. VANET urban scenario and vehicles movements 𝑇𝑃𝐶 = ∑ 𝑅𝑅𝐸𝑄A+ ∑ 𝑅𝑅𝐸𝑃 A+ ∑ 𝐴𝑃𝑃 A (3) Where RREQP, RREPP, APPp represent the power consumed by the REEQ, RREP, and application packets to be sent and received by all the participating nodes from the source and destination nodes. The power consumed is calculated using (1) regardless of the type of packet. 8 Application Packet Power Consumption (APPC) [mW]: It is defined as the total power consumed by the application packets during the simulation time. The objective is to obtain a low value of APPC. 𝐴𝑃𝑃𝐶 = ∑ 𝐴𝑃𝑃 A (( ( (4) ( Power Ratio (PR) [mW/pckts]: This ratio measures the power required to transmit each application packet. We seek to achieve a low PR value with GreeAODV. 𝑃𝑅 = ∑ DAAE FAG (( ( (5) ( APP stands for the number of application packets successfully received by the destination nodes. Request Power Consumption (RQPC) [mW]: It counts the power consumed by the RREQ packets during the discovery phase of the routing protocol. We desire a low value of RQPC. 𝑅𝑄𝑃𝐶 = ∑ 𝑅𝑅𝐸𝑄A (( ( (6) ( Reply Power Consumption (RPPC) [mW]: It measures the power consumed by RREP. We seek a low value of RPPC. 𝑅𝑃𝑃𝐶 = ∑ 𝑅𝑅𝐸𝑃 A (( ( (7) ( Throughput [kbps]: This metric measures the performance of the routing protocol in terms data delivery. The throughput is calculated as the number of successfully received application packets divided by the simulation time. A good routing protocol should guarantee a high throughput. 𝑇ℎ𝑟𝑜𝑢𝑔ℎ𝑝𝑢𝑡 = ∑ DAA $1RST9,1UV(,1RW (( ( (8) ( The results shown in Figures 4–6 were obtained by averaging out the results of 50 different simulations. The source and destination nodes of the communication flows are selected randomly among all nodes in the network. The only restriction is that the source and destination nodes are not repeated in different communication flows. This condition has been demonstrated that is important to obtain reliable simulation results of routing protocols [17]. 4.2 GreeAODV Parameter Settings The following Table 2 includes the power parameters used by nodes during the simulation time. These parameters are taken from [18]. These values are based on real data information on wireless sensor network that use Xbee commercial modules. In the