Ad-hoc networks are a new paradigm for communications systems in which wireless nodes can freely connect to each other without the need of a pre-specified structure. Difficult combinatorial optimization problems are associated with the design and operation of these networks. In this paper, we consider the problem of maximizing the connection time between a set of mobile agents in an ad-hoc network. Given a network and a set of wireless agents with starting nodes and target nodes, the objective is to find a set of trajectories for the agents that maximizes connectivity during their operation. This problem, referred to as the COOPERATIVE COMMUNICATION ON AD-HOC NETWORKS is known to be NP-hard. We look for heuristic algorithms that are able to efficiently compute high quality solutions to instances of large size. We propose the use of a greedy randomized adaptive search procedure (GRASP) to compute solutions for this problem. The GRASP is enhanced by applying a path-relinking intensification procedure. Extensive experimental results are presented, demonstrating that the proposed strategy provides near optimal solutions for the 900 instances tested.
Grasp with Path-Relinking for the Cooperative Communication Problem on ad-hoc Networks / C. W., Commander; Festa, Paola; C. A. S., Oliveira; P. M., Pardalos; M. G. C., Resende; M., Tsitselis. - STAMPA. - (2008), pp. 187-207.
Grasp with Path-Relinking for the Cooperative Communication Problem on ad-hoc Networks
FESTA, PAOLA;
2008
Abstract
Ad-hoc networks are a new paradigm for communications systems in which wireless nodes can freely connect to each other without the need of a pre-specified structure. Difficult combinatorial optimization problems are associated with the design and operation of these networks. In this paper, we consider the problem of maximizing the connection time between a set of mobile agents in an ad-hoc network. Given a network and a set of wireless agents with starting nodes and target nodes, the objective is to find a set of trajectories for the agents that maximizes connectivity during their operation. This problem, referred to as the COOPERATIVE COMMUNICATION ON AD-HOC NETWORKS is known to be NP-hard. We look for heuristic algorithms that are able to efficiently compute high quality solutions to instances of large size. We propose the use of a greedy randomized adaptive search procedure (GRASP) to compute solutions for this problem. The GRASP is enhanced by applying a path-relinking intensification procedure. Extensive experimental results are presented, demonstrating that the proposed strategy provides near optimal solutions for the 900 instances tested.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
