In the past few years Wireless Mesh Networks (WMNs) have developed as a promising technology to provide flexible and low-cost broadband network services. The Expected Transmission Count (ETX) routing metric has been put forward recently as an advanced routing metric to provide high QoS for static WMNs. Most previous research in this area suggests that ETX outperforms other routing metrics in throughput and efficiency. However, it has been determined that ETX is not immune to load sensitivity and route oscillations in a single radio environment. Route oscillations refer to the situation where packet transmission switches between two or more routes due to congestion. This has the effect of degrading performance of the network, as the routing protocol may select a non optimal path. In this thesis we avoided the route oscillation problem by forcing data transmission on fixed routes. This can be implemented in the AODV (Ad hoc On-demand Distance Vector) protocol by disabling both error messages and periodic updating messages (the HELLO scheme). However, a critical factor for our approach is that ETX must determine a high quality initial route in AODV. This thesis investigates whether the ETX metric improves initial route selection in AODV compared to the HOPS metric in two representative client-server applications: the Traffic Control Network (TCN) and the Video Stream (VS) network. We evaluate the ETX and HOPS metrics in a range of scenarios which possess different link qualities and different traffic loads. We find the ETX metric greatly improves initial route selection in AODV compared to the HOPS in the network in which only single flow exists. For networks in which there are multiple simultaneous flows, ETX behaves similar to HOPS in initial route selection. Based on these results, we find the solution of route stabilization to route oscillations in the context of ETX is only useful in the single flow case. To address this problem, we propose a modified solution of repeatedly broadcasting RREQ (Route Request) packets. Simulation results show that our modified solution allows ETX to be useful in the initial route selection in both single flow and multiple simultaneous flows cases.

This dissertation reports on studies of the application of lexicographic graph searches to solve problems in FPGA detailed routing. Our contributions include the derivation of iteration limits for scalar implementations of negotiation congestion for standard floating point types and the identification of pathological cases for path choice. In the study of the routability-driven detailed FPGA routing problem, we show universal detailed routability is NP-complete based on a related proof by Lee and Wong. We describe the design of a lexicographic composition operator of totally-ordered monoids as path cost metrics and show its optimality under an adapted A* search. Our new router, CornNC, based on lexicographic composition of congestion and wirelength, established a new minimum track count for the FPGA Place and Route Challenge. For the problem of long-path timing-driven FPGA detailed routing, we show that long-path budgeted detailed routability is NP-complete by reduction to universal detailed routability. We generalise the lexicographic composition to any finite length and verify its optimality under A* search. The application of the timing budget solution of Ghiasi et al. is used to solve the long-path timing budget problem for FPGA connections. Our delay-clamped spiral lexicographic composition design, SpiralRoute, ensures connection based budgets are always met, thus achieves timing closure when it successfully routes. For 113 test routing instances derived from standard benchmarks, SpiralRoute found 13 routable instances with timing closure that were unroutable by a scalar negotiated congestion router and achieved timing closure in another 27 cases when the scalar router did not, at the expense of increased runtime. We also study techniques to improve SpiralRoute runtimes, including a data structure of a trie augmented by data stacks for minimum element retrieval, and the technique of step tomonoid elimination in reducing the retrieval depth in a trie of stacks structure.

This thesis identifies some problems, the genetic algorithm (GA) is facing in the area of vehicle routing and proposes various methods to address those problems. Those problems arise from the unavailability of suitable chromosomal representation and evaluation schemes of GA for the Vehicle Routing Problem (VRP). The representation and evaluation schemes already in use have problems of high computational cost, illegal chromosomes (chromosomes not representing a legal tour) and wrong fitness assignment (fitness not truly representing chromosome genetic makeup). These problems are addressed by several proposed new schemes, namely the Self Imposed Constraints Evaluation scheme, the Contour and Reverse Contour Evaluation schemes and the Order Skipping Evaluation scheme, which are specifically tailored for various objectives, problems and situations. Apart from this, a methodology, which has previously being used in other meta-heuristics, is incorporated into GA i.e., the independent application of GA on various sub-localities of the problem. We call this GA, a Localized Genetic Algorithm (LGA). LGA is an iterative procedure between optimization and controlled de-optimization. The procedure of controlled de-optimization is also novel. It brings the solution into a new search space while controlling its cost effectively. LGA is introduced with various search techniques, i.e. intensive, extensive and selective, the use of which depends on the problem size and the availability of computational resources. Furthermore, search reduction techniques (Fitness Approximation Methods) are also introduced into the LGA, which has enabled the LGA to be applied to large scale problems. Due to the implementation of those proposals, LGA is the first GA-driven approach to be applied to very large scale CVRP problems of up to 1200 customers, i.e. datasets presented by Feiyue in 2005 and large scale VRPTW problems of up to 1000 customers, datasets presented by Gehring and Homberger in 1999. Lastly, a standard unit for computational comparison, i.e., Bellman's Evaluation Units BEUs, is also introduced to facilitate computational comparisons for future researchers. LGA has shown promising results on CVRP and VRPTW problems. It is flexible and also has the potential to be extended to not only other vehicle routing problems, but also to other ordering problems.

Universiẗat, Diss., 2006--Trier.

Thesis (Ph. D.)--Washington State University, December 2007. / Includes bibliographical references (p. 156-164).

Thesis (M.S.)--Rochester Institute of Technology, 2007. / Typescript. Includes bibliographical references (leaves 49-50).

Zugl.: Zürich, Techn. Hochsch., Diss., 2008

Thesis (MSc)--University of Stellenbosch, 2007. / Bibliography. Also available via the Internet.

Thesis (Ph. D.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Computer Science, 2007. / Includes bibliographical references.

Thesis (M.S.)--California Polytechnic State University, 2009. / Title from PDF title page; viewed on June 18, 2009. Major professor: Hugh Smith, Ph.D. "Presented to the faculty of California Polytechnic State University, San Luis Obispo." "In partial fulfillment of the requirements for the degree [of] Master of Science in Computer Science." "June 2009." Includes bibliographical references (p. 55-56). Also available on microfiche.