A one-pass heuristic for cooperative communication in mobile ad hoc networks

C.W. Commander, C.A.S. Oliveira, P.M. Pardalos, and M.G.C. Resende

Cooperative Systems: Control and Optimization,  D.A. Grundel, R.A. Murphey, P.M. Pardalos, and O.A. Prokopyev (editors), pp. 285-296, Springer, 2007.


Ad hoc networks have been used in the last few years to provide communications means among agents that need to accomplish common goals. Due to the importance of communication for the success of such missions, we study the problem of maximizing communication among a set of agents. As a practical tool to solve such problems, we introduce a one-pass randomized algorithm that maximizes the total communication, as measured by the proposed objective function. Agents in this problem are routed along the edges of a graph, connecting their individual starting nodes to their respective destination nodes. This problem, known as the Cooperative Communication Problem in Mobile Ad Hoc Networks, is known to be NP-hard. We present a new heuristic and motivate the need for more advanced methods for the solution of this problem. In particular, we describe 1) a construction algorithm and 2) a local improvement method for maximizing communication. Computational results for the proposed approach are provided, showing that instances of realistic size can be efficiently solved by the algorithm.

PDF file of paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 12 June 2008

Copyright Notice