Optimized Scheduled Multiple Access Control for Wireless Sensor Networks

We consider wireless sensor networks with multiple sensor modalities that capture data to be transported over multiple frequency channels to potentially multiple gateways. We study a general problem of maximizing a utility function of achievable transmission rates between communicating nodes. Decisions involve routing, transmission scheduling, power control, and channel selection, while constraints include physical communication constraints, interference constraints, and fairness constraints. Due to its structure the formulation grows exponentially with the size of the network. Drawing upon large-scale decomposition ideas in mathematical programming, we develop a cutting-plane algorithm and show that it terminates in a finite number of iterations. Every iteration requires the solution of a subproblem which is NP-hard. To solve the subproblem we i) devise a particular relaxation that is solvable in polynomial time and ii) leverage polynomial-time approximation schemes. A combination of both approaches enables an improved decomposition algorithm which is efficient for solving large problem instances.