Efficient Algorithms to Solve a Class of Resource Allocation Problems in Large Wireless Networks

Jun Luo; Andre Girard; Catherine Rosenberg

7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks

Research Article

Efficient Algorithms to Solve a Class of Resource Allocation Problems in Large Wireless Networks

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/WIOPT.2009.5291604,
    author={Jun Luo and Andre Girard and Catherine Rosenberg},
    title={Efficient Algorithms to Solve a Class of Resource Allocation Problems in Large Wireless Networks},
    proceedings={7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks},
    publisher={IEEE},
    proceedings_a={WIOPT},
    year={2009},
    month={10},
    keywords={Resource Allocation Optimization Column Generation Link Scheduling On-Off Scheduling},
    doi={10.1109/WIOPT.2009.5291604}
}

Jun Luo
Andre Girard
Catherine Rosenberg
Year: 2009
Efficient Algorithms to Solve a Class of Resource Allocation Problems in Large Wireless Networks
WIOPT
IEEE
DOI: 10.1109/WIOPT.2009.5291604

Jun Luo¹^,*, Andre Girard²^,*, Catherine Rosenberg³^,*

1: School of Computer Engineering Nanyang Technological University Singapore 639798
2: Groupe d’ ´ Etudes et de Recherche en Analyse des D´ecisions Montreal, Canada H3T 2A7
3: Department of Electrical and Computer Engineering University of Waterloo Waterloo, Canada N2L 3G1

*Contact email: junluo@ntu.edu.sg, andre.girard@gerad.ca, cath@ecemail.uwaterloo.ca

Abstract

We focus on efficient algorithms for resource allocation problems in large wireless networks. We first investigate the link scheduling problem and identify the properties that make it possible to compute solutions efficiently. We then show that the node on-off scheduling problem shares these features and is amenable to the same type of solution method. Numerical results confirm the efficiency of our technique for large scale problems. We also extend the technique to the case where the objective function is nonlinear showing that our technique blends smoothly with a sequential linear programming approach. Numerical results for a cross-layer design with a nonlinear fairness utility show that it is possible to compute optimal solutions for large wireless networks in reasonable CPU time.

Keywords: Resource Allocation Optimization Column Generation Link Scheduling On-Off Scheduling

Published: 2009-10-23
Publisher: IEEE
Modified: 2010-05-16

: http://dx.doi.org/10.1109/WIOPT.2009.5291604