Optimal routing and resource allocation in multi-hop wireless networks

Elisa Castorini*, Paolo Nobili, Chefi Triki

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


This paper addresses the problem of simultaneously optimizing power consumption and routing in multi-hop wireless networks while forcing the satisfaction 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 both the power and link capacity levels are suitably 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.

Original languageEnglish
Pages (from-to)593-608
Number of pages16
JournalOptimization Methods and Software
Issue number4
Publication statusPublished - Aug 2008
Externally publishedYes


  • Column-generation
  • Multi-hop wireless networks
  • Optimal routing
  • Power and capacity allocation

ASJC Scopus subject areas

  • Software
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'Optimal routing and resource allocation in multi-hop wireless networks'. Together they form a unique fingerprint.

Cite this