Project Title

Generalized MaxWeight Algorithms over Non-Convex Rate Regions in Wireless Networks with Multiple Antennas

Project Summary

Computing the capacity region of wireless networks is the holy grail of network information theory. Even though fundamental progress has been achieved recently, the problem still awaits its fundamental solution.

In this research proposal a new approach using Generalized MaxWeight routing and scheduing policies is introduced and investigated. The standard MaxWeight policy invented by Tassiulas et al in 1992, is a beautiful and simple concept to achieve the

entire throughput region; but it is known to provide typically suboptimal delay performance.

Very recently developed ideas on policy design called Generalized MaxWeight shall be used to improve on network performance including potentially network coding. Moreover, this proposal addresses the inherent resource allocation problem for multiple antennas typically involving non-convex rate regions. Accordingly, such problems are hard to tackle and will be investigated within non-convex optimization framework.

Outcome of this research is a new philosophy for policy design aiming to assess the impact of network coding on routing, scheduling, and even buffering in networks.

State of the Art

Wireless networks (cellular, mesh, ad hoc etc.) have emerged as an ubiquitous source of innovation with intriguing applications over the last decade. One of the many reasons for this economic success is the inherent support of mobility by exploiting free-space electromagnetic wave propagation. However, these advantages come at a cost: since channel access is often uncoordinated, communicating terminals transmit at the same time so that their individual transmit signals interfere with each other; random data traffic, random channel conditions and varying network topologies complicate the situation. Traditionally, communication engineers have considered the effect of mobility as a burden; nowadays, it is more seen as a remedy potentially boosting the capacity of wireless networks. This is because communication links can be established (or shut down) via resource allocation which, combined with sophisticated transmitter/receiver signal processing and routing, creates an ocean of possible communication protocols. Until now, the general capacity problem remains still unsolved.

Research Objectives

The general research direction of this proposal is to follow the path of the MaxWeight routing and scheduling policy and develop the theory into several new directions. Overall, the research proposal is divided into three working packages:

1. In the first working package preliminary work [1,2] in the context of broadcast channels shall be brought into the context of general wireless networks. Here, several problems need to be addressed: even though the results fundamentally characterize stable scheduling strategies in a wireless broadcast setting it is not immediately clear how this works in a network setting with routing. In the second phase of this package the analysis should be brought into the context of controlled queuing networks.

2. In the second working package the resource allocation in the generalized MaxWeight policy should be extended towards non-convex rate regions. Here very recent ideas regarding monotonic global optimization problems shall be used and extended to design new algorithms reflecting the non-convex nature of multiple antenna systems.

3. Finally, in the third package new network coding structures shall be incorporated.


Dr. Gerhard Wunder



Dr.-Ing. habil. Gerhard Wunder, Privatdozent

Fraunhofer German-Sino Lab for Mobile Communications MCI

Einsteinufer 37, D-10587 Berlin/Germany

Phone: +49(0)30-31002-872

Fax: +49(0)30-31002-863

wunder AT



C. Zhou G. Wunder.
Annual Allerton Conf. on Commun., Control and Computing
Monticello, USA
September 2008.


C. Zhou G. Wunder.
IEEE International Symposium on Information Theory (ISIT)


Gerhard Wunder, Martin Kasparick, Alexander Stolyar and Harish Viswanathan.
Self-Organizing Distributed Inter-Cell Beam Coordination in Cellular Networks with Best Effort Traffic.
Proc. 8th Intl. Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt '10)
June 2010.
Export as: BibTeX