As effective routing is critical in mobile ad hoc networks (MANETs), the Ad Hoc On-demand Distance Vector (AODV) has been extensively studied in recent years. AODV is a single path routing protocol that requires a new route discovery procedure whenever a link breaks, such frequent route discoveries incur a high routing overhead and increase end-to-end delay. Therefore, by modifying the AODV protocol, this work presents a novel backup routing scheme capable of repairing disrupted links locally without activating a route re-discovery procedure. Additionally, backup paths are established based on 2-hop neighbor knowledge. These backup paths are geographically close to the primary path in order to provide efficient recovery from route failure and maintain an adequate routing length. Simulation results indicate that the proposed backup routing scheme obtains a lower average end-to-end delay and less routing overhead than those of the Ad hoc On-demand Multipath Distance Vector (AOMDV) and the conventional AODV.

The ever-increasing number of devices capable of, not only connecting to existing communication networks, but also, independently creating new ones is defining a new communication network, in which the Internet is only one of the substrate networks pro- viding connectivity between diverse devices. This is a network with many interconnected mobile devices connecting to infrastructure networks and creating their own dynamic substrate networks. We present a novel routing scheme for diverse collections of substrate networks with a mix of mobile and static nodes. A key element of the routing scheme is to utilize the exiting routing paths in substrate networks, and set up routing paths between substrate networks. We use sets of nodes as landmarks and define locators that describe node position in the network relative to landmarks. This allows our routing scheme to scale to a large number of nodes, as only information about landmarks needs to be propagated throughout the network.

The ever-increasing number of devices capable of, not only connecting to existing communication networks, but also, independently creating new ones is defining a new communication network, in which the Internet is only one of the substrate networks pro- viding connectivity between diverse devices. This is a network with many interconnected mobile devices connecting to infrastructure networks and creating their own dynamic substrate networks. We present a novel routing scheme for diverse collections of substrate networks with a mix of mobile and static nodes. A key element of the routing scheme is to utilize the exiting routing paths in substrate networks, and set up routing paths between substrate networks. We use sets of nodes as landmarks and define locators that describe node position in the network relative to landmarks. This allows our routing scheme to scale to a large number of nodes, as only information about landmarks needs to be propagated throughout the network.

In recent years, wireless mesh networking has attracted a growing interest due to its inherent flexibility, scalability, and reliability. The IEEE 802.16 standard, commonly known as worldwide interoperability for microwave access (WiMAX), is the latest technology that enables broadband wireless access over long distances. WiMAX, which emerges as a wireless alternative to cable and digital subscriber line (DSL), is an ideal candidate to serve as the infrastructure for large scale wireless mesh networks. This thesis focuses on the quality of service (QoS) provisioning techniques in WiMAX-based metropolitan area mesh networks. We study the connection admission control (CAC) and routing issues in the design and operation of wireless multihop mesh networks. We propose a joint CAC and routing scheme for multiple service classes with the objective to maximize the overall revenue from all carried connections. Connection-level QoS constraints such as handoff connection dropping probability can be guaranteed within a threshold. Multiple service classes can be prioritized by imposing different reward rates. We apply optimization techniques to obtain the optimal CAC policies. The optimality criterion is the long-run average reward. We demonstrate that the proposed scheme can the maximum revenue obtainable by the system under QoS constraints. We show that the optimal joint policy is a randomized policy, i.e., connections are admitted to the system with some probabilities when the system is in certain states. Simulation results illustrate that the proposed scheme meets our design goals and outperforms the existing scheme.

Tor is a popular anonymity-preserving network, consisting of routers run by volunteers all around the world. It protects Internet users’ privacy by relaying their network traffic through a series of routers, thus concealing the linkage between the sender and the recipient. Despite the advantage of Tor’s anonymizing capabilities, it also brings extra latency, which discourages more users from joining the network. One of the factors that causes the latency lies in Tor’s circuit scheduling algorithm, which allows busy circuits to crowd out bursty circuits. In this work, we propose and implement a more advanced scheduling algorithm which treats circuits differently, based on their recent activity. In this way, bursty circuits such as those used for web browsing can gain higher priority over busy ones such as used for bulk transfer; the performance for most activities over Tor is improved, while minimal overhead is incurred. Our algorithm has been incorporated into the latest build of Tor.

A peer-to-peer (P2P) system is a networked system characterized by the lack of centralized control, in which all or most communication is symmetric. Also, a P2P system is supposed to handle frequent arrivals and departures of nodes, and is expected to scale to very large network sizes. These requirements make the design of P2P systems particularly challenging. We investigate two central issues pertaining to the design of P2P systems: load balancing and routing. In the first part of this thesis, we study the problem of load balancing in the context of Distributed Hash Tables (DHTs). Briefly, a DHT is a giant hash table that is maintained in a P2P fashion: Keys are mapped to a hash space I --- typically the interval [0,1), which is partitioned into blocks among the nodes, and each node stores the keys that are mapped to its block. Based on the position of their blocks in I, the nodes also set up connections among themselves, forming a routing network, which facilitates efficient key location. Typically, in a DHT it is desirable that the nodes' blocks are roughly of equal size, since this usually implies a balanced distribution of the load of storing keys among nodes, and it also simplifies the design of the routing network. We propose and analyze a simple distributed scheme for partitioning I, inspired by the multiple random choices paradigm. This scheme guarantees that, with high probability, the ratio between the largest and smallest blocks remains bounded by a small constant. It is also message efficient, and the arrival or departure of a node perturbs the current partition of I minimally. A unique feature of this scheme is that it tolerates adversarial arrivals and departures of nodes. In the second part of the thesis, we investigate the complexity of a natural decentralized routing protocol, in a broad family of randomized networks. The network family and routing protocol in question are inspired by a framework proposed by Kleinberg to model small-world phenomena in social networks, and they capture many designs that have been proposed for P2P systems. For this model we establish a general lower bound on the expected message complexity of routing, in terms of the average node degree. This lower bound almost matches the corresponding known upper bound.

Nowadays traffic congestion is a big problem all over the world. To solve this problem governments build broader roads, establish more reasonable traffic rules. Dynamic routing is a good and efficient way to reduce traffic congestion. That is why research of real time vehicle routing optimization algorithms was made. Experiment showed that best performance of shortest path algorithm was Dijkstra algorithm. Based on that, a software prototype was developed – optimized route search system. Driver can select shortest or fastest route to his destination. There was used roads length to evaluate shortest path and special coefficient to evaluate fastest route. This coefficient is calculated respectively to road load, length, speed limit, capacity. Performance of developed system is good so I conclude that the system is capable of routing vehicles in real time in complex traffic network.

The analysis of large-scale watershed processes and development of an efficient and integrated modelling platform is the focus of this research. The research focused on developing a series of modelling tools that can be used in the simulation of the overall response of a watershed based on a localized or distributed hydrologic event. This is achieved through the introduction of a hybrid modelling concept using a combination of empirically based lumped hydrologic processes and a physics-based distributed model representation. The watershed simulation model (GFLOOD) was developed to account for the complexity of the watershed including the variations in climate, soils, topography, and landuse conditions across the watershed. GFLOOD stands for Guelph Flood Forecasting Model, a river basin or watershed scale flow prediction model. Two major modelling components of the GFLOOD model are the time parameters (time of concentration (Tc) and recession constant (K)) and the channel routing component. Each of these modelling components is evaluated separately. The equations developed in this study for estimating the time parameters can be used as an initial estimate for Tc and K for ungauged basins, and through calibration and/or sensitivity analysis the values of Tc and K can be finalized. The Saint Venant equations for flood routing are solved by transforming the momentum equation into a partial differential equation which has six parameters related to cross-sectional area and discharge of the channel, left floodplain and right floodplain. The simplified dynamic model was further modified to account for transmission losses, evaporation losses and bank storage within the channel. The model was compared with the solutions of the general dynamic wave model, diffusion wave model and the more complex dynamic wave model. The comparison shows that there is good agreement between the results of the simplified dynamic model and the other models however, the simplified dynamic model is easier to formulate and compute than the other models. The complete GFLOOD model was applied to the Welland River Watershed within Southern Ontario. The model was evaluated for its ability to predict streamflow and water levels along the main branch of the Welland River.

In this paper, a Multiple Vehicle Routing Problem with Fuel Constraints (MVRPFC) is considered. This problem consists of a field of targets to be visited, and a collection of vehicles with fuel tanks that may visit the targets. Consideration of this problem is mainly in the improvement of feasible solutions, but the following steps are discussed: Cost Matrix Transformation, Field Partitioning, Tour Generation and Rerouting, and Tour Improvement. Four neighborhoods were investigated (2-opt, 3-opt, Target Vehicle Exchange, Depot Exchange), using the Variable Neighborhood Descent and Variable Neighborhood Search schemes, with APD and Voronoi partition methods. These neighborhoods were compared to investigate their performance for various instances using the above schemes and partition methods. In general, 2-opt performed as well as 3-opt in less time than 3-opt; in fact, 3-opt was the slowest of the four neighborhoods. Additionally, the Variable Neighborhood Descent scheme was found to produce better results than the Variable Neighborhood Search.

Recent advances in wireless and sensing technologies have enabled the deployment of large scale Wireless Sensor Networks (WSNs) which have a wide range of scientific and commercial applications. However, due to the limited energy supply of sensor nodes, extending the network lifetime has become crucial for WSNs to deliver their promised benefits. Several proposals have aimed at this objective by designing energy efficient protocols at the physical, medium access, and network layers. While the proposed protocols achieve significant energy savings for individual sensor nodes, they fail to solve topology-related problems. An example of such problems is the bottlenecks around the sink, which is a direct result of multi-hop relaying: sensor nodes around the sink relay data generated all over the network which makes them deplete their energy much faster than other nodes. A natural solution to this problem is to have multiple mobile data collectors so that the load is distributed evenly among all nodes. We investigate this promising direction for balancing the load and, hence, prolonging the lifetime of the network. We design optimization schemes for routing and placement of mobile data collectors in WSNs. We show, by theoretical analysis and simulations, that our approach has the potential to prolong the lifetime of the network significantly. / Thesis (Ph.D, Computing) -- Queen's University, 2009-04-26 21:58:55.152