Joint Topology Design and Frequency Allocation for Fixed Wireless SDR Networks

This paper considers the problem of connecting a collection of nodes to a backbone network. Each node may be directly connected to the backbone, at some cost, or it may communicate wirelessly to a directly connected hub and share its connection, at the "cost" of using spectrum for the wireless link. This problem arises in diverse areas such as cellular network backhaul and overlays of ad-hoc networks and wide area networks. We consider the joint problem of designing the topology and the frequency assignment at the same time, to minimize both cost and spectrum usage. We formulate the problem as an ILP and show that the complexity requirements make an exact solution infeasible. We then derive two heuristics one based on simulated annealing, the other based on greedy graph matchings and show that we are able to obtain nearly optimal solutions at significantly reduced complexity.