The recent proliferation of personal wireless devices has led to the emergence of disruption-tolerant networks (DTNs), which are characterized by intermittent connectivity among some or all participating nodes and a consequent lack of contemporaneous end-to-end paths between the source and consumer of information. However, the success of DTNs as a communication paradigm is critically dependent on the following challenges being addressed: (1) How to enable popular but demanding applications, such as video-on-demand, to operate in such constrained network settings, and (2) How to incentivize individual devices to cooperate when network operation is only possible under, or greatly benefits from cooperation. In this dissertation, we present a novel set of protocols and develop real systems that effectively meet the above challenges. We make the following contributions: First, we design and implement a novel system for enabling high bandwidth content distribution in vehicular DTNs by leveraging infrastructure access points (APs). We predict which APs will soon be visited by a vehicular node and then proactively push content-of-interest to those APs. Our replication schemes optimize content delivery by exploiting Internet connectivity, local wireless connectivity, node relay connectivity and mesh connectivity among APs. We demonstrate the effectiveness of our system through trace-driven simulation and Emulab emulation using real taxi and bus traces. We further deploy our system in two vehicular networks: a fourteen AP 802.11b network and a four AP 802.11n network with smartphones and laptops as clients. Second, we propose an incentive-aware routing protocol for DTNs. In DTNs, routing takes place in a store-and-forward fashion with the help of relay nodes. If the nodes in a DTN are controlled by rational entities, such as people or organizations, the nodes can be expected to behave selfishly by attempting to maximize their utilities and conserve their resources. Since routing is inherently a cooperative activity, system operation will be critically impaired unless cooperation is incentivized. We propose the use of pair-wise tit-for-tat (TFT) as a simple, robust and practical incentive mechanism for DTNs. We then develop an incentive-aware routing protocol that allows selfish nodes to maximize their own performance while conforming to TFT constraints. / text

No description available.

The networking paradigm uses new information vectors consisting of human carried devices is known as disruption-tolerant networks (DTN) or opportunistic networks. We identify the binary assertion issue in DTN. We notice how most DTNs mainly analyze nodes that are in contact. So all nodes that are not in contact are in intercontact. Nevertheless, when two nodes are not in contact, this does not mean that they are topologically far away from one another. We propose a formal definition of vicinities in DTNs and study the new resulting contact/intercontact temporal characterization. Then, we examine the internal organization of vicinities using the Vicinity Motion framework. We highlight movement types such as birth, death, and sequential moves. We analyze a number of their characteristics and extract vicinity usage directions for mobile networks. Based on the vicinity motion outputs and extracted directions, we build the TiGeR that simulates how pairs of nodes interact within their vicinities. Finally, we inquire about the possibilities of vicinity movement prediction in opportunistic networks. We expose a Vicinity Motion-based heuristic for pairwise shortest distance forecasting. We use two Vicinity Motion variants called AVM and SVM to collect vicinity information. We find that both heuristics perform quite well with performances up to 99% for SVM and around 40% for AVM.

Edge networks such as sensor, mobile, and disruption tolerant networks suffer from topological uncertainty and disconnections due to myriad of factors including limited battery capacity on client devices and mobility. Hence, providing reliable, always-on consistency for network applications in such mobile and sensor systems is non-trivial and challenging. However, the problem is of paramount importance given the proliferation of mobile phones, PDAs, laptops, and music players. This thesis identifies two fundamental deterrents to addressing the above problem. First, limited energy on client mobile and sensor devices makes high levels of consistency and availability impossible. Second, unreliable support from the network infrastructure, such as coverage holes in WiFi degrades network performance. We address these two issues in this dissertation through client and infrastructure end modifications. The first part of this thesis proposes a novel energy management architecture called Hierarchical Power Management (HPM). HPM combines platforms with diverse energy needs and capabilities into a single integrated system to provide high levels of consistency and availability at minimal energy consumption. We present two systems Triage and Turducken which are instantiations of HPM for sensor net microservers and laptops respectively. The second part of the thesis proposes and analyzes the use of additional infrastructure in the form of relays, mesh nodes, and base stations to enhance sparse and dense mobile networks. We present the design, implementation, and deployment of Throwboxes a relay system to enhance sparse mobile networks and an associated system for enhancing WiFi based mobile networks.

Master of Science / Department of Electrical and Computer Engineering / Caterina M. Scoglio / Disruption Tolerant Networks or opportunistic networks represent a class of networks where there is no contemporaneous path from source to destination. In other words, these are networks with intermittent connections. These networks are generally sparse or highly mobile wireless networks. Each node has a limited radio range and the connections between nodes may be disrupted due to node movement, hostile environments or power sleep schedules, etc. A common example of such networks is a sensor network monitoring nature or military field or a herd of animals under study. Epidemic routing is a widely proposed routing mechanism for data propagation in these type of networks. According to this mechanism, the source copies its packets to all the nodes it meets in its radio range. These nodes in turn copy the received packets to the other nodes they meet and so on. The data to be transmitted travels in a way analogous to the spread of an infection in a biological network. The destination finally receives the packet and measures are taken to eradicate the packet from the network. The task of routing in epidemic networks faces certain difficulties involving minimizing the delivery delay with a reduced consumption of resources. Every node has severe power constraints and the network is also susceptible to temporary but random failure of nodes. In the previous work, the parameter of mobility has been considered a constant for a certain setting. In our setting, we consider a varying parameter of mobility. In this framework, we determine the optimal mobility pattern and a forwarding policy that a network should follow in order to meet the trade-off between delivery delay and power consumption. In addition, the mobility pattern should be such that it can be practically incorporated. In our work, we formulate an optimization problem which is solved by using the principles of dynamic programming. We have tested the optimal algorithm through extensive simulations and they show that this optimization problem has a global solution.

Routing in Disruption-Tolerant Networks has been researched for over 15 years. Several proposed algorithms exploit the predictive behavior of mobile devices in order to maximize a desired metric (e.g., delivery probability) and minimize waste of resources. However, even devices that follow a highly predictive mobility model might have its behavior temporarily altered due to external events such as accidents, natural conditions, mechanical failures, etc. Some routing approaches for predictive networks are not able to make use of the available knowledge to support the routing decision. Others are not able to adapt under context change. In this work, we present the initial phase of our research and the necessary steps towards an adaptive DTN protocol for challenging networks that is able to exploit available knowledge and adapt under context changes.:I. Introduction II. Challenging Networks III. Challenges Towards an Adaptive Framework IV. Framework Design and Implementation V. Conclusion

Les réseaux opportunistes (DTN) permettent d'utiliser de nouveaux vecteurs de transmissions. Avant de pouvoir profiter de toutes les capacités des DTN, nous devons nous pencher sur la compréhension de ce nouveau paradigme. De nombreuses propriétés des réseaux DTN sont maintenant reconnues, cependant les relations entre un noeud du réseau et son voisinage proche ne semblent pas encore avoir été passée au crible. Souvent, la présence de noeuds voisins proches mais pas directement lié par le contact est ignorée. Dans cette thèse, nous montrons à quel point considérer les noeuds à proximité nous aide à améliorer les performances DTNs.En identifiant le paradoxe binaire dans les DTN, nous montrons que les caractérisations actuelles ne sont pas suffisantes pour bénéficier de toutes les possibilités de transmission dans les DTN. Nous proposons une définition formelle du voisinage pour les DTNs avec le ``k-vicinity''. Nous étudions les caractérisations temporelles du k-vicinity avec différentes données. Ensuite, nous nous concentrons sur l'étude de l'organisation interne du k-vicinity. Nous avons crée le Vicinity Motion qui permet d'obtenir un modèle markovien à partir de n'importe quelle trace de contact. Nous en extrayions trois mouvements principaux: la naissance, la mort et les mouvements séquentiels. Grâce aux valeurs du Vicinity Motion, nous avons pu créer un générateur synthétique de mouvements de proximité nommé TiGeR. Enfin, nous posons la question de la prévisibilité des distances entre deux noeuds du k-vicinity. En utilisant le savoir emmagasiné dans le Vicinity Motion, nous mettons au point une heuristique permettant de prédire les futures distances entre deux noeuds. / The networking paradigm uses new information vectors consisting of human carried devices is known as disruption-tolerant networks (DTN) or opportunistic networks. We identify the binary assertion issue in DTN. We notice how most DTNs mainly analyze nodes that are in contact. So all nodes that are not in contact are in intercontact. Nevertheless, when two nodes are not in contact, this does not mean that they are topologically far away from one another. We propose a formal definition of vicinities in DTNs and study the new resulting contact/intercontact temporal characterization. Then, we examine the internal organization of vicinities using the Vicinity Motion framework. We highlight movement types such as birth, death, and sequential moves. We analyze a number of their characteristics and extract vicinity usage directions for mobile networks. Based on the vicinity motion outputs and extracted directions, we build the TiGeR that simulates how pairs of nodes interact within their vicinities. Finally, we inquire about the possibilities of vicinity movement prediction in opportunistic networks. We expose a Vicinity Motion-based heuristic for pairwise shortest distance forecasting. We use two Vicinity Motion variants called AVM and SVM to collect vicinity information. We find that both heuristics perform quite well with performances up to 99% for SVM and around 40% for AVM.

Disruption Tolerant Networking (DTN) is a network architecture that enables communication between devices in challenging environments that may never have a contemporaneous end-to-end path. Routing in DTN is challenging since every node decides autonomously, based on local information, which bundles should be forwarded when two devices have a contact opportunity (i.e., when they meet). Frequently, devices exchange locally and transitively collected information (properties) during contact opportunities to support their routing algorithms. In the context of Public Transport Networks (PTN), devices may be vehicles (e.g., tram, bus) or stations that use vehicular mobility as a data carrier. Vehicles in a PTN tend to move back and forth, creating repetitive patterns. We assumed that routing algorithms capable of exploring those characteristics would likely maximize the desired metric, e.g., increasing delivery probability (DP) or minimizing latency. In the event of unexpected mobility changes, routing algorithms that perform well under normal mobility may perform poorly during this period. In this case, property exchange can provide context awareness, supporting a device in choosing the right moment to adapt the routing algorithm or tuning it at runtime. However, mobility adaptation and adaptive parametrization were not investigated in the context of DTN for PTN. This thesis proposes an adaptive routing module that supports multiple routing algorithms chosen independently, per bundle, at runtime. Our literature research revealed that many adaptive algorithms had been proposed. Still, only a few provided routing adaptation, and those approaches have not been addressed in the context of PTNs. From an extensive review of property exchange in DTN, we classified properties that algorithms exchanged at runtime. Finally, we provided an overview of the current DTN frameworks, showing that at least one allows the choice of the routing algorithm independently; however, the high coupling between routing and information exchange precludes the usage of multiple routing algorithms concurrently in practice. Therefore, our novel approach decouples property exchange from the routing algorithm, i.e., exchanging a set of properties consistently during contact opportunities independently of the routing algorithm used. From the different classes identified in the literature research, resource class is the most suitable for PTN as exchanging its properties enables reproducing the most common routing algorithms and providing context-awareness. The history of contacts is stored together with information about devices resources' state during each contact opportunity and spread transitively in the network. Since this information is immutable, it incrementally allows every device to improve its understanding of network behavior over time. Another improvement in our approach is exchanging raw information as an ordered list of the instantaneous information about the device state, allowing every device to derive the needed information to the routing support locally.Commonly, devices exchange summarized information (e.g., frequency of contacts, centrality, delivery predictability): an interesting approach for single routing, as it allows the exchange of the minimal amount of information; however, it is less attractive for a multi routing approach due to the high coupling between routing and property exchange. Creating an adaptative mechanism for a routing algorithm at runtime claims a careful choice considering multiple aspects of the development cycle: modeling, dynamic adaptation, and system extension. Runtime adaptability and extensibility support have been integrated into some programming languages. In some cases, it is also possible to provide those capabilities through development techniques and design patterns. However, at the modeling level, conceptual modeling languages, as the Entity-Relationship Model (ER) or the Unified Modeling Language (UML) cannot express the dynamics that arise from the context changes and behavioral interaction at runtime (e.g., the influence of congestion control techniques in the outcome of the routing algorithm according to a set of goals or intent of the network). Therefore, we used Role-based modeling languages to express the behavioral and relational nature of the proposed system. In a PTN, the router (vehicle or station) plays the role \textit{route} (executes an objective function) depending on the sensed context. The \textit{route} role can be further influenced by roles that encapsulate routing strategies, as congestion control (limiting the number of replication) or fairness. Routing algorithms are grouped in compartments and selected based on rules that determine what routing algorithm should be selected for a given context and how to tune the routing algorithm. A proof of concept was developed using SCROLL and integrated into the ONE simulator, allowing adaptive simulations. On the one hand, this solution is flexible, allowing algorithms to be designed independently. On the other hand, the integration between Java and SCALA reduced the system's flexibility due to the impossibility of using implicit types and the simulation time increased considerably. The potential performance improvement caused by routing adaptation depends on several variables, e.g., the scenario, the vehicular mobility, and the routing algorithms. Based on the evaluation of common routing algorithms proposed in DTN that can be reproduced by exchanging information about resources, we show that algorithms should be compared under average load. On the one hand, if the network load is low, all routing algorithms perform similarly, since all bundles are delivered; On the other hand, the network is congested regardless of the routing algorithm if the load is too high. Our experiments also indicate that routing algorithms able to explore the runtime behavior of the network are likely to achieve higher DP for an average load and highlighted the importance of proper tuning of each routing algorithm for the target scenario. The adaptive simulations showed that adapting the routing algorithm at runtime could increase the desired metric. Our simulations considered 24 hours of the tram PTN of Freiburg, in which we changed the mobility for a specific period of the day. In both experiments, we compare a historically based non-adaptive algorithm (PRoPHET) with an adaptive algorithm that modifies the behavior (PRoPHET and Epidemic) according to the context. In the first scenario, we simulate the effect of a disaster in which vehicular mobility is replaced by first aid vehicles. The adaptive variant resulted in a DP increase of up to 9.85\% at the end of the adaptation period. In the second scenario, we simulated mobility adaptation due to an accident that split two tramlines. Also, in this use case, the adaptation at runtime allowed the DP to increase up to 11.12\%. In both cases, the ability to perceive the context modification and adapt accordingly is essential. We evaluated the overhead of information exchange based on a concrete example for PTN and found that, for the chosen scenarios and multiple communication technologies, the network overhead caused by information exchange at runtime would be less than 1.2\%. The main contributions of this thesis are summarized as follows: we developed tools to support the creation and simulation of DTN in PTN scenarios; provided a classification of properties exchanged in the DTN literature to provide context awareness and support routing algorithms; pointed out a design decision in current frameworks (coupling between routing and property exchange) that precludes the adoption of current routing algorithms at runtime; reinforced, based on extensive simulations, the importance of tuning each routing algorithm to the target use-case; proposed a method to exchange and store properties that could enable nodes to collect historical data according to its resources (computing and storage space); demonstrated, for a specific property group how to break information into basic units and how to derive complex metrics for multiple purposes; last but not least, we demonstrated that, in scheduled networks, such as PTN, adaptive algorithms can increase the desired metric by adapting the routing algorithm at runtime. As future work remains the following question: how to effectively provide context awareness through the exchange of properties at runtime?

Made available in DSpace on 2016-06-02T19:06:08Z (GMT). No. of bitstreams: 1 5463.pdf: 18006027 bytes, checksum: 047b84b38eb03b475dacbf51b7bf50b1 (MD5) Previous issue date: 2013-07-31 / Financiadora de Estudos e Projetos / Vehicular ad-hoc networks (VANETs) are networks capable of establishing communications between vehicles and road-side units. VANETs could be employed in data transmission applications. However, due to vehicle mobility, VANETs present intermittent connectivity, making message transmission a challenging task. Due to the lack of an end-to-end connectivity, messages are forwarded from vehicle to vehicle and stored when it is not possible to retransmit. Additionally, in order to improve delivery probability, messages are replicated and disseminated over the network. However, message replication may cause high network overhead and resource usage. As result, considerable research e_ort has been devoted to develop algorithms for speci_c scenarios: low, moderate and high connectivity. Nevertheless, algorithms projected for scenarios with a speci_c connectivity lack the ability to adapt to situations with zones presenting diferent node density. This lack of adaptation may negatively a_ect the performance in application such as data transmission in cities. This masters project proposes develops a method to automatically adapt message replication routing algorithms to diferent node density scenarios. The proposed method is composed of three phases. The first phase collects data from message retransmission events using a standard routing algorithms. The second phase consists in training a decision tree classifier based on the collected data. Finally, in the third phase the trained classifier is used to determine whether a message should be retransmitted or not based on the local node density. Therefore, the proposed method allows routing algorithms to query the trained classifier to decide if a message should be retransmitted. The proposed method was evaluated with real movement traces in order to improve Spray and Wait and Epidemic routing algorithms. Results indicate that the proposed method may contribute to performance enhancement. / As VANETs são redes de veículos com capacidade de estabelecer comunicações sem fio entre veículos e com equipamentos nas estradas. Estas redes poderiam ser usadas para a transferência de dados de diversas aplicações. No entanto, devido á mobilidade dos veículos, as VANETs apresentam conectividade intermitente entre os nós, dificultando a transmissão de mensagens. Ante a impossibilidade de ter conectividade de fim a fim, as mensagens são encaminhadas progressivamente de veículo em veículo, e armazenadas quando não houver a possibilidade de retransmitir. Adicionalmente, para incrementar a probabilidade de entrega, as mensagens são replicadas e disseminadas pela rede. Não obstante, a replicação de mensagens pode gerar alta sobrecarga de rede e alto consumo de recursos. Por causa disto, projetaram-se algoritmos para cenários específicos de: baixa, moderada e alta conectividade. Estes algoritmos, quando aplicados em ambientes de zonas de diferente densidade de nós,como cidades, podem diminuir o seu desempenho pela falta da capacidade de se adaptar a diferentes condições de conectividade. Contudo, neste trabalho foi desenvolvido um método para adaptar o comportamento dos algoritmos de roteamento por replicação de mensagens a diferentes situações de conectividade segundo a densidade das zonas onde se movimentam os nós retransmissores. O método consiste em três fases. Na primeira, são coletados os dados dos eventos de repasse de mensagens utilizando o algoritmo de roteamento padrão. Na segunda fase, utilizam-se os dados coletados para treinar um classificador baseado em _arvores de decisão. Na _ultima fase, o classificador é então empregado para determinar se uma situação de repasse de mensagem _e favorável segundo a densidade de nós. Desta forma, os algoritmos de roteamento podem decidir se repassar ou não uma mensagem com o suporte do classificador. Esta abordagem foi avaliada com traces de movimentos reais, para aprimorar o desempenho dos algoritmos de roteamento Spray and Wait e Epidemic. Os resultados dos experimentos realizados revelam que esta abordagem pode contribuir para o aprimoramento do desempenho.