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.

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

FESTA, PAOLA;
2006

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/118625
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact