Publish/subscribe (P/S) is a communication paradigm of growing popularity for information dissemination in large-scale distributed systems. The weak coupling between information producers and consumers in P/S systems is attractive for loosely coupled and dynamic network infrastructures such as ad hoc networks. However, achieving end-to-end timeliness and reliability properties when P/S events are causally dependent is an open problem in ad hoc networks. In this thesis, we present, evaluate benefits of, and compare with past work, an architecture design that can effectively support timely and reliable delivery of events and causally related events in ad hoc environments, and especially in mobile ad hoc networks (MANETs). With observations from both realistic application model and simulation experiments, we reveal causal dependencies among events and their significance in a typical use notional system. We also examine and propose engineering methodologies to further tailor an event-based system to facilitate its self-reorganizing capability and self-reconfiguration. Our design features a two-layer structure, including novel distributed algorithms and mechanisms for P/S tree construction and maintenance. The trace-based experimental simulation studies illustrate our design's effectiveness in both cases with and without causal dependencies. / Master of Science

Thesis (PhD)-- Stellenbosch University, 2013. / ENGLISH ABSTRACT: The hidden terminal problem, coupled with high node mobility apparent in vehicular networks, present challenges to e cient communication between vehicles at the Medium Access Control (MAC) layer. Both of these challenges are fundamentally problems of lack of awareness, and manifest most prominently in the broadcasting of safety messages in infrastructure-free vehicle-to-vehicle communications. The design of existing contention-free and contention-based MAC approaches generally assumes that nodes that are in range of one another can take steps to coordinate communications at the MAC layer to overcome the hidden terminal problem and node mobility. Unicasting with the existing MAC standard, IEEE 802.11p, implicitly assumes an awareness range of twice the transmission range (a 1-hop awareness range) at most, since handshaking is used. For broadcasting, the assumption implies an awareness range that is at most equal to the transmission range, since only carrier sensing is used. Existing alternative contention-free approaches make the same assumption, with some protocols explicitly using a 1-hop awareness range to avoid packet collisions. This dissertation challenges the convention of assuming that a 1-hop awareness range is su cient for networks with high mobility, such as VANETs. In this dissertation, the impact of awareness range and management of the awareness information on MAC performance is researched. The impact of the number of slots that is required to support the awareness range is also evaluated. Three contention-free MAC protocols are introduced to support the research. The rst is an improved version of an existing MAC method, which is used to demonstrate the e ects on performance of changes to awareness management. The second MAC uses three competing processes to manage awareness information. The second MAC is designed for a con gurable awareness range and con gurable number of slots, and is used to evaluate the e ects of awareness range and number of slots on MAC performance. The third MAC is random access based and is used to evaluate the impact on performance of removing awareness completely. An analytical model is developed to support the simulated results. The simulation results demonstrate that awareness range, awareness information management, and number of slots used are key design parameters that signi cantly impact on MAC performance. The results further show that optimal awareness-related design parameters exist for given scenarios. Finally, the proposed contention-free and random access MAC methods are simulated and performance compared with IEEE 802.11p. All three outperform the contentionbased standard IEEE 802.11p. / AFRIKAANSE OPSOMMING: Die versteekte-nodus-probleem, gekoppel met die hoë vlakke van nodusbeweging teenwoordig in voertuignetwerke, bied uitdagings vir doeltre ende kommunikasie tussen voertuie in die medium-toegangbeheer- (MAC) vlak. Beide van hierdie probleme spruit uit beperkte bewustheid, en manifesteer veral in die uitsaai van veiligheidsboodskappe in infrastruktuurvrye voertuig-na-voertuig-kommunikasie. Die ontwerp van bestaande wedywerende en nie-wedywerende MAC benaderings neem aan dat nodusse wat binne bereik van mekaar is, stappe kan neem om kommunikasie op die MAC-vlak te koördineer, ten einde probleme met versteekte nodusse en mobiliteit te oorkom. Vir punt-tot-puntkommunikasie met IEEE 802.11p, impliseer dié aanname 'n bewustheidstrekking van hoogstens twee keer die radiobereik (1-hop bewustheidstrekking), aangesien bladskud gebruik word. In die geval van uitsaai, impliseer die aanname 'n bewustheidstrekking hoogstens gelyk is aan die radiobereik, aangesien slegs draeropsporing gebruik word. Nie-wedywerende metodes maak dieselfde aanname, met sommiges wat eksplisiet 1-hop-bewustheidstrekking gebruik om pakkieverliese te voorkom. Hierdie verhandeling wys dat hierdie aanname nie geld vir netwerke met hoë mobiliteit nie, soos wat die geval is vir VANET. In hierdie verhandeling word die impak van bewustheidstrekking en bestuur van die bewustheidsinligting in die MAC-vlak ondersoek. Die impak van die aantal tydgleuwe wat nodig is om die bewustheidstrekking te ondersteun word ook ondersoek. Drie nie-wedywerende metodes word bekendgestel om die navorsing te ondersteun. Die eerste is 'n verbeterde weergawe van 'n bestaande MAC, wat gebruik word om die e ekte van bewustheidsbestuur op MAC-werkverrigting te beoordeel. Die tweede MAC is ontwerp om veranderbare bewustheidstrekking en hoeveelheid tydgleuwe te ondersteun, en word gebruik om die e ekte van bewustheidstrekking en hoeveelheid tydgleuwe op MAC werkverrigting aan te beoordeel. Die derde MAC is ewetoeganklik (onbewus van omliggende nodusse) en word gebruik om die impak van die verwydering van bewustheid op werkverrigting te ondersoek. 'n Analitiese model is ontwikkel om die simulasieresultate te ondersteun. Die simulasieresultate dui aan dat bewustheidstrekking, bestuur van bewustheidsinligting, en hoeveelheid tydsgleuwe sleutel-ontwerpsveranderlikes is wat 'n beduidende impak het op MAC werkverrigting. Die resultate wys verder dat optimale ontwerpsveranderlikes, in terme van bewustheid, bestaan vir gegewe scenario's. Laastens, word die nie-wedywerende en ewetoeganklike MAC-metodes wat gesimuleer word se werkverrigting vergelyk met IEEE 802.11p. Al drie MAC metodes vaar beter as die wedywerende standaard, IEEE 802.11p.

Intelligent Transportation System (ITS)  is the main research domain for making road transport safer and more comfortable. For the sake of increasing the benefits of ITS, projects about Inter-Vehicle Communication (IVC)  system have been proposed to make communications among vehicles possible, to exchange traffic information and avoid accidents. In order to create communication network among vehicles or between vehicles and infrastructure,  Vehicular Ad hoc Networks (VANETs) has been proposed. Many applications in VANETs need to send messages to vehicles within a specific geographic region. This behavior is called geocast and this specific geographic region is called the Zone of Relevance (ZOR). Some routing protocols which are related to Geocast have been proposed in literature for VANETs. So it is significant to evaluate and compare the performance of these known Geocast routing protocols. In this thesis, categories of the routing protocols, as well as communication forwarding schemes are introduced. The routing protocols in VANETs are also summarized and compared. In order to evaluate the performance of these protocols, the evaluation methods are proposed and then a Geocast routing simulator is designed and used to simulate the Geocast network environment and several Geocast routing protocols.

Timeliness in delivering packets for delay-sensitive applications is an important QoS (Quality of Service) measure in many systems, notably those that need to provide real-time performance. In such systems, if delay-sensitive traffic is delivered to the destination beyond the deadline, then the packets will be rendered useless and dropped after received at the destination. Bandwidth that is already scarce and shared between network nodes is wasted in relaying these expired packets. This thesis proposes that a deterministic per-hop delay can be achieved by using a dynamic queue threshold concept to bound delay of each node. A deterministic per-hop delay is a key component in guaranteeing a deterministic end-to-end delay. The research aims to develop a generic approach that can constrain network delay of delay-sensitive traffic in a dynamic network. Two adaptive queue management schemes, namely, DTH (Dynamic THreshold) and ADTH (Adaptive DTH) are proposed to realize the claim. Both DTH and ADTH use the dynamic threshold concept to constrain queuing delay so that bounded average queuing delay can be achieved for the former and bounded maximum nodal delay can be achieved for the latter. DTH is an analytical approach, which uses queuing theory with superposition of N MMBP-2 (Markov Modulated Bernoulli Process) arrival processes to obtain a mapping relationship between average queuing delay and an appropriate queuing threshold, for queue management. While ADTH is an measurement-based algorithmic approach that can respond to the time-varying link quality and network dynamics in wireless ad hoc networks to constrain network delay. It manages a queue based on system performance measurements and feedback of error measured against a target delay requirement. Numerical analysis and Matlab simulation have been carried out for DTH for the purposes of validation and performance analysis. While ADTH has been evaluated in NS-2 simulation and implemented in a multi-hop wireless ad hoc network testbed for performance analysis. Results show that DTH and ADTH can constrain network delay based on the specified delay requirements, with higher packet loss as a trade-off.

Les réseaux ad hoc dynamiques qui évoluent de manière non planifiée et imprévisible sont souvent étudiés en faisant l’hypothèse d’une composition et d’une topologie qui évoluent peu et relativement lentement. Il est alors possible de proposer dans ce contexte faiblement mobile des mécanismes (comme par exemple du routage, des infrastructures PKI, etc.) qui permettent aux applications conçues pour les réseaux statiques de continuer à fonctionner. Les travaux présentés dans cette thèse sont au contraire centrés sur lesréseaux ad hoc fortement dynamiques (iMANets). Les nœuds qui les constituent sont extrêmement mobiles et volatils, ce qui engendre des modifications incessantes et rapides de topologie. Les contributions principales de cette thèse sont (i) la définition d’une algèbre nommée CiMAN (Calculus for highly Mobile Ad hoc Networks) qui permet de modéliser les processus communicants dans ces réseaux ad hoc fortement mobiles, (ii) l’utilisation de cette algèbre pour prouver la correction d’algorithmes dédiés à ces réseaux, et (iii) unmiddleware et des applications de référence adaptés à ce contexte. / Mobile ad hoc networks that evolve in an unplanned and unpredictable mannerare often studied assuming that their composition and their topology evolve relatively slowly. In this context of weak mobility, it is then possible to propose mechanisms (such asrouting, Public Key Infrastructure, etc.) which make the application designed for a static context still operational. At the opposite, the work presented in this thesis focuses on highlymobile ad hoc networks (iMANets). The nodes of these networks are extremely mobile,bringing ceaseless and fast changes in the network topology. The main contributions of this thesis are (i) the definition of an algebra called CiMAN (Calculus for highly Mobile Adhoc Networks) which makes it possible to model communicating processes in these highly mobile ad hoc networks, (ii) the use of this algebra to prove the correctness of algorithms dedicated to these networks, and (iii) a middleware and reference applications specifically designed for this context.

In this thesis, research is described which leads to the proposal of a link-directionality-based dual channel MAC (Medium Access Control) protocol (DCP) for carrier sense wireless ad hoc networks. It attempts to double the capacities of such networks using an industrial standard (the single-channel IEEE 802.11 protocol) as a benchmark. Simulations show that the proposed scheme can increase the capacities to more than 1.7 times of the single-channel IEEE 802.11 protocol in large-scale random network topologies. The algorithm, however, requires extra radio spectrum resource which could be costly. In addition to DCP, a signal-to-interference ratio comparison algorithm (SCA) is proposed to further release the protocol constraints imposed by the virtual carrier-sensing mechanism. Interestingly, while the capacity of the pure DCP decreases when link lengths are short, the capacity of the pure SCA increases when link lengths are short. The two algorithms compensate for the downside of each other to bring about a more uniform capacity improvement. Simulations show that the integrated scheme can further increase the network throughputs to more than 2.13 times in random topologies. This thesis also clarifies inter-link interference in wireless ad-hoc networks by using link-directional interference graphs (l-graph). By colouring the l-graphs, independent data streams obtained by Multi-Carrier Code Division Multiple Access (MC-CDMA) are assigned for transmitting up-link and down-link traffic separately in order to eliminate the hidden-node and exposed-node problems in wireless local area networks (WLAN). Finally, a generic approach for capacity analysis is proposed to show that the concept of link-directionality can also be adopted with other network models, protocols and parameter settings. However, in certain scenarios where links are densely packed together, the advantage of using link-directionality could be diminished. Therefore, the proposed generic approach for capacity analysis allows one to determine whether channel allocations according to link-directionalities should be applied to a given network.

La rapide progression des technologies sans fil au cours de ces dernières années a vu naître de nouveaux systèmes de communication dont les réseaux véhiculaires. Ces réseaux visent à intégrer les nouvelles technologies de l’information et de la communication dans le domaine automobile en vue d’améliorer la sécurité et le confort sur le réseau routier. Offrir un accès Internet aux véhicules et à leurs occupants peut sans doute aider à anticiper certains dangers sur la route tout en rendant plus agréables les déplacements à bord des véhicules. Le déploiement de ce service nécessite que des messages soient échangés entre les véhicules. Le routage constitue un élément crucial dans un réseau, car définissant la façon dont les différentes entités échangent des messages. Le routage dans les VANETS constitue un grand défi car ces derniers sont caractérisés par une forte mobilité entraînant une topologie très dynamique. Des protocoles ont été proposés pour étendre Internet aux réseaux véhiculaires. Toutefois, la plupart d’entre eux nécessitent un coût élevé de messages de contrôle pour l’établissement et le maintien des communications. Ceci a pour conséquence la saturation de la bande passante entrainant ainsi une baisse de performance du réseau. Nous proposons dans ce mémoire, un protocole de routage qui s’appuie sur des passerelles mobiles pour étendre Internet aux réseaux véhiculaires. Le protocole prend en compte la mobilité des véhicules et la charge du réseau pour l’établissement et le maintien des routes. / The fast progression of wireless technologies has motivated the emergence of new communications system called VANETS (Vehicular Adhoc Networks). VANETS enable vehicles on the roadway to communicate with each other and with road infrastructure using wireless capabilities. The applications of VANETS include improving safety and comfort on the road. For example, by providing Internet to vehicles, traveling can be safer and more comfortable. To provide Internet connectivity, messages need to be exchanged between the vehicles. However, it is hard to design an efficient routing protocol for connecting vehicles to Internet with a reasonable cost due to high mobility in VANETS. Although, several existing routing protocols have been proposed in the open literature to extend Internet to VANETS, they generate considerable overhead. This leads to unfairly consumption of bandwidth decreasing network performance. We design a routing protocol to connect vehicles to Internet through mobile gateways with the objective to make efficient use of the network bandwidth. Indeed, the protocol significantly reduces the communication overhead required to establish and maintain the routes relying on the mobility of the gateways and the network’s load.

Les réseaux sans fil sont sujets à des perturbations voire des pannes de liens et de noeuds en raison des caractéristiques intrinsèques de leur support de communication ; ces pannes sont aggravées par les particularités de relayage et de mobilité des noeuds dans les réseaux ad hoc. Ces réseaux requièrent donc la conception et la mise oeuvre des protocoles robustes au niveau de toutes les couches protocolaires. Dans cette thèse, nous choisissons une approche de robustesse pour améliorer les performances des communications dans un réseau mobile ad hoc. Nous proposons et étudions deux architectures de protection (protection par une analyse prédictive et protection par redondance de routes) qui sont couplées avec une restauration de niveau routage. Concernant la phase de détection, le protocole de routage utilise les notifications de niveau liaison pour détecter les pannes de liens. La première solution repose sur un protocole de routage réactif unipath dont le critère de sélection de routes est modifié. L’idée est d’utiliser des métriques capables de prédire l’état futur des routes dans le but d’améliorer leur durée de vie. Pour cela, deux métriques prédictives reposant sur la mobilité des noeuds sont proposées : la fiabilité des routes et une combinaison fiabilité-minimum de sauts. Pour calculer ces métriques prédictives, nous proposons une méthode analytique de calcul de la fiabilité de liens entre noeuds. Cette méthode prend compte le modèle de mobilité des noeuds et les caractéristiques de la communication sans fil notamment les collisions inter-paquets et les atténuations du signal. Les modèles de mobilité étudiés sont les modèles Random Walk et Random Way Point. Nous montrons l’impact de ces métriques sur les performances en termes de taux de livraison de paquets, de surcoût normalisé et de ruptures de routes. La seconde solution est une protection par redondance de routes qui s’appuie sur un protocole de routage multipath. Dans cette architecture, l’opération de recouvrement consiste soit à un basculement sur une route secondaire soit à une nouvelle découverte. Nous montrons que la redondance de routes améliore la robustesse de la communication en réduisant le temps de restauration. Ensuite, nous proposons une comparaison analytique entre les différentes politiques de recouvrement d’un protocole multipath. Nous en deduisons qu’un recouvrement segmenté donne les meilleurs résultats en termes de temps de restauration et de fiabilité / Due to the unreliability characteristics of wireless communications, and nodes mobility, Mobile Ad hoc Networks (MANETs) suffer from frequent failures and reactivation of links. Consequently, the routes frequently change, causing significant number of routing packets to discover new routes, leading to increased network congestion and transmission latency. Therefore, MANETs demand robust protocol design at all layers of the communication protocol stack, particularly at the MAC, the routing and transport layers. In this thesis, we adopt robustness approach to improve communication performance in MANET. We propose and study two protection architectures (protection by predictive analysis and protection by routes redundancy) which are coupled with a routing level restoration. The routing protocol is responsible of the failure detection phase, and uses the mechanism of link-level notifications to detect link failures. Our first proposition is based on unipath reactive routing protocol with a modified route selection criterion. The idea is to use metrics that can predict the future state of the route in order to improve their lifetime. Two predictive metrics based on the mobility of nodes are proposed : the routes reliability and, combining hop-count and reliability metrics. In order to determine the two predictive metrics, we propose an analytical formulation that computes link reliability between adjacent nodes. This formulation takes into account nodes mobility model and the the wireless communication characteristics including the collisions between packets and signal attenuations. Nodes mobility models studied are Random Walk and Random Way Point. We show the impact of these predictive metrics on the networks performance in terms of packet delivery ratio, normalized routing overhead and number of route failures. The second proposition is based on multipath routing protocol. It is a protection mechanism based on route redundancy. In this architecture, the recovery operation is either to switch the traffic to alternate route or to compute a new route. We show that the routes redundancy technique improves the communication robustness by reducing the failure recovery time. We propose an analytical comparison between different recovery policies of multipath routing protocol. We deduce that segment recovery is the best recovery policy in terms of recovery time and reliability

Cette thèse porte sur l'étude des techniques de fusion de données réparties et incertaines au sein d’un réseau de véhicules pour gérer la confiance dans les autres véhicules ou dans les données reçues. L'algorithme de fusion distribuée proposé est basé sur les fonctions de croyance et est appliqué par chaque nœud à la réception des messages. In se base sur la gestion d'une connaissance directe, locale à chaque nœud et d'une connaissance distribuée diffusée dans le réseau. Cette dernière résulte de la fusion des messages par un opérateur adapté prenant en compte les cycles éventuels et limitant l'effet de "data incest". Chaque nœud peut être autonome pour estimer la confiance mais la coopération entre les véhicules permet d'améliorer et de rendre plus robuste cette estimation. L'algorithme peut être adapté au cas d'étude en considérant un ou plusieurs éléments d'observation et en prenant en compte l'obsolescence des données. Lorsqu'il y a plusieurs éléments d'observation, se pose le problème de l'association de données nécessaire avant l'étape de combinaison. Un nouvel algorithme d'association a été formalisé dans le cadre des fonctions de croyance. Il a été démontré que ce problème est équivalent à un problème d'affectation linéaire, qui peut être résolu en temps polynomial. Cette solution est à la fois optimale et beaucoup plus efficace que d'autres approches développées dans ce formalisme. La gestion de la confiance dans les nœuds et dans les données échangées ont été illustrées par la mise en œuvre de deux applications : la détection de faux nœuds dans une attaque Sybil et la gestion de la confiance dans les cartes dynamiques pour la perception augmentée. / This thesis focuses on the study of fusion techniques for distributed and uncertain data in a vehicle network in order to manage the confidence in other vehicles or in received data. The proposed distributed fusion algorithm is based on belief functions and is applied by each node when it receives messages. It is based on the management of direct knowledge, local for each node, and the management of a distributed knowledge broadcasted over the network. The distributed knowledge is the result of the fusion of messages by a suitable operator taking into account the possible cycles and limiting the effect of "data incest". Each node can be autonomous to estimate confidence but cooperation between vehicles can improve and make more robust this estimation. The algorithm can be adapted to the case of study by considering one or more elements of observation and taking into account the data obsolescence. When there are multiple elements of observation, the data association is necessary before the combination step. A new association algorithm was formalized in the framework of belief functions.It has been shown that this problem is equivalent to a linear assignment problem which can be solved in polynomial time. This solution is both optimal and more effective than other approaches developed in this formalism. The confidence management in the nodes and in the received data were illustrated by the implementation of two applications : the detection of false nodes in a Sybil attack and the distributed dynamic maps for enhanced perception

Nous avons proposé une approche de clusterisation distribuée en vue de son application au problème de la gestion de groupes dynamiques et pour la sécurisation des échanges. Pour parvenir à cet objectif, une combinaison de critères permettant de sélectionner les noeuds les plus appropriés pour assurer les fonctionnalités de clusterheads a été défini, cette dernière s'appuie sur une topologie virtuelle avec le moins de sauts possible, en évitant ainsi de gaspiller les ressources dans les retransmissions dûes aux collisions. Une fois l'étape de mise au point de l'approche de clusterisation effectuée, une application pour résoudre le problème de la gestion de groupes dynamiques et la sécurisation des échanges a été réalisée. Les performances de notre approche de clusterisation ont été évaluées en terme de messages échangés et d'énergie dépensée par les noeuds du réseau. Les résultats de cette évaluation montrent que notre approche est performante. / The proposed clustering approache divides the network into clusters based on affinity relationships between nodes and two types of keys which are generated by a clusterhead. The first one is shared by a clusterhead and its local members and the second one is shared by the clusterhead and its parent cluster. The proposed algorithm is adaptive according to the limitation of the mobile nodes battery power and to the dynamic network topology changes.The performance evaluation and communication overhead analysis of the proposed algorithm are presented using simulation.