Master of Science / Department of Computing and Information Sciences / Gurdip Singh / Ad hoc based routing protocol is a reactive protocol to route messages between mobile nodes. It allows nodes to pass messages through their neighbors to nodes which they cannot directly communicate. It uses Route Request (RREQ) and Route Reply (RREP) messages for communication. Wireless sensor networks consist of tiny sensor motes with capabilities of sensing, computation and wireless communication. This project aims to implement data collector application to collect the temperature data from the set of wireless sensor devices located within a building, which will help in gathering the information by finding the route with minimum number of hops to reach destination and generates low message traffic by not encouraging the duplicate message within the network. Using this application, wireless devices can communicate effectively to provide the network information to the user. This system consists of a mobile wireless sensor device called base station which is connected to a PC to communicate and is the root of the network. It also consists of set of client sensor devices which are present in different parts of the building. This project has been evaluated by determining how well the ad hoc protocol performs by measuring the number of messages and time consumed in learning about the complete topology. This application will eventually find the path with minimum number of hops. Simple Network Management Protocol (SNMP) is also used to monitor the sensor nodes remotely. This project was developed using nesC and C programming languages with TinyOS and UNIX based operating systems. It has been tested with a sufficient number of motes and evaluated based on the number of messages generated and number of hops traveled for each route request.

In this thesis, we study time-sensitive applications where it is important to minimize the completion time, i.e., time passing between receiving the instance and finishing the implementation of the solution. Different from the traditional approach, we are directly focusing on the minimization of the computation time as well as finding the optimal solution to the problem. The conventional approach to these conflicting objectives is generally to trade off one for the other. As an alternative, we propose a new approach called Computation-Implementation Parallelization (CIP), and develop methods to embed the computation time into the solution-implementation to minimize the total completion time. We implement our CIP approach and show its effectiveness on a type of TSP we call the TSP Race problem, where the goal is to minimize the time between receiving the instance and finishing the travel. We demonstrate a method for determining a priori when CIP will be effective. We also implement our CIP approach on Computation-Time Limited Capacitated Vehicle Routing (CTL-CVRP) problems, and show that it is possible to decrease the computation-only time while maintaining the solution quality. By this means, some of the computation time can be set free and used to improve the customer service either by delaying the order cutoff time or dispatching the trucks earlier. As a tangential study, we develop a new TSP tour length estimation model. Our model is distribution-free, and is shown to produce very accurate estimates on many different node dispersions.

In communication networks today, the amount of users and traffic is constantly increasing. This results in the need for upgrading the networks to handle the demand. Free space optics, FSO, is a technique which is relatively cheap with high capacity compared to most systems today. On the other hand, FSO have some disadvantages with the effects on the system by, for instance, turbulence and weather. The aim of the project is to investigate the use of network optimization for designing an optimal network in terms of capacity and cost. Routing optimization is also covered in terms of singlepath and multipath routing. To mitigate the problem with turbulence affecting the system network survivability is implemented with both proactive and reactive solutions. The method used is to implement the system in Matlab, the system should also be tested so that it works as intended. The report covers related work as well as theory behind FSO and the chosen optimization algorithms. The system uses modified Bellman-Ford optimization as well as Kruskal’s minimum spanning tree. K-link-connectivity is also implemented for the network survivability and multipath algorithm. Results of the implementation shows that the network survivability improves the robustness of the system by changing paths for traffic which is affected by broken links. Routing done by multipath will increase the throughput and also reduce the delay for the traffic.

In recent years, the importance of incorporating uncertainty into planning models for logistics and transportation systems has been widely recognized in the Operations Research and transportation science communities. Maritime transportation, as a major mode of transport in the world, is subject to a wide range of disruptions at the strategic, tactical and operational levels. This thesis is mainly concerned with the development of robustness planning strategies that can mitigate the effects of some major types of disruptions for an important class of optimization problems in the shipping industry. Such problems arise in the creation and negotiation of long-term delivery contracts with customers who require on-time deliveries of high-value goods throughout the year. In this thesis, we consider the disruptions that can increase travel times between ports and ultimately affect one or more scheduled deliveries to the customers. Computational results show that our integrated solution procedure and robustness planning strategies can generate delivery plans that are both economical as well as robust against uncertain disruptions.

The Internet faces well-known challenges in realizing modifications to the core architecture. To help overcome these limitations, the use of network virtualization has been proposed. Network virtualization enables the deployment of novel network architectures and services on existing Internet infrastructure. Virtual networks run over physical networks and use Internet paths and protocols as essentially a link layer in the virtual network. Virtual networks can also share the resources in the physical substrate. Effective use of the underlying substrate network requires intelligent placement of virtual networks so that underlying resources do not incur over-subscription. Because virtual networks can come and go over time, and underlying networks can experience their own dynamic changes, virtual networks need to be migrated---re-mapped to the physical network during active operation---to maintain good performance. While virtual network placement, and to a lesser extent migration, has been studied in the past, little attention has been devoted to designing, deploying, and evaluating migration mechanisms for virtual networks. In this dissertation, we design virtual network migration mechanisms for different substrate platforms and further design a system to mitigate the effects of virtual network migration. In particular this dissertation makes the following contributions: 1. With the goal of minimizing the disruption during a virtual network migration, we design three algorithms for scheduling the sequence of virtual router moves that takes a virtual network from its original placement to its new placement. 2. We design and implement a controller-based architecture for virtual network migration on PlanetLab. This work explores the challenges in implementing virtual network migration on real infrastructure. Recommendations are given for infrastructure that support virtual network migration. 3. We propose and implement a mechanism to mitigate the performance degradation resulting from virtual network migration through transport and application layer collaboration. We utilize a centralized controller to notify the end-systems or the gateways about the time of the virtual network migration such that we prevent packet loss to the application traffic of the end-systems.

published_or_final_version / abstract / Computer Science / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

Mobile Ad-hoc Networks (MANETs) have received considerable research interest in recent years. Because of dynamic topology and limited resources, it is challenging to design routing protocols for MANETs. In this dissertation, we focus on the scalability and efficiency problems in designing routing protocols for MANETs. We design the Way Point Routing (WPR) model for medium to large networks. WPR selects a number of nodes on a route as waypoints and divides the route into segments at the waypoints. Waypoint nodes run a high-level inter-segment routing protocol, and nodes on each segment run a low-level intra-segment routing protocol. We use DSR and AODV as the inter-segment and the intra-segment routing protocols, respectively. We term this instantiation the DSR Over AODV (DOA) routing protocol. We develop Salvaging Route Reply (SRR) to salvage undeliverable route reply (RREP) messages. We propose two SRR schemes: SRR1 and SRR2. In SRR1, a salvor actively broadcasts a one-hop salvage request to find an alternative path to the source. In SRR2, nodes passively learn an alternative path from duplicate route request (RREQ) packets. A salvor uses the alternative path to forward a RREP when the original path is broken. We propose Multiple-Target Route Discovery (MTRD) to aggregate multiple route requests into one RREQ message and to discover multiple targets simultaneously. When a source initiates a route discovery, it first tries to attach its request to existing RREQ packets that it relays. MTRD improves routing performance by reducing the number of regular route discoveries. We develop a new scheme called Bilateral Route Discovery (BRD), in which both source and destination actively participate in a route discovery process. BRD consists of two halves: a source route discovery and a destination route discovery, each searching for the other. BRD has the potential to reduce control overhead by one half. We propose an efficient and generalized approach called Accumulated Path Metric (APM) to support High-Throughput Metrics (HTMs). APM finds the shortest path without collecting topology information and without running a shortest-path algorithm. Moreover, we develop the Broadcast Ordering (BO) technique to suppress unnecessary RREQ transmissions.

In Mobile Ad Hoc Networks (MANETs), nodes depend on each other for routing and forwarding packets. However, to save power and other resources, nodes belonging to independent authorities may behave selfishly, and may not be willing to help other nodes. Such selfish behavior poses a real threat to the proper functioning of MANETs. One way to foster node cooperation is to introduce punishment for selfish nodes. Based on neighbor-monitoring techniques, a fully distributed solution to detect, punish, and re-admit selfish nodes, is proposed here. This solution provides nodes the same opportunity to serve/and be served by others. A light-weight solution regarding battery status is also proposed here. This solution requires neighbor monitoring only when necessary, thereby saving nodes battery power. Another effective way to solve the selfish-node problem is to reward nodes for their service according to their cost. To force nodes to show their true cost, truthful protocols are needed. A low overhead truthful routing protocol to find optimal routes is proposed in this thesis. The most prominent feature of this protocol is the reduction of overhead from existing solutions O(n3) to O(n2). A light-weight scalable truthful routing protocol (LSTOP) is further proposed, which finds near-least-cost paths in dense networks. LSTOP reduces overhead to O(n) on average, and O(n2) in worst case scenarios. Multiple path routing protocols are an effective alternative to single path routing protocols. A generic mechanism that can turn any table-driven multipath routing protocol into a truthful one, is outlined here. A truthful multipath routing protocol (TMRP), based on well-known AOMDV protocol, is presented as an example. TMRP incurs an only 2n message overhead for a route discovery, and can also achieve load balancing without compromising truthfulness. To cope with the selfish-node problem in the area of position-based routing, a truthful geographic forwarding (TGF) algorithm is presented. TGF utilizes three auction-based forwarding schemes to stimulate node cooperation. The truthfulness of these schemes is proven, and their performance is evaluated through statistical analysis and simulation studies.

The all-over trend for an universal access and ubiquitous access to the Internet is driving a revolution in our societies. In order to support this era of nomadic applications, new flexible network architectures have emerged. They are referred to as “wireless ad-hoc networks.” Since human-operated devices will more likely be used indoor, it leads to many issues related to the strength of the fading in this environment. Recently, it has been suggested that a possible interaction might exist between various parameters of the ad-hoc networks and, more precisely, between the propagation model and the routing protocol. To address this question, we present in this dissertation a cross-layer perspective of the analysis of these indoor ad-hoc networks. Our reasoning is made of four stages. First, the cross-layer interactions are analyzed by the means of multivariate statistical techniques. Since a cross-layering between the physical layer and the routing protocol has been proven to be significant, we further investigate the possible development a physical layer-constrained routing algorithm. Second, fundamental equations governing the wireless telecommunications systems are developed in order to provide insightful informations on how a reliable routing strategy should be implemented in a strongly-faded environment. After that, and in order to allow a better spatial reuse, the routing protocol we propose is further enhanced by the adjonction of a power control algorithm. This last feature is extensively analyzed and a closed-form expression of the link probability of outage in presence of non-homogeneous transmission powers is given. Numerous simulations corroborate the applicability and the performance of the derived protocol. Also, we evaluate the gain, in terms of radio channel ressources, that has been achieved by the means of the power control algorithm. Third, an architecture for the interconnection with a cellular network is investigated. A closed-form expression of the relaying stability of a node is given. This equation expresses the minimal requirement that a relaying node from the ad-hoc network must fullfil in order to bridge properly the connections to the base-station. Finally, a real-life implementation is provided as a validation of the applicability of this novel ad-hoc routing protocol. It is concluded that, both from the performance and the spatial re-use point-of-views, it can be taken advantage from the cross-layering between the physical and the routing layers to positively enhance the networking architectures deployed in an indoor environment.