No description available.

<p>Wireless mesh networks are widely used for various communication purposes and are often deployed in a broad range of outdoor applications. In cases where the deployment area is outside the reach of fixed infrastructure, energy efficient operation of the mesh nodes is very important. Many approaches have been explored to find energy efficient network solutions for these types of scenarios. This thesisproposes power saving mechanisms where the mesh network nodes opportunistically access coexistent vehicular networks. This is referred to as Opportunistic Vehicle Assisted Ferrying (OVAF). The history of using moving particles for message carrying can be found in research on intermittently connected networks. However, this approachhas never been considered with fully connected networks. Two different models are presented to model the OVAFmechanism: \textbf{a}. \emph{A flow based model}, and \textbf{b}. \emph{Apacket based model}. For each model an analytic lower bound isobtained by formulating a linear integer optimization with differentcost functions. Heuristics, which simplify the complexity of theproblem, are then developed for eachmodel. Arriving vehicles and generated packets are also modeled asrandom processes under various scenarios using different parameters.Results are presented which demonstrate the superiority of the OVAFrouting method compared to conventional multihop forwarding (Up to $60\%$increase in energy saving).</p> / Master of Applied Science (MASc)

Cette thèse traite de la dissémination de messages dans les réseaux tolérants aux délais (DTNs). Ce type d'environnements très contraints ouvre de nombreux défis parmi lesquels le routage qui exploite au mieux les critères de mobilité des noeuds, le routage utilisant un nombre réduit de copies du message à disséminer, le routage de messages respectant la vie privée des noeuds, le routage en présence de nœuds égoïstes. Ce sont ces défis que nous adressons dans le cadre de cette thèse. La première contribution de cette thèse consiste en un protocole de routage adaptatif pour les DTNs exploitant au mieux les critères de mobilité des nœuds. En particulier, ce protocole permet de déterminer à chaque fois qu'une décision de routage doit être prise, quel critère de mobilité augmente la probabilité que le message soit délivré à sa destination. Cette décision est prise grâce à une fonction d'utilité calculée par les nœuds après normalisation des valeurs décrivant les différents critères de mobilité. Le protocole est validé par des simulations faites en utilisant des traces de mobilité réelles et en comparaison avec des protocoles de l'état de l'art. Les résultats montrent de meilleures performances en terme de taux de délivrance de messages mais à coût plus élevé. La seconde contribution de cette thèse consiste en un protocole dont le but est d'adapter dynamiquement le nombre de copies de messages disséminés dans le réseau. Le protocole proposé dans cette thèse résout ce problème en pré-calculant un nombre de copies nécessaire pour atteindre une certaine probabilité de délivrance, puis en augmentant dynamiquement ce nombre au fur et à mesure que le délai d'expiration du message approche. Les résultats montrent que le protocole proposé offre un taux de délivrance équivalent aux protocoles les plus performants à un cout bien inférieur. La troisième contribution de cette thèse consiste en un protocole de routage dans les DTNs qui protège la vie privée des nœuds. En particulier, ce protocole protège les informations relatives à la mobilité des nœuds. Ceci est fait en se basant sur l'organisation des nœuds en communautés. En particulier, au lieu de comparer leur propres probabilités de rencontrer la destination d'un message donné, dans le protocole proposé, les nœuds comparent la probabilité qu'un nœud de leur communauté rencontre la destination. Afin de calculer cette probabilité au sein de la communauté de manière à préserver les valeurs individuelle, le protocole se base sur des algorithmes de cryptographie afin de calculer des produits de probabilité de manière à protéger les valeurs individuelles. Les résultats montrent que le protocole exhibe des performances équivalentes aux protocoles existants tout en étant le seul à respecter les informations confidentielles des usagers. / Mobile Delay Tolerant Networks (MDTNs) are wireless mobile networks in which a complete routing path between two nodes that wish to communicate cannot be guaranteed. A number of networking scenarios have been categorized as MDTNs, such as vehicular ad hoc networks, pocket switched networks, etc. The network asynchrony, coupled with the limited resources of mobile devices make message dissemination (also called routing) one of the fundamental challenges in MDTNs. In the literature, a large body of work has been done to deal with routing in MDTNs. However, most of the existing routing protocols are based on at least one of the following three assumptions: (1) all messages can be routed by relying on a single mobility property; (2) all messages can be routed using a single message allocation strategy; (3) users are willing to disclose their mobility information and relationships to others in order to improve the quality of the routing. We argue that the above three assumptions are not realistic because: (1) users can exhibit various social behaviors and consequently various mobility properties (e.g., they can have regular movements during week-days and exhibit non-predictable movements during week-ends); (2) some messages might need more or less copies to be delivered according to the localization of the source and the destination and to the urgency of the message; and (3) users mobility data can disclose sensitive information about the users. In this thesis, we relieve MDTN routing from the above three restrictive assumptions. Firstly, we propose an adaptive routing protocol for mobile delay tolerant networks. The proposed protocol can dynamically learn the social properties of nodes based on their mobility patterns, and exploit the most appropriate routing strategy each time an intermediate node is encountered. Simulations performed on real mobility traces show that our protocol achieves a better delivery ratio than existing state-of-the-art routing protocols that rely on a single mobility property. Secondly, we present a delay and cost balancing protocol for efficient routing in mobile delay tolerant networks. The presented protocol reasons on the remaining time-to-live of a message to dynamically allocate the minimum number of copies that are necessary to achieve a given delivery probability. Evaluation results show that the protocol can achieve a good balance between message delivery delay and delivery cost, compared with most of the existing routing protocols in the literature. Lastly, we propose an efficient privacy preserving prediction-based routing protocol for mobile delay tolerant networks. This protocol preserves the mobility patterns of a node from being disclosed by exploiting the mobility pattern of communities that node belongs to. Evaluation results demonstrate that this protocol can obtain comparable routing performance to prediction-based protocols while preserving the mobility pattern of nodes.

Le transport est devenu fondamental dans les villes pour le bon fonctionnement de l'économie et le bien-être de la population urbaine. Depuis plusieurs années, le transport est confronté à de nombreux problèmes tels que l'embouteillage, le taux élevé d'accidents, la vie malsaine due à la fumée et à la poussière, la pollution atmosphérique due aux émissions de carbone, etc. Pour faire face à ces problèmes, les recherches intègrent les technologies numériques au transport terrestre, connu sous le nom de système de transport intelligent (ITS). Les ITS peuvent détecter, analyser, collecter, contrôler et communiquer différentes données. Cette thèse étudie et propose un nouveau protocole pour les applications de collecte de données dans un environnement urbain. Nous faisons trois contributions principales. Tout d'abord, nous proposons un nouveau protocole dénommé le protocole "Internet of Bikes" IoB-DTN qui applique le paradigme DTN (Réseau tolérant aux délais) aux applications de l'Internet des objets (IoT) exécutant une application de collecte de données sur un système de partage de vélo urbain basé sur un réseau de capteurs. Le protocole est évalué sur un scénario réaliste en évaluant les politiques de gestion des buffers, le nombre de copies pulvérisé dans le réseau ainsi que le nombre des vélos utilisés. Deuxiément, une évaluation comparative des performances du protocole IoB-DTN multi-sauts avec une technologie de réseau étendu à basse consommation (LPWAN), de type LoRa/LoRaWAN est étudiée. LPWAN a été conçu pour fournir une connectivité à grande distance et rentable pour les applications IoT à faible débit: durée de vie de plusieurs années et une portée de multikilomètres pour les appareils mobiles alimentés par des batteries. Cette partie de notre travail vise à fournir aux concepteurs et aux managers de réseaux des idées sur la technologie la plus pertinente pour leurs applications urbaines pouvant fonctionner sur des systèmes de partage de vélos. Enfin, nous proposons un protocole efficace, IoB-DTN basé sur un mécanisme d’agrégation de données. Nous proposons trois variantes de IoB-DTN: IoB basé sur l'agrégation spatiale (IoB-SA), IoB basé sur l'agrégation temporelle (IoB-TA) et IoB basé sur l'agrégation spatio-temporelle (IoB-STA). Nous comparons les trois variantes avec le protocole multi-saut IoB-DTN sans agrégation et la technologie à faible puissance et longue portée, de type LoRa. Les résultats de la comparaison permettent de vérifier que les trois variantes de l’IoB-DTN basées sur l’agrégation de données améliorent plusieurs paramètres tels que le taux de livraison, la consommation d’énergie et le débit. / Transport has become fundamental in the cities to the well functioning of the economy and the welfare of the city population. For several years, transportation faces many issues such as traffic jamming, high accidents rate, unhealthy life due to smoke and dust, air pollution as a result of carbon emission, etc. To deal with these matters, researches integrate digital technologies to ground transportation which is known as Intelligent Transport System (ITS). ITS can sense, analyze, collect, control and communicate different data. This thesis investigates and proposes a new protocol for data collection applications in an urban environment. We make three main contributions: firstly, we propose a new protocol denoted the "Internet of Bikes" IoB-DTN protocol which applies Delay/Disruption Tolerant Network (DTN) paradigm to the Internet of Things (IoT) applications running a data collection application on urban bike sharing system based sensor network. The protocol is evaluated on a realistic scenario by assessing the buffer management policies, the number of copies sprayed in the network as well as the number of bicycles used. Secondly, a comparative evaluation of the performance of the multi-hop IoB-DTN protocol with a low-power wide-area network (LPWAN) technology, LoRa/LoRaWAN type is investigated. LPWAN have been designed to provide cost-effective wide area connectivity for small throughput IoT applications: multiyear lifetime and multikilometer range for battery-operated mobile devices. This part of our work aims at providing network designers and managers insights on the most relevant technology for their urban applications that could run on bike sharing systems. Finally, we propose an efficient IoB-DTN protocol based on data aggregation mechanism. We propose three variants of IoB-DTN: IoB based on spatial aggregation (IoB-SA), IoB based on temporal aggregation (IoB-TA) and IoB based on spatio-temporal aggregation (IoB-STA). We compare the three variants with the multi-hop IoB-DTN protocol without aggregation and the low-power long-range technology, LoRa type. Comparison results verify that the three variants of IoB-DTN based on data aggregation improve several metrics such as the delivery rate, energy consumption and throughput.

O comportamento dinâmico das redes sem fio as torna muito peculiares e de difícil análise. No entanto, algumas destas redes, como as de sensores com funcionamento intermitente, redes periódicas ou cíclicas e as do sistema de satélites de órbita baixa têm um comportamento dinâmico relativamente previsível, pois as variações da topologia da rede no tempo são quase que determinísticas. Recentemente, um modelo teórico -- grafos evolutivos -- foi proposto com o intuito de capturar o comportamento dinâmico destas redes e formalizar algoritmos de roteamento de custo mínimo, além de outros. Os algoritmos e idéias obtidos com este modelo são teoricamente muito eficientes, mas, no entanto, antes deste trabalho não existiam estudos do uso destes modelos em situações práticas. Assim, o objetivo deste trabalho é analisar a aplicabilidade da teoria de grafos evolutivos na construção de protocolos de roteamento eficientes em cenários realistas. Foram implementados dois protocolos de roteamento para redes móveis ad hoc baseados nos algoritmos de grafos evolutivos, são eles: Jornada que Chega Mais Cedo e Jornada Mais Curta. Extensivas simulações foram realizadas utilizando o simulador de redes NS2 e os resultados foram comparados com outros quatro protocolos clássicos para este tipo de rede: AODV, DSR, OLSR e DSDV. Os resultados preliminares mostram que este recente modelo tem muito potencial para ser uma ferramenta poderosa no desenvolvimento e análise de algoritmos para redes dinâmicas com comportamento previsível. No entanto, foram apontados alguns aspectos que precisam ser melhores estudados para que estes algoritmos possam ser utilizados em situações reais. / The assessment of routing protocols for wireless networks is a difficult task, because of the networks\' highly dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and low earth orbit satellites systems, have more predictable dynamics, as the temporal variations in the network topology are somehow deterministic, which may make them easier to study. Recently, a graph theoretic model -- the evolving graphs -- was proposed to help to capture the dynamic behavior of these networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, before this work there was no study on the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. We use the NS2 network simulator to first implement two evolving graph based routing protocols: Foremost Journey and Shortest Journey, They are evaluated and compared to four major ad-hoc protocols: AODV, DSR, OLSR and DSDV. Interestingly, our experiments show that evolving graphs have all the potentials to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model.

在DTN(Delay Tolerant Networks)這類的網路架構下，無線節點之 間的通訊連線是採非連續性建立的。DTN 路由協定中, 決定中繼節點 方式大致可以分成兩類:依地理位置考量的路由協定（Geographic Routing Protocal）和依社交模式考量的路由協定（Social-based Routing Portocal）。 由於人與人間的互動是透過社交關係, 但是真實的資訊傳遞又須 仰賴當時的地理位置。因此我們提出的演算法將網路拓墣分成社交層與地理層, 在社交層中利用Social Ally Selection Algorithm 挑選出合適的社交盟友(Social Ally)。在地理層中利用Geographic Messenger Forwarding Algorithm 挑選合適的節點將訊息傳送給朝向目的地或是社交中繼站的節點。根據實驗模擬結果, 我們的路由協定能有較佳的傳遞成功率, 並降低了延遲時間。 / Delay Tolerant networks (DTN) may lack continuous network connectivity. Most of these DTN routing protocol, which attempt to make better routing decision, could be divided in two categories: Geographic routing protocols and Social-based routing protocols. Due to the interaction between people through social behaviors and message transmissions rely on geographic position information, we proposed a routing protocol which network topology is divided into two sub layers: social layer and geographic layer. In social layer, we propose a Social Ally Selection Algorithm to decide social allies that are controlled to improve delivery performance. In geographic layer, we propose a Geographic Messenger Forwarding Algorithm to transmit message to the nodes moving toward to social ally or destination. According to the simulation results, we could show that our routing protocol have higher delivery ratio and lower delay latency compare to other protocols.

在傳統的DTN路由協定中，由於網路拓樸的快速變動，為了能將訊息封包傳送到目的地，通常是透過大量的複製，或是透過資訊的過濾與計算，將封包交由適合的節點來協助傳送。 然而在電池電源有限的條件之下，過於冗餘的封包複製傳遞，或CPU運算的大量使用，將使得節點容易因電量耗盡而失去傳遞的功能，不只是造成整體系統的存活時間(System Lifetime)降低，亦非常不利於維持整體網路的傳遞成功率(Delivery Ratio)。 在旅行的過程中，同行的人們通常具有相同的移動軌跡以及最終目的地，因而形成團體行動的模式；針對這樣的特性，我們採用每個團隊只留下一位領隊來統籌探索鄰居及封包傳遞的概念，透過GPS的資訊輔助來設計出組隊省電機制，延長節點存活時間，進而提升系統存活時間，並在運算複雜度較低且封包冗餘複製亦降低的狀況下，仍保有不錯的傳遞成功率以及較低的效能衰減。 / In traditional routing protocols of DTNs, most of them are using redundancy messages and information computing to make a good relay decision. Due to energy limitation, too many redundant message transmissions or high computing will make nodes die off quickly. It will decrease the system lifetime and diminish the delivery ratio of the whole system. When people go on a tour, friends always form a group due that members have a similar moving path and destination. Based on the features of moving patterns, we design a grouping scheme, namely, Energy-aware Grouping, with the concept that there is only one node awake in a group in charge of contact and message transmissions. With the assistance by GPS, our method has reduced the numbers of redundant message transmissions and information computing. Simulation results show that it can extend the system lifetime with maintaining still good delivery ratio

Les réseaux cibles des applications distribuées ont connu une évolution significative ces dernières années, faisant apparaître un dynamisme croissant. Une première caractéristique des réseaux dynamiques est la volatilité, qui implique que certaines machines du réseau peuvent être amenées à ne plus participer à l'application, de façon temporaire ou définitive. Une autre caractéristique est apparue avec l'avènement de l'informatique mobile : dans un contexte où les machines sont mobiles et communiquent par radio, la portée limitée des transmissions induit de fréquents changements de topologie du réseau. Nos travaux concernent deux catégories de réseaux dynamiques. Dans un premier temps, nous nous sommes intéressés aux applications relevant du Grid Computing et plus particulièrement aux applications parallèles ciblant des grappes non dédiées, c'est-à-dire à des ensembles de stations de travail hétérogènes banalisées reliées par des réseaux d'interconnexion eux aussi banalisés, offrant donc des performances variables. Dans un deuxième temps, nous avons considéré des réseaux cibles de l'informatique ambiante. Nous avons en particulier étudié les réseaux mobiles ad hoc discontinus, c'est-à-dire des réseaux formés spontanément à partir de machines mobiles communiquant par radio directement entre elles, sans passer par une infrastructure fixe, et dont la topologie est telle qu'ils ne se présentent pas sous la forme d'une seule composante connexe mais plutôt d'un ensemble d'îlots de communication distincts. Pour faciliter le développement et l'exploitation des applications distribuées sur réseaux dynamiques, il apparaît utile de s'appuyer sur des paradigmes de programmation de haut niveau tel que ceux mis en avant dans l'approche orientée composants et l'approche orientée services. Ces approches permettent notamment un découplage entre les entités de l'application, facilitant la gestion de la complexité du développement et du déploiement des applications dans un environnement dynamique. La plupart des technologies de composants et de services ont été conçues pour des réseaux stables et ne conviennent généralement pas aux applications sur réseaux dynamiques. Les travaux que nous avons menés ont eu pour objectif de faciliter l'exploitation des composants et services dans un contexte dynamique. Nous nous sommes surtout focalisés sur le support à l'exécution des applications bâties à partir de composants et services, ce support prenant la forme d'un intergiciel, c'est-à-dire d'un ensemble de services logiciels construits au-dessus des systèmes d'exploitation et des protocoles de communication, et invoqués par les composants de l'application. Nos contributions sont présentées à travers trois projets principaux : le projet Concerto, portant sur la définition d'un modèle de composants parallèles associé à un intergiciel pour des applications devant être déployées sur des grappes de stations de travail banalisées ; le projet Cubik, étendant le modèle de composants Fractal et proposant un support pour le déploiement et l'exécution de composants ubiquitaires pour réseaux dynamiques ; et le projet Sarah, s'attachant à la construction d'une plate-forme à services bâtie au dessus d'un protocole de communication adapté aux réseaux mobiles ad hoc discontinus.

在耐延遲網路環境下節點的相遇情況不是很頻繁，這可能導致節點間的連線斷斷續續，使得有效地將訊息傳遞成為一件困難的事情。藉由社群感知轉送機制的中間度指標特性，可以來提升傳送成功率。雖然大多數研究幾乎都是將訊息轉送到單一目的地或是多個且已知的目的地。然而，一些應用像是廣告的散佈，要將訊息送給對訊息有興趣的人，但卻不知道是誰。因此，關鍵的問題為如何建立社群網路關係的親密度機制，來選擇作為轉送訊息的節點，並利用群體廣播的方式盡可能有效地傳播至最多可能目標目的地，進而提升效能。 本論文以群播機制和社群感知當作基礎概念，來設計新的轉送訊息的方法和公式化選擇中繼節點的機制。最後，我們使用政治大學實際軌跡來模擬，將模擬結果與其它路由演算法比較，其結果證明我們所提出的方法能提高訊息傳送成功率和正確率，降低傳送延遲時間和傳送訊息的成本。 / In delay tolerant networks (DTNs), nodes infrequently encounter with each others. This results in intermittent connectivity of the nodes, and makes it difficult to deliver the message effectively. A social-aware forwarding scheme can help for successful delivery ratio by utilizing the characteristic of their centrality metric. Most of the previous studies focus on message delivery to single destination or some priori known destinations. However, some applications like advertisement dissemination may not know who will be the interested persons to be delivered. Therefore, the key challenge is how to establish the social relationship strategy to select appropriate nodes as relays, and furthermore to use multicasting to disseminate effectively as many “target” destinations as possible to improve the performance. This thesis developed a new strategy which has a new forwarding message scheme and formulates the selection of the relay nodes based on the concept of the multicasting and the social network. Finally, we used the reality trace data of National Chengchi University to simulate. The simulation results are compared to others DTNs routing protocols as well as other social-aware forwarding schemes. The results showed that our proposed approach can enhance the successful delivery ratio and delivery accuracy, decrease the delivery delay and reduce the delivery overhead.

Current research on securing public computing infrastructure like Internet kiosks has focused on the use of smartphones to establish trust in a computing platform or to offload the processing of sensitive information, and the use of new cryptosystems such as Hierarchical Identity-based Encryption (HIBE) to protect kiosk user data. Challenges posed by rural kiosks, specifically (a) the absence of specialized hardware features such as Trusted Platform Modules (TPMs) or a modifiable BIOS in older recycled PCs, (b) the potential use of periodically disconnected links between kiosks and the Internet, (c) the absence of a production-ready implementation of HIBE and (d) the limited availability of smartphones in most developing regions make these approaches difficult, if not impossible, to implement in a rural public computing scenario. In this thesis, I present a practical, unobtrusive and easy-to-use security architecture for rural public computing that uses a combination of physical and cryptographic mechanisms to protect user data, public computing infrastructure and handheld devices that access this infrastructure. Key contributions of this work include (a) a detailed threat analysis of such systems with a particular focus on rural Internet kiosks and handheld devices, (b) a security architecture for rural public computing infrastructure that does not require any specialized hardware, (c) an application-independent and backward-compatible security API for securely sending and receiving data between these systems and the Internet that can operate over delay tolerant links, (d) an implementation of my scheme for rural Internet kiosks and (e) a performance evaluation of this implementation to demonstrate its feasibility.