主题：Maximizing Throughput in Multi-Channel Multi-Radio Multihop Wireless Networks
时间：2018年5月18日（星期五）上午10：30
地点：学术会议中心301
主办单位：计算机与网络安全学院、无线智能网络实验室
报告人简介：
Dr. Zhu Wang is currently a tenure-track Assistant Professor of Computer Science at State University of New York at Oneonta, USA. His research interest lies in wireless networks, algorithm design and analysis. He received his Ph.D. degree in Computer Science from Illinois Institute of Technology in 2014. He also holds a Bachelor’s degree in Computer Science from Beijing University of Aeronautics and Astronautics in 2005 and a Master’s degree in Management from Peking University in 2007. He has published 14 papers during recent years, mainly in top-tier international conferences and journals in the area of computer networks and data communications, such as ACM MobiHoc and IEEE INFOCOM. He is a member of IEEE and ACM.
报告内容摘要：
Maximizing Throughput in Multi-Channel Multi-Radio Multihop Wireless Networks
Maximizing throughput in multi-channel multi-radio (MC-MR) multihop wireless networks is not only of theoretical interest, but also of great practical importance. Maximum multiflow in MC-MR multihop wireless networks has been well-studied in the literature. It is NP-hard but admits a polynomial-time approximation scheme (PTAS) when the number of channels is bounded by a constant. However, such PTAS is quite infeasible practically. Other than the PTAS, all other known approximation algorithms, in both single-channel single-radio (SC-SR) wireless networks and MC-MR wireless networks, resorted to solve some polynomial-sized linear program (LP) exactly. The scalability of their running time is fundamentally limited by the general-purposed LP solvers. This talk will first introduce related background knowledge of MC-MR multihop wireless, then explore the concept of interference cost of a path and the relations between the least interference-cost paths and the maximum multiflow. Finally, a purely combinatorial approximation algorithm will be presented which computes successively a sequence of least interference-cost paths as well as the flow amounts routed along them. This algorithm is faster and simpler, and achieves nearly the same approximation bounds known in the literature.
