Energy Complexity of Distance Computation in Multi-hop Networks
share
Energy efficiency is a critical issue for wireless devices operated under stringent power constraint. Following prior works, we measure the energy cost of a device by its transceiver usage, and the energy complexity of an algorithm is defined as the maximum number of time slots a device transmits or listens, over all devices. In a recent paper of Chang et al. (PODC 2018), it was shown that broadcasting in a multi-hop network of unknown topology can be done in poly n energy. In this paper, we continue this line of research, and investigate the energy complexity of other fundamental graph problems in multi-hop networks. Our results are summarized as follows. 1. To avoid spending Ω(D) energy, the broadcasting protocols of Chang et al. (PODC 2018) do not send the message along a BFS tree, and it is open whether BFS could be computed in o(D) energy, for sufficiently large D. In this paper we devise an algorithm that attains Õ(√(n)) energy cost. 2. We show that the framework of the Ω(n /^2 n) round lower bound proof for computing diameter in CONGEST of Abboud et al. (DISC 2017) can be adapted to give an Ω̃(n / ^3 n) energy lower bound in the wireless network model (with no message size constraint), and this lower bound applies to O( n)-arboricity graphs. From the upper bound side, we show that the energy complexity of Õ(√(n)) can be attained for bounded-genus graphs (which includes planar graphs). 3. Our upper bounds for computing diameter can be extended to other graph problems. We show that exact global minimum cut or approximate s--t minimum cut can be computed in Õ(√(n)) energy for bounded-genus graphs.
READ FULL TEXT