Delay-tolerant networks (DTNs) have the potential to connect devices and areas of the world that are under-served by traditional networks. The idea is that an end-to-end connection may never be present. To make communication possible, intermediate nodes take custody of the data being transferred and forward it as the opportunity arises. Both links and nodes may be inherently unreliable and disconnections may be long-lived. A critical challenge for DTNs is determining routes through the network without ever having an end-to-end connection. <br /><br /> This thesis presents a practical routing protocol that uses only observed information about the network. Previous approaches either require complete future knowledge about the connection schedules, or use many copies of each message. Instead, our protocol uses a metric that estimates the average waiting time for each potential next hop. This learned topology information is distributed using a link-state routing protocol, where the link-state packets are flooded using epidemic routing. The routing is recomputed each time connections are established, allowing messages to take advantage of unpredictable contacts. Messages are exchanged if the topology suggests that a connected node is "closer" than the current node. <br /><br /> Simulation results are presented, showing that the protocol provides performance similar to that of schemes that have global knowledge of the network topology, yet without requiring that knowledge. Further, it requires a significantly less resources than the epidemic alternative, suggesting that this approach scales better with the number of messages in the network.

In this dissertation, routing protocols, load-balancing protocols, and efficient evaluation techniques for multi-hop mobile wireless networks are explored. With the advancements made in wireless communication and computer technologies, a new type of mobile wireless network, known as a mobile ad hoc network (MANET), has drawn constant attention. In recent years, several routing protocols for MANETs have been proposed. However, there still remains the need for mechanisms for better scalability support with respect to network size, traffic volume, and mobility. To address this issue, a new method for multi-hop routing in MANETs called Dynamic NIx-Vector Routing (DNVR) is proposed. DNVR has several distinct features compared to other existing on-demand routing protocols, which lead to more stable routes and better scalability. Currently, ad hoc routing protocols lack load-balancing capabilities. Therefore they often fail to provide good service quality, especially in the presence of a large volume of network traffic since the network load concentrates on some nodes, resulting in a highly congested environment. To address this issue, a novel load-balancing technique for ad hoc on-demand routing protocols is proposed. The new method is simple but very effective in achieving load balance and congestion alleviation. In addition, it operates in a completely distributed fashion. To evaluate and verify wireless network protocols effectively, especially to test their scalability properties, scalable and efficient network simulation methods are required. Usually simulation of such large-scale wireless networks needs a long execution time and requires a large amount of computing resources such as powerful CPUs and memory. Traditionally, to cope with this problem, parallel network simulation techniques with parallel computing capabilities have been considered. This dissertation explores a different type of method, which is efficient and can be achieved with a sequential simulation, as well as a parallel and distributed technique for large-scale mobile wireless networks.

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.

Information on the location of mobile nodes in Mobile Ad-hoc Networks (MANETs) has the potential to significantly improve network performance. This thesis uses node location information to develop new techniques for route discovery in on-demand routing protocols such as the Ad-hoc On-Demand Distance Vector (AODV), thus making an important contribution to enhancing the experience of using mobile networks. A Candidate Neighbours to Rebroadcast the Route Request (CNRR) approach has been proposed to reduce the deleterious impact, known as the broadcast storm, of RREQ packets flooding in traditional on-demand routing protocols. The main concept behind CNRR is specifying a set of neighbours which will rebroadcast the received RREQ. This is a departure from the traditional approach of all receiving nodes rebroadcasting RREQs and has the effect of reducing the problem of redundancy from which mobile networks suffer. The proposed protocol has been developed in two phases: Closest-CNRR and Furthest-CNRR. The simulation results show that the proposed algorithms have a significant effect as they reduce the routing overhead of the AODV protocol by up to 28% compared to the C-CNRR, and by up to 17.5% compared to the F-CNRR. Notably, the proposed algorithms simultaneously achieve better throughput and less data dropping. The Link Stability and Energy Aware protocol (LSEA) has been developed to reduce the overhead while increasing network lifetimes. The LSEA helps to control the global dissemination of RREQs in the network by eliminating those nodes that have a residual energy level below a specific threshold value from participation in end-to-end routes. The proposed LSEA protocol significantly increases network lifetimes by up to 19% compared with other on-demand routing protocols while still managing to obtain the same packet delivery ratio and network throughput levels. Furthermore, merging the LSEA and CNRR concepts has the great advantage of reducing the dissemination of RREQs in the network without loss of reachability among the nodes. This increases network lifetimes, reduces the overhead and increases the amount of data sent and received. Accordingly, a Position-based Selective Neighbour (PSN) approach has been proposed which combines the advantages of zoning and link stability. The results show that the proposed technique has notable advantages over both the AODV and MAAODV as it improves delivery ratios by 24.6% and 18.8%, respectively.

Hop count, i.e., the number of wireless hops a packet has to go through to reach the destination, is a fundamental metric in multi-hop wireless ad-hoc networks. Network performance, such as throughput, end-to-end delay, energy consumption, and so on, depends critically on hop count. Previous work on modeling hop count is limited in making unrealistic simplifying assumptions either at the physical or network, or both layers of the communication protocol stack. A key contribution of this thesis is to present an analytical model to derive the probability distribution of hop count under realistic assumptions at both physical and network layers. Specifically, the model considers a log-normal shadowing radio propagation capable of accommodating the random signal fading observed in most wireless communication environments, and the widely used geographic routing at the network layer. Validation of the model is achieved by a comprehensive set of simulation experiments including a trace driven simulation of a real-word vehicular ad-hoc network. The model reveals that the presence of randomness in radio propagation reduces the required number of hops to reach a given destination significantly. To demonstrate the utility of the proposed hop count model, the thesis proposes three new applications which address some of the key challenges in multi-hop wireless networks. The first application derives the per-node packet forwarding load in multi-hop wireless sensor networks and reveals that the nodes in the vicinity of the base station has a significantly less forwarding load than previously thought under simplifying radio propagation and routing assumptions. The second application demonstrates that using hop count as a measure of distance traveled by a data packet, geocasting can be achieved in multi-hop wireless networks in situations when some of the network nodes do not have access to reliable location information. Finally, the proposed hop count model is used to evaluate the performance of the third application which demonstrates that the overhead of geographic routing can be reduced significantly by embracing a position update philosophy which adapts to the mobility and communication patterns of the underlying ad-hoc network.

Hop count, i.e., the number of wireless hops a packet has to go through to reach the destination, is a fundamental metric in multi-hop wireless ad-hoc networks. Network performance, such as throughput, end-to-end delay, energy consumption, and so on, depends critically on hop count. Previous work on modeling hop count is limited in making unrealistic simplifying assumptions either at the physical or network, or both layers of the communication protocol stack. A key contribution of this thesis is to present an analytical model to derive the probability distribution of hop count under realistic assumptions at both physical and network layers. Specifically, the model considers a log-normal shadowing radio propagation capable of accommodating the random signal fading observed in most wireless communication environments, and the widely used geographic routing at the network layer. Validation of the model is achieved by a comprehensive set of simulation experiments including a trace driven simulation of a real-word vehicular ad-hoc network. The model reveals that the presence of randomness in radio propagation reduces the required number of hops to reach a given destination significantly. To demonstrate the utility of the proposed hop count model, the thesis proposes three new applications which address some of the key challenges in multi-hop wireless networks. The first application derives the per-node packet forwarding load in multi-hop wireless sensor networks and reveals that the nodes in the vicinity of the base station has a significantly less forwarding load than previously thought under simplifying radio propagation and routing assumptions. The second application demonstrates that using hop count as a measure of distance traveled by a data packet, geocasting can be achieved in multi-hop wireless networks in situations when some of the network nodes do not have access to reliable location information. Finally, the proposed hop count model is used to evaluate the performance of the third application which demonstrates that the overhead of geographic routing can be reduced significantly by embracing a position update philosophy which adapts to the mobility and communication patterns of the underlying ad-hoc network.

With the emergence of connected and autonomous vehicles, sensors are increasingly deployed within car. Traffic generated by these sensors congest traditional intra-vehicular networks, such as CAN buses. Furthermore, the large amount of wires needed to connect sensors makes it hard to design cars in a modular way. These limitations have created impetus to use wireless technologies to support intra-vehicular communication. In this dissertation, we tackle the challenge of designing and evaluating data collection protocols for intra-car networks that can operate reliably and efficiently under dynamic channel conditions. First, we evaluate the feasibility of deploying an intra-car wireless network based on the Backpressure Collection Protocol (BCP), which is theoretically proven to be throughput-optimal. We uncover a surprising behavior in which, under certain dynamic channel conditions, the average packet delay of BCP decreases with the traffic load. We propose and analyze a queueing-theoretic model to shed light into the observed phenomenon. As a solution, we propose a new protocol, called replication-based LIFO-backpressure (RBL). Analytical and simulation results indicate that RBL dramatically reduces the delay of BCP at low load, while maintaining its high throughput performance. Next, we propose and implement a hybrid wired/wireless architecture, in which each node is connected to either a wired interface or a wireless interface or both. We propose a new protocol, called Hybrid-Backpressure Collection Protocol (Hybrid-BCP), for the intra-car hybrid networks. Our testbed implementation, based on CAN and ZigBee transceivers, demonstrates the load balancing and routing functionalities of Hybrid-BCP and its resilience to DoS attacks. We further provide simulation results, obtained based on real intra-car RSSI traces, showing that Hybrid-BCP can achieve the same performance as a tree-based protocol while reducing the radio transmission power by a factor of 10. Finally, we present TeaCP, a prototype Toolkit for the evaluation and analysis of Collection Protocols in both simulation and experimental environments. TeaCP evaluates a wide range of standard performance metrics, such as reliability, throughput, and latency. TeaCP further allows visualization of routes and network topology evolution. Through simulation of an intra-car WSN and real lab experiments, we demonstrate the functionality of TeaCP for comparing different collection protocols.

Magister Scientiae - MSc / This thesis demonstrates that a situation-aware algorithm improves quality of service on small mesh networks running BATMAN-adv with some mobile nodes. BATMAN-adv is a proactive mesh routing protocol that counts beacons as a link quality metric. BATMAN-adv was modi ed to give more recently received beacons more weight, thereby calculating a more precise indication of the current state of a link that BATMAN-adv can use to forward packets. BATMAN-adv `original' was compared with a situation-aware version in two laboratory test beds with the same voice traffic profile on actual hardware with a realistic voice traffic profile; with controlled transmission rates and buffer sizes to simulate congestion. The second test bed included mesh potatoes, PCs and laptops as mobile nodes. BATMAN-adv achieved better jitter and packet loss than the situation-aware version in the initial, smaller test bed, and average throughput for both versions was almost identical. However, in the second slightly larger test bed, with additional mobile nodes, the situation-aware algorithm performed better than the original BATMAN-adv algorithm for all quality of service metrics, including throughput. Thus the thesis concludes that a situation-aware protocol offers a promising solution to address issues pertaining to mobility, congestion and scalability for voice traffic in mesh networks with mobile nodes. / South Africa

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / Os avanÃos alcanÃados na computaÃÃo mÃvel e na comunicaÃÃo sem o levaram ao desenvolvimento do Sistema Inteligente de Transporte, onde se pode destacar as redes veiculares. Nelas, o roteamento à uma tarefa desaadora devido à alta mobi- lidade dos nÃs, à instabilidade dos enlaces sem-o e a diversidade de cenÃrios. Por essa razÃo, diversos protocolos de roteamento foram projetados com o objetivo de solucionar um ou mais problemas especÃcos de cada cenÃrio. Entretanto, apesar de existirem vÃrias soluÃÃes propostas para o problema do roteamento em redes veicu- lares, nenhuma delas alcanÃou um desempenho satisfatÃrio em mais de um cenÃrio, como urbano e rodovia. Sendo assim, nesta dissertaÃÃo, analisamos atravÃs de si- mulaÃÃes o impacto da densidade, da carga da rede e da mobilidade no desempenho de um protocolo de roteamento para fornecer diretrizes para os projetistas de redes veiculares desenvolverem protocolos de roteamento ecientes, capazes de se adaptar aos cenÃrios urbano e de rodovia. Para alcanÃar esse objetivo, quatro protocolos existentes na literatura foram avaliados nos cenÃrios urbano e de rodovia, dois deles voltados diretamente para redes veiculares e os outro dois tradicionais de redes âd hoâ. / Advances in mobile computing and wireless communications have made possible the development of the Intelligent Transportation System, which contain the vehi- cular networks. There, routing is a challenging task due to the high node mobility, the instability of wireless links and the diversity of scenarios. For this reason, several routing protocols have been designed with the goal of solving one or more specic problems of each scenario. However, although there are several proposed solutions to the routing problem in vehicular networks, none of them has achieved a satisfac- tory performance in more than one scenario, such as urban and highway. Thus, in this work, we rst analyze with simulations the impact of density, the network load and the mobility pattern in the performance of routing protocols for these networks. Then, we provide new directions for designing ecient vehicular network routing protocols, able to adapt to urban and highway scenarios. To achieve this goal, four existing protocols were evaluated in urban and highway scenarios.

Dans les réseaux sans fil ad hoc, les liens de communication sont sujets à un taux d'erreurimportant. Dans ce contexte, le routage joue un rôle stratégique pour augmenter les performancesdans les transmissions. Dans nos études, par une approche cross-layer, nous prenons en compte lafiabilité des liens dans le choix des routes. Pour cela, dans un premier temps, nous construisonsdeux nouvelles métriques, l'une basée sur le taux d'erreur binaire (au niveau couche physique) etl'autre, plus adaptée à la mesure, sur le nombre de retransmissions (au niveau couche MAC).Ensuite, pour exploiter ces métriques lors du calcul de routes, nous adaptons les algorithmes à labase des protocoles de routage.Les trois familles de protocoles de routage ont été traitées : les protocoles pro-actifs où chaquenoeud a une vision globale du réseau grâce aux échanges périodiques de messages de contrôle detopologie ; les protocoles réactifs où, avant de commencer ses transmissions de données, chaquenoeud doit initier un processus de recherche de route ; les protocoles hybrides qui mixent les deuxapproches.Pour tester l'effectivité de nos améliorations, nous utilisons le simulateur NS2 enrichi par unmodèle de propagation et un modèle de mobilité réalistes. Les paramètres de performance tels quele délai, le taux de livraison de paquets et la charge de routage sont mesurés dans plusieursscénarios représentatifs des conditions d'utilisation. Les résultats obtenus montrent une améliorationsignificative des protocoles standards dans un contexte de qualité de service. / In ad hoc wireless networks, links are error-prone. In this context, routing plays a decisive role inimproving transmission performances. In our studies, by a cross-layer approach, we take intoaccount the reliability of links in route choice. For this, first, we concept two new metrics, onebased on bit error rate (at physical layer) and the other, more suitable for the measurement, onnumber of retransmissions (at MAC layer). Then, to exploit these metrics when determining routes,we adapt the algorithms based routing protocols.The three families of routing protocols have been addressed: proactive protocols where eachnode has a global view of the network through periodic exchanges of topology control messages;reactive protocols where, before starting data transmission, each node must initiate a routediscovery process; hybrid protocols which mix the two approaches.To test the effectiveness of our enhancements, we use the simulator NS.2 enhanced by arealistic propagation model and a realistic mobility model. Performance parameters such as delay,packets delivery ratio and routing load are measured in several scenarios including mobility andmulti-communication. The results show a significant improvement of standard protocols in thequality of service context.