A New Paradigm for Multiflow in MC-MR Wireless Networks: Theoretic Foundations And Practical Algorithms

无线网络中的多流问题是指在最大容量下通过多个端到端通信请求来解决流量需求的传输问题。最先进的解决多流问题的方法需要大量的计算资源，因此在实践中往往被证明是不可用的。该项目为多通道多无线电无线网络中的多流问题探索了一个全新的范例，并开发了更快、更简单的实用算法解决方案，在准确性和效率之间提供了量化的权衡。新范式在无线网络以外的领域具有广泛的应用，并可作为无线网络中网络容量和跨层设计和优化的有趣未来项目的基础。由于跨层的特性，无线网络中的多流问题提出了独特而重大的挑战。在现有的无线网络多流问题研究中，确定计算硬度和解决可实现近似边界的策略一直是重点。事实上，无线网络中多流问题的最先进的近似算法都是集中的，并且完全依赖于传统的线性规划方法。然而，即使对于中等大小的输入，这些传统的LP方法也需要大量的运行时间和内存，因此在实践中往往证明它们是不可用的。此外，传统LP方法的集中性使其不适合开发分布式网络协议。该项目探索了多通道多无线电无线网络中多流问题的新范式，该范式不同于流行的基于lp的范式，并开发了更快、更简单的实用算法解决方案。

The multiflow problems in wireless networks address the transportation of traffic demands by multiple end-to-end communication requests at the maximum capacity. State-of-the-art methods of solving the multiflow problems require an excessive amount of computational resources, and consequently often prove unusable in practice. This project explores a completely new paradigm for multiflow problems in multi-channel multi-radio wireless networks and develops much faster and simpler practical algorithmic solutions that offer quantified trade-off between accuracy and efficiency. The new paradigm has wide applications in domains beyond wireless networks, and serves as a basis for interesting future projects on network capacity and cross-layer design and optimizations in wireless networks.Due to the cross-layer nature, multiflow problems in wireless networks pose unique and significant challenges. Characterizing computational hardness and strategies for resolving achievable approximation bounds have been the priority in existing studies of multiflow problems in wireless networks. In fact, state-of-the-art approximation algorithms for multiflow problems in wireless networks are all centralized and rely upon traditional linear programming (LP) methods exclusively. However, these traditional LP methods require an inordinate amount of running time and memory even for a moderate sized input, and consequently they often prove unusable in practice. Furthermore, the centralized nature of traditional LP methods make them unsuitable for developing distributed network protocols. This project explores a new paradigm for multiflow problems in multi-channel multi-radio wireless networks that is different from the prevailing LP-based paradigm, and develops practical algorithmic solutions that are much faster and simpler.