Optimal Scheduling for Link Assignment in Traffic-Sensitive STDMA Wireless Ad-Hoc Networks

摘要

In this paper, we consider the resource optimization problem to maximize the network throughput by efficiently using the network capacity, where multi-hop functionality and spatial TDMA access scheme are used. The objective is to find the minimum frame length with given traffic distributions and corresponding routing information. Because of the complex structure of the underlying mathematical problem, previous work and analysis become intractable for networks of realistic sizes.We address the problem through mathematical programming approach, develop the linear integer formulation optimizing the network throughput, and then show the similarity between the original problem and the graph edge coloring problem through the conflict graph concept. We propose a column generation solution approach and make several enhancements in order to fasten its convergence. Numerical results demonstrate that the theoretical limit of the throughput can be efficiently computed for networks of realistic sizes.