On Throughput Optimal Routing and Scheduling in Wireless Networks: Feedback and Complexity

Event Date: May 19, 2008
Speaker: Dr. Lei Ying
Speaker Affiliation: Iowa State University
Sponsor: CNSIP Area Seminar
Time: 10:30 AM
Location: MSEE 239
Contact Name: Prof Xiaojun Lin
Contact Phone: (765) 494-0626
Contact Email: linx@purdue.edu

Wireless networks provide an extremely flexible way to establish communication, and are envisioned for use in a variety of applications. These applications can range over a diverse set of configurations --- citywide mesh networks, structured cellular deployments for mobile users, and ad-hoc battlefield networks. Intelligent scheduling and routing algorithms are demanded in all these networks to support high-quality communication. First proposed by Tassiulas and Ephremides, the back pressure algorithm is a throughput-optimal routing/scheduling algorithm, i.e., if any routing/scheduling algorithm can support a set of traffic flows, then the back pressure algorithm can as well.  Although extremely simple, the back pressure algorithm suffers serious drawbacks: (i) it requires perfect Network (channel and queue) State Information (NSI); and (ii) it requires the maintenance of one queue per
destination at every node.
In today’s talk, I will first address the problem of routing/scheduling in a wireless network with delayed NSI. I will characterize the optimal network throughput region, and then propose throughput-optimal routing/scheduling algorithms based on delayed NSI. Then I will introduce the cluster-based back pressure algorithm, which retains the throughput optimality and adaptability of the back pressure algorithm, while significantly reducing the number of queues that have to be maintained at each node.
Lei Ying received his B.E. degree from Tsinghua University, Beijing, in 2001, his M.S. and Ph.D in Electrical Engineering from the University of Illinois at Urbana-Champaign in 2003 and 2007, respectively. During Fall 2007, he worked as a Postdoctoral fellow in the University of Texas at Austin.  He is currently an Assistant Professor at the Department of Electrical and Computer Engineering at Iowa State University. 
His research interests are in the field of communication networks, including wireless communication networks, wireless sensor networks, and distributed algorithms.