Optimal design of wireless Ad-hoc networks

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.