Applying simulated annealing for domain generation in ad hoc networks

If heterogeneous ad hoc battlefield networks are to scale to hundreds or thousands of nodes, then they must be automatically split into separate network domains. Domains allow routing, QoS and other networking protocols to operate on the fewer nodes. This division greatly reduces the overall overhead (e.g., routing overhead with n nodes that goes from O(n²) to O(nlogn) and allows protocols to be tuned to more homogenous conditions (K. Manousakis et al., 2002). Domain generation (or clustering) can be done using either the local or global information. The two approaches are complementary since local domain generation reacts faster, requires less overhead, and is more robust while the global domain generation provides better overall domains. While the most existing work has concentrated on the local distributed solutions, this paper reports on the new global domain generation techniques. In particular we concentrate on the design of good cost functions and efficient optimization algorithms. We show that the simple "intuitive" cost functions do not produce good domains; rather we need complex functions with multiple parameters depending on the design goals (e.g., low overhead or low delay). Although existing optimization algorithms are too slow to be useful in a large dynamic network, we show that a modified simulated annealing algorithm with well chosen cooling schedule, state transition probabilities, and stop criteria produces good quality domains in acceptable time.