On Spectrum-Efficient Routing and Power Allocation in a Multihop Network of Passive Backscatter Tags

Motivated by advances in energy harvesting and Internet-of-Things (IoT) technologies, this article addresses the joint spectrum-efficient routing and power allocation problem in wireless networks of passive tags that communicate over multihop tag-to-tag paths by backscattering signals from an ambient radio frequency (RF) source. Our objective is to find the path from a source to a destination that minimizes the ambient source transmit power while satisfying an end-to-end spectral efficiency constraint. We formulate the problem as a mixed-integer nonlinear program (MINLP), and to the best of our knowledge, for the first time, formally prove that the problem is NP-complete. This is mainly due to the existence of two sets of constraints, an end-to-end spectral efficiency constraint, and power constraints for successful backscattering. We demonstrate that relaxing either constraint leads to a polynomially solvable relaxation of the original problem. This leads to two polynomially solvable lower bounds, two polynomially solvable special cases, as well as two polynomial-time heuristics to the original NP-complete problem. Moreover, we demonstrate that both algorithms can be implemented simultaneously using a modified Bellman-Ford shortest path algorithm. In contrast, we show that the best-effort variant, of maximizing the end-to-end spectral efficiency given fixed ambient source transmit powers, is polynomially solvable. Our computational results illustrate an average reduction of ambient transmit power by 16.1 dB as compared to routing along the direct link, while the algorithm performance closely follows that of a pruned exhaustive search benchmark.

Automated summary

This article addresses the joint spectrum-efficient routing and power allocation problem in wireless networks of passive tags, proving that the problem is NP-complete. The study introduces polynomially solvable lower bounds, special cases, and heuristics to solve the original NP-complete problem. Experimental results show an average reduction of 16.1 dB in ambient transmit power with algorithm performance comparable to a pruned exhaustive search benchmark.