Energy conserving routing in wireless ad-hoc networks

TLDR

An ad‑hoc wireless sensor network with static nodes generates data that must reach gateway nodes, using multi‑hop forwarding while each node adjusts transmission power within a limited range and consumes energy at rates dependent on power level and receiver. We propose algorithms that jointly select routes and transmission power levels to maximize the time until node batteries are depleted. The algorithms are local and suitable for distributed implementation. For a single power level the problem reduces to a maximum‑flow formulation with node capacities and the algorithms converge to the optimal solution; with multiple power levels the achieved lifetime is close to the linear‑programming optimum, and maximizing lifetime requires routing that balances energy consumption among nodes in proportion to their remaining reserves rather than simply minimizing absolute power.

Abstract

An ad-hoc network of wireless static nodes is considered as it arises in a rapidly deployed, sensor-based, monitoring system. Information is generated in certain nodes and needs to reach a set of designated gateway nodes. Each node may adjust its power within a certain range that determines the set of possible one hop away neighbors. Traffic forwarding through multiple hops is employed when the intended destination is not within immediate reach. The nodes have limited initial amounts of energy that is consumed at different rates depending on the power level and the intended receiver. We propose algorithms to select the routes and the corresponding power levels such that the time until the batteries of the nodes drain-out is maximized. The algorithms are local and amenable to distributed implementation. When there is a single power level, the problem is reduced to a maximum flow problem with node capacities and the algorithms converge to the optimal solution. When there are multiple power levels then the achievable lifetime is close to the optimal (that is computed by linear programming) most of the time. It turns out that in order to maximize the lifetime, the traffic should be routed such that the energy consumption is balanced among the nodes in proportion to their energy reserves, instead of routing to minimize the absolute consumed power.