Time: 2016-07-15 10:00-12:00
Venue: 1-415, FIT Building, Tsinghua
Full exploitation of the capacity of a general multi-hop multi-radio multi-channel wireless network requires joint optimization of routing at network layer, scheduling at link layer, and system configuration at physical layer, involving a variety of resources such as link, radio, channel, transmission power, and antenna configuration. Such a joint optimization problem is very challenging; note that optimization in the simplest single-radio single-channel (SR-SC) context is NP-hard in general. In this talk, we first introduce a novel concept of multi-dimensional conflict graph (MDCG), where each vertex represents a resource point in a multi-dimensional resource space. Based on the MDCG, the joint optimization problem over a MR-MC wireless network can be compactly formulated as a multi-commodity flow (MCF) problem augmented with the maximal independent set (MIS) based scheduling, under either the protocol interference model or the physical interference model. Such an MCF problem can be effectively solved with the delayed column generation (DCG) method, and the solution will provide not only the maximum throughput or utility, but also the associated optimal resource allocation in the multi-dimensional resource space. One fundamental contribution is that we theoretically analyze the capacity approximation ratio for the DCG-based algorithm. Furthermore, the multi-dimensional resource framework enables a virtual single-radio single-channel (SR-SC) model, under which the throughput-optimal control and cross-layer optimization of a MR-MC wireless network can be rigorously formulated and studied.
Yu Cheng received the B.E. and M.E. degrees in Electronic Engineering from Tsinghua University, Beijing, China, in 1995 and 1998, respectively, and the Ph.D. degree in Electrical and Computer Engineering from the University of Waterloo, Waterloo, Ontario, Canada, in 2003. From September 2004 to July 2006, he was a postdoctoral research fellow in the Department of Electrical and Computer Engineering, University of Toronto, Ontario, Canada. Since August 2006, he has been with the Department of Electrical and Computer Engineering, Illinois Institute of Technology, Chicago, Illinois, USA, and he is now an Associate Professor. His research interests include next-generation Internet architectures and management, wireless network performance analysis, network security, and wireless/wireline interworking. He received a Postdoctoral Fellowship Award from the Natural Sciences and Engineering Research Council of Canada (NSERC) in 2004, a Best Paper Award from the conferences QShine 2007 and ICC 2011, and Best Paper Runner-up award from ACM MobiHoc 2014. He received the National Science Foundation (NSF) CAREER AWARD in 2011 and IIT Sigma Xi Research Award in the junior faculty division in 2013. He served as symposium co-chairs in GLOBECOM 2011 and 2013, and ICC 2009, 2012, and 2016. He served as a Technical Program Committee (TPC) Co-Chair for WASA 2011, ICNC 2015, and IEEE/CIC ICCC 2015. He is a founding Vice Chair of the IEEE ComSoc Technical Subcommittee on Green Communications and Computing. He is an Associated Editor for IEEE Transactions on Vehicular Technology and the New Books & Multimedia Column Editor for IEEE Network.