On distributed multiple access control for wireless sensor networks

We consider the problem of efficiently “emptying” a wireless sensor network that has accumulated a large amount of data at its nodes and seeks to relay them to designated gateways so as to maximize a concave function of achievable transmission rates. Transmissions are subject to physical communication constraints, interference constraints, and fairness constraints. We adopt a framework where transmissions are scheduled (instead of randomly initiated) and formulate the problem as an optimization problem. Due to its structure the formulation grows exponentially with the size of the network. We devise polynomial-time algorithms for maximizing weighted throughput in some special network topologies (stars and trees) which, under some additional assumptions, admit analytical solutions. For more general networks, we build on the decomposition framework proposed in our prior work and develop a decentralized polynomial-time algorithm for solving a key subproblem. This leads to a decentralized algorithm for computing the schedule guided by some “light” centralized computations.