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

该补助金提供资金用于开发有效解决二次三维分配问题（Q3AP）的算法，这是一个困难的组合优化问题，出现在广泛的复杂数字无线通信系统的设计中。 第一项工作将是改进一个分支定界算法的基础上，1级重新制定线性化技术（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.