As the field of Delay Tolerant Networking continues to expand and receive more attention, a new class of routing algorithms have been proposed that are specifically tailored to perform in a network where no end to end paths between devices are assumed to exist. As the number of proposed routing algorithms has grown, it has become difficult to fully understand their similarities and differences. Although published results clearly show different performance results between algorithms, it can be difficult to pinpoint which of their characteristics are most responsible for their performance differences. This thesis proposes an architectural framework to define the underlying features that Delay Tolerant Network routing algorithms are composed of. Popular routing algorithms from research are discussed and shown to be compositions of the proposed architectural features, thereby validating the architecture itself. The architectural framework is also shown to be a useful guide to developing a modular and configurable simulation platform. Algorithms from literature were implemented as a composition of features, which can easily be modified and combined later to define and implement new algorithms. Better understanding the underlying structure and similarities between different routing algorithm approaches is key to truly analyzing their performance and obtaining a deep understanding of which components of an algorithm have the most influence, both positively and negatively, on the results. Armed with this knowledge, designers of Delay Tolerant Networks can more easily determine the proper composition of routing algorithm features to best fit their needs. / text

Consumer electronics such as cellular phones and portable computers with short-range communication capabilities have enabled the large-scale information dissemination through user mobility and contact, without the assistance of communication infrastructures. In such a new communication paradigm, one challenge is to determine when and how to forward a message to the destination, possibly through a series of third parties. This problem has attracted a lot of attention in the literature lately, with proposals ranging from epidemic to single or multi-copy spray and wait or focus strategies. However most existing work assumed independent or identically distributed mobility. Observing most human mobility and interaction are interest-driven in the real world, in this research, we evaluate the performance of these schemes with an interest-driven mobility model. We further propose to take the user interest into account when determining routing strategies to further improve the performance of these schemes for mobile social networks. Simulation results have demonstrated the efficacy of the interest-aware routing strategies. / Graduate

The recent years have seen an enormous advance in wireless communication technology and co-existence of various types of wireless networks, which requires effective inter-networking among the heterogeneous wireless networks in order to support user roaming over the networks while maintaining the connectivity. One of main challenges to achieve the connectivity over heterogeneous wireless networks is potential intermittent connections caused by user roaming. The issue is how to maintain the connection as the user roams and how to ensure service quality in the presence of a long disconnection period. In this dissertation, we apply the delay tolerant network (DTN) framework to heterogeneous terrestrial wireless networks, and propose a system architecture to achieve the connectivity in the presence of excessive long delays and intermittent paths. We study several possible approaches, discuss the applicability of each of the approaches and propose the super node architecture. To demonstrate the effectiveness of the proposed super node architecture, we give a simulation study that compares the system performance under the super node architecture and under the epidemic based architecture. Within the proposed architecture that employs the idea of super nodes, we further study how to effectively route a message over access networks. We present a new routing technique for mobile ad-hoc networks (MANETs) based on the DTN system architecture. We introduce the concept of virtual network topology and redefine the dominating-set based routing for the challenged network environment under consideration. In addition, we propose a time based methodology to predict the probability of future contacts between node pairs to construct the virtual network topology. We present a simulation study that demonstrates the effectiveness of the proposed routing approach as compared with the epidemic routing, and that the time based technique for predicting the future contacts gives better performance compared with that using the number of previous contacts. We further extend the dominating set routing technique through analyzing the underlying node mobility model. We shed some light on how using node mobility model can improve contact probability estimation. Based on our findings we propose a new algorithm that improves the routing performance by minimizing the selected dominating set size. Information security challenges in the super node architecture are introduced. We further address two main security challenges: The first is how to prevent unauthorized nodes from using the network resources, and the second is how to achieve end-to-end secure message exchange over the network. Our proposed solutions are based on asymmetric key cryptography techniques. Moreover, we introduce a new idea of separating the problem of source authentication from the problem of message authorization. We propose a new technique that employs the one-way key chain to use symmetric key cryptographic techniques to address the problems under consideration.

Delay-tolerant networking (DTN) has recently received considerable attention from the research community. This type of networks is characterized by frequent disconnections due to propagation phenomena, node mobility, and power outages. Thus, the complete path between the source and the destination may never have existed. This context requires the design of new communication paradigms and techniques that will make communication possible in these environments. To achieve message delivery, researchers have proposed the use of store-carry-and-forward protocols, whereby a node may store the message and carry it until an appropriate forwarding opportunity arises. Many flooding-routing schemes have been proposed for DTNs in order to increase the probability of message delivery. However, these schemes suffer from excessive energy consumption, severe contention that significantly degrades their performance, especially if we account for the fact that each node could be a hand-held and battery-powered device with stringent buffer size limitation. With such buffer limitations at the DTN nodes, message drop/loss could happen due to buffer overflow. In order to address the problem and improve the performance of DTNs, this thesis focuses on two main design objectives; first, the design and evaluation of new multi-copy routing schemes; second, the design and evaluation of new scheduling and dropping policies to reduce message drop/loss due to buffer overflow. To fulfill the first objective, a protocol called Self Adaptive Routing Protocol (SARP) is introduced. It is a multi-copy scheme designed to suit resource-sufficient DTNs. Based on SARP, two multi-copy routing schemes are further developed to suit resource-limited DTNs, in which compensating the traffic demand become a challenge: i) the Self Adaptive Utility-based Routing Protocol (SAURP), ii) and the Adaptive Reinforcement based Routing Protocol (ARBRP). The introduced protocols form a new framework of DTNs aiming to significantly reduce the resource requirements of flooding-based routing schemes. Each introduced scheme has its own way of exploring the possibility of taking mobile nodes as message carriers in order to increase the delivery ratio of the messages. In SAURP, the best carrier for a message characterized by jointly considering the inter-contact time that is obtained using a novel contact model and the network status, such as including wireless link condition and nodal buffer availability. In ARBRP, the routing problem is solved by manipulating a collaborative reinforcement learning technique, where a group of nodes can cooperate with each other to make a forwarding decision for the stored messages based on a cost function at each contact with another node. ARBRP is characterized by not only considering the contact time statistics, but also looks into the feedback on user behavior and network conditions, such as congestion and buffer occupancy sampled during each previous contact with any other node. The thesis argues and proves that the nodal movement and the predicted collocation with the message recipient can serve as meaningful information to achieve an intelligent message forwarding decision at each node. Therefore, the introduced protocols can achieve high efficiency via an adaptive and intelligent routing mechanism according to network conditions. To fulfill the second objective, we further enhanced the performance of DTN routing by introducing message scheduling and dropping policies such that the delivery ratio is increased and/or the delivery delay is reduced. This thesis investigates new buffer management and scheduling policies to improve the performance of flooding and utility-based forwarding routing in DTNs, such that the forwarding/dropping decision can be made at a node during each contact for either optimal message delivery ratio or message delivery delay. To examine their effectiveness, the introduced protocols and the buffer management and scheduling policies have been implemented and compared to a number of existing counterpart approaches. A near-realistic mobility model is used for testing. A number of scenarios are used to evaluate the performance of the introduced techniques in terms of delivery delay, ratio, and the number of transmissions performed.

In recent years, significant advances have been achieved in communication networks and electric power systems. Communication networks are developed to provide services within not only well-connected network environments such as wireless local area networks, but also challenged network environments where continuous end-to-end connections can hardly be established between information sources and destinations. Delay tolerant network (DTN) is proposed to achieve this objective by utilizing a store-carry-and-forward routing scheme. However, as the network connections in DTNs are intermittent in nature, the management of network resources such as communication bandwidth and buffer storage becomes a challenging issue. On the other hand, the smart grid is to explore information and communication technologies in electric power grids to achieve electricity delivery in a more efficient and reliable way. A high penetration level of electric vehicles and renewable power generation is expected in the future smart grid. However, the randomness of electric vehicle mobility and the intermittency of renewable power generation bring new challenges to the resources management in the smart grid, such as electric power, energy storage, and communication bandwidth management. This thesis consists of two parts. In part I, we focus on the resource management in DTNs. Specifically, we investigate data dissemination and on-demand data delivery which are two of the major data services in DTNs. Two kinds of mobile nodes are considered for the two types of services which correspond to the pedestrians and high-speed train passengers, respectively. For pedestrian nodes, the roadside wireless local area networks are used as an auxiliary communication infrastructure for data service delivery. We consider a cooperative data dissemination approach with a packet pre-downloading mechanism and propose a double-loop receiver-initiated medium access control scheme to resolve the channel contention among multiple direct/relay links and exploit the predictable traffic characteristics as a result of packet pre-downloading. For high-speed train nodes, we investigate on-demand data service delivery via a cellular/infostation integrated network. The optimal resource allocation problem is formulated by taking account of the intermittent network connectivity and multi-service demands. In order to achieve efficient resource allocation with low computational complexity, the original problem is transformed into a single-machine preemptive scheduling problem and an online resource allocation algorithm is proposed. If the link from the backbone network to an infostation is a bottleneck, a service pre-downloading algorithm is also proposed to facilitate the resource allocation. In part II, we focus on resource management in the smart grid. We first investigate the optimal energy delivery for plug-in hybrid electric vehicles via vehicle-to-grid systems. A dynamic programming formulation is established by considering the bidirectional energy flow, non-stationary energy demand, battery characteristics, and time-of-use electricity price. We prove the optimality of a state-dependent double-threshold policy based on the stochastic inventory theory. A modified backward iteration algorithm is devised for practical applications, where an exponentially weighted moving average algorithm is used to estimate the statistics of vehicle mobility and energy demand. Then, we propose a decentralized economic dispatch approach for microgrids such that the optimal decision on power generation is made by each distributed generation unit locally via multiagent coordination. To avoid a slow convergence speed of multiagent coordination, we propose a heterogeneous wireless network architecture for microgrids. Two multiagent coordination schemes are proposed for the single-stage and hierarchical operation modes, respectively. The optimal number of activated cellular communication devices is obtained based on the tradeoff between communication and generation costs.

Zugl.: Ilmenau, Techn. Univ., Diss., 2010

No description available.

在耐延遲網路(Delay Tolerant Network)中，因節點之間的高移動性、連接的不確定性環境嚴苛限制，採用Store-And-Forward 訊息傳輸的模式提供一個可接受的網路表現。常見的路由協定可分為機會路由、基於預測的路由以及調度路由，然而這些路由協定使用在市區環境中，有些許不足的地方，因此我們提出適用在市區封包轉發策略。 我們提出的以公車亭為基礎之耐延遲車載網路封包轉發策略，是在市區環境中建立一個以公車亭為基礎的資料傳送架構，包含汽車、公車、公車站、公車轉運站四種節點。我們建立節點與節點相遇時資料傳送規則，例如汽車與汽車相遇、汽車與公車相遇、公車與公車站相遇、公車與公車轉運站相遇、公車轉運站與公車相遇、公車站與汽車相遇、汽車與目的地相遇時各自有不同的資料傳送判斷與限制。 實驗結果也證明所提出的演算法，除了可以有效地減少延遲傳送時間並提高訊息成功傳送率，及在各節點有限的緩衝區大小下，我們的封包轉發策略有著最突出的效能。 / In Delay Tolerant Networks (DTNs), there does not exist an end-to-end path due to intermittent connectivity and high node mobility. Messages are stored for a period of time at network nodes and are conveyed hop-by-hop to the destination. The current DTN routing protocols can be summarized into three categories: opportunistic, prediction-based and scheduling protocols. However, these routing protocols have some deficiencies and are not specifically focused on the urban areas. Based on the characteristics of urban areas, we proposed a kiosk based packet forwarding strategy for vehicular delay tolerant networks. We established the rules of data transmission when one node contacts other nodes. More specifically, Car-to-Car, Car-to-Bus, Bus-to-Bus stop, Bus-to-Bus transfer station, Bus transfer station-to-Bus, Bus stop-to-Car ,Car-to-Destination contacts, have different judgments and restrictions for data forwarding. The simulation results demonstrate that we proposed packet forwarding strategy would reduce the delivery delay, and improve the successful delivery rate. Especially with limited buffer and little overhead, our proposed strategy has the most prominent performance.

許多國家正面臨因嚴重的交通壅塞所帶來龐大的經濟損失，同樣在台灣也面臨相同問題，根本解決之道就是找出壅塞路段，並即時地告知車輛駕駛以迴避此路段。因此如何有效率地偵測出壅塞路段，是當前重要的議題。以往大多透過長期所累積的統計數據，針對各路段收集行駛於該路段所有車輛的平均速度，來獲得該路段的交通狀況，但卻無法立即反應即時路況。 因此我們提出以耐延遲車載網路方式，收集路況資訊與彙整旅途時程，透過具有全球定位系統(GPS)以及無線網路的車輛來進行路況交通資訊的收整與交換。再透過本研究所提出路況交通覺知路由協定(RTARP)，以One-Hop Controlled Flooding的傳輸方式在節點與節點相遇時進行路況資訊的傳送，進而交換節點彼此間各自所存放各路段的路況資訊。 模擬實驗結果證明我們所提出的路由協定在路況交通資訊交換中，有效地減少網路傳輸負載、提高訊息送達成功率以及路況交通資訊(RTI)正確率。 / Many countries are concerning about the huge economic losses caused by the critical traffic congestion. We have the same problem in Taiwan. The solutions lie in finding the road section with traffic congestion first and informing drivers to avoid that section. But how to detect the road section with traffic congestion effectively is the most important issue of this research. Conventionally, the real-time road traffic is mostly predicted by long-term accumulated statistics calculated by the collection of the average speed of cars on the same road section. But this way can’t provide the real-time road traffic immediately. Based on vehicles with GPS and the capability of WiFi, we proposed gathering road traffic information and consolidating travel time estimation using vehicular delay tolerant networks. We also proposed the Road Traffic Awareness Routing Protocol (RTARP) to exchange the road traffic information preserved individually by One-Hop Controlled Flooding during nodes’ encounter. The results of simulations prove the routing protocol we proposed can effectively reduce the transmission overhead, improve the delivery ratio and the accuracy of the road traffic information.

Les réseaux mobiles Ad hoc (MANETs) visent à permettent à des noeuds mobiles de communiquer sans aucun support d'infrastructure. Les MANETs dispersés entrent dans la catégorie des réseaux tolérants aux délais (DTN), qui sont des réseaux connectés par intermittence et où il n'y a aucun chemin de bout-en-bout persistant à n'importe quel temps donné. Nous proposons, d'abord, un nouveau protocole de transport fiable pour les DTNs basé sur l'utilisation d'accusés de réception ainsi que le codage linéaire aléatoire. Nous modélisons l'évolution du réseau conformément à notre plan en utilisant l'approche fluide. Nous obtenons le temps de transfert d'un fichier en fonction de certains paramètres optimaux obtenus par l'approche d'évolution différentielle. Deuxièmement, Nous proposons ainsi et étudions un nouveau mécanisme d'ACK augmenté, pour améliorer le transport fiable pour les DTNs, pour les cas unicast et multicast. Nous nous servons du codage linéaire aléatoire aux relais pour que les paquets puissent atteindre la destination plus rapidement. Nous obtenons la fiabilité basée sur l'utilisation Global Sélective ACKnowledgement. Enfin, nous abordons le problème de l'estimation de propagation des fichiers dans les DTNs avec livraison directe et le routage épidémique. Nous estimons et suivons le degré de propagation d'un message dans le réseau. Nous fournissons la base analytique à notre cadre d'évaluation avec des aperçus validés en se basant sur des simulations. En plus, nous utilisons le filtre de Kalman et Minimum- Mean-Squared Error (MMSE) pour suivre le processus de propagation et trouvons que le filtre de Kalman fournit des résultats plus précis par rapport à MMSE / Mobile Ad hoc NETworks (MANETs) aim at making communication between mobile nodes feasible without any infrastructure support. Sparse MANETs fall into the class of Delay Tolerant Networks which are intermittently connected networks and where there is no contemporaneous end-to-end path at any given time. We first, propose a new reliable transport scheme for DTNs based on the use of ACKnowledgments and random linear coding. We model the evolution of the network under our scheme using a fluid-limit approach. We optimize our scheme to obtain mean file transfer times on certain optimal parameters obtained through differential evolution approach. Secondly, we propose and study a novel and enhanced ACK to improve reliable transport for DTNs covering both unicast and multicast flows. We make use of random linear coding at relays so that packets can reach the destination faster. We obtain reliability based on the use of so-called Global Selective ACKnowledgment. We obtain significant improvement through G-SACKs and coding at relays. Finally, we tackle the problem of estimating file-spread in DTNs with direct delivery and epidemic routing. We estimate and track the degree of spread of a message in the network. We provide analytical basis to our estimation framework alongwith insights validated with simulations. We observe that the deterministic fluid model can indeed be a good predictor with a large of nodes. Moreover, we use Kalman filter and Minimum- Mean-Squared-Error (MMSE) to track the spreading process and find that Kalman filter provides more accurate results as compared to MMSE