Class12

Optimal control of multihop wireless networks provides an exciting context where well-established fields such as Optimization Theory, Stability Theory, Algorithms, Stochastic Optimization, etc., meet to provide design and analysis methods that lead to implementable policies. In this talk, I will provide an important example to this paradigm whereby the problem of efficient and fair communication for general multihop wireless networks is tackled. The wireless environment is different from its wireline counterpart in several key aspects that result in new challenges. In particular, the presence of interference of concurrent transmissions lead to a coupling between different link rates, which complicates the resource allocation decision. Moreover, the medium may have a time-varying nature which necessitates the use of a dynamic controller. Also, in certain scenarios where the transmitters have limited energy it is critical that the communication is performed with small power consumption. In this talk, I will present a polynomial-complexity, distributed algorithm that achieves 100% utilization of the system resources and guarantees fair rate allocation across all the flows that share the network resources. To that end, I will start with a brief overview of some important results that provide an answer to the problem of efficient resource allocation in wireless environments. Then, I will address the fairness issue and introduce a Cross-layer Flow Control-Scheduling algorithm based on a dual formulation of an associated optimization problem. Finally, I will focus on the problem of distributed implementation of the proposed strategy and provide a polynomial-complexity randomized algorithm that achieves full utilization and fair allocation of the resources. To the best of our knowledge, this is the first distributed algorithm that provides 100% throughput in multihop wireless networks.