Source Routing in Time-Varing Lossy Networks

This paper addresses the path selection problem arising in multi-hop sensor networks, e.g., Smart Grids. A set of multi-hop paths, of varying transmission quality, connect source and destination nodes. The source must select one path for each message to send without knowing the state of the hops. It can however use information deduced from earlier transmissions to decide on a good path for the current message. The goal is to maximize the discounted number of successfully delivered messages. We prove that the myopic routing policy, arguably the most appealing known way to tackle this problem, can permanently ignore good paths. We also generalize an empirically proven good approach, the Whittle index, and show its intractability for the problem at hand. We propose a new tractable metric, Harmonic Discounted Index (HDI), as a measure of attractiveness of transmitting over a path. We evaluate the performance of our HDI metric in a variety of simulation scenarios revealing a superior performance compared to all alternative index policies.