Optimal design of wireless Ad-hoc networks

Shin Yi Wu, G. Anandalingam

Research output: Contribution to journalArticlepeer-review


This paper investigates the optimal design and deployment of wireless ad-hoc networks. Wireless ad-hoc networks are a new form of wireless communications that do not rely on any fixed infrastructure like wired base stations to keep the network up and running. Instead, hosts in a wireless ad-hoc network rely on each other to keep the network connected over either radio or infrared. Since direct communication is allowed only between adjacent nodes, distant nodes in an ad-hoc network communicate over multiple hops. We examine the optimal design of such networks by modeling the problem as a mixed integer mathematical program, and deriving solution procedures based on Lagrangean Relaxation (LR). Using the LR, we were able to decompose the network design problem into two fairly-easy-to-solve sub-problems. We present algorithms for each sub-problem, and an overall heuristic based on LR to solve the design problem. From the computational experiments we have done, our Lagrangean relaxation based algorithms can generate solutions within 2.20-13.16% of optimality. In addition, our algorithm also solves the design problem very rapidly, within a few minutes in the most complex case.

Original languageEnglish (US)
Pages (from-to)47-64
Number of pages18
JournalOperations Research/ Computer Science Interfaces Series
StatePublished - 2003
Externally publishedYes


  • Heuristic
  • Integer programming
  • Lagrangean relaxation
  • Network design
  • Subgradient method
  • Wireless Ad-hoc network

ASJC Scopus subject areas

  • Computer Science(all)
  • Management Science and Operations Research


Dive into the research topics of 'Optimal design of wireless Ad-hoc networks'. Together they form a unique fingerprint.

Cite this