Improving the Speed of Dynamic Cluster Formation in Manet via Simulated Annealing

Improving the Speed of Dynamic Cluster Formation in Manet via Simulated Annealing

Title : Improving the Speed of Dynamic Cluster Formation in Manet via Simulated Annealing
Authors :
Manousakis, Kyriakos
Baras, John, S.
Conference : 24th Army Science Conference (ASC2004)
Date: November 29 - December 02, 2004
Journal : pp 1-8
December 02, 2004

Future military systems, such as FCS, require a robust and flexible network that supports thousands of ad hoc nodes. Therefore, networking protocols for MANETs must be made to scale. The use of hierarchy is a powerful general solution to the scaling problem. We have previously proposed methods based on Simulated Annealing (SA) to optimize hierarchy in MANETs. The challenge, however, is to improve the slow convergence time of SA, so it can be used in dynamic environments, without penalizing optimality. In previous work, the importance of parameters such as cooling schedule, state transition probabilities, and convergence condition are investigated. This paper proposes a new approach to decrease SA convergence time. SA is an optimization technique based on an iterative process that takes an initial solution, or map, to start the process. In this paper, we analyze the effect that this initial solution has on the SA convergence time as a function of the network size. We believe that the combined modifications to SA can speed the optimization process to the point that it can quickly generate very efficient clustering solutions in large dynamic networks.

Download Full Paper