Constrained Node Placement and Assignment in Mobile Backbone Networks
Abstract
This paper describes new algorithms for mobile backbone network optimization. In this hierarchical communication framework, mobile backbone nodes (MBNs) are deployed to provide communication support for regular nodes (RNs). While previous work has assumed that MBNs are unconstrained in position, this work models constraints in MBN location. This
paper develops an exact technique for maximizing the number
of RNs that achieve a threshold throughput level, as well as a polynomial-time approximation algorithm for this problem. The approximation algorithm carries a performance guarantee of 12, and we demonstrate that this guarantee is tight in some problem instances.