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.

Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 180-187).

Underwater sensor networks find applications in oceanographic data collection, pollution monitoring, offshore exploration, disaster prevention, assisted navigation, tactical surveillance, and mine reconnaissance. The enabling technology for these applications is acoustic wireless networking. UnderWater Acoustic Sensor Networks (UW-ASNs) consist of sensors and Autonomous Underwater Vehicles (AUVs) deployed to perform collaborative monitoring tasks. The objective of this research is to explore fundamental key aspects of underwater acoustic communications, propose communication architectures for UW-ASNs, and develop efficient sensor communication protocols tailored for the underwater environment. Specifically, different deployment strategies for UW-ASNs are studied, and statistical deployment analysis for different architectures is provided. Moreover, a model characterizing the underwater acoustic channel utilization efficiency is introduced. The model allows setting the optimal packet size for underwater communications. Two distributed routing algorithms are proposed for delay-insensitive and delay-sensitive applications. The proposed routing solutions allow each node to select its next hop, with the objective of minimizing the energy consumption taking the different application requirements into account. In addition, a resilient routing solution to guarantee survivability of the network to node and link failures in long-term monitoring missions is developed. Moreover, a distributed Medium Access Control (MAC) protocol for UW-ASNs is proposed. It is a transmitter-based code division multiple access scheme that incorporates a novel closed-loop distributed algorithm to set the optimal transmit power and code length. It aims at achieving high network throughput, low channel access delay, and low energy consumption. Finally, an efficient cross-layer communication solution tailored for multimedia traffic (i.e., video and audio streams, still images, and scalar sensor data) is introduced.

Thesis (M.S.)--Kent State University, 2009. / Title from PDF t.p. (viewed Jan. 25, 2010). Advisor: Feodor Dragan. Keywords: greedy routing. Includes bibliographical references (p. 76-77).

M. Tech. Electrical Engineering. / Discusses the question of how to prolong the life of an entire sensor network by reducing the power consumption is the most important issue in wireless sensor networks. Traditional routing schemes have not fulfilled the expectations of an optimised WSN, and as a result, new algorithms are being designed globally. One of these protocols which serve as a basis for this study is the RCRR. In this project, we present a new approach of the Relative Coordinates Rumor Routing algorithm based on a link quality awareness scheme and a modified version of the protocol with better scaling.The benefits of this study are: Proposal of a tuneable algorithm that will not only consume less power compared to the classic RR but also addresses the scalability problem encountered with the original RCRR. Proposal a better trade-off between throughput and average end-to-end delay with the use of the SMAC (compared with Rumor protocol). Avoidance of long delays in queues and saving power on retransmission of packets. Reduction of the wandering of agents during communication. Prolonging the lifetime of the network and thus offering economic, operational, and environmental benefits. Balancing link quality awareness with a topological localisation scheme to achieve better throughput.

M. Tech. Electrical Engineering. / Wireless sensor networks (WSNs) are considered to be the next generation network after the Internet. However the limited energy supply is still a serious restriction for them. Hence energy consumption is a key design criterion for the routing protocol in WSNs. Gradient-based routing (GBR) is an energy efficient routing protocol for WSNs. However, shortcomings exist in the GBR scheme, such as: (1) nodes deliver the message in a point to point manner and do not use the broadcast nature of wireless networks; (2) the nodes which are near the sink will be overused; (3) sinks use flooding to broadcast the interest messages, and hence, many duplicated packets are transmitted. To address these shortcomings, three algorithms are presented according to the problems identified above. Firstly, a competing algorithm GBR-C is proposed. Simulation results showed that GBR-C provided better results than GBR in terms of energy efficiency. Secondly, a refilling algorithm GBR-R is proposed. The simulation results revealed that compared to GBR, network lifetime was prolonged up to 63% with the GBR-R algorithm. Thirdly, a network coding algorithm, GBR-NC, is proposed. Simulation results showed that compared with GBR, GBR-NC could save up to 60% of energy when the network coding scheme N of 4 is used.

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.

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).

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