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

无线网络中的多流问题解决了通过多个端到端通信请求以最大容量传输业务需求的问题。最先进的解决多流问题的方法需要过多的计算资源，因此在实践中往往被证明是不可用的。该项目为多通道多无线电无线网络中的多流问题探索了一种全新的范例，并开发出更快、更简单的实用算法解决方案，提供精度和效率之间的量化权衡。新范式在无线网络以外的领域有着广泛的应用，并为未来有关网络容量和无线网络跨层设计和优化的有趣项目奠定了基础。由于跨层的性质，无线网络中的多流问题构成了独特而重大的挑战。在现有的无线网络中多流问题的研究中，表征计算难度和解决可达近似界的策略一直是优先考虑的问题。事实上，无线网络中多流问题的最新近似算法都是集中的，完全依赖于传统的线性规划(LP)方法。然而，即使对于中等大小的输入，这些传统的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.