Hybrid ARQ Symbol Mapping In Digital Wireless Communication Systems Based on the Quadratic 3-Dimensional Assignment Problem (Q3AP)

该拨款为有效解决二次三维分配问题（Q3AP）的算法开发提供资金，二次三维分配问题是在设计广泛的复杂数字无线通信系统时出现的一个困难的组合优化问题。首先将改进基于一级重构线性化技术（RLT）公式的分支定界算法。需要考虑的因素包括计算策略、分支规则的选择、绑定计算的频率以及数据存储和检索的方法。此外，还将研究启发式求解方法，包括禁忌搜索、迭代局部搜索和模拟退火。这个项目的两个重点是代码并行化和通信应用程序生成。并行化将允许解决更大的问题实例，但也允许对枚举和启发式算法的顺序结构的替代方案进行快速实验。将生成通信应用程序，以确保充分的算法性能测试。Q3AP是目前最困难的组合优化问题之一。如果成功，Q3AP将解决涉及符号映射分集方案的实际问题实例，无线通信节点采用高阶调制，如相移键控（PSK）或正交调幅（QAM）。通过改变每个通信节点在混合ARQ （Automatic Repeat request，自动重复请求）分组重传中的位-符号映射，可以显著降低帧错误率和分组重传的平均次数，从而提高目标通信网络的性能。无线传感器网络通常在噪声、信道失真和干扰环境中运行，因此是追求优化的目标。该框架的实用性是显而易见的，因为只需要在几种常见的衰落情况下找到各种信噪比（SNR）的最优映射。一旦确定，任何实际系统都可以通过一个简单的查找表实现最终的最优映射。

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.