Natural computing for vehicular networks

DOCTORAL THESIS Natural Computing for Vehicular Networks Author: Jamal TOUTOUH Supervisor: Dr. Enrique ALBA PhD Thesis Dissertation in Computer Science Department of Lenguajes y Ciencias de la Computación Escuela Técnica Superior de Ingeniería Informática UNIVERSIDAD DE MÁLAGA December, 2015 AUTOR: Jamal Toutouh El Alamin http://orcid.org/0000-0003-1152-0346 EDITA: Publicaciones y Divulgación Científica. Universidad de Málaga Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercialSinObraDerivada 4.0 Internacional: http://creativecommons.org/licenses/by-nc-nd/4.0/legalcode Cualquier parte de esta obra se puede reproducir sin autorización pero con el reconocimiento y atribución de los autores. No se puede hacer uso comercial de la obra y no se puede alterar, transformar o hacer obras derivadas. Esta Tesis Doctoral está depositada en el Repositorio Institucional de la Universidad de Málaga (RIUMA): riuma.uma.es Carta de aval Departamento de Lenguajes y Ciencias de la Computación Escuela Técnica Superior de Ingeniería Informática Universidad de Málaga El Dr. Enrique Alba, Catedrático de Universidad perteneciente al Departamento de Lenguajes y Ciencias de la Computación de la Universidad de Málaga, certifica que D. Jamal Toutouh, Ingeniero en Informática por la Universidad de Málaga, ha realizado en el Departamento de Lenguajes y Ciencias de la Computación de la Universidad de Málaga, bajo su dirección, el trabajo de investigación correspondiente a su Tesis Doctoral titulada: Natural Computing for Vehicular Networks Revisado el presente trabajo, estimo que puede ser presentado al tribunal que ha de juzgarlo. Y para que conste a efectos de lo establecido en la legislación vigente, autorizo la presentación de la Tesis Doctoral en la Universidad de Málaga. En Málaga, 13 de noviembre de 2015 Firmado: Dr. Enrique Alba Torres iii Acknowledgements A PhD Thesis is a long and arduous process, which has only been possible thanks to the help, support, and contribution that I received from many people. I would like to thank my supervisor, Prof. Enrique Alba, for encouraging me to perform this work, for guiding me, and most importantly, for his patience. To the NEO Research Group members, not only to the current people in the team, but also to some of them who have already left and the visitors who have stayed with us just for short periods of time. I have learned uncountable new things during our discussions, meetings, and coffee breaks. I have found here more than colleagues, we are a great family (Briseida, Christian, Daniel, David, Francis, Gabriel, Guillermo, Hajer, Javier Apolloni, Javier Ferrer, Juanjo, Martín Bilbao, Martín Pedemonte, Pablo, Paco, Raúl, Sofiane, Yesnier, among many others). Additionally, I want to thank Sergio Nesmachnow and his endless energy for stimulating me. I cannot forget to make mention of Joni Jämsä, Dr. Fethi Filali, and Dr. Zeeshan Hameed Mir, among others, who supported me and facilitated my stays at Centria University of Applied Sciences in Finland and at QMIC in Qatar. Of course, I feel grateful to my family. Ahmed, my father, who one day, when he was still a young man, decided to leave his small hamlet in Morocco (Beni Sidel) to provide his family with a brighter future. Sakina, my mother, who is the strongest woman that I have ever met. She fought very hard to give us a great education, even when my father had passed away. The most important heritage that my parents have left us is the importance of the hard work and being honest. Mohamed and Said, my brothers, have always been there for me when I needed them. Finally, I want to highlight another person. I remember him taking care of me since I was a little child. He was always my best friend, my support, a model to follow, and he was with me in many adventures. He is my eldest brother, Abdeslam. Also, thanks to Laila, Petete, and Dikra for convincing/forcing me to leave Melilla to pursue a dream, when I was bombarded with doubts about my ability to study Computer Science at university. Also, thanks to my collages/friends of Engineering Without Borders (Ingeniería Sin Fronteras, Málaga), who I bored to death complaining about my hard work, for giving me advices even without understanding a word of what I was saying. Specially, I am grateful to Carmina, Marta, and Paco who supported me during some very complicated moments. To my friends (football and volleyball teammates), Anto, Marioli, Pablo Antón, Charlie, Cristobal, Guillermo, Sergio, etc., I’m grateful for the numerous good moments we shared during this time and I hope we can have many others in a near future. And last but of course not the least, I want to thank Rosa for staying on my side every day, and giving me her immeasurable support and unconditional encouragement. She shared with me all those bad moments of these intense years and she made me feel that they were not that bad. Furthermore, she was the right person to be with during the good times. Thank you very much Rosa. Financial support: Jamal Toutouh was partially supported by FPU AP2010-3108 Grant of the Spanish Ministry of Education. Also, this PhD thesis work has been partially funded by the Spanish MINECO and FEDER project TIN2014-57341-R (http://moveon.lcc.uma.es). v Contents Carta de aval iii Acknowledgements v 1 Introduction 1 1.1 Motivation ......................................... 1 1.2 Objectives and Phases .................................. 2 1.3 Thesis Contributions ................................... 3 1.4 Dissertation Outline ................................... 4 I Fundamentals 7 2 Vehicular Networks: Opportunities and Research Challenges 9 2.1 Introduction ........................................ 9 2.2 VANET Communication Technologies ......................... 10 2.2.1 Architecture .................................... 10 2.2.2 Communication Domains ............................ 11 2.2.3 Wireless Access Technologies for VANETs ................... 12 2.3 VANET Applications ................................... 13 2.3.1 VANET Safety Applications ........................... 14 2.3.2 VANET Traffic Efficiency Applications ..................... 15 2.3.3 VANET Comfort and Entertainment Applications .............. 16 2.3.4 Summary of the Main QoS Requirements ................... 17 2.4 Unique VANET Features ................................. 17 2.5 Research Projects and Consortia ............................. 18 2.6 Open Challenges ..................................... 19 3 Natural Computing and Optimization Challenges in VANETs 23 3.1 Introduction ........................................ 23 3.1.1 Overview of Optimization Problems ...................... 24 3.2 NC Applied in VANETs ................................. 26 3.2.1 Evolutionary Algorithms ............................ 26 3.2.2 Swarm Intelligence ................................ 29 3.2.3 Simulated Annealing ............................... 31 3.2.4 Parallel NC algorithms .............................. 32 3.3 Challenges Tackled in VANETs Using NC ....................... 32 3.3.1 Natural Computing for VANET Data Routing ................ 33 3.3.2 Natural Computing for VANET Beacon Broadcasting ............ 34 3.3.3 Natural Computing for Hardware Platform Deployment .......... 35 vii 3.4 Evaluation of the Results ................................. 36 3.4.1 Quality Indicators ................................ 36 3.4.2 Performance Indicators ............................. 38 3.4.3 Statistical Analysis of the Results ........................ 38 II Optimization and Experimentation in Vehicular Networks 41 4 Off-line Optimization of Vehicular Communications 43 4.1 Introduction ........................................ 43 4.1.1 Instances for the Evaluation of VANET Communications .......... 45 4.1.2 Metrics Used to Evaluate VANET Protocols .................. 46 4.1.3 Specific NC Operators for VANET Protocol Optimization .......... 47 4.2 Data Transfer Between Vehicles with Optimized QoS ................ 49 4.2.1 Vehicular Data Transfer Protocol ........................ 50 4.2.2 File Transfer Optimization Problem for VDTP ................ 50 4.2.3 Implementation Details ............................. 51 4.2.4 Experimental Results ............................... 52 4.2.5 Efficient VDTP Validation ............................ 55 4.2.6 General Discussion on File Transfer QoS Optimization ........... 56 4.3 Optimization of the QoS of Proactive Routing ..................... 57 4.3.1 OLSR Routing Protocol for VANETs ...................... 57 4.3.2 OLSR QoS optimization in VANETs ...................... 58 4.3.3 Implementation Details ............................. 58 4.3.4 Experimental Results ............................... 60 4.3.5 QoS Efficient OLSR Validation ......................... 62 4.3.6 General Discussion on Off-line Proactive Routing Optimization ...... 64 4.4 Power Aware Proactive Routing for VANETs ..................... 64 4.4.1 Energy-efficiency OLSR optimization in VANETs .............. 65 4.4.2 Implementation Details ............................. 65 4.4.3 Experimental Results ............................... 66 4.4.4 Power Aware OLSR Validation ......................... 68 4.4.5 General Discussion on Power-Aware Routing ................ 69 4.5 Efficient QoS for Reactive Data Routing for VANETs ................. 69 4.5.1 AODV Routing Protocol for VANETs ..................... 70 4.5.2 Multi-objective AODV Optimization in VANETs ............... 71 4.5.3 Implementation Details ............................. 71 4.5.4 Experimental Results ............................... 73 4.5.5 Improved AODV Validation .......................... 75 4.5.6 General Discussion on Efficient MO-QoS Optimization ........... 76 4.6 Conclusions ........................................ 77 5 On-line Broadcasting Optimization in Vehicular Networks 79 5.1 Introduction ........................................ 79 5.1.1 Problem Example ................................. 80 5.1.2 Beacon Frequency as a QoS Metric ....................... 81 5.1.3 Use Case of FBR Utilization in VANETs .................... 82 5.2 Fair Beacon Rate Optimization Problem ........................ 82 5.3 Greedy Dynamic Broadcasting ............................. 84 viii 5.4 Self FREEDY Methods .................................. 85 5.4.1 Self o-FREEDY .................................. 86 5.4.2 Self n-FREEDY .................................. 86 5.5 Swarm FREEDY Methods ................................ 87 5.5.1 Swarm o-FREEDY ................................ 88 5.5.2 Swarm n-FREEDY ................................ 89 5.6 Experimental Results ................................... 90 5.6.1 Highway VANET Scenarios ........................... 90 5.6.2 Self o-FREEDY Parameterization ........................ 91 5.6.3 Numerical Results and Discussion ....................... 92 5.7 Conclusions ........................................ 94 6 Natural Computing for Smart Roadside Unit Placement 95 6.1 Introduction ........................................ 95 6.2 The RSU Deployment Problem ............................. 96 6.3 Implementation Details .................................. 97 6.3.1 Problem Encoding ................................ 97 6.3.2 Objective Functions Computation ....................... 98 6.3.3 Evolutionary Operators ............................. 98 6.4 Experimental Results ...................................100 6.4.1 Problem Instances ................................100 6.4.2 Comparison Against Two Greedy Strategies .................102 6.4.3 Numerical results .................................102 6.5 Conclusions ........................................106 7 Real World VANET Experiments 107 7.1 Introduction ........................................107 7.2 Performance Analysis of Improved VDTP in Real World Tests ...........108 7.2.1 VDTP Testbed Definition ............................108 7.2.2 Numerical Results ................................109 7.2.3 General Discussion on VDTP Performance Analysis .............112 7.3 Lightweight Personal Devices for VANETs ......................112 7.3.1 VANET Ubiquitous Devices ...........................112 7.3.2 VANET Testbed Definition to Evaluate Personal Devices ..........114 7.3.3 VANET Nodes Transmission Power Analysis .................117 7.3.4 VANET Communication Feasibility Experimental Results .........119 7.3.5 General Discussion on V2V by Using Lightweight Devices .........122 7.4 Conclusions ........................................122 III Conclusions and Future Work 125 8 Conclusions and Future Work 127 8.1 Conclusions ........................................127 8.2 Future Work ........................................130 Appendices 131 Appendix A List of Publications Supporting this Thesis Dissertation 133 ix 4Chapter 1. Introduction •An in depth study in off-line protocol optimization in VANETs. Different formulations have been proposed according to the type of protocol (routing or file transfer) and the main purpose of optimization (QoS and/or energy efficiency). Additionally, we have also analyzed mono-objective and multi-objective models of these problems. Therewith, we have defined a general off-line optimization tool, which couples a NC method (e.g., an evolutionary algorithm or a swarm intelligence method) with a VANET simulator, that can be tailored to optimize any VANET protocol. •An improvement of the efficiency and the efficacy of the NC algorithms used to solve off-line optimization in VANETs by introducing parallel models and specific operators (e.g., initialization, mutation, and crossover). •A new formulation of the broadcasting optimization problem more in line with the specific features and requirements of the VANET’s has been defined. In this sense, four different distributed dynamic broadcasting algorithms have been proposed to address such optimization problem. •A novel multi-objective optimization problem formulation of the roadside unit deployment in vehicular communications (RSU-DP problem), which takes into account realwold existing devices and road traffic information. In order to address this problem, a large-sized instance with the main roads of Málaga (Spain) has been modeled with real traffic data from the city council. Additionally, we have proposed a bio-inspired multiobjective algorithm (with specific operators) to tackle RSU-DP in the city of Málaga. A comparison with the last state-of-the-art algorithms has been provided. •A large VANET simulation testbed defined based on real-world data of different neighborhoods of Málaga has been created. The instances that incorporate this testbed comprise different area sizes, road traffic patterns, VANET applications, etc. •A definition of a real-world outdoor testbed to evaluate different VANET solutions. Besides this, we have analyzed the feasibility of expanding VANET technology with the use of lightweight personal devices (smartphones, tablets, and laptops). 1.4 Dissertation Outline This thesis work is highly oriented towards the problem domain, and this reflects into its structure as a document. Thus, this volume is divided into three parts, that follow this introduction. In the first part we present the fundamentals and bases for the work: the vehicular networks domain, NC as a global family of methods to solve optimization problems, and the VANET optimization problems addressed in this work, including the literature review. The second part (the principal one) is devoted to the whole experimental research work performed in this thesis. Full analysis of the optimization problems are analyzed here (routing, broadcasting, and roadside infrastructure design). As most of them are pioneers in the current literature, full formulation, models, and evaluation methods are detailed for each problem. Additionally, this part includes the real-wold VANET experiments performed on the roads of Málaga. Finally, the third and last part of the thesis regroups the main conclusions drawn throughout the work and summarizes our findings. We detail the contents of the chapters below. Chapter 1. Introduction 5 •Part I: Fundamentals Chapter 2gives a general description of VANETs. It introduces some of the most important communication technologies, reviews the main VANET applications, provides the main differences between VANETs and other mobile networks, and overviews the different worldwide VANET-related projects and consortia. Finally, we discuss the main current open challenges, which have been the main motivation to formulate the optimization problems that are presented in the next chapter. Chapter 3gives an introduction to the research field of NC in optimization problems. We put special attention on the algorithms utilized in the whole thesis. Besides this, it introduces the VANET optimization problems analyzed and reviews the main related literature. Finally, this chapter includes the methodology followed to evaluate the optimization techniques applied in solving such problems. •Part II: Optimization and Experimentation in Vehicular Networks Chapter 4presents our approach to solve off-line protocol tuning optimization problems for VANETs. Different VANET protocols (file transfer and routing) are optimized in terms of quality-of-service (QoS) and/or energy consumption. For this reason, several problem formulations are presented for the problem objectives. In our analysis, we include a representative set of well-known NC algorithms, which include mono-objective and multi-objective solvers and sequential (one-thread) and parallel algorithms. Finally, the efficacy of the optimized protocols are confirmed by performing a set of validation experiments, which involve simulations over a number of realistic VANET scenarios. In Chapter 5, we introduce the concept of fair (balanced) beacon broadcasting. Then, we describe a series of distributed greedy algorithms for broadcasting beacons in VANET. These methods, that are supposed to be running in each vehicle, dynamically (on-line) optimize the balance and the VANET medium occupancy. Finally, a set of validation experiments are performed in a number of highway VANET scenarios. In Chapter 6, we present a novel explicit multi-objective formulation of the RSU-DP in order to find a set of solutions that maximize the QoS and minimize the installation costs. We devise a parallel evolutionary algorithm, which applies specific operators to improve the efficacy of this optimization method, to solve the problem in an instance defined with real data of Málaga. Finally, the results are compared against the last state-of-theart optimization algorithms proposed to address RSU-DP. Chapter 7describes a set of real-world VANET experiments that have been performed in open roads of the city of Málaga. These outdoor testbeds are performed with two main purposes: first, we compare the optimized and the standard parameterizations of a file transfer protocol to confirm the results obtained in Chapter 4; and second, we analyze real vehicle-to-vehicle communications by using a set of widely available personal portable devices (smartphones, tablets, and laptops) in order to evaluate their capabilities to be used to deploy real VANETs. •Part VI: Conclusions and Future Work Chapter 8contains a global review of this thesis dissertation, and regroups the main conclusions drawn for the whole research work. The thesis objectives and main contributions are discussed in view of the results obtained. Finally, the future lines of research that can be pursued following the work presented here are briefly sketched and discussed. 6Chapter 1. Introduction In summary, we have tried to give a new perspective to significant problems (in the domain of VANETs), we have applied new solving techniques focusing on the applicability of the solution, and we have analyzed how to make vehicular networks a reality. We have performed innovative research to fill gaps of the literature in order to conclude a meaningful PhD thesis in this competitive present world. Any fool can know. The point is to understand. ALBERT EINSTEIN PART I: FUNDAMENTALS 7 Chapter 2 Vehicular Networks: Opportunities and Research Challenges TODAY, the longstanding promise of deploying applications based on vehicular ad hoc networks (VANETs) to improve efficiency and safety in road transport is becoming a reality. However, there are still some open questions to be carefully addressed before a widespread deployment of this technology. The aim of this chapter is to introduce VANETs as a case of success of the implementation of Natural Computing as a design tool. Thus, this chapter introduces some of the most important VANET communication technologies, it reviews the most salient applications that rely on these type of networks, it presents the main differences between VANETs and other mobile networks, it overviews the different activities (projects and consortia) carried out in this domain, and finally, it describes the most salient current open challenges. Please notice that it does not intend to be a comprehensive analysis of the state-of-the-art of vehicular communications since it is out of the scope of this thesis. 2.1 Introduction Nowadays, the most widely used means of transport are cars and other private vehicles. The huge increase in the volume of road traffic experienced during the last decades causes today serious problems that have to be confronted by our modern society. Recent estimates have shown that 1.24 million human lives are lost each year as a result of road traffic crashes (WHO, 2015). In addition, traffic jams, besides causing discomfort, limit the efficiency in transportation with vehicles because of the growth of the travel times, with the subsequent increase of the energy consumption and the impact on the environment (affected by the large associate air pollution). As a global consequence, our present industry, academia, and governments worldwide are devoting considerable resources to increase road safety and traffic efficiency.Information and communication technologies (ICT) are the driving force behind some of the most important innovations in dealing with this challenge. The use of mobile communication systems in vehicular environments is a recent field that will provide modern intelligent transportation systems (ITS) that will allow the development of the next generation smart mobility services. One of the most promising solutions is the use of emerging vehicular communication networks known as vehicular ad hoc networks (VANETs) (Hartenstein and Laberteaux, 2009; Campolo et al., 2015; Yousefi et al., 2006; Morris et al., 2000). VANETs are composed by a collection of vehicles and roadside elements connected with each other using infrastructure-less wireless technologies. Although, many considerations are still in the air, like the open debate whether it is necessary 9 10 Chapter 2. Vehicular Networks: Opportunities and Research Challenges or not to redefine the term in order to include infrastructure-based and cellular systems in the vehicular communications (see Figure 2.1). VANETs offer the possibility of improving the safety and efficiency of the road traffic through powerful cooperative applications based on a continuous information sharing. FIGURE 2.1: A schematic representation of a vehicular network. 2.2 VANET Communication Technologies ITS applications have different and varied communication requirements in terms of bandwidth, latency, coverage and other performance metrics, which have to be fulfilled by VANETs. This section introduces the VANET’s architecture, the different communication domains, and the main radio access technologies utilized in these vehicular environments. 2.2.1 Architecture The three main components of the whole VANET system are the on-board, roadside, and application units. They are described bellow: •On-board unit (OBU): OBUs are hardware devices integrated in the vehicles in order to provide them with processing and communication capabilities. Their main functions are: i) gathering and processing the data collected from the sensors installed in the vehicle (e.g., kinematics data) and ii) exchanging vehicular information with other VANET nodes (OBUs or roadside units) via direct short range wireless communications (DSRC), which are principally based on IEEE 802.11p radio technology (FCC, 1999). OBUs may additionally include another network interfaces based on other radio access technologies such IEEE 802.11a/b/g/n or WiMAX (IEEE 802.16). They also provide communication services to the application units forwarding data on behalf of other OBUs in the network (see Figure 2.2.a). •Roadside unit (RSU): RSUs are devices that are usually installed on the roadside infrastructure elements, i.e., traffic lights or signals. In turn, they may be fixed along roadside as specific dedicated VANET elements. They include a network interface to exchange information with other VANET nodes through DSRC. They may also be equipped with other network interfaces to connect to other networks or to the Internet (see Figure 2.2.b). They perform three main functions (C2C-CC, 2007): i) acting as an information source or receiver in safety applications, e.g., warning about of the existence of roadworks; ii) extending the effective communication range by forwarding data to other VANET nodes (OBUs or RSUs) through multi-hop communications; and iii) providing Internet connectivity to the OBUs. Chapter 2. Vehicular Networks: Opportunities and Research Challenges 11 •Application unit (AU): The AU may be either an external device connected to the OBU or a device integrated into the OBU forming a single physical unit (see Figure 2.2.c). If it is external device, it can be a dedicated device for VANET applications or a regular mobile device, such as a smartphone or a personal digital assistant (PDA). The AU provides a user interface to access the VANET applications, e.g, microphone or speakers. It is connected to the OBU through wired or wireless connection, such as Bluetooth. The OBUs act as network gateway that is used by the AUs to exchange information through the VANET or to connect to the Internet. a) OBU. b) RSU. c) AU. FIGURE 2.2: Main elements of the VANET architecture (QMIC, 2015). 2.2.2 Communication Domains Vehicular communication systems include of three types of communication domains (Olariu and Weigle, 2009): •In-vehicle domain: This domain refers to the network composed by the devices inside the vehicle (i.e, the sensors, the OBU, and one or multiple AUs). Thus, the OBU is able to use the network links to gather the information from the sensors and share it with the AUs. The communication can be implemented with wired or wireless links. Some example of the used wireless technologies in this domain are the Bluetooth, the wireless universal serial bus (WUSB), and the ultra-wide band (UWB) (Jogi and Choudhary, 2009). •Ad hoc domain: The ad hoc domain is composed by OBUs (mobile devices) and RSUs forming a mobile ad hoc network (MANET). These nodes exchange information in a fully distributed manner without using any centralized coordination entity through DSRC. In this domain, the communicating nodes are either just vehicles (OBUs) exchanging information with each other through vehicle-to-vehicle (V2V) communication or vehicles communicating with RSUs via vehicle-to-infrastructure (V2I) communication (see Figure 2.3). The performance of the communications in the ad hoc domain is highly dependent on the routing and broadcasting protocols utilized to forward the data from the source to the destination nodes. •Infrastructural domain: Extending VANETs by including links to Internet provider agents, may increase the power of the VANET applications. Thus, RSUs can be attached to this kind of networks in order to act as gateway for OBUs allowing the vehicles to access services that are provided by infrastructure networks. In turn, OBUs may be equipped with cellular radio network interfaces, such as long term evolution (LTE), to perform vehicle-to-broadband cloud (V2B) communication to directly access infrastructure networks (see Figure 2.3) (Hossain et al., 2010). 12 Chapter 2. Vehicular Networks: Opportunities and Research Challenges FIGURE 2.3: A representation of the ad hoc and the infrastructural communication domains. In spite of the raising of different radio access technologies of cellular networks that may provide infrastructural domain vehicular communications (V2B), most research is addressed in proposing an ad hoc communication platform to allow reliable V2V and V2I communications (Hartenstein and Laberteaux, 2009). 2.2.3 Wireless Access Technologies for VANETs Vehicular networks can be deployed by using several of the numerous access technologies available today (Hossain et al., 2010). The radio access technologies (RATs) applied in vehicular environments, such as wireless local area networks (WLAN based on IEEE 802.11a/b/g/n/p standards), WiMAX (IEEE 802.16 a/e standards), Bluetooth (IEEE 802.15.1 standard), and last generations of cellular networks (3G and LTE), provide communications with different qualityof-service (QoS) which determine the communication latency, bandwidth, coverage, etc. The most salient RATs applied in V2V, V2I, and V2B communications are the following ones: •WLAN: The family of IEEE 802.11 wireless standards (Cooklev, 2004), which have achieved a great acceptance in the market, support short-range relatively high-speed data transmission. IEEE 802.11 standard defines over-the-air protocols necessary to support networking in a local area and it specifies physical (PHY) and medium access control (MAC) layers. There are several specifications in the IEEE 802.11 family which extend the original one (IEEE 802.11). The most extended ones are the IEEE 802.11b and IEEE 802.11g standards, that provide 11 Mbps and 54 Mbps transmission in the 2.4 GHz band with a maximum range of 500 m, respectively. IEEE 802.11a is an extension to 802.11 that provides up to 54 Mbps in the 5 GHz band using the orthogonal frequency division multiplexing (OFDM) encoding scheme. Transfer rates increased with IEEE 802.11n standard with a bandwidth up to 500 Mbps. In addition, there are a number of other 802.11 WG activities that define inter access point protocol (IEEE 802.11f), MAC enhancements for security (IEEE 802.11i), MAC enhancements for QoS (IEEE 802.11e), etc. WLAN radio access technologies enable V2V and V2I communications. •DSRC: In 1999, the U.S. Federal Communication Commission allocated 75 MHz of DSRC spectrum at 5.9 GHz to be used exclusively for vehicular ad hoc communications (FCC, 1999). DSRC technology allows high speed communications between VANET nodes that might be separated up to 1000 meters. There exist differences in the frequency allocation between North America and Europe, but the intention is to be able to use the same antenna and transmitter/receiver. Different organizations like the Institute of Electrical and Electronic Engineers (IEEE), International Standard Organization (ISO) or Car-to-Car Communication Consortium (C2C-CC) are working on developing an architecture for VANETs. Chapter 2. Vehicular Networks: Opportunities and Research Challenges 13 There is no agreement between the different organizations on which of the different proposals is more convenient for vehicular networks, thus, each of them is working on their own proposal: wireless access in vehicular environment (WAVE) by IEEE (Uzcategui and Acosta-Marum, 2009), communication access for land mobiles (CALM) by ISO (CALM, 2015), and Car-to-Car Network (C2CNet) by C2C-CC (C2C-CC, 2007). Nowadays, the most utilized architecture to provide DSRC (V2V and V2I communications) is based on the IEEE 802.11p standard (ETSI, 2010), which is specifically designed for supporting WAVE ITS applications. The IEEE 802.11p was firstly adopted by IEEE and American Society for Testing and Materials (ASTM) (ASTM, 2003) and specifies the PHY and MAC layers. WAVE protocol stack is completed by the IEEE 1609 standards family (Guerrero-Ibáñez et al., 2013) at the upper layers. •WiMAX: WiMax is a standard developed by IEEE, the IEEE 802.16 (Nuaymi, 2007). It was defined to provide wireless broadband access over long distances (up to 50 Km). WiMAX can operate with bandwidths up to 70 Mbps. However, when the distance between the nodes grows the bit error rate (BER) critically increases, and therefore, the effective bandwidth is reduced (Ghosh et al., 2005). In 2005, Mobile WiMAX (originally based on 802.16e-2005) was deployed in many countries to provide mobile nodes with WiMAX radio access. WiMAX has been proposed to improve the performance of V2I communications (Shrivastava et al., 2012). •LTE:Long term evolution (LTE), also known as Evolved Universal Terrestrial Access Network (E-UTRAN), is a standard for cellular wireless communication that has been developed by the Third Generation Partnership Project (3GPP) 3GPP, 2010. The main idea that motivated LTE was to improve the Universal Mobile Telecommunications System (UMTS), which is the third generation (3G) of mobile cellular systems for networks based on the Global System for Mobile (GSM) standard. LTE provides high spectral efficiency by a combination of advanced multi-antenna techniques, and orthogonal frequency-division multiple access (OFDMA) in the downlink (DL) and single-carrier frequency-division multiple access (SC-FDMA) in the uplink (UL). Thus, it improves significantly the data rates, with the potential for 300 Mbps downstream and 75 Mbps upstream, while reducing the communication latency. In addition, it offers scalable bandwidth capacity and backwards compatibility with existing GSM and UMTS technologies. Some authors have included this RAT to be used in vehicular communications because some of these features are ideal for ITS applications (Benslimane et al., 2011; Mosyagin, 2010). Since ITS applications request services with different communication requirements in terms of latency, bandwidth, error rate, coverage area, etc., recently, several studies urged to combine different RATs into a unified hybrid vehicular networking (HVN) or V2X-Communication architecture (Hameed Mir and Filali, 2014; Park et al., 2014; Vinel, 2012). For example, ISO proposed CALM M5 by incorporating a set of wireless technologies including UMTS-3G, infrared communication, and wireless systems adapted to IEEE 802.11p (Olariu and Weigle, 2009). 2.3 VANET Applications Vehicular networks allow the development of a large set of powerful applications that will improve the road transportation experience for both, drivers and passengers. Typically, the associated literature categorizes these applications in two different main groups: safety and non-safety applications. The first ones utilize VANETs to exchange information to improve road safety and avoid road accidents. Non-safety applications represent a hodgepodge of 20 Chapter 2. Vehicular Networks: Opportunities and Research Challenges FIGURE 2.6: Some examples of VANET routing algorithms analyzed in Dua et al. (2014). •Heterogeneous connectivity: VANETs originally emerged taking into account just IEEE 802.11 based technologies to exchange data via ad hoc networking, i.e., by using V2V and V2I communications (Hartenstein and Laberteaux, 2009). However, the increasing number of wireless communication technologies and standards have brought immense opportunities and challenges to provide seamless connectivity in vehicular networks. Thus, researchers defined advanced heterogeneous vehicular networks (AHVNs), also known as hybrid vehicular networks (HVNs), as vehicular networks that use multiple RATs (DSRC, WiMAX, LTE, ...) in a collaborative manner (Hossain et al., 2010). The main challenge in designing AHVNs is to efficiently decide which RAT to select to send a given packet, due to sheer number of use cases and applications with diverse and stringent QoS performance requirements and different communication conditions (Mir et al., 2015). For example, Benslimane et al. (2011) proposed a cluster-based strategy to deploy heterogeneous vehicular networks over Wi-Fi and 3G access technologies. •Hardware platform deployment: Vehicular communications may suffer from very frequent network disconnection during low density road traffic situations, i.e., in sparse VANETs. This can critically limit the network performance, and therefore, it adversely affect the proper operation of the VANET safety applications. The deployment of a fixed infrastructure along the roads composed by RSUs, that act as VANET base stations, may greatly improve the communications by increasing the overall coverage of the network (Reis et al., 2014). However, the deployment of the RSU infrastructure is a hard-to-solve (NPhard) problem (Trullols et al., 2010) because the designers have to decide about the location of the RSUs and the utilized hardware for each RSU, while not incurring to high deploying costs. There are different research lines to deal with this problem, e.g., some authors have model RSU deployment problem as a weighted approach for the traditional Maximum Coverage Problem (MCP) (Silva et al., 2015). Chapter 2. Vehicular Networks: Opportunities and Research Challenges 21 •Security and privacy: In VANET safety applications, drivers may take life-critical decisions and actions based on the information received from other nodes. Therefore, any malicious entity could cause disruption of traffic, dangerous situations, and accidents by modifying and replying the disseminated messages with fake information. In contrast, users are very conservative about sharing their privacy-related information, e.g., having their driving routes unconditionally accessed by the public. Thus, it is imperative that the VANET system must be able to determine the reliability of the users (drivers) and the messages while still maintaining their privacy and anonymity. In the literature, there are many studies dealing with this concern (Mejri et al., 2014). For example, Molina-Gil et al. (2014) proposed a new data aggregation protocol for vehicular networks, which uses probabilistic verification to detect malicious behavior of users. At the present time, the IEEE 1609.2 standard addresses the issues of securing WAVE messages against the possible malicious attacks and it is positioned for providing secure services for WAVE communications (Lin et al., 2008). •Network performance evaluation: The evaluation of the different implemented approaches (radio technologies, protocols, and network models) to deploy vehicular networks is a major concern in the field of VANETs. Outdoor testbeds can be undertaken to accomplish this task. These experiments may be carried out in real world environments offering close-to-real or real performance (in vitro versus in silico), as well as revealing behavioral issues (Santa et al., 2008). However, there is a lack of scientific articles that use outdoor experiments in the field of VANETs. The main reasons for this may be the unavailability and the cost of resources (high number of vehicles and road equipment). Thus, simulation and emulation tools are widely used to overcome the limitations of outdoor experiments in vehicular networks (Martinez et al., 2011). Authors have used three different types of strategies to simulate VANETs (Alba et al., 2008): utilizing a well-known network simulator, such as ns-2/ns-3 (NS2, 2015; Riley and Henderson, 2010; Issariyakul and Hossain, 2008) or OPNET (Sethi and Hnatyshin, 2012), that allows users to define the movement of the nodes by generating realistic VANET traces with transportation simulators, such as (Härri et al., 2011), SUMO (Krajzewicz et al., 2012) or VISSIM (Lownes and Machemehl, 2006); coupling vehicular traffic and wireless network in a single simulator, e.g., GrooveNet (Mangharam et al., 2006); and the most promising approach, synchronizing the existing and validated traffic and network simulators by using some specific bridge software, such as iTetris (Rondinone et al., 2013) and Veins (Sommer et al., 2011). Even if the simulators have achieved a high degree of realism and they obtain quite accurate results, the real world simplifications that they apply could limit their reliability. As it can be inferred from the previous list, this domain still comprises a heterogeneous set of open questions that have to be resolved in order to provide a body of knowledge to advance in vehicular communications. This PhD thesis aims at analyzing the application of Natural Computing (NC) in addressing a subset of these open challenges (see Section 3.3). Thus, the following chapters present the NC techniques utilized and how they are applied in dealing with data routing, beacon broadcasting, and designing the roadside infrastructure challenges. In addition, real world VANET/ITS applications and demonstrations are described. The idea is to make a journey from fundamental to more practical aspects related with vehicular communications, that have been selected because we thought that they are in the center of the worries in the whole domain. Chapter 3 Natural Computing and Optimization Challenges in VANETs NATURAL computing (NC) encompasses different classes of methods inspired in nature. Among others, it includes a novel methodology of complex problem solving techniques (e.g., evolutionary algorithms or swarm intelligence). In this thesis, we focus on the use of these techniques to address different VANETs questions. This chapter summarizes the basics about optimization problem solving, presents the NC algorithms utilized here, and introduces the reader to the different VANETs problems analyzed, including the most salient related works. Finally, it illustrates the process performed to evaluate NC in solving VANET optimization problems. 3.1 Introduction Natural phenomena, e.g., processes, organisms, etc., have long inspired and driven people to mimic, design, and develop systems and products. Natural Computing (NC) is the computational process of developing artificial (computational) systems by extracting ideas from nature or by using natural media (such as molecules). NC are generally divided in three main branches (De Castro, 2006): computing inspired by nature,the simulation and emulation of nature by means of computing, and computing with natural materials. In this thesis we focus on the first branch, computing inspired by nature, which globally takes the inspiration from nature (natural patterns, behaviors, and organisms) to design algorithms for the solution of complex problems. The computational techniques developed under this umbrella can also be termed as bio-inspired computing (Mange and Tomassini, 1998) or computing with biological metaphors (Paton, 1994). The landmark in the bio-inspired computing was the paper by McCulloch and Pitts (1943), which laid the foundations of artificial neural networks by introducing the first mathematical model of a neuron. Afterwards, another computation approaches emerged inspired by nature. These other techniques are grouped in three main types: 1) evolutionary computing, which uses the ideas from evolutionary biology to design evolutionary algorithms (EAs); 2) swarm intelligence, in which a set of simple agents mimic the behavior of social organisms in a given algorithm; and 3) artificial immune systems (AIS), which extract ideas from the models followed by immune systems to develop computational tools, cover one of the last groups to appear. In addition, several emerging bio-inspired algorithms can be found in the literature that specifically do not belong to any of the previous types, e.g., simulated annealing (SA). 23 24 Chapter 3. Natural Computing and Optimization Challenges in VANETs This thesis aims at addressing a set of the main challenges that limit the VANETs deployment (see Section 2.6). These challenges may be tackled as hard to solve optimization problems, which can be solved by utilizing NC. Specifically, in our research we have focus on the use of EAs, swarm intelligence, and SA in solving VANETs optimization problems. Now let us introduce some essential concepts about optimization problems. 3.1.1 Overview of Optimization Problems There exist a large number of real-life problems that are complex and difficult to solve. Exact algorithms are not appropriate or require large amount of resources (e.g. memory or computational cost) for using them. Therefore, approximate algorithms are needed. Among approximate algorithms, one can find two types: heuristics and metaheuristics. Heuristics can in turn be divided between constructive heuristics and local search methods. We focus this chapter on metaheuristics. Figure 3.1 shows a simple classification of optimization methods used throughout the history of computer science. Metaheuristics are approximate algorithms that emerged as efficient (stochastic) optimization tools that are able to provide good solutions for complex optimization problems (Glover and Kochenberger, 2003; Blum and Roli, 2003). In general, metaheuristics make no assumptions about the problem to solve, as generic tools they only use appropriate solution representations, quality or fitness functions, and (specific) operators to guide the solution towards better solutions (Osman and Kelly, 2012). Many metaheuristics are inspired by nature, such as EAs, swarm intelligence, and SA (Figure 3.1) (Yang, 2010). Before detailing these NC methods we will introduce some essential concepts about optimization. FIGURE 3.1: General classification of the optimization techniques. We shall begin with a formal definition of optimization. Assuming, without loss of generality, a minimization case, the definition of an optimization problem is as follows: Definition 1. Optimization problem An optimization problem is defined as a pair (S, f), where S6=∅is called the solution space (or search space) of the problem, while fis a quality criterion named objective function or fitness function, defined as: f:S−→ R(3.1) Chapter 3. Natural Computing and Optimization Challenges in VANETs 25 In this case where a single criterion fis optimized, known as mono-objective or single-objective optimization, the objective is to find a global optimum element s∗∈Ssuch that: f(s∗)≤f(s)∀s∈S(3.2) Depending on the domain where Sbelongs, we can speak of binary (S⊆B∗) , integer (S⊆N∗), continuous (S⊆R∗) or heterogeneous (S⊆(B∪N∪R)∗) optimization problems. Note that assuming either maximization or minimization does not restrict the generality of the results, since an equivalence can be made between the two cases in the following manner (Goldberg, 1989): max{f(s)|s∈S} ≡ min{−f(s)|s∈S}(3.3) This definition is utilized when the optimization problem focus on a single objective (monoobjective). Nevertheless, many the real-world problems deal with different objectives that are usually in conflict with each other (e.g. maximizing the coverage of the VANET infrastructure elements but while minimizing the cost of the installed infrastructure). This other types of problems are known as multi-objective optimization (Deb, 2001). The main difference between mono-objective and multi-objective optimization is that for the second ones there is not a single optimal solution that satisfies all the objectives but a set. A general multi-objective optimization problem (MOP) is to find vectors ~ s∗= [s∗ 1, s∗ 2, ..., s∗ n] that are optimizing the vector of functions ~ f(~s) = [f1(~s), f2(~s), ..., fk(~s)]. Each fi(~s)is a monoobjective optimization problem, and it is considered one of the objectives to optimize in our MOP. The different objectives must be in conflict with the others, meaning that an increase in the quality of one of them will lead to a decrease in the values of (some of) the others. If the objectives were not in conflict, then we could reformulate the problem as a mono-objective one. More formally multi-objective minimization problem is defined as: Definition 2. Multi-objective minimization Find a vector ~ s∗= [s∗ 1, s∗ 2, ..., s∗ n]which satisfies the minequality constraints gi(~s)≥0,i= 1,2, ..., m, the pequality constraints hj(~s) = 0, j= 1,2, ..., p, and minimizes the vector function ~ f(~s) = [f1(~s), f2(~s), ..., fk(~s)]T, where ~s = [s1, s2, ..., sn]Tis the vector of decision variables. In MOP, to decide whether a given solution is better than other is utilized the concept of dominance. A solution wdominates a solution vif wis strictly better than vin at least one objective and better or equal to vin the rest of objectives (see Figure 3.2.a). A set of solutions are said to be non-dominated if none dominates the others. Therefore, the goal of multi-objective optimization is to find the optimal set of non-dominated solutions to the problem, which is named Pareto optimal set (see Figure 3.2.b). The projection of the Pareto optimal set in the objectives domain is called the Pareto optimal front (Coello et al., 2007). a) The wsolution dominates uand v. b) Non-dominated solutions. FIGURE 3.2: Dominance in multi-objective optimization. After these definitions let us presenting the NC algorithms applied in this thesis. 26 Chapter 3. Natural Computing and Optimization Challenges in VANETs 3.2 NC Applied in VANETs The bio-inspired algorithms applied in this research are categorized into EAs, swarm intelligence, and SA. Evolutionary algorithms are based on the Darwinian theory of evolution (Fogel et al., 1966; Holland, 1975). Darwin proposed that a population of individuals capable of reproducing and subjected to (genetic) variation followed by selection result in new populations of individuals increasingly more fit to their environment (De Castro, 2006). These simple natural processes when applied in computation result in a number of different algorithms, such as: genetic algorithms (GA) (Goldberg, 1989), evolution strategies (ES) (Beyer and Schwefel, 2002), evolutionary programming (EP) (Fogel, 1999), and genetic programming (GP) (Koza, 1992). Swarm intelligence was introduced to refer to cellular robotic (multi-agent) systems in which a collection of simple agents in an environment interact based on local rules (Bonabeau et al., 1999). Currently, this term is used to describe the design of algorithms or problemsolving devices inspired by the collective behavior of social organisms. Some swarm intelligence algorithms used to address hard to solve optimization problems are: particle swarm optimization (PSO) (Eberhart and Kennedy, 1995), ant colony optimization (ACO) (Dorigo et al., 1996), and artificial bee colony algorithm (ABC) (Karaboga and Basturk, 2007). Finally, simulated annealing (SA) is one of the oldest bio-inspired algorithms and it is based on the annealing process of metal and crystal (Kirkpatrick et al., 1983). It is considered as the first method with an explicit strategy for escaping local optima. These natural inspired algorithms can be classified as trajectory based algorithms and population based or swarm based ones (see Figure 3.1). Those of the first type handle a single element of the search space at a time (one solution), e.g. SA; while those of the latter work on a set of elements (named population or swarm), the EAs and swarm intelligence algorithms utilized in this thesis belong this group. We will now describe the NC algorithms applied in our research. 3.2.1 Evolutionary Algorithms Four different EAs have been utilized in this thesis: three mono-objective algorithms, i.e., GA, ES, and differential evolution (DE), and one multi-objective EA (MOEA), the non-dominated sorting genetic algorithm-II (NSGA-II). They are detailed in the following subsections. Genetic Algorithm (GA) Genetic Algorithm (Goldberg, 1989) is the most popular EA. It iterates a process in which a set of solutions (parents) are selected from the whole population with a given selection criterion, they are then recombined (crossover operation), the obtained offsprings are mutated, and finally they are evaluated and inserted back into the population following a given criterion (fitness function). The mutation process is carried out by randomly (uniformly) selecting one of the elements in the solution, and assigning (randomly) a new value in a specific range. In this research work, we use a polynomial crossover defined for continuous variables and two point crossover (Goldberg, 1989) as the recombination operator. In addition, specific mutation operators have been designed for the problems addressed here. Algorithm 1 summarizes the operations of a canonical GA. There are two main versions of GA: steady state GA (ssGA) and generational GA (genGA). The difference between the ssGA and the genGA is the way in which the population is updated with the new individuals generated during the evolution. In the first one, new individuals are directly inserted into the current population. In the case of the genGA, a new auxiliary population is built with the obtained offsprings and then, once this auxiliary population is full, it completely replaces the current population. Thus, in ssGAs the population is asynchronously being updated with the newly generated individuals, while in the case of genGAs all the new individuals are updated at the same time, in a synchronous way. Chapter 3. Natural Computing and Optimization Challenges in VANETs 27 Algorithm 1 Pseudocode of GA g←0 Pg←initializePopulation() // P = population while not stopCondition() do parents ←selection(P) // Select parents offspring ←recombination(parents) // Generate offspring by recombination offspring ←mutation(offspring) // Generate offspring by mutation evaluate(offspring) Pg+1 ←select(offspring) // New population generation g←g+ 1 end while Evolutionary Strategy (ES) Evolutionary Strategy (Beyer and Schwefel, 2002) is an EA also based on the ideas of adaptation and evolution. As common with EAs, the mutation and selection operators are applied to the solutions (individuals) through a given number of generations. The selection in evolutionary strategies is deterministic and only based on the fitness rankings. In ES, we use the same mutation operator than the GA. Algorithm 2 Pseudocode of ES 1: g←0 2: parent0←initializeParent() 3: while not stopCondition() do 4: offspringg←mutate(parentg) 5: evaluate(offspringg) 6: if f(offspringg)is better than f(parentg)then 7: parentg←offspringg 8: end if 9: g←g+ 1 10: end while The canonical ES (Algorithm 2) operates on a population of size two: the current individual (parentg) and the result of its mutation (offspringg). After the parent initialization (Line 2), ES starts the evolutionary process by generating a mutated offspring (Line 4) which is evaluated (Line 5). Only if the offspring has a better fitness than the parent, it becomes the parent of the next generation (lines 6-8). Otherwise the offspring is ignored. This is version of ES is called (1 + 1)−ES. More generally, in (1 + λ)-ES, a population with more than one offsprings (λ) can be generated for being compared with the same parent. In a (1, λ)-ES the best offspring becomes the parent of the next generation while the current parent is always ignored. The most generalized version, (µ+/, λ)-ES, often uses a population of parents (µ) and also recombination as an additional operator. Differential Evolution (DE) Differential Evolution (Price et al., 2005) is also a stochastic population based algorithm designed to solve optimization problems in continuous domains. The main difference in the evolutionary model with the other EAs is that the fittest of an offspring competes one-to-one with that of corresponding parent. 28 Chapter 3. Natural Computing and Optimization Challenges in VANETs The population consists of a set of individuals (vectors) which evolve simultaneously through the search space of the problem. The task of generating new individuals is performed by differential operators such as the differential mutation and differential crossover. A mutant individual wi g+1 is generated by the following Equation 3.4: wi g+1 ←vr1 g+µ·(vr2 g−vr3 g)(3.4) where r1, r2, r3∈ {1,2, . . . , i −1, i + 1, . . . , N}are random integers mutually different, and also different from the index i. The mutation constant µ > 0stands for the amplification of the difference between the individuals vr2 gand vr3 g, and it avoids the stagnation of the search process. In order to increase even more the diversity in the population, each mutated individual undergoes a crossover operation with the target individual vi g, by means of which a trial individual ui g+1 is generated. A randomly chosen vector component is taken from the mutant individual to prevent that the trial individual replicates the target individual. ui g+1(j)←(wi g+1(j)if r(j)≤Cor j=jr, vi g(j)otherwise. (3.5) As shown in Equation 3.5, for each component jof the trial individual ui g+1, the crossover operator chooses both, a random integer value jrand a random real number r(j)∈(0,1), uniformly distributed. Then, the crossover probability Cand r(j)are compared just like jand jr. If ris less than or equal than Cor jis equal to jr, then we select the jth element of the mutant individual to be allocated in the jth element of the trial individual ui g+1. Otherwise, the jth element of the target individual vi gbecomes the jth element of the trial individual. Finally, a selection operator decides the acceptance of the trial individual for the next generation if and only if it yields a reduction (assuming minimization) in the value of the fitness function f, as shown in Equation 3.6: vi g+1 ←(ui g+1 if f(ui g+1)≤f(vi g), vi g(j)otherwise. (3.6) Algorithm 3 Pseudocode of DE 1: g←0 2: P0←initializePopulation() // P = Population 3: while not stopCondition() do 4: for each individual vi gin Pdo 5: chooseMutuallyDifferent(r1, r2, r3) 6: wi g+1 ←differentialMutation(vr1 g, vr2 g, vr3 g, µ) // Equation 3.4 7: ui g+1 ←differentialCrossover(vi g, wi g+1, C) // Equation 3.5 8: evaluate(ui g+1) 9: vi g+1 ←selection(vi g, ui g+1) // Equation 3.6 10: end for 11: g←g+ 1 12: end while Algorithm 3 shows the pseudocode of DE. After initializing the population, the individuals evolve while stop condition is not reached. Each individual is then mutated (Line 6) and recombined (Line 7). The new individual is selected (or not) following the operation of Equation 3.6 (lines 8 and 9). Chapter 3. Natural Computing and Optimization Challenges in VANETs 29 Non-dominated Sorting Genetic Algorithm-II (NSGA-II) NSGA-II is a multi-objective evolutionary algorithm (MOEA) version of the GA presented in Deb et al. (2002). It emerged to solve the main drawbacks of its prior version, NSGA, that are: the computational complexity, the lack of elitism, and the need of choosing the optimal parameter value for sharing parameter σshare. Nowadays, NSGA-II is one of the reference algorithms to solve multi-objective problems. Therefore, we have selected it as a baseline for the research work carried out in this thesis. Its pseudocode is presented in Algorithm 4. NSGA-II makes use of a population (Pg) of solutions. In each generation, it creates new individuals (offspring) after applying genetic operators to Pg(recombination and mutation) to create a new population Q(lines 6 to 8). Then, both the current (Pg) and the new population (Q) are merged; the resulting population, R, is ordered according to a ranking procedure and a density estimator known as crowding distance (Line 13) (Deb et al., 2002). Finally, the population Pgis updated with the best individuals in R(Line 14). These steps are repeated until the termination condition is fulfilled. Algorithm 4 Pseudocode of NSGA-II. 1: g←0 2: P0←initializePopulation() // Pg= population 3: while not stopCondition() do 4: Q← ∅ // Q= auxiliary population 5: for i←1to (Pg.popSize / 2) do 6: parents ←selection(Pg) 7: offspring ←recombination(parents) 8: offspring ←mutation(offspring) 9: evaluate_solution(offspring) 10: insert(offspring,Q) 11: end for 12: R←Pg∪Q// R = auxiliary resulting population 13: rankingCrowding(R) 14: Pg+1 ←selectBestIndividuals(R) // Applying elitism 15: g←g+ 1 16: end while 3.2.2 Swarm Intelligence Regarding swarm intelligence algorithms, in this PhD thesis we have applied two different methods: PSO to tackle mono-objective problems and speed-constrained multi-objective particle swarm optimization (SMPSO) to address MOPs (Nebro et al., 2009). Let us to describe these two algorithms. Particle Swarm Optimization (PSO) Particle swarm optimization (Eberhart and Kennedy, 1995) is a NC method inspired in the social behavior of bird flocking or fish schooling. It was initially designed for continuous optimization problems. Each potential solution to the problem is called particle and the set of particles is called a swarm (hence the name of the algorithm). In this algorithm, each particle position pi gis updated each generation gby means of the Equation 3.7: pi g+1 ←pi g+vi g+1,(3.7) where the term vi g+1 is the velocity of the particle, given by the next expression: 36 Chapter 3. Natural Computing and Optimization Challenges in VANETs given area of Brunswick, Germany (Lochert et al., 2008). Other two studies applied the same NC algorithm to optimize the coverage. Cavalcante et al. (2012) compared GA against the greedy approach proposed in Trullols et al. (2010), showing that the GA solutions obtained better vehicle coverage than those given by the greedy approach. Cheng et al. (2013) used just geometry-based coverage information about the roads (without vehicles mobility related data) of Yukon Territory (Canada). In this study, GA outperformed the α–coverage algorithm, which consists in placing the RSUs in the center of the junctions. All this research analyzed a problem that is essentially multi-objective (maximizing QoS while minimizing deployment cost) by using mono-objective NC algorithms. This drove us to accomplish the study presented in Chapter 6, which address RSU-DP applying an explicit multi-objective formulation. In this manner, the VANET designers may have a set of accurate solutions, which present different trade-off between QoS and cost, to efficiently decide the design to be deployed. 3.4 Evaluation of the Results In this research work, we have addressed real-world problems related to vehicular networks. Therefore, the desirable manner to evaluate the results is to validate them in real-world environments (by performing outdoor testbeds or realistic VANET simulations), which has been one of the regular practices carried out in here. Nevertheless, we have also wanted to evaluate NC in addressing such kind of problems, in order to provide a powerful base tool to be used in further VANET optimization problems. Thus, in this section we specify how we carried out the NC evaluation. The natural inspired methods applied in this thesis are non-deterministic, hence different executions of the same algorithm over the same problem instance can produce different results. This can cause inconveniences to researchers when evaluating those results, and in the comparison of different algorithms. Besides, in the domain of optimization problems with non-deterministic algorithms is commonly adopted the comparisons on the basis of empirical data. For these reasons, some methodology based on well defined indicators should be established. In this sense, there are two types of indicators: the ones to evaluate the quality of the computed solutions and those used to measure the performance in terms of required computation time or the amount of resources they use. There are different specific quality indicators depending on whether the problem is mono-objective or multi-objective. Let us to describe them, afterwards we will present the performance metrics used as well as the statistical analysis procedure adopted in this thesis. 3.4.1 Quality Indicators The optimization problems treated in this PhD thesis have not a known the optimum value beforehand (as most of real-world problems), and therefore, we cannot use hit rate metric (the ratio of times that the optimum is obtained). Thus, a most commonly adopted approach is to finish the algorithms after a given computational effort has been spent (like visiting a maximum number of points of the search space or running for a given time), and then, evaluate the quality of the solutions obtained. In mono-objective optimization, different metrics about the final fitness computed are used, such as average,standard deviation,median,maximum,minimum values obtained after a given number of independent runs. It is commonly adopted the use of 30 executions as the minimum accepted number of runs, though higher values (such as 100) are recommended (this is very dependent on the run time of the algorithms). Chapter 3. Natural Computing and Optimization Challenges in VANETs 37 Multi-objective optimization algorithms compute an approximation set to the optimal Pareto front (see Section 3.1.1), which stores a set of non-dominated solutions that presents different trade-offs between the objectives. In general, two properties are usually evaluated in MOP: convergence and a uniform diversity. In this thesis the three major performance used metrics are utilized to evaluate the multi-objective NC approaches: •Hypervolume (IHV ) (Zitzler and Thiele, 1999): This indicator calculates the volume, in the objective space, covered by members of a non-dominated set of solutions Q. Formally, for each solution i∈Q, a hypercube viis constructed with a reference point Wand the solution ias its diagonal corners. The reference point can simply be found by constructing a vector of worst objective function values. Thereafter, a union of all hypercubes is found and its IHV is calculated: IHV =volume   |Q| [ i=1 vi (3.10) •Epsilon (I) (Knowles et al., 2006): This indicator measures the smallest distance one would need to to translate every solution in a given front Aso that it dominates the optimal Pareto front of the problem. Mathematically, given ~ z1=z1 1, ..., z1 nand ~ z2=z2 1, ..., z2 n, where nis the number of objectives: I1 +(A) = inf n∈R| ∀~ z2∈PF∗∃~ z1∈A:~ z1≺~ z2o(3.11) where ~ z1≺~ z2if and only if ∀1≤i≤n:~ z1< ~ z2. •Spread (I∆) (Deb, 2001): This metric evaluates the extent of spread by the set of computed solutions and it is defined as: I∆=df+dl+PN−1 i=1 di−¯ d df+dl+ (N−1) ¯ d(3.12) where diis the Euclidean distance between consecutive solutions, ¯ dis the average of these distances, and dfand dlare the Euclidean distances to the extreme solutions of the optimal Pareto front in the objective space. This indicator takes a zero value for an ideal distribution, pointing out a perfect spread of the solutions in the Pareto front. •Generational Distance (GD): This metric measures how far the elements in the computed front are from those in the optimal Pareto (Veldhuizen and Lamont, 1998) and it is defined as: GD =qPN i=1 d2 i N(3.13) where Nis the number of solutions in the approximated front and diis the Euclidean distance (measured in objective space) between each of these solutions and the nearest member in the optimal Pareto front. A value of GD=0 indicates that all the generated elements are in the Pareto front. After presenting the quality indicators for both, mono-objective and multi-objective optimization, we will define the performance indicators utilized to asses our algorithms. 38 Chapter 3. Natural Computing and Optimization Challenges in VANETs 3.4.2 Performance Indicators The performance evaluation is carried out by measuring the amount of computational resources used by the algorithm (computational effort), which are generally calculated as the computation time or as the number of solutions visited in the search space. It is widespread among the research community the combined use of both metrics in order to obtain realistic picture of the computational effort. Therefore, we have followed this advice in our research. We discuss here the main indicators used in the literature to evaluate the performance of parallel algorithms because this thesis includes studies applying parallel bio-inspired methods. Among all the metrics used, the most common ones used by the research community are the speedup and the efficiency. The speedup evaluates how much faster a parallel algorithm is than its corresponding sequential version. It is computed as the ratio of the execution times of the sequential algorithm (T1) and the parallel version executed on mcomputing elements (Tm) (Equation 3.14). When applied to non-deterministic algorithms, such as the NC ones applied in our works, the speedup should compare the mean values of the sequential and parallel execution times (Equation 3.15) (Alba and Tomassini, 2002). The ideal case for a parallel algorithm is to achieve linear speedup (Sm=m), but the most common situation is to achieve sublinear speedup (Sm< m), mainly due to the times required to communicate and synchronize the parallel processes. The efficiency is the normalized value of the speedup, regarding the number of computing elements used to execute a parallel algorithm (Equation 3.16). This metric allows the comparison of algorithms eventually executed in non-identical computing platforms. The linear speedup corresponds to em= 1, and in the most usual situations em<1. Sm=T1 Tm (3.14) Sm=E[T1] E[Tm](3.15) em=Sm m(3.16) 3.4.3 Statistical Analysis of the Results After the definition of the indicators of quality and performance, we now present the statistical analysis performed here to extract correct conclusions from the results. In this sense, a number of independent runs are carried out to obtain a set of values for each indicator. From the statistics viewpoint, these data can be considered as a sample from a probability density function, and therefore, they can be compared by means of statistical tests (Demšar, 2006; Sheskin, 2007), which are used to validate and to provide confidence to our empirical analysis . The procedure adopted in our research work is as follows (see Figure 3.4). First, a Kolmogorov-Smirnov statistical test is carried out to check whether the samples are normally distributed (Gaussian) or not. For normal distributions, the homoskedasticity (i.e., equality of variances) is checked using the Levene test. If the Levene test returns a positive value, an ANOVA test is performed; otherwise a Welch test is performed. For non-normal distributions, non-parametric test are performed,i.e., Kruskal-Wallis or Wilcoxon test (to compare two distributions) or Friedman Rank statistical test (to compare/rank more than two distributions). If Friedman test returns the rank with statistical confidence, post hoc statistical test can be performed by using Wilcoxon or Holm test to confirm the Friedman results. Chapter 3. Natural Computing and Optimization Challenges in VANETs 39 FIGURE 3.4: Statistical validation analysis process of the experimental results. The dictionary is the only place that success comes before work. Work is the key to success, and hard work can help you accomplish anything. VINCE LOMBARDI PART II: OPTIMIZATION AND EXPERIMENTATION IN VEHICULAR NETWORKS 41 Chapter 4 Off-line Optimization of Vehicular Communications THIS chapter analyzes the use of NC to automatically search for high-quality parameter settings of VANET protocols previous to its deployment. The search is performed by an off-line optimization process that couples NC with a VANET simulation procedure. This methodology is applied to improve the QoS of a file transfer and two routing protocols, as well as we analyze the optimization process of the routing energy-efficiency. In addition, we study different variations of the optimization algorithms to improve the performance of NC in solving off-line protocol optimization: extending the basic operators and devising new ones, parallelizing the used techniques, and defining multi-objective models of the problem. 4.1 Introduction VANETs present a set of special characteristics that negatively affect the quality of the communications (see Section 2.4), and therefore, that limit the accuracy of their applications. This could expose road users to hazardous situations (Benslimane, 2004). Thus, data dissemination in vehicular environments is a critical issue in today’s research. Hence, the research community is very active with hot topics, creating new protocols and improving the existent ones (Chen et al., 2011; Ding et al., 2011; Dua et al., 2014; Lee et al., 2010; Santa et al., 2009). A promising research line proposes the modification of competitive MANET communication protocols to adapt them to the special case of VANETs. One way to modify the protocols operation is by changing the values of the configuration parameters that govern them (timers, counters, etc.). This approach basically keeps the base same protocols but adapts them to new working environments. In this chapter, we propose the idea of improving the protocols software operation in VANETs by optimizing their configuration parameters. The protocol’s configuration parameters have a strongly non-linear relationship with each other and a complex influence on the final performance. In fact, they represent a mix of discrete plus continuous variables which makes it a hard challenge to find the best configuration in a real world vehicular environments. The performance evaluation of each protocol configuration requires a high number of VANET simulations that take in order of minutes each one. Thus, exact and enumerative methods are not applicable for solving the underlying optimization problem of finding the best configuration of a given protocol, because they require critically long execution times to perform the search, and because we are far from having a traditional analytic equation representing the protocol (to later optimize it). In this context NC is a promising approach to find accurate efficient protocol configurations in reasonable times. 43 44 Chapter 4. Off-line Optimization of Vehicular Communications Specifically, in this PhD thesis we propose a methodology to optimize VANET protocols by using NC. The procedure adopted in our analysis is summarized as follows: 1. analyzing the protocol operation and performance in VANETs in order to study the configuration parameters to be improved, 2. defining an optimization problem to automatically tune the protocol parameters according to all the possible feasible parameter configurations (search space) and a given set of performance metrics (e.g., QoS) to define the objective (fitness) function, 3. selecting the NC algorithms (as efficient search engines) that better fit the requirements of the defined optimization problem, 4. generating realistic VANET instances to evaluate the computed solutions/protocol configurations (simulating them and obtaining the performance metric values), 5. running the NC algorithms to compute accurate VANET protocol configurations that improve its performance in vehicular environments, 6. and comparing the parameterizations computed by NC against the state-of-the-art ones. Focusing on the optimization part, NC techniques are coupled with a a realistic VANET simulator, which is utilized to accurately evaluate the solutions (protocol parameterizations) computed by the NC algorithm. As shown in Figure 4.1, during the protocol optimization the NC algorithm performs the search operations and invokes the simulation process (VANET evaluation). After the simulation, the results are used to compute the fitness function that guides the search. FIGURE 4.1: Optimization strategy to optimize VANET protocols. Currently, OBUs are not highly energy constrained because they benefit from the vehicle’s electricity. Nevertheless, VANETs can involve other wireless devices such as smartphones, roadside units, and sensors, that are fed with batteries or other energy sources. Limiting the energy consumption in vehicular communications may help the use of green renewable energy sources as solar cells installed in the used wireless devices. A similar strategy utilized to improve the QoS of the VANET communication has been applied to reduce their energy consumption, thus finding energy-efficient protocol configurations. Therefore, in this chapter we address two main important issues in vehicular communications: the optimization of the QoS and the reduction of the energy consumption of the protocols. In other systems, this is an improvement or a twist for efficiency; however, in VANETs it is a mandatory step to get the communications actually working. In short, this chapter analyzes the optimization of the QoS of a file transfer and two types of routing protocols. We have selected two different types of routing protocols (a proactive one and a reactive one), which represent two different ways of operating, in order to show the robustness of the use of NC in this filed. In addition, it studies the energy-efficiency optimization of a routing protocol. Chapter 4. Off-line Optimization of Vehicular Communications 45 The chapter is organized as follows: Section 4.2 applies NC to the optimization of the QoS a file transfer protocol. Section 4.3 analyzes the use of NC on the optimization of a proactive routing software. Section 4.4 concentrates in how to reduce the energy consumption routing data by using a parallel NC algorithm. Section 4.5 improves the QoS of a reactive routing protocol by applying parallel multi-objective NC techniques. Finally, Section 4.6 offers a global vision on applying off-line optimization in VANETs. We now turn to present the common definitions required for all subsequent work of this chapter. 4.1.1 Instances for the Evaluation of VANET Communications The evaluation of vehicular communications is a major concern as it has already been discussed in Section 2.6. In this thesis it has been made a great effort to defined realistic VANET simulations in order to obtain accurate results, i.e., as close as possible to the real world communications. The simulation of communications used in our studies comprises the utilization of a widely used network simulator, the Network Simulator (two versions are used ns-2 and ns-3). This network simulator is combined with one of the following two road traffic simulators (mobility models generators) to define the movement of the nodes as real vehicles: the VanetMobiSim (Härri et al., 2011) and the Simulation of Urban MObility (SUMO) (Krajzewicz et al., 2012). The main advantage of employing traffic simulators is that they can be used to generate realistic VANET environments by automatically selecting real areas from freely available digital maps, e.g., OpenStreetMap (Haklay and Weber, 2008), taking into account real road directions, traffic lights and signs, etc. This section introduces the main characteristics of the road VANET instances used in the simulations performed in the studies presented in chapter. The off-line optimization take into account both, urban (metropolitan) and highway areas, because the vehicular communications behave quite differently in this two types of roads. For the urban scenarios, three different geographical area sizes have been selected from the downtown of Málaga, in Spain, to study the scalability of the approaches proposed. The three urban areas are the U1, the U2, and the U3 that cover areas of 120,000 m2, 240,000 m2, and 360,000 m2, respectively (see Figure 4.2). Additionally, the analysis is extended by studying how do various road traffic densities affect the protocols’ performance. a) U1 area. b) U2 area. c) U3 area. FIGURE 4.2: Road maps used to define the urban VANET instance. The highway instance covers a stretch of road of one kilometer with four lanes and two directions (two lanes per direction) without buildings and semaphores. In this case, the absence of obstacles is made up for the handicap of the high speed of vehicles, which also interferes the communication among vehicles. 52 Chapter 4. Off-line Optimization of Vehicular Communications Fitness Function The simulator evaluates the communications of a VANET scenario and returns the values for each QoS metric. As the vehicular communications depend on several external elements, e.g., distance between the vehicles, it is important to evaluate each solution averaging the results of different file transfers in order to provide the most accurate fitness value possible. In this study, each solution requires 10 different file transfers of the same VDTP parameterization (N= 10). The fitness value for each solution is defined as an aggregate function taking into account the three metrics (transmission_time,lost_packets, and data_transferred), as it is shown in Equation 4.12: fitness(s) = 1 N N X i=1 transmission_timei+lost_packetsi log(data_transferredi+K)(4.12) In this equation, i∈[1,10] is the number of the file transfer. The data transferred is presented in logarithmic scale in order to make up for the difference in the range of values. The factor K= 2 avoids division by negative values or zero, preventing a possible error in the fitness calculation. Thus, the analyzed NC algorithms minimize the fitness defined in Equation 4.12 to solve the FTC optimization problem. 4.2.4 Experimental Results This section presents the experiments carried out to solve FTC optimization problem on VDTP and discusses the main results. The NC algorithms used to optimize the QoS of VDTP are implemented using the C++ MALLBA framework (Alba et al., 2006). Instances: VANET Scenarios The FTC optimization problem analyzed here takes into account two different vehicular scenarios: an urban area and a highway road. Thus, we can analyze in both scenarios the behavior and performance of the compared algorithms. The Urban and the Highway instances utilized in this study are defined by the U1 urban area and Hhighway road, respectively (see Section 4.1.1). In both instances 30 vehicles are circulating with appropriate speeds according to the road and 20 of them are trying to send or receive files of 1024 kilobytes (KB). The communication devices of the utilized vehicles are configured using IEEE 802.11b, DSR, and UDP protocols for the PHY/MAC, routing, and transportation layers, respectively. García-Nieto et al. (2010) describes further details of the analyzed VANET instances. Parameter Settings of the Algorithms The five studied algorithms are configured to perform 1,000 solution evaluations per run. The swarm/population based NC techniques (PSO, DE, GA, and (µ, λ)-ES) are configured with 20 particles/individuals, performing 50 generational steps; and SA iterates 1,000 times. Table 4.1 summarizes the remaining parameters specific to each algorithm. These parameters are selected as the most accurate after a set of initial tuning experiments. In those, a number of five combinations of parameters per algorithm and VANET instance are tested performing only 10 independent runs per combination, hence resulting in a number of 500 additional executions. However, later for the actual study we use 30 independent runs since it is the minimum to compute meaningful statistical results. Preliminary results of parameters tuning are available in Table B.1 (see Appendix B). Chapter 4. Off-line Optimization of Vehicular Communications 53 TABLE 4.1: Parameterization of the optimization algorithms to address FTC problem. Algorithm Parameter Symbol Value Local Coefficient ϕ12.0 PSO Social Coefficient ϕ22.0 Inertia Weigh w0.5 DE Crossover Probability Cr 0.9 Mutation Factor µ0.1 GA Crossover Probability Pcros 0.8 Mutation Probability Pmut 0.2 ES Crossover Probability Pcros 0.9 Mutation Probability Pmut 0.1 SA Temperature Decay T0.8 Numerical Analysis This section discusses the results obtained by the five studied algorithms when solving the optimal FTC problem on VDTP. Table 4.2 shows the resulting fitness values regarding the Urban and Highway scenarios in terms of the average, the normalized standard deviation, the minimum (best fitness), the median, and the maximum (worst fitness) found in 30 independent runs of every algorithm. TABLE 4.2: Final fitness values of FTC optimization for the Urban and Highway scenarios. Instance Algorithm Average ±Stdev. Minimum Median Maximum PSO 1.6346 ±17.74 % 0.9077 1.7809 1.8918 DE 1.7423 ±21.33 % 0.7389 1.8658 2.0228 Urban GA 1.9086 ±11.84 % 0.8799 1.9731 2.1614 ES 2.1517 ±5.88 % 1.8862 2.1222 2.4246 SA 2.7850 ±31.30 % 0.8730 2.1663 3.8025 PSO 4.1761 ±6.12 % 3.3301 4.2513 4.4554 DE 4.6631 ±20.01 % 2.7145 4.2272 7.0531 Highway GA 4.3805 ±19.85 % 2.5345 4.1918 5.8608 ES 5.7833 ±16.78 % 3.8836 6.1347 6.9421 SA 4.4246 ±16.73 % 3.1498 4.0855 5.7922 For the Urban scenario, Table 4.2 shows that PSO obtains the best result in terms of the average, median, and maximum fitness values. This result leads us to believe that using the PSO the resulting VDTP ends in an efficient communication which is fast and accurate between vehicles. Howeverm the very best VDTP configuration (minimum fitness) is found for Urban is reached by DE, so if the robustness is not an issue we could use DE instead PSO. ES provides the smallest deviation (5.88 %) since the results obtained are close each other, but they are far from the best obtained ones by the other NC techniques. Similar results are observed for the Highway scenario, in which PSO obtains the best average fitness value again. In terms of the minimum fitness, GA obtains the best VDTP configurations for the Highway scenario. For this instance the least competitive NC technique is ES, i.e., it computes the highest (undesired) average, minimum, and median fitness values. In order to provide such comparison with statistical confidence, the Friedman and the Wilcoxon Signed Rank non-parametric statistical tests (Sheskin, 2007) are performed because the distributions violate the condition of normality required to apply parametric tests. For Urban instance, the algorithm that significantly obtains the best results is PSO according to Friedman and Wilcoxon tests. The second and third ranked algorithms by Friedman are DE and GA, 54 Chapter 4. Off-line Optimization of Vehicular Communications respectively. For Highway instance, there is not a clear trend about which one is statistically the algorithm that performs the best since Friedman ranked SA, GA, and PSO as first, second, and third best algorithms, but these three algorithms do not show statistical differences with each other. These statistical results lead us to think that, in spite of the global (robust, predicable) competitive behavior of PSO, the different requirements implicit to both instances implies that each algorithm can show quite different results depending on the VANET scenario on which it operates. The results of these statistical tests are detailed in tables B.3,B.4, and B.5 (see Appendix B). Algorithms Performance Analysis This section basically lies in analyzing the quality of solutions during the whole evolution process of a given NC technique. Figure 4.6 illustrates the graphs of the best fitness values obtained through the median execution in Urban and Highway instances. FIGURE 4.6: Best fitness evolution for the median run when solving FTC problem. In both figures PSO and DE tend to converge in the same range of solution evaluations, and they could improve their fitness even in the final steps of the evolution process. GA shows a similar trend but it is subjected to an early stagnation. Finally, the high variability behaviors observed in ES, and specifically in SA, for both instances confirm us the high dependency of such algorithms to each different VANET scenarios (they do not seem robust in this application). Execution Time Analysis Concerning the run time each algorithm spends in the experiments, Table 4.3 shows both the average time in which the best solution is found Tbest, and the total average execution time per run Trun. In general, SA shows the shortest times to find its best solution for the two VANET instances. This is mainly due to SA quickly falls in local optima hence obtaining weak results in Urban scenario. Nevertheless, this behavior can be an advantage for Highway scenario where SA obtained accurate solutions with a fast performance. Besides this algorithm requires less internal operations. As expected in PSO and DE, they spent close executions times for the two VANET instances since they have similar internal operations. This resemblance is also registered in the two evolutionary algorithms, GA and ES. As a summary, the algorithms use between 80 and 150 minutes for the Urban scenario, and between 23 and 60 minutes for Highway scenario. This global low effort in the protocol design is completely justified by the subsequent benefits obtained in the global data transmission time and loss of packets. Chapter 4. Off-line Optimization of Vehicular Communications 55 TABLE 4.3: Average execution times (seconds) per independent run of each algorithm in solving FTC. Instance Algorithm Tbest (seconds) Trun (seconds) PSO 4.68E+03 7.95E+03 DE 4.37E+03 7.12E+03 Urban GA 3.48E+03 6.68E+03 ES 5.46E+03 9.00E+03 SA 2.18E+03 4.76E+03 PSO 1.39E+03 2.19E+03 DE 9.82E+02 2.10E+03 Highway GA 8.83E+02 1.56E+03 ES 9.84E+02 1.47E+03 SA 5.85E+02 8.45E+02 Scalability Analysis In order to analyze how do various network sizes affect the performance of the NC techniques, they are executed over unseen two urban VANET instances: U2 and U3 (see Section 4.1.1) with 40 and 50 vehicles, respectively. Table B.2 in Appendix Bpresents the results of the whole scalability analysis out of 30 independent runs. From the point of view of the fitness obtained by each algorithm, PSO keeps the best performance for the two new instances. Additionally, one of the most interesting results can be observed in GA, which arises as the second best algorithm in improving its behavior with the VANET size. Concerning to the execution time, as expected, the run times always increase with the network size. 4.2.5 Efficient VDTP Validation After the optimization process, the configurations obtained by the NC algorithms are analyzed in terms of the QoS indicators (transmission time, number of lost packets, and amount of data transferred). Table 4.4 shows the results after simulating the best solutions found by the studied algorithms during the median run. In addition, the last row of this table contains the results of simulating the configuration of VDTP that has been used in the scope of the CARLINK project. The amount of data transferred is not shown because all the file transfers finished successfully, and therefore, for all the simulations the average data exchanged for each file transfer is 1,024 KB. TABLE 4.4: Comparison among different VDTP configurations (improved and CARLINK experts). Instance Algorithm VDTP Configuration Simulation Results chunk size retrans. time max. attempts trans. time (secs.) lost packets PSO 41,358 10.00 3 3.41 0.27 DE 28,278 6.00 9 3.59 0.63 Urban GA 31,196 3.83 9 3.61 0.27 ES 23,433 10.00 8 3.50 0.27 SA 19,756 6.43 3 4.22 0.36 CARLINK 25,600 8.00 8 4.24 1.60 PSO 29,257 6.42 9 24.67 3.18 DE 19,810 6.91 8 27.66 3.45 Highway GA 34,542 9.54 10 26.96 2.72 ES 38,490 8.15 12 33.99 3.36 SA 32,002 8.21 4 25.43 2.54 CARLINK 25,600 10.00 10 33.08 3.27 56 Chapter 4. Off-line Optimization of Vehicular Communications FIGURE 4.7: Final effective data rate (KB/s) of the analized VDTP configurations. For the Urban scenario, the VDTP configuration obtained by PSO achieves the best performance in terms of transmission time and average number of lost packets. Specifically, in comparison to the human experts configuration of CARLINK, PSO produces a reduction in the transmission time of 0.83 seconds (19.5%) registering also a lower number of lost packets. Nevertheless, it is in the Highway scenario where PSO obtains the higher time reduction of 8.41 seconds (25%) regarding the human experts configuration (from 33.08 s to 24.67 s). It is noticeable that, in spite that PSO achieves a higher reduction in the transmission time than SA and GA, the fact of losing more packets (3.18 in PSO, 2.71 in GA, and 2.54 in SA) in the global transference leads SA and GA to calculate a better fitness value (as shown in Table 4.2). A final analysis is done concerning the effective transmission data rate achieved. As we can see in Figure 4.7, the VDTP configuration obtained by practically all algorithms in the two VANET scenarios obtained higher effective data rates than the human configured VDTP. This clearly claims for the utilization of NC to help network designers. The actual correction of effective data rates between cars are in the order of tens of KB per second, so our savings (58.79 KB/s in Urban and 10.5 KB/s in Highway) are truly meaningful in current real applications. As a final comment, concerning to the effective transmission data rate observed in Figure 4.7, practically all the configurations obtained by the NC algorithms in the two VANET scenarios outperform the human configured VDTP. This clearly claims for the utilization of NC to help network designers. The actual correction of effective data rates are in the order of tenths of KB per second, which are truly meaningful in current real VANET applications. 4.2.6 General Discussion on File Transfer QoS Optimization This study demonstrates that the use of NC is a promising tool for the off-line optimization of the file transfer protocols in VANETs. PSO and GA provide competitive performance in finding accurate VDTP parameterizations for both, metropolitan and highway roads. These results keep competitive even when the simulated VANET grows, i.e., increasing the complexity of the vehicular environment. From the point of view of its real world utilization, PSO computed VDTP parameterizations reduce 19% of the transmission time in urban and 25.43% in highway with regards to human expert configuration of CARLINK, while transmitting the same amount of data. The highest effective data rates are obtained by PSO, which are 300.39 kBytes/s in urban VANETs and 41.50 kBytes/s in highway roads in comparison with 241.5 kBytes/s and 30.95 kBytes/s of human experts. The results lead us to advise the final use of our automatic design NC tool. These improvements in the protocol performance have been later confirmed in real world experiments by using real vehicles in an open road presented in Toutouh and Alba (2011c) (see Section 7.2). Chapter 4. Off-line Optimization of Vehicular Communications 57 4.3 Optimization of the QoS of Proactive Routing As it is introduced in Section 2.4, designing efficient routing protocols for VANETs is a serious challenge due to their unique and difficult features like decentralization, high mobility, and hard delay requirements. Thus, after dealing with the optimization of a file transfer protocol in the previous section, this study analyzes the use of NC algorithms to improve the QoS of the routing protocols used to perform vehicular communications. A new optimization problem is here defined to find efficient parameterizations of a proactive (table driven and link-state) routing protocol. Proactive protocols can be recognized because they maintain routing information even before they need this information. Each node stores paths to every node in the network. This information is generally kept in a number of routing tables and is periodically updated (with a given frequency or when a given destination node cannot be reached). Proactive protocols are applied in vehicular environments because they present a series of features that make them well-suited for VANETs (Huhtonen, 2004): they exhibit very competitive transmission delays (which is an important feature for VANET applications) and they adapt well to the continuous topology changes. The main drawback of such protocols is the need of maintaining the routing tables. This process is carried out by periodically broadcasting control packets to update routing tables. This drawback is negligible for scenarios with a few nodes, but for large networks the overhead of control messages could provoke network congestion. This constraints the scalability of this type of protocols. Thus, the QoS significantly depends on the selection of its parameters, what determine the protocol operation. For example, the detection of topological changes and the network load generated by the protocol can be adjusted by changing the time interval for broadcasting HELLO messages. In the present work, we aim at defining and solving an off-line optimization problem to efficiently and automatically tune OLSR (Clausen and Jacquet, 2003), a widely used mobile ad hoc network proactive routing protocol, in order to optimize its QoS when it is used in vehicular environments. As shown in the results presented in (Gómez et al., 2005; Huang et al., 2006; Härri et al., 2006) and in the present study, OLSR admits a wide range of QoS improvement by changing the configuration parameters. 4.3.1 OLSR Routing Protocol for VANETs OLSR is a proactive routing protocol designed for mobile ad hoc networks which show low bandwidth and high mobility. It is a version of classical link-state routing protocol, which relies in employing an efficient periodic flooding of control information using special nodes that act as multipoint relays (MPRs) (Nguyen and Minet, 2007). OLSR daemons running on every node of the network periodically exchange different messages in order to maintain the topology information of the entire network in the presence of mobility and failures. The core functionality is performed mainly by using three different types of messages: HELLO, TC (topology control), and MID (multiple interface declaration) messages. •HELLO messages are exchanged between neighbors nodes (1-hop distance). They are employed to accommodate for link sensing, neighborhood detection, and MPR selection. These messages are generated periodically, containing information about the links between neighbor nodes. •TC messages are generated periodically by MPRs to indicate which other nodes have selected it as their MPR. This information is stored in the topology information base of each network node which is used for routing table calculations. 58 Chapter 4. Off-line Optimization of Vehicular Communications •MID messages are sent by the nodes to report information about their network interfaces employed to participate in the network. Such information is needed since the nodes may have multiple interfaces with distinct addresses. The OLSR mechanisms are regulated by a set of parameters predefined in the OLSR RFC 3626 (Clausen and Jacquet, 2003) (see Table 4.5). These parameters have been already tuned by different authors without using any automatic tool in (Gómez et al., 2005; Huang et al., 2006) and they are: the timeouts before resending HELLO, MID, and TC messages (HELLO_INTERVAL,REFRESH_INTERVAL, and TC_INTERVAL, respectively); the “validity time” of the information received via these message types, which are: NEIGHB_HOLD_TIME (HELLO), MID_HOLD_TIME (MID), and TOP_HOLD_ TIME (TC); the WILLINGNESS of a node to act as a MPR (to carry and forward traffic to other nodes); and DUP_HOLD_TIME, that represents the time during which the MPRs record information about the forwarded packets. TABLE 4.5: Main OLSR parameters and RFC 3626 specified values. Parameter Type Range Standard configuration HELLO_INTERVAL R[1.0,30.0] 2.0 s REFRESH_INTERVAL R[1.0,30.0] 2.0 s TC_INTERVAL R[1.0,30.0] 5.0 s WILLINGNESS Z[0,7] 3 NEIGHB_HOLD_TIME R[3.0,100.0] 3×HELLO_INTERVAL TOP_HOLD_TIME R[3.0,100.0] 3×TC_INTERVAL MID_HOLD_TIME R[3.0,100.0] 3×TC_INTERVAL DUP_HOLD_TIME R[3.0,100.0] 30.0 s 4.3.2 OLSR QoS optimization in VANETs The standard configuration of OLSR offers a moderate performance when used in VANETs (Santa et al., 2009). Because of this high impact of parameters in the QoS of the protocol, an optimization problem is defined in order to discover the best protocol configuration. The standard OLSR parameters are defined without clear values for their ranges. The range of values each parameter can take has been defined here by following OLSR restrictions with the aim of avoiding pointless configurations. According to that, we can use the OLSR parameters to define a solution vector of mixed integer and real variables, each one representing a given OLSR parameter. This way, the solution vector can be fine-tuned automatically by using NC with the aim of obtaining QoS efficient OLSR parameters configurations for VANETs hopefully outperforming the standard one defined in the RFC 3626. The OLSR QoS optimization problem analyzed here takes into account three metrics that evaluate the communication cost: PDR, NRL, and E2ED. Thus, the problem consist in finding the OLSR configuration that maximizes PDR and minimizes both, NRL and E2ED. 4.3.3 Implementation Details As it happened with the precedent FTC problem, there are not previous results of optimizing the QoS of OLSR for comparisons. Therefore, four NC algorithms are analyzed: PSO, DE, GA, and SA. These techniques are selected because they craft operators for real parameter optimization and represent a subset with heterogeneous schemes for search. In addition, a random search algorithm (RAND) is studied for comparison purposes. The main strategy used in this analysis is summarized in Figure 4.8. The NC algorithm iteratively computes solutions of (hopefully) larger QoS. The simulator evaluates the communication costs of the received OLSR parameterization (tentative solution) by using ns-2. After Chapter 4. Off-line Optimization of Vehicular Communications 59 the simulation procedure ns-2 returns the values of PDR, NRL, and E2ED to compute the fitness value, and then, the algorithms can go for a new improvement iteration. FIGURE 4.8: Strategy to address OLSR QoS optimization. Our NC algorithms will use standard operations. Let us now explain the problem encoding and the fitness function utilized to evaluate the solutions. Problem Encoding As OLSR is governed by eight configuration parameters, thus the solution is encoded as a vector of eight components. The type and valid ranges for the parameter values are presented in Table 4.5. Figure 4.9 shows a representation of of this vector. FIGURE 4.9: Solution encoding for the QoS OLSR tuning optimization problem. Fitness Function The simulator evaluates the communications of a given VANET under the circumstances defined by the OLSR routing parameters generated by the optimization algorithm. After the simulation, ns-2 returns information about the PDR, NRL, and E2ED of the whole VANET. This information is used in turn to compute the fitness value of the current solution as follows: fitness(s) = w2·NRL(s) + w3·E2ED(s)−w1·P DR(s)(4.13) As previously set, the objective here consists in maximizing PDR, and minimizing both, NRL and E2ED. As expressed in Equation 4.13, an aggregative minimizing function is used, and for this reason PDR is formulated with a negative sign. In this equation, factors w1,w2, and w3are in the range [0,1] and must sum up to 1.0, with actual values 0.5,0.2, and 0.3, respectively, in our forthcoming experimental analysis. This way, routing effectiveness (PDR) takes priority over the communication efficiency (NRL and E2ED). 60 Chapter 4. Off-line Optimization of Vehicular Communications 4.3.4 Experimental Results This section presents and analyzes the experiments carried out to solve optimization problem on OLSR to improve its QoS in VANETs. The NC algorithms applied to tackle the OLSR QoS optimization problem (PSO, DE, GA, and SA) are implemented in the C++ MALLBA framework. VANET Instance for Fitness Computations The VANET instance evaluated to compute the fitness function of the tentative OLSR configurations is defined over the previously defined U1 urban area. This scenario contains 30 vehicles moving through the roads during three minutes. The vehicles exchange data created by a constant bit rate data generator (CBR) application. Toutouh et al. (2012b) describes all the details of the used VANET. Parameter Settings of the Algorithms The studied five optimization algorithms are executed to reach the same stop condition (1,000 fitness function evaluations) in order to compare them. SA and RAND performs 1,000 iteration steps, and population/swarm based algorithms perform 100 generations with populations of 10 individuals/particles (100×10=1,000) each one of them. The main parameters of these algorithms are summarized in Table 4.6. TABLE 4.6: Parameterization of the optimization algorithms to address OLSR QoS tuning problem. Algorithm Parameter Symbol Value Local Coefficient ϕ12.00 PSO Social Coefficient ϕ22.00 Inertia Weigh w0.50 DE Crossover Probability Cr 0.90 Mutation Factor µ0.10 GA Crossover Probability Pcros 0.80 Mutation Probability Pmut 0.01 SA Temperature Decay T0.80 Numerical Analysis This section discusses the results obtained by the five studied algorithms when solving the QoS OLSR optimization problem. Table 4.7 shows the average and the normalized standard deviation of the fitness values obtained (out of 30 independent executions). The best (minimum), median, and worst (maximum) values are also provided. TABLE 4.7: Results obtained in the OLSR QoS optimization. Algorithm Average ±Stdev. Minimum Median Maximum Friedman rank. KW (p-value) SA -0.450297±5.32% -0.478242 -0.457451 -0.406932 1.40 3.0591E-6 DE -0.436897±6.86% -0.480030 -0.435264 -0.392578 2.10 3.0660E-6 PSO -0.432240±7.93% -0.482343 -0.419734 -0.392503 2.50 3.0669E-6 GA -0.350837±6.55% -0.437241 -0.344612 -0.327281 4.33 3.1592E-6 RAND -0.329878±15.16% -0.410131 -0.329792 -0.217024 4.50 3.3579E-6 SA outperforms all other algorithms in terms of average, median, and worst fitness values. According to these measures, SA is followed by DE, PSO, and GA, respectively. Nevertheless, Chapter 4. Off-line Optimization of Vehicular Communications 61 the best (minimum) fitness is computed by the PSO which is the algorithm that obtained the best performance in optimizing VDTP (see Section 4.2.2). Finally, as expected, the random search algorithm is the least competitive one. With the aim of providing these comparisons with statistical confidence, the Friedman and the Kruskal-Wallis tests (Sheskin, 2007) are applied to the distributions of the results. These non-parametric tests are utilized since the resulting distributions often violate the conditions of equality of variances (heteroskedasticity) several times. The confidence level is set to 99% (p-value=0.01). In effect, confirming the previous observations, the results of Friedman test ranked SA as the algorithm with the best global performance followed by DE, PSO, and GA, respectively (see sixth column of Table 4.7). Moreover, the multicompare test of Kruskal-Wallis resulted in p-values 0.01 (see last column of Table 4.7). Therefore, we can claim that all the compared algorithms obtained statistically different results. Algorithms Performance Analysis This section presents the evolution of the quality of the solutions during the optimization process. Figure 4.10 plots the best fitness value tracked throughout the best run for each algorithm. As the figure illustrates, DE, PSO, and SA converge into the same range of solutions. But their evolution is different. SA, the best ranked algorithm, performs several gradual improvements of its solution during the whole execution. FIGURE 4.10: Best fitness evolution solving the QoS OLSR optimization problem. Execution Time Analysis Concerning the run time that each algorithm spent in the experiments, Table 4.8 shows the average time in which the best solution is found Tbest and the average total run time Trun, which is between 12.11 and 32.66 hours. GA shows the shortest time (2.04E+04 s) to find its best solutions. It seems that this algorithm quickly falls in local optima, hence obtaining weak results (see Table 4.7). PSO needs the second shortest time (3.05E+04 s) to compute its optima. Finally, SA takes the longest time (5.78E+04 s) to find its best solutions because it performs fitness improvements during the whole execution, as Figure 4.10 illustrates. Regarding total run time (Trun), random search takes shorter times (4.36E+04 s) than the other algorithms since it has less internal operations. PSO is the NC technique that spends shortest mean running time (5.38E+04 s) followed by DE, SA, and GA, respectively. 68 Chapter 4. Off-line Optimization of Vehicular Communications Computational Efficiency Analysis This section discusses the speedup (Sm) and the computational efficiency (em) computed according to the equations 3.15 and 3.16 presented in Chapter 3. Table 4.12 shows the average and best run times, and the values of the speedup and efficiency the pGAs when using 8, 16, and 24 threads. These results suggest that significant reductions in the required run times are obtained when using the parallel implementations with respect to a sequential version. TABLE 4.12: Performance comparison of the proposed pGAs (computational cost and efficiency). Algorithm Execution time (s) Speedup Efficiency Average Best Average Best Average Best pGA-8, 8 threads 11113.73 9235.71 5.80 6.86 0.72 0.86 pGA-16, 16 threads 13192.70 12440.05 11.81 12.63 0.74 0.79 pGA-24, 24 threads 20239.02 13670.90 19.10 20.12 0.80 0.84 The results in Table 4.12 demonstrate that the proposed master-slave model is a useful choice to significantly reduce the execution times of the pGAs. Despite following a synchronous paradigm (that tends to generate idle times due to the synchronization of the execution threads), the parallel GAs show an almost-linear speedup behavior. The average efficiency values obtained are greater than 70% for the three implementations studied, and a maximum average of 80% is achieved when using the pGA-24. 4.4.4 Power Aware OLSR Validation In order to confirm the efficacy of the results obtained in the experimental analysis, a set of validation experiments are conducted to compare the performance of the best OLSR configurations found using each pGA against the standard OLSR (RFC) configuration. The validation experiments involved simulations performed over 36 different urban VANET scenarios, which comprise the simulation of three different road traffic densities defined in the U2 and the U3 areas and six different types of applications (three traffic densities ×two urban areas ×six applications =36). The definition of the simulation environment is detailed in Toutouh et al. (2013). This analysis evaluates the energy consumption in transmitting (Esend) and receiving (Erecv) modes, as well as the total energy (Etotal) and total energy per vehicle (Etot×v). Additionally, the non-parametric Friedman statistical test is performed over the energy-efficient results. The PDR, the NRL, the E2ED, and the RPL are also included in the study. The results of the whole validation experimentation are included in tables B.10 and B.11 in Appendix B. TABLE 4.13: Results of the validation experiments of the power-aware OLSR. Config. Friedman Energy metrics QoS metrics rank. Esent Erecv Etotal Etot×vPDR E2ED NRL hops pGA-24 1.92 13012.84 5928.54 18941.37 527.51 59.22% 269.33 3.45% 1.46 pGA-16 1.94 13383.40 6163.63 19547.03 547.34 60.64% 274.34 3.63% 1.46 pGA8 2.94 13390.95 6147.99 19538.93 547.67 58.64% 283.85 3.67% 1.54 RFC 3.94 19572.25 12102.03 31674.29 877.33 67.89% 506.26 25.22% 1.20 Table 4.13 summarizes the experimental results by showing the Friedman ranking and the average values for each metric (the best values are marked in bold). According to these results, significant reductions are obtained when using the OLSR parameterizations computed by using the three pGAs. The configuration found by the pGA-24 is the most efficient parameterization for OLSR in VANETs (first ranked by Friedman), allowing a reduction of up to 40.2% in the power consumption. Figure 4.12 illustrates the GAP of energy regarding the dimension of the simulated scenarios. Chapter 4. Off-line Optimization of Vehicular Communications 69 FIGURE 4.12: GAP of energy of the energy-efficient OLSR regarding the scenario dimension. The results in Figure 4.12 demonstrate that significant improvements in the power consumption are obtained when using the configuration found with pGAs. In addition, the energy reductions with respect to the standard RFC configuration increase for the largest scenarios. The configuration found by pGA-24 achieved up to 44.4% of improvement in average for the largest scenarios. These notable improvements confirm previous claims about the inefficiency of the standard OLSR configuration in large VANET scenarios with high traffic density, already suggested by previous experimental evaluations (De Rango et al., 2008). All the previous results demonstrate the efficacy of the proposed NC methodology to compute accurate energy-aware OLSR configurations. The energy-efficient OLSR parameterizations, in addition to obtain high power savings, reduce extremely the routing overhead (NRL) and the communication delays (E2ED). These results are obtained without suffering large reductions in the PDR (<8 %) or increments in the length of the routing paths. This is an acceptable value for the loss in the QoS, when taking into account the important advantages achieved. 4.4.5 General Discussion on Power-Aware Routing The proposed improvement in the use of NC techniques to deal with routing optimization in VANET, i.e., the use of parallelism, provided an almost-linear speedup, obtaining efficiency values greater than 80%. This allowed the parallel GAs presented here to outperform the energy-efficiency of the previous power-aware routing approaches using classic NC algorithms. The average energy reductions achieved by pGA-24 are up to 40.2%, in contrast to the 30% and the 33% obtained in Toutouh and Alba (2011a) and in Toutouh and Alba (2015b), respectively; keeping a higher PDR. Also, significantly better energy savings (up to 77.54%) are computed for large and dense VANET scenarios. In addition, the energy-aware OLSR configuration found in this study significantly reduces the network overload and communication delays. All these important features are obtained while only suffering a bounded PDR degradation (less than 8%), what means a promising result for real applications. 4.5 Efficient QoS for Reactive Data Routing for VANETs Reactive or on-demand routing protocols have been also analyzed to be used in VANETs (Chauhan and Dahiya, 2012; Ding et al., 2011). The main difference between reactive and proactive protocols is that the first ones determine routing paths only when there is any data to send and the second ones attempt to maintain routes to all destinations at all time. Therefore, reactive routing protocols can be considered as the flip-side of the proactive ones. 70 Chapter 4. Off-line Optimization of Vehicular Communications In reactive protocols, as AODV, if a node wants to start a communication with another node to which the route is unknown, it initiates a global search procedure to find the destination. This operation is based on classical flooding search algorithms. Indeed, a routing request message (RREQ) is flooded to other nodes. Neighbor nodes which do not know an active route for the requested destination forward the RREQ packet to their neighbors, until an active route is found or the maximum number of hops is reached. When the RREQ reaches the destination or intermediate node with a valid route entry to the destination, a route reply message (RREP) is sent back in a unicast manner to the requester node. Figure 4.13 summarizes this procedure (AODV operation). a) Route request packet delivery. b) Route reply packet delivery. FIGURE 4.13: AODV route discovery procedure. The main advantage of reactive protocols is that they generate less overhead and provide more reliable routing than proactive ones, but at the (long delay) cost of finding the optimal route. In turn, nodes do not utilize periodic messages, with a consequent energy advantage in battery consumption (De Rango et al., 2008). Specifically, this study analyzes the optimization of the QoS of a reactive protocol (AODV) in VANETs, because, as it happens with the other protocols analyzed before, its performance can be improved by finding parameterizations better adapted to vehicular communications. Here, we focus on the optimization of two important aspects in VANET communications: the reliability and communication delays. This is principally due to the competitive performance of this protocol in terms of overhead generated. This protocol has been optimized previously in different studies. A preliminary study presented by García-Nieto and Alba (2010) applied several sequential mono-objective NC techniques to the optimization AODV obtaining promising results. In turn, a parallel PSO (pPSO) was also analyzed in dealing with this problem, outperforming the classic PSO (Toutouh and Alba, 2012c). Recently, Said and Nakamura (2014) proposed an asynchronous pEA to tackle the optimization of the same protocol. All these previous studies defined the AODV QoS optimization problem as a monoobjective optimization problem, therefore, they obtained a single solution. In contrast, here, the problem is defined as a multi-objective optimization one, thus obtaining a set of accurate solutions that offer different trade-offs between the objectives. 4.5.1 AODV Routing Protocol for VANETs AODV (Perkins et al., 2003) is a reactive distance vector (on-demand) routing protocol for mobile ad hoc networks designed to overcome the overhead problem of its precedent, DSDV. As a reactive protocol, AODV determines the routes when a source node has data traffic to send, and it maintains just the paths that are currently in use. Thus, it reduces the routing overload generated by proactive routing protocols to maintain the routing paths at any Chapter 4. Off-line Optimization of Vehicular Communications 71 time. The operation shown in Figure 4.13 and the performance of AODV are significantly influenced by the value of its 11 main control parameters that can be grouped in: (1) five timeout timers: HELLO_INTERVAL,ACTIVE_ROUTE_TIMEOUT,MY_ROUTE_TIMEOUT, NODE_TRAVERSAL_TIME, and MAX_RREQ_TIMEOUT; (2) three decision variables used in the process of updating and maintaining the routing tables: NET_DIAMETER,ALLOWED_HELLO_LOSS, and REQ_RETRIES; and (3) three counters and decision variables that control the process of discovering new routing paths: TTL_START,TTL _INCREMENT, and TTL_THRES-HOLD. The AODV RFC 3561 suggests a generic MANET parameterization (see Table 4.14) that has been also used in vehicular networks (Chauhan and Dahiya, 2012). TABLE 4.14: Main AODV parameters and RFC 3561 specified values. Parameter Type Range Standard configuration HELLO_INTERVAL R[1.0, 20.0] 1.0 s ACTIVE_ROUTE_TIMEOUT R[1.0, 20.0] 3.0 s MY_ROUTE_TIMEOUT R[1.0, 40.0] 6.0 s NODE_TRAVERSAL_TIME R[0.01, 15.0] 0.040 s MAX_RREQ_TIMEOUT R[1.0, 100.0] 10.0 s NET_DIAMETER Z[3, 100] 35 ALLOWED_HELLO_LOSS Z[0, 20] 2 REQ_RETRIES Z[0, 20] 2 TTL_START Z[1, 40] 1 TTL_INCREMENT Z[1, 20] 2 TTL_THRESHOLD Z[1, 60] 7 4.5.2 Multi-objective AODV Optimization in VANETs AODV provides moderate QoS when it is used in vehicular communications, although the low routing load generated by reactive protocols makes it scalable to be used in large VANETs. This analysis is aimed at improving the reliability, evaluated in terms of PDR, and the communication delays (E2ED). Therefore, the main idea is to find configuration parameters that maximize the PDR and minimize the E2ED. However, E2ED increases critically with PDR. This is principally because the possibility of collisions increases with the number of the packets traveling through the network: the nodes take longer to relay/send the packets. The opposite occurs when decreasing PDR. Thus, a multi-objective (MO) optimization problem is defined with the aim of discovering a set of efficient AODV parameters based on their performance in terms of PDR and E2ED. This problem is named AODV multi-objective QoS optimization (AODV MO-QoS). 4.5.3 Implementation Details The AODV MO-QoS problem is treated by using two different multi-objective algorithms (MOAs): a multi-objective evolutionary algorithm, the Non-dominated Sorting Genetic Algorithm-II (NSGA-II) (Deb et al., 2002), and a multi-objective swarm optimization method, the Speed-constrained Multi-objective PSO (SMPSO) (Nebro et al., 2009). The competitive computational efficiency of the parallel NC algorithms in solving off-line optimization of protocols in vehicular communications (Toutouh and Alba, 2012c; Toutouh et al., 2013; Said and Nakamura, 2014) motivated the use of parallel implementations of the two utilized MOAs (pMOAs). The application of pMOAs mitigates the main issues of most precious work in optimizing VANET routing (Patil and Dhage, 2013; Toutouh et al., 2012b; Zukarnain et al., 2014), which are: i) the use of single-objective methods to optimize an aggregated objective function, obtaining a single biased solution, and ii) the relatively low number of fitness evaluations carried out during the search process due to the high computational costs of the VANET simulations, needed to perform such an operation. 72 Chapter 4. Off-line Optimization of Vehicular Communications Figure 4.14.a summarizes the operation of the two analyzed pMOAs, in which the master process performs most of operations of NSGA-II or SMPSO and the nslave processing units carry out the solution evaluation. The slave process is showed in Figure 4.14.b: it receives a given solution s(AODV configuration), which is simulated, and it returns the evaluation of the objective functions regarding to PDR and E2ED. a) Global master-slave methodology. b) Details of how one slave process performs solution evaluation of f1and f2objective functions. FIGURE 4.14: Methodology applied to solve the MO-AODV problem. Problem Encoding As AODV is governed by 11 configuration parameters, the solution is encoded as a vector of 11 components. The valid ranges for each one of the parameter values are presented in Table 4.14. Figure 4.15 illustrates a representation of of this vector. FIGURE 4.15: Solution encoding for the QoS AODV tuning problem. Multi-objective Solution Evaluation This study focuses on maximizing the PDR and minimizing the E2ED of AODV in VANETs. Thus, a multi-objective optimization problem (MOP) is defined (the multi-objective AODV MO-QoS problem) in which there are two objectives to be optimized, that are defined by two fitness functions (f1(s)and f2(s)). The fitness functions are evaluated after performing a VANET simulation configuring AODV with a given sparameterization. The f1(s)function is given by the expression in Equation 4.17, in which PDR(s)is the average PDR achieved by all the VANET nodes. As PDR(s) is a value from 0 to 100 (100 is the value achieved when all the data packets are delivered), then f1(s)∈[0,100]. The idea is that the problem of maximizing PDR has been changed to a problem of minimizing f1(s)to ease the representation. The f2(s)function evaluates the E2ED(s) which is the average delivery time of all the data packets (see Equation 4.18). Thus, f2(s)has to also be minimized. The E2ED time is given in milliseconds (ms). Therefore, the AODV MO QoS optimization problem is given by minimizing f1(s)and f2(s). Chapter 4. Off-line Optimization of Vehicular Communications 73 f1(s) = 100 −PDR(s)(4.17) f2(s) = E2ED(s)(4.18) Parallel Multi-objective Operators The two NC algorithms utilize the diagonal uniform initialization. The diversity is introduced by applying the arithmetic recombination and the AODV-µmutation operators, in the case of the parallel NSGA-II (pNSGA-II), and the AODV-µmutation operator, in the case of parallel SMPSO (pSMPSO). The operators are defined in Section 4.1.3. 4.5.4 Experimental Results The experiments carried out to solve the AODV MO-QoS optimization problem are presented in this section. The pMOAs are implemented using jMetalCpp framework (Durillo and Nebro, 2011) and the standard pthread library. The experimental analysis is done in a cluster with Opteron 6172 Magni-Core at 2.1 GHz with 24 GB RAM. VANET Instance for Fitness Computations In this study, the U2 urban VANET scenario with 30 vehicles moving along the roads during three minutes is used for fitness functions computations (ns-2 simulations). In this scenario there are 15 nodes transmitting data at 256 kilobits per second (kbps) during one minute. Toutouh and Alba (2015c) details this VANET instance. Parameter Settings of the Parallel NC Algorithms A parameter settings initial analysis is performed to set the crossover (pC) and mutation (pM) probabilities of the pNSGA-II and the mutation probability (pM) of pSMPSO. The experiments are carried out on both pMOAs with a population/swarm size of 24 solutions (24 threads) stopping after 300 generations. The candidate values for the parameters are for pC: {0.3, 0.5, 0.7, 0.9}; and for pM: { 1 4L,1 2L,1 L,1 0.5L} being Lthe number of components of the solution vector (L= 11). Each configuration of each algorithm is independently executed ten times and the hypervolume IHV metric (Deb, 2001) is compared among different configurations of the same algorithm. Table B.12 in Appendix Bshows the results for the parameterizations of the algorithms analyzed here. The best results are obtained configuring pNSGA-II by using pC=0.9, pM=1 4L=0.023, while pSMPSO with pM=1 L=0.091. Defining an Empirical Stop Criterion In order to compare both analyzed algorithms the stop criterion is set as obtaining a Pareto front with a given quality in terms of the hypervolume value. As the AODV MO-QoS is a new and open problem, no optimal Pareto front is known. Therefore, some initial experimentation is performed to compute an approximated Pareto front to later evaluate the hypervolume during the execution of the algorithms when solving the problem. These initial runs stop after computing 450 generations. The union set of all non-dominated solutions computed for both algorithms is considered as the optimized Pareto front. The median hypervolume computed by all the runs is 0.785. Thus, the stop criterion applied is, first, achieving a hypervolume value equal or higher than 0.785, or second, performing a given maximum number of generations. Numerical Analysis This section compares the performance of the two NC algorithms studied on the optimization of the QoS of AODV in VANETs after performing 30 independent runs of each method. 74 Chapter 4. Off-line Optimization of Vehicular Communications The comparison of the Pareto fronts approximations are carried out in terms of epsilon (I) and spread (I∆) values (Deb, 2001). The hypervolume is not used because it is used as stop criterion and there is not a significant difference between the two pMOAs in this metric (see Figure 4.16). In order to determine the significance of the comparisons, Wilcoxon statistical test with a confidence level of 99% (p-value<0.01) is applied to compare each metric because they are not normally distributed. Table 4.15 shows the minimum (Min), median (Med), and maximum (Max) values obtained for each metric and algorithm. Please, note that the minimum hypervolume values obtained by each algorithm (0.772 by pNSGA-II and 0.777 by pSMPSO) are lower than 0.785 (the threshold value used as the stop criterion). This occurs because four independent runs have not achieved such hypervolume value and they stopped when they performed the maximum number of generations (450). TABLE 4.15: AODV MO-QoS experimental results. Metric pNSGA-II pSMPSO Min Med Max Min Med Max IHV 0.772 0.786 0.791 0.777 0.786 0.799 I1.741 2.634 3.949 2.195 2.807 4.493 I∆0.511 0.619 0.953 0.603 0.706 0.911 FIGURE 4.16: Quality metrics of the Pareto fronts computed in solving AODV MO-QoS. The epsilon values of pNSGA-II are in general better (lower) than the ones computed by pSMPSO (see Figure 4.16 and Table 4.15). Therefore the convergence of pNSGA-II is more competitive than the one of pSMPSO. The spread values achieved by the pNSGA-II computed Pareto fronts are also better (lower) than the ones obtained by pSMPSO. Thus, the diversity of the pNSGA-II fronts is better than the ones computed by pSMPSO. These results are confirmed by the Wilcoxon test results because the p-values computed are 0.0036 and 0.0024 for epsilon and spread, respectively. Figure 4.17 illustrates two Pareto fronts obtained by each pMOA and the optimized Pareto front (the complete fronts in the left and a zoom of a given region of the shown fronts in the right). The selected Pareto fronts are the ones that obtain the median hypervolume value for each algorithm. The pNSGA-II solutions are better distributed among the optimized Pareto front (see Figure 4.17.a). The pSMPSO front does not contain solutions that best minimize f1(s)(maximize PDR), while it has solutions that sharply reduce the E2ED times and critically worsen the PDR. Figure 4.17.b shows that most of pNSGA-II solutions dominate the ones computed by pSMPSO. This confirms the aforementioned results that concluded that pNSGAII presents the best performance when the hypervolume is set as the stop criterion for solving AODV MO-QoS problem. Chapter 4. Off-line Optimization of Vehicular Communications 75 a) Complete Pareto fronts of median run. b) Detail of Pareto fronts of median run. FIGURE 4.17: Pareto fronts computed when solving AODV MO-QoS. Computational Efficiency Analysis This section evaluates the performance of parallel algorithms in terms of speedup and computational efficiency according to equations 3.15 and 3.16 presented in Chapter 3(see Table 4.16). Both algorithms, NSGA-II and SMPSO (with the same configurations as the pMOAs) are executed sequentially to compute E[T1](the run time of the one-thread version). As the average execution times of these sequential versions of NSGA-II and SMPSO are 94.5 hours (3.9 days) and 173.1 hours (7.2 days), respectively, we were bound to perform just 10 independent runs of each algorithm due to the limited access to the computational platform (and the large number of tests done for the rest of this research work). TABLE 4.16: Performance comparison of the proposed pMOAs in solving AODV MO-QoS. Algorithm E[T24]E[T1]Speedup Efficiency pNSGA-II 311.737 5668.040 21.614 0.901 pSMPSO 422.190 10383.449 20.829 0.868 As it happened in the analysis performed in Section 4.4, in the proposed pMOAs, the evaluation of the fitness function is the most consuming part within the algorithm, since the ns-2 simulations demand large computation costs. The results in Table 4.16 demonstrate that the proposed master-slave model is a successful choice to significantly improve the efficiency of the multi-objective metaheuristic algorithms analyzed in this study. The speedup values are larger than 20.8, obtaining highly satisfactory efficiency values both for pNSGA-II (90.1%) and pSMPSO (86.8%). 4.5.5 Improved AODV Validation A set of validation experiments are carried out to confirm the real applicability of our proposal. Thus, a representative solution (AODV configuration) obtained by each pMOA is compared against other state-of-the-art ones, which are: the standard AODV RFC 3651 (RFC), the one proposed in García-Nieto and Alba (2010) found applying a PSO (GN), and the one tuned using a pPSO (pPSO) proposed in Toutouh and Alba (2012c). The solutions selected as the representative one of each pMOA are the ones that minimize the distance to the ideal vector (Coello et al., 2007). Table B.13 in Appendix Bpresents these configurations. However, one of the most important advantages of using multi-objective NC techniques is that they return a set of accurate solutions (configurations), which offer different trade-offs between the objectives. Thus, these configurations may be selected according to the actual conditions of the VANET. 76 Chapter 4. Off-line Optimization of Vehicular Communications The comparison is carried out taking into account 30 VANET scenarios defined in the three urban areas defined in Section 4.1.1. These scenarios comprise ten urban VANET traffic conditions and three different applications. Toutouh and Alba (2015c) details these urban VANET scenarios. Table 4.17 summarizes the results by showing the median PDR and E2ED for the whole experimentation (Table B.14 presents the whole experimentation results). The best results are marked in bold. Moreover, Friedman Rank statistical test is applied because the results are not normally distributed. The confidence level is set to 99% (p-value=0.01). The statistical test results are presented in Table 4.18. TABLE 4.17: Median values of the whole AODV validation experiments. configurations PDR (%) E2ED (ms) RFC 64.510 59.787 pPSO 59.269 17.183 GN 59.787 10.753 pNSGA-II 67.015 97.206 pSMPSO 69.203 65.681 TABLE 4.18: Friedman Rank test results of the AODV validation experiments. PDR E2ED Configs. Rank Configs. Rank pSMPSO 3.93 GN 1.53 pNSGA-II 3.50 pPSO 1.87 RFC 3.20 RFC 3.40 pPSO 2.47 pSMPSO 3.60 GN 1.90 pNSGA-II 4.60 Concerning the PDR results, the best median values are: first pSMPSO, second pNSGA-II, and third RFC. The results of the statistical test in Table 4.18 confirm that these three configurations are the best ranked ones and in the same order. Regarding the times required to delivery the packets (E2ED), the configurations obtained by the single-objective algorithms (GN and pPSO) obtain the best results for the analyzed scenarios. The Friedman Rank statistical test confirms these results, because the test ranked GN as the first and pPSO as the second best configurations. Comparing just the configurations obtained by the pMOAs, pSMPSO performed better than pNSGA-II. In short, the selected solution to represent pMOAs in the validation experiments provided the best PDR results, while they suffered from slightly longer E2ED. Moreover, taking into account just pMOAs solutions, the pSMPSO solution performed the best. 4.5.6 General Discussion on Efficient MO-QoS Optimization This last research work has been motivated by the need of a deep experimentation in off-line optimization in VANETs with NC algorithms. In this sense, the problem has been formulated as a multi-objective optimization problem with the aim of maximizing the PDR and minimizing the E2ED. The problem has been addressed by using two pMOAs that perform the search with high competitive results from the point of view of parallelism (computational efficiency is 86.8% for pSMPSO and 90.1% for pNSGA-II). The AODV configurations computed by the pMOAs improve the PDR obtained by the other tstate-of-the-art AODV parameterizations (the standard AODV RFC and two improved ones by using other NC algorithms), while not leading to a degradation of the other network performance metrics. However, other solutions (AODV configurations) in the optimized Pareto front may offer different trade-off of QoS metrics. Analyzing the optimization process, pNSGA-II significantly outperformed pSMPSO in terms of diversity (spread) and convergence (epsilon) in solving AODV MO-QoS optimization problem. In addition, pNSGA-II required lower computation costs: fewer generations and shorter run times. Chapter 4. Off-line Optimization of Vehicular Communications 77 4.6 Conclusions This chapter has analyzed the application of NC algorithms for the off-line optimization of VANET software communication protocols. The works carried out in this research are a key part of the thesis presented here. For this reason, we have presented the design of algorithms, their implementations, initial results (with previous parameterization studies), validation other scenarios and extended comparisons. The off-line optimization requires the joint implementation of a NC algorithm and a realistic VANET simulation. Thus, we have included experimentation and analysis in order to improve the state-of-the-art approaches in both aspects: defining competitive search algorithms and providing new and realistic VANET scenarios for accurate simulation. We have focused on the optimization of a file transfer (VDTP) and two routing protocols (OLSR and AODV). However, nothing prevents the use of the techniques presented here to optimize other kinds of VANET protocols. The parameter configurations tuned by using NC better fit vehicular environments, and therefore, they improve the state-of-the-art ones in terms of QoS and energy-efficiency. Analyzing the VDTP QoS optimization by applying PSO, DE, GA, ES, and SA; we conclude that the communication configurations offered by PSO increased the effective data rate of the human expert configuration from 243 KB/s to 300 KB/s and from 31 KB/s to 42 KB/s in urban and highway roads, respectively. In addition, the NC algorithms applied demonstrated a high scalability in dealing with the problem. Regarding the optimization of the QoS of OLSR by using a set of sequential NC algorithms, the computed accurate protocol configurations outperformed other state-of-the-art ones. They showed high PDRs (>84%), they generated much smaller routing overhead than the standard OLSR, and they reduced the delivery times. Concerning the optimization process, SA outperformed the other analyzed algorithms, but PSO presented the best trade-off between performance and computation cost. The same protocol (OLSR) has been optimized in terms of energy-efficiency. For this problem, a pEA was utilized to mitigate the problem of the high computational costs of the fitness evaluations (VANET simulations). This approach provided a computational efficiency greater than 80%. The energy-efficient configurations achieved energy consumption reductions up to 40%, improving the results of other NC based search procedures presented in previous studies. AODV has been also optimized in terms of QoS (PDR and E2ED) by formulating a multiobjective optimization problem and addressing it by utilizing NSGA-II and SMPSO. The algorithms were implemented by following the parallel master-slave model, motivated by the high computational efficiency shown in previous studies. In effect, these algorithms provided acomputational efficiency of 87% in pSMPSO and 90% in pNSGA-II. The computed protocol configurations outperformed other state-of-the-art ones in terms of PDR while keeping the E2ED in the threshold of proper operation. Finally, there is another study published in off-line optimization that has not been detailed in this chapter because of length constraints. The energy-efficiency optimization of AODV presented in Toutouh et al. (2012a). In this case, the NC algorithm analyzed (DE) to address the problem performs the evaluation of a given solution by using parallel Monte-Carlo simulations of variations over the same VANET scenario, and thus, leading the algorithm to improve the accuracy in the solution evaluation. Using the computed parameterization an average reduction of 32% in the power consumption was obtained. All the results presented in this chapter lead us to confirm the working hypothesis of this thesis: that coupling NC techniques and accurate VANET simulations represents a valid methodology to optimize (to improve), and thus, make practical existing theoretical protocols for vehicular communications. 84 Chapter 5. On-line Broadcasting Optimization in Vehicular Networks •Given a vehicle vthat belongs the VANET, the NN(v)function returns the set that contains all the nodes inside its network coverage (1-hop neighbor nodes). This value is computed taking into account all the different source nodes of the received beacons. The problem consists in finding brv∈BR for each node vto optimize two objectives: 1. Maximizing number of the beacons traveling through the shared medium in terms of the ratio of the channel occupancy (η(v)in Equation 5.1). 2. Minimizing the difference between the effective beacon rates in the neighborhood of v (σ(v)in Equation 5.2), i.e, maximizing the balance in the use of the channel. In this case, we have decided to use the relative standard deviation to evaluate σ(v). MAX η(v) = MAX j∈NN(v) P j brj!+brv MaxQ η(v)∈[0,+∞)(5.1) MIN σ(v) = MIN j∈NN(v) P j (brj−¯ brv)2!+ (brv−¯ brv)2 |NN(v)|σ(v)∈[0,1] (5.2) ¯ brvrepresents the average beacon data rates in the neighborhood of v(see Equation 5.3). ¯ brv= j∈NN(v) P j brj!+brv |NN(v)|+ 1 (5.3) Furthermore, the selected beacon rates computed by the algorithms brvshould not generate network congestion. Therefore, computed solutions should not exceed the effective capacity of the channel (ω) even η(v)may return larger values, which means that the computed solutions are subjected to the restriction presented in Equation 5.4. η(v)≤ω(5.4) The congestion control algorithms guarantee that the VANET nodes generate at least brMIN ∈BR, which is the minimum beacon rate (brMIN < bri, brMIN ∀bri∈BR, bri6= brMIN ), and never more than brMAX ∈BR, which is the maximum beacon rate (brMAX > bri∀bri∈BR, bri6=brMAX ). Therefore, the fair beacon rate optimization problem consists in finding for each VANET node vits current brvthat optimizes both objectives with the restriction described in Equation 5.4. The computations are carried out by each node itself (there is not any central management entity) taking into account MaxQ,α, and the beacon rates of all its neighbors (NN(v)). 5.3 Greedy Dynamic Broadcasting In this thesis, we define a set of different methods to dynamically compute optimized beacon rates to address the FBR optimization problem. These methods compose the FREEDY (Fair beacon Rate grEEDY) family of algorithms. The proposed FREEDY algorithms are fully distributed (executed periodically by each node of the VANET after a given window time), thus, no central manager entity is used. Chapter 5. On-line Broadcasting Optimization in Vehicular Networks 85 As most of the proposed congestion control methods presented in the literature, the FREEDY’s perform two main operations: network monitoring and network components reconfiguration (Lochert et al., 2007). In this case, the network monitoring is performed by analyzing the actual channel occupancy (load) and the number of neighbor nodes. This information can be obtained by evaluating the queues in a given window time to measure the channel occupancy and the neighborhood. FREEDY is composed by four different algorithms: two Self FREEDY, in which the nodes compute FBR using isolated information from their own network monitoring, and two Swarm FREEDY, which combine isolated information with information received from the neighbor nodes. FREEDY algorithms follow a cross-layer design (see Figure 5.5). The two main operations defined in FREEDY are included in the WAVE Management Entity (WME) (Campolo et al., 2015). FIGURE 5.5: Global cross-layer architecture of FREEDY family. 5.4 Self FREEDY Methods Two Self FREEDY algorithms are defined according to the information used to monitor the network and to compute the new beacon rates: Self o-FREEDY, that evaluates the channel occupancy, and Self n-FREEDY, that utilizes the size of the neighborhood of the node (1-hop distance nodes). Both methods present the same two main software components in their architecture (see Figure 5.6): •Self Queue Monitoring Component (SQMC): It evaluates the filling level of the queues or the number of neighbor nodes. If it is necessary, the SQMC invokes the Beacon Rate Adaptation Component. •Beacon Rate Adaptation Component (BRAC): It analyzes the information received from the other component to take the decision about which will be the new beacon rate better suited to the current network status. 86 Chapter 5. On-line Broadcasting Optimization in Vehicular Networks FIGURE 5.6: Main components of Self FREEDY. 5.4.1 Self o-FREEDY Self o-FREEDY computes FBR by adapting the beacon rate to the current channel occupancy by applying a reduction to the beacon rate if the occupancy starts to be close to α. Figure 5.7 summarizes the main steps of this algorithm. Self o-FREEDY monitors the queue, when it detects the channel occupancy CO exceeds the channel occupancy threshold CO_Threshold, them Self o-FREEDY BRAC is invoked in order to apply the reduction function red : [CO_Threshold, 1] →BR to compute brv. FIGURE 5.7: Complete flowchart of the Self o-FREEDY algorithm. In this analysis, the use case evaluated to test beaconing adaptation is based on the real requirements of most CVS applications in the literature (Campolo et al., 2015), in which BR ∈ {1,2,3,4,5,6,7,8,9,10}and α= 0.8. In addition, after an initial experimentation, the CO_T hreshold is set to 0.6and logarithmic decay is the applied red function (see Equation 5.5). brv=MAX 1 + A×eB×COm(5.5) 5.4.2 Self n-FREEDY The main idea of the Self n-FREEDY consists in dividing the maximum effective capacity of the channel into all the nodes in the neighborhood (including the own node). The algorithm starts by analyzing the received beacons in the queues to compute |NN(v)|, i.e., the number of neighbor nodes (see Figure 5.8). Then, the tentative beacon rate (tbrv) is computed dividing the effective capacity of the channel (ω) by the number of the neighbor nodes plus one (see Equation 5.6). If tbrvis higher than brMAX (10 Hz in our studies), then brvis equal to brMAX . Otherwise, brvis equal to tbrv(see Equation 5.7). Chapter 5. On-line Broadcasting Optimization in Vehicular Networks 87 FIGURE 5.8: Complete flowchart of Self n-FREEDY algorithm. tbrv=ω |NN(v)|+ 1(5.6) brv=(tbrvif tbrv≤brMAX brMAX if tbrv> brMAX (5.7) 5.5 Swarm FREEDY Methods Swarm FREEDY algorithms combine self measured (monitored) information with shared congestion control data from the neighbor nodes. This control information is encoded as an integer value in the beacons to be broadcasted. This information is stored in a temporal buffer (BRBuffer) in order to utilize it in the near future beacon rate computations. We have designed two different Swarm FREEDY algorithms according to the information utilized to compute the new beacon rates: Swarm o-FREEDY, that evaluates the channel occupancy, and Swarm n-FREEDY, that utilizes the size of the neighborhood. The Swarm FREEDY algorithms have three different software components (see Figure 5.9): •Self Queue Monitoring Component (SQMC): It evaluates the filling level of the queues or the number of neighbor nodes in order to update BRBuffer. •Swarm Information Exchange Component (SIEC): It decodes information encoded in the received beacons and updates BRBuffer. •Beacon Rate Adaptation Component (BRAC): It analyzes the information stored in BRBuffer to compute the new beacon rate. FIGURE 5.9: Main components of FREED algorithms. In short, the SQMC and SIEC components operate in parallel with the aim of updating the information stored in the BRBuffer, and the BRAC component updates the beacon frequency br according to the stored information in the buffer. The main difference between the two defined swarm methods, Swarm o-FREEDY and Swarm n-FREEDY, is the type of information stored in the buffer and how it is used. 88 Chapter 5. On-line Broadcasting Optimization in Vehicular Networks 5.5.1 Swarm o-FREEDY The main idea applied in Swarm o-FREEDY is: if a node detects that the CO is higher than the effective capacity of the channel (ω) in a given percentage, then all the nodes of the neighborhood have to reduce their beacon rates in the same percentage. In this method, the BRBuffer is a vector of natural values with ten components, [x1x2... x10]. Each component xistores the number of petitions to modify its current beacon rate (brt) according to Equation 5.8. Therefore, iis the multiplicative factor to be applied to compute the new beacon rates. These values are stored in the BRBuffer during a given window of time. brt+1 =brt×(i×0.1) (5.8) For example, if BRBuffer=[0 0 10 25 0 0 0 0 0 1], then it means that the node has received 36 beacons that included the following broadcasting protocol information: 10 petitions to use a new beacon rate which is the 30% (x3= 10) of the current one, 25 requests to use a new beacon rate that is the 40% (x4= 25) of the current one, and one petition to not apply any modification (x10 = 1) on the current beacon rate (brt+1 = 100% brt). Figure 5.10 summarizes the Swarm o-FREEDY complete procedure. Notice that SQMC and SIEC are executed in parallel and BRAC is run once just after a given timeout is reached. FIGURE 5.10: Complete flowchart of the Swarm o-FREEDY algorithm. In the Swarm o-FREEDY, the SQMC component monitors the IEEE 802.11p queue length to obtain the actual CO. According to CO, it includes in the beacons to be broadcasted the beacon modification request (BMR ∈[1,10]) which is computed by following Equation 5.9. At the same time, the protocol modifies its own BRBuffer by adding an own petition according to the BMR computations, the BMR-th component of the vector is incremented (xBMR =xBMR + 1). Chapter 5. On-line Broadcasting Optimization in Vehicular Networks 89 BMR =     10 CO ≤ω 10 −CO−ω ω×10ω < CO < 2×ω 1CO ≥2×ω (5.9) The SIEC decodes the beacons received in order to extract the BMR requested by the neighbors and to update the BRBuffer. The buffer is modified by increasing in each component of the vector the request received, i.e., xBMR =xBMR + 1. The BRAC is invoked at the end of a given window time in order to compute the new beacon rate brt+1 according to the information stored in the BRBuffer. It applies a multiplicative factor mf to the current beacon rate according to the information stored in BRBuffer (brt+1 =brt×mf ×0.1). There are two different variants of Swarm o-FREEDY depending the what metric is evaluated to select the mf to use: a) the Swarm o-FREEDY-med, which selects the median value between the two most requested values of the BRBuffer, and b) the Swarm o-FREEDY-mod, which chooses the most requested one (the mode). FIGURE 5.11: Histogram that represents a given BRBuffer which stores the beacon rate modification requests received. Figure 5.11 shows a BRBuffer that stores the following information [0 0 5 15 20 40 15 30 5 0]. According to these values, Swarm o-FREEDY-med computes mf=7 (median value between 6 and 8) and Swarm o-FREEDY-mod mf=6 (the most frequent BMR). 5.5.2 Swarm n-FREEDY The Swarm n-FREEDY is motivated by the same idea as Self n-FREEDY: the channel should be proportionally divided according to the neighborhood size. However, in this case, in addition to the information about the own neighbor nodes, this new algorithm utilizes the information about the number of neighbor nodes of its neighbors to increase the accuracy. In Swarm n-FREEDY, the BRBuffer of each node is also a vector of natural values xi, where each one stores the number of petitions received by the node to change its beacon rate to i beacons per second. For example, if BRBuffer=[0 0 10 25 0 0 0 0 0 1], then it means that the node has received 10 requests to change the beacon rate to 3 Hz (x3= 10), 25 to change to 4Hz (x4= 25), and 1 to change to 10 Hz (x10=1). Figure 5.12 summarizes the Swarm n-FREEDY complete procedure. Notice that SQMC and SIEC are executed in parallel and BRAC is run once just after a given timeout is reached. 90 Chapter 5. On-line Broadcasting Optimization in Vehicular Networks FIGURE 5.12: Complete flowchart of the Swarm n-FREEDY algorithm. The Swarm n-FREEDY SQMC component behaves similarly to Self n-FREEDY. The difference is that the swarm method do not update the current beacon rate, in contrast, it increases the BRBuffer component of the desirable beacon rate (DBR) that is computed as brvin Equation 5.7, i.e., DRB =brv. Thus, this component updates the BRBuffer by increasing the DBR-th component (xDBR =xDBR + 1) and includes the DRB value in the new beacons in order to inform the neighbor nodes. In this method, the SIEC decodes the beacons received to extract the DBR requested by the neighbors to update the BRBuffer. The buffer is modified by increasing in each component the request received, i.e., xDBR =xDBR + 1. In addition, after a given timeout timer (window time), BRAC is executed to compute the new beaconing frequency brt+1 according to the DBRs stored in BRBuffer. There are two different variants of Swarm n-FREEDY depending the what metric is evaluated to select the brt+1 to use: a) the Swarm n-FREEDY-med, which chooses the median value between the two most requested values of the BRBuffer as new beacon rate, and b) the Swarm nFREEDY-mod, which selects the most requested one (the mode). Following the example in Figure 5.11 (BRBuffer=[0 0 5 15 20 40 15 30 5 0]), in Swarm n-FREEDY-med it holds that brt+1=7 and Swarm n-FREEDY-mod it holds that brt+1=6. 5.6 Experimental Results The experiments are carried out by using MATLAB. Each analyzed congestion control method is simulated 100 times over the same highway scenarios. We now define the highway VANET scenarios used in the experiments, we set the parameters of the Self o-FREEDY algorithm, and finally, we discuss the numerical results of evaluating the FREEDY algorithms. 5.6.1 Highway VANET Scenarios The on-line fair beacon rate optimization is studied in a highway road of two kilometers long and six lanes (three lanes in each direction). Nine highway VANET scenarios are defined over this road by changing the mobility models in order to test the performance of the congestion control algorithms proposed here in different vehicular network status. Chapter 5. On-line Broadcasting Optimization in Vehicular Networks 91 These scenarios are grouped in five homogeneous and four heterogeneous road traffic scenarios. In the first ones, the vehicles are assigned to a given lane randomly in which all the lanes have the same probability, and therefore, all the lanes have a very close number of vehicles. In the heterogeneous highway scenarios the probabilities are not the same. The vehicles have higher probability to be assigned to the external lanes than to the internal ones. The speed per lane increases from the external to the internal lanes, as in real highways. The distances between vehicles and the speeds are computed according to the square law for dry roads defined by Spanish authorities (DGT, 2015), i.e., speed ×speed ≃distance 100 . Tables 5.1 and 5.2 summarize the main characteristics of the used scenarios. The average values of the number of vehicles and the speed per lane are not shown in heterogeneous scenarios because these values are lane dependent (see Table 5.2) The simulation time for all scenarios is 100 seconds. TABLE 5.1: Main characteristics of homogeneous highway scenarios for congestion control tests. Road density and Total number Average vehicles Average distances Average speed scenario name of vehicles per lane between nodes Very low density (HM-Ld1) 120 20 100 m 100.00 km/h Low density (HM-Ld2) 160 26 75 m 86.60 km/h Middle density (HM-Ld3) 240 40 50 m 70.71 km/h High density (HM-Hd1) 480 80 25 m 50,00 km/h Very high density (HM-Hd2) 800 100 <25 m 38.73 km/h TABLE 5.2: Main characteristics of heterogeneous highway scenarios for congestion control tests. Road density and scenario name Total number of vehicles Range of speeds Very low density (HT-Ld1) 200 [40 km/h, 130 km/h] Low density (HT-Ld2) 240 [40 km/h, 130 km/h] High density (HT-Hd1) 320 [40 km/h, 130 km/h] Very high density (HT-Hd2) 380 [40 km/h, 130 km/h] In terms of communications, the vehicles are running CVS applications that require exchanging beacons with a frequency that ranges from 1 Hz to 10 Hz. The wireless devices utilized are configured with IEEE 802.11p with a communication range of 250 meters. In addition, following the MATLAB simulation presented in Mir et al. (2015), it is considered that the maximum size of the queues of IEEE 802.11p is 400 and αis 0.8. 5.6.2 Self o-FREEDY Parameterization As defined in Section 5.4.1, the Self o-FREEDY algorithm utilizes the logarithmic decay as reduction function (red) to compute the beacon rate according to the current channel occupancy (see Equation 5.5). This function depends on two parameters that have to be set Aand the logarithmic growth parameter B. In our case, we have selected a set of tentative values for both parameters A∈ {1,3,5,7,9}and B∈ {0.05,0.1,0.15,0.2,0.25,0.3,0.35,0.4,0.45,0.5}. These set of values generate different logarithmic decay functions that are plotted in Figure 5.13. Each possible configuration of the logarithmic decay function is evaluated by simulating 100 times the middle density homogeneous highway VANET scenario. The configuration that presents the best trade-off between the occupancy and the balance is A=3 and B=0.10. 92 Chapter 5. On-line Broadcasting Optimization in Vehicular Networks FIGURE 5.13: Different curves of the generated logarithmic decay functions. 5.6.3 Numerical Results and Discussion This section discusses the results obtained by all the proposed FREEDY congestion control methods in the defined scenarios. In addition, other two additional methods are included in the experiments as a baseline for the comparisons: •Aloha based method (Tanenbaum, 2002), the nodes broadcast beacons at the beginning of a given slot time slot without analyzing the medium, regardless whether there are another nodes using the medium or not. This is a very simple method, but the probability of having packet collisions critically grows with the size of the network. •CSMA based method: When VANET nodes have to transmit a given beacon they analyze the medium. If no other node is using it then they broadcast the beacons, otherwise they drop the given beacon since, after a short while, new beacons will be generated and the information in the current beacon will be obsolete. This method reduces the likelihood of collisions. These last two broadcasting methods utilize a fix beacon frequency. In order to analyze them, they are configured with three different fix beacon frequencies: 1 Hz, 5 Hz, and 10 Hz. Tables 5.3 and 5.4 summarize the experimental results by showing the average and the normalized standard deviation values of the two optimized metrics, channel occupancy (see Equation 5.1) and network balance (see Equation 5.2), respectively. These results are organized in four groups: homogeneous low density, which includes HM-Ld1, HM-Ld2, and HM-Ld3 scenarios; homogeneous high density, which comprises HM-Hd1 and HM-Hd2 ones; heterogeneous low density, which consists of HT-Ld1 and HT-Ld2 ones; and heterogeneous high density, which covers HT-Hd1 and HT-Hd2 ones. Analyzing the occupancy, there are three type of results: a) the ones that guarantee the proper operation of the network (CO ≤α), b) the ones that may incur in a critical drop of QoS (α < CO ≤1.0), and c) the ones that exceed the channel capacity (CO > 1.0). In table 5.3 and 5.4 the second and third group are shaded with light and dark gray, respectively. As expected, the aloha based methods allow the nodes to communicate with very low beacon rates (1 Hz) with a very poor performance. If the rate increases to 5 Hz it just is able to operate property in low density scenarios. In the other cases the channel occupancy reported value is higher than the channel capacity, which in practical means that the network is completely congested. There are no measure in terms of balance because they always broadcast packets and there are not difference between the beacon rates in the neighborhood, i.e., always σ(v)=0(see Equation 5.2). Chapter 5. On-line Broadcasting Optimization in Vehicular Networks 93 TABLE 5.3: Results in terms of occupancy for each congestion control method (Equation 5.1). Homogeneous scenarios Heterogeneous scenarios Algorithms low density high density low density high density Avg. Std. Avg. Std. Avg. Std. Avg. Std. Self o-FREEDY 0.614 3.53% 0.872 8.46% 0.642 5.85% 0.714 1.78% Self n-FREEDY 0.801 5.26% 0.908 2.56% 0.836 0.71% 0.845 0.31% Swarm o-FREEDY-med 0.741 14.25% 0.721 13.06% 0.766 17.25% 0.515 4.67% Swarm o-FREEDY-mod 0.753 2.17% 0.398 25.27% 0.727 32.42% 0.263 17.50% Swarm n-FREEDY-med 0.610 23.57% 0.638 5.53% 0.730 14.02% 0.691 16.48% Swarm n-FREEDY-mod 0.759 2.75% 0.548 9.15% 0.736 2.78% 0.732 3.70% Aloha-1Hz 0.107 29.06% 0.398 25.28% 0.142 29.29% 0.217 8.63% Aloha-5Hz 0.537 29.02% 1.988 25.26% 0.712 29.30% 1.083 8.64% Aloha-10Hz 1.075 29.02% 3.976 25.26% 1.424 29.25% 2.165 8.65% CSMA-1Hz 0.108 29.02% 0.398 25.27% 0.142 29.24% 0.217 8.64% CSMA-5Hz 0.537 28.98% 0.846 7.55% 0.694 8.88% 0.756 0.21% CSMA-10Hz 0.761 2.49% 0.988 6.41% 0.781 5.87% 0.864 2.17% TABLE 5.4: Results in terms of balance for each congestion control method (Equation 5.2). Homogeneous scenarios Heterogeneous scenarios Algorithms low density high density low density high density Avg. Std. Avg. Std. Avg. Std. Avg. Std. Self o-FREEDY 0.343 28.28% 0.196 6.08% 0.278 47.14% 0.165 12.96% Self n-FREEDY 0.137 83.18% 1.108 24.21% 0.285 37.20% 0.453 13.81% Swarm o-FREEDY-med 0.202 47.37% 0.293 33.33% 0.249 31.93% 0.349 13.18% Swarm o-FREEDY-mod 0.247 102.00% 0.000 0.00% 0.500 59.91% 0.268 108.63% Swarm n-FREEDY-med 0.070 99.40% 0.128 23.28% 0.082 74.32% 0.105 55.17% Swarm n-FREEDY-mod 0.004 153.26% 0.007 7.14% 0.027 87.12% 0.020 100.93% Aloha-1Hz - - - - - - - - Aloha-5Hz - - - - - - - - Aloha-10Hz - - - - - - - - CSMA-1Hz 0.000 0.00% 0.000 0.00% 0.000 0.00% 0.000 0.00% CSMA-5Hz 0.001 667.57% 1.162 17.22% 0.102 289.00% 0.656 15.02% CSMA-10Hz 0.520 74.90% 1.765 13.02% 0.918 21.23% 1.260 5.54% The CSMA based methods improve the performance of the aforementioned non-adaptive method. Taking into account just the channel occupancy metric, they offer the best values in low density highway scenarios when CSMA-10Hz is used. However, it incurs in a very high cost in terms of balance, and therefore, it suffers from the largest differences between the amount of data that each node in the neighborhood broadcasts. This means that although the channel is efficiently used, when managed by CSMA-10 Hz the VANET applications cannot property operate because many nodes do not broadcast their beacons. Regarding to the Self FREEDY methods, the channel occupancy of Self n-FREEDY (that divides the effective channel capacity among the neighbors) has exceeded the αvalue defined in our experiments. Therefore, it provokes a drop in the QoS of the network. This is because the computations take into account just the information of their neighborhood (1-hop nodes), and ignore the rest of the nodes in the same cluster. In addition, the fairness between the nodes (balance) is the least competitive of all FREEDY methods. In contrast, the Self o-FREEDY 100 Chapter 6. Natural Computing for Smart Roadside Unit Placement Recombination The crossover operator is Intermediate Recombination; two parents ~x ={xi}and ~y ={yi}are combined to generate two offspring O1 and O2; they satisfy O1i=αixi+ (1 −αi)yiand O2i=βiyi+ (1 −βi)xiwith αi, βirandomly chosen from the interval [−µ, 1 + µ]for a given value of parameter µ∈[0,1]. The recombination operator is applied with a probability pC. 6.4 Experimental Results This section presents the experiments carried out to solve RSU-DP optimization problem by using the proposed MOEA, which is implemented by using ECJ Java-based Evolutionary Computation framework (White, 2012). Further details about this experimental analysis can be found in Massobrio et al. (2015b). 6.4.1 Problem Instances In order to apply our evolutionary approach, we define a real world problem instance based on a real map of Málaga, real road traffic data, and real wireless antennas to equip the RSUs. The map covers an area of 42.557 km2in the city, including a number of 106 points, which define 121 segments with lengths between 55 and 1556 m (see Figure 6.5.a). All major traffic ways, including avenues and important streets in Málaga are sampled. Some important avenues with large traffic volume define multiple segments in the map (e.g., Avenida de Andalucía, Avenida de Velázquez,Avenida de Valle Inclán and Paseo Marítimo Pablo Ruiz Picasso, all of them with more than six segments defined in the map). The traffic data was collected by the Málaga governmental institutions using a set of sensors located along the roads. These sensors returned the total number of vehicles that circulated during the last three months of 2014. Thus, this information is utilized to define the normal pattern for traffic (see Figure 6.5.b). In addition, two probabilistic multiplicative factors are applied over the normal pattern to define two other ones: low pattern, reducing the traffic randomly in [0%–20%] and high pattern, increasing the traffic randomly in [0%–20%]. These patterns represent situations with lower and higher road traffic density, respectively. The RSUs hardware is defined by a processing unit equipped with a IEEE 802.11p network interface. Each network interface is connected to an external antenna to improve the communication range according to a given antenna gain. The gain, measured in decibels (dBi), is a measure of the power of the radio signal radiating from the antenna. Generally, the higher the gain of an antenna, the longer radio range will be obtained. The used antennas have to operate in 5.9 GHz band utilized in IEEE 802.11p standard. Our instance includes three types of RSUs that differ in the antenna gain connected. Three types of IEEE 802.11p antennas are considered, according to three commercial omni-directional antennas that can be found in Cetacea on-line shop (Cetacea, 2015). Table 6.1 summarizes the main features of such antennas. In order to define the effective radio range (ERR) of each RSU, we evaluate via simulations the average PDR, at different distances (from 0 to 650 m) for each RSU. The experiments were performed using the ns-2 simulator (NS2, 2015) to simulate vehicular communications using IEEE 802.11p PHY/MAC standard in a urban scenario defined in a one lane road of 1 km with one RSU and 10 moving cars at 40 km/h. During the simulations, the RSU sent continuous data streams at 256 Kbps to the cars. The Probabilistic Nakagami radio propagation model (Saunders and Aragon, 1999) is used to represent channel fading characteristics of urban scenarios. The results of these experiments are summarized in Figure 6.6. Chapter 6. Natural Computing for Smart Roadside Unit Placement 101 a) Segments that represent the road map. b) Road segments in which their width represents the traffic density. FIGURE 6.5: Road information from Málaga taken into account in RSU-DP analysis. Finally, in order to ensure a competitive QoS, we defined the ERR of each RSU as the distance at which the average PDR is equal or higher than 66.67%. Therefore the ERR is set for each antenna as it is shown in Table 6.1. FIGURE 6.6: PDR results regarding to the three types of antennas analyzed in RSU-DP. 102 Chapter 6. Natural Computing for Smart Roadside Unit Placement TABLE 6.1: General information about the used antennas to address RSU-DP. type commercial model gain ERR cost t1Echo Series Omni Site Antenna 6 dBi 243.12 m 121.70 $ t2Echo Series Omni Site Antenna 9 dBi 338.70 m 139.20 $ t3Echo Series Omni Site Antenna 12 dBi 503.93 m 227.50 $ 6.4.2 Comparison Against Two Greedy Strategies In order to compare the results achieved by the proposed MOEA, we develop two randomized greedy heuristics, focused on each one of the problem objectives. These heuristics apply intuitive ideas that simulate the behavior of human-planning strategies, and they are improved versions of the methods defined by Trullols et al. (2010) and later used in the comparative study by Cavalcante et al. (2012). The improvements in our heuristics (over the ones in Trullols et al. (2010)) include: i) in our methods, RSUs can be located anywhere within road segments (instead of placing RSUs only at road intersections), ii) we consider a variable number of RSUs (instead of using a fixed number of RSUs), and iii) a set of RSU types and coverages are considered (instead of a single RSU type). We compare the results achieved by the proposed MOEA against two greedy heuristics. The two greedy heuristics are briefly described next: 1. Greedy QoS (GQoS): the set of segments Pis sorted according to the QoS they provide (i.e., the ratio between number of vehicles and average speed) in case they are totally covered by a RSU. Iteratively, GQoS adds to the solution the RSU that provides the best QoS (or cheaper in case of overlapping), at a random location in the sorted segments, while computing the segments covered by the located infrastructure in each step. Segments that are already covered are not taken into account to be included in the solution. 2. Greedy cost (GCost): starting from the solution computed by GQoS, the algorithm tries to reduce the cost without significantly affecting the quality of service. Different solutions are explored, by replacing existing RSUs by cheaper ones, or deleted, and the option with the lower QoS degradation is selected. The algorithm stops when all segments are considered or when the QoS of the solution is equal to α·Qwhere Qis the best QoS value achieved by the greedy algorithm for QoS and α∈[0,1]. For the experimental analysis, GCost was executed using α∈ {0.70,0.75,0.80}. Parameter Settings of NSGA-II We perform an analysis to find the best values for NSGA-II parameters. In the parameter setting experiments, the best results are obtained using the configuration: population size = 72, pC= 0.95,pM= 0.01,πA= 0.5,πB= 0.25. The value of µin the Intermediate Recombination operator is set to 0.25. In the Gaussian mutation the value of parameter σis 0.25. 6.4.3 Numerical results The experimental analysis is oriented to evaluate the problem solving capabilities of NSGA-II for the RUS-DP. On the one hand, we compare NSGA-II with the greedy heuristics; on the other hand, we evaluate several standard multi-objective optimization metrics (Deb, 2001): generational distance (GD), to evaluate the solution quality; spread (I∆), to evaluate the distributions of solutions; and the combined metric relative hypervolume (RHV ), to evaluate both quality and dispersion. We also analyze the Pareto fronts computed by NSGA-II for each scenario in the experimental evaluation. For each problem instance, we perform 30 independent runs of the MOEA and both greedy algorithms. Chapter 6. Natural Computing for Smart Roadside Unit Placement 103 In the experimental analysis the proposed MOEA shows a good solving capability. NSGAII significantly outperforms the two greedy heuristics while computing accurate Pareto fronts. The solutions computed by the greedy heuristics tend to group in different areas of the solution space, depending on the parameters used for their execution. Therefore, the results obtained by the MOEA are compared against the average results of each group of greedy solutions. The improvements of NSGA-II over the greedy strategies are reported in Table 6.2. The selected NC algorithm is able to improve the QoS of the greedy heuristics in up to 6.0% while keeping the same cost, and improve up to 37.1% the cost of the greedy heuristics while keeping the same QoS (this value represents a $5218.4 saving on a $14079.7 investment). Regarding the cost objective, NSGA-II improves over the greedy results 19.8% in average (for low traffic instance), 20.3% in average (for normal traffic instance), and 17.0% in average (for high traffic instance). Improvements on QoS are smaller but still significative: 4.2% in average (for low and normal traffic instances) and 3.5% in average (for high traffic instance). TABLE 6.2: NSGA-II improvements over greedy heuristics in solving RSU-DP. Instance Cost improvement (%) QoS improvement (%) Best Avg.±Std. Best Avg.±Std. low 37.1 19.8±10.3 5.6 4.2±0.9 normal 36.9 20.3±10.7 6.0 4.2±1.2 high 31.0 17.0±8.3 5.5 3.5±1.4 Figures 6.7 and 6.8 illustrate two different solutions (RSU deployments) with the same QoS computed by the EA and the the heuristics, respectively. As it can be seen, the reduction of costs achieved by the NC method is principally because the RSUs are located such that they avoid unnecessary network overlapping. Thus, they can offer similar coverage by using a smaller amount of antennas. FIGURE 6.7: RSU-DP deployment computed by applying NC. 104 Chapter 6. Natural Computing for Smart Roadside Unit Placement FIGURE 6.8: RSU deployment computed by using a heuristic method. Table 6.3 shows the average, standard deviation and best results for the studied standard multi-objective optimization metrics. The ideal Pareto front (which is unknown for the problem instances studied) is approximated by gathering the non-dominated solutions obtained over all executions performed. The small generational distance values indicate a good convergence to an hypothetical ideal Pareto front, and demonstrate the robustness of the NSGA-II approach. Spread values suggest a good distribution of the non-dominated solutions, which is similar for the three analyzed instances. These results are confirmed by the unitary value of the relative hypervolume metric. TABLE 6.3: NSGA-II results (multi-objective optimization metrics) when solving RSU-DP. Instance GD I∆RHV Best Avg.±Std. Best Avg.±Std. Best Avg.±Std. low 1.2 1.5±0.3 0.7 0.7±0.0 1.0 1.0±0.0 normal 1.2 1.5±0.1 0.7 0.7±0.0 1.0 1.0±0.0 high 1.0 1.6±0.2 0.7 0.7±0.0 1.0 1.0±0.0 Finally, figures 6.9.a, 6.9.b, and 6.9.c illustrate the global Pareto fronts achieved by NSGA-II in the 30 executions performed, compared against the results obtained by the state-of-the-art greedy algorithms on low, normal, and high traffic density scenarios. In these figures, black dots represent the non-dominated solutions that belong to the obtained Pareto fronts and the red circled points are the solutions computed by the greedy algorithms. As it is illustrated, the solutions of the computed Pareto fronts by the parallel EA dominate the ones of the greedy algorithms. Therefore, the heuristics compute RSU designs with lower QoS and higher deployment costs than our NC method. Chapter 6. Natural Computing for Smart Roadside Unit Placement 105 a) Low traffic density. b) Normal traffic density. c) High traffic density. FIGURE 6.9: Global Pareto fronts computed by the NSGA-II and the solutions obtained by the greedy algorithms in solving RSU-DP. 106 Chapter 6. Natural Computing for Smart Roadside Unit Placement 6.5 Conclusions An explicit multi-objective formulation is presented and a parallel MOEA is applied to solve real problem instances in city-scaled scenarios. In the experimental analysis, the proposed MOEA shows good problem solving capabilities. NSGA-II significantly improves over two greedy heuristics for the problem (which are improved versions of methods proposed and used in the literature). The NSGA-II improvements are up to 37.1% (19.0% in average) in the cost objective and 6.0% (5.7% in average) in the QoS objective. Additionally, NSGA-II is able to compute accurate Pareto fronts, providing different trade-off solutions for the problem. The novel analysis presented in this chapter represents a first successful step to address RSU-DP in large-scaled cities by using NC. Chapter 7 Real World VANET Experiments THE evaluation of vehicular networks is overwhelmingly carried out in the present literature with simulations. The degree of realism of those is limited because their computations simplify the real world interactions too much in many cases. In this chapter, we define two different outdoor VANET testbeds to evaluate the performance of short range vehicular communications. This study is carried out to confirm the efficiency of configuring nodes with protocols improved by applying NC and to evaluate the use of lightweight personal devices in V2V communications. This chapter introduces the importance of performing outdoor experiments and details the experimental analysis results. 7.1 Introduction The different solutions obtained in the previous chapters have been evaluated by using simulators. This analytic method is limited by the complexity and dimension of real world systems, which usually require simplifications and approximations that generally lead to differences between their results and real world behavior. As a useful complement (or even realistic substitute) for simulations we can use experimental real world testbeds. Testbeds have important advantages with respect to the simulations because these tests are carried out in a real world environments offering close-to-real or real performance, as well as revealing behavioral issues (Pinart et al., 2008). However, there is a lack of scientific articles that use outdoor experiments in the field of vehicular networks. The main reasons for this may be the unavailability of resources (vehicles and road equipment), the difficulties in doing field studies, and the accuracy of the performance analysis. Despite these limitations some authors have analyzed the feasibility of VANET communications by using laptops equipped with IEEE 802.11bg wireless interfaces (Gass et al., 2006; Bychkovsky et al., 2006; Lee et al., 2007). In Festag et al. (2004), the authors analyzed FleetNet’s platform, which combines IEEE 802.11bg (WLAN) and GPRS (cellular) wireless interfaces. Recently, the performance of IEEE 802.11p PHY standard has been studied via V2I communications (Paier et al., 2010; Mangel et al., 2011). As the availability of IEEE 802.11p devices is very limited at present, other studies have utilized IEEE 802.11a PHY standard, which uses the band (5 GHz) closest to the one used by IEEE 802.11p (Sanchez et al., 2014). This chapter presents two different experimental analysis of vehicular communications performed in real outdoor VANETs (real vehicles and wireless devices): 1) we analyze the VDTP protocol (optimized versus standard) in order to validate the results of Chapter 4; and 2) we evaluate the performance of V2V communications by using personal devices (smartphones, tablets, and laptops) and two different PHY standards (IEEE 802.11g and IEEE 802.11a), in order to study the possibility of deploy VANETs without installing specific OBUs. 107 108 Chapter 7. Real World VANET Experiments 7.2 Performance Analysis of Improved VDTP in Real World Tests In the present section, we are aimed at defining a testbed in order to study the performance of the VDTP file transfer service between cars in a real urban VANET. In these outdoor experiments, the VDTP protocol has been tested following different parameter settings: the optimized VDTP configurations proposed in Chapter 4and the standard one proposed by CARLINK experts (Luna S., 2008). Thus, the results offer the possibility to confirm the QoS improvements on a VANET’s performance when optimized protocols are used, validating the previous results obtained through simulations. 7.2.1 VDTP Testbed Definition The VANET scenario utilized in our experiments is comprises of two cars moving through the roads in an area of 1.44 km2from the downtown of Málaga, Spain. The roads are opened to the general traffic during a non rush hour, so the number of vehicles traveling through our scenario are not constant (see Figure 7.1). Therefore, the speed and the distance between the vehicles vary over time, just as it would be in any real city. According to the tracking information, during the experiments the average distance between the nodes is 77 meters. FIGURE 7.1: Nodes during the real world VDTP experiments (P=petitioner and O=owner). Regarding the communication platform, the cars are equipped with a laptop with a PROXIM ORiNOCCO PCMCIA (IEEE 802.11bg) Wi-Fi transceiver (Proxim, 2015) connected to a 7 dBi omnidirectional antenna located on roof top of the car (see Figure 7.2). The file transfers are performed by using the six different configurations for urban VDTP shown in Table 4.4. Five of these configurations have been obtained automatically by using NC (i.e., PSO, DE, GA, ES, and SA) and the other one was proposed by Luna S. (2008), in this study it is named EXPERTS configuration. The global network is configured following the VANET specifications used in the simulations presented in Chapter 4. Additionally, we included a GPS unit in each vehicle to track their movement. In order to perform a general study, we take into account five types of data files of different sizes: 100 kBytes and 500 kBytes typical in traffic information services; and 1 MByte, 5 MBytes, and 10 MBytes that contain multimedia content. For each VDTP configuration, the vehicles exchange 15 files of each type, i.e., for each VDTP configuration there are 75 (5×15) file transfers. In turn, we define two different types of experiments named Urban Low Speed tests (uLs) and Urban High Speed tests (uHs) to study the influence of the speed in the performance of the VANET. In the first ones, the vehicles speed fluctuates between 20 and 30 km/h. In the Urban Chapter 7. Real World VANET Experiments 109 FIGURE 7.2: Vehicles equipment used to perform VDTP real world file transfers. High Speed tests, the vehicles speed fluctuates between 40 and 50 km/h. After the file transfers, the VDTP QoS is evaluated in terms of the number of lost packets during the downloads and the effective transmission data rate of the network during the file transfers. More information about the definition of the testbed is detailed in Toutouh and Alba (2011c). 7.2.2 Numerical Results We present here the experimental results from two points of view. First, we study the communications carried out between the cars during the experiments in order to evaluate the VDTP service. Next, we discuss about the performance of each VDTP parameterization taken into account in this work in order to compare them with each other. VANET Global Performance During the experimentation, all files are transferred completely and correctly. This is mainly because the two cars (network nodes) are always following the same course (see Figure 7.1). Therefore, even though there are lost packets because of networks problems related with the distance or the existence of obstacles between the nodes, they are able to reconnect with each other before refusing the file transfer. Table 7.1 presents the results obtained during the whole experimentation: the average number of lost packets during the transference of a file and the average effective transmission data rate performed during the downloads. The results are grouped by the VDTP parameterization used (PSO, DE, ES, GA, SA, and EXPERTS), the file type transferred (100 kBytes, 500 kBytes, 1 MByte, 5 MBytes, and 10 MBytes), and both experiment types (uLs and uHs). Globally, in terms of transmission data rates, the majority of the file transfers are carried out with a competitive bandwidth higher than 600 kBytes/s. As expected, we check that the communications perform better (larger data rates and smaller packet loss) when the speeds of the vehicles are lower. In Table 7.1 (last row), we can observe that, in average, during uLs there are 0.133 lost packets per file transfer with an effective data rate of 610.056 kBytes/s. In contrast, during uHs there are more packet loss (0.1533) and lower bandwidth (598.878 kBytes/s). 116 Chapter 7. Real World VANET Experiments a) Cases with no vehicle in-between our two moving cars. b) Cases of vehicles (in dotted circles) coming between our two moving cars. FIGURE 7.8: Nodes during the real-wold V2V experiments. In order to study how the distance between the VANET nodes also influences the performance of the communications, we have carried out different tests by modifying the distance between the vehicles over the journey in the dynamic experiments. As it was very difficult to maintain the same distances between the nodes as the ones defined for the experiments of the signal strength analysis because of the speed variations of the cars, we have used longer distances (distances multiple of 25 m). Thus, as shown in Figure 7.9.b, we have defined different experiments with the two vehicles separated by six different distances grouped in medium distance (25, 50, and 75 m) and long distance (100, 125, and 150 m). a) Distances at which the signal strength of the devices was measured. b) Distances between the cars during the V2V QoS analysis. FIGURE 7.9: Distances between the moving nodes during the real world experimentation. Seven kinds of VANET communication schemes are analyzed in the dynamic experiments. These communication schemes are distinguished by the devices connected to exchange the information and the IEEE 802.11 standard. They are named using the following format: <device1>-<device2>. Note that for the laptops we have included a capital letter to specify the PHY/MAC standard used, i.e., “A” for IEEE 802.11a and “G” for IEEE 802.11g. The smartphones and the tablets always communicate using IEEE 802.11g, therefore, we have not used any letter to specify the standard. Thus the communication schemes analyzed here are: smartphone-smartphone (sph-sph), smartphone-tablet (sph-tab), smartphone-laptopG (sphlaptG), tablet-tablet (tab-tab), tablet-laptopG (tab-laptG), laptopG-laptopG (laptG-laptG), and laptopA-laptopA (laptA-laptA). Figure 7.10 summarizes these seven communication schemes. Chapter 7. Real World VANET Experiments 117 We have carried out 42 different tests for the dynamic experiments. Each test is defined according to one of the seven aforementioned communication schemes and one of the six distances between nodes (see Section 7.3.2). These tests are named according to the communication scheme and the distance: <communication scheme>-<distance>. For instance, sph-sph-25m refers to the test in which both nodes are equipped with smartphones and are separated by 25 m while they are moving, and tab-laptG-125m represents the test in which one of the vehicles is equipped with a tablet and the other with a laptop (IEEE 802.11g) separated by 125 m. a) Communication schemes that use IEEE 802.11g (2.4 GHz). b) Communication scheme that uses IEEE 802.11a (5 GHz). FIGURE 7.10: Representation of the communications analyzed in the real world V2V experiments. The V2V transferring data tests consist in exchanging data streams from the source node to the destination node of the VANET while the cars are moving. The information exchange is done by using ICMP (Internet Control Message Protocol) packets (Tanenbaum, 2002) that encapsulate the bytes of data to be sent. We have selected this protocol as the use case protocol because we do not intend to test any specific type of application. In order to study the effects of the size of data packets on the performance of the VANET communications, we have performed data transfers by exchanging five kinds of data packets for each V2V test, that are defined by their size (32, 64, 128, 256, and 512 bytes of data). For each one of the five types of data packets, each node transfers to the other streams of 100 independent packets each. For more detailed information about the VANET testbed see (Toutouh and Alba, 2016). Now let us to present the results in terms of transmission power and QoS for the experimental analysis performed in this work. 7.3.3 VANET Nodes Transmission Power Analysis In the static experiments, the wireless transmission power of each device is evaluated in terms of the received signal strength indicator (RSSI) in a given location. RSSI reflects relative received signal strength in a wireless environment, in arbitrary units. Specifically, RSSI is an indication of the power level observed by a radio hardware while receiving a data frame. Remember that the evaluated RSSI includes the power from adjacent channel interference, thermal noise, etc. that could affect the signal received. In order to measure the RSSI we use dBm (also known as dBmW), which is an abbreviation for the power ratio in decibels (dB) of the measured power referenced to one milliwatt (mW). The experimental results are summarized in Figure 7.11, which shows the average signal strength sensed at a given point for each studied device. The shaded area represents the lowest receiver sensitivities for which a receiver can correctly decode frames for most of IEEE 802.11gbased wireless devices (signal strengths between -90 dBm and -80 dBm). 118 Chapter 7. Real World VANET Experiments FIGURE 7.11: Signal strength results the outdoor V2V experiments. As a first conclusion, the RSSI decreases with the distance between the node (device) that generates the signal and the measurement point (see Figure 7.11). At the same time, we observe that, even if we have measured the signal strength for some time to limit the negative effects over the signal propagation in real outdoor scenarios, the values still show some irregular behavior. Our explanation for this phenomenon is that the RSSI includes the received power of the interference, thermal noise, etc. that affect the possible regular behavior of such metric. As expected, the smartphone is the least competitive device in terms of RSSI results. The signal strength values for this device are between -90 dBm and -80 dBm from 60 m to 75 m, which means that its performance in transmitting information could suffer from a degradation at these distances. After 75 m, the RSSI is lower than -90 dBm, and therefore, smartphones barely have the capacity to exchange data streams at greater distances. The strength of the signal produced by the tablet is higher than -70 dBm for distances lower than 67.5 m. After that, from this point until 127.5 m, the strength of the signal decreases but it maintains values greater than -80 dBm. Thus, tablets may offer competitive communication performances at distances up to 127.5 m. Finally, when the distance is greater than 127.5 m the signal strength is lower than -80 dBm, but always higher than -90 dBm, which means that the tablet signal strength is over the lowest sensitivity threshold of IEEE 802.11g wireless based communications throughout our experiments. The best results in terms of signal strength are provided by the laptop when using both PHY/MAC standards, IEEE 802.11a and IEEE 802.11g. On the one hand, when IEEE 802.11a is used, the received signal strength is significantly higher than in the other devices. The main reason is that the antenna gain is higher on the 5 GHz band than on the 2.4 GHz. In this case, the RSSI is lower than -60 dBm just when the distance is longer than 90 m and the lowest measured signal strength is -70.29 dBm (see Figure 7.11). On the other hand, when the radio used in the laptop is configured with IEEE 802.11g, the RSSI results when the distance is lower than 67.5 m are surprisingly close to the ones obtained by the tablet. From this point until the furthest one the signal strength is always higher than -80 dBm. Therefore, the best results in terms of transmission power are achieved by the laptop when transmitting on the 5 GHz band. The second best ones are achieved when the same device uses the 2.4 GHz band. The third best RSSI is shown by the tablet, allowing interesting competitive results compared to the laptop for the complete experimentation (RSSI higher than -90 dBm). The lowest signal strength results are presented by the smartphone: so after 75 m the experimental results are lower than -90 dBm, offering an undesirable behavior. Applications needing more than 75 m would probably not rely on smartphone’s Wi-Fi, with the important exception of V2I (e.g., exchanging information with Wi-Fi spots). We must also mention that, even if these results were expected, we are here quantifying the distance ranges and communication power of regular smartphones, something difficult to find in the related literature. Chapter 7. Real World VANET Experiments 119 Finally, note that, although the signal strength decreases with the distance for all devices and frequency bands, the reduction is smoother and the signal strength is more stable when the radio used the 5 GHz band. This happens because the 2.4 GHz frequency band is way more crowded than the 5 GHz one, and therefore, the devices on the 2.4 GHz suffer much more interference than those on the 5 GHz. 7.3.4 VANET Communication Feasibility Experimental Results In this section, we present the experimental results, analyzing the exchange of data between the two moving vehicles by evaluating E2ED, PDR, and TDR (these metrics have been already defined in Section 4.1.2). Table B.18 in Appendix B, illustrates the whole results. Table 7.3 summarizes the results of the entire experiment by showing the average and the relative standard deviation of the three metrics studied. Thus, it is easier to conduct a comprehensive study of the performance of VANET communications by using smartphones, tablets, and laptops. The results are grouped by distances between the nodes (medium distance and long distance experiments). It also presents the global average results for the complete dynamic experiments set. TABLE 7.3: Average and relative standard deviation E2ED, PDR, and TDR results of the personal devices outdoor testbed grouped by the distance between vehicles. Connection E2ED (ms) PDR (%) TDR (KB/s) type Avg. Stdev. Avg. Stdev. Avg. Stdev. medium distance (from 25m to 75m) sph-sph 140.68 181.43% 83.11 32.21% 1.99 96.02% sph-tab 30.47 33.54% 81.33 27.22% 7.46 90.67% sph-laptG 13.06 51.68% 98.45 2.82% 18.26 80.90% tab-tab 56.43 52.82% 94.89 7.14% 3.91 69.69% tab-laptG 21.78 99.86% 92.67 11.63% 19.05 116.86% laptG-laptG 1.68 29.43% 98.45 3.81% 128.53 69.87% laptA-laptA 16.10 156.96% 40.76 18.29% 13.80 71.39% long distance (from 100m to 150m) sph-sph - - 0.00 0.00 0.00 0.00 sph-tab - - 0.00 0.00 0.00 0.00 sph-laptG 13.97 41.18% 86.45 14.54% 16.94 83.88% tab-tab 144.19 98.85% 43.67 68.73% 1.52 75.95% tab-laptG 64.71 87.39% 91.67 8.44% 9.11 146.81% laptG-laptG 3.06 63.29% 94.45 8.08% 72.86 67.42% laptA-laptA 156.01 63.80% 8.67 157.57% 0.44 192.93% global average (from 25m to 150m) sph-sph 101.33 251.88% 41.56 111.12% 0.99 167.79% sph-tab 15.70 65.10% 40.67 108.52% 3.73 161.92% sph-laptG 14.48 42.65% 92.45 11.71% 17.60 81.01% tab-tab 101.60 110.45% 63.99 59.38% 2.51 99.59% tab-laptG 47.59 101.79% 92.17 10.02% 14.08 133.09% laptG-laptG 2.51 63.59% 96.45 6.48% 100.71 76.01% laptA-laptA 38.42 259.38% 24.71 79.21% 7.12 135.65 % According to the results in Table 7.3, the communications in the testbed scenario in which both nodes are equipped with tablets (tab-tab tests) require longer E2ED than the scenario in which one node uses a smartphone and the other uses a tablet (sph-tab tests). This is not the expected behavior because the smartphone signal strength is lower than the one of the tablet 120 Chapter 7. Real World VANET Experiments (see Section 7.3.3), and therefore, our smartphone should show worse wireless communication capabilities than our tablets. The same occurs when we compare the E2ED of the tab-laptG and the sph-laptG tests. This can be explained by the road traffic density growth during the experiments with tablets (tab-tab and tab-laptG), as Figure 7.8.b illustrates. Thus, the data transfers suffer from the existence of obstacles between the nodes. Taking into account just the experiments carried out by using two laptops, we can observe that the average E2ED during the laptA-laptA tests is longer than ten times the E2ED during the laptG-laptG tests. This difference is significantly greater if we take into account the average E2ED during the long distance tests (E2ED laptA-laptA=156.01 ms and laptG-laptG=3.06 ms). This is principally because the performance of the network is more likely to be negatively affected by real world obstacles when it uses a higher frequency (Doefexi et al., 2003). Thus, the IEEE 802.11g standard is more promising than the IEEE 802.11a to perform competitive vehicular communications (average E2ED laptG-laptG=2.51 ms), while the market does not broadly assimilate the use of IEEE 802.11p. The data transfers performance suffers from variability of the communications provoked by the obstacles (e.g., other vehicles). This can be observed in the standard deviation results in Table 7.3. As the road traffic increased during the experiments involving the tablets, the tabtab and the tab-laptG transmissions presented larger deviation values than the sph-tab and the sph-laptG ones, respectively. The largest deviation value, which means the lowest robustness, is obtained by the laptop communicating on the 5 GHz band (laptA-laptA). Figures 7.12 and 7.13 summarize the experimental results in terms of PDR and TDR, respectively, grouped by the distances between the VANET nodes. Note that, in both figures, some bars that represent the results of sph-sph,sph-tab, and laptA-laptA tests do not appear because there has been no data information exchange due to the complete loss of communication, as it can be seen in Table 7.3. Analyzing the quantity of the successfully delivered data packets (PDR), we observe two clearly differentiated behaviors. On the one hand, all the VANET communications studied between devices that used the IEEE 802.11g standard (smartphones, tablets, and laptops) present similar and competitive results (PDR above 80%) for the scenarios in which the vehicles are separated by medium distance (see Table 7.3). However, only communications that involve laptops maintain such a high performance (PDR above 85%) when the distance passes beyond 100 m (long distance). On the other hand, when the vehicles exchanged data by using laptops configured with the IEEE 802.11a standard, the communications showed a limited performance since the PDR results were always below 50%. However, these nodes were not able to perform any data exchange when they were separated for distances greater than 100 m. FIGURE 7.12: Average PDR results of outdoor testbed of V2V personal devices communication. Chapter 7. Real World VANET Experiments 121 Laptops transferred the highest amount of data between each other transmitting on the 2.4 GHz band (see Figure 7.12). The average PDR for the laptG-laptG communications is 98.45% in medium distance and 94.45% in long distance. In any case, the global average PDR is higher than 90% for all tests in which at least one of the communication nodes is equipped with a laptop and is using the IEEE 802.11g standard (see Table 7.3). This is in sharp contrast to the results achieved by the same devices (laptops) when they communicate using IEEE 802.11a. The amount of delivered data are 40.76% and 8.67% for medium distance and long distance, respectively. In turn, the effective transmission range is shorter for the IEEE 802.11a communications than for the IEEE 802.11g ones. The main reason for this is that both standards use the same modulation (OFDM) and IEEE 802.11a transmits on higher frequencies (5 GHz over 2.4 GHz), reducing its communication capabilities against IEEE 802.11g (Al-Khusaibi et al., 2006; Paul et al., 2011). In terms of transmission data rates (TDR), there are considerable differences between the laptG-laptG communications and the other VANET communications studied here (see Table 7.3). For this reason, Figure 7.13 is shown in logarithmic scale. FIGURE 7.13: Average TDR results of outdoor testbed of V2V personal devices communication. Smartphones have the least competitive results in terms of TDR. In the sph-sph and sph-tab experiments, the nodes are able to exchange data in just medium distance scenarios by achieving average data rates of 1.99 KB/s and 7.46 KB/s, respectively. Although it seems a poor performance, the TDRs achieved for distances between 25 and 75 m are enough to deploy VANET applications for exchanging lightweight warning messages and traffic information with vehicles nearby and with the authorities via V2I. Tablets offer better TDR results than smartphones since tab-tab experiments achieve higher rates (its global average TDR 2.51 KB/s) and communicate with nodes at greater distances (up to 125 m). However, when one of the nodes is equipped with a laptop this does not hold true. The sph-laptG tests obtained more competitive TDR results than tab-laptG ones (global average TDRs, sph-laptG=17.60 KB/s and tab-laptG=14.08 KB/s). This is due to the increase in road traffic during the test that involved vehicles equipped with tablets, which negatively affected the communications. Taking into account the experiments carried out by transferring data by using laptops configured with the IEEE 802.11a standard, the performance is significantly different for both medium distance and long distance. When the distance is shorter or equal to 75 m, these communications achieved a competitive transmission data rate (average TDR laptAlaptA=13.80 KB/s). However, the TDR drops to 0.44 KB/s for long distance tests. 122 Chapter 7. Real World VANET Experiments As in the previously analyzed metrics, in the analysis of the data rates, the best results are achieved when the two VANET nodes use laptops using IEEE 802.11g to exchange data between each other. In the medium distance experiments the average laptG-laptG TDR is 128.53 KB/s and in the long distance ones the average TDR is 72.86 KB/s (see Table 7.3). These competitive transmission data rates may allow the exchange of multimedia information between the nodes, such as voice messages and videos. It is important to remark that this high TDR is achieved in distances up to 150 m. Broadly speaking, the feasibility of the communications carried out on the 2.4 GHz, vehicles equipped with laptops offer a practical solution for deploying VANETs right away, because this solution allows communications at distances greater than 150 m with the largest PDR and TDR and the lowest E2ED. This is not an unexpected behavior because the laptops are equipped with the highest gain antenna that is placed outside the car (see Figure 7.5.c). Analyzing the personal portable devices, both present competitive QoS and so could deploy useful VANETs with applications that do not require large transmission data rates. At the same time, tablets provided an effective communication coverage over 125 m, and smartphones a coverage up to 75 m. These relatively low performance results dramatically improve when devices with powerful wireless interfaces, such as laptops, are included in the VANET communication loop. Note that, even the results obtained when the radios used the 5 GHz band are less competitive, the IEEE 802.11p communications are still considered as a promising technology for vehicular environments. This standard provides several improvements that make it more robust than IEEE 802.11a. For instance, the reduction of the bandwidth of the channels from 20 MHz of IEEE 802.11a to 10 MHz of IEEE 802.11p, which duplicates the transmission time for a specific data symbol, allowing the receiver to better cope with the characteristics of the radio channel in vehicular environments (Lin et al., 2012). Finally, the importance of these outdoor testbeds is notable, because some of our experiments have suffered from the existence of real world obstacles producing a decrease in the performance of the wireless communications, leading to far from ideal results. A further detailed analysis of these experiments are presented in Toutouh and Alba (2016). 7.3.5 General Discussion on V2V by Using Lightweight Devices Widely available smartphones and tablets provide a set of facilities, which are required by VANET applications. Thus, they can be used to deploy VANETs even if specific on-board units are not available to most road users. This could accelerate an early development of vehicular networks to provide useful ITS services. In the light of the real-wold communications experimental analysis by using such devices, we can conclude that: smartphones allow useful information to be exchanged with nearby nodes in urban areas; tablets improve the smartphones’ communication capabilities and could be used to exchange more information, also on highways; finally, laptops are able to exchange multimedia information (audio and video) with the highest data rates and with any kind of communication partner node at distances up to 150 m. 7.4 Conclusions In this chapter, we have analyzed vehicular communications by defining two real world experiments carried out in open roads of the city of Málaga. They have been defined for two different main purposes: 1) confirming in vitro what we observed in silico about the use of optimized VANET protocols in Chapter 4and 2) evaluating the possibility of using the widely available lightweight devices in VANET communications. Chapter 7. Real World VANET Experiments 123 For the first purpose, we have focused on the VDTP file transfer protocol. Thus, we have analyzed the file transfers when configuring the protocol with the human experts parameterization and with the ones obtained by using NC. The human experts configuration performed the worst in exchanging files under the same conditions. The best results have been obtained when using the VDTP configuration computed by PSO. Therefore, the experimental results confirmed the QoS improvements of the optimized VDTP experienced by simulations. When the use of portable devices to deploy VANETs have been analyzed (instead of specific OBUs), we have observed that smartphones and tablets provide a set of facilities which can be directly utilized for VANET applications (e.g., GPS antenna). According to the VANET communications results, we have observed that smartphones can be used to exchange information with nodes located up to 75 m of distance. Nodes equipped with tablets provides a higher effective coverage over 125 m.Laptops equipped with a IEEE 802.11g Wi-Fi transceiver are able to exchange data with nodes at distances greater than 150 m, with the highest transmission data rates (higher than 100 kBytes/s). Besides this, when a laptop is included in the VANET communication loop the network dramatically improve the performance. It should be taken into account that the performance of VANET communications has not always followed the regular expected behavior. This can be explained by the variability of the road traffic density (vehicles act as obstacles for the signal propagation) and by the existence of a number of other wireless networks that interfered with the signal of our VANET. This kind of behavior, which influences the radio signal propagation, and therefore the communications QoS, is quite difficult to accurately represent and evaluate in simulators or emulators. Therefore, performing real world tests is strongly recommended to evaluate vehicular networks, even if it is difficult to master when conducting such experiments. The most important reason for going from one place to another is to see what is in between, and they took great pleasure in doing just that. NORTON JUSTER PART III: CONCLUSIONS AND FUTURE WORK 125 Appendix A List of Publications Supporting this Thesis Dissertation INthis appendix we present the set of works that have been published while this thesis work has been developed. These publications speak for the interest, validity, and impact on the scientific community and literature of the work contained in this thesis, since they have appeared in prestigious fora, and have been subject to peer review by expert researchers. It should be noted that the working hypothesis presented in this thesis dissertation was awarded with a second prize in the Doctoral Consortium Award 2013 given by Asociación Española para la Inteligencia Artificial (Spanish Association for Artificial Intelligence) (Toutouh and Alba, 2013a). We list our publications next. ISI JCR indexed journals [5]: J. García-Nieto, J. Toutouh, and E. Alba (2010). “Automatic tuning of communication protocols for vehicular ad hoc networks using metaheuristics”. In: Engineering Applications of Artificial Intelligence 23.5. Advances in metaheuristics for hard optimization: new trends and case studies, pp. 795–805 •Impact Factor: 2.207 •Category: –AUTOMATION & CONTROL SYSTEMS: Q2 –COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE: Q1 –ENGINEERING, ELECTRICAL & ELECTRONIC: Q1 –ENGINEERING, MULTIDISCIPLINARY: Q1 J. Toutouh, J. García-Nieto, and E. Alba (2012b). “Intelligent OLSR Routing Protocol Optimization for VANETs”. In: Vehicular Technology, IEEE Transactions on 61.4, pp. 1884–1894 •Impact Factor: 1.978 •Category: –ENGINEERING, ELECTRICAL & ELECTRONIC: Q2 –TELECOMMUNICATIONS: Q1 –TRANSPORTATION SCIENCE & TECHNOLOGY: Q2 J. Toutouh, S. Nesmachnow, and E. Alba (2013). “Fast energy-aware OLSR routing in VANETs by means of a parallel evolutionary algorithm”. In: Cluster Computing 16.3, pp. 435–450 •Impact Factor: 1.510 •Category: –COMPUTER SCIENCE, INFORMATION SYSTEMS: Q2 –COMPUTER SCIENCE, THEORY & METHODS: Q1 133 134 Appendix A. List of Publications Supporting this Thesis Dissertation J. Toutouh and E. Alba (2015c). “Parallel multi-objective metaheuristics for smart communications in vehicular networks”. English. In: Soft Computing. In Press., pp. 1–13. URL:http: //dx.doi.org/10.1007/s00500-015-1891-2 •Impact Factor: 1.271 •Category: –COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE Q3 –COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS: Q3 J. Toutouh and E. Alba (2016). “Light commodity devices for building vehicular ad hoc networks: An experimental study”. In: Ad Hoc Networks 37, Part 2, pp. 499–511 •Impact Factor: 1.530 •Category: –TELECOMMUNICATIONS: Q2 –COMPUTER SCIENCE, INFORMATION SYSTEMS: Q2 Peer review international journals [1]: J. Toutouh and E. Alba (2015b). “Metaheuristics for energy-efficient data routing in vehicular networks”. In: International Journal of Metaheuristics 4.1, pp. 27–56 CORE ranked intentional conferences [4]: J. Toutouh and E. Alba (2011a). “An efficient routing protocol for green communications in vehicular ad-hoc networks”. In: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation. GECCO ’11. Dublin, Ireland: ACM, pp. 719–726 •CORE Score: A J. Toutouh and E. Alba (2011c). “Performance analysis of optimized VANET protocols in real world tests”. In: Proceedings of the 7th International Wireless Communications and Mobile Computing Conference. IWCMC. Istanbul, Turkey: IEEE, pp. 1244–1249 •CORE Score: B J. Toutouh and E. Alba (2012a). “Green OLSR in VANETs with differential evolution”. In: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation. ACM, pp. 11–18 •CORE Score: A J. Toutouh, S. Nesmachnow, and E. Alba (2012a). “Evolutionary Power-Aware Routing in VANETs using Monte-Carlo Simulation”. In: Proceedings of The 10th International Conference on High Performance Computing and Simulation (HPCS 2012). Madrid, Spain: IEEE Computer Society Press, pp. 119–125 •CORE Score: B International conferences of Lecture Notes in Computer Science series [1]: Z. H. Mir, J. Toutouh, F. Filali, and E. Alba (2015). “QoS-Aware Radio Access Technology (RAT) Selection in Hybrid Vehicular Networks”. English. In: Communication Technologies for Vehicles. Ed. by M. Kassab et al. Vol. 9066. Lecture Notes in Computer Science. Springer International Publishing, pp. 117–128 Appendix A. List of Publications Supporting this Thesis Dissertation 135 Other peer review international conferences [8]: E. Alba, S. Luna, and J. Toutouh (2008). “Accuracy and Efficiency in Simulating VANETs”. In: Modelling, Computation and Optimization in Information Systems and Management Sciences, Second International Conference (MCO). vol. 14. Communications in Computer and Information Science. Metz, France - Luxembourg: Springer, pp. 568–578 J. Toutouh, J. García-Nieto, and E. Alba (2010b). “Optimal configuration of OLSR routing protocol for VANETs by means of Differential Evolution”. In: 3rd International Conference on Metaheuristics and Nature Inspired Computing, META 2010. D’Jerba (Tunissia), pp. 1–2 J. Toutouh and E. Alba (2011b). “Optimizing OLSR in VANETs with Differential Evolution: A Comprehensive Study”. In: First ACM International Symposium on Design and Analysis of Intelligent Vehicular Networks and Applications (DIVANet ’11). Florida, USA: ACM, pp. 1–8 J. Toutouh and E. Alba (2012b). “Multi-objective OLSR optimization for VANETs”. In: Wireless and Mobile Computing, Networking and Communications (WiMob), 2012 IEEE 8th International Conference on. Barcelona, Spain, pp. 571–578 J. Toutouh and E. Alba (2012c). “Parallel Swarm Intelligence for VANETs Optimization”. In: P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), 2012 Seventh International Conference on. IEEE, pp. 285–290 J. Toutouh and E. Alba (2013b). “Optimizing Telecommunications in Vehicular Networks with a Parallel Multiobjective PSO”. in: 22nd International Conference on Multiple Criteria Decision Making (MCDM2013), p. 295 R. Massobrio, J. Toutouh, and S. Nesmachnow (2015a). “A Multiobjective Evolutionary Algorithm for Infrastructure Location in Vehicular Networks”. In: 7th European Symposium on Computational Intelligence and Mathematics (ESCIM 2015). Cádiz, Spain, pp. 1–6 R. Massobrio, S. Bertinat, J. Toutouh, S. Nesmachnow, and E. Alba (2015b). “Smart placement of RSU for vehicular networks using multiobjective evolutionary algorithms”. In: 2nd LA-CCI Congress on Computational Intelligence (LA-CCI 2015). Curitiba, Brazil, pp. 1–6 National conferences [3]: J. Toutouh, J. García-Nieto, and E. Alba (2010a). “Configuración Óptima del Protocolo de Encaminamiento OLSR para VANETs Mediante Evolución Diferencial”. In: Actas del VII Congreso sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB’10). Valencia (Spain), pp. 463–471 J. Toutouh and E. Alba (2013a). “Computación Natural en Redes Vehiculares”. In: Doctoral Consortium de Multiconferencia CAEPIA - XV Conferencia de la Asociación Española para la Inteligencia Artificial (CAEPIA’13). Madrid (Spain), pp. 1740–1745 J. Toutouh and E. Alba (2015a). “Comunicación efficiente entre vehículos aplicando un algoritmo multi-objetivo paralelo”. In: Actas del VII Congreso sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB’2015). Mérida (Spain), pp. 503–510 Appendix B Complementary Results B.1 Data Transfer Between Vehicles with Optimized QoS Results This section includes different tables with complementary results obtained during the off-line optimization of the VDTP protocol (see Section 4.2). B.1.1 Parameterization of the Used NC Algorithms Table B.1 shows the results obtained in the preliminary parameters tuning procedure presented in Section 4.2.4. TABLE B.1: Different combinations and results of the preliminary parameter tuning of the algorithms used in FTC optimization problem. Algorithm Parameter Values Instances Results ϕ12.0 2.0 2.0 2.0 2.0 PSO ϕ22.0 2.0 2.0 2.0 2.0 w0.1 0.3 0.5 0.7 0.9 Urban 1.952 1.978 1.634 2.766 3.280 Highway 5.676 4.622 4.1761 5.283 6.045 DE Cr 0.1 0.3 0.5 0.7 0.9 µ0.9 0.7 0.5 0.3 0.1 Urban 4.027 2.647 2.241 1.866 1.742 Highway 7.255 5.622 4.776 4.734 4.663 GA Pcros 0.2 0.4 0.6 0.8 1.0 Pmut 0.8 0.6 0.4 0.2 0.1 Urban 2.701 2.245 1.953 1.908 2.077 Highway 5.216 4.848 4.380 4.490 4.609 ES Pcros 0.1 0.3 0.5 0.7 0.9 Pmut 0.9 0.7 0.5 0.3 0.1 Urban 4.920 3.878 3.031 2.606 2.151 Highway 7.836 6.877 6.240 5.783 5.923 SA T0.2 0.4 0.6 0.8 1.0 Urban 4.922 1.978 2.785 1.634 3.744 Highway 7.665 5.201 4.820 4.424 4.683 137 138 Appendix B. Complementary Results B.1.2 Scalability Analysis Table B.2 presents the results of the scalability analysis experimentation described in Section 4.2.4. The three last columns of the table show the time required to find the best solution (Tbest) for each VANET instance. TABLE B.2: Performance comparison in terms of average fitness and average optimization time (Tbest) of the scaled Urban VANET scenarios. Algorithm Average fitness ±Stdev. Tbest Scenario U1 Scenario U2 Scenario U3 Scenario U1 Scenario U2 Scenario U3 PSO 1.6346±17.74% 1.3920±20.34% 3.6763±12.06% 7.95E+03 5.93E+03 1.20E+04 DE 1.7423±21.33% 1.4504±13.00% 3.9186±18.93% 7.12E+03 1.10E+04 1.43E+04 GA 1.9086±11.84% 1.4100±8.76% 3.6829±13.75% 6.68E+03 9.81E+03 1.41E+04 ES 2.1517±5.88% 1.5462±38.95% 3.7799±16.47% 9.00E+03 8.99E+03 1.50E+04 SA 2.7850±31.30% 2.3880±42.74% 3.8143±3.30% 4.76E+03 3.40E+03 5.36E+03 B.1.3 Final Fitness Values Statistical Test results Table B.3 shows the Friedman ranking of the compared algorithms in Urban and Highway instances (the best ranked algorithm is in the top). TABLE B.3: Friedman Rank test results of NC solving FTC (confidence level set to 99%). Urban Highway Algorithm Rank Algorithm Rank PSO 1.27 SA 1.87 DE 1.83 GA 1.97 GA 3.07 PSO 2.63 ES 4.33 DE 3.57 SA 4.50 ES 4.97 Tables B.4 and B.5 contain the resulted p-value of applying the Wilcoxon Signed Rank test with a confidence level of 99% to PSO (the best ranked one for Urban instance) and SA (the best ranked one for Highway instance) in comparison with the remaining of algorithms, respectively. In this tables, the symbol Nmeans that there are statistical differences between the algorithms, and therefore, the best ranked algorithm is significantly better than the compared algorithm, whereas the symbol 4means that non-statistical difference can be assured between the two algorithms. TABLE B.4: PSO versus others Wilcoxon Signed Rank test in FTC (Urban scenario). Algorithm Test p-value DE N0.001 GA N<0.001 ES N<0.001 SA N<0.001 TABLE B.5: SA versus others Wilcoxon Signed Rank test in FTC (Highway scenario). Algorithm Test p-value PSO 40.371 DE N<0.001 GA 40.975 ES N<0.001 B.2 Optimization of the QoS of Proactive Routing Results This section includes different tables with complementary results obtained during the QoS off-line optimization of the OLSR routing protocol (see Section 4.3). Appendix B. Complementary Results 139 B.2.1 Parameterizations Analyzed of QoS Optimization of OLSR Table B.6 the OLSR parameter settings considered for comparison in the analysis in Section 4.3.5. Columns 2 to 4 contain three human expert configurations (#1, #2, and #3) proposed by Gómez et al. (2005); columns 5 and 6 contain the OLSR configurations of the RFC 3626 and the one obtained by the random search, respectively; columns 7 to 10 show the best OLSR configurations obtained by each one of the NC algorithms analyzed: PSO, DE, GA, and SA. TABLE B.6: OLSR parameterizations of the state of the art (Gómez et al. (2005)), the standard RFC 3626, and the best solutions in optimization algorithms validated in Section 4.3.5. Metric Human experts OLSR Optimized configurations #1 #2 #3 RFC RAND DE PSO GA SA HELLO_INTERVAL 0.50 1.0 4.0 2.0 3.730 8.477 8.909 8.568 9.005 REFRESH_INTERVAL 0.50 1.0 4.0 2.0 6.188 1.086 9.663 15.829 4.925 TC_INTERVAL 1.25 2.5 10.0 5.0 5.188 7.246 7.192 5.286 6.753 WILLINGNESS 3 3 3 3 4 0 1 1 0 NEIGHB_HOLD_TIME 1.50 3.0 12.0 6.0 5.400 16.924 67.238 83.771 80.334 TOP_HOLD_TIME 3.75 7.5 20.0 15.0 40.164 99.061 72.693 67.619 80.965 MID_HOLD_TIME 3.75 7.5 20.0 15.0 34.476 6.713 91.303 37.105 2.913 DUP_HOLD_TIME 30.0 30.0 30.0 30.0 31.515 71.938 21.572 16.268 16.705 B.2.2 Results of the Validation Experiments of QoS Optimization of OLSR Table B.7 presents for each OLSR configuration found using the optimization algorithms, the median values for each studied metric, computed in the simulations performed over the 54 different VANET scenarios. The results are compared with the values obtained in simulations performed with the standard OLSR configuration suggested by RFC 3626. The best median values obtained for each metric are marked in bold. TABLE B.7: Median results of the validation of the QoS optimized OLSR configurations. Scenario Configurations PDR NRL E2ED RPL U1 SA 99.95% 15.09% 2.13 ms 1.03 DE 92.58% 12.64% 4.34 ms 1.09 GA 99.95% 16.95% 2.10 ms 1.01 PSO 99.39% 12.73% 2.60 ms 1.05 RAND 94.41% 18.35% 17.16 ms 1.38 RFC 99.40% 22.28% 2.79 ms 1.05 U2 SA 84.01% 12.36% 8.99 ms 1.59 DE 85.77% 10.04% 9.23 ms 1.54 GA 85.70% 15.82% 3.81 ms 1.63 PSO 86.03% 12.36% 10.56 ms 1.54 RAND 84.98% 20.15% 21.11 ms 1.41 RFC 85.91% 23.94% 8.27 ms 1.18 U3 SA 74.85% 10.05% 44.38 ms 1.29 DE 78.29% 9.07% 19.19 ms 1.31 GA 75.08% 11.17% 44.95 ms 1.30 PSO 75.05% 9.97% 45.81 ms 1.28 RAND 69.76% 15.58% 398.42 ms 1.49 RFC 86.71% 20.65% 70.26 ms 1.05 Global SA 84.76% 14.56% 4.04 ms 1.35 Results DE 84.29% 11.98% 10.24 ms 1.34 GA 87.85% 16.32% 4.36 ms 1.34 PSO 86.73% 12.73% 8.12 ms 1.46 RAND 88.93% 19.21% 17.16 ms 1.38 RFC 89.56% 23.15% 6.06 ms 1.09 140 Appendix B. Complementary Results B.3 Power-aware of Proactive Routing Results This section includes different tables with complementary results obtained during the off-line optimization of the energy-efficiency OLSR routing protocol (see Section 4.4). B.3.1 Parameterization of the Energy-efficiency Optimization of OLSR Table B.8 presents the results for the combinations of pCand pManalyzed, reporting the average, relative standard deviation, and best values of fitness; the average energy and PDR, and the average gaps in energy and PDR with the standard RFC configuration. TABLE B.8: Results of parameter setting of the pGA for solving power-aware optimization of OLSR. (pC,pM) Fitness Metrics GAP RFC Avg. Stdev. Best Energy PDR Energy PDR (0.5,0.06125) 0.576836 0.31% 0.572319 3454.40 75.03% 39.19% -14.95% (0.7,0.06125) 0.577790 0.55% 0.571034 3446.11 75.01% 39.34% -14.99% (0.9,0.06125) 0.577498 0.39% 0.572754 3459.03 75.20% 39.11% -14.77% (0.5,0.125) 0.573733 0.21% 0.571268 3447.76 75.03% 39.31% -14.95% (0.7,0.125) 0.573778 0.24% 0.570946 3445.84 75.05% 39.34% -14.93% (0.9,0.125) 0.576217 0.14% 0.574546 3470.34 75.33% 38.91% -14.61% (0.5,0.25) 0.574279 0.13% 0.572724 3457.23 75.01% 39.14% -14.99% (0.7,0.25) 0.572346 0.15% 0.570118 3440.33 75.01% 39.44% -14.99% (0.9,0.25) 0.572408 0.17% 0.570351 3442.20 75.07% 39.41% -14.91% B.3.2 Statistical Analysis of pGA Table B.9 shows the results of the Kurskal-Wallis statistical test applied over the fitness results obtained by the pGAs solving power-aware optimization of OLSR. TABLE B.9: Statistical analysis of pGAs results in addressing power-aware optimization of OLSR. Statistical test Algorithm pGA-8 pGA-16 pGA-24 Kruskal-Wallis pGA-8 - 6.4×10−41.9×10−7 pGA-16 6.4×10−40.015 pGA-24 1.9×10−70.015 - B.3.3 Results of Validation Experiments of Power-Aware OLSR The validation analysis evaluated several metrics related to the energy-aware and QoS of the communication. From the point of view of the power consumption, the energy in transmitting (Esend) and receiving (Erecv) mode, as well as the total energy (Etotal) and total energy per vehicle (Etot×v) were studied. From the point of view of QoS, the studied metrics include the PDR, the E2ED (in miliseconds), the NRL, and the RPL . Table B.10 presents for each best OLSR configuration found using the three pGAs studied, the average values for each studied metric, computed in the simulations performed over the 36 VANET scenarios. Table B.11 summarizes the results of the Friedman and Wilcoxon statistical tests regarding the energy gaps. In the Wilcoxon test, the group of three values reported corresponds to the positive ranks, average positive ranks, and the sum of positive ranks for every pairwise comparison, respectively. Appendix B. Complementary Results 141 TABLE B.10: Results of the validation experiments of energy-efficient OLSR configurations. Configuration Energy metrics QoS metrics Esent Erecv Etotal Etot×vPDR E2ED NRL RPL Medium size (U2) pGA-8 12099.05 5265.45 17364.49 604.12 61.54% 62.39 3.36% 1.58 pGA-16 11902.02 5206.53 17108.55 589.17 63.64% 58.35 3.53% 1.43 pGA-24 11776.50 5094.87 16871.36 575.86 61.80% 55.04 3.34% 1.47 RFC 17918.45 8102.75 26021.20 876.91 70.22% 1356.18 25.46% 1.25 Large size (U3) pGA-8 14682.85 7030.52 21713.36 491.22 55.75% 505.30 3.98% 1.50 pGA-16 14864.78 7120.72 21985.51 505.51 57.63% 490.34 3.73% 1.48 pGA-24 14249.18 6762.22 21011.39 479.16 56.65% 483.62 3.57% 1.45 RFC 21574.81 16247.10 37821.93 877.75 64.00% 868.57 28.34% 1.15 Overall pGA8 13390.95 6147.99 19538.93 547.67 58.64% 283.85 3.67% 1.54 pGA-16 13383.40 6163.63 19547.03 547.34 60.64% 274.34 3.63% 1.46 pGA-24 13012.84 5928.54 18941.37 527.51 59.22% 269.33 3.45% 1.46 RFC 19572.25 12102.03 31674.29 877.33 67.89% 506.26 25.22% 1.20 TABLE B.11: Statistical analysis of the energy results. Statistical test Configuration pGA-8 pGA-16 pGA-24 RFC Friedman (Avg. rank) 2.19 1.94 1.92 3.94 Wilcoxon pGA-8 - (14, 19.8, 277) (16, 16.6, 266) (35, 19.0, 665) pGA-16 (22, 17.7, 389) - (16, 17.1, 274) (36, 18.5, 666) pGA-24 (20, 20.0, 400) (20, 19.6, 392) - (35, 18.9, 661) RFC (19.0, 1.0, 1) (18.5, 0.0, 0) (1, 5.0, 5) - B.4 Multi-objective Optimization of QoS Routing Results This section includes different tables with complementary results obtained during the multiobjective optimization of the QoS of AODV routing protocol (see Section 4.5). B.4.1 Parameter Configuration of pMOAs for addressing AODV MO-QoS Table B.12 presents the median hypervolume value for each parameterization analyzed for pNSGA-II and pSMPSO. TABLE B.12: Median hypervolume value for each parameterization of pNSGA-II and pSMPSO. pC pM 1 4L=0.023 1 2L=0.045 1 L=0.091 1 0.5L=0.182 pNSGA-II 0.3 0.757 0.749 0.751 0.801 0.5 0.734 0.760 0.810 0.776 0.7 0.752 0.776 0.786 0.810 0.9 0.832 0.770 0.767 0.776 pSMPSO 0.738 0.755 0.758 0.747