This dissertation is a study on the design and analysis of novel, optimal routing and rate control algorithms in wireless, mobile communication networks. Congestion control and routing algorithms upto now have been designed and optimized for wired or wireless mesh networks. In those networks, optimal algorithms (optimal in the sense that either the throughput is maximized or delay is minimized, or the network operation cost is minimized) can be engineered based on the classic time scale decomposition assumption that the dynamics of the network are either fast enough so that these algorithms essentially see the average or slow enough that any changes can be tracked to allow the algorithms to adapt over time. However, as technological advancements enable integration of ever more mobile nodes into communication networks, any rate control or routing algorithms based, for example, on averaging out the capacity of the wireless mobile link or tracking the instantaneous capacity will perform poorly. The common element in our solution to engineering efficient routing and rate control algorithms for mobile wireless networks is to make the wireless mobile links seem as if they are wired or wireless links to all but few nodes that directly see the mobile links (either the mobiles or nodes that can transmit to or receive from the mobiles) through an appropriate use of queuing structures at these selected nodes. This approach allows us to design end-to-end rate control or routing algorithms for wireless mobile networks so that neither averaging nor instantaneous tracking is necessary.
@cite_4 @cite_50 @cite_8 study networks that are closer to ours. In @cite_50 , distant groups of nodes are connected via mobiles, much like our network but with general random mobility. At the intra-group level, a MANET routing protocol is used for route discovery, and at the inter-group level, the Spray-and-Wait algorithm @cite_53 is used among mobiles to decrease forwarding time and increase delivery probability. @cite_4 augments AODV with DTN routing to discover routes and whether those routes support DTN routing and to what extent they support end-to-end IP routing and hop-by-hop DTN routing. @cite_8 studies how two properties of the mobile nodes, namely whether a mobile is dedicated to serve a specific region (ownership) and whether the mobile movement can be scheduled and controlled by regions (scheduling time), affect performance metrics such as delay and efficiency.
@cite_53 @cite_4 @cite_50 @cite_8
2125957038 2163071443 2142640475 2122354383
Intermittently connected mobile networks are sparse wireless networks where most of the time there does not exist a complete path from the source to the destination. These networks fall into the general category of Delay Tolerant Networks. There are many real networks that follow this paradigm, for example, wildlife tracking sensor networks, military networks, inter-planetary networks, etc. In this context, conventional routing schemes would fail.To deal with such networks researchers have suggested to use flooding-based routing schemes. While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention, which can significantly degrade their performance. Furthermore, proposed efforts to significantly reduce the overhead of flooding-based schemes have often be plagued by large delays. With this in mind, we introduce a new routing scheme, called Spray and Wait, that "sprays" a number of copies into the network, and then "waits" till one of these nodes meets the destination.Using theory and simulations we show that Spray and Wait outperforms all existing schemes with respect to both average message delivery delay and number of transmissions per message delivered; its overall performance is close to the optimal scheme. Furthermore, it is highly scalable retaining good performance under a large range of scenarios, unlike other schemes. Finally, it is simple to implement and to optimize in order to achieve given performance goals in practice. Mobile Ad-hoc Network (MANET) routing protocols aim at establishing end-to-end paths between communicating nodes and thus support end-to-end semantics of existing transports and applications. In contrast, DTN-based communication schemes imply asynchronous communication (and thus often require new applications) but achieve better reachability, particularly in sparsely populated environments. In this paper, we suggest a hybrid scheme that combines AODV and DTN-based routing and allows keeping the AODV advantage of maintaining end-to-end semantics whenever possible while, at the same time, also offering DTN-based communication options whenever available---leaving the choice to the application. We present our protocol and system design, particularly including the interaction of AODV and DTN, demonstrate achievable performance gains based upon measurements, and report on initial experiments with our implementation in an emulation environment. In this paper we propose HYMAD, a Hybrid DTN-MANET routing protocol which uses DTN between disjoint groups of nodes while using MANET routing within these groups. HYMAD is fully decentralized and only makes use of topological information exchanges between the nodes. We evaluate the scheme in simulation by replaying real life traces which exhibit this highly dynamic connectivity. The results show that HYMAD outperforms the multi-copy Spray-and-Wait DTN routing protocol it extends, both in terms of delivery ratio and delay, for any number of message copies. Our conclusion is that such a Hybrid DTN-MANET approach offers a promising venue for the delivery of elastic data in mobile ad-hoc networks as it retains the resilience of a pure DTN protocol while significantly improving performance. The evolution of wireless devices along with the increase in user mobility have created new challenges such as network partitioning and intermittent connectivity. These new challenges have become apparent in many situations where the transmission of critical data is of high priority. Disaster rescue groups, for example, are equipped with numerous devices which constantly gather and transmit various forms of data. The challenge of establishing communication between groups of this type has led to an evolutionary form of networks which we consider in this paper, namely, delay tolerant mobile networks (DTMNs). Nodes in DTMNs usually form clusters that we define as regions. Nodes within each region have end-to-end paths between them. Both regions, as well as nodes within a region, can be either stationary or mobile. For such environments, we propose using a dedicated set of messengers that relay message bundles between these regions. Our goal is to understand how messenger scheduling can be used to improve network performance and connectedness. We develop several classes of messenger scheduling algorithms which can be used to achieve inter-regional communication in such environments. We use simulation to better understand the performance and tradeoffs between these algorithms.