Abstract

This paper addresses the challenge of attaining an optimal wireless spanning tree backbone with a dual focus: minimizing both the worst arc flow within the network and the overall tree structure. Our approach assumes node-to-node simultaneous communication and introduces mixed-integer linear programming formulations to tackle the problem. The primary formulation adopts the Miller-Tucker-Zemlin approach to derive the tree backbone. Additionally, we consider its exponential counterpart, characterized by its numerous constraints. To evaluate the models, we conduct a comparative analysis considering CPU processing times, solution qualities, and Mipgaps achieved. Subsequently, we explore scenarios where the emphasis is solely on minimizing the worst arc flow while omitting the tree backbone. Our initial numerical findings indicate that excluding the tree backbone from the input graph notably reduces the burden of worst arc flow. However, this benefit forces the need for a denser connected graph. So far, the computational experiments encompass instances with up to 25 nodes for both sparse and complete graphs. Finally, our study underscores the significance of the proposed models, well-suited for assessing diverse transmission flow-based scenarios while accommodating forthcoming technologies in the evolution of 5G, 5G+, and 6G future infrastructure networks.