Routing is the fundamental problem for Wireless Ad hoc networks, including Wireless Mobile Ad hoc networks (MANETs) and Wireless Sensor networks (WSNs). Although the problem has been extensively studied in the past decade, the existing solutions have deficiencies in one or more aspects including efficiency, scalability, robustness, complexity, etc.This dissertation proposes several new solutions for routing in WSNs and MANETs. Spiral is a data-centric routing algorithm for short-term communication in unstructured static WSNs. Spiral is a biased walk that visits nodes near the source before more distant nodes. This results in a spiral-like search path that is not only more likely to find a closer copy of the desired data than random walk, but is also able to compute a shorter route because the network around the source is more thoroughly explored. Compared with existing flooding and random walk approaches, Spiral has a lower search cost than flooding and returns better routes than random walk.Closest Neighbor First Search (CNFS) is a query processing algorithm for mobile wireless sensor networks. It is also walk-based and biased to visit nodes close to the source first. Different from Spiral, CNFS collects topology information as the search progresses. The topology information is used to compute the shortest return path for the query result and to tolerate the network topology changes caused by node mobility, which could otherwise cause the query to fail. CNFS requires fewer messages to process a query than flooding-based algorithms, while tolerating node mobility better than random walk-based algorithms.Address Aggregation-based Routing (AAR) is a novel routing protocol designed for MANETs. It reactively performs route discovery, but proactively maintains an index hierarchy called a Route Discovery DAG (RDD) to make route discovery efficient. The RDD contains aggregated node address information, requiring fewer packets for route discovery than the flooding used in existing protocols, while handling mobility better than pre-computing routes to all nodes. Compared with some existing popular protocols, AAR shows better performance in delivery rate, message overhead, latency and scalability.

In wireless sensor networks, source nodes usually send their data packets to a single sink following a specific routing protocol. In this way, unicast delivery becomes a dominant means of data transmission through the network. However, if one of links in the route is out of order, a dynamic routing protocol will rule the search by the routers for a new transmission route and thus, more time will be taken with regards to searching for the route. In this paper, a condition in which an emergency occurs is envisioned. Source nodes must send the emergency information packets to the possible sink as soon as possible. Then the multicast delivery should be taken instead of the unicast delivery so as to save more time.

This thesis presents the Forecasting Routing Technique (FORTEL), a routing protocol for Mobile Ad-Hoc Networks (MANETs) based on the nodes' Location Information. FORTEL stores the nodes' location information in the Location Table (LT) in order to construct routes between the source and the destination nodes. FORTEL follows the source routing strategy, which has rarely been applied in position-based routing. According to the source routing strategy, the end-to-end route is attached to the packet, therefore, the processing cost, in regards to the intermediate nodes that simply relay the packet according to route, is minimized. FORTEL's key mechanisms include: first, the location update scheme, employed to keep the LT entries up-to-date with the network topology. Besides the mobility variation and the constant rate location update schemes applied, a window location update scheme is presented to increase the LT's information accuracy. Second, the switching mechanism, between "Hello" message and location update employed, to reduce the protocol's routing overhead. Third and most important is the route computation mechanism, which is integrated with a topology forecasting technique to construct up-to-date routes between the communication peers, aiming to achieve high delivery rate and increase the protocol robustness against the nodes' movement. FORTEL demonstrates higher performance as compared to other MANET's routing protocols, and it delivers up to 20% more packets than AODV and up to 60 % more than DSR and OLSR, while maintaining low levels of routing overhead and network delay at the same time. The effectiveness of the window update scheme is also discussed, and it proves to increase FORTEL's delivery rate by up to 30% as compared to the other update schemes. A common and frequently occurring phenomenon, in wireless networks, is the Hidden Terminal problem that significantly impacts the communication performance and the efficiency of the routing and MAC protocols. Beaconless routing approach in MANETs, which delivers data packets without prior knowledge of any sort `of information, suffers from packet duplication caused by the hidden nodes during the contention process. Moreover, the throughput of the IEEE MAC protocol decreases dramatically when the hidden terminal problem occurs. RTS/CTS mechanism fails to eliminate the problem and can further degrade the network's performance by introducing additional overhead. To tackle these challenges, this thesis presents two techniques, the Sender Suppression Algorithm and the Location-Aided MAC, where both rely on the nodes' position to eliminate packet duplication in the beaconless routing and improve the performance of the 802.11 MAC respectively. Both schemes are based on the concept of grouping the nodes into zones and assign different time delay to each one. According to the Sender Suppression Algorithm, the sender's forwarding area is divided into three zones, therefore, the local timer, set to define the time that the receiver has to wait before responding to the sender's transmission, is added to the assigned zone delay. Following the first response, the sender interferes and suppresses the receivers with active timer of. On the other hand, the Location-Aided MAC, essentially a hybrid MAC, combines the concepts of time division and carrier sensing. The radio range of the wireless receiver is partitioned into four zones with different zone delays assigned to each zone. Channel access within the zone is purely controlled by CSMA/CA protocol, while it is time-based amongst zones. The effectiveness of the proposed techniques is demonstrated through simulation tests. Location-Aided MAC considerably improves the network's throughput compared to CSMA/CA and RTS/CTS. However, remarkable results come when the proposed technique and the RTS/CTS are combined, which achieves up to 20% more throughput as compared to the standalone RTS/CTS. Finally, the thesis presents a novel link lifetime estimation method for greedy forwarding to compute the link duration between two nodes. Based on a newly introduced Stability-Aware Greedy (SAG) scheme, the proposed method incorporates the destination node in the computation process and thus has a significant advantage over the conventional method, which only considers the information of the nodes composing the link.

This thesis describes a stochastic ship routing problem with inventory management. The problem involves finding a set of least costs routes for a fleet of ships transporting a single commodity when the demand for the commodity is uncertain. Storage at consumption and supply ports is limited and inventory levels are monitored in the model. Consumer demands are at a constant rate within each time period in the deterministic problem, and in the stochastic problem, the demand rate for a period is not known until the beginning of that period. The demand situation in each time period can be described by a scenario tree with corresponding probabilities. Several possible solution approaches for solving the problem are studied in the thesis. This problem can be formulated as a mixed integer programming (MIP) model. However solving the problem this way is very time consuming even for a deterministic problem with small problem size. In order to solve the stochastic problem, we develop a decomposition formulation and solve it using a Branch and Price framework. A master problem (set partitioning with extra inventory constraints) is built, and the subproblems, one for each ship, involve solving stochastic dynamic programming problems to generate columns for the master problem. Each column corresponds to one possible tree of schedules for one ship giving the schedule for the ship for all demand scenarios. In each branch-and-bound node, the node problem is solved by iterating between the master problem and the subproblems. Dual variables can be obtained solving the master problem and are used in the subproblems to generate the most promising columns for the master problem. Computational results are given showing that medium sized problems can be solved successfully. Several extensions to the original model are developed, including a variable speed model, a diverting model, and a model which allows ships to do extra tasks in return for a bonus. Possible solution approaches for solving the variable speed and the diverting model are presented and computational results are given.

In the past decades, mobile traffic generated by devices such as smartphones, iphones, laptops and mobile gateways has been growing rapidly. While traditional direct connection techniques evolve to provide better access to the Internet, a new type of wireless network, mobile ad hoc network (MANET), has emerged. A MANET differs from a direct connection network in the way that it is multi-hopping and self-organizing and thus able to operate without the help of prefixed infrastructures. However, challenges such dynamic topology, unreliable wireless links and resource constraints impede the wide applications of MANETs. Routing in a MANET is complex because it has to react efficiently to unfavourable conditions and support traditional IP services. In addition, Quality of Service (QoS) provision is required to support the rapid growth of video in mobile traffic. As a consequence, tremendous efforts have been devoted to the design of QoS routing in MANETs, leading to the emergence of a number of QoS support techniques. However, the application independent nature of QoS routing protocols results in the absence of a one-for-all solution for MANETs. Meanwhile, the relative importance of QoS metrics in real applications is not considered in many studies. A Best Effort QoS support (BEQoS) routing model which evaluates and ranks alternative routing protocols by considering the relative importance of multiple QoS metrics is proposed in this thesis. BEQoS has two algorithms, SAW-AHP and FPP for different scenarios. The former is suitable for cases where uncertainty factors such as standard deviation can be neglected while the latter considers uncertainty of the problems. SAW-AHP is a combination of Simple Additive Weighting and Analytic Hierarchical Process in which the decision maker or network operator is firstly required to assign his/her preference of metrics with a specific number according to given rules. The comparison matrices are composed accordingly, based on which the synthetic weights for alternatives are gained. The one with the highest weight is the optimal protocol among all alternatives. The reliability and efficiency of SAW-AHP are validated through simulations. An integrated architecture, using evaluation results of SAW-AHP is proposed which incorporates the ad hoc technology into the existing WLAN and therefore provides a solution for the last mile access problems. The protocol selection induced cost and gains are also discussed. The thesis concludes by describing the potential application area of the proposed method. Fuzzy SAW-AHP is extended to accommodate the vagueness of the decision maker and complexity of problems such as standard deviation in simulations. The fuzzy triangular numbers are used to substitute the crisp numbers in comparison matrices in traditional AHP. Fuzzy Preference Programming (FPP) is employed to obtain the crisp synthetic weight for alternatives based on which they are ranked. The reliability and efficiency of SAW-FPP are demonstrated by simulations.

Many of the contemporary routing algorithms use simple mechanisms such as flooding or broadcasting to disseminate the routing information available to them. Such routing algorithms cause significant network resource overhead due to the large number of messages generated at each host/router throughout the route update process. Many of these messages are wasteful since they do not contribute to the route discovery process. Reducing the resource overhead may allow for several algorithms to be deployed in a wide range of networks (wireless and ad-hoc) which require a simple routing protocol due to limited availability of resources (memory and bandwidth). Motivated by the need to reduce the resource overhead associated with routing algorithms a new implementation of distance vector routing algorithm using an agent-based paradigm known as Agent-based Distance Vector Routing (ADVR) has been proposed. In ADVR, the ability of route discovery and message passing shifts from the nodes to individual agents that traverse the network, co-ordinate with each other and successively update the routing tables of the nodes they visit.

To ensure that services can be delivered reliably and continuously over theInternet, it is important that both Internet routes and edge networks aresecured. However, the sophistication and distributed nature of many at-tacks that target wide-area routing and edge networks make it difficult foran individual network, user, or router to detect these attacks. Thereforecollaboration is important. Although the benefits of collaboration betweendifferent network entities have been demonstrated, many open questionsstill remain, including how to best design distributed scalable mechanismsto mitigate attacks on the network infrastructure. This thesis makes severalcontributions that aim to secure the network infrastructure against attackstargeting wide-area routing and edge networks. First, we present a characterization of a controversial large-scale routinganomaly, in which a large Telecom operator hijacked a very large numberof Internet routes belonging to other networks. We use publicly availabledata from the time of the incident to understand what can be learned aboutlarge-scale routing anomalies and what type of data should be collected inthe future to diagnose and detect such anomalies. Second, we present multiple distributed mechanisms that enable col-laboration and information sharing between different network entities thatare affected by such attacks. The proposed mechanisms are applied in thecontexts of collaborating Autonomous Systems (ASes), users, and servers,and are shown to help raise alerts for various attacks. Using a combina-tion of data-driven analysis and simulations, based on publicly availablereal network data (including traceroutes, BGP announcements, and net-work relationship data), we show that our solutions are scalable, incur lowcommunication and processing overhead, and provide attractive tradeoffsbetween attack detection and false alert rates. Finally, for a set of previously proposed routing security mechanisms,we consider the impact of regional deployment restrictions, the scale of thecollaboration, and the size of the participants deploying the solutions. Al-though regional deployment can be seen as a restriction and the participationof large networks is often desirable, we find interesting cases where regionaldeployment can yield better results compared to random global deployment,and where smaller networks can play an important role in achieving bettersecurity gains. This study offers new insights towards incremental deploy-ment of different classes of routing security mechanisms.

The design and implementation of today's most advanced VLSI circuits and multi-layer printed circuit boards would not be possible without automated design tools that assist with the placement of components and the routing of connections between these components. In this work, we investigate how placement and routing can be implemented and accelerated using cloud computing resources. A parallel genetic algorithm approach is used to optimize component placement and the routing order supplied to a Lee's algorithm maze router. A study of mutation rate, dominance rate, and population size is presented to suggest favorable parameter values for arbitrary-sized printed circuit board problems. The algorithm is then used to successfully design a Microchip PIC18 breakout board and Micrel Ethernet Switch. Performance results demonstrate that a 50X runtime performance improvement over a serial approach is achievable using 64 cloud computing cores. The results further suggest that significantly greater performance could be achieved by requesting additional cloud computing resources for additional cost. It is our hope that this work will serve as a framework for future efforts to improve parallel placement and routing algorithms using cloud computing resources.

The focus of this work lies on the communication issues of Medium Access Control (MAC) and routing protocols in the context of WSNs. The communication challenges in these networks mainly result from high node density, low bandwidth, low energy constraints and the hardware limitations in terms of memory, computational power and sensing capabilities of low-power transceivers. For this reason, the structure of WSNs is always kept as simple as possible to minimize the impact of communication issues. Thus, the majority of WSNs apply a simple one hop star topology since multi-hop communication has high demands on the routing protocol since it increases the bandwidth requirements of the network. Moreover, medium access becomes a challenging problem due to the fact that low-power transceivers are very limited in their sensing capabilities. The first contribution is represented by the Backoff Preamble-based MAC Protocol with Sequential Contention Resolution (BPS-MAC) which is designed to overcome the limitations of low-power transceivers. Two communication issues, namely the Clear Channel Assessment (CCA) delay and the turnaround time, are directly addressed by the protocol. The CCA delay represents the period of time which is required by the transceiver to detect a busy radio channel while the turnaround time specifies the period of time which is required to switch between receive and transmit mode. Standard Carrier Sense Multiple Access (CSMA) protocols do not achieve high performance in terms of packet loss if the traffic is highly correlated due to the fact that the transceiver is not able to sense the medium during the switching phase. Therefore, a node may start to transmit data while another node is already transmitting since it has sensed an idle medium right before it started to switch its transceiver from receive to transmit mode. The BPS-MAC protocol uses a new sequential preamble-based medium access strategy which can be adapted to the hardware capabilities of the transceivers. The protocol achieves a very low packet loss rate even in wireless networks with high node density and event-driven traffic without the need of synchronization. This makes the protocol attractive to applications such as structural health monitoring, where event suppression is not an option. Moreover, acknowledgments or complex retransmission strategies become almost unnecessary since the sequential preamble-based contention resolution mechanism minimizes the collision probability. However, packets can still be lost as a consequence of interference or other issues which affect signal propagation. The second contribution consists of a new routing protocol which is able to quickly detect topology changes without generating a large amount of overhead. The key characteristics of the Statistic-Based Routing (SBR) protocol are high end-to-end reliability (in fixed and mobile networks), load balancing capabilities, a smooth continuous routing metric, quick adaptation to changing network conditions, low processing and memory requirements, low overhead, support of unidirectional links and simplicity. The protocol can establish routes in a hybrid or a proactive mode and uses an adaptive continuous routing metric which makes it very flexible in terms of scalability while maintaining stable routes. The hybrid mode is optimized for low-power WSNs since routes are only established on demand. The difference of the hybrid mode to reactive routing strategies is that routing messages are periodically transmitted to maintain already established routes. However, the protocol stops the transmission of routing messages if no data packets are transmitted for a certain time period in order to minimize the routing overhead and the energy consumption. The proactive mode is designed for high data rate networks which have less energy constraints. In this mode, the protocol periodically transmits routing messages to establish routes in a proactive way even in the absence of data traffic. Thus, nodes in the network can immediately transmit data since the route to the destination is already established in advance. In addition, a new delay-based routing message forwarding strategy is introduced. The forwarding strategy is part of SBR but can also be applied to many routing protocols in order to modify the established topology. The strategy can be used, e.g. in mobile networks, to decrease the packet loss by deferring routing messages with respect to the neighbor change rate. Thus, nodes with a stable neighborhood forward messages faster than nodes within a fast changing neighborhood. As a result, routes are established through nodes with correlated movement which results in fewer topology changes due to higher link durations. / Im Rahmen dieser Arbeit werden leistungsbeschränkende Faktoren von Medium Access Control (MAC) und Routingprotokollen im Kontext von drahtlosen Sensornetzen untersucht. Zunächst werden typische Probleme des Funkkanals diskutiert. Anschließend führen eine Einteilung von MAC Protokollen, sowie eine Gegenüberstellung relevanter Protokolle in die Thematik ein. Daraufhin werden hardwarelimitierende Faktoren und deren Auswirkung auf die Effizienz von Kanalzugriffsprotokollen untersucht. Des Weiteren wird das vom Autor entwickelte Backoff Preamble-based MAC Protokoll (BPS-MAC) vorgestellt, welches auf die limitierten Fähigkeiten sensortypischer Hardware eingeht und für dichte Sensornetze mit korreliertem Datenverkehr optimiert ist. Ein weiterer Schwerpunkt dieser Arbeit stellt das Thema Routing dar. Hier wird ebenfalls mit einer Einteilung der Protokolle in die Thematik eingeführt. Darüber hinaus werden die wichtigsten Aufgaben von Routingprotokollen vorgestellt. Ein Überblick über häufig verwendete Routingmetriken und Routingprotokolle schließen die Einführung in diesen Themenkomplex ab. Abschließend wird das im Rahmen der Dissertation entwickelte Statistic-Based-Routing (SBR) Protokoll vorgestellt, welches ebenfalls für drahtlose Sensornetze optimiert ist. Der letzte Schwerpunkt beschreibt die Problematik der Leistungsbewertung von Routingprotokollen hinsichtlich klassischer Leistungsparameter wie Paketverlust und Verzögerung. Ebenfalls werden weitere Leistungsparameter wie zum Beispiel die vom Nutzer wahrgenommene Netzqualität genauer untersucht.

O presente trabalho trata da determinação de um roteiro ótimo de separação manual de peças em armazéns, buscando a minimização da distância total percorrida. São considerados armazéns com dois corredores transversais localizados em suas extremidades, os quais conectam todos os corredores de separação, perpendiculares aos corredores transversais e paralelos entre si. O problema abordado é prático e comum a várias empresas, com impacto nos custos operacionais e relevância para a assertividade em relação aos itens coletados. Ainda assim, o tema é pouco explorado nos estudos de roteirização disponíveis em língua portuguesa e muitas empresas optam por confiar a criação das rotas aos próprios separadores. O método escolhido é baseado em programação dinâmica e foi aplicado na roteirização de listas de separação relacionadas a subconjuntos do produto final, na roteirização de grupos aleatórios de peças, e no estudo do impacto do número de corredores de separação no comprimento das rotas, totalizando 184 experimentos. A forma de avaliação do algoritmo foi comparar as rotas por ele criadas com aquelas criadas pelos separadores. Conclui-se que quanto mais complexa for a rota, maiores serão os ganhos da seqüência de coletas proposta pelo sistema em comparação com aquelas criadas por processos subjetivos. Concluiu-se também que o número de corredores a ser visitado é o fator que mais influencia no comprimento da rota a ser percorrida. Ainda, o algoritmo é flexível e genérico para ser utilizado em qualquer armazém com dois corredores transversais, independente da política de localização ou separação adotada e, por sua facilidade de implementação e utilização, representa uma alternativa de roteirização eficiente e de baixo custo para pequenas e médias empresas. Finalmente, tem-se um algoritmo que pode ser utilizado também como ferramenta gerencial e de simulação visto que pode ser configurado para diferentes leiautes e diferentes tamanhos listas de separação. / The present work deals with the shortest route creation for a low-level pickers-to-part warehouse, intending to minimize the total traveled distance. The considered warehouse has two traversing aisles, located in its extremities, connecting all of the picking aisles and perpendicularly set in relation to them. The proposed problem is practical and common to several companies, impacting their operational costs and important for mis picking reduction. Nevertheless, that theme is little explored among routing studies in Portuguese language and several companies still opt to trust the routes to be subjectively prepared by their own pickers. The proposed solution method is based on dynamic programming and it was applied in the routing of picking lists related to subsets of final products, random groups of items, and in the study of the impact that picking aisle quantity has on the total length of the routes, totaling 184 experiments. The proposed algorithm was evaluated comparing the routes prepared by it with those created by the pickers. Results show that the more complex the route is, the higher the earnings of the algorithm utilization in relation to the subjective processes will be. Besides it shows that the number of corridors to be visited is the main influence to the length of the route. Still, the algorithm is flexible and generic to be used at any warehouse with two traverse corridors, independent of the locating police or separation strategy adopted. Furthermore the algorithm implementation easiness and use support it to be an efficient low cost routing alternative for small and average size companies.