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

这笔赠款为有效解决二次型三维分配问题(Q3AP)的算法开发提供资金，Q3AP是在设计一大类复杂的数字无线通信系统时出现的一个困难的组合优化问题。第一项工作将是改进基于一级重构线性化技术(RLT)公式的分支定界算法。要考虑的问题包括计算策略、分支规则的选择、界限计算的频率以及数据存储和检索的方法。此外，还将继续研究启发式求解方法，包括禁忌搜索、迭代局部搜索和模拟退火法。该项目的两个重点是代码并行化和通信应用程序生成。并行化将允许解决更大的问题实例，但也将允许快速试验枚举和启发式算法的顺序结构的替代方案。Q3AP是目前提出的最困难的组合优化问题之一。如果成功，Q3AP将被用于涉及用于采用诸如相移键控(PSK)或正交幅度调制(QAM)等高阶调制的无线通信节点的符号映射分集方案的实际问题实例。通过改变每个通信节点在混合自动重传请求(ARQ)分组重传中的比特到符号的映射，将显著降低误帧率和分组重传的平均次数，从而增强目标通信网络的能力。无线传感器网络通常工作在噪声、信道失真和充满干扰的环境中，因此是进行优化的目标。该框架的实用性是显而易见的，因为在一些常见的衰落场景下，只需要为各种信噪比(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.