Energy -efficient routing for multi-hop networks

Multi-hop networks have a broad range of applicability in both civilian and military environments that include sensing, communication, and computation. Such networks could have stringent energy constraints, and therefore the operational capabilities are fundamentally limited by the energy available at the nodes (radios). In the first part of our work, we model and characterize the performance of multi-hop radio networks in the presence of energy constraints, and design routing algorithms to optimally utilize the available energy. We develop an algorithm that achieves a competitive ratio (i.e., the ratio of the performance of any off-line algorithm that has knowledge of all past and future packet arrivals to the performance of our online algorithm) that is asymptotically optimal with respect to the number of nodes in the network. This algorithm assumes no statistical information on packet arrivals. In the second part of our work, we present a simple static multi-path routing approach that is optimal in the large-system limit. This static routing scheme exploits the knowledge of the traffic patterns and energy replenishment statistics, but does not need to collect instantaneous information on node energy. In the third part of our work, we study the problem of minimizing the total power consumption in a multi-hop wireless network subject to a given offered load. We develop a low-complexity and distributed algorithm that is provably power-efficient. Our algorithm is the first such distributed solution with a provable performance bound, and also improves upon the performance efficiency of centralized solutions in the literature.