Automated MAC protocol generation for dynamic topologies

We formulate the automated 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. Since the state space of the model is very large, the main challenge is the generation of the optimization program via automated methods. 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.