This thesis presents the Forecasting Routing Technique (FORTEL), a routing protocol for Mobile Ad-Hoc Networks (MANETs) based on the nodes' Location Information. FORTEL stores the nodes' location information in the Location Table (LT) in order to construct routes between the source and the destination nodes. FORTEL follows the source routing strategy, which has rarely been applied in position-based routing. According to the source routing strategy, the end-to-end route is attached to the packet, therefore, the processing cost, in regards to the intermediate nodes that simply relay the packet according to route, is minimized. FORTEL's key mechanisms include: first, the location update scheme, employed to keep the LT entries up-to-date with the network topology. Besides the mobility variation and the constant rate location update schemes applied, a window location update scheme is presented to increase the LT's information accuracy. Second, the switching mechanism, between "Hello" message and location update employed, to reduce the protocol's routing overhead. Third and most important is the route computation mechanism, which is integrated with a topology forecasting technique to construct up-to-date routes between the communication peers, aiming to achieve high delivery rate and increase the protocol robustness against the nodes' movement. FORTEL demonstrates higher performance as compared to other MANET's routing protocols, and it delivers up to 20% more packets than AODV and up to 60 % more than DSR and OLSR, while maintaining low levels of routing overhead and network delay at the same time. The effectiveness of the window update scheme is also discussed, and it proves to increase FORTEL's delivery rate by up to 30% as compared to the other update schemes. A common and frequently occurring phenomenon, in wireless networks, is the Hidden Terminal problem that significantly impacts the communication performance and the efficiency of the routing and MAC protocols. Beaconless routing approach in MANETs, which delivers data packets without prior knowledge of any sort `of information, suffers from packet duplication caused by the hidden nodes during the contention process. Moreover, the throughput of the IEEE MAC protocol decreases dramatically when the hidden terminal problem occurs. RTS/CTS mechanism fails to eliminate the problem and can further degrade the network's performance by introducing additional overhead. To tackle these challenges, this thesis presents two techniques, the Sender Suppression Algorithm and the Location-Aided MAC, where both rely on the nodes' position to eliminate packet duplication in the beaconless routing and improve the performance of the 802.11 MAC respectively. Both schemes are based on the concept of grouping the nodes into zones and assign different time delay to each one. According to the Sender Suppression Algorithm, the sender's forwarding area is divided into three zones, therefore, the local timer, set to define the time that the receiver has to wait before responding to the sender's transmission, is added to the assigned zone delay. Following the first response, the sender interferes and suppresses the receivers with active timer of. On the other hand, the Location-Aided MAC, essentially a hybrid MAC, combines the concepts of time division and carrier sensing. The radio range of the wireless receiver is partitioned into four zones with different zone delays assigned to each zone. Channel access within the zone is purely controlled by CSMA/CA protocol, while it is time-based amongst zones. The effectiveness of the proposed techniques is demonstrated through simulation tests. Location-Aided MAC considerably improves the network's throughput compared to CSMA/CA and RTS/CTS. However, remarkable results come when the proposed technique and the RTS/CTS are combined, which achieves up to 20% more throughput as compared to the standalone RTS/CTS. Finally, the thesis presents a novel link lifetime estimation method for greedy forwarding to compute the link duration between two nodes. Based on a newly introduced Stability-Aware Greedy (SAG) scheme, the proposed method incorporates the destination node in the computation process and thus has a significant advantage over the conventional method, which only considers the information of the nodes composing the link.

Vehicular Ad hoc Network (VANET) is a promising emerging technology that enables road safety, traffic management, and passengers and drivers comfort applications. Many applications require multi-hop routing; position-based routing (PBR) is a well-recognized routing paradigm that performs well in the vehicular context to enable these applications. However, there are many security challenges and various routing attacks which may prevent the deployment of PBR protocols. In this study, we propose a novel security scheme called ESPR to secure PBR protocols in VANETs. ESPR considers both digital signature and keyed Hash Message Authentication Code (HMAC) to meet the unique requirements of PBR. In ESPR, all legitimate members share a secret key. ESPR scheme applies a novel probabilistic key distribution to allow unrevoked members to update the shared secret key. Furthermore, it defines a set of plausibility checks that enables network members to detect and avoid PBR attacks autonomously. By conducting security analysis and performance evaluation, ESPR scheme demonstrated to outperform its counterparts in terms of communication overhead and delay while achieving robust and secure operation.

Vehicular Ad hoc Network (VANET) is a promising emerging technology that enables road safety, traffic management, and passengers and drivers comfort applications. Many applications require multi-hop routing; position-based routing (PBR) is a well-recognized routing paradigm that performs well in the vehicular context to enable these applications. However, there are many security challenges and various routing attacks which may prevent the deployment of PBR protocols. In this study, we propose a novel security scheme called ESPR to secure PBR protocols in VANETs. ESPR considers both digital signature and keyed Hash Message Authentication Code (HMAC) to meet the unique requirements of PBR. In ESPR, all legitimate members share a secret key. ESPR scheme applies a novel probabilistic key distribution to allow unrevoked members to update the shared secret key. Furthermore, it defines a set of plausibility checks that enables network members to detect and avoid PBR attacks autonomously. By conducting security analysis and performance evaluation, ESPR scheme demonstrated to outperform its counterparts in terms of communication overhead and delay while achieving robust and secure operation.

A mobile ad-hoc network (MANET) is a collection of wireless mobile nodes forming a temporary network without the support of any established infrastructure or centralized administration. There are many potential applications based the techniques of MANETs, such as disaster rescue, personal area networking, wireless conference, military applications, etc. MANETs face a number of challenges for designing a scalable routing protocol due to their natural characteristics. Guaranteeing delivery and the capability to handle dynamic connectivity are the most important issues for routing protocols in MANETs. In this dissertation, we will propose four algorithms that address different aspects of routing problems in MANETs. Firstly, in position based routing protocols to design a scalable location management scheme is inherently difficult. Enhanced Scalable Location management Service (EnSLS) is proposed to improve the scalability of existing location management services, and a mathematical model is proposed to compare the performance of the classical location service, GLS, and our protocol, EnSLS. The analytical model shows that EnSLS has better scalability compared with that of GLS. Secondly, virtual backbone routing can reduce communication overhead and speedup the routing process compared with many existing on-demand routing protocols for routing detection. In many studies, Minimum Connected Dominating Set (MCDS) is used to approximate virtual backbones in a unit-disk graph. However finding a MCDS is an NP-hard problem. In the dissertation, we develop two new pure localized protocols for calculating the CDS. One emphasizes forming a small size initial near-optimal CDS via marking process, and the other uses an iterative synchronized method to avoid illegal simultaneously removal of dominating nodes. Our new protocols largely reduce the number of nodes in CDS compared with existing methods. We show the efficiency of our approach through both theoretical analysis and simulation experiments. Finally, using multiple redundant paths for routing is a promising solution. However, selecting an optimal path set is an NP hard problem. We propose the Genetic Fuzzy Multi-path Routing Protocol (GFMRP), which is a multi-path routing protocol based on fuzzy set theory and evolutionary computing.

Recently, many natural disasters have occurred (e.g., the 2011 tsunami in Japan). In response to those disasters, Wireless Sensor Networks have been proposed to improve their detection level. This new technology has two main challenges which are routing and topology control where their multi-dimensional dilations need to be improved/balanced. Related to those metrics, the packet delivery factor also needs to be improved/guaranteed. This thesis presents the design of new routing protocols, referred to as: 1) the 3-D Sensing Sphere close to the Line:Smallest Angle to the Line (SSL:SAL) protocol, 2) the 3-D Randomized Sensing Spheres (RSS) protocol, and 3) the SSL:SAL version 1 and version 2 (i.e., SSL:SALv1 and SSL:SALv2, respectively). Through simulations, these protocols are shown to balance/improve the multi-dimensional dilations metrics which also include new bandwidth metrics. The balance/improvement is achieved over some existing position-based protocols. In addition, packet delivery is guaranteed mathematically for new and existing protocols. Furthermore, some experimental evidences are gathered regarding the delivery rate impact on the multi-dimensional metrics. The thesis also proposes a new set of 2-D and 3-D graphs, so called: 1) the Derived Circle version 1 (DCv1) graphs and 2) the Derived Sphere (DSv1) graphs. The new approaches improve the multi-dimensional dilations over some existing graphs. In addition, connectivity, rotability, fault tolerance properties are achieved. Lastly, the thesis develops a framework that combines routing protocols and graphs in fully covered regions. Some experimental evidences demonstrate the improvement of the multi-dimensional metrics and the packet delivery rate for the routing protocols based on the DSv1. This is compared to the routing protocols based on an existing graph. Furthermore, based on either the proposed or existing graphs, some important findings are demonstrated for routing in terms of multi-dimensional metrics and packet delivery rate. Among those findings, the proposed protocol and an exiting protocol have higher delivery rates compared to another existing protocol. Furthermore, the proposed graph improves the multi-dimensional metrics for the proposed and existing protocols over another existing protocol for low communication ranges.

Chaque année en Europe, 1.300.000 accidents de la route ont comme conséquence 1.700.000 blessés. Le coût financier d’accidents de la route est évalué à 160 milliards d’euros (approximativement le même coût aux Etats-Unis). VANET (Vehicular Ad-hoc NETwork) est une des technologies clés qui peut permettre de réduire d’une façon significative le nombre d’accidents de la route (e.g. message d’urgence signalant la présence d’un obstacle ou d’un véhicule en cas de brouillard). En plus de l’amélioration de la sécurité et du confort des conducteurs et des passagers, VANET peut contribuer à beaucoup d’applications potentielles telles que la prévision et la détection d’embouteillages, la gestion d’infrastructure de système de transport urbain (e.g. système de transport intelligent multimodal) etc. Dans cette thèse, je présenterai un système embarqué dédié à la communication inter-véhicule particulièrement pour les applications sécuritaires de passagers et de conducteurs. Nos efforts de recherche et de développement sont centrés sur deux principaux objectifs : minimiser le temps de latence intra-noeud et le délai de communication inter-véhicule en prenant en compte le changement dynamique du VANET. De ce fait pour atteindre ces objectifs, des nouvelles approches (e.g. inter-couche ‘Cross-layering’) ont été explorées pour respecter les contraintes de ressource (QoS, mémoire, CPU et énergie de la communication inter-véhicule) d’un système embarqué à faible coût. Le système de communication embarqué proposé comporte deux composants logiciels principaux : un protocole de communication dénommé CIVIC (Communication Inter Véhicule Intelligente et Coopérative) et un système d’exploitation temps réel appelé HEROS (Hybrid Event-driven and Real-time multitasking Operating System). CIVIC est un protocole de communication géographique à faible consommation énergétique et à faible temps de latence (délai de communication). HEROS gère contextuellement l’ensemble du système (matériel et logiciel) en minimisant le temps de latence et la consommation des ressources (CPU et mémoire). En outre, le protocole de communication CIVIC est équipé d’un système de localisation LCD-GPS (Low Cost Differential GPS). Pour tester et valider les différentes techniques et théories, la plateforme matérielle LiveNode (LImos Versatile Embedded wireless sensor NODE) a été utilisée. En effet, la plateforme LiveNode permet de développer et de prototyper rapidement des applications dans différents domaines. Le protocole de communication CIVIC est basé sur la technique de ‘broadcast’ à un saut ; de ce fait il est indépendant de la spécificité du réseau. Pour les expérimentations, seule la norme d’IEEE 802.15.4 (ZigBee) a été choisie comme médium d’accès sans fil. Il est à noter que le médium d’accès sans fil ZigBee a été adopté comme le médium standard pour les réseaux de capteurs sans fil (RCSFs) et le standard 6LoWPAN ; car il est peu coûteux et peu gourmand en énergie. Bien que le protocole de communication à l’origine soit conçu pour répondre aux exigences de VANET, ses domaines d’application ne sont pas limités à VANET. Par exemple il a été utilisé dans différents projets tels que MOBI+ (système de transport urbain intelligent) et NeT-ADDED (projet européen FP6 : agriculture de précision). Les VANETs et les RCSFs sont les réseaux fortement dynamiques, mais les causes de changement topologique de réseau sont différentes : dans le réseau VANET, il est dû à la mobilité des véhicules, et dans le RCSF, il est dû aux pannes des noeuds sans fil. Il est à noter que le VANET et le RCSF sont généralement considérés comme un sous-ensemble du réseau MANET (réseau ad-hoc mobile). Cependant, ils sont réellement tout à fait différents du MANET classique, et leurs similitudes et différences seront expliquées en détail dans la thèse. La contribution principale de mes travaux est le protocole CIVIC, qui échange des messages en basant sur l’information géographique des noeuds (position). (...) / Each year in Europe, 1,300,000 vehicle accidents result in 1,700,000 personal injuries. The financial cost of vehicle accidents is evaluated at 160 billion Euros (approximately the same cost in the USA). VANET (Vehicular Ad-Hoc NETwork) is a key technology that can enable hazard alarming applications to reduce the accident number. In addition to improve the safety for drivers and passengers, VANET can contribute to many potential applications such as detecting and predicting traffic jams, auto-optimizing the traffic flow, and helping disabled passengers to access public transports.This thesis will present an embedded communication system dedicated to VANET especially for the safety-related applications. Our design mainly tries to achieve two requirements: as one can imagine, the embedded communication system for VANET requires extra effort to deal with the highly dynamic network topology caused by moving vehicles, thus to shorten the intra-node system latency and inter-node network delay is essential requirement for such embedded communication system. Besides, a fundamental requirement for any practical embedded system is resource-awareness. Although the embedded communication system on vehicles may gain better hardware supports, the characteristics of embedded hardware still have to cope with resource constraints in terms of QoS, memory, CPU and energy. The embedded communication system involves two major software components: a routing protocol called CIVIC (Communication Inter Véhicule Intelligente et Coopérative) and an embedded operating system called HEROS (Hybrid Event-driven and Real-time multitasking Operating System). The former is a quick reaction and low resource consumption geographic protocol for inter-vehicle message transmissions; and the latter controls the whole system and assures intra-node resource awareness. In addition, the system can use a localization software solution called LCD-GPS (Low Cost Differential GPS) to improve the accuracy of locations. The hardware platform is LiveNode (LImos Versatile Embedded wireless sensor NODE), which is a versatile wireless sensor node enabling to implement rapidly a prototype for different application domains. The communication system is based on the one-hop broadcast, thus it does not have a strict limitation on network specification. For the experiments only, the IEEE 802.15.4 standard is chosen as the underlying wireless access medium. The standard is well known as a low-power consumption standard requiring low-cost devices. Notice that the IEEE 802.15.4 standard is also the wireless access medium of 6LoWPAN. Although the embedded communication system is originally designed to meet the requirements of VANET, but its application domains are not limited to VANET. For example, another network which can use the embedded communication system is WSN (Wireless Sensor Network). CIVIC was used to implement different real-world projects such MOBI+ (intelligent urban transportation system) and EU-FP6 NeT-ADDED (precision agriculture). Both VANET and WSN are highly dynamic networks, but the causes of changing network topology are different: the former is because of the high-mobility feature of vehicles, and the latter is because of the fault of wireless sensors. Note that, although VANET and WSN are both commonly considered as the subset of MANET (Mobile Ad-hoc NETwork), they are actually quite different from the classical MANET, and the similarities and differences will be further explained in the thesis. The major contribution of my works relates to the CIVIC protocol, which routes messages based on the geographic information. The related works of the thesis will focus on the geographic routing techniques, problems and solutions, but other related techniques will also be addressed. Note that, although some related projects were investigated but their implementation and experiment aspects were not detailed. (...)