UC Santa Barbara

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

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 time 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 of the regimes where they are optimal. We examine the scaling of the optimal throughput and the computational complexity as a function of the number of nodes and the control lifetime.

Second, we generate optimal MAC protocols based on a more general MAC model that incorporates multiple MAC neighborhoods as well as acknowledgments. In this model, both the advertisement and acknowledgment frames are automatically generated by an optimization program that is built based on symbolic Monte Carlo simulation. The design flow chain produces an optimal MAC protocol with respect to the 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 the standard RTS/CTS protocol provides information on the value of side information on the probability distribution of local topologies, which RTS/CTS does not presume. Our investigations of 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 a 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 can be represented 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. Our research demonstrates that a MAC protocol that incorporates acknowledgments in a multi-hop setting under dynamic traffic can be generated automatically.

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, our framework can 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.