A Distributed Constraint Satisfaction Problem (DisCSP) is a CSP which is divided into several inter-related complex local problems, each assigned to a different agent. Thus, each agent has knowledge of the variables and corresponding domains of its local problem together with the constraints relating its own variables (intra-agent constraints) and the constraints linking its local problem to other local problems (inter-agent constraints). DisCSPs have a variety of practical applications including, for example, meeting scheduling and sensor networks. Existing approaches to Distributed Constraint Satisfaction can be mainly classified into two families of algorithms: systematic search and local search. Systematic search algorithms are complete but may take exponential time. Local search algorithms often converge quicker to a solution for large problems but are incomplete. Problem solving could be improved through using hybrid algorithms combining the completeness of systematic search with the speed of local search. This thesis explores hybrid (systematic + local search) algorithms which cooperate to solve DisCSPs. Three new hybrid approaches which combine both systematic and local search for Distributed Constraint Satisfaction are presented: (i) DisHyb; (ii) Multi-Hyb and; (iii) Multi-HDCS. These approaches use distributed local search to gather information about difficult variables and best values in the problem. Distributed systematic search is run with a variable and value ordering determined by the knowledge learnt through local search. Two implementations of each of the three approaches are presented: (i) using penalties as the distributed local search strategy and; (ii) using breakout as the distributed local search strategy. The three approaches are evaluated on several problem classes. The empirical evaluation shows these distributed hybrid approaches to significantly outperform both systematic and local search DisCSP algorithms. DisHyb, Multi-Hyb and Multi-HDCS are shown to substantially speed-up distributed problem solving with distributed systematic search taking less time to run by using the information learnt by distributed local search. As a consequence, larger problems can now be solved in a more practical timeframe.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

1 / Brittan Rosendahl

No description available.

The problem of the efficient use of Hybrid Automatic-Repeat-reQuest (Hybrid-ARQ) in wireless communication has attracted a considerable amount of research. In this thesis, the use and implementation of turbo codes as the Forward Error Correction (FEC) code for Hybrid-ARQ is investigated. The major accomplishments of the research include both the analysis and implementation of turbo Hybrid-ARQ. The thesis begins by obtaining a tractable bound for the performance of turbo codes with M-ary Quadrature-Amplitude-Modulation (M-ary QAM). The research considers the design problem of turbo coded Hybrid-ARQ optimized for AWGN and fading channels. The design problem of turbo Hybrid-ARQ in wideband channels is considered and an optimization strategy is proposed based on Orthogonal-Frequency-Division- Multiplexing (OFDM). The research also presents a novel rate scalable encoder structure that optimal selects a disparate but optimal pair of component codes given the channel conditions. A second part of the thesis considers the implementation of turbo Hybrid-ARQ in Very Large Scale Integration (VLSI ) systems. A design for a single architecture for Type-I and Type-II turbo Hybrid-ARQ is suggested in addition to approaches for improving performance of the Soft-Output-Viterbi-Algorithm(SOVA) decoder core. The research also proposes a SOVA decoder architecture that exploits reliability information to select between the SOVA and bi-directional SOVA.