Joint Routing and Medium Access Control for Lifetime Maximization of Distributed Wireless Sensor Networks

A joint routing and medium access control (MAC) algorithm is proposed for lifetime maximization of distributed wireless sensor networks. By adopting the flow contention graph model and the resulting MAC constraints, the problem can be formulated into a linear program (LP) with separable structure, which can be solved distributively using dual decomposition. However, the message passing overhead of such a solution is still high, since the information exchange must occur among the interfering links as well as the communicating links. In this work, the MAC layer constraints are relaxed in the form of a penalty function, which facilitates distributed optimization using only the collision statistic that each node can accumulate essentially at no extra cost. The resulting algorithm solves a convex optimization problem by a distributed primal-dual approach, where the network layer problem is solved in the dual domain, and the MAC layer problem is solved in the primal domain.