PhD Defense: "Automated Design of Optimal Medium Access Control Protocols for Wireless Networking"

Jian Zhen

March 21st (Friday), 10:00am
Harold Frank Hall (HFH), Rm 4164

We present a framework for the automated design of optimal Medium Access Control (MAC) protocols.

First, we describe a methodology that incorporates the impact of control information transfer into MAC protocol optimization. We apply this methodology to the problem of a synchronous broadcast MAC channel in order to generate the optimal protocol when the objective function is the average network throughput per slot. We describe a recursive procedure for the symbolic generation of the optimization program for any choice of the objective function. We demonstrate that this methodology subsumes two structurally different types of protocols, namely, pure Random Access protocols and protocols with data advertisements, as special cases in the regimes where they are optimal. We examine the scaling of the optimal throughput and that of computational complexity as a function of the number of nodes and the control lifetime.

Second, we generate optimal MAC protocols based on a more advanced MAC model that incorporates multiple MAC neighborhoods as well as acknowledgments. In this model, both the advertisement and acknowledgment packets are automatically generated by an optimization program that is built based on \emph{symbolic} Monte Carlo simulation. The design flow chain produces an optimal MAC protocol with respect to any desired objective function.

Third, we formulate the automated optimal MAC protocol generation problem for dynamic topologies, as encountered in wireless ad hoc networks, under multiple neighborhoods and in the presence of acknowledgments. The probability distribution over the set of local topologies encountered in the global network serves as a model for which an optimization program may be formulated that takes the per-node average throughput as its objective function. Symbolic Monte Carlo simulation is used to generate the optimization program, which is subsequently solved via state-of-the-art nonlinear solvers. A quantitative comparison with RTS/CTS provides information on the value of side information on the probability distribution of local topologies, which RTS/CTS does not presume. The results on computational complexity show that the time to generate the program dominates over the time to solve the resulting non-linear program, and that the complete program can be solved within reasonable computational time.

Fourth, we formulate the automated optimal MAC protocol generation problem under dynamic traffic conditions for multiple neighborhoods and in the presence of acknowledgments. We show that the problem can be formulated as a functional optimization program in which each design (a.k.a. decision) function of the program is the probability that a node takes an action given its knowledge state, as a function of the effective traffic demand at the current time at that node. In order to achieve a viable computational complexity for the functional optimization program, we discretize the effective traffic demands by virtue of which a look-up table is produced for each design function. Structurally different MAC protocols are subsumed in this framework, and are generated automatically with respect to traffic demand. The symbolic Monte Carlo method is used to generate an approximate expression for the objective function as well as for the non-linear constraints, in a manner that trades off accuracy versus computational complexity. Symbolic simulation results are presented for a fixed network topology under the assumption of Poisson traffic. The objective is to minimize the average power consumption of a node subject to a minimum average throughput constraint that incorporates soft delay guarantees. The results demonstrate that a MAC protocol that incorporates acknowledgments in a multi-hop setting under dynamic traffic can be generated automatically.

The results of this thesis opens the way for the design of an automated design flow chain for network protocols that are based only on local information, of which MAC protocols constitute an example. In the future, this framework may be integrated as a “back end” to Software Defined Networks (SDN’s) which are envisioned to run on optimizable protocols as the ones described in this thesis.

About Jian Zhen:

photo of jian zhen Jian Zhen is a Ph.D. candidate in the Electrical and Computer Engineering Department at University of California, Santa Barbara and is guided by Professor Volkan Rodoplu. He received his B.S. and Dipl. Ing. in Electrical Engineering (Elektrotechnik und Informationstechnik) from Technical University of Munich, Germany in 2008 and joined the Rodoplu group in 2009. As part of his graduate research work, he has worked on wireless protocol design and optimization, mainly on automated design of optimal medium access control protocols for wireless networking.

He was the recipient of the ECE Dissertation Fellowship in Spring 2013.

Hosted by: Professor Volkan Rodoplu