Resource allocation in multi-hop wireless networks

Abstract

Wireless mesh networks, though very promising needs to be managed efficiently. By introducing new nodes and gateways, effort needs to be put on maximizing the performance of the network in order to reap the benefits of such networks.

In order to find a solution for this process, a column generation technique is utilized as the method to allocate resources to the various parts of the network. The original column generation technique aims towards finding the exact solution to the resource allocation problem. In this report, a greedy pricing approach is utilized which aims at reducing the time required to solve the problem by a huge margin and at the same time minimize the error as much as possible.

The entire resource allocation problem boils down to solve a big convex optimization problem. The objective of this problem is to maximize the minimum throughputs of all the flows. Hard convex optimization problems have been solved by stat-of-the-art solvers. But as the size of networks increases, it is difficult even for these solvers to get an efficient solution. This warrants for some form of decomposition or column generation. The aim is to solve a hard, but small pricing sub-problem, the result of which is utilized in solving a master problem using the solvers.

The project is directed towards developing a software infrastructure which facilitates this entire process of optimized resource allocation. The project creates a necessary framework to describe the network aspects in a solid format, which is later utilized in the column generation technique. This project also covers the linking of the program with state-of-the-art solvers and solving small problems to understand the basic efficiency and accuracy of the algorithm and the implementation. This project also uses a utility C++ library called LEMON, which helps in interfacing with the solver API. Understanding the key aspects of the network model of a multi-hop wireless networks and implementing it along with the column generation technique is the key objective of this report and this project.