A greedy randomized algorithm for the cooperative communication problem on ad hoc networks

An ad hoc network is a system of mobile nodes that communicate through the use of wireless links. Due to the lack of central authority, ad hoc networks have non-fixed topology, and their communication pattern depends on the actual position of individual nodes. This characteristic presents a great challenge for some fundamental design tasks such as ensuring connectivity, robustness, and proper routing over the network. In this paper, we propose a heuristic for maximizing connectivity, based on the greedy randomized adaptive search algorithm (GRASP) of Feo and Resende. The algorithm provides a quick way of determining solutions for the problem without the necessity of a full scale enumerative algorithm. The solutions provided by the resulting algorithm are close to the optimal for most of the tested instances.