Prof Mohammed Ken Senouci

Prof Chen

Mr. François Véronique Veque

Prof. Guy Pujolle Colet

Prof Mühlethaler Paul

Dr Vincent Gauthier

Dr Abdallah M'hamed

Many

Khalifa Toumi

Amira Bradai

Chiraz Houaidia

Mohamed Ibn Kidhr

Emad Abd-Elrahman

Mohamed Abid

Oussama Soualah

Ali Mehdi

Amine Sboui

Na- Dia Othman

Wiem Sammoud

Aymen Amri

Mouna Selmi

Ben Sarra

Mo- Nia Frej

Mehdi Chikhrouhou

Meriem Bouleimen

Nicolas Yahiaoui

Fereshteh Gensollen

Mohamed Asgari

Mohamed Boutabia

Didi

Aziza & Farouk

Ben Azza

Mohamed-Haykel Mosbeh

Ines Zayani

Keywords: Vehicular Adhoc Networks, safety applications, dissemination protocol, analytical framework, congestion control, transmission power adjustment, data collection

Each day, Humanity loses thousands of persons on roads when they were traveling to work, to study or even to distract. The financial cost of these injuries is also terrifying: Some statistics evaluate this cost of vehicle accidents at 160 billion Euro in Europe each year. These alarming figures have driven researchers, automotive companies and public governments to improve the safety of our transportation systems and communication technologies aiming at offering safer roads and smooth driving to human beings. In this context, Vehicular Adhoc Networks (VANETs), where vehicles are able to communicate with each others and with existent road side units, emerge as a promising wireless technology able to enhance the vision of drivers and offer a larger telematic horizon. VANETs promising applications are not only restricted to road safety but span from vehicle traffic optimization like flow congestion control to commercial applications like file sharing and internet access.

Safety applications require that the alert information is propagated to the concerned vehicles (located in the hazardous zone) with little delay and high reliability. For these reasons, this category of applications is considered as delay sensitive and broadcast-oriented nature. While classical blind flooding is rapid, its major drawback is its huge bandwidth utilization.

Thus, in this thesis we are interested on enhancing vehicular communications under different scenarios and optimizations: First, we focus on deriving a new solution (EBDR) to disseminate alert messages among moving vehicles while maintaining it efficient and rapid. Our proposal is based on directional antennas to broadcast messages and a route guidance algorithm to choose the best path for the packets. Findings confirmed the efficiency of our approach in terms of probability of success and end-to-end delays. Moreover, in spite of the broadcast nature of the proposed technique, all transmissions stop very soon after the arrival of a packet to its destination representing a strong feature in the conception of EBDR.

Second, we propose a novel mathematical framework to evaluate the performance of EBDR analytically. Although most of the proposed techniques present in literature use experimental or simulation tools to defend their performance, we rely here on mathematical models to confirm our achieved results. Our proposed framework allows to derive meaningful performance metrics including the probability of transmission success and the required number of hops to reach the final destination.

Third, we refine our proposed broadcast-based routing EBDR to provide more efficient broadcasting by adjusting the transmission range of each vehicle based on its i ii distance to the destination and the local node density. This mechanism allows better minimization of interferences and bandwidth's saving. Furthermore, an analytical model is derived to calculate the transmission area in the case of a simplified node distribution.

Finally, we are interested on data collection mechanisms as they make inter-vehicle communications more efficient and reliable and minimize the bandwidth utilization. Our technique uses Q-learning to collect data among moving vehicles in VANETs. The aim behind using the learning technique is to make the collecting operation more reactive to nodes mobility and topology changes. For the simulation part, we compare it to a non-learning version to study the effect of the learning technique. Findings show that our technique far outperforms other propositions and achieves a good trade off between delay and collection ratio.

In conclusion, we believe that the different contributions presented in this thesis will improve the efficiency of inter-vehicle communications in both dissemination and data collection directions. In addition, our mathematical contributions will enrich the literature in terms of constructing suitable models to evaluate broadcasting techniques in urban zones.

Résumé

Chaque jour, l'humanité perd des milliers de personnes sur les routes pendant qu'ils se rendent à travailer, à étudier ou même à se distraire. Ce nombre alarmant s'accumule avec le coût financier terrifiant de ces décés: Certaines statistiques évaluent le coût à 160 milliards d'euros par an en Europe. Ces chiffres alarmants ont poussé les chercheurs, les constructeurs des automobiles et les gouvernements publics à améliorer la sécurité de nos systèmes de transport et des technologies de communication dans le but d' offrir des routes plus sûres et une conduite plus plaisible pour les usagers de la route. Dans ce contexte, les réseaux véhiculaires (VANETs), dans lesquels les véhicules sont capables de communiquer les uns avec les autres et avec aussi les infrastructures installées sur les routes, émergent comme une technologie sans fil prometteuse capable d'améliorer la vision des conducteurs et ainsi offrir un horizon télématique plus vaste. L'avènement des réseaux véhiculaires laisse entrevoir une myriade de possibilités, non seulement limitées à la sécurité routière, mais allant de la gestion du trafic routier (contrôle de congestion pour avoir un trafic fluide) jusqu'aux applications de divertissement (partage de fichiers, connexion internet).

Les applications de sécurité routière exigent que le message d'alerte soit propagé de proche en proche par les véhicules jusqu'à arriver à la zone concernée par l'alerte tout en respectant les délais minimaux exigés par ce type d'applications et la grande fiabilité des transmissions. Ces applications sont considérées très sensibles aux délais de bout en bout et se basent sur des transmissions en broadcast. Le broadcast aveugle est considéré la solution la plus rapide, néanmoins son principal inconvénient réside dans son énorme consommation de la bande passante.

Dans cette thèse, nous nous intéressons à l'amélioration de l'efficacité des communications inter-véhiculaires sous différents scénarios: Tout d'abord, nous nous concentrons sur le dévéloppement d'une nouvelle solution, appelée EBDR, pour disséminer les informations d'alertes dans un réseau véhiculaire tout en assurant des courts délais de bout en bout et une efficacité pour les transmissions. Notre proposition est basée sur des transmissions dirigées effectuées à l'aide des antennes directionnelles pour la diffusion des messages et un algorithme de guidage d'itérinaire afin de choisir le meilleur chemin pour le paquet. Les résultats obtenus ont confirmé l'efficacité de notre approche en terme de probabilité de réussite et délai de bout en bout. Par ailleurs, en dépit de son fonctionnement en diffusion, les transmissions de notre technique proposée s'arrêtent très rapidement après l'arrivée du paquet à la destination finale ce qui représente une caractéristique fondamentale dans la conception de EBDR.

iii Deuxièmement, nous proposons un framework mathématique ayant pour objectif l'évaluation des performances de EBDR analytiquement. Sachant que la plupart des techniques présentes dans la littérature utlisent les simulations ou les tests-bed d'expérimentation pour défendre leurs performances, nous nous appuyons ici sur des modèles mathématiques récursifs pour confirmer les résultats déja obtenus par simulation. Nos modèles analytiques permettent de dériver des métriques de performances significatives à savoir la probabilité de succès et le nombre de sauts requis pour atteindre la destination finale.

En outre, nous proposons une amélioration de notre protocole EBDR dans le but de fournir une diffusion plus efficace. Pour cela, nous nous basons sur l'ajustement de la puissance de transmission de chaque véhicule en fonction de la distance qui le sépare de la destination et la densité locale des noeuds. Ce mécanisme de contrôle de congestion permet de mieux minimiser les interférences et économiser de la bande passante. En plus, un modèle mathématique a été élaboré pour calculer la surface de la zone de transmission dans le cas d'une distribution uniforme des noeuds.

Finalement, nous nous sommes intéressés aux mécanismes de collecte de données dans les réseaux véhiculaires étant donné leurs implications positives sur l'efficacité et la fiabilité des communications inter-véhiculaires et la conservation de la bande passante. Notre approche est basée sur l'utilisation du principe du Q-learning pour la collecte des données des véhicules en mouvement. L'objectif de l'utilisation de ce mécanisme d'apprentissage est de rendre l'opération de collecte mieux adaptée et mieux réactive à la mobilité des noeuds et le changement rapide de la topologie du réseau. Notre technique a été comparée à des méthodes n'utilisant pas du "learning", afin d'étudier l'effet du mécanisme d'apprentissage. Les résultats ont montré que notre approche dépasse largement les autres propositions en termes de performances et réalise un bon compromis entre le taux de collecte et les délais de bout en bout.

Pour conclure, nous pensons que nos différentes contributions présentées tout le long de cette thèse permettrons d'améliorer l'efficacité des communications sans fil inter-véhiculaires dans les deux directions de recherches ciblées par cette thèse à savoir: la dissémination des messages et la collecte des données. En outre, nos contributions de modélisation mathématique enrichirons la littérature en terme de modèles analytiques capables d'évaluer les techniques de transmission des données dans un réseau urbain.

Mots clès: Réseaux Véhiculaires, applications de sécurité routière, protocole de dissémination, framework analytique, contrôle de congestion, ajustement de la puissance de transmission, collecte de données.

for the fun moments I have shared with you ! I also gratefully acknowledge the support of my country Tunisia for the contribution to this thesis financing. Thanks for giving me this opportunity to make my dream come true.

Last, I want to express my gratitude to my family for their unconditional love, support, and trust.

To my parents Salem and Souad, I am especially thankful for your love, your understanding and your continuous support. You gave me strengths on weak days and showed me the sun on rainy days.

Thanks for always believing in me.

To my brothers Ridha and Zied, and my sister Marwa, I am particularly indebted for your unconditional trust and sincere love. Thanks for always standing by my side during difficult times and for the fun moments I have shared with you !

In Honor of my grandfathers and grandmothers, List of Figures

Motivations

Since the mists of time, man tries to make his journeys safer and more pleasant.

Today, technical and cultural evolutions do not alter this need for road safety and smooth driving since human beings travel faster and farther. Therefore, during the last decades, public authorities and automotive companies have been involved in the improvement of the safety of our transportation systems by reducing the consequences of imminent accidents and decreasing the number of injuries on the road.

Nevertheless, most of these preventive measures (if not all) can only provide passive and limited security since they focus on the stage post accidents. In fact, tools like airbags and seat-belt tighteners lessen the impact of an accident but do not prevent it. This recognition of the inadequacy of these passive measures has directed the industrials to new and innovative perspectives that seek to avoid accidents and detect dangers in advance rather than minimize the damage. Drastic steps are already taken by automobile manufacturer to offer to drivers a larger telematic horizon and therefore enhance their range of awareness. If a collision is inevitable, active safety technology can proactively prepare the vehicle for the impact to reduce injuries. For example, sensors, present on the vehicles, are employed to measure and assess a vehicle's condition and environment, enabling the issuance of early warnings to drivers.

On the other hand, a remarkable and similar step in that direction is achieved by the networking research community by the emergence of vehicular networks, namely VANETs 1 . These adhoc cooperative safety networks leverage wireless communication 1 Vehicular Adhoc NETworks between vehicle nodes to continuously exchange messages with other moving cars in their proximity, and hence collect and share pieces of information about their surrounding environment. Thus, based on this context information and this larger telematic horizon offered to drivers, potential dangers can be detected in early stages and appropriate counter-measures can be initiated.

Given the unique capabilities of these smart vehicles and their potential impact on the road safety and driver awareness, the attention of car manufacturers, governments, and research institutions is with merit. Actually, many projects of national and international scale are under way worldwide aiming at developing efficient vehicular communication solutions for commercial use. VANETs promising applications are not only restricted to road safety but span from vehicle traffic optimization like flow congestion control, route optimization to commercial applications like file sharing, internet access and parking free places reporting.

Most of the applications envisioned for VANETs rely on multihop broadcastbased approaches to disseminate a message to a specific destination or geographic zone. Once an emergency situation occurs, it is vital to inform surrounding drivers as well as those who are farther as soon as possible. This situation needs practically a multihop forwarding operation of the message. Moreover, data broadcast is not only needed for road-safety scenarios but also for route and resource discovery services through periodic beaconing between vehicles.

So far, the topic of vehicle communications and broadcasting has been largely studied. A large number of dissemination techniques tailored to VANETs have been carried out. Most of them, are too complex for the context and the purpose of vehicular safety applications which required a simple conception and implementation to feet the network performances required by safety vehicular schemes. In addition, the mathematical aspect has only been studied by a small number of proposals present in literature in which theoretical-based evaluation performance model has usually been ignored.

In this thesis, we are interested on enhancing vehicular communications under different scenarios and optimizations. Our contributions span from broadcast-based routing technique, to transmission power improvement (MAC congestion control) and finally data collection schemes. Each of these contributions focus on a particular research field of the VANET world and tries to address the relevant challenges of nowadays VANET studies.

Contributions

The main contributions of these thesis are summarized below:

• Broadcast-based Routing technique for VANETs using Directional Antennas: This part of the thesis focuses on designing a novel broadcastbased routing technique for VANETs. The main goal is to reduce interferences between nodes and achieve lower end-to-end delays while remaining at the same time a simple approach . Therefore, our proposed technique EBDR uses directional antennas to achieve the broadcast transmission and is based on a route guidance algorithm to choose the path toward the destination. Simulations results confirm the efficiency of our proposal in terms of end-to-end delays and the probability of transmission success. Moreover, in spite of the broadcast nature of the proposed technique, all transmissions stop very soon after the arrival of a packet to its destination.

• Analytical framework dedicated to investigate EBDR performances:

The main goal behind this contribution is to investigate the performance of our proposed broadcast-based routing approach analytically. In fact, most of the proposed techniques present in literature use experimental or simulation tools to defend their performance and do not rely on mathematical models to confirm the achieved results: A phenomenon that explains the scanty efforts made in analytical modeling field. As a humble effort to enrich these research studies, our proposed framework allows deriving meaningful performance metrics including the probability of transmission success as well as the required number of hops to reach the final destination in the case of a linear propagation.

• Broadcast-based directional Routing scheme for VANETs with Transmission Range Adjustment: Enhancing the communication mechanism presented in the first contribution is the key purpose of this third effort. For that purpose, we investigate one of the known MAC layer congestion control mechanisms which is the power transmission control. In fact, power control has an important impact on the number of hidden terminals and the interferences between adjacent nodes. Hence, this mechanism can increase the reliability of communications and at the same time preserve the network bandwidth. We propose here a fully distributed scheme that allows nodes to set their transmission range based on their local densities and the distance to the destination.

Furthermore, an analytical model is derived to calculate the transmission area in the case of a simplified node distribution.

• Adaptive Data Collection Protocol using Reinforcement Learning for VANETs: As any research field, there is a lot of work being done on data collection techniques since they make inter-vehicle communications more efficient and reliable and minimize the bandwidth utilization. Nevertheless, our proposal stands as one of the few efforts that use Q-learning technique to collect data among moving vehicles in VANETs. The aim behind using the learning technique is to make the collecting operation more reactive to nodes mobility and topology changes.

Organization of the Thesis

The thesis is structured in the following way. First, an overview of the special characteristics of vehicular communications and an in-depth description of the standards and projects dedicated to promote vehicular networks are detailed in chapter 2.

Chapter 3 presents the design of our Enhanced Broadcast-based Routing Protocol (EBDR) and describes its operating principles. Simulation results are provided to evaluate the performance of our technique. The content of this work is published in [START_REF] Soua | Broadcast-based directional routing in vehicular ad-hoc networks[END_REF].

A novel mathematical framework to investigate analytically the performance of broadcast-based routing technique EBDR is presented in Chapter 4. It focuses on two main metrics: the probability of success for information to travel to a known destination and the required number of hops. In the models, recursive formulations are derived for the two previous criteria. Lower and upper bounds for our models are provided and computed by dynamic programming techniques. A comparison between simulations and analytical results is provided to confirm the precision of our bounds.

This work was published in [START_REF] Soua | Analysis of information relay processing in inter-vehicle communication: A novel visit[END_REF] Minimizing the inherent effects of high transmission power in vehicular networks is studied in chapter 5. We first highlight the related work that addresses the transmission range assignment techniques on a multihop wireless networks and then provide a full specification of our transmission range adjustment technique devoted to VANETs.

Our proposal is extensively evaluated in real road network-based simulations. In addition, the technique is evaluated using a simplified node distribution scheme, suitable to mobile adhoc network and an analytical model is derived to calculate the transmission area. Some contents of this chapter are published in [START_REF] Soua | Beamforming-Based Broadcast Scheme for Multihop Wireless Networks with Transmission Range Adjustment[END_REF].

Chapter 6 develops our proposed data collection technique devoted to VANETs.

The first section explores the most relevant strategies for data collection in the context of VANETs and details the motivation behind the use of such techniques. Then, we introduce our proposed Q-learning-based approach, present the functionalities and provide simulation results. The content of this chapter was published in [START_REF] Soua | Adaptive Data Collection Protocol using Reinforcement Learning for VANETs[END_REF] Chapter 7 concludes the thesis with a discussion of open issues and future work concerning inter-vehicle communications in VANETs. This is followed by a list of our publications and the bibliography.

Chapter 2

Vehicular Adhoc Networks: The big picture

Introduction

Over the last few years, the continuous advances achieved in wireless communications technologies have yielded to a plethora of new networking research fields aiming at extending connectivity to environments where wired solutions are not feasible.

As such, Vehicular Adhoc NETworks (VANETS) stand as one of the most attracting and promising research field for researchers, automotive companies and public governments given their commitment to providing safer roads and smooth driving. VANETs promising applications are not only restricted to road safety but span from vehicle traffic optimization like flow congestion control, route optimization to commercial applications like file sharing, internet access and parking free places reporting.

We provide in this chapter the concepts of vehicular networks by presenting the different communication types and the main components of these networks. Then, we give insight into ongoing worldwide projects which are contributing to the promotion of VANETs. The last part, will give an overview about the different networking architectures proposed to support such kind of networks.

Vehicular Networks

Vehicular adhoc networks are considered as an off-shoot of dynamic multihop wireless networks. Indeed, vehicles equipped with wireless radio interfaces are able to communicate with their direct neighbor provided that these latter are within their radio transmissions range. In addition, two communicating nodes that are far away from each other may rely on intermediate nodes to relay messages or may use a set of stationary units along the road called Road Side Units (RSUs). VANETs share several characteristics with general MANETs 1 [START_REF] Junhai | A survey of multicast routing protocols for mobile Ad-Hoc networks[END_REF], however, there are some important differences. In the following, we detail their characteristics as well as the different standardization efforts in this field.

Definition

Vehicular networks, or VANETs, are considered as a form of MANETs, deployed to provide communication within a group of intelligent vehicles (Smart vehicles). Vehicles can communicate either with other moving vehicles using V2V 2 communications or with fixed network nodes placed alongside the road (V2I To be part of such a network, a vehicle must be equipped with computational tools (Computing platform), wireless communications devices and geographic positioning

General Characteristics

VANETs are similar to MANETs since both of them support adhoc communications between mobile nodes in dynamic network scenarios. Nevertheless, research studies and achievements carried out in the field of MANETs can not be directly applied in the context of vehicular networks since these latter present unique features and specificities [6] [7]. Here are some properties that distinguish vehicular networks: proposals must take into account these specificities.

•
• Scalability: VANETs have the potential to grow to a very huge scale specially in urban areas where intersections and multi-lane roads are frequent. Hence, VANET protocols, especially those based on a dissemination process, have to face the large number of possible wireless collisions and interferences between nodes during transmissions [START_REF] Kosch | The scalability problem of vehicular ad hoc networks and how to solve it[END_REF].

• Processing and energy capacities: In contrast with other nodes in adhoc networks, moving vehicles supply, generally, sufficiently high electric and computing power. Therefore, the energy consumption, is a secondary factor in VANETs. In addition, each vehicle is equipped with an on-board unit (OBU)

that executes a single or a set of applications and supports a multitude of wireless technologies used to communicate such as WIFI 5 [13], WiMax 6 [14],

GSM 7 [15], Bluetooth [16], etc.

• Security and anonymity in the network: Data security and privacy stands as a major challenging problem in VANETs. Indeed, wireless communication, which is used in VANETs, is very vulnerable due to the fact that attacks can be played without requiring physical access to network infrastructure. Therefore, it is essential to design VANETs as robust as possible and secure them against attacks [START_REF] Al-Kahtani | Survey on security attacks in Vehicular Ad hoc Networks (VANETs)[END_REF] [18].

Related Projects

A large number of projects have been driven by institutions from all around the world. For instance, in 1992, the IVHS 8 of United States has committed its industries as well as the U.S transportation department to develop a national strategic plan to promote Intelligent Transportation Systems (ITS). Then in 1999, United States FCC 9 allocated a bandwidth of 75 MHz for inter-vehicles communications generally referred as DSRC 10 . Currently, as shown by Figure 2.4 many research activities, development and standardization of automotive communication are in progress.

In Europe, many research projects are beginning to form the basis of an intelligent transportation system. 3. Deployment strategies and business models for market penetration.

• SAFESPOT [START_REF] Safespot | [END_REF]: is interested in cooperative systems for road safety to prevent accidents by detecting potentially dangerous situations. The communication mode uses the future IEEE 802.11p [START_REF]IEEE Standard for Information technology-Local and Metropolitan area networks-Specific requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 6: Wireless Access in Vehicular Environments[END_REF].

• CVIS [21]: European research project aiming at designing, developing and testing the technologies needed to enable cars to communicate with each other and with the road infrastructure unit present in their neighborhood.

• SeVeCom [START_REF] Sevecom | [END_REF]: This project focuses on the security of future vehicular networks, including safety and anonymity of the vehicle-to-vehicle and Vehicle to Infrastructure communications.

• Projects in Japan: In the late 1980's, the public research institute of the Ministry of Construction launched the development of a Road Automobile Communication System (RACS) [START_REF] Takada | Progress of Road-Automobile Communication System[END_REF] jointly with several industrial partners. The main goal behind this project was to establish a system composed of: a navigation system, an information system and an individual communication system. With years, many other projects were launched aiming at providing safer roads.

For example, in 1996, VICS 11 [24] demonstrated successfully a dynamic route guidance technique. In addition, the Ministry of Construction and four expressway public corporations introduced Electronic Toll Collection (ETC) project in Japan. This group, initiated in 1995, has as main goal to promote ETC research studies. On March 30th 2001, with more than 63 tollgates installed in several areas of the country, the ETC service was functioning and offering its services to drivers. The main goals of this project are : the alleviation of traffic congestion near tollgates and eliminating the need to handle cash by drivers.

• Projects in USA: A reference Project in USA was called Automated Highway System (AHS) [25] in the early 90's by the National Automated Highway System Consortium (NAHCS) [START_REF] America | Strategic plan for intelligent vehicle-highway systems in the United States[END_REF]. The goal was to reduce highway crashes and their tragic consequences and help drivers avoid congestion roads. Another project related to cooperative assistance systems was initiated in the years 1998 to 2005 and is called Intelligent Vehicle Initiative (IVI) [START_REF]The Intelligent Vehicle Initiative: Advancing "Human-Centered[END_REF]. It aims at offering a cooperative active safety between moving vehicles and specially develop "human-centered" transportation systems. With these latter systems, intelligent vehicles will have the ability to give route directions to drivers and warn them from imminent collisions. They even aim at being able to take over driving in some situations.

Proposed Architectures and Related Protocols

Many organizations are involved in the standardization effort of vehicular technologies and their networking architectures. Communication architectures are usually based on the layered OSI-model. For VANETs, each category of applications requires different exigences in terms of delay, bandwidth consumption and QoS 12 . For instance, safety-critical applications [START_REF] Bai | Towards characterizing and classifying communication-based automotive applicat ions from a wireless networking perspective[END_REF] require strict latency and reliability requirements. On the other hand, infotainment applications are characterized by a huge bandwidth consumption. This variety of needs and requirements has led to proposing different new architectures offering different network access technologies, addressing schemes and protocols.

In the following sections, we will try to give an overview of the various proposed architectures and related protocols:

• CALM architecture [START_REF]International Organization for Standardization, Intelligent transport systems -Communications access for land mobiles (CALM) -Architecture[END_REF]: This architecture is proposed by the worldwide ISO [START_REF]International Organization for Standardization (ISO[END_REF] TC204/WG16 and it stands for Continuous Air-Interface, Long and Medium Range. The CALM main goal is to develop a standardized networking protocols stack that is capable of connecting vehicles and roadside systems continuously and seamlessly. Thus, CALM provides, as described by Figure 2.5, a multitude of communication media such as the cellular (GSM, UMTS 13 , etc), mobile, and WIFI networks and the DSRC [START_REF]Dedicated Short Range Communications (DSRC)[END_REF] or infrared (IR [START_REF]Infrared Radiation[END_REF]). The IEEE 1609.1 standard [START_REF]IEEE Trial-Use Standard for Wireless Access in Vehicular Environments (WAVE)-Resource Manager[END_REF] deals with the format of messages exchanged with the RSUs and neighboring vehicles as well as the data needed to be stored in the vehicles. It is related essentially to VANETs applications and specifies the need of each category in terms of delays and data.

In addition, the most important challenge related to the very dynamic nature of VANETS is that vehicles have to transmit or receive data from vehicles or RSUs as quickly as possible. Mac authentication mechanisms and traditional association techniques required to transmit data will obstruct this need to ra-pidity. Thereby, with WAVE, a vehicle does not require MAC authentication and association to send/receive messages. It only needs to receive the announcement of a RSU before starting its transmissions. The IEEE 1609.2 standard [START_REF]Security Services for Applications and Management Messages[END_REF] describes these security mechanisms needed in a vehicular environment.

The IEEE 1609.3 standard [START_REF]The Institute of Electrical and Electronics Engineers, IEEE Standard for Wireless Access in Vehicular Environments[END_REF] describes the WAVE Short Messages Protocol (WSMP) which replaces the TCP/IP stack and supports application priorities which mean that high priority data will be sent with minimum latency. The special message WSM can be transmitted on both CCH16 and SCH 17 channels. WAVE supports both IP and non-IP based applications. Non safety applications can use only the service channel SCH.

Mac and physic layers are defined by the IEEE 1609.4 standard [START_REF]IEEE Standard for Wireless Access in Vehicular Environments (WAVE) -Multi-channel Operation[END_REF]. it defines the multi-channel coordination and describes the prioritization mechanism between different traffics. It envisions the presence of a single Control CHannel (CCH), reserved for system control and safety messages, and up to 6 Service CHannels (SCHs) used to transmit non-safety data messages. According to the multi-channel coordination mechanism, all vehicles have to monitor the CCH during common time intervals and to switch to one SCH channel if they want to transmit non safety messages. Synchronization between nodes is achievable with the Global Positioning System (GPS) interfaces present in most moving vehicles.

VANETs Applications

Vehicular communications offer great potential for increasing road safety and driver awareness. In fact, according to relevant studies, 60% of accidents can be avoided if the driver had been alerted half a second before the collision [START_REF] Wang | Apparatus and method for motion detection and tracking of objects in a region for collsion avoidance utilizing a real-time adpative probabilistic neural network[END_REF]. Nevertheless, benefits are not restricted to safety standpoint but span to further horizons making use of a plethora of cooperating technologies. In fact, VANET applications can be divided into three categories: safety, traffic coordination and infotainment applications. In the following, we only concentrate on some key schemes of each category.

Safety Applications

These applications aim to minimize accidents and enhance driving safety by providing drivers and passengers with useful information including collision warning, fatal outcome, alarm of approaching vehicle, road sign alarms, etc. This category of applications is time-critical and so imposes strict real-time requirements on the proposed communications techniques. Among the scenarios belonging to this category, we can cite:

• Hazardous location warning: This application, as shown by Figure 2.8, provides information about events and roadway characteristics that are interesting to vehicles, drivers and passengers for a certain time and a specific area with sufficient anticipation. • Vehicle 2 Vehicle Cooperative Awareness: Vehicles share information by broadcasting or geocasting data to all surrounding neighbors or to vehicles within a geographic region. A Vehicle will execute an algorithm to assess the threat of other vehicles or passengers.

As illustrated by Figure 2.9, when a critical situation is detected, the algorithm warns the driver via visual or auditory displays. Thus, the driver will have

Traffic Related Applications

Applications in this category utilize vehicular communications to share traffic information between vehicles present in the street aiming at optimizing traffic flow and enhancing the driver experience. Several scenarios are proposed for this category, among which we can mention:

• Intelligent traffic flow control: In this use case (see Figure 2.11), the infrastructure is monitoring the streets, collecting traffic data and predicting congestion on roadways throughout a specific geographic region. Afterward, the RSU sends its expected flow situation to the vehicles traveling through its geographic zone. Vehicles use this information to alert drivers about expected delays or better routes that are available due to the traffic conditions [START_REF]European project REACT[END_REF].

Infotainment Applications

The main goal of this category of applications (see Figure 2.13) is to provide drivers with information, advertisements and entertainment during their journey. For example, such applications can provide Internet access, custom information services, file sharing and video streaming [START_REF] Soldo | Video Streaming Distribution in VANETs[END_REF]. Obviously, these applications are not delay sensitive applications and can tolerate delays since they are about offering luxury services to drivers.

Conclusion

The main goal behind this chapter was to present VANETs networks as a new network paradigm in the research field. Hence, VANETs emerge as a specialized form of MANETs with specific requirements related to the specific characteristics of such networks. A large number of research and standardization efforts have been carried out during last decades and was briefly presented in this chapter. We have also described the most important architectures dedicated to vehicular networks with a special focus on WAVE architecture as it was used as a reference networking stack in the next chapter. Moreover, we classified vehicular applications based on their impact on the road traffic and the requirements of each category in terms of delays and services. We presented for each category some key schemes to well understand the added value of each category. Next chapter will be dedicated to the presentation of our first contribution devoted to message dissemination in VANETs.

Introduction

Vehicular networks are promising safer roads and a smooth driving by implementing a several number of safety applications. These latter require that their alert information is propagated to the concerned vehicles (located in the hazardous zone) with a little delay and a high reliability. For these reasons, this category of applications is considered as delay sensitive and broadcast-oriented nature. In order to make this vision coming true, a plethora of multihop broadcast protocols have been proposed in the VANET literature.

The focus in this chapter is the challenges related to the dissemination process in vehicular networks and the different approaches developed to implement such kind of multihop data exchange between vehicles. In addition, we present our own approach to design a novel broadcast-based routing technique devoted to VANETs denoted as EBDR. EBDR combines route guidance technique and directional antennas to route the packet toward the final destination. The first step computes a path to the destination. The second phase uses directional antennas to broadcast the message into the chosen roads. Directional antennas with beamforming technique insures a minimization in wireless interferences as well as bandwidth consumption since only nodes located on the beamwidth of the antenna will be concerned by the forwarding transmission. The main goal behind the route guidance algorithm is to find a path for a packet to reach the destination. The EBDR protocol is extensively evaluated using a dedicated VANET simulator and real road maps. We compare and investigate the performance of our new approach with the flooding technique. Results highlight the efficiency of our proposal.

3.2 Dissemination in VANET: Specific Requirements and Prerequisites

Principe and Motivation

Dissemination traffic information in vehicular networks is a known problem. In contrast to routing technique, which usually refers to to the unicast data transmission from a source to a specific destination [START_REF] Li | Routing in vehicular ad hoc networks: A survey[END_REF] [46], traffic information in VANETs has a broadcast-oriented nature. Thus, it delivers an information to all nodes or a group of nodes within a certain geographic region. To reach the specified zone, the piece of information have to be propagated through the network using multihop relaying.

The main advantage of a broadcasting technique is that it does not depend on the destination ip address or the path to destination node [47] [48]. This weed out the problems of routing table maintenance, address resolution and topology management which are considered as major challenges in very dynamic networks such as VANETs.

Dissemination Related Challenges

The Scalability Problem

Referring to the definition given by Neuman in [START_REF] Neuman | Scale in distributed systems[END_REF], the scalability problem can be defined as the ability of a network to handle the addition of nodes or network size without being followed by a system failure or increasing the administrative complexity of the system. In a vehicular context, the increasing number of moving vehicles has a large impact on the network connectivity as well as the probability of packet collisions and wireless interferences. For example, in an urban area where the density of vehicles is very huge, information about traffic jam may be simultaneously detected by several neighboring nodes. Trying to send out the alert message to other nodes, a big number of forwarders compete to reserve the channel and hence the probability of collision increases dramatically. In [START_REF] Slavik | On the scalability of wireless multi-hop broadcast protocols with respect to density in VANET[END_REF], authors investigate the performance of some existing multihop protocols in terms of this scalability issue. For that purpose, they selected four broadcast techniques from the most known classes of dissemination approaches in VANETs, namely: distance-based method, stochastic broadcast, Multi-Point Relaying (MPR) and finally Advanced Adaptive Gossiping (AAG). For the simulation part, they used both ideal and real simulators dedicated to vehicular environment. Findings underline the efficiency and high adaptivity of both stochastic and distance-based broadcast protocols to node density in comparison to the other protocols.

Thus, information broadcast techniques in VANETs must deal with such problems to perform well in such conditions [START_REF] Wisitpongphan | Broadcast storm mitigation techniques in vehicular ad hoc networks[END_REF]. Most of works focus on adding probabilistic and timer-based suppression techniques when relaying the message aiming at decreasing the number of forwarders.

Traffic Differentiation

VANET applications, as mentioned before, are classified on three main categories.

Each category has its specific requirements on delay, bandwidth and message priority.

Hence, a priority mechanism for safety application must be assigned in order to respect delay times for alert messages when the source vehicle tries to access the channel. Moreover, even among alert messages, an order must be established since emergency situations might have different level of urgency. Thus, priority is not only application-dependent but also a situation-oriented [START_REF] Park | Dynamic Service-Channels Allocation (DSCA) in vehicular ad-hoc networks[END_REF].

Trust Issue

Vehicular networks are designed essentially to enhance the road safety by information exchange between moving nodes. One main consequence, is an inherent trust challenge to the information provided by vehicles to avoid fake alarm situations. In fact, a malicious driver may inject false warnings with the purpose of causing accidents or manipulating road traffic flow information to get rapidly to his destination. For that reason, a trust mechanism, joint to a broadcast technique, is worth considering to secure VANET communications [START_REF] Vinel | Trustworthy Broadcasting in IEEE 802[END_REF] [54] [START_REF] Bradai | A Framework Using IBC Achieving Non-Repudiation and Privacy in Vehicular Network[END_REF].

State-of-the Art: Techniques for Information

Dissemination in VANETs

Most of the applications envisioned for VANETs rely on multihop broadcast-based approaches to disseminate a message to a specific destination or geographic zone.

Once an emergency situation occurs, it is vital to inform surrounding drivers as well as those who are farther as soon as possible. This situation needs practically a multihop forwarding operation of the message. The basic dissemination technique used to achieve broadcast-based vehicular communications is the so-called flooding. Within this scheme, each node rebroadcasts every received message only once. Obviously, this can lead to a huge amount of redundant transmissions and numerous collisions. This phenomenon is known in literature as the broadcast storm problem [START_REF] Ni | The broadcast storm problem in a mobile ad hoc network[END_REF]. This situation may be aggravated with the increase of node density leading to the scalability problem. Therefore, urgent messages requiring little delay are prevented from accessing the medium and hence drivers are not informed in time. A good multihop broadcasting protocol must be able to resolve these issues.

In order to increase the efficiency of broadcast-based vehicular communication and guarantee reliable transmissions, rather sophisticated approaches have been developed during last years. These so-called "intelligent flooding" techniques aim at reducing the number of redundant rebroadcast packets. This is typically achieved by selecting only a set of nodes to relay the urgent information as opposed to letting each vehicle rebroadcast it.

Basically, these intelligent flooding techniques can be broadly divided into three main categories: "distance based", "probability based", and "neighbor knowledge based". In other studies such as [START_REF] Panichpapiboon | A Review of Information Dissemination Protocols for Vehicular Ad Hoc Networks[END_REF] [58], authors classify the existing techniques on other classes: single-hop and multihop broadcasting, or geocast and unicast broadcasting. In the following sections, we detail in-depth the relevant proposed approaches for each category.

Distance-based Broadcast Protocols

The distance-based broadcast protocols are a class of protocol exploiting the knowledge of some geographic information about the destination node to improve the efficiency of the relaying operation. Generally, a different waiting delay, prior to rebroadcasting, is assigned to each node that has received the alert message. The vehicle with the shortest waiting delay obtains the highest priority in the rebroadcasting operation [START_REF] Jerbi | Towards Efficient Geographic Routing in Urban Vehicular Networks[END_REF] [START_REF] Fasolo | Smart Broadcast algorithm for intervehicular communications[END_REF]. Typically, this waiting delay is inversely proportional to the distance between the sender and the relaying node. By doing so, the packet follows usually the path that maximizes the packet progressing distance. To tackle the problem of redundant transmissions, other vehicles, waiting to rebroadcast the message, cancel their sending when they hear that the same information was sent by another node. Obviously, such protocols assume to know the position of each vehicle to make the relay decision by using GPS receivers.

In the following, we detail a variety of proposed distance-based broadcast approaches.

The Improved Greedy Traffic-Aware Routing Protocol

In [START_REF] Jerbi | Towards Efficient Geographic Routing in Urban Vehicular Networks[END_REF], authors propose an intersection-based geographical routing technique for urban VANET, namely GyTAR. To find a suitable route for the packet to reach the final destination, GyTAR uses three main mechanisms: 1) a traffic density estimation mechanism which is based on the traffic information exchanged between moving vehicles. This step needs a segmentation of the roads in adjacent cells where the vehicle density is locally calculated by a cell leader. Afterwards, 2) A dynamic selection of the intersections through which the messages will be forwarded is triggered. The selection of these intermediate intersections is based on a score value. This latter is determined based on the traffic density estimation in this road and the curve-metric distance to the destination. Hence, the intersection with the highest score corresponds to the closet intersection to the final destination with the highest vehicle density. The final phase corresponds to 3) the selection of the next forwarding node. In this step, the closet vehicle to the destination intersection will be selected as next hop. In addition, GyTAR uses carry and forward approach in order to recover from the local maximum. This mechanism of intersection selection offers a maximum connectivity and thus increases the packet delivery ratio and at the same time decreases the end-to-end delay. Simulations findings have proven the efficiency of GyTAR compared to others techniques. However, GyTAR introduced a small overhead when computing the local density values: the protocol requires an exchange of the cell density packet (CDP) between groups leaders to have a big picture of the road density. An analytical model to evaluate their technique will also strengthen the work carried out by authors.

Spatial Distribution and Channel Quality Adaptive Protocol

To deal with the effect of node density and wireless channel quality, Slavik and al.

propose a multihop wireless broadcast scheme for vehicular networks called DADCQ [START_REF] Slavik | Spatial Distribution and Channel Quality Adaptive Protocol for Multihop Wireless Broadcast Routing in VANET[END_REF]. This protocol uses the distance heuristic method to select forwarding nodes.

In their proposal, they are interested on the distance to the nearest neighbor from which a node has received the broadcast message. Their method appeals to the basic intuition that there is no interest for a vehicle, in terms of additional coverage, to rebroadcast the message if it is received from one node very close to it. If this distance is greater than a specific threshold value, then the moving node relays the packet.

In addition, they adapt their decision threshold function to three independent input parameters: the density of nodes, the node clustering factor and the Rician fading parameter. The goal is to make this threshold function adaptive to the environmental conditions. The general expression for the threshold function was:

D c (N ) = D max -βe αN
where D max , β and α are local parameters that depends on external factors such as node distribution and channel quality.

The downside of this statistical protocol is that it is stochastic in nature and cannot be proven to always give full reachability. In fact, the performance of this technique depends heavily on several local parameters as well as node density, spatial distribution pattern and wireless channel quality. Thus, the guarantee of better global performance is not generally obvious.

TRAck Detection Protocol

Sun, Feng and al. in [START_REF] Sun | GPS-based message broadcast for adaptive inter-vehicle communications[END_REF] proposed the TRAck Detection protocol (TRADE) which classifies the neighboring vehicles into three main categories according to their position on the road; same road-ahead, same road behind and different road. Then, the algorithm selects nodes from each group in order to forward safety messages; the farthest vehicles from same road ahead and same road-behind and all vehicles from different road are chosen to rebroadcast the alert message. The neighbor GPS information can be acquired through beacon or periodical short GPS message exchanges.

The main drawbacks of TRADE protocol is that it requires explicit exchanges of GPS position information between neighboring nodes which still consumes precious wireless bandwidth. In addition, this technique assumes using very precise GPS devices to classify the moving nodes in the three categories specified early which is not always guaranteed.

Zone Based Forwarding Protocol

In [START_REF] Singh | Information dissemination in VANETs using zone based forwarding[END_REF], authors propose a zone forwarding scheme for information dissemination in VANETs (ZBF). The proposal tackles the problem of retaining the message in the target zone for the duration of the effect time. Thus, the algorithm divides the effect area of the alert message into segments of length the transmission range. A forwarder, a vehicle which is elected in each segment, is assigned the task of broadcasting the information to other neighboring vehicles. When the forwarder is about to leave the zone, a new forwarder will be elected. In fact, during broadcast operation, a vehicle can be in one of three modes: Receive, Forward, or Relay. In the Forwarding mode, the vehicle is broadcasting alert message to neighboring nodes. When the Forward is about to leave its zone, it become a Relay and initiates election of a new forwarder.

Vehicles receiving the broadcasted message are in Receive mode.

Nevertheless, this method can only be applied to highway scenarios and requires very precise positioning system in order to determine in which zone each vehicle belongs to. In addition, the proposed technique introduces an important overhead since it uses three type of messages: Info, Query and a Reply messages to implement the broadcast mechanism.

Highway Multihop Broadcast Protocol (HMB)

M. Barradi et al. propose in [START_REF] Barradi | Highway multihop broadcast protocols for vehicular networks[END_REF] a new vehicular multihop broadcast protocol called Highway Multihop Broadcast (HMB) that addresses several issues related to vehicular environment as well as the broadcast storm, hidden node and reliability problems.

To tackle these challenges, authors make use of a mechanism similar to RTS-CTS 1 [START_REF] Xu | How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks[END_REF] to prevent hidden node problem called Initial Clear to Broadcast (ICTB) and Forwarded Clear to Broadcast (FCTB). Regarding the reliability factor, a passive acknowledgment is simply implemented by identifying every frame by its ID, original MAC ID and the last sender ID. In fact, when forwarding, the relay nodes update only last-sender ID. The frame sender hears also the forwarded frame and compares the frame ID and the last sender ID. The decision to retransmit the message or not is based on the distance from the source, received signal strength and the speed deviation between sender and forwarder and the priority of received packets.

However, this proposal is only dedicated to highway scenarios and might encounter several difficulties in urban schemes. In addition, using the handshake mechanism introduced an additional overhead in the network with each forwarding operation.

Efficient Directional Broadcast Protocol (EDB)

EDB [START_REF] Li | A Distance-Based Directional Broadcast Protocol for Urban Vehicular Ad Hoc Network[END_REF] is a distance-based multihop broadcast protocol for VANETs where the furthest receiver is responsible to forward the packet in the opposite direction where the packet arrives. Furthermore, EDB exploits directional antennas [67] and proposes that each vehicle be equipped with two directional antennas each with the beamwidth of 30 degree. The proposal is composed of two phases: directional broadcast on the road and directional broadcast at intersections. The first phase deals with forwarding alert messages on roads by selecting the furthest away receiver behind. The delay waiting time is computed as following :

W T = (1 - D R ) * M axW T
Where R is the transmission range and M axW T is a configurable parameter which can be adjusted according to the density of vehicles. After the expiration of this waiting time, the concerned vehicle immediately sends an ACK packet. This is useful to inform other neighboring nodes to cancel their retransmission task. In addition, the relay vehicle keeps rebroadcasting the packet if no other node retransmits the packet within an interval if time equal to M axW T .

1 Request To Send-Clear To Send

In the second phase, a non-moving node, namely directional repeater, placed on intersections and equipped with several directional antennas, is responsible to retransmit received alert packets on the different intersection segments.

Obviously, the assumption of having vehicles with multiple directional antennas restricts the use of such approaches.

Efficient Road-based Directional Broadcast Protocol (ERD)

To deal with the broadcast issue at road intersections, Tung et al. propose a directional broadcast protocol, by using precise GPS navigation system, called Efficient Road-based Directional broadcast (ERD) [START_REF] Tung | An efficient road-based directional broadcast protocol for urban VANETs[END_REF]. It groups vehicles based on their road segments (single road case, node near an intersection case and node in an intersection) and selects relay nodes for each group. The protocol improves packet efficiency significantly but it still depends on a very precise position navigation system and an accurate road digital map which are not always present on each vehicle.

Probability based Broadcast Protocols

The major shortcoming of position-based broadcast protocols resides on the need of having information about the network topology or the geographical position of vehicles by using GPS devices. To countermeasure these drawbacks, a different approach was undertaken by the research community to achieve the same goal of position-based broadcast protocol without the need for a lot of information exchange. Thus, a probability based approach was designed to make nodes only retransmit alert packets with an adjustable probability p computed by each node in a distributed manner:

(i) Probabilistic in the sense that every intermediate node will decide to relay the packet or not based on a certain probability assignment function P AF ;

(ii) Distributed means that each vehicle makes a rebroadcast decision individually without coordination with other nodes and usually based on local information.

The aim of this mechanism is to limit the number of retransmissions. One of the main challenges of these techniques resides on constructing an optimal probability assignment function. Some techniques use a simple pre-defined fixed probability while others sophisticated approaches adjust this probability function based on some local parameters such local density, etc. Next paragraphs review some of the probabilistic-based multihop broadcast protocols for VANETs.

Weighted p-persistence Protocol

In [START_REF] Tonguz | Broadcasting in VANET, Mobile Networking for Vehicular Environments[END_REF] and [START_REF] Wisitpongphan | Broadcast storm mitigation techniques in vehicular ad hoc networks[END_REF], three probability-based broadcast schemes are proposed: weighted ppersistence, slotted 1-persistence and slotted p-persistence schemes. They are meant to be used at the network layer and mitigate the broadcast storm problem in well connected networks. The performance of this technique was evaluated in terms of packet loss rates, overhead and reachability. In this approach, a node that receives the emergency message for the first time, computes individually its own forwarding probability based on its distance progression beside the transmitter. The forwarding probability can be expressed as follows:

p ij = Dij R
where D ij refers to the distance between node i and node j, and R represents the transmission range of communicating vehicles. By doing so, the vehicle presenting the higher progression toward the destination will possess the highest probability to transmit. Similar approach was undertaken in [START_REF] Slavik | Stochastic broadcast for VANET[END_REF] where the probability function is proportional to the distance between the source and the receiving node.

Irresponsible Forwarding Protocol

In [START_REF] Busanelli | Efficient broadcasting in IEEE 802.11 networks through irresponsible forwarding[END_REF] and [START_REF] Busanelli | Efficient MultiHop Wireless Communications In VANETS[END_REF], authors design a probabilistic approach, denoted the Irresponsible Forwarding protocol (IF), within the retransmission probability function depends on the distance between the sender and the transmitter and the vehicle local density (spatial density of its neighbors). The exact expression of the probability follows the following function:

p = e (-ρs(z-d) c )
The first observation is that the given probability function is quite different from the existing approaches where the probability is a linear function of the distance and not exponential. ρ s refers here to the vehicle density, z is the transmission range, d is the distance between the sender and the vehicle, and finally c represents a tunable coefficient which can be selected to "shape" the probability of rebroadcasting. The key idea behind this new expression of the probability function resides on that a candidate node implicitly evaluates the probability of having another node in the vicinity able to retransmit the message. If this probability is high, then the node "irresponsibly"

chooses not to rebroadcast and gives way to the other node to retransmit. As it can be observed from the probability function given above, this latter decreases as the distance between the sender and the vehicle decreases (the receiving vehicle is very close to the sender and, therefore, it should let the other node take the responsibility of rebroadcasting). Moreover, when the network is sparse, the rebroadcast probability is important in order to ensure a complete reachability (the vehicle is not well surrounded by neighbors, thus it have to take the responsibility to rebroadcast).

AutoCast

Introducing the impact of local density of vehicles in the retransmission probability function is the aim behind the approach presented in [START_REF] Wegener | Efficient MultiHop Wireless Communications In VANETS[END_REF]. In fact, the probability function follows the expression below:

p = 2 N h × 0.4
where N h is the number of the surrounding one hop vehicles. We observe that when the local density of vehicles decreases, the probability to retransmit the emergency message by the concerned vehicle increases. This mechanism allows a better reachability for the packets in sparse networks. We can also remark that the above equation works only for N h ≥ 5. Authors do not give any details about the behavior of the probability p when N h < 5 which relieves a weak point for this effort.

Neighbor-knowledge-based Protocols

These approaches postulate that all moving vehicles know the identity of all their neighboring nodes. They assume a periodic exchange of messages between vehicles in order to have a view of their neighborhood and its mobility. A neighbor table is maintained at each node and is updated periodically to use it to designate the next forwarder.

The basic example of such kind of protocols is the "flooding with self pruning" technique where each node includes the list of its neighbors when broadcasting messages. Upon receiving such a message, vehicles compare the list with their corresponding neighbors and retransmit the packet if new nodes would be reached. In the following, we list some works in this category.

R-OB-VAN Protocol

Authors in [START_REF] Laouiti | Reliable opportunistic broadcast in VANETs (R-OB-VAN)[END_REF] present a reliable opportunistic broadcast technique called R-OB-VAN that overcomes the problem of message delivery in VANETs while maintaining a low average end-to-end-delay. The proposed protocol is composed of two main components: The first functionality consists in the forwarding mechanism that is handled by the OB-VAN technique [START_REF] Blaszczyszyn | Opportunistic broadcast in VANETs (OB-VAN) using active signaling for relays selection[END_REF], while the reliability component aims at ensuring that blocked vehicles get the emergency message despite shadowing. The first component that is supported by OB-VAN protocol, selects the vehicle that offers the best progression toward the destination to act as a relayer. In addition, it uses active signaling bursts to make this choice: after receiving the packet, each vehicle must transmit a short acknowledgment made up of signaling bursts and when a vehicle detects a signal during its any of its listening intervals, it quits the selection process.

The second component (reliability functionality) tries to make sure that even if a vehicle is unable to receive messages from the selected relays, other vehicles will take the responsibility to inform them. For that purpose, they developed three solutions to ensure this functionality. The proposed techniques are based on a two hop neighbor information in order to solve the problem of shadowing. The first variant is based on the requirement that vehicles know the number of neighbors that each neighboring one-hop vehicle has. On the other side, second variant make this decision more dynamic by taking into account the density of the network. Finally, the third approach is based on the requirement that nodes exchange their one-hop neighbor tables with their surrounding vehicles as well as their locations.

Simulation results have shown that variant 3 is able to maintained a higher delivery ratio than the other approaches while offering at the same time a lower delay. The major drawbacks of these techniques is the overhead caused by the periodic exchange of neighbor tables between vehicles even this overhead is little. In addition, variant 1 and 2 have parameters that can cause them to fail if they are chosen improperly.

The absence of a theoretical model that can validate their proposal still constitutes a missing point in this good effort.

DV-CAST technique

An outstanding example is the DV-CAST technique [START_REF] Tonguz | DV-CAST: A distributed vehicular broadcast protocol for vehicular ad hoc networks[END_REF]. The authors focus on highway scenarios and implement a distributed protocol, namely DV-CAST, that can operate in both dense and sparse traffic regimes. Their technique relies on the local one-hop neighbor information obtained via the use of periodic hello messages aiming at assisting DV-CAST in determining how the packet should be handled. DV-CAST protocol concept consists in three main functions: neighbor detection, broadcast suppression and store-carry and forward mechanisms. The first component estimates the local topology by monitoring hello updates received from one hop neighboring nodes.

By comparing its GPS information against the neighbors' information, the concerned node is able to classify them into different classes regarding their relative position.

In dense scenarios, DV-CAST performs broadcast suppression techniques to reduce the broadcast storm problem: authors make use of the weighted p-persistence scheme to handle this challenge. On the other side (on totally disconnected neighborhood), authors cope with such an extreme situation using the store-carry-forward mechanism to route the message to the zone of interest. Despite the little overhead introduced by DV-CAST, this latter still requires a precise positioning system (GPS) to classify neighboring vehicles in different categories (front, back, and opposite directions). In addition, there is an additional overhead introduced in order to add the GPS positions in the periodic hello messages even it is considered minimal.

DSP Technique

Another work carried out by Dai et al. in [START_REF] Fei | Efficient Broadcasting in Ad Hoc Wireless Networks Using Directional Antennas[END_REF] where a directional broadcast protocol is proposed for adhoc networks. Their proposal, called DSP, is a generalization of an existing localized broadcast protocol using omnidirectional antennas. Compared with its omnidirectional predecessor, DSP achieves lower broadcast redundancy and conserves bandwidth and energy consumption by switching off transmission in unnecessary directions. Nevertheless, DSP is based on 2-hop neighborhood information which requires an additional overhead in the broadcast transmission.

Proposed Technique: EBDR

As mentioned in Section 3.3, several multihop dissemination protocols have been proposed for VANETs with good characteristics and acceptable performance. Nevertheless, most of these approaches are empirical in the sense that they are not strengthened by a theoretical background to confirm their efficiency. In fact, they rely on practical test beds or simulations to demonstrate their performance. For our proposal EBDR, the performance part consists of two directions: The first direction tries to study the performance of EBDR by conducting several real-road simulations based on a well known vehicular simulator. The second approach, which is described in the next chapter, investigates the performance of our proposal analytically. Our novel theoretical framework offers some insights about the behavior of EBDR and allows to derive several performance metrics including the probability of transmission success as well as the required number of hops to reach the final destination.

In this section, we first focus on broadcast communications based on directional antennas to disseminate messages in a vehicular wireless multihop network conditions.

We propose an Enhanced Broadcast-based Directional Routing (EBDR) scheme that combines broadcast and directional transmission techniques to route a message to a known destination. A communicating node, using EBDR, calculates its itinerary based on a route guidance algorithm and then disseminates the message on the set of nodes within its transmission range and located in its beamforming area. EBDR technique does not introduce overhead, is extremely simple and it only requires the presence of a GPS receiver and a directional antenna in the vehicle. Our proposal aims to achieve good ratios of delivery while significantly reducing the bandwidth consumption and redundancy. The efficiency of our proposal is studied using realroad simulation scenarii.

In the following, we present the key properties of our antenna model. Then, we detail the functionalities of our proposed technique and present relevant simulation results.

Directional Antenna Model

In the study of VANETs, several types of smart antennas have been proposed to form directional transmission and/or reception beams [START_REF] Ramanathan | On the performance of ad hoc networks with beamforming antennas[END_REF]. In our modeling approach, the directional antenna is modeled as a circular sector with an angle θ and a radius equal to the transmission/reception range r. As shown in Fig. 3.1, the directional antenna gain is within the angle θ, which represents the beamwidth of the antenna. Hence, the gain outside the sector limited by θ is approximated to zero.

A real directional antenna pattern is formed by a mainlobe representing the direction of the maximum radiation and other smaller backlobes resulting from inefficiencies in the antenna design. For simplicity, we ignore the existence of such backlobes in our modeling approach. In addition, each vehicle can point its smart antenna in any direction. We assume also that each node possesses only one directional antenna.

Traditionally, a smart antenna offers two reception modes: omnidirectional and directional modes. While the former allows each vehicle to receive a packet from all its neighbors, the latter limits the receiving directions to a single one limited by the angle θ. Throughout the rest of this chapter, we assume transmissions in a directional mode and an omnidirectional reception mode.

EBDR Conception

In this section, we describe our proposed scheme for broadcast-based routing using directional antennas. The functioning of our technique is composed of two main phases. First, a route guidance algorithm is used to select a route from the source S to the destination D. This route, carried out by the route guidance algorithm, is composed of a set of intermediate destinations, called D i , through which the message must pass. These D i can be a road intersection, a turning point, an RSU, etc. The final destination can be a simple node or a geographic zone. This algorithm tries to select a short geographical path while ensuring the maximum covered distance and the minimum handovers. In fact, on a VANET network, vehicles follow roads and highways along their journeys and don't move randomly. Hence, it is mandatory to select the best path linking S and D according to specific criteria. This path is composed of several number of edges referring to geographic roads. Afterward, once the route is selected, we use the directional broadcasting to let the message reach the final destination [START_REF] Soua | Broadcast-based directional routing in vehicular ad-hoc networks[END_REF].

Route Guidance Algorithm

We consider a VANET environment where nodes are positioned along roads and highways. Vehicles are able to determine their geographic position using a Global Positioning System (GPS) receiver. We assume also that vehicles are equipped with a digital map that reflects the road structure of a city and can run the route guidance algorithm aiming at providing a suitable route.

Generally, such kind of algorithms are already used by some tools such as Mappy [START_REF] Mappy | [END_REF]. Indeed, an algorithm proposed by Ghedira et al . [START_REF] Ghedira | A Novel Route Guidance Algorithm with Maximum Coverage and Minimum Handover for Vehicular Networks[END_REF] uses geographical information such as vehicle location and the hotspot map to route vehicles toward a destination. It builds an oriented graph where nodes represent a portion of a route covered by a hotspot and edges account for possible routes between nodes with a weight function.

In our case, the situation is different since we do not want to guide drivers but we aim to find a path for a packet to reach the destination. More precisely, a directed graph G = (V, E) is built where the set of nodes V represent either road intersections, or some turning points, or some special nodes (control center, RSU, etc) (see Figure 3.2). Observe that since we are going to use directional broadcasting with a possibly small beamforming angle, the roads are supposed to be straight lines. That is why turning points of roads are considered as graph vertices to make this assumption valid.

Each road between two points of V will be represented by an edge. The weight of this edge might be equal to the geographical distance between the extremities of the edge. One can also consider more complicated weights taking into account the vehicle density or jam. In fact, roads with a large vehicle density can be more convenient to transmit the packet since the probability of transmission success increases with vehicle density (as will be shown by simulations and analytical formulas). Then the edge weight might be a well chosen function which is decreasing in the vehicle density and increasing in the distance. In fact, we can use the analytical framework, presented in the next chapter, to get an estimation of the probability of transmission success S λe (d e ) if the vehicle density on a link e ∈ E is λ e and the length of the road is d e .

Then, the probability to reach a destination using a path in G is almost equal to the product of the probabilities of success of the links belonging to the path. Maximizing the probability of success is obviously equivalent to finding a path P from source to destination minimizing e∈P ln( 1S λe (de) ). If vehicle densities are not equal on different links (roads), then the obtained path is not necessarily a shortest path in terms of geographical distance.

If a vehicle wants to communicate with a node having a known location (another vehicle, an RSU, etc.), it has to compute a minimum-weight path between its position and the destination. This path will be used to send the packet. Since there are generally many packets to be sent to the same destination, this path does not need to be computed for each packet. If the destination is also moving, the path might be updated from time to time (more details are given in the next section).

We assume that each geographic point has a unique identifier, called P ID. The unicity of this identifier is a valid assumption since each geographic point is characterized by a unique couple of GPS coordinates. Thus, the identifier P ID may be this couple of values. The sequence of these points are put into the first packet header to transmit as shown in Figure 3 In addition, we assume that all vehicles are equipped with directional antennas.

The beamforming angle used to transmit alert messages is equal to θ (θ ≤ 90 • ). This beamwidth ensures a directional propagation of the transmitted packets towards the intermediate destinations and prevents a returning back of the message transmission.

Hence, upon receiving an intermediate packet, each node must decide whether this packet should be forwarded and where to. To this end, vehicles that receive an intermediate message will broadcast it on their turn unless they have seen it before, or unless they are the destination. The system ends broadcasting when there are no more relays to broadcast. In this case, we assume that the message has arrived or that the system has encountered a transmission failure. The transmission failure is a situation when there is not any intermediate relay to reach the destination. In this case, only vehicles positioned in the zone covered by the directional beam will receive the message as shown in Fig. 3.1. It is worthnoting that the beamforming angle θ is fixed from the beginning of transmission operation and it is the same for all the participating nodes. As mentioned before, each vehicle is supposed to know or to guess the position of its destination in order to determine the direction of the transmitted beams. Our algorithm can be adapted to relatively precise or less precise direction information as it will be seen. The success or failure of the transmission is strongly dependent on the density of nodes λ.

The functioning of our proposed is summarized by the following Algorithm 1.

The broadcasting technique might be enhanced by asking the destination to send an Algorithm 1 EBDR Algorithm 1: The source node S runs the route guidance algorithm.

2:

The set of intermediate destinations {D i } is determined using the route guidance algorithm.

3: S puts the sequence of the intermediate destinations D i in the header packet. if Packet already received or node i is the final destination D then 7:

the packet is removed and not transmitted node i compares its current position to the geographic positions of D i .

11:

node i removes the sequence of D i already reached from the packet header.

12:

node i points its directional beam toward the next intermediate node D i .

13:

node i makes an angle θ 2 with each side of the central axis linking i to D i and transmits the message. end if 16: end for acknowledgment of receipt (for each packet, or for each group of packets). Since the received packets contain the position of the source, the destination can apply the same algorithm to compute a path to the source (or it can be the reverse path). This path is used to send an acknowledgment with the exact position of the destination.

Since the destination can be a moving vehicle, the new position can help the source to update the path from it to the destination. If the source node does not receive acknowledgment for a long time, then it can deduce that the chosen path is not convenient to transmit information, and it may use a second path (a shortest disjoint path for example) to broadcast packets. These enhancements are left for further study. We will next focus on the basic approach without acknowledgments.

Performance Evaluation

Simulation Plateform

In this section, we evaluate the performance of our proposed Broadcast-based Routing technique. To this end, we use the Veins [START_REF] Veins | [END_REF] framework a realistic vehicular communication simulator dedicated to VANETs networks. Veins is composed of two simulators: OMNET++ [START_REF]OMNET Simulator[END_REF] as a wireless network simulator and SUMO [START_REF]SUMO Simulator[END_REF] as a mobility traffic generator to perform real vehicular mobility simulations (see Fig. were designed for VANETs in order to accurately simulate the behavior of such very dynamic networks. Among these tools, we can mention:

• VanetMobiSim [90]/ NS2 [START_REF]NS2 simulator[END_REF]: VanetMobiSim simulator focuses on vehicular mobility models at macro and microscopic levels and simulates the movement of vehicles in roads. On the other side, NS2 forms the network simulator which provides a networking stack for the communications between vehicles and simulates the wireless transmissions. The combination between these two tools results in the formation of a decoupled simulator: the traces files generated by the traffic simulator, as a prior stage, are used as an input for the network simulator. Once used, the trace files can not be changed.

• TraNS [START_REF] Piorkowski | TraNS: realistic joint traffic and network simulator for VANETs[END_REF]: The traffic and network simulator TraNS is a graphical simulator that integrates SUMO and NS2 simulators. With this simulator, events occurred in the network simulator (accident, traffic light extension) can alter the movement of vehicles in the traffic simulator NS2 and vice-versa. This characteristic is very interesting because it offers a real model of the reality in VANETs. In fact, this solution is the most powerful and attracting since the vehicles react consequently to the reception of significant information from the traffic simulator.

• Veins (OMNET++/SUMO): This simulator follows the same idea behind TraNS, however it differs from it in choosing the network simulator OMNET++ in spite of NS2. This framework is well documented and offers a good bidirectional coupling between the two simulators resulting in more realistic behavior of protocols and deeper insights into the impact of network protocols on the road traffic [START_REF] Sommer | Bidirectionally Coupled Network and Road Traffic Simulation for Improved IVC Analysis[END_REF].

For these reasons, we have chosen to use this simulator in our study.

In the following, we focus on the impact of our broadcast technique on delays, ratio of implicated nodes and probability of transmission success (i.e the probability of the alert message to reach the destination). Findings corroborate the efficiency of our proposal compared to a simple broadcast technique.

To make the proposed scheme tractable, we consider the following steps:

• We use the WAVE architecture [START_REF] Ramanathan | VANET architectures and protocol stacks: a survey[END_REF] to model the MAC layer used for each communicating node. This architecture is based on the IEEE 802.11p protocol [START_REF]IEEE Standard for Information technology-Local and Metropolitan area networks-Specific requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 6: Wireless Access in Vehicular Environments[END_REF] dedicated specially to vehicular communications.

• All nodes have the same transmission/receiving range, which is denoted by r and equal to 200 m.

• For the road topology, we have chosen the "Champs-Élysées" avenue to test our optimized broadcast protocol. The map (see Figure 3 • The number of vehicles was varied from from 800 to 1060 (its corresponds to a realistic urban scenario).

• We vary the beamforming angle θ from 10 • to 90 • to study the effect of the beamwidth on several networking metrics.

For the mobility traffic generator, we use SUMO [START_REF]SUMO Simulator[END_REF] simulator which is already included in VEINS software and offers realistic vehicular mobility patterns. Details of the simulation setup parameters are listed in TABLE 3.1. The maps represent a zoom of one sector in Paris (France). Circled nodes denote the vehicles implicated in the forwarding operation. We observe that, with the Broadcast-based directional routing, nodes located outside the beamforming sector (which corresponds to the vehicles not present on the road given by the route guidance algorithm) are not participating in the broadcast process contrary to the blind dissemination technique. Furthermore, directional broadcast-based routing only allows the nodes located on the direction to the destination to participate on the forwarding process and then vehicles which are not interested by the alert are not involved.

Hence, we can conclude that the adjustment of the dissemination direction significantly reduces the number of implicated nodes.

In Figure 3.9, we present the average values of the probability of transmission success, i.e. the probability that the alert packet successfully reaches the final destination D obtained by simulations for the two approaches. Here, the distance between the sender S and the destination D is equal to 2000 m. Four levels of vehicle density are taken into account: λ = 0, 01; λ = 0, 02; λ = 0, 04; λ = 0, 05. We observe obviously that the probability of transmission success increases when the density of In fact, if the distance is doubled, then the probability of success is approximately squared. This is easy to understand since to reach a destination located at distance 2d, a message should successfully reach a point located at a distance d and then continues to be transmitted with success to reach the destination. In other words, ln(p) is linear in d where p is the probability of transmission success. on the performance of our proposal since the packet is transmitted linearly following the roads. Thus, even a smaller angle will have similar performance.

To confirm our proposition, we simulate, in Figure 3.11 the impact of the beamforming angle θ on the ratio of implicated nodes with a density of vehicles λ equal to 0, 02. From the results in Figure 3.11, it emerges clearly that the beamforming angle θ does not affect severally the percentage of participating vehicles. In fact, the proportion of implicated nodes ranges from 10% for an angle θ = 10 • to 14% for θ = 90 • . It can be observed from Figure 3.8 that vehicles participating on the forwarding process are located on the set of roads chosen by the route guidance algorithm. Thus, even with angle θ less than 90 • , the snapshot of implicated nodes will have the same shape.

For the traditional broadcast technique, the ratio of implicated nodes is independent from the beamforming angle θ. It achieves a ratio equal to 48% while our technique achieves for the worst case (θ = 90 • ) a gain of ≈ 60% compared to it. This fact confirms the efficiency of our proposal in terms of bandwidth consumption. The end-to-end delay can be considered as the delay of the shortest path from the source S to the destination D. We notice that this variation is very tight and that the curve is almost linear. This finding corroborates the fact that the variation of the beamforming angle has no effect on the global performance of our technique.

Furthermore, in this scheme, the delay relative to the blind dissemination is equal to 6, 7 ms. From Figure 3.12, we learn that for small values of θ (≤≈ 30 • ), the blind broadcast achieves better results than our technique. This can be explained by the fact that when the beamforming angle θ is small, a little number of relays are implicated on the forwarding process and consequently, the alert delivery is delayed due to the absence of "suitable" forwarding vehicles. Whereas, for higher values of θ (≥ 30 • ), our technique outperforms the blind broadcast and remains achieving smaller value of delay even with larger beamforming angle values.

On the other hand, the top line is for the total broadcast transmission duration.

We observe clearly that the difference between the two curves is very tight. This little difference between the two lines denotes clearly that the vehicles participating in the Consequently, these findings undoubtedly prove that our proposed technique conserves the bandwidth (ensures a less ratio of implicated nodes) and improves at the same time the end-to-end forwarding delay.

In the next section, we investigate the applicability of our proposed technique EBDR in a different network node distribution. Good performance results will endorse the efficiency of our technique in terms of adaptation to different node distribution schemes which is considered a very important asset in any networking algorithm conception.

Other Application Scenarios of EBDR

In this section, we focus on the evaluation of our proposed broadcasting technique in another networking scheme: The proposal is evaluated using a simplified node distribution scheme, suitable to wireless adhoc networks. Thus, we investigate the performance of EBDR in this new configuration and we derive an analytical model that is able to capture the transmission area of the messages. Obtained results confirm that the application of our proposal is not limited to vehicular networks but it can also be adapted to different networking schemes. This adaptation facility represents a strong key in the conception of our broadcasting technique.

Protocol Design

We suppose here that wirelesss nodes are randomly positioned in a square area. The broadcasting technique is based on the same principles as EBDR. However, the route guidance function is disabled in this case. The broadcast operation is based on two geographic parameters: the first is the destination direction. This information is sufficient in the context of wireless adhoc networks since the node distribution is quite uniform and not depends on streets, intersections, etc. For these reasons, the list of intermediate destinations D i is not needed here.

The second parameter is the beamforming angle θ. We use the same principle as in the vehicular scheme: Each node points its directional beam toward the position of the final destination D makes an angle θ 2 with each side of the central axis linking the relaying node and the final destination D. This mechanism is repeated until the message reaches D.

Results and Analysis

In this section, we evaluate the performance of our adhoc-version proposed technique through MATLAB simulations. We study precisely the impact of the density of nodes and the beamforming angle on the performance of our proposal. The results confirm the efficiency of our algorithm in terms of use of bandwidth, the ratio of implicated nodes and the probability of transmission success. In fact, transmitting messages within a limited area clearly reduces the number of nodes having to relay the message and considerably reduces the total number of transmissions and affect the probability of success. Moreover, varying the angle of transmission and the density of the nodes will give us an indication on the spectrum efficiency. There will be two kinds of results in this section. Some simulation results related to the probability of success and the proportion of vehicles participating to the forwarding process. An analytical model will also be given for the second performance criteria (the proportion of implicated vehicles).

Some Simulation Results

In order to analyze the performance of our protocol, we conduct several simulations varying the following system parameters:

• Number of vehicles in the simulation from 1000 to 3000.

• Beamforming angle θ (from 22.5 • to135 • ).

The nodes are assumed to be randomly positioned in a square area according to a Poisson process of density λ(so λis equal to the number of nodes divided by the area of the square).

In Figure 3.13, we show a snapshot of the nodes implicated in the transmission of a message from source S to destination D. We consider that the angle θ is equal to 60 • and that all nodes have a transmission range r equal to 200m. The figure shows that the relays are located within a geographical area. The analytical model will prove that this shape is similar to a leaf. in Figure 3.16, while it equals to 2000m (resp.3000m) in Figure 3.17 (resp. 3.18).

Observe that the probability of success seems to be convex for small angles and concave for large angles. One can deduce from Figures 3.16, 3.17 and 3.18 that the angle should be chosen carefully depending on the distance and the density.

An analytical Model for the Transmission Area

This section encloses an important contribution which consists in the derivation of an exact formula to evaluate the transmission area (.i.e., the set of nodes that receive a message and retransmit it). Thereby, this finding provides a good tool to confirm the results obtained by simulations.

As such, we assume that nodes are uniformly distributed in a square. The source and all relay nodes transmit messages according to an angle θ within a radius r. As shown in Figure 3.19, the transmission can be approximated by a set of triangles (the destination is a vertex of each triangle). Starting from the triangle containing the source, each two consecutive triangles have a common vertex (in addition to the destination). Each triangle's vertex is obtained by considering that there is a mobile situated in a vertex of the previous triangle transmitting within a distance r according to an angle θ. It should be understood that the union of these triangles is only an approximation of the true transmission area. We will see that this approximation is very good. Observe that the transmission area is again similar to a leaf.

Since the transmission area is symmetric, we can focus on the half plane above the line connecting the source and the destination. Starting from the triangle containing the source and using d i to denote the length of the common edge between the triangle Figure 3.19: Area of transmission number i and the triangle number i + 1, the area of triangle number i is given by:

S i = 1 2 rd i sin( θ 2 ) (3.1)
Moreover, the distances d i and d i-1 are linked through the following equation:

d 2 i = d 2 i-1 + r 2 -2rd i cos( θ 2 ) (3.2)
All these distances and triangle areas can be iteratively computed using the two previous equations. This directly leads to the total area given by:

S = 2 N b 1 S i (3.3)
We evaluate hereafter the model in Eq.3.3 and compare it to our simulations. The result is expressed in terms of the ratio of implicated nodes with respect to the angle θ. We show on Figure 3.20 the ratio of implicated nodes given by simulation when there are 1000 nodes in the square and also when there are 3000 nodes. We also show the theoretical ratio given by Eq.3.3. Notice that the theoretical value does not depend on the mobiles density. One can see that the three curves are very close. This clearly implies that the analytic model provides a very good approximation of the real situation. The relative error seems to be particularly small for angles between 45 • and 120

• .

An important observation related to Figure 3.20 (and confirmed by many other simulations) is that the ratio of implicated nodes seems to vary linearly when θ is less than 100 • .

Conclusion

In this chapter, we studied dissemination of emergency messages in VANETs. After an overview of the state of the art, we presented our proposed broadcast based routing technique, denoted EBDR, and devoted to urban vehicular networks. Unlike the majority of existing approaches, the EBDR protocol grasps the transmission opportunities offered by directional antennas and uses a route guidance algorithm to route messages toward their destination. Simulation results confirmed the efficiency of our approach in terms of probability of success and end-to-end delays. Moreover, in spite of the broadcast nature of the proposed technique, all transmissions stop very soon after the arrival of a packet to its destination representing a strong feature in the conception of EBDR. As a consequence, our approach fulfills the requirements of any dissemination technique: simplicity (broadcast-nature), reliability and efficiency.

Additionally, we studied our approach in a wireless adhoc environment to demonstrate the easy adaptivity of EBDR to different network schemes. Simulations as well as analytical analysis corroborate the efficiency of our technique in this new node distribution scheme. This feature distinguishes our approach from other existing techniques.

Deriving a novel mathematical framework that is able to investigate analytically the performance of our proposed technique EBDR will be the main goal of the next chapter.

Introduction

In literature, there is a plethora of multihop broadcast routing protocols for VANETs.

However, scant efforts are supported by a theoretical proof or background underlying their efficiency. In fact, most of the proposed techniques rely on experimental testbeds or simulations to demonstrate their performance and neglect the importance of having a mathematical proof of their results which make their findings more universal. For these reasons, we focus in this chapter on constructing an analytical framework able to investigate the performance of EBDR theoretically. As such, we derived recursive upper and lower bounds for the end-to-end probability of success and the average number of hops. Our proposed mathematical framework holds for any spatial node distribution and it can be modified to fit new protocols. In addition, simulation results, carried out in the previous chapter, are compared to the results obtained with the analytical models. Observations show that there is a good match between the two techniques.

State of the Art

We present here some insights of the relevant works that tackled the problem of reliable IVC and proposed some analytical models to investigate the performance of such vehicular scenarios.

In [START_REF] Wisitpongphan | Routing in Sparse Vehicular Ad Hoc Wireless Networks[END_REF], Nawaporn and al. focus on a sparsely connected highway in a vehicular network context. They develop an analytical framework to investigate the major characteristics of wireless networks such as the probability of being disconnected from the following vehicle, the cluster size and length, intra and inter cluster spacing in a single direction road. Besides, they studied a disconnected network with two directional traffic and carried out analytical expressions for the disconnection probability and the re-healing time defined as the time taken to deliver a message across two adjacent clusters. Monte Carlo simulations match the proposed analytical models.

Authors in [START_REF] Sou | Enhancing VANET connectivity through Roadside Units on Highways[END_REF] consider a sparsely vehicular network and investigate the use of RSUs to assist the traffic safety messaging. They propose an RSU advertising model to tackle the problem of network fragmentation. Besides, they carried out an analytical framework to evaluate the performance of their RSU-based solution.

Mathematical expressions are given for the connectivity probability, the re-healing delay, and the number of re-healing hops. In their work, the connectivity probability refers to the probability of finding an RSU within the transmission area of the source' cluster:

P I = 1 D u × Du ru=0 e -λeru ⌊ ru R ⌋ j=0 (-1) j j! [λ e (r u -jR)] j-1 × [j + λ e (r u -jR)]e λe(ru-jR) dru
where r u refers to the distance between the source vehicle V 0 and the succeeding RSU U 1 , R is the transmission range of each vehicle, D u corresponds to the distance between two successive RSUs, and λ e represents the density of vehicles in the highway.

The re-healing delay and the number of re-healing hops correspond, respectively, to the time and the expected number of hops required to deliver the message to either the nearby RSU or the the first vehicle in the following cluster. Simulations validate the mathematical proposal and demonstrate that the message delivery delay to a re-healing node can be significantly reduced.

Wang [START_REF] Wang | Modeling the process of information relay through intervehicle communication[END_REF] considered the case where vehicles are distributed according to a Poisson process. A closed form expression for the expected value of the propagation distance (the total distance traveled by a message before getting stuck due to the absence of any vehicle within the range r) is derived. The variance of this propagation distance is also computed. When a vehicle sends a message, we can assume that among all vehicles receiving it, only the farthest one will relay it. This is the traditional MFR assumption (most forwarded within range) of [START_REF] Takagi | Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals[END_REF]. This assumption does not influence the probability of success and the propagation distance. However, it has an influence on the number of transmissions before getting stuck. The average number of hops before the end of transmissions is exactly computed in [START_REF] Wang | Modeling the process of information relay through intervehicle communication[END_REF]. Some recursive formulas are also given for the probability of transmission success (the probability that the message reaches a destination located at a distance d).

A similar recursive approach is also presented in [START_REF] Jin | Instantaneous information propagation in a traffic stream through inter-vehicle communication[END_REF] to compute the probability of success. Notice that the number of hops before transmission's fading is called the number of cycles in [START_REF] Cheng | Critical connectivity phenomena in multihop radio models[END_REF]. As one of the early efforts, a generalization of some results of [START_REF] Wang | Modeling the process of information relay through intervehicle communication[END_REF] is proposed in [START_REF] Wang | The process of information propagation in a traffic stream with a general vehicle headway: a revisit[END_REF] where no assumptions are made about the distribution of vehicles. The expectation and the variance of the propagation distance are computed in an exact way through simple formulas.

Compared to this literature, we can claim that our solution is more complete since it is the first approach that provides closed form expressions both for the probability of success and the average number of hops and considers a propagation scheme where the message must be transmitted to a known destination. In the following, we will first focus on the probability of success. A novel recursive approach is proposed and used to compute lower and upper bounds for the success probability. Moreover, these lower and upper bounds will be useful to compute the average number of hops required to reach a specific destination if we assume that the forwarding process is successful.

Up to our knowledge, this average number of hops to reach a destination was not considered before. As mentioned above, only the average number of hops before getting stuck was considered in literature.

Problem Statement

The work performed in this section is motivated by the need of having an analytical framework with low complexity and able to evaluate the performance of our proposed broadcast-based routing technique.

Hence, our framework allows deriving meaningful performance metrics including the probability of transmission success as well as the required number of hops to reach the final destination. This latter is illustrative of the end -to-end delay needed to reach the final destination. In these analytical models, lower and upper bounds are provided and computed by dynamic programming techniques. To assess the merit of our mathematical expressions, a comparison with the simulation results obtained with the proposed routing technique is carried out and findings match very well the analytical models and show that the gap between lower and upper bounds is very tight. Up to our knowledge, this average number of hops to reach a destination was not considered before (only the average number of hops before getting stuck was considered in literature).

Throughout the rest of this chapter, we consider a traffic stream present on a straight line. This special case of inter-vehicle communication corresponds, in the vehicular context, to a transmission along a straight one way road or highway using a directional antenna. We assume that the vehicles are distributed on the line connecting the source and the destination according to a Poisson process of intensity λ (dimension : [veh/m]).

In other words, the distance between two consecutive vehicles follows an exponential distribution. The average distance between two vehicles is 1 λ . This assumption is based on some traffic studies that have proved that the inter-vehicle spacing on a highway can be modeled by an exponential distribution [START_REF] Wisitpongphan | Routing in Sparse Vehicular Ad Hoc Wireless Networks[END_REF]. We consider a fixed transmission range for all moving nodes denoted as r. The distance between the source and the destination is noted as d.

In what follows, we present an analytical model for the probability of success as well as the average number of hops. Simulations will also be conducted to validate the models.

Probability of Success

Analytical Model

As mentioned above, we assume that the vehicle position is confined to one dimension (single line). The vehicle spatial positions are modeled as a Poisson process of intensity λ. We consider also a fixed transmission power for all nodes. Thus, all vehicles have the same fixed transmission range denoted as r.

Initially, a sender vehicle (1) generates an alert message that has to be forwarded by other vehicles (see Figure 4.2). We assume also that each node only forwards the message once since it can recognize later copies of the original broadcast. We denote by d the distance between the sender S and the destination D.

We will compute the probability of success though recursive formulas. To evaluate this probability, we can assume that after the emission of the first message, by the source S, the farthest node from S will be the next relay. In other words, the message will reach the destination if two conditions are satisfied: first there are other nodes within a distance r from S, and second the message sent by the farthest node from S (among those that are within a distance r ) should reach the destination. In other words, one may think that this probability is given by

S(d) = r 0 e -λ(r-x) S(d -x) dx
where e -λ(r-x) represents the probability that there are no nodes in the interval [x, r], λ dx represents the probability to have a node around the position x while S(dx) is the probability to reach the destination from the farthest node (the distance between the farthest node and the destination is dx). The formula above is unfortunately not correct because there is some dependency between the probabilistic events "the farthest node has the position x " and "the message sent by the farthest node reaches the destination". Knowing that there are no nodes in the interval [x, r] has definitely some correlation with the success probability of any transmission initiated from this node.

One way to overcome this difficulty is to assume that the closest vehicle (instead of farthest) is relaying the message. As observed by [START_REF] Wang | The process of information propagation in a traffic stream with a general vehicle headway: a revisit[END_REF], this assumption does not have any impact on the probability of success. Then the following recursive formula is valid:

S(d) = r 0 e -λx S(d -x) dx (4.1)
Formula (4.1) can be used to compute the success probability (or more precisely to approximate it). However, we will introduce another recursive formula to compute it. The main reason for that is that what will be computed in this section, will be useful to compute the average number of hops in the next section.

Observe that assuming that the farthest node located in position x is transmitting the message within a distance r is in fact equivalent to assume that there is a node located in position r transmitting within a distance x.

Then, in order to compute the probability of success, we have to introduce the quantity S(d, a) representing the probability of success knowing that the first node (source) is transmitting within a range a, where 0 < a ≤ r, while all relays transmit within a distance r. The probability of success is now given by the following recursive formula for 0 < a ≤ r:

S(d, a) = a 0 λe -λ(a-x) S(d -a, r -a + x) dx (4.2)
In this equation, λdx refers to the probability of having a node around x, while e -λ(a-x) represents the probability of absence of any vehicle within the interval [x, a].

As explained above, the emission of a message within a distance r by a vehicle located in position x is equivalent to the emission of a message within a distance ra + x by an "imaginary" vehicle located in position a.

In order to exploit the recursive formula (4.2) to compute the numerical values of S(d, a), we will discretize the interval [0, a]. More precisely, we assume that:

r = kb d = lb (4.3) a = ib
Where b is a small distance called a step and i, l and k are integers. b can be seen as a precision factor in order to determine the probability of success. In fact, the smaller it is, more precise the probability will be.

Hereafter, we give some obvious upper and lower bounds of the probability of success.

By replacing a and x in the Eq.4.2, we obtain the probability of success transmission as:

S(lb, ib) = i-1 j=0 (j+1)b jb λe -λ(ib-x) S((l -i)b, (k -i)b + x) dx (4.4)
The upper bound of the probability is obtained using the fact that S(d, a) increases when a increases.

Let us use S(lb, ib) (resp. S(lb, ib)) to denote the upper bound (resp. lower bound) of S(lb, ib).

Thus:

S(lb, ib) = i-1 j=0 λe -λib S((l -i)b, (k -i + j + 1)b) (j+1)b jb e λx dx (4.5)
corresponds to the upper bound.

Moreover, by calculating the integral in the Eq.4.5, we get:

S(lb, ib) = i-1 j=0 e -λb(i-j) (e λb -1)S((l -i)b, (k -i + j + 1)b) (4.6)
Using the same approach, we get the following lower bound for the probability of success.

S(lb, ib) =

i-1 j=0 e -λb(i-j) (e λb -1)S((li)b, (ki + j)b) (4.7)

Model Validation

In this section, we evaluate the analytical model through several use cases. We also compare analytical results to simulation results reported in the previous section. Our goal is to verify the bounds given by Eq.4.6 and Eq.4.7.

To understand the impact of the density of vehicles on the analytical framework precision, we consider four levels of vehicle density: λ = 0, 01; λ = 0, 02; λ = 0, 04; λ = 0, 05.

The probability of success (upper and lower bounds) is evaluated against the results

given by simulations (reported on Figure 3.9).

We define the precision rate as follows: precision rate = (1-upper bound -lower bound simulation value )100.

We fix the precision step b = 5 and we compute upper and lower bounds using dynamic programming.

According to the results depicted in Figure 4.3, our analytical model shows good performance in all cases. Indeed, in the worse case, the precision of the model does not fall below 85% (λ = 0.01) and increases very quickly when λ increases. It can also be observed that the probability of success decreases very quickly when d increases. For example, increasing the distance from 1000 m to 4000 m reduces the probability from 70% to 20%.

In addition, if we plot the curve of the logarithm of the probability of success when d is varying from 1000 m to 8000 m, we can see that the curve is almost linear (see Figure 4.5).

This result may be justified as follows. If the distance d is large (compared to r ), then one can expect S(2d, r) to be approximately equal to S 2 (d, r). Reaching a destination located at a distance 2d is approximately equivalent to reaching a first is, the more accurate our bounds will be.

Average Number of Hops

To have a better understanding of the connectivity in VANETs, we investigate the average number of hops in the shortest path linking the source to the destination (if there is any).

We will focus on the case when the message reaches the destination. An analytical model based on a recursive formula will be presented for the average number of hops.

Analytical Model

We still use the same notation as in the previous section. Let h(d, a) denote the average number of hops needed to propagate the message to a destination located at a distance d assuming that: the message reached the destination, the source is emitting within a range a, where 0 < a ≤ r, while all relays transmit within a distance r. While we are mainly interested in computing h(d, r), we need to compute h(d, a) for different values of d and a.

Before presenting the recursive formula, we provide here some simple bounds related to h(d, r).

Theorem 1

⌈ d r ⌉ ≤ h(d, r) ≤ 1 + ⌈ 2d r ⌉ (4.8)
Proof: The first inequality is obvious and well known. It is valid because the distance between two consecutive relays is less than r. The second inequality seems to be new.

It can be proved very easily by observing that the distance between the relay number j (the j th vehicle forwarding the message) and the relay number j +2 is strictly larger than r. Adding up all inequalities for each j and rounding up leads to the wanted inequality.

Formula (4.8) clearly implies that the average number of hops is almost proportional to the distance. However, we should not forget that we are here making the assumption that the destination is reached.

To investigate the validity of these bounds, we compare on Figure 4.7, the simulations values obtained in the previous section to these analytical expressions. It can be observed clearly that simulation values are within the interval defined by the two bounds. We remark also that the precision of these bounds decreases when the endto-end distance is increasing. Nevertheless, these bounds still are interesting given their simplicity and their acceptable precision and can be exploited analytically by studying multihop broadcast protocols. , if d > a (4.9)

Proof: Let h(d, a, j) denote the probability to reach the destination in j hops. if d ≤ a we obviously have h(d, a) = 1 since the message sent by the source will reach the destination in one hop.

In the other case, the expected probability is given by:

h(d, a, j) = a 0 λe -λ(a-x) h(d -a, r -a + x, j -1) dx (4.10)
In this equation, λ dx refers to the probability of having a node around x, while e -λ(a-x) represents the probability of absence of any vehicle within the interval [x, a].

As explained before, the emission of a message within a distance r by a vehicle located in position x is equivalent to the emission of a message within a distance r-a+x by an "imaginary" vehicle located in position a. The first message reaches the destination in j hops if and only if the message sent by this imaginary vehicle reaches the destination in (j -1) hops.

Using the conditional expectation rule, the average number of hops conditionally to the success of the transmission is given by:

h(d, a) = ∞ j=1 jh(d, a, j) S(d, a) (4.11)
where S(d, a) is still the probability of a successful transmission from the source to the destination.

Replacing h(d, a, j) by its expression, Eq.4.11 becomes:

h(d, a) = ∞ j=1 j a 0 λe -λ(a-x) h(d -a, r -a + x, j -1) dx S(d, a) (4.12) h(d, a) = a 0 λe -λ(a-x) ∞ j=1 jh(d -a, r -a + x, j -1) dx S(d, a) (4.13)
Eq.4.13 can be rewritten as follows : Observe that the recursive formula (4.9) includes the success probabilities S(d, a).

h(d, a) = a 0 λe -λ(a-x) ∞ j=0 jh(d -a, r -a + x, j)dx S(d, a) + a 0 λe -λ(a-x) ∞ j=0 h(d -a, r -a + x, j)dx S(d, a) (4
That is why the success probabilities were calculated in the previous section.

Let us make the same assumptions given by Eq.4.3. Then, we get the following:

h(lb, ib) = 1 + i-1 j=0 (j+1)b jb λe -λ(ib-x) h((l -i)b, (k -i)b + x)S((l -i)b, (k -i)b + x)dx S(lb, ib) (4.16)
Using the upper and lower bounds of the probability of success computed before (S(lb, ib) and S(lb, ib)), upper and lower bound for h(lb, ib) can also be computed by dynamic programming.

Let us use h up (lb, ib) (resp. h low (lb, ib)) to denote the upper bound (resp. lower bound) of h(lb, ib).

Using the same approach as before (to bound the success probability), we get the following bounds:

h up (lb, ib) = 1+ i-1 j=0 e -λb(i-j) (e λb -1)h up ((l -i)b, (k -i + j)b)S((l -i)b, (k -i + j + 1)b)
S(lb, ib) (4.17)

h low (lb, ib) = 1+ i-1 j=0 e -λb(i-j) (e λb -1)h low ((l -i)b, (k -i + j + 1)b)S((l -i)b, (k -i + j)b) S(lb, ib) (4.18)
We see again that after computing the upper and the lower bounds for the probability of success, it is possible to compute upper and lower bounds for h(lb, ib) by dynamic programming.

Model Validation

In this section, we compute the values given by the analytical framework related to the required number of hops by means of dynamic programming. Furthermore, the framework is applied to our proposed broadcast-based routing technique to investigate the validity of the computed bounds.

Hence, we simulated the scenario shown in Figure 3.13 using Veins framework.

This scenario can be modeled as three successive highways. Hence, to calculate the This is also shown on Figure 4.12 where the precision rate is reported. One can deduce clearly that b has a great effect on the precision of our model. Hence, all of these simulation scenarii confirm the precision of our proposed mathematical framework and demonstrate its robustness even with different values of vehicle densities and end-to-end distances.

Conclusion

In this chapter, we presented a theoretical framework based on a recursive approach to analyze the performance of our proposed broadcast-based routing technique EBDR.

Analytical bounds are proposed to compute the end-to-end probability of success and the average number of hops in case of a successful linear transmission in a vehicular context. Several simulations have been performed to evaluate the precision of these models. Mathematical expressions match very well the simulation results.

Comparisons with conducted simulations corroborate the correctness of our analytical approach. In addition, the validity of our framework is not limited to our special case but span to other node distributions where the average positions are equally spaced.

We also showed that if the transmission range is r, the number of hops to reach a destination located at a distance d is between d r and 2d r . In the next chapter of this thesis, we will present an improvement of EBDR protocol that offers greater efficiency without penalizing its reliability. our proposed broadcast-based routing technique EBDR performs well this function and presents essentially a very good efficiency in total transmission delay. In fact, in spite of the broadcast nature of the proposed technique, all transmissions stop very soon after the arrival of a packet to its destination and the messages propagation is limited by destination zone.

The focus of this chapter is on increasing the efficiency of EBDR message delivery by minimizing the bandwidth consumption as well as the interferences level. In other words, we investigate here the following fundamental question: how can we achieve a high reachability while minimizing the inherent effects of high transmission power for a beamforming-based broadcast scheme in multihop wireless vehicular networks ? To circumvent this challenge, we will present through this chapter, an enhanced version of EBDR which maintains a high efficiency and a good reachability while severally minimizing the bandwidth consumption. This new technique proposes a fully distributed scheme that allows nodes to set dynamically their transmission range based on their local densities and the distance to the destination. Conducted simulations confirm the efficiency of our enhanced technique for several performance metrics. Moreover, we present an analytical framework that offers some insights about the behavior of our technique in the case of an uniform node distribution suitable to wireless adhoc network schemes.

Problem Statement

In vehicular communication, message propagation and dissemination occurs very often and have to be done in small delays. Therefore, reliability and low delay are extremely significant factors for VANETs applications. Generally, in a wireless transmission process, a larger transmission radius is often desirable to achieve a greater progress. However, a larger transmit power also lead to a huge amount of interferences between neighbor nodes, higher probability of packet collisions with other concurrent transmissions and channel contention.

As a consequence, various methods have been proposed to implement congestion control schemes. Amid them, transmission range adjustment technique (or transmission power control) has shown its merit as a crucial countermeasure to minimize interferences and guarantee a high reachability for the multihop transmission operation. The principle behind the concept is that reducing the transmission power of vehicles will also decrease the number of nodes participating in the broadcasting operation and then reduce the number of hidden terminals and packet collisions for each transmission. An important challenge related to transmission range adjustment technique should not be forgotten: the trade off between reducing the transmission range (which prevents the message from reaching some vehicles located further) and the reduced transmit power which inhibit a node to interfere with communications occurring away.

Moreover, smart antennas (directional antennas) mitigate interference with beambased transmission range. In fact, in a beamforming mode, the antenna sends and receives signals inside its sector limited by the angle of beamforming θ. Hence, the gain outside the sector is approximated to zero and the interferences are almost null.

Hence, the combination between beamforming-based broadcast and transmission range adjustment technique can further improve the efficiency of the dissemination process. This feature represents the main key behind the conception of the reliable version of EBDR.

State of the Art

In this section, we present the relevant approaches that address transmission range adjustment techniques for multihop wireless networks.

In [START_REF] Tolba | Energy saving and connectivity tradeoff by adpative transmission range in 802.11g MANETs[END_REF], authors focus on preserving the energy and maintaining the connectivity of the mobile nodes and propose an approach to control the energy used in adhoc networks. Their technique is based on varying the transmission range of the communicating nodes. In fact, this variation depends from the local density of the concerned node: if the node has no neighbors, the transmission range takes the maximum value.

Otherwise, it will be equal to the farthest neighbors distance in order to maintain the sufficient number of neighbors. The absence of any analytical model to evaluate their approach constitutes the main weakness of this work.

The concept of power management in wireless adhoc networks is studied in [START_REF] Ebatt | Power Management for Throughput Enhancement in Wireless Adhoc Networks[END_REF].

Authors proposal is based on a clustering scheme wherein a node adapts its transmit power to establish connectivity with only a limited number of neighborhood nodes.

Within a cluster, a node may adapt its power transmission to communicate with neighboring nodes or it might use the same power with all nodes located in the cluster. Nevertheless, this technique assumes that each node broadcasts a signaling packet containing its local connectivity table information to construct a global view of the network. This can lead undoubtedly to a huge overhead and a scalability problem since it is not feasible for each node to store the entire global topological information.

In [START_REF] Palazzi | How Do You Quickly Choreograph Inter-Vehicular Communications? A Fast Vehicle-to-Vehicle MultiHop Broadcast Algorithm[END_REF], Claudio E. Palazzi and al. proposed the Fast Broadcast (FB) protocol for vehicular networks which uses a distance-based approach with an estimated transmission range. This latter reduces the number of redundant transmissions as well as the hops to be traversed. Their scheme is composed of two phases. The first one, named estimation phase, aims to provide each vehicle with an up-to-date estimation of its forward and backward transmission range. The second, called broadcast phase, is performed only when a message has to be broadcasted to all cars in the senders area of interest. During the estimation phase, each car tries to estimate its transmission range (frontward and backward) by the means of hello messages. Each vehicle maintains two variables called: Current-turn Maximum Front Range (CM F R) and Current-turn Maximum Back Range (CM BR). The former reflects the estimation of the maximum frontward distance from which another car along the strip-shaped area-of-interest can be heard by the considered one. The latter estimates the maximum backward distance at which the considered car can be heard. In the sending operation, each node proceeds with transmitting a hello packet that includes the estimated maximum frontward transmission range. For the receiving procedure, the vehicle takes the maximum value among the distance between the considered car and the hello message sender, sender's transmission range estimation (provided by the hello message), and its CMFR value. Obviously, this technique introduces an overhead caused by the periodic exchange of the hello messages.

Authors in [START_REF] Artimy | Local Density Estimation and Dynamic Transmission-Range Assignment in Vehicular Ad Hoc Networks[END_REF] propose a dynamic transmission range assignment scheme called DTRA that adjusts a vehicle transmission range based on the estimation of its local traffic density. Their proposition uses an analytical traffic flow model to derive an expression of the local vehicle density which makes vehicles able to adjust the transmission range. This technique is dedicated to highway roads only, and can not be generalized to a planar case. The DTRA functioning mechanism is based on the ratio Ts Tt to distinguish between free-flow and congestioned traffic conditions. In fact, T s depicts the time during which a vehicle remains motionless and T t represents a short time window. A high value of this fraction highlights a non congested traffic and a low vehicle density. Hence, the algorithm sets the transmission range to its maximum level in this case to maintain reachability. M.Torento and al. [START_REF] Torrent-Moreno | Distributed Fair Transmit Power Adjustment for Vehicular Ad Hoc Networks[END_REF] considered a fully distributed strategy to adjust each vehicle transmission power. Their proposal, namely D-FPAV, aims to control the channel load by adjusting the transmission power of each vehicle and hence minimize the packet collisions. The optimization is built upon the concept of fairness and the ability of every communicating vehicle to send and receive alert messages in a fair way. In fact, according to the authors, the amount of load resulting from beaconing should be limited in order to avoid a high number of packet collisions and leave some available bandwidth to handle the emergency messages. Therefore, they define a specific maximum threshold value of load for the beacons namely MaxBeaconingLoad (MBL). The goal is to adjust the transmission power used for beaconing messages in order to keep the load in the medium below MBL. Each node collects continuously the power used by its neighboring nodes and computes the maximum common value P i of the transmit power for all of them. Since this value is locally obtained, D-FAPV node circumvent this problem by broadcasting this common value P i to all nodes in its range. In addition, the node receives the power levels computed by the nodes in its vicinity and then can calculate the final transmit power level, which is set to the minimum among the value P i computed by the node itself and the values received from nodes in the vicinity. Despite the acceptable results given by D-FPAV, it still introduce an important overhead when broadcasting at each time interval the values of the computed transmission powers.

Another effort made by B.Rawat and al. [START_REF] Rawat | Dynamic Adaptation of Joint Transmission Power and Contention Window in VANET[END_REF] focuses on dynamic adaptation of joint transmission power and contention window considering vehicle densities and network traffic conditions. Indeed, their proposed algorithm adapts the transmission power based on estimated traffic density: As such, the concerned vehicle counts its neighboring vehicles based on the sequence number acknowledgement received from them and evaluates the local density of vehicles by taking the ratio of total reachable neighbors to the maximum possible number of vehicles on the given road segment.

For the adaptation of QoS parameters (e.g. contention window), the prioritization is assigned according to the relevance of the message and time delay requirements.

To this end, they incorporated the enhanced distributed channel access (EDCA) mechanism from the IEEE 802.11e standard.

Finally, in [START_REF] Chen | Dynamic transmission range in intervehicle communication with stop-and-go traffic[END_REF], authors address inter vehicle communication with stop and go waves and carried out an algorithm to adjust the transmission range of vehicles with the aim to achieve a better reliability. They study communication on highways with single-hop periodic broadcast. Their proposed scheme adjusts the transmission range by taking into account the variance coefficient of vehicles' spacing. The adjusted range is computed as follows:

T R adj (m) = (1 + m × CV ) × T R avgsp
Where CV depicts the coefficient of variation of spacing for all vehicles in the traffic stream. For some traffic models, this parameter can be computed. m refers to the order of magnitude for increasing CV and T R avgsp corresponds to the average vehicle spacing over the entire traffic stream. Based on NS2 simulations, they prove that their technique realizes good packet reception rates. This technique is based on the prior known of the value of the parameter CV which is possible only in the case of some traffic models. Otherwise, to compute this value, a global knowledge of the network and a periodic exchange of messages containing the precise positions of vehicles will be required. Hence, these constraints represent a weakness for this proposal.

Proposed Technique

In this section, we present our congestion control mechanism based on a distributed adjustment of the transmission power for all vehicles. First of all, we outline the rationale behind our transmission control strategy and then we detail the functioning principles of our proposal. Finally, we give an overview of the simulation results followed by an analytical model to validate the efficiency of our strategy.

Design Goal

Based on the previous study of existing works, we observe that the transmission control techniques that try to improve the packet reachability at close distance from the senders will also reduce the transmission range in a very acute way leading to the stop of the propagation. Therefore, an approach is needed that balances both packet reception probability and transmission range and at the same time this balance must be adapted to varying network densities. In addition, such a control transmission mechanism have to be totally distributed in order to minimize the overhead related to message exchange compared to a centralize approach. Unfortunately, there is a dearth of literature that studies this balance and tries to implement a totally distributed technique. In addition, all these efforts study the performance of their contributions empirically and do not provide any analytical proof of their efficiency. In the following, our goal is to implement a totally distributed approach that controls the transmission range of all vehicles and adapts them to the local densities. In addition, we derive an analytical model to capture the transmission shape in the case of a uniform node distribution scheme.

Broadcasting Scheme

For the purpose of developing our technique R-EBDR (Reliable EBDR), we assume that the broadcasting technique is based on the same principles used above for EBDR (Chapter 3) i.e., we use directional antennas with broadcasting to disseminate the message to a specific destination. The main enhancement key concerns the transmission range adjustment of vehicles by enabling these latter to set dynamically their transmission power based on their distance to the destination and the local nodes densities.

Transmission Range Adjustment Technique

In the previous chapter, we used a fixed transmission range for all the participating nodes to disseminate the alert packets with EBDR. In this part, the proposed scheme adjusts the transmission range for each node by multiplying the original range with a coefficient called adjustment coefficient. This coefficient is the same for all nodes. In fact, only the sender (the node who originates the alert message) computes this coefficient and then relay nodes, participating in the broadcast operation, will calculate their transmission range based on this parameter.

Assume that the first node (the originator of the message) broadcasts the message with an angle θ and a radius r 1 . This latter is a fixed parameter. The distance between the source and the destination is denoted by d 1 . Therefore, the adjustment coefficient is given by:

C = r 1 d 1 (5.1)
This parameter has to be added to alert messages to allow other relays compute their adjusted transmission range based on C. Indeed, we denote node i a relay node indexed by i. This relay is distant from the destination by d i . The adjusted transmission range for node i , namely (r i ) can be computed using the following rule:

r i = C * d i (5.2)
We notice that the above equation can lead to very little transmission range (approximated to 0) when the relay vehicle becomes very close to the destination node (d i ≈ 0). This fact can easily stop the propagation of the message and hence the rest of the participating nodes will not be reachable by the propagated information.

To alleviate this challenge, the algorithm defines a minimum transmission range value (r min ) considered as a a minimum threshold. Thus, all nodes have to maintain a transmission radius greater or equal to this value. In fact, r min can be seen as the transmission range that guarantees the existence of at least one neighboring node in the vicinity of each forwarding node. r min depends on the local densities of nodes (λ i ) computed by each relaying node i in the network. As demonstrated in [START_REF] Li | Density Adaptive Routing Protocol for Large-Scale Ad Hoc Networks[END_REF], the node i 's local density can be expressed as follows:

λ i = C i onnectivity π * r 2 i (5.3)
where C i onnectivity refers to the node i 's connectivity i.e., the number of its direct neighbors. This latter can be easily obtained using the beaconing mechanism.

Thereby, r i min can be expressed as:

(r i min ) 2 * θ 2 * λ i ≈ 1 (5.4)
Consequently, we obtain r i min ≈ 2 θ * λ i . Thereby, Eq.5.2 can be rewritten as follows :

r i = max(r i min , C * d i ) (5.5)
This new expression of r i guarantees a none-zero dynamic transmission range for the communicating nodes and therefore reachability for distant neighbors.

Evaluation Study

In this section, we first investigate the performance of our proposed transmission range adjustment technique in the case of a vehicular network. Then, we compare it to our previous work EBDR (i.e. A fixed transmission range for the beamformingbased broadcast scheme) [START_REF] Soua | Broadcast-based directional routing in vehicular ad-hoc networks[END_REF]. To this end, we developed our Matlab [110] [111] based simulation tool and performed simulation with real street maps. As a meaningful performance metrics, we focus on the impact of this technique on bandwidth and power utilization. These metrics are illustrative of the efficiency of the proposed transmission range adjustment technique in minimizing interferences and keeping the average number of implicated nodes as small as possible, yet guaranteeing end-toend reachability. To this end, we study the performance of our proposal in terms of probability of success (i.e the probability of the alert message to reach the destination).

Another major contribution of this part is the development of an analytical model aiming at estimating the transmission area of the forwarding process in the case of a simplified multihop nodes distribution. The model is compared to simulations to validate its exactness.

Proposed Technique in Real Vehicular Road Network

In this section, we investigate the performance of our proposed technique in a vehicular environment by using real road-based network simulations. To make the proposed scheme tractable, we make the following assumptions:

1. We assume an ideal MAC layer without contention, collision, or node mobility.

2. All nodes have the initial transmission range equal to 200 m.

3. The number of vehicles was varied from from 250 to 1000.

4. We vary the beamforming angle θ from 22.5 • to 135 • .

We assume that the vehicles are distributed on each lane of the streets according to a Poisson process of intensity λ = 0.04. In other words, the distance between two consecutive vehicles follows an exponential distribution. The average distance between two vehicles is 1 λ . This assumption is based on some traffic studies that have proved that the inter-vehicle spacing on a highway can be modeled by an exponential distribution [START_REF] Wisitpongphan | Routing in Sparse Vehicular Ad Hoc Wireless Networks[END_REF].

Assumption related to the nodes mobility (1), can safely be adopted since during rush hour urban traffic the velocity of vehicles is limited and the vehicles density is very important. Indeed, the speed of nodes in such case, compared to the duration of wireless transmission, is very small and therefore we can assume that the node positions and connectivity do not change significantly from a broadcast operation to another.

Furthermore, we use the framework OpenStreetMap for Matlab [111] to construct a real road topology. Indeed, we have chosen, using the same approach as the previous chapter, the "Champs-Élysées" avenue to test our transmission range adjustment for broadcast-based routing in VANETs. The broadcast process is triggered along this street. Details of the simulation setup parameters are listed in Table 5.1. Two main scenarios are considered here: Fixed and dynamic transmission ranges are used in the beamforming broadcast process. Notice that the initial transmission range r 1 used in the dynamic approach is supposed to be equal to the fixed radius used in the fixed technique.

G power = 1 - P f -P d P f (5.6)
where P f and P d refer to the power used by all participating nodes in case of fixed and dynamic transmission radius respectively. In the case of directional antenna, the transmission power is proportional to the square of the transmission range r. Thus, P f and P d can be respectively expressed as :

β * m 1 * r 2 1 and β * m 2 j=1 r 2 j
Hence, Eq.5.6 can be simplified as follows:

G power = 1 - m 2 j=1 r 2 j m 1 * r 2 1 (5.7)
where m 1 and m 2 are respectively the implicated nodes in the broadcasting operation with fixed and dynamic transmission ranges. From Figure 5.2 we notice that our technique maintains for all cases (n = 500 and n = 750) a gain greater than 55%. We remark also that even using wide values of θ, the power gain stills important. This leads obviously to less interferences and packet loss. Thus, our adjustment technique excels in power preservation compared to a fixed transmission range approach.

In Figure 5.3, we investigate the proportion of implicated nodes in the beamformingbased broadcast operation when varying the density of vehicles. The top two lines are for nodes using a fixed transmission radius with variation of the density of nodes from 750 to 500. The bottom two lines depict the effect of adjusting the transmission range for the same values of nodes densities. When nodes transmit with a high beamforming angle, we observe an increase in the ratio of implicated nodes for the two scenarios. We also notice that transmitting messages within a limited beamwidth as well as with an adjusted transmission range reduces severally the number of nodes having to relay the message compared to a fixed transmission range approach. We observe that transmission range adjustment technique allows a good gain in power utilization such as the previous node distribution case. In addition, the values for the two scenarios are close. show that our approach performs well and fulfills its design functionality i.e., it is able to deliver the message to the destination with a good success probability while minimizing at the same time the bandwidth and power consumption. This observation corroborates the robustness of our scheme.

Analytical Model for the Transmission Area

We provide in the following an analytical model to estimate the area of message transmission (i.e the messages forwarding zone) in the case of an uniform node distribution. The communicating nodes are uniformly positioned in a rectangular area.

The goal of this part is to compare this analytical model to the ratio of implicated nodes (carried out by simulations in the previous section). Each node broadcasts the message according to an angle θ within a radius r proportional to the distance d as indicated by Eq.5.2. Therefore, the propagation shape of the forwarding area can be approximated by Figure 5.8. vertex is located at a distance d i of the destination, is obtained by considering that there is a mobile node transmitting according to an angle θ and within a transmission range r i proportional to the distance d i (see Eq.5.2). This figure has to be considered as an approximation of the actual area of transmission since we have added the supposition of the existence of a minimum transmission range in the broadcasting operation.

Theorem 3 Assuming that C = r 1 d 1 ≪ cos( θ 2 ), the total area of the transmission S total can be expressed as :

S total = 1 2 d 2 1 tan( θ 2 )(1 -e ( -2π tan( θ 2 )
)

) (5.8)
where d 1 is the distance between the first sender and the destination.

Proof: From Figure 5.9 and as we have mentioned before, the radius of transmission r i is proportional to the distance d i (see Eq.5.2). In addition, all nodes, situated on the vertex of each triangle, broadcast the message according to an angle θ. Hence, all triangles T r(i) are similar. Let

γ = d i d i-1
be the coefficient of this similarity. γ is called scale factor. We give a simple expression of γ.

d 2 2 = h 2 + (d 1 -r 1 cos( θ 2 )) 2
h is the height of the triangle ABC. h can be easily expressed as:h = r 1 sin( θ 2 ). Thus, a simple calculation gives:

d 2 2 = d 2 1 + r 2 1 -2r 1 d 1 cos ( θ 2 )
Then, γ can be expressed as follows:

γ = d 2 1 + r 2 1 -2r 1 d 1 cos ( θ 2 ) d 2 γ = 1 + r 2 1 -2r 1 d 1 cos ( θ 2 ) d 2 1
(5.9)

In Eq.5.9,

r 2 1 -2r 1 d 1 cos ( θ 2 ) d 2 1 ≈ 0(d 1 ≫ r 1 )
, then a limited development gives :

γ = 1 + 1 2 ( r 2 1 -2r 1 d 1 cos ( θ 2 ) d 2 1 ) ≈ 1 - r 1 cos( θ 2 ) d 1
(5.10)

We denote α the angle ABC. Then, the total number of triangles T ri situated on the half plane containing the source is given by :

N ≈ π α (5.11)
where

α ≈ sin(α) ≈ r 1 sin( θ 2 ) d 2 α ≈ r 1 sin( θ 2 ) γd 1 (5.12)
The elementary surface of each triangle T r i , denoted as S i , can be computed as follows :

S i = 1 2 r i d i sin θ 2 (5.13)
The similarity between triangles T ri implies that S i = γ 2i S 1 . Then, the total area of transmission can be given by:

S tot = 2 N 1 S i ≈ 2 N 1 γ 2i S 1 ≈ 2S 1 N 1 γ 2i ≈ 2S 1 1 -γ 2N 1 -γ 2 (5.14)
Using the fact that x y = e yLn(x) , and the assumption r 1 d 1 ≪ cos( θ 2 ), γ 2N can be expressed as

γ 2N ≈ e 2N Ln(γ) ≈ e 2N Ln(1- r 1 cos( θ 2 ) d 1 ) γ 2N ≈ e N ( -2r 1 cos( θ 2 ) d 1 )
(5.15) Eq.5.15 can be more simplified by using Eq.5.11, Eq.5.12 and the fact that γ ≪ 1.

We obtain then:

γ 2N ≈ e (-2π cot θ 2 )
(5.16) By using formula (5.10) and replacing γ N by its expression, Eq.5.14 can be expressed as:

S tot ≈ 2S 1 ( 1 -e (-2π cot( θ 2 )) 2r 1 cos( θ 2 ) d 1 ) S tot ≈ 2S 1 ( d 1 (1 -e -2π cot( θ 2 ) ) 2r 1 cos( θ 2 ) ) (5.17)
Hence, replacing S 1 by its expression, Eq.5.17 becomes :

S tot = 2 1 2 r 1 d 1 sin ( θ 2 )( d 1 (1 -e -2π cot( θ 2 ) ) 2r 1 cos θ 2 ) S tot = 1 2 d 2 1 tan( θ 2 )(1 -e ( -2π tan( θ 2 ) ) ) (5.18)
Note that the area of transmission does not depend on the initial radius r 1 (under the assumption r 1 d 1 ≪ cos( θ 2 )). With the above analytical result, we investigate hereafter the accuracy of our theoretical approach by comparing it to simulation results. Note that, the comparison analysis is presented here in terms of the ratio of implicated nodes.

For that purpose, we present in Figure 5.10 a comparison of the implicated nodes' ratio for both simulation and theoretical results. We consider, for the simulation scenario, a total number of communicating nodes equal to 3000.

The top two lines correspond to the case where the initial distance d 1 is equal to 3 Km while the bottom curves are for d 1 equal to 1 Km. We clearly observe that the gap between the simulation and the theoretical curves is very tight in the two cases. Thus, our proposed analytical model provides a good approximation of the real transmission shape.

Conclusion

In this chapter, we have considered the problem of transmission range adjustment in a multihop wireless network context. An optimized technique devoted to the adaptation of the transmission radius based on nodes' local densities and the distance to the destination was proposed. It uses the beamforming-based broadcast technique presented in chapter 3 to broadcast the messages. It also introduced a congestion control mechanism allowing vehicles to adapt their transmission power during the broadcast process. For the performance evaluation, we have tested our approach in two different network distribution: vehicular environment and wireless adhoc scheme.

Conducted simulations for vehicular networks using real street maps corroborate the efficiency of our proposed scheme in terms of ratio of implicated nodes, power transmission gain and probability of transmission success. Our technique confirmed its capacity in maintaining high delivery ratio while minimizing at the same time bandwidth consumption. We have also evaluated our approach in the case of an uniform node distribution and findings confirm the previous results. As a major contribution as well, we have derived an analytical model that provides an estimation of the transmission area. Our mathematical expression stands out for its simplicity and independence from the initial radius r 1 . Simulation results match very well the mathematical expressions and confirm the merit of the analytical model.

Chapter 6

Adaptive Data Collection Protocol using Reinforcement Learning for VANETs In addition, mathematical frameworks were derived to study the performance of our proposals analytically and confirm simulations results. In this part of this thesis, we will be focusing on a different VANET challenging domain called data collection. As any research field, a lot of work has been published on data collection techniques since they make inter-vehicle communications more efficient and reliable while minimizing bandwidth utilization. In fact, most of VANET applications are based on a dissemination process [START_REF] Soua | Broadcast-based directional routing in vehicular ad-hoc networks[END_REF] [113] [START_REF] Bi | Performance A Cross Layer Broadcast Protocol for Multihop Emergency Message Dissemination in Inter-Vehicle Communication[END_REF] [115] [START_REF] Chou | Location-Based Directional Broadcast for intervehicle Communications[END_REF] on which an information must be propagated to rather long distance so that drivers can be alerted in advance. Since each vehicle in a vehicular environment can detect a hazardous situation or a congestion zone, the number of messages pumped on the network might increase dramatically. Hence, data collection, as a technique aiming at collecting similar packets from moving vehicles and aggregating them, is regarded as an important approach to circumvent these problems.

In literature there are several proposals studying data collection protocols in VANETs. However, in our opinion, the existing related works are still not satisfactory, and we feel it is possible to obtain better results. First of all, most the proposed techniques were adapted from MANET proposition and their adjustment to vehicular conditions raises a lot of discussions and critics.

Furthermore, most of the proposed approaches ignore the fast topology changes of VANETs and therefore their performance and effectiveness in such conditions rise some doubts.

To fill this gap, we propose in this chapter a novel data collection technique devoted to vehicular networks, denoted as ADOPEL, designated with the goal of making the collecting operation more reactive to nodes mobility and topology changes. It is based on a distributed Qlearning technique where a reward function is provided and defined to take into account the delay and the number of aggregatable packets.

Before continuing with the remainder of this chapter, a review of existing techniques is necessary in order to underline the novelty of our approach. Then, the system specification is presented afterward followed by an underlining of the basic design of our proposal and its functioning principles. Finally, simulations results are presented and discussed to confirm the effectiveness of our technique.

State of the Art

Data gathering related literature reveals two main aspect for gathering issues. On one hand, some contributions focus on the manner of routing the aggregatable messages along farther distance in order to improve the aggregation ratio (data collection).

On the other hand, other studies concentrate on expressing data to be aggregated differently by using compressing and merging methods to reduce the overhead [START_REF] Cherfaoui | Distributed data fusion: application to confidence management in vehicular networks[END_REF].

In our case, we focus on how to route the aggregatable packets to a specific destination node in order to improve the data collection ratio and hence obtain more accurate global traffic information. Hence, we are not interested here on the mechanisms to express data differently.

Several works have been proposed to investigate the data collection concept by adopting different approaches.

In [START_REF] Saleet | Region-Based Location-Service-Management Protocol for VANETs[END_REF], authors propose a location service management protocol that solves the location querying and updating problems by aggregating the location information data. In this scheme, the vehicle's mobility space is viewed as a grid network which is partitioned into several segments and each segment is divided into a number of cells. The central node of a segment plays the location server role. This server is responsible for storing current location information about all nodes belonging to the same segment. Then, the server aggregates this information and broadcast it to the neighbors. In addition, the protocol uses message aggregation in location querying. It introduces some delays before forwarding the queries in order to gather more queries and aggregate them. This proposal is based on poor flooding to disseminate data on the network which presents a great weakness for this approach. In addition, the choice of the grid structure for the vehicle's mobility space is not justified and makes some ambiguous in this work.

B. Yu et al. in [START_REF] Yu | Adaptive Forwarding Delay Control for VANET Data aggregation[END_REF] focus on making similar reports broadcasted by vehicles meeting each other in order to be aggregated together. In fact, this technique dynamically changes the forwarding speed of nearby reports so that they can be delivered to the same node at the same time and then be merged into a single report. This adaptive forwarding is based on a distributed learning algorithm on which each node learns from local observations and chooses a delay based on the learning results. Simulation results outline the effectiveness of the proposed technique.

In [START_REF] Ibrahim | CASCADE: Cluster-based Accurate Syntactic Compression of Aggregated Data in VANETs[END_REF], A high cost is assigned for the vehicles that are close to the aggregating node. Thus, the produced view of traffic is not useful to any vehicle unless it is in the proximity of the aggregating vehicle.

Lochert et al. in [START_REF] Lochert | Probabilistic Aggregation for Data Dissemination in VANETs[END_REF] [124] focus on cooperative information gathering and sharing applications in VANETs and propose a hierarchical aggregation algorithm. Their proposal is based on a probabilistic data representation Flajolet-Martin sketches, which they extended to a soft-state data structure. In their scheme, there is no longer a need to decide which aggregate contained more up-to-date information since the resulting aggregate comprises all the information from all aggregates that have been merged. Nevertheless, this work does not consider routing related-issues but focus only on data representation.

The aforementioned aggregation/collect approaches do not strictly consider the potentially mobility issue and the collection ratio in finding a suitable relay in the collect process. In fact, most of the listed works focus on the representation and the processing of the aggregated data and neglect how to obtain the raw information among the running vehicles. In the next section, we present in depth our proposal which is interested on collecting aggregatable packets from vehicles taking into ac-count the dynamicity of the network. We use Q-learning method to select next hops aiming at collecting more raw data.

ADOPEL: Proposed Collection Technique

Hereinafter, we introduce ADOPEL technique-an Adaptive distributed Data cOllection Protocol using rEinforcement Learning for VANETs. The proposal is based on a distributed learning algorithm on which a reward function is defined. This latter takes into account the delay and the number of aggregatable packets and hence makes the collection operation more reactive to nodes mobility and topology changes.

After describing the system specifications, we show the functioning algorithm of our technique to investigate in details the different working steps of ADOPEL.

System Specifications

ADOPEL considers that each communicating vehicle knows its current position and speed using a positioning system such a Global Positioning System (GPS). Furthermore, we assume that vehicles exchange two types of messages: beacons and event driven messages. Where the former aims at improving driver awareness of surrounding environment by exchanging information about position, velocity, direction, etc., and the latter is triggered when a vehicle needs to collect traffic data toward a control center.

This collect operation is started by a node called initiator and involves a limited number of vehicles. Here, the initiator is a vehicle that is leading a group of nodes and running in a highway. The initiator, at each gathering operation, is randomly selected from vehicles. Thereby, the initiator have to collect the traffic data from vehicles and deliver it to a Traffic Control Center (T CC) in order to be processed and studied (see Figure 6.1). We assume here that T CCs are sufficiently deployed along the freeway.

In a vehicular context, the collect of traffic related data is periodically carried out and transmitted to a T CC in order to have an up to date big picture of the road.

Thus, ADOPEL triggers periodically a collect operation from the initiator toward a T CC. The collected data is provided to the T CC when this latter is reachable by the node ending the gathering operation. To limit the collection process, we use a d collect parameter, representing the depth of the collecting operation, i.e. the maximal distance in meters from the initiator. Indeed, this parameter reflects the zone that The frequent topology changes in the vehicular context make it necessary to adapt the aggregation and the forwarding policy to the network state. In fact, it is difficult to predict in advance the set of rules that will adjust the actions of each vehicle when the vehicular environment's variables are changing.

Fortunately, the reinforcement learning techniques [START_REF] Panait | Cooperative Multi-Agent Learning: The State of the Art[END_REF] can tackle these problems.

In reinforcement learning, each vehicle is a learner. Each vehicle tries to optimize its interactions with the very dynamic environment through its experience. The experience here is expressed in terms of errors and rewards. In addition, the vehicles collaborate with each other to share their feedbacks and establish the distributed learning system.

In this work, we model the aggregation operation in VANET as a Markov decision problem that can be solved by reinforcement learning. Each vehicle (agent) decides at each state which action to take based on its experience. After taking an action, the agent gets a reward or a cost from the environment.

The Markov decision problem is defined as a tuple s, a, r

• s is the states set; In our work, the packet state is the current vehicle.

• a is the set of actions a vehicle can perform: in our scheme, the action of a node is to select the next relay that will maximize the aggregation ratio. Hence, the possible set of actions allowed at each node is nothing but the set of neighbors.

• r is the immediate reward a vehicle may receive after taking an action a.

To solve this MDP model, we propose to use a reinforcement learning algorithm.

The literature provides a large number of reinforcement learning approaches, such as temporal difference learning, direct utility estimation and Q-learning [START_REF] Russel | Artificial Intelligence: A Modern Approach[END_REF]. We are motivated to use Q-learning algorithm since it allows comparing the expected utility of the available actions without requiring knowledge of the environment's model. A Q(s, a) matrix is used to store the learned reward/cost for each state and action pair. For example Q(s, a) is the expected reward for taking an action a at state s.

The updating function of Q(s, a) is defined as:

Q(s, a) = (1 -α) * Q(s, a) + α * (r + γ * max a ′ Q(s ′ , a ′ )) (6.1)
Where

• α denotes the learning rate which model here how quickly the Q-values can change with a dynamic network topology.

• γ refers to the discount factor. It models the fact that immediate reward is or not more valuable than future reward. If this value is high, future rewards are more valued than immediate reward. In the opposite case, the learning algorithm count immediate rewards more strongly.

• r represents the expected immediate reward of executing action a at state s.

• M ax a ′ Q(s ′ , a ′ ) models the maximum expected future reward when the system reaches the state s ′ after taking the action a.

The most important challenge to successfully achieve the collection performance is to define the suitable reward function. In fact, the vehicle will use this function to update its forwarding policy.

For immediate rewards, we consider the most relevant parameters effective in decision. First factor is based on the number of neighboring vehicles that each node possesses in its transmission range. In fact, the reward should be more for a vehicle with a high number of neighbors. Secondly, the aggregation proposal must route the packet to the destination in a limited delay. Thus, the node has to choose the node that offers the most relevant advance to the destination. It is worth saying that our proposal focuses on a collection process rather than a rapid propagation of a packet in the network. This observation has to be considered on the reward function.

Based on these decision factors, we formulate the reward function as follows :

r =            β * (1 -1 data(i) ) + (1 -β) * ( adv(i) adv(i)avg ) if next hop is not the destination K1 if next hop is the destination -K1
if the vehicle hasn't neighbors (6.

2)

The reward function considers several routing scenarios to improve the aggregation ratio and guarantee a steady advance to the destination.

The first item in Eq.6.2 combines the normalized number of neighboring nodes that the next hop possesses and its normalized progress toward the destination. adv refers to the advance of the node i (current node) to the destination vehicle D, situated at a distance d collect from the initiator, by choosing the neighboring node j as the next hop. This parameter d can be seen as the depth in distance of the collection process.

Hence, this advance can be expressed ad follows:

adv(ij) = dist(i, d) -dist(j, d) (6.3)
The average advance is given by:

adv(i) avg = ( t k=1
adv(ik))/nb neighbor(i) (6.4) where t = nb neighbor(i) is here the total number of neighbors of node i. Thus, more reward is assigned to the next hop with more neighbors and larger relative advance.

In fact, a node with a higher number of surrounding vehicles and a higher advance toward the T CC allows respectively a larger quantity of collected data and a faster delay to reach the destination.

The second item in Eq.6.2 denotes the reward if the node can reach directly the destination D. In this case, the reward is a positive constant K1.

Finally, the last item is to solve the "void" problem in geographic routing. In fact, when a node receives a packet and cannot find a neighboring vehicle, its drops the packet and sends a negative reward to the sending node to inform a forwarding failure. Then, the sending node will choose another vehicle to send the packet based on the Q-values. The node with the highest Q-value will be selected.

As an important feature in our proposal, we use a variable discount factor called γ ′ to handle the instability of the vicinity. This parameter depends on the link stability.

In fact, the node selected as a next relay is the vehicle that will spend more time in the vicinity of the sending vehicle. In this way, we ensure that the route we select is more stable. For that purpose, we define a stability factor SF i as:

SF i =    |N i | |N i+1 | |N i | if |N i | = 0 0 Otherwise (6.5)
Where N i (N i+1 respectively) is the current neighbor set of the sending node i (the forwarding node i+1 respectively). Neighbor list can be attached to the hello messages exchanged between vehicles. As aforementioned, the SF will reflect a higher value for a relatively stable couple of neighbors. Then, a node calculates the discount factor γ ′ as :

γ ′ = γ * SF i (6.6)
Therefore, every time a node has a packet to send, it calculates the reward for its neighboring set, the stability factor and updates the Q-values of its matrix using the following equation:

Q(s, a) = (1 -α) * Q(s, a) + α * (r + γ ′ * max a ′ Q(s ′ , a ′ )) (6.7)
The vehicle with the highest Q-value will be selected as next hop.

Exploration vs Exploitation:

In reinforcement learning there is a balance between exploitation and exploration.

Exploitation occurs when the action selection strategy is based on the highest value of the Qtable. In this case, exploitation will lead to locally optimal policies since the selection is greedy. In the case of most of the optimization problems, this will not lead necessary to a global optimum.

On the other hand, exploration consists on taking risk by choosing the non-optimal action and exploring other choices to obtain more knowledge about the network.

Obviously, excessive exploration degrades the performance of the Qlearning approach.

Thus, convergence is an important issue for our proposed algorithm. Nevertheless, in [START_REF] Watkins | Q-learning[END_REF], authors demonstrate that a Q-learning scheme converges to the optimum actions-values provided that "all actions are repeatedly sampled in all states and action-values are represented discretely". Here, the conditions of convergence are insured. In fact, ADOPEL uses hello messages to sample all its neighbors by computing the γ ′ factor. In addition, the action-values (Q-values) are represented discretely in ADOPEL. As a result of that, we can say loudly that our proposed technique converges to the optimum action values.

ADOPEL Algorithm Overview

Based on the description given in the previous section, we summarize here the different steps of ADOPEL. As stated above, each node uses the received "hello" messages from neighbors to a build a neighboring node table. The "hello" messages contains in addition to the usual information the list of neighboring nodes. This way, each vehicle can maintain its two-hop neighbor list and can easily compute the stability factor given by Eq.6.5.

Algorithm 2 shows the different steps of the execution of ADOPEL on a each node i whenever this latter receives a collect request. This execution is triggered periodically by an initiator node.

As illustrated by Figure 6.2, upon receiving a relaying request, the first step undertaken by a node i aims at collecting data from neighbors by sending them a collect data request. Afterward, the node processes the data received (eg: it computes the average value of the received ones) and starts the relaying process. For the relaying process, it classifies the neighboring nodes on three different lists. Highest priority is attributed to vehicles that are more surrounded and closest to the final destination node situated at a distance d collect . Notice that a vehicle with a large number of neighboring nodes leads to a larger quantity of collected data.

The second phase consists on selecting the appropriate relay node based on the previous classification (see Figure 6.2(c)). This operation depends on the Q-values of Since the collection process is periodically initiated by the initiator, a node i is involved in this operation for few times before leaving the concerned road. Thus, the vehicle learns from its acquired experience (rewards or costs) to select the appropriate relay node ensuring a good collection ratio and a faster propagation toward the destination.

Performance Evaluation

In this section, we show our simulations results and investigate the performance of our proposal in terms of collection ratio and number of hops. We compare our scheme to a non-learning protocol. We call a collection technique "nonlearning" when a first part of relays are selected based on the number of their neighboring cars and the other part are selected based on their advance toward the final destination. The destination is situated at a distance d collect behind the initiator.

Simulation Design

We used MATLAB to conduct simulations using Freeway mobility model. The freeway mobility model emulates the motion behavior of vehicles in a freeway. In our study, we use a freeway which has two lanes in each direction. All lanes of the freeway are 20 Km in length (see Figure 6.3) Figure 6.

3: ADOPEL Simulation framework

To make the proposed scheme tractable, we make the following assumptions:

• We assume an ideal MAC layer without contention and collision.

• All nodes have the initial transmission range equal to 200 m.

• The number of vehicles was varied from from 200 to 400.

• All vehicles are initially positioned at the entrance of the freeway.

• We respectively assigned to α, β and γ the following values: 0.8, 0.7 and 0.8.

• For the data collection depth, we set d collect equal to 1500 m.

In addition, each vehicle stores its own Q-values and the ones received from neighboring nodes (using hello messages) in a matrix to be used in the relaying process.

Furthermore, we compare our scheme to a non-learning version. For that purpose, we suppose for the non-learning schemes that at each relaying operation, a node has a 20 percent (respectively 40 percent) probability of choosing the most surrounding vehicles as a next relay and 80 percent (respectively 60 percent) to choose the node with the largest advance toward the destination node.

Simulation Results

In this section, we focus on the performance of our technique both for the average data collecting ratio and the average number of hops required to reach the final destination node.

Figure 6.4 depicts the average data collection ratio when varying the density of nodes for the two techniques. We can observe that our proposed scheme outperforms loudly the nonlearning versions. In fact, in all cases, ADOPEL achieves a gain of over than 20% compared to the other techniques. This can be explained by the fact that in very dynamically changing networks as VANETs, ADOPEL can change adaptively to better relaying nodes to increase the collect ratio as the network topology changes, whereas the others non-learning protocols find major difficulties to adapt to the dynamicity of the network.

To make a fair analysis, we investigate in Figure 6.5 the average number of hops needed to travel the collect distance d collect . Indeed, a good collect ratio might have a heavy cost and then can be a real weakness for the algorithm. However, 6.5 shows that the gap between the three techniques is very tight even ADOPEL achieves higher values than the others schemes. This clearly implies that our technique achieves a good trade-off between delays and collection ratio. This is because ADOPEL takes the stability of vicinity into account which yields in a higher probability of using nodes moving in the same direction as the destination node to relay aggregated messages.

On the other side, in non-learning versions, the source node may select a node moving in opposite direction as a next hop which can very vulnerable. As a result, many data collection operations may be penalized when relaying vehicles became far away from the destination. To unravel the impact of the depth of the collecting operation on the performance of our proposed technique, we investigate afterward the variation of the parameter d collect and how it will affect the collection ratio and the total number of hops required to reach the T CC. The total number of moving vehicles is equal to 400 for all the following scenarios.

In Figure 6.6, we show the variation of the collection ratio as a function of the distance d collect . We clearly observe, for the three collecting scheme, that the greater the distance d collect the higher the ratio of collected packets. This observation is perfectly expected because when the distance d collect increases, this means that the gathering operation will be extended to an additional parts of the vehicular network and hence it will touch more vehicles. Therefore, the ratio of the implicated vehicles in the collecting operation increases resulting in a higher gathering percent. However, our proposal performs better performance than the non-learning techniques. It can be observed also that the outperformance of ADOPEL is more clear for longer distance.

This can be explained by the fact that longer distances permit to the learning operation to be more efficient when updating the Q-learning values since we have in this case a more global view of the network which affects the learning process. In the following, we present in Figure 6.7 the impact of d collect on the number of hops to reach the control center. Obviously, as d collect increases, the number of required relays to reach T CC become more important. This observation underlines the need of a good trade-off between the two metrics : collection ratio and end-to-end delays. Higher delays may be accepted for non sensitive delay applications (like etraffic and infotainment applications, etc.), however, for e-safety applications, delays have to be less as possible. The comparison, as shown in Figure 6.7 between learning and non-learning techniques reveals that our technique achieves better results than the other approaches specially when the distance d collect is very important. This can be explained by the fact that with a higher distance non learning distance encounters several difficulties in finding the good path toward the T CC regarding the instability of wireless links between neighboring nodes and the higher probability to choose the vehicle moving in the wrong direction. On the other side, ADOPEL, with its stability approach to choose next relays (SF i factor) and learning technique, overcomes the negative effects of large distances and achieves better results in all cases.

Conclusion

In this chapter, we have tried to tackle another inherent challenging problem related to vehicular communications by developing a data collecting technique aiming at gathering raw data from moving vehicles. We proposed a total distributed scheme, namely ADOPEL, based on a Qlearning technique making the collecting operation more reactive to nodes mobility and topology changes. For that purpose, we defined a reward function to take into account the delay and the number of aggregatable packets. In addition, a novel expression of the discount factor γ ′ was provided to handle the instability of the vicinity and to choose the most stable route toward the control center where the raw data will be treated. The Q-learning technique offered to vehicles the opportunity to optimize their interactions with the very dynamic environment through their experience in the network.

To analyze the performance of our proposal, we compared it to a non-learning version to study the effect of the learning technique. We used two important metrics which are directly linked with the efficiency of our collecting approach: The collection ratio and the number of hops. A good technique must achieve a trade off between these two metrics to guarantee its success. Our simulation results show that our technique far outperforms other propositions and achieves a good trade off between delay and collection ratio.

Chapter 7

Conclusion and Ongoing Work

Conclusion

Vehicular networks arise from the incessant need of having safer roads and smooth driving during our daily journeys. This type of networks has given birth to a large variety of applications ranging from safety applications which aim to increase the user and vehicle safety to comfort applications like internet connection or file sharing.

Most of safety applications, if not all, are based on a dissemination process since they need to disseminate the alert information among a large number of moving vehicles or a specific geographic zone.

In our search for a better approach to disseminate emergency message in VANETs among the existing techniques in literature, we have examined, as a first contribution of this thesis, the problem of multihop broadcasting information in a vehicular environment. We have presented our broadcast-based directional routing technique, denoted as EBDR. EBDR is firstly based on a route guidance algorithm responsible for choosing the better route in which the alert packet will be propagated. The choice of this route can be adjusted according the user preferences (shortest path, road with high density of vehicles, etc.). In addition, EBDR uses directional anten- Moreover, we presented an analytical framework that offers a good attempt to model the behavior of our technique in the case of an uniform node distribution suitable to wireless adhoc network scheme.

Finally, we were interested on the data collection mechanisms devoted to VANETs.

This field of research is challenging regarding the rapid changing topology in vehicular networks and in consequence the instability of links between moving vehicles.

To tackle this challenge, we proposed an Adaptive Data cOllection Protocol using rEinforcement Learning (ADOPEL). It is based on a distributed Qlearning technique making the collecting operation more reactive to nodes mobility and topology changes.

In fact, the frequent topology changes in the vehicular context make it necessary to adapt the gathering and the forwarding policy to the network state. In fact, it is difficult to predict in advance the set of rules that will adjust the actions of each vehicle when the vehicular environment's variables are changing. Fortunately, the reinforcement learning techniques can tackle these problems since each vehicle tries to optimize its interactions with the very dynamic environment through its experience expressed in terms of errors and rewards. Simulation results confirm the efficiency of our technique compared to a non-learning version and demonstrate the trade-off achieved between delay and collection ratio.

Future Directions

The analysis and findings presented in this thesis report have shown a good performance for our proposed technique EBDR, as well as its improved version and specially the impressive correctness of our mathematical framework devoted to linear propagation in VANETS. Nevertheless, several future research directions open up.

First of all, we envision to enhance the broadcast technique EBDR with a dynamic adjustment of the beamforming angle θ to make it more adaptive to the local density of nodes and hence improve the bandwidth utilization and reduce the interferences between nodes. In fact, smart antennas have these capabilities of changing the direction as well as the width of beams transmitted toward the required destination. As such, we will grasp all the potential capabilities offered by these smart antennas.

In addition, we are interested on information relaying in the planar case. We aim at providing a complete mathematical framework that will be able to investigate the performance of multihop protocols in this special case. We think that our analyti- Nous nous sommes intéressés dans la dernière partie au probème de collecte de données et nous avons proposé un algorithme basé sur l'apprentissage appelé ADOPEL qui adapte sa politique de collecte selon la stabilité des liens entre les véhicules et le nombre de paquets à collecter. La comparison avec des techniques qui n'utlise pas de l'apprentissage a permet de dévoiler l'efficacité de notre approche.

Néanmoins, plusieurs directions de recherche s'ouvrent à la fin de cette thèse :

Tout d'abord, nous envisageons d'améliorer la technique EBDR par un ajustement

1

 1 Probability of transmission success (d = 2000m) . . . . . . . . . . . . xiii LIST OF FIGURES xiv 3.18 Probability of transmission success (d = 3000m) . . . . . . . . . . . . 3.19 Area of transmission . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.20 Comparison between the theoretical and practical values of the implicated nodes ratio for different densities . . . . . . . . . . . . . . . . . 3.21 Relative simulation results . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Linear propagation scheme . . . . . . . . . . . . . . . . . . . . . . . . 4.2 One dimension Broadcasting scheme . . . . . . . . . . . . . . . . . . 4.3 Precision of the probability model varying the density of vehicles . . . 4.4 Effect of distance on the broadcasting operation . . . . . . . . . . . . 4.5 Effect of distance on the probability of success . . . . . . . . . . . . . 4.6 Probability of success when varying the parameter b . . . . . . . . . . 4.7 The average number of hops: Simulation vs. analytical results using Theorem 1 and varying d . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 The average number of hops: Simulation vs. analytical results varying λ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Precision of the average number of hops model varying the density of vehicles λ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 The average number of hops: Simulation vs. analytical results varying d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11 Effect of b variation in the average number of hop model . . . . . . . 4.12 Precision of the average number of hops model varying the parameter b (d = 2000 m) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Implicated Nodes in the forwarding process for the 2 approaches . . . 5.2 Power transmission gain . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Ratio of implicated nodes: Comparison overview . . . . . . . . . . . . 5.4 Probability of transmission success: Comparison overview . . . . . . . 5.5 Uniform distribution: Implicated nodes for the 2 approaches . . . . . 5.6 Power transmission gain . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Effect of d on the the probability of success . . . . . . . . . . . . . . . 5.8 Forwarding shape with dynamic transmission range . . . . . . . . . . 5.9 Similar triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10 Comparison between the theoretical and practical values of the implicated nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 ADOPEL functioning Overview . . . . . . . . . . . . . . . . . . . . . 6.2 ADOPEL algorithm overview . . . . . . . . . . . . . . . . . . . . . . 6.3 ADOPEL Simulation framework . . . . . . . . . . . . . . . . . . . . . 6.4 The average data collect ratio: ADOPEL vs Non-learning versions . . 6.5 The average number of hops: ADOPEL vs Non-learning versions . . . 6.6 Effect of the variation of d collect on the ratio of collected packets . . . 6.7 Effect of the variation of d collect on the number of hops . . . . . . . . A.1 Structure du paquet à transmettre . . . . . . . . . . . . . . . . . . . A.2 Diffusion directionnelle dans VANETs . . . . . . . . . . . . . . . . . . A.3 Variation de la probabilité de succès en fonction de la densité des noeuds136 A.4 Impact de la distance sur la propagation du paquet . . . . . . . . . . A.5 Régime de propagation linéaire dans VANETs . . . . . . . . . . . . . A.6 Précision du modèle de probabilité en variant la densité de véhicules . A.7 Le nombre moyen de sauts: Simulation vs résultats analytiques en variant λ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.8 Le nombre moyen de sauts: Simulation vs résultats analytiques en variant d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.9 Gain en puissance de transmission . . . . . . . . . . . . . . . . . . . . A.10 Comparaison entre les valeurs théoriques et de simulation des noeuds impliqués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.11 Taux moyen de collecte de données: ADOPEL vs les versions nonlearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter Introduction 1.

1 1. 1

 11 Motivations

2

 2

Figure 2 . 1 :

 21 Figure 2.1: An overview of a VANET network

Figure 2 . 2 :

 22 Figure 2.2: Different equipments present on a VANET vehicle

  Network topology and density: Unlike adhoc networks, VANETs are characterized by high mobility caused by highly mobile vehicles. In fact, a node can join and leave the network in a very short time, which makes the topology changing frequently. In addition, issues of scaling must be included in the solutions because the network can become very large. In addition, network density in VANETs can vary from a very dense network (urban case) to a sparse node distribution (rural case, very late night hour). If the connectivity between cars is guaranteed in the first case, it becomes a rare phenomenon for the latter case[START_REF] Viriyasitavat | Network Connectivity of VANETs in Urban Areas[END_REF] [10]. Thus, VANET protocols have to tackle these density variation challenges to perform well.• Mobility model and network distribution: Environments in ad hoc networks are often limited to open spaces. In VANETs, the topology is dynamic but it is not completely random because the distribution of moving vehicles is generally along roads (streets, highways) as illustrated by Figure2.3. In fact, mobility of vehicles is somewhat restricted by predefined roads, as well as the direction and the number of lanes[START_REF] Mahajan | Urban mobility models for VANETs[END_REF].

Figure 2 . 3 :

 23 Figure 2.3: Example of road networks

Figure 2 . 4 : 1 .

 241 Figure 2.4: VANETs projects

Figure 2 . 5 :

 25 Figure 2.5: CALM architecture

Figure 2 .

 2 Figure 2.6: ITS architecture

Figure 2 .

 2 Figure 2.7: WAVE architecture

Figure 2 . 8 :

 28 Figure 2.8: Hazardous location warning scheme

Figure 2 . 9 :

 29 Figure 2.9: Vehicle 2 Vehicle Cooperative Awareness

Figure 2 . 10 :

 210 Figure 2.10: Sign extension alert

Figure 2 . 11 :

 211 Figure 2.11: Road congestion alert

Figure 2 . 12 :

 212 Figure 2.12: Merging assistance application

Figure 2 . 13 :

 213 Figure 2.13: VANET comfort applications

  [START_REF] Briesemeister | Role-based multicast in highly mobile but sparsely connected ad hoc networks[END_REF] [69] [61] [70] [62] [71] [63] [68] [64]

Figure 3 . 1 :

 31 Figure 3.1: Directional antenna model

Figure 3 . 2 :

 32 Figure 3.2: Road map representation

  .3.

Figure 3 . 3 :

 33 Figure 3.3: Packet structure

Figure 3 . 4 :

 34 Figure 3.4: Directional Broadcast in VANETs

Figure 3 . 5 :

 35 Figure 3.5: Packet propagation mechanism

4 :

 4 Transmission of the packet by S using beamforming angle toward the first D i . 5: for each node i do 6:

14 :

 14 until D i =D 15:

3. 6 )

 6 Figure 3.6: Simulation framework

  .7), centered at latitude: 2.303 • and longitude: 48.8712 • , has 10 intersections and 17 road segments. The main street (Champs-Élysées) is composed of 4 lanes in each direction. All lanes are 2 Km in length. The total width of the Champs-Élysées street is equal to 30 meters.

Figure 3 . 7 :

 37 Figure 3.7: Road topology

  Figure 3.8: Implicated Nodes in the transmissions for the 2 approaches

Figure 3 . 9 :

 39 Figure 3.9: Simulated values of probability of success

Figure 3 . 10 :

 310 Figure 3.10: Effect of distance on the broadcasting operation

Figure 3 . 11 :Figure 3 . 12 :

 311312 Figure 3.11: Ratio of implicated nodes: Comparison overview

  broadcast operation are almost the nodes located on the subroutes between S and D. The additional amount of time present on the top line is due to the additional broadcast transmissions performed by the neighbor nodes of the final destination and some nodes reached by the beamforming technique and present on secondary roads.For this metric, blind broadcast achieves 17.54 ms . As in the previous finding, our proposed EBDR far outperforms the traditional broadcast. In fact, even for largest value of θ = 90 • , our technique achieves a delay equal to 6.22 ms. This observation confirms the outperformance of our proposal in terms of total transmission delay and more specially demonstrates that the arrival time at destination is almost the same as the total broadcast delay: When the packet arrives at the destination D, all transmissions are almost implicitly stopped. This feature represents a major key in our modeling conception and underlines the efficiency of our technique.

Figure 3 .

 3 Figure 3.14 gives the ratio of implicated nodes in the transmission when varying the angle θ. Clearly, the fact that we transmit messages within a limited area reduces the number of nodes having to relay the message and in turn considerably reduces the total number of transmissions. In addition, the use of indicators to determine whether a node had already transmitted a message gives us the possibility to avoid unnecessary retransmissions and hence avoid the broadcast storms.

Figure 3 . 13 :

 313 Figure 3.13: Network topology and distribution of implicated nodes in the transmissions

Figure 3 . 15 :

 315 Figure 3.15: Gain in bandwidth

  Figures 3.16, 3.17 and 3.18 show the variations of the success probability with the beamforming angle. In each figure, different densities are considered (different node numbers). The distance d between the source and the destination is equal to 1000m

Figure 3 .Figure 3 . 18 :

 3318 Figure 3.16: Probability of transmission success (d = 1000m)

Figure 3 .Figure 3 . 20 :

 3320 Figure 3.21 represents the relative error of the model computed as follows:

Figure 4 .Figure 4 . 1 :

 441 Figure 4.1: Linear propagation scheme

Figure 4 . 2 :

 42 Figure 4.2: One dimension Broadcasting scheme

  While we are only interested in computing S(d, r), we must compute S(d, a) for different values of d and a.

Figure 4 .

 4 Figure 4.2 represents the situation described above. The first vehicle (S) will transmit the broadcast message with a range a, where 0 < a ≤ r, while the farthest vehicle transmits within a distance r.

Figure 4 . 3 :

 43 Figure 4.3: Precision of the probability model varying the density of vehicles

Figure 4 .

 4 Figure 4.4 shows again that the lower and upper bounds are very close . Furthermore, in this case as well there is an excellent agreement between the results obtained with the analytical model and the simulations.

Figure 4 . 4 :Figure 4 . 5 :

 4445 Figure 4.4: Effect of distance on the broadcasting operation

( a )

 a Effect of b variations on the probability of success (b) Precision of the probability model when varying the parameter b

Figure 4 . 6 :

 46 Figure 4.6: Probability of success when varying the parameter b

Figure 4 . 7 :

 47 Figure 4.7: The average number of hops: Simulation vs. analytical results using Theorem 1 and varying d

. 14 )

 14 Using Eq.4.11 and Eq.4.2, Eq.4.14 becomes : h(d, a) = a 0 λe -λ(a-x) h(da, ra + x)S(da, ra + x)dx S(d, a) + a 0 λe -λ(a-x) S(da, ra + x)dx S(d, a) h(d, a) = S(d, a) + a 0 λe -λ(a-x) h(da, ra + x)S(da, ra + x)dx S(d, a) h(d, a) = 1 + a 0 λe -λ(a-x) h(da, ra + x)S(da, ra + x)dx S(d, a) (4.15)

  average number of hops required to reach the final destination D , we compute the sum of hop numbers required to reach each intermediate destination D i . In our case, the main route is composed of three segments: (S,D 1 ), (D 1 , D 2 ) and (D 2 , D). The number of hops is obtained by computing the length of the shortest path between these intermediate nodes S, D 1 , D 2 and D . The transmission range r is always equal to 200 m. In Figure 4.8, several simulations are performed with different vehicle densities λ. The distance d between the source and the destination is here equal to 2000 m while we took b = 2. Lower bounds, upper bounds and simulated values are reported on Figure 4.8.

Figure 4 . 8 :

 48 Figure 4.8: The average number of hops: Simulation vs. analytical results varying λ

Figure 4 . 9 :Figure 4 . 10 :

 49410 Figure 4.9: Precision of the average number of hops model varying the density of vehicles λ

  and 4.9, it emerges clearly that our proposed theoretical framework is very accurate. In particular, lower and upper bounds become very close to the simulated value when the density increases. Also observe that the average number of hops shown on Figure 4.8 becomes constant when λ increases. In fact, the average number of hops is almost equal to ⌈ d r ⌉ for high densities. Moreover, several simulations are conducted with different values of d to evaluate the behavior of the upper and lower bounds (here b = 2 and λ = 0.02). Results are reported in Figure 4.10. The upper and the lower bounds seem to be very precise when the ratio d r is small. When the distance increases, since the bounds are computed by dynamic programming, there is an accumulation of errors leading to less and less precise bounds. Whereas, we observe that the simulation value is always in the range limited by the lower and upper bounds. In order to study the effect of the parameter b on the precision of our model, we ran several simulations with different values of b.

Figure 4 .

 4 11 reveals the performance of our analytical model when b is varying from 1 to 4 and for distance d = 2000 m.

Figure 4 . 11 :

 411 Figure 4.11: Effect of b variation in the average number of hop model

Figure 4 . 12 :

 412 Figure 4.12: Precision of the average number of hops model varying the parameter b (d = 2000 m)

  Figures 5.1(a) and 5.1(b) provide a comparison of the snapshot of the relaying nodes involved in the transmission process for both the two approaches. The maps represent a zoom of one region of the Champs-Élysées street. Circled nodes denote the vehicles implicated in the forwarding operation. We observe that, with the dynamic transmission range, nodes located on the side streets are not participating in the broadcast process contrary to the fixed transmission radius technique. Furthermore, the adjusted radius technique reduces the number of implicated vehicles in the Champs-Élysées main street compared to the fixed range method. Hence, we can conclude that the adjustment of the transmission radius significantly reduces the number of implicated nodes.

Figure 5 . 1 :

 51 Figure 5.1: Implicated Nodes in the forwarding process for the 2 approaches

Figure 5 . 2 :

 52 Figure 5.2: Power transmission gain

Figure 5 . 3 :Figure 5 . 5

 5355 Figure 5.3: Ratio of implicated nodes: Comparison overview

(a) Approach 1 :Figure 5 . 5 :

 155 Figure 5.5: Uniform distribution: Implicated nodes for the 2 approaches

Figure 5 .Figure 5 . 6 :Figure 5 . 7 :

 55657 Figure 5.7 depicts the variation of the probability of transmission success considering different values of distance d 1 .We notice that the proposed technique ensures a high reachability even in the case of a little density of nodes. We see also that the power efficiency technique achieves less performance than the fixed transmission range-based technique. Nevertheless, the two curves are still very close. These results

Figure 5 . 8 :

 58 Figure 5.8: Forwarding shape with dynamic transmission range

Figure 5 . 9 := d 2 d 1

 591 Figure 5.9: Similar triangles

Figure 5 . 10 :

 510 Figure 5.10: Comparison between the theoretical and practical values of the implicated nodes

Contents 6 . 1 98 6. 2 102 6. 3 . 1 102 6. 3 . 2 103 6. 4 115 6. 1 Introduction

 61982102311023210341151 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . State of the Art . . . . . . . . . . . . . . . . . . . . . . . . 99 6.3 ADOPEL: Proposed Collection Technique . . . . . . . . System Specifications . . . . . . . . . . . . . . . . . . . . . Protocol Design . . . . . . . . . . . . . . . . . . . . . . . . . Performance Evaluation . . . . . . . . . . . . . . . . . . . 110 6.4.1 Simulation Design . . . . . . . . . . . . . . . . . . . . . . . 110 6.4.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . 111 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . As mentioned at the outset, we are interested through this thesis on enhancing vehicular communications under different scenarios and optimizations. Each of our contributions focus on a particular research field of the VANET world and tries to address the relevant challenges of nowadays VANET studies. Previous proposals investigated the dissemination process in VANETs and implemented techniques (directional broadcast, congestion control) to minimize interferences and save bandwidth.

  authors present their proposal, called CASCADE, where they expose a new clustering-based data aggregation technique. This protocol uses two types of reports: primary and aggregated records. The first ones are broadcasted periodically by the nodes and comprise the local view of each vehicle. Then, the local view is grouped into clusters and used to compact and aggregate the local view data into an aggregated record. This aggregated record is then broadcast to neighboring vehicles to provide them information about vehicles beyond the local view. This technique allows vehicles to have an extended view of the road behind and then accurate information about upcoming traffic conditions. However, their approach introduced a large overhead to build the global view. Another effort carried out by Y. Dieudonne et al. in [121] focuses on a distributed collection information for VANETs. It collects data produced by vehicles using intervehicle communications only. It is based on the operator ant allowing to construct a local view of the network and therefore to collect data in spite of the network topology changes. A theoretical proof of correctness and experiments confirm the efficiency of the proposed technique. Nadeem et al. [122] introduce a system for data dissemination and aggregation in a vehicular context namely Traffic View. In this system, an aggregate record is composed of specific information: single speed, position, timestamp value and a list of vehicle's IDs. The authors propose two aggregation schemes: ratio and cost based techniques. In the ratio-based, the most important parameter is the aggregation ratio which indicates the number of vehicles to be aggregated into one single frame. For the cost based technique, a specific cost function is defined for each aggregating vehicle.

Figure 6 . 1 :

 61 Figure 6.1: ADOPEL functioning Overview

( a )Figure 6 . 2 :

 a62 Figure 6.2: ADOPEL algorithm overview

Figure 6 . 4 :Figure 6 . 5 :

 6465 Figure 6.4: The average data collect ratio: ADOPEL vs Non-learning versions

Figure 6 . 6 :

 66 Figure 6.6: Effect of the variation of d collect on the ratio of collected packets

Figure 6 . 7 :

 67 Figure 6.7: Effect of the variation of d collect on the number of hops

  nas to transmit the message among neighboring vehicles. These smart antennas have shown their merit in the conservation of bandwidth, energy consumption as well as the minimization of wireless interferences when compared to other omnidirectional antennas. Conducted simulations using a dedicated VANET simulator, have corroborated the efficiency of our technique in comparison to the flooding technique and shown that EBDR maintained a low bandwidth consumption and low end-to-end delivery delay. Interestingly, in spite of the broadcast nature of the proposed technique, all transmissions, in our proposal, stop very soon after the arrival of a packet to its destination. In addition, the arrival time at destination is almost the same as the total broadcast delay: when the packet arrives at the destination D, all transmissions are almost implicitly stopped. This feature represents a major key in our modeling conception and underlines the efficiency of our technique.Afterward, we have investigated the evaluation of our proposed technique EBDR analytically. As such, we have constructed a novel complete mathematical framework based on a recursive approach that offers precious insights about the protocol behavior. In fact, our analytical models provided uppers and lower bounds for two performance metrics: the probability of transmission success and the average number of hops to reach the final destination. This contribution presented the first attempt to investigate this number of relays (or hops) in this specific scheme of a known destination. The pertinence of our analytical expressions have been verified by comparisons with simulation results. Findings confirmed the correctness of the proposed analytical framework. Thereby, our mathematical framework stands out as a promising mathematical tool to evaluate the performance of end-to-end linear propagation in any mobile adhoc networks.On the basis of the performance shown by the EBDR protocol in the first chapter, we have presented an improvement of EBDR aiming at guaranteeing a greater efficiency (a smaller number of implicated nodes in the multihop transmissions), without penalizing the reachability of the EBDR first version. For that purpose, we added a congestion control mechanism to the EBDR protocol called transmission power adjustment. In fact, transmission power control has a great impact on the number of hidden nodes, and can increase the spatial reuse, and hence the channel capacity, in a congested network like a vehicular network. The new technique proposes a fully distributed scheme that allows nodes to set dynamically their transmission range based on their local densities and the distance to the destination. Conducted simulations confirmed the efficiency of our enhanced technique for several performance metrics.

cal model presented in chapter 4

 4 represents a good starting point to design such a complete framework. composante clé de cette évolution. Ces réseaux auto-organisés sont formés spontanément à partir d'un ensemble d'entités mobiles communicantes, sans nécessiter d'infrastructure fixe préexistante telle qu'une station de base ou un point d'accès par exemple. Les entités mobiles constituent en elles-mêmes le réseau. Elles peuvent être de formes variées : ordinateurs portables, téléphones mobiles, assistants électroniques, capteurs et présentent par conséquent des capacités non homogènes en termes de communication, de puissance de calcul et de stockage. L'hétérogénéité de ces réseaux, l'absence d'infrastructure et le besoin de plus en plus croissant d'un système de transport intelligent(ITS) ainsi que l'engagement des industriels ont ouvert de nouvelles perspectives pour les réseaux ad-hoc mobiles avec, par exemple, l'émergence sans précédente des réseaux véhiculaires. En effet, Les réseaux véhiculaires (VANET) sont une projection des systèmes de transports intelligents. Les véhicules, qui constituent les noeuds du réseau ad-hoc, communiquent les uns avec les autres par l'intermédiaire de la communication intervéhicule (V2V) aussi bien qu'avec les équipements de la route par l'intermédiaire de la communication d'équipement-à-Véhicule (I2V), ceci dans le but fort louable d'éviter les accidents en prévenant leurs conducteurs de dangers potentiels causés par d'autres automobilistes ou par des dangers sur la route. L'avènement des réseaux véhiculaires laisse entrevoir une myriade de possibilités de partage et d'exploitation des informations échangées entre les véhicules. Parmi ces domaines, un des plus prioritaires est celui lié à la sécurité des personnes et plus particulièrement sur les routes. En effet, le premier objectif d'un tel système de transport intelligent vise à diminuer les accidents en augmentant les informations disponibles au niveau du véhicule. Ce spectre d'application très étendu recouvre aussi une gestion efficace du trafic routier en aidant le conducteur à perdre moins de temps sur les routes et un confort routier qui permet par exemple aux passagers de naviguer sur Internet, faire de la vidéo à la demande. Dans cette perspective d'utilisation des possibilités de communications V2V et V2I offertes par un réseau et dans le but de rendre nos routes plus sûres et plus confortables, de nouveaux défis sont posés en termes de protocoles et d'architectures de communication qui doivent faire face à des caractéristiques inhérentes à ces réseaux d'automobiles telles que la grande mobilité des noeuds, la connectivité intermittente, et la fragmentation fréquente du réseau. Suivant cette même vision, nous nous intéressons dans ce manuscrit de thèse aux approches de dissémination des informations d'alerte dans un réseau VANET pour les applications eSafety. Ces mécanismes visent à informer le conducteur à un stage précoce d'une situation dangereuse sur la route en lui permettant ainsi de prendre les précautions nécessaires pour contourner ce danger. Notre objectif est d'optimiser les communications V2V afin de proposer une solution de dissémination (appelée EBDR) basée sur des transmissions directionnelles (en utilisant des antennes directionnelles) et un algorithme de guidage permettant de choisir la meilleure route que doit suivre le paquet selon les préférences du conducteur ou de l'application. Nous nous sommes aussi intéréssés à la modélisation mathématique de notre protocole de dissémination EBDR afin d'évaluer ses performances analytiquement. Ce modèle récursif a permis d'obtenir deux métriques de performances: La probabilité de succès et le nombre de sauts requis pour atteindre la destination. La comparison entre les résultats de simulation et les valeurs obtenues analytiquement ont permis de confirmer la précision de notre approche mathématique. Nous avons aussi amélioré notre technique EBDR par un mécanisme de contrôle de congestion. Ainsi, nous avons utilisé l'ajustement de la puissance de transmission (et donc l'ajustement du rayon de transmission) pour envoyer les messages. En fait, chaque noeud calcule son rayon de transmission en se basant sur la densité locale des voitures voisines et la distance qui le sépare de la destination finale. Cette technique a permis d'améliorer d'avantage les performances de notre approche en terme de consommation de bande passante tout en conservant son efficacité en terme de probabilité de succès. Finalement, nous nous sommes intéressés aux mécanismes de collecte de données dans les réseaux véhiculaires vu qu'ils rendent plus efficace les communications intervéhiculaires et minimisent l'utilisation de la bande passante. Plusieurs travaux existent dans la littérature, néanmoins, notre proposition se présente comme l'un des rares efforts qui utilise la technique d'apprentissage Q-learning pour collecter les données entre les véhicules en mouvement. L'objectif derrière l'utilisation de la technique d'apprentissage et de rendre l'opération de collecte plus réactive à la mobilité des noeuds et le changement fréquent de la toplogie du réseau.

Figure A. 1 :A. 2 . 1 . 1

 1211 Figure A.1: Structure du paquet à transmettre

Figure A. 2 :

 2 Figure A.2: Diffusion directionnelle dans VANETs

Figure A. 3 :

 3 Figure A.3: Variation de la probabilité de succès en fonction de la densité des noeuds

Figure A. 4 :

 4 Figure A.4: Impact de la distance sur la propagation du paquet

Figure A. 5 : 1 j=0e 1 j=0eFigure A. 6 :

 5116 Figure A.5: Régime de propagation linéaire dans VANETs

Figure A. 8 := r 1 d 1 (A. 4 ) 2 * θ 2 * λ i ≈ 1 (A. 6 )

 8142216 Figure A.8: Le nombre moyen de sauts: Simulation vs résultats analytiques en variant d

Figure A. 9 : 8 )

 98 Figure A.9: Gain en puissance de transmission

Figure A. 10 :

 10 Figure A.10: Comparaison entre les valeurs théoriques et de simulation des noeuds impliqués

  Simulation framework . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Road topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Implicated Nodes in the transmissions for the 2 approaches . . . . . . 3.9 Simulated values of probability of success . . . . . . . . . . . . . . . . 3.10 Effect of distance on the broadcasting operation . . . . . . . . . . . . 3.11 Ratio of implicated nodes: Comparison overview . . . . . . . . . . . . 3.12 Broadcast delay: Comparison overview . . . . . . . . . . . . . . . . . 3.13 Network topology and distribution of implicated nodes in the transmissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14 Ratio of implicated nodes . . . . . . . . . . . . . . . . . . . . . . . . 3.15 Gain in bandwidth . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.16 Probability of transmission success (d = 1000m) . . . . . . . . . . . . 3.17

2.1 An overview of a VANET network . . . . . . . . . . . . . . . . . . . . 2.2 Different equipments present on a VANET vehicle . . . . . . . . . . . 2.3 Example of road networks . . . . . . . . . . . . . . . . . . . . . . . . 2.4 VANETs projects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 CALM architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 ITS architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 WAVE architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Hazardous location warning scheme . . . . . . . . . . . . . . . . . . . 2.9 Vehicle 2 Vehicle Cooperative Awareness . . . . . . . . . . . . . . . . 2.10 Sign extension alert . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.11 Road congestion alert . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.12 Merging assistance application . . . . . . . . . . . . . . . . . . . . . . 2.13 VANET comfort applications . . . . . . . . . . . . . . . . . . . . . . 3.1 Directional antenna model . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Road map representation . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Packet structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Directional Broadcast in VANETs . . . . . . . . . . . . . . . . . . . . 3.5 Packet propagation mechanism . . . . . . . . . . . . . . . . . . . . . 3.6

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Dissemination in VANET: Specific Requirements and Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . Results and Analysis . . . . . . . . . . . . . . . . . . . . . . 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Chapter 3
	Broadcast-based Routing technique for
	VANETs using Directional Antennas
	Contents
	3.1 3.2.1 Principe and Motivation . . . . . . . . . . . . . . . . . . . .
	3.2.2 Dissemination Related Challenges . . . . . . . . . . . . . .
	3.3 State-of-the Art: Techniques for Information Dissemi-
	nation in VANETs . . . . . . . . . . . . . . . . . . . . . . .
	3.3.1 Distance-based Broadcast Protocols . . . . . . . . . . . . .
	3.3.2 Probability based Broadcast Protocols . . . . . . . . . . . .
	3.3.3 Neighbor-knowledge-based Protocols . . . . . . . . . . . . .
	3.4 Proposed Technique: EBDR . . . . . . . . . . . . . . . . .
	3.4.1 Directional Antenna Model . . . . . . . . . . . . . . . . . .
	3.4.2 EBDR Conception . . . . . . . . . . . . . . . . . . . . . . .
	3.4.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . .
	3.5 Other Application Scenarios of EBDR . . . . . . . . . . .
	3.5.1 Protocol Design . . . . . . . . . . . . . . . . . . . . . . . . .
	3.5.2

Table 3 . 1 :

 31 Simulation Parameters

	Parameter	Value
	Density of vehicles λ (veh/m) from 0.01 to 0.09
	Beamforming angle θ	from 10 • to 90 •
	Transmission power (pMax)	4 dbm
	Transmission range r 1	200 m
	Beacon periodicity	1 s
	Bit rate	18 Mbps
	Number of service channels	2
	Physical layer	IEEE 802.11p
	Accident start time	302 s
	Accident duration

Table 5 .

 5

	1: Simulation Configurations
	Parameter	Value
	Number of vehicles	from 250 to 1000
	Beamforming angle θ	from 11.25 • to 120 •
	Initial distance d 1	1500m
	Initial transmission range r 1	200m
	Coefficient C	0.13

Vehicle Information and Communication System

Control Channel

dynamique de l'angle de beamforming θ pour l'adapter à la densité locale des noeuds et améliorer ainsi l'utlisation de la bande passante et réduire les interférences.En outre, nous intéressons au relayage de l'information dans le cas planaire. Nous visons à fournir un framework mathématique complet capable d'étudier les performances des protocoles de diffusion multi-sauts dans ce cas de figure. Nous pensons aussi que notre modèle mathématique présenté au chapitre 4 représente un bon point de départ pour concevoir un tel outil mathématique complet.

gratitude to my supervisor, Prof. Hossam Afifi for his continuous support and his constant guidance during

applications. The performance of our technique will be studied through simulations, which will be properly described before presenting the obtained results. We provide afterwards an analytical model to estimate the area of messages transmission (i.e the message's forwarding zone). Comparison with simulation findings confirms the correctness of the theoretical expressions.

Algorithm 2 ADOPEL algorithm, for evry node i 1: Send a data collection request to neighboring nodes.

2: L1, L2, L3 are 3 lists initialized by NULL.

3: Q i is initialized based on the number of surrounding vehicles and the advance toward the destination.

4: N i is the neighboring nodes set of node i

for j ∈ N i do 7:

i compares each of its neighboring node j as follows :

8:

if "nb n eighbor(j) = 0 and (advance(j) > advance(i))" then if "nb n eighbor(j) = 0 and (advance(j) > advance(i))" then if "nb n eighbor(j) = 0 and (advance(j) ≤ advance(i))" then if "L1 = ∅" then if

The node with largest Q-Value will be the next hop

Next Hop will be chosen from L3 with the highest Q-Value

26:

end if

27:

i relays the message to the selected next hop after making aggregation (computing average value) i chooses its previous source as the next hop.