NeTS: Small: Multicommodity Flows in Multihop Wireless Networks

多商品流，或简称多流，是所有类型的通信网络(无论是有线还是无线)的中心话题。在多跳无线网络中计算最大(并发)多流特别具有挑战性，因为通信链路的容量不是固定的，而是随基础链路调度而变化的。因此，唯一的挑战是如何计算服从无线干扰约束的链路调度，该无线干扰约束导致支持最大(并发)多流的链路容量函数。该项目建立了多跳无线网络中计算最大(并发)多流的计算难度和近似难度，并开发了具有良好性能的实用近似算法。该项目采用多面体方法构造多跳无线网络的各种多项式近似容量子域。这些近似的容量子域不仅是计算最大(并发)多流的算法基础，而且也是未来关于网络容量以及多跳无线网络中的跨层设计和优化的有趣项目的基础。它们也是广大理论计算机科学界的独立利益所在。该项目为研究生提供奖学金，并为多跳无线网络上的优秀论文工作提供研究主题。该项目的成果不仅将通过期刊和会议记录传播给专业研究人员，而且还将纳入针对高年级本科生和研究生的课堂讲稿。

Multicommodity flows, or multiflows in short, are central topics in all types of communication networks, whether wired or wireless. Computing a maximum (concurrent) multiflow in multihop wireless networks is particularly challenging because the capacities of the communication links, rather than being fixed, vary with the underlying link schedule. A unique challenge is thus how to compute a link schedule subject to the wireless interference constraint which induces a link capacity function supporting a maximum (concurrent) multiflow. This project establishes both the computational hardness and approximation hardness of computing maximum (concurrent) multiflows in multihop wireless networks, and develops practical approximation algorithms with provably good performance. A polyhedral approach is taken by the project to construct various polynomial approximate capacity subregions of multihop wireless networks. These approximate capacity subregions not only are the algorithmic foundation of the computing maximum (concurrent) multiflows, but also serve as a basis for interesting future projects on network capacity and cross-layer design and optimizations in multihop wireless networks. They are also of independent interest to the theoretical computer science community at large. This project provides scholarships to graduate students and offers research topics for strong dissertation works on multihop wireless networks. The outcome of this project will not only be disseminated to the professional researchers through journals and conference proceedings, but also be integrated into the lecture notes targeted for senior undergraduate students and graduate students.