A Channel Assignment and Routing Algorithm for Energy Harvesting Multi-Radio Wireless Mesh Networks

Wireless mesh networks are being deployed all around the world both to provide ubiquitous connection to the Internet and to carry data generated by several services (video surveillance, smart grids, earthquake early warning systems, etc.). In those cases where fixed power connections are not available, mesh nodes operate by harvesting ambient energy (e.g., solar or wind power) and hence they can count on a limited and time-varying amount of power to accomplish their functions. Since we consider mesh nodes equipped with multiple radios, power savings and network performance can be maximized by properly routing flows, assigning channels to radios and identifying nodes/radios that can be turned off. Thus, the problem we address is a joint channel assignment and routing problem with additional constraints on the node power consumption, which is NP-complete. In this paper we propose a heuristic, named MP-CARA (Minimum Power Channel Assignment and Routing Algorithm), which is guaranteed to return a local optimum for this problem. Based on a theoretical analysis that we present in the paper, which gives an upper bound on the outage probability as a function of the constraint on power consumption, we can guarantee that the probability that a node runs out of power with MP-CARA falls below a desired threshold. The performance of MP-CARA is assessed by means of an extensive simulation study aiming to compare the solutions returned by MP-CARA % both to those found by other heuristics and to the optimal solutions obtained by solving two Mixed Integer Linear Programs (MILPs) presented in this paper. to those found by other heuristics proposed in the literature.