Game-theoretic models for reliable path-length and energy-constrained routing with data aggregation in wireless sensor networks

Path length, path reliability, and sensor energy-consumption are three major constraints affecting routing in resource constrained, unreliable wireless sensor networks. By considering the implicit collaborative imperative for sensors to achieve overall network objectives subject to individual resource consumption, we develop a game-theoretic model of reliable, length and energy-constrained, sensor-centric information routing in sensor networks. We define two distinct payoff (benefit) functions and show that computing optimally reliable energy-constrained paths is NP-Hard under both models for arbitrary sensor networks. We then show that optimal length-constrained paths can be computed in polynomial time in a distributed manner (using O(E) messages) for popular sensor network implementations using geographic routing. We also develop sensor-centric metrics called path weakness to measure the qualitative performance of different routing schemes and provide theoretical limits on the inapproximability of computing paths with bounded weakness. Heuristics for computing optimal paths in arbitrary sensor networks are described along with simulation results comparing performance with other routing algorithms.