OPTIMAL ROUTING AND RESOURCE ALLOCATION IN AD-HOC NETWORKS

Abstract. This paper addresses the problem of simultaneously optimizing power consumption and routing in ad-hoc networks while ensuring the satis-faction of the required transmission demands between given origin-destination pairs. We devise a linear programming model for the selection of optimal routes and transmission schemes where the power and link capacity levels are suit-ably discretized. Since the constraint matrix of such a model contains a huge number of columns, we propose an exact algorithm for its solution based on a column generation approach. The associated column generation procedure is based on the solution of linear integer programming models. We report some computational results on networks with up to 65 nodes, showing the feasibility of our solution approach