This grant provides funding for the development of algorithms for efficient solution of the Quadratic 3-dimensional Assignment Problem (Q3AP), a difficult combinatorial optimization problem that arises in the design of a broad class of sophisticated digital wireless communication systems. The first effort will be improving a branch-and-bound algorithm based on the level-1 Reformulation Linearization Technique (RLT) formulation. Considerations to be addressed include computational strategies, choice of branching rules, frequency of bound computations, and the methods for data storage and retrieval. Additionally, investigations of heuristic solution methods including Tabu Search, Iterated Local Search, and Simulated Annealing will be pursued. Two focal points of this project are code parallelization and communication application generation. Parallelizing will allow larger problem instances to be solved, but will also permit rapid experimentation with alternatives to the sequential structure of enumerative and heuristic algorithms. Communication applications will be generated to assure adequate algorithm performance testing.
The Q3AP is one of the most difficult combinatorial optimization problems yet posed. If successful, the Q3AP will be solved for practical problem instances involving a symbol-mapping diversity scheme for wireless communication nodes that employ higher-order modulations such as phase-shift keying (PSK) or quadrature amplitude modulation (QAM). By varying the bit-to-symbol mapping in hybrid Automatic Repeat request (ARQ) packet (re) transmission by each communication node, the frame error rate and the average number of packet retransmissions will be dramatically reduced, thereby enhancing the capabilities of the target communication network. Wireless sensor networks typically operate in noisy, channel-distorting, and interference-laden environments and thus are targets for the optimizations pursued. The practicality of this framework becomes evident, as the optimal mapping only needs to be found for various signal to noise ratio (SNR) under a few common fading scenarios. Once determined, any practical system can implement the resulting optimal mapping through a simple lookup table.
