Maximizing Energy Efficiency for Convergecast via Joint Duty Cycle and Route Optimization

The energy efficiency of the widely used convergecast pattern depends substantially on the choice of medium access control (MAC) and routing protocol. In this paper, we formalize the maximization of convergecast energy efficiency with respect to its MAC and routing as a resource constrained optimization problem. We then analytically show that this maximization problem is linear in the context of two prototypical MACs - a locally synchronized wakeup (as in S-MAC) and a locally staggered wakeup MAC (as in O-MAC) - assuming low, uniform traffic that is delivered reliably and without interference. With this insight, we present a centralized algorithm, MeeCast, that solves the optimization problem utilizing linear programming techniques. We also design a distributed version of MeeCast, for the case where the traffic is ultra-low, and prove that it achieves optimality as well as fast convergence time. Notably, this version is self-stabilizing, so it autonomically handles changes in traffic load, network topology, loss of coordination and state corruption. In comparison with Dozer, a state-of-the-art convergecast protocol, MeeCast achieves better energy efficiency and application lifetime in the context of S-MAC and identical energy efficiency but better application lifetime in the context of O-MAC.