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.

**ABSTRACT**

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